Make most things update post-dominance info and preserve it.
Our other alternative to not take up too much time seems to be invasive
surgery on how BB successors/predecessors work so they are a constant time
array. I say this because GCC recomputes post-dominators roughly 15-19
times per compilation, and can do it about 3-5x faster than we can. All
profiling i've done basically says all our time is spent trying to get at
successors and predecessors in dominance/post-dominance respectively, which
takes basically no time in gcc, because the edge lists are an array.
(Note that if you look at generic dominance code, like
http://www.cs.princeton.edu/~rwerneck/dominators/, it's much faster than
what we do on the same graphs. This is true even though we use the same
algorithms .....)
Given it seems unlikely we are going to change the internal representation
anytime soon (or at least i've not seen a proposal), updating post-dom
seems the easier answer.
Are we talking about the basic-blocks edges only?
Yes. Only the successor and predecessors.
I'm not sure changing the IR for the BBs would be a lot more work than
preserving dominance analysis everywhere, or I am totally underestimating
one / overestimating the other?
The way "edges" work right now is that it walks the use/users lists. In
the case of predecessors, it walks the user list of the bb, and sees which
ones are terminator instructions, and then hands you the parent bb's of
those.
In the case of successor, the operand array stores it, but it requires some
indirect loads per successor.
The advantage to this scheme is that if you set the operand of the
terminator, you've updated the edge. It requires no other work.
Chandler was strongly against edge cuts not being super-fast constant
time[1]
If you move to edge arrays, it now requires finding and updating the
terminators, unless you keep them both as use lists somehow (which are
still about 1.5-2x as slow as straight arrays for dominators purposes), or
always have the appropriate terminator around.
In any case, it's really hard to have a case where you don't have to
update some stuff on edge redirection, even if you can store stuff to do it
in constant time.
For example, you would have to keep an array of (bb, index in succ/pred
array) and (terminators, operandno) or something similar to give you
constant time cutting (because you have to update both ends, so you need to
know where everything is both directions from whatever list you are looking
at)
if you can deal with linear time this is much easier.
[1]I don't think it matters as much as he does. They don't happen that
often, and even in the case of bugpoint, most blocks do not have a ton of
edges, so it won't slow much down for bugpointing real programs. The
significantly better cache behavior may even make up for it in practice.
