Page Menu
Home
Phabricator
Search
Configure Global Search
Log In
Files
F11245906
D58327.id187188.diff
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Flag For Later
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Sat, Jan 25, 9:05 PM
Size
4 KB
Mime Type
text/xpatch; charset=utf8
Expires
Sun, Jan 26, 9:05 PM (3 w, 6 d ago)
Engine
blob
Format
Raw Data
Handle
5669003
Attached To
D58327: [Dominators] Simplify and optimize path compression used in linkeval forest.
D58327.id187188.diff
View Options
Index: include/llvm/Support/GenericDomTreeConstruction.h
===================================================================
 include/llvm/Support/GenericDomTreeConstruction.h
+++ include/llvm/Support/GenericDomTreeConstruction.h
@@ 15,9 +15,12 @@
/// Loukas Georgiadis, Princeton University, November 2005, pp. 2123:
/// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
///
/// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
/// out that the theoretically slower O(n*log(n)) implementation is actually
/// faster than the almostlinear O(n*alpha(n)) version, even for large CFGs.
+/// SemiNCA algorithm runs in O(n^2) worstcase time but usually slightly
+/// faster than Simple LengauerTarjan in practice.
+///
+/// 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
+/// ever turns out to be an issue, consider implementing a hybrid algorithm.
///
/// The file uses the Depth Based Search algorithm to perform incremental
/// updates (insertion and deletions). The implemented algorithm is based on
@@ 254,42 +257,46 @@
return LastNum;
}
 NodePtr eval(NodePtr VIn, unsigned LastLinked) {
 auto &VInInfo = NodeToInfo[VIn];
 if (VInInfo.DFSNum < LastLinked)
 return VIn;
+ // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum
+ // of sdom(U), where U > W and there is a virtual forest path from U to V. The
+ // virtual forest consists of linked edges of processed vertices.
+ //
+ // We can follow Parent pointers (virtual forest edges) to determine the
+ // ancestor U with minimum sdom(U). But it is slow and thus we employ the path
+ // compression technique to speed up to O(m*log(n)). Theoretically the virtual
+ // forest can be organized as balanced trees to achieve almost linear
+ // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size
+ // and Child) and unlikely to be faster than the simple path compression.
+ //
+ // For each vertex V, its Label points to the minimum Semi on its path from V
+ // to NodeToInfo[V].Parent (excluded).
+ NodePtr eval(NodePtr V, unsigned LastLinked) {
+ InfoRec *VInfo = &NodeToInfo[V];
+ if (VInfo>Parent < LastLinked)
+ return VInfo>Label;
 SmallVector<NodePtr, 32> Work;
 SmallPtrSet<NodePtr, 32> Visited;
+ // Store ancestors except the last (root of a virtual tree) into a stack.
+ SmallVector<InfoRec *, 32> Stack;
+ do {
+ Stack.push_back(VInfo);
+ VInfo = &NodeToInfo[NumToNode[VInfo>Parent]];
+ } while (VInfo>Parent >= LastLinked);
 if (VInInfo.Parent >= LastLinked)
 Work.push_back(VIn);

 while (!Work.empty()) {
 NodePtr V = Work.back();
 auto &VInfo = NodeToInfo[V];
 NodePtr VAncestor = NumToNode[VInfo.Parent];

 // Process Ancestor first
 if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
 Work.push_back(VAncestor);
 continue;
 }
 Work.pop_back();

 // Update VInfo based on Ancestor info
 if (VInfo.Parent < LastLinked)
 continue;

 auto &VAInfo = NodeToInfo[VAncestor];
 NodePtr VAncestorLabel = VAInfo.Label;
 NodePtr VLabel = VInfo.Label;
 if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
 VInfo.Label = VAncestorLabel;
 VInfo.Parent = VAInfo.Parent;
 }

 return VInInfo.Label;
+ // Path compression. Point each vertex's Parent to the root and update its
+ // Label if any of its ancestors' (PInfo>Label) has a smaller Semi.
+ const InfoRec *PInfo = VInfo;
+ const InfoRec *PLabelInfo = &NodeToInfo[PInfo>Label];
+ do {
+ VInfo = Stack.pop_back_val();
+ VInfo>Parent = PInfo>Parent;
+ const InfoRec *VLabelInfo = &NodeToInfo[VInfo>Label];
+ if (PLabelInfo>Semi < VLabelInfo>Semi)
+ VInfo>Label = PInfo>Label;
+ else
+ PLabelInfo = VLabelInfo;
+ PInfo = VInfo;
+ } while (!Stack.empty());
+ return VInfo>Label;
}
// This function requires DFS to be run before calling it.
Event Timeline
Log In to Comment