llvm/test/Transforms/StructurizeCFG/AMDGPU/loop-subregion-misordered.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -mtriple=amdgcn-amd-amdhsa -S -structurizecfg %s | FileCheck %s
   3 ;
   4 ; StructurizeCFG::orderNodes basically uses a reverse post-order (RPO) traversal of the region
   5 ; list to get the order. The only problem with it is that sometimes backedges
   6 ; for outer loops will be visited before backedges for inner loops. To solve this problem,
   7 ; a loop depth based approach has been used to make sure all blocks in this loop has been visited
   8 ; before moving on to outer loop.
   9 ;
  10 ; However, we found a problem for a SubRegion which is a loop itself:
  11 ;                   _
  12 ;                  | |
  13 ;                  V |
  14 ;      --> BB1 --> BB2 --> BB3 -->
  15 ;
  16 ; In this case, BB2 is a SubRegion (loop), and thus its loopdepth is different than that of
  17 ; BB1 and BB3. This fact will lead BB2 to be placed in the wrong order.
  18 ;
  19 ; In this work, we treat the SubRegion as a special case and use its exit block to determine
  20 ; the loop and its depth to guard the sorting.
  21 define amdgpu_kernel void @loop_subregion_misordered(ptr addrspace(1) %arg0) #0 {
  22 ; CHECK-LABEL: @loop_subregion_misordered(
  23 ; CHECK-NEXT:  entry:
  24 ; CHECK-NEXT:    [[TMP:%.*]] = load volatile <2 x i32>, ptr addrspace(1) undef, align 16
  25 ; CHECK-NEXT:    [[LOAD1:%.*]] = load volatile <2 x float>, ptr addrspace(1) undef, align 8
  26 ; CHECK-NEXT:    [[TID:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
  27 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr addrspace(1) [[ARG0:%.*]], i32 [[TID]]
  28 ; CHECK-NEXT:    [[I_INITIAL:%.*]] = load volatile i32, ptr addrspace(1) [[GEP]], align 4
  29 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
  30 ; CHECK:       LOOP.HEADER:
  31 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_INITIAL]], [[ENTRY:%.*]] ], [ [[TMP5:%.*]], [[FLOW3:%.*]] ]
  32 ; CHECK-NEXT:    call void asm sideeffect "s_nop 0x100b
  33 ; CHECK-NEXT:    [[TMP12:%.*]] = zext i32 [[I]] to i64
  34 ; CHECK-NEXT:    [[TMP13:%.*]] = getelementptr inbounds <4 x i32>, ptr addrspace(1) null, i64 [[TMP12]]
  35 ; CHECK-NEXT:    [[TMP14:%.*]] = load <4 x i32>, ptr addrspace(1) [[TMP13]], align 16
  36 ; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <4 x i32> [[TMP14]], i64 0
  37 ; CHECK-NEXT:    [[TMP16:%.*]] = and i32 [[TMP15]], 65535
  38 ; CHECK-NEXT:    [[TMP17:%.*]] = icmp ne i32 [[TMP16]], 1
  39 ; CHECK-NEXT:    br i1 [[TMP17]], label [[BB62:%.*]], label [[FLOW:%.*]]
  40 ; CHECK:       Flow1:
  41 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[INC_I:%.*]], [[INCREMENT_I:%.*]] ], [ undef, [[BB62]] ]
  42 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, [[INCREMENT_I]] ], [ true, [[BB62]] ]
  43 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ true, [[INCREMENT_I]] ], [ false, [[BB62]] ]
  44 ; CHECK-NEXT:    br label [[FLOW]]
  45 ; CHECK:       bb18:
  46 ; CHECK-NEXT:    [[TMP19:%.*]] = extractelement <2 x i32> [[TMP]], i64 0
  47 ; CHECK-NEXT:    [[TMP22:%.*]] = lshr i32 [[TMP19]], 16
  48 ; CHECK-NEXT:    [[TMP24:%.*]] = urem i32 [[TMP22]], 52
  49 ; CHECK-NEXT:    [[TMP25:%.*]] = mul nuw nsw i32 [[TMP24]], 52
  50 ; CHECK-NEXT:    br label [[INNER_LOOP:%.*]]
  51 ; CHECK:       Flow2:
  52 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ [[TMP59:%.*]], [[INNER_LOOP_BREAK:%.*]] ], [ [[TMP7:%.*]], [[FLOW]] ]
  53 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ true, [[INNER_LOOP_BREAK]] ], [ [[TMP9:%.*]], [[FLOW]] ]
  54 ; CHECK-NEXT:    br i1 [[TMP4]], label [[END_ELSE_BLOCK:%.*]], label [[FLOW3]]
  55 ; CHECK:       INNER_LOOP:
  56 ; CHECK-NEXT:    [[INNER_LOOP_J:%.*]] = phi i32 [ [[INNER_LOOP_J_INC:%.*]], [[INNER_LOOP]] ], [ [[TMP25]], [[BB18:%.*]] ]
  57 ; CHECK-NEXT:    call void asm sideeffect "
  58 ; CHECK-NEXT:    [[INNER_LOOP_J_INC]] = add nsw i32 [[INNER_LOOP_J]], 1
  59 ; CHECK-NEXT:    [[INNER_LOOP_CMP:%.*]] = icmp eq i32 [[INNER_LOOP_J]], 0
  60 ; CHECK-NEXT:    br i1 [[INNER_LOOP_CMP]], label [[INNER_LOOP_BREAK]], label [[INNER_LOOP]]
  61 ; CHECK:       INNER_LOOP_BREAK:
  62 ; CHECK-NEXT:    [[TMP59]] = extractelement <4 x i32> [[TMP14]], i64 2
  63 ; CHECK-NEXT:    call void asm sideeffect "s_nop 23 ", "~{memory}"() #[[ATTR0:[0-9]+]]
  64 ; CHECK-NEXT:    br label [[FLOW2:%.*]]
  65 ; CHECK:       bb62:
  66 ; CHECK-NEXT:    [[LOAD13:%.*]] = icmp uge i32 [[TMP16]], 271
  67 ; CHECK-NEXT:    br i1 [[LOAD13]], label [[INCREMENT_I]], label [[FLOW1:%.*]]
  68 ; CHECK:       Flow3:
  69 ; CHECK-NEXT:    [[TMP5]] = phi i32 [ [[TMP3]], [[END_ELSE_BLOCK]] ], [ undef, [[FLOW2]] ]
  70 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[CMP_END_ELSE_BLOCK:%.*]], [[END_ELSE_BLOCK]] ], [ true, [[FLOW2]] ]
  71 ; CHECK-NEXT:    br i1 [[TMP6]], label [[FLOW4:%.*]], label [[LOOP_HEADER]]
  72 ; CHECK:       Flow4:
  73 ; CHECK-NEXT:    br i1 [[TMP8:%.*]], label [[BB64:%.*]], label [[RETURN:%.*]]
  74 ; CHECK:       bb64:
  75 ; CHECK-NEXT:    call void asm sideeffect "s_nop 42", "~{memory}"() #[[ATTR0]]
  76 ; CHECK-NEXT:    br label [[RETURN]]
  77 ; CHECK:       Flow:
  78 ; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[TMP0]], [[FLOW1]] ], [ undef, [[LOOP_HEADER]] ]
  79 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP1]], [[FLOW1]] ], [ false, [[LOOP_HEADER]] ]
  80 ; CHECK-NEXT:    [[TMP9]] = phi i1 [ [[TMP2]], [[FLOW1]] ], [ false, [[LOOP_HEADER]] ]
  81 ; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ false, [[FLOW1]] ], [ true, [[LOOP_HEADER]] ]
  82 ; CHECK-NEXT:    br i1 [[TMP10]], label [[BB18]], label [[FLOW2]]
  83 ; CHECK:       INCREMENT_I:
  84 ; CHECK-NEXT:    [[INC_I]] = add i32 [[I]], 1
  85 ; CHECK-NEXT:    call void asm sideeffect "s_nop 0x1336
  86 ; CHECK-NEXT:    br label [[FLOW1]]
  87 ; CHECK:       END_ELSE_BLOCK:
  88 ; CHECK-NEXT:    call void asm sideeffect "s_nop 0x1337
  89 ; CHECK-NEXT:    [[CMP_END_ELSE_BLOCK]] = icmp eq i32 [[TMP3]], -1
  90 ; CHECK-NEXT:    br label [[FLOW3]]
  91 ; CHECK:       RETURN:
  92 ; CHECK-NEXT:    call void asm sideeffect "s_nop 0x99
  93 ; CHECK-NEXT:    store volatile <2 x float> [[LOAD1]], ptr addrspace(1) undef, align 8
  94 ; CHECK-NEXT:    ret void
  95 ;
  96 entry:
  97   %tmp = load volatile <2 x i32>, ptr addrspace(1) undef, align 16
  98   %load1 = load volatile <2 x float>, ptr addrspace(1) undef
  99   %tid = call i32 @llvm.amdgcn.workitem.id.x()
 100   %gep = getelementptr inbounds i32, ptr addrspace(1) %arg0, i32 %tid
 101   %i.initial = load volatile i32, ptr addrspace(1) %gep, align 4
 102   br label %LOOP.HEADER
 103
 104 LOOP.HEADER:
 105   %i = phi i32 [ %i.final, %END_ELSE_BLOCK ], [ %i.initial, %entry ]
 106   call void asm sideeffect "s_nop 0x100b ; loop $0 ", "r,~{memory}"(i32 %i) #0
 107   %tmp12 = zext i32 %i to i64
 108   %tmp13 = getelementptr inbounds <4 x i32>, ptr addrspace(1) null, i64 %tmp12
 109   %tmp14 = load <4 x i32>, ptr addrspace(1) %tmp13, align 16
 110   %tmp15 = extractelement <4 x i32> %tmp14, i64 0
 111   %tmp16 = and i32 %tmp15, 65535
 112   %tmp17 = icmp eq i32 %tmp16, 1
 113   br i1 %tmp17, label %bb18, label %bb62
 114
 115 bb18:
 116   %tmp19 = extractelement <2 x i32> %tmp, i64 0
 117   %tmp22 = lshr i32 %tmp19, 16
 118   %tmp24 = urem i32 %tmp22, 52
 119   %tmp25 = mul nuw nsw i32 %tmp24, 52
 120   br label %INNER_LOOP
 121
 122 INNER_LOOP:
 123   %inner.loop.j = phi i32 [ %tmp25, %bb18 ], [ %inner.loop.j.inc, %INNER_LOOP ]
 124   call void asm sideeffect "; inner loop body", ""() #0
 125   %inner.loop.j.inc = add nsw i32 %inner.loop.j, 1
 126   %inner.loop.cmp = icmp eq i32 %inner.loop.j, 0
 127   br i1 %inner.loop.cmp, label %INNER_LOOP_BREAK, label %INNER_LOOP
 128
 129 INNER_LOOP_BREAK:
 130   %tmp59 = extractelement <4 x i32> %tmp14, i64 2
 131   call void asm sideeffect "s_nop 23 ", "~{memory}"() #0
 132   br label %END_ELSE_BLOCK
 133
 134 bb62:
 135   %load13 = icmp ult i32 %tmp16, 271
 136   br i1 %load13, label %bb64, label %INCREMENT_I
 137
 138 bb64:
 139   call void asm sideeffect "s_nop 42", "~{memory}"() #0
 140   br label %RETURN
 141
 142 INCREMENT_I:
 143   %inc.i = add i32 %i, 1
 144   call void asm sideeffect "s_nop 0x1336 ; increment $0", "v,~{memory}"(i32 %inc.i) #0
 145   br label %END_ELSE_BLOCK
 146
 147 END_ELSE_BLOCK:
 148   %i.final = phi i32 [ %tmp59, %INNER_LOOP_BREAK ], [ %inc.i, %INCREMENT_I ]
 149   call void asm sideeffect "s_nop 0x1337 ; end else block $0", "v,~{memory}"(i32 %i.final) #0
 150   %cmp.end.else.block = icmp eq i32 %i.final, -1
 151   br i1 %cmp.end.else.block, label %RETURN, label %LOOP.HEADER
 152
 153 RETURN:
 154   call void asm sideeffect "s_nop 0x99 ; ClosureEval return", "~{memory}"() #0
 155   store volatile <2 x float> %load1, ptr addrspace(1) undef, align 8
 156   ret void
 157 }
 158
 159 declare i32 @llvm.amdgcn.workitem.id.x() #1
 160
 161 attributes #0 = { convergent nounwind }
 162 attributes #1 = { convergent nounwind readnone }