diff options
| -rw-r--r-- | lib/Transforms/Scalar/ObjCARC.cpp | 132 |
1 files changed, 94 insertions, 38 deletions
diff --git a/lib/Transforms/Scalar/ObjCARC.cpp b/lib/Transforms/Scalar/ObjCARC.cpp index e62b91a256..ab23884bb0 100644 --- a/lib/Transforms/Scalar/ObjCARC.cpp +++ b/lib/Transforms/Scalar/ObjCARC.cpp @@ -896,8 +896,9 @@ bool ObjCARCExpand::runOnFunction(Function &F) { #include "llvm/LLVMContext.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/CFG.h" -#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/DenseSet.h" STATISTIC(NumNoops, "Number of no-op objc calls eliminated"); STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); @@ -2490,18 +2491,16 @@ ObjCARCOpt::VisitTopDown(BasicBlock *BB, if (Pred == BB) continue; DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred); - assert(I != BBStates.end()); // If we haven't seen this node yet, then we've found a CFG cycle. // Be optimistic here; it's CheckForCFGHazards' job detect trouble. - if (!I->second.isVisitedTopDown()) + if (I == BBStates.end() || !I->second.isVisitedTopDown()) continue; MyStates.InitFromPred(I->second); while (PI != PE) { Pred = *PI++; if (Pred != BB) { I = BBStates.find(Pred); - assert(I != BBStates.end()); - if (I->second.isVisitedTopDown()) + if (I == BBStates.end() || I->second.isVisitedTopDown()) MyStates.MergePred(I->second); } } @@ -2657,49 +2656,106 @@ ObjCARCOpt::VisitTopDown(BasicBlock *BB, return NestingDetected; } -// Visit - Visit the function both top-down and bottom-up. -bool -ObjCARCOpt::Visit(Function &F, - DenseMap<const BasicBlock *, BBState> &BBStates, - MapVector<Value *, RRInfo> &Retains, - DenseMap<Value *, RRInfo> &Releases) { - // Use reverse-postorder on the reverse CFG for bottom-up, because we - // magically know that loops will be well behaved, i.e. they won't repeatedly - // call retain on a single pointer without doing a release. We can't use - // ReversePostOrderTraversal here because we want to walk up from each - // function exit point. +static void +ComputePostOrders(Function &F, + SmallVectorImpl<BasicBlock *> &PostOrder, + SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder) { + /// Backedges - Backedges detected in the DFS. These edges will be + /// ignored in the reverse-CFG DFS, so that loops with multiple exits will be + /// traversed in the desired order. + DenseSet<std::pair<BasicBlock *, BasicBlock *> > Backedges; + + /// Visited - The visited set, for doing DFS walks. SmallPtrSet<BasicBlock *, 16> Visited; - SmallVector<std::pair<BasicBlock *, pred_iterator>, 16> Stack; - SmallVector<BasicBlock *, 16> Order; + + // Do DFS, computing the PostOrder. + SmallPtrSet<BasicBlock *, 16> OnStack; + SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack; + BasicBlock *EntryBB = &F.getEntryBlock(); + SuccStack.push_back(std::make_pair(EntryBB, succ_begin(EntryBB))); + Visited.insert(EntryBB); + OnStack.insert(EntryBB); + do { + dfs_next_succ: + succ_iterator End = succ_end(SuccStack.back().first); + while (SuccStack.back().second != End) { + BasicBlock *BB = *SuccStack.back().second++; + if (Visited.insert(BB)) { + SuccStack.push_back(std::make_pair(BB, succ_begin(BB))); + OnStack.insert(BB); + goto dfs_next_succ; + } + if (OnStack.count(BB)) + Backedges.insert(std::make_pair(SuccStack.back().first, BB)); + } + OnStack.erase(SuccStack.back().first); + PostOrder.push_back(SuccStack.pop_back_val().first); + } while (!SuccStack.empty()); + + Visited.clear(); + + // Compute the exits, which are the starting points for reverse-CFG DFS. + SmallVector<BasicBlock *, 4> Exits; for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { BasicBlock *BB = I; if (BB->getTerminator()->getNumSuccessors() == 0) - Stack.push_back(std::make_pair(BB, pred_begin(BB))); + Exits.push_back(BB); } - while (!Stack.empty()) { - pred_iterator End = pred_end(Stack.back().first); - while (Stack.back().second != End) { - BasicBlock *BB = *Stack.back().second++; - if (Visited.insert(BB)) - Stack.push_back(std::make_pair(BB, pred_begin(BB))); - } - Order.push_back(Stack.pop_back_val().first); + + // Do reverse-CFG DFS, computing the reverse-CFG PostOrder. + SmallVector<std::pair<BasicBlock *, pred_iterator>, 16> PredStack; + for (SmallVectorImpl<BasicBlock *>::iterator I = Exits.begin(), E = Exits.end(); + I != E; ++I) { + BasicBlock *ExitBB = *I; + PredStack.push_back(std::make_pair(ExitBB, pred_begin(ExitBB))); + Visited.insert(ExitBB); + while (!PredStack.empty()) { + reverse_dfs_next_succ: + pred_iterator End = pred_end(PredStack.back().first); + while (PredStack.back().second != End) { + BasicBlock *BB = *PredStack.back().second++; + // Skip backedges detected in the forward-CFG DFS. + if (Backedges.count(std::make_pair(BB, PredStack.back().first))) + continue; + if (Visited.insert(BB)) { + PredStack.push_back(std::make_pair(BB, pred_begin(BB))); + goto reverse_dfs_next_succ; + } + } + ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first); + } } +} + +// Visit - Visit the function both top-down and bottom-up. +bool +ObjCARCOpt::Visit(Function &F, + DenseMap<const BasicBlock *, BBState> &BBStates, + MapVector<Value *, RRInfo> &Retains, + DenseMap<Value *, RRInfo> &Releases) { + + // Use reverse-postorder traversals, because we magically know that loops + // will be well behaved, i.e. they won't repeatedly call retain on a single + // pointer without doing a release. We can't use the ReversePostOrderTraversal + // class here because we want the reverse-CFG postorder to consider each + // function exit point, and we want to ignore selected cycle edges. + SmallVector<BasicBlock *, 16> PostOrder; + SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; + ComputePostOrders(F, PostOrder, ReverseCFGPostOrder); + + // Use reverse-postorder on the reverse CFG for bottom-up. bool BottomUpNestingDetected = false; for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = - Order.rbegin(), E = Order.rend(); I != E; ++I) { - BasicBlock *BB = *I; - BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains); - } + ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend(); + I != E; ++I) + BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains); - // Use regular reverse-postorder for top-down. + // Use reverse-postorder for top-down. bool TopDownNestingDetected = false; - typedef ReversePostOrderTraversal<Function *> RPOTType; - RPOTType RPOT(&F); - for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { - BasicBlock *BB = *I; - TopDownNestingDetected |= VisitTopDown(BB, BBStates, Releases); - } + for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = + PostOrder.rbegin(), E = PostOrder.rend(); + I != E; ++I) + TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases); return TopDownNestingDetected && BottomUpNestingDetected; } |