live.C

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.
// 11/20/98 MDJ: Fixed memory leak associated with WriteHashKeys. Need to 
//               delete the WriteHashKeys we allocated before erasing HashTable
// 12/16/98 MDJ: Fixed BB_uses to inlcude BRL MACRO sources used for parameter 
//               passing.
// Mon Jul 20 12:35:19 EDT 1998 Larin:  Changed the BB_live_out. (HB bug)  

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

// 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 object.
 */
inline void LiveVar::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 object.
 */
inline void LiveVar::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 object.
 */
inline void LiveVar::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 object.
 */
inline void LiveVar::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.
 */

/********************************************
In the case of the predicate associated 
with the register, we can take conservative 
approach by saying that predicate guarded regs
will always use instr. but not kill or define 
the regs : Sau
This step is also taken in "CompleteLiveness"
*********************************************/
void LiveVar::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" );

  if(OpPtr->GetPredOprdPtr() != NULL &&
        OpPtr->GetPredOprdPtr()->GetOprdType() == OT_REG &&
        OpPtr->GetPredOprdPtr()->GetOprdFileType() == FT_PR &&
        OpPtr->GetPredOprdPtr()->GetOprdRegNum() != 0)
        return;
  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
          
          // Also check predicate registers if filetype is FT_PR
          if ((NonDef == 0) && (OprdPtr->GetOprdFileType() == FT_PR)) {
            for ( WalkOpPtr = OpPtr->GetPrevLink(); WalkOpPtr != NULL &&
                 WalkOpPtr->GetOutListPtr() == NULL;
                 WalkOpPtr = WalkOpPtr->GetPrevLink() )  // walk up from OpPtr
              {
                for ( WalkOprdPtr = WalkOpPtr->GetPredOprdPtr();
                     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->IsBRLOp() &&
          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::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::BB_uses( legoOp *OpPtr, int BBId )
{
  legoOprd *OprdPtr, *WalkOprdPtr;
  legoOp *WalkOpPtr;
  SetInfo Info;
  SetInfoTable::iterator LookUpIter, EndPtr;
  attrs *a;

  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;
                  /**************************************
                  Check if the walkOpPtr has a predicate
                  associated with it, if yes don't
                  treat the oprd as a non-use. Rathter
                  we should take a conservative approach
                  and say it as a "use" : Sau
                  ***************************************/
                  if(WalkOpPtr->GetPredOprdPtr() != NULL &&
                   WalkOpPtr->GetPredOprdPtr()->GetOprdType() == OT_REG &&
                   WalkOpPtr->GetPredOprdPtr()->GetOprdFileType() == FT_PR &&
                   WalkOpPtr->GetPredOprdPtr()->GetOprdRegNum() != 0)
                   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->IsBRLOp() &&
                   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

  // mdj - 8/11/99: Don't forget about Predicate Sources
  for (OprdPtr = OpPtr->GetPredOprdPtr(); OprdPtr != NULL;
       OprdPtr = OprdPtr->GetNextOprdPtr() )  // loop through pred 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
              
              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

  // mdj - 12/16/98
  // Bill didn't understand BRL parameter sources at the time. 
  // Need to include these now
  // mdj - 3/29/98 
  // We need to assume that BRLs use INT_P*'s, FLT_P*'s, DBL_P*'s because 
  // recursive subroutine calls may use more parameters than the original call 
  /*
  if ( OpPtr->GetOpcode() == BRL ) {
//    for (int regid = INT_P1; regid <= INT_P4; regid++) {
    for (int regid = INT_P1; regid <= DBL_P2; regid++) {
      // create new operands for these, they may not all exist at this time

      OprdType = OT_MACRO;
      RegNum = regid;
      // this one is always a 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;
          // We need to create a new operand here because this one doesn't 
          // actually exist yet for this procedure
          OprdPtr = new legoOprd();
          OprdPtr->SetOprdType(OT_MACRO);
          OprdPtr->SetOprdRegNum(regid);
          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 (OpPtr->IsBRLOp()) 
  {
    int StartOpReg;
    int EndOpReg;
    if(OpPtr->GetOpcodePtr() != NULL)
    {
        // Get the number of outgoing Ops from the 
        // Alloc instr, The BRL Ops will not be present 
        // in the Leaf procedures
        //HZ: make sure proc is a proc
        legoProc * proc;
        legoRegion * reg_t = ((legoBB *)
                OpPtr->GetParentBlockPtr())->GetParentPtr();
        if(reg_t->GetRegionType() == RT_PROC)
            proc = (legoProc *)reg_t;
        else
        {
            reg_t = reg_t->GetParentPtr();
            proc = (legoProc *) reg_t;
        }
        assert(reg_t->GetRegionType() == RT_PROC);
        //legoProc *proc = (legoProc *)((legoBB *) OpPtr->GetParentBlockPtr())->GetParentPtr();
    
        if(proc == NULL)
        {
          LegoNonFatal ("LiveVar->BBuses", "This parent Proc is NULL\n");
          exit (-1);
        }
    
        StartOpReg = FindFirstOutGoingReg(proc);
        EndOpReg = FindLastOutGoingReg(proc);
    }
    else
    {
        StartOpReg = INT_P1;
        EndOpReg = DBL_P2; 
    }
    for (int regid = StartOpReg; regid <= EndOpReg; regid++) {
      // create new operands for these, they may not all exist at this time

      if(OpPtr->GetOpcodePtr() != NULL)
      {
        OprdType = OT_REG;
        RegFileType = FT_GPR;
      }
      else
      {
        OprdType = OT_MACRO;
        // this one is always a MACRO
        RegFileType = -1;  // pseudo-filetype
      }
      
      RegNum = regid;
      
      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->IsBRLOp() &&
              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;
          // We need to create a new operand here because this one doesn't 
          // actually exist yet for this procedure
          OprdPtr = new legoOprd();
          if(OpPtr->GetOpcodePtr() != NULL)
            {
             OprdPtr->SetOprdType(OT_REG);
             OprdPtr->SetOprdFileType(FT_GPR);
             OprdPtr->SetValid(1);
             OprdPtr->SetOprdRegType(RT_R);
             OprdPtr->SetOprdDataType(DT_I);
             OprdPtr->SetOprdRegStyle(RS_STATIC);
   
            }
          else
             OprdPtr->SetOprdType(OT_MACRO);
          OprdPtr->SetOprdRegNum(regid);
          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
    }
  }
  
  // mdj - 3/24/99
  // Need to make sure that subroutine return parameters are seen as 
  // live-out starting at each RTS for the subroutine. 
  /* if ( OpPtr->GetOpcode() == RTS ) {
    OprdType = OT_MACRO;
    for (RegNum = INT_RET; RegNum <= DBL_RET; RegNum++) {
      // this one is always a 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 ) {
        
        // 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;
            // We need to create a new operand here because this one doesn't 
            // actually exist yet for this procedure
            OprdPtr = new legoOprd();
            if(OpPtr->GetOpcodePtr() != NULL)
            {
             OprdPtr->SetOprdType(OT_REG);
             OprdPtr->SetOprdFileType(FT_GPR);
             OprdPtr->SetValid(1);
             OprdPtr->SetOprdRegType(RT_R);
             OprdPtr->SetOprdDataType(DT_I);
             OprdPtr->SetOprdRegStyle(RS_STATIC);
   
            }
            else
             OprdPtr->SetOprdType(OT_MACRO);
            OprdPtr->SetOprdRegNum(RegNum);
            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 ( OpPtr->IsRETOp()) {
    int StartOpReg;
    int EndOpReg;
    if(OpPtr->GetOpcodePtr() != NULL)
    {
        OprdType = OT_REG;
        RegFileType = FT_GPR;
        StartOpReg = 8;
        EndOpReg = 11;
    }
    else
    {
        OprdType = OT_MACRO;
        RegFileType = -1;  // pseudo-filetype
        StartOpReg = INT_RET;
        EndOpReg = DBL_RET;
    }
    for (RegNum = StartOpReg; RegNum <= EndOpReg; RegNum++) {
      // this one is always a MACRO
     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" );
              // for IA64 code we have become conservative,
              // so all the o/p regs are used  
              if(OpPtr->GetOpcodePtr() == NULL)
              NonUse = 1;
              break;
            } // end for
          // For BRLs, try to match the return macro as well.
          if ( !NonUse && WalkOpPtr->IsBRLOp() &&
              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 ) {
        
        // 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;
            // We need to create a new operand here because this one doesn't 
            // actually exist yet for this procedure
            OprdPtr = new legoOprd();
            if(OpPtr->GetOpcodePtr() != NULL)
            {
             OprdPtr->SetOprdType(OT_REG);
             OprdPtr->SetOprdFileType(FT_GPR);
             OprdPtr->SetValid(1);
             OprdPtr->SetOprdRegType(RT_R);
             OprdPtr->SetOprdDataType(DT_I);
             OprdPtr->SetOprdRegStyle(RS_STATIC);
   
            }
            else
             OprdPtr->SetOprdType(OT_MACRO);
            OprdPtr->SetOprdRegNum(RegNum);
            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
      }
    }
    // For IA64 we also need to check the "b0"
    // present as a source to the "br.ret..."
    legoOprd *btr;
    btr = OpPtr->GetSrcOprdPtr();
    if(btr->GetOprdFileType() == FT_BTR &&
        btr->GetOprdRegNum() == 0) {
    OprdType = OT_REG;
    RegFileType = FT_BTR;
    RegNum = 0;
    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.
      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 ( 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
            if(NonUse)
            break;
         }
         if ( !NonUse ) {
        
        // 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;
            // We need to create a new operand here because this one doesn't 
            // actually exist yet for this procedure
            OprdPtr = new legoOprd();
            if(OpPtr->GetOpcodePtr() != NULL)
            {
             OprdPtr->SetOprdType(OT_REG);
             OprdPtr->SetOprdFileType(FT_BTR);
             OprdPtr->SetValid(1);
             OprdPtr->SetOprdRegType(RT_R);
             OprdPtr->SetOprdDataType(DT_I);
             OprdPtr->SetOprdRegStyle(RS_STATIC);
            }
            else
            OprdPtr->SetOprdType(OT_MACRO);
            OprdPtr->SetOprdRegNum(RegNum);
            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
      }
    }    
  }
  
  derr( "<< BB_uses\n" );
} // end LiveVar::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 )
{
    if(Src->GetOprdType() != OT_REG)
    {
        assert(0); //HZ: not being able to process the literal string type of
                        //oprd.
    }
   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\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\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\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::BB_live_out( legoProc *ProcPtr, legoRegion *RegionPtr )
{
  regionList *ChildrenList;
  legoRegion *ChildRegionPtr;
  legoOp *ExitOp;
  opList *ExitOps; 
  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");

  // Ignore empty blocks left behind from Multi-Way branch formation. These 
  // blocks are no longer connected to any program control flow and will be 
  // removed after the proc is scheduled (they are not removed immediately 
  // because that fucks up region_ptrs used for tree-traversal scheduling).
  if (RegionPtr->GetCount() == 0)
    return; 

  // The next subblock after this one is also a successor. We'll do
  // that one last; right now we aren't doing it.
  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\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 )
        {
          // Find the relevant exit op from this block/subblock.
          if ( RegionPtr->GetRegionType() == RT_BB ) {
            
            // Because of Multi-Way branching, BB may now have more than one 
            // ExitOp. Need to find the appropriate ControlEdge/ExitOp pair
            
            for (ExitOps = RegionPtr->GetExitOpsPtr();
                 ExitOps != NULL; 
                 ExitOps = ExitOps->GetNextListPtr()) {
              ExitOp = ExitOps->GetOpPtr();
              ControlEdge = FindControlEdge (ExitOp, ChildRegionPtr->
                                             GetEntryOpsPtr()->GetOpPtr(), 1);
              if (ControlEdge != NULL) {
                break; 
              }
            }
          }
          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
              ControlEdge = FindControlEdge (ExitOp, ChildRegionPtr->
                                             GetEntryOpsPtr()->GetOpPtr(), 1);
            } // end else
          else
            {
              LegoNonFatal ("LiveVar::BB_live_out", "Passed non-block.");
              return;
            } // end else
          derr(">> Exit op is op " << ExitOp->GetOpId() << "\n");

          if ( ControlEdge == NULL )
            {
              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

      // 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!
      } // end else

      // 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++)
        {

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

          if ((*LookUpIterLoop).second.LiveIn)
            {
              // OK, we found something live-in. Let's keep a pointer to it.
              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

              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

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

              // 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
            } // 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
    } // while

  derr("<< BB_live_out\n" );
  return;
} // end LiveVar::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::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");

  // Ignore empty blocks left behind from Multi-Way branch formation. These 
  // blocks are no longer connected to any program control flow and will be 
  // removed after the proc is scheduled (they are not removed immediately 
  // because that fucks up region_ptrs used for tree-traversal scheduling).
  if (RegionPtr->GetCount() == 0)
    return; 

  // 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.
      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::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::Process ( legoRegion *RegionPtr, legoProc *ProcPtr )
{
  int BBId, RegionCount, NumSubRegions;

  if ( IS_BLOCK (RegionPtr->GetRegionType()) )
    {
      BBId = RegionPtr->GetRegionId();
      //    derr( "BB number " << (j + 1) << ", 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() != NULL) NumSubRegions++;
          } // end for
          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--)
        {
          BB_live_out( ProcPtr, RegionPtr );
          BB_live_in( ProcPtr, RegionPtr );
        } // end else
    } // end if
  else
    {
      RegionCount = RegionPtr->GetCount();
      // Try this backwards in interest of compile time
      // LiveVars uses 'BACKWARDS' equations
      for ( int i = (RegionCount - 1); i >= 0; i--)
//      for (int i = 0; i < RegionCount; i++)
        Process ( (legoRegion *) RegionPtr->GetItem ( i ), ProcPtr );
    } // end else

  return;
} // end LiveVar::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::analyze( legoRegion *RegionPtr, legoProc *ProcPtr )
{
  legoRegion *SubRegionPtr;
  legoOp *OpPtr;
  SetInfoTable::iterator LookUpIter;
  
  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.
              if (OpPtr->GetOutListPtr() != NULL) subblock++;
            } // end for
        } // end if
      else
        {
          // Do defs and uses for all the subregions.
          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;
      // Try this backwards in interest of compile time
      // LiveVars uses 'BACKWARDS' equations
      for ( j = (RegionCount - 1); j >= 0; j--)
        {
          SubRegionPtr = (legoRegion *) RegionPtr->GetItem( j );
          Process ( SubRegionPtr, ProcPtr );
        } // end for
      derr ("Iteration number " << IterCount << "\n");
      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;
  // mdj - 11/20/98
  // delete the WriteHashKeys that we allocated or else they leak
  for( LookUpIter = Table.begin();LookUpIter != Table.end();LookUpIter++ ) {
    delete ((*LookUpIter).first);
  }
  Table.erase( Table.begin(), Table.end() );

  return;
} // end LiveVar::analyze

/*
 * analyze
 *   modulePtr = legoModule to analyze
 *
 * Performs live analysis on an entire legoModule.
 */
void LiveVar::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::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::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 (legoProc *proc, int maketable = 0)
{
  legoHash <int, legoOprd *, legoHash_lt_int> *LiveInfo;
  LiveVar *live = new LiveVar;
  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

---