DepDFSet.cpp

Go to the documentation of this file.

#include "DepDFSet.hpp"
#include <Utils/Util.hpp>

namespace OA {
  namespace Activity {

static bool debug = false;

DepDFSet::DepDFSet() //: mMakeImplicitExplicitMemoized(false)
{
    OA_DEBUG_CTRL_MACRO("DEBUG_DepDFSet:ALL", debug);
    mImplicitRemoves = new DataFlow::LocDFSet;
    mUses = new DataFlow::LocDFSet;
    mDefs = new DataFlow::LocDFSet;
}

DepDFSet::DepDFSet(const DepDFSet &other) //: mMakeImplicitExplicitMemoized(false)
{ 
    mImplicitRemoves = other.mImplicitRemoves;
    mUseToDefsMap = other.mUseToDefsMap;
    mDefToUsesMap = other.mDefToUsesMap;
    mDefs = other.mDefs;
    mUses = other.mUses;
}

DepDFSet& DepDFSet::operator=(const DepDFSet &other)
{
    //mMakeImplicitExplicitMemoized = other.mMakeImplicitExplicitMemoized;
    mImplicitRemoves = other.mImplicitRemoves;
    mUseToDefsMap = other.mUseToDefsMap;
    mDefToUsesMap = other.mDefToUsesMap;
    mDefs = other.mDefs;
    mUses = other.mUses;
    return *this;
}

//*****************************************************************
// DataFlowSet Interface Implementation
//*****************************************************************
    
OA_ptr<DataFlow::DataFlowSet> DepDFSet::clone()
{ 
    OA_ptr<DepDFSet> retval;
    retval = new DepDFSet(*this); 
    return retval; 
}

bool DepDFSet::operator==(DataFlow::DataFlowSet &other) const
{ 
    DepDFSet& recastOther = dynamic_cast<DepDFSet&>(other);
    bool retval = true;

    // make sure that each have their implicits made explicit
    // will have to copy our own because makeImplicitExplicit
    // changes the data-structure
    //DepDFSet copyThis = *this;
    //copyThis.makeImplicitExplicit();
    //recastOther.makeImplicitExplicit();

    if (mImplicitRemoves == recastOther.mImplicitRemoves
        && mUseToDefsMap == recastOther.mUseToDefsMap
        && mDefToUsesMap == recastOther.mDefToUsesMap) 
    {
        retval = true;
    } else {
        retval = false;
    }

    /*
    // make sure each dep pair in this is in other
    OA_ptr<DepIterator> depIter = getDepIterator();
    for ( ; depIter->isValid(); (*depIter)++ ) {
        OA_ptr<Location> use = depIter->use();
        OA_ptr<Location> def = depIter->def();

        bool found = false;
        OA_ptr<DepIterator> otherDepIter = recastOther.getDepIterator();
        for ( ; otherDepIter->isValid(); (*otherDepIter)++ ) {
            OA_ptr<Location> otherUse = otherDepIter->use();
            OA_ptr<Location> otherDef = otherDepIter->def();

            if (use==otherUse  && def==otherDef) {
                found = true;
            }
        }

        if (!found) {
            retval = false;
        }
    }
    
    // make sure each dep pair in this is in other
    OA_ptr<DepIterator> otherDepIter = recastOther.getDepIterator();
    for ( ; otherDepIter->isValid(); (*otherDepIter)++ ) {
        OA_ptr<Location> otherUse = otherDepIter->use();
        OA_ptr<Location> otherDef = otherDepIter->def();

        bool found = false;
        OA_ptr<DepIterator> depIter = getDepIterator();
        for ( ; depIter->isValid(); (*depIter)++ ) {
            OA_ptr<Location> use = depIter->use();
            OA_ptr<Location> def = depIter->def();

            if (use==otherUse  && def==otherDef) {
                found = true;
            }
        }

        if (!found) {
            retval = false;
        }
    }

    */
    if (debug) {
        std::cout << "operator= returning " <<  retval << std::endl;
    }
    return retval;

}

bool DepDFSet::operator!=(DataFlow::DataFlowSet &other) const
{
    if (*this == other) {
        if (debug) { std::cout << "operator!= will return false" << std::endl; }
        return false;
    } else {
        if (debug) { std::cout << "operator!= will return true" << std::endl; }
        return true;
    }
}

//*****************************************************************
// Methods specific to DepDFSet
//*****************************************************************

/*
void DepDFSet::makeImplicitExplicit()
{
    if (mMakeImplicitExplicitMemoized == true) { 
        return; 
    } else {
        mMakeImplicitExplicitMemoized = true;
    }

    // make all implicit deps that haven't been explicitly
    // removed explicit in the data-structure as well
    LocToLocDFSetMap::const_iterator mapIter;
    for (mapIter=mUseToDefsMap.begin(); mapIter!=mUseToDefsMap.end();
         mapIter++) 
    {
        if (! isImplicitRemoved(mapIter->first) ) {
            insertDep(mapIter->first,mapIter->first);
        }
    }
    for (mapIter=mDefToUsesMap.begin(); mapIter!=mDefToUsesMap.end();
         mapIter++) 
    {
        if (! isImplicitRemoved(mapIter->first) ) {
            insertDep(mapIter->first,mapIter->first);
        }
    }
}
*/

OA_ptr<DepIterator> DepDFSet::getDepIterator() const
{

    // copy self and then create iterator for it
    OA_ptr<DepDFSet> setCopy; setCopy = new DepDFSet(*this);
    //setCopy->makeImplicitExplicit();
    OA_ptr<DepIterator> retval;
    retval = new DepIterator(setCopy);
    return retval;
}

  
OA_ptr<LocIterator> DepDFSet::getDefsIterator(const OA_ptr<Location> use) const
{
    OA_ptr<DataFlow::LocDFSet> retSet;
    retSet = new DataFlow::LocDFSet();

    // get iterator over uses the given location overlaps with
    OA_ptr<LocIterator> useOverlapIter
        = mUses->getOverlapLocIterator(use);
    for ( ; useOverlapIter->isValid(); (*useOverlapIter)++ ) {
        OA_ptr<Location> loc = useOverlapIter->current();

        // iterator over associated defs
        LocToLocDFSetMap::const_iterator pos = mUseToDefsMap.find(loc);
        if (pos!=mUseToDefsMap.end()) {
            OA_ptr<LocIterator> locIter = pos->second->getLocIterator();
            for ( ; locIter->isValid(); (*locIter)++ ) {
                retSet->insert(locIter->current());
            }
        }
    }

    // loop over sets that the use 
    /*
    LocToLocDFSetMap::const_iterator mapIter;
    for (mapIter=mUseToDefsMap.begin();
         mapIter!=mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> depuse = mapIter->first;
        if (depuse->mayOverlap(*use)) {
            OA_ptr<LocIterator> locIter = mapIter->second->getLocIterator();
            for ( ; locIter->isValid(); (*locIter)++ ) {
                retSet->insert(locIter->current());
            }
        }
    }
    */

    // see if reflexive dep for use loc should be included,
    // only reason why it wouldn't is if use
    // is in the ImplicitRemoves
    // FIXME: ok could put hasMustOverlapLoc, but for now going with 
    // conservative assumption which means equivalenced symbols will get
    // short shrifted. insertDep if use==def makes same assumption.
    if (!mImplicitRemoves->hasLoc(use)) {
        retSet->insert(use);
    }

    // construct the iterator
    OA_ptr<DataFlow::LocDFSetIterator> retval;
    retval = new DataFlow::LocDFSetIterator(*retSet);
    return retval;
}
  
OA_ptr<LocIterator> DepDFSet::getUsesIterator(OA_ptr<Location> def) const
{
    OA_ptr<DataFlow::LocDFSet> retSet;
    retSet = new DataFlow::LocDFSet();

    // get iterator over uses the given location overlaps with
    OA_ptr<LocIterator> defOverlapIter
        = mDefs->getOverlapLocIterator(def);
    for ( ; defOverlapIter->isValid(); (*defOverlapIter)++ ) {
        OA_ptr<Location> loc = defOverlapIter->current();
        if (debug) {
            std::cout << "getUsesIterator: loc = ";
            loc->dump(std::cout);
        }

        // iterator over associated deps
        LocToLocDFSetMap::const_iterator pos = mDefToUsesMap.find(loc);
        if (pos!=mDefToUsesMap.end()) {
            OA_ptr<LocIterator> locIter = pos->second->getLocIterator();
            for ( ; locIter->isValid(); (*locIter)++ ) {
                retSet->insert(locIter->current());
            }
        }
    }

    /*
    LocToLocDFSetMap::const_iterator mapIter;
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> depdef = mapIter->first;
        if (depdef->mayOverlap(*def)) {
            OA_ptr<LocIterator> locIter = mapIter->second->getLocIterator();
            for ( ; locIter->isValid(); (*locIter)++ ) {
                retSet->insert(locIter->current());
            }
        }
    }
    */

    // see if reflexive dep for def loc should be included,
    // only reason why it wouldn't is if def
    // is in the ImplicitRemoves
    // FIXME: ok could put hasMustOverlapLoc, but for now going with 
    // conservative assumption which means equivalenced symbols will get
    // short shrifted
    if (!mImplicitRemoves->hasLoc(def)) {
        retSet->insert(def);
    }

    OA_ptr<DataFlow::LocDFSetIterator> retval;
    retval = new DataFlow::LocDFSetIterator(*retSet);
    return retval;
}

DepDFSet& DepDFSet::setUnion(DataFlow::DataFlowSet &other)
{
    DepDFSet& recastOther = dynamic_cast<DepDFSet&>(other);
    if (debug) {
        std::cout << "DepDFSet::setUnion" << std::endl;
    }

    // for each use in other
    LocToLocDFSetMap::const_iterator mapIter;
    for (mapIter=recastOther.mUseToDefsMap.begin();
         mapIter!=recastOther.mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use = mapIter->first;

        // if this use is already in our map then just union it into
        // the associated defs location set
        // if not then will have to make a new LocDFSet and
        // then essentially do the same thing
        if (mUseToDefsMap[use].ptrEqual(0)) {
            mUseToDefsMap[use] = new DataFlow::LocDFSet;
        }
        *(mUseToDefsMap[use]) 
            = mUseToDefsMap[use]->setUnion(*(mapIter->second));
    }
    
    // for each def in other
    for (mapIter=recastOther.mDefToUsesMap.begin();
         mapIter!=recastOther.mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def = mapIter->first;

        if (mDefToUsesMap[def].ptrEqual(0)) {
            mDefToUsesMap[def] = new DataFlow::LocDFSet;
        }
        mDefToUsesMap[def]->setUnion(*(mapIter->second));
    }

    // take on all of other's implicitRemoves that we already have
    mImplicitRemoves->setIntersect(*(recastOther.mImplicitRemoves));

    // union the uses and defs sets
    mUses->setUnion(*(recastOther.mUses));
    mDefs->setUnion(*(recastOther.mDefs));

    return *this;
}


bool DepDFSet::isImplicitRemoved(const OA_ptr<Location> loc) const
{
    return mImplicitRemoves->hasLoc(loc);
}

DepDFSet& DepDFSet::compose(DataFlow::DataFlowSet &other)
{
    DepDFSet& recastOther = dynamic_cast<DepDFSet&>(other);
    if (debug) {
        std::cout << "DepDFSet::compose" << std::endl;
        std::cout << "\t*this = ";
        dump(std::cout);
        std::cout << "\tother = ";
        recastOther.dump(std::cout);
    }
    
    OA_ptr<DepDFSet> tempDFSet;
    tempDFSet = new DepDFSet;
    
    // have to do these before do insertDeps because could be inserting
    // a dep that will take things out of the mImplicitRemoves set
    tempDFSet->mImplicitRemoves->setUnion(*(mImplicitRemoves)); 
    tempDFSet->mImplicitRemoves->setUnion(*(recastOther.mImplicitRemoves)); 

    // iterate over deps in this keying off the def
    // see if the def overlaps with anything in recastOther
    LocToLocDFSetMap::const_iterator mapIter;
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def1 = mapIter->first;
        if (debug) {
            std::cout << "def1 = "; def1->dump(std::cout); 
            std::cout << std::endl;
        }
        OA_ptr<DataFlow::LocDFSet> use1Set = mapIter->second;
        if (debug) {
            std::cout << "use1Set = "; use1Set->dump(std::cout);
        }

        // get all the defs in use2,def2 where def1 overlaps with use2
        OA_ptr<LocIterator> def2Iter = recastOther.getDefsIterator(def1);

        // loop over all use1,def1 pairs
        OA_ptr<LocIterator> use1Iter = use1Set->getLocIterator();
        for ( ; use1Iter->isValid(); (*use1Iter)++ ) {
            OA_ptr<Location> use1 = use1Iter->current();

            // get all the defs in use2, def2 where def1 overlaps with use2
            for (def2Iter->reset(); def2Iter->isValid(); (*def2Iter)++ ) {
                tempDFSet->insertDep(use1, def2Iter->current());
                if (debug) {
                    std::cout << "inserting <use1,def2Iter->current> = "; 
                    use1->dump(std::cout); 
                    std::cout << " , ";
                    def2Iter->current()->dump(std::cout); 
                    std::cout << std::endl;
                }
            }

            /*
            // as long as d,d has not been removed from recastOther,
            // where d overlaps def1, we should add use1,def1 to result
            // if it was removed but is explicitly in recastOther then
            // use1,def1 was correctly inserted into the result in above code
            // eg. x = x + y, x,x will be explictly in recastOther and
            // be an implicit that is removed due to the mustdef of x
            if (! recastOther.isImplicitRemoved(def1) ) {
                tempDFSet->insertDep(use1,def1);
                if (debug) {
                    std::cout << "inserting <use1,def1> = "; 
                    use1->dump(std::cout); 
                    std::cout << " , ";
                    def1->dump(std::cout); 
                    std::cout << std::endl;
                }
            }
            */
        }
    }

    // iterate over deps in recastOther keying off the use
    // see if the use overlaps with anything in this
    // even if it doesn't insert dep pairs for use,def 
    // as long as use,use hasn't been removed from this
    for (mapIter=recastOther.mUseToDefsMap.begin();
         mapIter!=recastOther.mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use2 = mapIter->first;
        if (debug) {
            std::cout << "use2 = "; use2->dump(std::cout); 
            std::cout << std::endl;
        }
        OA_ptr<DataFlow::LocDFSet> def2Set = mapIter->second;
        assert(!def2Set.ptrEqual(0));
        if (debug) {
            std::cout << "def2Set = ";
            def2Set->dump(std::cout);
        }

        OA_ptr<LocIterator> use1Iter = getUsesIterator(use2);

        // loop over all use2,def2 pairs
        OA_ptr<LocIterator> def2Iter = def2Set->getLocIterator();
        for ( ; def2Iter->isValid(); (*def2Iter)++ ) {
            OA_ptr<Location> def2 = def2Iter->current();

            // get all the uses in use1,def1 where def1 overlaps with use2
            for (use1Iter->reset(); use1Iter->isValid(); (*use1Iter)++ ) {
                tempDFSet->insertDep(use1Iter->current(), def2);
                if (debug) {
                    std::cout << "inserting <use1Iter->current,def2> = "; 
                    use1Iter->current()->dump(std::cout); 
                    std::cout << " , ";
                    def2->dump(std::cout); 
                    std::cout << std::endl;
                }
            }

            /*
            // as long as u,u has not been removed from this,
            // where u overlaps use2, we should add use2,def2 to result
            if (! isImplicitRemoved(use2) ) {
                tempDFSet->insertDep(use2,def2);
                if (debug) {
                    std::cout << "inserting <use2,def2> = "; 
                    use2->dump(std::cout); 
                    std::cout << " , ";
                    def2->dump(std::cout); 
                    std::cout << std::endl;
                }
            }
            */
        }
    }

    (*this) = *tempDFSet;
    if (debug) {
        std::cout << "\t*this = ";
        dump(std::cout);
    }
    

    return (*this);
}

/*
DepDFSet& DepDFSet::setIntersect(DataFlowSet &other)
{
    assert(0);
}
*/

//*****************************************************************
// Output
//*****************************************************************
void DepDFSet::dump(std::ostream &os) 
{
  /*  
    os << "\tmUseToDefsMap.size() = " << mUseToDefsMap.size() << std::endl;
    os << "\tmDefToUsesMap.size() = " << mDefToUsesMap.size() << std::endl;
   */ 
   
    os << "\tuses" << std::endl;
    // iterate over all uses
    std::map<OA_ptr<Location>,OA_ptr<DataFlow::LocDFSet> >::const_iterator 
        mapIter;
    for (mapIter=mUseToDefsMap.begin();
         mapIter!=mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        use->dump(os);
        os << " ==> ";
        locset->dump(os);
        os << std::endl;
    }
    
    os << "\tdefs" << std::endl;
    // iterate over all defs
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        def->dump(os);
        os << " ==> ";
        locset->dump(os);
        os << std::endl;
    }
   
    os << "\tmImplicitRemoves = ";
    mImplicitRemoves->dump(os);
  
    os << "\tmUses = ";
    mUses->dump(os);
  
    os << "\tmDefs = ";
    mDefs->dump(os);

}

void DepDFSet::dump(std::ostream &os) const
{
   
/*
    os << "\tmUseToDefsMap.size() = " << mUseToDefsMap.size() << std::endl;
    os << "\tmDefToUsesMap.size() = " << mDefToUsesMap.size() << std::endl;
*/

    os << "\tuses" << std::endl;
    // iterate over all uses
    std::map<OA_ptr<Location>,OA_ptr<DataFlow::LocDFSet> >::const_iterator 
        mapIter;
    for (mapIter=mUseToDefsMap.begin();
         mapIter!=mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        use->dump(os);
        os << " ==> ";
        locset->dump(os);
        os << std::endl;
    }
    
    os << "\tdefs" << std::endl;
    // iterate over all defs
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        def->dump(os);
        os << " ==> ";
        locset->dump(os);
        os << std::endl;
    }
   
    os << "\tmImplicitRemoves = ";
    mImplicitRemoves->dump(os);
  
    os << "\tmUses = ";
    mUses->dump(os);
  
    os << "\tmDefs = ";
    mDefs->dump(os);

 }


void DepDFSet::dump(std::ostream &os, OA_ptr<IRHandlesIRInterface> ir) 
{
/*
    os << "\tmUseToDefsMap.size() = " << mUseToDefsMap.size() << std::endl;
    os << "\tmDefToUsesMap.size() = " << mDefToUsesMap.size() << std::endl;
*/


    os << "\tuses" << std::endl;
    // iterate over all uses
    std::map<OA_ptr<Location>,OA_ptr<DataFlow::LocDFSet> >::const_iterator mapIter;
    for (mapIter=mUseToDefsMap.begin();
         mapIter!=mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        use->dump(os,ir);
        os << " ==> ";
        locset->dump(os,ir);
        os << std::endl;
    }
    
    os << "\tdefs" << std::endl;
    // iterate over all defs
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;

        os << "\t\t";
        def->dump(os,ir);
        os << " ==> ";
        locset->dump(os,ir);
        os << std::endl;
    }
    
    // dump implicitRemoves
    os << "\tmImplicitRemoves = ";
    mImplicitRemoves->dump(os,ir); 
  
    os << "\tmUses = ";
    mUses->dump(os,ir);
  
    os << "\tmDefs = ";
    mDefs->dump(os,ir);

}

void DepDFSet::output(OA::IRHandlesIRInterface& ir) {
    
    // iterate over all uses
    sOutBuild->mapStart("mUseToDefsMap","UseLoc","DefLocSet");
    std::map<OA_ptr<Location>,OA_ptr<DataFlow::LocDFSet> >::const_iterator mapIter;
    for (mapIter=mUseToDefsMap.begin();
         mapIter!=mUseToDefsMap.end(); mapIter++ )
    {
        OA_ptr<Location> use = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;
        sOutBuild->mapEntryStart();
          sOutBuild->mapKeyStart();
            use->output(ir);
          sOutBuild->mapKeyEnd();
          sOutBuild->mapValueStart();
            locset->output(ir);
          sOutBuild->mapValueEnd();
        sOutBuild->mapEntryEnd();
    }
    sOutBuild->mapEnd("mUseToDefsMap");
    
    // iterate over all defs
    sOutBuild->mapStart("mDefToUsesMap","DefLoc","UseLocSet");
    for (mapIter=mDefToUsesMap.begin();
         mapIter!=mDefToUsesMap.end(); mapIter++ )
    {
        OA_ptr<Location> def = mapIter->first;
        OA_ptr<DataFlow::LocDFSet> locset = mapIter->second;
        sOutBuild->mapEntryStart();
          sOutBuild->mapKeyStart();
            def->output(ir);
          sOutBuild->mapKeyEnd();
          sOutBuild->mapValueStart();
            locset->output(ir);
          sOutBuild->mapValueEnd();
        sOutBuild->mapEntryEnd();
    }
    sOutBuild->mapEnd("mDefToUsesMap");

    
    // dump implicitRemoves
    std::ostringstream label1;
    label1 << indt << "ImplicitRemoves:";
    sOutBuild->outputString( label1.str() );
    mImplicitRemoves->output(ir); 

    std::ostringstream label2;
    label2 << indt << "Uses:";
    sOutBuild->outputString( label2.str() );
    mUses->output(ir); 

    std::ostringstream label3;
    label3 << indt << "Defs:";
    sOutBuild->outputString( label3.str() );
    mDefs->output(ir); 
    
}


//*****************************************************************
// Construction
//*****************************************************************
  
void DepDFSet::insertDep(OA_ptr<Location> use, OA_ptr<Location> def)
{
    if (use==def) {
        mImplicitRemoves->remove(use);

    } else {
        if (mUseToDefsMap[use].ptrEqual(0)) {
            mUseToDefsMap[use] = new DataFlow::LocDFSet;
        }
        if (mDefToUsesMap[def].ptrEqual(0)) {
            mDefToUsesMap[def] = new DataFlow::LocDFSet;
        }

        mUseToDefsMap[use]->insert(def);
        mDefToUsesMap[def]->insert(use);

        mUses->insert(use);
        mDefs->insert(def);
    }
}

void DepDFSet::removeImplicitDep(OA_ptr<Location> use, OA_ptr<Location> def)
{
//    mMakeImplicitExplicitMemoized = false;
    // to be conservative only insert locations when the use and def must
    // overlap each other, sublocs that only have partial accuracy will
    // only may loc
    if (use->mustOverlap(*def)) {
        mImplicitRemoves->insert(use);
    }
}

  } // end of Activity namespace
} // end of OA namespace