ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Classes | Typedefs | Functions
ivyMulti8.c File Reference
#include "ivy.h"
Include dependency graph for ivyMulti8.c:

Go to the source code of this file.

Classes

struct  Ivy_Eval_t_
 

Typedefs

typedef typedefABC_NAMESPACE_IMPL_START struct Ivy_Eval_t_ Ivy_Eval_t
 DECLARATIONS ///.
 

Functions

Ivy_Obj_t * Ivy_Multi_rec (Ivy_Obj_t **ppObjs, int nObjs, Ivy_Type_t Type)
 FUNCTION DEFINITIONS ///.
 
Ivy_Obj_t * Ivy_Multi (Ivy_Obj_t **pArgsInit, int nArgs, Ivy_Type_t Type)
 
Ivy_Obj_t * Ivy_MultiBalance_rec (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
 
Ivy_Obj_t * Ivy_Multi1 (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
 
Ivy_Obj_t * Ivy_Multi2 (Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
 

Typedef Documentation

◆ Ivy_Eval_t

typedef typedefABC_NAMESPACE_IMPL_START struct Ivy_Eval_t_ Ivy_Eval_t

DECLARATIONS ///.

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

FileName [ivyMulti.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [And-Inverter Graph package.]

Synopsis [Constructing multi-input AND/EXOR gates.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - May 11, 2006.]

Revision [

Id
ivyMulti.c,v 1.00 2006/05/11 00:00:00 alanmi Exp

]

Definition at line 30 of file ivyMulti8.c.

Function Documentation

◆ Ivy_Multi()

Ivy_Obj_t * Ivy_Multi ( Ivy_Obj_t ** pArgsInit,
int nArgs,
Ivy_Type_t Type )

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

Synopsis [Constructs a balanced tree while taking sharing into account.]

Description []

SideEffects []

SeeAlso []

Definition at line 83 of file ivyMulti8.c.

84{
85 static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5};
86 static Ivy_Eval_t pEvals[15+15*14/2];
87 static Ivy_Obj_t * pArgs[16];
88 Ivy_Eval_t * pEva, * pEvaBest;
89 int nArgsNew, nEvals, i, k;
90 Ivy_Obj_t * pTemp;
91
92 // consider the case of one argument
93 assert( nArgs > 0 );
94 if ( nArgs == 1 )
95 return pArgsInit[0];
96 // consider the case of two arguments
97 if ( nArgs == 2 )
98 return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type );
99
100//Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" );
101
102 // set the initial ones
103 for ( i = 0; i < nArgs; i++ )
104 {
105 pArgs[i] = pArgsInit[i];
106 pEva = pEvals + i;
107 pEva->Mask = (1 << i);
108 pEva->Weight = 1;
109 pEva->Cost = 0;
110 pEva->Level = Ivy_Regular(pArgs[i])->Level;
111 pEva->Fan0 = 0;
112 pEva->Fan1 = 0;
113 }
114
115 // find the available nodes
116 pEvaBest = pEvals;
117 nArgsNew = nArgs;
118 for ( i = 1; i < nArgsNew; i++ )
119 for ( k = 0; k < i; k++ )
120 if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) )
121 {
122 pEva = pEvals + nArgsNew;
123 pEva->Mask = pEvals[k].Mask | pEvals[i].Mask;
124 pEva->Weight = NumBits[pEva->Mask];
125 pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask];
126 pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level);
127 pEva->Fan0 = k;
128 pEva->Fan1 = i;
129// assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) );
130 // compare
131 if ( pEvaBest->Weight < pEva->Weight ||
132 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
133 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
134 pEvaBest = pEva;
135 // save the argument
136 pArgs[nArgsNew++] = pTemp;
137 if ( nArgsNew == 15 )
138 goto Outside;
139 }
140Outside:
141
142// printf( "Best = %d.\n", pEvaBest - pEvals );
143
144 // the case of no common nodes
145 if ( nArgsNew == nArgs )
146 {
147 Ivy_MultiSort( pArgs, nArgs );
148 return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
149 }
150 // the case of one common node
151 if ( nArgsNew == nArgs + 1 )
152 {
153 assert( pEvaBest - pEvals == nArgs );
154 k = 0;
155 for ( i = 0; i < nArgs; i++ )
156 if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 )
157 pArgs[k++] = pArgs[i];
158 pArgs[k++] = pArgs[nArgs];
159 assert( k == nArgs - 1 );
160 nArgs = k;
161 Ivy_MultiSort( pArgs, nArgs );
162 return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
163 }
164 // the case when there is a node that covers everything
165 if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) )
166 return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type );
167
168 // evaluate node pairs
169 nEvals = nArgsNew;
170 for ( i = 1; i < nArgsNew; i++ )
171 for ( k = 0; k < i; k++ )
172 {
173 pEva = pEvals + nEvals;
174 pEva->Mask = pEvals[k].Mask | pEvals[i].Mask;
175 pEva->Weight = NumBits[pEva->Mask];
176 pEva->Cost = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask];
177 pEva->Level = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level);
178 pEva->Fan0 = k;
179 pEva->Fan1 = i;
180 // compare
181 if ( pEvaBest->Weight < pEva->Weight ||
182 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
183 pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
184 pEvaBest = pEva;
185 // save the argument
186 nEvals++;
187 }
188 assert( pEvaBest - pEvals >= nArgsNew );
189
190// printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 );
191
192 // get the best implementation
193 pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type );
194
195 // collect those not covered by EvaBest
196 k = 0;
197 for ( i = 0; i < nArgs; i++ )
198 if ( (pEvaBest->Mask & (1 << i)) == 0 )
199 pArgs[k++] = pArgs[i];
200 pArgs[k++] = pTemp;
201 assert( k == nArgs - (int)pEvaBest->Weight + 1 );
202 nArgs = k;
203 Ivy_MultiSort( pArgs, nArgs );
204 return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
205}
Ivy_Eval_t
typedefABC_NAMESPACE_IMPL_START struct Ivy_Eval_t_ Ivy_Eval_t
DECLARATIONS ///.
Definition ivyMulti8.c:30
Ivy_MultiBalance_rec
Ivy_Obj_t * Ivy_MultiBalance_rec(Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
Definition ivyMulti8.c:301
IVY_INIT_NONE
@ IVY_INIT_NONE
Definition ivy.h:66
IVY_MAX
#define IVY_MAX(a, b)
Definition ivy.h:183
Ivy_TableLookup
Ivy_Obj_t * Ivy_TableLookup(Ivy_Man_t *p, Ivy_Obj_t *pObj)
FUNCTION DEFINITIONS ///.
Definition ivyTable.c:71
Ivy_Oper
Ivy_Obj_t * Ivy_Oper(Ivy_Man_t *p, Ivy_Obj_t *p0, Ivy_Obj_t *p1, Ivy_Type_t Type)
FUNCTION DEFINITIONS ///.
Definition ivyOper.c:63
Ivy_Obj_t
struct Ivy_Obj_t_ Ivy_Obj_t
Definition ivy.h:47
Ivy_Obj_t_::Level
unsigned Level
Definition ivy.h:84
assert
#define assert(ex)
Definition util_old.h:213
Here is the call graph for this function:

◆ Ivy_Multi1()

Ivy_Obj_t * Ivy_Multi1 ( Ivy_Obj_t ** pArgs,
int nArgs,
Ivy_Type_t Type )

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

Synopsis [Old code.]

Description []

SideEffects []

SeeAlso []

Definition at line 363 of file ivyMulti8.c.

364{
365 Ivy_Obj_t * pArgsRef[5], * pTemp;
366 int i, k, m, nArgsNew, Counter = 0;
367
368
369//Ivy_MultiEval( pArgs, nArgs, Type ); printf( "\n" );
370
371
372 assert( Type == IVY_AND || Type == IVY_EXOR );
373 assert( nArgs > 0 );
374 if ( nArgs == 1 )
375 return pArgs[0];
376
377 // find the nodes with more than one fanout
378 nArgsNew = 0;
379 for ( i = 0; i < nArgs; i++ )
380 if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 )
381 pArgsRef[nArgsNew++] = pArgs[i];
382
383 // go through pairs
384 if ( nArgsNew >= 2 )
385 for ( i = 0; i < nArgsNew; i++ )
386 for ( k = i + 1; k < nArgsNew; k++ )
387 if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
388 Counter++;
389// printf( "%d", Counter );
390
391 // go through pairs
392 if ( nArgsNew >= 2 )
393 for ( i = 0; i < nArgsNew; i++ )
394 for ( k = i + 1; k < nArgsNew; k++ )
395 if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
396 {
397 nArgsNew = 0;
398 for ( m = 0; m < nArgs; m++ )
399 if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] )
400 pArgs[nArgsNew++] = pArgs[m];
401 pArgs[nArgsNew++] = pTemp;
402 assert( nArgsNew == nArgs - 1 );
403 return Ivy_Multi1( pArgs, nArgsNew, Type );
404 }
405 return Ivy_Multi_rec( pArgs, nArgs, Type );
406}
Ivy_Multi_rec
Ivy_Obj_t * Ivy_Multi_rec(Ivy_Obj_t **ppObjs, int nObjs, Ivy_Type_t Type)
FUNCTION DEFINITIONS ///.
Definition ivyMulti8.c:62
Ivy_Multi1
Ivy_Obj_t * Ivy_Multi1(Ivy_Obj_t **pArgs, int nArgs, Ivy_Type_t Type)
Definition ivyMulti8.c:363
IVY_AND
@ IVY_AND
Definition ivy.h:58
IVY_EXOR
@ IVY_EXOR
Definition ivy.h:59
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Ivy_Multi2()

Ivy_Obj_t * Ivy_Multi2 ( Ivy_Obj_t ** pArgs,
int nArgs,
Ivy_Type_t Type )

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

Synopsis [Old code.]

Description []

SideEffects []

SeeAlso []

Definition at line 419 of file ivyMulti8.c.

420{
421 assert( Type == IVY_AND || Type == IVY_EXOR );
422 assert( nArgs > 0 );
423 return Ivy_Multi_rec( pArgs, nArgs, Type );
424}
Here is the call graph for this function:

◆ Ivy_Multi_rec()

Ivy_Obj_t * Ivy_Multi_rec ( Ivy_Obj_t ** ppObjs,
int nObjs,
Ivy_Type_t Type )

FUNCTION DEFINITIONS ///.

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

Synopsis [Constructs the well-balanced tree of gates.]

Description [Disregards levels and possible logic sharing.]

SideEffects []

SeeAlso []

Definition at line 62 of file ivyMulti8.c.

63{
64 Ivy_Obj_t * pObj1, * pObj2;
65 if ( nObjs == 1 )
66 return ppObjs[0];
67 pObj1 = Ivy_Multi_rec( ppObjs, nObjs/2, Type );
68 pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type );
69 return Ivy_Oper( pObj1, pObj2, Type );
70}
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Ivy_MultiBalance_rec()

Ivy_Obj_t * Ivy_MultiBalance_rec ( Ivy_Obj_t ** pArgs,
int nArgs,
Ivy_Type_t Type )

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

Synopsis [Balances the array recursively.]

Description []

SideEffects []

SeeAlso []

Definition at line 301 of file ivyMulti8.c.

302{
303 Ivy_Obj_t * pNodeNew;
304 // consider the case of one argument
305 assert( nArgs > 0 );
306 if ( nArgs == 1 )
307 return pArgs[0];
308 // consider the case of two arguments
309 if ( nArgs == 2 )
310 return Ivy_Oper( pArgs[0], pArgs[1], Type );
311 // get the last two nodes
312 pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type );
313 // add the new node
314 nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew );
315 return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
316}
Here is the call graph for this function:
Here is the caller graph for this function: