test/Transforms/SimplifyCFG/switch_to_lookup_table.ll

   1 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
   2
   3 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
   4 target triple = "x86_64-unknown-linux-gnu"
   5
   6 ; The table for @f
   7 ; CHECK: @switch.table = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1]
   8
   9 ; The float table for @h
  10 ; CHECK: @switch.table1 = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000]
  11
  12 ; The table for @foostring
  13 ; CHECK: @switch.table2 = private unnamed_addr constant [4 x i8*] [i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8]* @.str3, i64 0, i64 0)]
  14
  15 ; The table for @earlyreturncrash
  16 ; CHECK: @switch.table3 = private unnamed_addr constant [4 x i32] [i32 42, i32 9, i32 88, i32 5]
  17
  18 ; A simple int-to-int selection switch.
  19 ; It is dense enough to be replaced by table lookup.
  20 ; The result is directly by a ret from an otherwise empty bb,
  21 ; so we return early, directly from the lookup bb.
  22
  23 define i32 @f(i32 %c) nounwind uwtable readnone {
  24 entry:
  25   switch i32 %c, label %sw.default [
  26     i32 42, label %return
  27     i32 43, label %sw.bb1
  28     i32 44, label %sw.bb2
  29     i32 45, label %sw.bb3
  30     i32 46, label %sw.bb4
  31     i32 47, label %sw.bb5
  32     i32 48, label %sw.bb6
  33   ]
  34
  35 sw.bb1: br label %return
  36 sw.bb2: br label %return
  37 sw.bb3: br label %return
  38 sw.bb4: br label %return
  39 sw.bb5: br label %return
  40 sw.bb6: br label %return
  41 sw.default: br label %return
  42 return:
  43   %retval.0 = phi i32 [ 15, %sw.default ], [ 1, %sw.bb6 ], [ 62, %sw.bb5 ], [ 27, %sw.bb4 ], [ -1, %sw.bb3 ], [ 0, %sw.bb2 ], [ 123, %sw.bb1 ], [ 55, %entry ]
  44   ret i32 %retval.0
  45
  46 ; CHECK: @f
  47 ; CHECK: entry:
  48 ; CHECK-NEXT: %switch.tableidx = sub i32 %c, 42
  49 ; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 7
  50 ; CHECK-NEXT: br i1 %0, label %switch.lookup, label %return
  51 ; CHECK: switch.lookup:
  52 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [7 x i32]* @switch.table, i32 0, i32 %switch.tableidx
  53 ; CHECK-NEXT: %switch.load = load i32* %switch.gep
  54 ; CHECK-NEXT: ret i32 %switch.load
  55 ; CHECK: return:
  56 ; CHECK-NEXT: ret i32 15
  57 }
  58
  59 ; A switch used to initialize two variables, an i8 and a float.
  60
  61 declare void @dummy(i8 signext, float)
  62 define void @h(i32 %x) {
  63 entry:
  64   switch i32 %x, label %sw.default [
  65     i32 0, label %sw.epilog
  66     i32 1, label %sw.bb1
  67     i32 2, label %sw.bb2
  68     i32 3, label %sw.bb3
  69   ]
  70
  71 sw.bb1: br label %sw.epilog
  72 sw.bb2: br label %sw.epilog
  73 sw.bb3: br label %sw.epilog
  74 sw.default: br label %sw.epilog
  75
  76 sw.epilog:
  77   %a.0 = phi i8 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
  78   %b.0 = phi float [ 0x4023FAE140000000, %sw.default ], [ 0x4001AE1480000000, %sw.bb3 ], [ 0x4012449BA0000000, %sw.bb2 ], [ 0x3FF3BE76C0000000, %sw.bb1 ], [ 0x40091EB860000000, %entry ]
  79   call void @dummy(i8 signext %a.0, float %b.0)
  80   ret void
  81
  82 ; CHECK: @h
  83 ; CHECK: entry:
  84 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
  85 ; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 4
  86 ; CHECK-NEXT: br i1 %0, label %switch.lookup, label %sw.epilog
  87 ; CHECK: switch.lookup:
  88 ; CHECK-NEXT: %switch.shiftamt = mul i32 %switch.tableidx, 8
  89 ; CHECK-NEXT: %switch.downshift = lshr i32 89655594, %switch.shiftamt
  90 ; CHECK-NEXT: %switch.masked = trunc i32 %switch.downshift to i8
  91 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x float]* @switch.table1, i32 0, i32 %switch.tableidx
  92 ; CHECK-NEXT: %switch.load = load float* %switch.gep
  93 ; CHECK-NEXT: br label %sw.epilog
  94 ; CHECK: sw.epilog:
  95 ; CHECK-NEXT: %a.0 = phi i8 [ %switch.masked, %switch.lookup ], [ 7, %entry ]
  96 ; CHECK-NEXT: %b.0 = phi float [ %switch.load, %switch.lookup ], [ 0x4023FAE140000000, %entry ]
  97 ; CHECK-NEXT: call void @dummy(i8 signext %a.0, float %b.0)
  98 ; CHECK-NEXT: ret void
  99 }
 100
 101
 102 ; Switch used to return a string.
 103
 104 @.str = private unnamed_addr constant [4 x i8] c"foo\00", align 1
 105 @.str1 = private unnamed_addr constant [4 x i8] c"bar\00", align 1
 106 @.str2 = private unnamed_addr constant [4 x i8] c"baz\00", align 1
 107 @.str3 = private unnamed_addr constant [4 x i8] c"qux\00", align 1
 108 @.str4 = private unnamed_addr constant [6 x i8] c"error\00", align 1
 109
 110 define i8* @foostring(i32 %x)  {
 111 entry:
 112   switch i32 %x, label %sw.default [
 113     i32 0, label %return
 114     i32 1, label %sw.bb1
 115     i32 2, label %sw.bb2
 116     i32 3, label %sw.bb3
 117   ]
 118
 119 sw.bb1: br label %return
 120 sw.bb2: br label %return
 121 sw.bb3: br label %return
 122 sw.default: br label %return
 123
 124 return:
 125   %retval.0 = phi i8* [ getelementptr inbounds ([6 x i8]* @.str4, i64 0, i64 0), %sw.default ],
 126                       [ getelementptr inbounds ([4 x i8]* @.str3, i64 0, i64 0), %sw.bb3 ],
 127                       [ getelementptr inbounds ([4 x i8]* @.str2, i64 0, i64 0), %sw.bb2 ],
 128                       [ getelementptr inbounds ([4 x i8]* @.str1, i64 0, i64 0), %sw.bb1 ],
 129                       [ getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), %entry ]
 130   ret i8* %retval.0
 131
 132 ; CHECK: @foostring
 133 ; CHECK: entry:
 134 ; CHECK-NEXT: %switch.tableidx = sub i32 %x, 0
 135 ; CHECK-NEXT: %0 = icmp ult i32 %switch.tableidx, 4
 136 ; CHECK-NEXT: br i1 %0, label %switch.lookup, label %return
 137 ; CHECK: switch.lookup:
 138 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i8*]* @switch.table2, i32 0, i32 %switch.tableidx
 139 ; CHECK-NEXT: %switch.load = load i8** %switch.gep
 140 ; CHECK-NEXT: ret i8* %switch.load
 141 }
 142
 143 ; Switch used to initialize two values. The first value is returned, the second
 144 ; value is not used. This used to make the transformation generate illegal code.
 145
 146 define i32 @earlyreturncrash(i32 %x)  {
 147 entry:
 148   switch i32 %x, label %sw.default [
 149     i32 0, label %sw.epilog
 150     i32 1, label %sw.bb1
 151     i32 2, label %sw.bb2
 152     i32 3, label %sw.bb3
 153   ]
 154
 155 sw.bb1: br label %sw.epilog
 156 sw.bb2: br label %sw.epilog
 157 sw.bb3: br label %sw.epilog
 158 sw.default: br label %sw.epilog
 159
 160 sw.epilog:
 161   %a.0 = phi i32 [ 7, %sw.default ], [ 5, %sw.bb3 ], [ 88, %sw.bb2 ], [ 9, %sw.bb1 ], [ 42, %entry ]
 162   %b.0 = phi i32 [ 10, %sw.default ], [ 5, %sw.bb3 ], [ 1, %sw.bb2 ], [ 4, %sw.bb1 ], [ 3, %entry ]
 163   ret i32 %a.0
 164
 165 ; CHECK: @earlyreturncrash
 166 ; CHECK: switch.lookup:
 167 ; CHECK-NEXT: %switch.gep = getelementptr inbounds [4 x i32]* @switch.table3, i32 0, i32 %switch.tableidx
 168 ; CHECK-NEXT: %switch.load = load i32* %switch.gep
 169 ; CHECK-NEXT: ret i32 %switch.load
 170 ; CHECK: sw.epilog:
 171 ; CHECK-NEXT: ret i32 7
 172 }
 173
 174
 175 ; Example 7 from http://blog.regehr.org/archives/320
 176 ; It is not dense enough for a regular table, but the results
 177 ; can be packed into a bitmap.
 178
 179 define i32 @crud(i8 zeroext %c)  {
 180 entry:
 181   %cmp = icmp ult i8 %c, 33
 182   br i1 %cmp, label %lor.end, label %switch.early.test
 183
 184 switch.early.test:
 185   switch i8 %c, label %lor.rhs [
 186     i8 92, label %lor.end
 187     i8 62, label %lor.end
 188     i8 60, label %lor.end
 189     i8 59, label %lor.end
 190     i8 58, label %lor.end
 191     i8 46, label %lor.end
 192     i8 44, label %lor.end
 193     i8 34, label %lor.end
 194     i8 39, label %switch.edge
 195   ]
 196
 197 switch.edge: br label %lor.end
 198 lor.rhs: br label %lor.end
 199
 200 lor.end:
 201   %0 = phi i1 [ true, %switch.early.test ],
 202               [ false, %lor.rhs ],
 203               [ true, %entry ],
 204               [ true, %switch.early.test ],
 205               [ true, %switch.early.test ],
 206               [ true, %switch.early.test ],
 207               [ true, %switch.early.test ],
 208               [ true, %switch.early.test ],
 209               [ true, %switch.early.test ],
 210               [ true, %switch.early.test ],
 211               [ true, %switch.edge ]
 212   %lor.ext = zext i1 %0 to i32
 213   ret i32 %lor.ext
 214
 215 ; CHECK: @crud
 216 ; CHECK: entry:
 217 ; CHECK-NEXT: %cmp = icmp ult i8 %c, 33
 218 ; CHECK-NEXT: br i1 %cmp, label %lor.end, label %switch.early.test
 219 ; CHECK: switch.early.test:
 220 ; CHECK-NEXT: %switch.tableidx = sub i8 %c, 34
 221 ; CHECK-NEXT: %0 = icmp ult i8 %switch.tableidx, 59
 222 ; CHECK-NEXT: br i1 %0, label %switch.lookup, label %lor.end
 223 ; CHECK: switch.lookup:
 224 ; CHECK-NEXT: %switch.cast = zext i8 %switch.tableidx to i59
 225 ; CHECK-NEXT: %switch.shiftamt = mul i59 %switch.cast, 1
 226 ; CHECK-NEXT: %switch.downshift = lshr i59 -288230375765830623, %switch.shiftamt
 227 ; CHECK-NEXT: %switch.masked = trunc i59 %switch.downshift to i1
 228 ; CHECK-NEXT: br label %lor.end
 229 ; CHECK: lor.end:
 230 ; CHECK-NEXT: %1 = phi i1 [ true, %entry ], [ %switch.masked, %switch.lookup ], [ false, %switch.early.test ]
 231 ; CHECK-NEXT: %lor.ext = zext i1 %1 to i32
 232 ; CHECK-NEXT: ret i32 %lor.ext
 233 }