auto_ManagerAvailableExpressionsStandard.cpp

Go to the documentation of this file.

// ManagerAvailableExpressionsStandard.cpp

#include "auto_ManagerAvailableExpressionsStandard.hpp"

using namespace std;
using namespace OA::DataFlow;
using namespace OA::CFG;
using namespace OA::Alias;
using namespace OA::SideEffect;

namespace OA {
  namespace AvailableExpressions {

static bool debug = false;


ManagerAvailableExpressionsStandard::ManagerAvailableExpressionsStandard(
    OA_ptr<AvailableExpressionsIRInterface> _ir)
    :
    mIR(_ir)
{
    OA_DEBUG_CTRL_MACRO("DEBUG_ManagerAvailableExpressionsStandard:ALL", debug);
    mSolver = new CFGDFSolver(CFGDFSolver::Forward, *this);
}


OA_ptr<DataFlowSet> ManagerAvailableExpressionsStandard::initializeTop()
{
    OA_ptr<AvailableExpressionsDFSet> retval;
    retval = new AvailableExpressionsDFSet();
    return retval;
}


OA_ptr<DataFlowSet> ManagerAvailableExpressionsStandard::initializeBottom()
{
    OA_ptr<AvailableExpressionsDFSet> retval;
    retval = new AvailableExpressionsDFSet();
    return retval;
}


OA_ptr<DataFlowSet>
ManagerAvailableExpressionsStandard::initializeNodeIN(OA_ptr<NodeInterface> n)
{
    OA_ptr<AvailableExpressionsDFSet> retval;
    retval = new AvailableExpressionsDFSet();
    return retval;
}


OA_ptr<DataFlowSet>
ManagerAvailableExpressionsStandard::initializeNodeOUT(OA_ptr<NodeInterface> n)
{
    OA_ptr<AvailableExpressionsDFSet> retval;
    retval = new AvailableExpressionsDFSet();
    return retval;
}


OA_ptr<AvailableExpressionsStandard> ManagerAvailableExpressionsStandard::performAnalysis(
    ProcHandle proc,
    OA_ptr<CFGInterface> cfg,
    OA_ptr<OA::Alias::Interface> alias,
    OA_ptr<InterSideEffectInterface> interSE)
{
    if (debug) {
        cout << "In AvailableExpressions::ManagerAvailableExpressionsStandard::performAnalysis"
             << endl;
    }

    // create the object we'll store results in
    mAvailableExpressionsMap = new AvailableExpressionsStandard(proc, mIR);

    // store Alias information for use within the transfer function
    mAlias = alias;

    {

        // maycode for defs[s]
        OA_ptr<IRStmtIterator> stmtIter;
        stmtIter = mIR->getStmtIterator(proc);
        for(; stmtIter->isValid(); ++(*stmtIter)) {
            StmtHandle stmt = stmtIter->current();

            OA_ptr<MemRefHandleIterator> defsIter;
            defsIter = mIR->getDefMemRefs(stmt);
            for (; defsIter->isValid(); (*defsIter)++) {
                MemRefHandle ref = defsIter->current();

                OA_ptr<LocIterator> locIter;
                locIter = alias->getMayLocs(ref);
                for (; locIter->isValid(); ++(*locIter)) {
                    mStmt2MayDefMap[stmt].insert(locIter->current());
                }
            }
        }
    } {

        // mustcode for defs[s]
        OA_ptr<IRStmtIterator> stmtIter;
        stmtIter = mIR->getStmtIterator(proc);
        for(; stmtIter->isValid(); ++(*stmtIter)) {
            StmtHandle stmt = stmtIter->current();

            OA_ptr<MemRefHandleIterator> defsIter;
            defsIter = mIR->getDefMemRefs(stmt);
            for (; defsIter->isValid(); (*defsIter)++) {
                MemRefHandle ref = defsIter->current();
                OA_ptr<LocIterator> locIter;
                locIter = alias->getMayLocs(ref);
                for (; locIter->isValid(); ++(*locIter)) {
                    mStmt2MustDefMap[stmt].insert(locIter->current());
                }
            }
        }
    }
    {

      OA_ptr<IRStmtIterator> stmtIter;
      OA_ptr<ExprHandleIterator> iterHdlExpr;
      OA_ptr<NewExprTree> eTree;

      iterHdlExp = getExprHandleIterator(OA::StmtHandle stmt);

      // iterate through all statements in the procedure
      stmtIter = mIR->getStmtIterator(proc);
      for(; stmtIter->isValid(); ++(*stmtIter)) {
          StmtHandle stmt = stmtIter->current();

          // iterate through all expressions in the statement
          iterHdlExpr = mIR->getExprHandleIterator(stmt);
          for(; iterHdlExpr->isValid(); ++(*iterHdlExpr)) {
              ExprHandle hExp = iterHdlExpr->current();
              
              eTree = mIR->getNewExprTree(hExp);
              mStmt2MayExprMap[hExp].insert(eTree);
          }
      }
    } {

      OA_ptr<IRStmtIterator> stmtIter;
      OA_ptr<ExprHandleIterator> iterHdlExpr;
      OA_ptr<NewExprTree> eTree;

      iterHdlExp = getExprHandleIterator(OA::StmtHandle stmt);

      // iterate through all statements in the procedure
      stmtIter = mIR->getStmtIterator(proc);
      for(; stmtIter->isValid(); ++(*stmtIter)) {
          StmtHandle stmt = stmtIter->current();

          // iterate through all expressions in the statement
          iterHdlExpr = mIR->getExprHandleIterator(stmt);
          for(; iterHdlExpr->isValid(); ++(*iterHdlExpr)) {
              ExprHandle hExp = iterHdlExpr->current();
              
              eTree = mIR->getNewExprTree(hExp);
              mStmt2MayExprMap[hExp].insert(eTree);
          }
      }
    }
    {

        // maycode for uses[s]
        OA_ptr<IRStmtIterator> stmtIter;
        stmtIter = mIR->getStmtIterator(proc);
        for(; stmtIter->isValid(); ++(*stmtIter)) {
            StmtHandle stmt = stmtIter->current();

            OA_ptr<MemRefHandleIterator> useIterPtr = mIR->getUseMemRefs(stmt);
            for (; useIterPtr->isValid(); (*useIterPtr)++) {
                MemRefHandle ref = useIterPtr->current();
                OA_ptr<LocIterator> locIterPtr = alias->getMayLocs(ref);
                for (; locIterPtr->isValid(); ++(*locIterPtr)) {
                    mStmt2MayUseMap[stmt].insert(locIterPtr->current());
                }
            }
        }
    } {

        // mustcode for uses[s]
        OA_ptr<IRStmtIterator> stmtIter;
        stmtIter = mIR->getStmtIterator(proc);
        for(; stmtIter->isValid(); ++(*stmtIter)) {
            StmtHandle stmt = stmtIter->current();

            OA_ptr<MemRefHandleIterator> useIterPtr = mIR->getUseMemRefs(stmt);
            for (; useIterPtr->isValid(); (*useIterPtr)++) {
                MemRefHandle ref = useIterPtr->current();
                OA_ptr<LocIterator> locIterPtr = alias->getMustLocs(ref);
                for (; locIterPtr->isValid(); ++(*locIterPtr)) {
                    mStmt2MustUseMap[stmt].insert(locIterPtr->current());
                }
            }
        }
    }

    // use the dataflow solver to get the In and Out sets for the
    // basic blocks (BBs).
    mSolver->solve(cfg, ITERATIVE);

    // get exit node for CFG and determine what data flow values exit it.
    // store these data flow values in the result's exit information.
    OA_ptr<NodeInterface> node;
    node = cfg->getExit();
    OA_ptr<DataFlowSet> x = mSolver->getOutSet(node);
    OA_ptr<AvailableExpressionsDFSet> exitSet =
        x.convert<AvailableExpressionsDFSet>();
    for(AvailableExpressionsDFSet::iterator i = exitSet->begin();
        i != exitSet->end(); i++)
    {
        mAvailableExpressionsMap->insertExit(*i);
    }


    return mAvailableExpressionsMap;
}

void ManagerAvailableExpressionsStandard::dumpset(OA_ptr<AvailableExpressionsDFSet> inSet) {
    OA_ptr<set<OA_ptr<NewExprTree>  > > setRecast;
    setRecast = inSet.convert<set<OA_ptr<NewExprTree>  > >();
    set<OA_ptr<NewExprTree>  >::iterator iter;
    iter = setRecast->begin();
    for(; iter != setRecast->end(); iter++) {
        cout << (*iter)->toString(mIR);
    }
    cout << endl;
}


OA_ptr<DataFlowSet>
ManagerAvailableExpressionsStandard::meet(
    OA_ptr<DataFlowSet> set1orig,
    OA_ptr<DataFlowSet> set2orig)
{
    // convert the incoming sets to sets of the specific flow value.
    OA_ptr<AvailableExpressionsDFSet> set1 = set1orig.convert<AvailableExpressionsDFSet>();
    OA_ptr<AvailableExpressionsDFSet> set2 = set2orig.convert<AvailableExpressionsDFSet>();

    if (debug) {
        cout << "ManagerAvailableExpressionsStandard::meet" << endl;
        cout << "\tset1 = ";
        dumpset(set1);
        cout << "\tset2 = ";
        dumpset(set2);
    }

    // perform the meet operator on the left hand set.  It's okay to modify the
    // set and return it as a result [since the solver passes a temporary set
    // in as set1.  See the CFGDFProblem header for more info.
    set1->intersectEqu(*set2);

    if (debug) {
        cout << endl << "\tcalculated set = ";
        dumpset(set1);
    }

    return set1;
}

OA_ptr<DataFlowSet> ManagerAvailableExpressionsStandard::genSet(StmtHandle stmt)
{
    OA_ptr<AvailableExpressionsDFSet> genSet;
    genSet =  new AvailableExpressionsDFSet();

    // Generate GEN code:
    OA_ptr<AvailableExpressionsDFSet> set1;
    set1 = new AvailableExpressionsDFSet(mStmt2MustExprMap[stmt]);
    genSet = set1;

    return genSet;
}

OA_ptr<DataFlowSet> ManagerAvailableExpressionsStandard::killSet(
    StmtHandle stmt, OA_ptr<DataFlowSet> xdfset)
{
    OA_ptr<AvailableExpressionsDFSet> x;
    x = xdfset.convert<AvailableExpressionsDFSet>();

    OA_ptr<AvailableExpressionsDFSet> killSet;
    killSet = new AvailableExpressionsDFSet();

    // Generate KILL code:
    OA_ptr<DFAGenDFSet<OA_ptr<NewExprTree> > > set2;
    set2 = new DFAGenDFSet<OA_ptr<NewExprTree> >();
    AvailableExpressionsDFSet::iterator iter1;
    OA_ptr<NewExprTree> iter1Val;

    for(iter1 = x->begin(); iter1 != x->end(); iter1++) {
        iter1Val = *iter1
        OA_ptr<DFAGenDFSet<OA_ptr<Location> > > set3;
        set3 = new DFAGenDFSet<OA_ptr<Location> >(mStmt2MayUseMap[iter1Val]);
        OA_ptr<DFAGenDFSet<OA_ptr<Location> > > set4;
        set4 = new DFAGenDFSet<OA_ptr<Location> >(mStmt2MayDefMap[stmt]);
        OA_ptr<DFAGenDFSet<OA_ptr<Location> > > set5;
        set5 = set3->intersect(set4);
        bool cond1;
        cond1 = !set5->isEmpty();
        bool cond;
        cond = cond1;
        if(cond) {
            set2->insert(iter1Val);
        }
    }
    killSet = set2;

    return killSet;
}

// Currently the transfer function used by DFAGen is assumed to be:
// Y = gen[n] U (X - kill[n]).
OA_ptr<DataFlowSet>
ManagerAvailableExpressionsStandard::transfer(
    OA_ptr<DataFlowSet> xdfset,
    StmtHandle stmt)
{
    OA_ptr<set<".FLOWTYPE" > > xdfgenset;
    xdfgenset = xdfset.convert<set<OA_ptr<NewExprTree>  > >();

    OA_ptr<AvailableExpressionsDFSet> x;
    x = new AvailableExpressionsDFSet(*xdfgenset);

    // if debug mode is on print information about transfer function
    if (debug) {
        cout << "In transfer: " << endl;
        cout << "\t Stmt  = " << mIR->toString(stmt) << endl;
        cout << "\t X     = ";
        dumpset(x);
    }

    OA_ptr<DataFlowSet> genBaseObj = genSet(stmt);
    OA_ptr<AvailableExpressionsDFSet> gen = genBaseObj.convert<AvailableExpressionsDFSet>();

    OA_ptr<DataFlowSet> killBaseObj = killSet(stmt, x);
    OA_ptr<AvailableExpressionsDFSet> kill = killBaseObj.convert<AvailableExpressionsDFSet>();


    // Add gen[n] to Y
    AvailableExpressionsDFSet::iterator genIter = gen->begin();
    for(; genIter != gen->end(); ++genIter) {
        OA_ptr<NewExprTree>  genVal;
        genVal = *genIter;
        mAvailableExpressionsMap->insert(stmt, genVal);
    }
    // Add X - kill[n] to Y
    x->minusEqu(*kill);
    AvailableExpressionsDFSet::iterator xIter = x->begin();
    for(; xIter != x->end(); ++xIter) {
        OA_ptr<NewExprTree>  xVal;
        xVal = *xIter;
        mAvailableExpressionsMap->insert(stmt, xVal);
    }

    // if debug mode is on print information about transfer function
    if(debug) {
        cout << "\t gen  = ";
        dumpset(gen);
        cout << "\t kill = ";
        dumpset(kill);
        cout << "\t Y    = ";
        dumpset(mAvailableExpressionsMap->getAvailableExpressionsSet(stmt));
    }

    return mAvailableExpressionsMap->getAvailableExpressionsSet(stmt);
}

  } // end of namespace AvailableExpressions
} // end of namespace OA