From 7083930287fa87dbb94af6c931d36996468a0a6f Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Tue, 3 Oct 2017 14:33:41 +0000 Subject: [PATCH] [Dominators] Add DFS number verification Summary: This patch teaches the DominatorTree verifier to check DFS In/Out numbers which are used to answer dominance queries. DFS number verification is done in O(nlogn), so it shouldn't add much overhead on top of the O(n^3) sibling property verification. This check should detect errors like the one spotted in PR34466 and related bug reports. The patch also cleans up the DFS calculation a bit, as all constructed trees should have a single root now. I see 2 new test failures when running check-all after this change: ``` Failing Tests (2): Polly :: Isl/CodeGen/OpenMP/reference-argument-from-non-affine-region.ll Polly :: Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll ``` which seem to happen just after `Create LLVM-IR from SCoPs` -- I XFAILed them in r314800. Reviewers: dberlin, grosser, davide, zhendongsu, bollu Reviewed By: dberlin Subscribers: nandini12396, bollu, Meinersbur, brzycki, llvm-commits Differential Revision: https://reviews.llvm.org/D38331 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@314801 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/GenericDomTree.h | 19 ++--- include/llvm/Support/GenericDomTreeConstruction.h | 99 ++++++++++++++++++++++- 2 files changed, 106 insertions(+), 12 deletions(-) diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 066a61e1ec2..c4dd18751f4 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -702,28 +702,25 @@ public: return; } - unsigned DFSNum = 0; - SmallVector *, typename DomTreeNodeBase::const_iterator>, 32> WorkStack; const DomTreeNodeBase *ThisRoot = getRootNode(); - + assert((!Parent || ThisRoot) && "Empty constructed DomTree"); if (!ThisRoot) return; - // Even in the case of multiple exits that form the post dominator root - // nodes, do not iterate over all exits, but start from the virtual root - // node. Otherwise bbs, that are not post dominated by any exit but by the - // virtual root node, will never be assigned a DFS number. - WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); + // Both dominators and postdominators have a single root node. In the case + // case of PostDominatorTree, this node is a virtual root. + WorkStack.push_back({ThisRoot, ThisRoot->begin()}); + + unsigned DFSNum = 0; ThisRoot->DFSNumIn = DFSNum++; while (!WorkStack.empty()) { const DomTreeNodeBase *Node = WorkStack.back().first; - typename DomTreeNodeBase::const_iterator ChildIt = - WorkStack.back().second; + const auto ChildIt = WorkStack.back().second; // If we visited all of the children of this node, "recurse" back up the // stack setting the DFOutNum. @@ -735,7 +732,7 @@ public: const DomTreeNodeBase *Child = *ChildIt; ++WorkStack.back().second; - WorkStack.push_back(std::make_pair(Child, Child->begin())); + WorkStack.push_back({Child, Child->begin()}); Child->DFSNumIn = DFSNum++; } } diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index b0a1ffa3125..96ea74a5c50 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -1349,6 +1349,102 @@ struct SemiNCAInfo { return true; } + // Check if the computed DFS numbers are correct. Note that DFS info may not + // be valid, and when that is the case, we don't verify the numbers. + static bool VerifyDFSNumbers(const DomTreeT &DT) { + if (!DT.DFSInfoValid || !DT.Parent) + return true; + + const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0]; + const TreeNodePtr Root = DT.getNode(RootBB); + + auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) { + errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", " + << TN->getDFSNumOut() << '}'; + }; + + // Verify the root's DFS In number. Although DFS numbering would also work + // if we started from some other value, we assume 0-based numbering. + if (Root->getDFSNumIn() != 0) { + errs() << "DFSIn number for the tree root is not:\n\t"; + PrintNodeAndDFSNums(Root); + errs() << '\n'; + errs().flush(); + return false; + } + + // For each tree node verify if children's DFS numbers cover their parent's + // DFS numbers with no gaps. + for (const auto &NodeToTN : DT.DomTreeNodes) { + const TreeNodePtr Node = NodeToTN.second.get(); + + // Handle tree leaves. + if (Node->getChildren().empty()) { + if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) { + errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t"; + PrintNodeAndDFSNums(Node); + errs() << '\n'; + errs().flush(); + return false; + } + + continue; + } + + // Make a copy and sort it such that it is possible to check if there are + // no gaps between DFS numbers of adjacent children. + SmallVector Children(Node->begin(), Node->end()); + std::sort(Children.begin(), Children.end(), + [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) { + return Ch1->getDFSNumIn() < Ch2->getDFSNumIn(); + }); + + auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums]( + const TreeNodePtr FirstCh, const TreeNodePtr SecondCh = nullptr) { + assert(FirstCh); + + errs() << "Incorrect DFS numbers for:\n\tParent "; + PrintNodeAndDFSNums(Node); + + errs() << "\n\tChild "; + PrintNodeAndDFSNums(FirstCh); + + if (SecondCh) { + errs() << "\n\tSecond child "; + PrintNodeAndDFSNums(SecondCh); + } + + errs() << "\nAll children: "; + for (const TreeNodePtr Ch : Children) { + PrintNodeAndDFSNums(Ch); + errs() << ", "; + } + + errs() << '\n'; + errs().flush(); + }; + + if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) { + PrintChildrenError(Children.front()); + return false; + } + + if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) { + PrintChildrenError(Children.back()); + return false; + } + + for (size_t i = 0, e = Children.size() - 1; i != e; ++i) { + if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) { + PrintChildrenError(Children[i], Children[i + 1]); + return false; + } + } + } + + return true; + } + // Checks if for every edge From -> To in the graph // NCD(From, To) == IDom(To) or To. bool verifyNCD(const DomTreeT &DT) { @@ -1521,7 +1617,8 @@ bool Verify(const DomTreeT &DT) { SemiNCAInfo SNCA(nullptr); return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) && - SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT); + SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT) && + SNCA.VerifyDFSNumbers(DT); } } // namespace DomTreeBuilder -- 2.11.0