list_scheduler.H

Go to the documentation of this file.

#ifndef _LIST_SCHEDULER_H_
#define _LIST_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 

extern clock_t start_live, finish_live, start_rdef, finish_rdef;
extern double clocks_per_sec;
extern double total_live; 

class list_scheduler {

protected:

   typedef vector < BigListElement >::iterator ListIterator;

   vector < BigListElement >* List;
   ListIterator ListHead, ListTail, ListPtr;

   int    ListCount,
          ScheduleCluster,
          NumClusters;

   int PlayDoh;
   char aggr_list_sched;

   dag *DPG;
   legoRegion *Region;

   machine *Machine;
   int BypassLatency;           // The latency of result forwarding,
                                //    this indicates if results are
                                //    forwarded using the result
                                //    bus OR are written to registers
                                //    before they can be used
   legoOp *TailOp;

   int DominatorParallelism,
       CodeGen,
       CreateSchedVizFiles,
       TreeTraversalSched,
       NoSpeculation,
       AllowPBRSpeculation,
       AllowLoadSpeculation,
       AllowOnlySafeSpeculation,
       AllowDownwardCodeMotion,
       AllowMultiWayBR;

   FILE *SchedFile, *ListFile; 

   int bus_needed;

   int current_block_int;
   legoOp *current_before_op;
   ListIterator Op;
   
   //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);
   
   // TruePredecessorsScheduled: Returns YES if all predecessors of an 
   // operation have been scheduled, returns NO otherwise
   // Same as PredecessorsScheduled except that it 
   // ignores anti/output-deps   
   // HZ: If the current Node is a ld op (but not ld verify), the memory
   // deps is not enforced. (enables moving ld above store -- data speculation)
   //    Otherwise, (i.e., if the Node is a st or ld verify instr), the memory  
   //    deps is enforced.
   //   Control deps are enforced between the br op and the br op in its parent
   //   basic block. So the control speculation is also enabled.
   int          TruePredecessorsScheduled( ListIterator Node);
   
   // PredecessorsScheduled: Returns YES if all predecessors of an 
   // operation have been scheduled, returns NO otherwise   
   // HZ: enforce all the data deps including MEM deps among mem ops & control  
   //deps between br ops.
   int          PredecessorsScheduled( ListIterator Node);
   
   //BuildReadyTimes: Finds the ReadyTimes for each operand of an unscheduled
   // operation that will now be a Candidate for scheduling
   // HZ: The operands' ready times of the op are computed using its
   // predecessor's schedule time & latency.
   // Different set of ready times are computed with respect to different
   // dependency types:
   //   operand_ready_times: ready time considering all types of deps (reg, mem,
   //                            and cntl)
   //   true_operand_ready_times: ready time considering all types of deps
   //                           except reg_out and reg_anti deps.
   //   dsld_operand_ready_times: (ds stands for data speculative) ready time
   //                           considering all types of deps except mem dep if
   //                           the Node is a ld but not ld verify instr.
   //   true_dsld_operand_ready_times: ready time considering all deps except
   //                           reg_out , reg_anti and mem dep if Node is a ld
   //                           but not ld verify instr.
   void         BuildReadyTimes( ListIterator Node, int IssueCycle);
   
   // GetCandidateNodeTree: Tree-Traversal version of this function. scans 
   // the list of Ops to try and find one which is unscheduled, has all TRUE 
   // predecessors scheduled (excluding anti/output-deps) and meets requirements 
   // of tree-traversal scheduling (is dominated by cur_block_ptr)  Creates 
   // "int *operand_ready_times" for the op to be used during scheduling
   // HZ: Currently, if fully_if_convert and final_pass are both set,
   //     it scans through the unscheduled instructions (all instructions are
   //     maintained in attribute List), check whether the predecessors have
   //     been scheduled (i.e., enforce all the deps). If one is found, build
   //     its readytimes.
   //     If fully_if_convert is not set, check only the true predecessors of the
   //     unscheduled instruction to see whether they are scheduled. If the true
   //     predecessors of an unscheduled instruction are scheduled, then build  
   //     its ready times. Also check the oppurtunitis of renaming to get better
   //     readytimes (when ture_dsld_ready_time < dsld_ready_time). Then build
   //     readytimes one more time.
   //     Note that: the instructions in List are ordered by the Tree Traveral
   //     method and the dominence by cur_block_ptr is enforced.
   //      
   vector < BigListElement >::iterator
                GetCandidateNodeTree(int, knobs *Knobs,
                                     legoRegion *proc_ptr, int Final_Pass);
                                     
   // GetCandidateNode: scans the list of Ops to try and find one which 
   // is unscheduled and has all predecessors scheduled.  Creates 
   // "int *operand_ready_times" for the op to be used during scheduling
   // HZ: checks whether the predecessors have been scheduled (i.e., enforce all
   //  deps).
   vector < BigListElement >::iterator
                GetCandidateNode( int );
   
   // ResetListPtr: sets the attribute ListPtr to the first unscheduled Op in List
   void         ResetListPtr();

   // 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: 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, knobs *Knobs, 
               legoRegion *proc_ptr, int Final_Pass, 
               int IncMaxRegNum, int Hazardous);

   //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();
   
   //ScheduleOp: indicate that op is scheduled in Cycle
   //HZ: Try to schedule the op at Cycle.
   //  1. If the current region is BB (i.e., not formed as a treegion), move the op
   //     and set the schedule time of the op as Cycle.
   //  2. If the current region is a treegion, then deicde whether scheduling the
   //     op is speculative or not. Currently, if the code has predicated instr
   //     (due to the if-conversion), the speculative scheduling is not
   //     supported (i.e., the predicated instr is scheduled using
   //     non-speculative way). The speculativeness is determined from the fact
   //     whether the op is in the same BB as where current_before_op resides.
   //  3. If the scheduling of the op is speculative:
   //        a. If the op is st or brl, such a speculative code motion is not
   //           allowed. Return RENAMING_CONFLICT.
   //        b. check whether a liveness violation may be resulted from the code
   //           motion. (doubltful point in prothe last multi_op in the code ?)
   //        c. If there is possible liveness violation, renaming of the op is
   //           required.
   //        d. Set the speculative attr of the op.
   //        e. Perform the actual schedule of the op. If the op is a br instr
   //           (but not brl), call the function DoTheMessyStuff and
   //           DoMoreMessyStuff in sequence. (here the code needs to be
   //           updated!!!)
   //        f. Set the schedule time of the op. Also if the liveness needs to
   //           be re-analyzed, recall the LiveVariables function.
   //  4. If the scheduling is non-speculative:
   //        if the op is br, call DoTheMessyStuff, move the op and set the
   //        schedule time.
   
   // Input argument update_at_cycle_end is related with the last multiop
   // processing in step 3b.
   int          ScheduleOp(legoOp * op, int Cycle, knobs * Knobs, legoRegion *
                           proc_ptr, int Final_Pass, int Predicated, 
                           int update_at_cycle_end);
                           
   //HZ: This function seems not useful anymore and is replaced with the
   // function IsDominatorParallelwithRenameGeneral
   int          IsDominatorParallelwithRename(legoOp *op, int readytime, 
                                              legoTreegion* treegion,
                                              knobs *Knobs, 
                                              legoRegion *proc_ptr, 
                                              int Final_Pass);
   
   //HZ: Check whether there exists dominiate parallelism for the op. If so,
   // try to remove the op and update the UD/DU chain and deps relationship with
   // its duplicated op (i.e., combining the op with its duplicate). 
   //  The following steps are involved:
   //  1. For br ops (i.e., the op is a br), do not apply dominame parallelism
   //  2. Do not allow speculative stores and brls as a result of combining.
   //  3. do not apply dominate parallelism to C_MERGE ops.
   //  4. Scan through the instrs from current_before_op to its previous op
   //     with the same schedule time. For each one of them (op_in_multiop):
   //       a. Check if op_in_multiop BB dominates the BB where the op resides.
   //       b. Check whether the op is the same as the op_in_multiop by:
   //            b1. check the opcode;
   //            b2. check src oprds;
   //            b3: check pred src oprds;
   //            b4. if the op is a brl instr, it needs to make sure that there
   //                is no st/macro def bwteen the op and the op_in_multiop.
   //       c. If the src checking in step b succeeds, the op_in_multiop's
   //          BB dominates the op's BB, and the readytime is before the
   //          schedule time of the op_in_multiop, try to merge the op and the
   //          op_in_multiop.
   //            c1. If their dst reg nums are different:, try to use rename to
   //                get the same reg num. The merge involves the update of the
   //                UD/DU chain, fix of the liveness. (Predecessor/successor
   //                relationship has been processed in renaming process)
   //            c2. If they have the same dst reg num, merge the two ops.
   //       d. if speculative combining, add 'speculative' attr to op_in_multiop
   //          and add 'dp_remove' attr to the op.
   //       e. move the op_in_multiop if there is anti dep in the multiop. Also
   //          move the op to the op_in_multiop.
   //       f. Set the predicate of the op_in_multiop using the non-speculative
   //          predicate promotion. (doubtful point for me at this time)
   int          IsDominatorParallelwithRenameGeneral(legoOp *op, int readytime, 
                                              legoTreegion* treegion,
                                              knobs *Knobs, 
                                              legoRegion *proc_ptr, 
                                              int Final_Pass);
                           
   //HZ: Doubt ful point: could not find the definition of this function and seems
   //not used in the list_scheduler.
   int          checkIssue( int );


public:

   list_scheduler()     {}
   list_scheduler( legoRegion *region, machine *MDES, knobs *Knobs );
   ~list_scheduler()    {
     if ( CreateSchedVizFiles ) {
       fclose (SchedFile); 
       fclose (ListFile); 
     }
   }

   // Set the parameters for the scheduler from the knobs ptr
   virtual void SetKnobs( knobs * );

   // 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.
   virtual void ShowParameters( knobs * );

   // Returns 1 if dominator parallelism is being used, 0 otherwise
   int DominatorParallel()      { return DominatorParallelism; }

   // Schedule: schedule the 'current' region, return a pointer to the first
   // Op in the region
   //HZ: The following steps are involved:
   //  1. Compute the liveness of the region, if necessary
   //     (if ReDoLiveVarsNextTreegion is set, doubtfult point: Is there any
   //      chance that this variable is set?)
   //  2. Process the DEFINE instrs for BB scheduling, treegion scheduling.
   //  3. Scheduling the region -scheduling outer loop
   //       a. Get the candidate inst using GetCandidateNodeTree for treegion
   //          scheduling and GetCandidateNode for BB scheduling.
   //       b. Scheduling the instrs at the current_cycle (try to schedule the
   //          candidate instr)
   //            b1. If DominatorParallelism is allowed, determine if the srcs
   //                and dsts are ready, they try function
   //                IsDominatorParallelWithRanmeGeneral.
   //            b2. If DPScheduleTime == 0 (i.e., no dominator parallelism is
   //                found or allowed, check the resource by RU_can_schedule_op
   //                If DPScheduleTime != 0, set the mdes_slot = 0 to indicate
   //                the op is a pseudo op as a result of the Dominator
   //                parallelism scheduling.
   //            b3. If there is no problem with the resources, then call the
   //                function ScheduleOp to perform the code motion.
   //            b4. If there is no conflict (RENAMING CONFLICT) from the
   //                function ScheduleOp, do RU_Schedule_Op_at and also do
   //                machine->adjustIssueStatus &
   //                machine->adjustWriteBackStatus to make the execution       
   //                estimation more accurate.
   //            b5. Find another Candidate Node and repeat until there is no
   //                more available candidates.
   //  4. If the aggressive_list_scheduling is set, scan one more time (i.e.,
   //     go back to step 3b one more time) without increase current_cycle.
   //     Increase the current_cycle and go back to step 3.
   virtual legoOp *Schedule( int *UsefulInstrsScheduled, int *scheduleLength,
                             knobs *Knobs, int Final_Pass, int Predicated );
};

#endif

---