1; Test merging of blocks with phi nodes.
2;
3; RUN: opt < %s -simplifycfg -S > %t
4; RUN: not grep N: %t
5; RUN: not grep X: %t
6; RUN: not grep 'switch i32[^U]+%U' %t
7; RUN: not grep "^BB.tomerge" %t
8; RUN: grep "^BB.nomerge" %t | count 2
9;
10
11; ModuleID = '<stdin>'
12declare i1 @foo()
13
14declare i1 @bar(i32)
15
16define i32 @test(i1 %a) {
17Q:
18        br i1 %a, label %N, label %M
19N:              ; preds = %Q
20        br label %M
21M:              ; preds = %N, %Q
22        ; It's ok to merge N and M because the incoming values for W are the
23        ; same for both cases...
24        %W = phi i32 [ 2, %N ], [ 2, %Q ]               ; <i32> [#uses=1]
25        %R = add i32 %W, 1              ; <i32> [#uses=1]
26        ret i32 %R
27}
28
29; Test merging of blocks with phi nodes where at least one incoming value
30; in the successor is undef.
31define i8 @testundef(i32 %u) {
32R:
33  switch i32 %u, label %U [
34    i32 0, label %S
35    i32 1, label %T
36    i32 2, label %T
37  ]
38
39S:                                            ; preds = %R
40  br label %U
41
42T:                                           ; preds = %R, %R
43  br label %U
44
45U:                                        ; preds = %T, %S, %R
46  ; We should be able to merge either the S or T block into U by rewriting
47  ; R's incoming value with the incoming value of that predecessor since
48  ; R's incoming value is undef and both of those predecessors are simple
49  ; unconditional branches.
50  %val.0 = phi i8 [ undef, %R ], [ 1, %T ], [ 0, %S ]
51  ret i8 %val.0
52}
53
54; Test merging of blocks with phi nodes where at least one incoming value
55; in the successor is undef.
56define i8 @testundef2(i32 %u, i32* %A) {
57V:
58  switch i32 %u, label %U [
59    i32 0, label %W
60    i32 1, label %X
61    i32 2, label %X
62    i32 3, label %Z
63  ]
64
65W:                                            ; preds = %V
66  br label %U
67
68Z:
69  store i32 0, i32* %A, align 4
70  br label %X
71
72X:                                           ; preds = %V, %V, %Z
73  br label %U
74
75U:                                        ; preds = %X, %W, %V
76  ; We should be able to merge either the W or X block into U by rewriting
77  ; V's incoming value with the incoming value of that predecessor since
78  ; V's incoming value is undef and both of those predecessors are simple
79  ; unconditional branches. Note that X has predecessors beyond
80  ; the direct predecessors of U.
81  %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 1, %W ]
82  ret i8 %val.0
83}
84
85define i8 @testmergesome(i32 %u, i32* %A) {
86V:
87  switch i32 %u, label %Y [
88    i32 0, label %W
89    i32 1, label %X
90    i32 2, label %X
91    i32 3, label %Z
92  ]
93
94W:                                            ; preds = %V
95  store i32 1, i32* %A, align 4
96  br label %Y
97
98Z:
99  store i32 0, i32* %A, align 4
100  br label %X
101
102X:                                           ; preds = %V, %Z
103  br label %Y
104
105Y:                                        ; preds = %X, %W, %V
106  ; After merging X into Y, we should have 5 predecessors
107  ; and thus 5 incoming values to the phi.
108  %val.0 = phi i8 [ 1, %V ], [ 1, %X ], [ 2, %W ]
109  ret i8 %val.0
110}
111
112
113define i8 @testmergesome2(i32 %u, i32* %A) {
114V:
115  switch i32 %u, label %W [
116    i32 0, label %W
117    i32 1, label %Y
118    i32 2, label %X
119    i32 4, label %Y
120  ]
121
122W:                                            ; preds = %V
123  store i32 1, i32* %A, align 4
124  br label %Y
125
126X:                                           ; preds = %V, %Z
127  br label %Y
128
129Y:                                        ; preds = %X, %W, %V
130  ; Ensure that we deal with both undef inputs for V when we merge in X.
131  %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 2, %W ], [ undef, %V ]
132  ret i8 %val.0
133}
134
135; This function can't be merged
136define void @a() {
137entry:
138	br label %BB.nomerge
139
140BB.nomerge:		; preds = %Common, %entry
141        ; This phi has a conflicting value (0) with below phi (2), so blocks
142        ; can't be merged.
143	%a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
144	br label %Succ
145
146Succ:		; preds = %Common, %BB.nomerge
147	%b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
148	%conde = call i1 @foo( )		; <i1> [#uses=1]
149	br i1 %conde, label %Common, label %Exit
150
151Common:		; preds = %Succ
152	%cond = call i1 @foo( )		; <i1> [#uses=1]
153	br i1 %cond, label %BB.nomerge, label %Succ
154
155Exit:		; preds = %Succ
156	ret void
157}
158
159; This function can't be merged
160define void @b() {
161entry:
162	br label %BB.nomerge
163
164BB.nomerge:		; preds = %Common, %entry
165	br label %Succ
166
167Succ:		; preds = %Common, %BB.nomerge
168        ; This phi has confliction values for Common and (through BB) Common,
169        ; blocks can't be merged
170	%b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
171	%conde = call i1 @foo( )		; <i1> [#uses=1]
172	br i1 %conde, label %Common, label %Exit
173
174Common:		; preds = %Succ
175	%cond = call i1 @foo( )		; <i1> [#uses=1]
176	br i1 %cond, label %BB.nomerge, label %Succ
177
178Exit:		; preds = %Succ
179	ret void
180}
181
182; This function can be merged
183define void @c() {
184entry:
185	br label %BB.tomerge
186
187BB.tomerge:		; preds = %Common, %entry
188	br label %Succ
189
190Succ:		; preds = %Common, %BB.tomerge, %Pre-Exit
191        ; This phi has identical values for Common and (through BB) Common,
192        ; blocks can't be merged
193	%b = phi i32 [ 1, %BB.tomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
194	%conde = call i1 @foo( )		; <i1> [#uses=1]
195	br i1 %conde, label %Common, label %Pre-Exit
196
197Common:		; preds = %Succ
198	%cond = call i1 @foo( )		; <i1> [#uses=1]
199	br i1 %cond, label %BB.tomerge, label %Succ
200
201Pre-Exit:       ; preds = %Succ
202        ; This adds a backedge, so the %b phi node gets a third branch and is
203        ; not completely trivial
204	%cond2 = call i1 @foo( )		; <i1> [#uses=1]
205	br i1 %cond2, label %Succ, label %Exit
206
207Exit:		; preds = %Pre-Exit
208	ret void
209}
210
211; This function can be merged
212define void @d() {
213entry:
214	br label %BB.tomerge
215
216BB.tomerge:		; preds = %Common, %entry
217        ; This phi has a matching value (0) with below phi (0), so blocks
218        ; can be merged.
219	%a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
220	br label %Succ
221
222Succ:		; preds = %Common, %BB.tomerge
223	%b = phi i32 [ %a, %BB.tomerge ], [ 0, %Common ]		; <i32> [#uses=0]
224	%conde = call i1 @foo( )		; <i1> [#uses=1]
225	br i1 %conde, label %Common, label %Exit
226
227Common:		; preds = %Succ
228	%cond = call i1 @foo( )		; <i1> [#uses=1]
229	br i1 %cond, label %BB.tomerge, label %Succ
230
231Exit:		; preds = %Succ
232	ret void
233}
234
235; This function can be merged
236define void @e() {
237entry:
238	br label %BB.tomerge
239
240BB.tomerge:		; preds = %Use, %entry
241        ; This phi is used somewhere else than Succ, but this should not prevent
242        ; merging this block
243	%a = phi i32 [ 1, %entry ], [ 0, %Use ]		; <i32> [#uses=1]
244	br label %Succ
245
246Succ:		; preds = %BB.tomerge
247	%conde = call i1 @foo( )		; <i1> [#uses=1]
248	br i1 %conde, label %Use, label %Exit
249
250Use:		; preds = %Succ
251	%cond = call i1 @bar( i32 %a )		; <i1> [#uses=1]
252	br i1 %cond, label %BB.tomerge, label %Exit
253
254Exit:		; preds = %Use, %Succ
255	ret void
256}
257