modify.C

Go to the documentation of this file.

// modify.C

/*
 * LEGO Object Modification Functions
 * by Bill Havanki
 *
 * 1/29/98 WAH:  Created file.
 * 4/9/98 WAH:   Added TailDuplicate (moved from IR).
 * 4/14/98 WAH:  TailDuplicate now picks op ids from proc, not module.
 * 4/22/98 WAH:  Updated calls to attrs copy constructor in TailDuplicate.
 */

#include <stdio.h>
#include <stdlib.h>
#include "lego.H"
#include "modify.H"
#include "search.H"
#include "addremove.H"
#include "bitvector.H"

#define YES 1
#define NO 0

// #define MODIFY_DEBUG
#ifdef MODIFY_DEBUG
#define derr(_s_)  cerr << _s_ 
#define dprintf(s) fprintf s
#define OUTF stderr
#else
#define derr(_s_) 
#define dprintf(s)
#endif // MODIFY_DEBUG

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

/*
 * AddWeightAttribute
 *   op = op to annotate
 *   returns: new attr attached to op
 *
 * Attaches a new attr to the op saying what the weight of its block
 * is.
 */
static attrs *
AddWeightAttribute (legoOp *op)
{
  legoRegion *block;
  legoOprd *oprd;
  attrs *wtattr;

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

  oprd = new legoOprd;
  oprd->SetOprdType (OT_LITERAL_D);
  oprd->SetLiteralDouble (block->GetWeight());

  // Only update orig_wt for an op one time, as HBs may be in merged into 
  // other HBs. In this case we are only interested in the orig BB weight.
  if (FindLcAttribute( "orig_wt", op ) == NULL) {
    wtattr = AddLcAttribute ("orig_wt", oprd, op,
                             (legoProc *) FindParentRegionType (RT_PROC, op));
    return wtattr;
  }
  else {
    return NULL;
  }
}

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

/*
 * RedirectEdge
 *   edge = edge to redirect
 *   end = which end of edge to redirect
 *   op = op to which edge is to be redirected
 *   returns: 1 for success, 0 for failure
 *
 * Changes the source or destination of edge to op. Passing EDGE_FROM
 * changes the source, EDGE_TO the destination.
 *
 * Warning: Arbitrary use of this function will not only affect program
 * behavior but could invalidate some profile information.
 */
int
RedirectEdge (opEdges *edge, int end, legoOp *op)
{
  legoOp *oldop, *fromop, *toop;
  legoRegion *oldregion, *fromregion, *toregion;
  opList *opl;

  int from;
  double weight;

  if (edge == NULL || op == NULL ||
      (end != EDGE_FROM && end != EDGE_TO))
    {
      LegoNonFatal ("RedirectEdge", "Invalid argument: edge %p, end %d, "
                    "op %p.", edge, end, op);
      return 0;
    } // end if
  from = (end == EDGE_FROM);

  // Find the from and to components of the edge after the redirection
  // as well as the old (before).
  if (from)
    {
      toop = edge->GetToOpPtr();
      fromop = op;
      oldop = edge->GetFromOpPtr();
    } // end if
  else
    {
      fromop = edge->GetFromOpPtr();
      toop = op;
      oldop = edge->GetToOpPtr();
    } // end else
  fromregion = (legoRegion *) fromop->GetParentBlockPtr();
  toregion = (legoRegion *) toop->GetParentBlockPtr();
  oldregion = (legoRegion *) oldop->GetParentBlockPtr();

  // Remove the reference to from/toop from oldop, and add it to
  // to/fromop. First, though, save the weight!
  if (from)
    opl = oldop->GetOutListPtr();
  else
    opl = oldop->GetInListPtr();
  for ( ; opl != NULL; opl = opl->GetNextListPtr())
    if (opl->GetOpPtr() == (from ? toop : fromop)) break;
  if (opl != NULL) weight = opl->GetWeight();
  else weight = 0.0;

  // Now switch the references. Remove the old ref is fine. The new
  // ref should be added only if the op is a branch or C_MERGE!
  if (from)
    {
      opl = RemoveFromList (oldop->GetOutListPtr(), toop);
      oldop->SetOutListPtr (opl);
      if (IsBranchOp (fromop))
        {
          opl = AddToList (fromop->GetOutListPtr(), toop, 1, weight);
          fromop->SetOutListPtr (opl);
        } // end if
    } // end if
  else
    {
      opl = RemoveFromList (oldop->GetInListPtr(), fromop);
      oldop->SetInListPtr (opl);
      if (toop->GetOpcode() == C_MERGE)
        {
          opl = AddToList (toop->GetInListPtr(), fromop, 1, weight);
          toop->SetInListPtr (opl);
        } // end if
    } // end else

  // Now, change the reference to oldop in from/toop to refer
  // to to/fromop.
  if (from)
    opl = toop->GetInListPtr();
  else
    opl = fromop->GetOutListPtr();
  for ( ; opl != NULL; opl = opl->GetNextListPtr())
    if (opl->GetOpPtr() == oldop) break;
  if (opl != NULL)
    {
      opl->SetOpPtr ((from ? fromop : toop));
      opl->SetOpId (opl->GetOpPtr()->GetOpId());
    } // end if

  // Next, change the edge itself.
  if (from)
    {
      edge->SetFromOpPtr (fromop);
      edge->SetFromOpId (fromop->GetOpId());
    } // end if
  else
    {
      edge->SetToOpPtr (toop);
      edge->SetToOpId (toop->GetOpId());
    } // end else

  // Refresh everybody's edges.
  for ( ; oldregion->GetRegionType() != RT_PROC;
        oldregion = oldregion->GetParentPtr())
    oldregion->RefreshOpsAndEdges();
  for ( ; fromregion->GetRegionType() != RT_PROC;
        fromregion = fromregion->GetParentPtr())
    fromregion->RefreshOpsAndEdges();
  for ( ; toregion->GetRegionType() != RT_PROC;
        toregion = toregion->GetParentPtr())
    toregion->RefreshOpsAndEdges();

  return 1;
} // end RedirectEdge

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

/*
 * GetNewEdgeMergeValue
 *   edge = edge to analyze
 *   proc = procedure of edge
 *   returns: correct second value for edge freq attribute
 *
 * Determines the proper second value for the edge's freq attribute:
 *   0 if a dummy branch
 *   1 if the taken edge of a conditional or unconditional
 *   0 if the not-taken edge of a conditional
 *   cc value if a jumptable
 */
static int
GetNewEdgeMergeValue (opEdges *edge, legoProc *proc)
{
  int destblock;
  attrList *atl;
  legoOp *op;

  if (edge->GetFromOpPtr()->GetOpcode() == DUMMY_BR ||
      edge->GetFromOpPtr()->GetOpcode() == DUMMY_BRANCH)
    return 0;

  for (atl = edge->GetFromOpPtr()->GetOpAttrListPtr(); atl != NULL;
       atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_TBLNAME) break;
  if (atl != NULL)
    {
      jumpTable *jt;
      jumpList *jl;

      // Find cc value in jumptable (best guess).
      for (jt = proc->GetJumpDictionary(); jt != NULL;
           jt = jt->GetNextTablePtr())
        if (strcmp (jt->GetTableName(), atl->GetTableName()) == 0) break;
      if (jt == NULL) return 1;  // give up and return 1 for BRU

      for (jl = jt->GetJumpEntryPtr(); jl != NULL;
           jl = jl->GetNextListPtr())
        if (jl->GetOpId() == edge->GetToOpPtr()->GetOpId()) break;
      if (jl == NULL) return 1;

      if (jl->IsDefault()) return 1;
      else return jl->GetCcValue();
    } // end if

  // If branch takes to destination block, return 1, else 0.
  destblock = ((legoRegion *)(edge->GetToOpPtr()->GetParentBlockPtr()))
    ->GetRegionId();
  for (op = edge->GetFromOpPtr(); op != NULL; op = op->GetPrevLink())
    if (op->GetOpcode() == PBRR) break;
  if (op == NULL) return 1;  // give up and assume taken

  if (op->GetSrcOprdPtr()->GetLiteralControlBlock() == destblock)
    return 1;  // taken block
  else
    return 0;  // not-taken block
} // end GetNewEdgeMergeValue

// --------------------------------------------------------------------------

class pointer_map
{
public:
  void *original;  // pointer to original
  void *duplicate;  // pointer to duplicate
  class pointer_map *next;

  pointer_map() {original = duplicate = NULL; next = NULL;}
  ~pointer_map() {delete next;}

  void *lookup_original (void *dup)
  {
    if (duplicate == dup)
      return original;
    if (next != NULL)
      return next->lookup_original (dup);
    else
      return NULL;
  }

  void *lookup_duplicate (void *orig)
  {
    if (original == orig)
      return duplicate;
    if (next != NULL)
      return next->lookup_duplicate (orig);
    else
      return NULL;
  }

  class pointer_map *record (void *o, void *d)
  {
    original = o;
    duplicate = d;
    next = new pointer_map;
    return next;
  }
}; // end class pointer_map

/*
 * TailDuplicate
 *   sourceregion = region to duplicate
 *   dupedge = pointer to edge from last op in head region
 *   returns: duplicate of sourceregion
 *
 * Performs tail duplication of sourceregion.  The duplicate is attached to
 * head, while sourceregion remains attached to all other parents in control
 * flow.
 *
 * This is a horrendously long function, so be prepared to tax LEGO knowledge
 * to the limit!
 */
legoRegion *
TailDuplicate (legoRegion *sourceregion, opEdges *dupedge)
{
  regionList *allparents, *allchildren, *lrrscan, *oparents, *ochildren;
  int i, j, bingo, regionid, opid, eaid;
  double edgeweight, sourceweightratio;
  legoRegion *head, *duplicate, *region;
  legoProc *parentproc;
  legoOp *headop, *origop, *origop2, *dupop, *dupop2;
  legoOprd *oprd;
  opEdges *edgedictionary, *edgetail, *oescan;
  attrs *attrdictionary, *attrtail, *atscan;
  opList *oplscan, *oplscanprev;
  attrList *atlscan, *atl;
  edgeList *edlscan, *edlscanprev, *edlheadtosource;

  pointer_map *map, *tail;

//  cerr << "TailDuplicate sourceregion id " << sourceregion->GetRegionId() << " with Block Ptr " << sourceregion << "\n";

  headop = dupedge->GetFromOpPtr();
  head = (legoRegion *) (headop->GetParentBlockPtr());
  // First, some checking.
  if (!(IS_BLOCK(sourceregion->GetRegionType())))
    {
      LegoNonFatal ("TailDuplicate",
                    "Region %d not an op-holding block.", regionid);
      return NULL;
    } // end if

  allparents = sourceregion->GetParents();
  for (i = 0, bingo = 0, lrrscan = allparents; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      bingo++;
      if (lrrscan->GetRegionPtr() == head)
        i = 1;
    } // end for
  if (i == 0)
    {
      LegoNonFatal ("TailDuplicate", "Parent given is not actual parent.");
      return NULL;
    } // end if
  if (bingo < 2)
    {
      // No need to tail duplicate, so return sourceregion.
      return sourceregion;
    } // end if

  tail = map = new pointer_map;  // initialize pointer mapping table

  // Find parent proc.
  parentproc = (legoProc *) FindParentRegionType (RT_PROC, sourceregion);
  if (parentproc == NULL)
    LegoFatal ("TailDuplicate", "Can't find parent proc of region %d.",
               sourceregion->GetRegionId());

  // Get dictionaries.
  edgedictionary = parentproc->GetEdgeDictionary();
  if (edgedictionary == NULL)
    {
      LegoNonFatal ("TailDuplicate",
                    "Edge dictionary is missing.");
      return NULL;
    } // end if
  attrdictionary = parentproc->GetAttrDictionary();
  if (attrdictionary == NULL)
    {
      LegoNonFatal ("TailDuplicate",
                    "Attribute dictionary is missing.");
      return NULL;
    } // end if

  // Set up tail pointers and max edge/attr id.
  for (edgetail = edgedictionary; edgetail->GetNextOpEdgePtr() != NULL;
       edgetail = edgetail->GetNextOpEdgePtr()) /* do nothing */;

  for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
       attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;

  eaid = FindMaxEdgeAttrId (parentproc);

  // Before we begin, remember the parents and children of sourceregion.
  // Form them even if they're not there.
  if (sourceregion->GetParents() != NULL)
    oparents = new regionList (*(sourceregion->GetParents()));
  else
    oparents = NULL;
  if (sourceregion->GetChildren() != NULL)
    ochildren = new regionList (*(sourceregion->GetChildren()));
  else
    ochildren = NULL;

  // -----------------------------------------------------------------------
  // Step 1.  Duplicate the region (including ops).
  // -----------------------------------------------------------------------

  // 1a. Copy construct the region.
  switch (sourceregion->GetRegionType())
    {
    case RT_BB:
      duplicate = new legoBB (*(legoBB *) sourceregion); break;
    case RT_SB:
      duplicate = new legoSB (*(legoSB *) sourceregion); break;
    case RT_HB:
      duplicate = new legoHB (*(legoHB *) sourceregion); break;
    default:
      LegoFatal ("TailDuplicate", "Refuse to t-d region %d type %d.",
                 sourceregion->GetRegionId(),
                 (int) sourceregion->GetRegionType());
    } // end switch

  region = ((legoRegion *) parentproc->GetParentPtr())->FindMaxRegionId();
  regionid = region->GetRegionId();
  duplicate->SetRegionId (++regionid);

  // 1b. Duplicate region attributes.
  for (atlscan = duplicate->GetRegionAttrListPtr(); atlscan != NULL;
       atlscan = atlscan->GetNextListPtr())
    {
      if (atlscan->GetAttrPtr() == NULL)
        continue;
      atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
      atlscan->SetAttrPtr (atscan);
      atscan->SetAttrId (eaid);
      atlscan->SetAttrId (eaid);
      attrtail->SetNextAttrPtr (atscan);
      attrtail = attrtail->GetNextAttrPtr();
    } // end for

  opid = (FindMaxOpId ((legoProc *) parentproc))->GetOpId();

  // 1c. Copy construct each op from sourceregion to duplicate.
  for (origop = sourceregion->GetEntryOpsPtr()->GetOpPtr();
       origop != NULL;
       origop = origop->GetNextLink())
    {
      // 1c,i. Copy construct the op itself.
      dupop = new legoOp (*origop);
      tail = tail->record (origop, dupop);
      dupop->SetOpId (++opid);  // assign new id
      dupop->SetParentBlockPtr (duplicate);

      // Find origop in duplicate (there because of copy constructor).
      for (i = 0; i < duplicate->GetCount(); i++)
        {
          origop2 = (legoOp *) duplicate->GetItem (i);
          if (origop2 == origop) break;
        } // end for
      if (i == duplicate->GetCount())
        LegoFatal ("TailDuplicate", "Can't find original "
                   "op %d in duplicate.", origop->GetOpId());
      duplicate->Detach (i);  // remove original, slide down rest.  Then, ...
      duplicate->AddItem (dupop);  // add duplicate to end of region

      // 1c,ii. Duplicate op attributes.
      for (atlscan = dupop->GetOpAttrListPtr(); atlscan != NULL;
           atlscan = atlscan->GetNextListPtr())
        {
          if (atlscan->GetAttrPtr() == NULL)
            continue;
          atscan = new attrs (*(atlscan->GetAttrPtr()), dupop, ++eaid);
          atlscan->SetAttrPtr (atscan);
          atscan->SetAttrId (eaid);
          atlscan->SetAttrId (eaid);
          attrtail->SetNextAttrPtr (atscan);
          attrtail = attrtail->GetNextAttrPtr();
        } // end for

    } // end for

  // 1d. Update duplicate's entry/exit ops.
  duplicate->RefreshOps();

  // -----------------------------------------------------------------------
  // Step 2.  Update intra-block links, create new intra-block edges.
  // -----------------------------------------------------------------------

  // For each duplicated op...
  for (i = 0; i < duplicate->GetCount(); i++)
    {
      dupop = (legoOp *) duplicate->GetItem(i);
      // 2a. Update links and edges.
      if (i != duplicate->GetCount() - 1)
        {
          // 2a,i. Set previous and next links.
          dupop2 = (legoOp *) duplicate->GetItem(i + 1);
          dupop->SetNextLink (dupop2);
          dupop2->SetPrevLink (dupop);

          // 2a,ii. Hunt down original edge between them.
          // Find original ops by following duplicateOpsPtr list.
          for (oplscan = dupop->GetDuplicateOpsPtr(); oplscan != NULL;
               oplscan = oplscan->GetNextListPtr())
            if ((legoRegion *) oplscan->GetOpPtr()->GetParentBlockPtr()
                == sourceregion) break;
          if (oplscan == NULL)
            {
              LegoNonFatal ("TailDuplicate",
                            "Can't find original op for duplicate op %d.",
                            dupop->GetOpId());
              return NULL;
            } // end if
          origop = oplscan->GetOpPtr();
          for (oplscan = dupop2->GetDuplicateOpsPtr(); oplscan != NULL;
               oplscan = oplscan->GetNextListPtr())
            if ((legoRegion *) oplscan->GetOpPtr()->GetParentBlockPtr()
                == sourceregion) break;
          if (oplscan == NULL)
            {
              LegoNonFatal ("TailDuplicate",
                            "Can't find original op for duplicate op %d.",
                            dupop2->GetOpId());
              return NULL;
            } // end if
          origop2 = oplscan->GetOpPtr();

          oescan = FindControlEdge (origop, origop2);
          if (oescan == NULL)
            {
              LegoNonFatal ("TailDuplicate",
                            "Can't find edge between original ops %d and %d.",
                            origop->GetOpId(), origop2->GetOpId());
              return NULL;
            } // end if

          // 2a,iii. Copy construct a new edge between dupop and dupop2.
          edgetail->SetNextOpEdgePtr
            (new opEdges (*oescan, ++eaid, dupop->GetOpId(),
                          dupop, dupop2->GetOpId(), dupop2));
          edgetail = edgetail->GetNextOpEdgePtr();

          // 2a,iv. Duplicate edge attributes.
          for (atlscan = edgetail->GetEdgeAttrListPtr(); atlscan != NULL;
               atlscan = atlscan->GetNextListPtr())
            {
              if (atlscan->GetAttrPtr() == NULL)
                continue;
              atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
              atlscan->SetAttrPtr (atscan);
              atscan->SetAttrId (eaid);
              atlscan->SetAttrId (eaid);
              attrtail->SetNextAttrPtr (atscan);
              attrtail = attrtail->GetNextAttrPtr();
            } // end for

          // 2a,v. If dupop has an outlist, change the entry pointing
          //       to origop2 to point to dupop2.
          if (dupop->GetOutListPtr() != NULL)
            for (oplscan = dupop->GetOutListPtr(); oplscan != NULL;
                 oplscan = oplscan->GetNextListPtr())
              if (oplscan->GetOpId() == origop2->GetOpId())
                {
                  oplscan->SetOpPtr (dupop2);
                  oplscan->SetOpId (dupop2->GetOpId());
                } // end if (, for, if)

        } // end if

      // 2b. Update allListPtr as appropriate - ops are enqueued in reverse.
      if (i == 0)
        dupop->SetListOpPtr (parentproc->GetListOpPtr());
      if (i == duplicate->GetCount() - 1)
        parentproc->SetListOpPtr (dupop);
      else
        dupop2->SetListOpPtr (dupop);
        
    } // end for

  // -----------------------------------------------------------------------
  // Step 3.  Connect head and duplicate exclusively (handle jumptables later).
  // -----------------------------------------------------------------------
  
  // 3a. Count how many incoming edges there are to sourceregion (use i to
  //     count them).
  for (i = 0, edlscan = sourceregion->GetInEdgesPtr();
       edlscan != NULL;
       i++, edlscan = edlscan->GetNextListPtr()) /* do nothing */;

  // 3b. Redirect the head->sourceregion edge to head->duplicate.
  dupop = duplicate->GetEntryOpsPtr()->GetOpPtr();  // should be dup entry op
  RedirectEdge (dupedge, EDGE_TO, dupop);

  // 3bb. Fix jump tables if necessary
  for (atl = headop->GetOpAttrListPtr(); atl != NULL;
       atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_TBLNAME) break;
  if (atl != NULL)
    {
      jumpTable *jt;
      jumpList *jl;

      // For jump tables, there may be more than one edge from headop to 
      // sourceregion, we want to redirect all of these edges. 
      opEdges *extraedge = FindControlEdge (headop, sourceregion->GetEntryOpsPtr()->GetOpPtr(), 1);
      while (extraedge != NULL) {
        RedirectEdge (extraedge, EDGE_TO, dupop);
        extraedge = FindControlEdge (headop, sourceregion->GetEntryOpsPtr()->GetOpPtr(), 1);
      }
      
      // Now fix the jump table 
      for (jt = parentproc->GetJumpDictionary(); jt != NULL;
           jt = jt->GetNextTablePtr())
        if (strcmp (jt->GetTableName(), atl->GetTableName()) == 0) 
          break;
      if (jt != NULL) {
        for (jl = jt->GetJumpEntryPtr(); jl != NULL;
             jl = jl->GetNextListPtr()) {
          if (jl->GetOpId() == sourceregion->GetEntryOpsPtr()->GetOpPtr()->GetOpId()) {
//          cerr << "Fixing jump table from opId " << sourceregion->GetEntryOpsPtr()->GetOpPtr()->GetOpId() << " to opId " << duplicate->GetEntryOpsPtr()->GetOpPtr()->GetOpId() << "\n";
            jl->SetOpPtr(duplicate->GetEntryOpsPtr()->GetOpPtr());
            jl->SetOpId(duplicate->GetEntryOpsPtr()->GetOpPtr()->GetOpId());
          }
        }
      }
    } // end if   
  
  // 3c. If sourceregion had exactly two inedges, then the one remaining edge
  //     into sourceregion is no longer a merging edge.
  if (i == 2)
    {
      atlscan = FindFreqAttribute
        (sourceregion->GetInEdgesPtr()->GetEdgePtr());
      if (atlscan != NULL)
        atlscan->GetAttrValPtr()->GetNextIntListPtr()->SetAttrValue
          (GetNewEdgeMergeValue (sourceregion->GetInEdgesPtr()->GetEdgePtr(),
                                 parentproc));
    } // end if

  // 3d. Remove all but head's exit op from duplicate's entry op list.
  edgeweight = (double) FindEdgeFrequency (dupedge);
  if (edgeweight < 0) edgeweight = 0.0;

  delete dupop->GetInListPtr();
  oplscan = new opList;
  oplscan->SetOpPtr (headop);
  oplscan->SetOpId (headop->GetOpId());
  oplscan->SetValid (1);
  oplscan->SetWeight (edgeweight);
  dupop->SetInListPtr (oplscan);

  // 3e. Almost forgot: find any PBRR in head referring to sourceregion, and
  // change it to refer to duplicate.
  for (origop = (legoOp *) head->GetItem(0);
       origop->GetNextLink() != NULL;
       origop = origop->GetNextLink())
    {
      if (origop->GetOpcode() == PBRR)
        {
          oprd = origop->GetSrcOprdPtr();  // will be a literal cntl. block id
          if (oprd->GetOprdType() == OT_LITERAL_CB &&
              oprd->GetLiteralControlBlock() == sourceregion->GetRegionId())
            oprd->SetLiteralControlBlock (duplicate->GetRegionId());
        } // end if
    } // end for

  // 3f. Finally, copy the edge weight to duplicate, and subtract that
  // weight from sourceregion. Also, patch it to no longer be a merging edge.
  atlscan = FindFreqAttribute (dupedge);
  if (atlscan != NULL)
    {
      edgeweight = (double) (atlscan->GetAttrValPtr()->GetAttrValue());
      duplicate->SetWeight (edgeweight);
      sourceregion->SetWeight (sourceregion->GetWeight() - edgeweight);

      atlscan->GetAttrValPtr()->GetNextIntListPtr()->SetAttrValue
        (GetNewEdgeMergeValue (dupedge, (legoProc *) parentproc));
    } // end if

  // -----------------------------------------------------------------------
  // Step 4.  Connect duplicate to sourceregion' children.
  // -----------------------------------------------------------------------

  allchildren = sourceregion->GetChildren();
  sourceweightratio = sourceregion->GetWeight() + duplicate->GetWeight();
  if (sourceweightratio != 0.0)
    sourceweightratio = sourceregion->GetWeight() / sourceweightratio;
  // fraction of weight in original

  // For each child of source region ...
  if(allchildren != NULL)
  for (lrrscan = allchildren; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      if (region == NULL) continue;

      // 4a. Invalidate child's parents.
      region->SetParents (NULL);

      // 4b. Hunt down all edges between sourceregion and child and ...
      for (oescan = edgedictionary;
           oescan->GetNextOpEdgePtr() != NULL;
           oescan = oescan->GetNextOpEdgePtr())
        {
          origop = oescan->GetFromOpPtr();
          origop2 = oescan->GetToOpPtr();
          if ( ((legoRegion *)(origop->GetParentBlockPtr()) == sourceregion) &&
               ((legoRegion *)(origop2->GetParentBlockPtr()) ==
                region) )  // from sourceregion to child
            {
              dupop = (legoOp *) map->lookup_duplicate (origop);
              if (dupop == NULL)
                LegoFatal ("TailDuplicate", "Mapping error.");

              // 4b,i. Add a new control edge.
              edgetail->SetNextOpEdgePtr  // make from duplicate to child
                (new opEdges (*oescan, ++eaid, dupop->GetOpId(),
                                  dupop, origop2->GetOpId(), origop2));
              edgetail = edgetail->GetNextOpEdgePtr();
              //              edgetail = AddEdge (dupop, origop2, ET_CNTL);
              //              eaid++;

              // 4b,ii. Duplicate edge attributes.
              
              //HZ:
              //edgetail->SetEdgeAttrListPtr (new attrList
              //                            (*(oescan->GetEdgeAttrListPtr())));
              if(oescan->GetEdgeAttrListPtr() != NULL)
                edgetail->SetEdgeAttrListPtr (new attrList
                                            (*(oescan->GetEdgeAttrListPtr())));
              else
                edgetail->SetEdgeAttrListPtr(NULL);  
              for (atlscan = edgetail->GetEdgeAttrListPtr(); atlscan != NULL;
                   atlscan = atlscan->GetNextListPtr())
                {
                  if (atlscan->GetAttrPtr() == NULL)
                    continue;
                  atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
                  atlscan->SetAttrPtr (atscan);
                  atscan->SetAttrId (eaid);
                  atlscan->SetAttrId (eaid);
                  attrtail->SetNextAttrPtr (atscan);
                  attrtail = attrtail->GetNextAttrPtr();
                } // end for

              // 4b,iii. Scale edge weights appropriately as well as the
              //         weights of their ops.
              // oescan is the original. edgetail is the duplicate.
              edgeweight = -1.0;
              atlscan = FindFreqAttribute (oescan);
              if (atlscan != NULL)
                {
                  edgeweight = (double)
                    (atlscan->GetAttrValPtr()->GetAttrValue());  // original wt

                  // Scale oescan's weight down to its portion.
                  atlscan->GetAttrValPtr()->SetAttrValue
                    ((int) (edgeweight * sourceweightratio));
                  atlscan->GetAttrValPtr()->GetNextIntListPtr()
                    ->SetAttrValue (1);  // it's a merge now!

                  for (oplscan = origop->GetOutListPtr(); oplscan != NULL;
                       oplscan = oplscan->GetNextListPtr())
                    if (oplscan->GetOpId() == origop2->GetOpId())
                      {
                        oplscan->SetWeight (edgeweight * sourceweightratio);
                        break;
                      } // end if

                  // Scale edgetail's weight down to its portion.
                  atlscan = FindFreqAttribute (edgetail);
                  if (atlscan != NULL)
                    {
                      atlscan->GetAttrValPtr()->SetAttrValue
                        ((int) (edgeweight * (1.0 - sourceweightratio)));
                      atlscan->GetAttrValPtr()->GetNextIntListPtr()
                        ->SetAttrValue (1);  // it's a merge now!
                    } // end if

                  for (oplscan = dupop->GetOutListPtr(); oplscan != NULL;
                       oplscan = oplscan->GetNextListPtr())
                    if (oplscan->GetOpId() == origop2->GetOpId())
                      {
                        oplscan->SetWeight
                          (edgeweight * (1.0 - sourceweightratio));
                        break;
                      } // end if
                    
                } // end if

              // 4b,iv. While we're here, fix duplicate's out edge.
              //              for (edlscan = duplicate->GetOutEdgesPtr();
              //                   edlscan != NULL;
              //                   edlscan = edlscan->GetNextListPtr())
              //                {
              //                  if (edlscan->GetEdgePtr() == oescan)
              //                    {
              //                      edlscan->SetEdgePtr (edgetail);
              //                      edlscan->SetEdgeId (edgetail->GetEdgeId());
              //                      break;
              //                    } // end if
              //                } // end for

              // 4b,iv. Oh, and while we're at it, add edge to child.
              region->RefreshEdges();
              //              for (edlscan = region->GetInEdgesPtr();
              //                   edlscan != NULL && edlscan->GetNextListPtr() != NULL;
              //                   edlscan = edlscan->GetNextListPtr()) /* nothing */;
              //              if (edlscan != NULL)
              //                {
              //                  edlscan->SetNextListPtr (new edgeList);
              //                  edlscan = edlscan->GetNextListPtr();
              //                  edlscan->SetEdgePtr (edgetail);
              //                  edlscan->SetEdgeId (edgetail->GetEdgeId());
              //                  edlscan->SetValid (1);
              //                } // end if

              // 4b,v. All right, update the child's entry op too ... geez.
              //HZ
             if(origop2->GetInListPtr() != NULL)
              for (oplscan = origop2->GetInListPtr();
                   oplscan != NULL && oplscan->GetNextListPtr() != NULL;
                   oplscan = oplscan->GetNextListPtr())  // stop before end
                if (oplscan->GetOpId() == origop->GetOpId())
                  oplscan->SetWeight (edgeweight * sourceweightratio);
              if (oplscan->GetOpId() == origop->GetOpId())  // for last one
                oplscan->SetWeight (edgeweight * sourceweightratio);
              if (oplscan != NULL)
                {
                  oplscan->SetNextListPtr (new opList);
                  oplscan = oplscan->GetNextListPtr();
                  oplscan->SetOpPtr (dupop);
                  oplscan->SetOpId (dupop->GetOpId());
                  oplscan->SetValid (1);
                  oplscan->SetWeight (edgeweight * (1.0 - sourceweightratio));
                } // end if

            } // end if (found an edge to duplicate)

        } // end for (oescan)
    } // end for (lrrscan)

  // 4c (kinda). Fix duplicate's out edges.
  duplicate->RefreshEdges();

  // Finally finally finally, kill parents and children lists:
  // Original (sourceregion's) parents...
  for (lrrscan = oparents; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      //      delete region->children;
      //      region->children = NULL;
      region->SetChildren (NULL);
      region->RefreshEdges();
    } // end for
  // Original (sourceregion's) children...
  for (lrrscan = ochildren; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      //      delete region->parents;
      //      region->parents = NULL;
      region->SetParents (NULL);
      region->RefreshEdges();
    } // end for
  // And sourceregion' parents and children (duplicate's not copy-constr.'d)
  delete oparents;
  delete ochildren;
  sourceregion->SetParents (NULL);//HZ: it is ok, as the function call
                                   // GetParents will compute the pointer list
                                   // if it is NULL.
  sourceregion->SetChildren (NULL);
    
  return duplicate;
} // end TailDuplicate

/*
 * mdj - Remove Unconditional Branches (DUMMY_BR or BRU).
 * Treegion formations results in un-necessary unconditional branches. 
 * These braches originally were necessary because of merges, tail 
 * duplication eliminates several merges. As a result, unconditional 
 * branches can be removed, resulting in larger BBs within a Treegion. 
 *
 * If it was possible to remove the unconditional branch, 1 is returned,
 * otherwise 0 is returned.
 *
 */
int 
RemoveUncondBranch(legoRegion *sourceblock) {

  regionList *allchildren, *lrrscan;
  legoOp *predecessorop, *pbrrop, *predecessorbeforeop, *moveop, *oldbranch;
  legoOp  *listop, *verylastop;
  legoRegion *predecessor, *dupparent, *region;
  regionList *temp;
  legoProc *parentproc;
  int i; 
  
//  cerr << "RemoveUncondBranch sourceblock id " << sourceblock->GetRegionId() << " with Block Ptr " << sourceblock << "\n";

  // sourceblock can not be a merge in order to combine it with its 
  // predecessor block (must have only one predecessor block) 
  opList *entries = ((legoOp *)sourceblock->GetItem(0))->GetInListPtr();
  if (entries != NULL) {
    predecessorop = entries->GetOpPtr();
    predecessor = (legoRegion *) predecessorop->GetParentBlockPtr();
//    cerr << "RemoveUncondBranch predecessor id " << predecessor->GetRegionId() << " with Block Ptr " << predecessor << "\n";
    int entryopid = entries->GetOpPtr()->GetOpId(); 
    for (entries = entries->GetNextListPtr();
         entries != NULL;
         entries = entries->GetNextListPtr()) {
      if (entries->GetOpPtr()->GetOpId() != entryopid) {
        return 0;
      }
    }
  }
  else {
    return 0;
  }
  
  // BRUs can branch to more than one location. 
  // In order to merge, must be unconditional to only one location. 
  
  if (predecessorop->GetOpcode() == BRU) {
    opList *exits = predecessorop->GetOutListPtr();
    if (exits != NULL) {
      int exitopid = exits->GetOpPtr()->GetOpId(); 
      for (exits = exits->GetNextListPtr();
           exits != NULL;
           exits = exits->GetNextListPtr()) {
        if (exits->GetOpPtr()->GetOpId() != exitopid) {
          return 0;
        }
      }
    }
    else {
      return 0;
    }
  }
  
  // Can only be merged with the predecessor block if the branch from 
  // predecessor block to source block is unconditional.
  if ((predecessorop->GetOpcode() == DUMMY_BR) ||
      (predecessorop->GetOpcode() == DUMMY_BRANCH) ||
      (predecessorop->GetOpcode() == BRU)) {
//    cerr << "source BB " << sourceblock->GetRegionId() << " will be merged with predecessor BB " << predecessor->GetRegionId() << "\n";    

    allchildren = sourceblock->GetChildren();
    for (lrrscan = allchildren; lrrscan != NULL;
         lrrscan = lrrscan->GetNextListPtr())
      {
        region = lrrscan->GetRegionPtr();
        if (region == NULL) continue;
        
        // 4a. Invalidate child's parents.
        region->SetParents (NULL);
      }
    predecessor->SetChildren(NULL);
    
    // Find parent proc.
    parentproc = (legoProc *) FindParentRegionType (RT_PROC, sourceblock);
    if (parentproc == NULL)
      LegoFatal ("RemoveUncondBranch", "Can't find parent proc of region %d.",
                 sourceblock->GetRegionId());
    if (predecessorop->GetOpcode() == BRU) {
      // predecessor's PBRR will be replaced by sourceblocks PBRR. Get rid of 
      // it now. We will deal with the actual branch a little later
      for (pbrrop = predecessorop->GetPrevLink(); pbrrop != NULL; 
           pbrrop = pbrrop->GetPrevLink())
        if (pbrrop->GetOpcode() == PBRR) break;
      if (pbrrop != NULL) 
        RemoveMidOp(pbrrop, YES); // destroy this one
    }
    // now move all "internal" ops (other than C_MERGE and BRANCH) 
    // from sourceblock to predecessor. 
    // I am assuming that the C_MERGE is item = 0 
    predecessorbeforeop = predecessorop->GetPrevLink();
    int count = sourceblock->GetCount() - 1;
    for (i = 1; i < count; i++) {
      // move count items, the moved items are always in position following
      // the C_MERGE op, as the previously moved item is removed using 
      // RemoveMidOp()
      moveop = ((legoOp *) sourceblock->GetItem(0))->GetNextLink(); 
      // If I'm moving this to a HB, may need to add "orig_wt" attr
      if ((predecessor->GetRegionType() == RT_HB) && 
          (FindLcAttribute( "use_orig_wt",  predecessor) != NULL )) {
        AddWeightAttribute (moveop);
        // Copy predecessor op's PredVector
        if (predecessorop->GetPredVectorPtr() != NULL) {
          moveop->SetPredVectorPtr(new bitvector(*predecessorop->GetPredVectorPtr()));
//        moveop->GetPredVectorPtr()->Show();
        }
//      cerr << "OpId = " << moveop->GetOpId() << " (a RemoveUncond op)\n";
      }
      RemoveMidOp(moveop, NO); // don't destroy this one
      AddMidOp(moveop, predecessorbeforeop);
      predecessorbeforeop = moveop;
//      cerr << "op " << moveop->GetOpId() << " moved from sourceblock to predecessor block\n";
    }
    // Now handle the branches (LastOps)
    moveop = ((legoOp *) sourceblock->GetItem(0))->GetNextLink(); 
    // If I'm moving this to a HB, may need to add "orig_wt" attr
    if ((predecessor->GetRegionType() == RT_HB) && 
        (FindLcAttribute( "use_orig_wt",  predecessor) != NULL )) {
      AddWeightAttribute (moveop);
      // Copy predecessor op's PredVector
      if (predecessorop->GetPredVectorPtr() != NULL) {
        moveop->SetPredVectorPtr(new bitvector(*predecessorop->GetPredVectorPtr()));
//      moveop->GetPredVectorPtr()->Show();
      }
//      cerr << "OpId = " << moveop->GetOpId() << " (a RemoveUncond op)\n";
    }
    // remove the edge from the c_merge to this branch op
    RemoveEdge ((legoOp *) sourceblock->GetItem(0), moveop, parentproc, ET_CNTL);
    // remove this op from allList
    if ((listop = parentproc->GetListOpPtr()) != moveop) {
      for (;
           listop != NULL && listop->GetListOpPtr() != moveop;
           listop = listop->GetListOpPtr())
        /* do nothing */;
    }
    if (listop != NULL)
      {
        if (parentproc->GetListOpPtr() != moveop)
          listop->SetListOpPtr (moveop->GetListOpPtr());
        else
          parentproc->SetListOpPtr (moveop->GetListOpPtr());
      } // end if
    moveop->SetListOpPtr (NULL);
    
    // Detach from region.
    sourceblock->Detach(sourceblock->Search(moveop));
//    RemoveLastOp(moveop, NO); // don't destroy this one
    AddMidOp(moveop, predecessorbeforeop);
    oldbranch = moveop->GetNextLink();
    // remove the edge just created by AddMidOp between newbranch and oldbranch
    RemoveEdge (moveop, oldbranch, parentproc, ET_CNTL);
    // remove the edge from the uncond. branch to the c_merge
    RemoveEdge (oldbranch, (legoOp *) sourceblock->GetItem(0), parentproc, ET_CNTL);
    // destroy the uncond. branch in predecessor 
    // we'll do this one the old fashion way 
    // Fix the Links
    oldbranch->GetPrevLink()->SetNextLink (NULL);
    oldbranch->SetPrevLink (NULL);
    oldbranch->SetNextLink (NULL);
    // remove from allList 
    if ((listop = parentproc->GetListOpPtr()) != oldbranch) {
      for (;
           listop != NULL && listop->GetListOpPtr() != oldbranch;
           listop = listop->GetListOpPtr())
        /* do nothing */;
    }
    if (listop != NULL)
      {
        if (parentproc->GetListOpPtr() != oldbranch)
          listop->SetListOpPtr (oldbranch->GetListOpPtr());
        else
          parentproc->SetListOpPtr (oldbranch->GetListOpPtr());
      } // end if
    oldbranch->SetListOpPtr (NULL);
    
    // Detach from region.
    predecessor->Detach(predecessor->Search(oldbranch));

    attrList *atl;
    attrs *a;
    enum attrTypes atype;
    
    RemoveLiveAttribute (oldbranch, parentproc);  // kill live attribute right off
    
    atl = oldbranch->GetOpAttrListPtr();
    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(), oldbranch, parentproc);
        
        atl = oldbranch->GetOpAttrListPtr();  // reset for next scan
      } // end while
    delete oldbranch;
    
//    RemoveLastOp(oldbranch, YES); // destroy this one

    // destroy C_MERGE in sourceblock (last op remaining)
    // we'll do this one the old fashion way 
    // remove from allList 
    verylastop = (legoOp *) sourceblock->GetItem(0);
    if ((listop = parentproc->GetListOpPtr()) != verylastop) {
      for (;
           listop != NULL && listop->GetListOpPtr() != verylastop;
           listop = listop->GetListOpPtr())
        /* do nothing */;
    }
    if (listop != NULL)
      {
        if (parentproc->GetListOpPtr() != verylastop)
          listop->SetListOpPtr (verylastop->GetListOpPtr());
        else
          parentproc->SetListOpPtr (verylastop->GetListOpPtr());
      } // end if
    verylastop->SetListOpPtr (NULL);
    
    // Detach from region.
    sourceblock->Detach(0);

    RemoveLiveAttribute (verylastop, parentproc);  // kill live attribute right off
    
    atl = verylastop->GetOpAttrListPtr();
    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(), verylastop, parentproc);
        
        atl = verylastop->GetOpAttrListPtr();  // reset for next scan
      } // end while
    delete verylastop;
    
    // now destroy sourceblock
    dupparent = sourceblock->GetParentPtr();
    if (dupparent == NULL)
    {
      LegoFatal ("TailDuplicate", "Can't find parent of sourceblock to be removed %d.", sourceblock->GetRegionId());
    } 
    // Get rid of attributes before destroying sourceblock
    RemoveLiveAttribute (sourceblock, parentproc); 
    atl = sourceblock->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(), sourceblock, parentproc);
        
        atl = sourceblock->GetRegionAttrListPtr();  // reset for next scan
      } // end while
    i = dupparent->Search (sourceblock);
    if (i == MAX_UNSIGNED)
      {
        LegoFatal ("TailDuplicate", "Can't find sourceblock block %d in its "
                      "parent region %d.", sourceblock->GetRegionId(),
                      dupparent->GetRegionId());
      } // end if
    // Destroying blocks seems to fuck 
    // up things such as ParentBlockPtrs of Ops. So I will 
    // just leave them as orphaned blocks now and mark them. 
    // Will skip them in later in treeform()
//    sourceblock->Mark (RM_GENERAL);
    dupparent->DestroyItem (i);
//    cerr << "sourceblock " << sourceblock->GetRegionId() << " removed from parent region " << dupparent->GetRegionId() << " of region type " << dupparent->GetRegionType() << "\n";
//    if (!(dupparent->IsOwner())) 
//      delete sourceblock;

    switch (predecessor->GetRegionType())
      {
      case RT_BB:
        ((legoBB *) predecessor)->RefreshOps(); 
        ((legoBB *) predecessor)->RefreshEdges(); 
        break;
      case RT_SB:
        ((legoSB *) predecessor)->RefreshOps(); 
        ((legoSB *) predecessor)->RefreshEdges(); 
        break;
      case RT_HB:
        ((legoHB *) predecessor)->RefreshOps(); 
        ((legoHB *) predecessor)->RefreshEdges(); 
        break;
      default:
        LegoFatal ("RemoveUncondBranch", "Can not determine RegionType");
      } // end switch

//    predecessor->RefreshOps();
//    predecessor->RefreshEdges();

    region = (legoRegion *) predecessor->GetParentPtr(); 
    if (region->GetRegionType() == RT_TREE) {
      ((legoTreegion *)region)->RefreshOps();
      ((legoTreegion *)region)->RefreshEdges();
    }
    if (region->GetRegionType() == RT_PROC) 
      ((legoProc *)region)->RefreshOps();
    
    return 1;
  }
  else {
    return 0;
  }
}

/*
 *
 * This is a recursive function for breaking a superblock region into its 
 * component BB regions. If the input region has more than one sub-block, 
 * the top sub-block is split off and added to the encompassing proc. A 
 * pointer to the remaining sub-block(s) is returned or NULL is returned 
 * if the input region has only one sub-block (i.e. only a BB remains).
 * NULL is also returned if the region has more than one entry op 
 * (i.e. not a superblock/hyperblock or any known region for that matter)
 *
 */
void
UnBindSB ( legoHB *HB_region ) {
  
  opList *entry_op_list; 
  legoOp *curr_op, *last_op_HB_region, *first_op_new_region, *last_op_new_region;
  legoOp *detach_op, *prev_detach_op; 
  legoHB *new_region;
  legoProc *parentproc;
  int max_region_id, eaid;
  attrs *attrdictionary, *attrtail, *atscan;
  attrList *atlscan;
  double BBweight = 0; 
  edgeList *entry_edges_list;
  opEdges  *entry_edge;
  
  // Step through the ops in the HB_region to determine if there is more than 
  // one real branch in the region. If so, the region must be split.
  
  entry_op_list = HB_region->GetEntryOpsPtr();
  // return if region has more than one entry op (can't think of any 
  // region types where this would be the case).
  if (entry_op_list->GetNextListPtr() != NULL) {
    cerr << "Region " << HB_region->GetRegionId() 
      << " has more than one entry op \n";
    return;
  }
  else {
    curr_op = entry_op_list->GetOpPtr();
  }
  
  // step through the ops in the region in program order until a branch or 
  // DUMMY_BR is found (excluding BRLs)
  while ( (IsBranchOpButNotBRL(curr_op) != TRUE) && (curr_op != NULL) ) {
    curr_op = curr_op->GetNextLink();
  }
  if (curr_op == NULL) {
    cerr << "Region " << HB_region->GetRegionId() 
      << " does not have a branch op \n";
    return;
  }

  // The top portion of the input HB is split off as a BB
  HB_region->SetRegionType(RT_BB);
  
  // if this is the last op in HB_region, it is already a BB.
  if (curr_op->GetNextLink() == NULL) {
    return; 
  }

  // otherwise, split region at this boundary 

  // 1. copy construct a new region
  parentproc = (legoProc *) FindParentRegionType (RT_PROC, HB_region);
  max_region_id = parentproc->GetParentPtr()->FindMaxRegionId()->GetRegionId();  
  new_region = (legoHB *) new legoHB (*HB_region);
  new_region->SetRegionId(max_region_id + 1);
  // set region_type to RT_HB for recursive calls 
  new_region->SetRegionType(RT_HB);
  
  // 2. Duplicate region attributes.
  eaid = FindMaxEdgeAttrId (parentproc);
  attrdictionary = parentproc->GetAttrDictionary();
  if (attrdictionary == NULL)
    {
      LegoNonFatal ("UnBindSB",
                    "Attribute dictionary is missing.");
      return;
    } // end if
  for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
       attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;
  for (atlscan = new_region->GetRegionAttrListPtr(); atlscan != NULL;
       atlscan = atlscan->GetNextListPtr())
    {
      if (atlscan->GetAttrPtr() == NULL)
        continue;
      atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
      atlscan->SetAttrPtr (atscan);
      atscan->SetAttrId (eaid);
      atlscan->SetAttrId (eaid);
      attrtail->SetNextAttrPtr (atscan);
      attrtail = attrtail->GetNextAttrPtr();
    } // end for


  // 3. Split linked list of ops at the curr_op branch/C_MERGE boundary and 
  //    update allListPtr

  for (last_op_HB_region = curr_op, last_op_new_region = curr_op; 
       last_op_new_region->GetNextLink() != NULL; 
       last_op_new_region = last_op_new_region->GetNextLink() ) /* do nothing */ ;

  first_op_new_region = curr_op->GetNextLink();
  first_op_new_region->SetPrevLink(NULL);
  curr_op->SetNextLink(NULL);

  HB_region->SetListOpPtr(last_op_HB_region);
  new_region->SetListOpPtr(last_op_new_region);
     
  // detach ops that we have already scanned from new_region
  detach_op = entry_op_list->GetOpPtr();
  while ( detach_op != curr_op ) {
    prev_detach_op = detach_op;
    detach_op = detach_op->GetNextLink();
    new_region->Detach(new_region->Search(prev_detach_op));
  }
  // include the detach of curr_op, which remains the last op in HB_region
  new_region->Detach(new_region->Search(detach_op));

  // detach remaining ops from original HB_region 
  // and update their parentBlockPtr to new_region
  detach_op = first_op_new_region;
  while ( detach_op != NULL ) {
    prev_detach_op = detach_op;
    detach_op = detach_op->GetNextLink();
    prev_detach_op->SetParentBlockPtr(new_region);
    HB_region->Detach(HB_region->Search(prev_detach_op));
  }

  // 4. pray that RefreshOpsAndEdges will clean up the mess for each block
  HB_region->RefreshOps();
  HB_region->RefreshEdges();
  new_region->RefreshOps();
  new_region->RefreshEdges();

  // 5. update region weights for new_region, SB_region should still be ok
  entry_edges_list = new_region->GetInEdgesPtr();
  if (entry_edges_list != NULL) {
    entry_edge = entry_edges_list->GetEdgePtr(); 
    while (entry_edge != NULL) {
      BBweight += (double) FindEdgeFrequency (entry_edge);
      entry_edges_list = entry_edges_list->GetNextListPtr();
      if (entry_edges_list == NULL)
        entry_edge = NULL;
      else 
        entry_edge = entry_edges_list->GetEdgePtr();
    }
  }
  new_region->SetWeight(BBweight); 
  
  // recursively call UnBindSB on remainder of region
  UnBindSB(new_region);
  
  return; 
  
}

/*
 *
 * calls UnBindSB( legoRegion * ) for each region of the Proc
 *
 */
void
UnBindSB ( legoProc *proc ) {

  legoRegion *region;
  enum regionTypes region_type; 
  
  for (unsigned i = 0; i < proc->GetCount(); i++) {
    region = (legoRegion *) proc->GetItem (i);
    region_type = region->GetRegionType();
    // Rebel uses RT_HB for superblock regions
    // we eventually need to distinquish between real hyperblocks (e.g. due to 
    // hammock conversion) and superblock hyperblocks so that UnBindSB does 
    // not assign RT_BB to true hyperblocks that should be RT_HB
    if ( region_type == RT_HB )
      UnBindSB((legoHB *) region); 
  }
}


// FullyResolvePredicates: Create complementary second predicate destinations 
// for CMPP ops for future use. New second predicate destinations are not 
// used in our source Rebel until transformations such at hammock conversion, 
// if conversion, predication, etc. Opcodes will be changed from _UN_UN to 
// _UN_UC couterparts. 
void FullyResolvePredicates( legoRegion *Region, legoOp *PredecessorCMPP )
{
  regionList *Descendant;
  legoRegion *ParentRegion, *CurrentRegion; 
  legoOp *CurrentOp, *BranchOp, *PBROp, *ThisPredecessorCMPP;
  int OpCount, i, MaxRegNum;
  legoOprd *p1, *p2, *new_predicate; 
  
  MaxRegNum = FindMaxRegNum ((legoProc *) FindParentRegionType (RT_PROC, Region));

  ParentRegion = Region->GetParentPtr();
  
  ThisPredecessorCMPP = PredecessorCMPP;
  PredecessorCMPP = NULL; 
  
  OpCount = Region->GetCount();
  for (i = 0; i < OpCount; i++) {
    
    CurrentOp = (legoOp *) Region->GetItem(i); 
    
    // 
    if (CurrentOp->GetOpcode() >= CMPP_W_FALSE_UN_UN &&
        CurrentOp->GetOpcode() <= FCMPP_D_TRUE_AC_AC) {
      derr( "CMPP op found (OpId = " << CurrentOp->GetOpId() << ")\n" ); 
      
      // make sure that the second D-action is a complement (odd-number opcode)
      div_t remainder = div(CurrentOp->GetOpcode(), 2);
      if (remainder.rem == 0) {
        CurrentOp->SetOpcode((CurrentOp->GetOpcode() + 1));
      }
      else {
        // Assume Already Fully Resolved
        cerr << "\nAssuming already Fully Resolved\n";
        return; 
     }
      
      p1 = CurrentOp->GetDestOprdPtr();  // first destination!
      if (p1 == NULL || p1->GetNextOprdPtr() == NULL)
        {
          LegoFatal ("FullyResolvePredicates", "CMPP %d has bad destinations.", CurrentOp->GetOpId());
        } // end if
      p2 = p1->GetNextOprdPtr();  // p2 is there always!
      if (p1->GetNextOprdPtr()->GetOprdType() != OT_UNDEFINED) {
        ; // Good. We already have a second predicate
      }
      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

      // Tail Duplication results in duplicate predicate register numbers. 
      // Safer is each CMPP dest has a unique number 
      p1->SetOprdRegNum (++MaxRegNum);
      // Also update the branch this CMPP reaches
      for (BranchOp = CurrentOp->GetNextLink(); 
           ((BranchOp->GetOpcode() != BRCT) && 
            (BranchOp->GetOpcode() != BRCF));
           BranchOp = BranchOp->GetNextLink()) 
        ;// Do nothing
      BranchOp->GetSrcOprdPtr()->GetNextOprdPtr()->SetOprdRegNum(MaxRegNum);
      
      if (ThisPredecessorCMPP != NULL) {
        
        // Find the BRCT or BRCF for this CMPP
        for (BranchOp = ThisPredecessorCMPP->GetNextLink(); 
             ((BranchOp->GetOpcode() != BRCT) && 
              (BranchOp->GetOpcode() != BRCT));
             BranchOp = BranchOp->GetNextLink()) 
          ;// Do nothing

        // Find the PBR for this conditional branch
        for (PBROp = BranchOp->GetPrevLink(); 
             ((PBROp->GetOpcode() != PBRR) && 
              (PBROp->GetOpcode() != PBRA));
             PBROp = PBROp->GetPrevLink()) 
          ;// Do nothing

        // Predicate this CMPP op on the appropriate predecessor CMPP dest
        if (BranchOp->GetOpcode() == BRCT) {
          if (PBROp->GetSrcOprdPtr()->GetLiteralControlBlock() == 
              ((legoRegion *) CurrentOp->GetParentBlockPtr())->GetRegionId()) {
            new_predicate = new legoOprd(*ThisPredecessorCMPP->GetDestOprdPtr());
          }
          else {
            new_predicate = new legoOprd(*ThisPredecessorCMPP->GetDestOprdPtr()
                                         ->GetNextOprdPtr());
          }
        }
        else {
          if (PBROp->GetSrcOprdPtr()->GetLiteralControlBlock() == 
              ((legoRegion *) CurrentOp->GetParentBlockPtr())->GetRegionId()) {
            new_predicate = new legoOprd(*ThisPredecessorCMPP->GetDestOprdPtr()
                                         ->GetNextOprdPtr());
          }
          else {
            new_predicate = new legoOprd(*ThisPredecessorCMPP->GetDestOprdPtr());
          }
        }
        new_predicate->SetNextOprdPtr(NULL);
        new_predicate->SetParentOpPtr(CurrentOp);
        CurrentOp->SetPredOprdPtr(new_predicate);
      }
      PredecessorCMPP = CurrentOp; 
      break; 
    }
  }

  // Mark this block
  Region->Mark( RM_GENERAL );
  
  derr( "   Examining children of region " << Region->GetRegionId()
       << "\n" );
  // Cycle through all of the children for the current node being processed
  for (Descendant = Region->GetChildren(); 
       Descendant != NULL;
       Descendant = Descendant->GetNextListPtr() ) {
    
    derr( "   Child of region " << Region->GetRegionId()
         << " is region " << Descendant->GetRegionPtr()->GetRegionId()
         << "\n" );
    // Check if the current descendant is in the same tree.
    if ( ParentRegion != Descendant->GetRegionPtr()->GetParentPtr()
        || Region == Descendant->GetRegionPtr()
        || Descendant->GetRegionPtr()->IsMarked( RM_GENERAL ) == 1 )
      continue;
    
    CurrentRegion = Descendant->GetRegionPtr();
    derr( " FullyResolvePredicates for region " << CurrentRegion->GetRegionId()
         << "\n" );
    FullyResolvePredicates( CurrentRegion, PredecessorCMPP );
  }
  
  derr( "<< FullyResolvePredicates: block " << Region->GetRegionId()
       << " -- DONE\n" );
}

//HZ: code transformation for multiple (two actually) copies of code
//
//Function name: MulCpBB(legoBB *BB_orig) 
//
//step 1. create a new BB named BB_header. Copy the inedgesPtr and parents
// information of BB_orig to BB_header. Fill in the BB with the ops of CMERGE,
// HW probing instruction e.g., LDPRED, CMP instruction setting the branch
// condition, and the branch instruction. Set the entryops and exitops Ptr, copy
// the inListPtr of the CMERGE of BB_orig to the CMERGE of BB_header. 
//
//step 2. duplicate BB_orig (the duplicate name BB_dup). 
//
//step 3. Create edges between
// BB_header and BB_orig, between BB_header and BB_dup. Set parent chidlren
// relationship among them.
//
void MulCpBB(legoBB *BB_orig)
{
    legoProc * parentproc = (legoProc *) FindParentRegionType (RT_PROC, BB_orig);
    int max_op_id = FindMaxOpId(parentproc)->GetOpId();
            
    //step 0. Make up a new op (brct br)

    legoOp * cond_br;
    cond_br = new legoOp (++max_op_id);
    cond_br->SetOpcode (BRCT);
    
    int max_reg_num = FindMaxRegNum(parentproc);

    legoOprd *oprd;
    oprd = new legoOprd;
    oprd->SetOprdType (OT_REG);
    oprd->SetOprdFileType(FT_BTR);
    oprd->SetOprdRegType (RT_R);
    oprd->SetOprdDataType (DT_B);
    int btr_num = ++max_reg_num;
    oprd->SetOprdRegNum(btr_num);
    oprd->SetParentOpPtr (cond_br);
    cond_br->SetSrcOprdPtr (oprd);
    
    legoOprd *oprd2;
    oprd2 = new legoOprd;
    oprd2->SetOprdType (OT_REG);
    oprd2->SetOprdFileType(FT_PR);
    oprd2->SetOprdRegType (RT_R);
    oprd2->SetOprdDataType (DT_P);
    int pr_num = ++max_reg_num;
    oprd2->SetOprdRegNum(pr_num);
    oprd2->SetParentOpPtr (cond_br);
    oprd->SetNextOprdPtr (oprd2);    
        
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_P);
    oprd->SetParentOpPtr (cond_br);
    oprd->SetLiteralPredicate(1);
    cond_br->SetPredOprdPtr (oprd);    
    
    AddMidOp(cond_br, (legoOp *)BB_orig->GetItem(0));
    
    //add LDPRED op in the header_bb
    legoOp * new_ld;
    new_ld = new legoOp (++max_op_id);
    new_ld->SetOpcode (LDPRED);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_REG);
    oprd->SetOprdFileType(FT_GPR);
    oprd->SetOprdRegType (RT_R);
    oprd->SetOprdDataType (DT_I);
    int ld_gpr_num = ++max_reg_num;
    oprd->SetOprdRegNum(ld_gpr_num);
    oprd->SetParentOpPtr (new_ld);
    new_ld->SetDestOprdPtr (oprd);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_I);
    oprd->SetParentOpPtr (new_ld);
    oprd->SetLiteralInteger(0);
    new_ld->SetSrcOprdPtr (oprd);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_P);
    oprd->SetParentOpPtr (new_ld);
    oprd->SetLiteralPredicate(1);
    new_ld->SetPredOprdPtr (oprd);    
    
    AddMidOp(new_ld, (legoOp *)BB_orig->GetItem(0));
    
    //add PBRR op in the header_bb
    legoOp * pbrr_op;
    pbrr_op = new legoOp (++max_op_id);
    pbrr_op->SetOpcode (PBRR);
    
    oprd = new legoOprd;
    
    oprd->SetOprdType (OT_REG);
    oprd->SetOprdFileType(FT_BTR);
    oprd->SetOprdRegType (RT_R);
    oprd->SetOprdDataType (DT_B);
    oprd->SetOprdRegNum(btr_num);
    oprd->SetParentOpPtr (pbrr_op);
    pbrr_op->SetDestOprdPtr (oprd);
    
    legoOprd * pbrrsrc_oprd = new legoOprd;
    pbrrsrc_oprd->SetOprdType (OT_LITERAL_CB);
    pbrrsrc_oprd->SetParentOpPtr (pbrr_op);
    pbrr_op->SetSrcOprdPtr(pbrrsrc_oprd);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_I);
    oprd->SetParentOpPtr (pbrr_op);
    oprd->SetLiteralInteger(0);
    pbrrsrc_oprd->SetNextOprdPtr (oprd);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_P);
    oprd->SetParentOpPtr (pbrr_op);
    oprd->SetLiteralPredicate(1);
    pbrr_op->SetPredOprdPtr (oprd);    
    
    AddMidOp(pbrr_op, new_ld);
    
    //add CMPP op in the header_bb
    legoOp * cmpp_op;
    cmpp_op = new legoOp (++max_op_id);
    cmpp_op->SetOpcode (CMPP_W_EQ_UN_UN);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_REG);
    oprd->SetOprdFileType(FT_PR);
    oprd->SetOprdRegType (RT_R);
    oprd->SetOprdDataType (DT_P);
    oprd->SetOprdRegNum(pr_num);
    oprd->SetParentOpPtr (cmpp_op);
    cmpp_op->SetDestOprdPtr(oprd);
    
    oprd2 = new legoOprd;
    oprd2->SetOprdType (OT_UNDEFINED);
    oprd2->SetParentOpPtr (cmpp_op);
            
    oprd->SetNextOprdPtr (oprd2);    

    oprd = new legoOprd;
    oprd->SetOprdType (OT_REG);
    oprd->SetOprdFileType(FT_GPR);
    oprd->SetOprdRegType (RT_R);
    oprd->SetOprdDataType (DT_I);
    oprd->SetOprdRegNum(ld_gpr_num);
    oprd->SetParentOpPtr (cmpp_op);
    cmpp_op->SetSrcOprdPtr (oprd);
    
    oprd2 = new legoOprd;
    oprd2->SetOprdType (OT_LITERAL_I);
    oprd2->SetParentOpPtr (cmpp_op);
    oprd2->SetLiteralInteger(0);
    oprd->SetNextOprdPtr(oprd2);
    
    oprd = new legoOprd;
    oprd->SetOprdType (OT_LITERAL_P);
    oprd->SetParentOpPtr (cmpp_op);
    oprd->SetLiteralPredicate(1);
    cmpp_op->SetPredOprdPtr (oprd);    
    
    AddMidOp(cmpp_op, pbrr_op);
        
    //step 1, fortunately, there is a legoUtil function that we can use
    // to save the trouble here.    
//    legoBB * new_orig_bb = (legoBB *) SplitParentBlockBeforeOp(
//          BB_orig->GetEntryOpsPtr()->GetOpPtr()->GetNextLink());
    legoBB * new_orig_bb = (legoBB *) SplitParentBlockBeforeOp(
            cond_br->GetNextLink());
    legoBB * header_bb = BB_orig;
    
    
//    BB_orig->RefreshEdges();
    //step 2. BB duplicate, as it is not tail duplication, the entry edges are
    // not set as well as the inoplist of its CMERGE
    legoBB * dup_bb = BBDuplicate(new_orig_bb);
    
    //step 3. Fix the control edges among BB header, BB_dup, and BB_orig
    legoOp *from_op, *to_op;
    from_op = header_bb->GetExitOpsPtr()->GetOpPtr();
    to_op = dup_bb->GetEntryOpsPtr()->GetOpPtr();
    opEdges * edge1;
    edge1 = AddEdge(from_op, to_op, ET_CNTL);
    if(edge1 == NULL)
        LegoFatal ("MulCpBB", "Adding edge failed");
    header_bb->RefreshAll(); 
    //AddToList(header_bb->GetOutEdgesPtr(), edge1);
    //AddToList(dup_bb->GetInEdgesPtr(), edge1);
    dup_bb->RefreshAll();
    AddToList(from_op->GetOutListPtr(), to_op, 1, 0);
    AddToList(to_op->GetInListPtr(), from_op, 1, 0);
    
    pbrrsrc_oprd->SetLiteralControlBlock(dup_bb->GetRegionId());

}

//Duplicate a BB (BB_orig). Returns a pointer to the duplicated BB
legoBB * BBDuplicate(legoBB * BB_orig)
{
  regionList *allparents, *allchildren, *lrrscan, *oparents, *ochildren;
  int i, j, bingo, regionid, opid, eaid;
  double edgeweight, sourceweightratio;
  legoRegion *head, *duplicate, *region;
  legoProc *parentproc;
  legoOp *headop, *origop, *origop2, *dupop, *dupop2;
  legoOprd *oprd;
  opEdges *edgedictionary, *edgetail, *oescan;
  attrs *attrdictionary, *attrtail, *atscan;
  opList *oplscan, *oplscanprev;
  attrList *atlscan, *atl;
  edgeList *edlscan, *edlscanprev, *edlheadtosource;

  pointer_map *map, *tail;

  // First, some checking.
  if (BB_orig->GetRegionType() != RT_BB)
    {
      LegoNonFatal ("BBDuplicate",
                    "Region %d not a basic block.", BB_orig->GetRegionId());
      return NULL;
    } // end if

  allparents = BB_orig->GetParents();

  tail = map = new pointer_map;  // initialize pointer mapping table

  // Find parent proc.
  parentproc = (legoProc *) FindParentRegionType (RT_PROC, BB_orig);
  if (parentproc == NULL)
    LegoFatal ("BBDuplicate", "Can't find parent proc of region %d.",
               BB_orig->GetRegionId());

  // Get dictionaries.
  edgedictionary = parentproc->GetEdgeDictionary();
  if (edgedictionary == NULL)
    {
      LegoNonFatal ("BBDuplicate",
                    "Proc Edge dictionary is missing.");
      return NULL;
    } // end if
  attrdictionary = parentproc->GetAttrDictionary();
  if (attrdictionary == NULL)
    {
      LegoNonFatal ("BBDuplicate",
                    "Attribute dictionary is missing.");
      return NULL;
    } // end if

  // Set up tail pointers and max edge/attr id.
  for (edgetail = edgedictionary; edgetail->GetNextOpEdgePtr() != NULL;
       edgetail = edgetail->GetNextOpEdgePtr()) /* do nothing */;

  for (attrtail = attrdictionary; attrtail->GetNextAttrPtr() != NULL;
       attrtail = attrtail->GetNextAttrPtr()) /* do nothing */;

  eaid = FindMaxEdgeAttrId (parentproc);

  // Before we begin, remember the parents and children of sourceregion.
  // Form them even if they're not there.
  if (BB_orig->GetParents() != NULL)
    oparents = new regionList (*(BB_orig->GetParents())); 
    //HZ: should be the BB_header
  else
    oparents = NULL;
  if (BB_orig->GetChildren() != NULL)
    ochildren = new regionList (*(BB_orig->GetChildren()));
  else
    ochildren = NULL;

  // -----------------------------------------------------------------------
  // Step 1.  Duplicate the region (including ops).
  // -----------------------------------------------------------------------

  // 1a. Copy construct the region.
  
  duplicate = new legoBB (*(legoBB *) BB_orig);

  region = ((legoRegion *) parentproc->GetParentPtr())->FindMaxRegionId();
  regionid = region->GetRegionId();
  duplicate->SetRegionId (++regionid);

  // 1b. Duplicate region attributes.
  for (atlscan = duplicate->GetRegionAttrListPtr(); atlscan != NULL;
       atlscan = atlscan->GetNextListPtr())
    {
      if (atlscan->GetAttrPtr() == NULL)
        continue;
      atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
      atlscan->SetAttrPtr (atscan);
      atscan->SetAttrId (eaid);
      atlscan->SetAttrId (eaid);
      attrtail->SetNextAttrPtr (atscan);
      attrtail = attrtail->GetNextAttrPtr();
    } // end for

  opid = (FindMaxOpId ((legoProc *) parentproc))->GetOpId();

  // 1c. Copy construct each op from sourceregion to duplicate.
  for (origop = BB_orig->GetEntryOpsPtr()->GetOpPtr();
       origop != NULL;
       origop = origop->GetNextLink())
    {
      // 1c,i. Copy construct the op itself.
      dupop = new legoOp (*origop);
      tail = tail->record (origop, dupop);
      dupop->SetOpId (++opid);  // assign new id
      dupop->SetParentBlockPtr (duplicate);

      // Find origop in duplicate (there because of copy constructor).
      for (i = 0; i < duplicate->GetCount(); i++)
        {
          origop2 = (legoOp *) duplicate->GetItem (i);
          if (origop2 == origop) break;
        } // end for
      if (i == duplicate->GetCount())
        LegoFatal ("TailDuplicate", "Can't find original "
                   "op %d in duplicate.", origop->GetOpId());
      duplicate->Detach (i);  // remove original, slide down rest.  Then, ...
      duplicate->AddItem (dupop);  // add duplicate to end of region

      // 1c,ii. Duplicate op attributes.
      for (atlscan = dupop->GetOpAttrListPtr(); atlscan != NULL;
           atlscan = atlscan->GetNextListPtr())
        {
          if (atlscan->GetAttrPtr() == NULL)
            continue;
          atscan = new attrs (*(atlscan->GetAttrPtr()), dupop, ++eaid);
          atlscan->SetAttrPtr (atscan);
          atscan->SetAttrId (eaid);
          atlscan->SetAttrId (eaid);
          attrtail->SetNextAttrPtr (atscan);
          attrtail = attrtail->GetNextAttrPtr();
        } // end for

    } // end for

  // 1d. Update duplicate's entry/exit ops.
  //duplicate->RefreshOps();

  // -----------------------------------------------------------------------
  // Step 2.  Update intra-block links, create new intra-block edges.
  // -----------------------------------------------------------------------

  // For each duplicated op...
  for (i = 0; i < duplicate->GetCount(); i++)
    {
      dupop = (legoOp *) duplicate->GetItem(i);
      // 2a. Update links and edges.
      if (i != duplicate->GetCount() - 1)
        {
          // 2a,i. Set previous and next links.
          dupop2 = (legoOp *) duplicate->GetItem(i + 1);
          dupop->SetNextLink (dupop2);
          dupop2->SetPrevLink (dupop);

          // 2a,ii. Hunt down original edge between them.
          // Find original ops by following duplicateOpsPtr list.
          for (oplscan = dupop->GetDuplicateOpsPtr(); oplscan != NULL;
               oplscan = oplscan->GetNextListPtr())
            if ((legoRegion *) oplscan->GetOpPtr()->GetParentBlockPtr()
                == BB_orig) break;
          if (oplscan == NULL)
            {
              LegoNonFatal ("BBDuplicate",
                            "Can't find original op for duplicate op %d.",
                            dupop->GetOpId());
              return NULL;
            } // end if
          origop = oplscan->GetOpPtr();
          for (oplscan = dupop2->GetDuplicateOpsPtr(); oplscan != NULL;
               oplscan = oplscan->GetNextListPtr())
            if ((legoRegion *) oplscan->GetOpPtr()->GetParentBlockPtr()
                == BB_orig) break;
          if (oplscan == NULL)
            {
              LegoNonFatal ("BBDuplicate",
                            "Can't find original op for duplicate op %d.",
                            dupop2->GetOpId());
              return NULL;
            } // end if
          origop2 = oplscan->GetOpPtr();

          oescan = FindControlEdge (origop, origop2);
          if (oescan == NULL)
            {
              LegoNonFatal ("BBDuplicate",
                            "Can't find edge between original ops %d and %d.",
                            origop->GetOpId(), origop2->GetOpId());
              return NULL;
            } // end if

          // 2a,iii. Copy construct a new edge between dupop and dupop2.
          edgetail->SetNextOpEdgePtr
            (new opEdges (*oescan, ++eaid, dupop->GetOpId(),
                          dupop, dupop2->GetOpId(), dupop2));
          edgetail = edgetail->GetNextOpEdgePtr();

          // 2a,iv. Duplicate edge attributes.
          for (atlscan = edgetail->GetEdgeAttrListPtr(); atlscan != NULL;
               atlscan = atlscan->GetNextListPtr())
            {
              if (atlscan->GetAttrPtr() == NULL)
                continue;
              atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
              atlscan->SetAttrPtr (atscan);
              atscan->SetAttrId (eaid);
              atlscan->SetAttrId (eaid);
              attrtail->SetNextAttrPtr (atscan);
              attrtail = attrtail->GetNextAttrPtr();
            } // end for

          // 2a,v. If dupop has an outlist, change the entry pointing
          //       to origop2 to point to dupop2.
          if (dupop->GetOutListPtr() != NULL)
            for (oplscan = dupop->GetOutListPtr(); oplscan != NULL;
                 oplscan = oplscan->GetNextListPtr())
              if (oplscan->GetOpId() == origop2->GetOpId())
                {
                  oplscan->SetOpPtr (dupop2);
                  oplscan->SetOpId (dupop2->GetOpId());
                } // end if (, for, if)

        } // end if

      // 2b. Update allListPtr as appropriate - ops are enqueued in reverse.
      if (i == 0)
        dupop->SetListOpPtr (parentproc->GetListOpPtr());
      if (i == duplicate->GetCount() - 1)
        parentproc->SetListOpPtr (dupop);
      else
        dupop2->SetListOpPtr (dupop);
        
    } // end for
    
    duplicate->RefreshOps();
    duplicate->RefreshEdges();
  // -----------------------------------------------------------------------
  // Step 3.  Connect head and duplicate exclusively (handle jumptables later).
  // -----------------------------------------------------------------------
  

  // -----------------------------------------------------------------------
  // Step 4.  Connect duplicate to sourceregion' children.
  // -----------------------------------------------------------------------

  allchildren = BB_orig->GetChildren();
  sourceweightratio = BB_orig->GetWeight() + duplicate->GetWeight();
  if (sourceweightratio != 0.0)
    sourceweightratio = BB_orig->GetWeight() / sourceweightratio;
  // fraction of weight in original

  // For each child of source region ...
  if(allchildren != NULL)
  for (lrrscan = allchildren; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      if (region == NULL) continue;

      // 4a. Invalidate child's parents.
      region->SetParents (NULL);

      // 4b. Hunt down all edges between sourceregion and child and ...
      for (oescan = edgedictionary;
           oescan->GetNextOpEdgePtr() != NULL;
           oescan = oescan->GetNextOpEdgePtr())
        {
          origop = oescan->GetFromOpPtr();
          origop2 = oescan->GetToOpPtr();
          if ( ((legoRegion *)(origop->GetParentBlockPtr()) == BB_orig) &&
               ((legoRegion *)(origop2->GetParentBlockPtr()) ==
                region) )  // from sourceregion to child
            {
              dupop = (legoOp *) map->lookup_duplicate (origop);
              if (dupop == NULL)
                LegoFatal ("BBDuplicate", "Mapping error.");

              // 4b,i. Add a new control edge.
              edgetail->SetNextOpEdgePtr  // make from duplicate to child
                (new opEdges (*oescan, ++eaid, dupop->GetOpId(),
                                  dupop, origop2->GetOpId(), origop2));
              edgetail = edgetail->GetNextOpEdgePtr();
              //              edgetail = AddEdge (dupop, origop2, ET_CNTL);
              //              eaid++;

              // 4b,ii. Duplicate edge attributes.
              
              //HZ:
              //edgetail->SetEdgeAttrListPtr (new attrList
              //                            (*(oescan->GetEdgeAttrListPtr())));
              if(oescan->GetEdgeAttrListPtr() != NULL)
                edgetail->SetEdgeAttrListPtr (new attrList
                                            (*(oescan->GetEdgeAttrListPtr())));
              else
                edgetail->SetEdgeAttrListPtr(NULL);  
              for (atlscan = edgetail->GetEdgeAttrListPtr(); atlscan != NULL;
                   atlscan = atlscan->GetNextListPtr())
                {
                  if (atlscan->GetAttrPtr() == NULL)
                    continue;
                  atscan = new attrs (*(atlscan->GetAttrPtr()), NULL, ++eaid);
                  atlscan->SetAttrPtr (atscan);
                  atscan->SetAttrId (eaid);
                  atlscan->SetAttrId (eaid);
                  attrtail->SetNextAttrPtr (atscan);
                  attrtail = attrtail->GetNextAttrPtr();
                } // end for

              // 4b,iii. Scale edge weights appropriately as well as the
              //         weights of their ops.
              // oescan is the original. edgetail is the duplicate.
              edgeweight = -1.0;
              atlscan = FindFreqAttribute (oescan);
              if (atlscan != NULL)
                {
                  edgeweight = (double)
                    (atlscan->GetAttrValPtr()->GetAttrValue());  // original wt

                  // Scale oescan's weight down to its portion.
                  atlscan->GetAttrValPtr()->SetAttrValue
                    ((int) (edgeweight * sourceweightratio));
                  atlscan->GetAttrValPtr()->GetNextIntListPtr()
                    ->SetAttrValue (1);  // it's a merge now!

                  for (oplscan = origop->GetOutListPtr(); oplscan != NULL;
                       oplscan = oplscan->GetNextListPtr())
                    if (oplscan->GetOpId() == origop2->GetOpId())
                      {
                        oplscan->SetWeight (edgeweight * sourceweightratio);
                        break;
                      } // end if

                  // Scale edgetail's weight down to its portion.
                  atlscan = FindFreqAttribute (edgetail);
                  if (atlscan != NULL)
                    {
                      atlscan->GetAttrValPtr()->SetAttrValue
                        ((int) (edgeweight * (1.0 - sourceweightratio)));
                      atlscan->GetAttrValPtr()->GetNextIntListPtr()
                        ->SetAttrValue (1);  // it's a merge now!
                    } // end if

                  for (oplscan = dupop->GetOutListPtr(); oplscan != NULL;
                       oplscan = oplscan->GetNextListPtr())
                    if (oplscan->GetOpId() == origop2->GetOpId())
                      {
                        oplscan->SetWeight
                          (edgeweight * (1.0 - sourceweightratio));
                        break;
                      } // end if
                    
                } // end if

              // 4b,iv. While we're here, fix duplicate's out edge.
              //              for (edlscan = duplicate->GetOutEdgesPtr();
              //                   edlscan != NULL;
              //                   edlscan = edlscan->GetNextListPtr())
              //                {
              //                  if (edlscan->GetEdgePtr() == oescan)
              //                    {
              //                      edlscan->SetEdgePtr (edgetail);
              //                      edlscan->SetEdgeId (edgetail->GetEdgeId());
              //                      break;
              //                    } // end if
              //                } // end for

              // 4b,iv. Oh, and while we're at it, add edge to child.
              region->RefreshEdges();
              //              for (edlscan = region->GetInEdgesPtr();
              //                   edlscan != NULL && edlscan->GetNextListPtr() != NULL;
              //                   edlscan = edlscan->GetNextListPtr()) /* nothing */;
              //              if (edlscan != NULL)
              //                {
              //                  edlscan->SetNextListPtr (new edgeList);
              //                  edlscan = edlscan->GetNextListPtr();
              //                  edlscan->SetEdgePtr (edgetail);
              //                  edlscan->SetEdgeId (edgetail->GetEdgeId());
              //                  edlscan->SetValid (1);
              //                } // end if

              // 4b,v. All right, update the child's entry op too ... geez.
              //HZ
             if(origop2->GetInListPtr() != NULL)
              for (oplscan = origop2->GetInListPtr();
                   oplscan != NULL && oplscan->GetNextListPtr() != NULL;
                   oplscan = oplscan->GetNextListPtr())  // stop before end
                if (oplscan->GetOpId() == origop->GetOpId())
                  oplscan->SetWeight (edgeweight * sourceweightratio);
              if (oplscan->GetOpId() == origop->GetOpId())  // for last one
                oplscan->SetWeight (edgeweight * sourceweightratio);
              if (oplscan != NULL)
                {
                  oplscan->SetNextListPtr (new opList);
                  oplscan = oplscan->GetNextListPtr();
                  oplscan->SetOpPtr (dupop);
                  oplscan->SetOpId (dupop->GetOpId());
                  oplscan->SetValid (1);
                  oplscan->SetWeight (edgeweight * (1.0 - sourceweightratio));
                } // end if

            } // end if (found an edge to duplicate)

        } // end for (oescan)
    } // end for (lrrscan)

  // 4c (kinda). Fix duplicate's out edges.
  duplicate->RefreshEdges();

  // Finally finally finally, kill parents and children lists:
  // Original (sourceregion's) parents...
  for (lrrscan = oparents; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      //      delete region->children;
      //      region->children = NULL;
      region->SetChildren (NULL);
      region->RefreshEdges();
    } // end for
  // Original (sourceregion's) children...
  for (lrrscan = ochildren; lrrscan != NULL;
       lrrscan = lrrscan->GetNextListPtr())
    {
      region = lrrscan->GetRegionPtr();
      //      delete region->parents;
      //      region->parents = NULL;
      region->SetParents (NULL);
      region->RefreshEdges();
    } // end for
  // And sourceregion' parents and children (duplicate's not copy-constr.'d)
  delete oparents;
  delete ochildren;
  BB_orig->SetParents (NULL); //HZ: it is ok, as the function call
                                   // GetParents will compute the pointer list
                                   // if it is NULL.
  BB_orig->SetChildren (NULL); 
    
  return (legoBB *) duplicate;    
}

---