Version abc50819

1 files changed, 154 insertions, 62 deletions

diff --git a/src/opt/rwr/rwrEva.c b/src/opt/rwr/rwrEva.c
index 50e773f8..ddc9d742 100644
--- a/src/opt/rwr/rwrEva.c
+++ b/src/opt/rwr/rwrEva.c
@@ -19,13 +19,13 @@
 ***********************************************************************/
 
 #include "rwr.h"
+#include "ft.h"
 
 ////////////////////////////////////////////////////////////////////////
 ///                        DECLARATIONS                              ///
 ////////////////////////////////////////////////////////////////////////
 
-static void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut );
-static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut, Vec_Int_t * vForm );
+static Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax );
 
 ////////////////////////////////////////////////////////////////////////
 ///                     FUNCTION DEFITIONS                           ///
@@ -51,43 +51,34 @@ static void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pNode, Rwr_Cut_t * pCut
 ***********************************************************************/
 int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode )
 {
-    Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector;
-    Rwr_Cut_t * pCut, * pCutBest;
-    int BestGain = -1;
-    int i, Required = Vec_IntEntry( p->vReqTimes, pNode->Id );
-
-    // compute the cuts of the node
+    Vec_Int_t * vForm;
+    Rwr_Cut_t * pCut;
+    int Required, nNodesSaved;
+    int i, BestGain = -1;
+    // compute the cuts for this node
     Rwr_NodeComputeCuts( p, pNode );
-
+    // get the required times
+    Required = Vec_IntEntry( p->vReqTimes, pNode->Id );
+    // label MFFC with current ID
+    nNodesSaved = Abc_NodeMffcLabel( pNode );
     // go through the cuts
     for ( pCut = (Rwr_Cut_t *)pNode->pCopy, pCut = pCut->pNext; pCut; pCut = pCut->pNext )
     {
-        // collect the TFO
-        vFanins->nSize  = pCut->nLeaves;
-        vFanins->pArray = pCut->ppLeaves;
-        Abc_NodeCollectTfoCands( pNode->pNtk, pNode, vFanins, Required, p->vLevels, p->vTfo );
         // evaluate the cut
-        Rwr_CutEvaluate( p, pNode, pCut );
-        // check if the cut is the best
-        if ( pCut->fTime && pCut->fGain )
+        vForm = Rwr_CutEvaluate( p, pNode, pCut, nNodesSaved, Required );
+        // check if the cut is better than the currently best one
+        if ( vForm != NULL && BestGain < (int)pCut->Volume )
         {
-            pCutBest = pCut;
-            BestGain = pCut->Volume;
+            assert( pCut->Volume >= 0 );
+            BestGain  = pCut->Volume;
+            // save this form
+            p->vForm = vForm;
+            // collect fanins
+            Vec_PtrClear( p->vFanins );
+            for ( i = 0; i < (int)pCut->nLeaves; i++ )
+                Vec_PtrPush( p->vFanins, pCut->ppLeaves[i] );
         }
     }
-    if ( BestGain == -1 )
-        return -1;
-    // we found a good cut
-
-    // prepare the fanins
-    Vec_PtrClear( p->vFanins );
-    for ( i = 0; i < (int)pCutBest->nLeaves; i++ )
-        Vec_PtrPush( p->vFanins, pCutBest->ppLeaves[i] );
-    // collect the TFO again
-    Abc_NodeCollectTfoCands( pNode->pNtk, pNode, p->vFanins, Required, p->vLevels, p->vTfo );
-    // perform the decomposition
-    Rwr_CutDecompose( p, pNode, pCutBest, p->vForm );
-    // the best fanins are in p->vFanins, the result of decomposition is in p->vForm
     return BestGain;
 }
 
@@ -102,46 +93,113 @@ int Rwr_NodeRewrite( Rwr_Man_t * p, Abc_Obj_t * pNode )
   SeeAlso     []
 
 ***********************************************************************/
-void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut )
+Vec_Int_t * Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, int NodeMax, int LevelMax )
 {
-    Abc_Obj_t * pNode, * pFanin0, * pFanin1;
-    Rwr_Node_t * pNodeFor;
-    int i;
-    // mark forest PIs corresponding to cut leaves
-    Vec_PtrClear( p->vTfoFor );
-    for ( i = 0; i < (int)pCut->nLeaves; i++ )
+    Vec_Ptr_t Vector = {0,0,0}, * vFanins = &Vector;
+    Vec_Ptr_t * vSubgraphs;
+    Vec_Int_t * vFormBest;
+    Rwr_Node_t * pNode;
+    int GainCur, GainBest = -1, i;
+    // find the matching class of subgraphs
+    vSubgraphs = Vec_VecEntry( p->vClasses, p->pMap[pCut->uTruth] );
+    // determine the best subgraph
+    Vec_PtrForEachEntry( vSubgraphs, pNode, i )
     {
-        pNodeFor = p->vForest->pArray[i];
-        Vec_PtrPush( p->vTfoFor, pNodeFor );
-        pCut->ppLeaves[i]->pData = pNodeFor;
-        pNodeFor->fMark = 1;
+        // create the fanin array
+        vFanins->nSize  = pCut->nLeaves;
+        vFanins->pArray = pCut->ppLeaves;
+        // detect how many unlabeled nodes will be reused
+        GainCur = Abc_NodeStrashDecCount( pRoot->pNtk->pManFunc, vFanins, (Vec_Int_t *)pNode->pNext, 
+            p->vLevNums, NodeMax, LevelMax );
+        if ( GainBest < GainCur )
+        {
+            GainBest  = GainCur;
+            vFormBest = (Vec_Int_t *)pNode->pNext;
+        }
     }
-    // detect forest nodes corresponding to TFO
-    Vec_PtrForEachEntry( p->vTfo, pNode, i )
-    {
-        pFanin0 = Abc_ObjFanin0(pNode);
-        if ( pFanin0->pData == NULL )
-            continue;
-        pFanin1 = Abc_ObjFanin1(pNode);
-        if ( pFanin1->pData == NULL )
-            continue;
+    if ( GainBest == -1 )
+        return NULL;
+    pCut->Volume = GainBest;
+    return vFormBest;
+}
 
-    }
 
-    // find the best implementation of the root
+/**Function*************************************************************
+
+  Synopsis    [Adds one node.]
 
-    // assign costs
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
 
-    // clean the nodes
-    for ( i = 0; i < (int)pCut->nLeaves; i++ )
-        pCut->ppLeaves[i]->pData = NULL;
-    Vec_PtrForEachEntry( p->vTfo, pNode, i )
-        pNode->pData = NULL;
+***********************************************************************/
+int Rwr_TravCollect_rec( Rwr_Man_t * p, Rwr_Node_t * pNode, Vec_Int_t * vForm )
+{
+    Ft_Node_t Node, NodeA, NodeB;
+    int Node0, Node1;
+    // elementary variable
+    if ( pNode->fUsed )
+        return ((pNode->Id - 1) << 1); 
+    // previously visited node
+    if ( pNode->TravId == p->nTravIds )
+        return pNode->Volume;
+    pNode->TravId = p->nTravIds;
+    // solve for children
+    Node0 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p0), vForm );
+    Node1 = Rwr_TravCollect_rec( p, Rwr_Regular(pNode->p1), vForm );
+    // create the decomposition node(s)
+    if ( pNode->fExor )
+    {
+        assert( !Rwr_IsComplement(pNode->p0) );
+        assert( !Rwr_IsComplement(pNode->p1) );
+        NodeA.fIntern = 1;
+        NodeA.fConst  = 0;
+        NodeA.fCompl  = 0;
+        NodeA.fCompl0 = !(Node0 & 1);
+        NodeA.fCompl1 =  (Node1 & 1);
+        NodeA.iFanin0 = (Node0 >> 1);
+        NodeA.iFanin1 = (Node1 >> 1);
+        Vec_IntPush( vForm, Ft_Node2Int(NodeA) );
+
+        NodeB.fIntern = 1;
+        NodeB.fConst  = 0;
+        NodeB.fCompl  = 0;
+        NodeB.fCompl0 =  (Node0 & 1);
+        NodeB.fCompl1 = !(Node1 & 1);
+        NodeB.iFanin0 = (Node0 >> 1);
+        NodeB.iFanin1 = (Node1 >> 1);
+        Vec_IntPush( vForm, Ft_Node2Int(NodeB) );
+
+        Node.fIntern = 1;
+        Node.fConst  = 0;
+        Node.fCompl  = 0;
+        Node.fCompl0 = 1;
+        Node.fCompl1 = 1;
+        Node.iFanin0 = vForm->nSize - 2;
+        Node.iFanin1 = vForm->nSize - 1;
+        Vec_IntPush( vForm, Ft_Node2Int(Node) );
+    }
+    else
+    {
+        Node.fIntern = 1;
+        Node.fConst  = 0;
+        Node.fCompl  = 0;
+        Node.fCompl0 = Rwr_IsComplement(pNode->p0) ^ (Node0 & 1);
+        Node.fCompl1 = Rwr_IsComplement(pNode->p1) ^ (Node1 & 1);
+        Node.iFanin0 = (Node0 >> 1);
+        Node.iFanin1 = (Node1 >> 1);
+        Vec_IntPush( vForm, Ft_Node2Int(Node) );
+    }
+    // save the number of this node
+    pNode->Volume = ((vForm->nSize - 1) << 1) | pNode->fExor;
+    return pNode->Volume;
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Decomposes the cut.]
+  Synopsis    [Preprocesses subgraphs rooted at this node.]
 
   Description []
                
@@ -150,11 +208,45 @@ void Rwr_CutEvaluate( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut )
   SeeAlso     []
 
 ***********************************************************************/
-void Rwr_CutDecompose( Rwr_Man_t * p, Abc_Obj_t * pRoot, Rwr_Cut_t * pCut, Vec_Int_t * vForm )
+void Rwr_NodePreprocess( Rwr_Man_t * p, Rwr_Node_t * pNode )
 {
-
+    Vec_Int_t * vForm;
+    int i, Root;
+    vForm = Vec_IntAlloc( 10 );
+    for ( i = 0; i < 5; i++ )
+        Vec_IntPush( vForm, 0 );
+    // collect the nodes
+    Rwr_ManIncTravId( p );
+    Root = Rwr_TravCollect_rec( p, pNode, vForm );
+    if ( Root & 1 )
+        Ft_FactorComplement( vForm );
+    pNode->pNext = (Rwr_Node_t *)vForm;
 }
 
+/**Function*************************************************************
+
+  Synopsis    [Preprocesses computed library of subgraphs.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Rwr_ManPreprocess( Rwr_Man_t * p )
+{
+    Rwr_Node_t * pNode;
+    int i, k;
+    // put the nodes into the structure
+    p->vClasses = Vec_VecAlloc( 222 );
+    for ( i = 0; i < p->nFuncs; i++ )
+        for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext )
+            Vec_VecPush( p->vClasses, p->pMap[pNode->uTruth], pNode );
+    // compute decomposition forms for each node
+    Vec_VecForEachEntry( p->vClasses, pNode, i, k )
+        Rwr_NodePreprocess( p, pNode );
+}
 
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///