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: < case2 for.inc for.body > [ 1, for.inc ]
  10 ; CHECK-NEXT: < for.inc for.body > [ 1, for.inc ]
  11 ; CHECK-NEXT: < case1 for.inc for.body > [ 2, for.inc ]
  12 ; CHECK-NEXT: < case2 sel.si.unfold.false for.inc for.body > [ 2, sel.si.unfold.false ]
  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.1.backedge loop.1 loop.2 loop.3 > [ 1, loop.1 ]
  47 ; CHECK-NEXT: < case4 loop.1.backedge state.1.be2.si.unfold.false loop.1 loop.2 loop.3 > [ 2, loop.1.backedge ]
  48 ; CHECK-NEXT: < case2 loop.1.backedge state.1.be2.si.unfold.false loop.1 loop.2 loop.3 > [ 4, loop.1.backedge ]
  49 ; CHECK-NEXT: < case4 loop.2.backedge loop.2 loop.3 > [ 3, loop.2.backedge ]
  50 ; CHECK-NEXT: < case3 loop.2.backedge loop.2 loop.3 > [ 0, loop.2.backedge ]
  51 ; CHECK-NEXT: < case2 loop.3 > [ 3, loop.3 ]
  52 entry:
  53   %cmp = icmp eq i32 %init, 0
  54   %sel = select i1 %cmp, i32 0, i32 2
  55   br label %loop.1
  56
  57 loop.1:
  58   %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
  59   br label %loop.2
  60
  61 loop.2:
  62   %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
  63   br label %loop.3
  64
  65 loop.3:
  66   %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
  67   switch i32 %state, label %infloop.i [
  68     i32 2, label %case2
  69     i32 3, label %case3
  70     i32 4, label %case4
  71     i32 0, label %case0
  72     i32 1, label %case1
  73   ]
  74
  75 case2:
  76   br i1 %cmp, label %loop.3, label %loop.1.backedge
  77
  78 case3:
  79   br i1 %cmp, label %loop.2.backedge, label %case4
  80
  81 case4:
  82   br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
  83
  84 loop.1.backedge:
  85   %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
  86   %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
  87   br label %loop.1
  88
  89 loop.2.backedge:
  90   %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
  91   br label %loop.2
  92
  93 case0:
  94   br label %exit
  95
  96 case1:
  97   br label %exit
  98
  99 infloop.i:
 100   br label %infloop.i
 101
 102 exit:
 103   ret i32 0
 104 }
 105
 106 declare void @baz()
 107
 108 ; Do not jump-thread those paths where the determinator basic block does not
 109 ; precede the basic block that defines the switch condition.
 110 ;
 111 ; Otherwise, it is possible that the state defined in the determinator block
 112 ; defines the state for the next iteration of the loop, rather than for the
 113 ; current one.
 114 define i32 @wrong_bb_order() {
 115 ; CHECK-LABEL: DFA Jump threading: wrong_bb_order
 116 ; CHECK-NOT: [ 77, bb43 ]
 117 ; CHECK-NOT: [ 77, bb43 ]
 118 bb:
 119   %i = alloca [420 x i8], align 1
 120   %i2 = getelementptr inbounds [420 x i8], ptr %i, i64 0, i64 390
 121   br label %bb3
 122
 123 bb3:                                              ; preds = %bb59, %bb
 124   %i4 = phi ptr [ %i2, %bb ], [ %i60, %bb59 ]
 125   %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]
 126   %i6 = phi i32 [ 2, %bb ], [ %i63, %bb59 ]
 127   %i7 = phi i32 [ 26, %bb ], [ %i62, %bb59 ]
 128   %i8 = phi i32 [ 25, %bb ], [ %i61, %bb59 ]
 129   %i9 = icmp sgt i32 %i7, 2
 130   %i10 = select i1 %i9, i32 %i7, i32 2
 131   %i11 = add i32 %i8, 2
 132   %i12 = sub i32 %i11, %i10
 133   %i13 = mul nsw i32 %i12, 3
 134   %i14 = add nsw i32 %i13, %i6
 135   %i15 = sext i32 %i14 to i64
 136   %i16 = getelementptr inbounds i8, ptr %i4, i64 %i15
 137   %i17 = load i8, ptr %i16, align 1
 138   %i18 = icmp sgt i8 %i17, 0
 139   br i1 %i18, label %bb21, label %bb31
 140
 141 bb21:                                             ; preds = %bb3
 142   br i1 true, label %bb59, label %bb43
 143
 144 bb59:                                             ; preds = %bb49, %bb43, %bb31, %bb21
 145   %i60 = phi ptr [ %i44, %bb49 ], [ %i44, %bb43 ], [ %i34, %bb31 ], [ %i4, %bb21 ]
 146   %i61 = phi i32 [ %i45, %bb49 ], [ %i45, %bb43 ], [ %i33, %bb31 ], [ %i8, %bb21 ]
 147   %i62 = phi i32 [ %i47, %bb49 ], [ %i47, %bb43 ], [ %i32, %bb31 ], [ %i7, %bb21 ]
 148   %i63 = phi i32 [ %i48, %bb49 ], [ %i48, %bb43 ], [ 2, %bb31 ], [ %i6, %bb21 ]
 149   %i64 = phi i8 [ %i46, %bb49 ], [ %i46, %bb43 ], [ 77, %bb31 ], [ %i5, %bb21 ]
 150   %i65 = icmp sgt i32 %i62, 0
 151   br i1 %i65, label %bb3, label %bb66
 152
 153 bb31:                                             ; preds = %bb3
 154   %i32 = add nsw i32 %i7, -1
 155   %i33 = add nsw i32 %i8, -1
 156   %i34 = getelementptr inbounds i8, ptr %i4, i64 -15
 157   %i35 = icmp eq i8 %i5, 77
 158   br i1 %i35, label %bb59, label %bb41
 159
 160 bb41:                                             ; preds = %bb31
 161   tail call void @baz()
 162   br label %bb43
 163
 164 bb43:                                             ; preds = %bb41, %bb21
 165   %i44 = phi ptr [ %i34, %bb41 ], [ %i4, %bb21 ]
 166   %i45 = phi i32 [ %i33, %bb41 ], [ %i8, %bb21 ]
 167   %i46 = phi i8 [ 77, %bb41 ], [ %i5, %bb21 ]
 168   %i47 = phi i32 [ %i32, %bb41 ], [ %i7, %bb21 ]
 169   %i48 = phi i32 [ 2, %bb41 ], [ %i6, %bb21 ]
 170   tail call void @baz()
 171   switch i8 %i5, label %bb59 [
 172     i8 68, label %bb49
 173     i8 73, label %bb49
 174   ]
 175
 176 bb49:                                             ; preds = %bb43, %bb43
 177   tail call void @baz()
 178   br label %bb59
 179
 180 bb66:                                             ; preds = %bb59
 181   ret i32 0
 182 }
 183
 184 ; Value %init is not predictable but it's okay since it is the value initial to the switch.
 185 define i32 @initial.value.positive1(i32 %init) {
 186 ; CHECK: < loop.1.backedge loop.1 loop.2 loop.3 > [ 1, loop.1 ]
 187 ; CHECK-NEXT: < case4 loop.1.backedge state.1.be2.si.unfold.false loop.1 loop.2 loop.3 > [ 2, loop.1.backedge ]
 188 ; CHECK-NEXT: < case2 loop.1.backedge state.1.be2.si.unfold.false loop.1 loop.2 loop.3 > [ 4, loop.1.backedge ]
 189 ; CHECK-NEXT: < case4 loop.2.backedge loop.2 loop.3 > [ 3, loop.2.backedge ]
 190 ; CHECK-NEXT: < case3 loop.2.backedge loop.2 loop.3 > [ 0, loop.2.backedge ]
 191 ; CHECK-NEXT: < case2 loop.3 > [ 3, loop.3 ]
 192 entry:
 193   %cmp = icmp eq i32 %init, 0
 194   br label %loop.1
 195
 196 loop.1:
 197   %state.1 = phi i32 [ %init, %entry ], [ %state.1.be2, %loop.1.backedge ]
 198   br label %loop.2
 199
 200 loop.2:
 201   %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
 202   br label %loop.3
 203
 204 loop.3:
 205   %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
 206   switch i32 %state, label %infloop.i [
 207     i32 2, label %case2
 208     i32 3, label %case3
 209     i32 4, label %case4
 210     i32 0, label %case0
 211     i32 1, label %case1
 212   ]
 213
 214 case2:
 215   br i1 %cmp, label %loop.3, label %loop.1.backedge
 216
 217 case3:
 218   br i1 %cmp, label %loop.2.backedge, label %case4
 219
 220 case4:
 221   br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge
 222
 223 loop.1.backedge:
 224   %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
 225   %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
 226   br label %loop.1
 227
 228 loop.2.backedge:
 229   %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
 230   br label %loop.2
 231
 232 case0:
 233   br label %exit
 234
 235 case1:
 236   br label %exit
 237
 238 infloop.i:
 239   br label %infloop.i
 240
 241 exit:
 242   ret i32 0
 243 }