1;
2; Here all the branches we unswitch are exiting from the inner loop.
3; That means we should not be getting exponential behavior on inner-loop
4; unswitch. In fact there should be just a single version of inner-loop,
5; with possibly some outer loop copies.
6;
7; There should be just a single copy of each loop when strictest mutiplier
8; candidates formula (unscaled candidates == 0) is enforced:
9
10; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
11; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
12; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
13;
14; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
15; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
16; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
17;
18; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
19; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
20; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
21;
22; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
23; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
24; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
25;
26; When we relax the candidates part of a multiplier formula
27; When we relax the candidates part of a multiplier formula
28; (unscaled candidates == 2) we start getting some unswitches in outer loops,
29; which leads to siblings multiplier kicking in.
30;
31; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
32; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
33; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
34; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1
35;
36; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
37; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
38; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
39; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1
40;
41; NB: sort -b is essential here and below, otherwise blanks might lead to different
42; order depending on locale.
43;
44; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
45; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \
46; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
47; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
48;
49; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
50; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \
51; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
52; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
53;
54; With disabled cost-multiplier we get maximal possible amount of unswitches.
55;
56; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
57; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
58; RUN:	   sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
59;
60; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
61; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
62; RUN:	   sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
63;
64; Single loop nest, not unswitched
65; LOOP1:     Loop at depth 1 containing:
66; LOOP1-NOT:  Loop at depth 1 containing:
67; LOOP1:     Loop at depth 2 containing:
68; LOOP1-NOT:  Loop at depth 2 containing:
69; LOOP1:     Loop at depth 3 containing:
70; LOOP1-NOT:  Loop at depth 3 containing:
71;
72; Half unswitched loop nests, with unscaled3 and div1 it gets less depth1 loops unswitched
73; since they have more cost.
74; LOOP-UNSCALE3-DIV1-COUNT-4: Loop at depth 1 containing:
75; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 1 containing:
76; LOOP-UNSCALE3-DIV1-COUNT-1: Loop at depth 2 containing:
77; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 2 containing:
78; LOOP-UNSCALE3-DIV1-COUNT-1: Loop at depth 3 containing:
79; LOOP-UNSCALE3-DIV1-NOT:      Loop at depth 3 containing:
80;
81; Half unswitched loop nests, with unscaled3 and div2 it gets more depth1 loops unswitched
82; as div2 kicks in.
83; LOOP-UNSCALE3-DIV2-COUNT-6: Loop at depth 1 containing:
84; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 1 containing:
85; LOOP-UNSCALE3-DIV2-COUNT-1: Loop at depth 2 containing:
86; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 2 containing:
87; LOOP-UNSCALE3-DIV2-COUNT-1: Loop at depth 3 containing:
88; LOOP-UNSCALE3-DIV2-NOT:      Loop at depth 3 containing:
89;
90; Maximally unswitched (copy of the outer loop per each condition)
91; LOOP-MAX-COUNT-6: Loop at depth 1 containing:
92; LOOP-MAX-NOT:      Loop at depth 1 containing:
93; LOOP-MAX-COUNT-1: Loop at depth 2 containing:
94; LOOP-MAX-NOT:      Loop at depth 2 containing:
95; LOOP-MAX-COUNT-1: Loop at depth 3 containing:
96; LOOP-MAX-NOT:      Loop at depth 3 containing:
97
98declare void @bar()
99
100define void @loop_nested3_conds5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) {
101entry:
102  %addr1 = getelementptr i32, i32* %addr, i64 0
103  %addr2 = getelementptr i32, i32* %addr, i64 1
104  %addr3 = getelementptr i32, i32* %addr, i64 2
105  br label %outer
106outer:
107  %iv1 = phi i32 [0, %entry], [%iv1.next, %outer_latch]
108  %iv1.next = add i32 %iv1, 1
109  ;; skip nontrivial unswitch
110  call void @bar()
111  br label %middle
112middle:
113  %iv2 = phi i32 [0, %outer], [%iv2.next, %middle_latch]
114  %iv2.next = add i32 %iv2, 1
115  ;; skip nontrivial unswitch
116  call void @bar()
117  br label %loop
118loop:
119  %iv3 = phi i32 [0, %middle], [%iv3.next, %loop_latch]
120  %iv3.next = add i32 %iv3, 1
121  ;; skip nontrivial unswitch
122  call void @bar()
123  br i1 %c1, label %loop_next1_left, label %outer_latch
124loop_next1_left:
125  br label %loop_next1
126loop_next1_right:
127  br label %loop_next1
128
129loop_next1:
130  br i1 %c2, label %loop_next2_left, label %outer_latch
131loop_next2_left:
132  br label %loop_next2
133loop_next2_right:
134  br label %loop_next2
135
136loop_next2:
137  br i1 %c3, label %loop_next3_left, label %outer_latch
138loop_next3_left:
139  br label %loop_next3
140loop_next3_right:
141  br label %loop_next3
142
143loop_next3:
144  br i1 %c4, label %loop_next4_left, label %outer_latch
145loop_next4_left:
146  br label %loop_next4
147loop_next4_right:
148  br label %loop_next4
149
150loop_next4:
151  br i1 %c5, label %loop_latch_left, label %outer_latch
152loop_latch_left:
153  br label %loop_latch
154loop_latch_right:
155  br label %loop_latch
156
157loop_latch:
158  store volatile i32 0, i32* %addr1
159  %test_loop = icmp slt i32 %iv3, 50
160  br i1 %test_loop, label %loop, label %middle_latch
161middle_latch:
162  store volatile i32 0, i32* %addr2
163  %test_middle = icmp slt i32 %iv2, 50
164  br i1 %test_middle, label %middle, label %outer_latch
165outer_latch:
166  store volatile i32 0, i32* %addr3
167  %test_outer = icmp slt i32 %iv1, 50
168  br i1 %test_outer, label %outer, label %exit
169exit:
170  ret void
171}
172