llvm-project

1
; RUN: opt %loadNPMPolly -polly-process-unprofitable=false -polly-allow-nonaffine-loops '-passes=print<polly-detect>' -disable-output < %s 2>&1 | FileCheck %s
2
;
3
; Even if we allow non-affine loops we can only model the outermost loop, all
4
; other loops are boxed in non-affine regions. However, the inner loops can be
5
; distributed as black-boxes, thus we will recognize the outer loop as profitable.
6
;
7
; CHECK:  Valid Region for Scop: for.cond => for.end.51
8
;
9
;    void f(int *A) {
10
;      for (int i = 0; i < 100; i++) {
11
;        // Non-affine
12
;        for (int j = 0; j < i * i; j++)
13
;          for (int k = 0; k < i; k++)
14
;            A[i]++;
15
;        // Non-affine
16
;        for (int j = 0; j < i * i; j++)
17
;          // Non-affine
18
;          for (int k = 0; k < j; k++)
19
;            A[i]++;
20
;        // Non-affine
21
;        if (A[i])
22
;          for (int j = 0; j < 100; j++)
23
;            for (int k = 0; k < j * j; k++)
24
;              A[i]++;
25
;      }
26
;    }
27
;
28
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
29

30
define void @f(ptr %A) {
31
entry:
32
  br label %for.cond
33

34
for.cond:                                         ; preds = %for.inc.49, %entry
35
  %indvars.iv5 = phi i64 [ %indvars.iv.next6, %for.inc.49 ], [ 0, %entry ]
36
  %indvars.iv = phi i32 [ %indvars.iv.next, %for.inc.49 ], [ 0, %entry ]
37
  %exitcond9 = icmp ne i64 %indvars.iv5, 100
38
  br i1 %exitcond9, label %for.body, label %for.end.51
39

40
for.body:                                         ; preds = %for.cond
41
  br label %for.cond.1
42

43
for.cond.1:                                       ; preds = %for.inc.8, %for.body
44
  %j.0 = phi i32 [ 0, %for.body ], [ %inc9, %for.inc.8 ]
45
  %tmp = mul nsw i64 %indvars.iv5, %indvars.iv5
46
  %tmp10 = sext i32 %j.0 to i64
47
  %cmp2 = icmp slt i64 %tmp10, %tmp
48
  br i1 %cmp2, label %for.body.3, label %for.end.10
49

50
for.body.3:                                       ; preds = %for.cond.1
51
  br label %for.cond.4
52

53
for.cond.4:                                       ; preds = %for.inc, %for.body.3
54
  %k.0 = phi i32 [ 0, %for.body.3 ], [ %inc7, %for.inc ]
55
  %exitcond = icmp ne i32 %k.0, %indvars.iv
56
  br i1 %exitcond, label %for.body.6, label %for.end
57

58
for.body.6:                                       ; preds = %for.cond.4
59
  %arrayidx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5
60
  %tmp11 = load i32, ptr %arrayidx, align 4
61
  %inc = add nsw i32 %tmp11, 1
62
  store i32 %inc, ptr %arrayidx, align 4
63
  br label %for.inc
64

65
for.inc:                                          ; preds = %for.body.6
66
  %inc7 = add nuw nsw i32 %k.0, 1
67
  br label %for.cond.4
68

69
for.end:                                          ; preds = %for.cond.4
70
  br label %for.inc.8
71

72
for.inc.8:                                        ; preds = %for.end
73
  %inc9 = add nuw nsw i32 %j.0, 1
74
  br label %for.cond.1
75

76
for.end.10:                                       ; preds = %for.cond.1
77
  br label %for.cond.12
78

79
for.cond.12:                                      ; preds = %for.inc.26, %for.end.10
80
  %indvars.iv1 = phi i32 [ %indvars.iv.next2, %for.inc.26 ], [ 0, %for.end.10 ]
81
  %tmp12 = mul nsw i64 %indvars.iv5, %indvars.iv5
82
  %tmp13 = sext i32 %indvars.iv1 to i64
83
  %cmp14 = icmp slt i64 %tmp13, %tmp12
84
  br i1 %cmp14, label %for.body.15, label %for.end.28
85

86
for.body.15:                                      ; preds = %for.cond.12
87
  br label %for.cond.17
88

89
for.cond.17:                                      ; preds = %for.inc.23, %for.body.15
90
  %k16.0 = phi i32 [ 0, %for.body.15 ], [ %inc24, %for.inc.23 ]
91
  %exitcond3 = icmp ne i32 %k16.0, %indvars.iv1
92
  br i1 %exitcond3, label %for.body.19, label %for.end.25
93

94
for.body.19:                                      ; preds = %for.cond.17
95
  %arrayidx21 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5
96
  %tmp14 = load i32, ptr %arrayidx21, align 4
97
  %inc22 = add nsw i32 %tmp14, 1
98
  store i32 %inc22, ptr %arrayidx21, align 4
99
  br label %for.inc.23
100

101
for.inc.23:                                       ; preds = %for.body.19
102
  %inc24 = add nuw nsw i32 %k16.0, 1
103
  br label %for.cond.17
104

105
for.end.25:                                       ; preds = %for.cond.17
106
  br label %for.inc.26
107

108
for.inc.26:                                       ; preds = %for.end.25
109
  %indvars.iv.next2 = add nuw nsw i32 %indvars.iv1, 1
110
  br label %for.cond.12
111

112
for.end.28:                                       ; preds = %for.cond.12
113
  %arrayidx30 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5
114
  %tmp15 = load i32, ptr %arrayidx30, align 4
115
  %tobool = icmp eq i32 %tmp15, 0
116
  br i1 %tobool, label %if.end, label %if.then
117

118
if.then:                                          ; preds = %for.end.28
119
  br label %for.cond.32
120

121
for.cond.32:                                      ; preds = %for.inc.46, %if.then
122
  %j31.0 = phi i32 [ 0, %if.then ], [ %inc47, %for.inc.46 ]
123
  %exitcond4 = icmp ne i32 %j31.0, 100
124
  br i1 %exitcond4, label %for.body.34, label %for.end.48
125

126
for.body.34:                                      ; preds = %for.cond.32
127
  br label %for.cond.36
128

129
for.cond.36:                                      ; preds = %for.inc.43, %for.body.34
130
  %k35.0 = phi i32 [ 0, %for.body.34 ], [ %inc44, %for.inc.43 ]
131
  %mul37 = mul nsw i32 %j31.0, %j31.0
132
  %cmp38 = icmp slt i32 %k35.0, %mul37
133
  br i1 %cmp38, label %for.body.39, label %for.end.45
134

135
for.body.39:                                      ; preds = %for.cond.36
136
  %arrayidx41 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv5
137
  %tmp16 = load i32, ptr %arrayidx41, align 4
138
  %inc42 = add nsw i32 %tmp16, 1
139
  store i32 %inc42, ptr %arrayidx41, align 4
140
  br label %for.inc.43
141

142
for.inc.43:                                       ; preds = %for.body.39
143
  %inc44 = add nuw nsw i32 %k35.0, 1
144
  br label %for.cond.36
145

146
for.end.45:                                       ; preds = %for.cond.36
147
  br label %for.inc.46
148

149
for.inc.46:                                       ; preds = %for.end.45
150
  %inc47 = add nuw nsw i32 %j31.0, 1
151
  br label %for.cond.32
152

153
for.end.48:                                       ; preds = %for.cond.32
154
  br label %if.end
155

156
if.end:                                           ; preds = %for.end.28, %for.end.48
157
  br label %for.inc.49
158

159
for.inc.49:                                       ; preds = %if.end
160
  %indvars.iv.next6 = add nuw nsw i64 %indvars.iv5, 1
161
  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 1
162
  br label %for.cond
163

164
for.end.51:                                       ; preds = %for.cond
165
  ret void
166
}
167