src/res/resLayer.c

Go to the documentation of this file.

#include "resInt.h"

static char rcsid[] UNUSED = "$Id: resLayer.c,v 1.36 2005/04/16 07:31:03 fabio Exp $";

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

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

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

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

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

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

static array_t * ComputeCompositionLayersAsap(Ntk_Network_t *network, array_t *outputArray, array_t *ignoreArray);
static array_t * ComputeCompositionLayersAlap(Ntk_Network_t *network, array_t *outputArray, array_t *ignoreArray);
static int ComputeAlapLabelling(Ntk_Network_t *network, st_table *nodeLabelling);
static void ComputeAlapLabellingRecur(Ntk_Node_t *node, st_table *nodeLabelling);
static st_table * ComputeTransitiveFanin(array_t *outputArray);
static void ComputeTransitiveFaninRecur(Ntk_Node_t *nodePtr, st_table *faninTable);
static void RecursiveDecrementFanoutCount(Ntk_Node_t *nodePtr, st_table *fanoutCountTable, st_table *visitedTable);

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


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

array_t *
ResComputeCompositionLayers(Ntk_Network_t *network, 
                            array_t *outputArray,   
                            array_t *ignoreArray)   
{
  ResLayerScheduleMethod layerMethod; /* read from the set value */
  array_t *result;  /* Result obtained from procedure */
  char *flagValue;  /* To store the value read from the flag */

  /* Read the value from the flag */
  flagValue = Cmd_FlagReadByName("residue_layer_schedule");
  if (flagValue == NIL(char)) {
    layerMethod = ResDefaultScheduleLayerMethod_c;
  } 
  else {
    if (strcmp(flagValue, "asap") == 0) {
      layerMethod = ResLayerAsap_c;
    }
    else if (strcmp(flagValue, "alap") == 0) {
      layerMethod = ResLayerAlap_c;
    }
    else {
      (void) fprintf(vis_stderr, "** res error: Unknown method to compute layers.");
      (void) fprintf(vis_stderr, "** res error: Assuming default method.\n");
      layerMethod = ResDefaultScheduleLayerMethod_c;
    }
  }

  /* Call the pertinent procedure */
  switch (layerMethod) {
  case ResLayerAlap_c: {
      result = ComputeCompositionLayersAlap(network, outputArray, ignoreArray);
      break;
      }
  case ResLayerAsap_c: {
      result = ComputeCompositionLayersAsap(network, outputArray, ignoreArray);
      break;
      }
  default: {
      (void) fprintf(vis_stdout, "** res warning: Layer computation method not implemented.");
      (void) fprintf(vis_stdout, "** res warning: Executing default method.\n");
      result = ComputeCompositionLayersAlap(network, outputArray, ignoreArray);
      break;
    }
  }

  return result;
} /* End of ResComputeCompositionLayers */


void
ResLayerPrintInfo(Ntk_Network_t *network, 
                  array_t *layerArray)
{

  Ntk_Node_t   *nodePtr, *faninNodePtr; /* Node being processed */
  st_table *faninTable;                 /* Current nodes */
  int layerIndex, newVars;              /* index of the layer being processed */
  int i,j;                              /* For array traversal */
  array_t *currentLayer;                /* layer info */

  /* keep track of all nodes that have appeared in the support */
  faninTable = st_init_table(st_ptrcmp, st_ptrhash);
  /* Loop over the number of elements in layerArray */
  for (layerIndex = 0; layerIndex < array_n(layerArray); layerIndex++) {
    /* reset new variables in the support of this array */
    newVars = 0;
    
    (void) fprintf(vis_stdout, "Layer %d: ", layerIndex);

    /* Access the layer info */
    currentLayer = ResLayerFetchIthLayer(layerArray, layerIndex);  

    /* Print the nodes in a layer that are not PIs */
    LayerForEachNode(currentLayer, i, nodePtr) {
      (void) fprintf(vis_stdout, "%s ", Ntk_NodeReadName(nodePtr));

      /* store fanin nodes in the table, keep count */
      Ntk_NodeForEachFanin(nodePtr, j, faninNodePtr) {
        if (!st_is_member(faninTable, (char *)faninNodePtr)) {
          if (!((Ntk_NodeTestIsLatch(nodePtr) &&
                    (Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
                     Ntk_NodeTestIsLatchInitialInput(faninNodePtr))) ||
                Ntk_NodeTestIsConstant(faninNodePtr))) {
            
            st_insert(faninTable, (char *)faninNodePtr, NIL(char));
            newVars++;
          }
        }
      }
    }

    (void) fprintf(vis_stdout,": SUPPORT = %d", newVars);
    (void) fprintf(vis_stdout, "\n");

    
  } /* End of for every layer */

  /* Clean up */
  st_free_table(faninTable);
  return;
} /* End of ResLayerPrintInfo */


void
ResLayerArrayFree(array_t *layerArray)
{
  int i, end;
  array_t *currentLayer;

  i = 0;
  end = array_n(layerArray);
  for (i =0; i < end ; i++) {
    currentLayer = ResLayerFetchIthLayer(layerArray, i);
    LayerFree(currentLayer);
  }
  array_free(layerArray);
} /* End of ResLayerArrayFree */

/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

static array_t *
ComputeCompositionLayersAsap(Ntk_Network_t *network, 
                             array_t *outputArray,   
                             array_t *ignoreArray)
{
  Ntk_Node_t *nodePtr, *faninNodePtr; /* variables to store node pointers */
  int i, j, k;                        /* iterators */
  st_generator *stGen;                /* generator to step through st_table */
  char *key;                          /* values to read from st_table */
  lsGen listGen;                      /* list generator to step through nodes */
  array_t *currentLayer, *nextLayer;  /* array of nodes belonging to a layer */
  array_t *layerArray;                /* array of layers */
  st_table *fanoutCountTable;         /* table to store fanout counts of each
                                       * node
                                       */
  int fanoutCount;                    /* variable to store fanout count of a
                                       * node
                                       */
  int value;                          /* to read value off the st_table */
  st_table *visitedTable;             /* table to store visited nodes */
  
  /* create a fanout count table starting with all nodes except PIs,
   * constant node or a shadow node for any node but a latch(counts as
   * comb output).
   */
  fanoutCountTable = st_init_table(st_ptrcmp, st_ptrhash); 
  Ntk_NetworkForEachNode(network, listGen, nodePtr) {
    /* does not nodes like PIs, shadow nodes, constants, undefined
     * nodes to compute the fanouts, since they do not have to be
     * composed into the circuit.
     */
    if ((Ntk_NodeTestIsCombOutput(nodePtr)) ||
         (!(Ntk_NodeTestIsCombInput(nodePtr) ||
          Ntk_NodeTestIsConstant(nodePtr) ||
          Ntk_NodeTestIsUndefined(nodePtr) ||  
          Ntk_NodeTestIsShadow(nodePtr)))) {
      st_insert(fanoutCountTable, (char *)nodePtr, 
                (char *)(long)Ntk_NodeReadNumFanouts(nodePtr));
    }
  }
  
  /* take out outputs in directly verified table, if so desired */
  /* Assume ignore table has node pointers , reduce fanout count of
   * transitive fanin of these nodes
   */
  if (ignoreArray != NULL) {
    visitedTable = st_init_table(st_ptrcmp, st_ptrhash);
    arrayForEachItem(Ntk_Node_t *, ignoreArray, i, nodePtr) {
      /* each key is an output node */
      RecursiveDecrementFanoutCount(nodePtr, fanoutCountTable, visitedTable);
    }
    st_free_table(visitedTable);

    /* remove all nodes that are primary inputs and those with fanout
     * count 0 providing they are not primary outputs/ or latch inputs
     * or latch initial values.
     */
    st_foreach_item_int(fanoutCountTable, stGen, &key, &value) {
      fanoutCount = value;
      nodePtr = (Ntk_Node_t *)key;
      assert(fanoutCount >= -1);
      if ((!Ntk_NodeTestIsCombOutput(nodePtr))
          && (fanoutCount <= 0)) {
        /* delete the item corresponding to fanoutCount i.e. value */
        st_delete_int(fanoutCountTable, (char **)&key, &value);
      }
    }
    /* remove all outputs that belong to ignore outputs */
    arrayForEachItem(Ntk_Node_t *, ignoreArray, i, nodePtr) {
      st_delete_int(fanoutCountTable, &nodePtr, &value);
    }
  }  

  /* start preparing the layer array */
  layerArray = array_alloc(array_t *, 0); 
  currentLayer = LayerCreateEmptyLayer();

  /*  outputs form the first layer */
  Ntk_NetworkForEachCombOutput(network, listGen, nodePtr) {
    if (st_lookup_int(fanoutCountTable, (char *)nodePtr, &fanoutCount)) {
      /* insert all outputs that aren't to be ignored in the first layer of the
       * layer array
       */
      LayerAddNodeAtEnd(currentLayer, nodePtr);
    }
  }

  /* if current layer is not empty */
  while (ResLayerNumNodes(currentLayer) ) {
    /* insert current layer into layer array */
    array_insert_last(array_t *, layerArray, currentLayer);
    nextLayer = LayerCreateEmptyLayer();
    LayerForEachNode(currentLayer, i, nodePtr) {
      Ntk_NodeForEachFanin(nodePtr, j, faninNodePtr) {
        /* do not want to get the fanin for latch outputs */
        if(!(Ntk_NodeTestIsConstant(nodePtr) ||
             (Ntk_NodeTestIsLatch(nodePtr) &&
             (Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
              Ntk_NodeTestIsLatchInitialInput(faninNodePtr))))) {
          if (!st_lookup_int(fanoutCountTable, (char *)faninNodePtr,
                             &fanoutCount)) {
            /* maybe it is a PI or constant node */
            if (!(Ntk_NodeTestIsCombInput(faninNodePtr) ||
                  Ntk_NodeTestIsConstant(faninNodePtr) ||
                  Ntk_NodeTestIsUndefined(faninNodePtr) ||
                  Ntk_NodeTestIsShadow(faninNodePtr))) {
              error_append("Fanin node %s should have been in table");
              error_append(Ntk_NodeReadName(faninNodePtr));
              /* Cleanup */
              arrayForEachItem(array_t *, layerArray, k, currentLayer) {
                LayerFree(currentLayer);
              }
              array_free(layerArray);
              return NIL(array_t);
            } /* node is neither PI nor constant */
          } else { /* node is found in table */
            fanoutCount--;
            /* decrement fanout count, will go into a later layer */
            if (fanoutCount == 0) {
              /*
               * it is ready to be put in the array,
               * since its fanout count is 1
               */
              LayerAddNodeAtEnd(nextLayer, faninNodePtr);
            } else if (fanoutCount > 0) {
                /* insert new decremented value in table */
              st_insert(fanoutCountTable, (char *)faninNodePtr,
                        (char *)(long)fanoutCount);

            } /* end of nodes fanout count larger than 1 */
          } /* end of fanin node found in fanout count table */
        } /* do not want to get the fanin for latch outputs */
      } /* end of iteration through all the fanin nodes of current node */
    } /* end of iteration through all the nodes of current layer */
    /* the fanout count ensures unique entry of elements ????*/
    currentLayer = nextLayer;
  } /* end of while some nodes in current layer */  
  
  /* the loop always exits with an empty array */
  LayerFree(currentLayer);
  st_free_table(fanoutCountTable);
  if (array_n(layerArray) == 0) {
    array_free(layerArray);
    layerArray = NIL(array_t);
  }

  return (layerArray);
  
} /* End of ComputeCompositionLayersAsap */

static array_t *
ComputeCompositionLayersAlap(Ntk_Network_t *network,
                             array_t *outputArray,  
                             array_t *ignoreArray)
{
  Ntk_Node_t *nodePtr;       /* node being processed  */
  array_t *layerArray;       /* array of layers */
  array_t *currentLayer;     /* layer of nodes */
  st_table *nodeLabelling;   /* labeling of a node, its farthest distance
                              * from the primary input
                              */
  int numLayers;             /* Number of Layers */
  int layerIndex;            /* index of a layer (from the primary output */
  int arrayIndex;            /* iterator */
  st_generator *stGen;       /* generator to step through table */
  char *key;                 /* values to read from table */
  int value;                 /* integer value to read from the table */

  /* Initialize the labeling table */
  nodeLabelling = ComputeTransitiveFanin(outputArray);

  /* Compute the labeling of the nodes */
  numLayers = ComputeAlapLabelling(network, nodeLabelling);

  /* Create the layerArray structure */
  layerArray = array_alloc(array_t *, numLayers);
  /* initialize layers */
  for (layerIndex = 0; layerIndex < numLayers; layerIndex++) {
    currentLayer = LayerCreateEmptyLayer();
    array_insert(array_t *, layerArray, layerIndex, currentLayer);
  } /* end of for */

  /* insert elements of the st_table in the layers */
  st_foreach_item_int(nodeLabelling, stGen, &key, &value) {
    layerIndex = value;
    nodePtr = (Ntk_Node_t *)key;
    /* don't put PIs or comb inputs or constants or undefined
     * nodes in layer array
     */
    if ((Ntk_NodeTestIsCombOutput(nodePtr)) ||
        ((layerIndex > 0) &&
         !(Ntk_NodeTestIsCombInput(nodePtr) ||
           Ntk_NodeTestIsConstant(nodePtr) ||
           Ntk_NodeTestIsUndefined(nodePtr) ||
           Ntk_NodeTestIsShadow(nodePtr)))) {
      /* the layers are arranged in reverse order of their farthest
       * distance from the node. Hence each node is inserted into
       * the numLayers-1-layerIndex. Nodes with layerIndex should be
       * put in the last array since they are probably constants
       * at the primary outputs or latch initial value. LayerIndex
       * could be 0 for primary outputs if it does not appear in the
       * transitive fanin of the comb inputs. 
       */
      if (layerIndex == 0) {
        arrayIndex = 0;
        assert(Ntk_NodeTestIsCombOutput(nodePtr) == 1);
      } else {
        arrayIndex = numLayers - layerIndex;
      }
      currentLayer = array_fetch(array_t *, layerArray, arrayIndex);
      LayerAddNodeAtEnd(currentLayer, nodePtr);
    }
  }
  /* Clean up */
  st_free_table(nodeLabelling);

  
  return layerArray;
} /* End of ComputeCompositionLayersAlap */


static int
ComputeAlapLabelling(Ntk_Network_t *network, 
                     st_table *nodeLabelling)
{
  Ntk_Node_t *nodePtr; /* Node being processed */
  lsGen gen;           /* For list traversal */
  int numLayers;       /* To return as result */
  int outputDepth;     /* Depth of the output being processed */

  assert(nodeLabelling != NIL(st_table));

  /* For primary inputs in the table (those not in the table
   * are in the transitive fanin of the ignored outputs only
   */
  Ntk_NetworkForEachCombInput(network, gen, nodePtr) {
    /* do it for fanouts that are in table only */
    if (st_is_member(nodeLabelling, (char *)nodePtr)) {
      ComputeAlapLabellingRecur(nodePtr, nodeLabelling);
    }
  }

  /* Compute the number of layers */
  numLayers = 0;
  Ntk_NetworkForEachCombOutput(network, gen, nodePtr) {
    /* only those outputs not be to be ignored */
    if (st_lookup_int(nodeLabelling, (char *)nodePtr, &outputDepth)) {
      if (outputDepth > numLayers ) {
        numLayers = outputDepth;
      } /* End of if */
    }
  }
  
  return numLayers;
} /* End of ComputeAlapLabelling */

static void
ComputeAlapLabellingRecur(Ntk_Node_t *node,
                          st_table *nodeLabelling)
{
  Ntk_Node_t *fanoutPtr;
  int nodeDepth;
  int fanoutDepth;
  int i;

  /* Trivial case */
  if (Ntk_NodeReadNumFanouts(node) == 0) {
    return;
  } /* End of if */

  /* Look up information for the current node */
  st_lookup_int(nodeLabelling, (char *)node, &nodeDepth);
  
  /* Iterate over its fanouts */
  Ntk_NodeForEachFanout(node, i, fanoutPtr) {
    /* Do not process as soon as an input is found beyond an output */
    if (!((Ntk_NodeTestIsLatchDataInput(node) ||
           Ntk_NodeTestIsLatchInitialInput(node)) &&
          Ntk_NodeTestIsLatch(fanoutPtr))) {
      if (st_is_member(nodeLabelling, (char *)fanoutPtr)) {
        /* Look up information for the fanout */
        st_lookup_int(nodeLabelling, (char *)fanoutPtr, &fanoutDepth);
        /* If the fanout depth needs to be modified, do so, and recur */
        if (nodeDepth >= fanoutDepth) {
          st_insert(nodeLabelling, (char *)fanoutPtr, 
                    (char *)(long)(nodeDepth + 1));
          ComputeAlapLabellingRecur(fanoutPtr, nodeLabelling);
        } /* End of if */
      } /* End of if */
    } /* End of if */
  } /* End of for each fanout */

  return;
} /* End of ComputeAlapLabellingRecur */


static st_table *
ComputeTransitiveFanin(array_t *outputArray)
{
  Ntk_Node_t *nodePtr;
  st_table * faninTable;
  int i;
  
  faninTable = st_init_table(st_ptrcmp, st_ptrhash);
  arrayForEachItem(Ntk_Node_t *, outputArray, i, nodePtr) {
    ComputeTransitiveFaninRecur(nodePtr, faninTable);
  }
  return faninTable;
} /* End of ComputeTransitiveFanin */

static void
ComputeTransitiveFaninRecur(Ntk_Node_t *nodePtr,  
                            st_table *faninTable)
{
  Ntk_Node_t *faninNodePtr;
  int i;

  if (st_lookup(faninTable, (char *)nodePtr, NIL(char *))) {
    return;
  }


  /* recur on fanin nodes */
  Ntk_NodeForEachFanin(nodePtr, i, faninNodePtr) {
    /* Test this case cos other comb inputs have no fanins */
    if (!((Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
           Ntk_NodeTestIsLatchInitialInput(faninNodePtr)) &&
          Ntk_NodeTestIsLatch(nodePtr))) {
      ComputeTransitiveFaninRecur(faninNodePtr, faninTable);
    } /* end of if */
  } /* iterate over all fanins */
  
  st_insert(faninTable, (char *)nodePtr, NIL(char));
  return;

} /* End of ComputeTransitiveFaninRecur */

static void
RecursiveDecrementFanoutCount(Ntk_Node_t *nodePtr, 
                              st_table *fanoutCountTable,
                              st_table *visitedTable)
{
  Ntk_Node_t *faninNodePtr;
  int i, fanoutCount;

  /* the following kinds of nodes will not be in the table. */
  if ((!Ntk_NodeTestIsCombOutput(nodePtr)) && 
       (Ntk_NodeTestIsCombInput(nodePtr) ||
        Ntk_NodeTestIsUndefined(nodePtr)||
        Ntk_NodeTestIsConstant(nodePtr) ||
        Ntk_NodeTestIsShadow(nodePtr))) {
    return;
  }
  /* all nodes called here should exist in table */
  if (!st_lookup_int(fanoutCountTable, (char *)nodePtr, &fanoutCount)){
    error_append("Node ");
    error_append(Ntk_NodeReadName(nodePtr));
    error_append(" should have been in table\n");
    return;
  }

  fanoutCount--;
  /* reduce fanout count of node */
  st_insert(fanoutCountTable, (char *)nodePtr, (char *)(long)fanoutCount);
  /* if this node is visited, decrement its fanout but do not proceed
   * any further (i.e. do not proceed with its fanins
   */
  if (st_is_member(visitedTable, (char *)nodePtr)) {
    return;
  } else {
    st_insert(visitedTable, (char *)nodePtr, NIL(char));

    /* 
     * recur with fanin nodes except nodes with no fanins (that arent in table)
     * and latch outputs 
     */
    Ntk_NodeForEachFanin(nodePtr, i, faninNodePtr) {
      /* may be a redundant test, since it will pop out in the first line of
       * the procedure anyways. 
       */
      if (!(Ntk_NodeTestIsConstant(faninNodePtr) ||
          ((Ntk_NodeTestIsLatchDataInput(faninNodePtr) ||
            Ntk_NodeTestIsLatchInitialInput(faninNodePtr)) &&
           Ntk_NodeTestIsLatch(nodePtr)))) {
        RecursiveDecrementFanoutCount(faninNodePtr, fanoutCountTable, visitedTable);
      } 
    } /* end of iterating over fanins */
  } /* end of else if not visited */
  return;
} /* End of RecursiveDecrementFanoutCount */