Page MenuHomePhabricator

Makes incremental dominator calculation in Loop Unroll pass

Authored by sepavloff on Jan 13 2017, 6:07 AM.



Loop unroller contains code that tries to update dominator tree on fly,
but eventually it calculates the tree from scratch for entire function.
If there are many loops in the function the compilation may be slow down.
Also inconsistent dominator info prevents from loop verification during

This change implements incremental dominator tree update.

Part of this change (files Debug.h, LoopInfo.cpp and Dominators.cpp) is
independent from the rest of the patch, it implements changes required
to make testing of the dominator calculation.

Verifications of dominator tree and loop info are expensive operations
so they are disabled by default. They can be enabled by command line
options -verify-dom-info and -verify-loop-info. These options however
enable checks only in files Dominators.cpp and LoopInfo.cpp. If some
transformation changes dominaror tree and/or loop info, it would be
convenient to place similar checks to the files implementing the
transformation. By making corresponding flags global the verification
can be turned on optionally, even if expensive checks were not enabled
during build.

Event Timeline

sepavloff updated this revision to Diff 84291.Jan 13 2017, 6:07 AM
sepavloff retitled this revision from to Makes incremental dominator calculation in Loop Unroll pass.
sepavloff updated this object.
sepavloff added reviewers: mzolotukhin, atrick, mkuper.
sepavloff added subscribers: llvm-commits, davide.
mkuper edited edge metadata.

This looks like it has a lot of overlap with D28073.
Please sync with Eli.

One thing D28073 doesn't do is handle peeling (I guess mostly because Eli has better things to do than fix my code :-) ), so that's a part of this patch we want regardless. Added a couple of comments on that.


Why do you need the cast<Value>()?
Also, I'd a comment here that the reason VMap[IDom->getBlock()] is guaranteed to point to the right block is because the iteration order is RPO, so we've already made a copy of the IDom.


Do we really need to findNearestCommonDominator() here?
IIRC, we are guaranteed to be in loop-simplify form here, which means we have dedicated exit blocks. Can we figure out what the right IDom is without findNearestCommonDominator, a la D28073?

efriedma edited edge metadata.Jan 17 2017, 10:37 AM

Making a quick comparison between the two patches, the changes to LoopUnrollRuntime.cpp look almost identical. I think my version of the changes to the dominance calculation in LoopUnroll.cpp are more general. And obviously my changes to peeling don't actually dynamically update the domtree. I should probably merge the two loops in CloneLoopBlocks like this patch does.

Serge, do you have any other comments on my patch?

sepavloff abandoned this revision.Jan 17 2017, 9:51 PM

@mkuper - thank you for review and clarifications.

@efriedma - loop unrolling is a hot topic, things are changing too fast here, I somehow overlooked your patch, sorry. I agree, your treatment in LoopUnroll.cpp is more general, and don't think adding incremental update to LoopUnrollPeel.cpp will be a problem. The only advantage of my patch is testing, you are not going to add option unroll-peel-verify-domtree, right? :) But this is not related to loop unrolling, and probably deserves a separate patch. I think we should have possibility to provide verification flags to all tests in a test suite without need to alter the test sources. Other transformations may also gain from domtree and loop verification turned on.

Committed my changes in r292447; please rebase and submit your changes to loop peeling on top of that.