dag_utilities.C

Go to the documentation of this file.

/*

File: dag_utilities.C

Purpose: Contains utility functions that are part of the dag class and
         are otherwise useful.

ae: modif heights and depths definition to count the latency along
    an anti dep to be 0 cycles (Jan 30, 1998)
2/11/98 WAH:  Broke away from Scheduler package; minor patching up.
4/1/98 WAH:   Refreshed Back2 iterator in RemoveDepBetweenOps.


*/

static int counter;


// ListIntegrity:
void dag::ListIntegrity()
{
#if defined( _STL_LIST_USED_)
   ListIntegrity( &Vector );
#else if defined (_STL_VECTOR_USED_)
   ListIntegrity( &MasterList );
#endif
}


// ListIntegrity
void dag::ListIntegrity( vector < BigListElement > *V )
{
   int i, j, Size1, Size2, OpId;
   BigListElement Element, SearchElement;
   vector < BigListElement >::iterator BigIter;
   vector < SmallListElement > *ListPtr;
   vector < SmallListElement >::iterator Front, Back;
   SmallListElement SmallElement;


   for( i = 0, Size1 = V->size(); i < Size1; i++ ) {
      Element = (*V)[ i ];
      ListPtr = Element.Predecessors;
      for( Front = ListPtr->begin(), Back = ListPtr->end();
           Front != Back; Front++ ) {
         OpId = (*Front).GetOp()->GetOpId();
         BigIter = FindNode( OpId, V );
         if ( BigIter == V->end() )
            {cerr << " ** ERROR: OpId " << OpId << " not found!\n";};
      }

      ListPtr = Element.Successors;
      for( Front = ListPtr->begin(), Back = ListPtr->end();
           Front != Back; Front++ ) {
         OpId = (*Front).GetOp()->GetOpId();
         BigIter = FindNode( OpId, V );
         if ( BigIter == V->end() )
            {cerr << " ** ERROR: OpId " << OpId << " not found!\n";};
      }

   } // for
}


// SetNodeHeight: sets the height for the Node
int dag::SetNodeHeight( BigListElement *Node )
{
   int height, tmp, max, latency, OpId;
   vector < SmallListElement >::iterator Front, Back;
   vector < BigListElement >::iterator BigIter;


   // If the height has been set, return the height
   if ( (height=Node->GetHeight()) != -1 ) {
      derr( "<> SetNodeHeight: Node " << Node->GetOp()->GetOpId()
            << " already visited, height " << height << "\n" );
      return height; 
   }

   // If it is an exit node, set the height and return
   if ( Node->NumSuccessors() == 0 ) {
      height = Machine->opLatency( Node->GetOp() );
      Node->SetHeight( height );
      derr( "<> SetNodeHeight: exit Node " << Node->GetOp()->GetOpId()
            << " height set to " << height << ", " << ++counter
            << " node done\n" );
      return height; 
   }

   latency = Machine->opLatency( (*Node).GetOp() );

   // If the node has children, process the children
   for ( max = 0, Front = Node->Successors->begin(),
         Back = Node->Successors->end(); Front != Back; Front++ ) {
      OpId = (*Front).GetOp()->GetOpId(); 
#if defined (_STL_LIST_USED_)
      BigIter = FindNode( OpId, &Vector );
#else if defined (_STL_VECTOR_USED_)
      BigIter = FindNode( OpId, &MasterList );
#endif
      tmp = SetNodeHeight( &(*BigIter) );
  
      //ae
      switch( (*Front).GetDependencyType() ) {
        case ET_REGANTI: tmp += 0; break;
        case ET_REGFLOW: tmp += latency; break;
        case ET_REGOUT:  tmp += latency; break;
        case ET_MEM:     tmp += latency; break;
        case ET_CNTL:    tmp += latency; break;
        default:         tmp += latency; break;
      }

      max = max > tmp ? max : tmp;
   }

   // Set the node height
   //ae (latency integrated in the max computation)
   //height = latency + max;
   height = max;

   (*Node).SetHeight( height );

   derr( "<> SetNodeHeight: node " << (*Node).GetOp()->GetOpId()
         << " has height " << height << ", latency " << latency
         << ", " << ++counter << " node done\n" );
   return height;
}

//HZ:
// SetNodeHeightPath: sets the height for the Node based on the control path that
// ended with exit_bb_id
int dag::SetNodeHeightPath( BigListElement *Node, legoRegion * exit_reg )
{
   int height, tmp, max, latency, OpId;
   vector < SmallListElement >::iterator Front, Back;
   vector < BigListElement >::iterator BigIter;


   // If the height has been set, return the height
   if ( (height=Node->GetHeight()) != -1 ) {
      derr( "<> SetNodeHeight: Node " << Node->GetOp()->GetOpId()
            << " already visited, height " << height << "\n" );
      return height; 
   }

   bool on_path = false; //check whether the node is on the path or not
   legoRegion * par_reg = (legoRegion *)Node->GetOp()->GetParentBlockPtr();
   legoRegion * temp_reg = exit_reg;
   while(on_path == false)
   {
       if(temp_reg == par_reg)
       {
           on_path = true;
           break;
       }
       if(ParentRegion->GetRegionType() == RT_TREE)
           if(temp_reg == ((legoTreegion *) ParentRegion)->GetRoot())
               break;
       else
           if(temp_reg == ParentRegion)
               break;
       temp_reg = temp_reg->GetParents()->GetRegionPtr(); //a BB in a treegion
                                       //only has one parent       
   }
   
   if(on_path == false) 
   {
       Node->SetHeight(0);
       return(0); //make sure the followig process is based on
           //the fact that Node is on the path
   }
   
   //check whether any of its successors is on the path
   bool s_on_path = false;
   vector < SmallListElement >::iterator Front1, Back1;
   for (Front = Node->Successors->begin(),
         Back = Node->Successors->end(); Front != Back; Front++ )
   {
       legoOp * s_op = (*Front).GetOp();
       legoRegion * par_reg_1 = (legoRegion *)s_op->GetParentBlockPtr();
       legoRegion * temp_reg_1 = exit_reg;
       while(s_on_path == false)
       {
           if(temp_reg_1 == par_reg_1)
           {
               s_on_path = true;
               break;
           }
           if(ParentRegion->GetRegionType() == RT_TREE)
               if(temp_reg_1 == ((legoTreegion *) ParentRegion)->GetRoot())
                   break;
           else
               if(temp_reg_1 == ParentRegion)
                   break;
           temp_reg_1 = temp_reg_1->GetParents()->GetRegionPtr(); //a BB in a treegion
                                       //only has one parent       
       }
       if(s_on_path) break;
   }
   
   
   // If it is an exit node, set the height and return
   if ( Node->NumSuccessors() == 0 || s_on_path == false) {
      height = Machine->opLatency( Node->GetOp() );
      
      //HZ: since such dummy branches could be replaced as a real branch
      if(Node->GetOp()->IsDUMMYBROp())
          height = 1;
      
      
      Node->SetHeight( height );
      derr( "<> SetNodeHeight: exit Node " << Node->GetOp()->GetOpId()
            << " height set to " << height << ", " << ++counter
            << " node done\n" );
      return height; 
   }

   latency = Machine->opLatency( (*Node).GetOp() );
   
//   if((*Node).GetOp()->GetOpcode() == MOVE)
//   {
       //In scheduling the MOVE operation has zero latency
//       latency = 0;
//   }

   // If the node has children, process the children
   for ( max = 0, Front = Node->Successors->begin(),
         Back = Node->Successors->end(); Front != Back; Front++ ) {
      OpId = (*Front).GetOp()->GetOpId(); 
#if defined (_STL_LIST_USED_)
      BigIter = FindNode( OpId, &Vector );
#else if defined (_STL_VECTOR_USED_)
      BigIter = FindNode( OpId, &MasterList );
#endif
      tmp = SetNodeHeightPath( &(*BigIter), exit_reg );
  
      //ae
      switch( (*Front).GetDependencyType() ) {
        case ET_REGANTI: tmp -= latency; break;
        case ET_REGFLOW: 
                if((*Front).GetOp()->IsBRLOp())
                {
                    //the flow dep based on int_ps or dbl_ps
                    //This is added according to the scheduler.
                    // In the scheduler, such two operations can be scheduled at
                    // same cycle. ADD int_p1 = r1, r2   brl b1.
                    tmp += latency - 1;
                }
                else
                    tmp += latency; 
                break;
        case ET_REGOUT:  tmp -= latency; break;
        case ET_MEM:     tmp += 0; break;
        case ET_CNTL:   //tmp += 0;
                if((*Front).GetOp()->IsBRLOp()) //IsStoreOp((*Front).GetOp()))
                        tmp += latency;
                else
                        tmp += 0; 
                break; //control dep is considered with Flow
                                //dep of cmpps and cmpp - br
        default:         cout << "<SetNodeHeightPath> Unknown deps.\n"; tmp += 0; break;
      }

      max = max > tmp ? max : tmp;
   }

   // Set the node height
   //ae (latency integrated in the max computation)
   //height = latency + max;
   height = max;

   (*Node).SetHeight( height );

   derr( "<> SetNodeHeight: node " << (*Node).GetOp()->GetOpId()
         << " has height " << height << ", latency " << latency
         << ", " << ++counter << " node done\n" );
   return height;
}


// SetNodeHeights: sets the height for every node in the dag
void dag::SetNodeHeights()
{
   vector < BigListElement >::iterator Front, Back;

   counter = 0;
   derr( ">> SetNodeHeights - BEGIN\n" );
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
      if ( (*Front).NumPredecessors() == 0 ) {
         derr( "   Starting at entry node " << (*Front).GetOp()->GetOpId()
               << "\n" );
         SetNodeHeight( &(*Front) );
      }

   derr( "<< SetNodeHeights - END\n" );
}


//HZ:
// ResetNodeHeights: sets the height for every node in the dag
void dag::ResetNodeHeights()
{
   vector < BigListElement >::iterator Front, Back;

   counter = 0;
   derr( ">> ResetNodeHeights - BEGIN\n" );
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
         (*Front).SetHeight(-1);

   derr( "<< ResetNodeHeights - END\n" );
}

// SetNodeHeights: sets the height for every node in the dag
void dag::SetNodeHeightsPath(int exit_bb_id)
{
   vector < BigListElement >::iterator Front, Back;

   counter = 0;
   derr( ">> SetNodeHeights - BEGIN\n" );
   
   //find the BB point with exit_bb_id

   legoRegion * exit_reg = NULL;
   if(ParentRegion->GetRegionType() == RT_TREE)
   {
       for(int i = 0; i < ParentRegion->GetCount(); i++)
       {
           legoRegion * reg1 = (legoRegion *)ParentRegion->GetItem(i);
           assert(reg1->GetRegionType() == RT_BB);
           if(reg1->GetRegionId() == exit_bb_id) 
           {
               exit_reg = reg1;
               break;
           }
       }
   }
   else if(ParentRegion->GetRegionType() == RT_BB && exit_bb_id ==
       ParentRegion->GetRegionId())
   {
       exit_reg = ParentRegion;
   }
   assert(exit_reg != NULL);
   
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
      if ( (*Front).NumPredecessors() == 0 ) {
         derr( "   Starting at entry node " << (*Front).GetOp()->GetOpId()
               << "\n" );
         SetNodeHeightPath( &(*Front), exit_reg );
      }

   derr( "<< SetNodeHeights - END\n" );
}


// SetNodeDepth: sets the height for the Node
int dag::SetNodeDepth( BigListElement *Node )
{
   int depth, tmp, max, latency, OpId;
   vector < SmallListElement >::iterator Front, Back;
   vector < BigListElement >::iterator BigIter;


   // If the height has been set, return the height
   if ( (depth=Node->GetDepth()) != -1 ) {
      derr( "<> SetNodeDepth: node " << Node->GetOp()->GetOpId()
            << " already visited, depth " << depth << "\n" );
      return depth; 
   }

   // If it is an entry node, set the depth and return
   if ( Node->NumPredecessors() == 0 ) {
      depth = Machine->opLatency( Node->GetOp() );
      Node->SetDepth( depth );
      derr( "<> SetNodeDepth: entry node " << Node->GetOp()->GetOpId()
            << " depth set to " << depth << ", " << ++counter
            << " node done\n" );
      return depth; 
   }

   derr( ">> SetNodeDepth: processing node " << Node->GetOp()->GetOpId()
         << "\n" );
   // If the node has predecessors, process the predecessors
   for ( max = 0, Front = Node->Predecessors->begin(),
         Back = Node->Predecessors->end(); Front != Back; Front++ ) {
      OpId = (*Front).GetOp()->GetOpId(); 
      derr( "   ** Op " << Node->GetOp()->GetOpId() 
            << ": Process predecessor " << OpId << "\n" );
#if defined (_STL_LIST_USED_)
      BigIter = FindNode( OpId, &Vector );
#else if defined (_STL_VECTOR_USED_)
      BigIter = FindNode( OpId, &MasterList );
#endif
      tmp = SetNodeDepth( &(*BigIter) );

      //ae 
      //time of predecessor should not include its latency for anti dep
      int predecessor_latency = Machine->opLatency( (*BigIter).GetOp() );
      switch( (*Front).GetDependencyType() ) {
        case ET_REGANTI: tmp -= predecessor_latency; break;
        case ET_REGFLOW: break;
        case ET_REGOUT:  break;
        case ET_MEM:     break;
        case ET_CNTL:    break;
        default:         break;
      }
      max = max > tmp ? max : tmp;
   }

   // Set the node height
   latency = Machine->opLatency( (*Node).GetOp() );
   depth = latency + max;
   (*Node).SetDepth( depth );

   derr( "<< SetNodeDepth: node " << (*Node).GetOp()->GetOpId()
         << " has depth " << depth << ", latency " << latency
         << ", " << ++counter << " node done\n" );
   return depth;
}


// SetNodeDepths: sets the depth for every dag node
void dag::SetNodeDepths()
{
   vector < BigListElement >::iterator Front, Back;

   derr( ">> SetNodeDepths - BEGIN\n" );
   counter = 0;
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
      if ( (*Front).NumSuccessors() == 0 ) {
         derr( "   Starting at exit node " << (*Front).GetOp()->GetOpId()
               << "\n" );
         SetNodeDepth( &(*Front) );
      }

   derr( "<< SetNodeDepths - END\n" );
}

//HZ:
// ResetNodeDepths: sets the height for every node in the dag
void dag::ResetNodeDepths()
{
   vector < BigListElement >::iterator Front, Back;

   counter = 0;
   derr( ">> ResetNodeHeights - BEGIN\n" );
#if defined (_STL_LIST_USED_)
   for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
   for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
         (*Front).SetDepth(-1);

   derr( "<< ResetNodeDepths - END\n" );
}

//Calculate the average maximal crital path height: i.e.,
// Calculate the maximal critical path height for each possible execution path,
// then calculate the average based on execution frequency
// Before this function is called, the dag should have constructed for the
// region and the heights has not been set to the dag nodes.
void dag::MaxHeights()
{
    if(num_path == 0) return; // the DAG has not been setup
    
    vector < BigListElement >::iterator Front, Back;
    
    if(ParentRegion->GetRegionType() == RT_BB)
    {
        assert(num_path == 1);
        //calculate the DDG heights
        SetNodeHeightsPath(path_BB_ids[0]);
        //find the maximum
        double max_h = 0;
#if defined (_STL_LIST_USED_)
        for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
         Front++ )
#else if defined (_STL_VECTOR_USED_)
        for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
         Front++ )
#endif
        {
            if((*Front).GetHeight() > max_h)
                max_h = (*Front).GetHeight();
        }
        max_heights[0] = max_h;
        ave_max_height = max_h;
    }
    else if(ParentRegion->GetRegionType() == RT_TREE)
    {
        double total_weight = 0;
        ave_max_height = 0;
        
            //SetNodeHeights(); 
            //ofstream os1("tree54_1.txt");
            //PrintDag(os1);        
            //os1.close();
        
        
        //calculate the height for each path
        int i;
        for(i = 0; i < num_path; i++)
        {
            double max_h = 0;       
            if(weights[i] > 0)
            {
                ResetNodeHeights();
                SetNodeHeightsPath(path_BB_ids[i]);
            
            //if(ParentRegion->GetRegionId() == 131 && i == 3)
            //{
            //     ofstream os2("tree131_4.txt");
            //     PrintDag(os2);           
            //     os2.close();
            //}
            
            //if(ParentRegion->GetRegionId() == 145 && i == 3)
            //{
            //     ofstream os2("tree145_4.txt");
            //     PrintDag(os2);           
            //     os2.close();
            //}
            
            //find the maximum along this path
             
#if defined (_STL_LIST_USED_)
                for ( Front = Vector.begin(), Back = Vector.end(); Front != Back;
                Front++ )
#else if defined (_STL_VECTOR_USED_)
                for ( Front = MasterList.begin(), Back = MasterList.end(); Front != Back;
                Front++ )
#endif
                {
                    if((*Front).GetHeight() > max_h)
                        max_h = (*Front).GetHeight();
                }
            } //end of if weights[i] > 0
            max_heights[i] = max_h;
            ave_max_height += max_h * weights[i];
            total_weight += weights[i];
        }
        
        for(i = 0; i < num_path; i++)
        {
            double width_d = num_ops[i] * 1.0 / (Machine->GetNumSlots() - 1);
            width_d = (width_d - (int)width_d > 0.09) ? (int)(width_d +
                    1) : width_d;
            if(max_heights[i] < width_d)
                max_heights[i] = width_d;
        }
        
        
        if(total_weight != 0)
            ave_max_height = ave_max_height / total_weight; 
        else 
            ave_max_height = 0;
    }
    else
    {
        cout << "<MaxHeights> Unsupported region type.\n";
        return;
    }
}    


// Copy constructor that inits the adjacency list from the given dag
void dag::CopyGraph( dag *src )
{
   int size1, size2;

   derr( ">> CopyGraph\n" );
#if defined (_STL_LIST_USED_)
   size1 = src->Vector.size();
   CopyBigVector( &(src->Vector), &Vector );
   size2 = Vector.size();
   VectorActive = 1;
#else if defined (_STL_VECTOR_USED_)
   size1 = src->MasterList.size();
   CopyBigVector( &(src->MasterList), &MasterList );
   size2 = MasterList.size();
#endif
   if ( size1 != size2 )
     {cerr << "ERROR: dag::CopyGraph - graph node counts do not match: "
       << size1 << " vs. " << size2 << "\n";};
   derr( "   src dag has " << size1 << " nodes, target dag has " << size2
        << " nodes\n" );
   derr( "<< CopyGraph\n" );
}


// RemoveDepBetweenOps: remove any edges of type edge_type between Op 1 & Op2
//   The routine expects Op2 to be a successor of Op1.
//   RC info:
//      0: edges deleted successfully
//     -1: Op1 isn't found
//     -2: edge from Op1->Op2 of dep_type isn't found
//     -3: edge from Op2->Op1 of dep_type isn't found
int dag::RemoveDepBetweenOps( legoOp *Op1, legoOp *Op2,
                              enum edgeTypes dep_type )
{
   VectorList::iterator Front, Back;
   vector < SmallListElement >::iterator Front2, Back2;

#if defined (_STL_LIST_USED_)
   for (Front = Vector.begin(); Front != Back; Front++) {
#else if defined (_STL_VECTOR_USED_)
   for (Front = MasterList.begin(); Front != Back; Front++)
#endif
      if ( (*Front).GetOp() == Op1 ) break;

   // If Op1 isn't found, return -1
   if ( Front == Back ) return -1;

   // Search Op1's successors
   for ( Front2 = (*Front).Successors->begin(),
         Back2 = (*Front).Successors->end(); Front2 != Back2; Front2++ ) {

      // Search for the correct dependency type and Op
      if ( (*Front2).GetDependencyType() == dep_type &&
           (*Front2).GetDagEntry()->GetOp() == Op2 ) {

         VectorList::iterator Op2_location = (*Front2).GetDagEntry();

         (*Front).Successors->erase( Front2 );
         // Refresh Back2 now, since erase invalidates it. 4/1/98 wah
         Back2 = (*Front).Successors->end();
         SetVectorPtrs( (*Front).Successors );

         // Now find the edge in the other direction and delete it also
         for ( Front2 = (*Op2_location).Predecessors->begin(),
               Back2 = (*Op2_location).Predecessors->end(); Front2 != Back2;
               Front2++ )
            if ( (*Front2).GetDependencyType() == dep_type &&
                 (*Front2).GetDagEntry()->GetOp() == Op1 ) {
               (*Op2_location).Predecessors->erase( Front2 );
               // Refresh Back2 now, since erase invalidates it. 4/1/98 wah
               Back2 = (*Op2_location).Predecessors->end();
               SetVectorPtrs( (*Op2_location).Predecessors );
               break;
            }
         if ( Front2 == Back2 ) return -3;
         return 0;
      }
   }
   return -2;
}


/********************** General utilities *******************/

/********** Begin *************/


// PrintMapEntry: print one entry in the STL map
static void PrintMapEntry( char *Key, RegisterInfo Entry )
{
//   MainList::iterator ListIter;


//   ListIter = Entry.DefiningOp;
   cout << "\n Key " << Key << "\n";
   cout << "\t RFType " << Entry.RFType << ", Regid " << Entry.Regid << "\n";
   cout << "\t Defining OpId " << Entry.DefiningOpId;
//   cout << ", Again " << (*ListIter).GetOp()->GetOpId() << "\n";
//   cout << ", Again " << (*Entry.DefiningOp).GetOp()->GetOpId() << "\n";

//   ListIter = Entry.UsingOp;
   cout << "\t Using OpId " << Entry.UsingOpId;
//   cout << ", Again " << (*ListIter).GetOp()->GetOpId() << "\n\n";
//   cout << ", Again " << (*Entry.UsingOp).GetOp()->GetOpId() << "\n\n";
}


// PrintTable: print entries in the given map structure
void PrintTable( DagHashTable *TablePtr )
{
   DagHashTable::iterator Front, Back;


   cout << "\nPrinting def-use table\n"; 
   cout << "\n----------------------\n"; 
   for ( Front = TablePtr->begin(), Back = TablePtr->end(); Front != Back;
         Front++ )
      PrintMapEntry( (*Front).first, (*Front).second );
   cout << "\n---------- END -------\n"; 
}

/*********** End **************/

---