• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1; RUN: opt < %s -nary-reassociate -S | FileCheck %s
2
3target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
4
5declare void @foo(i32)
6
7; foo(a + c);
8; foo((a + (b + c));
9;   =>
10; t = a + c;
11; foo(t);
12; foo(t + b);
13define void @left_reassociate(i32 %a, i32 %b, i32 %c) {
14; CHECK-LABEL: @left_reassociate(
15  %1 = add i32 %a, %c
16; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c
17  call void @foo(i32 %1)
18  %2 = add i32 %b, %c
19  %3 = add i32 %a, %2
20; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b
21  call void @foo(i32 %3)
22; CHECK-NEXT: call void @foo(i32 [[RESULT]])
23  ret void
24}
25
26; foo(a + c);
27; foo((a + b) + c);
28;   =>
29; t = a + c;
30; foo(t);
31; foo(t + b);
32define void @right_reassociate(i32 %a, i32 %b, i32 %c) {
33; CHECK-LABEL: @right_reassociate(
34  %1 = add i32 %a, %c
35; CHECK: [[BASE:%[a-zA-Z0-9]+]] = add i32 %a, %c
36  call void @foo(i32 %1)
37  %2 = add i32 %a, %b
38  %3 = add i32 %2, %c
39; CHECK: [[RESULT:%[a-zA-Z0-9]+]] = add i32 [[BASE]], %b
40  call void @foo(i32 %3)
41; CHECK-NEXT: call void @foo(i32 [[RESULT]])
42  ret void
43}
44
45; t1 = a + c;
46; foo(t1);
47; t2 = a + b;
48; foo(t2);
49; t3 = t2 + c;
50; foo(t3);
51;
52; Do not rewrite t3 into t1 + b because t2 is used elsewhere and is likely free.
53define void @no_reassociate(i32 %a, i32 %b, i32 %c) {
54; CHECK-LABEL: @no_reassociate(
55  %1 = add i32 %a, %c
56; CHECK: add i32 %a, %c
57  call void @foo(i32 %1)
58  %2 = add i32 %a, %b
59; CHECK: add i32 %a, %b
60  call void @foo(i32 %2)
61  %3 = add i32 %2, %c
62; CHECK: add i32 %2, %c
63  call void @foo(i32 %3)
64  ret void
65}
66
67; if (p1)
68;   foo(a + c);
69; if (p2)
70;   foo(a + c);
71; if (p3)
72;   foo((a + b) + c);
73;
74; No action because (a + c) does not dominate ((a + b) + c).
75define void @conditional(i1 %p1, i1 %p2, i1 %p3, i32 %a, i32 %b, i32 %c) {
76; CHECK-LABEL: @conditional(
77entry:
78  br i1 %p1, label %then1, label %branch1
79
80then1:
81  %0 = add i32 %a, %c
82; CHECK: add i32 %a, %c
83  call void @foo(i32 %0)
84  br label %branch1
85
86branch1:
87  br i1 %p2, label %then2, label %branch2
88
89then2:
90  %1 = add i32 %a, %c
91; CHECK: add i32 %a, %c
92  call void @foo(i32 %1)
93  br label %branch2
94
95branch2:
96  br i1 %p3, label %then3, label %return
97
98then3:
99  %2 = add i32 %a, %b
100; CHECK: %2 = add i32 %a, %b
101  %3 = add i32 %2, %c
102; CHECK: add i32 %2, %c
103  call void @foo(i32 %3)
104  br label %return
105
106return:
107  ret void
108}
109
110; This test involves more conditional reassociation candidates. It exercises
111; the stack optimization in tryReassociatedAdd that pops the candidates that
112; do not dominate the current instruction.
113;
114;       def1
115;      cond1
116;      /  \
117;     /    \
118;   cond2  use2
119;   /  \
120;  /    \
121; def2  def3
122;      cond3
123;       /  \
124;      /    \
125;    def4   use1
126;
127; NaryReassociate should match use1 with def3, and use2 with def1.
128define void @conditional2(i32 %a, i32 %b, i32 %c, i1 %cond1, i1 %cond2, i1 %cond3) {
129entry:
130  %def1 = add i32 %a, %b
131  br i1 %cond1, label %bb1, label %bb6
132bb1:
133  br i1 %cond2, label %bb2, label %bb3
134bb2:
135  %def2 = add i32 %a, %b
136  call void @foo(i32 %def2)
137  ret void
138bb3:
139  %def3 = add i32 %a, %b
140  br i1 %cond3, label %bb4, label %bb5
141bb4:
142  %def4 = add i32 %a, %b
143  call void @foo(i32 %def4)
144  ret void
145bb5:
146  %0 = add i32 %a, %c
147  %1 = add i32 %0, %b
148; CHECK: [[t1:%[0-9]+]] = add i32 %def3, %c
149  call void @foo(i32 %1) ; foo((a + c) + b);
150; CHECK-NEXT: call void @foo(i32 [[t1]])
151  ret void
152bb6:
153  %2 = add i32 %a, %c
154  %3 = add i32 %2, %b
155; CHECK: [[t2:%[0-9]+]] = add i32 %def1, %c
156  call void @foo(i32 %3) ; foo((a + c) + b);
157; CHECK-NEXT: call void @foo(i32 [[t2]])
158  ret void
159}
160
161; foo((a + b) + c)
162; foo(((a + d) + b) + c)
163;   =>
164; t = (a + b) + c;
165; foo(t);
166; foo(t + d);
167define void @quaternary(i32 %a, i32 %b, i32 %c, i32 %d) {
168; CHECK-LABEL: @quaternary(
169  %1 = add i32 %a, %b
170  %2 = add i32 %1, %c
171  call void @foo(i32 %2)
172; CHECK: call void @foo(i32 [[TMP1:%[a-zA-Z0-9]]])
173  %3 = add i32 %a, %d
174  %4 = add i32 %3, %b
175  %5 = add i32 %4, %c
176; CHECK: [[TMP2:%[a-zA-Z0-9]]] = add i32 [[TMP1]], %d
177  call void @foo(i32 %5)
178; CHECK: call void @foo(i32 [[TMP2]]
179  ret void
180}
181
182define void @iterative(i32 %a, i32 %b, i32 %c) {
183  %ab = add i32 %a, %b
184  %abc = add i32 %ab, %c
185  call void @foo(i32 %abc)
186
187  %ab2 = add i32 %ab, %b
188  %ab2c = add i32 %ab2, %c
189; CHECK: %ab2c = add i32 %abc, %b
190  call void @foo(i32 %ab2c)
191; CHECK-NEXT: call void @foo(i32 %ab2c)
192
193  %ab3 = add i32 %ab2, %b
194  %ab3c = add i32 %ab3, %c
195; CHECK-NEXT: %ab3c = add i32 %ab2c, %b
196  call void @foo(i32 %ab3c)
197; CHECK-NEXT: call void @foo(i32 %ab3c)
198
199  ret void
200}
201
202define void @avoid_infinite_loop(i32 %a, i32 %b) {
203; CHECK-LABEL: @avoid_infinite_loop
204  %ab = add i32 %a, %b
205; CHECK-NEXT: %ab
206  %ab2 = add i32 %ab, %b
207; CHECK-NEXT: %ab2
208  call void @foo(i32 %ab2)
209; CHECK-NEXT: @foo(i32 %ab2)
210  ret void
211}
212