Skip to content

Commit b10f687

Browse files
author
Andrew Kaylor
committedAug 10, 2016
[ValueTracking] An improvement to IR ValueTracking on Non-negative Integers
Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267
·
llvmorg-21-initllvmorg-4.0.0-rc1
1 parent c9c2bba commit b10f687

File tree

3 files changed

+135
-2
lines changed

3 files changed

+135
-2
lines changed
 

‎llvm/lib/Analysis/ValueTracking.cpp

+37-1
Original file line numberDiff line numberDiff line change
@@ -1272,7 +1272,9 @@ static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero,
12721272
unsigned Opcode = LU->getOpcode();
12731273
// Check for operations that have the property that if
12741274
// both their operands have low zero bits, the result
1275-
// will have low zero bits.
1275+
// will have low zero bits. Also check for operations
1276+
// that are known to produce non-negative or negative
1277+
// recurrence values.
12761278
if (Opcode == Instruction::Add ||
12771279
Opcode == Instruction::Sub ||
12781280
Opcode == Instruction::And ||
@@ -1298,6 +1300,40 @@ static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero,
12981300
KnownZero = APInt::getLowBitsSet(BitWidth,
12991301
std::min(KnownZero2.countTrailingOnes(),
13001302
KnownZero3.countTrailingOnes()));
1303+
1304+
auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(LU);
1305+
if (OverflowOp && OverflowOp->hasNoSignedWrap()) {
1306+
// If initial value of recurrence is nonnegative, and we are adding
1307+
// a nonnegative number with nsw, the result can only be nonnegative
1308+
// or poison value regardless of the number of times we execute the
1309+
// add in phi recurrence. If initial value is negative and we are
1310+
// adding a negative number with nsw, the result can only be
1311+
// negative or poison value. Similar arguments apply to sub and mul.
1312+
//
1313+
// (add non-negative, non-negative) --> non-negative
1314+
// (add negative, negative) --> negative
1315+
if (Opcode == Instruction::Add) {
1316+
if (KnownZero2.isNegative() && KnownZero3.isNegative())
1317+
KnownZero.setBit(BitWidth - 1);
1318+
else if (KnownOne2.isNegative() && KnownOne3.isNegative())
1319+
KnownOne.setBit(BitWidth - 1);
1320+
}
1321+
1322+
// (sub nsw non-negative, negative) --> non-negative
1323+
// (sub nsw negative, non-negative) --> negative
1324+
else if (Opcode == Instruction::Sub && LL == I) {
1325+
if (KnownZero2.isNegative() && KnownOne3.isNegative())
1326+
KnownZero.setBit(BitWidth - 1);
1327+
else if (KnownOne2.isNegative() && KnownZero3.isNegative())
1328+
KnownOne.setBit(BitWidth - 1);
1329+
}
1330+
1331+
// (mul nsw non-negative, non-negative) --> non-negative
1332+
else if (Opcode == Instruction::Mul && KnownZero2.isNegative() &&
1333+
KnownZero3.isNegative())
1334+
KnownZero.setBit(BitWidth - 1);
1335+
}
1336+
13011337
break;
13021338
}
13031339
}

‎llvm/test/Analysis/ValueTracking/iv-known-sign.ll

+97
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
; RUN: opt < %s -instcombine -S | FileCheck %s
2+
3+
; Induction variable is known to be non-negative
4+
; when its initial value is non-negative and
5+
; increments by non-negative value
6+
define i32 @test_indvar_nonnegative_add() {
7+
; CHECK-LABEL: @test_indvar_nonnegative_add(
8+
; CHECK: br i1 true, label %for.end, label %for.body
9+
entry:
10+
br label %for.body
11+
12+
for.body:
13+
%i = phi i32 [0, %entry], [%inc, %for.body]
14+
%inc = add nsw i32 %i, 1
15+
%cmp = icmp sge i32 %i, 0
16+
br i1 %cmp, label %for.end, label %for.body
17+
18+
for.end:
19+
ret i32 %i
20+
}
21+
22+
; Induction variable is known to be non-negative
23+
; when its initial value is non-negative and
24+
; is multiplied by a non-negative value in each
25+
; iteration
26+
define i32 @test_indvar_nonnegative_mul() {
27+
; CHECK-LABEL: @test_indvar_nonnegative_mul(
28+
; CHECK: br i1 true, label %for.end, label %for.body
29+
entry:
30+
br label %for.body
31+
32+
for.body:
33+
%i = phi i32 [1, %entry], [%inc, %for.body]
34+
%inc = mul nsw i32 %i, 3
35+
%cmp = icmp sge i32 %i, 0
36+
br i1 %cmp, label %for.end, label %for.body
37+
38+
for.end:
39+
ret i32 %i
40+
}
41+
42+
; Induction variable is known to be non-negative,
43+
; Similar to add
44+
define i32 @test_indvar_nonnegative_sub(i32 %a) {
45+
; CHECK-LABEL: @test_indvar_nonnegative_sub(
46+
; CHECK: br i1 true, label %for.end, label %for.body
47+
entry:
48+
br label %for.body
49+
50+
for.body:
51+
%i = phi i32 [0, %entry], [%inc, %for.body]
52+
%b = or i32 %a, -2147483648
53+
%inc = sub nsw i32 %i, %b
54+
%cmp = icmp sge i32 %i, 0
55+
br i1 %cmp, label %for.end, label %for.body
56+
57+
for.end:
58+
ret i32 %i
59+
}
60+
61+
; Induction variable is known to be negative when
62+
; its initial value is negative and decrements by
63+
; a non-negative value
64+
define i32 @test_indvar_negative_add() {
65+
; CHECK-LABEL: @test_indvar_negative_add(
66+
; CHECK: br i1 true, label %for.end, label %for.body
67+
entry:
68+
br label %for.body
69+
70+
for.body:
71+
%i = phi i32 [-1, %entry], [%inc, %for.body]
72+
%inc = add nsw i32 %i, -1
73+
%cmp = icmp slt i32 %i, 0
74+
br i1 %cmp, label %for.end, label %for.body
75+
76+
for.end:
77+
ret i32 %i
78+
}
79+
80+
; Induction variable is known to be negative,
81+
; similar to add
82+
define i32 @test_indvar_negative_sub(i32 %a) {
83+
; CHECK-LABEL: @test_indvar_negative_sub(
84+
; CHECK: br i1 true, label %for.end, label %for.body
85+
entry:
86+
br label %for.body
87+
88+
for.body:
89+
%i = phi i32 [-1, %entry], [%inc, %for.body]
90+
%b = and i32 %a, 2147483647
91+
%inc = sub nsw i32 %i, %b
92+
%cmp = icmp slt i32 %i, 0
93+
br i1 %cmp, label %for.end, label %for.body
94+
95+
for.end:
96+
ret i32 %i
97+
}

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

+1-1
Original file line numberDiff line numberDiff line change
@@ -83,7 +83,7 @@ for.body: ; preds = %for.body, %entry
8383
; CHECK-UNRL: %add12 = fadd <2 x double> %add7, %mul11
8484
; CHECK-UNRL: %4 = bitcast double* %arrayidx14 to <2 x double>*
8585
; CHECK-UNRL: store <2 x double> %add12, <2 x double>* %4, align 8
86-
; CHECK-UNRL: %indvars.iv.next.1 = add nsw i64 %indvars.iv, 2
86+
; CHECK-UNRL: %indvars.iv.next.1 = add nuw nsw i64 %indvars.iv, 2
8787
; CHECK-UNRL: %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32
8888
; CHECK-UNRL: %exitcond.1 = icmp eq i32 %lftr.wideiv.1, 10
8989
; CHECK-UNRL: br i1 %exitcond.1, label %for.end, label %for.body

0 commit comments

Comments
 (0)
Please sign in to comment.