This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Incrementally update the dominator tree.
ClosedPublic

Authored by fhahn on Feb 12 2018, 2:53 AM.

Details

Summary

We can use incremental dominator tree updates to avoid re-calculating
the dominator tree after interchanging 2 loops.

Diff Detail

Event Timeline

fhahn created this revision.Feb 12 2018, 2:53 AM
fhahn updated this revision to Diff 133896.Feb 12 2018, 10:17 AM

Add DominatorTreeWrapperPass to preserved analysis.

fhahn updated this revision to Diff 133904.Feb 12 2018, 11:03 AM

Only update DT if DT != nullptr, add -verify-dom-info to a test.

efriedma added inline comments.
lib/Transforms/Scalar/LoopInterchange.cpp
465

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?

fhahn added inline comments.Feb 12 2018, 12:49 PM
lib/Transforms/Scalar/LoopInterchange.cpp
465

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

efriedma added inline comments.Feb 12 2018, 1:00 PM
lib/Transforms/Scalar/LoopInterchange.cpp
465

Okay.

You should probably make DomTree required, to simplify the code; you'll always have it anyway because LoopInfo requires it.

fhahn updated this revision to Diff 133929.Feb 12 2018, 2:11 PM

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
465

Right, done!

fhahn edited reviewers, added: kuhar; removed: kuba.Feb 13 2018, 7:06 AM
kuhar added inline comments.Feb 13 2018, 8:18 AM
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?

591

Is there a reason why the updates are applied int the destructor instead of at the end of this loop?

1282

const unsigned NumSucc?

1288

Can you have multiple successors that are the same BB? If so, you would have to exclude the redundant ones here.

fhahn updated this revision to Diff 134052.Feb 13 2018, 8:51 AM

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.

fhahn added inline comments.Feb 13 2018, 8:52 AM
lib/Transforms/Scalar/LoopInterchange.cpp
591

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.

1288

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

kuhar accepted this revision.Feb 13 2018, 9:42 AM

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
1285

for (unsigned i = 0, e = BI->getNumSuccessors(); i != e; ++i) {

1288

Looks fine, thanks!

This revision is now accepted and ready to land.Feb 13 2018, 9:42 AM
fhahn added a comment.Feb 13 2018, 9:47 AM

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.

This revision was automatically updated to reflect the committed changes.