00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #ifndef sched_util_INCLUDED
00029 #define sched_util_INCLUDED
00030
00031 #include "defs.h"
00032
00033 #include <list>
00034 #include <vector>
00035 #if (__GNUC__ == 3)
00036 using std::vector;
00037 #endif // __GNUC__ == 3
00038 #include <queue>
00039
00040
00041 #include "mempool.h"
00042 #include "mempool_allocator.h"
00043
00044
00045 #include "ipfec_defs.h"
00046 #include "cg_flags.h"
00047
00048
00049 #include "tracing.h"
00050 #include "bb.h"
00051 #include "op.h"
00052
00053
00054 #include "region.h"
00055 #include "region_verify.h"
00056 #include "dominate.h"
00057
00058 #include "reg_live.h"
00059
00060 #ifdef TARG_IA64
00061 #include "targ_issue_port.h"
00062 #endif
00063
00064 #include "dag.h"
00065
00066 #ifndef min
00067 #define min(a,b) (((a)<(b))?(a):(b))
00068 #endif
00069
00070 #ifndef max
00071 #define max(a,b) (((a)>(b))?(a):(b))
00072 #endif
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083 typedef enum {
00084 SPEC_NONE = 0,
00085 SPEC_CNTL = 1,
00086 SPEC_DATA = 2,
00087 SPEC_COMB = 3,
00088 SPEC_DISABLED = 4,
00089 } SPEC_TYPE ;
00090
00091 typedef enum {
00092 LOAD_FORM_NORMAL = 0,
00093 LOAD_FORM_DOT_S = 1,
00094 LOAD_FORM_DOT_A = 2,
00095 LOAD_FORM_DOT_SA = 3,
00096 LOAD_FORM_LAST = 4,
00097 } LOAD_FORM ;
00098
00099 extern const char* spec_text[] ;
00100
00101 extern SPEC_TYPE Derive_Spec_Type_If_Violate_Dep (ARC* arc);
00102
00103
00104 class RGN_CFLOW_MGR ;
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114 extern BOOL SCHED_TF_DUMP_IR ;
00115 extern BOOL SCHED_TF_DUMP_DAG ;
00116 extern BOOL SCHED_TF_DUMP_CAND ;
00117 extern BOOL SCHED_TF_SUMMARY_DUMP;
00118 extern BOOL SCHED_TF_VERBOSE_DUMP;
00119 extern BOOL SCHED_TF_DRAW_GLBL_CFG;
00120 extern BOOL SCHED_TF_DRAW_RGNL_CFG;
00121 extern BOOL SCHED_TF_DRAW_LOCAL_DAG;
00122 extern BOOL SCHED_TF_DRAW_RGNL_DAG;
00123 extern BOOL SCHED_TF_TEST_SPEC;
00124 extern BOOL SCHED_TF_CANDSEL_DUMP;
00125 #if defined(TARG_SL)
00126 extern BOOL SCHED_TF_DUMP_CS_PROCESS;
00127 #endif
00128 #if defined(TARG_SL2)
00129 extern BOOL SCHED_TF_DUMP_MACRO_INSN_COMBINATION;
00130 extern BOOL SCHED_TF_DUMP_OP_MOVE_IN_BB;
00131 extern BOOL SCHED_TF_DUMP_CAND_SELECTION_PROCESS;
00132 extern BOOL SCHED_TF_DUMP_SATD_COMB;
00133 extern BOOL SCHED_TF_DUMP_COND_MV_COMBINE;
00134 #endif
00135
00136 extern INT32 SAFE_CNTL_SPEC_PROB ;
00137 extern INT32 UNSAFE_CNTL_SPEC_PROB ;
00138 extern INT32 SPEC_SAFE_LOAD_WITHOUT_TRANSFORM_REACH_PROB;
00139
00140 extern void Get_Sched_Opts (BOOL prepass) ;
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150 class SCHED_UTIL_MEM_POOL {
00151 protected:
00152 MEM_POOL _mem_pool ;
00153
00154 public:
00155 SCHED_UTIL_MEM_POOL () {
00156 MEM_POOL_Initialize (&_mem_pool,"SCHED_UTIL", true);
00157 MEM_POOL_Push(&_mem_pool);
00158 }
00159
00160 ~SCHED_UTIL_MEM_POOL () {
00161 MEM_POOL_Pop (&_mem_pool);
00162 MEM_POOL_Delete (&_mem_pool);
00163 }
00164 };
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187 class CFG_NODE_MAP {
00188 private:
00189 MEM_POOL * _mem_pool ;
00190
00191 typedef struct tagNODE_ID_VAL_PAIR{
00192 void * value ;
00193 INT32 node_id ;
00194 tagNODE_ID_VAL_PAIR (void* Value, INT32 Node_id) {
00195 value = Value ; node_id = Node_id ;
00196 }
00197 } NODE_ID_VAL_PAIR ;
00198
00199 typedef mempool_allocator<NODE_ID_VAL_PAIR > _PAIR_ALLOC ;
00200 typedef vector<NODE_ID_VAL_PAIR , _PAIR_ALLOC> _PAIR_VECT ;
00201 typedef _PAIR_VECT::iterator _PAIR_VECT_ITER ;
00202
00203 _PAIR_VECT _bb_map_vect, _rgn_map_vect ;
00204
00205 void _bubble_sort (_PAIR_VECT& vect, INT32 low_idx, INT32 hign_idx);
00206 void _set_map (_PAIR_VECT& vect, INT32 id, void *value);
00207 INT32 _find_elem (_PAIR_VECT& vect, INT32 id);
00208
00209 public :
00210
00211 CFG_NODE_MAP (MEM_POOL * mp) :
00212 _mem_pool(mp), _bb_map_vect(mp), _rgn_map_vect(mp) { }
00213
00214 ~CFG_NODE_MAP () {} ;
00215
00216 void Initialize_Map (REGION* rgn) ;
00217 void Initialize_Map (BB *bb) ;
00218
00219 inline void Set_Map (BB * bb, void* value) {
00220 _set_map (_bb_map_vect,BB_id(bb), value);
00221 }
00222
00223 inline void Set_Map (REGION *rgn, void * value) {
00224 _set_map (_rgn_map_vect,rgn->Id(), value) ;
00225 }
00226
00227 inline void Set_Map (REGIONAL_CFG_NODE * nd, void* value) {
00228 if (nd->Is_Region()) Set_Map (nd->Region_Node(), value);
00229 else Set_Map (nd->BB_Node(), value);
00230 }
00231
00232 inline void * Get_Map (BB * bb) {
00233 INT32 pos = _find_elem (_bb_map_vect,BB_id(bb));
00234 return pos >= 0 ? _bb_map_vect[pos].value : NULL ;
00235 }
00236
00237 inline void * Get_Map (REGION * rgn) {
00238 INT32 pos = _find_elem (_rgn_map_vect,rgn->Id()) ;
00239 return pos >= 0 ? _rgn_map_vect[pos].value : NULL;
00240 }
00241
00242 inline void * Get_Map (REGIONAL_CFG_NODE *nd) {
00243 return nd->Is_Region() ? Get_Map (nd->Region_Node()) :
00244 Get_Map (nd->BB_Node()) ;
00245 }
00246
00247 void Dump (FILE *f=stderr) ;
00248
00249 #ifdef Is_True_On
00250 void gdb_dump (void);
00251 #endif
00252 };
00253
00254
00255
00256
00257 typedef INT32 REACH_PROB;
00258 typedef REACH_PROB PROBABILITY;
00259 #define REACH_PROB_SCALE (100)
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279 typedef INT16 CYCLE ;
00280 #define CYCLE_MAX 0x7fff
00281
00282 typedef UINT32 OP_EXT_FLAG;
00283
00284 class SCHED_OP_ANNOT {
00285
00286 public:
00287
00288 OP_EXT_FLAG _ext_flags ;
00289
00290 OP * _op;
00291 BB * _org_home_bb ;
00292
00293 SCHED_OP_ANNOT (OP *associated_op) {
00294 _ext_flags = (OP_EXT_FLAG)0 ;
00295
00296 _op = associated_op; _org_home_bb = OP_bb(_op);
00297 Is_True (_org_home_bb, ("OP has no home BB"));
00298
00299 }
00300
00301 void Add_OP_Ext_Flag (OP_EXT_FLAG e_flags) {
00302 _ext_flags |= e_flags ;
00303 }
00304
00305 void Del_OP_Ext_Flag (OP_EXT_FLAG e_flags) {
00306 _ext_flags &= ~e_flags;
00307 }
00308
00309 ~SCHED_OP_ANNOT () {} ;
00310
00311 SCHED_OP_ANNOT& operator = (SCHED_OP_ANNOT& opnd) {
00312 _ext_flags = opnd._ext_flags ;
00313 _op = opnd._op;
00314 _org_home_bb = opnd._org_home_bb;
00315 }
00316
00317 void Dump (FILE *f=stderr) ;
00318
00319 } ;
00320
00321
00322 class SCHED_BB_ANNOT {
00323
00324 private:
00325
00326 MEM_POOL * _mem_pool ;
00327
00328 BB * _bb ;
00329
00330 OP * _1st_append_op;
00331
00332
00333
00334
00335 OP * _last_prepend_op ;
00336
00337
00338
00339 OP * _xfer_op ;
00340
00341 BB_OP_MAP _ops_annot_map ;
00342 BS * _annot_inited_ops;
00343
00344 void _init_ops_annot (void) ;
00345
00346 inline void _set_op_annot (OP * op, SCHED_OP_ANNOT * annot) ;
00347
00348
00349 public :
00350
00351 SCHED_OP_ANNOT * Get_OP_Annot (OP * op) {
00352 if (BS_MemberP (_annot_inited_ops, OP_map_idx(op))) {
00353 return (SCHED_OP_ANNOT * )BB_OP_MAP_Get (_ops_annot_map, op);
00354 }
00355
00356 return NULL;
00357 }
00358
00359 void Set_OP_Annot (OP* op, SCHED_OP_ANNOT *annot) {
00360 BB_OP_MAP_Set (_ops_annot_map, op, annot);
00361 }
00362
00363 SCHED_OP_ANNOT * Init_New_OP_Annot (OP* op) ;
00364
00365 SCHED_OP_ANNOT * Detach_OP_Annot (OP * op);
00366 void Attach_OP_Annot (OP * op, SCHED_OP_ANNOT * annot) ;
00367
00368 OP * First_Append_OP (void) { return _1st_append_op ; }
00369 void Set_First_Append_OP(OP *op) { _1st_append_op = op; } ;
00370 OP * Last_Prepend_OP (void) { return _last_prepend_op ; }
00371
00372 SCHED_BB_ANNOT (BB *bb, MEM_POOL *mp) ;
00373 ~SCHED_BB_ANNOT () {} ;
00374
00375 void Dump (FILE *f=stderr) ;
00376
00377 };
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389 class SCHED_RGN_ANNOT {
00390 private:
00391 MEM_POOL * _mem_pool;
00392 REGION * _rgn;
00393
00394 public:
00395 SCHED_RGN_ANNOT (REGION *rgn, MEM_POOL *mp) :
00396 _mem_pool(mp) , _rgn(rgn) {}
00397 ~SCHED_RGN_ANNOT () {} ;
00398
00399 void Dump (FILE *f) ;
00400 };
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410 class SCHED_ANNOT : public SCHED_UTIL_MEM_POOL {
00411 private:
00412 CFG_NODE_MAP * _node_map ;
00413 static INT32 _inst_num ;
00414
00415 REGION * _rgn_scope ;
00416 BB * _local_scope;
00417 BB_SET * _isolated_bbs;
00418
00419 public:
00420
00421 SCHED_ANNOT (void);
00422 ~SCHED_ANNOT (void) { -- _inst_num ; }
00423
00424 void Init (REGION *scope) ;
00425 void Init (BB *scope) ;
00426
00427 inline SCHED_BB_ANNOT * Get_BB_Annot (BB *bb) {
00428 return (SCHED_BB_ANNOT*)_node_map->Get_Map (bb);
00429 }
00430
00431 inline SCHED_RGN_ANNOT * Get_Rgn_Annot (REGION *rgn) {
00432 return (SCHED_RGN_ANNOT*)_node_map->Get_Map (rgn);
00433 }
00434
00435 inline SCHED_OP_ANNOT * Get_OP_Annot (OP *op) {
00436 SCHED_BB_ANNOT * bb_annot = Get_BB_Annot (OP_bb(op));
00437 return bb_annot ? bb_annot->Get_OP_Annot (op) : NULL;
00438 }
00439
00440 inline UINT32 Get_OP_Ext_Flags (OP *op) {
00441 return Get_OP_Annot(op)->_ext_flags ;
00442 }
00443
00444 inline UINT32 * Get_OP_Ext_Flags_P (OP *op) {
00445 return &Get_OP_Annot(op)->_ext_flags ;
00446 }
00447
00448
00449 void Isolate_BB_From_Sched_Scope (BB * bb) {
00450 _isolated_bbs = BB_SET_Union1D (
00451 _isolated_bbs,bb, &_mem_pool);
00452 }
00453
00454 BOOL BB_Is_Isolated (BB *bb) { return BB_SET_MemberP(_isolated_bbs,bb); }
00455 void Delete_BB_From_Isolated_BB_Lst (BB* bb) {
00456 _isolated_bbs = BB_SET_Difference1D (_isolated_bbs,bb);
00457 }
00458
00459
00460
00461
00462 void Dump (FILE * f=stderr) ;
00463
00464 };
00465
00466 extern SCHED_ANNOT sched_annot ;
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477 #define OP_EXT_MASK_ACTUAL (0x00000001)
00478 #define OP_EXT_MASK_NO_CNTL_SPEC (0x00000002)
00479 #define OP_EXT_MASK_NO_DATA_SPEC (0x00000004)
00480 #define OP_EXT_MASK_COMPENSATION (0x00000008)
00481
00482 #define Set_OP_Ext_Flag(x,y) \
00483 { sched_annot.Get_OP_Annot ((x))->Add_OP_Ext_Flag (OP_EXT_MASK_ ## y); }
00484 #define OP_Ext_Flag(x,y) (sched_annot.Get_OP_Ext_Flags ((x)) & OP_EXT_MASK_ ## y)
00485 #define Reset_OP_Ext_Flag(x,y) \
00486 { sched_annot.Get_OP_Annot ((x))->Del_OP_Ext_Flag (OP_EXT_MASK_ ## y); }
00487
00488
00489 inline BOOL
00490 OP_ANNOT_Cannot_Data_Spec (OP* op) { return OP_Ext_Flag (op, NO_DATA_SPEC); }
00491
00492 inline void
00493 OP_ANNOT_Set_Cannot_Data_Spec(OP *op) { Set_OP_Ext_Flag (op, NO_DATA_SPEC); }
00494
00495 inline void
00496 OP_ANNOT_Reset_Cannot_Data_Spec(OP *op) { Reset_OP_Ext_Flag (op, NO_DATA_SPEC); }
00497
00498 inline BOOL
00499 OP_ANNOT_Cannot_Cntl_Spec (OP * op) { return OP_Ext_Flag(op, NO_CNTL_SPEC); }
00500
00501 inline void
00502 OP_ANNOT_Set_Cannot_Cntl_Spec (OP* op) { Set_OP_Ext_Flag(op, NO_CNTL_SPEC); }
00503
00504 inline void
00505 OP_ANNOT_Reset_Cannot_Cntl_Spec (OP* op) { Reset_OP_Ext_Flag(op,NO_CNTL_SPEC);}
00506
00507 inline BOOL
00508 OP_ANNOT_Is_Compensation (OP * op) { return OP_Ext_Flag(op, COMPENSATION); }
00509
00510 inline void
00511 OP_ANNOT_Set_Compenstation (OP* op) { Set_OP_Ext_Flag(op, COMPENSATION); }
00512
00513 inline void
00514 OP_ANNOT_Reset_Compensation (OP* op) { Reset_OP_Ext_Flag(op, COMPENSATION);}
00515
00516 inline BOOL
00517 OP_ANNOT_Cannot_Spec (OP * op) {
00518 return OP_ANNOT_Cannot_Cntl_Spec (op) ||
00519 OP_ANNOT_Cannot_Data_Spec (op) ;
00520 }
00521
00522 inline void
00523 OP_ANNOT_Set_Cannot_Spec (OP* op) {
00524 OP_ANNOT_Set_Cannot_Data_Spec (op) ;
00525 OP_ANNOT_Set_Cannot_Cntl_Spec (op) ;
00526 }
00527
00528 inline void
00529 OP_ANNOT_Reset_Cannot_Spec (OP* op) {
00530 OP_ANNOT_Reset_Cannot_Data_Spec (op) ;
00531 OP_ANNOT_Reset_Cannot_Cntl_Spec (op) ;
00532 }
00533
00534 inline BOOL
00535 OP_ANNOT_OP_Def_Actual_Para (OP *op) { return OP_Ext_Flag(op, ACTUAL); }
00536
00537 inline void
00538 OP_ANNOT_Set_OP_Def_Actual_Para (OP *op) { Set_OP_Ext_Flag (op, ACTUAL); }
00539
00540 inline void
00541 OP_ANNOT_Reset_OP_Def_Actual_Para (OP* op) { Reset_OP_Ext_Flag(op,ACTUAL) ;}
00542
00543 inline void
00544 Isolate_BB_From_Sched_Scope (BB * bb) {
00545 sched_annot.Isolate_BB_From_Sched_Scope (bb);
00546 }
00547
00548 inline BOOL
00549 BB_Is_Isolated_From_Sched (BB* bb) {
00550 return sched_annot.BB_Is_Isolated (bb);
00551 }
00552
00553 inline void
00554 Delete_BB_From_Isolated_BB_Lst (BB* bb) {
00555 sched_annot.Delete_BB_From_Isolated_BB_Lst (bb);
00556 }
00557
00558 extern BOOL
00559 OP1_Defs_Are_Used_By_OP2(OP* op1, OP* op2);
00560
00561 extern BOOL
00562 OP1_Defs_Are_Killed_By_OP2(OP* op1, OP* op2);
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577 BOOL Load_Has_Valid_Vaddr(OP* ld);
00578
00579 typedef mempool_allocator<OP*> OP_ALLOC;
00580 typedef vector<OP*,OP_ALLOC> OP_Vector;
00581 typedef OP_Vector::iterator OP_Vector_Iter;
00582 typedef OP_Vector::reverse_iterator OP_Vector_Riter ;
00583
00584 #ifdef TARG_IA64
00585
00586
00587
00588 inline ISSUE_PORT CGGRP_OP_Issue_Port (OP *op) { return ip_invalid ; }
00589 INT32 CGTARG_adjust_latency (ARC* arc, ISSUE_PORT pred_port,
00590 ISSUE_PORT succ_port);
00591 #endif
00592
00593 #if !defined(TARG_IA64)
00594 #ifdef OP_Scheduled
00595 #undef OP_Scheduled
00596 #undef Set_OP_Scheduled
00597 #undef Reset_OP_Scheduled
00598 #endif
00599
00600
00601
00602
00603 #define OP_Scheduled(o) OP_flag1(o)
00604 #define Set_OP_Scheduled(o) Set_OP_flag1(o)
00605 #define Reset_OP_Scheduled(o) Reset_OP_flag1(o)
00606
00607 #ifndef OP_chk
00608 #define OP_chk(o) (FALSE)
00609 #endif
00610
00611 #if !defined(Set_OP_data_spec) || !defined(Set_OP_cntl_spec)
00612 #define Set_OP_data_spec(o) ((void)0)
00613 #define Set_OP_cntl_spec(o) ((void)0)
00614 #endif
00615
00616 #ifndef Set_OP_orig_bb_id
00617 #define Set_OP_orig_bb_id(o, bid) ((void)0)
00618 #endif
00619
00620 #endif
00621
00622 #endif