llvm/test/Transforms/LoopUnroll/rebuild_lcssa.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=loop-unroll -verify-loop-lcssa -S | FileCheck %s
   3 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
   4
   5 ; This test shows how unrolling an inner loop could break LCSSA for an outer
   6 ; loop, and there is no cheap way to recover it.
   7 ;
   8 ; In this case the inner loop, L3, is being unrolled. It only runs one
   9 ; iteration, so unrolling basically means replacing
  10 ;   br i1 true, label %exit, label %L3_header
  11 ; with
  12 ;   br label %exit
  13 ;
  14 ; However, this change messes up the loops structure: for instance, block
  15 ; L3_body no longer belongs to L2. It becomes an exit block for L2, so LCSSA
  16 ; phis for definitions in L2 should now be placed there. In particular, we need
  17 ; to insert such a definition for %y1.
  18
  19 define void @foo1() {
  20 ; CHECK-LABEL: @foo1(
  21 ; CHECK-NEXT:  entry:
  22 ; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
  23 ; CHECK:       L1_header:
  24 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
  25 ; CHECK:       L2_header:
  26 ; CHECK-NEXT:    [[Y1:%.*]] = phi i64 [ undef, [[L1_HEADER]] ], [ [[X_LCSSA:%.*]], [[L2_LATCH:%.*]] ]
  27 ; CHECK-NEXT:    br label [[L3_HEADER:%.*]]
  28 ; CHECK:       L3_header:
  29 ; CHECK-NEXT:    br i1 true, label [[L2_LATCH]], label [[L3_BODY:%.*]]
  30 ; CHECK:       L2_latch:
  31 ; CHECK-NEXT:    [[X_LCSSA]] = phi i64 [ undef, [[L3_HEADER]] ]
  32 ; CHECK-NEXT:    br label [[L2_HEADER]]
  33 ; CHECK:       L3_body:
  34 ; CHECK-NEXT:    [[Y1_LCSSA:%.*]] = phi i64 [ [[Y1]], [[L3_HEADER]] ]
  35 ; CHECK-NEXT:    store i64 [[Y1_LCSSA]], ptr undef, align 8
  36 ; CHECK-NEXT:    br i1 false, label [[L3_LATCH:%.*]], label [[L1_LATCH:%.*]]
  37 ; CHECK:       L3_latch:
  38 ; CHECK-NEXT:    ret void
  39 ; CHECK:       L1_latch:
  40 ; CHECK-NEXT:    [[Y_LCSSA:%.*]] = phi i64 [ [[Y1_LCSSA]], [[L3_BODY]] ]
  41 ; CHECK-NEXT:    br label [[L1_HEADER]]
  42 ;
  43 entry:
  44   br label %L1_header
  45
  46 L1_header:
  47   br label %L2_header
  48
  49 L2_header:
  50   %y1 = phi i64 [ undef, %L1_header ], [ %x.lcssa, %L2_latch ]
  51   br label %L3_header
  52
  53 L3_header:
  54   %y2 = phi i64 [ 0, %L3_latch ], [ %y1, %L2_header ]
  55   %x = add i64 undef, -1
  56   br i1 true, label %L2_latch, label %L3_body
  57
  58 L2_latch:
  59   %x.lcssa = phi i64 [ %x, %L3_header ]
  60   br label %L2_header
  61
  62 L3_body:
  63   store i64 %y1, ptr undef
  64   br i1 false, label %L3_latch, label %L1_latch
  65
  66 L3_latch:
  67   br i1 true, label %exit, label %L3_header
  68
  69 L1_latch:
  70   %y.lcssa = phi i64 [ %y2, %L3_body ]
  71   br label %L1_header
  72
  73 exit:
  74   ret void
  75 }
  76
  77 ; Additional tests for some corner cases.
  78 define void @foo2() {
  79 ; CHECK-LABEL: @foo2(
  80 ; CHECK-NEXT:  entry:
  81 ; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
  82 ; CHECK:       L1_header:
  83 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
  84 ; CHECK:       L2_header.loopexit:
  85 ; CHECK-NEXT:    [[DEC_US_LCSSA:%.*]] = phi i64 [ undef, [[L3_HEADER:%.*]] ]
  86 ; CHECK-NEXT:    br label [[L2_HEADER]]
  87 ; CHECK:       L2_header:
  88 ; CHECK-NEXT:    [[A:%.*]] = phi i64 [ undef, [[L1_HEADER]] ], [ [[DEC_US_LCSSA]], [[L2_HEADER_LOOPEXIT:%.*]] ]
  89 ; CHECK-NEXT:    br label [[L3_HEADER]]
  90 ; CHECK:       L3_header:
  91 ; CHECK-NEXT:    br i1 true, label [[L2_HEADER_LOOPEXIT]], label [[L3_BREAK_TO_L1:%.*]]
  92 ; CHECK:       L3_break_to_L1:
  93 ; CHECK-NEXT:    [[A_LCSSA:%.*]] = phi i64 [ [[A]], [[L3_HEADER]] ]
  94 ; CHECK-NEXT:    br i1 false, label [[L3_LATCH:%.*]], label [[L1_LATCH:%.*]]
  95 ; CHECK:       L1_latch:
  96 ; CHECK-NEXT:    [[B_LCSSA:%.*]] = phi i64 [ [[A_LCSSA]], [[L3_BREAK_TO_L1]] ]
  97 ; CHECK-NEXT:    br label [[L1_HEADER]]
  98 ; CHECK:       L3_latch:
  99 ; CHECK-NEXT:    ret void
 100 ;
 101 entry:
 102   br label %L1_header
 103
 104 L1_header:
 105   br label %L2_header
 106
 107 L2_header:
 108   %a = phi i64 [ undef, %L1_header ], [ %dec_us, %L3_header ]
 109   br label %L3_header
 110
 111 L3_header:
 112   %b = phi i64 [ 0, %L3_latch ], [ %a, %L2_header ]
 113   %dec_us = add i64 undef, -1
 114   br i1 true, label %L2_header, label %L3_break_to_L1
 115
 116 L3_break_to_L1:
 117   br i1 false, label %L3_latch, label %L1_latch
 118
 119 L1_latch:
 120   %b_lcssa = phi i64 [ %b, %L3_break_to_L1 ]
 121   br label %L1_header
 122
 123 L3_latch:
 124   br i1 true, label %Exit, label %L3_header
 125
 126 Exit:
 127   ret void
 128 }
 129
 130 define void @foo3(i1 %arg) {
 131 ; CHECK-LABEL: @foo3(
 132 ; CHECK-NEXT:  entry:
 133 ; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
 134 ; CHECK:       L1_header:
 135 ; CHECK-NEXT:    [[A:%.*]] = phi ptr [ [[B:%.*]], [[L1_LATCH:%.*]] ], [ null, [[ENTRY:%.*]] ]
 136 ; CHECK-NEXT:    br i1 [[ARG:%.*]], label [[L2_HEADER_PREHEADER:%.*]], label [[L1_LATCH]]
 137 ; CHECK:       L2_header.preheader:
 138 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
 139 ; CHECK:       L2_header:
 140 ; CHECK-NEXT:    br i1 [[ARG]], label [[L2_LATCH:%.*]], label [[L1_LATCH_LOOPEXIT:%.*]]
 141 ; CHECK:       L2_latch:
 142 ; CHECK-NEXT:    [[A_LCSSA:%.*]] = phi ptr [ [[A]], [[L2_HEADER]] ]
 143 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 144 ; CHECK:       L1_latch.loopexit:
 145 ; CHECK-NEXT:    br label [[L1_LATCH]]
 146 ; CHECK:       L1_latch:
 147 ; CHECK-NEXT:    [[B]] = phi ptr [ undef, [[L1_HEADER]] ], [ null, [[L1_LATCH_LOOPEXIT]] ]
 148 ; CHECK-NEXT:    br label [[L1_HEADER]]
 149 ; CHECK:       Exit:
 150 ; CHECK-NEXT:    [[A_LCSSA2:%.*]] = phi ptr [ [[A_LCSSA]], [[L2_LATCH]] ]
 151 ; CHECK-NEXT:    ret void
 152 ;
 153 entry:
 154   br label %L1_header
 155
 156 L1_header:
 157   %a = phi ptr [ %b, %L1_latch ], [ null, %entry ]
 158   br i1 %arg, label %L2_header, label %L1_latch
 159
 160 L2_header:
 161   br i1 %arg, label %L2_latch, label %L1_latch
 162
 163 L2_latch:
 164   br i1 true, label %L2_exit, label %L2_header
 165
 166 L1_latch:
 167   %b = phi ptr [ undef, %L1_header ], [ null, %L2_header ]
 168   br label %L1_header
 169
 170 L2_exit:
 171   %a_lcssa1 = phi ptr [ %a, %L2_latch ]
 172   br label %Exit
 173
 174 Exit:
 175   %a_lcssa2 = phi ptr [ %a_lcssa1, %L2_exit ]
 176   ret void
 177 }
 178
 179 ; PR26688
 180 define i8 @foo4() {
 181 ; CHECK-LABEL: @foo4(
 182 ; CHECK-NEXT:  entry:
 183 ; CHECK-NEXT:    br label [[L1_HEADER:%.*]]
 184 ; CHECK:       L1_header:
 185 ; CHECK-NEXT:    br label [[L2_HEADER:%.*]]
 186 ; CHECK:       L2_header.loopexit:
 187 ; CHECK-NEXT:    br label [[L2_HEADER]]
 188 ; CHECK:       L2_header:
 189 ; CHECK-NEXT:    br label [[L3_HEADER:%.*]]
 190 ; CHECK:       L3_header:
 191 ; CHECK-NEXT:    br i1 true, label [[L2_HEADER_LOOPEXIT:%.*]], label [[L3_EXITING:%.*]]
 192 ; CHECK:       L3_exiting:
 193 ; CHECK-NEXT:    br i1 true, label [[L3_BODY:%.*]], label [[L1_LATCH:%.*]]
 194 ; CHECK:       L3_body:
 195 ; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i1 [ false, [[L3_EXITING]] ]
 196 ; CHECK-NEXT:    br i1 [[X_LCSSA]], label [[L3_LATCH:%.*]], label [[L3_LATCH]]
 197 ; CHECK:       L3_latch:
 198 ; CHECK-NEXT:    ret i8 0
 199 ; CHECK:       L1_latch:
 200 ; CHECK-NEXT:    unreachable
 201 ;
 202 entry:
 203   br label %L1_header
 204
 205 L1_header:
 206   %x = icmp eq i32 1, 0
 207   br label %L2_header
 208
 209 L2_header:
 210   br label %L3_header
 211
 212 L3_header:
 213   br i1 true, label %L2_header, label %L3_exiting
 214
 215 L3_exiting:
 216   br i1 true, label %L3_body, label %L1_latch
 217
 218 L3_body:
 219   br i1 %x, label %L3_latch, label %L3_latch
 220
 221 L3_latch:
 222   br i1 false, label %L3_header, label %exit
 223
 224 L1_latch:
 225   br label %L1_header
 226
 227 exit:
 228   ret i8 0
 229 }
 230
 231 define void @foo5() {
 232 ; CHECK-LABEL: @foo5(
 233 ; CHECK-NEXT:  entry:
 234 ; CHECK-NEXT:    br label [[OUTER:%.*]]
 235 ; CHECK:       outer:
 236 ; CHECK-NEXT:    br label [[INNER1:%.*]]
 237 ; CHECK:       inner1:
 238 ; CHECK-NEXT:    br label [[INNER2_INDIRECT_EXIT:%.*]]
 239 ; CHECK:       inner2_indirect_exit:
 240 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ [[B:%.*]], [[INNER2_LATCH:%.*]] ], [ undef, [[INNER1]] ]
 241 ; CHECK-NEXT:    indirectbr ptr undef, [label [[INNER2_LATCH]], label [[INNER3:%.*]], label %outer_latch]
 242 ; CHECK:       inner2_latch:
 243 ; CHECK-NEXT:    [[B]] = load i32, ptr undef, align 8
 244 ; CHECK-NEXT:    br label [[INNER2_INDIRECT_EXIT]]
 245 ; CHECK:       inner3:
 246 ; CHECK-NEXT:    [[A_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ], [ [[A]], [[INNER2_INDIRECT_EXIT]] ]
 247 ; CHECK-NEXT:    br i1 true, label [[OUTER_LATCH_LOOPEXIT:%.*]], label [[INNER3]]
 248 ; CHECK:       outer_latch.loopexit:
 249 ; CHECK-NEXT:    [[A_LCSSA_LCSSA2:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]
 250 ; CHECK-NEXT:    [[A_LCSSA_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]
 251 ; CHECK-NEXT:    br label [[OUTER_LATCH:%.*]]
 252 ; CHECK:       outer_latch:
 253 ; CHECK-NEXT:    br label [[OUTER]]
 254 ;
 255 entry:
 256   br label %outer
 257
 258 outer:
 259   br label %inner1
 260
 261 inner1:
 262   br i1 true, label %inner2_indirect_exit.preheader, label %inner1
 263
 264 inner2_indirect_exit.preheader:
 265   br label %inner2_indirect_exit
 266
 267 inner2_indirect_exit:
 268   %a = phi i32 [ %b, %inner2_latch ], [ undef, %inner2_indirect_exit.preheader ]
 269   indirectbr ptr undef, [label %inner2_latch, label %inner3, label %outer_latch]
 270
 271 inner2_latch:
 272   %b = load i32, ptr undef, align 8
 273   br label %inner2_indirect_exit
 274
 275 inner3:
 276   %a.lcssa = phi i32 [ %a.lcssa, %inner3 ], [ %a, %inner2_indirect_exit ]
 277   br i1 true, label %outer_latch.loopexit, label %inner3
 278
 279 outer_latch.loopexit:
 280   %a.lcssa.lcssa = phi i32 [ %a.lcssa, %inner3 ]
 281   br label %outer_latch
 282
 283 outer_latch:
 284   br label %outer
 285 }