Package proguard.analysis

Class 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 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