llvm/test/Transforms/StructurizeCFG/workarounds/needs-unified-loop-exits.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -unify-loop-exits -structurizecfg -S | FileCheck %s
   3
   4 ; The structurizer uses an RPO traversal over a region, along with a
   5 ; manual hack that is meant to sort ensure that blocks within a loop
   6 ; are all visited before visiting blocks outside the loop. But this
   7 ; does not always work as expected. For example the results are
   8 ; incorrect when multiple nested loops are involved.
   9
  10 ; The workaround for this is to unify loop exits. Each loop now
  11 ; becomes an SESE region with a single header and a single exit. The
  12 ; structurizer is a region pass, and it no longer sees the entire loop
  13 ; nest in a single region. More importantly, for each loop, the only
  14 ; block reachable outside the loop is the region exit, which avoids
  15 ; any confusion in the hacked RPO traversal.
  16
  17 ; In the function below, B1 is an exiting block in outer loop H1. It's
  18 ; successor inside the loop is the header of another loop H2. Due to
  19 ; the incorrect traversal, B1 dominates all the blocks in the
  20 ; structurized program, except the header H1.
  21
  22 define void @exiting-block(i1 %PredH1, i1 %PredB2, i1 %PredB1, i1 %PredH2) {
  23 ; CHECK-LABEL: @exiting-block(
  24 ; CHECK-NEXT:  entry:
  25 ; CHECK-NEXT:    [[PREDH1_INV:%.*]] = xor i1 [[PREDH1:%.*]], true
  26 ; CHECK-NEXT:    [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true
  27 ; CHECK-NEXT:    br label [[H1:%.*]]
  28 ; CHECK:       H1:
  29 ; CHECK-NEXT:    br i1 [[PREDH1_INV]], label [[B1:%.*]], label [[FLOW3:%.*]]
  30 ; CHECK:       Flow3:
  31 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[B1]] ], [ undef, [[H1]] ]
  32 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[PREDB1:%.*]], [[B1]] ], [ [[PREDH1]], [[H1]] ]
  33 ; CHECK-NEXT:    br i1 [[TMP1]], label [[H2:%.*]], label [[FLOW4:%.*]]
  34 ; CHECK:       H2:
  35 ; CHECK-NEXT:    br i1 [[PREDH2:%.*]], label [[B2:%.*]], label [[FLOW:%.*]]
  36 ; CHECK:       B2:
  37 ; CHECK-NEXT:    br i1 [[PREDB2_INV]], label [[L2:%.*]], label [[FLOW2:%.*]]
  38 ; CHECK:       Flow:
  39 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ]
  40 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ false, [[FLOW2]] ], [ undef, [[H2]] ]
  41 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW2]] ], [ true, [[H2]] ]
  42 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP_EXIT_GUARD1:%.*]], label [[H2]]
  43 ; CHECK:       L2:
  44 ; CHECK-NEXT:    br label [[FLOW2]]
  45 ; CHECK:       L1:
  46 ; CHECK-NEXT:    br label [[FLOW5:%.*]]
  47 ; CHECK:       B1:
  48 ; CHECK-NEXT:    br label [[FLOW3]]
  49 ; CHECK:       C:
  50 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  51 ; CHECK:       exit:
  52 ; CHECK-NEXT:    ret void
  53 ; CHECK:       Flow5:
  54 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ undef, [[L1:%.*]] ], [ [[TMP3]], [[LOOP_EXIT_GUARD1]] ]
  55 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ false, [[L1]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
  56 ; CHECK-NEXT:    br label [[FLOW4]]
  57 ; CHECK:       loop.exit.guard:
  58 ; CHECK-NEXT:    br i1 [[TMP8:%.*]], label [[C:%.*]], label [[EXIT]]
  59 ; CHECK:       Flow2:
  60 ; CHECK-NEXT:    [[TMP7]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
  61 ; CHECK-NEXT:    br label [[FLOW]]
  62 ; CHECK:       Flow4:
  63 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP5]], [[FLOW5]] ], [ [[TMP0]], [[FLOW3]] ]
  64 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[TMP6]], [[FLOW5]] ], [ true, [[FLOW3]] ]
  65 ; CHECK-NEXT:    br i1 [[TMP9]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
  66 ; CHECK:       loop.exit.guard1:
  67 ; CHECK-NEXT:    br i1 [[TMP2]], label [[L1]], label [[FLOW5]]
  68 ;
  69 entry:
  70   br label %H1
  71
  72 H1:                                               ; preds = %L1, %entry
  73   br i1 %PredH1, label %H2, label %B1
  74
  75 H2:                                               ; preds = %B1, %L2, %H1
  76   br i1 %PredH2, label %B2, label %L1
  77
  78 B2:                                               ; preds = %H2
  79   br i1 %PredB2, label %exit, label %L2
  80
  81 L2:                                               ; preds = %B2
  82   br label %H2
  83
  84 L1:                                               ; preds = %H2
  85   br label %H1
  86
  87 B1:                                               ; preds = %H1
  88   br i1 %PredB1, label %H2, label %C
  89
  90 C:                                                ; preds = %B1
  91   br label %exit
  92
  93 exit:                                             ; preds = %C, %B2
  94   ret void
  95 }
  96
  97 ; The function below has three nested loops. Due to the incorrect
  98 ; traversal, H2 dominates H3 in the structurized program, and the
  99 ; backedge from L13 to H3 has no equivalent path.
 100
 101 define void @incorrect-backedge(i1 %PredH2, i1 %PredH3, i1 %PredL2, i1 %PredL13, i1 %PredL1)
 102 ; CHECK-LABEL: @incorrect-backedge(
 103 ; CHECK-NEXT:  entry:
 104 ; CHECK-NEXT:    [[PREDH2_INV:%.*]] = xor i1 [[PREDH2:%.*]], true
 105 ; CHECK-NEXT:    [[PREDL2_INV:%.*]] = xor i1 [[PREDL2:%.*]], true
 106 ; CHECK-NEXT:    [[PREDH3_INV:%.*]] = xor i1 [[PREDH3:%.*]], true
 107 ; CHECK-NEXT:    [[PREDL13_INV:%.*]] = xor i1 [[PREDL13:%.*]], true
 108 ; CHECK-NEXT:    br label [[H1:%.*]]
 109 ; CHECK:       H1:
 110 ; CHECK-NEXT:    br label [[H2:%.*]]
 111 ; CHECK:       H2:
 112 ; CHECK-NEXT:    br i1 [[PREDH2_INV]], label [[H3:%.*]], label [[FLOW4:%.*]]
 113 ; CHECK:       H3:
 114 ; CHECK-NEXT:    br i1 [[PREDH3_INV]], label [[L2:%.*]], label [[FLOW:%.*]]
 115 ; CHECK:       L2:
 116 ; CHECK-NEXT:    br i1 [[PREDL2_INV]], label [[L13:%.*]], label [[FLOW3:%.*]]
 117 ; CHECK:       Flow:
 118 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
 119 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW3]] ], [ false, [[H3]] ]
 120 ; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP8]], [[FLOW3]] ], [ true, [[H3]] ]
 121 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP9:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
 122 ; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_EXIT_GUARD2:%.*]], label [[H3]]
 123 ; CHECK:       L13:
 124 ; CHECK-NEXT:    br label [[FLOW3]]
 125 ; CHECK:       Flow5:
 126 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP10:%.*]], [[LOOP_EXIT_GUARD1:%.*]] ], [ true, [[LOOP_EXIT_GUARD:%.*]] ]
 127 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD1]] ], [ true, [[LOOP_EXIT_GUARD]] ]
 128 ; CHECK-NEXT:    br i1 [[TMP5]], label [[L1:%.*]], label [[FLOW6:%.*]]
 129 ; CHECK:       L1:
 130 ; CHECK-NEXT:    br label [[FLOW6]]
 131 ; CHECK:       Flow6:
 132 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[PREDL1:%.*]], [[L1]] ], [ [[TMP4]], [[FLOW5:%.*]] ]
 133 ; CHECK-NEXT:    br i1 [[TMP6]], label [[EXIT:%.*]], label [[H1]]
 134 ; CHECK:       exit:
 135 ; CHECK-NEXT:    ret void
 136 ; CHECK:       loop.exit.guard:
 137 ; CHECK-NEXT:    br i1 [[DOTINV:%.*]], label [[LOOP_EXIT_GUARD1]], label [[FLOW5]]
 138 ; CHECK:       loop.exit.guard1:
 139 ; CHECK-NEXT:    br label [[FLOW5]]
 140 ; CHECK:       Flow3:
 141 ; CHECK-NEXT:    [[TMP7]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ]
 142 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ false, [[L13]] ], [ undef, [[L2]] ]
 143 ; CHECK-NEXT:    [[TMP9]] = phi i1 [ [[PREDL13_INV]], [[L13]] ], [ true, [[L2]] ]
 144 ; CHECK-NEXT:    br label [[FLOW]]
 145 ; CHECK:       Flow4:
 146 ; CHECK-NEXT:    [[TMP10]] = phi i1 [ [[TMP2]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ]
 147 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ [[TMP1]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
 148 ; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
 149 ; CHECK-NEXT:    [[DOTINV]] = xor i1 [[TMP11]], true
 150 ; CHECK-NEXT:    br i1 [[TMP12]], label [[LOOP_EXIT_GUARD]], label [[H2]]
 151 ; CHECK:       loop.exit.guard2:
 152 ; CHECK-NEXT:    br label [[FLOW4]]
 153 ;
 154 {
 155 entry:
 156   br label %H1
 157
 158 H1:
 159   br label %H2
 160
 161 H2:
 162   br i1 %PredH2, label %L1, label %H3
 163
 164 H3:
 165   br i1 %PredH3, label %exit, label %L2
 166
 167 L2:
 168   br i1 %PredL2, label %H2, label %L13
 169
 170 L13:
 171   br i1 %PredL13, label %H3, label %H1
 172
 173 L1:
 174   br i1 %PredL1, label %exit, label %H1
 175
 176 exit:
 177   ret void
 178 }