#include "base/abc/abc.h"
#include "misc/vec/vec.h"

Include dependency graph for fretime.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	Flow_Data_t_

struct	NodeLag_T_

struct	InitConstraint_t_

struct	MinRegMan_t_

Macros
#define	DEBUG_CHECK

#define	MAX_DIST 30000
	DECLARATIONS ///.

#define	VISITED_E 0x001

#define	VISITED_R 0x002

#define	VISITED (VISITED_E \| VISITED_R)

#define	FLOW 0x004

#define	CROSS_BOUNDARY 0x008

#define	BLOCK 0x010

#define	INIT_0 0x020

#define	INIT_1 0x040

#define	INIT_CARE (INIT_0 \| INIT_1)

#define	CONSERVATIVE 0x080

#define	BLOCK_OR_CONS (BLOCK \| CONSERVATIVE)

#define	BIAS_NODE 0x100

#define	MAX(a, b)

#define	MIN(a, b)

#define	FDATA(x)

#define	FSET(x, y)

#define	FUNSET(x, y)

#define	FTEST(x, y)

#define	FTIMEEDGES(x)

#define	vprintf if (pManMR->fVerbose) printf

Typedefs
typedef struct Flow_Data_t_	Flow_Data_t

typedef struct NodeLag_T_	NodeLag_t

typedef struct InitConstraint_t_	InitConstraint_t

typedef struct MinRegMan_t_	MinRegMan_t

Functions
Abc_Ntk_t *	Abc_FlowRetime_MinReg (Abc_Ntk_t *pNtk, int fVerbose, int fComputeInitState, int fGuaranteeInitState, int fBlockConst, int fForward, int fBackward, int nMaxIters, int maxDelay, int fFastButConservative)
	FUNCTION DEFINITIONS ///.

void	print_node (Abc_Obj_t *pObj)

void	Abc_ObjBetterTransferFanout (Abc_Obj_t pFrom, Abc_Obj_t pTo, int complement)

int	Abc_FlowRetime_PushFlows (Abc_Ntk_t *pNtk, int fVerbose)

int	Abc_FlowRetime_IsAcrossCut (Abc_Obj_t pCur, Abc_Obj_t pNext)

void	Abc_FlowRetime_ClearFlows (int fClearAll)

int	Abc_FlowRetime_GetLag (Abc_Obj_t *pObj)

void	Abc_FlowRetime_SetLag (Abc_Obj_t *pObj, int lag)

void	Abc_FlowRetime_UpdateLags ()

void	Abc_ObjPrintNeighborhood (Abc_Obj_t *pObj, int depth)

Abc_Ntk_t *	Abc_FlowRetime_NtkSilentRestrash (Abc_Ntk_t *pNtk, int fCleanup)

int	dfsplain_e (Abc_Obj_t pObj, Abc_Obj_t pPred)

int	dfsplain_r (Abc_Obj_t pObj, Abc_Obj_t pPred)

void	dfsfast_preorder (Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///.

int	dfsfast_e (Abc_Obj_t pObj, Abc_Obj_t pPred)

int	dfsfast_r (Abc_Obj_t pObj, Abc_Obj_t pPred)

void	Abc_FlowRetime_PrintInitStateInfo (Abc_Ntk_t *pNtk)

void	Abc_FlowRetime_InitState (Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///.

void	Abc_FlowRetime_UpdateForwardInit (Abc_Ntk_t *pNtk)

void	Abc_FlowRetime_UpdateBackwardInit (Abc_Ntk_t *pNtk)

void	Abc_FlowRetime_SetupBackwardInit (Abc_Ntk_t *pNtk)

int	Abc_FlowRetime_SolveBackwardInit (Abc_Ntk_t *pNtk)

void	Abc_FlowRetime_ConstrainInit ()

void	Abc_FlowRetime_AddInitBias ()

void	Abc_FlowRetime_RemoveInitBias ()

void	Abc_FlowRetime_InitTiming (Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///.

void	Abc_FlowRetime_FreeTiming (Abc_Ntk_t *pNtk)

int	Abc_FlowRetime_RefineConstraints ()

void	Abc_FlowRetime_ConstrainConserv (Abc_Ntk_t *pNtk)

void	Abc_FlowRetime_ConstrainExact (Abc_Obj_t *pObj)

void	Abc_FlowRetime_ConstrainExactAll (Abc_Ntk_t *pNtk)

Variables
MinRegMan_t *	pManMR

Macro Definition Documentation

◆ BIAS_NODE

#define BIAS_NODE 0x100

Definition at line 57 of file fretime.h.

◆ BLOCK

#define BLOCK 0x010

Definition at line 51 of file fretime.h.

◆ BLOCK_OR_CONS

#define BLOCK_OR_CONS (BLOCK | CONSERVATIVE)

Definition at line 56 of file fretime.h.

◆ CONSERVATIVE

#define CONSERVATIVE 0x080

Definition at line 55 of file fretime.h.

◆ CROSS_BOUNDARY

#define CROSS_BOUNDARY 0x008

Definition at line 50 of file fretime.h.

◆ DEBUG_CHECK

#define DEBUG_CHECK

CFile****************************************************************

FileName [fretime.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Flow-based retiming package.]

Synopsis [Header file for retiming package.]

Author [Aaron Hurst]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - January 1, 2008.]

Revision [

Id: fretime.h,v 1.00 2008/01/01 00:00:00 ahurst Exp

]

Definition at line 36 of file fretime.h.

◆ FDATA

#define FDATA ( x )

Value:

(pManMR->pDataArray+Abc_ObjId(x))

pManMR

MinRegMan_t * pManMR

Definition fretMain.c:52

Definition at line 80 of file fretime.h.

◆ FLOW

#define FLOW 0x004

Definition at line 49 of file fretime.h.

◆ FSET

#define FSET	(		x,
			y )

Value:

FDATA(x)->mark |= y

FDATA

#define FDATA(x)

Definition fretime.h:80

Definition at line 81 of file fretime.h.

◆ FTEST

#define FTEST	(		x,
			y )

Value:

(FDATA(x)->mark & y)

Definition at line 83 of file fretime.h.

◆ FTIMEEDGES

#define FTIMEEDGES ( x )

Value:

&(pManMR->vTimeEdges[Abc_ObjId( x )])

Definition at line 84 of file fretime.h.

◆ FUNSET

#define FUNSET	(		x,
			y )

Value:

FDATA(x)->mark &= ~y

Definition at line 82 of file fretime.h.

◆ INIT_0

#define INIT_0 0x020

Definition at line 52 of file fretime.h.

◆ INIT_1

#define INIT_1 0x040

Definition at line 53 of file fretime.h.

◆ INIT_CARE

#define INIT_CARE (INIT_0 | INIT_1)

Definition at line 54 of file fretime.h.

◆ MAX

#define MAX	(		a,
			b )

Value:

((a)>(b)?(a):(b))

Definition at line 60 of file fretime.h.

◆ MAX_DIST

#define MAX_DIST 30000

DECLARATIONS ///.

Definition at line 43 of file fretime.h.

◆ MIN

#define MIN	(		a,
			b )

Value:

((a)<(b)?(a):(b))

Definition at line 61 of file fretime.h.

◆ VISITED

#define VISITED (VISITED_E | VISITED_R)

Definition at line 48 of file fretime.h.

◆ VISITED_E

#define VISITED_E 0x001

Definition at line 46 of file fretime.h.

◆ VISITED_R

#define VISITED_R 0x002

Definition at line 47 of file fretime.h.

◆ vprintf

#define vprintf if (pManMR->fVerbose) printf

Definition at line 138 of file fretime.h.

Typedef Documentation

◆ Flow_Data_t

typedef struct Flow_Data_t_ Flow_Data_t

◆ InitConstraint_t

typedef struct InitConstraint_t_ InitConstraint_t

◆ MinRegMan_t

typedef struct MinRegMan_t_ MinRegMan_t

◆ NodeLag_t

typedef struct NodeLag_T_ NodeLag_t

Function Documentation

◆ Abc_FlowRetime_AddInitBias()

void Abc_FlowRetime_AddInitBias ( )

Function*************************************************************

Synopsis [Adds nodes to bias against uninitializable cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 1218 of file fretInit.c.

                                   {
  Abc_Ntk_t *pNtk = pManMR->pNtk;
  Abc_Obj_t *pBiasNode, *pObj;
  InitConstraint_t *pConstraint;
  int i, j, id;
  const int nConstraints = Vec_PtrSize( pManMR->vInitConstraints );
 
  pManMR->pDataArray = ABC_REALLOC( Flow_Data_t, pManMR->pDataArray, pManMR->nNodes + (nConstraints*(pManMR->iteration+1)) );
  memset(pManMR->pDataArray + pManMR->nNodes, 0, sizeof(Flow_Data_t)*(nConstraints*(pManMR->iteration+1)));
 
  vprintf("\t\tcreating %d bias structures\n", nConstraints);
 
  Vec_PtrForEachEntry(InitConstraint_t*, pManMR->vInitConstraints, pConstraint, i ) {
    if (pConstraint->pBiasNode) continue;
    
 //   printf("\t\t\tbias %d...\n", i);
    pBiasNode = Abc_NtkCreateBlackbox( pNtk );
 
    Vec_IntForEachEntry( &pConstraint->vNodes, id, j ) {
      pObj = Abc_NtkObj(pNtk, id);
      Abc_FlowRetime_ConnectBiasNode(pBiasNode, pObj, Vec_IntEntry(&pConstraint->vLags, j));
    }
 
    // pConstraint->pBiasNode = pBiasNode;
  }
}

Here is the call graph for this function:

◆ Abc_FlowRetime_ClearFlows()

void Abc_FlowRetime_ClearFlows ( int fClearAll )

Function*************************************************************

Synopsis [Resets flow problem]

Description [If fClearAll is true, all marks will be cleared; this is typically appropriate after the circuit structure has been modified.]

SideEffects []

SeeAlso []

Definition at line 1087 of file fretMain.c.

                                                {
  int i;
 
  if (fClearAll)
    memset(pManMR->pDataArray, 0, sizeof(Flow_Data_t)*pManMR->nNodes);
  else {
    // clear only data related to flow problem
    for(i=0; i<pManMR->nNodes; i++) {
      pManMR->pDataArray[i].mark &= ~(VISITED | FLOW );
      pManMR->pDataArray[i].e_dist = 0;
      pManMR->pDataArray[i].r_dist = 0;
      pManMR->pDataArray[i].pred = NULL;
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_FlowRetime_ConstrainConserv()

void Abc_FlowRetime_ConstrainConserv ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Marks nodes with conservative constraints.]

Description []

SideEffects []

SeeAlso []

Definition at line 90 of file fretTime.c.

                                                         {  
  Abc_Obj_t *pObj;
  int i;
  void *pArray;
 
  // clear all exact constraints
  pManMR->nExactConstraints = 0;
  while( Vec_PtrSize( pManMR->vExactNodes )) {
    pObj = (Abc_Obj_t*)Vec_PtrPop( pManMR->vExactNodes );
    
    if ( Vec_PtrSize( FTIMEEDGES(pObj) )) {
      pArray =  Vec_PtrReleaseArray( FTIMEEDGES(pObj) );
      ABC_FREE( pArray );
    }
  }
 
#if !defined(IGNORE_TIMING)
  if (pManMR->fIsForward) {
    Abc_FlowRetime_ConstrainConserv_forw(pNtk);
  } else {
    Abc_FlowRetime_ConstrainConserv_back(pNtk);
  }
#endif
 
  Abc_NtkForEachObj( pNtk, pObj, i)
    assert( !Vec_PtrSize(FTIMEEDGES(pObj)) );
}

◆ Abc_FlowRetime_ConstrainExact()

void Abc_FlowRetime_ConstrainExact ( Abc_Obj_t * pObj )

Function*************************************************************

Synopsis [Introduces exact timing constraints for a node.]

Description []

SideEffects []

SeeAlso []

Definition at line 407 of file fretTime.c.

                                                       {
 
  if (FTEST( pObj, CONSERVATIVE )) {
    pManMR->nConservConstraints--;
    FUNSET( pObj, CONSERVATIVE );
  }
 
#if !defined(IGNORE_TIMING)
  if (pManMR->fIsForward) {
    Abc_FlowRetime_ConstrainExact_forw(pObj);
  } else {
    Abc_FlowRetime_ConstrainExact_back(pObj);
  }
#endif
}

Here is the caller graph for this function:

◆ Abc_FlowRetime_ConstrainExactAll()

void Abc_FlowRetime_ConstrainExactAll ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Introduces all exact timing constraints in a network]

Description []

SideEffects []

SeeAlso []

Definition at line 584 of file fretTime.c.

                                                          {
  int i;
  Abc_Obj_t *pObj;
  void *pArray;
  
  // free existing constraints
  Abc_NtkForEachObj( pNtk, pObj, i )    
    if ( Vec_PtrSize( FTIMEEDGES(pObj) )) {
      pArray =  Vec_PtrReleaseArray( FTIMEEDGES(pObj) );
      ABC_FREE( pArray );
    }
  pManMR->nExactConstraints = 0;
  
  // generate all constraints
  Abc_NtkForEachObj(pNtk, pObj, i)
    if (!Abc_ObjIsLatch(pObj) && FTEST( pObj, CONSERVATIVE ) && !FTEST( pObj, BLOCK ))
      if (!Vec_PtrSize( FTIMEEDGES( pObj ) ))
        Abc_FlowRetime_ConstrainExact( pObj );
}

Here is the call graph for this function:

◆ Abc_FlowRetime_ConstrainInit()

void Abc_FlowRetime_ConstrainInit ( )

Function*************************************************************

Synopsis [Constrains backward retiming for initializability.]

Description []

SideEffects []

SeeAlso []

Definition at line 1023 of file fretInit.c.

                                     {
  Vec_Ptr_t *vNodes;
  int low, high, mid;
  int i, n, lag;
  Abc_Obj_t *pObj = NULL, *pOrigObj;
  InitConstraint_t *pConstraint = ABC_ALLOC( InitConstraint_t, 1 );
 
  memset( pConstraint, 0, sizeof(InitConstraint_t) );
 
  assert(pManMR->pInitNtk);
 
  vprintf("\tsearch for initial state conflict...\n");
 
  vNodes = Abc_NtkDfs(pManMR->pInitNtk, 0);
  n = Vec_PtrSize(vNodes);
  // also add PIs to vNodes
  Abc_NtkForEachPi(pManMR->pInitNtk, pObj, i) 
    Vec_PtrPush(vNodes, pObj);
  Vec_PtrReorder(vNodes, n);
 
#if defined(DEBUG_CHECK)
    assert(!Abc_FlowRetime_PartialSat( vNodes, 0 ));
#endif
 
  // grow initialization constraint
  do {
    vprintf("\t\t");
 
    // find element to add to set...
    low = 0, high = Vec_PtrSize(vNodes);
    while (low != high-1) {
      mid = (low + high) >> 1;
      
      if (!Abc_FlowRetime_PartialSat( vNodes, mid )) {
        low = mid;
        vprintf("-");
      } else {
        high = mid;
        vprintf("*");
      }
      fflush(stdout);
    }
      
#if defined(DEBUG_CHECK)
    assert(Abc_FlowRetime_PartialSat( vNodes, high ));
    assert(!Abc_FlowRetime_PartialSat( vNodes, low ));
#endif
    
    // mark its TFO
    pObj = (Abc_Obj_t*)Vec_PtrEntry( vNodes, low );
    Abc_NtkMarkCone_rec( pObj, 1 );
    vprintf("   conflict term = %d ", low);
 
#if 0
    printf("init ------\n");
    Abc_ObjPrint(stdout, pObj);
    printf("\n");
    Abc_ObjPrintNeighborhood( pObj, 1 );
    printf("------\n");
#endif
 
    // add node to constraint
    Abc_FlowRetime_GetInitToOrig( pObj, &pOrigObj, &lag );
    assert(pOrigObj);
    vprintf(" <=> %d/%d\n", Abc_ObjId(pOrigObj), lag);
 
#if 0    
    printf("orig ------\n");
    Abc_ObjPrint(stdout, pOrigObj);
    printf("\n");
    Abc_ObjPrintNeighborhood( pOrigObj, 1 );
    printf("------\n");
#endif
    Vec_IntPush( &pConstraint->vNodes, Abc_ObjId(pOrigObj) );
    Vec_IntPush( &pConstraint->vLags, lag );
 
  } while (Abc_FlowRetime_PartialSat( vNodes, Vec_PtrSize(vNodes) ));
 
  pConstraint->pBiasNode = NULL;
 
  // add constraint
  Vec_PtrPush( pManMR->vInitConstraints, pConstraint );
 
  // clear marks
  Abc_NtkForEachObj( pManMR->pInitNtk, pObj, i)
    pObj->fMarkA = 0;
 
  // free
  Vec_PtrFree( vNodes );
}

Here is the call graph for this function:

◆ Abc_FlowRetime_FreeTiming()

void Abc_FlowRetime_FreeTiming ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Deallocates exact constraints.]

Description []

SideEffects []

SeeAlso []

Definition at line 617 of file fretTime.c.

                                                  {
  Abc_Obj_t *pObj;
  void *pArray;
 
  while( Vec_PtrSize( pManMR->vExactNodes )) {
    pObj = (Abc_Obj_t*)Vec_PtrPop( pManMR->vExactNodes );
    
    if ( Vec_PtrSize( FTIMEEDGES(pObj) )) {
      pArray =  Vec_PtrReleaseArray( FTIMEEDGES(pObj) );
      ABC_FREE( pArray );
    }
  }
 
  Vec_PtrFree(pManMR->vExactNodes);
  ABC_FREE( pManMR->vTimeEdges );
}

Here is the caller graph for this function:

◆ Abc_FlowRetime_GetLag()

int Abc_FlowRetime_GetLag ( Abc_Obj_t * pObj )

Function*************************************************************

Synopsis [Gets lag value of a node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1323 of file fretMain.c.

                                         {
  assert( !Abc_ObjIsLatch(pObj) );
  assert( (int)Abc_ObjId(pObj) < Vec_IntSize(pManMR->vLags) );
 
  return Vec_IntEntry(pManMR->vLags, Abc_ObjId(pObj));
}

◆ Abc_FlowRetime_InitState()

void Abc_FlowRetime_InitState ( Abc_Ntk_t * pNtk )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Updates initial state information.]

Description [Assumes latch boxes in original position, latches in new positions.]

SideEffects []

SeeAlso []

Definition at line 75 of file fretInit.c.

                                             {
 
  if (!pManMR->fComputeInitState) return;
 
  if (pManMR->fIsForward)
    Abc_FlowRetime_UpdateForwardInit( pNtk );
  else {
    Abc_FlowRetime_UpdateBackwardInit( pNtk );
  }
}

Here is the call graph for this function:

◆ Abc_FlowRetime_InitTiming()

void Abc_FlowRetime_InitTiming ( Abc_Ntk_t * pNtk )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Initializes timing]

Description []

SideEffects []

SeeAlso []

Definition at line 67 of file fretTime.c.

                                                  {
 
  pManMR->nConservConstraints = pManMR->nExactConstraints = 0;
 
  pManMR->vExactNodes = Vec_PtrAlloc(1000);
 
  pManMR->vTimeEdges = ABC_ALLOC( Vec_Ptr_t, Abc_NtkObjNumMax(pNtk)+1 );
  assert(pManMR->vTimeEdges);
  memset(pManMR->vTimeEdges, 0, (Abc_NtkObjNumMax(pNtk)+1) * sizeof(Vec_Ptr_t) );
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_FlowRetime_IsAcrossCut()

int Abc_FlowRetime_IsAcrossCut	(	Abc_Obj_t *	pObj,
		Abc_Obj_t *	pNext )

Function*************************************************************

Synopsis [Returns true is a connection spans the min-cut.]

Description [pNext is a direct fanout of pObj.]

SideEffects []

SeeAlso []

Definition at line 1054 of file fretMain.c.

                                                                {
 
  if (FTEST(pObj, VISITED_R) && !FTEST(pObj, VISITED_E)) {
    if (pManMR->fIsForward) {
      if (!FTEST(pNext, VISITED_R) || 
          (FTEST(pNext, BLOCK_OR_CONS) & pManMR->constraintMask)|| 
          FTEST(pNext, CROSS_BOUNDARY) || 
          Abc_ObjIsLatch(pNext))
        return 1;
    } else {
      if (FTEST(pNext, VISITED_E) ||
          FTEST(pNext, CROSS_BOUNDARY))
        return 1;
    }
  }
  
  return 0;
}

◆ Abc_FlowRetime_MinReg()

Abc_Ntk_t * Abc_FlowRetime_MinReg	(	Abc_Ntk_t *	pNtk,
		int	fVerbose,
		int	fComputeInitState,
		int	fGuaranteeInitState,
		int	fBlockConst,
		int	fForwardOnly,
		int	fBackwardOnly,
		int	nMaxIters,
		int	maxDelay,
		int	fFastButConservative )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Performs minimum-register retiming.]

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file fretMain.c.

                                                                {
 
  int i;
  Abc_Obj_t   *pObj, *pNext;
  InitConstraint_t *pData;
 
  // create manager
  pManMR = ABC_ALLOC( MinRegMan_t, 1 );
 
  pManMR->pNtk = pNtk;
  pManMR->fVerbose = fVerbose;
  pManMR->fComputeInitState = fComputeInitState;
  pManMR->fGuaranteeInitState = fGuaranteeInitState;
  pManMR->fBlockConst = fBlockConst;
  pManMR->fForwardOnly = fForwardOnly;
  pManMR->fBackwardOnly = fBackwardOnly;
  pManMR->nMaxIters = nMaxIters;
  pManMR->maxDelay = maxDelay;
  pManMR->fComputeInitState = fComputeInitState;
  pManMR->fConservTimingOnly = fFastButConservative;
  pManMR->vNodes = Vec_PtrAlloc(100);
  pManMR->vInitConstraints = Vec_PtrAlloc(2);
  pManMR->pInitNtk = NULL;
  pManMR->pInitToOrig = NULL;
  pManMR->sizeInitToOrig = 0;
 
  vprintf("Flow-based minimum-register retiming...\n");  
 
  if (!Abc_NtkHasOnlyLatchBoxes(pNtk)) {
    printf("\tERROR: Can not retime with black/white boxes\n");
    return pNtk;
  }
 
  if (maxDelay) {
    vprintf("\tmax delay constraint = %d\n", maxDelay);
    if (maxDelay < (i = Abc_NtkLevel(pNtk))) {
      printf("ERROR: max delay constraint (%d) must be > current max delay (%d)\n", maxDelay, i);
      return pNtk;
    }
  }
 
  // print info about type of network
  vprintf("\tnetlist type = ");
  if (Abc_NtkIsNetlist( pNtk )) { vprintf("netlist/"); }
  else if (Abc_NtkIsLogic( pNtk )) { vprintf("logic/"); }
  else if (Abc_NtkIsStrash( pNtk )) { vprintf("strash/"); }
  else { vprintf("***unknown***/"); }
  if (Abc_NtkHasSop( pNtk )) { vprintf("sop\n"); }
  else if (Abc_NtkHasBdd( pNtk )) { vprintf("bdd\n"); }
  else if (Abc_NtkHasAig( pNtk )) { vprintf("aig\n"); }
  else if (Abc_NtkHasMapping( pNtk )) { vprintf("mapped\n"); }
  else { vprintf("***unknown***\n"); }
 
  vprintf("\tinitial reg count = %d\n", Abc_NtkLatchNum(pNtk));
  vprintf("\tinitial levels = %d\n", Abc_NtkLevel(pNtk));
 
  // remove bubbles from latch boxes
  if (pManMR->fVerbose) Abc_FlowRetime_PrintInitStateInfo(pNtk);
  vprintf("\tpushing bubbles out of latch boxes\n");
  Abc_NtkForEachLatch( pNtk, pObj, i )
    Abc_FlowRetime_RemoveLatchBubbles(pObj);
  if (pManMR->fVerbose) Abc_FlowRetime_PrintInitStateInfo(pNtk);
 
  // check for box inputs/outputs
  Abc_NtkForEachLatch( pNtk, pObj, i ) {
    assert(Abc_ObjFaninNum(pObj) == 1);
    assert(Abc_ObjFanoutNum(pObj) == 1);
    assert(!Abc_ObjFaninC0(pObj));
 
    pNext = Abc_ObjFanin0(pObj);
    assert(Abc_ObjIsBi(pNext));
    assert(Abc_ObjFaninNum(pNext) <= 1);
    if(Abc_ObjFaninNum(pNext) == 0) // every Bi should have a fanin
      Abc_FlowRetime_AddDummyFanin( pNext );
 
    pNext = Abc_ObjFanout0(pObj);
    assert(Abc_ObjIsBo(pNext));
    assert(Abc_ObjFaninNum(pNext) == 1);
    assert(!Abc_ObjFaninC0(pNext));
  }
 
  pManMR->nLatches = Abc_NtkLatchNum( pNtk );
  pManMR->nNodes = Abc_NtkObjNumMax( pNtk )+1;
   
  // build histogram
  pManMR->vSinkDistHist = Vec_IntStart( pManMR->nNodes*2+10 );
 
  // initialize timing
  if (maxDelay)
    Abc_FlowRetime_InitTiming( pNtk );
 
  // create lag and Flow_Data structure
  pManMR->vLags = Vec_IntStart(pManMR->nNodes);
  memset(pManMR->vLags->pArray, 0, sizeof(int)*pManMR->nNodes);
 
  pManMR->pDataArray = ABC_ALLOC( Flow_Data_t, pManMR->nNodes );
  Abc_FlowRetime_ClearFlows( 1 );
 
  // main loop!
  pNtk = Abc_FlowRetime_MainLoop();
 
  // cleanup node fields
  Abc_NtkForEachObj( pNtk, pObj, i ) {
    // if not computing init state, set all latches to DC
    if (!fComputeInitState && Abc_ObjIsLatch(pObj))
      Abc_LatchSetInitDc(pObj);
  }
 
  // deallocate space
  ABC_FREE( pManMR->pDataArray );
  if (pManMR->pInitToOrig) ABC_FREE( pManMR->pInitToOrig );
  if (pManMR->vNodes) Vec_PtrFree(pManMR->vNodes);
  if (pManMR->vLags) Vec_IntFree(pManMR->vLags);
  if (pManMR->vSinkDistHist) Vec_IntFree(pManMR->vSinkDistHist);
  if (pManMR->maxDelay) Abc_FlowRetime_FreeTiming( pNtk );
  while( Vec_PtrSize( pManMR->vInitConstraints )) {
    pData = (InitConstraint_t*)Vec_PtrPop( pManMR->vInitConstraints );
    //assert( pData->pBiasNode );
    //Abc_NtkDeleteObj( pData->pBiasNode );
    ABC_FREE( pData->vNodes.pArray );
    ABC_FREE( pData );
  }
  ABC_FREE( pManMR->vInitConstraints );
 
  // restrash if necessary
  if (Abc_NtkIsStrash(pNtk)) {
    Abc_NtkReassignIds( pNtk );
    pNtk = Abc_FlowRetime_NtkSilentRestrash( pNtk, 1 );
  }
  
  vprintf("\tfinal reg count = %d\n", Abc_NtkLatchNum(pNtk));
  vprintf("\tfinal levels = %d\n", Abc_NtkLevel(pNtk));
 
#if defined(DEBUG_CHECK)
  Abc_NtkDoCheck( pNtk );
#endif
 
  // free manager
  ABC_FREE( pManMR );
 
  return pNtk;
}

Here is the call graph for this function:

◆ Abc_FlowRetime_NtkSilentRestrash()

Abc_Ntk_t * Abc_FlowRetime_NtkSilentRestrash	(	Abc_Ntk_t *	pNtk,
		int	fCleanup )

Function*************************************************************

Synopsis [Silent restrash.]

Description [Same functionality as Abc_NtkRestrash but w/o warnings.]

SideEffects []

SeeAlso []

Definition at line 1184 of file fretMain.c.

{
    Abc_Ntk_t * pNtkAig;
    Abc_Obj_t * pObj;
    int i, nNodes;//, RetValue;
    assert( Abc_NtkIsStrash(pNtk) );
    // start the new network (constants and CIs of the old network will point to the their counterparts in the new network)
    pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
    // restrash the nodes (assuming a topological order of the old network)
    Abc_NtkForEachNode( pNtk, pObj, i )
        pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pNtkAig->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
    // finalize the network
    Abc_NtkFinalize( pNtk, pNtkAig );
    // perform cleanup if requested
    if ( fCleanup )
      nNodes = Abc_AigCleanup((Abc_Aig_t *)pNtkAig->pManFunc);
    // duplicate EXDC 
    if ( pNtk->pExdc )
      pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkAig ) )
      {
        printf( "Abc_NtkStrash: The network check has failed.\n" );
        Abc_NtkDelete( pNtkAig );
        return NULL;
      }
    return pNtkAig;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_FlowRetime_PrintInitStateInfo()

void Abc_FlowRetime_PrintInitStateInfo ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Prints initial state information.]

Description [Prints distribution of 0,1,and X initial states.]

SideEffects []

SeeAlso []

Definition at line 133 of file fretInit.c.

                                                      {
  int i, n0=0, n1=0, nDC=0, nOther=0;
  Abc_Obj_t *pLatch;
 
  Abc_NtkForEachLatch( pNtk, pLatch, i ) {
    if (Abc_LatchIsInit0(pLatch)) n0++;
    else if (Abc_LatchIsInit1(pLatch)) n1++;
    else if (Abc_LatchIsInitDc(pLatch)) nDC++;
    else nOther++;
  }     
 
  printf("\tinitial states {0,1,x} = {%d, %d, %d}", n0, n1, nDC);
  if (nOther)
    printf(" + %d UNKNOWN", nOther);
  printf("\n");
}

Here is the caller graph for this function:

◆ Abc_FlowRetime_PushFlows()

int Abc_FlowRetime_PushFlows	(	Abc_Ntk_t *	pNtk,
		int	fVerbose )

Function*************************************************************

Synopsis [Computes maximum flow.]

Description []

SideEffects [Leaves VISITED flags on source-reachable nodes.]

SeeAlso []

Definition at line 479 of file fretMain.c.

                                                           {
  int i, j, flow = 0, last, srcDist = 0;
  Abc_Obj_t   *pObj, *pObj2;
//  int clk = clock();
 
  pManMR->constraintMask |= BLOCK;
 
  pManMR->fSinkDistTerminate = 0;
  dfsfast_preorder( pNtk );
 
  // (i) fast max-flow computation
  while(!pManMR->fSinkDistTerminate && srcDist < MAX_DIST) {
    srcDist = MAX_DIST;
    Abc_NtkForEachLatch( pNtk, pObj, i )
      if (FDATA(pObj)->e_dist)    
        srcDist = MIN(srcDist, (int)FDATA(pObj)->e_dist);
    
    Abc_NtkForEachLatch( pNtk, pObj, i ) {
      if (srcDist == (int)FDATA(pObj)->e_dist &&
          dfsfast_e( pObj, NULL )) {
#ifdef DEBUG_PRINT_FLOWS
        printf("\n\n");
#endif
        flow++;
      }
    }
  }
 
  if (fVerbose) vprintf("\t\tmax-flow1 = %d \t", flow);
 
  // (ii) complete max-flow computation
  // also, marks source-reachable nodes
  do {
    last = flow;
    Abc_NtkForEachLatch( pNtk, pObj, i ) {
      if (dfsplain_e( pObj, NULL )) {
#ifdef DEBUG_PRINT_FLOWS
        printf("\n\n");
#endif
        flow++;
        Abc_NtkForEachObj( pNtk, pObj2, j )
          FUNSET( pObj2, VISITED );
      }
    }
  } while (flow > last);
  
  if (fVerbose) vprintf("max-flow2 = %d\n", flow);
 
//  PRT( "time", clock() - clk );
  return flow;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_FlowRetime_RefineConstraints()

int Abc_FlowRetime_RefineConstraints ( )

Function*************************************************************

Synopsis [Main timing-constrained routine.]

Description [Refines constraints that are limiting area improvement. These are identified by computing the min-cuts both with and without the conservative constraints: these two situation represent an over- and under-constrained version of the timing.]

SideEffects []

SeeAlso []

Definition at line 693 of file fretTime.c.

                                        {
  Abc_Ntk_t *pNtk = pManMR->pNtk;
  int i, flow, count = 0;
  Abc_Obj_t *pObj;
  int maxTighten = 99999;
 
  vprintf("\t\tsubiter %d : constraints = {cons, exact} = %d, %d\n", 
         pManMR->subIteration, pManMR->nConservConstraints, pManMR->nExactConstraints);
 
  // 1. overconstrained
  pManMR->constraintMask = BLOCK | CONSERVATIVE;
  vprintf("\t\trefinement: over ");
  fflush(stdout);
  flow = Abc_FlowRetime_PushFlows( pNtk, 0 );
  vprintf("= %d ", flow);
 
  // remember nodes
  if (pManMR->fIsForward) {
    Abc_NtkForEachObj( pNtk, pObj, i )
      if (!FTEST(pObj, VISITED_R))
        pObj->fMarkC = 1;
  } else {
    Abc_NtkForEachObj( pNtk, pObj, i )
      if (!FTEST(pObj, VISITED_E))
        pObj->fMarkC = 1;
  }
 
  if (pManMR->fConservTimingOnly) {
    vprintf(" done\n");
    return 0;
  }
 
  // 2. underconstrained
  pManMR->constraintMask = BLOCK;
  Abc_FlowRetime_ClearFlows( 0 );
  vprintf("under = ");
  fflush(stdout);
  flow = Abc_FlowRetime_PushFlows( pNtk, 0 );
  vprintf("%d refined nodes = ", flow);
  fflush(stdout);
 
  // find area-limiting constraints
  if (pManMR->fIsForward) {
    Abc_NtkForEachObj( pNtk, pObj, i ) {
      if (pObj->fMarkC &&
          FTEST(pObj, VISITED_R) &&
          FTEST(pObj, CONSERVATIVE) && 
          count < maxTighten) {
        count++;
        Abc_FlowRetime_ConstrainExact( pObj );
      }
      pObj->fMarkC = 0;
    }
  } else {
    Abc_NtkForEachObj( pNtk, pObj, i ) {
      if (pObj->fMarkC &&
          FTEST(pObj, VISITED_E) &&
          FTEST(pObj, CONSERVATIVE) &&
          count < maxTighten) {
        count++;
        Abc_FlowRetime_ConstrainExact( pObj );
      }
      pObj->fMarkC = 0;
    }
  }
  
  vprintf("%d\n", count);
  
  return (count > 0);
}

Here is the call graph for this function:

◆ Abc_FlowRetime_RemoveInitBias()

void Abc_FlowRetime_RemoveInitBias ( )

Function*************************************************************

Synopsis [Removes nodes to bias against uninitializable cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 1126 of file fretInit.c.

                                      {
  // Abc_Ntk_t *pNtk = pManMR->pNtk;
  Abc_Obj_t *pBiasNode;
  InitConstraint_t *pConstraint;
  int i;
 
  Vec_PtrForEachEntry( InitConstraint_t *, pManMR->vInitConstraints, pConstraint, i ) {
    pBiasNode = pConstraint->pBiasNode;
    pConstraint->pBiasNode = NULL;
 
    if (pBiasNode)
      Abc_NtkDeleteObj(pBiasNode);
  }
}

Here is the call graph for this function:

◆ Abc_FlowRetime_SetLag()

void Abc_FlowRetime_SetLag	(	Abc_Obj_t *	pObj,
		int	lag )

Function*************************************************************

Synopsis [Sets lag value of a node.]

Description []

SideEffects []

SeeAlso []

Definition at line 1342 of file fretMain.c.

                                                  {
  assert( Abc_ObjIsNode(pObj) );
  assert( (int)Abc_ObjId(pObj) < Vec_IntSize(pManMR->vLags) );
 
  Vec_IntWriteEntry(pManMR->vLags, Abc_ObjId(pObj), lag);
}

◆ Abc_FlowRetime_SetupBackwardInit()

void Abc_FlowRetime_SetupBackwardInit ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Sets up backward initial state computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 489 of file fretInit.c.

                                                          {
  Abc_Obj_t *pLatch, *pObj, *pPi;
  int i;
  Vec_Ptr_t *vObj = Vec_PtrAlloc(100);
 
  // create the network used for the initial state computation
  if (Abc_NtkIsStrash(pNtk)) {
    pManMR->pInitNtk = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
  } else if (Abc_NtkHasMapping(pNtk))
    pManMR->pInitNtk = Abc_NtkAlloc( pNtk->ntkType, ABC_FUNC_SOP, 1 );
  else
    pManMR->pInitNtk = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 );
 
  // mitre inputs
  Abc_NtkForEachLatch( pNtk, pLatch, i ) {
    // map latch to initial state network
    pPi = Abc_NtkCreatePi( pManMR->pInitNtk );
 
    // DEBUG
    // printf("setup : mapping latch %d to PI %d\n", pLatch->Id, pPi->Id);
 
    // has initial state requirement?
    if (Abc_LatchIsInit0(pLatch)) {
      pObj = Abc_NtkCreateNodeInv( pManMR->pInitNtk, pPi );
      Vec_PtrPush(vObj, pObj);
    }
    else if (Abc_LatchIsInit1(pLatch)) {
      Vec_PtrPush(vObj, pPi);
    }
    
    Abc_ObjSetData( pLatch, pPi );     // if not verifying init state
    // FDATA(pLatch)->pInitObj = pPi;  // if verifying init state
  }
 
  // are there any nodes not DC?
  if (!Vec_PtrSize(vObj)) {
    pManMR->fSolutionIsDc = 1;
    return;
  } else 
    pManMR->fSolutionIsDc = 0;
 
  // mitre output
 
  // create n-input AND gate
  pObj = Abc_NtkCreateNodeAnd( pManMR->pInitNtk, vObj );
 
  Abc_ObjAddFanin( Abc_NtkCreatePo( pManMR->pInitNtk ), pObj );
 
  Vec_PtrFree( vObj );
}

Here is the call graph for this function:

◆ Abc_FlowRetime_SolveBackwardInit()

int Abc_FlowRetime_SolveBackwardInit ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Solves backward initial state computation.]

Description []

SideEffects [Sets object copies in init ntk.]

SeeAlso []

Definition at line 552 of file fretInit.c.

                                                         {
  int i;
  Abc_Obj_t *pObj, *pInitObj;
  Vec_Ptr_t *vDelete = Vec_PtrAlloc(0);
  Abc_Ntk_t *pSatNtk;
  int result;
 
  assert(pManMR->pInitNtk);
 
  // is the solution entirely DC's?
  if (pManMR->fSolutionIsDc) {
    Vec_PtrFree(vDelete);
    Abc_NtkForEachLatch( pNtk, pObj, i ) Abc_LatchSetInitDc( pObj );
    vprintf("\tno init state computation: all-don't-care solution\n");
    return 1;
  }
 
  // check that network is combinational
  Abc_NtkForEachObj( pManMR->pInitNtk, pObj, i ) {
    assert(!Abc_ObjIsLatch(pObj));
    assert(!Abc_ObjIsBo(pObj));
    assert(!Abc_ObjIsBi(pObj));
  }
  
  // delete superfluous nodes
  while(Vec_PtrSize( vDelete )) {
    pObj = (Abc_Obj_t *)Vec_PtrPop( vDelete );
    Abc_NtkDeleteObj( pObj );
  }
  Vec_PtrFree(vDelete);
 
  // do some final cleanup on the network
  Abc_NtkAddDummyPoNames(pManMR->pInitNtk);
  Abc_NtkAddDummyPiNames(pManMR->pInitNtk);
  if (Abc_NtkIsLogic(pManMR->pInitNtk))
    Abc_NtkCleanup(pManMR->pInitNtk, 0);
 
#if defined(DEBUG_PRINT_INIT_NTK)
  Abc_NtkLevelReverse( pManMR->pInitNtk );
  Abc_NtkForEachObj( pManMR->pInitNtk, pObj, i ) 
    if (Abc_ObjLevel( pObj ) < 2)
      Abc_ObjPrint(stdout, pObj);
#endif
  
  vprintf("\tsolving for init state (%d nodes)... ", Abc_NtkObjNum(pManMR->pInitNtk));
  fflush(stdout);
#ifdef ABC_USE_CUDD
  // convert SOPs to BDD
  if (Abc_NtkHasSop(pManMR->pInitNtk))
    Abc_NtkSopToBdd( pManMR->pInitNtk );
  // convert AIGs to BDD
  if (Abc_NtkHasAig(pManMR->pInitNtk))
    Abc_NtkAigToBdd( pManMR->pInitNtk );
#else
  // convert SOPs to AIG
  if (Abc_NtkHasSop(pManMR->pInitNtk))
    Abc_NtkSopToAig( pManMR->pInitNtk );
#endif
  pSatNtk = pManMR->pInitNtk;
  
  // solve
  result = Abc_NtkMiterSat( pSatNtk, (ABC_INT64_T)500000, (ABC_INT64_T)50000000, 0, NULL, NULL );
 
  if (!result) { 
    vprintf("SUCCESS\n");
  } else  {    
    vprintf("FAILURE\n");
    return 0;
  }
 
  // clear initial values, associate PIs to latches
  Abc_NtkForEachPi( pManMR->pInitNtk, pInitObj, i ) Abc_ObjSetCopy( pInitObj, NULL );
  Abc_NtkForEachLatch( pNtk, pObj, i ) {
    pInitObj = (Abc_Obj_t*)Abc_ObjData( pObj );
    assert( Abc_ObjIsPi( pInitObj ));
    Abc_ObjSetCopy( pInitObj, pObj );
    Abc_LatchSetInitNone( pObj );
 
    // DEBUG
    // printf("solve : getting latch %d from PI %d\n", pObj->Id, pInitObj->Id);
  }
 
  // copy solution from PIs to latches
  assert(pManMR->pInitNtk->pModel);
  Abc_NtkForEachPi( pManMR->pInitNtk, pInitObj, i ) {
    if ((pObj = Abc_ObjCopy( pInitObj ))) {
      if ( pManMR->pInitNtk->pModel[i] )
        Abc_LatchSetInit1( pObj );
      else
        Abc_LatchSetInit0( pObj );
    }
  }
 
#if defined(DEBUG_CHECK)
  // check that all latches have initial state
  Abc_NtkForEachLatch( pNtk, pObj, i ) assert( !Abc_LatchIsInitNone( pObj ) );
#endif
 
  return 1;
}

Here is the call graph for this function:

◆ Abc_FlowRetime_UpdateBackwardInit()

void Abc_FlowRetime_UpdateBackwardInit ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Updates backward initial state computation problem.]

Description [Assumes box outputs in old positions stored w/ init values.]

SideEffects []

SeeAlso []

Definition at line 665 of file fretInit.c.

                                                           {
  Abc_Obj_t *pOrigObj,  *pInitObj;
  Vec_Ptr_t *vBo = Vec_PtrAlloc(100);
  Vec_Ptr_t *vPi = Vec_PtrAlloc(100);
  Abc_Ntk_t *pInitNtk = pManMR-> pInitNtk;
  Abc_Obj_t *pBuf;
  int i;
 
  // remove PIs from network (from BOs)
  Abc_NtkForEachObj( pNtk, pOrigObj, i )
    if (Abc_ObjIsBo(pOrigObj)) {
      pInitObj = FDATA(pOrigObj)->pInitObj;
      assert(Abc_ObjIsPi(pInitObj));
 
      // DEBUG
      // printf("update : freeing PI %d\n", pInitObj->Id);
      
      // create a buffer instead
      pBuf = Abc_NtkCreateNodeBuf( pInitNtk, NULL );
      Abc_FlowRetime_ClearInitToOrig( pBuf );
 
      Abc_ObjBetterTransferFanout( pInitObj, pBuf, 0 );
      FDATA(pOrigObj)->pInitObj = pBuf;
      pOrigObj->fMarkA = 1;
 
      Vec_PtrPush(vBo, pOrigObj);
      Vec_PtrPush(vPi, pInitObj);
    }
  
  // check that PIs are all free
  Abc_NtkForEachPi( pInitNtk, pInitObj, i) {
    assert( Abc_ObjFanoutNum( pInitObj ) == 0);
  }
 
  // add PIs to to latches
  Abc_NtkForEachLatch( pNtk, pOrigObj, i ) {
    assert(Vec_PtrSize(vPi) > 0);
    pInitObj = (Abc_Obj_t*)Vec_PtrPop(vPi);
 
    // DEBUG
    // printf("update : mapping latch %d to PI %d\n", pOrigObj->Id, pInitObj->Id);
 
    pOrigObj->fMarkA = pOrigObj->fMarkB = 1;
    FDATA(pOrigObj)->pInitObj = pInitObj;
    Abc_ObjSetData(pOrigObj, pInitObj);
  }  
 
  // recursively build init network
  Vec_PtrForEachEntry( Abc_Obj_t *, vBo, pOrigObj, i )
    Abc_FlowRetime_UpdateBackwardInit_rec( pOrigObj );
  
  // clear flags
  Abc_NtkForEachObj( pNtk, pOrigObj, i )
    pOrigObj->fMarkA = pOrigObj->fMarkB = 0;
 
  // deallocate
  Vec_PtrFree( vBo );
  Vec_PtrFree( vPi );
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_FlowRetime_UpdateForwardInit()

void Abc_FlowRetime_UpdateForwardInit ( Abc_Ntk_t * pNtk )

Function*************************************************************

Synopsis [Computes initial state after forward retiming.]

Description [Assumes box outputs in old positions stored w/ init values. Uses three-value simulation to preserve don't cares.]

SideEffects []

SeeAlso []

Definition at line 163 of file fretInit.c.

                                                          {
  Abc_Obj_t *pObj, *pFanin;
  int i;
 
  vprintf("\t\tupdating init state\n");
 
  Abc_NtkIncrementTravId( pNtk );
 
  Abc_NtkForEachLatch( pNtk, pObj, i ) {
    pFanin = Abc_ObjFanin0(pObj);
    Abc_FlowRetime_UpdateForwardInit_rec( pFanin );
 
    if (FTEST(pFanin, INIT_0))
      Abc_LatchSetInit0( pObj );
    else if (FTEST(pFanin, INIT_1))
      Abc_LatchSetInit1( pObj );
    else
      Abc_LatchSetInitDc( pObj );
  }
}

Here is the caller graph for this function:

◆ Abc_FlowRetime_UpdateLags()

void Abc_FlowRetime_UpdateLags ( )

Function*************************************************************

Synopsis [Updates lag values.]

Description []

SideEffects []

SeeAlso []

Definition at line 1294 of file fretMain.c.

                             {
  Abc_Obj_t *pObj, *pNext;
  int i, j;
 
  Abc_NtkIncrementTravId( pManMR->pNtk );
 
  Abc_NtkForEachLatch( pManMR->pNtk, pObj, i )
    if (pManMR->fIsForward) {
      Abc_ObjForEachFanin( pObj, pNext, j )          
        Abc_FlowRetime_UpdateLags_forw_rec( pNext );
    } else {
      Abc_ObjForEachFanout( pObj, pNext, j )          
        Abc_FlowRetime_UpdateLags_back_rec( pNext );
    }
}

◆ Abc_ObjBetterTransferFanout()

void Abc_ObjBetterTransferFanout	(	Abc_Obj_t *	pFrom,
		Abc_Obj_t *	pTo,
		int	complement )

Function*************************************************************

Synopsis [Transfers fanout.]

Description [Does not produce an error if there is no fanout. Complements as necessary.]

SideEffects []

SeeAlso []

Definition at line 1032 of file fretMain.c.

                                                                                  {
  Abc_Obj_t *pNext;
  
  while(Abc_ObjFanoutNum(pFrom) > 0) {
    pNext = Abc_ObjFanout0(pFrom);
    Abc_ObjPatchFanin( pNext, pFrom, Abc_ObjNotCond(pTo, complement) );
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_ObjPrintNeighborhood()

void Abc_ObjPrintNeighborhood	(	Abc_Obj_t *	pObj,
		int	depth )

Definition at line 1369 of file fretMain.c.

                                                            {
  Vec_Ptr_t *vNodes = Vec_PtrAlloc(100); 
  Abc_Obj_t *pObj2;
 
  Abc_ObjPrintNeighborhood_rec( pObj, vNodes, depth );
 
  while(Vec_PtrSize(vNodes)) {
    pObj2 = (Abc_Obj_t*)Vec_PtrPop(vNodes);
    pObj2->fMarkC = 0;
  }
 
  Vec_PtrFree(vNodes);
}

Here is the caller graph for this function:

◆ dfsfast_e()

int dfsfast_e	(	Abc_Obj_t *	pObj,
		Abc_Obj_t *	pPred )

Definition at line 210 of file fretFlow.c.

                                                   {
  int i;
  Abc_Obj_t *pNext;
  
  if (pManMR->fSinkDistTerminate) return 0;
 
  // have we reached the sink?
  if(FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask ||
     Abc_ObjIsPi(pObj)) {
    assert(pPred);
    assert(!pManMR->fIsForward);
    return 1;
  }
 
  FSET(pObj, VISITED_E);
 
#ifdef DEBUG_VISITED
  printf("(%de=%d) ", Abc_ObjId(pObj), FDATA(pObj)->e_dist);
#endif  
 
  // 1. structural edges
  if (pManMR->fIsForward)
    Abc_ObjForEachFanout( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          FDIST(pObj, e, pNext, r) &&
          dfsfast_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("o");
#endif
        goto found;
      }
    }
  else
    Abc_ObjForEachFanin( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          FDIST(pObj, e, pNext, r) &&
          dfsfast_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("o");
#endif
        goto found;
      }
    }  
  
  if (Abc_ObjIsLatch(pObj))
    goto not_found;
 
  // 2. reverse edges (backward retiming only)
  if (!pManMR->fIsForward) { 
    Abc_ObjForEachFanout( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_E) &&
          FDIST(pObj, e, pNext, e) &&
          dfsfast_e(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("i");
#endif
        goto found;
      }
    }
 
  // 3. timing edges (backward retiming only)
#if !defined(IGNORE_TIMING)
    if (pManMR->maxDelay) 
      Vec_PtrForEachEntry(Abc_Obj_t *, FTIMEEDGES(pObj), pNext, i) {
        if (!FTEST(pNext, VISITED_E) &&
            FDIST(pObj, e, pNext, e) &&
            dfsfast_e(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
          printf("o");
#endif
          goto found;
        }
      }
#endif
  }
  
  // unwind
  if (FTEST(pObj, FLOW) && 
      !FTEST(pObj, VISITED_R) &&
      FDIST(pObj, e, pObj, r) &&
      dfsfast_r(pObj, FGETPRED(pObj))) {
 
    FUNSET(pObj, FLOW);
    FSETPRED(pObj, NULL);
#ifdef DEBUG_PRINT_FLOWS
    printf("u");
#endif
    goto found;
  }
  
 not_found:
  FUNSET(pObj, VISITED_E);
  dfsfast_e_retreat(pObj);
  return 0;
  
 found:
#ifdef DEBUG_PRINT_FLOWS
  printf("%d ", Abc_ObjId(pObj));
#endif 
  FUNSET(pObj, VISITED_E);
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfsfast_preorder()

void dfsfast_preorder ( Abc_Ntk_t * pNtk )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Fast DFS.]

Description [Uses sink-distance-histogram heuristic. May not find all flow paths: this occurs in a small number of cases where the flow predecessor points to a non-adjacent node and the distance ordering is perturbed.]

SideEffects []

SeeAlso []

Definition at line 54 of file fretFlow.c.

                                         {
  Abc_Obj_t *pObj, *pNext;
  Vec_Ptr_t *vTimeIn, *qn = Vec_PtrAlloc(Abc_NtkObjNum(pNtk));
  Vec_Int_t *qe = Vec_IntAlloc(Abc_NtkObjNum(pNtk));
  int i, j, d = 0, end;
  int qpos = 0;
 
  // create reverse timing edges for backward traversal
#if !defined(IGNORE_TIMING)
  if (pManMR->maxDelay) {
    Abc_NtkForEachObj( pNtk, pObj, i ) {
      Vec_PtrForEachEntry( Abc_Obj_t *, FTIMEEDGES(pObj), pNext, j ) {
        vTimeIn = FDATA(pNext)->vNodes;
        if (!vTimeIn) {
          vTimeIn = FDATA(pNext)->vNodes = Vec_PtrAlloc(2);
        }
        Vec_PtrPush(vTimeIn, pObj);
      }
    }
  }
#endif
 
  // clear histogram
  assert(pManMR->vSinkDistHist);
  memset(Vec_IntArray(pManMR->vSinkDistHist), 0, sizeof(int)*Vec_IntSize(pManMR->vSinkDistHist));
 
  // seed queue : latches, PIOs, and blocks
  Abc_NtkForEachObj( pNtk, pObj, i )
    if (Abc_ObjIsPo(pObj) ||
        Abc_ObjIsLatch(pObj) || 
        (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
      Vec_PtrPush(qn, pObj);
      Vec_IntPush(qe, 'r');
      FDATA(pObj)->r_dist = 1;
    } else if (Abc_ObjIsPi(pObj) || 
               (!pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
      Vec_PtrPush(qn, pObj);
      Vec_IntPush(qe, 'e');
      FDATA(pObj)->e_dist = 1;
    }
 
  // until queue is empty...
  while(qpos < Vec_PtrSize(qn)) {
    pObj = (Abc_Obj_t *)Vec_PtrEntry(qn, qpos);
    assert(pObj);
    end = Vec_IntEntry(qe, qpos);
    qpos++;
    
    if (end == 'r') {
      d = FDATA(pObj)->r_dist;
 
      // 1. structural edges
      if (pManMR->fIsForward) {
        Abc_ObjForEachFanin( pObj, pNext, i )
          if (!FDATA(pNext)->e_dist) {
            FDATA(pNext)->e_dist = d+1;
            Vec_PtrPush(qn, pNext);
            Vec_IntPush(qe, 'e');
          }
      } else
        Abc_ObjForEachFanout( pObj, pNext, i )
          if (!FDATA(pNext)->e_dist) {
            FDATA(pNext)->e_dist = d+1;
            Vec_PtrPush(qn, pNext);
            Vec_IntPush(qe, 'e');
          }
 
      if (d == 1) continue;
 
      // 2. reverse edges (forward retiming only)
      if (pManMR->fIsForward) {
        Abc_ObjForEachFanout( pObj, pNext, i )
          if (!FDATA(pNext)->r_dist && !Abc_ObjIsLatch(pNext)) {
            FDATA(pNext)->r_dist = d+1;
            Vec_PtrPush(qn, pNext);
            Vec_IntPush(qe, 'r');
          }          
 
      // 3. timimg edges (forward retiming only)
#if !defined(IGNORE_TIMING)
        if (pManMR->maxDelay && FDATA(pObj)->vNodes)
          Vec_PtrForEachEntry(Abc_Obj_t *, FDATA(pObj)->vNodes, pNext, i ) {
            if (!FDATA(pNext)->r_dist) {
              FDATA(pNext)->r_dist = d+1;
              Vec_PtrPush(qn, pNext);
              Vec_IntPush(qe, 'r');
            }
          }
#endif
      }
      
    } else { // if 'e'
      if (Abc_ObjIsLatch(pObj)) continue;
 
      d = FDATA(pObj)->e_dist;
 
      // 1. through node
      if (!FDATA(pObj)->r_dist) {
        FDATA(pObj)->r_dist = d+1;
        Vec_PtrPush(qn, pObj);
        Vec_IntPush(qe, 'r');
      }
 
      // 2. reverse edges (backward retiming only)
      if (!pManMR->fIsForward) {
        Abc_ObjForEachFanin( pObj, pNext, i )
          if (!FDATA(pNext)->e_dist && !Abc_ObjIsLatch(pNext)) {
            FDATA(pNext)->e_dist = d+1;
            Vec_PtrPush(qn, pNext);
            Vec_IntPush(qe, 'e');
          }  
 
      // 3. timimg edges (backward retiming only)
#if !defined(IGNORE_TIMING)
        if (pManMR->maxDelay && FDATA(pObj)->vNodes)
          Vec_PtrForEachEntry(Abc_Obj_t *, FDATA(pObj)->vNodes, pNext, i ) {
            if (!FDATA(pNext)->e_dist) {
              FDATA(pNext)->e_dist = d+1;
              Vec_PtrPush(qn, pNext);
              Vec_IntPush(qe, 'e');
            }
          }
#endif
      }
    }
  }
 
  // free time edges
#if !defined(IGNORE_TIMING)
  if (pManMR->maxDelay) {
    Abc_NtkForEachObj( pNtk, pObj, i ) {
      vTimeIn = FDATA(pObj)->vNodes;
      if (vTimeIn) {
        Vec_PtrFree(vTimeIn);
        FDATA(pObj)->vNodes = 0;
      }
    }
  }
#endif
 
  Abc_NtkForEachObj( pNtk, pObj, i ) {
    Vec_IntAddToEntry(pManMR->vSinkDistHist, FDATA(pObj)->r_dist, 1);
    Vec_IntAddToEntry(pManMR->vSinkDistHist, FDATA(pObj)->e_dist, 1);
 
#ifdef DEBUG_PREORDER
    printf("node %d\t: r=%d\te=%d\n", Abc_ObjId(pObj), FDATA(pObj)->r_dist, FDATA(pObj)->e_dist);
#endif
  }
 
  // printf("\t\tpre-ordered (max depth=%d)\n", d+1);
 
  // deallocate
  Vec_PtrFree( qn );
  Vec_IntFree( qe );
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfsfast_r()

int dfsfast_r	(	Abc_Obj_t *	pObj,
		Abc_Obj_t *	pPred )

Definition at line 313 of file fretFlow.c.

                                                   {
  int i;
  Abc_Obj_t *pNext, *pOldPred;
 
  if (pManMR->fSinkDistTerminate) return 0;
 
#ifdef DEBUG_VISITED
  printf("(%dr=%d) ", Abc_ObjId(pObj), FDATA(pObj)->r_dist);
#endif  
 
  // have we reached the sink?
  if (Abc_ObjIsLatch(pObj) ||
      (pManMR->fIsForward && Abc_ObjIsPo(pObj)) || 
      (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
    assert(pPred);
    return 1;
  }
 
  FSET(pObj, VISITED_R);
 
  if (FTEST(pObj, FLOW)) {
 
    pOldPred = FGETPRED(pObj);
    if (pOldPred && 
        !FTEST(pOldPred, VISITED_E) &&
        FDIST(pObj, r, pOldPred, e) &&
        dfsfast_e(pOldPred, pOldPred)) {
 
      FSETPRED(pObj, pPred);
 
#ifdef DEBUG_PRINT_FLOWS
      printf("fr");
#endif
      goto found;
    }
    
  } else {
 
    if (!FTEST(pObj, VISITED_E) &&
        FDIST(pObj, r, pObj, e) &&
        dfsfast_e(pObj, pObj)) {
 
      FSET(pObj, FLOW);
      FSETPRED(pObj, pPred);
 
#ifdef DEBUG_PRINT_FLOWS
      printf("f");
#endif
      goto found;
    }
  }
 
  // 2. reverse edges (forward retiming only)
  if (pManMR->fIsForward) {
    Abc_ObjForEachFanin( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          FDIST(pObj, r, pNext, r) &&
          !Abc_ObjIsLatch(pNext) &&
          dfsfast_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("i");
#endif
        goto found;
      }
    }
  
  // 3. timing edges (forward retiming only)
#if !defined(IGNORE_TIMING)
    if (pManMR->maxDelay) 
      Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
        if (!FTEST(pNext, VISITED_R) &&
            FDIST(pObj, r, pNext, r) &&
            dfsfast_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
          printf("o");
#endif
          goto found;
        }
      }
#endif
  }
  
  FUNSET(pObj, VISITED_R);
  dfsfast_r_retreat(pObj);
  return 0;
 
 found:
#ifdef DEBUG_PRINT_FLOWS
  printf("%d ", Abc_ObjId(pObj));
#endif
  FUNSET(pObj, VISITED_R);
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfsplain_e()

int dfsplain_e	(	Abc_Obj_t *	pObj,
		Abc_Obj_t *	pPred )

Function*************************************************************

Synopsis [Plain DFS.]

Description [Does not use sink-distance-histogram heuristic.]

SideEffects []

SeeAlso []

Definition at line 528 of file fretFlow.c.

                                                    {
  int i;
  Abc_Obj_t *pNext;
  
  if (FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask || 
      Abc_ObjIsPi(pObj)) {
    assert(pPred);
    assert(!pManMR->fIsForward);
    return 1;
  }
 
  FSET(pObj, VISITED_E);
  
  // printf(" %de\n", Abc_ObjId(pObj));
  
  // 1. structural edges
  if (pManMR->fIsForward)
    Abc_ObjForEachFanout( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          dfsplain_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("o");
#endif
        goto found;
      }
    }
  else
    Abc_ObjForEachFanin( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          dfsplain_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("o");
#endif
        goto found;
      }
    }
  
  if (Abc_ObjIsLatch(pObj))
    return 0;
 
  // 2. reverse edges (backward retiming only)
  if (!pManMR->fIsForward) {
    Abc_ObjForEachFanout( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_E) &&
          dfsplain_e(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("i");
#endif
        goto found;
      }
    }
 
  // 3. timing edges (backward retiming only)
#if !defined(IGNORE_TIMING)
    if (pManMR->maxDelay) 
      Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
        if (!FTEST(pNext, VISITED_E) &&
            dfsplain_e(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
          printf("o");
#endif
          goto found;
        }
      }
#endif
  }
  
  // unwind
  if (FTEST(pObj, FLOW) && 
      !FTEST(pObj, VISITED_R) &&
      dfsplain_r(pObj, FGETPRED(pObj))) {
    FUNSET(pObj, FLOW);
    FSETPRED(pObj, NULL);
#ifdef DEBUG_PRINT_FLOWS
    printf("u");
#endif
    goto found;
  }
  
  return 0;
  
 found:
#ifdef DEBUG_PRINT_FLOWS
  printf("%d ", Abc_ObjId(pObj));
#endif
 
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfsplain_r()

int dfsplain_r	(	Abc_Obj_t *	pObj,
		Abc_Obj_t *	pPred )

Definition at line 617 of file fretFlow.c.

                                                    {
  int i;
  Abc_Obj_t *pNext, *pOldPred;
 
  // have we reached the sink?
  if (Abc_ObjIsLatch(pObj) || 
      (pManMR->fIsForward && Abc_ObjIsPo(pObj)) || 
      (pManMR->fIsForward && FTEST(pObj, BLOCK_OR_CONS) & pManMR->constraintMask)) {
    assert(pPred);
    return 1;
  }
 
  FSET(pObj, VISITED_R);
 
  // printf(" %dr\n", Abc_ObjId(pObj));
 
  if (FTEST(pObj, FLOW)) {
 
    pOldPred = FGETPRED(pObj);
    if (pOldPred && 
        !FTEST(pOldPred, VISITED_E) &&
        dfsplain_e(pOldPred, pOldPred)) {
 
      FSETPRED(pObj, pPred);
 
#ifdef DEBUG_PRINT_FLOWS
      printf("fr");
#endif
      goto found;
    }
    
  } else {
 
    if (!FTEST(pObj, VISITED_E) &&
        dfsplain_e(pObj, pObj)) {
 
      FSET(pObj, FLOW);
      FSETPRED(pObj, pPred);
 
#ifdef DEBUG_PRINT_FLOWS
      printf("f");
#endif
      goto found;
    }
  }
 
  // 2. follow reverse edges
  if (pManMR->fIsForward) { // forward retiming only
    Abc_ObjForEachFanin( pObj, pNext, i ) {
      if (!FTEST(pNext, VISITED_R) &&
          !Abc_ObjIsLatch(pNext) &&
          dfsplain_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
        printf("i");
#endif
        goto found;
      }
    }
  
  // 3. timing edges (forward only)
#if !defined(IGNORE_TIMING)
    if (pManMR->maxDelay) 
      Vec_PtrForEachEntry(Abc_Obj_t*, FTIMEEDGES(pObj), pNext, i) {
        if (!FTEST(pNext, VISITED_R) &&
            dfsplain_r(pNext, pPred)) {
#ifdef DEBUG_PRINT_FLOWS
          printf("o");
#endif
          goto found;
        }
      }
#endif
  }
  
  return 0;
 
 found:
#ifdef DEBUG_PRINT_FLOWS
  printf("%d ", Abc_ObjId(pObj));
#endif
  return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_node()

void print_node ( Abc_Obj_t * pObj )

Function*************************************************************

Synopsis [Prints information about a node.]

Description [Debuging.]

SideEffects []

SeeAlso []

Definition at line 945 of file fretMain.c.

                            {
  int i;
  Abc_Obj_t * pNext;
  char m[6];
 
  m[0] = 0;
  if (pObj->fMarkA)
    strcat(m, "A");
  if (pObj->fMarkB)
    strcat(m, "B");
  if (pObj->fMarkC)
    strcat(m, "C");
 
  printf("node %d type=%d lev=%d tedge=%d (%x%s) fanouts {", Abc_ObjId(pObj), Abc_ObjType(pObj),
         pObj->Level, Vec_PtrSize(FTIMEEDGES(pObj)), FDATA(pObj)->mark, m);
  Abc_ObjForEachFanout( pObj, pNext, i )
    printf("%d[%d](%d),", Abc_ObjId(pNext), Abc_ObjType(pNext), FDATA(pNext)->mark);
  printf("} fanins {");
  Abc_ObjForEachFanin( pObj, pNext, i )
    printf("%d[%d](%d),", Abc_ObjId(pNext), Abc_ObjType(pNext), FDATA(pNext)->mark);
  printf("}\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ pManMR

MinRegMan_t* pManMR

extern

Definition at line 52 of file fretMain.c.

Classes

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ BIAS_NODE

◆ BLOCK

◆ BLOCK_OR_CONS

◆ CONSERVATIVE

◆ CROSS_BOUNDARY

◆ DEBUG_CHECK

◆ FDATA

◆ FLOW

◆ FSET

◆ FTEST

◆ FTIMEEDGES

◆ FUNSET

◆ INIT_0

◆ INIT_1

◆ INIT_CARE

◆ MAX

◆ MAX_DIST

◆ MIN

◆ VISITED

◆ VISITED_E

◆ VISITED_R

◆ vprintf

Typedef Documentation

◆ Flow_Data_t

◆ InitConstraint_t

◆ MinRegMan_t

◆ NodeLag_t

Function Documentation

◆ Abc_FlowRetime_AddInitBias()

◆ Abc_FlowRetime_ClearFlows()

◆ Abc_FlowRetime_ConstrainConserv()

◆ Abc_FlowRetime_ConstrainExact()

◆ Abc_FlowRetime_ConstrainExactAll()

◆ Abc_FlowRetime_ConstrainInit()

◆ Abc_FlowRetime_FreeTiming()

◆ Abc_FlowRetime_GetLag()

◆ Abc_FlowRetime_InitState()

◆ Abc_FlowRetime_InitTiming()

◆ Abc_FlowRetime_IsAcrossCut()

◆ Abc_FlowRetime_MinReg()

◆ Abc_FlowRetime_NtkSilentRestrash()

◆ Abc_FlowRetime_PrintInitStateInfo()

◆ Abc_FlowRetime_PushFlows()

◆ Abc_FlowRetime_RefineConstraints()

◆ Abc_FlowRetime_RemoveInitBias()

◆ Abc_FlowRetime_SetLag()

◆ Abc_FlowRetime_SetupBackwardInit()

◆ Abc_FlowRetime_SolveBackwardInit()

◆ Abc_FlowRetime_UpdateBackwardInit()

◆ Abc_FlowRetime_UpdateForwardInit()

◆ Abc_FlowRetime_UpdateLags()

◆ Abc_ObjBetterTransferFanout()

◆ Abc_ObjPrintNeighborhood()

◆ dfsfast_e()

◆ dfsfast_preorder()

◆ dfsfast_r()

◆ dfsplain_e()

◆ dfsplain_r()

◆ print_node()

Variable Documentation

◆ pManMR