This is an archive of the discontinued LLVM Phabricator instance.

Use ValueOffsetPair to enhance value reuse during SCEV expansion.
ClosedPublic

Authored by wmi on Jun 13 2016, 4:07 PM.

Details

Summary

This patch is an expansion to http://reviews.llvm.org/D12090.

In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse difficult. I found a common case where the reuse opportunity was missed like this:

Loop lowerbound is intconst 2. Loop upperbound is a complex expr.
%lowerbound = 2
%smax = select ...
%complexexpr = add nsw %i32 %smax, -1
%upperbound = sext i32 %complexexpr i64

When we build SCEV for upperbound, %complexexpr is mapped to SCEV S1: (-1 + X smax Y) <nsw>
%upperbound is mapped to SCEV S2 = sext(S1) = sext((-1 + X smax Y) <nsw>) = (-1 + sext(X smax Y)) <nsw> (sext distribution for SCEV applied here)
Both S1 and S2 will have reuse value entries in ExprValueMap.

Then when we compute loop iteration number based on upperbound SCEV S2 and lowerbound 2: it is S2 - 2 + 1 = -2 + sext(X smax Y) (const folding applied here). Note we only have S1 and S2 in ExprValueMap so we don't have reuse entry for -2 + sext(X smax Y) or sext(X smax Y) so we have to expand "-2 + sext(X smax Y)" literally. When X and Y are also complex expression, it will produce a lot of redundent code.

The patch is proposing to save {Value, Offset} pair instead of just Value in ExprValueMap, and if a SCEV can be splitted into a stripped SCEV part plus an int offset, the mapping "stripped SCEV -> {Value, Offset}" will be added into ExprValueMap, so we won't worry missing reuse opportunity because of const folding.

For %upperbound which is mapped to SCEV S2 = (-1 + sext(X smax Y)), in addition to save mapping "S2 -> %upperbound" into ExprValueMap (Represented as S2 -> {%upperbound, 0}), it will split S2 into two parts: "stripped SCEV S3" + "offset -1". Here S3 is "sext(X smax Y)". Mapping "S3 -> {%upperbound, -1}" will also be saved into ExprValueMap.

Then when scev expander did code expansion for loop iteration number: -2 + sext(X smax Y), it will find out SCEV S3: sext(X smax Y) is in ExprValueMap (The entry: S3 -> {%upperbound, -1}), so it knows to reuse %upperbound - (-1) to represent sext(X smax Y), instead of expanding S3 literally.

Diff Detail

Repository
rL LLVM

Event Timeline

wmi updated this revision to Diff 60613.Jun 13 2016, 4:07 PM
wmi retitled this revision from to Use ValueOffsetPair to enhance value reuse during SCEV expansion. .
wmi updated this object.
wmi added reviewers: hfinkel, sanjoy.
wmi set the repository for this revision to rL LLVM.
wmi added subscribers: llvm-commits, davidxl, mkuper.
sanjoy requested changes to this revision.Jun 21 2016, 5:38 PM
sanjoy edited edge metadata.

I generally like the idea, but I have some implementation specific comments inline.

include/llvm/Analysis/ScalarEvolution.h
509 ↗(On Diff #60613)

I think this first part of the explanation can be made easier to
follow if we write in a more explicit way:

Suppose we know S1 expands to V1, and

  S1 = S2 + C_a
  S3 = S2 + C_b

where C_a and C_b are different SCEVConstants.  Then we'd like to
expand S3 as V1 - C_a + C_b.

The second part is fine, but please make it a obvious that it
semantically maps S to {expand(S + Offset), Offset}, that is, if
S is mapped to {V, Offset} then expand(S) is V - Offset.

lib/Analysis/ScalarEvolution.cpp
3392 ↗(On Diff #60613)

Why not use dyn_cast?

3401 ↗(On Diff #60613)

Again, please use dyn_cast. For instance, here you can do:

auto *ConstOp = dyn_cast<SCEVConstant>(Op1);
auto *NonConstOp = dyn_cast<SCEVConstant>(Op2);
if (!ConstOp && NonConstOp)
  std::swap(ConstOp, NonConstOp);
if (!ConstOp)
  return {S, nullptr};

However, since SCEV expressions are ordered in complexity, you should only ever need to check the first operand -- if there is a constant operand, then it will be the first one.

Once you've made these simplifications, if the function becomes small enough I'd suggest just inlining it into its caller. If it isn't small enough, please make it a static helper function -- there is no need for this to live in the ScalarEvolution interface.

3413 ↗(On Diff #60613)

We don't repeat function names in new code.

3441 ↗(On Diff #60613)

How about:

if (SetVector<ValueOffsetPair> *SV = getSCEVValues(S))
  SV->remove(...);

?

Same below.

3483 ↗(On Diff #60613)

Use isa<> instead of directly comparing getSCEVType.

This revision now requires changes to proceed.Jun 21 2016, 5:38 PM
wmi added inline comments.Jun 22 2016, 11:07 AM
include/llvm/Analysis/ScalarEvolution.h
509 ↗(On Diff #60613)

Thanks for helping to rephrase the comment. It makes the comment much clearer. Comment fixed as suggested.

lib/Analysis/ScalarEvolution.cpp
3392 ↗(On Diff #60613)

Change it to isa<SCEVAddExpr>(S) instead.

3401 ↗(On Diff #60613)

Thanks for the suggestion which simplifies the func a lot. I change the function to be static.

3413 ↗(On Diff #60613)

Fixed.

3441 ↗(On Diff #60613)

That is better. Fixed.

wmi updated this revision to Diff 61577.Jun 22 2016, 11:09 AM
wmi edited edge metadata.

Sanjoy, thanks for the review. comments addressed.

wmi added a subscriber: wmi.Jul 7 2016, 5:43 PM

Ping.

sanjoy accepted this revision.Jul 19 2016, 6:10 PM
sanjoy edited edge metadata.

lgtm modulo minor stuff (please fix and then directly check in)

lib/Analysis/ScalarEvolution.cpp
3396 ↗(On Diff #61577)

I think it is better to just cast to SCEVAddExpr to keep the code clear. Also, I'd prefer const auto *.

3470 ↗(On Diff #61577)

Nit: Stripped -> {V, Offset} to match actual code variable names.

3470 ↗(On Diff #61577)

Nit: Start with uppercase after period s/it/It/

3472 ↗(On Diff #61577)

same here.

lib/Analysis/ScalarEvolutionExpander.cpp
1896 ↗(On Diff #61577)

Can't you just do:

if (Value *Val = FindValueInExprValueMap(S, At).first)
  ScalarEvolution::ValueOffsetPair VO = FindValueInExprValueMap(S, At);
This revision is now accepted and ready to land.Jul 19 2016, 6:10 PM
This revision was automatically updated to reflect the committed changes.