From 72a13949913bd919fc26c0eb1033329eaaf0adc4 Mon Sep 17 00:00:00 2001 From: Erik Eckstein Date: Mon, 17 Nov 2014 09:13:57 +0000 Subject: [PATCH] Optimize switch lookup tables with linear mapping. This is a simple optimization for switch table lookup: It computes the output value directly with an (optional) mul and add if there is a linear mapping between index and output. Example: int f1(int x) { switch (x) { case 0: return 10; case 1: return 11; case 2: return 12; case 3: return 13; } return 0; } generates: define i32 @f1(i32 %x) #0 { entry: %0 = icmp ult i32 %x, 4 br i1 %0, label %switch.lookup, label %return switch.lookup: %switch.offset = add i32 %x, 10 ret i32 %switch.offset return: ret i32 0 } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@222121 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 59 +++++++++- .../SimplifyCFG/X86/switch_to_lookup_table.ll | 103 +++++++++++++++++- 2 files changed, 160 insertions(+), 2 deletions(-) diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 6037b1ffc24..a8a97f0e25c 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -70,6 +70,7 @@ static cl::opt HoistCondStores( cl::desc("Hoist conditional stores if an unconditional store precedes")); STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); +STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping"); STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)"); STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); @@ -3656,6 +3657,11 @@ namespace { // store that single value and return it for each lookup. SingleValueKind, + // For tables where there is a linear relationship between table index + // and values. We calculate the result with a simple multiplication + // and addition instead of a table lookup. + LinearMapKind, + // For small tables with integer elements, we can pack them into a bitmap // that fits into a target-legal register. Values are retrieved by // shift and mask operations. @@ -3673,6 +3679,10 @@ namespace { ConstantInt *BitMap; IntegerType *BitMapElementTy; + // For LinearMapKind, these are the constants used to derive the value. + ConstantInt *LinearOffset; + ConstantInt *LinearMultiplier; + // For ArrayKind, this is the array. GlobalVariable *Array; }; @@ -3685,7 +3695,7 @@ SwitchLookupTable::SwitchLookupTable(Module &M, Constant *DefaultValue, const DataLayout *DL) : SingleValue(nullptr), BitMap(nullptr), BitMapElementTy(nullptr), - Array(nullptr) { + LinearOffset(nullptr), LinearMultiplier(nullptr), Array(nullptr) { assert(Values.size() && "Can't build lookup table without values!"); assert(TableSize >= Values.size() && "Can't fit values in table!"); @@ -3730,6 +3740,43 @@ SwitchLookupTable::SwitchLookupTable(Module &M, return; } + // Check if we can derive the value with a linear transformation from the + // table index. + if (isa(ValueType)) { + bool LinearMappingPossible = true; + APInt PrevVal; + APInt DistToPrev; + assert(TableSize >= 2 && "Should be a SingleValue table."); + // Check if there is the same distance between two consecutive values. + for (uint64_t I = 0; I < TableSize; ++I) { + ConstantInt *ConstVal = dyn_cast(TableContents[I]); + if (!ConstVal) { + // This is an undef. We could deal with it, but undefs in lookup tables + // are very seldom. It's probably not worth the additional complexity. + LinearMappingPossible = false; + break; + } + APInt Val = ConstVal->getValue(); + if (I != 0) { + APInt Dist = Val - PrevVal; + if (I == 1) { + DistToPrev = Dist; + } else if (Dist != DistToPrev) { + LinearMappingPossible = false; + break; + } + } + PrevVal = Val; + } + if (LinearMappingPossible) { + LinearOffset = cast(TableContents[0]); + LinearMultiplier = ConstantInt::get(M.getContext(), DistToPrev); + Kind = LinearMapKind; + ++NumLinearMaps; + return; + } + } + // If the type is integer and the table fits in a register, build a bitmap. if (WouldFitInRegister(DL, TableSize, ValueType)) { IntegerType *IT = cast(ValueType); @@ -3765,6 +3812,16 @@ Value *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { switch (Kind) { case SingleValueKind: return SingleValue; + case LinearMapKind: { + // Derive the result value from the input value. + Value *Result = Builder.CreateIntCast(Index, LinearMultiplier->getType(), + false, "switch.idx.cast"); + if (!LinearMultiplier->isOne()) + Result = Builder.CreateMul(Result, LinearMultiplier, "switch.idx.mult"); + if (!LinearOffset->isZero()) + Result = Builder.CreateAdd(Result, LinearOffset, "switch.offset"); + return Result; + } case BitMapKind: { // Type of the bitmap (e.g. i59). IntegerType *MapTy = BitMap->getType(); diff --git a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll index 97ce25fd10f..b9f0e49cbe6 100644 --- a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll +++ b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll @@ -895,7 +895,7 @@ sw.bb1: br label %return sw.bb2: br label %return sw.default: br label %return return: - %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ] + %x = phi i32 [ 3, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 10, %entry ] ret i32 %x ; CHECK-LABEL: @threecases( ; CHECK-NOT: switch i32 @@ -977,3 +977,104 @@ return: ; CHECK: switch i32 ; CHECK-NOT: @switch.table } + +; We can use linear mapping. +define i8 @linearmap1(i32 %c) { +entry: + switch i32 %c, label %sw.default [ + i32 10, label %return + i32 11, label %sw.bb1 + i32 12, label %sw.bb2 + i32 13, label %sw.bb3 + ] +sw.bb1: br label %return +sw.bb2: br label %return +sw.bb3: br label %return +sw.default: br label %return +return: + %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 8, %sw.bb2 ], [ 13, %sw.bb1 ], [ 18, %entry ] + ret i8 %x +; CHECK-LABEL: @linearmap1( +; CHECK: entry: +; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10 +; CHECK: switch.lookup: +; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 +; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, -5 +; CHECK-NEXT: %switch.offset = add i8 %switch.idx.mult, 18 +; CHECK-NEXT: ret i8 %switch.offset +} + +; Linear mapping in a different configuration. +define i32 @linearmap2(i8 %c) { +entry: + switch i8 %c, label %sw.default [ + i8 -10, label %return + i8 -11, label %sw.bb1 + i8 -12, label %sw.bb2 + i8 -13, label %sw.bb3 + ] +sw.bb1: br label %return +sw.bb2: br label %return +sw.bb3: br label %return +sw.default: br label %return +return: + %x = phi i32 [ 3, %sw.default ], [ 18, %sw.bb3 ], [ 19, %sw.bb2 ], [ 20, %sw.bb1 ], [ 21, %entry ] + ret i32 %x +; CHECK-LABEL: @linearmap2( +; CHECK: entry: +; CHECK-NEXT: %switch.tableidx = sub i8 %c, -13 +; CHECK: switch.lookup: +; CHECK-NEXT: %switch.idx.cast = zext i8 %switch.tableidx to i32 +; CHECK-NEXT: %switch.offset = add i32 %switch.idx.cast, 18 +; CHECK-NEXT: ret i32 %switch.offset +} + +; Linear mapping with overflows. +define i8 @linearmap3(i32 %c) { +entry: + switch i32 %c, label %sw.default [ + i32 10, label %return + i32 11, label %sw.bb1 + i32 12, label %sw.bb2 + i32 13, label %sw.bb3 + ] +sw.bb1: br label %return +sw.bb2: br label %return +sw.bb3: br label %return +sw.default: br label %return +return: + %x = phi i8 [ 3, %sw.default ], [ 44, %sw.bb3 ], [ -56, %sw.bb2 ], [ 100, %sw.bb1 ], [ 0, %entry ] + ret i8 %x +; CHECK-LABEL: @linearmap3( +; CHECK: entry: +; CHECK-NEXT: %switch.tableidx = sub i32 %c, 10 +; CHECK: switch.lookup: +; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 +; CHECK-NEXT: %switch.idx.mult = mul i8 %switch.idx.cast, 100 +; CHECK-NEXT: ret i8 %switch.idx.mult +} + +; Linear mapping with with multiplier 1 and offset 0. +define i8 @linearmap4(i32 %c) { +entry: + switch i32 %c, label %sw.default [ + i32 -2, label %return + i32 -1, label %sw.bb1 + i32 0, label %sw.bb2 + i32 1, label %sw.bb3 + ] +sw.bb1: br label %return +sw.bb2: br label %return +sw.bb3: br label %return +sw.default: br label %return +return: + %x = phi i8 [ 3, %sw.default ], [ 3, %sw.bb3 ], [ 2, %sw.bb2 ], [ 1, %sw.bb1 ], [ 0, %entry ] + ret i8 %x +; CHECK-LABEL: @linearmap4( +; CHECK: entry: +; CHECK-NEXT: %switch.tableidx = sub i32 %c, -2 +; CHECK: switch.lookup: +; CHECK-NEXT: %switch.idx.cast = trunc i32 %switch.tableidx to i8 +; CHECK-NEXT: ret i8 %switch.idx.cast +} + -- 2.34.1