Version abc90118

1 files changed, 521 insertions, 0 deletions

diff --git a/src/map/amap/amapMerge.c b/src/map/amap/amapMerge.c
new file mode 100644
index 00000000..b024616e
--- /dev/null
+++ b/src/map/amap/amapMerge.c
@@ -0,0 +1,521 @@
+/**CFile****************************************************************
+
+  FileName    [amapMerge.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Technology mapper for standard cells.]
+
+  Synopsis    [Computing cuts for the node.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: amapMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "amapInt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Creates new cut and adds it to storage.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Amap_Cut_t * Amap_ManSetupPis( Amap_Man_t * p )
+{
+    Amap_Obj_t * pObj;
+    Amap_Cut_t * pCut;
+    int i, nBytes = sizeof(Amap_Cut_t) + sizeof(int);
+    char * pBuffer = ALLOC( char, Amap_ManPiNum(p) * nBytes );
+    Amap_ManForEachPi( p, pObj, i )
+    {
+        pCut = (Amap_Cut_t *)( pBuffer + i*nBytes );
+        pCut->iMat = 0;
+        pCut->fInv = 0;
+        pCut->nFans = 1;
+        pCut->Fans[0] = Amap_Var2Lit( pObj->Id, 0 );
+        pObj->pData = pCut;
+        pObj->nCuts = 1;
+        pObj->EstRefs = (float)1.0;
+    }
+    return (Amap_Cut_t *)pBuffer;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Creates new cut and adds it to storage.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Amap_Cut_t * Amap_ManCutStore( Amap_Man_t * p, Amap_Cut_t * pCut, int fCompl )
+{
+    Amap_Cut_t * pNew;
+    int iFan, nBytes = sizeof(Amap_Cut_t) + sizeof(int) * pCut->nFans + sizeof(Amap_Cut_t *);
+    pNew = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes );
+    pNew->iMat  = pCut->iMat;
+    pNew->fInv  = pCut->fInv ^ fCompl;
+    pNew->nFans = pCut->nFans;
+    memcpy( pNew->Fans, pCut->Fans, sizeof(int) * pCut->nFans );
+    // add it to storage
+    iFan = Amap_Var2Lit( pNew->iMat, pNew->fInv );
+    if ( p->ppCutsTemp[ iFan ] == NULL )
+        Vec_IntPushOrder( p->vTemp, iFan );
+    *Amap_ManCutNextP( pNew ) = p->ppCutsTemp[ iFan ];
+    p->ppCutsTemp[ iFan ] = pNew;
+    return pNew;
+} 
+
+/**Function*************************************************************
+
+  Synopsis    [Creates new cut and adds it to storage.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Amap_Cut_t * Amap_ManCutCreate( Amap_Man_t * p, 
+    Amap_Cut_t * pCut0, Amap_Cut_t * pCut1, int iMat )
+{
+    Amap_Cut_t * pCut;
+    int i, nSize  = pCut0->nFans + pCut1->nFans;
+    int nBytes = sizeof(Amap_Cut_t) + sizeof(int) * nSize + sizeof(Amap_Cut_t *);
+    assert( pCut0->iMat >= pCut1->iMat );
+    pCut = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes );
+    pCut->iMat  = iMat;
+    pCut->fInv  = 0;
+    pCut->nFans = nSize;
+    for ( i = 0; i < (int)pCut0->nFans; i++ )
+        pCut->Fans[i] = pCut0->Fans[i];
+    for ( i = 0; i < (int)pCut1->nFans; i++ )
+        pCut->Fans[pCut0->nFans+i] = pCut1->Fans[i];
+    // add it to storage
+    if ( p->ppCutsTemp[ pCut->iMat ] == NULL )
+        Vec_IntPushOrder( p->vTemp, pCut->iMat );
+    *Amap_ManCutNextP( pCut ) = p->ppCutsTemp[ pCut->iMat ];
+    p->ppCutsTemp[ pCut->iMat ] = pCut;
+    return pCut;
+} 
+
+/**Function*************************************************************
+
+  Synopsis    [Creates new cut and adds it to storage.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Amap_Cut_t * Amap_ManCutCreate3( Amap_Man_t * p, 
+    Amap_Cut_t * pCut0, Amap_Cut_t * pCut1, Amap_Cut_t * pCut2, int iMat )
+{
+    Amap_Cut_t * pCut;
+    int i, nSize  = pCut0->nFans + pCut1->nFans + pCut2->nFans;
+    int nBytes = sizeof(Amap_Cut_t) + sizeof(int) * nSize + sizeof(Amap_Cut_t *);
+    pCut = (Amap_Cut_t *)Aig_MmFlexEntryFetch( p->pMemTemp, nBytes );
+    pCut->iMat  = iMat;
+    pCut->fInv  = 0;
+    pCut->nFans = nSize;
+    for ( i = 0; i < (int)pCut0->nFans; i++ )
+        pCut->Fans[i] = pCut0->Fans[i];
+    for ( i = 0; i < (int)pCut1->nFans; i++ )
+        pCut->Fans[pCut0->nFans+i] = pCut1->Fans[i];
+    for ( i = 0; i < (int)pCut2->nFans; i++ )
+        pCut->Fans[pCut0->nFans+pCut1->nFans+i] = pCut2->Fans[i];
+    // add it to storage
+    if ( p->ppCutsTemp[ pCut->iMat ] == NULL )
+        Vec_IntPushOrder( p->vTemp, pCut->iMat );
+    *Amap_ManCutNextP( pCut ) = p->ppCutsTemp[ pCut->iMat ];
+    p->ppCutsTemp[ pCut->iMat ] = pCut;
+    return pCut;
+} 
+
+/**Function*************************************************************
+
+  Synopsis    [Removes cuts from the temporary storage.]
+
+  Description [] 
+               
+  SideEffects []
+
+  SeeAlso     [] 
+
+***********************************************************************/
+void Amap_ManCutSaveStored( Amap_Man_t * p, Amap_Obj_t * pNode )
+{
+    int * pBuffer;
+    Amap_Cut_t * pNext, * pCut;
+    int i, nWords, Entry, nCuts;
+    assert( pNode->pData == NULL );
+    // count memory needed
+    nCuts = 1;
+    nWords = 2;
+    Vec_IntForEachEntry( p->vTemp, Entry, i )
+    {
+        for ( pCut = p->ppCutsTemp[Entry]; pCut; pCut = *Amap_ManCutNextP(pCut) )
+        {
+            nCuts++;
+            nWords += pCut->nFans + 1;
+        }
+    }
+    p->nBytesUsed += 4*nWords;
+    // allocate memory
+    pBuffer = (int *)Aig_MmFlexEntryFetch( p->pMemCuts, 4*nWords );
+    pNext = (Amap_Cut_t *)pBuffer;
+    // add the first cut
+    pNext->iMat  = 0; 
+    pNext->fInv  = 0;
+    pNext->nFans = 1;
+    pNext->Fans[0] = Amap_Var2Lit(pNode->Id, 0);
+    pNext = (Amap_Cut_t *)(pBuffer + 2);
+    // add other cuts
+    Vec_IntForEachEntry( p->vTemp, Entry, i )
+    {
+        for ( pCut = p->ppCutsTemp[Entry]; pCut; pCut = *Amap_ManCutNextP(pCut) )
+        {
+            memcpy( pNext, pCut, sizeof(int) * (pCut->nFans + 1) );
+            pNext = (Amap_Cut_t *)((int *)pNext + pCut->nFans + 1);
+        }
+        p->ppCutsTemp[Entry] = NULL;
+    }
+    assert( (int *)pNext - pBuffer == nWords );
+    // restore the storage
+    Vec_IntClear( p->vTemp );
+    Aig_MmFlexRestart( p->pMemTemp );
+    for ( i = 0; i < 2*p->pLib->nNodes; i++ )
+        if ( p->ppCutsTemp[i] != NULL )
+            printf( "Amap_ManCutSaveStored(): Error!\n" );
+    pNode->pData = (Amap_Cut_t *)pBuffer;
+    pNode->nCuts = nCuts;
+//    printf("%d ", nCuts );
+    // verify cuts
+    pCut = NULL;
+    Amap_NodeForEachCut( pNode, pNext, i )
+//        for ( i = 0, pNext = (Amap_Cut_t *)pNode->pData; i < (int)pNode->nCuts; 
+//        i++, pNext = Amap_ManCutNext(pNext) )
+    {
+        assert( pCut == NULL || pCut->iMat <= pNext->iMat );
+        pCut = pNext;
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the number of possible new cuts.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Amap_ManMergeCountCuts( Amap_Man_t * p, Amap_Obj_t * pNode )
+{
+    Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode );
+    Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode );
+    Amap_Cut_t * pCut0, * pCut1;
+    int Entry, c0, c1, iCompl0, iCompl1, iFan0, iFan1;
+    int Counter = 1;
+    Amap_NodeForEachCut( pFanin0, pCut0, c0 )
+    Amap_NodeForEachCut( pFanin1, pCut1, c1 )
+    {
+        iCompl0 = pCut0->fInv ^ Amap_ObjFaninC0(pNode);
+        iCompl1 = pCut1->fInv ^ Amap_ObjFaninC1(pNode);
+        iFan0   = !pCut0->iMat? 0: Amap_Var2Lit( pCut0->iMat, iCompl0 );
+        iFan1   = !pCut1->iMat? 0: Amap_Var2Lit( pCut1->iMat, iCompl1 );
+        Entry = Amap_LibFindNode( p->pLib, iFan0, iFan1, pNode->Type == AMAP_OBJ_XOR );
+        Counter += ( Entry >=0 );
+//        if ( Entry >=0 )
+//            printf( "Full: %d + %d = %d\n", iFan0, iFan1, Entry );
+    }
+    return Counter;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Print cuts.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Amap_ManPrintCuts( Amap_Obj_t * pNode )
+{
+    Amap_Cut_t * pCut;
+    int c, i;
+    printf( "NODE %5d : Type = ", pNode->Id );
+    if ( pNode->Type == AMAP_OBJ_AND )
+        printf( "AND" );
+    else if ( pNode->Type == AMAP_OBJ_XOR )
+        printf( "XOR" );
+    else if ( pNode->Type == AMAP_OBJ_MUX )
+        printf( "MUX" );
+    printf( "  Cuts = %d\n", pNode->nCuts );
+    Amap_NodeForEachCut( pNode, pCut, c )
+    {
+        printf( "%3d :  Mat= %3d  Inv=%d  ", c, pCut->iMat, pCut->fInv );
+        for ( i = 0; i < (int)pCut->nFans; i++ )
+            printf( "%d%c ", Amap_Lit2Var(pCut->Fans[i]), Amap_LitIsCompl(pCut->Fans[i])?'-':'+' );
+        printf( "\n" );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives cuts for one node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Amap_ManMergeNodeChoice( Amap_Man_t * p, Amap_Obj_t * pNode )
+{
+    Amap_Obj_t * pTemp;
+    Amap_Cut_t * pCut;
+    int c;
+    // go through the nodes of the choice node
+    for ( pTemp = pNode; pTemp; pTemp = Amap_ObjChoice(p, pTemp) )
+    {
+        Amap_NodeForEachCut( pTemp, pCut, c )
+            if ( pCut->iMat )
+                Amap_ManCutStore( p, pCut, pNode->fPhase ^ pTemp->fPhase );
+        pTemp->pData = NULL;
+    }
+    Amap_ManCutSaveStored( p, pNode );
+
+//    Amap_ManPrintCuts( pNode );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives cuts for one node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Amap_ManFindCut( Amap_Obj_t * pNode, Amap_Obj_t * pFanin, int fComplFanin, int Val, Vec_Ptr_t * vCuts )
+{
+    Amap_Cut_t * pCut;
+    int c, iCompl, iFan;
+    Vec_PtrClear( vCuts );
+    Amap_NodeForEachCut( pFanin, pCut, c )
+    {
+        iCompl = pCut->fInv ^ fComplFanin;
+        iFan   = !pCut->iMat? 0: Amap_Var2Lit( pCut->iMat, iCompl );
+        if ( iFan == Val )
+            Vec_PtrPush( vCuts, pCut );
+    }
+    return Vec_PtrSize(vCuts) == 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives cuts for one node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Amap_ManMergeNodeCutsMux( Amap_Man_t * p, Amap_Obj_t * pNode )
+{
+    Vec_Int_t * vRules = p->pLib->vRules3;
+    Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode );
+    Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode );
+    Amap_Obj_t * pFanin2 = Amap_ObjFanin2( p, pNode );
+    int fComplFanin0 = Amap_ObjFaninC0( pNode );
+    int fComplFanin1 = Amap_ObjFaninC1( pNode );
+    int fComplFanin2 = Amap_ObjFaninC2( pNode );
+    Amap_Cut_t * pCut0, * pCut1, * pCut2;
+    int x, c0, c1, c2;
+    assert( pNode->pData == NULL );
+    assert( pNode->Type == AMAP_OBJ_MUX );
+    assert( pNode->fRepr == 0 );
+    // go through the rules
+    for ( x = 0; x < Vec_IntSize(vRules); x += 4 )
+    {
+        if ( Amap_ManFindCut( pNode, pFanin0, fComplFanin0, Vec_IntEntry(vRules, x), p->vCuts0 ) )
+            continue;
+        if ( Amap_ManFindCut( pNode, pFanin1, fComplFanin1, Vec_IntEntry(vRules, x+1), p->vCuts1 ) )
+            continue;
+        if ( Amap_ManFindCut( pNode, pFanin2, fComplFanin2, Vec_IntEntry(vRules, x+2), p->vCuts2 ) )
+            continue;
+        Vec_PtrForEachEntry( p->vCuts0, pCut0, c0 )
+        Vec_PtrForEachEntry( p->vCuts1, pCut1, c1 )
+        Vec_PtrForEachEntry( p->vCuts2, pCut2, c2 )
+        {
+            Amap_Nod_t * pNod = Amap_LibNod( p->pLib, Vec_IntEntry(vRules, x+3) );
+            if ( pNod->pSets == NULL )
+                continue;
+            // complement literals
+            if ( pCut0->nFans == 1 && (pCut0->fInv ^ fComplFanin0) )
+                pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]);
+            if ( pCut1->nFans == 1 && (pCut1->fInv ^ fComplFanin1) )
+                pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]);
+            if ( pCut2->nFans == 1 && (pCut2->fInv ^ fComplFanin2) )
+                pCut2->Fans[0] = Amap_LitNot(pCut2->Fans[0]);
+            // create new cut
+            Amap_ManCutCreate3( p, pCut0, pCut1, pCut2, Vec_IntEntry(vRules, x+3) );
+            // uncomplement literals
+            if ( pCut0->nFans == 1 && (pCut0->fInv ^ fComplFanin0) )
+                pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]);
+            if ( pCut1->nFans == 1 && (pCut1->fInv ^ fComplFanin1) )
+                pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]);
+            if ( pCut2->nFans == 1 && (pCut2->fInv ^ fComplFanin2) )
+                pCut2->Fans[0] = Amap_LitNot(pCut2->Fans[0]);
+        }
+    }
+    Amap_ManCutSaveStored( p, pNode );
+    p->nCutsUsed += pNode->nCuts;
+    p->nCutsTried3 += pFanin0->nCuts * pFanin1->nCuts * pFanin2->nCuts;
+
+//    Amap_ManPrintCuts( pNode );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives cuts for one node.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Amap_ManMergeNodeCuts( Amap_Man_t * p, Amap_Obj_t * pNode )
+{
+    Amap_Obj_t * pFanin0 = Amap_ObjFanin0( p, pNode );
+    Amap_Obj_t * pFanin1 = Amap_ObjFanin1( p, pNode );
+    Amap_Cut_t * pCut0, * pCut1;
+    int ** pRules, Entry, i, k, c, iCompl0, iCompl1, iFan0, iFan1;
+    assert( pNode->pData == NULL );
+    if ( pNode->Type == AMAP_OBJ_MUX )
+    {
+        Amap_ManMergeNodeCutsMux( p, pNode );
+        return;
+    }
+    assert( pNode->Type != AMAP_OBJ_MUX );
+    pRules = (pNode->Type == AMAP_OBJ_AND)? p->pLib->pRules: p->pLib->pRulesX;
+    Amap_NodeForEachCut( pFanin0, pCut0, c )
+    {
+        iCompl0 = pCut0->fInv ^ Amap_ObjFaninC0(pNode);
+        iFan0   = !pCut0->iMat? 0: Amap_Var2Lit( pCut0->iMat, iCompl0 );
+        // complement literals
+        if ( pCut0->nFans == 1 && iCompl0 )
+            pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]);
+        // label resulting sets
+        for ( i = 0; (Entry = pRules[iFan0][i]); i++ )
+            p->pMatsTemp[Entry & 0xffff] = (Entry >> 16);
+        // iterate through the cuts
+        Amap_NodeForEachCut( pFanin1, pCut1, k )
+        {
+            iCompl1 = pCut1->fInv ^ Amap_ObjFaninC1(pNode);
+            iFan1   = !pCut1->iMat? 0: Amap_Var2Lit( pCut1->iMat, iCompl1 );
+            if ( p->pMatsTemp[iFan1] == 0 )
+                continue;
+            // complement literals
+            if ( pCut1->nFans == 1 && iCompl1 )
+                pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]);
+            // create new cut
+            if ( iFan0 >= iFan1 )
+                Amap_ManCutCreate( p, pCut0, pCut1, p->pMatsTemp[iFan1] );
+            else
+                Amap_ManCutCreate( p, pCut1, pCut0, p->pMatsTemp[iFan1] );
+            // uncomplement literals
+            if ( pCut1->nFans == 1 && iCompl1 )
+                pCut1->Fans[0] = Amap_LitNot(pCut1->Fans[0]);
+        }
+        // uncomplement literals
+        if ( pCut0->nFans == 1 && iCompl0 )
+            pCut0->Fans[0] = Amap_LitNot(pCut0->Fans[0]);
+        // label resulting sets
+        for ( i = 0; (Entry = pRules[iFan0][i]); i++ )
+            p->pMatsTemp[Entry & 0xffff] = 0;
+    }
+    Amap_ManCutSaveStored( p, pNode );
+    p->nCutsUsed += pNode->nCuts;
+    p->nCutsTried += pFanin0->nCuts * pFanin1->nCuts;
+//    assert( (int)pNode->nCuts == Amap_ManMergeCountCuts(p, pNode) );
+    if ( pNode->fRepr )
+        Amap_ManMergeNodeChoice( p, pNode );
+
+//    Amap_ManPrintCuts( pNode );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives cuts for all nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Amap_ManMerge( Amap_Man_t * p )
+{
+    Amap_Obj_t * pObj;
+    int i, clk = clock();
+    p->pCutsPi = Amap_ManSetupPis( p );
+    Amap_ManForEachNode( p, pObj, i )
+        Amap_ManMergeNodeCuts( p, pObj );
+    if ( p->pPars->fVerbose )
+    {
+        printf( "AIG object is %d bytes.  ", sizeof(Amap_Obj_t) );
+        printf( "Internal AIG = %5.2f Mb.  Cuts = %5.2f Mb.\n", 
+            1.0*Amap_ManObjNum(p)*sizeof(Amap_Obj_t)/(1<<20), 1.0*p->nBytesUsed/(1<<20) );
+        printf( "Node =%6d. Try =%9d. Try3 =%10d. Used =%7d. R =%6.2f.  ", 
+            Amap_ManNodeNum(p), p->nCutsTried, p->nCutsTried3, p->nCutsUsed, 
+            1.0*p->nCutsUsed/Amap_ManNodeNum(p) );
+PRT( "Time ", clock() - clk );
+    }
+}
+
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+