region.C

Go to the documentation of this file.

/*--------------------------------------------------------------------
 *
 *  region.cpp
 *
 *  Willie Glover
 *
 *  12/09/96 WAH: Added tail duplication method.
 *  2/13/97 WAH:  Made name change from legoRegionRef to regionList et al.
 *  2/28/97 WAH:  Modified GetParents and GetChildren to return regions
 *                of the same type only.
 *  3/4/97 WAH:   Fixed said modifications to actually work. :)
 *  3/20/97 WAH:  Added markfield to legoRegion.
 *  3/21/97 WAH:  Copy constructor now adds copy to parent region.
 *  4/10/97 WAH:  Added OpKiller and RegionKiller methods.
 *  4/11/97 WAH:  Fixed destructor to invalidate children of this'
 *                parents and parents of this' children.
 *  7/11/97 WAH:  Deconstructor won't remove parents/children of self
 *                if self is child/parent.
 *  9/3/97 WAH:   Fixed region deconstructor to delete modules correctly.
 *  4/22/98 WAH:  Moved FindMaxRegionId here from region.taildup.C.
 *-------------------------------------------------------------------*/

#ifndef LEGOREGION_H
#include "region.H"
#include "flag.H"
#endif

//void LegoErr(char*);

legoRegion::legoRegion (enum regionTypes rType, unsigned id)
             : legoPSet<void *>()
{
  //  fprintf(stderr,"Creating LEGOREGION %p\n",this);
  regionId              = id;
  regionType            = rType;        // region type
  inEdgesPtr            = NULL;         // ptr to list of (op,flowfreq)
  outEdgesPtr           = NULL;         // ptr to list of (op,flowfreq)
  flagPtr               = NULL;         // ptr to list of region flags
  entryOpsPtr           = NULL;         // ptr to list of entry ops
  exitOpsPtr            = NULL;         // ptr to list of exit ops
  regionAttrListPtr     = NULL;         // ptr to attribute list
  weight                = 0;            // ptr to next op in prog flow
  parentPtr             = NULL;         // ptr to parent region
  parents = children    = NULL;         // ptrs in control flow
  dominators            = NULL;         // ptr to dominators
  allListPtr            = NULL;         // ptr to list of all ops
  markfield             = (long long)0; // array of bits to mark
  nestingLevel          = -1;           // level of loop nesting
}

legoRegion::legoRegion () : legoPSet<void *>()
{
  //  fprintf(stderr,"Creating LEGOREGION %p\n",this);
  regionId              = 0;            // mark as unintialized
  regionType            = RT_BB;                // default to basic block
  inEdgesPtr            = NULL;         // ptr to list of (op,flowfreq)
  outEdgesPtr           = NULL;         // ptr to list of (op,flowfreq)
  flagPtr               = NULL;         // ptr to list of region flags
  entryOpsPtr           = NULL;         // ptr to list of entry ops
  exitOpsPtr            = NULL;         // ptr to list of exit ops
  regionAttrListPtr     = NULL;         // ptr to attribute list
  weight                = 0;            // ptr to next op in prog flow
  parentPtr             = NULL;         // ptr to parent region
  parents = children    = NULL;         // ptrs in control flow
  dominators            = NULL;         // ptr to dominators
  allListPtr            = NULL;         // ptr to list of all ops
  markfield             = (long long)0; // array of bits to mark
  nestingLevel          = -1;           // level of loop nesting
}

legoRegion::legoRegion (const legoRegion &orig) :
  legoPSet<void *> ((legoPSet<void *>) orig)
{
  //  fprintf(stderr,"Creating LEGOREGION %p\n",this);
  regionId      = orig.regionId;  // will be changed anyway
  regionType    = orig.regionType;

  if (orig.inEdgesPtr != NULL)
        inEdgesPtr = new edgeList (*(orig.inEdgesPtr));
  else  inEdgesPtr = NULL; 

  if (orig.outEdgesPtr != NULL)
        outEdgesPtr = new edgeList (*(orig.outEdgesPtr));
  else  outEdgesPtr = NULL; 

  if (orig.flagPtr != NULL)
        flagPtr = new flags (*(orig.flagPtr));
  else  flagPtr = NULL; 

  if (orig.entryOpsPtr != NULL)
        entryOpsPtr = new opList (*(orig.entryOpsPtr));
  else  entryOpsPtr = NULL; 

  if (orig.exitOpsPtr != NULL)
        exitOpsPtr = new opList (*(orig.exitOpsPtr));
  else  exitOpsPtr = NULL; 

  if (orig.regionAttrListPtr != NULL)
        regionAttrListPtr = new attrList (*(orig.regionAttrListPtr));
  else  regionAttrListPtr = NULL; 

  weight        = orig.weight;
  parentPtr     = orig.parentPtr;
  parents       = NULL;                 // don't bother copying - will be constructed on demand
  children      = NULL;
  dominators    = NULL;                 // don't bother copying - will be wrong anyway
  allListPtr    = orig.allListPtr;
  markfield     = orig.markfield;
  nestingLevel  = orig.nestingLevel;
  DAG           = NULL;                 // since can be anything, don't want to copy construct

  if (parentPtr != NULL)
    parentPtr->AddItem (this);
} // end copy constructor

legoRegion::~legoRegion()
{
  regionList *rl;
  legoRegion *r, *rp;

  Mark (RM_KISSOFDEATH);
  delete flagPtr;
  delete entryOpsPtr;
  delete exitOpsPtr;
  delete regionAttrListPtr;

  // Destroy the parent/children lists of surrounding regions, so they
  // don't continue pointing to this. However, don't bother if the
  // encompassing proc is marked for death, since we're bound to end up
  // pointing to something that was just deleted.

  for (r = this; r->regionType != RT_PROC; r = r->parentPtr)
    if (r->regionType == RT_MODULE) break;
  if (!(r->IsMarked (RM_KISSOFDEATH)))
    {
      // Need to get to all parents, so construct list now!
      for (rl = GetParents(); rl != NULL; rl = rl->GetNextListPtr())
        {  // loop through parents of this one
          r = rl->GetRegionPtr();
          if (r != NULL && r != this)
            {
              delete r->children;  // delete children list
              r->children = NULL;
            } // end if
          for (rp = r->parentPtr; rp->regionType != RT_PROC;
               rp = rp->parentPtr)  // loop through containers of parent
            {
              delete rp->children;  // delete container's children list
              rp->children = NULL;
            } // end for
        } // end for
      delete parents;
      // Need to get to all children, so construct list now!
      for (rl = GetChildren(); rl != NULL; rl = rl->GetNextListPtr())
        {  // sim. for children of this one
          r = rl->GetRegionPtr();
          if (r != NULL && r != this)
            {
              delete r->parents;
              r->parents = NULL;
            } // end if
          for (rp = r->parentPtr; rp->regionType != RT_PROC;
               rp = rp->parentPtr)
            {
              delete rp->parents;
              rp->parents = NULL;
            } // end for
        } // end for
      delete children;
    } // end if
  else
    {
      delete parents;
      delete children;
    } // end else
  delete dominators;
  delete inEdgesPtr;
  delete outEdgesPtr;

  // Don't call Keeler - they're void *.
  //  fprintf(stderr,"Deleting LEGOREGION %p\n",this);
} // end destructor

/*
 * RefreshAll
 *
 * Calls RefreshOpsAndEdges on all contained regions, then self.
 */
void
legoRegion::RefreshAll (void)
{
  if (!(IS_BLOCK(regionType)))
    for (unsigned i = 0; i < GetCount(); i++)
      ((legoRegion *) GetItem (i))->RefreshAll();

  RefreshOpsAndEdges();
  return;
} // end RefreshAll

/*------------------------------------------------------------------
 *   Name:        RegionMap.C
 *   Designer:    Willie Glover
 *   Created:     4/24/96
 *   Description: This file maps legoRegion's char*.
 *------------------------------------------------------------------
 *
 *-----------------------------------------------------------------*/

static const char * const regionNames[] = {
  "proc",  "bb",  "hb",  "sb",  "loop",  "loopbody", "trace",
  "module", "tree", ""
};
char *RegionMap(int rType)
{
  char *regionName;

  regionName = const_cast<char *>(regionNames[rType]);
  return regionName;
}

/*------------------------------------------------------------------
 *   Name:        FindOpId.C
 *   Designer:    Willie Glover
 *   Created:     6/27/96
 *   Description: input is opId.  output in legoOp*. Start the search 
 *                at the first op in this region (use allListPtr).
 *------------------------------------------------------------------
 *
 *-----------------------------------------------------------------*/
legoOp *legoRegion::FindOpId(int currOpId)
{
  legoOp *returnOpPtr = NULL;
  legoOp *firstOpPtr = NULL;
  legoRegion *nextRegionPtr = NULL;
  switch (this->regionType) {
    case RT_PROC:
       nextRegionPtr = (legoRegion *)GetItem(0);
       if ( nextRegionPtr == NULL) { return returnOpPtr; }
       while ( (nextRegionPtr->regionType == RT_PROC) ||
               (nextRegionPtr->regionType == RT_LOOPBODY) ) {
        // fprintf(stderr,"in 1st FindOpId while block/n");
         nextRegionPtr = (legoRegion *)nextRegionPtr->GetItem(0);
       }
       firstOpPtr = (legoOp *)nextRegionPtr->GetItem(0);
       break;
    case RT_BB:
       firstOpPtr = (legoOp *)GetItem(0);
       break;
    case RT_HB:
       firstOpPtr = (legoOp *)GetItem(0);
       break;
    case RT_SB:
       firstOpPtr = (legoOp *)GetItem(0);
       break;
    case RT_LOOP:
       firstOpPtr = (legoOp *)GetItem(0);
       break;
    case RT_LOOPBODY:
       nextRegionPtr = (legoRegion *)GetItem(0);
       if ( nextRegionPtr == NULL) { return returnOpPtr; }
       while ( (nextRegionPtr->regionType == RT_PROC) ||
               (nextRegionPtr->regionType == RT_LOOPBODY) ) {
        // fprintf(stderr,"in 2nd FindOpId while block/n");
         nextRegionPtr = (legoRegion *)nextRegionPtr->GetItem(0);
       }
       firstOpPtr = (legoOp *)nextRegionPtr->GetItem(0);
       break;
    default:
       return returnOpPtr;
       break;
  }
  returnOpPtr = firstOpPtr;
  while ( currOpId != returnOpPtr->GetOpId() ) {
        // fprintf(stderr,"  opPtr =%p",returnOpPtr);
        // fprintf(stderr,"opId =%d/n",returnOpPtr->GetOpId());
    returnOpPtr = returnOpPtr->GetListOpPtr();
    if (returnOpPtr == NULL) { return returnOpPtr; }
  }
    return returnOpPtr;
}

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

regionList *
legoRegion::GetParents (void)
{
  edgeList *inedgelist, *scan;
  opEdges *inedge;
  legoOp *prevop;
  legoRegion *prevopparent;
  regionList *head = NULL, *current;

  if (parents != NULL)  // already built parent list
    return parents;
  // else build on demand

  inedgelist = GetInEdgesPtr();
  if (inedgelist != NULL)  // otherwise, no in edges = no parents
    {
      for (scan = inedgelist, inedge = scan->GetEdgePtr();
           inedge != NULL;
           inedge = scan->GetEdgePtr())  // ( don't update scan here)
        {
          prevop = inedge->GetFromOpPtr();
          if (prevop != NULL)  // otherwise, skip if missing op
            {
              prevopparent = (legoRegion *) prevop->GetParentBlockPtr();
              while (prevopparent->GetRegionType() != RT_MODULE)
                {
                  if ((prevopparent->GetRegionType() == regionType) ||
                      (IS_BLOCK(prevopparent->GetRegionType()) &&
                       IS_BLOCK(regionType)))
                    {
                      current = new regionList (prevopparent);

                      if (head != NULL)
                        head->Concatenate (current);
                      else
                        head = current;
                      break;
                    } // end if
                  prevopparent = prevopparent->GetParentPtr();
                } // end while
            } // end if
                        
          // Advance scan and check for NULL.
          scan = scan->GetNextListPtr();
          if (scan == NULL)
            break;
        } // end for
    } // end if

  parents = head;
  return head;
} // end legoRegion::GetParents

void legoRegion::SetParents (regionList *p)
{
  delete parents;
  parents = p;
} // end SetParents

regionList *
legoRegion::GetChildren (void)
{
  edgeList *outedgelist, *scan;
  opEdges *outedge;
  legoOp *nextop;
  legoRegion *nextopparent;
  regionList *head = NULL, *current;

  if (children != NULL)  // already built children list
    return children;
  // else build on demand

  outedgelist = GetOutEdgesPtr();
  if (outedgelist != NULL)  // otherwise, no out edges = no children
    {
      for (scan = outedgelist, outedge = scan->GetEdgePtr();
           outedge != NULL;
           outedge = scan->GetEdgePtr())  // ( don't update scan here)
        {
          nextop = outedge->GetToOpPtr();
          if (nextop != NULL)  // otherwise, skip if missing op
            {
              nextopparent = (legoRegion *) nextop->GetParentBlockPtr();
              while (nextopparent->GetRegionType() != RT_MODULE)
                {
                  if ((nextopparent->GetRegionType() == regionType) ||
                      (IS_BLOCK(nextopparent->GetRegionType()) &&
                       IS_BLOCK(regionType)))
                    {
                      current = new regionList (nextopparent);

                      if (head != NULL)
                        head->Concatenate (current);
                      else
                        head = current;
                      break;
                    } // end if
                  nextopparent = nextopparent->GetParentPtr();
                } // end while
            } // end if
                        
          // Advance scan and check for NULL.
          scan = scan->GetNextListPtr();
          if (scan == NULL)
            break;
        } // end for
    } // end if

  children = head;
  return head;
} // end legoRegion::GetChildren

void legoRegion::SetChildren (regionList *c)
{
  delete children;
  children = c;
} // end SetChildren

/*
 * legoRegion::IsContainedIn
 *   r = region being searched for
 *
 * Returns whether this region is contained in r. By definition, a
 * region contains itself.
 */
int
legoRegion::IsContainedIn (legoRegion *r)
{
  legoRegion *parent;

  for (parent = this; parent != NULL; parent = parent->GetParentPtr())
    {
      if (parent == r)
        return 1;
    } // end for

  return 0;
} // end legoRegion::IsContainedIn

/*
 * legoRegion::Contains
 *   r = region being searched for
 *
 * Returns whether this region contains r. By definition, a region
 * contains itself.
 */
int
legoRegion::Contains (legoRegion *r)
{
  return (r->IsContainedIn (this));
}

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

/*
 * FindMaxRegionId
 *   reg = region to look within
 *   returns: the region with the largest id within it
 *
 * Finds the largest region id within the given region.
 */
legoRegion *
legoRegion::FindMaxRegionId (void)
{
  int i;
  legoRegion *block, *maxblock = NULL, *candblock;

  for (i = 0; i < GetCount(); i++)
    {
      block = (legoRegion *) GetItem(i);
      if (!(IS_BLOCK(block->GetRegionType())))
        candblock = block->FindMaxRegionId();
      else
        candblock = block;
      if ((maxblock == NULL) ||
          (candblock->GetRegionId() > maxblock->GetRegionId()))
        maxblock = candblock;
    } // end for

  // Also check yourself!
  if (this->GetRegionType() != RT_PROC &&
      this->GetRegionType() != RT_MODULE &&
      this->GetRegionId() > maxblock->GetRegionId())
    maxblock = this;

  return maxblock;
} // end FindMaxRegionId

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

/*
 * regionList::Concatenate
 *   newhead = pointer to new refs
 *
 * Concatenates the list headed by newhead onto this one. Any duplicates
 * are removed. (Therefore this is a UNION.)
 */
void
regionList::Concatenate (class regionList *newhead)
{
  class regionList *oldhead, *oldtail, *r, *o, *dead;

  for (oldhead = oldtail = this; oldtail->GetNextListPtr() != NULL;
       oldtail = oldtail->GetNextListPtr()) ;

  r = newhead;
  while (r != NULL)
    {
      // Try to get o to point to a duplicate.
      for (o = oldhead; o != NULL; o = o->GetNextListPtr())
        {
          if (o->GetRegionPtr() == r->GetRegionPtr())
            break;  // found same ref, so stop
        } // end for

      if (o == NULL)
        {  // no duplicates, so append it
          oldtail->Append (r);  // append r to list
          oldtail = r;  // it's the new tail
          r = r->GetNextListPtr();
          oldtail->SetNextListPtr (NULL);  // it's the tail
        } // end if
      else
        {  // a duplicate, so move to next, then delete this one
          dead = r;
          r = r->GetNextListPtr();
          dead->SetNextListPtr (NULL);  // to avoid deleting r
          delete dead;
        } // end else
    } // end while

  oldtail->SetNextListPtr (NULL);  // terminate new list
  return;

} // end Concatenate

/*
 * regionList::Intersect
 *   newhead = pointer to new refs
 *
 * Intersects the list headed by newhead with this one. Neither list
 * is destroyed. Note that this returns a NEW list.
 */
regionList *
regionList::Intersect (class regionList *newhead)
{
  regionList *oldhead, *oldtail, *r, *o, *dead;
  regionList *intersection = NULL, *itail;

  for (oldhead = oldtail = this; oldtail->GetNextListPtr() != NULL;
       oldtail = oldtail->GetNextListPtr()) ;

  for (o = oldhead; o != NULL; o = o->GetNextListPtr())
    {
      // Try to get r to point to a duplicate.
      for (r = newhead; r != NULL; r = r->GetNextListPtr())
        {
          if (o->GetRegionPtr() == r->GetRegionPtr())
            break;  // found same ref, so stop
        } // end for

      if (r != NULL)
        {  // found duplicate, so create new entry
          if (intersection != NULL)
            {
              itail->SetNextListPtr (new regionList);
              itail = itail->GetNextListPtr();
            } // end if
          else
            intersection = itail = new regionList;
          itail->SetRegionPtr (o->GetRegionPtr());
        } // end if

    } // end while

  return intersection;

} // end Intersect

/*
 * OpKiller, RegionKiller
 *
 * Deletes the objects (of type legoOp *, legoRegion *) contained
 * in the region.
 *
 * Why are these here, you ask? Well, legoRegions weren't getting
 * deleted properly before. They hold pointers to void, so the
 * legoPArr method PEmpty deleted them as (void *), which skipped
 * the component legoOps' / legoRegions' destructors weren't
 * being called.
 *
 * The awesome solution is to make legoRegion still a template.
 * Then, a legoBB derives from legoRegion<legoOp *>, and legoProc
 * derives from legoRegion<legoRegion <whatever> >. Unfortunately,
 * you can't just leave "whatever" there.
 *
 * The nearly-as-awesome solution is to make PEmpty a member
 * template, with template parameter X being the type of whatever
 * is being held by the legoPArr. The calls from legoPArr and
 * legoPSet can call it with X = T. legoRegion can use X = void *.
 * The legoBB can use X = legoOp *, and the legoProc can use
 * legoRegion *. But, gcc 2.7.2 DOESN'T SUPPORT MEMBER TEMPLATES!
 *
 * No problem, make it a template function not in a class, which
 * gcc CAN do, and make it a friend of legoRegion ... which
 * gcc CAN'T do (that's a known BUG in gcc).
 *
 * So the template function (Keeler) can't be a friend, but other
 * than that, it can work.
 *
 * Still, it needs to do everything PEmpty did, including calling
 * legoPArr::Empty(). Since Keeler isn't a friend of legoRegion,
 * it can't say r->Data.Empty(), so this function has to be
 * public in legoRegion, which is dangerous, but required.
 *
 * And, alas, I can't even get this to compile as a template,
 * so I'll overload it with X as legoRegion * and again as legoOp *.
 *
 * But then it might as well be inside legoRegion, since it's not
 * a template anymore!
 *
 * In the future, SOMEBODY, PLEASE MAKE SOMETHING THAT WORKS BETTER!!!
 */
void legoRegion::OpKiller (void)
{
  unsigned i;
  int count;
  void *item;

  //  fprintf (stderr,"I am the KEELER of OPS!\n");
  count = GetCount();

  if (IsOwner())
  for (i = 0; i < count; i++)
    {
      item = GetItem(i);
      delete (legoOp *) item;
    } // end for
  Data.Empty();
  //  fprintf (stderr,"I KEEL the OPS!\n");
} // end legoRegion::OpKiller

void legoRegion::RegionKiller (void)
{
  unsigned i;
  int count;
  void *item;

  //  fprintf(stderr,"I am the KEELER of REEGIONS!\n");
  count = GetCount();

  if (IsOwner())
  for (i = 0; i < count; i++)
    {
      item = GetItem(i);
      delete (legoRegion *) item;
    } // end for
  Data.Empty();
  //  fprintf(stderr,"I KEEL the REEGIONS!\n");
} // end legoRegion::RegionKiller

---