op_scheduler.H

Go to the documentation of this file.

//
// File:
//
//      op_scheduler.H
//
// Purpose:
//
//      Defines class structure for an implementation of
//      operation scheduling. 
//
// Author:
//
//      Mark C. Toburen
//
// History:
//
//      02/15/02 - Created.
//

#ifndef _OP_SCHEDULER_H_
#define _OP_SCHEDULER_H_

#include <stl.h>
#include "TinkerKnobs.H"
#include "dag.H"
#include "machine.h"
#include "chains.H"
#include "opList.H"
#include "rdef.H"

#define UNSCHEDULED            -1 // Marks an Op as unscheduled
#define RENAMING_CONFLICT       1 // Marks Ops that can't be renamed
#define NO_RENAMING_CONFLICT    0 // Marks Ops that can be renamed

class op_scheduler {

protected:

   // Pointers, etc to hold the prioritized op list of the current region being scheduled
   typedef vector <BigListElement>::iterator ListIterator;
   vector <BigListElement> *List;
   ListIterator ListHead, ListTail, ListPtr, Op;
   int ListCount;

   // Miscellaneous global variables used during scheduling
   int *operand_ready_times, current_block_int;
   legoOp *current_before_op;
   regionList *Children;
   vector <legoRegion *> ScheduleList;
   map <int, int> ScheduleTimes;

   // Pointers to the current region being scheduled, its DDG, the Machine model, and knobs
   legoRegion *Region;
   dag *DDG;
   machine *Machine;
   knobs *Knobs;

   // OpSched Knobs
   char *TreeTraversal;
   int PlayDoh,
       BypassLatency,
       CodeGen,
       NoSpeculation,
       AllowPBRSpeculation,
       AllowLoadSpeculation,
       AllowOnlySafeSpeculation,
       AllowDownwardCodeMotion,
       AllowMultiWayBR;

   // *********************************************************************************************
   // Renaming Functions
   //    - taken from list scheduler
   // *********************************************************************************************

   // HZ: Rename the dst reg of the op.
   // Based on the following conditions to decide which renaming scheme will be
   // used: 
   //      whether there are any uses of the dsts of the op that are outside
   //      of treegion, or there are any uses that are not descedant of the
   //      BB where the op resides in. => variable UseOutsideTreeOrNotDom
   // If UseOutsideTreeOrNotDom is false, the SimpleRename is used.
   // If UseOutsideTreeOrNotDom is true, more conditions need to be checked to
   // determine either SimpleRenameWithCopy or GlobalRename to be used:
   //     -Check whether Merge problem exists. If not, the global rename is
   //      used. 
   //     -If there is Merge Problem, add a copy op if the op
   //      has at least one use that it dominates and there is no use preceeds
   //      the op.
   //     -Otherwise, return RENAMING_CONFLICT.
   // For the input Hazardous, if set, the Merge problem is assumed to exist. So
   // the SimpleRenameWithCopy is favored. 
   //
   // Doubtful point: (future work on DDG & scheduler) DDG analysis of FICT
   int Rename(legoOp *op, int RegNum, legoRegion *proc_ptr, int Final_Pass,
              int IncMaxRegNum, int Hazardous);

   // HZ: Simple rename of the dsts of the op
   // If IncMaxRegNum == 1, rename the dsts of the op starting from reg no (++MaxRegNum)
   // If IncMaxRegNum == 0, rename the dsts of the op starting from RegNum.
   // Simple rename works by setting just the reg no of the dsts of the op and
   // update the DAG by remove the Output and Anti(def) dep.
   void SimpleRename(legoOp *op, int RegNum, int IncMaxRegNum);

   // HZ: Rename the uses of the def.
   // For each use of the def (obtained by GetDUChain), set the oprdRegNum to
   // RegNum , also call the function ReverseGlobalRename(use, RegNum, orig_def)
   // to rename the defs of the use.
   void ForwardGlobalRename(legoOprd *def, int RegNum, legoOprd *orig_def);
   
   // HZ: Rename the defs of the use
   // For each def of the use (obtained by GetUDChain), set the oprdRegNum to
   // RegNum, also call the function ForwardGlobalRename(def, RegNum, orig_def)
   // to rename the uses of the def.
   //
   // Doubtful point: the setting of the ReDoLiveVarsAfterGlobal
   void ReverseGlobalRename(legoOprd *use, int RegNum, legoOprd *orig_def);   
      
   // HZ: Rename the dsts of the op.
   // If IncMaxRegNum == 1, rename the dsts of the op starting from reg no (++MaxRegNum)
   // If IncMaxRegNum == 0, rename the dsts of the op starting from RegNum.
   // For each dst of the op, after change the reg no, call
   // ForwardGlobalRename(def, localRegNum, def) to rename the reg no globally
   // Then remove the output deps on its predecessors and the antidep based on
   // the renamed def.
   void GlobalRename(legoOp *op, int RegNum, int IncMaxRegNum);

   // HZ: AddCopyOps: add the copy (move) ops of the op.
   // There are two scenarios considered in this function:
   // (1) If the op is scheduled, we are dealing with the dominate parallelism
   //   (Doubtful point for me at this time)
   // (2) If the op is unscheduled, we are doing the first step of
   //    renamewithcopy.
   // For each dst reg of the op, a copy (move) inst is created with the
   //  consideration of the predicate register.(e.g., mov r1,
   //  r1 (p1) ). Then the related DU, UD chains, and the copy ops are appended
   //  at the end of the List. Also the predecessor & successor
   //  dependency relationships in DAG are updated. 
   int AddCopyOps(legoOp *op);

   // HZ: Return true if orig_def is descendant of the BB that the def resides in.
   // This happens when a use has two reaching defs. In the renaming process,
   // just rename one of them is not enough. Matt called this 'Merge Problem' as
   // two defs merge at the same use.
   // Because of the nature of treegion, this mergeing use should not be in the
   // same treegion as the two defs.
   int IsRemoteMergeProblem(legoOprd *def, legoOprd *orig_def);
   
   // HZ: Check whether a merge problem exist for the orig_def.
   // For each use of the orig_def (obtained by GetDUChain()), if the use is
   // preceeds the def (due to the loop back), or the use is not descendant of
   // the def, or the use is in different treegions, check the defs of this use
   // to see whether there is a merge problem between the orig_def and any of the
   // defs. Also checks whether the dst of the orig_def are among the live-ins
   // of the treegion. If so, return YES to show that there is merge problem.
   int IsMergeProblem(legoOprd *orig_def);

   // HZ: Check whether there are any dsts of the op that are live along the edge.
   int anyliveout(legoOp *op, opEdges *edge);

   // HZ: The define (renamed_def) has been renamed. So we need to remove the output
   // dep caused by this define. The function does so by checking both its
   // successors and predecessors. Then remove the corresponding dependence edge
   // in the DAG.
   void RemoveOutputDepsAfterRename(legoOprd *renamed_def);
   
   // HZ: Same as the one above except that it just checks predecessors.
   void RemoveOutputDepsAfterRenameUp(legoOprd *renamed_def);
   
   // HZ: Anti Dep removal after renaming the use.
   //   In the following scenario:
   //   Inst. a     <- r1, r2 ( use of r1 has been renamed)
   //               ... (other instructions)
   //   Inst. b  r1 <- (define of r1)
   //   Looking through the successors of instruction a, remove the anti
   //   dep if the reg no, reg type, Oprd File Type, etc. match. Remove the
   //   dep edge by removing the successor from instr a and removing predecessor
   //   from instr. b. Also it is noted that for brl op, when reg no is INTP1 ~
   //   DBL_P2. This dep edge is not removed.
   void RemoveAntiDepsAfterUseRename(legoOprd *renamed_use);
   
   // HZ: Anti Dep removal after renaming the def.
   //   In the following scenario:
   //   Inst. a     <- r1, r2 ( use of r1)
   //               ... (other instructions)
   //   Inst. b  r1 <- (define of r1 has been renamed)
   //   Looking through the predecessors of instruction b, remove the anti
   //   dep if the reg no, reg type, Oprd File Type, etc. match. Remove the
   //   dep edge by removing the successor from instr a and removing predecessor
   //   from instr. b. Also it is noted that for brl op, when reg no is INTP1 ~
   //   DBL_P2. This dep edge is not removed.
   void RemoveAntiDepsAfterDefRename(legoOprd *renamed_def);

   
   // copy_operand 
   //   Src = source operand
   //   Target = target operand
   //
   // Copies fields from Src to Target, assuming a register-type operand.
   // Does NOT copy next and prev pointers.  
   void copy_operand(legoOprd *Src, legoOprd *Target);
   
   // add_to_existing_attr
   //   Attr = existing live attribute
   //   NewOprd = new operand to add to attribute
   //
   // Adds a copy of the operand NewOprd to attribute Attr. If a copy
   // already resides in Attr, no action is taken.   
   void add_to_existing_attr(attrs *Attr, legoOprd *NewOprd);
   
   // create_new_attr
   //   Edge = edge on which to add live attribute
   //   Oprd = operand to add to attribute
   //   Proc = proc to whose dictionary to add edge
   //
   // Creates a new live attribute for Edge containing a copy of Oprd.
   void create_new_attr(opEdges *Edge, legoOprd *Oprd, legoProc *Proc);
                                
   // HZ: Fix the liveness after we move the op sepculatively up to a different
   // block from its orginal block (where before_op resides in).
   // Add the dsts of the op to live attr of the edges along the path from its  
   // original block to its current block. 
   int FixLiveVarsUp(legoOp *op, legoOp *before_op, legoProc *proc_ptr);
   
   // HZ: Fix the liveness after we move the op sepculatively down to a different
   // block from its orginal block.
   // Add the srcs of the op to live attr of the edge.
   // Note: if op is a brl instr, the src oprds are MACRO REGS (from INT_P1 to
   // DBL_P2)
   int FixLiveVarsDown(legoOp *op, opEdges *edge, legoProc *proc_ptr);

   // HZ: Add use to the live attr of the edges along the path from the BB where
   // before_op resides in to the BB where the use is.
   int FixLiveVarsFromUses(legoOprd *use, legoOp *before_op, legoProc *proc_ptr);
   
   // HZ: Determine whether there is any instruction in the path from op to
   // before op that uses the same dst reg as compare_dest.
   // (the path is obtained using GetPrevLink or GetInList()->GetOp)
   int AnyOutputDepsBetween(legoOp *op, legoOp *op_in_multiop, legoOprd *compare_dest);
   
   // DoTheMessyStuff: This code allows branches to be scheduled above other 
   // operations (or allows ops to move below branches) during scheduling.
   // This usually results in copy of ops (depending on liveness out of the 
   // branches. Priority lists, liveness, and reaching definitions are updated 
   // incrementally.    
   // HZ: As it is said by Matt, this function moves the br op upwards. So the input
   // op is a br instr. The other input proc_ptr is used for updating the       
   // liveness attr.
   // This is how it is done:
   //   1. Process the case that the op is the exit op of the treegion or the op
   //   is either BRU or DUMMY BR. (return RENAMING CONFLICT)
   //   2. If the op is either BRCT or BRCF, then there are two exit edges,
   //      called first edge and second edge of
   //      the op (not the treegion). Processing each instruction that
   //      is above the op but not scheduled yet (variable above_op):
   //      a. If above_op is brl or store, set the attribute
   //         "no_longer_speculative".
   //      b. Check the control dep between above_op and op using
   //         DPG->AreOpsDependent(above_op, op) (Doubtful point for me,
   //        ambiguous in what the function does exactly)
   //      c. If above_op has control dep on op, then if the above_op is live on
   //         second edge or the above_op is either store/brl, a duplicate of
   //         the above op will be created (duplicate the predicate needs more
   //         work). Then the duplicate will be placed after the C_MERGE op
   //         along the second edge. Also the related DU, UD chain and DDG will 
   //         be updated to reflect the correct dep info and the liveness on the
   //         second edge need to be fixed by calling FixLiveVarsDown.
   //      d. If above_op has control dep on op, then if the above_op is live on
   //         first edge or the above_op is either store/brl, the above op      
   //         will be moved after the C_MERGE op along the first edge (there is
   //         no needs to duplicate the above op as it is processed along the
   //         second edge already). Also the related DU, UD chain and DDG will 
   //         be updated to reflect the correct dep info and the liveness on the
   //         first edge need to be fixed by calling FixLiveVarsDown.
   //      e. Processing the dead ops by adding the DPRemoveAttribute and remove
   //         the dep with its successors and predecessors.
   int DoTheMessyStuff(legoOp *op, legoRegion *proc_ptr);

   // This routine returns the second, complementary destination for a CMPP op.
   // If the second predicate dest is OT_UNDEFINED, one will be created. 
   // if the CMPP opcode does not produce a complementary second dest, the 
   // opcode will be updated. The second destination oprd is returned.
   legoOprd* GetComplementaryDestOprd(legoOp *cmppop);
   
   // This routine cleans up ops and adds a dp_remove attr so that they 
   // can be remove after procedure is scheduled. Removing them earlier fucks 
   // up priority lists and RDefs() 
   // HZ: This is the way how to do it:
   //    1. RemoveOp and AddOp such that the infor in priority list & RDefs are
   //       not disturbed.
   //    2. Set the schedule time as zero for the op and add DPRemoveAttribute
   //    3. Remove the dep between the op and its successors & predecessors.
   void PrepareToDie(legoOp *op);
   
   // As a result of control flow changes during the forming of Multi-Way 
   // branches, some ops get re-targeted. Need to update the dag to reflect 
   // new predecessor ops for control deps in these cases. 
   //HZ: This is the way it works: (the op is branch op ??)
   //    1.  Find the C_MERGE op preceeding the op and set the inlist of the
   //        C_MERGE op to include the new_predecessor_op.
   //    2.  Remove old predecessor/successor pair (CONT Dep) between the op and
   //        the old_predecessor_op.
   //    3.  Add control dep between op & new_predecessor_op.
   //    4.  Repeat step 2,3 for the C_MERGE op.        
   void UpdatePredecessorBranch(legoOp *op, legoOp *old_predecessor_op, legoOp *new_predecessor_op);

   // Allowing Multi-Way branches to be formed during list scheduling requires
   // even MoreMessyStuff. 
   // Here I DoMoreMessyStuff.    
   // HZ: DoMoreMessy stuff happens when we are trying to schedule the branch op
   // (op) speculatively  (i.e., the current_before_op is in a different BB from
   //  the BB where the op resides in.) After calling the function
   //  DoTheMessyStuff to move its above ops into its descendant BBs, the op and
   //  the CMERGE_op are the instructions left in the BB. The function
   //  DoMoreMessyStuff moves such a br upwards to its parentBB to form a
   //  multiway br. (the resulted empty BB is removed ??)
   //  This is the way how to do it:
   //    If Final_Pass is not set, return RENAMING_CONFLICT.
   //    1.  Find the related pointers, including predecessor_branch_op,
   //        original_block, c_merge_op
   //    2.  Find the last op in the predecessor_branc_op's multiop, since we
   //        will move the op just before this last op.
   //    3.  Since we currently can not handle the jump table, check the
   //        attributes of the op and predecessor_branch_op. If ATTR_TBLNAME is
   //        found, return RENAMING_CONFLICT. (Jump table is a doubtful point
   //        for me)
   //    4.  If the op is either an DUMMY_BR or an BRU instr:
   //         a. Update the inlist of the C_MERGE op following the op so that
   //            the predecessor_branch_op is in the inlist. Also adjust the
   //            edge from op to its following C_MERGE so that the edge starts  
   //            from predecessor_branch_op to the C_MERGE. Delete the edge from
   //            the predecessor to the C_MERGE which is just before the op.
   //            Update the outlist of the predecessor_branch_op.
   //         b. Retarget PBR of predecessor_branch_op to the target of the op
   //            if the predecessor is a BRU instr or the op is in the taken
   //            path of the predecssor_branch_op. (Doubtful point: what if the
   //            op is on the fall-through path of the predecessor_branch_op?)
   //         c. PrepareToDie the op and its pbrrop (probably already scheduled)
   //    5.  If the op is a RTS instr:
   //         a. If the predecessor_branch_op is either an BRU or an DUMMY_BR,
   //            replace the predecessor_branch_op with this RTS by:
   //            Move the RTS to the last op found in step 2; Remove the control
   //            dep of the predecessor and its following C_MERGE and set the
   //            predicate of the predecessor_branch_op as the predicate of the
   //            RTS; PrepareToDie the predecessor_branch_op & its pbrr and free
   //            the resources that scheduled to the predecessor_branch_op (PBRR
   //            op takes no resources ?).
   //         b. If the predecessor_branch_op is cond br, change the
   //            predecessor_branch_op to an BRU instr and move the RTS up.
   //            Implementing this involves the following steps:
   //              b1. check whether the op is in the taken path of the
   //                  predecessor_branch_op
   //              b2. create a predicate for the RTS op that will be moved up.
   //                  Based on the CMPP op / orig_fall_through attribute of the
   //                  predecessor_branch_op, a predicate orpd is constructed.
   //              b3. Adjust the UD, DU chains to include the new predicate
   //                  oprd.
   //              b4. If the op is in the taken path of the
   //                  predecessor_branch_op and the predecessor_branch_op is
   //                  BRCF, set the predicate value of the RTS as the
   //                  complementary of what cmpp set. Also set the predicate
   //                  value of the predecessor_branch_op as what cmpp set.
   //              b5. If the op is in the taken path of the
   //                  predecessor_branch_op and the predecessor_branch_op is
   //                  BRCT, set the predicate value of the RTS as what cmpp set
   //                  and set the predicate value of the predecessor_branch_op
   //                  as the complementary of what cmpp set.
   //              b6. Process the other two cases of the RTS is in the fall
   //                  through path of the predecessor_branch_op which is either
   //                  BRCT or BRCF.
   //              b7. move up the RTS op, change the predecessor_branch_op 
   //                  (BRCT/BRCF) to BRU and update the the target of the
   //                  pbrr to point to the right CB.
   //    6.  If the op is a BRCT or BRCF instr:
   //         a. If the predecessor_branch_op is a BRU instr, we will retarget
   //            this predecessor_branch_op to the op's fall through block and
   //            change the the op to a BRU instr. Then mode the op upwards,
   //            update the control edges, UD DU chain for the predicates,
   //            update the predecessor/successor relationship, etc.
   //         b. If the predecessor_branch_op is a BRCT/BRCF instr, we will
   //            combine the op and predecessor_branch_op into a BRU and a BRC.
   //              b1. If the op is in the taken path of the
   //                  predecessor_branch_op, make the op a predicated BRU and
   //                  retarget the predecessor_branch_op to the fall-through
   //                  path of the op. Also do the related book-keeping
   //                  including: creating the new predicate, update the in/out
   //                  edges, in/out lists, DU/UD chain, predecessor/successor
   //                  dep relationship, change the op to BRU, etc.
   //              b2. If the op is in the fall-through path of the
   //                  predecessor_branch_op, change the predecessor_branch_op
   //                  to a BRU targeting at its orginal taken path. Change the
   //                  position of the op and predecessor_branch_op such that
   //                  the brc* happens at the end of the multiway branch. (o.w.,
   //                  yula may take the fall-thru path of the brc*
   //                  incorrectly.)
   //    7.  If the original block only has c_merge op left, destroy the
   //        cmerge_op and the BB. (actually, it is not deleted here, but the
   //        edge info. is updated. The actual removal happened after the
   //        procedure is scheduled (in Function ScheduleProc in schedule.C)).
   // 
   int DoMoreMessyStuff(legoOp *op, int Final_Pass);

   // HZ: Scan the current region under scheduling. For each br instr, if it is
   // not DUMMY_BR or dp_removed, find the the corresponding PBR and move the
   // PBR just before the br inst. If the need_duplicate attribute is set for
   // the PBR, duplicate the PBR and move the duplicated pbrr just before the
   // br.
   void PlacePBRsJustBeforeBranches(); 
   
   // HZ: Scan through the current region. Put the br to the end of the BB that
   // it resides in.
   void PlaceBranchesLast();


   // *********************************************************************************************
   // Scheduling Functions
   // *********************************************************************************************
   
   // MCT: ScheduleOp moves ops and sets schedule times once they can be scheduled. An
   // integer flag is returned indicating whether a renaming conflict was encountered.
   int ScheduleOp(legoOp *op, int cycle);

   // MCT: These functions traverse a treegion and schedule its constituent basic-blocks in
   // either a depth-first or breadth-first manner. One of these two functions is called from
   // ScheduleTree based on the "op-scheduler:tree-traversal" knob.
   void ScheduleTreeBreadthFirst();
   void ScheduleTreeDepthFirst(legoRegion *Block, int StartCycle);

   // *********************************************************************************************
   // Utility Functions
   // *********************************************************************************************

   //HZ: Note:
   // Matt used the word 'attribute' to describe the private/public variables of
   // the class. Also the word is used in the description of the Rebel code.
   // The meaning of the word in the comments should be clear from the context.

   // DescendantofBlock: Returns YES if this operation 
   // belongs to a block which is a descendant of the 
   // block identified by a pointer of value input_block_int.      
   int DescendantofBlock(int input_block_int, legoOp *op);

   // DescendantofCurBlockPtr: Returns YES if this operation 
   // belongs to a block which is a descendant of the 
   // block identified by the current_block_int attribute. 
   // It can be seen as a special case of the previous function with
   // the input_block_int is current_block_int and op as Node->GetOp().
   int DescendantofCurBlockPtr(ListIterator Node);

   // MCT: BuildList builds a valid sequential order of LegoOps for the op scheduler to consume.
   // At inception, BuildList will basically just spit out the list generated by the
   // DAG builder.
   // void BuildList();

   // MCT: BuildReadyTimes finds the ready times for each operand of the next unscheduled
   // candidate op
   void BuildReadyTimes(ListIterator Node, int IssueCycle);
   
   // MCT: PredecessorsScheduled determines whether all of a candidate's predecessor ops have
   // been scheduled. Returns YES is all predecessors have been scheduled, NO otherwise.
   int PredecessorsScheduled(ListIterator Node);

   // MCT: SortRegionListByWeight takes a LEGO regionList, converts it into a vector of legoRegions,
   // then calls BubbleSortRegionList to sort the vector. This allows us to schedule child
   // basic-blocks in order of profile weight.
   vector <legoRegion *> SortRegionListByWeight(regionList *rlist);

   // MCT: Performs a bubble sort of a vector of legoRegions based on the Compare function passed.
   void BubbleSortRegionList(vector <legoRegion *> Vector, int (*Compare)(legoRegion *, legoRegion *));

   // MCT: Tells the scheduler if this region has already been scheduled. I use this to avoid spinning
   // trying to schedule a child block that is a child of itself (i.e. has a back edge to itself).
   int HasBlockBeenScheduled(legoRegion *Block);

   // MCT: PrintBlockSchedule is used for debug purposes only.
   void PrintSchedule();

public:

   // constructors and destructors
   op_scheduler() {}
   op_scheduler(legoRegion *, machine *, knobs *);
   ~op_scheduler() {}

   // Set knobs specific for operation scheduling
   virtual void SetKnobs();

   // Operation schedule a basic-block.
   int ScheduleBlock(legoRegion *Block, int StartCycle);

   // Operation schedule a treegion.
   void ScheduleTree();
};


#endif // _OP_SCHEDULER_H_

---