list_scheduler.C

Go to the documentation of this file.

#include <iostream.h>
#include <fstream.h>
#include <time.h>
#include <stl.h>
#include "lego.H"
#include "legoUtil.H"
#include "legoAn.H"
#include "scheduling_utilities.H"
#include "list_scheduler.H"
#include "lmdes.h"
#include "RU_manager.h"
#include "l_alloc_new.h"


/* Debugging support, courtesy of Sumedh */ 
//   #define temperr(_s_)  cerr << _s_ 
   #define temperr(_s_) 
//   #define dperr(_s_)  cerr << _s_ 
   #define dperr(_s_) 
//   #define ddderr(_s_)  cerr << _s_ 
   #define ddderr(_s_) 
//#define _LIST_SCHEDULER_DEBUG_ 
#if defined (_LIST_SCHEDULER_DEBUG_) 
   #define derr(_s_)  cerr << _s_ 
   #define dderr(_s_)  cerr << _s_ 
#else 
   #define derr(_s_) 
   #define dderr(_s_) 
#endif 


#define       YES     1
#define       NO      0

extern L_Alloc_Pool    *Operand_ready_pool;
chains* Chains;
int MaxRegNum;
int MaxOpId;
int ReDoLiveVarsNextTreegion = FALSE;
int live_call_number = 1;
int rdef_call_number = 1;
time_t now, then;
double elapsed, elapsed_c;
int *operand_ready_times;
int *true_operand_ready_times;
int *true_dsld_operand_ready_times; 
int *dsld_operand_ready_times; 
int ReDoLiveVarsAfterGlobal = FALSE;
int MergeProblemDuringGlobal = FALSE;
extern int dom_parallel_ops, copy_ops_added, speculated_ops;
extern int liveness_renamed_ops, falsedep_renamed_ops, combine_renamed_ops;
extern int liveness_calls, rdef_calls; 
extern int downward_motion_ops, unspeculated_ops, unspeculated_pbr_ops, dead_ops;
extern double downward_dynamic_op_reduction, combine_dynamic_op_reduction;
extern double speculative_dynamic_op_increase, multiway_dynamic_op_reduction;
extern double copy_dynamic_op_increase;
extern int total_branch_multiops, total_branch_ops, blocks_removed; 
int temp_dom_op_count=0;

//HZ: for debug 
legoOp *debug_op;



// DescendantofBlock: Returns YES if this operation 
// belongs to a block which is a descendant of the 
// block identified by a pointer of value input_block_int. 
int list_scheduler::DescendantofBlock( int input_block_int, legoOp *op )
{
  
  legoRegion *block_ptr, *root_block_ptr;
  regionList *region_list;
  int block_int;

  derr( ">> DescendantofBlock\n" );

  block_ptr = (legoRegion *) op->GetParentBlockPtr();
  block_int = (int) block_ptr;
  
  root_block_ptr = ((legoTreegion*) Region)->GetRoot();
  while ( (block_int != input_block_int) && (block_ptr != NULL) ) {
    if (block_ptr == root_block_ptr)
      break;
    region_list = block_ptr->GetParents();
    // blocks in a treegion have one and only one parent, except root block 
    // which has no parents. 
    if (region_list != NULL) {
      block_ptr = region_list->GetRegionPtr();
      block_int = (int) block_ptr;
    }
    else {
      block_ptr = NULL;
      block_int = 0;
    }
  }
  
  if (block_int == input_block_int) {
    derr( "... op is a descendant of input block pointer\n" );
    return TRUE;
  }
  else {
    derr( "... op is NOT a descendant of input block pointer\n" );
    return FALSE;
  }
}


// DescendantofCurBlockPtr: Returns YES if this operation 
// belongs to a block which is a descendant of the 
// block identified by the current_block_int attribute. 
int list_scheduler::DescendantofCurBlockPtr( vector < BigListElement >::iterator Node )
{
  
  legoRegion *block_ptr, *root_block_ptr;
  regionList *region_list;
  int block_int;

  derr( ">> DescendantofCurBlockPtr\n" );

  block_ptr = (legoRegion *) (*Node).GetOp()->GetParentBlockPtr();
  block_int = (int) block_ptr;
  
  //HZ: update to handle the case when the Reion is a BB instead of a Treegion
  if(Region->GetRegionType() != RT_BB)
      root_block_ptr = ((legoTreegion*) Region)->GetRoot();
  else
      root_block_ptr = Region;
  while ( (block_int != current_block_int) && (block_ptr != NULL) ) {
    if (block_ptr == root_block_ptr)
      break;
    region_list = block_ptr->GetParents();
    // blocks in a treegion have one and only one parent, except root block 
    // which has no parents. 
    if (region_list != NULL) {
      block_ptr = region_list->GetRegionPtr();
      block_int = (int) block_ptr;
    }
    else {
      block_ptr = NULL;
      block_int = 0;
    }
  }
  
  if (block_int == current_block_int) {
    derr( "... op is a descendant of current block pointer\n" );
    return TRUE;
  }
  else {
    derr( "... op is NOT a descendant of current block pointer\n" );
    return FALSE;
  }
}


// TruePredecessorsScheduled: Returns YES if all predecessors of an 
// operation have been scheduled, returns NO otherwise
// TruePredecessorsScheduled: Same as PredecessorsScheduled except that it 
// ignores anti/output-deps
int list_scheduler::TruePredecessorsScheduled( vector < BigListElement >::iterator Node )
{
  vector < SmallListElement >::iterator Front, Back;
  int PredecessorId,
  PredecessorIssueTime;
  enum edgeTypes DepType;
  
  derr( ">> CheckDeps\n" );
  if ( (*Node).NumPredecessors() == 0 ) {
    derr( "   Entry Node <<\n" );
    return YES;
  }
  
  // If predecessors exist check to see if they are scheduled yet
  for ( Front = (*Node).Predecessors->begin(),
       Back = (*Node).Predecessors->end(); Front != Back; Front++ ) {
     
    DepType = (*Front).GetDependencyType();
    if ((DepType != ET_REGOUT) && (DepType != ET_REGANTI)) {
      // Get the Op id of the current predecessor, so we can search for it
      PredecessorId = (*Front).GetOp()->GetOpId();
      derr( "   checking if Predecessor op " << PredecessorId << " has been scheduled...\n" );
      
      // Ok to consider unscheduled ET_MEM predecessors to load ops (unless 
      // already flagged as "load_verify")
      if (!((DepType == ET_MEM) && 
            IsLoadOp((*Node).GetOp()) && 
            (FindLcAttribute( "load_verify", (*Node).GetOp() ) == NULL))) {
        // If the dominating Op is unscheduled, dependencies should
        // be enforced.
        if ( (PredecessorIssueTime=(*Front).GetOp()->GetSchedTime())
            == UNSCHEDULED ) {
          derr( "... a Predecessor op is unscheduled\n" );
          return NO;
        }
      }
    }
  }
  derr( "... all Predecessor ops are scheduled\n" );
  return YES;
  
}


// PredecessorsScheduled: Returns YES if all predecessors of an 
// operation have been scheduled, returns NO otherwise
int list_scheduler::PredecessorsScheduled( vector < BigListElement >::iterator Node )
{
  vector < SmallListElement >::iterator Front, Back;
  int PredecessorId,
  PredecessorIssueTime;
  
  
  derr( ">> CheckDeps\n" );
  if ( (*Node).NumPredecessors() == 0 ) {
    derr( "   Entry Node <<\n" );
    return YES;
  }
  
  // If predecessors exist check to see if they are scheduled yet
  for ( Front = (*Node).Predecessors->begin(),
       Back = (*Node).Predecessors->end(); Front != Back; Front++ ) {
    
    // Get the Op id of the current predecessor, so we can search for it
    PredecessorId = (*Front).GetOp()->GetOpId();
    derr( "   checking if Predecessor op " << PredecessorId << " has been scheduled...\n" );
    
    // In the dominating Op is unscheduled, dependencies should
    // be enforced.
    if ( (PredecessorIssueTime=(*Front).GetOp()->GetSchedTime())
        == UNSCHEDULED ) {
      derr( "... a Predecessor op is unscheduled\n" );
      return NO;
    }
  }
  derr( "... all Predecessor ops are scheduled\n" );
  return YES;
  
}


// BuildReadyTimes: Finds the ReadyTimes for each operand of an unscheduled
// operation that will now be a Candidate for scheduling
void list_scheduler::BuildReadyTimes( vector < BigListElement >::iterator Node,
                                     int IssueCycle )
{
  vector < SmallListElement >::iterator Front, Back;
  int i, indexi, j, indexj, ready_time, op_latency, latency_count, operand_found;
  int PredecessorIssueTime;
  enum edgeTypes Dependency;
  legoOprd *destoprd, *srcoprd, *predoprd, *destoprd2;
  RU_Info* ru_info;
  
  operand_ready_times = (int *) L_alloc(Operand_ready_pool);
  true_operand_ready_times = (int *) L_alloc(Operand_ready_pool);
  true_dsld_operand_ready_times = (int *) L_alloc(Operand_ready_pool);
  dsld_operand_ready_times = (int *) L_alloc(Operand_ready_pool);
  
  // initialize operand_ready_times to zero
  latency_count = mdes_latency_count();
  for (i = 0; i < latency_count; i++) {
    operand_ready_times[i] = 0;
    true_operand_ready_times[i] = 0;
    true_dsld_operand_ready_times[i] = 0;
    dsld_operand_ready_times[i] = 0;
  }
  
  for ( Front = (*Node).Predecessors->begin(),
       Back = (*Node).Predecessors->end(); Front != Back; Front++ ) {
    switch (Dependency=(*Front).GetDependencyType()) {
    case (ET_CNTL): 
      ru_info = (*Front).GetOp()->GetRUInfoPtr();
      indexi = operand_index (MDES_SYNC_OUT, 1);
      op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, 
                                        indexi);
      // Branch latency now zero to enable Mulit-Way branching, but C_MERGE 
      // ops still require a latency of one for branches. 
      if ((*Node).GetOp()->GetOpcode() == C_MERGE)
        ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + 1; 
      else
        ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
      indexj = operand_index (MDES_SYNC_IN, 1);      
      derr( "** Control Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
           << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
      if ( ready_time > operand_ready_times[indexj])
        operand_ready_times[indexj] = ready_time;
      if ( ready_time > true_operand_ready_times[indexj])
        true_operand_ready_times[indexj] = ready_time;
      if ( ready_time > true_dsld_operand_ready_times[indexj])
        true_dsld_operand_ready_times[indexj] = ready_time;
      if ( ready_time > dsld_operand_ready_times[indexj])
        dsld_operand_ready_times[indexj] = ready_time;
      break;
    case (ET_MEM): 
      // Check MEM deps. If a PlayDoh architecture is used, allow issue
      // of dependent Ops. Otherwise treat as a flow dep.
      if ( PlayDoh == 1 ) {
        derr( "...PlayDoh arch being used" );
        PredecessorIssueTime=(*Front).GetOp()->GetSchedTime();
        if ( ! ( Machine->isStoreOp( (*Node).GetOp() )
                // mdj 10/13/98 DagEntries appear to change when copy ops are 
                // added to the priority list use the op directly here to 
                // avoid this problem. 
                //&& Machine->isBranchOp( (*Front).GetDagEntry()->GetOp() )
                && Machine->isBranchOp( (*Front).GetOp() )
                && (PredecessorIssueTime == UNSCHEDULED || PredecessorIssueTime == IssueCycle) ) ) {
          derr( ", no mem-dep\n" );
          break;
        }
        derr( ", store speculation disallowed\n" );
      } // if - PlayDoh arch
      if ((*Front).GetOp()->GetSchedTime() == UNSCHEDULED) { 
        indexj = operand_index (MDES_SYNC_IN, 0);
        operand_ready_times[indexj] = 9999;
        true_operand_ready_times[indexj] = 9999;
        if (!IsLoadOp((*Node).GetOp()) || 
            (FindLcAttribute( "load_verify", (*Node).GetOp() ) != NULL)) {
          true_dsld_operand_ready_times[indexj] = 9999;
          dsld_operand_ready_times[indexj] = 9999;
        }
      }
      else {
        ru_info = (*Front).GetOp()->GetRUInfoPtr();
        indexi = operand_index (MDES_SYNC_OUT, 0);
        op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexi);
        if ( Machine->isRealOp( (*Front).GetOp() ) )
          ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency; 
        else 
          ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
        indexj = operand_index (MDES_SYNC_IN, 0);      
        derr( "** Memory Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
             << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
        if ( ready_time > operand_ready_times[indexj])
          operand_ready_times[indexj] = ready_time;
        if ( ready_time > true_operand_ready_times[indexj])
          true_operand_ready_times[indexj] = ready_time;
        if (!IsLoadOp((*Node).GetOp()) || 
            (FindLcAttribute( "load_verify", (*Node).GetOp() ) != NULL)) {
          if ( ready_time > true_dsld_operand_ready_times[indexj])
            true_dsld_operand_ready_times[indexj] = ready_time;
          if ( ready_time > dsld_operand_ready_times[indexj])
            dsld_operand_ready_times[indexj] = ready_time;
        }
      }
      break;
    case (ET_REGFLOW):
      operand_found = FALSE;
      // determine operand_ready_times for the src operands (flow dependencies)
      for (j = 0, destoprd = (*Front).GetOp()->GetDestOprdPtr(); destoprd != NULL; 
           destoprd = destoprd->GetNextOprdPtr(), j++) {
        for (i = 0, srcoprd = (*Node).GetOp()->GetSrcOprdPtr(); srcoprd != NULL; 
             srcoprd = srcoprd->GetNextOprdPtr(), i++) {
          if (((destoprd->GetOprdType() == OT_MACRO) &&
               (srcoprd->GetOprdType() == OT_MACRO) &&
               (destoprd->GetOprdRegNum() == srcoprd->GetOprdRegNum())) ||
              
              ((destoprd->GetOprdType() == OT_REG) &&
               (srcoprd->GetOprdType() == OT_REG) &&
               (destoprd->GetOprdRegType() == srcoprd->GetOprdRegType()) &&
               (destoprd->GetOprdRegNum() == srcoprd->GetOprdRegNum()) &&
               (destoprd->GetOprdFileType() == srcoprd->GetOprdFileType()))) {
            operand_found = TRUE;
            ru_info = (*Front).GetOp()->GetRUInfoPtr();
            indexj = operand_index (MDES_DEST, j);
            if (IsLoadOp((*Front).GetOp()) && 
                (FindLcAttribute( "load_verify", (*Front).GetOp() ) != NULL)) {
                
                //HZ: Here Matt assumed that load verify will take 1 cycle.
                // However this "load_verify" attribute is not set and cleared correctly, so
                // there would be situation like
                //  r1 <- ld(r10) and r11 <- r1 in one multiop after scheduling, 
                // which is wrong
                // Quick fix: as we currently not generating the recovery code.
                //  let's change all ld's latency back to 2 cycles.
              //op_latency = 1;
                op_latency = 2;
            }
            else {
              op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexj);
            }
            if ( Machine->isRealOp( (*Front).GetOp() ) )
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency; 
            else 
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
            indexi = operand_index (MDES_SRC, i);
            derr( "** Flow Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
                 << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
            if ( ready_time > operand_ready_times[indexi])
              operand_ready_times[indexi] = ready_time;
            if ( ready_time > true_operand_ready_times[indexi])
              true_operand_ready_times[indexi] = ready_time;
            if ( ready_time > true_dsld_operand_ready_times[indexi])
              true_dsld_operand_ready_times[indexi] = ready_time;
            if ( ready_time > dsld_operand_ready_times[indexi])
              dsld_operand_ready_times[indexi] = ready_time;
          }
        }
        
        // determine operand_ready_times for the pred oprds (flow dependencies)
        for (i = 0, predoprd = (*Node).GetOp()->GetPredOprdPtr(); predoprd != NULL; 
             predoprd = predoprd->GetNextOprdPtr(), i++) {
          // probably do not need the macro comparisons for pred registers, include for now
          if (((destoprd->GetOprdType() == OT_MACRO) &&
               (predoprd->GetOprdType() == OT_MACRO) &&
               (destoprd->GetOprdRegNum() == predoprd->GetOprdRegNum())) ||
              
              ((destoprd->GetOprdType() == OT_REG) &&
               (predoprd->GetOprdType() == OT_REG) &&
               (destoprd->GetOprdRegType() == predoprd->GetOprdRegType()) &&
               (destoprd->GetOprdRegNum() == predoprd->GetOprdRegNum()) &&
               (destoprd->GetOprdFileType() == predoprd->GetOprdFileType()))) {
            operand_found = TRUE;
            ru_info = (*Front).GetOp()->GetRUInfoPtr();
            indexj = operand_index (MDES_DEST, j);
            if (IsLoadOp((*Front).GetOp()) && 
                (FindLcAttribute( "load_verify", (*Front).GetOp() ) != NULL)) {
                
                //HZ: same reason as before to change latency back to 2 cycles
              //op_latency = 1;
                op_latency = 2;
            }
            else {
              op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexj);
            }
            if ( Machine->isRealOp( (*Front).GetOp() ) )
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency; 
            else 
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
            indexi = operand_index (MDES_PRED, i);
            derr( "** Flow Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
                 << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
            if ( ready_time > operand_ready_times[indexi])
              operand_ready_times[indexi] = ready_time;
            if ( ready_time > true_operand_ready_times[indexi])
              true_operand_ready_times[indexi] = ready_time;
            if ( ready_time > true_dsld_operand_ready_times[indexi])
              true_dsld_operand_ready_times[indexi] = ready_time;
            if ( ready_time > dsld_operand_ready_times[indexi])
              dsld_operand_ready_times[indexi] = ready_time;
          }
        }
      }
      if (!operand_found) {
        ru_info = (*Front).GetOp()->GetRUInfoPtr();
        indexi = operand_index (MDES_DEST, 0);
        if (IsLoadOp((*Front).GetOp()) && 
            (FindLcAttribute( "load_verify", (*Front).GetOp() ) != NULL)) {
                //HZ: same reason as before to change latency back to 2 cycles
              //op_latency = 1;
                op_latency = 2;
        }
        else {
          op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexi);
        }
        if ( Machine->isRealOp( (*Front).GetOp() ) ) {
          if ( (*Node).GetOp()->GetOpcode() == BRL ) {
            ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency - 1; 
          }
          else {
            ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency; 
          }
        }
        else { 
          if ( (*Node).GetOp()->GetOpcode() == BRL ) {
            ready_time = (*Front).GetOp()->GetSchedTime() + op_latency - 1; 
          }
          else {
            ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
          }
        }
        indexj = operand_index (MDES_SRC, 0); 
        derr( "** Flow Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
             << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
        derr( "** this Flow Dependency results from a BRL return value, mdes treats as a control sync");
        if ( ready_time > operand_ready_times[indexj])
          operand_ready_times[indexj] = ready_time;
        if ( ready_time > true_operand_ready_times[indexj])
          true_operand_ready_times[indexj] = ready_time;
        if ( ready_time > true_dsld_operand_ready_times[indexj])
          true_dsld_operand_ready_times[indexj] = ready_time;
        if ( ready_time > dsld_operand_ready_times[indexj])
          dsld_operand_ready_times[indexj] = ready_time;
      }
      break;
    case (ET_REGOUT):
      if ((*Front).GetOp()->GetSchedTime() == UNSCHEDULED) { 
        indexj = operand_index (MDES_DEST, 0);
        operand_ready_times[indexj] = 9999;
        dsld_operand_ready_times[indexj] = 9999;
      }
      else {
        operand_found = FALSE;
        // determine operand_ready_times for the destination operands (output dependencies)
        for (i = 0, destoprd = (*Node).GetOp()->GetDestOprdPtr(); destoprd != NULL; 
             destoprd = destoprd->GetNextOprdPtr(), i++) {
          for (j = 0, destoprd2 = (*Front).GetOp()->GetDestOprdPtr(); destoprd2 != NULL; 
               destoprd2 = destoprd2->GetNextOprdPtr(), j++) {
            if (((destoprd2->GetOprdType() == OT_MACRO) &&
                 (destoprd->GetOprdType() == OT_MACRO) &&
                 (destoprd2->GetOprdRegNum() == destoprd->GetOprdRegNum())) ||
                
                ((destoprd2->GetOprdType() == OT_REG) &&
                 (destoprd->GetOprdType() == OT_REG) &&
                 (destoprd2->GetOprdRegType() == destoprd->GetOprdRegType()) &&
                 (destoprd2->GetOprdRegNum() == destoprd->GetOprdRegNum()) &&
                 (destoprd2->GetOprdFileType() == destoprd->GetOprdFileType()))) {
              operand_found = TRUE;
              ru_info = (*Front).GetOp()->GetRUInfoPtr();
              indexj = operand_index (MDES_DEST, j);
              if (IsLoadOp((*Front).GetOp()) && 
                  (FindLcAttribute( "load_verify", (*Front).GetOp() ) != NULL)) {
                //HZ: same reason as before to change latency back to 2 cycles
                //op_latency = 1;
                op_latency = 2;
              }
              else {
                op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexj);
              }
              // add one to ready time here so that op with an output dependency does not try to 
              // write register in same cycle as op it is dependent on, but ok in following cycle
              // Don't add 1 to DEFINEs to agree with Sanjeev's scheduler
              if ((*Node).GetOp()->GetOpcode() == DEFINE)
                ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
              else
                // BRLs define RET_ADDR macro on procedure entrance, not 
                // on procedure exit 
                if (((*Front).GetOp()->GetOpcode() == BRL) && 
                    (destoprd2->GetOprdRegNum() == RET_ADDR)) {
                  ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
                }
                else {
                  ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + 1; 
                }
              indexi = operand_index (MDES_DEST, i);
              derr( "** Output Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
                   << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
              if ( ready_time > operand_ready_times[indexi])
                operand_ready_times[indexi] = ready_time;
              if ( ready_time > dsld_operand_ready_times[indexi])
                dsld_operand_ready_times[indexi] = ready_time;
            }
          }
        }
        if (!operand_found) {
          ru_info = (*Front).GetOp()->GetRUInfoPtr();
          indexi = operand_index (MDES_DEST, 0);
          if (IsLoadOp((*Front).GetOp()) && 
              (FindLcAttribute( "load_verify", (*Front).GetOp() ) != NULL)) {
                //HZ: same reason as before to change latency back to 2 cycles
                //op_latency = 1;
                op_latency = 2;
          }
          else {
            op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, indexi);
          }
          // add one to ready time here so that op with an output dependency does not try to 
          // write register in same cycle as op it is dependent on, but ok in following cycle
          // Don't add 1 to DEFINEs to agree with Sanjeev's scheduler
          if ((*Node).GetOp()->GetOpcode() == DEFINE) {
            if ( (*Node).GetOp()->GetOpcode() == BRL ) {
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency - 1; 
            }
            else {
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
            }
          }
          else {
            if ( (*Node).GetOp()->GetOpcode() == BRL ) {
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
            }
            else {
              ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + 1; 
            }
          }
          indexj = operand_index (MDES_DEST, 0); 
          derr( "** Output Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
               << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
          derr( "** this Output Dependency results from a BRL return value, mdes treats as a control sync" 
               << "\n");
          if ( ready_time > operand_ready_times[indexj])
            operand_ready_times[indexj] = ready_time;
          if ( ready_time > dsld_operand_ready_times[indexj])
            dsld_operand_ready_times[indexj] = ready_time;
        }
      }
        break;
    case (ET_REGANTI):
      if ((*Front).GetOp()->GetSchedTime() == UNSCHEDULED) { 
        indexj = operand_index (MDES_DEST, 0);
        operand_ready_times[indexj] = 9999;
        dsld_operand_ready_times[indexj] = 9999;
      }
      else {
        for (i = 0, destoprd = (*Node).GetOp()->GetDestOprdPtr(); destoprd != NULL; 
             destoprd = destoprd->GetNextOprdPtr(), i++) {
          for (j = 0, srcoprd = (*Front).GetOp()->GetSrcOprdPtr(); srcoprd != NULL; 
               srcoprd = srcoprd->GetNextOprdPtr(), j++) {
            if (((srcoprd->GetOprdType() == OT_MACRO) &&
                 (destoprd->GetOprdType() == OT_MACRO) &&
                 (srcoprd->GetOprdRegNum() == destoprd->GetOprdRegNum())) ||
                
                ((srcoprd->GetOprdType() == OT_REG) &&
                 (destoprd->GetOprdType() == OT_REG) &&
                 (srcoprd->GetOprdRegType() == destoprd->GetOprdRegType()) &&
                 (srcoprd->GetOprdRegNum() == destoprd->GetOprdRegNum()) &&
                 (srcoprd->GetOprdFileType() == destoprd->GetOprdFileType()))) {
              ru_info = (*Front).GetOp()->GetRUInfoPtr();
              indexj = operand_index (MDES_SRC, j);
              op_latency = mdes_operand_latency(ru_info->proc_opc, ru_info->selected_alt->id, 
                                                indexj);
              if ( Machine->isRealOp( (*Front).GetOp() ) )
                ready_time = (*Front).GetOp()->GetSchedTime() + op_latency - BypassLatency; 
              else 
                ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
              indexi = operand_index (MDES_DEST, i);
              derr( "** Anti Dependency Found:   from Op" << (*Front).GetOp()->GetOpId() << " to Op" 
                   << (*Node).GetOp()->GetOpId() << " with ready_time = " << ready_time << "\n");
              if ( ready_time > operand_ready_times[indexi])
                operand_ready_times[indexi] = ready_time;
              if ( ready_time > dsld_operand_ready_times[indexi])
                dsld_operand_ready_times[indexi] = ready_time;
            }
          }
        }
      }
      break;
    }
  }
}


// GetCandidateNodeTree: Tree-Traversal version of this function. scans 
// the list of Ops to try and find one which is unscheduled, has all TRUE 
// predecessors scheduled (excluding anti/output-deps) and meets requirements 
// of tree-traversal scheduling (is dominated by cur_block_ptr)  Creates 
// "int *operand_ready_times" for the op to be used during scheduling
vector < BigListElement >::iterator
   list_scheduler::GetCandidateNodeTree(int IssueCycle, knobs *Knobs,
                                        legoRegion *proc_ptr, int Final_Pass)
{
  ListIterator Ptr;
  int sched_time, descendant, predecessors_scheduled, mdes_slot, i; 
  legoOp *dummy_br_op; 
  int rn_conflict, ready_time, true_ready_time, true_dsld_ready_time, dsld_ready_time;
  int latency_count, alt_id, operand_latency; 
  RU_Info* ru_info;
  Mdes_Info* mdes_info;
  Mdes_Compatable_Alt *compatable_alt;
  attrs *liveattr;
  opEdges *edge;
  int orig_ptr_id; 
  legoOprd *def, *use, *oprd; 
  oprdList *uses; 
  char *regiontype, fully_if_convert;
  int FullyIfConverted;
  
  derr( ">> GetCandidateNodeTree\n" );
  
  
  if (current_before_op->GetOpcode() == BRL && 
      current_before_op->GetNextLink()->GetOpcode() == DUMMY_BR && 
      current_before_op->GetNextLink()->GetSchedTime() == UNSCHEDULED ) {
    for (Ptr = List->begin(), dummy_br_op = current_before_op->GetNextLink();
         (*Ptr).GetOp() != dummy_br_op;
         Ptr++)
      ;// do nothing
    derr( ">> GetCandidateNodeTree: Linking DUMMY_BR to previous BRL\n" );
    //BuildReadyTimes( Ptr, IssueCycle );
    // or maybe don't worry about ready-times when linking DUMMY_BR
    for (i = 0; i < mdes_latency_count(); i++)
      operand_ready_times[i] = 0;
    mdes_slot = RU_can_schedule_op ((*Ptr).GetOp()->GetRUInfoPtr(), 
                                    (*Ptr).GetOp()->GetMdesInfoPtr(),
                                    operand_ready_times, IssueCycle, 0, 
                                    mdes_total_slots(), 0);
    if (mdes_slot == -1) {
      derr( "<< GetCandidateNodeTree: candidate not found, DUMMY_BR can not be scheduled in CurrentCycle.\n" );
      return List->end();
    }
    else
      return Ptr;
  }

  Ptr = ListPtr;
  ListTail = List->end();
  while ( Ptr != ListTail ) {
    derr( "   candidate Op " << (*Ptr).GetOp()->GetOpId() << "\n" );

    sched_time = (*Ptr).GetOp()->GetSchedTime();
    if ( sched_time == UNSCHEDULED ) {
      descendant = DescendantofCurBlockPtr( Ptr );
      
      //HZ: temp output info for debug
      //derr("  descendant: " << descendant << "\n");
      
      if ( descendant == YES ) {
          
        Knobs->SetDefaultPanel ("ccom");
        Knobs->Read ("region", regiontype);
        Knobs->Read ("fully-if-convert", fully_if_convert);
        FullyIfConverted = FALSE;
        if ((strcmp (regiontype, "FICT") == 0) || 
            (fully_if_convert && Final_Pass)) {
          FullyIfConverted = TRUE;
        }
        if (FullyIfConverted == TRUE) {
          predecessors_scheduled = PredecessorsScheduled( Ptr );
          if ( predecessors_scheduled == YES ) {
            BuildReadyTimes( Ptr, IssueCycle );
            ListPtr = Ptr + 1;
            
            derr( ">> GetCandidateNodeTree: candidate found\n" );
            // Update output to ListFile for accepted candidate
            if ( CreateSchedVizFiles ) {
              fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
            }
            return Ptr;
          }
          else {
            derr( "   candidate rejected, has unscheduled predecessor(s)\n" );
            // Update output to ListFile for rejected candidate
            if ( CreateSchedVizFiles ) {
              fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
              fprintf (ListFile, "n\n");
              fprintf (ListFile, "unscheduled predecessor(s)\n");
            }
            Ptr++;
          }
        }
        else { 
          predecessors_scheduled = TruePredecessorsScheduled( Ptr );

          if ( predecessors_scheduled == YES ) {
              
            //HZ: Debug:
            //if(IssueCycle == 2 && Ptr->GetOp()->GetOpId() == 804)
            //{
                //int temp_iiii = 1;
            //}
              
            
            BuildReadyTimes( Ptr, IssueCycle );
            
            // Allow renaming to try and improve operand_ready_times for trees
            latency_count = mdes_latency_count();
            ru_info = (*Ptr).GetOp()->GetRUInfoPtr();
            mdes_info = (*Ptr).GetOp()->GetMdesInfoPtr();
            compatable_alt = mdes_info->compatable_alts; 
            alt_id = compatable_alt->alt->id;
            ready_time = 0; 
            true_ready_time = 0; 
            true_dsld_ready_time = 0; 
            dsld_ready_time = 0; 
            for (i = 0; i < latency_count; i++) {
              operand_latency = mdes_operand_latency(ru_info->proc_opc, alt_id, i);
              if ( (operand_ready_times[i] - operand_latency) > ready_time )
                ready_time = operand_ready_times[i] - operand_latency;
              if ( (true_operand_ready_times[i] - operand_latency) >  true_ready_time )
                true_ready_time = true_operand_ready_times[i] - operand_latency;
              if ( (true_dsld_operand_ready_times[i] - operand_latency) >  true_dsld_ready_time )
                true_dsld_ready_time = true_dsld_operand_ready_times[i] - operand_latency;
              if ( (dsld_operand_ready_times[i] - operand_latency) >  dsld_ready_time )
                dsld_ready_time = dsld_operand_ready_times[i] - operand_latency;
            }
            
            if (true_dsld_ready_time < dsld_ready_time) {
              
              //cerr << "\nBefore Renaming:\n";
              //cerr << "\nOpId = " << (*Ptr).GetOp()->GetOpId() << "\n";
              //cerr << "  true_dsld_ready_time = " << true_dsld_ready_time << "\n";
              //cerr << "  dsld_ready_time = " << dsld_ready_time << "\n\n";
              
              if ( true_dsld_ready_time <= IssueCycle ) {
                
                // Rename may change Ptr
                orig_ptr_id = (*Ptr).GetOp()->GetOpId(); 
                ReDoLiveVarsAfterGlobal = FALSE; 
                rn_conflict = Rename((*Ptr).GetOp(), NO, Knobs, 
                                     (legoProc *) proc_ptr, Final_Pass, 
                                     YES, NO);
                
                // Now reset ListTail and Ptr to the original Id
                ListTail = List->end();
                Ptr = List->begin();
                while ((*Ptr).GetOp()->GetOpId() != orig_ptr_id) Ptr++; 
                
                if (rn_conflict == NO_RENAMING_CONFLICT) {
                  
                  //cerr << "Renaming Successfull !!!\n\n";
                  
                  if (!((*Ptr).GetOp()->IsDummy())) {
                    falsedep_renamed_ops++;
                  }
                  
                  // Op may not actually get scheduled this cycle. Make 
                  // sure that LiveVars get updated in this tree so 
                  // that op won't disappear (Due to DoTheMessyStuff())
                  for (def = (*Ptr).GetOp()->GetDestOprdPtr(); 
                       def != NULL; 
                       def = def->GetNextOprdPtr()) {
                    if (def->GetOprdType() != OT_UNDEFINED) {
                      for (uses = Chains->GetDUChains()->Lookup (def);
                           (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
                           uses = uses->GetNextListPtr()) {
                        use = uses->GetOprdPtr();
                        if (((legoRegion *) use->GetParentOpPtr()
                             ->GetParentBlockPtr())->GetParentPtr() == Region) {
                          FixLiveVarsFromUses(use, (*Ptr).GetOp(), 
                                              (legoProc*) proc_ptr);
                        }
                        else {
                          ReDoLiveVarsAfterGlobal = TRUE; 
                          break;
                        }
                      }
                    }
                  }
                  
                  if (ReDoLiveVarsAfterGlobal) {
                    // Clean-up previous live attrs generated by earlier call
                    for ( edge = ((legoProc*) proc_ptr)->GetEdgeDictionary(); edge != NULL;
                         edge = edge->GetNextOpEdgePtr() ) {
                      liveattr = FindLiveAttribute (edge);
                      if (liveattr != NULL) RemoveLiveAttribute (edge, ((legoProc *) proc_ptr));
                    }
                    
                    then = time(NULL);
                    start_live = clock();
                    LiveVariables ((legoProc*) proc_ptr);
                    liveness_calls++;
                    now = time(NULL);
                    finish_live = clock();
                    dderr ("LiveVariables() call number " << live_call_number++ << " ended\n");
                    elapsed = difftime(now, then);
                    elapsed_c = ((finish_live - start_live) / clocks_per_sec);
                    dderr ("---Elapsed time is " << elapsed << " seconds\n");
                    dderr ("---Elapsed time is " << elapsed_c << " ticks\n"); 
                    //total_live += elapsed_c;
                    total_live += elapsed;
                    
                    ReDoLiveVarsAfterGlobal = FALSE; 
                    ReDoLiveVarsNextTreegion = FALSE; 
                  }
                  
                  // Re-Do operand_ready_times[] so change is transparent to 
                  // the scheduler (Output/Anti-Deps incrementally removed 
                  // during renaming). 
                  BuildReadyTimes( Ptr, IssueCycle );
                  
                  ready_time = 0; 
                  true_ready_time = 0; 
                  true_dsld_ready_time = 0; 
                  dsld_ready_time = 0; 
                  for (i = 0; i < latency_count; i++) {
                    operand_latency = mdes_operand_latency(ru_info->proc_opc, alt_id, i);
                    if ( (operand_ready_times[i] - operand_latency) > ready_time )
                      ready_time = operand_ready_times[i] - operand_latency;
                    if ( (true_operand_ready_times[i] - operand_latency) >  true_ready_time )
                      true_ready_time = true_operand_ready_times[i] - operand_latency;
                    if ( (true_dsld_operand_ready_times[i] - operand_latency) >  true_dsld_ready_time )
                      true_dsld_ready_time = true_dsld_operand_ready_times[i] - operand_latency;
                    if ( (dsld_operand_ready_times[i] - operand_latency) >  dsld_ready_time )
                      dsld_ready_time = dsld_operand_ready_times[i] - operand_latency;
                  }
                  
                  //cerr << "After Renaming:\n";
                  //cerr << "  true_dsld_ready_time = " << true_dsld_ready_time << "\n";
                  //cerr << "  dsld_ready_time = " << dsld_ready_time << "\n\n";
                  
                }
                else {
                  
                  if (ReDoLiveVarsAfterGlobal) {
                    // Clean-up previous live attrs generated by earlier call
                    for ( edge = ((legoProc*) proc_ptr)->GetEdgeDictionary(); edge != NULL;
                         edge = edge->GetNextOpEdgePtr() ) {
                      liveattr = FindLiveAttribute (edge);
                      if (liveattr != NULL) RemoveLiveAttribute (edge, ((legoProc *) proc_ptr));
                    }
                    
                    then = time(NULL);
                    start_live = clock();
                    LiveVariables ((legoProc*) proc_ptr);
                    liveness_calls++;
                    now = time(NULL);
                    finish_live = clock();
                    dderr ("LiveVariables() call number " << live_call_number++ << " ended\n");
                    elapsed = difftime(now, then);
                    elapsed_c = ((finish_live - start_live) / clocks_per_sec);
                    dderr ("---Elapsed time is " << elapsed << " seconds\n");
                    dderr ("---Elapsed time is " << elapsed_c << " ticks\n"); 
                    //total_live += elapsed_c;
                    total_live += elapsed;
                    
                    ReDoLiveVarsAfterGlobal = FALSE; 
                    ReDoLiveVarsNextTreegion = FALSE; 
                  }
                  
                  //cerr << "Renaming Conflict !!!\n\n";
                  // Don't try to schedule unless predecessors have all been 
                  // scheduled (otherwise dom //ism may miss anti-deps
                  if (ready_time >= 9990) {
                    Ptr++;
                    continue; 
                  }
                  
                }
              }
              else {
                
                //cerr << "true_dsld_ready_time > IssueCycle !!!\n\n";
                // Don't try to schedule unless predecessors have all been 
                // scheduled (otherwise dom //ism may miss anti-deps
                if (ready_time >= 9990) {
                  Ptr++;
                  continue; 
                }
                
              }
            }
          
            //cerr << "  IssueCycle = " << IssueCycle << "\n"; 
            //cerr << "  dsld_ready_time = " << dsld_ready_time << "\n"; 
            //cerr << "  ready_time = " << ready_time << "\n"; 
            if ((dsld_ready_time < ready_time) && 
                (IssueCycle < ready_time) && 
                (dsld_ready_time <= IssueCycle)) { 
              //cerr << "Add load_verify attr !!!\n\n"; 
              oprd = new legoOprd; 
              oprd->SetOprdType (OT_LITERAL_I); 
              oprd->SetLiteralInteger(0); 
              AddLcAttribute ("load_verify", oprd, (*Ptr).GetOp(), 
                              (legoProc *) proc_ptr); 
              Ptr++; 
              continue; 
            } 
            
            //cerr << "Candidate Found !!!\n\n"; 
            ListPtr = Ptr + 1; 
            
            derr( ">> GetCandidateNodeTree: candidate found\n" );
            // Update output to ListFile for accepted candidate
            if ( CreateSchedVizFiles ) {
              fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
            }
            
            return Ptr;
            
          }
          else {
            derr( "   candidate rejected, has unscheduled predecessor(s)\n" );
            // Update output to ListFile for rejected candidate
            if ( CreateSchedVizFiles ) {
              fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
              fprintf (ListFile, "n\n");
              fprintf (ListFile, "unscheduled predecessor(s)\n");
            }
            Ptr++;
          }
        }
      }
      else {
        derr( "   candidate rejected, not a descendant of current block ptr\n" );
        // Update output to ListFile for rejected candidate
        if ( CreateSchedVizFiles ) {
          fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
          fprintf (ListFile, "n\n");
          fprintf (ListFile, "non-descendant of current_block_ptr\n");
        }
        Ptr++;
      }
    }
    else {
      derr( "   candidate rejected, already scheduled\n" );
      // Update output to ListFile for rejected candidate
      if ( CreateSchedVizFiles ) {
        fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
        fprintf (ListFile, "n\n");
        fprintf (ListFile, "already scheduled\n");
      }
      Ptr++;
    }

  }
  derr( "<< GetCandidateNodeTree: candidate not found\n" );
  return List->end();
}

//HZ: 08/25/00
/*
void list_scheduler::PrintCandidateNodes( int IssueCycle, ofstream & os1 )
{
  ListIterator Ptr;
  int sched_time, descendant, predecessors_scheduled; 
  
  
  derr( ">> PrintCandidateNodes\n" );
  Ptr = ListPtr;
  ListTail = List->end();
  
  os1 << "IssueCycle: " << IssueCycle << endl;  
  
  while ( Ptr != ListTail ) {
    derr( "   candidate Op " << (*Ptr).GetOp()->GetOpId() << "\n" );
    sched_time = (*Ptr).GetOp()->GetSchedTime();
    predecessors_scheduled = PredecessorsScheduled( Ptr );
    if ( sched_time == UNSCHEDULED  &&
        predecessors_scheduled == YES ) {
      
//      BuildReadyTimes( Ptr, IssueCycle );
//      ListPtr = Ptr + 1;
      
//      derr( ">> GetCandidateNode: candidate found\n" );
      // Update output to ListFile for accepted candidate
//      if ( CreateSchedVizFiles ) {
//      fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
//      }
 //     return Ptr;
 
        os1 << (*Ptr).PrintElement(os1);
    }
    else {
      if ( sched_time != UNSCHEDULED ) {
        derr( "   candidate rejected, already scheduled\n" );
        // Update output to ListFile for rejected candidate
        if ( CreateSchedVizFiles ) {
          fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
          fprintf (ListFile, "n\n");
          fprintf (ListFile, "already scheduled\n");
        }
      }
      else {
        derr( "   candidate rejected, has unscheduled predecessor(s)\n" );
        // Update output to ListFile for rejected candidate
        if ( CreateSchedVizFiles ) {
          fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
          fprintf (ListFile, "n\n");
          fprintf (ListFile, "unscheduled predecessor(s)\n");
        }
      }
      Ptr++;
    }
  }
  os1<< "PrintCandidateNode: candidate not found\n" );

}
*/



// GetCandidateNode: scans the list of Ops to try and find one which 
// is unscheduled and has all predecessors scheduled.  Creates 
// "int *operand_ready_times" for the op to be used during scheduling
vector < BigListElement >::iterator
   list_scheduler::GetCandidateNode( int IssueCycle )
{
  ListIterator Ptr;
  int sched_time, descendant, predecessors_scheduled; 
  
  
  derr( ">> GetCandidateNode\n" );
  Ptr = ListPtr;
  ListTail = List->end();
  while ( Ptr != ListTail ) {
    derr( "   candidate Op " << (*Ptr).GetOp()->GetOpId() << "\n" );
    sched_time = (*Ptr).GetOp()->GetSchedTime();
    predecessors_scheduled = PredecessorsScheduled( Ptr );
    if ( sched_time == UNSCHEDULED  &&
        predecessors_scheduled == YES ) {
      
      BuildReadyTimes( Ptr, IssueCycle );
      ListPtr = Ptr + 1;
      
      derr( ">> GetCandidateNode: candidate found\n" );
      // Update output to ListFile for accepted candidate
      if ( CreateSchedVizFiles ) {
        fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
      }
      return Ptr;
    }
    else {
      if ( sched_time != UNSCHEDULED ) {
        derr( "   candidate rejected, already scheduled\n" );
        // Update output to ListFile for rejected candidate
        if ( CreateSchedVizFiles ) {
          fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
          fprintf (ListFile, "n\n");
          fprintf (ListFile, "already scheduled\n");
        }
      }
      else {
        derr( "   candidate rejected, has unscheduled predecessor(s)\n" );
        // Update output to ListFile for rejected candidate
        if ( CreateSchedVizFiles ) {
          fprintf (ListFile, "%d\n", (*Ptr).GetOp()->GetOpId());
          fprintf (ListFile, "n\n");
          fprintf (ListFile, "unscheduled predecessor(s)\n");
        }
      }
      Ptr++;
    }
  }
  derr( "<< GetCandidateNode: candidate not found\n" );
  return List->end();
}


// ResetListPtr: sets the ListPtr to the first unscheduled Op in List
void list_scheduler::ResetListPtr()
{
  vector < BigListElement >::iterator Iter = List->begin();
  
  derr( ">> ResetListPtr\n" );
  while ( Iter != List->end() &&
         (*Iter).GetOp()->GetSchedTime() != UNSCHEDULED )
    Iter++;
  ListPtr = Iter;
  derr( "<< ResetListPtr\n" );
}

void list_scheduler::SimpleRename (legoOp *op, int RegNum, int IncMaxRegNum)
{
  oprdList *uses; 
  legoOprd *def, *use;
  int localRegNum; 
  
  dderr("RENAME: SimpleRename\n");
   
  if (!IncMaxRegNum) 
    localRegNum = RegNum; 
  for (def = op->GetDestOprdPtr(); 
       def != NULL; 
       def = def->GetNextOprdPtr()) {
    if (def->GetOprdType() != OT_UNDEFINED) {
      if (IncMaxRegNum)
        localRegNum = ++MaxRegNum;
      def->SetOprdRegNum (localRegNum);
      RemoveOutputDepsAfterRename(def);
      RemoveAntiDepsAfterDefRename(def);
      dderr("RENAME: rename original def (OpId = " << op->GetOpId() << ") to RegNum " << localRegNum << "\n");
      for (uses = Chains->GetDUChains()->Lookup (def);
           (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
           uses = uses->GetNextListPtr()) {
        use = uses->GetOprdPtr();
        use->SetOprdRegNum (localRegNum);
        dderr("RENAME: rename use (OpId = " << use->GetParentOpPtr()->GetOpId() << ") to RegNum " << localRegNum << "\n");
      }  
    }
    if (!IncMaxRegNum) 
      localRegNum++;
  }
}

void list_scheduler::ForwardGlobalRename (legoOprd *def, int RegNum, 
                                          legoOprd *orig_def)
{
  oprdList *uses;
  legoOprd *use;

  dderr("RENAME: ForwardGlobalRename\n");
  
  for (uses = Chains->GetDUChains()->Lookup (def);
       (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
       uses = uses->GetNextListPtr()) {
    use = uses->GetOprdPtr();
    if (use->GetOprdRegNum() != RegNum) {
      use->SetOprdRegNum (RegNum);
      // Turns out it is possible for other defs in treegion to still have 
      // dependencies if both dependent ops get renamed during global rename
      //RemoveAntiDepsAfterUseRename(use);
      dderr("RENAME: rename use (OpId = " << use->GetParentOpPtr()->GetOpId() << ") to RegNum " << RegNum << "\n");
      ReverseGlobalRename(use, RegNum, orig_def); 
    }
  }  
}

void list_scheduler::ReverseGlobalRename (legoOprd *use, int RegNum, 
                                          legoOprd *orig_def)
{
  oprdList *defs;
  legoOprd *def;
  
  dderr("RENAME: ReverseGlobalRename\n");
  
  for (defs = Chains->GetUDChains()->Lookup (use);
       (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
       defs = defs->GetNextListPtr()) {
    def = defs->GetOprdPtr();
    if (def->GetOprdRegNum() != RegNum) {
      // Need to redo LiveVars immediately after GlobalRename if  
      // more than one def in Treegion affected by GlobalRename
      if (((legoRegion *) def->GetParentOpPtr()->GetParentBlockPtr())
          ->GetParentPtr() == Region) {
        ReDoLiveVarsAfterGlobal = TRUE;
        // It is also still possible that there is a 'remote' Merge Problem 
        // not caught by the original IsMergeProblem() check.
        // If there is, finish with the global rename but return a 
        // RENAMING_CONFLICT (possible to re-do Rename with Hazardous, 
        // forcing a copy to be inserted, but this is infrequent).
        if (IsRemoteMergeProblem(def, orig_def) == TRUE) {
          MergeProblemDuringGlobal = TRUE; 
        }
      }
      // else the ReDo can wait until starting the next Treegion
      else {
        ReDoLiveVarsNextTreegion = TRUE;
      }
      def->SetOprdRegNum (RegNum);
      dderr("RENAME: rename def (OpId = " << def->GetParentOpPtr()->GetOpId() << ") to RegNum " << RegNum << "\n");
      ForwardGlobalRename(def, RegNum, orig_def);
    }  
  }  
}

void list_scheduler::GlobalRename (legoOp *op, int RegNum, int IncMaxRegNum)
{
  legoOprd *def;
  int localRegNum; 
  
  dderr("RENAME: GlobalRename\n");
  
  if (!IncMaxRegNum) 
    localRegNum = RegNum; 
  for (def = op->GetDestOprdPtr(); 
       def != NULL; 
       def = def->GetNextOprdPtr()) {
    if (def->GetOprdType() != OT_UNDEFINED) {
      if (IncMaxRegNum) 
        localRegNum = ++MaxRegNum;
      def->SetOprdRegNum (localRegNum);
      dderr("RENAME: rename original def (OpId = " << op->GetOpId() << ") to RegNum " << localRegNum << "\n");
      ForwardGlobalRename(def, localRegNum, def);
    }
    if (MergeProblemDuringGlobal == FALSE) { 
      // Output deps below this op may remain due to global rename, so 
      // introduce RemoveOutputDepsAfterRenameUp()
      RemoveOutputDepsAfterRenameUp(def);
      RemoveAntiDepsAfterDefRename(def);
    }
    if (!IncMaxRegNum) 
      localRegNum++;
  }
}

int list_scheduler::AddCopyOps (legoOp *op)
{
  
  edgeList *edgelist; 
  opEdges *edge; 
  legoRegion *block_ptr; 
  int block_int; 
  legoOp *exit_op, *new_op, *before_op, *last_op_in_multiop, *op_in_multiop; 
  opList *exit_ops; 
  legoOprd *def, *new_src, *new_dest, *new_pred, *oprd; 
  BigListElement Element;
  fileTypes filetype;
  int orig_op_id, rc, multiop_stime; 
  vector < BigListElement >::iterator ListIter, TempListIter, TempListIter2;
  oprdList *oprd_list, *new_uses_inside, *new_use_inside;
  oprdList *new_use_outside, *prev_use_outside, *uses, *defs;
  oprdList *more_uses, *more_defs;
  oprdList *orig_uses_outside = NULL;
  legoOprd *use, *this_def; 
  legoOprd *another_use, *another_def; 
  attrs *a; 
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  int UsePreceedsDefInBlock; 
  legoOp *predecessor_op; 
  oprdList *orig_ud_chain, *new_ud_chain; 
  
  dderr("RENAME: AddCopyOps\n");
  
  // Now that we are renaming for dom //ism (renaming scheduled ops), 
  // need to guarantee that copy op can be scheduled. Otherwise we have 
  // a RENAMING_CONFLICT
        if (op->GetSchedTime() != UNSCHEDULED) 
        {
                 // Find the last op in this multiop
                 for (last_op_in_multiop = current_before_op;
                 ((last_op_in_multiop->GetNextLink() != NULL) && 
                  (last_op_in_multiop->GetNextLink()->GetSchedTime() != 
                        UNSCHEDULED));
                 last_op_in_multiop = last_op_in_multiop->GetNextLink())
                        ; // Do Nothing
                 // See if this is a multiway branch yet. DoTheMessyStuff is not enough 
                 // if it is. Bail-out for now
                 multiop_stime = last_op_in_multiop->GetSchedTime();
                 for (op_in_multiop = last_op_in_multiop->GetPrevLink(); 
                 ((op_in_multiop != NULL) &&
                  ((op_in_multiop->GetSchedTime() == multiop_stime) || 
                        // PrepareToDie() may scatter ops with s_time = 0
                        (FindLcAttribute( "dp_remove", op_in_multiop ) != NULL)));
                 op_in_multiop = op_in_multiop->GetPrevLink()) 
       {
                        if (op_in_multiop->GetOpcode() == BRU) 
         {
                // this is already a multiway then
                //cerr << "\n\nWarning: Can't AddCopyOp() for scheduled op, Multi-Way branch present (opId = " << op->GetOpId() << ") !!! \n\n";
                return (RENAMING_CONFLICT);
                        }
                 }
                 if (last_op_in_multiop->GetNextLink() == NULL) {
                        if (!AllowDownwardCodeMotion) return (RENAMING_CONFLICT);

                        // For it to be ok to proceed, last_op_in_multiop must be a BRCT or BRCF 
                        // and must not be a treegion exit. 
                        if ((last_op_in_multiop->GetOpcode() != BRCT) &&  
                  (last_op_in_multiop->GetOpcode() != BRCF)) {
                return (RENAMING_CONFLICT);
                        } 
                        for (exit_ops = Region->GetExitOpsPtr(); 
                        exit_ops != NULL; 
                        exit_ops = exit_ops->GetNextListPtr()) {
                if ((exit_op = exit_ops->GetOpPtr()) == last_op_in_multiop) {
                  return (RENAMING_CONFLICT);
                }
                        }
                 }
         }
      
      
        // adding new elements to priority list screws up pointers for original 
        // Nodes. Need to remember which op is currently pointed to so 
        // that ListPtr can be reset to this Dag Node when done.
        orig_op_id = op->GetOpId(); 

        for (def = op->GetDestOprdPtr(); 
       def != NULL; 
       def = def->GetNextOprdPtr()) 
        {
        if (def->GetOprdType() != OT_UNDEFINED) 
                {
      new_op = new legoOp(++MaxOpId);
      copy_ops_added++;
      // make sure I copy construct the PredVector
      if (op->GetPredVectorPtr() != NULL) 
                {
                        new_op->SetPredVectorPtr(new bitvector(*op->GetPredVectorPtr()));
                }
      // Copy the "orig_wt" attr if it exists
      if ((a = FindLcAttribute( "orig_wt", op )) != NULL) 
                {
                        oprd = new legoOprd;
                        oprd->SetOprdType (OT_LITERAL_D);
                        oprd->SetLiteralDouble (a->GetAttrOprdPtr()->GetLiteralDouble());
                        AddLcAttribute ("orig_wt", oprd, new_op,
                                        (legoProc *) FindParentRegionType (RT_PROC, new_op));
                }
      new_src = new legoOprd(*def);
      printf("!1\n");
      new_dest = new legoOprd(*def);
      printf("!2\n");
      filetype = def->GetOprdFileType();
      if (filetype != FT_PR) 
      if(op->GetPredOprdPtr()!=NULL)
      {
                        new_pred = new legoOprd(*(op->GetPredOprdPtr()));
      }
      else
           {
                        printf("OPCODE:%d\n",op->GetOpcode()); 
                        printf("OP-ID:%d\n",op->GetOpId()); 
                }
     
      printf("!3\n");
      if ((filetype == FT_GPR) || (filetype == FT_CR)) 
        new_op->SetOpcode(MOVE);
      else if (filetype == FT_FPR)
        new_op->SetOpcode(MOVEF_D);
      else if (filetype == FT_PR)
        new_op->SetOpcode(CMPP_W_TRUE_UN_UN);
      else 
        // no move op for BTR-to-BTR moves, use int MOVE for now 
        new_op->SetOpcode(MOVE);
      //else if (filetype == FT_BTR)
      //new_op->SetOpcode(NOT_SURE);
      //else 
      //new_op->SetOpcode(NOT_SURE);
      if (filetype != FT_PR) {
        new_op->SetSrcOprdPtr(new_src);
        new_src->SetParentOpPtr(new_op);
        // Give the new op the original def and the original op the new dest 
        // So that ReachingDefinitions() does not need to be called again.
        new_op->SetDestOprdPtr(def);
        def->SetParentOpPtr(new_op);
        op->SetDestOprdPtr(new_dest);
        new_dest->SetParentOpPtr(op);
        new_op->SetPredOprdPtr (new_pred);
        new_pred->SetParentOpPtr(new_op);
        if (new_pred->GetOprdType() == OT_REG) {
          // Adjust Chains 
          orig_ud_chain = Chains->GetUDChains()->Lookup (op->GetPredOprdPtr());
          if (Chains->GetUDChains()->NotFound() == FALSE) {
            new_ud_chain = new oprdList(*orig_ud_chain);
            Chains->GetUDChains()->Set (new_pred, new_ud_chain); 
            // add this use to each def that reaches predicate
            for (more_defs = orig_ud_chain;
                 more_defs != NULL; 
                 more_defs = more_defs->GetNextListPtr()) { 
              another_def = more_defs->GetOprdPtr();
              for (more_uses = Chains->GetDUChains()->Lookup (another_def);
                   more_uses->GetNextListPtr() != NULL;
                   more_uses = more_uses->GetNextListPtr()) 
                ; // find end of DUChain
              more_uses->SetNextListPtr(new oprdList);
              more_uses->GetNextListPtr()->SetOprdPtr(new_pred); 
            }
          }
        }
      }
      else {
        cerr << "\n*** Would like to know if I'm adding any CMPP copy ops (need RDef patch-up work if I am ***\n";
        new_op->SetSrcOprdPtr(NULL);
        // Give the new op the original def and the original op the new dest 
        // So that ReachingDefinitions() does not need to be called again.
        new_op->SetDestOprdPtr(def);
        def->SetParentOpPtr(new_op);
        op->SetDestOprdPtr(new_dest);
        new_dest->SetParentOpPtr(op);
        new_op->SetPredOprdPtr (new_src);
        new_src->SetParentOpPtr(new_op);
      }

      // Now adjust Chains for the reaching def between the orig and new ops
      oprd_list = new oprdList;
      oprd_list->SetOprdPtr (new_src);
      Chains->GetDUChains()->Set (new_dest, oprd_list); 
      oprd_list = new oprdList;
      oprd_list->SetOprdPtr (new_dest);
      Chains->GetUDChains()->Set (new_src, oprd_list); 

      // Split original DUChains between those uses inside the Treegion 
      // and dominated by the original op and those not. Those inside the 
      // Treegion and dominated by the original op go to the original op, 
      // the others go the new MOVE op
      uses = Chains->GetDUChains()->Lookup (def);
      if (Chains->GetDUChains()->NotFound() == FALSE) {
        while (uses != NULL) {
          use = uses->GetOprdPtr();
          // Determine if this use preceeds the defining op in its own block 
          UsePreceedsDefInBlock = FALSE; 
          // new_op not yet scheduled, use original op to determine if any 
          // uses preceed.
          for (predecessor_op = op; 
               predecessor_op != NULL; 
               predecessor_op = predecessor_op->GetPrevLink()) {
            if (predecessor_op == use->GetParentOpPtr()) {
              UsePreceedsDefInBlock = TRUE; 
              break; 
            }
          }
          if ((((legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() == Region) && 
              (DescendantofBlock( (int) op->GetParentBlockPtr(), use->GetParentOpPtr() ) && 
               !UsePreceedsDefInBlock)) {
            new_uses_inside = Chains->GetDUChains()->Lookup (new_dest);
            new_use_inside = new oprdList;
            new_use_inside->SetOprdPtr (use);
            // need to find the end of the list of uses to add 
            // the latest use
            while (new_uses_inside->GetNextListPtr() != NULL) {
              new_uses_inside = new_uses_inside->GetNextListPtr();
            }
            new_uses_inside->SetNextListPtr (new_use_inside);
            // Now fix the UDChain to match new_use_inside
            for (defs = Chains->GetUDChains()->Lookup (use);
                 (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                 defs = defs->GetNextListPtr()) {
              this_def = defs->GetOprdPtr();
              if (this_def == def) {
                defs->SetOprdPtr(new_dest); 
              }
            }
          }
          else {
            if (orig_uses_outside == NULL) {
              orig_uses_outside = new oprdList;
              orig_uses_outside->SetOprdPtr(use);
              prev_use_outside = orig_uses_outside;
            }
            else {
              new_use_outside = new oprdList;
              new_use_outside->SetOprdPtr(use);
                prev_use_outside->SetNextListPtr(new_use_outside);
              prev_use_outside = new_use_outside;
            }
          }
          uses = uses->GetNextListPtr();
        }
        uses = Chains->GetDUChains()->Lookup (def);
        delete uses; 
        Chains->GetDUChains()->Set (def, orig_uses_outside);
      }
      
      // Add to end of priority list
      Element = BigListElement(); 
      Element.SetOp(new_op);
      Element.SetWeight( -1 );
      Element.SetHeight( -1 );  
      Element.SetDepth( -1 );
#if defined (_STL_LIST_USED_)
      ListIter = List->insert( List->begin(), Element );
#else if defined (_STL_VECTOR_USED_)
      List->push_back( Element );
      ListIter = List->end();
      ListIter--;
#endif
      ListCount++;

      // add a flow dep from the original op to the MOVE op (new_op)
      // don't need to worry about recursive renaming because we do 
      // not add copy ops unless there are uses from within the Treegion
      
      // First need to find the Node for the original op 
      TempListIter = List->begin();
      while ((*TempListIter).GetOp()->GetOpId() != op->GetOpId()) {
        TempListIter++; 
      }
      rc = (*ListIter).AddPredecessor( ET_REGFLOW, (*TempListIter).GetOp(), &(*TempListIter) );
      derr( " (" << rc << ") " );
      rc = (*TempListIter).AddSuccessor( ET_REGFLOW, (*ListIter).GetOp(), &(*ListIter) );
      ddderr( " (" << rc << ") " );
      ddderr( "Inserted ET_REGFLOW between " << (*TempListIter).GetOp()->GetOpId() << 
           " and " << (*ListIter).GetOp()->GetOpId() << "\n" );

      // Also need to split dependencies between original op and new MOVE op.
      // Successors first. 
      // Flow- and Anti-Deps stay with the original op. Output-Deps need to 
      // move to the new MOVE op. Both ops should have the same Memory-Deps
      for (Front = (*TempListIter).Successors->begin(),
           Back = (*TempListIter).Successors->end(); 
           Front != Back; ) {
        // first find the DagNode for the Successor op
        TempListIter2 = List->begin();
        while ((*TempListIter2).GetOp()->GetOpId() != 
               (*Front).GetOp()->GetOpId()) 
          TempListIter2++; 
        // find the edgetype
        edgetype = (*Front).GetDependencyType();
        // increment now (Front may be removed later) 
        Front++;
        // if an Output-Dep, want to remove this successor from 
        // original op and add it to the new MOVE op.
        if (edgetype == ET_REGOUT) {
          // Remove this Successor/Predecessor pair from original op
          Front = (*TempListIter).RemoveSuccessor(edgetype, 
                                                  (*TempListIter2).GetOp());
          // Reset Back
          Back = (*TempListIter).Successors->end();
          ddderr ("\nRemoveSuccessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*TempListIter).GetOp()->GetOpId() << "\n");  
          (*TempListIter2).RemovePredecessor(edgetype, 
                                             (*TempListIter).GetOp());
          ddderr ("\nRemovePredecessor (opId = " << (*TempListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << "\n");
          // Add this Successor/Predecessor pair to new MOVE op
          rc = (*ListIter).AddSuccessor(edgetype, 
                                        (*TempListIter2).GetOp(), 
                                        &(*TempListIter2));   
          ddderr ("\nAddSuccessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*ListIter).GetOp()->GetOpId() << ", now " << rc << " Successors\n");
          rc = (*TempListIter2).AddPredecessor(edgetype, 
                                               (*ListIter).GetOp(), 
                                               &(*ListIter));
          ddderr ("\nAddPredecessor (opId = " << (*ListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
        }
      }
      
      // Also need to fix Predecessors if we rename for Output/Anti-Deps
      // Output- and Anti-Deps move to the new MOVE op. Both ops should 
      // have the same Memory-Deps
      for (Front = (*TempListIter).Predecessors->begin(),
           Back = (*TempListIter).Predecessors->end(); 
           Front != Back; ) {
        // first find the DagNode for the Predecessor op
        TempListIter2 = List->begin();
        while ((*TempListIter2).GetOp()->GetOpId() != 
               (*Front).GetOp()->GetOpId()) 
          TempListIter2++; 
        // find the edgetype
        edgetype = (*Front).GetDependencyType();
        // increment now (Front may be removed later) 
        Front++;
        // if an Output-Dep, want to remove this predecessor from 
        // original op and add it to the new MOVE op.
        if (edgetype == ET_REGOUT) {
          // Remove this Successor/Predecessor pair from original op
          Front = (*TempListIter).RemovePredecessor(edgetype, 
                                                  (*TempListIter2).GetOp());
          // Reset Back
          Back = (*TempListIter).Predecessors->end();
          ddderr ("\nRemovePredecessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*TempListIter).GetOp()->GetOpId() << "\n");  
          (*TempListIter2).RemoveSuccessor(edgetype, 
                                             (*TempListIter).GetOp());
          ddderr ("\nRemoveSuccessor (opId = " << (*TempListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << "\n");
          // Add this Successor/Predecessor pair to new MOVE op
          rc = (*ListIter).AddPredecessor(edgetype, 
                                        (*TempListIter2).GetOp(), 
                                        &(*TempListIter2));   
          ddderr ("\nAddPredecessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*ListIter).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
          rc = (*TempListIter2).AddSuccessor(edgetype, 
                                               (*ListIter).GetOp(), 
                                               &(*ListIter));
          ddderr ("\nAddSuccessor (opId = " << (*ListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
        }
        // if an Anti-Dep, want to remove this predecessor from 
        // original op and add it to the new MOVE op.
        if (edgetype == ET_REGANTI) {
          // Remove this Successor/Predecessor pair from original op
          Front = (*TempListIter).RemovePredecessor(edgetype, 
                                                  (*TempListIter2).GetOp());
          // Reset Back
          Back = (*TempListIter).Predecessors->end();
          ddderr ("\nRemovePredecessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*TempListIter).GetOp()->GetOpId() << "\n");  
          (*TempListIter2).RemoveSuccessor(edgetype, 
                                             (*TempListIter).GetOp());
          ddderr ("\nRemoveSuccessor (opId = " << (*TempListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << "\n");
          // Add this Successor/Predecessor pair to new MOVE op
          rc = (*ListIter).AddPredecessor(edgetype, 
                                        (*TempListIter2).GetOp(), 
                                        &(*TempListIter2));   
          ddderr ("\nAddPredecessor (opId = " << (*TempListIter2).GetOp()->GetOpId() << ") of opId = " << (*ListIter).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
          rc = (*TempListIter2).AddSuccessor(edgetype, 
                                               (*ListIter).GetOp(), 
                                               &(*ListIter));
          ddderr ("\nAddSuccessor (opId = " << (*ListIter).GetOp()->GetOpId() << ") of opId = " << (*TempListIter2).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
        }
      }
      
      copy_dynamic_op_increase += ((legoRegion *) op->GetParentBlockPtr())->GetWeight(); 
      
      // Now that we are renaming for dom //ism (renaming scheduled ops), 
      // need to make sure the the copy op doesn't appear before 
      // any other scheduled ops or DoTheMessyStuff may not work. 
      // Trust me on this one. 
      if (op->GetSchedTime() != UNSCHEDULED) {
        if (last_op_in_multiop->GetNextLink() == NULL) {
          AddMidOp(new_op, last_op_in_multiop->GetPrevLink());
          DoTheMessyStuff(last_op_in_multiop, (legoProc *) FindParentRegionType (RT_PROC, last_op_in_multiop));
        }
        else {
          AddMidOp(new_op, last_op_in_multiop);
        }
      }
      else {
        AddMidOp(new_op, op);
      }
      dderr("RENAME: Copy added (OpId =  " << MaxOpId << ")\n");
      
      // need to initialize mdes_info and ru_info pointers
      L_build_oper_mdes_info (new_op);
      L_create_ru_info_oper (new_op);
    }
  }
  // Now reset ListPtr to the original Op Node and ListPtr Node
  ListPtr = List->begin();
  while ((*ListPtr).GetOp()->GetOpId() != orig_op_id) ListPtr++; 
  Op = ListPtr;
  ListPtr++;
  
  return (NO_RENAMING_CONFLICT);
}

int list_scheduler::IsRemoteMergeProblem (legoOprd *def, legoOprd *orig_def)
{  
  
  legoOprd *oprd; 

  if ((def != orig_def) && 
      (((legoRegion *) def->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() == Region) &&
      DescendantofBlock( (int) def->GetParentOpPtr()->GetParentBlockPtr(), orig_def->GetParentOpPtr() )) {
    dderr("RENAME: IsRemoteMergeProblem = TRUE\n");
    //cerr << "\n\nWarning: RemoteMergeProblem for opId = " << orig_def->GetParentOpPtr()->GetOpId() << " and opId = " << def->GetParentOpPtr()->GetOpId() << "\n\n";
    // Expensive to figure out that this op has a merge problem (LiveVars() 
    // need to be redone). Make as a MergeProblem for future scheduling 
    // attempts
    oprd = new legoOprd; 
    oprd->SetOprdType (OT_LITERAL_I); 
    oprd->SetLiteralInteger(0); 
    AddLcAttribute ("merge_problem", oprd, orig_def->GetParentOpPtr(), 
                    (legoProc *) FindParentRegionType (RT_PROC, orig_def->GetParentOpPtr())); 
    return TRUE; 
  }
  return FALSE; 
}

int list_scheduler::IsMergeProblem (legoOprd *orig_def)
{  
  legoOprd *use, *def;
  oprdList *defs, *uses;
  edgeList *edgelist;
  opEdges *edge;
  int AnyTreegionLiveIn = FALSE; 
  int UsePreceedsDefInBlock; 
  legoOp *predecessor_op; 

  dderr("RENAME: IsMergeProblem\n");

  if (FindLcAttribute("merge_problem", orig_def->GetParentOpPtr()) != NULL) {
    return TRUE; 
  }
  
  // there is a merge problem if a use outside of the treegion has  
  // another reaching def from inside the treegion which dominates it.

  for (uses = Chains->GetDUChains()->Lookup (orig_def);
       (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
       uses = uses->GetNextListPtr()) {
    use = uses->GetOprdPtr();

    // first determine if this use is from outside of treegion or from 
    // within the treegion but not dominated by orig_def (due to loopback). 
    // Because of the nature of treegions, there can not be a 
    // merge problem from within a treegion unless otherwise.

    // Determine if this use preceeds the defining op in its own block 
    UsePreceedsDefInBlock = FALSE; 
    for (predecessor_op = orig_def->GetParentOpPtr(); 
         predecessor_op != NULL; 
         predecessor_op = predecessor_op->GetPrevLink()) {
      if (predecessor_op == use->GetParentOpPtr()) {
        UsePreceedsDefInBlock = TRUE; 
        break; 
      }
    }
    if ((((legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() != Region) || 
        (!DescendantofBlock( (int) orig_def->GetParentOpPtr()->GetParentBlockPtr(), use->GetParentOpPtr() ) || UsePreceedsDefInBlock)) {
      for (defs = Chains->GetUDChains()->Lookup (use);
           (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
           defs = defs->GetNextListPtr()) {
        def = defs->GetOprdPtr();
        // if def != orig_def and is from the same treegion and orig_def is 
        // dominated by def, then we have a merge problem.
        if ((def != orig_def) && 
            (((legoRegion *) def->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() == Region) &&
            DescendantofBlock( (int) def->GetParentOpPtr()->GetParentBlockPtr(), orig_def->GetParentOpPtr() )) {
          dderr("RENAME: IsMergeProblem = TRUE\n");
          return TRUE; 
        }
        // There is also potential for a problem if renaming results in 
        // renaming of the same operand live-in to this treegion if global 
        // renaming is used. This means that it could be incorrect to 
        // speculate the original op even after global renaming. 
        for (edgelist = Region->GetInEdgesPtr();
             edgelist != NULL; edgelist = edgelist->GetNextListPtr()) {
          if ((edge = edgelist->GetEdgePtr()) != NULL)
            AnyTreegionLiveIn = anyliveout (orig_def->GetParentOpPtr(), edge);
          if (AnyTreegionLiveIn) break;
        }
        if (AnyTreegionLiveIn) {
          dderr("RENAME: IsMergeProblem = TRUE due to TreegionLiveIn\n");
          return TRUE; 
        }
      }
    }
  }
  dderr("RENAME: IsMergeProblem = FALSE\n");
  return FALSE; 
}

int list_scheduler::Rename (legoOp *op, int RegNum, knobs *Knobs, legoRegion *proc_ptr, 
            int Final_Pass, int IncMaxRegNum, int Hazardous)
{
  int UseOutsideTreeOrNotDom = FALSE, UseInsideTreeAndDom = FALSE, MergeProblem = FALSE;
  edgeList *edgelist;
  opEdges *edge;
  legoOprd *destoprd;
  legoOprd *use;
  oprdList *uses;
  int UsePreceedsDefInBlock; 
  legoOp *predecessor_op; 
  int rn_conflict; 
  char *regiontype, fully_if_convert;
  int FullyIfConverted; 
  
  derr( ">> Rename(): renaming op " << op->GetOpId() << "\n" );
  
  // Data-Flow analysis (LiveVars()/RDefs()) not yet sophisticated enough 
  // to support renaming for FICTs
  Knobs->SetDefaultPanel ("ccom");
  Knobs->Read ("region", regiontype);
  Knobs->Read ("fully-if-convert", fully_if_convert);
  FullyIfConverted = FALSE;
  if ((strcmp (regiontype, "FICT") == 0) || 
      (fully_if_convert && Final_Pass)) {
    FullyIfConverted = TRUE;
  }
  if (FullyIfConverted == TRUE) {
    return (RENAMING_CONFLICT);
  }
  
  // Need to determine what type of renaming is required
  // If any dests are other then OT_REG. This op actually can not be 
  // scheduled at this time (renaming only allowed for OT_REG)
  for (destoprd = op->GetDestOprdPtr(); 
       destoprd != NULL; 
       destoprd = destoprd->GetNextOprdPtr()) {
    if ((destoprd->GetOprdType() != OT_REG) && 
        (destoprd->GetOprdType() != OT_UNDEFINED)) {
      return (RENAMING_CONFLICT);
    }
    // also can not rename registers already bound by register renaming
    if (destoprd->GetOprdRegType() == RT_BR) {
      return (RENAMING_CONFLICT); 
    }
  }

  // Need to determine if there are any uses outside of treegion for this op 
  // or if any uses from within treegion are not dominated by this op 
  for (destoprd = op->GetDestOprdPtr(); 
       destoprd != NULL; 
       destoprd = destoprd->GetNextOprdPtr()) {
    for (uses = Chains->GetDUChains()->Lookup (destoprd);
         (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
         uses = uses->GetNextListPtr()) {
      use = uses->GetOprdPtr();
      // Determine if this use preceeds the defining op in its own block 
      UsePreceedsDefInBlock = FALSE; 
      for (predecessor_op = op; 
           predecessor_op != NULL; 
           predecessor_op = predecessor_op->GetPrevLink()) {
        if (predecessor_op == use->GetParentOpPtr()) {
          UsePreceedsDefInBlock = TRUE; 
          break; 
        }
      }
      if ((((legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() != Region) || 
          (!DescendantofBlock( (int) destoprd->GetParentOpPtr()->GetParentBlockPtr(), use->GetParentOpPtr() ) || UsePreceedsDefInBlock)) {
        UseOutsideTreeOrNotDom = TRUE;
        break;
      }
    }
    if (UseOutsideTreeOrNotDom) break; 
  }

  if (!UseOutsideTreeOrNotDom) {
    dderr ("RENAMING: SimpleRename\n");
    SimpleRename(op, RegNum, IncMaxRegNum);
  }
  else {
    // A copy must be inserted if a use outside of the treegion 
    // (live-out) has more than one reaching definition from within 
    // the treegion. Renaming just one of the reaching defs would be 
    // incorrect. This happens if the reaching defs merge into a use. 
    // I call this the MergeProblem. 
    if (!Hazardous) {
      for (destoprd = op->GetDestOprdPtr(); 
           destoprd != NULL; 
           destoprd = destoprd->GetNextOprdPtr()) {
        if (destoprd->GetOprdType() != OT_UNDEFINED) 
          MergeProblem = IsMergeProblem(destoprd);
        if (MergeProblem) break;
      } 
    }
    else {
      // It is more hazardous to rename to the same RegNum during operation 
      // combining. This can introduce output or anti deps that were not 
      // seen during BuildDag() and can result in-correct code. 
      MergeProblem = TRUE; 
    }
    if (MergeProblem) {
      // only continue by inserting a copy op if this op has a use from 
      // within the Treegion that it dominates. This will also stop 
      // recursive replacement of copy ops as they will not have uses from 
      // within the Treegion that they dominate
      for (destoprd = op->GetDestOprdPtr(); 
           destoprd != NULL; 
           destoprd = destoprd->GetNextOprdPtr()) {
        for (uses = Chains->GetDUChains()->Lookup (destoprd);
             (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
             uses = uses->GetNextListPtr()) {
          use = uses->GetOprdPtr();
          // Determine if this use preceeds the defining op in its own block 
          UsePreceedsDefInBlock = FALSE; 
          for (predecessor_op = op; 
               predecessor_op != NULL; 
               predecessor_op = predecessor_op->GetPrevLink()) {
            if (predecessor_op == use->GetParentOpPtr()) {
              UsePreceedsDefInBlock = TRUE; 
              break; 
            }
          }
          if ((((legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() == Region) &&
              (DescendantofBlock( (int) destoprd->GetParentOpPtr()->GetParentBlockPtr(), use->GetParentOpPtr() ) && !UsePreceedsDefInBlock)) {
            UseInsideTreeAndDom = TRUE;
            break;
          }
        }
        if (UseInsideTreeAndDom) break; 
      }
      
      if (UseInsideTreeAndDom) {
        
        dderr ("RENAMING: SimpleRenameWithCopy\n");
        rn_conflict = AddCopyOps(op);

        if (rn_conflict == RENAMING_CONFLICT) {
          derr("RENAMING: rn_conflict, AddCopyOp() unable to schedule copy \n");
          return (RENAMING_CONFLICT);
        }
        
        // I can get by with just calling SimpleRename because RDefs 
        // have been adjusted during AddCopyOps() so that the only uses of 
        // this op (including new copy op) are now all within the Treegion 
        SimpleRename(op, RegNum, IncMaxRegNum);
        
        dderr ("Copy op added while renaming op " << op->GetOpId() << "\n");
        
        // AddCopyOps() is now incrementally updates RDefs
      }
      else {
        derr("RENAMING: rn_conflict, Merge Problem, no uses dominated by op in Treegion\n");
        return (RENAMING_CONFLICT);
      }
    }
    else {
      dderr ("RENAMING: GlobalRename\n");
      // It is also still possible that there is a 'remote' Merge Problem 
      // not caught by the original IsMergeProblem() check.
      // If there is, finish with the global rename but return a 
      // RENAMING_CONFLICT (possible to re-do Rename with Hazardous, 
      // forcing a copy to be inserted, but this is infrequent).
      MergeProblemDuringGlobal = FALSE;
      GlobalRename(op, RegNum, IncMaxRegNum);
      if (MergeProblemDuringGlobal == TRUE) {
        return (RENAMING_CONFLICT);
      }
    }
  }
  return (NO_RENAMING_CONFLICT);
}

int list_scheduler::anyliveout (legoOp *op, opEdges *edge)
{
  attrs *liveattr;
  legoOprd *def, *liveoprd;

  liveattr = FindLiveAttribute (edge);
  if (liveattr == NULL) return 0;

  //  for (def = FindFirstDef (op); def != NULL; def = def->GetNextOprdPtr())
  for (def = op->GetDestOprdPtr(); def != NULL; def = def->GetNextOprdPtr())
    {
      for (liveoprd = liveattr->GetAttrOprdPtr();
           liveoprd != NULL; liveoprd = liveoprd->GetNextOprdPtr())
        {
          if (liveoprd->GetOprdType() != def->GetOprdType())
            continue;  // different type
          if (liveoprd->GetOprdRegNum() != def->GetOprdRegNum())
            continue;  // different register number / macro
          if ((def->GetOprdType() != OT_MACRO) && 
              (liveoprd->GetOprdFileType() != def->GetOprdFileType()))
            continue;  // different file type. NOT IMPORTANT for Macro Regs

          // If we get here, the def is live-out along edge.
          return 1;
        } // end for
    } // end for

  // Check the return macro for BRLs too.
  if (op->GetOpcode() == BRL)
    {
      def = FindReturnMacro (op);
      if (def == NULL) return 0;  // we're done!
      for (liveoprd = liveattr->GetAttrOprdPtr();
           liveoprd != NULL; liveoprd = liveoprd->GetNextOprdPtr())
        {
          if (liveoprd->GetOprdType() != OT_MACRO) continue;
          if (liveoprd->GetOprdRegNum() != def->GetOprdRegNum()) continue;
          if (liveoprd->GetOprdFileType() != def->GetOprdFileType()) continue;

          // If we get here, the def is live-out along edge.
          return 1;
        } // end for
    } // end if

  return 0;
} // end anyliveout

void list_scheduler::RemoveOutputDepsAfterRename (legoOprd *renamed_def)
{
  legoOp *parent_op; 
  vector < BigListElement >::iterator ListPtrParent, ListPtrPredecessor, ListPtrSuccessor;
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  legoOprd *def1, *def2; 
  int StillOutputDependent;

  parent_op = renamed_def->GetParentOpPtr(); 

  // Renaming scope sometimes beyond Treegion scope
  if (((legoRegion *) parent_op->GetParentBlockPtr())->GetParentPtr() 
      != Region) {
    return; 
  }
  
  // Find the op DagNode
  ListPtrParent = List->begin();
  while ((*ListPtrParent).GetOp()->GetOpId() != 
         parent_op->GetOpId()) 
    ListPtrParent++; 
  
  for (Front = (*ListPtrParent).Successors->begin(),
       Back = (*ListPtrParent).Successors->end(); 
       Front != Back; ) {

    edgetype = (*Front).GetDependencyType();

    // Find the DagNode for the Successor op
    ListPtrSuccessor = List->begin();
    while ((*ListPtrSuccessor).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtrSuccessor++; 
    
    // increment now (Front may be removed later) 
    Front++;
    
    if (edgetype == ET_REGOUT) {
      
      // This outputdep could be do to another def. Verify that there is no 
      // longer an outputdep.
      StillOutputDependent = FALSE;
      for (def1 = (*ListPtrSuccessor).GetOp()->GetDestOprdPtr();
           def1 != NULL;
           def1 = def1->GetNextOprdPtr()) {
        for (def2 = parent_op->GetDestOprdPtr(); 
             def2 != NULL;
             def2 = def2->GetNextOprdPtr()) {
          if ( def1->GetOprdType() != def2->GetOprdType() ) continue;
          if ( def1->GetOprdRegNum() != def2->GetOprdRegNum() ) continue;
          if ( def1->GetOprdType() != OT_MACRO &&
              def1->GetOprdFileType() != def2->GetOprdFileType() )
            continue; 
          StillOutputDependent = TRUE;
          break; 
        }
        if (StillOutputDependent) break;
      }
      
      if (!StillOutputDependent) {
        // Remove this Pair
        Front = (*ListPtrParent).RemoveSuccessor(ET_REGOUT, 
                                                 (*ListPtrSuccessor).GetOp());
        // Reset Back
        Back = (*ListPtrParent).Successors->end();
        temperr ("\nRemoveSuccessor (opId = " << (*ListPtrSuccessor).GetOp()->GetOpId() << ") of opId = " << (*ListPtrParent).GetOp()->GetOpId() << "\n");  
        (*ListPtrSuccessor).RemovePredecessor(ET_REGOUT, 
                                              (*ListPtrParent).GetOp());
        temperr ("\nRemovePredecessor (opId = " << (*ListPtrParent).GetOp()->GetOpId() << ") of opId = " << (*ListPtrSuccessor).GetOp()->GetOpId() << "\n");
      }
    }
  }
  
  for (Front = (*ListPtrParent).Predecessors->begin(),
       Back = (*ListPtrParent).Predecessors->end(); 
       Front != Back; ) {

    edgetype = (*Front).GetDependencyType();

    // Find the DagNode for the Predecessor op
    ListPtrPredecessor = List->begin();
    while ((*ListPtrPredecessor).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtrPredecessor++; 
    
    // increment now (Front may be removed later) 
    Front++;
    
    if (edgetype == ET_REGOUT) {
      
      // This outputdep could be do to another def. Verify that there is no 
      // longer an outputdep.
      StillOutputDependent = FALSE;
      for (def1 = (*ListPtrPredecessor).GetOp()->GetDestOprdPtr();
           def1 != NULL;
           def1 = def1->GetNextOprdPtr()) {
        for (def2 = parent_op->GetDestOprdPtr(); 
             def2 != NULL;
             def2 = def2->GetNextOprdPtr()) {
          if ( def1->GetOprdType() != def2->GetOprdType() ) continue;
          if ( def1->GetOprdRegNum() != def2->GetOprdRegNum() ) continue;
          if ( def1->GetOprdType() != OT_MACRO &&
              def1->GetOprdFileType() != def2->GetOprdFileType() )
            continue; 
          StillOutputDependent = TRUE;
          break; 
        }
        if (StillOutputDependent) break;
      }
      
      if (!StillOutputDependent) {
        // Remove this Pair
        Front = (*ListPtrParent).RemovePredecessor(ET_REGOUT, 
                                                 (*ListPtrPredecessor).GetOp());
        // Reset Back
        Back = (*ListPtrParent).Predecessors->end();
        temperr ("\nRemovePredecessor (opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << ") of opId = " << (*ListPtrParent).GetOp()->GetOpId() << "\n");  
        (*ListPtrPredecessor).RemoveSuccessor(ET_REGOUT, 
                                              (*ListPtrParent).GetOp());
        temperr ("\nRemoveSuccessor (opId = " << (*ListPtrParent).GetOp()->GetOpId() << ") of opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << "\n");
      }
    }
  }
}

void list_scheduler::RemoveOutputDepsAfterRenameUp (legoOprd *renamed_def)
{
  legoOp *parent_op; 
  vector < BigListElement >::iterator ListPtrParent, ListPtrPredecessor;
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  legoOprd *def1, *def2; 
  int StillOutputDependent;

  parent_op = renamed_def->GetParentOpPtr(); 

  // Renaming scope sometimes beyond Treegion scope
  if (((legoRegion *) parent_op->GetParentBlockPtr())->GetParentPtr() 
      != Region) {
    return; 
  }
  
  // Find the op DagNode
  ListPtrParent = List->begin();
  while ((*ListPtrParent).GetOp()->GetOpId() != 
         parent_op->GetOpId()) 
    ListPtrParent++; 
  
  for (Front = (*ListPtrParent).Predecessors->begin(),
       Back = (*ListPtrParent).Predecessors->end(); 
       Front != Back; ) {

    edgetype = (*Front).GetDependencyType();

    // Find the DagNode for the Predecessor op
    ListPtrPredecessor = List->begin();
    while ((*ListPtrPredecessor).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtrPredecessor++; 
    
    // increment now (Front may be removed later) 
    Front++;
    
    if (edgetype == ET_REGOUT) {
      
      // This outputdep could be do to another def. Verify that there is no 
      // longer an outputdep.
      StillOutputDependent = FALSE;
      for (def1 = (*ListPtrPredecessor).GetOp()->GetDestOprdPtr();
           def1 != NULL;
           def1 = def1->GetNextOprdPtr()) {
        for (def2 = parent_op->GetDestOprdPtr(); 
             def2 != NULL;
             def2 = def2->GetNextOprdPtr()) {
          if ( def1->GetOprdType() != def2->GetOprdType() ) continue;
          if ( def1->GetOprdRegNum() != def2->GetOprdRegNum() ) continue;
          if ( def1->GetOprdType() != OT_MACRO &&
              def1->GetOprdFileType() != def2->GetOprdFileType() )
            continue; 
          StillOutputDependent = TRUE;
          break; 
        }
        if (StillOutputDependent) break;
      }
      
      if (!StillOutputDependent) {
        // Remove this Pair
        Front = (*ListPtrParent).RemovePredecessor(ET_REGOUT, 
                                                 (*ListPtrPredecessor).GetOp());
        // Reset Back
        Back = (*ListPtrParent).Predecessors->end();
        temperr ("\nRemovePredecessor (opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << ") of opId = " << (*ListPtrParent).GetOp()->GetOpId() << "\n");  
        (*ListPtrPredecessor).RemoveSuccessor(ET_REGOUT, 
                                              (*ListPtrParent).GetOp());
        temperr ("\nRemoveSuccessor (opId = " << (*ListPtrParent).GetOp()->GetOpId() << ") of opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << "\n");
      }
    }
  }
}

void list_scheduler::RemoveAntiDepsAfterUseRename (legoOprd *renamed_use)
{
  legoOp *parent_op; 
  vector < BigListElement >::iterator ListPtrParent, ListPtrSuccessor;
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  legoOprd *use, *def; 
  int StillAntiDependent, def_regid, use_regid;

  parent_op = renamed_use->GetParentOpPtr(); 
  
  // Renaming scope sometimes beyond Treegion scope
  if (((legoRegion *) parent_op->GetParentBlockPtr())->GetParentPtr() 
      != Region) {
    return; 
  }
  
  // Find the op DagNode
  ListPtrParent = List->begin();
  while ((*ListPtrParent).GetOp()->GetOpId() != 
         parent_op->GetOpId()) 
    ListPtrParent++; 
  
  for (Front = (*ListPtrParent).Successors->begin(),
       Back = (*ListPtrParent).Successors->end(); 
       Front != Back; ) {

    edgetype = (*Front).GetDependencyType();

    // Find the DagNode for the Successor op
    ListPtrSuccessor = List->begin();
    while ((*ListPtrSuccessor).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtrSuccessor++; 
    
    // increment now (Front may be removed later) 
    Front++;
    
    if (edgetype == ET_REGANTI) {
      
      // This antidep could be do to another use. Verify that there is no 
      // longer an antidep.
      StillAntiDependent = FALSE;
      for (def = (*ListPtrSuccessor).GetOp()->GetDestOprdPtr();
           def != NULL;
           def = def->GetNextOprdPtr()) {
        for (use = parent_op->GetSrcOprdPtr(); 
             use != NULL;
             use = use->GetNextOprdPtr()) {
          if ( def->GetOprdType() != use->GetOprdType() ) continue;
          if ( def->GetOprdRegNum() != use->GetOprdRegNum() ) continue;
          if ( def->GetOprdType() != OT_MACRO &&
              def->GetOprdFileType() != use->GetOprdFileType() )
            continue; 
          StillAntiDependent = TRUE;
          break; 
        }
        if (StillAntiDependent) break;
        // The use could be the btr operand of a BRL, check other sources
        // Need to assume that BRLs use all INT_P*'s, FLT_P*'s, DBL_P*'s. 
        if (parent_op->GetOpcode() == BRL) {
          for (use_regid = INT_P1; use_regid <= DBL_P2; use_regid++) {
            if ( def->GetOprdType() != OT_MACRO ) continue; 
            if ( def->GetOprdRegNum() != use_regid ) continue;
            StillAntiDependent = TRUE;
            break; 
          }
        }
        if (StillAntiDependent) break;
      }
      if (!StillAntiDependent && 
          ((*ListPtrSuccessor).GetOp()->GetOpcode() == BRL)) {
        for (def_regid = INT_P1; def_regid <= DBL_RET; def_regid++) {
          for (use = parent_op->GetSrcOprdPtr(); 
               use != NULL;
               use = use->GetNextOprdPtr()) {
            if ( use->GetOprdType() != OT_MACRO ) continue;
            if ( def_regid != use->GetOprdRegNum() ) continue;
            StillAntiDependent = TRUE;
            break; 
          }
          if (StillAntiDependent) break;
          // BRLs followed by BRL alway remain dependent
          if (parent_op->GetOpcode() == BRL) {
            StillAntiDependent = TRUE;
          }
          if (StillAntiDependent) break;
        }
      }
        
      if (!StillAntiDependent) {
        // Remove this Pair
        Front = (*ListPtrParent).RemoveSuccessor(ET_REGANTI, 
                                                 (*ListPtrSuccessor).GetOp());
        // Reset Back
        Back = (*ListPtrParent).Successors->end();
        temperr ("\nRemoveSuccessor (opId = " << (*ListPtrSuccessor).GetOp()->GetOpId() << ") of opId = " << (*ListPtrParent).GetOp()->GetOpId() << "\n");  
        (*ListPtrSuccessor).RemovePredecessor(ET_REGANTI, 
                                              (*ListPtrParent).GetOp());
        temperr ("\nRemovePredecessor (opId = " << (*ListPtrParent).GetOp()->GetOpId() << ") of opId = " << (*ListPtrSuccessor).GetOp()->GetOpId() << "\n");
      }
    }
  }
}

void list_scheduler::RemoveAntiDepsAfterDefRename (legoOprd *renamed_def)
{
  legoOp *parent_op; 
  vector < BigListElement >::iterator ListPtrParent, ListPtrPredecessor;
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  legoOprd *use, *def; 
  int StillAntiDependent, def_regid, use_regid;

  parent_op = renamed_def->GetParentOpPtr(); 
  
  // Renaming scope sometimes beyond Treegion scope
  if (((legoRegion *) parent_op->GetParentBlockPtr())->GetParentPtr() 
      != Region) {
    return; 
  }
  
  // Find the op DagNode
  ListPtrParent = List->begin();
  while ((*ListPtrParent).GetOp()->GetOpId() != 
         parent_op->GetOpId()) 
    ListPtrParent++; 
  
  for (Front = (*ListPtrParent).Predecessors->begin(),
       Back = (*ListPtrParent).Predecessors->end(); 
       Front != Back; ) {

    edgetype = (*Front).GetDependencyType();

    // Find the DagNode for the Predecessor op
    ListPtrPredecessor = List->begin();
    while ((*ListPtrPredecessor).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtrPredecessor++; 
    
    // increment now (Front may be removed later) 
    Front++;
    
    if (edgetype == ET_REGANTI) {
      
      // This antidep could be do to another def. Verify that there is no 
      // longer an antidep.
      StillAntiDependent = FALSE;
      for (def = parent_op->GetDestOprdPtr();
           def != NULL;
           def = def->GetNextOprdPtr()) {
        for (use = (*ListPtrPredecessor).GetOp()->GetSrcOprdPtr(); 
             use != NULL;
             use = use->GetNextOprdPtr()) {
          if ( def->GetOprdType() != use->GetOprdType() ) continue;
          if ( def->GetOprdRegNum() != use->GetOprdRegNum() ) continue;
          if ( def->GetOprdType() != OT_MACRO &&
              def->GetOprdFileType() != use->GetOprdFileType() )
            continue; 
          StillAntiDependent = TRUE;
          break; 
        }
        if (StillAntiDependent) break;
        // The use could be the btr operand of a BRL, check other sources
        // Need to assume that BRLs use all INT_P*'s, FLT_P*'s, DBL_P*'s. 
        if ((*ListPtrPredecessor).GetOp()->GetOpcode() == BRL) {
          for (use_regid = INT_P1; use_regid <= DBL_P2; use_regid++) {
            if ( def->GetOprdType() != OT_MACRO ) continue; 
            if ( def->GetOprdRegNum() != use_regid ) continue;
            StillAntiDependent = TRUE;
            break; 
          }
        }
        if (StillAntiDependent) break;
      }
      if (!StillAntiDependent && 
          (parent_op->GetOpcode() == BRL)) {
        for (def_regid = INT_P1; def_regid <= DBL_RET; def_regid++) {
          for (use = (*ListPtrPredecessor).GetOp()->GetSrcOprdPtr();
               use != NULL;
               use = use->GetNextOprdPtr()) {
            if ( use->GetOprdType() != OT_MACRO ) continue;
            if ( def_regid != use->GetOprdRegNum() ) continue;
            StillAntiDependent = TRUE;
            break; 
          }
          if (StillAntiDependent) break;
          // BRLs followed by BRL alway remain dependent
          if ((*ListPtrPredecessor).GetOp()->GetOpcode() == BRL) {
            StillAntiDependent = TRUE;
          }
          if (StillAntiDependent) break;
        }
      }
        
      if (!StillAntiDependent) {
        // Remove this Pair
        Front = (*ListPtrParent).RemovePredecessor(ET_REGANTI, 
                                                   (*ListPtrPredecessor).GetOp());
        // Reset Back
        Back = (*ListPtrParent).Predecessors->end();
        temperr ("\nRemovePredecessor (opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << ") of opId = " << (*ListPtrParent).GetOp()->GetOpId() << "\n");  
        (*ListPtrPredecessor).RemoveSuccessor(ET_REGANTI, 
                                              (*ListPtrParent).GetOp());
        temperr ("\nRemoveSuccessor (opId = " << (*ListPtrParent).GetOp()->GetOpId() << ") of opId = " << (*ListPtrPredecessor).GetOp()->GetOpId() << "\n");
      }
    }
  }
}


/*
 * AddDPRemoveAttribute
 *   op = op to annotate
 *   returns: new attr attached to op
 *
 * Attaches a new attr to the op indicating that this op should be removed 
 * after list scheduling this region. Ops are removed when dominator 
 * parallelism allows them to be merged with other ops. Removing them 
 * before list scheduling screws up the dag and priority lists, so it 
 * is delayed until after scheduling. 
 * 
 */
static attrs *
AddDPRemoveAttribute (legoOp *op)
{
  legoRegion *block;
  legoOprd *oprd;
  attrs *attr;

  block = (legoRegion *) op->GetParentBlockPtr();
  if (block == NULL) return NULL;

  oprd = new legoOprd;

  attr = AddLcAttribute ("dp_remove", oprd, op,
                           (legoProc *) FindParentRegionType (RT_PROC, op));
  return attr;

}

/*
 * 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.
 */
void list_scheduler::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.
 */
void list_scheduler::add_to_existing_attr( attrs *Attr, legoOprd *NewOprd )
{
   legoOprd *OprdPtr, *ShadowPtr;

   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" );

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

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

   //   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.
 */
void list_scheduler::create_new_attr( opEdges *Edge, legoOprd *Oprd, legoProc *Proc )
{
  legoOprd *NewOprd = new legoOprd();

  derr( ">> create_new_attr\n" );

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

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

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

int list_scheduler::FixLiveVarsUp (legoOp *op, 
                                   legoOp *before_op, 
                                   legoProc *proc_ptr)
{
  attrs *liveattr;
  legoRegion *before_block_ptr, *block_ptr;
  edgeList *edgelist;
  opEdges *edge;
  legoOprd *def;

  before_block_ptr = (legoRegion *) before_op->GetParentBlockPtr();
  block_ptr = (legoRegion *) op->GetParentBlockPtr();

  while (block_ptr != before_block_ptr) {
    // For each block in treegion (excluding root), only one InEdge
    edgelist = block_ptr->GetInEdgesPtr();
    edge = edgelist->GetEdgePtr();
    for (def = op->GetDestOprdPtr(); 
         def != NULL; 
         def = def->GetNextOprdPtr()) {
      if (def->GetOprdType() != OT_UNDEFINED) {
        liveattr = FindLiveAttribute( edge );
        if ( liveattr != NULL ) { // exists
          add_to_existing_attr( liveattr, def );
        }
        else {
          create_new_attr( edge, def, proc_ptr );
        }
      }
    }
    block_ptr = block_ptr->GetParents()->GetRegionPtr();
  }
} // end FixLiveVarsUp

int list_scheduler::FixLiveVarsDown (legoOp *op, 
                                     opEdges *edge,
                                     legoProc *proc_ptr)
{
  attrs *liveattr;
  legoOprd *use;

  for (use = op->GetSrcOprdPtr(); 
       use != NULL; 
       use = use->GetNextOprdPtr()) {
    if ((use->GetOprdType() == OT_REG) ||
        (use->GetOprdType() == OT_MACRO)) {
      liveattr = FindLiveAttribute( edge );
      if ( liveattr != NULL ) { // exists
        add_to_existing_attr( liveattr, use );
      }
      else {
        create_new_attr( edge, use, proc_ptr );
      }
    }
  }

  for (use = op->GetPredOprdPtr(); 
       use != NULL; 
       use = use->GetNextOprdPtr()) {
    if ((use->GetOprdType() == OT_REG) ||
        (use->GetOprdType() == OT_MACRO)) {
      liveattr = FindLiveAttribute( edge );
      if ( liveattr != NULL ) { // exists
        add_to_existing_attr( liveattr, use );
      }
      else {
        create_new_attr( edge, use, proc_ptr );
      }
    }
  }

  if (op->GetOpcode() == BRL) {
    // Need to assume that BRLs use all INT_P*'s, FLT_P*'s, and DBL_P*'s. 
    legoOprd *Oprd = new legoOprd(); 
    // these are always MACRO regs
    Oprd->SetOprdType(OT_MACRO);
    for (int regid = INT_P1; regid <= DBL_P2; regid++) {
      Oprd->SetOprdRegNum(regid);
      liveattr = FindLiveAttribute( edge );
      if ( liveattr != NULL ) { // exists
        add_to_existing_attr( liveattr, Oprd );
      }
      else {
        create_new_attr( edge, Oprd, proc_ptr );
      }
    }
    delete Oprd; 
  }
} // end FixLiveVarsDown

int list_scheduler::FixLiveVarsFromUses(legoOprd *use, legoOp *before_op, 
                                        legoProc *proc_ptr) {

  attrs *liveattr;
  legoRegion *before_block_ptr, *block_ptr;
  edgeList *edgelist;
  opEdges *edge;

  before_block_ptr = (legoRegion *) before_op->GetParentBlockPtr();
  block_ptr = (legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr();

  while (block_ptr != before_block_ptr) {
    // For each block in treegion (excluding root), only one InEdge
    edgelist = block_ptr->GetInEdgesPtr();
    edge = edgelist->GetEdgePtr();
    liveattr = FindLiveAttribute( edge );
    if ( liveattr != NULL ) { // exists
      add_to_existing_attr( liveattr, use );
    }
    else {
      create_new_attr( edge, use, proc_ptr );
    }
    block_ptr = block_ptr->GetParents()->GetRegionPtr();
  }
} // end FixLiveVarsFromUses

int list_scheduler::AnyOutputDepsBetween(legoOp *op, legoOp *before_op, 
                                         legoOprd *compare_dest) {
  
  legoOp *traverse_op; 
  legoOprd *def; 

  if (op->GetPrevLink() == NULL) {
    traverse_op = op->GetInListPtr()->GetOpPtr(); 
  }
  else {
    traverse_op = op->GetPrevLink();
  }
  while (traverse_op != before_op) {
    if (DPG->AreOpsDependent(op, traverse_op) && 
        (FindLcAttribute( "dp_remove", traverse_op ) == NULL)) {
      for (def = traverse_op->GetDestOprdPtr(); 
           def != NULL; 
           def = def->GetNextOprdPtr()) {
        if (def->GetOprdType() != OT_UNDEFINED) {
          if ((def->GetOprdType() == OT_REG) &&
              (compare_dest->GetOprdType() == OT_REG) &&
              (def->GetOprdFileType() == 
               compare_dest->GetOprdFileType()) &&
              (def->GetOprdRegNum() == 
               compare_dest->GetOprdRegNum())) {
            return YES;
          }
          if ((def->GetOprdType() == OT_MACRO) &&
              (compare_dest->GetOprdType() == OT_MACRO) &&
              (def->GetOprdRegNum() == 
               compare_dest->GetOprdRegNum())) {
            return YES;
          }
        }
      }
    }
    if (traverse_op->GetPrevLink() == NULL) {
      traverse_op = traverse_op->GetInListPtr()->GetOpPtr(); 
    }
    else {
      traverse_op = traverse_op->GetPrevLink();
    }
  }
  return NO; 
}


// DoTheMessyStuff: This code allows branches to be scheduled above other 
// operations (or allows ops to move below branches) during scheduling.
// This usually results in copy of ops (depending on liveness out of the 
// branches. Priority lists, liveness, and reaching definitions are updated 
// incrementally. 
int list_scheduler::DoTheMessyStuff( legoOp *op, legoRegion *proc_ptr )
{

  legoOp *first_cmerge, *second_cmerge, *above_op, *next_above_op, *duplicate_op; 
  opEdges *first_edge, *second_edge;
  int TreegionExit, orig_op_id;
  opList *exit_ops; 
  legoOp *exit_op; 
  BigListElement Element;
  vector < BigListElement >::iterator ListIter, ListPtr2, ListPtr3;
  vector < SmallListElement >::iterator Front, Back;
  legoOprd *use, *use_first, *use_second, *def, *def_first, *def_second, *oprd; 
  oprdList *uses, *uses_first, *uses_second;
  oprdList *defs, *defs_first, *defs_second;
  oprdList *prev_use_first, *new_use_first, *prev_use_second, *new_use_second;
  oprdList *prev_def_first, *new_def_first, *prev_def_second, *new_def_second;
  enum edgeTypes edgetype;  
  int rc, eaid; 
  attrs *attrdictionary, *attrtail, *atscan;
  attrList *atlscan;
  legoOprd *btroprd, *cmppoprd, *PredOprd, *new_predicate;
  legoOp *cmppop, *pbrrop;
  oprdList *new_uses, *new_use, *prev_use, *oprd_list; 
  int one_dead;
  int UsePreceedsDefInBlock; 
  legoOp *predecessor_op;
  
  TreegionExit = NO; 
  for (exit_ops = Region->GetExitOpsPtr(); 
       exit_ops != NULL; 
       exit_ops = exit_ops->GetNextListPtr()) {
    if ((exit_op = exit_ops->GetOpPtr()) == op) {
      TreegionExit = YES; 
      break; 
    }
  }
  if ((op->GetOpcode() == BRU) ||  
      (op->GetOpcode() == DUMMY_BR) || 
      TreegionExit) {
    for (above_op = op->GetPrevLink();
         above_op != current_before_op; 
         above_op = above_op->GetPrevLink()) {
      if (above_op->GetOpcode() == C_MERGE) {
        break;
      }
      ddderr("\n *** Conflict for opId = " << op->GetOpId() << " ?????\n");
      if (DPG->AreOpsDependent(above_op, op)) {
        // not really a renaming conflict, but can not move ops 
        // below uncond branches (uncond branches should only occur 
        // as treegion exits) or other treegion exits
        ddderr("Yes there is a conflict\n");
        return (RENAMING_CONFLICT);
      }
    }
  }
  if (!TreegionExit && 
      ((op->GetOpcode() == BRCT) || 
       (op->GetOpcode() == BRCF))) { 

    first_cmerge = op->GetOutListPtr()->GetOpPtr(); 
    second_cmerge = op->GetOutListPtr()->GetNextListPtr()->GetOpPtr();
    first_edge = FindControlEdge (op, first_cmerge, 1);
    second_edge = FindControlEdge (op, second_cmerge, 1);
    
    for (next_above_op = op->GetPrevLink();
         ((next_above_op != current_before_op) && 
          (next_above_op->GetSchedTime() == UNSCHEDULED) && 
          (next_above_op->GetOpcode() != C_MERGE)); ) {
      above_op = next_above_op;
      next_above_op = above_op->GetPrevLink(); 
      
      // Store and BRLs no longer need to remain in blocks after moved down. 
      // They are now no longer speculative 
      if (IsStoreOp(above_op)) {
        oprd = new legoOprd;
        oprd->SetOprdType (OT_LITERAL_I);
        if (op->GetParentBlockPtr() == ((legoTreegion *)Region)->GetRoot()) {
          oprd->SetLiteralInteger(0);
        }
        else {
          oprd->SetLiteralInteger(((legoRegion *)current_before_op->GetParentBlockPtr())->GetRegionId());
        }
        AddLcAttribute ("no_longer_speculative", oprd, above_op, (legoProc *) proc_ptr);
      }
      if (above_op->GetOpcode() == BRL) {
        oprd = new legoOprd;
        oprd->SetOprdType (OT_LITERAL_I);
        if (op->GetParentBlockPtr() == ((legoTreegion *)Region)->GetRoot()) {
          oprd->SetLiteralInteger(0);
        }
        else {
          oprd->SetLiteralInteger(((legoRegion *)current_before_op->GetParentBlockPtr())->GetRegionId());
        }
        AddLcAttribute ("no_longer_speculative", oprd, above_op, (legoProc *) proc_ptr);
      }
      
      ddderr("\n *** Any for opId = " << op->GetOpId() << " ?????\n");
      if (DPG->AreOpsDependent(above_op, op)) {
        
        if (!AllowDownwardCodeMotion) return (RENAMING_CONFLICT);
        
        if (!(above_op->IsDummy())) {
          one_dead = FALSE;
          downward_motion_ops++;
        }

        if ((anyliveout(above_op, second_edge) ||
             IsStoreOp(above_op) ||  
             (above_op->GetOpcode() == BRL)) && 
            above_op->GetOpcode() != DEFINE) {
          duplicate_op = new legoOp(*above_op);
          duplicate_op->SetOpId(++MaxOpId);

          // May need to demote predicate if guarded by a predicate register
          if ((duplicate_op->GetOpcode() < CMPP) ||
              (duplicate_op->GetOpcode() > FCMPP_D_TRUE_AC_AC)) {
            PredOprd = duplicate_op->GetPredOprdPtr();
            if (PredOprd != NULL) {
              if (PredOprd->GetOprdType() == OT_REG) {
                // Needs demotion
                //cerr << "\nduplicate_op's (OpId = " << duplicate_op->GetOpId() << ") predicate (orig RegId = " << PredOprd->GetOprdRegNum() << ") demoted to ";

                // Clean-up RDefs before deleting oprd
                for (defs = Chains->GetUDChains()->Lookup (PredOprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  new_uses = NULL; 
                  for (uses = Chains->GetDUChains()->Lookup (def);
                       (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
                       uses = uses->GetNextListPtr()) {
                    use = uses->GetOprdPtr();
                    if (use != PredOprd) {
                      if (new_uses == NULL) {
                        new_uses = new oprdList;
                        new_uses->SetOprdPtr(use);
                        prev_use = new_uses;
                      }
                      else {
                        new_use = new oprdList;
                        new_use->SetOprdPtr(use);
                        prev_use->SetNextListPtr(new_use);
                        prev_use = new_use;
                      } 
                    }
                  }
                  if (Chains->GetDUChains()->NotFound() == FALSE) {
                    uses = Chains->GetDUChains()->Lookup (def);
                    delete uses; 
                    Chains->GetDUChains()->Set (def, new_uses);
                  }
                }
                Chains->GetUDChains()->Lookup (PredOprd);
                if (Chains->GetUDChains()->NotFound() == FALSE) {
                  Chains->GetUDChains()->Delete (PredOprd);
                }
                delete PredOprd; 
                
                // Find the CMPP op for branch 
                cmppoprd = op->GetSrcOprdPtr()->GetNextOprdPtr(); 
                cmppop = NULL;
                for (defs = Chains->GetUDChains()->Lookup (cmppoprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  cmppop = def->GetParentOpPtr(); // only one CMPP op should reach
                  break; 
                }
                
                dderr ("cmppop OpId is: " << cmppop->GetOpId() << "\n");
                
                if (cmppop == NULL) {
                  LegoFatal ("DoTheMessyStuff", "Can't find CMPP for branch");
                } 
                
                // Find the PBR op for branch 
                btroprd = op->GetSrcOprdPtr(); // should be 1st source
                pbrrop = NULL;
                for (defs = Chains->GetUDChains()->Lookup (btroprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
                  break; 
                }
                
                dderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
                
                if (pbrrop == NULL) {
                  LegoFatal ("DoTheMessyStuff", "Can't find PBRR/PBRA in block");
                } // end if
                
                if (op->GetOpcode() == BRCT) {
                  if (pbrrop->GetSrcOprdPtr()->GetLiteralControlBlock() == 
                      ((legoRegion *) second_cmerge->GetParentBlockPtr())->GetRegionId()) {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr());
                  }
                  else {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr()
                                                 ->GetNextOprdPtr());
                  }
                }
                else {
                  if (pbrrop->GetSrcOprdPtr()->GetLiteralControlBlock() == 
                      ((legoRegion *) second_cmerge->GetParentBlockPtr())->GetRegionId()) {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr()
                                                 ->GetNextOprdPtr());
                  }
                  else {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr());
                  }
                }
                // Assign demoted predicate
                new_predicate->SetNextOprdPtr(NULL);
                duplicate_op->SetPredOprdPtr(new_predicate);
                // Now adjust Chains 
                oprd_list = new oprdList;
                oprd_list->SetOprdPtr (cmppop->GetDestOprdPtr());
                Chains->GetUDChains()->Set (new_predicate, oprd_list); 
                // Add this use to DUChains of cmppop->GetDestOprdPtr()
                if ((Chains->GetDUChains()->Lookup (cmppop->GetDestOprdPtr()) == NULL) || 
                    (Chains->GetDUChains()->NotFound() == TRUE)) {
                  oprd_list = new oprdList;
                  oprd_list->SetOprdPtr (new_predicate);
                  Chains->GetDUChains()->Set (cmppop->GetDestOprdPtr(), oprd_list);    
                }
                else {
                  for (uses = Chains->GetDUChains()->Lookup (cmppop->GetDestOprdPtr());
                       uses->GetNextListPtr() != NULL;
                       uses = uses->GetNextListPtr()) 
                    ; // find end of DUChain
                  uses->SetNextListPtr(new oprdList);
                  uses->GetNextListPtr()->SetOprdPtr(new_predicate); 
                }
                //cerr << "RegId = " << new_predicate->GetOprdRegNum() << "\n";
              }
            }
          }
          
          // Duplicate op attributes.
          attrdictionary = ((legoProc*) proc_ptr)->GetAttrDictionary();
          if (attrdictionary == NULL)
            {
              LegoFatal ("DoTheMessyStuff",
                         "Attribute dictionary is missing.");
            } 
          for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
               attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;
          eaid = FindMaxEdgeAttrId ((legoProc*) proc_ptr);
          for (atlscan = duplicate_op->GetOpAttrListPtr(); atlscan != NULL;
               atlscan = atlscan->GetNextListPtr()) {
            if (atlscan->GetAttrPtr() == NULL)
              continue;
            atscan = new attrs (*(atlscan->GetAttrPtr()), duplicate_op, ++eaid);
            atlscan->SetAttrPtr (atscan);
            atscan->SetAttrId (eaid);
            atlscan->SetAttrId (eaid);
            attrtail->SetNextAttrPtr (atscan);
            attrtail = attrtail->GetNextAttrPtr();
          } // end for
          AddMidOp( duplicate_op, second_cmerge );
          FixLiveVarsDown(above_op, second_edge, (legoProc*) proc_ptr);
          ddderr("duplicate (opId = " << duplicate_op->GetOpId() << ") added for opId = " << above_op->GetOpId() << "\n");
          
          // Add to priority list
          
          // adding new elements to priority list screws up pointers for 
          // original Nodes. Need to remember which op is currently pointed 
          // to so that ListPtr can be reset to this Dag Node when done.

          orig_op_id = op->GetOpId(); 
          
          
          ListPtr = List->begin();
          while ((*ListPtr).GetOp()->GetOpId() != above_op->GetOpId()) ListPtr++; 
          Element = BigListElement(*ListPtr); 
          Element.SetOp(duplicate_op);
          
          ListCount++;
          // need to initialize mdes_info and ru_info pointers
          L_build_oper_mdes_info (duplicate_op);
          L_create_ru_info_oper (duplicate_op);
          
          // Now fix the DPG. Remove edges between successors that 
          // are not dominated by the block the op is now in, fix 
          // the others. 
          for (Front = Element.Successors->begin(),
               Back = Element.Successors->end(); 
               Front != Back; ) {
            // first find the DagNode for the Successor op
            ListPtr3 = List->begin();
            while ((*ListPtr3).GetOp()->GetOpId() != 
                   (*Front).GetOp()->GetOpId()) 
              ListPtr3++; 
            // find the edgetype
            edgetype = (*Front).GetDependencyType();
            // increment now (Front may be removed later) 
            Front++;
            if (DescendantofBlock((int) duplicate_op->GetParentBlockPtr(),
                                  (*ListPtr3).GetOp())) {
              // Change successor's predecessor op to duplicate_op
              // find the DagNode for above_op
              ListPtr2 = List->begin();
              while ((*ListPtr2).GetOp()->GetOpId() != 
                     above_op->GetOpId()) 
                ListPtr2++; 
              (*ListPtr3).RemovePredecessor(edgetype, 
                                           (*ListPtr2).GetOp());
              ddderr ("\nRemovePredecessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
              (*ListPtr2).RemoveSuccessor(edgetype, 
                                          (*ListPtr3).GetOp());
              ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
              rc = (*ListPtr3).AddPredecessor(edgetype, 
                                        Element.GetOp(), 
                                        &Element);
              ddderr ("\nAddPredecessor (opId = " << Element.GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
            }
            else {
              // Remove this Successor from the new Element
              Front = Element.RemoveSuccessor(edgetype, 
                                      (*ListPtr3).GetOp());
              // Reset Back
              Back = Element.Successors->end();
              ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << Element.GetOp()->GetOpId() << "\n");
            }
          }
          // This op is now a Successor to all of its Predecessors        
          for (Front = Element.Predecessors->begin(),
               Back = Element.Predecessors->end(); 
               Front != Back; Front++ ) {
            // Find the DagNode for this Predecessor
            ListPtr2 = List->begin();
            while ((*ListPtr2).GetOp()->GetOpId() != 
                   (*Front).GetOp()->GetOpId()) 
              ListPtr2++; 
            rc = (*ListPtr2).AddSuccessor((*Front).GetDependencyType(), 
                                     Element.GetOp(), 
                                     &Element);   
            ddderr ("\nAddSuccessor (opId = " << Element.GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << ", now " << rc << " Successors\n");
          }

          ListIter = List->insert( ListPtr, Element );
          
          // Now reset ListPtr to the original Op Node and ListPtr Node
          ListPtr = List->begin();
          while ((*ListPtr).GetOp()->GetOpId() != orig_op_id) ListPtr++; 
          Op = ListPtr;
          ListPtr++;
          
          // Now fix the RDefs when duplicate ops are added. 
          // Redirecting Chains for new duplicate_op should 
          // also fix the Chains for original above_op. 
          for (def_first = above_op->GetDestOprdPtr(), 
               def_second = duplicate_op->GetDestOprdPtr(); 
               def_first != NULL; 
               def_first = def_first->GetNextOprdPtr(),
               def_second = def_second->GetNextOprdPtr()) {
            if ((def_first->GetOprdType() == OT_REG) || 
                (def_first->GetOprdType() == OT_MACRO)) {       
              
              // Fix DUChains. Uses inside the Treegion and dominated by 
              // duplicate_op belong only to duplicate_op, those inside 
              // the Treegion and dominated by original_op belong only to 
              // original op. Others, (either outside of Treegion or source 
              // operands) belong to both.       
              uses_first = NULL;
              uses_second = NULL;
              uses = Chains->GetDUChains()->Lookup (def_first);
              
              while ((uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE)) {
                use = uses->GetOprdPtr();
                
                // Determine if this use preceeds the def op in its own block 
                UsePreceedsDefInBlock = FALSE; 
                for (predecessor_op = above_op; 
                     predecessor_op != NULL; 
                     predecessor_op = predecessor_op->GetPrevLink()) {
                  if (predecessor_op == use->GetParentOpPtr()) {
                    UsePreceedsDefInBlock = TRUE; 
                    break; 
                  }
                }
                
                if ((((legoRegion *) use->GetParentOpPtr()->GetParentBlockPtr())->GetParentPtr() == Region) && (DescendantofBlock( (int) above_op->GetParentBlockPtr(), use->GetParentOpPtr() ) && !UsePreceedsDefInBlock)) {
                  if ((DescendantofBlock( (int) duplicate_op->GetParentBlockPtr(), use->GetParentOpPtr() ))) {
                    if (uses_second == NULL) {
                      uses_second = new oprdList;
                      uses_second->SetOprdPtr(use);
                      prev_use_second = uses_second;
                    }
                    else {
                      new_use_second = new oprdList;
                      new_use_second->SetOprdPtr(use);
                      prev_use_second->SetNextListPtr(new_use_second);
                      prev_use_second = new_use_second;
                    }
                    // also need to patch the UDChain in this case
                    for (defs = Chains->GetUDChains()->Lookup (use);
                         defs->GetOprdPtr() != def_first;
                         defs = defs->GetNextListPtr())
                      ; // do nothing (find original def)
                    // now fix the original def to be new def of duplicate_op
                    defs->SetOprdPtr(def_second);
                  }
                  else {
                    if (uses_first == NULL) {
                      uses_first = new oprdList;
                      uses_first->SetOprdPtr(use);
                      prev_use_first = uses_first;
                    }
                    else {
                      new_use_first = new oprdList;
                      new_use_first->SetOprdPtr(use);
                      prev_use_first->SetNextListPtr(new_use_first);
                      prev_use_first = new_use_first;
                    }
                  }
                }
                else {
                  if (above_op == use->GetParentOpPtr()) {
                    // this is a special case of a def looping back to a use 
                    // in the same operation. Determine which src of 
                    // above_op/duplicate_op use belongs to
                    for (use_first = above_op->GetSrcOprdPtr(),
                         use_second = duplicate_op->GetSrcOprdPtr();
                         use_first != use; 
                         use_first = use_first->GetNextOprdPtr(),
                         use_second = use_second->GetNextOprdPtr())
                      ; // do nothing but increment used here
                    if (uses_second == NULL) {
                      uses_second = new oprdList;
                      uses_second->SetOprdPtr(use_first);
                      prev_use_second = uses_second;
                    }
                    else {
                      new_use_second = new oprdList;
                      new_use_second->SetOprdPtr(use_first);
                      prev_use_second->SetNextListPtr(new_use_second);
                      prev_use_second = new_use_second;
                    }
                    new_use_second = new oprdList;
                    new_use_second->SetOprdPtr(use_second);
                    prev_use_second->SetNextListPtr(new_use_second);
                    prev_use_second = new_use_second;
                    if (uses_first == NULL) {
                      uses_first = new oprdList;
                      uses_first->SetOprdPtr(use_first);
                      prev_use_first = uses_first;
                    }
                    else {
                      new_use_first = new oprdList;
                      new_use_first->SetOprdPtr(use_first);
                      prev_use_first->SetNextListPtr(new_use_first);
                      prev_use_first = new_use_first;
                    }
                    new_use_first = new oprdList;
                    new_use_first->SetOprdPtr(use_second);
                    prev_use_first->SetNextListPtr(new_use_first);
                    prev_use_first = new_use_first;
                    
                    // need to add a new UDChain for the new duplicate_op use
                    // and add to the UDChain of the original above_op
                    defs_second = new oprdList;
                    defs_second->SetOprdPtr(def_first);
                    defs_second->SetNextListPtr(new oprdList);
                    defs_second->GetNextListPtr()->SetOprdPtr(def_second);
                    Chains->GetUDChains()->Set (use_second, defs_second);
                    for (defs_first = Chains->GetUDChains()->Lookup (use_first);
                         defs_first->GetNextListPtr() != NULL;
                         defs_first = defs_first->GetNextListPtr()) 
                      ; // find end of UDChain
                    defs_first->SetNextListPtr(new oprdList);
                    defs_first->GetNextListPtr()->SetOprdPtr(def_second); 
                  }
                  else { // this use is outside of treegion and should belong to both
                    if (uses_second == NULL) {
                      uses_second = new oprdList;
                      uses_second->SetOprdPtr(use);
                      prev_use_second = uses_second;
                    }
                    else {
                      new_use_second = new oprdList;
                      new_use_second->SetOprdPtr(use);
                      prev_use_second->SetNextListPtr(new_use_second);
                      prev_use_second = new_use_second;
                    }
                    if (uses_first == NULL) {
                      uses_first = new oprdList;
                      uses_first->SetOprdPtr(use);
                      prev_use_first = uses_first;
                    }
                    else {
                      new_use_first = new oprdList;
                      new_use_first->SetOprdPtr(use);
                      prev_use_first->SetNextListPtr(new_use_first);
                      prev_use_first = new_use_first;
                    } 
                    // need to add to the UDChain for this use
                    for (defs = Chains->GetUDChains()->Lookup (use);
                         defs->GetNextListPtr() != NULL;
                         defs = defs->GetNextListPtr()) 
                      ; // find end of UDChain
                    defs->SetNextListPtr(new oprdList);
                    defs->GetNextListPtr()->SetOprdPtr(def_second); 
                  }
                }
                uses = uses->GetNextListPtr();
              }
              uses = Chains->GetDUChains()->Lookup (def_first);
              if (Chains->GetDUChains()->NotFound() == FALSE) {
                delete uses;    
                Chains->GetDUChains()->Set (def_first, uses_first);
                Chains->GetDUChains()->Set (def_second, uses_second);
              }
            }
          }
          for (use_first = above_op->GetSrcOprdPtr(), 
               use_second = duplicate_op->GetSrcOprdPtr(); 
               use_first != NULL; 
               use_first = use_first->GetNextOprdPtr(),
               use_second = use_second->GetNextOprdPtr()) {
            if ((use_first->GetOprdType() == OT_REG) || 
                (use_first->GetOprdType() == OT_MACRO)) {       
              
              // Fix Chains.      
              defs_second = NULL;
              defs = Chains->GetUDChains()->Lookup (use_first);
              if (Chains->GetUDChains()->NotFound() == FALSE) {
                while (defs != NULL) {
                  def = defs->GetOprdPtr();
                  // Build oprdList for UDChain
                  if (defs_second == NULL) {
                    defs_second = new oprdList;
                    defs_second->SetOprdPtr(def);
                    prev_def_second = defs_second;
                  }
                  else {
                    new_def_second = new oprdList;
                    new_def_second->SetOprdPtr(def);
                    prev_def_second->SetNextListPtr(new_def_second);
                    prev_def_second = new_def_second;
                  }
                  // need to add to the DUChain for this def
                  for (uses = Chains->GetDUChains()->Lookup (def);
                       uses->GetNextListPtr() != NULL;
                       uses = uses->GetNextListPtr()) 
                    ; // find end of DUChain
                  uses->SetNextListPtr(new oprdList);
                  uses->GetNextListPtr()->SetOprdPtr(use_second); 
                  
                  defs = defs->GetNextListPtr();
                }
                Chains->GetUDChains()->Set (use_second, defs_second);
              }
            }
          }
          
          // Now that I am demoting predicates, I only want to make these 
          // updates for CMPP ops (whose predicates are not demoted).  
          if ((duplicate_op->GetOpcode() >= CMPP) &&
              (duplicate_op->GetOpcode() <= FCMPP_D_TRUE_AC_AC)) {
            use_first = above_op->GetPredOprdPtr();
            use_second = duplicate_op->GetPredOprdPtr();
            if (use_first != NULL) {
              if ((use_first->GetOprdType() == OT_REG) || 
                  (use_first->GetOprdType() == OT_MACRO)) {     
                
                // Fix Chains.      
                defs_second = NULL;
                defs = Chains->GetUDChains()->Lookup (use_first);
                if (Chains->GetUDChains()->NotFound() == FALSE) {
                  while (defs != NULL) {
                    def = defs->GetOprdPtr();
                    // Build oprdList for UDChain
                    if (defs_second == NULL) {
                      defs_second = new oprdList;
                      defs_second->SetOprdPtr(def);
                      prev_def_second = defs_second;
                    }
                    else {
                      new_def_second = new oprdList;
                      new_def_second->SetOprdPtr(def);
                      prev_def_second->SetNextListPtr(new_def_second);
                      prev_def_second = new_def_second;
                    }
                    // need to add to the DUChain for this def
                    for (uses = Chains->GetDUChains()->Lookup (def);
                         uses->GetNextListPtr() != NULL;
                         uses = uses->GetNextListPtr()) 
                      ; // find end of DUChain
                    uses->SetNextListPtr(new oprdList);
                    uses->GetNextListPtr()->SetOprdPtr(use_second); 
                    
                    defs = defs->GetNextListPtr();
                  }
                  Chains->GetUDChains()->Set (use_second, defs_second);
                }
              }  
            }
          }
        }
        else {
          if (!(above_op->IsDummy())) {
            one_dead = TRUE; 
            unspeculated_ops++;
            downward_dynamic_op_reduction += ((legoRegion *) second_cmerge->GetParentBlockPtr())->GetWeight(); 
            if ((above_op->GetOpcode() == PBRR) || 
                (above_op->GetOpcode() == PBRA)) {
              unspeculated_pbr_ops++;
            }
          }
        }
        if ((anyliveout(above_op, first_edge) ||
             IsStoreOp(above_op) ||  
             (above_op->GetOpcode() == BRL)) && 
            above_op->GetOpcode() != DEFINE) {

          // May need to demote predicate if guarded by a predicate register
          if ((above_op->GetOpcode() < CMPP) ||
              (above_op->GetOpcode() > FCMPP_D_TRUE_AC_AC)) {
            PredOprd = above_op->GetPredOprdPtr();
            if (PredOprd != NULL) {
              if (PredOprd->GetOprdType() == OT_REG) {
                // Needs demotion
                //cerr << "\nabove_op's (OpId = " << above_op->GetOpId() << ") predicate (orig RegId = " << PredOprd->GetOprdRegNum() << ") demoted to ";

                // Clean-up RDefs before deleting oprd
                for (defs = Chains->GetUDChains()->Lookup (PredOprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  new_uses = NULL; 
                  for (uses = Chains->GetDUChains()->Lookup (def);
                       (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
                       uses = uses->GetNextListPtr()) {
                    use = uses->GetOprdPtr();
                    if (use != PredOprd) {
                      if (new_uses == NULL) {
                        new_uses = new oprdList;
                        new_uses->SetOprdPtr(use);
                        prev_use = new_uses;
                      }
                      else {
                        new_use = new oprdList;
                        new_use->SetOprdPtr(use);
                        prev_use->SetNextListPtr(new_use);
                        prev_use = new_use;
                      } 
                    }
                  }
                  if (Chains->GetDUChains()->NotFound() == FALSE) {
                    uses = Chains->GetDUChains()->Lookup (def);
                    delete uses; 
                    Chains->GetDUChains()->Set (def, new_uses);
                  }
                }
                Chains->GetUDChains()->Lookup (PredOprd);
                if (Chains->GetUDChains()->NotFound() == FALSE) {
                  Chains->GetUDChains()->Delete (PredOprd);
                }
                delete PredOprd; 
                
                // Find the CMPP op for branch 
                cmppoprd = op->GetSrcOprdPtr()->GetNextOprdPtr(); 
                cmppop = NULL;
                for (defs = Chains->GetUDChains()->Lookup (cmppoprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  cmppop = def->GetParentOpPtr(); // only one CMPP op should reach
                  break; 
                }
                
                dderr ("cmppop OpId is: " << cmppop->GetOpId() << "\n");
                
                if (cmppop == NULL) {
                  LegoFatal ("DoTheMessyStuff", "Can't find CMPP for branch");
                } 
                
                // Find the PBR op for branch 
                btroprd = op->GetSrcOprdPtr(); // should be 1st source
                pbrrop = NULL;
                for (defs = Chains->GetUDChains()->Lookup (btroprd);
                     (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                     defs = defs->GetNextListPtr()) {
                  def = defs->GetOprdPtr();
                  pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
                  break; 
                }
                
                dderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
                
                if (pbrrop == NULL) {
                  LegoFatal ("DoTheMessyStuff", "Can't find PBRR/PBRA in block");
                } // end if
                
                if (op->GetOpcode() == BRCT) {
                  if (pbrrop->GetSrcOprdPtr()->GetLiteralControlBlock() == 
                      ((legoRegion *) first_cmerge->GetParentBlockPtr())->GetRegionId()) {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr());
                  }
                  else {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr()
                                                 ->GetNextOprdPtr());
                  }
                }
                else {
                  if (pbrrop->GetSrcOprdPtr()->GetLiteralControlBlock() == 
                      ((legoRegion *) first_cmerge->GetParentBlockPtr())->GetRegionId()) {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr()
                                                 ->GetNextOprdPtr());
                  }
                  else {
                    new_predicate = new legoOprd(*cmppop->GetDestOprdPtr());
                  }
                }
                // Assign demoted predicate
                new_predicate->SetNextOprdPtr(NULL);
                above_op->SetPredOprdPtr(new_predicate);
                // Now adjust Chains 
                oprd_list = new oprdList;
                oprd_list->SetOprdPtr (cmppop->GetDestOprdPtr());
                Chains->GetUDChains()->Set (new_predicate, oprd_list); 
                // Add this use to DUChains of cmppop->GetDestOprdPtr()
                if ((Chains->GetDUChains()->Lookup (cmppop->GetDestOprdPtr()) == NULL) || 
                    (Chains->GetDUChains()->NotFound() == TRUE)) {
                  oprd_list = new oprdList;
                  oprd_list->SetOprdPtr (new_predicate);
                  Chains->GetDUChains()->Set (cmppop->GetDestOprdPtr(), oprd_list);    
                }
                else {
                  for (uses = Chains->GetDUChains()->Lookup (cmppop->GetDestOprdPtr());
                       uses->GetNextListPtr() != NULL;
                       uses = uses->GetNextListPtr()) 
                    ; // find end of DUChain
                  uses->SetNextListPtr(new oprdList);
                  uses->GetNextListPtr()->SetOprdPtr(new_predicate); 
                }
                //cerr << "RegId = " << new_predicate->GetOprdRegNum() << "\n";
              }
            }
          }
          
          RemoveMidOp( above_op, NO );
          AddMidOp( above_op, first_cmerge );
          FixLiveVarsDown(above_op, first_edge, (legoProc*) proc_ptr);
          ddderr("opId = " << above_op->GetOpId() << " moved below branch\n");
          // now fix the DPG. Remove edges between successors that 
          // are not dominated by the block above_op is now in. 
          // Find the DagNode for above_op
          ListPtr2 = List->begin();
          while ((*ListPtr2).GetOp()->GetOpId() != 
                 above_op->GetOpId()) 
            ListPtr2++; 
          for (Front = (*ListPtr2).Successors->begin(),
               Back = (*ListPtr2).Successors->end(); 
               Front != Back; ) {
            // first find the DagNode for the Successor op
            ListPtr3 = List->begin();
            while ((*ListPtr3).GetOp()->GetOpId() != 
                   (*Front).GetOp()->GetOpId()) 
              ListPtr3++; 
            // find the edgetype
            edgetype = (*Front).GetDependencyType();
            // increment now (Front may be removed later) 
            Front++;
            if (!DescendantofBlock((int) above_op->GetParentBlockPtr(),
                                   (*ListPtr3).GetOp())) {
              // Remove this Predecessor/Successor pair
              Front = (*ListPtr2).RemoveSuccessor(edgetype, 
                                           (*ListPtr3).GetOp());
              // Reset Back
              Back = (*ListPtr2).Successors->end();
              ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
              // the Successor's Predecessor is still above_op
              (*ListPtr3).RemovePredecessor(edgetype, 
                                           (*ListPtr2).GetOp());
              ddderr ("\nRemovePredecessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
            }
          }
        }
        else {
          
          if (!(above_op->IsDummy())) {
            if (one_dead == TRUE) dead_ops++;
            unspeculated_ops++;
            downward_dynamic_op_reduction += ((legoRegion *) first_cmerge->GetParentBlockPtr())->GetWeight(); 
            if ((above_op->GetOpcode() == PBRR) || 
                (above_op->GetOpcode() == PBRA)) {
              unspeculated_pbr_ops++;
            }
          }
          
          if (above_op->GetOpcode() != DEFINE) {
            // this op is dead along this path and therefore does not need to 
            // be scheduled. I will use dp_remove attr to delay removal so that 
            // RDefs remain valid
            AddDPRemoveAttribute ( above_op );
            // Set a non-negative_one s_time for above_op (op will be 
            // removed anyway)
            above_op->SetSchedTime( 0 );
            RemoveMidOp( above_op, NO );
            if (current_before_op->GetNextLink() == NULL) {
              AddMidOp( above_op, current_before_op->GetPrevLink() );
            }
            else  {
              AddMidOp( above_op, current_before_op );
            }
            if (next_above_op != current_before_op) {
              current_before_op = above_op; 
            }
            else {
              current_before_op = above_op; 
              next_above_op = current_before_op; 
            }
            // now fix the DPG. Remove edges between successors and predecessors
            ListPtr2 = List->begin();
            while ((*ListPtr2).GetOp()->GetOpId() != 
                   above_op->GetOpId()) 
              ListPtr2++; 
            for (Front = (*ListPtr2).Successors->begin(),
                 Back = (*ListPtr2).Successors->end(); 
                 Front != Back; ) {
              // Remove this Predecessor/Successor pair
              // first find the DagNode for the Successor op
              ListPtr3 = List->begin();
              while ((*ListPtr3).GetOp()->GetOpId() != 
                     (*Front).GetOp()->GetOpId()) 
                ListPtr3++; 
              // find the edgetype
              edgetype = (*Front).GetDependencyType();
              // increment now (Front may be removed later) 
              //Front++;
              Front = (*ListPtr2).RemoveSuccessor(edgetype, 
                                                  (*ListPtr3).GetOp());
              // Reset Back
              Back = (*ListPtr2).Successors->end();
              ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
              // the Successor's Predecessor is still above_op
              (*ListPtr3).RemovePredecessor(edgetype, 
                                            (*ListPtr2).GetOp());
              ddderr ("\nRemovePredecessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
            }
            for (Front = (*ListPtr2).Predecessors->begin(),
                 Back = (*ListPtr2).Predecessors->end(); 
                 Front != Back; ) {
              // Remove this Successor/Predecessor pair
              // first find the DagNode for the Predecessor op
              ListPtr3 = List->begin();
              while ((*ListPtr3).GetOp()->GetOpId() != 
                     (*Front).GetOp()->GetOpId()) 
                ListPtr3++; 
              // find the edgetype
              edgetype = (*Front).GetDependencyType();
              // increment now (Front may be removed later) 
              //Front++;
              Front = (*ListPtr2).RemovePredecessor(edgetype, 
                                                    (*ListPtr3).GetOp());
              // Reset Back
              Back = (*ListPtr2).Predecessors->end();
              ddderr ("\nRemovePredecessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
              // the Predecessor's Successor is still above_op
              (*ListPtr3).RemoveSuccessor(edgetype, 
                                          (*ListPtr2).GetOp());
              ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
            }
            ListCount--;
            //LegoNonFatal ("DoTheMessyStuff", "Dead Code Found ??\n");
          }
        }
      }
    }
  }
  return (NO_RENAMING_CONFLICT);
}

// This routine returns the second, complementary destination for a CMPP op.
// If the second predicate dest is OT_UNDEFINED, one will be created. 
// if the CMPP opcode does not produce a complementary second dest, the 
// opcode will be updated. The second destination oprd is returned.
legoOprd *list_scheduler::GetComplementaryDestOprd( legoOp *cmppop ) {

  legoOprd *p1, *p2; 

  if ((cmppop->GetOpcode() < CMPP) ||
      (cmppop->GetOpcode() > FCMPP_D_TRUE_AC_AC)) {
    LegoNonFatal ("GetComplementaryDestOprd", "Op passed not a CMPP op\n");
    return NULL;
  } // end if

  // make sure that the second D-action is a complement (odd-number opcode)
  div_t remainder = div(cmppop->GetOpcode(), 2);
  if (remainder.rem == 0) {
    cmppop->SetOpcode((cmppop->GetOpcode() + 1));
  }
  
  p1 = cmppop->GetDestOprdPtr();  // first destination!
  if (p1 == NULL || p1->GetNextOprdPtr() == NULL)
    {
      LegoNonFatal ("GetComplementaryDestOprd", "CMPP %d has bad destinations.",
                    cmppop->GetOpId());
      return NULL;
    } // end if
  p2 = p1->GetNextOprdPtr();  // p2 is there always!
  if (p1->GetNextOprdPtr()->GetOprdType() != OT_UNDEFINED)
    /* do nothing - we have two predicates! */;
  else {   // Make a second destination. 
    // Make the new operand and plop it into the CMPP.
    p2->SetOprdType (p1->GetOprdType());
    p2->SetOprdRegNum (++MaxRegNum);
    p2->SetOprdRegType (p1->GetOprdRegType());
    p2->SetOprdDataType (p1->GetOprdDataType());
    p2->SetOprdFileType (p1->GetOprdFileType());
    p2->SetOprdOmega (p1->GetOprdOmega());
    p2->SetOprdRegStyle (p1->GetOprdRegStyle());
    p2->SetIntValue (p1->GetOprdIntValue());
  } // end else

  return p2;
}


// This routine cleans up ops and adds a dp_remove attr so that they 
// can be remove after procedure is scheduled. Removing them earlier fucks 
// up priority lists and RDefs() 
void list_scheduler::PrepareToDie( legoOp *op ) {

  vector < BigListElement >::iterator ListPtr2, ListPtr3;
  vector < SmallListElement >::iterator Front, Back;
  enum edgeTypes edgetype;  
  
  if ((op != current_before_op) &&
      (op->GetNextLink() != current_before_op)) {
    
    if ((op->GetPrevLink() == NULL) && (op->GetNextLink() == NULL)) {
      RemoveVeryLastOp( op, NO ); 
    }
    else if ((op->GetPrevLink() != NULL) && (op->GetNextLink() != NULL)) {
      RemoveMidOp( op, NO ); 
    }
    else if ((op->GetPrevLink() != NULL) && (op->GetNextLink() == NULL)) {
      RemoveFinalOp( op, NO ); 
    }
    else if ((op->GetPrevLink() == NULL) && (op->GetNextLink() != NULL)) {
      RemoveFirstOp( op, NO ); 
    }
    else {
      LegoFatal ("PrepareToDie", "OK, now I'm stumped.");    
    }
    
    // Let's not actually delete it yet, it fucks up the priority list. Just 
    // schedule it in the previous multi-way branch block and dp_remove it 
    // later. Set the s_time so that it appears scheduled and adjust ListCount
    AddMidOp( op, current_before_op->GetPrevLink() );
  }
  
  AddDPRemoveAttribute ( op );
  if (op->GetSchedTime() == UNSCHEDULED ) {
    op->SetSchedTime( 0 );
  }
  // now fix the DPG. Remove edges between successors and predecessors
  ListPtr2 = List->begin();
  while ((*ListPtr2).GetOp()->GetOpId() != 
         op->GetOpId()) 
    ListPtr2++; 
  for (Front = (*ListPtr2).Successors->begin(),
       Back = (*ListPtr2).Successors->end(); 
       Front != Back; ) {
    // Remove this Predecessor/Successor pair
    // first find the DagNode for the Successor op
    ListPtr3 = List->begin();
    while ((*ListPtr3).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtr3++; 
    // find the edgetype
    edgetype = (*Front).GetDependencyType();
    // increment now (Front may be removed later) 
    //Front++;
    Front = (*ListPtr2).RemoveSuccessor(edgetype, 
                                        (*ListPtr3).GetOp());
    // Reset Back
    Back = (*ListPtr2).Successors->end();
    ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
    // the Successor's Predecessor is still above_op
    (*ListPtr3).RemovePredecessor(edgetype, 
                                  (*ListPtr2).GetOp());
    ddderr ("\nRemovePredecessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
  }
  for (Front = (*ListPtr2).Predecessors->begin(),
       Back = (*ListPtr2).Predecessors->end(); 
       Front != Back; ) {
    // Remove this Successor/Predecessor pair
    // first find the DagNode for the Predecessor op
    ListPtr3 = List->begin();
    while ((*ListPtr3).GetOp()->GetOpId() != 
           (*Front).GetOp()->GetOpId()) 
      ListPtr3++; 
    // find the edgetype
    edgetype = (*Front).GetDependencyType();
    // increment now (Front may be removed later) 
    //Front++;
    Front = (*ListPtr2).RemovePredecessor(edgetype, 
                                          (*ListPtr3).GetOp());
    // Reset Back
    Back = (*ListPtr2).Predecessors->end();
    ddderr ("\nRemovePredecessor (opId = " << (*ListPtr3).GetOp()->GetOpId() << ") of opId = " << (*ListPtr2).GetOp()->GetOpId() << "\n");
    // the Predecessor's Successor is still above_op
    (*ListPtr3).RemoveSuccessor(edgetype, 
                                (*ListPtr2).GetOp());
    ddderr ("\nRemoveSuccessor (opId = " << (*ListPtr2).GetOp()->GetOpId() << ") of opId = " << (*ListPtr3).GetOp()->GetOpId() << "\n");
  }
}


// As a result of control flow changes during the forming of Multi-Way 
// branches, some ops get re-targeted. Need to update the dag to reflect 
// new predecessor ops for control deps in these cases. 
void list_scheduler::UpdatePredecessorBranch( legoOp *op, legoOp *old_predecessor_op, legoOp *new_predecessor_op ) {

  vector < BigListElement >::iterator ListPtrOp, ListPtrOld, ListPtrNew, ListPtrCMERGE;
  int rc;
  legoOp *cmerge_op;

  // Let's also make sure that op's C_MERGE gets the right InList here as 
  // this also changes
  for (cmerge_op = op;
       cmerge_op->GetPrevLink() != NULL; 
       cmerge_op = cmerge_op->GetPrevLink())
    ; // Do nothing, just find C_MERGE
  cmerge_op->GetInListPtr()->SetOpPtr(new_predecessor_op);
  
  // Find the op DagNode
  ListPtrOp = List->begin();
  while ((*ListPtrOp).GetOp()->GetOpId() != 
         op->GetOpId()) 
    ListPtrOp++; 

  // Find the cmerge_op DagNode
  ListPtrCMERGE = List->begin();
  while ((*ListPtrCMERGE).GetOp()->GetOpId() != 
         cmerge_op->GetOpId()) 
    ListPtrCMERGE++; 

  // Find the old_predecessor_op DagNode
  ListPtrOld = List->begin();
  while ((*ListPtrOld).GetOp()->GetOpId() != 
         old_predecessor_op->GetOpId()) 
    ListPtrOld++; 

  // Find the new_predecessor_op DagNode
  ListPtrNew = List->begin();
  while ((*ListPtrNew).GetOp()->GetOpId() != 
         new_predecessor_op->GetOpId()) 
    ListPtrNew++; 

  // Remove the old Predecessor/Successor pair
  (*ListPtrOp).RemovePredecessor(ET_CNTL, 
                                 (*ListPtrOld).GetOp());
  ddderr ("\nRemovePredecessor (opId = " << (*ListPtrOld).GetOp()->GetOpId() << ") of opId = " << (*ListPtrOp).GetOp()->GetOpId() << "\n");
  (*ListPtrOld).RemoveSuccessor(ET_CNTL, 
                                (*ListPtrOp).GetOp());
  ddderr ("\nRemoveSuccessor (opId = " << (*ListPtrOp).GetOp()->GetOpId() << ") of opId = " << (*ListPtrOld).GetOp()->GetOpId() << "\n");
  
  // Add the new Predecessor/Successor pair 
  rc = (*ListPtrNew).AddSuccessor(ET_CNTL, 
                               (*ListPtrOp).GetOp(), 
                               &(*ListPtrOp));   
  ddderr ("\nAddSuccessor (opId = " << (*ListPtrOp).GetOp()->GetOpId() << ") of opId = " << (*ListPtrNew).GetOp()->GetOpId() << ", now " << rc << " Successors\n");
  rc = (*ListPtrOp).AddPredecessor(ET_CNTL, 
                                 (*ListPtrNew).GetOp(), 
                                 &(*ListPtrNew));
  ddderr ("\nAddPredecessor (opId = " << (*ListPtrNew).GetOp()->GetOpId() << ") of opId = " << (*ListPtrOp).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
  
  // Do the same for C_MERGE op
  // Remove the old Predecessor/Successor pair
  (*ListPtrCMERGE).RemovePredecessor(ET_CNTL, 
                                 (*ListPtrOld).GetOp());
  ddderr ("\nRemovePredecessor (opId = " << (*ListPtrOld).GetOp()->GetOpId() << ") of opId = " << (*ListPtrCMERGE).GetOp()->GetOpId() << "\n");
  (*ListPtrOld).RemoveSuccessor(ET_CNTL, 
                                (*ListPtrCMERGE).GetOp());
  ddderr ("\nRemoveSuccessor (opId = " << (*ListPtrCMERGE).GetOp()->GetOpId() << ") of opId = " << (*ListPtrOld).GetOp()->GetOpId() << "\n");
  
  // Add the new Predecessor/Successor pair 
  rc = (*ListPtrNew).AddSuccessor(ET_CNTL, 
                               (*ListPtrCMERGE).GetOp(), 
                               &(*ListPtrCMERGE));   
  ddderr ("\nAddSuccessor (opId = " << (*ListPtrCMERGE).GetOp()->GetOpId() << ") of opId = " << (*ListPtrNew).GetOp()->GetOpId() << ", now " << rc << " Successors\n");
  rc = (*ListPtrCMERGE).AddPredecessor(ET_CNTL, 
                                 (*ListPtrNew).GetOp(), 
                                 &(*ListPtrNew));
  ddderr ("\nAddPredecessor (opId = " << (*ListPtrNew).GetOp()->GetOpId() << ") of opId = " << (*ListPtrCMERGE).GetOp()->GetOpId() << ", now " << rc << " Predecessors\n");
  
}



// Allowing Multi-Way branches to be formed during list scheduling requires
// even MoreMessyStuff. 
// Here I DoMoreMessyStuff. 
int list_scheduler::DoMoreMessyStuff( legoOp *op, int Final_Pass )
{

  legoRegion *original_block, *current_block, *parent_block, *region;
  regionList *allchildren, *lrrscan;
  legoProc *parentproc; 
  legoOp *c_merge_op, *listop, *predecessor_branch_op=NULL; 
  legoOp *pbrrop, *pbrrop2, *cmppop, *cmppop2, *branch_that_needs_new_predecessor; 
  legoOp *last_op_in_multiop; 
  legoOprd *btroprd, *btroprd2, *def, *use, *oprd, *oprd2, *cmppoprd, *cmppoprd2;
  legoOprd *second_pred, *new_pred, *second_pred2, *new_pred2, *delete_oprd;
  opList *oplist, *oplisttoremove; 
  oprdList *defs, *uses, *oprd_list, *new_uses, *new_use, *prev_use; 
  attrList *atl;
  attrs *a;
  enum attrTypes atype;
  int i, TakenBlockId, TakenTakenBlockId; 
  int CurrentSTime, CurrentSlot, latency_count; 
  opEdges *edge;
  vector < BigListElement >::iterator TempListIter, ListPtr2, ListPtr3;
  vector < SmallListElement >::iterator Front, Back;
  regionList *temprl, *rlist; 
  enum edgeTypes edgetype;  
  
  bool pbrr_used; //HZ: used for the pbrr patch. This pbrr is used elsewhere?
  oprdList *use_temp; 
  legoOp *temp_br_op;

  //HZ: added to insert the mdes attribute so that we could use Emre's WeldSim
  legoOprd *attrmdes;

  ddderr ("\nDoMoreMessyStuff for opId = " << op->GetOpId() << "\n");
  
  if (!AllowMultiWayBR || !Final_Pass) return (RENAMING_CONFLICT);
  
  // First determine the block that the op is originally in. Will probably 
  // Need to remove this block later. 
  original_block = (legoRegion *) op->GetParentBlockPtr(); 
  c_merge_op = (legoOp *) original_block->GetItem(0);
  // Find parent proc.
  parentproc = (legoProc *) FindParentRegionType (RT_PROC, original_block);
  // Also want to know which branch this branch is control dependent on 
  // (should only be control dependent on one branch (Non-BRL)
  TempListIter = List->begin();
  while ((*TempListIter).GetOp()->GetOpId() != op->GetOpId()) 
    TempListIter++;
  for (Front = (*TempListIter).Predecessors->begin(),
       Back = (*TempListIter).Predecessors->end(); Front != Back; Front++ ) {
    if ((*Front).GetDependencyType() == ET_CNTL) {
      predecessor_branch_op = (*Front).GetOp();
      ddderr ("predecessor branch OpId = " << predecessor_branch_op->GetOpId() << "\n");
      break; 
    }
  }

  if (predecessor_branch_op == NULL) {
    LegoFatal ("DoMoreMessyStuff", "Could not find predecessor branch.");
  }
  
  // Find the last op in predecessor_branch_op's multiop. We will move other 
  // branches to the position just before this branch. 
  for (last_op_in_multiop = predecessor_branch_op; 
       (last_op_in_multiop->GetNextLink() != NULL); 
       last_op_in_multiop = last_op_in_multiop->GetNextLink()) {
    if ((last_op_in_multiop->GetNextLink()->GetSchedTime() != 
         predecessor_branch_op->GetSchedTime()) && 
        // PrepareToDie() may temporarily scatter ops with s_time = 0
        (FindLcAttribute( "dp_remove", last_op_in_multiop->GetNextLink() ) 
         == NULL)) {
      ddderr ("last_op_in_multiop: predecessor branch OpId = " << predecessor_branch_op->GetOpId() << "\n");
      ddderr ("last_op_in_multiop: last_op_in_multiop OpId = " << last_op_in_multiop->GetOpId() << "\n");      
      ddderr ("last_op_in_multiop: GetNextLink() OpId = " << last_op_in_multiop->GetNextLink()->GetOpId() << "\n");    
      break; 
    }
  }
  
  // Not yet ready to deal with jump tables. There may be some opportunities 
  // for improvement here, but skip these guys for now. It will be hard to 
  // 'split' jump tables because I need fully resolved predicates for each 
  // branch
  if (op->GetOpcode() == BRU) {
    for (atl = op->GetOpAttrListPtr(); atl != NULL;
         atl = atl->GetNextListPtr())
      if (atl->GetAttrType() == ATTR_TBLNAME) return (RENAMING_CONFLICT);
  }
  if (predecessor_branch_op->GetOpcode() == BRU) {
    for (atl = predecessor_branch_op->GetOpAttrListPtr(); atl != NULL;
         atl = atl->GetNextListPtr())
      if (atl->GetAttrType() == ATTR_TBLNAME) return (RENAMING_CONFLICT);
  }

  switch (op->GetOpcode()) {
  // BRUs and DUMMY_BRs will be removed (previous branches will be re-targeted 
  // in this case), otherwise move the branch op. 
  case BRU:
  case DUMMY_BR:
    {
      // Adjust one edge, remove the other
      edge = FindControlEdge (op, op->GetOutListPtr()->GetOpPtr());
      // Update new cmerge's In Op, weight should stay the same
      op->GetOutListPtr()->GetOpPtr()->GetInListPtr()->SetOpPtr(predecessor_branch_op);
      op->GetOutListPtr()->GetOpPtr()->GetInListPtr()->SetOpId(predecessor_branch_op->GetOpId());
      edge->SetFromOpPtr(predecessor_branch_op);
      edge->SetFromOpId(predecessor_branch_op->GetOpId());
      RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
      // Adjust Out opList
      oplist = predecessor_branch_op->GetOutListPtr();
      if (oplist->GetOpPtr() == c_merge_op) {
        oplist->SetOpPtr(op->GetOutListPtr()->GetOpPtr());
        oplist->SetOpId(op->GetOutListPtr()->GetOpPtr()->GetOpId());
        oplist->SetWeight(op->GetOutListPtr()->GetWeight());
      }
      else {
        oplist = oplist->GetNextListPtr(); 
        oplist->SetOpPtr(op->GetOutListPtr()->GetOpPtr());
        oplist->SetOpId(op->GetOutListPtr()->GetOpPtr()->GetOpId());
        oplist->SetWeight(op->GetOutListPtr()->GetWeight());
      }
      if (predecessor_branch_op->GetOpcode() != DUMMY_BR) {
        // retarget PBR if this is on the taken path or predecessor is a BRU
        btroprd = predecessor_branch_op->GetSrcOprdPtr(); // should be 1st source
        pbrrop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
        
        if (pbrrop == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        oprd = pbrrop->GetSrcOprdPtr();
        if (oprd->GetOprdType() != OT_LITERAL_CB) {
          LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                        pbrrop->GetOpId());
          return (RENAMING_CONFLICT);
        } // end if
        if (oprd->GetLiteralControlBlock() == ((legoRegion *) c_merge_op->GetParentBlockPtr())->GetRegionId()) {
          oprd->SetLiteralControlBlock(((legoRegion *) op->GetOutListPtr()->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
        }   
      }   
      
      // PrepareToDie for op and delete it's corresponding PBR (if BRU)
      if (op->GetOpcode() == BRU) {
        // Find PBR op
        btroprd = op->GetSrcOprdPtr(); // should be 1st source
        pbrrop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
        
        if (pbrrop == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        //HZ: 03/23/01 pbrr patch
        //    adding the processing of the pbrr op such that it would not
        //    be removed prematurely. Otherwise, yula would complain about the
        //    unfound branch target address, i.e., the BTR is not defined.
        //    The problem comes from the following senario:
        //      suppose one blcok is the same as the other due to the tail
        //      duplication and the pbrr in one block has been scheduled
        //      speculatively in a parent block. Then if the pbrr in the 
        //      other block is being scheduled, due to the dominator
        //      parallelism, this pbrr will be set to dp_remove and the use of
        //      this pbrr will be renamed and re-pointed to the former pbrr.
        //      Now if one of the two branches using the pbrr can be scheduled
        //      into the same parent block, the branches will be combined and
        //      its pbrr can be removed. But this removal will cause a problem
        //      for the other branch because its def of the src will be not
        //      available after the pbrr's removal.
        //      Now we add the following patch to this problem:
        //       Instead of call preparetodie(pbrr) directly, we will check its
        //       uses to see whether there are more valid uses (not set with
        //       dp_removal) of this pbrr. If there is, we will not set the
        //       dp_removal attribute to this pbrr.
        //     Apply this to all the pbrr removals in this function.
        
        pbrr_used = false;
        for(use_temp = Chains->GetDUChains()->Lookup(pbrrop->GetDestOprdPtr());
           (use_temp != NULL) && (Chains->GetDUChains()->NotFound() == false);
            use_temp = use_temp->GetNextListPtr())
        {
            temp_br_op = use_temp->GetOprdPtr()->GetParentOpPtr();
            if(temp_br_op != op && 
                    (FindLcAttribute("dp_remove", temp_br_op) == NULL))
            {
                pbrr_used = true;
                break;
            }
        }
                
        if(pbrr_used == false)
        {
            PrepareToDie(pbrrop);
            if (!(pbrrop->IsDummy())) 
            {
                multiway_dynamic_op_reduction += ((legoRegion *) pbrrop->GetParentBlockPtr())->GetWeight(); 
            }
        }
        
      }
      
      PrepareToDie(op);
      if (!(op->IsDummy())) {
        multiway_dynamic_op_reduction += ((legoRegion *) op->GetParentBlockPtr())->GetWeight(); 
      }
      
      break;
    }
  case RTS:
    {
      // Static estimator needs to know the original weight for the RTS op,
      // difficult to obtain after MultiWay branch formed, add attr.
      if (FindLcAttribute( "orig_wt", op ) == NULL) {
        oprd = new legoOprd;
        oprd->SetOprdType (OT_LITERAL_D);
        // FindOpWeight() should be fine before op is moved 
        oprd->SetLiteralDouble (FindOpWeight(op));
        AddLcAttribute ("orig_wt", oprd, op, parentproc);
      }
      if ((predecessor_branch_op->GetOpcode() == BRU) || 
          (predecessor_branch_op->GetOpcode() == DUMMY_BR)) {
        // replace unconditional branch with the RTS 
        if (op->GetNextLink() != NULL) {
          RemoveMidOp( op, NO ); 
        }
        else {
          RemoveFinalOp( op, NO ); 
        } 
        AddMidOp( op, last_op_in_multiop->GetPrevLink() );
        RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
        current_before_op = last_op_in_multiop; 
        
        op->SetPredOprdPtr(predecessor_branch_op->GetPredOprdPtr()); 
        predecessor_branch_op->SetPredOprdPtr(NULL);
          
        // Delete predecessor_branch_op and it's corresponding PBR (if BRU)
        if (predecessor_branch_op->GetOpcode() == BRU) {
          // Find PBR op
          btroprd = predecessor_branch_op->GetSrcOprdPtr(); // should be 1st source
          pbrrop = NULL;
          for (defs = Chains->GetUDChains()->Lookup (btroprd);
               (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
               defs = defs->GetNextListPtr()) {
            def = defs->GetOprdPtr();
            pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
            break; 
          }
          
          ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
          
          if (pbrrop == NULL) {
            LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
            return (RENAMING_CONFLICT);
          } // end if
          
          //HZ: pbrr patch
          pbrr_used = false;
          for(use_temp = Chains->GetDUChains()->Lookup(pbrrop->GetDestOprdPtr());
           (use_temp != NULL) && (Chains->GetDUChains()->NotFound() == false);
            use_temp = use_temp->GetNextListPtr())
          {
              temp_br_op = use_temp->GetOprdPtr()->GetParentOpPtr();
              if(temp_br_op != predecessor_branch_op && 
                    (FindLcAttribute("dp_remove", temp_br_op) == NULL))
              {
                   pbrr_used = true;
                break;
              }
          }
                
          if(pbrr_used == false)
          {
            PrepareToDie(pbrrop);
            if (!(pbrrop->IsDummy())) 
            {
                multiway_dynamic_op_reduction += ((legoRegion *) pbrrop->GetParentBlockPtr())->GetWeight(); 
            }
          }
          
        }

        // This was previously scheduled so we can free up these resources
        RU_unschedule_op(predecessor_branch_op->GetRUInfoPtr());
        L_free_oper_mdes_info (predecessor_branch_op);
        L_delete_ru_info_oper(predecessor_branch_op->GetRUInfoPtr());
        predecessor_branch_op->SetRUInfoPtr(NULL);
        PrepareToDie(predecessor_branch_op);
        if (!(predecessor_branch_op->IsDummy())) {
          multiway_dynamic_op_reduction += ((legoRegion *) predecessor_branch_op->GetParentBlockPtr())->GetWeight(); 
        }
        
      }
      else {
        // change predecessor branch to unconditional and move RTS up

        // Find the target of the predecessor_branch_op.
        btroprd = predecessor_branch_op->GetSrcOprdPtr(); // should be 1st source
        pbrrop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
        
        if (pbrrop == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        oprd = pbrrop->GetSrcOprdPtr();
        if (oprd->GetOprdType() != OT_LITERAL_CB) {
          LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                        pbrrop->GetOpId());
          return (RENAMING_CONFLICT);
        } // end if
        
        // Find the Taken Block Id
        TakenBlockId = oprd->GetLiteralControlBlock();
        
        if ((a = FindLcAttribute( "orig_fallthru_pred", predecessor_branch_op )) != NULL) {
          new_pred = new legoOprd(*((legoOprd *) (a->GetAttrOprdPtr()->GetLiteralULongLong())));
        }
        else {
          // Find the CMPP op for predecessor branch 
          cmppoprd = predecessor_branch_op->GetSrcOprdPtr()->GetNextOprdPtr(); 
          cmppop = NULL;
          for (defs = Chains->GetUDChains()->Lookup (cmppoprd);
               (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
               defs = defs->GetNextListPtr()) {
            def = defs->GetOprdPtr();
            cmppop = def->GetParentOpPtr(); // only one CMPP op should reach
            break; 
          }
          
          dderr ("cmppop OpId is: " << cmppop->GetOpId() << "\n");
          
          if (cmppop == NULL) {
            LegoFatal ("DoMoreMessyStuff", "Can't find CMPP for branch");
          } 
          
          second_pred = GetComplementaryDestOprd(cmppop);
          new_pred = new legoOprd(*second_pred);
        }

        // Now adjust Chains 
        oprd_list = new oprdList;
        oprd_list->SetOprdPtr (second_pred);
        Chains->GetUDChains()->Set (new_pred, oprd_list); 
        // Add this use to DUChains of second_pred
        if ((a = FindLcAttribute( "orig_fallthru_pred", predecessor_branch_op )) != NULL) {
          uses = Chains->GetDUChains()->Lookup ((legoOprd *) (a->GetAttrOprdPtr()->GetLiteralULongLong()));
        }
        else {
          uses = Chains->GetDUChains()->Lookup (second_pred);
        }
        if ((uses == NULL) || (Chains->GetDUChains()->NotFound() == TRUE)) {
          oprd_list = new oprdList;
          oprd_list->SetOprdPtr (new_pred);
          if ((a = FindLcAttribute( "orig_fallthru_pred", predecessor_branch_op )) != NULL) {
            Chains->GetDUChains()->Set (((legoOprd *) (a->GetAttrOprdPtr()->GetLiteralULongLong())), oprd_list);
          }
          else {
            Chains->GetDUChains()->Set (second_pred, oprd_list);
          }
        }
        else {
          for (;
               uses->GetNextListPtr() != NULL;
               uses = uses->GetNextListPtr()) 
            ; // find end of DUChain
          uses->SetNextListPtr(new oprdList);
          uses->GetNextListPtr()->SetOprdPtr(new_pred); 
        }

        if (((legoRegion *) c_merge_op->GetParentBlockPtr())
            ->GetRegionId() == TakenBlockId) {
          if (predecessor_branch_op->GetOpcode() == BRCF) {
            op->SetPredOprdPtr(new_pred);
            
            predecessor_branch_op->SetPredOprdPtr(predecessor_branch_op->GetSrcOprdPtr()
                                                  ->GetNextOprdPtr());
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
          }
          else if (predecessor_branch_op->GetOpcode() == BRCT) {
            op->SetPredOprdPtr(predecessor_branch_op->GetSrcOprdPtr()
                               ->GetNextOprdPtr());
            
            predecessor_branch_op->SetPredOprdPtr(new_pred);
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
            // Need to verify that predecessor_branch_op does not preceed 
            // it's new predicate register in this MultiOp (for yula)
            if ((predecessor_branch_op->GetNextLink() != NULL) &&
                !((predecessor_branch_op->GetOpcode() == BRCT) ||
                  (predecessor_branch_op->GetOpcode() == BRCF))) {
              RemoveMidOp(predecessor_branch_op, NO);
              // put just before op (depends on same CMPP)
              AddMidOp(predecessor_branch_op, op->GetPrevLink()); 
            }
          }
          else {
            LegoFatal ("DoMoreMessyStuff", "Branch not a BRCT or BRCF");
          }
          
          // Clean-up previous opcode
          CurrentSTime = predecessor_branch_op->GetSchedTime(); 
          CurrentSlot = predecessor_branch_op->GetRUInfoPtr()->slot_used; 
          RU_unschedule_op(predecessor_branch_op->GetRUInfoPtr());
          // Re-do mdes_info and ru_info pointer initialization
          L_free_oper_mdes_info (predecessor_branch_op);
          L_delete_ru_info_oper(predecessor_branch_op->GetRUInfoPtr());
          predecessor_branch_op->SetRUInfoPtr(NULL);

          // Now re-schedule the new opcode
          // initialize operand_ready_times to zero
          latency_count = mdes_latency_count();
          for (i = 0; i < latency_count; i++)
            operand_ready_times[i] = 0;
          predecessor_branch_op->SetOpcode(BRU);
          L_build_oper_mdes_info (predecessor_branch_op);
          L_create_ru_info_oper (predecessor_branch_op);
          if (RU_schedule_op_at (predecessor_branch_op->GetRUInfoPtr(), 
                             predecessor_branch_op->GetMdesInfoPtr(), 
                             operand_ready_times, CurrentSTime, 
                             CurrentSlot, 0) == -1) {
            LegoFatal ("DoMoreMessyStuff", "New Opcode re-schedule failed");
          }
          else
          {
              (*Op).GetOp()->SetMdesTime(CurrentSlot); // Emre  
              attrmdes=new legoOprd;
              attrmdes->SetOprdType(OT_LITERAL_I);
              attrmdes->SetLiteralInteger(CurrentSlot);
              attrmdes->SetOprdDataType(DT_I);
              attrmdes->SetIntValue(0);
              attrmdes->SetNextOprdPtr((legoOprd *)NULL);
              attrmdes->SetPrevOprdPtr((legoOprd *)NULL);
              attrmdes->SetParentOpPtr((legoOp *)NULL);                  
              attrmdes->SetParentAttrPtr((attrs *)NULL);
              attrmdes->SetValid(1);
              AddLcAttribute("Mdes",attrmdes,(*Op).GetOp(),(legoProc *) FindParentRegionType (RT_PROC,(*Op).GetOp()));
              (*Op).GetOp()->SetOpLatency(Machine->opLatency((*Op).GetOp())); // Emre                         
          }
        }
        else {
          if (predecessor_branch_op->GetOpcode() == BRCT) {
            op->SetPredOprdPtr(new_pred);
            
            predecessor_branch_op->SetPredOprdPtr(predecessor_branch_op->GetSrcOprdPtr()
                                                  ->GetNextOprdPtr());
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
          }
          else if (predecessor_branch_op->GetOpcode() == BRCF) {
            op->SetPredOprdPtr(predecessor_branch_op->GetSrcOprdPtr()
                               ->GetNextOprdPtr());
            
            predecessor_branch_op->SetPredOprdPtr(new_pred);
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
            // Need to verify that predecessor_branch_op does not preceed 
            // it's new predicate register in this MultiOp (for yula)
            if ((predecessor_branch_op->GetNextLink() != NULL) &&
                !((predecessor_branch_op->GetOpcode() == BRCT) ||
                  (predecessor_branch_op->GetOpcode() == BRCF))) {
              RemoveMidOp(predecessor_branch_op, NO);
              // put just before op (depends on same CMPP)
              AddMidOp(predecessor_branch_op, op->GetPrevLink()); 
            }
          }
          else {
            LegoFatal ("DoMoreMessyStuff", "Branch not a BRCT or BRCF");
          }
          // Clean-up previous opcode
          CurrentSTime = predecessor_branch_op->GetSchedTime(); 
          CurrentSlot = predecessor_branch_op->GetRUInfoPtr()->slot_used; 
          RU_unschedule_op(predecessor_branch_op->GetRUInfoPtr());
          // Re-do mdes_info and ru_info pointer initialization
          L_free_oper_mdes_info (predecessor_branch_op);
          L_delete_ru_info_oper(predecessor_branch_op->GetRUInfoPtr());
          predecessor_branch_op->SetRUInfoPtr(NULL);

          // Now re-schedule the new opcode
          // initialize operand_ready_times to zero
          latency_count = mdes_latency_count();
          for (i = 0; i < latency_count; i++)
            operand_ready_times[i] = 0;
          predecessor_branch_op->SetOpcode(BRU);
          L_build_oper_mdes_info (predecessor_branch_op);
          L_create_ru_info_oper (predecessor_branch_op);
          if (RU_schedule_op_at (predecessor_branch_op->GetRUInfoPtr(), 
                             predecessor_branch_op->GetMdesInfoPtr(), 
                             operand_ready_times, CurrentSTime, 
                             CurrentSlot, 0) == -1) {
            LegoFatal ("DoMoreMessyStuff", "New Opcode re-schedule failed");
          }
          else
          {
              (*Op).GetOp()->SetMdesTime(CurrentSlot); // Emre  
              attrmdes=new legoOprd;
              attrmdes->SetOprdType(OT_LITERAL_I);
              attrmdes->SetLiteralInteger(CurrentSlot);
              attrmdes->SetOprdDataType(DT_I);
              attrmdes->SetIntValue(0);
              attrmdes->SetNextOprdPtr((legoOprd *)NULL);
              attrmdes->SetPrevOprdPtr((legoOprd *)NULL);
              attrmdes->SetParentOpPtr((legoOp *)NULL);                  
              attrmdes->SetParentAttrPtr((attrs *)NULL);
              attrmdes->SetValid(1);
              AddLcAttribute("Mdes",attrmdes,(*Op).GetOp(),(legoProc *) FindParentRegionType (RT_PROC,(*Op).GetOp()));
              (*Op).GetOp()->SetOpLatency(Machine->opLatency((*Op).GetOp())); // Emre                         
          }
        }
        
        if (op->GetNextLink() != NULL) {
          RemoveMidOp( op, NO ); 
        }
        else {
          RemoveFinalOp( op, NO ); 
        } 
        AddMidOp( op, last_op_in_multiop->GetPrevLink() );
        current_before_op = last_op_in_multiop; 
        
        oplist = predecessor_branch_op->GetOutListPtr();
        if (oplist->GetOpPtr() !=  c_merge_op) {
          oplisttoremove = oplist->GetNextListPtr();
          oplist->SetNextListPtr(NULL);
          RemoveEdge(predecessor_branch_op, oplisttoremove->GetOpPtr(), parentproc, ET_CNTL); 
          delete oplisttoremove;
        }
        else {
          oplisttoremove = oplist;
          oplist = oplisttoremove->GetNextListPtr();
          oplisttoremove->SetNextListPtr(NULL);
          RemoveEdge(predecessor_branch_op, oplisttoremove->GetOpPtr(), parentproc, ET_CNTL); 
        delete oplisttoremove;
          predecessor_branch_op->SetOutListPtr(oplist);
        }
        
        // adjust this op's PBRR 
        oprd->SetLiteralControlBlock(((legoRegion *) oplist->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
        
      }
      break;
    }
  case BRCT:
  case BRCF:
    {
      if (predecessor_branch_op->GetOpcode() == BRU) {
        // Retarget predecessor BRU to this BRC*'s fall-thru.
        // Replace BRC* with a BRU. 
        if (op->GetNextLink() != NULL) {
          RemoveMidOp( op, NO ); 
        }
        else {
          RemoveFinalOp( op, NO ); 
        } 
        AddMidOp( op, last_op_in_multiop->GetPrevLink() );
        RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
        current_before_op = last_op_in_multiop; 
        
        // find predecessor_branch_op's PBR oprd (to redirect later)
        btroprd = predecessor_branch_op->GetSrcOprdPtr(); // should be 1st source
        pbrrop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
        
        if (pbrrop == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        oprd = pbrrop->GetSrcOprdPtr();
        if (oprd->GetOprdType() != OT_LITERAL_CB) {
          LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                        pbrrop->GetOpId());
          return (RENAMING_CONFLICT);
        } // end if
        
        // Make op a predicated BRU. 
        // retarget predecessor_branch_op to op's fall-thru (change predicate, 
        // edges, and out ops)
        
        ddderr ("*** Fix this BRU/BRC* predicate ***\n");
        
        // Find the CMPP op for this branch 
        cmppoprd = op->GetSrcOprdPtr()->GetNextOprdPtr(); 
        cmppop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (cmppoprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          cmppop = def->GetParentOpPtr(); // only one CMPP op should reach
          break; 
        }
        
        dderr ("cmppop OpId is: " << cmppop->GetOpId() << "\n");
        
        if (cmppop == NULL) {
          LegoFatal ("DoMoreMessyStuff", "Can't find CMPP for branch");
        } 
        
        second_pred = GetComplementaryDestOprd(cmppop);
        new_pred = new legoOprd(*second_pred);
        // Now adjust Chains 
        oprd_list = new oprdList;
        oprd_list->SetOprdPtr (second_pred);
        Chains->GetUDChains()->Set (new_pred, oprd_list); 
        // Add this use to DUChains of second_pred
        if ((Chains->GetDUChains()->Lookup (second_pred) == NULL) || 
            (Chains->GetDUChains()->NotFound() == TRUE)) {
          oprd_list = new oprdList;
          oprd_list->SetOprdPtr (new_pred);
          Chains->GetDUChains()->Set (second_pred, oprd_list);    
        }
        else {
          for (uses = Chains->GetDUChains()->Lookup (second_pred);
               uses->GetNextListPtr() != NULL;
               uses = uses->GetNextListPtr()) 
            ; // find end of DUChain
          uses->SetNextListPtr(new oprdList);
          uses->GetNextListPtr()->SetOprdPtr(new_pred); 
        }

        if (op->GetOpcode() == BRCT) {
          op->SetPredOprdPtr(op->GetSrcOprdPtr()->GetNextOprdPtr());
          predecessor_branch_op->SetPredOprdPtr(new_pred);
          // Need to verify that predecessor_branch_op does not preceed 
          // it's new predicate register in this MultiOp (for yula)
          if ((predecessor_branch_op->GetNextLink() != NULL) &&
              !((predecessor_branch_op->GetOpcode() == BRCT) ||
                (predecessor_branch_op->GetOpcode() == BRCF))) {
            RemoveMidOp(predecessor_branch_op, NO);
            // put just before op (depends on same CMPP)
            AddMidOp(predecessor_branch_op, op->GetPrevLink()); 
          }
        }
        else if (op->GetOpcode() == BRCF) {
          op->SetPredOprdPtr(new_pred);
          predecessor_branch_op->SetPredOprdPtr(op->GetSrcOprdPtr()->GetNextOprdPtr());
          // Need to verify that predecessor_branch_op does not preceed 
          // it's new predicate register in this MultiOp (for yula)
          if ((predecessor_branch_op->GetNextLink() != NULL) &&
              !((predecessor_branch_op->GetOpcode() == BRCT) ||
                (predecessor_branch_op->GetOpcode() == BRCF))) {
            RemoveMidOp(predecessor_branch_op, NO);
            // put just before op (depends on same CMPP)
            AddMidOp(predecessor_branch_op, op->GetPrevLink()); 
          }
        }
        else {
          LegoFatal ("DoMoreMessyStuff", "Branch not a BRCT or BRCF");
        }

        // Clean-up previous opcode
        // Re-do mdes_info and ru_info pointer initialization
        L_free_oper_mdes_info (op);
        L_delete_ru_info_oper(op->GetRUInfoPtr());
        op->SetRUInfoPtr(NULL);
        op->SetOpcode(BRU);
        op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
        L_build_oper_mdes_info (op);
        L_create_ru_info_oper (op);
        
        // Find the target of the original branch op.
        btroprd2 = op->GetSrcOprdPtr(); // should be 1st source
        pbrrop2 = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd2);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop2 = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop2 OpId is: " << pbrrop2->GetOpId() << "\n");
        ddderr ("op OpId is: " << op->GetOpId() << "\n");
        
        if (pbrrop2 == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        oprd2 = pbrrop2->GetSrcOprdPtr();
        if (oprd2->GetOprdType() != OT_LITERAL_CB) {
          LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                        pbrrop2->GetOpId());
          return (RENAMING_CONFLICT);
        } // end if
        
        // Find the Taken Block Id
        TakenTakenBlockId = oprd2->GetLiteralControlBlock();
        
        oplist = op->GetOutListPtr();
        if (((legoRegion *) oplist->GetOpPtr()->GetParentBlockPtr())
            ->GetRegionId() ==  TakenTakenBlockId) {
          oplisttoremove = oplist->GetNextListPtr();
          oplist->SetNextListPtr(NULL);
          // Adjust edge for new BRU
          edge = FindControlEdge (op, oplisttoremove->GetOpPtr());
          edge->SetFromOpPtr(predecessor_branch_op);
          edge->SetFromOpId(predecessor_branch_op->GetOpId());
          // Remove edge from predecessor_branch_op
          RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
          oprd->SetLiteralControlBlock(((legoRegion *) oplisttoremove->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
        }
        else {
          oplisttoremove = oplist;
          oplist = oplisttoremove->GetNextListPtr();
          oplisttoremove->SetNextListPtr(NULL);
          // Adjust edge for new BRU
          edge = FindControlEdge (op, oplisttoremove->GetOpPtr());
          edge->SetFromOpPtr(predecessor_branch_op);
          edge->SetFromOpId(predecessor_branch_op->GetOpId());
          // Remove edge from predecessor_branch_op
          RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
          oprd->SetLiteralControlBlock(((legoRegion *) oplisttoremove->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
          op->SetOutListPtr(oplist); 
        }
        predecessor_branch_op->GetOutListPtr()->SetOpPtr(oplisttoremove->GetOpPtr());
        predecessor_branch_op->GetOutListPtr()->SetOpId(oplisttoremove->GetOpPtr()->GetOpId());
        predecessor_branch_op->GetOutListPtr()->SetWeight(oplisttoremove->GetWeight());
        // Update new cmerge's In Op, weight should stay the same
        oplisttoremove->GetOpPtr()->GetInListPtr()->SetOpPtr(predecessor_branch_op);
        oplisttoremove->GetOpPtr()->GetInListPtr()->SetOpId(predecessor_branch_op->GetOpId());
        // Find branch_that_needs_new_predecessor 
        TempListIter = List->begin();
        while ((*TempListIter).GetOp()->GetOpId() != op->GetOpId()) 
          TempListIter++;
        for (Front = (*TempListIter).Successors->begin(),
             Back = (*TempListIter).Successors->end(); 
             Front != Back; 
             Front++ ) {
          if (((*Front).GetDependencyType() == ET_CNTL) && 
              (IsBranchOpButNotBRL((*Front).GetOp())) && 
              (((legoRegion *) (*Front).GetOp()->GetParentBlockPtr())
               ->GetRegionId() !=  TakenTakenBlockId)) {
            branch_that_needs_new_predecessor = (*Front).GetOp();
            ddderr ("branch_that_needs_new_predecessor OpId = " << branch_that_needs_new_predecessor->GetOpId() << "\n");
            break; 
          }
        }
        if (branch_that_needs_new_predecessor != NULL) {
          UpdatePredecessorBranch(branch_that_needs_new_predecessor, op, predecessor_branch_op);
        }
        delete oplisttoremove;
      }
      else { // predecessor branch is a BRCT or BRCF
        if (op->GetNextLink() != NULL) {
          RemoveMidOp( op, NO ); 
        }
        else {
          RemoveFinalOp( op, NO ); 
        } 
        AddMidOp( op, last_op_in_multiop->GetPrevLink() );
        current_before_op = last_op_in_multiop; 
        
        // Find the target of the predecessor_branch_op.
        btroprd = predecessor_branch_op->GetSrcOprdPtr(); // should be 1st source
        pbrrop = NULL;
        for (defs = Chains->GetUDChains()->Lookup (btroprd);
             (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
             defs = defs->GetNextListPtr()) {
          def = defs->GetOprdPtr();
          pbrrop = def->GetParentOpPtr(); // only one PBRR op should reach
          break; 
        }
        
        ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
        
        if (pbrrop == NULL) {
          LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
          return (RENAMING_CONFLICT);
        } // end if
        
        oprd = pbrrop->GetSrcOprdPtr();
        if (oprd->GetOprdType() != OT_LITERAL_CB) {
          LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                        pbrrop->GetOpId());
          return (RENAMING_CONFLICT);
        } // end if
        
        // Find the Taken Block Id
        TakenBlockId = oprd->GetLiteralControlBlock();
        
        if (((legoRegion *) c_merge_op->GetParentBlockPtr())
            ->GetRegionId() == TakenBlockId) {
          // Make op a predicated BRU. 
          // retarget predecessor_branch_op to op's fall-thru (change 
          // predicate,  edges, and out ops)
          
          // Find the CMPP op for this branch 
          cmppoprd = op->GetSrcOprdPtr()->GetNextOprdPtr(); 
          cmppop = NULL;
          for (defs = Chains->GetUDChains()->Lookup (cmppoprd);
               (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
               defs = defs->GetNextListPtr()) {
            def = defs->GetOprdPtr();
            cmppop = def->GetParentOpPtr(); // only one CMPP op should reach
            break; 
          }
          
          dderr ("cmppop OpId is: " << cmppop->GetOpId() << "\n");
          
          if (cmppop == NULL) {
            LegoFatal ("DoMoreMessyStuff", "Can't find CMPP for branch");
          } 
          
          second_pred = GetComplementaryDestOprd(cmppop);
          new_pred = new legoOprd(*second_pred);
          // Now adjust Chains 
          oprd_list = new oprdList;
          oprd_list->SetOprdPtr (second_pred);
          Chains->GetUDChains()->Set (new_pred, oprd_list); 
          // Add this use to DUChains of second_pred
          if ((Chains->GetDUChains()->Lookup (second_pred) == NULL) || 
              (Chains->GetDUChains()->NotFound() == TRUE)) {
            oprd_list = new oprdList;
            oprd_list->SetOprdPtr (new_pred);
            Chains->GetDUChains()->Set (second_pred, oprd_list);          
          }
          else {
            for (uses = Chains->GetDUChains()->Lookup (second_pred);
                 uses->GetNextListPtr() != NULL;
                 uses = uses->GetNextListPtr()) 
              ; // find end of DUChain
            uses->SetNextListPtr(new oprdList);
            uses->GetNextListPtr()->SetOprdPtr(new_pred); 
          }

          // Use existing orig_fallthru_pred or create a new one
          if (FindLcAttribute( "orig_fallthru_pred", predecessor_branch_op ) 
              == NULL) {
            // Find the CMPP op for predecessor_branch_op 
            // Will need to add attribute in case we need the original 
            // fall-thru predicate for later branches. 
            cmppoprd2 = predecessor_branch_op->GetSrcOprdPtr()->GetNextOprdPtr(); 
            cmppop2 = NULL;
            for (defs = Chains->GetUDChains()->Lookup (cmppoprd2);
                 (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                 defs = defs->GetNextListPtr()) {
              def = defs->GetOprdPtr();
              cmppop2 = def->GetParentOpPtr(); // only one CMPP op should reach
              break; 
            }
            
            dderr ("cmppop2 OpId is: " << cmppop2->GetOpId() << "\n");
            
            if (cmppop2 == NULL) {
              LegoFatal ("DoMoreMessyStuff", "Can't find CMPP for branch");
            } 
            
            if (predecessor_branch_op->GetOpcode() == BRCT) { 
              second_pred2 = GetComplementaryDestOprd(cmppop2);
              new_pred2 = new legoOprd;
              new_pred2->SetOprdType (OT_LITERAL_ULLNG);
              // want this attr to be the pointer predicate register
              new_pred2->SetLiteralULongLong ((int) second_pred2);
            }
            else if (predecessor_branch_op->GetOpcode() == BRCF) {
              new_pred2 = new legoOprd;
              new_pred2->SetOprdType (OT_LITERAL_ULLNG);
              // want this attr to be the pointer predicate register
              new_pred2->SetLiteralULongLong ((int) (cmppop2->GetDestOprdPtr()));
            }
            else {
              LegoFatal ("DoMoreMessyStuff", "Branch not a BRCT or BRCF");
            }
            
            AddLcAttribute ("orig_fallthru_pred", new_pred2, predecessor_branch_op, parentproc);
          }
            
          if (op->GetOpcode() == BRCT) {
            op->SetPredOprdPtr(op->GetSrcOprdPtr()->GetNextOprdPtr());
            // We no longer need this op's predicate second source
            delete_oprd = predecessor_branch_op->GetSrcOprdPtr()->GetNextOprdPtr();
            // Clean-up RDefs before deleting oprd
            for (defs = Chains->GetUDChains()->Lookup (delete_oprd);
                 (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                 defs = defs->GetNextListPtr()) {
              def = defs->GetOprdPtr();
              new_uses = NULL; 
              for (uses = Chains->GetDUChains()->Lookup (def);
                   (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
                   uses = uses->GetNextListPtr()) {
                use = uses->GetOprdPtr();
                if (use != delete_oprd) {
                  if (new_uses == NULL) {
                    new_uses = new oprdList;
                    new_uses->SetOprdPtr(use);
                    prev_use = new_uses;
                  }
                  else {
                    new_use = new oprdList;
                    new_use->SetOprdPtr(use);
                    prev_use->SetNextListPtr(new_use);
                    prev_use = new_use;
                  } 
                }
              }
              if (Chains->GetDUChains()->NotFound() == FALSE) {
                uses = Chains->GetDUChains()->Lookup (def);
                delete uses; 
                Chains->GetDUChains()->Set (def, new_uses);
              }
            }
            Chains->GetUDChains()->Lookup (delete_oprd);
            if (Chains->GetUDChains()->NotFound() == FALSE) {
              Chains->GetUDChains()->Delete (delete_oprd);
            }
            delete delete_oprd; 
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(new_pred);
          }
          else if (op->GetOpcode() == BRCF) {
            op->SetPredOprdPtr(new_pred);
            // We no longer need this op's predicate second source
            delete_oprd = predecessor_branch_op->GetSrcOprdPtr()->GetNextOprdPtr(); 
            // Clean-up RDefs before deleting oprd
            for (defs = Chains->GetUDChains()->Lookup (delete_oprd);
                 (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                 defs = defs->GetNextListPtr()) {
              def = defs->GetOprdPtr();
              new_uses = NULL; 
              for (uses = Chains->GetDUChains()->Lookup (def);
                   (uses != NULL) && (Chains->GetDUChains()->NotFound() == FALSE);
                   uses = uses->GetNextListPtr()) {
                use = uses->GetOprdPtr();
                if (use != delete_oprd) {
                  if (new_uses == NULL) {
                    new_uses = new oprdList;
                    new_uses->SetOprdPtr(use);
                    prev_use = new_uses;
                  }
                  else {
                    new_use = new oprdList;
                    new_use->SetOprdPtr(use);
                    prev_use->SetNextListPtr(new_use);
                    prev_use = new_use;
                  } 
                }
              }
              if (Chains->GetDUChains()->NotFound() == FALSE) {
                uses = Chains->GetDUChains()->Lookup (def);
                delete uses; 
                Chains->GetDUChains()->Set (def, new_uses);
              }
            }
            Chains->GetUDChains()->Lookup (delete_oprd);
            if (Chains->GetUDChains()->NotFound() == FALSE) {
              Chains->GetUDChains()->Delete (delete_oprd);
            }
            delete delete_oprd; 
            predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(op->GetSrcOprdPtr()->GetNextOprdPtr());
          }
          else {
            LegoFatal ("DoMoreMessyStuff", "Branch not a BRCT or BRCF");
          }

          // Clean-up previous opcode
          // Re-do mdes_info and ru_info pointer initialization
          L_free_oper_mdes_info (op);
          L_delete_ru_info_oper(op->GetRUInfoPtr());
          op->SetRUInfoPtr(NULL);
          op->SetOpcode(BRU);
          op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
          L_build_oper_mdes_info (op);
          L_create_ru_info_oper (op);
          
          // Find the target of the original branch op.
          btroprd2 = op->GetSrcOprdPtr(); // should be 1st source
          pbrrop2 = NULL;
          for (defs = Chains->GetUDChains()->Lookup (btroprd2);
               (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
               defs = defs->GetNextListPtr()) {
            def = defs->GetOprdPtr();
            pbrrop2 = def->GetParentOpPtr(); // only one PBRR op should reach
            break; 
          }
          
          ddderr ("pbrrop2 OpId is: " << pbrrop2->GetOpId() << "\n");
          ddderr ("op OpId is: " << op->GetOpId() << "\n");
          
          if (pbrrop2 == NULL) {
            LegoNonFatal ("DoMoreMessyStuff", "Can't find PBRR/PBRA in block");
            return (RENAMING_CONFLICT);
          } // end if
          
          oprd2 = pbrrop2->GetSrcOprdPtr();
          if (oprd2->GetOprdType() != OT_LITERAL_CB) {
            LegoNonFatal ("DoMoreMessyStuff", "PBRR %d not to control block.",
                          pbrrop2->GetOpId());
            return (RENAMING_CONFLICT);
          } // end if
          
          // Find the Taken Block Id
          TakenTakenBlockId = oprd2->GetLiteralControlBlock();
          
          oplist = op->GetOutListPtr();
          if (((legoRegion *) oplist->GetOpPtr()->GetParentBlockPtr())
              ->GetRegionId() ==  TakenTakenBlockId) {
            oplisttoremove = oplist->GetNextListPtr();
            oplist->SetNextListPtr(NULL);
            // Adjust edge for new BRU
            edge = FindControlEdge (op, oplisttoremove->GetOpPtr());
            edge->SetFromOpPtr(predecessor_branch_op);
            edge->SetFromOpId(predecessor_branch_op->GetOpId());
            // Remove edge from predecessor_branch_op
            RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
            oprd->SetLiteralControlBlock(((legoRegion *) oplisttoremove->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
          }
          else {
            oplisttoremove = oplist;
            oplist = oplisttoremove->GetNextListPtr();
            oplisttoremove->SetNextListPtr(NULL);
            // Adjust edge for new BRU
            edge = FindControlEdge (op, oplisttoremove->GetOpPtr());
            edge->SetFromOpPtr(predecessor_branch_op);
            edge->SetFromOpId(predecessor_branch_op->GetOpId());
            // Remove edge from predecessor_branch_op
            RemoveEdge(predecessor_branch_op, c_merge_op, parentproc, ET_CNTL); 
            oprd->SetLiteralControlBlock(((legoRegion *) oplisttoremove->GetOpPtr()->GetParentBlockPtr())->GetRegionId());
            op->SetOutListPtr(oplist); 
          }
          if (((legoRegion *) predecessor_branch_op->GetOutListPtr()->GetOpPtr()
               ->GetParentBlockPtr())->GetRegionId() ==  TakenBlockId) {
            predecessor_branch_op->GetOutListPtr()->SetOpPtr(oplisttoremove->GetOpPtr());
            predecessor_branch_op->GetOutListPtr()->SetOpId(oplisttoremove->GetOpPtr()->GetOpId());
            predecessor_branch_op->GetOutListPtr()->SetWeight(oplisttoremove->GetWeight());
          }
          else {
            predecessor_branch_op->GetOutListPtr()->GetNextListPtr()->SetOpPtr(oplisttoremove->GetOpPtr());
            predecessor_branch_op->GetOutListPtr()->GetNextListPtr()->SetOpId(oplisttoremove->GetOpPtr()->GetOpId());     
            predecessor_branch_op->GetOutListPtr()->GetNextListPtr()->SetWeight(oplisttoremove->GetWeight());
          }
          // Update new cmerge's In Op, weight should stay the same
          oplisttoremove->GetOpPtr()->GetInListPtr()->SetOpPtr(predecessor_branch_op);
          oplisttoremove->GetOpPtr()->GetInListPtr()->SetOpId(predecessor_branch_op->GetOpId());
          // Find branch_that_needs_new_predecessor 
          TempListIter = List->begin();
          while ((*TempListIter).GetOp()->GetOpId() != op->GetOpId()) 
            TempListIter++;
          for (Front = (*TempListIter).Successors->begin(),
               Back = (*TempListIter).Successors->end(); 
               Front != Back; 
               Front++ ) {
            if (((*Front).GetDependencyType() == ET_CNTL) && 
                (IsBranchOpButNotBRL((*Front).GetOp())) && 
                (((legoRegion *) (*Front).GetOp()->GetParentBlockPtr())
                 ->GetRegionId() !=  TakenTakenBlockId)) {
              branch_that_needs_new_predecessor = (*Front).GetOp();
              ddderr ("branch_that_needs_new_predecessor OpId = " << branch_that_needs_new_predecessor->GetOpId() << "\n");
              break; 
            }
          }
          if (branch_that_needs_new_predecessor != NULL) {
            UpdatePredecessorBranch(branch_that_needs_new_predecessor, op, predecessor_branch_op);
          }
          delete oplisttoremove;
          
        }
        else {
          // Make predecessor_branch_op a predicated BRU. op will now define 
          // the fall-thru path for the predecessor block. 

          // Clean-up previous opcode
          CurrentSTime = predecessor_branch_op->GetSchedTime(); 
          CurrentSlot = predecessor_branch_op->GetRUInfoPtr()->slot_used; 
          RU_unschedule_op(predecessor_branch_op->GetRUInfoPtr());
          // Re-do mdes_info and ru_info pointer initialization
          L_free_oper_mdes_info (predecessor_branch_op);
          L_delete_ru_info_oper(predecessor_branch_op->GetRUInfoPtr());
          predecessor_branch_op->SetRUInfoPtr(NULL);

          // Now re-schedule the new opcode
          // initialize operand_ready_times to zero
          latency_count = mdes_latency_count();
          for (i = 0; i < latency_count; i++)
            operand_ready_times[i] = 0;
          predecessor_branch_op->SetOpcode(BRU);
          predecessor_branch_op->SetPredOprdPtr(predecessor_branch_op->GetSrcOprdPtr()
                                                ->GetNextOprdPtr());
          predecessor_branch_op->GetSrcOprdPtr()->SetNextOprdPtr(NULL);
          L_build_oper_mdes_info (predecessor_branch_op);
          L_create_ru_info_oper (predecessor_branch_op);
          if (RU_schedule_op_at (predecessor_branch_op->GetRUInfoPtr(), 
                             predecessor_branch_op->GetMdesInfoPtr(), 
                             operand_ready_times, CurrentSTime, 
                             CurrentSlot, 0) == -1) {
            LegoFatal ("DoMoreMessyStuff", "New Opcode re-schedule failed");
          }
          else
          {
              (*Op).GetOp()->SetMdesTime(CurrentSlot); // Emre  
              attrmdes=new legoOprd;
              attrmdes->SetOprdType(OT_LITERAL_I);
              attrmdes->SetLiteralInteger(CurrentSlot);
              attrmdes->SetOprdDataType(DT_I);
              attrmdes->SetIntValue(0);
              attrmdes->SetNextOprdPtr((legoOprd *)NULL);
              attrmdes->SetPrevOprdPtr((legoOprd *)NULL);
              attrmdes->SetParentOpPtr((legoOp *)NULL);                  
              attrmdes->SetParentAttrPtr((attrs *)NULL);
              attrmdes->SetValid(1);
              AddLcAttribute("Mdes",attrmdes,(*Op).GetOp(),(legoProc *) FindParentRegionType (RT_PROC,(*Op).GetOp()));
              (*Op).GetOp()->SetOpLatency(Machine->opLatency((*Op).GetOp())); // Emre                         
          }
          
          oplist = predecessor_branch_op->GetOutListPtr();
          if (((legoRegion *) oplist->GetOpPtr()->GetParentBlockPtr())
              ->GetRegionId() ==  TakenBlockId) {
            oplisttoremove = oplist->GetNextListPtr();
            oplist->SetNextListPtr(NULL);
            RemoveEdge(predecessor_branch_op, oplisttoremove->GetOpPtr(), parentproc, ET_CNTL); 
            delete oplisttoremove;
          }
          else {
            oplisttoremove = oplist;
            oplist = oplisttoremove->GetNextListPtr();
            oplisttoremove->SetNextListPtr(NULL);
            RemoveEdge(predecessor_branch_op, oplisttoremove->GetOpPtr(), parentproc, ET_CNTL); 
            delete oplisttoremove;
            predecessor_branch_op->SetOutListPtr(oplist);
          }

          // Switch op and predecessor_branch_op locations. I want the BRC*
          // op to be the last op in the region so that the fall-thru is not 
          // taken prematurely by yula

          // Now move predecessor_branch_op from the last position (at least 
          // should be last prior to this move) to just before op
          RemoveFinalOp(predecessor_branch_op, NO);
          AddMidOp(predecessor_branch_op, op->GetPrevLink()); 
        }
      }
      break; 
    }
  default:
    {
      LegoFatal ("DoMoreMessyStuff", "Branch opcode not yet supported");
    }
  }

  // We will need to refresh Parents and Children, Exit Ops/Edges, etc..
  current_block = (legoRegion *) current_before_op->GetParentBlockPtr();
  allchildren = original_block->GetChildren();
  for (lrrscan = allchildren; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr()) {
    region = lrrscan->GetRegionPtr();
    if (region == NULL) continue;
    
    // Invalidate child's parents.
    region->SetParents (NULL);
  }
  current_block->SetChildren(NULL);
  

  // If only the c_merge is left in original block, destroy it and the block
  if (original_block->GetCount() == 1) {
    
    blocks_removed++;
    
    // First update the treeTraversalRList, this block will disappear
    rlist = ((legoTreegion*) Region)->GetTreeTraversalRList();
    if (rlist->GetRegionPtr() == original_block) {
      temprl = rlist; 
      rlist = rlist->GetNextListPtr(); 
      temprl->SetNextListPtr(NULL);
      delete temprl; 
      ((legoTreegion*) Region)->SetTreeTraversalRList(rlist);
    }
    else {
      for (;
           rlist->GetNextListPtr()->GetRegionPtr() != original_block; 
           rlist = rlist->GetNextListPtr()) {
        // just find the one to remove
      }
      temprl = rlist->GetNextListPtr(); 
      rlist->SetNextListPtr(rlist->GetNextListPtr()->GetNextListPtr());
      temprl->SetNextListPtr(NULL);
      delete temprl; 
    }

    PrepareToDie(c_merge_op);

    ListCount--;
    
    // now destroy original_block
    parent_block = original_block->GetParentPtr();
    if (parent_block == NULL)
    {
      LegoFatal ("DoMoreMessyStuff", "Can't find parent of original_block to be removed %d.", original_block->GetRegionId());
    } 
    // Get rid of attributes before destroying original_block
    RemoveLiveAttribute (original_block, parentproc); 
    atl = original_block->GetRegionAttrListPtr();
    while (atl != NULL)
      {
        atype = atl->GetAttrType();
        if (atype != ATTR_LC)
          {
            atl = atl->GetNextListPtr(); continue;  // skip to first lc
          } // end if
        
        // Remove the first attribute here.
        a = atl->GetAttrPtr();
        RemoveLcAttribute (a->GetAttrString(), original_block, parentproc);
        
        atl = original_block->GetRegionAttrListPtr();  // reset for next scan
      } // end while
    switch (current_block->GetRegionType())
      {
      case RT_BB:
        ((legoBB *) current_block)->RefreshOps(); 
        ((legoBB *) current_block)->RefreshEdges(); 
        break;
      case RT_SB:
        ((legoSB *) current_block)->RefreshOps(); 
        ((legoSB *) current_block)->RefreshEdges(); 
        break;
      case RT_HB:
        ((legoHB *) current_block)->RefreshOps(); 
        ((legoHB *) current_block)->RefreshEdges(); 
        break;
      default:
        LegoFatal ("DoMoreMessyStuff", "Can not determine RegionType");
      } // end switch
    
    // Since we can not delete this block yet, we need to Refresh It 
    // (it is deleted after procedure is schedule)
    switch (original_block->GetRegionType())
      {
      case RT_BB:
        ((legoBB *) original_block)->Re