1; RUN: opt %loadPolly -polly-detect -polly-process-unprofitable=false -analyze \
2; RUN:     -polly-allow-nonaffine-loops < %s | FileCheck %s
3;
4; Even if we allow non-affine loops we can only model the outermost loop, all
5; other loops are boxed in non-affine regions. However, the inner loops can be
6; distributed as black-boxes, thus we will recognize the outer loop as profitable.
7;
8; CHECK:  Valid Region for Scop: for.cond => for.end.51
9;
10;    void f(int *A) {
11;      for (int i = 0; i < 100; i++) {
12;        // Non-affine
13;        for (int j = 0; j < i * i; j++)
14;          for (int k = 0; k < i; k++)
15;            A[i]++;
16;        // Non-affine
17;        for (int j = 0; j < i * i; j++)
18;          // Non-affine
19;          for (int k = 0; k < j; k++)
20;            A[i]++;
21;        // Non-affine
22;        if (A[i])
23;          for (int j = 0; j < 100; j++)
24;            for (int k = 0; k < j * j; k++)
25;              A[i]++;
26;      }
27;    }
28;
29target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
30
31define void @f(i32* %A) {
32entry:
33  br label %for.cond
34
35for.cond:                                         ; preds = %for.inc.49, %entry
36  %indvars.iv5 = phi i64 [ %indvars.iv.next6, %for.inc.49 ], [ 0, %entry ]
37  %indvars.iv = phi i32 [ %indvars.iv.next, %for.inc.49 ], [ 0, %entry ]
38  %exitcond9 = icmp ne i64 %indvars.iv5, 100
39  br i1 %exitcond9, label %for.body, label %for.end.51
40
41for.body:                                         ; preds = %for.cond
42  br label %for.cond.1
43
44for.cond.1:                                       ; preds = %for.inc.8, %for.body
45  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc.8 ]
46  %tmp = mul nsw i64 %indvars.iv5, %indvars.iv5
47  %tmp10 = sext i32 %j.0 to i64
48  %cmp2 = icmp slt i64 %tmp10, %tmp
49  br i1 %cmp2, label %for.body.3, label %for.end.10
50
51for.body.3:                                       ; preds = %for.cond.1
52  br label %for.cond.4
53
54for.cond.4:                                       ; preds = %for.inc, %for.body.3
55  %k.0 = phi i32 [ 0, %for.body.3 ], [ %inc7, %for.inc ]
56  %exitcond = icmp ne i32 %k.0, %indvars.iv
57  br i1 %exitcond, label %for.body.6, label %for.end
58
59for.body.6:                                       ; preds = %for.cond.4
60  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv5
61  %tmp11 = load i32, i32* %arrayidx, align 4
62  %inc = add nsw i32 %tmp11, 1
63  store i32 %inc, i32* %arrayidx, align 4
64  br label %for.inc
65
66for.inc:                                          ; preds = %for.body.6
67  %inc7 = add nuw nsw i32 %k.0, 1
68  br label %for.cond.4
69
70for.end:                                          ; preds = %for.cond.4
71  br label %for.inc.8
72
73for.inc.8:                                        ; preds = %for.end
74  %inc9 = add nuw nsw i32 %j.0, 1
75  br label %for.cond.1
76
77for.end.10:                                       ; preds = %for.cond.1
78  br label %for.cond.12
79
80for.cond.12:                                      ; preds = %for.inc.26, %for.end.10
81  %indvars.iv1 = phi i32 [ %indvars.iv.next2, %for.inc.26 ], [ 0, %for.end.10 ]
82  %tmp12 = mul nsw i64 %indvars.iv5, %indvars.iv5
83  %tmp13 = sext i32 %indvars.iv1 to i64
84  %cmp14 = icmp slt i64 %tmp13, %tmp12
85  br i1 %cmp14, label %for.body.15, label %for.end.28
86
87for.body.15:                                      ; preds = %for.cond.12
88  br label %for.cond.17
89
90for.cond.17:                                      ; preds = %for.inc.23, %for.body.15
91  %k16.0 = phi i32 [ 0, %for.body.15 ], [ %inc24, %for.inc.23 ]
92  %exitcond3 = icmp ne i32 %k16.0, %indvars.iv1
93  br i1 %exitcond3, label %for.body.19, label %for.end.25
94
95for.body.19:                                      ; preds = %for.cond.17
96  %arrayidx21 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv5
97  %tmp14 = load i32, i32* %arrayidx21, align 4
98  %inc22 = add nsw i32 %tmp14, 1
99  store i32 %inc22, i32* %arrayidx21, align 4
100  br label %for.inc.23
101
102for.inc.23:                                       ; preds = %for.body.19
103  %inc24 = add nuw nsw i32 %k16.0, 1
104  br label %for.cond.17
105
106for.end.25:                                       ; preds = %for.cond.17
107  br label %for.inc.26
108
109for.inc.26:                                       ; preds = %for.end.25
110  %indvars.iv.next2 = add nuw nsw i32 %indvars.iv1, 1
111  br label %for.cond.12
112
113for.end.28:                                       ; preds = %for.cond.12
114  %arrayidx30 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv5
115  %tmp15 = load i32, i32* %arrayidx30, align 4
116  %tobool = icmp eq i32 %tmp15, 0
117  br i1 %tobool, label %if.end, label %if.then
118
119if.then:                                          ; preds = %for.end.28
120  br label %for.cond.32
121
122for.cond.32:                                      ; preds = %for.inc.46, %if.then
123  %j31.0 = phi i32 [ 0, %if.then ], [ %inc47, %for.inc.46 ]
124  %exitcond4 = icmp ne i32 %j31.0, 100
125  br i1 %exitcond4, label %for.body.34, label %for.end.48
126
127for.body.34:                                      ; preds = %for.cond.32
128  br label %for.cond.36
129
130for.cond.36:                                      ; preds = %for.inc.43, %for.body.34
131  %k35.0 = phi i32 [ 0, %for.body.34 ], [ %inc44, %for.inc.43 ]
132  %mul37 = mul nsw i32 %j31.0, %j31.0
133  %cmp38 = icmp slt i32 %k35.0, %mul37
134  br i1 %cmp38, label %for.body.39, label %for.end.45
135
136for.body.39:                                      ; preds = %for.cond.36
137  %arrayidx41 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv5
138  %tmp16 = load i32, i32* %arrayidx41, align 4
139  %inc42 = add nsw i32 %tmp16, 1
140  store i32 %inc42, i32* %arrayidx41, align 4
141  br label %for.inc.43
142
143for.inc.43:                                       ; preds = %for.body.39
144  %inc44 = add nuw nsw i32 %k35.0, 1
145  br label %for.cond.36
146
147for.end.45:                                       ; preds = %for.cond.36
148  br label %for.inc.46
149
150for.inc.46:                                       ; preds = %for.end.45
151  %inc47 = add nuw nsw i32 %j31.0, 1
152  br label %for.cond.32
153
154for.end.48:                                       ; preds = %for.cond.32
155  br label %if.end
156
157if.end:                                           ; preds = %for.end.28, %for.end.48
158  br label %for.inc.49
159
160for.inc.49:                                       ; preds = %if.end
161  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
162  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
163  br label %for.cond
164
165for.end.51:                                       ; preds = %for.cond
166  ret void
167}
168