/**CFile**************************************************************** FileName [cutOracle.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [K-feasible cut computation package.] Synopsis [Procedures to compute cuts for a node using the oracle.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - June 20, 2005.] Revision [$Id: cutOracle.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] ***********************************************************************/ #include "cutInt.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// struct Cut_OracleStruct_t_ { // cut comptupatation parameters Cut_Params_t * pParams; Vec_Int_t * vFanCounts; int fSimul; // storage for cuts Vec_Ptr_t * vCutsNew; Vec_Ptr_t * vCuts0; Vec_Ptr_t * vCuts1; // oracle info Vec_Int_t * vNodeCuts; Vec_Int_t * vNodeStarts; Vec_Int_t * vCutPairs; // memory management Extra_MmFixed_t * pMmCuts; int EntrySize; int nTruthWords; // stats int timeTotal; int nCuts; int nCutsTriv; }; static Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p ); static Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node ); static Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Starts the cut oracle.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Oracle_t * Cut_OracleStart( Cut_Man_t * pMan ) { Cut_Oracle_t * p; int clk = clock(); assert( pMan->pParams->nVarsMax >= 3 && pMan->pParams->nVarsMax <= CUT_SIZE_MAX ); assert( pMan->pParams->fRecord ); p = ALLOC( Cut_Oracle_t, 1 ); memset( p, 0, sizeof(Cut_Oracle_t) ); // set and correct parameters p->pParams = pMan->pParams; // transfer the recording info p->vNodeCuts = pMan->vNodeCuts; pMan->vNodeCuts = NULL; p->vNodeStarts = pMan->vNodeStarts; pMan->vNodeStarts = NULL; p->vCutPairs = pMan->vCutPairs; pMan->vCutPairs = NULL; // prepare storage for cuts p->vCutsNew = Vec_PtrAlloc( p->pParams->nIdsMax ); Vec_PtrFill( p->vCutsNew, p->pParams->nIdsMax, NULL ); p->vCuts0 = Vec_PtrAlloc( 100 ); p->vCuts1 = Vec_PtrAlloc( 100 ); // entry size p->EntrySize = sizeof(Cut_Cut_t) + p->pParams->nVarsMax * sizeof(int); if ( p->pParams->fTruth ) { if ( p->pParams->nVarsMax > 8 ) { p->pParams->fTruth = 0; printf( "Skipping computation of truth table for more than 8 inputs.\n" ); } else { p->nTruthWords = Cut_TruthWords( p->pParams->nVarsMax ); p->EntrySize += p->nTruthWords * sizeof(unsigned); } } // memory for cuts p->pMmCuts = Extra_MmFixedStart( p->EntrySize ); return p; } /**Function************************************************************* Synopsis [Stop the cut oracle.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_OracleStop( Cut_Oracle_t * p ) { Cut_Cut_t * pCut; int i; // if ( p->pParams->fVerbose ) { printf( "Cut computation statistics with oracle:\n" ); printf( "Current cuts = %8d. (Trivial = %d.)\n", p->nCuts-p->nCutsTriv, p->nCutsTriv ); PRT( "Total time ", p->timeTotal ); } Vec_PtrForEachEntry( p->vCutsNew, pCut, i ) if ( pCut != NULL ) { int k = 0; } if ( p->vCuts0 ) Vec_PtrFree( p->vCuts0 ); if ( p->vCuts1 ) Vec_PtrFree( p->vCuts1 ); if ( p->vCutsNew ) Vec_PtrFree( p->vCutsNew ); if ( p->vFanCounts ) Vec_IntFree( p->vFanCounts ); if ( p->vNodeCuts ) Vec_IntFree( p->vNodeCuts ); if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts ); if ( p->vCutPairs ) Vec_IntFree( p->vCutPairs ); Extra_MmFixedStop( p->pMmCuts, 0 ); free( p ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_OracleSetFanoutCounts( Cut_Oracle_t * p, Vec_Int_t * vFanCounts ) { p->vFanCounts = vFanCounts; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Cut_OracleReadDrop( Cut_Oracle_t * p ) { return p->pParams->fDrop; } /**Function************************************************************* Synopsis [Sets the trivial cut for the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_OracleNodeSetTriv( Cut_Oracle_t * p, int Node ) { assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL ); Vec_PtrWriteEntry( p->vCutsNew, Node, Cut_CutTriv(p, Node) ); } /**Function************************************************************* Synopsis [Allocates the cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p ) { Cut_Cut_t * pCut; // cut allocation pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts ); memset( pCut, 0, sizeof(Cut_Cut_t) ); pCut->nVarsMax = p->pParams->nVarsMax; pCut->fSimul = p->fSimul; p->nCuts++; return pCut; } /**Function************************************************************* Synopsis [Creates the trivial cut.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node ) { Cut_Cut_t * pCut; pCut = Cut_CutStart( p ); pCut->nLeaves = 1; pCut->pLeaves[0] = Node; if ( p->pParams->fTruth ) { unsigned * pTruth = Cut_CutReadTruth(pCut); int i; for ( i = 0; i < p->nTruthWords; i++ ) pTruth[i] = 0xAAAAAAAA; } p->nCutsTriv++; return pCut; } /**Function************************************************************* Synopsis [Merges two cuts.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { Cut_Cut_t * pCut; int Limit, i, k, c; // create the leaves of the new cut pCut = Cut_CutStart( p ); Limit = p->pParams->nVarsMax; for ( i = k = c = 0; c < Limit; c++ ) { if ( k == (int)pCut1->nLeaves ) { if ( i == (int)pCut0->nLeaves ) { pCut->nLeaves = c; return pCut; } pCut->pLeaves[c] = pCut0->pLeaves[i++]; continue; } if ( i == (int)pCut0->nLeaves ) { if ( k == (int)pCut1->nLeaves ) { pCut->nLeaves = c; return pCut; } pCut->pLeaves[c] = pCut1->pLeaves[k++]; continue; } if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] ) { pCut->pLeaves[c] = pCut0->pLeaves[i++]; continue; } if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] ) { pCut->pLeaves[c] = pCut1->pLeaves[k++]; continue; } pCut->pLeaves[c] = pCut0->pLeaves[i++]; k++; } assert( i == (int)pCut0->nLeaves && k == (int)pCut1->nLeaves ); pCut->nLeaves = c; return pCut; } /**Function************************************************************* Synopsis [Reconstruct the cuts of the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Cut_Cut_t * Cut_OracleComputeCuts( Cut_Oracle_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ) { Cut_Cut_t * pList = NULL, ** ppTail = &pList; Cut_Cut_t * pCut, * pCut0, * pCut1, * pList0, * pList1; int iCutStart, nCuts, i, Entry; int clk = clock(); // get the cuts of the children pList0 = Vec_PtrEntry( p->vCutsNew, Node0 ); pList1 = Vec_PtrEntry( p->vCutsNew, Node1 ); assert( pList0 && pList1 ); // get the complemented attribute of the cut p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul); // collect the cuts Vec_PtrClear( p->vCuts0 ); Cut_ListForEachCut( pList0, pCut ) Vec_PtrPush( p->vCuts0, pCut ); Vec_PtrClear( p->vCuts1 ); Cut_ListForEachCut( pList1, pCut ) Vec_PtrPush( p->vCuts1, pCut ); // get the first and last cuts of this node nCuts = Vec_IntEntry(p->vNodeCuts, Node); iCutStart = Vec_IntEntry(p->vNodeStarts, Node); // create trivial cut assert( Vec_IntEntry(p->vCutPairs, iCutStart) == 0 ); pCut = Cut_CutTriv( p, Node ); *ppTail = pCut; ppTail = &pCut->pNext; // create other cuts for ( i = 1; i < nCuts; i++ ) { Entry = Vec_IntEntry( p->vCutPairs, iCutStart + i ); pCut0 = Vec_PtrEntry( p->vCuts0, Entry & 0xFFFF ); pCut1 = Vec_PtrEntry( p->vCuts1, Entry >> 16 ); pCut = Cut_CutMerge( p, pCut0, pCut1 ); *ppTail = pCut; ppTail = &pCut->pNext; // compute the truth table if ( p->pParams->fTruth ) Cut_TruthCompute( pCut, pCut0, pCut1, fCompl0, fCompl1 ); } *ppTail = NULL; // write the new cut assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL ); Vec_PtrWriteEntry( p->vCutsNew, Node, pList ); p->timeTotal += clock() - clk; return pList; } /**Function************************************************************* Synopsis [Deallocates the cuts at the node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_OracleFreeCuts( Cut_Oracle_t * p, int Node ) { Cut_Cut_t * pList, * pCut, * pCut2; pList = Vec_PtrEntry( p->vCutsNew, Node ); if ( pList == NULL ) return; Cut_ListForEachCutSafe( pList, pCut, pCut2 ) Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); Vec_PtrWriteEntry( p->vCutsNew, Node, pList ); } /**Function************************************************************* Synopsis [Consider dropping cuts if they are useless by now.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Cut_OracleTryDroppingCuts( Cut_Oracle_t * p, int Node ) { int nFanouts; assert( p->vFanCounts ); nFanouts = Vec_IntEntry( p->vFanCounts, Node ); assert( nFanouts > 0 ); if ( --nFanouts == 0 ) Cut_OracleFreeCuts( p, Node ); Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// ////////////////////////////////////////////////////////////////////////