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