diff options
Diffstat (limited to 'src/base/abci/abcLut.c')
| -rw-r--r-- | src/base/abci/abcLut.c | 786 |
1 files changed, 0 insertions, 786 deletions
diff --git a/src/base/abci/abcLut.c b/src/base/abci/abcLut.c deleted file mode 100644 index afa76cc8..00000000 --- a/src/base/abci/abcLut.c +++ /dev/null @@ -1,786 +0,0 @@ -/**CFile**************************************************************** - - FileName [abcLut.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Network and node package.] - - Synopsis [Superchoicing for K-LUTs.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: abcLut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "abc.h" -#include "cut.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -#define SCL_LUT_MAX 6 // the maximum LUT size -#define SCL_VARS_MAX 15 // the maximum number of variables -#define SCL_NODE_MAX 1000 // the maximum number of nodes - -typedef struct Abc_ManScl_t_ Abc_ManScl_t; -struct Abc_ManScl_t_ -{ - // paramers - int nLutSize; // the LUT size - int nCutSizeMax; // the max number of leaves of the cone - int nNodesMax; // the max number of divisors in the cone - int nWords; // the number of machine words in sim info - // structural representation of the cone - Vec_Ptr_t * vLeaves; // leaves of the cut - Vec_Ptr_t * vVolume; // volume of the cut - int pBSet[SCL_VARS_MAX]; // bound set - // functional representation of the cone - unsigned * uTruth; // truth table of the cone - // representation of truth tables - unsigned ** uVars; // elementary truth tables - unsigned ** uSims; // truth tables of the nodes - unsigned ** uCofs; // truth tables of the cofactors -}; - -static Vec_Ptr_t * s_pLeaves = NULL; - -static Cut_Man_t * Abc_NtkStartCutManForScl( Abc_Ntk_t * pNtk, int nLutSize ); -static Abc_ManScl_t * Abc_ManSclStart( int nLutSize, int nCutSizeMax, int nNodesMax ); -static void Abc_ManSclStop( Abc_ManScl_t * p ); -static void Abc_NodeLutMap( Cut_Man_t * pManCuts, Abc_Obj_t * pObj ); - -static Abc_Obj_t * Abc_NodeSuperChoiceLut( Abc_ManScl_t * pManScl, Abc_Obj_t * pObj ); -static int Abc_NodeDecomposeStep( Abc_ManScl_t * pManScl ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Performs superchoicing for K-LUTs.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NtkSuperChoiceLut( Abc_Ntk_t * pNtk, int nLutSize, int nCutSizeMax, int fVerbose ) -{ - ProgressBar * pProgress; - Abc_ManCut_t * pManCut; - Abc_ManScl_t * pManScl; - Cut_Man_t * pManCuts; - Abc_Obj_t * pObj, * pFanin, * pObjTop; - int i, LevelMax, nNodes; - int nNodesTried, nNodesDec, nNodesExist, nNodesUsed; - - assert( Abc_NtkIsSopLogic(pNtk) ); - if ( nLutSize < 3 || nLutSize > SCL_LUT_MAX ) - { - printf( "LUT size (%d) does not belong to the interval: 3 <= LUT size <= %d\n", nLutSize, SCL_LUT_MAX ); - return 0; - } - if ( nCutSizeMax <= nLutSize || nCutSizeMax > SCL_VARS_MAX ) - { - printf( "Cut size (%d) does not belong to the interval: LUT size (%d) < Cut size <= %d\n", nCutSizeMax, nLutSize, SCL_VARS_MAX ); - return 0; - } - - assert( nLutSize <= SCL_LUT_MAX ); - assert( nCutSizeMax <= SCL_VARS_MAX ); - nNodesTried = nNodesDec = nNodesExist = nNodesUsed = 0; - - // set the delays of the CIs - Abc_NtkForEachCi( pNtk, pObj, i ) - pObj->Level = 0; - -//Abc_NtkLevel( pNtk ); - - // start the managers - pManScl = Abc_ManSclStart( nLutSize, nCutSizeMax, 1000 ); - pManCuts = Abc_NtkStartCutManForScl( pNtk, nLutSize ); - pManCut = Abc_NtkManCutStart( nCutSizeMax, 100000, 100000, 100000 ); - s_pLeaves = Abc_NtkManCutReadCutSmall( pManCut ); - pManScl->vVolume = Abc_NtkManCutReadVisited( pManCut ); - - // process each internal node (assuming topological order of nodes!!!) - nNodes = Abc_NtkObjNumMax(pNtk); - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - Abc_NtkForEachObj( pNtk, pObj, i ) - { -// if ( i != nNodes-1 ) -// continue; - Extra_ProgressBarUpdate( pProgress, i, NULL ); - if ( i >= nNodes ) - break; - if ( Abc_ObjFaninNum(pObj) != 2 ) - continue; - nNodesTried++; - - // map this node using regular cuts -// pObj->Level = 0; - Abc_NodeLutMap( pManCuts, pObj ); - // compute the cut - pManScl->vLeaves = Abc_NodeFindCut( pManCut, pObj, 0 ); - if ( Vec_PtrSize(pManScl->vLeaves) <= nLutSize ) - continue; - // get the volume of the cut - if ( Vec_PtrSize(pManScl->vVolume) > SCL_NODE_MAX ) - continue; - nNodesDec++; - - // decompose the cut - pObjTop = Abc_NodeSuperChoiceLut( pManScl, pObj ); - if ( pObjTop == NULL ) - continue; - nNodesExist++; - - // if there is no delay improvement, skip; otherwise, update level - if ( pObjTop->Level >= pObj->Level ) - { - Abc_NtkDeleteObj_rec( pObjTop, 1 ); - continue; - } - pObj->Level = pObjTop->Level; - nNodesUsed++; - } - Extra_ProgressBarStop( pProgress ); - - // delete the managers - Abc_ManSclStop( pManScl ); - Abc_NtkManCutStop( pManCut ); - Cut_ManStop( pManCuts ); - - // get the largest arrival time - LevelMax = 0; - Abc_NtkForEachCo( pNtk, pObj, i ) - { - pFanin = Abc_ObjFanin0( pObj ); - // skip inv/buf - if ( Abc_ObjFaninNum(pFanin) == 1 ) - pFanin = Abc_ObjFanin0( pFanin ); - // get the new level - LevelMax = ABC_MAX( LevelMax, (int)pFanin->Level ); - } - - if ( fVerbose ) - printf( "Try = %d. Dec = %d. Exist = %d. Use = %d. SUPER = %d levels of %d-LUTs.\n", - nNodesTried, nNodesDec, nNodesExist, nNodesUsed, LevelMax, nLutSize ); -// if ( fVerbose ) -// printf( "The network is superchoiced for %d levels of %d-LUTs.\n", LevelMax, nLutSize ); - - // clean the data field - Abc_NtkForEachObj( pNtk, pObj, i ) - pObj->pNext = NULL; - - // check - if ( !Abc_NtkCheck( pNtk ) ) - { - printf( "Abc_NtkSuperChoiceLut: The network check has failed.\n" ); - return 0; - } - return 1; -} - -/**Function************************************************************* - - Synopsis [Performs LUT mapping of the node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeLutMap( Cut_Man_t * pManCuts, Abc_Obj_t * pObj ) -{ - Cut_Cut_t * pCut; - Abc_Obj_t * pFanin; - int i, DelayMax; - pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCuts, pObj, 0, 0 ); - assert( pCut != NULL ); - assert( pObj->Level == 0 ); - // go through the cuts - pObj->Level = ABC_INFINITY; - for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext ) - { - DelayMax = 0; - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - { - pFanin = Abc_NtkObj( pObj->pNtk, pCut->pLeaves[i] ); -// assert( Abc_ObjIsCi(pFanin) || pFanin->Level > 0 ); // should hold if node ordering is topological - if ( DelayMax < (int)pFanin->Level ) - DelayMax = pFanin->Level; - } - if ( (int)pObj->Level > DelayMax ) - pObj->Level = DelayMax; - } - assert( pObj->Level < ABC_INFINITY ); - pObj->Level++; -// printf( "%d(%d) ", pObj->Id, pObj->Level ); -} - -/**Function************************************************************* - - Synopsis [Starts the cut manager for rewriting.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Man_t * Abc_NtkStartCutManForScl( Abc_Ntk_t * pNtk, int nLutSize ) -{ - 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 = nLutSize; // the max cut size ("k" of the k-feasible cuts) - pParams->nKeepMax = 500; // 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->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 manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_ManScl_t * Abc_ManSclStart( int nLutSize, int nCutSizeMax, int nNodesMax ) -{ - Abc_ManScl_t * p; - int i, k; - assert( sizeof(unsigned) == 4 ); - p = ALLOC( Abc_ManScl_t, 1 ); - memset( p, 0, sizeof(Abc_ManScl_t) ); - p->nLutSize = nLutSize; - p->nCutSizeMax = nCutSizeMax; - p->nNodesMax = nNodesMax; - p->nWords = Extra_TruthWordNum(nCutSizeMax); - // allocate simulation info - p->uVars = (unsigned **)Extra_ArrayAlloc( nCutSizeMax, p->nWords, 4 ); - p->uSims = (unsigned **)Extra_ArrayAlloc( nNodesMax, p->nWords, 4 ); - p->uCofs = (unsigned **)Extra_ArrayAlloc( 2 << nLutSize, p->nWords, 4 ); - memset( p->uVars[0], 0, nCutSizeMax * p->nWords * 4 ); - // assign elementary truth tables - for ( k = 0; k < p->nCutSizeMax; k++ ) - for ( i = 0; i < p->nWords * 32; i++ ) - if ( i & (1 << k) ) - p->uVars[k][i>>5] |= (1 << (i&31)); - // other data structures -// p->vBound = Vec_IntAlloc( nCutSizeMax ); - return p; -} - -/**Function************************************************************* - - Synopsis [Stops the manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_ManSclStop( Abc_ManScl_t * p ) -{ -// Vec_IntFree( p->vBound ); - free( p->uVars ); - free( p->uSims ); - free( p->uCofs ); - free( p ); -} - - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned * Abc_NodeSuperChoiceTruth( Abc_ManScl_t * pManScl ) -{ - Abc_Obj_t * pObj; - unsigned * puData0, * puData1, * puData; - char * pSop; - int i, k; - // set elementary truth tables - Vec_PtrForEachEntry( pManScl->vLeaves, pObj, i ) - pObj->pNext = (Abc_Obj_t *)pManScl->uVars[i]; - // compute truth tables for internal nodes - Vec_PtrForEachEntry( pManScl->vVolume, pObj, i ) - { - // set storage for the node's simulation info - pObj->pNext = (Abc_Obj_t *)pManScl->uSims[i]; - // get pointer to the simulation info - puData = (unsigned *)pObj->pNext; - puData0 = (unsigned *)Abc_ObjFanin0(pObj)->pNext; - puData1 = (unsigned *)Abc_ObjFanin1(pObj)->pNext; - // simulate - pSop = pObj->pData; - if ( pSop[0] == '0' && pSop[1] == '0' ) - for ( k = 0; k < pManScl->nWords; k++ ) - puData[k] = ~puData0[k] & ~puData1[k]; - else if ( pSop[0] == '0' ) - for ( k = 0; k < pManScl->nWords; k++ ) - puData[k] = ~puData0[k] & puData1[k]; - else if ( pSop[1] == '0' ) - for ( k = 0; k < pManScl->nWords; k++ ) - puData[k] = puData0[k] & ~puData1[k]; - else - for ( k = 0; k < pManScl->nWords; k++ ) - puData[k] = puData0[k] & puData1[k]; - } - return puData; -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeSuperChoiceCollect2_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vVolume ) -{ - if ( pObj->fMarkC ) - return; - pObj->fMarkC = 1; - assert( Abc_ObjFaninNum(pObj) == 2 ); - Abc_NodeSuperChoiceCollect2_rec( Abc_ObjFanin0(pObj), vVolume ); - Abc_NodeSuperChoiceCollect2_rec( Abc_ObjFanin1(pObj), vVolume ); - Vec_PtrPush( vVolume, pObj ); -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeSuperChoiceCollect2( Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume ) -{ - Abc_Obj_t * pObj; - int i; - Vec_PtrForEachEntry( vLeaves, pObj, i ) - pObj->fMarkC = 1; - Vec_PtrClear( vVolume ); - Abc_NodeSuperChoiceCollect2_rec( pRoot, vVolume ); - Vec_PtrForEachEntry( vLeaves, pObj, i ) - pObj->fMarkC = 0; - Vec_PtrForEachEntry( vVolume, pObj, i ) - pObj->fMarkC = 0; -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeSuperChoiceCollect_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume ) -{ - if ( pObj->fMarkB ) - { - Vec_PtrPush( vLeaves, pObj ); - pObj->fMarkB = 0; - } - if ( pObj->fMarkC ) - return; - pObj->fMarkC = 1; - assert( Abc_ObjFaninNum(pObj) == 2 ); - Abc_NodeSuperChoiceCollect_rec( Abc_ObjFanin0(pObj), vLeaves, vVolume ); - Abc_NodeSuperChoiceCollect_rec( Abc_ObjFanin1(pObj), vLeaves, vVolume ); - Vec_PtrPush( vVolume, pObj ); -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [Orders the leaves topologically.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeSuperChoiceCollect( Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume ) -{ - Abc_Obj_t * pObj; - int i, nLeaves; - nLeaves = Vec_PtrSize(vLeaves); - Vec_PtrForEachEntry( vLeaves, pObj, i ) - pObj->fMarkB = pObj->fMarkC = 1; - Vec_PtrClear( vVolume ); - Vec_PtrClear( vLeaves ); - Abc_NodeSuperChoiceCollect_rec( pRoot, vLeaves, vVolume ); - assert( Vec_PtrSize(vLeaves) == nLeaves ); - Vec_PtrForEachEntry( vLeaves, pObj, i ) - pObj->fMarkC = 0; - Vec_PtrForEachEntry( vVolume, pObj, i ) - pObj->fMarkC = 0; -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeLeavesRemove( Vec_Ptr_t * vLeaves, unsigned uPhase, int nVars ) -{ - int i; - for ( i = nVars - 1; i >= 0; i-- ) - if ( uPhase & (1 << i) ) - Vec_PtrRemove( vLeaves, Vec_PtrEntry(vLeaves, i) ); -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeGetLevel( Abc_Obj_t * pObj ) -{ - Abc_Obj_t * pFanin; - int i, Level; - Level = 0; - Abc_ObjForEachFanin( pObj, pFanin, i ) - Level = ABC_MAX( Level, (int)pFanin->Level ); - return Level + 1; -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Abc_NodeSuperChoiceLut( Abc_ManScl_t * p, Abc_Obj_t * pObj ) -{ - Abc_Obj_t * pFanin, * pObjNew; - int i, nVars, uSupport, nSuppVars; - // collect the cone using DFS (excluding leaves) - Abc_NodeSuperChoiceCollect2( pObj, p->vLeaves, p->vVolume ); - assert( Vec_PtrEntryLast(p->vVolume) == pObj ); - // compute the truth table - p->uTruth = Abc_NodeSuperChoiceTruth( p ); - // get the support of this truth table - nVars = Vec_PtrSize(p->vLeaves); - uSupport = Extra_TruthSupport(p->uTruth, nVars); - nSuppVars = Extra_WordCountOnes(uSupport); - assert( nSuppVars <= nVars ); - if ( nSuppVars == 0 ) - { - pObj->Level = 0; - return NULL; - } - if ( nSuppVars == 1 ) - { - // find the variable - for ( i = 0; i < nVars; i++ ) - if ( uSupport & (1 << i) ) - break; - assert( i < nVars ); - pFanin = Vec_PtrEntry( p->vLeaves, i ); - pObj->Level = pFanin->Level; - return NULL; - } - // support-minimize the truth table - if ( nSuppVars != nVars ) - { - Extra_TruthShrink( p->uCofs[0], p->uTruth, nSuppVars, nVars, uSupport ); - Extra_TruthCopy( p->uTruth, p->uCofs[0], nVars ); - Abc_NodeLeavesRemove( p->vLeaves, ((1 << nVars) - 1) & ~uSupport, nVars ); - } -// return NULL; - // decompose the truth table recursively - while ( Vec_PtrSize(p->vLeaves) > p->nLutSize ) - if ( !Abc_NodeDecomposeStep( p ) ) - { - Vec_PtrForEachEntry( p->vLeaves, pFanin, i ) - if ( Abc_ObjIsNode(pFanin) && Abc_ObjFanoutNum(pFanin) == 0 ) - Abc_NtkDeleteObj_rec( pFanin, 1 ); - return NULL; - } - // create the topmost node - pObjNew = Abc_NtkCreateNode( pObj->pNtk ); - Vec_PtrForEachEntry( p->vLeaves, pFanin, i ) - Abc_ObjAddFanin( pObjNew, pFanin ); - // create the function - pObjNew->pData = Abc_SopCreateFromTruth( pObj->pNtk->pManFunc, Vec_PtrSize(p->vLeaves), p->uTruth ); // need ISOP - pObjNew->Level = Abc_NodeGetLevel( pObjNew ); - return pObjNew; -} - -/**Function************************************************************* - - Synopsis [Procedure used for sorting the nodes in increasing order of levels.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeCompareLevelsInc( int * pp1, int * pp2 ) -{ - Abc_Obj_t * pNode1, * pNode2; - pNode1 = Vec_PtrEntry(s_pLeaves, *pp1); - pNode2 = Vec_PtrEntry(s_pLeaves, *pp2); - if ( pNode1->Level < pNode2->Level ) - return -1; - if ( pNode1->Level > pNode2->Level ) - return 1; - return 0; -} - -/**Function************************************************************* - - Synopsis [Selects the earliest arriving nodes from the array.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeDecomposeSort( Abc_Obj_t ** pLeaves, int nVars, int * pBSet, int nLutSize ) -{ - Abc_Obj_t * pTemp[SCL_VARS_MAX]; - int i, k, kBest, LevelMin; - assert( nLutSize < nVars ); - assert( nVars <= SCL_VARS_MAX ); - // copy nodes into the internal storage -// printf( "(" ); - for ( i = 0; i < nVars; i++ ) - { - pTemp[i] = pLeaves[i]; -// printf( " %d", pLeaves[i]->Level ); - } -// printf( " )\n" ); - // choose one node at a time - for ( i = 0; i < nLutSize; i++ ) - { - kBest = -1; - LevelMin = ABC_INFINITY; - for ( k = 0; k < nVars; k++ ) - if ( pTemp[k] && LevelMin > (int)pTemp[k]->Level ) - { - LevelMin = pTemp[k]->Level; - kBest = k; - } - pBSet[i] = kBest; - pTemp[kBest] = NULL; - } -} - -/**Function************************************************************* - - Synopsis [Performs superchoicing for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeDecomposeStep( Abc_ManScl_t * p ) -{ - static char pCofClasses[1<<SCL_LUT_MAX][1<<SCL_LUT_MAX]; - static char nCofClasses[1<<SCL_LUT_MAX]; - Abc_Ntk_t * pNtk; - Abc_Obj_t * pObjNew, * pFanin, * pNodesNew[SCL_LUT_MAX]; - unsigned * pTruthCof, * pTruthClass, * pTruth, uPhase; - int i, k, c, v, w, nVars, nVarsNew, nClasses, nCofs; - // set the network - pNtk = ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, 0))->pNtk; - // find the earliest nodes - nVars = Vec_PtrSize(p->vLeaves); - assert( nVars > p->nLutSize ); -/* - for ( v = 0; v < nVars; v++ ) - p->pBSet[v] = v; - qsort( (void *)p->pBSet, nVars, sizeof(int), - (int (*)(const void *, const void *)) Abc_NodeCompareLevelsInc ); -*/ - Abc_NodeDecomposeSort( (Abc_Obj_t **)Vec_PtrArray(p->vLeaves), Vec_PtrSize(p->vLeaves), p->pBSet, p->nLutSize ); - assert( ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, p->pBSet[0]))->Level <= - ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, p->pBSet[1]))->Level ); - // cofactor w.r.t. the selected variables - Extra_TruthCopy( p->uCofs[1], p->uTruth, nVars ); - c = 2; - for ( v = 0; v < p->nLutSize; v++ ) - for ( k = 0; k < (1<<v); k++ ) - { - Extra_TruthCopy( p->uCofs[c], p->uCofs[c/2], nVars ); - Extra_TruthCopy( p->uCofs[c+1], p->uCofs[c/2], nVars ); - Extra_TruthCofactor0( p->uCofs[c], nVars, p->pBSet[v] ); - Extra_TruthCofactor1( p->uCofs[c+1], nVars, p->pBSet[v] ); - c += 2; - } - assert( c == (2 << p->nLutSize) ); - // count unique cofactors - nClasses = 0; - nCofs = (1 << p->nLutSize); - for ( i = 0; i < nCofs; i++ ) - { - pTruthCof = p->uCofs[ nCofs + i ]; - for ( k = 0; k < nClasses; k++ ) - { - pTruthClass = p->uCofs[ nCofs + pCofClasses[k][0] ]; - if ( Extra_TruthIsEqual( pTruthCof, pTruthClass, nVars ) ) - { - pCofClasses[k][ nCofClasses[k]++ ] = i; - break; - } - } - if ( k != nClasses ) - continue; - // not found - pCofClasses[nClasses][0] = i; - nCofClasses[nClasses] = 1; - nClasses++; - if ( nClasses > nCofs/2 ) - return 0; - } - // the number of cofactors is acceptable - nVarsNew = Extra_Base2Log( nClasses ); - assert( nVarsNew < p->nLutSize ); - // create the remainder truth table - // for each class of cofactors, multiply cofactor truth table by its code - Extra_TruthClear( p->uTruth, nVars ); - for ( k = 0; k < nClasses; k++ ) - { - pTruthClass = p->uCofs[ nCofs + pCofClasses[k][0] ]; - for ( v = 0; v < nVarsNew; v++ ) - if ( k & (1 << v) ) - Extra_TruthAnd( pTruthClass, pTruthClass, p->uVars[p->pBSet[v]], nVars ); - else - Extra_TruthSharp( pTruthClass, pTruthClass, p->uVars[p->pBSet[v]], nVars ); - Extra_TruthOr( p->uTruth, p->uTruth, pTruthClass, nVars ); - } - // create nodes - pTruth = p->uCofs[0]; - for ( v = 0; v < nVarsNew; v++ ) - { - Extra_TruthClear( pTruth, p->nLutSize ); - for ( k = 0; k < nClasses; k++ ) - if ( k & (1 << v) ) - for ( i = 0; i < nCofClasses[k]; i++ ) - { - pTruthCof = p->uCofs[1]; - Extra_TruthFill( pTruthCof, p->nLutSize ); - for ( w = 0; w < p->nLutSize; w++ ) - if ( pCofClasses[k][i] & (1 << (p->nLutSize-1-w)) ) - Extra_TruthAnd( pTruthCof, pTruthCof, p->uVars[w], p->nLutSize ); - else - Extra_TruthSharp( pTruthCof, pTruthCof, p->uVars[w], p->nLutSize ); - Extra_TruthOr( pTruth, pTruth, pTruthCof, p->nLutSize ); - } - // implement the node - pObjNew = Abc_NtkCreateNode( pNtk ); - for ( i = 0; i < p->nLutSize; i++ ) - { - pFanin = Vec_PtrEntry( p->vLeaves, p->pBSet[i] ); - Abc_ObjAddFanin( pObjNew, pFanin ); - } - // create the function - pObjNew->pData = Abc_SopCreateFromTruth( pNtk->pManFunc, p->nLutSize, pTruth ); // need ISOP - pObjNew->Level = Abc_NodeGetLevel( pObjNew ); - pNodesNew[v] = pObjNew; - } - // put the new nodes back into the list - for ( v = 0; v < nVarsNew; v++ ) - Vec_PtrWriteEntry( p->vLeaves, p->pBSet[v], pNodesNew[v] ); - // compute the variables that should be removed - uPhase = 0; - for ( v = nVarsNew; v < p->nLutSize; v++ ) - uPhase |= (1 << p->pBSet[v]); - // remove entries from the array - Abc_NodeLeavesRemove( p->vLeaves, uPhase, nVars ); - // update truth table - Extra_TruthShrink( p->uCofs[0], p->uTruth, nVars - p->nLutSize + nVarsNew, nVars, ((1 << nVars) - 1) & ~uPhase ); - Extra_TruthCopy( p->uTruth, p->uCofs[0], nVars ); - assert( !Extra_TruthVarInSupport( p->uTruth, nVars, nVars - p->nLutSize + nVarsNew ) ); - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |