Do not copy gigantic switch instructions

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

2 files changed, 19 insertions, 2 deletions

diff --git a/lib/Transforms/Scalar/TailDuplication.cpp b/lib/Transforms/Scalar/TailDuplication.cpp
index a3980b342c..00d7f26303 100644
--- a/lib/Transforms/Scalar/TailDuplication.cpp
+++ b/lib/Transforms/Scalar/TailDuplication.cpp
@@ -91,7 +91,8 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
   if (Dest == BI->getParent()) return false;        // Do not loop infinitely!
 
   // Do not inline a block if we will just get another branch to the same block!
-  if (BranchInst *DBI = dyn_cast<BranchInst>(Dest->getTerminator()))
+  TerminatorInst *DTI = Dest->getTerminator();
+  if (BranchInst *DBI = dyn_cast<BranchInst>(DTI))
     if (DBI->isUnconditional() && DBI->getSuccessor(0) == Dest)
       return false;                                 // Do not loop infinitely!
 
@@ -110,6 +111,15 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
 
   for (unsigned Size = 0; I != Dest->end(); ++Size, ++I)
     if (Size == 6) return false;  // The block is too large...
+
+  // Do not tail duplicate a block that has thousands of successors into a block
+  // with a single successor if the block has many other predecessors.  This can
+  // cause an N^2 explosion in CFG edges (and PHI node entries), as seen in
+  // cases that have a large number of indirect gotos.
+  if (DTI->getNumSuccessors() > 8)
+    if (std::distance(PI, PE) * DTI->getNumSuccessors() > 128)
+      return false;
+
   return true;  
 }
 
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 089d0ac86e..09153ed3bb 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -331,8 +331,15 @@ static void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred,
 // isValueEqualityComparison - Return true if the specified terminator checks to
 // see if a value is equal to constant integer value.
 static Value *isValueEqualityComparison(TerminatorInst *TI) {
-  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+    // Do not permit merging of large switch instructions into their
+    // predecessors unless there is only one predecessor.
+    if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()),
+                                               pred_end(SI->getParent())) > 128)
+      return 0;
+
     return SI->getCondition();
+  }
   if (BranchInst *BI = dyn_cast<BranchInst>(TI))
     if (BI->isConditional() && BI->getCondition()->hasOneUse())
       if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition()))