addremove.C

Go to the documentation of this file.

// addremove.C

/*
 * LEGO Object Adding/Removing Functions
 * by Bill Havanki
 *
 * 5/13/97 WAH:  Created file; added RemoveEdge, RemoveMidOp.
 * 7/9/97  WAH:  Added AddEdge, AddMidOp.
 * 7/16/97 WAH:  Added AddLcAttribute, RemoveLcAttribute.
 * 7/18/97 WAH:  Enhanced ", " to work on opEdges too; added AddLiveAttribute,
 *               RemoveLiveAttribute.
 * 7/23/97 WAH:  Added AddFlag, RemoveFlag.
 * 8/1/97  WAH:  Added ClearRegionMarks.
 * 9/2/97  WAH:  Fixed bug in AddPointerAttribute; added edge type parameter
 *               to adding/removing edges.
 * 10/11/97 WAH: Functions return created objects; attribute operand
 *               parentPtr is set.
 * 10/16/97 WAH: Added AddFreqAttribute, RemoveFreqAttribute.
 * 10/29/97 WAH: Fixed minor bug in AddPointerAttribute (oprd->SetParentPtr).
 * 10/31/97 WAH: Fixed finding of available id for new edge in AddEdge;
 *               added choice whether to delete op in RemoveMidOp.
 * 11/3/97 WAH:  Fixed RemoveMidOp to remove op from region.
 * 11/21/97 WAH: Revamped some function calls; changed AddPointerAttribute
 *               to allocate its own lcname (yikes!).
 * 12/8/97 WAH:  Fixed AddMidOp and RemoveMidOp to update opLists.
 * 12/11/97 WAH: Undid 11/21 change to AddPointerAttribute; causes core
 *               dumps (yikes again!); changed AddMidOp to add op to
 *               block before adding edge.
 * 1/13/98 WAH:  Fixed NULL dereferencing in AddPointerAttribute (newattr)
 *               and RemovePointerAttribute (atl).
 * 1/14/98 WAH:  Added AddBBAlongEdge.
 * 1/16/98 WAH:  Fixed RemoveMidOp again (see 11/3/97) to not Detach if
 *               the op is already detached.
 * 1/27/98 WAH:  Updated RemoveEdge to delete edge attributes and RemoveMidOp
 *               to delete op attributes and RemovePointerAttribute to
 *               delete attribute operands.
 * 1/29/98 WAH:  Added AddToList and RemoveFromList.
 * 1/30/98 WAH:  Replaced some code with function calls.
 * 4/9/98 WAH:   Enhanced RemoveFromList for opLists to key on weight as well.
 * 4/22/98 WAH:  Updated legoOprd::parentPtr.
 * Thu Aug 27 09:55:16 EDT 1998 LSY:    Add SplitParentBlockBeforeOp and RemoveLastOp 
 * 11/2/98 MDJ:  Fixed bug in ClearMarks, previously did not work for treegions
 * 11/11/98 MDJ: Fixed bug in RemoveMidOp(), now allListPtr for the proc is 
 *               updated correctly in the end case
 */

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

//#define ADDREMOVE_DEBUG
#ifdef ADDREMOVE_DEBUG
#define dprintf(s) fprintf s
#define OUTF stderr
#else
#define dprintf(s)
#endif // ADDREMOVE_DEBUG

// Object types for add/remove functions.
#define ADDREMOVE_REGION (0)
#define ADDREMOVE_OP (1)
#define ADDREMOVE_EDGE (2)

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

/*
 * AddToList (all flavors)
 *   list = list on which to work
 *   object = op, edge, or region to add to list
 *   valid = valid bit
 *   weight = profile weight (opList only)
 *   returns: list if not originally NULL, new list otherwise.
 *
 * Adds a reference to object to the end of the list given. The valid bit
 * of the list object is set to valid, and the weight of an opList is set to
 * the weight given. If list is NULL, a new list is created and returned.
 * If list is not NULL, list is returned.
 *
 * If a reference to the object exists, no changes are made, and list is
 * returned.
 */

opList *
AddToList (opList *list, legoOp *object, int valid = 1, double weight = 0.0)
{
  opList *lprev, *l, *add;

  // Try to find duplicate.
  for (lprev = NULL, l = list; l != NULL;
       lprev = l, l = l->GetNextListPtr())
    {
      if (l->GetOpPtr() == object) return list;
    } // end for

  add = new opList;
  if (lprev != NULL)
    lprev->SetNextListPtr (add);
  else
    list = add;

  add->SetOpPtr (object);
  add->SetOpId (object->GetOpId());
  add->SetValid (valid);
  add->SetWeight (weight);

  return list;
} // end AddToList (opList)

edgeList *
AddToList (edgeList *list, opEdges *object, int valid = 1)
{
  edgeList *lprev, *l, *add;

  // Try to find duplicate.
  for (lprev = NULL, l = list; l != NULL;
       lprev = l, l = l->GetNextListPtr())
    {
      if (l->GetEdgePtr() == object) return list;
    } // end for

  add = new edgeList;
  if (lprev != NULL)
    lprev->SetNextListPtr (add);
  else
    list = add;

  add->SetEdgePtr (object);
  add->SetEdgeId (object->GetEdgeId());
  add->SetValid (valid);

  return list;
} // end AddToList (edgeList)

regionList *
AddToList (regionList *list, legoRegion *object, int valid = 1)
{
  regionList *lprev, *l, *add;

  // Try to find duplicate.
  for (lprev = NULL, l = list; l != NULL;
       lprev = l, l = l->GetNextListPtr())
    {
      if (l->GetRegionPtr() == object) return list;
    } // end for

  add = new regionList;
  if (lprev != NULL)
    lprev->SetNextListPtr (add);
  else
    list = add;

  add->SetRegionPtr (object);
  add->SetValid (valid);

  return list;
} // end AddToList (regionList)

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

/*
 * RemoveFromList (all flavors)
 *   list = list on which to work
 *   object = op, edge, or region to remove list
 *   weight = profile weight (opList only)
 *   returns: new list
 *
 * Removes a reference to object from the the list given.
 * If list is NULL, no actions are taken and NULL is returned.
 * If list is not NULL, the reference is removed and the new list is
 *   returned;
 * if the only reference in list is to object, it is removed and NULL is
 *   returned instead.
 *
 * If no reference to the object exists, no changes are made, and list is
 * returned.
 */

opList *
RemoveFromList (opList *list, legoOp *object, double weight = -1.0)
{
  opList *l, *lprev, *remove;

  if (list == NULL) return NULL;

  for (lprev = NULL, l = list; l != NULL;
       lprev = l, l = l->GetNextListPtr())
    {
      if (weight != -1.0 && l->GetWeight() != weight) continue;
      if (l->GetOpPtr() == object) break;
    } // end for

  if (l == NULL) return list;

  if (lprev != NULL)
    {
      lprev->SetNextListPtr (l->GetNextListPtr());
      remove = list;
    } // end if
  else
    remove = l->GetNextListPtr();

  l->SetNextListPtr (NULL);
  delete l;

  return remove;
} // end RemoveFromList (opList)

edgeList *
RemoveFromList (edgeList *list, opEdges *object)
{
  edgeList *l, *lprev, *remove;

  if (list == NULL) return NULL;

  for (lprev = NULL, l = list; l->GetEdgePtr() != object && l != NULL;
       lprev = l, l = l->GetNextListPtr()) ;

  if (l == NULL) return list;

  if (lprev != NULL)
    {
      lprev->SetNextListPtr (l->GetNextListPtr());
      remove = list;
    } // end if
  else
    remove = l->GetNextListPtr();

  l->SetNextListPtr (NULL);
  delete l;

  return remove;
} // end RemoveFromList (edgeList)

regionList *
RemoveFromList (regionList *list, legoRegion *object)
{
  regionList *l, *lprev, *remove;

  if (list == NULL) return NULL;

  for (lprev = NULL, l = list; l->GetRegionPtr() != object && l != NULL;
       lprev = l, l = l->GetNextListPtr()) ;

  if (l == NULL) return list;

  if (lprev != NULL)
    {
      lprev->SetNextListPtr (l->GetNextListPtr());
      remove = list;
    } // end if
  else
    remove = l->GetNextListPtr();

  l->SetNextListPtr (NULL);
  delete l;

  return remove;
} // end RemoveFromList (regionList)

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

/*
 * AddEdge
 *   fromop = op at tail of edge
 *   toop = op at head of edge
 *   et = type of edge to add
 *   srcPort = port of source op's operand
 *   destPort = port of destination op's operand
 *   returns: new opEdges, or NULL if failure
 *
 * Inserts an edge into the edge dictionary of proc going from op fromop
 * to op toop.
 */
opEdges *
AddEdge (legoOp *fromop, legoOp *toop, enum edgeTypes et,
         int srcPort = 0, int destPort = 0)
{
  legoProc *proc;
  opEdges *edgeprev, *edge;
  attrs *attr;
  int maxedgeid = -1;

  proc = (legoProc *) FindParentRegionType (RT_PROC, fromop);
  if (proc == NULL)
    {
      LegoNonFatal ("AddEdge", "Couldn't find proc of op %d.",
                    fromop->GetOpId());
      return NULL;
    } // end if

  // Look for edge already in dictionary.
  for (edgeprev = NULL, edge = proc->GetEdgeDictionary();
       edge != NULL;
       edgeprev = edge, edge = edge->GetNextOpEdgePtr())
    if (edge->GetFromOpPtr() == fromop &&
        edge->GetToOpPtr() == toop &&
        edge->GetEdgeType() == et &&
        edge->GetSrcPort() == srcPort &&
        edge->GetDestPort() == destPort)
      return NULL;

  maxedgeid = FindMaxEdgeAttrId (proc);

  edge = new opEdges();
  edge->SetEdgeId (maxedgeid + 1);
  edge->SetFromOpId (fromop->GetOpId());
  edge->SetFromOpPtr (fromop);
  edge->SetSrcPort (srcPort);
  edge->SetToOpId (toop->GetOpId());
  edge->SetToOpPtr (toop);
  edge->SetDestPort (destPort);
  edge->SetEdgeStatus (STATUS_CERTAIN);
  edge->SetEdgeLat (1);
  edge->SetEdgeType (et);
  edge->SetNextOpEdgePtr(NULL);
  switch (et)
    {
    case ET_CNTL:
      edge->SetSrcPortType (PT_CTL);
      edge->SetDestPortType (PT_CTL);
      break;
    case ET_REGFLOW:
      edge->SetSrcPortType (PT_DEST);
      edge->SetDestPortType (PT_SRC);
      break;
    case ET_REGANTI:
      edge->SetSrcPortType (PT_SRC);
      edge->SetDestPortType (PT_DEST);
      break;
    case ET_REGOUT:
      edge->SetSrcPortType (PT_DEST);
      edge->SetDestPortType (PT_DEST);
      break;
    case ET_MEM:
      edge->SetSrcPortType (PT_MEM);
      edge->SetDestPortType (PT_MEM);
      break;
    default:
      break;
    } // end switch
  
  if (edgeprev != NULL)
    edgeprev->SetNextOpEdgePtr (edge);
  else
    proc->SetEdgeDictionary (edge);

  return edge;
} // end AddEdge

opEdges *
AddEdge (legoOp *fromop, legoOp *toop, legoProc *proc, enum edgeTypes et,
         int srcPort = 0, int destPort = 0)
{
  LegoNonFatal ("AddEdge", "This is a deprecated version of this function.\n"
                "Remove the legoProc * parameter from the call.");

  return AddEdge (fromop, toop, et, srcPort, destPort);
} // end AddEdge

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

/*
 * AddMidOp
 *   midop = op to be added
 *   beforeop = op before where midop should be added
 *
 * Inserts midop into a block just after beforeop while properly updating
 * all links and whatnot.
 */
void
AddMidOp (legoOp *midop, legoOp *beforeop)
{
  legoRegion *region;
  legoProc *proc;
  opEdges *edge;
  legoOp *afterop;
  opList *oplscan;

  if (midop == NULL || beforeop == NULL)
    {
      LegoNonFatal ("AddMidOp", "Passed NULL argument.");
      return;
    } // end if

  proc = (legoProc *) FindParentRegionType (RT_PROC, beforeop);
  if (proc == NULL)
    {
      LegoNonFatal ("AddMidOp", "Couldn't find proc of op %d.",
                    beforeop->GetOpId());
      return;
    } // end if

  afterop = beforeop->GetNextLink();
  if (afterop == NULL)
    {
      LegoNonFatal ("AddMidOp", "Couldn't find op after %d.",
                    beforeop->GetOpId());
      return;
    } // end if

  // Find edge from beforeop to afterop.
  edge = FindControlEdge (beforeop, afterop);
  if (edge == NULL)
    {
      LegoNonFatal ("AddMidOp", "Couldn't find edge from beforeop to "
                    "afterop.");
      return;
    }

  // Point edge to midop.
  edge->SetToOpPtr (midop);
  edge->SetToOpId (midop->GetOpId());
  beforeop->SetNextLink (midop);
  midop->SetPrevLink (beforeop);

  // Insert midop into block and add to proc list.
  region = (legoRegion *) beforeop->GetParentBlockPtr();
  region->AddItem (midop);
  midop->SetParentBlockPtr (region);
  midop->SetListOpPtr (proc->GetListOpPtr());
  proc->SetListOpPtr (midop);

  // Add new edge from midop to afterop.
  AddEdge (midop, afterop, ET_CNTL);
  midop->SetNextLink (afterop);
  afterop->SetPrevLink (midop);

  // Change beforeop's reference to afterop to point to midop instead.
  for (oplscan = beforeop->GetOutListPtr();
       oplscan != NULL;
       oplscan = oplscan->GetNextListPtr())
    {
      if (oplscan->GetOpId() == afterop->GetOpId())
        {
          oplscan->SetOpPtr (midop);
          oplscan->SetOpId (midop->GetOpId());
          break;
        } // end if
    } // end for

  return;
} // end AddMidOp

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

/*
 * RemoveEdge
 *   fromopid = id of op at tail of edge
 *   toopid = id of op at head of edge
 *   proc = proc whose dictionary contains the edge
 *   et = type of edge to remove
 *   srcPort = port of source op's operand
 *   destPort = port of destination op's operand
 *   returns: 1 if edge removed, 0 if no match found
 *
 * Searches the edge dictionary of proc and removes the edge going from
 * op fromopid to op toopid.
 */
int
RemoveEdge (int fromopid, int toopid, legoProc *proc, enum edgeTypes et,
            int srcPort = EDGEPORT_DONTCARE, int destPort = EDGEPORT_DONTCARE)
{
  opEdges *edgeprev, *edge;
  int retval = 0;

  for (edgeprev = NULL, edge = proc->GetEdgeDictionary();
       edge != NULL;
       edgeprev = edge, edge = edge->GetNextOpEdgePtr())
    {
      if (edge->GetFromOpId() != fromopid || edge->GetToOpId() != toopid)
        continue;  // different ops
      if (srcPort > EDGEPORT_DONTCARE && edge->GetSrcPort() != srcPort)
        continue;  // src ports don't match
      if (destPort > EDGEPORT_DONTCARE && edge->GetDestPort() != destPort)
        continue;  // dest ports don't match

      if (edgeprev != NULL)
        edgeprev->SetNextOpEdgePtr (edge->GetNextOpEdgePtr());
      else
        proc->SetEdgeDictionary (edge->GetNextOpEdgePtr());
      edge->SetNextOpEdgePtr (NULL);
      delete edge;
      retval = 1; break;
    } // end for

  return retval;
} // end RemoveEdge (int, int, ...)

int
RemoveEdge (legoOp *fromop, legoOp *toop, enum edgeTypes et,
            int srcPort = EDGEPORT_DONTCARE, int destPort = EDGEPORT_DONTCARE)
{
  legoProc *proc = (legoProc *) FindParentRegionType (RT_PROC, fromop);
  if (proc == NULL)
    {
      LegoNonFatal ("RemoveEdge", "Couldn't find proc of op %d.",
                    fromop->GetOpId());
      return 0;
    } // end if

  return RemoveEdge (fromop->GetOpId(), toop->GetOpId(), proc, et, srcPort,
                     destPort);
} // end RemoveEdge (legoOp *, legoOp *, ...)

int
RemoveEdge (legoOp *fromop, legoOp *toop, legoProc *proc, enum edgeTypes et,
            int srcPort = EDGEPORT_DONTCARE, int destPort = EDGEPORT_DONTCARE)
{
  //  LegoNonFatal ("RemoveEdge", "This is a deprecated version of this "
  //            "function.\nRemove the legoProc * parameter from the call.");

  return RemoveEdge (fromop, toop, et, srcPort, destPort);
}

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

/*
 * RemoveMidOp
 *   midop = op to be removed
 *   destroy = whether to delete op
 *
 * Removes midop from existence while properly updating all links
 * and whatnot.
 */
void
RemoveMidOp (legoOp *midop, int destroy = 0)
{
  legoProc *proc;
  legoOp *listop, *listopprev;
  opEdges *edgeprev, *edge;
  opList *oplscan;
  legoRegion *block;
  unsigned loc;

  proc = (legoProc *) FindParentRegionType (RT_PROC, midop);
  if (proc == NULL)
    {
      LegoNonFatal ("RemoveMidOp", "Couldn't find proc of op %d.",
                    midop->GetOpId());
      return;
    } // end if

  if (midop->GetPrevLink() == NULL || midop->GetNextLink() == NULL)
    {
      LegoNonFatal ("RemoveMidOp", "Op %d not in middle.", midop->GetOpId());
      return;
    } // end if

  // Remove edge leading out, point edge leading in to next op.
  RemoveEdge (midop->GetOpId(), midop->GetNextLink()->GetOpId(), proc,
              ET_CNTL);

  for (edgeprev = NULL, edge = proc->GetEdgeDictionary();
       edge != NULL &&
         (edge->GetFromOpId() != midop->GetPrevLink()->GetOpId() ||
          edge->GetToOpId() != midop->GetOpId());
       edgeprev = edge, edge = edge->GetNextOpEdgePtr())
    /* do nothing */;
  if (edge != NULL)
    {
      edge->SetToOpPtr (midop->GetNextLink());
      edge->SetToOpId (midop->GetNextLink()->GetOpId());
    } // end if

  // Change previous op's reference to currentop to point to the next op
  // instead (does stuff for C_MERGE only).
  for (oplscan = midop->GetPrevLink()->GetOutListPtr();
       oplscan != NULL;
       oplscan = oplscan->GetNextListPtr())
    {
      if (oplscan->GetOpId() == midop->GetOpId())
        {
          oplscan->SetOpPtr (midop->GetNextLink());
          oplscan->SetOpId (midop->GetNextLink()->GetOpId());
          break;
        } // end if
    } // end for
  
  // Remove from op chains.
  midop->GetPrevLink()->SetNextLink (midop->GetNextLink());
  midop->GetNextLink()->SetPrevLink (midop->GetPrevLink());
  midop->SetPrevLink (NULL);
  midop->SetNextLink (NULL);

  // mdj 11/11/98 - fixed bug, now when proc->GetListOpPtr() == midop, 
  // lists are updated correctly
  if ((listop = proc->GetListOpPtr()) != midop) {
    for (;
         listop != NULL && listop->GetListOpPtr() != midop;
         listop = listop->GetListOpPtr())
      /* do nothing */;
  }
  if (listop != NULL)
    {
      if (proc->GetListOpPtr() != midop)
        listop->SetListOpPtr (midop->GetListOpPtr());
      else
        proc->SetListOpPtr (midop->GetListOpPtr());
    } // end if
  midop->SetListOpPtr (NULL);

  // Detach from region.
  block = (legoRegion *) midop->GetParentBlockPtr();
  loc = block->Search (midop);
  if (loc != MAX_UNSIGNED)
    block->Detach (loc);
  
  if (destroy)  // blow away attributes, then op
    {
      attrList *atl;
      attrs *a;
      enum attrTypes atype;

      RemoveLiveAttribute (midop, proc);  // kill live attribute right off

      atl = midop->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(), midop, proc);

          atl = midop->GetOpAttrListPtr();  // reset for next scan
        } // end while
      delete midop;
    } // end if
  return;
} // end RemoveMidOp

void
RemoveMidOp (legoOp *midop, legoProc *proc, int destroy = 0)
{
  //  LegoNonFatal ("RemoveMidOp", "This is a deprecated version of this "
  //            "function.\nRemove the legoProc * parameter from the call.");

  RemoveMidOp (midop, destroy);
}

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

/*
 * RemoveFinalOp
 *   midop = op to be removed
 *   destroy = whether to delete op
 *
 * Removes midop from existence while properly updating all links
 * and whatnot.
 */
void
RemoveFinalOp (legoOp *finalop, int destroy = 0)
{
  legoProc *proc;
  legoOp *listop, *listopprev;
  opEdges *edgeprev, *edge;
  opList *oplscan;
  legoRegion *block;
  unsigned loc;

  proc = (legoProc *) FindParentRegionType (RT_PROC, finalop);
  if (proc == NULL)
    {
      LegoNonFatal ("RemoveFinalOp", "Couldn't find proc of op %d.",
                    finalop->GetOpId());
      return;
    } // end if

  if (finalop->GetPrevLink() == NULL || finalop->GetNextLink() != NULL)
    {
      LegoNonFatal ("RemoveFinalOp", "Op %d not the final op in block.", finalop->GetOpId());
      return;
    } // end if

  // Remove the edge between the previous op and finalop 
  RemoveEdge (finalop->GetPrevLink()->GetOpId(), finalop->GetOpId(), proc,
              ET_CNTL);
  
  // Remove from op chains.
  finalop->GetPrevLink()->SetNextLink (NULL);
  finalop->SetPrevLink (NULL);
  finalop->SetNextLink (NULL);

  // mdj 11/11/98 - fixed bug, now when proc->GetListOpPtr() == finalop, 
  // lists are updated correctly
  if ((listop = proc->GetListOpPtr()) != finalop) {
    for (;
         listop != NULL && listop->GetListOpPtr() != finalop;
         listop = listop->GetListOpPtr())
      /* do nothing */;
  }
  if (listop != NULL)
    {
      if (proc->GetListOpPtr() != finalop)
        listop->SetListOpPtr (finalop->GetListOpPtr());
      else
        proc->SetListOpPtr (finalop->GetListOpPtr());
    } // end if
  finalop->SetListOpPtr (NULL);

  // Detach from region.
  block = (legoRegion *) finalop->GetParentBlockPtr();
  loc = block->Search (finalop);
  if (loc != MAX_UNSIGNED)
    block->Detach (loc);
  
  if (destroy)  // blow away attributes, then op
    {
      attrList *atl;
      attrs *a;
      enum attrTypes atype;

      RemoveLiveAttribute (finalop, proc);  // kill live attribute right off

      atl = finalop->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(), finalop, proc);

          atl = finalop->GetOpAttrListPtr();  // reset for next scan
        } // end while
      delete finalop;
    } // end if
  return;
} // end RemoveFinalOp

/*
 * RemoveFirstOp
 *   firstop = op to be removed
 *   destroy = whether to delete op
 *
 * Removes firstop from existence while properly updating all links
 * and whatnot.
 */
void
RemoveFirstOp (legoOp *firstop, int destroy = 0)
{
  legoProc *proc;
  legoOp *listop, *listopprev;
  opEdges *edgeprev, *edge;
  opList *oplscan;
  legoRegion *block;
  unsigned loc;

  proc = (legoProc *) FindParentRegionType (RT_PROC, firstop);
  if (proc == NULL)
    {
      LegoNonFatal ("RemoveFirstOp", "Couldn't find proc of op %d.",
                    firstop->GetOpId());
      return;
    } // end if

  if (firstop->GetPrevLink() != NULL || firstop->GetNextLink() == NULL)
    {
      LegoNonFatal ("RemoveFirstOp", "Op %d not the first op in block.", firstop->GetOpId());
      return;
    } // end if

  // Remove edge leading out.
  RemoveEdge (firstop->GetOpId(), firstop->GetNextLink()->GetOpId(), proc,
              ET_CNTL);

  // Remove from op chains.
  firstop->GetNextLink()->SetPrevLink (NULL);
  firstop->SetPrevLink (NULL);
  firstop->SetNextLink (NULL);

  // mdj 11/11/98 - fixed bug, now when proc->GetListOpPtr() == firstop, 
  // lists are updated correctly
  if ((listop = proc->GetListOpPtr()) != firstop) {
    for (;
         listop != NULL && listop->GetListOpPtr() != firstop;
         listop = listop->GetListOpPtr())
      /* do nothing */;
  }
  if (listop != NULL)
    {
      if (proc->GetListOpPtr() != firstop)
        listop->SetListOpPtr (firstop->GetListOpPtr());
      else
        proc->SetListOpPtr (firstop->GetListOpPtr());
    } // end if
  firstop->SetListOpPtr (NULL);

  // Detach from region.
  block = (legoRegion *) firstop->GetParentBlockPtr();
  loc = block->Search (firstop);
  if (loc != MAX_UNSIGNED)
    block->Detach (loc);
  
  if (destroy)  // blow away attributes, then op
    {
      attrList *atl;
      attrs *a;
      enum attrTypes atype;

      RemoveLiveAttribute (firstop, proc);  // kill live attribute right off

      atl = firstop->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(), firstop, proc);

          atl = firstop->GetOpAttrListPtr();  // reset for next scan
        } // end while
      delete firstop;
    } // end if
  return;
} // end RemoveFirstOp

/*
 * RemoveVeryLastOp
 *   verylastop = op to be removed
 *   destroy = whether to delete op
 *
 * Removes verylastop from existence while properly updating all links
 * and whatnot.
 */
void
RemoveVeryLastOp (legoOp *verylastop, int destroy = 0)
{
  legoProc *proc;
  legoOp *listop, *listopprev;
  opEdges *edgeprev, *edge;
  opList *oplscan;
  legoRegion *block;
  unsigned loc;

  proc = (legoProc *) FindParentRegionType (RT_PROC, verylastop);
  if (proc == NULL)
    {
      LegoNonFatal ("RemoveVeryLastOp", "Couldn't find proc of op %d.",
                    verylastop->GetOpId());
      return;
    } // end if

  if (verylastop->GetPrevLink() != NULL || verylastop->GetNextLink() != NULL)
    {
      LegoNonFatal ("RemoveVeryLastOp", "Op %d not the very last op in block.", verylastop->GetOpId());
      return;
    } // end if

  // Remove from op chains.
  verylastop->SetPrevLink (NULL);
  verylastop->SetNextLink (NULL);

  // mdj 11/11/98 - fixed bug, now when proc->GetListOpPtr() == verylastop, 
  // lists are updated correctly
  if ((listop = proc->GetListOpPtr()) != verylastop) {
    for (;
         listop != NULL && listop->GetListOpPtr() != verylastop;
         listop = listop->GetListOpPtr())
      /* do nothing */;
  }
  if (listop != NULL)
    {
      if (proc->GetListOpPtr() != verylastop)
        listop->SetListOpPtr (verylastop->GetListOpPtr());
      else
        proc->SetListOpPtr (verylastop->GetListOpPtr());
    } // end if
  verylastop->SetListOpPtr (NULL);

  // Detach from region.
  block = (legoRegion *) verylastop->GetParentBlockPtr();
  loc = block->Search (verylastop);
  if (loc != MAX_UNSIGNED)
    block->Detach (loc);
  
  if (destroy)  // blow away attributes, then op
    {
      attrList *atl;
      attrs *a;
      enum attrTypes atype;

      RemoveLiveAttribute (verylastop, proc);  // 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, proc);

          atl = verylastop->GetOpAttrListPtr();  // reset for next scan
        } // end while
      delete verylastop;
    } // end if
  return;
} // end RemoveVeryLastOp

/*
 * RemoveLastOp  
 *   last_op = op to be removed
 *   destroy = whether to delete op
 *
 * Removes last from existence
 */
void RemoveLastOp(legoOp *last_op,int destroy = 0)
{
   legoOp       *prev_op        = NULL;
   legoOp       *list_op        = NULL;
   legoProc     *proc_ptr       = NULL;
   opEdges      *op_edge        = NULL;


   if(!last_op){
        LegoNonFatal ("RemoveLastOp", "Empty argument passed");
        return;
   }
   if(!(prev_op = last_op->GetPrevLink())){
        LegoNonFatal ("RemoveLastOp", "Empty GetPrevLink");
        return;
   }
   if(!(proc_ptr = (legoProc *) FindParentRegionType (RT_PROC, last_op))){
        LegoNonFatal ("RemoveLastOp", "Couldn't find proc of op %d.",last_op->GetOpId());
        return;
   }
   //
   // Step 1:  Search the opEdge  from prev_op to last_op
   //
   int          prev_op_id      = prev_op->GetOpId();
   int          last_op_id      = last_op->GetOpId();
   opEdges      *edge_dict      = proc_ptr->GetEdgeDictionary();
   opEdges      *prev_op_edge   = NULL;

   for(op_edge=edge_dict;op_edge;op_edge=op_edge->GetNextOpEdgePtr()){
        if(op_edge->GetFromOpId()==prev_op_id && op_edge->GetToOpId()==last_op_id)      break;
        prev_op_edge    = op_edge;
   }
   //
   // Step 2: set prev_op_edge to next (delete this op_edge)
   //
   assert(op_edge!=NULL);
   prev_op_edge->SetNextOpEdgePtr(op_edge->GetNextOpEdgePtr());
   //
   // set link of prev_op
   //
   prev_op->SetNextLink(NULL);

   for(list_op=proc_ptr->GetListOpPtr();list_op!=NULL && list_op->GetListOpPtr()!=last_op;list_op=list_op->GetListOpPtr());
   if(list_op){
        if(list_op!=proc_ptr->GetListOpPtr())   list_op->SetListOpPtr(last_op->GetListOpPtr());
        else                                    proc_ptr->SetListOpPtr(last_op->GetListOpPtr());
   }
   last_op->SetListOpPtr(NULL);
   //
   // Detach from region
   // if not already detached
   //
   legoRegion   *bb     = (legoRegion *)last_op->GetParentBlockPtr();
   unsigned     loc     = bb->Search(last_op);
   if(loc != MAX_UNSIGNED)      bb->Detach(loc);

   // If needed then destroy the op
   // blow away attributes, then op
   if (destroy){
        attrList        *atl;
        attrs           *a;
        enum attrTypes  atype;

        RemoveLiveAttribute (last_op, proc_ptr);  // kill live attribute right off
        atl     = last_op->GetOpAttrListPtr();
        while(atl){
                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(), last_op, proc_ptr);
                atl     = last_op->GetOpAttrListPtr();  // reset for next scan
        } // end while
        delete last_op;
   }
}

void RemoveLastOp(legoOp *last_op, legoProc *proc, int destroy = 0)
{
   RemoveLastOp(last_op,destroy); 
} 

/*
 * AddBBAlongEdge
 *   edge = edge on which new block is placed
 *   proc = containing proc
 *   returns: pointer to new legoBB, or NULL if failure
 *
 * Creates a new empty basic block along the edge given, such that the
 * block now exists directly between the region at the tail of the edge
 * and the one at the head. The block is added to the parent region of
 * the destination block, just before it in the set.
 */
legoBB *
AddBBAlongEdge (opEdges *edge, legoProc *proc)
{
  opEdges *newedge;
  legoOp *fromop, *toop, *alllist, *top, *dummy_br;
  legoRegion *fromregion, *toregion, *parentregion, *r;
  legoBB *newblock;
  legoOprd *oprd;
  opList *opl;
  int id;
  unsigned loc;
  double fromweight;

  if (edge == NULL || proc == NULL)
    {
      LegoNonFatal ("AddBBAlongEdge", "Passed NULL parameter.");
      return NULL;
    } // end if

  fromop = edge->GetFromOpPtr();
  toop = edge->GetToOpPtr();
  if (fromop == NULL || toop == NULL)
    {
      LegoFatal ("AddBBAlongEdge", "Edge source is %p, destination %p - "
                 "one of them is NULL.", fromop, toop);
    } // end if

  fromregion = (legoRegion *) fromop->GetParentBlockPtr();
  toregion = (legoRegion *) toop->GetParentBlockPtr();
  if (fromregion == NULL || toregion == NULL)
    {
      LegoFatal ("AddBBAlongEdge", "Parent of op %p is %p; parent of %p "
                 "is %p - one of the parents is NULL.", fromop, fromregion,
                 toop, toregion);
    } // end if

  parentregion = toregion->GetParentPtr();
  if (parentregion == NULL)
    {
      LegoFatal ("AddBBAlongEdge", "Parent of %p region is NULL.",
                 toregion);
    } // end if

  dprintf ((OUTF, "AddBBAlongEdge: insering block along edge %d into region "
            "%d.\n", edge->GetEdgeId(), parentregion->GetRegionId()));

  // Make a new basic block.
  id = proc->FindMaxRegionId()->GetRegionId();
  newblock = new legoBB (id + 1);
  loc = parentregion->Search (toregion);
  if (loc != MAX_UNSIGNED)
    parentregion->Insert (newblock, loc);
  else
    parentregion->AddItem (newblock);
  newblock->SetParentPtr (parentregion);

  // Put in C_MERGE and DUMMY_BR ops.
  for (alllist = proc->GetListOpPtr(); alllist->GetListOpPtr() != NULL;
       alllist = alllist->GetListOpPtr()) ;
  id = (FindMaxOpId (proc))->GetOpId() + 1;

  // op id (C_MERGE [u<>] [u<>])
  top = new legoOp (id++);
  top->SetOpcode (C_MERGE);
  top->SetParentBlockPtr (newblock);
  alllist->SetListOpPtr (top);
  alllist = top;

  oprd = new legoOprd;
  oprd->SetOprdType (OT_UNDEFINED);
  oprd->SetParentOpPtr (top);
  top->SetSrcOprdPtr (oprd);
  oprd = new legoOprd;
  oprd->SetOprdType (OT_UNDEFINED);
  oprd->SetParentOpPtr (top);
  top->SetDestOprdPtr (oprd);

  newblock->AddItem(top);
  dprintf ((OUTF, "Added C_MERGE %d to new basic block.\n", top->GetOpId()));

  // op id (DUMMY_BR [u<>] [u<>])
  dummy_br = new legoOp (id++);
  dummy_br->SetOpcode (DUMMY_BR);
  dummy_br->SetParentBlockPtr (newblock);
  alllist->SetListOpPtr (dummy_br);
  alllist = dummy_br;

  oprd = new legoOprd;
  oprd->SetOprdType (OT_UNDEFINED);
  oprd->SetParentOpPtr (dummy_br);
  dummy_br->SetSrcOprdPtr (oprd);
  oprd = new legoOprd;
  oprd->SetOprdType (OT_UNDEFINED);
  oprd->SetParentOpPtr (dummy_br);
  dummy_br->SetDestOprdPtr (oprd);

  top->SetNextLink (dummy_br);
  dummy_br->SetPrevLink (top);
  newblock->AddItem (dummy_br);
  dprintf ((OUTF, "Added DUMMY_BR %d to new basic block.\n",
            dummy_br->GetOpId()));

  // Add the edge between them.
  newedge = AddEdge (top, dummy_br, ET_CNTL);
  dprintf ((OUTF, "Added edge %d between new ops.\n", newedge->GetEdgeId()));

  // Now, take the edge that points to toregion and point it to 
  // the new block instead.
  RedirectEdge (edge, EDGE_TO, top);
  dprintf ((OUTF, "Redirected edge %d to point to op %d.\n",
            edge->GetEdgeId(), top->GetOpId()));

  // Set the new block's weight to the weight of the incoming edge.
  fromweight = (double) FindEdgeFrequency (edge);
  newblock->SetWeight (fromweight);

  // Next, add an edge between the newblock and toregion, and update the
  // outLists and inLists.
  newedge = AddEdge (dummy_br, toop, ET_CNTL);
  AddFreqAttribute ((int) fromweight, 0, newedge);
  dprintf ((OUTF, "Added edge %d from new basic block to following block.\n",
            newedge->GetEdgeId()));

  opl = new opList;
  dummy_br->SetOutListPtr (opl);
  opl->SetOpPtr (toop);
  opl->SetOpId (toop->GetOpId());
  opl->SetValid (1);
  opl->SetWeight (fromweight);
  dprintf ((OUTF, "Added ref to op %d to dummy_br %d.\n", toop->GetOpId(),
            dummy_br->GetOpId()));

  // Add ref to dummy_br to inList of to block.
  opl = AddToList (toop->GetInListPtr(), dummy_br, 1, fromweight);
  toop->SetInListPtr (opl);
  dprintf ((OUTF, "Added ref the other way.\n"));

  // Before we exit, refresh the following regions:
  // * newblock
  // * toregion and all its parents (same as newblock's)
  // * fromregion and all its parents

  ClearMarks (RM_GENERAL, proc);

  dprintf ((OUTF, "Refreshing new block...\n"));
  newblock->RefreshOpsAndEdges();
  newblock->Mark (RM_GENERAL);

  dprintf ((OUTF, "Refreshing toregion and parents...\n"));
  toregion->RefreshEdges();  // ops didn't change
  for (r = toregion->GetParentPtr(); r->GetRegionType() != RT_MODULE;
       r = r->GetParentPtr())
    {
      r->RefreshOpsAndEdges();  // ops may have changed, edges did
      r->Mark (RM_GENERAL);
    } // end for

  dprintf ((OUTF, "Refreshing fromregion and parents...\n"));
  fromregion->RefreshEdges();  // ops didn't change
  for (r = fromregion->GetParentPtr(); r->GetRegionType() != RT_MODULE;
       r = r->GetParentPtr())
    {
      if (r->IsMarked (RM_GENERAL)) break;  // hit common parent, stop!
      r->RefreshEdges();  // ops didn't change
      r->Mark (RM_GENERAL);
    } // end for

  dprintf ((OUTF, "Done creating new block.\n"));
  return newblock;
} // end AddBBAlongEdge


/*
 * SplitParentBlockBeforeOp 
 * op_ptr - split before this instruction 
 *
 * Splits the parent block of op_ptr right before it, 
 * and returns ptr to the new block. 
 * NOT TESTED FOR HB,SB 
 */ 
legoRegion *SplitParentBlockBeforeOp(legoOp *op_ptr)
{
   legoProc     *proc_ptr               = NULL;
   legoOp       *branch_from_region     = NULL;
   legoRegion   *from_region            = NULL;
   legoRegion   *new_region             = NULL;
   legoRegion   *parent_region          = NULL;
   int          index                   = 0;
   int          this_edge_weight        = 0;    // assume edge freq.
   int          max_op_id               = 0;

   if(!op_ptr){
        LegoNonFatal ("SplitParentBlockBeforeOp", "Empty argument passed");
        return  NULL;
   }
   if(!(proc_ptr = (legoProc *) FindParentRegionType (RT_PROC, op_ptr))){
        LegoNonFatal ("SplitParentBlockBeforeOp", "Couldn't find proc of op %d.",op_ptr->GetOpId());
        return NULL;
   }
   if(!(from_region = (legoRegion *)op_ptr->GetParentBlockPtr())){
        LegoNonFatal ("SplitParentBlockBeforeOp", "Couldn't find Parent block of op %d.",op_ptr->GetOpId());
        return NULL;
   }
   if(!(branch_from_region = op_ptr->GetPrevLink())){
        LegoNonFatal ("SplitParentBlockBeforeOp", "Empty GetPrevLink");
        return NULL;
   }
   //
   // Create new region (BB)
   //
   new_region           = new legoBB((proc_ptr->FindMaxRegionId()->GetRegionId())+1);
   parent_region        = from_region->GetParentPtr();
   this_edge_weight     = (int)from_region->GetWeight();
   max_op_id            = (FindMaxOpId(proc_ptr))->GetOpId()+1;

   for(index=0;index<parent_region->GetCount();index++)
        if(from_region==(legoRegion *)parent_region->GetItem(index))    break;

   if(index < (parent_region->GetCount())-1)    parent_region->Insert(new_region,index+1);
   else                                         parent_region->AddItem(new_region);

   new_region->SetParentPtr(parent_region);
   //
   // Step 1: Put C_MERGE
   //
   legoOp       *alllist,*top,*dummy_br,*pbrr;

   for(alllist=proc_ptr->GetListOpPtr();alllist->GetListOpPtr()!=NULL;alllist=alllist->GetListOpPtr()) ;
   top          = new legoOp (max_op_id++);
   top->SetOpcode (C_MERGE);
   top->SetParentBlockPtr (new_region);
   alllist->SetListOpPtr (top);
   alllist      = top;

   legoOprd     *oprd   = new legoOprd;
   oprd->SetOprdType (OT_UNDEFINED);
   oprd->SetParentOpPtr (top);
   top->SetSrcOprdPtr (oprd);
   oprd = new legoOprd;
   oprd->SetOprdType (OT_UNDEFINED);
   oprd->SetParentOpPtr (top);
   top->SetDestOprdPtr (oprd);
   new_region->AddItem(top);
   //
   // Step 2: Put DUMMY_BR
   //
   dummy_br     = new legoOp (max_op_id++);
   dummy_br->SetOpcode (DUMMY_BR);
   dummy_br->SetParentBlockPtr (new_region);
   alllist->SetListOpPtr (dummy_br);
   alllist      = dummy_br;

   oprd = new legoOprd;
   oprd->SetOprdType (OT_UNDEFINED);
   oprd->SetParentOpPtr (dummy_br);
   dummy_br->SetSrcOprdPtr (oprd);
   oprd = new legoOprd;
   oprd->SetOprdType (OT_UNDEFINED);
   oprd->SetParentOpPtr (dummy_br);
   dummy_br->SetDestOprdPtr (oprd);

   top->SetNextLink (dummy_br);
   dummy_br->SetPrevLink (top);
   new_region->AddItem (dummy_br);

   //
   // Step 3: Add the edge between them.
   //
   opEdges *new_edge = AddEdge (top, dummy_br, ET_CNTL);
   //
   // Step 4: copy op from op_ptr to new_region
   //
   legoOp          *current_op          = top;
   legoOp          *copy_op_ptr         = NULL;
   attrs           *attrdictionary;
   attrs           *attrtail, *atscan;
   attrList        *atlscan;
   int             eaid                 = FindMaxEdgeAttrId(proc_ptr);

   if(!(attrdictionary = proc_ptr->GetAttrDictionary())){
        LegoNonFatal ("SplitParentBlockBeforeOp", "Attribute dictionary is missing.");
        return NULL;
   }
   for (attrtail = attrdictionary; attrtail->GetNextAttrPtr(); attrtail = attrtail->GetNextAttrPtr()) ;    // find the last one

   for(legoOp *my_op=op_ptr;my_op!=NULL;my_op=my_op->GetNextLink()){ 
                copy_op_ptr     = new legoOp(*my_op);
                copy_op_ptr->SetParentBlockPtr(new_region);
                AddMidOp(copy_op_ptr,current_op);
                // copy op attributes
                //
                for (atlscan = copy_op_ptr->GetOpAttrListPtr();atlscan;atlscan = atlscan->GetNextListPtr()){
                        if (atlscan->GetAttrPtr() == NULL)      continue;
                        atscan          = new attrs (*(atlscan->GetAttrPtr()),copy_op_ptr,++eaid);
                        atlscan->SetAttrPtr (atscan);
                        atscan->SetAttrId (eaid);
                        atlscan->SetAttrId (eaid);
                        attrtail->SetNextAttrPtr (atscan);
                        attrtail        = attrtail->GetNextAttrPtr();
                }
                current_op      = copy_op_ptr;
   }
   //
   // Step 5: remove ops in from_region
   //
   legoOp *next_op;
   for(legoOp *my_op = op_ptr;my_op;my_op=next_op){
                if(next_op = my_op->GetNextLink())      RemoveMidOp(my_op,1);
                else                                    RemoveLastOp(my_op,1);
   }
   // record the last branch in new region
   //
   legoOp  *last_branch_new_region = dummy_br->GetPrevLink();
   // 
   // Step 6: remove dummy_br in new_region
   // 
   RemoveLastOp(dummy_br,1);
   //
   // Step 7: set weight in new_region
   //
   new_region->SetWeight(from_region->GetWeight());
   //
   // Step 8: create opList for top in new region
   //
   opList *top_op_list=new opList();
   top->SetInListPtr(top_op_list);
   top_op_list->SetOpPtr(branch_from_region);
   top_op_list->SetOpId(branch_from_region->GetOpId());
   top_op_list->SetValid(1);
   top_op_list->SetWeight(this_edge_weight);
   //
   // Step 9: create entryoplist for new_region
   //
   opList *entry_op_list=new opList();
   entry_op_list->SetOpPtr(top);
   entry_op_list->SetOpId(top->GetOpId());
   entry_op_list->SetValid(1);
   new_region->SetEntryOpsPtr(entry_op_list);
   //
   // Step 10: create exitoplist for new_region
   //
   opList *exit_op_list=new opList();
   exit_op_list->SetOpPtr(last_branch_new_region);
   exit_op_list->SetOpId(last_branch_new_region->GetOpId());
   exit_op_list->SetValid(1);
   new_region->SetExitOpsPtr(exit_op_list);
   //
   // Step 11:  Search the last opEdge in the edge dictionary
   //
   opEdges *last_op_edge;
   opEdges *edge_dict=proc_ptr->GetEdgeDictionary();
   for(last_op_edge=edge_dict;last_op_edge->GetNextOpEdgePtr()!=NULL;last_op_edge=last_op_edge->GetNextOpEdgePtr());
   //
   // Step 12: create new opEdges to connect branch_from_region & top
   //
   opEdges *new_op_edge    = new opEdges();
   new_op_edge->SetEdgeType(ET_CNTL);
   new_op_edge->SetEdgeId(last_op_edge->GetEdgeId()+1);
   new_op_edge->SetFromOpId(branch_from_region->GetOpId());
   new_op_edge->SetToOpId(top->GetOpId());
   new_op_edge->SetFromOpPtr(branch_from_region);
   new_op_edge->SetToOpPtr(top);
   new_op_edge->SetNextOpEdgePtr(NULL);
   new_op_edge->SetSrcPortType(PT_CTL);
   new_op_edge->SetDestPortType(PT_CTL);
   new_op_edge->SetEdgeLat(1);

   last_op_edge->SetNextOpEdgePtr(new_op_edge);
   AddFreqAttribute(this_edge_weight,0,new_op_edge);
   //
   // Step 13: create edgeList to new_op_edge
   //          and SetInEdgePtr in new_region
   //
   edgeList *new_edge_list=new edgeList();
   new_edge_list->SetValid(1);
   new_edge_list->SetEdgePtr(new_op_edge);
   new_edge_list->SetEdgeId(new_op_edge->GetEdgeId());
   new_region->SetInEdgesPtr(new_edge_list);
   //
   // Step 14:  SetOutEdgePtr in new_region
   //           and update all of them accordingly 
   //
   new_region->SetOutEdgesPtr(from_region->GetOutEdgesPtr());

   edgeList     *out_edges_of_original_block    =       new_region->GetOutEdgesPtr();
   opEdges      *current_out_edge               =       NULL;

   while(out_edges_of_original_block){
        if(current_out_edge = out_edges_of_original_block->GetEdgePtr()) 
                current_out_edge->SetFromOpPtr(last_branch_new_region);
        out_edges_of_original_block     = out_edges_of_original_block->GetNextListPtr();
   }
   //
   // Step 15: create edgeList to new_op_edge
   //          and SetOutEdgePtr in from_region
   //
   new_edge_list=new edgeList();
   new_edge_list->SetValid(1);
   new_edge_list->SetEdgePtr(new_op_edge);
   new_edge_list->SetEdgeId(new_op_edge->GetEdgeId());
   from_region->SetOutEdgesPtr(new_edge_list);
   //
   // Step 16: create opList for branch_from_region
   //
   opList *bfr_op_list=new opList();
   branch_from_region->SetOutListPtr(bfr_op_list);
   bfr_op_list->SetOpPtr(top);
   bfr_op_list->SetOpId(top->GetOpId());
   bfr_op_list->SetValid(1);
   bfr_op_list->SetWeight(this_edge_weight);
   //
   // Step 17: create exitoplist for from_region
   //
   exit_op_list=new opList();
   exit_op_list->SetOpPtr(branch_from_region);
   exit_op_list->SetOpId(branch_from_region->GetOpId());
   exit_op_list->SetValid(1);
   from_region->SetExitOpsPtr(exit_op_list);
   //
   // Step 18: return ptr to the new_region
   //
   return new_region;
}

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

static flags *
AddFlag (int flagname, void *object, int objtype)
{
  flags *f;

  if (objtype == ADDREMOVE_REGION)
    f = ((legoRegion *) object)->GetFlagPtr();
  else
    f = ((legoOp *) object)->GetOpFlagPtr();

  for ( ; f != NULL && f->GetNextFlagPtr() != NULL;  // don't step past last!
        f = f->GetNextFlagPtr())
    if (f->GetFlagName() == flagname) return f;
  if (f != NULL && f->GetFlagName() == flagname) return f;  // for last flag

  // Make new flag and attach appropriately.
  if (f == NULL)
    {
      f = new flags;
      if (objtype == ADDREMOVE_REGION)
        ((legoRegion *) object)->SetFlagPtr (f);
      else
        ((legoOp *) object)->SetFlagPtr (f);
    } // end if
  else
    {
      f->SetNextFlagPtr (new flags);
      f = f->GetNextFlagPtr();
    } // end else
  f->SetFlagName (flagname);

  return f;
} // end AddFlag (object)

/*
 * AddFlag
 *   flagname = name of flag to be added
 *   region = region within which flag is added
 *   returns: new flag or existing flag with same name
 *
 * Adds flag with name flagname to region.
 */
flags *
AddFlag (int flagname, legoRegion *region)
{
  return AddFlag (flagname, (void *) region, ADDREMOVE_REGION);
} // end AddFlag (region)

/*
 * AddFlag
 *   flagname = name of flag to be added
 *   op = op for which flag is added
 *   returns: new flag or existing flag with same name
 *
 * Adds flag with name flagname to op.
 */
flags *
AddFlag (int flagname, legoOp *op)
{
  return AddFlag (flagname, (void *) op, ADDREMOVE_OP);
} // end AddFlag (op)

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

static void
RemoveFlag (int flagname, void *object, int objtype)
{
  flags *fprev, *f;

  fprev = NULL;
  if (objtype == ADDREMOVE_REGION)
    f = ((legoRegion *) object)->GetFlagPtr();
  else
    f = ((legoOp *) object)->GetOpFlagPtr();
  if (f == NULL) return;  // no flags

  // Find the flag with the name flagname.
  for ( ; f->GetFlagName() != flagname;
        fprev = f, f = f->GetNextFlagPtr()) /* do nothing */;
  if (f == NULL) return;  // flag not there

  // Remove f from the list of flags.
  if (fprev == NULL)
    {
      if (objtype == ADDREMOVE_REGION)
        ((legoRegion *) object)->SetFlagPtr (f->GetNextFlagPtr());
      else
        ((legoOp *) object)->SetFlagPtr (f->GetNextFlagPtr());
    } // end if
  else
    fprev->SetNextFlagPtr (f->GetNextFlagPtr());
  f->SetNextFlagPtr (NULL);
  delete f;

  return;
} // end RemoveFlag (object)

/*
 * RemoveFlag
 *   flagname = name of flag to be removed
 *   region = region within which flag is removed
 *
 * Removes flag with name flagname from region.
 */
void
RemoveFlag (int flagname, legoRegion *region)
{
  RemoveFlag (flagname, (void *) region, ADDREMOVE_REGION);
} // end RemoveFlag (region)

/*
 * RemoveFlag
 *   flagname = name of flag to be removed
 *   op = op for which flag is removed
 *
 * Removes flag with name flagname from op.
 */
void
RemoveFlag (int flagname, legoOp *op)
{
  RemoveFlag (flagname, (void *) op, ADDREMOVE_OP);
} // end RemoveFlag (op)

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

attrs *
AddPointerAttribute (enum attrTypes atype, char *lcname, legoOprd *oprd,
                     void *object, int objtype, legoProc *proc)
{
  opEdges *edgedictionary;
  attrs *newattr, *attrdictionary;
  attrList *atl;
  int foundit, maxeaid;

  // Get dictionaries and scan for highest id.
  edgedictionary = proc->GetEdgeDictionary();
  if (edgedictionary == NULL)
    {
      LegoNonFatal ("AddPointerAttribute", "Edge dictionary is missing.");
      return NULL;
    } // end if
  attrdictionary = proc->GetAttrDictionary();
  if (attrdictionary == NULL)
    {
      LegoNonFatal ("AddPointerAttribute", "Attribute dictionary is missing.");
      return NULL;
    } // end if
  maxeaid = -1;

  for ( ; edgedictionary != NULL;
        edgedictionary = edgedictionary->GetNextOpEdgePtr())
    if (edgedictionary->GetEdgeId() > maxeaid)
      maxeaid = edgedictionary->GetEdgeId();
  for ( ; attrdictionary->GetNextAttrPtr() != NULL;  // don't step past last!
        attrdictionary = attrdictionary->GetNextAttrPtr())
    if (attrdictionary->GetAttrId() > maxeaid)
      maxeaid = attrdictionary->GetAttrId();
  if (attrdictionary->GetAttrId() > maxeaid)
    maxeaid = attrdictionary->GetAttrId();  // for last attrs in dictionary

  // Find "atype" type attrList of object, or create empty one if absent.
  if (objtype == ADDREMOVE_REGION)
    atl = ((legoRegion *) object)->GetRegionAttrListPtr();
  else if (objtype == ADDREMOVE_OP)
    atl = ((legoOp *) object)->GetOpAttrListPtr();
  else
    atl = ((opEdges *) object)->GetEdgeAttrListPtr();
  for ( ; atl != NULL && atl->GetNextListPtr() != NULL;
        atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == atype) break;
  if (atl == NULL)
    {
      atl = new attrList;
      if (objtype == ADDREMOVE_REGION)
        ((legoRegion *) object)->SetRegionAttrListPtr (atl);
      else if (objtype == ADDREMOVE_OP)
        ((legoOp *) object)->SetOpAttrListPtr (atl);
      else
        ((opEdges *) object)->SetEdgeAttrListPtr (atl);
      atl->SetAttrType (atype);
      atl->SetValid (1);
    } // end if
  else if (atl->GetAttrType() != atype)
    {
      atl->SetNextListPtr (new attrList);
      atl = atl->GetNextListPtr();
      atl->SetAttrType (atype);
      atl->SetValid (1);
    } // end else

  // Search for preexisting "lcname" attribute, or create if missing.
  if (atype == ATTR_LC)
    {
      for (foundit = 0, newattr = atl->GetAttrPtr();
           newattr != NULL && newattr->GetNextLcEntryPtr() != NULL;
           newattr = newattr->GetNextLcEntryPtr())
        if (strcmp (newattr->GetAttrString(), lcname) == 0)
          {
            foundit = 1; break;
          } // end if
      if (newattr != NULL &&
          strcmp (newattr->GetAttrString(), lcname) == 0)  // get last one
        foundit = 1;
    } // end if
  else
    newattr = atl->GetAttrPtr();  // get first attr if not lc(ode)
  if (newattr == NULL)
    {
      newattr = new attrs;
      atl->SetAttrPtr (newattr);
      newattr->SetAttrId (++maxeaid);
      atl->SetAttrId (maxeaid);
      attrdictionary->SetNextAttrPtr (newattr);
      attrdictionary = attrdictionary->GetNextAttrPtr();
    } // end if
  else if (!foundit && atype == ATTR_LC)
    {
      newattr->SetNextLcEntryPtr (new attrs);
      newattr = newattr->GetNextLcEntryPtr();
      //      newattr->SetAttrId (++maxeaid);
      //      attrdictionary->SetNextAttrPtr (newattr);
      //      attrdictionary = attrdictionary->GetNextAttrPtr();
    } // end else

  // Set attribute fields and quit.
  newattr->SetAttrType (atype);  // OK even if already there
  newattr->SetAttrString (lcname); // ditto
  delete newattr->GetAttrOprdPtr();  // OK even if NOT already there
  newattr->SetAttrOprdPtr (oprd);
  if (oprd != NULL)
    {
      oprd->SetParentAttrPtr (newattr);
      if (objtype == ADDREMOVE_OP)
        oprd->SetParentOpPtr ((legoOp *) object);
    } // end if
  return newattr;
} // end AddPointerAttribute

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

/*
 * AddLcAttribute
 *   lcname = name of lc attribute
 *   oprd = new value of attribute
 *   region = region within which attribute is added
 *   proc = proc which contains region
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds lc attribute with name lcname and value oprd to region.
 */
attrs *
AddLcAttribute (char *lcname, legoOprd *oprd, legoRegion *region,
                legoProc *proc)
{
  return AddPointerAttribute (ATTR_LC, lcname, oprd, (void *) region,
                              ADDREMOVE_REGION, proc);
} // end AddLcAttribute (region)

/*
 * AddLcAttribute
 *   lcname = name of lc attribute
 *   oprd = new value of attribute
 *   op = op for which attribute is added
 *   proc = proc which contains op
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds lc attribute with name lcname and value oprd to op.
 */
attrs *
AddLcAttribute (char *lcname, legoOprd *oprd, legoOp *op, legoProc *proc)
{
  return AddPointerAttribute (ATTR_LC, lcname, oprd, (void *) op,
                              ADDREMOVE_OP, proc);
} // end AddLcAttribute (op)

/*
 * AddLcAttribute
 *   lcname = name of lc attribute
 *   oprd = new value of attribute
 *   edge = edge for which attribute is added
 *   proc = proc which contains edge
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds lc attribute with name lcname and value oprd to edge.
 */
attrs *
AddLcAttribute (char *lcname, legoOprd *oprd, opEdges *edge, legoProc *proc)
{
  return AddPointerAttribute (ATTR_LC, lcname, oprd, (void *) edge,
                              ADDREMOVE_EDGE, proc);
} // end AddLcAttribute (edge)


/*
 * AddLiveAttribute
 *   oprd = new value of attribute
 *   region = region within which attribute is added
 *   proc = proc which contains region
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds live attribute with value oprd to region.
 */
attrs *
AddLiveAttribute (legoOprd *oprd, legoRegion *region, legoProc *proc)
{
  return AddPointerAttribute (ATTR_LIVE, NULL, oprd, (void *) region,
                              ADDREMOVE_REGION, proc);
} // end AddLiveAttribute (region)

/*
 * AddLiveAttribute
 *   oprd = new value of attribute
 *   op = op for which attribute is added
 *   proc = proc which contains op
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds live attribute with value oprd to op.
 */
attrs *
AddLiveAttribute (legoOprd *oprd, legoOp *op, legoProc *proc)
{
  return AddPointerAttribute (ATTR_LIVE, NULL, oprd, (void *) op,
                              ADDREMOVE_OP, proc);
} // end AddLiveAttribute (op)

/*
 * AddLiveAttribute
 *   oprd = new value of attribute
 *   edge = edge for which attribute is added
 *   proc = proc which contains edge
 *   returns: new attribute, or existing attribute with same name
 *
 * Adds live attribute with value oprd to edge.
 */
attrs *
AddLiveAttribute (legoOprd *oprd, opEdges *edge, legoProc *proc)
{
  return AddPointerAttribute (ATTR_LIVE, NULL, oprd, (void *) edge,
                              ADDREMOVE_EDGE, proc);
} // end AddLiveAttribute (edge)

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

static void
RemovePointerAttribute (int atype, char *lcname, void *object, int objtype,
                        legoProc *proc)
{
  attrList *atl, *atlprev;
  attrs *aprev, *a, *adictprev, *adict;
  int i;

  // Scan through region attribute list for lc attribute.
  if (objtype == ADDREMOVE_REGION)
    atl = ((legoRegion *) object)->GetRegionAttrListPtr();
  else if (objtype == ADDREMOVE_OP)
    atl = ((legoOp *) object)->GetOpAttrListPtr();
  else
    atl = ((opEdges *) object)->GetEdgeAttrListPtr();

  for (atlprev = NULL;
       atl != NULL;
       atlprev = atl, atl = atl->GetNextListPtr())
    {
      if (atl->GetAttrType() != atype) continue;

      aprev = NULL;
      if (atype == ATTR_LC)
        {
          for (a = atl->GetAttrPtr();
               a != NULL;
               aprev = a, a = a->GetNextLcEntryPtr())
            if (strcmp (a->GetAttrString(), lcname) == 0) break;
        } // end if
      else
        a = atl->GetAttrPtr();
      if (a == NULL) continue;

      // Remove a from attribute dictionary if a is the first lc
      // attribute in its lc list. 
      if (aprev == NULL)  // a is the first (lc) attribute
        {
          adict = proc->GetAttrDictionary();
          if (adict != NULL)
            {
              // Find a in dictionary.
              for (adictprev = NULL; adict != NULL;
                   adictprev = adict, adict = adict->GetNextAttrPtr())
                if (adict == a) break;

              // adictprev now points to the attribute before a in the
              // attribute dictionary.
              // If a is the only lc attribute in its list, remove
              // the attribute from the dictionary completely. Otherwise,
              // swap in the one next in line.
              if (atype == ATTR_LC && a->GetNextLcEntryPtr() != NULL)
                {  // swap in next one
                  if (adictprev != NULL)  // not first attr in dict
                    adictprev->SetNextAttrPtr (a->GetNextLcEntryPtr());
                  else
                    proc->SetAttrDictionary (a->GetNextLcEntryPtr());
                  a->GetNextLcEntryPtr()->SetNextAttrPtr
                    (a->GetNextAttrPtr());
                  a->GetNextLcEntryPtr()->SetAttrType (ATTR_LC);
                  a->GetNextLcEntryPtr()->SetAttrId (a->GetAttrId());

                  atl->SetAttrPtr (a->GetNextLcEntryPtr());
                } // end if
              else
                {  // Remove completely.
                  if (adictprev != NULL)
                    adictprev->SetNextAttrPtr (a->GetNextAttrPtr());
                  else
                    proc->SetAttrDictionary (a->GetNextAttrPtr());
                  // Can leave atl alone, it will be deleted next...
                } // end else
            } // end if

          // Remove the attrList completely if it only refers to this
          // one (only possible if this is the only lc attribute).
          if (atype != ATTR_LC || a->GetNextLcEntryPtr() == NULL)
            {
              if (atlprev != NULL)
                atlprev->SetNextListPtr (atl->GetNextListPtr());
              else
                {
                  if (objtype == ADDREMOVE_REGION)
                    ((legoRegion *) object)->SetRegionAttrListPtr
                      (atl->GetNextListPtr());
                  else if (objtype == ADDREMOVE_OP)
                    ((legoOp *) object)->SetOpAttrListPtr
                      (atl->GetNextListPtr());
                  else
                    ((opEdges *) object)->SetEdgeAttrListPtr
                      (atl->GetNextListPtr());
                  } // end else
              atl->SetNextListPtr (NULL);
              delete atl;
              atl = atlprev;  // back up for next iteration
            } // end if

          a->SetNextLcEntryPtr (NULL);
          a->SetNextAttrPtr (NULL);
          delete a;

          if (atl == NULL) break;
        } // end if
      else // a is not the first attribute in list
        {
          aprev->SetNextLcEntryPtr (a->GetNextLcEntryPtr());
          a->SetNextLcEntryPtr (NULL);
          a->SetNextAttrPtr (NULL);
          delete a;
        } // end else
    } // end for

  return;
} // end RemovePointerAttribute

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

/*
 * RemoveLcAttribute
 *   lcname = name of lc attribute
 *   region = region within which attribute is removed
 *   proc = proc which contains region
 *
 * Removes lc attribute with name lcname from existence.
 */
void
RemoveLcAttribute (char *lcname, legoRegion *region, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LC, lcname, (void *) region,
                          ADDREMOVE_REGION, proc);
  return;
} // end RemoveLcAttribute (region);

/*
 * RemoveLcAttribute
 *   lcname = name of lc attribute
 *   op = op for which attribute is removed
 *   proc = proc which contains op
 *
 * Removes lc attribute with name lcname from existence.
 */
void
RemoveLcAttribute (char *lcname, legoOp *op, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LC, lcname, (void *) op,
                          ADDREMOVE_OP, proc);
  return;
} // end RemoveLcAttribute (op)

/*
 * RemoveLcAttribute
 *   lcname = name of lc attribute
 *   edge = edge for which attribute is removed
 *   proc = proc which contains edge
 *
 * Removes lc attribute with name lcname from existence.
 */
void
RemoveLcAttribute (char *lcname, opEdges *edge, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LC, lcname, (void *) edge,
                          ADDREMOVE_EDGE, proc);
  return;
} // end RemoveLcAttribute (edge)

/*
 * RemoveLiveAttribute
 *   region = region within which attribute is removed
 *   proc = proc which contains region
 *
 * Removes live attribute from existence.
 */
void
RemoveLiveAttribute (legoRegion *region, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LIVE, NULL, (void *) region,
                          ADDREMOVE_REGION, proc);
  return;
} // end RemoveLiveAttribute (region);

/*
 * RemoveLiveAttribute
 *   op = op for which attribute is removed
 *   proc = proc which contains op
 *
 * Removes live attribute from existence.
 */
void
RemoveLiveAttribute (legoOp *op, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LIVE, NULL, (void *) op,
                          ADDREMOVE_OP, proc);
  return;
} // end RemoveLiveAttribute (op)

/*
 * RemoveLiveAttribute
 *   edge = edge for which attribute is removed
 *   proc = proc which contains edge
 *
 * Removes live attribute from existence.
 */
void
RemoveLiveAttribute (opEdges *edge, legoProc *proc)
{
  RemovePointerAttribute (ATTR_LIVE, NULL, (void *) edge,
                          ADDREMOVE_EDGE, proc);
  return;
} // end RemoveLiveAttribute (edge)

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

/*
 * AddFreqAttribute
 *   weight = profile weight
 *   value = 0 for DUMMY_BR, 1/0 for conditional branch taken/not taken,
 *     cc value for jumptable edge, 1 for control merge (regardless of ops)
 *   edge = edge to which to add attribute
 *
 * Adds freq attribute with weight and value to edge.
 */
attrList *
AddFreqAttribute (int weight, int value, opEdges *edge)
{
  attrList *atl;
  intList *il;

  for (atl = edge->GetEdgeAttrListPtr(); atl != NULL &&
         atl->GetNextListPtr() != NULL; atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_FREQ) break;

  if (atl == NULL)
    {
      atl = new attrList;
      atl->SetAttrType (ATTR_FREQ);
      atl->SetValid (1);
      edge->SetEdgeAttrListPtr (atl);
    }
  else if (atl->GetAttrType() != ATTR_FREQ)
    {
      atl->SetNextListPtr (new attrList);
      atl = atl->GetNextListPtr();
      atl->SetAttrType (ATTR_FREQ);
      atl->SetValid (1);
    }
  il = atl->GetAttrValPtr();
  if (il == NULL)
    {
      il = new intList;
      atl->SetAttrValPtr (il);
    } // end if
  il->SetAttrValue (weight);
  if (il->GetNextIntListPtr() == NULL)
    il->SetNextIntListPtr (new intList);
  il->GetNextIntListPtr()->SetAttrValue (value);

  return atl;
} // end AddFreqAttribute

/*
 * RemoveFreqAttribute
 *   edge = edge from which to remove attribute
 *
 * Removes the freq attribute from an edge.
 */
void
RemoveFreqAttribute (opEdges *edge)
{
  attrList *atl, *atlprev;

  for (atlprev = NULL, atl = edge->GetEdgeAttrListPtr();
       atl != NULL;
       atlprev = atl, atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_FREQ)
      {
        if (atlprev != NULL)
          atlprev->SetNextListPtr (atl->GetNextListPtr());
        else
          edge->SetEdgeAttrListPtr (atl->GetNextListPtr());
        atl->SetNextListPtr (NULL);
        delete atl;
        break;
      } // end if
  return;
} // end RemoveFreqAttribute

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

/*
 * ClearMarks
 *   m = mark to clear
 *   region = region to look within for mark
 *
 * Clears the mark m from region and all regions it contains.
 */
void
ClearMarks (long long m, legoRegion *region)
{
  legoRegion *component;

  region->Unmark (m);
  if (!(IS_BLOCK (region->GetRegionType())))
    for (unsigned i = 0; i < region->GetCount(); i++)
      {
        component = (legoRegion *) region->GetItem(i);
        if (IS_BLOCK (component->GetRegionType()))
          component->Unmark (m);  // to avoid recursing one more level
        else
          ClearMarks (m, component);
      } // end for

  return;
} // end ClearMarks (legoRegion *)

/*
 * ClearMarks
 *   m = mark to clear
 *   edge = edge to start with clearing mark
 *
 * Clears the mark m from edges and all edges following it.
 */
void
ClearMarks (long long m, opEdges *edge)
{
  opEdges *e;

  for (e = edge; e != NULL; e = e->GetNextOpEdgePtr())
    e->Unmark (m);
  return;
} // end ClearMarks (opEdges *)

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

---