From 2a8c22aa6824143fdf4c00d4486c65eca26f6c9f Mon Sep 17 00:00:00 2001 From: Cameron Zwarich Date: Sun, 2 Jan 2011 10:40:14 +0000 Subject: [PATCH] Add the explanatory comment from r122680's commit message to the code itself. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122689 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DominatorInternals.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 8f8a2715484..88e7073f84f 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -195,6 +195,16 @@ void Calculate(DominatorTreeBase::NodeType>& DT, // infinite loops). In these cases an artificial exit node is required. MultipleRoots |= (DT.isPostDominator() && N != F.size()); + // When naively implemented, the Lengauer-Tarjan algorithm requires a separate + // bucket for each vertex. However, this is unnecessary, because each vertex + // is only placed into a single bucket (that of its semidominator), and each + // vertex's bucket is processed before it is added to any bucket itself. + // + // Instead of using a bucket per vertex, we use a single array Buckets that + // has two purposes. Before the vertex V with preorder number i is processed, + // Buckets[i] stores the index of the first element in V's bucket. After V's + // bucket is processed, Buckets[i] stores the index of the next element in the + // bucket containing V, if any. std::vector Buckets; Buckets.resize(N + 1); for (unsigned i = 1; i <= N; ++i) -- 2.34.1