oagFpgaRtlGraph.cpp

Go to the documentation of this file.

#include "oagFpgaRtlGraph.h"
#include "oagFpgaDebug.h"

using namespace std;

namespace oagFpga {

// initialization of static member

const char* RtlNode::funcTypeName [] = {"NULL_FUNC", "TERMINAL", "CONTROL",
    "OPERATOR", "SEQ", "CONSTANT0", "CONSTANT1"};
const char* RtlNode::optTypeName [] = {
    "UNKNOWN", "PRIMARY", "BUNDLE", "BITWISE_AND", "BITWISE_NAND", "BITWISE_OR", "BITWISE_NOR",
    "BITWISE_XOR", "BITWISE_XNOR", "BITWISE_NOT", "LOGICAL_AND", "LOGICAL_NOT", "LOGICAL_OR",
    "REDUCTION_AND", "REDUCTION_OR", "REDUCTION_XOR", "REDUCTION_NAND", "REDUCTION_NOR",
    "REDUCTION_XNOR", "LESS_THAN", "LESS_THAN_EQUAL", "GREATER_THAN", "GREATER_THAN_EQUAL",
    "EQUAL", "NOTEQUAL", "IF_ELSE", "LEFT_SHIFT", "RIGHT_SHIFT", "ADD", "SUBTRACT", "MULTIPLY",
    "DIVIDE", "MODULO", "NEGATE"
};
const char* RtlNode::seqTypeName [] = {
    "DFF", "LATCH"
};

// *****************************************************************************
// unaryOpt()
//
// *****************************************************************************

BBRef
RtlGraph::unaryOpt(RtlNode::OptType ot, BBRef driver) {

    // create output node of this unary operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connection between new node and driver
    node->fanin.push_back(driver);
    getNode(driver)->fanout.push_back(node->self);

    // setup input ports
    node->optInfo->op1.push_back(driver);

    return node->self;
}

// *****************************************************************************
// binaryOpt()
//
// *****************************************************************************

BBRef
RtlGraph::binaryOpt(RtlNode::OptType ot, BBRef in1, BBRef in2) {

    // create output node of this binary operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connections
    node->fanin.push_back(in1);
    node->fanin.push_back(in2);
    getNode(in1)->fanout.push_back(node->self);
    getNode(in2)->fanout.push_back(node->self);

    // setup input ports
    node->optInfo->op1.push_back(in1);
    node->optInfo->op1.push_back(in2);

    return node->self;
}

// *****************************************************************************
// unaryBusOpt()
//
// *****************************************************************************

BBRef
RtlGraph::unaryBusOpt(RtlNode::OptType ot, vector<BBRef>& ins) {
    
    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connections
    for(vector<BBRef>::iterator bbRefIter = ins.begin(); bbRefIter != ins.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        
        // setup input ports
        node->optInfo->op1.push_back(ref);
    }

    return node->self;
}

// *****************************************************************************
// binaryBusOpt()
//
// *****************************************************************************

BBRef
RtlGraph::binaryBusOpt(RtlNode::OptType ot, vector<BBRef>& in1, 
        vector<BBRef>& in2) {

    assert(in1.size() == in2.size());
    
    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connections
    for(vector<BBRef>::iterator bbRefIter = in1.begin(); bbRefIter != in1.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        // setup input ports
        node->optInfo->op1.push_back(ref);
    }
    for(vector<BBRef>::iterator bbRefIter = in2.begin(); bbRefIter != in2.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        // setup input ports
        node->optInfo->op2.push_back(ref);
    }

    return node->self;
}

// *****************************************************************************
// binaryBusInputOutputOpt()
//
// *****************************************************************************

void
RtlGraph::binaryBusInputOutputOpt(RtlNode::OptType ot, 
        int numOutBits, vector<BBRef>& in1, 
        vector<BBRef>& in2, vector<BBRef>& out) {

    assert(in1.size() == in2.size());
    // YH: TODO: need to check back!!!
    // the output of a ripper adder should be one-bit wider than the inputs, but
    // currently i assume the number of input/output bits are equal
    //assert(numOutBits > 1);
    
    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    node->numOutputBits = numOutBits;

    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connections
    for(vector<BBRef>::iterator bbRefIter = in1.begin(); bbRefIter != in1.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        // setup input ports
        node->optInfo->op1.push_back(ref);
    }
    for(vector<BBRef>::iterator bbRefIter = in2.begin(); bbRefIter != in2.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        // setup input ports
        node->optInfo->op2.push_back(ref);
    }

    // setup output bits according numOutBits
    out.push_back(node->self);
    for(int i=1;i<numOutBits;i++){
        bbNodes.push_back(node);
        out.push_back(node->self+i);
    }

}

// *****************************************************************************
// unaryBusInputOutputOpt()
//
// *****************************************************************************

void
RtlGraph::unaryBusInputOutputOpt(RtlNode::OptType ot, int numOutBits, 
        vector<BBRef>& in1, vector<BBRef>& out) {

    assert(numOutBits > 1);
    
    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::OPERATOR;
    node->optType = ot;
    node->numOutputBits = numOutBits;

    addNode(node);
    node->optInfo = new RtlNode::RtlOptNodeInfo();

    // build connections
    for(vector<BBRef>::iterator bbRefIter = in1.begin(); bbRefIter != in1.end();
            ++ bbRefIter) {
        BBRef ref = *bbRefIter;
        node->fanin.push_back(ref);
        getNode(ref)->fanout.push_back(node->self);
        // setup input ports
        node->optInfo->op1.push_back(ref);
    }

    // setup output bits according numOutBits
    out.push_back(node->self);
    for(int i=1;i<numOutBits;i++){
        bbNodes.push_back(node);
        out.push_back(node->self+i);
    }
}


// *****************************************************************************
// bitSeq()
//
//
// *****************************************************************************

BBRef
RtlGraph::bitSeq(RtlNode::SeqType st, BBRef D, BBRef clock, 
        BBRef aLoad, BBRef aData) {

    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::SEQ;
    node->seqType = st;
    addNode(node);

    // build connections
    if(st == RtlNode::LATCH){
        node->seqInfo = new RtlNode::RtlSeqNodeInfo(D, clock, getNull(),
                getNull());
        node->fanin.push_back(D);
        getNode(D)->fanout.push_back(node->self);
        node->fanin.push_back(clock);
        getNode(clock)->fanout.push_back(node->self);
    }else{
        assert(st == RtlNode::DFF);
        node->seqInfo = new RtlNode::RtlSeqNodeInfo(D, clock, aLoad, aData);
        node->fanin.push_back(D);
        node->fanin.push_back(clock);
        node->fanin.push_back(aLoad);
        node->fanin.push_back(aData);
        getNode(D)->fanout.push_back(node->self);
        getNode(clock)->fanout.push_back(node->self);
        getNode(aLoad)->fanout.push_back(node->self);
        getNode(aData)->fanout.push_back(node->self);
    }

    return node->self;
    
}

BBRef
RtlGraph::bitSeq(RtlNode::SeqType st, BBRef D) {

    return bitSeq(st, D, getNull(), getNull(), getNull());
}

// *****************************************************************************
// YH: a general mux could be much more complicated
// a general CONTROL element for following Verilog statement:
// 
// CASE A: out <= a;
// CASE B: out <= b;
// 
// should be
//
//           +---+
//      A--->|   |          +-----+
//           | = |------->--|     |
//       +-->|   |          | AND |-->-+
//       |   +---+    a-->--|     |    |     +----+
// sel-->+                  +-----+    +--->-|    |
//       |   +---+                           | OR |-->
//       +-->|   |          +-----+    +--->-|    |
//           | = |------->--|     |    |     +----+
//      B--->|   |          | AND |-->-+
//           +---+    b-->--|     |
//                          +-----+
//
// However, if A and B are constant (e.g., integers), this statement should
// be inferred as a MUX with sel properly encoded.
// *****************************************************************************


// *****************************************************************************
// bitMux()
//
//
// *****************************************************************************

BBRef
RtlGraph::bitMux(BBRef in1, BBRef in2, BBRef sel) {

    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::CONTROL;
    addNode(node);
 
    node->fanin.push_back(in1);
    node->fanin.push_back(in2);
    node->fanin.push_back(sel);
    getNode(in1)->fanout.push_back(node->self);
    getNode(in2)->fanout.push_back(node->self);
    getNode(sel)->fanout.push_back(node->self);

    // setup data inputs and selection bits
    node->muxInfo = new RtlNode::RtlMuxNodeInfo();
    node->muxInfo->in.push_back(in1);
    node->muxInfo->in.push_back(in2);
    node->muxInfo->sel.push_back(sel);

    return node->self;
}

// *****************************************************************************
// busMux()
//
//
// *****************************************************************************

BBRef
RtlGraph::busMux(vector<BBRef>& in, vector<BBRef>& sel) {

    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::CONTROL;
    addNode(node);

    vector<BBRef>::iterator bbRefIter;

    // setup inputs of this blackbox
    for(bbRefIter = in.begin(); bbRefIter != in.end(); ++ bbRefIter) {
        node->fanin.push_back(*bbRefIter);
        getNode(*bbRefIter)->fanout.push_back(node->self);
    }
    for(bbRefIter = sel.begin(); bbRefIter != sel.end(); ++ bbRefIter) {
        node->fanin.push_back(*bbRefIter);
        getNode(*bbRefIter)->fanout.push_back(node->self);
    }
 
    // setup data inputs and selection bits
    node->muxInfo = new RtlNode::RtlMuxNodeInfo();
    back_insert_iterator<list<BBRef> > biiIn(node->muxInfo->in);
    copy(in.begin(), in.end(), biiIn);
    back_insert_iterator<list<BBRef> > biiSel(node->muxInfo->in);
    copy(in.begin(), in.end(), biiSel);
    copy(sel.begin(), sel.end(), biiSel);

    return node->self;
}

// *****************************************************************************
// busMux()
//
//
// *****************************************************************************

void
RtlGraph::busMux(vector<BBRef>& in1, vector<BBRef>& in2, vector<BBRef>& sel,
        vector<BBRef>& outputs) {

    // i haven't seen the usefulness of this routine...
    QUIT_ON_INTERNAL_ERROR;

    assert(in1.size() == in2.size());

    // create output node of this multiple operator
    RtlNode* node = newNode();
    node->funcType = RtlNode::CONTROL;
    node->numOutputBits = in1.size();

    addNode(node);
 
    vector<BBRef>::iterator bbRefIter;

    // setup inputs of this blackbox
    for(bbRefIter = in1.begin(); bbRefIter != in1.end(); ++ bbRefIter) {
        node->fanin.push_back(*bbRefIter);
        getNode(*bbRefIter)->fanout.push_back(node->self);
    }
    for(bbRefIter = in2.begin(); bbRefIter != in2.end(); ++ bbRefIter) {
        node->fanin.push_back(*bbRefIter);
        getNode(*bbRefIter)->fanout.push_back(node->self);
    }
    for(bbRefIter = sel.begin(); bbRefIter != sel.end(); ++ bbRefIter) {
        node->fanin.push_back(*bbRefIter);
        getNode(*bbRefIter)->fanout.push_back(node->self);
    }

    // setup output bits
    for(size_t i=0;i<in1.size();i++){
        bbNodes.push_back(node);
        outputs.push_back(node->self+i);
    }

    // TODO: setup data inputs and selection bits
}

// *****************************************************************************
// addNode()
//
//
// *****************************************************************************
void 
RtlGraph::addNode(RtlNode* node) {

    node->self = bbNodes.size();
    bbNodes.push_back(node);
    
    //TODO: check missing??
}

RtlNode* RtlGraph::newNode() {
    RtlNode* node = new RtlNode();
    dataBBNodes.push_back(node);
    node->self = BBRef(-1);
    node->funcType = RtlNode::NULL_FUNC;
    return node;
}

BBRef
RtlGraph::newTerminal(BBRef driver) {

    // create a new terminal node
    RtlNode *node = newNode();
    addNode(node);
    node->funcType = RtlNode::TERMINAL;
    node->fanin.push_back(driver);

    // add this node to driver's fanout 
    getNode(driver)->fanout.push_back(node->self);

    DEBUG_PRINTLN("new TERM = " << node->self << "  \tdriver=" << driver);
    return node->self;
}

// *****************************************************************************
// removeFromFanout()
//
//
// *****************************************************************************
void
RtlGraph::removeFromFanout(BBRef x, BBRef fanout) {   
    if (isNull(x) || isNull(fanout))
        return;

    RtlNode *node = getNode(x);

    list<BBRef>::iterator it = node->fanout.begin();
    while(it != node->fanout.end()) {
        BBRef current = *it;
        if (current == fanout) {
            node->fanout.erase(it);
            return;
        }
        ++it;
    }

    // node not found in fanout list?
    cerr << "ERROR: Node " << fanout << " not found in fanout of " << x << endl;
    QUIT_ON_INTERNAL_ERROR;
}

// *****************************************************************************
// setTerminalDriver()
//
//
// *****************************************************************************
void
RtlGraph::setTerminalDriver(BBRef terminal, BBRef driver) { 
    RtlNode *node = getNode(terminal);
    assert(node);
    assert(node->funcType == RtlNode::TERMINAL);

    /*
    // mark dirty; existing graph structure may be modified
    dirtyMarker++;
    */

    // decrement old fan-in
    removeFromFanout(node->fanin.front(), terminal);
    // update terminal driver
    assert(node->fanin.size() == 1);
    node->fanin.front() = driver;
    // increment new fan-in
    getNode(driver)->fanout.push_back(terminal);
}

// *****************************************************************************
// print()
//
// *****************************************************************************

void
RtlGraph::print(ostream& os, RtlNode* node) {
    os << "BBNode " << node->self << ":" << RtlNode::funcTypeName[node->funcType];
    if(node->funcType == RtlNode::OPERATOR)
        os << "." << RtlNode::optTypeName[node->optType];
    else if(node->funcType == RtlNode::SEQ)
        os << "." << RtlNode::seqTypeName[node->seqType];
}

// *****************************************************************************
// print()
//
// *****************************************************************************

void
RtlGraph::print(ostream& os) {
    os << "========================================================" << endl;
    os << "Begin of RtlGraph:" << endl;

    // print all unique BB nodes
    for(vector<RtlNode*>::iterator bbIter = dataBBNodes.begin(); bbIter !=
            dataBBNodes.end(); ++ bbIter){
        RtlNode* node = *bbIter;
        print(os, node);
        os << endl;
    }

    // print all connections
    for(vector<RtlNode*>::iterator bbIter = bbNodes.begin(); bbIter !=
            bbNodes.end(); ++ bbIter){
        RtlNode* node = *bbIter;
        // output all fanouts
        os << "N" << node->self << ": " << endl;
        os << "Fanouts: ";
        for(list<BBRef>::iterator listIter = node->fanout.begin(); listIter !=
                node->fanout.end(); ++ listIter){
            os << getNode(*listIter)->self << ",";
        }
        os << endl;
        // output all fanins
        os << "Fanins: ";
        for(list<BBRef>::iterator listIter = node->fanin.begin(); listIter !=
                node->fanin.end(); ++ listIter){
            os << getNode(*listIter)->self << ",";
        }
        os << endl;
    }

    os << "End of RtlGraph:" << endl;
    os << "========================================================" << endl;
    os.flush();
}

// *****************************************************************************
// *****************************************************************************

// *****************************************************************************
// newTraversalID()
//
// *****************************************************************************
unsigned int
RtlGraph::newTraversalID() {

    // clear all travsersalIDs (if and only if currentTraversalID is out of
    // unsigned int bound (0xffffffff)
    if (++currentTraversalID == 0) {
        for(vector<RtlNode*>::iterator nodeIter = dataBBNodes.begin(); nodeIter
                != dataBBNodes.end(); ++ nodeIter){
           (*nodeIter)->traversalID = 0;
        }
        currentTraversalID = 1;
    }

    return currentTraversalID;
}

// *****************************************************************************
// hasCombinationalCycle()
//
//
// *****************************************************************************
bool
RtlGraph::hasCombinationalCycle() {
  unsigned int startingTravID = newTraversalID();

  for(vector<RtlNode*>::iterator nodeIter = dataBBNodes.begin(); nodeIter !=
          dataBBNodes.end(); ++ nodeIter){
      newTraversalID();
      RtlNode* node = *nodeIter;
      BBRef ref = node->self;
      if (hasCombinationalCycle_recursive(ref, startingTravID)) {
          DEBUG_PRINTLN("Combinational cycle on node " << ref);
          return true;
      }
  }

  return false;
}


// *****************************************************************************
// hasCombinationalCycle()
//
//
// *****************************************************************************
bool
RtlGraph::hasCombinationalCycle_recursive(BBRef x, unsigned int startingTravID) {
    // is this a null reference
    if (isNull(x)) {
        return false;
    }
    RtlNode *node = getNode(x);
    // is this node non-combinational?
    if (node->funcType == RtlNode::SEQ 
            || node->funcType == RtlNode::CONSTANT0
            || node->funcType == RtlNode::CONSTANT1) {
        return false;
    }
    // does this form a cycle?
    if (node->traversalID == currentTraversalID) {
        return true;
    }
    // has this already been proved to be cycle-free?
    if (node->traversalID >= startingTravID) {
        return false;
    }
    node->traversalID = currentTraversalID;
    // otherwise, continue backward
    if (node->funcType == RtlNode::CONTROL || node->funcType == RtlNode::OPERATOR) {
        bool result = false;
        for(list<BBRef>::iterator refIter = node->fanin.begin(); refIter !=
                node->fanin.end(); ++ refIter)
            result = result || hasCombinationalCycle_recursive(*refIter, startingTravID); 
        node->traversalID = startingTravID;
        return result;
    }
    else if (node->funcType == RtlNode::TERMINAL) {
        bool result = hasCombinationalCycle_recursive(getTerminalDriver(x), startingTravID);
        node->traversalID = startingTravID;
        return result;
    }

    QUIT_ON_INTERNAL_ERROR;
    return false;
}


// *****************************************************************************
// getTransitiveFanin()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin(BBRef x, vector<BBRef> &transitiveFanin, 
                          bool includeRoots, bool crossSequential) {
  newTraversalID();
  getTransitiveFanin_recursive(x, transitiveFanin, includeRoots, crossSequential);
  // remove initial node
  transitiveFanin.pop_back(); 
}


// *****************************************************************************
// getTransitiveFanin()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin(list<BBRef> x, vector<BBRef> &transitiveFanin, 
                          bool includeRoots, bool crossSequential) {

  // transitiveFanin = { transitiveFanin, fanin(x_1), fanin(x_2) ... fanin(x_n) }
  
  newTraversalID();
  for(list<BBRef>::iterator xIter = x.begin(); xIter != x.end(); xIter++) {
    getTransitiveFanin_recursive(*xIter, transitiveFanin, 
                                 includeRoots, crossSequential);
    // remove initial nodes
    transitiveFanin.pop_back();
  }
}


// *****************************************************************************
// getTransitiveFanin_recursive()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin_recursive(BBRef x, vector<BBRef> &transitiveFanin,
                          bool includeRoots, bool crossSequential) {
    markVisited(x);
      
    vector<BBRef>   fanin;

    RtlNode *node = getNode(x);

    switch(node->funcType) {

    case RtlNode::CONTROL:
    case RtlNode::OPERATOR: {
        for(list<BBRef>::iterator refIter = node->fanin.begin(); refIter !=
                node->fanin.end(); ++ refIter)
            fanin.push_back(*refIter);
        break;
    }
    case RtlNode::TERMINAL:
      fanin.push_back(getTerminalDriver(x));
      break;
    case RtlNode::SEQ:
      /*
      // the transitive fanins of "nextState" input of a sequential node will be
      // returned
      fanin.push_back(getNextState(x));
      */
      // All fanins including Data-input, clock and asynchronous signals will be
      // returned
      for(list<BBRef>::iterator refIter = node->fanin.begin(); refIter !=
              node->fanin.end(); ++ refIter)
          fanin.push_back(*refIter);
      break;
    case RtlNode::CONSTANT0:
    case RtlNode::CONSTANT1:
      // do nothing for constant0/1
      return;
    default:
      QUIT_ON_INTERNAL_ERROR;
    }

    for(vector<BBRef>::iterator refIter = fanin.begin(); refIter != fanin.end();
            ++ refIter){
        BBRef currentFanin = *refIter;
        if (!isNull(currentFanin) && !isVisited(currentFanin)) {
            if (isTerminal(currentFanin) &&
                    isNull(getTerminalDriver(currentFanin)) 
                    || currentFanin == constantZero()
                    || currentFanin == constantOne()
                    || isSequential(currentFanin) && !crossSequential) {
                // only include if includeRoots is true
                if (includeRoots) {
                    markVisited(currentFanin);
                    transitiveFanin.push_back(currentFanin);
                }
            } else {
                getTransitiveFanin_recursive(currentFanin, transitiveFanin, 
                        includeRoots, crossSequential);
            }
        }
    }

    transitiveFanin.push_back(x);
}


// *****************************************************************************
// getTransitiveFanin()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin(BBRef x, list<BBRef> &transitiveFanin,
                          bool includeRoots, bool crossSequential) {
  newTraversalID();
  getTransitiveFanin_recursive(x, transitiveFanin, includeRoots, crossSequential);
  // remove initial node
  transitiveFanin.pop_back(); 
}


// *****************************************************************************
// getTransitiveFanin()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin(list<BBRef> x, list<BBRef> &transitiveFanin,
                          bool includeRoots, bool crossSequential) {

  // transitiveFanin = { transitiveFanin, fanin(x_1), fanin(x_2) ... fanin(x_n-1), fanin(x_n) }

  newTraversalID();
  for(list<BBRef>::iterator xIter = x.begin(); xIter!=x.end(); xIter++) {
    getTransitiveFanin_recursive(*xIter, transitiveFanin, 
                                 includeRoots, crossSequential);
    // remove initial nodes
    transitiveFanin.pop_back();
  }
}

// *****************************************************************************
// getTransitiveFanin_recursive()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanin_recursive(BBRef x, list<BBRef> &transitiveFanin,
                          bool includeRoots, bool crossSequential) {
    markVisited(x);

    vector<BBRef>   fanin;

    RtlNode *node = getNode(x);

    switch(node->funcType) {
    case RtlNode::CONTROL:
    case RtlNode::OPERATOR:
        for(list<BBRef>::iterator refIter = node->fanin.begin(); refIter !=
                node->fanin.end(); ++ refIter)
            fanin.push_back(*refIter);
        break;
    case RtlNode::TERMINAL:
        fanin.push_back(getTerminalDriver(x));
        break;
    case RtlNode::SEQ:
        /*
        // the transitive fanins of "nextState" input of a sequential node will
        // be returned
        fanin.push_back(getNextState(x));
        */
        // All fanins including Data-input, clock and asynchronous signals will be
        // returned
        for(list<BBRef>::iterator refIter = node->fanin.begin(); refIter !=
                node->fanin.end(); ++ refIter)
            fanin.push_back(*refIter);
        break;
    case RtlNode::CONSTANT0:
    case RtlNode::CONSTANT1:
        // do nothing for constant 0/1
        return;
    default:
        QUIT_ON_INTERNAL_ERROR;
    }

    for(vector<BBRef>::iterator refIter = fanin.begin(); refIter != fanin.end();
            ++ refIter){
        BBRef currentFanin = *refIter;
        if (!isNull(currentFanin) && !isVisited(currentFanin)) {
            if (isTerminal(currentFanin) &&
                    isNull(getTerminalDriver(currentFanin))
                    || currentFanin == constantZero() 
                    || currentFanin == constantOne()
                    || isSequential(currentFanin) && !crossSequential)
            {
                // only include if includeRoots is true 
                if (includeRoots)
                {
                    markVisited(currentFanin);
                    transitiveFanin.push_back(currentFanin);
                }
            }
            else {
                getTransitiveFanin_recursive(currentFanin,
                        transitiveFanin, includeRoots, crossSequential);
            }
        }
    }

    transitiveFanin.push_back(x);
}

// *****************************************************************************
// getTransitiveFanout()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout(BBRef x, vector<BBRef> &transitiveFanout, 
                          bool includeRoots, bool crossSequential) {
  newTraversalID();
  // generate the reversed forward topological ordering of transitive fanout
  vector<BBRef> newReversedTransitiveFanout;
  getTransitiveFanout_recursive(x, newReversedTransitiveFanout, includeRoots, crossSequential);
  // remove initial node
  newReversedTransitiveFanout.pop_back(); 
  // append reversed result to original vector
  transitiveFanout.reserve(transitiveFanout.size()+newReversedTransitiveFanout.size());
  for(vector<BBRef>::reverse_iterator it = newReversedTransitiveFanout.rbegin();
      it != newReversedTransitiveFanout.rend(); it++) {
    transitiveFanout.push_back(*it);
  }
}


// *****************************************************************************
// getTransitiveFanout()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout(list<BBRef> x, vector<BBRef> &transitiveFanout,
                          bool includeRoots, bool crossSequential) {

  // transitiveFanout = { transitiveFanout, rev(fanout(x_n)) ... rev(fanout(2)), rev(fanout(1)) }

  newTraversalID();
  vector<BBRef> newReversedTransitiveFanout;
  for(list<BBRef>::iterator it = x.begin(); it != x.end(); it++) {
    // generate the reversed forward topological ordering of transitive fanout
    getTransitiveFanout_recursive(*it, newReversedTransitiveFanout,
                                  includeRoots, crossSequential);
    // remove initial node
    newReversedTransitiveFanout.pop_back(); 
  }
  // append reversed result to original vector
  transitiveFanout.reserve(transitiveFanout.size()+newReversedTransitiveFanout.size());
  for(vector<BBRef>::reverse_iterator it2 = newReversedTransitiveFanout.rbegin();
      it2 != newReversedTransitiveFanout.rend(); it2++) {
    transitiveFanout.push_back(*it2);
  }
}


// *****************************************************************************
// getTransitiveFanout_recursive()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout_recursive(BBRef x, vector<BBRef> &transitiveFanout, 
                          bool includeRoots, bool crossSequential) {
    markVisited(x);

    if (getNodeType(x) == RtlNode::TERMINAL && 
        hasFanout(x) && !includeRoots) {
      // only include if includeRoots is true
      return;
    }

    const list<BBRef> *immediateFanout = &getFanout(x);
    for(list<BBRef>::const_iterator it = immediateFanout->begin(); 
        it != immediateFanout->end(); ++it) {
      BBRef next = *it;

      // there shouldn't be fanout to a null or constant node
      assert(!isNull(next));
      assert(getNodeType(next) != RtlNode::CONSTANT0);
      assert(getNodeType(next) != RtlNode::CONSTANT1);

      // have we already explored this node?
      if (isVisited(next)) {
        continue;
      }
            
      if (getNodeType(next) == RtlNode::SEQ && !crossSequential) {
        // only include if includeRoots is true
        if (includeRoots) {
          markVisited(next);
          transitiveFanout.push_back(next);
        }
      } else {
        // continue traversal
        getTransitiveFanout_recursive(next, transitiveFanout, includeRoots);
      }
    }

    transitiveFanout.push_back(x);
}

// *****************************************************************************
// getTransitiveFanout()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout(list<BBRef> x, list<BBRef> &transitiveFanout,
                          bool includeRoots, bool crossSequential) {

  // transitiveFanout = { transitiveFanout, fanout(x_n) ... fanout(2), fanout(1) }

  newTraversalID();
  list<BBRef> allNewFanout;
  for(list<BBRef>::iterator it = x.begin(); it != x.end(); it++) {
    list<BBRef> oneNewFanout;
    getTransitiveFanout_recursive(*it, oneNewFanout, includeRoots, crossSequential);
    // remove initial node
    oneNewFanout.pop_front();
    allNewFanout.splice(allNewFanout.begin(), oneNewFanout);
  }
  transitiveFanout.splice(transitiveFanout.end(), allNewFanout);
}


// *****************************************************************************
// getTransitiveFanout()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout(BBRef x, list<BBRef> &transitiveFanout,
                          bool includeRoots, bool crossSequential) {
  newTraversalID();
  list<BBRef> newTransitiveFanout;
  getTransitiveFanout_recursive(x, newTransitiveFanout, 
                                includeRoots, crossSequential);
  // remove initial node
  newTransitiveFanout.pop_front(); 
  // append reversed result to original vector
  transitiveFanout.splice(transitiveFanout.end(), newTransitiveFanout);
}


// *****************************************************************************
// getTransitiveFanout_recursive()
//
//
// *****************************************************************************
void
RtlGraph::getTransitiveFanout_recursive(BBRef x, list<BBRef> &transitiveFanout, 
                                     bool includeRoots, bool crossSequential) {
    markVisited(x);

    // YH question: don't understand what's the case here??
    if (getNodeType(x) == RtlNode::TERMINAL && 
        hasFanout(x) && !includeRoots) {
      // only include if includeRoots is true
      return;
    }

    const list<BBRef> *immediateFanout = &getFanout(x);
    for(list<BBRef>::const_iterator it = immediateFanout->begin(); 
        it != immediateFanout->end(); ++it) {
      BBRef next = *it;

      // there shouldn't be fanout to a null or constant node
      assert(!isNull(next));
      assert(getNodeType(next) != RtlNode::CONSTANT0);
      assert(getNodeType(next) != RtlNode::CONSTANT1);

      // have we already explored this node?
      if (isVisited(next)) {
        continue;
      }
            
      if (getNodeType(next) == RtlNode::SEQ && !crossSequential) {
        // only include if includeRoots is true
        if (includeRoots) {
          markVisited(next);
          transitiveFanout.push_front(next);
        }
      } else {
        // continue traversal
        getTransitiveFanout_recursive(next, transitiveFanout, includeRoots);
      }
    }

    transitiveFanout.push_front(x);
}



}

---