test/Transforms/LoopUnroll/rebuild_lcssa.ll

   1 ; RUN: opt < %s -loop-unroll -S | FileCheck %s
   2 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
   3
   4 ; This test shows how unrolling an inner loop could break LCSSA for an outer
   5 ; loop, and there is no cheap way to recover it.
   6 ;
   7 ; In this case the inner loop, L3, is being unrolled. It only runs one
   8 ; iteration, so unrolling basically means replacing
   9 ;   br i1 true, label %exit, label %L3_header
  10 ; with
  11 ;   br label %exit
  12 ;
  13 ; However, this change messes up the loops structure: for instance, block
  14 ; L3_body no longer belongs to L2. It becomes an exit block for L2, so LCSSA
  15 ; phis for definitions in L2 should now be placed there. In particular, we need
  16 ; to insert such a definition for %y1.
  17
  18 ; CHECK-LABEL: @foo1
  19 define void @foo1() {
  20 entry:
  21   br label %L1_header
  22
  23 L1_header:
  24   br label %L2_header
  25
  26 L2_header:
  27   %y1 = phi i64 [ undef, %L1_header ], [ %x.lcssa, %L2_latch ]
  28   br label %L3_header
  29
  30 L3_header:
  31   %y2 = phi i64 [ 0, %L3_latch ], [ %y1, %L2_header ]
  32   %x = add i64 undef, -1
  33   br i1 true, label %L2_latch, label %L3_body
  34
  35 L2_latch:
  36   %x.lcssa = phi i64 [ %x, %L3_header ]
  37   br label %L2_header
  38
  39 ; CHECK:      L3_body:
  40 ; CHECK-NEXT:   %y1.lcssa = phi i64 [ %y1, %L3_header ]
  41 L3_body:
  42   store i64 %y1, i64* undef
  43   br i1 false, label %L3_latch, label %L1_latch
  44
  45 L3_latch:
  46   br i1 true, label %exit, label %L3_header
  47
  48 L1_latch:
  49   %y.lcssa = phi i64 [ %y2, %L3_body ]
  50   br label %L1_header
  51
  52 exit:
  53   ret void
  54 }
  55
  56 ; Additional tests for some corner cases.
  57 ;
  58 ; CHECK-LABEL: @foo2
  59 define void @foo2() {
  60 entry:
  61   br label %L1_header
  62
  63 L1_header:
  64   br label %L2_header
  65
  66 L2_header:
  67   %a = phi i64 [ undef, %L1_header ], [ %dec_us, %L3_header ]
  68   br label %L3_header
  69
  70 L3_header:
  71   %b = phi i64 [ 0, %L3_latch ], [ %a, %L2_header ]
  72   %dec_us = add i64 undef, -1
  73   br i1 true, label %L2_header, label %L3_break_to_L1
  74
  75 ; CHECK:      L3_break_to_L1:
  76 ; CHECK-NEXT:   %a.lcssa = phi i64 [ %a, %L3_header ]
  77 L3_break_to_L1:
  78   br i1 false, label %L3_latch, label %L1_latch
  79
  80 L1_latch:
  81   %b_lcssa = phi i64 [ %b, %L3_break_to_L1 ]
  82   br label %L1_header
  83
  84 L3_latch:
  85   br i1 true, label %Exit, label %L3_header
  86
  87 Exit:
  88   ret void
  89 }
  90
  91 ; CHECK-LABEL: @foo3
  92 define void @foo3() {
  93 entry:
  94   br label %L1_header
  95
  96 L1_header:
  97   %a = phi i8* [ %b, %L1_latch ], [ null, %entry ]
  98   br i1 undef, label %L2_header, label %L1_latch
  99
 100 L2_header:
 101   br i1 undef, label %L2_latch, label %L1_latch
 102
 103 ; CHECK:      L2_latch:
 104 ; CHECK-NEXT:   %a.lcssa = phi i8* [ %a, %L2_header ]
 105 L2_latch:
 106   br i1 true, label %L2_exit, label %L2_header
 107
 108 L1_latch:
 109   %b = phi i8* [ undef, %L1_header ], [ null, %L2_header ]
 110   br label %L1_header
 111
 112 L2_exit:
 113   %a_lcssa1 = phi i8* [ %a, %L2_latch ]
 114   br label %Exit
 115
 116 Exit:
 117   %a_lcssa2 = phi i8* [ %a_lcssa1, %L2_exit ]
 118   ret void
 119 }
 120
 121 ; PR26688
 122 ; CHECK-LABEL: @foo4
 123 define i8 @foo4() {
 124 entry:
 125   br label %L1_header
 126
 127 L1_header:
 128   %x = icmp eq i32 1, 0
 129   br label %L2_header
 130
 131 L2_header:
 132   br label %L3_header
 133
 134 L3_header:
 135   br i1 true, label %L2_header, label %L3_exiting
 136
 137 L3_exiting:
 138   br i1 true, label %L3_body, label %L1_latch
 139
 140 ; CHECK:      L3_body:
 141 ; CHECK-NEXT:   %x.lcssa = phi i1
 142 L3_body:
 143   br i1 %x, label %L3_latch, label %L3_latch
 144
 145 L3_latch:
 146   br i1 false, label %L3_header, label %exit
 147
 148 L1_latch:
 149   br label %L1_header
 150
 151 exit:
 152   ret i8 0
 153 }
 154
 155 ; CHECK-LABEL: @foo5
 156 define void @foo5() {
 157 entry:
 158   br label %outer
 159
 160 outer:
 161   br label %inner1
 162
 163 ; CHECK: inner1:
 164 ; CHECK-NOT: br i1 true
 165 ; CHECK: br label %inner2_indirect_exit
 166 inner1:
 167   br i1 true, label %inner2_indirect_exit.preheader, label %inner1
 168
 169 inner2_indirect_exit.preheader:
 170   br label %inner2_indirect_exit
 171
 172 inner2_indirect_exit:
 173   %a = phi i32 [ %b, %inner2_latch ], [ undef, %inner2_indirect_exit.preheader ]
 174   indirectbr i8* undef, [label %inner2_latch, label %inner3, label %outer_latch]
 175
 176 inner2_latch:
 177   %b = load i32, i32* undef, align 8
 178   br label %inner2_indirect_exit
 179
 180 inner3:
 181   %a.lcssa = phi i32 [ %a.lcssa, %inner3 ], [ %a, %inner2_indirect_exit ]
 182   br i1 true, label %outer_latch.loopexit, label %inner3
 183
 184 outer_latch.loopexit:
 185   %a.lcssa.lcssa = phi i32 [ %a.lcssa, %inner3 ]
 186   br label %outer_latch
 187
 188 outer_latch:
 189   br label %outer
 190 }