Add the explanatory comment from r122680's commit message to the code itself.

[oota-llvm.git] / include / llvm / Analysis / DominatorInternals.h

diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 8f8a2715484fdc5ece3049ead2af5adc69fe500c..88e7073f84f8b8496866c20cd1777d108006c0b6 100644 (file)
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -195,6 +195,16 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::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<unsigned> Buckets;
   Buckets.resize(N + 1);
   for (unsigned i = 1; i <= N; ++i)