Page MenuHomePhabricator

Converting ‘sext of addrec’ to ‘addrec of sext’
AbandonedPublic

Authored by ashutosh.nema on May 6 2015, 4:11 AM.

Details

Reviewers
majnemer
Summary

This change is for converting ‘sext of addrec’ to ‘addrec of sext’ when
compiler is sure transformation will not overflow.

By doing this will open opportunity for optimizations dependent on addRecExpr.

Consider below case:

for (j=1; j < itr; j++) {


for (i=1; i < itr; i++) {
{
  temp=  var[i * 2];
   - - - - - 
}

}

“var[i * 2]” "SCEVAddRecExpr" is computable in *Outer Loop*

I expected Scalar evolution to get that, but it's not doing that
if ‘*2’ is transformed to shift reduction in some specific circumstances.

In the above example, ‘var[i * 2]’ is converted into ‘var[i << 1]’
by Instruction combiner (Shift reduction).

After this addRecExpr is not computable.

To fix that issue made changes in ScalarEvolution & SimplifyIndVar.

In ScalarEvolution converting ‘sext of addrec’ to ‘addrec of sext’ only when
Compiler is sure operation will not overflow:
i.e. (sext i32 Addrec{2,+,2}<nuw><%for.body4> to i64)
will be transformed into:
// addrec{(sext i32 '2' to i64),+,(sext i32 '2' to i64)}<nsw><%for.body4>

In “SimplifyIndVar.cpp” we strengthen overflow operation for left shift.

Diff Detail

Repository
rL LLVM

Event Timeline

ashutosh.nema retitled this revision from to Converting ‘sext of addrec’ to ‘addrec of sext’.
ashutosh.nema updated this object.
ashutosh.nema edited the test plan for this revision. (Show Details)
ashutosh.nema added reviewers: sanjoy, majnemer.
ashutosh.nema set the repository for this revision to rL LLVM.
ashutosh.nema added a subscriber: Unknown Object (MLST).
sanjoy edited edge metadata.May 6 2015, 12:06 PM

Comments inline.

This kind of change *definitely* needs several test cases.

lib/Analysis/ScalarEvolution.cpp
4332

This needs to go in ScalarEvolution::getSignExtendExpr. There are a bunch of other rules for turning a sign extend of an add rec into an addrec there.

4339

I think you're also transforming sext({S,+,X}<nuw>) to {sext S,+,sext X} which isn't correct.

test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll
14

Note that these are regressions: we know that %start is slt 127 so we should be able to use the more canonical {(1 + (sext i32 %start to i64)),+,1}<nsw><%loop> here.

Thanks Sanjoy for review.
I'll work on your comments and come back.

Regards,
Ashutosh

sanjoy requested changes to this revision.May 8 2015, 11:23 AM
sanjoy edited edge metadata.
This revision now requires changes to proceed.May 8 2015, 11:23 AM
sanjoy resigned from this revision.Jul 6 2015, 7:37 PM
sanjoy removed a reviewer: sanjoy.

Resigning as reviewer so that this does not continue to show up in my review list. Feel free to add me back as reviewer if you're reviving this patch.

ashutosh.nema abandoned this revision.Jul 13 2015, 3:24 AM