This is an archive of the discontinued LLVM Phabricator instance.

[LoopUnroll] Add support for loops with exiting headers and uncond latches.
ClosedPublic

Authored by fhahn on May 15 2019, 1:49 PM.

Details

Summary

This patch generalizes the UnrollLoop utility to support loops that exit
from the header instead of the latch. Usually, LoopRotate would take care
of must of those cases, but in some cases (e.g. -Oz), LoopRotate does
not kick in.

Codesize impact looks relatively neutral on ARM64 with -Oz + LTO.

Program master patch diff
External/S.../CFP2006/447.dealII/447.dealII 629060.00 627676.00 -0.2%
External/SPEC/CINT2000/176.gcc/176.gcc 1245916.00 1244932.00 -0.1%
MultiSourc...Prolangs-C/simulator/simulator 86100.00 86156.00 0.1%
MultiSourc...arks/Rodinia/backprop/backprop 66212.00 66252.00 0.1%
MultiSourc...chmarks/Prolangs-C++/life/life 67276.00 67312.00 0.1%
MultiSourc...s/Prolangs-C/compiler/compiler 69824.00 69788.00 -0.1%
MultiSourc...Prolangs-C/assembler/assembler 86672.00 86696.00 0.0%

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.May 15 2019, 1:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 15 2019, 1:49 PM

If the loop is being completely unrolled, and the latch is unconditional, that implies the latch is unreachable. So you can just rewrite the terminator to an "unreachable", rather than making it connect to the exit. I think that would simplify the implementation a bit?

fhahn updated this revision to Diff 203042.Jun 4 2019, 4:01 PM

Mark final latch of fully unrolled loops as unreachable, simplifed some code.

fhahn added a comment.Jun 4 2019, 4:08 PM

If the loop is being completely unrolled, and the latch is unconditional, that implies the latch is unreachable. So you can just rewrite the terminator to an "unreachable", rather than making it connect to the exit. I think that would simplify the implementation a bit?

Done, thanks Eli. I've adjusted the inner loop in llvm/test/Transforms/LoopUnroll/runtime-li.ll to have multiple exits, to avoid unrolling it. Otherwise we fail to unroll the outer loop currently, because the unreachable terminator makes the block treated an exit block (no successors in the loop). SimplfiyCFG should take care of that later.

fhahn retitled this revision from [WIP][LoopUnroll] Add support for loops with exiting headers and uncond latches. to [LoopUnroll] Add support for loops with exiting headers and uncond latches..Jun 5 2019, 9:46 AM
fhahn edited the summary of this revision. (Show Details)
fhahn added reviewers: vsk, paquette.
jdoerfert added inline comments.
llvm/lib/Transforms/Utils/LoopUnroll.cpp
48 ↗(On Diff #203042)

Same msg as above, is that on purpose?

400 ↗(On Diff #203042)

This doesn't check anymore if BI->getParent() is not only a latch block but also an exiting block, or did I miss that? What if it is not?

588 ↗(On Diff #203042)

While somewhat theoretical, what if both targets are the header? I guess there is also an inner-loop case where this would be problematic but that is probably handled elsewhere.

608 ↗(On Diff #203042)

format

627 ↗(On Diff #203042)

I don't get why this is a lambda and not simply straight line control flow. I assumed it is recursive but it doesn't seem to be. Isn't the following easier to read?

auto Term = cast<BranchInst>(Header->getTerminator());
if (Term->isUnconditional() || L->contains(Term->getSuccessor(0))) {
  assert(L->contains(Header->getSuccessor(0)));
  HeaderSucc.push_back(Term->getSuccessor(0))
} else {
  assert(L->contains(Term->getSuccessor(1)));
  HeaderSucc.push_back(Term->getSuccessor(1))
}
fhahn updated this revision to Diff 204831.Jun 14 2019, 12:28 PM
fhahn marked 5 inline comments as done.

Address Johannes' comments, thanks!

ping

llvm/lib/Transforms/Utils/LoopUnroll.cpp
400 ↗(On Diff #203042)

I think if BI is unconditional in a latch block, the latch cannot be an exiting block as well, as the only successor should be back to the header.

588 ↗(On Diff #203042)

This should be covered by the checkLatchSuccessors check, which would fail in that case I think.

608 ↗(On Diff #203042)

std::vector<BasicBlock *> is what clang-format produces. I'll adjust the line above, because it looks extremely inconsistent.

627 ↗(On Diff #203042)

Yep thanks. I think an earlier version of the patch used it elsewhere too.

paquette added inline comments.Jun 21 2019, 2:34 PM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
369–371 ↗(On Diff #204831)

I think you can factor out the !BI case here to simplify the logic a little bit?

392 ↗(On Diff #204831)

Probably should be &&?

393 ↗(On Diff #204831)

indentation is strange here

844–852 ↗(On Diff #204831)

Can you make the braces here consistent? The if has braces while the else if doesn't which looks rather strange.

fhahn updated this revision to Diff 206136.Jun 23 2019, 8:12 AM
fhahn marked 5 inline comments as done.

Addressed Jessica's comments, thanks!

fhahn added inline comments.Jun 23 2019, 8:13 AM
llvm/lib/Transforms/Utils/LoopUnroll.cpp
393 ↗(On Diff #204831)

I've run clang-format, it should be fixed now, thanks!

This revision is now accepted and ready to land.Jun 24 2019, 8:57 AM
This revision was automatically updated to reflect the committed changes.