1; RUN: llc < %s -march=x86-64 -mtriple=x86_64-unknown-linux-gnu -asm-verbose=false -post-RA-scheduler=true | FileCheck %s
2
3declare void @bar(i32)
4declare void @car(i32)
5declare void @dar(i32)
6declare void @ear(i32)
7declare void @far(i32)
8declare i1 @qux()
9
10@GHJK = global i32 0
11@HABC = global i32 0
12
13; BranchFolding should tail-merge the stores since they all precede
14; direct branches to the same place.
15
16; CHECK-LABEL: tail_merge_me:
17; CHECK-NOT:  GHJK
18; CHECK:      movl $0, GHJK(%rip)
19; CHECK-NEXT: movl $1, HABC(%rip)
20; CHECK-NOT:  GHJK
21
22define void @tail_merge_me() nounwind {
23entry:
24  %a = call i1 @qux()
25  br i1 %a, label %A, label %next
26next:
27  %b = call i1 @qux()
28  br i1 %b, label %B, label %C
29
30A:
31  call void @bar(i32 0)
32  store i32 0, i32* @GHJK
33  br label %M
34
35B:
36  call void @car(i32 1)
37  store i32 0, i32* @GHJK
38  br label %M
39
40C:
41  call void @dar(i32 2)
42  store i32 0, i32* @GHJK
43  br label %M
44
45M:
46  store i32 1, i32* @HABC
47  %c = call i1 @qux()
48  br i1 %c, label %return, label %altret
49
50return:
51  call void @ear(i32 1000)
52  ret void
53altret:
54  call void @far(i32 1001)
55  ret void
56}
57
58declare i8* @choose(i8*, i8*)
59
60; BranchFolding should tail-duplicate the indirect jump to avoid
61; redundant branching.
62
63; CHECK-LABEL: tail_duplicate_me:
64; CHECK:      movl $0, GHJK(%rip)
65; CHECK-NEXT: jmpq *%r
66; CHECK:      movl $0, GHJK(%rip)
67; CHECK-NEXT: jmpq *%r
68; CHECK:      movl $0, GHJK(%rip)
69; CHECK-NEXT: jmpq *%r
70
71define void @tail_duplicate_me() nounwind {
72entry:
73  %a = call i1 @qux()
74  %c = call i8* @choose(i8* blockaddress(@tail_duplicate_me, %return),
75                        i8* blockaddress(@tail_duplicate_me, %altret))
76  br i1 %a, label %A, label %next
77next:
78  %b = call i1 @qux()
79  br i1 %b, label %B, label %C
80
81A:
82  call void @bar(i32 0)
83  store i32 0, i32* @GHJK
84  br label %M
85
86B:
87  call void @car(i32 1)
88  store i32 0, i32* @GHJK
89  br label %M
90
91C:
92  call void @dar(i32 2)
93  store i32 0, i32* @GHJK
94  br label %M
95
96M:
97  indirectbr i8* %c, [label %return, label %altret]
98
99return:
100  call void @ear(i32 1000)
101  ret void
102altret:
103  call void @far(i32 1001)
104  ret void
105}
106
107; BranchFolding shouldn't try to merge the tails of two blocks
108; with only a branch in common, regardless of the fallthrough situation.
109
110; CHECK-LABEL: dont_merge_oddly:
111; CHECK-NOT:   ret
112; CHECK:        ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
113; CHECK-NEXT:   jbe .LBB2_3
114; CHECK-NEXT:   ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
115; CHECK-NEXT:   ja .LBB2_4
116; CHECK-NEXT:   jmp .LBB2_2
117; CHECK-NEXT: .LBB2_3:
118; CHECK-NEXT:   ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
119; CHECK-NEXT:   jbe .LBB2_2
120; CHECK-NEXT: .LBB2_4:
121; CHECK-NEXT:   xorl %eax, %eax
122; CHECK-NEXT:   ret
123; CHECK-NEXT: .LBB2_2:
124; CHECK-NEXT:   movb $1, %al
125; CHECK-NEXT:   ret
126
127define i1 @dont_merge_oddly(float* %result) nounwind {
128entry:
129  %tmp4 = getelementptr float* %result, i32 2
130  %tmp5 = load float* %tmp4, align 4
131  %tmp7 = getelementptr float* %result, i32 4
132  %tmp8 = load float* %tmp7, align 4
133  %tmp10 = getelementptr float* %result, i32 6
134  %tmp11 = load float* %tmp10, align 4
135  %tmp12 = fcmp olt float %tmp8, %tmp11
136  br i1 %tmp12, label %bb, label %bb21
137
138bb:
139  %tmp23469 = fcmp olt float %tmp5, %tmp8
140  br i1 %tmp23469, label %bb26, label %bb30
141
142bb21:
143  %tmp23 = fcmp olt float %tmp5, %tmp11
144  br i1 %tmp23, label %bb26, label %bb30
145
146bb26:
147  ret i1 0
148
149bb30:
150  ret i1 1
151}
152
153; Do any-size tail-merging when two candidate blocks will both require
154; an unconditional jump to complete a two-way conditional branch.
155
156; CHECK-LABEL: c_expand_expr_stmt:
157;
158; This test only works when register allocation happens to use %rax for both
159; load addresses.
160;
161; CHE:        jmp .LBB3_11
162; CHE-NEXT: .LBB3_9:
163; CHE-NEXT:   movq 8(%rax), %rax
164; CHE-NEXT:   xorl %edx, %edx
165; CHE-NEXT:   movb 16(%rax), %al
166; CHE-NEXT:   cmpb $16, %al
167; CHE-NEXT:   je .LBB3_11
168; CHE-NEXT:   cmpb $23, %al
169; CHE-NEXT:   jne .LBB3_14
170; CHE-NEXT: .LBB3_11:
171
172%0 = type { %struct.rtx_def* }
173%struct.lang_decl = type opaque
174%struct.rtx_def = type { i16, i8, i8, [1 x %union.rtunion] }
175%struct.tree_decl = type { [24 x i8], i8*, i32, %union.tree_node*, i32, i8, i8, i8, i8, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %union.tree_node*, %struct.rtx_def*, %union..2anon, %0, %union.tree_node*, %struct.lang_decl* }
176%union..2anon = type { i32 }
177%union.rtunion = type { i8* }
178%union.tree_node = type { %struct.tree_decl }
179
180define fastcc void @c_expand_expr_stmt(%union.tree_node* %expr) nounwind {
181entry:
182  %tmp4 = load i8* null, align 8                  ; <i8> [#uses=3]
183  switch i8 %tmp4, label %bb3 [
184    i8 18, label %bb
185  ]
186
187bb:                                               ; preds = %entry
188  switch i32 undef, label %bb1 [
189    i32 0, label %bb2.i
190    i32 37, label %bb.i
191  ]
192
193bb.i:                                             ; preds = %bb
194  switch i32 undef, label %bb1 [
195    i32 0, label %lvalue_p.exit
196  ]
197
198bb2.i:                                            ; preds = %bb
199  br label %bb3
200
201lvalue_p.exit:                                    ; preds = %bb.i
202  %tmp21 = load %union.tree_node** null, align 8  ; <%union.tree_node*> [#uses=3]
203  %tmp22 = getelementptr inbounds %union.tree_node* %tmp21, i64 0, i32 0, i32 0, i64 0 ; <i8*> [#uses=1]
204  %tmp23 = load i8* %tmp22, align 8               ; <i8> [#uses=1]
205  %tmp24 = zext i8 %tmp23 to i32                  ; <i32> [#uses=1]
206  switch i32 %tmp24, label %lvalue_p.exit4 [
207    i32 0, label %bb2.i3
208    i32 2, label %bb.i1
209  ]
210
211bb.i1:                                            ; preds = %lvalue_p.exit
212  %tmp25 = getelementptr inbounds %union.tree_node* %tmp21, i64 0, i32 0, i32 2 ; <i32*> [#uses=1]
213  %tmp26 = bitcast i32* %tmp25 to %union.tree_node** ; <%union.tree_node**> [#uses=1]
214  %tmp27 = load %union.tree_node** %tmp26, align 8 ; <%union.tree_node*> [#uses=2]
215  %tmp28 = getelementptr inbounds %union.tree_node* %tmp27, i64 0, i32 0, i32 0, i64 16 ; <i8*> [#uses=1]
216  %tmp29 = load i8* %tmp28, align 8               ; <i8> [#uses=1]
217  %tmp30 = zext i8 %tmp29 to i32                  ; <i32> [#uses=1]
218  switch i32 %tmp30, label %lvalue_p.exit4 [
219    i32 0, label %bb2.i.i2
220    i32 2, label %bb.i.i
221  ]
222
223bb.i.i:                                           ; preds = %bb.i1
224  %tmp34 = tail call fastcc i32 @lvalue_p(%union.tree_node* null) nounwind ; <i32> [#uses=1]
225  %phitmp = icmp ne i32 %tmp34, 0                 ; <i1> [#uses=1]
226  br label %lvalue_p.exit4
227
228bb2.i.i2:                                         ; preds = %bb.i1
229  %tmp35 = getelementptr inbounds %union.tree_node* %tmp27, i64 0, i32 0, i32 0, i64 8 ; <i8*> [#uses=1]
230  %tmp36 = bitcast i8* %tmp35 to %union.tree_node** ; <%union.tree_node**> [#uses=1]
231  %tmp37 = load %union.tree_node** %tmp36, align 8 ; <%union.tree_node*> [#uses=1]
232  %tmp38 = getelementptr inbounds %union.tree_node* %tmp37, i64 0, i32 0, i32 0, i64 16 ; <i8*> [#uses=1]
233  %tmp39 = load i8* %tmp38, align 8               ; <i8> [#uses=1]
234  switch i8 %tmp39, label %bb2 [
235    i8 16, label %lvalue_p.exit4
236    i8 23, label %lvalue_p.exit4
237  ]
238
239bb2.i3:                                           ; preds = %lvalue_p.exit
240  %tmp40 = getelementptr inbounds %union.tree_node* %tmp21, i64 0, i32 0, i32 0, i64 8 ; <i8*> [#uses=1]
241  %tmp41 = bitcast i8* %tmp40 to %union.tree_node** ; <%union.tree_node**> [#uses=1]
242  %tmp42 = load %union.tree_node** %tmp41, align 8 ; <%union.tree_node*> [#uses=1]
243  %tmp43 = getelementptr inbounds %union.tree_node* %tmp42, i64 0, i32 0, i32 0, i64 16 ; <i8*> [#uses=1]
244  %tmp44 = load i8* %tmp43, align 8               ; <i8> [#uses=1]
245  switch i8 %tmp44, label %bb2 [
246    i8 16, label %lvalue_p.exit4
247    i8 23, label %lvalue_p.exit4
248  ]
249
250lvalue_p.exit4:                                   ; preds = %bb2.i3, %bb2.i3, %bb2.i.i2, %bb2.i.i2, %bb.i.i, %bb.i1, %lvalue_p.exit
251  %tmp45 = phi i1 [ %phitmp, %bb.i.i ], [ false, %bb2.i.i2 ], [ false, %bb2.i.i2 ], [ false, %bb.i1 ], [ false, %bb2.i3 ], [ false, %bb2.i3 ], [ false, %lvalue_p.exit ] ; <i1> [#uses=1]
252  %tmp46 = icmp eq i8 %tmp4, 0                    ; <i1> [#uses=1]
253  %or.cond = or i1 %tmp45, %tmp46                 ; <i1> [#uses=1]
254  br i1 %or.cond, label %bb2, label %bb3
255
256bb1:                                              ; preds = %bb2.i.i, %bb.i, %bb
257  %.old = icmp eq i8 %tmp4, 23                    ; <i1> [#uses=1]
258  br i1 %.old, label %bb2, label %bb3
259
260bb2:                                              ; preds = %bb1, %lvalue_p.exit4, %bb2.i3, %bb2.i.i2
261  br label %bb3
262
263bb3:                                              ; preds = %bb2, %bb1, %lvalue_p.exit4, %bb2.i, %entry
264  %expr_addr.0 = phi %union.tree_node* [ null, %bb2 ], [ %expr, %bb2.i ], [ %expr, %entry ], [ %expr, %bb1 ], [ %expr, %lvalue_p.exit4 ] ; <%union.tree_node*> [#uses=0]
265  unreachable
266}
267
268declare fastcc i32 @lvalue_p(%union.tree_node* nocapture) nounwind readonly
269
270declare fastcc %union.tree_node* @default_conversion(%union.tree_node*) nounwind
271
272
273; If one tail merging candidate falls through into the other,
274; tail merging is likely profitable regardless of how few
275; instructions are involved. This function should have only
276; one ret instruction.
277
278; CHECK-LABEL: foo:
279; CHECK:        callq func
280; CHECK-NEXT: .LBB4_2:
281; CHECK-NEXT:   popq
282; CHECK-NEXT:   ret
283
284define void @foo(i1* %V) nounwind {
285entry:
286  %t0 = icmp eq i1* %V, null
287  br i1 %t0, label %return, label %bb
288
289bb:
290  call void @func()
291  ret void
292
293return:
294  ret void
295}
296
297declare void @func()
298
299; one - One instruction may be tail-duplicated even with optsize.
300
301; CHECK-LABEL: one:
302; CHECK: movl $0, XYZ(%rip)
303; CHECK: movl $0, XYZ(%rip)
304
305@XYZ = external global i32
306
307define void @one() nounwind optsize {
308entry:
309  %0 = icmp eq i32 undef, 0
310  br i1 %0, label %bbx, label %bby
311
312bby:
313  switch i32 undef, label %bb7 [
314    i32 16, label %return
315  ]
316
317bb7:
318  store volatile i32 0, i32* @XYZ
319  unreachable
320
321bbx:
322  switch i32 undef, label %bb12 [
323    i32 128, label %return
324  ]
325
326bb12:
327  store volatile i32 0, i32* @XYZ
328  unreachable
329
330return:
331  ret void
332}
333
334; two - Same as one, but with two instructions in the common
335; tail instead of one. This is too much to be merged, given
336; the optsize attribute.
337
338; CHECK-LABEL: two:
339; CHECK-NOT: XYZ
340; CHECK: ret
341; CHECK: movl $0, XYZ(%rip)
342; CHECK: movl $1, XYZ(%rip)
343; CHECK-NOT: XYZ
344
345define void @two() nounwind optsize {
346entry:
347  %0 = icmp eq i32 undef, 0
348  br i1 %0, label %bbx, label %bby
349
350bby:
351  switch i32 undef, label %bb7 [
352    i32 16, label %return
353  ]
354
355bb7:
356  store volatile i32 0, i32* @XYZ
357  store volatile i32 1, i32* @XYZ
358  unreachable
359
360bbx:
361  switch i32 undef, label %bb12 [
362    i32 128, label %return
363  ]
364
365bb12:
366  store volatile i32 0, i32* @XYZ
367  store volatile i32 1, i32* @XYZ
368  unreachable
369
370return:
371  ret void
372}
373
374; two_nosize - Same as two, but without the optsize attribute.
375; Now two instructions are enough to be tail-duplicated.
376
377; CHECK-LABEL: two_nosize:
378; CHECK: movl $0, XYZ(%rip)
379; CHECK: movl $1, XYZ(%rip)
380; CHECK: movl $0, XYZ(%rip)
381; CHECK: movl $1, XYZ(%rip)
382
383define void @two_nosize() nounwind {
384entry:
385  %0 = icmp eq i32 undef, 0
386  br i1 %0, label %bbx, label %bby
387
388bby:
389  switch i32 undef, label %bb7 [
390    i32 16, label %return
391  ]
392
393bb7:
394  store volatile i32 0, i32* @XYZ
395  store volatile i32 1, i32* @XYZ
396  unreachable
397
398bbx:
399  switch i32 undef, label %bb12 [
400    i32 128, label %return
401  ]
402
403bb12:
404  store volatile i32 0, i32* @XYZ
405  store volatile i32 1, i32* @XYZ
406  unreachable
407
408return:
409  ret void
410}
411
412; Tail-merging should merge the two ret instructions since one side
413; can fall-through into the ret and the other side has to branch anyway.
414
415; CHECK-LABEL: TESTE:
416; CHECK: ret
417; CHECK-NOT: ret
418; CHECK: size TESTE
419
420define i64 @TESTE(i64 %parami, i64 %paraml) nounwind readnone {
421entry:
422  %cmp = icmp slt i64 %parami, 1                  ; <i1> [#uses=1]
423  %varx.0 = select i1 %cmp, i64 1, i64 %parami    ; <i64> [#uses=1]
424  %cmp410 = icmp slt i64 %paraml, 1               ; <i1> [#uses=1]
425  br i1 %cmp410, label %for.end, label %bb.nph
426
427bb.nph:                                           ; preds = %entry
428  %tmp15 = mul i64 %paraml, %parami                   ; <i64> [#uses=1]
429  ret i64 %tmp15
430
431for.end:                                          ; preds = %entry
432  ret i64 %varx.0
433}
434