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 }