From 09a31f31545b7360c78265f9ca9cd35430ea401d Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Wed, 12 Mar 2014 18:35:40 +0000 Subject: [PATCH] Allow switch-to-lookup table for tables with holes by adding bitmask check This allows us to generate table lookups for code such as: unsigned test(unsigned x) { switch (x) { case 100: return 0; case 101: return 1; case 103: return 2; case 105: return 3; case 107: return 4; case 109: return 5; case 110: return 6; default: return f(x); } } Since cases 102, 104, etc. are not constants, the lookup table has holes in those positions. We therefore guard the table lookup with a bitmask check. Patch by Jasper Neumann! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@203694 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 66 +++++++++++++++++-- .../SimplifyCFG/X86/switch_to_lookup_table.ll | 30 ++++++++- 2 files changed, 89 insertions(+), 7 deletions(-) diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 5b3bdbe4be2..1e885876942 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -68,6 +68,7 @@ static cl::opt HoistCondStores( STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); 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"); STATISTIC(NumSpeculations, "Number of speculative executed instructions"); @@ -3735,11 +3736,22 @@ static bool SwitchToLookupTable(SwitchInst *SI, uint64_t TableSize = RangeSpread.getLimitedValue() + 1; bool TableHasHoles = (NumResults < TableSize); - // If the table has holes, we need a constant result for the default case. + // If the table has holes, we need a constant result for the default case + // or a bitmask that fits in a register. SmallVector, 4> DefaultResultsList; - if (TableHasHoles && !GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest, - DefaultResultsList, DL)) - return false; + bool HasDefaultResults = false; + if (TableHasHoles) { + HasDefaultResults = GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest, + DefaultResultsList, DL); + } + bool NeedMask = (TableHasHoles && !HasDefaultResults); + if (NeedMask) { + // As an extra penalty for the validity test we require more cases. + if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark). + return false; + if (!(DL && DL->fitsInLegalInteger(TableSize))) + return false; + } for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) { PHINode *PHI = DefaultResultsList[I].first; @@ -3786,12 +3798,54 @@ static bool SwitchToLookupTable(SwitchInst *SI, // Populate the BB that does the lookups. Builder.SetInsertPoint(LookupBB); + + if (NeedMask) { + // Before doing the lookup we do the hole check. + // The LookupBB is therefore re-purposed to do the hole check + // and we create a new LookupBB. + BasicBlock *MaskBB = LookupBB; + MaskBB->setName("switch.hole_check"); + LookupBB = BasicBlock::Create(Mod.getContext(), + "switch.lookup", + CommonDest->getParent(), + CommonDest); + + // Build bitmask; fill in a 1 bit for every case. + APInt MaskInt(TableSize, 0); + APInt One(TableSize, 1); + const ResultListTy &ResultList = ResultLists[PHIs[0]]; + for (size_t I = 0, E = ResultList.size(); I != E; ++I) { + uint64_t Idx = (ResultList[I].first->getValue() - + MinCaseVal->getValue()).getLimitedValue(); + MaskInt |= One << Idx; + } + ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt); + + // Get the TableIndex'th bit of the bitmask. + // If this bit is 0 (meaning hole) jump to the default destination, + // else continue with table lookup. + IntegerType *MapTy = TableMask->getType(); + Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy, + "switch.maskindex"); + Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex, + "switch.shifted"); + Value *LoBit = Builder.CreateTrunc(Shifted, + Type::getInt1Ty(Mod.getContext()), + "switch.lobit"); + Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest()); + + Builder.SetInsertPoint(LookupBB); + AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent()); + } + bool ReturnedEarly = false; for (size_t I = 0, E = PHIs.size(); I != E; ++I) { PHINode *PHI = PHIs[I]; + // If using a bitmask, use any value to fill the lookup table holes. + Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI]; SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI], - DefaultResults[PHI], DL); + DV, DL); Value *Result = Table.BuildLookup(TableIndex, Builder); @@ -3821,6 +3875,8 @@ static bool SwitchToLookupTable(SwitchInst *SI, SI->eraseFromParent(); ++NumLookupTables; + if (NeedMask) + ++NumLookupTablesHoles; return true; } diff --git a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll index b47fa02af22..81079b1aa5a 100644 --- a/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll +++ b/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll @@ -832,7 +832,7 @@ return: ; CHECK-NOT: switch i32 } -; This lookup table will have holes, so we cannot build it without default result. +; This lookup table will have holes, so we need to test for the holes. define i32 @nodefaultwithholes(i32 %c) { entry: switch i32 %c, label %sw.default [ @@ -853,8 +853,34 @@ return: ret i32 %x ; CHECK-LABEL: @nodefaultwithholes( -; CHECK-NOT: @switch.table +; CHECK: entry: +; CHECK: br i1 %{{.*}}, label %switch.hole_check, label %sw.default +; CHECK: switch.hole_check: +; CHECK-NEXT: %switch.maskindex = trunc i32 %switch.tableidx to i6 +; CHECK-NEXT: %switch.shifted = lshr i6 -17, %switch.maskindex +; The mask is binary 101111. +; CHECK-NEXT: %switch.lobit = trunc i6 %switch.shifted to i1 +; CHECK-NEXT: br i1 %switch.lobit, label %switch.lookup, label %sw.default +; CHECK-NOT: switch i32 +} + +; We don't build lookup tables with holes for switches with less than four cases. +define i32 @threecasesholes(i32 %c) { +entry: + switch i32 %c, label %sw.default [ + i32 0, label %return + i32 1, label %sw.bb1 + i32 3, label %sw.bb2 + ] +sw.bb1: br label %return +sw.bb2: br label %return +sw.default: br label %return +return: + %x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ] + ret i32 %x +; CHECK-LABEL: @threecasesholes( ; CHECK: switch i32 +; CHECK-NOT: @switch.table } ; We build lookup tables for switches with three or more cases. -- 2.34.1