proguard.analysis

Class DominatorCalculator

java.lang.Object

proguard.analysis.DominatorCalculator

All Implemented Interfaces:

AttributeVisitor

public class DominatorCalculator
extends java.lang.Object
implements AttributeVisitor

Calculate the dominator tree of any method, making it possible to determine which instructions are guaranteed to be executed before others.

This is useful for applications like the CallResolver that would like to know whether an instruction, e.g. a method call, is always guaranteed to be executed assuming the containing method is invoked, or if its execution requires specific branches in the method to be taken.

In principle, dominator analysis is based on a simple equation:

1. The entry node dominates only itself
2. Any other node's dominator set is calculated by forming the intersection of the dominator sets of all its control flow predecessors. Afterwards, the node itself is also added to its dominator set.

Like this, the dominator information is propagated through the control flow graph one by one, potentially requiring several iterations until the solution is stable, as the dominator sets of some predecessors might still be uninitialized when used.

The implementation here is based on an algorithm that solves the underlying dataflow equation using optimized BitSet objects instead of normal sets.

Field Summary

Fields

Modifier and Type	Field and Description
static int	ENTRY_NODE_OFFSET Virtual instruction offset modelling the method entry.
static int	EXIT_NODE_OFFSET Virtual instruction offset modelling the method exit, i.e.

Constructor Summary

Constructors

Constructor and Description
DominatorCalculator() Creates a new DominatorCalculator.
DominatorCalculator(boolean ignoreExceptions) Creates a new DominatorCalculator.

Method Summary

Modifier and Type	Method and Description
boolean	dominates(int dominator, int inferior) Check if one instruction dominates another one.
void	visitAnyAttribute(Clazz clazz, Attribute attribute) Visits any Attribute instance.
void	visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface proguard.classfile.attribute.visitor.AttributeVisitor

visitAnnotationDefaultAttribute, visitAnyAnnotationsAttribute, visitAnyParameterAnnotationsAttribute, visitAnyTypeAnnotationsAttribute, visitBootstrapMethodsAttribute, visitConstantValueAttribute, visitDeprecatedAttribute, visitDeprecatedAttribute, visitDeprecatedAttribute, visitDeprecatedAttribute, visitEnclosingMethodAttribute, visitExceptionsAttribute, visitInnerClassesAttribute, visitLineNumberTableAttribute, visitLocalVariableTableAttribute, visitLocalVariableTypeTableAttribute, visitMethodParametersAttribute, visitModuleAttribute, visitModuleMainClassAttribute, visitModulePackagesAttribute, visitNestHostAttribute, visitNestMembersAttribute, visitPermittedSubclassesAttribute, visitRecordAttribute, visitRuntimeInvisibleAnnotationsAttribute, visitRuntimeInvisibleAnnotationsAttribute, visitRuntimeInvisibleAnnotationsAttribute, visitRuntimeInvisibleAnnotationsAttribute, visitRuntimeInvisibleAnnotationsAttribute, visitRuntimeInvisibleParameterAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeInvisibleTypeAnnotationsAttribute, visitRuntimeVisibleAnnotationsAttribute, visitRuntimeVisibleAnnotationsAttribute, visitRuntimeVisibleAnnotationsAttribute, visitRuntimeVisibleAnnotationsAttribute, visitRuntimeVisibleAnnotationsAttribute, visitRuntimeVisibleParameterAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitRuntimeVisibleTypeAnnotationsAttribute, visitSignatureAttribute, visitSignatureAttribute, visitSignatureAttribute, visitSignatureAttribute, visitSignatureAttribute, visitSourceDebugExtensionAttribute, visitSourceDirAttribute, visitSourceFileAttribute, visitStackMapAttribute, visitStackMapTableAttribute, visitSyntheticAttribute, visitSyntheticAttribute, visitSyntheticAttribute, visitSyntheticAttribute, visitUnknownAttribute

Field Detail

EXIT_NODE_OFFSET

public static final int EXIT_NODE_OFFSET

Virtual instruction offset modelling the method exit, i.e. all return instructions.

See Also:

Constant Field Values

ENTRY_NODE_OFFSET

public static final int ENTRY_NODE_OFFSET

Virtual instruction offset modelling the method entry. This is needed such that the method entry is guaranteed to have no incoming control flow edges, as this would prevent the algorithm from converging properly without complicated alternative measures.

See Also:

Constant Field Values

Constructor Detail

DominatorCalculator

public DominatorCalculator()

Creates a new DominatorCalculator. The default behavior is to ignore exceptions.

DominatorCalculator

public DominatorCalculator(boolean ignoreExceptions)

Creates a new DominatorCalculator.

Parameters:

ignoreExceptions - If false, exceptions will be taken into account in the analysis.

Method Detail

dominates

public boolean dominates(int dominator,
                         int inferior)

Check if one instruction dominates another one. If this is the case, the dominating instruction is guaranteed to be executed before the inferior instruction. Should you wish to check whether an instruction is guaranteed to be executed once the containing method is invoked, you can use the virtual inferior EXIT_NODE_OFFSET as a collection for all return instructions.

Parameters:

dominator - The potentially dominating instruction's offset

inferior - The potentially dominated instruction's offset

Returns:

true if the potential dominator is indeed guaranteed to be executed before the inferior

visitAnyAttribute

public void visitAnyAttribute(Clazz clazz,
                              Attribute attribute)

Description copied from interface: AttributeVisitor

Visits any Attribute instance. The more specific default implementations of this interface delegate to this method.

Specified by:

visitAnyAttribute in interface AttributeVisitor

visitCodeAttribute

public void visitCodeAttribute(Clazz clazz,
                               Method method,
                               CodeAttribute codeAttribute)

Specified by:

visitCodeAttribute in interface AttributeVisitor