Package soot.jimple.toolkits.pointer

Class LocalMustAliasAnalysis

  • Direct Known Subclasses:
    StrongLocalMustAliasAnalysis
    public class LocalMustAliasAnalysis
extends ForwardFlowAnalysis<Unit,​HashMap<Value,​Integer>>
    LocalMustAliasAnalysis attempts to determine if two local variables (at two potentially different program points) must point to the same object. The underlying abstraction is based on global value numbering. See also StrongLocalMustAliasAnalysis for an analysis that soundly treats redefinitions within loops. See Sable TR 2007-8 for details. P.S. The idea behind this analysis and the way it assigns numbers is very similar to what is described in the paper: Lapkowski, C. and Hendren, L. J. 1996. Extended SSA numbering: introducing SSA properties to languages with multi-level pointers. In Proceedings of the 1996 Conference of the Centre For Advanced Studies on Collaborative Research (Toronto, Ontario, Canada, November 12 - 14, 1996). M. Bauer, K. Bennet, M. Gentleman, H. Johnson, K. Lyons, and J. Slonim, Eds. IBM Centre for Advanced Studies Conference. IBM Press, 23. Only major differences: Here we only use primary numbers, no secondary numbers. Further, we use the call graph to determine fields that are not written to in the transitive closure of this method's execution. A third difference is that we assign fixed values to IdentityRefs, because those never change during one execution.
    Author:
    Patrick Lam, Eric Bodden
    See Also:
    StrongLocalMustAliasAnalysis

    • Field Detail

      • localsAndFieldRefs

        protected Set<Value> localsAndFieldRefs
        The set of all local variables and field references that we track. This set contains objects of type Local and, if tryTrackFieldAssignments is enabled, it may also contain EquivalentValues of FieldRefs. If so, these field references are to be tracked on the same way as Locals are.

      • rhsToNumber

        protected transient Map<Value,​Integer> rhsToNumber
        maps from right-hand side expressions (non-locals) to value numbers

      • mergePointToValueToNumber

        protected transient Map<Unit,​Map<Value,​Integer>> mergePointToValueToNumber
        maps from a merge point (a unit) and a value to the unique value number of that value at this point

      • nextNumber

        protected int nextNumber
        the next value number

      • container

        protected SootMethod container
        the containing method

    • Constructor Detail

      • LocalMustAliasAnalysis

        public LocalMustAliasAnalysis​(UnitGraph g,
                              boolean tryTrackFieldAssignments)
        Creates a new LocalMustAliasAnalysis. If tryTrackFieldAssignments, we run an interprocedural side-effects analysis to determine which fields are (transitively) written to by this method. All fields which that are not written to are tracked just as local variables. This semantics is sound for single-threaded programs.

    • Method Detail

      • flowThrough

        protected void flowThrough​(HashMap<Value,​Integer> in,
                           Unit u,
                           HashMap<Value,​Integer> out)
        Description copied from class: FlowAnalysis
        Given the merge of the out sets, compute the in set for s (or in to out, depending on direction). This function often causes confusion, because the same interface is used for both forward and backward flow analyses. The first parameter is always the argument to the flow function (i.e. it is the "in" set in a forward analysis and the "out" set in a backward analysis), and the third parameter is always the result of the flow function (i.e. it is the "out" set in a forward analysis and the "in" set in a backward analysis).
        Specified by:
        flowThrough in class FlowAnalysis<Unit,​HashMap<Value,​Integer>>
        Parameters:
        in - the input flow
        u - the current node
        out - the returned flow

      • thisRefNumber

        public static int thisRefNumber()

      • parameterRefNumber

        public static int parameterRefNumber​(ParameterRef r)

      • instanceKeyString

        public String instanceKeyString​(Local l,
                                Stmt s)
        Returns a string (natural number) representation of the instance key associated with l at statement s or null if there is no such key associated.
        Parameters:
        l - any local of the associated method
        s - the statement at which to check

      • hasInfoOn

        public boolean hasInfoOn​(Local l,
                         Stmt s)
        Returns true if this analysis has any information about local l at statement s. In particular, it is safe to pass in locals/statements that are not even part of the right method. In those cases false will be returned. Permits s to be null, in which case false will be returned.

      • mustAlias

        public boolean mustAlias​(Local l1,
                         Stmt s1,
                         Local l2,
                         Stmt s2)
        Returns:
        true if values of l1 (at s1) and l2 (at s2) have the exact same object IDs, i.e. at statement s1 the variable l1 must point to the same object as l2 at s2.