search.C

Go to the documentation of this file.

// search.C

/*
 * LEGO Search Functions
 * by Bill Havanki
 *
 * 7/16/97 WAH:  Created file; added FindParentRegionType.
 * 7/17/97 WAH:  Added FindLcAttribute.
 * 10/14/97 WAH: Added FindFlag.
 * 10/17/97 WAH: Added FindEdgeFrequency.
 * 10/28/97 WAH: Added FindLiveAttribute.
 * 11/21/97 WAH: Revamped some function calls; added FindLcAttribute for
 *               opEdges and FindMaxEdgeAttrId.
 * 12/16/97 WAH: Added FindControlEdge.
 * 1/14/98 WAH:  Added check for NULL object in FindLcAttribute.
 * 1/15/98 WAH:  Added FindFirstBranch.
 * 2/11/98 WAH:  Added FindOpWeight.
 * 2/12/98 WAH:  Added FindReturnMacro.
 * 2/24/98 WAH:  Added IsFallThrough.
 * 4/9/98 WAH:   Added FindFreqAttribute.
 * 5/6/98 WAH:   Updated classification functions for UDPRED, LDPRED,
 *               COPY_B, COPY_H, and COPY_W.
 * 02/28/02 HZ:  Updated the IsXXOp functions to the legoOpcode class
 */

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

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

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

/*
 * FindMaxOpId
 *   proc = procedure to look within
 *   returns: legoOp with highest op id, NULL if error
 *
 * Searches through procedure for op with the highest op id.
 */
legoOp *
FindMaxOpId (legoProc *proc)
{
  legoOp *allList, *maxop = NULL;
  int maxid = -1;

  if (proc->GetRegionType() != RT_PROC)
    return NULL;
  for (allList = proc->GetListOpPtr();
       allList != NULL; allList = allList->GetListOpPtr())
    if (allList->GetOpId() > maxid)
      {
        maxid = allList->GetOpId();
        maxop = allList;
      } // end if
  return maxop;
} // end FindMaxOpId (proc)

/*
 * FindMaxOpId
 *   mod = module to look within
 *   returns: legoOp with highest op id, NULL if error
 *
 * Searches through module for op with the highest op id.
 *
 * If any changes are made to FindMaxOpId, echo them to the copy in
 * region.taildup.C (Lego IR).
 */
legoOp *
FindMaxOpId (legoModule *mod)
{
  legoProc *proc;
  legoOp *procop, *maxop = NULL;
  int i, maxid = -1;

  if (mod->GetRegionType() != RT_MODULE)
    return NULL;
  for (i = 0; i < mod->GetCount(); i++)
    {
      proc = (legoProc *) mod->GetItem(i);
      procop = FindMaxOpId (proc);
      if (procop != NULL && procop->GetOpId() > maxid)
        {
          maxid = procop->GetOpId();
          maxop = procop;
        } // end if
    } // end for
  return maxop;
} // end FindMaxOpId (mod)

/*
 *      FindMaxRegNum
 *      proc_ptr        = the procedure to look in 
 *
 *
 *      Finds the Maximum reg number among all 
 *      register files 
 *      Regards Rg allocated code 
 */ 

int FindMaxRegNum (legoProc *proc_ptr) 
{ 
   int          max_id          = 0;
   legoOp       *allList        = NULL;
   legoOprd     *test_oprd      = NULL;

   if(proc_ptr->GetRegionType() != RT_PROC){
        LegoNonFatal("FindMaxRegNum","Warning: find_max_reg_num called for non-procedure.");
        return 0;
   }
   for(allList=proc_ptr->GetListOpPtr();allList!=NULL;allList = allList->GetListOpPtr()){
        // Look through all srcs
        test_oprd       = allList->GetSrcOprdPtr();
        while(test_oprd){
                if(test_oprd->GetOprdType()==OT_REG){ 
                        if(test_oprd->GetOprdRegType() == RT_BR){               
                                // In bounded registers, this is the real value  
                                if(test_oprd->GetOprdIntValue()>max_id) max_id  = test_oprd->GetOprdIntValue(); 
                        } 
                        else    if(test_oprd->GetOprdRegNum()>max_id)   max_id  = test_oprd->GetOprdRegNum();        
                } 
                test_oprd       = test_oprd->GetNextOprdPtr();
        }
        // ... and all dests
        test_oprd       = allList->GetDestOprdPtr();
        while(test_oprd){
                if(test_oprd->GetOprdType()==OT_REG){ 
                        if(test_oprd->GetOprdRegType() == RT_BR){   
                                if(test_oprd->GetOprdIntValue()>max_id) max_id  = test_oprd->GetOprdIntValue(); 
                        } 
                        else    if(test_oprd->GetOprdRegNum()>max_id)   max_id  = test_oprd->GetOprdRegNum();        
                } 
                test_oprd       = test_oprd->GetNextOprdPtr();
        }
   }
   return max_id;
}

/*
 *   Same as previous, but looks only through correspondent 
 *   file type
 */ 

int FindMaxRegNum (legoProc *proc_ptr,enum fileTypes current_ft)
{
   int          max_id          = 0;
   legoOp       *allList        = NULL;
   legoOprd     *test_oprd      = NULL;

   if(proc_ptr->GetRegionType() != RT_PROC){
        LegoNonFatal("FindMaxRegNum","Warning: find_max_reg_num called for non-procedure.");
        return 0;
   }
   for(allList=proc_ptr->GetListOpPtr();allList!=NULL;allList = allList->GetListOpPtr()){
        // Look through all srcs
        test_oprd       = allList->GetSrcOprdPtr();
        while(test_oprd){
                if((test_oprd->GetOprdType() == OT_REG)&&(test_oprd->GetOprdFileType() == current_ft)){ 
                        if(test_oprd->GetOprdRegType() == RT_BR){               
                                // In bounded registers, this is the real value
                                if(test_oprd->GetOprdIntValue()>max_id) max_id  = test_oprd->GetOprdIntValue(); 
                        } 
                        else    if(test_oprd->GetOprdRegNum()>max_id)   max_id  = test_oprd->GetOprdRegNum();        
                } 
                test_oprd       = test_oprd->GetNextOprdPtr();
        }
        // ... and all dests
        test_oprd       = allList->GetDestOprdPtr();
        while(test_oprd){
                if((test_oprd->GetOprdType() == OT_REG)&&(test_oprd->GetOprdFileType() == current_ft)){ 
                        if(test_oprd->GetOprdRegType() == RT_BR){   
                                if(test_oprd->GetOprdIntValue()>max_id) max_id  = test_oprd->GetOprdIntValue(); 
                        } 
                        else    if(test_oprd->GetOprdRegNum()>max_id)   max_id  = test_oprd->GetOprdRegNum();        
                } 
                test_oprd       = test_oprd->GetNextOprdPtr();
        }
   }
   return max_id;
}

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

/*
 * FindMaxEdgeAttrId
 *   proc = proc within which to look
 *   returns: id of edge or attribute with maximum id, 0 if none found
 *
 * Searches through the edge and attribute dictionaries of proc and
 * returns the id of the edge or attribute with the biggest id.
 */
int
FindMaxEdgeAttrId (legoProc *proc)
{
  opEdges *edge;
  attrs *at;
  int maxid = 0;

  // Start by getting dictionaries.
  edge = ((legoProc *) proc)->GetEdgeDictionary();
  if (edge == NULL)
    {
      LegoNonFatal ("FindMaxEdgeAttrId", "Edge dictionary is missing.");
      return 0;
    } // end if
  at = ((legoProc *) proc)->GetAttrDictionary();
  if (at == NULL)
    {
      LegoNonFatal ("FindMaxEdgeAttrId", "Attribute dictionary is missing.");
      return 0;
    } // end if

  for ( ; edge != NULL; edge = edge->GetNextOpEdgePtr())
    if (edge->GetEdgeId() > maxid) maxid = edge->GetEdgeId();
  for ( ; at != NULL; at = at->GetNextAttrPtr())
    if (at->GetAttrId() > maxid) maxid = at->GetAttrId();

  return maxid;
} // end FindMaxEdgeAttrId

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

/*
 * FindParentRegionType
 *   t = type to search for
 *   region/op = starting point for parent search
 *   returns: region of type t, NULL otherwise
 *
 * Searches for container of region/op with type t.
 */
legoRegion *
FindParentRegionType (enum regionTypes t, legoRegion *region)
{
  legoRegion *r;
  for (r = region; r != NULL; r = r->GetParentPtr())
    if (r->GetRegionType() == t) break;
  if (r == NULL) return NULL;
  else return (legoProc *) r;
} // end FindParentRegionType (region)

legoRegion *
FindParentRegionType (legoRegion *region, enum regionTypes t)
{
  LegoNonFatal ("FindParentRegionType", "This is a deprecated version of "
                "this function.\nSwap the parameters in the call.");

  return FindParentRegionType (t, region);
}

legoRegion *
FindParentRegionType (enum regionTypes t, legoOp *op)
{
  return FindParentRegionType (t, (legoRegion *) (op->GetParentBlockPtr()));
} // end FindParentRegionType (op)

legoRegion *
FindParentRegionType (legoOp *op, enum regionTypes t)
{
  LegoNonFatal ("FindParentRegionType", "This is a deprecated version of "
                "this function.\nSwap the parameters in the call.");

  return FindParentRegionType (t, op);
}

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

/*
 * FindFirstBranch
 *   region = region within which to search
 *   returns: first branch op in region, NULL if no branch found
 *
 * Runs down the ops of a region and finds the first branch in control
 * flow from the first entry op listed.
 */
legoOp *
FindFirstBranch (legoRegion *region)
{
  opList *opl;
  legoOp *opscan;

  opl = region->GetEntryOpsPtr();
  if (opl == NULL) return NULL;

  for (opscan = opl->GetOpPtr(); opscan != NULL;
       opscan = opscan->GetNextLink())
    {
      if (opscan->GetOutListPtr() != NULL) return opscan;
    } // end for

  return NULL;
} // end FindFirstBranch

/*
 * IsFallThrough
 *   src = source op
 *   dest = destination op
 *   returns: 1 if src can fall-through to dest, 0 otherwise or if error
 *
 * Determines whether it is possible for control to fall through from
 * src directly to dest. src must be a branch, and dest a C_MERGE.
 */
int
IsFallThrough (legoOp *src, legoOp *dest)
{
  legoOp *walkop;
  legoOprd *btr;

  if (src->GetOutListPtr() == NULL)
    {
      LegoNonFatal ("IsFallThrough", "Source op %d is not a branch!",
                    src->GetOpId());
      return 0;
    } // end if
  if (dest->IsCMERGEOp() == false)
    {
      LegoNonFatal ("IsFallThrough", "Destination op %d is not a merge!",
                    dest->GetOpId());
      return 0;
    } // end if

  // If src is a DUMMY_BR, yes.
  if (src->IsDUMMYBROp()) return 1;

  // If dest follows src in the same block, yes.
  if (src->GetNextLink() == dest) return 1;

  // If src is a BRU, no.
  if (src->IsBRUOp()) return 0;

  // If src is a BRCT or BRCF, walk up to the last PBRR/A. If it prepares
  // to branch to the block dest lives in, then it's NOT a fall-through.
  if (src->IsBRCONDOp())
    {
      for (walkop = src->GetPrevLink(); walkop != NULL;
           walkop = walkop->GetPrevLink())
        {
          if (walkop->GetOpcode() == PBRR) break;
          if (walkop->GetOpcode() == PBRA) break;
        } // end for
      if (walkop == NULL)
        {
          LegoNonFatal ("IsFallThrough", "Can't find PBR before op %d.",
                        src->GetOpId());
          return 0;
        } // end if
      btr = walkop->GetSrcOprdPtr();
      if (btr == NULL)
        {
          LegoNonFatal ("IsFallThrough", "No btr operand for op %d.",
                        walkop->GetOpId());
          return 0;
        } // end if
      if (btr->GetOprdType() != OT_LITERAL_CB) return 0;  // explicit branch
      if (btr->GetLiteralControlBlock() ==
          ((legoRegion *) dest->GetParentBlockPtr())->GetRegionId())
        return 0;  // the branch is taken to dest, so not fall-thru
      return 1;  // else, it is
    } // end if (BRCT / BRCF)

  // If haven't figured it out yet, assume it's not a fall-through.
  LegoNonFatal ("IsFallThrough", "Don't know how to decide on ops %d and "
                "%d.", src->GetOpId(), dest->GetOpId());
  return 0;
} // end IsFallThrough

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

/*
 * FindControlEdge
 *   fromop = op at tail of edge
 *   toop = op at head of edge
 *   between = whether fromop exits a block and toop enters a block
 *   returns: control edge between fromop and toop
 *
 * Hunts through the edge dictionary to find the first control edge
 * between fromop and toop, and returns a pointer to it. If between
 * is 1, assumes that fromop is an exit op and toop is an entry op,
 * and searches the block edge information only (faster). If that fails,
 * the search fails.
 */
opEdges *
FindControlEdge (legoOp *fromop, legoOp *toop, int between = 0)
{
  opEdges *theedge;

  if (fromop == NULL || toop == NULL)
    {
      LegoNonFatal ("FindControlEdge", "Passed NULL op.");
      return NULL;
    } // end if
  if (between)
    {
      legoRegion *fromblock, *toblock;
      edgeList *outedges, *inedges;

      fromblock = (legoRegion *) fromop->GetParentBlockPtr();
      toblock = (legoRegion *) toop->GetParentBlockPtr();
      theedge = NULL;

      if (fromblock == NULL || toblock == NULL)
        {
          LegoNonFatal ("FindControlEdge", "Can't find parent block of "
                        "an op.");
        } // end if
      else
        {
          // Search through all of fromblock's exit egdes until the one that
          // flows between fromop and toop is found.
          for (outedges = fromblock->GetOutEdgesPtr();
               outedges != NULL; outedges = outedges->GetNextListPtr())
            {
              if (outedges->GetEdgePtr()->GetFromOpPtr() != fromop)
                continue;

              for (inedges = toblock->GetInEdgesPtr();
                   inedges != NULL; inedges = inedges->GetNextListPtr())
                {
                  if (inedges->GetEdgePtr() == outedges->GetEdgePtr())
                    {
                      theedge = inedges->GetEdgePtr();
                      break;
                    } // end if
                } // end for

              if (theedge != NULL) return theedge;
            } // end for

        } // end else
      return NULL;
    } // end if

  // We get here if the between test failed. Run through the edge dictionary.
  legoProc *proc = (legoProc *) FindParentRegionType (RT_PROC, fromop);
  if (proc == NULL)
    {
      LegoNonFatal ("FindControlEdge", "Couldn;t find proc of op %d.",
                    fromop->GetOpId());
      return NULL;
    } // end if

  for (theedge = proc->GetEdgeDictionary(); theedge != NULL;
       theedge = theedge->GetNextOpEdgePtr())
    {
      if (theedge->GetFromOpPtr() != fromop) continue;
      if (theedge->GetToOpPtr() != toop) continue;
      if (theedge->GetEdgeType() != ET_CNTL) continue;
      // Found it.
      return theedge;
    } // end for

  // Failed.
  return NULL;
} // end FindControlEdge

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

/*
 * FindLcAttribute
 *   lcname = name of lc attribute to search for
 *   region/op/edge = where to look for attribute
 *   returns: attribute if found, NULL otherwise
 *
 * Finds the first lc attribute named lcname in the object.
 */
static attrs *
FindLcAttribute (char *lcname, void *object, int objtype)
{
  attrList *atl;
  attrs *a;

  if (object == NULL) return NULL;

  if (objtype == 1)
    atl = ((legoRegion *) object)->GetRegionAttrListPtr();
  else if (objtype == 0)
    atl = ((legoOp *) object)->GetOpAttrListPtr();
  else
    atl = ((opEdges *) object)->GetEdgeAttrListPtr();

  for ( ; atl != NULL; atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_LC) break;
  if (atl == NULL) return NULL;

  for (a = atl->GetAttrPtr(); a != NULL; a = a->GetNextLcEntryPtr())
    if (strcmp (a->GetAttrString(), lcname) == 0) break;

  return a;
} // end FindLcAttribute (object)

attrs *
FindLcAttribute (char *lcname, legoRegion *region)
{
  return FindLcAttribute (lcname, (void *) region, 1);
} // end FindLcAttribute (region)

attrs *
FindLcAttribute (char *lcname, legoOp *op)
{
  return FindLcAttribute (lcname, (void *) op, 0);
} // end FindLcAttribute (op)

attrs *
FindLcAttribute (char *lcname, opEdges *edge)
{
  return FindLcAttribute (lcname, (void *) edge, 2);
} // end FindLcAttribute (edge);

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

/*
 * FindLiveAttribute
 *   edge = edge within which to search
 *   returns: live attribute, or NULL if not listed
 *
 * Returns the live attribute associated with edge.
 */
attrs *
FindLiveAttribute (opEdges *edge)
{
  attrList *atl;

  for (atl = edge->GetEdgeAttrListPtr(); atl != NULL;
       atl = atl->GetNextListPtr())
    if (atl->GetAttrType() == ATTR_LIVE)
      return atl->GetAttrPtr();

   return NULL;
} // end FindLiveAttribute

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

/*
 * FindFreqAttribute
 *   edge = edge within which to search
 *   returns: frequency attribute, or NULL if not listed
 *
 * Returns the frequency attribute associated with edge.
 */
attrList *
FindFreqAttribute (opEdges *edge)
{
  attrList *atl;

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

  return NULL;
} // end FindFreqAttribute

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

/*
 * FindEdgeFrequency
 *   edge = edge within which to search
 *   returns: edge frequency, or -1 if not listed
 *
 * Returns the frequency of an edge (freq attribute), or -1 if the
 * attribute is not present.
 */
int
FindEdgeFrequency (opEdges *edge)
{
  attrList *atl;

  if (edge == NULL) return -1;

  atl = FindFreqAttribute (edge);
  if (atl == NULL) return -1;

  return atl->GetAttrValPtr()->GetAttrValue();
} // end FindEdgeFrequency

/*
 * FindOpWeight
 *   op = op for which to get weight
 *   returns: true execution frequency of op, -1.0 if an error occurs
 *
 * Returns the true execution frequency of an op. In a basic block this
 * is the same as the basic block's weight, but for a superblock or
 * hyperblock it may be less due to side exits above the op.
 */
double
FindOpWeight (legoOp *op)
{
  legoRegion *pregion;
  legoOp *blockop, *prevblockop;
  opList *opl;
  attrs *a; 
  
  if (op == NULL)
    {
      LegoNonFatal ("FindOpWeight", "Passed NULL op.");
      return -1.0;
    } // end if
  pregion = (legoRegion *) op->GetParentBlockPtr();

  // Am I in a basic block? If so, return the block's weight.
  if (pregion->GetRegionType() == RT_BB)
    return pregion->GetWeight();
  // Am I at the top of the block? If so, return the block's weight.
  if (op->GetPrevLink() == NULL)
    return pregion->GetWeight();

  // If IfConvertHammock or IfConvertTreeBranch was used, use the "orig_wt" 
  // attribute that was added to each op
  if ((pregion->GetRegionType() == RT_HB) && 
      (FindLcAttribute( "use_orig_wt",  pregion) != NULL )) {
    // I want the error here if orig_wt not available (it should be)
    a = FindLcAttribute( "orig_wt", op ) ;
    return (a->GetAttrOprdPtr()->GetLiteralDouble());
  }

  // Walk backwards to the last branch or the top of the block,
  // whichever comes first.
  prevblockop = op;
  blockop = op->GetPrevLink();
  while (blockop->GetOutListPtr() == NULL && blockop->GetPrevLink() != NULL)
    {
      //       (m->TinkerOptype (blockop) != BR_OP || blockop->GetOpcode() == BRL
      //        || blockop->GetOpcode() == C_MERGE) &&

      prevblockop = blockop;
      blockop = blockop->GetPrevLink();
    } // end while
  dprintf ((OUTF, "Stopped walk at op %d, before op %d.\n",
            blockop->GetOpId(), prevblockop->GetOpId()));

  //  if (m->TinkerOptype (blockop) == BR_OP && blockop->GetOpcode() != C_MERGE
  //      && blockop->GetOpcode() != BRL)
  if (blockop->GetOutListPtr() != NULL)
    {  // found branch - get weight of opList pointing into block
      for (opl = blockop->GetOutListPtr(); opl != NULL;
           opl = opl->GetNextListPtr())
        if (opl->GetOpId() == prevblockop->GetOpId())
          {
            dprintf ((OUTF, "Found fall-through weight %lf.\n",
                      opl->GetWeight()));
            return opl->GetWeight();
          } // end if (, for)
      if (opl == NULL)
        LegoNonFatal ("FindOpWeight", "Can't find opList from op %d to "
                      "op %d.", blockop->GetOpId(), prevblockop->GetOpId());
    } // end if
  else  // hit top of block - use block weight
    {
      dprintf ((OUTF, "Hit top - using weight %lf.\n", pregion->GetWeight()));
      return pregion->GetWeight();
    }
  return -1.0;
} // end FindOpWeight

/*
 * FindReturnMacro
 *   op = BRL operation
 *   returns: macro defined by return from function call, NULL if error
 *     or no return value
 *
 * Returns a pointer to the macro that holds the return value from a
 * function call operation (BRL). If op is not a BRL, NULL is returned. If
 * op has no return value, NULL is returned as well.
 */
legoOprd *
FindReturnMacro (legoOp *op)
{
  attrs *retattr;

  if (op->IsBRLOp() == false)
    {
      LegoNonFatal ("FindReturnMacro", "Op %d not a BRL.", op->GetOpId());
      return NULL;
    } // end if

  retattr = FindLcAttribute ("ret", op);
  if (retattr == NULL) return NULL;

  return retattr->GetAttrOprdPtr();
} // end FindReturnMacro

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

/*
 * FindFlag
 *   name = flag name to find
 *   flagiter/op/region = set of flags/op/region in which to search
 *   returns: flag if found, NULL otherwise
 *
 * Searches a set of flags / an op's flags / a region's flags for
 * a given flag.
 */
flags *
FindFlag (int name, flags *flagiter)
{
  flags *f = flagiter;

  for ( ; f != NULL; f = f->GetNextFlagPtr())
    if (f->GetFlagName() == name) return f;

  return NULL;   
} // end FindFlag (flags *)

flags *
FindFlag (int name, legoOp *op)
{
  return FindFlag (name, op->GetOpFlagPtr());
} // end FindFlag (op)

flags *
FindFlag (int name, legoRegion *region)
{
  return FindFlag (name, region->GetFlagPtr());
} // end FindFlag (region)

flags *
FindFlag (flags *flagiter, int name)
{
  LegoNonFatal ("FindFlag", "This is a deprecated version of this function.\n"
                "Swap the parameters in the call.");

  return FindFlag (name, flagiter);
}

flags *
FindFlag (legoOp *op, int name)
{
  LegoNonFatal ("FindFlag", "This is a deprecated version of this function.\n"
                "Swap the parameters in the call.");

  return FindFlag (name, op);
}

flags *
FindFlag (legoRegion *region, int name)
{
  LegoNonFatal ("FindFlag", "This is a deprecated version of this function.\n"
                "Swap the parameters in the call.");

  return FindFlag (name, region);
}

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

/*
 * Is????Op
 *   op = op to check
 *   returns: 1 if op is of specified type, 0 otherwise
 *
 * Returns true (1) if op is of a certain classification, and false (0)
 * otherwise. The classifications correspond to functional units: an
 * integer op is executed on an integer unit, while a load is executed
 * on a load (or memory) unit. [Note that comparison opcodes are
 * classified both as compares and as either integer or float ops as well.]
 */

static inline int in_range (int x, int a, int b)
{
  return (x >= a && x <= b);
} // end in_range

int IsIntegerOp (legoOp *op)
{
    return op->IsIntegerOp();
} // end IsIntegerOp

int IsFloatOp (legoOp *op)
{
    return op->IsFloatOp();
} // end IsFloatOp

int IsCompareOp (legoOp *op)
{
    return op->IsCompareOp();
} // end IsCompareOp

int IsBranchOp (legoOp *op)
{
    return op->IsBranchOp();
} // end IsBranchOp

int IsBranchOpButNotBRL (legoOp *op)
{
    return op->IsBranchOpButNotBRL();
} // end IsBranchOpButNotBRL

int IsLoadOp (legoOp *op)
{
    return op->IsLDOp();
} // end IsLoadOp

int IsStoreOp (legoOp *op)
{
    return op->IsSTOp();
} // end IsStoreOp

int IsMemoryOp (legoOp *op)
{
    return (op->IsLDOp() || op->IsSTOp());
} // end IsMemoryOp


//HZ:
//Utility function find_op
//Find the legop ptr to the op with the id in the region
legoOp * find_op(legoRegion * region, int opid)
{
    int i;
    legoOp *op1 = NULL;
    switch(region->GetRegionType())
    {
        case RT_PROC:
        {
                for(i = 0; i < region->GetCount(); i++)
                {
                    op1 = find_op((legoRegion *) region->GetItem(i), opid);
                    if(op1 != NULL)
                        break;
                }
                return op1;
                break;
        }
        case RT_TREE:
        {
                for(i = 0; i < region->GetCount(); i++)
                {
                    op1 = find_op((legoRegion *) region->GetItem(i), opid);
                    if(op1 != NULL)
                        break;
                }
                return op1;
                break;
        }
        case RT_HB:
        case RT_SB:
        case RT_BB:
        {
                for(i = 0; i < region->GetCount(); i++)
                {
                    legoOp * op_ptr = (legoOp *) region->GetItem(i);
                    if(op_ptr->GetOpId() == opid)
                    {
                        op1 = op_ptr;
                        break;
                    }
                }
                return op1;
                break;
        }
        
    }
    return op1;
}

bool SameOpcode(legoOp *op1, legoOp *op2)
{
    if(op1->GetOpcodePtr() == NULL || op2->GetOpcodePtr() == NULL)
        return (op1->GetOpcode() == op2->GetOpcode());
    else
    {
        legoOpcode *opc1, *opc2;
        opc1 = op1->GetOpcodePtr();
        opc2 = op2->GetOpcodePtr();
        if(opc1->GetOpcodeClass() == opc2->GetOpcodeClass() &&
                opc1->GetBaseOpcode() == opc2->GetBaseOpcode() ) 
        {
            switch (opc1->GetOpcodeClass())
            {
                case OC_INT:
                        return (opc1->GetIaluQuals() == opc2->GetIaluQuals());
                        break;
                case OC_PINT:
                        return (opc1->GetIsimdQuals() == opc2->GetIsimdQuals());
                        break;
                case OC_FP:
                        return (opc1->GetFaluQuals() == opc2->GetFaluQuals());
                        break;
                case OC_PFP:
                        return (opc1->GetFsimdQuals() == opc2->GetFsimdQuals());
                        break;
                case OC_CMP:
                        return (opc1->GetIcmpQuals() == opc2->GetIcmpQuals());
                        break;
                case OC_FCMP:
                        return (opc1->GetFcmpQuals() == opc2->GetFcmpQuals());
                        break;
                case OC_BR:
                        return (opc1->GetBranchQuals() ==
                        opc2->GetBranchQuals());
                        break;
                case OC_LDST:
                        return (opc1->GetImemQuals() == opc2->GetImemQuals());
                        break;
                case OC_FPLDST:
                        return (opc1->GetFmemQuals() == opc2->GetFmemQuals());
                        break;
                case OC_MISC:
                        return (opc1->GetMiscQuals() == opc2->GetMiscQuals());
                        break;
                default:
                        return true;
                        break;
            }
        }
        else
            return false;
    }
}

//HZ: Testing the legoModule CFG constructions.
//Testing methodology:
//For each function:
//  0. the start op is C_MERGE
//  1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
//  2. entry/exit edges should be NULL
//  3. region type
//  4. parentPtr should be the legoModule
//  5. parents & children ptr should be NULL
//  6. allListPtr is set
//For each subregion of proc:
//  If the region type is BB:
//    0. the start op is C_MERGE
//    1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
//                one op for each for BB
//    2. entry/exit edges should be set correctly (see step 5)
//    3. region type
//    4. parentPtr should be set
//    5. parents & children ptr should be set correctly (by checking the entry
//       edges and exit edges)
//    6. allListPtr should be NULL
//  If the region type is Treegion:
//    0. the start op is C_MERGE
//    1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
//                one op for each for BB
//    2. entry/exit edges should be set correctly (see step 5)
//    3. region type
//    4. parentPtr should be set (Proc)
//    5. parents & children ptr should be set correctly (by checking the entry
//       edges and exit edges)
//    6. allListPtr should set
//For each op in the BB
//    1. if the op is not the entry op or exit op of a region
//          Make sure there is no in edge or out op list
//    2. if the op is the entry op (i.e., C_MERGE),
//          check the in_edges are set correctly (using the entry edge of the
//          parent BB).
//    3. if the op is an exit op (i.e., BR, DUMMYBR, or RTS, also it should be the
//          last op of the parent BB and vise versa), check the Out Op list is
//          set correctly (using the exit edge of the parent BB)
//    4. make sure the prevOpPtr and nextOpPtr are set correctly for each op
//
// Functionality test:
//  1. add ops, remove ops
//  2. duplicate regions
//  3. tree form
//  4. schedule ...
bool legoAudit(legoModule * Module)
{
    int i;
    if(Module->GetCount() == 0)
    {
        fprintf(stderr, "legoAudit: warning Empty lego module.\n");
        return true;
    }
    for(i = 0; i < Module->GetCount(); i++)
    {
        legoProc * proc = (legoProc *) Module->GetItem(i);
        //For each function:
        //  0. the start op is C_MERGE
        assert(proc->GetEntryOpsPtr() != NULL);
        legoOp * entry_op = proc->GetEntryOpsPtr()->GetOpPtr();
        assert(entry_op->IsCMERGEOp() == true);
        //  1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
        if(proc->GetExitOpsPtr() == NULL)
        {
            fprintf(stderr, "Warning: there seems to be no ret from the proc %s.\n",
                    proc->GetProcName());
        }
        //assert(proc->GetExitOpsPtr() != NULL);
        //  2. entry/exit edges should be NULL
        assert(proc->GetInEdgesPtr()->GetEdgePtr() == NULL);
        assert(proc->GetOutEdgesPtr()->GetEdgePtr() == NULL);
        //  3. region type
        assert(proc->GetRegionType() == RT_PROC);
        //  4. parentPtr should be the legoModule
        assert(proc->GetParentPtr() == Module);
        //  5. parents & children ptr should be NULL
        assert(proc->GetParents() == NULL);
        assert(proc->GetChildren() == NULL);
        //  6. allListPtr is set
        assert(proc->GetListOpPtr() != NULL);
        
        int j;
        for(j = 0; j < proc->GetCount(); j++)
        {
            legoRegion * region = (legoRegion *) proc->GetItem(j);
            if(region->GetRegionType() == RT_BB)
            {           
                //For each subregion of proc:
                //  If the region type is BB:
                //    0. the start op is C_MERGE
                legoOp * bb_entry_op = (legoOp *)
                        region->GetEntryOpsPtr()->GetOpPtr();
                assert(bb_entry_op->IsCMERGEOp() == true);
                //    1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
                //                one op for each for BB
                //assert(bb_entry_op == region->GetEntryOpsPtr()->GetOpPtr());
                assert(region->GetEntryOpsPtr()->GetNextListPtr() == NULL);
                
                assert(region->GetExitOpsPtr()->GetNextListPtr() == NULL);              
                //assert(region->GetExitOpsPtr()->GetOpPtr() == region->GetItem(region->GetCount() - 1));

                //    2. entry/exit edges should be set correctly (see step 5)
                //       make sure the edges correspoond to the parents / children of the BB
                edgeList * bb_in_edges, * bb_out_edges;
                bb_in_edges = region->GetInEdgesPtr();
                bb_out_edges = region->GetOutEdgesPtr();
                if(j != 0) //begining of the proc
                {
                    if(bb_in_edges == NULL)
                        bb_in_edges = NULL;                 
                    assert(bb_in_edges->GetEdgePtr() != NULL);
                }
                if(bb_in_edges != NULL && bb_in_edges->GetEdgePtr() != NULL)
                {
                    opEdges * edgep;
                    for(; bb_in_edges != NULL; bb_in_edges =
                        bb_in_edges->GetNextListPtr())
                    {
                        edgep = bb_in_edges->GetEdgePtr();
                        assert(edgep->GetFromOpId() ==
                            edgep->GetFromOpPtr()->GetOpId());
                        assert(edgep->GetToOpId() ==
                            edgep->GetToOpPtr()->GetOpId());
                        assert(edgep->GetToOpPtr() == bb_entry_op);
                        int parent_chk = false;
                        regionList *pars;
                        legoRegion *par;
                        for(pars = region->GetParents(); pars != NULL;
                            pars = pars->GetNextListPtr())
                        {
                            par = pars->GetRegionPtr();
                            if(edgep->GetFromOpPtr()->GetParentBlockPtr() == par)
                            {
                                parent_chk = true;
                                break;
                            }
                        }
                        assert(parent_chk == true);                             
                    }
                }
                bool exitBB = false; //exit BB of a proc
                opList * exit_opl = proc->GetExitOpsPtr();
                for(; exit_opl != NULL; exit_opl = exit_opl->GetNextListPtr())
                {
                    
                    if((exit_opl->GetOpPtr() != 0) && (exit_opl->GetOpPtr()->GetParentBlockPtr() == region))
                    {
                        exitBB = true;
                        break;
                    }
                    
                }
                //opList *exit_BB_opl = region->GetExitOpsPtr();
                //for(; exit_BB_opl != NULL; exit_BB_opl = exit_BB_opl->GetNextListPtr())
                //{
                    
                  //  attrs *a = FindLcAttribute("indirect_form", 
                  //            (legoOp *)exit_BB_opl->GetOpPtr());
                  //  if(!a) continue;
                    
                  //  exitBB = true;
                  //  break;    
                //}
                if(exitBB == false) //last of the proc
                {
                    if(bb_out_edges != NULL)
                        assert(bb_out_edges->GetEdgePtr() != NULL);
                }
                if(bb_out_edges != NULL && bb_out_edges->GetEdgePtr() != NULL)
                {
                    
                    opEdges * edgep;
                    for(; bb_out_edges != NULL; bb_out_edges =
                        bb_out_edges->GetNextListPtr())
                    {
                        edgep = bb_out_edges->GetEdgePtr();
                        assert(edgep->GetFromOpId() ==
                            edgep->GetFromOpPtr()->GetOpId());
                        assert(edgep->GetToOpId() ==
                            edgep->GetToOpPtr()->GetOpId());
                        assert(edgep->GetFromOpPtr() == region->GetExitOpsPtr()->GetOpPtr());
                        int child_chk = false;
                        legoRegion *chd;
                        regionList * chdren;
                        for(chdren = region->GetChildren(); chdren != NULL;
                            chdren = chdren->GetNextListPtr())
                        {
                            chd = chdren->GetRegionPtr();
                            if(edgep->GetToOpPtr()->GetParentBlockPtr() == chd)
                            {
                                child_chk = true;
                                break;
                            }
                        }
                        assert(child_chk == true);                              
                    }
                }
                
                //    3. region type
                
                //    4. parentPtr should be set
                assert(region->GetParentPtr() != NULL);
                //    5. parents & children ptr should be set correctly (by checking the entry
                //       edges and exit edges) 
                regionList * reg_l;
                for(reg_l = region->GetParents(); reg_l != NULL; reg_l =
                        reg_l->GetNextListPtr())
                {
                    legoRegion * reg1 = reg_l->GetRegionPtr();
                    bool inedge_chk = false;
                    edgeList * edge_l;
                    for(edge_l = region->GetInEdgesPtr(); edge_l != NULL; edge_l =
                            edge_l->GetNextListPtr())
                    {
                        if(edge_l->GetEdgePtr()->GetFromOpPtr()->GetParentBlockPtr() == reg1)
                        {
                            inedge_chk = true;
                            break;
                        }
                    }
                    assert(inedge_chk == true);
                }
                for(reg_l = region->GetChildren(); reg_l != NULL; reg_l =
                        reg_l->GetNextListPtr())
                {
                    legoRegion * reg1 = reg_l->GetRegionPtr();
                    bool outedge_chk = false;
                    edgeList * edge_l;
                    for(edge_l = region->GetOutEdgesPtr(); edge_l != NULL; edge_l =
                            edge_l->GetNextListPtr())
                    {
                        if(edge_l->GetEdgePtr()->GetToOpPtr()->GetParentBlockPtr() == reg1)
                        {
                            outedge_chk = true;
                            break;
                        }
                    }
                    assert(outedge_chk == true);
                }
                
                
                //    6. allListPtr should be NULL
                assert(region->GetListOpPtr() == NULL);
                
                //op level checking 
                int k;
                for(legoOp * op = region->GetEntryOpsPtr()->GetOpPtr(); 
                        op != NULL; op = op->GetNextLink())
                //              k = 0; k < region->GetCount(); k++)
                {
                    //legoOp *op = (legoOp *) region->GetItem(k);
                    //For each op in the BB
                    //    1. if the op is not the entry op or exit op of a region
                    //          Make sure there is no in edge or out op list
                    if(op != region->GetEntryOpsPtr()->GetOpPtr()) //(k != 0) 
                        assert(op->GetInListPtr() == NULL);
                    if(op->GetNextLink() != NULL) //k != region->GetCount() - 1)
                    {
                        assert(op->GetOutListPtr() == NULL);
                        assert(op->IsRETOp() == false && op->IsBRUOp() == false
                                && op->IsBRCONDOp() == false &&
                                op->IsDUMMYBROp() == false);
                    }
                    //    2. if the op is the entry op (i.e., C_MERGE),
                    //          check the in_edges are set correctly (using the entry edge of the
                    //          parent BB).
                    if(op == region->GetEntryOpsPtr()->GetOpPtr()) //k == 0) //entry op
                    {
                        assert(op->IsCMERGEOp() == true);
                        int num_entry_edges = 0;
                        int num_in_ops = 0;
                        edgeList * in_edges;
                        for(in_edges = ((legoRegion *) op->GetParentBlockPtr())->GetInEdgesPtr();
                                    in_edges != NULL; in_edges = in_edges->GetNextListPtr())
                        {
                            if(in_edges->GetEdgePtr() != NULL)
                                num_entry_edges++;
                        }
                        opList * ops;
                        for(ops = op->GetInListPtr(); ops != NULL; ops = ops->GetNextListPtr())
                        {
                            if(ops->GetOpPtr() != NULL)
                                num_in_ops++;
                        }
                        assert(num_in_ops == num_entry_edges);
                        
                        if(region->GetInEdgesPtr() == NULL || region->GetInEdgesPtr()->GetEdgePtr() == NULL)
                            assert(op->GetInListPtr() == NULL || op->GetInListPtr()->GetOpPtr() == NULL);
                        if(region->GetInEdgesPtr() != NULL && region->GetInEdgesPtr()->GetEdgePtr() != NULL)
                        {
                            assert(op->GetInListPtr()->GetOpPtr() != NULL);
                            opEdges * edgep;
                            edgeList *inedges;
                            for(inedges = region->GetInEdgesPtr(); inedges != NULL; inedges =
                                 inedges->GetNextListPtr())
                            {
                                edgep = inedges->GetEdgePtr();
                                legoOp * from_op = edgep->GetFromOpPtr();
                                bool from_op_chk = false;
                                for(opList * op_l = op->GetInListPtr(); op_l !=
                                        NULL; op_l = op_l->GetNextListPtr())
                                {
                                    if(from_op == op_l->GetOpPtr())
                                    {
                                        from_op_chk = true;
                                        break;
                                    }
                                    if(from_op != op_l->GetOpPtr() &&
                                        from_op->GetOpId() == op_l->GetOpId())
                                    {
                                        from_op_chk = true;
                                        fprintf(stderr, "legoAudit Warning: Proc name: %s BB %d\n", proc->GetProcName(), region->GetRegionId());
                                        fprintf(stderr, " The ops in the parent BB of this BB may have been changed using \
AddItem, AddMidOp, etc. (add/remove op) functions.\n");
                                        fprintf(stderr, " Try with write Module out and re-load it in. Then Audit it.\n");  
                                        fprintf(stderr, " The reason is that those functions may change the op_ptr in one BB\
while the related oplist keeps the op_ptr when it is constructed.\n");
                                    }
                                }
                                assert(from_op_chk == true);
                            }
                        }                   
                    } //entry_op
                    
                    //    3. if the op is an exit op (i.e., BR, DUMMYBR, or RTS, also it should be the
                    //          last op of the parent BB and vise versa), check the Out Op list is
                    //          set correctly (using the exit edge of the parent BB)                
                    if(op->GetNextLink() == NULL) //k == region->GetCount() - 1) //exit op
                    {
                        if(!op->IsBRLOp()) //as the proc may end with br.call exit
                            assert(op->IsDUMMYBROp() || op->IsBRUOp() || op->IsBRCONDOp() ||
                                op->IsRETOp() || op->IsBreakOp());
                        if(op->IsRETOp())
                        {
                            int num_exit_edges = 0;
                            int num_out_ops = 0;
                            edgeList * out_edges;
                            for(out_edges = ((legoRegion *) op->GetParentBlockPtr())->GetOutEdgesPtr();
                                    out_edges != NULL; out_edges = out_edges->GetNextListPtr())
                            {
                                if(out_edges->GetEdgePtr() != NULL)
                                    num_exit_edges++;
                            }
                            opList * ops;
                            for(ops = op->GetOutListPtr(); ops != NULL; ops = ops->GetNextListPtr())
                            {
                                if(ops->GetOpPtr() != NULL)
                                    num_out_ops++;
                            }
                            assert(num_out_ops == num_exit_edges);
                            if(op->GetPredOprdPtr() == NULL)
                                assert(num_out_ops == 0);
                            else if(op->GetPredOprdPtr()->GetOprdType() !=
                                OT_REG)
                                assert(num_out_ops == 0);
                        }
                        if(op->IsDUMMYBROp() || op->IsBRUOp())
                        {
                            int num_exit_edges = 0;
                            int num_out_ops = 0;
                            edgeList * out_edges;
                            
                            // We need to add the information here
                            for(out_edges = ((legoRegion *) op->GetParentBlockPtr())->GetOutEdgesPtr();
                                    out_edges != NULL; out_edges = out_edges->GetNextListPtr())
                            {
                                if(out_edges->GetEdgePtr() != NULL)
                                    num_exit_edges++;
                            }
                            opList * ops;
                            for(ops = op->GetOutListPtr(); ops != NULL; ops = ops->GetNextListPtr())
                            {
                                if(ops->GetOpPtr() != NULL)
                                    num_out_ops++;
                            }
                            assert(num_out_ops == num_exit_edges);
                            attrList *atl;
                            bool jump_table = false; //switch case structure
                            for(atl = op->GetOpAttrListPtr(); atl != NULL; atl =
                                    atl->GetNextListPtr())
                            {
                                if(atl->GetAttrType() == ATTR_TBLNAME)
                                    jump_table = true;
                            }
                            assert(num_out_ops >= 1);
                            if(num_out_ops > 1 && jump_table == false)
                            {
                                fprintf(stderr, "legoAudit WARNING: op %d in proc %s may have too many out ops (%d). \n",
                                        op->GetOpId(), proc->GetProcName(), num_out_ops);
                            }                       
                        }
                        if(op->IsBRCONDOp())
                        {
                            int num_exit_edges = 0;
                            int num_out_ops = 0;
                            edgeList * out_edges;
                            for(out_edges = ((legoRegion *) op->GetParentBlockPtr())->GetOutEdgesPtr();
                                    out_edges != NULL; out_edges = out_edges->GetNextListPtr())
                            {
                                if(out_edges->GetEdgePtr() != NULL)
                                    num_exit_edges++;
                            }
                            opList * ops;
                            for(ops = op->GetOutListPtr(); ops != NULL; ops = ops->GetNextListPtr())
                            {
                                if(ops->GetOpPtr() != NULL)
                                    num_out_ops++;
                            }
                            assert(num_out_ops == num_exit_edges);
                            assert(num_out_ops >= 2);
                            if(num_out_ops > 2)
                            {
                                fprintf(stderr, "legoAudit warning: op %d in proc %s may have too many out ops (%d).\n",
                                        op->GetOpId(), proc->GetProcName(), num_out_ops);
                            }                       
                        }
                        if(region->GetOutEdgesPtr() == NULL || region->GetOutEdgesPtr()->GetEdgePtr() == NULL)
                            assert(op->GetOutListPtr() == NULL || op->GetOutListPtr()->GetOpPtr() == NULL);
                        if(region->GetOutEdgesPtr() != NULL && region->GetOutEdgesPtr()->GetEdgePtr() != NULL)
                        {
                            assert(op->GetOutListPtr()->GetOpPtr() != NULL);
                            opEdges * edgep;
                            edgeList * outedges;
                            for(outedges = region->GetOutEdgesPtr(); outedges != NULL; outedges =
                                 outedges->GetNextListPtr())
                            {
                                edgep = outedges->GetEdgePtr();
                                legoOp * to_op = edgep->GetToOpPtr();
                                bool to_op_chk = false;
                                for(opList * op_l = op->GetOutListPtr(); op_l !=
                                        NULL; op_l = op_l->GetNextListPtr())
                                {
                                    if(to_op == op_l->GetOpPtr())
                                    {
                                        to_op_chk = true;
                                        break;
                                    }
                                    if(to_op != op_l->GetOpPtr() &&
                                        to_op->GetOpId() == op_l->GetOpId())
                                    {
                                        to_op_chk = true;
                                        fprintf(stderr, "legoAudit Warning: Proc name: %s BB %d\n", proc->GetProcName(), region->GetRegionId());
                                        fprintf(stderr, " The ops in the child BB of this BB may have been changed using \
AddItem, AddMidOp, etc. (add/remove op)functions.\n");
                                        fprintf(stderr, " Try with write Module out and re-load it in. Then Audit it.\n");  
                                        fprintf(stderr, " The reason is that those functions may change the op_ptr in one BB\
while the related oplist keeps the op_ptr when it is constructed.\n");
                                    }
                                    
                                }
                                assert(to_op_chk == true);
                            }
                        }
                    }//exit op
                    
                    //    4. make sure the prevOpPtr and nextOpPtr are set correctly for each op. also check those control
                    //       relationship appear in the edge dictionary
                    if(op != region->GetEntryOpsPtr()->GetOpPtr())
                    {
                         assert(op->GetPrevLink() != NULL);
                         assert(FindControlEdge(op->GetPrevLink(), op) != NULL);
                    }
                    else
                    {
                         assert(op->GetPrevLink() == NULL);
                        //may be multiple edges pointing to it. But the entry edges checking should take care of it
                    }
                    opList * opl1;
                    bool proc_exit = false;
                    for(opl1 = region->GetExitOpsPtr(); opl1 != NULL; opl1 =
                            opl1->GetNextListPtr())
                    {
                        if(op == opl1->GetOpPtr())
                        {
                            proc_exit = true;
                            break;
                        }
                    }
                    if(proc_exit == false)
                    {
                        assert(op->GetNextLink() != NULL);
                        assert(FindControlEdge(op, op->GetNextLink()) != NULL);
                    }
                    else 
                    {
                        assert(op->GetNextLink() == NULL);                                                  
                        //there may be multiple control edges from this op. But the exit edges checking should take care of
                        //it.
                    }
                    
                    //    5. Make sure each op appeared at least in one control edges
                    //       For CMERGE op, it may be to_op of N (>=0) edges
                    //       For proc exit ops including RTS ops, it may be to_op of 1 edge and from op of 0 edge.
                    //       For BRCOND op, it may be to_op of 1 edge and from_op of 2 edges
                    //       For other ops, it should be to_op of 1 edge and from_op of 1 edge.
                }//op level
            }//BB level
            if(region->GetRegionType() == RT_TREE)
            {
                //  If the region type is Treegion:
                //    0. the start op is C_MERGE
                //    1. entry/exit op list - of format opList *entryOpsPtr and *exitOpsPtr
                //                one op for each for BB
                //    2. entry/exit edges should be set correctly (see step 5)
                //    3. region type
                //    4. parentPtr should be set (Proc)
                //    5. parents & children ptr should be set correctly (by checking the entry
                //       edges and exit edges)
                //    6. allListPtr should set
                fprintf(stderr, "legoAudit: treegions have not been tested.\n");

            } //treegion level
        }//region level
        
        //check control edges
        opEdges * edge;
                
        for(edge = proc->GetEdgeDictionary(); edge != NULL; edge =
                        edge->GetNextOpEdgePtr())
        {
            int from_op_id = edge->GetFromOpId();
            int to_op_id = edge->GetToOpId();
            legoOp * from_op, *to_op;
            from_op = find_op(proc, from_op_id); 
            assert(from_op != NULL);
            //this fromop may not be same as edge->GetFromOpPtr()
            // due to the addItem() addMidOps function calls/
            //So here we take a conservative approach
            to_op = find_op(proc, to_op_id);
            assert(to_op != NULL);
            if(((legoRegion *)from_op->GetParentBlockPtr())->GetRegionId() != 
                        ((legoRegion *)to_op->GetParentBlockPtr())->GetRegionId() )
            {
                //inter block edges: check the Freq Attr
                assert(edge->GetEdgeAttrListPtr() != NULL);
                //also make sure this edge appears in entry edges and exit edges
                edgeList * in_edges = ((legoRegion *)to_op->GetParentBlockPtr())->GetInEdgesPtr();
                bool ck_edges = false;
                for(; in_edges != NULL; in_edges = in_edges->GetNextListPtr())
                {
                    if(edge == in_edges->GetEdgePtr())
                    {
                        ck_edges = true;
                        break;
                    }
                }
                if(ck_edges == false)
                {
                    ck_edges = false;
                }
                assert(ck_edges == true);
                ck_edges = false;
                edgeList * out_edges = ((legoRegion *)from_op->GetParentBlockPtr())->GetOutEdgesPtr();
                for(; out_edges != NULL; out_edges = out_edges->GetNextListPtr())
                {
                    if(edge == out_edges->GetEdgePtr())
                    {
                        ck_edges = true;
                        break;
                    }
                }
                assert(ck_edges == true);
            }
        }
        
        //check  the listOpPtr of the proc and the ops
        legoOp * allList;
        int op_count1 = 0;
        for(allList=proc->GetListOpPtr();allList!=NULL;allList = allList->GetListOpPtr())
        {
            op_count1++;
        }
        int op_count2 = 0;
        for(int rc = 0; rc < proc->GetCount(); rc++)
        {
            op_count2 += ((legoRegion *)proc->GetItem(rc))->GetCount();
        }
        assert(op_count1 == op_count2);
        
    }//proc level
    
    
    //functionality test
    
    return true;
}

int FindFirstOutGoingReg(legoProc *Proc)
{
        legoRegion *Region;
        legoOp *op;
        legoOprd *src;
        
        int Reg = 31;
        
        op = Proc->GetEntryOpsPtr()->GetOpPtr(); //C_MERGE op
        op = op->GetNextLink(); //this one should be the alloc if there is one
        
        //go through the first BB as scheduling may change its position although
        // it should be scheduled right after the C_MERGE
        for(; op != NULL; op = op->GetNextLink())
        {
            if(op->IsAllocOp())
                break;
        }
        
        if(op == NULL || !op->IsAllocOp())
        {
                LegoNonFatal ("FindFirstOutGoingReg", "This Proc %s has no alloc instruction.\n",
                        Proc->GetProcName());           
                return (-1); 
        }
        
        src = op->GetSrcOprdPtr();
        
        // Now point towards the number of incoming
        // regs.
        src = src->GetNextOprdPtr();
        Reg = Reg + src->GetLiteralLongLong();
        
        // Now point towards the number of locals
        src = src->GetNextOprdPtr();
        Reg = Reg + src->GetLiteralLongLong();
        
        // Here the (Reg + 1) will be having the starting 
        // o/p register, so return it.
        
        return (Reg + 1); 
        
} 

int FindLastOutGoingReg(legoProc *Proc)
{
        legoRegion *Region;
        legoOp *op;
        legoOprd *src;
        
        int Reg = 31;
        
        op = Proc->GetEntryOpsPtr()->GetOpPtr(); //C_MERGE op
        op = op->GetNextLink(); //this one should be the alloc if there is one
        
        
        //go through the first BB as scheduling may change its position although
        // it should be scheduled right after the C_MERGE
        for(; op != NULL; op = op->GetNextLink())
        {
            if(op->IsAllocOp())
                break;
        }
        
        if(op == NULL || !op->IsAllocOp())
        {
                LegoNonFatal ("FindLastOutGoingReg", "This Proc %s has no alloc instruction.\n",
                        Proc->GetProcName());           
                return (-2); 
        }
        
        src = op->GetSrcOprdPtr();
        
        // Now point towards the number of incoming
        // regs.
        src = src->GetNextOprdPtr();
        Reg = Reg + src->GetLiteralLongLong();
        
        // Now point towards the number of locals
        src = src->GetNextOprdPtr();
        Reg = Reg + src->GetLiteralLongLong();
        
        // Now point towards the number of outgoing Regs
        src = src->GetNextOprdPtr();
        Reg = Reg + src->GetLiteralLongLong();
        
        // Here the (Reg) will be having the ending 
        // o/p register, so return it.
        
        return (Reg); 
        
} 

---