dataflow.h

Go to the documentation of this file.

#ifndef DATAFLOW_H
#define DATAFLOW_H

#include "analysisCommon.h"
#include "nodeState.h"
#include "functionState.h"
#include "analysis.h"
#include "lattice.h"

#include <boost/shared_ptr.hpp>
#include <vector>
#include <set>
#include <map>
#include <string>

// !!! NOTE: THE CURRENT INTER-/INTRA-PROCEDURAL ANALYSIS API EFFECTIVELY ASSUMES THAT EACH ANALYSIS WILL BE EXECUTED
// !!!       ONCE BECAUSE DURING A GIVEN ANALYSIS PASS THE INTRA- ANALYSIS MAY ACCUMULATE STATE AND THERE IS NO
// !!!       API FUNCTION THAT THE INTER- ANALYSIS CAN USE THE RE-INITIALIZE THE STATE OF THE INTRA- ANALYSIS.

/*************************
 *** Dataflow Analyses ***
 *************************/
class InterProceduralDataflow;

class IntraProceduralDataflow : virtual public IntraProceduralAnalysis
{
        public:
        // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
        //virtual std::vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state)=0;

        // !!! NOTE: THIS FUNCTION SHOULD BE AMENDED TO MAKE IT POSSIBLE TO SPECIFY THAT WE WANT THE INITIAL STATE
        // !!!       FOR ABOVE THIS NODE, BELOW THIS NODE OR A UNION OF BOTH. THIS IS IMPORTANT FOR LATTICES THAT
        // !!!       MAINTAIN DIFFERENT INFORMATION FOR THE DIFFERENT CASES, SUCH AS VarsExprsProductLattice, WHERE
        // !!!       DIFFERENT VARIABLES ARE LIVE BEFORE AND AFTER THE NODE. IN PARTICULAR, THIS WOULD BE USEFUL FOR
        // !!!       INTERPROCEDURAL ANALYSES WHERE THE SAME SgFunctionDefinition SgNode IS BOTH THE FIRST AND LAST
        // !!!       VirtualCFG NODE OF EACH FUNCTION WITH DIFFERENT INDEXES AND THE STATE BELOW IT CORRESPONDS TO THE
        // !!!       START OF THE FUNCTION AND THE STATE ABOVE IT CORRESPONDS TO THE END.
        virtual void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
                                  std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts)=0;


        // Set of functions that have already been visited by this analysis, used
        // to make sure that the dataflow state of previously-visited functions is
        // not re-initialized when they are visited again.
        std::set<Function> visited;

        void setInterAnalysis(InterProceduralDataflow* interDataflowAnalysis)
        { this->interAnalysis = (InterProceduralAnalysis*)interDataflowAnalysis; }

        void setInterAnalysis(IntraProceduralDataflow* intraDFAnalysis)
        { this->interAnalysis = intraDFAnalysis->interAnalysis; }

        // Dataflow version of the function that intra-procedural analysis on the given function.
        // Takes in:
        //    state - the function's NodeState
        //    analyzeDueToCallers - true if this function is analyzed due to changes in the the dataflow state from
        //       its caller functions at their call sites to this function
        //    calleesUpdated - true if the function is analyzed due to changes of dataflow state of functions called
        //       by this function at their exit points (i.e. points where this state affects the caller)
        // Returns true if the function's NodeState gets modified as a result and false otherwise
        virtual bool runAnalysis(const Function& func, NodeState* state, bool analyzeDueToCallers, std::set<Function> calleesUpdated)=0;

        // Calls the full dataflow runAnalysis with dummy arguments to make it possible to use IntraProceduralDataflow
        // as if it were an IntraProceduralAnalysis
        bool runAnalysis(const Function& func, NodeState* state)
        {
                // Each function is analyzed as if it were called directly by the language's runtime, ignoring
                // the application's actual call graph
                bool analyzeDueToCallers = true;

                // We ignore the application's call graph, so it doesn't matter whether this function calls other functions
                std::set<Function> calleesUpdated;

                return runAnalysis(func, state, analyzeDueToCallers, calleesUpdated);
        }

        InterProceduralDataflow* getInterAnalysis() const
        {
                return (InterProceduralDataflow*)interAnalysis;
        }
};

class IntraDFTransferVisitor : public ROSE_VisitorPatternDefaultBase
{
protected:
  // Common arguments to the underlying transfer function
  const Function &func;
  const DataflowNode &dfNode;
  NodeState &nodeState;
  const std::vector<Lattice*> &dfInfo;

public:

  IntraDFTransferVisitor(const Function &f, const DataflowNode &n, NodeState &s, const std::vector<Lattice*> &d)
    : func(f), dfNode(n), nodeState(s), dfInfo(d)
  { }

  virtual bool finish() = 0;
  virtual ~IntraDFTransferVisitor() { }
};

class IntraUnitDataflow : virtual public IntraProceduralDataflow
{
        public:

        // the transfer function that is applied to every node
        // n - the dataflow node that is being processed
        // state - the NodeState object that describes the state of the node, as established by earlier
        //         analysis passes
        // dfInfo - the Lattices that this transfer function operates on. The function takes these lattices
        //          as input and overwrites them with the result of the transfer.
        // Returns true if any of the input lattices changed as a result of the transfer function and
        //    false otherwise.
        virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo)=0;

  class DefaultTransfer : public IntraDFTransferVisitor
  {
    bool modified;
    IntraUnitDataflow *analysis;
  public:
    DefaultTransfer(const Function& func_, const DataflowNode& n_, NodeState& state_, const std::vector<Lattice*>& dfInfo_, IntraUnitDataflow *a)
      : IntraDFTransferVisitor(func_, n_, state_, dfInfo_), modified(false), analysis(a)
      { }


    void visit(SgNode *n) { modified = analysis->transfer(func, dfNode, nodeState, dfInfo); }
    bool finish() { return modified; }
  };


    // \todo \pp IMO. the function getTransferVisitor is not necessary and can be removed.
    //           Users wanting to write the analysis based on visitors can do so
    //           in the transfer function. (This safes one memory allocation, deallocation,
    //           and boost::shared_pointer management overhead per transfer).
    //           A transfer function using the visitor would look like (if desired this can be
    //           simplified by providing a convenience function taking a visitor as argument):
    // \code
    //           virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)
    //           {
    //             MyTransferVisitor visitor(myarguments, func, n, ...);
    //             n.getNode().accept(visitor);
    //             return visitor.finish();
    //           }
    // \endcode
    virtual boost::shared_ptr<IntraDFTransferVisitor> getTransferVisitor(const Function& func, const DataflowNode& n,
                                                                  NodeState& state, const std::vector<Lattice*>& dfInfo)
  { return boost::shared_ptr<IntraDFTransferVisitor>(new DefaultTransfer(func, n, state, dfInfo, this)); }
};

class InterProceduralDataflow : virtual public InterProceduralAnalysis
{
        public:
        InterProceduralDataflow(IntraProceduralDataflow* intraDataflowAnalysis);

        // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
        // fw - =true if this is a forward analysis and =false if this is a backward analysis
        // n - the dataflow node that is being processed
        // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
        //         (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
        // dfInfo - the Lattices that this transfer function operates on. The function propagates them
        //          to the calling function and overwrites them with the dataflow result of calling this function.
        // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
        //          the function call's return value. The callee may not modify these lattices.
        // Returns true if any of the input lattices changed as a result of the transfer function and
        //    false otherwise.
        virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
                              const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)=0;
};

class InitDataflowState : public UnstructuredPassIntraAnalysis
{
        //std::vector<Lattice*> initState;
        IntraProceduralDataflow* dfAnalysis;

        public:
        InitDataflowState(IntraProceduralDataflow* dfAnalysis/*, std::vector<Lattice*> &initState*/)
        {
                this->dfAnalysis = dfAnalysis;
                this->filter = dfAnalysis->filter; // Must transfer the custom CFG filter, this is tricky!!
                //this->initState = initState;
        }

        void visit(const Function& func, const DataflowNode& n, NodeState& state);
};

// Analysis that finds the DataflowNodes that corresponds to calls to a given set of functions
class FindAllFunctionCalls : public UnstructuredPassIntraAnalysis
{
        // The set of functions that we wish to find the calls to
        const std::set<Function>& funcsToFind;

        // Maps each function in funcsToFind to a set of DataflowNodes that hold calls to this function
        std::map<Function, std::set<DataflowNode> > funcCalls;

        public:
        FindAllFunctionCalls(const std::set<Function>& funcsToFind): funcsToFind(funcsToFind)
        { }

        void visit(const Function& func, const DataflowNode& n, NodeState& state);

        // Returns a reference to funcCalls
        std::map<Function, std::set<DataflowNode> >& getFuncCalls() { return funcCalls; }
};

/* Base class of Uni-directional (Forward or Backward) Intra-Procedural Dataflow Analyses */
class IntraUniDirectionalDataflow : public IntraUnitDataflow
{
        public:

        // Runs the intra-procedural analysis on the given function and returns true if
        // the function's NodeState gets modified as a result and false otherwise
        // state - the function's NodeState
        bool runAnalysis(const Function& func, NodeState* state, bool analyzeDueToCallers, std::set<Function> calleesUpdated);

        protected:
        // propagates the dataflow info from the current node's NodeState (curNodeState) to the next node's
        // NodeState (nextNodeState)
        bool propagateStateToNextNode(
             const std::vector<Lattice*>& curNodeState, DataflowNode curDFNode, int nodeIndex,
             const std::vector<Lattice*>& nextNodeState, DataflowNode nextDFNode);

        std::vector<DataflowNode> gatherDescendants(std::vector<DataflowEdge> edges,
                                                    DataflowNode (DataflowEdge::*edgeFn)() const);

        virtual NodeState*initializeFunctionNodeState(const Function &func, NodeState *fState) = 0;
        virtual VirtualCFG::dataflow*
          getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState) = 0;
        virtual vector<Lattice*> getLatticeAnte(NodeState *state) = 0;
        virtual vector<Lattice*> getLatticePost(NodeState *state) = 0;

        // If we're currently at a function call, use the associated inter-procedural
        // analysis to determine the effect of this function call on the dataflow state.
        virtual void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state) = 0;


        virtual vector<DataflowNode> getDescendants(const DataflowNode &n) = 0;
        virtual DataflowNode getUltimate(const Function &func) = 0;
};

/* Forward Intra-Procedural Dataflow Analysis */
class IntraFWDataflow  : public IntraUniDirectionalDataflow
{
        public:

        IntraFWDataflow()
        {}

        NodeState* initializeFunctionNodeState(const Function &func, NodeState *fState);
        VirtualCFG::dataflow*
          getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState);
        vector<Lattice*> getLatticeAnte(NodeState *state);
        vector<Lattice*> getLatticePost(NodeState *state);
        void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state);
        vector<DataflowNode> getDescendants(const DataflowNode &n);
        DataflowNode getUltimate(const Function &func);
};

/* Backward Intra-Procedural Dataflow Analysis */
class IntraBWDataflow  : public IntraUniDirectionalDataflow
{
        public:

        IntraBWDataflow()
        {}

        NodeState* initializeFunctionNodeState(const Function &func, NodeState *fState);
        VirtualCFG::dataflow*
          getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState);
        virtual vector<Lattice*> getLatticeAnte(NodeState *state);
        virtual vector<Lattice*> getLatticePost(NodeState *state);
        void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state);
        vector<DataflowNode> getDescendants(const DataflowNode &n);
        DataflowNode getUltimate(const Function &func);
};

/*// Dataflow class that maintains a Lattice for every currently live variable
class IntraFWPerVariableDataflow  : public IntraFWDataflow
{
        private:
        bool includeScalars;
        bool includeArrays;


        public:
        IntraFWPerVariableDataflow(bool includeScalars, bool includeArrays);

        // returns the set of global variables(scalars and/or arrays)
        varIDSet& getGlobalVars();

        // returns the set of variables(scalars and/or arrays) declared in this function
        varIDSet& getLocalVars(Function func);

        // returns the set of variables(scalars and/or arrays) referenced in this function
        varIDSet& getRefVars(Function func);

        // generates the initial variable-specific lattice state for a dataflow node
        virtual Lattice* genInitVarState(const Function& func, const DataflowNode& n, const NodeState& state)=0;

        // generates the initial non-variable-specific lattice state for a dataflow node
        virtual Lattice* genInitNonVarState(const Function& func, const DataflowNode& n, const NodeState& state)=0;

        // Generates a map of special constant variables (such as zeroVar) and the lattices that correspond to them
        // These lattices are assumed to be constants: it is assumed that they are never modified and it is legal to
        //    maintain only one copy of each lattice may for the duration of the analysis.
        virtual std::map<varID, Lattice*> genConstVarLattices() const=0;

        private:
        // maps variables to the index of their respective Lattice objects in a given function
        std::map<Function, std::map<varID, int> > varLatticeIndex;
        // map of lattices that correspond to constant variables
        std::map<varID, Lattice*> constVarLattices;
        // =true if constVarLattices has been initialized and =false otherwise
        bool constVarLattices_init;

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

        Lattice* getVarLattice(const Function& func, const varID& var, const std::vector<Lattice*>& dfInfo);
};*/

/******************************************************
 ***            printDataflowInfoPass               ***
 *** Prints out the dataflow information associated ***
 *** with a given analysis for every CFG node a     ***
 *** function.                                      ***
 ******************************************************/
class printDataflowInfoPass : public IntraFWDataflow
{
        Analysis* analysis;

        public:
        printDataflowInfoPass(Analysis *analysis)
        {
                this->analysis = analysis;
        }

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

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

/**********************************************************************
 ***                 UnstructuredPassInterDataflow                  ***
 *** The trivial inter-procedural dataflow where a intra-procedural ***
 *** dataflow analysis is executed once on every function in the    ***
 *** application, with no guarantees about how dataflow information ***
 *** is transmitted across function calls.                          ***
 **********************************************************************/
class UnstructuredPassInterDataflow : virtual public InterProceduralDataflow
{
        public:

        UnstructuredPassInterDataflow(IntraProceduralDataflow* intraDataflowAnalysis)
                             : InterProceduralAnalysis((IntraProceduralAnalysis*)intraDataflowAnalysis), InterProceduralDataflow(intraDataflowAnalysis)
        {}

        // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
        // fw - =true if this is a forward analysis and =false if this is a backward analysis
        // n - the dataflow node that is being processed
        // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
        //         (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
        // dfInfo - the Lattices that this transfer function operates on. The function propagates them
        //          to the calling function and overwrites them with the dataflow result of calling this function.
        // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
        //          the function call's return value. The callee may not modify these lattices.
        // Returns true if any of the input lattices changed as a result of the transfer function and
        //    false otherwise.
        bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
                      const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)
        {
                return false;
        }

        void runAnalysis();
};

// Analysis that merges the dataflow states belonging to the given Analysis at all the return statements in the given function
// and produces a list of merged lattices (same number of lattices as were maintained by the nodes in the function).
// NOTE: The callers of this analysis are responsible for deallocating the lattices stored n mergedLatsRetStmt
//       and mergedLatsRetVal at the end of the analysis pass.
class MergeAllReturnStates : public UnstructuredPassIntraAnalysis
{
        // Analysis whose states we'll be merging
        Analysis* analysis;

        // List of merged lattices of all the return statements and the returned values
        std::vector<Lattice*> mergedLatsRetStmt;
        std::vector<Lattice*> mergedLatsRetVal;

        public:
        //typedef enum ab {above=0, below=1};
        protected:
        //ab latSide;

        // After the analysis is complete, records true if the state of the mergedLattices changed
        // during the analysis and false otherwise
        bool modified;

        public:
        MergeAllReturnStates(Analysis* analysis/*, ab latSide*/): analysis(analysis)/*, latSide(latSide)*/
        { modified=false; }

        MergeAllReturnStates(Analysis* analysis, const std::vector<Lattice*>& mergedLatsRetStmt, const std::vector<Lattice*>& mergedLatsRetVal/*, ab latSide*/):
                analysis(analysis), mergedLatsRetStmt(mergedLatsRetStmt), mergedLatsRetVal(mergedLatsRetVal)/*, latSide(latSide)*/
        { modified=false; }

        void visit(const Function& func, const DataflowNode& n, NodeState& state);

        // Merges the lattices in the given vector into mergedLat, which may be mergedLatsRetStmt or mergedLatsRetVal
        // Returns true of mergedLatsStmt changes as a result and false otherwise.
        static bool mergeLats(std::vector<Lattice*>& mergedLat, const std::vector<Lattice*>& lats);

        // Returns a reference to mergedLatsRetStmt
        std::vector<Lattice*>& getMergedLatsRetStmt() { return mergedLatsRetStmt; }

        // Returns a reference to mergedLatsRetVal
        std::vector<Lattice*>& getMergedLatsRetVal() { return mergedLatsRetVal; }

        // Returns the value of modified
        bool getModified() { return modified; }

        // Deallocates all the merged lattices
        ~MergeAllReturnStates();
};

// A NodeFact associated with a FunctionState that stores the merge of the lattices immediately
// above all return statements in a given function.
class DFStateAtReturns : public NodeFact
{
        // The dataflow state at the end of the function, merged over all the return statements
        // and the implicit return at the end of the function
        std::vector<Lattice*>& latsAtFuncReturn;
        // The dataflow state of the return value, merged over all the return statements
        std::vector<Lattice*>& latsRetVal;

        public:
        //DFStateAtReturns();

        DFStateAtReturns(std::vector<Lattice*>& latsAtFuncReturn, std::vector<Lattice*>& latsRetVal);

        // Returns a copy of this node fact
        NodeFact* copy() const;

        // Applies the MergeAllReturnStates analysis on the given function, incorporating the results into
        // the lattices held by this object.
        // Returns true of the lattices change as a result and false otherwise.
        bool mergeReturnStates(const Function& func, FunctionState* fState, IntraProceduralDataflow* intraAnalysis);

        // Returns a reference to latsAtFuncReturn
        std::vector<Lattice*>& getLatsAtFuncReturn() { return latsAtFuncReturn; }

        // Returns a reference to latsRetVal
        std::vector<Lattice*>& getLatsRetVal() { return latsRetVal; }

        std::string str(std::string indent);
};

class ContextInsensitiveInterProceduralDataflow : virtual public InterProceduralDataflow, public TraverseCallGraphDataflow
{
        // list of functions that still remain to be processed
        //list<Function> remaining;

        // The functions that still remain to be processed.

        // These functions need to be processed because they are called by functions that have been processed
        // or are called at startup such as main() and the constructors of static objects.
        std::set<Function> remainingDueToCallers;

        // Each function F in this map needs to be processed because it has called other functions and those functions
        // have now been analyzed and the dataflow information at their exit points has changed since the last time
        // F was analyzed. remainingDueToCalls maps each F to all such functions. As such, F needs to be re-analyzed,
        // starting at the calls to these functions.
        std::map<Function, std::set<Function> > remainingDueToCalls;

        public:
        ContextInsensitiveInterProceduralDataflow(IntraProceduralDataflow* intraDataflowAnalysis, SgIncidenceDirectedGraph* graph) ;

        public:

        // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
        // fw - =true if this is a forward analysis and =false if this is a backward analysis
        // n - the dataflow node that is being processed
        // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
        //         (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
        // dfInfo - the Lattices that this transfer function operates on. The function propagates them
        //          to the calling function and overwrites them with the dataflow result of calling this function.
        // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
        //          the function call's return value. The callee may not modify these lattices.
        // Returns true if any of the input lattices changed as a result of the transfer function and
        //    false otherwise.
        bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
                      const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw);

        // Uses TraverseCallGraphDataflow to traverse the call graph.
        void runAnalysis();

        // Runs the intra-procedural analysis every time TraverseCallGraphDataflow passes a function.
        void visit(const CGFunction* func);
};

#endif