1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
; RUN: opt < %s -S -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
declare i1 @cond()
define i32 @test_01(i32 %a, i32 %b) {
; CHECK-LABEL: 'test_01'
; CHECK-NEXT: Classifying expressions for: @test_01
; CHECK-NEXT: %outer.iv = phi i32 [ 0, %entry ], [ %iv.next, %outer.backedge ]
; CHECK-NEXT: --> %outer.iv U: [0,-2147483647) S: [0,-2147483647) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
; CHECK-NEXT: %iv = phi i32 [ 0, %outer ], [ %iv.next, %inner.backedge ]
; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%inner> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
; CHECK-NEXT: %iv.next = add nuw nsw i32 %iv, 1
; CHECK-NEXT: --> {1,+,1}<nuw><%inner> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
; CHECK-NEXT: %inner.loop.cond = call i1 @cond()
; CHECK-NEXT: --> %inner.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Variant, %outer: Variant }
; CHECK-NEXT: %outer.loop.cond = call i1 @cond()
; CHECK-NEXT: --> %outer.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
; CHECK-NEXT: Determining loop execution counts for: @test_01
; CHECK-NEXT: Loop %inner: <multiple exits> Unpredictable backedge-taken count.
; CHECK-NEXT: exit count for inner: %b
; CHECK-NEXT: exit count for inner.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %inner: constant max backedge-taken count is 2147483647
; CHECK-NEXT: Loop %inner: symbolic max backedge-taken count is %b
; CHECK-NEXT: symbolic max exit count for inner: %b
; CHECK-NEXT: symbolic max exit count for inner.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %inner: Unpredictable predicated backedge-taken count.
; CHECK-NEXT: Loop %outer: <multiple exits> Unpredictable backedge-taken count.
; CHECK-NEXT: exit count for inner: ***COULDNOTCOMPUTE***
; CHECK-NEXT: exit count for outer.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %outer: Unpredictable constant max backedge-taken count.
; CHECK-NEXT: Loop %outer: Unpredictable symbolic max backedge-taken count.
; CHECK-NEXT: symbolic max exit count for inner: ***COULDNOTCOMPUTE***
; CHECK-NEXT: symbolic max exit count for outer.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %outer: Unpredictable predicated backedge-taken count.
;
entry:
%b_is_non_negative = icmp sge i32 %b, 0
br i1 %b_is_non_negative, label %outer, label %failure
outer:
%outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge]
br label %inner
inner:
%iv = phi i32 [0, %outer], [%iv.next, %inner.backedge]
%signed_cond = icmp slt i32 %iv, %b
br i1 %signed_cond, label %inner.backedge, label %side.exit
inner.backedge:
%iv.next = add nuw nsw i32 %iv, 1
%inner.loop.cond = call i1 @cond()
br i1 %inner.loop.cond, label %inner, label %outer.backedge
outer.backedge:
%outer.loop.cond = call i1 @cond()
br i1 %outer.loop.cond, label %outer, label %exit
failure:
unreachable
side.exit:
ret i32 0
exit:
ret i32 1
}
; FIXME: both outer.iv and iv here can be proved non-negative.
define i32 @test_02(i32 %a, i32 %b) {
; CHECK-LABEL: 'test_02'
; CHECK-NEXT: Classifying expressions for: @test_02
; CHECK-NEXT: %outer.iv = phi i32 [ 0, %entry ], [ %iv.next, %outer.backedge ]
; CHECK-NEXT: --> %outer.iv U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
; CHECK-NEXT: %iv = phi i32 [ %outer.iv, %outer ], [ %iv.next, %inner.backedge ]
; CHECK-NEXT: --> {%outer.iv,+,1}<nuw><nsw><%inner> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
; CHECK-NEXT: %iv.next = add nuw nsw i32 %iv, 1
; CHECK-NEXT: --> {(1 + %outer.iv),+,1}<nw><%inner> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
; CHECK-NEXT: %inner.loop.cond = call i1 @cond()
; CHECK-NEXT: --> %inner.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Variant, %outer: Variant }
; CHECK-NEXT: %outer.loop.cond = call i1 @cond()
; CHECK-NEXT: --> %outer.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
; CHECK-NEXT: Determining loop execution counts for: @test_02
; CHECK-NEXT: Loop %inner: <multiple exits> Unpredictable backedge-taken count.
; CHECK-NEXT: exit count for inner: ((-1 * %outer.iv) + (%b smax %outer.iv))
; CHECK-NEXT: exit count for inner.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %inner: constant max backedge-taken count is -1
; CHECK-NEXT: Loop %inner: symbolic max backedge-taken count is ((-1 * %outer.iv) + (%b smax %outer.iv))
; CHECK-NEXT: symbolic max exit count for inner: ((-1 * %outer.iv) + (%b smax %outer.iv))
; CHECK-NEXT: symbolic max exit count for inner.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %inner: Unpredictable predicated backedge-taken count.
; CHECK-NEXT: Loop %outer: <multiple exits> Unpredictable backedge-taken count.
; CHECK-NEXT: exit count for inner: ***COULDNOTCOMPUTE***
; CHECK-NEXT: exit count for outer.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %outer: Unpredictable constant max backedge-taken count.
; CHECK-NEXT: Loop %outer: Unpredictable symbolic max backedge-taken count.
; CHECK-NEXT: symbolic max exit count for inner: ***COULDNOTCOMPUTE***
; CHECK-NEXT: symbolic max exit count for outer.backedge: ***COULDNOTCOMPUTE***
; CHECK-NEXT: Loop %outer: Unpredictable predicated backedge-taken count.
;
entry:
%b_is_non_negative = icmp sge i32 %b, 0
br i1 %b_is_non_negative, label %outer, label %failure
outer:
%outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge]
br label %inner
inner:
%iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
%signed_cond = icmp slt i32 %iv, %b
br i1 %signed_cond, label %inner.backedge, label %side.exit
inner.backedge:
%iv.next = add nuw nsw i32 %iv, 1
%inner.loop.cond = call i1 @cond()
br i1 %inner.loop.cond, label %inner, label %outer.backedge
outer.backedge:
%outer.loop.cond = call i1 @cond()
br i1 %outer.loop.cond, label %outer, label %exit
failure:
unreachable
side.exit:
ret i32 0
exit:
ret i32 1
}
|
