yula_not_mine_live.cpp

Go to the documentation of this file.

// live.C
// 12/16/97 WAH: Cosmetic changes; fixed copy_operand (valid field); fixed
//               matching of operands in BB_defs and BB_uses; adjusted
//               live-in computation.
// 1/9/98 WAH:   Fixed bug in finding children of block in BB_live_out;
//               ChildrenList may be NULL.
// 1/22/98 WAH:  Added checks for valid operands.
// 2/12/98 WAH:  Removed FindFirstDef calls to repair handling of BRLs.

#include <string.h>
#include <iostream.h>
#include <stl.h> 
//#include "lego.H"
//#include "legoUtil.H"
#include        <lego.H>
#include        <legoUtil.H> 
// #include "rdef.H"
//#include "live.H"
#include        "yula_not_mine_live.h" 

char            *get_string_out_of_op(legoOprd *);

// Comment out the debug token if you do NOT want debugging info printed
//#define _LIVE_VAR_DEBUG_
#ifdef _LIVE_VAR_DEBUG_
#define derr(s)         cerr << s
#else
#define derr(s)
#endif

/*
 * CreateReadHashKey
 *   X = basic block id
 *   Y = register number
 *   Z = register file type
 *
 * Creates a hash key for reading the hash table of the form:
 *   bbid-regnum-regfiletype
 * and places it into the ReadHashKey field of the LiveVar_nm object.
 */
inline void LiveVar_nm::CreateReadHashKey (int X, int Y, int Z)
{
  sprintf( ReadHashKey, "%d-", (X) );
  sprintf( ReadHashPart1, "%d-", (Y) );
  sprintf( ReadHashPart2, "%d", (Z) );
  ReadHashKey = strcat(ReadHashKey,ReadHashPart1);
  ReadHashKey = strcat(ReadHashKey,ReadHashPart2);
}

/*
 * CreateReadHashKey
 *   X = basic block id
 *   W = subblock id
 *   Y = register number
 *   Z = register file type
 *
 * Creates a hash key for reading the hash table of the form:
 *   bbid/subblock-regnum-regfiletype
 * and places it into the ReadHashKey field of the LiveVar_nm object.
 */
inline void LiveVar_nm::CreateReadHashKey (int X, int W, int Y, int Z)
{
  sprintf( ReadHashKey, "%d/", (X) );
  sprintf( ReadHashPart1, "%d-", (W) );
  sprintf( ReadHashPart2, "%d-", (Y) );
  sprintf( ReadHashPart3, "%d", (Z) );
  ReadHashKey = strcat(ReadHashKey,ReadHashPart1);
  ReadHashKey = strcat(ReadHashKey,ReadHashPart2);
  ReadHashKey = strcat(ReadHashKey,ReadHashPart3);
}

/*
 * CreateWriteHashKey
 *   X = basic block id
 *   Y = register number
 *   Z = register file type
 *
 * Creates a hash key for writing to the hash table of the form:
 *   bbid-regnum-regfiletype
 * and places it into the WriteHashKey field of the LiveVar_nm object.
 */
inline void LiveVar_nm::CreateWriteHashKey (int X, int Y, int Z)
{
  WriteHashKey = new char[ HASH_KEY_SIZE ];
  WriteHashPart1 = new char[ HASH_PART_SIZE ];
  WriteHashPart2 = new char[ HASH_PART_SIZE ];
  sprintf( WriteHashKey, "%d-", (X) );
  sprintf( WriteHashPart1, "%d-", (Y) );
  sprintf( WriteHashPart2, "%d", (Z) );
  WriteHashKey=strcat(WriteHashKey,WriteHashPart1 );
  WriteHashKey=strcat(WriteHashKey,WriteHashPart2 );
  delete[] WriteHashPart1; delete[] WriteHashPart2;
}

/*
 * CreateWriteHashKey
 *   X = basic block id
 *   W = subblock id
 *   Y = register number
 *   Z = register file type
 *
 * Creates a hash key for writing to the hash table of the form:
 *   bbid/subblcok-regnum-regfiletype
 * and places it into the WriteHashKey field of the LiveVar_nm object.
 */
inline void LiveVar_nm::CreateWriteHashKey (int X, int W, int Y, int Z)
{
  WriteHashKey = new char[ HASH_KEY_SIZE ];
  WriteHashPart1 = new char[ HASH_PART_SIZE ];
  WriteHashPart2 = new char[ HASH_PART_SIZE ];
  WriteHashPart3 = new char[ HASH_PART_SIZE ];
  sprintf( WriteHashKey, "%d/", (X) );
  sprintf( WriteHashPart1, "%d-", (W) );
  sprintf( WriteHashPart2, "%d-", (Y) );
  sprintf( WriteHashPart3, "%d", (Z) );
  WriteHashKey=strcat(WriteHashKey,WriteHashPart1 );
  WriteHashKey=strcat(WriteHashKey,WriteHashPart2 );
  WriteHashKey=strcat(WriteHashKey,WriteHashPart3 );
  delete[] WriteHashPart1; delete[] WriteHashPart2;
  delete[] WriteHashPart3;
}

static int subblock;

/*
 * BB_defs
 *   OpPtr = op on which to work
 *   BBId = id of basic block where op resides
 *
 * Determines the defs for op OpPtr.
 */
void LiveVar_nm::BB_defs( legoOp *OpPtr, int BBId )
{
  legoOprd *OprdPtr, *WalkOprdPtr;
  legoOp *WalkOpPtr;
  SetInfo Info;
  SetInfoTable::iterator LookUpIter, EndPtr;

  int RegNum, RegFileType, OprdType, IsBB, NonDef;


  derr( ">> BB_defs: Op " << OpPtr->GetOpId() << "\n" );

  //  for (OprdPtr = FindFirstDef (OpPtr); OprdPtr != NULL;
  //       OprdPtr = OprdPtr->GetNextOprdPtr() )  // loop through defs of op
  OprdPtr = OpPtr->GetDestOprdPtr();
  while (OprdPtr != NULL)
    {
      //      if (!(OprdPtr->GetValid())) continue;

      OprdType = OprdPtr->GetOprdType();
      if ( OprdType == OT_REG || OprdType == OT_MACRO &&  // reg or macro
           OprdPtr->GetValid())  // ... and a valid operand
        {
          RegNum = OprdPtr->GetOprdRegNum();
          RegFileType = OprdPtr->GetOprdFileType();
          if ( OprdType == OT_MACRO ) RegFileType = -1;  // pseudo-filetype

          derr( "   Dest Reg: # " << RegNum << ", type: " << RegFileType
                << "\n" );

          // It's not in the def set yet. Skip it if there's a use before it
          // in the block / subblock.
          NonDef = 0;
          for ( WalkOpPtr = OpPtr->GetPrevLink(); WalkOpPtr != NULL &&
                  WalkOpPtr->GetOutListPtr() == NULL;
                WalkOpPtr = WalkOpPtr->GetPrevLink() )  // walk up from OpPtr
            {
              for ( WalkOprdPtr = WalkOpPtr->GetSrcOprdPtr();
                    WalkOprdPtr != NULL;
                    WalkOprdPtr = WalkOprdPtr->GetNextOprdPtr() )  // srcs...
                {
                  if ( WalkOprdPtr->GetOprdType() != OprdType ) continue;
                  if ( WalkOprdPtr->GetOprdRegNum() != RegNum ) continue;
                  if ( OprdType != OT_MACRO &&
                       WalkOprdPtr->GetOprdFileType() != RegFileType )
                    continue;

                  // Found a match, so it's not a def.
                  derr( "   Found prior use at op " << WalkOpPtr->GetOpId()
                        << "\n" );
                  NonDef = 1;
                  break;
                } // end for
              if ( NonDef ) break;
            } // for

          // If this is a def (i.e., not a NonDef), write to def set for
          // op.
          //      if ( NonDef ) continue;  // go to next destination
          if ( !NonDef )
            {
              // Write to def set for op.
              IsBB = (((legoRegion *) OpPtr->GetParentBlockPtr())->
                      GetRegionType() == RT_BB);
              if (IsBB)
                CreateReadHashKey( BBId, RegNum, RegFileType );
              else
                CreateReadHashKey( BBId, subblock, RegNum, RegFileType );

              LookUpIter = Table.find( ReadHashKey );  // lookup item
              EndPtr = Table.end();
              if ( LookUpIter == EndPtr )  // If not found...
                {
                  if (IsBB)
                    CreateWriteHashKey( BBId, RegNum, RegFileType );
                  else
                    CreateWriteHashKey( BBId, subblock, RegNum, RegFileType );
                  // Create information.
                  Info.Use = FALSE;
                  Info.Def = TRUE;
                  Info.LiveIn = FALSE;
                  Info.LiveOut = FALSE;
                  Info.Oprd = OprdPtr;
                  Table[ WriteHashKey ] = Info;  // write to hash table!
                  derr( "   ** Add to def set\n");
                } // end if
              else
                {
                  (*LookUpIter).second.Def = TRUE;  // turn on def in item
                  derr( "   ** Mod to def set\n");
                } // end else
            } // end if (is a def)
        } // end if (oprd is reg or macro and is valid)

      // Advance to the next operand. If this is the last real destination
      // of a BRL, move to the return macro.
      if (OpPtr->GetOpcode() == BRL &&
          FindReturnMacro (OpPtr) != OprdPtr &&
          OprdPtr->GetNextOprdPtr() == NULL)
        OprdPtr = FindReturnMacro (OpPtr);  // go to return macro
      else
        OprdPtr = OprdPtr->GetNextOprdPtr();  // advance as usual
      
    } // end for

  derr( "<< BB_defs\n" );
} // end LiveVar_nm::BB_defs


/*
 * BB_uses
 *   OpPtr = op on which to work
 *   BBId = id of basic block where op resides
 *
 * Determines the uses for op OpPtr.
 */
void LiveVar_nm::BB_uses( legoOp *OpPtr, int BBId )
{
  legoOprd *OprdPtr, *WalkOprdPtr;
  legoOp *WalkOpPtr;
  SetInfo Info;
  SetInfoTable::iterator LookUpIter, EndPtr;

  int RegNum, RegFileType, OprdType, IsBB, NonUse;


  derr( ">> BB_uses: Op " << OpPtr->GetOpId() << "\n" );

  for (OprdPtr = OpPtr->GetSrcOprdPtr(); OprdPtr != NULL;
       OprdPtr = OprdPtr->GetNextOprdPtr() )  // loop through sources
    {
      if (!(OprdPtr->GetValid())) continue;

      OprdType = OprdPtr->GetOprdType();
      if ( OprdType == OT_REG || OprdType == OT_MACRO )  // reg or macro
        {
          RegNum = OprdPtr->GetOprdRegNum();
          RegFileType = OprdPtr->GetOprdFileType();
          if ( OprdType == OT_MACRO ) RegFileType = -1;  // pseudo-filetype
          derr( "   Src Register:  # " << RegNum << ", type: "
                << RegFileType << "\n" );

          // It's not in the use set yet. Skip it if there's a def before it
          // in the block / subblock.
          NonUse = 0;
          for ( WalkOpPtr = OpPtr->GetPrevLink(); WalkOpPtr != NULL &&
                  WalkOpPtr->GetOutListPtr() == NULL;
                WalkOpPtr = WalkOpPtr->GetPrevLink() )  // walk up from OpPtr
            {
              //              for ( WalkOprdPtr = FindFirstDef (WalkOpPtr);
              for ( WalkOprdPtr = WalkOpPtr->GetDestOprdPtr();
                    WalkOprdPtr != NULL;
                    WalkOprdPtr = WalkOprdPtr->GetNextOprdPtr() )  // defs...
                {
                  if ( WalkOprdPtr->GetOprdType() != OprdType ) continue;
                  if ( WalkOprdPtr->GetOprdRegNum() != RegNum ) continue;
                  if ( OprdType != OT_MACRO &&
                       WalkOprdPtr->GetOprdFileType() != RegFileType )
                    continue;

                  // Found a match, so it's not a use.
                  derr( "   Found prior def at op " << WalkOpPtr->GetOpId()
                        << "\n" );
                  NonUse = 1;
                  break;
                } // end for
              // For BRLs, try to match the return macro as well.
              if ( !NonUse && WalkOpPtr->GetOpcode() == BRL &&
                   OprdType == OT_MACRO )
                {
                  WalkOprdPtr = FindReturnMacro( WalkOpPtr );
                  if ( WalkOprdPtr != NULL &&
                       WalkOprdPtr->GetOprdRegNum() == RegNum )  // enough
                    {
                      // Found a match, so it's not a use.
                      derr( "   Found prior def at op " << WalkOpPtr->GetOpId()
                            << "\n" );
                      NonUse = 1;
                    } // end if
                } // end if
              
              if ( NonUse ) break;
            } // end for
          if ( NonUse ) continue;  // go to next source

          // Write to use set for op.
          IsBB = (((legoRegion *) OpPtr->GetParentBlockPtr())->GetRegionType()
                  == RT_BB);
          if (IsBB)
            CreateReadHashKey( BBId, RegNum, RegFileType );
          else
            CreateReadHashKey( BBId, subblock, RegNum, RegFileType );

          LookUpIter = Table.find( ReadHashKey );  // lookup item
          EndPtr = Table.end();
          if ( LookUpIter == EndPtr )  // If not found...
            {
              if (IsBB)
                CreateWriteHashKey( BBId, RegNum, RegFileType );
              else
                CreateWriteHashKey( BBId, subblock, RegNum, RegFileType );
              // Create information.
              Info.Use = TRUE;
              Info.Def = FALSE;
              Info.LiveIn = FALSE;
              Info.LiveOut = FALSE;
              Info.Oprd = OprdPtr;
              Table[ WriteHashKey ] = Info;  // write to hash table!
              derr( "   ** Add to use set\n");
            } // if
          else
            {
              (*LookUpIter).second.Use = TRUE;  // turn on use in item
              derr( "   ** Mod to use set\n");
            } // end else
        } // if
    } // end for

  derr( "<< BB_uses\n" );
} // end LiveVar_nm::BB_uses

// ==========================================================================

// find_control_edge: return a ptr to the control edge between Parent & Child.
//    Assumes that there exists at most 1 control edge between Parent & Child.
/*
static opEdges *find_control_edge( legoOp *ParentExit, legoRegion *Child )
{
   legoRegion *Parent = (legoRegion *) ParentExit->GetParentBlockPtr();
   int OutEdgeId, InEdgeId;
   edgeList *OutEdges, *InEdges;
   opEdges *CurrentOutEdge, *CurrentInEdge;


   // Search through all of Parent's exit egdes until the one that
   // flows between Parent & Child is found
   for ( OutEdges = Parent->GetOutEdgesPtr(); OutEdges != NULL;
      OutEdges = OutEdges->GetNextListPtr() ) {
      if ( OutEdges->GetEdgePtr()->GetFromOpPtr() != ParentExit ) continue;
      OutEdgeId = OutEdges->GetEdgePtr()->GetEdgeId();

      for ( InEdges = Child->GetInEdgesPtr(); InEdges != NULL;
            InEdges = InEdges->GetNextListPtr() ) {
         InEdgeId = InEdges->GetEdgePtr()->GetEdgeId();
         if ( OutEdgeId == InEdgeId ) return InEdges->GetEdgePtr();
      }
    }

   return NULL;
}
*/

// print_attr: print the entire attr
/*
static void print_attr( attrs *Attr )
{
   legoOprd *OprdPtr;

   derr( ">> print_attr\n" );
   for ( OprdPtr = Attr->GetAttrOprdPtr(); OprdPtr != NULL;
         OprdPtr = OprdPtr->GetNextOprdPtr() ) {

      int RegNum = OprdPtr->GetOprdRegNum(),
          RegFileType = OprdPtr->GetOprdFileType();

      if ( OprdPtr->GetOprdType() == OT_MACRO ) RegFileType = -1;
      cerr << "   RegFile " << RegFileType << ", RegNum " << RegNum << "\n";
   }
   derr( "<< print_attr\n" );
}
*/

/*
 * copy_operand
 *   Src = source operand
 *   Target = target operand
 *
 * Copies fields from Src to Target, assuming a register-type operand.
 * Does NOT copy next and prev pointers.
 */
static void copy_operand( legoOprd *Src, legoOprd *Target )
{
   Target->SetOprdType( Src->GetOprdType() );
   Target->SetValid( Src->GetValid() );
   Target->SetOprdRegType( Src->GetOprdRegType() );
   Target->SetOprdRegNum( Src->GetOprdRegNum() );
   Target->SetOprdDataType( Src->GetOprdDataType() );
   Target->SetOprdFileType( Src->GetOprdFileType() );
   Target->SetOprdRegStyle( Src->GetOprdRegStyle() );
   Target->SetIntValue( Src->GetOprdIntValue() );
} // end copy_operand

/*
 * add_to_existing_attr
 *   Attr = existing live attribute
 *   NewOprd = new operand to add to attribute
 *
 * Adds a copy of the operand NewOprd to attribute Attr. If a copy
 * already resides in Attr, no action is taken.
 */
static void add_to_existing_attr( attrs *Attr, legoOprd *NewOprd )
{
   legoOprd *OprdPtr, *ShadowPtr;
#ifdef _LIVE_VAR_DEBUG_
   int RegNum, RegFileType;
#endif


   derr( ">> add_to_existing_attr\t" << get_string_out_of_op(NewOprd) << " \n" );

   // Find the end of the Attr list.

   //   derr( "   Attr before addition\n" );
   //   print_attr( Attr );
   for ( OprdPtr = ShadowPtr = Attr->GetAttrOprdPtr(); OprdPtr != NULL;
         ShadowPtr = OprdPtr, OprdPtr = OprdPtr->GetNextOprdPtr() )
     {
       if ( OprdPtr->GetOprdType() == NewOprd->GetOprdType() &&
            OprdPtr->GetOprdRegNum() == NewOprd->GetOprdRegNum() &&
            OprdPtr->GetOprdFileType() == NewOprd->GetOprdFileType() )
         {
           //derr( "   already present in attribute " );
           //fprintf(stderr,"\t\tthis one:(%s).\n",get_string_out_of_op(OprdPtr)); 
           //derr( "<< add_to_existing_attr\n" ); 
           return;  // no change
         } // end if
     } // end for

   // At this point, OprdPtr should be NULL and ShadowPtr should point to
   // the last legoOprd in the list.
   if ( OprdPtr != NULL ) derr( "   ** OprdPtr not NULL!! **\n" );

#ifdef _LIVE_VAR_DEBUG_
   RegFileType = NewOprd->GetOprdFileType();
   if ( NewOprd->GetOprdType() == OT_MACRO )
     RegFileType = -1;
   cerr << "   Oprd to be added: RegFile " << RegFileType << ", RegNum "
        << NewOprd->GetOprdRegNum() << "\n";

   RegFileType = ShadowPtr->GetOprdFileType();
   if ( ShadowPtr->GetOprdType() == OT_MACRO )
     RegFileType = -1;
   cerr << "   ShadowPtr values: RegFile " << RegFileType << ", RegNum "
        << ShadowPtr->GetOprdRegNum() << "\n";
#endif

   OprdPtr = ShadowPtr->AddOprd();  // create new operand at end of list

   // Copy all legoOprd fields individually.
   copy_operand( NewOprd, OprdPtr );

#ifdef _LIVE_VAR_DEBUG_
   RegFileType = OprdPtr->GetOprdFileType();
   if ( OprdPtr->GetOprdType() == OT_MACRO )
     RegFileType = -1;
   cerr << "   Newly created Oprd values: RegFile "
        << RegFileType << ", RegNum " << OprdPtr->GetOprdRegNum() << "\n";
#endif

   //   derr( "   Attr after addition\n" );
   //   print_attr( Attr );

   derr( "<< add_to_existing_attr\n" );
   return;
} // end add_to_existing_attr

/*
 * create_new_attr
 *   Edge = edge on which to add live attribute
 *   Oprd = operand to add to attribute
 *   Proc = proc to whose dictionary to add edge
 *
 * Creates a new live attribute for Edge containing a copy of Oprd.
 */
static void create_new_attr( opEdges *Edge, legoOprd *Oprd, legoProc *Proc )
{
  legoOprd *NewOprd = new legoOprd();

  derr( ">> create_new_attr" << get_string_out_of_op(Oprd) << "\n" );

#ifdef _LIVE_VAR_DEBUG_
  attrs* Attr;
  int RegFileType;

  RegFileType = Oprd->GetOprdFileType();
  if ( Oprd->GetOprdType() == OT_MACRO )
    RegFileType = -1;
  cerr << "   Oprd to be added: RegFile " << RegFileType << ", RegNum "
       << Oprd->GetOprdRegNum() << "\n";
#endif

  // Copy all legoOprd fields individually.
  copy_operand( Oprd, NewOprd );

  // Add the attribute after creating a new operand copy.
  AddLiveAttribute( NewOprd, Edge, Proc );

#ifdef _LIVE_VAR_DEBUG_
   //   print_attr( FindLiveAttribute( Edge ) );
#endif

  derr( "<< create_new_attr\n" );
  return;
} // end create_new_attr

// ==========================================================================

/*
 * BB_live_out
 *   ProcPtr = proc containing RegionPtr
 *   RegionPtr = region for which to create live-out set
 *
 * out[B] = U (S succ. B) in[S]
 *
 * Performs the iterative live-out computation.
 */
void LiveVar_nm::BB_live_out( legoProc *ProcPtr, legoRegion *RegionPtr )
{
  regionList    *ChildrenList;
  legoRegion    *ChildRegionPtr;
  legoOp        *ExitOp;
  opEdges       *ControlEdge;
  SetInfo       Info;
  SetInfoTable::iterator LookUpIter, LookUpIterLoop, EndPtr;
  attrs *Attr;

  int           i, BBId = RegionPtr->GetRegionId(), ChildBBId, DoingNextSubBlock,SkipIt; 
  char          temp, *tempstr;
  legoOprd      *NewOprd;


  derr(">> BB_live_out: iteration #" << IterCount << ", BBId " << BBId << " subblock " << subblock << "\n");

  // Find the relevant exit op from this block/subblock.
  if ( RegionPtr->GetRegionType() == RT_BB )
        ExitOp = RegionPtr->GetExitOpsPtr()->GetOpPtr();  // easy!
  else if ( IS_BLOCK(RegionPtr->GetRegionType()) ){ 
                for ( i = 0, ExitOp = RegionPtr->GetEntryOpsPtr()->GetOpPtr();i < subblock; ExitOp = ExitOp->GetNextLink() ){  
                        if ( ExitOp->GetOutListPtr() != NULL ) i++;
                        if ( i == subblock ) break;  // count up to subblock
                } // end for
        } // end else
  else{ 
        LegoNonFatal ("LiveVar_nm::BB_live_out", "Passed non-block.");
        return;
  } // end else
  derr(">> Exit op is op " << ExitOp->GetOpId() << "\n");

  // The next subblock after this one is also a successor. We'll do
  // that one last; right now we aren't doing it.
  // Larin: It is NEVR done!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  // 
  DoingNextSubBlock = 0;

  ChildrenList = (regionList *) RegionPtr->GetChildren();

  // Iterate down children of RegionPtr.
  // If ChildrenList is immediately NULL, there's no children except for
  // possibly the next subblock. Try accessing that.
  if (ChildrenList != NULL)     ChildRegionPtr = (legoRegion *) ChildrenList->GetRegionPtr(); 
  else{ 
        if ( RegionPtr->GetRegionType() != RT_BB ){ 
                ChildRegionPtr          = RegionPtr;
                DoingNextSubBlock       = 1;
        } // end if
        // Else else, we're done.
        else    ChildRegionPtr = NULL;
  } // end else

  while (ChildRegionPtr != NULL){ 
        //    if ( (ChildRegionPtr->GetRegionType()) == RT_BB ) 
        //    if ( IS_BLOCK(ChildRegionPtr->GetRegionType()) ) 
      ChildBBId = ChildRegionPtr->GetRegionId();
      derr("   >> BBId " << ChildBBId << " being processed (as subblock? " << DoingNextSubBlock << ")\n" );

      // Immediately find the control edge leading from the exit of
      // the current block/subblock to ChildRegionPtr. If it's not there,
      // and we're on a subblock, skip it; the edge must come from another
      // exit op. This is the edge that will have its attribute updated.
      SkipIt = 0;
      if ( !DoingNextSubBlock ){ 
                ControlEdge = FindControlEdge (ExitOp, ChildRegionPtr->GetEntryOpsPtr()->GetOpPtr(), 1); 
                if ( ControlEdge == NULL ){ 
                        //fprintf(stderr,"Set to skipp this edge...\n");        
                        if ( subblock == 0 )
                                LegoNonFatal ("liveness", "Can't find control edge from op %d "  
                                                "to region %d.", ExitOp->GetOpId(),
                                                ChildRegionPtr->GetRegionId());
                        SkipIt = 1;
                } // end if
      } // end if
/* 
      else{
                fprintf(stderr,"\tCan we look for an edge from (%d)to (%d) in case of subblock? (%x).\n",
                        ExitOp->GetOpId(),
                        ChildRegionPtr->GetEntryOpsPtr()->GetOpPtr()->GetOpId(),
                        FindControlEdge (ExitOp, ChildRegionPtr->GetEntryOpsPtr()->GetOpPtr(), 1)); 
                // Larin 
                // try to find relevant ENTRY Op to the SUBREGION! 
                // 
                if(ExitOp->GetNextLink()){
                        fprintf(stderr,"\tOn other hand, an edge from (%d) to (%d) still cannot be found but make more sence.\n",
                                ExitOp->GetOpId(),
                                ExitOp->GetNextLink()->GetOpId()); 
                }  
      } 
*/ 

      // Do all entries that start with either:
      // <bbid>-     or
      // <bbid>/1-   or
      // <thisbbid>/<subblock+1>- if we're doing the next subblock
      if ( !DoingNextSubBlock ) {
                sprintf( LBHashKey, "%d-", ChildBBId );  // look between this ...
                sprintf( UBHashKey, "%d0", ChildBBId );  // ... and this!
      } // end if
      else {
                //sprintf( LBHashKey, "%d/%d-", BBId, subblock + 1 );  // or this ...
                //sprintf( UBHashKey, "%d/%d-", BBId, subblock + 2 );  // ... and this!
                sprintf( LBHashKey, "%d/%d-", BBId, subblock+1);  // or this ...
                sprintf( UBHashKey, "%d/%d0", BBId, subblock+1); 
      } // end else

//              fprintf(stderr,"\tDefined LBHashKey (%s),UBHashKey(%s).\n",LBHashKey,UBHashKey); 
/* 
        if(ChildBBId == 18){  
                for( LookUpIter = Table.begin();LookUpIter != Table.end();LookUpIter++ ) {
                        derr( "Key : " );
                        cerr.width(12);
                        derr( (*LookUpIter).first );
                        derr( " -- Def: " << (*LookUpIter).second.Def << ", Use: "
                                << (*LookUpIter).second.Use << ", LiveIn: "
                                << (*LookUpIter).second.LiveIn << ", LiveOut: "
                                << (*LookUpIter).second.LiveOut << "\n" );
                }
        } 
        else{
                for( LookUpIterLoop = Table.lower_bound(LBHashKey);
                        ((LookUpIterLoop != (Table.lower_bound(UBHashKey))) &&
                        (LookUpIterLoop != Table.end())) &&
                        !SkipIt;
                        LookUpIterLoop++){ 

                        derr( "Key : " );
                        cerr.width(12);
                        derr( (*LookUpIter).first );
                        derr( " -- Def: " << (*LookUpIter).second.Def << ", Use: "
                                << (*LookUpIter).second.Use << ", LiveIn: "
                                << (*LookUpIter).second.LiveIn << ", LiveOut: "
                                << (*LookUpIter).second.LiveOut << "\n" ); 
                } 
        } 
*/ 

      // Run through every hashtable entry that is in the range of keys
      // we're looking for.
      for( LookUpIterLoop = Table.lower_bound(LBHashKey);
           ((LookUpIterLoop != (Table.lower_bound(UBHashKey))) &&
            (LookUpIterLoop != Table.end())) &&
             !SkipIt;
           LookUpIterLoop++)
        {
/* 
                fprintf(stderr,"\tLooking at the entry: "); 
                derr( (*LookUpIterLoop).first );
                derr( " -- Def: " << (*LookUpIterLoop).second.Def << ", Use: "
                                << (*LookUpIterLoop).second.Use << ", LiveIn: "
                                << (*LookUpIterLoop).second.LiveIn << ", LiveOut: "
                                << (*LookUpIterLoop).second.LiveOut << "\n" ); 
*/ 

          // Check that it's not from a subblock of a superblock
          // numbered 2 or later (i.e., it must be <bbid>/1-...).
          //tempstr = strstr ( (*LookUpIterLoop).first, "/");
          //if ( tempstr != NULL ) {
            // It's a superblock.
                // Larin 
                //fprintf(stderr,"\tthe tempstr (%s).\n",tempstr); 
                //if ( tempstr [ 1 ] != '1' || tempstr [ 2 ] != '-' ) continue;
          //} // if

          if ((*LookUpIterLoop).second.LiveIn){ 
              // OK, we found something live-in. Let's keep a pointer to it.
              //fprintf(stderr,"\tFound live-in .\n"); 
              SetInfoTable::iterator TmpIter = LookUpIterLoop;

              // Check whether it's marked as live-out already from RegionPtr.
              // If not, do so, adding a table entry if needed.
              ReadHashKey       = (*LookUpIterLoop).first;
              ReadHashKey       = strchr(ReadHashKey, '-');  // pop off end
              if ( subblock == 0 )  // create new front
                        sprintf( ReadHashPart1, "%d", BBId );
              else
                        sprintf( ReadHashPart1, "%d/%d", BBId, subblock );
              ReadHashKey = strcat(ReadHashPart1,ReadHashKey);  // merge

              //fprintf(stderr,"\tMerge (%s).\n",ReadHashKey);  

              LookUpIter        = Table.find( ReadHashKey );
              EndPtr            = Table.end();
              if ( LookUpIter == EndPtr || (*LookUpIter).second.LiveOut != TRUE ){ 
                  // The value is live-in to the child block.
                  derr( "   Live-out (" << ReadHashKey << ") from region "
                        << RegionPtr->GetRegionId() << " to region "
                        << ChildRegionPtr->GetRegionId() << "\n" );

                  // Make a new table entry if needed.
                  if ( LookUpIter == EndPtr )
                    {
                      WriteHashKey = new char[HASH_KEY_SIZE];   
                      strcpy(WriteHashKey, ReadHashKey);
                      Info.Use = FALSE;
                      Info.Def = FALSE;
                      Info.LiveIn = FALSE;
                      Info.LiveOut = TRUE;
                      Info.Oprd = (*TmpIter).second.Oprd;
                      Table[ WriteHashKey ] = Info;
                      derr("   Table entry added\n");
                    } // end if
                  else
                    {
                      (*LookUpIter).second.LiveOut = TRUE;
                      derr("   HashKey " << ReadHashKey << " updated for LiveOut\n"); 
                    } // end else

                  //              ChangeBit = TRUE;  // a change occurred!
              } // end if
              //else    fprintf(stderr,"\tMissing...\n"); 

              // Set a pointer to the operand that is live-out.
              NewOprd = (*TmpIter).second.Oprd;

              //fprintf(stderr,"\tCreated new operand (%s).\n",get_string_out_of_op(NewOprd)); 

              // Possibly create a live attribute for this control edge.
              // First, see if a live-ness attr exists. If yes, add
              // this regid to the end. If no, create a new attr & add this
              // regid.
              // (This must be here, instead of above when a live-out is
              //  first discovered, so that if a value is live-out along
              //  multiple edges, each one gets its chance to have its
              //  live attribute updated.)

              // Also, we can create a hash table representation of the
              // edge information (EdgeInfo), as well or instead. That will
              // be made as a postpass.
              if ( !DoingNextSubBlock ){   // o/w, no edge to bother with
                  Attr = FindLiveAttribute( ControlEdge );
                  if ( Attr != NULL ) // exists
                    add_to_existing_attr( Attr, NewOprd );
                  else
                    create_new_attr( ControlEdge, NewOprd, ProcPtr );
                  derr( "   Edge " << ControlEdge->GetEdgeId() <<
                        " updated\n" );
              } // end if
/* 
              else{     // Larin 
                  if(ControlEdge)       fprintf(stderr,"\tSuppose to add the new operand to the edge (%d).\n",ControlEdge->GetEdgeId());  
                  else                  fprintf(stderr,"\tThere is no edge to add new operand to.\n"); 
              } 
*/ 
          } // if LiveIn
        } // for (hashtable items in range)
      //     // if IS_BLOCK

      // Move to next child if we can.
      if ( ChildrenList != NULL )       ChildrenList = ChildrenList->GetNextListPtr(); 

      // If not at end of children list, set ChildRegionPtr.
      if ( ChildrenList != NULL )       ChildRegionPtr = (legoRegion *) ChildrenList->GetRegionPtr(); 
      // Else, if we haven't done the next subblock yet, set it up.
      else{ 
                if ( !DoingNextSubBlock && RegionPtr->GetRegionType() != RT_BB ){ 
                        ChildRegionPtr  = RegionPtr;
                        DoingNextSubBlock = 1;
                } // end if
                // Else else, we're done.
                else ChildRegionPtr     = NULL;
      } // end else
      //fprintf(stderr,"   << done with the block.\n"); 
  } // while

  derr("<< BB_live_out\n" );
  return;
} // end LiveVar_nm::BB_live_out

/*
 * BB_live_in
 *   ProcPtr = proc containing RegionPtr
 *   RegionPtr = region for which to create live-in set
 *
 * in[B] = use[B] U (out[B] - def[B])
 *
 * Performs the iterative live-in computation.
 */
void LiveVar_nm::BB_live_in( legoProc *ProcPtr, legoRegion *RegionPtr )
{
  SetInfoTable::iterator LookUpIter;  
  int BBId = RegionPtr->GetRegionId();
  bool Out_Not_Def, old_LiveIn;

  derr(">> BB_live_in: iteration #" << IterCount << ", BBId " << BBId << " subblock " << subblock << "\n");

  // Make up hash-key ranges for operands in the block/subblock.
  if ( subblock == 0 ) { // doing basic block
    sprintf( LBHashKey, "%d-", BBId );  
    sprintf( UBHashKey, "%d0", BBId );  
  } // end if
  else {
    sprintf( LBHashKey, "%d/%d-", BBId, subblock );
    sprintf( UBHashKey, "%d/%d-", BBId, subblock + 1 );
  } // end else

  // Iterate over each operand in the block/subblock.
  for( LookUpIter = Table.lower_bound(LBHashKey);
       //       ((LookUpIter != Table.upper_bound(UBHashKey)) &&
       ((LookUpIter != Table.lower_bound(UBHashKey)) &&
        (LookUpIter != Table.end()));
       LookUpIter++){ 
      // First find whether it's live-out of this block/subblock but
      // not defined here.
        //fprintf(stderr,"Iterating through each oprd of the subblock .\n"); 
        if( ((*LookUpIter).second.LiveOut == TRUE) && ((*LookUpIter).second.Def == FALSE) ) 
                Out_Not_Def     = TRUE;
        else    Out_Not_Def     = FALSE;

      // Now, perform the iteration and check for a change.
        old_LiveIn = (*LookUpIter).second.LiveIn;
        (*LookUpIter).second.LiveIn     = ((*LookUpIter).second.Use || Out_Not_Def); 
        if ((*LookUpIter).second.LiveIn != old_LiveIn){ 
                ChangeBit = TRUE;
                derr("   HashKey " << (*LookUpIter).first << " updated for LiveIn\n"); 
        } // end if
      //      if ( (*LookUpIter).second.LiveIn != ((*LookUpIter).second.Use ||
      //                                         Out_Not_Def) )
      //        {
      //          (*LookUpIter).second.LiveIn =
      //            ((*LookUpIter).second.Use || Out_Not_Def);
      //          ChangeBit = TRUE;
      //          derr("   HashKey " << (*LookUpIter).first <<
      //               " updated for LiveIn\n");
      //        } // end if
  } // end for
  
  derr("<< BB_live_in\n" );
  return;
} // end LiveVar_nm::BB_live_in

// ==========================================================================

/*
 * Process
 *   RegionPtr = region for which to compute liveness
 *   ProcPtr = proc containing RegionPtr
 *
 * Computes the live-out and live-in sets for RegionPtr if it is a
 * block, or for the regions within RegionPtr otherwise. This function
 * represents one iteration of the overall iterative algorithm, with
 * an implicit hierarchical ordering (not necessarily the fastest).
 */
void LiveVar_nm::Process ( legoRegion *RegionPtr, legoProc *ProcPtr )
{
  int BBId, RegionCount, NumSubRegions;

  if(IS_BLOCK (RegionPtr->GetRegionType())){ 
        BBId    = RegionPtr->GetRegionId();
        derr( "BB with BBId: " << BBId << "\n");

        // Count the number of subregions (subblocks) if RegionPtr is a
        // superblock (or hyperblock).
        NumSubRegions = 0;
        if(RegionPtr->GetRegionType() != RT_BB){ 
                legoOp *op;

                for(op= RegionPtr->GetEntryOpsPtr()->GetOpPtr();op!=NULL;op=op->GetNextLink()) 
                        if(op->GetOutListPtr())         NumSubRegions++;
                derr(">> Contains " << NumSubRegions << " subblocks.\n");
        } // end if
        // Loop over each subblock, from the bottom up, for superblocks;
        // just do the basic block otherwise.
        if(RegionPtr->GetRegionType()==RT_BB){ 
                subblock = 0;
                BB_live_out( ProcPtr, RegionPtr );
                BB_live_in( ProcPtr, RegionPtr );
        } // end if
        else for(subblock = NumSubRegions; subblock>0;subblock--){      // Larin >0;  
                //fprintf(stderr,"\tHere processing subblock (%d).\n",subblock); 
                BB_live_out( ProcPtr, RegionPtr );
                BB_live_in( ProcPtr, RegionPtr );
        } // end else
  } // end if
  else{ 
        RegionCount     = RegionPtr->GetCount();
        for (int i=0;i<RegionCount;i++)
                Process ( (legoRegion *) RegionPtr->GetItem ( i ), ProcPtr );
  } // end else

  return;
} // end LiveVar_nm::Process

/*
 * analyze
 *   RegionPtr = region on which to work (must not be op-holding)
 *   ProcPtr = proc containing region
 *
 * Perform liveness analysis on RegionPtr. If RegionPtr is a block,
 * finds defs and uses, then quits. If RegionPtr is not a block but
 * not a proc, finds defs and uses of its subregions, then quits.
 * If RegionPtr is a proc, finds defs and uses of its subregions,
 * then cranks the iterative algorithm.
 */
// analyze: perform live-out analysis on ProcPtr
void LiveVar_nm::analyze( legoRegion *RegionPtr, legoProc *ProcPtr )
{
  legoRegion *SubRegionPtr;
  legoOp *OpPtr;
#ifdef _LIVE_VAR_DEBUG_
  SetInfoTable::iterator LookUpIter;
#endif
  
  int j, k, RegionCount, OpCount, BBId;

  // Initialize a few things if we are just starting.
  if ( RegionPtr->GetRegionType() == RT_PROC )
    {
      //      Table.map();
      // wah 3/24/98
      Table = SetInfoTable();
      ReadHashKey = new char[ HASH_KEY_SIZE ];
      ReadHashPart1 = new char[ HASH_PART_SIZE ];
      ReadHashPart2 = new char[ HASH_PART_SIZE ];
      ReadHashPart3 = new char[ HASH_PART_SIZE ];
      LBHashKey = new char[ HASH_KEY_SIZE ];
      UBHashKey = new char[ HASH_KEY_SIZE ];
      delete EdgeInfo;
    } // end if

  RegionCount = RegionPtr->GetCount();
  if ( RegionPtr == (legoRegion *) ProcPtr )
    derr( RegionCount << " Region(s) in Proc " << ProcPtr->GetProcName()
          << "\n");

  // Go over each subregion of the region.
  for ( j = 0; j < RegionCount; j++)
    {
      SubRegionPtr = (legoRegion *) RegionPtr->GetItem( j ); 

      // If it's a block, do defs and uses for its ops.
      if ( IS_BLOCK (SubRegionPtr->GetRegionType()) )
        {
          BBId = SubRegionPtr->GetRegionId();
          derr( "BB number " << (j + 1) << ", BBId: " << BBId << "\n");

          OpCount = SubRegionPtr->GetCount();
          derr( OpCount << " Op(s) in BB number " << (j + 1) << "\n");
          subblock = 1;  // on first subblock

          // Do defs and uses for each op in the block.
          for ( k = 0; k < OpCount; k++)
            {
              OpPtr = (legoOp *) SubRegionPtr->GetItem( k );
              derr( "Op number " << (k + 1) << ", OpId: " << OpPtr->GetOpId()
                    << "\n");
              BB_uses(OpPtr, BBId);
              BB_defs(OpPtr, BBId);
              // Increment subblock if just saw branch.
              // Larin 
              if (OpPtr->GetOutListPtr() != NULL){
                //fprintf(stderr,"\tDetected Subblock.\n");     
                subblock++;
              } 
            } // end for
        } // end if
      else
        {
          // Do defs and uses for all the subregions.
          //fprintf(stderr,"\tThis is subregion.\n"); 
          analyze ( SubRegionPtr, ProcPtr );
        } // end else
    } // end for

  if ( RegionPtr != (legoRegion *) ProcPtr)
    return;  // only proceed if whole proc is done
  derr( "** Defs/uses complete **\n" );

  // Here, we know we're on a proc. Set up for cranking the iteration.
  ChangeBit = TRUE;
  IterCount = 1;
  while (ChangeBit == TRUE)
    {
      ChangeBit = FALSE;
      for ( j = 0; j < RegionCount; j++)
        {
          SubRegionPtr = (legoRegion *) RegionPtr->GetItem( j );
          Process ( SubRegionPtr, ProcPtr );
        } // end for
      IterCount++;
    } // end while

  // We're done.
#ifdef _LIVE_VAR_DEBUG_
  for( LookUpIter = Table.begin();LookUpIter != Table.end();LookUpIter++ ) {
    derr( "Key : " );
    cerr.width(12);
    derr( (*LookUpIter).first );
    derr( " -- Def: " << (*LookUpIter).second.Def << ", Use: "
          << (*LookUpIter).second.Use << ", LiveIn: "
          << (*LookUpIter).second.LiveIn << ", LiveOut: "
          << (*LookUpIter).second.LiveOut << "\n" );
  }
#endif
  if ( CreateTable )
    CollectEdgeInfo ( ProcPtr );

  delete [] ReadHashKey;
  delete [] ReadHashPart1;
  delete [] ReadHashPart2;
  delete [] ReadHashPart3;
  //  delete [] WriteHashKey;
  //  delete [] WriteHashPart1;
  //  delete [] WriteHashPart2;
  //  delete [] WriteHashPart3;
  delete [] LBHashKey;
  delete [] UBHashKey;
  Table.erase( Table.begin(), Table.end() );
  Table.~map();

  return;
} // end LiveVar_nm::analyze

/*
 * analyze
 *   modulePtr = legoModule to analyze
 *
 * Performs live analysis on an entire legoModule.
 */
void LiveVar_nm::analyze( legoModule *modulePtr )
{ 
  legoProc *ProcPtr;
  int i, ProcCount;
  
  ProcCount = modulePtr->GetCount();
  derr( ProcCount << " Proc(s) in legoModule\n");

  for ( i = 0; i < ProcCount; i++ )
    analyze( ( legoProc *)  modulePtr->GetItem( i ),
             ( legoProc *)  modulePtr->GetItem( i ));
}

// deleteedgeinfo: remove list of operands for given edge (if 0, all!)
void LiveVar_nm::deleteedgeinfo ( int edgeid )
{
  if ( EdgeInfo == NULL ) return;
  if ( edgeid != 0 ) {
    //    oprdl = EdgeInfo->Lookup ( edgeid );
    //    if ( ! (EdgeInfo->NotFound()) ) delete oprdl;
    EdgeInfo->Delete ( edgeid );
    return;
  }

  //  for ( EdgeInfo->Start(); ! (EdgeInfo->AtEnd()); EdgeInfo->Next() ) {
    //    oprdl = EdgeInfo->LookupCurrent();
    //    if ( ! (EdgeInfo->NotFound()) ) delete oprdl;
  //  }
  EdgeInfo->DeleteAll();
  return;
}

/*
 * CollectEdgeInfo
 *   ProcPtr = procedure for which to collect information
 *
 * Creates a hashtable representation of the live attribute information
 * found in ProcPtr.
 */
void LiveVar_nm::CollectEdgeInfo ( legoProc *ProcPtr )
{
  opEdges *edge;
  attrs *liveattr;
  //  oprdList *liveoprds, *oprdl;
  legoOprd *oprd;

  if ( !CreateTable ) return;

  if ( EdgeInfo == NULL )
    EdgeInfo = new legoHash <int, legoOprd *, legoHash_lt_int>;
  else
    deleteedgeinfo (0);

  for ( edge = ProcPtr->GetEdgeDictionary(); edge != NULL;
        edge = edge->GetNextOpEdgePtr() ) {
    liveattr = FindLiveAttribute (edge);
    if ( liveattr == NULL ) continue;

    //    liveoprds = oprdl = NULL;
    //    for ( oprd = liveattr->GetAttrOprdPtr(); oprd != NULL;
    //    oprd = oprd->GetNextOprdPtr() ) {
    //      if ( oprdl != NULL ) {
    //  oprdl->SetNextListPtr ( new oprdList );
    //  oprdl = oprdl->GetNextListPtr();
    //      }
    //      else {
    //  liveoprds = oprdl = new oprdList;
    //      }
    //
    //      oprdl->SetOprdPtr ( oprd );
    //    }

    oprd = liveattr->GetAttrOprdPtr();
    //    if ( liveoprds != NULL )
    if ( oprd != NULL )
      EdgeInfo->Set ( edge->GetEdgeId(), oprd );
  }

  return;
} // end CollectEdgeInfo


/*
 * LiveVariables
 *   proc = procedure to analyze
 *   maketable = whether to create hashtable of info for return
 *   returns: hashtable of liveness information
 *
 * Performs live variable analysis on procedure proc. The information is
 * stored in live attributes directly in the IR, and also returned in
 * tabular form.
 */
legoHash <int, legoOprd *, legoHash_lt_int> *
LiveVariables_not_mine (legoProc *proc, int maketable = 0)
{
  legoHash <int, legoOprd *, legoHash_lt_int> *LiveInfo;
  LiveVar_nm *live = new LiveVar_nm;
  if (maketable) live->SetCreateTable (TRUE);
  else live->SetCreateTable (FALSE);

  live->analyze (proc, proc);

  LiveInfo = live->GetEdgeInfo();
  live->SetEdgeInfo ( NULL );
  delete live;
  return LiveInfo;
} // end LiveVariables

---