abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
retArea.c File Reference
#include "retInt.h"

Go to the source code of this file.

Functions

static
ABC_NAMESPACE_IMPL_START
Abc_Ntk_t
Abc_NtkRetimeMinAreaOne (Abc_Ntk_t *pNtk, int fForward, int fVerbose)
 DECLARATIONS ///. More...
 
static void Abc_NtkRetimeMinAreaPrepare (Abc_Ntk_t *pNtk, int fForward)
 
static void Abc_NtkRetimeMinAreaInitValues (Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut)
 
static Abc_Ntk_tAbc_NtkRetimeMinAreaConstructNtk (Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut)
 
static void Abc_NtkRetimeMinAreaUpdateLatches (Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut, int fForward)
 
Abc_Ntk_tAbc_NtkAttachBottom (Abc_Ntk_t *pNtkTop, Abc_Ntk_t *pNtkBottom)
 
int Abc_NtkRetimeMinArea (Abc_Ntk_t *pNtk, int fForwardOnly, int fBackwardOnly, int fVerbose)
 FUNCTION DEFINITIONS ///. More...
 
void Abc_NtkMarkCone_rec (Abc_Obj_t *pObj, int fForward)
 
void Abc_NtkUnmarkCone_rec (Abc_Obj_t *pObj, int fForward)
 
int Abc_NtkRetimeMinAreaInitValues_rec (Abc_Obj_t *pObj)
 
Abc_Obj_tAbc_NtkRetimeMinAreaConstructNtk_rec (Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj)
 

Function Documentation

Abc_Ntk_t* Abc_NtkAttachBottom ( Abc_Ntk_t pNtkTop,
Abc_Ntk_t pNtkBottom 
)

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

Synopsis [Attaches the second network at the bottom of the first.]

Description [Returns the first network. Deletes the second network.]

SideEffects []

SeeAlso []

Definition at line 760 of file abcNtk.c.

761 {
762  Abc_Obj_t * pObj, * pFanin, * pBuffer;
763  Vec_Ptr_t * vNodes;
764  int i, k;
765  assert( pNtkBottom != NULL );
766  if ( pNtkTop == NULL )
767  return pNtkBottom;
768  // make sure the networks are combinational
769  assert( Abc_NtkPiNum(pNtkTop) == Abc_NtkCiNum(pNtkTop) );
770  assert( Abc_NtkPiNum(pNtkBottom) == Abc_NtkCiNum(pNtkBottom) );
771  // make sure the POs of the bottom correspond to the PIs of the top
772  assert( Abc_NtkPoNum(pNtkBottom) == Abc_NtkPiNum(pNtkTop) );
773  assert( Abc_NtkPiNum(pNtkBottom) < Abc_NtkPiNum(pNtkTop) );
774  // add buffers for the PIs of the top - save results in the POs of the bottom
775  Abc_NtkForEachPi( pNtkTop, pObj, i )
776  {
777  pBuffer = Abc_NtkCreateNodeBuf( pNtkTop, NULL );
778  Abc_ObjTransferFanout( pObj, pBuffer );
779  Abc_NtkPo(pNtkBottom, i)->pCopy = pBuffer;
780  }
781  // remove useless PIs of the top
782  for ( i = Abc_NtkPiNum(pNtkTop) - 1; i >= Abc_NtkPiNum(pNtkBottom); i-- )
783  Abc_NtkDeleteObj( Abc_NtkPi(pNtkTop, i) );
784  assert( Abc_NtkPiNum(pNtkBottom) == Abc_NtkPiNum(pNtkTop) );
785  // copy the bottom network
786  Abc_NtkForEachPi( pNtkBottom, pObj, i )
787  Abc_NtkPi(pNtkBottom, i)->pCopy = Abc_NtkPi(pNtkTop, i);
788  // construct all nodes
789  vNodes = Abc_NtkDfs( pNtkBottom, 0 );
790  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
791  {
792  Abc_NtkDupObj(pNtkTop, pObj, 0);
793  Abc_ObjForEachFanin( pObj, pFanin, k )
794  Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
795  }
796  Vec_PtrFree( vNodes );
797  // connect the POs
798  Abc_NtkForEachPo( pNtkBottom, pObj, i )
799  Abc_ObjAddFanin( pObj->pCopy, Abc_ObjFanin0(pObj)->pCopy );
800  // delete old network
801  Abc_NtkDelete( pNtkBottom );
802  // return the network
803  if ( !Abc_NtkCheck( pNtkTop ) )
804  fprintf( stdout, "Abc_NtkAttachBottom(): Network check has failed.\n" );
805  return pNtkTop;
806 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
ABC_DLL Abc_Obj_t * Abc_NtkDupObj(Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, int fCopyName)
Definition: abcObj.c:337
static int Abc_NtkCiNum(Abc_Ntk_t *pNtk)
Definition: abc.h:287
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
ABC_DLL Vec_Ptr_t * Abc_NtkDfs(Abc_Ntk_t *pNtk, int fCollectAll)
Definition: abcDfs.c:81
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
Abc_Ntk_t * Abc_NtkAttachBottom(Abc_Ntk_t *pNtkTop, Abc_Ntk_t *pNtkBottom)
Definition: abcNtk.c:760
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
static void check(int expr)
Definition: satSolver.c:46
Abc_Obj_t * pCopy
Definition: abc.h:148
ABC_DLL void Abc_NtkDeleteObj(Abc_Obj_t *pObj)
Definition: abcObj.c:167
void Abc_NtkDelete(Abc_Ntk_t *pNtk)
Definition: abcNtk.c:1233
ABC_DLL Abc_Obj_t * Abc_NtkCreateNodeBuf(Abc_Ntk_t *pNtk, Abc_Obj_t *pFanin)
Definition: abcObj.c:692
if(last==0)
Definition: sparse_int.h:34
ABC_DLL void Abc_ObjTransferFanout(Abc_Obj_t *pObjOld, Abc_Obj_t *pObjNew)
Definition: abcFanio.c:264
static Abc_Obj_t * Abc_NtkPo(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:316
static int Abc_NtkPoNum(Abc_Ntk_t *pNtk)
Definition: abc.h:286
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
static int Abc_NtkPiNum(Abc_Ntk_t *pNtk)
Definition: abc.h:285
#define assert(ex)
Definition: util_old.h:213
static Abc_Obj_t * Abc_NtkPi(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:315
#define Abc_NtkForEachPo(pNtk, pPo, i)
Definition: abc.h:517
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
#define Abc_NtkForEachPi(pNtk, pPi, i)
Definition: abc.h:513
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkMarkCone_rec ( Abc_Obj_t pObj,
int  fForward 
)

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

Synopsis [Marks the cone with MarkA.]

Description []

SideEffects []

SeeAlso []

Definition at line 147 of file retArea.c.

148 {
149  Abc_Obj_t * pNext;
150  int i;
151  if ( pObj->fMarkA )
152  return;
153  pObj->fMarkA = 1;
154  if ( fForward )
155  {
156  Abc_ObjForEachFanout( pObj, pNext, i )
157  Abc_NtkMarkCone_rec( pNext, fForward );
158  }
159  else
160  {
161  Abc_ObjForEachFanin( pObj, pNext, i )
162  Abc_NtkMarkCone_rec( pNext, fForward );
163  }
164 }
unsigned fMarkA
Definition: abc.h:134
else
Definition: sparse_int.h:55
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
void Abc_NtkMarkCone_rec(Abc_Obj_t *pObj, int fForward)
Definition: retArea.c:147
int Abc_NtkRetimeMinArea ( Abc_Ntk_t pNtk,
int  fForwardOnly,
int  fBackwardOnly,
int  fVerbose 
)

FUNCTION DEFINITIONS ///.

INCLUDES ///.

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

Synopsis [Performs min-area retiming.]

Description [Returns the number of latches reduced.]

SideEffects []

SeeAlso []

Definition at line 53 of file retArea.c.

54 {
55  Abc_Ntk_t * pNtkTotal = NULL, * pNtkBottom;
56  Vec_Int_t * vValuesNew = NULL, * vValues;
57  int nLatches = Abc_NtkLatchNum(pNtk);
58  int fOneFrame = 0;
59  assert( !fForwardOnly || !fBackwardOnly );
60  // there should not be black boxes
61  assert( Abc_NtkIsSopLogic(pNtk) );
62  assert( Abc_NtkLatchNum(pNtk) == Vec_PtrSize(pNtk->vBoxes) );
63  // reorder CI/CO/latch inputs
64  Abc_NtkOrderCisCos( pNtk );
65  // perform forward retiming
66  if ( !fBackwardOnly )
67  {
68  if ( fOneFrame )
69  Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose );
70  else
71  while ( Abc_NtkRetimeMinAreaOne( pNtk, 1, fVerbose ) );
72  }
73  // remember initial values
74  vValues = Abc_NtkCollectLatchValues( pNtk );
75  // perform backward retiming
76  if ( !fForwardOnly )
77  {
78  if ( fOneFrame )
79  pNtkTotal = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose );
80  else
81  while ( (pNtkBottom = Abc_NtkRetimeMinAreaOne( pNtk, 0, fVerbose )) )
82  pNtkTotal = Abc_NtkAttachBottom( pNtkTotal, pNtkBottom );
83  }
84  // compute initial values
85  vValuesNew = Abc_NtkRetimeInitialValues( pNtkTotal, vValues, fVerbose );
86  if ( pNtkTotal ) Abc_NtkDelete( pNtkTotal );
87  // insert new initial values
88  Abc_NtkInsertLatchValues( pNtk, vValuesNew );
89  if ( vValuesNew ) Vec_IntFree( vValuesNew );
90  if ( vValues ) Vec_IntFree( vValues );
91  // fix the COs (this changes the circuit structure)
92 // Abc_NtkLogicMakeSimpleCos( pNtk, 0 );
93  // check for correctness
94  if ( !Abc_NtkCheck( pNtk ) )
95  fprintf( stdout, "Abc_NtkRetimeMinArea(): Network check has failed.\n" );
96  // return the number of latches saved
97  return nLatches - Abc_NtkLatchNum(pNtk);
98 }
ABC_DLL void Abc_NtkInsertLatchValues(Abc_Ntk_t *pNtk, Vec_Int_t *vValues)
Definition: abcLatch.c:241
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_Ptr_t * vBoxes
Definition: abc.h:168
static int Abc_NtkLatchNum(Abc_Ntk_t *pNtk)
Definition: abc.h:294
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
static int Abc_NtkIsSopLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:264
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
ABC_DLL void Abc_NtkDelete(Abc_Ntk_t *pNtk)
Definition: abcNtk.c:1233
Vec_Int_t * Abc_NtkRetimeInitialValues(Abc_Ntk_t *pNtkCone, Vec_Int_t *vValues, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition: retInit.c:47
ABC_DLL Vec_Int_t * Abc_NtkCollectLatchValues(Abc_Ntk_t *pNtk)
Definition: abcLatch.c:187
Abc_Ntk_t * Abc_NtkAttachBottom(Abc_Ntk_t *pNtkTop, Abc_Ntk_t *pNtkBottom)
Definition: abcNtk.c:760
static ABC_NAMESPACE_IMPL_START Abc_Ntk_t * Abc_NtkRetimeMinAreaOne(Abc_Ntk_t *pNtk, int fForward, int fVerbose)
DECLARATIONS ///.
Definition: retArea.c:111
#define assert(ex)
Definition: util_old.h:213
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
ABC_DLL void Abc_NtkOrderCisCos(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:71
Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk ( Abc_Ntk_t pNtk,
Vec_Ptr_t vMinCut 
)
static

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

Synopsis [Creates the network from computing initial state.]

Description []

SideEffects []

SeeAlso []

Definition at line 365 of file retArea.c.

366 {
367  Abc_Ntk_t * pNtkNew;
368  Abc_Obj_t * pObj, * pObjNew;
369  int i;
370  // create new network
371  pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
372  // map new latches into PIs of the new network
374  Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
375  {
376  pObj->pCopy = Abc_NtkCreatePi(pNtkNew);
377  Abc_NodeSetTravIdCurrent( pObj );
378  }
379  // construct the network recursively
380  Abc_NtkForEachLatch( pNtk, pObj, i )
381  {
382  pObjNew = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
383  Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObjNew );
384  }
385  // unmark the nodes in the cut
386  Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
388  // unmark the latches
389  Abc_NtkForEachLatch( pNtk, pObj, i )
391  // assign dummy node names
392  Abc_NtkAddDummyPiNames( pNtkNew );
393  Abc_NtkAddDummyPoNames( pNtkNew );
394  if ( !Abc_NtkCheck( pNtkNew ) )
395  fprintf( stdout, "Abc_NtkRetimeMinAreaConstructNtk(): Network check has failed.\n" );
396  return pNtkNew;
397 }
static void Abc_NodeSetTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:410
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec(Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj)
Definition: retArea.c:329
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
ABC_DLL Abc_Ntk_t * Abc_NtkAlloc(Abc_NtkType_t Type, Abc_NtkFunc_t Func, int fUseMemMan)
DECLARATIONS ///.
Definition: abcNtk.c:50
static void check(int expr)
Definition: satSolver.c:46
ABC_DLL void Abc_NtkAddDummyPoNames(Abc_Ntk_t *pNtk)
Definition: abcNames.c:398
Abc_Obj_t * pCopy
Definition: abc.h:148
static Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk(Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut)
Definition: retArea.c:365
if(last==0)
Definition: sparse_int.h:34
#define Abc_NtkForEachLatch(pNtk, pObj, i)
Definition: abc.h:497
static Abc_Obj_t * Abc_NtkCreatePi(Abc_Ntk_t *pNtk)
Definition: abc.h:303
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
ABC_DLL void Abc_NtkAddDummyPiNames(Abc_Ntk_t *pNtk)
Definition: abcNames.c:378
static Abc_Obj_t * Abc_NtkCreatePo(Abc_Ntk_t *pNtk)
Definition: abc.h:304
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Abc_Obj_t* Abc_NtkRetimeMinAreaConstructNtk_rec ( Abc_Ntk_t pNtkNew,
Abc_Obj_t pObj 
)

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

Synopsis [Performs min-area retiming backward.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file retArea.c.

330 {
331  Abc_Obj_t * pFanin;
332  int i;
333  // skip visited nodes
334  if ( Abc_NodeIsTravIdCurrent(pObj) )
335  return pObj->pCopy;
337  // consider the case of a latch output
338  if ( Abc_ObjIsBi(pObj) )
339  {
340  pObj->pCopy = Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, Abc_ObjFanin0(pObj) );
341  return pObj->pCopy;
342  }
343  assert( Abc_ObjIsNode(pObj) );
344  // visit the fanins
345  Abc_ObjForEachFanin( pObj, pFanin, i )
346  Abc_NtkRetimeMinAreaConstructNtk_rec( pNtkNew, pFanin );
347  // compute the value of the node
348  Abc_NtkDupObj( pNtkNew, pObj, 0 );
349  Abc_ObjForEachFanin( pObj, pFanin, i )
350  Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
351  return pObj->pCopy;
352 }
ABC_DLL Abc_Obj_t * Abc_NtkDupObj(Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, int fCopyName)
Definition: abcObj.c:337
Abc_Obj_t * Abc_NtkRetimeMinAreaConstructNtk_rec(Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj)
Definition: retArea.c:329
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_Obj_t * pCopy
Definition: abc.h:148
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
static int Abc_ObjIsBi(Abc_Obj_t *pObj)
Definition: abc.h:349
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
#define assert(ex)
Definition: util_old.h:213
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
void Abc_NtkRetimeMinAreaInitValues ( Abc_Ntk_t pNtk,
Vec_Ptr_t vMinCut 
)
static

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

Synopsis [Compute initial values.]

Description []

SideEffects []

SeeAlso []

Definition at line 299 of file retArea.c.

300 {
301  Abc_Obj_t * pObj;
302  int i;
303  // transfer initial values to pCopy and mark the latches
305  Abc_NtkForEachLatch( pNtk, pObj, i )
306  {
307  pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_LatchIsInit1(pObj);
308  Abc_NodeSetTravIdCurrent( pObj );
309  }
310  // propagate initial values
311  Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
313  // unmark the latches
314  Abc_NtkForEachLatch( pNtk, pObj, i )
316 }
static void Abc_NodeSetTravIdPrevious(Abc_Obj_t *p)
Definition: abc.h:410
Abc_Obj_t * pCopy
Definition: abc.h:148
int Abc_NtkRetimeMinAreaInitValues_rec(Abc_Obj_t *pObj)
Definition: retArea.c:264
#define Abc_NtkForEachLatch(pNtk, pObj, i)
Definition: abc.h:497
static int Abc_LatchIsInit1(Abc_Obj_t *pLatch)
Definition: abc.h:423
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
int Abc_NtkRetimeMinAreaInitValues_rec ( Abc_Obj_t pObj)

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

Synopsis [Compute initial values.]

Description []

SideEffects []

SeeAlso []

Definition at line 264 of file retArea.c.

265 {
266  Abc_Obj_t * pFanin;
267  int i;
268  // skip visited nodes
269  if ( Abc_NodeIsTravIdCurrent(pObj) )
270  return (int)(ABC_PTRUINT_T)pObj->pCopy;
272  // consider the case of a latch output
273  if ( Abc_ObjIsBo(pObj) )
274  {
276  pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_NtkRetimeMinAreaInitValues_rec( Abc_ObjFanin0(pObj) );
277  return (int)(ABC_PTRUINT_T)pObj->pCopy;
278  }
279  assert( Abc_ObjIsNode(pObj) );
280  // visit the fanins
281  Abc_ObjForEachFanin( pObj, pFanin, i )
283  // compute the value of the node
284  pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)Abc_ObjSopSimulate(pObj);
285  return (int)(ABC_PTRUINT_T)pObj->pCopy;
286 }
static int Abc_ObjIsBo(Abc_Obj_t *pObj)
Definition: abc.h:350
static int Abc_ObjIsLatch(Abc_Obj_t *pObj)
Definition: abc.h:356
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_Obj_t * pCopy
Definition: abc.h:148
int Abc_ObjSopSimulate(Abc_Obj_t *pObj)
Definition: retInit.c:93
int Abc_NtkRetimeMinAreaInitValues_rec(Abc_Obj_t *pObj)
Definition: retArea.c:264
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
#define assert(ex)
Definition: util_old.h:213
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Abc_Ntk_t * Abc_NtkRetimeMinAreaOne ( Abc_Ntk_t pNtk,
int  fForward,
int  fVerbose 
)
static

DECLARATIONS ///.

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

FileName [retArea.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Retiming package.]

Synopsis [Min-area retiming.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Oct 31, 2006.]

Revision [

Id:
retArea.c,v 1.00 2006/10/31 00:00:00 alanmi Exp

]

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

Synopsis [Performs min-area retiming backward.]

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file retArea.c.

112 {
113  Abc_Ntk_t * pNtkNew = NULL;
114  Vec_Ptr_t * vMinCut;
115  // mark current latches and TFI(POs)
116  Abc_NtkRetimeMinAreaPrepare( pNtk, fForward );
117  // run the maximum forward flow
118  vMinCut = Abc_NtkMaxFlow( pNtk, fForward, fVerbose );
119 // assert( Vec_PtrSize(vMinCut) <= Abc_NtkLatchNum(pNtk) );
120  // create new latch boundary if there is improvement
121  if ( Vec_PtrSize(vMinCut) < Abc_NtkLatchNum(pNtk) )
122  {
123  pNtkNew = (Abc_Ntk_t *)1;
124  if ( fForward )
125  Abc_NtkRetimeMinAreaInitValues( pNtk, vMinCut );
126  else
127  pNtkNew = Abc_NtkRetimeMinAreaConstructNtk( pNtk, vMinCut );
128  Abc_NtkRetimeMinAreaUpdateLatches( pNtk, vMinCut, fForward );
129  }
130  // clean up
131  Vec_PtrFree( vMinCut );
132  Abc_NtkCleanMarkA( pNtk );
133  return pNtkNew;
134 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Vec_Ptr_t * Abc_NtkMaxFlow(Abc_Ntk_t *pNtk, int fForward, int fVerbose)
Definition: retFlow.c:143
static void Abc_NtkRetimeMinAreaUpdateLatches(Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut, int fForward)
Definition: retArea.c:411
static int Abc_NtkLatchNum(Abc_Ntk_t *pNtk)
Definition: abc.h:294
static void Abc_NtkRetimeMinAreaPrepare(Abc_Ntk_t *pNtk, int fForward)
Definition: retArea.c:207
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
ABC_DLL void Abc_NtkCleanMarkA(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:663
static Abc_Ntk_t * Abc_NtkRetimeMinAreaConstructNtk(Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut)
Definition: retArea.c:365
static void Abc_NtkRetimeMinAreaInitValues(Abc_Ntk_t *pNtk, Vec_Ptr_t *vMinCut)
Definition: retArea.c:299
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkRetimeMinAreaPrepare ( Abc_Ntk_t pNtk,
int  fForward 
)
static

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

Synopsis [Prepares the network for running MaxFlow.]

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file retArea.c.

208 {
209  Vec_Ptr_t * vNodes;
210  Abc_Obj_t * pObj, * pFanin;
211  int i, k;
212  if ( fForward )
213  {
214  // mark the frontier
215  Abc_NtkForEachPo( pNtk, pObj, i )
216  pObj->fMarkA = 1;
217  Abc_NtkForEachLatch( pNtk, pObj, i )
218  {
219  pObj->fMarkA = 1;
220  Abc_ObjFanin0(pObj)->fMarkA = 1;
221  }
222  // mark the nodes reachable from the PIs
223  Abc_NtkForEachPi( pNtk, pObj, i )
224  Abc_NtkMarkCone_rec( pObj, fForward );
225  // collect the unmarked fanins of the marked nodes
226  vNodes = Vec_PtrAlloc( 100 );
227  Abc_NtkForEachObj( pNtk, pObj, i )
228  if ( pObj->fMarkA )
229  Abc_ObjForEachFanin( pObj, pFanin, k )
230  if ( !pFanin->fMarkA )
231  Vec_PtrPush( vNodes, pFanin );
232  // mark these nodes
233  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
234  pObj->fMarkA = 1;
235  Vec_PtrFree( vNodes );
236  }
237  else
238  {
239  // mark the frontier
240  Abc_NtkForEachPi( pNtk, pObj, i )
241  pObj->fMarkA = 1;
242  Abc_NtkForEachLatch( pNtk, pObj, i )
243  {
244  pObj->fMarkA = 1;
245  Abc_ObjFanout0(pObj)->fMarkA = 1;
246  }
247  // mark the nodes reachable from the POs
248  Abc_NtkForEachPo( pNtk, pObj, i )
249  Abc_NtkMarkCone_rec( pObj, fForward );
250  }
251 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
unsigned fMarkA
Definition: abc.h:134
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
if(last==0)
Definition: sparse_int.h:34
else
Definition: sparse_int.h:55
#define Abc_NtkForEachLatch(pNtk, pObj, i)
Definition: abc.h:497
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
#define Abc_NtkForEachPo(pNtk, pPo, i)
Definition: abc.h:517
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
#define Abc_NtkForEachObj(pNtk, pObj, i)
ITERATORS ///.
Definition: abc.h:446
static Abc_Obj_t * Abc_ObjFanout0(Abc_Obj_t *pObj)
Definition: abc.h:371
void Abc_NtkMarkCone_rec(Abc_Obj_t *pObj, int fForward)
Definition: retArea.c:147
#define Abc_NtkForEachPi(pNtk, pPi, i)
Definition: abc.h:513
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkRetimeMinAreaUpdateLatches ( Abc_Ntk_t pNtk,
Vec_Ptr_t vMinCut,
int  fForward 
)
static

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

Synopsis [Updates the network after backward retiming.]

Description [Assumes that fMarkA denotes all nodes reachabe from the latches toward the cut.]

SideEffects []

SeeAlso []

Definition at line 411 of file retArea.c.

412 {
413  Vec_Ptr_t * vCis, * vCos, * vBoxes, * vBoxesNew, * vNodes, * vBuffers;
414  Abc_Obj_t * pObj, * pLatch, * pLatchIn, * pLatchOut, * pNext, * pBuffer;
415  int i, k;
416  // create new latches
417  Vec_PtrShrink( pNtk->vCis, Abc_NtkCiNum(pNtk) - Abc_NtkLatchNum(pNtk) );
418  Vec_PtrShrink( pNtk->vCos, Abc_NtkCoNum(pNtk) - Abc_NtkLatchNum(pNtk) );
419  vCis = pNtk->vCis; pNtk->vCis = NULL;
420  vCos = pNtk->vCos; pNtk->vCos = NULL;
421  vBoxes = pNtk->vBoxes; pNtk->vBoxes = NULL;
422  // transfer boxes
423  vBoxesNew = Vec_PtrAlloc(100);
424  Vec_PtrForEachEntry( Abc_Obj_t *, vBoxes, pObj, i )
425  if ( !Abc_ObjIsLatch(pObj) )
426  Vec_PtrPush( vBoxesNew, pObj );
427  // create or reuse latches
428  vNodes = Vec_PtrAlloc( 100 );
429  vBuffers = Vec_PtrAlloc( 100 );
430  Vec_PtrForEachEntry( Abc_Obj_t *, vMinCut, pObj, i )
431  {
432  if ( Abc_ObjIsCi(pObj) && fForward )
433  {
434  pLatchOut = pObj;
435  pLatch = Abc_ObjFanin0(pLatchOut);
436  pLatchIn = Abc_ObjFanin0(pLatch);
437  assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
438  // mark the latch as reused
439  Abc_NodeSetTravIdCurrent( pLatch );
440 
441  // check if there are marked fanouts
442  // (these are fanouts to be connected to the latch input)
443  Abc_ObjForEachFanout( pObj, pNext, k )
444  if ( pNext->fMarkA )
445  break;
446  if ( k < Abc_ObjFanoutNum(pObj) )
447  {
448  // add the buffer
449  pBuffer = Abc_NtkCreateNodeBuf( pNtk, Abc_ObjFanin0(pLatchIn) );
450  Abc_ObjPatchFanin( pLatchIn, Abc_ObjFanin0(pLatchIn), pBuffer );
451  Vec_PtrPush( vBuffers, pBuffer );
452  // redirect edges to the unvisited fanouts of the node
453  Abc_NodeCollectFanouts( pObj, vNodes );
454  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
455  if ( pNext->fMarkA )
456  Abc_ObjPatchFanin( pNext, pObj, pBuffer );
457  }
458  assert( Abc_ObjFanoutNum(pObj) > 0 );
459 // if ( Abc_ObjFanoutNum(pObj) == 0 )
460 // Abc_NtkDeleteObj_rec( pObj, 0 );
461  }
462  else if ( Abc_ObjIsCo(pObj) && !fForward )
463  {
464  pLatchIn = pObj;
465  pLatch = Abc_ObjFanout0(pLatchIn);
466  pLatchOut = Abc_ObjFanout0(pLatch);
467  assert( Abc_ObjIsBo(pLatchOut) && Abc_ObjIsLatch(pLatch) && Abc_ObjIsBi(pLatchIn) );
468  // mark the latch as reused
469  Abc_NodeSetTravIdCurrent( pLatch );
470  assert( !Abc_ObjFanin0(pLatchIn)->fMarkA );
471  }
472  else
473  {
474  pLatchOut = Abc_NtkCreateBo(pNtk);
475  pLatch = Abc_NtkCreateLatch(pNtk);
476  pLatchIn = Abc_NtkCreateBi(pNtk);
477  Abc_ObjAssignName( pLatchOut, Abc_ObjName(pLatch), "_out" );
478  Abc_ObjAssignName( pLatchIn, Abc_ObjName(pLatch), "_in" );
479  // connect
480  Abc_ObjAddFanin( pLatchOut, pLatch );
481  Abc_ObjAddFanin( pLatch, pLatchIn );
482  if ( fForward )
483  {
484  pLatch->pData = (void *)(ABC_PTRUINT_T)(pObj->pCopy? ABC_INIT_ONE : ABC_INIT_ZERO);
485  // redirect edges to the unvisited fanouts of the node
486  Abc_NodeCollectFanouts( pObj, vNodes );
487  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
488  if ( !pNext->fMarkA )
489  Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
490  }
491  else
492  {
493  // redirect edges to the visited fanouts of the node
494  Abc_NodeCollectFanouts( pObj, vNodes );
495  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNext, k )
496  if ( pNext->fMarkA )
497  Abc_ObjPatchFanin( pNext, pObj, pLatchOut );
498  }
499  // connect latch to the node
500  Abc_ObjAddFanin( pLatchIn, pObj );
501  }
502  Vec_PtrPush( vCis, pLatchOut );
503  Vec_PtrPush( vBoxesNew, pLatch );
504  Vec_PtrPush( vCos, pLatchIn );
505  }
506  Vec_PtrFree( vNodes );
507  // remove buffers
508  Vec_PtrForEachEntry( Abc_Obj_t *, vBuffers, pObj, i )
509  {
510  Abc_ObjTransferFanout( pObj, Abc_ObjFanin0(pObj) );
511  Abc_NtkDeleteObj( pObj );
512  }
513  Vec_PtrFree( vBuffers );
514  // remove useless latches
515  Vec_PtrForEachEntry( Abc_Obj_t *, vBoxes, pObj, i )
516  {
517  if ( !Abc_ObjIsLatch(pObj) )
518  continue;
519  if ( Abc_NodeIsTravIdCurrent(pObj) )
520  continue;
521  pLatchOut = Abc_ObjFanout0(pObj);
522  pLatch = pObj;
523  pLatchIn = Abc_ObjFanin0(pObj);
524  if ( Abc_ObjFanoutNum(pLatchOut) > 0 )
525  Abc_ObjTransferFanout( pLatchOut, Abc_ObjFanin0(pLatchIn) );
526  Abc_NtkDeleteObj( pLatchOut );
527  Abc_NtkDeleteObj( pObj );
528  Abc_NtkDeleteObj( pLatchIn );
529  }
530  // set the arrays
531  pNtk->vCis = vCis;
532  pNtk->vCos = vCos;
533  pNtk->vBoxes = vBoxesNew;
534  Vec_PtrFree( vBoxes );
535 }
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
static int Abc_ObjIsBo(Abc_Obj_t *pObj)
Definition: abc.h:350
Vec_Ptr_t * vBoxes
Definition: abc.h:168
static int Abc_ObjIsLatch(Abc_Obj_t *pObj)
Definition: abc.h:356
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
static int Abc_NtkLatchNum(Abc_Ntk_t *pNtk)
Definition: abc.h:294
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Abc_NtkCiNum(Abc_Ntk_t *pNtk)
Definition: abc.h:287
ABC_DLL char * Abc_ObjAssignName(Abc_Obj_t *pObj, char *pName, char *pSuffix)
Definition: abcNames.c:68
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
static int Abc_NtkCoNum(Abc_Ntk_t *pNtk)
Definition: abc.h:288
static int Abc_ObjIsCo(Abc_Obj_t *pObj)
Definition: abc.h:352
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
Vec_Ptr_t * vCis
Definition: abc.h:165
static Abc_Obj_t * Abc_NtkCreateBo(Abc_Ntk_t *pNtk)
Definition: abc.h:306
ABC_DLL void Abc_ObjPatchFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFaninOld, Abc_Obj_t *pFaninNew)
Definition: abcFanio.c:172
ABC_DLL void Abc_NtkDeleteObj(Abc_Obj_t *pObj)
Definition: abcObj.c:167
Vec_Ptr_t * vCos
Definition: abc.h:166
ABC_DLL Abc_Obj_t * Abc_NtkCreateNodeBuf(Abc_Ntk_t *pNtk, Abc_Obj_t *pFanin)
Definition: abcObj.c:692
if(last==0)
Definition: sparse_int.h:34
else
Definition: sparse_int.h:55
static Abc_Obj_t * Abc_NtkCreateLatch(Abc_Ntk_t *pNtk)
Definition: abc.h:309
ABC_DLL void Abc_ObjTransferFanout(Abc_Obj_t *pObjOld, Abc_Obj_t *pObjNew)
Definition: abcFanio.c:264
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
static int Abc_ObjIsBi(Abc_Obj_t *pObj)
Definition: abc.h:349
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_DLL char * Abc_ObjName(Abc_Obj_t *pNode)
DECLARATIONS ///.
Definition: abcNames.c:48
#define assert(ex)
Definition: util_old.h:213
void * pData
Definition: abc.h:145
static Abc_Obj_t * Abc_NtkCreateBi(Abc_Ntk_t *pNtk)
Definition: abc.h:305
ABC_DLL void Abc_NodeCollectFanouts(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
Definition: abcUtil.c:1607
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
static void Vec_PtrShrink(Vec_Ptr_t *p, int nSizeNew)
Definition: vecPtr.h:528
static Abc_Obj_t * Abc_ObjFanout0(Abc_Obj_t *pObj)
Definition: abc.h:371
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkUnmarkCone_rec ( Abc_Obj_t pObj,
int  fForward 
)

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

Synopsis [Marks the cone with MarkA.]

Description []

SideEffects []

SeeAlso []

Definition at line 177 of file retArea.c.

178 {
179  Abc_Obj_t * pNext;
180  int i;
181  if ( !pObj->fMarkA || Abc_ObjIsLatch(pObj) )
182  return;
183  pObj->fMarkA = 0;
184  if ( fForward )
185  {
186  Abc_ObjForEachFanout( pObj, pNext, i )
187  Abc_NtkUnmarkCone_rec( pNext, fForward );
188  }
189  else
190  {
191  Abc_ObjForEachFanin( pObj, pNext, i )
192  Abc_NtkUnmarkCone_rec( pNext, fForward );
193  }
194 }
unsigned fMarkA
Definition: abc.h:134
static int Abc_ObjIsLatch(Abc_Obj_t *pObj)
Definition: abc.h:356
void Abc_NtkUnmarkCone_rec(Abc_Obj_t *pObj, int fForward)
Definition: retArea.c:177
else
Definition: sparse_int.h:55
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524