abc70930: src/aig/hop/hopUtil.c Source File

00001 
00021 #include "hop.h"
00022 
00026 
00030 
00042 void Hop_ManIncrementTravId( Hop_Man_t * p )
00043 {
00044     if ( p->nTravIds >= (1<<30)-1 )
00045         Hop_ManCleanData( p );
00046     p->nTravIds++;
00047 }
00048 
00060 void Hop_ManCleanData( Hop_Man_t * p )
00061 {
00062     Hop_Obj_t * pObj;
00063     int i;
00064     p->nTravIds = 1;
00065     Hop_ManConst1(p)->pData = NULL;
00066     Hop_ManForEachPi( p, pObj, i )
00067         pObj->pData = NULL;
00068     Hop_ManForEachPo( p, pObj, i )
00069         pObj->pData = NULL;
00070     Hop_ManForEachNode( p, pObj, i )
00071         pObj->pData = NULL;
00072 }
00073 
00085 void Hop_ObjCleanData_rec( Hop_Obj_t * pObj )
00086 {
00087     assert( !Hop_IsComplement(pObj) );
00088     assert( !Hop_ObjIsPo(pObj) );
00089     if ( Hop_ObjIsAnd(pObj) )
00090     {
00091         Hop_ObjCleanData_rec( Hop_ObjFanin0(pObj) );
00092         Hop_ObjCleanData_rec( Hop_ObjFanin1(pObj) );
00093     }
00094     pObj->pData = NULL;
00095 }
00096 
00108 void Hop_ObjCollectMulti_rec( Hop_Obj_t * pRoot, Hop_Obj_t * pObj, Vec_Ptr_t * vSuper )
00109 {
00110     if ( pRoot != pObj && (Hop_IsComplement(pObj) || Hop_ObjIsPi(pObj) || Hop_ObjType(pRoot) != Hop_ObjType(pObj)) )
00111     {
00112         Vec_PtrPushUnique(vSuper, pObj);
00113         return;
00114     }
00115     Hop_ObjCollectMulti_rec( pRoot, Hop_ObjChild0(pObj), vSuper );
00116     Hop_ObjCollectMulti_rec( pRoot, Hop_ObjChild1(pObj), vSuper );
00117 }
00118 
00130 void Hop_ObjCollectMulti( Hop_Obj_t * pRoot, Vec_Ptr_t * vSuper )
00131 {
00132     assert( !Hop_IsComplement(pRoot) );
00133     Vec_PtrClear( vSuper );
00134     Hop_ObjCollectMulti_rec( pRoot, pRoot, vSuper );
00135 }
00136 
00148 int Hop_ObjIsMuxType( Hop_Obj_t * pNode )
00149 {
00150     Hop_Obj_t * pNode0, * pNode1;
00151     // check that the node is regular
00152     assert( !Hop_IsComplement(pNode) );
00153     // if the node is not AND, this is not MUX
00154     if ( !Hop_ObjIsAnd(pNode) )
00155         return 0;
00156     // if the children are not complemented, this is not MUX
00157     if ( !Hop_ObjFaninC0(pNode) || !Hop_ObjFaninC1(pNode) )
00158         return 0;
00159     // get children
00160     pNode0 = Hop_ObjFanin0(pNode);
00161     pNode1 = Hop_ObjFanin1(pNode);
00162     // if the children are not ANDs, this is not MUX
00163     if ( !Hop_ObjIsAnd(pNode0) || !Hop_ObjIsAnd(pNode1) )
00164         return 0;
00165     // otherwise the node is MUX iff it has a pair of equal grandchildren
00166     return (Hop_ObjFanin0(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC0(pNode1))) || 
00167            (Hop_ObjFanin0(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC1(pNode1))) ||
00168            (Hop_ObjFanin1(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC0(pNode1))) ||
00169            (Hop_ObjFanin1(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC1(pNode1)));
00170 }
00171 
00172 
00184 int Hop_ObjRecognizeExor( Hop_Obj_t * pObj, Hop_Obj_t ** ppFan0, Hop_Obj_t ** ppFan1 )
00185 {
00186     Hop_Obj_t * p0, * p1;
00187     assert( !Hop_IsComplement(pObj) );
00188     if ( !Hop_ObjIsNode(pObj) )
00189         return 0;
00190     if ( Hop_ObjIsExor(pObj) )
00191     {
00192         *ppFan0 = Hop_ObjChild0(pObj);
00193         *ppFan1 = Hop_ObjChild1(pObj);
00194         return 1;
00195     }
00196     assert( Hop_ObjIsAnd(pObj) );
00197     p0 = Hop_ObjChild0(pObj);
00198     p1 = Hop_ObjChild1(pObj);
00199     if ( !Hop_IsComplement(p0) || !Hop_IsComplement(p1) )
00200         return 0;
00201     p0 = Hop_Regular(p0);
00202     p1 = Hop_Regular(p1);
00203     if ( !Hop_ObjIsAnd(p0) || !Hop_ObjIsAnd(p1) )
00204         return 0;
00205     if ( Hop_ObjFanin0(p0) != Hop_ObjFanin0(p1) || Hop_ObjFanin1(p0) != Hop_ObjFanin1(p1) )
00206         return 0;
00207     if ( Hop_ObjFaninC0(p0) == Hop_ObjFaninC0(p1) || Hop_ObjFaninC1(p0) == Hop_ObjFaninC1(p1) )
00208         return 0;
00209     *ppFan0 = Hop_ObjChild0(p0);
00210     *ppFan1 = Hop_ObjChild1(p0);
00211     return 1;
00212 }
00213 
00228 Hop_Obj_t * Hop_ObjRecognizeMux( Hop_Obj_t * pNode, Hop_Obj_t ** ppNodeT, Hop_Obj_t ** ppNodeE )
00229 {
00230     Hop_Obj_t * pNode0, * pNode1;
00231     assert( !Hop_IsComplement(pNode) );
00232     assert( Hop_ObjIsMuxType(pNode) );
00233     // get children
00234     pNode0 = Hop_ObjFanin0(pNode);
00235     pNode1 = Hop_ObjFanin1(pNode);
00236 
00237     // find the control variable
00238     if ( Hop_ObjFanin1(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC1(pNode1)) )
00239     {
00240 //        if ( Fraig_IsComplement(pNode1->p2) )
00241         if ( Hop_ObjFaninC1(pNode0) )
00242         { // pNode2->p2 is positive phase of C
00243             *ppNodeT = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1);
00244             *ppNodeE = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1);
00245             return Hop_ObjChild1(pNode1);//pNode2->p2;
00246         }
00247         else
00248         { // pNode1->p2 is positive phase of C
00249             *ppNodeT = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1);
00250             *ppNodeE = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1);
00251             return Hop_ObjChild1(pNode0);//pNode1->p2;
00252         }
00253     }
00254     else if ( Hop_ObjFanin0(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC0(pNode1)) )
00255     {
00256 //        if ( Fraig_IsComplement(pNode1->p1) )
00257         if ( Hop_ObjFaninC0(pNode0) )
00258         { // pNode2->p1 is positive phase of C
00259             *ppNodeT = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2);
00260             *ppNodeE = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2);
00261             return Hop_ObjChild0(pNode1);//pNode2->p1;
00262         }
00263         else
00264         { // pNode1->p1 is positive phase of C
00265             *ppNodeT = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2);
00266             *ppNodeE = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2);
00267             return Hop_ObjChild0(pNode0);//pNode1->p1;
00268         }
00269     }
00270     else if ( Hop_ObjFanin0(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC1(pNode1)) )
00271     {
00272 //        if ( Fraig_IsComplement(pNode1->p1) )
00273         if ( Hop_ObjFaninC0(pNode0) )
00274         { // pNode2->p2 is positive phase of C
00275             *ppNodeT = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1);
00276             *ppNodeE = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2);
00277             return Hop_ObjChild1(pNode1);//pNode2->p2;
00278         }
00279         else
00280         { // pNode1->p1 is positive phase of C
00281             *ppNodeT = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2);
00282             *ppNodeE = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1);
00283             return Hop_ObjChild0(pNode0);//pNode1->p1;
00284         }
00285     }
00286     else if ( Hop_ObjFanin1(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC0(pNode1)) )
00287     {
00288 //        if ( Fraig_IsComplement(pNode1->p2) )
00289         if ( Hop_ObjFaninC1(pNode0) )
00290         { // pNode2->p1 is positive phase of C
00291             *ppNodeT = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2);
00292             *ppNodeE = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1);
00293             return Hop_ObjChild0(pNode1);//pNode2->p1;
00294         }
00295         else
00296         { // pNode1->p2 is positive phase of C
00297             *ppNodeT = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1);
00298             *ppNodeE = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2);
00299             return Hop_ObjChild1(pNode0);//pNode1->p2;
00300         }
00301     }
00302     assert( 0 ); // this is not MUX
00303     return NULL;
00304 }
00305 
00306 
00319 void Hop_ObjPrintEqn( FILE * pFile, Hop_Obj_t * pObj, Vec_Vec_t * vLevels, int Level )
00320 {
00321     Vec_Ptr_t * vSuper;
00322     Hop_Obj_t * pFanin;
00323     int fCompl, i;
00324     // store the complemented attribute
00325     fCompl = Hop_IsComplement(pObj);
00326     pObj = Hop_Regular(pObj);
00327     // constant case
00328     if ( Hop_ObjIsConst1(pObj) )
00329     {
00330         fprintf( pFile, "%d", !fCompl );
00331         return;
00332     }
00333     // PI case
00334     if ( Hop_ObjIsPi(pObj) )
00335     {
00336         fprintf( pFile, "%s%s", fCompl? "!" : "", pObj->pData );
00337         return;
00338     }
00339     // AND case
00340     Vec_VecExpand( vLevels, Level );
00341     vSuper = Vec_VecEntry(vLevels, Level);
00342     Hop_ObjCollectMulti( pObj, vSuper );
00343     fprintf( pFile, "%s", (Level==0? "" : "(") );
00344     Vec_PtrForEachEntry( vSuper, pFanin, i )
00345     {
00346         Hop_ObjPrintEqn( pFile, Hop_NotCond(pFanin, fCompl), vLevels, Level+1 );
00347         if ( i < Vec_PtrSize(vSuper) - 1 )
00348             fprintf( pFile, " %s ", fCompl? "+" : "*" );
00349     }
00350     fprintf( pFile, "%s", (Level==0? "" : ")") );
00351     return;
00352 }
00353 
00366 void Hop_ObjPrintVerilog( FILE * pFile, Hop_Obj_t * pObj, Vec_Vec_t * vLevels, int Level )
00367 {
00368     Vec_Ptr_t * vSuper;
00369     Hop_Obj_t * pFanin, * pFanin0, * pFanin1, * pFaninC;
00370     int fCompl, i;
00371     // store the complemented attribute
00372     fCompl = Hop_IsComplement(pObj);
00373     pObj = Hop_Regular(pObj);
00374     // constant case
00375     if ( Hop_ObjIsConst1(pObj) )
00376     {
00377         fprintf( pFile, "1\'b%d", !fCompl );
00378         return;
00379     }
00380     // PI case
00381     if ( Hop_ObjIsPi(pObj) )
00382     {
00383         fprintf( pFile, "%s%s", fCompl? "~" : "", pObj->pData );
00384         return;
00385     }
00386     // EXOR case
00387     if ( Hop_ObjIsExor(pObj) )
00388     {
00389         Vec_VecExpand( vLevels, Level );
00390         vSuper = Vec_VecEntry( vLevels, Level );
00391         Hop_ObjCollectMulti( pObj, vSuper );
00392         fprintf( pFile, "%s", (Level==0? "" : "(") );
00393         Vec_PtrForEachEntry( vSuper, pFanin, i )
00394         {
00395             Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin, (fCompl && i==0)), vLevels, Level+1 );
00396             if ( i < Vec_PtrSize(vSuper) - 1 )
00397                 fprintf( pFile, " ^ " );
00398         }
00399         fprintf( pFile, "%s", (Level==0? "" : ")") );
00400         return;
00401     }
00402     // MUX case
00403     if ( Hop_ObjIsMuxType(pObj) )
00404     {
00405         if ( Hop_ObjRecognizeExor( pObj, &pFanin0, &pFanin1 ) )
00406         {
00407             fprintf( pFile, "%s", (Level==0? "" : "(") );
00408             Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin0, fCompl), vLevels, Level+1 );
00409             fprintf( pFile, " ^ " );
00410             Hop_ObjPrintVerilog( pFile, pFanin1, vLevels, Level+1 );
00411             fprintf( pFile, "%s", (Level==0? "" : ")") );
00412         }
00413         else 
00414         {
00415             pFaninC = Hop_ObjRecognizeMux( pObj, &pFanin1, &pFanin0 );
00416             fprintf( pFile, "%s", (Level==0? "" : "(") );
00417             Hop_ObjPrintVerilog( pFile, pFaninC, vLevels, Level+1 );
00418             fprintf( pFile, " ? " );
00419             Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin1, fCompl), vLevels, Level+1 );
00420             fprintf( pFile, " : " );
00421             Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin0, fCompl), vLevels, Level+1 );
00422             fprintf( pFile, "%s", (Level==0? "" : ")") );
00423         }
00424         return;
00425     }
00426     // AND case
00427     Vec_VecExpand( vLevels, Level );
00428     vSuper = Vec_VecEntry(vLevels, Level);
00429     Hop_ObjCollectMulti( pObj, vSuper );
00430     fprintf( pFile, "%s", (Level==0? "" : "(") );
00431     Vec_PtrForEachEntry( vSuper, pFanin, i )
00432     {
00433         Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin, fCompl), vLevels, Level+1 );
00434         if ( i < Vec_PtrSize(vSuper) - 1 )
00435             fprintf( pFile, " %s ", fCompl? "|" : "&" );
00436     }
00437     fprintf( pFile, "%s", (Level==0? "" : ")") );
00438     return;
00439 }
00440 
00441 
00453 void Hop_ObjPrintVerbose( Hop_Obj_t * pObj, int fHaig )
00454 {
00455     assert( !Hop_IsComplement(pObj) );
00456     printf( "Node %p : ", pObj );
00457     if ( Hop_ObjIsConst1(pObj) )
00458         printf( "constant 1" );
00459     else if ( Hop_ObjIsPi(pObj) )
00460         printf( "PI" );
00461     else
00462         printf( "AND( %p%s, %p%s )", 
00463             Hop_ObjFanin0(pObj), (Hop_ObjFaninC0(pObj)? "\'" : " "), 
00464             Hop_ObjFanin1(pObj), (Hop_ObjFaninC1(pObj)? "\'" : " ") );
00465     printf( " (refs = %3d)", Hop_ObjRefs(pObj) );
00466 }
00467 
00479 void Hop_ManPrintVerbose( Hop_Man_t * p, int fHaig )
00480 {
00481     Vec_Ptr_t * vNodes;
00482     Hop_Obj_t * pObj;
00483     int i;
00484     printf( "PIs: " );
00485     Hop_ManForEachPi( p, pObj, i )
00486         printf( " %p", pObj );
00487     printf( "\n" );
00488     vNodes = Hop_ManDfs( p );
00489     Vec_PtrForEachEntry( vNodes, pObj, i )
00490         Hop_ObjPrintVerbose( pObj, fHaig ), printf( "\n" );
00491     printf( "\n" );
00492 }
00493 
00505 void Hop_ManDumpBlif( Hop_Man_t * p, char * pFileName )
00506 {
00507     FILE * pFile;
00508     Vec_Ptr_t * vNodes;
00509     Hop_Obj_t * pObj, * pConst1 = NULL;
00510     int i, nDigits, Counter = 0;
00511     if ( Hop_ManPoNum(p) == 0 )
00512     {
00513         printf( "Hop_ManDumpBlif(): AIG manager does not have POs.\n" );
00514         return;
00515     }
00516     // collect nodes in the DFS order
00517     vNodes = Hop_ManDfs( p );
00518     // assign IDs to objects
00519     Hop_ManConst1(p)->pData = (void *)Counter++;
00520     Hop_ManForEachPi( p, pObj, i )
00521         pObj->pData = (void *)Counter++;
00522     Hop_ManForEachPo( p, pObj, i )
00523         pObj->pData = (void *)Counter++;
00524     Vec_PtrForEachEntry( vNodes, pObj, i )
00525         pObj->pData = (void *)Counter++;
00526     nDigits = Hop_Base10Log( Counter );
00527     // write the file
00528     pFile = fopen( pFileName, "w" );
00529     fprintf( pFile, "# BLIF file written by procedure Hop_ManDumpBlif() in ABC\n" );
00530     fprintf( pFile, "# http://www.eecs.berkeley.edu/~alanmi/abc/\n" );
00531     fprintf( pFile, ".model test\n" );
00532     // write PIs
00533     fprintf( pFile, ".inputs" );
00534     Hop_ManForEachPi( p, pObj, i )
00535         fprintf( pFile, " n%0*d", nDigits, (int)pObj->pData );
00536     fprintf( pFile, "\n" );
00537     // write POs
00538     fprintf( pFile, ".outputs" );
00539     Hop_ManForEachPo( p, pObj, i )
00540         fprintf( pFile, " n%0*d", nDigits, (int)pObj->pData );
00541     fprintf( pFile, "\n" );
00542     // write nodes
00543     Vec_PtrForEachEntry( vNodes, pObj, i )
00544     {
00545         fprintf( pFile, ".names n%0*d n%0*d n%0*d\n", 
00546             nDigits, (int)Hop_ObjFanin0(pObj)->pData, 
00547             nDigits, (int)Hop_ObjFanin1(pObj)->pData, 
00548             nDigits, (int)pObj->pData );
00549         fprintf( pFile, "%d%d 1\n", !Hop_ObjFaninC0(pObj), !Hop_ObjFaninC1(pObj) );
00550     }
00551     // write POs
00552     Hop_ManForEachPo( p, pObj, i )
00553     {
00554         fprintf( pFile, ".names n%0*d n%0*d\n", 
00555             nDigits, (int)Hop_ObjFanin0(pObj)->pData, 
00556             nDigits, (int)pObj->pData );
00557         fprintf( pFile, "%d 1\n", !Hop_ObjFaninC0(pObj) );
00558         if ( Hop_ObjIsConst1(Hop_ObjFanin0(pObj)) )
00559             pConst1 = Hop_ManConst1(p);
00560     }
00561     if ( pConst1 )
00562         fprintf( pFile, ".names n%0*d\n 1\n", nDigits, (int)pConst1->pData );
00563     fprintf( pFile, ".end\n\n" );
00564     fclose( pFile );
00565     Vec_PtrFree( vNodes );
00566 }
00567 
00571 
00572