diff options
author | Jakub Kuderski <kubakuderski@gmail.com> | 2018-07-31 15:53:10 +0000 |
---|---|---|
committer | Jakub Kuderski <kubakuderski@gmail.com> | 2018-07-31 15:53:10 +0000 |
commit | 8f61a2ac04195ff347df2bec9738ee5b982a48fc (patch) | |
tree | af79c7403a62fb580ae29f1f4c064983eca4aaff /include | |
parent | d9904414c214ef94c480ce1cd76ebde0558403a0 (diff) |
[Dominators] Make slow walks shorter
Summary:
When DFS numbers are not yet calculated for a dominator tree, we have to walk it up to say whether one node dominates some other.
This patch makes the slow walks shorter by only walking until the level of the node we check against is reached. This is because a node cannot possibly dominate something higher in its tree.
When running opt with -O3, the patch results in:
* 25% fewer loop iterations for `opt` (fullLTO)
* 30% fewer loop iterations for sqlite
Reviewers: brzycki, asbirlea, chandlerc, NutshellySima, grosser
Reviewed By: NutshellySima
Subscribers: mehdi_amini, dexonsmith, llvm-commits
Differential Revision: https://reviews.llvm.org/D49955
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@338396 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/Support/GenericDomTree.h | 9 |
1 files changed, 7 insertions, 2 deletions
diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index e93d570c271..c716e4a4d30 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -853,10 +853,15 @@ protected: assert(isReachableFromEntry(B)); assert(isReachableFromEntry(A)); + const unsigned ALevel = A->getLevel(); const DomTreeNodeBase<NodeT> *IDom; - while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) + + // Don't walk nodes above A's subtree. When we reach A's level, we must + // either find A or be in some other subtree not dominated by A. + while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) B = IDom; // Walk up the tree - return IDom != nullptr; + + return B == A; } /// Wipe this tree's state without releasing any resources. |