dag_node_ordering.H

Go to the documentation of this file.

#ifndef _INCLUDE_DAG_NODE_ORDERING_H_
#define _INCLUDE_DAG_NODE_ORDERING_H_

/*
  ae: modif heights and depths definition to count the latency along
    an anti dep to be 0 cycles (Jan 30, 1998)
  4/7/98 WAH:   Fixed bug in DoSuperblockPriorities.
*/

#include <TinkerKnobs.H>
#include <dag.H>
#include <machine.h>
//ae
#include <search.H>
#include <assert.h> 

// #define _DAG_NODE_ORDERING_DEBUG_
#if defined (_DAG_NODE_ORDERING_DEBUG_)
#define public_derr(s)  cerr << s
#else
#define public_derr(s)
#endif

static double
GetCountHelped (DagNode *node)
{
  legoOp *nodeop = node->GetOp();
  legoRegion *region;
  opList *exitops;
  double numhelped;

  if (nodeop == NULL) return 0.0;
  for (region = (legoRegion *) nodeop->GetParentBlockPtr();
       region->GetRegionType() != RT_TREE &&
         region->GetRegionType() != RT_SB &&
         region->GetRegionType() != RT_HB &&
         region->GetRegionType() != RT_PROC;
       region = region->GetParentPtr()) /* do nothing */;
  if (region->GetRegionType() == RT_PROC)
    return 1.0;  // a basic block => one exit
      
  exitops = region->GetExitOpsPtr();
  numhelped = 0.0;
    
  if (region->GetRegionType() == RT_SB || region->GetRegionType() == RT_HB)
    {
      for (opList *opl = exitops; opl != NULL; opl = opl->GetNextListPtr())
        {
          for (legoOp *op = opl->GetOpPtr(); op != NULL;
               op = op->GetPrevLink())  // walk up block
            if (op == nodeop)
              {
                numhelped += 1.0;  // if encounter our op, it helps the exit
                break;
              } // end if
        } // end for
      return numhelped;
    } // end if

  if (region->GetRegionType() == RT_TREE)
    {
      for (opList *opl = exitops; opl != NULL; opl = opl->GetNextListPtr())
        {
          legoOp *op = opl->GetOpPtr();
          while (op != NULL)
            {
              if (op == nodeop)
                {
                  numhelped += 1.0; break;
                } // end if
              if (op->GetPrevLink() != NULL)
                op = op->GetPrevLink();  // walk up like in superblock
              else if ((legoRegion *) op->GetParentBlockPtr() !=
                       ((legoTreegion *) region)->GetRoot())
                {  // jump to previous basic block if not at root
                  op = ((legoRegion *) op->GetParentBlockPtr())
                    ->GetParents()->GetRegionPtr()->GetExitOpsPtr()
                    ->GetOpPtr();
                } // end else if
              else op = NULL;  // hit C_MERGE of root
            } // end while
        } // end for
      return numhelped;
    } // end if

  return 0.0;
} // end GetCountHelped

static double
GetGlobalWeight (DagNode *node)
{
  legoOp *nodeop = node->GetOp();
  machine *mach = new machine();
  legoOp *blockop, *prevblockop;
  opList *opl;
  attrs *a;

  public_derr( ">> GetGlobalWeight: Op " << node->GetOp()->GetOpId() << "\n" );
  legoRegion* tttt = (legoRegion*)(nodeop->GetParentBlockPtr());

  if (tttt->GetRegionType() == RT_BB)
    return tttt->GetWeight();

  if ( nodeop->GetPrevLink() == NULL ) return tttt->GetWeight();

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

  for (prevblockop = nodeop, blockop = nodeop->GetPrevLink();
       (mach->TinkerOptype (blockop) != BR_OP ||
        blockop->GetOpcode() == BRL) && blockop->GetPrevLink() != NULL ||
       (blockop->GetOpcode() == C_MERGE && blockop->GetPrevLink() != NULL);
       prevblockop = blockop,
         blockop = blockop->GetPrevLink()) /* do nothing */;

  public_derr( "   About to call TinkerOptype\n" );
  if (mach->TinkerOptype (blockop) == BR_OP)
    {
      delete mach;
      public_derr( "   Getting weight\n" );

      // If a C_MERGE is encountered, return the region weight.
      if (blockop->GetOpcode() == C_MERGE )
          return tttt->GetWeight();
      for (opl = blockop->GetOutListPtr(); opl != NULL;
           opl = opl->GetNextListPtr())
        if (opl->GetOpId() == prevblockop->GetOpId())
          return opl->GetWeight();
      cerr << "Can't find oplist from " << blockop->GetOpId()
           << " to " << prevblockop->GetOpId() << "\n";
      return 0.0;
    }
  else
    {
      delete mach;
      return tttt->GetWeight();
    }
} // end GetGlobalWeight

class VLilist
{
public:
  VectorList::iterator p;
  int depth;
  class VLilist *next;

  VLilist() {p = NULL; depth = 0; next = NULL;}
  VLilist (VectorList::iterator iter)
    {p = iter; depth = (*p).GetDepth(); next = NULL;}
  ~VLilist() {delete next;}
};

enum node_orderings { DEPENDENCE_HEIGHT, EXIT_COUNT, GLOBAL_WEIGHT,
                      WEIGHTED_COUNT };

class dag_node_ordering {

private:

   node_orderings Ordering;     // The node ordering selected
   legoRegion   *Region;        // The region to process
   dag          *D;             // The dag from Region
   int          sb_override;    // Override superblock heuristic


   void dag_node_ordering::DoSuperblockPriorities ()
     {
       VectorList::iterator Front, Back, Current, Predecessor, Step4;
       VLilist *queue, *cur, *vliscan;
       vector <SmallListElement>::iterator PredIter;
       machine *mach = new machine();
       int i, maxlevel = 0, brweight;
       opList *opl;

       /* Taken from Roger Bringmann's Ph.D. thesis. */

       /* Step 1. Levelize DAG = set depths. */
       D->SetNodeDepths();

       /* Step 2. Determine path length of exit arcs. */
#if defined (_STL_LIST_USED_)
       Back = D->Vector.end();
       for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
       Back = D->MasterList.end();
       for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
         {
           if ((*Front).GetDepth() > maxlevel)
             maxlevel = (*Front).GetDepth();
         }
       public_derr ("Max. depth = " << maxlevel << "\n");

#if defined (_STL_LIST_USED_)
       for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
       for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
         {
           if (mach->TinkerOptype ((*Front).GetOp()) == BR_OP &&
               (*Front).GetOp()->GetOpcode() != BRL &&
               (*Front).GetOp()->GetOpcode() != C_MERGE)
             /* Using depth as a temporary. */
             {
               (*Front).SetDepth (maxlevel - (*Front).GetDepth() + 1);
               public_derr ("Setting branch " << (*Front).GetOp()->GetOpId() <<
                     " path length to " << (*Front).GetDepth() << "\n");
             }
           (*Front).Value = 0;  /* clear value to start */
         }

       /* Steps 3 and 4. Compute max path lengths from each instruction to
          each exit arc and compute static priorities using them and branch
          probabilities. */
#if defined (_STL_LIST_USED_)
       for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
       for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
         {
           if (mach->TinkerOptype ((*Front).GetOp()) != BR_OP ||
               (*Front).GetOp()->GetOpcode() == BRL ||
               (*Front).GetOp()->GetOpcode() == C_MERGE)
             continue;

           /* Traverse up the DAG from each branch. */
           if ((*Front).GetOp()->GetOpcode() != RTS)
             {
               brweight = 0;
               for (opl = (*Front).GetOp()->GetOutListPtr(); opl != NULL;
                    opl = opl->GetNextListPtr())
                 {
                   if (opl->GetOpPtr() != (*Front).GetOp()->GetNextLink())
                     brweight += (int) opl->GetWeight();
                 }
             }
           else
             {
               legoOp *op, *prevop;

               for (prevop = (*Front).GetOp(), op = prevop->GetPrevLink();
                    (mach->TinkerOptype (op) != BR_OP ||
                     op->GetOpcode() == BRL || op->GetOpcode() == C_MERGE)
                      && op->GetPrevLink() != NULL;
                    prevop = op, op = op->GetPrevLink()) /* do nothing */;
               brweight = 0;
               if (mach->TinkerOptype (op) == BR_OP)
                 {
                   for (opl = op->GetOutListPtr(); opl != NULL;
                        opl = opl->GetNextListPtr())
                     if (opl->GetOpId() == prevop->GetOpId())
                       {
                         brweight += (int) opl->GetWeight();
                       }
                 }
               else  // hit top of block - use block weight
                 {
                   brweight += (int) ((legoRegion *) op->GetParentBlockPtr())
                     ->GetWeight();
                 }
             }
           public_derr ("Branch " << (*Front).GetOp()->GetOpId() <<
                 " has branch weight " << brweight << "\n");
           /* Update branch value first. */
           (*Front).Value += (brweight * (*Front).GetDepth());

           /* Recurse over DAG. */
           queue = new VLilist (Front);
           while (queue != NULL)
             {
               cur = queue;
               queue = queue->next;
               Current = cur->p;
               cur->next = NULL;
               delete cur;
               public_derr ("Dequeued op " << (*Current).GetOp()->GetOpId() << "\n");

               /* Update each predecessor, then enqueue. */
               for (PredIter = (*Current).Predecessors->begin();
                    PredIter != (*Current).Predecessors->end(); PredIter++)
                 {
                   Predecessor = (*PredIter).GetDagEntry();
                   //ae
                   //added reg anti too
                   if ((*PredIter).GetDependencyType() == ET_CNTL ||
                       (*PredIter).GetDependencyType() == ET_REGANTI)
                     /* Control edge has no latency. */
                     {
                       if ((*Current).GetDepth() > (*Predecessor).GetDepth())
                         {
                           (*Predecessor).SetDepth ((*Current).GetDepth());
                           /* Enqueue for next go-round. */
                           cur = new VLilist (Predecessor);
                           cur->next = queue;
                           queue = cur;
                           public_derr ("Enqueued op " <<
                                 (*Predecessor).GetOp()->GetOpId() << "\n");
                           /* Kill queue entries with lower depth than now. */
                           for (vliscan = queue; vliscan->next != NULL;
                                vliscan = vliscan->next)
                             if (vliscan->next->p == Predecessor &&
                                 vliscan->next->depth <=
                                 (*Predecessor).GetDepth())
                               {
                                 cur = vliscan->next;
                                 vliscan->next = cur->next;
                                 cur->next = NULL;
                                 public_derr ("Killing a queue entry.\n");
                                 delete cur;
                                 // 4/15/98 WAH
                                 if (vliscan->next == NULL) break;
                               }
                         }
                     }
                   else
                     {
                       if ((*Current).GetDepth() +
                           mach->opLatency ((*Predecessor).GetOp()) >
                           (*Predecessor).GetDepth())
                         {
                           /* Add op latency to depth of predecessor. */
                           (*Predecessor).SetDepth ((*Current).GetDepth() +
                                                    mach->opLatency
                                                    ((*Predecessor).GetOp()));
                           /* Enqueue for next go-round. */
                           cur = new VLilist (Predecessor);
                           cur->next = queue;
                           queue = cur;
                           public_derr ("Enqueued op " <<
                                 (*Predecessor).GetOp()->GetOpId() << "\n");
                           /* Kill queue entries with lower depth than now. */
                           for (vliscan = queue; vliscan->next != NULL;
                                vliscan = vliscan->next)
                             if (vliscan->next->p == Predecessor &&
                                 vliscan->next->depth <=
                                 (*Predecessor).GetDepth())
                               {
                                 cur = vliscan->next;
                                 vliscan->next = cur->next;
                                 cur->next = NULL;
                                 public_derr ("Killing a queue entry.\n");
                                 delete cur;
                                 // 4/7/98 WAH
                                 if (vliscan->next == NULL) break;
                               }
                         }
                     }

                 }
               public_derr ("Done with predecessors of op " <<
                     (*Current).GetOp()->GetOpId() << "\n");
             }

           /* Actual step 4. */
#if defined (_STL_LIST_USED_)
           for (Step4 = D->Vector.begin(); Step4 != Back; Step4++)
#else if defined (_STL_VECTOR_USED_)
           for (Step4 = D->MasterList.begin(); Step4 != Back; Step4++)
#endif
             {
 
               /* Accumulate op priority. */
               (*Step4).Value += (brweight * (*Step4).GetDepth());
               public_derr ("Op " << (*Step4).GetOp()->GetOpId() <<
                     " now has priority " << (*Step4).Value << "\n");
             }
         }      

       public_derr ("Done!\n");
       D->SetNodeDepths();
       delete mach;
       return;
     }

public:

   // constructor
   dag_node_ordering()          {}

   // constructor
   dag_node_ordering( legoRegion *R )
   {
      public_derr( ">> dag_node_ordering\n" );
      Region = R;
      D = (dag *) R->GetDAG();
      public_derr( "<< dag_node_ordering\n" );
   }

   ~dag_node_ordering()         {}

   
   // ShowParameters - show the values of knobs used in scheduling in
   //    formatted output. This can be called from a program to show
   //    knobs settings in 'nice' output.
   void ShowParameters( knobs *Knobs )
   {
      char *string, flag;

      Knobs->SetDefaultPanel( "dag-node-ordering" );
      Knobs->Read( "node-ordering", string );
      cout << "> Scheduling node ordering: " << string << "\n";
      Knobs->Read( "superblock-override", flag );
      if ( flag == KNOB_TRUE ) cout << "> Override superblock heuristic\n";
   }


   // SetKnobs - sets parm values for the class
   void SetKnobs( knobs *Knobs )
   {

      public_derr( ">> dag_node_ordering::SetKnobs\n" );
      Ordering = DEPENDENCE_HEIGHT;
      sb_override = 0;
      if ( Knobs != NULL ) {

         char flag;
         char *string;

         Knobs->SetDefaultPanel( "dag-node-ordering" );
         Knobs->Read( "node-ordering", string );
         public_derr( "   node ordering selected: " << string << "\n" );
         if ( strcmp( string, "none" ) == 0 ||
              strcmp( string, "dependence-height" ) == 0 )
            Ordering = DEPENDENCE_HEIGHT;
         else if ( strcmp( string, "exit-count" ) == 0 )
            Ordering = EXIT_COUNT;
         else if ( strcmp( string, "global-weight" ) == 0 )
            Ordering = GLOBAL_WEIGHT;
         else if ( strcmp( string, "weighted-count" ) == 0 )
            Ordering = WEIGHTED_COUNT;
         Knobs->Read( "superblock-override", flag );
         if ( flag == KNOB_TRUE ) sb_override = 1;
         public_derr( "   sb_override: " << sb_override << "\n" );
      }
      public_derr( "   Node ordering: " );
      switch (Ordering) {
         case DEPENDENCE_HEIGHT: public_derr( "dependence height\n" );
         case EXIT_COUNT: public_derr( "exit count\n" );
         case GLOBAL_WEIGHT: public_derr( "global weight\n" );
         case WEIGHTED_COUNT: public_derr( "weighted count\n" );
      }
      public_derr( "<< SetKnobs\n" );
   }


   // Sets the value field for all nodes to the nodes' depth
   SetValueToDepth()
   {
      VectorList::iterator Front, Back;
      int i, size;

      public_derr( ">> dag_node_ordering::SetValueToDepth " );
#if defined (_STL_LIST_USED_)
      for ( i= 0, Front = D->Vector.begin(), Back = D->Vector.end();
            Front != Back; Front++, i++ ) {
#else if defined (_STL_VECTOR_USED_)
      for ( i= 0, Front = D->MasterList.begin(), Back = D->MasterList.end();
            Front != Back; Front++, i++ ) {
#endif
         public_derr( "   Node # " << i << ", depth " << (*Front).GetDepth()
               << "\n" );
         (*Front).Value = (*Front).GetDepth();
      }
      public_derr( "<< dag_node_ordering::SetValueToDepth\n" );
   }


   // Sets the value field for all nodes to the nodes' profile counts
   SetValueToWeight()
   {
      VectorList::iterator Front, Back;
      int i, size;

      public_derr( ">> dag_node_ordering::SetValueToWeight" );
#if defined (_STL_LIST_USED_)
      for ( i= 0, Front = D->Vector.begin(), Back = D->Vector.end();
            Front != Back; Front++, i++ ) {
#else if defined (_STL_VECTOR_USED_)
      for ( i= 0, Front = D->MasterList.begin(), Back = D->MasterList.end();
            Front != Back; Front++, i++ ) {
#endif
         public_derr( "   Node # " << i << ", weight " << (*Front).GetDepth()
               << "\n" );
         (*Front).Value = (*Front).GetWeight();
      }
      public_derr( "<< dag_node_ordering::SetValueToWeight\n" );
   }


   void SetDagValues()
   {
     VectorList::iterator Front, Back;
     int i, region_type = Region->GetRegionType();


     public_derr( ">> SetDagValues\n" );

#if defined (_STL_LIST_USED_)
     Back = D->Vector.end();
     Front = D->Vector.begin();
#else if defined (_STL_VECTOR_USED_)
     Back = D->MasterList.end();
     Front = D->MasterList.begin();
#endif

     // For BBs, allow only crtical-path orderings
     if ( region_type == RT_BB ) Ordering = DEPENDENCE_HEIGHT;
     {
       legoRegion *scan;
       int foundSB = 0, foundTREE = 0;

       for (scan = ((legoRegion *) (*Front).GetOp()->GetParentBlockPtr());
            scan->GetRegionType() != RT_PROC;
            scan = scan->GetParentPtr())
         {
           // Bill 1/14/98
           if (scan->GetFlagPtr() != NULL &&
               scan->GetFlagPtr()->GetFlagName() == SB)
             foundSB = 1;
           if (scan->GetRegionType() == RT_TREE)
             foundTREE = 1;
         }
       if (foundSB && !foundTREE)
         {
           DoSuperblockPriorities();
           D->SortByHeight();

           // sanjeev - an over-ride is put here. If the user _really_
           // wants to sort a SB by height, let him.
           if ( sb_override == 1 ) {
#if defined (_STL_LIST_USED_)
             for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
             for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
               (*Front).Value = (*Front).GetHeight();
             }
           D->SortByValue();
           return;
         }
     }

#if defined (_STL_LIST_USED_)
     for (Front = D->Vector.begin(); Front != Back; Front++)
# else if defined (_STL_VECTOR_USED_)
     for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
       {
         int opcode = (*Front).GetOp()->GetOpcode();
         if (opcode ==  BRDVI || opcode == BRDVF ||
             (opcode >= BRU && opcode <= BRCF) ||
             (opcode >= RTS && opcode <= BRW_F_F_F))
           (*Front).Value = 1.0;
         else
           (*Front).Value = 2.0;
       }

     D->SetNodeHeights();
     D->SortByHeight();

     if ( Ordering == DEPENDENCE_HEIGHT )
       public_derr( "   Dependence height\n" );

     else if ( Ordering == EXIT_COUNT )
       {
         public_derr( "   Helped count\n" );
#if defined (_STL_LIST_USED_)
         for (i = 0, Front = D->Vector.begin(); Front != Back; Front++, i++)
#else if defined (_STL_VECTOR_USED_)
         for (i = 0, Front = D->MasterList.begin(); Front != Back; Front++, i++)
#endif
           {
             (*Front).Value = GetCountHelped (Front);
             public_derr ("Node " << i << " has " << (*Front).Value << "\n");
           }
         D->SortByValue();
       }

     else if  ( Ordering == GLOBAL_WEIGHT )
       {
         public_derr( "   Global weight\n" );
#if defined (_STL_LIST_USED_)
         for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
         for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
           (*Front).Value = GetGlobalWeight (Front);
         D->SortByValue();
       }

     else if ( Ordering == WEIGHTED_COUNT )
       {
         public_derr( "   Weighted count\n" );
#if defined (_STL_LIST_USED_)
         for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
         for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
           (*Front).Value = GetCountHelped (Front);
         D->SortByValue();
#if defined (_STL_LIST_USED_)
         for (Front = D->Vector.begin(); Front != Back; Front++)
#else if defined (_STL_VECTOR_USED_)
         for (Front = D->MasterList.begin(); Front != Back; Front++)
#endif
           (*Front).Value = GetGlobalWeight (Front);
         D->SortByValue();
       }

     public_derr( "<< SetDagValues\n" );
     return;
   }

};

#endif

---