[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

805 ↗

(On Diff #52635)

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

805 ↗

(On Diff #52635)

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

817 ↗

(On Diff #52740)

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

1301 ↗

(On Diff #52740)

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

1292 ↗

(On Diff #54519)

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 ↗

(On Diff #65843)

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

796 ↗

(On Diff #65843)

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

1271 ↗

(On Diff #65843)

Use auto *.

1288 ↗

(On Diff #65843)

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 ↗

(On Diff #65843)

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

1288 ↗

(On Diff #65843)

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

1248 ↗

(On Diff #67236)

s/Initial/initial/

1255 ↗

(On Diff #67236)

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

1275 ↗

(On Diff #67236)

Indent looks off -- please use clang-format.

[lihuang]

Use APInt::setBit, fix the indentation

[lihuang]

lib/Analysis/ValueTracking.cpp

1255 ↗

(On Diff #67399)

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

llvm/trunk/lib/Analysis/ValueTracking.cpp

 
 const unsigned MaxDepth = 6;
 
 // Controls the number of uses of the value searched for possible
 // dominating comparisons.
 static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
                                               cl::Hidden, cl::init(20));
 
+// This optimization is known to cause performance regressions is some cases,
+// keep it under a temporary flag for now.
+static cl::opt<bool>
+DontImproveNonNegativePhiBits("dont-improve-non-negative-phi-bits",
+                              cl::Hidden, cl::init(true));
+
 /// Returns the bitwidth of the given scalar or pointer type (if unknown returns
 /// 0). For vector types, returns the element type's bitwidth.
 static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
   if (unsigned BitWidth = Ty->getScalarSizeInBits())
     return BitWidth;
 
   return DL.getPointerTypeSizeInBits(Ty);
 }
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(),
+
+          if (DontImproveNonNegativePhiBits)
+            break;
+
+          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;

llvm/trunk/test/Transforms/BBVectorize/loop1.ll

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 ; RUN: opt < %s -bb-vectorize -bb-vectorize-req-chain-depth=3 -bb-vectorize-ignore-target-info -instcombine -gvn -S | FileCheck %s
-; RUN: opt < %s -basicaa -loop-unroll -unroll-threshold=45 -unroll-allow-partial -bb-vectorize -bb-vectorize-req-chain-depth=3 -bb-vectorize-ignore-target-info -instcombine -gvn -S | FileCheck %s -check-prefix=CHECK-UNRL
+; RUN: opt < %s -dont-improve-non-negative-phi-bits=false -basicaa -loop-unroll -unroll-threshold=45 -unroll-allow-partial -bb-vectorize -bb-vectorize-req-chain-depth=3 -bb-vectorize-ignore-target-info -instcombine -gvn -S | FileCheck %s -check-prefix=CHECK-UNRL
 ; The second check covers the use of alias analysis (with loop unrolling).
 
 define void @test1(double* noalias %out, double* noalias %in1, double* noalias %in2) nounwind uwtable {
 entry:
   br label %for.body
 ; CHECK-LABEL: @test1(
 ; CHECK-UNRL-LABEL: @test1(
 

 ; 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
 }