abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
abcFxu.c File Reference
#include "base/abc/abc.h"
#include "opt/fxu/fxu.h"

Go to the source code of this file.

Functions

static ABC_NAMESPACE_IMPL_START int Abc_NtkFxuCheck (Abc_Ntk_t *pNtk)
 DECLARATIONS ///. More...
 
static void Abc_NtkFxuCollectInfo (Abc_Ntk_t *pNtk, Fxu_Data_t *p)
 
static void Abc_NtkFxuReconstruct (Abc_Ntk_t *pNtk, Fxu_Data_t *p)
 
int Fxu_FastExtract (Fxu_Data_t *pData)
 FUNCTION DEFINITIONS ///. More...
 
void Abc_NtkSetDefaultFxParams (Fxu_Data_t *p)
 FUNCTION DEFINITIONS ///. More...
 
int Abc_NtkFastExtract (Abc_Ntk_t *pNtk, Fxu_Data_t *p)
 
void Abc_NtkFxuFreeInfo (Fxu_Data_t *p)
 

Function Documentation

int Abc_NtkFastExtract ( Abc_Ntk_t *  pNtk,
Fxu_Data_t *  p 
)

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

Synopsis [Performs fast_extract on the current network.]

Description [Takes the network and the maximum number of nodes to extract. Uses the concurrent double-cube and single cube divisor extraction procedure. Modifies the network in the end, after extracting all nodes. Note that Ntk_NetworkSweep() may increase the performance of this procedure because the single-literal nodes will not be created in the sparse matrix. Returns 1 if the network has been changed.]

SideEffects []

SeeAlso []

Definition at line 83 of file abcFxu.c.

84 {
85  assert( Abc_NtkIsLogic(pNtk) );
86  // if the network is already in the SOP form, it may come from BLIF file
87  // and it may not be SCC-free, in which case FXU will not work correctly
88  if ( Abc_NtkIsSopLogic(pNtk) )
89  { // to make sure the SOPs are SCC-free
90 // Abc_NtkSopToBdd(pNtk);
91 // Abc_NtkBddToSop(pNtk);
92  }
93  // get the network in the SOP form
94  if ( !Abc_NtkToSop(pNtk, 0) )
95  {
96  printf( "Abc_NtkFastExtract(): Converting to SOPs has failed.\n" );
97  return 0;
98  }
99  // check if the network meets the requirements
100  if ( !Abc_NtkFxuCheck(pNtk) )
101  {
102  printf( "Abc_NtkFastExtract: Nodes have duplicated or complemented fanins. FXU is not performed.\n" );
103  return 0;
104  }
105  // sweep removes useless nodes
106  Abc_NtkCleanup( pNtk, 0 );
107  // collect information about the covers
108  Abc_NtkFxuCollectInfo( pNtk, p );
109  // call the fast extract procedure
110  if ( Fxu_FastExtract(p) > 0 )
111  {
112  // update the network
113  Abc_NtkFxuReconstruct( pNtk, p );
114  // make sure everything is okay
115  if ( !Abc_NtkCheck( pNtk ) )
116  printf( "Abc_NtkFastExtract: The network check has failed.\n" );
117  return 1;
118  }
119  else
120  printf( "Warning: The network has not been changed by \"fx\".\n" );
121  return 0;
122 }
Abc_NtkIsLogic
static int Abc_NtkIsLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:250
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Abc_NtkFxuReconstruct
static void Abc_NtkFxuReconstruct(Abc_Ntk_t *pNtk, Fxu_Data_t *p)
Definition: abcFxu.c:234
Abc_NtkCheck
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
Abc_NtkIsSopLogic
static int Abc_NtkIsSopLogic(Abc_Ntk_t *pNtk)
Definition: abc.h:264
Abc_NtkCleanup
ABC_DLL int Abc_NtkCleanup(Abc_Ntk_t *pNtk, int fVerbose)
Definition: abcSweep.c:476
Abc_NtkToSop
ABC_DLL int Abc_NtkToSop(Abc_Ntk_t *pNtk, int fDirect)
Definition: abcFunc.c:1124
Abc_NtkFxuCheck
static ABC_NAMESPACE_IMPL_START int Abc_NtkFxuCheck(Abc_Ntk_t *pNtk)
DECLARATIONS ///.
Definition: abcFxu.c:136
assert
#define assert(ex)
Definition: util_old.h:213
Fxu_FastExtract
int Fxu_FastExtract(Fxu_Data_t *pData)
FUNCTION DEFINITIONS ///.
Definition: fxu.c:58
Abc_NtkFxuCollectInfo
static void Abc_NtkFxuCollectInfo(Abc_Ntk_t *pNtk, Fxu_Data_t *p)
Definition: abcFxu.c:169
int Abc_NtkFxuCheck ( Abc_Ntk_t *  pNtk)
static

DECLARATIONS ///.

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

FileName [abcFxu.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Interface with the fast extract package.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

]

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

Synopsis [Makes sure the nodes do not have complemented and duplicated fanins.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file abcFxu.c.

137 {
138  Abc_Obj_t * pNode, * pFanin1, * pFanin2;
139  int n, i, k;
140  Abc_NtkForEachNode( pNtk, pNode, n )
141  {
142  Abc_ObjForEachFanin( pNode, pFanin1, i )
143  {
144  if ( i < 2 && Abc_ObjFaninC(pNode, i) )
145  return 0;
146  Abc_ObjForEachFanin( pNode, pFanin2, k )
147  {
148  if ( i == k )
149  continue;
150  if ( pFanin1 == pFanin2 )
151  return 0;
152  }
153  }
154  }
155  return 1;
156 }
Abc_Obj_t_
Definition: abc.h:128
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Abc_ObjFaninC
static int Abc_ObjFaninC(Abc_Obj_t *pObj, int i)
Definition: abc.h:379
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
void Abc_NtkFxuCollectInfo ( Abc_Ntk_t *  pNtk,
Fxu_Data_t *  p 
)
static

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

Synopsis [Collect information about the network for fast_extract.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file abcFxu.c.

170 {
171  Abc_Obj_t * pNode;
172  int i;
173  // add information to the manager
174  p->pManSop = (Mem_Flex_t *)pNtk->pManFunc;
175  p->vSops = Vec_PtrAlloc(0);
176  p->vFanins = Vec_PtrAlloc(0);
177  p->vSopsNew = Vec_PtrAlloc(0);
178  p->vFaninsNew = Vec_PtrAlloc(0);
179  Vec_PtrFill( p->vSops, Abc_NtkObjNumMax(pNtk), NULL );
180  Vec_PtrFill( p->vFanins, Abc_NtkObjNumMax(pNtk), NULL );
181  Vec_PtrFill( p->vSopsNew, Abc_NtkObjNumMax(pNtk) + p->nNodesExt, NULL );
182  Vec_PtrFill( p->vFaninsNew, Abc_NtkObjNumMax(pNtk) + p->nNodesExt, NULL );
183  // add SOPs and fanin array
184  Abc_NtkForEachNode( pNtk, pNode, i )
185  {
186  if ( Abc_SopGetVarNum((char *)pNode->pData) < 2 )
187  continue;
188  if ( Abc_SopGetCubeNum((char *)pNode->pData) < 1 )
189  continue;
190  p->vSops->pArray[i] = pNode->pData;
191  p->vFanins->pArray[i] = &pNode->vFanins;
192  }
193  p->nNodesOld = Abc_NtkObjNumMax(pNtk);
194 }
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_PtrFill
static void Vec_PtrFill(Vec_Ptr_t *p, int nSize, void *Entry)
Definition: vecPtr.h:449
Abc_SopGetCubeNum
ABC_DLL int Abc_SopGetCubeNum(char *pSop)
Definition: abcSop.c:489
Abc_Obj_t_::vFanins
Vec_Int_t vFanins
Definition: abc.h:143
Mem_Flex_t_
Definition: mem.c:55
Abc_Obj_t_
Definition: abc.h:128
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Abc_SopGetVarNum
ABC_DLL int Abc_SopGetVarNum(char *pSop)
Definition: abcSop.c:536
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
void Abc_NtkFxuFreeInfo ( Fxu_Data_t *  p)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file abcFxu.c.

208 {
209  int i;
210  // free the arrays of new fanins
211  if ( p->vFaninsNew )
212  for ( i = 0; i < p->vFaninsNew->nSize; i++ )
213  if ( p->vFaninsNew->pArray[i] )
214  Vec_IntFree( (Vec_Int_t *)p->vFaninsNew->pArray[i] );
215  // free the arrays
216  if ( p->vSops ) Vec_PtrFree( p->vSops );
217  if ( p->vSopsNew ) Vec_PtrFree( p->vSopsNew );
218  if ( p->vFanins ) Vec_PtrFree( p->vFanins );
219  if ( p->vFaninsNew ) Vec_PtrFree( p->vFaninsNew );
220 // ABC_FREE( p );
221 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
void Abc_NtkFxuReconstruct ( Abc_Ntk_t *  pNtk,
Fxu_Data_t *  p 
)
static

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

Synopsis [Reconstructs the network after FX.]

Description []

SideEffects []

SeeAlso []

Definition at line 234 of file abcFxu.c.

235 {
236  Vec_Int_t * vFanins;
237  Abc_Obj_t * pNode, * pFanin;
238  int i, k;
239 
240  assert( p->vFanins->nSize < p->vFaninsNew->nSize );
241  // create the new nodes
242  for ( i = p->vFanins->nSize; i < p->vFanins->nSize + p->nNodesNew; i++ )
243  {
244  // start the node
245  pNode = Abc_NtkCreateNode( pNtk );
246  assert( i == (int)pNode->Id );
247  }
248  // update the old nodes
249  for ( i = 0; i < p->vFanins->nSize; i++ )
250  {
251  // the new array of fanins
252  vFanins = (Vec_Int_t *)p->vFaninsNew->pArray[i];
253  if ( vFanins == NULL )
254  continue;
255  // remove old fanins
256  pNode = Abc_NtkObj( pNtk, i );
257  Abc_ObjRemoveFanins( pNode );
258  // add new fanins
259  vFanins = (Vec_Int_t *)p->vFaninsNew->pArray[i];
260  for ( k = 0; k < vFanins->nSize; k++ )
261  {
262  pFanin = Abc_NtkObj( pNtk, vFanins->pArray[k] );
263  Abc_ObjAddFanin( pNode, pFanin );
264  }
265  pNode->pData = p->vSopsNew->pArray[i];
266  assert( pNode->pData != NULL );
267  }
268  // set up the new nodes
269  for ( i = p->vFanins->nSize; i < p->vFanins->nSize + p->nNodesNew; i++ )
270  {
271  // get the new node
272  pNode = Abc_NtkObj( pNtk, i );
273  // add the fanins
274  vFanins = (Vec_Int_t *)p->vFaninsNew->pArray[i];
275  for ( k = 0; k < vFanins->nSize; k++ )
276  {
277  pFanin = Abc_NtkObj( pNtk, vFanins->pArray[k] );
278  Abc_ObjAddFanin( pNode, pFanin );
279  }
280  pNode->pData = p->vSopsNew->pArray[i];
281  assert( pNode->pData != NULL );
282  }
283 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Abc_NtkObj
static Abc_Obj_t * Abc_NtkObj(Abc_Ntk_t *pNtk, int i)
Definition: abc.h:314
for
for(p=first;p->value< newval;p=p->next)
Abc_ObjAddFanin
ABC_DLL void Abc_ObjAddFanin(Abc_Obj_t *pObj, Abc_Obj_t *pFanin)
Definition: abcFanio.c:84
Abc_Obj_t_
Definition: abc.h:128
if
if(last==0)
Definition: sparse_int.h:34
Abc_ObjRemoveFanins
ABC_DLL void Abc_ObjRemoveFanins(Abc_Obj_t *pObj)
Definition: abcFanio.c:141
Abc_Obj_t_::Id
int Id
Definition: abc.h:132
Abc_NtkCreateNode
static Abc_Obj_t * Abc_NtkCreateNode(Abc_Ntk_t *pNtk)
Definition: abc.h:308
assert
#define assert(ex)
Definition: util_old.h:213
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
void Abc_NtkSetDefaultFxParams ( Fxu_Data_t *  p)

FUNCTION DEFINITIONS ///.

MACRO DEFINITIONS ///.

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

Synopsis [Sets default values of the FXU parameters.]

Description []

SideEffects []

SeeAlso []

Definition at line 52 of file abcFxu.c.

53 {
54  memset( p, 0, sizeof(Fxu_Data_t) );
55  p->nSingleMax = 20000;
56  p->nPairsMax = 30000;
57  p->nNodesExt =1000000;
58  p->WeightMin = 0;
59  p->LitCountMax= 0;
60  p->fOnlyS = 0;
61  p->fOnlyD = 0;
62  p->fUse0 = 0;
63  p->fUseCompl = 1;
64  p->fVerbose = 0;
65 }
memset
char * memset()
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fxu_Data_t
typedefABC_NAMESPACE_HEADER_START struct FxuDataStruct Fxu_Data_t
INCLUDES ///.
Definition: fxu.h:42
int Fxu_FastExtract ( Fxu_Data_t *  pData)

FUNCTION DEFINITIONS ///.

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

Synopsis [Performs fast_extract on a set of covers.]

Description [All the covers are given in the array p->vSops. The resulting covers are returned in the array p->vSopsNew. The entries in these arrays correspond to objects in the network. The entries corresponding to the PI and objects with trivial covers are NULL. The number of extracted covers (not exceeding p->nNodesExt) is returned. Two other things are important for the correct operation of this procedure: (1) The input covers do not have duplicated fanins and are SCC-free. (2) The fanins array contains the numbers of the fanin objects.]

SideEffects []

SeeAlso []

Definition at line 58 of file fxu.c.

59 {
60  int fScrollLines = 0;
61  Fxu_Matrix * p;
62  Fxu_Single * pSingle;
63  Fxu_Double * pDouble;
64  int Weight1, Weight2, Weight3;
65  int Counter = 0;
66 
67  s_MemoryTotal = 0;
68  s_MemoryPeak = 0;
69 
70  // create the matrix
71  p = Fxu_CreateMatrix( pData );
72  if ( p == NULL )
73  return -1;
74 // if ( pData->fVerbose )
75 // printf( "Memory usage after construction: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
76 //Fxu_MatrixPrint( NULL, p );
77 
78  if ( pData->fOnlyS )
79  {
80  pData->nNodesNew = 0;
81  do
82  {
83  Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
84  if ( pData->fVerbose )
85  printf( "Div %5d : Best single = %5d.%s", Counter++, Weight1, fScrollLines?"\n":"\r" );
86  if ( Weight1 > pData->WeightMin || (Weight1 == 0 && pData->fUse0) )
87  Fxu_UpdateSingle( p );
88  else
89  break;
90  }
91  while ( ++pData->nNodesNew < pData->nNodesExt );
92  }
93  else if ( pData->fOnlyD )
94  {
95  pData->nNodesNew = 0;
96  do
97  {
98  Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
99  if ( pData->fVerbose )
100  printf( "Div %5d : Best double = %5d.%s", Counter++, Weight2, fScrollLines?"\n":"\r" );
101  if ( Weight2 > pData->WeightMin || (Weight2 == 0 && pData->fUse0) )
102  Fxu_UpdateDouble( p );
103  else
104  break;
105  }
106  while ( ++pData->nNodesNew < pData->nNodesExt );
107  }
108  else if ( !pData->fUseCompl )
109  {
110  pData->nNodesNew = 0;
111  do
112  {
113  Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
114  Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
115 
116  if ( pData->fVerbose )
117  printf( "Div %5d : Best double = %5d. Best single = %5d.%s", Counter++, Weight2, Weight1, fScrollLines?"\n":"\r" );
118 //Fxu_Select( p, &pSingle, &pDouble );
119 
120  if ( Weight1 >= Weight2 )
121  {
122  if ( Weight1 > pData->WeightMin || (Weight1 == 0 && pData->fUse0) )
123  Fxu_UpdateSingle( p );
124  else
125  break;
126  }
127  else
128  {
129  if ( Weight2 > pData->WeightMin || (Weight2 == 0 && pData->fUse0) )
130  Fxu_UpdateDouble( p );
131  else
132  break;
133  }
134  }
135  while ( ++pData->nNodesNew < pData->nNodesExt );
136  }
137  else
138  { // use the complement
139  pData->nNodesNew = 0;
140  do
141  {
142  Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle );
143  Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble );
144 
145  // select the best single and double
146  Weight3 = Fxu_Select( p, &pSingle, &pDouble );
147  if ( pData->fVerbose )
148  printf( "Div %5d : Best double = %5d. Best single = %5d. Best complement = %5d.%s",
149  Counter++, Weight2, Weight1, Weight3, fScrollLines?"\n":"\r" );
150 
151  if ( Weight3 > pData->WeightMin || (Weight3 == 0 && pData->fUse0) )
152  Fxu_Update( p, pSingle, pDouble );
153  else
154  break;
155  }
156  while ( ++pData->nNodesNew < pData->nNodesExt );
157  }
158 
159  if ( pData->fVerbose )
160  printf( "Total single = %3d. Total double = %3d. Total compl = %3d. \n",
161  p->nDivs1, p->nDivs2, p->nDivs3 );
162 
163  // create the new covers
164  if ( pData->nNodesNew )
165  Fxu_CreateCovers( p, pData );
166  Fxu_MatrixDelete( p );
167 // printf( "Memory usage after deallocation: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak );
168  if ( pData->nNodesNew == pData->nNodesExt )
169  printf( "Warning: The limit on the number of extracted divisors has been reached.\n" );
170  return pData->nNodesNew;
171 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fxu_Update
void Fxu_Update(Fxu_Matrix *p, Fxu_Single *pSingle, Fxu_Double *pDouble)
FUNCTION DEFINITIONS ///.
Definition: fxuUpdate.c:57
s_MemoryPeak
static int s_MemoryPeak
Definition: fxu.c:34
Fxu_MatrixDelete
void Fxu_MatrixDelete(Fxu_Matrix *p)
Definition: fxuMatrix.c:96
Fxu_UpdateSingle
void Fxu_UpdateSingle(Fxu_Matrix *p)
Definition: fxuUpdate.c:149
Fxu_HeapDoubleReadMaxWeight
int Fxu_HeapDoubleReadMaxWeight(Fxu_HeapDouble *p)
Definition: fxuHeapD.c:319
Fxu_CreateCovers
void Fxu_CreateCovers(Fxu_Matrix *p, Fxu_Data_t *pData)
Definition: fxuCreate.c:278
Fxu_UpdateDouble
void Fxu_UpdateDouble(Fxu_Matrix *p)
Definition: fxuUpdate.c:219
Counter
static int Counter
Definition: extraBddMisc.c:1877
Fxu_HeapSingleReadMaxWeight
int Fxu_HeapSingleReadMaxWeight(Fxu_HeapSingle *p)
Definition: fxuHeapS.c:321
Fxu_Matrix
typedefABC_NAMESPACE_HEADER_START struct FxuMatrix Fxu_Matrix
INCLUDES ///.
Definition: fxuInt.h:63
Fxu_CreateMatrix
ABC_NAMESPACE_IMPL_START Fxu_Matrix * Fxu_CreateMatrix(Fxu_Data_t *pData)
DECLARATIONS ///.
Definition: fxuCreate.c:52
s_MemoryTotal
static int s_MemoryTotal
Definition: fxu.c:33
Fxu_Select
int Fxu_Select(Fxu_Matrix *p, Fxu_Single **ppSingle, Fxu_Double **ppDouble)
FUNCTION DEFINITIONS ///.
Definition: fxuSelect.c:57