From 3ae770aa2be9f8b6c9da5c8dc84748a7fdbd33f4 Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Tue, 31 Jul 2018 15:53:10 +0000 Subject: [PATCH] [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 llvm-svn: 338396 --- llvm/include/llvm/Support/GenericDomTree.h | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h index e93d570..c716e4a 100644 --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -853,10 +853,15 @@ protected: assert(isReachableFromEntry(B)); assert(isReachableFromEntry(A)); + const unsigned ALevel = A->getLevel(); const DomTreeNodeBase *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. -- 2.7.4