[IndVarSimplify] Integrate changes in D18777 and D18867 which depend on each other

[lihuang]

Summary

Integrate changes in D18777 and D18867 which depend on each other.

Finally, changes in D18777 and D18867 depend on each other and should be checked in at the same time, otherwise will break tests.

[lihuang]

Hi Sanjoy,

I have merged the changes in D18777 and D18867 because they depend on each other and should go in together, and have rebased the change on top of latest source. Do you think this whole thing is ready to go in?

Thanks,
Li Huang

[sanjoy]

Hi Li,

In D23227#507506, @lihuang wrote:

Hi Sanjoy,

I have merged the changes in D18777 and D18867 because they depend on each other and should go in together, and have rebased the change on top of latest source. Do you think this whole thing is ready to go in?

Why do they depend on each other? If they individually are correct and pass all tests (and only need the other one to be fully effective) then they should go in separately.

• Sanjoy

[lihuang]

Hi Sanjoy,

Actually I was wrong here, the change in IndVarSimplify depends on that of ValueTracking but not the opposite.

The change in IndVarSimplify uses ValueTracking's isKnownNonNegative to test the signedness of IV and IV users, so without the change in ValueTracking the iv-widen tests will fail. I thought the tests I made for ValueTracking changes also requires IndVars change but they actually don't.

Sorry about this, just ignore this patch.

-Li Huang

lib/Analysis/ValueTracking.cpp

// assume(v <_u c)
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
       else
         KnownZero |=
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
     }
   }
 }
 
+// Compute known sign bit from a shift operator, based on the known sign bit of
+// its first operand and the nsw flag. KnownZero2 and KnownOne2 are the computed
+// known bits of its first operand.
+static void computeKnownSignBitFromShift(Operator *I, 
+                                         APInt &KnownZero, APInt &KnownOne,
+                                         APInt &KnownZero2, APInt &KnownOne2) {
+  // If this is a left shift with nsw, then the shift produces a poison value
+  // if it shifts out any bits that disagree with the resultant sign bit.
+  // This means the result is either a poison value or has the same sign bit 
+  // as the first operand.
+  unsigned BitWidth = KnownZero.getBitWidth();
+  if (I->getOpcode() == Instruction::Shl &&
+      cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap()) {
+    if (KnownZero2.isNegative())
+        KnownZero |= APInt::getSignBit(BitWidth);
+    else if (KnownOne2.isNegative())
+        KnownOne |= APInt::getSignBit(BitWidth);
+  }
+}
+
 // Compute known bits from a shift operator, including those with a
 // non-constant shift amount. KnownZero and KnownOne are the outputs of this
 // function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the
 // same bit width as KnownZero and KnownOne. KZF and KOF are operator-specific
 // functors that, given the known-zero or known-one bits respectively, and a
 // shift amount, compute the implied known-zero or known-one bits of the shift
 // operator's result respectively for that shift amount. The results from calling
 // KZF and KOF are conservatively combined for all permitted shift amounts.
 template <typename KZFunctor, typename KOFunctor>
 static void computeKnownBitsFromShiftOperator(Operator *I,
               APInt &KnownZero, APInt &KnownOne,
               APInt &KnownZero2, APInt &KnownOne2,
               unsigned Depth, const Query &Q, KZFunctor KZF, KOFunctor KOF) {
   unsigned BitWidth = KnownZero.getBitWidth();
 
   if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
     unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
 
-    computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
-    KnownZero = KZF(KnownZero, ShiftAmt);
-    KnownOne  = KOF(KnownOne, ShiftAmt);
+    computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, Depth + 1, Q);
+    KnownZero = KZF(KnownZero2, ShiftAmt);
+    KnownOne  = KOF(KnownOne2, ShiftAmt);
+
+    computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2);
+
     return;
   }
 
   computeKnownBits(I->getOperand(1), KnownZero, KnownOne, Depth + 1, Q);
 
   // Note: We cannot use KnownZero.getLimitedValue() here, because if
   // BitWidth > 64 and any upper bits are known, we'll end up returning the
   // limit value (which implies all bits are known).
if (ShiftAmt == 0) {
       if (*ShifterOperandIsNonZero)
         continue;
     }
 
     KnownZero &= KZF(KnownZero2, ShiftAmt);
     KnownOne  &= KOF(KnownOne2, ShiftAmt);
   }
 
+  computeKnownSignBitFromShift(I, KnownZero, KnownOne, KnownZero2, KnownOne2);
+
   // If there are no compatible shift amounts, then we've proven that the shift
   // amount must be >= the BitWidth, and the result is undefined. We could
   // return anything we'd like, but we need to make sure the sets of known bits
   // stay disjoint (it should be better for some other code to actually
   // propagate the undef than to pick a value here using known bits).
   if ((KnownZero & KnownOne) != 0) {
     KnownZero.clearAllBits();
     KnownOne.clearAllBits();
if (P->getNumIncomingValues() == 2) {
         Value *L = P->getIncomingValue(i);
         Value *R = P->getIncomingValue(!i);
         Operator *LU = dyn_cast<Operator>(L);
         if (!LU)
           continue;
         unsigned Opcode = LU->getOpcode();
         // Check for operations that have the property that if
         // both their operands have low zero bits, the result
-        // will have low zero bits.
+        // will have low zero bits. Also check for operations 
+        // that are known to produce non-negative or negative
+        // recurrence values. 
         if (Opcode == Instruction::Add ||
             Opcode == Instruction::Sub ||
             Opcode == Instruction::And ||
             Opcode == Instruction::Or ||
             Opcode == Instruction::Mul) {
           Value *LL = LU->getOperand(0);
           Value *LR = LU->getOperand(1);
           // Find a recurrence.
if (P->getNumIncomingValues() == 2) {
 
           // We need to take the minimum number of known bits
           APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
           computeKnownBits(L, KnownZero3, KnownOne3, Depth + 1, Q);
 
           KnownZero = APInt::getLowBitsSet(BitWidth,
                                            std::min(KnownZero2.countTrailingOnes(),
                                                     KnownZero3.countTrailingOnes()));
+
+          auto OverflowOp = dyn_cast<OverflowingBinaryOperator>(LU);
+          if (OverflowOp && OverflowOp->hasNoSignedWrap()) {
+            // If Initial value of recurrence is nonnegative, and we are adding 
+            // a nonnegative number with nsw, the result can only be nonnegative
+            // or poison value regardless of the number of times we execute the 
+            // add in phi recurrence. If initial value is negative and we are 
+            // adding a negative number with nsw, the result can only be 
+            // negative or poison value. Similar arguments apply to sub and mul.
+            //
+            // (add non-negative, non-negative) --> non-negative
+            // (add negative, negative) --> negative
+            if (Opcode == Instruction::Add) {
+              if (KnownZero2.isNegative() && KnownZero3.isNegative())
+                KnownZero |= APInt::getSignBit(BitWidth);
+              else if (KnownOne2.isNegative() && KnownOne3.isNegative())
+                KnownOne |= APInt::getSignBit(BitWidth);
+            }
+            
+            // (sub nsw non-negative, negative) --> non-negative
+            // (sub nsw negative, non-negative) --> negative
+            else if (Opcode == Instruction::Sub && LL == I) {
+              if (KnownZero2.isNegative() && KnownOne3.isNegative())
+                KnownZero |= APInt::getSignBit(BitWidth);
+              else if (KnownOne2.isNegative() && KnownZero3.isNegative())
+                KnownOne |= APInt::getSignBit(BitWidth);
+            }
+            
+            // (mul nsw non-negative, non-negative) --> non-negative
+            else if (Opcode == Instruction::Mul && KnownZero2.isNegative() && 
+                KnownZero3.isNegative())
+              KnownZero |= APInt::getSignBit(BitWidth);
+          }
+
           break;
         }
       }
     }
 
     // Unreachable blocks may have zero-operand PHI nodes.
     if (P->getNumIncomingValues() == 0)
       break;

lib/Transforms/Scalar/IndVarSimplify.cpp

 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopPassManager.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
if (LI->getLoopFor(UsePhi->getParent()) != L) {
         DeadInsts.emplace_back(UsePhi);
         DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi
               << " to " << *WidePhi << "\n");
       }
       return nullptr;
     }
   }
   // Our raison d'etre! Eliminate sign and zero extension.
-  if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) {
+  if ((isa<SExtInst>(DU.NarrowUse) && (IsSigned || DU.NeverNegative)) ||
+      (isa<ZExtInst>(DU.NarrowUse) && (!IsSigned || DU.NeverNegative))) {
     Value *NewDef = DU.WideDef;
     if (DU.NarrowUse->getType() != WideType) {
       unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
       unsigned IVWidth = SE->getTypeSizeInBits(WideType);
       if (CastWidth < IVWidth) {
         // The cast isn't as wide as the IV, so insert a Trunc.
         IRBuilder<> Builder(DU.NarrowUse);
         NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
   // Returning WideUse pushes it on the worklist.
   return WideUse;
 }
 
 /// Add eligible users of NarrowDef to NarrowIVUsers.
 ///
 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
   const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
+  // isKnownPredicate is enough for most cases but still need isKnownNonNegative 
+  // here to work around conservatism in ScalarEvolution about no-wrap flags. 
   bool NeverNegative =
       SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
-                           SE->getConstant(NarrowSCEV->getType(), 0));
+                           SE->getConstant(NarrowSCEV->getType(), 0)) ||
+      isKnownNonNegative(NarrowDef, NarrowDef->getModule()->getDataLayout());
   for (User *U : NarrowDef->users()) {
     Instruction *NarrowUser = cast<Instruction>(U);
 
     // Handle data flow merges and bizarre phi cycles.
     if (!Widened.insert(NarrowUser).second)
       continue;
 
     NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef, NeverNegative);

test/Analysis/ValueTracking/known-non-negative.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; Induction variable is known to be non-negative
+define i32 @test_indvar_nonnegative_add() {
+; CHECK-LABEL: @test_indvar_nonnegative_add(
+; CHECK: br i1 true, label %for.end, label %for.body
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [0, %entry], [%inc, %for.body]
+  %inc = add nsw i32 %i, 1
+  %cmp = icmp sge i32 %i, 0
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:
+  ret i32 %i
+}
+
+define i32 @test_indvar_nonnegative_mul() {
+; CHECK-LABEL: @test_indvar_nonnegative_mul(
+; CHECK: br i1 true, label %for.end, label %for.body
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [1, %entry], [%inc, %for.body]
+  %inc = mul nsw i32 %i, 3
+  %cmp = icmp sge i32 %i, 0
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:
+  ret i32 %i
+}
+
+define i32 @test_indvar_nonnegative_sub(i32 %a) {
+; CHECK-LABEL: @test_indvar_nonnegative_sub(
+; CHECK: br i1 true, label %for.end, label %for.body
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [0, %entry], [%inc, %for.body]
+  %b = or i32 %a, -2147483648
+  %inc = sub nsw i32 %i, %b
+  %cmp = icmp sge i32 %i, 0
+  br i1 %cmp, label %for.end, label %for.body
+
+for.end:
+  ret i32 %i
+}
+
+; Result of left shifting a non-negative integer 
+; with nsw flag should also be non-negative
+define i1 @test_shift_nonnegative(i32 %a) {
+; CHECK-LABEL: @test_shift_nonnegative(
+; CHECK: ret i1 true
+  %b = lshr i32 %a, 2
+  %shift = shl nsw i32 %b, 3
+  %cmp = icmp sge i32 %shift, 0
+  ret i1 %cmp
+}

test/Transforms/BBVectorize/loop1.ll

 ; CHECK-UNRL: %add7 = fadd <2 x double> %add, %mul6
 ; CHECK-UNRL: %mul8 = fmul <2 x double> %3, %3
 ; CHECK-UNRL: %add9 = fadd <2 x double> %2, %2
 ; CHECK-UNRL: %add10 = fadd <2 x double> %add9, %2
 ; CHECK-UNRL: %mul11 = fmul <2 x double> %mul8, %add10
 ; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11
 ; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>*
 ; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8
-; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2
+; CHECK-UNRL: %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
 ; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32
 ; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10
 ; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body
   ret void
 }

test/Transforms/IndVarSimplify/iv-widen-elim-ext.ll

+; RUN: opt < %s -indvars -S | FileCheck %s
+
+target datalayout = "p:64:64:64-n32:64"
+
+; When widening IV and its users, trunc and zext/sext are not needed
+; if the original 32-bit user is known to be non-negative, whether
+; the IV is considered signed or unsigned.
+define void @foo(i32* %A, i32* %B, i32* %C, i32 %N) {
+; CHECK-LABEL: @foo(
+; CHECK-NOT: zext
+; CHECK-NOT: sext
+entry:
+  %cmp1 = icmp slt i32 0, %N
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %idxprom = sext i32 %i.02 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %i.02, 2
+  %idxprom1 = zext i32 %add to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %idxprom1
+  %1 = load i32, i32* %arrayidx2, align 4
+  %add3 = add nsw i32 %0, %1
+  %idxprom4 = zext i32 %i.02 to i64
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %idxprom4
+  store i32 %add3, i32* %arrayidx5, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %N
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}
+
+define void @foo1(i32* %A, i32* %B, i32* %C, i32 %N) {
+; CHECK-LABEL: @foo1(
+; CHECK-NOT: zext
+; CHECK-NOT: sext
+entry:
+  %cmp1 = icmp slt i32 0, %N
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %idxprom = zext i32 %i.02 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %i.02, 2
+  %idxprom1 = sext i32 %add to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %C, i64 %idxprom1
+  %1 = load i32, i32* %arrayidx2, align 4
+  %add3 = add nsw i32 %0, %1
+  %idxprom4 = sext i32 %i.02 to i64
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %idxprom4
+  store i32 %add3, i32* %arrayidx5, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.02, 1
+  %cmp = icmp slt i32 %inc, %N
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.inc
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
+  ret void
+}