[ValueTracking] An improvement to IR ValueTracking on Non-negative Integers

[lihuang]

Summary

An improvement to IR ValueTracking on Non-negative Integers.

Current IR ValueTracking does not recognize the cases below, thus hiding optimization opportunities.

1. Induction variable starting from a non-negative integer and incrementing in each iteration is known to be non-negative.
2. Result of left shifting a non-negative integer with nsw flag is known to be non-negative.

This change is a small improvement to computeKnownBits on PHI node and Shift.

Patch by Ruben Perez.

[sanjoy]

lib/Analysis/ValueTracking.cpp

786

Can this rule be split out into a separate change of its own (with its own tests etc.)?

lib/Transforms/Scalar/IndVarSimplify.cpp

1309 ↗

(On Diff #52635)

Usually we refrain from changing multiple passes at once. Can you please move these IndVarSimplify changes to their own patch, with their own tests?

test/Analysis/ValueTracking/shift-nsw.ll

11 ↗

(On Diff #52635)

• The filename is misleading -- there is a lot going on here other than the "nsw shift" optimization.

• Please break these into small bits of IR functions each of which show one transform.

• Use CHECK-LABEL

[lihuang]

I will separate the change in IndVarSimplify into another patch and create a new diff.

lib/Analysis/ValueTracking.cpp

786

Yes it could, I will make a separate patch for this with its own tests.

lib/Transforms/Scalar/IndVarSimplify.cpp

1309 ↗

(On Diff #52635)

Sure, I will make a separate patch for this change and its tests.

test/Analysis/ValueTracking/shift-nsw.ll

11 ↗

(On Diff #52635)

Thanks! I will update this test.

[lihuang]

Make a separate patch for changes in ValueTracking.cpp. Updated the tests. Changes in IndVarSimplify.cpp will go to another diff.

This change fails a front-end test (Frontend/optimization-remark-options.c), but the change in IndVarSimplify.cpp will fix this test.

[lihuang]

Sorry I didn't generate a full diff, updated.

[lihuang]

Ping :), any suggestions/comments on this change?

[mbodart]

lib/Analysis/ValueTracking.cpp

798

This could be an "else if", as the sign bit cannot be both known 0 and known 1.

1283

For the Sub case we have to be more careful about which value is the LHS and which is the RHS.
The way the code is currently structured, if (LL == I) then R is the LHS and L is the RHS,
otherwise vice versa. So we have to take (LL == I) into account to know whether to
check (KnownZero3, KnownOne2) or (KnownZero2, KnownOne3).

And while I don't know how valuable it would be to catch additional cases, we could set a KnownOne sign bit result for the Sub case if it's (negative -= non-negative), and for the Add case if it's (negative += negative).

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

7

Please add additional test cases for mul and sub.

[lihuang]

Address Mitch's comments.

For the sub case, I added the check (LL == I), this is the case when IV is LHS. I didn't add the case when IV is RHS because it's hard to infer anything meaningful.

[mbodart]

lib/Analysis/ValueTracking.cpp

1291

This "if", and the one below for Mul, should be "else if".

Otherwise LGTM!

[lihuang]

Rebase the same patch on the latest source.

This ValueTracking change breaks a FE test (clang/test/Frontend/optimization-remark-options.c), but now the test could be fixed by D18777 and D21773.

[lihuang]

In D18777#468445, @lihuang wrote:

Rebase the same patch on the latest source.

This ValueTracking change breaks a FE test (clang/test/Frontend/optimization-remark-options.c), but now the test could be fixed by D18777 and D21773.

Sorry, my mistake, the test could be fixed by D18867 and D21773.

[lihuang]

Rebase this change on latest source. The test in D21773 should be fixed by D18867.

[lihuang]

Another Ping for this patch :).

Sanjoy, this patch and D18867 depends on each other so they need to go in at the same time, otherwise it will break tests.

[sanjoy]

lib/Analysis/ValueTracking.cpp

788

I'd s/KnownZero2/KnownZeroOp (same for KnownOne2), and s/KnownZero/KnownZeroResult/. Also, pass in KnownZeroOp by const ref.

796

Why can't this be folded into the KZF and KOF for the Instruction::Shl case?

1271

Use auto *.

1288

What does this bit have to do with the changes to how we handle shifts? If they're not related, they should definitely be reviewed/tested/committed separately.

[lihuang]

lib/Analysis/ValueTracking.cpp

796

Thank you for suggesting this, will fold this logic to KZF and KOF

1288

Will separate out the shift part

[lihuang]

Separate the non-negative shift changes to another patch. Address Sanjoy's comments.

[lihuang]

The non-negative shift part goes to patch D23296.

[sanjoy]

Mostly looks okay, I just have a few minor nits.

lib/Analysis/ValueTracking.cpp

1273

s/Initial/initial/

1280

Nit: I'd use setBit instead of |= with a new APInt. For BitWidth larger than 64, what you have currently will allocate unnecessarily, and I think setBit will look just as obvious (if not more).

1300

Indent looks off -- please use clang-format.

[lihuang]

Use APInt::setBit, fix the indentation

[lihuang]

lib/Analysis/ValueTracking.cpp

1280

Agree, changed to use setBit

[sanjoy]

lgtm

[sanjoy]

lgtm

[rogfer01]

This change caused a noticeable regression in benchmark MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT.

You can check this in the daily LNT results from 11th August (scroll down until MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt)

http://llvm.org/perf/db_default/v4/nts/daily_report/2016/8/11?day_start=16

MultiSource/Benchmarks/TSVC/Symbolics-dbl/Symbolics-dbl is also affected.

Can you take a look at it?

Thank you!

[reames]

In D18777#513652, @rogfer01 wrote:

This change caused a noticeable regression in benchmark MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT.

This also caused a number of major regressions on our internal benchmarking framework. I would like to see the change reverted while the public regression mentioned above is investigated. We can provide some analysis of what went wrong in our internal environment, but I'd prefer to avoid investing that effort if we can diagnose from public benchmarks.

[lihuang]

I will look into the regressions on public benchmarks.

If you'd prefer reverting this change then you need also revert D18867 since that change relies on this.

[lihuang]

The problem is in indvarsimplify, this patch results in redundant trunc/sext that should be eliminated by indvarsimplify but not, causing the loop in TSVC/s174 not vectorizable. I will submit a fix for review.

[lihuang]

Rebase this patch to latest source.

As the performance problem has been fixed by r282650 (D24280), we can re-commit this patch.

[lihuang]

Hi Sanjoy and Artur,

This patch is the same as before, can we re-commit it?

[reames]

Recommit LGTM

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;

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
 }