# Changeset View

Changeset View

# Standalone View

Standalone View

# llvm/include/llvm/Support/GenericDomTreeConstruction.h

//===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==// | //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==// | ||||

// | // | ||||

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | ||||

// See https://llvm.org/LICENSE.txt for license information. | // See https://llvm.org/LICENSE.txt for license information. | ||||

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | ||||

// | // | ||||

//===----------------------------------------------------------------------===// | //===----------------------------------------------------------------------===// | ||||

/// \file | /// \file | ||||

/// | /// | ||||

/// Generic dominator tree construction - This file provides routines to | /// Generic dominator tree construction - this file provides routines to | ||||

/// construct immediate dominator information for a flow-graph based on the | /// construct immediate dominator information for a flow-graph based on the | ||||

/// Semi-NCA algorithm described in this dissertation: | /// Semi-NCA algorithm described in this dissertation: | ||||

/// | /// | ||||

/// Linear-Time Algorithms for Dominators and Related Problems | /// [1] Linear-Time Algorithms for Dominators and Related Problems | ||||

/// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: | /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: | ||||

/// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf | /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf | ||||

/// | /// | ||||

/// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly | /// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly | ||||

/// faster than Simple Lengauer-Tarjan in practice. | /// faster than Simple Lengauer-Tarjan in practice. | ||||

/// | /// | ||||

/// O(n^2) worst cases happen when the computation of nearest common ancestors | /// O(n^2) worst cases happen when the computation of nearest common ancestors | ||||

/// requires O(n) average time, which is very unlikely in real world. If this | /// requires O(n) average time, which is very unlikely in real world. If this | ||||

/// ever turns out to be an issue, consider implementing a hybrid algorithm. | /// ever turns out to be an issue, consider implementing a hybrid algorithm | ||||

/// that uses SLT to perform full constructions and SemiNCA for incremental | |||||

/// updates. | |||||

/// | /// | ||||

/// The file uses the Depth Based Search algorithm to perform incremental | /// The file uses the Depth Based Search algorithm to perform incremental | ||||

/// updates (insertion and deletions). The implemented algorithm is based on | /// updates (insertion and deletions). The implemented algorithm is based on | ||||

/// this publication: | /// this publication: | ||||

/// | /// | ||||

/// An Experimental Study of Dynamic Dominators | /// [2] An Experimental Study of Dynamic Dominators | ||||

/// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: | /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: | ||||

/// https://arxiv.org/pdf/1604.02711.pdf | /// https://arxiv.org/pdf/1604.02711.pdf | ||||

/// | /// | ||||

//===----------------------------------------------------------------------===// | //===----------------------------------------------------------------------===// | ||||

#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H | #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H | ||||

#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H | #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H | ||||

▲ Show 20 Lines • Show All 689 Lines • ▼ Show 20 Lines | if (!isPermutation(DT.Roots, Roots)) { | ||||

// The roots chosen in the CFG have changed. This is because the | // The roots chosen in the CFG have changed. This is because the | ||||

// incremental algorithm does not really know or use the set of roots and | // incremental algorithm does not really know or use the set of roots and | ||||

// can make a different (implicit) decision about which node within an | // can make a different (implicit) decision about which node within an | ||||

// infinite loop becomes a root. | // infinite loop becomes a root. | ||||

LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n" | LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n" | ||||

<< "The entire tree needs to be rebuilt\n"); | << "The entire tree needs to be rebuilt\n"); | ||||

// It may be possible to update the tree without recalculating it, but | // It may be possible to update the tree without recalculating it, but | ||||

// we do not know yet how to do it, and it happens rarely in practise. | // we do not know yet how to do it, and it happens rarely in practice. | ||||

CalculateFromScratch(DT, BUI); | CalculateFromScratch(DT, BUI); | ||||

} | } | ||||

} | } | ||||

// Handles insertion to a node already in the dominator tree. | // Handles insertion to a node already in the dominator tree. | ||||

static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, | static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, | ||||

const TreeNodePtr From, const TreeNodePtr To) { | const TreeNodePtr From, const TreeNodePtr To) { | ||||

LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) | LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) | ||||

<< " -> " << BlockNamePrinter(To->getBlock()) << "\n"); | << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); | ||||

if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return; | if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return; | ||||

// DT.findNCD expects both pointers to be valid. When From is a virtual | // 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' | // root, then its CFG block pointer is a nullptr, so we have to 'compute' | ||||

// the NCD manually. | // the NCD manually. | ||||

const NodePtr NCDBlock = | const NodePtr NCDBlock = | ||||

(From->getBlock() && To->getBlock()) | (From->getBlock() && To->getBlock()) | ||||

? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) | ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) | ||||

: nullptr; | : nullptr; | ||||

assert(NCDBlock || DT.isPostDominator()); | assert(NCDBlock || DT.isPostDominator()); | ||||

const TreeNodePtr NCD = DT.getNode(NCDBlock); | const TreeNodePtr NCD = DT.getNode(NCDBlock); | ||||

assert(NCD); | assert(NCD); | ||||

LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); | LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); | ||||

const unsigned NCDLevel = NCD->getLevel(); | const unsigned NCDLevel = NCD->getLevel(); | ||||

// Based on Lemma 2.5 from the second paper, after insertion of (From,To), v | // Based on Lemma 2.5 from [2], after insertion of (From,To), v is affected | ||||

// is affected iff depth(NCD)+1 < depth(v) && a path P from To to v exists | // iff depth(NCD)+1 < depth(v) && a path P from To to v exists where every | ||||

// where every w on P s.t. depth(v) <= depth(w) | // w on P s.t. depth(v) <= depth(w) | ||||

// | // | ||||

// This reduces to a widest path problem (maximizing the depth of the | // This reduces to a widest path problem (maximizing the depth of the | ||||

// minimum vertex in the path) which can be solved by a modified version of | // minimum vertex in the path) which can be solved by a modified version of | ||||

// Dijkstra with a bucket queue (named depth-based search in the paper). | // Dijkstra with a bucket queue (named depth-based search in [2]). | ||||

// To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing | // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing | ||||

// affected if this does not hold. | // affected if this does not hold. | ||||

if (NCDLevel + 1 >= To->getLevel()) | if (NCDLevel + 1 >= To->getLevel()) | ||||

return; | return; | ||||

InsertionInfo II; | InsertionInfo II; | ||||

SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel; | SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel; | ||||

▲ Show 20 Lines • Show All 177 Lines • ▼ Show 20 Lines | #endif | ||||

if (ToTN != NCD) { | if (ToTN != NCD) { | ||||

DT.DFSInfoValid = false; | DT.DFSInfoValid = false; | ||||

const TreeNodePtr ToIDom = ToTN->getIDom(); | const TreeNodePtr ToIDom = ToTN->getIDom(); | ||||

LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " | LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " | ||||

<< BlockNamePrinter(ToIDom) << "\n"); | << BlockNamePrinter(ToIDom) << "\n"); | ||||

// To remains reachable after deletion. | // To remains reachable after deletion. | ||||

// (Based on the caption under Figure 4. from the second paper.) | // (Based on the caption under Figure 4. from [2].) | ||||

if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) | if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) | ||||

DeleteReachable(DT, BUI, FromTN, ToTN); | DeleteReachable(DT, BUI, FromTN, ToTN); | ||||

else | else | ||||

DeleteUnreachable(DT, BUI, ToTN); | DeleteUnreachable(DT, BUI, ToTN); | ||||

} | } | ||||

if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); | if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); | ||||

} | } | ||||

// Handles deletions that leave destination nodes reachable. | // Handles deletions that leave destination nodes reachable. | ||||

static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, | static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, | ||||

const TreeNodePtr FromTN, | const TreeNodePtr FromTN, | ||||

const TreeNodePtr ToTN) { | const TreeNodePtr ToTN) { | ||||

LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) | LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) | ||||

<< " -> " << BlockNamePrinter(ToTN) << "\n"); | << " -> " << BlockNamePrinter(ToTN) << "\n"); | ||||

LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n"); | LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n"); | ||||

// Find the top of the subtree that needs to be rebuilt. | // Find the top of the subtree that needs to be rebuilt. | ||||

// (Based on the lemma 2.6 from the second paper.) | // (Based on the lemma 2.6 from [2].) | ||||

const NodePtr ToIDom = | const NodePtr ToIDom = | ||||

DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); | DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); | ||||

assert(ToIDom || DT.isPostDominator()); | assert(ToIDom || DT.isPostDominator()); | ||||

const TreeNodePtr ToIDomTN = DT.getNode(ToIDom); | const TreeNodePtr ToIDomTN = DT.getNode(ToIDom); | ||||

assert(ToIDomTN); | assert(ToIDomTN); | ||||

const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom(); | const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom(); | ||||

// Top of the subtree to rebuild is the root node. Rebuild the tree from | // Top of the subtree to rebuild is the root node. Rebuild the tree from | ||||

// scratch. | // scratch. | ||||

Show All 15 Lines | static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, | ||||

SemiNCAInfo SNCA(BUI); | SemiNCAInfo SNCA(BUI); | ||||

SNCA.runDFS(ToIDom, 0, DescendBelow, 0); | SNCA.runDFS(ToIDom, 0, DescendBelow, 0); | ||||

LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n"); | LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n"); | ||||

SNCA.runSemiNCA(DT, Level); | SNCA.runSemiNCA(DT, Level); | ||||

SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); | SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); | ||||

} | } | ||||

// Checks if a node has proper support, as defined on the page 3 and later | // Checks if a node has proper support, as defined on the page 3 and later | ||||

// explained on the page 7 of the second paper. | // explained on the page 7 of [2]. | ||||

static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, | static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, | ||||

const TreeNodePtr TN) { | const TreeNodePtr TN) { | ||||

LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) | LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) | ||||

<< "\n"); | << "\n"); | ||||

for (const NodePtr Pred : | for (const NodePtr Pred : | ||||

ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) { | ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) { | ||||

LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); | LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); | ||||

if (!DT.getNode(Pred)) continue; | if (!DT.getNode(Pred)) continue; | ||||

const NodePtr Support = | const NodePtr Support = | ||||

DT.findNearestCommonDominator(TN->getBlock(), Pred); | DT.findNearestCommonDominator(TN->getBlock(), Pred); | ||||

LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); | LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); | ||||

if (Support != TN->getBlock()) { | if (Support != TN->getBlock()) { | ||||

LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) | LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) | ||||

<< " is reachable from support " | << " is reachable from support " | ||||

<< BlockNamePrinter(Support) << "\n"); | << BlockNamePrinter(Support) << "\n"); | ||||

return true; | return true; | ||||

} | } | ||||

} | } | ||||

return false; | return false; | ||||

} | } | ||||

// Handle deletions that make destination node unreachable. | // Handle deletions that make destination node unreachable. | ||||

// (Based on the lemma 2.7 from the second paper.) | // (Based on the lemma 2.7 from the [2].) | ||||

static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, | static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, | ||||

const TreeNodePtr ToTN) { | const TreeNodePtr ToTN) { | ||||

LLVM_DEBUG(dbgs() << "Deleting unreachable subtree " | LLVM_DEBUG(dbgs() << "Deleting unreachable subtree " | ||||

<< BlockNamePrinter(ToTN) << "\n"); | << BlockNamePrinter(ToTN) << "\n"); | ||||

assert(ToTN); | assert(ToTN); | ||||

assert(ToTN->getBlock()); | assert(ToTN->getBlock()); | ||||

if (IsPostDom) { | if (IsPostDom) { | ||||

▲ Show 20 Lines • Show All 443 Lines • ▼ Show 20 Lines | #endif | ||||

// The sibling property is similar. It says that for each pair of sibling | // The sibling property is similar. It says that for each pair of sibling | ||||

// nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each | // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each | ||||

// other. If sibling LEFT dominated sibling RIGHT, it means there are no | // other. If sibling LEFT dominated sibling RIGHT, it means there are no | ||||

// paths in the CFG from sibling LEFT to sibling RIGHT that do not go through | // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through | ||||

// LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of | // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of | ||||

// RIGHT, not a sibling. | // RIGHT, not a sibling. | ||||

// It is possible to verify the parent and sibling properties in | // It is possible to verify the parent and sibling properties in linear time, | ||||

// linear time, but the algorithms are complex. Instead, we do it in a | // but the algorithms are complex. Instead, we do it in a straightforward | ||||

// straightforward N^2 and N^3 way below, using direct path reachability. | // N^2 and N^3 way below, using direct path reachability. | ||||

// Checks if the tree has the parent property: if for all edges from V to W in | // Checks if the tree has the parent property: if for all edges from V to W in | ||||

// the input graph, such that V is reachable, the parent of W in the tree is | // the input graph, such that V is reachable, the parent of W in the tree is | ||||

// an ancestor of V in the tree. | // an ancestor of V in the tree. | ||||

// Running time: O(N^2). | // Running time: O(N^2). | ||||

// | // | ||||

// This means that if a node gets disconnected from the graph, then all of | // This means that if a node gets disconnected from the graph, then all of | ||||

// the nodes it dominated previously will now become unreachable. | // the nodes it dominated previously will now become unreachable. | ||||

asbirlea: No new line between method description and method declaration? | |||||

kuharAuthorUnsubmitted Good catch, thanks! kuhar: Good catch, thanks! | |||||

bool verifyParentProperty(const DomTreeT &DT) { | bool verifyParentProperty(const DomTreeT &DT) { | ||||

for (auto &NodeToTN : DT.DomTreeNodes) { | for (auto &NodeToTN : DT.DomTreeNodes) { | ||||

const TreeNodePtr TN = NodeToTN.second.get(); | const TreeNodePtr TN = NodeToTN.second.get(); | ||||

const NodePtr BB = TN->getBlock(); | const NodePtr BB = TN->getBlock(); | ||||

if (!BB || TN->getChildren().empty()) continue; | if (!BB || TN->getChildren().empty()) continue; | ||||

LLVM_DEBUG(dbgs() << "Verifying parent property of node " | LLVM_DEBUG(dbgs() << "Verifying parent property of node " | ||||

<< BlockNamePrinter(TN) << "\n"); | << BlockNamePrinter(TN) << "\n"); | ||||

▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Lines | for (auto &NodeToTN : DT.DomTreeNodes) { | ||||

} | } | ||||

} | } | ||||

return true; | return true; | ||||

} | } | ||||

// Check if the given tree is the same as a freshly computed one for the same | // Check if the given tree is the same as a freshly computed one for the same | ||||

// Parent. | // Parent. | ||||

// Running time: O(N^2), but faster in practise (same as tree construction). | // Running time: O(N^2), but faster in practice (same as tree construction). | ||||

// | // | ||||

// Note that this does not check if that the tree construction algorithm is | // Note that this does not check if that the tree construction algorithm is | ||||

// correct and should be only used for fast (but possibly unsound) | // correct and should be only used for fast (but possibly unsound) | ||||

// verification. | // verification. | ||||

static bool IsSameAsFreshTree(const DomTreeT &DT) { | static bool IsSameAsFreshTree(const DomTreeT &DT) { | ||||

DomTreeT FreshTree; | DomTreeT FreshTree; | ||||

FreshTree.recalculate(*DT.Parent); | FreshTree.recalculate(*DT.Parent); | ||||

const bool Different = DT.compare(FreshTree); | const bool Different = DT.compare(FreshTree); | ||||

▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Lines | |||||

bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) { | bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) { | ||||

SemiNCAInfo<DomTreeT> SNCA(nullptr); | SemiNCAInfo<DomTreeT> SNCA(nullptr); | ||||

// Simplist check is to compare against a new tree. This will also | // Simplist check is to compare against a new tree. This will also | ||||

// usefully print the old and new trees, if they are different. | // usefully print the old and new trees, if they are different. | ||||

if (!SNCA.IsSameAsFreshTree(DT)) | if (!SNCA.IsSameAsFreshTree(DT)) | ||||

return false; | return false; | ||||

// Common checks to verify the properties of the tree. O(N log N) at worst | // Common checks to verify the properties of the tree. O(N log N) at worst. | ||||

if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) || | if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) || | ||||

!SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT)) | !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT)) | ||||

return false; | return false; | ||||

// Extra checks depending on VerificationLevel. Up to O(N^3) | // Extra checks depending on VerificationLevel. Up to O(N^3). | ||||

if (VL == DomTreeT::VerificationLevel::Basic || | if (VL == DomTreeT::VerificationLevel::Basic || | ||||

VL == DomTreeT::VerificationLevel::Full) | VL == DomTreeT::VerificationLevel::Full) | ||||

if (!SNCA.verifyParentProperty(DT)) | if (!SNCA.verifyParentProperty(DT)) | ||||

return false; | return false; | ||||

if (VL == DomTreeT::VerificationLevel::Full) | if (VL == DomTreeT::VerificationLevel::Full) | ||||

if (!SNCA.verifySiblingProperty(DT)) | if (!SNCA.verifySiblingProperty(DT)) | ||||

return false; | return false; | ||||

Show All 9 Lines |

No new line between method description and method declaration?