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

[ashutosh.nema]

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.

[sanjoy]

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.

[ashutosh.nema]

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

Regards,
Ashutosh

[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.

lib/Analysis/ScalarEvolution.cpp

case Instruction::AShr:
     break;
 
   case Instruction::Trunc:
     return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
 
   case Instruction::ZExt:
     return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
 
-  case Instruction::SExt:
+  case Instruction::SExt: {
+    // Converting 'sext of addRec' to 'addRec of sext'
+    // 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>
+    const SCEVAddRecExpr *AddRec =
+        dyn_cast<SCEVAddRecExpr>(getSCEV(U->getOperand(0)));
+    if (AddRec && (AddRec->getNoWrapFlags(SCEV::FlagNSW) ||
+                   AddRec->getNoWrapFlags(SCEV::FlagNUW))) {
+      SmallVector<const SCEV *, 4> Operands;
+      for (SCEVAddRecExpr::op_iterator I = AddRec->op_begin(),
+                                       E = AddRec->op_end();
+           I != E; ++I) {
+        const SCEV *addRecOpr = *I;
+        addRecOpr = getSignExtendExpr(addRecOpr, U->getType());
+        Operands.push_back(addRecOpr);
+      }
+      if (AddRec->getNoWrapFlags(SCEV::FlagNSW))
+        return getAddRecExpr(Operands, AddRec->getLoop(),
+                             AddRec->getNoWrapFlags(SCEV::FlagNSW));
+      else
+        return getAddRecExpr(Operands, AddRec->getLoop(),
+                             AddRec->getNoWrapFlags(SCEV::FlagNUW));
+    } else {
       return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+    }
+  }
 
   case Instruction::BitCast:
     // BitCasts are no-op casts so we just eliminate the cast.
     if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
       return getSCEV(U->getOperand(0));
     break;
 
   // It's tempting to handle inttoptr and ptrtoint as no-ops, however this can

lib/Transforms/Utils/SimplifyIndVar.cpp

bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
 
   case Instruction::Sub:
     GetExprForBO = &ScalarEvolution::getMinusSCEV;
     break;
 
   case Instruction::Mul:
     GetExprForBO = &ScalarEvolution::getMulExpr;
     break;
+
+  case Instruction::Shl:
+    // shift by operand should be constant.
+    if (dyn_cast<ConstantInt>(BO->getOperand(1))) {
+      // shift should be marked with 'nsw' or 'nuw'.
+      if (!BO->hasNoUnsignedWrap() && !BO->hasNoSignedWrap())
+        return false;
+      GetExprForBO = &ScalarEvolution::getMulExpr;
+      break;
+    } else {
+      return false;
+    }
   }
 
   unsigned BitWidth = cast<IntegerType>(BO->getType())->getBitWidth();
   Type *WideTy = IntegerType::get(BO->getContext(), BitWidth * 2);
   const SCEV *LHS = SE->getSCEV(BO->getOperand(0));
   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
 
   bool Changed = false;

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

 ; ; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
 
 define void @infer.sext.0(i1* %c, i32 %start) {
 ; CHECK-LABEL: Classifying expressions for: @infer.sext.0
  entry:
   br label %loop
 
  loop:
   %counter = phi i32 [ 0, %entry ], [ %counter.inc, %loop ]
   %idx = phi i32 [ %start, %entry ], [ %idx.inc, %loop ]
   %idx.inc = add nsw i32 %idx, 1
   %idx.inc.sext = sext i32 %idx.inc to i64
 ; CHECK: %idx.inc.sext = sext i32 %idx.inc to i64
-; CHECK-NEXT: -->  {(1 + (sext i32 %start to i64)),+,1}<nsw><%loop>
+; CHECK-NEXT: -->  {(sext i32 (1 + %start) to i64),+,1}<nsw><%loop>
   %condition = icmp eq i32 %counter, 1
   %counter.inc = add i32 %counter, 1
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }
 
entry:
   %start.inc = add i8 %start, 1
   %entry.condition = icmp slt i8 %start, 127
   br i1 %entry.condition, label %loop, label %exit
 
  loop:
   %idx = phi i8 [ %start.inc, %entry ], [ %idx.inc, %loop ]
   %idx.sext = sext i8 %idx to i16
 ; CHECK: %idx.sext = sext i8 %idx to i16
-; CHECK-NEXT: -->  {(1 + (sext i8 %start to i16)),+,1}<nsw><%loop>
+; CHECK-NEXT: -->  {(sext i8 (1 + %start) to i16),+,1}<nsw><%loop>
   %idx.inc = add nsw i8 %idx, 1
   %condition = load volatile i1, i1* %c
   br i1 %condition, label %exit, label %loop
 
  exit:
   ret void
 }