abc70930: src/aig/ivy/ivyMulti8.c Source File

00001 
00021 #include "ivy.h"
00022 
00026 
00027 typedef struct Ivy_Eval_t_ Ivy_Eval_t;
00028 struct Ivy_Eval_t_
00029 {
00030     unsigned Mask   :  5;  // the mask of covered nodes
00031     unsigned Weight :  3;  // the number of covered nodes
00032     unsigned Cost   :  4;  // the number of overlapping nodes
00033     unsigned Level  : 12;  // the level of this node
00034     unsigned Fan0   :  4;  // the first fanin
00035     unsigned Fan1   :  4;  // the second fanin
00036 };
00037 
00038 static Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type );
00039 static void        Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs );
00040 static int         Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode );
00041 static Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type );
00042 
00043 
00047 
00059 Ivy_Obj_t * Ivy_Multi_rec( Ivy_Obj_t ** ppObjs, int nObjs, Ivy_Type_t Type )
00060 {
00061     Ivy_Obj_t * pObj1, * pObj2;
00062     if ( nObjs == 1 )
00063         return ppObjs[0];
00064     pObj1 = Ivy_Multi_rec( ppObjs,           nObjs/2,         Type );
00065     pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type );
00066     return Ivy_Oper( pObj1, pObj2, Type );
00067 }
00068 
00080 Ivy_Obj_t * Ivy_Multi( Ivy_Obj_t ** pArgsInit, int nArgs, Ivy_Type_t Type )
00081 {
00082     static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5};
00083     static Ivy_Eval_t pEvals[15+15*14/2];
00084     static Ivy_Obj_t * pArgs[16];
00085     Ivy_Eval_t * pEva, * pEvaBest;
00086     int nArgsNew, nEvals, i, k;
00087     Ivy_Obj_t * pTemp;
00088 
00089     // consider the case of one argument
00090     assert( nArgs > 0 );
00091     if ( nArgs == 1 )
00092         return pArgsInit[0];
00093     // consider the case of two arguments
00094     if ( nArgs == 2 )
00095         return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type );
00096 
00097 //Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" );
00098 
00099     // set the initial ones
00100     for ( i = 0; i < nArgs; i++ )
00101     {
00102         pArgs[i] = pArgsInit[i];
00103         pEva = pEvals + i;
00104         pEva->Mask   = (1 << i);
00105         pEva->Weight = 1;
00106         pEva->Cost   = 0; 
00107         pEva->Level  = Ivy_Regular(pArgs[i])->Level; 
00108         pEva->Fan0   = 0; 
00109         pEva->Fan1   = 0; 
00110     }
00111 
00112     // find the available nodes
00113     pEvaBest = pEvals;
00114     nArgsNew = nArgs;
00115     for ( i = 1; i < nArgsNew; i++ )
00116     for ( k = 0; k < i; k++ )
00117         if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) )
00118         {
00119             pEva = pEvals + nArgsNew;
00120             pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
00121             pEva->Weight = NumBits[pEva->Mask];
00122             pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
00123             pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
00124             pEva->Fan0   = k; 
00125             pEva->Fan1   = i; 
00126 //            assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) );
00127             // compare
00128             if ( pEvaBest->Weight < pEva->Weight ||
00129                  pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
00130                  pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
00131                  pEvaBest = pEva;
00132             // save the argument
00133             pArgs[nArgsNew++] = pTemp;
00134             if ( nArgsNew == 15 )
00135                 goto Outside;
00136         }
00137 Outside:
00138 
00139 //    printf( "Best = %d.\n", pEvaBest - pEvals );
00140 
00141     // the case of no common nodes
00142     if ( nArgsNew == nArgs )
00143     {
00144         Ivy_MultiSort( pArgs, nArgs );
00145         return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
00146     }
00147     // the case of one common node
00148     if ( nArgsNew == nArgs + 1 )
00149     {
00150         assert( pEvaBest - pEvals == nArgs );
00151         k = 0;
00152         for ( i = 0; i < nArgs; i++ )
00153             if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 )
00154                 pArgs[k++] = pArgs[i];
00155         pArgs[k++] = pArgs[nArgs];
00156         assert( k == nArgs - 1 );
00157         nArgs = k;
00158         Ivy_MultiSort( pArgs, nArgs );
00159         return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
00160     }
00161     // the case when there is a node that covers everything
00162     if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) )
00163         return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); 
00164 
00165     // evaluate node pairs
00166     nEvals = nArgsNew;
00167     for ( i = 1; i < nArgsNew; i++ )
00168     for ( k = 0; k < i; k++ )
00169     {
00170         pEva = pEvals + nEvals;
00171         pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
00172         pEva->Weight = NumBits[pEva->Mask];
00173         pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
00174         pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
00175         pEva->Fan0   = k; 
00176         pEva->Fan1   = i; 
00177         // compare
00178         if ( pEvaBest->Weight < pEva->Weight ||
00179              pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
00180              pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
00181              pEvaBest = pEva;
00182         // save the argument
00183         nEvals++;
00184     }
00185     assert( pEvaBest - pEvals >= nArgsNew );
00186 
00187 //    printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 );
00188 
00189     // get the best implementation
00190     pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type );
00191 
00192     // collect those not covered by EvaBest
00193     k = 0;
00194     for ( i = 0; i < nArgs; i++ )
00195         if ( (pEvaBest->Mask & (1 << i)) == 0 )
00196             pArgs[k++] = pArgs[i];
00197     pArgs[k++] = pTemp;
00198     assert( k == nArgs - (int)pEvaBest->Weight + 1 );
00199     nArgs = k;
00200     Ivy_MultiSort( pArgs, nArgs );
00201     return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
00202 }
00203 
00215 Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
00216 {
00217     Ivy_Obj_t * pNode0, * pNode1;
00218     if ( iNum < nArgs )
00219         return pArgs[iNum];
00220     pNode0 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan0, pArgs, nArgs, Type );
00221     pNode1 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan1, pArgs, nArgs, Type );
00222     return Ivy_Oper( pNode0, pNode1, Type );
00223 }
00224 
00236 void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs )
00237 {
00238     Ivy_Obj_t * pTemp;
00239     int i, j, iBest;
00240 
00241     for ( i = 0; i < nArgs-1; i++ )
00242     {
00243         iBest = i;
00244         for ( j = i+1; j < nArgs; j++ )
00245             if ( Ivy_Regular(pArgs[j])->Level > Ivy_Regular(pArgs[iBest])->Level )
00246                 iBest = j;
00247         pTemp = pArgs[i]; 
00248         pArgs[i] = pArgs[iBest]; 
00249         pArgs[iBest] = pTemp;
00250     }
00251 }
00252 
00264 int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode )
00265 {
00266     Ivy_Obj_t * pNode1, * pNode2;
00267     int i;
00268     // try to find the node in the array
00269     for ( i = 0; i < nArgs; i++ )
00270         if ( pArray[i] == pNode )
00271             return nArgs;
00272     // put the node last
00273     pArray[nArgs++] = pNode;
00274     // find the place to put the new node
00275     for ( i = nArgs-1; i > 0; i-- )
00276     {
00277         pNode1 = pArray[i  ];
00278         pNode2 = pArray[i-1];
00279         if ( Ivy_Regular(pNode1)->Level <= Ivy_Regular(pNode2)->Level )
00280             break;
00281         pArray[i  ] = pNode2;
00282         pArray[i-1] = pNode1;
00283     }
00284     return nArgs;
00285 }
00286 
00298 Ivy_Obj_t * Ivy_MultiBalance_rec( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
00299 {
00300     Ivy_Obj_t * pNodeNew;
00301     // consider the case of one argument
00302     assert( nArgs > 0 );
00303     if ( nArgs == 1 )
00304         return pArgs[0];
00305     // consider the case of two arguments
00306     if ( nArgs == 2 )
00307         return Ivy_Oper( pArgs[0], pArgs[1], Type );
00308     // get the last two nodes
00309     pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type );
00310     // add the new node
00311     nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew );
00312     return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
00313 }
00314 
00326 Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
00327 {
00328     Ivy_Obj_t * pTemp;
00329     int i, k;
00330     int nArgsOld = nArgs;
00331     for ( i = 0; i < nArgs; i++ )
00332         printf( "%d[%d] ", i, Ivy_Regular(pArgs[i])->Level );
00333     for ( i = 1; i < nArgs; i++ )
00334         for ( k = 0; k < i; k++ )
00335         {
00336             pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE));
00337             if ( pTemp != NULL )
00338             {
00339                 printf( "%d[%d]=(%d,%d) ", nArgs, Ivy_Regular(pTemp)->Level, k, i );
00340                 pArgs[nArgs++] = pTemp;
00341             }
00342         }
00343     printf( "     ((%d/%d))    ", nArgsOld, nArgs-nArgsOld );
00344     return NULL;
00345 }
00346 
00347 
00348 
00360 Ivy_Obj_t * Ivy_Multi1( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
00361 {
00362     Ivy_Obj_t * pArgsRef[5], * pTemp;
00363     int i, k, m, nArgsNew, Counter = 0;
00364  
00365     
00366 //Ivy_MultiEval( pArgs, nArgs, Type );  printf( "\n" );
00367 
00368 
00369     assert( Type == IVY_AND || Type == IVY_EXOR );
00370     assert( nArgs > 0 );
00371     if ( nArgs == 1 )
00372         return pArgs[0];
00373 
00374     // find the nodes with more than one fanout
00375     nArgsNew = 0;
00376     for ( i = 0; i < nArgs; i++ )
00377         if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 )
00378             pArgsRef[nArgsNew++] = pArgs[i];
00379 
00380     // go through pairs
00381     if ( nArgsNew >= 2 )
00382     for ( i = 0; i < nArgsNew; i++ )
00383     for ( k = i + 1; k < nArgsNew; k++ )
00384         if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
00385             Counter++;
00386 //    printf( "%d", Counter );
00387             
00388     // go through pairs
00389     if ( nArgsNew >= 2 )
00390     for ( i = 0; i < nArgsNew; i++ )
00391     for ( k = i + 1; k < nArgsNew; k++ )
00392         if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
00393         {
00394             nArgsNew = 0;
00395             for ( m = 0; m < nArgs; m++ )
00396                 if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] )
00397                     pArgs[nArgsNew++] = pArgs[m];
00398             pArgs[nArgsNew++] = pTemp;
00399             assert( nArgsNew == nArgs - 1 );
00400             return Ivy_Multi1( pArgs, nArgsNew, Type );
00401         }
00402     return Ivy_Multi_rec( pArgs, nArgs, Type );
00403 }
00404 
00416 Ivy_Obj_t * Ivy_Multi2( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
00417 {
00418     assert( Type == IVY_AND || Type == IVY_EXOR );
00419     assert( nArgs > 0 );
00420     return Ivy_Multi_rec( pArgs, nArgs, Type );
00421 }
00422 
00426 
00427