llvm/test/Transforms/DFAJumpThreading/dfa-jump-threading-transform.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -dfa-jump-threading %s | FileCheck %s
   3
   4 ; These tests check that the DFA jump threading transformation is applied
   5 ; properly to two CFGs. It checks that blocks are cloned, branches are updated,
   6 ; and SSA form is restored.
   7 define i32 @test1(i32 %num) {
   8 ; CHECK-LABEL: @test1(
   9 ; CHECK-NEXT:  entry:
  10 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
  11 ; CHECK:       for.body:
  12 ; CHECK-NEXT:    [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
  13 ; CHECK-NEXT:    [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ undef, [[FOR_INC]] ]
  14 ; CHECK-NEXT:    switch i32 [[STATE]], label [[FOR_INC_JT1:%.*]] [
  15 ; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
  16 ; CHECK-NEXT:    i32 2, label [[CASE2:%.*]]
  17 ; CHECK-NEXT:    ]
  18 ; CHECK:       for.body.jt2:
  19 ; CHECK-NEXT:    [[COUNT_JT2:%.*]] = phi i32 [ [[INC_JT2:%.*]], [[FOR_INC_JT2:%.*]] ]
  20 ; CHECK-NEXT:    [[STATE_JT2:%.*]] = phi i32 [ [[STATE_NEXT_JT2:%.*]], [[FOR_INC_JT2]] ]
  21 ; CHECK-NEXT:    br label [[CASE2]]
  22 ; CHECK:       for.body.jt1:
  23 ; CHECK-NEXT:    [[COUNT_JT1:%.*]] = phi i32 [ [[INC_JT1:%.*]], [[FOR_INC_JT1]] ]
  24 ; CHECK-NEXT:    [[STATE_JT1:%.*]] = phi i32 [ [[STATE_NEXT_JT1:%.*]], [[FOR_INC_JT1]] ]
  25 ; CHECK-NEXT:    br label [[CASE1]]
  26 ; CHECK:       case1:
  27 ; CHECK-NEXT:    [[COUNT2:%.*]] = phi i32 [ [[COUNT_JT1]], [[FOR_BODY_JT1:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ]
  28 ; CHECK-NEXT:    br label [[FOR_INC_JT2]]
  29 ; CHECK:       case2:
  30 ; CHECK-NEXT:    [[COUNT1:%.*]] = phi i32 [ [[COUNT_JT2]], [[FOR_BODY_JT2:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ]
  31 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[COUNT1]], 50
  32 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE:%.*]]
  33 ; CHECK:       si.unfold.false:
  34 ; CHECK-NEXT:    br label [[FOR_INC_JT2]]
  35 ; CHECK:       for.inc:
  36 ; CHECK-NEXT:    [[INC]] = add nsw i32 undef, 1
  37 ; CHECK-NEXT:    [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]]
  38 ; CHECK-NEXT:    br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]]
  39 ; CHECK:       for.inc.jt2:
  40 ; CHECK-NEXT:    [[COUNT4:%.*]] = phi i32 [ [[COUNT1]], [[SI_UNFOLD_FALSE]] ], [ [[COUNT2]], [[CASE1]] ]
  41 ; CHECK-NEXT:    [[STATE_NEXT_JT2]] = phi i32 [ 2, [[CASE1]] ], [ 2, [[SI_UNFOLD_FALSE]] ]
  42 ; CHECK-NEXT:    [[INC_JT2]] = add nsw i32 [[COUNT4]], 1
  43 ; CHECK-NEXT:    [[CMP_EXIT_JT2:%.*]] = icmp slt i32 [[INC_JT2]], [[NUM]]
  44 ; CHECK-NEXT:    br i1 [[CMP_EXIT_JT2]], label [[FOR_BODY_JT2]], label [[FOR_END]]
  45 ; CHECK:       for.inc.jt1:
  46 ; CHECK-NEXT:    [[COUNT3:%.*]] = phi i32 [ [[COUNT1]], [[CASE2]] ], [ [[COUNT]], [[FOR_BODY]] ]
  47 ; CHECK-NEXT:    [[STATE_NEXT_JT1]] = phi i32 [ 1, [[CASE2]] ], [ 1, [[FOR_BODY]] ]
  48 ; CHECK-NEXT:    [[INC_JT1]] = add nsw i32 [[COUNT3]], 1
  49 ; CHECK-NEXT:    [[CMP_EXIT_JT1:%.*]] = icmp slt i32 [[INC_JT1]], [[NUM]]
  50 ; CHECK-NEXT:    br i1 [[CMP_EXIT_JT1]], label [[FOR_BODY_JT1]], label [[FOR_END]]
  51 ; CHECK:       for.end:
  52 ; CHECK-NEXT:    ret i32 0
  53 ;
  54 entry:
  55   br label %for.body
  56
  57 for.body:
  58   %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  59   %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
  60   switch i32 %state, label %for.inc [
  61   i32 1, label %case1
  62   i32 2, label %case2
  63   ]
  64
  65 case1:
  66   br label %for.inc
  67
  68 case2:
  69   %cmp = icmp eq i32 %count, 50
  70   %sel = select i1 %cmp, i32 1, i32 2
  71   br label %for.inc
  72
  73 for.inc:
  74   %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
  75   %inc = add nsw i32 %count, 1
  76   %cmp.exit = icmp slt i32 %inc, %num
  77   br i1 %cmp.exit, label %for.body, label %for.end
  78
  79 for.end:
  80   ret i32 0
  81 }
  82
  83
  84 define i32 @test2(i32 %init) {
  85 ; CHECK-LABEL: @test2(
  86 ; CHECK-NEXT:  entry:
  87 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[INIT:%.*]], 0
  88 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1:%.*]], label [[SI_UNFOLD_FALSE1:%.*]]
  89 ; CHECK:       si.unfold.false:
  90 ; CHECK-NEXT:    br label [[LOOP_1]]
  91 ; CHECK:       si.unfold.false.jt2:
  92 ; CHECK-NEXT:    br label [[LOOP_1_JT2:%.*]]
  93 ; CHECK:       si.unfold.false.jt4:
  94 ; CHECK-NEXT:    br label [[LOOP_1_JT4:%.*]]
  95 ; CHECK:       si.unfold.false1:
  96 ; CHECK-NEXT:    br label [[LOOP_1]]
  97 ; CHECK:       loop.1:
  98 ; CHECK-NEXT:    [[STATE_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ undef, [[SI_UNFOLD_FALSE:%.*]] ], [ 2, [[SI_UNFOLD_FALSE1]] ]
  99 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 100 ; CHECK:       loop.1.jt2:
 101 ; CHECK-NEXT:    [[STATE_1_JT2:%.*]] = phi i32 [ [[STATE_1_BE_JT2:%.*]], [[SI_UNFOLD_FALSE_JT2:%.*]] ]
 102 ; CHECK-NEXT:    br label [[LOOP_2_JT2:%.*]]
 103 ; CHECK:       loop.1.jt4:
 104 ; CHECK-NEXT:    [[STATE_1_JT4:%.*]] = phi i32 [ [[STATE_1_BE_JT4:%.*]], [[SI_UNFOLD_FALSE_JT4:%.*]] ]
 105 ; CHECK-NEXT:    br label [[LOOP_2_JT4:%.*]]
 106 ; CHECK:       loop.1.jt1:
 107 ; CHECK-NEXT:    [[STATE_1_JT1:%.*]] = phi i32 [ 1, [[LOOP_1_BACKEDGE:%.*]] ], [ 1, [[LOOP_1_BACKEDGE_JT4:%.*]] ], [ 1, [[LOOP_1_BACKEDGE_JT2:%.*]] ]
 108 ; CHECK-NEXT:    br label [[LOOP_2_JT1:%.*]]
 109 ; CHECK:       loop.2:
 110 ; CHECK-NEXT:    [[STATE_2:%.*]] = phi i32 [ [[STATE_1]], [[LOOP_1]] ], [ undef, [[LOOP_2_BACKEDGE:%.*]] ]
 111 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 112 ; CHECK:       loop.2.jt2:
 113 ; CHECK-NEXT:    [[STATE_2_JT2:%.*]] = phi i32 [ [[STATE_1_JT2]], [[LOOP_1_JT2]] ]
 114 ; CHECK-NEXT:    br label [[LOOP_3_JT2:%.*]]
 115 ; CHECK:       loop.2.jt3:
 116 ; CHECK-NEXT:    [[STATE_2_JT3:%.*]] = phi i32 [ [[STATE_2_BE_JT3:%.*]], [[LOOP_2_BACKEDGE_JT3:%.*]] ]
 117 ; CHECK-NEXT:    br label [[LOOP_3_JT3:%.*]]
 118 ; CHECK:       loop.2.jt0:
 119 ; CHECK-NEXT:    [[STATE_2_JT0:%.*]] = phi i32 [ [[STATE_2_BE_JT0:%.*]], [[LOOP_2_BACKEDGE_JT0:%.*]] ]
 120 ; CHECK-NEXT:    br label [[LOOP_3_JT0:%.*]]
 121 ; CHECK:       loop.2.jt4:
 122 ; CHECK-NEXT:    [[STATE_2_JT4:%.*]] = phi i32 [ [[STATE_1_JT4]], [[LOOP_1_JT4]] ]
 123 ; CHECK-NEXT:    br label [[LOOP_3_JT4:%.*]]
 124 ; CHECK:       loop.2.jt1:
 125 ; CHECK-NEXT:    [[STATE_2_JT1:%.*]] = phi i32 [ [[STATE_1_JT1]], [[LOOP_1_JT1:%.*]] ]
 126 ; CHECK-NEXT:    br label [[LOOP_3_JT1:%.*]]
 127 ; CHECK:       loop.3:
 128 ; CHECK-NEXT:    [[STATE:%.*]] = phi i32 [ [[STATE_2]], [[LOOP_2]] ]
 129 ; CHECK-NEXT:    switch i32 [[STATE]], label [[INFLOOP_I:%.*]] [
 130 ; CHECK-NEXT:    i32 2, label [[CASE2:%.*]]
 131 ; CHECK-NEXT:    i32 3, label [[CASE3:%.*]]
 132 ; CHECK-NEXT:    i32 4, label [[CASE4:%.*]]
 133 ; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
 134 ; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
 135 ; CHECK-NEXT:    ]
 136 ; CHECK:       loop.3.jt2:
 137 ; CHECK-NEXT:    [[STATE_JT2:%.*]] = phi i32 [ [[STATE_2_JT2]], [[LOOP_2_JT2]] ]
 138 ; CHECK-NEXT:    br label [[CASE2]]
 139 ; CHECK:       loop.3.jt0:
 140 ; CHECK-NEXT:    [[STATE_JT0:%.*]] = phi i32 [ [[STATE_2_JT0]], [[LOOP_2_JT0:%.*]] ]
 141 ; CHECK-NEXT:    br label [[CASE0]]
 142 ; CHECK:       loop.3.jt4:
 143 ; CHECK-NEXT:    [[STATE_JT4:%.*]] = phi i32 [ [[STATE_2_JT4]], [[LOOP_2_JT4]] ]
 144 ; CHECK-NEXT:    br label [[CASE4]]
 145 ; CHECK:       loop.3.jt1:
 146 ; CHECK-NEXT:    [[STATE_JT1:%.*]] = phi i32 [ [[STATE_2_JT1]], [[LOOP_2_JT1]] ]
 147 ; CHECK-NEXT:    br label [[CASE1]]
 148 ; CHECK:       loop.3.jt3:
 149 ; CHECK-NEXT:    [[STATE_JT3:%.*]] = phi i32 [ 3, [[CASE2]] ], [ [[STATE_2_JT3]], [[LOOP_2_JT3:%.*]] ]
 150 ; CHECK-NEXT:    br label [[CASE3]]
 151 ; CHECK:       case2:
 152 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_3_JT3]], label [[LOOP_1_BACKEDGE_JT4]]
 153 ; CHECK:       case3:
 154 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_2_BACKEDGE_JT0]], label [[CASE4]]
 155 ; CHECK:       case4:
 156 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_2_BACKEDGE_JT3]], label [[LOOP_1_BACKEDGE_JT2]]
 157 ; CHECK:       loop.1.backedge:
 158 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE]]
 159 ; CHECK:       loop.1.backedge.jt2:
 160 ; CHECK-NEXT:    [[STATE_1_BE_JT2]] = phi i32 [ 2, [[CASE4]] ]
 161 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE_JT2]]
 162 ; CHECK:       loop.1.backedge.jt4:
 163 ; CHECK-NEXT:    [[STATE_1_BE_JT4]] = phi i32 [ 4, [[CASE2]] ]
 164 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE_JT4]]
 165 ; CHECK:       loop.2.backedge:
 166 ; CHECK-NEXT:    br label [[LOOP_2]]
 167 ; CHECK:       loop.2.backedge.jt3:
 168 ; CHECK-NEXT:    [[STATE_2_BE_JT3]] = phi i32 [ 3, [[CASE4]] ]
 169 ; CHECK-NEXT:    br label [[LOOP_2_JT3]]
 170 ; CHECK:       loop.2.backedge.jt0:
 171 ; CHECK-NEXT:    [[STATE_2_BE_JT0]] = phi i32 [ 0, [[CASE3]] ]
 172 ; CHECK-NEXT:    br label [[LOOP_2_JT0]]
 173 ; CHECK:       case0:
 174 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 175 ; CHECK:       case1:
 176 ; CHECK-NEXT:    br label [[EXIT]]
 177 ; CHECK:       infloop.i:
 178 ; CHECK-NEXT:    br label [[INFLOOP_I]]
 179 ; CHECK:       exit:
 180 ; CHECK-NEXT:    ret i32 0
 181 ;
 182 entry:
 183   %cmp = icmp eq i32 %init, 0
 184   %sel = select i1 %cmp, i32 0, i32 2
 185   br label %loop.1
 186
 187 loop.1:
 188   %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
 189   br label %loop.2
 190
 191 loop.2:
 192   %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
 193   br label %loop.3
 194
 195 loop.3:
 196   %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
 197   switch i32 %state, label %infloop.i [
 198   i32 2, label %case2
 199   i32 3, label %case3
 200   i32 4, label %case4
 201   i32 0, label %case0
 202   i32 1, label %case1
 203   ]
 204
 205 case2:
 206   br i1 %cmp, label %loop.3, label %loop.1.backedge
 207
 208 case3:
 209   br i1 %cmp, label %loop.2.backedge, label %case4
 210
 211 case4:
 212   br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
 213
 214 loop.1.backedge:
 215   %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
 216   %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
 217   br label %loop.1
 218
 219 loop.2.backedge:
 220   %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
 221   br label %loop.2
 222
 223 case0:
 224   br label %exit
 225
 226 case1:
 227   br label %exit
 228
 229 infloop.i:
 230   br label %infloop.i
 231
 232 exit:
 233   ret i32 0
 234 }