1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
/**CFile****************************************************************
FileName [aigWin.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [AIG package.]
Synopsis [Window computation.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - April 28, 2007.]
Revision [$Id: aigWin.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
***********************************************************************/
#include "aig.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Evaluate the cost of removing the node from the set of leaves.]
Description [Returns the number of new leaves that will be brought in.
Returns large number if the node cannot be removed from the set of leaves.]
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Aig_NodeGetLeafCostOne( Aig_Obj_t * pNode, int nFanoutLimit )
{
int Cost;
// make sure the node is in the construction zone
assert( pNode->fMarkA );
// cannot expand over the PI node
if ( Aig_ObjIsCi(pNode) )
return 999;
// get the cost of the cone
Cost = (!Aig_ObjFanin0(pNode)->fMarkA) + (!Aig_ObjFanin1(pNode)->fMarkA);
// always accept if the number of leaves does not increase
if ( Cost < 2 )
return Cost;
// skip nodes with many fanouts
if ( (int)pNode->nRefs > nFanoutLimit )
return 999;
// return the number of nodes that will be on the leaves if this node is removed
return Cost;
}
/**Function*************************************************************
Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.]
Description [This procedure looks at the current leaves and tries to change
one leaf at a time in such a way that the cut grows as little as possible.
In evaluating the fanins, this procedure looks only at their immediate
predecessors (this is why it is called a one-level construction procedure).]
SideEffects []
SeeAlso []
***********************************************************************/
int Aig_ManFindCut_int( Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited, int nSizeLimit, int nFanoutLimit )
{
Aig_Obj_t * pNode, * pFaninBest, * pNext;
int CostBest, CostCur, i;
// find the best fanin
CostBest = 100;
pFaninBest = NULL;
//printf( "Evaluating fanins of the cut:\n" );
Vec_PtrForEachEntry( Aig_Obj_t *, vFront, pNode, i )
{
CostCur = Aig_NodeGetLeafCostOne( pNode, nFanoutLimit );
//printf( " Fanin %s has cost %d.\n", Aig_ObjName(pNode), CostCur );
if ( CostBest > CostCur ||
(CostBest == CostCur && pNode->Level > pFaninBest->Level) )
{
CostBest = CostCur;
pFaninBest = pNode;
}
if ( CostBest == 0 )
break;
}
if ( pFaninBest == NULL )
return 0;
assert( CostBest < 3 );
if ( Vec_PtrSize(vFront) - 1 + CostBest > nSizeLimit )
return 0;
assert( Aig_ObjIsNode(pFaninBest) );
// remove the node from the array
Vec_PtrRemove( vFront, pFaninBest );
//printf( "Removing fanin %s.\n", Aig_ObjName(pFaninBest) );
// add the left child to the fanins
pNext = Aig_ObjFanin0(pFaninBest);
if ( !pNext->fMarkA )
{
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
pNext->fMarkA = 1;
Vec_PtrPush( vFront, pNext );
Vec_PtrPush( vVisited, pNext );
}
// add the right child to the fanins
pNext = Aig_ObjFanin1(pFaninBest);
if ( !pNext->fMarkA )
{
//printf( "Adding fanin %s.\n", Aig_ObjName(pNext) );
pNext->fMarkA = 1;
Vec_PtrPush( vFront, pNext );
Vec_PtrPush( vVisited, pNext );
}
assert( Vec_PtrSize(vFront) <= nSizeLimit );
// keep doing this
return 1;
}
/**Function*************************************************************
Synopsis [Computes one sequential cut of the given size.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Aig_ManFindCut( Aig_Obj_t * pRoot, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited, int nSizeLimit, int nFanoutLimit )
{
Aig_Obj_t * pNode;
int i;
assert( !Aig_IsComplement(pRoot) );
assert( Aig_ObjIsNode(pRoot) );
assert( Aig_ObjChild0(pRoot) );
assert( Aig_ObjChild1(pRoot) );
// start the cut
Vec_PtrClear( vFront );
Vec_PtrPush( vFront, Aig_ObjFanin0(pRoot) );
Vec_PtrPush( vFront, Aig_ObjFanin1(pRoot) );
// start the visited nodes
Vec_PtrClear( vVisited );
Vec_PtrPush( vVisited, pRoot );
Vec_PtrPush( vVisited, Aig_ObjFanin0(pRoot) );
Vec_PtrPush( vVisited, Aig_ObjFanin1(pRoot) );
// mark these nodes
assert( !pRoot->fMarkA );
assert( !Aig_ObjFanin0(pRoot)->fMarkA );
assert( !Aig_ObjFanin1(pRoot)->fMarkA );
pRoot->fMarkA = 1;
Aig_ObjFanin0(pRoot)->fMarkA = 1;
Aig_ObjFanin1(pRoot)->fMarkA = 1;
// compute the cut
while ( Aig_ManFindCut_int( vFront, vVisited, nSizeLimit, nFanoutLimit ) );
assert( Vec_PtrSize(vFront) <= nSizeLimit );
// clean the visit markings
Vec_PtrForEachEntry( Aig_Obj_t *, vVisited, pNode, i )
pNode->fMarkA = 0;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END
|
