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

Go to the source code of this file.

Functions

static Nwk_Obj_tNwk_ObjPred (Nwk_Obj_t *pObj)
 DECLARATIONS ///. More...
 
static int Nwk_ObjSetPred (Nwk_Obj_t *pObj, Nwk_Obj_t *p)
 
static int Nwk_ObjIsSink (Nwk_Obj_t *pObj)
 
static void Nwk_ObjSetSink (Nwk_Obj_t *pObj)
 
static int Nwk_ObjHasFlow (Nwk_Obj_t *pObj)
 
static void Nwk_ObjSetFlow (Nwk_Obj_t *pObj)
 
static void Nwk_ObjClearFlow (Nwk_Obj_t *pObj)
 
static int Nwk_ObjVisitedBotOnly (Nwk_Obj_t *pObj)
 
static int Nwk_ObjVisitedBot (Nwk_Obj_t *pObj)
 
static int Nwk_ObjVisitedTop (Nwk_Obj_t *pObj)
 
static void Nwk_ObjSetVisitedBot (Nwk_Obj_t *pObj)
 
static void Nwk_ObjSetVisitedTop (Nwk_Obj_t *pObj)
 
static Nwk_ManIncrementTravIdFlow (Nwk_Man_t *pMan)
 
static int Nwk_ManPushForwardTop_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
static int Nwk_ManPushForwardBot_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
static int Nwk_ManPushBackwardTop_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
static int Nwk_ManPushBackwardBot_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
void Nwk_ManMarkTfiCone_rec (Nwk_Obj_t *pObj)
 FUNCTION DEFINITIONS ///. More...
 
void Nwk_ManMarkTfoCone_rec (Nwk_Obj_t *pObj)
 
int Nwk_ManPushForwardFast_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
int Nwk_ManPushBackwardFast_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
 
int Nwk_ManVerifyCut_rec (Nwk_Obj_t *pObj)
 
int Nwk_ManRetimeVerifyCutForward (Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
 
int Nwk_ManRetimeVerifyCutBackward (Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
 
Vec_Ptr_tNwk_ManRetimeCutForward (Nwk_Man_t *pMan, int nLatches, int fVerbose)
 
Vec_Ptr_tNwk_ManRetimeCutBackward (Nwk_Man_t *pMan, int nLatches, int fVerbose)
 

Variables

ABC_NAMESPACE_IMPL_START int DepthFwd
 
ABC_NAMESPACE_IMPL_START int DepthBwd
 
ABC_NAMESPACE_IMPL_START int DepthFwdMax
 
ABC_NAMESPACE_IMPL_START int DepthBwdMax
 

Function Documentation

static Nwk_ManIncrementTravIdFlow ( Nwk_Man_t pMan)
inlinestatic

Definition at line 86 of file nwkFlow_depth.c.

87 {
88  Nwk_ManIncrementTravId( pMan );
89  Nwk_ManIncrementTravId( pMan );
90  Nwk_ManIncrementTravId( pMan );
91 }
ABC_DLL void Nwk_ManIncrementTravId(Nwk_Man_t *pNtk)
DECLARATIONS ///.
Definition: nwkUtil.c:47
void Nwk_ManMarkTfiCone_rec ( Nwk_Obj_t pObj)

FUNCTION DEFINITIONS ///.

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

Synopsis [Marks TFI of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 114 of file nwkFlow_depth.c.

115 {
116  Nwk_Obj_t * pNext;
117  int i;
118  if ( pObj->MarkA )
119  return;
120  pObj->MarkA = 1;
121  Nwk_ObjForEachFanin( pObj, pNext, i )
122  Nwk_ManMarkTfiCone_rec( pNext );
123 }
void Nwk_ManMarkTfiCone_rec(Nwk_Obj_t *pObj)
FUNCTION DEFINITIONS ///.
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
void Nwk_ManMarkTfoCone_rec ( Nwk_Obj_t pObj)

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

Synopsis [Marks TFO of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file nwkFlow_depth.c.

137 {
138  Nwk_Obj_t * pNext;
139  int i;
140  if ( pObj->MarkA )
141  return;
142  pObj->MarkA = 1;
143  Nwk_ObjForEachFanout( pObj, pNext, i )
144  Nwk_ManMarkTfoCone_rec( pNext );
145 }
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
#define Nwk_ObjForEachFanout(pObj, pFanout, i)
Definition: nwk.h:201
void Nwk_ManMarkTfoCone_rec(Nwk_Obj_t *pObj)
int Nwk_ManPushBackwardBot_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)
static

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

Synopsis [Pushing the flow through the bottom part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 317 of file nwkFlow_depth.c.

318 {
319  if ( Nwk_ObjVisitedBot(pObj) )
320  return 0;
321  Nwk_ObjSetVisitedBot(pObj);
322  // propagate through the internal edge
323  if ( Nwk_ObjHasFlow(pObj) )
324  {
325  if ( Nwk_ObjPred(pObj) )
326  if ( Nwk_ManPushBackwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
327  return Nwk_ObjSetPred( pObj, pPred );
328  }
329  else if ( Nwk_ManPushBackwardTop_rec(pObj, pObj) )
330  {
331  Nwk_ObjSetFlow( pObj );
332  return Nwk_ObjSetPred( pObj, pPred );
333  }
334  return 0;
335 }
static Nwk_Obj_t * Nwk_ObjPred(Nwk_Obj_t *pObj)
DECLARATIONS ///.
Definition: nwkFlow_depth.c:41
static void Nwk_ObjSetFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:48
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
static int Nwk_ObjVisitedBot(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:60
static void Nwk_ObjSetVisitedBot(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:68
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
static int Nwk_ManPushBackwardTop_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
int Nwk_ManPushBackwardFast_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)

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

Synopsis [Fast backward flow pushing.]

Description []

SideEffects []

SeeAlso []

Definition at line 192 of file nwkFlow_depth.c.

193 {
194  Nwk_Obj_t * pNext;
195  int i;
196  if ( Nwk_ObjIsTravIdCurrent( pObj ) )
197  return 0;
198  Nwk_ObjSetTravIdCurrent( pObj );
199  if ( Nwk_ObjHasFlow(pObj) )
200  return 0;
201  if ( Nwk_ObjIsSink(pObj) )
202  {
203  Nwk_ObjSetFlow(pObj);
204  return Nwk_ObjSetPred( pObj, pPred );
205  }
206  Nwk_ObjForEachFanin( pObj, pNext, i )
207  if ( Nwk_ManPushBackwardFast_rec( pNext, pObj ) )
208  {
209  Nwk_ObjSetFlow(pObj);
210  return Nwk_ObjSetPred( pObj, pPred );
211  }
212  return 0;
213 }
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static void Nwk_ObjSetFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:48
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
int Nwk_ManPushBackwardFast_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static void Nwk_ObjSetTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:166
static int Nwk_ObjIsTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:168
if(last==0)
Definition: sparse_int.h:34
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
static int Nwk_ObjIsSink(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:44
int Nwk_ManPushBackwardTop_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)
static

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

Synopsis [Pushing the flow through the top part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 348 of file nwkFlow_depth.c.

349 {
350  Nwk_Obj_t * pNext;
351  int i;
352  if ( Nwk_ObjVisitedTop(pObj) )
353  return 0;
354  Nwk_ObjSetVisitedTop(pObj);
355  // check if this is the sink
356  if ( Nwk_ObjIsSink(pObj) )
357  return 1;
358  // try to push through the fanins
359  Nwk_ObjForEachFanin( pObj, pNext, i )
360  if ( Nwk_ManPushBackwardBot_rec( pNext, pPred ) )
361  return 1;
362  // try to push through the fanouts
363  Nwk_ObjForEachFanout( pObj, pNext, i )
364  if ( !Nwk_ObjIsCo(pObj) && Nwk_ManPushBackwardTop_rec( pNext, pPred ) )
365  return 1;
366  // redirect the flow
367  if ( Nwk_ObjHasFlow(pObj) )
368  if ( Nwk_ObjPred(pObj) && Nwk_ManPushBackwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
369  {
370  Nwk_ObjClearFlow( pObj );
371  return Nwk_ObjSetPred( pObj, NULL );
372  }
373  return 0;
374 }
static Nwk_Obj_t * Nwk_ObjPred(Nwk_Obj_t *pObj)
DECLARATIONS ///.
Definition: nwkFlow_depth.c:41
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
static void Nwk_ObjSetVisitedTop(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:77
#define Nwk_ObjForEachFanout(pObj, pFanout, i)
Definition: nwk.h:201
static int Nwk_ObjIsCo(Nwk_Obj_t *p)
Definition: nwk.h:147
static int Nwk_ManPushBackwardBot_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
if(last==0)
Definition: sparse_int.h:34
static void Nwk_ObjClearFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:49
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
static int Nwk_ObjIsSink(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:44
static int Nwk_ManPushBackwardTop_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ObjVisitedTop(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:64
int Nwk_ManPushForwardBot_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)
static

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

Synopsis [Pushing the flow through the bottom part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 226 of file nwkFlow_depth.c.

227 {
228  Nwk_Obj_t * pNext;
229  int i;
230  if ( Nwk_ObjVisitedBot(pObj) )
231  return 0;
232  Nwk_ObjSetVisitedBot(pObj);
233  DepthFwd++;
234  if ( DepthFwdMax < DepthFwd )
236  // propagate through the internal edge
237  if ( Nwk_ObjHasFlow(pObj) )
238  {
239  if ( Nwk_ObjPred(pObj) )
240  if ( Nwk_ManPushForwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
241  {
242  DepthFwd--;
243  return Nwk_ObjSetPred( pObj, pPred );
244  }
245  }
246  else if ( Nwk_ManPushForwardTop_rec(pObj, pObj) )
247  {
248  DepthFwd--;
249  Nwk_ObjSetFlow( pObj );
250  return Nwk_ObjSetPred( pObj, pPred );
251  }
252  // try to push through the fanins
253  Nwk_ObjForEachFanin( pObj, pNext, i )
254  if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
255  {
256  DepthFwd--;
257  return 1;
258  }
259  DepthFwd--;
260  return 0;
261 }
static Nwk_Obj_t * Nwk_ObjPred(Nwk_Obj_t *pObj)
DECLARATIONS ///.
Definition: nwkFlow_depth.c:41
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static void Nwk_ObjSetFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:48
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
static int Nwk_ObjVisitedBot(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:60
static int Nwk_ManPushForwardBot_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ManPushForwardTop_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
if(last==0)
Definition: sparse_int.h:34
ABC_NAMESPACE_IMPL_START int DepthFwd
Definition: nwkFlow_depth.c:34
ABC_NAMESPACE_IMPL_START int DepthFwdMax
Definition: nwkFlow_depth.c:34
static void Nwk_ObjSetVisitedBot(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:68
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
int Nwk_ManPushForwardFast_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)

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

Synopsis [Fast forward flow pushing.]

Description []

SideEffects []

SeeAlso []

Definition at line 158 of file nwkFlow_depth.c.

159 {
160  Nwk_Obj_t * pNext;
161  int i;
162  if ( Nwk_ObjIsTravIdCurrent( pObj ) )
163  return 0;
164  Nwk_ObjSetTravIdCurrent( pObj );
165  if ( Nwk_ObjHasFlow(pObj) )
166  return 0;
167  if ( Nwk_ObjIsSink(pObj) )
168  {
169  Nwk_ObjSetFlow(pObj);
170  return Nwk_ObjSetPred( pObj, pPred );
171  }
172  Nwk_ObjForEachFanout( pObj, pNext, i )
173  if ( Nwk_ManPushForwardFast_rec( pNext, pObj ) )
174  {
175  Nwk_ObjSetFlow(pObj);
176  return Nwk_ObjSetPred( pObj, pPred );
177  }
178  return 0;
179 }
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static void Nwk_ObjSetFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:48
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
#define Nwk_ObjForEachFanout(pObj, pFanout, i)
Definition: nwk.h:201
static void Nwk_ObjSetTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:166
int Nwk_ManPushForwardFast_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ObjIsTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:168
if(last==0)
Definition: sparse_int.h:34
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
static int Nwk_ObjIsSink(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:44
int Nwk_ManPushForwardTop_rec ( Nwk_Obj_t pObj,
Nwk_Obj_t pPred 
)
static

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

Synopsis [Pushing the flow through the top part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 274 of file nwkFlow_depth.c.

275 {
276  Nwk_Obj_t * pNext;
277  int i;
278  if ( Nwk_ObjVisitedTop(pObj) )
279  return 0;
280  Nwk_ObjSetVisitedTop(pObj);
281  // check if this is the sink
282  if ( Nwk_ObjIsSink(pObj) )
283  return 1;
284  DepthFwd++;
285  if ( DepthFwdMax < DepthFwd )
287  // try to push through the fanouts
288  Nwk_ObjForEachFanout( pObj, pNext, i )
289  if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
290  {
291  DepthFwd--;
292  return 1;
293  }
294  // redirect the flow
295  if ( Nwk_ObjHasFlow(pObj) && !Nwk_ObjIsCi(pObj) )
296  if ( Nwk_ManPushForwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
297  {
298  DepthFwd--;
299  Nwk_ObjClearFlow( pObj );
300  return Nwk_ObjSetPred( pObj, NULL );
301  }
302  DepthFwd--;
303  return 0;
304 }
static int Nwk_ObjIsCi(Nwk_Obj_t *p)
Definition: nwk.h:146
static Nwk_Obj_t * Nwk_ObjPred(Nwk_Obj_t *pObj)
DECLARATIONS ///.
Definition: nwkFlow_depth.c:41
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static int Nwk_ObjSetPred(Nwk_Obj_t *pObj, Nwk_Obj_t *p)
Definition: nwkFlow_depth.c:42
static void Nwk_ObjSetVisitedTop(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:77
#define Nwk_ObjForEachFanout(pObj, pFanout, i)
Definition: nwk.h:201
static int Nwk_ManPushForwardBot_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
if(last==0)
Definition: sparse_int.h:34
static void Nwk_ObjClearFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:49
ABC_NAMESPACE_IMPL_START int DepthFwd
Definition: nwkFlow_depth.c:34
ABC_NAMESPACE_IMPL_START int DepthFwdMax
Definition: nwkFlow_depth.c:34
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
static int Nwk_ObjIsSink(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:44
static int Nwk_ObjVisitedTop(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:64
Vec_Ptr_t* Nwk_ManRetimeCutBackward ( Nwk_Man_t pMan,
int  nLatches,
int  fVerbose 
)

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

Synopsis [Computes minimum cut for backward retiming.]

Description []

SideEffects []

SeeAlso []

Definition at line 548 of file nwkFlow_depth.c.

549 {
550  Vec_Ptr_t * vNodes;
551  Nwk_Obj_t * pObj;
552  int i, RetValue, Counter = 0, Counter2 = 0;
553  clock_t clk = clock();
554  // set the sequential parameters
555  pMan->nLatches = nLatches;
556  pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
557  pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
558  // mark the CIs, the TFI of POs, and the constant nodes
559  Nwk_ManForEachCi( pMan, pObj, i )
560  pObj->MarkA = 1;
561  Nwk_ManForEachPoSeq( pMan, pObj, i )
562  Nwk_ManMarkTfiCone_rec( pObj );
563  Nwk_ManForEachNode( pMan, pObj, i )
564  if ( Nwk_ObjFaninNum(pObj) == 0 )
565  pObj->MarkA = 1;
566  // start flow computation from each LI driver
568  Nwk_ManForEachLiSeq( pMan, pObj, i )
569  {
570  if ( !Nwk_ManPushBackwardFast_rec( Nwk_ObjFanin0(pObj), NULL ) )
571  continue;
573  Counter++;
574  }
575  if ( fVerbose )
576  printf( "Backward: Max-flow = %4d -> ", Counter );
577  // continue flow computation from each LI driver
579  Nwk_ManForEachLiSeq( pMan, pObj, i )
580  {
581  if ( !Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL ) )
582  continue;
584  Counter2++;
585  }
586  if ( fVerbose )
587  printf( "%4d. ", Counter+Counter2 );
588  // repeat flow computation from each LI driver
589  if ( Counter2 > 0 )
590  {
592  Nwk_ManForEachLiSeq( pMan, pObj, i )
593  {
594  RetValue = Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL );
595  assert( !RetValue );
596  }
597  }
598  // cut is a set of nodes whose bottom is visited but top is not visited
599  vNodes = Vec_PtrAlloc( Counter+Counter2 );
600  Nwk_ManForEachObj( pMan, pObj, i )
601  {
602  if ( Nwk_ObjVisitedBotOnly(pObj) )
603  {
604  assert( Nwk_ObjHasFlow(pObj) );
605  assert( !Nwk_ObjIsCo(pObj) );
606  Vec_PtrPush( vNodes, pObj );
607  }
608  }
609  // count CO drivers
610  Counter = 0;
611  Nwk_ManForEachLiSeq( pMan, pObj, i )
613  Counter++;
614  Nwk_ManCleanMarks( pMan );
615  assert( Nwk_ManRetimeVerifyCutBackward(pMan, vNodes) );
616  if ( fVerbose )
617  {
618  printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
619  PRT( "Time", clock() - clk );
620  }
621  return vNodes;
622 }
void Nwk_ManMarkTfiCone_rec(Nwk_Obj_t *pObj)
FUNCTION DEFINITIONS ///.
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
ABC_DLL void Nwk_ManCleanMarks(Nwk_Man_t *pNtk)
Definition: nwkUtil.c:464
int Nwk_ManRetimeVerifyCutBackward(Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
int nTruePis
Definition: nwk.h:82
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
#define Nwk_ManForEachCi(p, pObj, i)
ITERATORS ///.
Definition: nwk.h:179
int Nwk_ManPushBackwardFast_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
static int Nwk_ObjFaninNum(Nwk_Obj_t *p)
Definition: nwk.h:137
static Nwk_ManIncrementTravIdFlow(Nwk_Man_t *pMan)
Definition: nwkFlow_depth.c:86
static int Nwk_ObjIsCo(Nwk_Obj_t *p)
Definition: nwk.h:147
#define Nwk_ManForEachPoSeq(p, pObj, i)
Definition: nwk.h:207
static int Nwk_ManPushBackwardBot_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ObjVisitedBotOnly(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:56
if(last==0)
Definition: sparse_int.h:34
static int Counter
static int Nwk_ManCiNum(Nwk_Man_t *p)
MACRO DEFINITIONS ///.
Definition: nwk.h:125
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
#define Nwk_ManForEachLiSeq(p, pObj, i)
Definition: nwk.h:211
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
#define Nwk_ManForEachObj(p, pObj, i)
Definition: nwk.h:189
static Nwk_Obj_t * Nwk_ObjFanin0(Nwk_Obj_t *p)
Definition: nwk.h:140
#define assert(ex)
Definition: util_old.h:213
int nLatches
Definition: nwk.h:81
int nTruePos
Definition: nwk.h:83
static int Nwk_ManCoNum(Nwk_Man_t *p)
Definition: nwk.h:126
#define Nwk_ManForEachNode(p, pObj, i)
Definition: nwk.h:192
Vec_Ptr_t* Nwk_ManRetimeCutForward ( Nwk_Man_t pMan,
int  nLatches,
int  fVerbose 
)

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

Synopsis [Computes minimum cut for forward retiming.]

Description []

SideEffects []

SeeAlso []

Definition at line 463 of file nwkFlow_depth.c.

464 {
465  Vec_Ptr_t * vNodes;
466  Nwk_Obj_t * pObj;
467  int i, RetValue, Counter = 0, Counter2 = 0;
468  clock_t clk = clock();
469  // set the sequential parameters
470  pMan->nLatches = nLatches;
471  pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches;
472  pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches;
473  // mark the COs and the TFO of PIs
474  Nwk_ManForEachCo( pMan, pObj, i )
475  pObj->MarkA = 1;
476  Nwk_ManForEachPiSeq( pMan, pObj, i )
477  Nwk_ManMarkTfoCone_rec( pObj );
478  // start flow computation from each LO
480  Nwk_ManForEachLoSeq( pMan, pObj, i )
481  {
482  if ( !Nwk_ManPushForwardFast_rec( pObj, NULL ) )
483  continue;
485  Counter++;
486  }
487  if ( fVerbose )
488  printf( "Forward: Max-flow = %4d -> ", Counter );
489  // continue flow computation from each LO
490  DepthFwdMax = DepthFwd = 0;
492  Nwk_ManForEachLoSeq( pMan, pObj, i )
493  {
494  printf( "%d ", DepthFwdMax );
495  if ( !Nwk_ManPushForwardBot_rec( pObj, NULL ) )
496  continue;
497  assert( DepthFwd == 0 );
499  Counter2++;
500  }
501  printf( "DepthMax = %d.\n", DepthFwdMax );
502  if ( fVerbose )
503  printf( "%4d. ", Counter+Counter2 );
504  // repeat flow computation from each LO
505  if ( Counter2 > 0 )
506  {
508  Nwk_ManForEachLoSeq( pMan, pObj, i )
509  {
510  RetValue = Nwk_ManPushForwardBot_rec( pObj, NULL );
511  assert( !RetValue );
512  }
513  }
514  // cut is a set of nodes whose bottom is visited but top is not visited
515  vNodes = Vec_PtrAlloc( Counter+Counter2 );
516  Counter = 0;
517  Nwk_ManForEachObj( pMan, pObj, i )
518  {
519  if ( Nwk_ObjVisitedBotOnly(pObj) )
520  {
521  assert( Nwk_ObjHasFlow(pObj) );
522  assert( !Nwk_ObjIsCo(pObj) );
523  Vec_PtrPush( vNodes, pObj );
524  Counter += Nwk_ObjIsCi(pObj);
525  }
526  }
527  Nwk_ManCleanMarks( pMan );
528  assert( Nwk_ManRetimeVerifyCutForward(pMan, vNodes) );
529  if ( fVerbose )
530  {
531  printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter );
532  PRT( "Time", clock() - clk );
533  }
534  return vNodes;
535 }
static int Nwk_ObjIsCi(Nwk_Obj_t *p)
Definition: nwk.h:146
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
ABC_DLL void Nwk_ManCleanMarks(Nwk_Man_t *pNtk)
Definition: nwkUtil.c:464
#define Nwk_ManForEachCo(p, pObj, i)
Definition: nwk.h:181
int nTruePis
Definition: nwk.h:82
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
int Nwk_ManRetimeVerifyCutForward(Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
#define Nwk_ManForEachLoSeq(p, pObj, i)
Definition: nwk.h:209
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
#define Nwk_ManForEachPiSeq(p, pObj, i)
Definition: nwk.h:205
static Nwk_ManIncrementTravIdFlow(Nwk_Man_t *pMan)
Definition: nwkFlow_depth.c:86
int Nwk_ManPushForwardFast_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ObjIsCo(Nwk_Obj_t *p)
Definition: nwk.h:147
static int Nwk_ManPushForwardBot_rec(Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
static int Nwk_ObjVisitedBotOnly(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:56
static int Counter
ABC_NAMESPACE_IMPL_START int DepthFwd
Definition: nwkFlow_depth.c:34
ABC_NAMESPACE_IMPL_START int DepthFwdMax
Definition: nwkFlow_depth.c:34
static int Nwk_ManCiNum(Nwk_Man_t *p)
MACRO DEFINITIONS ///.
Definition: nwk.h:125
static int Nwk_ObjHasFlow(Nwk_Obj_t *pObj)
Definition: nwkFlow_depth.c:47
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
void Nwk_ManMarkTfoCone_rec(Nwk_Obj_t *pObj)
#define Nwk_ManForEachObj(p, pObj, i)
Definition: nwk.h:189
#define assert(ex)
Definition: util_old.h:213
int nLatches
Definition: nwk.h:81
int nTruePos
Definition: nwk.h:83
static int Nwk_ManCoNum(Nwk_Man_t *p)
Definition: nwk.h:126
int Nwk_ManRetimeVerifyCutBackward ( Nwk_Man_t pMan,
Vec_Ptr_t vNodes 
)

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

Synopsis [Verifies the forward cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 447 of file nwkFlow_depth.c.

448 {
449  return 1;
450 }
int Nwk_ManRetimeVerifyCutForward ( Nwk_Man_t pMan,
Vec_Ptr_t vNodes 
)

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

Synopsis [Verifies the forward cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 415 of file nwkFlow_depth.c.

416 {
417  Nwk_Obj_t * pObj;
418  int i;
419  // mark the nodes
420  Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
421  {
422  assert( pObj->MarkA == 0 );
423  pObj->MarkA = 1;
424  }
425  // traverse from the COs
426  Nwk_ManIncrementTravId( pMan );
427  Nwk_ManForEachCo( pMan, pObj, i )
428  if ( !Nwk_ManVerifyCut_rec( pObj ) )
429  printf( "Nwk_ManRetimeVerifyCutForward(): Internal cut verification failed.\n" );
430  // unmark the nodes
431  Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i )
432  pObj->MarkA = 0;
433  return 1;
434 }
#define Nwk_ManForEachCo(p, pObj, i)
Definition: nwk.h:181
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
int Nwk_ManRetimeVerifyCutForward(Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
if(last==0)
Definition: sparse_int.h:34
int Nwk_ManVerifyCut_rec(Nwk_Obj_t *pObj)
ABC_DLL void Nwk_ManIncrementTravId(Nwk_Man_t *pNtk)
DECLARATIONS ///.
Definition: nwkUtil.c:47
#define assert(ex)
Definition: util_old.h:213
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
int Nwk_ManVerifyCut_rec ( Nwk_Obj_t pObj)

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

Synopsis [Returns 0 if there is an unmarked path to a CI.]

Description []

SideEffects []

SeeAlso []

Definition at line 387 of file nwkFlow_depth.c.

388 {
389  Nwk_Obj_t * pNext;
390  int i;
391  if ( pObj->MarkA )
392  return 1;
393  if ( Nwk_ObjIsLo(pObj) )
394  return 0;
395  if ( Nwk_ObjIsTravIdCurrent( pObj ) )
396  return 1;
397  Nwk_ObjSetTravIdCurrent( pObj );
398  Nwk_ObjForEachFanin( pObj, pNext, i )
399  if ( !Nwk_ManVerifyCut_rec( pNext ) )
400  return 0;
401  return 1;
402 }
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
static void Nwk_ObjSetTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:166
static int Nwk_ObjIsLo(Nwk_Obj_t *p)
Definition: nwk.h:153
static int Nwk_ObjIsTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:168
if(last==0)
Definition: sparse_int.h:34
int Nwk_ManVerifyCut_rec(Nwk_Obj_t *pObj)
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
static void Nwk_ObjClearFlow ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 49 of file nwkFlow_depth.c.

49 { pObj->MarkB = 0; }
static int Nwk_ObjHasFlow ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 47 of file nwkFlow_depth.c.

47 { return pObj->MarkB; }
static int Nwk_ObjIsSink ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 44 of file nwkFlow_depth.c.

44 { return pObj->MarkA; }
static Nwk_Obj_t* Nwk_ObjPred ( Nwk_Obj_t pObj)
inlinestatic

DECLARATIONS ///.

Definition at line 41 of file nwkFlow_depth.c.

41 { return pObj->pCopy; }
static void Nwk_ObjSetFlow ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 48 of file nwkFlow_depth.c.

48 { pObj->MarkB = 1; }
static int Nwk_ObjSetPred ( Nwk_Obj_t pObj,
Nwk_Obj_t p 
)
inlinestatic

Definition at line 42 of file nwkFlow_depth.c.

42 { pObj->pCopy = p; return 1; }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static void Nwk_ObjSetSink ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 45 of file nwkFlow_depth.c.

45 { pObj->MarkA = 1; }
static void Nwk_ObjSetVisitedBot ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 68 of file nwkFlow_depth.c.

69 {
70  if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
71  pObj->TravId = pObj->pMan->nTravIds - 2;
72  else if ( pObj->TravId == pObj->pMan->nTravIds - 1 )
73  pObj->TravId = pObj->pMan->nTravIds;
74  else
75  assert( 0 );
76 }
#define assert(ex)
Definition: util_old.h:213
static void Nwk_ObjSetVisitedTop ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 77 of file nwkFlow_depth.c.

78 {
79  if ( pObj->TravId < pObj->pMan->nTravIds - 2 )
80  pObj->TravId = pObj->pMan->nTravIds - 1;
81  else if ( pObj->TravId == pObj->pMan->nTravIds - 2 )
82  pObj->TravId = pObj->pMan->nTravIds;
83  else
84  assert( 0 );
85 }
#define assert(ex)
Definition: util_old.h:213
static int Nwk_ObjVisitedBot ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 60 of file nwkFlow_depth.c.

61 {
62  return pObj->TravId == pObj->pMan->nTravIds - 2 || pObj->TravId == pObj->pMan->nTravIds;
63 }
static int Nwk_ObjVisitedBotOnly ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 56 of file nwkFlow_depth.c.

57 {
58  return pObj->TravId == pObj->pMan->nTravIds - 2;
59 }
static int Nwk_ObjVisitedTop ( Nwk_Obj_t pObj)
inlinestatic

Definition at line 64 of file nwkFlow_depth.c.

65 {
66  return pObj->TravId == pObj->pMan->nTravIds - 1 || pObj->TravId == pObj->pMan->nTravIds;
67 }

Variable Documentation

Definition at line 34 of file nwkFlow_depth.c.

ABC_NAMESPACE_IMPL_START int DepthBwdMax

Definition at line 34 of file nwkFlow_depth.c.

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

FileName [nwkFlow.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Netlist representation.]

Synopsis [Max-flow/min-cut computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:
nwkFlow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 34 of file nwkFlow_depth.c.

ABC_NAMESPACE_IMPL_START int DepthFwdMax

Definition at line 34 of file nwkFlow_depth.c.