Revert "IntRange:" as it appears to be breaking self hosting.

This reverts commit b2833d9dcba88c6f0520cad760619200adc0442c.

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

3 files changed, 159 insertions, 98 deletions

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 2d074079cc..42b9099cdc 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2450,23 +2450,22 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
   size_t numCmps = 0;
   for (Clusterifier::RangeIterator i = TheClusterifier.begin(),
        e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
-    const Clusterifier::RangeEx &R = i->first;
-    MachineBasicBlock *MBB = i->second;
+    Clusterifier::Cluster &C = *i;
     unsigned W = 0;
     if (BPI) {
-      W = BPI->getEdgeWeight(SI.getParent(), MBB->getBasicBlock());
+      W = BPI->getEdgeWeight(SI.getParent(), C.second->getBasicBlock());
       if (!W)
         W = 16;
-      W *= R.Weight;
-      BPI->setEdgeWeight(SI.getParent(), MBB->getBasicBlock(), W);  
+      W *= C.first.Weight;
+      BPI->setEdgeWeight(SI.getParent(), C.second->getBasicBlock(), W);  
     }
 
     // FIXME: Currently work with ConstantInt based numbers.
     // Changing it to APInt based is a pretty heavy for this commit.
-    Cases.push_back(Case(R.getLow().toConstantInt(),
-                         R.getHigh().toConstantInt(), MBB, W));
+    Cases.push_back(Case(C.first.getLow().toConstantInt(),
+                         C.first.getHigh().toConstantInt(), C.second, W));
     
-    if (R.getLow() != R.getHigh())
+    if (C.first.getLow() != C.first.getHigh())
     // A range counts double, since it requires two compares.
     ++numCmps;
   }
diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp
index d2bd9d0284..1547439b5c 100644
--- a/lib/Transforms/Utils/LowerSwitch.cpp
+++ b/lib/Transforms/Utils/LowerSwitch.cpp
@@ -238,14 +238,13 @@ unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) {
   size_t numCmps = 0;
   for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(),
        e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
-    const IntegersSubsetToBB::RangeTy &R = i->first;
-    BasicBlock *S = i->second;
+    IntegersSubsetToBB::Cluster &C = *i;
     
     // FIXME: Currently work with ConstantInt based numbers.
     // Changing it to APInt based is a pretty heavy for this commit.
-    Cases.push_back(CaseRange(R.getLow().toConstantInt(),
-                              R.getHigh().toConstantInt(), S));
-    if (R.isSingleNumber())
+    Cases.push_back(CaseRange(C.first.getLow().toConstantInt(),
+                              C.first.getHigh().toConstantInt(), C.second));
+    if (C.first.isSingleNumber())
       // A range counts double, since it requires two compares.
       ++numCmps;
   }
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 4a58eb3d84..f37ea91397 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -56,12 +56,26 @@ DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 
 namespace {
+  /// ValueEqualityComparisonCase - Represents a case of a switch.
+  struct ValueEqualityComparisonCase {
+    ConstantInt *Value;
+    BasicBlock *Dest;
+
+    ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest)
+      : Value(Value), Dest(Dest) {}
+
+    bool operator<(ValueEqualityComparisonCase RHS) const {
+      // Comparing pointers is ok as we only rely on the order for uniquing.
+      return Value < RHS.Value;
+    }
+  };
+
 class SimplifyCFGOpt {
   const TargetData *const TD;
 
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
-                               IntegersSubsetToBB &Mapping);   
+                               std::vector<ValueEqualityComparisonCase> &Cases);
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
@@ -518,25 +532,72 @@ Value *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) {
 /// decode all of the 'cases' that it represents and return the 'default' block.
 BasicBlock *SimplifyCFGOpt::
 GetValueEqualityComparisonCases(TerminatorInst *TI,
-                                IntegersSubsetToBB &Mapping) {
+                                std::vector<ValueEqualityComparisonCase>
+                                                                       &Cases) {
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
-    for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
-         i != e; ++i)
-      Mapping.add(i.getCaseValueEx(), i.getCaseSuccessor());
+    Cases.reserve(SI->getNumCases());
+    for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i)
+      Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(),
+                                                  i.getCaseSuccessor()));
     return SI->getDefaultDest();
   }
- 
+
   BranchInst *BI = cast<BranchInst>(TI);
   ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
-  IntegersSubsetToBB Builder;
-  
-  Mapping.add(
-      IntItem::fromConstantInt(GetConstantInt(ICI->getOperand(1), TD)),
-      BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE));
-  
+  BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE);
+  Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1),
+                                                             TD),
+                                              Succ));
   return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ);
 }
 
+
+/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries
+/// in the list that match the specified block.
+static void EliminateBlockCases(BasicBlock *BB,
+                              std::vector<ValueEqualityComparisonCase> &Cases) {
+  for (unsigned i = 0, e = Cases.size(); i != e; ++i)
+    if (Cases[i].Dest == BB) {
+      Cases.erase(Cases.begin()+i);
+      --i; --e;
+    }
+}
+
+/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as
+/// well.
+static bool
+ValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1,
+              std::vector<ValueEqualityComparisonCase > &C2) {
+  std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2;
+
+  // Make V1 be smaller than V2.
+  if (V1->size() > V2->size())
+    std::swap(V1, V2);
+
+  if (V1->size() == 0) return false;
+  if (V1->size() == 1) {
+    // Just scan V2.
+    ConstantInt *TheVal = (*V1)[0].Value;
+    for (unsigned i = 0, e = V2->size(); i != e; ++i)
+      if (TheVal == (*V2)[i].Value)
+        return true;
+  }
+
+  // Otherwise, just sort both lists and compare element by element.
+  array_pod_sort(V1->begin(), V1->end());
+  array_pod_sort(V2->begin(), V2->end());
+  unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size();
+  while (i1 != e1 && i2 != e2) {
+    if ((*V1)[i1].Value == (*V2)[i2].Value)
+      return true;
+    if ((*V1)[i1].Value < (*V2)[i2].Value)
+      ++i1;
+    else
+      ++i2;
+  }
+  return false;
+}
+
 /// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a
 /// terminator instruction and its block is known to only have a single
 /// predecessor block, check to see if that predecessor is also a value
@@ -555,27 +616,23 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
   if (ThisVal != PredVal) return false;  // Different predicates.
 
   // Find out information about when control will move from Pred to TI's block.
-  IntegersSubsetToBB PredCases;
+  std::vector<ValueEqualityComparisonCase> PredCases;
   BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(),
                                                         PredCases);
+  EliminateBlockCases(PredDef, PredCases);  // Remove default from cases.
 
-  // Remove default from cases.
-  PredCases.removeCase(PredDef);
-  
   // Find information about how control leaves this block.
-  IntegersSubsetToBB ThisCases;
+  std::vector<ValueEqualityComparisonCase> ThisCases;
   BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases);
+  EliminateBlockCases(ThisDef, ThisCases);  // Remove default from cases.
 
-  // Remove default from cases.
-  ThisCases.removeCase(ThisDef);
-  
   // If TI's block is the default block from Pred's comparison, potentially
   // simplify TI based on this knowledge.
   if (PredDef == TI->getParent()) {
     // If we are here, we know that the value is none of those cases listed in
     // PredCases.  If there are any cases in ThisCases that are in PredCases, we
     // can simplify TI.
-    if (!PredCases.isOverlapped(ThisCases))
+    if (!ValuesOverlap(PredCases, ThisCases))
       return false;
     
     if (isa<BranchInst>(TI)) {
@@ -587,7 +644,7 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
       (void) NI;
 
       // Remove PHI node entries for the dead edge.
-      ThisCases.begin()->second->removePredecessor(TI->getParent());
+      ThisCases[0].Dest->removePredecessor(TI->getParent());
 
       DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
            << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n");
@@ -598,45 +655,45 @@ SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
       
     SwitchInst *SI = cast<SwitchInst>(TI);
     // Okay, TI has cases that are statically dead, prune them away.
-    IRBuilder<> CodeBuilder(SI);
-    CodeBuilder.SetCurrentDebugLocation(SI->getDebugLoc());
+    SmallPtrSet<Constant*, 16> DeadCases;
+    for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
+      DeadCases.insert(PredCases[i].Value);
 
     DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator()
                  << "Through successor TI: " << *TI);
 
-    // Okay, TI has cases that are statically dead, prune them away.
-    IntegersSubsetToBB NewThisCases;
-    IntegersSubsetToBB WastedCases;
-    ThisCases.diff(&NewThisCases, &WastedCases, 0, PredCases);
-    
-    IntegersSubsetToBB::Cases Cases;
-    NewThisCases.getCases(Cases, true/*temporary prevent complex cases*/);
-    
-    SwitchInst *NewSI =
-        CodeBuilder.CreateSwitch(ThisVal, SI->getDefaultDest(), Cases.size());
-    
-    for (IntegersSubsetToBB::RangeIterator i = WastedCases.begin(),
-                                           e = WastedCases.end(); i != e; ++i)
-      i->second->removePredecessor(TI->getParent());
-    
-    for (IntegersSubsetToBB::CasesIt i = Cases.begin(), e = Cases.end();
-         i != e; ++i)
-      NewSI->addCase(i->second, i->first);
-    
-    EraseTerminatorInstAndDCECond(SI);
-    DEBUG(dbgs() << "Leaving: " << *NewSI << "\n");
+    for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) {
+      --i;
+      if (DeadCases.count(i.getCaseValue())) {
+        i.getCaseSuccessor()->removePredecessor(TI->getParent());
+        SI->removeCase(i);
+      }
+    }
+
+    DEBUG(dbgs() << "Leaving: " << *TI << "\n");
     return true;
   }
   
   // Otherwise, TI's block must correspond to some matched value.  Find out
   // which value (or set of values) this is.
+  ConstantInt *TIV = 0;
   BasicBlock *TIBB = TI->getParent();
-  const IntItem* TIVIntITem = PredCases.getCaseSingleNumber(TIBB); 
-  assert(TIVIntITem && "No edge from pred to succ?");
+  for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
+    if (PredCases[i].Dest == TIBB) {
+      if (TIV != 0)
+        return false;  // Cannot handle multiple values coming to this block.
+      TIV = PredCases[i].Value;
+    }
+  assert(TIV && "No edge from pred to succ?");
 
   // Okay, we found the one constant that our value can be if we get into TI's
   // BB.  Find out which successor will unconditionally be branched to.
-  BasicBlock *TheRealDest = ThisCases.findSuccessor(*TIVIntITem);
+  BasicBlock *TheRealDest = 0;
+  for (unsigned i = 0, e = ThisCases.size(); i != e; ++i)
+    if (ThisCases[i].Value == TIV) {
+      TheRealDest = ThisCases[i].Dest;
+      break;
+    }
 
   // If not handled by any explicit cases, it is handled by the default case.
   if (TheRealDest == 0) TheRealDest = ThisDef;
@@ -702,10 +759,10 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
 
     if (PCV == CV && SafeToMergeTerminators(TI, PTI)) {
       // Figure out which 'cases' to copy from SI to PSI.
-      IntegersSubsetToBB BBCases;
+      std::vector<ValueEqualityComparisonCase> BBCases;
       BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases);
 
-      IntegersSubsetToBB PredCases;
+      std::vector<ValueEqualityComparisonCase> PredCases;
       BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases);
 
       // Based on whether the default edge from PTI goes to BB or not, fill in
@@ -716,51 +773,61 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
       if (PredDefault == BB) {
         // If this is the default destination from PTI, only the edges in TI
         // that don't occur in PTI, or that branch to BB will be activated.
-                
-        PredCases.removeCase(BB);
-        IntegersSubsetToBB NewBBCases;
-        BBCases.diff(&NewBBCases, 0, 0, PredCases);
-        PredCases.add(NewBBCases);
-        for (IntegersSubsetToBB::RangeIterator i = NewBBCases.begin(),
-                                               e = NewBBCases.end(); i != e; ++i)
-          NewSuccessors.push_back(i->second);
-
-        // Replace the default if needed.
+        std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
+        for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
+          if (PredCases[i].Dest != BB)
+            PTIHandled.insert(PredCases[i].Value);
+          else {
+            // The default destination is BB, we don't need explicit targets.
+            std::swap(PredCases[i], PredCases.back());
+            PredCases.pop_back();
+            --i; --e;
+          }
+
+        // Reconstruct the new switch statement we will be building.
         if (PredDefault != BBDefault) {
           PredDefault->removePredecessor(Pred);
           PredDefault = BBDefault;
           NewSuccessors.push_back(BBDefault);
         }
+        for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
+          if (!PTIHandled.count(BBCases[i].Value) &&
+              BBCases[i].Dest != BBDefault) {
+            PredCases.push_back(BBCases[i]);
+            NewSuccessors.push_back(BBCases[i].Dest);
+          }
 
       } else {
         // If this is not the default destination from PSI, only the edges
         // in SI that occur in PSI with a destination of BB will be
         // activated.
-        IntegersSubsetToBB BBPredCase;
-        PredCases.detachCase(BBPredCase, BB);
-        IntegersSubsetToBB CasesWithBBDef;
-        IntegersSubsetToBB InharitedCases;
+        std::set<ConstantInt*, ConstantIntOrdering> PTIHandled;
+        for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
+          if (PredCases[i].Dest == BB) {
+            PTIHandled.insert(PredCases[i].Value);
+            std::swap(PredCases[i], PredCases.back());
+            PredCases.pop_back();
+            --i; --e;
+          }
 
         // Okay, now we know which constants were sent to BB from the
         // predecessor.  Figure out where they will all go now.
-        if (!BBPredCase.empty()) {
-          BBCases.diff(
-              0, // LHS excl RHS
-              &InharitedCases, // intersection
-              &CasesWithBBDef, // RHS excl LHS
-              BBPredCase);     // RHS.
-        }
-        PredCases.add(InharitedCases);
-        for (IntegersSubsetToBB::RangeIterator i = InharitedCases.begin(),
-                                               e = InharitedCases.end();
-                                               i != e; ++i)
-          NewSuccessors.push_back(i->second);
-        
+        for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
+          if (PTIHandled.count(BBCases[i].Value)) {
+            // If this is one we are capable of getting...
+            PredCases.push_back(BBCases[i]);
+            NewSuccessors.push_back(BBCases[i].Dest);
+            PTIHandled.erase(BBCases[i].Value);// This constant is taken care of
+          }
+
         // If there are any constants vectored to BB that TI doesn't handle,
         // they must go to the default destination of TI.
-        PredCases.add(CasesWithBBDef, BBDefault);
-        for (unsigned i = 0, e = CasesWithBBDef.size(); i != e; ++i)
+        for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 
+                                    PTIHandled.begin(),
+               E = PTIHandled.end(); I != E; ++I) {
+          PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault));
           NewSuccessors.push_back(BBDefault);
+        }
       }
 
       // Okay, at this point, we know which new successor Pred will get.  Make
@@ -781,12 +848,8 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
       SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault,
                                                PredCases.size());
       NewSI->setDebugLoc(PTI->getDebugLoc());
-      IntegersSubsetToBB::Cases Cases;
-      PredCases.getCases(Cases, true/*temporary prevent complex case*/);
-      
-      for (IntegersSubsetToBB::CasesIt i = Cases.begin(), e = Cases.end();
-           i != e; ++i)
-        NewSI->addCase(i->second, i->first);
+      for (unsigned i = 0, e = PredCases.size(); i != e; ++i)
+        NewSI->addCase(PredCases[i].Value, PredCases[i].Dest);
 
       EraseTerminatorInstAndDCECond(PTI);