src/opt/sim/simSymStr.c File Reference

#include "abc.h"
#include "sim.h"
Include dependency graph for simSymStr.c:

Go to the source code of this file.

Defines

#define SIM_READ_SYMMS(pNode)   ((Vec_Int_t *)pNode->pCopy)
#define SIM_SET_SYMMS(pNode, vVect)   (pNode->pCopy = (Abc_Obj_t *)(vVect))

Functions

static void Sim_SymmsStructComputeOne (Abc_Ntk_t *pNtk, Abc_Obj_t *pNode, int *pMap)
static void Sim_SymmsBalanceCollect_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
static void Sim_SymmsPartitionNodes (Vec_Ptr_t *vNodes, Vec_Ptr_t *vNodesPis0, Vec_Ptr_t *vNodesPis1, Vec_Ptr_t *vNodesOther)
static void Sim_SymmsAppendFromGroup (Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodesPi, Vec_Ptr_t *vNodesOther, Vec_Int_t *vSymms, int *pMap)
static void Sim_SymmsAppendFromNode (Abc_Ntk_t *pNtk, Vec_Int_t *vSymms0, Vec_Ptr_t *vNodesOther, Vec_Ptr_t *vNodesPi0, Vec_Ptr_t *vNodesPi1, Vec_Int_t *vSymms, int *pMap)
static int Sim_SymmsIsCompatibleWithNodes (Abc_Ntk_t *pNtk, unsigned uSymm, Vec_Ptr_t *vNodesOther, int *pMap)
static int Sim_SymmsIsCompatibleWithGroup (unsigned uSymm, Vec_Ptr_t *vNodesPi, int *pMap)
static void Sim_SymmsPrint (Vec_Int_t *vSymms)
static void Sim_SymmsTrans (Vec_Int_t *vSymms)
static void Sim_SymmsTransferToMatrix (Extra_BitMat_t *pMatSymm, Vec_Int_t *vSymms, unsigned *pSupport)
static int * Sim_SymmsCreateMap (Abc_Ntk_t *pNtk)
void Sim_SymmsStructCompute (Abc_Ntk_t *pNtk, Vec_Ptr_t *vMatrs, Vec_Ptr_t *vSuppFun)

Define Documentation

#define SIM_READ_SYMMS ( pNode   )     ((Vec_Int_t *)pNode->pCopy)

CFile****************************************************************

FileName [simSymStr.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Structural detection of symmetries.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
simSymStr.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

] DECLARATIONS ///

Definition at line 28 of file simSymStr.c.

#define SIM_SET_SYMMS ( pNode,
vVect   )     (pNode->pCopy = (Abc_Obj_t *)(vVect))

Definition at line 29 of file simSymStr.c.

Function Documentation

void Sim_SymmsAppendFromGroup ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vNodesPi,
Vec_Ptr_t *  vNodesOther,
Vec_Int_t *  vSymms,
int *  pMap 
) [static]

Function*************************************************************

Synopsis [Makes the product of two partitions.]

Description []

SideEffects []

SeeAlso []

Definition at line 221 of file simSymStr.c.

00222 {
00223     Abc_Obj_t * pNode1, * pNode2;
00224     unsigned uSymm;
00225     int i, k;
00226 
00227     if ( vNodesPi->nSize == 0 )
00228         return;
00229 
00230     // go through the pairs
00231     for ( i = 0; i < vNodesPi->nSize; i++ )
00232     for ( k = i+1; k < vNodesPi->nSize; k++ )
00233     {
00234         // get the two PI nodes
00235         pNode1 = Abc_ObjRegular(vNodesPi->pArray[i]);
00236         pNode2 = Abc_ObjRegular(vNodesPi->pArray[k]);
00237         assert( pMap[pNode1->Id] != pMap[pNode2->Id] );
00238         assert( pMap[pNode1->Id] >= 0 );
00239         assert( pMap[pNode2->Id] >= 0 );
00240         // generate symmetry
00241         if ( pMap[pNode1->Id] < pMap[pNode2->Id] )
00242             uSymm = ((pMap[pNode1->Id] << 16) | pMap[pNode2->Id]);
00243         else
00244             uSymm = ((pMap[pNode2->Id] << 16) | pMap[pNode1->Id]);
00245         // check if symmetry belongs
00246         if ( Sim_SymmsIsCompatibleWithNodes( pNtk, uSymm, vNodesOther, pMap ) )
00247             Vec_IntPushUnique( vSymms, (int)uSymm );
00248     }
00249 }

void Sim_SymmsAppendFromNode ( Abc_Ntk_t *  pNtk,
Vec_Int_t *  vSymms0,
Vec_Ptr_t *  vNodesOther,
Vec_Ptr_t *  vNodesPi0,
Vec_Ptr_t *  vNodesPi1,
Vec_Int_t *  vSymms,
int *  pMap 
) [static]

Function*************************************************************

Synopsis [Add the filters symmetries from the nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 262 of file simSymStr.c.

00264 {
00265     unsigned uSymm;
00266     int i;
00267 
00268     if ( vSymms0->nSize == 0 )
00269         return;
00270 
00271     // go through the pairs
00272     for ( i = 0; i < vSymms0->nSize; i++ )
00273     {
00274         uSymm = (unsigned)vSymms0->pArray[i];
00275         // check if symmetry belongs
00276         if ( Sim_SymmsIsCompatibleWithNodes( pNtk, uSymm, vNodesOther, pMap ) &&
00277              Sim_SymmsIsCompatibleWithGroup( uSymm, vNodesPi0, pMap ) && 
00278              Sim_SymmsIsCompatibleWithGroup( uSymm, vNodesPi1, pMap ) )
00279             Vec_IntPushUnique( vSymms, (int)uSymm );
00280     }
00281 }

void Sim_SymmsBalanceCollect_rec ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vNodes 
) [static]

Function*************************************************************

Synopsis [Returns the array of nodes to be combined into one multi-input AND-gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 164 of file simSymStr.c.

00165 {
00166     // if the new node is complemented, another gate begins
00167     if ( Abc_ObjIsComplement(pNode) )
00168     {
00169         Vec_PtrPushUnique( vNodes, pNode );
00170         return;
00171     }
00172     // if pNew is the PI node, return
00173     if ( Abc_ObjIsCi(pNode) )
00174     {
00175         Vec_PtrPushUnique( vNodes, pNode );
00176         return;    
00177     }
00178     // go through the branches
00179     Sim_SymmsBalanceCollect_rec( Abc_ObjChild0(pNode), vNodes );
00180     Sim_SymmsBalanceCollect_rec( Abc_ObjChild1(pNode), vNodes );
00181 }

int * Sim_SymmsCreateMap ( Abc_Ntk_t *  pNtk  )  [static]

Function*************************************************************

Synopsis [Mapping of indices into numbers.]

Description []

SideEffects []

SeeAlso []

Definition at line 469 of file simSymStr.c.

00470 {
00471     int * pMap;
00472     Abc_Obj_t * pNode;
00473     int i;
00474     pMap = ALLOC( int, Abc_NtkObjNumMax(pNtk) );
00475     for ( i = 0; i < Abc_NtkObjNumMax(pNtk); i++ )
00476         pMap[i] = -1;
00477     Abc_NtkForEachCi( pNtk, pNode, i )
00478         pMap[pNode->Id] = i;
00479     return pMap;
00480 }

int Sim_SymmsIsCompatibleWithGroup ( unsigned  uSymm,
Vec_Ptr_t *  vNodesPi,
int *  pMap 
) [static]

Function*************************************************************

Synopsis [Returns 1 if symmetry is compatible with the group of PIs.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file simSymStr.c.

00345 {
00346     Abc_Obj_t * pNode;
00347     int i, Ind1, Ind2, fHasVar1, fHasVar2;
00348 
00349     if ( vNodesPi->nSize == 0 )
00350         return 1;
00351 
00352     // get the indices of the PI variables
00353     Ind1 = (uSymm & 0xffff);
00354     Ind2 = (uSymm >> 16);
00355 
00356     // go through the PI nodes
00357     fHasVar1 = fHasVar2 = 0;
00358     for ( i = 0; i < vNodesPi->nSize; i++ )
00359     {
00360         pNode = Abc_ObjRegular(vNodesPi->pArray[i]);
00361         if ( pMap[pNode->Id] == Ind1 )
00362             fHasVar1 = 1;
00363         else if ( pMap[pNode->Id] == Ind2 )
00364             fHasVar2 = 1;
00365     }
00366     return fHasVar1 == fHasVar2;
00367 }

int Sim_SymmsIsCompatibleWithNodes ( Abc_Ntk_t *  pNtk,
unsigned  uSymm,
Vec_Ptr_t *  vNodesOther,
int *  pMap 
) [static]

Function*************************************************************

Synopsis [Returns 1 if symmetry is compatible with the group of nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 294 of file simSymStr.c.

00295 {
00296     Vec_Int_t * vSymmsNode;
00297     Abc_Obj_t * pNode;
00298     int i, s, Ind1, Ind2, fIsVar1, fIsVar2;
00299 
00300     if ( vNodesOther->nSize == 0 )
00301         return 1;
00302 
00303     // get the indices of the PI variables
00304     Ind1 = (uSymm & 0xffff);
00305     Ind2 = (uSymm >> 16);
00306 
00307     // go through the nodes
00308     // if they do not belong to a support, it is okay
00309     // if one belongs, the other does not belong, quit
00310     // if they belong, but are not part of symmetry, quit
00311     for ( i = 0; i < vNodesOther->nSize; i++ )
00312     {
00313         pNode = Abc_ObjRegular(vNodesOther->pArray[i]);
00314         fIsVar1 = Sim_SuppStrHasVar( pNtk->vSupps, pNode, Ind1 );
00315         fIsVar2 = Sim_SuppStrHasVar( pNtk->vSupps, pNode, Ind2 );
00316 
00317         if ( !fIsVar1 && !fIsVar2 )
00318             continue;
00319         if ( fIsVar1 ^ fIsVar2 )
00320             return 0;
00321         // both belong
00322         // check if there is a symmetry
00323         vSymmsNode = SIM_READ_SYMMS( pNode );
00324         for ( s = 0; s < vSymmsNode->nSize; s++ )
00325             if ( uSymm == (unsigned)vSymmsNode->pArray[s] )
00326                 break;
00327         if ( s == vSymmsNode->nSize )
00328             return 0;
00329     }
00330     return 1;
00331 }

void Sim_SymmsPartitionNodes ( Vec_Ptr_t *  vNodes,
Vec_Ptr_t *  vNodesPis0,
Vec_Ptr_t *  vNodesPis1,
Vec_Ptr_t *  vNodesOther 
) [static]

Function*************************************************************

Synopsis [Divides PI variables into groups.]

Description []

SideEffects []

SeeAlso []

Definition at line 194 of file simSymStr.c.

00196 {
00197     Abc_Obj_t * pNode;
00198     int i;
00199     Vec_PtrForEachEntry( vNodes, pNode, i )
00200     {
00201         if ( !Abc_ObjIsCi(Abc_ObjRegular(pNode)) )
00202             Vec_PtrPush( vNodesOther, pNode );
00203         else if ( Abc_ObjIsComplement(pNode) )
00204             Vec_PtrPush( vNodesPis0, pNode );
00205         else
00206             Vec_PtrPush( vNodesPis1, pNode );
00207     }
00208 }

static void Sim_SymmsPrint ( Vec_Int_t *  vSymms  )  [static]
void Sim_SymmsStructCompute ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vMatrs,
Vec_Ptr_t *  vSuppFun 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Computes symmetries for a single output function.]

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file simSymStr.c.

00059 {
00060     Vec_Ptr_t * vNodes;
00061     Abc_Obj_t * pTemp;
00062     int * pMap, i;
00063 
00064     assert( Abc_NtkCiNum(pNtk) + 10 < (1<<16) );
00065 
00066     // get the structural support
00067     pNtk->vSupps = Sim_ComputeStrSupp( pNtk );
00068     // set elementary info for the CIs
00069     Abc_NtkForEachCi( pNtk, pTemp, i )
00070         SIM_SET_SYMMS( pTemp, Vec_IntAlloc(0) );
00071     // create the map of CI ids into their numbers
00072     pMap = Sim_SymmsCreateMap( pNtk );
00073     // collect the nodes in the TFI cone of this output
00074     vNodes = Abc_NtkDfs( pNtk, 0 );
00075     Vec_PtrForEachEntry( vNodes, pTemp, i )
00076     {
00077 //        if ( Abc_NodeIsConst(pTemp) )
00078 //            continue;
00079         Sim_SymmsStructComputeOne( pNtk, pTemp, pMap );
00080     }
00081     // collect the results for the COs;
00082     Abc_NtkForEachCo( pNtk, pTemp, i )
00083     {
00084 //printf( "Output %d:\n", i );
00085         pTemp = Abc_ObjFanin0(pTemp);
00086         if ( Abc_ObjIsCi(pTemp) || Abc_AigNodeIsConst(pTemp) )
00087             continue;
00088         Sim_SymmsTransferToMatrix( Vec_PtrEntry(vMatrs, i), SIM_READ_SYMMS(pTemp), Vec_PtrEntry(vSuppFun, i) );
00089     }
00090     // clean the intermediate results
00091     Sim_UtilInfoFree( pNtk->vSupps );
00092     pNtk->vSupps = NULL;
00093     Abc_NtkForEachCi( pNtk, pTemp, i )
00094         Vec_IntFree( SIM_READ_SYMMS(pTemp) );
00095     Vec_PtrForEachEntry( vNodes, pTemp, i )
00096 //        if ( !Abc_NodeIsConst(pTemp) )
00097             Vec_IntFree( SIM_READ_SYMMS(pTemp) );
00098     Vec_PtrFree( vNodes );
00099     free( pMap );
00100 }

void Sim_SymmsStructComputeOne ( Abc_Ntk_t *  pNtk,
Abc_Obj_t *  pNode,
int *  pMap 
) [static]

Function*************************************************************

Synopsis [Recursively computes symmetries. ]

Description []

SideEffects []

SeeAlso []

Definition at line 113 of file simSymStr.c.

00114 {
00115     Vec_Ptr_t * vNodes, * vNodesPi0, * vNodesPi1, * vNodesOther;
00116     Vec_Int_t * vSymms;
00117     Abc_Obj_t * pTemp;
00118     int i;
00119 
00120     // allocate the temporary arrays
00121     vNodes      = Vec_PtrAlloc( 10 );
00122     vNodesPi0   = Vec_PtrAlloc( 10 );
00123     vNodesPi1   = Vec_PtrAlloc( 10 );
00124     vNodesOther = Vec_PtrAlloc( 10 );  
00125 
00126     // collect the fanins of the implication supergate
00127     Sim_SymmsBalanceCollect_rec( pNode, vNodes );
00128 
00129     // sort the nodes in the implication supergate
00130     Sim_SymmsPartitionNodes( vNodes, vNodesPi0, vNodesPi1, vNodesOther );
00131 
00132     // start the resulting set
00133     vSymms = Vec_IntAlloc( 10 );
00134     // generate symmetries from the groups
00135     Sim_SymmsAppendFromGroup( pNtk, vNodesPi0, vNodesOther, vSymms, pMap );
00136     Sim_SymmsAppendFromGroup( pNtk, vNodesPi1, vNodesOther, vSymms, pMap );
00137     // add symmetries from other inputs
00138     for ( i = 0; i < vNodesOther->nSize; i++ )
00139     {
00140         pTemp = Abc_ObjRegular(vNodesOther->pArray[i]);
00141         Sim_SymmsAppendFromNode( pNtk, SIM_READ_SYMMS(pTemp), vNodesOther, vNodesPi0, vNodesPi1, vSymms, pMap );
00142     }
00143     Vec_PtrFree( vNodes );
00144     Vec_PtrFree( vNodesPi0 );
00145     Vec_PtrFree( vNodesPi1 );
00146     Vec_PtrFree( vNodesOther );
00147 
00148     // set the symmetry at the node
00149     SIM_SET_SYMMS( pNode, vSymms );
00150 }

void Sim_SymmsTrans ( Vec_Int_t *  vSymms  )  [static]

Function*************************************************************

Synopsis [Improvements due to transitivity.]

Description []

SideEffects []

SeeAlso []

Definition at line 382 of file simSymStr.c.

00383 {
00384     unsigned uSymm, uSymma, uSymmr;
00385     int i, Ind1, Ind2;
00386     int k, Ind1a, Ind2a;
00387     int j;
00388     int nTrans = 0;
00389 
00390     for ( i = 0; i < vSymms->nSize; i++ )
00391     {
00392         uSymm = (unsigned)vSymms->pArray[i];
00393         Ind1 = (uSymm & 0xffff);
00394         Ind2 = (uSymm >> 16);
00395         // find other symmetries that have Ind1
00396         for ( k = i+1; k < vSymms->nSize; k++ )
00397         {
00398             uSymma = (unsigned)vSymms->pArray[k];
00399             if ( uSymma == uSymm )
00400                 continue;
00401             Ind1a = (uSymma & 0xffff);
00402             Ind2a = (uSymma >> 16);
00403             if ( Ind1a == Ind1 )
00404             {
00405                 // find the symmetry (Ind2,Ind2a)
00406                 if ( Ind2 < Ind2a )
00407                     uSymmr = ((Ind2 << 16) | Ind2a);
00408                 else
00409                     uSymmr = ((Ind2a << 16) | Ind2);
00410                 for ( j = 0; j < vSymms->nSize; j++ )
00411                     if ( uSymmr == (unsigned)vSymms->pArray[j] )
00412                         break;
00413                 if ( j == vSymms->nSize )
00414                     nTrans++;
00415             }
00416         }
00417 
00418     }
00419     printf( "Trans = %d.\n", nTrans );
00420 }

void Sim_SymmsTransferToMatrix ( Extra_BitMat_t *  pMatSymm,
Vec_Int_t *  vSymms,
unsigned *  pSupport 
) [static]

Function*************************************************************

Synopsis [Transfers from the vector to the matrix.]

Description []

SideEffects []

SeeAlso []

Definition at line 434 of file simSymStr.c.

00435 {
00436     int i, Ind1, Ind2, nInputs;
00437     unsigned uSymm;
00438     // add diagonal elements
00439     nInputs = Extra_BitMatrixReadSize( pMatSymm );
00440     for ( i = 0; i < nInputs; i++ )
00441         Extra_BitMatrixInsert1( pMatSymm, i, i );
00442     // add non-diagonal elements
00443     for ( i = 0; i < vSymms->nSize; i++ )
00444     {
00445         uSymm = (unsigned)vSymms->pArray[i];
00446         Ind1 = (uSymm & 0xffff);
00447         Ind2 = (uSymm >> 16);
00448 //printf( "%d,%d ", Ind1, Ind2 );
00449         // skip variables that are not in the true support
00450         assert( Sim_HasBit(pSupport, Ind1) == Sim_HasBit(pSupport, Ind2) );
00451         if ( !Sim_HasBit(pSupport, Ind1) || !Sim_HasBit(pSupport, Ind2) )
00452             continue;
00453         Extra_BitMatrixInsert1( pMatSymm, Ind1, Ind2 );
00454         Extra_BitMatrixInsert2( pMatSymm, Ind1, Ind2 );
00455     }
00456 }

Generated on Tue Jan 5 12:19:36 2010 for abc70930 by  doxygen 1.6.1