diff options
Diffstat (limited to 'llvm')
23 files changed, 731 insertions, 226 deletions
diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h index 6f9a6805f4f..9b102ffb203 100644 --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -417,14 +417,15 @@ class DominatorTreeBase { } /// findNearestCommonDominator - Find nearest common dominator basic block - /// for basic block A and B. If there is no such block then return NULL. + /// for basic block A and B. If there is no such block then return nullptr. NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { + assert(A && B && "Pointers are not valid"); assert(A->getParent() == B->getParent() && "Two blocks are not in same function"); // If either A or B is a entry block then it is nearest common dominator // (for forward-dominators). - if (!this->isPostDominator()) { + if (!isPostDominator()) { NodeT &Entry = A->getParent()->front(); if (A == &Entry || B == &Entry) return &Entry; @@ -580,6 +581,15 @@ class DominatorTreeBase { } DomTreeNodes.erase(BB); + + if (!IsPostDom) return; + + // Remember to update PostDominatorTree roots. + auto RIt = llvm::find(Roots, BB); + if (RIt != Roots.end()) { + std::swap(*RIt, Roots.back()); + Roots.pop_back(); + } } /// splitBlock - BB is split and now it has one successor. Update dominator @@ -595,7 +605,7 @@ class DominatorTreeBase { /// void print(raw_ostream &O) const { O << "=============================--------------------------------\n"; - if (this->isPostDominator()) + if (IsPostDominator) O << "Inorder PostDominator Tree: "; else O << "Inorder Dominator Tree: "; @@ -605,6 +615,14 @@ class DominatorTreeBase { // The postdom tree can have a null root if there are no returns. if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); + if (IsPostDominator) { + O << "Roots: "; + for (const NodePtr Block : Roots) { + Block->printAsOperand(O, false); + O << " "; + } + O << "\n"; + } } public: diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h index f23ee0acb1c..503ea763303 100644 --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -64,6 +64,7 @@ struct SemiNCAInfo { using NodePtr = typename DomTreeT::NodePtr; using NodeT = typename DomTreeT::NodeType; using TreeNodePtr = DomTreeNodeBase<NodeT> *; + using RootsT = decltype(DomTreeT::Roots); static constexpr bool IsPostDom = DomTreeT::IsPostDominator; // Information record used by Semi-NCA during tree construction. @@ -131,7 +132,11 @@ struct SemiNCAInfo { // Custom DFS implementation which can skip nodes based on a provided // predicate. It also collects ReverseChildren so that we don't have to spend // time getting predecessors in SemiNCA. - template <typename DescendCondition> + // + // If IsReverse is set to true, the DFS walk will be performed backwards + // relative to IsPostDom -- using reverse edges for dominators and forward + // edges for postdominators. + template <bool IsReverse = false, typename DescendCondition> unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum) { assert(V); @@ -148,7 +153,8 @@ struct SemiNCAInfo { BBInfo.Label = BB; NumToNode.push_back(BB); - for (const NodePtr Succ : ChildrenGetter<NodePtr, IsPostDom>::Get(BB)) { + constexpr bool Direction = IsReverse != IsPostDom; // XOR. + for (const NodePtr Succ : ChildrenGetter<NodePtr, Direction>::Get(BB)) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect // ReverseChildren. @@ -256,45 +262,214 @@ struct SemiNCAInfo { } } - template <typename DescendCondition> - unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { - unsigned Num = 0; + // PostDominatorTree always has a virtual root that represents a virtual CFG + // node that serves as a single exit from the function. All the other exits + // (CFG nodes with terminators and nodes in infinite loops are logically + // connected to this virtual CFG exit node). + // This functions maps a nullptr CFG node to the virtual root tree node. + void addVirtualRoot() { + assert(IsPostDom && "Only postdominators have a virtual root"); + assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed"); - // If the DT is a PostDomTree, always add a virtual root. - if (IsPostDom) { - auto &BBInfo = NodeToInfo[nullptr]; - BBInfo.DFSNum = BBInfo.Semi = ++Num; - BBInfo.Label = nullptr; + auto &BBInfo = NodeToInfo[nullptr]; + BBInfo.DFSNum = BBInfo.Semi = 1; + BBInfo.Label = nullptr; - NumToNode.push_back(nullptr); // NumToNode[n] = V; - } + NumToNode.push_back(nullptr); // NumToNode[1] = nullptr; + } - const unsigned InitialNum = Num; - for (auto *Root : DT.Roots) Num = runDFS(Root, Num, DC, InitialNum); + // For postdominators, nodes with no forward successors are trivial roots that + // are always selected as tree roots. Roots with forward successors correspond + // to CFG nodes within infinite loops. + static bool HasForwardSuccessors(const NodePtr N) { + assert(N && "N must be a valid node"); + using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>; + return TraitsTy::child_begin(N) != TraitsTy::child_end(N); + } - return Num; + static NodePtr GetEntryNode(const DomTreeT &DT) { + assert(DT.Parent && "Parent not set"); + return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent); } - static void FindAndAddRoots(DomTreeT &DT) { + // Finds all roots without relaying on the set of roots already stored in the + // tree. + // We define roots to be some non-redundant set of the CFG nodes + static RootsT FindRoots(const DomTreeT &DT) { assert(DT.Parent && "Parent pointer is not set"); - using TraitsTy = GraphTraits<typename DomTreeT::ParentPtr>; + RootsT Roots; + // For dominators, function entry CFG node is always a tree root node. + if (!IsPostDom) { + Roots.push_back(GetEntryNode(DT)); + return Roots; + } + + SemiNCAInfo SNCA; + + // PostDominatorTree always has a virtual root. + SNCA.addVirtualRoot(); + unsigned Num = 1; + + DEBUG(dbgs() << "\t\tLooking for trivial roots\n"); + + // Step #1: Find all the trivial roots that are going to will definitely + // remain tree roots. + unsigned Total = 0; + for (const NodePtr N : nodes(DT.Parent)) { + ++Total; + // If it has no *successors*, it is definitely a root. + if (!HasForwardSuccessors(N)) { + Roots.push_back(N); + // Run DFS not to walk this part of CFG later. + Num = SNCA.runDFS(N, Num, AlwaysDescend, 1); + DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N) + << "\n"); + DEBUG(dbgs() << "Last visited node: " + << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n"); + } + } + + DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n"); + + // Step #2: Find all non-trivial root candidates. Those are CFG nodes that + // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG + // nodes in infinite loops). + bool HasNonTrivialRoots = false; + // Accounting for the virtual exit, see if we had any reverse-unreachable + // nodes. + if (Total + 1 != Num) { + HasNonTrivialRoots = true; + // Make another DFS pass over all other nodes to find the + // reverse-unreachable blocks, and find the furthest paths we'll be able + // to make. + // Note that this looks N^2, but it's really 2N worst case, if every node + // is unreachable. This is because we are still going to only visit each + // unreachable node once, we may just visit it in two directions, + // depending on how lucky we get. + SmallPtrSet<NodePtr, 4> ConnectToExitBlock; + for (const NodePtr I : nodes(DT.Parent)) { + if (SNCA.NodeToInfo.count(I) == 0) { + DEBUG(dbgs() << "\t\t\tVisiting node " << BlockNamePrinter(I) + << "\n"); + // Find the furthest away we can get by following successors, then + // follow them in reverse. This gives us some reasonable answer about + // the post-dom tree inside any infinite loop. In particular, it + // guarantees we get to the farthest away point along *some* + // path. This also matches the GCC's behavior. + // If we really wanted a totally complete picture of dominance inside + // this infinite loop, we could do it with SCC-like algorithms to find + // the lowest and highest points in the infinite loop. In theory, it + // would be nice to give the canonical backedge for the loop, but it's + // expensive and does not always lead to a minimal set of roots. + DEBUG(dbgs() << "\t\t\tRunning forward DFS\n"); + + const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num); + const NodePtr FurthestAway = SNCA.NumToNode[NewNum]; + DEBUG(dbgs() << "\t\t\tFound a new furthest away node " + << "(non-trivial root): " + << BlockNamePrinter(FurthestAway) << "\n"); + ConnectToExitBlock.insert(FurthestAway); + Roots.push_back(FurthestAway); + DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: " + << NewNum << "\n\t\t\tRemoving DFS info\n"); + for (unsigned i = NewNum; i > Num; --i) { + const NodePtr N = SNCA.NumToNode[i]; + DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for " + << BlockNamePrinter(N) << "\n"); + SNCA.NodeToInfo.erase(N); + SNCA.NumToNode.pop_back(); + } + const unsigned PrevNum = Num; + DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n"); + Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1); + for (unsigned i = PrevNum + 1; i <= Num; ++i) + DEBUG(dbgs() << "\t\t\t\tfound node " + << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); + } + } + } + + DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n"); + DEBUG(dbgs() << "Discovered CFG nodes:\n"); + DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs() + << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); + + assert((Total + 1 == Num) && "Everything should have been visited"); + + // Step #3: If we found some non-trivial roots, make them non-redundant. + if (HasNonTrivialRoots) RemoveRedundantRoots(DT, Roots); + + DEBUG(dbgs() << "Found roots: "); + DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " "); + DEBUG(dbgs() << "\n"); + + return Roots; + } + + // This function only makes sense for postdominators. + // We define roots to be some set of CFG nodes where (reverse) DFS walks have + // to start in order to visit all the CFG nodes (including the + // reverse-unreachable ones). + // When the search for non-trivial roots is done it may happen that some of + // the non-trivial roots are reverse-reachable from other non-trivial roots, + // which makes them redundant. This function removes them from the set of + // input roots. + static void RemoveRedundantRoots(const DomTreeT &DT, RootsT &Roots) { + assert(IsPostDom && "This function is for postdominators only"); + DEBUG(dbgs() << "Removing redundant roots\n"); + + SemiNCAInfo SNCA; + + for (unsigned i = 0; i < Roots.size(); ++i) { + auto &Root = Roots[i]; + // Trivial roots are always non-redundant. + if (!HasForwardSuccessors(Root)) continue; + DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root) + << " remains a root\n"); + SNCA.clear(); + // Do a forward walk looking for the other roots. + const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0); + // Skip the start node and begin from the second one (note that DFS uses + // 1-based indexing). + for (unsigned x = 2; x <= Num; ++x) { + const NodePtr N = SNCA.NumToNode[x]; + // If we wound another root in a (forward) DFS walk, remove the current + // root from the set of roots, as it is reverse-reachable from the other + // one. + if (llvm::find(Roots, N) != Roots.end()) { + DEBUG(dbgs() << "\tForward DFS walk found another root " + << BlockNamePrinter(N) << "\n\tRemoving root " + << BlockNamePrinter(Root) << "\n"); + std::swap(Root, Roots.back()); + Roots.pop_back(); + + // Root at the back takes the current root's place. + // Start the next loop iteration with the same index. + --i; + break; + } + } + } + } + + template <typename DescendCondition> + void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { if (!IsPostDom) { - // Dominators have a single root that is the function's entry. - NodeT *entry = TraitsTy::getEntryNode(DT.Parent); - DT.addRoot(entry); - } else { - // Initialize the roots list for PostDominators. - for (auto *Node : nodes(DT.Parent)) - if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node)) - DT.addRoot(Node); + assert(DT.Roots.size() == 1 && "Dominators should have a singe root"); + runDFS(DT.Roots[0], 0, DC, 0); + return; } + + addVirtualRoot(); + unsigned Num = 1; + for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0); } void calculateFromScratch(DomTreeT &DT) { // Step #0: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - FindAndAddRoots(DT); + DT.Roots = FindRoots(DT); doFullDFSWalk(DT, AlwaysDescend); runSemiNCA(DT); @@ -326,11 +501,11 @@ struct SemiNCAInfo { NodePtr ImmDom = getIDom(W); - // Get or calculate the node for the immediate dominator + // Get or calculate the node for the immediate dominator. TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT); // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode + // IDomNode. DT.DomTreeNodes[W] = IDomNode->addChild( llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode)); } @@ -367,13 +542,25 @@ struct SemiNCAInfo { }; static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { - assert(From && To && "Cannot connect nullptrs"); + assert((From || IsPostDom) && + "From has to be a valid CFG node or a virtual root"); + assert(To && "Cannot be a nullptr"); DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> " << BlockNamePrinter(To) << "\n"); - const TreeNodePtr FromTN = DT.getNode(From); - - // Ignore edges from unreachable nodes. - if (!FromTN) return; + TreeNodePtr FromTN = DT.getNode(From); + + if (!FromTN) { + // Ignore edges from unreachable nodes for (forward) dominators. + if (!IsPostDom) return; + + // The unreachable node becomes a new root -- a tree node for it. + TreeNodePtr VirtualRoot = DT.getNode(nullptr); + FromTN = + (DT.DomTreeNodes[From] = VirtualRoot->addChild( + llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot))) + .get(); + DT.Roots.push_back(From); + } DT.DFSInfoValid = false; @@ -384,13 +571,71 @@ struct SemiNCAInfo { InsertReachable(DT, FromTN, ToTN); } + // Determines if some existing root becomes reverse-reachable after the + // insertion. Rebuilds the whole tree if that situation happens. + static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const TreeNodePtr From, + const TreeNodePtr To) { + assert(IsPostDom && "This function is only for postdominators"); + // Destination node is not attached to the virtual root, so it cannot be a + // root. + if (!DT.isVirtualRoot(To->getIDom())) return false; + + auto RIt = llvm::find(DT.Roots, To->getBlock()); + if (RIt == DT.Roots.end()) + return false; // To is not a root, nothing to update. + + DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To) + << " is no longer a root\n\t\tRebuilding the tree!!!\n"); + + DT.recalculate(*DT.Parent); + return true; + } + + // Updates the set of roots after insertion or deletion. This ensures that + // roots are the same when after a series of updates and when the tree would + // be built from scratch. + static void UpdateRootsAfterUpdate(DomTreeT &DT) { + assert(IsPostDom && "This function is only for postdominators"); + + // The tree has only trivial roots -- nothing to update. + if (std::none_of(DT.Roots.begin(), DT.Roots.end(), HasForwardSuccessors)) + return; + + // Recalculate the set of roots. + DT.Roots = FindRoots(DT); + for (const NodePtr R : DT.Roots) { + const TreeNodePtr TN = DT.getNode(R); + // A CFG node was selected as a tree root, but the corresponding tree node + // is not connected to the virtual root. This is because the incremental + // algorithm does not really know or use the set of roots and can make a + // different (implicit) decision about which nodes within an infinite loop + // becomes a root. + if (DT.isVirtualRoot(TN->getIDom())) { + DEBUG(dbgs() << "Root " << BlockNamePrinter(R) + << " is not virtual root's child\n" + << "The entire tree needs to be rebuilt\n"); + // It should be possible to rotate the subtree instead of recalculating + // the whole tree, but this situation happens extremely rarely in + // practice. + DT.recalculate(*DT.Parent); + return; + } + } + } + // Handles insertion to a node already in the dominator tree. static void InsertReachable(DomTreeT &DT, const TreeNodePtr From, const TreeNodePtr To) { DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); + if (IsPostDom && UpdateRootsBeforeInsertion(DT, From, To)) return; + // DT.findNCD expects both pointers to be valid. When From is a virtual + // root, then its CFG block pointer is a nullptr, so we have to 'compute' + // the NCD manually. const NodePtr NCDBlock = - DT.findNearestCommonDominator(From->getBlock(), To->getBlock()); + (From->getBlock() && To->getBlock()) + ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) + : nullptr; assert(NCDBlock || DT.isPostDominator()); const TreeNodePtr NCD = DT.getNode(NCDBlock); assert(NCD); @@ -483,6 +728,7 @@ struct SemiNCAInfo { } UpdateLevelsAfterInsertion(II); + if (IsPostDom) UpdateRootsAfterUpdate(DT); } static void UpdateLevelsAfterInsertion(InsertionInfo &II) { @@ -548,40 +794,6 @@ struct SemiNCAInfo { DEBUG(DT.print(dbgs())); } - // Checks if the tree contains all reachable nodes in the input graph. - bool verifyReachability(const DomTreeT &DT) { - clear(); - doFullDFSWalk(DT, AlwaysDescend); - - for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); - const NodePtr BB = TN->getBlock(); - - // Virtual root has a corresponding virtual CFG node. - if (DT.isVirtualRoot(TN)) continue; - - if (NodeToInfo.count(BB) == 0) { - errs() << "DomTree node " << BlockNamePrinter(BB) - << " not found by DFS walk!\n"; - errs().flush(); - - return false; - } - } - - for (const NodePtr N : NumToNode) { - if (N && !DT.getNode(N)) { - errs() << "CFG node " << BlockNamePrinter(N) - << " not found in the DomTree!\n"; - errs().flush(); - - return false; - } - } - - return true; - } - static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { assert(From && To && "Cannot disconnect nullptrs"); DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> " @@ -621,6 +833,8 @@ struct SemiNCAInfo { DeleteReachable(DT, FromTN, ToTN); else DeleteUnreachable(DT, ToTN); + + if (IsPostDom) UpdateRootsAfterUpdate(DT); } // Handles deletions that leave destination nodes reachable. @@ -692,6 +906,17 @@ struct SemiNCAInfo { assert(ToTN); assert(ToTN->getBlock()); + if (IsPostDom) { + // Deletion makes a region reverse-unreachable and creates a new root. + // Simulate that by inserting an edge from the virtual root to ToTN and + // adding it as a new root. + DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n"); + DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n"); + DT.Roots.push_back(ToTN->getBlock()); + InsertReachable(DT, DT.getNode(nullptr), ToTN); + return; + } + SmallVector<NodePtr, 16> AffectedQueue; const unsigned Level = ToTN->getLevel(); @@ -791,6 +1016,83 @@ struct SemiNCAInfo { //===--------------- DomTree correctness verification ---------------------=== //~~ + // Check if the tree has correct roots. A DominatorTree always has a single + // root which is the function's entry node. A PostDominatorTree can have + // multiple roots - one for each node with no successors and for infinite + // loops. + bool verifyRoots(const DomTreeT &DT) { + if (!DT.Parent && !DT.Roots.empty()) { + errs() << "Tree has no parent but has roots!\n"; + errs().flush(); + return false; + } + + if (!IsPostDom) { + if (DT.Roots.empty()) { + errs() << "Tree doesn't have a root!\n"; + errs().flush(); + return false; + } + + if (DT.getRoot() != GetEntryNode(DT)) { + errs() << "Tree's root is not its parent's entry node!\n"; + errs().flush(); + return false; + } + } + + RootsT ComputedRoots = FindRoots(DT); + if (DT.Roots.size() != ComputedRoots.size() || + !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), + ComputedRoots.begin())) { + errs() << "Tree has different roots than freshly computed ones!\n"; + errs() << "\tPDT roots: "; + for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", "; + errs() << "\n\tComputed roots: "; + for (const NodePtr N : ComputedRoots) + errs() << BlockNamePrinter(N) << ", "; + errs() << "\n"; + errs().flush(); + return false; + } + + return true; + } + + // Checks if the tree contains all reachable nodes in the input graph. + bool verifyReachability(const DomTreeT &DT) { + clear(); + doFullDFSWalk(DT, AlwaysDescend); + + for (auto &NodeToTN : DT.DomTreeNodes) { + const TreeNodePtr TN = NodeToTN.second.get(); + const NodePtr BB = TN->getBlock(); + + // Virtual root has a corresponding virtual CFG node. + if (DT.isVirtualRoot(TN)) continue; + + if (NodeToInfo.count(BB) == 0) { + errs() << "DomTree node " << BlockNamePrinter(BB) + << " not found by DFS walk!\n"; + errs().flush(); + + return false; + } + } + + for (const NodePtr N : NumToNode) { + if (N && !DT.getNode(N)) { + errs() << "CFG node " << BlockNamePrinter(N) + << " not found in the DomTree!\n"; + errs().flush(); + + return false; + } + } + + return true; + } + // Check if for every parent with a level L in the tree all of its children // have level L + 1. static bool VerifyLevels(const DomTreeT &DT) { @@ -905,6 +1207,8 @@ struct SemiNCAInfo { const NodePtr BB = TN->getBlock(); if (!BB || TN->getChildren().empty()) continue; + DEBUG(dbgs() << "Verifying parent property of node " + << BlockNamePrinter(TN) << "\n"); clear(); doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) { return From != BB && To != BB; @@ -985,9 +1289,9 @@ void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, template <class DomTreeT> bool Verify(const DomTreeT &DT) { SemiNCAInfo<DomTreeT> SNCA; - return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && - SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) && - SNCA.verifySiblingProperty(DT); + return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) && + SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) && + SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT); } } // namespace DomTreeBuilder diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp index 5b467dc9fe1..9d45c3da38f 100644 --- a/llvm/lib/Transforms/Scalar/ADCE.cpp +++ b/llvm/lib/Transforms/Scalar/ADCE.cpp @@ -253,27 +253,23 @@ void AggressiveDeadCodeElimination::initialize() { } } - // Mark blocks live if there is no path from the block to the - // return of the function or a successor for which this is true. - // This protects IDFCalculator which cannot handle such blocks. - for (auto &BBInfoPair : BlockInfo) { - auto &BBInfo = BBInfoPair.second; - if (BBInfo.terminatorIsLive()) - continue; - auto *BB = BBInfo.BB; - if (!PDT.getNode(BB)) { - DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName() + // Mark blocks live if there is no path from the block to a + // return of the function. + // We do this by seeing which of the postdomtree root children exit the + // program, and for all others, mark the subtree live. + for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) { + auto *BB = PDTChild->getBlock(); + auto &Info = BlockInfo[BB]; + // Real function return + if (isa<ReturnInst>(Info.Terminator)) { + DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName() << '\n';); - markLive(BBInfo.Terminator); continue; } - for (auto *Succ : successors(BB)) - if (!PDT.getNode(Succ)) { - DEBUG(dbgs() << "Successor not post-dominated by return: " - << BB->getName() << '\n';); - markLive(BBInfo.Terminator); - break; - } + + // This child is something else, like an infinite loop. + for (auto DFNode : depth_first(PDTChild)) + markLive(BlockInfo[DFNode->getBlock()].Terminator); } // Treat the entry block as always live diff --git a/llvm/test/Analysis/PostDominators/infinite-loop.ll b/llvm/test/Analysis/PostDominators/infinite-loop.ll new file mode 100644 index 00000000000..5796b8614db --- /dev/null +++ b/llvm/test/Analysis/PostDominators/infinite-loop.ll @@ -0,0 +1,30 @@ +; RUN: opt < %s -postdomtree -analyze | FileCheck %s +; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s + +@a = external global i32, align 4 + +define void @fn1() { +entry: + store i32 5, i32* @a, align 4 + %call = call i32 (...) @foo() + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %entry + br label %loop + +loop: ; preds = %loop, %if.then + br label %loop + +if.end: ; preds = %entry + store i32 6, i32* @a, align 4 + ret void +} + +declare i32 @foo(...) + +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK: [2] %loop +; CHECK-NEXT: [3] %if.then +; CHECK: Roots: %if.end %loop diff --git a/llvm/test/Analysis/PostDominators/infinite-loop2.ll b/llvm/test/Analysis/PostDominators/infinite-loop2.ll new file mode 100644 index 00000000000..139abb76e95 --- /dev/null +++ b/llvm/test/Analysis/PostDominators/infinite-loop2.ll @@ -0,0 +1,34 @@ +; RUN: opt < %s -postdomtree -analyze | FileCheck %s +; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s + +@a = external global i32, align 4 + +define void @fn1() { +entry: + store i32 5, i32* @a, align 4 + %call = call i32 (...) @foo() + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %entry + br label %loop + +loop: ; preds = %loop, %if.then + %0 = load i32, i32* @a, align 4 + call void @bar(i32 %0) + br label %loop + +if.end: ; preds = %entry + store i32 6, i32* @a, align 4 + ret void +} + +declare i32 @foo(...) +declare void @bar(i32) + + +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK: [2] %loop +; CHECK-NEXT: [3] %if.then +; CHECK: Roots: %if.end %loop diff --git a/llvm/test/Analysis/PostDominators/infinite-loop3.ll b/llvm/test/Analysis/PostDominators/infinite-loop3.ll new file mode 100644 index 00000000000..f767df79d3a --- /dev/null +++ b/llvm/test/Analysis/PostDominators/infinite-loop3.ll @@ -0,0 +1,34 @@ +; RUN: opt < %s -postdomtree -analyze | FileCheck %s +; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s + +@a = external global i32, align 4 + +define void @fn1() { +entry: + store i32 5, i32* @a, align 4 + %call = call i32 (...) @foo() + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %entry, %loop + br label %loop + +loop: ; preds = %loop, %if.then + %0 = load i32, i32* @a, align 4 + call void @bar(i32 %0) + br i1 true, label %loop, label %if.then + +if.end: ; preds = %entry + store i32 6, i32* @a, align 4 + ret void +} + +declare i32 @foo(...) +declare void @bar(i32) + + +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK: [2] %loop +; CHECK-NEXT: [3] %if.then +; CHECK: Roots: %if.end %loop diff --git a/llvm/test/Analysis/PostDominators/pr24415.ll b/llvm/test/Analysis/PostDominators/pr24415.ll new file mode 100644 index 00000000000..536c36848b9 --- /dev/null +++ b/llvm/test/Analysis/PostDominators/pr24415.ll @@ -0,0 +1,18 @@ +; RUN: opt < %s -postdomtree -analyze | FileCheck %s +; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s + +; Function Attrs: nounwind ssp uwtable +define void @foo() { + br label %1 + +; <label>:1 ; preds = %0, %1 + br label %1 + ; No predecessors! + ret void +} + +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK-NEXT: [2] %2 +; CHECK-NEXT: [2] %1 +; CHECK-NEXT: [3] %0
\ No newline at end of file diff --git a/llvm/test/Analysis/PostDominators/pr6047_a.ll b/llvm/test/Analysis/PostDominators/pr6047_a.ll index ec1455b46fe..32ccbe61271 100644 --- a/llvm/test/Analysis/PostDominators/pr6047_a.ll +++ b/llvm/test/Analysis/PostDominators/pr6047_a.ll @@ -12,4 +12,10 @@ bb35.loopexit3: bb35: ret void } -; CHECK: [3] %entry + +;CHECK:Inorder PostDominator Tree: +;CHECK-NEXT: [1] <<exit node>> +;CHECK-NEXT: [2] %bb35 +;CHECK-NEXT: [3] %bb35.loopexit3 +;CHECK-NEXT: [2] %entry +;CHECK-NEXT: [2] %bb3.i diff --git a/llvm/test/Analysis/PostDominators/pr6047_b.ll b/llvm/test/Analysis/PostDominators/pr6047_b.ll index 7bd2c86b737..f1fbb648f53 100644 --- a/llvm/test/Analysis/PostDominators/pr6047_b.ll +++ b/llvm/test/Analysis/PostDominators/pr6047_b.ll @@ -16,4 +16,10 @@ bb35.loopexit3: bb35: ret void } -; CHECK: [4] %entry +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK-NEXT: [2] %bb35 +; CHECK-NEXT: [3] %bb35.loopexit3 +; CHECK-NEXT: [2] %a +; CHECK-NEXT: [2] %entry +; CHECK-NEXT: [2] %bb3.i
\ No newline at end of file diff --git a/llvm/test/Analysis/PostDominators/pr6047_c.ll b/llvm/test/Analysis/PostDominators/pr6047_c.ll index 08c9551f156..0eef023b418 100644 --- a/llvm/test/Analysis/PostDominators/pr6047_c.ll +++ b/llvm/test/Analysis/PostDominators/pr6047_c.ll @@ -144,4 +144,54 @@ bb35.loopexit3: bb35: ret void } -; CHECK: [3] %entry +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK-NEXT: [2] %bb35 +; CHECK-NEXT: [3] %bb +; CHECK-NEXT: [3] %bb.i +; CHECK-NEXT: [3] %_float32_unpack.exit +; CHECK-NEXT: [3] %bb.i5 +; CHECK-NEXT: [3] %_float32_unpack.exit8 +; CHECK-NEXT: [3] %bb32.preheader +; CHECK-NEXT: [3] %bb3 +; CHECK-NEXT: [3] %bb3.split.us +; CHECK-NEXT: [3] %bb.i4.us +; CHECK-NEXT: [3] %bb7.i.us +; CHECK-NEXT: [3] %bb.i4.us.backedge +; CHECK-NEXT: [3] %bb1.i.us +; CHECK-NEXT: [3] %bb6.i.us +; CHECK-NEXT: [3] %bb4.i.us +; CHECK-NEXT: [3] %bb8.i.us +; CHECK-NEXT: [3] %bb3.i.loopexit.us +; CHECK-NEXT: [3] %bb.nph21 +; CHECK-NEXT: [3] %bb4 +; CHECK-NEXT: [3] %bb5 +; CHECK-NEXT: [3] %bb14.preheader +; CHECK-NEXT: [3] %bb.nph18 +; CHECK-NEXT: [3] %bb8.us.preheader +; CHECK-NEXT: [3] %bb8.preheader +; CHECK-NEXT: [3] %bb8.us +; CHECK-NEXT: [3] %bb8 +; CHECK-NEXT: [3] %bb15.loopexit +; CHECK-NEXT: [3] %bb15.loopexit2 +; CHECK-NEXT: [3] %bb15 +; CHECK-NEXT: [3] %bb16 +; CHECK-NEXT: [3] %bb17.loopexit.split +; CHECK-NEXT: [3] %bb.nph14 +; CHECK-NEXT: [3] %bb19 +; CHECK-NEXT: [3] %bb20 +; CHECK-NEXT: [3] %bb29.preheader +; CHECK-NEXT: [3] %bb.nph +; CHECK-NEXT: [3] %bb23.us.preheader +; CHECK-NEXT: [3] %bb23.preheader +; CHECK-NEXT: [3] %bb23.us +; CHECK-NEXT: [3] %bb23 +; CHECK-NEXT: [3] %bb30.loopexit +; CHECK-NEXT: [3] %bb30.loopexit1 +; CHECK-NEXT: [3] %bb30 +; CHECK-NEXT: [3] %bb31 +; CHECK-NEXT: [3] %bb35.loopexit +; CHECK-NEXT: [3] %bb35.loopexit3 +; CHECK-NEXT: [2] %entry +; CHECK-NEXT: [2] %bb3.i +; CHECK-NEXT: Roots: %bb35 %bb3.i
\ No newline at end of file diff --git a/llvm/test/Analysis/PostDominators/pr6047_d.ll b/llvm/test/Analysis/PostDominators/pr6047_d.ll index 4cfa88029ae..45ed86c27f8 100644 --- a/llvm/test/Analysis/PostDominators/pr6047_d.ll +++ b/llvm/test/Analysis/PostDominators/pr6047_d.ll @@ -21,4 +21,12 @@ bb35.loopexit3: bb35: ret void } -; CHECK: [4] %entry +; CHECK: Inorder PostDominator Tree: +; CHECK-NEXT: [1] <<exit node>> +; CHECK-NEXT: [2] %bb35 +; CHECK-NEXT: [3] %bb35.loopexit3 +; CHECK-NEXT: [2] %c +; CHECK-NEXT: [3] %a +; CHECK-NEXT: [3] %entry +; CHECK-NEXT: [3] %b +; CHECK-NEXT: [2] %bb3.i
\ No newline at end of file diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop.ll b/llvm/test/Analysis/RegionInfo/infinite_loop.ll index d8412bf1ddd..4d9057e0406 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop.ll @@ -16,6 +16,4 @@ define void @normal_condition() nounwind { } ; CHECK-NOT: => ; CHECK: [0] 0 => <Function Return> -; CHECK: [1] 1 => 4 -; STAT: 2 region - The # of regions -; STAT: 1 region - The # of simple regions +; STAT: 1 region - The # of regions
\ No newline at end of file diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop_2.ll b/llvm/test/Analysis/RegionInfo/infinite_loop_2.ll index 4068babae4e..09feecd96f5 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop_2.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop_2.ll @@ -26,12 +26,9 @@ define void @normal_condition() nounwind { } ; CHECK-NOT: => ; CHECK: [0] 0 => <Function Return> -; CHECK: [1] 1 => 3 -; STAT: 2 region - The # of regions -; STAT: 1 region - The # of simple regions +; CHECK-NOT: [1] +; STAT: 1 region - The # of regions -; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4, -; BBIT: 1, 2, 5, 11, 6, 12, +; BBIT: 0, 1, 2, 5, 11, 6, 12, 3, 4, -; RNIT: 0, 1 => 3, 3, 4, -; RNIT: 1, 2, 5, 11, 6, 12, +; RNIT: 0, 1, 2, 5, 11, 6, 12, 3, 4, diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop_3.ll b/llvm/test/Analysis/RegionInfo/infinite_loop_3.ll index 055e5e1d550..00d555177af 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop_3.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop_3.ll @@ -38,16 +38,10 @@ define void @normal_condition() nounwind { ret void } ; CHECK-NOT: => -; CHECK: [0] 0 => <Function Return> -; CHECK-NEXT: [1] 1 => 3 -; CHECK-NEXT: [1] 7 => 1 -; STAT: 3 region - The # of regions -; STAT: 2 region - The # of simple regions +; CHECK:[0] 0 => <Function Return> +; CHECK-NOT: [1] +; STAT: 1 region - The # of regions ; BBIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14, -; BBIT: 7, 8, 9, 13, 10, 14, -; BBIT: 1, 2, 5, 11, 6, 12, -; RNIT: 0, 7 => 1, 1 => 3, 3, 4, -; RNIT: 7, 8, 9, 13, 10, 14, -; RNIT: 1, 2, 5, 11, 6, 12, +; RNIT: 0, 7, 1, 2, 5, 11, 6, 12, 3, 4, 8, 9, 13, 10, 14, diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop_4.ll b/llvm/test/Analysis/RegionInfo/infinite_loop_4.ll index 1c5bb74aed5..51d8ffe0d5b 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop_4.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop_4.ll @@ -38,12 +38,14 @@ define void @normal_condition() nounwind { } ; CHECK-NOT: => ; CHECK: [0] 0 => <Function Return> -; CHECK-NEXT: [1] 7 => 3 -; STAT: 2 region - The # of regions +; CHECK-NEXT: [1] 2 => 10 +; CHECK_NEXT: [2] 5 => 6 +; STAT: 3 region - The # of regions ; STAT: 1 region - The # of simple regions ; BBIT: 0, 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, 3, 4, -; BBIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, - -; RNIT: 0, 7 => 3, 3, 4, -; RNIT: 7, 1, 2, 5, 11, 6, 10, 8, 9, 13, 14, 12, +; BBIT: 2, 5, 11, 6, 12, +; BBIT: 5, 11, 12, +; RNIT: 0, 7, 1, 2 => 10, 10, 8, 9, 13, 14, 3, 4, +; RNIT: 2, 5 => 6, 6, +; RNIT: 5, 11, 12,
\ No newline at end of file diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop_5_a.ll b/llvm/test/Analysis/RegionInfo/infinite_loop_5_a.ll index b0e52861b7c..12796417351 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop_5_a.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop_5_a.ll @@ -19,6 +19,4 @@ define void @normal_condition() nounwind { ; CHECK: Region tree: ; CHECK-NEXT: [0] 0 => <Function Return> -; CHECK-NEXT: [1] 7 => 3 ; CHECK-NEXT: End region tree - diff --git a/llvm/test/Analysis/RegionInfo/infinite_loop_5_b.ll b/llvm/test/Analysis/RegionInfo/infinite_loop_5_b.ll index 49580c9de3d..9759ea873c5 100644 --- a/llvm/test/Analysis/RegionInfo/infinite_loop_5_b.ll +++ b/llvm/test/Analysis/RegionInfo/infinite_loop_5_b.ll @@ -21,5 +21,4 @@ define void @normal_condition() nounwind { ; CHECK: Region tree: ; CHECK-NEXT: [0] 0 => <Function Return> -; CHECK-NEXT: [1] 7 => 3 ; CHECK-NEXT: End region tree diff --git a/llvm/test/CodeGen/AMDGPU/branch-relaxation.ll b/llvm/test/CodeGen/AMDGPU/branch-relaxation.ll index 661a6bd9958..9edf439b586 100644 --- a/llvm/test/CodeGen/AMDGPU/branch-relaxation.ll +++ b/llvm/test/CodeGen/AMDGPU/branch-relaxation.ll @@ -428,24 +428,13 @@ endif: } ; si_mask_branch -; s_cbranch_execz -; s_branch ; GCN-LABEL: {{^}}analyze_mask_branch: ; GCN: v_cmp_lt_f32_e32 vcc ; GCN-NEXT: s_and_saveexec_b64 [[MASK:s\[[0-9]+:[0-9]+\]]], vcc ; GCN-NEXT: ; mask branch [[RET:BB[0-9]+_[0-9]+]] -; GCN-NEXT: s_cbranch_execz [[BRANCH_SKIP:BB[0-9]+_[0-9]+]] -; GCN-NEXT: s_branch [[LOOP_BODY:BB[0-9]+_[0-9]+]] -; GCN-NEXT: [[BRANCH_SKIP]]: ; %entry -; GCN-NEXT: s_getpc_b64 vcc -; GCN-NEXT: s_add_u32 vcc_lo, vcc_lo, [[RET]]-([[BRANCH_SKIP]]+4) -; GCN-NEXT: s_addc_u32 vcc_hi, vcc_hi, 0 -; GCN-NEXT: s_setpc_b64 vcc - -; GCN-NEXT: [[LOOP_BODY]]: ; %loop_body -; GCN: s_mov_b64 vcc, -1{{$}} +; GCN-NEXT: [[LOOP_BODY:BB[0-9]+_[0-9]+]]: ; %loop_body ; GCN: ;;#ASMSTART ; GCN: v_nop_e64 ; GCN: v_nop_e64 @@ -454,7 +443,6 @@ endif: ; GCN: v_nop_e64 ; GCN: v_nop_e64 ; GCN: ;;#ASMEND -; GCN-NEXT: s_cbranch_vccz [[RET]] ; GCN-NEXT: [[LONGBB:BB[0-9]+_[0-9]+]]: ; %loop_body ; GCN-NEXT: ; in Loop: Header=[[LOOP_BODY]] Depth=1 @@ -463,7 +451,7 @@ endif: ; GCN-NEXT: s_subb_u32 vcc_hi, vcc_hi, 0 ; GCN-NEXT: s_setpc_b64 vcc -; GCN-NEXT: [[RET]]: ; %Flow +; GCN-NEXT: [[RET]]: ; %ret ; GCN-NEXT: s_or_b64 exec, exec, [[MASK]] ; GCN: buffer_store_dword ; GCN-NEXT: s_endpgm diff --git a/llvm/test/CodeGen/ARM/struct-byval-frame-index.ll b/llvm/test/CodeGen/ARM/struct-byval-frame-index.ll index 68629d3581d..b3ed5de857b 100644 --- a/llvm/test/CodeGen/ARM/struct-byval-frame-index.ll +++ b/llvm/test/CodeGen/ARM/struct-byval-frame-index.ll @@ -4,22 +4,11 @@ ; generated. ; PR16393 -; We expect the spill to be generated in %if.end230 and the reloads in -; %if.end249 and %for.body285. +; We expect 4-byte spill and reload to be generated. ; CHECK: set_stored_macroblock_parameters -; CHECK: @ %if.end230 -; CHECK-NOT:@ %if. -; CHECK-NOT:@ %for. -; CHECK: str r{{.*}}, [sp, [[SLOT:#[0-9]+]]] @ 4-byte Spill -; CHECK: @ %if.end249 -; CHECK-NOT:@ %if. -; CHECK-NOT:@ %for. -; CHECK: ldr r{{.*}}, [sp, [[SLOT]]] @ 4-byte Reload -; CHECK: @ %for.body285 -; CHECK-NOT:@ %if. -; CHECK-NOT:@ %for. -; CHECK: ldr r{{.*}}, [sp, [[SLOT]]] @ 4-byte Reload +; CHECK: str r{{.*}}, [sp, {{#[0-9]+}}] @ 4-byte Spill +; CHECK: ldr r{{.*}}, [lr, {{#[0-9]+}}] @ 4-byte Reload target triple = "armv7l-unknown-linux-gnueabihf" diff --git a/llvm/test/CodeGen/Thumb2/v8_IT_5.ll b/llvm/test/CodeGen/Thumb2/v8_IT_5.ll index 5e7a40299ed..4e9ebac7d15 100644 --- a/llvm/test/CodeGen/Thumb2/v8_IT_5.ll +++ b/llvm/test/CodeGen/Thumb2/v8_IT_5.ll @@ -1,6 +1,6 @@ ; RUN: llc < %s -mtriple=thumbv8 -arm-atomic-cfg-tidy=0 | FileCheck %s ; RUN: llc < %s -mtriple=thumbv7 -arm-atomic-cfg-tidy=0 -arm-restrict-it | FileCheck %s -; CHECK: it ne +; CHECK: it ne ; CHECK-NEXT: cmpne ; CHECK-NEXT: bne [[JUMPTARGET:.LBB[0-9]+_[0-9]+]] ; CHECK: cbz @@ -9,9 +9,10 @@ ; CHECK-NEXT: b ; CHECK: [[JUMPTARGET]]:{{.*}}%if.else173 ; CHECK-NEXT: mov.w -; CHECK-NEXT: pop -; CHECK-NEXT: %if.else145 +; CHECK-NEXT: bx lr +; CHECK: %if.else145 ; CHECK-NEXT: mov.w +; CHECK: pop.w %struct.hc = type { i32, i32, i32, i32 } diff --git a/llvm/test/Transforms/StructurizeCFG/branch-on-argument.ll b/llvm/test/Transforms/StructurizeCFG/branch-on-argument.ll index 386994f1fd9..cdd4b70592b 100644 --- a/llvm/test/Transforms/StructurizeCFG/branch-on-argument.ll +++ b/llvm/test/Transforms/StructurizeCFG/branch-on-argument.ll @@ -3,14 +3,17 @@ ; CHECK-LABEL: @invert_branch_on_arg_inf_loop( ; CHECK: entry: ; CHECK: %arg.inv = xor i1 %arg, true -; CHECK: phi i1 [ false, %Flow1 ], [ %arg.inv, %entry ] define void @invert_branch_on_arg_inf_loop(i32 addrspace(1)* %out, i1 %arg) { entry: - br i1 %arg, label %for.end, label %for.body + br i1 %arg, label %for.end, label %sesestart +sesestart: + br label %for.body for.body: ; preds = %entry, %for.body store i32 999, i32 addrspace(1)* %out, align 4 - br label %for.body + br i1 %arg, label %for.body, label %seseend +seseend: + ret void for.end: ; preds = %Flow ret void diff --git a/llvm/test/Transforms/StructurizeCFG/no-branch-to-entry.ll b/llvm/test/Transforms/StructurizeCFG/no-branch-to-entry.ll index 1db1060ca82..b0897ee6c85 100644 --- a/llvm/test/Transforms/StructurizeCFG/no-branch-to-entry.ll +++ b/llvm/test/Transforms/StructurizeCFG/no-branch-to-entry.ll @@ -1,3 +1,10 @@ +; XFAIL: * + +; This test used to generate a region that caused it to delete the entry block, +; but it does not anymore after the changes to handling of infinite loops in the +; PostDominatorTree. +; TODO: This should be either replaced with another IR or deleted completely. + ; RUN: opt -S -o - -structurizecfg -verify-dom-info < %s | FileCheck %s ; CHECK-LABEL: @no_branch_to_entry_undef( diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp index ed8053ef5ab..bf5aced4928 100644 --- a/llvm/unittests/IR/DominatorTreeTest.cpp +++ b/llvm/unittests/IR/DominatorTreeTest.cpp @@ -327,7 +327,8 @@ TEST(DominatorTree, NonUniqueEdges) { } // Verify that the PDT is correctly updated in case an edge removal results -// in a new unreachable CFG node. +// in a new unreachable CFG node. Also make sure that the updated PDT is the +// same as a freshly recalculated one. // // For the following input code and initial PDT: // @@ -348,27 +349,18 @@ TEST(DominatorTree, NonUniqueEdges) { // CFG' PDT-updated // // A Exit -// | | -// B D +// | / | \ +// B C B D // | \ | -// v \ B -// / D \ -// C \ A -// | v +// v \ A +// / D +// C \ +// | \ // unreachable Exit // -// WARNING: PDT-updated is inconsistent with PDT-recalculated, which is -// constructed from CFG' when recalculating the PDT from scratch. -// -// PDT-recalculated +// Both the blocks that end with ret and with unreachable become trivial +// PostDomTree roots, as they have no successors. // -// Exit -// / | \ -// C B D -// | -// A -// -// TODO: document the wanted behavior after resolving this inconsistency. TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { StringRef ModuleString = "define void @f() {\n" @@ -395,7 +387,9 @@ TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { BasicBlock *C = &*FI++; BasicBlock *D = &*FI++; - assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_TRUE(DT->verify()); + EXPECT_TRUE(PDT->verify()); C->getTerminator()->eraseFromParent(); new UnreachableInst(C->getContext(), C); @@ -403,18 +397,23 @@ TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { DT->deleteEdge(C, B); PDT->deleteEdge(C, B); - EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_EQ(PDT->getNode(C), nullptr); - - PDT->recalculate(F); + EXPECT_TRUE(DT->verify()); + EXPECT_TRUE(PDT->verify()); EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); EXPECT_NE(PDT->getNode(C), nullptr); + + DominatorTree NDT(F); + EXPECT_EQ(DT->compare(NDT), 0); + + PostDomTree NPDT(F); + EXPECT_EQ(PDT->compare(NPDT), 0); }); } // Verify that the PDT is correctly updated in case an edge removal results -// in an infinite loop. +// in an infinite loop. Also make sure that the updated PDT is the +// same as a freshly recalculated one. // // Test case: // @@ -434,27 +433,26 @@ TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { // After deleting the edge C->B, C is part of an infinite reverse-unreachable // loop: // -// CFG' PDT' +// CFG' PDT' // // A Exit -// | | -// B D +// | / | \ +// B C B D // | \ | -// v \ B -// / D \ -// C \ A +// v \ A +// / D +// C \ // / \ v // ^ v Exit // \_/ // -// In PDT, D post-dominates B. We verify that this post-dominance -// relation is preserved _after_ deleting the edge C->B from CFG. -// -// As C now becomes reverse-unreachable, it is not anymore part of the -// PDT. We also verify this property. +// As C now becomes reverse-unreachable, it forms a new non-trivial root and +// gets connected to the virtual exit. +// D does not postdominate B anymore, because there are two forward paths from +// B to the virtual exit: +// - B -> C -> VirtualExit +// - B -> D -> VirtualExit. // -// TODO: Can we change the PDT definition such that C remains part of the -// CFG? TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { StringRef ModuleString = "define void @f() {\n" @@ -483,20 +481,25 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { BasicBlock *C = &*FI++; BasicBlock *D = &*FI++; - assert(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_TRUE(DT->verify()); + EXPECT_TRUE(PDT->verify()); auto SwitchC = cast<SwitchInst>(C->getTerminator()); SwitchC->removeCase(SwitchC->case_begin()); DT->deleteEdge(C, B); + EXPECT_TRUE(DT->verify()); PDT->deleteEdge(C, B); + EXPECT_TRUE(PDT->verify()); - EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_EQ(PDT->getNode(C), nullptr); + EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_NE(PDT->getNode(C), nullptr); - PDT->recalculate(F); + DominatorTree NDT(F); + EXPECT_EQ(DT->compare(NDT), 0); - EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_EQ(PDT->getNode(C), nullptr); + PostDomTree NPDT(F); + EXPECT_EQ(PDT->compare(NPDT), 0); }); } @@ -509,9 +512,9 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { // // A Exit // | / | \ -// B-- C B D -// | \ | -// v \ A +// B-- C2 B D +// | \ / | +// v \ C A // / D // C--C2 \ // / \ \ v @@ -521,27 +524,22 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { // After deleting the edge C->E, C is part of an infinite reverse-unreachable // loop: // -// CFG' PDT' +// CFG' PDT' // // A Exit -// | | -// B D +// | / | \ +// B C B D // | \ | -// v \ B -// / D \ -// C \ A +// v \ A +// / D +// C \ // / \ v // ^ v Exit // \_/ // -// In PDT, D does not post-dominate B. After the edge C->E is removed, a new -// post-dominance relation is introduced. -// -// As C now becomes reverse-unreachable, it is not anymore part of the -// PDT. We also verify this property. +// In PDT, D does not post-dominate B. After the edge C -> C2 is removed, +// C becomes a new nontrivial PDT root. // -// TODO: Can we change the PDT definition such that C remains part of the -// CFG, at best without loosing the dominance relation D postdom B. TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { StringRef ModuleString = "define void @f() {\n" @@ -573,24 +571,30 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { BasicBlock *C2 = &*FI++; BasicBlock *D = &*FI++; + EXPECT_TRUE(DT->verify()); + EXPECT_TRUE(PDT->verify()); + auto SwitchC = cast<SwitchInst>(C->getTerminator()); SwitchC->removeCase(SwitchC->case_begin()); DT->deleteEdge(C, C2); PDT->deleteEdge(C, C2); - C2->eraseFromParent(); + C2->removeFromParent(); EXPECT_EQ(DT->getNode(C2), nullptr); PDT->eraseNode(C2); + delete C2; + + EXPECT_TRUE(DT->verify()); + EXPECT_TRUE(PDT->verify()); - EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_EQ(PDT->getNode(C), nullptr); - EXPECT_EQ(PDT->getNode(C2), nullptr); + EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); + EXPECT_NE(PDT->getNode(C), nullptr); - PDT->recalculate(F); + DominatorTree NDT(F); + EXPECT_EQ(DT->compare(NDT), 0); - EXPECT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); - EXPECT_EQ(PDT->getNode(C), nullptr); - EXPECT_EQ(PDT->getNode(C2), nullptr); + PostDomTree NPDT(F); + EXPECT_EQ(PDT->compare(NPDT), 0); }); } @@ -686,6 +690,27 @@ TEST(DominatorTree, InsertUnreachable) { } } +TEST(DominatorTree, InsertFromUnreachable) { + CFGHolder Holder; + std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}}; + + std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}}; + CFGBuilder B(Holder.F, Arcs, Updates); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); + EXPECT_TRUE(LastUpdate); + + EXPECT_EQ(LastUpdate->Action, Insert); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + PDT.insertEdge(From, To); + EXPECT_TRUE(PDT.verify()); + EXPECT_TRUE(PDT.getRoots().size() == 2); + EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), nullptr); +} + TEST(DominatorTree, InsertMixed) { CFGHolder Holder; std::vector<CFGBuilder::Arc> Arcs = { |
