Restore minor deletion.

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

3 files changed, 143 insertions, 113 deletions

diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp
index 9c09f5c74e..342b1e563d 100644
--- a/lib/Transforms/Scalar/CodeGenPrepare.cpp
+++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp
@@ -52,7 +52,7 @@ namespace {
 
     /// BackEdges - Keep a set of all the loop back edges.
     ///
-    SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> BackEdges;
+    SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges;
   public:
     static char ID; // Pass identification, replacement for typeid
     explicit CodeGenPrepare(const TargetLowering *tli = 0)
@@ -69,7 +69,7 @@ namespace {
     bool OptimizeInlineAsmInst(Instruction *I, CallSite CS,
                                DenseMap<Value*,Value*> &SunkAddrs);
     bool OptimizeExtUses(Instruction *I);
-    void findLoopBackEdges(Function &F);
+    void findLoopBackEdges(const Function &F);
   };
 }
 
@@ -83,45 +83,11 @@ FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) {
 
 /// findLoopBackEdges - Do a DFS walk to find loop back edges.
 ///
-void CodeGenPrepare::findLoopBackEdges(Function &F) {
-  SmallPtrSet<BasicBlock*, 8> Visited;
-  SmallVector<std::pair<BasicBlock*, succ_iterator>, 8> VisitStack;
-  SmallPtrSet<BasicBlock*, 8> InStack;
-
-  BasicBlock *BB = &F.getEntryBlock();
-  if (succ_begin(BB) == succ_end(BB))
-    return;
-  Visited.insert(BB);
-  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-  InStack.insert(BB);
-  do {
-    std::pair<BasicBlock*, succ_iterator> &Top = VisitStack.back();
-    BasicBlock *ParentBB = Top.first;
-    succ_iterator &I = Top.second;
-
-    bool FoundNew = false;
-    while (I != succ_end(ParentBB)) {
-      BB = *I++;
-      if (Visited.insert(BB)) {
-        FoundNew = true;
-        break;
-      }
-      // Successor is in VisitStack, it's a back edge.
-      if (InStack.count(BB))
-        BackEdges.insert(std::make_pair(ParentBB, BB));
-    }
-
-    if (FoundNew) {
-      // Go down one level if there is a unvisited successor.
-      InStack.insert(BB);
-      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-    } else {
-      // Go up one level.
-      std::pair<BasicBlock*, succ_iterator> &Pop = VisitStack.back();
-      InStack.erase(Pop.first);
-      VisitStack.pop_back();
-    }
-  } while (!VisitStack.empty());
+void CodeGenPrepare::findLoopBackEdges(const Function &F) {
+  SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
+  FindFunctionBackedges(F, Edges);
+  
+  BackEdges.insert(Edges.begin(), Edges.end());
 }
 
 
@@ -328,7 +294,8 @@ void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
 /// predecessor of the succ that is empty (and thus has no phi nodes), use it
 /// instead of introducing a new block.
 static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum,
-                     SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> &BackEdges,
+                     SmallSet<std::pair<const BasicBlock*,
+                                        const BasicBlock*>, 8> &BackEdges,
                              Pass *P) {
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *Dest = TI->getSuccessor(SuccNum);
diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp
index 69d17993b5..c0ca2df1ce 100644
--- a/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/lib/Transforms/Scalar/JumpThreading.cpp
@@ -15,17 +15,19 @@
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/IntrinsicInst.h"
 #include "llvm/Pass.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/ValueHandle.h"
 using namespace llvm;
 
 STATISTIC(NumThreads, "Number of jumps threaded");
@@ -55,6 +57,11 @@ namespace {
   ///
   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
     TargetData *TD;
+#ifdef NDEBUG
+    SmallPtrSet<BasicBlock*, 16> LoopHeaders;
+#else
+    SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders;
+#endif
   public:
     static char ID; // Pass identification
     JumpThreading() : FunctionPass(&ID) {}
@@ -64,8 +71,11 @@ namespace {
     }
 
     bool runOnFunction(Function &F);
+    void FindLoopHeaders(Function &F);
+    
     bool ProcessBlock(BasicBlock *BB);
-    void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
+    bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB,
+                    unsigned JumpThreadCost);
     BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
     bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
     bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
@@ -91,6 +101,8 @@ bool JumpThreading::runOnFunction(Function &F) {
   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
   TD = &getAnalysis<TargetData>();
   
+  FindLoopHeaders(F);
+  
   bool AnotherIteration = true, EverChanged = false;
   while (AnotherIteration) {
     AnotherIteration = false;
@@ -108,6 +120,7 @@ bool JumpThreading::runOnFunction(Function &F) {
           BB != &BB->getParent()->getEntryBlock()) {
         DOUT << "  JT: Deleting dead block '" << BB->getNameStart()
              << "' with terminator: " << *BB->getTerminator();
+        LoopHeaders.erase(BB);
         DeleteDeadBlock(BB);
         Changed = true;
       }
@@ -115,9 +128,35 @@ bool JumpThreading::runOnFunction(Function &F) {
     AnotherIteration = Changed;
     EverChanged |= Changed;
   }
+  
+  LoopHeaders.clear();
   return EverChanged;
 }
 
+/// FindLoopHeaders - We do not want jump threading to turn proper loop
+/// structures into irreducible loops.  Doing this breaks up the loop nesting
+/// hierarchy and pessimizes later transformations.  To prevent this from
+/// happening, we first have to find the loop headers.  Here we approximate this
+/// by finding targets of backedges in the CFG.
+///
+/// Note that there definitely are cases when we want to allow threading of
+/// edges across a loop header.  For example, threading a jump from outside the
+/// loop (the preheader) to an exit block of the loop is definitely profitable.
+/// It is also almost always profitable to thread backedges from within the loop
+/// to exit blocks, and is often profitable to thread backedges to other blocks
+/// within the loop (forming a nested loop).  This simple analysis is not rich
+/// enough to track all of these properties and keep it up-to-date as the CFG
+/// mutates, so we don't allow any of these transformations.
+///
+void JumpThreading::FindLoopHeaders(Function &F) {
+  SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
+  FindFunctionBackedges(F, Edges);
+  
+  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
+    LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second));
+}
+
+
 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
 /// value for the PHI, factor them together so we get one block to thread for
 /// the whole group.
@@ -191,6 +230,10 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
   if (BasicBlock *SinglePred = BB->getSinglePredecessor())
     if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
         SinglePred != BB) {
+      // If SinglePred was a loop header, BB becomes one.
+      if (LoopHeaders.erase(SinglePred))
+        LoopHeaders.insert(BB);
+      
       // Remember if SinglePred was the entry block of the function.  If so, we
       // will need to move BB back to the entry position.
       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
@@ -389,22 +432,8 @@ bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB,
   // Next, figure out which successor we are threading to.
   BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-         << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
-       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
-       << ", across block:\n    "
-       << *BB << "\n";
-  
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
@@ -675,22 +704,8 @@ bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
   }
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-         << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
-       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
-       << ", across block:\n    "
-       << *BB << "\n";
-       
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
@@ -751,22 +766,8 @@ bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
   // 'true' block.
   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-    << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
-       << "' to '" << SuccBB->getNameStart() << "' with cost: "
-       << JumpThreadCost << ", across block:\n    "
-       << *BB << "\n";
-  
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
@@ -829,32 +830,40 @@ bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
   // Next, get our successor.
   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
   
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
+}
+
+
+/// ThreadEdge - We have decided that it is safe and profitable to thread an
+/// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
+/// change.
+bool JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
+                               BasicBlock *SuccBB, unsigned JumpThreadCost) {
+
   // If threading to the same block as we come from, we would infinite loop.
   if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-    << "' - would thread to self!\n";
+    DOUT << "  Not threading across BB '" << BB->getNameStart()
+         << "' - would thread to self!\n";
     return false;
   }
   
-  
+  // If threading this would thread across a loop header, don't thread the edge.
+  // See the comments above FindLoopHeaders for justifications and caveats.
+  if (LoopHeaders.count(BB)) {
+    DOUT << "  Not threading from '" << PredBB->getNameStart()
+         << "' across loop header BB '" << BB->getNameStart()
+         << "' to dest BB '" << SuccBB->getNameStart()
+         << "' - it might create an irreducible loop!\n";
+    return false;
+  }
+
   // And finally, do it!
-  DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
-       << "' to '" << SuccBB->getNameStart() << "' with cost: "
-       << JumpThreadCost << ", across block:\n    "
+  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
+       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
+       << ", across block:\n    "
        << *BB << "\n";
   
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
-}
-
-
-/// ThreadEdge - We have decided that it is safe and profitable to thread an
-/// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
-/// change.
-void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
-                               BasicBlock *SuccBB) {
-
   // Jump Threading can not update SSA properties correctly if the values
   // defined in the duplicated block are used outside of the block itself.  For
   // this reason, we spill all values that are used outside of BB to the stack.
@@ -938,4 +947,8 @@ void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
     
     RecursivelyDeleteTriviallyDeadInstructions(Inst);
   }
+  
+  // Threaded an edge!
+  ++NumThreads;
+  return true;
 }
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 076f89e337..0a6d7ef5db 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -442,6 +442,56 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
   return NewBB;
 }
 
+/// FindFunctionBackedges - Analyze the specified function to find all of the
+/// loop backedges in the function and return them.  This is a relatively cheap
+/// (compared to computing dominators and loop info) analysis.
+///
+/// The output is added to Result, as pairs of <from,to> edge info.
+void llvm::FindFunctionBackedges(const Function &F,
+     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
+  const BasicBlock *BB = &F.getEntryBlock();
+  if (succ_begin(BB) == succ_end(BB))
+    return;
+  
+  SmallPtrSet<const BasicBlock*, 8> Visited;
+  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
+  SmallPtrSet<const BasicBlock*, 8> InStack;
+  
+  Visited.insert(BB);
+  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+  InStack.insert(BB);
+  do {
+    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
+    const BasicBlock *ParentBB = Top.first;
+    succ_const_iterator &I = Top.second;
+    
+    bool FoundNew = false;
+    while (I != succ_end(ParentBB)) {
+      BB = *I++;
+      if (Visited.insert(BB)) {
+        FoundNew = true;
+        break;
+      }
+      // Successor is in VisitStack, it's a back edge.
+      if (InStack.count(BB))
+        Result.push_back(std::make_pair(ParentBB, BB));
+    }
+    
+    if (FoundNew) {
+      // Go down one level if there is a unvisited successor.
+      InStack.insert(BB);
+      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+    } else {
+      // Go up one level.
+      InStack.erase(VisitStack.pop_back_val().first);
+    }
+  } while (!VisitStack.empty());
+  
+  
+}
+
+
+
 /// AreEquivalentAddressValues - Test if A and B will obviously have the same
 /// value. This includes recognizing that %t0 and %t1 will have the same
 /// value in code like this: