giaScl.c 8.76 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*************************************************************

36
  Synopsis    [Marks unreachable internal nodes and returns 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) );
53
    assert( !Gia_ObjIsBuf(pObj) );
Alan Mishchenko committed
54
    return 1 + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) )
Alan Mishchenko committed
55
             + Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin1(pObj) )
56
             + (p->pNexts ? Gia_ManCombMarkUsed_rec( p, Gia_ObjNextObj(p, Gia_ObjId(p, pObj)) ) : 0)
57
             + (p->pSibls ? Gia_ManCombMarkUsed_rec( p, Gia_ObjSiblObj(p, Gia_ObjId(p, pObj)) ) : 0)
58
             + (p->pMuxes ? Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin2(p, pObj) ) : 0);
Alan Mishchenko committed
59 60 61 62 63 64
}
int Gia_ManCombMarkUsed( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i, nNodes = 0;
    Gia_ManForEachObj( p, pObj, i )
65 66 67
        pObj->fMark0 = Gia_ObjIsAnd(pObj) && !Gia_ObjIsBuf(pObj);
    Gia_ManForEachBuf( p, pObj, i )
        nNodes += Gia_ManCombMarkUsed_rec( p, Gia_ObjFanin0(pObj) );
Alan Mishchenko committed
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
    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 );
}

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

Alan Mishchenko committed
117 118
/**Function*************************************************************

Alan Mishchenko committed
119
  Synopsis    [Marks CIs/COs/ANDs unreachable from POs.]
Alan Mishchenko committed
120 121 122 123 124 125 126 127

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
128
int Gia_ManSeqMarkUsed_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vRoots )
Alan Mishchenko committed
129 130
{
    if ( !pObj->fMark0 )
Alan Mishchenko committed
131
        return 0;
Alan Mishchenko committed
132 133
    pObj->fMark0 = 0;
    if ( Gia_ObjIsCo(pObj) )
Alan Mishchenko committed
134
        return Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots );
Alan Mishchenko committed
135 136 137
    if ( Gia_ObjIsRo(p, pObj) )
    {
        Vec_IntPush( vRoots, Gia_ObjId(p, Gia_ObjRoToRi(p, pObj)) );
Alan Mishchenko committed
138
        return 0;
Alan Mishchenko committed
139 140
    }
    assert( Gia_ObjIsAnd(pObj) );
Alan Mishchenko committed
141 142
    return 1 + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin0(pObj), vRoots )
             + Gia_ManSeqMarkUsed_rec( p, Gia_ObjFanin1(pObj), vRoots );
Alan Mishchenko committed
143 144 145 146
}

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

Alan Mishchenko committed
147
  Synopsis    [Marks CIs/COs/ANDs unreachable from POs.]
Alan Mishchenko committed
148 149 150 151 152 153 154 155

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
156
int Gia_ManSeqMarkUsed( Gia_Man_t * p )
Alan Mishchenko committed
157 158 159
{
    Vec_Int_t * vRoots;
    Gia_Obj_t * pObj;
Alan Mishchenko committed
160
    int i, nNodes = 0;
Alan Mishchenko committed
161 162 163 164 165 166
    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
167
        nNodes += Gia_ManSeqMarkUsed_rec( p, pObj, vRoots );
Alan Mishchenko committed
168
    Vec_IntFree( vRoots );
Alan Mishchenko committed
169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
    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
186 187 188 189 190 191 192
    return Gia_ManDupMarked( p );
}

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

  Synopsis    [Find representatives due to identical fanins.]

Alan Mishchenko committed
193
  Description [Returns the old manager if there is no changes.]
Alan Mishchenko committed
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211
               
  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) );
212
    pMaps   = ABC_FALLOC( unsigned, 2 * nFanins );
Alan Mishchenko committed
213 214 215
    Gia_ManForEachRiRo( p, pObjRi, pObjRo, i )
    {
        iLit = Gia_ObjFanin0Copy( pObjRi );
Alan Mishchenko committed
216
        if ( Gia_ObjFaninId0p(p, pObjRi) == 0 && Gia_ObjFaninC0(pObjRi) == 0 ) // const 0 
Alan Mishchenko committed
217 218 219 220
            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
221
            pMaps[iLit] = Abc_Var2Lit( Gia_ObjId(p, pObjRo), 0 );
Alan Mishchenko committed
222 223 224 225 226 227 228 229 230 231 232 233 234 235
    }
/*
    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
236 237
//    if ( fVerbose )
//        printf( "ReduceEquiv detected %d constant regs and %d equivalent regs.\n", Counter0, Counter );
Alan Mishchenko committed
238
    ABC_FREE( pMaps );
Alan Mishchenko committed
239
    if ( Counter0 || Counter )
240
        pNew = Gia_ManDupDfsCiMap( p, (int *)pCi2Lit, NULL );
Alan Mishchenko committed
241 242
    else
        pNew = p;
Alan Mishchenko committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
    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 )
262
        return Gia_ManCleanup( p );
Alan Mishchenko committed
263 264 265 266 267
    if ( fVerbose )
        printf( "Performing sequential cleanup.\n" );
    p = Gia_ManSeqCleanup( pTemp = p );
    if ( fVerbose )
        Gia_ManReportImprovement( pTemp, p );
Alan Mishchenko committed
268 269 270
    if ( fConst && Gia_ManRegNum(p) )
    {
        p = Gia_ManReduceConst( pTemp = p, fVerbose );
Alan Mishchenko committed
271 272
        if ( fVerbose )
            Gia_ManReportImprovement( pTemp, p );
Alan Mishchenko committed
273 274
        Gia_ManStop( pTemp );
    }
Alan Mishchenko committed
275 276 277 278
    if ( fVerbose && fEquiv )
        printf( "Merging combinationally equivalent flops.\n" );
    if ( fEquiv )
    while ( 1 )
Alan Mishchenko committed
279
    {
Alan Mishchenko committed
280 281 282 283 284 285
        p = Gia_ManSeqCleanup( pTemp = p );
        if ( fVerbose )
            Gia_ManReportImprovement( pTemp, p );
        Gia_ManStop( pTemp );
        if ( Gia_ManRegNum(p) == 0 )
            break;
Alan Mishchenko committed
286
        p = Gia_ManReduceEquiv( pTemp = p, fVerbose );
Alan Mishchenko committed
287 288
        if ( p == pTemp )
            break;
Alan Mishchenko committed
289 290 291 292 293 294 295 296 297 298
        Gia_ManStop( pTemp );
    }
    return p;
}

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


299 300
ABC_NAMESPACE_IMPL_END