abc70930: src/aig/hop/hop.h Source File

00001 
00021 #ifndef __HOP_H__
00022 #define __HOP_H__
00023 
00024 #ifdef __cplusplus
00025 extern "C" {
00026 #endif 
00027 
00031 
00032 #include <stdio.h>
00033 #include <stdlib.h>
00034 #include <string.h>
00035 #include <assert.h>
00036 #include <time.h>
00037 
00038 #include "vec.h"
00039 
00043 
00047 
00048 typedef struct Hop_Man_t_            Hop_Man_t;
00049 typedef struct Hop_Obj_t_            Hop_Obj_t;
00050 typedef int                          Hop_Edge_t;
00051 
00052 // object types
00053 typedef enum { 
00054     AIG_NONE,                        // 0: non-existent object
00055     AIG_CONST1,                      // 1: constant 1 
00056     AIG_PI,                          // 2: primary input
00057     AIG_PO,                          // 3: primary output
00058     AIG_AND,                         // 4: AND node
00059     AIG_EXOR,                        // 5: EXOR node
00060     AIG_VOID                         // 6: unused object
00061 } Hop_Type_t;
00062 
00063 // the AIG node
00064 struct Hop_Obj_t_  // 6 words
00065 {
00066     void *           pData;          // misc
00067     Hop_Obj_t *      pNext;          // strashing table
00068     Hop_Obj_t *      pFanin0;        // fanin
00069     Hop_Obj_t *      pFanin1;        // fanin
00070     unsigned int     Type    :  3;   // object type
00071     unsigned int     fPhase  :  1;   // value under 000...0 pattern
00072     unsigned int     fMarkA  :  1;   // multipurpose mask
00073     unsigned int     fMarkB  :  1;   // multipurpose mask
00074     unsigned int     nRefs   : 26;   // reference count (level)
00075     int              Id;             // unique ID of the node
00076 };
00077 
00078 // the AIG manager
00079 struct Hop_Man_t_
00080 {
00081     // AIG nodes
00082     Vec_Ptr_t *      vPis;           // the array of PIs
00083     Vec_Ptr_t *      vPos;           // the array of POs
00084     Vec_Ptr_t *      vObjs;          // the array of all nodes (optional)
00085     Hop_Obj_t *      pConst1;        // the constant 1 node
00086     Hop_Obj_t        Ghost;          // the ghost node
00087     // AIG node counters
00088     int              nObjs[AIG_VOID];// the number of objects by type
00089     int              nCreated;       // the number of created objects
00090     int              nDeleted;       // the number of deleted objects
00091     // stuctural hash table
00092     Hop_Obj_t **     pTable;         // structural hash table
00093     int              nTableSize;     // structural hash table size
00094     // various data members
00095     void *           pData;          // the temporary data
00096     int              nTravIds;       // the current traversal ID
00097     int              fRefCount;      // enables reference counting
00098     int              fCatchExor;     // enables EXOR nodes
00099     // memory management
00100     Vec_Ptr_t *      vChunks;        // allocated memory pieces
00101     Vec_Ptr_t *      vPages;         // memory pages used by nodes
00102     Hop_Obj_t *      pListFree;      // the list of free nodes 
00103     // timing statistics
00104     int              time1;
00105     int              time2;
00106 };
00107 
00111 
00112 #define AIG_MIN(a,b)       (((a) < (b))? (a) : (b))
00113 #define AIG_MAX(a,b)       (((a) > (b))? (a) : (b))
00114 
00115 #ifndef PRT
00116 #define PRT(a,t)  printf("%s = ", (a)); printf("%6.2f sec\n", (float)(t)/(float)(CLOCKS_PER_SEC))
00117 #endif
00118 
00119 static inline int          Hop_BitWordNum( int nBits )            { return (nBits>>5) + ((nBits&31) > 0);           }
00120 static inline int          Hop_TruthWordNum( int nVars )          { return nVars <= 5 ? 1 : (1 << (nVars - 5));     }
00121 static inline int          Hop_InfoHasBit( unsigned * p, int i )  { return (p[(i)>>5] & (1<<((i) & 31))) > 0;       }
00122 static inline void         Hop_InfoSetBit( unsigned * p, int i )  { p[(i)>>5] |= (1<<((i) & 31));                   }
00123 static inline void         Hop_InfoXorBit( unsigned * p, int i )  { p[(i)>>5] ^= (1<<((i) & 31));                   }
00124 static inline int          Hop_Base2Log( unsigned n )             { int r; assert( n >= 0 ); if ( n < 2 ) return n; for ( r = 0, n--; n; n >>= 1, r++ ); return r; }
00125 static inline int          Hop_Base10Log( unsigned n )            { int r; assert( n >= 0 ); if ( n < 2 ) return n; for ( r = 0, n--; n; n /= 10, r++ ); return r; }
00126 
00127 static inline Hop_Obj_t *  Hop_Regular( Hop_Obj_t * p )           { return (Hop_Obj_t *)((unsigned long)(p) & ~01);      }
00128 static inline Hop_Obj_t *  Hop_Not( Hop_Obj_t * p )               { return (Hop_Obj_t *)((unsigned long)(p) ^  01);      }
00129 static inline Hop_Obj_t *  Hop_NotCond( Hop_Obj_t * p, int c )    { return (Hop_Obj_t *)((unsigned long)(p) ^ (c));      }
00130 static inline int          Hop_IsComplement( Hop_Obj_t * p )      { return (int )(((unsigned long)p) & 01);              }
00131 
00132 static inline Hop_Obj_t *  Hop_ManConst0( Hop_Man_t * p )         { return Hop_Not(p->pConst1);                     }
00133 static inline Hop_Obj_t *  Hop_ManConst1( Hop_Man_t * p )         { return p->pConst1;                              }
00134 static inline Hop_Obj_t *  Hop_ManGhost( Hop_Man_t * p )          { return &p->Ghost;                               }
00135 static inline Hop_Obj_t *  Hop_ManPi( Hop_Man_t * p, int i )      { return (Hop_Obj_t *)Vec_PtrEntry(p->vPis, i);   }
00136 static inline Hop_Obj_t *  Hop_ManPo( Hop_Man_t * p, int i )      { return (Hop_Obj_t *)Vec_PtrEntry(p->vPos, i);   }
00137 static inline Hop_Obj_t *  Hop_ManObj( Hop_Man_t * p, int i )     { return p->vObjs ? (Hop_Obj_t *)Vec_PtrEntry(p->vObjs, i) : NULL;  }
00138 
00139 static inline Hop_Edge_t   Hop_EdgeCreate( int Id, int fCompl )            { return (Id << 1) | fCompl;             }
00140 static inline int          Hop_EdgeId( Hop_Edge_t Edge )                   { return Edge >> 1;                      }
00141 static inline int          Hop_EdgeIsComplement( Hop_Edge_t Edge )         { return Edge & 1;                       }
00142 static inline Hop_Edge_t   Hop_EdgeRegular( Hop_Edge_t Edge )              { return (Edge >> 1) << 1;               }
00143 static inline Hop_Edge_t   Hop_EdgeNot( Hop_Edge_t Edge )                  { return Edge ^ 1;                       }
00144 static inline Hop_Edge_t   Hop_EdgeNotCond( Hop_Edge_t Edge, int fCond )   { return Edge ^ fCond;                   }
00145 
00146 static inline int          Hop_ManPiNum( Hop_Man_t * p )          { return p->nObjs[AIG_PI];                    }
00147 static inline int          Hop_ManPoNum( Hop_Man_t * p )          { return p->nObjs[AIG_PO];                    }
00148 static inline int          Hop_ManAndNum( Hop_Man_t * p )         { return p->nObjs[AIG_AND];                   }
00149 static inline int          Hop_ManExorNum( Hop_Man_t * p )        { return p->nObjs[AIG_EXOR];                  }
00150 static inline int          Hop_ManNodeNum( Hop_Man_t * p )        { return p->nObjs[AIG_AND]+p->nObjs[AIG_EXOR];}
00151 static inline int          Hop_ManGetCost( Hop_Man_t * p )        { return p->nObjs[AIG_AND]+3*p->nObjs[AIG_EXOR]; }
00152 static inline int          Hop_ManObjNum( Hop_Man_t * p )         { return p->nCreated - p->nDeleted;           }
00153 
00154 static inline Hop_Type_t   Hop_ObjType( Hop_Obj_t * pObj )        { return (Hop_Type_t)pObj->Type;               }
00155 static inline int          Hop_ObjIsNone( Hop_Obj_t * pObj )      { return pObj->Type == AIG_NONE;   }
00156 static inline int          Hop_ObjIsConst1( Hop_Obj_t * pObj )    { assert(!Hop_IsComplement(pObj)); return pObj->Type == AIG_CONST1; }
00157 static inline int          Hop_ObjIsPi( Hop_Obj_t * pObj )        { return pObj->Type == AIG_PI;     }
00158 static inline int          Hop_ObjIsPo( Hop_Obj_t * pObj )        { return pObj->Type == AIG_PO;     }
00159 static inline int          Hop_ObjIsAnd( Hop_Obj_t * pObj )       { return pObj->Type == AIG_AND;    }
00160 static inline int          Hop_ObjIsExor( Hop_Obj_t * pObj )      { return pObj->Type == AIG_EXOR;   }
00161 static inline int          Hop_ObjIsNode( Hop_Obj_t * pObj )      { return pObj->Type == AIG_AND || pObj->Type == AIG_EXOR;   }
00162 static inline int          Hop_ObjIsTerm( Hop_Obj_t * pObj )      { return pObj->Type == AIG_PI  || pObj->Type == AIG_PO || pObj->Type == AIG_CONST1; }
00163 static inline int          Hop_ObjIsHash( Hop_Obj_t * pObj )      { return pObj->Type == AIG_AND || pObj->Type == AIG_EXOR;   }
00164 
00165 static inline int          Hop_ObjIsMarkA( Hop_Obj_t * pObj )     { return pObj->fMarkA;  }
00166 static inline void         Hop_ObjSetMarkA( Hop_Obj_t * pObj )    { pObj->fMarkA = 1;     }
00167 static inline void         Hop_ObjClearMarkA( Hop_Obj_t * pObj )  { pObj->fMarkA = 0;     }
00168  
00169 static inline void         Hop_ObjSetTravId( Hop_Obj_t * pObj, int TravId )                { pObj->pData = (void *)TravId;                       }
00170 static inline void         Hop_ObjSetTravIdCurrent( Hop_Man_t * p, Hop_Obj_t * pObj )      { pObj->pData = (void *)p->nTravIds;                  }
00171 static inline void         Hop_ObjSetTravIdPrevious( Hop_Man_t * p, Hop_Obj_t * pObj )     { pObj->pData = (void *)(p->nTravIds - 1);            }
00172 static inline int          Hop_ObjIsTravIdCurrent( Hop_Man_t * p, Hop_Obj_t * pObj )       { return (int )((int)pObj->pData == p->nTravIds);     }
00173 static inline int          Hop_ObjIsTravIdPrevious( Hop_Man_t * p, Hop_Obj_t * pObj )      { return (int )((int)pObj->pData == p->nTravIds - 1); }
00174 
00175 static inline int          Hop_ObjTravId( Hop_Obj_t * pObj )      { return (int)pObj->pData;                       }
00176 static inline int          Hop_ObjPhase( Hop_Obj_t * pObj )       { return pObj->fPhase;                           }
00177 static inline int          Hop_ObjRefs( Hop_Obj_t * pObj )        { return pObj->nRefs;                            }
00178 static inline void         Hop_ObjRef( Hop_Obj_t * pObj )         { pObj->nRefs++;                                 }
00179 static inline void         Hop_ObjDeref( Hop_Obj_t * pObj )       { assert( pObj->nRefs > 0 ); pObj->nRefs--;      }
00180 static inline void         Hop_ObjClearRef( Hop_Obj_t * pObj )    { pObj->nRefs = 0;                               }
00181 static inline int          Hop_ObjFaninC0( Hop_Obj_t * pObj )     { return Hop_IsComplement(pObj->pFanin0);        }
00182 static inline int          Hop_ObjFaninC1( Hop_Obj_t * pObj )     { return Hop_IsComplement(pObj->pFanin1);        }
00183 static inline Hop_Obj_t *  Hop_ObjFanin0( Hop_Obj_t * pObj )      { return Hop_Regular(pObj->pFanin0);             }
00184 static inline Hop_Obj_t *  Hop_ObjFanin1( Hop_Obj_t * pObj )      { return Hop_Regular(pObj->pFanin1);             }
00185 static inline Hop_Obj_t *  Hop_ObjChild0( Hop_Obj_t * pObj )      { return pObj->pFanin0;                          }
00186 static inline Hop_Obj_t *  Hop_ObjChild1( Hop_Obj_t * pObj )      { return pObj->pFanin1;                          }
00187 static inline Hop_Obj_t *  Hop_ObjChild0Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin0(pObj)? Hop_NotCond((Hop_Obj_t *)Hop_ObjFanin0(pObj)->pData, Hop_ObjFaninC0(pObj)) : NULL;  }
00188 static inline Hop_Obj_t *  Hop_ObjChild1Copy( Hop_Obj_t * pObj ) { assert( !Hop_IsComplement(pObj) ); return Hop_ObjFanin1(pObj)? Hop_NotCond((Hop_Obj_t *)Hop_ObjFanin1(pObj)->pData, Hop_ObjFaninC1(pObj)) : NULL;  }
00189 static inline int          Hop_ObjLevel( Hop_Obj_t * pObj )       { return pObj->nRefs;                            }
00190 static inline int          Hop_ObjLevelNew( Hop_Obj_t * pObj )    { return 1 + Hop_ObjIsExor(pObj) + AIG_MAX(Hop_ObjFanin0(pObj)->nRefs, Hop_ObjFanin1(pObj)->nRefs);       }
00191 static inline int          Hop_ObjFaninPhase( Hop_Obj_t * pObj )  { return Hop_IsComplement(pObj)? !Hop_Regular(pObj)->fPhase : pObj->fPhase; }
00192 static inline void         Hop_ObjClean( Hop_Obj_t * pObj )       { memset( pObj, 0, sizeof(Hop_Obj_t) ); }
00193 static inline int          Hop_ObjWhatFanin( Hop_Obj_t * pObj, Hop_Obj_t * pFanin )    
00194 { 
00195     if ( Hop_ObjFanin0(pObj) == pFanin ) return 0; 
00196     if ( Hop_ObjFanin1(pObj) == pFanin ) return 1; 
00197     assert(0); return -1; 
00198 }
00199 static inline int          Hop_ObjFanoutC( Hop_Obj_t * pObj, Hop_Obj_t * pFanout )    
00200 { 
00201     if ( Hop_ObjFanin0(pFanout) == pObj ) return Hop_ObjFaninC0(pObj); 
00202     if ( Hop_ObjFanin1(pFanout) == pObj ) return Hop_ObjFaninC1(pObj); 
00203     assert(0); return -1; 
00204 }
00205 
00206 // create the ghost of the new node
00207 static inline Hop_Obj_t *  Hop_ObjCreateGhost( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Type_t Type )    
00208 {
00209     Hop_Obj_t * pGhost;
00210     assert( Type != AIG_AND || !Hop_ObjIsConst1(Hop_Regular(p0)) );
00211     assert( p1 == NULL || !Hop_ObjIsConst1(Hop_Regular(p1)) );
00212     assert( Type == AIG_PI || Hop_Regular(p0) != Hop_Regular(p1) );
00213     pGhost = Hop_ManGhost(p);
00214     pGhost->Type = Type;
00215     if ( Hop_Regular(p0)->Id < Hop_Regular(p1)->Id )
00216     {
00217         pGhost->pFanin0 = p0;
00218         pGhost->pFanin1 = p1;
00219     }
00220     else
00221     {
00222         pGhost->pFanin0 = p1;
00223         pGhost->pFanin1 = p0;
00224     }
00225     return pGhost;
00226 }
00227 
00228 // internal memory manager
00229 static inline Hop_Obj_t * Hop_ManFetchMemory( Hop_Man_t * p )  
00230 { 
00231     extern void Hop_ManAddMemory( Hop_Man_t * p );
00232     Hop_Obj_t * pTemp;
00233     if ( p->pListFree == NULL )
00234         Hop_ManAddMemory( p );
00235     pTemp = p->pListFree;
00236     p->pListFree = *((Hop_Obj_t **)pTemp);
00237     memset( pTemp, 0, sizeof(Hop_Obj_t) ); 
00238     if ( p->vObjs )
00239     {
00240         assert( p->nCreated == Vec_PtrSize(p->vObjs) );
00241         Vec_PtrPush( p->vObjs, pTemp );
00242     }
00243     pTemp->Id = p->nCreated++;
00244     return pTemp;
00245 }
00246 static inline void Hop_ManRecycleMemory( Hop_Man_t * p, Hop_Obj_t * pEntry )
00247 {
00248     pEntry->Type = AIG_NONE; // distinquishes dead node from live node
00249     *((Hop_Obj_t **)pEntry) = p->pListFree;
00250     p->pListFree = pEntry;
00251 }
00252 
00253 
00257 
00258 // iterator over the primary inputs
00259 #define Hop_ManForEachPi( p, pObj, i )                                          \
00260     Vec_PtrForEachEntry( p->vPis, pObj, i )
00261 // iterator over the primary outputs
00262 #define Hop_ManForEachPo( p, pObj, i )                                          \
00263     Vec_PtrForEachEntry( p->vPos, pObj, i )
00264 // iterator over all objects, including those currently not used
00265 #define Hop_ManForEachNode( p, pObj, i )                                        \
00266     for ( i = 0; i < p->nTableSize; i++ )                                       \
00267         if ( ((pObj) = p->pTable[i]) == NULL ) {} else
00268 
00272 
00273 /*=== hopBalance.c ========================================================*/
00274 extern Hop_Man_t *     Hop_ManBalance( Hop_Man_t * p, int fUpdateLevel );
00275 extern Hop_Obj_t *     Hop_NodeBalanceBuildSuper( Hop_Man_t * p, Vec_Ptr_t * vSuper, Hop_Type_t Type, int fUpdateLevel );
00276 /*=== hopCheck.c ========================================================*/
00277 extern int             Hop_ManCheck( Hop_Man_t * p );
00278 /*=== hopDfs.c ==========================================================*/
00279 extern Vec_Ptr_t *     Hop_ManDfs( Hop_Man_t * p );
00280 extern Vec_Ptr_t *     Hop_ManDfsNode( Hop_Man_t * p, Hop_Obj_t * pNode );
00281 extern int             Hop_ManCountLevels( Hop_Man_t * p );
00282 extern void            Hop_ManCreateRefs( Hop_Man_t * p );
00283 extern int             Hop_DagSize( Hop_Obj_t * pObj );
00284 extern void            Hop_ConeUnmark_rec( Hop_Obj_t * pObj );
00285 extern Hop_Obj_t *     Hop_Transfer( Hop_Man_t * pSour, Hop_Man_t * pDest, Hop_Obj_t * pObj, int nVars );
00286 extern Hop_Obj_t *     Hop_Compose( Hop_Man_t * p, Hop_Obj_t * pRoot, Hop_Obj_t * pFunc, int iVar );
00287 /*=== hopMan.c ==========================================================*/
00288 extern Hop_Man_t *     Hop_ManStart();
00289 extern Hop_Man_t *     Hop_ManDup( Hop_Man_t * p );
00290 extern void            Hop_ManStop( Hop_Man_t * p );
00291 extern int             Hop_ManCleanup( Hop_Man_t * p );
00292 extern void            Hop_ManPrintStats( Hop_Man_t * p );
00293 /*=== hopMem.c ==========================================================*/
00294 extern void            Hop_ManStartMemory( Hop_Man_t * p );
00295 extern void            Hop_ManStopMemory( Hop_Man_t * p );
00296 /*=== hopObj.c ==========================================================*/
00297 extern Hop_Obj_t *     Hop_ObjCreatePi( Hop_Man_t * p );
00298 extern Hop_Obj_t *     Hop_ObjCreatePo( Hop_Man_t * p, Hop_Obj_t * pDriver );
00299 extern Hop_Obj_t *     Hop_ObjCreate( Hop_Man_t * p, Hop_Obj_t * pGhost );
00300 extern void            Hop_ObjConnect( Hop_Man_t * p, Hop_Obj_t * pObj, Hop_Obj_t * pFan0, Hop_Obj_t * pFan1 );
00301 extern void            Hop_ObjDisconnect( Hop_Man_t * p, Hop_Obj_t * pObj );
00302 extern void            Hop_ObjDelete( Hop_Man_t * p, Hop_Obj_t * pObj );
00303 extern void            Hop_ObjDelete_rec( Hop_Man_t * p, Hop_Obj_t * pObj );
00304 extern Hop_Obj_t *     Hop_ObjRepr( Hop_Obj_t * pObj );
00305 extern void            Hop_ObjCreateChoice( Hop_Obj_t * pOld, Hop_Obj_t * pNew );
00306 /*=== hopOper.c =========================================================*/
00307 extern Hop_Obj_t *     Hop_IthVar( Hop_Man_t * p, int i );
00308 extern Hop_Obj_t *     Hop_Oper( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Type_t Type );
00309 extern Hop_Obj_t *     Hop_And( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 );
00310 extern Hop_Obj_t *     Hop_Or( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 );
00311 extern Hop_Obj_t *     Hop_Exor( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 );
00312 extern Hop_Obj_t *     Hop_Mux( Hop_Man_t * p, Hop_Obj_t * pC, Hop_Obj_t * p1, Hop_Obj_t * p0 );
00313 extern Hop_Obj_t *     Hop_Maj( Hop_Man_t * p, Hop_Obj_t * pA, Hop_Obj_t * pB, Hop_Obj_t * pC );
00314 extern Hop_Obj_t *     Hop_Miter( Hop_Man_t * p, Vec_Ptr_t * vPairs );
00315 extern Hop_Obj_t *     Hop_CreateAnd( Hop_Man_t * p, int nVars );
00316 extern Hop_Obj_t *     Hop_CreateOr( Hop_Man_t * p, int nVars );
00317 extern Hop_Obj_t *     Hop_CreateExor( Hop_Man_t * p, int nVars );
00318 /*=== hopTable.c ========================================================*/
00319 extern Hop_Obj_t *     Hop_TableLookup( Hop_Man_t * p, Hop_Obj_t * pGhost );
00320 extern void            Hop_TableInsert( Hop_Man_t * p, Hop_Obj_t * pObj );
00321 extern void            Hop_TableDelete( Hop_Man_t * p, Hop_Obj_t * pObj );
00322 extern int             Hop_TableCountEntries( Hop_Man_t * p );
00323 extern void            Hop_TableProfile( Hop_Man_t * p );
00324 /*=== hopUtil.c =========================================================*/
00325 extern void            Hop_ManIncrementTravId( Hop_Man_t * p );
00326 extern void            Hop_ManCleanData( Hop_Man_t * p );
00327 extern void            Hop_ObjCleanData_rec( Hop_Obj_t * pObj );
00328 extern void            Hop_ObjCollectMulti( Hop_Obj_t * pFunc, Vec_Ptr_t * vSuper );
00329 extern int             Hop_ObjIsMuxType( Hop_Obj_t * pObj );
00330 extern int             Hop_ObjRecognizeExor( Hop_Obj_t * pObj, Hop_Obj_t ** ppFan0, Hop_Obj_t ** ppFan1 );
00331 extern Hop_Obj_t *     Hop_ObjRecognizeMux( Hop_Obj_t * pObj, Hop_Obj_t ** ppObjT, Hop_Obj_t ** ppObjE );
00332 extern void            Hop_ObjPrintEqn( FILE * pFile, Hop_Obj_t * pObj, Vec_Vec_t * vLevels, int Level );
00333 extern void            Hop_ObjPrintVerilog( FILE * pFile, Hop_Obj_t * pObj, Vec_Vec_t * vLevels, int Level );
00334 extern void            Hop_ObjPrintVerbose( Hop_Obj_t * pObj, int fHaig );
00335 extern void            Hop_ManPrintVerbose( Hop_Man_t * p, int fHaig );
00336 extern void            Hop_ManDumpBlif( Hop_Man_t * p, char * pFileName );
00337 
00338 #ifdef __cplusplus
00339 }
00340 #endif
00341 
00342 #endif
00343 
00347