giaScl.c 8.79 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
/**CFile****************************************************************

  FileName    [giaScl.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Sequential cleanup.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: giaScl.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "gia.h"

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30 31 32 33 34 35
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

Alan Mishchenko committed
36
  Synopsis    [Marks unreachable internal nodes and returned their number.]
Alan Mishchenko committed
37 38 39 40 41 42 43 44 45 46

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManCombMarkUsed_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
Alan Mishchenko committed
47 48
    if ( pObj == NULL )
        return 0;
Alan Mishchenko committed
49 50 51 52
    if ( !pObj->fMark0 )
        return 0;
    pObj->fMark0 = 0;
    assert( Gia_ObjIsAnd(pObj) );
Alan Mishchenko committed
53
    return 1 + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) )
Alan Mishchenko committed
54
             + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin1(pObj) )
55 56
             + (p->pNexts ? Gia_ManCombMarkUsed_rec( p, Gia_ObjNextObj(p, Gia_ObjId(p, pObj)) ) : 0)
             + (p->pMuxes ? Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin2(p, pObj) ) : 0);
Alan Mishchenko committed
57 58 59 60
}

/**Function*************************************************************

Alan Mishchenko committed
61
  Synopsis    [Marks unreachable internal nodes and returned their number.]
Alan Mishchenko committed
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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Gia_ManCombMarkUsed( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i, nNodes = 0;
    Gia_ManForEachObj( p, pObj, i )
        pObj->fMark0 = Gia_ObjIsAnd(pObj);
    Gia_ManForEachCo( p, pObj, i )
        nNodes += Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) );
    return nNodes;
}

/**Function*************************************************************

  Synopsis    [Performs combinational cleanup.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManCleanup( Gia_Man_t * p )
{
    Gia_ManCombMarkUsed( p );
    return Gia_ManDupMarked( p );
}

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
/**Function*************************************************************

  Synopsis    [Skip the first outputs during cleanup.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManCleanupOutputs( Gia_Man_t * p, int nOutputs )
{
    Gia_Obj_t * pObj;
    int i;
    assert( Gia_ManRegNum(p) == 0 );
    assert( nOutputs < Gia_ManCoNum(p) );
    Gia_ManCombMarkUsed( p );
    Gia_ManForEachCo( p, pObj, i )
        if ( i < nOutputs )
            pObj->fMark0 = 1;
        else
            break;
    return Gia_ManDupMarked( p );
}

Alan Mishchenko committed
124

Alan Mishchenko committed
125 126
/**Function*************************************************************

Alan Mishchenko committed
127
  Synopsis    [Marks CIs/COs/ANDs unreachable from POs.]
Alan Mishchenko committed
128 129 130 131 132 133 134 135

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
136
int Gia_ManSeqMarkUsed_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vRoots )
Alan Mishchenko committed
137 138
{
    if ( !pObj->fMark0 )
Alan Mishchenko committed
139
        return 0;
Alan Mishchenko committed
140 141
    pObj->fMark0 = 0;
    if ( Gia_ObjIsCo(pObj) )
Alan Mishchenko committed
142
        return Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots );
Alan Mishchenko committed
143 144 145
    if ( Gia_ObjIsRo(p, pObj) )
    {
        Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ObjRoToRi(p, pObj)) );
Alan Mishchenko committed
146
        return 0;
Alan Mishchenko committed
147 148
    }
    assert( Gia_ObjIsAnd(pObj) );
Alan Mishchenko committed
149 150
    return 1 + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots )
             + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin1(pObj), vRoots );
Alan Mishchenko committed
151 152 153 154
}

/**Function*************************************************************

Alan Mishchenko committed
155
  Synopsis    [Marks CIs/COs/ANDs unreachable from POs.]
Alan Mishchenko committed
156 157 158 159 160 161 162 163

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
164
int Gia_ManSeqMarkUsed( Gia_Man_t * p )
Alan Mishchenko committed
165 166 167
{
    Vec_Int_t * vRoots;
    Gia_Obj_t * pObj;
Alan Mishchenko committed
168
    int i, nNodes = 0;
Alan Mishchenko committed
169 170 171 172 173 174
    Gia_ManSetMark0( p );
    Gia_ManConst0(p)->fMark0 = 0;
    Gia_ManForEachPi( p, pObj, i )
        pObj->fMark0 = 0;
    vRoots = Gia_ManCollectPoIds( p );
    Gia_ManForEachObjVec( vRoots, p, pObj, i )
Alan Mishchenko committed
175
        nNodes += Gia_ManSeqMarkUsed_rec( p, pObj, vRoots );
Alan Mishchenko committed
176
    Vec_IntFree( vRoots );
Alan Mishchenko committed
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
    return nNodes;
}

/**Function*************************************************************

  Synopsis    [Performs sequential cleanup.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManSeqCleanup( Gia_Man_t * p )
{
    Gia_ManSeqMarkUsed( p );
Alan Mishchenko committed
194 195 196 197 198 199 200
    return Gia_ManDupMarked( p );
}

/**Function*************************************************************

  Synopsis    [Find representatives due to identical fanins.]

Alan Mishchenko committed
201
  Description [Returns the old manager if there is no changes.]
Alan Mishchenko committed
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManReduceEquiv( Gia_Man_t * p, int fVerbose )
{
    Gia_Man_t * pNew;
    Gia_Obj_t * pObjRi, * pObjRo;
    unsigned * pCi2Lit, * pMaps;
    int i, iLit, nFanins = 1, Counter0 = 0, Counter = 0;
    Gia_ManForEachRi( p, pObjRi, i )
        Gia_ObjFanin0(pObjRi)->Value = 0;
    Gia_ManForEachRi( p, pObjRi, i )
        if ( Gia_ObjFanin0(pObjRi)->Value == 0 )
            Gia_ObjFanin0(pObjRi)->Value = 2*nFanins++;
    pCi2Lit = ABC_FALLOC( unsigned, Gia_ManCiNum(p) );
220
    pMaps   = ABC_FALLOC( unsigned, 2 * nFanins );
Alan Mishchenko committed
221 222 223
    Gia_ManForEachRiRo( p, pObjRi, pObjRo, i )
    {
        iLit = Gia_ObjFanin0Copy( pObjRi );
Alan Mishchenko committed
224
        if ( Gia_ObjFaninId0p(p, pObjRi) == 0 && Gia_ObjFaninC0(pObjRi) == 0 ) // const 0 
Alan Mishchenko committed
225 226 227 228
            pCi2Lit[Gia_ManPiNum(p)+i] = 0, Counter0++;
        else if ( ~pMaps[iLit] ) // in this case, ID(pObj) > ID(pRepr) 
            pCi2Lit[Gia_ManPiNum(p)+i] = pMaps[iLit], Counter++; 
        else
229
            pMaps[iLit] = Abc_Var2Lit( Gia_ObjId(p, pObjRo), 0 );
Alan Mishchenko committed
230 231 232 233 234 235 236 237 238 239 240 241 242 243
    }
/*
    Gia_ManForEachCi( p, pObjRo, i )
    {
        if ( ~pCi2Lit[i] )
        {
            Gia_Obj_t * pObj0 = Gia_ObjRoToRi(p, pObjRo);
            Gia_Obj_t * pObj1 = Gia_ObjRoToRi(p, Gia_ManObj(p, pCi2Lit[i]));
            Gia_Obj_t * pFan0 = Gia_ObjChild0( p, Gia_ObjRoToRi(p, pObjRo) );
            Gia_Obj_t * pFan1 = Gia_ObjChild0( p, Gia_ObjRoToRi(p, Gia_ManObj(p, pCi2Lit[i])) );
            assert( pFan0 == pFan1 );
        }
    }
*/
Alan Mishchenko committed
244 245
//    if ( fVerbose )
//        printf( "ReduceEquiv detected %d constant regs and %d equivalent regs.\n", Counter0, Counter );
Alan Mishchenko committed
246
    ABC_FREE( pMaps );
Alan Mishchenko committed
247
    if ( Counter0 || Counter )
248
        pNew = Gia_ManDupDfsCiMap( p, (int *)pCi2Lit, NULL );
Alan Mishchenko committed
249 250
    else
        pNew = p;
Alan Mishchenko committed
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
    ABC_FREE( pCi2Lit );
    return pNew;
}

/**Function*************************************************************

  Synopsis    [Performs sequential cleanup.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManSeqStructSweep( Gia_Man_t * p, int fConst, int fEquiv, int fVerbose )
{
    Gia_Man_t * pTemp;
    if ( Gia_ManRegNum(p) == 0 )
270
        return Gia_ManCleanup( p );
Alan Mishchenko committed
271 272 273 274 275
    if ( fVerbose )
        printf( "Performing sequential cleanup.\n" );
    p = Gia_ManSeqCleanup( pTemp = p );
    if ( fVerbose )
        Gia_ManReportImprovement( pTemp, p );
Alan Mishchenko committed
276 277 278
    if ( fConst && Gia_ManRegNum(p) )
    {
        p = Gia_ManReduceConst( pTemp = p, fVerbose );
Alan Mishchenko committed
279 280
        if ( fVerbose )
            Gia_ManReportImprovement( pTemp, p );
Alan Mishchenko committed
281 282
        Gia_ManStop( pTemp );
    }
Alan Mishchenko committed
283 284 285 286
    if ( fVerbose && fEquiv )
        printf( "Merging combinationally equivalent flops.\n" );
    if ( fEquiv )
    while ( 1 )
Alan Mishchenko committed
287
    {
Alan Mishchenko committed
288 289 290 291 292 293
        p = Gia_ManSeqCleanup( pTemp = p );
        if ( fVerbose )
            Gia_ManReportImprovement( pTemp, p );
        Gia_ManStop( pTemp );
        if ( Gia_ManRegNum(p) == 0 )
            break;
Alan Mishchenko committed
294
        p = Gia_ManReduceEquiv( pTemp = p, fVerbose );
Alan Mishchenko committed
295 296
        if ( p == pTemp )
            break;
Alan Mishchenko committed
297 298 299 300 301 302 303 304 305 306
        Gia_ManStop( pTemp );
    }
    return p;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


307 308
ABC_NAMESPACE_IMPL_END