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