src/part/partFine.c

Go to the documentation of this file.

#include "partInt.h"

static char rcsid[] UNUSED = "$Id: partFine.c,v 1.5 2005/04/30 04:00:38 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

#define PartVertexReadGeneric(vPtr)  ((PartVertexInfo_t *)(vPtr)->user_data)->generic
#define PartVertexReadGeneric1(vPtr)  ((PartVertexInfo_t *)(vPtr)->user_data)->generic1
#define BASIC_PARTITION_UNIT 15

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static  int             Part_IsFanoutInverter(Ntk_Node_t *node);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


void
PartPartitionFineGrain(
  Ntk_Network_t *network,
  graph_t       *partition,
  mdd_t         *careSet)
{
  Ntk_Node_t     *node;            /* Pointer to iterate over nodes */
  Mvf_Function_t *mddFunction;     /* Pointer to a MDD */
  mdd_manager    *manager;         /* Mdd manager in the partition */
  st_table       *tableOfLeaves;   /* To store the leaves of the graph */
  st_table       *mddIdToNodeName; /* For quick lookup of node's name */
  array_t        *arrayOfMvf;      /* To store the next state functions */
  array_t        *arrayOfRoots;    /* To store the roots of the graph */
  lsList         sinkList;         /* Vertices representing comb. outputs */
  lsGen          gen;              /* To iterate over lists */
  vertex_t       *toVertex;        /* Will hold the current function vertex */
  int            i;                /* Index for loops */
  long           mddId;            /* Will hold the mddId being processed */
  st_table       *mddSupport;      /* To store the support of the Mvf_Function */
  st_generator   *stGen;           /* To iterate over the MddIds of the support */
  vertex_t       *fromVertex;      /* Will hold the current vertex in the support */
  array_t        *singletonMvfArray;
  array_t        *singletonArrayOfRoots;
  array_t        *tmpArrayOfMvf;
  Mvf_Function_t *nodeMvf;
  lsList         sortedListOfNodes;     
  array_t        *sortedArrayOfPartitionNodes;
  array_t        *unsortedArrayOfPartitionNodes;
  st_table       *tableOfPartitionNodes;
  Ntk_Node_t     *fanin, *fanout;

  manager = PartPartitionReadMddManager(partition);
  
  /* Make the combinational input  nodes into leaves */
  tableOfLeaves = st_init_table(st_ptrcmp, st_ptrhash);
  mddIdToNodeName = st_init_table(st_numcmp, st_numhash);
  Ntk_NetworkForEachCombInput(network, gen, node) {
    if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID)
      Ord_NetworkAssignMddIdForNode(network, node);
    st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );
    st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
              Ntk_NodeReadName(node));
  }

  unsortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);  
  tableOfPartitionNodes = st_init_table(st_ptrcmp, st_ptrhash);
  /* Make the target node list for partition */
  Ntk_NetworkForEachNode(network, gen, node) {
    if(Ntk_NodeTestIsShadow(node))      continue;
    else if(Ntk_NodeTestIsCombInput(node))      continue;
    else if(Ntk_NodeTestIsCombOutput(node))     continue;
    else if(Ntk_NodeReadNumFanouts(node) == 1) { 
      fanout = Part_GetFanoutFreeLogic(node);
      if(Ntk_NodeTestIsCombOutput(fanout));
      else if(Ntk_NodeReadNumFanins(node) > 10);
      else if(Ntk_NodeReadNumFanins(fanout) == 1)       continue;
      else if(!Part_CheckLeafNodeCondition(node, tableOfPartitionNodes, 5, 10)) {
        if(Ntk_NodeReadNumFanins(node) == 1) {
           fanin = Part_GetFaninFreeLogic(node);
           if(!fanin)   continue;
           if(Ntk_NodeTestIsCombInput(fanin))   continue;
        }
        continue;
      }
    }
    array_insert_last(Ntk_Node_t *, unsortedArrayOfPartitionNodes, node);
    st_insert(tableOfPartitionNodes, (char *) node, (char *) (long) (-1));
  }

  /* create sorted array of partition nodes */
  sortedListOfNodes = Ntk_NetworkComputeTopologicalOrder(network, 
                               unsortedArrayOfPartitionNodes, tableOfLeaves);

  sortedArrayOfPartitionNodes = array_alloc(Ntk_Node_t *, 0);  
  lsForEachItem(sortedListOfNodes, gen, node){
    /* sortedListOfNodes includes many internal nodes, need to filter them out */
    if(st_is_member(tableOfPartitionNodes, (char *) node)){
      array_insert_last(Ntk_Node_t *, sortedArrayOfPartitionNodes, node);
      if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID) 
        Ord_NetworkAssignMddIdForNode(network, node);
    }   
  }
  array_free(unsortedArrayOfPartitionNodes);
  lsDestroy(sortedListOfNodes, (void (*)(lsGeneric))0);  
  st_free_table(tableOfPartitionNodes);
      

  tmpArrayOfMvf = array_alloc(Mvf_Function_t *, 0);
  for(i=0; i < array_n(sortedArrayOfPartitionNodes); i++){
    node = array_fetch(Ntk_Node_t *, sortedArrayOfPartitionNodes, i);
    singletonArrayOfRoots = array_alloc(Ntk_Node_t *, 0);
    array_insert_last(Ntk_Node_t *, singletonArrayOfRoots, node);
    singletonMvfArray = Ntm_NetworkBuildMvfs(network, singletonArrayOfRoots, 
                                             tableOfLeaves, careSet);
    nodeMvf = array_fetch(Mvf_Function_t *, singletonMvfArray, 0);
    array_insert_last(Mvf_Function_t *, tmpArrayOfMvf, nodeMvf);
    array_free(singletonMvfArray);
    array_free(singletonArrayOfRoots);
    
    if(Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID){
      Ord_NetworkAssignMddIdForNode(network, node);
    }
    st_insert(tableOfLeaves, (char *)node, (char *) (long) (-1) );    
    st_insert(mddIdToNodeName, (char *) (long)Ntk_NodeReadMddId(node), 
                Ntk_NodeReadName(node));

  }


  arrayOfRoots = array_alloc(Ntk_Node_t *, 0);
  Ntk_NetworkForEachCombOutput(network, gen, node) {
    array_insert_last(Ntk_Node_t *, arrayOfRoots, node);
  }
  arrayOfMvf = Ntm_NetworkBuildMvfs(network, arrayOfRoots, tableOfLeaves, 
                                    careSet);

  array_append(arrayOfRoots, sortedArrayOfPartitionNodes);
  array_append(arrayOfMvf, tmpArrayOfMvf);
  array_free(sortedArrayOfPartitionNodes);
  array_free(tmpArrayOfMvf);


  /* Create one vertex for every component of arrayOfMvf */
  for (i=0; i < array_n(arrayOfRoots); i++) {
    node = array_fetch(Ntk_Node_t *, arrayOfRoots, i);
    mddId = Ntk_NodeReadMddId(node);

    /* obtain the function attached to the node */
    mddFunction = array_fetch(Mvf_Function_t *, arrayOfMvf, i);


    toVertex = g_add_vertex(partition);
    
    /* Update the look-up tables in the graph */
    st_insert(PartPartitionReadNameToVertex(partition),
              Ntk_NodeReadName(node), (char *)toVertex);
    if (mddId != -1) {
      st_insert(PartPartitionReadMddIdToVertex(partition),
                (char *)(long) mddId, (char *)toVertex);
    } 
    toVertex->user_data = 
      (gGeneric)PartVertexInfoCreateSingle(Ntk_NodeReadName(node), 
                                           mddFunction, 
                                           mddId);
  } 
  
  /* Read the list of vertices on the graph */
  sinkList = lsCopy(g_get_vertices(partition), (lsGeneric (*)(lsGeneric))0);

  /* 
   * For every function on every combinational output, compute the
   * support and create vertices in the graph when needed 
   */
  lsForEachItem(sinkList, gen, toVertex) {
    mddFunction = PartVertexReadFunction(toVertex);
    mddSupport = PartCreateFunctionSupportTable(mddFunction);

    /* 
     * Create one edge (and one vertex if necessary) for every element
     * in mddSupport 
     */
    st_foreach_item(mddSupport, stGen, &mddId, NULL) {
      char *name;

      /* Create vertex with the information if needed */
      if (st_lookup(PartPartitionReadMddIdToVertex(partition), 
                    (char *)(long) mddId, &fromVertex) == 0) {
        fromVertex = g_add_vertex(partition);
        
        st_lookup(mddIdToNodeName, (char *)(long) mddId, &name);

        /* Update the look-up tables in the graph */
        st_insert(PartPartitionReadNameToVertex(partition), 
                  name, (char *)fromVertex);
        st_insert(PartPartitionReadMddIdToVertex(partition),
                  (char *)(long) mddId, (char *)fromVertex);
        
        /* Create vertex data */
        fromVertex->user_data = 
          (gGeneric)PartVertexInfoCreateSingle(name,
                                               Mvf_FunctionCreateFromVariable(manager,mddId),
                                               mddId);
      } 
      
      /* 
       * Add the edge to the graph. Make sure a self loop is not added. The
       * self loop may be produced by a mdd that has in its support the same
       * variables that represent the mddId of the node.
       */
      if (fromVertex != toVertex) {
        g_add_edge(fromVertex, toVertex);
      } /* End of if */
      
    } /* End of st_foreach_item */
    
    /* Clean the support table */
    st_free_table(mddSupport);
  } /* End of lsForEachItem */
  
  /* Clean up */
  st_free_table(mddIdToNodeName);
  st_free_table(tableOfLeaves);
  array_free(arrayOfRoots);
  lsDestroy(sinkList, (void (*)(lsGeneric))0);
  /* 
   * The contents of this array (array of mdds) is not deallocated because the
   * information has been transferred to the partition structure. All the
   * functions are stored now as part of the vertex information.
   */
  array_free(arrayOfMvf);
  fprintf(stdout, "NOTICE : current peak memory = %ld\n",
  bdd_read_peak_memory(manager));

} /* End of PartPartitionCut */


int 
Part_IsFanoutInverter(Ntk_Node_t *node)
{
  Ntk_Node_t *fanout;

  fanout = Part_GetFanoutFreeLogic(node);
  if(!fanout)   return(1);
  if(Ntk_NodeReadNumFanins(fanout) == 1)        return(1);
  else                                  return(0);

}

int
Part_CheckLeafNodeCondition(Ntk_Node_t *node, 
                            st_table *leafTable,
                            int fanoutFreeLimit,
                            int numVariableLimit)
{
  int nVar, nDepth, i;
  Ntk_Node_t *fanout, *tnode, *tfanin;
  st_table *ownTable;


  nVar = Ntk_NodeReadNumFanins(node);
  nDepth = 0;
  fanout = node;
  ownTable = st_init_table(st_ptrcmp, st_ptrhash);
  while(1) {
    if(nDepth > fanoutFreeLimit)return(1);
    if(nVar > numVariableLimit) return(1);

    if(!st_lookup(leafTable, fanout, &tnode)) {
       fanout = Part_GetFanoutFreeLogic(fanout);
       if(fanout == 0)  break;
       if(Ntk_NodeTestIsCombInput(fanout))      break;
       if(Ntk_NodeTestIsCombOutput(fanout))     break;
    }
    else break;
    nDepth++;
    if(fanout == 0)     break;
    nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, fanout,
    node, numVariableLimit);
    if(nVar > numVariableLimit) {
      st_free_table(ownTable);
      return(1);
    }
  }

  Ntk_NodeForEachFanin(node, i, tfanin) {
    if(tfanin == 0)     continue;
    if(Ntk_NodeReadNumFanouts(tfanin) != 1)     continue;
    nVar += Img_CutCalcTransitiveFanin(leafTable, ownTable, tfanin, 0, numVariableLimit)-1;
    if(nVar > numVariableLimit) {       
      st_free_table(ownTable);
      return(1);
    }
  }
  if(nVar > numVariableLimit) {
    st_free_table(ownTable);
    return(1);
  }
  return(0);
}

int
Img_CutCalcTransitiveFanin(st_table *table, 
                           st_table *ownTable,
                           Ntk_Node_t *node, 
                           Ntk_Node_t *fanin,
                           int limit)
{
  int i, nVar;
  Ntk_Node_t *tfanin, *tnode;

  nVar = 0;
  Ntk_NodeForEachFanin(node, i, tfanin) {
    if(tfanin == fanin) continue;
    if(tfanin == 0)     continue;
    if(Ntk_NodeReadNumFanouts(tfanin) != 1){
      if(!st_lookup(ownTable, tfanin, &tnode)) {
        st_insert(ownTable, tfanin, tfanin);
        nVar++;
      }
      continue;
    }
    if(Ntk_NodeTestIsCombInput(tfanin)) {
      if(!st_lookup(ownTable, tfanin, &tnode)) {
        st_insert(ownTable, tfanin, tfanin);
        nVar++;
      }
      continue;
    }
    if(Ntk_NodeTestIsCombOutput(tfanin)) {
      if(!st_lookup(ownTable, tfanin, &tnode)) {
        st_insert(ownTable, tfanin, tfanin);
        nVar++;
      }
      continue;
    }
    if(!st_lookup(table, tfanin, &tnode)) {
      nVar += Img_CutCalcTransitiveFanin(table, ownTable, tfanin,  0, limit);
    }
    else
      nVar++;
    if(nVar > limit)    return(nVar);
  }
  return(nVar);
}

Ntk_Node_t *
Part_GetFaninFreeLogic(Ntk_Node_t *node)
{
  int i;
  Ntk_Node_t *fanin;

  Ntk_NodeForEachFanin(node, i, fanin) {
    if(Ntk_NodeReadNumFanouts(fanin) != 1)      continue;
    return(fanin); 
  }
  return(0);
}

Ntk_Node_t *
Part_GetFanoutFreeLogic(Ntk_Node_t *node)
{
  int i;
  Ntk_Node_t *fanout;

  if(Ntk_NodeReadNumFanouts(node) != 1) return(0);
  Ntk_NodeForEachFanout(node, i, fanout) {
    return(fanout); 
  }
  return(0);
}