abcRenode.c 10 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8
/**CFile****************************************************************

  FileName    [abcRenode.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

Alan Mishchenko committed
9
  Synopsis    []
Alan Mishchenko committed
10 11 12 13 14 15 16 17 18 19 20

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

21 22 23
#include "base/abc/abc.h"
#include "map/if/if.h"
#include "bool/kit/kit.h"
24 25

#ifdef ABC_USE_CUDD
26
#include "bdd/extrab/extraBdd.h"
27 28
#include "bdd/reo/reo.h"
#endif
Alan Mishchenko committed
29

30 31 32
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
33 34 35 36
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

37 38
#ifdef ABC_USE_CUDD

39 40 41 42 43
static int Abc_NtkRenodeEvalAig( If_Man_t * p, If_Cut_t * pCut );
static int Abc_NtkRenodeEvalBdd( If_Man_t * p, If_Cut_t * pCut );
static int Abc_NtkRenodeEvalSop( If_Man_t * p, If_Cut_t * pCut );
static int Abc_NtkRenodeEvalCnf( If_Man_t * p, If_Cut_t * pCut );
static int Abc_NtkRenodeEvalMv( If_Man_t * p, If_Cut_t * pCut );
Alan Mishchenko committed
44

Alan Mishchenko committed
45 46 47 48
static reo_man * s_pReo       = NULL;
static DdManager * s_pDd      = NULL;
static Vec_Int_t * s_vMemory  = NULL;
static Vec_Int_t * s_vMemory2 = NULL;
Alan Mishchenko committed
49

Alan Mishchenko committed
50
static int nDsdCounter = 0;
Alan Mishchenko committed
51

Alan Mishchenko committed
52
////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
53
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
54 55 56 57
////////////////////////////////////////////////////////////////////////

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

Alan Mishchenko committed
58
  Synopsis    [Performs renoding as technology mapping.]
Alan Mishchenko committed
59

Alan Mishchenko committed
60
  Description []
Alan Mishchenko committed
61 62 63 64 65 66
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
67
Abc_Ntk_t * Abc_NtkRenode( Abc_Ntk_t * pNtk, int nFaninMax, int nCubeMax, int nFlowIters, int nAreaIters, int fArea, int fUseBdds, int fUseSops, int fUseCnfs, int fUseMv, int fVerbose )
Alan Mishchenko committed
68
{
Alan Mishchenko committed
69 70
    extern Abc_Ntk_t * Abc_NtkIf( Abc_Ntk_t * pNtk, If_Par_t * pPars );
    If_Par_t Pars, * pPars = &Pars;
Alan Mishchenko committed
71 72
    Abc_Ntk_t * pNtkNew;

Alan Mishchenko committed
73
    if ( Abc_NtkGetChoiceNum( pNtk ) )
Alan Mishchenko committed
74 75 76 77 78 79 80 81 82 83 84 85
        printf( "Performing renoding with choices.\n" );

    nDsdCounter = 0;

    // set defaults
    memset( pPars, 0, sizeof(If_Par_t) );
    // user-controlable paramters
    pPars->nLutSize    =  nFaninMax;
    pPars->nCutsMax    =  nCubeMax;
    pPars->nFlowIters  =  nFlowIters;
    pPars->nAreaIters  =  nAreaIters;
    pPars->DelayTarget = -1;
Alan Mishchenko committed
86
    pPars->Epsilon     =  (float)0.005;
Alan Mishchenko committed
87 88 89 90 91 92 93 94 95
    pPars->fPreprocess =  1;
    pPars->fArea       =  fArea;
    pPars->fFancy      =  0;
    pPars->fExpRed     =  0; //
    pPars->fLatchPaths =  0;
    pPars->fVerbose    =  fVerbose;
    // internal parameters
    pPars->fTruth      =  1;
    pPars->fUsePerm    =  1; 
96 97
    pPars->nLatchesCi  =  0;
    pPars->nLatchesCo  =  0;
Alan Mishchenko committed
98 99 100 101 102 103 104 105 106 107 108 109
    pPars->pLutLib     =  NULL; // Abc_FrameReadLibLut();
    pPars->pTimesArr   =  NULL; 
    pPars->pTimesArr   =  NULL;   
    pPars->fUseBdds    =  fUseBdds;
    pPars->fUseSops    =  fUseSops;
    pPars->fUseCnfs    =  fUseCnfs;
    pPars->fUseMv      =  fUseMv;
    if ( fUseBdds )
        pPars->pFuncCost = Abc_NtkRenodeEvalBdd;
    else if ( fUseSops )
        pPars->pFuncCost = Abc_NtkRenodeEvalSop;
    else if ( fUseCnfs )
Alan Mishchenko committed
110
    {
Alan Mishchenko committed
111 112
        pPars->fArea = 1;
        pPars->pFuncCost = Abc_NtkRenodeEvalCnf;
Alan Mishchenko committed
113
    }
Alan Mishchenko committed
114 115 116 117
    else if ( fUseMv )
        pPars->pFuncCost = Abc_NtkRenodeEvalMv;
    else
        pPars->pFuncCost = Abc_NtkRenodeEvalAig;
Alan Mishchenko committed
118

Alan Mishchenko committed
119 120
    // start the manager
    if ( fUseBdds )
Alan Mishchenko committed
121
    {
Alan Mishchenko committed
122 123 124 125
        assert( s_pReo == NULL );
        s_pDd  = Cudd_Init( nFaninMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
        s_pReo = Extra_ReorderInit( nFaninMax, 100 );
        pPars->pReoMan  = s_pReo;
Alan Mishchenko committed
126
    }
Alan Mishchenko committed
127
    else
Alan Mishchenko committed
128
    {
Alan Mishchenko committed
129 130 131
        assert( s_vMemory == NULL );
        s_vMemory  = Vec_IntAlloc( 1 << 16 );
        s_vMemory2 = Vec_IntAlloc( 1 << 16 );
Alan Mishchenko committed
132
    }
Alan Mishchenko committed
133

Alan Mishchenko committed
134 135
    // perform mapping/renoding
    pNtkNew = Abc_NtkIf( pNtk, pPars );
Alan Mishchenko committed
136

Alan Mishchenko committed
137 138
    // start the manager
    if ( fUseBdds )
Alan Mishchenko committed
139
    {
Alan Mishchenko committed
140 141 142 143
        Extra_StopManager( s_pDd );
        Extra_ReorderQuit( s_pReo );
        s_pReo = NULL;
        s_pDd  = NULL;
Alan Mishchenko committed
144
    }
Alan Mishchenko committed
145
    else
Alan Mishchenko committed
146
    {
Alan Mishchenko committed
147 148 149 150
        Vec_IntFree( s_vMemory );
        Vec_IntFree( s_vMemory2 );
        s_vMemory = NULL;
        s_vMemory2 = NULL;
Alan Mishchenko committed
151 152
    }

Alan Mishchenko committed
153
//    printf( "Decomposed %d functions.\n", nDsdCounter );
Alan Mishchenko committed
154

Alan Mishchenko committed
155
    return pNtkNew;
Alan Mishchenko committed
156
}
Alan Mishchenko committed
157 158 159

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

Alan Mishchenko committed
160
  Synopsis    [Computes the cost based on the factored form.]
Alan Mishchenko committed
161

Alan Mishchenko committed
162
  Description []
Alan Mishchenko committed
163 164 165 166 167 168
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
169
int Abc_NtkRenodeEvalAig( If_Man_t * p, If_Cut_t * pCut )
Alan Mishchenko committed
170
{
171
    char * pPerm = If_CutPerm( pCut );
Alan Mishchenko committed
172 173
    Kit_Graph_t * pGraph;
    int i, nNodes;
174
    pGraph = Kit_TruthToGraph( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory );
Alan Mishchenko committed
175
    if ( pGraph == NULL )
Alan Mishchenko committed
176
    {
Alan Mishchenko committed
177
        for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
178
            pPerm[i] = 100;
Alan Mishchenko committed
179
        return IF_COST_MAX;
Alan Mishchenko committed
180
    }
Alan Mishchenko committed
181 182
    nNodes = Kit_GraphNodeNum( pGraph );
    for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
183
        pPerm[i] = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeLast(pGraph), Kit_GraphNode(pGraph, i) );
Alan Mishchenko committed
184 185 186
    Kit_GraphFree( pGraph );
    return nNodes;
}
Alan Mishchenko committed
187 188 189

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

Alan Mishchenko committed
190
  Synopsis    [Computes the cost based on the BDD size after reordering.]
Alan Mishchenko committed
191 192 193 194 195 196 197 198

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
199
int Abc_NtkRenodeEvalBdd( If_Man_t * p, If_Cut_t * pCut )
Alan Mishchenko committed
200
{
201
    char * pPerm = If_CutPerm( pCut );
Alan Mishchenko committed
202 203 204 205
    int pOrder[IF_MAX_LUTSIZE];
    DdNode * bFunc, * bFuncNew;
    int i, k, nNodes;
    for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
206
        pPerm[i] = pOrder[i] = -100;
207
    bFunc = Kit_TruthToBdd( s_pDd, If_CutTruth(p, pCut), If_CutLeaveNum(pCut), 0 );  Cudd_Ref( bFunc );
Alan Mishchenko committed
208 209 210
    bFuncNew = Extra_Reorder( s_pReo, s_pDd, bFunc, pOrder );                     Cudd_Ref( bFuncNew );
    for ( i = k = 0; i < If_CutLeaveNum(pCut); i++ )
        if ( pOrder[i] >= 0 )
211
            pPerm[pOrder[i]] = ++k; // double-check this!
Alan Mishchenko committed
212 213 214 215
    nNodes = -1 + Cudd_DagSize( bFuncNew );
    Cudd_RecursiveDeref( s_pDd, bFuncNew );
    Cudd_RecursiveDeref( s_pDd, bFunc );
    return nNodes; 
Alan Mishchenko committed
216 217 218 219
}

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

Alan Mishchenko committed
220
  Synopsis    [Computes the cost based on ISOP.]
Alan Mishchenko committed
221 222 223 224 225 226 227 228

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
229
int Abc_NtkRenodeEvalSop( If_Man_t * p, If_Cut_t * pCut )
Alan Mishchenko committed
230
{
231
    char * pPerm = If_CutPerm( pCut );
Alan Mishchenko committed
232 233
    int i, RetValue;
    for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
234
        pPerm[i] = 1;
235
    RetValue = Kit_TruthIsop( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory, 1 );
Alan Mishchenko committed
236 237 238 239
    if ( RetValue == -1 )
        return IF_COST_MAX;
    assert( RetValue == 0 || RetValue == 1 );
    return Vec_IntSize( s_vMemory );
Alan Mishchenko committed
240 241 242
}

/**Function*************************************************************
Alan Mishchenko committed
243

Alan Mishchenko committed
244
  Synopsis    [Computes the cost based on two ISOPs.]
Alan Mishchenko committed
245 246 247 248 249 250 251 252

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
253
int Abc_NtkRenodeEvalCnf( If_Man_t * p, If_Cut_t * pCut )
Alan Mishchenko committed
254
{
255
    char * pPerm = If_CutPerm( pCut );
Alan Mishchenko committed
256 257 258
    int i, RetValue, nClauses;
    // set internal mapper parameters
    for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
259
        pPerm[i] = 1;
Alan Mishchenko committed
260
    // compute ISOP for the positive phase
261
    RetValue = Kit_TruthIsop( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory, 0 );
Alan Mishchenko committed
262 263 264 265 266
    if ( RetValue == -1 )
        return IF_COST_MAX;
    assert( RetValue == 0 || RetValue == 1 );
    nClauses = Vec_IntSize( s_vMemory );
    // compute ISOP for the negative phase
267 268 269
    Kit_TruthNot( If_CutTruth(p, pCut), If_CutTruth(p, pCut), If_CutLeaveNum(pCut) );
    RetValue = Kit_TruthIsop( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory, 0 );
    Kit_TruthNot( If_CutTruth(p, pCut), If_CutTruth(p, pCut), If_CutLeaveNum(pCut) );
Alan Mishchenko committed
270 271 272 273 274
    if ( RetValue == -1 )
        return IF_COST_MAX;
    assert( RetValue == 0 || RetValue == 1 );
    nClauses += Vec_IntSize( s_vMemory );
    return nClauses;
Alan Mishchenko committed
275 276 277
}

/**Function*************************************************************
Alan Mishchenko committed
278

Alan Mishchenko committed
279
  Synopsis    [Computes the cost of MV-SOP of the cut function.]
Alan Mishchenko committed
280 281 282 283 284 285 286 287

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
288
int Abc_NtkRenodeEvalMv( If_Man_t * p, If_Cut_t * pCut )
Alan Mishchenko committed
289
{
290
    char * pPerm = If_CutPerm( pCut );
Alan Mishchenko committed
291 292 293
    int i, RetValue;
    // set internal mapper parameters
    for ( i = 0; i < If_CutLeaveNum(pCut); i++ )
294
        pPerm[i] = 1;
Alan Mishchenko committed
295
    // compute ISOP for the positive phase
296
    RetValue = Kit_TruthIsop( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory, 0 );
Alan Mishchenko committed
297 298 299 300
    if ( RetValue == -1 )
        return IF_COST_MAX;
    assert( RetValue == 0 || RetValue == 1 );
    // compute ISOP for the negative phase
301 302 303
    Kit_TruthNot( If_CutTruth(p, pCut), If_CutTruth(p, pCut), If_CutLeaveNum(pCut) );
    RetValue = Kit_TruthIsop( If_CutTruth(p, pCut), If_CutLeaveNum(pCut), s_vMemory2, 0 );
    Kit_TruthNot( If_CutTruth(p, pCut), If_CutTruth(p, pCut), If_CutLeaveNum(pCut) );
Alan Mishchenko committed
304 305 306 307 308 309 310 311
    if ( RetValue == -1 )
        return IF_COST_MAX;
    assert( RetValue == 0 || RetValue == 1 );
    // return the cost of the cut 
    RetValue = Abc_NodeEvalMvCost( If_CutLeaveNum(pCut), s_vMemory, s_vMemory2 );
    if ( RetValue >= IF_COST_MAX )
        return IF_COST_MAX;
    return RetValue;
Alan Mishchenko committed
312 313
}

314 315 316 317 318 319
#else

Abc_Ntk_t * Abc_NtkRenode( Abc_Ntk_t * pNtk, int nFaninMax, int nCubeMax, int nFlowIters, int nAreaIters, int fArea, int fUseBdds, int fUseSops, int fUseCnfs, int fUseMv, int fVerbose ) { return NULL; }

#endif

Alan Mishchenko committed
320 321 322 323 324
////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


325 326
ABC_NAMESPACE_IMPL_END