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 4target 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" 5target 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 124define 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; 136entry: 137 %0 = icmp ult i32 %cond, 3 138 br i1 %0, label %switch.lookup, label %return 139 140switch.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 145return: ; preds = %entry 146 ret ptr @d1 147} 148 149; Relative switch lookup table for integer pointers that have internal linkage 150define 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; 162entry: 163 %0 = icmp ult i32 %cond, 3 164 br i1 %0, label %switch.lookup, label %return 165 166switch.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 171return: ; preds = %entry 172 ret ptr @d2 173} 174 175; ; Relative switch lookup table for strings 176define 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 ; 188entry: 189 %0 = icmp ult i32 %cond, 3 190 br i1 %0, label %switch.lookup, label %return 191 192switch.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 197return: ; 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 202define 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; 214entry: 215 %0 = icmp ult i32 %cond, 4 216 br i1 %0, label %switch.lookup, label %return 217 218switch.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 223return: ; 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 231define 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 244entry: 245 %0 = icmp ult i32 %cond, 3 246 br i1 %0, label %switch.lookup, label %sw.epilog 247 248switch.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 253sw.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 260define 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; 274entry: 275 %cmp = icmp sgt i32 %cond, 3 276 br i1 %cmp, label %cond.end, label %cond.false 277 278cond.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 284cond.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. 292define 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; 305entry: 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 310if.false: 311 %2 = load ptr, ptr %1 312 br label %if.done 313 314if.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() 323declare void @may_not_return() 324 325define 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; 333entry: 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"} 346