diff options
Diffstat (limited to 'src/opt/cut/cutOracle.c')
| -rw-r--r-- | src/opt/cut/cutOracle.c | 428 |
1 files changed, 428 insertions, 0 deletions
diff --git a/src/opt/cut/cutOracle.c b/src/opt/cut/cutOracle.c new file mode 100644 index 00000000..a254fd96 --- /dev/null +++ b/src/opt/cut/cutOracle.c @@ -0,0 +1,428 @@ +/**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 /// +//////////////////////////////////////////////////////////////////////// + + |