[BUG][INDVAR] Fix for PR21014: wrong SCEV operands commuting for non-commutative instructions

[zinovy.nis]

Summary

My commit rL216160 introduced a bug PR21014.

IndVars widens code

for (i = ; i < ...; i++) arr[ CONST - i]

into

for (i = ; i < ...; i++) arr[ i - CONST]

thus inverting index expression. The patch attached fixes it.
Thanks to Jörg Sonnenberger for pointing.

[hfinkel]

LGTM. (In the future, simple bug fixes like this can be reviewed post-commit).

[zinovy.nis]

Closed by commit rL218867 (authored by @zinovy.nis).

[zinovy.nis]

Thanks.

lib/Transforms/Scalar/IndVarSimplify.cpp

const SCEVAddRecExpr* WidenIV::GetExtendedOperandRecurrence(NarrowIVDefUse DU) {
   const unsigned OpCode = DU.NarrowUse->getOpcode();
   // Only Add/Sub/Mul instructions supported yet.
   if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
       OpCode != Instruction::Mul)
     return nullptr;
 
   // One operand (NarrowDef) has already been extended to WideDef. Now determine
   // if extending the other will lead to a recurrence.
-  unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
+  const unsigned ExtendOperIdx =
+      DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
   assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
 
   const SCEV *ExtendOperExpr = nullptr;
   const OverflowingBinaryOperator *OBO =
     cast<OverflowingBinaryOperator>(DU.NarrowUse);
   if (IsSigned && OBO->hasNoSignedWrap())
     ExtendOperExpr = SE->getSignExtendExpr(
       SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
   else if(!IsSigned && OBO->hasNoUnsignedWrap())
     ExtendOperExpr = SE->getZeroExtendExpr(
       SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
   else
     return nullptr;
 
   // When creating this SCEV expr, don't apply the current operations NSW or NUW
   // flags. This instruction may be guarded by control flow that the no-wrap
   // behavior depends on. Non-control-equivalent instructions can be mapped to
   // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
   // semantics to those operations.
-  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(
-      GetSCEVByOpCode(SE->getSCEV(DU.WideDef), ExtendOperExpr, OpCode));
+  const SCEV *lhs = SE->getSCEV(DU.WideDef);
+  const SCEV *rhs = ExtendOperExpr;
+
+  // Let's swap operands to the initial order for the case of non-commutative
+  // operations, like SUB. See PR21014.
+  if (ExtendOperIdx == 0)
+    std::swap(lhs, rhs);
+  const SCEVAddRecExpr *AddRec =
+      dyn_cast<SCEVAddRecExpr>(GetSCEVByOpCode(lhs, rhs, OpCode));
+
   if (!AddRec || AddRec->getLoop() != L)
     return nullptr;
   return AddRec;
 }
 
 /// GetWideRecurrence - Is this instruction potentially interesting from
 /// IVUsers' perspective after widening it's type? In other words, can the
 /// extend be safely hoisted out of the loop with SCEV reducing the value to a

test/Transforms/IndVarSimplify/2011-09-10-widen-nsw.ll

for.body11:                                       ; preds = %entry
   %shl132 = shl i32 %shl, 1
   br label %for.body153
 
 for.body153:                                      ; preds = %for.body153, %for.body11
   br i1 undef, label %for.body170, label %for.body153
 
 ; CHECK: add nsw i64 %indvars.iv, 1
 ; CHECK: sub nsw i64 %indvars.iv, 2
-; CHECK: mul nsw i64 %indvars.iv, 4
+; CHECK: sub nsw i64 4, %indvars.iv
+; CHECK: mul nsw i64 %indvars.iv, 8
 for.body170:                                      ; preds = %for.body170, %for.body153
   %i2.19 = phi i32 [ %add249, %for.body170 ], [ 0, %for.body153 ]
 
   %add = add nsw i32 %i2.19, 1
   %add.idxprom = sext i32 %add to i64
 
   %sub = sub nsw i32 %i2.19, 2
   %sub.idxprom = sext i32 %sub to i64
 
-  %mul = mul nsw i32 %i2.19, 4
+  %sub.neg = sub nsw i32 4, %i2.19
+  %sub.neg.idxprom = sext i32 %sub.neg to i64
+
+  %mul = mul nsw i32 %i2.19, 8
   %mul.idxprom = sext i32 %mul to i64
 
   %add249 = add nsw i32 %i2.19, %shl132
   br label %for.body170
 for.end285:                                       ; preds = %entry
   ret void
 }