/**CFile****************************************************************
FileName [abcRestruct.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis []
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: abcRestruct.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "base/abc/abc.h"
#include "bool/dec/dec.h"
#include "opt/cut/cut.h"
#ifdef ABC_USE_CUDD
#include "bdd/extrab/extraBdd.h"
#include "bdd/dsd/dsd.h"
#endif
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
#ifdef ABC_USE_CUDD
#define RST_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand()))
typedef struct Abc_ManRst_t_ Abc_ManRst_t;
struct Abc_ManRst_t_
{
// the network
Abc_Ntk_t * pNtk; // the network for restructuring
// user specified parameters
int nCutMax; // the limit on the size of the supernode
int fUpdateLevel; // turns on watching the number of levels
int fUseZeros; // turns on zero-cost replacements
int fVerbose; // the verbosity flag
// internal data structures
DdManager * dd; // the BDD manager
Dsd_Manager_t * pManDsd; // the DSD manager
Vec_Ptr_t * vVisited; // temporary
Vec_Ptr_t * vLeaves; // temporary
Vec_Ptr_t * vDecs; // temporary
Vec_Ptr_t * vTemp; // temporary
Vec_Int_t * vSims; // temporary
Vec_Int_t * vRands; // temporary
Vec_Int_t * vOnes; // temporary
Vec_Int_t * vBinate; // temporary
Vec_Int_t * vTwos; // temporary
// node statistics
int nLastGain;
int nCutsConsidered;
int nCutsExplored;
int nNodesConsidered;
int nNodesRestructured;
int nNodesGained;
// runtime statistics
int timeCut;
int timeBdd;
int timeDsd;
int timeEval;
int timeRes;
int timeNtk;
int timeTotal;
};
static Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList );
static Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList );
static Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCut );
static Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded );
static Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag );
static Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose );
static void Abc_NtkManRstStop( Abc_ManRst_t * p );
static void Abc_NtkManRstPrintStats( Abc_ManRst_t * p );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Implements AIG restructuring.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NtkRestructure( Abc_Ntk_t * pNtk, int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose )
{
extern void Dec_GraphUpdateNetwork( Abc_Obj_t * pRoot, Dec_Graph_t * pGraph, int fUpdateLevel, int nGain );
ProgressBar * pProgress;
Abc_ManRst_t * pManRst;
Cut_Man_t * pManCut;
Cut_Cut_t * pCutList;
Dec_Graph_t * pGraph;
Abc_Obj_t * pNode;
abctime clk, clkStart = Abc_Clock();
int fMulti = 1;
int fResub = 0;
int i, nNodes;
assert( Abc_NtkIsStrash(pNtk) );
// cleanup the AIG
Abc_AigCleanup((Abc_Aig_t *)pNtk->pManFunc);
Abc_NtkCleanCopy(pNtk);
// compute the reverse levels if level update is requested
if ( fUpdateLevel )
Abc_NtkStartReverseLevels( pNtk, 0 );
// start the restructuring manager
pManRst = Abc_NtkManRstStart( nCutMax, fUpdateLevel, fUseZeros, fVerbose );
pManRst->pNtk = pNtk;
// start the cut manager
clk = Abc_Clock();
pManCut = Abc_NtkStartCutManForRestruct( pNtk, nCutMax, fMulti );
pManRst->timeCut += Abc_Clock() - clk;
// pNtk->pManCut = pManCut;
// resynthesize each node once
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 node if it is inside the tree
// if ( Abc_ObjFanoutNum(pNode) < 2 )
// continue;
// skip the nodes with too many fanouts
if ( Abc_ObjFanoutNum(pNode) > 1000 )
continue;
// stop if all nodes have been tried once
if ( i >= nNodes )
break;
// get the cuts for the given node
clk = Abc_Clock();
pCutList = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCut, pNode, fMulti, 0 );
pManRst->timeCut += Abc_Clock() - clk;
// perform restructuring
clk = Abc_Clock();
if ( fResub )
pGraph = Abc_NodeResubstitute( pManRst, pNode, pCutList );
else
pGraph = Abc_NodeRestructure( pManRst, pNode, pCutList );
pManRst->timeRes += Abc_Clock() - clk;
if ( pGraph == NULL )
continue;
// acceptable replacement found, update the graph
clk = Abc_Clock();
Dec_GraphUpdateNetwork( pNode, pGraph, fUpdateLevel, pManRst->nLastGain );
pManRst->timeNtk += Abc_Clock() - clk;
Dec_GraphFree( pGraph );
}
Extra_ProgressBarStop( pProgress );
pManRst->timeTotal = Abc_Clock() - clkStart;
// print statistics of the manager
// if ( fVerbose )
Abc_NtkManRstPrintStats( pManRst );
// delete the managers
Cut_ManStop( pManCut );
Abc_NtkManRstStop( pManRst );
// put the nodes into the DFS order and reassign their IDs
Abc_NtkReassignIds( pNtk );
// Abc_AigCheckFaninOrder( pNtk->pManFunc );
// 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 1;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_RestructNodeDivisors( Abc_ManRst_t * p, Abc_Obj_t * pRoot, int nNodesSaved )
{
Abc_Obj_t * pNode, * pFanout;//, * pFanin;
int i, k;
// start with the leaves
Vec_PtrClear( p->vDecs );
Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pNode, i )
{
Vec_PtrPush( p->vDecs, pNode );
assert( pNode->fMarkC == 0 );
pNode->fMarkC = 1;
}
// explore the fanouts
Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
{
// if the fanout has both fanins in the set, add it
Abc_ObjForEachFanout( pNode, pFanout, k )
{
if ( pFanout->fMarkC || Abc_ObjIsPo(pFanout) )
continue;
if ( Abc_ObjFanin0(pFanout)->fMarkC && Abc_ObjFanin1(pFanout)->fMarkC )
{
Vec_PtrPush( p->vDecs, pFanout );
pFanout->fMarkC = 1;
}
}
}
// unmark the nodes
Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
pNode->fMarkC = 0;
/*
// print the nodes
Vec_PtrForEachEntryStart( Abc_Obj_t *, p->vDecs, pNode, i, Vec_PtrSize(p->vLeaves) )
{
printf( "%2d %s = ", i, Abc_NodeIsTravIdCurrent(pNode)? "*" : " " );
// find the first fanin
Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k )
if ( Abc_ObjFanin0(pNode) == pFanin )
break;
if ( k < Vec_PtrSize(p->vLeaves) )
printf( "%c", 'a' + k );
else
printf( "%d", k );
printf( "%s ", Abc_ObjFaninC0(pNode)? "\'" : "" );
// find the second fanin
Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pFanin, k )
if ( Abc_ObjFanin1(pNode) == pFanin )
break;
if ( k < Vec_PtrSize(p->vLeaves) )
printf( "%c", 'a' + k );
else
printf( "%d", k );
printf( "%s ", Abc_ObjFaninC1(pNode)? "\'" : "" );
printf( "\n" );
}
*/
printf( "%d\n", Vec_PtrSize(p->vDecs)-nNodesSaved-Vec_PtrSize(p->vLeaves) );
}
/**Function*************************************************************
Synopsis [Starts the cut manager for rewriting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeRestructure( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList )
{
Dec_Graph_t * pGraph;
Cut_Cut_t * pCut;
// int nCuts;
p->nNodesConsidered++;
/*
// count the number of cuts with four inputs or more
nCuts = 0;
for ( pCut = pCutList; pCut; pCut = pCut->pNext )
nCuts += (int)(pCut->nLeaves > 3);
printf( "-----------------------------------\n" );
printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts );
*/
// go through the interesting cuts
for ( pCut = pCutList; pCut; pCut = pCut->pNext )
{
if ( pCut->nLeaves < 4 )
continue;
if ( (pGraph = Abc_NodeRestructureCut( p, pNode, pCut )) )
return pGraph;
}
return NULL;
}
/**Function*************************************************************
Synopsis [Starts the cut manager for rewriting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeRestructureCut( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
{
extern DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pNode, Vec_Ptr_t * vFanins, Vec_Ptr_t * vVisited );
Dec_Graph_t * pGraph;
Dsd_Node_t * pNodeDsd;
Abc_Obj_t * pLeaf;
DdNode * bFunc;
int nNodesSaved, nNodesAdded;
int Required, nMaxSize, clk, i;
int fVeryVerbose = 0;
p->nCutsConsidered++;
// get the required time for the node
Required = p->fUpdateLevel? Abc_ObjRequiredLevel(pRoot) : ABC_INFINITY;
// collect the leaves of the cut
Vec_PtrClear( p->vLeaves );
for ( i = 0; i < (int)pCut->nLeaves; i++ )
{
pLeaf = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]);
if ( pLeaf == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes
return NULL;
Vec_PtrPush( p->vLeaves, pLeaf );
}
clk = Abc_Clock();
// collect the internal nodes of the cut
// Abc_NodeConeCollect( &pRoot, 1, p->vLeaves, p->vVisited, 0 );
// derive the BDD of the cut
bFunc = Abc_NodeConeBdd( p->dd, p->dd->vars, pRoot, p->vLeaves, p->vVisited ); Cudd_Ref( bFunc );
p->timeBdd += Abc_Clock() - clk;
// consider the special case, when the function is a constant
if ( Cudd_IsConstant(bFunc) )
{
p->nLastGain = Abc_NodeMffcSize( pRoot );
p->nNodesGained += p->nLastGain;
p->nNodesRestructured++;
Cudd_RecursiveDeref( p->dd, bFunc );
if ( Cudd_IsComplement(bFunc) )
return Dec_GraphCreateConst0();
return Dec_GraphCreateConst1();
}
clk = Abc_Clock();
// try disjoint support decomposition
pNodeDsd = Dsd_DecomposeOne( p->pManDsd, bFunc );
p->timeDsd += Abc_Clock() - clk;
// skip nodes with non-decomposable blocks
Dsd_TreeNodeGetInfoOne( pNodeDsd, NULL, &nMaxSize );
if ( nMaxSize > 3 )
{
Cudd_RecursiveDeref( p->dd, bFunc );
return NULL;
}
/*
// skip nodes that cannot be improved
if ( Vec_PtrSize(p->vVisited) <= Dsd_TreeGetAigCost(pNodeDsd) )
{
Cudd_RecursiveDeref( p->dd, bFunc );
return NULL;
}
*/
p->nCutsExplored++;
// mark the fanin boundary
// (can mark only essential fanins, belonging to bNodeFunc!)
Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i )
pLeaf->vFanouts.nSize++;
// label MFFC with current traversal ID
Abc_NtkIncrementTravId( pRoot->pNtk );
nNodesSaved = Abc_NodeMffcLabelAig( pRoot );
// unmark the fanin boundary and set the fanins as leaves in the form
Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pLeaf, i )
pLeaf->vFanouts.nSize--;
/*
if ( nNodesSaved < 3 )
{
Cudd_RecursiveDeref( p->dd, bFunc );
return NULL;
}
*/
/*
printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d.\n",
pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd),
nNodesSaved );
Dsd_NodePrint( stdout, pNodeDsd );
Abc_RestructNodeDivisors( p, pRoot );
if ( pRoot->Id == 433 )
{
int x = 0;
}
*/
// Abc_RestructNodeDivisors( p, pRoot, nNodesSaved );
// detect how many new nodes will be added (while taking into account reused nodes)
clk = Abc_Clock();
if ( nMaxSize > 3 )
pGraph = NULL;
else
pGraph = Abc_NodeEvaluateDsd( p, pNodeDsd, pRoot, Required, nNodesSaved, &nNodesAdded );
// pGraph = NULL;
p->timeEval += Abc_Clock() - clk;
// quit if there is no improvement
if ( pGraph == NULL || nNodesAdded == -1 || (nNodesAdded == nNodesSaved && !p->fUseZeros) )
{
Cudd_RecursiveDeref( p->dd, bFunc );
if ( pGraph ) Dec_GraphFree( pGraph );
return NULL;
}
/*
// print stats
printf( "%5d : Cut-size = %d. Old AIG = %2d. New AIG = %2d. Old MFFC = %2d. New MFFC = %2d. Gain = %d.\n",
pRoot->Id, pCut->nLeaves, Vec_PtrSize(p->vVisited), Dsd_TreeGetAigCost(pNodeDsd),
nNodesSaved, nNodesAdded, (nNodesAdded == -1)? 0 : nNodesSaved-nNodesAdded );
// Dsd_NodePrint( stdout, pNodeDsd );
// Dec_GraphPrint( stdout, pGraph, NULL, NULL );
*/
// compute the total gain in the number of nodes
p->nLastGain = nNodesSaved - nNodesAdded;
p->nNodesGained += p->nLastGain;
p->nNodesRestructured++;
// report the progress
if ( fVeryVerbose )
{
printf( "Node %6s : ", Abc_ObjName(pRoot) );
printf( "Cone = %2d. ", p->vLeaves->nSize );
printf( "BDD = %2d. ", Cudd_DagSize(bFunc) );
printf( "FF = %2d. ", 1 + Dec_GraphNodeNum(pGraph) );
printf( "MFFC = %2d. ", nNodesSaved );
printf( "Add = %2d. ", nNodesAdded );
printf( "GAIN = %2d. ", p->nLastGain );
printf( "\n" );
}
Cudd_RecursiveDeref( p->dd, bFunc );
return pGraph;
}
/**Function*************************************************************
Synopsis [Moves closer to the end the node that is best for sharing.]
Description [If the flag is set, tries to find an EXOR, otherwise, tries
to find an OR.]
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeEdgeDsdPermute( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Vec_Int_t * vEdges, int fExor )
{
Dec_Edge_t eNode1, eNode2, eNode3;
Abc_Obj_t * pNode1, * pNode2, * pNode3, * pTemp;
int LeftBound = 0, RightBound, i;
// get the right bound
RightBound = Vec_IntSize(vEdges) - 2;
assert( LeftBound <= RightBound );
if ( LeftBound == RightBound )
return;
// get the two last nodes
eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound + 1) );
eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, RightBound ) );
pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
// quit if the last node does not exist
if ( pNode1 == NULL )
return;
// find the first node that can be shared
for ( i = RightBound; i >= LeftBound; i-- )
{
// get the third node
eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, i) );
pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc;
pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl );
if ( pNode3 == NULL )
continue;
// check if the node exists
if ( fExor )
{
if ( pNode1 && pNode3 )
{
pTemp = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode3, NULL );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
continue;
if ( pNode3 == pNode2 )
return;
Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) );
Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) );
return;
}
}
else
{
if ( pNode1 && pNode3 )
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
continue;
if ( eNode3.Node == eNode2.Node )
return;
Vec_IntWriteEntry( vEdges, i, Dec_EdgeToInt(eNode2) );
Vec_IntWriteEntry( vEdges, RightBound, Dec_EdgeToInt(eNode3) );
return;
}
}
}
}
/**Function*************************************************************
Synopsis [Adds the new edge in the given order.]
Description [Similar to Vec_IntPushOrder, except in decreasing order.]
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeEdgeDsdPushOrdered( Dec_Graph_t * pGraph, Vec_Int_t * vEdges, int Edge )
{
int i, NodeOld, NodeNew;
vEdges->nSize++;
for ( i = vEdges->nSize-2; i >= 0; i-- )
{
NodeOld = Dec_IntToEdge(vEdges->pArray[i]).Node;
NodeNew = Dec_IntToEdge(Edge).Node;
// use <= because we are trying to push the new (non-existent) nodes as far as possible
if ( Dec_GraphNode(pGraph, NodeOld)->Level <= Dec_GraphNode(pGraph, NodeNew)->Level )
vEdges->pArray[i+1] = vEdges->pArray[i];
else
break;
}
vEdges->pArray[i+1] = Edge;
}
/**Function*************************************************************
Synopsis [Evaluation one DSD.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Edge_t Abc_NodeEvaluateDsd_rec( Dec_Graph_t * pGraph, Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, int Required, int nNodesSaved, int * pnNodesAdded )
{
Dec_Edge_t eNode1, eNode2, eNode3, eResult, eQuit = { 0, 2006 };
Abc_Obj_t * pNode1, * pNode2, * pNode3, * pNode4, * pTemp;
Dsd_Node_t * pChildDsd;
Dsd_Type_t DecType;
Vec_Int_t * vEdges;
int Level1, Level2, Level3, Level4;
int i, Index, fCompl, Type;
// remove the complemented attribute
fCompl = Dsd_IsComplement( pNodeDsd );
pNodeDsd = Dsd_Regular( pNodeDsd );
// consider the trivial case
DecType = Dsd_NodeReadType( pNodeDsd );
if ( DecType == DSD_NODE_BUF )
{
Index = Dsd_NodeReadFunc(pNodeDsd)->index;
assert( Index < Dec_GraphLeaveNum(pGraph) );
eResult = Dec_EdgeCreate( Index, fCompl );
return eResult;
}
assert( DecType == DSD_NODE_OR || DecType == DSD_NODE_EXOR || DecType == DSD_NODE_PRIME );
// solve the problem for the children
vEdges = Vec_IntAlloc( Dsd_NodeReadDecsNum(pNodeDsd) );
Dsd_NodeForEachChild( pNodeDsd, i, pChildDsd )
{
eResult = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pChildDsd, Required, nNodesSaved, pnNodesAdded );
if ( eResult.Node == eQuit.Node ) // infeasible
{
Vec_IntFree( vEdges );
return eQuit;
}
// order the inputs only if this is OR or EXOR
if ( DecType == DSD_NODE_PRIME )
Vec_IntPush( vEdges, Dec_EdgeToInt(eResult) );
else
Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eResult) );
}
// the edges are sorted by the level of their nodes in decreasing order
// consider special cases
if ( DecType == DSD_NODE_OR )
{
// try to balance the nodes by delay
assert( Vec_IntSize(vEdges) > 1 );
while ( Vec_IntSize(vEdges) > 1 )
{
// permute the last two entries
if ( Vec_IntSize(vEdges) > 2 )
Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 0 );
// get the two last nodes
eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) );
eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) );
pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
// check if the new node exists
pNode3 = NULL;
if ( pNode1 && pNode2 )
{
pNode3 = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
pNode3 = !pNode3? NULL : Abc_ObjNot(pNode3);
}
// create the new node
eNode3 = Dec_GraphAddNodeOr( pGraph, eNode1, eNode2 );
// set level
Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
Dec_GraphNode( pGraph, eNode3.Node )->Level = 1 + Abc_MaxInt(Level1, Level2);
// get the new node if possible
if ( pNode3 )
{
Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl);
Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level );
}
if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) )
{
(*pnNodesAdded)++;
if ( *pnNodesAdded > nNodesSaved )
{
Vec_IntFree( vEdges );
return eQuit;
}
}
// add the resulting node to the form
Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) );
}
// get the last node
eResult = Dec_IntToEdge( Vec_IntPop(vEdges) );
Vec_IntFree( vEdges );
// complement the graph if the node was complemented
eResult.fCompl ^= fCompl;
return eResult;
}
if ( DecType == DSD_NODE_EXOR )
{
// try to balance the nodes by delay
assert( Vec_IntSize(vEdges) > 1 );
while ( Vec_IntSize(vEdges) > 1 )
{
// permute the last two entries
if ( Vec_IntSize(vEdges) > 2 )
Abc_NodeEdgeDsdPermute( pGraph, pManRst, vEdges, 1 );
// get the two last nodes
eNode1 = Dec_IntToEdge( Vec_IntPop(vEdges) );
eNode2 = Dec_IntToEdge( Vec_IntPop(vEdges) );
pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
// check if the new node exists
Type = 0;
pNode3 = NULL;
if ( pNode1 && pNode2 )
pNode3 = Abc_AigXorLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, &Type );
// create the new node
eNode3 = Dec_GraphAddNodeXor( pGraph, eNode1, eNode2, Type ); // should have the same structure as in AIG
// set level
Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
Dec_GraphNode( pGraph, eNode3.Node )->Level = 2 + Abc_MaxInt(Level1, Level2);
// get the new node if possible
if ( pNode3 )
{
Dec_GraphNode( pGraph, eNode3.Node )->pFunc = Abc_ObjNotCond(pNode3, eNode3.fCompl);
Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
assert( Required == ABC_INFINITY || Level3 == (int)Abc_ObjRegular(pNode3)->Level );
}
if ( !pNode3 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode3)) )
{
(*pnNodesAdded)++;
if ( !pNode1 || !pNode2 )
(*pnNodesAdded) += 2;
else if ( Type == 0 )
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode2 );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
else
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode2) );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
if ( *pnNodesAdded > nNodesSaved )
{
Vec_IntFree( vEdges );
return eQuit;
}
}
// add the resulting node to the form
Abc_NodeEdgeDsdPushOrdered( pGraph, vEdges, Dec_EdgeToInt(eNode3) );
}
// get the last node
eResult = Dec_IntToEdge( Vec_IntPop(vEdges) );
Vec_IntFree( vEdges );
// complement the graph if the node is complemented
eResult.fCompl ^= fCompl;
return eResult;
}
if ( DecType == DSD_NODE_PRIME )
{
DdNode * bLocal, * bVar, * bCofT, * bCofE;
bLocal = Dsd_TreeGetPrimeFunction( pManRst->dd, pNodeDsd ); Cudd_Ref( bLocal );
//Extra_bddPrint( pManRst->dd, bLocal );
bVar = pManRst->dd->vars[0];
bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
{
Cudd_RecursiveDeref( pManRst->dd, bCofE );
Cudd_RecursiveDeref( pManRst->dd, bCofT );
bVar = pManRst->dd->vars[1];
bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
{
Cudd_RecursiveDeref( pManRst->dd, bCofE );
Cudd_RecursiveDeref( pManRst->dd, bCofT );
bVar = pManRst->dd->vars[2];
bCofE = Cudd_Cofactor( pManRst->dd, bLocal, Cudd_Not(bVar) ); Cudd_Ref( bCofE );
bCofT = Cudd_Cofactor( pManRst->dd, bLocal, bVar ); Cudd_Ref( bCofT );
if ( !Extra_bddIsVar(bCofE) || !Extra_bddIsVar(bCofT) )
{
Cudd_RecursiveDeref( pManRst->dd, bCofE );
Cudd_RecursiveDeref( pManRst->dd, bCofT );
Cudd_RecursiveDeref( pManRst->dd, bLocal );
Vec_IntFree( vEdges );
return eQuit;
}
}
}
Cudd_RecursiveDeref( pManRst->dd, bLocal );
// we found the control variable (bVar) and the var-cofactors (bCofT, bCofE)
// find the graph nodes
eNode1 = Dec_IntToEdge( Vec_IntEntry(vEdges, bVar->index) );
eNode2 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofT)->index) );
eNode3 = Dec_IntToEdge( Vec_IntEntry(vEdges, Cudd_Regular(bCofE)->index) );
// add the complements to the graph nodes
eNode2.fCompl ^= Cudd_IsComplement(bCofT);
eNode3.fCompl ^= Cudd_IsComplement(bCofE);
// because the cofactors are vars, we can just as well deref them here
Cudd_RecursiveDeref( pManRst->dd, bCofE );
Cudd_RecursiveDeref( pManRst->dd, bCofT );
// find the ABC nodes
pNode1 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode1.Node )->pFunc;
pNode2 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode2.Node )->pFunc;
pNode3 = (Abc_Obj_t *)Dec_GraphNode( pGraph, eNode3.Node )->pFunc;
pNode1 = !pNode1? NULL : Abc_ObjNotCond( pNode1, eNode1.fCompl );
pNode2 = !pNode2? NULL : Abc_ObjNotCond( pNode2, eNode2.fCompl );
pNode3 = !pNode3? NULL : Abc_ObjNotCond( pNode3, eNode3.fCompl );
// check if the new node exists
Type = 0;
pNode4 = NULL;
if ( pNode1 && pNode2 && pNode3 )
pNode4 = Abc_AigMuxLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2, pNode3, &Type );
// create the new node
eResult = Dec_GraphAddNodeMux( pGraph, eNode1, eNode2, eNode3, Type ); // should have the same structure as AIG
// set level
Level1 = Dec_GraphNode( pGraph, eNode1.Node )->Level;
Level2 = Dec_GraphNode( pGraph, eNode2.Node )->Level;
Level3 = Dec_GraphNode( pGraph, eNode3.Node )->Level;
Dec_GraphNode( pGraph, eResult.Node )->Level = 2 + Abc_MaxInt( Abc_MaxInt(Level1, Level2), Level3 );
// get the new node if possible
if ( pNode4 )
{
Dec_GraphNode( pGraph, eResult.Node )->pFunc = Abc_ObjNotCond(pNode4, eResult.fCompl);
Level4 = Dec_GraphNode( pGraph, eResult.Node )->Level;
assert( Required == ABC_INFINITY || Level4 == (int)Abc_ObjRegular(pNode4)->Level );
}
if ( !pNode4 || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pNode4)) )
{
(*pnNodesAdded)++;
if ( Type == 0 )
{
if ( !pNode1 || !pNode2 )
(*pnNodesAdded)++;
else
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, pNode2 );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
if ( !pNode1 || !pNode3 )
(*pnNodesAdded)++;
else
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), pNode3 );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
}
else
{
if ( !pNode1 || !pNode2 )
(*pnNodesAdded)++;
else
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, pNode1, Abc_ObjNot(pNode2) );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
if ( !pNode1 || !pNode3 )
(*pnNodesAdded)++;
else
{
pTemp = Abc_AigAndLookup( (Abc_Aig_t *)pManRst->pNtk->pManFunc, Abc_ObjNot(pNode1), Abc_ObjNot(pNode3) );
if ( !pTemp || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pTemp)) )
(*pnNodesAdded)++;
}
}
if ( *pnNodesAdded > nNodesSaved )
{
Vec_IntFree( vEdges );
return eQuit;
}
}
Vec_IntFree( vEdges );
// complement the graph if the node was complemented
eResult.fCompl ^= fCompl;
return eResult;
}
Vec_IntFree( vEdges );
return eQuit;
}
/**Function*************************************************************
Synopsis [Evaluation one DSD.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeEvaluateDsd( Abc_ManRst_t * pManRst, Dsd_Node_t * pNodeDsd, Abc_Obj_t * pRoot, int Required, int nNodesSaved, int * pnNodesAdded )
{
Dec_Graph_t * pGraph;
Dec_Edge_t gEdge;
Abc_Obj_t * pLeaf;
Dec_Node_t * pNode;
int i;
// create the graph and set the leaves
pGraph = Dec_GraphCreate( Vec_PtrSize(pManRst->vLeaves) );
Dec_GraphForEachLeaf( pGraph, pNode, i )
{
pLeaf = (Abc_Obj_t *)Vec_PtrEntry( pManRst->vLeaves, i );
pNode->pFunc = pLeaf;
pNode->Level = pLeaf->Level;
}
// create the decomposition structure from the DSD
*pnNodesAdded = 0;
gEdge = Abc_NodeEvaluateDsd_rec( pGraph, pManRst, pNodeDsd, Required, nNodesSaved, pnNodesAdded );
if ( gEdge.Node > 1000 ) // infeasible
{
*pnNodesAdded = -1;
Dec_GraphFree( pGraph );
return NULL;
}
// quit if the root node is the same
pLeaf = (Abc_Obj_t *)Dec_GraphNode( pGraph, gEdge.Node )->pFunc;
if ( Abc_ObjRegular(pLeaf) == pRoot )
{
*pnNodesAdded = -1;
Dec_GraphFree( pGraph );
return NULL;
}
Dec_GraphSetRoot( pGraph, gEdge );
return pGraph;
}
/**Function*************************************************************
Synopsis [Starts the cut manager for rewriting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Man_t * Abc_NtkStartCutManForRestruct( Abc_Ntk_t * pNtk, int nCutMax, int fDag )
{
static Cut_Params_t Params, * pParams = &Params;
Cut_Man_t * pManCut;
Abc_Obj_t * pObj;
int i;
// start the cut manager
memset( pParams, 0, sizeof(Cut_Params_t) );
pParams->nVarsMax = nCutMax; // the max cut size ("k" of the k-feasible cuts)
pParams->nKeepMax = 250; // the max number of cuts kept at a node
pParams->fTruth = 0; // compute truth tables
pParams->fFilter = 1; // filter dominated cuts
pParams->fSeq = 0; // compute sequential cuts
pParams->fDrop = 0; // drop cuts on the fly
pParams->fDag = fDag; // compute DAG cuts
pParams->fTree = 0; // compute tree cuts
pParams->fVerbose = 0; // the verbosiness flag
pParams->nIdsMax = Abc_NtkObjNumMax( pNtk );
pManCut = Cut_ManStart( pParams );
if ( pParams->fDrop )
Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) );
// set cuts for PIs
Abc_NtkForEachCi( pNtk, pObj, i )
if ( Abc_ObjFanoutNum(pObj) > 0 )
Cut_NodeSetTriv( pManCut, pObj->Id );
return pManCut;
}
/**Function*************************************************************
Synopsis [Starts the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Abc_ManRst_t * Abc_NtkManRstStart( int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose )
{
Abc_ManRst_t * p;
p = ABC_ALLOC( Abc_ManRst_t, 1 );
memset( p, 0, sizeof(Abc_ManRst_t) );
// set the parameters
p->nCutMax = nCutMax;
p->fUpdateLevel = fUpdateLevel;
p->fUseZeros = fUseZeros;
p->fVerbose = fVerbose;
// start the BDD manager
p->dd = Cudd_Init( p->nCutMax, 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0 );
Cudd_zddVarsFromBddVars( p->dd, 2 );
// start the DSD manager
p->pManDsd = Dsd_ManagerStart( p->dd, p->dd->size, 0 );
// other temp datastructures
p->vVisited = Vec_PtrAlloc( 100 );
p->vLeaves = Vec_PtrAlloc( 100 );
p->vDecs = Vec_PtrAlloc( 100 );
p->vTemp = Vec_PtrAlloc( 100 );
p->vSims = Vec_IntAlloc( 100 );
p->vOnes = Vec_IntAlloc( 100 );
p->vBinate = Vec_IntAlloc( 100 );
p->vTwos = Vec_IntAlloc( 100 );
p->vRands = Vec_IntAlloc( 20 );
{
int i;
for ( i = 0; i < 20; i++ )
Vec_IntPush( p->vRands, (int)RST_RANDOM_UNSIGNED );
}
return p;
}
/**Function*************************************************************
Synopsis [Stops the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkManRstStop( Abc_ManRst_t * p )
{
Dsd_ManagerStop( p->pManDsd );
Extra_StopManager( p->dd );
Vec_PtrFree( p->vDecs );
Vec_PtrFree( p->vLeaves );
Vec_PtrFree( p->vVisited );
Vec_PtrFree( p->vTemp );
Vec_IntFree( p->vSims );
Vec_IntFree( p->vOnes );
Vec_IntFree( p->vBinate );
Vec_IntFree( p->vTwos );
Vec_IntFree( p->vRands );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Stops the resynthesis manager.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NtkManRstPrintStats( Abc_ManRst_t * p )
{
printf( "Refactoring statistics:\n" );
printf( "Nodes considered = %8d.\n", p->nNodesConsidered );
printf( "Cuts considered = %8d.\n", p->nCutsConsidered );
printf( "Cuts explored = %8d.\n", p->nCutsExplored );
printf( "Nodes restructured = %8d.\n", p->nNodesRestructured );
printf( "Calculated gain = %8d.\n", p->nNodesGained );
ABC_PRT( "Cuts ", p->timeCut );
ABC_PRT( "Resynthesis", p->timeRes );
ABC_PRT( " BDD ", p->timeBdd );
ABC_PRT( " DSD ", p->timeDsd );
ABC_PRT( " Eval ", p->timeEval );
ABC_PRT( "AIG update ", p->timeNtk );
ABC_PRT( "TOTAL ", p->timeTotal );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_Abc_NodeResubCollectDivs( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
{
Abc_Obj_t * pNode, * pFanout;
int i, k;
// collect the leaves of the cut
Vec_PtrClear( p->vDecs );
Abc_NtkIncrementTravId( pRoot->pNtk );
for ( i = 0; i < (int)pCut->nLeaves; i++ )
{
pNode = Abc_NtkObj(pRoot->pNtk, pCut->pLeaves[i]);
if ( pNode == NULL ) // the so-called "bad cut phenomenon" is due to removed nodes
return 0;
Vec_PtrPush( p->vDecs, pNode );
Abc_NodeSetTravIdCurrent( pNode );
}
// explore the fanouts
Vec_PtrForEachEntry( Abc_Obj_t *, p->vDecs, pNode, i )
{
// if the fanout has both fanins in the set, add it
Abc_ObjForEachFanout( pNode, pFanout, k )
{
if ( Abc_NodeIsTravIdCurrent(pFanout) || Abc_ObjIsPo(pFanout) )
continue;
if ( Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pFanout)) && Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pFanout)) )
{
Vec_PtrPush( p->vDecs, pFanout );
Abc_NodeSetTravIdCurrent( pFanout );
}
}
}
return 1;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeResubMffc_rec( Abc_Obj_t * pNode )
{
if ( Abc_NodeIsTravIdCurrent(pNode) )
return 0;
Abc_NodeSetTravIdCurrent( pNode );
return 1 + Abc_NodeResubMffc_rec( Abc_ObjFanin0(pNode) ) +
Abc_NodeResubMffc_rec( Abc_ObjFanin1(pNode) );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeResubMffc( Abc_ManRst_t * p, Vec_Ptr_t * vDecs, int nLeaves, Abc_Obj_t * pRoot )
{
Abc_Obj_t * pObj;
int Counter, i, k;
// increment the traversal ID for the leaves
Abc_NtkIncrementTravId( pRoot->pNtk );
// label the leaves
Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
Abc_NodeSetTravIdCurrent( pObj );
// make sure the node is in the cone and is no one of the leaves
assert( Abc_NodeIsTravIdPrevious(pRoot) );
Counter = Abc_NodeResubMffc_rec( pRoot );
// move the labeled nodes to the end
Vec_PtrClear( p->vTemp );
k = 0;
Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
if ( Abc_NodeIsTravIdCurrent(pObj) )
Vec_PtrPush( p->vTemp, pObj );
else
Vec_PtrWriteEntry( vDecs, k++, pObj );
// add the labeled nodes
Vec_PtrForEachEntry( Abc_Obj_t *, p->vTemp, pObj, i )
Vec_PtrWriteEntry( vDecs, k++, pObj );
assert( k == Vec_PtrSize(p->vDecs) );
assert( pRoot == Vec_PtrEntryLast(p->vDecs) );
return Counter;
}
/**Function*************************************************************
Synopsis [Performs simulation.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeMffcSimulate( Vec_Ptr_t * vDecs, int nLeaves, Vec_Int_t * vRands, Vec_Int_t * vSims )
{
Abc_Obj_t * pObj;
unsigned uData0, uData1, uData;
int i;
// initialize random simulation data
Vec_IntClear( vSims );
Vec_PtrForEachEntryStop( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
{
uData = (unsigned)Vec_IntEntry( vRands, i );
pObj->pData = (void *)(ABC_PTRUINT_T)uData;
Vec_IntPush( vSims, uData );
}
// simulate
Vec_PtrForEachEntryStart( Abc_Obj_t *, vDecs, pObj, i, nLeaves )
{
uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
uData = (Abc_ObjFaninC0(pObj)? ~uData0 : uData0) & (Abc_ObjFaninC1(pObj)? ~uData1 : uData1);
pObj->pData = (void *)(ABC_PTRUINT_T)uData;
Vec_IntPush( vSims, uData );
}
}
/**Function*************************************************************
Synopsis [Full equality check.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeCheckFull( Abc_ManRst_t * p, Dec_Graph_t * pGraph )
{
return 1;
}
/**Function*************************************************************
Synopsis [Detect contants.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeMffcConstants( Abc_ManRst_t * p, Vec_Int_t * vSims )
{
Dec_Graph_t * pGraph = NULL;
unsigned uRoot;
// get the root node
uRoot = (unsigned)Vec_IntEntryLast( vSims );
// get the graph if the node looks constant
if ( uRoot == 0 )
pGraph = Dec_GraphCreateConst0();
else if ( uRoot == ~(unsigned)0 )
pGraph = Dec_GraphCreateConst1();
// check the graph
assert(pGraph);
if ( Abc_NodeCheckFull( p, pGraph ) )
return pGraph;
Dec_GraphFree( pGraph );
return NULL;
}
/**Function*************************************************************
Synopsis [Detect single non-overlaps.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeMffcSingleVar( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
{
Dec_Graph_t * pGraph;
unsigned uRoot, uNode;
int i;
Vec_IntClear( vOnes );
Vec_IntClear( p->vBinate );
uRoot = (unsigned)Vec_IntEntryLast( vSims );
for ( i = 0; i < nNodes; i++ )
{
uNode = (unsigned)Vec_IntEntry( vSims, i );
if ( uRoot == uNode || uRoot == ~uNode )
{
pGraph = Dec_GraphCreate( 1 );
Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, i );
Dec_GraphSetRoot( pGraph, Dec_IntToEdge( (int)(uRoot == ~uNode) ) );
// check the graph
if ( Abc_NodeCheckFull( p, pGraph ) )
return pGraph;
Dec_GraphFree( pGraph );
}
if ( (uRoot & uNode) == 0 )
Vec_IntPush( vOnes, i << 1 );
else if ( (uRoot & ~uNode) == 0 )
Vec_IntPush( vOnes, (i << 1) + 1 );
else
Vec_IntPush( p->vBinate, i );
}
return NULL;
}
/**Function*************************************************************
Synopsis [Detect single non-overlaps.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeMffcSingleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
{
Dec_Graph_t * pGraph;
Dec_Edge_t eNode0, eNode1, eRoot;
unsigned uRoot;
int i, k;
uRoot = (unsigned)Vec_IntEntryLast( vSims );
for ( i = 0; i < vOnes->nSize; i++ )
for ( k = i+1; k < vOnes->nSize; k++ )
if ( ~uRoot == ((unsigned)vOnes->pArray[i] | (unsigned)vOnes->pArray[k]) )
{
eNode0 = Dec_IntToEdge( vOnes->pArray[i] ^ 1 );
eNode1 = Dec_IntToEdge( vOnes->pArray[k] ^ 1 );
pGraph = Dec_GraphCreate( 2 );
Dec_GraphNode( pGraph, 0 )->pFunc = Vec_PtrEntry( p->vDecs, eNode0.Node );
Dec_GraphNode( pGraph, 1 )->pFunc = Vec_PtrEntry( p->vDecs, eNode1.Node );
eRoot = Dec_GraphAddNodeAnd( pGraph, eNode0, eNode1 );
Dec_GraphSetRoot( pGraph, eRoot );
if ( Abc_NodeCheckFull( p, pGraph ) )
return pGraph;
Dec_GraphFree( pGraph );
}
return NULL;
}
/**Function*************************************************************
Synopsis [Detect single non-overlaps.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeMffcDoubleNode( Abc_ManRst_t * p, Vec_Int_t * vSims, int nNodes, Vec_Int_t * vOnes )
{
// Dec_Graph_t * pGraph;
// unsigned uRoot, uNode;
// int i;
return NULL;
}
/**Function*************************************************************
Synopsis [Evaluates resubstution of one cut.]
Description [Returns the graph to add if any.]
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeResubEval( Abc_ManRst_t * p, Abc_Obj_t * pRoot, Cut_Cut_t * pCut )
{
Dec_Graph_t * pGraph;
int nNodesSaved;
// collect the nodes in the cut
if ( !Abc_Abc_NodeResubCollectDivs( p, pRoot, pCut ) )
return NULL;
// label MFFC and count its size
nNodesSaved = Abc_NodeResubMffc( p, p->vDecs, pCut->nLeaves, pRoot );
assert( nNodesSaved > 0 );
// simulate MFFC
Abc_NodeMffcSimulate( p->vDecs, pCut->nLeaves, p->vRands, p->vSims );
// check for constant output
pGraph = Abc_NodeMffcConstants( p, p->vSims );
if ( pGraph )
{
p->nNodesGained += nNodesSaved;
p->nNodesRestructured++;
return pGraph;
}
// check for one literal (fill up the ones array)
pGraph = Abc_NodeMffcSingleVar( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
if ( pGraph )
{
p->nNodesGained += nNodesSaved;
p->nNodesRestructured++;
return pGraph;
}
if ( nNodesSaved == 1 )
return NULL;
// look for one node
pGraph = Abc_NodeMffcSingleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
if ( pGraph )
{
p->nNodesGained += nNodesSaved - 1;
p->nNodesRestructured++;
return pGraph;
}
if ( nNodesSaved == 2 )
return NULL;
// look for two nodes
pGraph = Abc_NodeMffcDoubleNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved, p->vOnes );
if ( pGraph )
{
p->nNodesGained += nNodesSaved - 2;
p->nNodesRestructured++;
return pGraph;
}
if ( nNodesSaved == 3 )
return NULL;
/*
// look for MUX/EXOR
pGraph = Abc_NodeMffcMuxNode( p, p->vSims, Vec_IntSize(p->vSims) - nNodesSaved );
if ( pGraph )
{
p->nNodesGained += nNodesSaved - 1;
p->nNodesRestructured++;
return pGraph;
}
*/
return NULL;
}
/**Function*************************************************************
Synopsis [Performs resubstution.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Dec_Graph_t * Abc_NodeResubstitute( Abc_ManRst_t * p, Abc_Obj_t * pNode, Cut_Cut_t * pCutList )
{
Dec_Graph_t * pGraph, * pGraphBest = NULL;
Cut_Cut_t * pCut;
int nCuts;
p->nNodesConsidered++;
// count the number of cuts with four inputs or more
nCuts = 0;
for ( pCut = pCutList; pCut; pCut = pCut->pNext )
nCuts += (int)(pCut->nLeaves > 3);
printf( "-----------------------------------\n" );
printf( "Node %6d : Factor-cuts = %5d.\n", pNode->Id, nCuts );
// go through the interesting cuts
for ( pCut = pCutList; pCut; pCut = pCut->pNext )
{
if ( pCut->nLeaves < 4 )
continue;
pGraph = Abc_NodeResubEval( p, pNode, pCut );
if ( pGraph == NULL )
continue;
if ( !pGraphBest || Dec_GraphNodeNum(pGraph) < Dec_GraphNodeNum(pGraphBest) )
{
if ( pGraphBest )
Dec_GraphFree(pGraphBest);
pGraphBest = pGraph;
}
else
Dec_GraphFree(pGraph);
}
return pGraphBest;
}
#else
int Abc_NtkRestructure( Abc_Ntk_t * pNtk, int nCutMax, int fUpdateLevel, int fUseZeros, int fVerbose ) { return 1; }
#endif
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END