diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2008-01-30 20:01:00 -0800 |
commit | 0c6505a26a537dc911b6566f82d759521e527c08 (patch) | |
tree | f2687995efd4943fe3b1307fce7ef5942d0a57b3 /src/opt/cut | |
parent | 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 (diff) | |
download | abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.gz abc-0c6505a26a537dc911b6566f82d759521e527c08.tar.bz2 abc-0c6505a26a537dc911b6566f82d759521e527c08.zip |
Version abc80130_2
Diffstat (limited to 'src/opt/cut')
-rw-r--r-- | src/opt/cut/abcCut.c | 492 | ||||
-rw-r--r-- | src/opt/cut/cut.h | 124 | ||||
-rw-r--r-- | src/opt/cut/cutApi.c | 197 | ||||
-rw-r--r-- | src/opt/cut/cutCut.c | 359 | ||||
-rw-r--r-- | src/opt/cut/cutExpand.c | 184 | ||||
-rw-r--r-- | src/opt/cut/cutInt.h | 79 | ||||
-rw-r--r-- | src/opt/cut/cutList.h | 120 | ||||
-rw-r--r-- | src/opt/cut/cutMan.c | 243 | ||||
-rw-r--r-- | src/opt/cut/cutMerge.c | 11 | ||||
-rw-r--r-- | src/opt/cut/cutNode.c | 1072 | ||||
-rw-r--r-- | src/opt/cut/cutOracle.c | 428 | ||||
-rw-r--r-- | src/opt/cut/cutPre22.c | 988 | ||||
-rw-r--r-- | src/opt/cut/cutSeq.c | 184 | ||||
-rw-r--r-- | src/opt/cut/cutTable.c | 253 | ||||
-rw-r--r-- | src/opt/cut/cutTruth.c | 314 | ||||
-rw-r--r-- | src/opt/cut/module.make | 7 |
16 files changed, 4125 insertions, 930 deletions
diff --git a/src/opt/cut/abcCut.c b/src/opt/cut/abcCut.c new file mode 100644 index 00000000..9bbd5790 --- /dev/null +++ b/src/opt/cut/abcCut.c @@ -0,0 +1,492 @@ +/**CFile**************************************************************** + + FileName [abcCut.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Interface to cut computation.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: abcCut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "cut.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ); +static void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ); + + +extern int nTotal, nGood, nEqual; + +// temporary +//Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ) { return NULL; } +Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ) +{ + Vec_Int_t * vAttrs = Vec_IntStart( Abc_NtkObjNumMax(pNtk) + 1 ); + int i; + Abc_Obj_t * pObj; + +// Abc_NtkForEachCi( pNtk, pObj, i ) +// Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); + + Abc_NtkForEachObj( pNtk, pObj, i ) + { +// if ( Abc_ObjIsNode(pObj) && (rand() % 4 == 0) ) + if ( Abc_ObjIsNode(pObj) && Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj) && (rand() % 3 == 0) ) + Vec_IntWriteEntry( vAttrs, pObj->Id, 1 ); + } + return vAttrs; +} + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Man_t * Abc_NtkCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) +{ + ProgressBar * pProgress; + Cut_Man_t * p; + Abc_Obj_t * pObj, * pNode; + Vec_Ptr_t * vNodes; + Vec_Int_t * vChoices; + int i; + int clk = clock(); + + extern void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk ); + extern void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk ); + + nTotal = nGood = nEqual = 0; + + assert( Abc_NtkIsStrash(pNtk) ); + // start the manager + pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); + p = Cut_ManStart( pParams ); + // compute node attributes if local or global cuts are requested + if ( pParams->fGlobal || pParams->fLocal ) + { + extern Vec_Int_t * Abc_NtkGetNodeAttributes( Abc_Ntk_t * pNtk ); + Cut_ManSetNodeAttrs( p, Abc_NtkGetNodeAttributes(pNtk) ); + } + // prepare for cut dropping + if ( pParams->fDrop ) + Cut_ManSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); + // set cuts for PIs + Abc_NtkForEachCi( pNtk, pObj, i ) + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_NodeSetTriv( p, pObj->Id ); + // compute cuts for internal nodes + vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs + vChoices = Vec_IntAlloc( 100 ); + pProgress = Extra_ProgressBarStart( stdout, Vec_PtrSize(vNodes) ); + Vec_PtrForEachEntry( vNodes, pObj, i ) + { + // when we reached a CO, it is time to deallocate the cuts + if ( Abc_ObjIsCo(pObj) ) + { + if ( pParams->fDrop ) + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + continue; + } + // skip constant node, it has no cuts +// if ( Abc_NodeIsConst(pObj) ) +// continue; + Extra_ProgressBarUpdate( pProgress, i, NULL ); + // compute the cuts to the internal node + Abc_NodeGetCuts( p, pObj, pParams->fDag, pParams->fTree ); + // consider dropping the fanins cuts + if ( pParams->fDrop ) + { + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + Cut_NodeTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); + } + // add cuts due to choices + if ( Abc_AigNodeIsChoice(pObj) ) + { + Vec_IntClear( vChoices ); + for ( pNode = pObj; pNode; pNode = pNode->pData ) + Vec_IntPush( vChoices, pNode->Id ); + Cut_NodeUnionCuts( p, vChoices ); + } + } + Extra_ProgressBarStop( pProgress ); + Vec_PtrFree( vNodes ); + Vec_IntFree( vChoices ); +PRT( "Total", clock() - clk ); +//Abc_NtkPrintCuts( p, pNtk, 0 ); +// Cut_ManPrintStatsToFile( p, pNtk->pSpec, clock() - clk ); + + // temporary printout of stats + if ( nTotal ) + printf( "Total cuts = %d. Good cuts = %d. Ratio = %5.2f\n", nTotal, nGood, ((double)nGood)/nTotal ); + return p; +} + +/**Function************************************************************* + + Synopsis [Cut computation using the oracle.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkCutsOracle( Abc_Ntk_t * pNtk, Cut_Oracle_t * p ) +{ + Abc_Obj_t * pObj; + Vec_Ptr_t * vNodes; + int i, clk = clock(); + int fDrop = Cut_OracleReadDrop(p); + + assert( Abc_NtkIsStrash(pNtk) ); + + // prepare cut droppping + if ( fDrop ) + Cut_OracleSetFanoutCounts( p, Abc_NtkFanoutCounts(pNtk) ); + + // set cuts for PIs + Abc_NtkForEachCi( pNtk, pObj, i ) + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_OracleNodeSetTriv( p, pObj->Id ); + + // compute cuts for internal nodes + vNodes = Abc_AigDfs( pNtk, 0, 1 ); // collects POs + Vec_PtrForEachEntry( vNodes, pObj, i ) + { + // when we reached a CO, it is time to deallocate the cuts + if ( Abc_ObjIsCo(pObj) ) + { + if ( fDrop ) + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + continue; + } + // skip constant node, it has no cuts +// if ( Abc_NodeIsConst(pObj) ) +// continue; + // compute the cuts to the internal node + Cut_OracleComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); + // consider dropping the fanins cuts + if ( fDrop ) + { + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId0(pObj) ); + Cut_OracleTryDroppingCuts( p, Abc_ObjFaninId1(pObj) ); + } + } + Vec_PtrFree( vNodes ); +//PRT( "Total", clock() - clk ); +//Abc_NtkPrintCuts_( p, pNtk, 0 ); +} + + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Man_t * Abc_NtkSeqCuts( Abc_Ntk_t * pNtk, Cut_Params_t * pParams ) +{ +/* + Cut_Man_t * p; + Abc_Obj_t * pObj, * pNode; + int i, nIters, fStatus; + Vec_Int_t * vChoices; + int clk = clock(); + + assert( Abc_NtkIsSeq(pNtk) ); + assert( pParams->fSeq ); +// assert( Abc_NtkIsDfsOrdered(pNtk) ); + + // start the manager + pParams->nIdsMax = Abc_NtkObjNumMax( pNtk ); + pParams->nCutSet = Abc_NtkCutSetNodeNum( pNtk ); + p = Cut_ManStart( pParams ); + + // set cuts for the constant node and the PIs + pObj = Abc_AigConst1(pNtk); + if ( Abc_ObjFanoutNum(pObj) > 0 ) + Cut_NodeSetTriv( p, pObj->Id ); + Abc_NtkForEachPi( pNtk, pObj, i ) + { +//printf( "Setting trivial cut %d.\n", pObj->Id ); + Cut_NodeSetTriv( p, pObj->Id ); + } + // label the cutset nodes and set their number in the array + // assign the elementary cuts to the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + { + assert( pObj->fMarkC == 0 ); + pObj->fMarkC = 1; + pObj->pCopy = (Abc_Obj_t *)i; + Cut_NodeSetTriv( p, pObj->Id ); +//printf( "Setting trivial cut %d.\n", pObj->Id ); + } + + // process the nodes + vChoices = Vec_IntAlloc( 100 ); + for ( nIters = 0; nIters < 10; nIters++ ) + { +//printf( "ITERATION %d:\n", nIters ); + // compute the cuts for the internal nodes + Abc_AigForEachAnd( pNtk, pObj, i ) + { + Abc_NodeGetCutsSeq( p, pObj, nIters==0 ); + // add cuts due to choices + if ( Abc_AigNodeIsChoice(pObj) ) + { + Vec_IntClear( vChoices ); + for ( pNode = pObj; pNode; pNode = pNode->pData ) + Vec_IntPush( vChoices, pNode->Id ); + Cut_NodeUnionCutsSeq( p, vChoices, (pObj->fMarkC ? (int)pObj->pCopy : -1), nIters==0 ); + } + } + // merge the new cuts with the old cuts + Abc_NtkForEachPi( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + Abc_AigForEachAnd( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + // for the cutset, transfer temp cuts to new cuts + fStatus = 0; + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + fStatus |= Cut_NodeTempTransferToNew( p, pObj->Id, i ); + if ( fStatus == 0 ) + break; + } + Vec_IntFree( vChoices ); + + // if the status is not finished, transfer new to old for the cutset + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + Cut_NodeNewMergeWithOld( p, pObj->Id ); + + // transfer the old cuts to the new positions + Abc_NtkForEachObj( pNtk, pObj, i ) + Cut_NodeOldTransferToNew( p, pObj->Id ); + + // unlabel the cutset nodes + Abc_SeqForEachCutsetNode( pNtk, pObj, i ) + pObj->fMarkC = 0; +if ( pParams->fVerbose ) +{ +PRT( "Total", clock() - clk ); +printf( "Converged after %d iterations.\n", nIters ); +} +//Abc_NtkPrintCuts( p, pNtk, 1 ); + return p; +*/ +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void * Abc_NodeGetCutsRecursive( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) +{ + void * pList; + if ( pList = Abc_NodeReadCuts( p, pObj ) ) + return pList; + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin0(pObj), fDag, fTree ); + Abc_NodeGetCutsRecursive( p, Abc_ObjFanin1(pObj), fDag, fTree ); + return Abc_NodeGetCuts( p, pObj, fDag, fTree ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void * Abc_NodeGetCuts( void * p, Abc_Obj_t * pObj, int fDag, int fTree ) +{ + Abc_Obj_t * pFanin; + int fDagNode, fTriv, TreeCode = 0; +// assert( Abc_NtkIsStrash(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); + + + // check if the node is a DAG node + fDagNode = (Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsMuxControlType(pObj)); + // increment the counter of DAG nodes + if ( fDagNode ) Cut_ManIncrementDagNodes( p ); + // add the trivial cut if the node is a DAG node, or if we compute all cuts + fTriv = fDagNode || !fDag; + // check if fanins are DAG nodes + if ( fTree ) + { + pFanin = Abc_ObjFanin0(pObj); + TreeCode |= (Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)); + pFanin = Abc_ObjFanin1(pObj); + TreeCode |= ((Abc_ObjFanoutNum(pFanin) > 1 && !Abc_NodeIsMuxControlType(pFanin)) << 1); + } + + + // changes due to the global/local cut computation + { + Cut_Params_t * pParams = Cut_ManReadParams(p); + if ( pParams->fLocal ) + { + Vec_Int_t * vNodeAttrs = Cut_ManReadNodeAttrs(p); + fDagNode = Vec_IntEntry( vNodeAttrs, pObj->Id ); + if ( fDagNode ) Cut_ManIncrementDagNodes( p ); +// fTriv = fDagNode || !pParams->fGlobal; + fTriv = !Vec_IntEntry( vNodeAttrs, pObj->Id ); + TreeCode = 0; + pFanin = Abc_ObjFanin0(pObj); + TreeCode |= Vec_IntEntry( vNodeAttrs, pFanin->Id ); + pFanin = Abc_ObjFanin1(pObj); + TreeCode |= (Vec_IntEntry( vNodeAttrs, pFanin->Id ) << 1); + } + } + return Cut_NodeComputeCuts( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), fTriv, TreeCode ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NodeGetCutsSeq( void * p, Abc_Obj_t * pObj, int fTriv ) +{ + int CutSetNum; + assert( Abc_NtkIsSeq(pObj->pNtk) ); + assert( Abc_ObjFaninNum(pObj) == 2 ); + fTriv = pObj->fMarkC ? 0 : fTriv; + CutSetNum = pObj->fMarkC ? (int)pObj->pCopy : -1; + Cut_NodeComputeCutsSeq( p, pObj->Id, Abc_ObjFaninId0(pObj), Abc_ObjFaninId1(pObj), + Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj), Seq_ObjFaninL0(pObj), Seq_ObjFaninL1(pObj), fTriv, CutSetNum ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void * Abc_NodeReadCuts( void * p, Abc_Obj_t * pObj ) +{ + return Cut_NodeReadCutsNew( p, pObj->Id ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NodeFreeCuts( void * p, Abc_Obj_t * pObj ) +{ + Cut_NodeFreeCuts( p, pObj->Id ); +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + int i; + printf( "Cuts of the network:\n" ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkPrintCuts_( void * p, Abc_Ntk_t * pNtk, int fSeq ) +{ + Cut_Man_t * pMan = p; + Cut_Cut_t * pList; + Abc_Obj_t * pObj; + pObj = Abc_NtkObj( pNtk, 2 * Abc_NtkObjNum(pNtk) / 3 ); + pList = Abc_NodeReadCuts( p, pObj ); + printf( "Node %s:\n", Abc_ObjName(pObj) ); + Cut_CutPrintList( pList, fSeq ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cut.h b/src/opt/cut/cut.h index 6719ed4d..dee05dfc 100644 --- a/src/opt/cut/cut.h +++ b/src/opt/cut/cut.h @@ -21,6 +21,10 @@ #ifndef __CUT_H__ #define __CUT_H__ +#ifdef __cplusplus +extern "C" { +#endif + //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -29,81 +33,133 @@ /// PARAMETERS /// //////////////////////////////////////////////////////////////////////// +#define CUT_SIZE_MIN 3 // the min K of the K-feasible cut computation +#define CUT_SIZE_MAX 12 // the max K of the K-feasible cut computation + +#define CUT_SHIFT 8 // the number of bits for storing latch number in the cut leaves +#define CUT_MASK 0xFF // the mask to get the stored latch number + //////////////////////////////////////////////////////////////////////// /// BASIC TYPES /// //////////////////////////////////////////////////////////////////////// typedef struct Cut_ManStruct_t_ Cut_Man_t; +typedef struct Cut_OracleStruct_t_ Cut_Oracle_t; typedef struct Cut_CutStruct_t_ Cut_Cut_t; typedef struct Cut_ParamsStruct_t_ Cut_Params_t; struct Cut_ParamsStruct_t_ { - int nVarsMax; // the max cut size ("k" of the k-feasible cuts) - int nKeepMax; // the max number of cuts kept at a node - int nIdsMax; // the max number of IDs of cut objects - int fTruth; // compute truth tables - int fHash; // hash cuts to detect unique - int fFilter; // filter dominated cuts - int fSeq; // compute sequential cuts - int fDrop; // drop cuts on the fly - int fVerbose; // the verbosiness flag + int nVarsMax; // the max cut size ("k" of the k-feasible cuts) + int nKeepMax; // the max number of cuts kept at a node + int nIdsMax; // the max number of IDs of cut objects + int nBitShift; // the number of bits used for the latch counter of an edge + int nCutSet; // the number of nodes in the cut set + int fTruth; // compute truth tables + int fFilter; // filter dominated cuts + int fSeq; // compute sequential cuts + int fDrop; // drop cuts on the fly + int fDag; // compute only DAG cuts + int fTree; // compute only tree cuts + int fGlobal; // compute only global cuts + int fLocal; // compute only local cuts + int fRecord; // record the cut computation flow + int fFancy; // perform fancy computations + int fMap; // computes delay of FPGA mapping with cuts + int fVerbose; // the verbosiness flag }; struct Cut_CutStruct_t_ { - unsigned uTruth : 16; // truth table for 4-input cuts - unsigned uPhase : 7; // the phase when mapping into a canonical form + unsigned Num0 : 11; // temporary number + unsigned Num1 : 11; // temporary number unsigned fSimul : 1; // the value of cut's output at 000.. pattern unsigned fCompl : 1; // the cut is complemented - unsigned fSeq : 1; // the cut is sequential - unsigned nVarsMax : 3; // the max number of vars [4-6] - unsigned nLeaves : 3; // the number of leaves [4-6] + unsigned nVarsMax : 4; // the max number of vars [4-6] + unsigned nLeaves : 4; // the number of leaves [4-6] + unsigned uSign; // the signature + unsigned uCanon0; // the canonical form + unsigned uCanon1; // the canonical form Cut_Cut_t * pNext; // the next cut in the list - void * pData; // the user data int pLeaves[0]; // the array of leaves }; -static inline unsigned * Cut_CutReadTruth( Cut_Cut_t * p ) { if ( p->nVarsMax == 4 ) return (unsigned *)p; return (unsigned *)(p->pLeaves + p->nVarsMax + p->fSeq); } -static inline unsigned Cut_CutReadPhase( Cut_Cut_t * p ) { return p->uPhase; } static inline int Cut_CutReadLeaveNum( Cut_Cut_t * p ) { return p->nLeaves; } static inline int * Cut_CutReadLeaves( Cut_Cut_t * p ) { return p->pLeaves; } -static inline void * Cut_CutReadData( Cut_Cut_t * p ) { return p->pData; } - -static inline void Cut_CutWriteData( Cut_Cut_t * p, void * pData ) { p->pData = pData; } +static inline unsigned * Cut_CutReadTruth( Cut_Cut_t * p ) { return (unsigned *)(p->pLeaves + p->nVarsMax); } static inline void Cut_CutWriteTruth( Cut_Cut_t * p, unsigned * puTruth ) { - if ( p->nVarsMax == 4 ) { p->uTruth = *puTruth; return; } - p->pLeaves[p->nVarsMax + p->fSeq] = (int)puTruth[0]; - if ( p->nVarsMax == 6 ) p->pLeaves[p->nVarsMax + p->fSeq + 1] = (int)puTruth[1]; + int i; + for ( i = (p->nVarsMax <= 5) ? 0 : ((1 << (p->nVarsMax - 5)) - 1); i >= 0; i-- ) + p->pLeaves[p->nVarsMax + i] = (int)puTruth[i]; } //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/*=== cutApi.c ==========================================================*/ +extern Cut_Cut_t * Cut_NodeReadCutsNew( Cut_Man_t * p, int Node ); +extern Cut_Cut_t * Cut_NodeReadCutsOld( Cut_Man_t * p, int Node ); +extern Cut_Cut_t * Cut_NodeReadCutsTemp( Cut_Man_t * p, int Node ); +extern void Cut_NodeWriteCutsNew( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); +extern void Cut_NodeWriteCutsOld( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); +extern void Cut_NodeWriteCutsTemp( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); +extern void Cut_NodeSetTriv( Cut_Man_t * p, int Node ); +extern void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ); +extern void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ); +/*=== cutCut.c ==========================================================*/ +extern void Cut_CutPrint( Cut_Cut_t * pCut, int fSeq ); +extern void Cut_CutPrintList( Cut_Cut_t * pList, int fSeq ); +extern int Cut_CutCountList( Cut_Cut_t * pList ); /*=== cutMan.c ==========================================================*/ extern Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ); extern void Cut_ManStop( Cut_Man_t * p ); extern void Cut_ManPrintStats( Cut_Man_t * p ); +extern void Cut_ManPrintStatsToFile( Cut_Man_t * p, char * pFileName, int TimeTotal ); extern void Cut_ManSetFanoutCounts( Cut_Man_t * p, Vec_Int_t * vFanCounts ); +extern void Cut_ManSetNodeAttrs( Cut_Man_t * p, Vec_Int_t * vFanCounts ); +extern int Cut_ManReadVarsMax( Cut_Man_t * p ); +extern Cut_Params_t * Cut_ManReadParams( Cut_Man_t * p ); +extern Vec_Int_t * Cut_ManReadNodeAttrs( Cut_Man_t * p ); +extern void Cut_ManIncrementDagNodes( Cut_Man_t * p ); /*=== cutNode.c ==========================================================*/ -extern void Cut_NodeSetTriv( Cut_Man_t * p, int Node ); -extern Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ); +extern Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode ); extern Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ); -extern Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ); -extern void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ); -extern void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ); -extern void Cut_NodeSetComputedAsNew( Cut_Man_t * p, int Node ); -extern void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ); -extern void Cut_CutPrint( Cut_Cut_t * pCut ); +extern Cut_Cut_t * Cut_NodeUnionCutsSeq( Cut_Man_t * p, Vec_Int_t * vNodes, int CutSetNum, int fFirst ); +extern int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node ); +/*=== cutSeq.c ==========================================================*/ +extern void Cut_NodeComputeCutsSeq( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int nLat0, int nLat1, int fTriv, int CutSetNum ); +extern void Cut_NodeNewMergeWithOld( Cut_Man_t * p, int Node ); +extern int Cut_NodeTempTransferToNew( Cut_Man_t * p, int Node, int CutSetNum ); +extern void Cut_NodeOldTransferToNew( Cut_Man_t * p, int Node ); +/*=== cutOracle.c ==========================================================*/ +extern Cut_Oracle_t * Cut_OracleStart( Cut_Man_t * pMan ); +extern void Cut_OracleStop( Cut_Oracle_t * p ); +extern void Cut_OracleSetFanoutCounts( Cut_Oracle_t * p, Vec_Int_t * vFanCounts ); +extern int Cut_OracleReadDrop( Cut_Oracle_t * p ); +extern void Cut_OracleNodeSetTriv( Cut_Oracle_t * p, int Node ); +extern Cut_Cut_t * Cut_OracleComputeCuts( Cut_Oracle_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ); +extern void Cut_OracleTryDroppingCuts( Cut_Oracle_t * p, int Node ); +/*=== cutTruth.c ==========================================================*/ +extern void Cut_TruthNCanonicize( Cut_Cut_t * pCut ); +/*=== cutPre22.c ==========================================================*/ +extern void Cut_CellPrecompute(); +extern void Cut_CellLoad(); +extern int Cut_CellIsRunning(); +extern void Cut_CellDumpToFile(); +extern int Cut_CellTruthLookup( unsigned * pTruth, int nVars ); + +#ifdef __cplusplus +} +#endif + +#endif //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif - diff --git a/src/opt/cut/cutApi.c b/src/opt/cut/cutApi.c new file mode 100644 index 00000000..980c6b12 --- /dev/null +++ b/src/opt/cut/cutApi.c @@ -0,0 +1,197 @@ +/**CFile**************************************************************** + + FileName [cutNode.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [K-feasible cut computation package.] + + Synopsis [Procedures to compute cuts for a node.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_NodeReadCutsNew( Cut_Man_t * p, int Node ) +{ + if ( Node >= p->vCutsNew->nSize ) + return NULL; + return Vec_PtrEntry( p->vCutsNew, Node ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_NodeReadCutsOld( Cut_Man_t * p, int Node ) +{ + assert( Node < p->vCutsOld->nSize ); + return Vec_PtrEntry( p->vCutsOld, Node ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_NodeReadCutsTemp( Cut_Man_t * p, int Node ) +{ + assert( Node < p->vCutsTemp->nSize ); + return Vec_PtrEntry( p->vCutsTemp, Node ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeWriteCutsNew( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +{ + Vec_PtrWriteEntry( p->vCutsNew, Node, pList ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeWriteCutsOld( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +{ + Vec_PtrWriteEntry( p->vCutsOld, Node, pList ); +} + +/**Function************************************************************* + + Synopsis [Returns the pointer to the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeWriteCutsTemp( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +{ + Vec_PtrWriteEntry( p->vCutsTemp, Node, pList ); +} + +/**Function************************************************************* + + Synopsis [Sets the trivial cut for the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) +{ + assert( Cut_NodeReadCutsNew(p, Node) == NULL ); + Cut_NodeWriteCutsNew( p, Node, Cut_CutCreateTriv(p, Node) ); +} + +/**Function************************************************************* + + Synopsis [Consider dropping cuts if they are useless by now.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ) +{ + int nFanouts; + assert( p->vFanCounts ); + nFanouts = Vec_IntEntry( p->vFanCounts, Node ); + assert( nFanouts > 0 ); + if ( --nFanouts == 0 ) + Cut_NodeFreeCuts( p, Node ); + Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts ); +} + +/**Function************************************************************* + + Synopsis [Deallocates the cuts at the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pList, * pCut, * pCut2; + pList = Cut_NodeReadCutsNew( p, Node ); + if ( pList == NULL ) + return; + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + Cut_NodeWriteCutsNew( p, Node, NULL ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutCut.c b/src/opt/cut/cutCut.c new file mode 100644 index 00000000..94147278 --- /dev/null +++ b/src/opt/cut/cutCut.c @@ -0,0 +1,359 @@ +/**CFile**************************************************************** + + FileName [cutNode.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [K-feasible cut computation package.] + + Synopsis [Procedures to compute cuts for a node.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutAlloc( Cut_Man_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; + // statistics + p->nCutsAlloc++; + p->nCutsCur++; + if ( p->nCutsPeak < p->nCutsAlloc - p->nCutsDealloc ) + p->nCutsPeak = p->nCutsAlloc - p->nCutsDealloc; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Recybles the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ) +{ + p->nCutsDealloc++; + p->nCutsCur--; + if ( pCut->nLeaves == 1 ) + p->nCutsTriv--; + Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); +} + +/**Function************************************************************* + + Synopsis [Compares two cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_CutCompare( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 ) +{ + int i; + if ( pCut1->nLeaves < pCut2->nLeaves ) + return -1; + if ( pCut1->nLeaves > pCut2->nLeaves ) + return 1; + for ( i = 0; i < (int)pCut1->nLeaves; i++ ) + { + if ( pCut1->pLeaves[i] < pCut2->pLeaves[i] ) + return -1; + if ( pCut1->pLeaves[i] > pCut2->pLeaves[i] ) + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Duplicates the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutDupList( Cut_Man_t * p, Cut_Cut_t * pList ) +{ + Cut_Cut_t * pHead = NULL, ** ppTail = &pHead; + Cut_Cut_t * pTemp, * pCopy; + if ( pList == NULL ) + return NULL; + Cut_ListForEachCut( pList, pTemp ) + { + pCopy = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts ); + memcpy( pCopy, pTemp, p->EntrySize ); + *ppTail = pCopy; + ppTail = &pCopy->pNext; + } + *ppTail = NULL; + return pHead; +} + +/**Function************************************************************* + + Synopsis [Recycles the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutRecycleList( Cut_Man_t * p, Cut_Cut_t * pList ) +{ + Cut_Cut_t * pCut, * pCut2; + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); +} + +/**Function************************************************************* + + Synopsis [Counts the number of cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_CutCountList( Cut_Cut_t * pList ) +{ + int Counter = 0; + Cut_ListForEachCut( pList, pList ) + Counter++; + return Counter; +} + +/**Function************************************************************* + + Synopsis [Merges two NULL-terminated linked lists.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutMergeLists( Cut_Cut_t * pList1, Cut_Cut_t * pList2 ) +{ + Cut_Cut_t * pList = NULL, ** ppTail = &pList; + Cut_Cut_t * pCut; + while ( pList1 && pList2 ) + { + if ( Cut_CutCompare(pList1, pList2) < 0 ) + { + pCut = pList1; + pList1 = pList1->pNext; + } + else + { + pCut = pList2; + pList2 = pList2->pNext; + } + *ppTail = pCut; + ppTail = &pCut->pNext; + } + *ppTail = pList1? pList1: pList2; + return pList; +} + +/**Function************************************************************* + + Synopsis [Sets the number of the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutNumberList( Cut_Cut_t * pList ) +{ + Cut_Cut_t * pCut; + int i = 0; + Cut_ListForEachCut( pList, pCut ) + pCut->Num0 = i++; +} + +/**Function************************************************************* + + Synopsis [Creates the trivial cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pCut; + if ( p->pParams->fSeq ) + Node <<= CUT_SHIFT; + pCut = Cut_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->pLeaves[0] = Node; + pCut->uSign = Cut_NodeSign( Node ); + if ( p->pParams->fTruth ) + { +/* + if ( pCut->nVarsMax == 4 ) + Cut_CutWriteTruth( pCut, p->uTruthVars[0] ); + else + Extra_BitCopy( pCut->nLeaves, p->uTruths[0], (uint8*)Cut_CutReadTruth(pCut) ); +*/ + unsigned * pTruth = Cut_CutReadTruth(pCut); + int i; + for ( i = 0; i < p->nTruthWords; i++ ) + pTruth[i] = 0xAAAAAAAA; + } + p->nCutsTriv++; + return pCut; +} + + +/**Function************************************************************* + + Synopsis [Print the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutPrint( Cut_Cut_t * pCut, int fSeq ) +{ + int i; + assert( pCut->nLeaves > 0 ); + printf( "%d : {", pCut->nLeaves ); + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + { + if ( fSeq ) + { + printf( " %d", pCut->pLeaves[i] >> CUT_SHIFT ); + if ( pCut->pLeaves[i] & CUT_MASK ) + printf( "(%d)", pCut->pLeaves[i] & CUT_MASK ); + } + else + printf( " %d", pCut->pLeaves[i] ); + } + printf( " }" ); +// printf( "\nSign = " ); +// Extra_PrintBinary( stdout, &pCut->uSign, 32 ); +} + +/**Function************************************************************* + + Synopsis [Print the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutPrintList( Cut_Cut_t * pList, int fSeq ) +{ + Cut_Cut_t * pCut; + for ( pCut = pList; pCut; pCut = pCut->pNext ) + Cut_CutPrint( pCut, fSeq ), printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Consider dropping cuts if they are useless by now.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +{ + printf( "\n" ); + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut0->nLeaves, + pCut0->nLeaves > 0 ? pCut0->pLeaves[0] : -1, + pCut0->nLeaves > 1 ? pCut0->pLeaves[1] : -1, + pCut0->nLeaves > 2 ? pCut0->pLeaves[2] : -1, + pCut0->nLeaves > 3 ? pCut0->pLeaves[3] : -1, + pCut0->nLeaves > 4 ? pCut0->pLeaves[4] : -1 + ); + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut1->nLeaves, + pCut1->nLeaves > 0 ? pCut1->pLeaves[0] : -1, + pCut1->nLeaves > 1 ? pCut1->pLeaves[1] : -1, + pCut1->nLeaves > 2 ? pCut1->pLeaves[2] : -1, + pCut1->nLeaves > 3 ? pCut1->pLeaves[3] : -1, + pCut1->nLeaves > 4 ? pCut1->pLeaves[4] : -1 + ); + if ( pCut == NULL ) + printf( "Cannot merge\n" ); + else + printf( "%d : %5d %5d %5d %5d %5d\n", + pCut->nLeaves, + pCut->nLeaves > 0 ? pCut->pLeaves[0] : -1, + pCut->nLeaves > 1 ? pCut->pLeaves[1] : -1, + pCut->nLeaves > 2 ? pCut->pLeaves[2] : -1, + pCut->nLeaves > 3 ? pCut->pLeaves[3] : -1, + pCut->nLeaves > 4 ? pCut->pLeaves[4] : -1 + ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutExpand.c b/src/opt/cut/cutExpand.c new file mode 100644 index 00000000..d389ef7a --- /dev/null +++ b/src/opt/cut/cutExpand.c @@ -0,0 +1,184 @@ +/**CFile**************************************************************** + + FileName [cutExpand.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [K-feasible cut computation package.] + + Synopsis [Computes the truth table of the cut after expansion.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutExpand.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define CUT_CELL_MVAR 9 + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline unsigned Cut_TruthPhase( Cut_Cut_t * pCut, Cut_Cut_t * pCut1 ) +{ + unsigned uPhase = 0; + int i, k; + for ( i = k = 0; i < (int)pCut->nLeaves; i++ ) + { + if ( k == (int)pCut1->nLeaves ) + break; + if ( pCut->pLeaves[i] < pCut1->pLeaves[k] ) + continue; + assert( pCut->pLeaves[i] == pCut1->pLeaves[k] ); + uPhase |= (1 << i); + k++; + } + return uPhase; +} + +/**Function************************************************************* + + Synopsis [Computes the truth table of the composition of cuts.] + + Description [Inputs are: + - a factor cut (truth table is stored inside) + - a node in the factor cut + - a tree cut to be substituted (truth table is stored inside) + - the resulting cut (truth table will be filled in). + Note that all cuts, including the resulting one, should be already + computed and the nodes should be stored in the ascending order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_TruthCompose( Cut_Cut_t * pCutF, int Node, Cut_Cut_t * pCutT, Cut_Cut_t * pCutRes ) +{ + static unsigned uCof0[1<<(CUT_CELL_MVAR-5)]; + static unsigned uCof1[1<<(CUT_CELL_MVAR-5)]; + static unsigned uTemp[1<<(CUT_CELL_MVAR-5)]; + unsigned * pIn, * pOut, * pTemp; + unsigned uPhase; + int NodeIndex, i, k; + + // sanity checks + assert( pCutF->nVarsMax == pCutT->nVarsMax ); + assert( pCutF->nVarsMax == pCutRes->nVarsMax ); + assert( pCutF->nVarsMax <= CUT_CELL_MVAR ); + // the factor cut (pCutF) should have its nodes sorted in the ascending order + assert( pCutF->nLeaves <= pCutF->nVarsMax ); + for ( i = 0; i < (int)pCutF->nLeaves - 1; i++ ) + assert( pCutF->pLeaves[i] < pCutF->pLeaves[i+1] ); + // the tree cut (pCutT) should have its nodes sorted in the ascending order + assert( pCutT->nLeaves <= pCutT->nVarsMax ); + for ( i = 0; i < (int)pCutT->nLeaves - 1; i++ ) + assert( pCutT->pLeaves[i] < pCutT->pLeaves[i+1] ); + // the resulting cut (pCutRes) should have its nodes sorted in the ascending order + assert( pCutRes->nLeaves <= pCutRes->nVarsMax ); + for ( i = 0; i < (int)pCutRes->nLeaves - 1; i++ ) + assert( pCutRes->pLeaves[i] < pCutRes->pLeaves[i+1] ); + // make sure that every node in pCutF (except Node) appears in pCutRes + for ( i = 0; i < (int)pCutF->nLeaves; i++ ) + { + if ( pCutF->pLeaves[i] == Node ) + continue; + for ( k = 0; k < (int)pCutRes->nLeaves; k++ ) + if ( pCutF->pLeaves[i] == pCutRes->pLeaves[k] ) + break; + assert( k < (int)pCutRes->nLeaves ); // node i from pCutF is not found in pCutRes!!! + } + // make sure that every node in pCutT appears in pCutRes + for ( i = 0; i < (int)pCutT->nLeaves; i++ ) + { + for ( k = 0; k < (int)pCutRes->nLeaves; k++ ) + if ( pCutT->pLeaves[i] == pCutRes->pLeaves[k] ) + break; + assert( k < (int)pCutRes->nLeaves ); // node i from pCutT is not found in pCutRes!!! + } + + + // find the index of the given node in the factor cut + NodeIndex = -1; + for ( NodeIndex = 0; NodeIndex < (int)pCutF->nLeaves; NodeIndex++ ) + if ( pCutF->pLeaves[NodeIndex] == Node ) + break; + assert( NodeIndex >= 0 ); // Node should be in pCutF + + // copy the truth table + Extra_TruthCopy( uTemp, Cut_CutReadTruth(pCutF), pCutF->nLeaves ); + + // bubble-move the NodeIndex variable to be the last one (the most significant one) + pIn = uTemp; pOut = uCof0; // uCof0 is used for temporary storage here + for ( i = NodeIndex; i < (int)pCutF->nLeaves - 1; i++ ) + { + Extra_TruthSwapAdjacentVars( pOut, pIn, pCutF->nLeaves, i ); + pTemp = pIn; pIn = pOut; pOut = pTemp; + } + if ( (pCutF->nLeaves - 1 - NodeIndex) & 1 ) + Extra_TruthCopy( pOut, pIn, pCutF->nLeaves ); + // the result of stretching is in uTemp + + // cofactor the factor cut with respect to the node + Extra_TruthCopy( uCof0, uTemp, pCutF->nLeaves ); + Extra_TruthCofactor0( uCof0, pCutF->nLeaves, pCutF->nLeaves-1 ); + Extra_TruthCopy( uCof1, uTemp, pCutF->nLeaves ); + Extra_TruthCofactor1( uCof1, pCutF->nLeaves, pCutF->nLeaves-1 ); + + // temporarily shrink the factor cut's variables by removing Node + for ( i = NodeIndex; i < (int)pCutF->nLeaves - 1; i++ ) + pCutF->pLeaves[i] = pCutF->pLeaves[i+1]; + pCutF->nLeaves--; + + // spread out the cofactors' truth tables to the same var order as the resulting cut + uPhase = Cut_TruthPhase(pCutRes, pCutF); + assert( Extra_WordCountOnes(uPhase) == (int)pCutF->nLeaves ); + Extra_TruthStretch( uTemp, uCof0, pCutF->nLeaves, pCutF->nVarsMax, uPhase ); + Extra_TruthCopy( uCof0, uTemp, pCutF->nVarsMax ); + Extra_TruthStretch( uTemp, uCof1, pCutF->nLeaves, pCutF->nVarsMax, uPhase ); + Extra_TruthCopy( uCof1, uTemp, pCutF->nVarsMax ); + + // spread out the tree cut's truth table to the same var order as the resulting cut + uPhase = Cut_TruthPhase(pCutRes, pCutT); + assert( Extra_WordCountOnes(uPhase) == (int)pCutT->nLeaves ); + Extra_TruthStretch( uTemp, Cut_CutReadTruth(pCutT), pCutT->nLeaves, pCutT->nVarsMax, uPhase ); + + // create the resulting truth table + pTemp = Cut_CutReadTruth(pCutRes); + for ( i = Extra_TruthWordNum(pCutRes->nLeaves)-1; i >= 0; i-- ) + pTemp[i] = (uCof0[i] & ~uTemp[i]) | (uCof1[i] & uTemp[i]); + + // undo the removal of the node from the cut + for ( i = (int)pCutF->nLeaves - 1; i >= NodeIndex; --i ) + pCutF->pLeaves[i+1] = pCutF->pLeaves[i]; + pCutF->pLeaves[NodeIndex] = Node; + pCutF->nLeaves++; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutInt.h b/src/opt/cut/cutInt.h index fe5080b4..17f268c7 100644 --- a/src/opt/cut/cutInt.h +++ b/src/opt/cut/cutInt.h @@ -29,6 +29,7 @@ #include "extra.h" #include "vec.h" #include "cut.h" +#include "cutList.h" //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// @@ -41,56 +42,103 @@ typedef struct Cut_HashTableStruct_t_ Cut_HashTable_t; struct Cut_ManStruct_t_ -{ +{ // user preferences Cut_Params_t * pParams; // computation parameters Vec_Int_t * vFanCounts; // the array of fanout counters + Vec_Int_t * vNodeAttrs; // node attributes (1 = global; 0 = local) // storage for cuts - Vec_Ptr_t * vCuts; // cuts by ID - Vec_Ptr_t * vCutsNew; // cuts by ID - Cut_HashTable_t * tTable; // cuts by their leaves (and root) + Vec_Ptr_t * vCutsNew; // new cuts by node ID + Vec_Ptr_t * vCutsOld; // old cuts by node ID + Vec_Ptr_t * vCutsTemp; // temp cuts for cutset nodes by cutset node number // memory management Extra_MmFixed_t * pMmCuts; int EntrySize; + int nTruthWords; // temporary variables Cut_Cut_t * pReady; Vec_Ptr_t * vTemp; int fCompl0; int fCompl1; int fSimul; - // precomputations - unsigned uTruthVars[6][2]; - unsigned short ** pPerms43; - unsigned ** pPerms53; - unsigned ** pPerms54; + int nNodeCuts; + Cut_Cut_t * pStore0[2]; + Cut_Cut_t * pStore1[2]; + Cut_Cut_t * pCompareOld; + Cut_Cut_t * pCompareNew; + unsigned * puTemp[4]; + // record of the cut computation + Vec_Int_t * vNodeCuts; // the number of cuts for each node + Vec_Int_t * vNodeStarts; // the number of the starting cut of each node + Vec_Int_t * vCutPairs; // the pairs of parent cuts for each cut + // minimum delay mapping with the given cuts + Vec_Ptr_t * vCutsMax; + Vec_Int_t * vDelays; + Vec_Int_t * vDelays2; + int nDelayMin; // statistics int nCutsCur; int nCutsAlloc; int nCutsDealloc; int nCutsPeak; int nCutsTriv; - int nCutsNode; + int nCutsFilter; + int nCutsLimit; int nNodes; + int nNodesDag; + int nNodesNoCuts; // runtime int timeMerge; int timeUnion; int timeTruth; int timeFilter; int timeHash; + int timeMap; }; +// iterator through all the cuts of the list +#define Cut_ListForEachCut( pList, pCut ) \ + for ( pCut = pList; \ + pCut; \ + pCut = pCut->pNext ) +#define Cut_ListForEachCutStop( pList, pCut, pStop ) \ + for ( pCut = pList; \ + pCut != pStop; \ + pCut = pCut->pNext ) +#define Cut_ListForEachCutSafe( pList, pCut, pCut2 ) \ + for ( pCut = pList, \ + pCut2 = pCut? pCut->pNext: NULL; \ + pCut; \ + pCut = pCut2, \ + pCut2 = pCut? pCut->pNext: NULL ) + //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +// computes signature of the node +static inline unsigned Cut_NodeSign( int Node ) { return (1 << (Node % 31)); } +static inline int Cut_TruthWords( int nVarsMax ) { return nVarsMax <= 5 ? 1 : (1 << (nVarsMax - 5)); } + //////////////////////////////////////////////////////////////////////// /// FUNCTION DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +/*=== cutCut.c ==========================================================*/ +extern Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ); +extern void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ); +extern int Cut_CutCompare( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 ); +extern Cut_Cut_t * Cut_CutDupList( Cut_Man_t * p, Cut_Cut_t * pList ); +extern void Cut_CutRecycleList( Cut_Man_t * p, Cut_Cut_t * pList ); +extern Cut_Cut_t * Cut_CutMergeLists( Cut_Cut_t * pList1, Cut_Cut_t * pList2 ); +extern void Cut_CutNumberList( Cut_Cut_t * pList ); +extern Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ); +extern void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); /*=== cutMerge.c ==========================================================*/ extern Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); /*=== cutNode.c ==========================================================*/ -extern Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ); +extern void Cut_NodeDoComputeCuts( Cut_Man_t * p, Cut_List_t * pSuper, int Node, int fCompl0, int fCompl1, Cut_Cut_t * pList0, Cut_Cut_t * pList1, int fTriv, int TreeCode ); +extern int Cut_CutListVerify( Cut_Cut_t * pList ); /*=== cutTable.c ==========================================================*/ extern Cut_HashTable_t * Cut_TableStart( int Size ); extern void Cut_TableStop( Cut_HashTable_t * pTable ); @@ -98,11 +146,12 @@ extern int Cut_TableLookup( Cut_HashTable_t * pTable, Cut_Cut_t extern void Cut_TableClear( Cut_HashTable_t * pTable ); extern int Cut_TableReadTime( Cut_HashTable_t * pTable ); /*=== cutTruth.c ==========================================================*/ -extern void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); +extern void Cut_TruthComputeOld( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ); +extern void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ); + +#endif //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif - diff --git a/src/opt/cut/cutList.h b/src/opt/cut/cutList.h index eb008ef9..a03ec9d5 100644 --- a/src/opt/cut/cutList.h +++ b/src/opt/cut/cutList.h @@ -36,12 +36,12 @@ typedef struct Cut_ListStruct_t_ Cut_List_t; struct Cut_ListStruct_t_ { - Cut_Cut_t * pHead[7]; - Cut_Cut_t ** ppTail[7]; + Cut_Cut_t * pHead[CUT_SIZE_MAX+1]; + Cut_Cut_t ** ppTail[CUT_SIZE_MAX+1]; }; //////////////////////////////////////////////////////////////////////// -/// MACRO DEFITIONS /// +/// MACRO DEFINITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// @@ -50,7 +50,7 @@ struct Cut_ListStruct_t_ /**Function************************************************************* - Synopsis [] + Synopsis [Start the cut list.] Description [] @@ -62,7 +62,7 @@ struct Cut_ListStruct_t_ static inline void Cut_ListStart( Cut_List_t * p ) { int i; - for ( i = 1; i <= 6; i++ ) + for ( i = 1; i <= CUT_SIZE_MAX; i++ ) { p->pHead[i] = 0; p->ppTail[i] = &p->pHead[i]; @@ -71,7 +71,7 @@ static inline void Cut_ListStart( Cut_List_t * p ) /**Function************************************************************* - Synopsis [] + Synopsis [Adds one cut to the cut list.] Description [] @@ -82,14 +82,100 @@ static inline void Cut_ListStart( Cut_List_t * p ) ***********************************************************************/ static inline void Cut_ListAdd( Cut_List_t * p, Cut_Cut_t * pCut ) { - assert( pCut->nLeaves > 0 && pCut->nLeaves < 7 ); + assert( pCut->nLeaves > 0 && pCut->nLeaves <= CUT_SIZE_MAX ); *p->ppTail[pCut->nLeaves] = pCut; p->ppTail[pCut->nLeaves] = &pCut->pNext; } /**Function************************************************************* - Synopsis [] + Synopsis [Adds one cut to the cut list while preserving order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Cut_ListAdd2( Cut_List_t * p, Cut_Cut_t * pCut ) +{ + extern int Cut_CutCompare( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 ); + Cut_Cut_t * pTemp, ** ppSpot; + assert( pCut->nLeaves > 0 && pCut->nLeaves <= CUT_SIZE_MAX ); + if ( p->pHead[pCut->nLeaves] != NULL ) + { + ppSpot = &p->pHead[pCut->nLeaves]; + for ( pTemp = p->pHead[pCut->nLeaves]; pTemp; pTemp = pTemp->pNext ) + { + if ( Cut_CutCompare(pCut, pTemp) < 0 ) + { + *ppSpot = pCut; + pCut->pNext = pTemp; + return; + } + else + ppSpot = &pTemp->pNext; + } + } + *p->ppTail[pCut->nLeaves] = pCut; + p->ppTail[pCut->nLeaves] = &pCut->pNext; +} + +/**Function************************************************************* + + Synopsis [Derive the super list from the linked list of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Cut_ListDerive( Cut_List_t * p, Cut_Cut_t * pList ) +{ + Cut_Cut_t * pPrev; + int nLeaves; + Cut_ListStart( p ); + while ( pList != NULL ) + { + nLeaves = pList->nLeaves; + p->pHead[nLeaves] = pList; + for ( pPrev = pList, pList = pList->pNext; pList; pPrev = pList, pList = pList->pNext ) + if ( nLeaves < (int)pList->nLeaves ) + break; + p->ppTail[nLeaves] = &pPrev->pNext; + pPrev->pNext = NULL; + } +} + +/**Function************************************************************* + + Synopsis [Adds the second list to the first list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Cut_ListAddList( Cut_List_t * pOld, Cut_List_t * pNew ) +{ + int i; + for ( i = 1; i <= CUT_SIZE_MAX; i++ ) + { + if ( pNew->pHead[i] == NULL ) + continue; + *pOld->ppTail[i] = pNew->pHead[i]; + pOld->ppTail[i] = pNew->ppTail[i]; + } +} + +/**Function************************************************************* + + Synopsis [Returns the cut list linked into one sequence of cuts.] Description [] @@ -100,16 +186,22 @@ static inline void Cut_ListAdd( Cut_List_t * p, Cut_Cut_t * pCut ) ***********************************************************************/ static inline Cut_Cut_t * Cut_ListFinish( Cut_List_t * p ) { + Cut_Cut_t * pHead = NULL, ** ppTail = &pHead; int i; - for ( i = 1; i < 6; i++ ) - *p->ppTail[i] = p->pHead[i+1]; - *p->ppTail[6] = NULL; - return p->pHead[1]; + for ( i = 1; i <= CUT_SIZE_MAX; i++ ) + { + if ( p->pHead[i] == NULL ) + continue; + *ppTail = p->pHead[i]; + ppTail = p->ppTail[i]; + } + *ppTail = NULL; + return pHead; } +#endif + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -#endif - diff --git a/src/opt/cut/cutMan.c b/src/opt/cut/cutMan.c index 4ad3a66a..8593ef93 100644 --- a/src/opt/cut/cutMan.c +++ b/src/opt/cut/cutMan.c @@ -24,8 +24,10 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +extern void Npn_StartTruth8( uint8 uTruths[][32] ); + //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -43,47 +45,65 @@ Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ) { Cut_Man_t * p; int clk = clock(); - assert( pParams->nVarsMax >= 4 && pParams->nVarsMax <= 6 ); +// extern int nTruthDsd; +// nTruthDsd = 0; + assert( pParams->nVarsMax >= 3 && pParams->nVarsMax <= CUT_SIZE_MAX ); p = ALLOC( Cut_Man_t, 1 ); memset( p, 0, sizeof(Cut_Man_t) ); // set and correct parameters p->pParams = pParams; - if ( p->pParams->fSeq ) - p->pParams->fHash = 1; - // space for cuts - p->vCuts = Vec_PtrAlloc( pParams->nIdsMax ); - Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); + // prepare storage for cuts + p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax ); + Vec_PtrFill( p->vCutsNew, pParams->nIdsMax, NULL ); + // prepare storage for sequential cuts if ( pParams->fSeq ) { - p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax ); - Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); + p->pParams->fFilter = 1; + p->vCutsOld = Vec_PtrAlloc( pParams->nIdsMax ); + Vec_PtrFill( p->vCutsOld, pParams->nIdsMax, NULL ); + p->vCutsTemp = Vec_PtrAlloc( pParams->nCutSet ); + Vec_PtrFill( p->vCutsTemp, pParams->nCutSet, NULL ); + if ( pParams->fTruth && pParams->nVarsMax > 5 ) + { + pParams->fTruth = 0; + printf( "Skipping computation of truth tables for sequential cuts with more than 5 inputs.\n" ); + } } - // hash tables - if ( pParams->fHash ) - p->tTable = Cut_TableStart( p->pParams->nKeepMax ); // entry size - p->EntrySize = sizeof(Cut_Cut_t) + (pParams->nVarsMax + pParams->fSeq) * sizeof(int); - if ( pParams->nVarsMax == 5 ) - p->EntrySize += sizeof(unsigned); - else if ( pParams->nVarsMax == 6 ) - p->EntrySize += 2 * sizeof(unsigned); + p->EntrySize = sizeof(Cut_Cut_t) + pParams->nVarsMax * sizeof(int); + if ( pParams->fTruth ) + { + if ( pParams->nVarsMax > 14 ) + { + pParams->fTruth = 0; + printf( "Skipping computation of truth table for more than %d inputs.\n", 14 ); + } + else + { + p->nTruthWords = Cut_TruthWords( pParams->nVarsMax ); + p->EntrySize += p->nTruthWords * sizeof(unsigned); + } + p->puTemp[0] = ALLOC( unsigned, 4 * p->nTruthWords ); + p->puTemp[1] = p->puTemp[0] + p->nTruthWords; + p->puTemp[2] = p->puTemp[1] + p->nTruthWords; + p->puTemp[3] = p->puTemp[2] + p->nTruthWords; + } + // enable cut computation recording + if ( pParams->fRecord ) + { + p->vNodeCuts = Vec_IntStart( pParams->nIdsMax ); + p->vNodeStarts = Vec_IntStart( pParams->nIdsMax ); + p->vCutPairs = Vec_IntAlloc( 0 ); + } + // allocate storage for delays + if ( pParams->fMap && !p->pParams->fSeq ) + { + p->vDelays = Vec_IntStart( pParams->nIdsMax ); + p->vDelays2 = Vec_IntStart( pParams->nIdsMax ); + p->vCutsMax = Vec_PtrStart( pParams->nIdsMax ); + } // memory for cuts p->pMmCuts = Extra_MmFixedStart( p->EntrySize ); - // precomputations -// if ( pParams->fTruth && pParams->nVarsMax == 4 ) -// p->pPerms43 = Extra_TruthPerm43(); -// else if ( pParams->fTruth ) -// { -// p->pPerms53 = Extra_TruthPerm53(); -// p->pPerms54 = Extra_TruthPerm54(); -// } - p->uTruthVars[0][1] = p->uTruthVars[0][0] = 0xAAAAAAAA; // 1010 1010 1010 1010 1010 1010 1010 1010 - p->uTruthVars[1][1] = p->uTruthVars[1][0] = 0xCCCCCCCC; // 1010 1010 1010 1010 1010 1010 1010 1010 - p->uTruthVars[2][1] = p->uTruthVars[2][0] = 0xF0F0F0F0; // 1111 0000 1111 0000 1111 0000 1111 0000 - p->uTruthVars[3][1] = p->uTruthVars[3][0] = 0xFF00FF00; // 1111 1111 0000 0000 1111 1111 0000 0000 - p->uTruthVars[4][1] = p->uTruthVars[4][0] = 0xFFFF0000; // 1111 1111 1111 1111 0000 0000 0000 0000 - p->uTruthVars[5][0] = 0x00000000; - p->uTruthVars[5][1] = 0xFFFFFFFF; p->vTemp = Vec_PtrAlloc( 100 ); return p; } @@ -103,23 +123,29 @@ void Cut_ManStop( Cut_Man_t * p ) { Cut_Cut_t * pCut; int i; - Vec_PtrForEachEntry( p->vCuts, pCut, i ) - { +// extern int nTruthDsd; +// printf( "Decomposable cuts = %d.\n", nTruthDsd ); + + Vec_PtrForEachEntry( p->vCutsNew, pCut, i ) if ( pCut != NULL ) { int k = 0; } - } - - if ( p->vCutsNew ) Vec_PtrFree( p->vCutsNew ); - if ( p->vCuts ) Vec_PtrFree( p->vCuts ); - if ( p->vFanCounts ) Vec_IntFree( p->vFanCounts ); - if ( p->pPerms43 ) free( p->pPerms43 ); - if ( p->pPerms53 ) free( p->pPerms53 ); - if ( p->pPerms54 ) free( p->pPerms54 ); - if ( p->vTemp ) Vec_PtrFree( p->vTemp ); - if ( p->tTable ) Cut_TableStop( p->tTable ); - Extra_MmFixedStop( p->pMmCuts, 0 ); + if ( p->vCutsNew ) Vec_PtrFree( p->vCutsNew ); + if ( p->vCutsOld ) Vec_PtrFree( p->vCutsOld ); + if ( p->vCutsTemp ) Vec_PtrFree( p->vCutsTemp ); + if ( p->vFanCounts ) Vec_IntFree( p->vFanCounts ); + if ( p->vTemp ) Vec_PtrFree( p->vTemp ); + + if ( p->vCutsMax ) Vec_PtrFree( p->vCutsMax ); + if ( p->vDelays ) Vec_IntFree( p->vDelays ); + if ( p->vDelays2 ) Vec_IntFree( p->vDelays2 ); + if ( p->vNodeCuts ) Vec_IntFree( p->vNodeCuts ); + if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts ); + if ( p->vCutPairs ) Vec_IntFree( p->vCutPairs ); + if ( p->puTemp[0] ) free( p->puTemp[0] ); + + Extra_MmFixedStop( p->pMmCuts ); free( p ); } @@ -136,21 +162,66 @@ void Cut_ManStop( Cut_Man_t * p ) ***********************************************************************/ void Cut_ManPrintStats( Cut_Man_t * p ) { + if ( p->pReady ) + { + Cut_CutRecycle( p, p->pReady ); + p->pReady = NULL; + } printf( "Cut computation statistics:\n" ); printf( "Current cuts = %8d. (Trivial = %d.)\n", p->nCutsCur-p->nCutsTriv, p->nCutsTriv ); printf( "Peak cuts = %8d.\n", p->nCutsPeak ); printf( "Total allocated = %8d.\n", p->nCutsAlloc ); printf( "Total deallocated = %8d.\n", p->nCutsDealloc ); + printf( "Cuts filtered = %8d.\n", p->nCutsFilter ); + printf( "Nodes saturated = %8d. (Max cuts = %d.)\n", p->nCutsLimit, p->pParams->nKeepMax ); printf( "Cuts per node = %8.1f\n", ((float)(p->nCutsCur-p->nCutsTriv))/p->nNodes ); printf( "The cut size = %8d bytes.\n", p->EntrySize ); printf( "Peak memory = %8.2f Mb.\n", (float)p->nCutsPeak * p->EntrySize / (1<<20) ); + printf( "Total nodes = %8d.\n", p->nNodes ); + if ( p->pParams->fDag || p->pParams->fTree ) + { + printf( "DAG nodes = %8d.\n", p->nNodesDag ); + printf( "Tree nodes = %8d.\n", p->nNodes - p->nNodesDag ); + } + printf( "Nodes w/o cuts = %8d.\n", p->nNodesNoCuts ); + if ( p->pParams->fMap && !p->pParams->fSeq ) + printf( "Mapping delay = %8d.\n", p->nDelayMin ); + PRT( "Merge ", p->timeMerge ); PRT( "Union ", p->timeUnion ); - PRT( "Hash ", Cut_TableReadTime(p->tTable) ); PRT( "Filter", p->timeFilter ); PRT( "Truth ", p->timeTruth ); + PRT( "Map ", p->timeMap ); +// printf( "Nodes = %d. Multi = %d. Cuts = %d. Multi = %d.\n", +// p->nNodes, p->nNodesMulti, p->nCutsCur-p->nCutsTriv, p->nCutsMulti ); +// printf( "Count0 = %d. Count1 = %d. Count2 = %d.\n\n", p->Count0, p->Count1, p->Count2 ); } + +/**Function************************************************************* + + Synopsis [Prints some interesting stats.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_ManPrintStatsToFile( Cut_Man_t * p, char * pFileName, int TimeTotal ) +{ + FILE * pTable; + pTable = fopen( "cut_stats.txt", "a+" ); + fprintf( pTable, "%-20s ", pFileName ); + fprintf( pTable, "%8d ", p->nNodes ); + fprintf( pTable, "%6.1f ", ((float)(p->nCutsCur))/p->nNodes ); + fprintf( pTable, "%6.2f ", ((float)(100.0 * p->nCutsLimit))/p->nNodes ); + fprintf( pTable, "%6.2f ", (float)p->nCutsPeak * p->EntrySize / (1<<20) ); + fprintf( pTable, "%6.2f ", (float)(TimeTotal)/(float)(CLOCKS_PER_SEC) ); + fprintf( pTable, "\n" ); + fclose( pTable ); +} /**Function************************************************************* @@ -168,6 +239,86 @@ void Cut_ManSetFanoutCounts( Cut_Man_t * p, Vec_Int_t * vFanCounts ) p->vFanCounts = vFanCounts; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_ManSetNodeAttrs( Cut_Man_t * p, Vec_Int_t * vNodeAttrs ) +{ + p->vNodeAttrs = vNodeAttrs; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_ManReadVarsMax( Cut_Man_t * p ) +{ + return p->pParams->nVarsMax; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_Params_t * Cut_ManReadParams( Cut_Man_t * p ) +{ + return p->pParams; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Cut_ManReadNodeAttrs( Cut_Man_t * p ) +{ + return p->vNodeAttrs; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_ManIncrementDagNodes( Cut_Man_t * p ) +{ + p->nNodesDag++; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/cut/cutMerge.c b/src/opt/cut/cutMerge.c index ba1afce4..d8a9989c 100644 --- a/src/opt/cut/cutMerge.c +++ b/src/opt/cut/cutMerge.c @@ -25,7 +25,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -39,7 +39,7 @@ SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}}; Cut_Cut_t * pRes; @@ -164,7 +164,7 @@ Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { Cut_Cut_t * pRes; int * pLeaves; @@ -526,7 +526,7 @@ Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut return NULL; } pRes = Cut_CutAlloc( p ); - pRes->uTruth = (uSign1 << 8); + pRes->Num1 = uSign1; } for ( i = 0; i < (int)pCut0->nLeaves; i++ ) pRes->pLeaves[i] = pCut0->pLeaves[i]; @@ -645,7 +645,8 @@ Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut } assert( Count == nNodes ); pRes->nLeaves = nNodes; - pRes->uTruth = (uSign1 << 8) | uSign0; + pRes->Num1 = uSign1; + pRes->Num0 = uSign0; return pRes; } diff --git a/src/opt/cut/cutNode.c b/src/opt/cut/cutNode.c index 8d16ac8a..1f93b14b 100644 --- a/src/opt/cut/cutNode.c +++ b/src/opt/cut/cutNode.c @@ -19,42 +19,21 @@ ***********************************************************************/ #include "cutInt.h" -#include "cutList.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static inline Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ); -static inline void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ); -static inline int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ); - -static void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); -static void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ); - -// iterator through all the cuts of the list -#define Cut_ListForEachCut( pList, pCut ) \ - for ( pCut = pList; \ - pCut; \ - pCut = pCut->pNext ) -#define Cut_ListForEachCutStop( pList, pCut, pStop ) \ - for ( pCut = pList; \ - pCut != pStop; \ - pCut = pCut->pNext ) -#define Cut_ListForEachCutSafe( pList, pCut, pCut2 ) \ - for ( pCut = pList, \ - pCut2 = pCut? pCut->pNext: NULL; \ - pCut; \ - pCut = pCut2, \ - pCut2 = pCut? pCut->pNext: NULL ) +static int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ); +static int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Returns the pointer to the linked list of cuts.] + Synopsis [Returns 1 if pDom is contained in pCut.] Description [] @@ -63,16 +42,24 @@ static void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ); SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ) +static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut ) { - if ( Node >= p->vCuts->nSize ) - return NULL; - return Vec_PtrEntry( p->vCuts, Node ); + int i, k; + for ( i = 0; i < (int)pDom->nLeaves; i++ ) + { + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) + break; + if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut + return 0; + } + // every node in pDom is contained in pCut + return 1; } /**Function************************************************************* - Synopsis [Returns the pointer to the linked list of cuts.] + Synopsis [Filters cuts using dominance.] Description [] @@ -81,14 +68,293 @@ Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) +static inline void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) +{ + Cut_Cut_t * pListR, ** ppListR = &pListR; + Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev; + // save the first cut + *ppListR = pList, ppListR = &pList->pNext; + // try to filter out other cuts + pPrev = pList; + Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 ) + { + assert( pCut->nLeaves > 1 ); + // go through all the previous cuts up to pCut + Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) + { + if ( pDom->nLeaves > pCut->nLeaves ) + continue; + if ( (pDom->uSign & pCut->uSign) != pDom->uSign ) + continue; + if ( Cut_CutCheckDominance( pDom, pCut ) ) + break; + } + if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut + { + // make sure cuts are connected after removing + pPrev->pNext = pCut->pNext; + // recycle the cut + Cut_CutRecycle( p, pCut ); + } + else // pDom is NOT contained in pCut - save pCut + { + *ppListR = pCut, ppListR = &pCut->pNext; + pPrev = pCut; + } + } + *ppListR = NULL; +} + +/**Function************************************************************* + + Synopsis [Checks equality of one cut.] + + Description [Returns 1 if the cut is removed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Cut_CutFilterOneEqual( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut ) { - Vec_PtrWriteEntry( p->vCuts, Node, pList ); + Cut_Cut_t * pTemp; + Cut_ListForEachCut( pSuperList->pHead[pCut->nLeaves], pTemp ) + { + // skip the non-contained cuts + if ( pCut->uSign != pTemp->uSign ) + continue; + // check containment seriously + if ( Cut_CutCheckDominance( pTemp, pCut ) ) + { + p->nCutsFilter++; + Cut_CutRecycle( p, pCut ); + return 1; + } + } + return 0; } /**Function************************************************************* - Synopsis [Sets the trivial cut for the node.] + Synopsis [Checks containment for one cut.] + + Description [Returns 1 if the cut is removed.] + + SideEffects [May remove other cuts in the set.] + + SeeAlso [] + +***********************************************************************/ +static inline int Cut_CutFilterOne( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut ) +{ + Cut_Cut_t * pTemp, * pTemp2, ** ppTail; + int a; + + // check if this cut is filtered out by smaller cuts + for ( a = 2; a <= (int)pCut->nLeaves; a++ ) + { + Cut_ListForEachCut( pSuperList->pHead[a], pTemp ) + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) + continue; + // check containment seriously + if ( Cut_CutCheckDominance( pTemp, pCut ) ) + { + p->nCutsFilter++; + Cut_CutRecycle( p, pCut ); + return 1; + } + } + } + + // filter out other cuts using this one + for ( a = pCut->nLeaves + 1; a <= (int)pCut->nVarsMax; a++ ) + { + ppTail = pSuperList->pHead + a; + Cut_ListForEachCutSafe( pSuperList->pHead[a], pTemp, pTemp2 ) + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) + { + ppTail = &pTemp->pNext; + continue; + } + // check containment seriously + if ( Cut_CutCheckDominance( pCut, pTemp ) ) + { + p->nCutsFilter++; + p->nNodeCuts--; + // move the head + if ( pSuperList->pHead[a] == pTemp ) + pSuperList->pHead[a] = pTemp->pNext; + // move the tail + if ( pSuperList->ppTail[a] == &pTemp->pNext ) + pSuperList->ppTail[a] = ppTail; + // skip the given cut in the list + *ppTail = pTemp->pNext; + // recycle pTemp + Cut_CutRecycle( p, pTemp ); + } + else + ppTail = &pTemp->pNext; + } + assert( ppTail == pSuperList->ppTail[a] ); + assert( *ppTail == NULL ); + } + + return 0; +} + +/**Function************************************************************* + + Synopsis [Checks if the cut is local and can be removed.] + + Description [Returns 1 if the cut is removed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Cut_CutFilterGlobal( Cut_Man_t * p, Cut_Cut_t * pCut ) +{ + int a; + if ( pCut->nLeaves == 1 ) + return 0; + for ( a = 0; a < (int)pCut->nLeaves; a++ ) + if ( Vec_IntEntry( p->vNodeAttrs, pCut->pLeaves[a] ) ) // global + return 0; + // there is no global nodes, the cut should be removed + p->nCutsFilter++; + Cut_CutRecycle( p, pCut ); + return 1; +} + + +/**Function************************************************************* + + Synopsis [Checks containment for one cut.] + + Description [Returns 1 if the cut is removed.] + + SideEffects [May remove other cuts in the set.] + + SeeAlso [] + +***********************************************************************/ +static inline int Cut_CutFilterOld( Cut_Man_t * p, Cut_Cut_t * pList, Cut_Cut_t * pCut ) +{ + Cut_Cut_t * pPrev, * pTemp, * pTemp2, ** ppTail; + + // check if this cut is filtered out by smaller cuts + pPrev = NULL; + Cut_ListForEachCut( pList, pTemp ) + { + if ( pTemp->nLeaves > pCut->nLeaves ) + break; + pPrev = pTemp; + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) + continue; + // check containment seriously + if ( Cut_CutCheckDominance( pTemp, pCut ) ) + { + p->nCutsFilter++; + Cut_CutRecycle( p, pCut ); + return 1; + } + } + assert( pPrev->pNext == pTemp ); + + // filter out other cuts using this one + ppTail = &pPrev->pNext; + Cut_ListForEachCutSafe( pTemp, pTemp, pTemp2 ) + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) + { + ppTail = &pTemp->pNext; + continue; + } + // check containment seriously + if ( Cut_CutCheckDominance( pCut, pTemp ) ) + { + p->nCutsFilter++; + p->nNodeCuts--; + // skip the given cut in the list + *ppTail = pTemp->pNext; + // recycle pTemp + Cut_CutRecycle( p, pTemp ); + } + else + ppTail = &pTemp->pNext; + } + assert( *ppTail == NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Processes two cuts.] + + Description [Returns 1 if the limit has been reached.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Cut_CutProcessTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ) +{ + Cut_Cut_t * pCut; + // merge the cuts + if ( pCut0->nLeaves >= pCut1->nLeaves ) + pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); + else + pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); + if ( pCut == NULL ) + return 0; + assert( p->pParams->fSeq || pCut->nLeaves > 1 ); + // set the signature + pCut->uSign = pCut0->uSign | pCut1->uSign; + if ( p->pParams->fRecord ) + pCut->Num0 = pCut0->Num0, pCut->Num1 = pCut1->Num0; + // check containment + if ( p->pParams->fFilter ) + { + if ( Cut_CutFilterOne(p, pSuperList, pCut) ) +// if ( Cut_CutFilterOneEqual(p, pSuperList, pCut) ) + return 0; + if ( p->pParams->fSeq ) + { + if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) + return 0; + if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) + return 0; + } + } + + if ( p->pParams->fGlobal ) + { + assert( p->vNodeAttrs != NULL ); + if ( Cut_CutFilterGlobal( p, pCut ) ) + return 0; + } + + // compute the truth table + if ( p->pParams->fTruth ) + Cut_TruthCompute( p, pCut, pCut0, pCut1, p->fCompl0, p->fCompl1 ); + // add to the list + Cut_ListAdd( pSuperList, pCut ); + // return status (0 if okay; 1 if exceeded the limit) + return ++p->nNodeCuts == p->pParams->nKeepMax; +} + +/**Function************************************************************* + + Synopsis [Computes the cuts by merging cuts at two nodes.] Description [] @@ -97,15 +363,68 @@ void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * pList ) SeeAlso [] ***********************************************************************/ -void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) +Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode ) { - assert( Cut_NodeReadCuts(p, Node) == NULL ); - Cut_NodeWriteCuts( p, Node, Cut_CutCreateTriv(p, Node) ); + Cut_List_t Super, * pSuper = &Super; + Cut_Cut_t * pList, * pCut; + int clk; + // start the number of cuts at the node + p->nNodes++; + p->nNodeCuts = 0; + // prepare information for recording + if ( p->pParams->fRecord ) + { + Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) ); + Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) ); + } + // compute the cuts +clk = clock(); + Cut_ListStart( pSuper ); + Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode ); + pList = Cut_ListFinish( pSuper ); +p->timeMerge += clock() - clk; + // verify the result of cut computation +// Cut_CutListVerify( pList ); + // performing the recording + if ( p->pParams->fRecord ) + { + Vec_IntWriteEntry( p->vNodeStarts, Node, Vec_IntSize(p->vCutPairs) ); + Cut_ListForEachCut( pList, pCut ) + Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) ); + Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) ); + } + // check if the node is over the list + if ( p->nNodeCuts == p->pParams->nKeepMax ) + p->nCutsLimit++; + // set the list at the node + Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL ); + assert( Cut_NodeReadCutsNew(p, Node) == NULL ); + ///// +// pList->pNext = NULL; + ///// + Cut_NodeWriteCutsNew( p, Node, pList ); + // filter the cuts +//clk = clock(); +// if ( p->pParams->fFilter ) +// Cut_CutFilter( p, pList0 ); +//p->timeFilter += clock() - clk; + // perform mapping of this node with these cuts +clk = clock(); + if ( p->pParams->fMap && !p->pParams->fSeq ) + { +// int Delay1, Delay2; +// Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 ); +// Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 ); +// assert( Delay1 >= Delay2 ); + Cut_NodeMapping( p, pList, Node, Node0, Node1 ); + } +p->timeMap += clock() - clk; + return pList; } /**Function************************************************************* - Synopsis [Deallocates the cuts at the node.] + Synopsis [Returns optimum delay mapping.] Description [] @@ -114,21 +433,96 @@ void Cut_NodeSetTriv( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) +int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ) { - Cut_Cut_t * pList, * pCut, * pCut2; - pList = Cut_NodeReadCuts( p, Node ); - if ( pList == NULL ) - return; - Cut_ListForEachCutSafe( pList, pCut, pCut2 ) - Cut_CutRecycle( p, pCut ); - Cut_NodeWriteCuts( p, Node, NULL ); + Cut_Cut_t * pCut; + int DelayMin, DelayCur, i; + if ( pCuts == NULL ) + p->nDelayMin = -1; + if ( p->nDelayMin == -1 ) + return -1; + DelayMin = 1000000; + Cut_ListForEachCut( pCuts, pCut ) + { + if ( pCut->nLeaves == 1 ) + continue; + DelayCur = 0; + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + if ( DelayCur < Vec_IntEntry(p->vDelays, pCut->pLeaves[i]) ) + DelayCur = Vec_IntEntry(p->vDelays, pCut->pLeaves[i]); + if ( DelayMin > DelayCur ) + DelayMin = DelayCur; + } + if ( DelayMin == 1000000 ) + { + p->nDelayMin = -1; + return -1; + } + DelayMin++; + Vec_IntWriteEntry( p->vDelays, Node, DelayMin ); + if ( p->nDelayMin < DelayMin ) + p->nDelayMin = DelayMin; + return DelayMin; } +/**Function************************************************************* + + Synopsis [Returns optimum delay mapping using the largest cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ) +{ + Cut_Cut_t * pCut0, * pCut1, * pCut; + int Delay0, Delay1, Delay; + // get the fanin cuts + Delay0 = Vec_IntEntry( p->vDelays2, Node0 ); + Delay1 = Vec_IntEntry( p->vDelays2, Node1 ); + pCut0 = (Delay0 == 0) ? Vec_PtrEntry( p->vCutsNew, Node0 ) : Vec_PtrEntry( p->vCutsMax, Node0 ); + pCut1 = (Delay1 == 0) ? Vec_PtrEntry( p->vCutsNew, Node1 ) : Vec_PtrEntry( p->vCutsMax, Node1 ); + if ( Delay0 == Delay1 ) + Delay = (Delay0 == 0) ? Delay0 + 1: Delay0; + else if ( Delay0 > Delay1 ) + { + Delay = Delay0; + pCut1 = Vec_PtrEntry( p->vCutsNew, Node1 ); + assert( pCut1->nLeaves == 1 ); + } + else // if ( Delay0 < Delay1 ) + { + Delay = Delay1; + pCut0 = Vec_PtrEntry( p->vCutsNew, Node0 ); + assert( pCut0->nLeaves == 1 ); + } + // merge the cuts + if ( pCut0->nLeaves < pCut1->nLeaves ) + pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); + else + pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); + if ( pCut == NULL ) + { + Delay++; + pCut = Cut_CutAlloc( p ); + pCut->nLeaves = 2; + pCut->pLeaves[0] = Node0 < Node1 ? Node0 : Node1; + pCut->pLeaves[1] = Node0 < Node1 ? Node1 : Node0; + } + assert( Delay > 0 ); + Vec_IntWriteEntry( p->vDelays2, Node, Delay ); + Vec_PtrWriteEntry( p->vCutsMax, Node, pCut ); + if ( p->nDelayMin < Delay ) + p->nDelayMin = Delay; + return Delay; +} /**Function************************************************************* - Synopsis [] + Synopsis [Computes area after mapping.] Description [] @@ -137,10 +531,23 @@ void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -void Cut_NodeSetComputedAsNew( Cut_Man_t * p, int Node ) +int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node ) { + Cut_Cut_t * pCut; + int i, Counter; + if ( p->vCutsMax == NULL ) + return 0; + pCut = Vec_PtrEntry( p->vCutsMax, Node ); + if ( pCut == NULL || pCut->nLeaves == 1 ) + return 0; + Counter = 0; + for ( i = 0; i < (int)pCut->nLeaves; i++ ) + Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] ); + Vec_PtrWriteEntry( p->vCutsMax, Node, NULL ); + return 1 + Counter; } + /**Function************************************************************* Synopsis [Computes the cuts by merging cuts at two nodes.] @@ -152,24 +559,43 @@ void Cut_NodeSetComputedAsNew( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ) +void Cut_NodeDoComputeCuts( Cut_Man_t * p, Cut_List_t * pSuper, int Node, int fCompl0, int fCompl1, Cut_Cut_t * pList0, Cut_Cut_t * pList1, int fTriv, int TreeCode ) { - Cut_List_t SuperList; - Cut_Cut_t * pList0, * pList1, * pStop0, * pStop1, * pTemp0, * pTemp1; - int i, Limit = p->pParams->nVarsMax; - int clk = clock(); - assert( p->pParams->nVarsMax <= 6 ); - // start the new list - Cut_ListStart( &SuperList ); + Cut_Cut_t * pStop0, * pStop1, * pTemp0, * pTemp1, * pStore0, * pStore1; + int i, nCutsOld, Limit; + // start with the elementary cut + if ( fTriv ) + { +// printf( "Creating trivial cut %d.\n", Node ); + pTemp0 = Cut_CutCreateTriv( p, Node ); + Cut_ListAdd( pSuper, pTemp0 ); + p->nNodeCuts++; + } // get the cut lists of children - pList0 = Cut_NodeReadCuts( p, Node0 ); - pList1 = Cut_NodeReadCuts( p, Node1 ); - assert( pList0 && pList1 ); + if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode) ) + return; + + // remember the old number of cuts + nCutsOld = p->nCutsCur; + Limit = p->pParams->nVarsMax; // get the simultation bit of the node p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul); // set temporary variables p->fCompl0 = fCompl0; p->fCompl1 = fCompl1; + // if tree cuts are computed, make sure only the unit cuts propagate over the DAG nodes + if ( TreeCode & 1 ) + { + assert( pList0->nLeaves == 1 ); + pStore0 = pList0->pNext; + pList0->pNext = NULL; + } + if ( TreeCode & 2 ) + { + assert( pList1->nLeaves == 1 ); + pStore1 = pList1->pNext; + pList1->pNext = NULL; + } // find the point in the list where the max-var cuts begin Cut_ListForEachCut( pList0, pStop0 ) if ( pStop0->nLeaves == (unsigned)Limit ) @@ -177,101 +603,54 @@ Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, Cut_ListForEachCut( pList1, pStop1 ) if ( pStop1->nLeaves == (unsigned)Limit ) break; - // start with the elementary cut - pTemp0 = Cut_CutCreateTriv( p, Node ); - Cut_ListAdd( &SuperList, pTemp0 ); - p->nCutsNode = 1; + // small by small Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) - if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) - goto finish; - // all by large - Cut_ListForEachCut( pList0, pTemp0 ) + { + if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) + goto Quits; + } + // small by large + Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) Cut_ListForEachCut( pStop1, pTemp1 ) - if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) - goto finish; - // all by large - Cut_ListForEachCut( pList1, pTemp1 ) + { + if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign ) + continue; + if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) + goto Quits; + } + // small by large + Cut_ListForEachCutStop( pList1, pTemp1, pStop1 ) Cut_ListForEachCut( pStop0, pTemp0 ) - if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) - goto finish; + { + if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign ) + continue; + if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) + goto Quits; + } // large by large Cut_ListForEachCut( pStop0, pTemp0 ) Cut_ListForEachCut( pStop1, pTemp1 ) { assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit ); + if ( pTemp0->uSign != pTemp1->uSign ) + continue; for ( i = 0; i < Limit; i++ ) if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] ) break; if ( i < Limit ) continue; - if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) - goto finish; - } -finish : - // set the list at the node - Vec_PtrFillExtra( p->vCuts, Node + 1, NULL ); - assert( Cut_NodeReadCuts(p, Node) == NULL ); - pList0 = Cut_ListFinish( &SuperList ); - Cut_NodeWriteCuts( p, Node, pList0 ); - // clear the hash table - if ( p->pParams->fHash && !p->pParams->fSeq ) - Cut_TableClear( p->tTable ); - // consider dropping the fanins cuts - if ( p->pParams->fDrop ) - { - Cut_NodeTryDroppingCuts( p, Node0 ); - Cut_NodeTryDroppingCuts( p, Node1 ); - } -p->timeMerge += clock() - clk; - // filter the cuts -clk = clock(); - if ( p->pParams->fFilter ) - Cut_CutFilter( p, pList0 ); -p->timeFilter += clock() - clk; - p->nNodes++; - return pList0; -} - -/**Function************************************************************* - - Synopsis [Processes two cuts.] - - Description [Returns 1 if the limit has been reached.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList ) -{ - Cut_Cut_t * pCut; - // merge the cuts - if ( pCut0->nLeaves >= pCut1->nLeaves ) - pCut = Cut_CutMergeTwo( p, pCut0, pCut1 ); - else - pCut = Cut_CutMergeTwo( p, pCut1, pCut0 ); - if ( pCut == NULL ) - return 0; - assert( pCut->nLeaves > 1 ); - // add the root if sequential - if ( p->pParams->fSeq ) - pCut->pLeaves[pCut->nLeaves] = Root; - // check the lookup table - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); - return 0; - } - // compute the truth table - if ( p->pParams->fTruth ) - Cut_TruthCompute( p, pCut, pCut0, pCut1 ); - // add to the list - Cut_ListAdd( pSuperList, pCut ); - // return status (0 if okay; 1 if exceeded the limit) - return ++p->nCutsNode == p->pParams->nKeepMax; + if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) + goto Quits; + } + if ( p->nNodeCuts == 0 ) + p->nNodesNoCuts++; +Quits: + if ( TreeCode & 1 ) + pList0->pNext = pStore0; + if ( TreeCode & 2 ) + pList1->pNext = pStore1; } /**Function************************************************************* @@ -287,33 +666,32 @@ int Cut_CutProcessTwo( Cut_Man_t * p, int Root, Cut_Cut_t * pCut0, Cut_Cut_t * p ***********************************************************************/ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) { - Cut_List_t SuperList; + Cut_List_t Super, * pSuper = &Super; Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop; int i, k, Node, Root, Limit = p->pParams->nVarsMax; int clk = clock(); - assert( p->pParams->nVarsMax <= 6 ); - // start the new list - Cut_ListStart( &SuperList ); + Cut_ListStart( pSuper ); // remember the root node to save the resulting cuts Root = Vec_IntEntry( vNodes, 0 ); - p->nCutsNode = 1; + p->nNodeCuts = 1; // collect small cuts first Vec_PtrClear( p->vTemp ); Vec_IntForEachEntry( vNodes, Node, i ) { // get the cuts of this node - pList = Cut_NodeReadCuts( p, Node ); - Cut_NodeWriteCuts( p, Node, NULL ); + pList = Cut_NodeReadCutsNew( p, Node ); + Cut_NodeWriteCutsNew( p, Node, NULL ); assert( pList ); // remember the starting point pListStart = pList->pNext; + pList->pNext = NULL; // save or recycle the elementary cut if ( i == 0 ) - Cut_ListAdd( &SuperList, pList ), pTop = pList; + Cut_ListAdd( pSuper, pList ), pTop = pList; else Cut_CutRecycle( p, pList ); // save all the cuts that are smaller than the limit @@ -324,20 +702,19 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) Vec_PtrPush( p->vTemp, pCut ); break; } - // check hash tables - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); + // check containment + if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) continue; - } // set the complemented bit by comparing the first cut with the current cut pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; // add to the list - Cut_ListAdd( &SuperList, pCut ); - if ( ++p->nCutsNode == p->pParams->nKeepMax ) + Cut_ListAdd( pSuper, pCut ); + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts of this node - Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle all cuts of other nodes Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) @@ -349,25 +726,25 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) goto finish; } } - } + } // collect larger cuts next Vec_PtrForEachEntry( p->vTemp, pList, i ) { Cut_ListForEachCutSafe( pList, pCut, pCut2 ) { - if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) - { - Cut_CutRecycle( p, pCut ); + // check containment + if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) continue; - } // set the complemented bit pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; // add to the list - Cut_ListAdd( &SuperList, pCut ); - if ( ++p->nCutsNode == p->pParams->nKeepMax ) + Cut_ListAdd( pSuper, pCut ); + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) { // recycle the rest of the cuts - Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle the saved cuts of other nodes Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 ) @@ -379,97 +756,22 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) } finish : // set the cuts at the node - assert( Cut_NodeReadCuts(p, Root) == NULL ); - pList = Cut_ListFinish( &SuperList ); - Cut_NodeWriteCuts( p, Root, pList ); - // clear the hash table - if ( p->pParams->fHash && !p->pParams->fSeq ) - Cut_TableClear( p->tTable ); + assert( Cut_NodeReadCutsNew(p, Root) == NULL ); + pList = Cut_ListFinish( pSuper ); + Cut_NodeWriteCutsNew( p, Root, pList ); p->timeUnion += clock() - clk; // filter the cuts -clk = clock(); - if ( p->pParams->fFilter ) - Cut_CutFilter( p, pList ); -p->timeFilter += clock() - clk; +//clk = clock(); +// if ( p->pParams->fFilter ) +// Cut_CutFilter( p, pList ); +//p->timeFilter += clock() - clk; p->nNodes -= vNodes->nSize - 1; return pList; } /**Function************************************************************* - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Cut_t * Cut_CutAlloc( Cut_Man_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->fSeq = p->pParams->fSeq; - pCut->fSimul = p->fSimul; - // statistics - p->nCutsAlloc++; - p->nCutsCur++; - if ( p->nCutsPeak < p->nCutsAlloc - p->nCutsDealloc ) - p->nCutsPeak = p->nCutsAlloc - p->nCutsDealloc; - return pCut; -} - -/**Function************************************************************* - - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node ) -{ - Cut_Cut_t * pCut; - pCut = Cut_CutAlloc( p ); - pCut->nLeaves = 1; - pCut->pLeaves[0] = Node; - if ( p->pParams->fTruth ) - Cut_CutWriteTruth( pCut, p->uTruthVars[0] ); - p->nCutsTriv++; - return pCut; -} - -/**Function************************************************************* - - Synopsis [Start the cut computation.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ) -{ - p->nCutsDealloc++; - p->nCutsCur--; - if ( pCut->nLeaves == 1 ) - p->nCutsTriv--; - Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut ); -} - - -/**Function************************************************************* - - Synopsis [Consider dropping cuts if they are useless by now.] + Synopsis [Computes the cuts by unioning cuts at a choice node.] Description [] @@ -478,85 +780,182 @@ void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void Cut_NodeTryDroppingCuts( Cut_Man_t * p, int Node ) +Cut_Cut_t * Cut_NodeUnionCutsSeq( Cut_Man_t * p, Vec_Int_t * vNodes, int CutSetNum, int fFirst ) { - int nFanouts; - assert( p->vFanCounts ); - nFanouts = Vec_IntEntry( p->vFanCounts, Node ); - assert( nFanouts > 0 ); - if ( --nFanouts == 0 ) - Cut_NodeFreeCuts( p, Node ); - Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts ); -} + Cut_List_t Super, * pSuper = &Super; + Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop; + int i, k, Node, Root, Limit = p->pParams->nVarsMax; + int clk = clock(); -/**Function************************************************************* + // start the new list + Cut_ListStart( pSuper ); - Synopsis [Print the cut.] + // remember the root node to save the resulting cuts + Root = Vec_IntEntry( vNodes, 0 ); + p->nNodeCuts = 1; - Description [] - - SideEffects [] + // store the original lists for comparison + p->pCompareOld = Cut_NodeReadCutsOld( p, Root ); + p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL; - SeeAlso [] + // get the topmost cut + pTop = NULL; + if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL ) + pTop = Cut_NodeReadCutsNew( p, Root ); + assert( pTop != NULL ); -***********************************************************************/ -void Cut_CutPrint( Cut_Cut_t * pCut ) -{ - int i; - assert( pCut->nLeaves > 0 ); - printf( "%d : {", pCut->nLeaves ); - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - printf( " %d", pCut->pLeaves[i] ); - printf( " }" ); -} + // collect small cuts first + Vec_PtrClear( p->vTemp ); + Vec_IntForEachEntry( vNodes, Node, i ) + { + // get the cuts of this node + if ( i == 0 && CutSetNum >= 0 ) + { + pList = Cut_NodeReadCutsTemp( p, CutSetNum ); + Cut_NodeWriteCutsTemp( p, CutSetNum, NULL ); + } + else + { + pList = Cut_NodeReadCutsNew( p, Node ); + Cut_NodeWriteCutsNew( p, Node, NULL ); + } + if ( pList == NULL ) + continue; -/**Function************************************************************* + // process the cuts + if ( fFirst ) + { + // remember the starting point + pListStart = pList->pNext; + pList->pNext = NULL; + // save or recycle the elementary cut + if ( i == 0 ) + Cut_ListAdd( pSuper, pList ); + else + Cut_CutRecycle( p, pList ); + } + else + pListStart = pList; - Synopsis [Consider dropping cuts if they are useless by now.] + // save all the cuts that are smaller than the limit + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) + { + if ( pCut->nLeaves == (unsigned)Limit ) + { + Vec_PtrPush( p->vTemp, pCut ); + break; + } + // check containment +// if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) +// continue; + if ( p->pParams->fFilter ) + { + if ( Cut_CutFilterOne(p, pSuper, pCut) ) + continue; + if ( p->pParams->fSeq ) + { + if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) + continue; + if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) + continue; + } + } - Description [] - - SideEffects [] + // set the complemented bit by comparing the first cut with the current cut + pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; + // add to the list + Cut_ListAdd( pSuper, pCut ); + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) + { + // recycle the rest of the cuts of this node + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + // recycle all cuts of other nodes + Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) + Cut_NodeFreeCuts( p, Node ); + // recycle the saved cuts of other nodes + Vec_PtrForEachEntry( p->vTemp, pList, k ) + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + goto finish; + } + } + } + // collect larger cuts next + Vec_PtrForEachEntry( p->vTemp, pList, i ) + { + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + { + // check containment +// if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) +// continue; + if ( p->pParams->fFilter ) + { + if ( Cut_CutFilterOne(p, pSuper, pCut) ) + continue; + if ( p->pParams->fSeq ) + { + if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) ) + continue; + if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) ) + continue; + } + } - SeeAlso [] + // set the complemented bit + pCut->fCompl = pTop->fSimul ^ pCut->fSimul; + pListStart = pCut->pNext; + pCut->pNext = NULL; + // add to the list + Cut_ListAdd( pSuper, pCut ); + if ( ++p->nNodeCuts == p->pParams->nKeepMax ) + { + // recycle the rest of the cuts + Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + // recycle the saved cuts of other nodes + Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 ) + Cut_ListForEachCutSafe( pList, pCut, pCut2 ) + Cut_CutRecycle( p, pCut ); + goto finish; + } + } + } +finish : + // set the cuts at the node + pList = Cut_ListFinish( pSuper ); -***********************************************************************/ -void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) -{ - printf( "\n" ); - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut0->nLeaves, - pCut0->nLeaves > 0 ? pCut0->pLeaves[0] : -1, - pCut0->nLeaves > 1 ? pCut0->pLeaves[1] : -1, - pCut0->nLeaves > 2 ? pCut0->pLeaves[2] : -1, - pCut0->nLeaves > 3 ? pCut0->pLeaves[3] : -1, - pCut0->nLeaves > 4 ? pCut0->pLeaves[4] : -1 - ); - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut1->nLeaves, - pCut1->nLeaves > 0 ? pCut1->pLeaves[0] : -1, - pCut1->nLeaves > 1 ? pCut1->pLeaves[1] : -1, - pCut1->nLeaves > 2 ? pCut1->pLeaves[2] : -1, - pCut1->nLeaves > 3 ? pCut1->pLeaves[3] : -1, - pCut1->nLeaves > 4 ? pCut1->pLeaves[4] : -1 - ); - if ( pCut == NULL ) - printf( "Cannot merge\n" ); + // set the lists at the node +// assert( Cut_NodeReadCutsNew(p, Root) == NULL ); +// Cut_NodeWriteCutsNew( p, Root, pList ); + if ( CutSetNum >= 0 ) + { + assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL ); + Cut_NodeWriteCutsTemp( p, CutSetNum, pList ); + } else - printf( "%d : %5d %5d %5d %5d %5d\n", - pCut->nLeaves, - pCut->nLeaves > 0 ? pCut->pLeaves[0] : -1, - pCut->nLeaves > 1 ? pCut->pLeaves[1] : -1, - pCut->nLeaves > 2 ? pCut->pLeaves[2] : -1, - pCut->nLeaves > 3 ? pCut->pLeaves[3] : -1, - pCut->nLeaves > 4 ? pCut->pLeaves[4] : -1 - ); + { + assert( Cut_NodeReadCutsNew(p, Root) == NULL ); + Cut_NodeWriteCutsNew( p, Root, pList ); + } + +p->timeUnion += clock() - clk; + // filter the cuts +//clk = clock(); +// if ( p->pParams->fFilter ) +// Cut_CutFilter( p, pList ); +//p->timeFilter += clock() - clk; +// if ( fFirst ) +// p->nNodes -= vNodes->nSize - 1; + return pList; } /**Function************************************************************* - Synopsis [Filter the cuts using dominance.] + Synopsis [Verifies that the list contains only non-dominated cuts.] Description [] @@ -565,62 +964,27 @@ void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) SeeAlso [] ***********************************************************************/ -void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) +int Cut_CutListVerify( Cut_Cut_t * pList ) { - Cut_Cut_t * pListR, ** ppListR = &pListR; - Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev; - int i, k; - // save the first cut - *ppListR = pList, ppListR = &pList->pNext; - // try to filter out other cuts - pPrev = pList; - Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 ) + Cut_Cut_t * pCut, * pDom; + Cut_ListForEachCut( pList, pCut ) { - assert( pCut->nLeaves > 1 ); - // go through all the previous cuts up to pCut - Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) + Cut_ListForEachCutStop( pList, pDom, pCut ) { - if ( pDom->nLeaves >= pCut->nLeaves ) - continue; - // check if every node in pDom is contained in pCut - for ( i = 0; i < (int)pDom->nLeaves; i++ ) + if ( Cut_CutCheckDominance( pDom, pCut ) ) { - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) - break; - if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut - break; + int x = 0; + printf( "******************* These are contained cuts:\n" ); + Cut_CutPrint( pDom, 1 ); + Cut_CutPrint( pDom, 1 ); + + return 0; } - if ( i == (int)pDom->nLeaves ) // every node in pDom is contained in pCut - break; - } - if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut - { - // make sure cuts are connected after removing - pPrev->pNext = pCut->pNext; -/* - // report - printf( "Recycling cut: " ); - Cut_CutPrint( pCut ); - printf( "\n" ); - printf( "As contained in: " ); - Cut_CutPrint( pDom ); - printf( "\n" ); -*/ - // recycle the cut - Cut_CutRecycle( p, pCut ); - } - else // pDom is NOT contained in pCut - save pCut - { - *ppListR = pCut, ppListR = &pCut->pNext; - pPrev = pCut; } } - *ppListR = NULL; + return 1; } - - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/cut/cutOracle.c b/src/opt/cut/cutOracle.c new file mode 100644 index 00000000..3eb4462b --- /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 DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**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 ); + 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_TruthComputeOld( 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 /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutPre22.c b/src/opt/cut/cutPre22.c new file mode 100644 index 00000000..5cb87a9c --- /dev/null +++ b/src/opt/cut/cutPre22.c @@ -0,0 +1,988 @@ +/**CFile**************************************************************** + + FileName [cutPre22.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Network and node package.] + + Synopsis [Precomputes truth tables for the 2x2 macro cell.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: cutPre22.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "cutInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define CUT_CELL_MVAR 9 + +typedef struct Cut_Cell_t_ Cut_Cell_t; +typedef struct Cut_CMan_t_ Cut_CMan_t; + +struct Cut_Cell_t_ +{ + Cut_Cell_t * pNext; // pointer to the next cell in the table + Cut_Cell_t * pNextVar; // pointer to the next cell of this support size + Cut_Cell_t * pParent; // pointer to the cell used to derive this one + int nUsed; // the number of times the cell is used + char Box[4]; // functions in the boxes + unsigned nVars : 4; // the number of variables + unsigned CrossBar0 : 4; // the variable set equal + unsigned CrossBar1 : 4; // the variable set equal + unsigned CrossBarPhase : 2; // the phase of the cross bar (0, 1, or 2) + unsigned CanonPhase : 18; // the canonical phase + char CanonPerm[CUT_CELL_MVAR+3]; // semicanonical permutation + short Store[2*CUT_CELL_MVAR]; // minterm counts in the cofactors + unsigned uTruth[1<<(CUT_CELL_MVAR-5)]; // the current truth table +}; + +struct Cut_CMan_t_ +{ + // storage for canonical cells + Extra_MmFixed_t * pMem; + st_table * tTable; + Cut_Cell_t * pSameVar[CUT_CELL_MVAR+1]; + // elementary truth tables + unsigned uInputs[CUT_CELL_MVAR][1<<(CUT_CELL_MVAR-5)]; + // temporary truth tables + unsigned uTemp1[22][1<<(CUT_CELL_MVAR-5)]; + unsigned uTemp2[22][1<<(CUT_CELL_MVAR-5)]; + unsigned uTemp3[22][1<<(CUT_CELL_MVAR-5)]; + unsigned uFinal[1<<(CUT_CELL_MVAR-5)]; + unsigned puAux[1<<(CUT_CELL_MVAR-5)]; + // statistical variables + int nTotal; + int nGood; + int nVarCounts[CUT_CELL_MVAR+1]; + int nSymGroups[CUT_CELL_MVAR+1]; + int nSymGroupsE[CUT_CELL_MVAR+1]; + int timeCanon; + int timeSupp; + int timeTable; + int nCellFound; + int nCellNotFound; +}; + +// NP-classes of functions of 3 variables (22) +static char * s_NP3[22] = { + " 0\n", // 00 const 0 // 0 vars + " 1\n", // 01 const 1 // 0 vars + "1 1\n", // 02 a // 1 vars + "11 1\n", // 03 ab // 2 vars + "11 0\n", // 04 (ab)' // 2 vars + "10 1\n01 1\n", // 05 a<+>b // 2 vars + "111 1\n", // 06 0s abc // 3 vars + "111 0\n", // 07 (abc)' // + "11- 1\n1-1 1\n", // 08 1p a(b+c) // + "11- 0\n1-1 0\n", // 09 (a(b+c))' // + "111 1\n100 1\n010 1\n001 1\n", // 10 2s a<+>b<+>c // + "10- 0\n1-0 0\n011 0\n", // 11 3p a<+>bc // + "101 1\n110 1\n", // 12 4p a(b<+>c) // + "101 0\n110 0\n", // 13 (a(b<+>c))' // + "11- 1\n1-1 1\n-11 1\n", // 14 5s ab+bc+ac // + "111 1\n000 1\n", // 15 6s abc+a'b'c' // + "111 0\n000 0\n", // 16 (abc+a'b'c')' // + "11- 1\n-11 1\n0-1 1\n", // 17 7 ab+bc+a'c // + "011 1\n101 1\n110 1\n", // 18 8s a'bc+ab'c+abc' // + "011 0\n101 0\n110 0\n", // 19 (a'bc+ab'c+abc')' // + "100 1\n-11 1\n", // 20 9p ab'c'+bc // + "100 0\n-11 0\n" // 21 (ab'c'+bc)' // +}; + +// NP-classes of functions of 3 variables (22) +static char * s_NP3Names[22] = { + " const 0 ", + " const 1 ", + " a ", + " ab ", + " (ab)' ", + " a<+>b ", + "0s abc ", + " (abc)' ", + "1p a(b+c) ", + " (a(b+c))' ", + "2s a<+>b<+>c ", + "3p a<+>bc ", + "4p a(b<+>c) ", + " (a(b<+>c))' ", + "5s ab+bc+ac ", + "6s abc+a'b'c' ", + " (abc+a'b'c')' ", + "7 ab+bc+a'c ", + "8s a'bc+ab'c+abc' ", + " (a'bc+ab'c+abc')' ", + "9p ab'c'+bc ", + " (ab'c'+bc)' " +}; + +// the number of variables in each function +static int s_NP3VarNums[22] = { 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }; + +// NPN classes of functions of exactly 3 inputs (10) +static int s_NPNe3[10] = { 6, 8, 10, 11, 12, 14, 15, 17, 18, 20 }; + +// NPN classes of functions of exactly 3 inputs that are symmetric (5) +static int s_NPNe3s[10] = { 6, 10, 14, 15, 18 }; + +// NPN classes of functions of exactly 3 inputs (4) +static int s_NPNe3p[10] = { 8, 11, 12, 20 }; + +static Cut_CMan_t * Cut_CManStart(); +static void Cut_CManStop( Cut_CMan_t * p ); +static void Cut_CellTruthElem( unsigned * InA, unsigned * InB, unsigned * InC, unsigned * pOut, int nVars, int Type ); +static void Cut_CellCanonicize( Cut_CMan_t * p, Cut_Cell_t * pCell ); +static int Cut_CellTableLookup( Cut_CMan_t * p, Cut_Cell_t * pCell ); +static void Cut_CellSuppMin( Cut_Cell_t * pCell ); +static void Cut_CellCrossBar( Cut_Cell_t * pCell ); + + +static Cut_CMan_t * s_pCMan = NULL; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Start the precomputation manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellLoad() +{ + FILE * pFile; + char * pFileName = "cells22_daomap_iwls.txt"; + char pString[1000]; + Cut_CMan_t * p; + Cut_Cell_t * pCell; + int Length; //, i; + pFile = fopen( pFileName, "r" ); + if ( pFile == NULL ) + { + printf( "Cannot open file \"%s\".\n", pFileName ); + return; + } + // start the manager + p = Cut_CManStart(); + // load truth tables + while ( fgets(pString, 1000, pFile) ) + { + Length = strlen(pString); + pString[Length--] = 0; + if ( Length == 0 ) + continue; + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = Extra_Base2Log(Length*4); + pCell->nUsed = 1; +// Extra_TruthCopy( pCell->uTruth, pTruth, nVars ); + Extra_ReadHexadecimal( pCell->uTruth, pString, pCell->nVars ); + Cut_CellSuppMin( pCell ); +/* + // set the elementary permutation + for ( i = 0; i < (int)pCell->nVars; i++ ) + pCell->CanonPerm[i] = i; + // canonicize + pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store ); +*/ + // add to the table + p->nTotal++; + +// Extra_PrintHexadecimal( stdout, pCell->uTruth, pCell->nVars ); printf( "\n" ); +// if ( p->nTotal == 500 ) +// break; + + if ( !Cut_CellTableLookup( p, pCell ) ) // new cell + p->nGood++; + } + printf( "Read %d cells from file \"%s\". Added %d cells to the table.\n", p->nTotal, pFileName, p->nGood ); + fclose( pFile ); +// return p; +} + +/**Function************************************************************* + + Synopsis [Precomputes truth tables for the 2x2 macro cell.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellPrecompute() +{ + Cut_CMan_t * p; + Cut_Cell_t * pCell, * pTemp; + int i1, i2, i3, i, j, k, c, clk = clock(), clk2 = clock(); + + p = Cut_CManStart(); + + // precompute truth tables + for ( i = 0; i < 22; i++ ) + Cut_CellTruthElem( p->uInputs[0], p->uInputs[1], p->uInputs[2], p->uTemp1[i], 9, i ); + for ( i = 0; i < 22; i++ ) + Cut_CellTruthElem( p->uInputs[3], p->uInputs[4], p->uInputs[5], p->uTemp2[i], 9, i ); + for ( i = 0; i < 22; i++ ) + Cut_CellTruthElem( p->uInputs[6], p->uInputs[7], p->uInputs[8], p->uTemp3[i], 9, i ); +/* + if ( k == 8 && ((i1 == 6 && i2 == 14 && i3 == 20) || (i1 == 20 && i2 == 6 && i3 == 14)) ) + { + Extra_PrintBinary( stdout, &pCell->CanonPhase, pCell->nVars+1 ); printf( " : " ); + for ( i = 0; i < pCell->nVars; i++ ) + printf( "%d=%d/%d ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] ); + Extra_PrintHexadecimal( stdout, pCell->uTruth, pCell->nVars ); + printf( "\n" ); + } +*/ +/* + // go through symmetric roots + for ( k = 0; k < 5; k++ ) + for ( i1 = 0; i1 < 22; i1++ ) + for ( i2 = i1; i2 < 22; i2++ ) + for ( i3 = i2; i3 < 22; i3++ ) + { + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = 9; + pCell->Box[0] = s_NPNe3s[k]; + pCell->Box[1] = i1; + pCell->Box[2] = i2; + pCell->Box[3] = i3; + // fill in the truth table + Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3s[k] ); + // canonicize + Cut_CellCanonicize( pCell ); + + // add to the table + p->nTotal++; + if ( Cut_CellTableLookup( p, pCell ) ) // already exists + Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell ); + else + p->nGood++; + } + + // go through partially symmetric roots + for ( k = 0; k < 4; k++ ) + for ( i1 = 0; i1 < 22; i1++ ) + for ( i2 = 0; i2 < 22; i2++ ) + for ( i3 = i2; i3 < 22; i3++ ) + { + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = 9; + pCell->Box[0] = s_NPNe3p[k]; + pCell->Box[1] = i1; + pCell->Box[2] = i2; + pCell->Box[3] = i3; + // fill in the truth table + Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3p[k] ); + // canonicize + Cut_CellCanonicize( pCell ); + + // add to the table + p->nTotal++; + if ( Cut_CellTableLookup( p, pCell ) ) // already exists + Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell ); + else + p->nGood++; + } + + // go through non-symmetric functions + for ( i1 = 0; i1 < 22; i1++ ) + for ( i2 = 0; i2 < 22; i2++ ) + for ( i3 = 0; i3 < 22; i3++ ) + { + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = 9; + pCell->Box[0] = 17; + pCell->Box[1] = i1; + pCell->Box[2] = i2; + pCell->Box[3] = i3; + // fill in the truth table + Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, 17 ); + // canonicize + Cut_CellCanonicize( pCell ); + + // add to the table + p->nTotal++; + if ( Cut_CellTableLookup( p, pCell ) ) // already exists + Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell ); + else + p->nGood++; + } +*/ + + // go through non-symmetric functions + for ( k = 0; k < 10; k++ ) + for ( i1 = 0; i1 < 22; i1++ ) + for ( i2 = 0; i2 < 22; i2++ ) + for ( i3 = 0; i3 < 22; i3++ ) + { + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = 9; + pCell->Box[0] = s_NPNe3[k]; + pCell->Box[1] = i1; + pCell->Box[2] = i2; + pCell->Box[3] = i3; + // set the elementary permutation + for ( i = 0; i < (int)pCell->nVars; i++ ) + pCell->CanonPerm[i] = i; + // fill in the truth table + Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3[k] ); + // minimize the support + Cut_CellSuppMin( pCell ); + + // canonicize + pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store ); + + // add to the table + p->nTotal++; + if ( Cut_CellTableLookup( p, pCell ) ) // already exists + Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell ); + else + { + p->nGood++; + p->nVarCounts[pCell->nVars]++; + + if ( pCell->nVars ) + for ( i = 0; i < (int)pCell->nVars-1; i++ ) + { + if ( pCell->Store[2*i] != pCell->Store[2*(i+1)] ) // i and i+1 cannot be symmetric + continue; + // i and i+1 can be symmetric + // find the end of this group + for ( j = i+1; j < (int)pCell->nVars; j++ ) + if ( pCell->Store[2*i] != pCell->Store[2*j] ) + break; + + if ( pCell->Store[2*i] == pCell->Store[2*i+1] ) + p->nSymGroupsE[j-i]++; + else + p->nSymGroups[j-i]++; + i = j - 1; + } +/* + if ( pCell->nVars == 3 ) + { + Extra_PrintBinary( stdout, pCell->uTruth, 32 ); printf( "\n" ); + for ( i = 0; i < (int)pCell->nVars; i++ ) + printf( "%d=%d/%d ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] ); + printf( "\n" ); + } +*/ + } + } + + printf( "BASIC: Total = %d. Good = %d. Entry = %d. ", p->nTotal, p->nGood, sizeof(Cut_Cell_t) ); + PRT( "Time", clock() - clk ); + printf( "Cells: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nVarCounts[i] ); + printf( "\nDiffs: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nSymGroups[i] ); + printf( "\nEquals: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nSymGroupsE[i] ); + printf( "\n" ); + + // continue adding new cells using support + for ( k = CUT_CELL_MVAR; k > 3; k-- ) + { + for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar ) + for ( i1 = 0; i1 < k; i1++ ) + for ( i2 = i1+1; i2 < k; i2++ ) + for ( c = 0; c < 3; c++ ) + { + // derive the cell + pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem ); + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = pTemp->nVars; + pCell->pParent = pTemp; + // set the elementary permutation + for ( i = 0; i < (int)pCell->nVars; i++ ) + pCell->CanonPerm[i] = i; + // fill in the truth table + Extra_TruthCopy( pCell->uTruth, pTemp->uTruth, pTemp->nVars ); + // create the cross-bar + pCell->CrossBar0 = i1; + pCell->CrossBar1 = i2; + pCell->CrossBarPhase = c; + Cut_CellCrossBar( pCell ); + // minimize the support +//clk2 = clock(); + Cut_CellSuppMin( pCell ); +//p->timeSupp += clock() - clk2; + // canonicize +//clk2 = clock(); + pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store ); +//p->timeCanon += clock() - clk2; + + // add to the table +//clk2 = clock(); + p->nTotal++; + if ( Cut_CellTableLookup( p, pCell ) ) // already exists + Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell ); + else + { + p->nGood++; + p->nVarCounts[pCell->nVars]++; + + for ( i = 0; i < (int)pCell->nVars-1; i++ ) + { + if ( pCell->Store[2*i] != pCell->Store[2*(i+1)] ) // i and i+1 cannot be symmetric + continue; + // i and i+1 can be symmetric + // find the end of this group + for ( j = i+1; j < (int)pCell->nVars; j++ ) + if ( pCell->Store[2*i] != pCell->Store[2*j] ) + break; + + if ( pCell->Store[2*i] == pCell->Store[2*i+1] ) + p->nSymGroupsE[j-i]++; + else + p->nSymGroups[j-i]++; + i = j - 1; + } +/* + if ( pCell->nVars == 3 ) + { + Extra_PrintBinary( stdout, pCell->uTruth, 32 ); printf( "\n" ); + for ( i = 0; i < (int)pCell->nVars; i++ ) + printf( "%d=%d/%d ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] ); + printf( "\n" ); + } +*/ + } +//p->timeTable += clock() - clk2; + } + + printf( "VAR %d: Total = %d. Good = %d. Entry = %d. ", k, p->nTotal, p->nGood, sizeof(Cut_Cell_t) ); + PRT( "Time", clock() - clk ); + printf( "Cells: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nVarCounts[i] ); + printf( "\nDiffs: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nSymGroups[i] ); + printf( "\nEquals: " ); + for ( i = 0; i <= 9; i++ ) + printf( "%d=%d ", i, p->nSymGroupsE[i] ); + printf( "\n" ); + } +// printf( "\n" ); + PRT( "Supp ", p->timeSupp ); + PRT( "Canon", p->timeCanon ); + PRT( "Table", p->timeTable ); +// Cut_CManStop( p ); +} + +/**Function************************************************************* + + Synopsis [Check the table.] + + Description [Returns 1 if such a truth table already exists.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_CellTableLookup( Cut_CMan_t * p, Cut_Cell_t * pCell ) +{ + Cut_Cell_t ** pSlot, * pTemp; + unsigned Hash; + Hash = Extra_TruthHash( pCell->uTruth, Extra_TruthWordNum( pCell->nVars ) ); + if ( !st_find_or_add( p->tTable, (char *)Hash, (char ***)&pSlot ) ) + *pSlot = NULL; + for ( pTemp = *pSlot; pTemp; pTemp = pTemp->pNext ) + { + if ( pTemp->nVars != pCell->nVars ) + continue; + if ( Extra_TruthIsEqual(pTemp->uTruth, pCell->uTruth, pCell->nVars) ) + return 1; + } + // the entry is new + pCell->pNext = *pSlot; + *pSlot = pCell; + // add it to the variable support list + pCell->pNextVar = p->pSameVar[pCell->nVars]; + p->pSameVar[pCell->nVars] = pCell; + return 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellSuppMin( Cut_Cell_t * pCell ) +{ + static unsigned uTemp[1<<(CUT_CELL_MVAR-5)]; + unsigned * pIn, * pOut, * pTemp; + int i, k, Counter, Temp; + + // go backward through the support variables and remove redundant + for ( k = pCell->nVars - 1; k >= 0; k-- ) + if ( !Extra_TruthVarInSupport(pCell->uTruth, pCell->nVars, k) ) + { + // shift all the variables above this one + Counter = 0; + pIn = pCell->uTruth; pOut = uTemp; + for ( i = k; i < (int)pCell->nVars - 1; i++ ) + { + Extra_TruthSwapAdjacentVars( pOut, pIn, pCell->nVars, i ); + pTemp = pIn; pIn = pOut; pOut = pTemp; + // swap the support vars + Temp = pCell->CanonPerm[i]; + pCell->CanonPerm[i] = pCell->CanonPerm[i+1]; + pCell->CanonPerm[i+1] = Temp; + Counter++; + } + // return the function back into its place + if ( Counter & 1 ) + Extra_TruthCopy( pOut, pIn, pCell->nVars ); + // remove one variable + pCell->nVars--; +// Extra_PrintBinary( stdout, pCell->uTruth, (1<<pCell->nVars) ); printf( "\n" ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellCrossBar( Cut_Cell_t * pCell ) +{ + static unsigned uTemp0[1<<(CUT_CELL_MVAR-5)]; + static unsigned uTemp1[1<<(CUT_CELL_MVAR-5)]; + Extra_TruthCopy( uTemp0, pCell->uTruth, pCell->nVars ); + Extra_TruthCopy( uTemp1, pCell->uTruth, pCell->nVars ); + if ( pCell->CanonPhase == 0 ) + { + Extra_TruthCofactor0( uTemp0, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor0( uTemp0, pCell->nVars, pCell->CrossBar1 ); + Extra_TruthCofactor1( uTemp1, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor1( uTemp1, pCell->nVars, pCell->CrossBar1 ); + } + else if ( pCell->CanonPhase == 1 ) + { + Extra_TruthCofactor1( uTemp0, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor0( uTemp0, pCell->nVars, pCell->CrossBar1 ); + Extra_TruthCofactor0( uTemp1, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor1( uTemp1, pCell->nVars, pCell->CrossBar1 ); + } + else if ( pCell->CanonPhase == 2 ) + { + Extra_TruthCofactor0( uTemp0, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor1( uTemp0, pCell->nVars, pCell->CrossBar1 ); + Extra_TruthCofactor1( uTemp1, pCell->nVars, pCell->CrossBar0 ); + Extra_TruthCofactor0( uTemp1, pCell->nVars, pCell->CrossBar1 ); + } + else assert( 0 ); + Extra_TruthMux( pCell->uTruth, uTemp0, uTemp1, pCell->nVars, pCell->CrossBar0 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellTruthElem( unsigned * InA, unsigned * InB, unsigned * InC, unsigned * pOut, int nVars, int Type ) +{ + int nWords = Extra_TruthWordNum( nVars ); + int i; + + assert( Type < 22 ); + switch ( Type ) + { + // " 0\n", // 00 const 0 + case 0: + for ( i = 0; i < nWords; i++ ) + pOut[i] = 0; + return; + // " 1\n", // 01 const 1 + case 1: + for ( i = 0; i < nWords; i++ ) + pOut[i] = 0xFFFFFFFF; + return; + // "1 1\n", // 02 a + case 2: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i]; + return; + // "11 1\n", // 03 ab + case 3: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] & InB[i]; + return; + // "11 0\n", // 04 (ab)' + case 4: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~(InA[i] & InB[i]); + return; + // "10 1\n01 1\n", // 05 a<+>b + case 5: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] ^ InB[i]; + return; + // "111 1\n", // 06 + abc + case 6: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] & InB[i] & InC[i]; + return; + // "111 0\n", // 07 (abc)' + case 7: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~(InA[i] & InB[i] & InC[i]); + return; + // "11- 1\n1-1 1\n", // 08 + a(b+c) + case 8: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] & (InB[i] | InC[i]); + return; + // "11- 0\n1-1 0\n", // 09 (a(b+c))' + case 9: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~(InA[i] & (InB[i] | InC[i])); + return; + // "111 1\n100 1\n010 1\n001 1\n", // 10 + a<+>b<+>c + case 10: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] ^ InB[i] ^ InC[i]; + return; + // "10- 0\n1-0 0\n011 0\n", // 11 + a<+>bc + case 11: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] ^ (InB[i] & InC[i]); + return; + // "101 1\n110 1\n", // 12 + a(b<+>c) + case 12: + for ( i = 0; i < nWords; i++ ) + pOut[i] = InA[i] & (InB[i] ^ InC[i]); + return; + // "101 0\n110 0\n", // 13 (a(b<+>c))' + case 13: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~(InA[i] & (InB[i] ^ InC[i])); + return; + // "11- 1\n1-1 1\n-11 1\n", // 14 + ab+bc+ac + case 14: + for ( i = 0; i < nWords; i++ ) + pOut[i] = (InA[i] & InB[i]) | (InB[i] & InC[i]) | (InA[i] & InC[i]); + return; + // "111 1\n000 1\n", // 15 + abc+a'b'c' + case 15: + for ( i = 0; i < nWords; i++ ) + pOut[i] = (InA[i] & InB[i] & InC[i]) | (~InA[i] & ~InB[i] & ~InC[i]); + return; + // "111 0\n000 0\n", // 16 (abc+a'b'c')' + case 16: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~((InA[i] & InB[i] & InC[i]) | (~InA[i] & ~InB[i] & ~InC[i])); + return; + // "11- 1\n-11 1\n0-1 1\n", // 17 + ab+bc+a'c + case 17: + for ( i = 0; i < nWords; i++ ) + pOut[i] = (InA[i] & InB[i]) | (InB[i] & InC[i]) | (~InA[i] & InC[i]); + return; + // "011 1\n101 1\n110 1\n", // 18 + a'bc+ab'c+abc' + case 18: + for ( i = 0; i < nWords; i++ ) + pOut[i] = (~InA[i] & InB[i] & InC[i]) | (InA[i] & ~InB[i] & InC[i]) | (InA[i] & InB[i] & ~InC[i]); + return; + // "011 0\n101 0\n110 0\n", // 19 (a'bc+ab'c+abc')' + case 19: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~((~InA[i] & InB[i] & InC[i]) | (InA[i] & ~InB[i] & InC[i]) | (InA[i] & InB[i] & ~InC[i])); + return; + // "100 1\n-11 1\n", // 20 + ab'c'+bc + case 20: + for ( i = 0; i < nWords; i++ ) + pOut[i] = (InA[i] & ~InB[i] & ~InC[i]) | (InB[i] & InC[i]); + return; + // "100 0\n-11 0\n" // 21 (ab'c'+bc)' + case 21: + for ( i = 0; i < nWords; i++ ) + pOut[i] = ~((InA[i] & ~InB[i] & ~InC[i]) | (InB[i] & InC[i])); + return; + } +} + + +/**Function************************************************************* + + Synopsis [Start the precomputation manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Cut_CMan_t * Cut_CManStart() +{ + Cut_CMan_t * p; + int i, k; + // start the manager + assert( sizeof(unsigned) == 4 ); + p = ALLOC( Cut_CMan_t, 1 ); + memset( p, 0, sizeof(Cut_CMan_t) ); + // start the table and the memory manager + p->tTable = st_init_table(st_ptrcmp,st_ptrhash); + p->pMem = Extra_MmFixedStart( sizeof(Cut_Cell_t) ); + // set elementary truth tables + for ( k = 0; k < CUT_CELL_MVAR; k++ ) + for ( i = 0; i < (1<<CUT_CELL_MVAR); i++ ) + if ( i & (1 << k) ) + p->uInputs[k][i>>5] |= (1 << (i&31)); + s_pCMan = p; + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CManStop( Cut_CMan_t * p ) +{ + st_free_table( p->tTable ); + Extra_MmFixedStop( p->pMem ); + free( p ); +} +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_CellIsRunning() +{ + return s_pCMan != NULL; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_CellDumpToFile() +{ + FILE * pFile; + Cut_CMan_t * p = s_pCMan; + Cut_Cell_t * pTemp; + char * pFileName = "celllib22.txt"; + int NumUsed[10][5] = {{0}}; + int BoxUsed[22][5] = {{0}}; + int i, k, Counter; + int clk = clock(); + + if ( p == NULL ) + { + printf( "Cut_CellDumpToFile: Cell manager is not defined.\n" ); + return; + } + + // count the number of cells used + for ( k = CUT_CELL_MVAR; k >= 0; k-- ) + { + for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar ) + { + if ( pTemp->nUsed == 0 ) + NumUsed[k][0]++; + else if ( pTemp->nUsed < 10 ) + NumUsed[k][1]++; + else if ( pTemp->nUsed < 100 ) + NumUsed[k][2]++; + else if ( pTemp->nUsed < 1000 ) + NumUsed[k][3]++; + else + NumUsed[k][4]++; + + for ( i = 0; i < 4; i++ ) + if ( pTemp->nUsed == 0 ) + BoxUsed[ pTemp->Box[i] ][0]++; + else if ( pTemp->nUsed < 10 ) + BoxUsed[ pTemp->Box[i] ][1]++; + else if ( pTemp->nUsed < 100 ) + BoxUsed[ pTemp->Box[i] ][2]++; + else if ( pTemp->nUsed < 1000 ) + BoxUsed[ pTemp->Box[i] ][3]++; + else + BoxUsed[ pTemp->Box[i] ][4]++; + } + } + + printf( "Functions found = %10d. Functions not found = %10d.\n", p->nCellFound, p->nCellNotFound ); + for ( k = 0; k <= CUT_CELL_MVAR; k++ ) + { + printf( "%3d : ", k ); + for ( i = 0; i < 5; i++ ) + printf( "%8d ", NumUsed[k][i] ); + printf( "\n" ); + } + printf( "Box usage:\n" ); + for ( k = 0; k < 22; k++ ) + { + printf( "%3d : ", k ); + for ( i = 0; i < 5; i++ ) + printf( "%8d ", BoxUsed[k][i] ); + printf( " %s", s_NP3Names[k] ); + printf( "\n" ); + } + + pFile = fopen( pFileName, "w" ); + if ( pFile == NULL ) + { + printf( "Cut_CellDumpToFile: Cannout open output file.\n" ); + return; + } + + Counter = 0; + for ( k = 0; k <= CUT_CELL_MVAR; k++ ) + { + for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar ) + if ( pTemp->nUsed > 0 ) + { + Extra_PrintHexadecimal( pFile, pTemp->uTruth, (k <= 5? 5 : k) ); + fprintf( pFile, "\n" ); + Counter++; + } + fprintf( pFile, "\n" ); + } + fclose( pFile ); + + printf( "Library composed of %d functions is written into file \"%s\". ", Counter, pFileName ); + + PRT( "Time", clock() - clk ); +} + + +/**Function************************************************************* + + Synopsis [Looks up if the given function exists in the hash table.] + + Description [If the function exists, returns 1, meaning that it can be + implemented using two levels of 3-input LUTs. If the function does not + exist, return 0.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_CellTruthLookup( unsigned * pTruth, int nVars ) +{ + Cut_CMan_t * p = s_pCMan; + Cut_Cell_t * pTemp; + Cut_Cell_t Cell, * pCell = &Cell; + unsigned Hash; + int i; + + // cell manager is not defined + if ( p == NULL ) + { + printf( "Cut_CellTruthLookup: Cell manager is not defined.\n" ); + return 0; + } + + // canonicize + memset( pCell, 0, sizeof(Cut_Cell_t) ); + pCell->nVars = nVars; + Extra_TruthCopy( pCell->uTruth, pTruth, nVars ); + Cut_CellSuppMin( pCell ); + // set the elementary permutation + for ( i = 0; i < (int)pCell->nVars; i++ ) + pCell->CanonPerm[i] = i; + // canonicize + pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store ); + + + // check if the cell exists + Hash = Extra_TruthHash( pCell->uTruth, Extra_TruthWordNum(pCell->nVars) ); + if ( st_lookup( p->tTable, (char *)Hash, (char **)&pTemp ) ) + { + for ( ; pTemp; pTemp = pTemp->pNext ) + { + if ( pTemp->nVars != pCell->nVars ) + continue; + if ( Extra_TruthIsEqual(pTemp->uTruth, pCell->uTruth, pCell->nVars) ) + { + pTemp->nUsed++; + p->nCellFound++; + return 1; + } + } + } + p->nCellNotFound++; + return 0; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/cut/cutSeq.c b/src/opt/cut/cutSeq.c index 869bd7b3..d36f94f7 100644 --- a/src/opt/cut/cutSeq.c +++ b/src/opt/cut/cutSeq.c @@ -25,12 +25,12 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [] + Synopsis [Shifts all cut leaves of the node by the given number of latches.] Description [] @@ -39,6 +39,186 @@ SeeAlso [] ***********************************************************************/ +static inline void Cut_NodeShiftCutLeaves( Cut_Cut_t * pList, int nLat ) +{ + Cut_Cut_t * pTemp; + int i; + // shift the cuts by as many latches + Cut_ListForEachCut( pList, pTemp ) + { + pTemp->uSign = 0; + for ( i = 0; i < (int)pTemp->nLeaves; i++ ) + { + pTemp->pLeaves[i] += nLat; + pTemp->uSign |= Cut_NodeSign( pTemp->pLeaves[i] ); + } + } +} + +/**Function************************************************************* + + Synopsis [Computes sequential cuts for the node from its fanins.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeComputeCutsSeq( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int nLat0, int nLat1, int fTriv, int CutSetNum ) +{ + Cut_List_t Super, * pSuper = &Super; + Cut_Cut_t * pListNew; + int clk; + + // get the number of cuts at the node + p->nNodeCuts = Cut_CutCountList( Cut_NodeReadCutsOld(p, Node) ); + if ( p->nNodeCuts >= p->pParams->nKeepMax ) + return; + + // count only the first visit + if ( p->nNodeCuts == 0 ) + p->nNodes++; + + // store the fanin lists + p->pStore0[0] = Cut_NodeReadCutsOld( p, Node0 ); + p->pStore0[1] = Cut_NodeReadCutsNew( p, Node0 ); + p->pStore1[0] = Cut_NodeReadCutsOld( p, Node1 ); + p->pStore1[1] = Cut_NodeReadCutsNew( p, Node1 ); + + // duplicate the cut lists if fanin nodes are non-standard + if ( Node == Node0 || Node == Node1 || Node0 == Node1 ) + { + p->pStore0[0] = Cut_CutDupList( p, p->pStore0[0] ); + p->pStore0[1] = Cut_CutDupList( p, p->pStore0[1] ); + p->pStore1[0] = Cut_CutDupList( p, p->pStore1[0] ); + p->pStore1[1] = Cut_CutDupList( p, p->pStore1[1] ); + } + + // shift the cuts by as many latches and recompute signatures + if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[0], nLat0 ); + if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[1], nLat0 ); + if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[0], nLat1 ); + if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[1], nLat1 ); + + // store the original lists for comparison + p->pCompareOld = Cut_NodeReadCutsOld( p, Node ); + p->pCompareNew = Cut_NodeReadCutsNew( p, Node ); + + // merge the old and the new +clk = clock(); + Cut_ListStart( pSuper ); + Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[0], p->pStore1[1], 0, 0 ); + Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[1], p->pStore1[0], 0, 0 ); + Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[1], p->pStore1[1], fTriv, 0 ); + pListNew = Cut_ListFinish( pSuper ); +p->timeMerge += clock() - clk; + + // shift the cuts by as many latches and recompute signatures + if ( Node == Node0 || Node == Node1 || Node0 == Node1 ) + { + Cut_CutRecycleList( p, p->pStore0[0] ); + Cut_CutRecycleList( p, p->pStore0[1] ); + Cut_CutRecycleList( p, p->pStore1[0] ); + Cut_CutRecycleList( p, p->pStore1[1] ); + } + else + { + if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[0], -nLat0 ); + if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[1], -nLat0 ); + if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[0], -nLat1 ); + if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[1], -nLat1 ); + } + + // set the lists at the node + if ( CutSetNum >= 0 ) + { + assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL ); + Cut_NodeWriteCutsTemp( p, CutSetNum, pListNew ); + } + else + { + assert( Cut_NodeReadCutsNew(p, Node) == NULL ); + Cut_NodeWriteCutsNew( p, Node, pListNew ); + } + + // mark the node if we exceeded the number of cuts + if ( p->nNodeCuts >= p->pParams->nKeepMax ) + p->nCutsLimit++; +} + +/**Function************************************************************* + + Synopsis [Merges the new cuts with the old cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeNewMergeWithOld( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pListOld, * pListNew, * pList; + // get the new cuts + pListNew = Cut_NodeReadCutsNew( p, Node ); + if ( pListNew == NULL ) + return; + Cut_NodeWriteCutsNew( p, Node, NULL ); + // get the old cuts + pListOld = Cut_NodeReadCutsOld( p, Node ); + if ( pListOld == NULL ) + { + Cut_NodeWriteCutsOld( p, Node, pListNew ); + return; + } + // merge the lists + pList = Cut_CutMergeLists( pListOld, pListNew ); + Cut_NodeWriteCutsOld( p, Node, pList ); +} + + +/**Function************************************************************* + + Synopsis [Transfers the temporary cuts to be the new cuts.] + + Description [Returns 1 if something was transferred.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Cut_NodeTempTransferToNew( Cut_Man_t * p, int Node, int CutSetNum ) +{ + Cut_Cut_t * pList; + pList = Cut_NodeReadCutsTemp( p, CutSetNum ); + Cut_NodeWriteCutsTemp( p, CutSetNum, NULL ); + Cut_NodeWriteCutsNew( p, Node, pList ); + return pList != NULL; +} + +/**Function************************************************************* + + Synopsis [Transfers the old cuts to be the new cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Cut_NodeOldTransferToNew( Cut_Man_t * p, int Node ) +{ + Cut_Cut_t * pList; + pList = Cut_NodeReadCutsOld( p, Node ); + Cut_NodeWriteCutsOld( p, Node, NULL ); + Cut_NodeWriteCutsNew( p, Node, pList ); +// Cut_CutListVerify( pList ); +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/cut/cutTable.c b/src/opt/cut/cutTable.c deleted file mode 100644 index 5dfaca7b..00000000 --- a/src/opt/cut/cutTable.c +++ /dev/null @@ -1,253 +0,0 @@ -/**CFile**************************************************************** - - FileName [cutTable.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [K-feasible cut computation package.] - - Synopsis [Hashing cuts to prevent duplication.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: cutTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "cutInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -struct Cut_HashTableStruct_t_ -{ - int nBins; - Cut_Cut_t ** pBins; - int nEntries; - int * pPlaces; - int nPlaces; - int timeLookup; -}; - -// iterator through all the cuts of the list -#define Cut_TableListForEachCut( pList, pCut ) \ - for ( pCut = pList; \ - pCut; \ - pCut = pCut->pData ) -#define Cut_TableListForEachCutSafe( pList, pCut, pCut2 ) \ - for ( pCut = pList, \ - pCut2 = pCut? pCut->pData: NULL; \ - pCut; \ - pCut = pCut2, \ - pCut2 = pCut? pCut->pData: NULL ) - -// primes used to compute the hash key -static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; - -// hashing function -static inline unsigned Cut_HashKey( Cut_Cut_t * pCut ) -{ - unsigned i, uRes = pCut->nLeaves * s_HashPrimes[9]; - for ( i = 0; i < pCut->nLeaves + pCut->fSeq; i++ ) - uRes += s_HashPrimes[i] * pCut->pLeaves[i]; - return uRes; -} - -// hashing function -static inline int Cut_CompareTwo( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 ) -{ - unsigned i; - if ( pCut1->nLeaves != pCut2->nLeaves ) - return 1; - for ( i = 0; i < pCut1->nLeaves; i++ ) - if ( pCut1->pLeaves[i] != pCut2->pLeaves[i] ) - return 1; - return 0; -} - -static void Cut_TableResize( Cut_HashTable_t * pTable ); - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Starts the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Cut_HashTable_t * Cut_TableStart( int Size ) -{ - Cut_HashTable_t * pTable; - pTable = ALLOC( Cut_HashTable_t, 1 ); - memset( pTable, 0, sizeof(Cut_HashTable_t) ); - // allocate the table - pTable->nBins = Cudd_PrimeCopy( Size ); - pTable->pBins = ALLOC( Cut_Cut_t *, pTable->nBins ); - memset( pTable->pBins, 0, sizeof(Cut_Cut_t *) * pTable->nBins ); - pTable->pPlaces = ALLOC( int, pTable->nBins ); - return pTable; -} - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableStop( Cut_HashTable_t * pTable ) -{ - FREE( pTable->pPlaces ); - free( pTable->pBins ); - free( pTable ); -} - -/**Function************************************************************* - - Synopsis [Check the existence of a cut in the lookup table] - - Description [Returns 1 if the entry is found.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_TableLookup( Cut_HashTable_t * pTable, Cut_Cut_t * pCut, int fStore ) -{ - Cut_Cut_t * pEnt; - unsigned Key; - int clk = clock(); - - Key = Cut_HashKey(pCut) % pTable->nBins; - Cut_TableListForEachCut( pTable->pBins[Key], pEnt ) - { - if ( !Cut_CompareTwo( pEnt, pCut ) ) - { -pTable->timeLookup += clock() - clk; - return 1; - } - } - if ( pTable->nEntries > 2 * pTable->nBins ) - { - Cut_TableResize( pTable ); - Key = Cut_HashKey(pCut) % pTable->nBins; - } - // remember the place - if ( fStore && pTable->pBins[Key] == NULL ) - pTable->pPlaces[ pTable->nPlaces++ ] = Key; - // add the cut to the table - pCut->pData = pTable->pBins[Key]; - pTable->pBins[Key] = pCut; - pTable->nEntries++; -pTable->timeLookup += clock() - clk; - return 0; -} - - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableClear( Cut_HashTable_t * pTable ) -{ - int i; - assert( pTable->nPlaces <= pTable->nBins ); - for ( i = 0; i < pTable->nPlaces; i++ ) - { - assert( pTable->pBins[ pTable->pPlaces[i] ] ); - pTable->pBins[ pTable->pPlaces[i] ] = NULL; - } - pTable->nPlaces = 0; - pTable->nEntries = 0; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TableResize( Cut_HashTable_t * pTable ) -{ - Cut_Cut_t ** pBinsNew; - Cut_Cut_t * pEnt, * pEnt2; - int nBinsNew, Counter, i, clk; - unsigned Key; - -clk = clock(); - // get the new table size - nBinsNew = Cudd_PrimeCopy( 3 * pTable->nBins ); - // allocate a new array - pBinsNew = ALLOC( Cut_Cut_t *, nBinsNew ); - memset( pBinsNew, 0, sizeof(Cut_Cut_t *) * nBinsNew ); - // rehash the entries from the old table - Counter = 0; - for ( i = 0; i < pTable->nBins; i++ ) - Cut_TableListForEachCutSafe( pTable->pBins[i], pEnt, pEnt2 ) - { - Key = Cut_HashKey(pEnt) % nBinsNew; - pEnt->pData = pBinsNew[Key]; - pBinsNew[Key] = pEnt; - Counter++; - } - assert( Counter == pTable->nEntries ); -// printf( "Increasing the structural table size from %6d to %6d. ", pMan->nBins, nBinsNew ); -// PRT( "Time", clock() - clk ); - // replace the table and the parameters - free( pTable->pBins ); - pTable->pBins = pBinsNew; - pTable->nBins = nBinsNew; -} - -/**Function************************************************************* - - Synopsis [Stops the hash table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Cut_TableReadTime( Cut_HashTable_t * pTable ) -{ - if ( pTable == NULL ) - return 0; - return pTable->timeLookup; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/cut/cutTruth.c b/src/opt/cut/cutTruth.c index efacd456..c3514ad7 100644 --- a/src/opt/cut/cutTruth.c +++ b/src/opt/cut/cutTruth.c @@ -20,21 +20,27 @@ #include "cutInt.h" +/* + Truth tables computed in this package are represented as bit-strings + stored in the cut data structure. Cuts of any number of inputs have + the truth table with 2^k bits, where k is the max number of cut inputs. +*/ + //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void Cut_TruthCompute4( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); -static void Cut_TruthCompute5( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); -static void Cut_TruthCompute6( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); +extern int nTotal = 0; +extern int nGood = 0; +extern int nEqual = 0; //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFITIONS /// +/// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Performs truth table computation.] + Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.] Description [] @@ -64,58 +70,42 @@ static inline unsigned Cut_TruthPhase( Cut_Cut_t * pCut, Cut_Cut_t * pCut1 ) Synopsis [Performs truth table computation.] - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) -{ -int clk = clock(); - if ( pCut->nVarsMax == 4 ) - Cut_TruthCompute4( p, pCut, pCut0, pCut1 ); - else if ( pCut->nVarsMax == 5 ) - Cut_TruthCompute5( p, pCut, pCut0, pCut1 ); - else // if ( pCut->nVarsMax == 6 ) - Cut_TruthCompute6( p, pCut, pCut0, pCut1 ); -p->timeTruth += clock() - clk; -} - -/**Function************************************************************* - - Synopsis [Performs truth table computation.] - - Description [] + Description [This procedure cannot be used while recording oracle + because it will overwrite Num0 and Num1.] SideEffects [] SeeAlso [] ***********************************************************************/ -void Cut_TruthCompute4( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +void Cut_TruthNCanonicize( Cut_Cut_t * pCut ) { - unsigned * puTruthCut0, * puTruthCut1; - unsigned uTruth0, uTruth1, uPhase; - - puTruthCut0 = Cut_CutReadTruth(pCut0); - puTruthCut1 = Cut_CutReadTruth(pCut1); - - uPhase = Cut_TruthPhase( pCut, pCut0 ); - uTruth0 = Extra_TruthPerm4One( *puTruthCut0, uPhase ); - uTruth0 = p->fCompl0? ~uTruth0: uTruth0; - - uPhase = Cut_TruthPhase( pCut, pCut1 ); - uTruth1 = Extra_TruthPerm4One( *puTruthCut1, uPhase ); - uTruth1 = p->fCompl1? ~uTruth1: uTruth1; + unsigned uTruth; + unsigned * uCanon2; + char * pPhases2; + assert( pCut->nVarsMax < 6 ); - uTruth1 = uTruth0 & uTruth1; - if ( pCut->fCompl ) - uTruth1 = ~uTruth1; - if ( pCut->nVarsMax == 4 ) - uTruth1 &= 0xFFFF; - Cut_CutWriteTruth( pCut, &uTruth1 ); + // get the direct truth table + uTruth = *Cut_CutReadTruth(pCut); + + // compute the direct truth table + Extra_TruthCanonFastN( pCut->nVarsMax, pCut->nLeaves, &uTruth, &uCanon2, &pPhases2 ); +// uCanon[0] = uCanon2[0]; +// uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0]; +// uPhases[0] = pPhases2[0]; + pCut->uCanon0 = uCanon2[0]; + pCut->Num0 = pPhases2[0]; + + // get the complemented truth table + uTruth = ~*Cut_CutReadTruth(pCut); + + // compute the direct truth table + Extra_TruthCanonFastN( pCut->nVarsMax, pCut->nLeaves, &uTruth, &uCanon2, &pPhases2 ); +// uCanon[0] = uCanon2[0]; +// uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0]; +// uPhases[0] = pPhases2[0]; + pCut->uCanon1 = uCanon2[0]; + pCut->Num1 = pPhases2[0]; } /**Function************************************************************* @@ -129,26 +119,44 @@ void Cut_TruthCompute4( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_ SeeAlso [] ***********************************************************************/ -void Cut_TruthCompute5( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +void Cut_TruthComputeOld( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ) { - unsigned * puTruthCut0, * puTruthCut1; - unsigned uTruth0, uTruth1, uPhase; + static unsigned uTruth0[8], uTruth1[8]; + int nTruthWords = Cut_TruthWords( pCut->nVarsMax ); + unsigned * pTruthRes; + int i, uPhase; - puTruthCut0 = Cut_CutReadTruth(pCut0); - puTruthCut1 = Cut_CutReadTruth(pCut1); + // permute the first table + uPhase = Cut_TruthPhase( pCut, pCut0 ); + Extra_TruthExpand( pCut->nVarsMax, nTruthWords, Cut_CutReadTruth(pCut0), uPhase, uTruth0 ); + if ( fCompl0 ) + { + for ( i = 0; i < nTruthWords; i++ ) + uTruth0[i] = ~uTruth0[i]; + } - uPhase = Cut_TruthPhase( pCut, pCut0 ); - uTruth0 = Extra_TruthPerm5One( *puTruthCut0, uPhase ); - uTruth0 = p->fCompl0? ~uTruth0: uTruth0; + // permute the second table + uPhase = Cut_TruthPhase( pCut, pCut1 ); + Extra_TruthExpand( pCut->nVarsMax, nTruthWords, Cut_CutReadTruth(pCut1), uPhase, uTruth1 ); + if ( fCompl1 ) + { + for ( i = 0; i < nTruthWords; i++ ) + uTruth1[i] = ~uTruth1[i]; + } - uPhase = Cut_TruthPhase( pCut, pCut1 ); - uTruth1 = Extra_TruthPerm5One( *puTruthCut1, uPhase ); - uTruth1 = p->fCompl1? ~uTruth1: uTruth1; + // write the resulting table + pTruthRes = Cut_CutReadTruth(pCut); - uTruth1 = uTruth0 & uTruth1; if ( pCut->fCompl ) - uTruth1 = ~uTruth1; - Cut_CutWriteTruth( pCut, &uTruth1 ); + { + for ( i = 0; i < nTruthWords; i++ ) + pTruthRes[i] = ~(uTruth0[i] & uTruth1[i]); + } + else + { + for ( i = 0; i < nTruthWords; i++ ) + pTruthRes[i] = uTruth0[i] & uTruth1[i]; + } } /**Function************************************************************* @@ -162,158 +170,54 @@ void Cut_TruthCompute5( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_ SeeAlso [] ***********************************************************************/ -void Cut_TruthCompute6( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ) { - unsigned * puTruthCut0, * puTruthCut1; - unsigned uTruth0[2], uTruth1[2], uPhase; - - puTruthCut0 = Cut_CutReadTruth(pCut0); - puTruthCut1 = Cut_CutReadTruth(pCut1); - - uPhase = Cut_TruthPhase( pCut, pCut0 ); - Extra_TruthPerm6One( puTruthCut0, uPhase, uTruth0 ); - uTruth0[0] = p->fCompl0? ~uTruth0[0]: uTruth0[0]; - uTruth0[1] = p->fCompl0? ~uTruth0[1]: uTruth0[1]; - - uPhase = Cut_TruthPhase( pCut, pCut1 ); - Extra_TruthPerm6One( puTruthCut1, uPhase, uTruth1 ); - uTruth1[0] = p->fCompl1? ~uTruth1[0]: uTruth1[0]; - uTruth1[1] = p->fCompl1? ~uTruth1[1]: uTruth1[1]; - - uTruth1[0] = uTruth0[0] & uTruth1[0]; - uTruth1[1] = uTruth0[1] & uTruth1[1]; + // permute the first table + if ( fCompl0 ) + Extra_TruthNot( p->puTemp[0], Cut_CutReadTruth(pCut0), pCut->nVarsMax ); + else + Extra_TruthCopy( p->puTemp[0], Cut_CutReadTruth(pCut0), pCut->nVarsMax ); + Extra_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nLeaves, pCut->nVarsMax, Cut_TruthPhase(pCut, pCut0) ); + // permute the second table + if ( fCompl1 ) + Extra_TruthNot( p->puTemp[1], Cut_CutReadTruth(pCut1), pCut->nVarsMax ); + else + Extra_TruthCopy( p->puTemp[1], Cut_CutReadTruth(pCut1), pCut->nVarsMax ); + Extra_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nLeaves, pCut->nVarsMax, Cut_TruthPhase(pCut, pCut1) ); + // produce the resulting table if ( pCut->fCompl ) - { - uTruth1[0] = ~uTruth0[0]; - uTruth1[1] = ~uTruth0[1]; - } - Cut_CutWriteTruth( pCut, uTruth1 ); -} - + Extra_TruthNand( Cut_CutReadTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nVarsMax ); + else + Extra_TruthAnd( Cut_CutReadTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nVarsMax ); +// Ivy_TruthTestOne( *Cut_CutReadTruth(pCut) ); + // quit if no fancy computation is needed + if ( !p->pParams->fFancy ) + return; + if ( pCut->nLeaves != 7 ) + return; + // count the total number of truth tables computed + nTotal++; -/**Function************************************************************* - - Synopsis [Performs truth table computation.] - - Description [] - - SideEffects [] + // MAPPING INTO ALTERA 6-2 LOGIC BLOCKS + // call this procedure to find the minimum number of common variables in the cofactors + // if this number is less or equal than 3, the cut can be implemented using the 6-2 logic block + if ( Extra_TruthMinCofSuppOverlap( Cut_CutReadTruth(pCut), pCut->nVarsMax, NULL ) <= 4 ) + nGood++; - SeeAlso [] + // MAPPING INTO ACTEL 2x2 CELLS + // call this procedure to see if a semi-canonical form can be found in the lookup table + // (if it exists, then a two-level 3-input LUT implementation of the cut exists) + // Before this procedure is called, cell manager should be defined by calling + // Cut_CellLoad (make sure file "cells22_daomap_iwls.txt" is available in the working dir) +// if ( Cut_CellIsRunning() && pCut->nVarsMax <= 9 ) +// nGood += Cut_CellTruthLookup( Cut_CutReadTruth(pCut), pCut->nVarsMax ); +} -***********************************************************************/ -void Cut_TruthComputeOld( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) -{ - unsigned uTruth0, uTruth1, uPhase; - int clk = clock(); - assert( pCut->nVarsMax < 6 ); - - // assign the truth table - if ( pCut0->nLeaves == pCut->nLeaves ) - uTruth0 = *Cut_CutReadTruth(pCut0); - else - { - assert( pCut0->nLeaves < pCut->nLeaves ); - uPhase = Cut_TruthPhase( pCut, pCut0 ); - if ( pCut->nVarsMax == 4 ) - { - assert( pCut0->nLeaves < 4 ); - assert( uPhase < 16 ); - uTruth0 = p->pPerms43[pCut0->uTruth & 0xFF][uPhase]; - } - else - { - assert( pCut->nVarsMax == 5 ); - assert( pCut0->nLeaves < 5 ); - assert( uPhase < 32 ); - if ( pCut0->nLeaves == 4 ) - { -// Count4++; -/* - if ( uPhase == 31-16 ) // 01111 - uTruth0 = pCut0->uTruth; - else if ( uPhase == 31-8 ) // 10111 - uTruth0 = p->pPerms54[pCut0->uTruth & 0xFFFF][0]; - else if ( uPhase == 31-4 ) // 11011 - uTruth0 = p->pPerms54[pCut0->uTruth & 0xFFFF][1]; - else if ( uPhase == 31-2 ) // 11101 - uTruth0 = p->pPerms54[pCut0->uTruth & 0xFFFF][2]; - else if ( uPhase == 31-1 ) // 11110 - uTruth0 = p->pPerms54[pCut0->uTruth & 0xFFFF][3]; - else - assert( 0 ); -*/ - uTruth0 = Extra_TruthPerm5One( *Cut_CutReadTruth(pCut0), uPhase ); - } - else - { -// Count5++; -// uTruth0 = p->pPerms53[pCut0->uTruth & 0xFF][uPhase]; - uTruth0 = Extra_TruthPerm5One( *Cut_CutReadTruth(pCut0), uPhase ); - } - } - } - uTruth0 = p->fCompl0? ~uTruth0: uTruth0; - - // assign the truth table - if ( pCut1->nLeaves == pCut->nLeaves ) - uTruth0 = *Cut_CutReadTruth(pCut1); - else - { - assert( pCut1->nLeaves < pCut->nLeaves ); - uPhase = Cut_TruthPhase( pCut, pCut1 ); - if ( pCut->nVarsMax == 4 ) - { - assert( pCut1->nLeaves < 4 ); - assert( uPhase < 16 ); - uTruth1 = p->pPerms43[pCut1->uTruth & 0xFF][uPhase]; - } - else - { - assert( pCut->nVarsMax == 5 ); - assert( pCut1->nLeaves < 5 ); - assert( uPhase < 32 ); - if ( pCut1->nLeaves == 4 ) - { -// Count4++; -/* - if ( uPhase == 31-16 ) // 01111 - uTruth1 = pCut1->uTruth; - else if ( uPhase == 31-8 ) // 10111 - uTruth1 = p->pPerms54[pCut1->uTruth & 0xFFFF][0]; - else if ( uPhase == 31-4 ) // 11011 - uTruth1 = p->pPerms54[pCut1->uTruth & 0xFFFF][1]; - else if ( uPhase == 31-2 ) // 11101 - uTruth1 = p->pPerms54[pCut1->uTruth & 0xFFFF][2]; - else if ( uPhase == 31-1 ) // 11110 - uTruth1 = p->pPerms54[pCut1->uTruth & 0xFFFF][3]; - else - assert( 0 ); -*/ - uTruth1 = Extra_TruthPerm5One( *Cut_CutReadTruth(pCut1), uPhase ); - } - else - { -// Count5++; -// uTruth1 = p->pPerms53[pCut1->uTruth & 0xFF][uPhase]; - uTruth1 = Extra_TruthPerm5One( *Cut_CutReadTruth(pCut1), uPhase ); - } - } - } - uTruth1 = p->fCompl1? ~uTruth1: uTruth1; - uTruth1 = uTruth0 & uTruth1; - if ( pCut->fCompl ) - uTruth1 = ~uTruth1; - if ( pCut->nVarsMax == 4 ) - uTruth1 &= 0xFFFF; - Cut_CutWriteTruth( pCut, &uTruth1 ); -p->timeTruth += clock() - clk; -} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// diff --git a/src/opt/cut/module.make b/src/opt/cut/module.make index 1175b3f2..132e730b 100644 --- a/src/opt/cut/module.make +++ b/src/opt/cut/module.make @@ -1,6 +1,9 @@ -SRC += src/opt/cut/cutMan.c \ +SRC += src/opt/cut/cutApi.c \ + src/opt/cut/cutCut.c \ + src/opt/cut/cutMan.c \ src/opt/cut/cutMerge.c \ src/opt/cut/cutNode.c \ + src/opt/cut/cutOracle.c \ + src/opt/cut/cutPre22.c \ src/opt/cut/cutSeq.c \ - src/opt/cut/cutTable.c \ src/opt/cut/cutTruth.c |