[IndVars] Widen more comparisons for non-negative induction vars.

[sanjoy]

Summary

If an induction variable is provably non-negative, its sign extension is
equal to its zero extension. This means narrow uses like

icmp slt iNarrow %indvar, %rhs

can be widened into

icmp slt iWide zext(%indvar), sext(%rhs)

[sanjoy]

• rename AlwaysPositive to NeverNegative

[reames]

Minor comments. The direction of the change looks right to me. I'm not comfortable giving a LGTM on this given I don't know the area well enough.

lib/Transforms/Scalar/IndVarSimplify.cpp

851

A brief bit about what we can use this fact for would be good in the comment.

1269

Why not just SE->isKnownNonNegative(AddRec)?

test/Transforms/IndVarSimplify/widen-loop-comp.ll

200

CHECK_LABEL

213

It isn't obvious to me whether we chose a sext or a sext for the induction variable in this loop. We could do either base on order of visitation. Could you clarify this?

Also, can you add tests for the full 2 x 2 matrix of signed/unsigned widdening x signed/unsigned compare?

[reames]

lib/Transforms/Scalar/IndVarSimplify.cpp

1271

p.s. A follow on change which would be good would be to use NeverNegative to set IsSigned. (Either value is legal, I think treating it as unsigned would be more canonical.) This would remove the order of visit dependency in the common case and help create a single canonical form.

When you do this, you'll need to adjust some of the extension elimination logic to account for when a sext and zext are interchangable.

Once that's done, we can canonicalize all sext on non-negative indvars to zext. Arguably, that could be done instead of adjusting the cast removal logic mentioned previously.

[sanjoy]

• Address Philip's review.

[sanjoy]

replied inline.

lib/Transforms/Scalar/IndVarSimplify.cpp

851

Added a comment, ptal.

1269

isKnownNonNegative does not look at control flow and so is weaker than isKnownPredicate. I've added a test case (test8) that does not work with isKnownNonNegative.

test/Transforms/IndVarSimplify/widen-loop-comp.ll

213

It isn't obvious to me whether we chose a sext or a sext for the
induction variable in this loop. We could do either base on order of
visitation. Could you clarify this?

Thanks for pointing this out!

In @test7 and @test6 it is impossible to tell what -indvars did
(sign extend or zero extend) based solely on how the structure of
%indvars.iv. This is because normally you'd look at the initial
value of induction variable to deduce if the induction variable was
sign or zero extended; but here we're out of luck since the initial
value is a positive constant (== 0) so its sign and zero extensions
are the same.

I've added two more tests @test8 and @test9 that have a
non-constant initial value of the induction variable being widened.
By looking at the initial value of the induction variable phi (whether
it is a sext or zext), we can deduce if the indvar was zero extended
or sign extended.

If we start canonicalizing sign extensions of positive induction
variables to zero extensions then then it would be impossible tell if
zero or signed widening happened on @test8 and @test9 also; but we
do not do that today.

Also, can you add tests for the full 2 x 2 matrix of signed/unsigned
widdening x signed/unsigned compare?

The rest of the file already has tests for the two (signed widening,
signed compare) and (unsigned widening, unsigned compare) cases.
@test8 checks the (signed extension, unsigned compare) case, while
@test9 checks the (unsigned extension, signed compare) case.

Also, given your comment, I think @test6 and @test7 do not add
much value to this change beyond just being generic correctness tests.
Do you think it makes sense to remove these?

[reames]

test/Transforms/IndVarSimplify/widen-loop-comp.ll

213

I would prefer you left them. The zero based increasing loop is a simpler, easier to understand, and really important case. I think there's value even if they're covered by the additional cases.

[sanjoy]

ping!

[mcrosier]

My understanding of the CHECK-LABEL directive is that it matches a single unique strings within a file (e.g., function names). I assumed FileCheck would complain if you have multiple CHECK-LABEL directives with the same (i.e., for.cond:) check, but that doesn't appear to be the case here. What have I missed?

[sanjoy]

The docs are pretty clear about CHECK-LABEL's matching unique lines
"they must simply uniquely match a single line in the file being
verified.", so I've removed the problematic CHECK-LABEL directives.

However, FileCheck does not complain either way.

[hfinkel]

LGTM.

lib/Transforms/Scalar/IndVarSimplify.cpp

 /// inserting truncs whenever we stop propagating the type.
 ///
 class WidenIV {
   // Parameters
   PHINode *OrigPhi;
   Type *WideType;
   bool IsSigned;
 
+  // True if the narrow induction variable is never negative.  Tracking this
+  // information lets us use a sign extension instead of a zero extension or
+  // vice versa, when profitable and legal.
+  bool NeverNegative;
+
   // Context
   LoopInfo        *LI;
   Loop            *L;
   ScalarEvolution *SE;
   DominatorTree   *DT;
 
   // Result
   PHINode *WidePhi;
   Instruction *WideInc;
   const SCEV *WideIncExpr;
   SmallVectorImpl<WeakVH> &DeadInsts;
 
   SmallPtrSet<Instruction*,16> Widened;
   SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
 
 public:
   WidenIV(const WideIVInfo &WI, LoopInfo *LInfo,
           ScalarEvolution *SEv, DominatorTree *DTree,
           SmallVectorImpl<WeakVH> &DI) :
     OrigPhi(WI.NarrowIV),
     WideType(WI.WidestNativeType),
     IsSigned(WI.IsSigned),
+    NeverNegative(false),
     LI(LInfo),
     L(LI->getLoopFor(OrigPhi->getParent())),
     SE(SEv),
     DT(DTree),
     WidePhi(nullptr),
     WideInc(nullptr),
     WideIncExpr(nullptr),
     DeadInsts(DI) {

 /// If the narrow use is a compare instruction, then widen the compare
 //  (and possibly the other operand).  The extend operation is hoisted into the
 // loop preheader as far as possible.
 bool WidenIV::WidenLoopCompare(NarrowIVDefUse DU) {
   ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
   if (!Cmp)
     return false;
 
-  // Sign of IV user and compare must match.
-  if (IsSigned != CmpInst::isSigned(Cmp->getPredicate()))
+  // We can legally widen the comparison in the following two cases:
+  //
+  //  - The signedness of the IV extension and comparison match
+  //
+  //  - The narrow IV is always positive (and thus its sign extension is equal
+  //    to its zero extension).  For instance, let's say we're zero extending
+  //    %narrow for the following use
+  //
+  //      icmp slt i32 %narrow, %val   ... (A)
+  //
+  //    and %narrow is always positive.  Then
+  //
+  //      (A) == icmp slt i32 sext(%narrow), sext(%val)
+  //          == icmp slt i32 zext(%narrow), sext(%val)
+
+  if (!(NeverNegative || IsSigned == Cmp->isSigned()))
     return false;
 
   Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
   unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
   unsigned IVWidth = SE->getTypeSizeInBits(WideType);
   assert (CastWidth <= IVWidth && "Unexpected width while widening compare.");
 
   // Widen the compare instruction.
   IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT));
   DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
 
   // Widen the other operand of the compare, if necessary.
   if (CastWidth < IVWidth) {
-    Value *ExtOp = getExtend(Op, WideType, IsSigned, Cmp);
+    Value *ExtOp = getExtend(Op, WideType, Cmp->isSigned(), Cmp);
     DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
   }
   return true;
 }
 
 /// WidenIVUse - Determine whether an individual user of the narrow IV can be
 /// widened. If so, return the wide clone of the user.
 Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {

 /// invalidating SCEV expressions.
 ///
 PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) {
   // Is this phi an induction variable?
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
   if (!AddRec)
     return nullptr;
 
+  NeverNegative = SE->isKnownPredicate(ICmpInst::ICMP_SGE, AddRec,
+                                       SE->getConstant(AddRec->getType(), 0));
+
   // Widen the induction variable expression.
   const SCEV *WideIVExpr = IsSigned ?
     SE->getSignExtendExpr(AddRec, WideType) :
     SE->getZeroExtendExpr(AddRec, WideType);
 
   assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
          "Expect the new IV expression to preserve its type");
 

test/Transforms/IndVarSimplify/widen-loop-comp.ll

for.body:
   %0 = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %sum.0, %0
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:
   ret i32 %sum.0
 }
+
+define i32 @test6(i32* %a, i32 %b) {
+; CHECK-LABEL: @test6(
+; CHECK: [[B_SEXT:%[a-z0-9]+]] = sext i32 %b to i64
+; CHECK: for.cond:
+; CHECK: icmp sle i64 %indvars.iv, [[B_SEXT]]
+
+entry:
+  br label %for.cond
+
+for.cond:
+  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp sle i32 %i.0, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:
+  ret i32 %sum.0
+}
+
+define i32 @test7(i32* %a, i32 %b) {
+; CHECK-LABEL: @test7(
+; CHECK: [[B_ZEXT:%[a-z0-9]+]] = zext i32 %b to i64
+; CHECK: [[B_SEXT:%[a-z0-9]+]] = sext i32 %b to i64
+; CHECK: for.cond:
+; CHECK: icmp ule i64 %indvars.iv, [[B_ZEXT]]
+; CHECK: for.body:
+; CHECK: icmp sle i64 %indvars.iv, [[B_SEXT]]
+
+entry:
+  br label %for.cond
+
+for.cond:
+  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %cmp = icmp ule i32 %i.0, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %i.0, 1
+  %cmp2 = icmp sle i32 %i.0, %b
+  br i1 %cmp2, label %for.cond, label %for.end
+
+for.end:
+  ret i32 %sum.0
+}
+
+define i32 @test8(i32* %a, i32 %b, i32 %init) {
+; CHECK-LABEL: @test8(
+; CHECK: [[INIT_SEXT:%[a-z0-9]+]] = sext i32 %init to i64
+; CHECK: [[B_ZEXT:%[a-z0-9]+]] = zext i32 %b to i64
+; CHECK: for.cond:
+;     Note: %indvars.iv is the sign extension of %i.0
+; CHECK: %indvars.iv = phi i64 [ [[INIT_SEXT]], %for.cond.preheader ], [ %indvars.iv.next, %for.body ]
+; CHECK: icmp ule i64 %indvars.iv, [[B_ZEXT]]
+
+entry:
+  %e = icmp sgt i32 %init, 0
+  br i1 %e, label %for.cond, label %leave
+
+for.cond:
+  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ %init, %entry ], [ %inc, %for.body ]
+  %cmp = icmp ule i32 %i.0, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %i.0, 1
+  %cmp2 = icmp slt i32 0, %inc
+  br i1 %cmp2, label %for.cond, label %for.end
+
+for.end:
+  ret i32 %sum.0
+
+leave:
+  ret i32 0
+}
+
+define i32 @test9(i32* %a, i32 %b, i32 %init) {
+; CHECK-LABEL: @test9(
+; CHECK: [[INIT_ZEXT:%[a-z0-9]+]] = zext i32 %init to i64
+; CHECK: [[B_SEXT:%[a-z0-9]+]] = sext i32 %b to i64
+; CHECK: for.cond:
+;     Note: %indvars.iv is the zero extension of %i.0
+; CHECK: %indvars.iv = phi i64 [ [[INIT_ZEXT]], %for.cond.preheader ], [ %indvars.iv.next, %for.body ]
+; CHECK: icmp slt i64 %indvars.iv, [[B_SEXT]]
+
+entry:
+  %e = icmp sgt i32 %init, 0
+  br i1 %e, label %for.cond, label %leave
+
+for.cond:
+  %sum.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ %init, %entry ], [ %inc, %for.body ]
+  %cmp = icmp slt i32 %i.0, %b
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %sum.0, %0
+  %inc = add nsw i32 %i.0, 1
+  %cmp2 = icmp slt i32 0, %inc
+  br i1 %cmp2, label %for.cond, label %for.end
+
+for.end:
+  ret i32 %sum.0
+
+leave:
+  ret i32 0
+}