diff options
| -rw-r--r-- | src/aig/gia/gia.h | 2 | ||||
| -rw-r--r-- | src/aig/gia/giaShow.c | 310 | ||||
| -rw-r--r-- | src/base/abci/abc.c | 15 | ||||
| -rw-r--r-- | src/opt/sbd/sbdPath.c | 54 | 
4 files changed, 365 insertions, 16 deletions
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 7cf1feff..68060119 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -1426,7 +1426,7 @@ extern Gia_Man_t *         Gia_ManCleanupOutputs( Gia_Man_t * p, int nOutputs );  extern Gia_Man_t *         Gia_ManSeqCleanup( Gia_Man_t * p );  extern Gia_Man_t *         Gia_ManSeqStructSweep( Gia_Man_t * p, int fConst, int fEquiv, int fVerbose );  /*=== giaShow.c ===========================================================*/ -extern void                Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds ); +extern void                Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds, int fPath );  /*=== giaShrink.c ===========================================================*/  extern Gia_Man_t *         Gia_ManMapShrink4( Gia_Man_t * p, int fKeepLevel, int fVerbose );  extern Gia_Man_t *         Gia_ManMapShrink6( Gia_Man_t * p, int nFanoutMax, int fKeepLevel, int fVerbose ); diff --git a/src/aig/gia/giaShow.c b/src/aig/gia/giaShow.c index 5589d384..28e874bf 100644 --- a/src/aig/gia/giaShow.c +++ b/src/aig/gia/giaShow.c @@ -46,6 +46,294 @@ ABC_NAMESPACE_IMPL_START    SeeAlso     []  ***********************************************************************/ +void Gia_ShowPath( Gia_Man_t * p, char * pFileName ) +{ +    FILE * pFile; +    Gia_Obj_t * pNode; +    Vec_Bit_t * vPath = Vec_BitStart( Gia_ManObjNum(p) ); +    int i, k, iFan, LevelMax, nLevels, * pLevels, Level, Prev; +    int nLuts = 0, nNodes = 0, nEdges = 0, nEdgesAll = 0; +    assert( Gia_ManHasMapping(p) ); + +    // set critical CO drivers +    nLevels = Gia_ManLutLevel( p, &pLevels ); +    Gia_ManForEachCoDriverId( p, iFan, i ) +        if ( pLevels[iFan] == nLevels ) +            Vec_BitWriteEntry( vPath, iFan, 1 ); + +    // set critical internal nodes +    Gia_ManForEachLutReverse( p, i ) +    {  +        nLuts++; +        if ( !Vec_BitEntry(vPath, i) ) +            continue; +        nNodes++; +        Gia_LutForEachFanin( p, i, iFan, k ) +        { +            if ( pLevels[iFan] +1 < pLevels[i] ) +                continue; +            assert( pLevels[iFan] + 1 == pLevels[i] ); +            Vec_BitWriteEntry( vPath, iFan, 1 ); +            nEdges++; +            //printf( "%d -> %d\n", i, iFan ); +        } +    } + +    if ( nNodes > 500 ) +    { +        ABC_FREE( pLevels ); +        Vec_BitFree( vPath ); +        fprintf( stdout, "Cannot visualize AIG with more than 500 critical nodes.\n" ); +        return; +    } +    if ( (pFile = fopen( pFileName, "w" )) == NULL ) +    { +        ABC_FREE( pLevels ); +        Vec_BitFree( vPath ); +        fprintf( stdout, "Cannot open the intermediate file \"%s\".\n", pFileName ); +        return; +    } + +    Vec_IntFreeP( &p->vLevels ); +    p->vLevels = Vec_IntAllocArray( pLevels, Gia_ManObjNum(p) ); + +    // compute CO levels +    LevelMax = 1 + nLevels; +    Gia_ManForEachCo( p, pNode, i ) +        Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax ); + +    // write the DOT header +    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "digraph AIG {\n" ); +    fprintf( pFile, "size = \"7.5,10\";\n" ); +//  fprintf( pFile, "ranksep = 0.5;\n" ); +//  fprintf( pFile, "nodesep = 0.5;\n" ); +    fprintf( pFile, "center = true;\n" ); +//  fprintf( pFile, "orientation = landscape;\n" ); +//  fprintf( pFile, "edge [fontsize = 10];\n" ); +//  fprintf( pFile, "edge [dir = none];\n" ); +    fprintf( pFile, "edge [dir = back];\n" ); +    fprintf( pFile, "\n" ); + +    // labels on the left of the picture +    fprintf( pFile, "{\n" ); +    fprintf( pFile, "  node [shape = plaintext];\n" ); +    fprintf( pFile, "  edge [style = invis];\n" ); +    fprintf( pFile, "  LevelTitle1 [label=\"\"];\n" ); +    fprintf( pFile, "  LevelTitle2 [label=\"\"];\n" ); +    // generate node names with labels +    for ( Level = LevelMax; Level >= 0; Level-- ) +    { +        // the visible node name +        fprintf( pFile, "  Level%d", Level ); +        fprintf( pFile, " [label = " ); +        // label name +        fprintf( pFile, "\"" ); +        fprintf( pFile, "\"" ); +        fprintf( pFile, "];\n" ); +    } + +    // genetate the sequence of visible/invisible nodes to mark levels +    fprintf( pFile, "  LevelTitle1 ->  LevelTitle2 ->" ); +    for ( Level = LevelMax; Level >= 0; Level-- ) +    { +        // the visible node name +        fprintf( pFile, "  Level%d",  Level ); +        // the connector +        if ( Level != 0 ) +            fprintf( pFile, " ->" ); +        else +            fprintf( pFile, ";" ); +    } +    fprintf( pFile, "\n" ); +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); + +    // generate title box on top +    fprintf( pFile, "{\n" ); +    fprintf( pFile, "  rank = same;\n" ); +    fprintf( pFile, "  LevelTitle1;\n" ); +    fprintf( pFile, "  title1 [shape=plaintext,\n" ); +    fprintf( pFile, "          fontsize=20,\n" ); +    fprintf( pFile, "          fontname = \"Times-Roman\",\n" ); +    fprintf( pFile, "          label=\"" ); +    fprintf( pFile, "%s", "AIG structure visualized by ABC" ); +    fprintf( pFile, "\\n" ); +    fprintf( pFile, "Benchmark \\\"%s\\\". ", "aig" ); +//    fprintf( pFile, "Time was %s. ",  Extra_TimeStamp() ); +    fprintf( pFile, "\"\n" ); +    fprintf( pFile, "         ];\n" ); +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); + +    // generate statistics box +    fprintf( pFile, "{\n" ); +    fprintf( pFile, "  rank = same;\n" ); +    fprintf( pFile, "  LevelTitle2;\n" ); +    fprintf( pFile, "  title2 [shape=plaintext,\n" ); +    fprintf( pFile, "          fontsize=18,\n" ); +    fprintf( pFile, "          fontname = \"Times-Roman\",\n" ); +    fprintf( pFile, "          label=\"" ); +    fprintf( pFile, "The critical path contains %d LUTs with %d critical edges and spans %d levels.", nNodes, nEdges, nLevels ); +    fprintf( pFile, "\\n" ); +    fprintf( pFile, "\"\n" ); +    fprintf( pFile, "         ];\n" ); +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); + +    // generate the COs +    fprintf( pFile, "{\n" ); +    fprintf( pFile, "  rank = same;\n" ); +    // the labeling node of this level +    fprintf( pFile, "  Level%d;\n",  LevelMax ); +    // generate the CO nodes +    Gia_ManForEachCo( p, pNode, i ) +    { +        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels ) +            continue; +        assert( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels ); +        fprintf( pFile, "  Node%d [label = \"%d\"", Gia_ObjId(p, pNode), Gia_ObjId(p, pNode) );  +        fprintf( pFile, ", shape = %s", "invtriangle" ); +        fprintf( pFile, ", color = coral, fillcolor = coral" ); +        fprintf( pFile, "];\n" ); +    } +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); + +    // generate nodes of each rank +    for ( Level = LevelMax - 1; Level > 0; Level-- ) +    { +        fprintf( pFile, "{\n" ); +        fprintf( pFile, "  rank = same;\n" ); +        // the labeling node of this level +        fprintf( pFile, "  Level%d;\n",  Level ); +        Gia_ManForEachObj( p, pNode, i ) +        { +            if ( (int)Gia_ObjLevel(p, pNode) != Level || !Vec_BitEntry(vPath, i) ) +                continue; +            fprintf( pFile, "  Node%d [label = \"%d:%d\"", i, i, Gia_ObjIsAnd(pNode)? Gia_ObjLutSize(p, i) : 0 );  +            fprintf( pFile, ", shape = ellipse" ); +            if ( pNode->fMark0 ) +                fprintf( pFile, ", style = filled" ); +            fprintf( pFile, "];\n" ); +        } +        fprintf( pFile, "}" ); +        fprintf( pFile, "\n" ); +        fprintf( pFile, "\n" ); +    } + +    // generate the CI nodes +    fprintf( pFile, "{\n" ); +    fprintf( pFile, "  rank = same;\n" ); +    // the labeling node of this level +    fprintf( pFile, "  Level%d;\n",  0 ); +    // generate the CI nodes +    Gia_ManForEachCi( p, pNode, i ) +    { +        if ( !Vec_BitEntry(vPath, Gia_ObjId(p, pNode)) ) +            continue; +        fprintf( pFile, "  Node%d [label = \"%d\"", Gia_ObjId(p, pNode), Gia_ObjId(p, pNode) );  +        fprintf( pFile, ", shape = %s", "triangle" ); +        fprintf( pFile, ", color = coral, fillcolor = coral" ); +        fprintf( pFile, "];\n" ); +    } +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); + +    // generate invisible edges from the square down +    fprintf( pFile, "title1 -> title2 [style = invis];\n" ); +    Gia_ManForEachCo( p, pNode, i ) +    { +        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels ) +            continue; +        fprintf( pFile, "title2 -> Node%d [style = invis];\n", Gia_ObjId(p, pNode) ); +    } +    // generate invisible edges among the COs +    Prev = -1; +    Gia_ManForEachCo( p, pNode, i ) +    { +        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels ) +            continue; +        assert( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels ); +        if ( Prev >= 0 ) +            fprintf( pFile, "Node%d -> Node%d [style = invis];\n", Prev, Gia_ObjId(p, pNode) ); +        Prev = Gia_ObjId(p, pNode); +    } +    // generate invisible edges among the CIs +    Prev = -1; +    Gia_ManForEachCi( p, pNode, i ) +    { +        if ( !Vec_BitEntry(vPath, Gia_ObjId(p, pNode)) ) +            continue; +        if ( Prev >= 0 ) +            fprintf( pFile, "Node%d -> Node%d [style = invis];\n", Prev, Gia_ObjId(p, pNode) ); +        Prev = Gia_ObjId(p, pNode); +    } + +    // generate edges +    Gia_ManForEachObj( p, pNode, i ) +    { +        if ( Gia_ObjIsCo(pNode) ) +        { +            if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels ) +            { +                // generate the edge from this node to the next +                fprintf( pFile, "Node%d",  i ); +                fprintf( pFile, " -> " ); +                fprintf( pFile, "Node%d",  Gia_ObjFaninId0p(p, pNode) ); +                fprintf( pFile, " [" ); +                fprintf( pFile, "style = %s", "bold" ); +                fprintf( pFile, "]" ); +                fprintf( pFile, ";\n" ); +            } +            continue; +        } +        if ( !Gia_ObjIsAnd(pNode) || !Vec_BitEntry(vPath, i) ) +            continue; +        Gia_LutForEachFanin( p, i, iFan, k ) +        { +            if ( pLevels[iFan] + 1 < pLevels[i] ) +                continue; +            assert( pLevels[iFan] + 1 == pLevels[i] ); +            // generate the edge from this node to the next +            fprintf( pFile, "Node%d",  i ); +            fprintf( pFile, " -> " ); +            fprintf( pFile, "Node%d",  iFan ); +            fprintf( pFile, " [" ); +            fprintf( pFile, "style = %s", "bold" ); +            fprintf( pFile, "]" ); +            fprintf( pFile, ";\n" ); +        } +    } + +    fprintf( pFile, "}" ); +    fprintf( pFile, "\n" ); +    fprintf( pFile, "\n" ); +    fclose( pFile ); + +    Vec_IntFreeP( &p->vLevels ); +    Vec_BitFree( vPath ); +} + + +/**Function************************************************************* + +  Synopsis    [Writes the graph structure of AIG for DOT.] + +  Description [Useful for graph visualization using tools such as GraphViz:  +  http://www.graphviz.org/] +   +  SideEffects [] + +  SeeAlso     [] + +***********************************************************************/  void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )  {      FILE * pFile; @@ -79,7 +367,7 @@ void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )          Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax );      // write the DOT header -    fprintf( pFile, "# %s\n",  "AIG structure generated by IVY package" ); +    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" );      fprintf( pFile, "\n" );      fprintf( pFile, "digraph AIG {\n" );      fprintf( pFile, "size = \"7.5,10\";\n" ); @@ -153,7 +441,7 @@ void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )      fprintf( pFile, "          fontsize=18,\n" );      fprintf( pFile, "          fontname = \"Times-Roman\",\n" );      fprintf( pFile, "          label=\"" ); -    fprintf( pFile, "The set contains %d logic nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax ); +    fprintf( pFile, "The AIG contains %d nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax-1 );      fprintf( pFile, "\\n" );      fprintf( pFile, "\"\n" );      fprintf( pFile, "         ];\n" ); @@ -388,6 +676,7 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In      Gia_Obj_t * pNode;//, * pTemp, * pPrev;      int LevelMax, Prev, Level, i;      int fConstIsUsed = 0; +    int nFadds = Ree_ManCountFadds( vAdds );      if ( Gia_ManAndNum(p) > 1000 )      { @@ -406,7 +695,7 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In          Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax );      // write the DOT header -    fprintf( pFile, "# %s\n",  "AIG structure generated by IVY package" ); +    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" );      fprintf( pFile, "\n" );      fprintf( pFile, "digraph AIG {\n" );      fprintf( pFile, "size = \"7.5,10\";\n" ); @@ -480,7 +769,8 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In      fprintf( pFile, "          fontsize=18,\n" );      fprintf( pFile, "          fontname = \"Times-Roman\",\n" );      fprintf( pFile, "          label=\"" ); -    fprintf( pFile, "The set contains %d logic nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax ); +    fprintf( pFile, "The AIG contains %d nodes, %d full-adders, and %d half-adders, and spans %d levels.",  +        Gia_ManAndNum(p), nFadds, Vec_IntSize(vAdds)/6-nFadds, LevelMax-1 );      fprintf( pFile, "\\n" );      fprintf( pFile, "\"\n" );      fprintf( pFile, "         ];\n" ); @@ -813,12 +1103,12 @@ void Gia_ShowProcess( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In      Vec_IntFree( vMapXors );      Vec_IntFree( vOrder );  } -void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds ) +void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds, int fPath )  {      extern void Abc_ShowFile( char * FileNameDot );      char FileNameDot[200];      FILE * pFile; -    Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( pMan, &vXors, 0 ); +    Vec_Int_t * vXors = NULL, * vAdds = fAdders ? Ree_ManComputeCuts( pMan, &vXors, 0 ) : NULL;      sprintf( FileNameDot, "%s", Extra_FileNameGenericAppend(pMan->pName, ".dot") );      // check that the file can be opened      if ( (pFile = fopen( FileNameDot, "w" )) == NULL ) @@ -828,15 +1118,17 @@ void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds )      }      fclose( pFile );      // generate the file -    if ( fAdders ) +    if ( fPath ) +        Gia_ShowPath( pMan, FileNameDot ); +    else if ( fAdders )          Gia_ShowProcess( pMan, FileNameDot, vAdds, vXors, fFadds );      else          Gia_WriteDotAigSimple( pMan, FileNameDot, vBold );      // visualize the file       Abc_ShowFile( FileNameDot ); -    Vec_IntFree( vAdds ); -    Vec_IntFree( vXors ); +    Vec_IntFreeP( &vAdds ); +    Vec_IntFreeP( &vXors );  } diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index 20d44227..910014c6 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -28594,9 +28594,9 @@ usage:  int Abc_CommandAbc9Show( Abc_Frame_t * pAbc, int argc, char ** argv )  {      Vec_Int_t * vBold = NULL; -    int c, fAdders = 0, fFadds = 0; +    int c, fAdders = 0, fFadds = 0, fPath = 0;      Extra_UtilGetoptReset(); -    while ( ( c = Extra_UtilGetopt( argc, argv, "afh" ) ) != EOF ) +    while ( ( c = Extra_UtilGetopt( argc, argv, "afph" ) ) != EOF )      {          switch ( c )          { @@ -28606,6 +28606,9 @@ int Abc_CommandAbc9Show( Abc_Frame_t * pAbc, int argc, char ** argv )          case 'f':              fFadds ^= 1;              break; +        case 'p': +            fPath ^= 1; +            break;          case 'h':              goto usage;          default: @@ -28628,15 +28631,16 @@ int Abc_CommandAbc9Show( Abc_Frame_t * pAbc, int argc, char ** argv )          Gia_ManForEachLut( pAbc->pGia, c )              Vec_IntPush( vBold, c );      } -    Gia_ManShow( pAbc->pGia, vBold, fAdders, fFadds ); +    Gia_ManShow( pAbc->pGia, vBold, fAdders, fFadds, fPath );      Vec_IntFreeP( &vBold );      return 0;  usage: -    Abc_Print( -2, "usage: &show [-afh]\n" ); +    Abc_Print( -2, "usage: &show [-afph]\n" );      Abc_Print( -2, "\t        shows the current GIA using GSView\n" );      Abc_Print( -2, "\t-a    : toggle visualazing adders [default = %s]\n", fAdders? "yes": "no" ); -    Abc_Print( -2, "\t-f    : toggle only showing full-adders with \"-a\" [default = %s]\n", fFadds? "yes": "no" ); +    Abc_Print( -2, "\t-f    : toggle showing only full-adders with \"-a\" [default = %s]\n", fFadds? "yes": "no" ); +    Abc_Print( -2, "\t-p    : toggle showing the critical path of a LUT mapping [default = %s]\n", fPath? "yes": "no" );      Abc_Print( -2, "\t-h    : print the command usage\n");      return 1;  } @@ -42679,7 +42683,6 @@ int Abc_CommandAbc9Test( Abc_Frame_t * pAbc, int argc, char ** argv )  //    Gia_ManCheckFalseTest( pAbc->pGia, nFrames );  //    Gia_ParTest( pAbc->pGia, nWords, nProcs );  //    Gia_PolynExplore( pAbc->pGia ); -//    Gia_ManTestSatEnum( pAbc->pGia );  //    printf( "\nThis command is currently disabled.\n\n" );      return 0; diff --git a/src/opt/sbd/sbdPath.c b/src/opt/sbd/sbdPath.c index a2b1a9b0..270c81c8 100644 --- a/src/opt/sbd/sbdPath.c +++ b/src/opt/sbd/sbdPath.c @@ -134,6 +134,60 @@ Vec_Bit_t * Sbc_ManCriticalPath( Gia_Man_t * p )  } +/**Function************************************************************* + +  Synopsis    [] + +  Description [] +                +  SideEffects [] + +  SeeAlso     [] + +***********************************************************************/ +void Sbc_ManDelayTrace( Gia_Man_t * p ) +{ +    Vec_Bit_t * vPath = Vec_BitStart( Gia_ManObjNum(p) ); +    int i, k, iFan, nLevels, * pLevels; +    int nLuts = 0, nNodes = 0, nEdges = 0, nEdgesAll = 0; +    if ( !Gia_ManHasMapping(p) ) +    { +        printf( "No mapping is available.\n" ); +        return; +    } +    assert( Gia_ManHasMapping(p) ); +    // set critical CO drivers +    nLevels = Gia_ManLutLevel( p, &pLevels ); +    Gia_ManForEachCoDriverId( p, iFan, i ) +        if ( pLevels[iFan] == nLevels ) +            Vec_BitWriteEntry( vPath, iFan, 1 ); +    // set critical internal nodes +    Gia_ManForEachLutReverse( p, i ) +    {  +        nLuts++; +        if ( !Vec_BitEntry(vPath, i) ) +            continue; +        nNodes++; +        Gia_LutForEachFanin( p, i, iFan, k ) +        { +            if ( pLevels[iFan] +1 < pLevels[i] ) +                continue; +            assert( pLevels[iFan] + 1 == pLevels[i] ); +            Vec_BitWriteEntry( vPath, iFan, 1 ); +            nEdges++; +            //printf( "%d -> %d\n", i, iFan ); +        } +    } +    Gia_ManForEachLut( p, i ) +        Gia_LutForEachFanin( p, i, iFan, k ) +            nEdgesAll += (Vec_BitEntry(vPath, i) && Vec_BitEntry(vPath, iFan)); + +    ABC_FREE( pLevels ); +    Vec_BitFree( vPath ); +    printf( "AIG = %d. LUT = %d. Lev = %d.   Path nodes = %d.  Path edges = %d. (%d.)\n",  +        Gia_ManAndNum(p), nLuts, nLevels, nNodes, nEdges, nEdgesAll ); +} +  ////////////////////////////////////////////////////////////////////////  ///                       END OF FILE                                ///  ////////////////////////////////////////////////////////////////////////  | 
