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