This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Try to use existing values in RewriteLoopExitValues.
ClosedPublic

Authored by sanjoy on Jun 26 2015, 4:11 PM.

Details

Summary

In RewriteLoopExitValues, before expanding out an SCEV expression using
SCEVExpander, try to see if an existing LLVM IR expression already
computes the value we're interested in. If so use that existing
expression.

Apart from reducing IndVars' reliance on the rest of the compilation
pipeline, this also prevents IndVars from concluding some expressions as
"high cost" when they're not. For instance,
InductiveRangeCheckElimination often emits code of the following form:

len = umin(len_A, len_B)

loop:
  ...
  if (i++ < len)
    goto loop

outside_loop:
    use(i)

SCEVExpander refuses to rewrite the use of i in outside_loop,
since it thinks the value of i on loop exit, len, is a high cost
expansion since it contains an umax in it. With this change,
IndVars can see that it can re-use len instead of creating a new
expression to compute umin(len_A, len_B).

I considered putting this cleverness in SCEVExpander, but I was
worried that it may then have a deterimental effect on other passes
that use it. So I decided it was better to just do this in the one
place where it seems like an obviously good idea, with the intent of
generalizing later if needed.

Diff Detail

Event Timeline

sanjoy updated this revision to Diff 28609.Jun 26 2015, 4:11 PM
sanjoy retitled this revision from to [IndVars] Try to use existing values in RewriteLoopExitValues..
sanjoy updated this object.
sanjoy edited the test plan for this revision. (Show Details)
sanjoy added reviewers: atrick, reames.
sanjoy added a subscriber: Unknown Object (MLST).
hfinkel accepted this revision.Jul 8 2015, 9:31 PM
hfinkel added a reviewer: hfinkel.
hfinkel added a subscriber: hfinkel.

LGTM.

lib/Transforms/Scalar/IndVarSimplify.cpp
529

The somewhat arbitrary nature of this heuristic is bothersome, although I can certainly understand why this is a common case.

Nevertheless, I can't think of anything better at the moment.

This revision is now accepted and ready to land.Jul 8 2015, 9:31 PM
sanjoy added inline comments.Jul 8 2015, 11:58 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
529

The somewhat arbitrary nature of this heuristic is bothersome

Agreed. I initially wanted to do a more sophisticated crawl through the use list, but then decided to cross that bridge after I actually see real-world examples -- no point burning compile time on cases that don't really happen in practice.

This revision was automatically updated to reflect the committed changes.