Certain transformations, like tail-duplication (Bug 174) and the correlated expression elimination pass, fundamentally need to make arbitrary changes to the CFG _AND_ update the SSA form of expressions. To do this, they need to _update_ dominators and dominator frontiers as they change the CFG. Basically the dominator information passes need an 'addEdge/removeEdge' interface that clients can use to incrementally update the dominator information. There is a paper that describes how to do this: http://citeseer.nj.nec.com/sreedhar94efficient.html ... someone should implement it. Given this functionality, many other transformations would also be able to incrementally update dominator information, instead of recalculating it, which would speed up the optimizer as well. -Chris
Changing all of these bugs who do not have people looking at them to be assigned to "unassignedbugs", indicating that if someone is feeling ambitious, they can take ownership of the bug. If I stole your bug, and you still want it, feel free to take ownership back. -Chris
I would also like this for my pass in PR807. Unfortunately, my compiler theory is no match for this paper. What does it mean on page 14: "2. PseudoAffected: This set consists of any /proper/ descendant of a *PossiblyAffected* node." Assuming that I have the list of PossiblyAffected nodes, what are the proper descendants? Every node in the sub-tree?
Created attachment 390 [details] it compiles, but i've never run it. I tried to implement it and this is as far as I got.
Nick, If you're still interested in this, there's an expanded/clearer version of the paper at: http://citeseer.ist.psu.edu/sreedhar95incremental.html Otherwise, I might tackle this next time I need something to do. --Owen
Step #1 complete: Owen removed idom.
Implemented here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091005/088600.html Jump threading switched to use it here: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091005/088601.html
Chris, I don't think that solves _all_ of what this bug asks for. We're still lacking a generc dominato r update function.
As originator of the bug, I know what it was about. :) Updating domtree wasn't the point, that was seen as a way to get to SSA updates.
Would it be worthwhile to split dominator updates into a new PR? It still seems like a useful feature.
Why? If it existed, we still wouldn't use it in the standard optimizer (too slow). Lets wait until there is an actual reason to have it.