diff options
Diffstat (limited to 'src/aig/dch/dchSim.c')
| -rw-r--r-- | src/aig/dch/dchSim.c | 238 |
1 files changed, 136 insertions, 102 deletions
diff --git a/src/aig/dch/dchSim.c b/src/aig/dch/dchSim.c index f11b701f..9882dd05 100644 --- a/src/aig/dch/dchSim.c +++ b/src/aig/dch/dchSim.c @@ -39,6 +39,121 @@ static inline unsigned Dch_ObjRandomSim() /**Function************************************************************* + Synopsis [Computes hash value of the node using its simulation info.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Dch_NodeHash( void * p, Aig_Obj_t * pObj ) +{ + Vec_Ptr_t * vSims = p; + static int s_FPrimes[128] = { + 1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459, + 1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997, + 2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543, + 2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089, + 3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671, + 3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243, + 4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871, + 4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471, + 5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073, + 6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689, + 6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309, + 7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933, + 8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147 + }; + unsigned * pSim; + unsigned uHash; + int k, nWords; + nWords = (unsigned *)Vec_PtrEntry(vSims, 1) - (unsigned *)Vec_PtrEntry(vSims, 0); + uHash = 0; + pSim = Dch_ObjSim( vSims, pObj ); + if ( pObj->fPhase ) + { + for ( k = 0; k < nWords; k++ ) + uHash ^= ~pSim[k] * s_FPrimes[k & 0x7F]; + } + else + { + for ( k = 0; k < nWords; k++ ) + uHash ^= pSim[k] * s_FPrimes[k & 0x7F]; + } + return uHash; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if simulation info is composed of all zeros.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dch_NodeIsConst( void * p, Aig_Obj_t * pObj ) +{ + Vec_Ptr_t * vSims = p; + unsigned * pSim; + int k, nWords; + nWords = (unsigned *)Vec_PtrEntry(vSims, 1) - (unsigned *)Vec_PtrEntry(vSims, 0); + pSim = Dch_ObjSim( vSims, pObj ); + if ( pObj->fPhase ) + { + for ( k = 0; k < nWords; k++ ) + if ( ~pSim[k] ) + return 0; + } + else + { + for ( k = 0; k < nWords; k++ ) + if ( pSim[k] ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if simulation infos are equal.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dch_NodesAreEqual( void * p, Aig_Obj_t * pObj0, Aig_Obj_t * pObj1 ) +{ + Vec_Ptr_t * vSims = p; + unsigned * pSim0, * pSim1; + int k, nWords; + nWords = (unsigned *)Vec_PtrEntry(vSims, 1) - (unsigned *)Vec_PtrEntry(vSims, 0); + pSim0 = Dch_ObjSim( vSims, pObj0 ); + pSim1 = Dch_ObjSim( vSims, pObj1 ); + if ( pObj0->fPhase != pObj1->fPhase ) + { + for ( k = 0; k < nWords; k++ ) + if ( pSim0[k] != ~pSim1[k] ) + return 0; + } + else + { + for ( k = 0; k < nWords; k++ ) + if ( pSim0[k] != pSim1[k] ) + return 0; + } + return 1; +} + +/**Function************************************************************* + Synopsis [Perform random simulation.] Description [] @@ -48,11 +163,12 @@ static inline unsigned Dch_ObjRandomSim() SeeAlso [] ***********************************************************************/ -void Dch_PerformRandomSimulation( Aig_Man_t * pAig, Vec_Ptr_t * vSims, int nWords ) +void Dch_PerformRandomSimulation( Aig_Man_t * pAig, Vec_Ptr_t * vSims ) { unsigned * pSim, * pSim0, * pSim1; Aig_Obj_t * pObj; - int i, k; + int i, k, nWords; + nWords = (unsigned *)Vec_PtrEntry(vSims, 1) - (unsigned *)Vec_PtrEntry(vSims, 0); // assign const 1 sim info pObj = Aig_ManConst1(pAig); @@ -65,6 +181,7 @@ void Dch_PerformRandomSimulation( Aig_Man_t * pAig, Vec_Ptr_t * vSims, int nWord pSim = Dch_ObjSim( vSims, pObj ); for ( k = 0; k < nWords; k++ ) pSim[k] = Dch_ObjRandomSim(); + pSim[0] <<= 1; } // simulate AIG in the topological order @@ -95,92 +212,11 @@ void Dch_PerformRandomSimulation( Aig_Man_t * pAig, Vec_Ptr_t * vSims, int nWord pSim[k] = pSim0[k] & pSim1[k]; } } - // get simulation information for primary outputs } /**Function************************************************************* - Synopsis [Hashing nodes by sim info.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Dch_HashNodesBySimulationInfo( Aig_Man_t * pAig, Vec_Ptr_t * vSims, int nWords ) -{ - unsigned * pSim0, * pSim1; - Aig_Obj_t * pObj, * pUnique; - int i, k, j, nodeId, Counter, c, CountNodes; - - Vec_Int_t * vUniqueNodes, * vNodeCounters; - - vUniqueNodes = Vec_IntAlloc( 1000 ); - vNodeCounters = Vec_IntStart( Aig_ManObjNumMax(pAig) ); - - Aig_ManForEachObj( pAig, pObj, i ) - { - if ( Aig_ObjIsPo(pObj) ) - continue; - - // node's sim info - pSim0 = Dch_ObjSim( vSims, pObj ); - - Vec_IntForEachEntry( vUniqueNodes, nodeId, j ) - { - pUnique = Aig_ManObj( pAig, nodeId ); - // unique node's sim info - pSim1 = Dch_ObjSim( vSims, pUnique ); - - for ( k = 0; k < nWords; k++ ) - if ( pSim0[k] != pSim1[k] ) - break; - if ( k == nWords ) // sim info is same as this node - { - Counter = Vec_IntEntry( vNodeCounters, nodeId ); - Vec_IntWriteEntry( vNodeCounters, nodeId, Counter+1 ); - break; - } - } - - if ( j == Vec_IntSize(vUniqueNodes) ) // sim info of pObj is unique - { - Vec_IntPush( vUniqueNodes, pObj->Id ); - - Counter = Vec_IntEntry( vNodeCounters, pObj->Id ); - assert( Counter == 0 ); - Vec_IntWriteEntry( vNodeCounters, pObj->Id, Counter+1 ); - } - } - - Counter = 0; - Vec_IntForEachEntry( vNodeCounters, c, k ) - if ( c > 1 ) - Counter++; - - - printf( "Detected %d non-trivial candidate equivalence classes for %d nodes.\n", - Counter, Vec_IntSize(vUniqueNodes) ); - - CountNodes = 0; - Vec_IntForEachEntry( vUniqueNodes, nodeId, k ) - { - if ( Vec_IntEntry( vNodeCounters, nodeId ) == 1 ) - continue; -// printf( "%d ", Vec_IntEntry( vNodeCounters, nodeId ) ); - CountNodes += Vec_IntEntry( vNodeCounters, nodeId ); - } -// printf( "\n" ); - printf( "Nodes participating in non-trivial classes = %d.\n", CountNodes ); - - -} - -/**Function************************************************************* - Synopsis [Derives candidate equivalence classes of AIG nodes.] Description [] @@ -190,32 +226,30 @@ void Dch_HashNodesBySimulationInfo( Aig_Man_t * pAig, Vec_Ptr_t * vSims, int nWo SeeAlso [] ***********************************************************************/ -Dch_Cla_t ** Dch_CreateCandEquivClasses( Aig_Man_t * pAig, int nWords, int fVerbose ) +Dch_Cla_t * Dch_CreateCandEquivClasses( Aig_Man_t * pAig, int nWords, int fVerbose ) { - Dch_Cla_t ** ppClasses; // place for equivalence classes - Aig_MmFlex_t * pMemCla; // memory for equivalence classes + Dch_Cla_t * pClasses; Vec_Ptr_t * vSims; - - // start storage for equivalence classes - ppClasses = CALLOC( Dch_Cla_t *, Aig_ManObjNumMax(pAig) ); - pMemCla = Aig_MmFlexStart(); - + int i; // allocate simulation information vSims = Vec_PtrAllocSimInfo( Aig_ManObjNumMax(pAig), nWords ); - - // run simulation - Dch_PerformRandomSimulation( pAig, vSims, nWords ); - + // run random simulation from the primary inputs + Dch_PerformRandomSimulation( pAig, vSims ); + // start storage for equivalence classes + pClasses = Dch_ClassesStart( pAig ); + Dch_ClassesSetData( pClasses, vSims, Dch_NodeHash, Dch_NodeIsConst, Dch_NodesAreEqual ); // hash nodes by sim info - Dch_HashNodesBySimulationInfo( pAig, vSims, nWords ); - - // collect equivalence classes -// ppClasses = NULL; - + Dch_ClassesPrepare( pClasses, 0, 0 ); + // iterate random simulation + for ( i = 0; i < 3; i++ ) + { + Dch_PerformRandomSimulation( pAig, vSims ); + Dch_ClassesRefine( pClasses ); + } // clean up and return - Aig_MmFlexStop( pMemCla, 0 ); + Dch_ClassesSetData( pClasses, NULL, NULL, NULL, NULL ); Vec_PtrFree( vSims ); - return ppClasses; + return pClasses; } //////////////////////////////////////////////////////////////////////// |