Open64: osprey/be/cg/orc_intel/sched

00001 /* -*-Mode: c++;-*- (Tell emacs to use c++ mode) */
00002 /*
00003  *  Copyright (C) 2000-2003, Intel Corporation
00004  *  All rights reserved.
00005  *  
00006  *  Redistribution and use in source and binary forms, with or without modification,
00007  *  are permitted provided that the following conditions are met:
00008  *  
00009  *  Redistributions of source code must retain the above copyright notice, this list
00010  *  of conditions and the following disclaimer. 
00011  *  
00012  *  Redistributions in binary form must reproduce the above copyright notice, this list
00013  *  of conditions and the following disclaimer in the documentation and/or other materials
00014  *  provided with the distribution. 
00015  *
00016  *  Neither the name of the owner nor the names of its contributors may be used to endorse or
00017  *  promote products derived from this software without specific prior written permission. 
00018  *
00019  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
00020  *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
00021  *  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR
00022  *  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00023  *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
00024  *  BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00026  *  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  *
00028  */
00029 
00030  /* =======================================================================
00031   * =======================================================================
00032   * 
00033   * Module: sched_heur.h
00034   * $Revision: 1.1.1.1 $
00035   * $Date: 2005/10/21 19:00:00 $
00036   * $Author: marcel $
00037   * $Source: /proj/osprey/CVS/open64/osprey1.0/be/cg/orc_intel/sched_heur.h,v $
00038   *
00039   * Revision comments:
00040   * 
00041   * Description:
00042   * ============
00043   *     
00044   *     TODO: finish this comment
00045   *
00046   * =======================================================================
00047   * =======================================================================
00048   */
00049 #ifndef sched_heur_INCLUDED
00050 #define sched_heur_INCLUDED
00051 
00052 #include "targ_issue_port.h" /* for TSI_Issue_Ports */
00053 
00054 /* STL template */
00055 #include <vector> 
00056 
00057 #include "tracing.h"
00058 #include "bb.h"
00059 #include "op.h"
00060 #include "errors.h"
00061 
00062 /* memory management */
00063 #include "mempool.h"
00064 #include "mempool_allocator.h"
00065 
00066 #include "region.h"
00067 #include "sched_util.h"
00068 #include "sched_cand.h"
00069 
00070 
00071 #define COLD_PATH_EXEC_PROB  (0.1f)
00072 #define HOT_PATH_EXEC_PROB   (0.7f)
00073 
00074 #define DONATE_P_READY_CAND_BB_REACH_PROB (0.7f * REACH_PROB_SCALE)
00075 
00076 /* The following two structures apply a e-time constraint to 
00077  * candidate's qualification.
00078  * 
00079  */
00080 typedef enum {
00081     NO_LATER,
00082     AS_EARLY_AS_POSSIBLE, 
00083 } E_TIME_CONSTRAIT ;
00084 
00085  /* the semantic of the combination of <threshold> and <constraint>
00086   *
00087   *  +--------------+-----------------------------------------------+
00088   *  | <constraint> |    qualified candidate(s)                     |
00089   *  +--------------+-----------------------------------------------+
00090   *  | NO_LATER     |  e_time of *UNTRIED* candidate is not later   |
00091   *  |              |  than <threshold>.                            |
00092   *  +--------------+------------------------+----------------------+
00093   *  | AS_EAR...BLE |    If there exist at   |                      |
00094   *  |              | least untried candidate|                      |
00095   *  |              | whose issue cycle is no|     otherwise        |
00096   *  |              | great than <threshold> |                      |
00097   *  |              +------------------------+----------------------+
00098   *  |              | all untried candidates | *UNTRIED* candidates |
00099   *  |              | whose issue cycle is   | whose issue cycle is |
00100   *  |              | no-great than          | EXACTLY equal to     |
00101   *  |              | <threshold>.           | min{ e_time(x) },    |
00102   *  |              |                        | where x are the      |
00103   *  |              |                        | untried candidates.  |
00104   *  +--------------+------------------------+----------------------+
00105   *
00106   */
00107 typedef struct tagE_Time_Constraint {
00108 
00109     CYCLE threshold;
00110     E_TIME_CONSTRAIT constraint;
00111 
00112 } E_Time_Constraint ;
00113 
00114 
00115 
00116 class FAVOR_DELAY_HEUR {
00117 
00118 private:
00119     MEM_POOL* _mp ;        /* underlying mempool */ 
00120 
00121     REGION* _rgn_scope ;   /* the global schedule scope */
00122     BB*     _bb_scope ;    /* the local  scheudle scope */
00123     BB*     _target_block; /* which BB we now deal with */
00124     BB*     _significant_pred;
00125     OP*     _xfer_op  ;    /* cntl-transfer op of <_target_block> */
00126     char*   _describe ;    /* the literal text to describe this heuristic 
00127                             */
00128     
00129     BOOL    _initialize ;  /* indicate whether this class has 
00130                             * initialized or not */
00131     BOOL    _stress_spec ; /* heuristic is used to stress speculation
00132                             * rather than to better expolit ILP, which 
00133                             * is used to expose dormant bugs.
00134                             */
00135 
00136     RGN_CFLOW_MGR* _cflow_mgr;/* _cflow_mgr is used to query 
00137                                * cntl flow information
00138                                */
00139         /* data structure used to hold some information of OP. these 
00140          * information can help me to determine which OP/candidate
00141          * is the best one.
00142          */ 
00143     #define OP_HEUR_INFO_MAGIC_NUM (0x55aa) 
00144     typedef struct tagOP_HEUR_INFO {
00145 
00146         OP*    _op;
00147         BB*    _etime_set_by_which_bb ;
00148         INT32  _fan_out ;
00149         INT32  _issuable_port_num ;
00150         float  _delay ;
00151         CYCLE  _e_time ;
00152         mINT16 _magic_num ;
00153 
00154         tagOP_HEUR_INFO (OP *op) : _op(op) {
00155             _etime_set_by_which_bb = NULL;
00156             _delay      = 0.0f ;
00157             _e_time     = (CYCLE)0;
00158             _magic_num  = OP_HEUR_INFO_MAGIC_NUM ;
00159 
00160             _fan_out    = 0;
00161             _issuable_port_num = 0;
00162             PORT_SET port_set = TSI_Issue_Ports(OP_code(op));
00163             while (port_set.Body()) {
00164 
00165                 if (port_set.Body() & 1) { ++ _issuable_port_num ; }
00166                 port_set = (PORT_SET)((port_set.Body() >> 1)); 
00167             }
00168         }
00169 
00170         void Dump (FILE *f=stderr,BOOL verbose=FALSE) ;
00171         
00172     } OP_HEUR_INFO ;
00173 
00174         /* data structure used to hold some information of BB. ;
00175          */
00176     typedef struct tagBB_HEUR_STUFF {
00177 
00178         mBOOL     _heur_need_adjust; 
00179         BB*       _bb;
00180         BB_OP_MAP _op_2_op_heur_info;
00181         MEM_POOL* _mp;
00182 
00183         void  Set_OP_Heur_Info (OP* op, OP_HEUR_INFO * info) {
00184                     
00185                     if (info) {
00186                         Is_True (op == info->_op, 
00187                                 ("corrupted heuristic structure!"));
00188 
00189                         Is_True (OP_bb(info->_op) == _bb, 
00190                                  ("BB:%d is not op's home bb", 
00191                                   BB_id (OP_bb(info->_op))));
00192                     }
00193 
00194                     BB_OP_MAP_Set (_op_2_op_heur_info, op, (void*)info);
00195               }
00196 
00197         OP_HEUR_INFO * Get_OP_Heur_Info (OP * op) {
00198             return (OP_HEUR_INFO *)
00199                     BB_OP_MAP_Get (_op_2_op_heur_info, op);
00200         }
00201 
00202         tagBB_HEUR_STUFF (BB* bb, MEM_POOL *mp) :
00203                 _bb(bb), _mp(mp) {
00204 
00205             _op_2_op_heur_info = BB_OP_MAP_Create (_bb, _mp);
00206 
00207             _heur_need_adjust = TRUE ;
00208 
00209             OP * op ;
00210             FOR_ALL_BB_OPs (_bb, op) {
00211 
00212                  OP_HEUR_INFO *tmp = CXX_NEW(OP_HEUR_INFO(op),_mp);
00213                  BB_OP_MAP_Set (_op_2_op_heur_info, op, tmp);
00214             }
00215 
00216         }
00217     } BB_HEUR_STUFF; 
00218 
00219     CFG_NODE_MAP  _heur_map; /* f: regional-cfg-node -> 
00220                               *    info-associated-with-this-code
00221                               */
00222 
00223     BOOL  _trace_cand_sel; /* turn on/off candidate selection process*/
00224     FILE* _trace_file;     /* dump the tracing text into this file*/ 
00225 
00226     typedef struct { BB* succ ; float reach_prob ; float max_delay ; 
00227                      INT32 flow_shift_latency ; 
00228                    } SUCC_INFO ;
00229 
00230     void    Alloc_Heur_Data (BB* bb);
00231     void    Alloc_Heur_Data (REGION* rgn);
00232 
00233     BB_HEUR_STUFF* Get_BB_Heur_Stuff (BB* bb) {
00234                         return (BB_HEUR_STUFF*)_heur_map.Get_Map (bb);
00235                    }
00236                     
00237     OP_HEUR_INFO*  Get_OP_Heur_Info (OP* op) {
00238 
00239                         BB_HEUR_STUFF* bb_heur_stuff = 
00240                                 Get_BB_Heur_Stuff (OP_bb(op));
00241 
00242                         Is_True (bb_heur_stuff, 
00243                                  ("Fail to get BB:%d's heuristic stuff",
00244                                  BB_id(OP_bb(op))));
00245 
00246                         return  (OP_HEUR_INFO*)BB_OP_MAP_Get (
00247                                     bb_heur_stuff->_op_2_op_heur_info, op);
00248                     }
00249 
00250 
00251     void Reset_BB_OPs_etime (const BB_VECTOR *bbs) ;
00252     void Reset_BB_OPs_etime (BB *bb);
00253     void Set_OP_etime (OP* op, CYCLE cyc) {
00254 
00255             OP_HEUR_INFO* heur = Get_OP_Heur_Info (op);
00256             Is_True (heur, ("OP[%d] of BB:%d has no heuristic information")); 
00257             
00258             heur->_e_time = cyc ;
00259          }
00260     void Find_Significant_Pred_For_Target_Blk (void);
00261     void Adjust_Etime_For_Target_Block (void);
00262 
00263     BOOL BB_Need_Adjusting_Delay (BB* bb);
00264     void Set_BB_Need_Adjusting_Delay (BB* bb);
00265     void Set_BB_Need_Not_Adjusting_Delay (BB* bb);
00266 
00267     void Compute_Delay (OP* op, SUCC_INFO* succ_info, INT32 succ_num) ;
00268     void Compute_Delay (BB* bb);
00269     void Compute_Delay (REGION* rgn);
00270     
00271     void Adjust_Delay (BB* bb);
00272     void Adjust_Delay (REGION* rgn);
00273 
00274     void Compute_FanOut (OP* op);
00275     void Compute_FanOut_For_All_OP (BB* bb);
00276     void Compute_FanOut_For_All_OP (REGION* rgn);
00277 
00278     CYCLE Exclude_Unqualifed_Cand_Under_Etime_Constraint
00279                 (CAND_LIST& cand_lst, E_Time_Constraint* constraint) ;
00280 
00281     CANDIDATE* Choose_Better_Of_Tie (
00282                     CANDIDATE*, OP_HEUR_INFO* , 
00283                     CANDIDATE* , OP_HEUR_INFO* ,
00284                     BOOL comes_from_targ_bb) ;
00285 
00286     CANDIDATE* Select_Best_Candidate (
00287                     CAND_LIST& cand_lst,
00288                     BB* targ,
00289                     E_Time_Constraint* etime_constraint);
00290 
00291     void Initialize (REGION* rgn);
00292     void Initialize (BB* bb);
00293 
00294 
00295     BOOL Is_In_Global_Scope (void) {
00296             Is_True (_initialize, ("have not been initialized!"));
00297             return _rgn_scope != NULL;
00298          }
00299 
00300             /* return TRUE iff we (cntl-)speculate <op> without 
00301              * trasforming its form is profitable. called only by 
00302              * <Spec_Code_Motion_Is_Profitable>.
00303              */
00304     inline BOOL Cntl_Spec_Ld_In_Normal_Form_Is_Profitable (OP* op) ;
00305 
00306     BOOL Upward_Code_Motion_Inc_Live_Range_Greatly 
00307             (CANDIDATE* cand, SRC_BB_INFO* bb_info,
00308              RGN_CFLOW_MGR* cflow_info) ;
00309 
00310         /* stress speculation stuff :
00311          *
00312          *  Currently, some phases such as GRA LRA EBO etc are lack 
00313          *  of speculation awareness. Sometimes, these phases 
00314          *  get confused or are clumzy at the speculative OPs. 
00315          *  strees spculation stuff are used to trigger those doment 
00316          *  bugs, which are caused by speculation, in these phases.
00317          * 
00318          *  The stress-speculation is implemented in a transparent
00319          *  approach in heurstic-package. When stress-speculation 
00320          *  is turned on (option at command line "-Wb,-IPFEC:stress_spec=on")
00321          *  We try to speculate OPs even if there are non-speculative OPs     
00322          *  ready to be scheduled. 
00323          */ 
00324     CANDIDATE* Select_Best_Candidate_For_Stress_Spec_Purpose ( 
00325                       CAND_LIST& m_ready_cand_lst,
00326                       CAND_LIST& p_ready_cand_lst, 
00327                       BB*  targ,
00328                       E_Time_Constraint* etime_constraint);
00329                 
00330     CANDIDATE* Select_Best_Candidate_For_Stress_Spec_Purpose (
00331                       CAND_LIST& cand_lst,
00332                       BB* targ,
00333                       E_Time_Constraint* etime_constraint);
00334                             
00335 public:
00336         
00337         /* =================================================
00338          *
00339          *    EXPORTED INTERFACE 
00340          *
00341          * ================================================
00342          */
00343     FAVOR_DELAY_HEUR (MEM_POOL *mp) ; 
00344 
00345     ~FAVOR_DELAY_HEUR (void) ;
00346 
00347         /*  Initialize and clean-up this class 
00348          */
00349     void Initialize (REGION *rgn,RGN_CFLOW_MGR* rgn_cflow_mgr) ;
00350     void Initialize (BB *bb,RGN_CFLOW_MGR* rgn_cflow_mgr) ;
00351     void Finialize  (void) ;
00352 
00353         /*  Select the best candidate from dual candidate list. 
00354          *
00355          *  Upon returning, etime_constraint->threshold is set 
00356          *  to the earilest cycle at which candidate can be issued,
00357          *  iff we have found the best candidate. and 
00358          *
00359          *  etime_constraint->threshold remain unchanged when 
00360          *  etime_constraint->constraint is AS_EARLY_AS_POSSIBLE.
00361          */
00362     CANDIDATE * Select_Best_Candidate (
00363                             CAND_LIST& m_ready_cand_lst,
00364                             CAND_LIST& p_ready_cand_lst, 
00365                             BB *       targ,
00366                             E_Time_Constraint * etime_constraint);
00367 
00368          /*  Get the <cand>'s earlist issue cycle 
00369           */
00370     CYCLE Get_Cand_Issue_Cyc (CANDIDATE *cand);
00371 
00372          /* Adjust heurstic stuff when target-bb shifts.
00373           */
00374     void Adjust_Heur_Stuff_When_BB_Changed   
00375            (BB * new_target,SRC_BB_MGR& src_bb_mgr);
00376 
00377          /* Adjust heuristic stuff after we schedule <cand> at
00378           * cycle <issue_cyc>.
00379           */
00380     void Adjust_Heur_After_Cand_Sched 
00381                     (OP *cand,CYCLE issue_cyc);
00382 
00383          /* Adjust heuristic stuff when there are no qualified 
00384           * candidate which can be issued at <issue_cyc>(and 
00385           * than we call SCHEDULER::Cycle_Advance().
00386           * 
00387           * <op_vect> contains all OPs that have been issued at 
00388           * current cycle <issue_cyc>.
00389           */
00390     void Adjust_Heur_After_Sched_One_Cyc 
00391                     (OP_Vector& op_vect, CYCLE issue_cyc);
00392 
00393           /* Compute heuristic data associated with <op> which is 
00394            * currently inserted, appended or prepended to OP_bb(op)
00395            */
00396     void Compute_Heur_Data_For_Inserted_OP   (OP* op) ;
00397     void Compute_Heur_Data_For_Appended_OP   (OP* op) ;
00398     void Compute_Heur_Data_For_Prepended_OP  (OP* op);
00399 
00400           /* Cut off the association between <op> and its heuristic data
00401            */
00402     void * Detach_OP_Heur_Info (OP* op) ;
00403 
00404           /* Bind <op> with <Heur_Data> which is now between <op>'s 
00405            * heuristic data
00406            */
00407     void   Attach_OP_Heur_Info (OP* op, void* Heur_Data);
00408 
00409     BOOL Upward_Global_Sched_Inc_Live_Range_Greatly 
00410             (CANDIDATE* cand,
00411              SRC_BB_INFO* bb_info,
00412              RGN_CFLOW_MGR* cflow_info);
00413 
00414     BOOL Upward_Spec_Global_Sched_Is_Profitable 
00415             (CANDIDATE* cand, SRC_BB_INFO* bb_info,
00416              RGN_CFLOW_MGR* cflow_info);
00417 
00418     BOOL Upward_Useful_Sched_Is_Profitable 
00419             (CANDIDATE* cand, SRC_BB_INFO* bb_info, 
00420              RGN_CFLOW_MGR* cflow_info) ;
00421 
00422     BOOL Upward_Global_Sched_Is_Profitable 
00423             (CANDIDATE* cand, 
00424              SRC_BB_INFO* bb_info, 
00425              RGN_CFLOW_MGR* cflow_info);
00426     
00427     BOOL Renaming_Is_Profitable(CANDIDATE * cand);
00428 
00429           /* check to see whether it is the right time for scheudler to 
00430            * close the code motion of <_target_block>.   
00431            */
00432     BOOL  It_is_Better_No_New_Cycle_For_Cur_BB (void) ;
00433     BOOL  BB_Can_Potentially_Donate_P_Ready_Cand (BB* src, BB* targ);
00434 
00435           /* misc */
00436     void Estimate_Cand_Etime (OP* op) ;
00437 
00438           /* tracing facility */
00439     void  Dump_OP_Heur_Info (OP* op, FILE* f=stderr,
00440                              BOOL verbose=FALSE);
00441     void  Dump_OP_Heur_Info (BB* bb, FILE* f=stderr,
00442                              BOOL verbose=FALSE); 
00443     void  Dump (FILE* f=stderr, BOOL verbose=TRUE);
00444     
00445           /* trace candidate selection process 
00446            */
00447     void Enable_Trace_Cand_Sel_Process (FILE* f) ;
00448     void Disable_Trace_Cand_Sel_Process (void);
00449     BOOL Trace_Cand_Sel_Enabled (void) { return  _trace_cand_sel; }
00450     void Trace_Cand_Sel_Process (const char* fmt, ...); 
00451 
00452 #ifdef Is_True_On     
00453     void gdb_dump(void);
00454 #endif 
00455 
00456 };
00457 
00458 
00459 #endif /* sched_heur_INCLUDED */
osprey/be/cg/orc_intel/sched_heur.h
