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

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<const ConstantInt>(C1.Low);
-      const ConstantInt* CI2 = cast<const ConstantInt>(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<ConstantInt>(J->Low)->getSExtValue();
-      int64_t currentValue = cast<ConstantInt>(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