diff --git a/clang/test/CodeGen/switch-to-lookup-table.c b/clang/test/CodeGen/switch-to-lookup-table.c new file mode 100644 --- /dev/null +++ b/clang/test/CodeGen/switch-to-lookup-table.c @@ -0,0 +1,58 @@ +// Check switch to lookup optimization in fPIC and fno-PIC mode +// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fno-PIC -S -emit-llvm -o - | FileCheck %s --check-prefix=CHECK --check-prefix=FNOPIC +// RUN: %clang_cc1 %s -triple=aarch64-unknown-fuchsia -O2 -fPIC -S -emit-llvm -o - | FileCheck %s --check-prefix=CHECK --check-prefix=FPIC + +// Switch lookup table +// FNOPIC: @switch.table.string_table = private unnamed_addr constant [9 x i8*] [i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str.3, i64 0, i64 0), i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.4, i64 0, i64 0), i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.5, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.6, i64 0, i64 0), i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str.7, i64 0, i64 0), i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str.8, i64 0, i64 0)], align 8 + +// Relative switch lookup table +// FPIC: @switch.reltable.string_table = private unnamed_addr constant [9 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.3 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.4 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.5 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.6 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.7 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.8 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32)], align 4 + +char* string_table(int cond) +{ + // FNOPIC-LABEL: @string_table( + // FNOPIC-NEXT: entry: + // FNOPIC-NEXT: [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 9 + // FNOPIC-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] + // FNOPIC: switch.lookup: + // FNOPIC-NEXT: [[TMP1:%.*]] = sext i32 %cond to i64 + // FNOPIC-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8*], [9 x i8*]* @switch.table.string_table, i64 0, i64 [[TMP1]] + // FNOPIC-NEXT: [[SWITCH_LOAD:%.*]] = load i8*, i8** [[SWITCH_GEP]], align 8 + // FNOPIC-NEXT: ret i8* [[SWITCH_LOAD]] + // FNOPIC: return: + // FNOPIC-NEXT: ret i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0) + + // FPIC-LABEL: @string_table( + // FPIC-NEXT: entry: + // FPIC-NEXT: [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 9 + // FPIC-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] + // FPIC: switch.lookup: + // FPIC-NEXT: [[SWITCH_RELTABLE_SHIFT:%.*]] = lshr i32 %cond, 2 + // FPIC-NEXT: [[SWITCH_RELTABLE_INTRINSIC:%.*]] = call i8* @llvm.load.relative.i32(i8* bitcast ([9 x i32]* @switch.reltable.string_table to i8*), i32 [[SWITCH_RELTABLE_SHIFT]]) + // FPIC-NEXT: ret i8* [[SWITCH_RELTABLE_INTRINSIC]] + // FPIC: return: + // FPIC-NEXT: ret i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0) + + switch (cond) { + case 0: + return "zero"; + case 1: + return "one"; + case 2: + return "two"; + case 3: + return "three"; + case 4: + return "four"; + case 5: + return "five"; + case 6: + return "six"; + case 7: + return "seven"; + case 8: + return "eight"; + default: + return "default"; + } +} diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -5464,13 +5464,13 @@ /// Build instructions with Builder to retrieve the value at /// the position given by Index in the lookup table. - Value *BuildLookup(Value *Index, IRBuilder<> &Builder); + Value *BuildLookup(Module &M, Value *Index, Type *ValueType, + IRBuilder<> &Builder); /// Return true if a table with TableSize elements of /// type ElementType would fit in a target-legal register. static bool WouldFitInRegister(const DataLayout &DL, uint64_t TableSize, Type *ElementType); - private: // Depending on the contents of the table, it can be represented in // different ways. @@ -5491,7 +5491,12 @@ // The table is stored as an array of values. Values are retrieved by load // instructions from the table. - ArrayKind + ArrayKind, + + // The table is stored as an array of relative offsets between + // the lookup table and case results. + // Values are retrieved by shift and load.relative intrinsic call. + RelOffsetArrayKind } Kind; // For SingleValueKind, this is the single value. @@ -5507,6 +5512,15 @@ // For ArrayKind, this is the array. GlobalVariable *Array = nullptr; + + /// Determines whether a relative table should be generated. + static bool ShouldBuildRelLookupTable( + Module &M, + const SmallVectorImpl> &Values); + + /// Generate an offset between the lookup table and given case result. + static Constant *GenerateRelOffset(Module &M, GlobalVariable *Array, + Constant *CaseRes); }; } // end anonymous namespace @@ -5614,21 +5628,89 @@ return; } - // Store the table in an array. - ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); - Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); + // Check if relative lookup table should be generated. + if (ShouldBuildRelLookupTable(M, Values)) { + ArrayType *ArrayTy = + ArrayType::get(Type::getInt32Ty(M.getContext()), TableSize); + + Array = new GlobalVariable(M, ArrayTy, /*isConstant=*/true, + GlobalVariable::PrivateLinkage, nullptr, + "switch.reltable." + FuncName); + + for (size_t I = 0, E = Values.size(); I != E; ++I) { + ConstantInt *CaseVal = Values[I].first; + Constant *CaseRes = Values[I].second; + uint64_t Idx = + (CaseVal->getValue() - Offset->getValue()).getLimitedValue(); + + // If relative lookup table is enabled, put relative offsets into table. + TableContents[Idx] = GenerateRelOffset(M, Array, CaseRes); + } + + if (Values.size() < TableSize) { + Constant *DefaultValueOffset = GenerateRelOffset(M, Array, DefaultValue); + for (uint64_t I = 0; I < TableSize; ++I) { + if (TableContents[I] == DefaultValue) + TableContents[I] = DefaultValueOffset; + } + } + + // If relative table is generated, initialize the array with the table. + Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); + Array->setInitializer(Initializer); + Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); + Array->setAlignment( + Align(DL.getPrefTypeAlignment(Type::getInt32Ty(M.getContext())))); + Kind = RelOffsetArrayKind; + } else { + // Store the table in an array. + ArrayType *ArrayTy = ArrayType::get(ValueType, TableSize); + Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); + Array = new GlobalVariable(M, ArrayTy, /*isConstant=*/true, + GlobalVariable::PrivateLinkage, Initializer, + "switch.table." + FuncName); + Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); + Array->setAlignment(Align(DL.getPrefTypeAlignment(ValueType))); + Kind = ArrayKind; + } +} + +bool SwitchLookupTable::ShouldBuildRelLookupTable( + Module &M, + const SmallVectorImpl> &Values) { + // If not in PIC mode, do not generate a relative lookup table. + if (M.getPICLevel() == PICLevel::NotPIC) + return false; + + Type *ValueType = Values.begin()->second->getType(); + // If values are not pointers, do not generate a relative lookup table. + if (!ValueType->isPointerTy()) + return false; + + /// If any of the pointer values is not dso_local, do not generate + /// a relative lookup table. + for (size_t I = 0, E = Values.size(); I != E; ++I) { + Constant *CaseRes = Values[I].second; + if (auto *GlobalVal = dyn_cast(CaseRes)) + if (!GlobalVal->isDSOLocal()) + return false; + } + + return true; +} - Array = new GlobalVariable(M, ArrayTy, /*isConstant=*/true, - GlobalVariable::PrivateLinkage, Initializer, - "switch.table." + FuncName); - Array->setUnnamedAddr(GlobalValue::UnnamedAddr::Global); - // Set the alignment to that of an array items. We will be only loading one - // value out of it. - Array->setAlignment(Align(DL.getPrefTypeAlignment(ValueType))); - Kind = ArrayKind; +Constant *SwitchLookupTable::GenerateRelOffset(Module &M, GlobalVariable *Array, + Constant *CaseRes) { + Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext()); + Constant *Base = llvm::ConstantExpr::getPtrToInt(Array, IntPtrTy); + Constant *Target = llvm::ConstantExpr::getPtrToInt(CaseRes, IntPtrTy); + Constant *RelOffset = llvm::ConstantExpr::getSub(Target, Base); + return llvm::ConstantExpr::getTrunc(RelOffset, + Type::getInt32Ty(M.getContext())); } -Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { +Value *SwitchLookupTable::BuildLookup(Module &M, Value *Index, Type *ValueType, + IRBuilder<> &Builder) { switch (Kind) { case SingleValueKind: return SingleValue; @@ -5662,7 +5744,8 @@ // Mask off. return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked"); } - case ArrayKind: { + case ArrayKind: + case RelOffsetArrayKind: { // Make sure the table index will not overflow when treated as signed. IntegerType *IT = cast(Index->getType()); uint64_t TableSize = @@ -5672,12 +5755,30 @@ Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1), "switch.tableidx.zext"); - Value *GEPIndices[] = {Builder.getInt32(0), Index}; - Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, - GEPIndices, "switch.gep"); - return Builder.CreateLoad( - cast(Array->getValueType())->getElementType(), GEP, - "switch.load"); + if (Kind == ArrayKind) { + Value *GEPIndices[] = {Builder.getInt32(0), Index}; + Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array, + GEPIndices, "switch.gep"); + return Builder.CreateLoad( + cast(Array->getValueType())->getElementType(), GEP, + "switch.load"); + } else { + Constant *Base = + llvm::ConstantExpr::getBitCast(Array, Builder.getInt8PtrTy()); + + // Shift index by 2 to compute the offset. + Value *Offset = Builder.CreateLShr(Index, Builder.getInt32(2), + "switch.reltable.shift"); + + Function *LoadRelIntrinsic = llvm::Intrinsic::getDeclaration( + &M, Intrinsic::load_relative, {Index->getType()}); + + // Call load relative intrinsic that computes the target address + // by adding base address (lookup table address) and relative offset. + Value *Call = Builder.CreateCall(LoadRelIntrinsic, {Base, Offset}, + "switch.reltable.intrinsic"); + return Builder.CreateBitCast(Call, ValueType); + } } } llvm_unreachable("Unknown lookup table kind!"); @@ -6032,7 +6133,8 @@ SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultList, DV, DL, FuncName); - Value *Result = Table.BuildLookup(TableIndex, Builder); + Type *ValueType = ResultList.begin()->second->getType(); + Value *Result = Table.BuildLookup(Mod, TableIndex, ValueType, Builder); // If the result is used to return immediately from the function, we want to // do that right here. diff --git a/llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll b/llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SimplifyCFG/X86/switch_to_relative_lookup_table.ll @@ -0,0 +1,239 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s +; RUN: opt < %s -passes='simplify-cfg' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s +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" +target triple = "x86_64-unknown-linux-gnu" + +@.str = private unnamed_addr constant [5 x i8] c"zero\00", align 1 +@.str.1 = private unnamed_addr constant [4 x i8] c"one\00", align 1 +@.str.2 = private unnamed_addr constant [4 x i8] c"two\00", align 1 +@.str.3 = private unnamed_addr constant [6 x i8] c"three\00", align 1 +@.str.4 = private unnamed_addr constant [5 x i8] c"four\00", align 1 +@.str.5 = private unnamed_addr constant [5 x i8] c"five\00", align 1 +@.str.6 = private unnamed_addr constant [4 x i8] c"six\00", align 1 +@.str.7 = private unnamed_addr constant [6 x i8] c"seven\00", align 1 +@.str.8 = private unnamed_addr constant [6 x i8] c"eight\00", align 1 +@.str.9 = private unnamed_addr constant [8 x i8] c"default\00", align 1 +@.str.10 = private unnamed_addr constant [12 x i8] c"singlevalue\00", align 1 +@.str.11 = private unnamed_addr constant [9 x i8] c"default1\00", align 1 +@.str.12 = private unnamed_addr constant [9 x i8] c"default2\00", align 1 +; Relative string table lookup +; CHECK: @switch.reltable.string_table = private unnamed_addr constant [9 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.3 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.4 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.5 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.6 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.7 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.8 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table to i64)) to i32)], align 4 + +; Relative string table lookup that holes are filled with relative offset to default values +; CHECK: @switch.reltable.string_table_holes = private unnamed_addr constant [9 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([8 x i8]* @.str.9 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.3 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.4 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str.5 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([8 x i8]* @.str.9 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.7 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([6 x i8]* @.str.8 to i64), i64 ptrtoint ([9 x i32]* @switch.reltable.string_table_holes to i64)) to i32)], align 4 + +; Integer pointer table lookup +; CHECK: @switch.table.no_dso_local = private unnamed_addr constant [7 x i32*] [i32* @a, i32* @b, i32* @c, i32* @d, i32* @e, i32* @f, i32* @g], align 8 + +; Single value check +;; CHECK: @switch.reltable.single_value = private unnamed_addr constant [3 x i32] [i32 trunc (i64 sub (i64 ptrtoint ([5 x i8]* @.str to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.1 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32), i32 trunc (i64 sub (i64 ptrtoint ([4 x i8]* @.str.2 to i64), i64 ptrtoint ([3 x i32]* @switch.reltable.single_value to i64)) to i32)], align 4 + +; Switch used to return a string. +; Relative lookup table should be generated. +define i8* @string_table(i32 %cond) { +; CHECK-LABEL: @string_table( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 9 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_RELTABLE_SHIFT:%.*]] = lshr i32 [[COND:%.*]], 2 +; CHECK-NEXT: [[SWITCH_RELTABLE_INTRINSIC:%.*]] = call i8* @llvm.load.relative.i32(i8* bitcast ([9 x i32]* @switch.reltable.string_table to i8*), i32 [[SWITCH_RELTABLE_SHIFT]]) +; CHECK-NEXT: ret i8* [[SWITCH_RELTABLE_INTRINSIC]] +; CHECK: return: +; CHECK-NEXT: ret i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0) +; +entry: + switch i32 %cond, label %sw.default [ + i32 0, label %return + i32 1, label %sw.bb1 + i32 2, label %sw.bb2 + i32 3, label %sw.bb3 + i32 4, label %sw.bb4 + i32 5, label %sw.bb5 + i32 6, label %sw.bb6 + i32 7, label %sw.bb7 + i32 8, label %sw.bb8 + ] + +sw.bb1: ; preds = %entry + br label %return + +sw.bb2: ; preds = %entry + br label %return + +sw.bb3: ; preds = %entry + br label %return + +sw.bb4: ; preds = %entry + br label %return + +sw.bb5: ; preds = %entry + br label %return + +sw.bb6: ; preds = %entry + br label %return + +sw.bb7: ; preds = %entry + br label %return + +sw.bb8: ; preds = %entry + br label %return + +sw.default: ; preds = %entry + br label %return + +return: ; preds = %entry, %sw.default, %sw.bb8, %sw.bb7, %sw.bb6, %sw.bb5, %sw.bb4, %sw.bb3, %sw.bb2, %sw.bb1 + %retval.0 = phi i8* [ getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0), %sw.default ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.8, i64 0, i64 0), %sw.bb8 ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.7, i64 0, i64 0), %sw.bb7 ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.6, i64 0, i64 0), %sw.bb6 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str.5, i64 0, i64 0), %sw.bb5 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str.4, i64 0, i64 0), %sw.bb4 ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.3, i64 0, i64 0), %sw.bb3 ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), %sw.bb2 ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), %sw.bb1 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), %entry ] + ret i8* %retval.0 +} + +; Fill the holes with offset of the default value in the relative lookup table. +define i8* @string_table_holes(i32 %cond) { +; CHECK-LABEL: @string_table_holes( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 9 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_RELTABLE_SHIFT:%.*]] = lshr i32 [[COND:%.*]], 2 +; CHECK-NEXT: [[SWITCH_RELTABLE_INTRINSIC:%.*]] = call i8* @llvm.load.relative.i32(i8* bitcast ([9 x i32]* @switch.reltable.string_table_holes to i8*), i32 [[SWITCH_RELTABLE_SHIFT]]) +; CHECK-NEXT: ret i8* [[SWITCH_RELTABLE_INTRINSIC]] +; CHECK: return: +; CHECK-NEXT: ret i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0) +; +entry: + switch i32 %cond, label %sw.default [ + i32 0, label %return + i32 2, label %sw.bb1 + i32 3, label %sw.bb2 + i32 4, label %sw.bb3 + i32 5, label %sw.bb4 + i32 7, label %sw.bb5 + i32 8, label %sw.bb6 + ] + +sw.bb1: ; preds = %entry + br label %return + +sw.bb2: ; preds = %entry + br label %return + +sw.bb3: ; preds = %entry + br label %return + +sw.bb4: ; preds = %entry + br label %return + +sw.bb5: ; preds = %entry + br label %return + +sw.bb6: ; preds = %entry + br label %return + +sw.default: ; preds = %entry + br label %return + +return: ; preds = %entry, %sw.default, %sw.bb6, %sw.bb5, %sw.bb4, %sw.bb3, %sw.bb2, %sw.bb1 + %retval.0 = phi i8* [ getelementptr inbounds ([8 x i8], [8 x i8]* @.str.9, i64 0, i64 0), %sw.default ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.8, i64 0, i64 0), %sw.bb6 ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.7, i64 0, i64 0), %sw.bb5 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str.5, i64 0, i64 0), %sw.bb4 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str.4, i64 0, i64 0), %sw.bb3 ], [ getelementptr inbounds ([6 x i8], [6 x i8]* @.str.3, i64 0, i64 0), %sw.bb2 ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), %sw.bb1 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), %entry ] + ret i8* %retval.0 +} + +@a = external global i32, align 4 +@b = external global i32, align 4 +@c = external global i32, align 4 +@d = external global i32, align 4 +@e = external global i32, align 4 +@f = external global i32, align 4 +@g = external global i32, align 4 +@h = external global i32, align 4 + +; If pointers are not dso_local, relative lookup table should not be generated. +define i32* @no_dso_local(i32 %cond) { +; CHECK-LABEL: @no_dso_local( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 7 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32*], [7 x i32*]* @switch.table.no_dso_local, i32 0, i32 [[COND:%.*]] +; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32*, i32** [[SWITCH_GEP]], align 8 +; CHECK-NEXT: ret i32* [[SWITCH_LOAD]] +; CHECK: return: +; CHECK-NEXT: ret i32* @h +; +entry: + switch i32 %cond, label %sw.default [ + i32 0, label %return + i32 1, label %sw.bb1 + i32 2, label %sw.bb2 + i32 3, label %sw.bb3 + i32 4, label %sw.bb4 + i32 5, label %sw.bb5 + i32 6, label %sw.bb6 + ] + +sw.bb1: ; preds = %entry + br label %return + +sw.bb2: ; preds = %entry + br label %return + +sw.bb3: ; preds = %entry + br label %return + +sw.bb4: ; preds = %entry + br label %return + +sw.bb5: ; preds = %entry + br label %return + +sw.bb6: ; preds = %entry + br label %return + +sw.default: ; preds = %entry + br label %return + +return: ; preds = %entry, %sw.default, %sw.bb6, %sw.bb5, %sw.bb4, %sw.bb3, %sw.bb2, %sw.bb1 + %retval.0 = phi i32* [ @h, %sw.default ], [ @g, %sw.bb6 ], [ @f, %sw.bb5 ], [ @e, %sw.bb4 ], [ @d, %sw.bb3 ], [ @c, %sw.bb2 ], [ @b, %sw.bb1 ], [ @a, %entry ] + ret i32* %retval.0 +} + +; Single value check +; If there is a lookup table, where each element contains the same value, +; a relative lookup should not be generated +define void @single_value(i32 %cond) { +; CHECK-LABEL: @single_value( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[COND:%.*]], 3 +; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]] +; CHECK: switch.lookup: +; CHECK-NEXT: [[SWITCH_RELTABLE_SHIFT:%.*]] = lshr i32 [[COND:%.*]], 2 +; CHECK-NEXT: [[SWITCH_RELTABLE_INTRINSIC:%.*]] = call i8* @llvm.load.relative.i32(i8* bitcast ([3 x i32]* @switch.reltable.single_value to i8*), i32 [[SWITCH_RELTABLE_SHIFT]]) +; CHECK: sw.epilog: +; CHECK-NEXT: [[STR1:%.*]] = phi i8* [ [[SWITCH_RELTABLE_INTRINSIC]], [[SWITCH_LOOKUP]] ], [ getelementptr inbounds ([9 x i8], [9 x i8]* @.str.11, i64 0, i64 0), %entry ] +; CHECK-NEXT: [[STR2:%.*]] = phi i8* [ getelementptr inbounds ([12 x i8], [12 x i8]* @.str.10, i64 0, i64 0), [[SWITCH_LOOKUP]] ], [ getelementptr inbounds ([9 x i8], [9 x i8]* @.str.12, i64 0, i64 0), %entry ] +; CHECK-NEXT: ret void +entry: + switch i32 %cond, label %sw.default [ + i32 0, label %sw.epilog + i32 1, label %sw.bb1 + i32 2, label %sw.bb2 + ] + +sw.bb1: ; preds = %entry + br label %sw.epilog + +sw.bb2: ; preds = %entry + br label %sw.epilog + +sw.default: ; preds = %entry + br label %sw.epilog + +sw.epilog: ; preds = %entry, %sw.default, %sw.bb2, %sw.bb1 + %str1.0 = phi i8* [ getelementptr inbounds ([9 x i8], [9 x i8]* @.str.11, i64 0, i64 0), %sw.default ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0), %sw.bb2 ], [ getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0), %sw.bb1 ], [ getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), %entry ] + %str2.0 = phi i8* [ getelementptr inbounds ([9 x i8], [9 x i8]* @.str.12, i64 0, i64 0), %sw.default ], [ getelementptr inbounds ([12 x i8], [12 x i8]* @.str.10, i64 0, i64 0), %sw.bb2 ], [ getelementptr inbounds ([12 x i8], [12 x i8]* @.str.10, i64 0, i64 0), %sw.bb1 ], [ getelementptr inbounds ([12 x i8], [12 x i8]* @.str.10, i64 0, i64 0), %entry ] + ret void +} + +!llvm.module.flags = !{!0} +!0 = !{i32 7, !"PIC Level", i32 2} +