Program Listing for File IntraProcAliasAnalysis.h

↰ Return to documentation for file (src/midend/programAnalysis/VirtualFunctionAnalysis/IntraProcAliasAnalysis.h)

#ifndef INTRA_PROC_ALIAS_ANALYSIS_H
#define INTRA_PROC_ALIAS_ANALYSIS_H
#include "IntraProcDataFlowAnalysis.h"
#include "customFilteredCFG.h"
#include "ClassHierarchyGraph.h"
#include "CallGraph.h"
#include <memory>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct AliasRelationNode{
    SgVariableSymbol *var;
    int derefLevel;

    bool operator==(const AliasRelationNode &that) const {
        assert(this != NULL);
        return (this->var == that.var && this->derefLevel == that.derefLevel);
    }

};


struct AliasCfgFilter
{
        bool operator() (CFGNode cfgn) const
        {
                SgNode *node = cfgn.getNode();
                switch (node->variantT())
                {
                    case V_SgBasicBlock:
                        return cfgn == node->cfgForBeginning()  || cfgn == node->cfgForBeginning();
                    case V_SgAssignStatement:
                    case V_SgAssignOp:
                    case V_SgAssignInitializer:
                        //return (cfgn == node->cfgForBeginning());
                        return (cfgn == node->cfgForEnd());
                    case V_SgConditionalExp:
                                return (cfgn.getIndex() == 1);
                    case V_SgConstructorInitializer:
                    case V_SgFunctionCallExp:
                    case V_SgReturnStmt:
                                return (cfgn == node->cfgForBeginning());
                                //return (cfgn == node->cfgForEnd());
                     default:
                        return false;

                }
        }
};
// Base class for CompactRepresentation
class CompReprBase{


public:
    CompReprBase() {
    }
    virtual void computeAliases (SgVariableSymbol *var, int derefLevel, vector<SgGraphNode *> &) = 0;

    virtual void computeAliases (SgGraphNode *node, int derefLevel, vector<SgGraphNode *> &) = 0;

    virtual void addMustAliasRelation(const AliasRelationNode &left, const AliasRelationNode &right) = 0;

    virtual void addMayAliasRelation(const AliasRelationNode &left, const AliasRelationNode &right) = 0;

    virtual unsigned long getHash() const = 0;
    virtual SgIncidenceDirectedGraph * getGraph() const = 0;

    virtual void merge(const CompReprBase &) = 0;

    virtual void toDot(const std::string& file_name) = 0;

protected:
    SgIncidenceDirectedGraph *graph;
    unsigned long hash;
 // DQ (12/6/2016): Aded virtual to fix compiler warning that we want to considered an error: -Wdelete-non-virtual-dtor
    virtual ~CompReprBase(){
        delete graph;
        graph = NULL;
    }
};

// The actual Compact Representation. It's implemented
// as a graph(SgIncidenceDirectedGraph).
class CompactRepresentation : public CompReprBase{

    std::unordered_map<SgNode *,SgGraphNode *> all_nodes;

    SgGraphNode * getGraphNode(SgNode *node);

    void merge(SgIncidenceDirectedGraph *thatGraph);

    void updateHash(SgNode *from, SgNode *to);

    void init();

    void addEdge(SgGraphNode *g_from, SgGraphNode *g_to);

    void processNodes(std::ostream & o, SgGraphNode* n, std::set<SgGraphNode*>& explored);

    void printNodePlusEdges(std::ostream & o, SgGraphNode* node);

    void printNode(std::ostream & o, SgGraphNode* node);

    void printEdge(std::ostream & o, SgDirectedGraphEdge* edge, bool isInEdge);


public:
    std::unordered_map<SgNode *,SgGraphNode *>  getNodesMapping(){ return all_nodes;}
    CompactRepresentation() {  init(); }

    SgIncidenceDirectedGraph * getGraph() const{ return graph; }

    unsigned long getHash() const {  return hash; }

    CompactRepresentation(const CompactRepresentation& copy);

    CompactRepresentation& operator=(const CompactRepresentation& p);

    void computeAliases (SgVariableSymbol *var, int derefLevel, vector<SgGraphNode *> &nodes);

    void computeAliases (SgGraphNode *node, int derefLevel, vector<SgGraphNode *> &);

    void addMustAliasRelation(const AliasRelationNode &left, const AliasRelationNode &right);

    void addMayAliasRelation(const AliasRelationNode &left, const AliasRelationNode &right);

    void merge(const CompReprBase &that);

    bool operator==(const CompactRepresentation &that) const;

    bool operator !=(const CompactRepresentation &that) const;

    void toDot(const std::string& file_name);
};

class CompReprPtr  {
     std::shared_ptr<CompReprBase> ptr;
public:
    CompReprPtr() { ptr = std::shared_ptr<CompReprBase>(); }

    CompReprPtr(CompactRepresentation *repr)   { ptr = std::shared_ptr<CompReprBase>(repr);  }

    CompReprBase * get() const{ return ptr.get();  }

    // Equality operator overload. Compares two CompactRepresentations
    bool operator==(const CompReprPtr &that) const;

    // Not Equality operator overload. Compares two CompactRepresentations
    bool operator!=(const CompReprPtr &that) const {  return !(*this == that);   }

    // += operator overload
    void operator+=(const CompReprPtr &that) const;
};

class AliasInfoGenerator {
    std::unordered_map<SgGraphNode *, CompReprPtr> ins;

    std::unordered_map<SgGraphNode *, CompReprPtr> outs;

    std::vector <AliasRelationNode > returnStmts;

    std::unordered_map<SgGraphNode *, std::vector <std::pair<AliasRelationNode, AliasRelationNode> > >aliasRelations;

public :
    AliasInfoGenerator();

    void init(SgGraphNode *n);

    CompReprPtr getEntryData(SgGraphNode *node);

    void setEntryData(SgGraphNode *node, CompReprPtr en) {    ins[node] = en;    }

    CompReprPtr getExitData(SgGraphNode *node);

    void setExitData(SgGraphNode *node, CompReprPtr en) {  outs[node] = en;   }

    std::vector <std::pair<AliasRelationNode, AliasRelationNode> > getAliasRelations(SgGraphNode *node);

    void addNewAliasRelation(SgGraphNode *node, std::pair<AliasRelationNode, AliasRelationNode> a_relation) ;

    void addReturnStmt(AliasRelationNode node) { returnStmts.push_back(node);  }

    std::vector<AliasRelationNode> getReturnStmts(){ return returnStmts; }

};

namespace ProcessExpression {
    void processLHS(SgNode *node, struct AliasRelationNode &arNode) ;

    void processRHS(SgNode *node, struct AliasRelationNode &arNode) ;
}

class CollectAliasRelations {
      StaticCFG::CFG *cfg;

      AliasInfoGenerator *g;

      void processNode(SgGraphNode *);
  public:
      enum COLOR {WHITE=0, GREY, BLACK};
      enum TRAVERSAL_TYPE {TOPOLOGICAL=0, NON_TOPOLOGICAL};

      CollectAliasRelations(StaticCFG::CFG *_cfg, AliasInfoGenerator *_g ) : cfg(_cfg), g(_g) { }
      void run();
  private:
      void recursiveCollect(SgGraphNode *, std::unordered_map<SgGraphNode*, CollectAliasRelations::COLOR> &);
};

class IntraProcAliasAnalysis :
        public IntraProcDataFlowAnalysis <SgGraphNode, CompReprPtr> {

    AliasInfoGenerator *gen;

    ClassHierarchyWrapper *classHierarchy;

protected:
    StaticCFG::CustomFilteredCFG<AliasCfgFilter> *cfg;

    CallGraphBuilder *cgBuilder;

    vector<SgGraphNode *> cfgNodes;

   //typedef FilteredCFGNode<AliasCfgFilter> FilteredCfgNode;
   //typedef FilteredCFGEdge<AliasCfgFilter> FilteredCfgEdge;

   CompReprPtr entry;

   CompReprPtr exit;

   unsigned long checkPointHash;

   virtual void buildCFG() ;

   std::unordered_map<SgFunctionDeclaration *, IntraProcAliasAnalysis *> &mapping;

   std::unordered_map<SgExpression*, std::vector<SgFunctionDeclaration*> > &resolver;

   void getFunctionParametersAliasRelations(SgFunctionCallExp *f_exp, SgFunctionDeclaration *funcDecl,
        std::vector <std::pair<AliasRelationNode, AliasRelationNode> > &arg_relations,
        std::vector <std::pair<AliasRelationNode, AliasRelationNode> > &return_relations);

   void getConstructorParametersAliasRelations(SgConstructorInitializer *f_exp, SgFunctionDeclaration *funcDecl,
        std::vector <std::pair<AliasRelationNode, AliasRelationNode> > &arg_relations );

   bool addVirtualFunction(SgType *type, SgFunctionCallExp *funcExp);

   bool updateVirtualFunctionInCallGraph (SgFunctionCallExp *funcCall, CompReprPtr &callSiteIN);

   // Get all the aliases
    void getAliases(CompReprPtr &ptr, AliasRelationNode &node, std::vector<SgVariableSymbol*>& aliases);

public:
    //ReachingDefinitionAnalysis(SgNode *head) : DataFlowAnalysis<ReachingDefNode, ReachingDefinitions>(head),  g(0) {
    IntraProcAliasAnalysis(SgNode *head, ClassHierarchyWrapper *_classHierarchy, CallGraphBuilder *_cgB,
                std::unordered_map<SgFunctionDeclaration *, IntraProcAliasAnalysis *> &mapping,
                std::unordered_map<SgExpression*, std::vector<SgFunctionDeclaration*> > &resolver);

    CompReprPtr getFunctionEntry() {return entry;}

    CompReprPtr getFunctionExit() {return exit;}

    std::vector<AliasRelationNode> getReturnStmts () { return gen->getReturnStmts(); }

    void setFunctionEntry(CompReprPtr &n);

    void setFunctionExit(CompReprPtr &n);

    bool runCheck();

    virtual void run() ;

    void init() { }

 // DQ (12/6/2016): Aded virtual to fix compiler warning that we want to considered an error: -Wdelete-non-virtual-dtor
    virtual ~IntraProcAliasAnalysis();

    CompReprPtr meet_data( const CompReprPtr& d1, const CompReprPtr& d2);

    virtual std::vector<SgGraphNode *> getAllNodes() {    return cfgNodes;  }

    virtual std::vector<SgGraphNode *> getPredecessors(SgGraphNode *n);

    CompReprPtr getCFGInData(SgGraphNode *a) {     return gen->getEntryData(a);   }

    CompReprPtr getCFGOutData(SgGraphNode *a) {      return gen->getExitData(a);  }

    void setCFGInData(SgGraphNode*a, CompReprPtr &b) {      gen->setEntryData(a, b);  }


    void applyCFGTransferFunction(SgGraphNode* s);

};

#endif