From 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 08:01:00 -0800 Subject: Version abc80130 --- src/opt/cut/abcCut.c | 492 ---------------------- src/opt/cut/cut.h | 124 ++---- src/opt/cut/cutApi.c | 197 --------- src/opt/cut/cutCut.c | 359 ---------------- src/opt/cut/cutExpand.c | 184 -------- src/opt/cut/cutInt.h | 79 +--- src/opt/cut/cutList.h | 120 +----- src/opt/cut/cutMan.c | 243 ++--------- src/opt/cut/cutMerge.c | 11 +- src/opt/cut/cutNode.c | 1072 ++++++++++++++++------------------------------- src/opt/cut/cutOracle.c | 428 ------------------- src/opt/cut/cutPre22.c | 988 ------------------------------------------- src/opt/cut/cutSeq.c | 184 +------- src/opt/cut/cutTable.c | 253 +++++++++++ src/opt/cut/cutTruth.c | 314 +++++++++----- src/opt/cut/module.make | 7 +- 16 files changed, 930 insertions(+), 4125 deletions(-) delete mode 100644 src/opt/cut/abcCut.c delete mode 100644 src/opt/cut/cutApi.c delete mode 100644 src/opt/cut/cutCut.c delete mode 100644 src/opt/cut/cutExpand.c delete mode 100644 src/opt/cut/cutOracle.c delete mode 100644 src/opt/cut/cutPre22.c create mode 100644 src/opt/cut/cutTable.c (limited to 'src/opt/cut') diff --git a/src/opt/cut/abcCut.c b/src/opt/cut/abcCut.c deleted file mode 100644 index 9bbd5790..00000000 --- a/src/opt/cut/abcCut.c +++ /dev/null @@ -1,492 +0,0 @@ -/**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 dee05dfc..6719ed4d 100644 --- a/src/opt/cut/cut.h +++ b/src/opt/cut/cut.h @@ -21,10 +21,6 @@ #ifndef __CUT_H__ #define __CUT_H__ -#ifdef __cplusplus -extern "C" { -#endif - //////////////////////////////////////////////////////////////////////// /// INCLUDES /// //////////////////////////////////////////////////////////////////////// @@ -33,133 +29,81 @@ extern "C" { /// 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 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 + 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 }; struct Cut_CutStruct_t_ { - unsigned Num0 : 11; // temporary number - unsigned Num1 : 11; // temporary number + unsigned uTruth : 16; // truth table for 4-input cuts + unsigned uPhase : 7; // the phase when mapping into a canonical form unsigned fSimul : 1; // the value of cut's output at 000.. pattern unsigned fCompl : 1; // the cut is complemented - 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 + 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] 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 unsigned * Cut_CutReadTruth( Cut_Cut_t * p ) { return (unsigned *)(p->pLeaves + p->nVarsMax); } +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 void Cut_CutWriteTruth( Cut_Cut_t * p, unsigned * puTruth ) { - int i; - for ( i = (p->nVarsMax <= 5) ? 0 : ((1 << (p->nVarsMax - 5)) - 1); i >= 0; i-- ) - p->pLeaves[p->nVarsMax + i] = (int)puTruth[i]; + 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]; } //////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// +/// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// 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 Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode ); +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_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ); -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 +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 ); //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +#endif + diff --git a/src/opt/cut/cutApi.c b/src/opt/cut/cutApi.c deleted file mode 100644 index 980c6b12..00000000 --- a/src/opt/cut/cutApi.c +++ /dev/null @@ -1,197 +0,0 @@ -/**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 deleted file mode 100644 index 94147278..00000000 --- a/src/opt/cut/cutCut.c +++ /dev/null @@ -1,359 +0,0 @@ -/**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 deleted file mode 100644 index d389ef7a..00000000 --- a/src/opt/cut/cutExpand.c +++ /dev/null @@ -1,184 +0,0 @@ -/**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 17f268c7..fe5080b4 100644 --- a/src/opt/cut/cutInt.h +++ b/src/opt/cut/cutInt.h @@ -29,7 +29,6 @@ #include "extra.h" #include "vec.h" #include "cut.h" -#include "cutList.h" //////////////////////////////////////////////////////////////////////// /// PARAMETERS /// @@ -42,103 +41,56 @@ 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 * 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 + Vec_Ptr_t * vCuts; // cuts by ID + Vec_Ptr_t * vCutsNew; // cuts by ID + Cut_HashTable_t * tTable; // cuts by their leaves (and root) // 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; - 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; + // precomputations + unsigned uTruthVars[6][2]; + unsigned short ** pPerms43; + unsigned ** pPerms53; + unsigned ** pPerms54; // statistics int nCutsCur; int nCutsAlloc; int nCutsDealloc; int nCutsPeak; int nCutsTriv; - int nCutsFilter; - int nCutsLimit; + int nCutsNode; 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 DEFINITIONS /// +/// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// -// 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 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 ); +extern Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ); /*=== cutTable.c ==========================================================*/ extern Cut_HashTable_t * Cut_TableStart( int Size ); extern void Cut_TableStop( Cut_HashTable_t * pTable ); @@ -146,12 +98,11 @@ 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_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 +extern void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ); //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +#endif + diff --git a/src/opt/cut/cutList.h b/src/opt/cut/cutList.h index a03ec9d5..eb008ef9 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[CUT_SIZE_MAX+1]; - Cut_Cut_t ** ppTail[CUT_SIZE_MAX+1]; + Cut_Cut_t * pHead[7]; + Cut_Cut_t ** ppTail[7]; }; //////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// +/// MACRO DEFITIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// @@ -50,7 +50,7 @@ struct Cut_ListStruct_t_ /**Function************************************************************* - Synopsis [Start the cut list.] + Synopsis [] Description [] @@ -62,7 +62,7 @@ struct Cut_ListStruct_t_ static inline void Cut_ListStart( Cut_List_t * p ) { int i; - for ( i = 1; i <= CUT_SIZE_MAX; i++ ) + for ( i = 1; i <= 6; 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 [Adds one cut to the cut list.] + Synopsis [] Description [] @@ -82,100 +82,14 @@ 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 <= CUT_SIZE_MAX ); + assert( pCut->nLeaves > 0 && pCut->nLeaves < 7 ); *p->ppTail[pCut->nLeaves] = pCut; p->ppTail[pCut->nLeaves] = &pCut->pNext; } /**Function************************************************************* - 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.] + Synopsis [] Description [] @@ -186,22 +100,16 @@ static inline void Cut_ListAddList( Cut_List_t * pOld, Cut_List_t * pNew ) ***********************************************************************/ static inline Cut_Cut_t * Cut_ListFinish( Cut_List_t * p ) { - Cut_Cut_t * pHead = NULL, ** ppTail = &pHead; int i; - 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; + for ( i = 1; i < 6; i++ ) + *p->ppTail[i] = p->pHead[i+1]; + *p->ppTail[6] = NULL; + return p->pHead[1]; } -#endif - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// +#endif + diff --git a/src/opt/cut/cutMan.c b/src/opt/cut/cutMan.c index 8593ef93..4ad3a66a 100644 --- a/src/opt/cut/cutMan.c +++ b/src/opt/cut/cutMan.c @@ -24,10 +24,8 @@ /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -extern void Npn_StartTruth8( uint8 uTruths[][32] ); - //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -45,65 +43,47 @@ Cut_Man_t * Cut_ManStart( Cut_Params_t * pParams ) { Cut_Man_t * p; int clk = clock(); -// extern int nTruthDsd; -// nTruthDsd = 0; - assert( pParams->nVarsMax >= 3 && pParams->nVarsMax <= CUT_SIZE_MAX ); + assert( pParams->nVarsMax >= 4 && pParams->nVarsMax <= 6 ); p = ALLOC( Cut_Man_t, 1 ); memset( p, 0, sizeof(Cut_Man_t) ); // set and correct parameters p->pParams = pParams; - // prepare storage for cuts - p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax ); - Vec_PtrFill( p->vCutsNew, pParams->nIdsMax, NULL ); - // prepare storage for sequential cuts + if ( p->pParams->fSeq ) + p->pParams->fHash = 1; + // space for cuts + p->vCuts = Vec_PtrAlloc( pParams->nIdsMax ); + Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); if ( pParams->fSeq ) { - 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" ); - } + p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax ); + Vec_PtrFill( p->vCuts, pParams->nIdsMax, NULL ); } + // hash tables + if ( pParams->fHash ) + p->tTable = Cut_TableStart( p->pParams->nKeepMax ); // entry size - 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 ); - } + 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); // 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; } @@ -123,29 +103,23 @@ void Cut_ManStop( Cut_Man_t * p ) { Cut_Cut_t * pCut; int i; -// extern int nTruthDsd; -// printf( "Decomposable cuts = %d.\n", nTruthDsd ); - - Vec_PtrForEachEntry( p->vCutsNew, pCut, i ) + Vec_PtrForEachEntry( p->vCuts, pCut, i ) + { if ( pCut != NULL ) { int k = 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 ); + } + + 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 ); free( p ); } @@ -162,66 +136,21 @@ 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************************************************************* @@ -239,86 +168,6 @@ 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 d8a9989c..ba1afce4 100644 --- a/src/opt/cut/cutMerge.c +++ b/src/opt/cut/cutMerge.c @@ -25,7 +25,7 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* @@ -39,7 +39,7 @@ 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 ) { static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}}; Cut_Cut_t * pRes; @@ -164,7 +164,7 @@ Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut 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 ) { 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->Num1 = uSign1; + pRes->uTruth = (uSign1 << 8); } for ( i = 0; i < (int)pCut0->nLeaves; i++ ) pRes->pLeaves[i] = pCut0->pLeaves[i]; @@ -645,8 +645,7 @@ Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut } assert( Count == nNodes ); pRes->nLeaves = nNodes; - pRes->Num1 = uSign1; - pRes->Num0 = uSign0; + pRes->uTruth = (uSign1 << 8) | uSign0; return pRes; } diff --git a/src/opt/cut/cutNode.c b/src/opt/cut/cutNode.c index 1f93b14b..8d16ac8a 100644 --- a/src/opt/cut/cutNode.c +++ b/src/opt/cut/cutNode.c @@ -19,21 +19,42 @@ ***********************************************************************/ #include "cutInt.h" +#include "cutList.h" //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -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 ); +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 ) //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Returns 1 if pDom is contained in pCut.] + Synopsis [Returns the pointer to the linked list of cuts.] Description [] @@ -42,24 +63,16 @@ static int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Nod SeeAlso [] ***********************************************************************/ -static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut ) +Cut_Cut_t * Cut_NodeReadCuts( Cut_Man_t * p, int 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; + if ( Node >= p->vCuts->nSize ) + return NULL; + return Vec_PtrEntry( p->vCuts, Node ); } /**Function************************************************************* - Synopsis [Filters cuts using dominance.] + Synopsis [Returns the pointer to the linked list of cuts.] Description [] @@ -68,293 +81,14 @@ static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -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 ) +void Cut_NodeWriteCuts( Cut_Man_t * p, int Node, Cut_Cut_t * 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; + Vec_PtrWriteEntry( p->vCuts, Node, pList ); } /**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_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.] + Synopsis [Sets the trivial cut for the node.] Description [] @@ -363,68 +97,15 @@ static inline int Cut_CutProcessTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode ) +void Cut_NodeSetTriv( Cut_Man_t * p, int 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; + assert( Cut_NodeReadCuts(p, Node) == NULL ); + Cut_NodeWriteCuts( p, Node, Cut_CutCreateTriv(p, Node) ); } /**Function************************************************************* - Synopsis [Returns optimum delay mapping.] + Synopsis [Deallocates the cuts at the node.] Description [] @@ -433,96 +114,21 @@ p->timeMap += clock() - clk; SeeAlso [] ***********************************************************************/ -int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 ) +void Cut_NodeFreeCuts( Cut_Man_t * p, int Node ) { - 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; + 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 ); } -/**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 [Computes area after mapping.] + Synopsis [] Description [] @@ -531,23 +137,10 @@ int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int SeeAlso [] ***********************************************************************/ -int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node ) +void Cut_NodeSetComputedAsNew( 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.] @@ -559,43 +152,24 @@ int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node ) SeeAlso [] ***********************************************************************/ -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_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 ) { - 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++; - } + 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 ); // get the cut lists of children - if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode) ) - return; - - // remember the old number of cuts - nCutsOld = p->nCutsCur; - Limit = p->pParams->nVarsMax; + pList0 = Cut_NodeReadCuts( p, Node0 ); + pList1 = Cut_NodeReadCuts( p, Node1 ); + assert( pList0 && pList1 ); // 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 ) @@ -603,54 +177,101 @@ void Cut_NodeDoComputeCuts( Cut_Man_t * p, Cut_List_t * pSuper, int Node, int fC 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, pTemp0, pTemp1, pSuper ) ) - goto Quits; - } - // small by large - Cut_ListForEachCutStop( pList0, pTemp0, pStop0 ) + if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) + goto finish; + // all by large + Cut_ListForEachCut( pList0, pTemp0 ) Cut_ListForEachCut( pStop1, 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 ) + if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) + goto finish; + // all by large + Cut_ListForEachCut( pList1, pTemp1 ) Cut_ListForEachCut( pStop0, pTemp0 ) - { - if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign ) - continue; - if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) ) - goto Quits; - } + if ( Cut_CutProcessTwo( p, Node, pTemp0, pTemp1, &SuperList ) ) + goto finish; // 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, pTemp0, pTemp1, pSuper ) ) - goto Quits; - } - if ( p->nNodeCuts == 0 ) - p->nNodesNoCuts++; -Quits: - if ( TreeCode & 1 ) - pList0->pNext = pStore0; - if ( TreeCode & 2 ) - pList1->pNext = pStore1; + 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; } /**Function************************************************************* @@ -666,32 +287,33 @@ Quits: ***********************************************************************/ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) { - Cut_List_t Super, * pSuper = &Super; + Cut_List_t SuperList; 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( pSuper ); + Cut_ListStart( &SuperList ); // remember the root node to save the resulting cuts Root = Vec_IntEntry( vNodes, 0 ); - p->nNodeCuts = 1; + p->nCutsNode = 1; // collect small cuts first Vec_PtrClear( p->vTemp ); Vec_IntForEachEntry( vNodes, Node, i ) { // get the cuts of this node - pList = Cut_NodeReadCutsNew( p, Node ); - Cut_NodeWriteCutsNew( p, Node, NULL ); + pList = Cut_NodeReadCuts( p, Node ); + Cut_NodeWriteCuts( 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( pSuper, pList ), pTop = pList; + Cut_ListAdd( &SuperList, pList ), pTop = pList; else Cut_CutRecycle( p, pList ); // save all the cuts that are smaller than the limit @@ -702,19 +324,20 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) Vec_PtrPush( p->vTemp, pCut ); break; } - // check containment - if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) + // check hash tables + if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) + { + Cut_CutRecycle( p, 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( pSuper, pCut ); - if ( ++p->nNodeCuts == p->pParams->nKeepMax ) + Cut_ListAdd( &SuperList, pCut ); + if ( ++p->nCutsNode == p->pParams->nKeepMax ) { // recycle the rest of the cuts of this node - Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) + Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle all cuts of other nodes Vec_IntForEachEntryStart( vNodes, Node, k, i+1 ) @@ -726,25 +349,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 ) { - // check containment - if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) ) + if ( p->pParams->fHash && Cut_TableLookup( p->tTable, pCut, !p->pParams->fSeq ) ) + { + Cut_CutRecycle( p, pCut ); continue; + } // 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 ) + Cut_ListAdd( &SuperList, pCut ); + if ( ++p->nCutsNode == p->pParams->nKeepMax ) { // recycle the rest of the cuts - Cut_ListForEachCutSafe( pListStart, pCut, pCut2 ) + Cut_ListForEachCutSafe( pCut->pNext, pCut, pCut2 ) Cut_CutRecycle( p, pCut ); // recycle the saved cuts of other nodes Vec_PtrForEachEntryStart( p->vTemp, pList, k, i+1 ) @@ -756,22 +379,25 @@ Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes ) } finish : // set the cuts at the node - assert( Cut_NodeReadCutsNew(p, Root) == NULL ); - pList = Cut_ListFinish( pSuper ); - Cut_NodeWriteCutsNew( p, Root, pList ); + 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 ); 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 [Computes the cuts by unioning cuts at a choice node.] + Synopsis [Start the cut computation.] Description [] @@ -780,182 +406,157 @@ p->timeUnion += clock() - clk; SeeAlso [] ***********************************************************************/ -Cut_Cut_t * Cut_NodeUnionCutsSeq( Cut_Man_t * p, Vec_Int_t * vNodes, int CutSetNum, int fFirst ) +Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p ) { - 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(); + 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; +} - // start the new list - Cut_ListStart( pSuper ); +/**Function************************************************************* - // remember the root node to save the resulting cuts - Root = Vec_IntEntry( vNodes, 0 ); - p->nNodeCuts = 1; + Synopsis [Start the cut computation.] - // store the original lists for comparison - p->pCompareOld = Cut_NodeReadCutsOld( p, Root ); - p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL; + Description [] + + SideEffects [] - // get the topmost cut - pTop = NULL; - if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL ) - pTop = Cut_NodeReadCutsNew( p, Root ); - assert( pTop != NULL ); + SeeAlso [] - // 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; +***********************************************************************/ +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; +} - // 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; +/**Function************************************************************* - // 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; - } - } + Synopsis [Start the cut computation.] - // 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; - } - } + Description [] + + SideEffects [] - // 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 ); + SeeAlso [] - // 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 - { - assert( Cut_NodeReadCutsNew(p, Root) == NULL ); - Cut_NodeWriteCutsNew( p, Root, pList ); - } +***********************************************************************/ +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 ); +} -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 [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 [Print the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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( " }" ); +} + +/**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 + ); } /**Function************************************************************* - Synopsis [Verifies that the list contains only non-dominated cuts.] + Synopsis [Filter the cuts using dominance.] Description [] @@ -964,27 +565,62 @@ p->timeUnion += clock() - clk; SeeAlso [] ***********************************************************************/ -int Cut_CutListVerify( Cut_Cut_t * pList ) +void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList ) { - Cut_Cut_t * pCut, * pDom; - Cut_ListForEachCut( pList, pCut ) + 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_ListForEachCutStop( pList, pDom, pCut ) + assert( pCut->nLeaves > 1 ); + // go through all the previous cuts up to pCut + Cut_ListForEachCutStop( pList->pNext, pDom, pCut ) { - if ( Cut_CutCheckDominance( 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++ ) { - int x = 0; - printf( "******************* These are contained cuts:\n" ); - Cut_CutPrint( pDom, 1 ); - Cut_CutPrint( pDom, 1 ); - - return 0; + 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; } + 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; } } - return 1; + *ppListR = NULL; } + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/opt/cut/cutOracle.c b/src/opt/cut/cutOracle.c deleted file mode 100644 index 3eb4462b..00000000 --- a/src/opt/cut/cutOracle.c +++ /dev/null @@ -1,428 +0,0 @@ -/**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 deleted file mode 100644 index 5cb87a9c..00000000 --- a/src/opt/cut/cutPre22.c +++ /dev/null @@ -1,988 +0,0 @@ -/**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<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<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 d36f94f7..869bd7b3 100644 --- a/src/opt/cut/cutSeq.c +++ b/src/opt/cut/cutSeq.c @@ -25,12 +25,12 @@ //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Shifts all cut leaves of the node by the given number of latches.] + Synopsis [] Description [] @@ -39,186 +39,6 @@ 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 new file mode 100644 index 00000000..5dfaca7b --- /dev/null +++ b/src/opt/cut/cutTable.c @@ -0,0 +1,253 @@ +/**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 c3514ad7..efacd456 100644 --- a/src/opt/cut/cutTruth.c +++ b/src/opt/cut/cutTruth.c @@ -20,27 +20,21 @@ #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 /// //////////////////////////////////////////////////////////////////////// -extern int nTotal = 0; -extern int nGood = 0; -extern int nEqual = 0; +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 ); //////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// +/// FUNCTION DEFITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* - Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.] + Synopsis [Performs truth table computation.] Description [] @@ -70,42 +64,23 @@ static inline unsigned Cut_TruthPhase( Cut_Cut_t * pCut, Cut_Cut_t * pCut1 ) Synopsis [Performs truth table computation.] - Description [This procedure cannot be used while recording oracle - because it will overwrite Num0 and Num1.] + Description [] SideEffects [] SeeAlso [] ***********************************************************************/ -void Cut_TruthNCanonicize( Cut_Cut_t * pCut ) +void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { - unsigned uTruth; - unsigned * uCanon2; - char * pPhases2; - assert( pCut->nVarsMax < 6 ); - - // 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]; +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************************************************************* @@ -119,44 +94,28 @@ void Cut_TruthNCanonicize( Cut_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -void Cut_TruthComputeOld( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ) +void Cut_TruthCompute4( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { - static unsigned uTruth0[8], uTruth1[8]; - int nTruthWords = Cut_TruthWords( pCut->nVarsMax ); - unsigned * pTruthRes; - int i, uPhase; + unsigned * puTruthCut0, * puTruthCut1; + unsigned uTruth0, uTruth1, uPhase; - // 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]; - } + puTruthCut0 = Cut_CutReadTruth(pCut0); + puTruthCut1 = Cut_CutReadTruth(pCut1); - // 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, pCut0 ); + uTruth0 = Extra_TruthPerm4One( *puTruthCut0, uPhase ); + uTruth0 = p->fCompl0? ~uTruth0: uTruth0; - // write the resulting table - pTruthRes = Cut_CutReadTruth(pCut); + uPhase = Cut_TruthPhase( pCut, pCut1 ); + uTruth1 = Extra_TruthPerm4One( *puTruthCut1, uPhase ); + uTruth1 = p->fCompl1? ~uTruth1: uTruth1; + uTruth1 = uTruth0 & uTruth1; if ( pCut->fCompl ) - { - 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]; - } + uTruth1 = ~uTruth1; + if ( pCut->nVarsMax == 4 ) + uTruth1 &= 0xFFFF; + Cut_CutWriteTruth( pCut, &uTruth1 ); } /**Function************************************************************* @@ -170,55 +129,192 @@ void Cut_TruthComputeOld( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 SeeAlso [] ***********************************************************************/ -void Cut_TruthCompute( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, int fCompl0, int fCompl1 ) +void Cut_TruthCompute5( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) { - // 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 + unsigned * puTruthCut0, * puTruthCut1; + unsigned uTruth0, uTruth1, uPhase; + + puTruthCut0 = Cut_CutReadTruth(pCut0); + puTruthCut1 = Cut_CutReadTruth(pCut1); + + uPhase = Cut_TruthPhase( pCut, pCut0 ); + uTruth0 = Extra_TruthPerm5One( *puTruthCut0, uPhase ); + uTruth0 = p->fCompl0? ~uTruth0: uTruth0; + + uPhase = Cut_TruthPhase( pCut, pCut1 ); + uTruth1 = Extra_TruthPerm5One( *puTruthCut1, uPhase ); + uTruth1 = p->fCompl1? ~uTruth1: uTruth1; + + uTruth1 = uTruth0 & uTruth1; if ( pCut->fCompl ) - 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 ); + uTruth1 = ~uTruth1; + Cut_CutWriteTruth( pCut, &uTruth1 ); +} + +/**Function************************************************************* -// Ivy_TruthTestOne( *Cut_CutReadTruth(pCut) ); + Synopsis [Performs truth table computation.] - // quit if no fancy computation is needed - if ( !p->pParams->fFancy ) - return; + Description [] + + SideEffects [] - if ( pCut->nLeaves != 7 ) - return; + SeeAlso [] - // count the total number of truth tables computed - nTotal++; +***********************************************************************/ +void Cut_TruthCompute6( Cut_Man_t * p, Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) +{ + unsigned * puTruthCut0, * puTruthCut1; + unsigned uTruth0[2], uTruth1[2], uPhase; - // 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++; + 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]; - // 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 ); + 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]; + if ( pCut->fCompl ) + { + uTruth1[0] = ~uTruth0[0]; + uTruth1[1] = ~uTruth0[1]; + } + Cut_CutWriteTruth( pCut, uTruth1 ); } + + + +/**Function************************************************************* + + Synopsis [Performs truth table computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +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 132e730b..1175b3f2 100644 --- a/src/opt/cut/module.make +++ b/src/opt/cut/module.make @@ -1,9 +1,6 @@ -SRC += src/opt/cut/cutApi.c \ - src/opt/cut/cutCut.c \ - src/opt/cut/cutMan.c \ +SRC += 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 -- cgit v1.2.3