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

   1 ; REQUIRES: asserts
   2 ; RUN: opt -S -passes=dfa-jump-threading -debug-only=dfa-jump-threading -disable-output %s 2>&1 | FileCheck %s
   3
   4 ; This test checks that the analysis identifies all threadable paths in a
   5 ; simple CFG. A threadable path includes a list of basic blocks, the exit
   6 ; state, and the block that determines the next state.
   7 ; < path of BBs that form a cycle > [ state, determinator ]
   8 define i32 @test1(i32 %num) {
   9 ; CHECK: < for.body for.inc > [ 1, for.inc ]
  10 ; CHECK-NEXT: < for.body case1 for.inc > [ 2, for.inc ]
  11 ; CHECK-NEXT: < for.body case2 for.inc > [ 1, for.inc ]
  12 ; CHECK-NEXT: < for.body case2 si.unfold.false for.inc > [ 2, for.inc ]
  13 entry:
  14   br label %for.body
  15
  16 for.body:
  17   %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  18   %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
  19   switch i32 %state, label %for.inc [
  20     i32 1, label %case1
  21     i32 2, label %case2
  22   ]
  23
  24 case1:
  25   br label %for.inc
  26
  27 case2:
  28   %cmp = icmp eq i32 %count, 50
  29   %sel = select i1 %cmp, i32 1, i32 2
  30   br label %for.inc
  31
  32 for.inc:
  33   %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
  34   %inc = add nsw i32 %count, 1
  35   %cmp.exit = icmp slt i32 %inc, %num
  36   br i1 %cmp.exit, label %for.body, label %for.end
  37
  38 for.end:
  39   ret i32 0
  40 }
  41
  42 ; This test checks that the analysis finds threadable paths in a more
  43 ; complicated CFG. Here the FSM is represented as a nested loop, with
  44 ; fallthrough cases.
  45 define i32 @test2(i32 %init) {
  46 ; CHECK: < loop.3 case2 > [ 3, loop.3 ]
  47 ; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
  48 ; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 4, loop.1.backedge ]
  49 ; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 0, loop.2.backedge ]
  50 ; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
  51 ; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
  52 ; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
  53 ; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
  54 ; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
  55 ; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
  56 entry:
  57   %cmp = icmp eq i32 %init, 0
  58   %sel = select i1 %cmp, i32 0, i32 2
  59   br label %loop.1
  60
  61 loop.1:
  62   %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
  63   br label %loop.2
  64
  65 loop.2:
  66   %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
  67   br label %loop.3
  68
  69 loop.3:
  70   %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
  71   switch i32 %state, label %infloop.i [
  72     i32 2, label %case2
  73     i32 3, label %case3
  74     i32 4, label %case4
  75     i32 0, label %case0
  76     i32 1, label %case1
  77   ]
  78
  79 case2:
  80   br i1 %cmp, label %loop.3, label %loop.1.backedge
  81
  82 case3:
  83   br i1 %cmp, label %loop.2.backedge, label %case4
  84
  85 case4:
  86   br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
  87
  88 loop.1.backedge:
  89   %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
  90   %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
  91   br label %loop.1
  92
  93 loop.2.backedge:
  94   %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
  95   br label %loop.2
  96
  97 case0:
  98   br label %exit
  99
 100 case1:
 101   br label %exit
 102
 103 infloop.i:
 104   br label %infloop.i
 105
 106 exit:
 107   ret i32 0
 108 }
 109
 110 declare void @baz()
 111
 112 ; Do not jump-thread those paths where the determinator basic block does not
 113 ; precede the basic block that defines the switch condition.
 114 ;
 115 ; Otherwise, it is possible that the state defined in the determinator block
 116 ; defines the state for the next iteration of the loop, rather than for the
 117 ; current one.
 118 define i32 @wrong_bb_order() {
 119 ; CHECK-LABEL: DFA Jump threading: wrong_bb_order
 120 ; CHECK-NOT: < bb43 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
 121 ; CHECK-NOT: < bb43 bb49 bb59 bb3 bb31 bb41 > [ 77, bb43 ]
 122 bb:
 123   %i = alloca [420 x i8], align 1
 124   %i2 = getelementptr inbounds [420 x i8], ptr %i, i64 0, i64 390
 125   br label %bb3
 126
 127 bb3:                                              ; preds = %bb59, %bb
 128   %i4 = phi ptr [ %i2, %bb ], [ %i60, %bb59 ]
 129   %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]
 130   %i6 = phi i32 [ 2, %bb ], [ %i63, %bb59 ]
 131   %i7 = phi i32 [ 26, %bb ], [ %i62, %bb59 ]
 132   %i8 = phi i32 [ 25, %bb ], [ %i61, %bb59 ]
 133   %i9 = icmp sgt i32 %i7, 2
 134   %i10 = select i1 %i9, i32 %i7, i32 2
 135   %i11 = add i32 %i8, 2
 136   %i12 = sub i32 %i11, %i10
 137   %i13 = mul nsw i32 %i12, 3
 138   %i14 = add nsw i32 %i13, %i6
 139   %i15 = sext i32 %i14 to i64
 140   %i16 = getelementptr inbounds i8, ptr %i4, i64 %i15
 141   %i17 = load i8, ptr %i16, align 1
 142   %i18 = icmp sgt i8 %i17, 0
 143   br i1 %i18, label %bb21, label %bb31
 144
 145 bb21:                                             ; preds = %bb3
 146   br i1 true, label %bb59, label %bb43
 147
 148 bb59:                                             ; preds = %bb49, %bb43, %bb31, %bb21
 149   %i60 = phi ptr [ %i44, %bb49 ], [ %i44, %bb43 ], [ %i34, %bb31 ], [ %i4, %bb21 ]
 150   %i61 = phi i32 [ %i45, %bb49 ], [ %i45, %bb43 ], [ %i33, %bb31 ], [ %i8, %bb21 ]
 151   %i62 = phi i32 [ %i47, %bb49 ], [ %i47, %bb43 ], [ %i32, %bb31 ], [ %i7, %bb21 ]
 152   %i63 = phi i32 [ %i48, %bb49 ], [ %i48, %bb43 ], [ 2, %bb31 ], [ %i6, %bb21 ]
 153   %i64 = phi i8 [ %i46, %bb49 ], [ %i46, %bb43 ], [ 77, %bb31 ], [ %i5, %bb21 ]
 154   %i65 = icmp sgt i32 %i62, 0
 155   br i1 %i65, label %bb3, label %bb66
 156
 157 bb31:                                             ; preds = %bb3
 158   %i32 = add nsw i32 %i7, -1
 159   %i33 = add nsw i32 %i8, -1
 160   %i34 = getelementptr inbounds i8, ptr %i4, i64 -15
 161   %i35 = icmp eq i8 %i5, 77
 162   br i1 %i35, label %bb59, label %bb41
 163
 164 bb41:                                             ; preds = %bb31
 165   tail call void @baz()
 166   br label %bb43
 167
 168 bb43:                                             ; preds = %bb41, %bb21
 169   %i44 = phi ptr [ %i34, %bb41 ], [ %i4, %bb21 ]
 170   %i45 = phi i32 [ %i33, %bb41 ], [ %i8, %bb21 ]
 171   %i46 = phi i8 [ 77, %bb41 ], [ %i5, %bb21 ]
 172   %i47 = phi i32 [ %i32, %bb41 ], [ %i7, %bb21 ]
 173   %i48 = phi i32 [ 2, %bb41 ], [ %i6, %bb21 ]
 174   tail call void @baz()
 175   switch i8 %i5, label %bb59 [
 176     i8 68, label %bb49
 177     i8 73, label %bb49
 178   ]
 179
 180 bb49:                                             ; preds = %bb43, %bb43
 181   tail call void @baz()
 182   br label %bb59
 183
 184 bb66:                                             ; preds = %bb59
 185   ret i32 0
 186 }
 187
 188 ; Value %init is not predictable but it's okay since it is the value initial to the switch.
 189 define i32 @initial.value.positive1(i32 %init) {
 190 ; CHECK: < loop.3 case2 > [ 3, loop.3 ]
 191 ; CHECK-NEXT: < loop.3 case2 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
 192 ; CHECK-NEXT: < loop.3 case2 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 4, loop.1.backedge ]
 193 ; CHECK-NEXT: < loop.3 case3 loop.2.backedge loop.2 > [ 0, loop.2.backedge ]
 194 ; CHECK-NEXT: < loop.3 case3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
 195 ; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
 196 ; CHECK-NEXT: < loop.3 case3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
 197 ; CHECK-NEXT: < loop.3 case4 loop.2.backedge loop.2 > [ 3, loop.2.backedge ]
 198 ; CHECK-NEXT: < loop.3 case4 loop.1.backedge loop.1 loop.2 > [ 1, loop.1 ]
 199 ; CHECK-NEXT: < loop.3 case4 loop.1.backedge si.unfold.false loop.1 loop.2 > [ 2, loop.1.backedge ]
 200 entry:
 201   %cmp = icmp eq i32 %init, 0
 202   br label %loop.1
 203
 204 loop.1:
 205   %state.1 = phi i32 [ %init, %entry ], [ %state.1.be2, %loop.1.backedge ]
 206   br label %loop.2
 207
 208 loop.2:
 209   %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
 210   br label %loop.3
 211
 212 loop.3:
 213   %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
 214   switch i32 %state, label %infloop.i [
 215     i32 2, label %case2
 216     i32 3, label %case3
 217     i32 4, label %case4
 218     i32 0, label %case0
 219     i32 1, label %case1
 220   ]
 221
 222 case2:
 223   br i1 %cmp, label %loop.3, label %loop.1.backedge
 224
 225 case3:
 226   br i1 %cmp, label %loop.2.backedge, label %case4
 227
 228 case4:
 229   br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
 230
 231 loop.1.backedge:
 232   %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
 233   %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
 234   br label %loop.1
 235
 236 loop.2.backedge:
 237   %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
 238   br label %loop.2
 239
 240 case0:
 241   br label %exit
 242
 243 case1:
 244   br label %exit
 245
 246 infloop.i:
 247   br label %infloop.i
 248
 249 exit:
 250   ret i32 0
 251 }