PR1255: Case Ranges

Implemented IntItem - the wrapper around APInt. Why not to use APInt item directly right now?
1. It will very difficult to implement case ranges as series of small patches. We got several large and heavy patches. Each patch will about 90-120 kb. If you replace ConstantInt with APInt in SwitchInst you will need to changes at the same time all Readers,Writers and absolutely all passes that uses SwitchInst.
2. We can implement APInt pool inside and save memory space. E.g. we use several switches that works with 256 bit items (switch on signatures, or strings). We can avoid value duplicates in this case.
3. IntItem can be easyly easily replaced with APInt.
4. Currenly we can interpret IntItem both as ConstantInt and as APInt. It allows to provide SwitchInst methods that works with ConstantInt for non-updated passes.

Why I need it right now? Currently I need to update SimplifyCFG pass (EqualityComparisons). I need to work with APInts directly a lot, so peaces of code
ConstantInt *V = ...;
if (V->getValue().ugt(AnotherV->getValue()) {
  ...
}
will look awful. Much more better this way:
IntItem V = ConstantIntVal->getValue();
if (AnotherV < V) {
}

Of course any reviews are welcome.

P.S.: I'm also going to rename ConstantRangesSet to IntegersSubset, and CRSBuilder to IntegersSubsetMapping (allows to map individual subsets of integers to the BasicBlocks).
Since in future these classes will founded on APInt, it will possible to use them in more generic ways.




git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157576 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 34 insertions, 15 deletions

diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index 5a132a4f2f..3477bbc02b 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -2283,18 +2283,21 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
               ActiveWords = Record[CurIdx++];
             Low = ReadWideAPInt(&Record[CurIdx], ActiveWords, ValueBitWidth);
             CurIdx += ActiveWords;
-            
+
             if (!isSingleNumber) {
               ActiveWords = 1;
               if (ValueBitWidth > 64)
                 ActiveWords = Record[CurIdx++];
               APInt High =
                   ReadWideAPInt(&Record[CurIdx], ActiveWords, ValueBitWidth);
-              CaseBuilder.add(cast<ConstantInt>(ConstantInt::get(OpTy, Low)),
-                              cast<ConstantInt>(ConstantInt::get(OpTy, High)));
+              IntItemConstantIntImpl HighImpl =
+                  cast<ConstantInt>(ConstantInt::get(OpTy, High));
+              
+              CaseBuilder.add(IntItem::fromType(OpTy, Low),
+                              IntItem::fromType(OpTy, High));
               CurIdx += ActiveWords;
             } else
-              CaseBuilder.add(cast<ConstantInt>(ConstantInt::get(OpTy, Low)));
+              CaseBuilder.add(IntItem::fromType(OpTy, Low));
           }
           BasicBlock *DestBB = getBasicBlock(Record[CurIdx++]);
           ConstantRangesSet Case = CaseBuilder.getCase(); 
diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp
index 9557a44992..c68086655f 100644
--- a/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -1175,8 +1175,8 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
 
           Vals64.push_back(CRS.isSingleNumber(ri));
 
-          const APInt &Low = r.Low->getValue();
-          const APInt &High = r.High->getValue();
+          const APInt &Low = r.Low;
+          const APInt &High = r.High;
           unsigned Code, Abbrev; // will unused.
           
           EmitAPInt(Vals64, Code, Abbrev, Low, true);
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 90fec6a28e..83df110d73 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2427,7 +2427,7 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
   
   /// Use a shorter form of declaration, and also
   /// show the we want to use CRSBuilder as Clusterifier.
-  typedef CRSBuilderBase<MachineBasicBlock, true> Clusterifier;
+  typedef CRSBuilderBase<MachineBasicBlock> Clusterifier;
   
   Clusterifier TheClusterifier;
 
@@ -2456,7 +2456,10 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
       BPI->setEdgeWeight(SI.getParent(), C.second->getBasicBlock(), W);  
     }
 
-    Cases.push_back(Case(C.first.Low, C.first.High, C.second, W));
+    // FIXME: Currently work with ConstantInt based numbers.
+    // Changing it to APInt based is a pretty heavy for this commit.
+    Cases.push_back(Case(C.first.Low.toConstantInt(),
+                         C.first.High.toConstantInt(), C.second, W));
     
     if (C.first.Low != C.first.High)
     // A range counts double, since it requires two compares.
diff --git a/lib/ExecutionEngine/Interpreter/Execution.cpp b/lib/ExecutionEngine/Interpreter/Execution.cpp
index 298ce2c2b9..46ed6fdfbf 100644
--- a/lib/ExecutionEngine/Interpreter/Execution.cpp
+++ b/lib/ExecutionEngine/Interpreter/Execution.cpp
@@ -654,8 +654,11 @@ void Interpreter::visitSwitchInst(SwitchInst &I) {
     ConstantRangesSet Case = i.getCaseValueEx();
     for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) {
       ConstantRangesSet::Range r = Case.getItem(n);
-      GenericValue Low = getOperandValue(r.Low, SF);
-      GenericValue High = getOperandValue(r.High, SF);
+      // FIXME: Currently work with ConstantInt based numbers.
+      const ConstantInt *LowCI = r.Low.getImplementation();
+      const ConstantInt *HighCI = r.High.getImplementation();
+      GenericValue Low = getOperandValue(const_cast<ConstantInt*>(LowCI), SF);
+      GenericValue High = getOperandValue(const_cast<ConstantInt*>(HighCI), SF);
       if (executeICMP_ULE(Low, CondVal, ElTy).IntVal != 0 &&
           executeICMP_ULE(CondVal, High, ElTy).IntVal != 0) {
         Dest = cast<BasicBlock>(i.getCaseSuccessor());
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index 179f29cdaf..130b876ee9 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -171,8 +171,10 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions) {
       SwitchInst::CaseIt FirstCase = SI->case_begin();
       ConstantRangesSet CRS = FirstCase.getCaseValueEx();
       if (CRS.getNumItems() == 1 && CRS.isSingleNumber(0)) {
+        // FIXME: Currently work with ConstantInt based numbers.
         Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
-            CRS.getItem(0).Low, "cond");
+            CRS.getItem(0).Low.toConstantInt(),
+            "cond");
 
         // Insert the new branch.
         Builder.CreateCondBr(Cond, FirstCase.getCaseSuccessor(),
diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp
index fa5a9340f4..23620373a0 100644
--- a/lib/Transforms/Utils/LowerSwitch.cpp
+++ b/lib/Transforms/Utils/LowerSwitch.cpp
@@ -239,7 +239,11 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
   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));
+    
+    // FIXME: Currently work with ConstantInt based numbers.
+    // Changing it to APInt based is a pretty heavy for this commit.
+    Cases.push_back(CaseRange(C.first.Low.toConstantInt(),
+                              C.first.High.toConstantInt(), C.second));
     if (C.first.Low != C.first.High)
       // A range counts double, since it requires two compares.
       ++numCmps;
diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 819a090cc3..42a92d955c 100644
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -3170,7 +3170,10 @@ SwitchInst::~SwitchInst() {
 ///
 void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
   CRSBuilder CB;
-  CB.add(OnVal);
+  
+  // FIXME: Currently we work with ConstantInt based cases.
+  // So inititalize IntItem container directly from ConstantInt.
+  CB.add(IntItem::fromConstantInt(OnVal));
   ConstantRangesSet CRS = CB.getCase();
   addCase(CRS, Dest);
 }
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index 64b087631e..c546e416f4 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -805,15 +805,16 @@ void Verifier::visitSwitchInst(SwitchInst &SI) {
   // Check to make sure that all of the constants in the switch instruction
   // have the same type as the switched-on value.
   Type *SwitchTy = SI.getCondition()->getType();
+  IntegerType *IntTy = cast<IntegerType>(SwitchTy);
   CRSBuilder Builder;
   std::map<ConstantRangesSet::Range, unsigned> RangeSetMap;
   for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) {
     ConstantRangesSet RS = i.getCaseValueEx();
     for (unsigned ri = 0, rie = RS.getNumItems(); ri < rie; ++ri) {
       ConstantRangesSet::Range r = RS.getItem(ri);
-      Assert1(r.Low->getType() == SwitchTy,
+      Assert1(r.Low->getBitWidth() == IntTy->getBitWidth(),
               "Switch constants must all be same type as switch value!", &SI);
-      Assert1(r.High->getType() == SwitchTy,
+      Assert1(r.High->getBitWidth() == IntTy->getBitWidth(),
               "Switch constants must all be same type as switch value!", &SI);
       Builder.add(r);
       RangeSetMap[r] = i.getCaseIndex();