src/opt/cut/cutOracle.c File Reference

#include "cutInt.h"
Include dependency graph for cutOracle.c:

Go to the source code of this file.

Data Structures

struct  Cut_OracleStruct_t_

Functions

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)
Cut_Oracle_t * Cut_OracleStart (Cut_Man_t *pMan)
void Cut_OracleStop (Cut_Oracle_t *p)
void Cut_OracleSetFanoutCounts (Cut_Oracle_t *p, Vec_Int_t *vFanCounts)
int Cut_OracleReadDrop (Cut_Oracle_t *p)
void Cut_OracleNodeSetTriv (Cut_Oracle_t *p, int Node)
Cut_Cut_t * Cut_OracleComputeCuts (Cut_Oracle_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1)
void Cut_OracleFreeCuts (Cut_Oracle_t *p, int Node)
void Cut_OracleTryDroppingCuts (Cut_Oracle_t *p, int Node)

Function Documentation

Cut_Cut_t * Cut_CutMerge ( Cut_Oracle_t *  p,
Cut_Cut_t *  pCut0,
Cut_Cut_t *  pCut1 
) [static]

Function*************************************************************

Synopsis [Merges two cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 268 of file cutOracle.c.

00269 {
00270     Cut_Cut_t * pCut;
00271     int Limit, i, k, c;
00272     // create the leaves of the new cut
00273     pCut = Cut_CutStart( p );
00274     Limit = p->pParams->nVarsMax;
00275     for ( i = k = c = 0; c < Limit; c++ )
00276     {
00277         if ( k == (int)pCut1->nLeaves )
00278         {
00279             if ( i == (int)pCut0->nLeaves )
00280             {
00281                 pCut->nLeaves = c;
00282                 return pCut;
00283             }
00284             pCut->pLeaves[c] = pCut0->pLeaves[i++];
00285             continue;
00286         }
00287         if ( i == (int)pCut0->nLeaves )
00288         {
00289             if ( k == (int)pCut1->nLeaves )
00290             {
00291                 pCut->nLeaves = c;
00292                 return pCut;
00293             }
00294             pCut->pLeaves[c] = pCut1->pLeaves[k++];
00295             continue;
00296         }
00297         if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
00298         {
00299             pCut->pLeaves[c] = pCut0->pLeaves[i++];
00300             continue;
00301         }
00302         if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
00303         {
00304             pCut->pLeaves[c] = pCut1->pLeaves[k++];
00305             continue;
00306         }
00307         pCut->pLeaves[c] = pCut0->pLeaves[i++]; 
00308         k++;
00309     }
00310     assert( i == (int)pCut0->nLeaves && k == (int)pCut1->nLeaves );
00311     pCut->nLeaves = c;
00312     return pCut;
00313 }

Cut_Cut_t * Cut_CutStart ( Cut_Oracle_t *  p  )  [static]

Function*************************************************************

Synopsis [Allocates the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file cutOracle.c.

00218 {
00219     Cut_Cut_t * pCut;
00220     // cut allocation
00221     pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts );
00222     memset( pCut, 0, sizeof(Cut_Cut_t) );
00223     pCut->nVarsMax   = p->pParams->nVarsMax;
00224     pCut->fSimul     = p->fSimul;
00225     p->nCuts++;
00226     return pCut;
00227 }

Cut_Cut_t * Cut_CutTriv ( Cut_Oracle_t *  p,
int  Node 
) [static]

Function*************************************************************

Synopsis [Creates the trivial cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 240 of file cutOracle.c.

00241 {
00242     Cut_Cut_t * pCut;
00243     pCut = Cut_CutStart( p );
00244     pCut->nLeaves    = 1;
00245     pCut->pLeaves[0] = Node;
00246     if ( p->pParams->fTruth )
00247     {
00248         unsigned * pTruth = Cut_CutReadTruth(pCut);
00249         int i;
00250         for ( i = 0; i < p->nTruthWords; i++ )
00251             pTruth[i] = 0xAAAAAAAA;
00252     }
00253     p->nCutsTriv++;
00254     return pCut;
00255 }

Cut_Cut_t* Cut_OracleComputeCuts ( Cut_Oracle_t *  p,
int  Node,
int  Node0,
int  Node1,
int  fCompl0,
int  fCompl1 
)

Function*************************************************************

Synopsis [Reconstruct the cuts of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 326 of file cutOracle.c.

00327 {
00328     Cut_Cut_t * pList = NULL, ** ppTail = &pList;
00329     Cut_Cut_t * pCut, * pCut0, * pCut1, * pList0, * pList1;
00330     int iCutStart, nCuts, i, Entry;
00331     int clk = clock();
00332 
00333     // get the cuts of the children
00334     pList0 = Vec_PtrEntry( p->vCutsNew, Node0 );
00335     pList1 = Vec_PtrEntry( p->vCutsNew, Node1 );
00336     assert( pList0 && pList1 );
00337 
00338     // get the complemented attribute of the cut
00339     p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);
00340 
00341     // collect the cuts
00342     Vec_PtrClear( p->vCuts0 );
00343     Cut_ListForEachCut( pList0, pCut )
00344         Vec_PtrPush( p->vCuts0, pCut );
00345     Vec_PtrClear( p->vCuts1 );
00346     Cut_ListForEachCut( pList1, pCut )
00347         Vec_PtrPush( p->vCuts1, pCut );
00348 
00349     // get the first and last cuts of this node
00350     nCuts = Vec_IntEntry(p->vNodeCuts, Node);
00351     iCutStart = Vec_IntEntry(p->vNodeStarts, Node);
00352 
00353     // create trivial cut
00354     assert( Vec_IntEntry(p->vCutPairs, iCutStart) == 0 );
00355     pCut = Cut_CutTriv( p, Node );
00356     *ppTail = pCut;
00357     ppTail = &pCut->pNext;
00358     // create other cuts
00359     for ( i = 1; i < nCuts; i++ )
00360     {
00361         Entry = Vec_IntEntry( p->vCutPairs, iCutStart + i );
00362         pCut0 = Vec_PtrEntry( p->vCuts0, Entry & 0xFFFF );
00363         pCut1 = Vec_PtrEntry( p->vCuts1, Entry >> 16 );
00364         pCut  = Cut_CutMerge( p, pCut0, pCut1 );
00365         *ppTail = pCut;
00366         ppTail = &pCut->pNext;
00367         // compute the truth table
00368         if ( p->pParams->fTruth )
00369             Cut_TruthComputeOld( pCut, pCut0, pCut1, fCompl0, fCompl1 );
00370     }
00371     *ppTail = NULL;
00372 
00373     // write the new cut
00374     assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
00375     Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
00376 p->timeTotal += clock() - clk;
00377     return pList;
00378 }

void Cut_OracleFreeCuts ( Cut_Oracle_t *  p,
int  Node 
)

Function*************************************************************

Synopsis [Deallocates the cuts at the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 391 of file cutOracle.c.

00392 {
00393     Cut_Cut_t * pList, * pCut, * pCut2;
00394     pList = Vec_PtrEntry( p->vCutsNew, Node );
00395     if ( pList == NULL )
00396         return;
00397     Cut_ListForEachCutSafe( pList, pCut, pCut2 )
00398         Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut );
00399     Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
00400 }

void Cut_OracleNodeSetTriv ( Cut_Oracle_t *  p,
int  Node 
)

Function*************************************************************

Synopsis [Sets the trivial cut for the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 198 of file cutOracle.c.

00199 {
00200     assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
00201     Vec_PtrWriteEntry( p->vCutsNew, Node, Cut_CutTriv(p, Node) );
00202 }

int Cut_OracleReadDrop ( Cut_Oracle_t *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 182 of file cutOracle.c.

00183 {
00184     return p->pParams->fDrop;
00185 }

void Cut_OracleSetFanoutCounts ( Cut_Oracle_t *  p,
Vec_Int_t *  vFanCounts 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 166 of file cutOracle.c.

00167 {
00168     p->vFanCounts = vFanCounts;
00169 }

Cut_Oracle_t* Cut_OracleStart ( Cut_Man_t *  pMan  ) 

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Starts the cut oracle.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file cutOracle.c.

00071 {
00072     Cut_Oracle_t * p;
00073     int clk = clock();
00074 
00075     assert( pMan->pParams->nVarsMax >= 3 && pMan->pParams->nVarsMax <= CUT_SIZE_MAX );
00076     assert( pMan->pParams->fRecord );
00077 
00078     p = ALLOC( Cut_Oracle_t, 1 );
00079     memset( p, 0, sizeof(Cut_Oracle_t) );
00080 
00081     // set and correct parameters
00082     p->pParams     = pMan->pParams;
00083 
00084     // transfer the recording info
00085     p->vNodeCuts   = pMan->vNodeCuts;    pMan->vNodeCuts   = NULL;
00086     p->vNodeStarts = pMan->vNodeStarts;  pMan->vNodeStarts = NULL;
00087     p->vCutPairs   = pMan->vCutPairs;    pMan->vCutPairs   = NULL;
00088 
00089     // prepare storage for cuts
00090     p->vCutsNew = Vec_PtrAlloc( p->pParams->nIdsMax );
00091     Vec_PtrFill( p->vCutsNew, p->pParams->nIdsMax, NULL );
00092     p->vCuts0 = Vec_PtrAlloc( 100 );
00093     p->vCuts1 = Vec_PtrAlloc( 100 );
00094 
00095     // entry size
00096     p->EntrySize = sizeof(Cut_Cut_t) + p->pParams->nVarsMax * sizeof(int);
00097     if ( p->pParams->fTruth )
00098     {
00099         if ( p->pParams->nVarsMax > 8 )
00100         {
00101             p->pParams->fTruth = 0;
00102             printf( "Skipping computation of truth table for more than 8 inputs.\n" );
00103         }
00104         else
00105         {
00106             p->nTruthWords = Cut_TruthWords( p->pParams->nVarsMax );
00107             p->EntrySize += p->nTruthWords * sizeof(unsigned);
00108         }
00109     }
00110     // memory for cuts
00111     p->pMmCuts = Extra_MmFixedStart( p->EntrySize );
00112     return p;
00113 }

void Cut_OracleStop ( Cut_Oracle_t *  p  ) 

Function*************************************************************

Synopsis [Stop the cut oracle.]

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file cutOracle.c.

00126 {
00127     Cut_Cut_t * pCut;
00128     int i;
00129 
00130 //    if ( p->pParams->fVerbose )
00131     {
00132         printf( "Cut computation statistics with oracle:\n" );
00133         printf( "Current cuts      = %8d. (Trivial = %d.)\n", p->nCuts-p->nCutsTriv, p->nCutsTriv );
00134         PRT( "Total time ", p->timeTotal );
00135     }
00136 
00137     Vec_PtrForEachEntry( p->vCutsNew, pCut, i )
00138         if ( pCut != NULL )
00139         {
00140             int k = 0;
00141         }
00142     if ( p->vCuts0 )      Vec_PtrFree( p->vCuts0 );
00143     if ( p->vCuts1 )      Vec_PtrFree( p->vCuts1 );
00144     if ( p->vCutsNew )    Vec_PtrFree( p->vCutsNew );
00145     if ( p->vFanCounts )  Vec_IntFree( p->vFanCounts );
00146 
00147     if ( p->vNodeCuts )   Vec_IntFree( p->vNodeCuts );
00148     if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts );
00149     if ( p->vCutPairs )   Vec_IntFree( p->vCutPairs );
00150 
00151     Extra_MmFixedStop( p->pMmCuts );
00152     free( p ); 
00153 }

void Cut_OracleTryDroppingCuts ( Cut_Oracle_t *  p,
int  Node 
)

Function*************************************************************

Synopsis [Consider dropping cuts if they are useless by now.]

Description []

SideEffects []

SeeAlso []

Definition at line 413 of file cutOracle.c.

00414 {
00415     int nFanouts;
00416     assert( p->vFanCounts );
00417     nFanouts = Vec_IntEntry( p->vFanCounts, Node );
00418     assert( nFanouts > 0 );
00419     if ( --nFanouts == 0 )
00420         Cut_OracleFreeCuts( p, Node );
00421     Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts );
00422 }

Generated on Tue Jan 5 12:19:24 2010 for abc70930 by  doxygen 1.6.1