Experiments with MUX decomposition.

2 files changed, 134 insertions, 1 deletions

diff --git a/src/aig/gia/giaSimBase.c b/src/aig/gia/giaSimBase.c
index 2e61c1ff..9e7033ab 100644
--- a/src/aig/gia/giaSimBase.c
+++ b/src/aig/gia/giaSimBase.c
@@ -149,6 +149,85 @@ void Gia_ManSimPatWrite( char * pFileName, Vec_Wrd_t * vSimsIn, int nWords )
     Vec_WrdDumpHex( pFileName, vSimsIn, nWords, 0 );
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+word * Gia_ManDeriveFuncs( Gia_Man_t * p )
+{
+    int nVars2 = (Gia_ManCiNum(p) + 6)/2;
+    int nVars3 = Gia_ManCiNum(p) - nVars2;
+    int nWords = Abc_Truth6WordNum( Gia_ManCiNum(p) );
+    int nWords2 = Abc_Truth6WordNum( nVars2 );
+    word * pRes = ABC_ALLOC( word, Gia_ManCoNum(p) * nWords );
+    Vec_Wrd_t * vSims = Vec_WrdStart( nWords2 * Gia_ManObjNum(p) );
+    Vec_Ptr_t * vTruths = Vec_PtrAllocTruthTables( nVars2 );
+    Gia_Obj_t * pObj; int i, v, m;
+    Gia_ManForEachCi( p, pObj, i )
+        assert( Gia_ObjId(p, pObj) == i+1 );
+    for ( i = 0; i < nVars2; i++ )
+        Abc_TtCopy( Vec_WrdEntryP(vSims, nWords2*(i+1)), (word *)Vec_PtrEntry(vTruths, i), nWords2, 0 );
+    Vec_PtrFree( vTruths );
+    for ( m = 0; m < (1 << nVars3); m++ )
+    {
+        for ( v = 0; v < nVars3; v++ )
+            Abc_TtConst( Vec_WrdEntryP(vSims, nWords2*(nVars2+v+1)), nWords2, (m >> v) & 1 );
+        Gia_ManForEachAnd( p, pObj, i ) 
+            Gia_ManSimPatSimAnd( p, i, pObj, nWords2, vSims );
+        Gia_ManForEachCo( p, pObj, i )
+            Gia_ManSimPatSimPo( p, Gia_ObjId(p, pObj), pObj, nWords2, vSims );
+        Gia_ManForEachCo( p, pObj, i )
+            Abc_TtCopy( pRes + i*nWords + m*nWords2, Vec_WrdEntryP(vSims, nWords2*Gia_ObjId(p, pObj)), nWords2, 0 );
+    }
+    Vec_WrdFree( vSims );
+    return pRes;
+}
+Gia_Man_t * Gia_ManPerformMuxDec( Gia_Man_t * p )
+{
+    extern int Gia_ManFindMuxTree_rec( Gia_Man_t * pNew, int * pCtrl, int nCtrl, Vec_Int_t * vData, int Shift );
+    extern int Kit_TruthToGia( Gia_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory, Vec_Int_t * vLeaves, int fHash );
+    int nWords = Abc_Truth6WordNum( Gia_ManCiNum(p) );
+    int nCofs = 1 << (Gia_ManCiNum(p) - 6);
+    word * pRes = Gia_ManDeriveFuncs( p );
+    Vec_Int_t * vMemory = Vec_IntAlloc( 1 << 16 );
+    Vec_Int_t * vLeaves = Vec_IntAlloc( 6 );
+    Vec_Int_t * vCtrls  = Vec_IntAlloc( nCofs );
+    Vec_Int_t * vDatas  = Vec_IntAlloc( Gia_ManCoNum(p) );
+    Gia_Man_t * pNew, * pTemp; int i, o;
+    pNew = Gia_ManStart( Gia_ManObjNum(p) );
+    pNew->pName = Abc_UtilStrsav( p->pName );
+    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+    Gia_ManConst0(p)->Value = 0;
+    for ( i = 0; i < Gia_ManCiNum(p); i++ )
+        Vec_IntPush( i < 6 ? vLeaves : vCtrls, Gia_ManAppendCi(pNew) );
+    Gia_ManHashAlloc( pNew );
+    for ( o = 0; o < Gia_ManCoNum(p); o++ )
+    {
+        Vec_IntClear( vDatas );
+        for ( i = 0; i < nWords; i++ )
+            Vec_IntPush( vDatas, Kit_TruthToGia(pNew, (unsigned *)(pRes+o*nWords+i), 6, vMemory, vLeaves, 1) );
+        Gia_ManAppendCo( pNew, Gia_ManFindMuxTree_rec(pNew, Vec_IntArray(vCtrls), Vec_IntSize(vCtrls), vDatas, 0) );
+    }
+    Gia_ManHashStop( pNew );
+    ABC_FREE( pRes );
+    Vec_IntFree( vMemory );
+    Vec_IntFree( vLeaves );
+    Vec_IntFree( vCtrls );
+    Vec_IntFree( vDatas );   
+    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+
 /**Function*************************************************************
 
   Synopsis    []
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 913a8981..9e24d2c0 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -400,6 +400,7 @@ static int Abc_CommandAbc9Status             ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandAbc9MuxProfile         ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9MuxPos             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9MuxStr             ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9MuxDec             ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9PrintTruth         ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Unate              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandAbc9Rex2Gia            ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1129,6 +1130,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "ABC9",         "&profile",      Abc_CommandAbc9MuxProfile,   0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&muxpos",       Abc_CommandAbc9MuxPos,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&muxstr",       Abc_CommandAbc9MuxStr,       0 );
+    Cmd_CommandAdd( pAbc, "ABC9",         "&muxdec",       Abc_CommandAbc9MuxDec,       0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&print_truth",  Abc_CommandAbc9PrintTruth,   0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&unate",        Abc_CommandAbc9Unate,        0 );
     Cmd_CommandAdd( pAbc, "ABC9",         "&rex2gia",      Abc_CommandAbc9Rex2Gia,      0 );
@@ -31728,6 +31730,58 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandAbc9MuxDec( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern Gia_Man_t * Gia_ManPerformMuxDec( Gia_Man_t * p );
+    Gia_Man_t * pGia;
+    int c, fVerbose = 0;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "vh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+        case 'v':
+            fVerbose ^= 1;
+            break;
+        case 'h':
+            goto usage;
+        default:
+            goto usage;
+        }
+    }
+    if ( pAbc->pGia == NULL )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9MuxDec(): There is no AIG.\n" );
+        return 1;
+    }
+    if ( Gia_ManCiNum(pAbc->pGia) <= 6 || Gia_ManCiNum(pAbc->pGia) > 26 )
+    {
+        Abc_Print( -1, "Abc_CommandAbc9MuxDec(): The number of inputs is wrong.\n" );
+        return 1;
+    }
+    pGia = Gia_ManPerformMuxDec( pAbc->pGia );
+    Abc_FrameUpdateGia( pAbc, pGia );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: &muxdec [-vh]\n" );
+    Abc_Print( -2, "\t         performs restructuring\n" );
+    Abc_Print( -2, "\t-v     : toggle verbose output [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h     : print the command usage\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9PrintTruth( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     extern word Gia_LutComputeTruth6Simple( Gia_Man_t * p, int iPo );
@@ -48930,7 +48984,7 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )
         Abc_Print( -1, "Abc_CommandAbc9Test(): There is no AIG.\n" );
         return 1;
     }
-    Abc_FrameUpdateGia( pAbc, Gia_ManPerformNewResub(pAbc->pGia, 10, 8, 1, 1) );
+    Abc_FrameUpdateGia( pAbc, Gia_ManPerformNewResub(pAbc->pGia, 100, 8, 1, 1) );
 //    printf( "AIG in \"%s\" has the sum of output support sizes equal to %d.\n", pAbc->pGia->pSpec, Gia_ManSumTotalOfSupportSizes(pAbc->pGia) );
     //Gia_ManExtractTest( pAbc->pGia );
     //Abc_Tt6MinTest2( pAbc->pGia );