We can use incremental dominator tree updates to avoid re-calculating
the dominator tree after interchanging 2 loops.
Details
Diff Detail
Event Timeline
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
457 | This list of preserved passes seems really short; at the very least, it should preserve GlobalsAA. Would be nice to preserve LoopInfo, LCSSA, and ScalarEvolution; I think the pass needs to preserve them anyway to interact correctly with itself? | |
test/Transforms/LoopInterchange/reductions.ll | ||
1 | Maybe add verify-dom-info to all the LoopInterchange tests? |
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
457 | Yes, making it preserve the DT is a first step. It indeed relies on LoopInfo, LCSSA, and ScalarEvolution being preserved too after interchanging 2 loops, for loop nests > 2. At least LoopInfo is not preserved properly at the moment. I plan to fix those issues in follow up commits. | |
test/Transforms/LoopInterchange/reductions.ll | ||
1 | Will do, thanks |
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
457 | Okay. You should probably make DomTree required, to simplify the code; you'll always have it anyway because LoopInfo requires it. |
Thanks again Eli! I've updated the patch to always preserve the DT and also added -verify-dom-info to the tests that interchange loops.
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
457 | Right, done! |
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
407 | Is this necessary? I guess you want to make the vector look clean in case a crash happens, is that it? | |
582 | Is there a reason why the updates are applied int the destructor instead of at the end of this loop? | |
1273 | const unsigned NumSucc? | |
1279 | Can you have multiple successors that are the same BB? If so, you would have to exclude the redundant ones here. |
Thanks! I've moved collecting and applying updates to adjustLoopLinks and added an assertion to make sure we do not have BBs with redundant successors.
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
582 | The first version of the patch had to collect updates from multiple code paths, but I've simplified things so there actually is no need to have DTUpdates as member variable. The only point where we adjust branches is in adjustLoopLinks, at the end we can apply the updates. I think we have to apply the updates after every transform, so we have a valid DT when we deal with loops with nests > 2. | |
1279 | That should never happen I think. I've added a break and also an assertion. Please let me know if this is exactly the case you meant |
Looks good to me now.
One last question: is DomTreeWrapperPass always available when LoopInterchange is run? I'm thinking about requireAnalysis vs. getAnalysisIfAvailable.
lib/Transforms/Scalar/LoopInterchange.cpp | ||
---|---|---|
1276 | for (unsigned i = 0, e = BI->getNumSuccessors(); i != e; ++i) { | |
1279 | Looks fine, thanks! |
Thanks!
One last question: is DomTreeWrapperPass always available when LoopInterchange is run? I'm thinking about requireAnalysis vs. getAnalysisIfAvailable.
Yep, LoopInterchange relies on LoopInfo, so the DT should be computed already.
Is this necessary? I guess you want to make the vector look clean in case a crash happens, is that it?