llvm-project

1
; XFAIL: *
2
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
3
; RUN: opt -mtriple=amdgcn-amd-amdhsa -S -structurizecfg %s | FileCheck %s
4

5
; StructurizeCFG::orderNodes used an arbitrary and nonsensical sorting
6
; function which broke the basic backedge identification algorithm. It
7
; would use RPO order, but then do a weird partial sort by the loop
8
; depth assuming blocks are sorted by loop. However a block can appear
9
; in between blocks of a loop that is not part of a loop, breaking the
10
; assumption of the sort.
11
;
12
; The collectInfos must be done in RPO order. The actual
13
; structurization order I think is less important, but unless the loop
14
; headers are identified in RPO order, it finds the wrong set of back
15
; edges.
16

17
define amdgpu_kernel void @loop_backedge_misidentified(ptr addrspace(1) %arg0) #0 {
18
; CHECK-LABEL: @loop_backedge_misidentified(
19
; CHECK-NEXT:  entry:
20
; CHECK-NEXT:    [[TMP:%.*]] = load volatile <2 x i32>, ptr addrspace(1) undef, align 16
21
; CHECK-NEXT:    [[LOAD1:%.*]] = load volatile <2 x float>, ptr addrspace(1) undef
22
; CHECK-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
23
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr addrspace(1) [[ARG0:%.*]], i32 [[TID]]
24
; CHECK-NEXT:    [[I_INITIAL:%.*]] = load volatile i32, ptr addrspace(1) [[GEP]], align 4
25
; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
26
; CHECK:       LOOP.HEADER:
27
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_INITIAL]], [[ENTRY:%.*]] ], [ [[TMP10:%.*]], [[FLOW4:%.*]] ]
28
; CHECK-NEXT:    call void asm sideeffect "s_nop 0x100b
29
; CHECK-NEXT:    [[TMP12:%.*]] = zext i32 [[I]] to i64
30
; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds <4 x i32>, ptr addrspace(1) null, i64 [[TMP12]]
31
; CHECK-NEXT:    [[TMP14:%.*]] = load <4 x i32>, ptr addrspace(1) [[TMP13]], align 16
32
; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x i32> [[TMP14]], i64 0
33
; CHECK-NEXT:    [[TMP16:%.*]] = and i32 [[TMP15]], 65535
34
; CHECK-NEXT:    [[TMP17:%.*]] = icmp eq i32 [[TMP16]], 1
35
; CHECK-NEXT:    [[TMP0:%.*]] = xor i1 [[TMP17]], true
36
; CHECK-NEXT:    br i1 [[TMP0]], label [[BB62:%.*]], label [[FLOW:%.*]]
37
; CHECK:       Flow2:
38
; CHECK-NEXT:    br label [[FLOW]]
39
; CHECK:       bb18:
40
; CHECK-NEXT:    [[TMP19:%.*]] = extractelement <2 x i32> [[TMP]], i64 0
41
; CHECK-NEXT:    [[TMP22:%.*]] = lshr i32 [[TMP19]], 16
42
; CHECK-NEXT:    [[TMP24:%.*]] = urem i32 [[TMP22]], 52
43
; CHECK-NEXT:    [[TMP25:%.*]] = mul nuw nsw i32 [[TMP24]], 52
44
; CHECK-NEXT:    br label [[INNER_LOOP:%.*]]
45
; CHECK:       Flow3:
46
; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP59:%.*]], [[INNER_LOOP_BREAK:%.*]] ], [ [[TMP7:%.*]], [[FLOW]] ]
47
; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ true, [[INNER_LOOP_BREAK]] ], [ [[TMP8:%.*]], [[FLOW]] ]
48
; CHECK-NEXT:    br i1 [[TMP2]], label [[END_ELSE_BLOCK:%.*]], label [[FLOW4]]
49
; CHECK:       INNER_LOOP:
50
; CHECK-NEXT:    [[INNER_LOOP_J:%.*]] = phi i32 [ [[INNER_LOOP_J_INC:%.*]], [[INNER_LOOP]] ], [ [[TMP25]], [[BB18:%.*]] ]
51
; CHECK-NEXT:    call void asm sideeffect "
52
; CHECK-NEXT:    [[INNER_LOOP_J_INC]] = add nsw i32 [[INNER_LOOP_J]], 1
53
; CHECK-NEXT:    [[INNER_LOOP_CMP:%.*]] = icmp eq i32 [[INNER_LOOP_J]], 0
54
; CHECK-NEXT:    br i1 [[INNER_LOOP_CMP]], label [[INNER_LOOP_BREAK]], label [[INNER_LOOP]]
55
; CHECK:       INNER_LOOP_BREAK:
56
; CHECK-NEXT:    [[TMP59]] = extractelement <4 x i32> [[TMP14]], i64 2
57
; CHECK-NEXT:    call void asm sideeffect "s_nop 23 ", "~{memory}"() #0
58
; CHECK-NEXT:    br label [[FLOW3:%.*]]
59
; CHECK:       bb62:
60
; CHECK-NEXT:    [[LOAD13:%.*]] = icmp ult i32 [[TMP16]], 271
61
; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[LOAD13]], true
62
; CHECK-NEXT:    br i1 [[TMP3]], label [[INCREMENT_I:%.*]], label [[FLOW1:%.*]]
63
; CHECK:       Flow1:
64
; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[INC_I:%.*]], [[INCREMENT_I]] ], [ undef, [[BB62]] ]
65
; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ true, [[INCREMENT_I]] ], [ false, [[BB62]] ]
66
; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ false, [[INCREMENT_I]] ], [ true, [[BB62]] ]
67
; CHECK-NEXT:    br i1 [[TMP6]], label [[BB64:%.*]], label [[FLOW2:%.*]]
68
; CHECK:       bb64:
69
; CHECK-NEXT:    call void asm sideeffect "s_nop 42", "~{memory}"() #0
70
; CHECK-NEXT:    br label [[FLOW2]]
71
; CHECK:       Flow:
72
; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[TMP4]], [[FLOW2]] ], [ undef, [[LOOP_HEADER]] ]
73
; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP5]], [[FLOW2]] ], [ false, [[LOOP_HEADER]] ]
74
; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[LOOP_HEADER]] ]
75
; CHECK-NEXT:    br i1 [[TMP9]], label [[BB18]], label [[FLOW3]]
76
; CHECK:       INCREMENT_I:
77
; CHECK-NEXT:    [[INC_I]] = add i32 [[I]], 1
78
; CHECK-NEXT:    call void asm sideeffect "s_nop 0x1336
79
; CHECK-NEXT:    br label [[FLOW1]]
80
; CHECK:       END_ELSE_BLOCK:
81
; CHECK-NEXT:    [[I_FINAL:%.*]] = phi i32 [ [[TMP1]], [[FLOW3]] ]
82
; CHECK-NEXT:    call void asm sideeffect "s_nop 0x1337
83
; CHECK-NEXT:    [[CMP_END_ELSE_BLOCK:%.*]] = icmp eq i32 [[I_FINAL]], -1
84
; CHECK-NEXT:    br label [[FLOW4]]
85
; CHECK:       Flow4:
86
; CHECK-NEXT:    [[TMP10]] = phi i32 [ [[I_FINAL]], [[END_ELSE_BLOCK]] ], [ undef, [[FLOW3]] ]
87
; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ [[CMP_END_ELSE_BLOCK]], [[END_ELSE_BLOCK]] ], [ true, [[FLOW3]] ]
88
; CHECK-NEXT:    br i1 [[TMP11]], label [[RETURN:%.*]], label [[LOOP_HEADER]]
89
; CHECK:       RETURN:
90
; CHECK-NEXT:    call void asm sideeffect "s_nop 0x99
91
; CHECK-NEXT:    store volatile <2 x float> [[LOAD1]], ptr addrspace(1) undef, align 8
92
; CHECK-NEXT:    ret void
93
;
94
entry:
95
  %tmp = load volatile <2 x i32>, ptr addrspace(1) undef, align 16
96
  %load1 = load volatile <2 x float>, ptr addrspace(1) undef
97
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
98
  %gep = getelementptr inbounds i32, ptr addrspace(1) %arg0, i32 %tid
99
  %i.initial = load volatile i32, ptr addrspace(1) %gep, align 4
100
  br label %LOOP.HEADER
101

102
LOOP.HEADER:
103
  %i = phi i32 [ %i.final, %END_ELSE_BLOCK ], [ %i.initial, %entry ]
104
  call void asm sideeffect "s_nop 0x100b ; loop $0 ", "r,~{memory}"(i32 %i) #0
105
  %tmp12 = zext i32 %i to i64
106
  %tmp13 = getelementptr inbounds <4 x i32>, ptr addrspace(1) null, i64 %tmp12
107
  %tmp14 = load <4 x i32>, ptr addrspace(1) %tmp13, align 16
108
  %tmp15 = extractelement <4 x i32> %tmp14, i64 0
109
  %tmp16 = and i32 %tmp15, 65535
110
  %tmp17 = icmp eq i32 %tmp16, 1
111
  br i1 %tmp17, label %bb18, label %bb62
112

113
bb18:
114
  %tmp19 = extractelement <2 x i32> %tmp, i64 0
115
  %tmp22 = lshr i32 %tmp19, 16
116
  %tmp24 = urem i32 %tmp22, 52
117
  %tmp25 = mul nuw nsw i32 %tmp24, 52
118
  br label %INNER_LOOP
119

120
INNER_LOOP:
121
  %inner.loop.j = phi i32 [ %tmp25, %bb18 ], [ %inner.loop.j.inc, %INNER_LOOP ]
122
  call void asm sideeffect "; inner loop body", ""() #0
123
  %inner.loop.j.inc = add nsw i32 %inner.loop.j, 1
124
  %inner.loop.cmp = icmp eq i32 %inner.loop.j, 0
125
  br i1 %inner.loop.cmp, label %INNER_LOOP_BREAK, label %INNER_LOOP
126

127
INNER_LOOP_BREAK:
128
  %tmp59 = extractelement <4 x i32> %tmp14, i64 2
129
  call void asm sideeffect "s_nop 23 ", "~{memory}"() #0
130
  br label %END_ELSE_BLOCK
131

132
bb62:
133
  %load13 = icmp ult i32 %tmp16, 271
134
  br i1 %load13, label %bb64, label %INCREMENT_I
135

136
bb64:
137
  call void asm sideeffect "s_nop 42", "~{memory}"() #0
138
  br label %RETURN
139

140
INCREMENT_I:
141
  %inc.i = add i32 %i, 1
142
  call void asm sideeffect "s_nop 0x1336 ; increment $0", "v,~{memory}"(i32 %inc.i) #0
143
  br label %END_ELSE_BLOCK
144

145
END_ELSE_BLOCK:
146
  %i.final = phi i32 [ %tmp59, %INNER_LOOP_BREAK ], [ %inc.i, %INCREMENT_I ]
147
  call void asm sideeffect "s_nop 0x1337 ; end else block $0", "v,~{memory}"(i32 %i.final) #0
148
  %cmp.end.else.block = icmp eq i32 %i.final, -1
149
  br i1 %cmp.end.else.block, label %RETURN, label %LOOP.HEADER
150

151
RETURN:
152
  call void asm sideeffect "s_nop 0x99 ; ClosureEval return", "~{memory}"() #0
153
  store volatile <2 x float> %load1, ptr addrspace(1) undef, align 8
154
  ret void
155
}
156

157
; The same function, except break to return block goes directly to the
158
; return, which managed to hide the bug.
159
define amdgpu_kernel void @loop_backedge_misidentified_alt(ptr addrspace(1) %arg0) #0 {
160
entry:
161
  %tmp = load volatile <2 x i32>, ptr addrspace(1) undef, align 16
162
  %load1 = load volatile <2 x float>, ptr addrspace(1) undef
163
  %tid = call i32 @llvm.amdgcn.workitem.id.x()
164
  %gep = getelementptr inbounds i32, ptr addrspace(1) %arg0, i32 %tid
165
  %i.initial = load volatile i32, ptr addrspace(1) %gep, align 4
166
  br label %LOOP.HEADER
167

168
LOOP.HEADER:
169
  %i = phi i32 [ %i.final, %END_ELSE_BLOCK ], [ %i.initial, %entry ]
170
  call void asm sideeffect "s_nop 0x100b ; loop $0 ", "r,~{memory}"(i32 %i) #0
171
  %tmp12 = zext i32 %i to i64
172
  %tmp13 = getelementptr inbounds <4 x i32>, ptr addrspace(1) null, i64 %tmp12
173
  %tmp14 = load <4 x i32>, ptr addrspace(1) %tmp13, align 16
174
  %tmp15 = extractelement <4 x i32> %tmp14, i64 0
175
  %tmp16 = and i32 %tmp15, 65535
176
  %tmp17 = icmp eq i32 %tmp16, 1
177
  br i1 %tmp17, label %bb18, label %bb62
178

179
bb18:
180
  %tmp19 = extractelement <2 x i32> %tmp, i64 0
181
  %tmp22 = lshr i32 %tmp19, 16
182
  %tmp24 = urem i32 %tmp22, 52
183
  %tmp25 = mul nuw nsw i32 %tmp24, 52
184
  br label %INNER_LOOP
185

186
INNER_LOOP:
187
  %inner.loop.j = phi i32 [ %tmp25, %bb18 ], [ %inner.loop.j.inc, %INNER_LOOP ]
188
  call void asm sideeffect "; inner loop body", ""() #0
189
  %inner.loop.j.inc = add nsw i32 %inner.loop.j, 1
190
  %inner.loop.cmp = icmp eq i32 %inner.loop.j, 0
191
  br i1 %inner.loop.cmp, label %INNER_LOOP_BREAK, label %INNER_LOOP
192

193
INNER_LOOP_BREAK:
194
  %tmp59 = extractelement <4 x i32> %tmp14, i64 2
195
  call void asm sideeffect "s_nop 23 ", "~{memory}"() #0
196
  br label %END_ELSE_BLOCK
197

198
bb62:
199
  %load13 = icmp ult i32 %tmp16, 271
200
  ;br i1 %load13, label %bb64, label %INCREMENT_I
201
  ; branching directly to the return avoids the bug
202
  br i1 %load13, label %RETURN, label %INCREMENT_I
203

204

205
bb64:
206
  call void asm sideeffect "s_nop 42", "~{memory}"() #0
207
  br label %RETURN
208

209
INCREMENT_I:
210
  %inc.i = add i32 %i, 1
211
  call void asm sideeffect "s_nop 0x1336 ; increment $0", "v,~{memory}"(i32 %inc.i) #0
212
  br label %END_ELSE_BLOCK
213

214
END_ELSE_BLOCK:
215
  %i.final = phi i32 [ %tmp59, %INNER_LOOP_BREAK ], [ %inc.i, %INCREMENT_I ]
216
  call void asm sideeffect "s_nop 0x1337 ; end else block $0", "v,~{memory}"(i32 %i.final) #0
217
  %cmp.end.else.block = icmp eq i32 %i.final, -1
218
  br i1 %cmp.end.else.block, label %RETURN, label %LOOP.HEADER
219

220
RETURN:
221
  call void asm sideeffect "s_nop 0x99 ; ClosureEval return", "~{memory}"() #0
222
  store volatile <2 x float> %load1, ptr addrspace(1) undef, align 8
223
  ret void
224
}
225

226
declare i32 @llvm.amdgcn.workitem.id.x() #1
227

228
attributes #0 = { convergent nounwind }
229
attributes #1 = { convergent nounwind readnone }
230