llvm/test/Transforms/StructurizeCFG/interleaved-loop-order.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -lowerswitch -structurizecfg %s -o - | FileCheck %s
   3
   4 ; This test have an outer loop containing an inner loop,
   5 ; for which there is an interleaved post-order traversal.
   6 ;
   7 ; This used to produce incorrect code.
   8 ; For example %outer.loop.body used to branched to %inner.loop.end
   9 ; (instead of %inner.loop.header).
  10
  11 define i1 @test_nested(i32 %x, i1 %b1, i1 %b2, i1 %b3) {
  12 ; CHECK-LABEL: @test_nested(
  13 ; CHECK-NEXT:  entry:
  14 ; CHECK-NEXT:    [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true
  15 ; CHECK-NEXT:    br label [[OUTER_LOOP_HEADER:%.*]]
  16 ; CHECK:       Flow12:
  17 ; CHECK-NEXT:    br i1 [[TMP3:%.*]], label [[EXIT_TRUE:%.*]], label [[FLOW13:%.*]]
  18 ; CHECK:       exit.true:
  19 ; CHECK-NEXT:    br label [[FLOW13]]
  20 ; CHECK:       Flow13:
  21 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[EXIT_TRUE]] ], [ undef, [[FLOW12:%.*]] ]
  22 ; CHECK-NEXT:    br i1 [[TMP2:%.*]], label [[EXIT_FALSE:%.*]], label [[EXIT:%.*]]
  23 ; CHECK:       exit.false:
  24 ; CHECK-NEXT:    br label [[EXIT]]
  25 ; CHECK:       outer.loop.header:
  26 ; CHECK-NEXT:    br i1 [[B1:%.*]], label [[OUTER_LOOP_BODY:%.*]], label [[FLOW3:%.*]]
  27 ; CHECK:       outer.loop.body:
  28 ; CHECK-NEXT:    br label [[INNER_LOOP_HEADER:%.*]]
  29 ; CHECK:       Flow3:
  30 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP16:%.*]], [[FLOW11:%.*]] ], [ true, [[OUTER_LOOP_HEADER]] ]
  31 ; CHECK-NEXT:    [[TMP2]] = phi i1 [ [[TMP12:%.*]], [[FLOW11]] ], [ false, [[OUTER_LOOP_HEADER]] ]
  32 ; CHECK-NEXT:    [[TMP3]] = phi i1 [ false, [[FLOW11]] ], [ true, [[OUTER_LOOP_HEADER]] ]
  33 ; CHECK-NEXT:    br i1 [[TMP1]], label [[FLOW12]], label [[OUTER_LOOP_HEADER]]
  34 ; CHECK:       inner.loop.header:
  35 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW4:%.*]] ], [ false, [[OUTER_LOOP_BODY]] ]
  36 ; CHECK-NEXT:    br i1 [[B2:%.*]], label [[INNER_LOOP_BODY:%.*]], label [[FLOW4]]
  37 ; CHECK:       Flow6:
  38 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[INNER_LOOP_LATCH:%.*]] ], [ true, [[LEAFBLOCK:%.*]] ]
  39 ; CHECK-NEXT:    br label [[FLOW5:%.*]]
  40 ; CHECK:       Flow7:
  41 ; CHECK-NEXT:    br i1 [[TMP10:%.*]], label [[INNER_LOOP_END:%.*]], label [[FLOW8:%.*]]
  42 ; CHECK:       inner.loop.end:
  43 ; CHECK-NEXT:    br label [[FLOW8]]
  44 ; CHECK:       inner.loop.body:
  45 ; CHECK-NEXT:    br i1 [[B3_INV]], label [[INNER_LOOP_BODY_ELSE:%.*]], label [[FLOW:%.*]]
  46 ; CHECK:       inner.loop.body.else:
  47 ; CHECK-NEXT:    br label [[FLOW]]
  48 ; CHECK:       Flow:
  49 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ false, [[INNER_LOOP_BODY_ELSE]] ], [ true, [[INNER_LOOP_BODY]] ]
  50 ; CHECK-NEXT:    br i1 [[TMP6]], label [[INNER_LOOP_BODY_THEN:%.*]], label [[INNER_LOOP_COND:%.*]]
  51 ; CHECK:       inner.loop.body.then:
  52 ; CHECK-NEXT:    br label [[INNER_LOOP_COND]]
  53 ; CHECK:       Flow4:
  54 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ]
  55 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP18:%.*]], [[FLOW5]] ], [ [[TMP4]], [[INNER_LOOP_HEADER]] ]
  56 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[TMP19:%.*]], [[FLOW5]] ], [ false, [[INNER_LOOP_HEADER]] ]
  57 ; CHECK-NEXT:    [[TMP10]] = phi i1 [ false, [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ]
  58 ; CHECK-NEXT:    br i1 [[TMP7]], label [[FLOW7:%.*]], label [[INNER_LOOP_HEADER]]
  59 ; CHECK:       inner.loop.cond:
  60 ; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
  61 ; CHECK:       NodeBlock:
  62 ; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[X:%.*]], 1
  63 ; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK]], label [[FLOW5]]
  64 ; CHECK:       Flow8:
  65 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ true, [[INNER_LOOP_END]] ], [ false, [[FLOW7]] ]
  66 ; CHECK-NEXT:    br i1 [[TMP9]], label [[LEAFBLOCK1:%.*]], label [[FLOW9:%.*]]
  67 ; CHECK:       LeafBlock1:
  68 ; CHECK-NEXT:    [[SWITCHLEAF2:%.*]] = icmp eq i32 [[X]], 1
  69 ; CHECK-NEXT:    br i1 [[SWITCHLEAF2]], label [[INNER_LOOP_BREAK:%.*]], label [[FLOW10:%.*]]
  70 ; CHECK:       LeafBlock:
  71 ; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[X]], 0
  72 ; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[INNER_LOOP_LATCH]], label [[FLOW6:%.*]]
  73 ; CHECK:       Flow9:
  74 ; CHECK-NEXT:    [[TMP12]] = phi i1 [ [[TMP14:%.*]], [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ]
  75 ; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ [[TMP15:%.*]], [[FLOW10]] ], [ [[TMP11]], [[FLOW8]] ]
  76 ; CHECK-NEXT:    br i1 [[TMP13]], label [[OUTER_LOOP_CLEANUP:%.*]], label [[FLOW11]]
  77 ; CHECK:       inner.loop.break:
  78 ; CHECK-NEXT:    br label [[FLOW10]]
  79 ; CHECK:       Flow10:
  80 ; CHECK-NEXT:    [[TMP14]] = phi i1 [ false, [[INNER_LOOP_BREAK]] ], [ true, [[LEAFBLOCK1]] ]
  81 ; CHECK-NEXT:    [[TMP15]] = phi i1 [ true, [[INNER_LOOP_BREAK]] ], [ [[TMP11]], [[LEAFBLOCK1]] ]
  82 ; CHECK-NEXT:    br label [[FLOW9]]
  83 ; CHECK:       outer.loop.cleanup:
  84 ; CHECK-NEXT:    br label [[OUTER_LOOP_LATCH:%.*]]
  85 ; CHECK:       Flow11:
  86 ; CHECK-NEXT:    [[TMP16]] = phi i1 [ false, [[OUTER_LOOP_LATCH]] ], [ true, [[FLOW9]] ]
  87 ; CHECK-NEXT:    br label [[FLOW3]]
  88 ; CHECK:       outer.loop.latch:
  89 ; CHECK-NEXT:    br label [[FLOW11]]
  90 ; CHECK:       Flow5:
  91 ; CHECK-NEXT:    [[TMP17]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ true, [[NODEBLOCK]] ]
  92 ; CHECK-NEXT:    [[TMP18]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ [[TMP4]], [[NODEBLOCK]] ]
  93 ; CHECK-NEXT:    [[TMP19]] = phi i1 [ false, [[FLOW6]] ], [ true, [[NODEBLOCK]] ]
  94 ; CHECK-NEXT:    br label [[FLOW4]]
  95 ; CHECK:       inner.loop.latch:
  96 ; CHECK-NEXT:    br label [[FLOW6]]
  97 ; CHECK:       exit:
  98 ; CHECK-NEXT:    [[R:%.*]] = phi i1 [ [[TMP0]], [[FLOW13]] ], [ false, [[EXIT_FALSE]] ]
  99 ; CHECK-NEXT:    ret i1 [[R]]
 100 ;
 101 entry:
 102   br label %outer.loop.header
 103
 104 exit.true:                                       ; preds = %outer.loop.header
 105   br label %exit
 106
 107 exit.false:                                      ; preds = %inner.loop.cond
 108   br label %exit
 109
 110 outer.loop.header:                               ; preds = %outer.loop.latch, %entry
 111   br i1 %b1, label %outer.loop.body, label %exit.true
 112
 113 outer.loop.body:                                 ; preds = %outer.loop.header
 114   br label %inner.loop.header
 115
 116 inner.loop.header:                               ; preds = %inner.loop.latch, %outer.loop.body
 117   br i1 %b2, label %inner.loop.body, label %inner.loop.end
 118
 119 inner.loop.end:                                  ; preds = %inner.loop.header
 120   br label %outer.loop.cleanup
 121
 122 inner.loop.body:                                 ; preds = %inner.loop.header
 123   br i1 %b3, label %inner.loop.body.then, label %inner.loop.body.else
 124
 125 inner.loop.body.else:                            ; preds = %inner.loop.body
 126   br label %inner.loop.cond
 127
 128 inner.loop.body.then:                            ; preds = %inner.loop.body
 129   br label %inner.loop.cond
 130
 131 inner.loop.cond:                                 ; preds = %inner.loop.body.then, %inner.loop.body.else
 132   switch i32 %x, label %exit.false [
 133   i32 0, label %inner.loop.latch
 134   i32 1, label %inner.loop.break
 135   ]
 136
 137 inner.loop.break:                                ; preds = %inner.loop.cond
 138   br label %outer.loop.cleanup
 139
 140 outer.loop.cleanup:                              ; preds = %inner.loop.break, %inner.loop.end
 141   br label %outer.loop.latch
 142
 143 outer.loop.latch:                                ; preds = %outer.loop.cleanup
 144   br label %outer.loop.header
 145
 146 inner.loop.latch:                                ; preds = %inner.loop.cond
 147   br label %inner.loop.header
 148
 149 exit:                                            ; preds = %exit.false, %exit.true
 150   %r = phi i1 [ true, %exit.true ], [ false, %exit.false ]
 151   ret i1 %r
 152 }
 153
 154 ; This test checks sibling loops that by default have an
 155 ; interleaved post-order traversal.
 156
 157 define void @test_siblings(i1 %b1, i1 %b2, i1 %b3, i1 %b4, i1 %b5, i1 %b6, i1 %b7, i1 %b8, i1 %b9) {
 158 ; CHECK-LABEL: @test_siblings(
 159 ; CHECK-NEXT:  entry:
 160 ; CHECK-NEXT:    [[B9_INV:%.*]] = xor i1 [[B9:%.*]], true
 161 ; CHECK-NEXT:    [[B6_INV:%.*]] = xor i1 [[B6:%.*]], true
 162 ; CHECK-NEXT:    [[B2_INV:%.*]] = xor i1 [[B2:%.*]], true
 163 ; CHECK-NEXT:    [[B8_INV:%.*]] = xor i1 [[B8:%.*]], true
 164 ; CHECK-NEXT:    [[B5_INV:%.*]] = xor i1 [[B5:%.*]], true
 165 ; CHECK-NEXT:    [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true
 166 ; CHECK-NEXT:    [[B4_INV:%.*]] = xor i1 [[B4:%.*]], true
 167 ; CHECK-NEXT:    [[B1_INV:%.*]] = xor i1 [[B1:%.*]], true
 168 ; CHECK-NEXT:    br i1 [[B1_INV]], label [[IF_ELSE:%.*]], label [[FLOW:%.*]]
 169 ; CHECK:       if.else:
 170 ; CHECK-NEXT:    br label [[FLOW]]
 171 ; CHECK:       Flow:
 172 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[TMP0]], [[FLOW1:%.*]] ], [ [[B2]], [[IF_ELSE]] ], [ false, [[ENTRY:%.*]] ]
 173 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP5:%.*]], [[FLOW1]] ], [ [[B2_INV]], [[IF_ELSE]] ], [ false, [[ENTRY]] ]
 174 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW1]] ], [ false, [[IF_ELSE]] ], [ true, [[ENTRY]] ]
 175 ; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP1_HEADER:%.*]], label [[FLOW1]]
 176 ; CHECK:       loop1.header:
 177 ; CHECK-NEXT:    br i1 [[B3_INV]], label [[LOOP1_BODY:%.*]], label [[FLOW2:%.*]]
 178 ; CHECK:       Flow2:
 179 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ true, [[LOOP1_BODY]] ], [ [[TMP1]], [[LOOP1_HEADER]] ]
 180 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[B5_INV]], [[LOOP1_BODY]] ], [ [[B3]], [[LOOP1_HEADER]] ]
 181 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP1_LATCH:%.*]], label [[FLOW3:%.*]]
 182 ; CHECK:       loop1.latch:
 183 ; CHECK-NEXT:    br label [[FLOW3]]
 184 ; CHECK:       Flow1:
 185 ; CHECK-NEXT:    [[TMP5]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ [[TMP1]], [[FLOW]] ]
 186 ; CHECK-NEXT:    br i1 true, label [[FLOW4:%.*]], label [[FLOW]]
 187 ; CHECK:       loop1.body:
 188 ; CHECK-NEXT:    br label [[FLOW2]]
 189 ; CHECK:       Flow3:
 190 ; CHECK-NEXT:    [[TMP6]] = phi i1 [ false, [[LOOP1_LATCH]] ], [ [[TMP3]], [[FLOW2]] ]
 191 ; CHECK-NEXT:    br label [[FLOW1]]
 192 ; CHECK:       Flow4:
 193 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ [[TMP5]], [[FLOW1]] ]
 194 ; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP2_HEADER:%.*]], label [[FLOW5]]
 195 ; CHECK:       loop2.header:
 196 ; CHECK-NEXT:    br i1 [[B6_INV]], label [[LOOP2_BODY:%.*]], label [[FLOW6:%.*]]
 197 ; CHECK:       Flow5:
 198 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ [[TMP11:%.*]], [[FLOW7:%.*]] ], [ false, [[FLOW4]] ]
 199 ; CHECK-NEXT:    br i1 true, label [[FLOW8:%.*]], label [[FLOW4]]
 200 ; CHECK:       loop2.body:
 201 ; CHECK-NEXT:    br label [[FLOW6]]
 202 ; CHECK:       Flow6:
 203 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ true, [[LOOP2_BODY]] ], [ false, [[LOOP2_HEADER]] ]
 204 ; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[B7:%.*]], [[LOOP2_BODY]] ], [ [[B6]], [[LOOP2_HEADER]] ]
 205 ; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP2_LATCH:%.*]], label [[FLOW7]]
 206 ; CHECK:       loop2.latch:
 207 ; CHECK-NEXT:    br label [[FLOW7]]
 208 ; CHECK:       Flow7:
 209 ; CHECK-NEXT:    [[TMP11]] = phi i1 [ false, [[LOOP2_LATCH]] ], [ [[TMP9]], [[FLOW6]] ]
 210 ; CHECK-NEXT:    br label [[FLOW5]]
 211 ; CHECK:       Flow8:
 212 ; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ false, [[FLOW10:%.*]] ], [ [[TMP0]], [[FLOW5]] ]
 213 ; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW5]] ]
 214 ; CHECK-NEXT:    br i1 [[TMP13]], label [[LOOP3_HEADER:%.*]], label [[FLOW9:%.*]]
 215 ; CHECK:       loop3.header:
 216 ; CHECK-NEXT:    br label [[FLOW9]]
 217 ; CHECK:       Flow9:
 218 ; CHECK-NEXT:    [[TMP14:%.*]] = phi i1 [ true, [[LOOP3_HEADER]] ], [ [[TMP12]], [[FLOW8]] ]
 219 ; CHECK-NEXT:    br i1 [[TMP14]], label [[LOOP3_LATCH:%.*]], label [[FLOW10]]
 220 ; CHECK:       loop3.latch:
 221 ; CHECK-NEXT:    br label [[FLOW10]]
 222 ; CHECK:       Flow10:
 223 ; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[FLOW8]]
 224 ; CHECK:       exit:
 225 ; CHECK-NEXT:    ret void
 226 ;
 227 entry:
 228   br i1 %b1, label %loop1.header, label %if.else
 229
 230 if.else:
 231   br i1 %b2, label %loop3.latch, label %loop2.header
 232
 233 loop1.header:
 234   br i1 %b3, label %loop1.latch, label %loop1.body
 235
 236 loop1.latch:
 237   br i1 %b4, label %loop1.header, label %exit
 238
 239 loop1.body:
 240   br i1 %b5, label %loop2.header, label %loop1.latch
 241
 242 loop2.header:
 243   br i1 %b6, label %loop2.latch, label %loop2.body
 244
 245 loop2.body:
 246   br i1 %b7, label %loop2.latch, label %loop3.header
 247
 248 loop2.latch:
 249   br i1 %b8, label %loop2.header, label %exit
 250
 251 loop3.header:
 252   br label %loop3.latch
 253
 254 loop3.latch:
 255   br i1 %b9, label %loop3.header, label %exit
 256
 257 exit:
 258   ret void
 259 }