ManagerFIAlias.hpp

Go to the documentation of this file.

#ifndef ManagerFIAlias_H
#define ManagerFIAlias_H

//--------------------------------------------------------------------
#include <cassert>
#include <map>
#include <set>

// OpenAnalysis headers
#include <OpenAnalysis/IRInterface/AliasIRInterface.hpp>
#include <OpenAnalysis/Utils/UnionFindUniverse.hpp>
#include <OpenAnalysis/MemRefExpr/MemRefExprVisitor.hpp>
#include <OpenAnalysis/Alias/Interface.hpp>
#include <OpenAnalysis/Location/Locations.hpp>

namespace OA {
  namespace Alias {

class FixedLocationVisitor : public virtual MemRefExprVisitor {
  public:
    FixedLocationVisitor(OA_ptr<AliasIRInterface> ir, ProcHandle proc,
                         OA_ptr<Interface> aliasInterface)
      : mIR(ir), mProc(proc), mDirectRef(false),
        mAliasInterface(aliasInterface) 
    {
       mDirectRefLocations = new LocSet;
    }
    ~FixedLocationVisitor() {}

    OA_ptr<LocSetIterator> getDirectRefLocIterator();

    void visitNamedRef(NamedRef& ref); 
    void visitUnnamedRef(UnnamedRef& ref); 
    void visitUnknownRef(UnknownRef& ref);
    void visitAddressOf(AddressOf& ref);
    void visitDeref(Deref& ref);
    void visitFieldAccess(FieldAccess& ref); 
    // default handling of more specific SubSet specificiations
    void visitSubSetRef(SubSetRef& ref); 

  private:

    OA_ptr<LocSet> mDirectRefLocations;

    OA_ptr<Alias::Interface> mAliasInterface;

    void notDirect();

    bool mDirectRef;
    OA_ptr<Location> mLoc;
    OA_ptr<AliasIRInterface> mIR;
    ProcHandle mProc;
};

class InvisibleLocationVisitor : public virtual MemRefExprVisitor {
  public:
    InvisibleLocationVisitor(OA_ptr<AliasIRInterface> ir, ProcHandle proc,
                             std::set<SymHandle>& procFormalSet) 
        : mIR(ir),mProc(proc),mInvisibleRef(false), 
          mProcFormalSet(procFormalSet) {}
    ~InvisibleLocationVisitor() {}

    bool isInvisibleRef();

    OA_ptr<Location> getInvisibleRefLoc();

    void visitNamedRef(NamedRef& ref);

    void visitUnnamedRef(UnnamedRef& ref);
    void visitUnknownRef(UnknownRef& ref);
    void visitDeref(Deref& ref);
    void visitAddressOf(AddressOf& ref);

    // default handling of more specific SubSet specificiations
    // nothing more specific than this is needed because if
    // a deref to a global or formal was involved then this ref will 
    // become the mre in the invisible location.  Doesn't matter what 
    // subclass the ref is
    void visitSubSetRef(SubSetRef& ref);
    void visitFieldAccess(FieldAccess& ref);
    void visitIdxAccess(IdxAccess& ref);
    void visitIdxExprAccess(IdxExprAccess& ref);

  private:
    void notInvisible();

    bool mInvisibleRef;
    bool mBaseIsNotLocal;
    bool mBaseIsFormal;
    OA_ptr<Location> mLoc;
    OA_ptr<AliasIRInterface> mIR;
    ProcHandle mProc;
    std::set<SymHandle>& mProcFormalSet;

};

class VisibleBaseVisitor : public virtual MemRefExprVisitor {
  public:
    VisibleBaseVisitor(OA_ptr<AliasIRInterface> ir, ProcHandle proc)
      : mIR(ir), mProc(proc),
        mBaseVisible(true)
    { }
    ~VisibleBaseVisitor() {}

    bool isBaseVisible() { return mBaseVisible; }

    void visitNamedRef(NamedRef& ref); 
    void visitUnnamedRef(UnnamedRef& ref); 
    void visitUnknownRef(UnknownRef& ref);
    void visitDeref(Deref& ref);
    void visitAddressOf(AddressOf& ref);
    // default handling of more specific SubSet specificiations
    void visitSubSetRef(SubSetRef& ref); 

  private:
    bool mBaseVisible;
    OA_ptr<AliasIRInterface> mIR;
    ProcHandle mProc;
};

class AnalyzedProcIterator : public IRProcIterator { 
public: 
  AnalyzedProcIterator(std::set<ProcHandle> analyzedProcs) :
    mAnalyzedProcs(analyzedProcs), mIt(analyzedProcs.begin())
  { } 
  ~AnalyzedProcIterator() { }; 
 
  virtual ProcHandle current() const; // Returns the current item. 
  virtual bool isValid() const;        // False when all items are exhausted. 
         
  virtual void operator++();     // prefix 
  void operator++(int) { ++*this; }  // postfix 

  virtual void reset(); 
private:
  std::set<ProcHandle>           mAnalyzedProcs;
  std::set<ProcHandle>::iterator mIt;

}; 

class RecordMREsVisitor;

// FIAlias may analyze all procedures defined in the program or  
// only those (iteratively) determined to be reachable.  
// The latter is our modification to Ryder's algorithm.
enum FIAliasImplement { ALL_PROCS = 0, REACHABLE_PROCS };

class ManagerFIAlias 
{ 
public:
  ManagerFIAlias(OA_ptr<AliasIRInterface> _ir);
  ~ManagerFIAlias () {}

  OA_ptr<UnionFindUniverse>
  performFIAlias( OA_ptr<IRProcIterator> procIter,
                  FIAliasImplement implement = ALL_PROCS );

  OA_ptr<IRProcIterator> getAnalyzedProcIter();

  void mergeSubSetRefs(OA_ptr<UnionFindUniverse> ufset);

protected:
  OA_ptr<AliasIRInterface> mIR;

  //===== helper datastructures and routines
  // mapping of MemRefExpr to unique ids
  std::map<OA_ptr<MemRefExpr>,int> mMREToID;
  // use a counter to assign unique ids to each MemRefExpr
  int mCount;

  // mapping of MemRefExpr to set of MemRefHandles that can
  // be expressed by said MemRefExpr
  std::map<OA_ptr<MemRefExpr>,std::set<MemRefHandle> > mMREToMemRefHandles;

  // mapping of MemRefExpr to procedures it shows up in
  std::map<OA_ptr<MemRefExpr>,std::set<ProcHandle> > mMREToProcs;

  // mapping of MemRefHandles to procedures, each MemRefHandle is only in
  // one procedure
  std::map<MemRefHandle,ProcHandle> mMemRefHandleToProc;

  std::map<ProcHandle,std::set<SymHandle> > mProcToFormalSet;

  void recordMRE( OA_ptr<MemRefExpr> mre, ProcHandle proc, MemRefHandle memref);
  void recordMRE( OA_ptr<MemRefExpr> mre, ProcHandle proc );

  OA_ptr<MemRefExpr> createDeref( OA_ptr<MemRefExpr> mre );

  std::set<OA_ptr<MemRefExpr> > 
    allMemRefExprsInSameSet( OA_ptr<MemRefExpr> pMRE, 
                             OA_ptr<UnionFindUniverse> ufset);

  void initMemRefExprs( ProcHandle proc );

  void initMemRefExprs( OA_ptr<IRProcIterator> procIter );

  void addProcToWorkList(ProcHandle proc);

  void doPhase1Iteration(StmtHandle stmt, ProcHandle currProc, OA_ptr<UnionFindUniverse> ufset);

  bool doPhase2Iteration(OA_ptr<UnionFindUniverse> ufset, std::map<int,std::map<OA_ptr<MemRefExpr>,int> > & map);

  void doPhase3Iteration(CallHandle call, ProcHandle currProc,OA_ptr<UnionFindUniverse> ufset, std::map<int,std::map<OA_ptr<MemRefExpr>,int> > & map);

  std::set<ProcHandle> mAnalyzedProcs;

  OA_ptr<UnionFindUniverse>
  performFIAliasAllProcs( OA_ptr<IRProcIterator> procIter );

  OA_ptr<UnionFindUniverse>
  performFIAliasReachableProcs( OA_ptr<IRProcIterator> procIter );

  friend class RecordMREsVisitor;

private: // helper functions
void outputMREsInSet(int setID, 
        OA_ptr<UnionFindUniverse> ufset, 
        std::map<int,std::map<OA_ptr<MemRefExpr>,int> > & map  );
void merge(int part1, int part2, OA_ptr<UnionFindUniverse> ufset, 
           std::map<int,std::map<OA_ptr<MemRefExpr>,int> > & map  );

  std::set<ProcHandle> mWorklist;

  FIAliasImplement mImplement;

};


  } // end of Alias namespace
} // end of OA namespace

#endif