@@ -68,6 +68,7 @@ static cl::opt<bool> HoistCondStores(
68
68
69
69
STATISTIC (NumBitMaps, " Number of switch instructions turned into bitmaps" );
70
70
STATISTIC (NumLookupTables, " Number of switch instructions turned into lookup tables" );
71
+ STATISTIC (NumLookupTablesHoles, " Number of switch instructions turned into lookup tables (holes checked)" );
71
72
STATISTIC (NumSinkCommons, " Number of common instructions sunk down to the end block" );
72
73
STATISTIC (NumSpeculations, " Number of speculative executed instructions" );
73
74
@@ -3735,11 +3736,22 @@ static bool SwitchToLookupTable(SwitchInst *SI,
3735
3736
uint64_t TableSize = RangeSpread.getLimitedValue () + 1 ;
3736
3737
bool TableHasHoles = (NumResults < TableSize);
3737
3738
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.
3739
3741
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
+ }
3743
3755
3744
3756
for (size_t I = 0 , E = DefaultResultsList.size (); I != E; ++I) {
3745
3757
PHINode *PHI = DefaultResultsList[I].first ;
@@ -3786,12 +3798,54 @@ static bool SwitchToLookupTable(SwitchInst *SI,
3786
3798
3787
3799
// Populate the BB that does the lookups.
3788
3800
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
+
3789
3841
bool ReturnedEarly = false ;
3790
3842
for (size_t I = 0 , E = PHIs.size (); I != E; ++I) {
3791
3843
PHINode *PHI = PHIs[I];
3792
3844
3845
+ // If using a bitmask, use any value to fill the lookup table holes.
3846
+ Constant *DV = NeedMask ? ResultLists[PHI][0 ].second : DefaultResults[PHI];
3793
3847
SwitchLookupTable Table (Mod, TableSize, MinCaseVal, ResultLists[PHI],
3794
- DefaultResults[PHI] , DL);
3848
+ DV , DL);
3795
3849
3796
3850
Value *Result = Table.BuildLookup (TableIndex, Builder);
3797
3851
@@ -3821,6 +3875,8 @@ static bool SwitchToLookupTable(SwitchInst *SI,
3821
3875
SI->eraseFromParent ();
3822
3876
3823
3877
++NumLookupTables;
3878
+ if (NeedMask)
3879
+ ++NumLookupTablesHoles;
3824
3880
return true ;
3825
3881
}
3826
3882
0 commit comments