From e98a88957ea0c16ec49ff33bff564604255c024f Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Thu, 24 May 2012 09:33:20 +0000 Subject: PR1255 related changes (case ranges): LowerSwitch::Clusterify : main functinality was replaced with CRSBuilder::optimize, so big part of Clusterify's code was reduced. test/Transform/LowerSwitch/feature.ll - this test was refactored: grep + count was replaced with FileCheck usage. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157384 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/LowerSwitch.cpp | 58 +++++++------------- test/Transforms/LowerSwitch/feature.ll | 97 ++++++++++++++++++++++++++++++++-- 2 files changed, 111 insertions(+), 44 deletions(-) diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp index a16130d3d7..fa5a9340f4 100644 --- a/lib/Transforms/Utils/LowerSwitch.cpp +++ b/lib/Transforms/Utils/LowerSwitch.cpp @@ -66,18 +66,6 @@ namespace { BasicBlock* OrigBlock, BasicBlock* Default); unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); }; - - /// The comparison function for sorting the switch case values in the vector. - /// WARNING: Case ranges should be disjoint! - struct CaseCmp { - bool operator () (const LowerSwitch::CaseRange& C1, - const LowerSwitch::CaseRange& C2) { - - const ConstantInt* CI1 = cast(C1.Low); - const ConstantInt* CI2 = cast(C2.High); - return CI1->getValue().slt(CI2->getValue()); - } - }; } char LowerSwitch::ID = 0; @@ -159,7 +147,7 @@ BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, Function::iterator FI = OrigBlock; F->getBasicBlockList().insert(++FI, NewNode); - ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, + ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_ULT, Val, Pivot.Low, "Pivot"); NewNode->getInstList().push_back(Comp); BranchInst::Create(LBranch, RBranch, Comp, NewNode); @@ -234,40 +222,30 @@ BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, // Clusterify - Transform simple list of Cases into list of CaseRange's unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { - unsigned numCmps = 0; + + CRSBuilder TheClusterifier; // Start with "simple" cases - for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) - Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), - i.getCaseSuccessor())); + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); + i != e; ++i) { + BasicBlock *SuccBB = i.getCaseSuccessor(); + ConstantRangesSet CRS = i.getCaseValueEx(); + TheClusterifier.add(CRS, SuccBB); + } - std::sort(Cases.begin(), Cases.end(), CaseCmp()); - - // Merge case into clusters - if (Cases.size()>=2) - for (CaseItr I=Cases.begin(), J=llvm::next(Cases.begin()); J!=Cases.end(); ) { - int64_t nextValue = cast(J->Low)->getSExtValue(); - int64_t currentValue = cast(I->High)->getSExtValue(); - BasicBlock* nextBB = J->BB; - BasicBlock* currentBB = I->BB; - - // If the two neighboring cases go to the same destination, merge them - // into a single case. - if ((nextValue-currentValue==1) && (currentBB == nextBB)) { - I->High = J->High; - J = Cases.erase(J); - } else { - I = J++; - } - } - - for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { - if (I->Low != I->High) + TheClusterifier.optimize(); + + size_t numCmps = 0; + for (CRSBuilder::RangeIterator i = TheClusterifier.begin(), + e = TheClusterifier.end(); i != e; ++i, ++numCmps) { + CRSBuilder::Cluster &C = *i; + Cases.push_back(CaseRange(C.first.Low, C.first.High, C.second)); + if (C.first.Low != C.first.High) // A range counts double, since it requires two compares. ++numCmps; } - return numCmps; + return numCmps; } // processSwitchInst - Replace the specified switch instruction with a sequence diff --git a/test/Transforms/LowerSwitch/feature.ll b/test/Transforms/LowerSwitch/feature.ll index cdfa0f371d..cc77d3c44d 100644 --- a/test/Transforms/LowerSwitch/feature.ll +++ b/test/Transforms/LowerSwitch/feature.ll @@ -1,10 +1,99 @@ -; RUN: opt < %s -lowerswitch -S > %t -; RUN: grep slt %t | count 10 -; RUN: grep ule %t | count 3 -; RUN: grep eq %t | count 9 +; RUN: opt < %s -lowerswitch -S | FileCheck %s + +; We have switch on input. +; On output we should got binary comparison tree. Check that all is fine. + +;CHECK: entry: +;CHECK-NEXT: br label %NodeBlock37 + +;CHECK: NodeBlock37: ; preds = %entry +;CHECK-NEXT: %Pivot38 = icmp ult i32 %tmp158, 11 +;CHECK-NEXT: br i1 %Pivot38, label %NodeBlock13, label %NodeBlock35 + +;CHECK: NodeBlock35: ; preds = %NodeBlock37 +;CHECK-NEXT: %Pivot36 = icmp ult i32 %tmp158, 14 +;CHECK-NEXT: br i1 %Pivot36, label %NodeBlock23, label %NodeBlock33 + +;CHECK: NodeBlock33: ; preds = %NodeBlock35 +;CHECK-NEXT: %Pivot34 = icmp ult i32 %tmp158, 15 +;CHECK-NEXT: br i1 %Pivot34, label %LeafBlock25, label %NodeBlock31 + +;CHECK: NodeBlock31: ; preds = %NodeBlock33 +;CHECK-NEXT: %Pivot32 = icmp ult i32 %tmp158, -6 +;CHECK-NEXT: br i1 %Pivot32, label %LeafBlock27, label %LeafBlock29 + +;CHECK: LeafBlock29: ; preds = %NodeBlock31 +;CHECK-NEXT: %tmp158.off = add i32 %tmp158, 6 +;CHECK-NEXT: %SwitchLeaf30 = icmp ule i32 %tmp158.off, 4 +;CHECK-NEXT: br i1 %SwitchLeaf30, label %bb338, label %NewDefault + +;CHECK: LeafBlock27: ; preds = %NodeBlock31 +;CHECK-NEXT: %SwitchLeaf28 = icmp eq i32 %tmp158, 15 +;CHECK-NEXT: br i1 %SwitchLeaf28, label %bb334, label %NewDefault + +;CHECK: LeafBlock25: ; preds = %NodeBlock33 +;CHECK-NEXT: %SwitchLeaf26 = icmp eq i32 %tmp158, 14 +;CHECK-NEXT: br i1 %SwitchLeaf26, label %bb332, label %NewDefault + +;CHECK: NodeBlock23: ; preds = %NodeBlock35 +;CHECK-NEXT: %Pivot24 = icmp ult i32 %tmp158, 12 +;CHECK-NEXT: br i1 %Pivot24, label %LeafBlock15, label %NodeBlock21 + +;CHECK: NodeBlock21: ; preds = %NodeBlock23 +;CHECK-NEXT: %Pivot22 = icmp ult i32 %tmp158, 13 +;CHECK-NEXT: br i1 %Pivot22, label %LeafBlock17, label %LeafBlock19 + +;CHECK: LeafBlock19: ; preds = %NodeBlock21 +;CHECK-NEXT: %SwitchLeaf20 = icmp eq i32 %tmp158, 13 +;CHECK-NEXT: br i1 %SwitchLeaf20, label %bb330, label %NewDefault + +;CHECK: LeafBlock17: ; preds = %NodeBlock21 +;CHECK-NEXT: %SwitchLeaf18 = icmp eq i32 %tmp158, 12 +;CHECK-NEXT: br i1 %SwitchLeaf18, label %bb328, label %NewDefault + +;CHECK: LeafBlock15: ; preds = %NodeBlock23 +;CHECK-NEXT: %SwitchLeaf16 = icmp eq i32 %tmp158, 11 +;CHECK-NEXT: br i1 %SwitchLeaf16, label %bb326, label %NewDefault + +;CHECK: NodeBlock13: ; preds = %NodeBlock37 +;CHECK-NEXT: %Pivot14 = icmp ult i32 %tmp158, 8 +;CHECK-NEXT: br i1 %Pivot14, label %NodeBlock, label %NodeBlock11 + +;CHECK: NodeBlock11: ; preds = %NodeBlock13 +;CHECK-NEXT: %Pivot12 = icmp ult i32 %tmp158, 9 +;CHECK-NEXT: br i1 %Pivot12, label %LeafBlock3, label %NodeBlock9 + +;CHECK: NodeBlock9: ; preds = %NodeBlock11 +;CHECK-NEXT: %Pivot10 = icmp ult i32 %tmp158, 10 +;CHECK-NEXT: br i1 %Pivot10, label %LeafBlock5, label %LeafBlock7 + +;CHECK: LeafBlock7: ; preds = %NodeBlock9 +;CHECK-NEXT: %SwitchLeaf8 = icmp eq i32 %tmp158, 10 +;CHECK-NEXT: br i1 %SwitchLeaf8, label %bb324, label %NewDefault + +;CHECK: LeafBlock5: ; preds = %NodeBlock9 +;CHECK-NEXT: %SwitchLeaf6 = icmp eq i32 %tmp158, 9 +;CHECK-NEXT: br i1 %SwitchLeaf6, label %bb322, label %NewDefault + +;CHECK: LeafBlock3: ; preds = %NodeBlock11 +;CHECK-NEXT: %SwitchLeaf4 = icmp eq i32 %tmp158, 8 +;CHECK-NEXT: br i1 %SwitchLeaf4, label %bb338, label %NewDefault + +;CHECK: NodeBlock: ; preds = %NodeBlock13 +;CHECK-NEXT: %Pivot = icmp ult i32 %tmp158, 7 +;CHECK-NEXT: br i1 %Pivot, label %LeafBlock, label %LeafBlock1 + +;CHECK: LeafBlock1: ; preds = %NodeBlock +;CHECK-NEXT: %SwitchLeaf2 = icmp eq i32 %tmp158, 7 +;CHECK-NEXT: br i1 %SwitchLeaf2, label %bb, label %NewDefault + +;CHECK: LeafBlock: ; preds = %NodeBlock +;CHECK-NEXT: %SwitchLeaf = icmp ule i32 %tmp158, 6 +;CHECK-NEXT: br i1 %SwitchLeaf, label %bb338, label %NewDefault define i32 @main(i32 %tmp158) { entry: + switch i32 %tmp158, label %bb336 [ i32 -2, label %bb338 i32 -3, label %bb338 -- cgit v1.2.3