Package com.ibm.wala.fixedpoint.impl

Class AbstractFixedPointSolver<T extends IVariable<T>>

java.lang.Object
com.ibm.wala.fixedpoint.impl.AbstractFixedPointSolver<T>
All Implemented Interfaces:
FixedPointConstants, IFixedPointSolver<T>, VerboseAction
Direct Known Subclasses:
DefaultFixedPointSolver
public abstract class AbstractFixedPointSolver<T extends IVariable<T>> extends Object implements IFixedPointSolver<T>, FixedPointConstants, VerboseAction
Represents a set of IFixedPointStatements to be solved by a IFixedPointSolver

Implementation Note:

The set of steps and variables is internally represented as a graph. Each step and each variable is a node in the graph. If a step produces a variable that is used by another step, the graph has a directed edge from the producer to the consumer. Fixed-point iteration proceeds in a topological order according to these edges.

  • Field Details

    • verbose

      public static final boolean verbose

    • DEFAULT_VERBOSE_INTERVAL

      public static final int DEFAULT_VERBOSE_INTERVAL
      See Also:

    • DEFAULT_PERIODIC_MAINTENANCE_INTERVAL

      public static final int DEFAULT_PERIODIC_MAINTENANCE_INTERVAL
      See Also:

    • workList

      protected Worklist workList
      worklist for the iterative solver

  • Constructor Details

    • AbstractFixedPointSolver

      public AbstractFixedPointSolver()

  • Method Details

    • makeStmtRHS

      protected abstract T[] makeStmtRHS(int size)

    • initForFirstSolve

      public void initForFirstSolve()
      Some setup which occurs only before the first solve

    • emptyWorkList

      public boolean emptyWorkList()
      Returns:
      true iff work list is empty

    • solve

      public boolean solve(MonitorUtil.IProgressMonitor monitor) throws CancelException
      Solve the set of dataflow graph.

      PRECONDITION: graph is set up

      Specified by:
      solve in interface IFixedPointSolver<T extends IVariable<T>>
      Returns:
      true iff the evaluation of some equation caused a change in the value of some variable.
      Throws:
      CancelException

    • performVerboseAction

      public void performVerboseAction()
      Description copied from interface: VerboseAction
      optional method used for performance debugging
      Specified by:
      performVerboseAction in interface VerboseAction

    • lineBreak

      public static String lineBreak(String string, int wrap)

    • removeStatement

      public void removeStatement(AbstractStatement<T,?> s)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • getStatements

      public Iterator<? extends INodeWithNumber> getStatements()

    • addToWorkList

      public void addToWorkList(AbstractStatement s)
      Add a step to the work list.
      Parameters:
      s - the step to add

    • addAllStatementsToWorkList

      public void addAllStatementsToWorkList()
      Add all to the work list.

    • changedVariable

      public void changedVariable(T v)
      Call this method when the contents of a variable changes. This routine adds all graph using this variable to the set of new graph.
      Parameters:
      v - the variable that has changed

    • newStatement

      public boolean newStatement(T lhs, NullaryOperator<T> operator, boolean toWorkList, boolean eager)
      Add a step with zero operands on the right-hand side.

      TODO: this is a little odd, in that this equation will never fire unless explicitly added to a work list. I think in most cases we shouldn't be creating this nullary form.

      Parameters:
      lhs - the variable set by this equation
      operator - the step operator
      Throws:
      IllegalArgumentException - if lhs is null

    • newStatement

      public boolean newStatement(@Nullable T lhs, UnaryOperator<T> operator, T rhs, boolean toWorkList, boolean eager)
      Add a step with one operand on the right-hand side.
      Parameters:
      lhs - the lattice variable set by this equation
      operator - the step's operator
      rhs - first operand on the rhs
      Returns:
      true iff the system changes
      Throws:
      IllegalArgumentException - if operator is null

    • newStatement

      public boolean newStatement(T lhs, AbstractOperator<T> operator, T op1, T op2, boolean toWorkList, boolean eager)
      Add an equation with two operands on the right-hand side.
      Parameters:
      lhs - the lattice variable set by this equation
      operator - the equation operator
      op1 - first operand on the rhs
      op2 - second operand on the rhs

    • newStatement

      public boolean newStatement(T lhs, AbstractOperator<T> operator, T op1, T op2, T op3, boolean toWorkList, boolean eager)
      Add a step with three operands on the right-hand side.
      Parameters:
      lhs - the lattice variable set by this equation
      operator - the equation operator
      op1 - first operand on the rhs
      op2 - second operand on the rhs
      op3 - third operand on the rhs
      Throws:
      IllegalArgumentException - if lhs is null

    • newStatement

      public boolean newStatement(T lhs, AbstractOperator<T> operator, T[] rhs, boolean toWorkList, boolean eager)
      Add a step to the system with an arbitrary number of operands on the right-hand side.
      Parameters:
      lhs - lattice variable set by this equation
      operator - the operator
      rhs - the operands on the rhs

    • initializeVariables

      protected abstract void initializeVariables()
      Initialize all lattice vars in the system.

    • initializeWorkList

      protected abstract void initializeWorkList()
      Initialize the work list for iteration.j

    • orderStatements

      public void orderStatements()

    • isChanged

      public static boolean isChanged(byte code)

    • isSideEffect

      public static boolean isSideEffect(byte code)

    • isFixed

      public static boolean isFixed(byte code)

    • getMinSizeForTopSort

      public int getMinSizeForTopSort()

    • setMinEquationsForTopSort

      public void setMinEquationsForTopSort(int i)

    • getMaxEvalBetweenTopo

      public int getMaxEvalBetweenTopo()

    • getTopologicalGrowthFactor

      public double getTopologicalGrowthFactor()

    • setMaxEvalBetweenTopo

      public void setMaxEvalBetweenTopo(int i)

    • setTopologicalGrowthFactor

      public void setTopologicalGrowthFactor(double d)

    • getNumberOfEvaluations

      public int getNumberOfEvaluations()

    • incNumberOfEvaluations

      public void incNumberOfEvaluations()

    • periodicMaintenance

      protected void periodicMaintenance()
      a method that will be called every N evaluations. subclasses should override as desired.

    • getVerboseInterval

      protected int getVerboseInterval()
      subclasses should override as desired.

    • getPeriodicMaintainInterval

      protected int getPeriodicMaintainInterval()
      subclasses should override as desired.