abcRefactor.c File Reference

#include "base/abc/abc.h"
#include "bool/dec/dec.h"
#include "bool/kit/kit.h"

Include dependency graph for abcRefactor.c:

Go to the source code of this file.

Classes
struct	Abc_ManRef_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Abc_ManRef_t_	Abc_ManRef_t
	DECLARATIONS ///.

Functions
word *	Abc_NodeConeTruth (Vec_Ptr_t *vVars, Vec_Ptr_t *vFuncs, int nWordsMax, Abc_Obj_t *pRoot, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vVisited)
	FUNCTION DEFINITIONS ///.
int	Abc_NodeConeIsConst0 (word *pTruth, int nVars)
int	Abc_NodeConeIsConst1 (word *pTruth, int nVars)
Dec_Graph_t *	Abc_NodeRefactor (Abc_ManRef_t *p, Abc_Obj_t *pNode, Vec_Ptr_t *vFanins, int nMinSaved, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose)
Abc_ManRef_t *	Abc_NtkManRefStart (int nNodeSizeMax, int nConeSizeMax, int fUseDcs, int fVerbose)
void	Abc_NtkManRefStop (Abc_ManRef_t *p)
void	Abc_NtkManRefPrintStats (Abc_ManRef_t *p)
int	Abc_NtkRefactor (Abc_Ntk_t *pNtk, int nNodeSizeMax, int nMinSaved, int nConeSizeMax, int fUpdateLevel, int fUseZeros, int fUseDcs, int fVerbose)
	DECLARATIONS ///.

Typedef Documentation

Abc_ManRef_t

typedef typedefABC_NAMESPACE_IMPL_START struct Abc_ManRef_t_ Abc_ManRef_t

DECLARATIONS ///.

CFile****************************************************************

FileName [abcRefactor.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Resynthesis based on collapsing and refactoring.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

abcRefactor.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 32 of file abcRefactor.c.

Function Documentation

Abc_NodeConeIsConst0()

int Abc_NodeConeIsConst0	(	word *	pTruth,
		int	nVars )

Definition at line 123 of file abcRefactor.c.

{
    int k, nWords = Abc_Truth6WordNum( nVars );
    for ( k = 0; k < nWords; k++ )
        if ( pTruth[k] )
            return 0;
    return 1;
}

Here is the caller graph for this function:

Abc_NodeConeIsConst1()

int Abc_NodeConeIsConst1	(	word *	pTruth,
		int	nVars )

Definition at line 131 of file abcRefactor.c.

{
    int k, nWords = Abc_Truth6WordNum( nVars );
    for ( k = 0; k < nWords; k++ )
        if ( ~pTruth[k] )
            return 0;
    return 1;
}

Here is the caller graph for this function:

Abc_NodeConeTruth()

word * Abc_NodeConeTruth	(	Vec_Ptr_t *	vVars,
		Vec_Ptr_t *	vFuncs,
		int	nWordsMax,
		Abc_Obj_t *	pRoot,
		Vec_Ptr_t *	vLeaves,
		Vec_Ptr_t *	vVisited )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Returns function of the cone.]

Description []

SideEffects []

SeeAlso []

Definition at line 81 of file abcRefactor.c.

{
    Abc_Obj_t * pNode;
    word * pTruth0, * pTruth1, * pTruth = NULL;
    int i, k, nWords = Abc_Truth6WordNum( Vec_PtrSize(vLeaves) );
    // get nodes in the cut without fanins in the DFS order
    Abc_NodeConeCollect( &pRoot, 1, vLeaves, vVisited, 0 );
    // set elementary functions
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
        pNode->pCopy = (Abc_Obj_t *)Vec_PtrEntry( vVars, i );
    // prepare functions
    for ( i = Vec_PtrSize(vFuncs); i < Vec_PtrSize(vVisited); i++ )
        Vec_PtrPush( vFuncs, ABC_ALLOC(word, nWordsMax) );
    // compute functions for the collected nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
    {
        assert( !Abc_ObjIsPi(pNode) );
        pTruth0 = (word *)Abc_ObjFanin0(pNode)->pCopy;
        pTruth1 = (word *)Abc_ObjFanin1(pNode)->pCopy;
        pTruth  = (word *)Vec_PtrEntry( vFuncs, i );
        if ( Abc_ObjFaninC0(pNode) )
        {
            if ( Abc_ObjFaninC1(pNode) )
                for ( k = 0; k < nWords; k++ )
                    pTruth[k] = ~pTruth0[k] & ~pTruth1[k];
            else
                for ( k = 0; k < nWords; k++ )
                    pTruth[k] = ~pTruth0[k] &  pTruth1[k];
        }
        else
        {
            if ( Abc_ObjFaninC1(pNode) )
                for ( k = 0; k < nWords; k++ )
                    pTruth[k] =  pTruth0[k] & ~pTruth1[k];
            else
                for ( k = 0; k < nWords; k++ )
                    pTruth[k] =  pTruth0[k] &  pTruth1[k];
        }
        pNode->pCopy = (Abc_Obj_t *)pTruth;
    }
    return pTruth;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NodeRefactor()

Dec_Graph_t * Abc_NodeRefactor	(	Abc_ManRef_t *	p,
		Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vFanins,
		int	nMinSaved,
		int	fUpdateLevel,
		int	fUseZeros,
		int	fUseDcs,
		int	fVerbose )

Function*************************************************************

Synopsis [Resynthesizes the node using refactoring.]

Description []

SideEffects []

SeeAlso []

Definition at line 152 of file abcRefactor.c.

{
    extern int    Dec_GraphToNetworkCount( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int NodeMax, int LevelMax );
    int fVeryVerbose = 0;
    int nVars = Vec_PtrSize(vFanins);
    int nWordsMax = Abc_Truth6WordNum(p->nNodeSizeMax);
    Dec_Graph_t * pFForm;
    Abc_Obj_t * pFanin;
    word * pTruth;
    abctime clk;
    int i, nNodesSaved, nNodesAdded, Required;
    if ( fUseZeros )
        nMinSaved = 0;
 
    p->nNodesConsidered++;
 
    Required = fUpdateLevel? Abc_ObjRequiredLevel(pNode) : ABC_INFINITY;
 
    // get the function of the cut
clk = Abc_Clock();
    pTruth = Abc_NodeConeTruth( p->vVars, p->vFuncs, nWordsMax, pNode, vFanins, p->vVisited );
p->timeTru += Abc_Clock() - clk;
    if ( pTruth == NULL )
        return NULL;
 
    // always accept the case of constant node
    if ( Abc_NodeConeIsConst0(pTruth, nVars) || Abc_NodeConeIsConst1(pTruth, nVars) )
    {
        p->nLastGain = Abc_NodeMffcSize( pNode );
        p->nNodesGained += p->nLastGain;
        p->nNodesRefactored++;
        return Abc_NodeConeIsConst0(pTruth, nVars) ? Dec_GraphCreateConst0() : Dec_GraphCreateConst1();
    }
 
    // get the factored form
clk = Abc_Clock();
    pFForm = (Dec_Graph_t *)Kit_TruthToGraph( (unsigned *)pTruth, nVars, p->vMemory );
p->timeFact += Abc_Clock() - clk;
 
    // mark the fanin boundary 
    // (can mark only essential fanins, belonging to bNodeFunc!)
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i )
        pFanin->vFanouts.nSize++;
    // label MFFC with current traversal ID
    Abc_NtkIncrementTravId( pNode->pNtk );
    nNodesSaved = Abc_NodeMffcLabelAig( pNode );
    // unmark the fanin boundary and set the fanins as leaves in the form
    Vec_PtrForEachEntry( Abc_Obj_t *, vFanins, pFanin, i )
    {
        pFanin->vFanouts.nSize--;
        Dec_GraphNode(pFForm, i)->pFunc = pFanin;
    }
 
    // detect how many new nodes will be added (while taking into account reused nodes)
clk = Abc_Clock();
    nNodesAdded = Dec_GraphToNetworkCount( pNode, pFForm, nNodesSaved, Required );
p->timeEval += Abc_Clock() - clk;
    // quit if there is no improvement
    //if ( nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !fUseZeros) )
    if ( nNodesAdded == -1 || nNodesSaved - nNodesAdded < nMinSaved )
    {
        Dec_GraphFree( pFForm );
        return NULL;
    }
 
    // compute the total gain in the number of nodes
    p->nLastGain = nNodesSaved - nNodesAdded;
    p->nNodesGained += p->nLastGain;
    p->nNodesRefactored++;
 
    // report the progress
    if ( fVeryVerbose )
    {
        printf( "Node %6s : ",  Abc_ObjName(pNode) );
        printf( "Cone = %2d. ", vFanins->nSize );
        printf( "FF = %2d. ",   1 + Dec_GraphNodeNum(pFForm) );
        printf( "MFFC = %2d. ", nNodesSaved );
        printf( "Add = %2d. ",  nNodesAdded );
        printf( "GAIN = %2d. ", p->nLastGain );
        printf( "\n" );
    }
    return pFForm;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkManRefPrintStats()

void Abc_NtkManRefPrintStats

(

Abc_ManRef_t *

p

)

Function*************************************************************

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 296 of file abcRefactor.c.

{
    printf( "Refactoring statistics:\n" );
    printf( "Nodes considered  = %8d.\n", p->nNodesConsidered );
    printf( "Nodes refactored  = %8d.\n", p->nNodesRefactored );
    printf( "Gain              = %8d. (%6.2f %%).\n", p->nNodesBeg-p->nNodesEnd, 100.0*(p->nNodesBeg-p->nNodesEnd)/p->nNodesBeg );
    ABC_PRT( "Cuts       ", p->timeCut );
    ABC_PRT( "Resynthesis", p->timeRes );
    ABC_PRT( "    BDD    ", p->timeTru );
    ABC_PRT( "    DCs    ", p->timeDcs );
    ABC_PRT( "    SOP    ", p->timeSop );
    ABC_PRT( "    FF     ", p->timeFact );
    ABC_PRT( "    Eval   ", p->timeEval );
    ABC_PRT( "AIG update ", p->timeNtk );
    ABC_PRT( "TOTAL      ", p->timeTotal );
}

Here is the caller graph for this function:

Abc_NtkManRefStart()

Abc_ManRef_t * Abc_NtkManRefStart	(	int	nNodeSizeMax,
		int	nConeSizeMax,
		int	fUseDcs,
		int	fVerbose )

Function*************************************************************

Synopsis [Starts the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 248 of file abcRefactor.c.

{
    Abc_ManRef_t * p;
    p = ABC_ALLOC( Abc_ManRef_t, 1 );
    memset( p, 0, sizeof(Abc_ManRef_t) );
    p->vCube        = Vec_StrAlloc( 100 );
    p->vVisited     = Vec_PtrAlloc( 100 );
    p->nNodeSizeMax = nNodeSizeMax;
    p->nConeSizeMax = nConeSizeMax;
    p->fVerbose     = fVerbose;
    p->vVars        = Vec_PtrAllocTruthTables( Abc_MaxInt(nNodeSizeMax, 6) );
    p->vFuncs       = Vec_PtrAlloc( 100 );
    p->vMemory      = Vec_IntAlloc( 1 << 16 );
    return p;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkManRefStop()

void Abc_NtkManRefStop

(

Abc_ManRef_t *

p

)

Function*************************************************************

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file abcRefactor.c.

{
    Vec_PtrFreeFree( p->vFuncs );
    Vec_PtrFree( p->vVars );
    Vec_IntFree( p->vMemory );
    Vec_PtrFree( p->vVisited );
    Vec_StrFree( p->vCube );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Abc_NtkRefactor()

int Abc_NtkRefactor	(	Abc_Ntk_t *	pNtk,
		int	nNodeSizeMax,
		int	nMinSaved,
		int	nConeSizeMax,
		int	fUpdateLevel,
		int	fUseZeros,
		int	fUseDcs,
		int	fVerbose )

DECLARATIONS ///.

Function*************************************************************

Synopsis [Performs incremental resynthesis of the AIG.]

Description [Starting from each node, computes a reconvergence-driven cut, derives BDD of the cut function, constructs ISOP, factors the ISOP, and replaces the current implementation of the MFFC of the node by the new factored form, if the number of AIG nodes is reduced and the total number of levels of the AIG network is not increated. Returns the number of AIG nodes saved.]

SideEffects []

SeeAlso []

Definition at line 329 of file abcRefactor.c.

{
    extern int           Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );
    ProgressBar * pProgress;
    Abc_ManRef_t * pManRef;
    Abc_ManCut_t * pManCut;
    Dec_Graph_t * pFForm;
    Vec_Ptr_t * vFanins;
    Abc_Obj_t * pNode;
    abctime clk, clkStart = Abc_Clock();
    int i, nNodes, RetValue = 1;
 
    assert( Abc_NtkIsStrash(pNtk) );
    // cleanup the AIG
    Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc);
    // start the managers
    pManCut = Abc_NtkManCutStart( nNodeSizeMax, nConeSizeMax, 2, 1000 );
    pManRef = Abc_NtkManRefStart( nNodeSizeMax, nConeSizeMax, fUseDcs, fVerbose );
    pManRef->vLeaves   = Abc_NtkManCutReadCutLarge( pManCut );
    // compute the reverse levels if level update is requested
    if ( fUpdateLevel )
        Abc_NtkStartReverseLevels( pNtk, 0 );
 
    // resynthesize each node once
    pManRef->nNodesBeg = Abc_NtkNodeNum(pNtk);
    nNodes = Abc_NtkObjNumMax(pNtk);
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        Extra_ProgressBarUpdate( pProgress, i, NULL );
        // skip the constant node
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // skip persistant nodes
        if ( Abc_NodeIsPersistant(pNode) )
            continue;
        // skip the nodes with many fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1000 )
            continue;
        // stop if all nodes have been tried once
        if ( i >= nNodes )
            break;
        // compute a reconvergence-driven cut
clk = Abc_Clock();
        vFanins = Abc_NodeFindCut( pManCut, pNode, fUseDcs );
pManRef->timeCut += Abc_Clock() - clk;
        // evaluate this cut
clk = Abc_Clock();
        pFForm = Abc_NodeRefactor( pManRef, pNode, vFanins, nMinSaved, fUpdateLevel, fUseZeros, fUseDcs, fVerbose );
pManRef->timeRes += Abc_Clock() - clk;
        if ( pFForm == NULL )
            continue;
        // acceptable replacement found, update the graph
clk = Abc_Clock();
        if ( !Dec_GraphUpdateNetwork( pNode, pFForm, fUpdateLevel, pManRef->nLastGain ) )
        {
            Dec_GraphFree( pFForm );
            RetValue = -1;
            break;
        }
pManRef->timeNtk += Abc_Clock() - clk;
        Dec_GraphFree( pFForm );
    }
    Extra_ProgressBarStop( pProgress );
pManRef->timeTotal = Abc_Clock() - clkStart;
    pManRef->nNodesEnd = Abc_NtkNodeNum(pNtk);
 
    // print statistics of the manager
    if ( fVerbose )
        Abc_NtkManRefPrintStats( pManRef );
    // delete the managers
    Abc_NtkManCutStop( pManCut );
    Abc_NtkManRefStop( pManRef );
    // put the nodes into the DFS order and reassign their IDs
    Abc_NtkReassignIds( pNtk );
//    Abc_AigCheckFaninOrder( pNtk->pManFunc );
    if ( RetValue != -1 )
    {
        // fix the levels
        if ( fUpdateLevel )
            Abc_NtkStopReverseLevels( pNtk );
        else
            Abc_NtkLevel( pNtk );
        // check
        if ( !Abc_NtkCheck( pNtk ) )
        {
            printf( "Abc_NtkRefactor: The network check has failed.\n" );
            return 0;
        }
    }
    return RetValue;
}

Here is the call graph for this function:

Here is the caller graph for this function: