diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2016-12-04 13:05:51 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2016-12-04 13:05:51 -0800 |
commit | 91aab10757add03dc29e5b7d0d966f5784625949 (patch) | |
tree | 2b92e1e07c2794c511c86578e3ea87e1a40349ff /src/proof | |
parent | c88a2421b46288e4a4c74a72b906f81ea9ed00b1 (diff) | |
download | abc-91aab10757add03dc29e5b7d0d966f5784625949.tar.gz abc-91aab10757add03dc29e5b7d0d966f5784625949.tar.bz2 abc-91aab10757add03dc29e5b7d0d966f5784625949.zip |
Analysis of arithmetic logic cones.
Diffstat (limited to 'src/proof')
-rw-r--r-- | src/proof/acec/acecCo.c | 4 | ||||
-rw-r--r-- | src/proof/acec/acecPa.c | 4 | ||||
-rw-r--r-- | src/proof/acec/acecPool.c | 317 | ||||
-rw-r--r-- | src/proof/acec/acecRe.c | 44 |
4 files changed, 351 insertions, 18 deletions
diff --git a/src/proof/acec/acecCo.c b/src/proof/acec/acecCo.c index 39f092b2..1e8ed7bb 100644 --- a/src/proof/acec/acecCo.c +++ b/src/proof/acec/acecCo.c @@ -387,10 +387,10 @@ Gia_Man_t * Gia_PolynCoreDupTree( Gia_Man_t * p, Vec_Int_t * vAddCos, Vec_Int_t ***********************************************************************/ Gia_Man_t * Gia_PolynCoreDetectTest_int( Gia_Man_t * pGia, Vec_Int_t * vAddCos, int fAddCones, int fVerbose ) { - extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ); + extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose ); abctime clk = Abc_Clock(); Gia_Man_t * pNew; - Vec_Int_t * vAdds = Ree_ManComputeCuts( pGia, 1 ); + Vec_Int_t * vAdds = Ree_ManComputeCuts( pGia, NULL, 1 ); Vec_Int_t * vLeaves, * vRoots, * vOrder = Gia_PolynCoreOrder( pGia, vAdds, vAddCos, &vLeaves, &vRoots ); Vec_Int_t * vNodes = Gia_PolynCoreCollect( pGia, vAdds, vOrder ); diff --git a/src/proof/acec/acecPa.c b/src/proof/acec/acecPa.c index 11d68d37..ecaf2047 100644 --- a/src/proof/acec/acecPa.c +++ b/src/proof/acec/acecPa.c @@ -248,13 +248,13 @@ int Pas_ManComputeCuts( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vOrder, Ve ***********************************************************************/ void Pas_ManComputeCutsTest( Gia_Man_t * p ) { - extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ); + extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose ); extern Vec_Int_t * Gia_PolynCoreOrder( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vAddCos, Vec_Int_t ** pvIns, Vec_Int_t ** pvOuts ); extern int Ree_ManCountFadds( Vec_Int_t * vAdds ); extern void Ree_ManPrintAdders( Vec_Int_t * vAdds, int fVerbose ); abctime clk = Abc_Clock(); - Vec_Int_t * vAdds = Ree_ManComputeCuts( p, 1 ); + Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 ); Vec_Int_t * vIns, * vOuts; Vec_Int_t * vOrder = Gia_PolynCoreOrder( p, vAdds, NULL, &vIns, &vOuts ); int nTrees, nFadds = Ree_ManCountFadds( vAdds ); diff --git a/src/proof/acec/acecPool.c b/src/proof/acec/acecPool.c index 294066fa..08ee37f2 100644 --- a/src/proof/acec/acecPool.c +++ b/src/proof/acec/acecPool.c @@ -45,6 +45,319 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ +Vec_Int_t * Acec_ManCreateCarryMap( Gia_Man_t * p, Vec_Int_t * vAdds ) +{ + // map carries into their boxes + Vec_Int_t * vCarryMap = Vec_IntStartFull( Gia_ManObjNum(p) ); int i; + for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) + Vec_IntWriteEntry( vCarryMap, Vec_IntEntry(vAdds, 6*i+4), i ); + return vCarryMap; +} +int Acec_ManCheckCarryMap( Gia_Man_t * p, int Carry, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap ) +{ + int iBox = Vec_IntEntry( vCarryMap, Carry ); + assert( iBox >= 0 ); + return Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+0) ) >= 0 || + Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+1) ) >= 0 || + Vec_IntEntry( vCarryMap, Vec_IntEntry(vAdds, 6*iBox+2) ) >= 0; +} +Vec_Int_t * Acec_ManCollectCarryRoots( Gia_Man_t * p, Vec_Int_t * vAdds ) +{ + Vec_Int_t * vCarryRoots = Vec_IntAlloc( 100 ); + Vec_Bit_t * vIns = Vec_BitStart( Gia_ManObjNum(p) ); int i; + // marks box inputs + for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) + { + Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+0), 1 ); + Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+1), 1 ); + Vec_BitWriteEntry( vIns, Vec_IntEntry(vAdds, 6*i+2), 1 ); + } + // collect roots + for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ ) + if ( !Vec_BitEntry(vIns, Vec_IntEntry(vAdds, 6*i+4)) ) + Vec_IntPush( vCarryRoots, Vec_IntEntry(vAdds, 6*i+4) ); + Vec_BitFree( vIns ); + return vCarryRoots; +} +Vec_Int_t * Acec_ManCollectXorRoots( Gia_Man_t * p, Vec_Int_t * vXors ) +{ + Vec_Int_t * vXorRoots = Vec_IntAlloc( 100 ); + Vec_Bit_t * vIns = Vec_BitStart( Gia_ManObjNum(p) ); int i; + // marks box inputs + for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) + { + Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+1), 1 ); + Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+2), 1 ); + Vec_BitWriteEntry( vIns, Vec_IntEntry(vXors, 4*i+3), 1 ); + } + // collect roots + for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) + if ( !Vec_BitEntry(vIns, Vec_IntEntry(vXors, 4*i)) ) + Vec_IntPush( vXorRoots, Vec_IntEntry(vXors, 4*i) ); + Vec_BitFree( vIns ); + return vXorRoots; +} +void Acec_ManCountXorTreeInputs_rec( Gia_Man_t * p, int Node, Vec_Int_t * vXors, Vec_Int_t * vXorMap, Vec_Bit_t * vIsCarryRoot, Vec_Int_t * vCarryRootSet, Vec_Int_t * vXorSet ) +{ + int k, iXorBox; + if ( Node == 0 || Gia_ObjIsTravIdCurrentId(p, Node) ) + return; + Gia_ObjSetTravIdCurrentId(p, Node); + iXorBox = Vec_IntEntry( vXorMap, Node ); + if ( iXorBox == -1 ) + { + if ( Vec_BitEntry(vIsCarryRoot, Node) ) + Vec_IntPush( vCarryRootSet, Node ); + return; + } + for ( k = 1; k < 4; k++ ) + Acec_ManCountXorTreeInputs_rec( p, Vec_IntEntry(vXors, 4*iXorBox+k), vXors, vXorMap, vIsCarryRoot, vCarryRootSet, vXorSet ); + Vec_IntPush( vXorSet, Vec_IntEntry(vXors, 4*iXorBox) ); +} +Vec_Wec_t * Acec_ManCollectCarryRootSets( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap, Vec_Int_t * vXors, Vec_Int_t * vXorRoots, Vec_Int_t * vCarryRoots ) +{ + Vec_Wec_t * vCarryRootSets = Vec_WecAlloc( 100 ); // XorBoxes, CarryRoots, AdderBoxes, Ins/Ranks, Outs/Ranks + Vec_Int_t * vCarryRootSet = Vec_IntAlloc( 100 ); + Vec_Bit_t * vIsCarryRoot = Vec_BitStart( Gia_ManObjNum(p) ); + Vec_Int_t * vXorSet = Vec_IntAlloc( 100 ), * vLevel; + int i, k, XorRoot, CarryRoot; + // map XORs into their cuts + Vec_Int_t * vXorMap = Vec_IntStartFull( Gia_ManObjNum(p) ); + for ( i = 0; 4*i < Vec_IntSize(vXors); i++ ) + Vec_IntWriteEntry( vXorMap, Vec_IntEntry(vXors, 4*i), i ); + // create carry root marks + Vec_IntForEachEntry( vCarryRoots, CarryRoot, i ) + Vec_BitWriteEntry( vIsCarryRoot, CarryRoot, 1 ); + // collect carry roots attached to each XOR root + Vec_IntForEachEntry( vXorRoots, XorRoot, i ) + { + Vec_IntClear( vXorSet ); + Vec_IntClear( vCarryRootSet ); + Gia_ManIncrementTravId( p ); + Acec_ManCountXorTreeInputs_rec( p, XorRoot, vXors, vXorMap, vIsCarryRoot, vCarryRootSet, vXorSet ); + // skip trivial + Vec_IntForEachEntry( vCarryRootSet, CarryRoot, k ) + if ( Acec_ManCheckCarryMap(p, CarryRoot, vAdds, vCarryMap) ) + break; + if ( k == Vec_IntSize(vCarryRootSet) ) + continue; + Vec_IntSort( vCarryRootSet, 0 ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + Vec_IntAppend( vLevel, vXorSet ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + Vec_IntAppend( vLevel, vCarryRootSet ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + // unmark carry root set + Vec_IntForEachEntry( vCarryRootSet, CarryRoot, k ) + { + assert( Vec_BitEntry(vIsCarryRoot, CarryRoot) ); + Vec_BitWriteEntry( vIsCarryRoot, CarryRoot, 0 ); + } + } + Vec_IntFree( vCarryRootSet ); + Vec_IntFree( vXorSet ); + Vec_IntFree( vXorMap ); + // collect unmarked carry roots + Vec_IntForEachEntry( vCarryRoots, CarryRoot, k ) + { + if ( !Vec_BitEntry(vIsCarryRoot, CarryRoot) ) + continue; + if ( !Acec_ManCheckCarryMap(p, CarryRoot, vAdds, vCarryMap) ) + continue; + vLevel = Vec_WecPushLevel( vCarryRootSets ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + Vec_IntFill( vLevel, 1, CarryRoot ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + vLevel = Vec_WecPushLevel( vCarryRootSets ); + } + Vec_BitFree( vIsCarryRoot ); + return vCarryRootSets; +} +int Acec_ManCompareTwo( int * pPair0, int * pPair1 ) +{ + if ( pPair0[1] < pPair1[1] ) return -1; + if ( pPair0[1] > pPair1[1] ) return 1; + return 0; +} +void Acec_ManCollectInsOuts( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vBoxes, Vec_Int_t * vBoxRanks, Vec_Bit_t * vBoxIns, Vec_Bit_t * vBoxOuts, Vec_Int_t * vResIns, Vec_Int_t * vResOuts ) +{ + int i, k, iBox, iObj, Rank, RankMax = 0; + // mark box inputs/outputs + Vec_IntForEachEntry( vBoxes, iBox, i ) + { + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+0), 1 ); + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+1), 1 ); + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+2), 1 ); + Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+3), 1 ); + Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+4), 1 ); + } + // collect unmarked inputs/output and their ranks + Vec_IntForEachEntry( vBoxes, iBox, i ) + { + for ( k = 0; k < 3; k++ ) + if ( !Vec_BitEntry(vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+k)) ) + Vec_IntPushTwo( vResIns, Vec_IntEntry(vAdds, 6*iBox+k), Vec_IntEntry(vBoxRanks, iBox) ); + for ( k = 3; k < 5; k++ ) + if ( Vec_IntEntry(vAdds, 6*iBox+k) && !Vec_BitEntry(vBoxIns, Vec_IntEntry(vAdds, 6*iBox+k)) ) + Vec_IntPushTwo( vResOuts, Vec_IntEntry(vAdds, 6*iBox+k), Vec_IntEntry(vBoxRanks, iBox)-(int)(k==4) ); + } + // unmark box inputs/outputs + Vec_IntForEachEntry( vBoxes, iBox, i ) + { + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+0), 0 ); + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+1), 0 ); + Vec_BitWriteEntry( vBoxIns, Vec_IntEntry(vAdds, 6*iBox+2), 0 ); + Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+3), 0 ); + Vec_BitWriteEntry( vBoxOuts, Vec_IntEntry(vAdds, 6*iBox+4), 0 ); + } + // normalize ranks + Vec_IntForEachEntryDouble( vResIns, iObj, Rank, k ) + RankMax = Abc_MaxInt( RankMax, Rank ); + Vec_IntForEachEntryDouble( vResOuts, iObj, Rank, k ) + RankMax = Abc_MaxInt( RankMax, Rank ); + Vec_IntForEachEntryDouble( vResIns, iObj, Rank, k ) + Vec_IntWriteEntry( vResIns, k+1, 1 + RankMax - Rank ); + Vec_IntForEachEntryDouble( vResOuts, iObj, Rank, k ) + Vec_IntWriteEntry( vResOuts, k+1, 1 + RankMax - Rank ); + // sort by rank + qsort( Vec_IntArray(vResIns), Vec_IntSize(vResIns)/2, 8, (int (*)(const void *, const void *))Acec_ManCompareTwo ); + qsort( Vec_IntArray(vResOuts), Vec_IntSize(vResOuts)/2, 8, (int (*)(const void *, const void *))Acec_ManCompareTwo ); +} +void Acec_ManCollectBoxSets_rec( Gia_Man_t * p, int Carry, int iRank, Vec_Int_t * vAdds, Vec_Int_t * vCarryMap, Vec_Int_t * vBoxes, Vec_Int_t * vBoxRanks ) +{ + int iBox = Vec_IntEntry( vCarryMap, Carry ); + if ( iBox == -1 ) + return; + Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+0), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); + Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+1), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); + if ( Vec_IntEntry(vAdds, 6*iBox+2) ) + Acec_ManCollectBoxSets_rec( p, Vec_IntEntry(vAdds, 6*iBox+2), iRank+1, vAdds, vCarryMap, vBoxes, vBoxRanks ); + Vec_IntPush( vBoxes, iBox ); + Vec_IntWriteEntry( vBoxRanks, iBox, iRank ); +} +Vec_Wec_t * Acec_ManCollectBoxSets( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vXors ) +{ + Vec_Int_t * vCarryMap = Acec_ManCreateCarryMap( p, vAdds ); + Vec_Int_t * vCarryRoots = Acec_ManCollectCarryRoots( p, vAdds ); + Vec_Int_t * vXorRoots = Acec_ManCollectXorRoots( p, vXors ); + Vec_Wec_t * vBoxSets = Acec_ManCollectCarryRootSets( p, vAdds, vCarryMap, vXors, vXorRoots, vCarryRoots ); + Vec_Int_t * vBoxRanks = Vec_IntStart( Vec_IntSize(vAdds)/6 ); + Vec_Bit_t * vBoxIns = Vec_BitStart( Gia_ManObjNum(p) ); + Vec_Bit_t * vBoxOuts = Vec_BitStart( Gia_ManObjNum(p) ); int i, k, Root; + Vec_IntFree( vCarryRoots ); + Vec_IntFree( vXorRoots ); + // collect boxes for each carry set + assert( Vec_WecSize(vBoxSets) % 5 == 0 ); + for ( i = 0; 5*i < Vec_WecSize(vBoxSets); i++ ) + { + Vec_Int_t * vRoots = Vec_WecEntry( vBoxSets, 5*i+1 ); + Vec_Int_t * vBoxes = Vec_WecEntry( vBoxSets, 5*i+2 ); + Vec_Int_t * vIns = Vec_WecEntry( vBoxSets, 5*i+3 ); + Vec_Int_t * vOuts = Vec_WecEntry( vBoxSets, 5*i+4 ); + Vec_IntForEachEntry( vRoots, Root, k ) + Acec_ManCollectBoxSets_rec( p, Root, 1, vAdds, vCarryMap, vBoxes, vBoxRanks ); + Acec_ManCollectInsOuts( p, vAdds, vBoxes, vBoxRanks, vBoxIns, vBoxOuts, vIns, vOuts ); + } + Vec_IntFree( vBoxRanks ); + Vec_BitFree( vBoxIns ); + Vec_BitFree( vBoxOuts ); + Vec_IntFree( vCarryMap ); + return vBoxSets; +} +void Acec_ManPrintRanks2( Vec_Int_t * vPairs ) +{ + int k, iObj, Rank; + Vec_IntForEachEntryDouble( vPairs, iObj, Rank, k ) + printf( "%d ", Rank ); + printf( "\n" ); +} +void Acec_ManPrintRanks( Vec_Int_t * vPairs ) +{ + int k, iObj, Count, Rank, RankMax = 0; + Vec_Int_t * vCounts = Vec_IntStart( 100 ); + Vec_IntForEachEntryDouble( vPairs, iObj, Rank, k ) + { + Vec_IntFillExtra( vCounts, Rank+1, 0 ); + Vec_IntAddToEntry( vCounts, Rank, 1 ); + RankMax = Abc_MaxInt( RankMax, Rank ); + } + Vec_IntForEachEntryStartStop( vCounts, Count, Rank, 1, RankMax+1 ) + printf( "%2d=%2d ", Rank, Count ); + printf( "\n" ); + Vec_IntFree( vCounts ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Acec_ManProfile( Gia_Man_t * p, int fVerbose ) +{ + extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose ); + extern void Ree_ManRemoveTrivial( Gia_Man_t * p, Vec_Int_t * vAdds ); + extern void Ree_ManRemoveContained( Gia_Man_t * p, Vec_Int_t * vAdds ); + extern int Ree_ManCountFadds( Vec_Int_t * vAdds ); + extern void Ree_ManPrintAdders( Vec_Int_t * vAdds, int fVerbose ); + + abctime clk = Abc_Clock(); + Vec_Wec_t * vBoxes; int i; + Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( p, &vXors, fVerbose ); + Ree_ManRemoveTrivial( p, vAdds ); + Ree_ManRemoveContained( p, vAdds ); + + //Ree_ManPrintAdders( vAdds, 1 ); + printf( "Detected %d full-adders and %d half-adders. Found %d XOR-cuts. ", Ree_ManCountFadds(vAdds), Vec_IntSize(vAdds)/6-Ree_ManCountFadds(vAdds), Vec_IntSize(vXors)/4 ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + + clk = Abc_Clock(); + vBoxes = Acec_ManCollectBoxSets( p, vAdds, vXors ); + printf( "Detected %d adder-tree%s. ", Vec_WecSize(vBoxes)/5, Vec_WecSize(vBoxes)/5 > 1 ? "s":"" ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + + if ( fVerbose ) + for ( i = 0; 5*i < Vec_WecSize(vBoxes); i++ ) + { + printf( "Tree %3d : ", i ); + printf( "Xor = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+0)) ); + printf( "Root = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+1)) ); + //printf( "(Top = %5d) ", Vec_IntEntryLast(Vec_WecEntry(vBoxes,5*i+1)) ); + printf( "Adder = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+2)) ); + printf( "In = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+3))/2 ); + printf( "Out = %4d ", Vec_IntSize(Vec_WecEntry(vBoxes,5*i+4))/2 ); + printf( "\n" ); + printf( " Ins: " ); + Acec_ManPrintRanks( Vec_WecEntry(vBoxes,5*i+3) ); + printf( " Outs: " ); + Acec_ManPrintRanks( Vec_WecEntry(vBoxes,5*i+4) ); + } + + Vec_IntFree( vXors ); + Vec_IntFree( vAdds ); + Vec_WecFree( vBoxes ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ Vec_Bit_t * Acec_ManPoolGetPointed( Gia_Man_t * p, Vec_Int_t * vAdds ) { Vec_Bit_t * vMarks = Vec_BitStart( Gia_ManObjNum(p) ); @@ -83,7 +396,7 @@ Vec_Int_t * Acec_ManPoolTopMost( Gia_Man_t * p, Vec_Int_t * vAdds ) } void Acec_ManPool( Gia_Man_t * p ) { - extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ); + extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose ); extern Vec_Wec_t * Gia_PolynCoreOrderArray( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vRootBoxes ); extern int Ree_ManCountFadds( Vec_Int_t * vAdds ); @@ -94,7 +407,7 @@ void Acec_ManPool( Gia_Man_t * p ) Vec_Wec_t * vTrees; abctime clk = Abc_Clock(); - Vec_Int_t * vAdds = Ree_ManComputeCuts( p, 1 ); + Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 ); int i, nFadds = Ree_ManCountFadds( vAdds ); printf( "Detected %d FAs and %d HAs. ", nFadds, Vec_IntSize(vAdds)/6-nFadds ); Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); diff --git a/src/proof/acec/acecRe.c b/src/proof/acec/acecRe.c index e2340dba..26faad00 100644 --- a/src/proof/acec/acecRe.c +++ b/src/proof/acec/acecRe.c @@ -248,10 +248,11 @@ void Ree_ManCutPrint( int * pCut, int Count, word Truth ) Abc_TtPrintHexRev( stdout, &Truth, 3 ); printf( "\n" ); } -void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_Int_t * vCuts, Hash_IntMan_t * pHash, Vec_Int_t * vData ) +void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_Int_t * vCuts, Hash_IntMan_t * pHash, Vec_Int_t * vData, Vec_Int_t * vXors ) { int fVerbose = 0; int i, k, c, Value, Truth, TruthC, * pCut0, * pCut1, pCut[6], Count = 0; + int iXor2 = -1, iXor3 = -1; if ( fVerbose ) printf( "Object %d\n", iObj ); Vec_IntFill( vCuts, 2, 1 ); @@ -266,12 +267,16 @@ void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_I continue; Truth = TruthC = Ree_ManCutTruth(Gia_ManObj(p, iObj), pCut0, pCut1, pCut); //assert( Truth == Ree_ObjComputeTruth(p, iObj, pCut) ); + if ( Truth & 0x80 ) + Truth = 0xFF & ~Truth; + if ( Truth == 0x66 && iXor2 == -1 ) + iXor2 = Vec_IntSize(vCuts); + else if ( Truth == 0x69 && iXor3 == -1 ) + iXor3 = Vec_IntSize(vCuts); Vec_IntAddToEntry( vCuts, 0, 1 ); for ( c = 0; c <= pCut[0]; c++ ) Vec_IntPush( vCuts, pCut[c] ); - Vec_IntPush( vCuts, Truth ); - if ( Truth & 0x80 ) - Truth = 0xFF & ~Truth; + Vec_IntPush( vCuts, TruthC ); if ( (Truth == 0x66 || Truth == 0x11 || Truth == 0x22 || Truth == 0x44 || Truth == 0x77) && pCut[0] == 2 ) { assert( pCut[0] == 2 ); @@ -287,6 +292,19 @@ void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_I if ( fVerbose ) Ree_ManCutPrint( pCut, ++Count, TruthC ); } + if ( !vXors ) + return; + if ( iXor2 > 0 ) + pCut0 = Vec_IntEntryP( vCuts, iXor2 ); + else if ( iXor3 > 0 ) + pCut0 = Vec_IntEntryP( vCuts, iXor3 ); + else + return; + Vec_IntPush( vXors, iObj ); + for ( c = 1; c <= pCut0[0]; c++ ) + Vec_IntPush( vXors, pCut0[c] ); + if ( pCut0[0] == 2 ) + Vec_IntPush( vXors, 0 ); } /**Function************************************************************* @@ -300,7 +318,7 @@ void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_I SeeAlso [] ***********************************************************************/ -Vec_Int_t * Ree_ManDeriveAdds( Hash_IntMan_t * p, Vec_Int_t * vData ) +Vec_Int_t * Ree_ManDeriveAdds( Hash_IntMan_t * p, Vec_Int_t * vData, int fVerbose ) { int i, j, k, iObj, iObj2, Value, Truth, Truth2, CountX, CountM, Index = 0; int nEntries = Hash_IntManEntryNum(p); @@ -327,7 +345,8 @@ Vec_Int_t * Ree_ManDeriveAdds( Hash_IntMan_t * p, Vec_Int_t * vData ) } Vec_IntFree( vXors ); Vec_IntFree( vMajs ); - printf( "Detected %d shared cuts among %d hashed cuts.\n", Index, nEntries ); + //if ( fVerbose ) + // printf( "Detected %d shared cuts among %d hashed cuts.\n", Index, nEntries ); // collect nodes vXorMap = Vec_WecStart( Index ); vMajMap = Vec_WecStart( Index ); @@ -371,7 +390,7 @@ Vec_Int_t * Ree_ManDeriveAdds( Hash_IntMan_t * p, Vec_Int_t * vData ) Vec_WecFree( vMajMap ); return vAdds; } -Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ) +Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, Vec_Int_t ** pvXors, int fVerbose ) { Gia_Obj_t * pObj; int * pList0, * pList1, i, nCuts = 0; @@ -390,23 +409,24 @@ Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ) Vec_IntPush( vCuts, Gia_ObjId(p, pObj) ); Vec_IntPush( vCuts, 0xAA ); } + if ( pvXors ) *pvXors = Vec_IntAlloc( 1000 ); Gia_ManForEachAnd( p, pObj, i ) { pList0 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId0(pObj, i)) ); pList1 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId1(pObj, i)) ); - Ree_ManCutMerge( p, i, pList0, pList1, vTemp, pHash, vData ); + Ree_ManCutMerge( p, i, pList0, pList1, vTemp, pHash, vData, pvXors ? *pvXors : NULL ); Vec_IntWriteEntry( vCuts, i, Vec_IntSize(vCuts) ); Vec_IntAppend( vCuts, vTemp ); nCuts += Vec_IntEntry( vTemp, 0 ); } if ( fVerbose ) - printf( "Nodes = %d. Cuts = %d. Cuts/Node = %.2f. Ints/Node = %.2f.\n", + printf( "AIG nodes = %d. Cuts = %d. Cuts/Node = %.2f. Ints/Node = %.2f.\n", Gia_ManAndNum(p), nCuts, 1.0*nCuts/Gia_ManAndNum(p), 1.0*Vec_IntSize(vCuts)/Gia_ManAndNum(p) ); Vec_IntFree( vTemp ); Vec_IntFree( vCuts ); - vAdds = Ree_ManDeriveAdds( pHash, vData ); + vAdds = Ree_ManDeriveAdds( pHash, vData, fVerbose ); if ( fVerbose ) - printf( "Adds = %d. Total = %d. Hashed = %d. Hashed/Adds = %.2f.\n", + printf( "Adders = %d. Total cuts = %d. Hashed cuts = %d. Hashed/Adders = %.2f.\n", Vec_IntSize(vAdds)/6, Vec_IntSize(vData)/3, Hash_IntManEntryNum(pHash), 6.0*Hash_IntManEntryNum(pHash)/Vec_IntSize(vAdds) ); Vec_IntFree( vData ); Hash_IntManStop( pHash ); @@ -539,7 +559,7 @@ void Ree_ManPrintAdders( Vec_Int_t * vAdds, int fVerbose ) void Ree_ManComputeCutsTest( Gia_Man_t * p ) { abctime clk = Abc_Clock(); - Vec_Int_t * vAdds = Ree_ManComputeCuts( p, 1 ); + Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 ); int nFadds = Ree_ManCountFadds( vAdds ); Ree_ManPrintAdders( vAdds, 1 ); printf( "Detected %d FAs and %d HAs. ", nFadds, Vec_IntSize(vAdds)/6-nFadds ); |