This is an archive of the discontinued LLVM Phabricator instance.

[Guards] Introduce loop-predication pass
ClosedPublic

Authored by apilipenko on Jan 23 2017, 8:08 AM.

Details

Summary

This patch introduces guard based loop predication optimization. The new LoopPredication pass tries to convert loop variant range checks to loop invariant by widening checks across loop iterations. For example, it will convert

for (i = 0; i < n; i++) {
  guard(i < len);
  ...
}

to

for (i = 0; i < n; i++) {
  guard(n - 1 < len);
  ...
}

After this transformation the condition of the guard is loop invariant, so loop-unswitch can later unswitch the loop by this condition which basically predicates the loop by the widened condition:

if (n - 1 < len)
  for (i = 0; i < n; i++) {
    ...
  }
else
  deoptimize

This patch relies on an NFC change to make ScalarEvolution::isMonotonicPredicate public which is not included in the review.

Diff Detail

Event Timeline

apilipenko created this revision.Jan 23 2017, 8:08 AM
apilipenko edited the summary of this revision. (Show Details)Jan 23 2017, 8:10 AM
sanjoy accepted this revision.Jan 23 2017, 9:55 AM

Looks great!

I have some nitpicky comments inline, but feel free to push after addressing them without further review (or address them in follow-up commits).

lib/Transforms/Scalar/LoopPredication.cpp
2

Please edit the header to include a description like in other .cpp files.

60

Now is a good time to make sure this pass also runs with the new pass manager.

130

Why do you care about !IndexAR->isAffine() here?

144

I'd s/NewIndexSCEV/NewLHS/ since it isn't an index any more.

147

Since you invoked getSCEVAtScope (which can fail), you should check (and bail) if NewIndexSCEV was SCEVCouldNotCompute.

160

processGuard basically says nothing about what this function does. "Processing" them to what end? :)

I'd call this widenGuard or predicateUsingGuard or something like that.

171

s/resuting/resulting/

178

This might be better as as do-while loop, since you know you'll run at least one iteration.

192

Use auto * to emphasize that you'll get back a pointer.

Actually, I'd rather spell out the type here as Value * (since it is not 100% obvious what widenICmpRangeCheck returns), and instead use auto * for the result of of the dyn_cast in the if expression.

210

Use auto *.

249

auto *.

This revision is now accepted and ready to land.Jan 23 2017, 9:55 AM

Actually, given that this is a new pass, I'd give one or two days for people to chime in in case they have objections; but this LGTM from my side.

Address Sanjoy's comments: add new pass manager support, fix nits here and there.
Add an early exit if the module doesn't use guards.

I'm going to land this version if there is no more comments in a couple of days.

This revision was automatically updated to reflect the committed changes.