diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-07-29 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-07-29 08:01:00 -0700 |
commit | 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc (patch) | |
tree | 11d48c9e9069f54dc300c3571ae63c744c802c50 /src/map/mapper | |
parent | 7f94414388cce67bd3cc1a6d6269f0ed31ed0d06 (diff) | |
download | abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.tar.gz abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.tar.bz2 abc-888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc.zip |
Version abc50729
Diffstat (limited to 'src/map/mapper')
-rw-r--r-- | src/map/mapper/mapper.c | 176 | ||||
-rw-r--r-- | src/map/mapper/mapper.h | 181 | ||||
-rw-r--r-- | src/map/mapper/mapperCanon.c | 161 | ||||
-rw-r--r-- | src/map/mapper/mapperCore.c | 167 | ||||
-rw-r--r-- | src/map/mapper/mapperCreate.c | 592 | ||||
-rw-r--r-- | src/map/mapper/mapperCut.c | 1072 | ||||
-rw-r--r-- | src/map/mapper/mapperCutUtils.c | 273 | ||||
-rw-r--r-- | src/map/mapper/mapperFanout.c | 139 | ||||
-rw-r--r-- | src/map/mapper/mapperGENERIC.c | 46 | ||||
-rw-r--r-- | src/map/mapper/mapperInt.h | 475 | ||||
-rw-r--r-- | src/map/mapper/mapperLib.c | 233 | ||||
-rw-r--r-- | src/map/mapper/mapperMatch.c | 578 | ||||
-rw-r--r-- | src/map/mapper/mapperRefs.c | 541 | ||||
-rw-r--r-- | src/map/mapper/mapperSuper.c | 449 | ||||
-rw-r--r-- | src/map/mapper/mapperTable.c | 402 | ||||
-rw-r--r-- | src/map/mapper/mapperTime.c | 508 | ||||
-rw-r--r-- | src/map/mapper/mapperTree.c | 804 | ||||
-rw-r--r-- | src/map/mapper/mapperTruth.c | 449 | ||||
-rw-r--r-- | src/map/mapper/mapperUtils.c | 1254 | ||||
-rw-r--r-- | src/map/mapper/mapperVec.c | 318 | ||||
-rw-r--r-- | src/map/mapper/module.make | 17 |
21 files changed, 8835 insertions, 0 deletions
diff --git a/src/map/mapper/mapper.c b/src/map/mapper/mapper.c new file mode 100644 index 00000000..546186a2 --- /dev/null +++ b/src/map/mapper/mapper.c @@ -0,0 +1,176 @@ +/**CFile**************************************************************** + + FileName [mapper.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Command file for the mapper package.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapper.c,v 1.7 2005/01/23 06:59:42 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "mainInt.h" +#include "mio.h" +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_CommandReadLibrary ( Abc_Frame_t * pAbc, int argc, char **argv ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_Init( Abc_Frame_t * pAbc ) +{ + Cmd_CommandAdd( pAbc, "SC mapping", "read_super", Map_CommandReadLibrary, 0 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_End() +{ +// Map_SuperLibFree( s_pSuperLib ); + Map_SuperLibFree( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CommandReadLibrary( Abc_Frame_t * pAbc, int argc, char **argv ) +{ + FILE * pFile; + FILE * pOut, * pErr; + Map_SuperLib_t * pLib; + Abc_Ntk_t * pNet; + char * FileName, * ExcludeFile; + int fVerbose; + int fAlgorithm; + int c; + + pNet = Abc_FrameReadNet(pAbc); + pOut = Abc_FrameReadOut(pAbc); + pErr = Abc_FrameReadErr(pAbc); + + // set the defaults + fVerbose = 1; + fAlgorithm = 1; + ExcludeFile = 0; + util_getopt_reset(); + while ( (c = util_getopt(argc, argv, "eovh")) != EOF ) + { + switch (c) + { + case 'e': + ExcludeFile = argv[util_optind]; + if ( ExcludeFile == 0 ) + goto usage; + util_optind++; + break; + case 'o': + fAlgorithm ^= 1; + break; + case 'v': + fVerbose ^= 1; + break; + case 'h': + goto usage; + break; + default: + goto usage; + } + } + + + if ( argc != util_optind + 1 ) + { + goto usage; + } + + // get the input file name + FileName = argv[util_optind]; +// if ( (pFile = Io_FileOpen( FileName, "open_path", "r" )) == NULL ) + if ( (pFile = fopen( FileName, "r" )) == NULL ) + { + fprintf( pErr, "Cannot open input file \"%s\". ", FileName ); + if ( FileName = Extra_FileGetSimilarName( FileName, ".genlib", ".lib", ".gen", ".g", NULL ) ) + fprintf( pErr, "Did you mean \"%s\"?", FileName ); + fprintf( pErr, "\n" ); + return 1; + } + fclose( pFile ); + + // set the new network + pLib = Map_SuperLibCreate( FileName, ExcludeFile, fAlgorithm, fVerbose ); + if ( pLib == NULL ) + { + fprintf( pErr, "Reading supergate library has failed.\n" ); + goto usage; + } + // replace the current library +// Map_SuperLibFree( s_pSuperLib ); +// s_pSuperLib = pLib; + Map_SuperLibFree( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) ); + Abc_FrameSetLibSuper( Abc_FrameGetGlobalFrame(), pLib ); + // replace the current genlib library +// if ( s_pLib ) Mio_LibraryDelete( s_pLib ); +// s_pLib = s_pSuperLib->pGenlib; + Mio_LibraryDelete( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) ); + Abc_FrameSetLibGen( Abc_FrameGetGlobalFrame(), pLib->pGenlib ); + return 0; + +usage: + fprintf( pErr, "\nusage: read_super [-ovh]\n"); + fprintf( pErr, "\t read the supergate library from the file\n" ); + fprintf( pErr, "\t-e file : file contains list of genlib gates to exclude\n" ); + fprintf( pErr, "\t-o : toggles the use of old file format [default = %s]\n", (fAlgorithm? "new" : "old") ); + fprintf( pErr, "\t-v : toggles enabling of verbose output [default = %s]\n", (fVerbose? "yes" : "no") ); + fprintf( pErr, "\t-h : print the command usage\n"); + return 1; /* error exit */ +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapper.h b/src/map/mapper/mapper.h new file mode 100644 index 00000000..a6bfccf8 --- /dev/null +++ b/src/map/mapper/mapper.h @@ -0,0 +1,181 @@ +/**CFile**************************************************************** + + FileName [mapper.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapper.h,v 1.11 2005/02/28 05:34:26 alanmi Exp $] + +***********************************************************************/ + +#ifndef __MAPPER_H__ +#define __MAPPER_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +typedef struct Map_ManStruct_t_ Map_Man_t; +typedef struct Map_NodeStruct_t_ Map_Node_t; +typedef struct Map_NodeVecStruct_t_ Map_NodeVec_t; +typedef struct Map_CutStruct_t_ Map_Cut_t; +typedef struct Map_MatchStruct_t_ Map_Match_t; +typedef struct Map_SuperStruct_t_ Map_Super_t; +typedef struct Map_SuperLibStruct_t_ Map_SuperLib_t; +typedef struct Map_HashTableStruct_t_ Map_HashTable_t; +typedef struct Map_HashEntryStruct_t_ Map_HashEntry_t; +typedef struct Map_TimeStruct_t_ Map_Time_t; + +// the pair of rise/fall time parameters +struct Map_TimeStruct_t_ +{ + float Rise; + float Fall; + float Worst; +}; + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Map_IsComplement(p) (((int)((long) (p) & 01))) +#define Map_Regular(p) ((Map_Node_t *)((unsigned)(p) & ~01)) +#define Map_Not(p) ((Map_Node_t *)((long)(p) ^ 01)) +#define Map_NotCond(p,c) ((Map_Node_t *)((long)(p) ^ (c))) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== mapperCreate.c =============================================================*/ +extern Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ); +extern Map_Node_t * Map_NodeCreate( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ); +extern void Map_ManFree( Map_Man_t * pMan ); +extern void Map_ManPrintTimeStats( Map_Man_t * p ); +extern void Map_ManPrintStatsToFile( char * pName, float Area, float Delay, int Time ); +extern int Map_ManReadInputNum( Map_Man_t * p ); +extern int Map_ManReadOutputNum( Map_Man_t * p ); +extern Map_Node_t ** Map_ManReadInputs ( Map_Man_t * p ); +extern Map_Node_t ** Map_ManReadOutputs( Map_Man_t * p ); +extern Map_Node_t * Map_ManReadConst1 ( Map_Man_t * p ); +extern Map_Time_t * Map_ManReadInputArrivals( Map_Man_t * p ); +extern Mio_Library_t * Map_ManReadGenLib ( Map_Man_t * p ); +extern bool Map_ManReadVerbose( Map_Man_t * p ); +extern void Map_ManSetTimeToMap( Map_Man_t * p, int Time ); +extern void Map_ManSetTimeToNet( Map_Man_t * p, int Time ); +extern void Map_ManSetTimeSweep( Map_Man_t * p, int Time ); +extern void Map_ManSetTimeTotal( Map_Man_t * p, int Time ); +extern void Map_ManSetOutputNames( Map_Man_t * p, char ** ppNames ); +extern void Map_ManSetAreaRecovery( Map_Man_t * p, int fAreaRecovery ); +extern void Map_ManSetDelayTarget( Map_Man_t * p, float DelayTarget ); +extern void Map_ManSetInputArrivals( Map_Man_t * p, Map_Time_t * pArrivals ); +extern void Map_ManSetObeyFanoutLimits( Map_Man_t * p, bool fObeyFanoutLimits ); +extern void Map_ManSetNumIterations( Map_Man_t * p, int nNumIterations ); +extern int Map_ManReadPass( Map_Man_t * p ); +extern void Map_ManSetPass( Map_Man_t * p, int nPass ); +extern int Map_ManReadFanoutViolations( Map_Man_t * p ); +extern void Map_ManSetFanoutViolations( Map_Man_t * p, int nVio ); +extern void Map_ManSetChoiceNodeNum( Map_Man_t * p, int nChoiceNodes ); +extern void Map_ManSetChoiceNum( Map_Man_t * p, int nChoices ); +extern void Map_ManSetVerbose( Map_Man_t * p, int fVerbose ); + +extern Map_Man_t * Map_NodeReadMan( Map_Node_t * p ); +extern char * Map_NodeReadData( Map_Node_t * p, int fPhase ); +extern int Map_NodeReadNum( Map_Node_t * p ); +extern int Map_NodeReadLevel( Map_Node_t * p ); +extern Map_Cut_t * Map_NodeReadCuts( Map_Node_t * p ); +extern Map_Cut_t * Map_NodeReadCutBest( Map_Node_t * p, int fPhase ); +extern Map_Node_t * Map_NodeReadOne( Map_Node_t * p ); +extern Map_Node_t * Map_NodeReadTwo( Map_Node_t * p ); +extern void Map_NodeSetData( Map_Node_t * p, int fPhase, char * pData ); +extern void Map_NodeSetNextE( Map_Node_t * p, Map_Node_t * pNextE ); +extern void Map_NodeSetRepr( Map_Node_t * p, Map_Node_t * pRepr ); + +extern int Map_NodeIsConst( Map_Node_t * p ); +extern int Map_NodeIsVar( Map_Node_t * p ); +extern int Map_NodeIsAnd( Map_Node_t * p ); +extern int Map_NodeComparePhase( Map_Node_t * p1, Map_Node_t * p2 ); + +extern Map_Super_t * Map_CutReadSuperBest( Map_Cut_t * p, int fPhase ); +extern Map_Super_t * Map_CutReadSuper0( Map_Cut_t * p ); +extern Map_Super_t * Map_CutReadSuper1( Map_Cut_t * p ); +extern int Map_CutReadLeavesNum( Map_Cut_t * p ); +extern Map_Node_t ** Map_CutReadLeaves( Map_Cut_t * p ); +extern unsigned Map_CutReadPhaseBest( Map_Cut_t * p, int fPhase ); +extern unsigned Map_CutReadPhase0( Map_Cut_t * p ); +extern unsigned Map_CutReadPhase1( Map_Cut_t * p ); + +extern char * Map_SuperReadFormula( Map_Super_t * p ); +extern Mio_Gate_t * Map_SuperReadRoot( Map_Super_t * p ); +extern int Map_SuperReadNum( Map_Super_t * p ); +extern Map_Super_t ** Map_SuperReadFanins( Map_Super_t * p ); +extern int Map_SuperReadFaninNum( Map_Super_t * p ); +extern Map_Super_t * Map_SuperReadNext( Map_Super_t * p ); +extern int Map_SuperReadNumPhases( Map_Super_t * p ); +extern unsigned char * Map_SuperReadPhases( Map_Super_t * p ); +extern int Map_SuperReadFanoutLimit( Map_Super_t * p ); + +extern Mio_Library_t * Map_SuperLibReadGenLib( Map_SuperLib_t * p ); +extern float Map_SuperLibReadAreaInv( Map_SuperLib_t * p ); +extern Map_Time_t Map_SuperLibReadDelayInv( Map_SuperLib_t * p ); +extern int Map_SuperLibReadVarsMax( Map_SuperLib_t * p ); + +extern Map_Node_t * Map_NodeAnd( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ); +extern Map_Node_t * Map_NodeOr( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ); +extern Map_Node_t * Map_NodeExor( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ); +extern Map_Node_t * Map_NodeMux( Map_Man_t * p, Map_Node_t * pNode, Map_Node_t * pNodeT, Map_Node_t * pNodeE ); +extern void Map_NodeSetChoice( Map_Man_t * pMan, Map_Node_t * pNodeOld, Map_Node_t * pNodeNew ); + +/*=== resmCanon.c =============================================================*/ +extern int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] ); +/*=== mapperCut.c =============================================================*/ +extern void Map_MappingCreatePiCuts( Map_Man_t * p ); +extern Map_Cut_t * Map_CutAlloc( Map_Man_t * p ); +/*=== mapperCutUtils.c =============================================================*/ +extern void Map_CutCreateFromNode( Map_Man_t * p, Map_Super_t * pSuper, int iRoot, unsigned uPhaseRoot, + int * pLeaves, int nLeaves, unsigned uPhaseLeaves ); +/*=== mapperCore.c =============================================================*/ +extern int Map_Mapping( Map_Man_t * p ); +/*=== mapperLib.c =============================================================*/ +extern int Map_SuperLibDeriveFromGenlib( Mio_Library_t * pLib ); +/*=== mapperMntk.c =============================================================*/ +//extern Mntk_Man_t * Map_ConvertMappingToMntk( Map_Man_t * pMan ); +/*=== mapperSuper.c =============================================================*/ +extern char * Map_LibraryReadFormulaStep( char * pFormula, char * pStrings[], int * pnStrings ); +/*=== mapperSweep.c =============================================================*/ +extern void Map_NetworkSweep( Abc_Ntk_t * pNet ); +/*=== mapperTable.c =============================================================*/ +extern Map_Super_t * Map_SuperTableLookupC( Map_SuperLib_t * pLib, unsigned uTruth[] ); +/*=== mapperTime.c =============================================================*/ +/*=== mapperUtil.c =============================================================*/ +extern int Map_ManCheckConsistency( Map_Man_t * p ); +extern st_table * Map_CreateTableGate2Super( Map_Man_t * p ); +extern void Map_ManCleanData( Map_Man_t * p ); +extern void Map_MappingSetupTruthTables( unsigned uTruths[][2] ); +extern void Map_MappingSetupTruthTablesLarge( unsigned uTruths[][32] ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// +#endif diff --git a/src/map/mapper/mapperCanon.c b/src/map/mapper/mapperCanon.c new file mode 100644 index 00000000..c5186c7e --- /dev/null +++ b/src/map/mapper/mapperCanon.c @@ -0,0 +1,161 @@ +/**CFile**************************************************************** + + FileName [mapperCanon.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperCanon.c,v 1.2 2005/01/23 06:59:42 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase ); +static void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the N-canonical form of the Boolean function.] + + Description [The N-canonical form is defined as the truth table with + the minimum integer value. This function exhaustively enumerates + through the complete set of 2^N phase assignments.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] ) +{ + unsigned uTruthPerm[2]; + int nMints, nPhases, m; + + nPhases = 0; + nMints = (1 << nVarsReal); + if ( nVarsMax < 6 ) + { + uTruthRes[0] = MAP_MASK(32); + for ( m = 0; m < nMints; m++ ) + { + uTruthPerm[0] = Map_CanonComputePhase( uTruths, nVarsMax, uTruth[0], m ); + if ( uTruthRes[0] > uTruthPerm[0] ) + { + uTruthRes[0] = uTruthPerm[0]; + nPhases = 0; + puPhases[nPhases++] = (unsigned char)m; + } + else if ( uTruthRes[0] == uTruthPerm[0] ) + { + if ( nPhases < 4 ) // the max number of phases in Map_Super_t + puPhases[nPhases++] = (unsigned char)m; + } + } + uTruthRes[1] = uTruthRes[0]; + } + else + { + uTruthRes[0] = MAP_MASK(32); + uTruthRes[1] = MAP_MASK(32); + for ( m = 0; m < nMints; m++ ) + { + Map_CanonComputePhase6( uTruths, nVarsMax, uTruth, m, uTruthPerm ); + if ( uTruthRes[1] > uTruthPerm[1] || uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] > uTruthPerm[0] ) + { + uTruthRes[0] = uTruthPerm[0]; + uTruthRes[1] = uTruthPerm[1]; + nPhases = 0; + puPhases[nPhases++] = (unsigned char)m; + } + else if ( uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] == uTruthPerm[0] ) + { + if ( nPhases < 4 ) // the max number of phases in Map_Super_t + puPhases[nPhases++] = (unsigned char)m; + } + } + } + assert( nPhases > 0 ); +// printf( "%d ", nPhases ); + return nPhases; +} + +/**Function************************************************************* + + Synopsis [Performs phase transformation for one function of less than 6 variables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase ) +{ + int v, Shift; + for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 ) + if ( uPhase & Shift ) + uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift)); + return uTruth; +} + +/**Function************************************************************* + + Synopsis [Performs phase transformation for one function of 6 variables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] ) +{ + unsigned uTemp; + int v, Shift; + + // initialize the result + uTruthRes[0] = uTruth[0]; + uTruthRes[1] = uTruth[1]; + if ( uPhase == 0 ) + return; + // compute the phase + for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 ) + if ( uPhase & Shift ) + { + if ( Shift < 32 ) + { + uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift)); + uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift)); + } + else + { + uTemp = uTruthRes[0]; + uTruthRes[0] = uTruthRes[1]; + uTruthRes[1] = uTemp; + } + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperCore.c b/src/map/mapper/mapperCore.c new file mode 100644 index 00000000..415e4974 --- /dev/null +++ b/src/map/mapper/mapperCore.c @@ -0,0 +1,167 @@ +/**CFile**************************************************************** + + FileName [mapperCore.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperCore.c,v 1.7 2004/10/01 23:41:04 satrajit Exp $] + +***********************************************************************/ + +#include "mapperInt.h" +//#include "resm.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs technology mapping for the given object graph.] + + Description [The object graph is stored in the mapping manager. + First, the AND nodes that fanout into POs are collected in the DFS order. + Two preprocessing steps are performed: the k-feasible cuts are computed + for each node and the truth tables are computed for each cut. Next, the + delay-optimal matches are assigned for each node, followed by several + iterations of area recoveryd: using area flow (global optimization) + and using exact area at a node (local optimization).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_Mapping( Map_Man_t * p ) +{ + int fUseAreaFlow = 1; + int fUseExactArea = 1; + int fUseExactAreaWithPhase = 1; + int clk; + + ////////////////////////////////////////////////////////////////////// + // perform pre-mapping computations + // collect the nodes reachable from POs in the DFS order (including the choices) + p->vAnds = Map_MappingDfs( p, 1 ); + if ( p->fVerbose ) + Map_MappingReportChoices( p ); + Map_MappingSetChoiceLevels( p ); // should always be called before mapping! +// return 1; + + // compute the cuts of nodes in the DFS order + clk = clock(); + Map_MappingCuts( p ); + p->timeCuts = clock() - clk; + // derive the truth tables + clk = clock(); + Map_MappingTruths( p ); + p->timeTruth = clock() - clk; + ////////////////////////////////////////////////////////////////////// + + ////////////////////////////////////////////////////////////////////// + // compute the minimum-delay mapping + clk = clock(); + p->fMappingMode = 0; + if ( !Map_MappingMatches( p ) ) + return 0; + p->timeMatch = clock() - clk; + // compute the references and collect the nodes used in the mapping + Map_MappingSetRefs( p ); + p->AreaBase = Map_MappingGetArea( p, p->vMapping ); +if ( p->fVerbose ) +{ +printf( "Delay : FanViols = %5d Flow = %11.1f Area = %11.1f %4.1f %% ", + 0, Map_MappingGetAreaFlow(p), p->AreaBase, 0.0 ); +PRT( "Time", p->timeMatch ); +} + ////////////////////////////////////////////////////////////////////// + + ////////////////////////////////////////////////////////////////////// + // perform area recovery using area flow + clk = clock(); + if ( fUseAreaFlow ) + { + // compute the required times and the fanouts + Map_TimeComputeRequiredGlobal( p ); + // recover area flow + p->fMappingMode = 1; + Map_MappingMatches( p ); + // compute the references and collect the nodes used in the mapping + Map_MappingSetRefs( p ); + p->AreaFinal = Map_MappingGetArea( p, p->vMapping ); +if ( p->fVerbose ) +{ +printf( "AreaFlow : FanViols = %5d Flow = %11.1f Area = %11.1f %4.1f %% ", + 0, Map_MappingGetAreaFlow(p), p->AreaFinal, + 100.0*(p->AreaBase-p->AreaFinal)/p->AreaBase ); +PRT( "Time", clock() - clk ); +} + } + p->timeArea += clock() - clk; + ////////////////////////////////////////////////////////////////////// + + ////////////////////////////////////////////////////////////////////// + // perform area recovery using exact area + clk = clock(); + if ( fUseExactArea ) + { + // compute the required times and the fanouts + Map_TimeComputeRequiredGlobal( p ); + // recover area flow + p->fMappingMode = 2; + Map_MappingMatches( p ); + // compute the references and collect the nodes used in the mapping + Map_MappingSetRefs( p ); + p->AreaFinal = Map_MappingGetArea( p, p->vMapping ); +if ( p->fVerbose ) +{ +printf( "Area : FanViols = %5d Flow = %11.1f Area = %11.1f %4.1f %% ", + 0, 0.0, p->AreaFinal, + 100.0*(p->AreaBase-p->AreaFinal)/p->AreaBase ); +PRT( "Time", clock() - clk ); +} + } + p->timeArea += clock() - clk; + ////////////////////////////////////////////////////////////////////// + + ////////////////////////////////////////////////////////////////////// + // perform area recovery using exact area + clk = clock(); + if ( fUseExactAreaWithPhase ) + { + // compute the required times and the fanouts + Map_TimeComputeRequiredGlobal( p ); + // recover area flow + p->fMappingMode = 3; + Map_MappingMatches( p ); + // compute the references and collect the nodes used in the mapping + Map_MappingSetRefs( p ); + p->AreaFinal = Map_MappingGetArea( p, p->vMapping ); +if ( p->fVerbose ) +{ +printf( "Area : FanViols = %5d Flow = %11.1f Area = %11.1f %4.1f %% ", + 0, 0.0, p->AreaFinal, + 100.0*(p->AreaBase-p->AreaFinal)/p->AreaBase ); +PRT( "Time", clock() - clk ); +} + } + p->timeArea += clock() - clk; + ////////////////////////////////////////////////////////////////////// + + // print the arrival times of the latest outputs + if ( p->fVerbose ) + Map_MappingPrintOutputArrivals( p ); + return 1; +} diff --git a/src/map/mapper/mapperCreate.c b/src/map/mapper/mapperCreate.c new file mode 100644 index 00000000..61c90d1c --- /dev/null +++ b/src/map/mapper/mapperCreate.c @@ -0,0 +1,592 @@ +/**CFile**************************************************************** + + FileName [mapperCreate.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperCreate.c,v 1.15 2005/02/28 05:34:26 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Map_TableCreate( Map_Man_t * p ); +static void Map_TableResize( Map_Man_t * p ); +static Map_Node_t * Map_TableLookup( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ); + +// hash key for the structural hash table +static inline unsigned Map_HashKey2( Map_Node_t * p0, Map_Node_t * p1, int TableSize ) { return ((unsigned)(p0) + (unsigned)(p1) * 12582917) % TableSize; } + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads parameters from the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_ManReadInputNum( Map_Man_t * p ) { return p->nInputs; } +int Map_ManReadOutputNum( Map_Man_t * p ) { return p->nOutputs; } +Map_Node_t ** Map_ManReadInputs ( Map_Man_t * p ) { return p->pInputs; } +Map_Node_t ** Map_ManReadOutputs( Map_Man_t * p ) { return p->pOutputs; } +Map_Node_t * Map_ManReadConst1 ( Map_Man_t * p ) { return p->pConst1; } +Map_Time_t * Map_ManReadInputArrivals( Map_Man_t * p ) { return p->pInputArrivals;} +Mio_Library_t * Map_ManReadGenLib ( Map_Man_t * p ) { return p->pSuperLib->pGenlib; } +bool Map_ManReadVerbose( Map_Man_t * p ) { return p->fVerbose; } +void Map_ManSetTimeToMap( Map_Man_t * p, int Time ) { p->timeToMap = Time; } +void Map_ManSetTimeToNet( Map_Man_t * p, int Time ) { p->timeToNet = Time; } +void Map_ManSetTimeSweep( Map_Man_t * p, int Time ) { p->timeSweep = Time; } +void Map_ManSetTimeTotal( Map_Man_t * p, int Time ) { p->timeTotal = Time; } +void Map_ManSetOutputNames( Map_Man_t * p, char ** ppNames ) { p->ppOutputNames = ppNames; } +void Map_ManSetAreaRecovery( Map_Man_t * p, int fAreaRecovery ) { p->fAreaRecovery = fAreaRecovery;} +void Map_ManSetDelayTarget( Map_Man_t * p, float DelayTarget ) { p->DelayTarget = DelayTarget;} +void Map_ManSetInputArrivals( Map_Man_t * p, Map_Time_t * pArrivals ) { p->pInputArrivals = pArrivals;} +void Map_ManSetObeyFanoutLimits( Map_Man_t * p, bool fObeyFanoutLimits ) { p->fObeyFanoutLimits = fObeyFanoutLimits; } +void Map_ManSetNumIterations( Map_Man_t * p, int nIterations ) { p->nIterations = nIterations; } +int Map_ManReadFanoutViolations( Map_Man_t * p ) { return p->nFanoutViolations; } +void Map_ManSetFanoutViolations( Map_Man_t * p, int nVio ) { p->nFanoutViolations = nVio; } +void Map_ManSetChoiceNodeNum( Map_Man_t * p, int nChoiceNodes ) { p->nChoiceNodes = nChoiceNodes; } +void Map_ManSetChoiceNum( Map_Man_t * p, int nChoices ) { p->nChoices = nChoices; } +void Map_ManSetVerbose( Map_Man_t * p, int fVerbose ) { p->fVerbose = fVerbose; } + +/**Function************************************************************* + + Synopsis [Reads parameters from the mapping node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Man_t * Map_NodeReadMan( Map_Node_t * p ) { return p->p; } +char * Map_NodeReadData( Map_Node_t * p, int fPhase ) { return fPhase? p->pData1 : p->pData0; } +int Map_NodeReadNum( Map_Node_t * p ) { return p->Num; } +int Map_NodeReadLevel( Map_Node_t * p ) { return Map_Regular(p)->Level; } +Map_Cut_t * Map_NodeReadCuts( Map_Node_t * p ) { return p->pCuts; } +Map_Cut_t * Map_NodeReadCutBest( Map_Node_t * p, int fPhase ) { return p->pCutBest[fPhase]; } +Map_Node_t * Map_NodeReadOne( Map_Node_t * p ) { return p->p1; } +Map_Node_t * Map_NodeReadTwo( Map_Node_t * p ) { return p->p2; } +void Map_NodeSetData( Map_Node_t * p, int fPhase, char * pData ) { if (fPhase) p->pData1 = pData; else p->pData0 = pData; } +void Map_NodeSetNextE( Map_Node_t * p, Map_Node_t * pNextE ) { p->pNextE = pNextE; } +void Map_NodeSetRepr( Map_Node_t * p, Map_Node_t * pRepr ) { p->pRepr = pRepr; } + +/**Function************************************************************* + + Synopsis [Checks the type of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeIsConst( Map_Node_t * p ) { return (Map_Regular(p))->Num == -1; } +int Map_NodeIsVar( Map_Node_t * p ) { return (Map_Regular(p))->p1 == NULL && (Map_Regular(p))->Num >= 0; } +int Map_NodeIsAnd( Map_Node_t * p ) { return (Map_Regular(p))->p1 != NULL; } +int Map_NodeComparePhase( Map_Node_t * p1, Map_Node_t * p2 ) { assert( !Map_IsComplement(p1) ); assert( !Map_IsComplement(p2) ); return p1->fInv ^ p2->fInv; } + +/**Function************************************************************* + + Synopsis [Reads parameters from the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Super_t * Map_CutReadSuperBest( Map_Cut_t * p, int fPhase ) { return p->M[fPhase].pSuperBest;} +Map_Super_t * Map_CutReadSuper0( Map_Cut_t * p ) { return p->M[0].pSuperBest;} +Map_Super_t * Map_CutReadSuper1( Map_Cut_t * p ) { return p->M[1].pSuperBest;} +int Map_CutReadLeavesNum( Map_Cut_t * p ) { return p->nLeaves; } +Map_Node_t ** Map_CutReadLeaves( Map_Cut_t * p ) { return p->ppLeaves; } +unsigned Map_CutReadPhaseBest( Map_Cut_t * p, int fPhase ) { return p->M[fPhase].uPhaseBest;} +unsigned Map_CutReadPhase0( Map_Cut_t * p ) { return p->M[0].uPhaseBest;} +unsigned Map_CutReadPhase1( Map_Cut_t * p ) { return p->M[1].uPhaseBest;} + +/**Function************************************************************* + + Synopsis [Reads parameters from the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Map_SuperReadFormula( Map_Super_t * p ) { return p->pFormula; } +Mio_Gate_t * Map_SuperReadRoot( Map_Super_t * p ) { return p->pRoot; } +int Map_SuperReadNum( Map_Super_t * p ) { return p->Num; } +Map_Super_t ** Map_SuperReadFanins( Map_Super_t * p ) { return p->pFanins; } +int Map_SuperReadFaninNum( Map_Super_t * p ) { return p->nFanins; } +Map_Super_t * Map_SuperReadNext( Map_Super_t * p ) { return p->pNext; } +int Map_SuperReadNumPhases( Map_Super_t * p ) { return p->nPhases; } +unsigned char * Map_SuperReadPhases( Map_Super_t * p ) { return p->uPhases; } +int Map_SuperReadFanoutLimit( Map_Super_t * p ) { return p->nFanLimit;} + +Mio_Library_t * Map_SuperLibReadGenLib( Map_SuperLib_t * p ) { return p->pGenlib; } +float Map_SuperLibReadAreaInv( Map_SuperLib_t * p ) { return p->AreaInv; } +Map_Time_t Map_SuperLibReadDelayInv( Map_SuperLib_t * p ) { return p->tDelayInv;} +int Map_SuperLibReadVarsMax( Map_SuperLib_t * p ) { return p->nVarsMax; } + + +/**Function************************************************************* + + Synopsis [Create the mapping manager.] + + Description [The number of inputs and outputs is assumed to be + known is advance. It is much simpler to have them fixed upfront. + When it comes to representing the object graph in the form of + AIG, the resulting manager is similar to the regular AIG manager, + except that it does not use reference counting (and therefore + does not have garbage collections). It does have table resizing. + The data structure is more flexible to represent additional + information needed for mapping.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose ) +{ + Map_Man_t * p; + int i; + + // derive the supergate library + if ( Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()) == NULL ) + { + printf( "The supergate library is not specified. Use \"read_library\" or \"read_super\".\n" ); + return NULL; + } + + // start the manager + p = ALLOC( Map_Man_t, 1 ); + memset( p, 0, sizeof(Map_Man_t) ); + p->pSuperLib = Abc_FrameReadLibSuper(Abc_FrameGetGlobalFrame()); + p->nVarsMax = p->pSuperLib->nVarsMax; + p->fVerbose = fVerbose; + p->fEpsilon = (float)0.00001; + assert( p->nVarsMax > 0 ); + + // start various data structures + Map_TableCreate( p ); + Map_MappingSetupTruthTables( p->uTruths ); + Map_MappingSetupTruthTablesLarge( p->uTruthsLarge ); +// printf( "Node = %d bytes. Cut = %d bytes. Super = %d bytes.\n", sizeof(Map_Node_t), sizeof(Map_Cut_t), sizeof(Map_Super_t) ); + p->mmNodes = Extra_MmFixedStart( sizeof(Map_Node_t) ); + p->mmCuts = Extra_MmFixedStart( sizeof(Map_Cut_t) ); + + // make sure the constant node will get index -1 + p->nNodes = -1; + // create the constant node + p->pConst1 = Map_NodeCreate( p, NULL, NULL ); + p->vNodesAll = Map_NodeVecAlloc( 100 ); + p->vNodesTemp = Map_NodeVecAlloc( 100 ); + p->vMapping = Map_NodeVecAlloc( 100 ); + p->vInside = Map_NodeVecAlloc( 100 ); + p->vFanins = Map_NodeVecAlloc( 100 ); + + // create the PI nodes + p->nInputs = nInputs; + p->pInputs = ALLOC( Map_Node_t *, nInputs ); + for ( i = 0; i < nInputs; i++ ) + p->pInputs[i] = Map_NodeCreate( p, NULL, NULL ); + + // create the place for the output nodes + p->nOutputs = nOutputs; + p->pOutputs = ALLOC( Map_Node_t *, nOutputs ); + memset( p->pOutputs, 0, sizeof(Map_Node_t *) * nOutputs ); + return p; +} + +/**Function************************************************************* + + Synopsis [Deallocates the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_ManFree( Map_Man_t * p ) +{ +// int i; +// for ( i = 0; i < p->vNodesAll->nSize; i++ ) +// Map_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts ); +// Map_NodeVecFree( p->pConst1->vFanouts ); + if ( p->vInside ) + Map_NodeVecFree( p->vInside ); + if ( p->vFanins ) + Map_NodeVecFree( p->vFanins ); + if ( p->vAnds ) + Map_NodeVecFree( p->vAnds ); + if ( p->vNodesAll ) + Map_NodeVecFree( p->vNodesAll ); + if ( p->vNodesTemp ) + Map_NodeVecFree( p->vNodesTemp ); + if ( p->vMapping ) + Map_NodeVecFree( p->vMapping ); + Extra_MmFixedStop( p->mmNodes, 0 ); + Extra_MmFixedStop( p->mmCuts, 0 ); + FREE( p->pInputArrivals ); + FREE( p->pInputs ); + FREE( p->pOutputs ); + FREE( p->pBins ); +// FREE( p->ppOutputNames ); + if ( p->pSimInfo ) FREE( p->pSimInfo[0] ); + FREE( p->pSimInfo ); + FREE( p ); +} + + +/**Function************************************************************* + + Synopsis [Deallocates the mapping manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_ManPrintTimeStats( Map_Man_t * p ) +{ + printf( "N-canonical = %d. Matchings = %d. Phases = %d. ", p->nCanons, p->nMatches, p->nPhases ); + printf( "Choice nodes = %d. Choices = %d.\n", p->nChoiceNodes, p->nChoices ); + PRT( "ToMap", p->timeToMap ); + PRT( "Cuts ", p->timeCuts ); + PRT( "Truth", p->timeTruth ); + PRT( "Match", p->timeMatch ); + PRT( "Area ", p->timeArea ); + PRT( "Sweep", p->timeSweep ); + PRT( "ToNet", p->timeToNet ); + PRT( "TOTAL", p->timeTotal ); + if ( p->time1 ) { PRT( "time1", p->time1 ); } + if ( p->time2 ) { PRT( "time2", p->time2 ); } + if ( p->time3 ) { PRT( "time3", p->time3 ); } +} + +/**Function************************************************************* + + Synopsis [Prints the mapping stats.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_ManPrintStatsToFile( char * pName, float Area, float Delay, int Time ) +{ + FILE * pTable; + pTable = fopen( "stats.txt", "a+" ); + fprintf( pTable, "%s ", pName ); + fprintf( pTable, "%4.2f ", Area ); + fprintf( pTable, "%4.2f ", Delay ); + fprintf( pTable, "%4.2f\n", (float)(Time)/(float)(CLOCKS_PER_SEC) ); + fclose( pTable ); +} + +/**Function************************************************************* + + Synopsis [Creates a new node.] + + Description [This procedure should be called to create the constant + node and the PI nodes first.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeCreate( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ) +{ + Map_Node_t * pNode; + // create the node + pNode = (Map_Node_t *)Extra_MmFixedEntryFetch( p->mmNodes ); + memset( pNode, 0, sizeof(Map_Node_t) ); + pNode->tRequired[0].Rise = pNode->tRequired[0].Fall = pNode->tRequired[0].Worst = MAP_FLOAT_LARGE; + pNode->tRequired[1].Rise = pNode->tRequired[1].Fall = pNode->tRequired[1].Worst = MAP_FLOAT_LARGE; + pNode->p1 = p1; + pNode->p2 = p2; + pNode->p = p; + // set the number of this node + pNode->Num = p->nNodes++; + // place to store the fanouts +// pNode->vFanouts = Map_NodeVecAlloc( 5 ); + // store this node in the internal array + if ( pNode->Num >= 0 ) + Map_NodeVecPush( p->vNodesAll, pNode ); + else + pNode->fInv = 1; + // set the level of this node + if ( p1 ) + { + // create the fanout info + Map_NodeAddFaninFanout( Map_Regular(p1), pNode ); + Map_NodeAddFaninFanout( Map_Regular(p2), pNode ); + pNode->Level = 1 + MAP_MAX(Map_Regular(pNode->p1)->Level, Map_Regular(pNode->p2)->Level); + pNode->fInv = Map_NodeIsSimComplement(p1) & Map_NodeIsSimComplement(p2); + } + // reference the inputs (will be used to compute the number of fanouts) + if ( p1 ) Map_NodeRef(p1); + if ( p2 ) Map_NodeRef(p2); + + pNode->nRefEst[0] = pNode->nRefEst[1] = -1; + return pNode; +} + +/**Function************************************************************* + + Synopsis [Create the unique table of AND gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TableCreate( Map_Man_t * pMan ) +{ + assert( pMan->pBins == NULL ); + pMan->nBins = Cudd_Prime(5000); + pMan->pBins = ALLOC( Map_Node_t *, pMan->nBins ); + memset( pMan->pBins, 0, sizeof(Map_Node_t *) * pMan->nBins ); + pMan->nNodes = 0; +} + +/**Function************************************************************* + + Synopsis [Looks up the AND2 node in the unique table.] + + Description [This procedure implements one-level hashing. All the nodes + are hashed by their children. If the node with the same children was already + created, it is returned by the call to this procedure. If it does not exist, + this procedure creates a new node with these children. ] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_TableLookup( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2 ) +{ + Map_Node_t * pEnt; + unsigned Key; + + if ( p1 == p2 ) + return p1; + if ( p1 == Map_Not(p2) ) + return Map_Not(pMan->pConst1); + if ( Map_NodeIsConst(p1) ) + { + if ( p1 == pMan->pConst1 ) + return p2; + return Map_Not(pMan->pConst1); + } + if ( Map_NodeIsConst(p2) ) + { + if ( p2 == pMan->pConst1 ) + return p1; + return Map_Not(pMan->pConst1); + } + + if ( Map_Regular(p1)->Num > Map_Regular(p2)->Num ) + pEnt = p1, p1 = p2, p2 = pEnt; + + Key = Map_HashKey2( p1, p2, pMan->nBins ); + for ( pEnt = pMan->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->p1 == p1 && pEnt->p2 == p2 ) + return pEnt; + // resize the table + if ( pMan->nNodes >= 2 * pMan->nBins ) + { + Map_TableResize( pMan ); + Key = Map_HashKey2( p1, p2, pMan->nBins ); + } + // create the new node + pEnt = Map_NodeCreate( pMan, p1, p2 ); + // add the node to the corresponding linked list in the table + pEnt->pNext = pMan->pBins[Key]; + pMan->pBins[Key] = pEnt; + return pEnt; +} + + +/**Function************************************************************* + + Synopsis [Resizes the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TableResize( Map_Man_t * pMan ) +{ + Map_Node_t ** pBinsNew; + Map_Node_t * pEnt, * pEnt2; + int nBinsNew, Counter, i, clk; + unsigned Key; + +clk = clock(); + // get the new table size + nBinsNew = Cudd_Prime(2 * pMan->nBins); + // allocate a new array + pBinsNew = ALLOC( Map_Node_t *, nBinsNew ); + memset( pBinsNew, 0, sizeof(Map_Node_t *) * nBinsNew ); + // rehash the entries from the old table + Counter = 0; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pEnt = pMan->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; + pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL ) + { + Key = Map_HashKey2( pEnt->p1, pEnt->p2, nBinsNew ); + pEnt->pNext = pBinsNew[Key]; + pBinsNew[Key] = pEnt; + Counter++; + } + assert( Counter == pMan->nNodes - pMan->nInputs ); + if ( pMan->fVerbose ) + { +// printf( "Increasing the unique table size from %6d to %6d. ", pMan->nBins, nBinsNew ); +// PRT( "Time", clock() - clk ); + } + // replace the table and the parameters + free( pMan->pBins ); + pMan->pBins = pBinsNew; + pMan->nBins = nBinsNew; +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeAnd( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ) +{ + Map_Node_t * pNode; + pNode = Map_TableLookup( p, p1, p2 ); + return pNode; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeOr( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ) +{ + Map_Node_t * pNode; + pNode = Map_Not( Map_TableLookup( p, Map_Not(p1), Map_Not(p2) ) ); + return pNode; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeExor( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 ) +{ + return Map_NodeMux( p, p1, Map_Not(p2), p2 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeMux( Map_Man_t * p, Map_Node_t * pC, Map_Node_t * pT, Map_Node_t * pE ) +{ + Map_Node_t * pAnd1, * pAnd2, * pRes; + pAnd1 = Map_TableLookup( p, pC, pT ); + pAnd2 = Map_TableLookup( p, Map_Not(pC), pE ); + pRes = Map_NodeOr( p, pAnd1, pAnd2 ); + return pRes; +} + + +/**Function************************************************************* + + Synopsis [Sets the node to be equivalent to the given one.] + + Description [This procedure is a work-around for the equivalence check. + Does not verify the equivalence. Use at the user's risk.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeSetChoice( Map_Man_t * pMan, Map_Node_t * pNodeOld, Map_Node_t * pNodeNew ) +{ + pNodeNew->pNextE = pNodeOld->pNextE; + pNodeOld->pNextE = pNodeNew; + pNodeNew->pRepr = pNodeOld; +} + + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c new file mode 100644 index 00000000..87592365 --- /dev/null +++ b/src/map/mapper/mapperCut.c @@ -0,0 +1,1072 @@ +/**CFile**************************************************************** + + FileName [mapperCut.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperCut.c,v 1.12 2005/02/28 05:34:27 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the largest number of cuts considered +#define MAP_CUTS_MAX_COMPUTE 200 +// the largest number of cuts used +#define MAP_CUTS_MAX_USE 50 + +// temporary hash table to store the cuts +typedef struct Map_CutTableStrutct_t Map_CutTable_t; +struct Map_CutTableStrutct_t +{ + Map_Cut_t ** pBins; // the table used for linear probing + int nBins; // the size of the table + int * pCuts; // the array of cuts currently stored + int nCuts; // the number of cuts currently stored + Map_Cut_t ** pArray; // the temporary array of cuts + Map_Cut_t ** pCuts1; // the temporary array of cuts + Map_Cut_t ** pCuts2; // the temporary array of cuts +}; + +// primes used to compute the hash key +static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 }; + +static Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t * pNode ); +static void Map_CutFilter( Map_Man_t * p, Map_Node_t * pNode ); +static Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable, Map_Cut_t * pList1, Map_Cut_t * pList2, int fComp1, int fComp2 ); +static int Map_CutMergeTwo( Map_Cut_t * pCut1, Map_Cut_t * pCut2, Map_Node_t * ppNodes[], int nNodesMax ); +static Map_Cut_t * Map_CutUnionLists( Map_Cut_t * pList1, Map_Cut_t * pList2 ); +static int Map_CutBelongsToList( Map_Cut_t * pList, Map_Node_t * ppNodes[], int nNodes ); + +static void Map_CutListPrint( Map_Man_t * pMan, Map_Node_t * pRoot ); +static void Map_CutListPrint2( Map_Man_t * pMan, Map_Node_t * pRoot ); +static void Map_CutPrint_( Map_Man_t * pMan, Map_Cut_t * pCut, Map_Node_t * pRoot ); + +static Map_CutTable_t * Map_CutTableStart( Map_Man_t * pMan ); +static void Map_CutTableStop( Map_CutTable_t * p ); +static unsigned Map_CutTableHash( Map_Node_t * ppNodes[], int nNodes ); +static int Map_CutTableLookup( Map_CutTable_t * p, Map_Node_t * ppNodes[], int nNodes ); +static Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node_t * ppNodes[], int nNodes ); +static void Map_CutTableRestart( Map_CutTable_t * p ); + +static Map_Cut_t * Map_CutSortCuts( Map_Man_t * pMan, Map_CutTable_t * p, Map_Cut_t * pList ); +static int Map_CutList2Array( Map_Cut_t ** pArray, Map_Cut_t * pList ); +static Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ); + + +// iterator through all the cuts of the list +#define Map_ListForEachCut( pList, pCut ) \ + for ( pCut = pList; \ + pCut; \ + pCut = pCut->pNext ) +#define Map_ListForEachCutSafe( pList, pCut, pCut2 ) \ + for ( pCut = pList, \ + pCut2 = pCut? pCut->pNext: NULL; \ + pCut; \ + pCut = pCut2, \ + pCut2 = pCut? pCut->pNext: NULL ) + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the cuts for each node in the object graph.] + + Description [The cuts are computed in one sweep over the mapping graph. + First, the elementary cuts, which include the node itself, are assigned + to the PI nodes. The internal nodes are considered in the DFS order. + Each node is two-input AND-gate. So to compute the cuts at a node, we + need to merge the sets of cuts of its two predecessors. The merged set + contains only unique cuts with the number of inputs equal to k or less. + Finally, the elementary cut, composed of the node itself, is added to + the set of cuts for the node. + + This procedure is pretty fast for 5-feasible cuts, but it dramatically + slows down on some "dense" networks when computing 6-feasible cuts. + The problem is that there are too many cuts in this case. We should + think how to heuristically trim the number of cuts in such cases, + to have reasonable runtime.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingCuts( Map_Man_t * p ) +{ + ProgressBar * pProgress; + Map_CutTable_t * pTable; + Map_Node_t * pNode; + Map_Cut_t * pCut; + int nCuts, nNodes, i; + // set the elementary cuts for the PI variables + assert( p->nVarsMax > 1 && p->nVarsMax < 7 ); + for ( i = 0; i < p->nInputs; i++ ) + { + pCut = Map_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = p->pInputs[i]; +// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + p->pInputs[i]->pCuts = pCut; + p->pInputs[i]->pCutBest[0] = NULL; // negative polarity is not mapped + p->pInputs[i]->pCutBest[1] = pCut; // positive polarity is a trivial cut + pCut->M[0].AreaFlow = 0.0; + pCut->M[1].AreaFlow = 0.0; + } + + // compute the cuts for the internal nodes + nNodes = p->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + pTable = Map_CutTableStart( p ); + for ( i = 0; i < nNodes; i++ ) + { + pNode = p->vAnds->pArray[i]; + if ( !Map_NodeIsAnd( pNode ) ) + continue; + Map_CutCompute( p, pTable, pNode ); + Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." ); + } + Extra_ProgressBarStop( pProgress ); + Map_CutTableStop( pTable ); + + // report the stats + if ( p->fVerbose ) + { + nCuts = Map_MappingCountAllCuts(p); + printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n", + p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes ); + } + + // print the cuts for the first primary output +// Map_CutListPrint( p, Map_Regular(p->pOutputs[0]) ); +} + +/**Function************************************************************* + + Synopsis [Performs technology mapping for variable-size-LUTs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingCreatePiCuts( Map_Man_t * p ) +{ + Map_Cut_t * pCut; + int i; + + // set the elementary cuts for the PI variables + for ( i = 0; i < p->nInputs; i++ ) + { + pCut = Map_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = p->pInputs[i]; +// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + p->pInputs[i]->pCuts = pCut; + p->pInputs[i]->pCutBest[1] = pCut; + p->pInputs[i]->pCutBest[0] = pCut; + // set the input arrival times +// p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i]; + + // set the input arrival times + pCut = p->pInputs[i]->pCutBest[1]; + pCut->M[1].tArrive = p->pInputArrivals[i]; + pCut->M[1].tArrive.Worst = MAP_MAX( pCut->M[1].tArrive.Rise, pCut->M[1].tArrive.Fall ); + // set the arrival times of the negative phases of the PI nodes + pCut = p->pInputs[i]->pCutBest[0]; + pCut->M[0].tArrive.Rise = p->pInputArrivals[i].Fall + p->pSuperLib->tDelayInv.Rise; + pCut->M[0].tArrive.Fall = p->pInputArrivals[i].Rise + p->pSuperLib->tDelayInv.Fall; + pCut->M[0].tArrive.Worst = MAP_MAX( pCut->M[0].tArrive.Rise, pCut->M[0].tArrive.Fall ); + + } +} + +/**Function************************************************************* + + Synopsis [Computes the cuts for one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t * pNode ) +{ + Map_Node_t * pTemp; + Map_Cut_t * pList, * pList1, * pList2; + Map_Cut_t * pCut; + + // if the cuts are computed return them + if ( pNode->pCuts ) + return pNode->pCuts; + + // compute the cuts for the children + pList1 = Map_Regular(pNode->p1)->pCuts; + pList2 = Map_Regular(pNode->p2)->pCuts; + // merge the lists + pList = Map_CutMergeLists( p, pTable, pList1, pList2, + Map_IsComplement(pNode->p1), Map_IsComplement(pNode->p2) ); + // if there are functionally equivalent nodes, union them with this list + assert( pList ); + // only add to the list of cuts if the node is a representative one + if ( pNode->pRepr == NULL ) + { + for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) + { + assert( pTemp->pCuts ); + pList = Map_CutUnionLists( pList, pTemp->pCuts ); + assert( pTemp->pCuts ); + pList = Map_CutSortCuts( p, pTable, pList ); + } + } + // add the new cut + pCut = Map_CutAlloc( p ); + pCut->nLeaves = 1; + pCut->ppLeaves[0] = pNode; +// pCut->fLevel = (float)pCut->ppLeaves[0]->Level; + // append (it is important that the elementary cut is appended first) + pCut->pNext = pList; + // set at the node + pNode->pCuts = pCut; + // remove the dominated cuts +// Map_CutFilter( p, pNode ); + // set the phase correctly + if ( pNode->pRepr && Map_NodeComparePhase(pNode, pNode->pRepr) ) + { + Map_ListForEachCut( pNode->pCuts, pCut ) + pCut->Phase = 1; + } +/* + { + int i, Counter = 0;; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + for ( i = 0; i < pCut->nLeaves; i++ ) + Counter += (pCut->ppLeaves[i]->Level >= pNode->Level); +// if ( Counter ) +// printf( " %d", Counter ); + } +*/ + return pCut; +} + +/**Function************************************************************* + + Synopsis [Filter the cuts using dominance.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutFilter( Map_Man_t * p, Map_Node_t * pNode ) +{ + Map_Cut_t * pTemp, * pPrev, * pCut, * pCut2; + int i, k, Counter; + + Counter = 0; + pPrev = pNode->pCuts; + Map_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 ) + { + // go through all the previous cuts up to pCut + for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext ) + { + // check if every node in pTemp is contained in pCut + for ( i = 0; i < pTemp->nLeaves; i++ ) + { + for ( k = 0; k < pCut->nLeaves; k++ ) + if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] ) + break; + if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut + break; + } + if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut + { + Counter++; + break; + } + } + if ( pTemp != pCut ) // pTemp contain pCut + { + pPrev->pNext = pCut->pNext; // skip pCut + // recycle pCut + Map_CutFree( p, pCut ); + } + else + pPrev = pCut; + } +// printf( "Dominated = %3d. \n", Counter ); +} + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable, + Map_Cut_t * pList1, Map_Cut_t * pList2, int fComp1, int fComp2 ) +{ + Map_Node_t * ppNodes[6]; + Map_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Map_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; + int nNodes, Counter, i; + Map_Cut_t ** ppArray1, ** ppArray2, ** ppArray3; + int nCuts1, nCuts2, nCuts3, k, fComp3; + + ppArray1 = pTable->pCuts1; + ppArray2 = pTable->pCuts2; + nCuts1 = Map_CutList2Array( ppArray1, pList1 ); + nCuts2 = Map_CutList2Array( ppArray2, pList2 ); + // swap the lists based on their length + if ( nCuts1 > nCuts2 ) + { + ppArray3 = ppArray1; + ppArray1 = ppArray2; + ppArray2 = ppArray3; + + nCuts3 = nCuts1; + nCuts1 = nCuts2; + nCuts2 = nCuts3; + + fComp3 = fComp1; + fComp1 = fComp2; + fComp2 = fComp3; + } + // pList1 is shorter or equal length compared to pList2 + + // prepare the manager for the cut computation + Map_CutTableRestart( pTable ); + // go through the cut pairs + Counter = 0; +// for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext ) +// for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext ) + for ( i = 0; i < nCuts1; i++ ) + { + for ( k = 0; k <= i; k++ ) + { + pTemp1 = ppArray1[i]; + pTemp2 = ppArray2[k]; + + // check if k-feasible cut exists + nNodes = Map_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Map_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == MAP_CUTS_MAX_COMPUTE ) + goto QUITS; + } + for ( k = 0; k < i; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + // check if k-feasible cut exists + nNodes = Map_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Map_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == MAP_CUTS_MAX_COMPUTE ) + goto QUITS; + } + } + // consider the rest of them + for ( i = nCuts1; i < nCuts2; i++ ) + for ( k = 0; k < nCuts1; k++ ) + { + pTemp1 = ppArray1[k]; + pTemp2 = ppArray2[i]; + + // check if k-feasible cut exists + nNodes = Map_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Map_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == MAP_CUTS_MAX_COMPUTE ) + goto QUITS; + } +QUITS : + // combine all the lists into one + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 1; i <= p->nVarsMax; i++ ) + { + if ( pLists[i] == NULL ) + continue; + // find the last entry + for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; + pPrev = pCut, pCut = pCut->pNext ); + // connect these lists + *ppListNew = pLists[i]; + ppListNew = &pPrev->pNext; + } + *ppListNew = NULL; + // soft the cuts by arrival times and use only the first MAP_CUTS_MAX_USE + pListNew = Map_CutSortCuts( p, pTable, pListNew ); + return pListNew; +} + + +/**Function************************************************************* + + Synopsis [Merges two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutMergeLists2( Map_Man_t * p, Map_CutTable_t * pTable, + Map_Cut_t * pList1, Map_Cut_t * pList2, int fComp1, int fComp2 ) +{ + Map_Node_t * ppNodes[6]; + Map_Cut_t * pListNew, ** ppListNew, * pLists[7] = { NULL }; + Map_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2; + int nNodes, Counter, i; + + // prepare the manager for the cut computation + Map_CutTableRestart( pTable ); + // go through the cut pairs + Counter = 0; + for ( pTemp1 = pList1; pTemp1; pTemp1 = pTemp1->pNext ) + for ( pTemp2 = pList2; pTemp2; pTemp2 = pTemp2->pNext ) + { + // check if k-feasible cut exists + nNodes = Map_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax ); + if ( nNodes == 0 ) + continue; + // consider the cut for possible addition to the set of new cuts + pCut = Map_CutTableConsider( p, pTable, ppNodes, nNodes ); + if ( pCut == NULL ) + continue; + // add data to the cut + pCut->pOne = Map_CutNotCond( pTemp1, fComp1 ); + pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 ); + // add it to the corresponding list + pCut->pNext = pLists[pCut->nLeaves]; + pLists[pCut->nLeaves] = pCut; + // count this cut and quit if limit is reached + Counter++; + if ( Counter == MAP_CUTS_MAX_COMPUTE ) + goto QUITS; + } +QUITS : + // combine all the lists into one + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 1; i <= p->nVarsMax; i++ ) + { + if ( pLists[i] == NULL ) + continue; + // find the last entry + for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; + pPrev = pCut, pCut = pCut->pNext ); + // connect these lists + *ppListNew = pLists[i]; + ppListNew = &pPrev->pNext; + } + *ppListNew = NULL; + // soft the cuts by arrival times and use only the first MAP_CUTS_MAX_USE + pListNew = Map_CutSortCuts( p, pTable, pListNew ); + return pListNew; +} + +/**Function************************************************************* + + Synopsis [Merges two cuts.] + + Description [Returns the number of nodes in the resulting cut, or 0 if the + cut is infeasible. Returns the resulting nodes in the array ppNodes[].] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutMergeTwo( Map_Cut_t * pCut1, Map_Cut_t * pCut2, Map_Node_t * ppNodes[], int nNodesMax ) +{ + Map_Node_t * pNodeTemp; + int nTotal, i, k, min, fMismatch; + + // check the special case when at least of the cuts is the largest + if ( pCut1->nLeaves == nNodesMax ) + { + if ( pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] ) + return 0; + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + else if ( pCut2->nLeaves == nNodesMax - 1 ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut1->ppLeaves[i]; + return nNodesMax; + } + } + else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax ) + { + // return 0 if the cuts are different + fMismatch = 0; + for ( i = 0; i < nNodesMax; i++ ) + if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] ) + { + if ( fMismatch == 1 ) + return 0; + fMismatch = 1; + } + // return nNodesMax if they are the same + for ( i = 0; i < nNodesMax; i++ ) + ppNodes[i] = pCut2->ppLeaves[i]; + return nNodesMax; + } + + // count the number of unique entries in pCut2 + nTotal = pCut1->nLeaves; + for ( i = 0; i < pCut2->nLeaves; i++ ) + { + // try to find this entry among the leaves of pCut1 + for ( k = 0; k < pCut1->nLeaves; k++ ) + if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] ) + break; + if ( k < pCut1->nLeaves ) // found + continue; + // we found a new entry to add + if ( nTotal == nNodesMax ) + return 0; + ppNodes[nTotal++] = pCut2->ppLeaves[i]; + } + // we know that the feasible cut exists + + // add the starting entries + for ( k = 0; k < pCut1->nLeaves; k++ ) + ppNodes[k] = pCut1->ppLeaves[k]; + + // selection-sort the entries + for ( i = 0; i < nTotal - 1; i++ ) + { + min = i; + for ( k = i+1; k < nTotal; k++ ) + if ( ppNodes[k] < ppNodes[min] ) + min = k; + pNodeTemp = ppNodes[i]; + ppNodes[i] = ppNodes[min]; + ppNodes[min] = pNodeTemp; + } + + return nTotal; +} + +/**Function************************************************************* + + Synopsis [Computes the union of the two lists of cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutUnionLists( Map_Cut_t * pList1, Map_Cut_t * pList2 ) +{ + Map_Cut_t * pTemp, * pRoot; + // find the last cut in the first list + pRoot = pList1; + Map_ListForEachCut( pList1, pTemp ) + pRoot = pTemp; + // attach the non-trival part of the second cut to the end of the first + assert( pRoot->pNext == NULL ); + pRoot->pNext = pList2->pNext; + pList2->pNext = NULL; + return pList1; +} + + +/**Function************************************************************* + + Synopsis [Checks whether the given cut belongs to the list.] + + Description [This procedure takes most of the runtime in the cut + computation.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutBelongsToList( Map_Cut_t * pList, Map_Node_t * ppNodes[], int nNodes ) +{ + Map_Cut_t * pTemp; + int i; + for ( pTemp = pList; pTemp; pTemp = pTemp->pNext ) + { + for ( i = 0; i < nNodes; i++ ) + if ( pTemp->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return 1; + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Counts all the cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCountAllCuts( Map_Man_t * pMan ) +{ + Map_Node_t * pNode; + Map_Cut_t * pCut; + int i, nCuts; + nCuts = 0; + for ( i = 0; i < pMan->nBins; i++ ) + for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext ) + for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext ) + if ( pCut->nLeaves > 1 ) // skip the elementary cuts + nCuts++; + return nCuts; +} + + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutListPrint( Map_Man_t * pMan, Map_Node_t * pRoot ) +{ + Map_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Map_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cuts in the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutListPrint2( Map_Man_t * pMan, Map_Node_t * pRoot ) +{ + Map_Cut_t * pTemp; + int Counter; + for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ ) + { + printf( "%2d : ", Counter + 1 ); + Map_CutPrint_( pMan, pTemp, pRoot ); + } +} + +/**Function************************************************************* + + Synopsis [Prints the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutPrint_( Map_Man_t * pMan, Map_Cut_t * pCut, Map_Node_t * pRoot ) +{ + int i; + printf( "(%3d) {", pRoot->Num ); + for ( i = 0; i < pMan->nVarsMax; i++ ) + if ( pCut->ppLeaves[i] ) + printf( " %3d", pCut->ppLeaves[i]->Num ); + printf( " }\n" ); +} + + + + + + + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_CutTable_t * Map_CutTableStart( Map_Man_t * pMan ) +{ + Map_CutTable_t * p; + // allocate the table + p = ALLOC( Map_CutTable_t, 1 ); + memset( p, 0, sizeof(Map_CutTable_t) ); + p->nBins = Cudd_Prime( 10 * MAP_CUTS_MAX_COMPUTE ); + p->pBins = ALLOC( Map_Cut_t *, p->nBins ); + memset( p->pBins, 0, sizeof(Map_Cut_t *) * p->nBins ); + p->pCuts = ALLOC( int, 2 * MAP_CUTS_MAX_COMPUTE ); + p->pArray = ALLOC( Map_Cut_t *, 2 * MAP_CUTS_MAX_COMPUTE ); + p->pCuts1 = ALLOC( Map_Cut_t *, 2 * MAP_CUTS_MAX_COMPUTE ); + p->pCuts2 = ALLOC( Map_Cut_t *, 2 * MAP_CUTS_MAX_COMPUTE ); + return p; +} + +/**Function************************************************************* + + Synopsis [Stops the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutTableStop( Map_CutTable_t * p ) +{ + free( p->pCuts1 ); + free( p->pCuts2 ); + free( p->pArray ); + free( p->pBins ); + free( p->pCuts ); + free( p ); +} + +/**Function************************************************************* + + Synopsis [Computes the hash value of the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_CutTableHash( Map_Node_t * ppNodes[], int nNodes ) +{ + unsigned uRes; + int i; + uRes = 0; + for ( i = 0; i < nNodes; i++ ) + uRes += s_HashPrimes[i] * ppNodes[i]->Num; + return uRes; +} + +/**Function************************************************************* + + Synopsis [Looks up the table for the available cut.] + + Description [Returns -1 if the same cut is found. Returns the index + of the cell where the cut should be added, if it does not exist.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutTableLookup( Map_CutTable_t * p, Map_Node_t * ppNodes[], int nNodes ) +{ + Map_Cut_t * pCut; + unsigned Key; + int b, i; + + Key = Map_CutTableHash(ppNodes, nNodes) % p->nBins; + for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins ) + { + pCut = p->pBins[b]; + if ( pCut->nLeaves != nNodes ) + continue; + for ( i = 0; i < nNodes; i++ ) + if ( pCut->ppLeaves[i] != ppNodes[i] ) + break; + if ( i == nNodes ) + return -1; + } + return b; +} + + +/**Function************************************************************* + + Synopsis [Starts the hash table to canonicize cuts.] + + Description [Considers addition of the cut to the hash table.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node_t * ppNodes[], int nNodes ) +{ + Map_Cut_t * pCut; + int Place, i; +// int clk; + // check the cut + Place = Map_CutTableLookup( p, ppNodes, nNodes ); + if ( Place == -1 ) + return NULL; + assert( nNodes > 0 ); + // create the new cut +//clk = clock(); + pCut = Map_CutAlloc( pMan ); +//pMan->time1 += clock() - clk; + pCut->nLeaves = nNodes; +// pCut->fLevel = 0; + for ( i = 0; i < nNodes; i++ ) + { + pCut->ppLeaves[i] = ppNodes[i]; +// pCut->fLevel += ppNodes[i]->Level; + } +// pCut->fLevel /= nNodes; + // add the cut to the table + assert( p->pBins[Place] == NULL ); + p->pBins[Place] = pCut; + // add the cut to the new list + p->pCuts[ p->nCuts++ ] = Place; + return pCut; +} + +/**Function************************************************************* + + Synopsis [Prepares the table to be used with other cuts.] + + Description [Restarts the table by cleaning the info about cuts stored + when the previous node was considered.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutTableRestart( Map_CutTable_t * p ) +{ + int i; + for ( i = 0; i < p->nCuts; i++ ) + { + assert( p->pBins[ p->pCuts[i] ] ); + p->pBins[ p->pCuts[i] ] = NULL; + } + p->nCuts = 0; +} + + + +/**Function************************************************************* + + Synopsis [Compares the cuts by the number of leaves and then by delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutSortCutsCompare( Map_Cut_t ** pC1, Map_Cut_t ** pC2 ) +{ + if ( (*pC1)->nLeaves < (*pC2)->nLeaves ) + return -1; + if ( (*pC1)->nLeaves > (*pC2)->nLeaves ) + return 1; +/* + if ( (*pC1)->fLevel < (*pC2)->fLevel ) + return -1; + if ( (*pC1)->fLevel > (*pC2)->fLevel ) + return 1; +*/ + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorts the cuts by average arrival time.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutSortCuts( Map_Man_t * pMan, Map_CutTable_t * p, Map_Cut_t * pList ) +{ + Map_Cut_t * pListNew; + int nCuts, i; +// int clk; + // move the cuts from the list into the array + nCuts = Map_CutList2Array( p->pCuts1, pList ); + assert( nCuts <= MAP_CUTS_MAX_COMPUTE ); + // sort the cuts +//clk = clock(); + qsort( (void *)p->pCuts1, nCuts, sizeof(Map_Cut_t *), + (int (*)(const void *, const void *)) Map_CutSortCutsCompare ); +//pMan->time2 += clock() - clk; + // move them back into the list + if ( nCuts > MAP_CUTS_MAX_USE - 1 ) + { + // free the remaining cuts + for ( i = MAP_CUTS_MAX_USE - 1; i < nCuts; i++ ) + Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] ); + // update the number of cuts + nCuts = MAP_CUTS_MAX_USE - 1; + } + pListNew = Map_CutArray2List( p->pCuts1, nCuts ); + return pListNew; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the list into the array.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutList2Array( Map_Cut_t ** pArray, Map_Cut_t * pList ) +{ + int i; + for ( i = 0; pList; pList = pList->pNext, i++ ) + pArray[i] = pList; + return i; +} + +/**Function************************************************************* + + Synopsis [Moves the nodes from the array into the list.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts ) +{ + Map_Cut_t * pListNew, ** ppListNew; + int i; + pListNew = NULL; + ppListNew = &pListNew; + for ( i = 0; i < nCuts; i++ ) + { + // connect these lists + *ppListNew = pArray[i]; + ppListNew = &pArray[i]->pNext; +//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel ); + } +//printf( "\n" ); + + *ppListNew = NULL; + return pListNew; +} + + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/mapper/mapperCutUtils.c b/src/map/mapper/mapperCutUtils.c new file mode 100644 index 00000000..9f572e75 --- /dev/null +++ b/src/map/mapper/mapperCutUtils.c @@ -0,0 +1,273 @@ +/**CFile**************************************************************** + + FileName [mapperCutUtils.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperCutUtils.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutAlloc( Map_Man_t * p ) +{ + Map_Cut_t * pCut; + Map_Match_t * pMatch; + pCut = (Map_Cut_t *)Extra_MmFixedEntryFetch( p->mmCuts ); + memset( pCut, 0, sizeof(Map_Cut_t) ); + + pMatch = pCut->M; + pMatch->AreaFlow = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Rise = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Fall = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Worst = MAP_FLOAT_LARGE; // unassigned + + pMatch = pCut->M + 1; + pMatch->AreaFlow = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Rise = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Fall = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Worst = MAP_FLOAT_LARGE; // unassigned + return pCut; +} + +/**Function************************************************************* + + Synopsis [Deallocates the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutFree( Map_Man_t * p, Map_Cut_t * pCut ) +{ + if ( pCut ) + Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pCut ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutPrint( Map_Man_t * p, Map_Node_t * pRoot, Map_Cut_t * pCut, int fPhase ) +{ + int i; + printf( "CUT: Delay = (%4.2f, %4.2f). Area = %4.2f. Nodes = %d -> {", + pCut->M[fPhase].tArrive.Rise, pCut->M[fPhase].tArrive.Fall, pCut->M[fPhase].AreaFlow, pRoot->Num ); + for ( i = 0; i < pCut->nLeaves; i++ ) + printf( " %d", pCut->ppLeaves[i]->Num ); + printf( " } \n" ); +} + + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutGetRootArea( Map_Cut_t * pCut, int fPhase ) +{ + assert( pCut->M[fPhase].pSuperBest ); + return pCut->M[fPhase].pSuperBest->Area; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +int Map_CutGetLeafPhase( Map_Cut_t * pCut, int fPhase, int iLeaf ) +{ + assert( pCut->M[fPhase].pSuperBest ); + return (( pCut->M[fPhase].uPhaseBest & (1<<iLeaf) ) == 0); +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +int Map_NodeGetLeafPhase( Map_Node_t * pNode, int fPhase, int iLeaf ) +{ + assert( pNode->pCutBest[fPhase]->M[fPhase].pSuperBest ); + return (( pNode->pCutBest[fPhase]->M[fPhase].uPhaseBest & (1<<iLeaf) ) == 0); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Cut_t * Map_CutListAppend( Map_Cut_t * pSetAll, Map_Cut_t * pSets ) +{ + Map_Cut_t * pPrev, * pTemp; + if ( pSetAll == NULL ) + return pSets; + if ( pSets == NULL ) + return pSetAll; + // find the last one + for ( pTemp = pSets; pTemp; pTemp = pTemp->pNext ) + pPrev = pTemp; + // append all the end of the current set + assert( pPrev->pNext == NULL ); + pPrev->pNext = pSetAll; + return pSets; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CutListRecycle( Map_Man_t * p, Map_Cut_t * pSetList, Map_Cut_t * pSave ) +{ + Map_Cut_t * pNext, * pTemp; + for ( pTemp = pSetList, pNext = pTemp? pTemp->pNext : NULL; + pTemp; + pTemp = pNext, pNext = pNext? pNext->pNext : NULL ) + if ( pTemp != pSave ) + Extra_MmFixedEntryRecycle( p->mmCuts, (char *)pTemp ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CutListCount( Map_Cut_t * pSets ) +{ + Map_Cut_t * pTemp; + int i; + for ( i = 0, pTemp = pSets; pTemp; pTemp = pTemp->pNext, i++ ); + return i; +} + +#if 0 + +/**function************************************************************* + + synopsis [Removes the fanouts of the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Map_CutRemoveFanouts( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase ) +{ + Map_NodeVec_t * vFanouts; + int i, k; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + vFanouts = pCut->ppLeaves[i]->vFanouts; + for ( k = 0; k < vFanouts->nSize; k++ ) + if ( vFanouts->pArray[k] == pNode ) + break; + assert( k != vFanouts->nSize ); + for ( k++; k < vFanouts->nSize; k++ ) + vFanouts->pArray[k-1] = vFanouts->pArray[k]; + vFanouts->nSize--; + } +} + +/**function************************************************************* + + synopsis [Removes the fanouts of the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +void Map_CutInsertFanouts( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase ) +{ + int i; + for ( i = 0; i < pCut->nLeaves; i++ ) + Map_NodeVecPush( pCut->ppLeaves[i]->vFanouts, pNode ); +} + +#endif + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperFanout.c b/src/map/mapper/mapperFanout.c new file mode 100644 index 00000000..7bd92ed9 --- /dev/null +++ b/src/map/mapper/mapperFanout.c @@ -0,0 +1,139 @@ +/**CFile**************************************************************** + + FileName [mapperFanout.c] + + PackageName [FRAIG: Functionally reduced AND-INV graphs.] + + Synopsis [Procedures to manipulate fanouts of the FRAIG nodes.] + + Author [Alan Mishchenko <alanmi@eecs.berkeley.edu>] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperFanout.c,v 1.5 2005/01/23 06:59:43 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + + +/**Function************************************************************* + + Synopsis [Add the fanout to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeAddFaninFanout( Map_Node_t * pFanin, Map_Node_t * pFanout ) +{ + Map_Node_t * pPivot; + + // pFanins is a fanin of pFanout + assert( !Map_IsComplement(pFanin) ); + assert( !Map_IsComplement(pFanout) ); + assert( Map_Regular(pFanout->p1) == pFanin || Map_Regular(pFanout->p2) == pFanin ); + + pPivot = pFanin->pFanPivot; + if ( pPivot == NULL ) + { + pFanin->pFanPivot = pFanout; + return; + } + + if ( Map_Regular(pPivot->p1) == pFanin ) + { + if ( Map_Regular(pFanout->p1) == pFanin ) + { + pFanout->pFanFanin1 = pPivot->pFanFanin1; + pPivot->pFanFanin1 = pFanout; + } + else // if ( Map_Regular(pFanout->p2) == pFanin ) + { + pFanout->pFanFanin2 = pPivot->pFanFanin1; + pPivot->pFanFanin1 = pFanout; + } + } + else // if ( Map_Regular(pPivot->p2) == pFanin ) + { + assert( Map_Regular(pPivot->p2) == pFanin ); + if ( Map_Regular(pFanout->p1) == pFanin ) + { + pFanout->pFanFanin1 = pPivot->pFanFanin2; + pPivot->pFanFanin2 = pFanout; + } + else // if ( Map_Regular(pFanout->p2) == pFanin ) + { + pFanout->pFanFanin2 = pPivot->pFanFanin2; + pPivot->pFanFanin2 = pFanout; + } + } +} + +/**Function************************************************************* + + Synopsis [Add the fanout to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeRemoveFaninFanout( Map_Node_t * pFanin, Map_Node_t * pFanoutToRemove ) +{ + Map_Node_t * pFanout, * pFanout2, ** ppFanList; + // start the linked list of fanouts + ppFanList = &pFanin->pFanPivot; + // go through the fanouts + Map_NodeForEachFanoutSafe( pFanin, pFanout, pFanout2 ) + { + // skip the fanout-to-remove + if ( pFanout == pFanoutToRemove ) + continue; + // add useful fanouts to the list + *ppFanList = pFanout; + ppFanList = Map_NodeReadNextFanoutPlace( pFanin, pFanout ); + } + *ppFanList = NULL; +} + +/**Function************************************************************* + + Synopsis [Returns the number of fanouts of a node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeGetFanoutNum( Map_Node_t * pNode ) +{ + Map_Node_t * pFanout; + int Counter = 0; + Map_NodeForEachFanout( pNode, pFanout ) + Counter++; + return Counter; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperGENERIC.c b/src/map/mapper/mapperGENERIC.c new file mode 100644 index 00000000..4df5ee51 --- /dev/null +++ b/src/map/mapper/mapperGENERIC.c @@ -0,0 +1,46 @@ +/**CFile**************************************************************** + + FileName [mapper__.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: mapper__.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperInt.h b/src/map/mapper/mapperInt.h new file mode 100644 index 00000000..c5ecce73 --- /dev/null +++ b/src/map/mapper/mapperInt.h @@ -0,0 +1,475 @@ +/**CFile**************************************************************** + + FileName [mapperInt.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperInt.h,v 1.8 2004/09/30 21:18:10 satrajit Exp $] + +***********************************************************************/ + +#ifndef __MAPPER_INT_H__ +#define __MAPPER_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +//#include "leaks.h" +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <float.h> +#include "cuddInt.h" +#include "main.h" +#include "mio.h" +#include "mapper.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +// the bit masks +#define MAP_MASK(n) ((~((unsigned)0)) >> (32-(n))) +#define MAP_FULL (~((unsigned)0)) +#define MAP_NO_VAR (-9999.0) + +// maximum/minimum operators +#define MAP_MIN(a,b) (((a) < (b))? (a) : (b)) +#define MAP_MAX(a,b) (((a) > (b))? (a) : (b)) + +// the small and large numbers (min/max float are 1.17e-38/3.40e+38) +#define MAP_FLOAT_LARGE ((float)(FLT_MAX/10)) +#define MAP_FLOAT_SMALL ((float)1.0e-03) + +// generating random unsigned (#define RAND_MAX 0x7fff) +#define MAP_RANDOM_UNSIGNED ((((unsigned)rand()) << 24) ^ (((unsigned)rand()) << 12) ^ ((unsigned)rand())) + +// internal macros to work with cuts +#define Map_CutIsComplement(p) (((int)((long) (p) & 01))) +#define Map_CutRegular(p) ((Map_Cut_t *)((unsigned)(p) & ~01)) +#define Map_CutNot(p) ((Map_Cut_t *)((long)(p) ^ 01)) +#define Map_CutNotCond(p,c) ((Map_Cut_t *)((long)(p) ^ (c))) + +// internal macros for referencing of nodes +#define Map_NodeReadRef(p) ((Map_Regular(p))->nRefs) +#define Map_NodeRef(p) ((Map_Regular(p))->nRefs++) + +// macros to get hold of the bits in the support info +#define Map_InfoSetVar(p,i) (p[(i)>>5] |= (1<<((i) & 31))) +#define Map_InfoRemVar(p,i) (p[(i)>>5] &= ~(1<<((i) & 31))) +#define Map_InfoFlipVar(p,i) (p[(i)>>5] ^= (1<<((i) & 31))) +#define Map_InfoReadVar(p,i) ((p[(i)>>5] & (1<<((i) & 31))) > 0) + +// returns the complemented attribute of the node +#define Map_NodeIsSimComplement(p) (Map_IsComplement(p)? !(Map_Regular(p)->fInv) : (p)->fInv) + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +// the mapping manager +struct Map_ManStruct_t_ +{ + // the mapping graph + Map_Node_t ** pBins; // the table of nodes hashed by their children + int nBins; // the size of the table + Map_Node_t ** pInputs; // the array of inputs + int nInputs; // the number of inputs + Map_Node_t ** pOutputs; // the array of outputs + int nOutputs; // the number of outputs + int nNodes; // the total number of nodes + Map_Node_t * pConst1; // the constant 1 node + Map_NodeVec_t * vAnds; // the array of nodes in the DFS order + Map_NodeVec_t * vNodesAll; // the array of all nodes + Map_NodeVec_t * vNodesTemp; // the array of all nodes + Map_NodeVec_t * vMapping; // the array of internal nodes used in the mapping + + // info about the original circuit + char ** ppOutputNames; // the primary output names + Map_Time_t * pInputArrivals;// the PI arrival times + + // mapping parameters + int nVarsMax; // the max number of variables + int fAreaRecovery; // the flag to enable area recovery + int fVerbose; // the verbosiness flag + int fMappingMode; // set to 1 when doing area + float fRequiredGlo; // the global required times + float fEpsilon; // the epsilon used to compare floats + float AreaBase; // the area after delay-oriented mapping + float AreaFinal; // the area after delay-oriented mapping + int nIterations; // How many matching passes to do + bool fObeyFanoutLimits;// Should mapper try to obey fanout limits or not + float DelayTarget; // the required times set by the user + int nTravIds; // the traversal counter + + // the supergate library + Map_SuperLib_t * pSuperLib; // the current supergate library + unsigned uTruths[6][2]; // the elementary truth tables + unsigned uTruthsLarge[10][32]; // the elementary truth tables + int nCounts[32]; // the counter of minterms + int nCountsBest[32];// the counter of minterms + + // simulation info from the FRAIG manager + int nSimRounds; // the number of words in the simulation info + unsigned ** pSimInfo; // the simulation info for each PI + + // don't-care computation + Map_NodeVec_t * vInside; // the array of nodes for SDC computation + Map_NodeVec_t * vFanins; // the array of nodes for SDC computation + + // the memory managers + Extra_MmFixed_t * mmNodes; // the memory manager for nodes + Extra_MmFixed_t * mmCuts; // the memory manager for cuts + + // various statistical variables + int nChoiceNodes; // the number of choice nodes + int nChoices; // the number of all choices + int nCanons; // the number of times N-canonical form was computed + int nMatches; // the number of times supergate matching was performed + int nPhases; // the number of phases considered during matching + int nFanoutViolations; // the number of nodes in mapped circuit violating fanout + + // runtime statistics + int timeToMap; // time to transfer to the mapping structure + int timeCuts; // time to compute k-feasible cuts + int timeTruth; // time to compute the truth table for each cut + int timeMatch; // time to perform matching for each node + int timeArea; // time to recover area after delay oriented mapping + int timeSweep; // time to perform technology dependent sweep + int timeToNet; // time to transfer back to the network + int timeTotal; // the total mapping time + int time1; // time to transfer to the mapping structure + int time2; // time to transfer to the mapping structure + int time3; // time to transfer to the mapping structure +}; + +// the supergate library +struct Map_SuperLibStruct_t_ +{ + // general info + char * pName; // the name of the supergate library + Mio_Library_t * pGenlib; // the generic library + + // other info + int nVarsMax; // the max number of variables + int nSupersAll; // the total number of supergates + int nSupersReal; // the total number of supergates + int nLines; // the total number of lines in the supergate file + bool fVerbose; // the verbosity flag + + // hash tables + Map_Super_t ** ppSupers; // the array of supergates + Map_HashTable_t * tTableC; // the table mapping N-canonical forms into supergates + Map_HashTable_t * tTable; // the table mapping truth tables into supergates + + // data structures for N-canonical form computation + unsigned uTruths[6][2]; // the elementary truth tables + unsigned uMask[2]; // the mask for the truth table + + // the invertor + Mio_Gate_t * pGateInv; // the pointer to the intertor gate + Map_Time_t tDelayInv; // the delay of the inverter + float AreaInv; // the area of the inverter + Map_Super_t * pSuperInv; // the supergate representing the inverter + + // the memory manager for the internal table + Extra_MmFixed_t * mmSupers; // the mamory manager for supergates + Extra_MmFixed_t * mmEntries; // the memory manager for the entries + Extra_MmFlex_t * mmForms; // the memory manager for formulas +}; + +// the mapping node +struct Map_NodeStruct_t_ +{ + // general information about the node + Map_Man_t * p; // the mapping manager + Map_Node_t * pNext; // the next node in the hash table + int Num; // the unique number of this node + int TravId; // the traversal ID (use to avoid cleaning marks) + int nRefs; // the number of references (fanouts) of the given node + unsigned fMark0 : 1; // the mark used for traversals + unsigned fMark1 : 1; // the mark used for traversals + unsigned fUsed : 1; // the mark to mark the node or its fanins + unsigned fInv : 1; // the complemented attribute for the equivalent nodes + unsigned fInvert: 1; // the flag to denote the use of interter + unsigned Level :16; // the level of the given node + unsigned NumTemp:10; // the level of the given node + int nRefAct[3]; // estimated fanout for current covering phase, neg and pos and sum + float nRefEst[3]; // actual fanout for previous covering phase, neg and pos and sum + + // the successors of this node + Map_Node_t * p1; // the first child + Map_Node_t * p2; // the second child + Map_Node_t * pNextE; // the next functionally equivalent node + Map_Node_t * pRepr; // the representative of the functionally equivalent class +// Map_NodeVec_t * vFanouts; // the array of fanouts of the node + + // representation of node's fanouts + Map_Node_t * pFanPivot; // the first fanout of this node + Map_Node_t * pFanFanin1; // the next fanout of p1 + Map_Node_t * pFanFanin2; // the next fanout of p2 + + unsigned * pSims; // the simulation info + float SwitchProb; // the switching probability + + // the delay information + Map_Time_t tArrival[2]; // the best arrival time of the neg (0) and pos (1) phases + Map_Time_t tRequired[2]; // the required time of the neg (0) and pos (1) phases + + // misc information + Map_Cut_t * pCutOld[2]; // the old mapping for neg and pos phase + Map_Cut_t * pCutBest[2]; // the best mapping for neg and pos phase + Map_Cut_t * pCuts; // mapping choices for the node (elementary comes first) + char * pData0; // temporary storage for the corresponding network node + char * pData1; // temporary storage for the corresponding network node +}; + +// the match of the cut +struct Map_MatchStruct_t_ +{ + // information used for matching + Map_Super_t * pSupers; + unsigned uPhase; + // information about the best selected match + unsigned uPhaseBest; // the best phase (the EXOR of match's phase and gate's phase) + Map_Super_t * pSuperBest; // the best supergate matched + // the parameters of the match + Map_Time_t tArrive; // the arrival time of this match + float AreaFlow; // the area flow or area of this match +}; + +// the cuts used for matching +struct Map_CutStruct_t_ +{ + Map_Cut_t * pNext; // the pointer to the next cut in the list + Map_Cut_t * pOne; // the father of this cut + Map_Cut_t * pTwo; // the mother of this cut + Map_Node_t * ppLeaves[6]; // the leaves of this cut + char nLeaves; // the number of leaves + char nVolume; // the volume of this cut + char fMark; // the mark to denote visited cut + char Phase; // the mark to denote complemented cut +// float fLevel; // the average level of the fanins + + unsigned uTruthTemp[2]; // the temporary truth table used to derive other cuts + unsigned uTruthZero[2]; // the temporary truth table used to derive other cuts + unsigned uTruthDc[2]; // the don't-cares (SDCs) computed for this cut + + Map_Match_t M[2]; // the matches for the positive/negative phase +}; + +// the supergate internally represented +struct Map_SuperStruct_t_ +{ + int Num; // the ID of the supergate + unsigned fSuper : 1; // the flag to distinquish a real super from a fake one + unsigned fExclude: 1; // the flag if set causes gate to be excluded from being used for mapping + unsigned nFanins : 3; // the number of inputs + unsigned nGates : 3; // the number of gates inside this supergate + unsigned nFanLimit: 4; // the max number of fanout count + unsigned nSupers : 16; // the number of supergates in the list + unsigned nPhases : 4; // the number of phases for matching with canonical form + unsigned char uPhases[4]; // the maximum of 4 phases for matching with canonical form + int nUsed; // the number of times the supergate is used + Map_Super_t * pFanins[6]; // the fanins of the gate + Mio_Gate_t * pRoot; // the root gate + unsigned uTruth[2]; // the truth table + Map_Time_t tDelaysR[6]; // the pin-to-pin delay constraints for the rise of the output + Map_Time_t tDelaysF[6]; // the pin-to-pin delay constraints for the rise of the output + Map_Time_t tDelayMax; // the maximum delay + float Area; // the area + char * pFormula; // the symbolic formula + Map_Super_t * pNext; // the pointer to the next super in the list +}; + +// the vector of nodes +struct Map_NodeVecStruct_t_ +{ + Map_Node_t ** pArray; // the array of nodes + int nSize; // the number of entries in the array + int nCap; // the number of allocated entries +}; + +// the hash table +struct Map_HashTableStruct_t_ +{ + Map_HashEntry_t ** pBins; // the table bins + int nBins; // the size of the table + int nEntries; // the total number of entries in the table + Extra_MmFixed_t * mmMan; // the memory manager for entries +}; + +// the entry in the hash table +struct Map_HashEntryStruct_t_ +{ + unsigned uTruth[2]; // the truth table for 6-var function + unsigned uPhase; // the phase to tranform it into the canonical form + Map_Super_t * pGates; // the linked list of matching supergates + Map_HashEntry_t * pNext; // the next entry in the hash table +}; + +// getting hold of the next fanout of the node +#define Map_NodeReadNextFanout( pNode, pFanout ) \ + ( ( pFanout == NULL )? NULL : \ + ((Map_Regular((pFanout)->p1) == (pNode))? \ + (pFanout)->pFanFanin1 : (pFanout)->pFanFanin2) ) + +// getting hold of the place where the next fanout will be attached +#define Map_NodeReadNextFanoutPlace( pNode, pFanout ) \ + ( (Map_Regular((pFanout)->p1) == (pNode))? \ + &(pFanout)->pFanFanin1 : &(pFanout)->pFanFanin2 ) + +// iterator through the fanouts of the node +#define Map_NodeForEachFanout( pNode, pFanout ) \ + for ( pFanout = (pNode)->pFanPivot; pFanout; \ + pFanout = Map_NodeReadNextFanout(pNode, pFanout) ) + +// safe iterator through the fanouts of the node +#define Map_NodeForEachFanoutSafe( pNode, pFanout, pFanout2 ) \ + for ( pFanout = (pNode)->pFanPivot, \ + pFanout2 = Map_NodeReadNextFanout(pNode, pFanout); \ + pFanout; \ + pFanout = pFanout2, \ + pFanout2 = Map_NodeReadNextFanout(pNode, pFanout) ) + +//////////////////////////////////////////////////////////////////////// +/// GLOBAL VARIABLES /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*=== mapperCanon.c =============================================================*/ +/*=== mapperCut.c ===============================================================*/ +extern void Map_MappingCuts( Map_Man_t * p ); +extern int Map_MappingCountAllCuts( Map_Man_t * p ); +/*=== mapperCutDcs.c ===============================================================*/ +extern void Map_ComputeDcs( Map_Man_t * p ); +extern unsigned Map_ComputeIsop_rec( Map_Man_t * p, unsigned uF, unsigned uFD, int iVar, int nVars, int fDir ); +/*=== mapperCutUtils.c ===============================================================*/ +extern Map_Cut_t * Map_CutAlloc( Map_Man_t * p ); +extern void Map_CutFree( Map_Man_t * p, Map_Cut_t * pCut ); +extern void Map_CutPrint( Map_Man_t * p, Map_Node_t * pRoot, Map_Cut_t * pCut, int fPhase ); +extern float Map_CutGetRootArea( Map_Cut_t * pCut, int fPhase ); +extern int Map_CutGetLeafPhase( Map_Cut_t * pCut, int fPhase, int iLeaf ); +extern int Map_NodeGetLeafPhase( Map_Node_t * pNode, int fPhase, int iLeaf ); +extern Map_Cut_t * Map_CutListAppend( Map_Cut_t * pSetAll, Map_Cut_t * pSets ); +extern void Map_CutListRecycle( Map_Man_t * p, Map_Cut_t * pSetList, Map_Cut_t * pSave ); +extern int Map_CutListCount( Map_Cut_t * pSets ); +extern void Map_CutRemoveFanouts( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase ); +extern void Map_CutInsertFanouts( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase ); +/*=== mapperFanout.c =============================================================*/ +extern void Map_NodeAddFaninFanout( Map_Node_t * pFanin, Map_Node_t * pFanout ); +extern void Map_NodeRemoveFaninFanout( Map_Node_t * pFanin, Map_Node_t * pFanoutToRemove ); +extern int Map_NodeGetFanoutNum( Map_Node_t * pNode ); +/*=== mapperLib.c ============================================================*/ +extern Map_SuperLib_t * Map_SuperLibCreate( char * pFileName, char * pExcludeFile, bool fAlgorithm, bool fVerbose ); +extern void Map_SuperLibFree( Map_SuperLib_t * p ); +/*=== mapperMatch.c ===============================================================*/ +extern int Map_MappingMatches( Map_Man_t * p ); +extern float Map_MappingCombinePhases( Map_Man_t * p ); +extern void Map_MatchClean( Map_Match_t * pMatch ); +extern int Map_MatchCompare( Map_Man_t * pMan, Map_Match_t * pM1, Map_Match_t * pM2, int fDoingArea ); +/*=== mapperRefs.c =============================================================*/ +extern int Map_NodeReadRefPhaseAct( Map_Node_t * pNode, int fPhase ); +extern float Map_NodeReadRefPhaseEst( Map_Node_t * pNode, int fPhase ); +extern void Map_MappingEstimateRefsInit( Map_Man_t * p ); +extern void Map_MappingEstimateRefs( Map_Man_t * p ); +extern float Map_CutGetAreaFlow( Map_Cut_t * pCut, int fPhase ); +extern float Map_CutGetAreaRefed( Map_Cut_t * pCut, int fPhase ); +extern float Map_CutGetAreaDerefed( Map_Cut_t * pCut, int fPhase ); +extern float Map_CutRef( Map_Cut_t * pCut, int fPhase ); +extern float Map_CutDeref( Map_Cut_t * pCut, int fPhase ); +extern void Map_MappingSetRefs( Map_Man_t * pMan ); +extern float Map_MappingGetArea( Map_Man_t * pMan, Map_NodeVec_t * vMapping ); +/*=== mapperShow.c =============================================================*/ +extern void Map_MappingShow( Map_Man_t * pMan, char * pFileName ); +/*=== mapperTree.c ===============================================================*/ +extern int Map_LibraryReadTree( Map_SuperLib_t * pLib, char * pFileName, char * pExcludeFile ); +extern void Map_LibraryPrintTree( Map_SuperLib_t * pLib ); +/*=== mapperSuper.c ===============================================================*/ +extern int Map_LibraryRead( Map_SuperLib_t * p, char * pFileName ); +extern void Map_LibraryPrintSupergate( Map_Super_t * pGate ); +/*=== mapperTable.c ============================================================*/ +extern Map_HashTable_t * Map_SuperTableCreate( Map_SuperLib_t * pLib ); +extern void Map_SuperTableFree( Map_HashTable_t * p ); +extern int Map_SuperTableInsertC( Map_HashTable_t * pLib, unsigned uTruthC[], Map_Super_t * pGate ); +extern int Map_SuperTableInsert( Map_HashTable_t * pLib, unsigned uTruth[], Map_Super_t * pGate, unsigned uPhase ); +extern Map_Super_t * Map_SuperTableLookup( Map_HashTable_t * p, unsigned uTruth[], unsigned * puPhase ); +extern void Map_SuperTableSortSupergates( Map_HashTable_t * p, int nSupersMax ); +extern void Map_SuperTableSortSupergatesByDelay( Map_HashTable_t * p, int nSupersMax ); +/*=== mapperTime.c =============================================================*/ +extern float Map_TimeCutComputeArrival( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float tWorstCaseLimit ); +extern void Map_TimeCutComputeArrival_rec( Map_Cut_t * pCut, int fPhase ); +extern float Map_TimeComputeArrivalMax( Map_Man_t * p ); +extern void Map_TimeComputeRequiredGlobal( Map_Man_t * p ); +extern void Map_TimeComputeRequired( Map_Man_t * p, float fRequired ); +extern float Map_TimeNodeFanoutDelay( Map_Node_t * pNode, int fPhase ); +extern float Map_TimeCutFanoutDelay( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase ); +extern float Map_TimeMatchWithInverter( Map_Man_t * p, Map_Match_t * pMatch ); +/*=== mapperTruth.c ===============================================================*/ +extern void Map_MappingTruths( Map_Man_t * pMan ); +extern int Map_TruthsCutDontCare( Map_Man_t * pMan, Map_Cut_t * pCut, unsigned * uTruthDc ); +extern int Map_TruthCountOnes( unsigned * uTruth, int nLeaves ); +extern int Map_TruthDetectTwoFirst( unsigned * uTruth, int nLeaves ); +/*=== mapperUtils.c ===============================================================*/ +extern Map_NodeVec_t * Map_MappingDfs( Map_Man_t * pMan, int fCollectEquiv ); +extern Map_NodeVec_t * Map_MappingDfsNodes( Map_Man_t * pMan, Map_Node_t ** ppNodes, int nNodes, int fEquiv ); + +extern void Map_MappingDfsMarked1_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fFirst ); +extern void Map_MappingDfsMarked2_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, Map_NodeVec_t * vBoundary, int fFirst ); + +extern int Map_MappingCountLevels( Map_Man_t * pMan ); +extern void Map_MappingUnmark( Map_Man_t * pMan ); +extern void Map_MappingMark_rec( Map_Node_t * pNode ); +extern void Map_MappingUnmark_rec( Map_Node_t * pNode ); +extern void Map_MappingPrintOutputArrivals( Map_Man_t * p ); +extern void Map_MappingSetupMask( unsigned uMask[], int nVarsMax ); +extern int Map_MappingNodeIsViolator( Map_Node_t * pNode, Map_Cut_t * pCut, int fPosPol ); +extern float Map_MappingGetAreaFlow( Map_Man_t * p ); +extern void Map_MappingSortByLevel( Map_Man_t * pMan, Map_NodeVec_t * vNodes ); +extern int Map_MappingCountDoubles( Map_Man_t * pMan, Map_NodeVec_t * vNodes ); +extern void Map_MappingExpandTruth( unsigned uTruth[2], int nVars ); +extern float Map_MappingPrintSwitching( Map_Man_t * pMan ); +extern void Map_MappingSetPlacementInfo( Map_Man_t * p ); +extern float Map_MappingPrintWirelength( Map_Man_t * p ); +extern void Map_MappingWireReport( Map_Man_t * p ); +extern float Map_MappingComputeDelayWithFanouts( Map_Man_t * p ); +extern int Map_MappingGetMaxLevel( Map_Man_t * pMan ); +extern void Map_MappingSetChoiceLevels( Map_Man_t * pMan ); +extern void Map_MappingReportChoices( Map_Man_t * pMan ); +/*=== mapperVec.c =============================================================*/ +extern Map_NodeVec_t * Map_NodeVecAlloc( int nCap ); +extern void Map_NodeVecFree( Map_NodeVec_t * p ); +extern Map_Node_t ** Map_NodeVecReadArray( Map_NodeVec_t * p ); +extern int Map_NodeVecReadSize( Map_NodeVec_t * p ); +extern void Map_NodeVecGrow( Map_NodeVec_t * p, int nCapMin ); +extern void Map_NodeVecShrink( Map_NodeVec_t * p, int nSizeNew ); +extern void Map_NodeVecClear( Map_NodeVec_t * p ); +extern void Map_NodeVecPush( Map_NodeVec_t * p, Map_Node_t * Entry ); +extern int Map_NodeVecPushUnique( Map_NodeVec_t * p, Map_Node_t * Entry ); +extern Map_Node_t * Map_NodeVecPop( Map_NodeVec_t * p ); +extern void Map_NodeVecRemove( Map_NodeVec_t * p, Map_Node_t * Entry ); +extern void Map_NodeVecWriteEntry( Map_NodeVec_t * p, int i, Map_Node_t * Entry ); +extern Map_Node_t * Map_NodeVecReadEntry( Map_NodeVec_t * p, int i ); +extern void Map_NodeVecSortByLevel( Map_NodeVec_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif diff --git a/src/map/mapper/mapperLib.c b/src/map/mapper/mapperLib.c new file mode 100644 index 00000000..5530f8cb --- /dev/null +++ b/src/map/mapper/mapperLib.c @@ -0,0 +1,233 @@ +/**CFile**************************************************************** + + FileName [mapperLib.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperLib.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads in the supergate library and prepares it for use.] + + Description [The supergates library comes in a .super file. This file + contains descriptions of supergates along with some relevant information. + This procedure reads the supergate file, canonicizes the supergates, + and constructs an additional lookup table, which can be used to map + truth tables of the cuts into the pair (phase, supergate). The phase + indicates how the current truth table should be phase assigned to + match the canonical form of the supergate. The resulting phase is the + bitwise EXOR of the phase needed to canonicize the supergate and the + phase needed to transform the truth table into its canonical form.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_SuperLib_t * Map_SuperLibCreate( char * pFileName, char * pExcludeFile, bool fAlgorithm, bool fVerbose ) +{ + Map_SuperLib_t * p; + int clk; + + // start the supergate library + p = ALLOC( Map_SuperLib_t, 1 ); + memset( p, 0, sizeof(Map_SuperLib_t) ); + p->pName = pFileName; + p->fVerbose = fVerbose; + p->mmSupers = Extra_MmFixedStart( sizeof(Map_Super_t) ); + p->mmEntries = Extra_MmFixedStart( sizeof(Map_HashEntry_t) ); + p->mmForms = Extra_MmFlexStart(); + Map_MappingSetupTruthTables( p->uTruths ); + + // start the hash table + p->tTableC = Map_SuperTableCreate( p ); + p->tTable = Map_SuperTableCreate( p ); + + // read the supergate library from file +clk = clock(); + if ( fAlgorithm ) + { + if ( !Map_LibraryReadTree( p, pFileName, pExcludeFile ) ) + { + Map_SuperLibFree( p ); + return NULL; + } + } + else + { + if ( pExcludeFile != 0 ) + { + printf ("Error: Exclude file support not present for old format. Stop.\n"); + return NULL; + } + if ( !Map_LibraryRead( p, pFileName ) ) + { + Map_SuperLibFree( p ); + return NULL; + } + } + assert( p->nVarsMax > 0 ); + + // report the stats +if ( fVerbose ) { + printf( "Loaded %d unique %d-input supergates from \"%s\". ", + p->nSupersReal, p->nVarsMax, pFileName ); + PRT( "Time", clock() - clk ); +} + + // assign the interver parameters + p->pGateInv = Mio_LibraryReadInv( p->pGenlib ); + p->tDelayInv.Rise = Mio_LibraryReadDelayInvRise( p->pGenlib ); + p->tDelayInv.Fall = Mio_LibraryReadDelayInvFall( p->pGenlib ); + p->tDelayInv.Worst = MAP_MAX( p->tDelayInv.Rise, p->tDelayInv.Fall ); + p->AreaInv = Mio_LibraryReadAreaInv( p->pGenlib ); + + // assign the interver supergate + p->pSuperInv = (Map_Super_t *)Extra_MmFixedEntryFetch( p->mmSupers ); + memset( p->pSuperInv, 0, sizeof(Map_Super_t) ); + p->pSuperInv->Num = -1; + p->pSuperInv->nGates = 1; + p->pSuperInv->nFanins = 1; + p->pSuperInv->nFanLimit = 10; + p->pSuperInv->pFanins[0] = p->ppSupers[0]; + p->pSuperInv->pRoot = p->pGateInv; + p->pSuperInv->Area = p->AreaInv; + p->pSuperInv->tDelayMax = p->tDelayInv; + p->pSuperInv->tDelaysR[0].Rise = MAP_NO_VAR; + p->pSuperInv->tDelaysR[0].Fall = p->tDelayInv.Rise; + p->pSuperInv->tDelaysF[0].Rise = p->tDelayInv.Fall; + p->pSuperInv->tDelaysF[0].Fall = MAP_NO_VAR; + return p; +} + + +/**Function************************************************************* + + Synopsis [Deallocates the supergate library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_SuperLibFree( Map_SuperLib_t * p ) +{ + if ( p == NULL ) return; + if ( p->pGenlib ) + { +// if ( s_pLib == p->pGenlib ) +// s_pLib = NULL; + if ( Abc_FrameReadLibGen(Abc_FrameGetGlobalFrame()) == p->pGenlib ) + Abc_FrameSetLibGen(Abc_FrameGetGlobalFrame(), NULL); +// Mio_LibraryDelete( p->pGenlib ); + Mio_LibraryDelete( p->pGenlib ); + } + if ( p->tTableC ) + Map_SuperTableFree( p->tTableC ); + if ( p->tTable ) + Map_SuperTableFree( p->tTable ); + Extra_MmFixedStop( p->mmSupers, 0 ); + Extra_MmFixedStop( p->mmEntries, 0 ); + Extra_MmFlexStop( p->mmForms, 0 ); + FREE( p->ppSupers ); + FREE( p ); +} + +/**Function************************************************************* + + Synopsis [Derives the library from the genlib library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_SuperLibDeriveFromGenlib( Mio_Library_t * pLib ) +{ + Abc_Frame_t * pAbc = Abc_FrameGetGlobalFrame(); + char * pNameGeneric; + char FileNameGenlib[100]; + char FileNameSuper[100]; + char CommandSuper[500]; + char CommandRead[500]; + FILE * pFile; + + if ( pLib == NULL ) + return 0; + + // write the current library into the file + strcpy( FileNameGenlib, Mio_LibraryReadName(pLib) ); + pFile = fopen( FileNameGenlib, "w" ); + Mio_WriteLibrary( pFile, pLib, 0 ); + fclose( pFile ); + + // get the file name with the library + pNameGeneric = Extra_FileNameGeneric( Mio_LibraryReadName(pLib) ); + sprintf( FileNameSuper, "%s.super", pNameGeneric ); + free( pNameGeneric ); + + sprintf( CommandSuper, "super -l 1 -i 5 -d 10000000 -a 10000000 -t 100 %s", FileNameGenlib ); + if ( Cmd_CommandExecute( pAbc, CommandSuper ) ) + { + fprintf( stdout, "Cannot execute command \"%s\".\n", CommandSuper ); + return 0; + } +//#ifdef WIN32 +// _unlink( FileNameGenlib ); +//#else +// unlink( FileNameGenlib ); +//#endif + + sprintf( CommandRead, "read_super %s", FileNameSuper ); + if ( Cmd_CommandExecute( pAbc, CommandRead ) ) + { +#ifdef WIN32 + _unlink( FileNameSuper ); +#else + unlink( FileNameSuper ); +#endif + fprintf( stdout, "Cannot execute command \"%s\".\n", CommandRead ); + return 0; + } + +/* // don't remove the intermediate file +#ifdef WIN32 + _unlink( FileNameSuper ); +#else + unlink( FileNameSuper ); +#endif +*/ + return 1; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperMatch.c b/src/map/mapper/mapperMatch.c new file mode 100644 index 00000000..5b72311c --- /dev/null +++ b/src/map/mapper/mapperMatch.c @@ -0,0 +1,578 @@ +/**CFile**************************************************************** + + FileName [mapperMatch.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperMatch.c,v 1.7 2004/09/30 21:18:10 satrajit Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +/* + A potential improvement: + When an internal node is not used in the mapping, its required times + are set to be +infinity. So when we recover area, we try to find the + best match for area and completely disregard the delay for the nodes + that are not currently used in the mapping because any match whose + arrival times are less than the required times (+infinity) can be used. + It may be possible to develop a better approach to recover area for + the nodes that are not currently used in the mapping... +*/ + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_MatchNodePhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ); +static int Map_MatchNodeCut( Map_Man_t * p, Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float fWorstLimit ); + +static void Map_MappingSetPiArrivalTimes( Map_Man_t * p ); +static void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode ); +static void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes the best matches of the nodes.] + + Description [Uses parameter p->fMappingMode to decide how to assign + the matches for both polarities of the node. While the matches are + being assigned, one of them may turn out to be better than the other + (in terms of delay, for example). In this case, the worse match can + be permanently dropped, and the corresponding pointer set to NULL.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingMatches( Map_Man_t * p ) +{ + ProgressBar * pProgress; + Map_Node_t * pNode; + int i; + + assert( p->fMappingMode >= 0 && p->fMappingMode <= 3 ); + + // use the externally given PI arrival times + if ( p->fMappingMode == 0 ) + Map_MappingSetPiArrivalTimes( p ); + + // estimate the fanouts + if ( p->fMappingMode == 0 ) + Map_MappingEstimateRefsInit( p ); + else if ( p->fMappingMode == 1 ) + Map_MappingEstimateRefs( p ); + + // the PI cuts are matched in the cut computation package + // in the loop below we match the internal nodes + pProgress = Extra_ProgressBarStart( stdout, p->vAnds->nSize ); + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + // skip primary inputs and secondary nodes if mapping with choices + pNode = p->vAnds->pArray[i]; + if ( !Map_NodeIsAnd( pNode ) || pNode->pRepr ) + continue; + + // make sure that at least one non-trival cut is present + if ( pNode->pCuts->pNext == NULL ) + { + printf( "\nError: A node in the mapping graph does not have feasible cuts.\n" ); + return 0; + } + + // match negative phase + if ( !Map_MatchNodePhase( p, pNode, 0 ) ) + return 0; + // match positive phase + if ( !Map_MatchNodePhase( p, pNode, 1 ) ) + return 0; + + // make sure that at least one phase is mapped + if ( pNode->pCutBest[0] == NULL && pNode->pCutBest[1] == NULL ) + { + printf( "\nError: Could not match both phases of AIG node %d.\n", pNode->Num ); + printf( "Please make sure that the supergate library has equivalents of AND2 or NAND2.\n" ); + printf( "If such supergates exist in the library, report a bug.\n" ); + return 0; + } + + // if both phases are assigned, check if one of them can be dropped + Map_NodeTryDroppingOnePhase( p, pNode ); + // set the arrival times of the node using the best cuts + Map_NodeTransferArrivalTimes( p, pNode ); + + // update the progress bar + Extra_ProgressBarUpdate( pProgress, i, "Matches ..." ); + } + Extra_ProgressBarStop( pProgress ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Find the matching of one polarity of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchNodePhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ) +{ + Map_Match_t MatchBest, * pMatch; + Map_Cut_t * pCut, * pCutBest; + float Area1, Area2, fWorstLimit; + + // skip the cuts that have been unassigned during area recovery + pCutBest = pNode->pCutBest[fPhase]; + if ( p->fMappingMode != 0 && pCutBest == NULL ) + return 1; + + // recompute the arrival times of the current best match + // because the arrival times of the fanins may have changed + // as a result of remapping fanins in the topological order + if ( p->fMappingMode != 0 ) + { + Map_TimeCutComputeArrival( pNode, pCutBest, fPhase, MAP_FLOAT_LARGE ); + // make sure that the required times are met + assert( pCutBest->M[fPhase].tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon ); + assert( pCutBest->M[fPhase].tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon ); + } + + // recompute the exact area of the current best match + // because the exact area of the fanins may have changed + // as a result of remapping fanins in the topological order + if ( p->fMappingMode >= 2 ) + { + pMatch = pCutBest->M + fPhase; + if ( pNode->nRefAct[fPhase] > 0 || + (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0) ) + pMatch->AreaFlow = Area1 = Map_CutDeref( pCutBest, fPhase ); + else + pMatch->AreaFlow = Area1 = Map_CutGetAreaDerefed( pCutBest, fPhase ); + } + + // save the old mapping + if ( pCutBest ) + MatchBest = pCutBest->M[fPhase]; + else + Map_MatchClean( &MatchBest ); + + // select the new best cut + fWorstLimit = pNode->tRequired[fPhase].Worst; + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + { + pMatch = pCut->M + fPhase; + if ( pMatch->pSupers == NULL ) + continue; + + // find the matches for the cut + Map_MatchNodeCut( p, pNode, pCut, fPhase, fWorstLimit ); + if ( pMatch->pSuperBest == NULL || pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + + // if the cut can be matched compare the matchings + if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) ) + { + pCutBest = pCut; + MatchBest = *pMatch; + // if we are mapping for delay, the worst-case limit should be tightened + if ( p->fMappingMode == 0 ) + fWorstLimit = MatchBest.tArrive.Worst; + } + } + + if ( pCutBest == NULL ) + return 1; + + // set the new mapping + pNode->pCutBest[fPhase] = pCutBest; + pCutBest->M[fPhase] = MatchBest; + + // reference the new cut if it used + if ( p->fMappingMode >= 2 && + (pNode->nRefAct[fPhase] > 0 || + (pNode->pCutBest[!fPhase] == NULL && pNode->nRefAct[!fPhase] > 0)) ) + { + Area2 = Map_CutRef( pNode->pCutBest[fPhase], fPhase ); + assert( Area2 < Area1 + p->fEpsilon ); + } + + // make sure that the requited times are met + assert( MatchBest.tArrive.Rise < pNode->tRequired[fPhase].Rise + p->fEpsilon ); + assert( MatchBest.tArrive.Fall < pNode->tRequired[fPhase].Fall + p->fEpsilon ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Find the best matching of the cut.] + + Description [The parameters: the node (pNode), the cut (pCut), the phase to be matched + (fPhase), and the upper bound on the arrival times of the cut (fWorstLimit). This + procedure goes through the matching supergates up to the phase assignment, and selects the + best supergate, which will be used to map the cut. As a result of calling this procedure + the matching information is written into pMatch.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchNodeCut( Map_Man_t * p, Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float fWorstLimit ) +{ + Map_Match_t MatchBest, * pMatch = pCut->M + fPhase; + Map_Super_t * pSuper; + int i, Counter; + + // save the current match of the cut + MatchBest = *pMatch; + // go through the supergates + for ( pSuper = pMatch->pSupers, Counter = 0; pSuper; pSuper = pSuper->pNext, Counter++ ) + { + p->nMatches++; + // this is an attempt to reduce the runtime of matching and area + // at the cost of rare and very minor increase in delay + // (the supergates are sorted by increasing area) + if ( Counter == 30 ) + break; + + // go through different phases of the given match and supergate + pMatch->pSuperBest = pSuper; + for ( i = 0; i < (int)pSuper->nPhases; i++ ) + { + p->nPhases++; + // find the overall phase of this match + pMatch->uPhaseBest = pMatch->uPhase ^ pSuper->uPhases[i]; + if ( p->fMappingMode == 0 ) + { + // get the arrival time + Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit ); + // skip the cut if the arrival times exceed the required times + if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + // get the area (area flow) + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + } + else + { + // get the area (area flow) + if ( p->fMappingMode >= 2 ) + pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase ); + else + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + // skip if the cut is too large + if ( pMatch->AreaFlow > MatchBest.AreaFlow + p->fEpsilon ) + continue; + // get the arrival time + Map_TimeCutComputeArrival( pNode, pCut, fPhase, fWorstLimit ); + // skip the cut if the arrival times exceed the required times + if ( pMatch->tArrive.Worst > fWorstLimit + p->fEpsilon ) + continue; + } + + // if the cut is non-trivial, compare it + if ( Map_MatchCompare( p, &MatchBest, pMatch, p->fMappingMode ) ) + { + MatchBest = *pMatch; + // if we are mapping for delay, the worst-case limit should be reduced + if ( p->fMappingMode == 0 ) + fWorstLimit = MatchBest.tArrive.Worst; + } + } + } + // set the best match + *pMatch = MatchBest; + + // recompute the arrival time and area (area flow) of this cut + if ( pMatch->pSuperBest ) + { + Map_TimeCutComputeArrival( pNode, pCut, fPhase, MAP_FLOAT_LARGE ); + if ( p->fMappingMode >= 2 ) + pMatch->AreaFlow = Map_CutGetAreaDerefed( pCut, fPhase ); + else + pMatch->AreaFlow = Map_CutGetAreaFlow( pCut, fPhase ); + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Cleans the match.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MatchClean( Map_Match_t * pMatch ) +{ + memset( pMatch, 0, sizeof(Map_Match_t) ); + pMatch->AreaFlow = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Rise = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Fall = MAP_FLOAT_LARGE; // unassigned + pMatch->tArrive.Worst = MAP_FLOAT_LARGE; // unassigned +} + +/**Function************************************************************* + + Synopsis [Compares two matches.] + + Description [Returns 1 if the second match is better. Otherwise returns 0.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MatchCompare( Map_Man_t * pMan, Map_Match_t * pM1, Map_Match_t * pM2, int fDoingArea ) +{ + if ( !fDoingArea ) + { + // compare the arrival times + if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon ) + return 0; + if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon ) + return 1; + // compare the areas or area flows + if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon ) + return 0; + if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon ) + return 1; + // compare the fanout limits + if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit ) + return 0; + if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit ) + return 1; + // compare the number of leaves + if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins ) + return 0; + if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins ) + return 1; + // otherwise prefer the old cut + return 0; + } + else + { + // compare the areas or area flows + if ( pM1->AreaFlow < pM2->AreaFlow - pMan->fEpsilon ) + return 0; + if ( pM1->AreaFlow > pM2->AreaFlow + pMan->fEpsilon ) + return 1; + // compare the arrival times + if ( pM1->tArrive.Worst < pM2->tArrive.Worst - pMan->fEpsilon ) + return 0; + if ( pM1->tArrive.Worst > pM2->tArrive.Worst + pMan->fEpsilon ) + return 1; + // compare the fanout limits + if ( pM1->pSuperBest->nFanLimit > pM2->pSuperBest->nFanLimit ) + return 0; + if ( pM1->pSuperBest->nFanLimit < pM2->pSuperBest->nFanLimit ) + return 1; + // compare the number of leaves + if ( pM1->pSuperBest->nFanins < pM2->pSuperBest->nFanins ) + return 0; + if ( pM1->pSuperBest->nFanins > pM2->pSuperBest->nFanins ) + return 1; + // otherwise prefer the old cut + return 0; + } +} + +/**Function************************************************************* + + Synopsis [Sets the PI arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetPiArrivalTimes( Map_Man_t * p ) +{ + Map_Node_t * pNode; + int i; + for ( i = 0; i < p->nInputs; i++ ) + { + pNode = p->pInputs[i]; + // set the arrival time of the positive phase + pNode->tArrival[1] = p->pInputArrivals[i]; + // set the arrival time of the negative phase + pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall); + } +} + + +/**Function************************************************************* + + Synopsis [Attempts dropping one phase of the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeTryDroppingOnePhase( Map_Man_t * p, Map_Node_t * pNode ) +{ + Map_Match_t * pMatchBest0, * pMatchBest1; + float tWorst0Using1, tWorst1Using0; + int fUsePhase1, fUsePhase0; + + // nothing to do if one of the phases is already dropped + if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL ) + return; + + // do not drop while recovering area flow + if ( p->fMappingMode == 1 )//|| p->fMappingMode == 2 ) + return; + + // get the pointers to the matches of the best cuts + pMatchBest0 = pNode->pCutBest[0]->M + 0; + pMatchBest1 = pNode->pCutBest[1]->M + 1; + + // get the worst arrival times of each phase + // implemented using the other phase with inverter added + tWorst0Using1 = Map_TimeMatchWithInverter( p, pMatchBest1 ); + tWorst1Using0 = Map_TimeMatchWithInverter( p, pMatchBest0 ); + + // consider the case of mapping for delay + if ( p->fMappingMode == 0 ) + { + // if the arrival time of a phase is larger than the arrival time + // of the opposite phase plus the inverter, drop this phase + if ( pMatchBest0->tArrive.Worst > tWorst0Using1 + p->fEpsilon ) + pNode->pCutBest[0] = NULL; + else if ( pMatchBest1->tArrive.Worst > tWorst1Using0 + p->fEpsilon ) + pNode->pCutBest[1] = NULL; + return; + } + + // do not perform replacement if one of the phases is unused + if ( pNode->nRefAct[0] == 0 || pNode->nRefAct[1] == 0 ) + return; + + // check if replacement of each phase is possible using required times + fUsePhase0 = fUsePhase1 = 0; + if ( p->fMappingMode == 2 ) + { + fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon); + fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + 3*p->pSuperLib->tDelayInv.Worst + p->fEpsilon); + } + else if ( p->fMappingMode == 3 ) + { + fUsePhase0 = (pNode->tRequired[1].Worst > tWorst1Using0 + p->fEpsilon); + fUsePhase1 = (pNode->tRequired[0].Worst > tWorst0Using1 + p->fEpsilon); + } + if ( !fUsePhase0 && !fUsePhase1 ) + return; + + // if replacement is possible both ways, use the one that works better + if ( fUsePhase0 && fUsePhase1 ) + { + if ( pMatchBest0->AreaFlow < pMatchBest1->AreaFlow ) + fUsePhase1 = 0; + else + fUsePhase0 = 0; + } + // only one phase should be used + assert( fUsePhase0 ^ fUsePhase1 ); + + // set the corresponding cut to NULL + if ( fUsePhase0 ) + { + // deref phase 1 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[1] > 0 ) + Map_CutDeref( pNode->pCutBest[1], 1 ); + // get rid of the cut + pNode->pCutBest[1] = NULL; + // ref phase 0 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[0] == 0 ) + Map_CutRef( pNode->pCutBest[0], 0 ); + } + else + { + // deref phase 0 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[0] > 0 ) + Map_CutDeref( pNode->pCutBest[0], 0 ); + // get rid of the cut + pNode->pCutBest[0] = NULL; + // ref phase 1 cut if necessary + if ( p->fMappingMode >= 2 && pNode->nRefAct[1] == 0 ) + Map_CutRef( pNode->pCutBest[1], 1 ); + } +} + + +/**Function************************************************************* + + Synopsis [Transfers the arrival times from the best cuts to the node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeTransferArrivalTimes( Map_Man_t * p, Map_Node_t * pNode ) +{ + // if both phases are available, set their arrival times + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) + { + pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive; + pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive; + } + // if only one phase is available, compute the arrival time of other phase + else if ( pNode->pCutBest[0] ) + { + pNode->tArrival[0] = pNode->pCutBest[0]->M[0].tArrive; + pNode->tArrival[1].Rise = pNode->tArrival[0].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[1].Fall = pNode->tArrival[0].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[1].Worst = MAP_MAX(pNode->tArrival[1].Rise, pNode->tArrival[1].Fall); + } + else if ( pNode->pCutBest[1] ) + { + pNode->tArrival[1] = pNode->pCutBest[1]->M[1].tArrive; + pNode->tArrival[0].Rise = pNode->tArrival[1].Fall + p->pSuperLib->tDelayInv.Rise; + pNode->tArrival[0].Fall = pNode->tArrival[1].Rise + p->pSuperLib->tDelayInv.Fall; + pNode->tArrival[0].Worst = MAP_MAX(pNode->tArrival[0].Rise, pNode->tArrival[0].Fall); + } + else + { + assert( 0 ); + } + + assert( pNode->tArrival[0].Rise < pNode->tRequired[0].Rise + p->fEpsilon ); + assert( pNode->tArrival[0].Fall < pNode->tRequired[0].Fall + p->fEpsilon ); + + assert( pNode->tArrival[1].Rise < pNode->tRequired[1].Rise + p->fEpsilon ); + assert( pNode->tArrival[1].Fall < pNode->tRequired[1].Fall + p->fEpsilon ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// diff --git a/src/map/mapper/mapperRefs.c b/src/map/mapper/mapperRefs.c new file mode 100644 index 00000000..334e98c7 --- /dev/null +++ b/src/map/mapper/mapperRefs.c @@ -0,0 +1,541 @@ +/**CFile**************************************************************** + + FileName [mapperRefs.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperRefs.h,v 1.0 2003/09/08 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_NodeIncRefPhaseAct( Map_Node_t * pNode, int fPhase ); +static int Map_NodeDecRefPhaseAct( Map_Node_t * pNode, int fPhase ); +static float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ); +static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads the actual reference counter of a phase.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeReadRefPhaseAct( Map_Node_t * pNode, int fPhase ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned + return pNode->nRefAct[fPhase]; + assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned + return pNode->nRefAct[2]; +} + +/**Function************************************************************* + + Synopsis [Reads the estimated reference counter of a phase.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_NodeReadRefPhaseEst( Map_Node_t * pNode, int fPhase ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned + return pNode->nRefEst[fPhase]; + assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned +// return pNode->nRefEst[0] + pNode->nRefEst[1]; + return pNode->nRefEst[2]; +} + + +/**Function************************************************************* + + Synopsis [Increments the actual reference counter of a phase.] + + Description [Returns the old reference counter.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeIncRefPhaseAct( Map_Node_t * pNode, int fPhase ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned + return pNode->nRefAct[fPhase]++; + assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned + return pNode->nRefAct[2]++; +} + +/**Function************************************************************* + + Synopsis [Decrements the actual reference counter of a phase.] + + Description [Returns the new reference counter.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeDecRefPhaseAct( Map_Node_t * pNode, int fPhase ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->pCutBest[0] && pNode->pCutBest[1] ) // both assigned + return --pNode->nRefAct[fPhase]; + assert( pNode->pCutBest[0] || pNode->pCutBest[1] ); // at least one assigned + return --pNode->nRefAct[2]; +} + + +/**Function************************************************************* + + Synopsis [Sets the estimated reference counter for the PIs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingEstimateRefsInit( Map_Man_t * p ) +{ + Map_Node_t * pNode; + int i; + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + pNode = p->vAnds->pArray[i]; +// pNode->nRefEst[0] = pNode->nRefEst[1] = ((float)pNode->nRefs)*(float)2.0; + pNode->nRefEst[0] = pNode->nRefEst[1] = pNode->nRefEst[2] = ((float)pNode->nRefs); + } +} + +/**Function************************************************************* + + Synopsis [Sets the estimated reference counter.] + + Description [When this procedure is called for the first time, + the reference counter is estimated from the AIG. Otherwise, it is + a linear combination of reference counters in the last two iterations.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingEstimateRefs( Map_Man_t * p ) +{ + Map_Node_t * pNode; + int i; + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + pNode = p->vAnds->pArray[i]; +// pNode->nRefEst[0] = (float)((2.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 3.0); +// pNode->nRefEst[1] = (float)((2.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 3.0); +// pNode->nRefEst[2] = (float)((2.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 3.0); + pNode->nRefEst[0] = (float)((3.0 * pNode->nRefEst[0] + 1.0 * pNode->nRefAct[0]) / 4.0); + pNode->nRefEst[1] = (float)((3.0 * pNode->nRefEst[1] + 1.0 * pNode->nRefAct[1]) / 4.0); + pNode->nRefEst[2] = (float)((3.0 * pNode->nRefEst[2] + 1.0 * pNode->nRefAct[2]) / 4.0); + } +} + + + + + +/**function************************************************************* + + synopsis [Computes the area flow of the cut.] + + description [Computes the area flow of the cut if it is implemented using + the best supergate with the best phase.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutGetAreaFlow( Map_Cut_t * pCut, int fPhase ) +{ + Map_Match_t * pM = pCut->M + fPhase; + Map_Super_t * pSuper = pM->pSuperBest; + unsigned uPhaseTot = pM->uPhaseBest; + Map_Cut_t * pCutFanin; + float aFlowRes, aFlowFanin, nRefs; + int i, fPinPhasePos; + + // start the resulting area flow + aFlowRes = pSuper->Area; + // iterate through the leaves + for ( i = 0; i < pCut->nLeaves; i++ ) + { + // get the phase of this fanin + fPinPhasePos = ((uPhaseTot & (1 << i)) == 0); + // get the cut implementing this phase of the fanin + pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos]; + // if the cut is not available, we have to use the opposite phase + if ( pCutFanin == NULL ) + { + fPinPhasePos = !fPinPhasePos; + pCutFanin = pCut->ppLeaves[i]->pCutBest[fPinPhasePos]; + } + aFlowFanin = pCutFanin->M[fPinPhasePos].AreaFlow; // ignores the area of the interter + // get the fanout count of the cut in the given phase + nRefs = Map_NodeReadRefPhaseEst( pCut->ppLeaves[i], fPinPhasePos ); + // if the node does no fanout, assume fanout count equal to 1 + if ( nRefs == (float)0.0 ) + nRefs = (float)1.0; + // add the area flow due to the fanin + aFlowRes += aFlowFanin / nRefs; + } + pM->AreaFlow = aFlowRes; + return aFlowRes; +} + + + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [Assumes that the cut is referenced.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutGetAreaRefed( Map_Cut_t * pCut, int fPhase ) +{ + float aResult, aResult2; + aResult2 = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference + aResult = Map_CutRefDeref( pCut, fPhase, 1 ); // reference + assert( aResult == aResult2 ); + return aResult; +} + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutGetAreaDerefed( Map_Cut_t * pCut, int fPhase ) +{ + float aResult, aResult2; + aResult2 = Map_CutRefDeref( pCut, fPhase, 1 ); // reference + aResult = Map_CutRefDeref( pCut, fPhase, 0 ); // dereference + assert( aResult == aResult2 ); + return aResult; +} + +/**function************************************************************* + + synopsis [References the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutRef( Map_Cut_t * pCut, int fPhase ) +{ + return Map_CutRefDeref( pCut, fPhase, 1 ); // reference +} + +/**function************************************************************* + + synopsis [References the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutDeref( Map_Cut_t * pCut, int fPhase ) +{ + return Map_CutRefDeref( pCut, fPhase, 0 ); // dereference +} + +/**function************************************************************* + + synopsis [References or dereferences the cut.] + + description [This reference part is similar to Cudd_NodeReclaim(). + The dereference part is similar to Cudd_RecursiveDeref(). The + area of the inverter is not counted.] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference ) +{ + Map_Node_t * pNodeChild; + Map_Cut_t * pCutChild; + float aArea; + int i, fPhaseChild; +// int nRefs; + + // consider the elementary variable + if ( pCut->nLeaves == 1 ) + return 0; + // start the area of this cut + aArea = Map_CutGetRootArea( pCut, fPhase ); + // go through the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pNodeChild = pCut->ppLeaves[i]; + fPhaseChild = Map_CutGetLeafPhase( pCut, fPhase, i ); + // get the reference counter of the child +/* + // this code does not take inverters into account + // the quality of area recovery seems to always be a little worse + if ( fReference ) + nRefs = Map_NodeIncRefPhaseAct( pNodeChild, fPhaseChild ); + else + nRefs = Map_NodeDecRefPhaseAct( pNodeChild, fPhaseChild ); + assert( nRefs >= 0 ); + // skip if the child was already reference before + if ( nRefs > 0 ) + continue; +*/ + + if ( fReference ) + { + if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present + { + // if this phase of the node is referenced, there is no recursive call + pNodeChild->nRefAct[2]++; + if ( pNodeChild->nRefAct[fPhaseChild]++ > 0 ) + continue; + } + else // only one phase is present + { + // inverter should be added if the phase + // (a) has no reference and (b) is implemented using other phase + if ( pNodeChild->nRefAct[fPhaseChild]++ == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL ) + aArea += pNodeChild->p->pSuperLib->AreaInv; + // if the node is referenced, there is no recursive call + if ( pNodeChild->nRefAct[2]++ > 0 ) + continue; + } + } + else + { + if ( pNodeChild->pCutBest[0] && pNodeChild->pCutBest[1] ) // both phases are present + { + // if this phase of the node is referenced, there is no recursive call + --pNodeChild->nRefAct[2]; + if ( --pNodeChild->nRefAct[fPhaseChild] > 0 ) + continue; + } + else // only one phase is present + { + // inverter should be added if the phase + // (a) has no reference and (b) is implemented using other phase + if ( --pNodeChild->nRefAct[fPhaseChild] == 0 && pNodeChild->pCutBest[fPhaseChild] == NULL ) + aArea += pNodeChild->p->pSuperLib->AreaInv; + // if the node is referenced, there is no recursive call + if ( --pNodeChild->nRefAct[2] > 0 ) + continue; + } + assert( pNodeChild->nRefAct[fPhaseChild] >= 0 ); + } + + // get the child cut + pCutChild = pNodeChild->pCutBest[fPhaseChild]; + // if the child does not have this phase mapped, take the opposite phase + if ( pCutChild == NULL ) + { + fPhaseChild = !fPhaseChild; + pCutChild = pNodeChild->pCutBest[fPhaseChild]; + } + // reference and compute area recursively + aArea += Map_CutRefDeref( pCutChild, fPhaseChild, fReference ); + } + return aArea; +} + + + + +/**Function************************************************************* + + Synopsis [Computes actual reference counters.] + + Description [Stores all the nodes used in the mapping in the array pMan->vMapping. + The nodes are stored in the random order.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetRefs( Map_Man_t * pMan ) +{ + Map_Node_t * pNode; + int i, fPhase; + // clean all references + for ( i = 0; i < pMan->vNodesAll->nSize; i++ ) + { + pNode = pMan->vNodesAll->pArray[i]; + pNode->nRefAct[0] = 0; + pNode->nRefAct[1] = 0; + pNode->nRefAct[2] = 0; + } + // visit nodes reachable from POs in the DFS order through the best cuts + pMan->vMapping->nSize = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + { + pNode = pMan->pOutputs[i]; + fPhase = !Map_IsComplement(pNode); + if ( !Map_NodeIsConst(pNode) ) + Map_MappingSetRefs_rec( pMan, pNode ); + // reference count the PO node +// Map_Regular(pNode)->nRefAct[fPhase]++; +// Map_Regular(pNode)->nRefAct[2]++; + } +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode ) +{ + Map_Cut_t * pCut; + Map_Node_t * pNodeR; + unsigned uPhase; + int i, fPhase, fInvPin; + + // get the regular node and its phase + pNodeR = Map_Regular(pNode); + fPhase = !Map_IsComplement(pNode); + + // add the node to the list of all visited nodes + if ( pNodeR->nRefAct[2]++ == 0 ) + Map_NodeVecPush( pMan->vMapping, pNodeR ); + + // quit if the node was already visited in this phase + if ( pNodeR->nRefAct[fPhase]++ ) + return; + + // quit if this is a PI node + if ( Map_NodeIsVar(pNodeR) ) + return; + + // get the cut implementing this or opposite polarity + pCut = pNodeR->pCutBest[fPhase]; + if ( pCut == NULL ) + { + fPhase = !fPhase; + pCut = pNodeR->pCutBest[fPhase]; + } + + // visit the transitive fanin + uPhase = pCut->M[fPhase].uPhaseBest; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + fInvPin = ((uPhase & (1 << i)) > 0); + Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin) ); + } +} + + +/**Function************************************************************* + + Synopsis [Computes the array of mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_MappingGetArea( Map_Man_t * pMan, Map_NodeVec_t * vMapping ) +{ + Map_Node_t * pNode; + float Area; + int i; + Area = 0.0; + for ( i = 0; i < vMapping->nSize; i++ ) + { + pNode = vMapping->pArray[i]; + // at least one phase has the best cut assigned + assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL ); + // at least one phase is used in the mapping + assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 ); + // compute the array due to the supergate + if ( Map_NodeIsAnd(pNode) ) + { + // count area of the negative phase + if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) ) + Area += pNode->pCutBest[0]->M[0].pSuperBest->Area; + // count area of the positive phase + if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) ) + Area += pNode->pCutBest[1]->M[1].pSuperBest->Area; + } + // count area of the interver if we need to implement one phase with another phase + if ( (pNode->pCutBest[0] == NULL && pNode->nRefAct[0] > 0) || + (pNode->pCutBest[1] == NULL && pNode->nRefAct[1] > 0) ) + Area += pMan->pSuperLib->AreaInv; + } + // add two inverters for each PO buffer + for ( i = 0; i < pMan->nOutputs; i++ ) + if ( Map_NodeIsVar(pMan->pOutputs[i]) && !Map_IsComplement(pMan->pOutputs[i]) ) + Area += 2 * pMan->pSuperLib->AreaInv; + return Area; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperSuper.c b/src/map/mapper/mapperSuper.c new file mode 100644 index 00000000..34b1d8e6 --- /dev/null +++ b/src/map/mapper/mapperSuper.c @@ -0,0 +1,449 @@ +/**CFile**************************************************************** + + FileName [mapperSuper.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperSuper.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_LibraryReadFile( Map_SuperLib_t * pLib, FILE * pFile ); +static Map_Super_t * Map_LibraryReadGate( Map_SuperLib_t * pLib, char * pBuffer, int nVars ); +static int Map_LibraryTruthVerify( Map_SuperLib_t * pLib, Map_Super_t * pGate ); +static void Map_LibraryComputeTruth( Map_SuperLib_t * pLib, char * pFormula, unsigned uTruthRes[] ); +static void Map_LibraryComputeTruth_rec( Map_SuperLib_t * pLib, char * pFormula, unsigned uTruthsIn[][2], unsigned uTruthRes[] ); +static void Map_LibraryPrintClasses( Map_SuperLib_t * p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads the supergate library from file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryRead( Map_SuperLib_t * pLib, char * pFileName ) +{ + FILE * pFile; + int Status; + // read the beginning of the file + assert( pLib->pGenlib == NULL ); + pFile = fopen( pFileName, "r" ); + if ( pFile == NULL ) + { + printf( "Cannot open input file \"%s\".\n", pFileName ); + return 0; + } + Status = Map_LibraryReadFile( pLib, pFile ); + fclose( pFile ); +// Map_LibraryPrintClasses( pLib ); + return Status; +} + + +/**Function************************************************************* + + Synopsis [Reads the library file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryReadFile( Map_SuperLib_t * pLib, FILE * pFile ) +{ + ProgressBar * pProgress; + char pBuffer[2000]; + FILE * pFileGen; + Map_Super_t * pGate; + char * pTemp, * pLibName; + int nCounter, nGatesTotal; + unsigned uCanon[2]; + + // skip empty and comment lines + while ( fgets( pBuffer, 5000, pFile ) != NULL ) + { + // skip leading spaces + for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ ); + // skip comment lines and empty lines + if ( *pTemp != 0 && *pTemp != '#' ) + break; + } + + // get the genlib file name + pLibName = strtok( pTemp, " \t\r\n" ); + if ( strcmp( pLibName, "GATE" ) == 0 ) + { + printf( "The input file \"%s\" looks like a GENLIB file and not a supergate library file.\n", pLib->pName ); + return 0; + } + pFileGen = fopen( pLibName, "r" ); + if ( pFileGen == NULL ) + { + printf( "Cannot open the GENLIB file \"%s\".\n", pLibName ); + return 0; + } + fclose( pFileGen ); + + // read the genlib library + pLib->pGenlib = Mio_LibraryRead( Abc_FrameGetGlobalFrame(), pLibName, 0, 0 ); + if ( pLib->pGenlib == NULL ) + { + printf( "Cannot read GENLIB file \"%s\".\n", pLibName ); + return 0; + } + + // read the number of variables + fscanf( pFile, "%d\n", &pLib->nVarsMax ); + if ( pLib->nVarsMax < 2 || pLib->nVarsMax > 10 ) + { + printf( "Suspicious number of variables (%d).\n", pLib->nVarsMax ); + return 0; + } + + // read the number of gates + fscanf( pFile, "%d\n", &nGatesTotal ); + if ( nGatesTotal < 1 || nGatesTotal > 10000000 ) + { + printf( "Suspicious number of gates (%d).\n", nGatesTotal ); + return 0; + } + + // read the lines + nCounter = 0; + pProgress = Extra_ProgressBarStart( stdout, nGatesTotal ); + while ( fgets( pBuffer, 5000, pFile ) != NULL ) + { + for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ ); + if ( pTemp[0] == '\0' ) + continue; + // get the gate + pGate = Map_LibraryReadGate( pLib, pTemp, pLib->nVarsMax ); + assert( pGate->Num == nCounter + 1 ); + // count the number of parantheses in the formula - this is the number of gates + for ( pTemp = pGate->pFormula; *pTemp; pTemp++ ) + pGate->nGates += (*pTemp == '('); + // verify the truth table + assert( Map_LibraryTruthVerify(pLib, pGate) ); + + // find the N-canonical form of this supergate + pGate->nPhases = Map_CanonComputeSlow( pLib->uTruths, pLib->nVarsMax, pLib->nVarsMax, pGate->uTruth, pGate->uPhases, uCanon ); + // add the supergate into the table by its N-canonical table + Map_SuperTableInsertC( pLib->tTableC, uCanon, pGate ); + // update the progress bar + Extra_ProgressBarUpdate( pProgress, ++nCounter, NULL ); + } + Extra_ProgressBarStop( pProgress ); + pLib->nSupersAll = nCounter; + if ( nCounter != nGatesTotal ) + printf( "The number of gates read (%d) is different what the file says (%d).\n", nGatesTotal, nCounter ); + return 1; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Super_t * Map_LibraryReadGate( Map_SuperLib_t * pLib, char * pBuffer, int nVars ) +{ + Map_Super_t * pGate; + char * pTemp; + int i; + + // start and clean the gate + pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers ); + memset( pGate, 0, sizeof(Map_Super_t) ); + + // read the number + pTemp = strtok( pBuffer, " " ); + pGate->Num = atoi(pTemp); + + // read the signature + pTemp = strtok( NULL, " " ); + if ( pLib->nVarsMax < 6 ) + { + pGate->uTruth[0] = Extra_ReadBinary(pTemp); + pGate->uTruth[1] = 0; + } + else + { + pGate->uTruth[0] = Extra_ReadBinary(pTemp+32); + pTemp[32] = 0; + pGate->uTruth[1] = Extra_ReadBinary(pTemp); + } + + // read the max delay + pTemp = strtok( NULL, " " ); + pGate->tDelayMax.Rise = (float)atof(pTemp); + pGate->tDelayMax.Fall = pGate->tDelayMax.Rise; + + // read the pin-to-pin delay + for ( i = 0; i < nVars; i++ ) + { + pTemp = strtok( NULL, " " ); + pGate->tDelaysR[i].Rise = (float)atof(pTemp); + pGate->tDelaysF[i].Fall = pGate->tDelaysR[i].Rise; + } + + // read the area + pTemp = strtok( NULL, " " ); + pGate->Area = (float)atof(pTemp); + + // the rest is the gate name + pTemp = strtok( NULL, " \r\n" ); + if ( strlen(pTemp) == 0 ) + printf( "A gate name is empty.\n" ); + + // save the gate name + pGate->pFormula = Extra_MmFlexEntryFetch( pLib->mmForms, strlen(pTemp) + 1 ); + strcpy( pGate->pFormula, pTemp ); + + // the rest is the gate name + pTemp = strtok( NULL, " \n\0" ); + if ( pTemp != NULL ) + printf( "The following trailing symbols found \"%s\".\n", pTemp ); + return pGate; +} + +/**Function************************************************************* + + Synopsis [Performs one step of parsing the formula into parts.] + + Description [This function will eventually be replaced when the + tree-supergate library representation will become standard.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Map_LibraryReadFormulaStep( char * pFormula, char * pStrings[], int * pnStrings ) +{ + char * pName, * pPar1, * pPar2, * pCur; + int nStrings, CountPars; + + // skip leading spaces + for ( pName = pFormula; *pName && *pName == ' '; pName++ ); + assert( *pName ); + // find the first opening paranthesis + for ( pPar1 = pName; *pPar1 && *pPar1 != '('; pPar1++ ); + if ( *pPar1 == 0 ) + { + *pnStrings = 0; + return pName; + } + // overwrite it with space + assert( *pPar1 == '(' ); + *pPar1 = 0; + // find the corresponding closing paranthesis + for ( CountPars = 1, pPar2 = pPar1 + 1; *pPar2 && CountPars; pPar2++ ) + if ( *pPar2 == '(' ) + CountPars++; + else if ( *pPar2 == ')' ) + CountPars--; + pPar2--; + assert( CountPars == 0 ); + // overwrite it with space + assert( *pPar2 == ')' ); + *pPar2 = 0; + // save the intervals between the commas + nStrings = 0; + pCur = pPar1 + 1; + while ( 1 ) + { + // save the current string + pStrings[ nStrings++ ] = pCur; + // find the beginning of the next string + for ( CountPars = 0; *pCur && (CountPars || *pCur != ','); pCur++ ) + if ( *pCur == '(' ) + CountPars++; + else if ( *pCur == ')' ) + CountPars--; + if ( *pCur == 0 ) + break; + assert( *pCur == ',' ); + *pCur = 0; + pCur++; + } + // save the results and return + *pnStrings = nStrings; + return pName; +} + + +/**Function************************************************************* + + Synopsis [Verifies the truth table of the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryTruthVerify( Map_SuperLib_t * pLib, Map_Super_t * pGate ) +{ + unsigned uTruthRes[2]; + Map_LibraryComputeTruth( pLib, pGate->pFormula, uTruthRes ); + if ( uTruthRes[0] != pGate->uTruth[0] || uTruthRes[1] != pGate->uTruth[1] ) + return 0; + return 1; +} + + +/**Function************************************************************* + + Synopsis [Derives the functionality of the supergate.] + + Description [This procedure is useful for verification the supergate + library. The truth table derived by this procedure should be the same + as the one contained in the original supergate file.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryComputeTruth( Map_SuperLib_t * pLib, char * pFormula, unsigned uTruthRes[] ) +{ + char Buffer[1000]; + strcpy( Buffer, pFormula ); + Map_LibraryComputeTruth_rec( pLib, Buffer, pLib->uTruths, uTruthRes ); +} + +/**Function************************************************************* + + Synopsis [Derives the functionality of the supergate.] + + Description [This procedure is useful for verification the supergate + library. The truth table derived by this procedure should be the same + as the one contained in the original supergate file.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryComputeTruth_rec( Map_SuperLib_t * pLib, char * pFormula, unsigned uTruthsIn[][2], unsigned uTruthRes[] ) +{ + Mio_Gate_t * pMioGate; + char * pGateName, * pStrings[6]; + unsigned uTruthsFanins[6][2]; + int nStrings, i; + + // perform one step parsing of the formula + // detect the root gate name, the next-step strings, and their number + pGateName = Map_LibraryReadFormulaStep( pFormula, pStrings, &nStrings ); + if ( nStrings == 0 ) // elementary variable + { + assert( pGateName[0] - 'a' < pLib->nVarsMax ); + uTruthRes[0] = uTruthsIn[pGateName[0] - 'a'][0]; + uTruthRes[1] = uTruthsIn[pGateName[0] - 'a'][1]; + return; + } + // derive the functionality of the fanins + for ( i = 0; i < nStrings; i++ ) + Map_LibraryComputeTruth_rec( pLib, pStrings[i], uTruthsIn, uTruthsFanins[i] ); + // get the root supergate + pMioGate = Mio_LibraryReadGateByName( pLib->pGenlib, pGateName ); + if ( pMioGate == NULL ) + printf( "A supergate contains gate \"%s\" that is not in \"%s\".\n", pGateName, Mio_LibraryReadName(pLib->pGenlib) ); + // derive the functionality of the output of the supergate + Mio_DeriveTruthTable( pMioGate, uTruthsFanins, nStrings, pLib->nVarsMax, uTruthRes ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryPrintSupergate( Map_Super_t * pGate ) +{ + printf( "%5d : ", pGate->nUsed ); + printf( "%5d ", pGate->Num ); + printf( "A = %5.2f ", pGate->Area ); + printf( "D = %5.2f ", pGate->tDelayMax ); + printf( "%s", pGate->pFormula ); + printf( "\n" ); +} + + +/**Function************************************************************* + + Synopsis [Prints N-classes of supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryPrintClasses( Map_SuperLib_t * p ) +{ +/* + st_generator * gen; + Map_Super_t * pSuper, * pSuper2; + unsigned Key, uTruth; + int Counter = 0; + // copy all the supergates into one array + st_foreach_item( p->tSuplib, gen, (char **)&Key, (char **)&pSuper ) + { + for ( pSuper2 = pSuper; pSuper2; pSuper2 = pSuper2->pNext ) + { + uTruth = pSuper2->Phase; + Extra_PrintBinary( stdout, &uTruth, 5 ); + printf( " %5d ", pSuper2->Num ); + printf( "%s", pSuper2->pFormula ); + printf( "\n" ); + } + printf( "\n" ); + if ( ++ Counter == 100 ) + break; + } +*/ +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperTable.c b/src/map/mapper/mapperTable.c new file mode 100644 index 00000000..747fe1c8 --- /dev/null +++ b/src/map/mapper/mapperTable.c @@ -0,0 +1,402 @@ +/**CFile**************************************************************** + + FileName [mapperTable.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperTable.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the table function for the tables +#define MAP_TABLE_HASH(u1,u2,nSize) (((u1) + 2003 * (u2)) % nSize) + +static void Map_SuperTableResize( Map_HashTable_t * pLib ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates the hash table for supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_HashTable_t * Map_SuperTableCreate( Map_SuperLib_t * pLib ) +{ + Map_HashTable_t * p; + // allocate the table + p = ALLOC( Map_HashTable_t, 1 ); + memset( p, 0, sizeof(Map_HashTable_t) ); + p->mmMan = pLib->mmEntries; + // allocate and clean the bins + p->nBins = Cudd_Prime(20000); + p->pBins = ALLOC( Map_HashEntry_t *, p->nBins ); + memset( p->pBins, 0, sizeof(Map_HashEntry_t *) * p->nBins ); + return p; +} + + +/**Function************************************************************* + + Synopsis [Deallocates the supergate hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_SuperTableFree( Map_HashTable_t * p ) +{ + FREE( p->pBins ); + FREE( p ); +} + +/**Function************************************************************* + + Synopsis [Inserts a new entry into the hash table.] + + Description [This function inserts the new gate (pGate), which will be + accessible through its canonical form (uTruthC).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_SuperTableInsertC( Map_HashTable_t * p, unsigned uTruthC[], Map_Super_t * pGate ) +{ + Map_HashEntry_t * pEnt; + unsigned Key; + // resize the table + if ( p->nEntries >= 2 * p->nBins ) + Map_SuperTableResize( p ); + // check if another supergate with the same canonical form exists + Key = MAP_TABLE_HASH( uTruthC[0], uTruthC[1], p->nBins ); + for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->uTruth[0] == uTruthC[0] && pEnt->uTruth[1] == uTruthC[1] ) + break; + // create a new entry if it does not exist + if ( pEnt == NULL ) + { + // add the new entry to the table + pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan ); + memset( pEnt, 0, sizeof(Map_HashEntry_t) ); + pEnt->uTruth[0] = uTruthC[0]; + pEnt->uTruth[1] = uTruthC[1]; + // add the hash table entry to the corresponding linked list in the table + pEnt->pNext = p->pBins[Key]; + p->pBins[Key] = pEnt; + p->nEntries++; + } + // add the supergate to the entry + pGate->pNext = pEnt->pGates; + pEnt->pGates = pGate; + return 0; +} + + + +/**Function************************************************************* + + Synopsis [Inserts a new entry into the library.] + + Description [This function inserts the new gate (pGate), which will be + accessible through its unfolded function (uTruth).] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_SuperTableInsert( Map_HashTable_t * p, unsigned uTruth[], Map_Super_t * pGate, unsigned uPhase ) +{ + Map_HashEntry_t * pEnt; + unsigned Key; + // resize the table + if ( p->nEntries >= 2 * p->nBins ) + Map_SuperTableResize( p ); + // check if this entry already exists + Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins ); + for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) + return 1; + // add the new hash table entry to the table + pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan ); + memset( pEnt, 0, sizeof(Map_HashEntry_t) ); + pEnt->uTruth[0] = uTruth[0]; + pEnt->uTruth[1] = uTruth[1]; + pEnt->pGates = pGate; + pEnt->uPhase = uPhase; + // add the hash table to the corresponding linked list in the table + pEnt->pNext = p->pBins[Key]; + p->pBins[Key] = pEnt; + p->nEntries++; +/* +printf( "Adding gate: %10u ", Key ); +Map_LibraryPrintSupergate( pGate ); +Extra_PrintBinary( stdout, uTruth, 32 ); +printf( "\n" ); +*/ + return 0; +} + +/**Function************************************************************* + + Synopsis [Looks up an entry in the library.] + + Description [This function looks up the function, given by its truth table, + and return two things: (1) the linked list of supergates, which can implement + the functions of this N-class; (2) the phase, which should be applied to the + given function, in order to derive the canonical form of this N-class.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Super_t * Map_SuperTableLookupC( Map_SuperLib_t * p, unsigned uTruth[] ) +{ + Map_HashEntry_t * pEnt; + unsigned Key; + Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->tTableC->nBins ); + for ( pEnt = p->tTableC->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) + return pEnt->pGates; + return NULL; +} + +/**Function************************************************************* + + Synopsis [Looks up an entry in the library.] + + Description [This function looks up the function, given by its truth table, + and return two things: (1) the linked list of supergates, which can implement + the functions of this N-class; (2) the phase, which should be applied to the + given function, in order to derive the canonical form of this N-class.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Super_t * Map_SuperTableLookup( Map_HashTable_t * p, unsigned uTruth[], unsigned * puPhase ) +{ + Map_HashEntry_t * pEnt; + unsigned Key; + Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins ); + for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext ) + if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] ) + { + *puPhase = pEnt->uPhase; + return pEnt->pGates; + } + return NULL; +} + +/**Function************************************************************* + + Synopsis [Resizes the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_SuperTableResize( Map_HashTable_t * p ) +{ + Map_HashEntry_t ** pBinsNew; + Map_HashEntry_t * pEnt, * pEnt2; + int nBinsNew, Counter, i, clk = clock(); + unsigned Key; + // get the new table size + nBinsNew = Cudd_Prime(2 * p->nBins); + // allocate a new array + pBinsNew = ALLOC( Map_HashEntry_t *, nBinsNew ); + memset( pBinsNew, 0, sizeof(Map_HashEntry_t *) * nBinsNew ); + // rehash the entries from the old table + Counter = 0; + for ( i = 0; i < p->nBins; i++ ) + for ( pEnt = p->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; + pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL ) + { + Key = MAP_TABLE_HASH( pEnt->uTruth[0], pEnt->uTruth[1], nBinsNew ); + pEnt->pNext = pBinsNew[Key]; + pBinsNew[Key] = pEnt; + Counter++; + } + assert( Counter == p->nEntries ); + // replace the table and the parameters + free( p->pBins ); + p->pBins = pBinsNew; + p->nBins = nBinsNew; +} + +/**Function************************************************************* + + Synopsis [Compares the supergates by the number of times they are used.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_SuperTableCompareSupergates( Map_Super_t ** ppS1, Map_Super_t ** ppS2 ) +{ + if ( (*ppS1)->nUsed > (*ppS2)->nUsed ) + return -1; + if ( (*ppS1)->nUsed < (*ppS2)->nUsed ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Compares the supergates by the number of times they are used.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_SuperTableCompareGatesInList( Map_Super_t ** ppS1, Map_Super_t ** ppS2 ) +{ +// if ( (*ppS1)->tDelayMax.Rise > (*ppS2)->tDelayMax.Rise ) + if ( (*ppS1)->Area > (*ppS2)->Area ) + return -1; +// if ( (*ppS1)->tDelayMax.Rise < (*ppS2)->tDelayMax.Rise ) + if ( (*ppS1)->Area < (*ppS2)->Area ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Sorts supergates by usefulness and prints out most useful.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_SuperTableSortSupergates( Map_HashTable_t * p, int nSupersMax ) +{ + Map_HashEntry_t * pEnt; + Map_Super_t ** ppSupers; + Map_Super_t * pSuper; + int nSupers, i; + + // copy all the supergates into one array + ppSupers = ALLOC( Map_Super_t *, nSupersMax ); + nSupers = 0; + for ( i = 0; i < p->nBins; i++ ) + for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext ) + for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext ) + ppSupers[nSupers++] = pSuper; + + // sort by usage + qsort( (void *)ppSupers, nSupers, sizeof(int), + (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates ); + assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); + + // print out the "top ten" +// for ( i = 0; i < nSupers; i++ ) + for ( i = 0; i < 10; i++ ) + { + if ( ppSupers[i]->nUsed == 0 ) + break; + printf( "%5d : ", ppSupers[i]->nUsed ); + printf( "%5d ", ppSupers[i]->Num ); + printf( "A = %5.2f ", ppSupers[i]->Area ); + printf( "D = %5.2f ", ppSupers[i]->tDelayMax.Rise ); + printf( "%s", ppSupers[i]->pFormula ); + printf( "\n" ); + } + free( ppSupers ); +} + +/**Function************************************************************* + + Synopsis [Sorts supergates by max delay for each truth table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_SuperTableSortSupergatesByDelay( Map_HashTable_t * p, int nSupersMax ) +{ + Map_HashEntry_t * pEnt; + Map_Super_t ** ppSupers; + Map_Super_t * pSuper; + int nSupers, i, k; + + ppSupers = ALLOC( Map_Super_t *, nSupersMax ); + for ( i = 0; i < p->nBins; i++ ) + for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext ) + { + // collect the gates in this entry + nSupers = 0; + for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext ) + { + // skip supergates, whose root is the AND gate +// if ( strcmp( Mio_GateReadName(pSuper->pRoot), "and" ) == 0 ) +// continue; + ppSupers[nSupers++] = pSuper; + } + pEnt->pGates = NULL; + if ( nSupers == 0 ) + continue; + // sort the gates by delay + qsort( (void *)ppSupers, nSupers, sizeof(int), + (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList ); + assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 ); + // link them in the reverse order + for ( k = 0; k < nSupers; k++ ) + { + ppSupers[k]->pNext = pEnt->pGates; + pEnt->pGates = ppSupers[k]; + } + // save the number of supergates in the list + pEnt->pGates->nSupers = nSupers; + } + FREE( ppSupers ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperTime.c b/src/map/mapper/mapperTime.c new file mode 100644 index 00000000..0ff88b0e --- /dev/null +++ b/src/map/mapper/mapperTime.c @@ -0,0 +1,508 @@ +/**CFile**************************************************************** + + FileName [mapperTime.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperTime.c,v 1.3 2005/03/02 02:35:54 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Map_TimePropagateRequired( Map_Man_t * p, Map_NodeVec_t * vNodes ); +static void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ); +static float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**function************************************************************* + + synopsis [Computes the exact area associated with the cut.] + + description [] + + sideeffects [] + + seealso [] + +***********************************************************************/ +float Map_TimeMatchWithInverter( Map_Man_t * p, Map_Match_t * pMatch ) +{ + Map_Time_t tArrInv; + tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall; + tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise; + tArrInv.Worst = MAP_MAX( tArrInv.Rise, tArrInv.Fall ); + return tArrInv.Worst; +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times of the cut recursively.] + + Description [When computing the arrival time for the previously unused + cuts, their arrival time may be incorrect because their fanins have + incorrect arrival time. This procedure is called to fix this problem.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimeCutComputeArrival_rec( Map_Cut_t * pCut, int fPhase ) +{ + int i, fPhaseLeaf; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + fPhaseLeaf = Map_CutGetLeafPhase( pCut, fPhase, i ); + if ( pCut->ppLeaves[i]->nRefAct[fPhaseLeaf] > 0 ) + continue; + Map_TimeCutComputeArrival_rec( pCut->ppLeaves[i]->pCutBest[fPhaseLeaf], fPhaseLeaf ); + } + Map_TimeCutComputeArrival( NULL, pCut, fPhase, MAP_FLOAT_LARGE ); +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times of the cut.] + + Description [Computes the arrival times of the cut if it is implemented using + the given supergate with the given phase. Uses the constraint-type specification + of rise/fall arrival times.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_TimeCutComputeArrival( Map_Node_t * pNode, Map_Cut_t * pCut, int fPhase, float tWorstLimit ) +{ + Map_Match_t * pM = pCut->M + fPhase; + Map_Super_t * pSuper = pM->pSuperBest; + unsigned uPhaseTot = pM->uPhaseBest; + Map_Time_t * ptArrRes = &pM->tArrive; + Map_Time_t * ptArrIn; + bool fPinPhase; + float tDelay; + int i; + + ptArrRes->Rise = ptArrRes->Fall = 0.0; + ptArrRes->Worst = MAP_FLOAT_LARGE; + for ( i = pCut->nLeaves - 1; i >= 0; i-- ) + { + // get the phase of the given pin + fPinPhase = ((uPhaseTot & (1 << i)) == 0); + ptArrIn = pCut->ppLeaves[i]->tArrival + fPinPhase; + + // get the rise of the output due to rise of the inputs + if ( pSuper->tDelaysR[i].Rise > 0 ) + { + tDelay = ptArrIn->Rise + pSuper->tDelaysR[i].Rise; + if ( tDelay > tWorstLimit ) + return MAP_FLOAT_LARGE; + if ( ptArrRes->Rise < tDelay ) + ptArrRes->Rise = tDelay; + } + + // get the rise of the output due to fall of the inputs + if ( pSuper->tDelaysR[i].Fall > 0 ) + { + tDelay = ptArrIn->Fall + pSuper->tDelaysR[i].Fall; + if ( tDelay > tWorstLimit ) + return MAP_FLOAT_LARGE; + if ( ptArrRes->Rise < tDelay ) + ptArrRes->Rise = tDelay; + } + + // get the fall of the output due to rise of the inputs + if ( pSuper->tDelaysF[i].Rise > 0 ) + { + tDelay = ptArrIn->Rise + pSuper->tDelaysF[i].Rise; + if ( tDelay > tWorstLimit ) + return MAP_FLOAT_LARGE; + if ( ptArrRes->Fall < tDelay ) + ptArrRes->Fall = tDelay; + } + + // get the fall of the output due to fall of the inputs + if ( pSuper->tDelaysF[i].Fall > 0 ) + { + tDelay = ptArrIn->Fall + pSuper->tDelaysF[i].Fall; + if ( tDelay > tWorstLimit ) + return MAP_FLOAT_LARGE; + if ( ptArrRes->Fall < tDelay ) + ptArrRes->Fall = tDelay; + } + } + // return the worst-case of rise/fall arrival times + ptArrRes->Worst = MAP_MAX(ptArrRes->Rise, ptArrRes->Fall); + return ptArrRes->Worst; +} + + +/**Function************************************************************* + + Synopsis [Computes the maximum arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_TimeComputeArrivalMax( Map_Man_t * p ) +{ + float tReqMax, tReq; + int i, fPhase; + // get the critical PO arrival time + tReqMax = -MAP_FLOAT_LARGE; + for ( i = 0; i < p->nOutputs; i++ ) + { + if ( Map_NodeIsConst(p->pOutputs[i]) ) + continue; + fPhase = !Map_IsComplement(p->pOutputs[i]); + tReq = Map_Regular(p->pOutputs[i])->tArrival[fPhase].Worst; + tReqMax = MAP_MAX( tReqMax, tReq ); + } + return tReqMax; +} + +/**Function************************************************************* + + Synopsis [Computes the required times of all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimeComputeRequiredGlobal( Map_Man_t * p ) +{ + p->fRequiredGlo = Map_TimeComputeArrivalMax( p ); + // update the required times according to the target + if ( p->DelayTarget != -1 ) + { + if ( p->fRequiredGlo > p->DelayTarget + p->fEpsilon ) + { + if ( p->fMappingMode == 1 ) + printf( "Cannot meet the target required times (%4.2f). Continue anyway.\n", p->DelayTarget ); + } + else if ( p->fRequiredGlo < p->DelayTarget - p->fEpsilon ) + { + if ( p->fMappingMode == 1 ) + printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->fRequiredGlo, p->DelayTarget ); + p->fRequiredGlo = p->DelayTarget; + } + } + Map_TimeComputeRequired( p, p->fRequiredGlo ); +} + +/**Function************************************************************* + + Synopsis [Computes the required times of all nodes.] + + Description [This procedure assumes that the nodes used in the mapping + are collected in p->vMapping.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimeComputeRequired( Map_Man_t * p, float fRequired ) +{ + Map_Time_t * ptTime; + int fPhase, i; + + // clean the required times + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + p->vAnds->pArray[i]->tRequired[0].Rise = MAP_FLOAT_LARGE; + p->vAnds->pArray[i]->tRequired[0].Fall = MAP_FLOAT_LARGE; + p->vAnds->pArray[i]->tRequired[0].Worst = MAP_FLOAT_LARGE; + p->vAnds->pArray[i]->tRequired[1].Rise = MAP_FLOAT_LARGE; + p->vAnds->pArray[i]->tRequired[1].Fall = MAP_FLOAT_LARGE; + p->vAnds->pArray[i]->tRequired[1].Worst = MAP_FLOAT_LARGE; + } + + // set the required times for the POs + for ( i = 0; i < p->nOutputs; i++ ) + { + fPhase = !Map_IsComplement(p->pOutputs[i]); + ptTime = Map_Regular(p->pOutputs[i])->tRequired + fPhase; + ptTime->Rise = ptTime->Fall = ptTime->Worst = fRequired; + } + + // sorts the nodes in the decreasing order of levels + // this puts the nodes in reverse topological order + Map_MappingSortByLevel( p, p->vMapping ); + Map_TimePropagateRequired( p, p->vMapping ); +} + +/**Function************************************************************* + + Synopsis [Computes the required times of the given nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimePropagateRequired( Map_Man_t * p, Map_NodeVec_t * vNodes ) +{ + Map_Node_t * pNode; + Map_Time_t tReqOutTest, * ptReqOutTest = &tReqOutTest; + Map_Time_t * ptReqIn, * ptReqOut; + int fPhase, k; + + // go through the nodes in the reverse topological order + for ( k = 0; k < vNodes->nSize; k++ ) + { + pNode = vNodes->pArray[k]; + + // this computation works for regular nodes only + assert( !Map_IsComplement(pNode) ); + // at least one phase should be mapped + assert( pNode->pCutBest[0] != NULL || pNode->pCutBest[1] != NULL ); + // the node should be used in the currently assigned mapping + assert( pNode->nRefAct[0] > 0 || pNode->nRefAct[1] > 0 ); + + // if one of the cuts is not given, project the required times from the other cut + if ( pNode->pCutBest[0] == NULL || pNode->pCutBest[1] == NULL ) + { +// assert( 0 ); + // get the missing phase + fPhase = (pNode->pCutBest[1] == NULL); + // check if the missing phase is needed in the mapping + if ( pNode->nRefAct[fPhase] > 0 ) + { + // get the pointers to the required times of the missing phase + ptReqOut = pNode->tRequired + fPhase; +// assert( ptReqOut->Fall < MAP_FLOAT_LARGE ); + // get the pointers to the required times of the present phase + ptReqIn = pNode->tRequired + !fPhase; + // propagate the required times from the missing phase to the present phase + // tArrInv.Fall = pMatch->tArrive.Rise + p->pSuperLib->tDelayInv.Fall; + // tArrInv.Rise = pMatch->tArrive.Fall + p->pSuperLib->tDelayInv.Rise; + ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, ptReqOut->Rise - p->pSuperLib->tDelayInv.Rise ); + ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, ptReqOut->Fall - p->pSuperLib->tDelayInv.Fall ); + } + } + + // finalize the worst case computation + pNode->tRequired[0].Worst = MAP_MIN( pNode->tRequired[0].Fall, pNode->tRequired[0].Rise ); + pNode->tRequired[1].Worst = MAP_MIN( pNode->tRequired[1].Fall, pNode->tRequired[1].Rise ); + + // skip the PIs + if ( !Map_NodeIsAnd(pNode) ) + continue; + + // propagate required times of different phases of the node + // the ordering of phases does not matter since they are mapped independently + if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE ) + Map_TimePropagateRequiredPhase( p, pNode, 0 ); + if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE ) + Map_TimePropagateRequiredPhase( p, pNode, 1 ); + } + + // in the end, we verify the required times + // for this, we compute the arrival times of the outputs of each phase + // of the supergates using the fanins' required times as the fanins' arrival times + // the resulting arrival time of the supergate should be less than the actual required time + for ( k = 0; k < vNodes->nSize; k++ ) + { + pNode = vNodes->pArray[k]; + if ( !Map_NodeIsAnd(pNode) ) + continue; + // verify that the required times are propagated correctly +// if ( pNode->pCutBest[0] && (pNode->nRefAct[0] > 0 || pNode->pCutBest[1] == NULL) ) + if ( pNode->pCutBest[0] && pNode->tRequired[0].Worst < MAP_FLOAT_LARGE ) + { + Map_MatchComputeReqTimes( pNode->pCutBest[0], 0, ptReqOutTest ); + assert( ptReqOutTest->Rise < pNode->tRequired[0].Rise + p->fEpsilon ); + assert( ptReqOutTest->Fall < pNode->tRequired[0].Fall + p->fEpsilon ); + } +// if ( pNode->pCutBest[1] && (pNode->nRefAct[1] > 0 || pNode->pCutBest[0] == NULL) ) + if ( pNode->pCutBest[1] && pNode->tRequired[1].Worst < MAP_FLOAT_LARGE ) + { + Map_MatchComputeReqTimes( pNode->pCutBest[1], 1, ptReqOutTest ); + assert( ptReqOutTest->Rise < pNode->tRequired[1].Rise + p->fEpsilon ); + assert( ptReqOutTest->Fall < pNode->tRequired[1].Fall + p->fEpsilon ); + } + } + +} + +/**Function************************************************************* + + Synopsis [Computes the required times of the given nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TimePropagateRequiredPhase( Map_Man_t * p, Map_Node_t * pNode, int fPhase ) +{ + Map_Time_t * ptReqIn, * ptReqOut; + Map_Cut_t * pCut; + Map_Super_t * pSuper; + float tNewReqTime; + unsigned uPhase; + int fPinPhase, i; + + // get the cut to be propagated + pCut = pNode->pCutBest[fPhase]; + assert( pCut != NULL ); + // get the supergate and its polarity + pSuper = pCut->M[fPhase].pSuperBest; + uPhase = pCut->M[fPhase].uPhaseBest; + // get the required time of the output of the supergate + ptReqOut = pNode->tRequired + fPhase; + // set the required time of the children + for ( i = 0; i < pCut->nLeaves; i++ ) + { + // get the phase of the given pin of the supergate + fPinPhase = ((uPhase & (1 << i)) == 0); + ptReqIn = pCut->ppLeaves[i]->tRequired + fPinPhase; + assert( pCut->ppLeaves[i]->nRefAct[2] > 0 ); + + // get the rise of the output due to rise of the inputs +// if ( ptArrOut->Rise < ptArrIn->Rise + pSuper->tDelaysR[i].Rise ) +// ptArrOut->Rise = ptArrIn->Rise + pSuper->tDelaysR[i].Rise; + if ( pSuper->tDelaysR[i].Rise > 0 ) + { + tNewReqTime = ptReqOut->Rise - pSuper->tDelaysR[i].Rise; + ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, tNewReqTime ); + } + + // get the rise of the output due to fall of the inputs +// if ( ptArrOut->Rise < ptArrIn->Fall + pSuper->tDelaysR[i].Fall ) +// ptArrOut->Rise = ptArrIn->Fall + pSuper->tDelaysR[i].Fall; + if ( pSuper->tDelaysR[i].Fall > 0 ) + { + tNewReqTime = ptReqOut->Rise - pSuper->tDelaysR[i].Fall; + ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, tNewReqTime ); + } + + // get the fall of the output due to rise of the inputs +// if ( ptArrOut->Fall < ptArrIn->Rise + pSuper->tDelaysF[i].Rise ) +// ptArrOut->Fall = ptArrIn->Rise + pSuper->tDelaysF[i].Rise; + if ( pSuper->tDelaysF[i].Rise > 0 ) + { + tNewReqTime = ptReqOut->Fall - pSuper->tDelaysF[i].Rise; + ptReqIn->Rise = MAP_MIN( ptReqIn->Rise, tNewReqTime ); + } + + // get the fall of the output due to fall of the inputs +// if ( ptArrOut->Fall < ptArrIn->Fall + pSuper->tDelaysF[i].Fall ) +// ptArrOut->Fall = ptArrIn->Fall + pSuper->tDelaysF[i].Fall; + if ( pSuper->tDelaysF[i].Fall > 0 ) + { + tNewReqTime = ptReqOut->Fall - pSuper->tDelaysF[i].Fall; + ptReqIn->Fall = MAP_MIN( ptReqIn->Fall, tNewReqTime ); + } + } + + // compare the required times with the arrival times + assert( pNode->tArrival[fPhase].Rise < ptReqOut->Rise + p->fEpsilon ); + assert( pNode->tArrival[fPhase].Fall < ptReqOut->Fall + p->fEpsilon ); +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times of the cut.] + + Description [Computes the arrival times of the cut if it is implemented using + the given supergate with the given phase. Uses the constraint-type specification + of rise/fall arrival times.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_MatchComputeReqTimes( Map_Cut_t * pCut, int fPhase, Map_Time_t * ptArrRes ) +{ + Map_Time_t * ptArrIn; + Map_Super_t * pSuper; + unsigned uPhaseTot; + int fPinPhase, i; + float tDelay; + + // get the supergate and the phase + pSuper = pCut->M[fPhase].pSuperBest; + uPhaseTot = pCut->M[fPhase].uPhaseBest; + + // propagate the arrival times + ptArrRes->Rise = ptArrRes->Fall = -MAP_FLOAT_LARGE; + for ( i = 0; i < pCut->nLeaves; i++ ) + { + // get the phase of the given pin + fPinPhase = ((uPhaseTot & (1 << i)) == 0); + ptArrIn = pCut->ppLeaves[i]->tRequired + fPinPhase; +// assert( ptArrIn->Worst < MAP_FLOAT_LARGE ); + + // get the rise of the output due to rise of the inputs + if ( pSuper->tDelaysR[i].Rise > 0 ) + { + tDelay = ptArrIn->Rise + pSuper->tDelaysR[i].Rise; + if ( ptArrRes->Rise < tDelay ) + ptArrRes->Rise = tDelay; + } + + // get the rise of the output due to fall of the inputs + if ( pSuper->tDelaysR[i].Fall > 0 ) + { + tDelay = ptArrIn->Fall + pSuper->tDelaysR[i].Fall; + if ( ptArrRes->Rise < tDelay ) + ptArrRes->Rise = tDelay; + } + + // get the fall of the output due to rise of the inputs + if ( pSuper->tDelaysF[i].Rise > 0 ) + { + tDelay = ptArrIn->Rise + pSuper->tDelaysF[i].Rise; + if ( ptArrRes->Fall < tDelay ) + ptArrRes->Fall = tDelay; + } + + // get the fall of the output due to fall of the inputs + if ( pSuper->tDelaysF[i].Fall > 0 ) + { + tDelay = ptArrIn->Fall + pSuper->tDelaysF[i].Fall; + if ( ptArrRes->Fall < tDelay ) + ptArrRes->Fall = tDelay; + } + } + // return the worst-case of rise/fall arrival times + return MAP_MAX(ptArrRes->Rise, ptArrRes->Fall); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperTree.c b/src/map/mapper/mapperTree.c new file mode 100644 index 00000000..61e12748 --- /dev/null +++ b/src/map/mapper/mapperTree.c @@ -0,0 +1,804 @@ +/**CFile**************************************************************** + + FileName [mapperTree.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperTree.c,v 1.9 2005/01/23 06:59:45 alanmi Exp $] + +***********************************************************************/ + +#ifdef __linux__ +#include <libgen.h> +#endif + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_LibraryReadFileTree( Map_SuperLib_t * pLib, FILE * pFile, char *pFileName ); +static Map_Super_t * Map_LibraryReadGateTree( Map_SuperLib_t * pLib, char * pBuffer, int Number, int nVars ); +static int Map_LibraryDeriveGateInfo( Map_SuperLib_t * pLib, st_table * tExcludeGate ); +static void Map_LibraryAddFaninDelays( Map_SuperLib_t * pLib, Map_Super_t * pGate, Map_Super_t * pFanin, Mio_Pin_t * pPin ); +static int Map_LibraryGetMaxSuperPi_rec( Map_Super_t * pGate ); +static unsigned Map_LibraryGetGateSupp_rec( Map_Super_t * pGate ); + +// fanout limits +extern const int s_MapFanoutLimits[10] = { 1/*0*/, 10/*1*/, 5/*2*/, 2/*3*/, 1/*4*/, 1/*5*/, 1/*6*/ }; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Reads the supergate library from file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryReadTree( Map_SuperLib_t * pLib, char * pFileName, char * pExcludeFile ) +{ + FILE * pFile; + int Status, num; + Abc_Frame_t * pAbc; + st_table * tExcludeGate = 0; + + // read the beginning of the file + assert( pLib->pGenlib == NULL ); +// pFile = Io_FileOpen( pFileName, "open_path", "r" ); + pFile = fopen( pFileName, "r" ); + if ( pFile == NULL ) + { + printf( "Cannot open input file \"%s\".\n", pFileName ); + return 0; + } + + if ( pExcludeFile ) + { + pAbc = Abc_FrameGetGlobalFrame(); + + tExcludeGate = st_init_table(strcmp, st_strhash); + if ( (num = Mio_LibraryReadExclude( pAbc, pExcludeFile, tExcludeGate )) == -1 ) + { + st_free_table( tExcludeGate ); + tExcludeGate = 0; + return 0; + } + + fprintf ( Abc_FrameReadOut( pAbc ), "Read %d gates from exclude file\n", num ); + } + + Status = Map_LibraryReadFileTree( pLib, pFile, pFileName ); + fclose( pFile ); + if ( Status == 0 ) + return 0; + // prepare the info about the library + return Map_LibraryDeriveGateInfo( pLib, tExcludeGate ); +} + + +/**Function************************************************************* + + Synopsis [Reads the library file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryReadFileTree( Map_SuperLib_t * pLib, FILE * pFile, char *pFileName ) +{ + ProgressBar * pProgress; + char pBuffer[5000], pLibFile[5000]; + FILE * pFileGen; + Map_Super_t * pGate; + char * pTemp = 0, * pLibName; + int nCounter, k, i; + + // skip empty and comment lines + while ( fgets( pBuffer, 5000, pFile ) != NULL ) + { + // skip leading spaces + for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ ); + // skip comment lines and empty lines + if ( *pTemp != 0 && *pTemp != '#' ) + break; + } + + // get the genlib file name (base) + pLibName = strtok( pTemp, " \t\r\n" ); + + if ( strcmp( pLibName, "GATE" ) == 0 ) + { + printf( "The input file \"%s\" looks like a GENLIB file and not a supergate library file.\n", pLib->pName ); + return 0; + } + + + // now figure out the directory if any in the pFileName +#ifdef __linux__ + snprintf( pLibFile, 5000, "%s/%s", dirname(strdup(pFileName)), pLibName ); +#else + { + char * pStr; + strcpy( pLibFile, pFileName ); + pStr = pLibFile + strlen(pBuffer) - 1; + while ( pStr > pLibFile && *pStr != '\\' && *pStr != '/' ) + pStr--; + if ( pStr == pLibFile ) + strcpy( pLibFile, pLibName ); + else + sprintf( pStr, "/%s", pLibName ); + } +#endif + +// pFileGen = Io_FileOpen( pLibFile, "open_path", "r" ); + pFileGen = fopen( pLibFile, "r" ); + if ( pFileGen == NULL ) + { + printf( "Cannot open the GENLIB file \"%s\".\n", pLibFile ); + return 0; + } + fclose( pFileGen ); + + // read the genlib library + pLib->pGenlib = Mio_LibraryRead( Abc_FrameGetGlobalFrame(), pLibFile, 0, 0 ); + if ( pLib->pGenlib == NULL ) + { + printf( "Cannot read GENLIB file \"%s\".\n", pLibFile ); + return 0; + } + + // read the number of variables + fscanf( pFile, "%d\n", &pLib->nVarsMax ); + if ( pLib->nVarsMax < 2 || pLib->nVarsMax > 10 ) + { + printf( "Suspicious number of variables (%d).\n", pLib->nVarsMax ); + return 0; + } + + // read the number of gates + fscanf( pFile, "%d\n", &pLib->nSupersReal ); + if ( pLib->nSupersReal < 1 || pLib->nSupersReal > 10000000 ) + { + printf( "Suspicious number of gates (%d).\n", pLib->nSupersReal ); + return 0; + } + + // read the number of lines + fscanf( pFile, "%d\n", &pLib->nLines ); + if ( pLib->nLines < 1 || pLib->nLines > 10000000 ) + { + printf( "Suspicious number of lines (%d).\n", pLib->nLines ); + return 0; + } + + // allocate room for supergate pointers + pLib->ppSupers = ALLOC( Map_Super_t *, pLib->nLines + 10000 ); + + // create the elementary supergates + for ( i = 0; i < pLib->nVarsMax; i++ ) + { + // get a new gate + pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers ); + memset( pGate, 0, sizeof(Map_Super_t) ); + // assign the elementary variable, the truth table, and the delays + pGate->Num = i; + // set the truth table + pGate->uTruth[0] = pLib->uTruths[i][0]; + pGate->uTruth[1] = pLib->uTruths[i][1]; + // set the arrival times of all input to non-existent delay + for ( k = 0; k < pLib->nVarsMax; k++ ) + { + pGate->tDelaysR[k].Rise = pGate->tDelaysR[k].Fall = MAP_NO_VAR; + pGate->tDelaysF[k].Rise = pGate->tDelaysF[k].Fall = MAP_NO_VAR; + } + // set an existent arrival time for rise and fall + pGate->tDelaysR[i].Rise = 0.0; + pGate->tDelaysF[i].Fall = 0.0; + // set the gate + pLib->ppSupers[i] = pGate; + } + + // read the lines + nCounter = pLib->nVarsMax; + pProgress = Extra_ProgressBarStart( stdout, pLib->nLines ); + while ( fgets( pBuffer, 5000, pFile ) != NULL ) + { + for ( pTemp = pBuffer; *pTemp == ' ' || *pTemp == '\r' || *pTemp == '\n'; pTemp++ ); + if ( pTemp[0] == '\0' ) + continue; +// if ( pTemp[0] == 'a' || pTemp[2] == 'a' ) +// { +// pLib->nLines--; +// continue; +// } + + // get the gate + pGate = Map_LibraryReadGateTree( pLib, pTemp, nCounter, pLib->nVarsMax ); + if ( pGate == NULL ) + { + Extra_ProgressBarStop( pProgress ); + return 0; + } + pLib->ppSupers[nCounter++] = pGate; + // later we will derive: truth table, delays, area, number of component gates, etc + + // update the progress bar + Extra_ProgressBarUpdate( pProgress, nCounter, NULL ); + } + Extra_ProgressBarStop( pProgress ); + if ( nCounter != pLib->nLines ) + printf( "The number of lines read (%d) is different what the file says (%d).\n", nCounter, pLib->nLines ); + pLib->nSupersAll = nCounter; + // count the number of real supergates + nCounter = 0; + for ( k = 0; k < pLib->nLines; k++ ) + nCounter += pLib->ppSupers[k]->fSuper; + if ( nCounter != pLib->nSupersReal ) + printf( "The number of gates read (%d) is different what the file says (%d).\n", nCounter, pLib->nSupersReal ); + pLib->nSupersReal = nCounter; + return 1; +} + +/**Function************************************************************* + + Synopsis [Reads one gate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Super_t * Map_LibraryReadGateTree( Map_SuperLib_t * pLib, char * pBuffer, int Number, int nVarsMax ) +{ + Map_Super_t * pGate; + char * pTemp; + int i, Num; + + // start and clean the gate + pGate = (Map_Super_t *)Extra_MmFixedEntryFetch( pLib->mmSupers ); + memset( pGate, 0, sizeof(Map_Super_t) ); + + // set the gate number + pGate->Num = Number; + + // read the mark + pTemp = strtok( pBuffer, " " ); + if ( pTemp[0] == '*' ) + { + pGate->fSuper = 1; + pTemp = strtok( NULL, " " ); + } + + // read the root gate + pGate->pRoot = Mio_LibraryReadGateByName( pLib->pGenlib, pTemp ); + if ( pGate->pRoot == NULL ) + { + printf( "Cannot read the root gate names %s.\n", pTemp ); + return NULL; + } + // set the max number of fanouts + pGate->nFanLimit = s_MapFanoutLimits[ Mio_GateReadInputs(pGate->pRoot) ]; + + // read the pin-to-pin delay + for ( i = 0; ( pTemp = strtok( NULL, " \n\0" ) ); i++ ) + { + if ( pTemp[0] == '#' ) + break; + if ( i == nVarsMax ) + { + printf( "There are too many entries on the line.\n" ); + return NULL; + } + Num = atoi(pTemp); + if ( Num < 0 ) + { + printf( "The number of a child supergate is negative.\n" ); + return NULL; + } + if ( Num > pLib->nLines ) + { + printf( "The number of a child supergate (%d) exceeded the number of lines (%d).\n", + Num, pLib->nLines ); + return NULL; + } + pGate->pFanins[i] = pLib->ppSupers[Num]; + } + pGate->nFanins = i; + if ( pGate->nFanins != (unsigned)Mio_GateReadInputs(pGate->pRoot) ) + { + printf( "The number of fanins of a root gate is wrong.\n" ); + return NULL; + } + + // save the gate name, just in case + if ( pTemp && pTemp[0] == '#' ) + { + if ( pTemp[1] == 0 ) + pTemp = strtok( NULL, " \n\0" ); + else // skip spaces + for ( pTemp++; *pTemp == ' '; pTemp++ ); + // save the formula + pGate->pFormula = Extra_MmFlexEntryFetch( pLib->mmForms, strlen(pTemp)+1 ); + strcpy( pGate->pFormula, pTemp ); + } + // check the rest of the string + pTemp = strtok( NULL, " \n\0" ); + if ( pTemp != NULL ) + printf( "The following trailing symbols found \"%s\".\n", pTemp ); + return pGate; +} + + +/**Function************************************************************* + + Synopsis [Derives information about the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryDeriveGateInfo( Map_SuperLib_t * pLib, st_table * tExcludeGate ) +{ + Map_Super_t * pGate, * pFanin; + Mio_Pin_t * pPin; + unsigned uCanon[2]; + unsigned uTruths[6][2]; + int i, k, nRealVars; + + // set all the derivable info related to the supergates + for ( i = pLib->nVarsMax; i < (int)pLib->nLines; i++ ) + { + pGate = pLib->ppSupers[i]; + + if ( tExcludeGate ) + { + if ( st_is_member( tExcludeGate, Mio_GateReadName( pGate->pRoot ) ) ) + pGate->fExclude = 1; + for ( k = 0; k < (int)pGate->nFanins; k++ ) + { + pFanin = pGate->pFanins[k]; + if ( pFanin->fExclude ) + { + pGate->fExclude = 1; + continue; + } + } + } + + // collect the truth tables of the fanins + for ( k = 0; k < (int)pGate->nFanins; k++ ) + { + pFanin = pGate->pFanins[k]; + uTruths[k][0] = pFanin->uTruth[0]; + uTruths[k][1] = pFanin->uTruth[1]; + } + // derive the new truth table + Mio_DeriveTruthTable( pGate->pRoot, uTruths, pGate->nFanins, 6, pGate->uTruth ); + + // set the initial delays of the supergate + for ( k = 0; k < pLib->nVarsMax; k++ ) + { + pGate->tDelaysR[k].Rise = pGate->tDelaysR[k].Fall = MAP_NO_VAR; + pGate->tDelaysF[k].Rise = pGate->tDelaysF[k].Fall = MAP_NO_VAR; + } + // get the linked list of pins for the given root gate + pPin = Mio_GateReadPins( pGate->pRoot ); + // update the initial delay of the supergate using info from the corresponding pin + for ( k = 0; k < (int)pGate->nFanins; k++, pPin = Mio_PinReadNext(pPin) ) + { + // if there is no corresponding pin, this is a bug, return fail + if ( pPin == NULL ) + { + printf( "There are less pins than gate inputs.\n" ); + return 0; + } + // update the delay information of k-th fanins info from the corresponding pin + Map_LibraryAddFaninDelays( pLib, pGate, pGate->pFanins[k], pPin ); + } + // if there are some pins left, this is a bug, return fail + if ( pPin != NULL ) + { + printf( "There are more pins than gate inputs.\n" ); + return 0; + } + // find the max delay + pGate->tDelayMax.Rise = pGate->tDelayMax.Fall = MAP_NO_VAR; + for ( k = 0; k < pLib->nVarsMax; k++ ) + { + // the rise of the output depends on the rise and fall of the output + if ( pGate->tDelayMax.Rise < pGate->tDelaysR[k].Rise ) + pGate->tDelayMax.Rise = pGate->tDelaysR[k].Rise; + if ( pGate->tDelayMax.Rise < pGate->tDelaysR[k].Fall ) + pGate->tDelayMax.Rise = pGate->tDelaysR[k].Fall; + // the fall of the output depends on the rise and fall of the output + if ( pGate->tDelayMax.Fall < pGate->tDelaysF[k].Rise ) + pGate->tDelayMax.Fall = pGate->tDelaysF[k].Rise; + if ( pGate->tDelayMax.Fall < pGate->tDelaysF[k].Fall ) + pGate->tDelayMax.Fall = pGate->tDelaysF[k].Fall; + } + + // count gates and area of the supergate + pGate->nGates = 1; + pGate->Area = (float)Mio_GateReadArea(pGate->pRoot); + for ( k = 0; k < (int)pGate->nFanins; k++ ) + { + pGate->nGates += pGate->pFanins[k]->nGates; + pGate->Area += pGate->pFanins[k]->Area; + } + // do not add the gate to the table, if this gate is an internal gate + // of some supegate and does not correspond to a supergate output + if ( ( !pGate->fSuper ) || pGate->fExclude ) + continue; + + // find the maximum index of a variable in the support of the supergates + // this is important for two reasons: + // (1) to limit the number of permutations considered for canonicization + // (2) to get rid of equivalence phases to speed-up matching + nRealVars = Map_LibraryGetMaxSuperPi_rec( pGate ) + 1; + assert( nRealVars > 0 && nRealVars <= pLib->nVarsMax ); + // if there are some problems with this code, try this instead +// nRealVars = pLib->nVarsMax; + + // find the N-canonical form of this supergate + pGate->nPhases = Map_CanonComputeSlow( pLib->uTruths, pLib->nVarsMax, nRealVars, pGate->uTruth, pGate->uPhases, uCanon ); + // add the supergate into the table by its N-canonical table + Map_SuperTableInsertC( pLib->tTableC, uCanon, pGate ); + } + // sort the gates in each line + Map_SuperTableSortSupergatesByDelay( pLib->tTableC, pLib->nSupersAll ); + + // let the glory be manifest +// Map_LibraryPrintTree( pLib ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Finds the largest PI number in the support of the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_LibraryGetMaxSuperPi_rec( Map_Super_t * pGate ) +{ + int i, VarCur, VarMax = 0; + if ( pGate->pRoot == NULL ) + return pGate->Num; + for ( i = 0; i < (int)pGate->nFanins; i++ ) + { + VarCur = Map_LibraryGetMaxSuperPi_rec( pGate->pFanins[i] ); + if ( VarMax < VarCur ) + VarMax = VarCur; + } + return VarMax; +} + +/**Function************************************************************* + + Synopsis [Finds the largest PI number in the support of the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_LibraryGetGateSupp_rec( Map_Super_t * pGate ) +{ + unsigned uSupport; + int i; + if ( pGate->pRoot == NULL ) + return (unsigned)(1 << (pGate->Num)); + uSupport = 0; + for ( i = 0; i < (int)pGate->nFanins; i++ ) + uSupport |= Map_LibraryGetGateSupp_rec( pGate->pFanins[i] ); + return uSupport; +} + +/**Function************************************************************* + + Synopsis [Derives the pin-to-pin delay constraints for the supergate.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryAddFaninDelays( Map_SuperLib_t * pLib, Map_Super_t * pGate, Map_Super_t * pFanin, Mio_Pin_t * pPin ) +{ + Mio_PinPhase_t PinPhase; + float tDelayBlockRise, tDelayBlockFall, tDelayPin; + bool fMaxDelay = 0; + int i; + + // use this node to enable max-delay model + if ( fMaxDelay ) + { + float tDelayBlockMax; + // get the maximum delay + tDelayBlockMax = (float)Mio_PinReadDelayBlockMax(pPin); + // go through the supergate inputs + for ( i = 0; i < pLib->nVarsMax; i++ ) + { + if ( pFanin->tDelaysR[i].Rise < 0 ) + continue; + tDelayPin = pFanin->tDelaysR[i].Rise + tDelayBlockMax; + if ( pGate->tDelaysR[i].Rise < tDelayPin ) + pGate->tDelaysR[i].Rise = tDelayPin; + } + // go through the supergate inputs + for ( i = 0; i < pLib->nVarsMax; i++ ) + { + if ( pFanin->tDelaysF[i].Fall < 0 ) + continue; + tDelayPin = pFanin->tDelaysF[i].Fall + tDelayBlockMax; + if ( pGate->tDelaysF[i].Fall < tDelayPin ) + pGate->tDelaysF[i].Fall = tDelayPin; + } + return; + } + + // get the interesting parameters of this pin + PinPhase = Mio_PinReadPhase(pPin); + tDelayBlockRise = (float)Mio_PinReadDelayBlockRise( pPin ); + tDelayBlockFall = (float)Mio_PinReadDelayBlockFall( pPin ); + + // update the rise and fall of the output depending on the phase of the pin + if ( PinPhase != MIO_PHASE_INV ) // NONINV phase is present + { + // the rise of the gate is determined by the rise of the fanin + // the fall of the gate is determined by the fall of the fanin + for ( i = 0; i < pLib->nVarsMax; i++ ) + { + //////////////////////////////////////////////////////// + // consider the rise of the gate + //////////////////////////////////////////////////////// + // check two types of constraints on the rise of the fanin: + // (1) the constraints related to the rise of the PIs + // (2) the constraints related to the fall of the PIs + if ( pFanin->tDelaysR[i].Rise >= 0 ) // case (1) + { // fanin's rise depends on the rise of i-th PI + // update the rise of the gate's output + if ( pGate->tDelaysR[i].Rise < pFanin->tDelaysR[i].Rise + tDelayBlockRise ) + pGate->tDelaysR[i].Rise = pFanin->tDelaysR[i].Rise + tDelayBlockRise; + } + if ( pFanin->tDelaysR[i].Fall >= 0 ) // case (2) + { // fanin's rise depends on the fall of i-th PI + // update the rise of the gate's output + if ( pGate->tDelaysR[i].Fall < pFanin->tDelaysR[i].Fall + tDelayBlockRise ) + pGate->tDelaysR[i].Fall = pFanin->tDelaysR[i].Fall + tDelayBlockRise; + } + //////////////////////////////////////////////////////// + + //////////////////////////////////////////////////////// + // consider the fall of the gate (similar) + //////////////////////////////////////////////////////// + // check two types of constraints on the fall of the fanin: + // (1) the constraints related to the rise of the PIs + // (2) the constraints related to the fall of the PIs + if ( pFanin->tDelaysF[i].Rise >= 0 ) // case (1) + { + if ( pGate->tDelaysF[i].Rise < pFanin->tDelaysF[i].Rise + tDelayBlockFall ) + pGate->tDelaysF[i].Rise = pFanin->tDelaysF[i].Rise + tDelayBlockFall; + } + if ( pFanin->tDelaysF[i].Fall >= 0 ) // case (2) + { + if ( pGate->tDelaysF[i].Fall < pFanin->tDelaysF[i].Fall + tDelayBlockFall ) + pGate->tDelaysF[i].Fall = pFanin->tDelaysF[i].Fall + tDelayBlockFall; + } + //////////////////////////////////////////////////////// + } + } + if ( PinPhase != MIO_PHASE_NONINV ) // INV phase is present + { + // the rise of the gate is determined by the fall of the fanin + // the fall of the gate is determined by the rise of the fanin + for ( i = 0; i < pLib->nVarsMax; i++ ) + { + //////////////////////////////////////////////////////// + // consider the rise of the gate's output + //////////////////////////////////////////////////////// + // check two types of constraints on the fall of the fanin: + // (1) the constraints related to the rise of the PIs + // (2) the constraints related to the fall of the PIs + if ( pFanin->tDelaysF[i].Rise >= 0 ) // case (1) + { // fanin's rise depends on the rise of i-th PI + // update the rise of the gate + if ( pGate->tDelaysR[i].Rise < pFanin->tDelaysF[i].Rise + tDelayBlockRise ) + pGate->tDelaysR[i].Rise = pFanin->tDelaysF[i].Rise + tDelayBlockRise; + } + if ( pFanin->tDelaysF[i].Fall >= 0 ) // case (2) + { // fanin's rise depends on the fall of i-th PI + // update the rise of the gate + if ( pGate->tDelaysR[i].Fall < pFanin->tDelaysF[i].Fall + tDelayBlockRise ) + pGate->tDelaysR[i].Fall = pFanin->tDelaysF[i].Fall + tDelayBlockRise; + } + //////////////////////////////////////////////////////// + + //////////////////////////////////////////////////////// + // consider the fall of the gate (similar) + //////////////////////////////////////////////////////// + // check two types of constraints on the rise of the fanin: + // (1) the constraints related to the rise of the PIs + // (2) the constraints related to the fall of the PIs + if ( pFanin->tDelaysR[i].Rise >= 0 ) // case (1) + { + if ( pGate->tDelaysF[i].Rise < pFanin->tDelaysR[i].Rise + tDelayBlockFall ) + pGate->tDelaysF[i].Rise = pFanin->tDelaysR[i].Rise + tDelayBlockFall; + } + if ( pFanin->tDelaysR[i].Fall >= 0 ) // case (2) + { + if ( pGate->tDelaysF[i].Fall < pFanin->tDelaysR[i].Fall + tDelayBlockFall ) + pGate->tDelaysF[i].Fall = pFanin->tDelaysR[i].Fall + tDelayBlockFall; + } + //////////////////////////////////////////////////////// + } + } +} + + +/**Function************************************************************* + + Synopsis [Performs phase transformation for one function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_CalculatePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase ) +{ + int v, Shift; + for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 ) + if ( uPhase & Shift ) + uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift)); + return uTruth; +} + +/**Function************************************************************* + + Synopsis [Performs phase transformation for one function.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_CalculatePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] ) +{ + unsigned uTemp; + int v, Shift; + + // initialize the result + uTruthRes[0] = uTruth[0]; + uTruthRes[1] = uTruth[1]; + if ( uPhase == 0 ) + return; + // compute the phase + for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 ) + if ( uPhase & Shift ) + { + if ( Shift < 32 ) + { + uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift)); + uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift)); + } + else + { + uTemp = uTruthRes[0]; + uTruthRes[0] = uTruthRes[1]; + uTruthRes[1] = uTemp; + } + } +} + +/**Function************************************************************* + + Synopsis [Prints the supergate library after deriving parameters.] + + Description [This procedure is very useful to see the library after + it has been read into the mapper by "read_super" and all the information + about the supergates derived.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_LibraryPrintTree( Map_SuperLib_t * pLib ) +{ + Map_Super_t * pGate; + int i, k; + + // print all the info related to the supergates +// for ( i = pLib->nVarsMax; i < (int)pLib->nLines; i++ ) + for ( i = pLib->nVarsMax; i < 20; i++ ) + { + pGate = pLib->ppSupers[i]; + + // write the gate's fanin info and formula + printf( "%6d ", pGate->Num ); + printf( "%c ", pGate->fSuper? '*' : ' ' ); + printf( "%6s", Mio_GateReadName(pGate->pRoot) ); + for ( k = 0; k < (int)pGate->nFanins; k++ ) + printf( " %6d", pGate->pFanins[k]->Num ); + printf( " %s", pGate->pFormula ); + printf( "\n" ); + + // write the gate's derived info + Extra_PrintBinary( stdout, pGate->uTruth, 64 ); + printf( " %3d", pGate->nGates ); + printf( " %6.2f", pGate->Area ); + printf( " (%4.2f, %4.2f)", pGate->tDelayMax.Rise, pGate->tDelayMax.Fall ); + printf( "\n" ); + for ( k = 0; k < pLib->nVarsMax; k++ ) + { + // print the constraint on the rise of the gate in the form (D1, D2), + // where D1 is the constraint related to the rise of the k-th PI + // where D2 is the constraint related to the fall of the k-th PI + if ( pGate->tDelaysR[k].Rise < 0 && pGate->tDelaysR[k].Fall < 0 ) + printf( " (----, ----)" ); + else if ( pGate->tDelaysR[k].Fall < 0 ) + printf( " (%4.2f, ----)", pGate->tDelaysR[k].Rise ); + else if ( pGate->tDelaysR[k].Rise < 0 ) + printf( " (----, %4.2f)", pGate->tDelaysR[k].Fall ); + else + printf( " (%4.2f, %4.2f)", pGate->tDelaysR[k].Rise, pGate->tDelaysR[k].Fall ); + + // print the constraint on the fall of the gate in the form (D1, D2), + // where D1 is the constraint related to the rise of the k-th PI + // where D2 is the constraint related to the fall of the k-th PI + if ( pGate->tDelaysF[k].Rise < 0 && pGate->tDelaysF[k].Fall < 0 ) + printf( " (----, ----)" ); + else if ( pGate->tDelaysF[k].Fall < 0 ) + printf( " (%4.2f, ----)", pGate->tDelaysF[k].Rise ); + else if ( pGate->tDelaysF[k].Rise < 0 ) + printf( " (----, %4.2f)", pGate->tDelaysF[k].Fall ); + else + printf( " (%4.2f, %4.2f)", pGate->tDelaysF[k].Rise, pGate->tDelaysF[k].Fall ); + printf( "\n" ); + } + printf( "\n" ); + } +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperTruth.c b/src/map/mapper/mapperTruth.c new file mode 100644 index 00000000..9388b42f --- /dev/null +++ b/src/map/mapper/mapperTruth.c @@ -0,0 +1,449 @@ +/**CFile**************************************************************** + + FileName [mapperTruth.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperTruth.c,v 1.8 2005/01/23 06:59:45 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//static void Map_TruthsCutDcs( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] ); +static void Map_TruthsCut( Map_Man_t * pMan, Map_Cut_t * pCut ); +static void Map_TruthsCut_rec( Map_Cut_t * pCut, unsigned uTruth[] ); +static void Map_TruthsUnmark_rec( Map_Cut_t * pCut ); + +/* +static int s_Same = 0; +static int s_Diff = 0; +static int s_Same2 = 0; +static int s_Diff2 = 0; +static int s_Truth = 0; +static int s_Isop1 = 0; +static int s_Isop2 = 0; +*/ +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Derives truth tables for each cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingTruths( Map_Man_t * pMan ) +{ + ProgressBar * pProgress; + Map_Node_t * pNode; + Map_Cut_t * pCut; + int nNodes, i; + // compute the cuts for the POs + nNodes = pMan->vAnds->nSize; + pProgress = Extra_ProgressBarStart( stdout, nNodes ); + for ( i = 0; i < nNodes; i++ ) + { + pNode = pMan->vAnds->pArray[i]; + if ( !Map_NodeIsAnd( pNode ) ) + continue; + assert( pNode->pCuts ); + assert( pNode->pCuts->nLeaves == 1 ); + + // match the simple cut + pNode->pCuts->M[0].uPhase = 0; + pNode->pCuts->M[0].pSupers = pMan->pSuperLib->pSuperInv; + pNode->pCuts->M[0].uPhaseBest = 0; + pNode->pCuts->M[0].pSuperBest = pMan->pSuperLib->pSuperInv; + + pNode->pCuts->M[1].uPhase = 0; + pNode->pCuts->M[1].pSupers = pMan->pSuperLib->pSuperInv; + pNode->pCuts->M[1].uPhaseBest = 1; + pNode->pCuts->M[1].pSuperBest = pMan->pSuperLib->pSuperInv; + + // match the rest of the cuts + for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext ) + Map_TruthsCut( pMan, pCut ); + Extra_ProgressBarUpdate( pProgress, i, "Tables ..." ); + } + Extra_ProgressBarStop( pProgress ); + +// printf( "Same = %6d. Diff = %6d.\n", s_Same, s_Diff ); +// printf( "Same2 = %6d. Diff2 = %6d.\n", s_Same2, s_Diff2 ); +// printf( "Truth = %6d. Isop1 = %6d. Isop2 = %6d.\n", s_Truth, s_Isop1, s_Isop2 ); +} + +/**Function************************************************************* + + Synopsis [Derives the truth table for one cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut ) +{ + unsigned uTruth[2], uCanon[2]; + unsigned char uPhases[16]; + int i; + + // generally speaking, 1-input cut can be matched into a wire! + if ( pCut->nLeaves == 1 ) + return; + // set the leaf truth tables + for ( i = 0; i < pCut->nLeaves; i++ ) + { + pCut->ppLeaves[i]->pCuts->uTruthTemp[0] = p->uTruths[i][0]; + pCut->ppLeaves[i]->pCuts->uTruthTemp[1] = p->uTruths[i][1]; + } + // recursively compute the truth table + pCut->nVolume = 0; + Map_TruthsCut_rec( pCut, uTruth ); + // recursively unmark the visited cuts + Map_TruthsUnmark_rec( pCut ); + + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + + // restore the truth table + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + // enable don't-care computation +// Map_TruthsCutDcs( p, pCut, uTruth ); +} + +#if 0 + +/**Function************************************************************* + + Synopsis [Adds several other choices using SDCs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TruthsCutDcs( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] ) +{ + unsigned uIsop1[2], uIsop2[2], uCanon[2]; + unsigned char uPhases[16]; + + // add several other supergate classes derived using don't-cares + if ( pCut->uTruthDc[0] ) + { + int nOnes; + nOnes = Map_TruthCountOnes( pCut->uTruthDc, pCut->nLeaves ); + if ( nOnes == 1 ) + { + uTruth[0] ^= pCut->uTruthDc[0]; + uTruth[1] ^= pCut->uTruthDc[1]; + + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + } + else if ( nOnes == 2 ) + { + int Num1, Num2, RetValue; + RetValue = Map_TruthDetectTwoFirst( pCut->uTruthDc, pCut->nLeaves ); + Num1 = RetValue & 255; + Num2 = (RetValue >> 8) & 255; + + // add the first bit + Map_InfoFlipVar( uTruth, Num1 ); + + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + + // add the first bit + Map_InfoFlipVar( uTruth, Num2 ); + + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + + // add the first bit + Map_InfoFlipVar( uTruth, Num1 ); + + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uTruth[0] = ~uTruth[0]; + uTruth[1] = ~uTruth[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + } + else + { + // compute the ISOPs + uIsop1[0] = Map_ComputeIsop_rec( p, uTruth[0] & ~pCut->uTruthDc[0], uTruth[0] | pCut->uTruthDc[0], 0, pCut->nLeaves, 0 ); + uIsop1[1] = uIsop1[0]; + if ( uIsop1[0] != uTruth[0] ) + { + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uIsop1, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[1].uPhase = uPhases[0]; + p->nCanons++; + + // compute the canonical form for the negative phase + uIsop1[0] = ~uIsop1[0]; + uIsop1[1] = ~uIsop1[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uIsop1, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + } + + uIsop2[0] = Map_ComputeIsop_rec( p, uTruth[0] & ~pCut->uTruthDc[0], uTruth[0] | pCut->uTruthDc[0], pCut->nLeaves-1, pCut->nLeaves, 1 ); + uIsop2[1] = uIsop2[0]; + if ( uIsop2[0] != uTruth[0] && uIsop2[0] != uIsop1[0] ) + { + // compute the canonical form for the positive phase + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uIsop2, uPhases, uCanon ); + pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + p->nCanons++; + + // compute the canonical form for the negative phase + uIsop2[0] = ~uIsop2[0]; + uIsop2[1] = ~uIsop2[1]; + Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uIsop2, uPhases, uCanon ); + pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon ); + pCut->M[0].uPhase = uPhases[0]; + p->nCanons++; + } + } + } +} + +#endif + +/**Function************************************************************* + + Synopsis [Recursively derives the truth table for the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TruthsCut_rec( Map_Cut_t * pCut, unsigned uTruthRes[] ) +{ + unsigned uTruth1[2], uTruth2[2]; + // if this is the elementary cut, its truth table is already available + if ( pCut->nLeaves == 1 ) + { + uTruthRes[0] = pCut->uTruthTemp[0]; + uTruthRes[1] = pCut->uTruthTemp[1]; + return; + } + // if this node was already visited, return its computed truth table + if ( pCut->fMark ) + { + uTruthRes[0] = pCut->uTruthTemp[0]; + uTruthRes[1] = pCut->uTruthTemp[1]; + return; + } + pCut->fMark = 1; + pCut->nVolume++; + + assert( !Map_IsComplement(pCut) ); + Map_TruthsCut_rec( Map_CutRegular(pCut->pOne), uTruth1 ); + if ( Map_CutIsComplement(pCut->pOne) ) + { + uTruth1[0] = ~uTruth1[0]; + uTruth1[1] = ~uTruth1[1]; + } + Map_TruthsCut_rec( Map_CutRegular(pCut->pTwo), uTruth2 ); + if ( Map_CutIsComplement(pCut->pTwo) ) + { + uTruth2[0] = ~uTruth2[0]; + uTruth2[1] = ~uTruth2[1]; + } + if ( !pCut->Phase ) + { + uTruthRes[0] = pCut->uTruthTemp[0] = uTruth1[0] & uTruth2[0]; + uTruthRes[1] = pCut->uTruthTemp[1] = uTruth1[1] & uTruth2[1]; + } + else + { + uTruthRes[0] = pCut->uTruthTemp[0] = ~(uTruth1[0] & uTruth2[0]); + uTruthRes[1] = pCut->uTruthTemp[1] = ~(uTruth1[1] & uTruth2[1]); + } +} + +/**Function************************************************************* + + Synopsis [Recursively derives the truth table for the cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_TruthsUnmark_rec( Map_Cut_t * pCut ) +{ + if ( pCut->nLeaves == 1 ) + return; + // if this node was already visited, return its computed truth table + if ( pCut->fMark == 0 ) + return; + pCut->fMark = 0; + Map_TruthsUnmark_rec( Map_CutRegular(pCut->pOne) ); + Map_TruthsUnmark_rec( Map_CutRegular(pCut->pTwo) ); +} + +/**Function************************************************************* + + Synopsis [Returns the truth table of the don't-care set.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_TruthsCutDontCare( Map_Man_t * pMan, Map_Cut_t * pCut, unsigned * uTruthDc ) +{ + if ( pCut->pOne || (pCut->uTruthZero[0] == 0 && pCut->uTruthZero[1] == 0) ) + return 0; + assert( (pCut->uTruthTemp[0] & pCut->uTruthZero[0]) == 0 ); + assert( (pCut->uTruthTemp[1] & pCut->uTruthZero[1]) == 0 ); + uTruthDc[0] = ((~0) & (~pCut->uTruthTemp[0]) & (~pCut->uTruthZero[0])); + uTruthDc[1] = ((~0) & (~pCut->uTruthTemp[1]) & (~pCut->uTruthZero[1])); + if ( uTruthDc[0] == 0 && uTruthDc[1] == 0 ) + return 0; + return 1; +} + +/**Function************************************************************* + + Synopsis [Expand the truth table] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_TruthCountOnes( unsigned * uTruth, int nLeaves ) +{ + int i, nMints, Counter; + nMints = (1 << nLeaves); + Counter = 0; + for ( i = 0; i < nMints; i++ ) + Counter += Map_InfoReadVar( uTruth, i ); + return Counter; +} + +/**Function************************************************************* + + Synopsis [Expand the truth table] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_TruthDetectTwoFirst( unsigned * uTruth, int nLeaves ) +{ + int i, nMints, Num1 = -1, Num2 = -1; + nMints = (1 << nLeaves); + for ( i = 0; i < nMints; i++ ) + if ( Map_InfoReadVar( uTruth, i ) ) + { + if ( Num1 == -1 ) + Num1 = i; + else if ( Num2 == -1 ) + Num2 = i; + else + break; + } + assert( Num1 != -1 && Num2 != -1 ); + return (Num1 << 8) | Num2; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperUtils.c b/src/map/mapper/mapperUtils.c new file mode 100644 index 00000000..f8fd1a4c --- /dev/null +++ b/src/map/mapper/mapperUtils.c @@ -0,0 +1,1254 @@ +/**CFile**************************************************************** + + FileName [mapperUtils.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperUtils.c,v 1.8 2004/11/03 22:41:45 satrajit Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Map_MappingDfs_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fCollectEquiv ); +static int Map_MappingCountLevels_rec( Map_Node_t * pNode ); +static float Map_MappingSetRefsAndArea_rec( Map_Man_t * pMan, Map_Node_t * pNode ); +static float Map_MappingSetRefsAndSwitch_rec( Map_Man_t * pMan, Map_Node_t * pNode ); +static float Map_MappingSetRefsAndWire_rec( Map_Man_t * pMan, Map_Node_t * pNode ); +static void Map_MappingDfsCuts_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes ); +static float Map_MappingArea_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_NodeVec_t * vNodes ); +static int Map_MappingCompareOutputDelay( int * pOut1, int * pOut2 ); +static unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars ); +static void Map_MappingGetChoiceLevels( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2, int * pMin, int * pMax ); +static float Map_MappingGetChoiceVolumes( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2 ); +static int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices ); +static Map_Man_t * s_pMan = NULL; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_NodeVec_t * Map_MappingDfs( Map_Man_t * pMan, int fCollectEquiv ) +{ + Map_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Map_NodeVecAlloc( 100 ); + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingDfs_rec( Map_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; +// for ( i = 0; i < pMan->nOutputs; i++ ) +// Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_NodeVec_t * Map_MappingDfsNodes( Map_Man_t * pMan, Map_Node_t ** ppCuts, int nNodes, int fEquiv ) +{ + Map_NodeVec_t * vNodes; + int i; + // perform the traversal + vNodes = Map_NodeVecAlloc( 200 ); + for ( i = 0; i < nNodes; i++ ) + Map_MappingDfs_rec( ppCuts[i], vNodes, fEquiv ); + for ( i = 0; i < vNodes->nSize; i++ ) + vNodes->pArray[i]->fMark0 = 0; + return vNodes; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingDfs_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fCollectEquiv ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark0 ) + return; + // visit the transitive fanin + if ( Map_NodeIsAnd(pNode) ) + { + Map_MappingDfs_rec( Map_Regular(pNode->p1), vNodes, fCollectEquiv ); + Map_MappingDfs_rec( Map_Regular(pNode->p2), vNodes, fCollectEquiv ); + } + // visit the equivalent nodes + if ( fCollectEquiv && pNode->pNextE ) + Map_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv ); + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + Map_NodeVecPush( vNodes, pNode ); +} + + + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingDfsMarked1_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fFirst ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark0 ) + return; + // visit the transitive fanin + if ( Map_NodeIsAnd(pNode) ) + { + Map_MappingDfsMarked1_rec( Map_Regular(pNode->p1), vNodes, 0 ); + Map_MappingDfsMarked1_rec( Map_Regular(pNode->p2), vNodes, 0 ); + } + // visit the equivalent nodes + if ( !fFirst && pNode->pNextE ) + Map_MappingDfsMarked1_rec( pNode->pNextE, vNodes, 0 ); + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + Map_NodeVecPush( vNodes, pNode ); +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingDfsMarked2_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, Map_NodeVec_t * vBoundary, int fFirst ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark1 ) + return; + if ( pNode->fMark0 || Map_NodeIsVar(pNode) ) + { + pNode->fMark1 = 1; + Map_NodeVecPush(vBoundary, pNode); + return; + } + // visit the transitive fanin + if ( Map_NodeIsAnd(pNode) ) + { + Map_MappingDfsMarked2_rec( Map_Regular(pNode->p1), vNodes, vBoundary, 0 ); + Map_MappingDfsMarked2_rec( Map_Regular(pNode->p2), vNodes, vBoundary, 0 ); + } + // visit the equivalent nodes + if ( !fFirst && pNode->pNextE ) + Map_MappingDfsMarked2_rec( pNode->pNextE, vNodes, vBoundary, 0 ); + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark1 == 0 ); + // mark the node as visited + pNode->fMark1 = 1; + // add the node to the list + Map_NodeVecPush( vNodes, pNode ); +} + + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingDfsMarked3_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark0 ) + return; + // visit the transitive fanin + if ( Map_NodeIsAnd(pNode) ) + { + Map_MappingDfsMarked3_rec( Map_Regular(pNode->p1), vNodes ); + Map_MappingDfsMarked3_rec( Map_Regular(pNode->p2), vNodes ); + } + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark0 == 0 ); + // mark the node as visited + pNode->fMark0 = 1; + // add the node to the list + Map_NodeVecPush( vNodes, pNode ); +} + +/**Function************************************************************* + + Synopsis [Recursively computes the DFS ordering of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingDfsMarked4_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark1 ) + return; + // visit the transitive fanin + if ( Map_NodeIsAnd(pNode) ) + { + Map_MappingDfsMarked4_rec( Map_Regular(pNode->p1), vNodes ); + Map_MappingDfsMarked4_rec( Map_Regular(pNode->p2), vNodes ); + } + // make sure the node is not visited through the equivalent nodes + assert( pNode->fMark1 == 0 ); + // mark the node as visited + pNode->fMark1 = 1; + // add the node to the list + Map_NodeVecPush( vNodes, pNode ); +} + + + +/**Function************************************************************* + + Synopsis [Computes the number of logic levels not counting PIs/POs.] + + Description [] + + SideEffects [Note that this procedure will reassign the levels assigned + originally by NodeCreate() because it counts the number of levels with + choices differently!] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCountLevels( Map_Man_t * pMan ) +{ + int i, LevelsMax, LevelsCur; + // perform the traversal + LevelsMax = -1; + for ( i = 0; i < pMan->nOutputs; i++ ) + { + LevelsCur = Map_MappingCountLevels_rec( Map_Regular(pMan->pOutputs[i]) ); + if ( LevelsMax < LevelsCur ) + LevelsMax = LevelsCur; + } + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); + return LevelsMax; +} + +/**Function************************************************************* + + Synopsis [Recursively computes the number of logic levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCountLevels_rec( Map_Node_t * pNode ) +{ + int Level1, Level2; + assert( !Map_IsComplement(pNode) ); + if ( !Map_NodeIsAnd(pNode) ) + { + pNode->Level = 0; + return 0; + } + if ( pNode->fMark0 ) + return pNode->Level; + pNode->fMark0 = 1; + // visit the transitive fanin + Level1 = Map_MappingCountLevels_rec( Map_Regular(pNode->p1) ); + Level2 = Map_MappingCountLevels_rec( Map_Regular(pNode->p2) ); + // set the number of levels + pNode->Level = 1 + ((Level1>Level2)? Level1: Level2); + return pNode->Level; +} + +/**Function************************************************************* + + Synopsis [Unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingUnmark( Map_Man_t * pMan ) +{ + int i; + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); +} + +/**Function************************************************************* + + Synopsis [Recursively unmarks the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingUnmark_rec( Map_Node_t * pNode ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark0 == 0 ) + return; + pNode->fMark0 = 0; + if ( !Map_NodeIsAnd(pNode) ) + return; + Map_MappingUnmark_rec( Map_Regular(pNode->p1) ); + Map_MappingUnmark_rec( Map_Regular(pNode->p2) ); + // visit the equivalent nodes + if ( pNode->pNextE ) + Map_MappingUnmark_rec( pNode->pNextE ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingMark_rec( Map_Node_t * pNode ) +{ + assert( !Map_IsComplement(pNode) ); + if ( pNode->fMark0 == 1 ) + return; + pNode->fMark0 = 1; + if ( !Map_NodeIsAnd(pNode) ) + return; + // visit the transitive fanin of the selected cut + Map_MappingMark_rec( Map_Regular(pNode->p1) ); + Map_MappingMark_rec( Map_Regular(pNode->p2) ); +} + +/**Function************************************************************* + + Synopsis [Prints a bunch of latest arriving outputs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingPrintOutputArrivals( Map_Man_t * p ) +{ + Map_Time_t * pTimes; + Map_Node_t * pNode; + int fPhase, Limit, i; + int nOutputs; + int * pSorted; + + // sort outputs by arrival time + s_pMan = p; + pSorted = ALLOC( int, p->nOutputs ); + nOutputs = 0; + for ( i = 0; i < p->nOutputs; i++ ) + { + if ( Map_NodeIsConst(p->pOutputs[i]) ) + continue; + pSorted[nOutputs++] = i; + } + qsort( (void *)pSorted, nOutputs, sizeof(int), + (int (*)(const void *, const void *)) Map_MappingCompareOutputDelay ); + assert( Map_MappingCompareOutputDelay( pSorted, pSorted + nOutputs - 1 ) <= 0 ); + s_pMan = NULL; + + // print the latest outputs + Limit = (nOutputs > 5)? 5 : nOutputs; + for ( i = 0; i < Limit; i++ ) + { + // get the i-th latest output + pNode = Map_Regular(p->pOutputs[pSorted[i]]); + fPhase =!Map_IsComplement(p->pOutputs[pSorted[i]]); + pTimes = pNode->tArrival + fPhase; + // print out the best arrival time + printf( "Out %20s : ", p->ppOutputNames[pSorted[i]] ); + printf( "Delay = (%5.2f, %5.2f) ", (double)pTimes->Rise, (double)pTimes->Fall ); + printf( "%s", fPhase? "POS" : "NEG" ); + printf( "\n" ); + } + free( pSorted ); +} + +/**Function************************************************************* + + Synopsis [Compares the outputs by their arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCompareOutputDelay( int * pOut1, int * pOut2 ) +{ + Map_Node_t * pNode1 = Map_Regular(s_pMan->pOutputs[*pOut1]); + Map_Node_t * pNode2 = Map_Regular(s_pMan->pOutputs[*pOut2]); + int fPhase1 = (pNode1 == s_pMan->pOutputs[*pOut1]); + int fPhase2 = (pNode2 == s_pMan->pOutputs[*pOut2]); + float Arrival1 = pNode1->tArrival[fPhase1].Worst; + float Arrival2 = pNode2->tArrival[fPhase2].Worst; + if ( Arrival1 > Arrival2 ) + return -1; + if ( Arrival1 < Arrival2 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Sets up the truth tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetupTruthTables( unsigned uTruths[][2] ) +{ + int m, v; + // set up the truth tables + for ( m = 0; m < 32; m++ ) + for ( v = 0; v < 5; v++ ) + if ( m & (1 << v) ) + uTruths[v][0] |= (1 << m); + // make adjustments for the case of 6 variables + for ( v = 0; v < 5; v++ ) + uTruths[v][1] = uTruths[v][0]; + uTruths[5][0] = 0; + uTruths[5][1] = MAP_FULL; +} + +/**Function************************************************************* + + Synopsis [Sets up the truth tables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetupTruthTablesLarge( unsigned uTruths[][32] ) +{ + int m, v; + // clean everything + for ( m = 0; m < 32; m++ ) + for ( v = 0; v < 10; v++ ) + uTruths[v][m] = 0; + // set up the truth tables + for ( m = 0; m < 32; m++ ) + for ( v = 0; v < 5; v++ ) + if ( m & (1 << v) ) + { + uTruths[v][0] |= (1 << m); + uTruths[v+5][m] = MAP_FULL; + } + // extend this info for the rest of the first 5 variables + for ( m = 0; m < 32; m++ ) + for ( v = 0; v < 5; v++ ) + uTruths[v][m] = uTruths[v][0]; +/* + // verify + for ( m = 0; m < 1024; m++, printf("\n") ) + for ( v = 0; v < 10; v++ ) + if ( Map_InfoReadVar( uTruths[v], m ) ) + printf( "1" ); + else + printf( "0" ); +*/ +} + +/**Function************************************************************* + + Synopsis [Sets up the mask.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetupMask( unsigned uMask[], int nVarsMax ) +{ + if ( nVarsMax == 6 ) + uMask[0] = uMask[1] = MAP_FULL; + else + { + uMask[0] = MAP_MASK(1 << nVarsMax); + uMask[1] = 0; + } +} + +/**Function************************************************************* + + Synopsis [Verify one useful property.] + + Description [This procedure verifies one useful property. After + the FRAIG construction with choice nodes is over, each primary node + should have fanins that are primary nodes. The primary nodes is the + one that does not have pNode->pRepr set to point to another node.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_ManCheckConsistency( Map_Man_t * p ) +{ + Map_Node_t * pNode; + Map_NodeVec_t * pVec; + int i; + pVec = Map_MappingDfs( p, 0 ); + for ( i = 0; i < pVec->nSize; i++ ) + { + pNode = pVec->pArray[i]; + if ( Map_NodeIsVar(pNode) ) + { + if ( pNode->pRepr ) + printf( "Primary input %d is a secondary node.\n", pNode->Num ); + } + else if ( Map_NodeIsConst(pNode) ) + { + if ( pNode->pRepr ) + printf( "Constant 1 %d is a secondary node.\n", pNode->Num ); + } + else + { + if ( pNode->pRepr ) + printf( "Internal node %d is a secondary node.\n", pNode->Num ); + if ( Map_Regular(pNode->p1)->pRepr ) + printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num ); + if ( Map_Regular(pNode->p2)->pRepr ) + printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num ); + } + } + Map_NodeVecFree( pVec ); + return 1; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if current mapping of the node violates fanout limits.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingNodeIsViolator( Map_Node_t * pNode, Map_Cut_t * pCut, int fPosPol ) +{ + return pNode->nRefAct[fPosPol] > (int)pCut->M[fPosPol].pSuperBest->nFanLimit; +} + +/**Function************************************************************* + + Synopsis [Computes the total are flow of the network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_MappingGetAreaFlow( Map_Man_t * p ) +{ + Map_Node_t * pNode; + Map_Cut_t * pCut; + float aFlowFlowTotal = 0; + int fPosPol, i; + for ( i = 0; i < p->nOutputs; i++ ) + { + pNode = Map_Regular(p->pOutputs[i]); + if ( !Map_NodeIsAnd(pNode) ) + continue; + fPosPol = !Map_IsComplement(p->pOutputs[i]); + pCut = pNode->pCutBest[fPosPol]; + if ( pCut == NULL ) + { + fPosPol = !fPosPol; + pCut = pNode->pCutBest[fPosPol]; + } + aFlowFlowTotal += pNode->pCutBest[fPosPol]->M[fPosPol].AreaFlow; + } + return aFlowFlowTotal; +} + + +/**Function************************************************************* + + Synopsis [Compares the supergates by their level.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CompareNodesByLevel( Map_Node_t ** ppS1, Map_Node_t ** ppS2 ) +{ + Map_Node_t * pN1 = Map_Regular(*ppS1); + Map_Node_t * pN2 = Map_Regular(*ppS2); + if ( pN1->Level > pN2->Level ) + return -1; + if ( pN1->Level < pN2->Level ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Orders the nodes in the decreasing order of levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSortByLevel( Map_Man_t * pMan, Map_NodeVec_t * vNodes ) +{ + qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Map_Node_t *), + (int (*)(const void *, const void *)) Map_CompareNodesByLevel ); +// assert( Map_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 ); +} + + +/**Function************************************************************* + + Synopsis [Compares the supergates by their pointer.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_CompareNodesByPointer( Map_Node_t ** ppS1, Map_Node_t ** ppS2 ) +{ + if ( *ppS1 < *ppS2 ) + return -1; + if ( *ppS1 > *ppS2 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Counts how many AIG nodes are mapped in both polarities.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCountDoubles( Map_Man_t * pMan, Map_NodeVec_t * vNodes ) +{ + Map_Node_t * pNode; + int Counter, i; + // count the number of equal adjacent nodes + Counter = 0; + for ( i = 0; i < vNodes->nSize; i++ ) + { + pNode = vNodes->pArray[i]; + if ( !Map_NodeIsAnd(pNode) ) + continue; + if ( (pNode->nRefAct[0] && pNode->pCutBest[0]) && + (pNode->nRefAct[1] && pNode->pCutBest[1]) ) + Counter++; + } + return Counter; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +st_table * Map_CreateTableGate2Super( Map_Man_t * pMan ) +{ + Map_Super_t * pSuper; + st_table * tTable; + int i, nInputs, v; + tTable = st_init_table(strcmp, st_strhash); + for ( i = 0; i < pMan->pSuperLib->nSupersAll; i++ ) + { + pSuper = pMan->pSuperLib->ppSupers[i]; + if ( pSuper->nGates == 1 ) + { + // skip different versions of the same root gate + nInputs = Mio_GateReadInputs(pSuper->pRoot); + for ( v = 0; v < nInputs; v++ ) + if ( pSuper->pFanins[v]->Num != nInputs - 1 - v ) + break; + if ( v != nInputs ) + continue; +// printf( "%s\n", Mio_GateReadName(pSuper->pRoot) ); + if ( st_insert( tTable, (char *)pSuper->pRoot, (char *)pSuper ) ) + { + assert( 0 ); + } + } + } + return tTable; +} + +/**Function************************************************************* + + Synopsis [Get the FRAIG node with phase.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_ManCleanData( Map_Man_t * p ) +{ + int i; + for ( i = 0; i < p->vNodesAll->nSize; i++ ) + p->vNodesAll->pArray[i]->pData0 = p->vNodesAll->pArray[i]->pData1 = 0; +} + +/**Function************************************************************* + + Synopsis [Expand the truth table] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingExpandTruth( unsigned uTruth[2], int nVars ) +{ + assert( nVars < 7 ); + if ( nVars == 6 ) + return; + if ( nVars < 5 ) + { + uTruth[0] &= MAP_MASK( (1<<nVars) ); + uTruth[0] = Map_MappingExpandTruth_rec( uTruth[0], nVars ); + } + uTruth[1] = uTruth[0]; +} + +/**Function************************************************************* + + Synopsis [Expand the truth table] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars ) +{ + assert( nVars < 6 ); + if ( nVars == 5 ) + return uTruth; + return Map_MappingExpandTruth_rec( uTruth | (uTruth << (1 << nVars)), nVars + 1 ); +} + +/**Function************************************************************* + + Synopsis [Compute the arrival times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_MappingComputeDelayWithFanouts( Map_Man_t * p ) +{ + Map_Node_t * pNode; + float Result; + int i; + for ( i = 0; i < p->vAnds->nSize; i++ ) + { + // skip primary inputs + pNode = p->vAnds->pArray[i]; + if ( !Map_NodeIsAnd( pNode ) ) + continue; + // skip a secondary node + if ( pNode->pRepr ) + continue; + // count the switching nodes + if ( pNode->nRefAct[0] > 0 ) + Map_TimeCutComputeArrival( pNode, pNode->pCutBest[0], 0, MAP_FLOAT_LARGE ); + if ( pNode->nRefAct[1] > 0 ) + Map_TimeCutComputeArrival( pNode, pNode->pCutBest[1], 1, MAP_FLOAT_LARGE ); + } + Result = Map_TimeComputeArrivalMax(p); + printf( "Max arrival times with fanouts = %10.2f.\n", Result ); + return Result; +} + + +/**Function************************************************************* + + Synopsis [Sets up the mask.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingGetMaxLevel( Map_Man_t * pMan ) +{ + int nLevelMax, i; + nLevelMax = 0; + for ( i = 0; i < pMan->nOutputs; i++ ) + nLevelMax = ((unsigned)nLevelMax) > Map_Regular(pMan->pOutputs[i])->Level? + nLevelMax : Map_Regular(pMan->pOutputs[i])->Level; + return nLevelMax; +} + +/**Function************************************************************* + + Synopsis [Analyses choice nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingUpdateLevel_rec( Map_Man_t * pMan, Map_Node_t * pNode, int fMaximum ) +{ + Map_Node_t * pTemp; + int Level1, Level2, LevelE; + assert( !Map_IsComplement(pNode) ); + if ( !Map_NodeIsAnd(pNode) ) + return pNode->Level; + // skip the visited node + if ( pNode->TravId == pMan->nTravIds ) + return pNode->Level; + pNode->TravId = pMan->nTravIds; + // compute levels of the children nodes + Level1 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p1), fMaximum ); + Level2 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p2), fMaximum ); + pNode->Level = 1 + MAP_MAX( Level1, Level2 ); + if ( pNode->pNextE ) + { + LevelE = Map_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum ); + if ( fMaximum ) + { + if ( pNode->Level < (unsigned)LevelE ) + pNode->Level = LevelE; + } + else + { + if ( pNode->Level > (unsigned)LevelE ) + pNode->Level = LevelE; + } + // set the level of all equivalent nodes to be the same minimum + if ( pNode->pRepr == NULL ) // the primary node + for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) + pTemp->Level = pNode->Level; + } + return pNode->Level; +} + +/**Function************************************************************* + + Synopsis [Resets the levels of the nodes in the choice graph.] + + Description [Makes the level of the choice nodes to be equal to the + maximum of the level of the nodes in the equivalence class. This way + sorting by level leads to the reverse topological order, which is + needed for the required time computation.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingSetChoiceLevels( Map_Man_t * pMan ) +{ + int i; + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); +} + +/**Function************************************************************* + + Synopsis [Reports statistics on choice nodes.] + + Description [The number of choice nodes is the number of primary nodes, + which has pNextE set to a pointer. The number of choices is the number + of entries in the equivalent-node lists of the primary nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingReportChoices( Map_Man_t * pMan ) +{ + Map_Node_t * pNode, * pTemp; + int nChoiceNodes, nChoices; + int i, LevelMax1, LevelMax2; + + // report the number of levels + LevelMax1 = Map_MappingGetMaxLevel( pMan ); + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 ); + LevelMax2 = Map_MappingGetMaxLevel( pMan ); + + // report statistics about choices + nChoiceNodes = nChoices = 0; + for ( i = 0; i < pMan->vAnds->nSize; i++ ) + { + pNode = pMan->vAnds->pArray[i]; + if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) + { // this is a choice node = the primary node that has equivalent nodes + nChoiceNodes++; + for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) + nChoices++; + } + } + printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); + printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); +} + +/* +void Map_MappingReportChoices( Map_Man_t * pMan ) +{ + Map_Node_t * pNode, * pTemp; + int nChoiceNodes, nChoices; + int i, LevelMax1, LevelMax2; + int DiffMaxTotal, DiffMinTotal, Min, Max; + int CounterByMin[300]={0}, CounterByMax[300]={0}; + + // report the number of levels + LevelMax1 = Map_MappingGetMaxLevel( pMan ); + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) +// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 ); + Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); + LevelMax2 = Map_MappingGetMaxLevel( pMan ); + + // report statistics about choices + nChoiceNodes = nChoices = 0; + DiffMaxTotal = DiffMinTotal = 0; + for ( i = 0; i < pMan->vAnds->nSize; i++ ) + { + pNode = pMan->vAnds->pArray[i]; + if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) + { // this is a choice node = the primary node that has equivalent nodes + nChoiceNodes++; + for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) + nChoices++; + // call to compare the levels + Map_MappingGetChoiceLevels( pMan, pNode, pNode->pNextE, &Min, &Max ); + assert( Min < (int)pNode->Level ); + assert( Max < (int)pNode->Level ); + DiffMinTotal += pNode->Level - Max; + DiffMaxTotal += pNode->Level - Min; + + CounterByMin[pNode->Level - Max]++; + CounterByMax[pNode->Level - Min]++; + + } + } + printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); + printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); + printf( "Choice depth: Minimum = %4.2f. Maximum = %4.2f.\n", + ((float)DiffMinTotal)/nChoiceNodes, ((float)DiffMaxTotal)/nChoiceNodes ); + + { + FILE * pTable; + pTable = fopen( "statsc.txt", "a+" ); + fprintf( pTable, "%6d ", pMan->vAnds->nSize ); + fprintf( pTable, "%5d ", LevelMax2 ); + fprintf( pTable, "%5d ", nChoiceNodes ); + fprintf( pTable, "%5d ", nChoices ); + fprintf( pTable, "%5.2f ", ((float)DiffMinTotal)/nChoiceNodes ); + fprintf( pTable, "%5.2f ", ((float)DiffMaxTotal)/nChoiceNodes ); +// fprintf( pTable, "%4.2f\n", (float)(Time)/(float)(CLOCKS_PER_SEC) ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } + + + printf( "Distribution by min/max levels:\n" ); + for ( i = 0; i < LevelMax2; i++ ) + printf( "%3d : %5d %5d\n", i, CounterByMin[i], CounterByMax[i] ); + printf( "\n" ); +} +*/ + +/* +void Map_MappingReportChoices( Map_Man_t * pMan ) +{ + Map_Node_t * pNode, * pTemp; + int nChoiceNodes, nChoices; + int i, LevelMax1, LevelMax2; + int CounterByVol[1000]={0}; + float VolumeAve, Volume; + + // report the number of levels + LevelMax1 = Map_MappingGetMaxLevel( pMan ); + pMan->nTravIds++; + for ( i = 0; i < pMan->nOutputs; i++ ) + Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 ); +// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); + LevelMax2 = Map_MappingGetMaxLevel( pMan ); + + // report statistics about choices + nChoiceNodes = nChoices = 0; + VolumeAve = 0.0; + for ( i = 0; i < pMan->vAnds->nSize; i++ ) + { + pNode = pMan->vAnds->pArray[i]; + if ( pNode->pRepr == NULL && pNode->pNextE != NULL ) + { // this is a choice node = the primary node that has equivalent nodes + nChoiceNodes++; + for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE ) + nChoices++; + Volume = Map_MappingGetChoiceVolumes( pMan, pNode, pNode->pNextE ); + VolumeAve += Volume; + assert( Volume < 1000 ); + CounterByVol[(int)Volume]++; + } + } + printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 ); + printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices ); + printf( "Average volume = %5.4f.\n", VolumeAve/nChoiceNodes ); +*/ +/* + { + FILE * pTable; + pTable = fopen( "statsv.txt", "a+" ); + fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,1) ); + fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,0) ); + fprintf( pTable, "%5d ", LevelMax1 ); + fprintf( pTable, " " ); + fprintf( pTable, "%5d ", nChoiceNodes ); + fprintf( pTable, "%5d ", nChoices ); + fprintf( pTable, " " ); + fprintf( pTable, "%5.4f ", VolumeAve/nChoiceNodes ); + fprintf( pTable, "\n" ); + fclose( pTable ); + } + printf( "Distribution by volume:\n" ); + for ( i = 0; i < 1000; i++ ) + if ( CounterByVol[i] > 0 ) + printf( "%3d : %5d\n", i, CounterByVol[i] ); + printf( "\n" ); +*/ +/* +} +*/ + +/**Function************************************************************* + + Synopsis [Computes the maximum and minimum levels of the choice nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_MappingGetChoiceLevels( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2, int * pMin, int * pMax ) +{ + Map_NodeVec_t * vNodes; + Map_NodeVec_t * vBoundary; + Map_Node_t * pNode; + int i, Min, Max; + + vNodes = Map_NodeVecAlloc( 100 ); + vBoundary = Map_NodeVecAlloc( 100 ); + Map_MappingDfsMarked1_rec( p1, vNodes, 1 ); + Map_MappingDfsMarked2_rec( p2, vNodes, vBoundary, 1 ); + // clean the marks + Min = 100000; + Max = -100000; + for ( i = 0; i < vBoundary->nSize; i++ ) + { + pNode = vBoundary->pArray[i]; + if ( Min > (int)pNode->Level ) + Min = pNode->Level; + if ( Max < (int)pNode->Level ) + Max = pNode->Level; + } + Map_NodeVecFree( vBoundary ); + for ( i = 0; i < vNodes->nSize; i++ ) + { + pNode = vNodes->pArray[i]; + pNode->fMark0 = pNode->fMark1 = 0; + } + Map_NodeVecFree( vNodes ); + *pMin = Min; + *pMax = Max; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Map_MappingGetChoiceVolumes( Map_Man_t * pMan, Map_Node_t * p1, Map_Node_t * p2 ) +{ + Map_NodeVec_t * vNodes; + Map_Node_t * pNode; + int i, nVolumeTotal, nVolumeUnique; + + vNodes = Map_NodeVecAlloc( 100 ); + Map_MappingDfsMarked3_rec( p1, vNodes ); + Map_MappingDfsMarked4_rec( p2, vNodes ); + // clean the marks + nVolumeTotal = nVolumeUnique = 0; + for ( i = 0; i < vNodes->nSize; i++ ) + { + pNode = vNodes->pArray[i]; + if ( !Map_NodeIsAnd(pNode) ) + continue; + nVolumeTotal++; + if ( pNode->fMark0 ^ pNode->fMark1 ) + nVolumeUnique++; + pNode->fMark0 = pNode->fMark1 = 0; + } + Map_NodeVecFree( vNodes ); +// return ((float)nVolumeUnique)/nVolumeTotal; + return (float)nVolumeUnique; +} + + +/**Function************************************************************* + + Synopsis [Computes the maximum and minimum levels of the choice nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices ) +{ + Map_NodeVec_t * vNodes; + int Result; + vNodes = Map_MappingDfs( pMan, fChoices ); + Result = vNodes->nSize; + Map_NodeVecFree( vNodes ); + return Result; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/map/mapper/mapperVec.c b/src/map/mapper/mapperVec.c new file mode 100644 index 00000000..e3ab4b7f --- /dev/null +++ b/src/map/mapper/mapperVec.c @@ -0,0 +1,318 @@ +/**CFile**************************************************************** + + FileName [mapperVec.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Generic technology mapping engine.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 2.0. Started - June 1, 2004.] + + Revision [$Id: mapperVec.c,v 1.3 2005/01/23 06:59:45 alanmi Exp $] + +***********************************************************************/ + +#include "mapperInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Map_NodeVecCompareLevels( Map_Node_t ** pp1, Map_Node_t ** pp2 ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Allocates a vector with the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_NodeVec_t * Map_NodeVecAlloc( int nCap ) +{ + Map_NodeVec_t * p; + p = ALLOC( Map_NodeVec_t, 1 ); + if ( nCap > 0 && nCap < 16 ) + nCap = 16; + p->nSize = 0; + p->nCap = nCap; + p->pArray = p->nCap? ALLOC( Map_Node_t *, p->nCap ) : NULL; + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecFree( Map_NodeVec_t * p ) +{ + FREE( p->pArray ); + FREE( p ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t ** Map_NodeVecReadArray( Map_NodeVec_t * p ) +{ + return p->pArray; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeVecReadSize( Map_NodeVec_t * p ) +{ + return p->nSize; +} + +/**Function************************************************************* + + Synopsis [Resizes the vector to the given capacity.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecGrow( Map_NodeVec_t * p, int nCapMin ) +{ + if ( p->nCap >= nCapMin ) + return; + p->pArray = REALLOC( Map_Node_t *, p->pArray, nCapMin ); + p->nCap = nCapMin; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecShrink( Map_NodeVec_t * p, int nSizeNew ) +{ + assert( p->nSize >= nSizeNew ); + p->nSize = nSizeNew; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecClear( Map_NodeVec_t * p ) +{ + p->nSize = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecPush( Map_NodeVec_t * p, Map_Node_t * Entry ) +{ + if ( p->nSize == p->nCap ) + { + if ( p->nCap < 16 ) + Map_NodeVecGrow( p, 16 ); + else + Map_NodeVecGrow( p, 2 * p->nCap ); + } + p->pArray[p->nSize++] = Entry; +} + +/**Function************************************************************* + + Synopsis [Add the element while ensuring uniqueness.] + + Description [Returns 1 if the element was found, and 0 if it was new. ] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeVecPushUnique( Map_NodeVec_t * p, Map_Node_t * Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + return 1; + Map_NodeVecPush( p, Entry ); + return 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeVecPop( Map_NodeVec_t * p ) +{ + return p->pArray[--p->nSize]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecRemove( Map_NodeVec_t * p, Map_Node_t * Entry ) +{ + int i; + for ( i = 0; i < p->nSize; i++ ) + if ( p->pArray[i] == Entry ) + break; + assert( i < p->nSize ); + for ( i++; i < p->nSize; i++ ) + p->pArray[i-1] = p->pArray[i]; + p->nSize--; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecWriteEntry( Map_NodeVec_t * p, int i, Map_Node_t * Entry ) +{ + assert( i >= 0 && i < p->nSize ); + p->pArray[i] = Entry; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Map_Node_t * Map_NodeVecReadEntry( Map_NodeVec_t * p, int i ) +{ + assert( i >= 0 && i < p->nSize ); + return p->pArray[i]; +} + +/**Function************************************************************* + + Synopsis [Sorting the entries by their integer value.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Map_NodeVecSortByLevel( Map_NodeVec_t * p ) +{ + qsort( (void *)p->pArray, p->nSize, sizeof(Map_Node_t *), + (int (*)(const void *, const void *)) Map_NodeVecCompareLevels ); +} + +/**Function************************************************************* + + Synopsis [Comparison procedure for two clauses.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Map_NodeVecCompareLevels( Map_Node_t ** pp1, Map_Node_t ** pp2 ) +{ + int Level1 = Map_Regular(*pp1)->Level; + int Level2 = Map_Regular(*pp2)->Level; + if ( Level1 < Level2 ) + return -1; + if ( Level1 > Level2 ) + return 1; + if ( Map_Regular(*pp1)->Num < Map_Regular(*pp2)->Num ) + return -1; + if ( Map_Regular(*pp1)->Num > Map_Regular(*pp2)->Num ) + return 1; + return 0; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + diff --git a/src/map/mapper/module.make b/src/map/mapper/module.make new file mode 100644 index 00000000..1d3b8867 --- /dev/null +++ b/src/map/mapper/module.make @@ -0,0 +1,17 @@ +SRC += src/map/mapper/mapper.c \ + src/map/mapper/mapperCanon.c \ + src/map/mapper/mapperCore.c \ + src/map/mapper/mapperCreate.c \ + src/map/mapper/mapperCut.c \ + src/map/mapper/mapperCutUtils.c \ + src/map/mapper/mapperFanout.c \ + src/map/mapper/mapperLib.c \ + src/map/mapper/mapperMatch.c \ + src/map/mapper/mapperRefs.c \ + src/map/mapper/mapperSuper.c \ + src/map/mapper/mapperTable.c \ + src/map/mapper/mapperTime.c \ + src/map/mapper/mapperTree.c \ + src/map/mapper/mapperTruth.c \ + src/map/mapper/mapperUtils.c \ + src/map/mapper/mapperVec.c |