This class computes dominator and post-dominator information using the Lengauer-Tarjan method. See A Fast Algorithm for Finding Dominators in a Flowgraph T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. This implementation runs in time O(n log n). The time bound could be changed to O(n * ack(n)) with a small change to the link and eval, and an addition of a child field to the DFS info. In reality, the constant overheads are high enough that the current method is faster in all but the strangest artificially constructed examples. The basic idea behind this algorithm is to perform a DFS walk, keeping track of various info about parents. We then use this info to calculate the dominators, using union-find structures to link together the DFS info, then finally evaluate the union-find results to get the dominators. This implementation is m log n because it does not perform union by rank to keep the union-find tree balanced.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	Dominators.DFSInfo
private class	Dominators.DfsWalker Callback for depth-first walk through control flow graph (either from the entry block or the exit block).

Field Summary

Modifier and Type	Field and Description
private final ArrayList<SsaBasicBlock>	blocks
private final DomFront.DomInfo[]	domInfos `non-null;` the raw dominator info
private final Dominators.DFSInfo[]	info indexed by basic block index
private final SsaMethod	meth
private final boolean	postdom
private final ArrayList<SsaBasicBlock>	vertex

Constructor Summary

Access	Constructor and Description
private	Dominators(SsaMethod `non-null;` method to process meth, DomFront.DomInfo[] `non-null;` the raw dominator info domInfos, boolean true for postdom information, false for normal dom info postdom) Constructs an instance.

Method Summary

Modifier and Type	Method and Description
private void	compress(SsaBasicBlock Basic block whose DFS info we are path compressing. in) Performs path compress on the DFS info.
private SsaBasicBlock	eval(SsaBasicBlock v)
private BitSet	getPreds(SsaBasicBlock block)
private BitSet	getSuccs(SsaBasicBlock block)
public static Dominators	make(SsaMethod `non-null;` method to process meth, DomFront.DomInfo[] `non-null;` the raw dominator info domInfos, boolean true for postdom information, false for normal dom info postdom) Constructs a fully-initialized instance.
private void	run() Performs dominator/post-dominator calculation for the control flow graph.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

blocks	back to summary
private final ArrayList<SsaBasicBlock> blocks

domInfos	back to summary
private final DomFront.DomInfo[] domInfos `non-null;` the raw dominator info

info	back to summary
private final Dominators.DFSInfo[] info indexed by basic block index

meth	back to summary
private final SsaMethod meth

postdom	back to summary
private final boolean postdom

vertex	back to summary
private final ArrayList<SsaBasicBlock> vertex

Constructor Detail

Dominators back to summary

Dominators	back to summary
private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom) Constructs an instance. Parameters meth:SsaMethod `non-null;` method to process domInfos:DomFront.DomInfo[] `non-null;` the raw dominator info postdom:boolean true for postdom information, false for normal dom info

private Dominators(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom)

Constructs an instance.

Parameters

meth:SsaMethod: non-null; method to process
domInfos:DomFront.DomInfo[]: non-null; the raw dominator info
postdom:boolean: true for postdom information, false for normal dom info

Method Detail

compress	back to summary
private void compress(SsaBasicBlock in) Performs path compress on the DFS info. Parameters in:SsaBasicBlock Basic block whose DFS info we are path compressing.

compress

back to summary

private void compress(SsaBasicBlock in)

Performs path compress on the DFS info.

Parameters

in:SsaBasicBlock: Basic block whose DFS info we are path compressing.

eval	back to summary
private SsaBasicBlock eval(SsaBasicBlock v)

getPreds	back to summary
private BitSet getPreds(SsaBasicBlock block)

getSuccs	back to summary
private BitSet getSuccs(SsaBasicBlock block)

make back to summary

make	back to summary
public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom) Constructs a fully-initialized instance. (This method exists so as to avoid calling a large amount of code in the constructor.) Parameters meth:SsaMethod `non-null;` method to process domInfos:DomFront.DomInfo[] `non-null;` the raw dominator info postdom:boolean true for postdom information, false for normal dom info

public static Dominators make(SsaMethod meth, DomFront.DomInfo[] domInfos, boolean postdom)

Constructs a fully-initialized instance. (This method exists so as to avoid calling a large amount of code in the constructor.)

Parameters

meth:SsaMethod: non-null; method to process
domInfos:DomFront.DomInfo[]: non-null; the raw dominator info
postdom:boolean: true for postdom information, false for normal dom info

run	back to summary
private void run() Performs dominator/post-dominator calculation for the control flow graph.

org.droidparts.dexmaker.dx.ssa back to summary

private final Class Dominators.DFSInfo

Class Inheritance

extends Object

java.lang.Object
org.droidparts.dexmaker.dx.ssa.Dominators.DFSInfo

Field Summary

Modifier and Type	Field and Description
public SsaBasicBlock	ancestor
public ArrayList<SsaBasicBlock>	bucket
public SsaBasicBlock	parent
public SsaBasicBlock	rep rep(resentative) is known as "label" in the paper.
public int	semidom

Constructor Summary

Access	Constructor and Description
public	DFSInfo()

Method Summary

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

ancestor	back to summary
public SsaBasicBlock ancestor

bucket	back to summary
public ArrayList<SsaBasicBlock> bucket

parent	back to summary
public SsaBasicBlock parent

rep	back to summary
public SsaBasicBlock rep rep(resentative) is known as "label" in the paper. It is the node that our block's DFS info has been unioned to.

semidom	back to summary
public int semidom

Constructor Detail

DFSInfo	back to summary
public DFSInfo()

org.droidparts.dexmaker.dx.ssa back to summary

private Class Dominators.DfsWalker

Class Inheritance

extends Object
implements Visitor

java.lang.Object
org.droidparts.dexmaker.dx.ssa.Dominators.DfsWalker

All Implemented Interfaces

org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor

Callback for depth-first walk through control flow graph (either from the entry block or the exit block). Records the traversal order in the infolist.

Field Summary

Modifier and Type	Field and Description
private int	dfsNum

Constructor Summary

Access	Constructor and Description
private	DfsWalker()

Method Summary

Modifier and Type	Method and Description
public void	visitBlock(SsaBasicBlock `non-null;` block visited v, SsaBasicBlock `null-ok;` parent node if applicable parent) Implements org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor.visitBlock. Indicates a block has been visited by an iterator method.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

dfsNum	back to summary
private int dfsNum

Constructor Detail

DfsWalker	back to summary
private DfsWalker()

Method Detail

visitBlock back to summary

visitBlock	back to summary
public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent) Implements org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor.visitBlock. Doc from org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor.visitBlock. Indicates a block has been visited by an iterator method. Parameters v:SsaBasicBlock `non-null;` block visited parent:SsaBasicBlock `null-ok;` parent node if applicable

public void visitBlock(SsaBasicBlock v, SsaBasicBlock parent)

Implements org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor.visitBlock.

Doc from org.droidparts.dexmaker.dx.ssa.SsaBasicBlock.Visitor.visitBlock.

Indicates a block has been visited by an iterator method.

Parameters

v:SsaBasicBlock: non-null; block visited
parent:SsaBasicBlock: null-ok; parent node if applicable

public final Class Dominators

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class Dominators.DFSInfo

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

private Class Dominators.DfsWalker

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail