scheduling_utilities.C

Go to the documentation of this file.

#include <iostream.h>
#include <stdlib.h>
#include "scheduling_utilities.H"

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

extern int MaxRegNum;
int inp_start, inp_end;

int IsDominatorParallel(legoOp *op, int readytime, legoTreegion* treegion)
{
  legoOp *dupop;
  opList *dupops = op->GetDuplicateOpsPtr();
  int dpoptime = 0;
  legoRegion *dupop_block_ptr, *op_block_ptr, *root_block_ptr;
  regionList *region_list;

  derr( ">> IsDominatorParallel\n" );
  if (dupops == NULL)
    return dpoptime;
  derr( "Op " << op->GetOpId() << " has duplicates.\n" );
  for ( ; dupops != NULL && dpoptime == 0; dupops = dupops->GetNextListPtr())
  {
    dupop = dupops->GetOpPtr();
    if (dupop == NULL) continue;  // skip if op is missing
    if (dupop->GetOpId() == op->GetOpId()) continue;  // op not dp with self
    // Check if dupop BB dominates the BB of candidate op
    dupop_block_ptr = (legoRegion *) dupop->GetParentBlockPtr();
    op_block_ptr = (legoRegion *) op->GetParentBlockPtr();
    root_block_ptr = treegion->GetRoot();
    while ( (op_block_ptr != dupop_block_ptr) && (op_block_ptr != NULL) ) {
      if (op_block_ptr == root_block_ptr)
        break;
      region_list = op_block_ptr->GetParents();
      // blocks in a treegion have one and only one parent, except root block 
      // which has no parents. 
      if (region_list != NULL) 
        op_block_ptr = region_list->GetRegionPtr();
      else 
        op_block_ptr = NULL;
    }
    if ( (op_block_ptr == dupop_block_ptr) && (readytime <= dupop->GetSchedTime()) ) {
      dpoptime = dupop->GetSchedTime();
      break;
    }
  }
  derr ("Op " << op->GetOpId() << " is " << (!dpoptime ? "not " : "")
        << "dominator parallel" << (dpoptime ? " with op " : "")
        << (dpoptime ? dupop->GetOpId() : 0) << "\n");
  return dpoptime;
}


// GetFlowDepOprd: returns a ptr to the legoOprd that forms a flow
//    dep between the Producer and Consumer operands. If Producer produces
//    multiple values, the _first_ legoOprd is returned. If no flow-dep
//    is found, NULL is returned.
legoOprd *GetFlowDepOprd( legoOp *Producer, legoOp *Consumer )
{
   int match, j;
   legoOprd *DestOprd;


   // A flow-dep between a BRL and a consumer is a special case. The
   // consumer is waiting on the BRL's return code. So set up the Consumer
   // to use what Producer dest oprd has the phrase 'ret' in it.
   if ( Producer->GetOpcode() == BRL ) {

      attrList *atl;
      attrs *a;
      legoOprd *oprd = NULL;

      for ( atl = Producer->GetOpAttrListPtr(); atl != NULL;
            atl = atl->GetNextListPtr() ) {
         if ( atl->GetAttrType() != ATTR_LC ) continue;
         for ( a = atl->GetAttrPtr(); a != NULL; a = a->GetNextLcEntryPtr()) {
            if ( strcmp( a->GetAttrString(), "ret" ) != 0 ) continue;
            return a->GetAttrOprdPtr();
         } // for
      } // for
      return NULL;
   } // if


   // Inspect all of Node's destination operands
   for ( match = j = 0, DestOprd = Producer->GetDestOprdPtr();
         DestOprd != NULL && match == 0;
         j++, DestOprd = DestOprd->GetNextOprdPtr() ) {

      int DestOprdType = DestOprd->GetOprdType();

      derr( "      Checking dest oprd # " << j << "\n" );
      if ( DestOprdType == OT_REG || DestOprdType == OT_MACRO ) {

         int dest_regid = DestOprd->GetOprdRegNum();
         int dest_reg_file_type = DestOprdType == OT_MACRO ? -1 :
                                        DestOprd->GetOprdFileType();
         legoOprd *SrcOprd;
         int k;

         // Compare the current dest. operand with all of the src
         // operands
         for ( k = 0, SrcOprd = Consumer->GetSrcOprdPtr();
               SrcOprd != NULL && match == 0;
               k++, SrcOprd = SrcOprd->GetNextOprdPtr() ) {

            int SrcOprdType = SrcOprd->GetOprdType();

            derr( "      Checking src oprd # " << k << "\n" );
            // if ( SrcOprdType == OT_REG || SrcOprdType == OT_MACRO ) {
            if ( SrcOprdType == DestOprdType ) {

               int src_regid = SrcOprd->GetOprdRegNum();
               int src_reg_file_type = SrcOprdType == OT_MACRO ? -1 :
                                       SrcOprd->GetOprdFileType();

               // if ( DestOprdType == SrcOprdType &&
               if ( dest_regid == src_regid &&
                    dest_reg_file_type == src_reg_file_type ) {

                  legoOprd *Src = new legoOprd( *DestOprd ),
                           *Dest = new legoOprd( *DestOprd );

                  match = 1;
                  derr( "   !! Match !!\n" );
                  return DestOprd;
               } // if - regid & regfiletype match
            } // if - operand types match
         } // for - all src operands
      } // if - dest operand is reg or macros
   } // for - all dest operands

   return NULL; // Nothing found
}


// ResetS_Times: Resets s_times for all operations in a procedure to -1 so 
// that another pass of scheduling may follow
void ResetSchedTimes( legoProc *proc )
{

  legoOp *op; 

  for (op = proc->GetListOpPtr(); op != NULL; op = op->GetListOpPtr())
    op->SetSchedTime( -1 );
  
}

// BuildDagForRegion: builds a dag for the region
void BuildDagForRegion( legoRegion *Region, machine *Machine, knobs *Knobs)
{
   dag *DPG;
   
   derr( ">> BuildDagsForRegion: " << Region->GetRegionId() << "\n" );
   //DPG = new dag( Machine, Knobs );
#ifdef IA64_SUPPORT
   printf("IA64_SUPPORT\n");
   DPG = new dag( Machine, Knobs, inp_start, inp_end, 8, 11, 8, 15);
#endif
#ifndef IA64_SUPPORT
   printf("NO IA64 SUPPORT\n");
   DPG = new dag( Machine, Knobs, 0, 0, 0, 0, 0, 0);
#endif
   
// Moved FullyResolvePredicates to LegoUtil, called during treeform
//   if (Region->GetRegionType() == RT_TREE) {
//     ClearMarks (RM_GENERAL, Region);
//     DPG->FullyResolvePredicates( ((legoTreegion *)Region)->GetRoot(), NULL );
//   }
   ClearMarks (RM_GENERAL, Region);
   printf("ClearMarks\n");
   DPG->ConstructDag( Region );
   printf("ConstructDag\n");
   Region->SetDAG( (dag *) DPG );
   printf("SetDAG\n");
   derr( "<< BuildDagsForRegion\n" );
}


// BuildDagsForProc: build dags for the regions contained within ProcPtr
void BuildDagsForProc( legoProc *ProcPtr, machine *Machine, knobs *Knobs )
{
   int i, RegionCount;
   legoRegion *Region;
   
   derr( ">> BuildDagsForProc: " << ProcPtr->GetProcName() << "\n" );

   //HZ: In constucting the DDG, we must consider the implicit dependence dewteen
   // arguments/returns and function calls. In IA64 assembly, 
   // the alloc insn, if there is one, will tell this information.   
   inp_start = FindFirstOutGoingReg(ProcPtr);
   inp_end = FindLastOutGoingReg(ProcPtr);   
   
   MaxRegNum = FindMaxRegNum (ProcPtr);

   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
     Region = (legoRegion *) ProcPtr->GetItem( i );
     BuildDagForRegion( Region, Machine, Knobs);
   }
   derr( "<< BuildDagsForProc\n" );
}


// PrintDagsForProc: prints dags for the regions contained within ProcPtr
void PrintDagsForProc( legoProc *ProcPtr )
{
   int i, RegionCount;
   legoRegion *Region;
   dag *DPG;


   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      DPG = (dag *) Region->GetDAG();
      DPG->PrintDag();
   }
}

//HZ: 08/25/00
//Add function to print DAG to a file stream
void PrintDagsForProc( legoProc *ProcPtr, ofstream & os1 )
{
   int i, RegionCount;
   legoRegion *Region;
   dag *DPG;

   os1 << "Proc " << ProcPtr->GetProcName() << endl;
   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) 
   {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      os1 << endl << "Region " << Region->GetRegionId() << endl;      
      DPG = (dag *) Region->GetDAG();
      if (DPG == NULL) 
          LegoFatal("", "DAG not constructed yet.\n");
      DPG->PrintDag(os1);      
   }
}


// SetNodeHeightsAndDepthsForRegion: as the name says, sets these fields for
//    use by later scheduling passes
void SetNodeHeightsAndDepthsForRegion( legoRegion *Region )
{
   dag *DPG = (dag *) Region->GetDAG();
 
   DPG->SetNodeHeights();
   DPG->SetNodeDepths();
}


// SetNodeHeightsAndDepthsForProc: as the name says, sets these fields for
//    use by later scheduling passes
void SetNodeHeightsAndDepthsForProc( legoProc *ProcPtr )
{
   int i, RegionCount;
   legoRegion *Region;
 
   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      SetNodeHeightsAndDepthsForRegion( Region );
   }
}


// SetValuesForRegion: as the name says, set Value field for each Op for
//    use by later scheduling passes
void SetValuesForRegion( legoRegion *Region, knobs *Knobs )
{
   dag_node_ordering *NodeOrder = new dag_node_ordering( Region );

   NodeOrder->SetKnobs( Knobs ); 
   NodeOrder->SetDagValues();
   delete NodeOrder;
}


// SetValuesForProc: as the name says, set the Value field for each Op for
//    use by later scheduling passes
void SetValuesForProc( legoProc *ProcPtr, knobs *Knobs )
{
   int i, RegionCount;
   legoRegion *Region;



   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      SetValuesForRegion( Region, Knobs );
   }
}


// MakeValueListForRegion: do a Value-based sorting on nodes
//    within the Region
void MakeValueListForRegion( legoRegion *Region )
{
   dag *DPG = (dag *) Region->GetDAG();
 
   DPG->SortByValue();
}


// MakeValueListForProc: do a Value-based sortiing on nodes
//    within the Proc
void MakeValueListForProc( legoProc *ProcPtr )
{
   int i, RegionCount;
   legoRegion *Region;


   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      MakeValueListForRegion( Region );
   }
}

// RemoveExtraAttributes: deletes non-standard attributes from Ops in Proc
void RemoveExtraAttributes( legoProc *Proc )
{

  legoOp *op; 

  op = Proc->GetListOpPtr();
  while (op != NULL) {
    RemoveLcAttribute( "need_duplicate", op, Proc );
    RemoveLcAttribute( "orig_fallthru_pred", op, Proc );
    RemoveLcAttribute( "no_longer_speculative", op, Proc );
    // RemoveLcAttribute( "inter-cluster-copy", Op, Proc );
    // RemoveLcAttribute( "clusterid", Op, Proc );
    op = op->GetListOpPtr(); 
  }
}


// DeleteRegionDag: Delete the dag for the block
void DeleteRegionDag( legoRegion *Region )
{
   dag *DPG = (dag *) Region->GetDAG();

   if ( DPG != NULL ) delete DPG;
}


// DeleteDagsInProc: Delete all dags in the proc
void DeleteDagsInProc( legoProc *ProcPtr )
{
   int i, RegionCount;
   legoRegion *Region;


   for ( i = 0, RegionCount = ProcPtr->GetCount(); i < RegionCount; i++ ) {
      Region = (legoRegion *) ProcPtr->GetItem( i );
      DeleteRegionDag( Region );
   }
}

---