oagFpgaOccGraph.cpp

Go to the documentation of this file.

#include "oagFpga.h"
#include "oagFpgaModGraph.h"
#include "oagFpgaOccGraph.h"
#include <memory>

#include "oagFpgaDebug.h"

namespace oagFpga {

// Used in OccGraph::getNetToBBConnection
typedef oa::oaIter<oa::oaOccNet> OccNetIter;


// *****************************************************************************
// convertRefListToOccRefList()
//
//
// *****************************************************************************
void
OccGraph::convertRefListToOccRefList(const list<BBRef> &source,
                                     oa::oaOccurrence *occurrence,
                                     list<OccRef> &result) {
    for(list<BBRef>::const_iterator it = source.begin(); it != source.end(); ++it) {
        result.push_back(OccRef(*it, occurrence));
    }
}

/*
// *****************************************************************************
// enumerateKfeasibleCuts()
//
//
// *****************************************************************************
void
OccGraph::enumerateKfeasibleCuts(OccRef x, unsigned int maxCutSize, CutSet &result) {
    // UNIMPLEMENTED
    QUIT_ON_INTERNAL_ERROR;
}


// *****************************************************************************
// clearKfeasibleCuts()
//
//
// *****************************************************************************
void
OccGraph::clearKfeasibleCuts(oa::oaOccurrence *occurrence) {
    // UNIMPLEMENTED
    QUIT_ON_INTERNAL_ERROR;
}
*/

// *****************************************************************************
// getFanout()
//
//
// *****************************************************************************
void
OccGraph::getFanout(OccRef x, list<OccRef> &result) {
    convertRefListToOccRefList(getGraph(x)->getFanout(x.ref), x.occurrence, result);
}
    
    
// *****************************************************************************
// getTransitiveFanin()
//
//
// *****************************************************************************
void
OccGraph::getTransitiveFanin(OccRef x, list<OccRef> &transitiveFanin) {
    list<BBRef> flatResult;
    getGraph(x)->getTransitiveFanin(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, transitiveFanin);
}


// *****************************************************************************
// getTransitiveFanout()
//
//
// *****************************************************************************
void
OccGraph::getTransitiveFanout(OccRef x, list<OccRef> &transitiveFanout) {
    list<BBRef> flatResult;
    getGraph(x)->getTransitiveFanout(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, transitiveFanout);
}


/*
// *****************************************************************************
// getFaninRoots()
//
//
// *****************************************************************************
void
OccGraph::getFaninRoots(OccRef x, list<OccRef> &faninRoots) {
    list<BBRef> flatResult;
    getGraph(x)->getFaninRoots(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, faninRoots);
}

// *****************************************************************************
// getFanoutRoots()
//
//
// *****************************************************************************
void
OccGraph::getFanoutRoots(OccRef x, list<OccRef> &fanoutRoots) {
    list<oagAi::Ref> flatResult;
    getGraph(x)->getFanoutRoots(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, fanoutRoots);
}

// *****************************************************************************
// testEquivalence()
//
//
// *****************************************************************************
bool
OccGraph::testEquivalence(OccRef x, OccRef y) {

    return x.occurrence == y.occurrence && getGraph(x)->testEquivalence(x.ref, y.ref);
}

// *****************************************************************************
// getEquivalents()
//
//
// *****************************************************************************
void
OccGraph::getEquivalents(OccRef x, list<OccRef> &result) {
    list<oagAi::Ref> flatResult;
    getGraph(x)->getEquivalents(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, result);
}


// *****************************************************************************
// getFanoutOfEquivalentNodes()
//
//
// *****************************************************************************
void
OccGraph::getFanoutOfEquivalentNodes(OccRef x, list<OccRef> &result) {
    list<oagAi::Ref> flatResult;
    getGraph(x)->getFanoutOfEquivalentNodes(x.ref, flatResult);
    
    convertRefListToOccRefList(flatResult, x.occurrence, result);
}
*/


// *****************************************************************************
// getNetToBBConnection()
//
//
// *****************************************************************************
oa::oaOccBitNet *   
OccGraph::getNetToBBConnection(OccRef x) {
    Manager *manager = Manager::get(x.occurrence->getModule()->getDesign());
    oa::oaModBitNet *modNet = manager->getNetToBBConnection(x.ref);
    if (!modNet) {
        return NULL;
    }

    oa::oaOccurrence *topOcc = x.occurrence->getTopOccurrence();
    auto_ptr<OccNetIter> occNetIter;
    if (x.occurrence == topOcc) {
        // let the database find the net in the occurrence that corresponds to
        // the modNet
        occNetIter.reset(new OccNetIter(modNet->getOccNets(topOcc)));
    } else {
        // search all nets in the occurrence for the one that corresponds to
        // the modNet
        occNetIter.reset(
                new OccNetIter(x.occurrence->getNets(oacNetIterSingleBit)));
    }
    oa::oaOccNet *occNet;
    while((occNet = occNetIter->getNext())) {
        oa::oaOccBitNet *occBitNet = toBitNet(occNet);
        if (occBitNet->getModNet() == modNet) {
            return occBitNet;
        }
    }

    // one of the occNets must correspond to the modNet!
    QUIT_ON_INTERNAL_ERROR;
    return NULL;
}


// *****************************************************************************
// getNetToAiConnection()
//
//
// *****************************************************************************
OccRef
OccGraph::getNetToAiConnection(oa::oaOccBitNet *net) {
    Manager *manager = Manager::get(net->getModNet()->getDesign());
    oa::oaModBitNet *modNet = static_cast<oa::oaModBitNet*>(net->getModNet());
    return OccRef(manager->getNetToAiConnection(modNet), net->getOccurrence());
}


// *****************************************************************************
// getOutputs()
//
//
// *****************************************************************************
void         
OccGraph::getOutputs(oa::oaOccurrence *top, list<OccRef> &result) {
    assert(top);
    oa::oaOccTerm *term;
    oa::oaIter<oa::oaOccTerm> termIter(top->getTerms(oacTermIterSingleBit));
    while((term = termIter.getNext())) {
        if(term->getTermType() == oa::oacOutputTermType) {
            ModRef modRef = oagFpga::ModGraph::prepareNetToAiConnection(toBitNet(term->getNet()->getModNet()));
            result.push_back(OccRef(modRef.ref, top));
        }
    }
}


// *****************************************************************************
// getOutputs()
//
//
// *****************************************************************************
void         
OccGraph::getOutputs(oa::oaOccurrence *top, list<oa::oaOccBitNet *> &result) {
    assert(top);
    oa::oaOccTerm *term;
    oa::oaIter<oa::oaOccTerm> termIter(top->getTerms(oacTermIterSingleBit));
    while((term = termIter.getNext())) {
        if(term->getTermType() == oa::oacOutputTermType) {
            result.push_back(toBitNet(term->getNet()));
        }
    }
}


// *****************************************************************************
// getInputs()
//
//
// *****************************************************************************
void         
OccGraph::getInputs(oa::oaOccurrence *top, list<OccRef> &result) {
    assert(top);
    oa::oaOccTerm *term;
    oa::oaIter<oa::oaOccTerm> termIter(top->getTerms(oacTermIterSingleBit));
    while((term = termIter.getNext())) {
        if(term->getTermType() == oa::oacInputTermType) {
            ModRef modRef = oagFpga::ModGraph::prepareNetToAiConnection(toBitNet(term->getNet()->getModNet()));
            result.push_back(OccRef(modRef.ref, top));
        }
    }
}


// *****************************************************************************
// getInputs()
//
//
// *****************************************************************************
void         
OccGraph::getInputs(oa::oaOccurrence *top, list<oa::oaOccBitNet *> &result) {
    assert(top);
    oa::oaOccTerm *term;
    oa::oaIter<oa::oaOccTerm> termIter(top->getTerms(oacTermIterSingleBit));
    while((term = termIter.getNext())) {
        if(term->getTermType() == oa::oacInputTermType) {
            result.push_back(toBitNet(term->getNet()));
        }
    }
}


// *****************************************************************************
// getConstants()
//
// *****************************************************************************
void         
OccGraph::getConstants(oa::oaOccurrence *occurrence, list<OccRef> &zeros, list<OccRef> &ones) {
    assert(occurrence);
    
    const oa::oaNativeNS nativeNS;
    const oa::oaScalarName tie0Name(nativeNS, "tie0");
    const oa::oaScalarName tie1Name(nativeNS, "tie1");

    list<oa::oaOccurrence*> toBeVisited;
    toBeVisited.push_back(occurrence);

    while(!toBeVisited.empty()) {
        oa::oaOccurrence *currentOcc = toBeVisited.front();
        toBeVisited.pop_front();
        
        // add the constant zero inside this object
        zeros.push_back(OccGraph::constantZero(currentOcc));
        oa::oaOccScalarNet *net;
        if ((net = oa::oaOccScalarNet::find(currentOcc, tie0Name))) {
            OccRef ref = getNetToAiConnection(net);
            assert(!isNull(ref));
            zeros.push_back(ref);
        }
        if ((net = oa::oaOccScalarNet::find(currentOcc, tie1Name))) {
            OccRef ref = getNetToAiConnection(net);
            assert(!isNull(ref));
            ones.push_back(ref);
        }
               
        // recursively descend into the instances inside this object
        oa::oaOccInst *inst;
        oa::oaIter<oa::oaOccInst> instIter(currentOcc->getInsts());
        while((inst = instIter.getNext())) {
            oa::oaOccurrence *subOcc = inst->getMasterOccurrence();
            if(!subOcc) {
                oa::oaString str;
                inst->getInst()->getCellName(oa::oaVerilogNS(), str);
                cerr << "ERROR: Could not find instantiated design \"" << str << "\" in OA database" << endl;
                QUIT_ON_ERROR;
            }
            toBeVisited.push_back(subOcc);
        }
    }
}


// *****************************************************************************
// getStates()
//
// *****************************************************************************
void         
OccGraph::getStates(oa::oaOccurrence *occurrence, list<OccRef> &result) {
    assert(occurrence);
    
    list<oa::oaOccurrence*> toBeVisited;
    toBeVisited.push_back(occurrence);

    while(!toBeVisited.empty()) {
        oa::oaOccurrence *currentOcc = toBeVisited.front();
        toBeVisited.pop_front();
        
        // add the state bits inside this object
        list<oagAi::Ref> currentResult;
        getGraph(currentOcc)->getAllSequential(currentResult);
        convertRefListToOccRefList(currentResult, currentOcc, result);
        
        // recursively descend into the instances inside this object
        oa::oaOccInst *inst;
        oa::oaIter<oa::oaOccInst> instIter(currentOcc->getInsts());
        while((inst = instIter.getNext())) {
            oa::oaOccurrence *subOcc = inst->getMasterOccurrence();
            if(!subOcc) {
                oa::oaString str;
                inst->getInst()->getCellName(oa::oaVerilogNS(), str);
                cerr << "ERROR: Could not find instantiated design \"" << str << "\" in OA database" << endl;
                QUIT_ON_ERROR;
            }
            toBeVisited.push_back(subOcc);
        }
    }
}    


// *****************************************************************************
// getLocalStates()
//
//
// *****************************************************************************
void         
OccGraph::getLocalStates(oa::oaOccurrence *occurrence, list<OccRef> &result) {
    assert(occurrence);

    // add the state bits inside this object
    list<oagAi::Ref> flatResult;
    getGraph(occurrence)->getAllSequential(flatResult);
    convertRefListToOccRefList(flatResult, occurrence, result);
}    


// *****************************************************************************
// getAllConnections()
//
//
// *****************************************************************************
void
OccGraph::getAllConnections(oa::oaOccBitNet *net, 
                            set<oa::oaOccBitNet*> &connectedNets,
                            set<OccRef> &connectedRefs,
                            bool searchForwardThroughGraph,
                            bool searchBackwardThroughGraph,
                            bool searchThroughHierarchy,
                            bool searchThroughEquivNets,
                            bool searchThroughEquivRefs,
                            bool includeSelf) {
    assert(net);
    
    // has this net been visited?
    if (connectedNets.find(net) == connectedNets.end()) {
        connectedNets.insert(net);
    } else {
        return;
    }

    // --- directly connected refs
    getAllConnections(getNetToAiConnection(net), connectedNets, connectedRefs,
            searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
            searchThroughEquivNets, searchThroughEquivRefs, true);
    
    // --- equivalent nets (if searchThroughEquivNets)
    if (searchThroughEquivNets) {
        oa::oaOccBitNet *equivNet;
        oa::oaIter<oa::oaOccBitNet> equivIter(net->getEquivalentNets());
        while((equivNet = equivIter.getNext())) {
            getAllConnections(equivNet, connectedNets, connectedRefs,
                searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                searchThroughEquivNets, searchThroughEquivRefs, true);
        }
    }
    
    // --- across hierarchy (if searchThroughHierarchy)
    if (searchThroughHierarchy) {

        // down hierarchy
        oa::oaOccInstTerm   *nextInstTerm;
        oa::oaIter<oa::oaOccInstTerm> instTermIter(net->getInstTerms(oacInstTermIterAll));                                                                                 
        while((nextInstTerm = instTermIter.getNext())) {
            oa::oaOccTerm *nextTerm = nextInstTerm->getTerm();
            assert(nextTerm);
            assert(nextTerm->getNumBits() == 1);
            oa::oaOccBitNet *nextNet = toBitNet(nextTerm->getNet());
            assert(nextNet);
            getAllConnections(nextNet, connectedNets, connectedRefs,
                searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                searchThroughEquivNets, searchThroughEquivRefs, true);
        }      
        
        // up hierarchy
        oa::oaOccTerm   *nextTerm;
        oa::oaIter<oa::oaOccTerm> termIter(net->getTerms(oacTermIterAll));
        while((nextTerm = termIter.getNext())) {
            oa::oaOccInst *parent = net->getOccurrence()->getOccInst();
            if (parent) {
             
                // find the corresponding InstTerm in the parent
                oa::oaOccInstTerm *nextInstTerm;
                unsigned int bitIndex = oacNullIndex;
                if (nextTerm->isImplicit()) {
                    // this is an implicit bit in a bus
                          
                    // find the corresponding bus term
                    oa::oaOccTerm *busTerm = findBusTerm(static_cast<oa::oaOccBusTermBit*>(nextTerm));
                    assert(busTerm);

                    // which bit within the bus term?
                    oa::oaName generalName;
                    nextTerm->getName(generalName);
                    assert(generalName.getVectorBit());
                    bitIndex = generalName.getVectorBit()->getIndex();
                    
                    if (parent->usesTermPositions()) {   
                        // connected by position
                        unsigned int portPosition = busTerm->getPosition();
                        assert(portPosition != oacNullIndex);
                        nextInstTerm = oa::oaOccInstTerm::find(parent, portPosition);
                    } else {
                        // connected by name
                        oa::oaName termName;
                        busTerm->getName(termName);
                        nextInstTerm = oa::oaOccInstTerm::find(parent, termName);
                    }

                    // select appropriate bit out of instTerm
                    if (nextInstTerm) {
                      nextInstTerm = nextInstTerm->getBit(bitIndex);
                    }

                } else {
                    // this is a scalar term

                    if (parent->usesTermPositions()) {
                        // connected by position
                        unsigned int portPosition = nextTerm->getPosition();
                        assert(portPosition != oacNullIndex);
                        nextInstTerm = oa::oaOccInstTerm::find(parent, portPosition);
                    } else {
                        // connected by name
                        oa::oaName termName;
                        nextTerm->getName(termName);
                        nextInstTerm = oa::oaOccInstTerm::find(parent, termName);
                    }
                }
                   
                if (!nextInstTerm) {
                    // this Term wasn't connected to an InstTerm
                    DEBUG_PRINTLN("\tterminal isn't bound to any instTerm!")
                    continue;
                }

                assert(nextInstTerm->getNumBits() == 1);
                oa::oaOccBitNet *nextNet = toBitNet(nextInstTerm->getNet());
                assert(nextNet);

                getAllConnections(nextNet, connectedNets, connectedRefs,
                    searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                    searchThroughEquivNets, searchThroughEquivRefs, true);
                 
            } else {
                DEBUG_PRINTLN("\t\talready at top of hierarchy")
            }

        }
    }
 
    // -- exclude self
    if (!includeSelf) {
        connectedNets.erase(net);
    } 
}


// *****************************************************************************
// getAllConnections()
//
//
// *****************************************************************************    
void 
OccGraph::getAllConnections(OccRef x, 
                            set<oa::oaOccBitNet*> &connectedNets,
                            set<OccRef> &connectedRefs,
                            bool searchForwardThroughGraph,
                            bool searchBackwardThroughGraph,
                            bool searchThroughHierarchy,
                            bool searchThroughEquivNets,
                            bool searchThroughEquivRefs,
                            bool includeSelf) {
    if (isNull(x)) {
        return;
    }

    // has this ref been visited?
    if (connectedRefs.find(x) == connectedRefs.end()) {
        connectedRefs.insert(x);
    } else {
        return;
    }
    
    // --- directly connected nets
    if (isTerminal(x) && !isInverted(x)) {
        oa::oaOccBitNet *net;
        if ((net = getNetToAiConnection(x))) {
            getAllConnections(net, connectedNets, connectedRefs,
                searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                searchThroughEquivNets, searchThroughEquivRefs, true);
        }
    }

    // --- connected backward through graph (if searchBackwardThroughGraph)
    if (searchBackwardThroughGraph) {
        // terminal drivers
        if (isTerminal(x)) {
            OccRef driver = getTerminalDriver(x);
            driver = isInverted(x) ? notOf(driver) : driver;
            getAllConnections(driver, connectedNets, connectedRefs,
                searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                searchThroughEquivNets, searchThroughEquivRefs, true);
        }
    }

    // --- connected forward through graph (if searchForwardThroughGraph)
    if (searchForwardThroughGraph) {
        // terminals in fanout
        list<OccRef> fanoutList;
        getFanout(x, fanoutList);
        while(!fanoutList.empty()) {
            OccRef fanout(fanoutList.front());
            fanoutList.pop_front();
            if(isTerminal(fanout)) {
                fanout = isInverted(x) ? notOf(fanout) : fanout;
                fanout = isInverted(getTerminalDriver(fanout)) ? notOf(fanout) : fanout;
                getAllConnections(fanout, connectedNets, connectedRefs,
                    searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                    searchThroughEquivNets, searchThroughEquivRefs, true);
            }
        }
    }

    // --- equivalent nodes (if searchThroughEquivRefs)
    if (searchThroughEquivRefs) {
        list<OccRef> equivList;
        getEquivalents(x, equivList);
        while(!equivList.empty()) {
            OccRef equiv(equivList.front());
            equivList.pop_front();
            getAllConnections(equiv, connectedNets, connectedRefs,
                searchForwardThroughGraph, searchBackwardThroughGraph, searchThroughHierarchy, 
                searchThroughEquivNets, searchThroughEquivRefs, true);
        }
    }
    
    // -- exclude self
    if (!includeSelf) {
        connectedRefs.erase(x);
    }
}


// *****************************************************************************
// getTerminalDriver()
//
//
// *****************************************************************************    
OccRef
OccGraph::getTerminalDriver(OccRef terminal,
                            bool searchHierarchy) {
    assert(isTerminal(terminal));

    oagAi::Ref result = getGraph(terminal)->getTerminalDriver(terminal.ref);
    if (!oagAi::Graph::isNull(result)) {
        return OccRef(result, terminal.occurrence);    
    }
    
    if (searchHierarchy) {
        QUIT_ON_ERROR
    }
    
    return OccRef();
}  


// *****************************************************************************
// print()
//
//
// *****************************************************************************
void                
OccRef::print(bool lineFeed) {

    oa::oaString occPathString;
    if (!occurrence) {
        occPathString = "(null)";
    } else if (occurrence->getOccInst()) {
        occurrence->getOccInst()->getPathName(oa::oaVerilogNS(), occPathString);
    } else {
        occPathString = "(top)";
    }

    if (OccGraph::getNodeType(*this) == oagAi::Node::AND) {
        cout << "AND " << occPathString << "." << ref << " :\t"
                << OccGraph::getAndLeft(*this).ref << ", " << OccGraph::getAndLeft(*this).ref;
    } else if (OccGraph::getNodeType(*this) == oagAi::Node::SEQUENTIAL) {
        cout    << "SEQ " << occPathString << "." << ref << " :\t"
                << OccGraph::getNextState(*this).ref;
    } else if (OccGraph::getNodeType(*this) == oagAi::Node::CONSTANT0) {
        cout    << "ZRO " << occPathString << "." << ref << " :\t";
    } else if (OccGraph::getNodeType(*this) == oagAi::Node::TERMINAL) {
        cout    << "TRM " << occPathString << "." << ref << " :\t"
                << OccGraph::getTerminalDriver(*this).ref;
    } else if (OccGraph::getNodeType(*this) == oagAi::Node::NONE) {
        cout    << "NUL " << occPathString << "." << ref << " :\t";
    }

    if (OccGraph::isInverted(*this)) {
        cout << " (inverted)";
    }
    
    if (lineFeed) {
        cout << endl;
    }
}


// *****************************************************************************
// printName()
//
//
// *****************************************************************************
void                
OccRef::printName(bool lineFeed) {

    oa::oaString occPathString;
    if (!occurrence) {
        occPathString = "(null)";
    } else if (occurrence->getOccInst()) {
        occurrence->getOccInst()->getPathName(oa::oaVerilogNS(), occPathString);
    } else {
        occPathString = "(top)";
    }

    cout << occPathString << "." << ref;
    
    if (lineFeed) {
        cout << endl;
    }
}


}

---