From b10f6876cd7353d1e3fe2b13cf3f0e8171d8335f Mon Sep 17 00:00:00 2001 From: Andrew Kaylor Date: Wed, 10 Aug 2016 18:47:19 +0000 Subject: [PATCH] [ValueTracking] An improvement to IR ValueTracking on Non-negative Integers Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267 --- llvm/lib/Analysis/ValueTracking.cpp | 38 ++++++++- llvm/test/Analysis/ValueTracking/iv-known-sign.ll | 97 +++++++++++++++++++++++ llvm/test/Transforms/BBVectorize/loop1.ll | 2 +- 3 files changed, 135 insertions(+), 2 deletions(-) create mode 100644 llvm/test/Analysis/ValueTracking/iv-known-sign.ll diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 59c39e5..c4403c6 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -1272,7 +1272,9 @@ static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero, 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 || @@ -1298,6 +1300,40 @@ static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero, KnownZero = APInt::getLowBitsSet(BitWidth, std::min(KnownZero2.countTrailingOnes(), KnownZero3.countTrailingOnes())); + + auto *OverflowOp = dyn_cast(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; } } diff --git a/llvm/test/Analysis/ValueTracking/iv-known-sign.ll b/llvm/test/Analysis/ValueTracking/iv-known-sign.ll new file mode 100644 index 0000000..303031b --- /dev/null +++ b/llvm/test/Analysis/ValueTracking/iv-known-sign.ll @@ -0,0 +1,97 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s + +; Induction variable is known to be non-negative +; when its initial value is non-negative and +; increments by non-negative value +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 +} + +; Induction variable is known to be non-negative +; when its initial value is non-negative and +; is multiplied by a non-negative value in each +; iteration +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 +} + +; Induction variable is known to be non-negative, +; Similar to add +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 +} + +; Induction variable is known to be negative when +; its initial value is negative and decrements by +; a non-negative value +define i32 @test_indvar_negative_add() { +; CHECK-LABEL: @test_indvar_negative_add( +; 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 = add nsw i32 %i, -1 + %cmp = icmp slt i32 %i, 0 + br i1 %cmp, label %for.end, label %for.body + +for.end: + ret i32 %i +} + +; Induction variable is known to be negative, +; similar to add +define i32 @test_indvar_negative_sub(i32 %a) { +; CHECK-LABEL: @test_indvar_negative_sub( +; 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] + %b = and i32 %a, 2147483647 + %inc = sub nsw i32 %i, %b + %cmp = icmp slt i32 %i, 0 + br i1 %cmp, label %for.end, label %for.body + +for.end: + ret i32 %i +} diff --git a/llvm/test/Transforms/BBVectorize/loop1.ll b/llvm/test/Transforms/BBVectorize/loop1.ll index 70a5def..445dec1 100644 --- a/llvm/test/Transforms/BBVectorize/loop1.ll +++ b/llvm/test/Transforms/BBVectorize/loop1.ll @@ -83,7 +83,7 @@ for.body: ; preds = %for.body, %entry ; 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 -- 2.7.4