ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Functions
acecOrder.c File Reference
#include "acecInt.h"
Include dependency graph for acecOrder.c:

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START Vec_Int_t * Gia_PolynFindOrder (Gia_Man_t *pGia, Vec_Int_t *vFadds, Vec_Int_t *vHadds, int fVerbose, int fVeryVerbose)
 DECLARATIONS ///.
 
Vec_Int_t * Gia_PolynReorder (Gia_Man_t *pGia, int fVerbose, int fVeryVerbose)
 

Function Documentation

◆ Gia_PolynFindOrder()

ABC_NAMESPACE_IMPL_START Vec_Int_t * Gia_PolynFindOrder ( Gia_Man_t * pGia,
Vec_Int_t * vFadds,
Vec_Int_t * vHadds,
int fVerbose,
int fVeryVerbose )

DECLARATIONS ///.

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

FileName [acecOrder.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [CEC for arithmetic circuits.]

Synopsis [Node ordering.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

] FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file acecOrder.c.

46{
47 int fDumpLeftOver = 0;
48 int i, iXor, iMaj, iAnd, Entry, Iter, fFound, fFoundAll = 1;
49 Vec_Int_t * vRecord = Vec_IntAlloc( 100 ), * vLeft, * vRecord2;
50 Vec_Int_t * vMap = Vec_IntStart( Gia_ManObjNum(pGia) );
51 Gia_ManForEachCoDriverId( pGia, iAnd, i )
52 Vec_IntWriteEntry( vMap, iAnd, 1 );
53
54 // collect the last XOR
55 Vec_IntFreeP( &pGia->vXors );
56 pGia->vXors = Gia_PolynCollectLastXor( pGia, fVerbose );
57 printf( "Collected %d topmost XORs\n", Vec_IntSize(pGia->vXors) );
58 //Vec_IntPrint( p->vXors );
59 Vec_IntForEachEntry( pGia->vXors, iAnd, i )
60 {
61 Gia_Obj_t * pAnd = Gia_ManObj( pGia, iAnd );
62 assert( Vec_IntEntry(vMap, iAnd) );
63 Vec_IntWriteEntry( vMap, iAnd, 0 );
64 Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
65 Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
66 Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 3) );
67 if ( fVeryVerbose )
68 printf( "Recognizing %d => XXXOR(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
69 }
70
71 // detect FAs and HAs
72 for ( Iter = 0; fFoundAll; Iter++ )
73 {
74 if ( fVeryVerbose )
75 printf( "Iteration %d\n", Iter );
76
77 // check if we can extract FADDs
78 fFoundAll = 0;
79 do {
80 fFound = 0;
81 for ( i = Vec_IntSize(vFadds)/5 - 1; i >= 0; i-- )
82 {
83 iXor = Vec_IntEntry(vFadds, 5*i+3);
84 iMaj = Vec_IntEntry(vFadds, 5*i+4);
85 if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
86 {
87 Vec_IntWriteEntry( vMap, iXor, 0 );
88 Vec_IntWriteEntry( vMap, iMaj, 0 );
89 Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+0), 1 );
90 Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+1), 1 );
91 Vec_IntWriteEntry( vMap, Vec_IntEntry(vFadds, 5*i+2), 1 );
92 Vec_IntPush( vRecord, Abc_Var2Lit2(i, 2) );
93 fFound = 1;
94 fFoundAll = 1;
95 if ( fVeryVerbose )
96 printf( "Recognizing (%d %d) => FA(%d %d %d)\n", iXor, iMaj, Vec_IntEntry(vFadds, 5*i+0), Vec_IntEntry(vFadds, 5*i+1), Vec_IntEntry(vFadds, 5*i+2) );
97 }
98 }
99 } while ( fFound );
100 // check if we can extract HADDs
101 do {
102 fFound = 0;
103 for ( i = Vec_IntSize(vHadds)/2 - 1; i >= 0; i-- )
104 {
105 iXor = Vec_IntEntry(vHadds, 2*i+0);
106 iMaj = Vec_IntEntry(vHadds, 2*i+1);
107 if ( Vec_IntEntry(vMap, iXor) && Vec_IntEntry(vMap, iMaj) )
108 {
109 Gia_Obj_t * pAnd = Gia_ManObj( pGia, iMaj );
110 Vec_IntWriteEntry( vMap, iXor, 0 );
111 Vec_IntWriteEntry( vMap, iMaj, 0 );
112 Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iMaj), 1 );
113 Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iMaj), 1 );
114 Vec_IntPush( vRecord, Abc_Var2Lit2(i, 1) );
115 fFound = 1;
116 fFoundAll = 1;
117 if ( fVeryVerbose )
118 printf( "Recognizing (%d %d) => HA(%d %d)\n", iXor, iMaj, Gia_ObjFaninId0(pAnd, iMaj), Gia_ObjFaninId1(pAnd, iMaj) );
119 }
120 }
121 break; // only one iter!
122 } while ( fFound );
123 if ( fFoundAll )
124 continue;
125/*
126 // find the last one
127 Vec_IntForEachEntryReverse( vMap, Entry, iAnd )
128 if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, iAnd)) )//&& Vec_IntFind(vFadds, iAnd) == -1 )//&& Vec_IntFind(vHadds, iAnd) == -1 )
129 {
130 Gia_Obj_t * pFan0, * pFan1, * pAnd = Gia_ManObj( pGia, iAnd );
131 if ( !Gia_ObjRecognizeExor(pAnd, &pFan0, &pFan1) )
132 {
133 Vec_IntWriteEntry( vMap, iAnd, 0 );
134 Vec_IntWriteEntry( vMap, Gia_ObjFaninId0(pAnd, iAnd), 1 );
135 Vec_IntWriteEntry( vMap, Gia_ObjFaninId1(pAnd, iAnd), 1 );
136 Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
137 }
138 else
139 {
140 Vec_IntWriteEntry( vMap, iAnd, 0 );
141 Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan0), 1 );
142 Vec_IntWriteEntry( vMap, Gia_ObjId(pGia, pFan1), 1 );
143 Vec_IntPush( vRecord, Abc_Var2Lit2(iAnd, 0) );
144 Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId0(pAnd, iAnd), 0) );
145 Vec_IntPush( vRecord, Abc_Var2Lit2(Gia_ObjFaninId1(pAnd, iAnd), 0) );
146 printf( "Recognizing %d => XOR(%d %d)\n", iAnd, Gia_ObjId(pGia, pFan0), Gia_ObjId(pGia, pFan1) );
147 }
148 fFoundAll = 1;
149 if ( fVeryVerbose )
150 printf( "Recognizing %d => AND(%d %d)\n", iAnd, Gia_ObjFaninId0(pAnd, iAnd), Gia_ObjFaninId1(pAnd, iAnd) );
151 break;
152 }
153*/
154 }
155 //Vec_IntPrint( vMap );
156
157 // collect remaining ones
158 vLeft = Vec_IntAlloc( 100 );
159 Vec_IntForEachEntry( vMap, Entry, i )
160 if ( Entry && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) )
161 Vec_IntPush( vLeft, i );
162 Vec_IntFree( vMap );
163
164 // collect them in the topo order
165 vRecord2 = Vec_IntAlloc( 100 );
166 Gia_ManIncrementTravId( pGia );
167 Gia_ManCollectAnds( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), vRecord2, NULL );
168 Vec_IntForEachEntry( vRecord2, iAnd, i )
169 Vec_IntWriteEntry( vRecord2, i, Abc_Var2Lit2(iAnd, 0) );
170
171 // dump remaining nodes as an AIG
172 if ( fDumpLeftOver )
173 {
174 Gia_Man_t * pNew;
175 pNew = Gia_ManDupAndCones( pGia, Vec_IntArray(vLeft), Vec_IntSize(vLeft), 0 );
176 Gia_AigerWrite( pNew, "leftover.aig", 0, 0, 0 );
177 printf( "Leftover AIG with %d nodes is dumped into file \"%s\".\n", Gia_ManAndNum(pNew), "leftover.aig" );
178 Gia_ManStop( pNew );
179 }
180 Vec_IntFree( vLeft );
181
182 Vec_IntReverseOrder( vRecord );
183 Vec_IntAppend( vRecord2, vRecord );
184 Vec_IntFree( vRecord );
185 return vRecord2;
186}
Gia_PolynCollectLastXor
Vec_Int_t * Gia_PolynCollectLastXor(Gia_Man_t *pGia, int fVerbose)
Definition acecUtil.c:57
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
Gia_ManStop
void Gia_ManStop(Gia_Man_t *p)
Definition giaMan.c:82
Gia_ManForEachCoDriverId
#define Gia_ManForEachCoDriverId(p, DriverId, i)
Definition gia.h:1246
Gia_Obj_t
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
Gia_Man_t
struct Gia_Man_t_ Gia_Man_t
Definition gia.h:96
Gia_ManIncrementTravId
void Gia_ManIncrementTravId(Gia_Man_t *p)
Definition giaUtil.c:190
Gia_ManDupAndCones
Gia_Man_t * Gia_ManDupAndCones(Gia_Man_t *p, int *pAnds, int nAnds, int fTrimPis)
Definition giaDup.c:3941
Gia_AigerWrite
void Gia_AigerWrite(Gia_Man_t *p, char *pFileName, int fWriteSymbols, int fCompact, int fWriteNewLine)
Definition giaAiger.c:1595
Gia_ManCollectAnds
void Gia_ManCollectAnds(Gia_Man_t *p, int *pNodes, int nNodes, Vec_Int_t *vNodes, Vec_Int_t *vLeaves)
Definition giaDfs.c:125
Gia_Man_t_::vXors
Vec_Int_t * vXors
Definition gia.h:164
assert
#define assert(ex)
Definition util_old.h:213
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Gia_PolynReorder()

Vec_Int_t * Gia_PolynReorder ( Gia_Man_t * pGia,
int fVerbose,
int fVeryVerbose )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file acecOrder.c.

200{
201 Vec_Int_t * vFadds = Gia_ManDetectFullAdders( pGia, fVeryVerbose, NULL );
202 Vec_Int_t * vHadds = Gia_ManDetectHalfAdders( pGia, fVeryVerbose );
203 Vec_Int_t * vRecord = Gia_PolynFindOrder( pGia, vFadds, vHadds, fVerbose, fVeryVerbose );
204 Vec_Int_t * vOrder = Vec_IntAlloc( Gia_ManAndNum(pGia) );
205 Vec_Int_t * vOrder2 = Vec_IntStart( Gia_ManObjNum(pGia) );
206 int i, k, Entry;
207
208 // collect nodes
209 Gia_ManIncrementTravId( pGia );
210 Vec_IntForEachEntry( vRecord, Entry, i )
211 {
212 int Node = Abc_Lit2Var2(Entry);
213 int Attr = Abc_Lit2Att2(Entry);
214 if ( Attr == 2 )
215 {
216 int * pFanins = Vec_IntEntryP( vFadds, 5*Node );
217 for ( k = 3; k < 5; k++ )
218 Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
219 }
220 else if ( Attr == 1 )
221 {
222 int * pFanins = Vec_IntEntryP( vHadds, 2*Node );
223 for ( k = 0; k < 2; k++ )
224 Gia_ManCollectAnds_rec( pGia, pFanins[k], vOrder );
225 }
226 else
227 Gia_ManCollectAnds_rec( pGia, Node, vOrder );
228 //printf( "Order = %d. Node = %d. Size = %d ", i, Node, Vec_IntSize(vOrder) );
229 }
230 //printf( "\n" );
231 //assert( Vec_IntSize(vOrder) == Gia_ManAndNum(pGia) );
232
233 // remap order
234 Gia_ManForEachCiId( pGia, Entry, i )
235 Vec_IntWriteEntry( vOrder2, Entry, 1+i );
236 Vec_IntForEachEntry( vOrder, Entry, i )
237 Vec_IntWriteEntry( vOrder2, Entry, 1+Gia_ManCiNum(pGia)+i );
238 //Vec_IntPrint( vOrder );
239
240 Vec_IntFree( vRecord );
241 Vec_IntFree( vFadds );
242 Vec_IntFree( vHadds );
243 Vec_IntFree( vOrder );
244 return vOrder2;
245}
Gia_PolynFindOrder
ABC_NAMESPACE_IMPL_START Vec_Int_t * Gia_PolynFindOrder(Gia_Man_t *pGia, Vec_Int_t *vFadds, Vec_Int_t *vHadds, int fVerbose, int fVeryVerbose)
DECLARATIONS ///.
Definition acecOrder.c:45
Gia_ManDetectHalfAdders
Vec_Int_t * Gia_ManDetectHalfAdders(Gia_Man_t *p, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition acecFadds.c:50
Gia_ManDetectFullAdders
Vec_Int_t * Gia_ManDetectFullAdders(Gia_Man_t *p, int fVerbose, Vec_Int_t **vCutsXor2)
Definition acecFadds.c:442
Gia_ManCollectAnds_rec
void Gia_ManCollectAnds_rec(Gia_Man_t *p, int iObj, Vec_Int_t *vNodes)
Definition giaDfs.c:99
Gia_ManForEachCiId
#define Gia_ManForEachCiId(p, Id, i)
Definition gia.h:1230
Here is the call graph for this function: