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
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157 #ifndef sched_cflow_INCLUDED
00158 #define sched_cflow_INCLUDED
00159
00160
00161 #include <ext/slist>
00162
00163
00164
00165 #include <list>
00166 #include <vector>
00167 using std::vector;
00168 #include <map>
00169
00170
00171 #include "ipfec_defs.h"
00172
00173 #include "region.h"
00174 #include "region_map.h"
00175
00176
00177
00178
00179 #include "tracing.h"
00180 #include "bb.h"
00181 #include "dominate.h"
00182 #include "sched_util.h"
00183 #include "sched_path.h"
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266 class RGN_CFLOW_MGR : public SCHED_UTIL_MEM_POOL {
00267
00268 private :
00269
00270 BOOL _cflow_info_valid;
00271
00272
00273
00274
00275
00276
00277 UINT32 _bb_num ;
00278 UINT32 _rgn_num ;
00279
00280
00281 UINT32 _max_bb_id ;
00282 UINT32 _min_bb_id ;
00283 UINT32 _max_rgn_id ;
00284 UINT32 _min_rgn_id ;
00285
00286 REGION * _scope ;
00287 BB * _bb_scope;
00288
00289 void _init_data_member (void) ;
00290 void _acquire_basic_cflow_info (void);
00291
00292
00293
00294
00295
00296 enum { ID_MAP_BASE = 1, };
00297 enum { INVALID_MAP_IDX = ID_MAP_BASE - 1,};
00298
00299 UINT32 * _bb_id_2_map_idx_vect ;
00300 UINT32 * _rgn_id_2_map_idx_vect ;
00301 BB** _map_idx_2_bb_vect ;
00302 REGION ** _map_idx_2_rgn_vect ;
00303
00304 inline void _setup_map_array (void) ;
00305 inline void _setup_node_cflow_info_array (void) ;
00306
00307 INT32 _bb_2_map_idx (BB *bb) const {
00308 return _bb_id_2_map_idx_vect[BB_id(bb)] ;
00309 }
00310
00311 INT32 _rgn_2_map_idx (REGION *rgn) const {
00312 return _rgn_id_2_map_idx_vect[rgn->Id()];
00313 }
00314
00315 INT32 _rgn_2_map_idx (REGIONAL_CFG_NODE * node) const {
00316 return node->Is_Region () ?
00317 _bb_2_map_idx(node->BB_Node()) :
00318 _rgn_2_map_idx(node->Region_Node()) ;
00319 }
00320
00321 BB * _map_idx_2_bb (INT32 map_idx) const {
00322 return _map_idx_2_bb_vect[map_idx] ;
00323 }
00324
00325 REGION * _map_idx_2_rgn (INT32 map_idx) const {
00326 return _map_idx_2_rgn_vect[map_idx] ;
00327 }
00328
00329 INT32 _max_bb_map_idx (void) const { return ID_MAP_BASE + _bb_num - 1; }
00330 INT32 _min_bb_map_idx (void) const { return ID_MAP_BASE ; }
00331
00332 INT32 _max_rgn_map_idx (void) const { return ID_MAP_BASE + _rgn_num - 1;}
00333 INT32 _min_rgn_map_idx (void) const { return ID_MAP_BASE; }
00334
00335
00336
00337
00338
00339
00340
00341 typedef BS REACH_INFO_VECT ;
00342
00343
00344 typedef struct tagREACH_PROB_VECT{
00345 INT32 elem_num ;
00346 INT32 vect_size;
00347 REACH_PROB * reach_prob_vect;
00348
00349 tagREACH_PROB_VECT (void) {
00350 elem_num = 0;
00351 vect_size = 0;
00352 reach_prob_vect = NULL;
00353 };
00354 } REACH_PROB_VECT;
00355
00356 typedef struct tagNODE_CFLOW_INFO {
00357 union {
00358 BB * bb ;
00359 REGION * rgn ;
00360 } node ;
00361 REACH_INFO_VECT * reach_bb ;
00362
00363 INT32 min_level ;
00364 INT32 max_level ;
00365 REACH_PROB_VECT reach_prob;
00366
00367 tagNODE_CFLOW_INFO () {
00368 node.bb = NULL ;
00369 node.rgn = NULL ;
00370 reach_bb = NULL ;
00371 min_level = max_level = 1 ;
00372 }
00373 } _NODE_CFLOW_INFO ;
00374
00375
00376 typedef mempool_allocator<_NODE_CFLOW_INFO > _NODE_CFLOW_INFO_ALLOC;
00377 typedef vector<_NODE_CFLOW_INFO, _NODE_CFLOW_INFO_ALLOC>
00378 _NODE_CFLOW_VECT;
00379 typedef _NODE_CFLOW_VECT::iterator _NODE_CFLOW_VECT_ITER;
00380
00381 _NODE_CFLOW_VECT _bb_node_cflow_info ;
00382 _NODE_CFLOW_VECT _rgn_node_cflow_info ;
00383
00384 _NODE_CFLOW_INFO& _node_cflow_info (BB *bb) ;
00385 _NODE_CFLOW_INFO& _node_cflow_info (REGION *rgn) ;
00386 _NODE_CFLOW_INFO& _node_cflow_info (REGIONAL_CFG_NODE *node);
00387
00388 BS* _reach_info_vect (BB *bb) ;
00389 BS* _reach_info_vect (REGION *rgn);
00390 BS* _reach_info_vect (REGIONAL_CFG_NODE *node);
00391
00392 REACH_PROB_VECT * _reach_prob_vect (BB *bb);
00393 REACH_PROB_VECT * _reach_prob_vect (REGION *rgn);
00394 REACH_PROB_VECT * _reach_prob_vect (REGIONAL_CFG_NODE * node);
00395
00396
00397
00398
00399
00400
00401
00402
00403 BS * _create_empty_reach_bb_vect () ;
00404 BS * _add_reachable_bb (BB *from, BB* to);
00405 BS * _add_reachable_bb (REGION* rgn, BB* to);
00406 BS * _add_reachable_bb (BS * vect, BB* bb,MEM_POOL * mp);
00407
00408
00409
00410
00411
00412
00413
00414 BS* _add_reachable_bbs (BB *from, BS * reach_bbs);
00415 BS* _add_reachable_bbs (REGION* rgn, BS * reach_bbs);
00416 BS* _add_reachable_bbs (REGIONAL_CFG_NODE * node, BS * reach_bbs);
00417
00418 BS* _set_bb_is_reachable (BS* reach_vect, BB * bb, MEM_POOL *mp);
00419 BOOL _is_bb_reachable (BS *reach_vect, BB *bb);
00420
00421 void _set_bb_reach_prob (REACH_PROB_VECT* prob_vect,
00422 BB* src_bb,REACH_PROB prob) ;
00423 void _set_bb_reach_prob (BB *from, BB* to,REACH_PROB prob) ;
00424 void _set_bb_reach_prob (REGION *from , BB * to, REACH_PROB prob);
00425 void _set_bb_reach_prob (REGIONAL_CFG_NODE *node,
00426 BB * to, REACH_PROB prob);
00427
00428 REACH_PROB _bb_reach_prob (REGION * from,BB *to);
00429 REACH_PROB _bb_reach_prob (BB * from,BB *to);
00430 REACH_PROB _bb_reach_prob (REGIONAL_CFG_NODE * node,BB *to);
00431
00432
00433 void _fused_mult_add (REACH_PROB_VECT * dest,
00434 REACH_PROB_VECT * src, float scalor) ;
00435
00436
00437
00438
00439 void * _alloc_array (INT32 elem_num , INT32 unit_size) ;
00440 void _acquire_cflow_info (void) ;
00441
00442 void _acquire_reachable_info (void) ;
00443 void _acquire_reach_prob_info (void) ;
00444
00445 static UINT16 bb_node_succ_num (REGIONAL_CFG_NODE * node) ;
00446 static UINT16 bb_node_pred_num (REGIONAL_CFG_NODE * node) ;
00447
00448 void _compute_node_level (void) ;
00449
00450 _NODE_CFLOW_INFO _bb_cflow_info ;
00451
00452 static char * _invalid_prompt_msg ;
00453
00454 EXEC_PATH_MGR _exec_path_mgr;
00455
00456
00457
00458
00459
00460
00461
00462
00463 public :
00464
00465
00466 RGN_CFLOW_MGR (void) :
00467 _bb_node_cflow_info (_NODE_CFLOW_INFO_ALLOC(&_mem_pool)),
00468 _rgn_node_cflow_info (_NODE_CFLOW_INFO_ALLOC(&_mem_pool)),
00469 _exec_path_mgr (&_mem_pool) {
00470
00471 _init_data_member () ;
00472 }
00473
00474 ~RGN_CFLOW_MGR (void) {}
00475
00476
00477 void Init (REGION * rgn);
00478 void Init (BB * bb) ;
00479
00480
00481 BOOL Path_Info_Is_Valid (void) const
00482 { return !_exec_path_mgr.Path_Info_Is_Invalid (); }
00483 BOOL Valid (void) const { return _cflow_info_valid; }
00484 REGION* Scope (void) const { return _scope; }
00485
00486
00487
00488 INT32 BB_Node_Num (void) const {
00489 Is_True (Valid (), (_invalid_prompt_msg));
00490 return _bb_num ;
00491 }
00492
00493 INT32 RGN_Node_Num (void) const {
00494 Is_True (Valid (), (_invalid_prompt_msg));
00495 return _rgn_num ;
00496 }
00497
00498 INT32 Max_BB_Id (void) const {
00499 Is_True (Valid (), (_invalid_prompt_msg));
00500 return _max_bb_id;
00501 }
00502
00503 INT32 Max_Rgn_Id (void) const {
00504 Is_True (Valid (), (_invalid_prompt_msg));
00505 return _max_rgn_id ;
00506 }
00507
00508
00509
00510 INT32 Max_Level (REGIONAL_CFG_NODE * node) ;
00511 INT32 Max_Level (BB * bb);
00512
00513 INT32 Min_Level (REGIONAL_CFG_NODE * node) ;
00514 INT32 Min_Level (BB * bb);
00515
00516
00517
00518
00519 BOOL BB1_Reachable_From_BB2 (BB* bb1, BB* bb2) ;
00520 BOOL BB_Reachable_From_RGN (BB* bb, REGION* rgn) ;
00521 BOOL BB_Reachable_From_Node (BB* bb, REGIONAL_CFG_NODE* n) {
00522 return n->Is_Region () ?
00523 BB_Reachable_From_RGN (bb, n->Region_Node()) :
00524 BB1_Reachable_From_BB2 (bb, n->BB_Node ());
00525 }
00526
00527
00528 BOOL BB_Is_Reachable (BB * bb, BB_VECTOR * bb_vect) {
00529 for (BB_VECTOR_ITER iter = bb_vect->begin () ;
00530 iter != bb_vect->end() ; iter++) {
00531 if (BB1_Reachable_From_BB2 (bb, *iter)) return TRUE;
00532 }
00533 return FALSE;
00534 }
00535
00536 REACH_PROB Reachable_Prob (BB* from, BB* to) {
00537
00538 if (from != to) {
00539 Is_True (Valid (), (_invalid_prompt_msg));
00540 return _bb_reach_prob (from, to);
00541 }
00542
00543 return (REACH_PROB)(1.0f * REACH_PROB_SCALE);
00544 }
00545
00546
00547
00548
00549 static BOOL Critical_Edge_Present (REGION *rgn);
00550
00551 void Add_Ficticious_BB_to_Remove_Critical_Edge (void) ;
00552 void Remove_Ficticious_Empty_BB (void);
00553
00554
00555 EXEC_PATH_MGR* Get_Exec_Path_Mgr (void) { return &_exec_path_mgr; }
00556 EXEC_PATH_SET* Get_Path_Flow_Thru (BB* b) {
00557 return _exec_path_mgr.Get_Path_Flow_Thru (b);
00558 }
00559 EXEC_PATH_SET* Get_Path_Flow_Thru (REGION* r) {
00560 return _exec_path_mgr.Get_Path_Flow_Thru (r);
00561 }
00562 EXEC_PATH_SET* Get_Path_Flow_Thru (REGIONAL_CFG_NODE* n) {
00563 return _exec_path_mgr.Get_Path_Flow_Thru (n);
00564 }
00565
00566
00567 BOOL Has_Scheduled_Preds (BB* bb) ;
00568 INT32 Across_Node_Num (BB* from , BB* to) ;
00569
00570 void Dump (FILE *f=stderr,BOOL verbose=TRUE) ;
00571
00572 #ifdef Is_True_On
00573 void gdb_dump (void) ;
00574 #endif
00575 };
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589 void Calculate_Dominator_Info (REGION_TREE *rgn_tree);
00590 BOOL BB1_Postdominate_BB2 (BB * bb1, BB* bb2) ;
00591
00592 inline BOOL BB1_Dominate_BB2 (BB* bb1, BB * bb2) {
00593 return BB_SET_MemberP (BB_dom_set(bb2), bb1);
00594 }
00595
00596 inline BOOL BB1_BB2_Cntl_Equiv (BB* bb_a, BB * bb_b) {
00597 return BB1_Postdominate_BB2 (bb_a,bb_b) &&
00598 BB1_Dominate_BB2 (bb_b, bb_a);
00599 }
00600
00601 inline BOOL Free_Dominator_Info_Memory (void) {
00602 Free_Dominators_Memory () ;
00603 }
00604
00605 void Workaround_Dom_Info_For_In_Abnormal_Loop_Rgn (REGION * r);
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617 void Init_Split_PU_Entry_Or_Exit_BB (void);
00618
00619 BB * Split_PU_Entry_BB (BB * entry) ;
00620 BB * Split_PU_Entry_BB (REGION * rgn) ;
00621 BB * Split_PU_Exit_BB (BB * exit);
00622 void Split_PU_Exit_BB (REGION * rgn) ;
00623
00624 void Merge_Splitted_PU_Entry_BB (BB * splitted_entry) ;
00625 void Merge_Splitted_PU_Exit_BB (BB * splitted_exit) ;
00626 void Merge_All_Splitted_Entry_and_Exit_BB (void);
00627
00628
00629
00630
00631
00632 typedef enum { IN_SISS, ABOVE_SISS, BELOW_SISS, OTHER } BB_POS ;
00633 BB_POS BB_Pos_Analysis (BB* block, BB_VECTOR* cutting_set,
00634 RGN_CFLOW_MGR* _cflow_info);
00635
00636 BB_POS BB_Pos_Analysis (BB* block, BB_VECTOR* cutting_set,
00637 RGN_CFLOW_MGR* _cflow_info);
00638
00639 #endif