Experiments with MFFC computation.

4 files changed, 228 insertions, 1 deletions

diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index 4203329e..3616e10c 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -1403,6 +1403,7 @@ extern void                Gia_ManFanoutStart( Gia_Man_t * p );
 extern void                Gia_ManFanoutStop( Gia_Man_t * p );
 extern void                Gia_ManStaticFanoutStart( Gia_Man_t * p );
 extern void                Gia_ManStaticFanoutStop( Gia_Man_t * p );
+extern void                Gia_ManStaticMappingFanoutStart( Gia_Man_t * p );
 /*=== giaForce.c =========================================================*/
 extern void                For_ManExperiment( Gia_Man_t * pGia, int nIters, int fClustered, int fVerbose );
 /*=== giaFrames.c =========================================================*/
@@ -1693,6 +1694,7 @@ extern int                 Gia_ObjRecognizeMuxLits( Gia_Man_t * p, Gia_Obj_t * p
 extern int                 Gia_NodeMffcSize( Gia_Man_t * p, Gia_Obj_t * pNode );
 extern int                 Gia_NodeMffcSizeMark( Gia_Man_t * p, Gia_Obj_t * pNode );
 extern int                 Gia_NodeMffcSizeSupp( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp );
+extern int                 Gia_NodeMffcMapping( Gia_Man_t * p );
 extern int                 Gia_ManHasDangling( Gia_Man_t * p );
 extern int                 Gia_ManMarkDangling( Gia_Man_t * p );
 extern Vec_Int_t *         Gia_ManGetDangling( Gia_Man_t * p );
diff --git a/src/aig/gia/giaFanout.c b/src/aig/gia/giaFanout.c
index 44e79ba2..8b104e9b 100644
--- a/src/aig/gia/giaFanout.c
+++ b/src/aig/gia/giaFanout.c
@@ -283,6 +283,89 @@ void Gia_ManStaticFanoutStart( Gia_Man_t * p )
     Vec_IntFree( vCounts );
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Compute the map of all edges.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManStartMappingFanoutMap( Gia_Man_t * p, Vec_Int_t * vFanoutNums )
+{
+    Gia_Obj_t * pObj;
+    int i, iOffset = Gia_ManObjNum(p);
+    Vec_Int_t * vEdgeMap = Vec_IntAlloc( 2 * iOffset );
+    Vec_IntFill( vEdgeMap, iOffset, 0 );
+    Gia_ManForEachObj( p, pObj, i )
+    {
+        if ( Vec_IntEntry(vFanoutNums, i) == 0 )
+            continue;
+        Vec_IntWriteEntry( vEdgeMap, i, iOffset );
+        iOffset += Vec_IntEntry( vFanoutNums, i );
+        Vec_IntFillExtra( vEdgeMap, iOffset, 0 );
+    }
+    //printf( "Fanout map is %.2fx larger than AIG manager.\n", 1.0*Vec_IntSize(vEdgeMap)/Gia_ManObjNum(p) );
+    return vEdgeMap;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Allocates static fanout.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManStaticMappingFanoutStart( Gia_Man_t * p )
+{
+    Vec_Int_t * vCounts;
+    int * pRefsOld;
+    Gia_Obj_t * pObj, * pFanin;
+    int i, k, iFan, iFanout;
+    assert( p->vFanoutNums == NULL );
+    assert( p->vFanout == NULL );
+    // recompute reference counters
+    pRefsOld = p->pLutRefs; p->pLutRefs = NULL;
+    Gia_ManSetLutRefs(p);
+    p->vFanoutNums = Vec_IntAllocArray( p->pLutRefs, Gia_ManObjNum(p) );
+    p->pLutRefs = pRefsOld;
+    // start the fanout maps
+    p->vFanout = Gia_ManStartMappingFanoutMap( p, p->vFanoutNums );
+    // incrementally add fanouts
+    vCounts = Vec_IntStart( Gia_ManObjNum(p) );
+    Gia_ManForEachLut( p, i )
+    {
+        pObj = Gia_ManObj( p, i );
+        Gia_LutForEachFanin( p, i, iFan, k )
+        {
+            pFanin = Gia_ManObj( p, iFan );
+            iFanout = Vec_IntEntry( vCounts, iFan );
+            Gia_ObjSetFanout( p, pFanin, iFanout, pObj );
+            Vec_IntAddToEntry( vCounts, iFan, 1 );
+        }
+    }
+    Gia_ManForEachCo( p, pObj, i )
+    {
+        iFan = Gia_ObjFaninId0p(p, pObj);
+        pFanin = Gia_ManObj( p, iFan );
+        iFanout = Vec_IntEntry( vCounts, iFan );
+        Gia_ObjSetFanout( p, pFanin, iFanout, pObj );
+        Vec_IntAddToEntry( vCounts, iFan, 1 );
+    }
+    // double-check the current number of fanouts added
+    Gia_ManForEachObj( p, pObj, i )
+        assert( Vec_IntEntry(vCounts, i) == Gia_ObjFanoutNum(p, pObj) );
+    Vec_IntFree( vCounts );
+}
+
 /**Function*************************************************************
 
   Synopsis    [Deallocates static fanout.]
diff --git a/src/aig/gia/giaMf.c b/src/aig/gia/giaMf.c
index 4bd08dcf..7c67fb88 100644
--- a/src/aig/gia/giaMf.c
+++ b/src/aig/gia/giaMf.c
@@ -1569,6 +1569,16 @@ static inline int Mf_CutAreaDerefed2( Mf_Man_t * p, int * pCut )
         Mf_ObjMapRefDec( p, iObj );
     return Ela1;
 }
+static inline int Mf_CutAreaDerefed2Multi( Mf_Man_t * p, int ** ppCuts, int nCuts )
+{
+    int Ela1 = 0, iObj, i;
+    Vec_IntClear( &p->vTemp );
+    for ( i = 0; i < nCuts; i++ )
+        Ela1 += Mf_CutRef2_rec( p, ppCuts[i], &p->vTemp, ABC_INFINITY );
+    Vec_IntForEachEntry( &p->vTemp, iObj, i )
+        Mf_ObjMapRefDec( p, iObj );
+    return Ela1;
+}
 
 int Mf_CutRef_rec( Mf_Man_t * p, int * pCut )
 {
@@ -1586,11 +1596,18 @@ int Mf_CutDeref_rec( Mf_Man_t * p, int * pCut )
             Count += Mf_CutDeref_rec( p, Mf_ObjCutBest(p, pCut[i]) );
     return Count;
 }
+static inline int Mf_CutAreaRefed( Mf_Man_t * p, int * pCut )
+{
+    int Ela1 = Mf_CutDeref_rec( p, pCut );
+    int Ela2 = Mf_CutRef_rec( p, pCut );
+    //assert( Ela1 == Ela2 );
+    return Ela1;
+}
 static inline int Mf_CutAreaDerefed( Mf_Man_t * p, int * pCut )
 {
     int Ela1 = Mf_CutRef_rec( p, pCut );
     int Ela2 = Mf_CutDeref_rec( p, pCut );
-    assert( Ela1 == Ela2 );
+    //assert( Ela1 == Ela2 );
     return Ela1;
 }
 static inline float Mf_CutFlow( Mf_Man_t * p, int * pCut, int * pTime )
@@ -1642,6 +1659,83 @@ static inline void Mf_ObjComputeBestCut( Mf_Man_t * p, int iObj )
 
 /**Function*************************************************************
 
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Mf_ManPrintFanoutProfile( Mf_Man_t * p, Vec_Int_t * vFanCounts )
+{
+    Gia_Man_t * pGia = p->pGia0;
+    int i, Count, nMax = Vec_IntFindMax( vFanCounts );
+    Vec_Int_t * vCounts = Vec_IntStart( nMax + 1 );
+    Vec_IntForEachEntry( vFanCounts, Count, i )
+        if ( Count && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) ) 
+            Vec_IntAddToEntry( vCounts, Count, 1 );
+    printf( "\nFanout distribution for internal nodes:\n" );
+    Vec_IntForEachEntry( vCounts, Count, i )
+        if ( Count ) printf( "Fanout = %5d : Nodes = %5d.\n", i, Count );
+    printf( "Total nodes with fanout = %d. Max fanout = %d.\n\n", Vec_IntCountPositive(vCounts), nMax );
+    Vec_IntFree( vCounts );
+}
+int Mf_ManPrintMfccStats( Mf_Man_t * p, int iObj )
+{
+    Gia_Man_t * pGia = p->pGia0;
+    int Area = Mf_ObjMapRefNum(p, iObj) > 0 ? 
+            Mf_CutAreaRefed  (p, Mf_ObjCutBest(p, iObj)) : 
+            Mf_CutAreaDerefed(p, Mf_ObjCutBest(p, iObj));
+    printf( "%5d : Level = %5d  Refs = %5d  Mffc = %5d\n", 
+        iObj, Gia_ObjLevelId(pGia, iObj), Mf_ObjMapRefNum(p, iObj), Area );
+    return Area;
+}
+void Mf_ManOptimizationOne( Mf_Man_t * p, int iObj )
+{
+    Gia_Man_t * pGia = p->pGia0;
+    int * ppCuts[32], nCuts = 0;
+    int iFanout, i, nAreaSum = 0, nAreaBest = 0;
+    // skip pivots whose MFFC fanouts are not used in the mapping or pointed to by COs
+    Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i )
+        if ( Mf_ObjMapRefNum(p, iFanout) == 0 || Gia_ObjIsCo(Gia_ManObj(pGia, iFanout)) )
+            return;
+    // print this pivot and its fanouts
+    printf( "\nPivot node = %d\n", iObj );
+    printf( "Pivot " ), Mf_ManPrintMfccStats( p, iObj );
+    Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i )
+        printf( "Node  " ), nAreaSum += Mf_ManPrintMfccStats( p, iFanout );
+    // calculate the shared MFFC
+    Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i )
+        Mf_ObjMapRefInc( p, iFanout );
+    Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i )
+        ppCuts[nCuts++] = Mf_ObjCutBest( p, iFanout );
+    nAreaBest = Mf_CutAreaDerefed2Multi( p, ppCuts, nCuts );
+    Gia_ObjForEachFanoutStaticId( pGia, iObj, iFanout, i )
+        Mf_ObjMapRefDec( p, iFanout );
+    printf( "Sum of MFFC size = %d\n", nAreaSum );
+    printf( "Shared MFFC size = %d\n", nAreaBest );
+}
+void Mf_ManOptimization( Mf_Man_t * p )
+{
+    int nOutMax = 3;
+    Gia_Man_t * pGia = p->pGia0;
+    int i, Count, nNodes = Gia_NodeMffcMapping( pGia );
+    Gia_ManLevelNum( pGia );
+    Gia_ManStaticMappingFanoutStart( pGia );
+    Mf_ManPrintFanoutProfile( p, pGia->vFanoutNums );
+    printf( "\nIndividual logic cones:\n" );
+    Vec_IntForEachEntry( pGia->vFanoutNums, Count, i )
+        if ( Count >= 2 && Count <= nOutMax && Gia_ObjIsAnd(Gia_ManObj(pGia, i)) )
+            Mf_ManOptimizationOne( p, i );
+    printf( "\nFinished printing individual logic cones.\n" );
+    Gia_ManStaticFanoutStop( pGia );
+    Vec_IntFreeP( &pGia->vMapping );
+}
+
+/**Function*************************************************************
+
   Synopsis    [Technology mappping.]
 
   Description []
@@ -1682,6 +1776,7 @@ Gia_Man_t * Mf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars )
     p->fUseEla = 1;
     for ( ; p->Iter < p->pPars->nRounds + pPars->nRoundsEla; p->Iter++ )
         Mf_ManComputeMapping( p );
+    //Mf_ManOptimization( p );
     if ( pPars->fVeryVerbose && pPars->fCutMin )
         Vec_MemDumpTruthTables( p->vTtMem, Gia_ManName(p->pGia), pPars->nLutSize );
     if ( pPars->fCutMin )
diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c
index 2e1830c5..b8f33b69 100644
--- a/src/aig/gia/giaUtil.c
+++ b/src/aig/gia/giaUtil.c
@@ -1236,6 +1236,53 @@ int Gia_NodeMffcSizeSupp( Gia_Man_t * p, Gia_Obj_t * pNode, Vec_Int_t * vSupp )
 
 /**Function*************************************************************
 
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Gia_NodeMffcMapping_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vMapping, Vec_Int_t * vSupp )
+{
+    Gia_Obj_t * pObj; int i, iNode, Count = 1;
+    if ( !iObj || Vec_IntEntry(vMapping, iObj) )
+        return 0;
+    pObj = Gia_ManObj( p, iObj );
+    if ( Gia_ObjIsCi(pObj) )
+        return 0;
+    Gia_NodeMffcSizeSupp( p, pObj, vSupp );
+    Vec_IntSort( vSupp, 0 );
+    Vec_IntWriteEntry( vMapping, iObj, Vec_IntSize(vMapping) );
+    Vec_IntPush( vMapping, Vec_IntSize(vSupp) );
+    Vec_IntAppend( vMapping, vSupp );
+    Vec_IntPush( vMapping, iObj );
+    Vec_IntForEachEntry( vSupp, iNode, i )
+        Count += Gia_NodeMffcMapping_rec( p, iNode, vMapping, vSupp );
+    return Count;
+}
+int Gia_NodeMffcMapping( Gia_Man_t * p )
+{
+    int i, Id, Count = 0;
+    int * pRefsOld;
+    Vec_Int_t * vMapping, * vSupp = Vec_IntAlloc( 100 );
+    vMapping = Vec_IntAlloc( 2 * Gia_ManObjNum(p) );
+    Vec_IntFill( vMapping, Gia_ManObjNum(p), 0 );
+    pRefsOld = p->pRefs; p->pRefs = NULL;
+    Gia_ManCreateRefs( p ); 
+    p->pRefs = pRefsOld;
+    Gia_ManForEachCoDriverId( p, Id, i )
+        Count += Gia_NodeMffcMapping_rec( p, Id, vMapping, vSupp );
+    Vec_IntFree( vSupp );
+    p->vMapping = vMapping;
+    //printf( "Mapping is %.2fx larger than AIG manager.\n", 1.0*Vec_IntSize(vMapping)/Gia_ManObjNum(p) );
+    return Count;
+}
+
+/**Function*************************************************************
+
   Synopsis    [Returns 1 if AIG has dangling nodes.]
 
   Description []