diff options
Diffstat (limited to 'src/aig')
-rw-r--r-- | src/aig/aig/aig.h | 1 | ||||
-rw-r--r-- | src/aig/aig/aigDup.c | 2 | ||||
-rw-r--r-- | src/aig/aig/aigRepr.c | 2 | ||||
-rw-r--r-- | src/aig/nwk/nwk.h | 5 | ||||
-rw-r--r-- | src/aig/nwk/nwkSpeedup.c | 319 |
5 files changed, 325 insertions, 4 deletions
diff --git a/src/aig/aig/aig.h b/src/aig/aig/aig.h index f04a420d..13a82817 100644 --- a/src/aig/aig/aig.h +++ b/src/aig/aig/aig.h @@ -544,6 +544,7 @@ extern void Aig_ObjCreateRepr( Aig_Man_t * p, Aig_Obj_t * pNode1, Aig extern void Aig_ManTransferRepr( Aig_Man_t * pNew, Aig_Man_t * p ); extern Aig_Man_t * Aig_ManDupRepr( Aig_Man_t * p, int fOrdered ); extern Aig_Man_t * Aig_ManRehash( Aig_Man_t * p ); +extern int Aig_ObjCheckTfi( Aig_Man_t * p, Aig_Obj_t * pNew, Aig_Obj_t * pOld ); extern void Aig_ManMarkValidChoices( Aig_Man_t * p ); extern int Aig_TransferMappedClasses( Aig_Man_t * pAig, Aig_Man_t * pPart, int * pMapBack ); /*=== aigRet.c ========================================================*/ diff --git a/src/aig/aig/aigDup.c b/src/aig/aig/aigDup.c index ca1f1cc3..61e71c31 100644 --- a/src/aig/aig/aigDup.c +++ b/src/aig/aig/aigDup.c @@ -255,7 +255,7 @@ Aig_Man_t * Aig_ManDupDfs( Aig_Man_t * p ) pObj->pData = pObjNew; } } - assert( Aig_ManBufNum(p) != 0 || Aig_ManNodeNum(p) == Aig_ManNodeNum(pNew) ); + assert( p->pEquivs != NULL || Aig_ManBufNum(p) != 0 || Aig_ManNodeNum(p) == Aig_ManNodeNum(pNew) ); if ( p->pEquivs == NULL && p->pReprs == NULL && (nNodes = Aig_ManCleanup( pNew )) ) printf( "Aig_ManDupDfs(): Cleanup after AIG duplication removed %d nodes.\n", nNodes ); // duplicate the timing manager diff --git a/src/aig/aig/aigRepr.c b/src/aig/aig/aigRepr.c index eff31fff..422dea47 100644 --- a/src/aig/aig/aigRepr.c +++ b/src/aig/aig/aigRepr.c @@ -341,6 +341,8 @@ int Aig_ObjCheckTfi_rec( Aig_Man_t * p, Aig_Obj_t * pNode, Aig_Obj_t * pOld ) // check the trivial cases if ( pNode == NULL ) return 0; + if ( Aig_ObjIsPi(pNode) ) + return 0; // if ( pNode->Id < pOld->Id ) // cannot use because of choices of pNode // return 0; if ( pNode == pOld ) diff --git a/src/aig/nwk/nwk.h b/src/aig/nwk/nwk.h index 191ca3e5..eafc1bbf 100644 --- a/src/aig/nwk/nwk.h +++ b/src/aig/nwk/nwk.h @@ -231,8 +231,13 @@ extern Nwk_Obj_t * Nwk_ManCreateBox( Nwk_Man_t * pMan, int nFanins, int nFan extern Nwk_Obj_t * Nwk_ManCreateLatch( Nwk_Man_t * pMan ); extern void Nwk_ManDeleteNode( Nwk_Obj_t * pObj ); extern void Nwk_ManDeleteNode_rec( Nwk_Obj_t * pObj ); +/*=== nwkSpeedup.c ============================================================*/ +extern Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose ); +/*=== nwkStrash.c ============================================================*/ +extern Aig_Man_t * Nwk_ManStrash( Nwk_Man_t * pNtk ); /*=== nwkTiming.c ============================================================*/ extern int Nwk_ManVerifyTiming( Nwk_Man_t * pNtk ); +extern void Nwk_ManDelayTraceSortPins( Nwk_Obj_t * pNode, int * pPinPerm, float * pPinDelays ); extern float Nwk_ManDelayTraceLut( Nwk_Man_t * pNtk ); extern void Nwk_ManDelayTracePrint( Nwk_Man_t * pNtk ); extern void Nwk_ManUpdate( Nwk_Obj_t * pObj, Nwk_Obj_t * pObjNew, Vec_Vec_t * vLevels ); diff --git a/src/aig/nwk/nwkSpeedup.c b/src/aig/nwk/nwkSpeedup.c index 1eb7cbdd..80404a44 100644 --- a/src/aig/nwk/nwkSpeedup.c +++ b/src/aig/nwk/nwkSpeedup.c @@ -30,7 +30,7 @@ /**Function************************************************************* - Synopsis [] + Synopsis [Adds strashed nodes for one node.] Description [] @@ -39,9 +39,322 @@ SeeAlso [] ***********************************************************************/ -Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk ) +int Aig_ManSpeedupNode_rec( Aig_Man_t * pAig, Aig_Obj_t * pNode, Vec_Ptr_t * vNodes ) { - return NULL; + if ( Aig_ObjIsTravIdCurrent(pAig, pNode) ) + return 1; + if ( Aig_ObjIsPi(pNode) ) + return 0; + assert( Aig_ObjIsNode(pNode) ); + Aig_ObjSetTravIdCurrent( pAig, pNode ); + if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin0(pNode), vNodes ) ) + return 0; + if ( !Aig_ManSpeedupNode_rec( pAig, Aig_ObjFanin1(pNode), vNodes ) ) + return 0; + Vec_PtrPush( vNodes, pNode ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Adds strashed nodes for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Aig_ManSpeedupNode( Nwk_Man_t * pNtk, Aig_Man_t * pAig, Nwk_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vTimes ) +{ + Vec_Ptr_t * vNodes; + Nwk_Obj_t * pObj, * pObj2; + Aig_Obj_t * ppCofs[32], * pAnd, * pTemp; + int nCofs, i, k, nSkip; + + // quit of regulars are the same + Vec_PtrForEachEntry( vLeaves, pObj, i ) + Vec_PtrForEachEntry( vLeaves, pObj2, k ) + if ( i != k && Aig_Regular(pObj->pCopy) == Aig_Regular(pObj2->pCopy) ) + { +// printf( "Identical after structural hashing!!!\n" ); + return; + } + + // collect the AIG nodes + vNodes = Vec_PtrAlloc( 100 ); + Aig_ManIncrementTravId( pAig ); + Aig_ObjSetTravIdCurrent( pAig, Aig_ManConst1(pAig) ); + Vec_PtrForEachEntry( vLeaves, pObj, i ) + { + pAnd = pObj->pCopy; + Aig_ObjSetTravIdCurrent( pAig, Aig_Regular(pAnd) ); + } + // traverse from the root node + pAnd = pNode->pCopy; + if ( !Aig_ManSpeedupNode_rec( pAig, Aig_Regular(pAnd), vNodes ) ) + { +// printf( "Bad node!!!\n" ); + Vec_PtrFree( vNodes ); + return; + } + + // derive cofactors + nCofs = (1 << Vec_PtrSize(vTimes)); + for ( i = 0; i < nCofs; i++ ) + { + Vec_PtrForEachEntry( vLeaves, pObj, k ) + { + pAnd = pObj->pCopy; + Aig_Regular(pAnd)->pData = Aig_Regular(pAnd); + } + Vec_PtrForEachEntry( vTimes, pObj, k ) + { + pAnd = pObj->pCopy; + Aig_Regular(pAnd)->pData = Aig_NotCond( Aig_ManConst1(pAig), ((i & (1<<k)) == 0) ); + } + Vec_PtrForEachEntry( vNodes, pTemp, k ) + pTemp->pData = Aig_And( pAig, Aig_ObjChild0Copy(pTemp), Aig_ObjChild1Copy(pTemp) ); + // save the result + pAnd = pNode->pCopy; + ppCofs[i] = Aig_NotCond( Aig_Regular(pAnd)->pData, Aig_IsComplement(pAnd) ); + } + Vec_PtrFree( vNodes ); + +//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] ); +//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[1] ); + + // collect the resulting tree + Vec_PtrForEachEntry( vTimes, pObj, k ) + for ( nSkip = (1<<k), i = 0; i < nCofs; i += 2*nSkip ) + { + pAnd = pObj->pCopy; + ppCofs[i] = Aig_Mux( pAig, Aig_Regular(pAnd), ppCofs[i+nSkip], ppCofs[i] ); + } +//Nwk_ObjAddFanin( Nwk_ManCreatePo(pAig), ppCofs[0] ); + + // create choice node + pAnd = Aig_Regular(pNode->pCopy); // repr + pTemp = Aig_Regular(ppCofs[0]); // new + if ( pAig->pEquivs[pAnd->Id] == NULL && pAig->pEquivs[pTemp->Id] == NULL && !Aig_ObjCheckTfi(pAig, pTemp, pAnd) ) + pAig->pEquivs[pAnd->Id] = pTemp; +} + +/**Function************************************************************* + + Synopsis [Determines timing-critical edges of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Nwk_ManDelayTraceTCEdges( Nwk_Man_t * pNtk, Nwk_Obj_t * pNode, float tDelta, int fUseLutLib ) +{ + int pPinPerm[32]; + float pPinDelays[32]; + If_Lib_t * pLutLib = fUseLutLib? pNtk->pLutLib : NULL; + Nwk_Obj_t * pFanin; + unsigned uResult = 0; + float tRequired, * pDelays; + int k; + tRequired = Nwk_ObjRequired(pNode); + if ( pLutLib == NULL ) + { + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Nwk_ObjArrival(pFanin) + 1.0 + tDelta ) + uResult |= (1 << k); + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)]; + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Nwk_ObjArrival(pFanin) + pDelays[0] + tDelta ) + uResult |= (1 << k); + } + else + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pNode)]; + Nwk_ManDelayTraceSortPins( pNode, pPinPerm, pPinDelays ); + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( tRequired < Nwk_ObjArrival(Nwk_ObjFanin(pNode,pPinPerm[k])) + pDelays[k] + tDelta ) + uResult |= (1 << pPinPerm[k]); + } + return uResult; +} + +/**Function************************************************************* + + Synopsis [Adds choices to speed up the network by the given percentage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Aig_Man_t * Nwk_ManSpeedup( Nwk_Man_t * pNtk, int fUseLutLib, int Percentage, int Degree, int fVerbose, int fVeryVerbose ) +{ + Aig_Man_t * pAig, * pTemp; + Vec_Ptr_t * vTimeCries, * vTimeFanins; + Nwk_Obj_t * pNode, * pFanin, * pFanin2; + Aig_Obj_t * pAnd; + If_Lib_t * pTempLib = pNtk->pLutLib; + float tDelta, tArrival; + int i, k, k2, Counter, CounterRes, nTimeCris; + unsigned * puTCEdges; + // perform delay trace + if ( !fUseLutLib ) + pNtk->pLutLib = NULL; + tArrival = Nwk_ManDelayTraceLut( pNtk ); + tDelta = fUseLutLib ? tArrival*Percentage/100.0 : 1.0; + if ( fVerbose ) + { + printf( "Max delay = %.2f. Delta = %.2f. ", tArrival, tDelta ); + printf( "Using %s model. ", fUseLutLib? "LUT library" : "unit-delay" ); + if ( fUseLutLib ) + printf( "Percentage = %d. ", Percentage ); + printf( "\n" ); + } + // mark the timing critical nodes and edges + puTCEdges = ALLOC( int, Nwk_ManObjNumMax(pNtk) ); + memset( puTCEdges, 0, sizeof(int) * Nwk_ManObjNumMax(pNtk) ); + Nwk_ManForEachNode( pNtk, pNode, i ) + { + if ( Nwk_ObjSlack(pNode) >= tDelta ) + continue; + puTCEdges[pNode->Id] = Nwk_ManDelayTraceTCEdges( pNtk, pNode, tDelta, fUseLutLib ); + } + if ( fVerbose ) + { + Counter = CounterRes = 0; + Nwk_ManForEachNode( pNtk, pNode, i ) + { + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( !Nwk_ObjIsCi(pFanin) && Nwk_ObjSlack(pFanin) < tDelta ) + Counter++; + CounterRes += Aig_WordCountOnes( puTCEdges[pNode->Id] ); + } + printf( "Edges: Total = %7d. 0-slack = %7d. Critical = %7d. Ratio = %4.2f\n", + Nwk_ManGetTotalFanins(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 ); + } + // start the resulting network + pAig = Nwk_ManStrash( pNtk ); + pAig->pEquivs = ALLOC( Aig_Obj_t *, 3 * Aig_ManObjNumMax(pAig) ); + memset( pAig->pEquivs, 0, sizeof(Aig_Obj_t *) * 3 * Aig_ManObjNumMax(pAig) ); + + // collect nodes to be used for resynthesis + Counter = CounterRes = 0; + vTimeCries = Vec_PtrAlloc( 16 ); + vTimeFanins = Vec_PtrAlloc( 16 ); + Nwk_ManForEachNode( pNtk, pNode, i ) + { + if ( Nwk_ObjSlack(pNode) >= tDelta ) + continue; + // count the number of non-PI timing-critical nodes + nTimeCris = 0; + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) ) + nTimeCris++; + if ( !fVeryVerbose && nTimeCris == 0 ) + continue; + Counter++; + // count the total number of timing critical second-generation nodes + Vec_PtrClear( vTimeCries ); + if ( nTimeCris ) + { + Nwk_ObjForEachFanin( pNode, pFanin, k ) + if ( !Nwk_ObjIsCi(pFanin) && (puTCEdges[pNode->Id] & (1<<k)) ) + Nwk_ObjForEachFanin( pFanin, pFanin2, k2 ) + if ( puTCEdges[pFanin->Id] & (1<<k2) ) + Vec_PtrPushUnique( vTimeCries, pFanin2 ); + } +// if ( !fVeryVerbose && (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + if ( (Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree) ) + continue; + CounterRes++; + // collect second generation nodes + Vec_PtrClear( vTimeFanins ); + Nwk_ObjForEachFanin( pNode, pFanin, k ) + { + if ( Nwk_ObjIsCi(pFanin) ) + Vec_PtrPushUnique( vTimeFanins, pFanin ); + else + Nwk_ObjForEachFanin( pFanin, pFanin2, k2 ) + Vec_PtrPushUnique( vTimeFanins, pFanin2 ); + } + // print the results + if ( fVeryVerbose ) + { + printf( "%5d Node %5d : %d %2d %2d ", Counter, pNode->Id, + nTimeCris, Vec_PtrSize(vTimeCries), Vec_PtrSize(vTimeFanins) ); + Nwk_ObjForEachFanin( pNode, pFanin, k ) + printf( "%d(%.2f)%s ", pFanin->Id, Nwk_ObjSlack(pFanin), (puTCEdges[pNode->Id] & (1<<k))? "*":"" ); + printf( "\n" ); + } + // add the node to choices + if ( Vec_PtrSize(vTimeCries) == 0 || Vec_PtrSize(vTimeCries) > Degree ) + continue; + // order the fanins in the increasing order of criticalily + if ( Vec_PtrSize(vTimeCries) > 1 ) + { + pFanin = Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = Vec_PtrEntry( vTimeCries, 1 ); + if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + if ( Vec_PtrSize(vTimeCries) > 2 ) + { + pFanin = Vec_PtrEntry( vTimeCries, 1 ); + pFanin2 = Vec_PtrEntry( vTimeCries, 2 ); + if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 1, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 2, pFanin ); + } + pFanin = Vec_PtrEntry( vTimeCries, 0 ); + pFanin2 = Vec_PtrEntry( vTimeCries, 1 ); + if ( Nwk_ObjSlack(pFanin) < Nwk_ObjSlack(pFanin2) ) + { + Vec_PtrWriteEntry( vTimeCries, 0, pFanin2 ); + Vec_PtrWriteEntry( vTimeCries, 1, pFanin ); + } + } + // add choice + Aig_ManSpeedupNode( pNtk, pAig, pNode, vTimeFanins, vTimeCries ); + } + Vec_PtrFree( vTimeCries ); + Vec_PtrFree( vTimeFanins ); + free( puTCEdges ); + if ( fVerbose ) + printf( "Nodes: Total = %7d. 0-slack = %7d. Workable = %7d. Ratio = %4.2f\n", + Nwk_ManNodeNum(pNtk), Counter, CounterRes, Counter? 1.0*CounterRes/Counter : 0.0 ); + + // remove invalid choice nodes + Aig_ManForEachNode( pAig, pAnd, i ) + if ( pAig->pEquivs[pAnd->Id] ) + { + if ( Aig_ObjRefs(pAig->pEquivs[pAnd->Id]) > 0 ) + pAig->pEquivs[pAnd->Id] = NULL; + } + + // put back the library + if ( !fUseLutLib ) + pNtk->pLutLib = pTempLib; + + // reconstruct the network + pAig = Aig_ManDupDfs( pTemp = pAig ); + Aig_ManStop( pTemp ); + // reset levels + Aig_ManChoiceLevel( pAig ); + return pAig; } //////////////////////////////////////////////////////////////////////// |