diff options
| -rw-r--r-- | lib/Transforms/Utils/SimplifyCFG.cpp | 34 | ||||
| -rw-r--r-- | test/Transforms/SimplifyCFG/CoveredLookupTable.ll | 48 |
2 files changed, 76 insertions, 6 deletions
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index 0e56904ebd..ad3b92a714 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -3734,14 +3734,30 @@ static bool SwitchToLookupTable(SwitchInst *SI, CommonDest->getParent(), CommonDest); - // Check whether the condition value is within the case range, and branch to - // the new BB. + // Compute the table index value. Builder.SetInsertPoint(SI); Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, "switch.tableidx"); - Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( - MinCaseVal->getType(), TableSize)); - Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); + + // Compute the maximum table size representable by the integer type we are + // switching upon. + const unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); + const uint64_t MaxTableSize = CaseSize > 63? UINT64_MAX : 1ULL << CaseSize; + assert(MaxTableSize >= TableSize && + "It is impossible for a switch to have more entries than the max " + "representable value of its input integer type's size."); + + // If we have a covered lookup table, unconditionally branch to the lookup table + // BB. Otherwise, check if the condition value is within the case range. If it + // is so, branch to the new BB. Otherwise branch to SI's default destination. + const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize; + if (GeneratingCoveredLookupTable) { + Builder.CreateBr(LookupBB); + } else { + Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( + MinCaseVal->getType(), TableSize)); + Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); + } // Populate the BB that does the lookups. Builder.SetInsertPoint(LookupBB); @@ -3772,7 +3788,13 @@ static bool SwitchToLookupTable(SwitchInst *SI, // Remove the switch. for (unsigned i = 0; i < SI->getNumSuccessors(); ++i) { BasicBlock *Succ = SI->getSuccessor(i); - if (Succ == SI->getDefaultDest()) continue; + + // If we are not generating a covered lookup table, we will have a + // conditional branch from SI's parent BB to SI's default destination if our + // input value lies outside of our case range. Thus in that case leave the + // default destination BB as a predecessor of SI's parent BB. + if (Succ == SI->getDefaultDest() && !GeneratingCoveredLookupTable) + continue; Succ->removePredecessor(SI->getParent()); } SI->eraseFromParent(); diff --git a/test/Transforms/SimplifyCFG/CoveredLookupTable.ll b/test/Transforms/SimplifyCFG/CoveredLookupTable.ll new file mode 100644 index 0000000000..8b45a590bb --- /dev/null +++ b/test/Transforms/SimplifyCFG/CoveredLookupTable.ll @@ -0,0 +1,48 @@ +; RUN: opt -simplifycfg -S %s | FileCheck %s +; rdar://15268442 + +target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" +target triple = "x86_64-apple-darwin12.0.0" + +; CHECK-LABEL: define i3 @coveredswitch_test( +; CHECK: entry: +; CHECK-NEXT: sub i3 %input, -4 +; CHECK-NEXT: zext i3 %switch.tableidx to i24 +; CHECK-NEXT: mul i24 %switch.cast, 3 +; CHECK-NEXT: lshr i24 7507338, %switch.shiftamt +; CHECK-NEXT: trunc i24 %switch.downshift to i3 +; CHECK-NEXT: ret i3 %switch.masked + +define i3 @coveredswitch_test(i3 %input) { +entry: + switch i3 %input, label %bb8 [ + i3 0, label %bb7 + i3 1, label %bb + i3 2, label %bb3 + i3 3, label %bb4 + i3 4, label %bb5 + i3 5, label %bb6 + ] + +bb: ; preds = %entry + br label %bb8 + +bb3: ; preds = %entry + br label %bb8 + +bb4: ; preds = %entry + br label %bb8 + +bb5: ; preds = %entry + br label %bb8 + +bb6: ; preds = %entry + br label %bb8 + +bb7: ; preds = %entry + br label %bb8 + +bb8: ; preds = %bb7, %bb6, %bb5, %bb4, %bb3, %bb, %entry + %result = phi i3 [ 0, %bb7 ], [ 1, %bb6 ], [ 2, %bb5 ], [ 3, %bb4 ], [ 4, %bb3 ], [ 5, %bb ], [ 6, %entry ] + ret i3 %result +} |