summaryrefslogtreecommitdiffstats
path: root/src/map/if
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/if')
-rw-r--r--src/map/if/if.h410
-rw-r--r--src/map/if/ifCore.c148
-rw-r--r--src/map/if/ifCut.c988
-rw-r--r--src/map/if/ifMan.c577
-rw-r--r--src/map/if/ifMap.c350
-rw-r--r--src/map/if/ifReduce.c575
-rw-r--r--src/map/if/ifSeq.c405
-rw-r--r--src/map/if/ifTime.c228
-rw-r--r--src/map/if/ifTruth.c404
-rw-r--r--src/map/if/ifUtil.c658
-rw-r--r--src/map/if/if_.c47
-rw-r--r--src/map/if/module.make8
12 files changed, 4798 insertions, 0 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h
new file mode 100644
index 00000000..b3d2d745
--- /dev/null
+++ b/src/map/if/if.h
@@ -0,0 +1,410 @@
+/**CFile****************************************************************
+
+ FileName [if.h]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [External declarations.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: if.h,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#ifndef __IF_H__
+#define __IF_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// INCLUDES ///
+////////////////////////////////////////////////////////////////////////
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <time.h>
+#include "vec.h"
+#include "mem.h"
+#include "tim.h"
+
+////////////////////////////////////////////////////////////////////////
+/// PARAMETERS ///
+////////////////////////////////////////////////////////////////////////
+
+// the maximum size of LUTs used for mapping (should be the same as FPGA_MAX_LUTSIZE defined in "fpga.h"!!!)
+#define IF_MAX_LUTSIZE 32
+// the largest possible number of LUT inputs when funtionality of the LUTs are computed
+#define IF_MAX_FUNC_LUTSIZE 15
+// a very large number
+#define IF_INFINITY 100000000
+// the largest possible user cut cost
+#define IF_COST_MAX ((1<<14)-1)
+
+// object types
+typedef enum {
+ IF_NONE, // 0: non-existent object
+ IF_CONST1, // 1: constant 1
+ IF_CI, // 2: combinational input
+ IF_CO, // 3: combinational output
+ IF_AND, // 4: AND node
+ IF_VOID // 5: unused object
+} If_Type_t;
+
+////////////////////////////////////////////////////////////////////////
+/// BASIC TYPES ///
+////////////////////////////////////////////////////////////////////////
+
+typedef struct If_Man_t_ If_Man_t;
+typedef struct If_Par_t_ If_Par_t;
+typedef struct If_Lib_t_ If_Lib_t;
+typedef struct If_Obj_t_ If_Obj_t;
+typedef struct If_Cut_t_ If_Cut_t;
+typedef struct If_Set_t_ If_Set_t;
+
+// parameters
+struct If_Par_t_
+{
+ // user-controlable parameters
+ int nLutSize; // the LUT size
+ int nCutsMax; // the max number of cuts
+ int nFlowIters; // the number of iterations of area recovery
+ int nAreaIters; // the number of iterations of area recovery
+ float DelayTarget; // delay target
+ int fPreprocess; // preprossing
+ int fArea; // area-oriented mapping
+ int fFancy; // a fancy feature
+ int fExpRed; // expand/reduce of the best cuts
+ int fLatchPaths; // reset timing on latch paths
+ int fEdge; // uses edge-based cut selection heuristics
+ int fCutMin; // performs cut minimization by removing functionally reducdant variables
+ int fSeqMap; // sequential mapping
+ int fVerbose; // the verbosity flag
+ // internal parameters
+ int fAreaOnly; // area only mode
+ int fTruth; // truth table computation enabled
+ int fUsePerm; // use permutation (delay info)
+ int fUseBdds; // use local BDDs as a cost function
+ int fUseSops; // use local SOPs as a cost function
+ int fUseCnfs; // use local CNFs as a cost function
+ int fUseMv; // use local MV-SOPs as a cost function
+ int nLatches; // the number of latches in seq mapping
+ int fLiftLeaves; // shift the leaves for seq mapping
+ If_Lib_t * pLutLib; // the LUT library
+ float * pTimesArr; // arrival times
+ float * pTimesReq; // required times
+ int (* pFuncCost) (If_Cut_t *); // procedure to compute the user's cost of a cut
+ int (* pFuncUser) (If_Man_t *, If_Obj_t *, If_Cut_t *); // procedure called for each cut when cut computation is finished
+ void * pReoMan; // reordering manager
+};
+
+// the LUT library
+struct If_Lib_t_
+{
+ char * pName; // the name of the LUT library
+ int LutMax; // the maximum LUT size
+ int fVarPinDelays; // set to 1 if variable pin delays are specified
+ float pLutAreas[IF_MAX_LUTSIZE+1]; // the areas of LUTs
+ float pLutDelays[IF_MAX_LUTSIZE+1][IF_MAX_LUTSIZE+1];// the delays of LUTs
+};
+
+// manager
+struct If_Man_t_
+{
+ // mapping parameters
+ If_Par_t * pPars;
+ // mapping nodes
+ If_Obj_t * pConst1; // the constant 1 node
+ Vec_Ptr_t * vCis; // the primary inputs
+ Vec_Ptr_t * vCos; // the primary outputs
+ Vec_Ptr_t * vObjs; // all objects
+ Vec_Ptr_t * vObjsRev; // reverse topological order of objects
+// Vec_Ptr_t * vMapped; // objects used in the mapping
+ Vec_Ptr_t * vTemp; // temporary array
+ int nObjs[IF_VOID];// the number of objects by type
+ // various data
+ int nLevelMax; // the max number of AIG levels
+ float fEpsilon; // epsilon used for comparison
+ float RequiredGlo; // global required times
+ float RequiredGlo2; // global required times
+ float AreaGlo; // global area
+ int nNets; // the sum total of fanins of all LUTs in the mapping
+ int nCutsUsed; // the number of cuts currently used
+ int nCutsMerged; // the total number of cuts merged
+ unsigned * puTemp[4]; // used for the truth table computation
+ int SortMode; // one of the three sorting modes
+ int fNextRound; // set to 1 after the first round
+ int nChoices; // the number of choice nodes
+ // sequential mapping
+ Vec_Ptr_t * vLatchOrder; // topological ordering of latches
+ Vec_Int_t * vLags; // sequentail lags of all nodes
+ int nAttempts; // the number of attempts in binary search
+ int nMaxIters; // the maximum number of iterations
+ int Period; // the current value of the clock period (for seq mapping)
+ // memory management
+ int nTruthWords; // the size of the truth table if allocated
+ int nPermWords; // the size of the permutation array (in words)
+ int nObjBytes; // the size of the object
+ int nCutBytes; // the size of the cut
+ int nSetBytes; // the size of the cut set
+ Mem_Fixed_t * pMemObj; // memory manager for objects (entrysize = nEntrySize)
+ Mem_Fixed_t * pMemSet; // memory manager for sets of cuts (entrysize = nCutSize*(nCutsMax+1))
+ If_Set_t * pMemCi; // memory for CI cutsets
+ If_Set_t * pMemAnd; // memory for AND cutsets
+ If_Set_t * pFreeList; // the list of free cutsets
+ int nSmallSupp; // the small support
+ // timing manager
+ Tim_Man_t * pManTim;
+};
+
+// priority cut
+struct If_Cut_t_
+{
+ float Delay; // delay of the cut
+ float Area; // area (or area-flow) of the cut
+ float AveRefs; // the average number of leaf references
+ float Edge; // the edge flow
+ unsigned uSign; // cut signature
+ unsigned Cost : 14; // the user's cost of the cut
+ unsigned fCompl : 1; // the complemented attribute
+ unsigned fUser : 1; // using the user's area and delay
+ unsigned nLimit : 8; // the maximum number of leaves
+ unsigned nLeaves : 8; // the number of leaves
+ int * pLeaves; // array of fanins
+ char * pPerm; // permutation
+ unsigned * pTruth; // the truth table
+};
+
+// set of priority cut
+struct If_Set_t_
+{
+ short nCutsMax; // the max number of cuts
+ short nCuts; // the current number of cuts
+ If_Set_t * pNext; // next cutset in the free list
+ If_Cut_t ** ppCuts; // the array of pointers to the cuts
+};
+
+// node extension
+struct If_Obj_t_
+{
+ unsigned Type : 4; // object
+ unsigned fCompl0 : 1; // complemented attribute
+ unsigned fCompl1 : 1; // complemented attribute
+ unsigned fPhase : 1; // phase of the node
+ unsigned fRepr : 1; // representative of the equivalence class
+ unsigned fMark : 1; // multipurpose mark
+ unsigned fVisit : 1; // multipurpose mark
+ unsigned Level : 22; // logic level of the node
+ int Id; // integer ID
+ int IdPio; // integer ID of PIs/POs
+ int nRefs; // the number of references
+ int nVisits; // the number of visits to this node
+ int nVisitsCopy; // the number of visits to this node
+ If_Obj_t * pFanin0; // the first fanin
+ If_Obj_t * pFanin1; // the second fanin
+ If_Obj_t * pEquiv; // the choice node
+ float EstRefs; // estimated reference counter
+ float Required; // required time of the onde
+ float LValue; // sequential arrival time of the node
+ void * pCopy; // used for object duplication
+ If_Set_t * pCutSet; // the pointer to the cutset
+ If_Cut_t CutBest; // the best cut selected
+};
+
+static inline If_Obj_t * If_Regular( If_Obj_t * p ) { return (If_Obj_t *)((unsigned long)(p) & ~01); }
+static inline If_Obj_t * If_Not( If_Obj_t * p ) { return (If_Obj_t *)((unsigned long)(p) ^ 01); }
+static inline If_Obj_t * If_NotCond( If_Obj_t * p, int c ) { return (If_Obj_t *)((unsigned long)(p) ^ (c)); }
+static inline int If_IsComplement( If_Obj_t * p ) { return (int )(((unsigned long)p) & 01); }
+
+static inline int If_ManCiNum( If_Man_t * p ) { return p->nObjs[IF_CI]; }
+static inline int If_ManCoNum( If_Man_t * p ) { return p->nObjs[IF_CO]; }
+static inline int If_ManAndNum( If_Man_t * p ) { return p->nObjs[IF_AND]; }
+static inline int If_ManObjNum( If_Man_t * p ) { return Vec_PtrSize(p->vObjs); }
+
+static inline If_Obj_t * If_ManConst1( If_Man_t * p ) { return p->pConst1; }
+static inline If_Obj_t * If_ManCi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCis, i ); }
+static inline If_Obj_t * If_ManCo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCos, i ); }
+static inline If_Obj_t * If_ManLi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCos, If_ManCoNum(p) - p->pPars->nLatches + i ); }
+static inline If_Obj_t * If_ManLo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCis, If_ManCiNum(p) - p->pPars->nLatches + i ); }
+static inline If_Obj_t * If_ManObj( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); }
+
+static inline int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; }
+static inline int If_ObjIsCi( If_Obj_t * pObj ) { return pObj->Type == IF_CI; }
+static inline int If_ObjIsCo( If_Obj_t * pObj ) { return pObj->Type == IF_CO; }
+//static inline int If_ObjIsPi( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 == NULL; }
+static inline int If_ObjIsLatch( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 != NULL; }
+static inline int If_ObjIsAnd( If_Obj_t * pObj ) { return pObj->Type == IF_AND; }
+
+static inline If_Obj_t * If_ObjFanin0( If_Obj_t * pObj ) { return pObj->pFanin0; }
+static inline If_Obj_t * If_ObjFanin1( If_Obj_t * pObj ) { return pObj->pFanin1; }
+static inline int If_ObjFaninC0( If_Obj_t * pObj ) { return pObj->fCompl0; }
+static inline int If_ObjFaninC1( If_Obj_t * pObj ) { return pObj->fCompl1; }
+static inline void * If_ObjCopy( If_Obj_t * pObj ) { return pObj->pCopy; }
+static inline void If_ObjSetCopy( If_Obj_t * pObj, void * pCopy ) { pObj->pCopy = pCopy; }
+static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { pObj->pEquiv = pEqu; }
+
+static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return &pObj->CutBest; }
+static inline unsigned If_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); }
+
+static inline float If_ObjArrTime( If_Obj_t * pObj ) { return If_ObjCutBest(pObj)->Delay; }
+static inline void If_ObjSetArrTime( If_Obj_t * pObj, float ArrTime ) { If_ObjCutBest(pObj)->Delay = ArrTime; }
+
+static inline float If_ObjLValue( If_Obj_t * pObj ) { return pObj->LValue; }
+static inline void If_ObjSetLValue( If_Obj_t * pObj, float LValue ) { pObj->LValue = LValue; }
+
+static inline void * If_CutData( If_Cut_t * pCut ) { return *(void **)pCut; }
+static inline void If_CutSetData( If_Cut_t * pCut, void * pData ) { *(void **)pCut = pData; }
+
+static inline int If_CutLeaveNum( If_Cut_t * pCut ) { return pCut->nLeaves; }
+static inline int * If_CutLeaves( If_Cut_t * pCut ) { return pCut->pLeaves; }
+static inline unsigned * If_CutTruth( If_Cut_t * pCut ) { return pCut->pTruth; }
+static inline unsigned If_CutSuppMask( If_Cut_t * pCut ) { return (~(unsigned)0) >> (32-pCut->nLeaves); }
+static inline int If_CutTruthWords( int nVarsMax ) { return nVarsMax <= 5 ? 1 : (1 << (nVarsMax - 5)); }
+static inline int If_CutPermWords( int nVarsMax ) { return nVarsMax / sizeof(int) + ((nVarsMax % sizeof(int)) > 0); }
+
+static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); }
+
+////////////////////////////////////////////////////////////////////////
+/// MACRO DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+#define IF_MIN(a,b) (((a) < (b))? (a) : (b))
+#define IF_MAX(a,b) (((a) > (b))? (a) : (b))
+
+// the small and large numbers (min/max float are 1.17e-38/3.40e+38)
+#define IF_FLOAT_LARGE ((float)1.0e+20)
+#define IF_FLOAT_SMALL ((float)1.0e-20)
+#define IF_INT_LARGE (10000000)
+
+// iterator over the primary inputs
+#define If_ManForEachCi( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vCis, pObj, i )
+// iterator over the primary outputs
+#define If_ManForEachCo( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vCos, pObj, i )
+// iterator over the primary inputs
+#define If_ManForEachPi( p, pObj, i ) \
+ Vec_PtrForEachEntryStop( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
+// iterator over the primary outputs
+#define If_ManForEachPo( p, pObj, i ) \
+ Vec_PtrForEachEntryStop( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
+// iterator over the latches
+#define If_ManForEachLatchInput( p, pObj, i ) \
+ Vec_PtrForEachEntryStart( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
+#define If_ManForEachLatchOutput( p, pObj, i ) \
+ Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
+// iterator over all objects in topological order
+#define If_ManForEachObj( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vObjs, pObj, i )
+// iterator over all objects in reverse topological order
+#define If_ManForEachObjReverse( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vObjsRev, pObj, i )
+// iterator over logic nodes
+#define If_ManForEachNode( p, pObj, i ) \
+ If_ManForEachObj( p, pObj, i ) if ( pObj->Type != IF_AND ) {} else
+// iterator over cuts of the node
+#define If_ObjForEachCut( pObj, pCut, i ) \
+ for ( i = 0; (i < (pObj)->pCutSet->nCuts) && ((pCut) = (pObj)->pCutSet->ppCuts[i]); i++ )
+// iterator over the leaves of the cut
+#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \
+ for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i++ )
+#define If_CutForEachLeafReverse( p, pCut, pLeaf, i ) \
+ for ( i = (int)(pCut)->nLeaves - 1; (i >= 0) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i-- )
+//#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \
+// for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, p->pPars->fLiftLeaves? (pCut)->pLeaves[i] >> 8 : (pCut)->pLeaves[i])); i++ )
+// iterator over the leaves of the sequential cut
+#define If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i ) \
+ for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i] >> 8)) && (((Shift) = ((pCut)->pLeaves[i] & 255)) >= 0); i++ )
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/*=== ifCore.c ===========================================================*/
+extern int If_ManPerformMapping( If_Man_t * p );
+extern int If_ManPerformMappingComb( If_Man_t * p );
+/*=== ifCut.c ============================================================*/
+extern int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut );
+extern void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut );
+extern int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut );
+extern void If_CutPrint( If_Man_t * p, If_Cut_t * pCut );
+extern void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut );
+extern void If_CutLift( If_Cut_t * pCut );
+extern void If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc );
+extern float If_CutAreaFlow( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutEdgeFlow( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutAreaDeref( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutAreaRef( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutEdgeDeref( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutEdgeRef( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutEdgeDerefed( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutEdgeRefed( If_Man_t * p, If_Cut_t * pCut );
+/*=== ifMan.c =============================================================*/
+extern If_Man_t * If_ManStart( If_Par_t * pPars );
+extern void If_ManRestart( If_Man_t * p );
+extern void If_ManStop( If_Man_t * p );
+extern If_Obj_t * If_ManCreateCi( If_Man_t * p );
+extern If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver );
+extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 );
+extern If_Obj_t * If_ManCreateXor( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 );
+extern If_Obj_t * If_ManCreateMux( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1, If_Obj_t * pCtrl );
+extern void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pRepr );
+extern void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId );
+extern void If_ManSetupCiCutSets( If_Man_t * p );
+extern If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManSetupSetAll( If_Man_t * p, int nCrossCut );
+/*=== ifMap.c =============================================================*/
+extern void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
+extern void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
+extern int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel );
+/*=== ifReduce.c ==========================================================*/
+extern void If_ManImproveMapping( If_Man_t * p );
+/*=== ifSeq.c =============================================================*/
+extern int If_ManPerformMappingSeq( If_Man_t * p );
+/*=== ifTime.c ============================================================*/
+extern float If_CutDelay( If_Man_t * p, If_Cut_t * pCut );
+extern void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float Required );
+/*=== ifTruth.c ===========================================================*/
+extern void If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 );
+/*=== ifUtil.c ============================================================*/
+extern void If_ManCleanNodeCopy( If_Man_t * p );
+extern void If_ManCleanCutData( If_Man_t * p );
+extern void If_ManCleanMarkV( If_Man_t * p );
+extern float If_ManDelayMax( If_Man_t * p, int fSeq );
+extern void If_ManComputeRequired( If_Man_t * p );
+extern float If_ManScanMapping( If_Man_t * p );
+extern float If_ManScanMappingDirect( If_Man_t * p );
+extern float If_ManScanMappingSeq( If_Man_t * p );
+extern void If_ManResetOriginalRefs( If_Man_t * p );
+extern int If_ManCrossCut( If_Man_t * p );
+
+extern Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p );
+extern void If_ManMarkMapping( If_Man_t * p );
+extern Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p );
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c
new file mode 100644
index 00000000..f7124703
--- /dev/null
+++ b/src/map/if/ifCore.c
@@ -0,0 +1,148 @@
+/**CFile****************************************************************
+
+ FileName [ifCore.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [The central part of the mapper.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifCore.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+extern int s_MappingTime;
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMapping( If_Man_t * p )
+{
+ p->pPars->fAreaOnly = p->pPars->fArea; // temporary
+
+ // create the CI cutsets
+ If_ManSetupCiCutSets( p );
+ // allocate memory for other cutsets
+ If_ManSetupSetAll( p, If_ManCrossCut(p) );
+ // derive reverse top order
+ p->vObjsRev = If_ManReverseOrder( p );
+
+ // try sequential mapping
+ if ( p->pPars->fSeqMap )
+ {
+ int RetValue = 1;
+ printf( "Currently sequential mapping is not performed.\n" );
+// RetValue = If_ManPerformMappingSeq( p );
+ return RetValue;
+// return 1;
+ }
+
+ return If_ManPerformMappingComb( p );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingComb( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int clkTotal = clock();
+ int i;
+
+ // set arrival times and fanout estimates
+ If_ManForEachCi( p, pObj, i )
+ {
+ If_ObjSetArrTime( pObj, p->pPars->pTimesArr[i] );
+ pObj->EstRefs = (float)1.0;
+ }
+
+ // delay oriented mapping
+ if ( p->pPars->fPreprocess && !p->pPars->fArea )
+ {
+ // map for delay
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay" );
+ // map for delay second option
+ p->pPars->fFancy = 1;
+ If_ManResetOriginalRefs( p );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay-2" );
+ p->pPars->fFancy = 0;
+ // map for area
+ p->pPars->fArea = 1;
+ If_ManResetOriginalRefs( p );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Area" );
+ p->pPars->fArea = 0;
+ }
+ else
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, "Delay" );
+
+ // try to improve area by expanding and reducing the cuts
+ if ( p->pPars->fExpRed && !p->pPars->fTruth )
+ If_ManImproveMapping( p );
+
+ // area flow oriented mapping
+ for ( i = 0; i < p->pPars->nFlowIters; i++ )
+ {
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1, 0, "Flow" );
+ if ( p->pPars->fExpRed && !p->pPars->fTruth )
+ If_ManImproveMapping( p );
+ }
+
+ // area oriented mapping
+ for ( i = 0; i < p->pPars->nAreaIters; i++ )
+ {
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2, 0, "Area" );
+ if ( p->pPars->fExpRed && !p->pPars->fTruth )
+ If_ManImproveMapping( p );
+ }
+
+ if ( p->pPars->fVerbose )
+ {
+// printf( "Total memory = %7.2f Mb. Peak cut memory = %7.2f Mb. ",
+// 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20),
+// 1.0 * p->nSetBytes * Mem_FixedReadMaxEntriesUsed(p->pMemSet) / (1<<20) );
+ PRT( "Total time", clock() - clkTotal );
+ }
+// printf( "Cross cut memory = %d.\n", Mem_FixedReadMaxEntriesUsed(p->pMemSet) );
+ s_MappingTime = clock() - clkTotal;
+ return 1;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c
new file mode 100644
index 00000000..cc842c19
--- /dev/null
+++ b/src/map/if/ifCut.c
@@ -0,0 +1,988 @@
+/**CFile****************************************************************
+
+ FileName [ifCut.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Cut computation.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifCut.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if pDom is contained in pCut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut )
+{
+ int i, k;
+ for ( i = 0; i < (int)pDom->nLeaves; i++ )
+ {
+ for ( k = 0; k < (int)pCut->nLeaves; k++ )
+ if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
+ break;
+ if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
+ return 0;
+ }
+ // every node in pDom is contained in pCut
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if pDom is equal to pCut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut )
+{
+ int i;
+ if ( (int)pDom->nLeaves != (int)pCut->nLeaves )
+ return 0;
+ for ( i = 0; i < (int)pDom->nLeaves; i++ )
+ if ( pDom->pLeaves[i] != pCut->pLeaves[i] )
+ return 0;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the cut is contained.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut )
+{
+ If_Cut_t * pTemp;
+ int i, k;
+ assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut );
+ for ( i = 0; i < pCutSet->nCuts; i++ )
+ {
+ pTemp = pCutSet->ppCuts[i];
+ if ( pTemp->nLeaves > pCut->nLeaves )
+ {
+ // do not fiter the first cut
+ if ( i == 0 )
+ continue;
+ // skip the non-contained cuts
+ if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
+ continue;
+ // check containment seriously
+ if ( If_CutCheckDominance( pCut, pTemp ) )
+ {
+// p->ppCuts[i] = p->ppCuts[p->nCuts-1];
+// p->ppCuts[p->nCuts-1] = pTemp;
+// p->nCuts--;
+// i--;
+ // remove contained cut
+ for ( k = i; k < pCutSet->nCuts; k++ )
+ pCutSet->ppCuts[k] = pCutSet->ppCuts[k+1];
+ pCutSet->ppCuts[pCutSet->nCuts] = pTemp;
+ pCutSet->nCuts--;
+ i--;
+ }
+ }
+ else
+ {
+ // skip the non-contained cuts
+ if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
+ continue;
+ // check containment seriously
+ if ( If_CutCheckDominance( pTemp, pCut ) )
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Merges two cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC )
+{
+ int i, k, c;
+ assert( pC0->nLeaves >= pC1->nLeaves );
+ // the case of the largest cut sizes
+ if ( pC0->nLeaves == pC->nLimit && pC1->nLeaves == pC->nLimit )
+ {
+ for ( i = 0; i < (int)pC0->nLeaves; i++ )
+ if ( pC0->pLeaves[i] != pC1->pLeaves[i] )
+ return 0;
+ for ( i = 0; i < (int)pC0->nLeaves; i++ )
+ pC->pLeaves[i] = pC0->pLeaves[i];
+ pC->nLeaves = pC0->nLeaves;
+ return 1;
+ }
+ // the case when one of the cuts is the largest
+ if ( pC0->nLeaves == pC->nLimit )
+ {
+ for ( i = 0; i < (int)pC1->nLeaves; i++ )
+ {
+ for ( k = (int)pC0->nLeaves - 1; k >= 0; k-- )
+ if ( pC0->pLeaves[k] == pC1->pLeaves[i] )
+ break;
+ if ( k == -1 ) // did not find
+ return 0;
+ }
+ for ( i = 0; i < (int)pC0->nLeaves; i++ )
+ pC->pLeaves[i] = pC0->pLeaves[i];
+ pC->nLeaves = pC0->nLeaves;
+ return 1;
+ }
+
+ // compare two cuts with different numbers
+ i = k = 0;
+ for ( c = 0; c < (int)pC->nLimit; c++ )
+ {
+ if ( k == (int)pC1->nLeaves )
+ {
+ if ( i == (int)pC0->nLeaves )
+ {
+ pC->nLeaves = c;
+ return 1;
+ }
+ pC->pLeaves[c] = pC0->pLeaves[i++];
+ continue;
+ }
+ if ( i == (int)pC0->nLeaves )
+ {
+ if ( k == (int)pC1->nLeaves )
+ {
+ pC->nLeaves = c;
+ return 1;
+ }
+ pC->pLeaves[c] = pC1->pLeaves[k++];
+ continue;
+ }
+ if ( pC0->pLeaves[i] < pC1->pLeaves[k] )
+ {
+ pC->pLeaves[c] = pC0->pLeaves[i++];
+ continue;
+ }
+ if ( pC0->pLeaves[i] > pC1->pLeaves[k] )
+ {
+ pC->pLeaves[c] = pC1->pLeaves[k++];
+ continue;
+ }
+ pC->pLeaves[c] = pC0->pLeaves[i++];
+ k++;
+ }
+ if ( i < (int)pC0->nLeaves || k < (int)pC1->nLeaves )
+ return 0;
+ pC->nLeaves = c;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Merges two cuts.]
+
+ Description [Special case when the cut is known to exist.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_CutMergeOrdered2( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC )
+{
+ int i, k, c;
+ assert( pC0->nLeaves >= pC1->nLeaves );
+ // copy the first cut
+ for ( i = 0; i < (int)pC0->nLeaves; i++ )
+ pC->pLeaves[i] = pC0->pLeaves[i];
+ pC->nLeaves = pC0->nLeaves;
+ // the case when one of the cuts is the largest
+ if ( pC0->nLeaves == pC->nLimit )
+ return 1;
+ // add nodes of the second cut
+ k = 0;
+ for ( i = 0; i < (int)pC1->nLeaves; i++ )
+ {
+ // find k-th node before which i-th node should be added
+ for ( ; k < (int)pC->nLeaves; k++ )
+ if ( pC->pLeaves[k] >= pC1->pLeaves[i] )
+ break;
+ // check the case when this should be the last node
+ if ( k == (int)pC->nLeaves )
+ {
+ pC->pLeaves[k++] = pC1->pLeaves[i];
+ pC->nLeaves++;
+ continue;
+ }
+ // check the case when equal node is found
+ if ( pC1->pLeaves[i] == pC->pLeaves[k] )
+ continue;
+ // add the node
+ for ( c = (int)pC->nLeaves; c > k; c-- )
+ pC->pLeaves[c] = pC->pLeaves[c-1];
+ pC->pLeaves[k++] = pC1->pLeaves[i];
+ pC->nLeaves++;
+ }
+/*
+ assert( pC->nLeaves <= pC->nLimit );
+ for ( i = 1; i < (int)pC->nLeaves; i++ )
+ assert( pC->pLeaves[i-1] < pC->pLeaves[i] );
+*/
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut )
+{
+ assert( pCut->nLimit > 0 );
+ // merge the nodes
+ if ( pCut0->nLeaves < pCut1->nLeaves )
+ {
+ if ( !If_CutMergeOrdered( pCut1, pCut0, pCut ) )
+ return 0;
+ }
+ else
+ {
+ if ( !If_CutMergeOrdered( pCut0, pCut1, pCut ) )
+ return 0;
+ }
+ pCut->uSign = pCut0->uSign | pCut1->uSign;
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutCompareDelay( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
+{
+ If_Cut_t * pC0 = *ppC0;
+ If_Cut_t * pC1 = *ppC1;
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutCompareDelayOld( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
+{
+ If_Cut_t * pC0 = *ppC0;
+ If_Cut_t * pC1 = *ppC1;
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares the object for FPGA mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutCompareArea( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
+{
+ If_Cut_t * pC0 = *ppC0;
+ If_Cut_t * pC1 = *ppC1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->AveRefs > pC1->AveRefs )
+ return -1;
+ if ( pC0->AveRefs < pC1->AveRefs )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sorts the cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSortCuts( If_Man_t * p, int Mode )
+{
+/*
+ // sort the cuts
+ if ( Mode || p->pPars->fArea ) // area
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea );
+ else if ( p->pPars->fFancy )
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld );
+ else
+ qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay );
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Comparison function for two cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_ManSortCompare( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1 )
+{
+ if ( p->SortMode == 1 ) // area
+ {
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->Edge < pC1->Edge - p->fEpsilon )
+ return -1;
+ if ( pC0->Edge > pC1->Edge + p->fEpsilon )
+ return 1;
+ if ( pC0->AveRefs > pC1->AveRefs )
+ return -1;
+ if ( pC0->AveRefs < pC1->AveRefs )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ return 0;
+ }
+ if ( p->SortMode == 0 ) // delay
+ {
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->Edge < pC1->Edge - p->fEpsilon )
+ return -1;
+ if ( pC0->Edge > pC1->Edge + p->fEpsilon )
+ return 1;
+ return 0;
+ }
+ assert( p->SortMode == 2 ); // delay old
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->Edge < pC1->Edge - p->fEpsilon )
+ return -1;
+ if ( pC0->Edge > pC1->Edge + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Comparison function for two cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_ManSortCompare_old( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1 )
+{
+ if ( p->SortMode == 1 ) // area
+ {
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->AveRefs > pC1->AveRefs )
+ return -1;
+ if ( pC0->AveRefs < pC1->AveRefs )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ return 0;
+ }
+ if ( p->SortMode == 0 ) // delay
+ {
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ return 0;
+ }
+ assert( p->SortMode == 2 ); // delay old
+ if ( pC0->Delay < pC1->Delay - p->fEpsilon )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + p->fEpsilon )
+ return 1;
+ if ( pC0->Area < pC1->Area - p->fEpsilon )
+ return -1;
+ if ( pC0->Area > pC1->Area + p->fEpsilon )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs incremental sorting of cuts.]
+
+ Description [Currently only the trivial sorting is implemented.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut )
+{
+// int Counter = 0;
+ int i;
+
+ // the new cut is the last one
+ assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+
+ // cut structure is empty
+ if ( pCutSet->nCuts == 0 )
+ {
+ pCutSet->nCuts++;
+ return;
+ }
+
+ // the cut will be added - find its place
+ for ( i = pCutSet->nCuts-1; i >= 0; i-- )
+ {
+// Counter++;
+ if ( If_ManSortCompare( p, pCutSet->ppCuts[i], pCut ) <= 0 )
+ break;
+ pCutSet->ppCuts[i+1] = pCutSet->ppCuts[i];
+ pCutSet->ppCuts[i] = pCut;
+ }
+// printf( "%d ", Counter );
+
+ // update the number of cuts
+ if ( pCutSet->nCuts < pCutSet->nCutsMax )
+ pCutSet->nCuts++;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutPrint( If_Man_t * p, If_Cut_t * pCut )
+{
+ unsigned i;
+ printf( "{" );
+ for ( i = 0; i < pCut->nLeaves; i++ )
+ printf( " %d", pCut->pLeaves[i] );
+ printf( " }\n" );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prints one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ unsigned i;
+ printf( "{" );
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ printf( " %d(%.2f/%.2f)", pLeaf->Id, If_ObjCutBest(pLeaf)->Delay, pLeaf->Required );
+ printf( " }\n" );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Moves the cut over the latch.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutLift( If_Cut_t * pCut )
+{
+ unsigned i;
+ for ( i = 0; i < pCut->nLeaves; i++ )
+ {
+ assert( (pCut->pLeaves[i] & 255) < 255 );
+ pCut->pLeaves[i]++;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc )
+{
+ int * pLeaves;
+ char * pPerm;
+ unsigned * pTruth;
+ // save old arrays
+ pLeaves = pCutDest->pLeaves;
+ pPerm = pCutDest->pPerm;
+ pTruth = pCutDest->pTruth;
+ // copy the cut info
+ memcpy( pCutDest, pCutSrc, p->nCutBytes );
+ // restore the arrays
+ pCutDest->pLeaves = pLeaves;
+ pCutDest->pPerm = pPerm;
+ pCutDest->pTruth = pTruth;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Computes area flow.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAreaFlow( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Flow;
+ int i;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ Flow = If_CutLutArea(p, pCut);
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ if ( pLeaf->nRefs == 0 )
+ Flow += If_ObjCutBest(pLeaf)->Area;
+ else if ( p->pPars->fSeqMap ) // seq
+ Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->nRefs;
+ else
+ {
+ assert( pLeaf->EstRefs > p->fEpsilon );
+ Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs;
+ }
+ }
+ return Flow;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area flow.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutEdgeFlow( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Flow;
+ int i;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ Flow = pCut->nLeaves;
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ if ( pLeaf->nRefs == 0 )
+ Flow += If_ObjCutBest(pLeaf)->Edge;
+ else if ( p->pPars->fSeqMap ) // seq
+ Flow += If_ObjCutBest(pLeaf)->Edge / pLeaf->nRefs;
+ else
+ {
+ assert( pLeaf->EstRefs > p->fEpsilon );
+ Flow += If_ObjCutBest(pLeaf)->Edge / pLeaf->EstRefs;
+ }
+ }
+ return Flow;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Average number of references of the leaves.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ int nRefsTotal, i;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ nRefsTotal = 0;
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ nRefsTotal += pLeaf->nRefs;
+ return ((float)nRefsTotal)/pCut->nLeaves;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAreaDeref( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Area;
+ int i;
+ Area = If_CutLutArea(p, pCut);
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ assert( pLeaf->nRefs > 0 );
+ if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) )
+ continue;
+ Area += If_CutAreaDeref( p, If_ObjCutBest(pLeaf) );
+ }
+ return Area;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAreaRef( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Area;
+ int i;
+ Area = If_CutLutArea(p, pCut);
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ assert( pLeaf->nRefs >= 0 );
+ if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) )
+ continue;
+ Area += If_CutAreaRef( p, If_ObjCutBest(pLeaf) );
+ }
+ return Area;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut )
+{
+ float aResult, aResult2;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ aResult2 = If_CutAreaRef( p, pCut );
+ aResult = If_CutAreaDeref( p, pCut );
+ assert( aResult > aResult2 - p->fEpsilon );
+ assert( aResult < aResult2 + p->fEpsilon );
+ return aResult;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut )
+{
+ float aResult, aResult2;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ aResult2 = If_CutAreaDeref( p, pCut );
+ aResult = If_CutAreaRef( p, pCut );
+ assert( aResult > aResult2 - p->fEpsilon );
+ assert( aResult < aResult2 + p->fEpsilon );
+ return aResult;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutEdgeDeref( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Edge;
+ int i;
+ Edge = pCut->nLeaves;
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ assert( pLeaf->nRefs > 0 );
+ if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) )
+ continue;
+ Edge += If_CutEdgeDeref( p, If_ObjCutBest(pLeaf) );
+ }
+ return Edge;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutEdgeRef( If_Man_t * p, If_Cut_t * pCut )
+{
+ If_Obj_t * pLeaf;
+ float Edge;
+ int i;
+ Edge = pCut->nLeaves;
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ assert( pLeaf->nRefs >= 0 );
+ if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) )
+ continue;
+ Edge += If_CutEdgeRef( p, If_ObjCutBest(pLeaf) );
+ }
+ return Edge;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes edge of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutEdgeDerefed( If_Man_t * p, If_Cut_t * pCut )
+{
+ float aResult, aResult2;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ aResult2 = If_CutEdgeRef( p, pCut );
+ aResult = If_CutEdgeDeref( p, pCut );
+ assert( aResult > aResult2 - p->fEpsilon );
+ assert( aResult < aResult2 + p->fEpsilon );
+ return aResult;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area of the first level.]
+
+ Description [The cut need to be derefed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutEdgeRefed( If_Man_t * p, If_Cut_t * pCut )
+{
+ float aResult, aResult2;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ aResult2 = If_CutEdgeDeref( p, pCut );
+ aResult = If_CutEdgeRef( p, pCut );
+ assert( aResult > aResult2 - p->fEpsilon );
+ assert( aResult < aResult2 + p->fEpsilon );
+ return aResult;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
new file mode 100644
index 00000000..6b21919b
--- /dev/null
+++ b/src/map/if/ifMan.c
@@ -0,0 +1,577 @@
+/**CFile****************************************************************
+
+ FileName [ifMan.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Mapping manager.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifMan.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static If_Obj_t * If_ManSetupObj( If_Man_t * p );
+
+static void If_ManCutSetRecycle( If_Man_t * p, If_Set_t * pSet ) { pSet->pNext = p->pFreeList; p->pFreeList = pSet; }
+static If_Set_t * If_ManCutSetFetch( If_Man_t * p ) { If_Set_t * pTemp = p->pFreeList; p->pFreeList = p->pFreeList->pNext; return pTemp; }
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Starts the AIG manager.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Man_t * If_ManStart( If_Par_t * pPars )
+{
+ If_Man_t * p;
+ // start the manager
+ p = ALLOC( If_Man_t, 1 );
+ memset( p, 0, sizeof(If_Man_t) );
+ p->pPars = pPars;
+ p->fEpsilon = (float)0.001;
+ // allocate arrays for nodes
+ p->vCis = Vec_PtrAlloc( 100 );
+ p->vCos = Vec_PtrAlloc( 100 );
+ p->vObjs = Vec_PtrAlloc( 100 );
+// p->vMapped = Vec_PtrAlloc( 100 );
+ p->vTemp = Vec_PtrAlloc( 100 );
+ // prepare the memory manager
+ p->nTruthWords = p->pPars->fTruth? If_CutTruthWords( p->pPars->nLutSize ) : 0;
+ p->nPermWords = p->pPars->fUsePerm? If_CutPermWords( p->pPars->nLutSize ) : 0;
+ p->nObjBytes = sizeof(If_Obj_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords);
+ p->nCutBytes = sizeof(If_Cut_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords);
+ p->nSetBytes = sizeof(If_Set_t) + (sizeof(If_Cut_t *) + p->nCutBytes) * (p->pPars->nCutsMax + 1);
+ p->pMemObj = Mem_FixedStart( p->nObjBytes );
+// p->pMemSet = Mem_FixedStart( p->nSetBytes );
+ // report expected memory usage
+ if ( p->pPars->fVerbose )
+ printf( "K = %d. Memory (bytes): Truth = %4d. Cut = %4d. Obj = %4d. Set = %4d.\n",
+ p->pPars->nLutSize, 4 * p->nTruthWords, p->nCutBytes, p->nObjBytes, p->nSetBytes );
+ // room for temporary truth tables
+ p->puTemp[0] = p->pPars->fTruth? ALLOC( unsigned, 4 * p->nTruthWords ) : NULL;
+ p->puTemp[1] = p->puTemp[0] + p->nTruthWords;
+ p->puTemp[2] = p->puTemp[1] + p->nTruthWords;
+ p->puTemp[3] = p->puTemp[2] + p->nTruthWords;
+ // create the constant node
+ p->pConst1 = If_ManSetupObj( p );
+ p->pConst1->Type = IF_CONST1;
+ p->pConst1->fPhase = 1;
+ p->nObjs[IF_CONST1]++;
+ return p;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManRestart( If_Man_t * p )
+{
+ FREE( p->pMemCi );
+ Vec_PtrClear( p->vCis );
+ Vec_PtrClear( p->vCos );
+ Vec_PtrClear( p->vObjs );
+// Vec_PtrClear( p->vMapped );
+ Vec_PtrClear( p->vTemp );
+ Mem_FixedRestart( p->pMemObj );
+ // create the constant node
+ p->pConst1 = If_ManSetupObj( p );
+ p->pConst1->Type = IF_CONST1;
+ p->pConst1->fPhase = 1;
+ // reset the counter of other nodes
+ p->nObjs[IF_CI] = p->nObjs[IF_CO] = p->nObjs[IF_AND] = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManStop( If_Man_t * p )
+{
+// printf( "Small support = %d.\n", p->nSmallSupp );
+ Vec_PtrFree( p->vCis );
+ Vec_PtrFree( p->vCos );
+ Vec_PtrFree( p->vObjs );
+// Vec_PtrFree( p->vMapped );
+ Vec_PtrFree( p->vTemp );
+ if ( p->vObjsRev ) Vec_PtrFree( p->vObjsRev );
+ if ( p->vLatchOrder ) Vec_PtrFree( p->vLatchOrder );
+ if ( p->vLags ) Vec_IntFree( p->vLags );
+ Mem_FixedStop( p->pMemObj, 0 );
+ FREE( p->pMemCi );
+ FREE( p->pMemAnd );
+ FREE( p->puTemp[0] );
+ // free pars memory
+ if ( p->pPars->pTimesArr )
+ FREE( p->pPars->pTimesArr );
+ if ( p->pPars->pTimesReq )
+ FREE( p->pPars->pTimesReq );
+ if ( p->pManTim )
+ Tim_ManStop( p->pManTim );
+ free( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates primary input.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManCreateCi( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ pObj = If_ManSetupObj( p );
+ pObj->Type = IF_CI;
+ pObj->IdPio = Vec_PtrSize( p->vCis );
+ Vec_PtrPush( p->vCis, pObj );
+ p->nObjs[IF_CI]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates primary output with the given driver.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver )
+{
+ If_Obj_t * pObj;
+ pObj = If_ManSetupObj( p );
+ pObj->IdPio = Vec_PtrSize( p->vCos );
+ Vec_PtrPush( p->vCos, pObj );
+ pObj->Type = IF_CO;
+ pObj->fCompl0 = If_IsComplement(pDriver); pDriver = If_Regular(pDriver);
+ pObj->pFanin0 = pDriver; pDriver->nRefs++;
+ pObj->Level = pDriver->Level;
+ p->nObjs[IF_CO]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Create the new node assuming it does not exist.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 )
+{
+ If_Obj_t * pObj;
+ // perform constant propagation
+ if ( pFan0 == pFan1 )
+ return pFan0;
+ if ( pFan0 == If_Not(pFan1) )
+ return If_Not(p->pConst1);
+ if ( If_Regular(pFan0) == p->pConst1 )
+ return pFan0 == p->pConst1 ? pFan1 : If_Not(p->pConst1);
+ if ( If_Regular(pFan1) == p->pConst1 )
+ return pFan1 == p->pConst1 ? pFan0 : If_Not(p->pConst1);
+ // get memory for the new object
+ pObj = If_ManSetupObj( p );
+ pObj->Type = IF_AND;
+ pObj->fCompl0 = If_IsComplement(pFan0); pFan0 = If_Regular(pFan0);
+ pObj->fCompl1 = If_IsComplement(pFan1); pFan1 = If_Regular(pFan1);
+ pObj->pFanin0 = pFan0; pFan0->nRefs++; pFan0->nVisits++; pFan0->nVisitsCopy++;
+ pObj->pFanin1 = pFan1; pFan1->nRefs++; pFan1->nVisits++; pFan1->nVisitsCopy++;
+ pObj->fPhase = (pObj->fCompl0 ^ pFan0->fPhase) & (pObj->fCompl1 ^ pFan1->fPhase);
+ pObj->Level = 1 + IF_MAX( pFan0->Level, pFan1->Level );
+ if ( p->nLevelMax < (int)pObj->Level )
+ p->nLevelMax = (int)pObj->Level;
+ p->nObjs[IF_AND]++;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Create the new node assuming it does not exist.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManCreateXor( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1 )
+{
+ If_Obj_t * pRes1, * pRes2;
+ pRes1 = If_ManCreateAnd( p, If_Not(pFan0), pFan1 );
+ pRes2 = If_ManCreateAnd( p, pFan0, If_Not(pFan1) );
+ return If_Not( If_ManCreateAnd( p, If_Not(pRes1), If_Not(pRes2) ) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Create the new node assuming it does not exist.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManCreateMux( If_Man_t * p, If_Obj_t * pFan0, If_Obj_t * pFan1, If_Obj_t * pCtrl )
+{
+ If_Obj_t * pRes1, * pRes2;
+ pRes1 = If_ManCreateAnd( p, pFan0, If_Not(pCtrl) );
+ pRes2 = If_ManCreateAnd( p, pFan1, pCtrl );
+ return If_Not( If_ManCreateAnd( p, If_Not(pRes1), If_Not(pRes2) ) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Creates the choice node.]
+
+ Description [Should be called after the equivalence class nodes are linked.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pTemp;
+ // mark the node as a representative if its class
+ assert( pObj->fRepr == 0 );
+ pObj->fRepr = 1;
+ // update the level of this node (needed for correct required time computation)
+ for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ {
+ pObj->Level = IF_MAX( pObj->Level, pTemp->Level );
+ pTemp->nVisits++; pTemp->nVisitsCopy++;
+ }
+ // mark the largest level
+ if ( p->nLevelMax < (int)pObj->Level )
+ p->nLevelMax = (int)pObj->Level;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupCut( If_Man_t * p, If_Cut_t * pCut )
+{
+ memset( pCut, 0, sizeof(If_Cut_t) );
+ pCut->nLimit = p->pPars->nLutSize;
+ pCut->pLeaves = (int *)(pCut + 1);
+ if ( p->pPars->fUsePerm )
+ pCut->pPerm = (char *)(pCut->pLeaves + p->pPars->nLutSize);
+ if ( p->pPars->fTruth )
+ pCut->pTruth = pCut->pLeaves + p->pPars->nLutSize + p->nPermWords;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cutset.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupSet( If_Man_t * p, If_Set_t * pSet )
+{
+ char * pArray;
+ int i;
+ pSet->nCuts = 0;
+ pSet->nCutsMax = p->pPars->nCutsMax;
+ pSet->ppCuts = (If_Cut_t **)(pSet + 1);
+ pArray = (char *)pSet->ppCuts + sizeof(If_Cut_t *) * (pSet->nCutsMax+1);
+ for ( i = 0; i <= pSet->nCutsMax; i++ )
+ {
+ pSet->ppCuts[i] = (If_Cut_t *)(pArray + i * p->nCutBytes);
+ If_ManSetupCut( p, pSet->ppCuts[i] );
+ }
+// pArray += (pSet->nCutsMax + 1) * p->nCutBytes;
+// assert( ((char *)pArray) - ((char *)pSet) == p->nSetBytes );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId )
+{
+ pCut->fCompl = 0;
+ pCut->nLimit = p->pPars->nLutSize;
+ pCut->nLeaves = 1;
+ pCut->pLeaves[0] = p->pPars->fLiftLeaves? (ObjId << 8) : ObjId;
+ pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] );
+ // set up elementary truth table of the unit cut
+ if ( p->pPars->fTruth )
+ {
+ int i, nTruthWords;
+ nTruthWords = pCut->nLimit <= 5 ? 1 : (1 << (pCut->nLimit - 5));
+ for ( i = 0; i < nTruthWords; i++ )
+ If_CutTruth(pCut)[i] = 0xAAAAAAAA;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for the node with cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManSetupObj( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ // get memory for the object
+ pObj = (If_Obj_t *)Mem_FixedEntryFetch( p->pMemObj );
+ memset( pObj, 0, sizeof(If_Obj_t) );
+ If_ManSetupCut( p, &pObj->CutBest );
+ // assign ID and save
+ pObj->Id = Vec_PtrSize(p->vObjs);
+ Vec_PtrPush( p->vObjs, pObj );
+ // set the required times
+ pObj->Required = IF_FLOAT_LARGE;
+ return pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupCiCutSets( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ assert( p->pMemCi == NULL );
+ // create elementary cuts for the CIs
+ If_ManForEachCi( p, pObj, i )
+ If_ManSetupCutTriv( p, &pObj->CutBest, pObj->Id );
+ // create elementary cutsets for the CIs
+ p->pMemCi = (If_Set_t *)malloc( If_ManCiNum(p) * (sizeof(If_Set_t) + sizeof(void *)) );
+ If_ManForEachCi( p, pObj, i )
+ {
+ pObj->pCutSet = (If_Set_t *)((char *)p->pMemCi + i * (sizeof(If_Set_t) + sizeof(void *)));
+ pObj->pCutSet->nCuts = 1;
+ pObj->pCutSet->nCutsMax = p->pPars->nCutsMax;
+ pObj->pCutSet->ppCuts = (If_Cut_t **)(pObj->pCutSet + 1);
+ pObj->pCutSet->ppCuts[0] = &pObj->CutBest;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares cutset of the node.]
+
+ Description [Elementary cutset will be added last.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ assert( If_ObjIsAnd(pObj) );
+ assert( pObj->pCutSet == NULL );
+// pObj->pCutSet = (If_Set_t *)Mem_FixedEntryFetch( p->pMemSet );
+// If_ManSetupSet( p, pObj->pCutSet );
+
+ pObj->pCutSet = If_ManCutSetFetch( p );
+ pObj->pCutSet->nCuts = 0;
+ pObj->pCutSet->nCutsMax = p->pPars->nCutsMax;
+
+ return pObj->pCutSet;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pFanin;
+ assert( If_ObjIsAnd(pObj) );
+ // consider the node
+ assert( pObj->nVisits >= 0 );
+ if ( pObj->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pObj->pCutSet );
+ If_ManCutSetRecycle( p, pObj->pCutSet );
+ pObj->pCutSet = NULL;
+ }
+ // consider the first fanin
+ pFanin = If_ObjFanin0(pObj);
+ assert( pFanin->nVisits > 0 );
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet );
+ If_ManCutSetRecycle( p, pFanin->pCutSet );
+ pFanin->pCutSet = NULL;
+ }
+ // consider the second fanin
+ pFanin = If_ObjFanin1(pObj);
+ assert( pFanin->nVisits > 0 );
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet );
+ If_ManCutSetRecycle( p, pFanin->pCutSet );
+ pFanin->pCutSet = NULL;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pTemp;
+ assert( If_ObjIsAnd(pObj) );
+ assert( pObj->fRepr );
+ assert( pObj->nVisits > 0 );
+ // consider the nodes in the choice class
+ for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ {
+ assert( pTemp == pObj || pTemp->nVisits == 1 );
+ if ( --pTemp->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pTemp->pCutSet );
+ If_ManCutSetRecycle( p, pTemp->pCutSet );
+ pTemp->pCutSet = NULL;
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupSetAll( If_Man_t * p, int nCrossCut )
+{
+ If_Set_t * pCutSet;
+ int i, nCutSets;
+ nCutSets = 128 + nCrossCut;
+ p->pFreeList = p->pMemAnd = pCutSet = (If_Set_t *)malloc( nCutSets * p->nSetBytes );
+ for ( i = 0; i < nCutSets; i++ )
+ {
+ If_ManSetupSet( p, pCutSet );
+ if ( i == nCutSets - 1 )
+ pCutSet->pNext = NULL;
+ else
+ pCutSet->pNext = (If_Set_t *)( (char *)pCutSet + p->nSetBytes );
+ pCutSet = pCutSet->pNext;
+ }
+ assert( pCutSet == NULL );
+
+ if ( p->pPars->fVerbose )
+ {
+ printf( "Node = %7d. Ch = %5d. Total mem = %7.2f Mb. Peak cut mem = %7.2f Mb.\n",
+ If_ManAndNum(p), p->nChoices,
+ 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20),
+ 1.0 * p->nSetBytes * nCrossCut / (1<<20) );
+ }
+// printf( "Cross cut = %d.\n", nCrossCut );
+
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
new file mode 100644
index 00000000..1ac5ef21
--- /dev/null
+++ b/src/map/if/ifMap.c
@@ -0,0 +1,350 @@
+/**CFile****************************************************************
+
+ FileName [ifMap.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Mapping procedures.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifMap.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of 1s in the signature.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_WordCountOnes( unsigned uWord )
+{
+ uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
+ uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
+ uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
+ uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
+ return (uWord & 0x0000FFFF) + (uWord>>16);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Finds the best cut for the given node.]
+
+ Description [Mapping modes: delay (0), area flow (1), area (2).]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess )
+{
+ If_Set_t * pCutSet;
+ If_Cut_t * pCut0, * pCut1, * pCut;
+ int i, k;
+
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 1 );
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 1 );
+
+ // prepare
+ if ( !p->pPars->fSeqMap )
+ {
+ if ( Mode == 0 )
+ pObj->EstRefs = (float)pObj->nRefs;
+ else if ( Mode == 1 )
+ pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
+ }
+ if ( Mode && pObj->nRefs > 0 )
+ If_CutAreaDeref( p, If_ObjCutBest(pObj) );
+
+ // prepare the cutset
+ pCutSet = If_ManSetupNodeCutSet( p, pObj );
+
+ // get the current assigned best cut
+ pCut = If_ObjCutBest(pObj);
+ if ( pCut->nLeaves > 0 )
+ {
+ // recompute the parameters of the best cut
+ pCut->Delay = If_CutDelay( p, pCut );
+ assert( pCut->Delay <= pObj->Required + p->fEpsilon );
+ pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut ) : If_CutAreaFlow( p, pCut );
+ if ( p->pPars->fEdge )
+ pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( p, pCut );
+ // save the best cut from the previous iteration
+ if ( !fPreprocess )
+ If_CutCopy( p, pCutSet->ppCuts[pCutSet->nCuts++], pCut );
+ }
+
+ // generate cuts
+ If_ObjForEachCut( pObj->pFanin0, pCut0, i )
+ If_ObjForEachCut( pObj->pFanin1, pCut1, k )
+ {
+ // get the next free cut
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+ pCut = pCutSet->ppCuts[pCutSet->nCuts];
+ // make sure K-feasible cut exists
+ if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize )
+ continue;
+ // merge the nodes
+ if ( !If_CutMerge( pCut0, pCut1, pCut ) )
+ continue;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ p->nCutsMerged++;
+ // check if this cut is contained in any of the available cuts
+// if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts
+ if ( If_CutFilter( pCutSet, pCut ) )
+ continue;
+ // compute the truth table
+ pCut->fCompl = 0;
+ if ( p->pPars->fTruth )
+ If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 );
+ // compute the application-specific cost and depth
+ pCut->fUser = (p->pPars->pFuncCost != NULL);
+ pCut->Cost = p->pPars->pFuncCost? p->pPars->pFuncCost(pCut) : 0;
+ if ( pCut->Cost == IF_COST_MAX )
+ continue;
+ // check if the cut satisfies the required times
+ pCut->Delay = If_CutDelay( p, pCut );
+// printf( "%.2f ", pCut->Delay );
+ if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
+ continue;
+ // compute area of the cut (this area may depend on the application specific cost)
+ pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut ) : If_CutAreaFlow( p, pCut );
+ if ( p->pPars->fEdge )
+ pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( p, pCut );
+ pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
+ // insert the cut into storage
+ If_CutSort( p, pCutSet, pCut );
+ }
+ assert( pCutSet->nCuts > 0 );
+
+ // add the trivial cut to the set
+ If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
+
+ // update the best cut
+ if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
+ If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
+ assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
+
+ // ref the selected cut
+ if ( Mode && pObj->nRefs > 0 )
+ If_CutAreaRef( p, If_ObjCutBest(pObj) );
+
+ // call the user specified function for each cut
+ if ( p->pPars->pFuncUser )
+ If_ObjForEachCut( pObj, pCut, i )
+ p->pPars->pFuncUser( p, pObj, pCut );
+
+ // free the cuts
+ If_ManDerefNodeCutSet( p, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Finds the best cut for the choice node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess )
+{
+ If_Set_t * pCutSet;
+ If_Obj_t * pTemp;
+ If_Cut_t * pCutTemp, * pCut;
+ int i;
+ assert( pObj->pEquiv != NULL );
+
+ // prepare
+ if ( Mode && pObj->nRefs > 0 )
+ If_CutAreaDeref( p, If_ObjCutBest(pObj) );
+
+ // remove elementary cuts
+ for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ pTemp->pCutSet->nCuts--;
+
+ // update the cutset of the node
+ pCutSet = pObj->pCutSet;
+
+ // generate cuts
+ for ( pTemp = pObj->pEquiv; pTemp; pTemp = pTemp->pEquiv )
+ {
+ assert( pTemp->nRefs == 0 );
+ assert( p->pPars->fSeqMap || pTemp->pCutSet->nCuts > 0 );
+ // go through the cuts of this node
+ If_ObjForEachCut( pTemp, pCutTemp, i )
+ {
+ assert( p->pPars->fSeqMap || pCutTemp->nLeaves > 1 );
+ // get the next free cut
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+ pCut = pCutSet->ppCuts[pCutSet->nCuts];
+ // copy the cut into storage
+ If_CutCopy( p, pCut, pCutTemp );
+ // check if this cut is contained in any of the available cuts
+ if ( If_CutFilter( pCutSet, pCut ) )
+ continue;
+ // check if the cut satisfies the required times
+ assert( pCut->Delay == If_CutDelay( p, pCut ) );
+ if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
+ continue;
+ // set the phase attribute
+ assert( pCut->fCompl == 0 );
+ pCut->fCompl ^= (pObj->fPhase ^ pTemp->fPhase); // why ^= ?
+ // compute area of the cut (this area may depend on the application specific cost)
+ pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut ) : If_CutAreaFlow( p, pCut );
+ if ( p->pPars->fEdge )
+ pCut->Edge = (Mode == 2)? If_CutEdgeDerefed( p, pCut ) : If_CutEdgeFlow( p, pCut );
+ pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
+ // insert the cut into storage
+ If_CutSort( p, pCutSet, pCut );
+ }
+ }
+ assert( pCutSet->nCuts > 0 );
+
+ // add the trivial cut to the set
+ If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
+
+ // update the best cut
+ if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
+ If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
+ assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
+
+ // ref the selected cut
+ if ( Mode && pObj->nRefs > 0 )
+ If_CutAreaRef( p, If_ObjCutBest(pObj) );
+
+ // free the cuts
+ If_ManDerefChoiceCutSet( p, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs one mapping pass over all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel )
+{
+// ProgressBar * pProgress;
+ If_Obj_t * pObj;
+ int i, clk = clock();
+ float arrTime;
+ assert( Mode >= 0 && Mode <= 2 );
+ // set the sorting function
+ if ( Mode || p->pPars->fArea ) // area
+ p->SortMode = 1;
+ else if ( p->pPars->fFancy )
+ p->SortMode = 2;
+ else
+ p->SortMode = 0;
+ // set the cut number
+ p->nCutsUsed = nCutsUsed;
+ p->nCutsMerged = 0;
+ // make sure the visit counters are all zero
+ If_ManForEachNode( p, pObj, i )
+ assert( pObj->nVisits == pObj->nVisitsCopy );
+ // map the internal nodes
+ if ( p->pManTim != NULL )
+ {
+ Tim_ManIncrementTravId( p->pManTim );
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsAnd(pObj) )
+ {
+ If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess );
+ if ( pObj->fRepr )
+ If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess );
+ }
+ else if ( If_ObjIsCi(pObj) )
+ {
+ arrTime = Tim_ManGetPiArrival( p->pManTim, pObj->IdPio );
+ If_ObjSetArrTime( pObj, arrTime );
+/*
+ if ( pObj->IdPio >= 2000 )
+ {
+ int x = 0;
+ printf( "+%d %6.3f ", pObj->IdPio, arrTime );
+ }
+*/
+ }
+ else if ( If_ObjIsCo(pObj) )
+ {
+ arrTime = If_ObjArrTime( If_ObjFanin0(pObj) );
+ Tim_ManSetPoArrival( p->pManTim, pObj->IdPio, arrTime );
+ }
+ else if ( If_ObjIsConst1(pObj) )
+ {
+ }
+ else
+ assert( 0 );
+ }
+// Tim_ManPrint( p->pManTim );
+ }
+ else
+ {
+ // pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
+ If_ManForEachNode( p, pObj, i )
+ {
+ // Extra_ProgressBarUpdate( pProgress, i, pLabel );
+ If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess );
+ if ( pObj->fRepr )
+ If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess );
+ }
+ }
+// Extra_ProgressBarStop( pProgress );
+ // make sure the visit counters are all zero
+ If_ManForEachNode( p, pObj, i )
+ assert( pObj->nVisits == 0 );
+ // compute required times and stats
+ If_ManComputeRequired( p );
+// Tim_ManPrint( p->pManTim );
+ if ( p->pPars->fVerbose )
+ {
+ char Symb = fPreprocess? 'P' : ((Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A'));
+ printf( "%c: Del = %7.2f. Ar = %9.1f. Edge = %8d. Cut = %8d. ",
+ Symb, p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
+ PRT( "T", clock() - clk );
+// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n",
+// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ }
+ return 1;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c
new file mode 100644
index 00000000..0912a965
--- /dev/null
+++ b/src/map/if/ifReduce.c
@@ -0,0 +1,575 @@
+/**CFile****************************************************************
+
+ FileName [ifExpand.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Incremental improvement of current mapping.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifExpand.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static void If_ManImproveReduce( If_Man_t * p, int nLimit );
+static void If_ManImproveExpand( If_Man_t * p, int nLimit );
+static void If_ManImproveNodeExpand( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited );
+static void If_ManImproveNodePrepare( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited );
+static void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront );
+static void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Improves current mapping using expand/Expand of one cut.]
+
+ Description [Assumes current mapping assigned and required times computed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveMapping( If_Man_t * p )
+{
+ int clk;
+
+ clk = clock();
+ If_ManImproveExpand( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "E: Del = %7.2f. Ar = %9.1f. Edge = %8d. Cut = %8d. ",
+ p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
+ PRT( "T", clock() - clk );
+ }
+
+/*
+ clk = clock();
+ If_ManImproveReduce( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p, 0 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "R: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+*/
+/*
+ clk = clock();
+ If_ManImproveExpand( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p, 0 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "E: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveExpand( If_Man_t * p, int nLimit )
+{
+ Vec_Ptr_t * vFront, * vFrontOld, * vVisited;
+ If_Obj_t * pObj;
+ int i;
+ vFront = Vec_PtrAlloc( nLimit );
+ vFrontOld = Vec_PtrAlloc( nLimit );
+ vVisited = Vec_PtrAlloc( 100 );
+ // iterate through all nodes in the topological order
+ If_ManForEachNode( p, pObj, i )
+ If_ManImproveNodeExpand( p, pObj, nLimit, vFront, vFrontOld, vVisited );
+ Vec_PtrFree( vFront );
+ Vec_PtrFree( vFrontOld );
+ Vec_PtrFree( vVisited );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of nodes with no external fanout.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveCutCost( If_Man_t * p, Vec_Ptr_t * vFront )
+{
+ If_Obj_t * pFanin;
+ int i, Counter = 0;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ if ( pFanin->nRefs == 0 )
+ Counter++;
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeExpand( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ If_Cut_t * pCut;
+ int CostBef, CostAft, i;
+ float DelayOld, AreaBef, AreaAft;
+ pCut = If_ObjCutBest(pObj);
+ pCut->Delay = If_CutDelay( p, pCut );
+ assert( pCut->Delay <= pObj->Required + p->fEpsilon );
+ if ( pObj->nRefs == 0 )
+ return;
+ // get the delay
+ DelayOld = pCut->Delay;
+ // get the area
+ AreaBef = If_CutAreaRefed( p, pCut );
+// if ( AreaBef == 1 )
+// return;
+ // the cut is non-trivial
+ If_ManImproveNodePrepare( p, pObj, nLimit, vFront, vFrontOld, vVisited );
+ // iteratively modify the cut
+ If_CutAreaDeref( p, pCut );
+ CostBef = If_ManImproveCutCost( p, vFront );
+ If_ManImproveNodeFaninCompact( p, pObj, nLimit, vFront, vVisited );
+ CostAft = If_ManImproveCutCost( p, vFront );
+ If_CutAreaRef( p, pCut );
+ assert( CostBef >= CostAft );
+ // clean up
+ Vec_PtrForEachEntry( vVisited, pFanin, i )
+ pFanin->fMark = 0;
+ // update the node
+ If_ManImproveNodeUpdate( p, pObj, vFront );
+ pCut->Delay = If_CutDelay( p, pCut );
+ // get the new area
+ AreaAft = If_CutAreaRefed( p, pCut );
+ if ( AreaAft > AreaBef || pCut->Delay > pObj->Required + p->fEpsilon )
+ {
+ If_ManImproveNodeUpdate( p, pObj, vFrontOld );
+ AreaAft = If_CutAreaRefed( p, pCut );
+ assert( AreaAft == AreaBef );
+ pCut->Delay = DelayOld;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveMark_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vVisited )
+{
+ if ( pObj->fMark )
+ return;
+ assert( If_ObjIsAnd(pObj) );
+ If_ManImproveMark_rec( p, If_ObjFanin0(pObj), vVisited );
+ If_ManImproveMark_rec( p, If_ObjFanin1(pObj), vVisited );
+ Vec_PtrPush( vVisited, pObj );
+ pObj->fMark = 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares node mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodePrepare( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited )
+{
+ If_Cut_t * pCut;
+ If_Obj_t * pLeaf;
+ int i;
+ Vec_PtrClear( vFront );
+ Vec_PtrClear( vFrontOld );
+ Vec_PtrClear( vVisited );
+ // expand the cut downwards from the given place
+ pCut = If_ObjCutBest(pObj);
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ Vec_PtrPush( vFront, pLeaf );
+ Vec_PtrPush( vFrontOld, pLeaf );
+ Vec_PtrPush( vVisited, pLeaf );
+ pLeaf->fMark = 1;
+ }
+ // mark the nodes in the cone
+ If_ManImproveMark_rec( p, pObj, vVisited );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Updates the frontier.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront )
+{
+ If_Cut_t * pCut;
+ If_Obj_t * pFanin;
+ int i;
+ pCut = If_ObjCutBest(pObj);
+ // deref node's cut
+ If_CutAreaDeref( p, pCut );
+ // update the node's cut
+ pCut->nLeaves = Vec_PtrSize(vFront);
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ pCut->pLeaves[i] = pFanin->Id;
+ // ref the new cut
+ If_CutAreaRef( p, pCut );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the number of fanins will grow.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeWillGrow( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pFanin0, * pFanin1;
+ assert( If_ObjIsAnd(pObj) );
+ pFanin0 = If_ObjFanin0(pObj);
+ pFanin1 = If_ObjFanin1(pObj);
+ return !pFanin0->fMark && !pFanin1->fMark;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the increase in the number of fanins with no external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCost( If_Man_t * p, If_Obj_t * pObj )
+{
+ int Counter = 0;
+ assert( If_ObjIsAnd(pObj) );
+ // check if the node has external refs
+ if ( pObj->nRefs == 0 )
+ Counter--;
+ // increment the number of fanins without external refs
+ if ( !If_ObjFanin0(pObj)->fMark && If_ObjFanin0(pObj)->nRefs == 0 )
+ Counter++;
+ // increment the number of fanins without external refs
+ if ( !If_ObjFanin1(pObj)->fMark && If_ObjFanin1(pObj)->nRefs == 0 )
+ Counter++;
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Updates the frontier.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeFaninUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ assert( If_ObjIsAnd(pObj) );
+ Vec_PtrRemove( vFront, pObj );
+ pFanin = If_ObjFanin0(pObj);
+ if ( !pFanin->fMark )
+ {
+ Vec_PtrPush( vFront, pFanin );
+ Vec_PtrPush( vVisited, pFanin );
+ pFanin->fMark = 1;
+ }
+ pFanin = If_ObjFanin1(pObj);
+ if ( !pFanin->fMark )
+ {
+ Vec_PtrPush( vFront, pFanin );
+ Vec_PtrPush( vVisited, pFanin );
+ pFanin->fMark = 1;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact0( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsCi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeWillGrow(p, pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact1( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsCi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) < 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact2( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsCi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact_int( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ if ( If_ManImproveNodeFaninCompact0(p, pObj, nLimit, vFront, vVisited) )
+ return 1;
+ if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact1(p, pObj, nLimit, vFront, vVisited) )
+ return 1;
+// if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact2(p, pObj, nLimit, vFront, vVisited) )
+// return 1;
+ assert( Vec_PtrSize(vFront) <= nLimit );
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ while ( If_ManImproveNodeFaninCompact_int( p, pObj, nLimit, vFront, vVisited ) );
+}
+
+
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs fast mapping for one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit )
+{
+/*
+ If_Cut_t * pCut, * pCut0, * pCut1, * pCutR;
+ If_Obj_t * pFanin0, * pFanin1;
+ float AreaBef, AreaAft;
+ int RetValue;
+
+ assert( nLimit <= 32 );
+ assert( If_ObjIsAnd(pObj) );
+ // get the fanins
+ pFanin0 = If_ObjFanin0(pObj);
+ pFanin1 = If_ObjFanin1(pObj);
+ // get the cuts
+ pCut = If_ObjCutBest(pObj);
+ pCut0 = If_ObjIsCi(pFanin0) ? If_ObjCutTriv(pFanin0) : If_ObjCutBest(pFanin0);
+ pCut1 = If_ObjIsCi(pFanin1) ? If_ObjCutTriv(pFanin1) : If_ObjCutBest(pFanin1);
+ assert( pCut->Delay <= pObj->Required + p->fEpsilon );
+
+ // deref the cut if the node is refed
+ if ( pObj->nRefs > 0 )
+ If_CutAreaDeref( p, pCut );
+ // get the area
+ AreaBef = If_CutAreaDerefed( p, pCut );
+ // get the fanin support
+ if ( pFanin0->nRefs > 2 && pCut0->Delay < pObj->Required + p->fEpsilon )
+// if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results
+ {
+ pCut0 = If_ObjCutTriv(pFanin0);
+ }
+ // get the fanin support
+ if ( pFanin1->nRefs > 2 && pCut1->Delay < pObj->Required + p->fEpsilon )
+// if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR )
+ {
+ pCut1 = If_ObjCutTriv(pFanin1);
+ }
+
+ // merge the cuts
+ pCutR = p->ppCuts[0];
+ RetValue = If_CutMerge( pCut0, pCut1, pCutR );
+ // try very simple cut
+ if ( !RetValue )
+ {
+ RetValue = If_CutMerge( If_ObjCutTriv(pFanin0), If_ObjCutTriv(pFanin1), pCutR );
+ assert( RetValue == 1 );
+ }
+ if ( RetValue )
+ {
+ pCutR->Delay = If_CutDelay( p, pCutR );
+ AreaAft = If_CutAreaDerefed( p, pCutR );
+ // update the best cut
+ if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon )
+ If_CutCopy( p, pCut, pCutR );
+ }
+ // recompute the delay of the best cut
+ pCut->Delay = If_CutDelay( p, pCut );
+ // ref the cut if the node is refed
+ if ( pObj->nRefs > 0 )
+ If_CutRef( p, pCut );
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveReduce( If_Man_t * p, int nLimit )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachNode( p, pObj, i )
+ If_ManImproveNodeReduce( p, pObj, nLimit );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c
new file mode 100644
index 00000000..8d1de8c1
--- /dev/null
+++ b/src/map/if/ifSeq.c
@@ -0,0 +1,405 @@
+/**CFile****************************************************************
+
+ FileName [ifSeq.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Sequential mapping.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifSeq.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+extern int s_MappingTime;
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Prepares for sequential mapping by linking the latches.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManPrepareMappingSeq( If_Man_t * p )
+{
+ If_Obj_t * pObjLi, * pObjLo;
+ int i;
+
+ // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
+ for ( i = 0; i < p->pPars->nLatches; i++ )
+ {
+ pObjLi = If_ManLi( p, i );
+ pObjLo = If_ManLo( p, i );
+ pObjLo->pFanin0 = If_ObjFanin0( pObjLi );
+ pObjLo->fCompl0 = If_ObjFaninC0( pObjLi );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects latches in the topological order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches )
+{
+ if ( !If_ObjIsLatch(pObj) )
+ return;
+ if ( pObj->fMark )
+ return;
+ pObj->fMark = 1;
+ If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
+ Vec_PtrPush( vLatches, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects latches in the topological order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
+{
+ Vec_Ptr_t * vLatches;
+ If_Obj_t * pObj;
+ int i;
+ // collect latches
+ vLatches = Vec_PtrAlloc( p->pPars->nLatches );
+ If_ManForEachLatchOutput( p, pObj, i )
+ If_ManCollectLatches_rec( pObj, vLatches );
+ // clean marks
+ Vec_PtrForEachEntry( vLatches, pObj, i )
+ pObj->fMark = 0;
+ assert( Vec_PtrSize(vLatches) == p->pPars->nLatches );
+ return vLatches;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs one pass of l-value computation over all nodes.]
+
+ Description [Experimentally it was found that checking POs changes
+ is not enough to detect the convergence of l-values in the network.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingRoundSeq( If_Man_t * p, int nIter )
+{
+ If_Obj_t * pObj;
+ int i, clk = clock();
+ int fVeryVerbose = 0;
+ int fChange = 0;
+
+ // map the internal nodes
+ p->nCutsMerged = 0;
+ If_ManForEachNode( p, pObj, i )
+ {
+ If_ObjPerformMappingAnd( p, pObj, 0, 0 );
+ if ( pObj->fRepr )
+ If_ObjPerformMappingChoice( p, pObj, 0, 0 );
+ }
+
+ // postprocess the mapping
+//printf( "Itereation %d: \n", nIter );
+ If_ManForEachNode( p, pObj, i )
+ {
+ // update the LValues stored separately
+ if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon )
+ {
+ If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay );
+ fChange = 1;
+ }
+//printf( "%d ", (int)If_ObjLValue(pObj) );
+ // reset the visit counters
+ assert( pObj->nVisits == 0 );
+ pObj->nVisits = pObj->nVisitsCopy;
+ }
+//printf( "\n" );
+
+ // propagate LValues over the registers
+ Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
+ {
+ If_ObjSetLValue( pObj, If_ObjLValue(If_ObjFanin0(pObj)) - p->Period );
+ If_ObjSetArrTime( pObj, If_ObjLValue(pObj) );
+ }
+
+ // compute area and delay
+ if ( fVeryVerbose )
+ {
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+ p->AreaGlo = If_ManScanMapping(p);
+ printf( "S%d: Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. ",
+ nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged );
+ PRT( "T", clock() - clk );
+ }
+ return fChange;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if retiming with this clock period is feasible.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManBinarySearchPeriod( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i, c, fConverged;
+ int fResetRefs = 0;
+
+ p->nAttempts++;
+
+ // reset initial LValues (PIs to 0; others to -inf)
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
+ {
+ If_ObjSetLValue( pObj, (float)0.0 );
+ If_ObjSetArrTime( pObj, (float)0.0 );
+ }
+ else
+ {
+ If_ObjSetLValue( pObj, (float)-IF_INFINITY );
+ If_ObjSetArrTime( pObj, (float)-IF_INFINITY );
+ }
+ // undo any previous mapping, except for CIs
+ if ( If_ObjIsAnd(pObj) )
+ If_ObjCutBest(pObj)->nLeaves = 0;
+ }
+
+ // update all values iteratively
+ fConverged = 0;
+ for ( c = 1; c <= p->nMaxIters; c++ )
+ {
+ if ( !If_ManPerformMappingRoundSeq( p, c ) )
+ {
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+ fConverged = 1;
+ break;
+ }
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+//printf( "Global = %d \n", (int)p->RequiredGlo );
+ if ( p->RequiredGlo > p->Period + p->fEpsilon )
+ break;
+ }
+
+ // report the results
+ if ( p->pPars->fVerbose )
+ {
+ p->AreaGlo = If_ManScanMapping(p);
+ printf( "Attempt = %2d. Iters = %3d. Area = %10.2f. Fi = %6.2f. ", p->nAttempts, c, p->AreaGlo, (float)p->Period );
+ if ( fConverged )
+ printf( " Feasible" );
+ else if ( c > p->nMaxIters )
+ printf( "Infeasible (timeout)" );
+ else
+ printf( "Infeasible" );
+ printf( "\n" );
+ }
+ return fConverged;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs binary search for the optimal clock period.]
+
+ Description [Assumes that FiMin is infeasible while FiMax is feasible.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManBinarySearch_rec( If_Man_t * p, int FiMin, int FiMax )
+{
+ assert( FiMin < FiMax );
+ if ( FiMin + 1 == FiMax )
+ return FiMax;
+ // compute the median
+ p->Period = FiMin + (FiMax - FiMin)/2;
+ if ( If_ManBinarySearchPeriod( p ) )
+ return If_ManBinarySearch_rec( p, FiMin, p->Period ); // Median is feasible
+ else
+ return If_ManBinarySearch_rec( p, p->Period, FiMax ); // Median is infeasible
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManPerformMappingSeqPost( If_Man_t * p )
+{
+ If_Obj_t * pObjLi, * pObjLo, * pObj;
+ int i;
+
+ // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
+ for ( i = 0; i < p->pPars->nLatches; i++ )
+ {
+ pObjLi = If_ManLi( p, i );
+ pObjLo = If_ManLo( p, i );
+// printf( "%3d : %2d -> %2d \n", i,
+// (int)If_ObjLValue(If_ObjFanin0(pObjLo)), (int)If_ObjLValue(pObjLo) );
+ }
+
+ // set arrival times
+ assert( p->pPars->pTimesArr != NULL );
+ If_ManForEachLatchOutput( p, pObjLo, i )
+ p->pPars->pTimesArr[i] = If_ObjLValue(pObjLo);
+
+ // set the required times
+ assert( p->pPars->pTimesReq == NULL );
+ p->pPars->pTimesReq = ALLOC( float, If_ManCoNum(p) );
+ If_ManForEachPo( p, pObj, i )
+ {
+ p->pPars->pTimesReq[i] = p->RequiredGlo2;
+// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] );
+ }
+ If_ManForEachLatchInput( p, pObjLi, i )
+ {
+ p->pPars->pTimesReq[i] = If_ObjLValue(If_ObjFanin0(pObjLi));
+// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] );
+ }
+
+ // undo previous mapping
+ If_ManForEachObj( p, pObj, i )
+ if ( If_ObjIsAnd(pObj) )
+ If_ObjCutBest(pObj)->nLeaves = 0;
+
+ // map again combinationally
+ p->pPars->fSeqMap = 0;
+ If_ManPerformMappingComb( p );
+ p->pPars->fSeqMap = 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingSeq( If_Man_t * p )
+{
+ int clkTotal = clock();
+ int PeriodBest;
+
+ p->SortMode = 0;
+
+ // perform combinational mapping to get the upper bound on the clock period
+ If_ManPerformMappingRound( p, 1, 0, 0, NULL );
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+ p->RequiredGlo2 = p->RequiredGlo;
+
+ // set direct linking of latches with their inputs
+ If_ManPrepareMappingSeq( p );
+
+ // collect latches
+ p->vLatchOrder = If_ManCollectLatches( p );
+
+ // set parameters
+ p->nCutsUsed = p->pPars->nCutsMax;
+ p->nAttempts = 0;
+ p->nMaxIters = 50;
+ p->Period = (int)p->RequiredGlo;
+
+ // make sure the clock period works
+ if ( !If_ManBinarySearchPeriod( p ) )
+ {
+ printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
+ return 0;
+ }
+
+ // perform binary search
+ PeriodBest = If_ManBinarySearch_rec( p, 0, p->Period );
+
+ // recompute the best l-values
+ if ( p->Period != PeriodBest )
+ {
+ p->Period = PeriodBest;
+ if ( !If_ManBinarySearchPeriod( p ) )
+ {
+ printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" );
+ return 0;
+ }
+ }
+ if ( p->pPars->fVerbose )
+ {
+/*
+ {
+ FILE * pTable;
+ pTable = fopen( "iscas/stats_new.txt", "a+" );
+// fprintf( pTable, "%s ", pNtk->pName );
+ fprintf( pTable, "%d ", p->Period );
+ // fprintf( pTable, "%.2f ", (float)(s_MappingMem)/(float)(1<<20) );
+// fprintf( pTable, "%.2f", (float)(s_MappingTime)/(float)(CLOCKS_PER_SEC) );
+// fprintf( pTable, "\n" );
+ fclose( pTable );
+ }
+*/
+ printf( "The best clock period is %3d. ", p->Period );
+ PRT( "Sequential time", clock() - clkTotal );
+ }
+ p->RequiredGlo = (float)PeriodBest;
+
+ // postprocess it using combinational mapping
+ If_ManPerformMappingSeqPost( p );
+ s_MappingTime = clock() - clkTotal;
+ return 1;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifTime.c b/src/map/if/ifTime.c
new file mode 100644
index 00000000..3d1dab1b
--- /dev/null
+++ b/src/map/if/ifTime.c
@@ -0,0 +1,228 @@
+/**CFile****************************************************************
+
+ FileName [ifTime.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Computation of delay paramters depending on the library.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifTime.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static void If_CutSortInputPins( If_Man_t * p, If_Cut_t * pCut, int * pPinPerm, float * pPinDelays );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Computes delay.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_CutDelay( If_Man_t * p, If_Cut_t * pCut )
+{
+ static int pPinPerm[IF_MAX_LUTSIZE];
+ static float pPinDelays[IF_MAX_LUTSIZE];
+ If_Obj_t * pLeaf;
+ float Delay, DelayCur;
+ float * pLutDelays;
+ int i, Shift;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ Delay = -IF_FLOAT_LARGE;
+ if ( p->pPars->pLutLib )
+ {
+ assert( !p->pPars->fLiftLeaves );
+ pLutDelays = p->pPars->pLutLib->pLutDelays[pCut->nLeaves];
+ if ( p->pPars->pLutLib->fVarPinDelays )
+ {
+ // compute the delay using sorted pins
+ If_CutSortInputPins( p, pCut, pPinPerm, pPinDelays );
+ for ( i = 0; i < (int)pCut->nLeaves; i++ )
+ {
+ DelayCur = pPinDelays[pPinPerm[i]] + pLutDelays[i];
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ else
+ {
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ DelayCur = If_ObjCutBest(pLeaf)->Delay + pLutDelays[0];
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ }
+ else
+ {
+ if ( pCut->fUser )
+ {
+ assert( !p->pPars->fLiftLeaves );
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ DelayCur = If_ObjCutBest(pLeaf)->Delay + (float)pCut->pPerm[i];
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ else
+ {
+ if ( p->pPars->fLiftLeaves )
+ {
+ If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i )
+ {
+ DelayCur = If_ObjCutBest(pLeaf)->Delay - Shift * p->Period;
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ else
+ {
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+/*
+ if ( pLeaf->IdPio > 2000 )
+ {
+ int x = 0;
+ printf( "-%d %6.3f ", pLeaf->IdPio, If_ObjCutBest(pLeaf)->Delay );
+ }
+*/
+ DelayCur = If_ObjCutBest(pLeaf)->Delay;
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ Delay += 1.0;
+ }
+ }
+ return Delay;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float ObjRequired )
+{
+ static int pPinPerm[IF_MAX_LUTSIZE];
+ static float pPinDelays[IF_MAX_LUTSIZE];
+ If_Obj_t * pLeaf;
+ float * pLutDelays;
+ float Required;
+ int i;
+ assert( !p->pPars->fLiftLeaves );
+ // compute the pins
+ if ( p->pPars->pLutLib )
+ {
+ pLutDelays = p->pPars->pLutLib->pLutDelays[pCut->nLeaves];
+ if ( p->pPars->pLutLib->fVarPinDelays )
+ {
+ // compute the delay using sorted pins
+ If_CutSortInputPins( p, pCut, pPinPerm, pPinDelays );
+ for ( i = 0; i < (int)pCut->nLeaves; i++ )
+ {
+ Required = ObjRequired - pLutDelays[i];
+ pLeaf = If_ManObj( p, pCut->pLeaves[pPinPerm[i]] );
+ pLeaf->Required = IF_MIN( pLeaf->Required, Required );
+ }
+ }
+ else
+ {
+ Required = ObjRequired - pLutDelays[0];
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ pLeaf->Required = IF_MIN( pLeaf->Required, Required );
+ }
+ }
+ else
+ {
+ if ( pCut->fUser )
+ {
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ Required = ObjRequired - (float)pCut->pPerm[i];
+ pLeaf->Required = IF_MIN( pLeaf->Required, Required );
+ }
+ }
+ else
+ {
+ Required = ObjRequired - (float)1.0;
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ pLeaf->Required = IF_MIN( pLeaf->Required, Required );
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sorts the pins in the decreasing order of delays.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutSortInputPins( If_Man_t * p, If_Cut_t * pCut, int * pPinPerm, float * pPinDelays )
+{
+ If_Obj_t * pLeaf;
+ int i, j, best_i, temp;
+ // start the trivial permutation and collect pin delays
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ pPinPerm[i] = i;
+ pPinDelays[i] = If_ObjCutBest(pLeaf)->Delay;
+ }
+ // selection sort the pins in the decreasible order of delays
+ // this order will match the increasing order of LUT input pins
+ for ( i = 0; i < (int)pCut->nLeaves-1; i++ )
+ {
+ best_i = i;
+ for ( j = i+1; j < (int)pCut->nLeaves; j++ )
+ if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] )
+ best_i = j;
+ if ( best_i == i )
+ continue;
+ temp = pPinPerm[i];
+ pPinPerm[i] = pPinPerm[best_i];
+ pPinPerm[best_i] = temp;
+ }
+ // verify
+ assert( pPinPerm[0] < (int)pCut->nLeaves );
+ for ( i = 1; i < (int)pCut->nLeaves; i++ )
+ {
+ assert( pPinPerm[i] < (int)pCut->nLeaves );
+ assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] );
+ }
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c
new file mode 100644
index 00000000..f18d8308
--- /dev/null
+++ b/src/map/if/ifTruth.c
@@ -0,0 +1,404 @@
+/**CFile****************************************************************
+
+ FileName [ifTruth.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Computation of truth tables of the cuts.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifTruth.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Several simple procedures working with truth tables.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_TruthWordNum( int nVars ) { return nVars <= 5 ? 1 : (1 << (nVars - 5)); }
+static inline void If_TruthNot( unsigned * pOut, unsigned * pIn, int nVars )
+{
+ int w;
+ for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = ~pIn[w];
+}
+static inline void If_TruthCopy( unsigned * pOut, unsigned * pIn, int nVars )
+{
+ int w;
+ for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = pIn[w];
+}
+static inline void If_TruthNand( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars )
+{
+ int w;
+ for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = ~(pIn0[w] & pIn1[w]);
+}
+static inline void If_TruthAnd( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars )
+{
+ int w;
+ for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- )
+ pOut[w] = pIn0[w] & pIn1[w];
+}
+
+/**Function*************************************************************
+
+ Synopsis [Swaps two adjacent variables in the truth table.]
+
+ Description [Swaps var number Start and var number Start+1 (0-based numbers).
+ The input truth table is pIn. The output truth table is pOut.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_TruthSwapAdjacentVars( unsigned * pOut, unsigned * pIn, int nVars, int iVar )
+{
+ static unsigned PMasks[4][3] = {
+ { 0x99999999, 0x22222222, 0x44444444 },
+ { 0xC3C3C3C3, 0x0C0C0C0C, 0x30303030 },
+ { 0xF00FF00F, 0x00F000F0, 0x0F000F00 },
+ { 0xFF0000FF, 0x0000FF00, 0x00FF0000 }
+ };
+ int nWords = If_TruthWordNum( nVars );
+ int i, k, Step, Shift;
+
+ assert( iVar < nVars - 1 );
+ if ( iVar < 4 )
+ {
+ Shift = (1 << iVar);
+ for ( i = 0; i < nWords; i++ )
+ pOut[i] = (pIn[i] & PMasks[iVar][0]) | ((pIn[i] & PMasks[iVar][1]) << Shift) | ((pIn[i] & PMasks[iVar][2]) >> Shift);
+ }
+ else if ( iVar > 4 )
+ {
+ Step = (1 << (iVar - 5));
+ for ( k = 0; k < nWords; k += 4*Step )
+ {
+ for ( i = 0; i < Step; i++ )
+ pOut[i] = pIn[i];
+ for ( i = 0; i < Step; i++ )
+ pOut[Step+i] = pIn[2*Step+i];
+ for ( i = 0; i < Step; i++ )
+ pOut[2*Step+i] = pIn[Step+i];
+ for ( i = 0; i < Step; i++ )
+ pOut[3*Step+i] = pIn[3*Step+i];
+ pIn += 4*Step;
+ pOut += 4*Step;
+ }
+ }
+ else // if ( iVar == 4 )
+ {
+ for ( i = 0; i < nWords; i += 2 )
+ {
+ pOut[i] = (pIn[i] & 0x0000FFFF) | ((pIn[i+1] & 0x0000FFFF) << 16);
+ pOut[i+1] = (pIn[i+1] & 0xFFFF0000) | ((pIn[i] & 0xFFFF0000) >> 16);
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Expands the truth table according to the phase.]
+
+ Description [The input and output truth tables are in pIn/pOut. The current number
+ of variables is nVars. The total number of variables in nVarsAll. The last argument
+ (Phase) contains shows where the variables should go.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_TruthStretch( unsigned * pOut, unsigned * pIn, int nVars, int nVarsAll, unsigned Phase )
+{
+ unsigned * pTemp;
+ int i, k, Var = nVars - 1, Counter = 0;
+ for ( i = nVarsAll - 1; i >= 0; i-- )
+ if ( Phase & (1 << i) )
+ {
+ for ( k = Var; k < i; k++ )
+ {
+ If_TruthSwapAdjacentVars( pOut, pIn, nVarsAll, k );
+ pTemp = pIn; pIn = pOut; pOut = pTemp;
+ Counter++;
+ }
+ Var--;
+ }
+ assert( Var == -1 );
+ // swap if it was moved an even number of times
+ if ( !(Counter & 1) )
+ If_TruthCopy( pOut, pIn, nVarsAll );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Shrinks the truth table according to the phase.]
+
+ Description [The input and output truth tables are in pIn/pOut. The current number
+ of variables is nVars. The total number of variables in nVarsAll. The last argument
+ (Phase) contains shows what variables should remain.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_TruthShrink( unsigned * pOut, unsigned * pIn, int nVars, int nVarsAll, unsigned Phase, int fReturnIn )
+{
+ unsigned * pTemp;
+ int i, k, Var = 0, Counter = 0;
+ for ( i = 0; i < nVarsAll; i++ )
+ if ( Phase & (1 << i) )
+ {
+ for ( k = i-1; k >= Var; k-- )
+ {
+ If_TruthSwapAdjacentVars( pOut, pIn, nVarsAll, k );
+ pTemp = pIn; pIn = pOut; pOut = pTemp;
+ Counter++;
+ }
+ Var++;
+ }
+ assert( Var == nVars );
+ // swap if it was moved an even number of times
+ if ( fReturnIn ^ !(Counter & 1) )
+ If_TruthCopy( pOut, pIn, nVarsAll );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if TT depends on the given variable.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutTruthVarInSupport( unsigned * pTruth, int nVars, int iVar )
+{
+ int nWords = If_TruthWordNum( nVars );
+ int i, k, Step;
+
+ assert( iVar < nVars );
+ switch ( iVar )
+ {
+ case 0:
+ for ( i = 0; i < nWords; i++ )
+ if ( (pTruth[i] & 0x55555555) != ((pTruth[i] & 0xAAAAAAAA) >> 1) )
+ return 1;
+ return 0;
+ case 1:
+ for ( i = 0; i < nWords; i++ )
+ if ( (pTruth[i] & 0x33333333) != ((pTruth[i] & 0xCCCCCCCC) >> 2) )
+ return 1;
+ return 0;
+ case 2:
+ for ( i = 0; i < nWords; i++ )
+ if ( (pTruth[i] & 0x0F0F0F0F) != ((pTruth[i] & 0xF0F0F0F0) >> 4) )
+ return 1;
+ return 0;
+ case 3:
+ for ( i = 0; i < nWords; i++ )
+ if ( (pTruth[i] & 0x00FF00FF) != ((pTruth[i] & 0xFF00FF00) >> 8) )
+ return 1;
+ return 0;
+ case 4:
+ for ( i = 0; i < nWords; i++ )
+ if ( (pTruth[i] & 0x0000FFFF) != ((pTruth[i] & 0xFFFF0000) >> 16) )
+ return 1;
+ return 0;
+ default:
+ Step = (1 << (iVar - 5));
+ for ( k = 0; k < nWords; k += 2*Step )
+ {
+ for ( i = 0; i < Step; i++ )
+ if ( pTruth[i] != pTruth[Step+i] )
+ return 1;
+ pTruth += 2*Step;
+ }
+ return 0;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns support of the function.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+unsigned If_CutTruthSupport( unsigned * pTruth, int nVars, int * pnSuppSize )
+{
+ int i, Support = 0;
+ int nSuppSize = 0;
+ for ( i = 0; i < nVars; i++ )
+ if ( If_CutTruthVarInSupport( pTruth, nVars, i ) )
+ {
+ Support |= (1 << i);
+ nSuppSize++;
+ }
+ *pnSuppSize = nSuppSize;
+ return Support;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Computes the stretching phase of the cut w.r.t. the merged cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline unsigned If_CutTruthPhase( If_Cut_t * pCut, If_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 [Performs truth table computation.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 )
+{
+ extern void If_CutFactorTest( unsigned * pTruth, int nVars );
+
+ // permute the first table
+ if ( fCompl0 ^ pCut0->fCompl )
+ If_TruthNot( p->puTemp[0], If_CutTruth(pCut0), pCut->nLimit );
+ else
+ If_TruthCopy( p->puTemp[0], If_CutTruth(pCut0), pCut->nLimit );
+ If_TruthStretch( p->puTemp[2], p->puTemp[0], pCut0->nLeaves, pCut->nLimit, If_CutTruthPhase(pCut, pCut0) );
+ // permute the second table
+ if ( fCompl1 ^ pCut1->fCompl )
+ If_TruthNot( p->puTemp[1], If_CutTruth(pCut1), pCut->nLimit );
+ else
+ If_TruthCopy( p->puTemp[1], If_CutTruth(pCut1), pCut->nLimit );
+ If_TruthStretch( p->puTemp[3], p->puTemp[1], pCut1->nLeaves, pCut->nLimit, If_CutTruthPhase(pCut, pCut1) );
+ // produce the resulting table
+ assert( pCut->fCompl == 0 );
+ if ( pCut->fCompl )
+ If_TruthNand( If_CutTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nLimit );
+ else
+ If_TruthAnd( If_CutTruth(pCut), p->puTemp[2], p->puTemp[3], pCut->nLimit );
+
+ // minimize the support of the cut
+ if ( p->pPars->fCutMin )
+ If_CutTruthMinimize( p, pCut );
+
+ // perform
+// If_CutFactorTest( If_CutTruth(pCut), pCut->nLimit );
+// printf( "%d ", If_CutLeaveNum(pCut) - If_CutTruthSupportSize(If_CutTruth(pCut), If_CutLeaveNum(pCut)) );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Minimize support of the cut.]
+
+ Description [Returns 1 if the node's support has changed]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut )
+{
+ unsigned uSupport;
+ int nSuppSize, i, k;
+ // compute the support of the cut's function
+ uSupport = If_CutTruthSupport( If_CutTruth(pCut), If_CutLeaveNum(pCut), &nSuppSize );
+ if ( nSuppSize == If_CutLeaveNum(pCut) )
+ return 0;
+
+// TEMPORARY
+ if ( nSuppSize < 2 )
+ {
+ p->nSmallSupp++;
+ return 0;
+ }
+// if ( If_CutLeaveNum(pCut) - nSuppSize > 1 )
+// return 0;
+//printf( "%d %d ", If_CutLeaveNum(pCut), nSuppSize );
+
+ // shrink the truth table
+ If_TruthShrink( p->puTemp[0], If_CutTruth(pCut), nSuppSize, pCut->nLimit, uSupport, 1 );
+ // update leaves and signature
+ pCut->uSign = 0;
+ for ( i = k = 0; i < If_CutLeaveNum(pCut); i++ )
+ {
+ if ( !(uSupport & (1 << i)) )
+ continue;
+ pCut->pLeaves[k++] = pCut->pLeaves[i];
+ pCut->uSign |= If_ObjCutSign( pCut->pLeaves[i] );
+ }
+ assert( k == nSuppSize );
+ pCut->nLeaves = nSuppSize;
+ // verify the result
+// uSupport = If_CutTruthSupport( If_CutTruth(pCut), If_CutLeaveNum(pCut), &nSuppSize );
+// assert( nSuppSize == If_CutLeaveNum(pCut) );
+ return 1;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c
new file mode 100644
index 00000000..2624efd0
--- /dev/null
+++ b/src/map/if/ifUtil.c
@@ -0,0 +1,658 @@
+/**CFile****************************************************************
+
+ FileName [ifUtil.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Various utilities.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifUtil.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Sets all the node copy to NULL.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanNodeCopy( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ If_ObjSetCopy( pObj, NULL );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sets all the cut data to NULL.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanCutData( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ If_CutSetData( If_ObjCutBest(pObj), NULL );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sets all visited marks to 0.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanMarkV( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ pObj->fVisit = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the max delay of the POs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManDelayMax( If_Man_t * p, int fSeq )
+{
+ If_Obj_t * pObj;
+ float DelayBest;
+ int i;
+ if ( p->pPars->fLatchPaths && p->pPars->nLatches == 0 )
+ {
+ printf( "Delay optimization of latch path is not performed because there is no latches.\n" );
+ p->pPars->fLatchPaths = 0;
+ }
+ DelayBest = -IF_FLOAT_LARGE;
+ if ( fSeq )
+ {
+ assert( p->pPars->nLatches > 0 );
+ If_ManForEachPo( p, pObj, i )
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
+ }
+ else if ( p->pPars->fLatchPaths )
+ {
+ If_ManForEachLatchInput( p, pObj, i )
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
+ }
+ else
+ {
+ If_ManForEachCo( p, pObj, i )
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
+ }
+ return DelayBest;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the required times of all nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManComputeRequired( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i, Counter;
+ float reqTime;
+
+ // compute area, clean required times, collect nodes used in the mapping
+// p->AreaGlo = If_ManScanMapping( p );
+ If_ManMarkMapping( p );
+
+ if ( p->pManTim == NULL )
+ {
+ // consider the case when the required times are given
+ if ( p->pPars->pTimesReq )
+ {
+ assert( !p->pPars->fAreaOnly );
+ // make sure that the required time hold
+ Counter = 0;
+ If_ManForEachCo( p, pObj, i )
+ {
+ if ( If_ObjArrTime(If_ObjFanin0(pObj)) > p->pPars->pTimesReq[i] + p->fEpsilon )
+ {
+ Counter++;
+ // printf( "Required times are violated for output %d (arr = %d; req = %d).\n",
+ // i, (int)If_ObjArrTime(If_ObjFanin0(pObj)), (int)p->pPars->pTimesReq[i] );
+ }
+ If_ObjFanin0(pObj)->Required = p->pPars->pTimesReq[i];
+ }
+ if ( Counter )
+ printf( "Required times are violated for %d outputs.\n", Counter );
+ }
+ else
+ {
+ // get the global required times
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+ // update the required times according to the target
+ if ( p->pPars->DelayTarget != -1 )
+ {
+ if ( p->RequiredGlo > p->pPars->DelayTarget + p->fEpsilon )
+ {
+ if ( p->fNextRound == 0 )
+ {
+ p->fNextRound = 1;
+ printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->pPars->DelayTarget );
+ }
+ }
+ else if ( p->RequiredGlo < p->pPars->DelayTarget - p->fEpsilon )
+ {
+ if ( p->fNextRound == 0 )
+ {
+ p->fNextRound = 1;
+ printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget );
+ }
+ p->RequiredGlo = p->pPars->DelayTarget;
+ }
+ }
+ // do not propagate required times if area minimization is requested
+ if ( p->pPars->fAreaOnly )
+ return;
+ // set the required times for the POs
+ if ( p->pPars->fLatchPaths )
+ {
+ If_ManForEachLatchInput( p, pObj, i )
+ If_ObjFanin0(pObj)->Required = p->RequiredGlo;
+ }
+ else
+ {
+ If_ManForEachCo( p, pObj, i )
+ If_ObjFanin0(pObj)->Required = p->RequiredGlo;
+ }
+ }
+ // go through the nodes in the reverse topological order
+ // Vec_PtrForEachEntry( p->vMapped, pObj, i )
+ // If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required );
+ If_ManForEachObjReverse( p, pObj, i )
+ {
+ if ( pObj->nRefs == 0 )
+ continue;
+ If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required );
+ }
+ }
+ else
+ {
+ // get the global required times
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+ // do not propagate required times if area minimization is requested
+ if ( p->pPars->fAreaOnly )
+ return;
+ // set the required times for the POs
+ Tim_ManIncrementTravId( p->pManTim );
+ if ( p->pPars->fLatchPaths )
+ {
+ assert( 0 );
+ If_ManForEachPo( p, pObj, i )
+ Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, IF_FLOAT_LARGE );
+ If_ManForEachLatchInput( p, pObj, i )
+ Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo );
+ }
+ else
+ {
+ Tim_ManSetPoRequiredAll( p->pManTim, p->RequiredGlo );
+// If_ManForEachCo( p, pObj, i )
+// Tim_ManSetPoRequired( p->pManTim, pObj->IdPio, p->RequiredGlo );
+ }
+ // go through the nodes in the reverse topological order
+ If_ManForEachObjReverse( p, pObj, i )
+ {
+ if ( If_ObjIsAnd(pObj) )
+ {
+ if ( pObj->nRefs == 0 )
+ continue;
+ If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required );
+ }
+ else if ( If_ObjIsCi(pObj) )
+ {
+ reqTime = pObj->Required;
+ Tim_ManSetPiRequired( p->pManTim, pObj->IdPio, reqTime );
+ }
+ else if ( If_ObjIsCo(pObj) )
+ {
+ reqTime = Tim_ManGetPoRequired( p->pManTim, pObj->IdPio );
+ If_ObjFanin0(pObj)->Required = IF_MIN( reqTime, If_ObjFanin0(pObj)->Required );
+ }
+ else if ( If_ObjIsConst1(pObj) )
+ {
+ }
+ else // add the node to the mapper
+ assert( 0 );
+ }
+ }
+}
+
+#if 0
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMapping_rec( If_Man_t * p, If_Obj_t * pObj, If_Obj_t ** ppStore )
+{
+ If_Obj_t * pLeaf;
+ If_Cut_t * pCutBest;
+ float aArea;
+ int i;
+ if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
+ return 0.0;
+ // store the node in the structure by level
+ assert( If_ObjIsAnd(pObj) );
+ pObj->pCopy = (char *)ppStore[pObj->Level];
+ ppStore[pObj->Level] = pObj;
+ // visit the transitive fanin of the selected cut
+ pCutBest = If_ObjCutBest(pObj);
+ p->nNets += pCutBest->nLeaves;
+ aArea = If_CutLutArea( p, pCutBest );
+ If_CutForEachLeaf( p, pCutBest, pLeaf, i )
+ aArea += If_ManScanMapping_rec( p, pLeaf, ppStore );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description [Collects the nodes in reverse topological order in array
+ p->vMapping.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMapping( If_Man_t * p )
+{
+ If_Obj_t * pObj, ** ppStore;
+ float aArea;
+ int i;
+ assert( !p->pPars->fLiftLeaves );
+ // clean all references
+ p->nNets = 0;
+ If_ManForEachObj( p, pObj, i )
+ {
+ pObj->Required = IF_FLOAT_LARGE;
+ pObj->nVisits = pObj->nVisitsCopy;
+ pObj->nRefs = 0;
+ }
+ // allocate place to store the nodes
+ ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 );
+ memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
+ // collect nodes reachable from POs in the DFS order through the best cuts
+ aArea = 0;
+ If_ManForEachCo( p, pObj, i )
+ aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore );
+ // reconnect the nodes in reverse topological order
+ Vec_PtrClear( p->vMapped );
+ for ( i = p->nLevelMax; i >= 0; i-- )
+ for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy )
+ Vec_PtrPush( p->vMapped, pObj );
+ free( ppStore );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description [Collects the nodes in reverse topological order in array
+ p->vMapping.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMappingDirect( If_Man_t * p )
+{
+ If_Obj_t * pObj, ** ppStore;
+ float aArea;
+ int i;
+ assert( !p->pPars->fLiftLeaves );
+ // clean all references
+ If_ManForEachObj( p, pObj, i )
+ {
+ pObj->Required = IF_FLOAT_LARGE;
+ pObj->nVisits = pObj->nVisitsCopy;
+ pObj->nRefs = 0;
+ }
+ // allocate place to store the nodes
+ ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 );
+ memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
+ // collect nodes reachable from POs in the DFS order through the best cuts
+ aArea = 0;
+ If_ManForEachCo( p, pObj, i )
+ aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore );
+ // reconnect the nodes in reverse topological order
+ Vec_PtrClear( p->vMapped );
+// for ( i = p->nLevelMax; i >= 0; i-- )
+ for ( i = 0; i <= p->nLevelMax; i++ )
+ for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy )
+ Vec_PtrPush( p->vMapped, pObj );
+ free( ppStore );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMappingSeq_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vMapped )
+{
+ If_Obj_t * pLeaf;
+ If_Cut_t * pCutBest;
+ float aArea;
+ int i, Shift;
+ // treat latches transparently
+ if ( If_ObjIsLatch(pObj) )
+ return If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), vMapped );
+ // consider trivial cases
+ if ( pObj->nRefs++ || If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
+ return 0.0;
+ // store the node in the structure by level
+ assert( If_ObjIsAnd(pObj) );
+ // visit the transitive fanin of the selected cut
+ pCutBest = If_ObjCutBest(pObj);
+ aArea = If_ObjIsAnd(pObj)? If_CutLutArea(p, pCutBest) : (float)0.0;
+ If_CutForEachLeafSeq( p, pCutBest, pLeaf, Shift, i )
+ aArea += If_ManScanMappingSeq_rec( p, pLeaf, vMapped );
+ // add the node
+ Vec_PtrPush( vMapped, pObj );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description [Collects the nodes in reverse topological order in array
+ p->vMapping.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMappingSeq( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ float aArea;
+ int i;
+ assert( p->pPars->fLiftLeaves );
+ // clean all references
+ If_ManForEachObj( p, pObj, i )
+ pObj->nRefs = 0;
+ // collect nodes reachable from POs in the DFS order through the best cuts
+ aArea = 0;
+ Vec_PtrClear( p->vMapped );
+ If_ManForEachPo( p, pObj, i )
+ aArea += If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), p->vMapped );
+ return aArea;
+}
+
+#endif
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description [Collects the nodes in reverse topological order in array
+ p->vMapping.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManResetOriginalRefs( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ pObj->nRefs = 0;
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsAnd(pObj) )
+ {
+ pObj->pFanin0->nRefs++;
+ pObj->pFanin1->nRefs++;
+ }
+ else if ( If_ObjIsCo(pObj) )
+ pObj->pFanin0->nRefs++;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes cross-cut of the circuit.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManCrossCut( If_Man_t * p )
+{
+ If_Obj_t * pObj, * pFanin;
+ int i, nCutSize = 0, nCutSizeMax = 0;
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( !If_ObjIsAnd(pObj) )
+ continue;
+ // consider the node
+ if ( nCutSizeMax < ++nCutSize )
+ nCutSizeMax = nCutSize;
+ if ( pObj->nVisits == 0 )
+ nCutSize--;
+ // consider the fanins
+ pFanin = If_ObjFanin0(pObj);
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ pFanin = If_ObjFanin1(pObj);
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ // consider the choice class
+ if ( pObj->fRepr )
+ for ( pFanin = pObj; pFanin; pFanin = pFanin->pEquiv )
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ }
+ If_ManForEachObj( p, pObj, i )
+ {
+ assert( If_ObjIsCi(pObj) || pObj->fVisit == 0 );
+ pObj->nVisits = pObj->nVisitsCopy;
+ }
+ assert( nCutSize == 0 );
+// printf( "Max cross cut size = %6d.\n", nCutSizeMax );
+ return nCutSizeMax;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes the reverse topological order of nodes.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p )
+{
+ Vec_Ptr_t * vOrder;
+ If_Obj_t * pObj, ** ppStore;
+ int i;
+ // allocate place to store the nodes
+ ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 );
+ memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
+ // add the nodes
+ If_ManForEachObj( p, pObj, i )
+ {
+ assert( pObj->Level >= 0 && pObj->Level <= (unsigned)p->nLevelMax );
+ pObj->pCopy = (char *)ppStore[pObj->Level];
+ ppStore[pObj->Level] = pObj;
+ }
+ vOrder = Vec_PtrAlloc( If_ManObjNum(p) );
+ for ( i = p->nLevelMax; i >= 0; i-- )
+ for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy )
+ Vec_PtrPush( vOrder, pObj );
+ free( ppStore );
+ // print the order
+// Vec_PtrForEachEntry( vOrder, pObj, i )
+// printf( "Obj %2d Type %d Level = %d\n", pObj->Id, pObj->Type, pObj->Level );
+ return vOrder;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManMarkMapping_rec( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pLeaf;
+ If_Cut_t * pCutBest;
+ float aArea;
+ int i;
+ if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
+ return 0.0;
+ // store the node in the structure by level
+ assert( If_ObjIsAnd(pObj) );
+ // visit the transitive fanin of the selected cut
+ pCutBest = If_ObjCutBest(pObj);
+ p->nNets += pCutBest->nLeaves;
+ aArea = If_CutLutArea( p, pCutBest );
+ If_CutForEachLeaf( p, pCutBest, pLeaf, i )
+ aArea += If_ManMarkMapping_rec( p, pLeaf );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManMarkMapping( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ {
+ pObj->Required = IF_FLOAT_LARGE;
+ pObj->nVisits = pObj->nVisitsCopy;
+ pObj->nRefs = 0;
+ }
+ p->nNets = 0;
+ p->AreaGlo = 0.0;
+ If_ManForEachCo( p, pObj, i )
+ p->AreaGlo += If_ManMarkMapping_rec( p, If_ObjFanin0(pObj) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects nodes used in the mapping in the topological order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p )
+{
+ Vec_Ptr_t * vOrder;
+ If_Obj_t * pObj;
+ int i;
+ If_ManMarkMapping( p );
+ vOrder = Vec_PtrAlloc( If_ManObjNum(p) );
+ If_ManForEachObj( p, pObj, i )
+ if ( If_ObjIsAnd(pObj) && pObj->nRefs )
+ Vec_PtrPush( vOrder, pObj );
+ return vOrder;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/if_.c b/src/map/if/if_.c
new file mode 100644
index 00000000..d2960077
--- /dev/null
+++ b/src/map/if/if_.c
@@ -0,0 +1,47 @@
+/**CFile****************************************************************
+
+ FileName [if_.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis []
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: if_.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/module.make b/src/map/if/module.make
new file mode 100644
index 00000000..c14428da
--- /dev/null
+++ b/src/map/if/module.make
@@ -0,0 +1,8 @@
+SRC += src/map/if/ifCore.c \
+ src/map/if/ifCut.c \
+ src/map/if/ifMan.c \
+ src/map/if/ifMap.c \
+ src/map/if/ifReduce.c \
+ src/map/if/ifTime.c \
+ src/map/if/ifTruth.c \
+ src/map/if/ifUtil.c
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-09 07:36:42 +0000