src/base/abc/abcDfs.c File Reference
#include "abc.h"
Go to the source code of this file.
Function Documentation
Function*************************************************************
Synopsis [Returns the DFS ordered array of logic nodes.]
Description [Collects only the internal nodes, leaving out CIs/COs. However it marks both CIs and COs with the current TravId.]
SideEffects []
SeeAlso []
Definition at line 798 of file abcDfs.c.
00799 { 00800 Vec_Ptr_t * vNodes; 00801 Abc_Obj_t * pNode; 00802 int i; 00803 assert( Abc_NtkIsStrash(pNtk) ); 00804 // set the traversal ID 00805 Abc_NtkIncrementTravId( pNtk ); 00806 // start the array of nodes 00807 vNodes = Vec_PtrAlloc( 100 ); 00808 // go through the PO nodes and call for each of them 00809 Abc_NtkForEachCo( pNtk, pNode, i ) 00810 { 00811 Abc_AigDfs_rec( Abc_ObjFanin0(pNode), vNodes ); 00812 Abc_NodeSetTravIdCurrent( pNode ); 00813 if ( fCollectCos ) 00814 Vec_PtrPush( vNodes, pNode ); 00815 } 00816 // collect dangling nodes if asked to 00817 if ( fCollectAll ) 00818 { 00819 Abc_NtkForEachNode( pNtk, pNode, i ) 00820 if ( !Abc_NodeIsTravIdCurrent(pNode) ) 00821 Abc_AigDfs_rec( pNode, vNodes ); 00822 } 00823 return vNodes; 00824 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 762 of file abcDfs.c.
00763 { 00764 Abc_Obj_t * pFanin; 00765 int i; 00766 // if this node is already visited, skip 00767 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00768 return; 00769 // mark the node as visited 00770 Abc_NodeSetTravIdCurrent( pNode ); 00771 // skip the PI 00772 if ( Abc_ObjIsCi(pNode) || Abc_AigNodeIsConst(pNode) ) 00773 return; 00774 assert( Abc_ObjIsNode( pNode ) ); 00775 // visit the transitive fanin of the node 00776 Abc_ObjForEachFanin( pNode, pFanin, i ) 00777 Abc_AigDfs_rec( pFanin, vNodes ); 00778 // visit the equivalent nodes 00779 if ( Abc_AigNodeIsChoice( pNode ) ) 00780 for ( pFanin = pNode->pData; pFanin; pFanin = pFanin->pData ) 00781 Abc_AigDfs_rec( pFanin, vNodes ); 00782 // add the node after the fanins have been added 00783 Vec_PtrPush( vNodes, pNode ); 00784 }
Function*************************************************************
Synopsis [Returns nodes by level from the smallest to the largest.]
Description [Correctly handles the case of choice nodes, by first spreading them out across several levels and then collecting.]
SideEffects [What happens with dangling nodes???]
SeeAlso []
Definition at line 1234 of file abcDfs.c.
01235 { 01236 Vec_Ptr_t * vNodes, * vLevels; 01237 Abc_Obj_t * pNode, ** ppHead; 01238 int LevelMax, i; 01239 assert( Abc_NtkIsStrash(pNtk) ); 01240 // set the correct levels 01241 Abc_NtkCleanCopy( pNtk ); 01242 LevelMax = Abc_AigSetChoiceLevels( pNtk ); 01243 // relink nodes by level 01244 vLevels = Vec_PtrStart( LevelMax + 1 ); 01245 Abc_NtkForEachNode( pNtk, pNode, i ) 01246 { 01247 ppHead = ((Abc_Obj_t **)vLevels->pArray) + (int)pNode->pCopy; 01248 pNode->pCopy = *ppHead; 01249 *ppHead = pNode; 01250 } 01251 // recollect nodes 01252 vNodes = Vec_PtrStart( Abc_NtkNodeNum(pNtk) ); 01253 Vec_PtrForEachEntryStart( vLevels, pNode, i, !fCollectCis ) 01254 for ( ; pNode; pNode = pNode->pCopy ) 01255 Vec_PtrPush( vNodes, pNode ); 01256 Vec_PtrFree( vLevels ); 01257 return vNodes; 01258 }
| int Abc_AigSetChoiceLevels | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Resets the levels of the nodes in the choice graph.]
Description [Makes the level of the choice nodes to be equal to the maximum of the level of the nodes in the equivalence class. This way sorting by level leads to the reverse topological order, which is needed for the required time computation.]
SideEffects []
SeeAlso []
Definition at line 1196 of file abcDfs.c.
01197 { 01198 Abc_Obj_t * pObj; 01199 int i, LevelMax, LevelCur; 01200 assert( Abc_NtkIsStrash(pNtk) ); 01201 // set the new travid counter 01202 Abc_NtkIncrementTravId( pNtk ); 01203 // set levels of the CI and constant 01204 Abc_NtkForEachCi( pNtk, pObj, i ) 01205 { 01206 Abc_NodeSetTravIdCurrent( pObj ); 01207 pObj->pCopy = NULL; 01208 } 01209 pObj = Abc_AigConst1( pNtk ); 01210 Abc_NodeSetTravIdCurrent( pObj ); 01211 pObj->pCopy = NULL; 01212 // set levels of all other nodes 01213 LevelMax = 0; 01214 Abc_NtkForEachCo( pNtk, pObj, i ) 01215 { 01216 LevelCur = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pObj), 1 ); 01217 LevelMax = ABC_MAX( LevelMax, LevelCur ); 01218 } 01219 return LevelMax; 01220 }
Function*************************************************************
Synopsis [Collects nodes in the DFS manner by level.]
Description [The number of levels should be set!!!]
SideEffects []
SeeAlso []
Definition at line 869 of file abcDfs.c.
00870 { 00871 Vec_Vec_t * vLevels; 00872 Abc_Obj_t * pFanout; 00873 int i; 00874 assert( fTfi == 0 ); 00875 assert( !Abc_NtkIsNetlist(pNode->pNtk) ); 00876 // set the traversal ID 00877 Abc_NtkIncrementTravId( pNode->pNtk ); 00878 vLevels = Vec_VecAlloc( 100 ); 00879 if ( Abc_ObjIsNode(pNode) ) 00880 Abc_DfsLevelizedTfo_rec( pNode, vLevels ); 00881 else 00882 { 00883 assert( Abc_ObjIsCi(pNode) ); 00884 Abc_NodeSetTravIdCurrent( pNode ); 00885 Abc_ObjForEachFanout( pNode, pFanout, i ) 00886 Abc_DfsLevelizedTfo_rec( pFanout, vLevels ); 00887 } 00888 return vLevels; 00889 }
Function*************************************************************
Synopsis [Collects nodes in the DFS manner by level.]
Description [The number of levels should be set!!!]
SideEffects []
SeeAlso []
Definition at line 838 of file abcDfs.c.
00839 { 00840 Abc_Obj_t * pFanout; 00841 int i; 00842 // if this node is already visited, skip 00843 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00844 return; 00845 // mark the node as visited 00846 Abc_NodeSetTravIdCurrent( pNode ); 00847 // skip the terminals 00848 if ( Abc_ObjIsCo(pNode) ) 00849 return; 00850 assert( Abc_ObjIsNode(pNode) ); 00851 // add the node to the structure 00852 Vec_VecPush( vLevels, pNode->Level, pNode ); 00853 // visit the TFO 00854 Abc_ObjForEachFanout( pNode, pFanout, i ) 00855 Abc_DfsLevelizedTfo_rec( pFanout, vLevels ); 00856 }
| int Abc_NodeSetChoiceLevel_rec | ( | Abc_Obj_t * | pNode, | |
| int | fMaximum | |||
| ) |
Function*************************************************************
Synopsis [Analyses choice nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 1155 of file abcDfs.c.
01156 { 01157 Abc_Obj_t * pTemp; 01158 int Level1, Level2, Level, LevelE; 01159 // skip the visited node 01160 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 01161 return (int)pNode->pCopy; 01162 Abc_NodeSetTravIdCurrent( pNode ); 01163 // compute levels of the children nodes 01164 Level1 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pNode), fMaximum ); 01165 Level2 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin1(pNode), fMaximum ); 01166 Level = 1 + ABC_MAX( Level1, Level2 ); 01167 if ( pNode->pData ) 01168 { 01169 LevelE = Abc_NodeSetChoiceLevel_rec( pNode->pData, fMaximum ); 01170 if ( fMaximum ) 01171 Level = ABC_MAX( Level, LevelE ); 01172 else 01173 Level = ABC_MIN( Level, LevelE ); 01174 // set the level of all equivalent nodes to be the same minimum 01175 for ( pTemp = pNode->pData; pTemp; pTemp = pTemp->pData ) 01176 pTemp->pCopy = (void *)Level; 01177 } 01178 pNode->pCopy = (void *)Level; 01179 return Level; 01180 }
Function*************************************************************
Synopsis [Returns the DFS ordered array of logic nodes.]
Description [Collects only the internal nodes, leaving CIs and CO. However it marks with the current TravId both CIs and COs.]
SideEffects []
SeeAlso []
Definition at line 78 of file abcDfs.c.
00079 { 00080 Vec_Ptr_t * vNodes; 00081 Abc_Obj_t * pObj; 00082 int i; 00083 // set the traversal ID 00084 Abc_NtkIncrementTravId( pNtk ); 00085 // start the array of nodes 00086 vNodes = Vec_PtrAlloc( 100 ); 00087 Abc_NtkForEachCo( pNtk, pObj, i ) 00088 { 00089 Abc_NodeSetTravIdCurrent( pObj ); 00090 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes ); 00091 } 00092 // collect dangling nodes if asked to 00093 if ( fCollectAll ) 00094 { 00095 Abc_NtkForEachNode( pNtk, pObj, i ) 00096 if ( !Abc_NodeIsTravIdCurrent(pObj) ) 00097 Abc_NtkDfs_rec( pObj, vNodes ); 00098 } 00099 return vNodes; 00100 }
Function*************************************************************
Synopsis [Iterative version of the DFS procedure.]
Description []
SideEffects []
SeeAlso []
Definition at line 474 of file abcDfs.c.
00475 { 00476 Abc_Obj_t * pNode, * pFanin; 00477 int iFanin; 00478 // if this node is already visited, skip 00479 if ( Abc_NodeIsTravIdCurrent( pRoot ) ) 00480 return; 00481 // mark the node as visited 00482 Abc_NodeSetTravIdCurrent( pRoot ); 00483 // skip the CI 00484 if ( Abc_ObjIsCi(pRoot) || (Abc_NtkIsStrash(pRoot->pNtk) && Abc_AigNodeIsConst(pRoot)) ) 00485 return; 00486 // add the CI 00487 Vec_PtrClear( vStack ); 00488 Vec_PtrPush( vStack, pRoot ); 00489 Vec_PtrPush( vStack, (void *)0 ); 00490 while ( Vec_PtrSize(vStack) > 0 ) 00491 { 00492 // get the node and its fanin 00493 iFanin = (int)Vec_PtrPop(vStack); 00494 pNode = Vec_PtrPop(vStack); 00495 assert( !Abc_ObjIsNet(pNode) ); 00496 // add it to the array of nodes if we finished 00497 if ( iFanin == Abc_ObjFaninNum(pNode) ) 00498 { 00499 Vec_PtrPush( vNodes, pNode ); 00500 continue; 00501 } 00502 // explore the next fanin 00503 Vec_PtrPush( vStack, pNode ); 00504 Vec_PtrPush( vStack, (void *)(iFanin+1) ); 00505 // get the fanin 00506 pFanin = Abc_ObjFanin0Ntk( Abc_ObjFanin(pNode,iFanin) ); 00507 // if this node is already visited, skip 00508 if ( Abc_NodeIsTravIdCurrent( pFanin ) ) 00509 continue; 00510 // mark the node as visited 00511 Abc_NodeSetTravIdCurrent( pFanin ); 00512 // skip the CI 00513 if ( Abc_ObjIsCi(pFanin) || (Abc_NtkIsStrash(pFanin->pNtk) && Abc_AigNodeIsConst(pFanin)) ) 00514 continue; 00515 Vec_PtrPush( vStack, pFanin ); 00516 Vec_PtrPush( vStack, (void *)0 ); 00517 } 00518 }
CFile****************************************************************
FileName [abcDfs.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Procedures that use depth-first search.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [
- Id
- abcDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp
] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 42 of file abcDfs.c.
00043 { 00044 Abc_Obj_t * pFanin; 00045 int i; 00046 assert( !Abc_ObjIsNet(pNode) ); 00047 // if this node is already visited, skip 00048 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00049 return; 00050 // mark the node as visited 00051 Abc_NodeSetTravIdCurrent( pNode ); 00052 // skip the CI 00053 if ( Abc_ObjIsCi(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsConst(pNode)) ) 00054 return; 00055 assert( Abc_ObjIsNode( pNode ) || Abc_ObjIsBox( pNode ) ); 00056 // visit the transitive fanin of the node 00057 Abc_ObjForEachFanin( pNode, pFanin, i ) 00058 { 00059 // pFanin = Abc_ObjFanin( pNode, Abc_ObjFaninNum(pNode)-1-i ); 00060 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(pFanin), vNodes ); 00061 } 00062 // add the node after the fanins have been added 00063 Vec_PtrPush( vNodes, pNode ); 00064 }
Function*************************************************************
Synopsis [Returns the DFS ordered array of all objects.]
Description [This procedure collects everything from POs to PIs.]
SideEffects []
SeeAlso []
Definition at line 597 of file abcDfs.c.
00598 { 00599 Vec_Ptr_t * vNodes; 00600 Abc_Obj_t * pObj; 00601 int i; 00602 // set the traversal ID 00603 Abc_NtkIncrementTravId( pNtk ); 00604 // start the array of nodes 00605 vNodes = Vec_PtrAlloc( 100 ); 00606 Abc_NtkForEachPo( pNtk, pObj, i ) 00607 Abc_NtkDfsHie_rec( pObj, vNodes ); 00608 // collect dangling nodes if asked to 00609 if ( fCollectAll ) 00610 { 00611 Abc_NtkForEachObj( pNtk, pObj, i ) 00612 if ( !Abc_NodeIsTravIdCurrent(pObj) ) 00613 Abc_NtkDfs_rec( pObj, vNodes ); 00614 } 00615 return vNodes; 00616 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 570 of file abcDfs.c.
00571 { 00572 Abc_Obj_t * pFanin; 00573 int i; 00574 // if this node is already visited, skip 00575 if ( Abc_NodeIsTravIdCurrent( pObj ) ) 00576 return; 00577 // mark the node as visited 00578 Abc_NodeSetTravIdCurrent( pObj ); 00579 // visit the transitive fanin of the node 00580 Abc_ObjForEachFanin( pObj, pFanin, i ) 00581 Abc_NtkDfsHie_rec( pFanin, vNodes ); 00582 // add the node after the fanins have been added 00583 Vec_PtrPush( vNodes, pObj ); 00584 }
Function*************************************************************
Synopsis [Returns the DFS ordered array of logic nodes.]
Description [Collects only the internal nodes, leaving CIs and CO. However it marks with the current TravId both CIs and COs.]
SideEffects []
SeeAlso []
Definition at line 532 of file abcDfs.c.
00533 { 00534 Vec_Ptr_t * vNodes, * vStack; 00535 Abc_Obj_t * pObj; 00536 int i; 00537 // set the traversal ID 00538 Abc_NtkIncrementTravId( pNtk ); 00539 // start the array of nodes 00540 vNodes = Vec_PtrAlloc( 1000 ); 00541 vStack = Vec_PtrAlloc( 1000 ); 00542 Abc_NtkForEachCo( pNtk, pObj, i ) 00543 { 00544 Abc_NodeSetTravIdCurrent( pObj ); 00545 Abc_NtkDfs_iter( vStack, Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes ); 00546 } 00547 // collect dangling nodes if asked to 00548 if ( fCollectAll ) 00549 { 00550 Abc_NtkForEachNode( pNtk, pObj, i ) 00551 if ( !Abc_NodeIsTravIdCurrent(pObj) ) 00552 Abc_NtkDfs_iter( vStack, pObj, vNodes ); 00553 } 00554 Vec_PtrFree( vStack ); 00555 return vNodes; 00556 }
Function*************************************************************
Synopsis [Returns the DFS ordered array of logic nodes.]
Description [Collects only the internal nodes, leaving out PIs, POs and latches.]
SideEffects []
SeeAlso []
Definition at line 113 of file abcDfs.c.
00114 { 00115 Vec_Ptr_t * vNodes; 00116 int i; 00117 // set the traversal ID 00118 Abc_NtkIncrementTravId( pNtk ); 00119 // start the array of nodes 00120 vNodes = Vec_PtrAlloc( 100 ); 00121 // go through the PO nodes and call for each of them 00122 for ( i = 0; i < nNodes; i++ ) 00123 { 00124 if ( Abc_ObjIsCo(ppNodes[i]) ) 00125 { 00126 Abc_NodeSetTravIdCurrent(ppNodes[i]); 00127 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(ppNodes[i])), vNodes ); 00128 } 00129 else if ( Abc_ObjIsNode(ppNodes[i]) ) 00130 Abc_NtkDfs_rec( ppNodes[i], vNodes ); 00131 } 00132 return vNodes; 00133 }
Function*************************************************************
Synopsis [Returns the reverse DFS ordered array of logic nodes.]
Description [Collects only the internal nodes, leaving out CIs/COs. However it marks both CIs and COs with the current TravId.]
SideEffects []
SeeAlso []
Definition at line 181 of file abcDfs.c.
00182 { 00183 Vec_Ptr_t * vNodes; 00184 Abc_Obj_t * pObj, * pFanout; 00185 int i, k; 00186 // set the traversal ID 00187 Abc_NtkIncrementTravId( pNtk ); 00188 // start the array of nodes 00189 vNodes = Vec_PtrAlloc( 100 ); 00190 Abc_NtkForEachCi( pNtk, pObj, i ) 00191 { 00192 Abc_NodeSetTravIdCurrent( pObj ); 00193 pObj = Abc_ObjFanout0Ntk(pObj); 00194 Abc_ObjForEachFanout( pObj, pFanout, k ) 00195 Abc_NtkDfsReverse_rec( pFanout, vNodes ); 00196 } 00197 // add constant nodes in the end 00198 if ( !Abc_NtkIsStrash(pNtk) ) 00199 Abc_NtkForEachNode( pNtk, pObj, i ) 00200 if ( Abc_NodeIsConst(pObj) ) 00201 Vec_PtrPush( vNodes, pObj ); 00202 return vNodes; 00203 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 147 of file abcDfs.c.
00148 { 00149 Abc_Obj_t * pFanout; 00150 int i; 00151 assert( !Abc_ObjIsNet(pNode) ); 00152 // if this node is already visited, skip 00153 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00154 return; 00155 // mark the node as visited 00156 Abc_NodeSetTravIdCurrent( pNode ); 00157 // skip the CI 00158 if ( Abc_ObjIsCo(pNode) ) 00159 return; 00160 assert( Abc_ObjIsNode( pNode ) ); 00161 // visit the transitive fanin of the node 00162 pNode = Abc_ObjFanout0Ntk(pNode); 00163 Abc_ObjForEachFanout( pNode, pFanout, i ) 00164 Abc_NtkDfsReverse_rec( pFanout, vNodes ); 00165 // add the node after the fanins have been added 00166 Vec_PtrPush( vNodes, pNode ); 00167 }
Function*************************************************************
Synopsis [Returns the levelized array of TFO nodes.]
Description [Collects the levelized array of internal nodes, leaving out CIs/COs. However it marks both CIs and COs with the current TravId.]
SideEffects []
SeeAlso []
Definition at line 253 of file abcDfs.c.
00254 { 00255 Vec_Ptr_t * vNodes; 00256 Abc_Obj_t * pObj, * pFanout; 00257 int i, k; 00258 assert( Abc_NtkIsStrash(pNtk) ); 00259 // set the traversal ID 00260 Abc_NtkIncrementTravId( pNtk ); 00261 // start the array of nodes 00262 vNodes = Vec_PtrStart( Abc_AigLevel(pNtk) + 1 ); 00263 for ( i = 0; i < nNodes; i++ ) 00264 { 00265 pObj = ppNodes[i]; 00266 assert( Abc_ObjIsCi(pObj) ); 00267 Abc_NodeSetTravIdCurrent( pObj ); 00268 pObj = Abc_ObjFanout0Ntk(pObj); 00269 Abc_ObjForEachFanout( pObj, pFanout, k ) 00270 Abc_NtkDfsReverseNodes_rec( pFanout, vNodes ); 00271 } 00272 return vNodes; 00273 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 216 of file abcDfs.c.
00217 { 00218 Abc_Obj_t * pFanout; 00219 int i; 00220 assert( !Abc_ObjIsNet(pNode) ); 00221 // if this node is already visited, skip 00222 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00223 return; 00224 // mark the node as visited 00225 Abc_NodeSetTravIdCurrent( pNode ); 00226 // skip the CI 00227 if ( Abc_ObjIsCo(pNode) ) 00228 return; 00229 assert( Abc_ObjIsNode( pNode ) ); 00230 // visit the transitive fanin of the node 00231 pNode = Abc_ObjFanout0Ntk(pNode); 00232 Abc_ObjForEachFanout( pNode, pFanout, i ) 00233 Abc_NtkDfsReverseNodes_rec( pFanout, vNodes ); 00234 // add the node after the fanins have been added 00235 // Vec_PtrPush( vNodes, pNode ); 00236 Vec_PtrFillExtra( vNodes, pNode->Level + 1, NULL ); 00237 pNode->pCopy = Vec_PtrEntry( vNodes, pNode->Level ); 00238 Vec_PtrWriteEntry( vNodes, pNode->Level, pNode ); 00239 }
Function*************************************************************
Synopsis [Returns the levelized array of TFO nodes.]
Description [Collects the levelized array of internal nodes, leaving out CIs/COs. However it marks both CIs and COs with the current TravId. Collects only the nodes whose support does not exceed the set of given CI nodes.]
SideEffects []
SeeAlso []
Definition at line 288 of file abcDfs.c.
00289 { 00290 Vec_Ptr_t * vNodes; 00291 Abc_Obj_t * pObj, * pFanout, * pFanin; 00292 int i, k, m, nLevels; 00293 // set the levels 00294 nLevels = Abc_NtkLevel( pNtk ); 00295 // set the traversal ID 00296 Abc_NtkIncrementTravId( pNtk ); 00297 // start the array of nodes 00298 vNodes = Vec_PtrStart( nLevels + 2 ); 00299 for ( i = 0; i < nNodes; i++ ) 00300 { 00301 pObj = ppNodes[i]; 00302 assert( Abc_ObjIsCi(pObj) ); 00303 Abc_NodeSetTravIdCurrent( pObj ); 00304 // add to the array 00305 assert( pObj->Level == 0 ); 00306 pObj->pCopy = Vec_PtrEntry( vNodes, pObj->Level ); 00307 Vec_PtrWriteEntry( vNodes, pObj->Level, pObj ); 00308 } 00309 // iterate through the levels 00310 for ( i = 0; i <= nLevels; i++ ) 00311 { 00312 // iterate through the nodes on each level 00313 for ( pObj = Vec_PtrEntry(vNodes, i); pObj; pObj = pObj->pCopy ) 00314 { 00315 // iterate through the fanouts of each node 00316 Abc_ObjForEachFanout( pObj, pFanout, k ) 00317 { 00318 // skip visited nodes 00319 if ( Abc_NodeIsTravIdCurrent(pFanout) ) 00320 continue; 00321 // visit the fanins of this fanout 00322 Abc_ObjForEachFanin( pFanout, pFanin, m ) 00323 { 00324 if ( !Abc_NodeIsTravIdCurrent(pFanin) ) 00325 break; 00326 } 00327 if ( m < Abc_ObjFaninNum(pFanout) ) 00328 continue; 00329 // all fanins are already collected 00330 00331 // mark the node as visited 00332 Abc_NodeSetTravIdCurrent( pFanout ); 00333 // handle the COs 00334 if ( Abc_ObjIsCo(pFanout) ) 00335 pFanout->Level = nLevels + 1; 00336 // add to the array 00337 pFanout->pCopy = Vec_PtrEntry( vNodes, pFanout->Level ); 00338 Vec_PtrWriteEntry( vNodes, pFanout->Level, pFanout ); 00339 // handle the COs 00340 if ( Abc_ObjIsCo(pFanout) ) 00341 pFanout->Level = 0; 00342 } 00343 } 00344 } 00345 return vNodes; 00346 }
Function*************************************************************
Synopsis [Returns the array of nodes and latches reachable from POs.]
Description []
SideEffects []
SeeAlso []
Definition at line 387 of file abcDfs.c.
00388 { 00389 Vec_Ptr_t * vNodes; 00390 Abc_Obj_t * pObj; 00391 int i; 00392 assert( !Abc_NtkIsNetlist(pNtk) ); 00393 // set the traversal ID 00394 Abc_NtkIncrementTravId( pNtk ); 00395 // start the array of nodes 00396 vNodes = Vec_PtrAlloc( 100 ); 00397 Abc_NtkForEachPo( pNtk, pObj, i ) 00398 Abc_NtkDfsSeq_rec( pObj, vNodes ); 00399 // mark the PIs 00400 Abc_NtkForEachPi( pNtk, pObj, i ) 00401 Abc_NtkDfsSeq_rec( pObj, vNodes ); 00402 return vNodes; 00403 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 360 of file abcDfs.c.
00361 { 00362 Abc_Obj_t * pFanin; 00363 int i; 00364 // if this node is already visited, skip 00365 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00366 return; 00367 // mark the node as visited 00368 Abc_NodeSetTravIdCurrent( pNode ); 00369 // visit the transitive fanin of the node 00370 Abc_ObjForEachFanin( pNode, pFanin, i ) 00371 Abc_NtkDfsSeq_rec( pFanin, vNodes ); 00372 // add the node after the fanins have been added 00373 Vec_PtrPush( vNodes, pNode ); 00374 }
Function*************************************************************
Synopsis [Returns the array of nodes and latches reachable from POs.]
Description []
SideEffects []
SeeAlso []
Definition at line 444 of file abcDfs.c.
00445 { 00446 Vec_Ptr_t * vNodes; 00447 Abc_Obj_t * pObj; 00448 int i; 00449 assert( !Abc_NtkIsNetlist(pNtk) ); 00450 // set the traversal ID 00451 Abc_NtkIncrementTravId( pNtk ); 00452 // start the array of nodes 00453 vNodes = Vec_PtrAlloc( 100 ); 00454 Abc_NtkForEachPi( pNtk, pObj, i ) 00455 Abc_NtkDfsSeqReverse_rec( pObj, vNodes ); 00456 // mark the logic feeding into POs 00457 Abc_NtkForEachPo( pNtk, pObj, i ) 00458 Abc_NtkDfsSeq_rec( pObj, vNodes ); 00459 return vNodes; 00460 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 417 of file abcDfs.c.
00418 { 00419 Abc_Obj_t * pFanout; 00420 int i; 00421 // if this node is already visited, skip 00422 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00423 return; 00424 // mark the node as visited 00425 Abc_NodeSetTravIdCurrent( pNode ); 00426 // visit the transitive fanin of the node 00427 Abc_ObjForEachFanout( pNode, pFanout, i ) 00428 Abc_NtkDfsSeqReverse_rec( pFanout, vNodes ); 00429 // add the node after the fanins have been added 00430 Vec_PtrPush( vNodes, pNode ); 00431 }
Function*************************************************************
Synopsis [Detects combinational loops.]
Description [This procedure is based on the idea suggested by Donald Chai. As we traverse the network and visit the nodes, we need to distinquish three types of nodes: (1) those that are visited for the first time, (2) those that have been visited in this traversal but are currently not on the traversal path, (3) those that have been visited and are currently on the travesal path. When the node of type (3) is encountered, it means that there is a combinational loop. To mark the three types of nodes, two new values of the traversal IDs are used.]
SideEffects []
SeeAlso []
Definition at line 1116 of file abcDfs.c.
01117 { 01118 Abc_Obj_t * pNode; 01119 int fAcyclic, i; 01120 // set the traversal ID for this DFS ordering 01121 Abc_NtkIncrementTravId( pNtk ); 01122 Abc_NtkIncrementTravId( pNtk ); 01123 // pNode->TravId == pNet->nTravIds means "pNode is on the path" 01124 // pNode->TravId == pNet->nTravIds - 1 means "pNode is visited but is not on the path" 01125 // pNode->TravId < pNet->nTravIds - 1 means "pNode is not visited" 01126 // traverse the network to detect cycles 01127 fAcyclic = 1; 01128 Abc_NtkForEachCo( pNtk, pNode, i ) 01129 { 01130 pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode)); 01131 if ( Abc_NodeIsTravIdPrevious(pNode) ) 01132 continue; 01133 // traverse the output logic cone 01134 if ( fAcyclic = Abc_NtkIsAcyclic_rec(pNode) ) 01135 continue; 01136 // stop as soon as the first loop is detected 01137 fprintf( stdout, " CO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) ); 01138 break; 01139 } 01140 return fAcyclic; 01141 }
Function*************************************************************
Synopsis [Recursively detects combinational loops.]
Description []
SideEffects []
SeeAlso []
Definition at line 1040 of file abcDfs.c.
01041 { 01042 Abc_Ntk_t * pNtk = pNode->pNtk; 01043 Abc_Obj_t * pFanin; 01044 int fAcyclic, i; 01045 assert( !Abc_ObjIsNet(pNode) ); 01046 if ( Abc_ObjIsCi(pNode) || Abc_ObjIsBox(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsConst(pNode)) ) 01047 return 1; 01048 assert( Abc_ObjIsNode(pNode) ); 01049 // make sure the node is not visited 01050 assert( !Abc_NodeIsTravIdPrevious(pNode) ); 01051 // check if the node is part of the combinational loop 01052 if ( Abc_NodeIsTravIdCurrent(pNode) ) 01053 { 01054 fprintf( stdout, "Network \"%s\" contains combinational loop!\n", Abc_NtkName(pNtk) ); 01055 fprintf( stdout, "Node \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(pNode) ); 01056 return 0; 01057 } 01058 // mark this node as a node on the current path 01059 Abc_NodeSetTravIdCurrent( pNode ); 01060 // visit the transitive fanin 01061 Abc_ObjForEachFanin( pNode, pFanin, i ) 01062 { 01063 pFanin = Abc_ObjFanin0Ntk(pFanin); 01064 // make sure there is no mixing of networks 01065 assert( pFanin->pNtk == pNode->pNtk ); 01066 // check if the fanin is visited 01067 if ( Abc_NodeIsTravIdPrevious(pFanin) ) 01068 continue; 01069 // traverse the fanin's cone searching for the loop 01070 if ( fAcyclic = Abc_NtkIsAcyclic_rec(pFanin) ) 01071 continue; 01072 // return as soon as the loop is detected 01073 fprintf( stdout, " %s ->", Abc_ObjName(pFanin) ); 01074 return 0; 01075 } 01076 // visit choices 01077 if ( Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsChoice(pNode) ) 01078 { 01079 for ( pFanin = pNode->pData; pFanin; pFanin = pFanin->pData ) 01080 { 01081 // check if the fanin is visited 01082 if ( Abc_NodeIsTravIdPrevious(pFanin) ) 01083 continue; 01084 // traverse the fanin's cone searching for the loop 01085 if ( fAcyclic = Abc_NtkIsAcyclic_rec(pFanin) ) 01086 continue; 01087 // return as soon as the loop is detected 01088 fprintf( stdout, " %s", Abc_ObjName(pFanin) ); 01089 fprintf( stdout, " (choice of %s) -> ", Abc_ObjName(pNode) ); 01090 return 0; 01091 } 01092 } 01093 // mark this node as a visited node 01094 Abc_NodeSetTravIdPrevious( pNode ); 01095 return 1; 01096 }
Function*************************************************************
Synopsis [Returns 1 if the ordering of nodes is DFS.]
Description []
SideEffects []
SeeAlso []
Definition at line 630 of file abcDfs.c.
00631 { 00632 Abc_Obj_t * pNode, * pFanin; 00633 int i, k; 00634 // set the traversal ID 00635 Abc_NtkIncrementTravId( pNtk ); 00636 // mark the CIs 00637 Abc_NtkForEachCi( pNtk, pNode, i ) 00638 Abc_NodeSetTravIdCurrent( pNode ); 00639 // go through the nodes 00640 Abc_NtkForEachNode( pNtk, pNode, i ) 00641 { 00642 // check the fanins of the node 00643 Abc_ObjForEachFanin( pNode, pFanin, k ) 00644 if ( !Abc_NodeIsTravIdCurrent(pFanin) ) 00645 return 0; 00646 // check the choices of the node 00647 if ( Abc_NtkIsStrash(pNtk) && Abc_AigNodeIsChoice(pNode) ) 00648 for ( pFanin = pNode->pData; pFanin; pFanin = pFanin->pData ) 00649 if ( !Abc_NodeIsTravIdCurrent(pFanin) ) 00650 return 0; 00651 // mark the node as visited 00652 Abc_NodeSetTravIdCurrent( pNode ); 00653 } 00654 return 1; 00655 }
| int Abc_NtkLevel | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Computes the number of logic levels not counting PIs/POs.]
Description []
SideEffects []
SeeAlso []
Definition at line 979 of file abcDfs.c.
00980 { 00981 Abc_Obj_t * pNode; 00982 int i, LevelsMax; 00983 // set the CI levels to zero 00984 Abc_NtkForEachCi( pNtk, pNode, i ) 00985 pNode->Level = 0; 00986 // perform the traversal 00987 LevelsMax = 0; 00988 Abc_NtkIncrementTravId( pNtk ); 00989 Abc_NtkForEachNode( pNtk, pNode, i ) 00990 { 00991 Abc_NtkLevel_rec( pNode ); 00992 if ( LevelsMax < (int)pNode->Level ) 00993 LevelsMax = (int)pNode->Level; 00994 } 00995 return LevelsMax; 00996 }
| int Abc_NtkLevel_rec | ( | Abc_Obj_t * | pNode | ) |
Function*************************************************************
Synopsis [Recursively counts the number of logic levels of one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 903 of file abcDfs.c.
00904 { 00905 Abc_Obj_t * pNext; 00906 int i, Level; 00907 assert( !Abc_ObjIsNet(pNode) ); 00908 // skip the PI 00909 if ( Abc_ObjIsCi(pNode) ) 00910 return pNode->Level; 00911 assert( Abc_ObjIsNode( pNode ) ); 00912 // if this node is already visited, return 00913 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00914 return pNode->Level; 00915 // mark the node as visited 00916 Abc_NodeSetTravIdCurrent( pNode ); 00917 // visit the transitive fanin 00918 pNode->Level = 0; 00919 Abc_ObjForEachFanin( pNode, pNext, i ) 00920 { 00921 Level = Abc_NtkLevel_rec( Abc_ObjFanin0Ntk(pNext) ); 00922 if ( pNode->Level < (unsigned)Level ) 00923 pNode->Level = Level; 00924 } 00925 if ( Abc_ObjFaninNum(pNode) > 0 ) 00926 pNode->Level++; 00927 return pNode->Level; 00928 }
| int Abc_NtkLevelReverse | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Computes the number of logic levels not counting PIs/POs.]
Description []
SideEffects []
SeeAlso []
Definition at line 1009 of file abcDfs.c.
01010 { 01011 Abc_Obj_t * pNode; 01012 int i, LevelsMax; 01013 // set the CO levels to zero 01014 Abc_NtkForEachCo( pNtk, pNode, i ) 01015 pNode->Level = 0; 01016 // perform the traversal 01017 LevelsMax = 0; 01018 Abc_NtkIncrementTravId( pNtk ); 01019 Abc_NtkForEachNode( pNtk, pNode, i ) 01020 { 01021 Abc_NtkLevelReverse_rec( pNode ); 01022 if ( LevelsMax < (int)pNode->Level ) 01023 LevelsMax = (int)pNode->Level; 01024 } 01025 return LevelsMax; 01026 }
| int Abc_NtkLevelReverse_rec | ( | Abc_Obj_t * | pNode | ) |
Function*************************************************************
Synopsis [Recursively counts the number of logic levels of one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 941 of file abcDfs.c.
00942 { 00943 Abc_Obj_t * pNext; 00944 int i, Level; 00945 assert( !Abc_ObjIsNet(pNode) ); 00946 // skip the PI 00947 if ( Abc_ObjIsCo(pNode) ) 00948 return pNode->Level; 00949 assert( Abc_ObjIsNode( pNode ) ); 00950 // if this node is already visited, return 00951 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00952 return pNode->Level; 00953 // mark the node as visited 00954 Abc_NodeSetTravIdCurrent( pNode ); 00955 // visit the transitive fanin 00956 pNode->Level = 0; 00957 Abc_ObjForEachFanout( pNode, pNext, i ) 00958 { 00959 Level = Abc_NtkLevelReverse_rec( Abc_ObjFanout0Ntk(pNext) ); 00960 if ( pNode->Level < (unsigned)Level ) 00961 pNode->Level = Level; 00962 } 00963 if ( Abc_ObjFaninNum(pNode) > 0 ) 00964 pNode->Level++; 00965 return pNode->Level; 00966 }
Function*************************************************************
Synopsis [Returns the set of CI nodes in the support of the given nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 733 of file abcDfs.c.
00734 { 00735 Vec_Ptr_t * vNodes; 00736 int i; 00737 // set the traversal ID 00738 Abc_NtkIncrementTravId( pNtk ); 00739 // start the array of nodes 00740 vNodes = Vec_PtrAlloc( 100 ); 00741 // go through the PO nodes and call for each of them 00742 for ( i = 0; i < nNodes; i++ ) 00743 if ( Abc_ObjIsCo(ppNodes[i]) ) 00744 Abc_NtkNodeSupport_rec( Abc_ObjFanin0(ppNodes[i]), vNodes ); 00745 else 00746 Abc_NtkNodeSupport_rec( ppNodes[i], vNodes ); 00747 return vNodes; 00748 }
Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
Definition at line 669 of file abcDfs.c.
00670 { 00671 Abc_Obj_t * pFanin; 00672 int i; 00673 assert( !Abc_ObjIsNet(pNode) ); 00674 // if this node is already visited, skip 00675 if ( Abc_NodeIsTravIdCurrent( pNode ) ) 00676 return; 00677 // mark the node as visited 00678 Abc_NodeSetTravIdCurrent( pNode ); 00679 // collect the CI 00680 if ( Abc_ObjIsCi(pNode) || Abc_ObjFaninNum(pNode) == 0 ) 00681 { 00682 Vec_PtrPush( vNodes, pNode ); 00683 return; 00684 } 00685 assert( Abc_ObjIsNode( pNode ) ); 00686 // visit the transitive fanin of the node 00687 Abc_ObjForEachFanin( pNode, pFanin, i ) 00688 Abc_NtkNodeSupport_rec( Abc_ObjFanin0Ntk(pFanin), vNodes ); 00689 }
Function*************************************************************
Synopsis [Returns the set of CI nodes in the support of the given nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 702 of file abcDfs.c.
00703 { 00704 Vec_Ptr_t * vNodes; 00705 Abc_Obj_t * pNode; 00706 int i; 00707 // set the traversal ID 00708 Abc_NtkIncrementTravId( pNtk ); 00709 // start the array of nodes 00710 vNodes = Vec_PtrAlloc( 100 ); 00711 // go through the PO nodes and call for each of them 00712 Abc_NtkForEachCo( pNtk, pNode, i ) 00713 Abc_NtkNodeSupport_rec( Abc_ObjFanin0(pNode), vNodes ); 00714 // add unused CIs 00715 Abc_NtkForEachCi( pNtk, pNode, i ) 00716 if ( !Abc_NodeIsTravIdCurrent( pNode ) ) 00717 Vec_PtrPush( vNodes, pNode ); 00718 assert( Vec_PtrSize(vNodes) == Abc_NtkCiNum(pNtk) ); 00719 return vNodes; 00720 }
