Skip to content

Commit b73c0b0

Browse files
committedMar 12, 2014
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! llvm-svn: 203694
1 parent 44be154 commit b73c0b0

File tree

2 files changed

+89
-7
lines changed

2 files changed

+89
-7
lines changed
 

‎llvm/lib/Transforms/Utils/SimplifyCFG.cpp

+61-5
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,7 @@ static cl::opt<bool> HoistCondStores(
6868

6969
STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
7070
STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
71+
STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
7172
STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
7273
STATISTIC(NumSpeculations, "Number of speculative executed instructions");
7374

@@ -3735,11 +3736,22 @@ static bool SwitchToLookupTable(SwitchInst *SI,
37353736
uint64_t TableSize = RangeSpread.getLimitedValue() + 1;
37363737
bool TableHasHoles = (NumResults < TableSize);
37373738

3738-
// If the table has holes, we need a constant result for the default case.
3739+
// If the table has holes, we need a constant result for the default case
3740+
// or a bitmask that fits in a register.
37393741
SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
3740-
if (TableHasHoles && !GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest,
3741-
DefaultResultsList, DL))
3742-
return false;
3742+
bool HasDefaultResults = false;
3743+
if (TableHasHoles) {
3744+
HasDefaultResults = GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest,
3745+
DefaultResultsList, DL);
3746+
}
3747+
bool NeedMask = (TableHasHoles && !HasDefaultResults);
3748+
if (NeedMask) {
3749+
// As an extra penalty for the validity test we require more cases.
3750+
if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark).
3751+
return false;
3752+
if (!(DL && DL->fitsInLegalInteger(TableSize)))
3753+
return false;
3754+
}
37433755

37443756
for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
37453757
PHINode *PHI = DefaultResultsList[I].first;
@@ -3786,12 +3798,54 @@ static bool SwitchToLookupTable(SwitchInst *SI,
37863798

37873799
// Populate the BB that does the lookups.
37883800
Builder.SetInsertPoint(LookupBB);
3801+
3802+
if (NeedMask) {
3803+
// Before doing the lookup we do the hole check.
3804+
// The LookupBB is therefore re-purposed to do the hole check
3805+
// and we create a new LookupBB.
3806+
BasicBlock *MaskBB = LookupBB;
3807+
MaskBB->setName("switch.hole_check");
3808+
LookupBB = BasicBlock::Create(Mod.getContext(),
3809+
"switch.lookup",
3810+
CommonDest->getParent(),
3811+
CommonDest);
3812+
3813+
// Build bitmask; fill in a 1 bit for every case.
3814+
APInt MaskInt(TableSize, 0);
3815+
APInt One(TableSize, 1);
3816+
const ResultListTy &ResultList = ResultLists[PHIs[0]];
3817+
for (size_t I = 0, E = ResultList.size(); I != E; ++I) {
3818+
uint64_t Idx = (ResultList[I].first->getValue() -
3819+
MinCaseVal->getValue()).getLimitedValue();
3820+
MaskInt |= One << Idx;
3821+
}
3822+
ConstantInt *TableMask = ConstantInt::get(Mod.getContext(), MaskInt);
3823+
3824+
// Get the TableIndex'th bit of the bitmask.
3825+
// If this bit is 0 (meaning hole) jump to the default destination,
3826+
// else continue with table lookup.
3827+
IntegerType *MapTy = TableMask->getType();
3828+
Value *MaskIndex = Builder.CreateZExtOrTrunc(TableIndex, MapTy,
3829+
"switch.maskindex");
3830+
Value *Shifted = Builder.CreateLShr(TableMask, MaskIndex,
3831+
"switch.shifted");
3832+
Value *LoBit = Builder.CreateTrunc(Shifted,
3833+
Type::getInt1Ty(Mod.getContext()),
3834+
"switch.lobit");
3835+
Builder.CreateCondBr(LoBit, LookupBB, SI->getDefaultDest());
3836+
3837+
Builder.SetInsertPoint(LookupBB);
3838+
AddPredecessorToBlock(SI->getDefaultDest(), MaskBB, SI->getParent());
3839+
}
3840+
37893841
bool ReturnedEarly = false;
37903842
for (size_t I = 0, E = PHIs.size(); I != E; ++I) {
37913843
PHINode *PHI = PHIs[I];
37923844

3845+
// If using a bitmask, use any value to fill the lookup table holes.
3846+
Constant *DV = NeedMask ? ResultLists[PHI][0].second : DefaultResults[PHI];
37933847
SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI],
3794-
DefaultResults[PHI], DL);
3848+
DV, DL);
37953849

37963850
Value *Result = Table.BuildLookup(TableIndex, Builder);
37973851

@@ -3821,6 +3875,8 @@ static bool SwitchToLookupTable(SwitchInst *SI,
38213875
SI->eraseFromParent();
38223876

38233877
++NumLookupTables;
3878+
if (NeedMask)
3879+
++NumLookupTablesHoles;
38243880
return true;
38253881
}
38263882

‎llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

+28-2
Original file line numberDiff line numberDiff line change
@@ -832,7 +832,7 @@ return:
832832
; CHECK-NOT: switch i32
833833
}
834834

835-
; This lookup table will have holes, so we cannot build it without default result.
835+
; This lookup table will have holes, so we need to test for the holes.
836836
define i32 @nodefaultwithholes(i32 %c) {
837837
entry:
838838
switch i32 %c, label %sw.default [
@@ -853,8 +853,34 @@ return:
853853
ret i32 %x
854854

855855
; CHECK-LABEL: @nodefaultwithholes(
856-
; CHECK-NOT: @switch.table
856+
; CHECK: entry:
857+
; CHECK: br i1 %{{.*}}, label %switch.hole_check, label %sw.default
858+
; CHECK: switch.hole_check:
859+
; CHECK-NEXT: %switch.maskindex = trunc i32 %switch.tableidx to i6
860+
; CHECK-NEXT: %switch.shifted = lshr i6 -17, %switch.maskindex
861+
; The mask is binary 101111.
862+
; CHECK-NEXT: %switch.lobit = trunc i6 %switch.shifted to i1
863+
; CHECK-NEXT: br i1 %switch.lobit, label %switch.lookup, label %sw.default
864+
; CHECK-NOT: switch i32
865+
}
866+
867+
; We don't build lookup tables with holes for switches with less than four cases.
868+
define i32 @threecasesholes(i32 %c) {
869+
entry:
870+
switch i32 %c, label %sw.default [
871+
i32 0, label %return
872+
i32 1, label %sw.bb1
873+
i32 3, label %sw.bb2
874+
]
875+
sw.bb1: br label %return
876+
sw.bb2: br label %return
877+
sw.default: br label %return
878+
return:
879+
%x = phi i32 [ %c, %sw.default ], [ 5, %sw.bb2 ], [ 7, %sw.bb1 ], [ 9, %entry ]
880+
ret i32 %x
881+
; CHECK-LABEL: @threecasesholes(
857882
; CHECK: switch i32
883+
; CHECK-NOT: @switch.table
858884
}
859885

860886
; We build lookup tables for switches with three or more cases.

0 commit comments

Comments
 (0)
Please sign in to comment.