This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > m
ClosedPublic

Authored by zzheng on Jan 4 2017, 11:51 AM.

Details

Summary
Given below case:

  %y = shl %x, c0
  %z = ashr %y, c1

when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle
the case where c0 > c1 by using sext(mul(trunc(x), 2^(c0-c1)))) as the SCEV
expression.

Diff Detail

Repository
rL LLVM

Event Timeline

zzheng updated this revision to Diff 83100.Jan 4 2017, 11:51 AM
zzheng retitled this revision from to [SCEV] Model ashr(shl(x, n), m), where n > m, as mul(x, 2^(n-m)).
zzheng updated this object.
zzheng added reviewers: zinob, sanjoy.
zzheng set the repository for this revision to rL LLVM.
zzheng added a subscriber: llvm-commits.

Please upload patches with full context (-U1000000).

lib/Analysis/ScalarEvolution.cpp
5276

Maybe reorganize the code to look more like this (rough outline)?

ConstantInt *LCI = dyn_cast<ConstantInt>(LOp1));
if (!LCI) break;
if (ashr greater than shl) break;
if (ashr less than than shl) {
  // Multiply SCEV
}
return sext(trunc(scev));
test/Analysis/ScalarEvolution/sext-mul.ll
5

The loop induction variable (let's call it i) translates to {0,+,1}<%9>. i*2 translates to {0,+,2}<%9>. sext(trunc(i to i32) to i64) (sext i32 {0,+,1}<%9> to i64). sext(trunc(i*2 to i32) to i64) translates to (sext i32 {0,+,2}<%9> to i64). ashr(shl(i, 33), 32) should also translate to (sext i32 {0,+,2}<%9> to i64).

With your patch, ashr(shl(i, 33), 32) translates to {0,+,2}<%9>, which is wrong because the loop can iterate more that INT_MAX times.

zzheng updated this revision to Diff 83740.Jan 9 2017, 4:39 PM
zzheng retitled this revision from [SCEV] Model ashr(shl(x, n), m), where n > m, as mul(x, 2^(n-m)) to [SCEV] Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > m.
zzheng updated this object.
zzheng added a reviewer: efriedma.

Addressed comment in 1st version by efriedman.

efriedma added inline comments.Jan 9 2017, 5:02 PM
lib/Analysis/ScalarEvolution.cpp
5333

You have to check whether Amt == BitWidth before you call getTruncateExpr(); otherwise, you'll get an assertion failure in getTruncateExpr in edge cases like "ashr i32 %x, 0".

5366

Typo: "Handle".

5378

This TODO is suggesting an incorrect transformation; udiv doesn't preserve the sign.

test/Analysis/ScalarEvolution/sext-mul.ll
42

Maybe run opt -instnamer over the testcase, so it's easier to edit if we ever need to change it?

zzheng updated this revision to Diff 83901.Jan 10 2017, 5:10 PM

Added check for edge conditions.

efriedma added inline comments.Jan 11 2017, 11:01 AM
lib/Analysis/ScalarEvolution.cpp
5266

Maybe rename Amt and LOp1 to something which actually describes the values?

5267

Maybe move this check earlier? You could do it before you even check that the LHS of the ashr is another shift: just "if (CI->isNullValue()) return getSCEV(BO->LHS)".

5290

Hoist this variable definition, so you don't call CI->getZExtValue() twice.

5298

"LShAmt - AShrAmt >= Amt" is equivalent to "LShAmt - AShrAmt >= BitWidth - AshrAmt", which is equivalent to "LShAmt >= BitWidth", which you already check earlier.

5300

APInt::getOneBitSet? (The amount of the multiply could overflow "int".)

zzheng updated this revision to Diff 84612.Jan 16 2017, 4:28 PM
efriedma added inline comments.Jan 16 2017, 4:51 PM
lib/Analysis/ScalarEvolution.cpp
5271

I think you meant to return getSCEV(L) here? Please add a testcase for (ashr (shl x, 1) 0).

5304

64 might not be large enough, and getZExtValue() will assert if the value doesn't fit into a 64-bit integer. The right code is something like APInt Mul = APInt::getOneBitSet(TruncToWidth, LShAmt - AShrAmt); const SCEV *MulSCEV = getConstant(Mul);. Please add a testcase like (ashr (shl i128 x, 100) 1) to show this works correctly.

efriedma added inline comments.Jan 18 2017, 2:14 PM
lib/Analysis/ScalarEvolution.cpp
5294

To clarify my earlier comment about this: we can in fact transform ashr i32 %x, C to sext(trunc(udiv(x, (1 << C)))).

zzheng updated this revision to Diff 86466.Jan 31 2017, 11:01 AM

Revised per Eli's comments. Added new test case.

efriedma edited edge metadata.Jan 31 2017, 11:43 AM

Sanjoy, would you mind looking over this? I'd like a second set of eyes on this.

lib/Analysis/ScalarEvolution.cpp
5323

Whitespace.

5327

"getSCEV(ConstantInt::get(TruncTy, Mul))" can be shortened to "getConstant(Mul)".

zzheng updated this revision to Diff 86499.Jan 31 2017, 2:38 PM
sanjoy edited edge metadata.Feb 1 2017, 12:42 AM

Sanjoy, would you mind looking over this? I'd like a second set of eyes on this.

I'll take a look at this sometime this week.

sanjoy requested changes to this revision.Feb 2 2017, 3:24 PM

Did you consider doing this same thing in two more general steps (with separate tests for each case):

  • Lower ashr X C as sext(trunc(udiv(X, 1 << C))), irrespective of what X is
  • Add a separate rule that (A mul (1 << C0)) udiv (1 << C1) is sext(trunc(A mul (1 << (C0 - C1)))) if C0 > C1
lib/Analysis/ScalarEvolution.cpp
5299

LShOp1 is somewhat ambiguous -- how about ShlOp1 (unique since there is only one Shl in context)?

5316

Please call this ShlAmt, and please call LCI ShlAmtCI or something like that.

test/Analysis/ScalarEvolution/sext-mul.ll
14

Please add some target test cases here (i.e. ones that check specific SCEV expressions for the patterns you want SCEV to catch).

This revision now requires changes to proceed.Feb 2 2017, 3:24 PM
zzheng added a comment.EditedFeb 22 2017, 11:55 AM

Sanjoy,

I'm not familiar with SCEV, can you clarify my questions below?

  • Lower ashr X C as sext(trunc(udiv(X, 1 << C))), irrespective of what X is

This part should be done in const SCEV *ScalarEvolution::createSCEV(Value *V) as the patch is doing

  • Add a separate rule that (A mul (1 << C0)) udiv (1 << C1) is sext(trunc(A mul (1 << (C0 - C1)))) if C0 > C1

Should this be done inside getMulExpr()?

zzheng updated this revision to Diff 90361.Mar 2 2017, 11:14 AM
zzheng edited edge metadata.

Adding tranformation: AShr X, C --> sext(trunc(udiv(X, (1<<C))))

Will update test cases later.

zzheng updated this revision to Diff 90903.Mar 7 2017, 11:56 AM
zzheng edited the summary of this revision. (Show Details)

ping..

efriedma added inline comments.Mar 7 2017, 12:14 PM
lib/Analysis/ScalarEvolution.cpp
5367

dyn_cast<Value>() will always succeed; what are you trying to check here?

test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll
6 ↗(On Diff #90903)

This is defeating the point of the test. I would guess SCEVExpander isn't realizing that sext(trunc(udiv))) is equivalent to an ashr?

zzheng updated this revision to Diff 91202.Mar 9 2017, 11:48 AM

Removed ashr (X, C) -> sext(truc(udiv(X, 1<<C))) from previous revision.
This is causing a test failure and needs more work. I'd like to do it in another patch.

zzheng edited the summary of this revision. (Show Details)Mar 9 2017, 11:49 AM
zzheng added inline comments.
lib/Analysis/ScalarEvolution.cpp
5368

This is failing test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll. See inlined comments of the test.
I'd like to do this in a separated patch.

test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll
6 ↗(On Diff #90903)

"%shr = ashr i32 %add, 16" becomes computable and SCEVExpander hoists its InsertPt to outer loop, causing FindValueInExprValueMap() to return {nullptr, nullptr}.
SCEVExpander then expands it literally and creates another 'select' instruction, failing the test.

Did you consider doing this same thing in two more general steps (with separate tests for each case):

  • Lower ashr X C as sext(trunc(udiv(X, 1 << C))), irrespective of what X is

This is failing test/Analysis/ScalarEvolution/scev-expander-reuse-unroll.ll.
"%shr = ashr i32 %add, 16" becomes computable and SCEVExpander hoists its InsertPt to outer loop, causing FindValueInExprValueMap() to return {nullptr, nullptr}.
SCEVExpander then expands it literally and creates another 'select' instruction, failing the test.

  • Add a separate rule that (A mul (1 << C0)) udiv (1 << C1) is sext(trunc(A mul (1 << (C0 - C1)))) if C0 > C1

For my test case, Shl is already lowered to a mul expr before processing AShr.

AShr can be lowered to udiv(1<<C1) but it's not easy to look for the pattern "(A mul (1 << C0)) udiv (1 << C1)".

Sorry for the delay, I'll make sure to review this in the next one / two days.

sanjoy accepted this revision.Mar 15 2017, 6:36 PM

lgtm modulo minor comments

lib/Analysis/ScalarEvolution.cpp
5322

I'd call this OuterTy, since at this point it isn't obvious what this has to do with sext.

5336

IMO things would read a bit clearer if you just s/TruncToWidth/BitWidth - AShrAmt/ everywhere. But this is a minor stylistic thing, and I'd understand if you did not want to make this change.

5346

If you want to use n and m, please denote that in the legend above, i.e:

// X = Shl A, n
// Y = AShr X, m

or use C0 and C1 in this comment.

5357

Typo: LhlAmt.

test/Analysis/ScalarEvolution/sext-mul.ll
9

Why not CHECK-NEXT here?

test/Analysis/ScalarEvolution/sext-zero.ll
7

Please remove the S: [-9223372036854775808,9223372028264841217) Exits: (-8589934592 + (8589934592 * (zext i32 %arg2 to i64))) LoopDispositions: { %bb7: Computable } bits, here and elsewhere, unless you specifically want to check them. They're pretty distracting.

This revision is now accepted and ready to land.Mar 15 2017, 6:36 PM
zzheng updated this revision to Diff 92057.Mar 16 2017, 2:30 PM

addressed Sanjoy's comments

lgtm again, in case you were waiting for it.

zzheng closed this revision.Mar 23 2017, 11:20 AM

rebased and commited as r298631