Program Listing for File liveDeadVarAnalysis.h

Program Listing for File liveDeadVarAnalysis.h#

↰ Return to documentation for file (src/midend/programAnalysis/genericDataflow/simpleAnalyses/liveDeadVarAnalysis.h)

#include <featureTests.h>
#ifdef ROSE_ENABLE_SOURCE_ANALYSIS

#ifndef LIVE_DEAD_VAR_ANALYSIS_H
#define LIVE_DEAD_VAR_ANALYSIS_H

#include "genericDataflowCommon.h"
#include "VirtualCFGIterator.h"
#include "cfgUtils.h"
#include "CallGraphTraverse.h"
#include "analysisCommon.h"
#include "analysis.h"
#include "dataflow.h"
#include "latticeFull.h"
#include "printAnalysisStates.h"

#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <memory>

extern int liveDeadAnalysisDebugLevel;

// Lattice that stores the variables that are live at a given DataflowNode
class LiveVarsLattice : public FiniteLattice
{
        public:
        std::set<varID> liveVars;

        public:
        LiveVarsLattice();
        LiveVarsLattice(const varID& var);
        LiveVarsLattice(const std::set<varID>& liveVars);

        // Initializes this Lattice to its default state, if it is not already initialized
        void initialize();

        // Returns a copy of this lattice
        Lattice* copy() const;

        // Overwrites the state of this Lattice with that of that Lattice
        void copy(Lattice* that);

        // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
        //    information on a per-variable basis, these per-variable mappings must be converted from
        //    the current set of variables to another set. This may be needed during function calls,
        //    when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
        // We do not force child classes to define their own versions of this function since not all
        //    Lattices have per-variable information.
        // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
        //              old variable and pair->second is the new variable
        // func - the function that the copy Lattice will now be associated with
        void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc);

        // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
        // that contains data for a set of variables and incorporateVars must overwrite the state of just
        // those variables, while leaving its state for other variables alone.
        // We do not force child classes to define their own versions of this function since not all
        //    Lattices have per-variable information.
        void incorporateVars(Lattice* that_arg);

        // Returns a Lattice that describes the information known within this lattice
        // about the given expression. By default this could be the entire lattice or any portion of it.
        // For example, a lattice that maintains lattices for different known variables and expression will
        // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
        // on values of variables and expressions will return the portion of the lattice that relates to
        // the given expression.
        // It it legal for this function to return NULL if no information is available.
        // The function's caller is responsible for deallocating the returned object
        Lattice* project(SgExpression* expr);

        // The inverse of project(). The call is provided with an expression and a Lattice that describes
        // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
        // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
        // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
        // Returns true if this causes this to change and false otherwise.
        bool unProject(SgExpression* expr, Lattice* exprState);

        // computes the meet of this and that and saves the result in this
        // returns true if this causes this to change and false otherwise
        bool meetUpdate(Lattice* that_arg);

        bool operator==(Lattice* that);

        // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
        //    scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
        //    an expression or variable is dead).
        // It is assumed that a newly-added variable has not been added before and that a variable that is being
        //    removed was previously added
        // Returns true if this causes the lattice to change and false otherwise.
        bool addVar(const varID& var);
        bool remVar(const varID& var);

        // Returns true if the given variable is recorded as live and false otherwise
        bool isLiveVar(varID var);

        // The string that represents this object
        // If indent!="", every line of this string must be prefixed by indent
        // The last character of the returned string should not be '\n', even if it is a multi-line string.
        std::string str(std::string indent="");
};

// Virtual class that allows users of the LiveDeadVarsAnalysis to mark certain variables as
// being used inside a function call if the function's body is not available.
class funcSideEffectUses
{
public:
  // Returns the set of variables that are used in a call to the given function for which a body has not been provided.
  // The function is also provided with the DataflowNode where the function was called, as well as its state.
  virtual std::set<varID> usedVarsInFunc(const Function& func, const DataflowNode& n, NodeState& state)=0;
};

class LiveDeadVarsTransfer : public IntraDFTransferVisitor
{
  std::string indent;
  LiveVarsLattice* liveLat;

  bool modified;
  // Expressions that are assigned by the current operation
  std::set<SgExpression*> assignedExprs;
  // Variables that are assigned by the current operation
  std::set<varID> assignedVars;
  // Variables that are used/read by the current operation
  std::set<varID> usedVars;

  funcSideEffectUses *fseu;

  friend class LDVAExpressionTransfer;

  // Note that the variable corresponding to this expression is used
  void used(SgExpression *);

public:
  LiveDeadVarsTransfer(const Function &f, const DataflowNode &n, NodeState &s, const std::vector<Lattice*> &d, funcSideEffectUses *fseu_)
    : IntraDFTransferVisitor(f, n, s, d), indent("    "), liveLat(dynamic_cast<LiveVarsLattice*>(*(dfInfo.begin()))), modified(false), fseu(fseu_)
  {
        if(liveDeadAnalysisDebugLevel>=1) Dbg::dbg << indent << "liveLat="<<liveLat->str(indent + "    ")<<std::endl;
        // Make sure that all the lattice is initialized
        liveLat->initialize();
  }

  bool finish();

  void visit(SgExpression *);
  void visit(SgInitializedName *);
  void visit(SgReturnStmt *);
  void visit(SgExprStatement *);
  void visit(SgCaseOptionStmt *);
  void visit(SgIfStmt *);
  void visit(SgForStatement *);
  void visit(SgWhileStmt *);
  void visit(SgDoWhileStmt *);
};

/* Computes an over-approximation of the set of variables that are live at each DataflowNode. It may consider a given
   variable as live when in fact it is not. */
// !!! CURRENTLY THE ANALYSIS IS IMPRECISE BECAUSE:
// !!!    - IF THERE IS A VARIABLE USE WHERE THE IDENTITY OF THE VARIABLE IS COMPUTED THROUGH AN EXPRESSION, WE DO NOT
// !!!         RESPOND BY CONSERVATIVELY MAKING ALL VARIABLES LIVE.
// !!!    - IT DOES NOT CONSIDER INTERNALS OF ARRAYS OR OTHER HEAP MEMORY
class LiveDeadVarsAnalysis : public IntraBWDataflow
{
        protected:
        funcSideEffectUses* fseu;

        public:
        LiveDeadVarsAnalysis(SgProject *project, funcSideEffectUses* fseu=NULL);

        // Generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
        void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
                          std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts);

  std::shared_ptr<IntraDFTransferVisitor> getTransferVisitor(const Function& func, const DataflowNode& n,
                                                             NodeState& state, const std::vector<Lattice*>& dfInfo)
  { return std::shared_ptr<IntraDFTransferVisitor>(new LiveDeadVarsTransfer(func, n, state, dfInfo, fseu)); }

  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo) { ROSE_ABORT(); }
};

// Initialize vars to hold all the variables and expressions that are live at DataflowNode n
//void getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const DataflowNode& n, const NodeState& state, std::set<varID>& vars, std::string indent="");
void getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const NodeState& state, std::set<varID>& vars, std::string indent="");

// Returns the set of variables and expressions that are live at DataflowNode n
//std::set<varID> getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const DataflowNode& n, const NodeState& state, std::string indent="");
std::set<varID> getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const NodeState& state, std::string indent="");

// get Live-In lattice for a control flow graph node generated from a SgNode with an index
LiveVarsLattice* getLiveInVarsAt(LiveDeadVarsAnalysis* ldva, SgNode* n, unsigned int index = 0);

// get Live-Out lattice for a control flow graph node generated from a SgNode with an index
LiveVarsLattice* getLiveOutVarsAt(LiveDeadVarsAnalysis* ldva, SgNode* n, unsigned int index = 0);

class VarsExprsProductLattice: public virtual ProductLattice
{
        protected:
        // Sample lattice that will be initially associated with every variable (before the analysis)
        Lattice* perVarLattice;

        // Lattice that corresponds to allVar;
        Lattice* allVarLattice;

        // Map of lattices that correspond to constant variables
        std::map<varID, Lattice*> constVarLattices;

        // Maps variables in a given function to the index of their respective Lattice objects in
        // the ProductLattice::lattice[] array
        std::map<varID, int> varLatticeIndex;

        // The analysis that identified the variables that are live at this Dataflow node
        LiveDeadVarsAnalysis* ldva;

        bool (*filter) (CFGNode cfgn);

        // Dataflow node that this lattice is associated with and its corresponding node state.
        DataflowNode n;
        const NodeState& state;

        protected:
        // Minimal constructor that initializes just the portions of the object required to make an
        // initial blank VarsExprsProductLattice
        VarsExprsProductLattice(const DataflowNode& n, const NodeState& state, bool (*filter) (CFGNode cfgn));

        // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
        virtual VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state)=0;

        public:
        // creates a new VarsExprsProductLattice
        // perVarLattice - sample lattice that will be associated with every variable in scope at node n
        //     it should be assumed that the object pointed to by perVarLattice will be either
        //     used internally by this VarsExprsProductLatticeobject or deallocated
        // constVarLattices - map of additional variables and their associated lattices, that will be
        //     incorporated into this VarsExprsProductLatticein addition to any other lattices for
        //     currently live variables (these correspond to various useful constant variables like zeroVar)
        // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
        //     if allVarLattice==NULL, no support is provided for allVar
        // ldva - liveness analysis result. This can be set to NULL. Or only live variables at a CFG node will be used to initialize the product lattice
        // n - the dataflow node that this lattice will be associated with
        // state - the NodeState at this dataflow node
        VarsExprsProductLattice(Lattice* perVarLattice,
                                const std::map<varID, Lattice*>& constVarLattices,
                                Lattice* allVarLattice,
                                LiveDeadVarsAnalysis* ldva,
                                const DataflowNode& n, const NodeState& state);

        // Create a copy of that. It is assumed that the types of all the lattices in  VarsExprsProductLattice that are
        // the same as in this.
        VarsExprsProductLattice(const VarsExprsProductLattice& that);

        ~VarsExprsProductLattice();

        public:

        // Returns the Lattice mapped to the given variable or NULL if nothing is mapped to it
        Lattice* getVarLattice(const varID& var);

        // Returns the set of all variables mapped by this VarsExprsProductLattice
        std::set<varID> getAllVars();

        protected:

        // Returns the index of var among the variables associated with func
        // or -1 otherwise
        int getVarIndex(const varID& var);

        public:

        // Overwrites the state of this Lattice with that of that Lattice
        void copy(Lattice* that);
        // Set this to be a copy of that. It is assumed that the types of all the lattices in  VarsExprsProductLattice
        // that are the same as in this.
        void copy(const VarsExprsProductLattice* that);

        bool meetUpdate(Lattice *that);

        // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
        //    information on a per-variable basis, these per-variable mappings must be converted from
        //    the current set of variables to another set. This may be needed during function calls,
        //    when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
        // We do not force child classes to define their own versions of this function since not all
        //    Lattices have per-variable information.
        // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
        //              old variable and pair->second is the new variable
        // func - the function that the copy Lattice will now be associated with

        /*Lattice**/void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc);

        // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
        // that contains data for a set of variables and incorporateVars must overwrite the state of just
        // those variables, while leaving its state for other variables alone.
        // We do not force child classes to define their own versions of this function since not all
        //    Lattices have per-variable information.
        void incorporateVars(Lattice* that);

        // Returns a Lattice that describes the information known within this lattice
        // about the given expression. By default this could be the entire lattice or any portion of it.
        // For example, a lattice that maintains lattices for different known variables and expression will
        // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
        // on values of variables and expressions will return the portion of the lattice that relates to
        // the given expression.
        // It it legal for this function to return NULL if no information is available.
        // The function's caller is responsible for deallocating the returned object
        Lattice* project(SgExpression* expr);

        // The inverse of project(). The call is provided with an expression and a Lattice that describes
        // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
        // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
        // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
        // Returns true if this causes this to change and false otherwise.
        bool unProject(SgExpression* expr, Lattice* exprState);

        // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
        //    scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
        //    an expression or variable is dead).
        // Returns true if this causes this Lattice to change and false otherwise.
        bool addVar(const varID& var);
        bool remVar(const varID& var);

        // Sets the lattice of the given var to be lat.
        // If the variable is already mapped to some other Lattice,
        //   If *(the current lattice) == *lat, the mapping is not changed
        //   If *(the current lattice) != *lat, the current lattice is deallocated and var is mapped to lat->copy()
        // Returns true if this causes this Lattice to change and false otherwise.
        bool addVar(const varID& var, Lattice* lat);

        // The string that represents this object
        // If indent!="", every line of this string must be prefixed by indent
        // The last character of the returned string should not be '\n', even if it is a multi-line string.
        std::string str(std::string indent="");
};

class FiniteVarsExprsProductLattice : public virtual VarsExprsProductLattice, public virtual FiniteProductLattice
{
        protected:
        // Minimal constructor that initializes just the portions of the object required to make an
        // initial blank VarsExprsProductLattice
        FiniteVarsExprsProductLattice(const DataflowNode& n, const NodeState& state);

        // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
        VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state);

        public:
        // creates a new VarsExprsProductLattice
        // perVarLattice - sample lattice that will be associated with every variable in scope at node n
        //     it should be assumed that the object pointed to by perVarLattice will be either
        //     used internally by this VarsExprsProductLattice object or deallocated
        // constVarLattices - map of additional variables and their associated lattices, that will be
        //     incorporated into this VarsExprsProductLattice in addition to any other lattices for
        //     currently live variables (these correspond to various useful constant variables like zeroVar)
        // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
        //     if allVarLattice==NULL, no support is provided for allVar
        // func - the current function
        // n - the dataflow node that this lattice will be associated with
        // state - the NodeState at this dataflow node
        FiniteVarsExprsProductLattice(Lattice* perVarLattice,
                                     const std::map<varID, Lattice*>& constVarLattices,
                                     Lattice* allVarLattice,
                                     LiveDeadVarsAnalysis* ldva,
                                     const DataflowNode& n, const NodeState& state);

        FiniteVarsExprsProductLattice(const FiniteVarsExprsProductLattice& that);

        // returns a copy of this lattice
        Lattice* copy() const;
};

class InfiniteVarsExprsProductLattice: public virtual VarsExprsProductLattice, public virtual InfiniteProductLattice
{
        protected:
        // Minimal constructor that initializes just the portions of the object required to make an
        // initial blank VarsExprsProductLattice
        InfiniteVarsExprsProductLattice(const DataflowNode& n, const NodeState& state);

        // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
        VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state);

        public:
        // creates a new VarsExprsProductLattice
        // perVarLattice - sample lattice that will be associated with every variable in scope at node n
        //     it should be assumed that the object pointed to by perVarLattice will be either
        //     used internally by this VarsExprsProductLatticeobject or deallocated
        // constVarLattices - map of additional variables and their associated lattices, that will be
        //     incorporated into this VarsExprsProductLatticein addition to any other lattices for
        //     currently live variables (these correspond to various useful constant variables like zeroVar)
        // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
        //     if allVarLattice==NULL, no support is provided for allVar
        // func - the current function
        // n - the dataflow node that this lattice will be associated with
        // state - the NodeState at this dataflow node
        InfiniteVarsExprsProductLattice(Lattice* perVarLattice,
                                        const std::map<varID, Lattice*>& constVarLattices,
                                        Lattice* allVarLattice,
                                        LiveDeadVarsAnalysis* ldva,
                                        const DataflowNode& n, const NodeState& state);

        InfiniteVarsExprsProductLattice(const FiniteVarsExprsProductLattice& that);

        // returns a copy of this lattice
        Lattice* copy() const;
};

// prints the Lattices set by the given LiveDeadVarsAnalysis
void printLiveDeadVarsAnalysisStates(LiveDeadVarsAnalysis* da, std::string indent="");

#endif
#endif