dag.H

Go to the documentation of this file.

// dag.H
//
// 2/11/98 WAH:  Broke away from Scheduler package; minor patching up.
// 3/17/98 WAH:  Made drawing routine a friend.
// 3/23/98 WAH:  Added RemoveUndefPredecessors.
// 3/27/98 WAH:  Fixed declaration of DrawDAG (shouldn't contain default
//               parameter.)
// 4/1/98 WAH:   Removed explicit call to DagHashTable destructor in
//               CopyDefUseTable.

#ifndef _INCLUDE_DAG_H_
#define _INCLUDE_DAG_H_

#define IA64_SUPPORT //HZ: enable the setting of inp_start, inp_end, etc.,
        //intead of using INT_P1, INT_P2, etc.

/*
Open Issues
===========

o When building the DAG, various pointers into MasterList must be
  maintained. The <vector> class does not gaurantee that an iterator
  that points into the list will point to the same item across vector
  insertions. How can I overcome this? Use the 'reserve' function. Could
  I alternatively use a ptr to a MasterList element instead?

4/2/98 WAH
  The answer is to reserve big enough to avoid reallocation. If
  a vector is reallocated/expanded, iterators will become invalid;
  otherwise, a push_back is completely safe, while an insert invalidates
  iterators at the insertion point and after. An alternative is to
  work things so you can refresh the iterators after an insertion.

  Using a pointer won't work. Reallocation will physically relocate the
  vector somewhere else in memory, leaving a bunch of dangling pointers.

  I haven't looked into the code enough to be sure Sanjeev has overcome
  this ... I assume he has, since the DAG seems to build OK. Anyway,
  future developers should keep this in mind if things start going
  screwy. :)
*/


/* The Eos STL dist is in /afs/eos.ncsu.edu/contrib/gcc272/lib/g++-include */
#include <stl.h>
#include "TinkerKnobs.H"
#include "lego.H"
// #include <machine.h>
class machine;  // wah: replaced include with forward declaration
// #include <vcgdraw.H> wah: not referenced in this file

/*
The DAG is implemented as an adjacency list. The list has additional
pointers that allow easy graph traversal from an element of one adjacency
list to the all of the successors/predecessor of that element.

Ths list is organized as:


     Master     Small
     List       List
      _____     _       -
     |     |   |------>|-----> NULL  The list end
     |    ---->| |     | |
     |  |  |   | |<------|
      --|--     -       -
        |
        |       Small
       \ /      List
      _____     _       -
     |     |   |------>|-----> NULL  The list end
     |    ---->| |     | |
     |  |  |   | |<------|
      --|--     -       -
        |
        |
       \ /
       NULL

Both sets of lists are actually organized as lists, as defined within
the C++ STL.
*/

/* DAG-specific routines */
#include "DagNode.H"
#include "SmallListNode.H"
#include "SmallListElement.H"
#include "BigListElement.H"
#include "DagHashTable.H"

//HZ:

#define MAX_NUM_PATH 1000

// wah: some forward declarations for classes which are friends of dag
class dag_node_ordering;
class list_scheduler;
class bottom_up_greedy;

// PrintTable: print entries in the def-use table
void PrintTable( DagHashTable *TablePtr );


/* The actual DAG */
class dag {

friend class dag_node_ordering;
friend class list_scheduler;
friend class bottom_up_greedy;
friend void DrawDAG (dag *, char *);

public:

   MainList MasterList;                 // The Master List



protected:

   const int Hash_Key_Size = 20, Hash_Reg_Size = 10;


#if defined (_STL_LIST_USED_)
#endif
   vector < BigListElement > Vector;
   int  VectorActive;

   legoRegion           *ParentRegion;
   enum regionTypes     ParentRegionType;

   vector <char *> HashKeyList;         // A list of hash keys

   int KillDagFlag;                     // Work-around destructor bug

   MainList::iterator MainListIter,     // For misc.
                      BranchBarrier;    // To control branch speculation

   vector <MainList::iterator> StoreList; // non-load store barriers
   vector <MainList::iterator> LoadList;  // list of loads

   DagHashTable::const_iterator LookupIter;// For table lookups
   RegisterInfo WriteElement,           // For Table insertions
                ReadElement;            // For Table reads

   DagHashTable Table;                  // Def-use table

   int NumNodes;                        // # nodes in the Master List
   double ProfileWeight;                // Profile weight of region, for
                                        // DAGs built from a single basic
                                        // block.

   machine *Machine;                    // For latency-weighted calculations

   int InternalNodes;

   // mdj 5/14/98 setBrDepsFirst patch
   int NotRoot;

   // mdj 6/9/98 prev_block_ptr used to create next_block_int attribute
   legoRegion *prev_block_ptr;

   char *WriteHashKey, *ReadHashKey,
        *WriteHashReg, *ReadHashReg;    // Aid in creating hash keys
private:   
   //HZ: added for calculating the max critical path height
   double ave_max_height;
   double * max_heights;
   int num_path;
   int * path_BB_ids; 
   double * weights;
   int * num_ops; 
   
   //HZ: These parameters are added to make dag analysis aware of the use &
   // define of brl & ret.
   // These parameters should be set at the construction
   int inp_start, inp_end, ret_start, ret_end, fp_ret_start, fp_ret_end;
   
   
   void SetNodeHeightsPath(int end_bb_id);
   int SetNodeHeightPath(vector < BigListElement >::iterator, legoRegion
           *exit_reg);
protected:
   MainList::iterator   InsertOp( BigListElement Element );
   void     SetBrDeps( MainList::iterator MasterListIter );
   // mdj 5/14/98 setBrDepsFirst patch
   void     SetBrDepsFirst( MainList::iterator MasterListIter, legoRegion *Region );
   void     SetPBRDeps( MainList::iterator MasterListIter, legoRegion *Region );

   void     SetVectorPtrs( vector < SmallListElement > * );
   void     SetSublistPtrs( VectorList *V );
   void     CopyVectorToVector( VectorList *v1, VectorList *v2 );
   void     CopyListToVector( MainList::iterator, MainList::iterator );
   void     CopyListToVector();

   void     AnalyzeFlowDep( legoOprd *, MainList::iterator );
   int      OutputDeps( legoOprd *, MainList::iterator );
   int      AntiDeps( legoOprd *, MainList::iterator );

   void     FlowDeps( MainList::iterator, BigListElement * );
   void     OutputAntiDeps( MainList::iterator, BigListElement * );
   void     UpdateUseStatus( MainList::iterator, BigListElement * );
   void     RemoveUndefPredecessors();

   void     ConstructLinearDag( legoRegion * );
   void     ConstructTreeDag(legoRegion *, DagHashTable *, 
                             vector <MainList::iterator> *, 
                             vector <MainList::iterator> *);

   int      SetNodeHeight( vector < BigListElement >::iterator );
   int      SetNodeDepth( vector < BigListElement >::iterator );

   void     PrintVectorDag( vector < BigListElement> * );
   
   //HZ: 08/24/00
   void     PrintVectorDag( vector < BigListElement> *, ofstream & os1);
   
   void     ListIntegrity( vector < BigListElement > * );

   void     BubbleSort( vector < BigListElement >::iterator,
                        vector < BigListElement >::iterator,
                        int (*)( BigListElement *, BigListElement * ) );
   void     BubbleSort( int (*)( BigListElement *, BigListElement * ) );

public:

   // Constructors and functions to help copy info from this dag

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

   // Constructor
   dag(int Inp_start, int Inp_end, int Ret_start, int Ret_end, int Fp_ret_start,
        int Fp_ret_end)
   {
       NumNodes = KillDagFlag = 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;
   }

   // Constructor
   dag( machine *, int Inp_start, int Inp_end, int Ret_start, int Ret_end, int Fp_ret_start,
        int Fp_ret_end );

   // Constructor that takes a machine description and a knobs structure
   dag( machine *, knobs *, int Inp_start, int Inp_end, int Ret_start, int Ret_end, int Fp_ret_start,
        int Fp_ret_end );

   // Copy constructor that inits the adjacency list from the given dag
   void CopyGraph( dag *src );

   // Copy constructor that inits the def-use table from the given dag
   void CopyDefUseTable( dag *src )
   {
     //      Table.map( src->Table);
     //     Table.~DagHashTable();  // Remove old elements commented 4/1/98
     Table = src->Table;  // wah 3/24/98
   }

   // GetMachine
   machine *GetMachine()                { return Machine; }

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


   // Destructors and functions to reset/free data structures

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

   // Destructor. Calls KillDag().
   ~dag();

   // DeleteDefUseTable: delete the def-use table
   void     DeleteDefUseTable();

   // DeleteGraphNodes: delete the adjacency list
   void     DeleteGraphNodes();

   // The effective destructor. Calls DeleteDefUseTable() and
   // DeleteGraphNodes().
   void     KillDag();

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


   // Dag info
   Stats();

   void     SetNumNodes( int Value )            { NumNodes = Value; }
   int      GetListSize()                       { return NumNodes; }

   void     ConstructDag( legoRegion * );
   vector < BigListElement > *GetList()
   {
   #if defined (_STL_LIST_USED_)
      return &Vector;
   #else if defined (_STL_VECTOR_USED_)
      return &MasterList;
   #endif
   }

   void     FullyResolvePredicates( legoRegion *, legoOp* );

   void     SortByOpId();
   void     SortByHeight();
   void     SortByValue();

   void     SetNodeHeights();
   void     SetNodeDepths();
   
   //HZ:
   void     ResetNodeHeights();
   void     ResetNodeDepths();
   
   void MaxHeights(); //calculate the maximum heights for each path and the
                          //average as well
   double GetAveMaxHeight() {return ave_max_height;}
   int GetNumPath() {return num_path;}
   int GetAveWidth() 
   {
       int ave_width = 0;
       for(int i = 0; i < num_path; i++)
       {
           ave_width += num_ops[i];
       }
       if(num_path > 0)
           return ave_width/num_path;
       else
           return 0;
   }

   void     PrintDag();
   void     PrintGraphicDag( int print_control_edges = 1 );
   void     PrintDag(ofstream & os1);
   void     PrintDefUseTable()                  { PrintTable( &Table ); }

   void     ListIntegrity();

   // RemoveDepBetweenOps: remove any edges of type edge_type between Op 1 &
   //   Op2. The routine expects Op2 to be a successor of Op1.
   //   return code 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 RemoveDepBetweenOps( legoOp *Op1, legoOp *Op2, enum edgeTypes dep_type );
   int AreVectorsIndependent(bitvector *vector1, bitvector *vector2, int vector_size);
   int AreOpsDependent(legoOp *Op1, legoOp *Op2);
};

#endif  // _INCLUDE_DAG_H_

---