Multiplexer profiling.

5 files changed, 369 insertions, 129 deletions

diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index c890b165..d09129a5 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -336,7 +336,7 @@ static inline int          Gia_ObjIsCi( Gia_Obj_t * pObj )                     {
 static inline int          Gia_ObjIsCo( Gia_Obj_t * pObj )                     { return pObj->fTerm && pObj->iDiff0 != GIA_NONE; } 
 static inline int          Gia_ObjIsAnd( Gia_Obj_t * pObj )                    { return!pObj->fTerm && pObj->iDiff0 != GIA_NONE; } 
 static inline int          Gia_ObjIsXor( Gia_Obj_t * pObj )                    { return Gia_ObjIsAnd(pObj) && pObj->iDiff0 < pObj->iDiff1; } 
-static inline int          Gia_ObjIsMux( Gia_Man_t * p, Gia_Obj_t * pObj )     { return p->pMuxes && p->pMuxes[Gia_ObjId(p, pObj)] > 0;    } 
+static inline int          Gia_ObjIsMux( Gia_Man_t * p, int iObj )             { return p->pMuxes && p->pMuxes[iObj] > 0;        } 
 static inline int          Gia_ObjIsCand( Gia_Obj_t * pObj )                   { return Gia_ObjIsAnd(pObj) || Gia_ObjIsCi(pObj); } 
 static inline int          Gia_ObjIsConst0( Gia_Obj_t * pObj )                 { return pObj->iDiff0 == GIA_NONE && pObj->iDiff1 == GIA_NONE; } 
 static inline int          Gia_ManObjIsConst0( Gia_Man_t * p, Gia_Obj_t * pObj){ return pObj == p->pObjs;                        } 
@@ -419,8 +419,10 @@ static inline int          Gia_ObjRefInc( Gia_Man_t * p, Gia_Obj_t * pObj )    {
 static inline int          Gia_ObjRefDec( Gia_Man_t * p, Gia_Obj_t * pObj )    { assert(p->pRefs); return --p->pRefs[Gia_ObjId(p, pObj)];  }
 static inline void         Gia_ObjRefFanin0Inc(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefInc(p, Gia_ObjFanin0(pObj));  }
 static inline void         Gia_ObjRefFanin1Inc(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefInc(p, Gia_ObjFanin1(pObj));  }
+static inline void         Gia_ObjRefFanin2Inc(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefInc(p, Gia_ObjFanin2(p, pObj));  }
 static inline void         Gia_ObjRefFanin0Dec(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefDec(p, Gia_ObjFanin0(pObj));  }
 static inline void         Gia_ObjRefFanin1Dec(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefDec(p, Gia_ObjFanin1(pObj));  }
+static inline void         Gia_ObjRefFanin2Dec(Gia_Man_t * p, Gia_Obj_t * pObj){ assert(p->pRefs); Gia_ObjRefDec(p, Gia_ObjFanin2(p, pObj));  }
 
 static inline void         Gia_ObjSetTravIdCurrent( Gia_Man_t * p, Gia_Obj_t * pObj )         { assert( Gia_ObjId(p, pObj) < p->nTravIdsAlloc ); p->pTravIds[Gia_ObjId(p, pObj)] = p->nTravIds;                    }
 static inline void         Gia_ObjSetTravIdPrevious( Gia_Man_t * p, Gia_Obj_t * pObj )        { assert( Gia_ObjId(p, pObj) < p->nTravIdsAlloc ); p->pTravIds[Gia_ObjId(p, pObj)] = p->nTravIds - 1;                }
@@ -823,6 +825,8 @@ static inline int         Gia_ObjLutFanin( Gia_Man_t * p, int Id, int i )   { re
     for ( i = 0; (i < p->nObjs) && ((pObj) = Gia_ManObj(p, i)); i++ )      if ( !Gia_ObjIsCand(pObj) ) {} else
 #define Gia_ManForEachAndReverse( p, pObj, i )                          \
     for ( i = p->nObjs - 1; (i > 0) && ((pObj) = Gia_ManObj(p, i)); i-- )  if ( !Gia_ObjIsAnd(pObj) ) {} else
+#define Gia_ManForEachMux( p, pObj, i )                                 \
+    for ( i = 0; (i < p->nObjs) && ((pObj) = Gia_ManObj(p, i)); i++ )      if ( !Gia_ObjIsMux(p, i) ) {} else
 #define Gia_ManForEachCi( p, pObj, i )                                  \
     for ( i = 0; (i < Vec_IntSize(p->vCis)) && ((pObj) = Gia_ManCi(p, i)); i++ )
 #define Gia_ManForEachCo( p, pObj, i )                                  \
@@ -1163,6 +1167,7 @@ extern void                Gia_ManMarkFanoutDrivers( Gia_Man_t * p );
 extern void                Gia_ManSwapPos( Gia_Man_t * p, int i );
 extern Vec_Int_t *         Gia_ManSaveValue( Gia_Man_t * p );
 extern void                Gia_ManLoadValue( Gia_Man_t * p, Vec_Int_t * vValues );
+extern Vec_Int_t *         Gia_ManFirstFanouts( Gia_Man_t * p );
 
 
 /*=== giaCTas.c ===========================================================*/
diff --git a/src/aig/gia/giaDup.c b/src/aig/gia/giaDup.c
index d533dc1f..965d6ce3 100644
--- a/src/aig/gia/giaDup.c
+++ b/src/aig/gia/giaDup.c
@@ -852,7 +852,7 @@ Gia_Man_t * Gia_ManDupMarked( Gia_Man_t * p )
         {
             if ( Gia_ObjIsXor(pObj) )
                 pObj->Value = Gia_ManAppendXorReal( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
-            else if ( Gia_ObjIsMux(p, pObj) )
+            else if ( Gia_ObjIsMux(p, i) )
                 pObj->Value = Gia_ManAppendMuxReal( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
             else
                 pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
@@ -2444,132 +2444,6 @@ Gia_Man_t * Gia_ManDupFromVecs( Gia_Man_t * p, Vec_Int_t * vCis, Vec_Int_t * vAn
     return pNew;
 }
 
-/**Function*************************************************************
-
-  Synopsis    [Derives GIA with MUXes.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p )
-{
-    Gia_Man_t * pNew, * pTemp;
-    Gia_Obj_t * pObj, * pFan0, * pFan1, * pFanC;
-    int i;
-    assert( p->pMuxes == NULL );
-    // start the new manager
-    pNew = Gia_ManStart( 5000 );
-    pNew->pName = Abc_UtilStrsav( p->pName );
-    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
-    pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
-    // create constant
-    Gia_ManConst0(p)->Value = 0;
-    // create PIs
-    Gia_ManForEachCi( p, pObj, i )
-        pObj->Value = Gia_ManAppendCi( pNew );
-    // create internal nodes
-    Gia_ManHashStart( pNew );
-    Gia_ManForEachAnd( p, pObj, i )
-    {
-        if ( !Gia_ObjIsMuxType(pObj) )
-            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
-        else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
-            pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) );
-        else
-        {
-            pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 );
-            pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) );
-        }
-    }
-    Gia_ManHashStop( pNew );
-    // create ROs
-    Gia_ManForEachCo( p, pObj, i )
-        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
-    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
-    // perform cleanup
-    pNew = Gia_ManCleanup( pTemp = pNew );
-    Gia_ManStop( pTemp );
-    return pNew;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Derives GIA without MUXes.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p )
-{
-    Gia_Man_t * pNew, * pTemp;
-    Gia_Obj_t * pObj;
-    int i;
-    assert( p->pMuxes != NULL );
-    // start the new manager
-    pNew = Gia_ManStart( 5000 );
-    pNew->pName = Abc_UtilStrsav( p->pName );
-    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
-    // create constant
-    Gia_ManConst0(p)->Value = 0;
-    // create PIs
-    Gia_ManForEachCi( p, pObj, i )
-        pObj->Value = Gia_ManAppendCi( pNew );
-    // create internal nodes
-    Gia_ManHashStart( pNew );
-    Gia_ManForEachAnd( p, pObj, i )
-    {
-        if ( Gia_ObjIsMux(p, pObj) )
-            pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
-        else if ( Gia_ObjIsXor(pObj) )
-            pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
-        else 
-            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
-    }
-    Gia_ManHashStop( pNew );
-    // create ROs
-    Gia_ManForEachCo( p, pObj, i )
-        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
-    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
-    // perform cleanup
-    pNew = Gia_ManCleanup( pTemp = pNew );
-    Gia_ManStop( pTemp );
-    return pNew;
-}
-
-/**Function*************************************************************
-
-  Synopsis    [Test these procedures.]
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Gia_Man_t * Gia_ManDupMuxesTest( Gia_Man_t * p )
-{
-    Gia_Man_t * pNew, * pNew2;
-    pNew = Gia_ManDupMuxes( p );
-    pNew2 = Gia_ManDupNoMuxes( pNew );
-    Gia_ManPrintStats( p, 0, 0, 0 );
-    Gia_ManPrintStats( pNew, 0, 0, 0 );
-    Gia_ManPrintStats( pNew2, 0, 0, 0 );
-    Gia_ManStop( pNew );
-//    Gia_ManStop( pNew2 );
-    return pNew2;
-}
-
-
-
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/aig/gia/giaMuxes.c b/src/aig/gia/giaMuxes.c
new file mode 100644
index 00000000..479d75e7
--- /dev/null
+++ b/src/aig/gia/giaMuxes.c
@@ -0,0 +1,322 @@
+/**CFile****************************************************************
+
+  FileName    [giaMuxes.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Scalable AIG package.]
+
+  Synopsis    [Multiplexer profiling algorithm.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: giaMuxes.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "gia.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Derives GIA with MUXes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManDupMuxes( Gia_Man_t * p )
+{
+    Gia_Man_t * pNew, * pTemp;
+    Gia_Obj_t * pObj, * pFan0, * pFan1, * pFanC;
+    int i;
+    assert( p->pMuxes == NULL );
+    // start the new manager
+    pNew = Gia_ManStart( 5000 );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    pNew->pMuxes = ABC_CALLOC( unsigned, pNew->nObjsAlloc );
+    // create constant
+    Gia_ManConst0(p)->Value = 0;
+    // create PIs
+    Gia_ManForEachCi( p, pObj, i )
+        pObj->Value = Gia_ManAppendCi( pNew );
+    // create internal nodes
+    Gia_ManHashStart( pNew );
+    Gia_ManForEachAnd( p, pObj, i )
+    {
+        if ( !Gia_ObjIsMuxType(pObj) )
+            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+        else if ( Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
+            pObj->Value = Gia_ManHashXorReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)) );
+        else
+        {
+            pFanC = Gia_ObjRecognizeMux( pObj, &pFan1, &pFan0 );
+            pObj->Value = Gia_ManHashMuxReal( pNew, Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFanC)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan1)), Gia_ObjLitCopy(p, Gia_ObjToLit(p, pFan0)) );
+        }
+    }
+    Gia_ManHashStop( pNew );
+    // create ROs
+    Gia_ManForEachCo( p, pObj, i )
+        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
+    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
+    // perform cleanup
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives GIA without MUXes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManDupNoMuxes( Gia_Man_t * p )
+{
+    Gia_Man_t * pNew, * pTemp;
+    Gia_Obj_t * pObj;
+    int i;
+    assert( p->pMuxes != NULL );
+    // start the new manager
+    pNew = Gia_ManStart( 5000 );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    // create constant
+    Gia_ManConst0(p)->Value = 0;
+    // create PIs
+    Gia_ManForEachCi( p, pObj, i )
+        pObj->Value = Gia_ManAppendCi( pNew );
+    // create internal nodes
+    Gia_ManHashStart( pNew );
+    Gia_ManForEachAnd( p, pObj, i )
+    {
+        if ( Gia_ObjIsMux(p, i) )
+            pObj->Value = Gia_ManHashMux( pNew, Gia_ObjFanin2Copy(p, pObj), Gia_ObjFanin1Copy(pObj), Gia_ObjFanin0Copy(pObj) );
+        else if ( Gia_ObjIsXor(pObj) )
+            pObj->Value = Gia_ManHashXor( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+        else 
+            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+    }
+    Gia_ManHashStop( pNew );
+    // create ROs
+    Gia_ManForEachCo( p, pObj, i )
+        pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
+    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
+    // perform cleanup
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Test these procedures.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Gia_Man_t * Gia_ManDupMuxesTest( Gia_Man_t * p )
+{
+    Gia_Man_t * pNew, * pNew2;
+    pNew = Gia_ManDupMuxes( p );
+    pNew2 = Gia_ManDupNoMuxes( pNew );
+    Gia_ManPrintStats( p, 0, 0, 0 );
+    Gia_ManPrintStats( pNew, 0, 0, 0 );
+    Gia_ManPrintStats( pNew2, 0, 0, 0 );
+    Gia_ManStop( pNew );
+//    Gia_ManStop( pNew2 );
+    return pNew2;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the size of MUX structure.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Gia_MuxRef_rec( Gia_Man_t * p, int iObj )
+{
+    Gia_Obj_t * pObj;
+    if ( !Gia_ObjIsMux(p, iObj) )
+        return 0;
+    pObj = Gia_ManObj( p, iObj );
+    if ( Gia_ObjRefInc(p, pObj) )
+        return 0;
+    return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
+           Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
+           Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
+}
+int Gia_MuxRef( Gia_Man_t * p, int iObj )
+{
+    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+    assert( Gia_ObjIsMux(p, iObj) );
+    return Gia_MuxRef_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
+           Gia_MuxRef_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
+           Gia_MuxRef_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
+}
+int Gia_MuxDeref_rec( Gia_Man_t * p, int iObj )
+{
+    Gia_Obj_t * pObj;
+    if ( !Gia_ObjIsMux(p, iObj) )
+        return 0;
+    pObj = Gia_ManObj( p, iObj );
+    if ( Gia_ObjRefDec(p, pObj) )
+        return 0;
+    return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
+           Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
+           Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
+}
+int Gia_MuxDeref( Gia_Man_t * p, int iObj )
+{
+    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+    assert( Gia_ObjIsMux(p, iObj) );
+    return Gia_MuxDeref_rec( p, Gia_ObjFaninId0p(p, pObj) ) + 
+           Gia_MuxDeref_rec( p, Gia_ObjFaninId1p(p, pObj) ) + 
+           Gia_MuxDeref_rec( p, Gia_ObjFaninId2p(p, pObj) ) + 1;
+}
+int Gia_MuxMffcSize( Gia_Man_t * p, int iObj )
+{
+    int Count1, Count2;
+    if ( !Gia_ObjIsMux(p, iObj) )
+        return 0;
+    Count1 = Gia_MuxDeref( p, iObj );
+    Count2 = Gia_MuxRef( p, iObj );
+    assert( Count1 == Count2 );
+    return Count1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_MuxStructPrint_rec( Gia_Man_t * p, int iObj, int fFirst )
+{
+    Gia_Obj_t * pObj = Gia_ManObj( p, iObj );
+    if ( !fFirst && (!Gia_ObjIsMux(p, iObj) || Gia_ObjRefNumId(p, iObj) > 0) )
+        return;
+    printf( " [(%s", Gia_ObjFaninC2(p, pObj)? "!": "" );
+    if ( !Gia_ObjIsMux(p, Gia_ObjFaninId2p(p, pObj)) )
+        printf( "%d", Gia_ObjFaninId2p(p, pObj) );
+    else
+        Gia_MuxStructPrint_rec( p, Gia_ObjFaninId2p(p, pObj), 0 );
+    printf( ")" );
+    Gia_MuxStructPrint_rec( p, Gia_ObjFaninId0p(p, pObj), 0 );
+    printf( "|" );
+    Gia_MuxStructPrint_rec( p, Gia_ObjFaninId1p(p, pObj), 0 );
+    printf( "] " );
+}
+void Gia_MuxStructPrint( Gia_Man_t * p, int iObj )
+{
+    int Count1, Count2;
+    assert( Gia_ObjIsMux(p, iObj) );
+    Count1 = Gia_MuxDeref( p, iObj );
+    Gia_MuxStructPrint_rec( p, iObj, 1 );
+    Count2 = Gia_MuxRef( p, iObj );
+    assert( Count1 == Count2 );
+    printf( "\n" );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_ManMuxProfiling( Gia_Man_t * p )
+{
+    Gia_Man_t * pNew;
+    Gia_Obj_t * pObj;
+    Vec_Int_t * vFans;
+    Vec_Int_t * vCounts;
+    int i, nRefs, Size, Count, Total = 0, Roots = 0;
+
+    pNew = Gia_ManDupMuxes( p );
+    Gia_ManCreateRefs( pNew );
+    Gia_ManForEachCo( pNew, pObj, i )
+        Gia_ObjRefFanin0Inc( pNew, pObj );
+
+    vFans = Gia_ManFirstFanouts( pNew );
+    vCounts = Vec_IntStart( 100 );
+    Gia_ManForEachMux( pNew, pObj, i )
+    {
+        Total++;
+        nRefs = Gia_ObjRefNumId(pNew, i);
+        assert( nRefs > 0 );
+        if ( nRefs > 1 || !Gia_ObjIsMux(pNew, Vec_IntEntry(vFans, i)) )
+        {
+            Roots++;
+            Size = Gia_MuxMffcSize(pNew, i);
+            Vec_IntAddToEntry( vCounts, Abc_MinInt(Size, 99), 1 );
+
+            if ( Size > 3 )
+            {
+                printf( "%d ", Size );
+                Gia_MuxStructPrint( pNew, i );
+            }
+        }
+    }
+    printf( "MUXes: Total = %d. Roots = %d.\n", Total, Roots );
+
+    Vec_IntForEachEntry( vCounts, Count, i )
+        if ( Count )
+            printf( "%d=%d ", i, Count );
+    printf( "\n" );
+
+    Vec_IntFree( vCounts );
+    Vec_IntFree( vFans );
+    Gia_ManStop( pNew );
+}
+
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/aig/gia/giaUtil.c b/src/aig/gia/giaUtil.c
index bec23f8c..99557c7a 100644
--- a/src/aig/gia/giaUtil.c
+++ b/src/aig/gia/giaUtil.c
@@ -555,6 +555,8 @@ void Gia_ManCreateRefs( Gia_Man_t * p )
         {
             Gia_ObjRefFanin0Inc( p, pObj );
             Gia_ObjRefFanin1Inc( p, pObj );
+            if ( Gia_ObjIsMux(p, i) )
+                Gia_ObjRefFanin2Inc( p, pObj );
         }
         else if ( Gia_ObjIsCo(pObj) )
             Gia_ObjRefFanin0Inc( p, pObj );
@@ -1124,7 +1126,7 @@ void Gia_ObjPrint( Gia_Man_t * p, Gia_Obj_t * pObj )
         printf( "XOR( %4d%s, %4d%s )", 
             Gia_ObjFaninId0p(p, pObj), (Gia_ObjFaninC0(pObj)? "\'" : " "), 
             Gia_ObjFaninId1p(p, pObj), (Gia_ObjFaninC1(pObj)? "\'" : " ") );
-    else if ( Gia_ObjIsMux(p, pObj) )
+    else if ( Gia_ObjIsMux(p, Gia_ObjId(p, pObj)) )
         printf( "MUX( %4d%s, %4d%s, %4d%s )", 
             Gia_ObjFaninId2p(p, pObj), (Gia_ObjFaninC2(p, pObj)? "\'" : " "), 
             Gia_ObjFaninId1p(p, pObj), (Gia_ObjFaninC1(pObj)? "\'" : " "), 
@@ -1405,6 +1407,42 @@ void Gia_ManLoadValue( Gia_Man_t * p, Vec_Int_t * vValues )
 }
 
 
+/**Function*************************************************************
+
+  Synopsis    [Returns the array containing the first fanout of each object.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Gia_ManFirstFanouts( Gia_Man_t * p )
+{
+    Vec_Int_t * vFans = Vec_IntStart( Gia_ManObjNum(p) );
+    Gia_Obj_t * pObj;
+    int i;
+    Gia_ManForEachObj( p, pObj, i )
+    {
+        if ( Gia_ObjIsAnd(pObj) )
+        {
+            if ( Vec_IntEntry(vFans, Gia_ObjFaninId0p(p, pObj)) == 0 )
+                Vec_IntWriteEntry(vFans, Gia_ObjFaninId0p(p, pObj), i);
+            if ( Vec_IntEntry(vFans, Gia_ObjFaninId1p(p, pObj)) == 0 )
+                Vec_IntWriteEntry(vFans, Gia_ObjFaninId1p(p, pObj), i);
+            if ( Gia_ObjIsMux(p, i) && Vec_IntEntry(vFans, Gia_ObjFaninId2p(p, pObj)) == 0 )
+                Vec_IntWriteEntry(vFans, Gia_ObjFaninId2p(p, pObj), i);
+        }
+        else if ( Gia_ObjIsCo(pObj) )
+        {
+            if ( Vec_IntEntry(vFans, Gia_ObjFaninId0p(p, pObj)) == 0 )
+                Vec_IntWriteEntry(vFans, Gia_ObjFaninId0p(p, pObj), i);
+        }
+    }
+    return vFans;
+}
+
 #include "base/main/mainInt.h"
 
 /**Function*************************************************************
diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make
index 8573584c..34985059 100644
--- a/src/aig/gia/module.make
+++ b/src/aig/gia/module.make
@@ -29,6 +29,7 @@ SRC +=    src/aig/gia/giaAig.c \
     src/aig/gia/giaMan.c \
     src/aig/gia/giaMem.c \
     src/aig/gia/giaMini.c \
+    src/aig/gia/giaMuxes.c \
     src/aig/gia/giaPat.c \
     src/aig/gia/giaRetime.c \
     src/aig/gia/giaScl.c \