dag.C

Go to the documentation of this file.

// dag.C
//
// 2/11/98 WAH:  Broke away from Scheduler package; minor patching up;
//               disabled PrintGraphicDag.
// 3/23/98 WAH:  Added call to RemoveUndefPredecessors.
// 3/30/98 WAH:  Removed bad destructor calls.
// 4/2/98 WAH:   Removed all explicit destructor calls; blew away old
// 11/20/98 MDJ: Fixed memory leak associated with WriteHashKeys. Need to 
//               delete the WriteHashKeys we allocated before erasing HashTable
//               PrintGraphicDag code.

#include <iostream.h>
#include <fstream.h>
#include "legoUtil.H"
#include "legoMach.H"
#include "dag.H"
#include "bitvector.H"

/* Open issues:

1) The dependencies for the very last Op in a Lego basic block are initially
   set but later lost.
   Work around: Dependencies are visible after the STL _list_ is copied to a
                vector.

2) DAG building crashes in non-debug mode.
   Work around: Have debug mode write its output to /dev/null.
   3/19/98 WAH:  This has been taken care of (sort of) - see the anecdote
                 in dag_dependency.C.

3) Predication is not accounted for when determining dependencies between
   Ops.
*/

/* Debugging support, courtesy of Sumedh */
//#define _SHOW_VECTORS_
//#define _DAG_DEBUG_
//#define ddderr(s)  cerr << s
#define ddderr(s)  
//#define dderr(s)  cerr << s
#define dderr(s)  
#if defined (_DAG_DEBUG_)
   #define derr(s)  cerr << s
#else
   #define derr(s)  
#endif

// #define _STL_SORTING_

// wah 3/24/98 in macros, changed ??.BigListElement() to ?? = BigListElement()
#define PrepOpForInsertion(X,Y,Z)                       \
                (X) = BigListElement();                 \
                (X).SetOp( (Y) );                       \
                (X).SetWeight( (Z) );                   \
                (X).SetHeight( -1 );                    \
                (X).SetDepth( -1 )


#define SetClusterId(X,Y)                                       \
      if ( (A=FindLcAttribute( "clusterid", (X) )) != NULL ) {  \
         legoOprd *OprdPtr = A->GetAttrOprdPtr();               \
         (Y).ClusterId = OprdPtr->GetLiteralInteger();          \
      }


#define CorrectionCode()        Element = BigListElement();     \
                                Element.SetOp( NULL );          \
                                InsertOp( Element );            \
                                MasterList.pop_back()


static char *FunctionName;

#include "dag_utilities.C"              // Utility routines
#include "dag_dependency.C"             // Routines to detect dependencies
#include "dag_sort.C"                   // Comparsion routines for sorting

extern int MaxRegNum; 

/*
 * UpdateTreeTraversalRList
 * 
 */
void 
UpdateTreeTraversalRList (legoRegion *region)
{

  derr( ">> UpdateTreeTraversalRList\n" );

  regionList *treetraversalrl, *thisrl; 
  
  treetraversalrl = ((legoTreegion *)region->GetParentPtr())
    ->GetTreeTraversalRList();
  if (treetraversalrl != NULL) {
    for (;
         treetraversalrl->GetNextListPtr() != NULL;
         treetraversalrl = treetraversalrl->GetNextListPtr())
      ; // find the end of the list
  }

  // Add this region to the end
  thisrl = new regionList();
  thisrl->SetRegionPtr(region);
  
  if (treetraversalrl == NULL) {
    ((legoTreegion *)region->GetParentPtr())->SetTreeTraversalRList(thisrl);
  }
  else {
    treetraversalrl->SetNextListPtr(thisrl);
  }
  
}

// mdj 6/9/98 add attribute for tree-traversal treegion scheduling
/*
 * AddNextBlockAttribute
 *   op = op to annotate
 *   returns: new attr attached to op
 *
 * Attaches a new attr to the op with the ptr to the next block in 
 * the tree-traversal search used to ConstructTreeDag. The pointer 
 * will be used to determine which ops to mask out of the priority 
 * list for tree-traversal scheduling. Ops that are not "below" this 
 * block are not considered for scheduling
 * 
 */
static attrs *
AddNextBlockAttribute (legoRegion *region, int BlockPtr)
{
  legoOprd *oprd;
  attrs *wtattr;

  derr( ">> AddNextBlockAttribute\n" );

  oprd = new legoOprd;
  oprd->SetOprdType (OT_LITERAL_ULLNG);
  oprd->SetLiteralULongLong (BlockPtr);

  derr ("... adding next_block_int = " << BlockPtr << " to region id " 
        << region->GetRegionId() << "\n" );
  wtattr = AddLcAttribute ("next_block_int", oprd, region,
                           (legoProc *) FindParentRegionType (RT_PROC, region));
  return wtattr;

}

// PrintGraphicDag: shows the dag in a graphic manner
void dag::PrintGraphicDag( int print_control_edges )
{
  LegoNonFatal ("dag::PrintGraphicDag", "This function has been disabled.\n"
                "A new graph drawing routine, DrawDAG, is in the LEGO "
                "Analysis library.");
  return;
}



// PrintVectorDag:
void dag::PrintVectorDag( vector < BigListElement > *V )
{
   vector < BigListElement >::iterator Front, Back;

   for( Front = V->begin(), Back = V->end(); Front != Back; Front++ )
      (*Front).PrintElement();
}

//HZ: 08/29/00
void dag::PrintVectorDag( vector < BigListElement > *V, ofstream & os1)
{
   vector < BigListElement >::iterator Front, Back;

   for( Front = V->begin(), Back = V->end(); Front != Back; Front++ )
      (*Front).PrintElement(os1);
}



// PrintDag: prints only the MasterList portion of the DAG
void dag::PrintDag()
{
   BigListElement Element;
   MainList::iterator Front, Back;


   cerr << "\nPrinting the DAG\n----------------\n";

#if defined (_STL_LIST_USED_)
   if ( VectorActive == 1 ) {
      if ( Vector.size() == 0 ) {
         cerr << "*** Empty dag!! ***\n";
         return;
      }
      cerr << "   DAG has " << Vector.size() << " nodes\n";
      PrintVectorDag( &Vector );
      return;
   } // if
   else {
      if ( MasterList.size() == 0 ) {
         cerr << "*** Empty dag!! ***\n";
         return;
      }
      cerr << "   DAG has " << MasterList.size() << " nodes\n";
      for( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
           Front++ )
         (*Front).PrintElement();
   }
#else if defined (_STL_VECTOR_USED_)
   if ( MasterList.size() == 0 ) {
      cerr << "*** Empty dag!! ***\n";
      return;
   }
   cerr << "   DAG has " << MasterList.size() << " nodes\n";
   PrintVectorDag( &MasterList );
#endif
}

//HZ: 08/24/00
// PrintDag: prints only the MasterList portion of the DAG
void dag::PrintDag(ofstream & os1)
{
   BigListElement Element;
   MainList::iterator Front, Back;

   cerr << "\nPrinting the DAG\n----------------\n";

#if defined (_STL_LIST_USED_)
   if ( VectorActive == 1 ) {
      if ( Vector.size() == 0 ) {
         cerr << "*** Empty dag!! ***\n";
         return;
      }
      os1 << "   DAG has " << Vector.size() << " nodes\n";
      PrintVectorDag( &Vector, os1 );
      return;
   } // if
   else {
      if ( MasterList.size() == 0 ) {
         os1 << "*** Empty dag!! ***\n";
         return;
      }
      os1 << "   DAG has " << MasterList.size() << " nodes\n";
      for( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
           Front++ )
         (*Front).PrintElement(os1);
   }
#else if defined (_STL_VECTOR_USED_)
   if ( MasterList.size() == 0 ) {
      os1 << "*** Empty dag!! ***\n";
      return;
   }
   os1 << "   DAG has " << MasterList.size() << " nodes\n";
   PrintVectorDag( &MasterList, os1 );
#endif
}



// InsertOp: insert Element into MasterList
MainList::iterator dag::InsertOp( BigListElement Element )
{

   MainList::iterator MasterListIter;

#if defined (_STL_LIST_USED_)
   MasterListIter = MasterList.insert( MasterList.begin(), Element )
#else if defined (_STL_VECTOR_USED_)
   MasterList.push_back( Element );
   MasterListIter = MasterList.end();
   MasterListIter--;
#endif

   return MasterListIter;
}


// SetBrDeps: sets control dep arcs to Target from Front to Back
void dag::SetBrDeps( MainList::iterator MasterListIter )
{
   int rc;
   MainList::iterator Front;

   derr( ">> SetBrDeps\n" );
   for ( Front = BranchBarrier; Front != MasterListIter;
#if defined (_STL_LIST_USED_)
        Front-- ) {
#else if defined (_STL_VECTOR_USED_)
     Front++ ) {
#endif
      if ((*MasterListIter).GetOp()->IsBRLOp()) {
        // only add edges between other BRL ops, if dependent
        if ((*Front).GetOp()->IsBRLOp()) {
          if (AreOpsDependent((*Front).GetOp(), (*MasterListIter).GetOp())) {
            dderr( ">> Inserted br-dep edge between "
                  << (*Front).GetOp()->GetOpId() );
            rc = (*Front).AddSuccessor( ET_CNTL, (*MasterListIter).GetOp(),
                                       &(*MasterListIter) );
            dderr( " (" << rc << ") " );
            rc = (*MasterListIter).AddPredecessorBeginning( ET_CNTL, (*Front).GetOp(),
                                                  &(*Front) );
            dderr( " and " << (*MasterListIter).GetOp()->GetOpId() << " (" << rc
                  << ")\n" );
          }
        }
      }
    } // for
   derr( "<< SetBrDeps\n" );
}


// SetBrDepsFirst: sets control dep arcs to Target from Front to Back
// mdj 5/14/98 I added this function to get the correct dep from the 
// branch in the parent BB to the first branch in a sibling BB. Previously,
// control edges were being added from sibling BB to sibling BB incorrectly
void dag::SetBrDepsFirst( MainList::iterator MasterListIter, legoRegion *Region )
{
  int rc;
  MainList::iterator Front, Search, Search2;
  legoOp *EntryOp;
  opList *ParentExitOp;
  
  derr( ">> SetBrDepsFirst\n" );
  // because this is a treegion, the only InEdge is from the branch 
  // from the parent BB
  EntryOp = (legoOp *) Region->GetItem( 0 );
  ParentExitOp = EntryOp->GetInListPtr();
#if defined (_STL_LIST_USED_)
  Search = MasterList.begin();
#else if defined (_STL_VECTOR_USED_)
  Search = MasterList.begin();
#endif
  while ( ParentExitOp->GetOpId() != (*Search).GetOp()->GetOpId() ) {
#if defined (_STL_LIST_USED_)
    Search++;
#else if defined (_STL_VECTOR_USED_)
    Search++;
#endif
  }
  dderr( ">> Inserted br-dep edge between "
       << (*Search).GetOp()->GetOpId() );
  rc = (*Search).AddSuccessor( ET_CNTL, (*MasterListIter).GetOp(),
                              &(*MasterListIter) );
  dderr( " (" << rc << ") " );
  rc = (*MasterListIter).AddPredecessorBeginning( ET_CNTL, (*Search).GetOp(),
                                        &(*Search) );
  dderr( " and " << (*MasterListIter).GetOp()->GetOpId() << " (" << rc
       << ")\n" );
  
  // Now add a control edge from the ParentExitOp to the entry C_MERGE 
#if defined (_STL_LIST_USED_)
  Search2 = MasterList.begin();
#else if defined (_STL_VECTOR_USED_)
  Search2 = MasterList.begin();
#endif
  while ( EntryOp->GetOpId() != (*Search2).GetOp()->GetOpId() ) {
#if defined (_STL_LIST_USED_)
    Search2+
#else if defined (_STL_VECTOR_USED_)
    Search2++;
#endif
  }
  dderr( ">> Inserted control edge between "
       << (*Search).GetOp()->GetOpId() );
  rc = (*Search).AddSuccessor( ET_CNTL, (*Search2).GetOp(),
                              &(*Search2) );
  dderr( " (" << rc << ") " );
  rc = (*Search2).AddPredecessorBeginning( ET_CNTL, (*Search).GetOp(),
                                        &(*Search) );
  dderr( " and entry C_MERGE " << (*Search2).GetOp()->GetOpId() << " (" << rc
       << ")\n" );
  
  // Now handle the other edges for ops preceding this branch
  for (Front = BranchBarrier;
       Front != MasterListIter;
#if defined (_STL_LIST_USED_)
       Front-- ) {
#else if defined (_STL_VECTOR_USED_)
    Front++ ) {
#endif 
         if ((*MasterListIter).GetOp()->IsBRLOp()) {
           // only add edges between other BRL ops, if dependent
           if ((*Front).GetOp()->IsBRLOp()) {
             if (AreOpsDependent((*Front).GetOp(), (*MasterListIter).GetOp())) {
               dderr( ">> Inserted br-dep edge between "
                     << (*Front).GetOp()->GetOpId() );
               rc = (*Front).AddSuccessor( ET_CNTL, (*MasterListIter).GetOp(),
                                          &(*MasterListIter) );
               dderr( " (" << rc << ") " );
               rc = (*MasterListIter).AddPredecessorBeginning( ET_CNTL, (*Front).GetOp(),
                                                              &(*Front) );
               dderr( " and " << (*MasterListIter).GetOp()->GetOpId() << " (" << rc
                     << ")\n" );
             }
           }
         }
       } // for
  derr( "<< SetBrDepsFirst\n" );
}


// 
void dag::SetPBRDeps( MainList::iterator MasterListIter, legoRegion *Region )
{
  int rc;
  MainList::iterator Front, Search, Search2;
  legoOp *EntryOp;
  opList *ParentExitOp;
  
  derr( ">> SetPBRDeps\n" );
  // because this is a treegion, the only InEdge is from the branch 
  // from the parent BB
  EntryOp = (legoOp *) Region->GetItem( 0 );
  ParentExitOp = EntryOp->GetInListPtr();
#if defined (_STL_LIST_USED_)
  Search = MasterList.begin();
#else if defined (_STL_VECTOR_USED_)
  Search = MasterList.begin();
#endif
  while ( ParentExitOp->GetOpId() != (*Search).GetOp()->GetOpId() ) {
#if defined (_STL_LIST_USED_)
    Search++;
#else if defined (_STL_VECTOR_USED_)
    Search++;
#endif
  }
  dderr( ">> Inserted PBR br-dep edge between "
       << (*Search).GetOp()->GetOpId() );
  rc = (*Search).AddSuccessor( ET_CNTL, (*MasterListIter).GetOp(),
                              &(*MasterListIter) );
  dderr( " (" << rc << ") " );
  rc = (*MasterListIter).AddPredecessorBeginning( ET_CNTL, (*Search).GetOp(),
                                        &(*Search) );
  dderr( " and " << (*MasterListIter).GetOp()->GetOpId() << " (" << rc
       << ")\n" );
  
  derr( "<< SetPBRDeps\n" );
}


// ConstructTreeDag: Construct a DAG for the tree region
void dag::ConstructTreeDag(legoRegion *Region, DagHashTable *TablePtr, 
                           vector <MainList::iterator> *StoreListPtr,
                           vector <MainList::iterator> *LoadListPtr)
{
   regionList *Descendant;
   legoRegion *ParentRegion, *CurrentRegion;
   int OpCount;
   legoOp *CurrentOp;
   BigListElement Element;
   int i;
   MainList::iterator MasterListIter, Front, Back, TmpFront, TmpBack;
   DagHashTable MyTable;
   vector <MainList::iterator> MyStoreList;
   vector <MainList::iterator> MyLoadList;
   attrs *RC;
   int FirstBranch = 1;
   legoOprd *PredOprd; 
   int true_predicate; 


   FunctionName = "ConstructTreeDag()";
   
   if (NotRoot)
     UpdateTreeTraversalRList(Region);
   prev_block_ptr = Region;
   
   OpCount = Region->GetCount();
   derr( ">> ConstructTreeDag: block " << Region->GetRegionId()
         << " w/" << OpCount << " Ops -- BEGIN\n" );
#if defined(_STL_LIST_USED_)
   // Assume that new insertions into the list will expand the vector
   // by no more than 100%.
   Vector.reserve( 2 * OpCount );
#endif
   if ( TablePtr != NULL )
     {
       //       Table.~DagHashTable();
       Table = *TablePtr;
     } // end if
   
   if (StoreListPtr != NULL) { 
     StoreList.erase( StoreList.begin(), StoreList.end() );     
     StoreList = (*StoreListPtr); 
   }
   if (LoadListPtr != NULL) { 
     LoadList.erase( LoadList.begin(), LoadList.end() );
     LoadList = (*LoadListPtr); 
   }
   
#if defined(_STL_LIST_USED_)
   TmpFront = MasterList.begin();
#endif
   for ( i = 0, CurrentOp = (legoOp *) Region->GetItem( 0 ); i < OpCount;
         i++ ) {

      attrs *A;

      derr( "** Op # " << i << ", Op id " << CurrentOp->GetOpId() );
      NumNodes++;
      PrepOpForInsertion( Element, CurrentOp, Region->GetWeight() );

      // Insert the Op into the Master List
      SetClusterId( CurrentOp, Element );
      MasterListIter = InsertOp( Element );
      Element = (*MasterListIter);
      derr( ", cluster " << Element.ClusterId << ", list size "
            << MasterList.size() << "\n" );

      // Set the branch barrier
      if ( i == 0 ) {
         BranchBarrier = MasterListIter;
      }

      // Don't let DEFINES affect the DPG
      if (CurrentOp->IsDEFINEOp()) {
        CurrentOp = CurrentOp->GetNextLink();
        continue; 
      }

      FlowDeps( MasterListIter, &Element );
      OutputAntiDeps( MasterListIter, &Element );
      UpdateUseStatus( MasterListIter, &Element );

      // Set branch dependency edges
      if ( Machine->TinkerOptype( (*MasterListIter).GetOp() )
          == BR_OP && i != 0 ) {
        if (NotRoot == 1) {
          SetBrDepsFirst( MasterListIter, Region );
        }
        else {
          SetBrDeps( MasterListIter );
        }
      } // if
      
      // Set PBRR dependency edges. These edges allow PBRRs to intermix with
      // the multi-way branch ops (in the same cycle if zero latency PBRRs)
      // But limits them from being speculated higher
      
      if (NotRoot == 1) {
        if ((*MasterListIter).GetOp()->IsPBROp()) {
           SetPBRDeps( MasterListIter, Region );
        }
      }

      // Prevent the speculation of stores
      // Right now "mem_independent" never appears in source rebel. Left this
      // hook in code in case we ever do any memory disambiguation
      RC = FindLcAttribute( "mem_independent", (*MasterListIter).GetOp() );
      if ((IsStoreOp( (*MasterListIter).GetOp() ) && RC == NULL) ||
          (IsLoadOp( (*MasterListIter).GetOp() ) && RC == NULL) || 
          (*MasterListIter).GetOp()->IsBRLOp()) {
        // Determine if op has a true predicate
        PredOprd = (*MasterListIter).GetOp()->GetPredOprdPtr();
        true_predicate = TRUE; 
        if (PredOprd != NULL) 
          if (PredOprd->GetOprdType() != OT_LITERAL_P ||
              PredOprd->GetLiteralPredicate() != TRUE ) 
            true_predicate = FALSE; 

        // Either push op onto appropriate StoreList/LoadList or refresh 
        // Lists before pushing op on
        if ( IsLoadOp( (*MasterListIter).GetOp() ) || !true_predicate ) {
          if (IsLoadOp( (*MasterListIter).GetOp())) {
            LoadList.push_back(MasterListIter); 
          }
          else {
            StoreList.push_back(MasterListIter); 
          }
        }
        else {
          StoreList.erase( StoreList.begin(), StoreList.end() );           
          LoadList.erase( LoadList.begin(), LoadList.end() );
          if (IsLoadOp( (*MasterListIter).GetOp())) {
            LoadList.push_back(MasterListIter); 
          }
          else {
            StoreList.push_back(MasterListIter); 
          }
        }
        derr( ">> Store barrier set to Op "
             << (*MasterListIter).GetOp()->GetOpId() << "\n" );
      }
      CurrentOp = CurrentOp->GetNextLink();
   } // for all Ops

   // Since the last entry in a list/vector doesn't 'show up', use some
   // extra logic to correct the situation.
   CorrectionCode();

   // Mark this block
   Region->Mark( RM_GENERAL );
   MyTable = DagHashTable ( Table );
   MyStoreList = StoreList;
   MyLoadList = LoadList;
#if defined(_STL_LIST_USED_)
   CopyListToVector( MasterList.begin(), TmpFront );
#endif
   derr( "   Examining children of region " << Region->GetRegionId()
         << "\n" );

   // Cycle through all of the children for the current node being processed
   for ( Descendant = Region->GetChildren(),
         ParentRegion = Region->GetParentPtr(); Descendant != NULL;
         Descendant = Descendant->GetNextListPtr() ) {

      derr( "   Child of region " << Region->GetRegionId()
            << " is region " << Descendant->GetRegionPtr()->GetRegionId()
            << "\n" );

      // Check if the current descendant is in the same tree.
      if ( ParentRegion != Descendant->GetRegionPtr()->GetParentPtr()
           || Region == Descendant->GetRegionPtr()
           || Descendant->GetRegionPtr()->IsMarked( RM_GENERAL ) == 1 )
         continue;

      CurrentRegion = Descendant->GetRegionPtr();
      derr( "   Build DAG for region " << CurrentRegion->GetRegionId()
            << "\n" );
      // mdj 5/14/98 setBrDepsFirst patch
      NotRoot = 1;
      ConstructTreeDag( CurrentRegion, &MyTable, &MyStoreList, &MyLoadList );
   }
   MyTable.erase( MyTable.begin(), MyTable.end() );
   MyStoreList.erase( MyStoreList.begin(), MyStoreList.end() );    
   MyLoadList.erase( MyLoadList.begin(), MyLoadList.end() );
   derr( "<< ConstructTreeDag: block " << Region->GetRegionId()
         << " -- DONE\n" );
}


// ConstructLinearDag: Construct a DAG for the linear region
void dag::ConstructLinearDag( legoRegion *ParentRegion )
{
   int i, rc, OpCount, region_type = ParentRegion->GetRegionType();
   BigListElement Element;
   legoOp *CurrentOp;
   legoRegion *Region;
   MainList::iterator MasterListIter, Front, Back;
   double weight = ParentRegion->GetWeight();
   attrs *RC;
   legoOprd *PredOprd; 
   int true_predicate; 


   FunctionName = "ConstructLinearDag()";
   derr( ">> ConstructLinearDag\n" );
   OpCount = ParentRegion->GetCount();
   // wah 3/20/98 Added #ifdef.
#ifdef _DAG_DEBUG_
   if ( region_type == RT_SB || ( region_type == RT_HB &&
        FindFlag( SB, ParentRegion ) != NULL  )  )
      {derr( "   Superblock " );}
   else {derr( "   Basic block " );}
   derr( ParentRegion->GetRegionId() << " has " << OpCount << " Ops.\n" );
#endif

#if defined (_STL_VECTOR_USED_)
   MasterList.reserve( OpCount + 1 );
#endif
   for ( i = 0, CurrentOp = (legoOp *) ParentRegion->GetItem( 0 );
         i < OpCount; i++ ) {

      attrs *A;

      derr( "   Op # " << i << ", Op id " << CurrentOp->GetOpId() );
      NumNodes++;

      // DON'T REMOVE THE BRACES AROUND THE PrepOpForInsertion(). It's a
      // macro.
      if ( region_type == RT_BB ) {
         PrepOpForInsertion( Element, CurrentOp, weight );
      }
      else if ( region_type == RT_HB || region_type == RT_SB ) {
        PrepOpForInsertion( Element, CurrentOp,
                           FindOpWeight( CurrentOp ) );
      }

      // Insert the Op into the Master List
      SetClusterId( CurrentOp, Element );
      MasterListIter = InsertOp( Element );
      Element = (*MasterListIter);
      derr( ", cluster " << Element.ClusterId << "\n" );

      // Set the first branch barrier
      if ( i == 0 ) {
        BranchBarrier = MasterListIter;
      }

      // Don't let DEFINES affect the DPG
      if (CurrentOp->IsDEFINEOp()) {
        CurrentOp = CurrentOp->GetNextLink();
        continue; 
      }

      FlowDeps( MasterListIter, &Element );
      OutputAntiDeps( MasterListIter, &Element );
      UpdateUseStatus( MasterListIter, &Element );

      // Set branch dependency edges
      if ( Machine->TinkerOptype( (*MasterListIter).GetOp() )
          == BR_OP && i != 0 ) {
        SetBrDeps( MasterListIter );
      } // if
      
      // Prevent the speculation of stores
      // Right now "mem_independent" never appears in source rebel. Left this
      // hook in code in case we ever do any memory disambiguation
      RC = FindLcAttribute( "mem_independent", (*MasterListIter).GetOp() );
      if (( IsStoreOp( (*MasterListIter).GetOp() ) && RC == NULL ) ||
          ( IsLoadOp( (*MasterListIter).GetOp() ) && RC == NULL ) || 
          (*MasterListIter).GetOp()->IsBRLOp()) {
        // Determine if op has a true predicate
        PredOprd = (*MasterListIter).GetOp()->GetPredOprdPtr();
        true_predicate = TRUE; 
        if (PredOprd != NULL) 
          if (PredOprd->GetOprdType() != OT_LITERAL_P ||
              PredOprd->GetLiteralPredicate() != TRUE ) 
            true_predicate = FALSE; 

        // Either push op onto appropriate StoreList/LoadList or refresh 
        // Lists before pushing op on
        if ( IsLoadOp( (*MasterListIter).GetOp() ) || !true_predicate ) {
          if (IsLoadOp( (*MasterListIter).GetOp())) {
            LoadList.push_back(MasterListIter); 
          }
          else {
            StoreList.push_back(MasterListIter); 
          }
        }
        else {
          StoreList.erase( StoreList.begin(), StoreList.end() );           
          LoadList.erase( LoadList.begin(), LoadList.end() );
          if (IsLoadOp( (*MasterListIter).GetOp())) {
            LoadList.push_back(MasterListIter); 
          }
          else {
            StoreList.push_back(MasterListIter); 
          }
        }
        derr( ">> Store barrier set to Op "
             << (*MasterListIter).GetOp()->GetOpId() << "\n" );
      }
      CurrentOp = CurrentOp->GetNextLink();
    } // for all Ops
   
   // Since the last entry in a list/vector doesn't 'show up', use some
   // extra logic to correct the situation.
   CorrectionCode();

#if defined (_STL_LIST_USED_)
   MasterList.reverse();
   CopyListToVector();
#endif
   derr( "<< ConstructLinearDag\n" );
}


// ConstructDag: Construct a DAG for the Region
void dag::ConstructDag( legoRegion *Region )
{
   int region_type;

   FunctionName = "ConstructDag()";
   derr( ">> ConstructDag\n" );
   ParentRegion = Region;
   
   //HZ:
   //calculate the num of execution paths in the treegion and fill in the path
   //info using exit_ops 
   opList * op_list1;
   num_path = 0;
   for(op_list1 = Region->GetExitOpsPtr(); op_list1 != NULL; op_list1 =
        op_list1->GetNextListPtr())
   {
       legoOp * exit_op1 = op_list1->GetOpPtr();
       if(exit_op1 != NULL)
       {
           //set up the path_BB_id (exit BB_id for each path)
           path_BB_ids[num_path] =
                ((legoRegion *)exit_op1->GetParentBlockPtr())->GetRegionId();
           
           //set up the weight for each path
           if(exit_op1->IsRETOp())
               weights[num_path] =
                ((legoRegion *)exit_op1->GetParentBlockPtr())->GetWeight();
           else if(((legoRegion *)exit_op1->GetParentBlockPtr())->GetWeight() >
               0)
           {
               //use the exit edge freq.
               //Find the corresponding exit edge(s) and sum up their freqs
               //Note that we can not use the region weight as RTS case, as the
               // exit edge of the region may not be a true exit edge.
               //For example, the fall through edge of a br is a true exit deg
               //and its taken edge point to another BB in the same treegion,
               // when calculating the weight of the fall through path, the takn
               // freq should not be counted.
               edgeList *oel = ((legoRegion
                       *)exit_op1->GetParentBlockPtr())->GetOutEdgesPtr();
               double s_weight = 0;
               for(; oel != NULL; oel = oel->GetNextListPtr())
               {
                   opEdges * edge_p = oel->GetEdgePtr();
                   if(edge_p != NULL)
                   {
                       assert(edge_p->GetFromOpId() == exit_op1->GetOpId());
                       if(find_op(Region, edge_p->GetToOpId()) == NULL
                               || edge_p->GetToOpId() ==
                               Region->GetEntryOpsPtr()->GetOpId())
                       {
                           //true exit edge
                           s_weight += FindEdgeFrequency(edge_p);
                       }
                   }
               }
               weights[num_path] = s_weight;
           }
           else
               weights[num_path] = 0;
           //setup the # of ops for each path 
           int num_op = 0;
           legoRegion * temp_reg = (legoRegion *)exit_op1->GetParentBlockPtr();
           while(1)
           {
               if(ParentRegion->GetRegionType() == RT_TREE)
               {
                   if(temp_reg == ((legoTreegion *)ParentRegion)->GetRoot())
                   {
                       num_op += temp_reg->GetOpCount();
                       break;
                   }
               }
               else 
               {
                   if(temp_reg == ParentRegion)
                   {
                       num_op += temp_reg->GetOpCount();
                       break;
                   }
               }
               num_op += temp_reg->GetOpCount();
               temp_reg = temp_reg->GetParents()->GetRegionPtr();
           }
           num_ops[num_path] = num_op;
           
           num_path++;
           if(num_path > MAX_NUM_PATH)
           {
               cout << "Fatal: <DAG Contruction> Paths exceeds MAX_NUM_PATH.\n";
               exit(-1);
           }
       }
       else
       {
           cout << "<DAG Contruction> exit_op not found... \n";
       }
   }
   printf("dag.c: ConstructDag(): EndFor\n");
   
   if ( !IS_BLOCK( (region_type=Region->GetRegionType()) ) ) {

      int i, BlockCount, OpCount;
      legoRegion *CurrentRegion;

      // Count the # of Ops in the region
      BlockCount = ParentRegion->GetCount();
      derr( "   Treegion " << ParentRegion->GetRegionId() << " has "
            << BlockCount << " blocks\n" );
      for ( i = 0, OpCount = 0; i < BlockCount; i++ ) {
         CurrentRegion = (legoRegion *) ParentRegion->GetItem( i );
         OpCount += CurrentRegion->GetCount();
         derr( "      Sub-region " << CurrentRegion->GetRegionId()
               << " has " << CurrentRegion->GetCount() << " Ops "
               << " ( total = " << OpCount << " )\n" );
      }
#if defined (_STL_VECTOR_USED_)
      MasterList.reserve( OpCount + 1 );
      derr( "** " << OpCount << " entries reserved\n" );
#elif defined (_STL_LIST_USED_)
      Vector.reserve( OpCount );
#endif

      if ( region_type == RT_TREE ) {
         legoTreegion *Tree = (legoTreegion *) ParentRegion;
         // mdj 5/14/98 setBrDepsFirst patch
         NotRoot = 0;   
         ConstructTreeDag( Tree->GetRoot(), NULL, NULL, NULL );
         
         //HZ: as ConstructTreeDag marks the RM_GENERAL, here to clear it
         ClearMarks (RM_GENERAL, Tree);
      }
      else if ( region_type == RT_TRACE ) {
         legoTrace *Trace = (legoTrace *) ParentRegion;
         for ( i = 0; i < BlockCount; i++ ) {
            CurrentRegion = (legoTrace *) ParentRegion->GetItem( i );
            ConstructLinearDag( CurrentRegion );
         }
      }
      // SetSublistPtrs();
#if defined (_STL_LIST_USED_)
      DestructBigList( &MasterList );
      VectorActive = 1;
#endif
   printf("dag.c: ConstructDag(): EndIf\n");
   }

   // sanjeev - We do not use hyperblocks at all, but Elcor labels its
   // superblocks as hyperblocks. So I need to realize that a HB is really
   // a SB w/a different label.
   else 
  {
      ConstructLinearDag( ParentRegion );
        printf("dag.c: ConstructDag(): EndElse\n");
  }

   // Remove thos spurious ET_UNDEF edges (see dag_dependency.C).
   RemoveUndefPredecessors();
   printf("RemoveUndef\n");
   SetNodeHeights();
   printf("SetNodeHeights\n");
   SetNodeDepths();
   printf("SetNodeDepths\n");
   derr( "<< ConstructDag\n" );
}


// Stats: get size info on the adjacency list
dag::Stats()
{
   int i, j, size;


   cout << "> DAG stats\n";
   cout << ">\n";
#if defined (_STL_LIST_USED_)
   if ( VectorActive == 1 )
      cout << "> Master list has " << Vector.size() << " nodes\n";
   else 
      cout << "> Master list has " << MasterList.size() << " nodes\n";
#elif defined (_STL_VECTOR_USED_)
      cout << "> Master list has " << MasterList.size() << " nodes\n";
#endif

   cout << "> Hash table has " << Table.size() << " nodes\n\n";
}


// dag: constructor
dag::dag( machine *mdes, int Inp_start, int Inp_end, int Ret_start, int Ret_end, int Fp_ret_start,
        int Fp_ret_end )
{
   derr( ">> dag::constructor\n" );
   FunctionName = "constructor()";
   Machine = mdes;
   VectorActive = 0;
   NumNodes = KillDagFlag = 0;
   ReadHashKey = new char[ Hash_Key_Size ];
   ReadHashReg = new char[ Hash_Reg_Size ];
   
   //HZ:
   max_heights = new double[MAX_NUM_PATH];
   path_BB_ids = new int[MAX_NUM_PATH];
   weights = new double[MAX_NUM_PATH];
   num_ops = new int[MAX_NUM_PATH];
   num_path = 0;
   ave_max_height = 0;

   inp_start = Inp_start;
   inp_end = Inp_end;
   ret_start = Ret_start;
   ret_end = Ret_end;
   fp_ret_start = Fp_ret_start;
   fp_ret_end = Fp_ret_end;   
   
   derr( "<< dag::constructor\n" );
   
}


// dag: constructor
dag::dag( machine *mdes, knobs *Knobs, int Inp_start, int Inp_end, int Ret_start, int Ret_end, int Fp_ret_start,
        int Fp_ret_end )
{
   derr( ">> dag::constructor\n" );
   FunctionName = "constructor()";
   Machine = mdes;
   VectorActive = 0;
   NumNodes = KillDagFlag = 0;
   ReadHashKey = new char[ Hash_Key_Size ];
   ReadHashReg = new char[ Hash_Reg_Size ];

   // Read knobs
   Knobs->SetDefaultPanel( "estimator" );

   //HZ:
   max_heights = new double[MAX_NUM_PATH];
   path_BB_ids = new int[MAX_NUM_PATH];
   weights = new double[MAX_NUM_PATH];
   num_ops = new int[MAX_NUM_PATH];
   num_path = 0;
   ave_max_height = 0;
   
   inp_start = Inp_start;
   inp_end = Inp_end;
   ret_start = Ret_start;
   ret_end = Ret_end;
   fp_ret_start = Fp_ret_start;
   fp_ret_end = Fp_ret_end;
   
   derr( "<< dag::constructor\n" );
}


// DeleteDefUseTable: delete the def-use table
void dag::DeleteDefUseTable()
{
   derr( ">> DeleteDefUseTable\n" );
   delete[] ReadHashKey;
   delete[] ReadHashReg;

   // 11/20/98 MDJ: Fixed memory leak associated with WriteHashKeys
   for(vector <char *>::const_iterator LookUpIter = HashKeyList.begin();
       LookUpIter != HashKeyList.end();
       LookUpIter++ ) {
     delete ((*LookUpIter));
   }
   HashKeyList.erase( HashKeyList.begin(), HashKeyList.end() );

   Table.erase( Table.begin(), Table.end() );
   derr( "<< DeleteDefUseTable\n" );
}


// DeleteGraphNodes: delete the adjacency list
void dag::DeleteGraphNodes()
{
   derr( ">> DeleteGraphNodes\n" );
#if defined (_STL_LIST_USED_)
   if ( VectorActive == 1 ) {
      derr( "   Delete Vector\n" );
      DestructBigVector( &Vector );
   }
   else {
      derr( "   Delete MainList List\n" );
      DestructBigList( &MasterList );
   }
#else if defined (_STL_VECTOR_USED_)
   derr( "   Delete MasterList Vector\n" );
   DestructBigVector( &MasterList );
#endif
   derr( "<< DeleteGraphNodes\n" );
}


// KillDag: destructor
void dag::KillDag()
{
   derr( ">> KillDag\n" );
   KillDagFlag = 1;
   DeleteDefUseTable();
   DeleteGraphNodes();
   derr( "<< KillDag\n" );
}


// dag: destructor
dag::~dag()
{
    //HZ:
    if(path_BB_ids != NULL) 
    {
        delete path_BB_ids;
        path_BB_ids = NULL;
    }
    if(max_heights != NULL)
    {
        delete max_heights;
        max_heights = NULL;
    }
    if(weights != NULL)
    {
        delete weights;
        weights = NULL;
    }
    if(num_ops != NULL)
    {
        delete num_ops;
        num_ops = NULL;
    }
   if ( KillDagFlag == 1 ) return;
   derr( ">> ~dag\n" );
   KillDag();
   derr( "<< ~dag\n" );
}

---