[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

780

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

780

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

792

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

1317

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

6 ↗

(On Diff #52740)

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

1325

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

782

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

790

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

1305

Use auto *.

1322

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

790

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

1322

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

1307

s/Initial/initial/

1314

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

1334

Indent looks off -- please use clang-format.

[lihuang]

Use APInt::setBit, fix the indentation

[lihuang]

lib/Analysis/ValueTracking.cpp

1314

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());
     }
   }
 }
 
 // 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.
 static void computeKnownBitsFromShiftOperator(
     const Operator *I, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2,
     APInt &KnownOne2, unsigned Depth, const Query &Q,
     function_ref<APInt(const APInt &, unsigned)> KZF,
     function_ref<APInt(const APInt &, unsigned)> 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);
     // If there is conflict between KnownZero and KnownOne, this must be an
     // overflowing left shift, so the shift result is undefined. Clear KnownZero
     // and KnownOne bits so that other code could propagate this undef.
if (P->getNumIncomingValues() == 2) {
           // Ok, we have a PHI of the form L op= R. Check for low
           // zero bits.
           computeKnownBits(R, KnownZero2, KnownOne2, Depth + 1, Q);
 
           // 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()));
+          KnownZero = APInt::getLowBitsSet(
+              BitWidth, std::min(KnownZero2.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.setBit(BitWidth - 1);
+              else if (KnownOne2.isNegative() && KnownOne3.isNegative())
+                KnownOne.setBit(BitWidth - 1);
+            }
+
+            // (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.setBit(BitWidth - 1);
+              else if (KnownOne2.isNegative() && KnownZero3.isNegative())
+                KnownOne.setBit(BitWidth - 1);
+            }
+
+            // (mul nsw non-negative, non-negative) --> non-negative
+            else if (Opcode == Instruction::Mul && KnownZero2.isNegative() &&
+                     KnownZero3.isNegative())
+              KnownZero.setBit(BitWidth - 1);
+          }
+
           break;
         }
       }
     }
 
     // Unreachable blocks may have zero-operand PHI nodes.
     if (P->getNumIncomingValues() == 0)
       break;

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
 }