llvm/test/Transforms/RelLookupTableConverter/X86/relative_lookup_table.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; REQUIRES: x86-registered-target
   3 ; RUN: opt < %s -passes=rel-lookup-table-converter -relocation-model=pic -S | FileCheck %s
   4 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"
   5 target triple = "x86_64-unknown-linux-gnu"
   6
   7 @.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1
   8 @.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1
   9 @.str.2 = private unnamed_addr constant [4 x i8] c"two\00", align 1
  10 @.str.3 = private unnamed_addr constant [8 x i8] c"default\00", align 1
  11 @.str.4 = private unnamed_addr constant [6 x i8] c"three\00", align 1
  12 @.str.5 = private unnamed_addr constant [5 x i8] c"str1\00", align 1
  13 @.str.6 = private unnamed_addr constant [5 x i8] c"str2\00", align 1
  14 @.str.7 = private unnamed_addr constant [12 x i8] c"singlevalue\00", align 1
  15 @.str.8 = private unnamed_addr constant [2 x i8] c"a\00", align 1
  16 @.str.9 = private unnamed_addr constant [2 x i8] c"b\00", align 1
  17 @.str.10 = private unnamed_addr constant [2 x i8] c"c\00", align 1
  18
  19 @a1 = external global i32, align 4
  20 @b1 = external global i32, align 4
  21 @c1 = external global i32, align 4
  22 @d1 = external global i32, align 4
  23
  24 @a2 = internal constant i32 0, align 4
  25 @b2 = internal constant i32 0, align 4
  26 @c2 = internal constant i32 0, align 4
  27 @d2 = internal constant i32 0, align 4
  28
  29 @switch.table.external_linkage = private unnamed_addr constant [3 x ptr] [ptr @a1, ptr @b1, ptr @c1], align 8
  30
  31 @switch.table.internal_linkage = private unnamed_addr constant [3 x ptr] [ptr @a2, ptr @b2, ptr @c2], align 8
  32
  33 @switch.table.string_table = private unnamed_addr constant [3 x ptr]
  34                              [
  35                               ptr @.str,
  36                               ptr @.str.1,
  37                               ptr @.str.2
  38                              ], align 8
  39
  40 @switch.table.string_table_holes = private unnamed_addr constant [4 x ptr]
  41                                    [
  42                                     ptr @.str,
  43                                     ptr @.str.3,
  44                                     ptr @.str.2,
  45                                     ptr @.str.4
  46                                    ], align 8
  47
  48 @switch.table.single_value = private unnamed_addr constant [3 x ptr]
  49                              [
  50                               ptr @.str,
  51                               ptr @.str.1,
  52                               ptr @.str.2
  53                              ], align 8
  54
  55 @user_defined_lookup_table.table = internal unnamed_addr constant [3 x ptr]
  56                                    [
  57                                     ptr @.str,
  58                                     ptr @.str.1,
  59                                     ptr @.str.2
  60                                    ], align 16
  61
  62 @table = internal constant [2 x ptr] [
  63   ptr @.str.8,
  64   ptr @.str.9
  65 ], align 16
  66
  67 @table2 = internal constant [2 x ptr] [
  68   ptr @.str.8,
  69   ptr @.str.9
  70 ], align 16
  71
  72 ; Lookup table check for integer pointers that have external linkage
  73 ; CHECK: @switch.table.external_linkage = private unnamed_addr constant [3 x ptr] [ptr @a1, ptr @b1, ptr @c1], align
  74
  75 ; Lookup table check for integer pointers that have internal linkage
  76 ; CHECK: @switch.table.internal_linkage.rel = private unnamed_addr constant [3 x i32]
  77 ; CHECK-SAME: [
  78 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @a2 to i64), i64 ptrtoint (ptr @switch.table.internal_linkage.rel to i64)) to i32),
  79 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @b2 to i64), i64 ptrtoint (ptr @switch.table.internal_linkage.rel to i64)) to i32),
  80 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @c2 to i64), i64 ptrtoint (ptr @switch.table.internal_linkage.rel to i64)) to i32)
  81 ; CHECK-SAME: ], align 4
  82
  83 ; Relative switch lookup table for strings
  84 ; CHECK: @switch.table.string_table.rel = private unnamed_addr constant [3 x i32]
  85 ; CHECK-SAME: [
  86 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str to i64), i64 ptrtoint (ptr @switch.table.string_table.rel to i64)) to i32),
  87 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.1 to i64), i64 ptrtoint (ptr @switch.table.string_table.rel to i64)) to i32),
  88 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.2 to i64), i64 ptrtoint (ptr @switch.table.string_table.rel to i64)) to i32)
  89 ; CHECK-SAME: ], align 4
  90
  91 ; Relative switch lookup table for strings with holes, where holes are filled with relative offset to default values
  92 ; CHECK: @switch.table.string_table_holes.rel = private unnamed_addr constant [4 x i32]
  93 ; CHECK-SAME: [
  94 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str to i64), i64 ptrtoint (ptr @switch.table.string_table_holes.rel to i64)) to i32),
  95 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.3 to i64), i64 ptrtoint (ptr @switch.table.string_table_holes.rel to i64)) to i32),
  96 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.2 to i64), i64 ptrtoint (ptr @switch.table.string_table_holes.rel to i64)) to i32),
  97 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.4 to i64), i64 ptrtoint (ptr @switch.table.string_table_holes.rel to i64)) to i32)
  98 ; CHECK-SAME: ], align 4
  99
 100 ; Single value check
 101 ; CHECK: @switch.table.single_value.rel = private unnamed_addr constant [3 x i32]
 102 ; CHECK-SAME: [
 103 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str to i64), i64 ptrtoint (ptr @switch.table.single_value.rel to i64)) to i32),
 104 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.1 to i64), i64 ptrtoint (ptr @switch.table.single_value.rel to i64)) to i32),
 105 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.2 to i64), i64 ptrtoint (ptr @switch.table.single_value.rel to i64)) to i32)
 106 ; CHECK-SAME: ], align 4
 107 ;
 108
 109 ; Relative lookup table for the loop hoist check test
 110 ; CHECK: @table.rel = internal unnamed_addr constant [2 x i32]
 111 ; CHECK-SAME: [
 112 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.8 to i64), i64 ptrtoint (ptr @table.rel to i64)) to i32),
 113 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.9 to i64), i64 ptrtoint (ptr @table.rel to i64)) to i32)
 114 ; CHECK-SAME: ], align 4
 115
 116 ; Relative look up table for the test where gep is not immediately followed by a load check
 117 ; CHECK: @table2.rel = internal unnamed_addr constant [2 x i32]
 118 ; CHECK-SAME: [
 119 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.8 to i64), i64 ptrtoint (ptr @table2.rel to i64)) to i32),
 120 ; CHECK-SAME: i32 trunc (i64 sub (i64 ptrtoint (ptr @.str.9 to i64), i64 ptrtoint (ptr @table2.rel to i64)) to i32)
 121 ; CHECK-SAME: ], align 4
 122
 123 ; Lookup table check for integer pointers that have external linkage
 124 define ptr @external_linkage(i32 %cond) {
 125 ; CHECK-LABEL: @external_linkage(
 126 ; CHECK-NEXT:  entry:
 127 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3
 128 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 129 ; CHECK:       switch.lookup:
 130 ; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x ptr], ptr @switch.table.external_linkage, i32 0, i32 [[COND:%.*]]
 131 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load ptr, ptr [[SWITCH_GEP]], align 8
 132 ; CHECK-NEXT:    ret ptr [[SWITCH_LOAD]]
 133 ; CHECK:       return:
 134 ; CHECK-NEXT:    ret ptr @d1
 135 ;
 136 entry:
 137   %0 = icmp ult i32 %cond, 3
 138   br i1 %0, label %switch.lookup, label %return
 139
 140 switch.lookup:                                    ; preds = %entry
 141   %switch.gep = getelementptr inbounds [3 x ptr], ptr @switch.table.external_linkage, i32 0, i32 %cond
 142   %switch.load = load ptr, ptr %switch.gep, align 8
 143   ret ptr %switch.load
 144
 145 return:                                           ; preds = %entry
 146   ret ptr @d1
 147 }
 148
 149 ; Relative switch lookup table for integer pointers that have internal linkage
 150 define ptr @internal_linkage(i32 %cond) {
 151 ; CHECK-LABEL: @internal_linkage(
 152 ; CHECK-NEXT:  entry:
 153 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3
 154 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 155 ; CHECK:       switch.lookup:
 156 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 %cond, 2
 157 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @switch.table.internal_linkage.rel, i32 [[RELTABLE_SHIFT]])
 158 ; CHECK-NEXT:    ret ptr [[RELTABLE_INTRINSIC]]
 159 ; CHECK:       return:
 160 ; CHECK-NEXT:    ret ptr @d2
 161 ;
 162 entry:
 163   %0 = icmp ult i32 %cond, 3
 164   br i1 %0, label %switch.lookup, label %return
 165
 166 switch.lookup:                                    ; preds = %entry
 167   %switch.gep = getelementptr inbounds [3 x ptr], ptr @switch.table.internal_linkage, i32 0, i32 %cond
 168   %switch.load = load ptr, ptr %switch.gep, align 8
 169   ret ptr %switch.load
 170
 171 return:                                           ; preds = %entry
 172   ret ptr @d2
 173 }
 174
 175 ; ; Relative switch lookup table for strings
 176 define ptr @string_table(i32 %cond) {
 177   ; CHECK-LABEL: @string_table(
 178   ; CHECK-NEXT:  entry:
 179   ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3
 180   ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 181   ; CHECK:       switch.lookup:
 182   ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 %cond, 2
 183   ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @switch.table.string_table.rel, i32 [[RELTABLE_SHIFT]])
 184   ; CHECK-NEXT:    ret ptr [[RELTABLE_INTRINSIC]]
 185   ; CHECK:       return:
 186   ; CHECK-NEXT:    ret ptr @.str.3
 187   ;
 188 entry:
 189   %0 = icmp ult i32 %cond, 3
 190   br i1 %0, label %switch.lookup, label %return
 191
 192 switch.lookup:                                    ; preds = %entry
 193   %switch.gep = getelementptr inbounds [3 x ptr], ptr @switch.table.string_table, i32 0, i32 %cond
 194   %switch.load = load ptr, ptr %switch.gep, align 8
 195   ret ptr %switch.load
 196
 197 return:                                           ; preds = %entry
 198   ret ptr @.str.3
 199 }
 200
 201 ; Relative switch lookup table for strings with holes, where holes are filled with relative offset to default values
 202 define ptr @string_table_holes(i32 %cond) {
 203 ; CHECK-LABEL: @string_table_holes(
 204 ; CHECK-NEXT:  entry:
 205 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 4
 206 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 207 ; CHECK:       switch.lookup:
 208 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 [[COND]], 2
 209 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @switch.table.string_table_holes.rel, i32 [[RELTABLE_SHIFT]])
 210 ; CHECK-NEXT:    ret ptr [[RELTABLE_INTRINSIC]]
 211 ; CHECK:       return:
 212 ; CHECK-NEXT:    ret ptr @.str.3
 213 ;
 214 entry:
 215   %0 = icmp ult i32 %cond, 4
 216   br i1 %0, label %switch.lookup, label %return
 217
 218 switch.lookup:                                    ; preds = %entry
 219   %switch.gep = getelementptr inbounds [4 x ptr], ptr @switch.table.string_table_holes, i32 0, i32 %cond
 220   %switch.load = load ptr, ptr %switch.gep, align 8
 221   ret ptr %switch.load
 222
 223 return:                                           ; preds = %entry
 224   ret ptr @.str.3
 225 }
 226
 227
 228 ; Single value check
 229 ; If there is a lookup table, where each element contains the same value,
 230 ; a relative lookup should not be generated
 231 define void @single_value(i32 %cond)  {
 232 ; CHECK-LABEL: @single_value(
 233 ; CHECK-NEXT:  entry:
 234 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3
 235 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 236 ; CHECK:       switch.lookup:
 237 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 [[COND]], 2
 238 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @switch.table.single_value.rel, i32 [[RELTABLE_SHIFT]])
 239 ; CHECK:       sw.epilog:
 240 ; CHECK-NEXT:   [[STR1:%.*]] = phi ptr [ @.str.5, %entry ], [ @.str.7, %switch.lookup ]
 241 ; CHECK-NEXT:   [[STR2:%.*]] = phi ptr [ @.str.6, %entry ], [ [[RELTABLE_INTRINSIC]], [[SWITCH_LOOKUP]] ]
 242 ; CHECK-NEXT:    ret void
 243
 244 entry:
 245   %0 = icmp ult i32 %cond, 3
 246   br i1 %0, label %switch.lookup, label %sw.epilog
 247
 248 switch.lookup:                                    ; preds = %entry
 249   %switch.gep = getelementptr inbounds [3 x ptr], ptr @switch.table.single_value, i32 0, i32 %cond
 250   %switch.load = load ptr, ptr %switch.gep, align 8
 251   br label %sw.epilog
 252
 253 sw.epilog:                                        ; preds = %switch.lookup, %entry
 254   %str1.0 = phi ptr [ @.str.5, %entry ], [ @.str.7, %switch.lookup ]
 255   %str2.0 = phi ptr [ @.str.6, %entry ], [ %switch.load, %switch.lookup ]
 256   ret void
 257 }
 258
 259 ; Relative lookup table generated for a user-defined lookup table
 260 define ptr @user_defined_lookup_table(i32 %cond)  {
 261 ; CHECK-LABEL: @user_defined_lookup_table(
 262 ; CHECK-NEXT:  entry:
 263 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[COND:%.*]], 3
 264 ; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
 265 ; CHECK:       cond.false:
 266 ; CHECK-NEXT:    [[IDX_PROM:%.*]] = sext i32 [[COND]] to i64
 267 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i64 [[IDX_PROM]], 2
 268 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i64(ptr @user_defined_lookup_table.table.rel, i64 [[RELTABLE_SHIFT]])
 269 ; CHECK-NEXT:    br label %cond.end
 270 ; CHECK:       cond.end:
 271 ; CHECK-NEXT:    [[COND1:%.*]] = phi ptr [ [[RELTABLE_INTRINSIC]], %cond.false ], [ @.str.3, %entry ]
 272 ; CHECK-NEXT:    ret ptr [[COND1]]
 273 ;
 274 entry:
 275   %cmp = icmp sgt i32 %cond, 3
 276   br i1 %cmp, label %cond.end, label %cond.false
 277
 278 cond.false:                                       ; preds = %entry
 279   %idxprom = sext i32 %cond to i64
 280   %arrayidx = getelementptr inbounds [3 x ptr], ptr @user_defined_lookup_table.table, i64 0, i64 %idxprom
 281   %0 = load ptr, ptr %arrayidx, align 8, !tbaa !4
 282   br label %cond.end
 283
 284 cond.end:                                         ; preds = %entry, %cond.false
 285   %cond1 = phi ptr [ %0, %cond.false ], [ @.str.3, %entry ]
 286   ret ptr %cond1
 287 }
 288
 289 ; Check to ensure that call @llvm.load.relative is inserted before load, not before gep.
 290 ; When a lookup table is accessed inside a loop, and a gep is hosted outside the loop via licm,
 291 ; make sure that call @llvm.load.relative is inserted before load.
 292 define ptr @loop_hoist(i32 %x) {
 293 ; CHECK-LABEL: @loop_hoist(i32 %x)
 294 ; CHECK-NEXT:  entry:
 295 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 1
 296 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 [[X:%.*]], 2
 297 ; CHECK-NEXT:    br i1 [[TMP0]], label %if.done, label %if.false
 298 ; CHECK:       if.false:
 299 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @table.rel, i32 [[RELTABLE_SHIFT]])
 300 ; CHECK-NEXT:    br label %if.done
 301 ; CHECK:       if.done:
 302 ; CHECK-NEXT:    [[TMP2:%.*]] = phi ptr [ @.str.10, %entry ], [ [[RELTABLE_INTRINSIC]], %if.false ]
 303 ; CHECK-NEXT:    ret ptr [[TMP2]]
 304 ;
 305 entry:
 306   %0 = icmp sgt i32 %x, 1
 307   %1 = getelementptr [2 x ptr], ptr @table, i32 0, i32 %x
 308   br i1 %0, label %if.done, label %if.false
 309
 310 if.false:
 311   %2 = load ptr, ptr %1
 312   br label %if.done
 313
 314 if.done:
 315   %3 = phi ptr [ @.str.10, %entry ], [ %2, %if.false ]
 316   ret ptr %3
 317 }
 318
 319 ; Another check to ensure that call @llvm.load.relative is inserted before load but not before gep.
 320 ; When a lookup table is accessed, and gep is not immediately followed by a load (like if there is a function call
 321 ; or an exception in between), make sure that call @llvm.load.relative is inserted before load.
 322 ; CHECK-LABEL: @may_not_return()
 323 declare void @may_not_return()
 324
 325 define ptr @gep_is_not_imm_followed_by_load(i32 %x) {
 326 ; CHECK-LABEL: @gep_is_not_imm_followed_by_load(i32 %x)
 327 ; CHECK:       entry:
 328 ; CHECK-NEXT:    [[RELTABLE_SHIFT:%.*]] = shl i32 [[X:%.*]], 2
 329 ; CHECK-NEXT:    call void @may_not_return()
 330 ; CHECK-NEXT:    [[RELTABLE_INTRINSIC:%.*]] = call ptr @llvm.load.relative.i32(ptr @table2.rel, i32 [[RELTABLE_SHIFT]])
 331 ; CHECK-NEXT:    ret ptr [[RELTABLE_INTRINSIC]]
 332 ;
 333 entry:
 334   %0 = getelementptr [2 x ptr], ptr @table2, i32 0, i32 %x
 335   call void @may_not_return()
 336   %1 = load ptr, ptr %0
 337   ret ptr %1
 338 }
 339
 340 !llvm.module.flags = !{!0, !1}
 341 !0 = !{i32 7, !"PIC Level", i32 2}
 342 !1 = !{i32 1, !"Code Model", i32 1}
 343 !4 = !{!"any pointer", !5, i64 0}
 344 !5 = !{!"omnipotent char", !6, i64 0}
 345 !6 = !{!"Simple C/C++ TBAA"}