op_scheduler.C

Go to the documentation of this file.

//
// File:
//
//      op_scheduler.C
//
// Purpose:
//
//      Implementation of operation scheduling.
//
// Author:
//
//      Mark C. Toburen
//
// History:
//
//      02/18/02 - Created.
//

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

#define temperr(_s_)
#define dperr(_s_)
#define ddderr(_s_)
#define _OP_SCHEDULER_DEBUG_ 1
#if defined (_OP_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

// Global scheduling variables
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;

// CompareBlockWeights
//   Comparison function to use with BubbleSort. Compare by block weight.
static int CompareBlockWeights(legoRegion *Reg1, legoRegion *Reg2) {
   return (Reg1->GetWeight() > Reg2->GetWeight());
}

// 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;

}

// 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 op_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 op_scheduler::DescendantofCurBlockPtr(ListIterator 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;
  }
}

// op_scheduler: BuildReadyTimes
//   Finds the ReadyTimes for each operand of an unscheduled
//   operation that will now be a Candidate for scheduling
void op_scheduler::BuildReadyTimes(ListIterator 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;
   int *true_operand_ready_times, *true_dsld_operand_ready_times;
   int *dsld_operand_ready_times;
  
   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()->IsCMERGEOp())
            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()->IsBRLOp())
                  ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency - 1;
               else
                  ready_time = (*Front).GetOp()->GetSchedTime() + op_latency + BypassLatency;
            } else { 
               if ((*Node).GetOp()->IsBRLOp())
                  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()->IsDEFINEOp())
                        ready_time = (*Front).GetOp()->GetSchedTime() + op_latency; 
                     else {
                        // BRLs define RET_ADDR macro on procedure entrance, not 
                        // on procedure exit 
                        if (((*Front).GetOp()->IsBRLOp()) && (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()->IsDEFINEOp()) {
                  if ((*Node).GetOp()->IsBRLOp())
                     ready_time = (*Front).GetOp()->GetSchedTime() + op_latency - 1; 
                  else
                     ready_time = (*Front).GetOp()->GetSchedTime() + op_latency;
               } else {
                  if ((*Node).GetOp()->IsBRLOp())
                     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;
      }
   }
}

// op_scheduler: PredecessorsScheduled
//   Returns YES if all predecessors of an op have been scheduled,
//   returns NO otherwise.
int op_scheduler::PredecessorsScheduled(ListIterator Node)
{
   vector <SmallListElement>::iterator Front, Back;
   int PredecessorId, PredecessorIssueTime;
   
   //derr(">> PredecessorsScheduled\n");
   if (Node->NumPredecessors() == 0) {
      //derr("   Entry node\n");
      return YES;
   }
   
   // If predecessors exist check to see if they have been scheduled
   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");
      
      // If the dominating op is unscheduled, dependencies should be enforced
      if ((PredecessorIssueTime = Front->GetOp()->GetSchedTime()) == UNSCHEDULED) {
         //derr(" ... NO\n");
         return NO;
      } //else derr(" ... YES\n");
   }
   
   //derr("   all predecessor ops are scheduled\n");
   return YES;
}

// op_scheduler: Rename
int op_scheduler::Rename(legoOp *op, int RegNum, 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);
}

// op_scheduler: SimpleRename
void op_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++;
   }
}

// op_scheduler: ForwardGlobalRename
void op_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); 
      }
   }  
}

// op_scheduler: ReverseGlobalRename
void op_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);
      }  
   }  
}

// op_scheduler: GlobalRename
void op_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++;
   }
}

// op_scheduler: AddCopyOps
int op_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);
      new_dest = new legoOprd(*def);
      filetype = def->GetOprdFileType();
      if (filetype != FT_PR) 
        new_pred = new legoOprd(*(op->GetPredOprdPtr()));
      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);

}

// op_scheduler: IsRemoteMergeProblem
int op_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; 
}

// op_scheduler: IsMergeProblem
int op_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; 
}

// op_scheduler: anyliveout
int op_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

// op_scheduler: RemoveOutputDepsAfterRename
void op_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");
      }
    }
  }
}

// op_scheduler: RemoveOutputDepsAfterRenameUp
void op_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");
      }
    }
  }
}

// op_scheduler: RemoveAntiDepsAfterUseRename
void op_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");
      }
    }
  }
}

// op_scheduler: RemoveAntiDepsAfterDefRename
void op_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");
      }
    }
  }
}

// op_scheduler: copy_operand
void op_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

// op_scheduler: add_to_existing_attr
void op_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

// op_scheduler: create_new_attr
void op_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

// op_scheduler: FixLiveVarsUp
int op_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

// op_scheduler: FixLiveVarsDown
int op_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

// op_scheduler: FixLiveVarsFromUses
int op_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

// op_scheduler: AnyOutputDepsBetween
int op_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 (DDG->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 op_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 (DDG->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 (DDG->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 DDG. 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 DDG. 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 DDG. 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* op_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 screws 
// up priority lists and RDefs() 
void op_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 DDG. 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 op_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 op_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)->RefreshOps(); 
        ((legoBB *) original_block)->RefreshEdges(); 
        break;
      case RT_SB:
        ((legoSB *) original_block)->RefreshOps(); 
        ((legoSB *) original_block)->RefreshEdges(); 
        break;
      case RT_HB:
        ((legoHB *) original_block)->RefreshOps(); 
        ((legoHB *) original_block)->RefreshEdges(); 
        break;
      default:
        LegoFatal ("DoMoreMessyStuff", "Can not determine RegionType");
      } // end switch
    
    region = (legoRegion *) current_block->GetParentPtr(); 
    if (region->GetRegionType() == RT_TREE) {
      ((legoTreegion *)region)->RefreshOps();
      ((legoTreegion *)region)->RefreshEdges();
    }
    if (region->GetRegionType() == RT_PROC) 
      ((legoProc *)region)->RefreshOps();
  }
  return (NO_RENAMING_CONFLICT);
}

// op_scheduler: PlacePBRsJustBeforeBranches 
void op_scheduler::PlacePBRsJustBeforeBranches() 
{
  
  legoRegion *BB_region; 
  legoOp *op, *pbrrop;
  oprdList *defs; 
  legoOprd *def, *oprd; 
  attrs *attrdictionary, *attrtail, *atscan, *attr;
  attrList *atlscan;
  legoProc *proc_ptr; 
  int eaid; 
  
  //HZ: update to handle the case when Region is BB.
  if(Region->GetRegionType() != RT_BB)
  {
     for (unsigned i = 0; i < Region->GetCount(); i++) 
     {
       BB_region = (legoRegion *) Region->GetItem(i); 
       // Some blocks may be empty do to Multi-Way branching and delayed removal
       if (BB_region->GetCount() > 0) 
       {
         for (op = (legoOp *) BB_region->GetItem(0); 
              op != NULL;
              op = op->GetNextLink()) 
         {
           if (IsBranchOp(op) && 
               (op->GetOpcode() != DUMMY_BR) && 
               (op->GetOpcode() != DUMMY_BRANCH) &&
               (FindLcAttribute( "dp_remove", op ) == NULL)) 
           {
          
             // This op has a PBR, find it
             ddderr ("branch (OpId = " << op->GetOpId() << ") has PBR, find it\n");
          
             pbrrop = NULL;
             for (defs = Chains->GetUDChains()->Lookup (op->GetSrcOprdPtr());
                  (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                  defs = defs->GetNextListPtr()) 
             {
               def = defs->GetOprdPtr();
               pbrrop = def->GetParentOpPtr(); 
               if ((pbrrop->GetOpcode() == PBRR) || 
                   (pbrrop->GetOpcode() == PBRA)) 
               {
                 break;           // only one PBRR op should reach
               }
             }
          
             ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
          
             if (pbrrop == NULL) 
             {
               LegoNonFatal ("PlacePBRsJustBeforeBranches", "Can't find PBRR/PBRA in block");
               return;
             } // end if
          
             if (FindLcAttribute( "need_duplicate", pbrrop ) != NULL) 
             {
               pbrrop = new legoOp(*pbrrop);
               pbrrop->SetOpId(++MaxOpId);
               // Duplicate op attributes.
               proc_ptr = (legoProc *) FindParentRegionType (RT_PROC, op);
               attrdictionary = proc_ptr->GetAttrDictionary();
               if (attrdictionary == NULL)
               {
                   LegoFatal ("PlacePBRsJustBeforeBranches",
                              "Attribute dictionary is missing.");
               }    
               for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
                    attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;
               eaid = FindMaxEdgeAttrId ((legoProc*) proc_ptr);
               for (atlscan = pbrrop->GetOpAttrListPtr(); atlscan != NULL;
                    atlscan = atlscan->GetNextListPtr()) 
               {
                 if (atlscan->GetAttrPtr() == NULL)
                   continue;
                 atscan = new attrs (*(atlscan->GetAttrPtr()), pbrrop, ++eaid);
                 atlscan->SetAttrPtr (atscan);
                 atscan->SetAttrId (eaid);
                 atlscan->SetAttrId (eaid);
                 attrtail->SetNextAttrPtr (atscan);
                 attrtail = attrtail->GetNextAttrPtr();
               } // end for(atlscan = ...
               AddMidOp(pbrrop, op->GetPrevLink());
               pbrrop->SetSchedTime(op->GetSchedTime());            
             } //end of if(FindLcAttribute( "need_duplicate", pbrrop) != NULL)
             else 
             {
               oprd = new legoOprd;
               attr = AddLcAttribute ("need_duplicate", oprd, pbrrop,
                                      (legoProc *) FindParentRegionType (RT_PROC, op));
            
               // Move this PBR to just before the Branch op
               if (pbrrop->GetNextLink() != op) 
               {
                 RemoveMidOp(pbrrop, NO); 
                 AddMidOp(pbrrop, op->GetPrevLink());
                 pbrrop->SetSchedTime(op->GetSchedTime()); 
               }
             } //end of else of if(FindLcAttribute( "need_duplicate", pbrrop) != NULL) 
           } //end of if(IsBranchOp(....
         } //end of for(op = (legoOp *) BB_region->GetItem(0); ...
       } //end of if (BB_region->GetCount() > 0) 
     } //end of for (unsigned i = 0; i < Region->GetCount(); i++)
  }//end of if(Region->GetRegionType()!=RT_BB)
  else //Region->GetRegionType() == RT_BB)
  {
       BB_region = Region; 
       // Some blocks may be empty do to Multi-Way branching and delayed removal
       if (BB_region->GetCount() > 0) 
       {
         for (op = (legoOp *) BB_region->GetItem(0); 
              op != NULL;
              op = op->GetNextLink()) 
         {
           if (IsBranchOp(op) && 
               (op->GetOpcode() != DUMMY_BR) && 
               (op->GetOpcode() != DUMMY_BRANCH) &&
               (FindLcAttribute( "dp_remove", op ) == NULL)) 
           {
          
             // This op has a PBR, find it
             ddderr ("branch (OpId = " << op->GetOpId() << ") has PBR, find it\n");
          
             pbrrop = NULL;
             for (defs = Chains->GetUDChains()->Lookup (op->GetSrcOprdPtr());
                  (defs != NULL) && (Chains->GetUDChains()->NotFound() == FALSE);
                  defs = defs->GetNextListPtr()) 
             {
               def = defs->GetOprdPtr();
               pbrrop = def->GetParentOpPtr(); 
               if ((pbrrop->GetOpcode() == PBRR) || 
                   (pbrrop->GetOpcode() == PBRA)) 
               {
                 break;           // only one PBRR op should reach
               }
             }
          
             ddderr ("pbrrop OpId is: " << pbrrop->GetOpId() << "\n");
          
             if (pbrrop == NULL) 
             {
               LegoNonFatal ("PlacePBRsJustBeforeBranches", "Can't find PBRR/PBRA in block");
               return;
             } // end if
          
             if (FindLcAttribute( "need_duplicate", pbrrop ) != NULL) 
             {
               pbrrop = new legoOp(*pbrrop);
               pbrrop->SetOpId(++MaxOpId);
               // Duplicate op attributes.
               proc_ptr = (legoProc *) FindParentRegionType (RT_PROC, op);
               attrdictionary = proc_ptr->GetAttrDictionary();
               if (attrdictionary == NULL)
               {
                   LegoFatal ("PlacePBRsJustBeforeBranches",
                              "Attribute dictionary is missing.");
               }    
               for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
                    attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;
               eaid = FindMaxEdgeAttrId ((legoProc*) proc_ptr);
               for (atlscan = pbrrop->GetOpAttrListPtr(); atlscan != NULL;
                    atlscan = atlscan->GetNextListPtr()) 
               {
                 if (atlscan->GetAttrPtr() == NULL)
                   continue;
                 atscan = new attrs (*(atlscan->GetAttrPtr()), pbrrop, ++eaid);
                 atlscan->SetAttrPtr (atscan);
                 atscan->SetAttrId (eaid);
                 atlscan->SetAttrId (eaid);
                 attrtail->SetNextAttrPtr (atscan);
                 attrtail = attrtail->GetNextAttrPtr();
               } // end for(atlscan = ...
               AddMidOp(pbrrop, op->GetPrevLink());
               pbrrop->SetSchedTime(op->GetSchedTime());            
             } //end of if(FindLcAttribute( "need_duplicate", pbrrop) != NULL)
             else 
             {
               oprd = new legoOprd;
               attr = AddLcAttribute ("need_duplicate", oprd, pbrrop,
                                      (legoProc *) FindParentRegionType (RT_PROC, op));
            
               // Move this PBR to just before the Branch op
               if (pbrrop->GetNextLink() != op) 
               {
                 RemoveMidOp(pbrrop, NO); 
                 AddMidOp(pbrrop, op->GetPrevLink());
                 pbrrop->SetSchedTime(op->GetSchedTime()); 
               }
             } //end of else of if(FindLcAttribute( "need_duplicate", pbrrop) != NULL) 
           } //end of if(IsBranchOp(....
         } //end of for(op = (legoOp *) BB_region->GetItem(0); ...
       } //end of if (BB_region->GetCount() > 0)       
  } //end of else of if(Region->GetRegionType() != RT_BB)
}

// op_scheduler: PlaceBranchesLast
void op_scheduler::PlaceBranchesLast() 
{
  
  legoRegion *BB_region; 
  legoOp *op, *previous_branch_op, *previous_op;

  //HZ: update to handle the case when Region is BB.  
  if(Region->GetRegionType() != RT_BB)
  {
     for (unsigned i = 0; i < Region->GetCount(); i++) 
     {
       BB_region = (legoRegion *) Region->GetItem(i); 
       // Some blocks may be empty do to Multi-Way branching and delayed removal
       if (BB_region->GetCount() > 0) 
       {
         unsigned j = (BB_region->GetCount() - 1);
         for (previous_branch_op = (legoOp*) BB_region->GetItem(j); 
              previous_branch_op->GetNextLink() != NULL;
              previous_branch_op = previous_branch_op->GetNextLink())
           ; // Do Nothing
         total_branch_multiops++;
         total_branch_ops++; 
         op = previous_branch_op->GetPrevLink();
         while (op != NULL) 
         {
           previous_op = op->GetPrevLink();
           if (IsBranchOpButNotBRL(op)) 
           {
             total_branch_ops++; 
             if (op->GetNextLink() != previous_branch_op) 
             {
               RemoveMidOp(op, NO);
               AddMidOp(op, previous_branch_op->GetPrevLink()); 
             }
             previous_branch_op = op;
           }
           op = previous_op;
         } // end of while(op != NULL)
       } //end of if(BB_region->GetCount() > 0) 
     } // end of for (unsigned i = 0; i < Region->GetCount(); i++)
   } //end of if(Region->GetRegionType() != RT_BB)
   else  //(Region->GetRegionType() == RT_BB)
   {
       BB_region = Region; 
       // Some blocks may be empty do to Multi-Way branching and delayed removal
       if (BB_region->GetCount() > 0) 
       {
         unsigned j = (BB_region->GetCount() - 1);
         for (previous_branch_op = (legoOp*) BB_region->GetItem(j); 
              previous_branch_op->GetNextLink() != NULL;
              previous_branch_op = previous_branch_op->GetNextLink())
           ; // Do Nothing
         total_branch_multiops++;
         total_branch_ops++; 
         op = previous_branch_op->GetPrevLink();
         while (op != NULL) 
         {
           previous_op = op->GetPrevLink();
           if (IsBranchOpButNotBRL(op)) 
           {
             total_branch_ops++; 
             if (op->GetNextLink() != previous_branch_op) 
             {
               RemoveMidOp(op, NO);
               AddMidOp(op, previous_branch_op->GetPrevLink()); 
             }
             previous_branch_op = op;
           }
           op = previous_op;
         } // end of while(op != NULL)
       } //end of if(BB_region->GetCount() > 0)        
   } //end of else if(Region->GetRegionType() != RT_BB)
}


// op_scheduler: ScheduleOp
//   Actually schedule the current op: Move it and set its schedule time
int op_scheduler::ScheduleOp(legoOp *op, int cycle)
{
   switch (Region->GetRegionType()) {
      case RT_TREE:
      case RT_BB:
         if (!(op->IsCMERGEOp())) {
            if (op->GetNextLink() != NULL) {
               RemoveMidOp(op, NO);
               AddMidOp(op, current_before_op);
               current_before_op = op;
            } else if (op->GetPrevLink() != current_before_op)
               return RENAMING_CONFLICT;
            else current_before_op = op;
         }
         op->SetSchedTime(cycle);
         break;
      default:
         LegoFatal("ScheduleOp", "RegionType not currently supported for operation scheduling");
         break;
   }

   return NO_RENAMING_CONFLICT;
}

// op_scheduler: ScheduleBlock
//   Schedule basic-block, Block, via operation scheduling starting at cycle StartCycle.
//   Return the writeback cycle of the last scheduled non-branch op.
int op_scheduler::ScheduleBlock(legoRegion *Block, int StartCycle)
{
   legoOp *temp_op;
   int ItemsScheduled = 0, CurrentCycle, WbCycle, LastWbCycle = 0;
   int mdes_slot, rn_conflict;

   if (Block->GetRegionType() != RT_BB)
      LegoFatal("ScheduleBlock", "Current region is not a basic-block");

   // MCT: Check to see if we're scheduling a treegion. If so, build the DDG for this
   // individual BB, sort it, and set the List pointers accordingly. We want to 
   // check dependencies using the entire treegion DDG, but schedule only looking 
   // at the BB's DDG.
   if (Region->GetRegionType() == RT_TREE) {
      BuildDagForRegion(Block, Machine, Knobs);
      SetValuesForRegion(Block, Knobs);
      vector <BigListElement> *BlockList = ((dag *)Block->GetDAG())->GetList();
      ListHead = BlockList->begin();
      ListTail = BlockList->end();
      ListCount = ((dag *)Block->GetDAG())->GetListSize();
   }
   
   // Schedule the DEFINEs first
   for (current_before_op = temp_op = (legoOp *)Block->GetItem(0); 
        temp_op != NULL; temp_op = temp_op->GetNextLink()) {
      if (temp_op->IsDEFINEOp()) {
         RemoveMidOp(temp_op, NO);
         AddMidOp(temp_op, current_before_op);
         temp_op->SetSchedTime(0);
         current_before_op = temp_op;
         ItemsScheduled++;
      }
   }

   derr("   Scheduling remaining " << ListCount - ItemsScheduled << 
        " ops out of original " << ListCount << "\n");
   while (ItemsScheduled < ListCount) {
      ListPtr = ListHead;
      while (ListPtr != ListTail) {
         // MCT: Make sure that the op to be scheduled has all its predecessors scheduled.
         // And skip it if we've already scheduled it.
         if (PredecessorsScheduled(ListPtr) &&
             ListPtr->GetOp()->GetSchedTime() == UNSCHEDULED) {

            // MCT: Enforce branches, with the exception of BRLs, to be scheduled
            // last and make sure that they are scheduled at the proper cycle (LastWbCycle).
            // If ListPtr is pointed to any op that's not a branch (except BRLs) set the
            // CurrentCycle to the ops earliest possible schedule time. If its a branch, set
            // the CurrentCycle to the writeback cycle of the last instruction scheduled.
            if (!IsBranchOpButNotBRL(ListPtr->GetOp()))
               CurrentCycle = StartCycle + ListPtr->GetDepth() - Machine->opLatency(ListPtr->GetOp());
            else if (ItemsScheduled == ListCount - 1)
               CurrentCycle = LastWbCycle;
            else {
               ListPtr++;
               continue;
            }

            // MCT: Now, begin trying to schedule at CurrentCycle. Build the operand ready
            // times and query MDES to see if there's an available slot. If so, schedule the
            // op - reserve its slot through the RU manager and call ScheduleOp to actually
            // move the op to its proper place. Otherwise, increment CurrentCycle and try again.
            // Once the op has been scheduled, adjust the last writeback cycle so we can 
            // enforce branch scheduling at the proper time and go to the next op in the list.
            while (1) {
               // MCT: Call BuildReadyTimes using the FindNode method because we want to make sure
               // that, if we're scheduling a treegion basic-block, we check dependencies from the
               // root block on down. If we're not treegion scheduling, this won't affect correctness.
               BuildReadyTimes(FindNode(ListPtr->GetOp()->GetOpId(), List), CurrentCycle);
               mdes_slot = RU_can_schedule_op(ListPtr->GetOp()->GetRUInfoPtr(), 
                                              ListPtr->GetOp()->GetMdesInfoPtr(),
                                              operand_ready_times, CurrentCycle, 0, 
                                              mdes_total_slots(), 0);
               if (mdes_slot != -1) {
                  //derr("   Trying to schedule Op " << ListPtr->GetOp()->GetOpId() << " ... ");
                  mdes_slot = RU_schedule_op_at(ListPtr->GetOp()->GetRUInfoPtr(), 
                                                ListPtr->GetOp()->GetMdesInfoPtr(),
                                                operand_ready_times, CurrentCycle, 
                                                mdes_slot, 0);
                  //derr(" scheduling on slot "<< mdes_slot << ", cycle " << CurrentCycle <<"\n");
                  rn_conflict = ScheduleOp(ListPtr->GetOp(), CurrentCycle);
                  if (rn_conflict == NO_RENAMING_CONFLICT) {
                     ItemsScheduled++;
                     Machine->adjustIssueStatus(ListPtr->GetOp(), CurrentCycle, mdes_slot);
                     if ((WbCycle = CurrentCycle + Machine->opLatency(ListPtr->GetOp())) > LastWbCycle)
                        LastWbCycle = WbCycle;
                  }
                  break;
               } // mdes_slot != -1
               CurrentCycle++;
            } // inner while
         } // if PredecessorsScheduled ...
         ListPtr++;
      } // outer while
   }
   //PrintSchedule();

   return LastWbCycle;
}

// op_scheduler: ScheduleTree
//   Treegion schedule via operation scheduling.
void op_scheduler::ScheduleTree()
{
   legoRegion *root_block_ptr;

   if (strcmp(TreeTraversal, "breadth") == 0)
      ScheduleTreeBreadthFirst();
   else if (strcmp(TreeTraversal, "depth") == 0) {
      root_block_ptr = ((legoTreegion *)Region)->GetRoot();
      derr("   Scheduling root block " << root_block_ptr->GetRegionId() << "\n");
      ScheduleTreeDepthFirst(root_block_ptr, 0);
   }
}

// op_scheduler:ScheduleTreeDepthFirst
//   Treegion schedule via operation scheduling by a recursive depth-first,
//   global-weight traversal of the treegion's basic-blocks.
void op_scheduler::ScheduleTreeDepthFirst(legoRegion *Block, int StartCycle)
{
   int i, LastWbCycle;
   regionList *children;
   legoRegion *child_ptr;
   vector <legoRegion *> rlist;

   derr("   Scheduling block " << Block->GetRegionId() << "\n");
   LastWbCycle = ScheduleBlock(Block, StartCycle);
   if (Block->GetChildren() != NULL) {
      children = new regionList(*(Block->GetChildren()));
      rlist = SortRegionListByWeight(children);

      for (i = 0; i < rlist.size(); i++) {
         if (((legoTreegion *)((rlist[i])->GetParentPtr()) == 
             (legoTreegion *)(Block->GetParentPtr())) && 
             (HasBlockBeenScheduled(rlist[i]) == UNSCHEDULED))
            ScheduleTreeDepthFirst(rlist[i], LastWbCycle);
      }
      delete children; 
   }
}

// op_scheduler: ScheduleTreeBreadthFirst
//   Treegion schedule via operation scheduling by a breadth-first, global-weigth traversal
//   of the treegion's basic-blocks.
void op_scheduler::ScheduleTreeBreadthFirst()
{
   legoRegion *root_block_ptr;
   int i, StartCycle, LastWbCycle, BlocksScheduled, BlockId;
   regionList *rlist;
   map <int, int>::iterator find;

   if (Region->GetRegionType() != RT_TREE)
      LegoFatal("ScheduleTree", "Current region is not a treegion");

   derr("   *** Scheduling treegion " << Region->GetRegionId() << " with " <<
        Region->GetCount() << " subblocks\n");

   // MCT: Start by scheduling the root basic-block.
   root_block_ptr = ((legoTreegion *)Region)->GetRoot();
   derr("   Scheduling root block id " << root_block_ptr->GetRegionId() << "\n");
   LastWbCycle = ScheduleBlock(root_block_ptr, 0);
   BlocksScheduled = 1;
   if (root_block_ptr->GetChildren() != NULL) {
      Children = new regionList(*(root_block_ptr->GetChildren()));
      for (rlist = root_block_ptr->GetChildren(); rlist != NULL; rlist = rlist->GetNextListPtr()) {
         BlockId = rlist->GetRegionPtr()->GetRegionId();
         ScheduleTimes.insert(pair<int, int>(BlockId, LastWbCycle));
      }
   } else Children = NULL;

   // MCT: After scheduling the root, schedule each of the saplings in a top-down,
   // global-weight fashion (i.e. schedule all of the root's children in order
   // of max profile weight, then schedule each of their child