oagFpgaMapper.cpp

Go to the documentation of this file.

#include "oagFpgaMapperUtils.h"
#include "oagFpgaMapper.h"
#include "oagFpga.h"
#include "oagFpgaAiModGraph.h"
#include "oagFpgaSimMod.h"
//#include "oagFpgaSimOcc.h"
#include "oagFpgaManager.h"
#include "oagFpgaDebug.h"
#include <values.h>

using namespace oagFpga;

namespace oagMapper {

// *****************************************************************************
// FpgaMapper()
//
// *****************************************************************************
FpgaMapper::FpgaMapper(int cutsPerNode) {

    // set the maximum number of cuts generated per node
    this->cutsPerNode = cutsPerNode;

    gateCount = seqCount = 0;
    //useAlternateViews = false;

#ifdef CELL_MAPPING
    // create table for library gate cut functions
    addTrivialGates();
#endif

    // there must be enough bits in the table entry to store cut function
    assert((1<<MAX_CUT_SIZE) <= TableEntry::MAX_WORDS*TableEntry::BITS_PER_WORD);

    // prepare simulation vectors
    initializeSimulation();
}

#ifdef CELL_MAPPING

// *****************************************************************************
// useAlternateView()
//
// *****************************************************************************
void
FpgaMapper::useAlternateView(const oa::oaScalarName &viewName) {
  useAlternateViews = true;
  alternateViewName = viewName;
}


// *****************************************************************************
// addTrivialGates()
//
//
// *****************************************************************************
void
FpgaMapper::addTrivialGates() {

    // for each cut width
    for(int i=0; i<=MAX_CUT_SIZE; i++) {

        // add constant zero entry
        TableEntry constantEntry;
        constantEntry.cell = NULL;
        bzero(constantEntry.func, sizeof(int)*constantEntry.MAX_WORDS);
        constantEntry.N_input = 0;
        constantEntry.P = 0;
        constantEntry.directFlag = 0;
        constantEntry.constantFlag = 1;
        tables[i].push_back(constantEntry);

        // add constant one entry
        for(int bit=0; bit<(1<<i); bit++) {
            constantEntry.setBit(bit, true);
        }
        tables[i].push_back(constantEntry);

        // add all direct connections
        // YH: 06/26/07, don't understand what is direct connections...
        for(int j=0; j<i; j++) {
            TableEntry wireEntry;
            wireEntry.cell = NULL;
            bzero(wireEntry.func, sizeof(int)*wireEntry.MAX_WORDS);
            wireEntry.directInput = j;
            wireEntry.P = 0;
            wireEntry.directFlag = 1;
            wireEntry.constantFlag = 0;
            for(int v=0; v<(1<<i); v++) {
                wireEntry.setBit(v, (v >> j) & 0x1);
            }
            tables[i].push_back(wireEntry);
        }
    }
}

// *****************************************************************************
// addLibraryGate()
//
// *****************************************************************************
void
FpgaMapper::addLibraryGate(oa::oaDesign* design) {
  assert(design);

  oa::oaModule *module = design->getTopModule();
  assert(module);
  Manager *manager = Manager::get(design);
  if (!manager) {
    std::cout << "WARNING: Ignoring library cell.  "
              << "Either it is structural or is missing a functional description." << std::endl;
    return;
  }

#if defined(DEBUG)
  oa::oaString modString;
  module->getName(oa::oaVerilogNS(), modString);
  DEBUG_PRINTLN(modString);
#endif

  // find all input and output terminals
  std::vector<oa::oaModTerm*> inputTerms;
  std::vector<oa::oaModTerm*> outputTerms;
  oa::oaModTerm *term;
  oa::oaIter<oa::oaModTerm> termIter(module->getTerms(oacTermIterSingleBit));
  while((term = termIter.getNext())) {
    if (term->getTermType() == oa::oacInputTermType) {
      inputTerms.push_back(term);
    } else if (term->getTermType() == oa::oacOutputTermType) {
      outputTerms.push_back(term);
    }
  }

  // if this gate has zero or multiple outputs, ignore
  if (outputTerms.size() != 1) {
    std::cout << "WARNING: Ignoring library cell.  "
              << "Multiple outputs are currently unsupported." << std::endl;
    return;
  }
  // if this gate has zero inputs, ignore
  if (inputTerms.size() == 0) return;

  // find the AI nodes of the inputs and outputs
  oa::oaModBitNet *outputNet = oagFpga::toBitNet(outputTerms[0]->getNet());
  assert(outputNet);
  AiModRef outputNode = AiModGraph::getNetToAiConnection(outputNet);
  assert(!AiModGraph::isNull(outputNode));

  int len = inputTerms.size();
  vector<oagFpga::AiModRef> inputNodes(len);
  for(int i=0; i<len; i++) {
    oa::oaModBitNet *net = oagFpga::toBitNet(inputTerms[i]->getNet());
    inputNodes[i] = AiModGraph::getNetToAiConnection(net);
    assert(!AiModGraph::isNull(inputNodes[i]));
  }
  
  // check that there is enough room for the full truth table
  if (len > MAX_CUT_SIZE) {
    std::cout << "WARNING: Ignoring library cell.  "
              << "Too many inputs for the size of the truth tables." << std::endl;
    return;
  }
  assert(TableEntry::MAX_WORDS >= (1 << len)/TableEntry::BITS_PER_WORD);

  // find an alternate view, if specified
  oa::oaDesign *implementDesign = NULL;
  if (useAlternateViews) {
    // an alternate view was specified...
    oa::oaScalarName libName, viewName, cellName;
    design->getLibName(libName);
    design->getCellName(cellName);
    implementDesign = oa::oaDesign::find(libName, cellName, alternateViewName);
    // try opening from disk
    if (!implementDesign) {
      try {
        implementDesign = oa::oaDesign::open(libName, cellName, alternateViewName, 'r');
        assert(implementDesign);
      } catch (oa::oaException &e) {}
    }
    if (!implementDesign) {
      // couldn't open alternate view!
      oa::oaString viewString, cellString;
      alternateViewName.get(viewString);
      cellName.get(cellString);
      std::cerr << "ERROR: Could not find alternate view " << viewString 
                << " for cell " << cellString << endl;
      QUIT_ON_ERROR;
    }
  } else {
    implementDesign = design;
  }

  libraryCells.push_back(design);

  // N_input...
  for(unsigned char N_input=0; N_input<(1<<len); N_input++) {
    TableEntry t;
    t.cell = design;
    t.implementCell = implementDesign;
    bzero(t.func, sizeof(int)*t.MAX_WORDS);
    t.N_input = N_input;
    t.P = 0;         // input permutation unsupported
    t.directFlag = t.constantFlag = 0;
    simulate(design, t, outputNode, inputNodes);
    DEBUG_PRINTMORE(" ");
    tables[len].push_back(t);
    if (len <= 1) break; // don't bother with inverting 1-input gates
  }

  DEBUG_PRINTMORE("\n");
}

#endif // #ifdef CELL_MAPPING

// *****************************************************************************
// initializeSimulation()
//
//
// *****************************************************************************
void
FpgaMapper::initializeSimulation() {
  bzero(exhaustiveInputVectors, sizeof(unsigned int)*(MAX_CUT_SIZE)*TableEntry::MAX_WORDS);
  for(int v=0; v<(1<<MAX_CUT_SIZE); v++) {
    assert(v/TableEntry::BITS_PER_WORD < TableEntry::MAX_WORDS);
    for(int i=0; i<MAX_CUT_SIZE; i++) {
      exhaustiveInputVectors[i][v/TableEntry::BITS_PER_WORD] |= ((v >> i) & 0x1) << (v%TableEntry::BITS_PER_WORD);
    }
  }
}



// *****************************************************************************
// simulate()
//
//
// *****************************************************************************
void
FpgaMapper::simulate(oa::oaDesign *design, 
                TableEntry & outResult, oagFpga::AiModRef & out, 
                const vector<oagFpga::AiModRef> cut) {
  assert(design);

  const int cutWidth = cut.size();

  // Note: because this is such a performance critical component of the mapper,
  // the logic cone between a cut and a mapping point is computed using a direct
  // call to the oagAi class instead of the AiModGraph.  this avoids some slight
  // overhead in converting the oagAi::Refs to AiModRefs

  // gather full cone
  static vector<oagAi::Ref> cone;
  cone.clear();
  static vector<oagAi::Ref> coneRoots;
  coneRoots.clear();
  coneRoots.reserve(cutWidth);
  for(int i=0; i<cutWidth; i++)
    coneRoots.push_back(cut[i].ref);
  Manager::get(design)->getAiGraph()->getFaninCone(out.ref, coneRoots, cone, false);
  // add back vertex
  cone.push_back(out.ref);
  
  // create simulation engine
  static SimMod sim(design);

  // repeat with as many words as necessary for the full truth table
  int bits = (1 << cutWidth);
  unsigned int word = 0;
  while(bits > 0) {
    assert(word < TableEntry::MAX_WORDS);
    for(int i=0; i<cutWidth; i++) {
      if ((outResult.N_input >> i) & 0x1) {
        sim.setVector(cut[i], ~exhaustiveInputVectors[i][word]);
      } else {
        sim.setVector(cut[i], exhaustiveInputVectors[i][word]);
      }
    }
    // simulate every node in the cone
    for(vector<oagAi::Ref>::iterator it = cone.begin(); it!=cone.end(); it++) {
      sim.runOne(AiModRef(*it, out.module));
    }
    sim.getVector(out, outResult.func[word]);
    bits -= TableEntry::BITS_PER_WORD;
    word++;
  }

  // if the last result was a partial word, mask invalid bits
  if (bits < 0) {
    unsigned int mask = (0x1 << (bits + TableEntry::BITS_PER_WORD))-1;
    outResult.func[word-1] &= mask;
  }

#if defined(DEBUG)
  // print out the binary result
  for(unsigned int b=0; b<TableEntry::BITS_PER_WORD*TableEntry::MAX_WORDS; b++)
    cout << (outResult.getBit(b) ? "1" : "0");
#endif
}

// *****************************************************************************
// setAreaCosts()
//
// *****************************************************************************
void
FpgaMapper::setAreaCosts() {

#ifdef CELL_MAPPING

    // iterate through all table entries
    for(int i=0; i<=MAX_CUT_SIZE; i++) {
        for(unsigned int j=0; j<tables[i].size(); j++) {
            TableEntry *choice = &(tables[i][j]);

            // is a trivial mapping?
            if (choice->directFlag || choice->constantFlag) {
                choice->cost = 0.0;
                continue;
            }
            assert(choice->implementCell);

            // has a top block?
            oa::oaBlock *topBlock;
            if ((topBlock = choice->implementCell->getTopBlock())) {
                // has a bounding box?
                oa::oaBox box;
                topBlock->getBBox(box);
                choice->cost = box.getWidth()*box.getHeight();
                if (choice->cost > 0) continue;

                // count input terms
                oa::oaTerm *term;
                oa::oaIter<oa::oaTerm> termIter = topBlock->getTerms(oacTermIterSingleBit);
                int numInputs = 0;
                while((term = termIter.getNext())) {
                    if (term->getTermType() == oa::oacInputTermType) {
                        numInputs++;
                    }
                }
                choice->cost = numInputs;
                continue;
            }

            // has a top module?
            oa::oaModule *topModule;
            if ((topModule = choice->implementCell->getTopModule())) {
                // count input terms
                oa::oaModTerm *term;
                oa::oaIter<oa::oaModTerm> termIter = topModule->getTerms(oacTermIterSingleBit);
                int numInputs = 0;
                while((term = termIter.getNext())) {
                    if (term->getTermType() == oa::oacInputTermType) {
                        numInputs++;
                    }
                }
                choice->cost = numInputs;
                continue;
            }

            cerr << "ERROR: Library cell has neither top block nor top module" << endl;
            QUIT_ON_ERROR;
        }
    }
#else // #ifdef CELL_MAPPING

    this->mapUtils.lutArea = 1.0;
    this->mapUtils.seqArea = 1.0;

#endif // #ifdef CELL_MAPPING
}



// *****************************************************************************
// setDelayCosts()
//
// *****************************************************************************
void
FpgaMapper::setDelayCosts() {

#ifdef CELL_MAPPING

    // iterate through all table entries
    for(int i=0; i<=MAX_CUT_SIZE; i++) {
        for(unsigned int j=0; j<tables[i].size(); j++) {
            TableEntry *choice = &(tables[i][j]);

            // is a trivial mapping?
            if (choice->directFlag || choice->constantFlag) {
                choice->cost = 0.0;
                continue;
            }

            choice->cost = 1.0;
        }
    }
#else // #ifdef CELL_MAPPING

    this->mapUtils.lutDelay = 1.0;
    this->mapUtils.seqDelay = 0.0;

#endif // #ifdef CELL_MAPPING
}


// *****************************************************************************
// getCumulativeAreaCost()
//
// *****************************************************************************
double
FpgaMapper::getCumulativeAreaCost(AiModGraph::Cut *cut, TableEntry *choice) {
    assert(cut);
    assert(choice);

    // 1. cost of choice
    double cost = choice->cost;
    // 2. cost of inputs
    int i=0;
    for(AiModGraph::Cut::iterator it = cut->begin(); it!= cut->end(); it++) {
        if ((choice->N_input >> i) & 0x1) {
            // inverted
            assert(cost_n.find(*it) != cost_n.end());
            cost += cost_n[*it];
        } else {
            // non-inverted
            assert(cost_p.find(*it) != cost_p.end());
            cost += cost_p[*it];
        }
        i++;
    }
    return cost;
}


// *****************************************************************************
// getCumulativeDelayCost()
//
// *****************************************************************************
double
FpgaMapper::getCumulativeDelayCost(AiModGraph::Cut *cut, TableEntry *choice) {
    assert(cut);
    assert(choice);

    // 1. cost of inputs
    double cost = 0.0;
    int i=0;
    for(AiModGraph::Cut::iterator it = cut->begin(); it!= cut->end(); it++) {
        if ((choice->N_input >> i) & 0x1) {
            // inverted
            assert(cost_n.find(*it) != cost_n.end());
            cost >?= cost_n[*it];
        } else {
            // non-inverted
            assert(cost_p.find(*it) != cost_p.end());
            cost >?= cost_p[*it];
        }
        i++;
    }
  return cost + choice->cost;
}


// *****************************************************************************
// techmapArea()
//
// *****************************************************************************
void
FpgaMapper::techmapArea(oa::oaModule *target) {
    assert(target);

    cout << "Mapping for area..." << endl;

#ifdef CELL_MAPPING
    // has a set of library cells been supplied?
    if (libraryCells.empty()) {
      cerr << "ERROR: Empty combinational library.  Aborting." << endl;
      return;
    }
#endif // #ifdef CELL_MAPPING

    Manager *currentManager = Manager::get(target->getDesign());
    if (currentManager->isStructural()) {
        // the design is already entirely structural
        cerr << "ERROR: Target is already structural or is missing functional "
             << "description.  Aborting." << endl;
        return;
    }

    // initialize
    AiModGraph::clearKfeasibleCuts(target);
    cut_p.clear(); cut_n.clear();
    choice_p.clear(); choice_n.clear();
    cost_p.clear(); cost_n.clear();
    totalArea = totalDelay = 0;

    // check for combinational cycles
    if (AiModGraph::hasCombinationalCycle(target)) {
      cerr << "ERROR: Target graph has a combinational cycle" << endl;
      QUIT_ON_ERROR;
    }

    // set cost of all mapping choices to area
    setAreaCosts();

#ifdef CELL_MAPPING

    // identify not (and corresponding table entry)
    if (!mapUtils.notGate) {
      mapUtils.identifyNot(libraryCells);
    }
    if (!mapUtils.notGate) {
      cerr << "ERROR : Could not identify inverter in cell library" << endl;
      QUIT_ON_ERROR;
    }
    mapUtils.identifyNotTerminals();
    notEntry = NULL;
    for(unsigned int i = 0; i < tables[1].size(); i++) {
      if (tables[1][i].cell == mapUtils.notGate) {
        notEntry = &(tables[1][i]);
        break;
      }
    }
    assert(notEntry);

    // identify seq gate
    if (!mapUtils.seqGate) {
      cerr << "ERROR : Could not sequential gate in cell library" << endl;
      QUIT_ON_ERROR;
    }    
    mapUtils.identifySeqTerminalsByName();
#else

    // setup some frequently used technology entries

    // add not entry
    bzero(notEntry.func, sizeof(int)*notEntry.MAX_WORDS);
    notEntry.setBit(0, true);
    notEntry.cost = 0.;
    // add constant zero entry
    bzero(constantZeroEntry.func, sizeof(int)*constantZeroEntry.MAX_WORDS);
    constantZeroEntry.cost = 0.;

#endif // #ifdef CELL_MAPPING

    // strip reset nets
    mapUtils.identifyControls(target);
    mapUtils.removeAsyncResetsFromLogic(target);

    // handle constant nodes and nets
    AiModRef constantZero = AiModGraph::constantZero(target);
    oa::oaModNet *constantNet = oa::oaModNet::find(target, 
                                                   oa::oaScalarName(oa::oaNativeNS(), "tie0"));    
    if (constantNet) {
      AiModGraph::setTerminalDriver(AiModGraph::getNetToAiConnection(toBitNet(constantNet)),
                                  constantZero);
    }
    constantNet = oa::oaModNet::find(target, 
                                     oa::oaScalarName(oa::oaNativeNS(), "tie1"));
    if (constantNet) {
      AiModGraph::setTerminalDriver(AiModGraph::getNetToAiConnection(toBitNet(constantNet)),
                                  AiModGraph::constantOne(target));
    }

    // collect the points that must be mapped
    //    1. primary outputs
    //    2. next state inputs of sequential nodes
    list<AiModRef> outputsToMap, seqNodes;
    AiModGraph::getOutputs(target, outputsToMap);
    AiModGraph::getLocalStates(target, seqNodes);
    for(list<AiModRef>::iterator it = seqNodes.begin();
        it != seqNodes.end(); it++) {
      if (!AiModGraph::isNull(AiModGraph::getNextState(*it))) {
        outputsToMap.push_back(AiModGraph::getNextState(*it));
      }
    }
    // collect all fan-ins of these points
    vector<AiModRef> nodesToMap;
    AiModGraph::getTransitiveFanin(outputsToMap, nodesToMap, true);
    for(list<AiModRef>::iterator it = outputsToMap.begin();
        it != outputsToMap.end(); it++) {
      nodesToMap.push_back(*it);
    }

    // --- PHASE 1 : collect best choice for each node

    cout << "\tnum. nodes to map = " << nodesToMap.size() << endl;
    cout << "\t(i) collecting best choice for each node" << endl;
    cout.flush();

    int m = 0;
    static_cast<void>(m);

    // map each point
    for(vector<AiModRef>::iterator it = nodesToMap.begin();
        it != nodesToMap.end(); it++) {
      AiModRef mapPoint = AiModGraph::getNonInverted(*it);
      AiModGraph::Cut selfCut;
      selfCut.insert(selfCut.begin(), mapPoint);

      // progress indicator (one dot = 1000 points mapped)
#if !defined(DEBUG)
      m++;
      if (m%1000 == 0) { cout << "."; cout.flush(); }
#else
      DEBUG_PRINT("Mapping node ");
      mapPoint.print();
#endif

      if (mapPoint == constantZero) {
          cost_p[mapPoint] = 0;
          cost_n[mapPoint] = 0;
      } else if (AiModGraph::isTerminal(mapPoint) && 
          AiModGraph::isNull(AiModGraph::getTerminalDriver(mapPoint)) ||
          AiModGraph::isSequential(mapPoint)) {
              cost_p[mapPoint] = 0;
              cut_n[mapPoint] = selfCut;
              choice_n[mapPoint] = &notEntry;
              cost_n[mapPoint] = notEntry.cost;
      } else {
          // explore all possible k-feasible cuts
          // AiModGraph::clearKfeasibleCuts(target);
          AiModGraph::CutSet cuts = AiModGraph::enumerateKfeasibleCuts(
              mapPoint, MAX_CUT_SIZE, cutsPerNode, -1, true);

          // choose best "p" and "n" cuts and choices
          double minCost_p = DBL_MAX,
              minCost_n = DBL_MAX;
          AiModGraph::Cut *bestCut_p = NULL,
              *bestCut_n = NULL;
          TableEntry *bestChoice_p = NULL,
              *bestChoice_n = NULL;

          for(list<AiModGraph::Cut>::iterator cut_it = cuts.begin(); cut_it != cuts.end(); cut_it++) {
              AiModGraph::Cut *currentCut = &(*cut_it);
              assert(currentCut);
              int cutWidth = currentCut->size();
              assert(cutWidth <= MAX_CUT_SIZE);

              // ignore self-cut
              if (cutWidth == 1 && *(currentCut->begin()) == mapPoint) continue;

              // construct cut array
              DEBUG_PRINT("\tcut {");
              int p = 0;
              vector<AiModRef> cutArray(cutWidth);
              for(set<AiModRef>::iterator cut_it = currentCut->begin(); 
                        cut_it != currentCut->end(); cut_it++) {
                  DEBUG_PRINTMORE(cut_it->ref << ", ");
                  assert(p < cutWidth);
                  cutArray[p++] = *cut_it;
              }
              DEBUG_PRINTMORE("} ");

              // compute cut function
              TableEntry cutFunction;
              simulate(target->getDesign(), cutFunction, mapPoint, cutArray);
              // compute complement of cut function
              TableEntry complementFunction;
              memcpy(&complementFunction, &cutFunction, sizeof(TableEntry));
              for(int bit=0; bit<(1<<cutWidth); bit++) {
                  complementFunction.setBit(bit, !complementFunction.getBit(bit));
              }
#ifdef CELL_MAPPING
              // match cut function
              for(vector<TableEntry>::iterator lib_it = tables[cutWidth].begin(); 
                  lib_it != tables[cutWidth].end(); lib_it++) {
                      TableEntry *currentChoice = &(*lib_it);
                      assert(currentChoice);

                      // with non-inverted function...
                      if (currentChoice->match(cutFunction)) {
                          // print name
                          if (currentChoice->cell) {
                              oa::oaScalarName gateName;
                              currentChoice->cell->getCellName(gateName);
                              oa::oaString gateString;
                              gateName.get(gateString);
                              DEBUG_PRINTMORE(" " << gateString);
                          } else if (currentChoice->directFlag) {
                              DEBUG_PRINTMORE(" WIRE");
                          } else if (currentChoice->constantFlag) {
                              DEBUG_PRINTMORE(" CONST");
                          }
                          // keep best match
                          if (getCumulativeAreaCost(currentCut, currentChoice) < minCost_p) {
                              minCost_p = getCumulativeAreaCost(currentCut, currentChoice);
                              bestChoice_p = currentChoice;
                              bestCut_p = currentCut;
                          }
                      }

                      // with inverted function...
                      if (currentChoice->match(complementFunction)) {
                          // print name
                          if (currentChoice->cell) {
                              oa::oaScalarName gateName;
                              currentChoice->cell->getCellName(gateName);
                              oa::oaString gateString;
                              gateName.get(gateString);
                              DEBUG_PRINTMORE(" !" << gateString);
                          } else if (currentChoice->directFlag) {
                              DEBUG_PRINTMORE(" !WIRE");
                          } else if (currentChoice->constantFlag) {
                              DEBUG_PRINTMORE(" !CONST");
                          }
                          // keep best match
                          if (getCumulativeAreaCost(currentCut, currentChoice) < minCost_n) {
                              minCost_n = getCumulativeAreaCost(currentCut, currentChoice);
                              bestChoice_n = currentChoice;
                              bestCut_n = currentCut;
                          }
                      }
              }
#else

              // only one choice for each cut when LUT map is assumed

              // with non-inverted function...
              TableEntry *currentChoice = new TableEntry(cutFunction);
              minCost_p = getCumulativeAreaCost(currentCut, currentChoice);
              bestChoice_p = currentChoice;
              bestCut_p = currentCut;
              // with inverted function...
              currentChoice = new TableEntry(complementFunction);
              minCost_n = getCumulativeAreaCost(currentCut, currentChoice);
              bestChoice_n = currentChoice;
              bestCut_n = currentCut;

#endif // #ifdef CELL_MAPPING

              DEBUG_PRINTMORE(endl);
          }

          // could we not find a mapping?
          if (!bestChoice_p && !bestChoice_n) {
              cerr << endl << "ERROR: Could not find a mapping for ";
              mapPoint.print();
              cerr << "       This shouldn't happen.  Perhaps the cut count/depth is too small?" << endl;
              QUIT_ON_ERROR;
          }

          // lastly, check self-cuts (i.e. just using an inverter)
#ifdef CELL_MAPPING
          if (minCost_p + notEntry->cost < minCost_n) {
              minCost_n = minCost_p + notEntry->cost;
              bestChoice_n = notEntry;
              bestCut_n = &selfCut;
              DEBUG_PRINTLN("\tself-cut {} !p");
          }
          if (minCost_n + notEntry->cost < minCost_p) {
              minCost_p = minCost_n + notEntry->cost;
              bestChoice_p = notEntry;
              bestCut_p = &selfCut;
              DEBUG_PRINTLN("\tself-cut {} !n");
          }
#else
          assert(minCost_p == minCost_n);

#endif // #ifdef CELL_MAPPING
          DEBUG_PRINTLN("\tp-cost = " << minCost_p << " n-cost = " << minCost_n);
          cost_p[mapPoint] = minCost_p;
          cost_n[mapPoint] = minCost_n;
          assert(bestChoice_p);
          choice_p[mapPoint] = bestChoice_p;
          assert(bestChoice_n);
          choice_n[mapPoint] = bestChoice_n;
          assert(bestCut_p);
          cut_p[mapPoint] = *bestCut_p;
          assert(bestCut_n);
          cut_n[mapPoint] = *bestCut_n;
      }
    }

    // --- PHASE 2 : implement choices

    cout << endl << "\t(ii) implementing best global choices" << endl;

    implementAll(target);

    // PHASE 3 : clean up

    cout << "\t(iii) cleaning up" << endl;
    AiModGraph::clearKfeasibleCuts(target);

    // make module structural
    oa::oaModNet *net;
    oa::oaIter<oa::oaModNet> netIter(target->getNets(oacNetIterSingleBit));
    while((net = netIter.getNext())) {
      AiModRef termNode = AiModGraph::getNetToAiConnection(toBitNet(net));
      if (AiModGraph::isTerminal(termNode)) {
        AiModGraph::detach(termNode);
      }
    }
    // delete manager if this is the only module
    if (target->getDesign()->getModules().getCount() == 1) {
      Manager::destroy(target->getDesign());
    }

    cout << "\tarea cost = " << totalArea << endl;
}


// *****************************************************************************
// implementAll()
//
//
// *****************************************************************************
void
FpgaMapper::implementAll(oa::oaModule *target) {
    assert(target);

    list<AiModRef> toBeImplemented;

#ifdef DEBUG
    cerr << "Begin to make all bus nets and terms explicit" << endl;
#endif

    // make all bus nets and terms explicit
    oa::oaModNet *net;
    oa::oaIter<oa::oaModNet> explicitNetIter(target->getNets(oacNetIterNotImplicit));
    while((net = explicitNetIter.getNext())) {
      assert(net);
      if(!net->isImplicit() && net->getNumBits() > 1) {
        net->scalarize();
      }
    }
    oa::oaModTerm *term;
    oa::oaIter<oa::oaModTerm> explicitTermIter(target->getTerms(oacTermIterNotImplicit));
    while((term = explicitTermIter.getNext())) {
      assert(term);
      if(!term->isImplicit() && term->getNumBits() > 1) {
        term->scalarize();
      }
    }

#ifdef DEBUG
    cerr << "Begin to map all existing wires" << endl;
#endif

    // map all existings wires
    oa::oaIter<oa::oaModNet> netIter(target->getNets(oacNetIterSingleBit));
    while((net = netIter.getNext())) {
      oa::oaModBitNet *bitNet = toBitNet(net);
      assert(bitNet);
      AiModRef ref = AiModGraph::getNetToAiConnection(bitNet);
      if (AiModGraph::isNull(ref)) continue;
      assert(AiModGraph::isTerminal(ref));
      if (!AiModGraph::isNull(AiModGraph::getTerminalDriver(ref))) continue;
      mapped[ref] = bitNet;
    }

#ifdef DEBUG
    cerr << "Begin to pre-map sequential nodes" << endl;
#endif

    // pre-map sequential nodes
    map<AiModRef, oa::oaModInst*> seqInsts;
    list<AiModRef> outputsToMap, seqNodes;
    AiModGraph::getLocalStates(target, seqNodes);
    for(list<AiModRef>::iterator it = seqNodes.begin();
        it != seqNodes.end(); it++) {
      seqInsts[*it] = implementSeqNode(*it); 
    }

#ifdef DEBUG
    cerr << "Begin to map sequential nodes" << endl;
#endif

    // map sequential nodes
    for(list<AiModRef>::iterator it = seqNodes.begin();
        it != seqNodes.end(); it++) {
      AiModRef nextState = AiModGraph::getNextState(*it);
      if (!AiModGraph::isNull(nextState)) {
        oa::oaModBitNet *mapped_in = implementNode(nextState);
        assert(mapped_in);
        oa::oaModInstTerm::create(mapped_in, seqInsts[*it], mapUtils.seqInput);
      }
    }

#ifdef DEBUG
    cerr << "Begin to map primary outputs" << endl;
#endif

    // map primary outputs
    oa::oaIter<oa::oaModTerm> termIter(target->getTerms(oacTermIterSingleBit));
    while((term = termIter.getNext())) {
      oa::oaModBitNet *oldNet = toBitNet(term->getNet());
      assert(oldNet);

      AiModRef ref = AiModGraph::getNetToAiConnection(oldNet);
      assert(!AiModGraph::isNull(ref));
      oa::oaModBitNet *newNet = implementNode(ref);
      assert(newNet);

      term->moveToNet(newNet);
    }
}


// *****************************************************************************
// implementSeqNode()
//
// *****************************************************************************
oa::oaModInst *
FpgaMapper::implementSeqNode(oagFpga::AiModRef ref) {
  oa::oaModule *currentModule = ref.module;
  assert(currentModule);

#ifdef DEBUG
  cerr << "begin to create new sequential gate" << endl;
#endif
  // create new sequential gate
  oa::oaModScalarInst *inst = oa::oaModScalarInst::create(currentModule, mapUtils.seqGate);
#ifdef DEBUG
  cerr << "end to create new sequential gate" << endl;
#endif

  // create output net
  oa::oaModBitNet *mapped_out = oa::oaModScalarNet::create(currentModule);
  assert(!mapped_out->isImplicit());
  oa::oaModInstTerm::create(mapped_out, inst, mapUtils.seqOutput);
  mapped[ref] = mapped_out;
  
  // TODO: need to find some way to connect those asynchronous signals
#ifdef CELL_MAPPING
  // connect clocks, resets, etc.
  mapUtils.connectAllControls(ref, inst);
#endif

  return inst;
}


// *****************************************************************************
// implementNode()
//
// *****************************************************************************
oa::oaModBitNet *
FpgaMapper::implementNode(oagFpga::AiModRef ref) {

  // has this node already been mapped?
  if (mapped.find(ref) != mapped.end()) {
    return mapped[ref];
  }

  DEBUG_PRINTLN("Implementing node " << ref.ref);

  oa::oaModule *currentModule = ref.module;
  assert(currentModule);

  // is this a dangling node?
  if (AiModGraph::isTerminal(ref) && !AiModGraph::isInverted(ref) && 
      AiModGraph::isNull(AiModGraph::getTerminalDriver(ref)) ||
      AiModGraph::isAnd(ref) && AiModGraph::isNull(AiModGraph::getAndRight(ref)) &&
      AiModGraph::isNull(AiModGraph::getAndLeft(ref))) {
    // default action: connect to constant zero
    oa::oaModNet *constantNet = oa::oaModNet::find(currentModule, 
                                                   oa::oaScalarName(oa::oaNativeNS(), "tie0"));
    assert(constantNet);
    mapped[ref] = toBitNet(constantNet);
    DEBUG_PRINTLN("\tfloating... tying to zero");
    return toBitNet(constantNet);
  }

  // is this a constant node?
  if (ref == AiModGraph::constantZero(currentModule)) {
    oa::oaModNet *constantNet = oa::oaModNet::find(currentModule, 
                                                   oa::oaScalarName(oa::oaNativeNS(), "tie0"));
    assert(constantNet);
    mapped[ref] = toBitNet(constantNet);
    DEBUG_PRINTLN("\tconstant zero");
    return toBitNet(constantNet);
  } else if (ref == AiModGraph::constantOne(currentModule)) {
    oa::oaModNet *constantNet = oa::oaModNet::find(currentModule, 
                                                   oa::oaScalarName(oa::oaNativeNS(), "tie1"));
    assert(constantNet);
    mapped[ref] = toBitNet(constantNet);
    DEBUG_PRINTLN("\tconstant one");
    return toBitNet(constantNet);
  }

  // is this an inverted ref? return with "p" or "n" version of node
  TableEntry    *choice;
  AiModGraph::Cut *cut;
  if (AiModGraph::isInverted(ref)) {
    // "n" mapping
    choice = choice_n[AiModGraph::getNonInverted(ref)];
    cut = &(cut_n[AiModGraph::getNonInverted(ref)]);
    totalDelay >?= cost_n[AiModGraph::getNonInverted(ref)];
  } else {
    // "p" mapping
    choice = choice_p[AiModGraph::getNonInverted(ref)];
    cut = &(cut_p[AiModGraph::getNonInverted(ref)]);
    totalDelay >?= cost_p[AiModGraph::getNonInverted(ref)];
  }
  if (!choice || !cut) {
    ref.print();
    oa::oaModBitNet *net = AiModGraph::getNetToAiConnection(ref);
    oa::oaString n;
    net->getName(oa::oaVerilogNS(), n);
    cout << n << endl;
  }
  assert(choice);
  assert(cut);

#ifdef CELL_MAPPING
  // come back !! for the direct connect (06/29/07)
  // is this a trivial mapping?
  if (choice->directFlag) {
    // return the wire that is connected to the direct input
    int inputNum = choice->directInput;
    for(AiModGraph::Cut::iterator it = cut->begin(); it != cut->end(); it++) {
      if (!inputNum) {
        assert(*it != ref);
        DEBUG_PRINTLN("\twire");
        return implementNode(*it);
      }
      --inputNum;
    }
    assert(false);
  }
  if (choice->constantFlag) {
    // return the constant 0 or 1 wire
    oa::oaModNet *constantNet;
    if (choice->func[0] & 0x1) {
      constantNet = oa::oaModNet::find(currentModule, oa::oaScalarName(oa::oaNativeNS(), "tie1"));
    } else {
      constantNet = oa::oaModNet::find(currentModule, oa::oaScalarName(oa::oaNativeNS(), "tie0"));
    }
    assert(constantNet);
    mapped[ref] = toBitNet(constantNet);
    DEBUG_PRINTLN("\tconstant");
    return toBitNet(constantNet);
  }
#endif // #ifdef CELL_MAPPING

  // create logic gate
#ifdef CELL_MAPPING
  assert(choice->implementCell);
  oa::oaModScalarInst *inst = oa::oaModScalarInst::create(currentModule, choice->implementCell);
    #if defined(DEBUG)
      oa::oaString gateString;
      choice->implementCell->getCellName(oa::oaVerilogNS(), gateString);
      DEBUG_PRINTLN("\tgate " << gateString);
    #endif
#else
  // at this point, the choice of the node must be a LUT (seq node has been mapped)
  cerr << "begin to create a modual instant" << endl;

#ifdef YU_TEST
  //oagFpga::YuTest(YuTestCurLib, YuTestCurView, currentModule);
  oa::oaString lutCellNameString, lutModuleNameString;
  mapUtils.getLut()->getCellName(oa::oaNativeNS(),lutCellNameString);
  mapUtils.getLut()->getTopModule()->getName(oa::oaNativeNS(), lutModuleNameString);
  cerr << "the LUT design's name is " << lutCellNameString << endl;
  cerr << "the LUT module's name is " << lutModuleNameString << endl;
#endif // #ifdef YU_TEST

  oa::oaModScalarInst *inst = oa::oaModScalarInst::create(currentModule, mapUtils.getLut());
  cerr << "end to create a modual instant" << endl;
#endif // #ifdef CELL_MAPPING
  totalArea += choice->cost;

  // map inputs
  int num = 0;
  oa::oaModTerm *term, *outputTerm = NULL;
  oa::oaIter<oa::oaModTerm> termIter(mapUtils.getLut()->getTopModule()->getTerms(oacTermIterSingleBit));
  for(AiModGraph::Cut::iterator it = cut->begin(); it != cut->end(); it++, num++) {
    AiModRef cutRef = *it;
    assert(!AiModGraph::isNull(cutRef));
    assert(!AiModGraph::isInverted(cutRef));

    // is this input inverted in the mapping?
    if ((choice->N_input >> num) & 0x1) {
#ifndef CELL_MAPPING
        assert(0); // none of inputs is inverted, should never reach here ...
#endif // #ifndef CELL_MAPPING
      cutRef = AiModGraph::notOf(cutRef);
    }
    // was an inverter used to map _p <=> _n?
    if (choice == &notEntry && cutRef == ref) {
#ifndef CELL_MAPPING
        assert(0); // only LUT is used for map, should never reach here ...
#endif // #ifndef CELL_MAPPING
      cutRef = AiModGraph::notOf(cutRef);
    }
    assert(cutRef != ref);

    // get corresponding instTerm
    while((term = termIter.getNext())) {
      if (term->getTermType() == oa::oacInputTermType) {
        break;
      } else if (term->getTermType() == oa::oacOutputTermType) {
        assert(!outputTerm); // can only handle gates with one output
        outputTerm = term;
      }
    }
    assert(term);

    oa::oaModBitNet *mapped_in = implementNode(cutRef);
    assert(mapped_in);
    assert(!mapped_in->isImplicit());
    oa::oaModInstTerm::create(mapped_in, inst, term);
  }

  // find output term (if not already found)
  while(!outputTerm && (term = termIter.getNext())) {
    if (term->getTermType() == oa::oacOutputTermType) {
      outputTerm = term;
    }
  }
  assert(outputTerm);
  
  // create output net
  oa::oaModBitNet *mapped_out = oa::oaModScalarNet::create(currentModule);
  assert(!mapped_out->isImplicit());
  oa::oaModInstTerm::create(mapped_out, inst, outputTerm);

  mapped[ref] = mapped_out;
  return mapped_out;
}


// *****************************************************************************
// techmapDelay()
//
// *****************************************************************************
void
FpgaMapper::techmapDelay(oa::oaModule *target) {

assert(target);

    cout << "Mapping for delay..." << endl;

#ifdef CELL_MAPPING
    // has a set of library cells been supplied?
    if (libraryCells.empty()) {
      cerr << "ERROR: Empty combinational library.  Aborting." << endl;
      return;
    }
#endif // #ifdef CELL_MAPPING

    Manager *currentManager = Manager::get(target->getDesign());
    if (currentManager->isStructural()) {
        // the design is already entirely structural
        cerr << "ERROR: Target is already structural or is missing functional "
             << "description.  Aborting." << endl;
        return;
    }

    // initialize
    AiModGraph::clearKfeasibleCuts(target);
    cut_p.clear(); cut_n.clear();
    choice_p.clear(); choice_n.clear();
    cost_p.clear(); cost_n.clear();
    totalArea = totalDelay = 0;

    // check for combinational cycles
    if (AiModGraph::hasCombinationalCycle(target)) {
      cerr << "ERROR: Target graph has a combinational cycle" << endl;
      QUIT_ON_ERROR;
    }

    // set cost of all mapping choices to delay
    setDelayCosts();

#ifdef CELL_MAPPING

    // identify not (and corresponding table entry)
    if (!mapUtils.notGate) {
      mapUtils.identifyNot(libraryCells);
    }
    if (!mapUtils.notGate) {
      cerr << "ERROR : Could not identify inverter in cell library" << endl;
      QUIT_ON_ERROR;
    }
    mapUtils.identifyNotTerminals();
    notEntry = NULL;
    for(unsigned int i = 0; i < tables[1].size(); i++) {
      if (tables[1][i].cell == mapUtils.notGate) {
        notEntry = &(tables[1][i]);
        break;
      }
    }
    assert(notEntry);

    // identify seq gate
    if (!mapUtils.seqGate) {
      cerr << "ERROR : Could not sequential gate in cell library" << endl;
      QUIT_ON_ERROR;
    }    
    mapUtils.identifySeqTerminalsByName();
#else

    // setup some frequently used technology entries

    // add not entry
    bzero(notEntry.func, sizeof(int)*notEntry.MAX_WORDS);
    notEntry.setBit(0, true);
    notEntry.cost = 0.;
    // add constant zero entry
    bzero(constantZeroEntry.func, sizeof(int)*constantZeroEntry.MAX_WORDS);
    constantZeroEntry.cost = 0.;

#endif // #ifdef CELL_MAPPING

    // strip reset nets
    mapUtils.identifyControls(target);
    mapUtils.removeAsyncResetsFromLogic(target);

    // handle constant nodes and nets
    AiModRef constantZero = AiModGraph::constantZero(target);
    oa::oaModNet *constantNet = oa::oaModNet::find(target, 
                                                   oa::oaScalarName(oa::oaNativeNS(), "tie0"));    
    if (constantNet) {
      AiModGraph::setTerminalDriver(AiModGraph::getNetToAiConnection(toBitNet(constantNet)),
                                  constantZero);
    }
    constantNet = oa::oaModNet::find(target, 
                                     oa::oaScalarName(oa::oaNativeNS(), "tie1"));
    if (constantNet) {
      AiModGraph::setTerminalDriver(AiModGraph::getNetToAiConnection(toBitNet(constantNet)),
                                  AiModGraph::constantOne(target));
    }

    // collect the points that must be mapped
    //    1. primary outputs
    //    2. next state inputs of sequential nodes
    list<AiModRef> outputsToMap, seqNodes;
    AiModGraph::getOutputs(target, outputsToMap);
    AiModGraph::getLocalStates(target, seqNodes);
    for(list<AiModRef>::iterator it = seqNodes.begin();
        it != seqNodes.end(); it++) {
      if (!AiModGraph::isNull(AiModGraph::getNextState(*it))) {
        outputsToMap.push_back(AiModGraph::getNextState(*it));
      }
    }
    // collect all fan-ins of these points
    vector<AiModRef> nodesToMap;
    AiModGraph::getTransitiveFanin(outputsToMap, nodesToMap, true);
    for(list<AiModRef>::iterator it = outputsToMap.begin();
        it != outputsToMap.end(); it++) {
      nodesToMap.push_back(*it);
    }

    // --- PHASE 1 : collect best choice for each node

    cout << "\tnum. nodes to map = " << nodesToMap.size() << endl;
    cout << "\t(i) collecting best choice for each node";
    cout.flush();

    int m = 0;
    static_cast<void>(m);

    // map each point
    for(vector<AiModRef>::iterator it = nodesToMap.begin();
        it != nodesToMap.end(); it++) {
      AiModRef mapPoint = AiModGraph::getNonInverted(*it);
      AiModGraph::Cut selfCut;
      selfCut.insert(selfCut.begin(), mapPoint);

      // progress indicator (one dot = 1000 points mapped)
#if !defined(DEBUG)
      m++;
      if (m%1000 == 0) { cout << "."; cout.flush(); }
#else
      DEBUG_PRINT("Mapping node ");
      mapPoint.print();
#endif

      if (mapPoint == constantZero) {
          cost_p[mapPoint] = 0;
          cost_n[mapPoint] = 0;
      } else if (AiModGraph::isTerminal(mapPoint) && 
          AiModGraph::isNull(AiModGraph::getTerminalDriver(mapPoint)) ||
          AiModGraph::isSequential(mapPoint)) {
              cost_p[mapPoint] = 0;
              cut_n[mapPoint] = selfCut;
              choice_n[mapPoint] = &notEntry;
              cost_n[mapPoint] = notEntry.cost;
      } else {
          // explore all possible k-feasible cuts
          // AiModGraph::clearKfeasibleCuts(target);
          AiModGraph::CutSet cuts = AiModGraph::enumerateKfeasibleCuts(
              mapPoint, MAX_CUT_SIZE, cutsPerNode, -1, true);

          // choose best "p" and "n" cuts and choices
          double minCost_p = DBL_MAX,
              minCost_n = DBL_MAX;
          AiModGraph::Cut *bestCut_p = NULL,
              *bestCut_n = NULL;
          TableEntry *bestChoice_p = NULL,
              *bestChoice_n = NULL;

          for(list<AiModGraph::Cut>::iterator cut_it = cuts.begin(); cut_it != cuts.end(); cut_it++) {
              AiModGraph::Cut *currentCut = &(*cut_it);
              assert(currentCut);
              int cutWidth = currentCut->size();
              assert(cutWidth <= MAX_CUT_SIZE);

              // ignore self-cut
              if (cutWidth == 1 && *(currentCut->begin()) == mapPoint) continue;

              // construct cut array
              DEBUG_PRINT("\tcut {");
              int p = 0;
              vector<AiModRef> cutArray(cutWidth);
              for(set<AiModRef>::iterator cut_it = currentCut->begin(); 
                        cut_it != currentCut->end(); cut_it++) {
                  DEBUG_PRINTMORE(cut_it->ref << ", ");
                  assert(p < cutWidth);
                  cutArray[p++] = *cut_it;
              }
              DEBUG_PRINTMORE("} ");

              // compute cut function
              TableEntry cutFunction;
              simulate(target->getDesign(), cutFunction, mapPoint, cutArray);
              // compute complement of cut function
              TableEntry complementFunction;
              memcpy(&complementFunction, &cutFunction, sizeof(TableEntry));
              for(int bit=0; bit<(1<<cutWidth); bit++) {
                  complementFunction.setBit(bit, !complementFunction.getBit(bit));
              }
#ifdef CELL_MAPPING
              // match cut function
              for(vector<TableEntry>::iterator lib_it = tables[cutWidth].begin(); 
                  lib_it != tables[cutWidth].end(); lib_it++) {
                      TableEntry *currentChoice = &(*lib_it);
                      assert(currentChoice);

                      // with non-inverted function...
                      if (currentChoice->match(cutFunction)) {
                          // print name
                          if (currentChoice->cell) {
                              oa::oaScalarName gateName;
                              currentChoice->cell->getCellName(gateName);
                              oa::oaString gateString;
                              gateName.get(gateString);
                              DEBUG_PRINTMORE(" " << gateString);
                          } else if (currentChoice->directFlag) {
                              DEBUG_PRINTMORE(" WIRE");
                          } else if (currentChoice->constantFlag) {
                              DEBUG_PRINTMORE(" CONST");
                          }
                          // keep best match
                          if (getCumulativeDelayCost(currentCut, currentChoice) < minCost_p) {
                              minCost_p = getCumulativeDelayCost(currentCut, currentChoice);
                              bestChoice_p = currentChoice;
                              bestCut_p = currentCut;
                          }
                      }

                      // with inverted function...
                      if (currentChoice->match(complementFunction)) {
                          // print name
                          if (currentChoice->cell) {
                              oa::oaScalarName gateName;
                              currentChoice->cell->getCellName(gateName);
                              oa::oaString gateString;
                              gateName.get(gateString);
                              DEBUG_PRINTMORE(" !" << gateString);
                          } else if (currentChoice->directFlag) {
                              DEBUG_PRINTMORE(" !WIRE");
                          } else if (currentChoice->constantFlag) {
                              DEBUG_PRINTMORE(" !CONST");
                          }
                          // keep best match
                          if (getCumulativeDelayCost(currentCut, currentChoice) < minCost_n) {
                              minCost_n = getCumulativeDelayCost(currentCut, currentChoice);
                              bestChoice_n = currentChoice;
                              bestCut_n = currentCut;
                          }
                      }
              }
#else

              // only one choice for each cut when LUT map is assumed

              // with non-inverted function...
              TableEntry *currentChoice = new TableEntry(cutFunction);
              minCost_p = getCumulativeDelayCost(currentCut, currentChoice);
              bestChoice_p = currentChoice;
              bestCut_p = currentCut;
              // with inverted function...
              currentChoice = new TableEntry(complementFunction);
              minCost_n = getCumulativeDelayCost(currentCut, currentChoice);
              bestChoice_n = currentChoice;
              bestCut_n = currentCut;

#endif // #ifdef CELL_MAPPING

              DEBUG_PRINTMORE(endl);
          }

          // could we not find a mapping?
          if (!bestChoice_p && !bestChoice_n) {
              cerr << endl << "ERROR: Could not find a mapping for ";
              mapPoint.print();
              cerr << "       This shouldn't happen.  Perhaps the cut count/depth is too small?" << endl;
              QUIT_ON_ERROR;
          }

          // lastly, check self-cuts (i.e. just using an inverter)
#ifdef CELL_MAPPING
          if (minCost_p + notEntry->cost < minCost_n) {
              minCost_n = minCost_p + notEntry->cost;
              bestChoice_n = notEntry;
              bestCut_n = &selfCut;
              DEBUG_PRINTLN("\tself-cut {} !p");
          }
          if (minCost_n + notEntry->cost < minCost_p) {
              minCost_p = minCost_n + notEntry->cost;
              bestChoice_p = notEntry;
              bestCut_p = &selfCut;
              DEBUG_PRINTLN("\tself-cut {} !n");
          }
#else
          assert(minCost_p == minCost_n);

#endif // #ifdef CELL_MAPPING
          DEBUG_PRINTLN("\tp-cost = " << minCost_p << " n-cost = " << minCost_n);
          cost_p[mapPoint] = minCost_p;
          cost_n[mapPoint] = minCost_n;
          assert(bestChoice_p);
          choice_p[mapPoint] = bestChoice_p;
          assert(bestChoice_n);
          choice_n[mapPoint] = bestChoice_n;
          assert(bestCut_p);
          cut_p[mapPoint] = *bestCut_p;
          assert(bestCut_n);
          cut_n[mapPoint] = *bestCut_n;
      }
    }

    // --- PHASE 2 : implement choices

    cout << endl << "\t(ii) implementing best global choices" << endl;
    implementAll(target);

    // PHASE 3 : clean up

    cout << "\t(iii) cleaning up" << endl;
    AiModGraph::clearKfeasibleCuts(target);

    // make module structural
    oa::oaModNet *net;
    oa::oaIter<oa::oaModNet> netIter(target->getNets(oacNetIterSingleBit));
    while((net = netIter.getNext())) {
      AiModRef termNode = AiModGraph::getNetToAiConnection(toBitNet(net));
      if (AiModGraph::isTerminal(termNode)) {
        AiModGraph::detach(termNode);
      }
    }
    // delete manager if this is the only module
    if (target->getDesign()->getModules().getCount() == 1) {
      Manager::destroy(target->getDesign());
    }

    cout << "\tdelay cost = " << totalDelay << endl;
}


}

---