This is an archive of the discontinued LLVM Phabricator instance.

[MustExecute] Improve MustExecute to correctly handle loop nest
ClosedPublic

Authored by Whitney on May 24 2019, 12:32 PM.

Details

Summary
for.outer:
  br for.inner
for.inner:
  LI <loop invariant load instruction>
for.inner.latch:
  br for.inner, for.outer.latch
for.outer.latch:
  br for.outer, for.outer.exit

LI is a loop invariant load instruction that post dominate for.outer, so LI should be able to move out of the loop nest. However, there is a bug in allLoopPathsLeadToBlock().

Current algorithm of allLoopPathsLeadToBlock()

  1. get all the transitive predecessors of the basic block LI belongs to (for.inner) ==> for.outer, for.inner.latch
  2. if any successors of any of the predecessors are not for.inner or for.inner's predecessors, then return false
  3. return true

Although for.inner.latch is for.inner's predecessor, but for.inner dominates for.inner.latch, which means if for.inner.latch is ever executed, for.inner should be as well. It should not return false for cases like this.

Diff Detail

Repository
rL LLVM

Event Timeline

Whitney created this revision.May 24 2019, 12:32 PM
jdoerfert accepted this revision.May 24 2019, 6:58 PM

LGTM once the two comments are adjusted.

llvm/lib/Analysis/MustExecute.cpp
199 ↗(On Diff #201311)

The comment should reflect the change.

207 ↗(On Diff #201311)

The check here is basically testing if the edge is a loop latch. I think the comment should include that.

This revision is now accepted and ready to land.May 24 2019, 6:58 PM
Whitney updated this revision to Diff 201406.May 25 2019, 9:40 AM

Addressed all review comments.

This revision was automatically updated to reflect the committed changes.