src/restr/restrCmd.c

Go to the documentation of this file.

#include "restrInt.h"

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


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


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


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

static jmp_buf timeOutEnv;
int restrCreatedPart;
int restrCreatedFsm;
boolean restrVerbose;

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

static int CommandRestructureFsm(Hrc_Manager_t **hmgr, int argc, char **argv);
static void TimeOutHandle(void);
static st_table * readInputProbabilities(Ntk_Network_t *network, FILE *fp);
static void CleanUp(Ntk_Network_t *network1, st_table *inputProb, char *outOrderFileName, char *dumpFileName, char *prefix, int varOrdered, int restrCreatedPart, int restrCreatedFsm, char *probFile);
static enum st_retval stCountFree(char *key, char *value, char *arg);
static int IsPartitionValid(Ntk_Network_t *network, graph_t *partition);
static int TestIsNetworkMultipleValued(Ntk_Network_t *network);

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

void
Restr_Init(void)
{
  Cmd_CommandAdd("restruct_fsm", CommandRestructureFsm, 0);
}

void
Restr_End(void)
{

} /* End of Restr_End */


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

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


static int
CommandRestructureFsm(
  Hrc_Manager_t **hmgr,
  int argc,
  char **argv)
{
  graph_t *partition = NIL(graph_t);
  Fsm_Fsm_t *fsm = NIL(Fsm_Fsm_t);
  Ntk_Network_t *network1 = NIL(Ntk_Network_t);
  Hrc_Node_t *currentNode = NIL(Hrc_Node_t);
  lsList dummy = (lsList) 0;
  char *modelName,*str;
  int timeOutPeriod;
  boolean status;
  int c;
  long initialTime, finalTime;
  RestructureHeuristic heuristic;
  boolean equivClasses, nonReachEquiv;
  boolean eqvMethod;
  int varOrdered;
  char *outOrderFileName,*blifName;
  char *dumpFileName,*probFile;
  int reorder,trySharing,realign;
  FILE *fp;
  st_table *inputProb = NULL;

    /* Synthesis related options */
  Synth_InfoData_t *synthInfo;
  int factoring, divisor;
  char *prefix;
  
  if (bdd_get_package_name() != CUDD) {
    (void) fprintf(vis_stderr,
                   "** restr error: The restr package can be used only with CUDD package\n");
    (void) fprintf(vis_stderr,"** restr error: Please link with CUDD package\n");
    return 0;
  }
        
  /* These are the default values. */
  timeOutPeriod   = 0;  
  status          = FALSE;
  restrVerbose    = 0;
  equivClasses    = 0;
  nonReachEquiv   = 0;
  eqvMethod       = 0;
  heuristic       = RestrHammingD_c;
  fp              = NIL(FILE);
  outOrderFileName = NIL(char);
  dumpFileName = NIL(char);
  probFile = NIL(char);
  restrCreatedPart = 0;
  restrCreatedFsm = 0;
  varOrdered = 0;

  /* Synthesis related default values */
  factoring = 0;
  divisor = 1;
  prefix = NIL(char);
  reorder = 0;
  trySharing = 0;
  realign = 0;

  util_getopt_reset();

  while((c = util_getopt(argc, argv, "f:d:i:EeNvD:o:t:s:F:R:TAh")) != EOF) {
    switch(c) {
    case 'f':
      factoring = atoi(util_optarg);
      break;
    case 'd':
      divisor = atoi(util_optarg);
      break;
    case 'i':
      prefix = util_strsav(util_optarg);
      break;
    case 'E':
      equivClasses = 1;
      break;
    case 'e':
      eqvMethod = 1;
      break;
    case 'N':
      nonReachEquiv = 1;
      break;
    case 'v':
      restrVerbose = 1;
      break;
    case 'D':
      dumpFileName = util_strsav(util_optarg);
      break;
    case 'o':
      outOrderFileName = util_strsav(util_optarg);
      /* Check if the file specified to dump variable order already exists */
      fp = Cmd_FileOpen(outOrderFileName,"r",NIL(char *),1);
      if (fp) {
        (void) fprintf(vis_stderr,"** restr error: Output order file %s already exists.\n",
                       outOrderFileName);
        (void) fprintf(vis_stderr,"** restr error: Please specify another name.\n");
        fclose(fp);
        FREE(outOrderFileName);
        goto endgame;
      }
      break;
    case 't':
      timeOutPeriod = atoi(util_optarg);
      break;
    case 's':
      str = util_strsav(util_optarg);
      if (strcmp(str,"ham") == 0) {
        heuristic = RestrHammingD_c;
      } else if (strcmp(str,"fanin") == 0) {
        heuristic = RestrFanin_c;
      } else if (strcmp(str,"faninout") == 0) {
        heuristic = RestrFaninFanout_c;
      } else if (strcmp(str,"cproj") == 0) {
        heuristic = RestrCProjection_c;
      } else {
        (void) fprintf(vis_stderr,"** restr warning: Invalid option %s\n",str);
        (void) fprintf(vis_stderr,"** restr warning: Using Hamming distance heuristic\n\n");
        heuristic = RestrHammingD_c;
      }
      FREE(str);
      break;
    case 'F':
      probFile = util_strsav(util_optarg);
      fp = Cmd_FileOpen(probFile,"r",NIL(char *),1);
      if (!fp) {
        fprintf(vis_stderr,"** restr warning: Cannot open %s \n",probFile);
        fprintf(vis_stderr,"** restr warning: Assuming equi probable primary inputs\n");
        FREE(probFile);
        probFile = NIL(char);
      } else {
        fclose(fp);
      }
      break;
    case 'R':
      /* Option to enable/disable reordering during synthesis
         (factorization) stage */
      reorder = atoi(util_optarg);
      break;
    case 'T':
      /* During factorization maximize sharing of nodes */
      trySharing = 1;
      break;
    case 'A':
      /* Realign ZDD variables after BDD variable reordering and vice
         versa */
      realign = 1;
      break;
    case 'h':
      goto usage;
    default:
      goto usage;
    }
  }

  if(Hrc_ManagerReadCurrentNode(*hmgr) == NIL(Hrc_Node_t)) {
    (void) fprintf(vis_stderr,"** restr error: The hierarchy manager is empty.");
    (void) fprintf(vis_stderr," Read in design.\n");
    goto endgame;
  }

  network1 = (Ntk_Network_t *) 
    Hrc_NodeReadApplInfo(Hrc_ManagerReadCurrentNode(*hmgr), 
                         NTK_HRC_NODE_APPL_KEY);

  if(network1 == NIL(Ntk_Network_t)) {
    (void) fprintf(vis_stderr,"** restr error: There is no network. ");
    (void) fprintf(vis_stderr,"Use flatten_hierarchy.\n");
    goto endgame;
  }

  if(!Ntk_NetworkReadNumLatches(network1)) {
    (void) fprintf(vis_stderr,"**restr error: No latches present in the ");
    (void) fprintf(vis_stderr,"current network.\n");
    (void) fprintf(vis_stderr,"** restr error: This algorithm does not apply.\n");
    goto endgame;
  }

  /* Check if the current network has signals with multiple values. */
  if (TestIsNetworkMultipleValued(network1)) {
    (void) fprintf(vis_stderr,"** restr error: Circuit has multiple valued variables.\n");
    (void) fprintf(vis_stderr,"** restr error: This algorithm applies to boolean signals only.\n");
    goto endgame;
  }

  if(Ntk_NetworkReadNumPrimaryInputs(network1) !=
     Ntk_NetworkReadNumInputs(network1)) {
    (void) fprintf(vis_stderr,"** restr error: Pseudo inputs present in the network.\n");
    (void) fprintf(vis_stderr,"** restr error: This algorithm does not apply.\n");
    goto endgame;
  }

  if (!dumpFileName)
    dumpFileName = util_strsav(Ntk_NetworkReadName(network1));
  /* Check if the output blif file already exists */
  blifName = util_strcat3(dumpFileName,".ml.blif","");
  fp = Cmd_FileOpen(blifName,"r",NIL(char *),1);
  if (fp) {
    (void) fprintf(vis_stderr,"** restr error: Output blif file %s already exists.\n",
                   blifName);
    (void) fprintf(vis_stderr,"** restr error: Please specify another name.\n");
    fclose(fp);
    FREE(blifName);
    goto endgame;
  }
  FREE(blifName);


  /* Check if the network has the variables ordered */
  if (Ord_NetworkTestAreVariablesOrdered(network1, Ord_InputAndLatch_c) == 
      FALSE) {
    Ord_NetworkOrderVariables(network1,Ord_RootsByDefault_c,
                              Ord_NodesByDefault_c, FALSE,
                              Ord_InputAndLatch_c,Ord_Unassigned_c,
                              dummy,0);
    varOrdered = 1;
  }

  /* If primary input probabilities are specified, read them */
  if (probFile) {
    fp = Cmd_FileOpen(probFile,"r",NIL(char *),1);
    inputProb = readInputProbabilities(network1,fp);
    fclose(fp);
    FREE(probFile);
    fp = NIL(FILE);
  }

  /* Check if there is an FSM already attached to the network */
  fsm = (Fsm_Fsm_t *) Ntk_NetworkReadApplInfo(network1, 
                                              FSM_NETWORK_APPL_KEY);
  if (fsm == NIL(Fsm_Fsm_t)) {
    partition = (graph_t *) Ntk_NetworkReadApplInfo(network1,
                                                    PART_NETWORK_APPL_KEY);
    /* If there is none then create one. */
    if (partition == NIL(graph_t) ||
        (!IsPartitionValid(network1,partition))) {
      currentNode = Hrc_ManagerReadCurrentNode(*hmgr);
      modelName = Hrc_NodeReadModelName(currentNode);
      partition = Part_NetworkCreatePartition(network1, currentNode,
                                              modelName, (lsList) 0, 
                                              (lsList) 0, NIL(mdd_t), 
                                              Part_InOut_c, (lsList) 0, 
                                              FALSE, FALSE, TRUE);
 
      Ntk_NetworkAddApplInfo(network1, RESTR_PART_NETWORK_APPL_KEY,
                             (Ntk_ApplInfoFreeFn) Part_PartitionFreeCallback,
                             (void *) partition);
      restrCreatedPart = 1;
    }
    fsm = Fsm_FsmCreateFromNetworkWithPartition(network1, 
                                                Part_PartitionDuplicate(partition));
    if (fsm == NIL(Fsm_Fsm_t)) {
      (void) fprintf(vis_stderr,"** restr error: Could not create ");
      (void) fprintf(vis_stderr,"an Fsm\n");
      goto endgame;
    }
    Ntk_NetworkAddApplInfo(network1, RESTR_FSM_NETWORK_APPL_KEY,
                           (Ntk_ApplInfoFreeFn) Fsm_FsmFreeCallback,
                           (void *) fsm);
    restrCreatedFsm = 1;
  } else {
    partition = (graph_t *) Fsm_FsmReadPartition(fsm);

    if (partition == NIL(graph_t) || 
        (!IsPartitionValid(network1,partition))) {
      currentNode = Hrc_ManagerReadCurrentNode(*hmgr);
      modelName = Hrc_NodeReadModelName(currentNode);
      partition = Part_NetworkCreatePartition(network1, currentNode,
                                              modelName, (lsList) 0, 
                                              (lsList) 0, NIL(mdd_t), 
                                              Part_InOut_c, (lsList) 0, 
                                              FALSE, FALSE, TRUE);
      Ntk_NetworkAddApplInfo(network1, RESTR_PART_NETWORK_APPL_KEY,
                             (Ntk_ApplInfoFreeFn) Part_PartitionFreeCallback,
                             (void *) partition);
      restrCreatedPart = 1;

      fsm = Fsm_FsmCreateFromNetworkWithPartition(network1, 
                                                  Part_PartitionDuplicate(partition));
      if (fsm == NIL(Fsm_Fsm_t)) {
        (void) fprintf(vis_stderr,"** restr error: Could not create ");
        (void) fprintf(vis_stderr,"an Fsm\n");
        goto endgame;
      }
      Ntk_NetworkAddApplInfo(network1, RESTR_FSM_NETWORK_APPL_KEY,
                             (Ntk_ApplInfoFreeFn) Fsm_FsmFreeCallback,
                             (void *) fsm);
      restrCreatedFsm = 1;
    }
  }

  /* Start the timer before calling restruct. */
  if (timeOutPeriod > 0){
    (void) signal(SIGALRM, (void(*)(int))TimeOutHandle);
    (void) alarm(timeOutPeriod);
    if (setjmp(timeOutEnv) > 0) {
      (void) fprintf(vis_stderr, "** restr warning: Timeout occurred after ");
      (void) fprintf(vis_stderr, "%d seconds.\n", timeOutPeriod);
      alarm(0);
      goto endgame;
    }
  }

  /* Prepare the data structure for the synthesis package */
  synthInfo = Synth_InitializeInfo(factoring,divisor,0,
                                   reorder,trySharing,realign,
                                   dumpFileName,prefix,0);

  initialTime = util_cpu_time();
  status = RestrCommandRestructureFsm(fsm, heuristic,outOrderFileName,
                                      equivClasses,nonReachEquiv,
                                      eqvMethod,inputProb,synthInfo);
  finalTime = util_cpu_time();
  if(status) {
    (void) fprintf(vis_stdout, "%-20s%10ld\n", "RESTR: analysis time =",
                   (finalTime-initialTime)/1000);

  }
  else {
    (void) fprintf(vis_stdout, "** restr error: Could not restructure successfully.\n");
  }
    
  if (synthInfo)
    Synth_FreeInfo(synthInfo);

    /* Clean up */
  CleanUp(network1,inputProb,outOrderFileName,dumpFileName,prefix,
          varOrdered,restrCreatedPart,restrCreatedFsm,probFile);

  alarm(0);
  return 0;  /* normal exit */

endgame:
  /* Clean up */
  CleanUp(network1,inputProb,outOrderFileName,dumpFileName,prefix,
          varOrdered,restrCreatedPart,restrCreatedFsm,probFile);
    
  return 1; /* Error exit */

usage:
  if (outOrderFileName)
    FREE(outOrderFileName);
  if (dumpFileName)
    FREE(dumpFileName);
  if (prefix)
    FREE(prefix);
  if (probFile)
    FREE(probFile);

  (void) fprintf(vis_stderr, "\nusage: Also see help restruct_fsm for more details.\n\n");
  (void) fprintf(vis_stderr, "    -A      \t\tAllow realignment--during symbolic factorization--of BDD\n");
  (void) fprintf(vis_stderr, "            \t\tand ZDD variables after reordering.\n\n");
  (void) fprintf(vis_stderr, "    -D <fileHead>\tOutput file name for synthesized circuit.\n");
  (void) fprintf(vis_stderr, "            \t\tDefault: model_name.ml.blif\n\n");
  (void) fprintf(vis_stderr, "    -d <divMethod>\tChoose a divisor during synthesis. See\n");
  (void) fprintf(vis_stderr, "            \t\tsynthesize_network command for more details.\n");
  (void) fprintf(vis_stderr, "            \t\t0 : Fast divisor\n");
  (void) fprintf(vis_stderr, "            \t\t1 : Least occuring literal divisor (default)\n");
  (void) fprintf(vis_stderr, "            \t\t2 : Most occuring literal divisor\n");
  (void) fprintf(vis_stderr, "            \t\t3 : Level-0 kernel divisor\n\n");
  (void) fprintf(vis_stderr, "    -E      \t\tPrint the number of equivalence classes in the STG.\n\n");
  (void) fprintf(vis_stderr, "    -F <probFile>\tInput file with PI probabilities, one per line.\n\n");
  (void) fprintf(vis_stderr, "    -f <factMethod>\tChoose a factorization method. See synthesize_network\n");
  (void) fprintf(vis_stderr, "            \t\tfor more details.\n");
  (void) fprintf(vis_stderr, "            \t\t0 : Simple factoring (default)\n");
  (void) fprintf(vis_stderr, "            \t\t1 : Generic factoring\n\n");
  (void) fprintf(vis_stderr, "    -h      \t\tPrint command usage.\n\n");
  (void) fprintf(vis_stderr, "    -i <name>\t\tPrefix to be used to generate names for internal\n");
  (void) fprintf(vis_stderr, "            \t\tnodes during synthesis. Default: \"_n\"\n\n");
  (void) fprintf(vis_stderr, "    -N      \t\tExpand the reachable set R to include those states\n");
  (void) fprintf(vis_stderr, "            \t\twhich are equivalent to R but unreachable.\n");
  (void) fprintf(vis_stderr, "            \t\tThe default is not to include.\n\n");
  (void) fprintf(vis_stderr, "    -o <orderFile>\tFile to output BDD variable order at the end.\n\n");
  (void) fprintf(vis_stderr, "    -R <value>\t\tSet reordering (0-3)\n");
  (void) fprintf(vis_stderr, "            \t\t0 : no reordering (default)\n");
  (void) fprintf(vis_stderr, "            \t\t1 : reordering in only BDD\n");
  (void) fprintf(vis_stderr, "            \t\t2 : reordering on only ZDD\n");
  (void) fprintf(vis_stderr, "            \t\t3 : reordering on both\n\n");
  (void) fprintf(vis_stderr, "    -s <heuristic>\tHeuristic to perform restructuring.\n");
  (void) fprintf(vis_stderr, "            \t\tType help restruct_fsm for more details on each option.\n");
  (void) fprintf(vis_stderr, "            \t\tham : Hamming distance based heuristic. (Default)\n");
  (void) fprintf(vis_stderr, "            \t\tfanin : Fanin oriented heuristic.\n");
  (void) fprintf(vis_stderr, "            \t\tfaninout : Fanin-Fanout oriented heuristic.\n");
  (void) fprintf(vis_stderr, "            \t\tcproj : C-Projection based heuristic.\n\n");
  (void) fprintf(vis_stderr, "    -T      \t\tTry to share mode nodes during symbolic factorization.\n\n");
  (void) fprintf(vis_stderr, "    -t <seconds>\tTime in seconds to complete the command. The command\n");
  (void) fprintf(vis_stderr, "            \t\tis aborted if computation time goes above this limit.\n\n");
  (void) fprintf(vis_stderr, "    -v      \t\tTurn on verbosity.\n");


  return 1;    /* error exit */
}

static void
TimeOutHandle(void)
{
  longjmp(timeOutEnv, 1);
}


static st_table *
readInputProbabilities(
  Ntk_Network_t *network,
  FILE *fp)

{
  Ntk_Node_t *node;
  char name[MAX_NAME_LEN];
  double value;
  double *valuePtr;
  st_table *inputProb;

  inputProb = st_init_table(st_numcmp,st_numhash);

  while (fscanf(fp, "%s %lf\n", name, &value) != EOF) {
    node = Ntk_NetworkFindNodeByName(network,name);
    if (node == NIL(Ntk_Node_t)) {
      (void) fprintf(vis_stderr,"** restr error: No node by name %s in the network\n",name);
      (void) fprintf(vis_stderr,"** restr error: Aborting.\n");
      st_foreach(inputProb,stCountFree,NIL(char));
      st_free_table(inputProb);
      return NULL;
    }
    if (!Ntk_NodeTestIsPrimaryInput(node)) {
      fprintf(vis_stderr,"** restr warning: <%s> is not a primary input.\n",name);
      fprintf(vis_stderr,"** restr warning: Assuming equiprobable primary inputs\n");
      st_foreach(inputProb,stCountFree,NIL(char));
      st_free_table(inputProb);
      return NULL;
    }
    valuePtr = ALLOC(double,1);
    if (value > 1.0) {
      (void) fprintf(vis_stderr,"** restr warning: %s has prob. value greater than 1: %g\n",
                     name,value);
      (void) fprintf(vis_stderr,"** restr warning: Assuming a prob. value of 0.5\n");
      *valuePtr = 0.5;
    } else {
      *valuePtr = value;
    }
    st_insert(inputProb,(char *)(long)Ntk_NodeReadMddId(node),(char *)valuePtr);
  }

  return inputProb;
}

static void
CleanUp(
  Ntk_Network_t *network1,
  st_table *inputProb,
  char *outOrderFileName,
  char *dumpFileName,
  char *prefix,
  int varOrdered,
  int restrCreatedPart,
  int restrCreatedFsm,
  char *probFile)
{
  Ntk_Node_t *node;
  lsGen gen;

  if (inputProb) {
    st_foreach(inputProb,stCountFree,NIL(char));
    st_free_table(inputProb);
  }
    
  if (outOrderFileName)
    FREE(outOrderFileName);
  if (dumpFileName)
    FREE(dumpFileName);
  if (prefix)
    FREE(prefix);
  if (probFile)
    FREE(probFile);

  /* Set the mdd id's for all the primary inputs, latches and next
   * state nodes to UNASSIGNED if it was specifically set in this
   * routine.
   */
  if (varOrdered) {
    Ntk_NetworkForEachPrimaryInput(network1,gen,node) {
      Ntk_NodeSetMddId(node,NTK_UNASSIGNED_MDD_ID);
    }
    Ntk_NetworkForEachLatch(network1,gen,node) {
      Ntk_Node_t *shadow;
      shadow = Ntk_NodeReadShadow(node);
      Ntk_NodeSetMddId(node,NTK_UNASSIGNED_MDD_ID);    
      Ntk_NodeSetMddId(shadow,NTK_UNASSIGNED_MDD_ID);    
    }
  }
  /* Delete the partition hooked to the network if it was created in
   * this routine.
   */
  if (restrCreatedPart) {
    Ntk_NetworkFreeApplInfo(network1,RESTR_PART_NETWORK_APPL_KEY);
  }
  /* Delete the FSM hooked to the network if it was created in
   * this routine.
   */
  if (restrCreatedFsm) {
    Ntk_NetworkFreeApplInfo(network1,RESTR_FSM_NETWORK_APPL_KEY);
  }
}

static enum st_retval
stCountFree(
  char *key,
  char *value,
  char *arg)
{
  double        *d;
  
  d = (double *)value;
  FREE(d);
  return(ST_CONTINUE);
  
} /* end of stCountfree */


static int
IsPartitionValid(Ntk_Network_t *network,
                 graph_t *partition)
{
  Ntk_Node_t *node;
  lsGen gen;
  char *name;

  Ntk_NetworkForEachCombOutput(network, gen, node) {
    name = Ntk_NodeReadName(node);
    if(Part_PartitionFindVertexByName(partition, name) == NIL(vertex_t)) {
      return(0);
    }
  }
  Ntk_NetworkForEachCombInput(network, gen, node) {
    name = Ntk_NodeReadName(node);
    if(Part_PartitionFindVertexByName(partition, name) == NIL(vertex_t)) {
      return(0);
    }
  }

  return 1;
}

static int
TestIsNetworkMultipleValued(Ntk_Network_t *network)
{
  Ntk_Node_t *node;
  lsGen gen;
  Var_Variable_t *var;
  int numValues;

  Ntk_NetworkForEachNode(network,gen,node) {
    var = Ntk_NodeReadVariable(node);
    numValues = Var_VariableReadNumValues(var);
    if (numValues > 2)
      return 1;
  }
  return 0;
}