#include "abc.h"
#include "if.h"
#include "kit.h"
Go to the source code of this file.
typedef struct Abc_ManRec_t_ Abc_ManRec_t |
CFile****************************************************************
FileName [abcRec.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Record of semi-canonical AIG subgraphs.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [
] DECLARATIONS ///
void Abc_NtkRecAdd | ( | Abc_Ntk_t * | pNtk | ) |
Function*************************************************************
Synopsis [Performs renoding as technology mapping.]
Description []
SideEffects []
SeeAlso []
Definition at line 506 of file abcRec.c.
00507 { 00508 extern Abc_Ntk_t * Abc_NtkIf( Abc_Ntk_t * pNtk, If_Par_t * pPars ); 00509 extern int Abc_NtkRecAddCut( If_Man_t * pIfMan, If_Obj_t * pRoot, If_Cut_t * pCut ); 00510 00511 If_Par_t Pars, * pPars = &Pars; 00512 Abc_Ntk_t * pNtkNew; 00513 int clk = clock(); 00514 00515 if ( Abc_NtkGetChoiceNum( pNtk ) ) 00516 printf( "Performing renoding with choices.\n" ); 00517 00518 // set defaults 00519 memset( pPars, 0, sizeof(If_Par_t) ); 00520 // user-controlable paramters 00521 pPars->nLutSize = s_pMan->nVarsInit; 00522 pPars->nCutsMax = s_pMan->nCuts; 00523 pPars->nFlowIters = 0; 00524 pPars->nAreaIters = 0; 00525 pPars->DelayTarget = -1; 00526 pPars->fPreprocess = 0; 00527 pPars->fArea = 1; 00528 pPars->fFancy = 0; 00529 pPars->fExpRed = 0; 00530 pPars->fLatchPaths = 0; 00531 pPars->fSeqMap = 0; 00532 pPars->fVerbose = 0; 00533 // internal parameters 00534 pPars->fTruth = 0; 00535 pPars->fUsePerm = 0; 00536 pPars->nLatches = 0; 00537 pPars->pLutLib = NULL; // Abc_FrameReadLibLut(); 00538 pPars->pTimesArr = NULL; 00539 pPars->pTimesArr = NULL; 00540 pPars->fUseBdds = 0; 00541 pPars->fUseSops = 0; 00542 pPars->fUseCnfs = 0; 00543 pPars->fUseMv = 0; 00544 pPars->pFuncCost = NULL; 00545 pPars->pFuncUser = Abc_NtkRecAddCut; 00546 00547 // perform recording 00548 pNtkNew = Abc_NtkIf( pNtk, pPars ); 00549 Abc_NtkDelete( pNtkNew ); 00550 s_pMan->timeTotal += clock() - clk; 00551 00552 // if ( !Abc_NtkCheck( s_pMan->pNtk ) ) 00553 // printf( "Abc_NtkRecAdd: The network check has failed.\n" ); 00554 }
Function*************************************************************
Synopsis [Adds the cut function to the internal storage.]
Description []
SideEffects []
SeeAlso []
Definition at line 774 of file abcRec.c.
00775 { 00776 static int s_MaxSize[16] = { 0 }; 00777 char Buffer[40], Name[20], Truth[20]; 00778 char pCanonPerm[16]; 00779 Abc_Obj_t * pObj, * pFanin0, * pFanin1, ** ppSpot, * pObjPo; 00780 Abc_Ntk_t * pAig = s_pMan->pNtk; 00781 If_Obj_t * pIfObj; 00782 Vec_Ptr_t * vNodes = s_pMan->vNodes; 00783 unsigned * pInOut = s_pMan->pTemp1; 00784 unsigned * pTemp = s_pMan->pTemp2; 00785 unsigned * pTruth; 00786 int i, RetValue, nNodes, nNodesBeg, nInputs = s_pMan->nVars, nLeaves = If_CutLeaveNum(pCut); 00787 unsigned uCanonPhase; 00788 int clk; 00789 00790 if ( pRoot->Id == 2639 ) 00791 { 00792 int y = 0; 00793 } 00794 00795 assert( nInputs <= 16 ); 00796 assert( nInputs == (int)pCut->nLimit ); 00797 s_pMan->nTried++; 00798 00799 // skip small cuts 00800 if ( nLeaves < 3 ) 00801 { 00802 s_pMan->nFilterSize++; 00803 return 1; 00804 } 00805 00806 // collect internal nodes and skip redundant cuts 00807 clk = clock(); 00808 RetValue = Abc_NtkRecCollectNodes( pIfMan, pRoot, pCut, vNodes ); 00809 s_pMan->timeCollect += clock() - clk; 00810 if ( !RetValue ) 00811 { 00812 s_pMan->nFilterRedund++; 00813 return 1; 00814 } 00815 00816 // skip cuts with very large volume 00817 if ( Vec_PtrSize(vNodes) > nLeaves + 3*(nLeaves-1) + s_MaxSize[nLeaves] ) 00818 { 00819 s_pMan->nFilterVolume++; 00820 return 1; 00821 } 00822 00823 // compute truth table and skip the redundant structures 00824 clk = clock(); 00825 RetValue = Abc_NtkRecCutTruth( vNodes, nLeaves, s_pMan->vTtTemps, s_pMan->vTtElems ); 00826 s_pMan->timeTruth += clock() - clk; 00827 if ( !RetValue ) 00828 { 00829 s_pMan->nFilterTruth++; 00830 return 1; 00831 } 00832 00833 // copy the truth table 00834 Kit_TruthCopy( pInOut, (unsigned *)pRoot->pCopy, nInputs ); 00835 00836 // set permutation 00837 for ( i = 0; i < nInputs; i++ ) 00838 pCanonPerm[i] = i; 00839 00840 // semi-canonicize the truth table 00841 clk = clock(); 00842 uCanonPhase = Kit_TruthSemiCanonicize( pInOut, pTemp, nInputs, pCanonPerm, (short *)s_pMan->pMints ); 00843 s_pMan->timeCanon += clock() - clk; 00844 // pCanonPerm and uCanonPhase show what was the variable corresponding to each var in the current truth 00845 00846 // go through the variables in the new truth table 00847 for ( i = 0; i < nLeaves; i++ ) 00848 { 00849 // get hold of the corresponding leaf 00850 pIfObj = If_ManObj( pIfMan, pCut->pLeaves[pCanonPerm[i]] ); 00851 // get hold of the corresponding new node 00852 pObj = Abc_NtkPi( pAig, i ); 00853 pObj = Abc_ObjNotCond( pObj, (uCanonPhase & (1 << i)) ); 00854 // map them 00855 pIfObj->pCopy = pObj; 00856 /* 00857 if ( pRoot->Id == 2639 ) 00858 { 00859 unsigned uSupp; 00860 printf( "Node %6d : ", pIfObj->Id ); 00861 printf( "Support " ); 00862 uSupp = Kit_TruthSupport(Vec_PtrEntry( s_pMan->vTtNodes, Abc_ObjRegular(pObj)->Id ), nInputs); 00863 Extra_PrintBinary( stdout, &uSupp, nInputs ); 00864 printf( " " ); 00865 Extra_PrintBinary( stdout, Vec_PtrEntry( s_pMan->vTtNodes, Abc_ObjRegular(pObj)->Id ), 1<<6 ); 00866 printf( "\n" ); 00867 } 00868 */ 00869 } 00870 00871 // build the node and compute its truth table 00872 nNodesBeg = Abc_NtkObjNumMax( pAig ); 00873 Vec_PtrForEachEntryStart( vNodes, pIfObj, i, nLeaves ) 00874 { 00875 pFanin0 = Abc_ObjNotCond( If_ObjFanin0(pIfObj)->pCopy, If_ObjFaninC0(pIfObj) ); 00876 pFanin1 = Abc_ObjNotCond( If_ObjFanin1(pIfObj)->pCopy, If_ObjFaninC1(pIfObj) ); 00877 00878 nNodes = Abc_NtkObjNumMax( pAig ); 00879 pObj = Abc_AigAnd( pAig->pManFunc, pFanin0, pFanin1 ); 00880 assert( !Abc_ObjIsComplement(pObj) ); 00881 pIfObj->pCopy = pObj; 00882 00883 if ( pObj->Id == nNodes ) 00884 { 00885 // increase storage for truth tables 00886 if ( Vec_PtrSize(s_pMan->vTtNodes) <= pObj->Id ) 00887 Vec_PtrDoubleSimInfo(s_pMan->vTtNodes); 00888 // compute the truth table 00889 RetValue = Abc_NtkRecComputeTruth( pObj, s_pMan->vTtNodes, nInputs ); 00890 if ( RetValue == 0 ) 00891 { 00892 s_pMan->nFilterError++; 00893 printf( "T" ); 00894 return 1; 00895 } 00896 } 00897 } 00898 00899 pTruth = Vec_PtrEntry( s_pMan->vTtNodes, pObj->Id ); 00900 if ( Kit_TruthSupport(pTruth, nInputs) != Kit_BitMask(nLeaves) ) 00901 { 00902 s_pMan->nFilterError++; 00903 printf( "S" ); 00904 return 1; 00905 } 00906 00907 // compare the truth tables 00908 if ( !Kit_TruthIsEqualWithPhase( pTruth, pInOut, nInputs ) ) 00909 { 00910 s_pMan->nFilterError++; 00911 printf( "F" ); 00912 return 1; 00913 } 00914 // Extra_PrintBinary( stdout, pInOut, 8 ); printf( "\n" ); 00915 00916 // if not new nodes were added and the node has a CO fanout 00917 if ( nNodesBeg == Abc_NtkObjNumMax(pAig) && Abc_NodeFindCoFanout(pObj) != NULL ) 00918 { 00919 s_pMan->nFilterSame++; 00920 return 1; 00921 } 00922 s_pMan->nAdded++; 00923 00924 // create PO for this node 00925 pObjPo = Abc_NtkCreatePo(pAig); 00926 Abc_ObjAddFanin( pObjPo, pObj ); 00927 00928 // assign the name to this PO 00929 sprintf( Name, "%d_%06d", nLeaves, Abc_NtkPoNum(pAig) ); 00930 if ( (nInputs <= 6) && 0 ) 00931 { 00932 Extra_PrintHexadecimalString( Truth, pInOut, nInputs ); 00933 sprintf( Buffer, "%s_%s", Name, Truth ); 00934 } 00935 else 00936 { 00937 sprintf( Buffer, "%s", Name ); 00938 } 00939 Abc_ObjAssignName( pObjPo, Buffer, NULL ); 00940 00941 // add the resulting truth table to the hash table 00942 ppSpot = Abc_NtkRecTableLookup( s_pMan, pTruth, nInputs ); 00943 assert( pObj->pEquiv == NULL ); 00944 assert( pObj->pCopy == NULL ); 00945 if ( *ppSpot == NULL ) 00946 { 00947 s_pMan->nAddedFuncs++; 00948 *ppSpot = pObj; 00949 } 00950 else 00951 { 00952 pObj->pEquiv = (*ppSpot)->pEquiv; 00953 (*ppSpot)->pEquiv = (Hop_Obj_t *)pObj; 00954 if ( !Abc_NtkRecAddCutCheckCycle_rec(*ppSpot, pObj) ) 00955 printf( "Loop!\n" ); 00956 } 00957 return 1; 00958 }
Function*************************************************************
Synopsis [Adds the cut function to the internal storage.]
Description []
SideEffects []
SeeAlso []
Definition at line 749 of file abcRec.c.
00750 { 00751 assert( pRoot->Level > 0 ); 00752 if ( pObj->Level < pRoot->Level ) 00753 return 1; 00754 if ( pObj == pRoot ) 00755 return 0; 00756 if ( !Abc_NtkRecAddCutCheckCycle_rec(pRoot, Abc_ObjFanin0(pObj)) ) 00757 return 0; 00758 if ( !Abc_NtkRecAddCutCheckCycle_rec(pRoot, Abc_ObjFanin1(pObj)) ) 00759 return 0; 00760 return 1; 00761 }
int Abc_NtkRecCollectNodes | ( | If_Man_t * | pIfMan, | |
If_Obj_t * | pRoot, | |||
If_Cut_t * | pCut, | |||
Vec_Ptr_t * | vNodes | |||
) |
Function*************************************************************
Synopsis [Adds the cut function to the internal storage.]
Description []
SideEffects []
SeeAlso []
Definition at line 589 of file abcRec.c.
00590 { 00591 If_Obj_t * pLeaf; 00592 int i, RetValue = 1; 00593 00594 // collect the internal nodes of the cut 00595 Vec_PtrClear( vNodes ); 00596 If_CutForEachLeaf( pIfMan, pCut, pLeaf, i ) 00597 { 00598 Vec_PtrPush( vNodes, pLeaf ); 00599 assert( pLeaf->fMark == 0 ); 00600 pLeaf->fMark = 1; 00601 } 00602 00603 // collect other nodes 00604 Abc_NtkRecCollectNodes_rec( pRoot, vNodes ); 00605 00606 // check if there are leaves, such that both of their fanins are marked 00607 // this indicates a redundant cut 00608 If_CutForEachLeaf( pIfMan, pCut, pLeaf, i ) 00609 { 00610 if ( !If_ObjIsAnd(pLeaf) ) 00611 continue; 00612 if ( If_ObjFanin0(pLeaf)->fMark && If_ObjFanin1(pLeaf)->fMark ) 00613 { 00614 RetValue = 0; 00615 break; 00616 } 00617 } 00618 00619 // clean the mark 00620 Vec_PtrForEachEntry( vNodes, pLeaf, i ) 00621 pLeaf->fMark = 0; 00622 /* 00623 if ( pRoot->Id == 2639 ) 00624 { 00625 // print the cut 00626 Vec_PtrForEachEntry( vNodes, pLeaf, i ) 00627 { 00628 if ( If_ObjIsAnd(pLeaf) ) 00629 printf( "%4d = %c%4d & %c%4d\n", pLeaf->Id, 00630 (If_ObjFaninC0(pLeaf)? '-':'+'), If_ObjFanin0(pLeaf)->Id, 00631 (If_ObjFaninC1(pLeaf)? '-':'+'), If_ObjFanin1(pLeaf)->Id ); 00632 else 00633 printf( "%4d = pi\n", pLeaf->Id ); 00634 } 00635 printf( "\n" ); 00636 } 00637 */ 00638 return RetValue; 00639 }
Function*************************************************************
Synopsis [Adds the cut function to the internal storage.]
Description []
SideEffects []
SeeAlso []
Definition at line 567 of file abcRec.c.
00568 { 00569 if ( pNode->fMark ) 00570 return; 00571 pNode->fMark = 1; 00572 assert( If_ObjIsAnd(pNode) ); 00573 Abc_NtkRecCollectNodes_rec( If_ObjFanin0(pNode), vNodes ); 00574 Abc_NtkRecCollectNodes_rec( If_ObjFanin1(pNode), vNodes ); 00575 Vec_PtrPush( vNodes, pNode ); 00576 }
Function*************************************************************
Synopsis [Computes the truth table of the node.]
Description []
SideEffects []
SeeAlso []
Definition at line 481 of file abcRec.c.
00482 { 00483 unsigned * pTruth, * pTruth0, * pTruth1; 00484 int RetValue; 00485 assert( Abc_ObjIsNode(pObj) ); 00486 pTruth = Vec_PtrEntry( vTtNodes, pObj->Id ); 00487 pTruth0 = Vec_PtrEntry( vTtNodes, Abc_ObjFaninId0(pObj) ); 00488 pTruth1 = Vec_PtrEntry( vTtNodes, Abc_ObjFaninId1(pObj) ); 00489 Kit_TruthAndPhase( pTruth, pTruth0, pTruth1, nVars, Abc_ObjFaninC0(pObj), Abc_ObjFaninC1(pObj) ); 00490 assert( (pTruth[0] & 1) == pObj->fPhase ); 00491 RetValue = ((pTruth[0] & 1) == pObj->fPhase); 00492 return RetValue; 00493 }
int Abc_NtkRecCutTruth | ( | Vec_Ptr_t * | vNodes, | |
int | nLeaves, | |||
Vec_Ptr_t * | vTtTemps, | |||
Vec_Ptr_t * | vTtElems | |||
) |
Function*************************************************************
Synopsis [Computes truth tables of nodes in the cut.]
Description [Returns 0 if the TT does not depend on some cut variables. Or if the TT can be expressed simpler using other nodes.]
SideEffects []
SeeAlso []
Definition at line 653 of file abcRec.c.
00654 { 00655 unsigned * pSims, * pSims0, * pSims1; 00656 unsigned * pTemp = s_pMan->pTemp2; 00657 unsigned uWord; 00658 If_Obj_t * pObj, * pObj2, * pRoot; 00659 int i, k, nLimit, nInputs = s_pMan->nVars; 00660 00661 assert( Vec_PtrSize(vNodes) > nLeaves ); 00662 00663 // set the elementary truth tables and compute the truth tables of the nodes 00664 Vec_PtrForEachEntry( vNodes, pObj, i ) 00665 { 00666 pObj->pCopy = Vec_PtrEntry(vTtTemps, i); 00667 pSims = (unsigned *)pObj->pCopy; 00668 if ( i < nLeaves ) 00669 { 00670 Kit_TruthCopy( pSims, Vec_PtrEntry(vTtElems, i), nInputs ); 00671 continue; 00672 } 00673 assert( If_ObjIsAnd(pObj) ); 00674 // get hold of the simulation information 00675 pSims0 = (unsigned *)If_ObjFanin0(pObj)->pCopy; 00676 pSims1 = (unsigned *)If_ObjFanin1(pObj)->pCopy; 00677 // simulate the node 00678 Kit_TruthAndPhase( pSims, pSims0, pSims1, nInputs, If_ObjFaninC0(pObj), If_ObjFaninC1(pObj) ); 00679 } 00680 00681 // check the support size 00682 pRoot = Vec_PtrEntryLast( vNodes ); 00683 pSims = (unsigned *)pRoot->pCopy; 00684 if ( Kit_TruthSupport(pSims, nInputs) != Kit_BitMask(nLeaves) ) 00685 return 0; 00686 00687 // make sure none of the nodes has the same simulation info as the output 00688 // check pairwise comparisons 00689 nLimit = Vec_PtrSize(vNodes) - 1; 00690 Vec_PtrForEachEntryStop( vNodes, pObj, i, nLimit ) 00691 { 00692 pSims0 = (unsigned *)pObj->pCopy; 00693 if ( Kit_TruthIsEqualWithPhase(pSims, pSims0, nInputs) ) 00694 return 0; 00695 Vec_PtrForEachEntryStop( vNodes, pObj2, k, i ) 00696 { 00697 if ( (If_ObjFanin0(pRoot) == pObj && If_ObjFanin1(pRoot) == pObj2) || 00698 (If_ObjFanin1(pRoot) == pObj && If_ObjFanin0(pRoot) == pObj2) ) 00699 continue; 00700 pSims1 = (unsigned *)pObj2->pCopy; 00701 00702 uWord = pSims0[0] & pSims1[0]; 00703 if ( pSims[0] == uWord || pSims[0] == ~uWord ) 00704 { 00705 Kit_TruthAndPhase( pTemp, pSims0, pSims1, nInputs, 0, 0 ); 00706 if ( Kit_TruthIsEqualWithPhase(pSims, pTemp, nInputs) ) 00707 return 0; 00708 } 00709 00710 uWord = pSims0[0] & ~pSims1[0]; 00711 if ( pSims[0] == uWord || pSims[0] == ~uWord ) 00712 { 00713 Kit_TruthAndPhase( pTemp, pSims0, pSims1, nInputs, 0, 1 ); 00714 if ( Kit_TruthIsEqualWithPhase(pSims, pTemp, nInputs) ) 00715 return 0; 00716 } 00717 00718 uWord = ~pSims0[0] & pSims1[0]; 00719 if ( pSims[0] == uWord || pSims[0] == ~uWord ) 00720 { 00721 Kit_TruthAndPhase( pTemp, pSims0, pSims1, nInputs, 1, 0 ); 00722 if ( Kit_TruthIsEqualWithPhase(pSims, pTemp, nInputs) ) 00723 return 0; 00724 } 00725 00726 uWord = ~pSims0[0] & ~pSims1[0]; 00727 if ( pSims[0] == uWord || pSims[0] == ~uWord ) 00728 { 00729 Kit_TruthAndPhase( pTemp, pSims0, pSims1, nInputs, 1, 1 ); 00730 if ( Kit_TruthIsEqualWithPhase(pSims, pTemp, nInputs) ) 00731 return 0; 00732 } 00733 } 00734 } 00735 return 1; 00736 }
void Abc_NtkRecFilter | ( | int | iVar, | |
int | iPlus | |||
) |
int Abc_NtkRecIsRunning | ( | ) |
Vec_Int_t* Abc_NtkRecMemory | ( | ) |
void Abc_NtkRecPs | ( | ) |
Function*************************************************************
Synopsis [Print statistics about the current record.]
Description []
SideEffects []
SeeAlso []
Definition at line 346 of file abcRec.c.
00347 { 00348 int Counter, Counters[17] = {0}; 00349 int CounterS, CountersS[17] = {0}; 00350 Abc_ManRec_t * p = s_pMan; 00351 Abc_Ntk_t * pNtk = p->pNtk; 00352 Abc_Obj_t * pObj, * pEntry, * pTemp; 00353 int i; 00354 00355 // set the max PI number 00356 Abc_NtkForEachPi( pNtk, pObj, i ) 00357 Abc_ObjSetMax( pObj, i+1 ); 00358 Abc_AigForEachAnd( pNtk, pObj, i ) 00359 Abc_ObjSetMax( pObj, ABC_MAX( Abc_ObjGetMax(Abc_ObjFanin0(pObj)), Abc_ObjGetMax(Abc_ObjFanin1(pObj)) ) ); 00360 // go through the table 00361 Counter = CounterS = 0; 00362 for ( i = 0; i < p->nBins; i++ ) 00363 for ( pEntry = p->pBins[i]; pEntry; pEntry = pEntry->pCopy ) 00364 { 00365 Counters[ Abc_ObjGetMax(pEntry) ]++; 00366 Counter++; 00367 for ( pTemp = pEntry; pTemp; pTemp = (Abc_Obj_t *)pTemp->pEquiv ) 00368 { 00369 assert( Abc_ObjGetMax(pTemp) == Abc_ObjGetMax(pEntry) ); 00370 CountersS[ Abc_ObjGetMax(pTemp) ]++; 00371 CounterS++; 00372 } 00373 } 00374 // printf( "Functions = %d. Expected = %d.\n", Counter, p->nAddedFuncs ); 00375 // printf( "Subgraphs = %d. Expected = %d.\n", CounterS, p->nAdded ); 00376 assert( Counter == p->nAddedFuncs ); 00377 assert( CounterS == p->nAdded ); 00378 00379 // clean 00380 Abc_NtkForEachObj( pNtk, pObj, i ) 00381 { 00382 Abc_ObjClearMax( pObj ); 00383 } 00384 00385 printf( "The record with %d AND nodes in %d subgraphs for %d functions with %d inputs:\n", 00386 Abc_NtkNodeNum(pNtk), Abc_NtkPoNum(pNtk), p->nAddedFuncs, Abc_NtkPiNum(pNtk) ); 00387 for ( i = 0; i <= 16; i++ ) 00388 { 00389 if ( Counters[i] ) 00390 printf( "Inputs = %2d. Funcs = %8d. Subgrs = %8d. Ratio = %6.2f.\n", i, Counters[i], CountersS[i], 1.0*CountersS[i]/Counters[i] ); 00391 } 00392 00393 printf( "Subgraphs tried = %8d. (%6.2f %%)\n", p->nTried, !p->nTried? 0 : 100.0*p->nTried/p->nTried ); 00394 printf( "Subgraphs filtered by support size = %8d. (%6.2f %%)\n", p->nFilterSize, !p->nTried? 0 : 100.0*p->nFilterSize/p->nTried ); 00395 printf( "Subgraphs filtered by structural redundancy = %8d. (%6.2f %%)\n", p->nFilterRedund, !p->nTried? 0 : 100.0*p->nFilterRedund/p->nTried ); 00396 printf( "Subgraphs filtered by volume = %8d. (%6.2f %%)\n", p->nFilterVolume, !p->nTried? 0 : 100.0*p->nFilterVolume/p->nTried ); 00397 printf( "Subgraphs filtered by TT redundancy = %8d. (%6.2f %%)\n", p->nFilterTruth, !p->nTried? 0 : 100.0*p->nFilterTruth/p->nTried ); 00398 printf( "Subgraphs filtered by error = %8d. (%6.2f %%)\n", p->nFilterError, !p->nTried? 0 : 100.0*p->nFilterError/p->nTried ); 00399 printf( "Subgraphs filtered by isomorphism = %8d. (%6.2f %%)\n", p->nFilterSame, !p->nTried? 0 : 100.0*p->nFilterSame/p->nTried ); 00400 printf( "Subgraphs added = %8d. (%6.2f %%)\n", p->nAdded, !p->nTried? 0 : 100.0*p->nAdded/p->nTried ); 00401 printf( "Functions added = %8d. (%6.2f %%)\n", p->nAddedFuncs, !p->nTried? 0 : 100.0*p->nAddedFuncs/p->nTried ); 00402 00403 p->timeOther = p->timeTotal - p->timeCollect - p->timeTruth - p->timeCanon; 00404 PRTP( "Collecting nodes ", p->timeCollect, p->timeTotal ); 00405 PRTP( "Computing truth ", p->timeTruth, p->timeTotal ); 00406 PRTP( "Canonicizing ", p->timeCanon, p->timeTotal ); 00407 PRTP( "Other ", p->timeOther, p->timeTotal ); 00408 PRTP( "TOTAL ", p->timeTotal, p->timeTotal ); 00409 if ( p->nFunsFound ) 00410 printf( "During rewriting found = %d and not found = %d functions.\n", p->nFunsFound, p->nFunsNotFound ); 00411 }
void Abc_NtkRecStart | ( | Abc_Ntk_t * | pNtk, | |
int | nVars, | |||
int | nCuts | |||
) |
Function*************************************************************
Synopsis [Starts the record for the given network.]
Description []
SideEffects []
SeeAlso []
Definition at line 143 of file abcRec.c.
00144 { 00145 Abc_ManRec_t * p; 00146 Abc_Obj_t * pObj, ** ppSpot; 00147 char Buffer[10]; 00148 unsigned * pTruth; 00149 int i, RetValue; 00150 int clkTotal = clock(), clk; 00151 00152 assert( s_pMan == NULL ); 00153 if ( pNtk == NULL ) 00154 { 00155 assert( nVars > 2 && nVars <= 16 ); 00156 pNtk = Abc_NtkAlloc( ABC_NTK_STRASH, ABC_FUNC_AIG, 1 ); 00157 pNtk->pName = Extra_UtilStrsav( "record" ); 00158 } 00159 else 00160 { 00161 if ( Abc_NtkGetChoiceNum(pNtk) > 0 ) 00162 { 00163 printf( "The starting record should be a network without choice nodes.\n" ); 00164 return; 00165 } 00166 if ( Abc_NtkPiNum(pNtk) > 16 ) 00167 { 00168 printf( "The starting record should be a network with no more than %d primary inputs.\n", 16 ); 00169 return; 00170 } 00171 if ( Abc_NtkPiNum(pNtk) > nVars ) 00172 printf( "The starting record has %d inputs (warning only).\n", Abc_NtkPiNum(pNtk) ); 00173 pNtk = Abc_NtkDup( pNtk ); 00174 } 00175 // create the primary inputs 00176 for ( i = Abc_NtkPiNum(pNtk); i < nVars; i++ ) 00177 { 00178 pObj = Abc_NtkCreatePi( pNtk ); 00179 Buffer[0] = 'a' + i; 00180 Buffer[1] = 0; 00181 Abc_ObjAssignName( pObj, Buffer, NULL ); 00182 } 00183 Abc_NtkCleanCopy( pNtk ); 00184 Abc_NtkCleanEquiv( pNtk ); 00185 00186 // start the manager 00187 p = ALLOC( Abc_ManRec_t, 1 ); 00188 memset( p, 0, sizeof(Abc_ManRec_t) ); 00189 p->pNtk = pNtk; 00190 p->nVars = Abc_NtkPiNum(pNtk); 00191 p->nWords = Kit_TruthWordNum( p->nVars ); 00192 p->nCuts = nCuts; 00193 p->nVarsInit = nVars; 00194 00195 // create elementary truth tables 00196 p->vTtElems = Vec_PtrAlloc( 0 ); assert( p->vTtElems->pArray == NULL ); 00197 p->vTtElems->nSize = p->nVars; 00198 p->vTtElems->nCap = p->nVars; 00199 p->vTtElems->pArray = (void *)Extra_TruthElementary( p->nVars ); 00200 00201 // allocate room for node truth tables 00202 if ( Abc_NtkObjNum(pNtk) > (1<<14) ) 00203 p->vTtNodes = Vec_PtrAllocSimInfo( 2 * Abc_NtkObjNum(pNtk), p->nWords ); 00204 else 00205 p->vTtNodes = Vec_PtrAllocSimInfo( 1<<14, p->nWords ); 00206 00207 // create hash table 00208 p->nBins = 50011; 00209 p->pBins = ALLOC( Abc_Obj_t *, p->nBins ); 00210 memset( p->pBins, 0, sizeof(Abc_Obj_t *) * p->nBins ); 00211 00212 // set elementary tables 00213 Kit_TruthFill( Vec_PtrEntry(p->vTtNodes, 0), p->nVars ); 00214 Abc_NtkForEachPi( pNtk, pObj, i ) 00215 Kit_TruthCopy( Vec_PtrEntry(p->vTtNodes, pObj->Id), Vec_PtrEntry(p->vTtElems, i), p->nVars ); 00216 00217 // compute the tables 00218 clk = clock(); 00219 Abc_AigForEachAnd( pNtk, pObj, i ) 00220 { 00221 RetValue = Abc_NtkRecComputeTruth( pObj, p->vTtNodes, p->nVars ); 00222 assert( RetValue ); 00223 } 00224 p->timeTruth += clock() - clk; 00225 00226 // insert the PO nodes into the table 00227 Abc_NtkForEachPo( pNtk, pObj, i ) 00228 { 00229 p->nTried++; 00230 p->nAdded++; 00231 00232 pObj = Abc_ObjFanin0(pObj); 00233 pTruth = Vec_PtrEntry( p->vTtNodes, pObj->Id ); 00234 00235 if ( pTruth[0] == 1128481603 ) 00236 { 00237 int x = 0; 00238 } 00239 00240 // add the resulting truth table to the hash table 00241 ppSpot = Abc_NtkRecTableLookup( p, pTruth, p->nVars ); 00242 assert( pObj->pEquiv == NULL ); 00243 assert( pObj->pCopy == NULL ); 00244 if ( *ppSpot == NULL ) 00245 { 00246 p->nAddedFuncs++; 00247 *ppSpot = pObj; 00248 } 00249 else 00250 { 00251 pObj->pEquiv = (*ppSpot)->pEquiv; 00252 (*ppSpot)->pEquiv = (Hop_Obj_t *)pObj; 00253 if ( !Abc_NtkRecAddCutCheckCycle_rec(*ppSpot, pObj) ) 00254 printf( "Loop!\n" ); 00255 } 00256 } 00257 00258 // temporaries 00259 p->pBytes = ALLOC( int, 4*p->nWords ); 00260 p->pMints = ALLOC( int, 2*p->nVars ); 00261 p->pTemp1 = ALLOC( unsigned, p->nWords ); 00262 p->pTemp2 = ALLOC( unsigned, p->nWords ); 00263 p->vNodes = Vec_PtrAlloc( 100 ); 00264 p->vTtTemps = Vec_PtrAllocSimInfo( 64, p->nWords ); 00265 p->vMemory = Vec_IntAlloc( Abc_TruthWordNum(p->nVars) * 1000 ); 00266 00267 // set the manager 00268 s_pMan = p; 00269 p->timeTotal += clock() - clkTotal; 00270 }
void Abc_NtkRecStop | ( | ) |
Function*************************************************************
Synopsis [Returns the given record.]
Description []
SideEffects []
SeeAlso []
Definition at line 283 of file abcRec.c.
00284 { 00285 assert( s_pMan != NULL ); 00286 if ( s_pMan->pNtk ) 00287 Abc_NtkDelete( s_pMan->pNtk ); 00288 Vec_PtrFree( s_pMan->vTtNodes ); 00289 Vec_PtrFree( s_pMan->vTtElems ); 00290 free( s_pMan->pBins ); 00291 00292 // temporaries 00293 free( s_pMan->pBytes ); 00294 free( s_pMan->pMints ); 00295 free( s_pMan->pTemp1 ); 00296 free( s_pMan->pTemp2 ); 00297 Vec_PtrFree( s_pMan->vNodes ); 00298 Vec_PtrFree( s_pMan->vTtTemps ); 00299 if ( s_pMan->vLabels ) 00300 Vec_PtrFree( s_pMan->vLabels ); 00301 if ( s_pMan->vCosts ) 00302 Vec_StrFree( s_pMan->vCosts ); 00303 Vec_IntFree( s_pMan->vMemory ); 00304 00305 free( s_pMan ); 00306 s_pMan = NULL; 00307 }
Function*************************************************************
Synopsis [Strashes the given node using its local function.]
Description [Assumes that the fanins are already strashed. Returns 0 if the function is not found in the table.]
SideEffects []
SeeAlso []
Definition at line 1041 of file abcRec.c.
01042 { 01043 char pCanonPerm[16]; 01044 Abc_Ntk_t * pAig = s_pMan->pNtk; 01045 unsigned * pInOut = s_pMan->pTemp1; 01046 unsigned * pTemp = s_pMan->pTemp2; 01047 unsigned * pTruthRec; 01048 Abc_Obj_t * pCand, * pCandMin, * pLeaf, * pFanin, ** ppSpot; 01049 unsigned uCanonPhase; 01050 int i, nLeaves, CostMin, Cost, nOnes, fCompl; 01051 01052 // check if the record works 01053 nLeaves = Abc_ObjFaninNum(pObj); 01054 assert( nLeaves >= 3 && nLeaves <= s_pMan->nVars ); 01055 pFanin = Abc_ObjFanin0(pObj); 01056 assert( Abc_ObjRegular(pFanin->pCopy)->pNtk == pNtkNew ); 01057 assert( s_pMan != NULL ); 01058 assert( nVars == s_pMan->nVars ); 01059 01060 // copy the truth table 01061 Kit_TruthCopy( pInOut, pTruth, nVars ); 01062 01063 // set permutation 01064 for ( i = 0; i < nVars; i++ ) 01065 pCanonPerm[i] = i; 01066 01067 // canonicize the truth table 01068 uCanonPhase = Kit_TruthSemiCanonicize( pInOut, pTemp, nVars, pCanonPerm, (short *)s_pMan->pMints ); 01069 01070 // get hold of the curresponding class 01071 ppSpot = Abc_NtkRecTableLookup( s_pMan, pInOut, nVars ); 01072 if ( *ppSpot == NULL ) 01073 { 01074 s_pMan->nFunsNotFound++; 01075 // printf( "The class of a function with %d inputs is not found.\n", nLeaves ); 01076 return 0; 01077 } 01078 s_pMan->nFunsFound++; 01079 01080 // make sure the truth table is the same 01081 pTruthRec = Vec_PtrEntry( s_pMan->vTtNodes, (*ppSpot)->Id ); 01082 if ( !Kit_TruthIsEqualWithPhase( pTruthRec, pInOut, nVars ) ) 01083 { 01084 assert( 0 ); 01085 return 0; 01086 } 01087 01088 01089 // allocate storage for costs 01090 if ( s_pMan->vLabels && Vec_PtrSize(s_pMan->vLabels) < Abc_NtkObjNumMax(pAig) ) 01091 { 01092 Vec_PtrFree( s_pMan->vLabels ); 01093 s_pMan->vLabels = NULL; 01094 } 01095 if ( s_pMan->vLabels == NULL ) 01096 s_pMan->vLabels = Vec_PtrStart( Abc_NtkObjNumMax(pAig) ); 01097 01098 // go through the variables in the new truth table 01099 Abc_NtkIncrementTravId( pAig ); 01100 for ( i = 0; i < nLeaves; i++ ) 01101 { 01102 // get hold of the corresponding fanin 01103 pFanin = Abc_ObjFanin( pObj, pCanonPerm[i] )->pCopy; 01104 pFanin = Abc_ObjNotCond( pFanin, (uCanonPhase & (1 << i)) ); 01105 // label the PI of the AIG subgraphs with this fanin 01106 pLeaf = Abc_NtkPi( pAig, i ); 01107 Vec_PtrWriteEntry( s_pMan->vLabels, pLeaf->Id, pFanin ); 01108 Abc_NodeSetTravIdCurrent( pLeaf ); 01109 } 01110 01111 // go through the candidates - and recursively label them 01112 for ( pCand = *ppSpot; pCand; pCand = (Abc_Obj_t *)pCand->pEquiv ) 01113 Abc_NtkRecStrashNodeLabel_rec( pNtkNew, pCand, 0, s_pMan->vLabels ); 01114 01115 01116 // allocate storage for costs 01117 if ( s_pMan->vCosts && Vec_StrSize(s_pMan->vCosts) < Abc_NtkObjNumMax(pAig) ) 01118 { 01119 Vec_StrFree( s_pMan->vCosts ); 01120 s_pMan->vCosts = NULL; 01121 } 01122 if ( s_pMan->vCosts == NULL ) 01123 s_pMan->vCosts = Vec_StrStart( Abc_NtkObjNumMax(pAig) ); 01124 01125 // find the best subgraph 01126 CostMin = ABC_INFINITY; 01127 pCandMin = NULL; 01128 for ( pCand = *ppSpot; pCand; pCand = (Abc_Obj_t *)pCand->pEquiv ) 01129 { 01130 // label the leaves 01131 Abc_NtkIncrementTravId( pAig ); 01132 // count the number of non-labeled nodes 01133 Cost = Abc_NtkRecStrashNodeCount_rec( pCand, s_pMan->vCosts, s_pMan->vLabels ); 01134 if ( CostMin > Cost ) 01135 { 01136 // printf( "%d ", Cost ); 01137 CostMin = Cost; 01138 pCandMin = pCand; 01139 } 01140 } 01141 // printf( "\n" ); 01142 assert( pCandMin != NULL ); 01143 if ( pCandMin == NULL ) 01144 return 0; 01145 01146 01147 // label the leaves 01148 Abc_NtkIncrementTravId( pAig ); 01149 for ( i = 0; i < nLeaves; i++ ) 01150 Abc_NodeSetTravIdCurrent( Abc_NtkPi(pAig, i) ); 01151 01152 // implement the subgraph 01153 pObj->pCopy = Abc_NtkRecStrashNodeLabel_rec( pNtkNew, pCandMin, 1, s_pMan->vLabels ); 01154 assert( Abc_ObjRegular(pObj->pCopy)->pNtk == pNtkNew ); 01155 01156 // determine phase difference 01157 nOnes = Kit_TruthCountOnes(pTruth, nVars); 01158 fCompl = (nOnes > (1<< nVars)/2); 01159 // assert( fCompl == ((uCanonPhase & (1 << nVars)) > 0) ); 01160 01161 nOnes = Kit_TruthCountOnes(pTruthRec, nVars); 01162 fCompl ^= (nOnes > (1<< nVars)/2); 01163 // complement 01164 pObj->pCopy = Abc_ObjNotCond( pObj->pCopy, fCompl ); 01165 return 1; 01166 }
Function*************************************************************
Synopsis [Counts the area of the given node.]
Description []
SideEffects []
SeeAlso []
Definition at line 1011 of file abcRec.c.
01012 { 01013 int Cost0, Cost1; 01014 if ( Vec_PtrEntry( vLabels, pObj->Id ) ) 01015 return 0; 01016 assert( Abc_ObjIsNode(pObj) ); 01017 // if this node is already visited, skip 01018 if ( Abc_NodeIsTravIdCurrent( pObj ) ) 01019 return Vec_StrEntry( vCosts, pObj->Id ); 01020 // mark the node as visited 01021 Abc_NodeSetTravIdCurrent( pObj ); 01022 // count for the fanins 01023 Cost0 = Abc_NtkRecStrashNodeCount_rec( Abc_ObjFanin0(pObj), vCosts, vLabels ); 01024 Cost1 = Abc_NtkRecStrashNodeCount_rec( Abc_ObjFanin1(pObj), vCosts, vLabels ); 01025 Vec_StrWriteEntry( vCosts, pObj->Id, (char)(Cost0 + Cost1 + 1) ); 01026 return Cost0 + Cost1 + 1; 01027 }
Abc_Obj_t* Abc_NtkRecStrashNodeLabel_rec | ( | Abc_Ntk_t * | pNtkNew, | |
Abc_Obj_t * | pObj, | |||
int | fBuild, | |||
Vec_Ptr_t * | vLabels | |||
) |
Function*************************************************************
Synopsis [Labels the record AIG with the corresponding new AIG nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 972 of file abcRec.c.
00973 { 00974 Abc_Obj_t * pFanin0New, * pFanin1New, * pLabel; 00975 assert( !Abc_ObjIsComplement(pObj) ); 00976 // if this node is already visited, skip 00977 if ( Abc_NodeIsTravIdCurrent( pObj ) ) 00978 return Vec_PtrEntry( vLabels, pObj->Id ); 00979 assert( Abc_ObjIsNode(pObj) ); 00980 // mark the node as visited 00981 Abc_NodeSetTravIdCurrent( pObj ); 00982 // label the fanins 00983 pFanin0New = Abc_NtkRecStrashNodeLabel_rec( pNtkNew, Abc_ObjFanin0(pObj), fBuild, vLabels ); 00984 pFanin1New = Abc_NtkRecStrashNodeLabel_rec( pNtkNew, Abc_ObjFanin1(pObj), fBuild, vLabels ); 00985 // label the node if possible 00986 pLabel = NULL; 00987 if ( pFanin0New && pFanin1New ) 00988 { 00989 pFanin0New = Abc_ObjNotCond( pFanin0New, Abc_ObjFaninC0(pObj) ); 00990 pFanin1New = Abc_ObjNotCond( pFanin1New, Abc_ObjFaninC1(pObj) ); 00991 if ( fBuild ) 00992 pLabel = Abc_AigAnd( pNtkNew->pManFunc, pFanin0New, pFanin1New ); 00993 else 00994 pLabel = Abc_AigAndLookup( pNtkNew->pManFunc, pFanin0New, pFanin1New ); 00995 } 00996 Vec_PtrWriteEntry( vLabels, pObj->Id, pLabel ); 00997 return pLabel; 00998 }
static unsigned Abc_NtkRecTableHash | ( | unsigned * | pTruth, | |
int | nVars, | |||
int | nBins, | |||
int * | pPrimes | |||
) | [inline, static] |
Function*************************************************************
Synopsis [Returns the hash key.]
Description []
SideEffects []
SeeAlso []
Definition at line 439 of file abcRec.c.
00440 { 00441 int i, nWords = Kit_TruthWordNum( nVars ); 00442 unsigned uHash = 0; 00443 for ( i = 0; i < nWords; i++ ) 00444 uHash ^= pTruth[i] * pPrimes[i & 0x7]; 00445 return uHash % nBins; 00446 }
Abc_Obj_t ** Abc_NtkRecTableLookup | ( | Abc_ManRec_t * | p, | |
unsigned * | pTruth, | |||
int | nVars | |||
) | [static] |
Function*************************************************************
Synopsis [Returns the given record.]
Description []
SideEffects []
SeeAlso []
Definition at line 459 of file abcRec.c.
00460 { 00461 static int s_Primes[10] = { 1291, 1699, 2357, 4177, 5147, 5647, 6343, 7103, 7873, 8147 }; 00462 Abc_Obj_t ** ppSpot, * pEntry; 00463 ppSpot = p->pBins + Abc_NtkRecTableHash( pTruth, nVars, p->nBins, s_Primes ); 00464 for ( pEntry = *ppSpot; pEntry; ppSpot = &pEntry->pCopy, pEntry = pEntry->pCopy ) 00465 if ( Kit_TruthIsEqualWithPhase(Vec_PtrEntry(p->vTtNodes, pEntry->Id), pTruth, nVars) ) 00466 return ppSpot; 00467 return ppSpot; 00468 }
Abc_Ntk_t* Abc_NtkRecUse | ( | ) |
Function*************************************************************
Synopsis [Returns the given record.]
Description []
SideEffects []
SeeAlso []
Definition at line 320 of file abcRec.c.
00321 { 00322 Abc_ManRec_t * p = s_pMan; 00323 Abc_Ntk_t * pNtk = p->pNtk; 00324 assert( p != NULL ); 00325 Abc_NtkRecPs(); 00326 p->pNtk = NULL; 00327 Abc_NtkRecStop(); 00328 return pNtk; 00329 }
int Abc_NtkRecVarNum | ( | ) |
static void Abc_ObjClearMax | ( | Abc_Obj_t * | pObj | ) | [inline, static] |
static int Abc_ObjGetMax | ( | Abc_Obj_t * | pObj | ) | [inline, static] |
static void Abc_ObjSetMax | ( | Abc_Obj_t * | pObj, | |
int | Value | |||
) | [inline, static] |
Abc_ManRec_t* s_pMan = NULL [static] |