src/aig/ivy/ivyRwr.c

Go to the documentation of this file.

#include "ivy.h"
#include "deco.h"
#include "rwt.h"


static unsigned Ivy_NodeGetTruth( Ivy_Obj_t * pObj, int * pNums, int nNums );
static int Ivy_NodeRewrite( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pNode, int fUpdateLevel, int fUseZeroCost );
static Dec_Graph_t * Rwt_CutEvaluate( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pRoot, 
    Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, unsigned uTruth );

static int Ivy_GraphToNetworkCount( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax );
static void Ivy_GraphUpdateNetwork( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );


int Ivy_ManRewritePre( Ivy_Man_t * p, int fUpdateLevel, int fUseZeroCost, int fVerbose )
{
    Rwt_Man_t * pManRwt;
    Ivy_Obj_t * pNode;
    int i, nNodes, nGain;
    int clk, clkStart = clock();
    // start the rewriting manager
    pManRwt = Rwt_ManStart( 0 );
    p->pData = pManRwt;
    if ( pManRwt == NULL )
        return 0; 
    // create fanouts
    if ( fUpdateLevel && p->fFanout == 0 )
        Ivy_ManStartFanout( p );
    // compute the reverse levels if level update is requested
    if ( fUpdateLevel )
        Ivy_ManRequiredLevels( p );
    // set the number of levels
//    p->nLevelMax = Ivy_ManLevels( p );
    // resynthesize each node once
    nNodes = Ivy_ManObjIdMax(p);
    Ivy_ManForEachNode( p, pNode, i )
    {
        // fix the fanin buffer problem
        Ivy_NodeFixBufferFanins( p, pNode, 1 );
        if ( Ivy_ObjIsBuf(pNode) )
            continue;
        // stop if all nodes have been tried once
        if ( i > nNodes )
            break;
        // for each cut, try to resynthesize it
        nGain = Ivy_NodeRewrite( p, pManRwt, pNode, fUpdateLevel, fUseZeroCost );
        if ( nGain > 0 || nGain == 0 && fUseZeroCost )
        {
            Dec_Graph_t * pGraph = Rwt_ManReadDecs(pManRwt);
            int fCompl           = Rwt_ManReadCompl(pManRwt);
/*
            {
                Ivy_Obj_t * pObj;
                int i;
                printf( "USING: (" );
                Vec_PtrForEachEntry( Rwt_ManReadLeaves(pManRwt), pObj, i )
                    printf( "%d ", Ivy_ObjFanoutNum(Ivy_Regular(pObj)) );
                printf( ")   Gain = %d.\n", nGain );
            }
            if ( nGain > 0 )
            { // print stats on the MFFC
                extern void Ivy_NodeMffsConeSuppPrint( Ivy_Obj_t * pNode );
                printf( "Node %6d : Gain = %4d  ", pNode->Id, nGain );
                Ivy_NodeMffsConeSuppPrint( pNode );
            }
*/
            // complement the FF if needed
clk = clock();
            if ( fCompl ) Dec_GraphComplement( pGraph );
            Ivy_GraphUpdateNetwork( p, pNode, pGraph, fUpdateLevel, nGain );
            if ( fCompl ) Dec_GraphComplement( pGraph );
Rwt_ManAddTimeUpdate( pManRwt, clock() - clk );
        }
    }
Rwt_ManAddTimeTotal( pManRwt, clock() - clkStart );
    // print stats
    if ( fVerbose )
        Rwt_ManPrintStats( pManRwt );
    // delete the managers
    Rwt_ManStop( pManRwt );
    p->pData = NULL;
    // fix the levels
    if ( fUpdateLevel )
        Vec_IntFree( p->vRequired ), p->vRequired = NULL;
    else
        Ivy_ManResetLevels( p );
    // check
    if ( i = Ivy_ManCleanup(p) )
        printf( "Cleanup after rewriting removed %d dangling nodes.\n", i );
    if ( !Ivy_ManCheck(p) )
        printf( "Ivy_ManRewritePre(): The check has failed.\n" );
    return 1;
}

int Ivy_NodeRewrite( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pNode, int fUpdateLevel, int fUseZeroCost )
{
    int fVeryVerbose = 0;
    Dec_Graph_t * pGraph;
    Ivy_Store_t * pStore;
    Ivy_Cut_t * pCut;
    Ivy_Obj_t * pFanin;
    unsigned uPhase, uTruthBest, uTruth;
    char * pPerm;
    int Required, nNodesSaved, nNodesSaveCur;
    int i, c, GainCur, GainBest = -1;
    int clk, clk2;

    p->nNodesConsidered++;
    // get the required times
    Required = fUpdateLevel? Vec_IntEntry( pMan->vRequired, pNode->Id ) : 1000000;
    // get the node's cuts
clk = clock();
    pStore = Ivy_NodeFindCutsAll( pMan, pNode, 5 );
p->timeCut += clock() - clk;

    // go through the cuts
clk = clock();
    for ( c = 1; c < pStore->nCuts; c++ )
    {
        pCut = pStore->pCuts + c;
        // consider only 4-input cuts
        if ( pCut->nSize != 4 )
            continue;
        // skip the cuts with buffers
        for ( i = 0; i < (int)pCut->nSize; i++ )
            if ( Ivy_ObjIsBuf( Ivy_ManObj(pMan, pCut->pArray[i]) ) )
                break;
        if ( i != pCut->nSize )
        {
            p->nCutsBad++;
            continue;
        }
        p->nCutsGood++;
        // get the fanin permutation
clk2 = clock();
        uTruth = 0xFFFF & Ivy_NodeGetTruth( pNode, pCut->pArray, pCut->nSize );  // truth table
p->timeTruth += clock() - clk2;
        pPerm = p->pPerms4[ p->pPerms[uTruth] ];
        uPhase = p->pPhases[uTruth];
        // collect fanins with the corresponding permutation/phase
        Vec_PtrClear( p->vFaninsCur );
        Vec_PtrFill( p->vFaninsCur, (int)pCut->nSize, 0 );
        for ( i = 0; i < (int)pCut->nSize; i++ )
        {
            pFanin = Ivy_ManObj( pMan, pCut->pArray[pPerm[i]] );
            assert( Ivy_ObjIsNode(pFanin) || Ivy_ObjIsCi(pFanin) );
            pFanin = Ivy_NotCond(pFanin, ((uPhase & (1<<i)) > 0) );
            Vec_PtrWriteEntry( p->vFaninsCur, i, pFanin );
        }
clk2 = clock();
/*
        printf( "Considering: (" );
        Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
            printf( "%d ", Ivy_ObjFanoutNum(Ivy_Regular(pFanin)) );
        printf( ")\n" );
*/
        // mark the fanin boundary 
        Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
            Ivy_ObjRefsInc( Ivy_Regular(pFanin) );
        // label MFFC with current ID
        Ivy_ManIncrementTravId( pMan );
        nNodesSaved = Ivy_ObjMffcLabel( pMan, pNode );
        // unmark the fanin boundary
        Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
            Ivy_ObjRefsDec( Ivy_Regular(pFanin) );
p->timeMffc += clock() - clk2;

        // evaluate the cut
clk2 = clock();
        pGraph = Rwt_CutEvaluate( pMan, p, pNode, p->vFaninsCur, nNodesSaved, Required, &GainCur, uTruth );
p->timeEval += clock() - clk2;

        // check if the cut is better than the current best one
        if ( pGraph != NULL && GainBest < GainCur )
        {
            // save this form
            nNodesSaveCur = nNodesSaved;
            GainBest  = GainCur;
            p->pGraph  = pGraph;
            p->fCompl = ((uPhase & (1<<4)) > 0);
            uTruthBest = uTruth;
            // collect fanins in the
            Vec_PtrClear( p->vFanins );
            Vec_PtrForEachEntry( p->vFaninsCur, pFanin, i )
                Vec_PtrPush( p->vFanins, pFanin );
        }
    }
p->timeRes += clock() - clk;

    if ( GainBest == -1 )
        return -1;

//    printf( "%d", nNodesSaveCur - GainBest );
/*
    if ( GainBest > 0 )
    {
        if ( Rwt_CutIsintean( pNode, p->vFanins ) )
            printf( "b" );
        else
        {
            printf( "Node %d : ", pNode->Id );
            Vec_PtrForEachEntry( p->vFanins, pFanin, i )
                printf( "%d ", Ivy_Regular(pFanin)->Id );
            printf( "a" );
        }
    }
*/
/*
    if ( GainBest > 0 )
        if ( p->fCompl )
            printf( "c" );
        else
            printf( "." );
*/

    // copy the leaves
    Vec_PtrForEachEntry( p->vFanins, pFanin, i )
        Dec_GraphNode(p->pGraph, i)->pFunc = pFanin;

    p->nScores[p->pMap[uTruthBest]]++;
    p->nNodesGained += GainBest;
    if ( fUseZeroCost || GainBest > 0 )
        p->nNodesRewritten++;

    // report the progress
    if ( fVeryVerbose && GainBest > 0 )
    {
        printf( "Node %6d :   ", Ivy_ObjId(pNode) );
        printf( "Fanins = %d. ", p->vFanins->nSize );
        printf( "Save = %d.  ", nNodesSaveCur );
        printf( "Add = %d.  ",  nNodesSaveCur-GainBest );
        printf( "GAIN = %d.  ", GainBest );
        printf( "Cone = %d.  ", p->pGraph? Dec_GraphNodeNum(p->pGraph) : 0 );
        printf( "Class = %d.  ", p->pMap[uTruthBest] );
        printf( "\n" );
    }
    return GainBest;
}

unsigned Ivy_NodeGetTruth_rec( Ivy_Obj_t * pObj, int * pNums, int nNums )
{
    static unsigned uMasks[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
    unsigned uTruth0, uTruth1;
    int i;
    for ( i = 0; i < nNums; i++ )
        if ( pObj->Id == pNums[i] )
            return uMasks[i];
    assert( Ivy_ObjIsNode(pObj) || Ivy_ObjIsBuf(pObj) );
    uTruth0 = Ivy_NodeGetTruth_rec( Ivy_ObjFanin0(pObj), pNums, nNums );
    if ( Ivy_ObjFaninC0(pObj) )
        uTruth0 = ~uTruth0;
    if ( Ivy_ObjIsBuf(pObj) )
        return uTruth0;
    uTruth1 = Ivy_NodeGetTruth_rec( Ivy_ObjFanin1(pObj), pNums, nNums );
    if ( Ivy_ObjFaninC1(pObj) )
        uTruth1 = ~uTruth1;
    return uTruth0 & uTruth1;
}


unsigned Ivy_NodeGetTruth( Ivy_Obj_t * pObj, int * pNums, int nNums )
{
    assert( nNums < 6 );
    return Ivy_NodeGetTruth_rec( pObj, pNums, nNums );
}

Dec_Graph_t * Rwt_CutEvaluate( Ivy_Man_t * pMan, Rwt_Man_t * p, Ivy_Obj_t * pRoot, Vec_Ptr_t * vFaninsCur, int nNodesSaved, int LevelMax, int * pGainBest, unsigned uTruth )
{
    Vec_Ptr_t * vSubgraphs;
    Dec_Graph_t * pGraphBest, * pGraphCur;
    Rwt_Node_t * pNode, * pFanin;
    int nNodesAdded, GainBest, i, k;
    // find the matching class of subgraphs
    vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[uTruth] );
    p->nSubgraphs += vSubgraphs->nSize;
    // determine the best subgraph
    GainBest = -1;
    Vec_PtrForEachEntry( vSubgraphs, pNode, i )
    {
        // get the current graph
        pGraphCur = (Dec_Graph_t *)pNode->pNext;
        // copy the leaves
        Vec_PtrForEachEntry( vFaninsCur, pFanin, k )
            Dec_GraphNode(pGraphCur, k)->pFunc = pFanin;
        // detect how many unlabeled nodes will be reused
        nNodesAdded = Ivy_GraphToNetworkCount( pMan, pRoot, pGraphCur, nNodesSaved, LevelMax );
        if ( nNodesAdded == -1 )
            continue;
        assert( nNodesSaved >= nNodesAdded );
        // count the gain at this node
        if ( GainBest < nNodesSaved - nNodesAdded )
        {
            GainBest   = nNodesSaved - nNodesAdded;
            pGraphBest = pGraphCur;
        }
    }
    if ( GainBest == -1 )
        return NULL;
    *pGainBest = GainBest;
    return pGraphBest;
}


int Ivy_GraphToNetworkCount( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax )
{
    Dec_Node_t * pNode, * pNode0, * pNode1;
    Ivy_Obj_t * pAnd, * pAnd0, * pAnd1;
    int i, Counter, LevelNew, LevelOld;
    // check for constant function or a literal
    if ( Dec_GraphIsConst(pGraph) || Dec_GraphIsVar(pGraph) )
        return 0;
    // set the levels of the leaves
    Dec_GraphForEachLeaf( pGraph, pNode, i )
        pNode->Level = Ivy_Regular(pNode->pFunc)->Level;
    // compute the AIG size after adding the internal nodes
    Counter = 0;
    Dec_GraphForEachNode( pGraph, pNode, i )
    {
        // get the children of this node
        pNode0 = Dec_GraphNode( pGraph, pNode->eEdge0.Node );
        pNode1 = Dec_GraphNode( pGraph, pNode->eEdge1.Node );
        // get the AIG nodes corresponding to the children 
        pAnd0 = pNode0->pFunc; 
        pAnd1 = pNode1->pFunc; 
        if ( pAnd0 && pAnd1 )
        {
            // if they are both present, find the resulting node
            pAnd0 = Ivy_NotCond( pAnd0, pNode->eEdge0.fCompl );
            pAnd1 = Ivy_NotCond( pAnd1, pNode->eEdge1.fCompl );
            pAnd  = Ivy_TableLookup( p, Ivy_ObjCreateGhost(p, pAnd0, pAnd1, IVY_AND, IVY_INIT_NONE) );
            // return -1 if the node is the same as the original root
            if ( Ivy_Regular(pAnd) == pRoot )
                return -1;
        }
        else
            pAnd = NULL;
        // count the number of added nodes
        if ( pAnd == NULL || Ivy_ObjIsTravIdCurrent(p, Ivy_Regular(pAnd)) )
        {
            if ( ++Counter > NodeMax )
                return -1;
        }
        // count the number of new levels
        LevelNew = 1 + RWT_MAX( pNode0->Level, pNode1->Level );
        if ( pAnd )
        {
            if ( Ivy_Regular(pAnd) == p->pConst1 )
                LevelNew = 0;
            else if ( Ivy_Regular(pAnd) == Ivy_Regular(pAnd0) )
                LevelNew = (int)Ivy_Regular(pAnd0)->Level;
            else if ( Ivy_Regular(pAnd) == Ivy_Regular(pAnd1) )
                LevelNew = (int)Ivy_Regular(pAnd1)->Level;
            LevelOld = (int)Ivy_Regular(pAnd)->Level;
//            assert( LevelNew == LevelOld );
        }
        if ( LevelNew > LevelMax )
            return -1;
        pNode->pFunc = pAnd;
        pNode->Level = LevelNew;
    }
    return Counter;
}

Ivy_Obj_t * Ivy_GraphToNetwork( Ivy_Man_t * p, Dec_Graph_t * pGraph )
{
    Ivy_Obj_t * pAnd0, * pAnd1;
    Dec_Node_t * pNode;
    int i;
    // check for constant function
    if ( Dec_GraphIsConst(pGraph) )
        return Ivy_NotCond( Ivy_ManConst1(p), Dec_GraphIsComplement(pGraph) );
    // check for a literal
    if ( Dec_GraphIsVar(pGraph) )
        return Ivy_NotCond( Dec_GraphVar(pGraph)->pFunc, Dec_GraphIsComplement(pGraph) );
    // build the AIG nodes corresponding to the AND gates of the graph
    Dec_GraphForEachNode( pGraph, pNode, i )
    {
        pAnd0 = Ivy_NotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); 
        pAnd1 = Ivy_NotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl ); 
        pNode->pFunc = Ivy_And( p, pAnd0, pAnd1 );
    }
    // complement the result if necessary
    return Ivy_NotCond( pNode->pFunc, Dec_GraphIsComplement(pGraph) );
}

void Ivy_GraphUpdateNetwork( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain )
{
    Ivy_Obj_t * pRootNew;
    int nNodesNew, nNodesOld, Required;
    Required = fUpdateLevel? Vec_IntEntry( p->vRequired, pRoot->Id ) : 1000000;
    nNodesOld = Ivy_ManNodeNum(p);
    // create the new structure of nodes
    pRootNew = Ivy_GraphToNetwork( p, pGraph );
    assert( (int)Ivy_Regular(pRootNew)->Level <= Required );
//    if ( Ivy_Regular(pRootNew)->Level == Required )
//        printf( "Difference %d.\n", Ivy_Regular(pRootNew)->Level - Required );
    // remove the old nodes
//    Ivy_AigReplace( pMan->pManFunc, pRoot, pRootNew, fUpdateLevel );
/*
    if ( Ivy_IsComplement(pRootNew) )
        printf( "c" );
    else
        printf( "d" );
    if ( Ivy_ObjRefs(Ivy_Regular(pRootNew)) > 0 )
        printf( "%d", Ivy_ObjRefs(Ivy_Regular(pRootNew)) );
    printf( " " );
*/
    Ivy_ObjReplace( p, pRoot, pRootNew, 1, 0, 1 );
    // compare the gains
    nNodesNew = Ivy_ManNodeNum(p);
    assert( nGain <= nNodesOld - nNodesNew );
    // propagate the buffer
    Ivy_ManPropagateBuffers( p, 1 );
}

void Ivy_GraphUpdateNetwork3( Ivy_Man_t * p, Ivy_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain )
{
    Ivy_Obj_t * pRootNew, * pFanin;
    int nNodesNew, nNodesOld, i, nRefsOld;
    nNodesOld = Ivy_ManNodeNum(p);

//printf( "Before = %d. ", Ivy_ManNodeNum(p) );
    // mark the cut
    Vec_PtrForEachEntry( ((Rwt_Man_t *)p->pData)->vFanins, pFanin, i )
        Ivy_ObjRefsInc( Ivy_Regular(pFanin) );
    // deref the old cone
    nRefsOld = pRoot->nRefs;  
    pRoot->nRefs = 0;
    Ivy_ObjDelete_rec( p, pRoot, 0 );
    pRoot->nRefs = nRefsOld;
    // unmark the cut
    Vec_PtrForEachEntry( ((Rwt_Man_t *)p->pData)->vFanins, pFanin, i )
        Ivy_ObjRefsDec( Ivy_Regular(pFanin) );
//printf( "Deref = %d. ", Ivy_ManNodeNum(p) );
 
    // create the new structure of nodes
    pRootNew = Ivy_GraphToNetwork( p, pGraph );
//printf( "Create = %d. ", Ivy_ManNodeNum(p) );
    // remove the old nodes
//    Ivy_AigReplace( pMan->pManFunc, pRoot, pRootNew, fUpdateLevel );
/*
    if ( Ivy_IsComplement(pRootNew) )
        printf( "c" );
    else
        printf( "d" );
    if ( Ivy_ObjRefs(Ivy_Regular(pRootNew)) > 0 )
        printf( "%d", Ivy_ObjRefs(Ivy_Regular(pRootNew)) );
    printf( " " );
*/
    Ivy_ObjReplace( p, pRoot, pRootNew, 0, 0, 1 );
//printf( "Replace = %d. ", Ivy_ManNodeNum(p) );

    // delete remaining dangling nodes
    Vec_PtrForEachEntry( ((Rwt_Man_t *)p->pData)->vFanins, pFanin, i )
    {
        pFanin = Ivy_Regular(pFanin);
        if ( !Ivy_ObjIsNone(pFanin) && Ivy_ObjRefs(pFanin) == 0 )
            Ivy_ObjDelete_rec( p, pFanin, 1 );
    }
//printf( "Deref = %d. ", Ivy_ManNodeNum(p) );
//printf( "\n" );

    // compare the gains
    nNodesNew = Ivy_ManNodeNum(p);
    assert( nGain <= nNodesOld - nNodesNew );
}

---