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 #include <vector>
00047 #include "defs.h"
00048 #include "errors.h"
00049 #include "mempool.h"
00050 #include "if_conv.h"
00051 #include "op.h"
00052 #include "tn.h"
00053 #include "tn_map.h"
00054 #include "tracing.h"
00055 #include "cg.h"
00056 #include "dominate.h"
00057 #include "timing.h"
00058 #include "prdb.h"
00059 #include "ipfec_defs.h"
00060 #include <ipfec_options.h>
00061 #include "vt_region.h"
00062 #include "vt_partition.h"
00063 #include "region_bb_util.h"
00064
00065
00066 #include "be_util.h"
00067
00068
00069 void Find_BB_Predicates(BB* bb, TN*& first_tn, TN*& second_tn);
00070 void Print_OP_No_SrcLine(const OP *op);
00071 void fPrint_TN ( FILE *f, char *fmt, TN *tn);
00072 BOOL Is_In_Infinite_Loop(REGION*);
00073 BOOL Is_Abnormal_Loop(REGION*);
00074 BOOL Is_OP_Cond(OP *op);
00075
00076 static PRDB_GEN* prdb = NULL;
00077
00078 MEM_POOL* PRDB_pool;
00079
00080 COMPARE_TYPE Compare_Type(TOP opcode);
00081
00082
00083 inline BOOL Is_Critical_Edge(REGIONAL_CFG_EDGE* edge)
00084 {
00085 REGIONAL_CFG_NODE* cfg_node = edge->Dest();
00086 if(cfg_node->Pred_Num()==1) return FALSE;
00087 cfg_node = edge->Src();
00088 if (cfg_node->Succ_Num()==1&&!cfg_node->Is_Exit()) return FALSE;
00089 return TRUE;
00090 }
00091
00092 inline BB* Find_Region_Entry_BB(REGION* region)
00093 {
00094 REGIONAL_CFG_NODE *node = region->Entries()[0];
00095 do{
00096 if ( !node -> Is_Region()) return node->BB_Node();
00097 node = node->Region_Node()->Entries()[0];
00098 }while(1);
00099 return NULL;
00100 }
00101
00102 BOOL
00103 Is_No_BB_Region(REGION *region)
00104 {
00105 for (TOPOLOGICAL_REGIONAL_CFG_ITER iter( region -> Regional_Cfg());
00106 iter!=0;
00107 ++iter)
00108 {
00109 REGIONAL_CFG_NODE *node = *iter;
00110 if(!node->Is_Region())
00111 {
00112 return FALSE;
00113 }
00114 }
00115 return TRUE;
00116 }
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131 void
00132 Find_Reaching_Def_Use_Set(OP_CONTAINER* result_set,
00133 TN* tn,
00134 OP* home_op,
00135 BB* home_bb,
00136 BB_SET* visited_bb,
00137 BOOL reaching_def,
00138 MEM_POOL* mem_pool)
00139 {
00140 visited_bb = BB_SET_Union1D(visited_bb, home_bb, mem_pool);
00141
00142 if (!TN_is_register(tn))
00143 {
00144 Is_True(0,
00145 ("look for reaching definition/use for REGISTER_UNDEFINED"));
00146 }
00147
00148 OP *op;
00149 if (home_op) {
00150 op = OP_prev(home_op);
00151 } else {
00152 op = BB_last_op(home_bb);
00153 }
00154
00155 while (op) {
00156 if ( reaching_def )
00157 {
00158 if( OP_Defs_TN(op, tn) ) {
00159 result_set->push_back(op);
00160 if (!Is_OP_Cond(op) || (home_op && Is_OP_Cond(home_op) &&
00161 OP_bb(op) == home_bb && OP_opnd(op, OP_PREDICATE_OPND)
00162 == OP_opnd(home_op, OP_PREDICATE_OPND)))
00163 return;
00164 }
00165 } else {
00166 if(OP_Refs_TN(op, tn)){
00167 result_set->push_back(op);
00168 return;
00169 }
00170 }
00171 op = OP_prev(op);
00172 }
00173
00174 REGIONAL_CFG_NODE* rgn_node = Regional_Cfg_Node(home_bb);
00175 CFG_PRED_NODE_ITER pre_iter(rgn_node);
00176 for(pre_iter; pre_iter != 0; ++pre_iter){
00177 if((*pre_iter)->Is_Region()) continue;
00178 BB *pred = (*pre_iter)->BB_Node();
00179 if(!BB_SET_MemberP(visited_bb, pred))
00180 Find_Reaching_Def_Use_Set(result_set, tn, NULL, pred, visited_bb, reaching_def, mem_pool);
00181 }
00182
00183 return;
00184 }
00185
00186
00187 BOOL
00188 Same_OPS(OP_CONTAINER* set1, OP_CONTAINER* set2)
00189 {
00190 if(set1->size() != set2->size()) return FALSE;
00191 OP_CONTAINER::iterator iter1, iter2;
00192 for(iter1 = set1->begin(); iter1 != set1->end(); ++iter1){
00193 OP* op1 = *iter1;
00194 BOOL match = FALSE;
00195 for(iter2 = set2->begin(); iter2 != set2->end(); ++iter2){
00196 OP* op2 = *iter2;
00197 if(op1 == op2)
00198 {
00199 match = TRUE;
00200 break;
00201 }
00202 }
00203 if(!match) return FALSE;
00204 }
00205
00206 return TRUE;
00207 }
00208
00209
00210
00211
00212
00213 BOOL
00214 Is_In_Abnormal_Loop(REGION* r)
00215 {
00216 while(r){
00217 if(Is_Abnormal_Loop(r)) return TRUE;
00218 r = r->Parent();
00219 }
00220 return FALSE;
00221 }
00222
00223
00224
00225
00226 BOOL
00227 PARTITION::operator==(PARTITION* par1)
00228 {
00229 if ( this ->_child .size() == par1->Child().size())
00230 {
00231 if ( this -> Parent() -> Index() == par1->Parent() ->Index())
00232 {
00233 for (INT i = 0; i< this ->_child. size(); i++)
00234 {
00235 if (this ->_child[i]->Index()
00236 != (par1 ->Child())[i] -> Index())
00237 return FALSE;
00238 }
00239 return TRUE;
00240 }
00241 }
00242 return FALSE;
00243 }
00244
00245
00246 PARTITION_GRAPH_NODE::PARTITION_GRAPH_NODE():
00247 _parent_partitions(PT_ALLOC(PRDB_pool)),
00248 _child_partitions(PT_ALLOC(PRDB_pool)),
00249 _related_tns(TN_CONTAINER_ALLOC(PRDB_pool))
00250
00251 {
00252 _related_bbs = BB_SET_Create_Empty( PU_BB_Count+2, PRDB_pool);
00253 _level = -1;
00254 _control_pred = NULL;
00255 }
00256
00257 void
00258 PARTITION_GRAPH_NODE::Del_Related_TN(TN* tn, OP* op)
00259 {
00260
00261
00262 TP_CONTAINER* tn_set = &_related_tns;
00263 TP_CONTAINER::iterator iter;
00264 DEF_KIND kind;
00265 if (TN_Reaching_Value_At_Op(tn , op, &kind, TRUE) != op &&
00266 TN_Reaching_Value_At_Op(tn , op, &kind, FALSE) != op)
00267 {
00268 for(iter = tn_set->begin(); iter!=tn_set->end(); iter++)
00269 {
00270 if ((*iter)->first == tn)
00271 {
00272 iter = tn_set->erase(iter);
00273 break;
00274 }
00275 }
00276 }
00277 }
00278
00279 COMPARE_TYPE Compare_Type(TOP opcode)
00280 {
00281 switch(opcode) {
00282 case TOP_cmp4_eq_or_andcm:
00283 case TOP_cmp4_ge_or_andcm:
00284 case TOP_cmp4_gt_or_andcm:
00285 case TOP_cmp4_i_eq_or_andcm:
00286 case TOP_cmp4_i_ne_or_andcm:
00287 case TOP_cmp4_le_or_andcm:
00288 case TOP_cmp4_lt_or_andcm:
00289 case TOP_cmp4_ne_or_andcm:
00290 case TOP_cmp4_z1_ge_or_andcm:
00291 case TOP_cmp4_z1_gt_or_andcm:
00292 case TOP_cmp4_z1_le_or_andcm:
00293 case TOP_cmp4_z1_lt_or_andcm:
00294 case TOP_cmp4_z2_ge_or_andcm:
00295 case TOP_cmp4_z2_gt_or_andcm:
00296 case TOP_cmp4_z2_le_or_andcm:
00297 case TOP_cmp4_z2_lt_or_andcm:
00298 case TOP_cmp_eq_or_andcm:
00299 case TOP_cmp_ge_or_andcm:
00300 case TOP_cmp_gt_or_andcm:
00301 case TOP_cmp_i_eq_or_andcm:
00302 case TOP_cmp_i_ne_or_andcm:
00303 case TOP_cmp_le_or_andcm:
00304 case TOP_cmp_lt_or_andcm:
00305 case TOP_cmp_ne_or_andcm:
00306 case TOP_cmp_z1_ge_or_andcm:
00307 case TOP_cmp_z1_gt_or_andcm:
00308 case TOP_cmp_z1_le_or_andcm:
00309 case TOP_cmp_z1_lt_or_andcm:
00310 case TOP_cmp_z2_ge_or_andcm:
00311 case TOP_cmp_z2_gt_or_andcm:
00312 case TOP_cmp_z2_le_or_andcm:
00313 case TOP_cmp_z2_lt_or_andcm:
00314 case TOP_tbit_nz_or_andcm:
00315 case TOP_tbit_z_or_andcm:
00316 case TOP_tnat_nz_or_andcm:
00317 case TOP_tnat_z_or_andcm:
00318 return COMPARE_TYPE_or_andcm;
00319
00320 case TOP_cmp4_eq_and_orcm:
00321 case TOP_cmp4_ge_and_orcm:
00322 case TOP_cmp4_gt_and_orcm:
00323 case TOP_cmp4_i_eq_and_orcm:
00324 case TOP_cmp4_i_ne_and_orcm:
00325 case TOP_cmp4_le_and_orcm:
00326 case TOP_cmp4_lt_and_orcm:
00327 case TOP_cmp4_ne_and_orcm:
00328 case TOP_cmp4_z1_ge_and_orcm:
00329 case TOP_cmp4_z1_gt_and_orcm:
00330 case TOP_cmp4_z1_le_and_orcm:
00331 case TOP_cmp4_z1_lt_and_orcm:
00332 case TOP_cmp4_z2_ge_and_orcm:
00333 case TOP_cmp4_z2_gt_and_orcm:
00334 case TOP_cmp4_z2_le_and_orcm:
00335 case TOP_cmp4_z2_lt_and_orcm:
00336 case TOP_cmp_eq_and_orcm:
00337 case TOP_cmp_ge_and_orcm:
00338 case TOP_cmp_gt_and_orcm:
00339 case TOP_cmp_i_eq_and_orcm:
00340 case TOP_cmp_i_ne_and_orcm:
00341 case TOP_cmp_le_and_orcm:
00342 case TOP_cmp_lt_and_orcm:
00343 case TOP_cmp_ne_and_orcm:
00344 case TOP_cmp_z1_ge_and_orcm:
00345 case TOP_cmp_z1_gt_and_orcm:
00346 case TOP_cmp_z1_le_and_orcm:
00347 case TOP_cmp_z1_lt_and_orcm:
00348 case TOP_cmp_z2_ge_and_orcm:
00349 case TOP_cmp_z2_gt_and_orcm:
00350 case TOP_cmp_z2_le_and_orcm:
00351 case TOP_cmp_z2_lt_and_orcm:
00352 return COMPARE_TYPE_and_orcm;
00353
00354 case TOP_cmp4_eq_andcm:
00355 case TOP_cmp4_ge_andcm:
00356 case TOP_cmp4_gt_andcm:
00357 case TOP_cmp4_i_eq_andcm:
00358 case TOP_cmp4_i_ne_andcm:
00359 case TOP_cmp4_le_andcm:
00360 case TOP_cmp4_lt_andcm:
00361 case TOP_cmp4_ne_andcm:
00362 case TOP_cmp4_z1_ge_andcm:
00363 case TOP_cmp4_z1_gt_andcm:
00364 case TOP_cmp4_z1_le_andcm:
00365 case TOP_cmp4_z1_lt_andcm:
00366 case TOP_cmp4_z2_ge_andcm:
00367 case TOP_cmp4_z2_gt_andcm:
00368 case TOP_cmp4_z2_le_andcm:
00369 case TOP_cmp4_z2_lt_andcm:
00370 case TOP_cmp_eq_andcm:
00371 case TOP_cmp_ge_andcm:
00372 case TOP_cmp_gt_andcm:
00373 case TOP_cmp_i_eq_andcm:
00374 case TOP_cmp_i_ne_andcm:
00375 case TOP_cmp_le_andcm:
00376 case TOP_cmp_lt_andcm:
00377 case TOP_cmp_ne_andcm:
00378 case TOP_cmp_z1_ge_andcm:
00379 case TOP_cmp_z1_gt_andcm:
00380 case TOP_cmp_z1_le_andcm:
00381 case TOP_cmp_z1_lt_andcm:
00382 case TOP_cmp_z2_ge_andcm:
00383 case TOP_cmp_z2_gt_andcm:
00384 case TOP_cmp_z2_le_andcm:
00385 case TOP_cmp_z2_lt_andcm:
00386 return COMPARE_TYPE_andcm;
00387
00388 case TOP_cmp4_eq_and:
00389 case TOP_cmp4_ge_and:
00390 case TOP_cmp4_gt_and:
00391 case TOP_cmp4_i_eq_and:
00392 case TOP_cmp4_i_ne_and:
00393 case TOP_cmp4_le_and:
00394 case TOP_cmp4_lt_and:
00395 case TOP_cmp4_ne_and:
00396 case TOP_cmp4_z1_ge_and:
00397 case TOP_cmp4_z1_gt_and:
00398 case TOP_cmp4_z1_le_and:
00399 case TOP_cmp4_z1_lt_and:
00400 case TOP_cmp4_z2_ge_and:
00401 case TOP_cmp4_z2_gt_and:
00402 case TOP_cmp4_z2_le_and:
00403 case TOP_cmp4_z2_lt_and:
00404 case TOP_cmp_eq_and:
00405 case TOP_cmp_ge_and:
00406 case TOP_cmp_gt_and:
00407 case TOP_cmp_i_eq_and:
00408 case TOP_cmp_i_ne_and:
00409 case TOP_cmp_le_and:
00410 case TOP_cmp_lt_and:
00411 case TOP_cmp_ne_and:
00412 case TOP_cmp_z1_ge_and:
00413 case TOP_cmp_z1_gt_and:
00414 case TOP_cmp_z1_le_and:
00415 case TOP_cmp_z1_lt_and:
00416 case TOP_cmp_z2_ge_and:
00417 case TOP_cmp_z2_gt_and:
00418 case TOP_cmp_z2_le_and:
00419 case TOP_cmp_z2_lt_and:
00420 case TOP_tbit_nz_and:
00421 case TOP_tbit_z_and:
00422 case TOP_tnat_nz_and:
00423 case TOP_tnat_z_and:
00424 return COMPARE_TYPE_and;
00425
00426 case TOP_cmp4_eq_orcm:
00427 case TOP_cmp4_ge_orcm:
00428 case TOP_cmp4_gt_orcm:
00429 case TOP_cmp4_i_eq_orcm:
00430 case TOP_cmp4_i_ne_orcm:
00431 case TOP_cmp4_le_orcm:
00432 case TOP_cmp4_lt_orcm:
00433 case TOP_cmp4_ne_orcm:
00434 case TOP_cmp4_z1_ge_orcm:
00435 case TOP_cmp4_z1_gt_orcm:
00436 case TOP_cmp4_z1_le_orcm:
00437 case TOP_cmp4_z1_lt_orcm:
00438 case TOP_cmp4_z2_ge_orcm:
00439 case TOP_cmp4_z2_gt_orcm:
00440 case TOP_cmp4_z2_le_orcm:
00441 case TOP_cmp4_z2_lt_orcm:
00442 case TOP_cmp_eq_orcm:
00443 case TOP_cmp_ge_orcm:
00444 case TOP_cmp_gt_orcm:
00445 case TOP_cmp_i_eq_orcm:
00446 case TOP_cmp_i_ne_orcm:
00447 case TOP_cmp_le_orcm:
00448 case TOP_cmp_lt_orcm:
00449 case TOP_cmp_ne_orcm:
00450 case TOP_cmp_z1_ge_orcm:
00451 case TOP_cmp_z1_gt_orcm:
00452 case TOP_cmp_z1_le_orcm:
00453 case TOP_cmp_z1_lt_orcm:
00454 case TOP_cmp_z2_ge_orcm:
00455 case TOP_cmp_z2_gt_orcm:
00456 case TOP_cmp_z2_le_orcm:
00457 case TOP_cmp_z2_lt_orcm:
00458 return COMPARE_TYPE_orcm;
00459
00460 case TOP_cmp4_eq_or:
00461 case TOP_cmp4_ge_or:
00462 case TOP_cmp4_gt_or:
00463 case TOP_cmp4_i_eq_or:
00464 case TOP_cmp4_i_ne_or:
00465 case TOP_cmp4_le_or:
00466 case TOP_cmp4_lt_or:
00467 case TOP_cmp4_ne_or:
00468 case TOP_cmp4_z1_ge_or:
00469 case TOP_cmp4_z1_gt_or:
00470 case TOP_cmp4_z1_le_or:
00471 case TOP_cmp4_z1_lt_or:
00472 case TOP_cmp4_z2_ge_or:
00473 case TOP_cmp4_z2_gt_or:
00474 case TOP_cmp4_z2_le_or:
00475 case TOP_cmp4_z2_lt_or:
00476 case TOP_cmp_eq_or:
00477 case TOP_cmp_ge_or:
00478 case TOP_cmp_gt_or:
00479 case TOP_cmp_i_eq_or:
00480 case TOP_cmp_i_ne_or:
00481 case TOP_cmp_le_or:
00482 case TOP_cmp_lt_or:
00483 case TOP_cmp_ne_or:
00484 case TOP_cmp_z1_ge_or:
00485 case TOP_cmp_z1_gt_or:
00486 case TOP_cmp_z1_le_or:
00487 case TOP_cmp_z1_lt_or:
00488 case TOP_cmp_z2_ge_or:
00489 case TOP_cmp_z2_gt_or:
00490 case TOP_cmp_z2_le_or:
00491 case TOP_cmp_z2_lt_or:
00492 case TOP_tbit_nz_or:
00493 case TOP_tbit_z_or:
00494 case TOP_tnat_nz_or:
00495 case TOP_tnat_z_or:
00496 return COMPARE_TYPE_or;
00497
00498 case TOP_fcmp_ord_unc:
00499 case TOP_fcmp_unord_unc:
00500 case TOP_cmp4_eq_unc:
00501 case TOP_cmp4_ge_unc:
00502 case TOP_cmp4_geu_unc:
00503 case TOP_cmp4_gt_unc:
00504 case TOP_cmp4_gtu_unc:
00505 case TOP_cmp4_i_eq_unc:
00506 case TOP_cmp4_i_ge_unc:
00507 case TOP_cmp4_i_geu_unc:
00508 case TOP_cmp4_i_gt_unc:
00509 case TOP_cmp4_i_gtu_unc:
00510 case TOP_cmp4_i_le_unc:
00511 case TOP_cmp4_i_leu_unc:
00512 case TOP_cmp4_i_lt_unc:
00513 case TOP_cmp4_i_ltu_unc:
00514 case TOP_cmp4_i_ne_unc:
00515 case TOP_cmp4_le_unc:
00516 case TOP_cmp4_leu_unc:
00517 case TOP_cmp4_lt_unc:
00518 case TOP_cmp4_ltu_unc:
00519 case TOP_cmp4_ne_unc:
00520 case TOP_cmp_eq_unc:
00521 case TOP_cmp_ge_unc:
00522 case TOP_cmp_geu_unc:
00523 case TOP_cmp_gt_unc:
00524 case TOP_cmp_gtu_unc:
00525 case TOP_cmp_i_eq_unc:
00526 case TOP_cmp_i_ge_unc:
00527 case TOP_cmp_i_geu_unc:
00528 case TOP_cmp_i_gt_unc:
00529 case TOP_cmp_i_gtu_unc:
00530 case TOP_cmp_i_le_unc:
00531 case TOP_cmp_i_leu_unc:
00532 case TOP_cmp_i_lt_unc:
00533 case TOP_cmp_i_ltu_unc:
00534 case TOP_cmp_i_ne_unc:
00535 case TOP_cmp_le_unc:
00536 case TOP_cmp_leu_unc:
00537 case TOP_cmp_lt_unc:
00538 case TOP_cmp_ltu_unc:
00539 case TOP_cmp_ne_unc:
00540 case TOP_fclass_m_unc:
00541 case TOP_fclass_nm_unc:
00542 case TOP_fcmp_eq_unc:
00543 case TOP_fcmp_ge_unc:
00544 case TOP_fcmp_gt_unc:
00545 case TOP_fcmp_le_unc:
00546 case TOP_fcmp_lt_unc:
00547 case TOP_fcmp_neq_unc:
00548 case TOP_fcmp_nge_unc:
00549 case TOP_fcmp_ngt_unc:
00550 case TOP_fcmp_nle_unc:
00551 case TOP_fcmp_nlt_unc:
00552 case TOP_tbit_nz_unc:
00553 case TOP_tbit_z_unc:
00554 case TOP_tnat_nz_unc:
00555 case TOP_tnat_z_unc:
00556 return COMPARE_TYPE_unc;
00557
00558 case TOP_fcmp_ord:
00559 case TOP_fcmp_unord:
00560 case TOP_cmp4_eq:
00561 case TOP_cmp4_ge:
00562 case TOP_cmp4_geu:
00563 case TOP_cmp4_gt:
00564 case TOP_cmp4_gtu:
00565 case TOP_cmp4_i_eq:
00566 case TOP_cmp4_i_ge:
00567 case TOP_cmp4_i_geu:
00568 case TOP_cmp4_i_gt:
00569 case TOP_cmp4_i_gtu:
00570 case TOP_cmp4_i_le:
00571 case TOP_cmp4_i_leu:
00572 case TOP_cmp4_i_lt:
00573 case TOP_cmp4_i_ltu:
00574 case TOP_cmp4_i_ne:
00575 case TOP_cmp4_le:
00576 case TOP_cmp4_leu:
00577 case TOP_cmp4_lt:
00578 case TOP_cmp4_ltu:
00579 case TOP_cmp4_ne:
00580 case TOP_cmp_eq:
00581 case TOP_cmp_ge:
00582 case TOP_cmp_geu:
00583 case TOP_cmp_gt:
00584 case TOP_cmp_gtu:
00585 case TOP_cmp_i_eq:
00586 case TOP_cmp_i_ge:
00587 case TOP_cmp_i_geu:
00588 case TOP_cmp_i_gt:
00589 case TOP_cmp_i_gtu:
00590 case TOP_cmp_i_le:
00591 case TOP_cmp_i_leu:
00592 case TOP_cmp_i_lt:
00593 case TOP_cmp_i_ltu:
00594 case TOP_cmp_i_ne:
00595 case TOP_cmp_le:
00596 case TOP_cmp_leu:
00597 case TOP_cmp_lt:
00598 case TOP_cmp_ltu:
00599 case TOP_cmp_ne:
00600 case TOP_fclass_m:
00601 case TOP_fclass_nm:
00602 case TOP_fcmp_eq:
00603 case TOP_fcmp_ge:
00604 case TOP_fcmp_gt:
00605 case TOP_fcmp_le:
00606 case TOP_fcmp_lt:
00607 case TOP_fcmp_neq:
00608 case TOP_fcmp_nge:
00609 case TOP_fcmp_ngt:
00610 case TOP_fcmp_nle:
00611 case TOP_fcmp_nlt:
00612 case TOP_tbit_nz:
00613 case TOP_tbit_z:
00614 case TOP_tnat_nz:
00615 case TOP_tnat_z:
00616 return COMPARE_TYPE_normal;
00617
00618 default:
00619 Is_True(TRUE, ("Not compare instruction!!!"));
00620 return (COMPARE_TYPE) -1;
00621 }
00622 }
00623
00624
00625
00626
00627
00628 PARTITION_GRAPH::PARTITION_GRAPH(REGION* region)
00629 :_nodes(PG_ALLOC(PRDB_pool)),
00630 _disjoint_relation(BV_ALLOC(PRDB_pool)),
00631 _subset_relation(BV_ALLOC(PRDB_pool)),
00632 _visited(0,PRDB_pool)
00633 {
00634 partition_graph_node_number = 0;
00635 _tn_node_map = OP_MAP_Create();
00636 _bb_node_map = BB_MAP_Create();
00637
00638
00639 _dummy_node = CXX_NEW(PARTITION_GRAPH_NODE(), PRDB_pool);
00640 _dummy_node -> Index(partition_graph_node_number++);
00641 _root = CXX_NEW(PARTITION_GRAPH_NODE(), PRDB_pool);
00642 _root -> Index(partition_graph_node_number++);
00643 _root ->Level(1);
00644
00645 Add_Node(_dummy_node);
00646 Add_Node(_root);
00647
00648
00649
00650 Collect_Info (region);
00651 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00652 Print(TFile);
00653
00654
00655 Look_For_Partition(region);
00656
00657 for(INT k = 0; k<partition_graph_node_number; k++){
00658 _visited.push_back(FALSE);
00659 }
00660 Mark_Level(_root);
00661
00662 if(VT_Enable_Partition_Graph) draw_partition_graph(this, "before complete!");
00663 Complete_Partition_Graph();
00664
00665 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00666 fprintf(TFile, "\nbefore pre_computing\n");
00667
00668 Pre_Computing();
00669 }
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685 void
00686 PARTITION_GRAPH::Collect_Info(REGION* region)
00687 {
00688 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00689 fprintf(TFile, "\nstarting to collect info.\n");
00690
00691
00692 BB* bb, *entry_bb = NULL;
00693 BB_CONTAINER bbs(PRDB_pool);
00694 BB_CONTAINER::iterator iter;
00695 for (TOPOLOGICAL_REGIONAL_CFG_ITER iter( region -> Regional_Cfg());
00696 iter!=0;
00697 ++iter)
00698 {
00699
00700
00701 REGIONAL_CFG_NODE *node = *iter;
00702 if ( node -> Is_Region()) {
00703 if(node->Is_Entry())
00704 {
00705 entry_bb = Find_Region_Entry_BB(region);
00706 Is_True(entry_bb, ("The region without entry BB node!"));
00707 bbs.push_back(entry_bb);
00708 }
00709 continue;
00710 }
00711
00712 bb = node -> BB_Node();
00713 bbs.push_back(bb);
00714 }
00715
00716
00717
00718
00719 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00720 fprintf(TFile, "starting to collect infomation about BBs.\n");
00721
00722
00723
00724 if(Is_In_Infinite_Loop(region) || Is_In_Abnormal_Loop(region))
00725 {
00726 for(iter = bbs.begin(); iter != bbs.end(); ++iter) {
00727 bb = *iter;
00728
00729 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)) {
00730 fprintf(TFile, " == collecting infomation about BB_%d.\n", BB_id(bb));
00731 }
00732 PARTITION_GRAPH_NODE* graph_node = NULL;
00733
00734 BB* eq_bb;
00735 INT bb_size = 0;
00736 FOR_ALL_BB_SET_members(BB_dom_set(bb), eq_bb)
00737 {
00738 if (Region_Contains_BB(region, eq_bb) && eq_bb != bb)
00739 {
00740 bb_size++;
00741 break;
00742 }
00743 }
00744
00745
00746 if ((entry_bb && bb == entry_bb) || !bb_size){
00747 graph_node = _root;
00748 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00749 fprintf(TFile, " it can share node with root. \n");
00750 } else {
00751 graph_node = CXX_NEW(PARTITION_GRAPH_NODE(),PRDB_pool);
00752 graph_node -> Index(partition_graph_node_number++);
00753 Add_Node(graph_node);
00754 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)) {
00755 fprintf(TFile, " create a partition graph node.\n");
00756 }
00757 }
00758 graph_node -> Add_Related_BB(bb);
00759 BB_MAP_Set(_bb_node_map, bb, graph_node);
00760 }
00761 }else{
00762 BB_SET* equal_classes = BB_SET_Create_Empty(PU_BB_Count+2, PRDB_pool);
00763 for(iter = bbs.begin(); iter != bbs.end(); ++iter){
00764 bb = *iter;
00765
00766 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00767 fprintf(TFile, " == collecting infomation about BB_%d.\n", BB_id(bb));
00768 PARTITION_GRAPH_NODE* graph_node = NULL;
00769
00770
00771
00772
00773 BB* ec;
00774 FOR_ALL_BB_SET_members( equal_classes, ec){
00775 if ((BB_SET_MemberP(BB_dom_set(bb), ec)&&
00776 BB_SET_MemberP(BB_pdom_set(ec), bb)) ||
00777 (BB_SET_MemberP(BB_dom_set(ec), bb) &&
00778 BB_SET_MemberP(BB_pdom_set(bb), ec)))
00779 {
00780 graph_node =
00781 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, ec);
00782 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00783 fprintf(TFile,
00784 " it can share the partition graph node "
00785 "with BB_%d.\n", BB_id(ec));
00786 }
00787 break;
00788 }
00789 }
00790
00791 if (! graph_node) {
00792 BB* eq_bb;
00793 INT bb_size = 0;
00794 FOR_ALL_BB_SET_members(BB_dom_set(bb), eq_bb)
00795 {
00796 if (Region_Contains_BB(region, eq_bb) && eq_bb != bb)
00797 {
00798 bb_size++;
00799 break;
00800 }
00801 }
00802
00803
00804 if ((entry_bb && bb == entry_bb) || !bb_size){
00805 graph_node = _root;
00806 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00807 fprintf(TFile, " it can share node with root. \n");
00808 }else {
00809 graph_node = CXX_NEW(PARTITION_GRAPH_NODE(),PRDB_pool);
00810 graph_node -> Index(partition_graph_node_number++);
00811 Add_Node(graph_node);
00812 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00813 fprintf(TFile,
00814 " create a new partition graph node for it.\n");
00815 }
00816 BB_SET_Union1D(equal_classes, bb, PRDB_pool);
00817 }
00818 graph_node -> Add_Related_BB(bb);
00819 BB_MAP_Set(_bb_node_map, bb, graph_node);
00820
00821 }
00822 }
00823
00824 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00825 fprintf(TFile, "starting to collect info about OPs.\n");
00826
00827
00828 BB_SET* visited_bb = BB_SET_Create_Empty(PU_BB_Count+2, PRDB_pool);
00829 for(iter = bbs.begin(); iter != bbs.end(); ++iter){
00830 bb = *iter;
00831 if(entry_bb && bb == entry_bb) continue;
00832
00833 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00834 fprintf(TFile,
00835 " == collecting infomation about def TNs in BB_%d.\n",
00836 BB_id(bb));
00837
00838 OP* br_op = NULL;
00839 TN *true_tn = NULL, *false_tn = NULL;
00840 BB *fall_thru_bb = NULL,*branch_targ_bb = NULL;
00841
00842
00843
00844 br_op = BB_branch_op(bb);
00845 if(br_op && OP_code(br_op) == TOP_br_cond) {
00846 if (!(BB_kind(bb)==BBKIND_VARGOTO || BB_kind(bb)==BBKIND_INDGOTO))
00847 {
00848 fall_thru_bb = BB_Fall_Thru_Successor(bb);
00849 if( !fall_thru_bb || BB_preds_len(fall_thru_bb) >1
00850 || region != Home_Region(fall_thru_bb)) {
00851 false_tn = NULL;
00852 fall_thru_bb = NULL;
00853 }
00854 if(fall_thru_bb) {
00855 branch_targ_bb = BB_Other_Successor(bb, fall_thru_bb);
00856 if (!branch_targ_bb || BB_preds_len(branch_targ_bb) >1
00857 || region != Home_Region(branch_targ_bb)) {
00858 true_tn = NULL;
00859 branch_targ_bb = NULL;
00860 }
00861 }
00862 }
00863 if(fall_thru_bb && branch_targ_bb && BB_preds_len(fall_thru_bb) == 1
00864 && BB_preds_len(branch_targ_bb) == 1) {
00865 true_tn = OP_opnd(br_op, OP_PREDICATE_OPND);
00866 OP_CONTAINER def_set(PRDB_pool);
00867 Find_Reaching_Def_Use_Set(&def_set, true_tn, br_op, bb, visited_bb, TRUE, PRDB_pool);
00868 visited_bb = BB_SET_ClearD(visited_bb);
00869 if(def_set.size() == 1) {
00870 OP* def_op = *def_set.begin();
00871 false_tn = true_tn == OP_result(def_op, 1) ? OP_result(def_op, 0): OP_result(def_op, 1);
00872 PARTITION_GRAPH_NODE* succ_node = (PARTITION_GRAPH_NODE*)
00873 BB_MAP_Get(_bb_node_map, branch_targ_bb);
00874 succ_node -> Control_Pred(true_tn);
00875 succ_node = (PARTITION_GRAPH_NODE*) BB_MAP_Get(_bb_node_map, fall_thru_bb);
00876 succ_node -> Control_Pred(false_tn);
00877 } else if(def_set.size() == 2) {
00878 OP* def_op1 = *def_set.begin();
00879 OP* def_op2 = *(def_set.begin()+1);
00880 if((OP_result(def_op1, 0) == OP_result(def_op2, 0) &&
00881 OP_result(def_op1, 1) == OP_result(def_op2, 1)) ||
00882 (OP_result(def_op1, 0) == OP_result(def_op2, 1) &&
00883 OP_result(def_op1, 1) == OP_result(def_op2, 0))) {
00884 false_tn = true_tn == OP_result(def_op1, 1) ? OP_result(def_op1, 0): OP_result(def_op1, 1);
00885 PARTITION_GRAPH_NODE* succ_node = (PARTITION_GRAPH_NODE*)
00886 BB_MAP_Get(_bb_node_map, branch_targ_bb);
00887 succ_node -> Control_Pred(true_tn);
00888 succ_node = (PARTITION_GRAPH_NODE*) BB_MAP_Get(_bb_node_map, fall_thru_bb);
00889 succ_node -> Control_Pred(false_tn);
00890 }
00891 } else {
00892 true_tn = NULL;
00893 }
00894 }
00895 }
00896
00897
00898
00899
00900 OP* op;
00901 FOR_ALL_BB_OPs_REV(bb, op)
00902 {
00903
00904 PG_CONTAINER* nodes_of_tn =
00905 CXX_NEW(PG_CONTAINER, PRDB_pool);
00906 OP_MAP_Set( _tn_node_map, op, nodes_of_tn);
00907
00908 for(INT i=0; i<OP_results(op); i++)
00909 {
00910 TN* tn = OP_result(op, i);
00911 if (!TN_is_register(tn)||
00912 TN_register_class(tn) != ISA_REGISTER_CLASS_predicate)
00913 {
00914 nodes_of_tn -> push_back(NULL);
00915 continue;
00916 }
00917 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00918 {
00919 fprintf(TFile,
00920 " == collecting infomation about op : \n");
00921 Print_OP_No_SrcLine(op);
00922 }
00923
00924 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00925 fprintf(TFile,
00926 " == collecting infomation of \n");
00927 fPrint_TN (TFile, "%s \n", tn);
00928 }
00929
00930 PARTITION_GRAPH_NODE* graph_node = NULL;
00931
00932
00933 if (tn == true_tn){
00934 graph_node =
00935 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map,
00936 branch_targ_bb);
00937 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00938 fprintf(TFile,
00939 " it can share the node with BB_%d \n",
00940 BB_id(branch_targ_bb));
00941 }
00942
00943
00944 }else if (tn == false_tn){
00945 graph_node =
00946 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map,
00947 fall_thru_bb);
00948 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00949 fprintf(TFile,
00950 " it can share the node with BB_%d \n",
00951 BB_id(fall_thru_bb));
00952 }
00953
00954 }else
00955 {
00956 graph_node = CXX_NEW(PARTITION_GRAPH_NODE(), PRDB_pool);
00957 graph_node -> Index(partition_graph_node_number++);
00958 Add_Node(graph_node);
00959 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00960 fprintf(TFile,
00961 " create a new code for it \n");
00962 }
00963 }
00964 nodes_of_tn -> push_back(graph_node);
00965 TN_OP_PAIR* tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
00966 tn_op->first = tn;
00967 tn_op->second = op;
00968 graph_node->Add_Related_TN (tn_op);
00969 }
00970 }
00971 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
00972 fprintf(TFile,
00973 " == collecting infomation about use TNs in BB_%d.\n",
00974 BB_id(bb));
00975 }
00976
00977
00978 FOR_ALL_BB_OPs_REV(bb, op)
00979 {
00980 PG_CONTAINER* nodes_of_tn = (PG_CONTAINER*)
00981 OP_MAP_Get( _tn_node_map, op);
00982
00983 for(INT i=0 ; i< OP_opnds(op); i++)
00984 {
00985 TN* tn = OP_opnd(op, i);
00986
00987 PARTITION_GRAPH_NODE* graph_node = NULL;
00988
00989
00990 if (!TN_is_register(tn)
00991 || TN_register_class(tn) != ISA_REGISTER_CLASS_predicate)
00992 {
00993 nodes_of_tn -> push_back(NULL);
00994 continue;
00995 }
00996 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
00997 {
00998 fprintf(TFile,
00999 " == collecting infomation about op : \n");
01000 Print_OP_No_SrcLine(op);
01001 }
01002
01003 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01004 fprintf(TFile,
01005 " == collecting infomation of \n");
01006 fPrint_TN (TFile, "%s \n", tn);
01007 }
01008
01009 if (TN_is_true_pred(tn))
01010 {
01011 graph_node = (PARTITION_GRAPH_NODE*)
01012 BB_MAP_Get(_bb_node_map, bb);
01013 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01014 fprintf(TFile,
01015 " it can share the node with its home bb. \n");
01016 }
01017
01018 }else {
01019 DEF_KIND kind;
01020 OP_CONTAINER def_set(PRDB_pool);
01021 Find_Reaching_Def_Use_Set(&def_set, tn, op, bb, visited_bb, TRUE, PRDB_pool);
01022 visited_bb = BB_SET_ClearD(visited_bb);
01023 OP* use = TN_Reaching_Value_At_Op(tn, op, &kind, FALSE);
01024 if ( def_set.size() == 1
01025 && OP_bb((*def_set.begin())) == bb )
01026
01027 {
01028 OP *def = *def_set.begin();
01029 PG_CONTAINER* node_set = (PG_CONTAINER*)
01030 OP_MAP_Get(_tn_node_map,def);
01031
01032 for (INT j=0; j<OP_results(def); j++) {
01033 if (OP_result(def,j) == tn){
01034 graph_node = (*node_set)[j];
01035 break;
01036 }
01037 }
01038
01039 Is_True(graph_node, (" False op without def tn!\n"));
01040 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01041 fprintf(TFile,
01042 " it can share the node with its def \n");
01043 }
01044
01045
01046 }else if (use && use != op && OP_Precedes(op, use) &&
01047 OP_bb(use) == bb){
01048
01049 PG_CONTAINER* node_set = (PG_CONTAINER*)
01050 OP_MAP_Get(_tn_node_map,use);
01051
01052 for (INT j=0; j<OP_opnds(use); j++) {
01053 if (OP_opnd(use, j) == tn){
01054 graph_node = (*node_set)[j+OP_results(use)];
01055 break;
01056 }
01057 }
01058
01059 Is_True(graph_node, (" False op without use tn!\n"));
01060 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01061 fprintf(TFile,
01062 " it can share the node with its use \n");
01063 }
01064
01065 }else {
01066
01067
01068 OP_CONTAINER use_set(PRDB_pool);
01069 Find_Reaching_Def_Use_Set(&use_set, tn, NULL, bb, visited_bb, FALSE, PRDB_pool);
01070 visited_bb = BB_SET_ClearD(visited_bb);
01071
01072 BOOL has_eq_use = ((use_set.size() == 1) &&
01073 OP_bb(*use_set.begin()) == bb);
01074
01075 OP *r_use = has_eq_use ? *use_set.begin():NULL;
01076 OP_CONTAINER def_set_of_use(PRDB_pool);
01077 if (r_use && r_use != op) {
01078 Find_Reaching_Def_Use_Set
01079 (&def_set_of_use, tn, r_use, OP_bb(r_use), visited_bb, TRUE, PRDB_pool);
01080 visited_bb = BB_SET_ClearD(visited_bb);
01081 }
01082
01083 if ( r_use && r_use != op && Same_OPS(&def_set, &def_set_of_use)) {
01084 PG_CONTAINER* node_set = (PG_CONTAINER*)
01085 OP_MAP_Get(_tn_node_map,r_use);
01086 for (INT j=0; j<OP_opnds(r_use); j++) {
01087 if (OP_opnd(r_use, j) == tn){
01088 graph_node = (*node_set)[j+OP_results(r_use)];
01089 break;
01090 }
01091 }
01092
01093 Is_True(graph_node, (" False op without use tn!\n"));
01094 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01095 fprintf(TFile,
01096 " it can share the node with its use \n");
01097 }
01098
01099 } else {
01100 graph_node =
01101 CXX_NEW(PARTITION_GRAPH_NODE(), PRDB_pool);
01102 graph_node -> Index(partition_graph_node_number++);
01103 Add_Node(graph_node);
01104 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)){
01105 fprintf(TFile,
01106 " create a new code for it \n");
01107 }
01108 }
01109 }
01110 }
01111
01112 nodes_of_tn -> push_back(graph_node);
01113 TN_OP_PAIR* tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
01114 tn_op->first = tn;
01115 tn_op->second = op;
01116 graph_node->Add_Related_TN (tn_op);
01117 }
01118
01119 }
01120 }
01121 }
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133 void PARTITION_GRAPH::Look_For_Partition(REGION *region)
01134 {
01135 BB *bb, *tmp_bb;
01136 OP* op;
01137 PARTITION_GRAPH_NODE* node, *cur_node;
01138 PT_ALLOC par = PT_ALLOC(PRDB_pool);
01139 INT i;
01140
01141
01142 PARTITION_GRAPH_NODE *pp_node, *bp_node, *qp_node, *p1_node, *p2_node;
01143
01144
01145 TOPOLOGICAL_REGIONAL_CFG_ITER top_rg_iter(region->Regional_Cfg());
01146
01147 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01148 fprintf(TFile, "\n\nLook for partitions of CFG nodes of region.\n");
01149 for(top_rg_iter; top_rg_iter != 0; ++top_rg_iter)
01150 {
01151 if ((*top_rg_iter) -> Is_Region() && (*top_rg_iter) -> Pred_Num() <= 1
01152 && (*top_rg_iter)->Succ_Num() <= 1)
01153 continue;
01154
01155 if ((*top_rg_iter) -> Is_Region())
01156 bb = Find_Region_Entry_BB(region);
01157 else
01158 bb=(*top_rg_iter) -> BB_Node();
01159
01160
01161 cur_node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb);
01162
01163
01164
01165
01166
01167 BOOL dup_dummy = FALSE;
01168 if ((*top_rg_iter)->Pred_Num () > 1)
01169 {
01170 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01171 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01172 fprintf(TFile, "\n\nLook for partitions of CFG node preds.");
01173
01174 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01175 fprintf(TFile, "\nPartition: Parent--%d, ", cur_node->Index ());
01176 CFG_PRED_EDGE_ITER pre_iter(*top_rg_iter);
01177 for(pre_iter; pre_iter != 0; ++pre_iter)
01178 {
01179 if(Is_Critical_Edge(*pre_iter)||(*pre_iter)->Src()->Is_Region())
01180 {
01181 if(!dup_dummy)
01182 {
01183 children->push_back(_dummy_node);
01184 dup_dummy = TRUE;
01185 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01186 fprintf(TFile, "child--0 ");
01187 }
01188 continue;
01189 }
01190 tmp_bb = (*pre_iter)-> Src()->BB_Node();
01191 node = (PARTITION_GRAPH_NODE*)
01192 BB_MAP_Get(_bb_node_map, tmp_bb);
01193 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01194 fprintf(TFile, "child--%d ", node->Index ());
01195 children->push_back(node);
01196 }
01197 if(children->size()<=1) {
01198 CXX_DELETE(children, PRDB_pool);
01199 } else {
01200 Add_Partition(cur_node, children);
01201 }
01202 }
01203
01204
01205
01206 dup_dummy = FALSE;
01207 if ((*top_rg_iter)->Succ_Num () > 1)
01208 {
01209 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01210 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01211 fprintf(TFile, "\n\nLook for partitions of CFG node succs.");
01212
01213 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01214 fprintf(TFile, "\nPartition:Parent--%d, ",cur_node->Index ());
01215 CFG_SUCC_EDGE_ITER succ_iter(*top_rg_iter);
01216 for(succ_iter; succ_iter != 0; ++succ_iter)
01217 {
01218 if(Is_Critical_Edge(*succ_iter)||(*succ_iter)->Dest()->Is_Region())
01219 {
01220 if(!dup_dummy)
01221 {
01222 children->push_back(_dummy_node);
01223 dup_dummy = TRUE;
01224 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01225 fprintf(TFile, "child--0 ");
01226 }
01227 continue;
01228 }
01229 tmp_bb = (*succ_iter)->Dest()-> BB_Node();
01230 node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, tmp_bb);
01231 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01232 fprintf(TFile, "child--%d ", node->Index ());
01233 children->push_back(node);
01234 }
01235 if(children->size()<=1) {
01236 CXX_DELETE(children, PRDB_pool);
01237 } else {
01238 Add_Partition(cur_node, children);
01239 }
01240 }
01241 }
01242
01243
01244 TOPOLOGICAL_REGIONAL_CFG_ITER top_rg_iter1(region->Regional_Cfg());
01245
01246 COMPARE_TYPE cmp_type;
01247
01248 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01249 fprintf(TFile, "\n\nLook for partitions of material predicate.");
01250 for(top_rg_iter1; top_rg_iter1 != 0; ++top_rg_iter1)
01251 {
01252
01253 if ((*top_rg_iter1) -> Is_Region())
01254 continue;
01255
01256 bb=(*top_rg_iter1) -> BB_Node();
01257
01258 bp_node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb);
01259
01260 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01261 fprintf(TFile, "\n\nCurrent BB is BB%d.", BB_id(bb));
01262 FOR_ALL_BB_OPs(bb, op)
01263 {
01264 if (!BB_exit(bb)
01265 && (OP_code(op) == TOP_mov_t_pr || OP_code(op) == TOP_mov_t_pr_i))
01266 {
01267 for (i=0; i<partition_graph_node_number; i++)
01268 {
01269 _nodes[i]->Clear_Child_Partitions();
01270 _nodes[i]->Clear_Parent_Partitions();
01271 }
01272 }
01273 if (OP_results(op)==0 || !TN_is_register(OP_result(op,0))||
01274 TN_register_class(OP_result(op,0)) !=
01275 ISA_REGISTER_CLASS_predicate)
01276 continue;
01277 INT16 node_pos=OP_PREDICATE_OPND+OP_results(op);
01278
01279
01280
01281 qp_node = (*((PG_CONTAINER*)
01282 OP_MAP_Get(_tn_node_map, op)))[node_pos];
01283 pp_node = TN_is_true_pred(OP_opnd(op, OP_PREDICATE_OPND))
01284 ?bp_node:qp_node;
01285
01286 Is_True(OP_results(op)>1, ("invalid compare instruction!"));
01287
01288
01289
01290 p1_node = TN_is_true_pred(OP_result(op, 0))?_dummy_node:
01291 (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[0];
01292 p2_node = TN_is_true_pred(OP_result(op, 1))?_dummy_node:
01293 (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[1];
01294
01295 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01296 cmp_type = Compare_Type(OP_code(op));
01297
01298
01299
01300 switch(cmp_type) {
01301 case COMPARE_TYPE_unc:
01302 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01303 fprintf(TFile,
01304 "\nUnconditional partition: Parent--%d child1--%d child2--%d",
01305 pp_node->Index (), p1_node->Index (),p2_node->Index ());
01306 if (p1_node == pp_node) children->push_back(_dummy_node);
01307 else children->push_back(p1_node);
01308 if (p2_node == pp_node) children->push_back(_dummy_node);
01309 else children->push_back(p2_node);
01310 Add_Partition(pp_node, children);
01311 break;
01312 case COMPARE_TYPE_normal:
01313 if (TN_is_true_pred(OP_opnd(op, OP_PREDICATE_OPND)))
01314 {
01315 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01316 fprintf(TFile,
01317 "\nNormal partition: Parent--%d child1--%d child2--%d",
01318 bp_node->Index (),p1_node->Index (),p2_node->Index ());
01319 children->push_back(p1_node);
01320 children->push_back(p2_node);
01321 Add_Partition(bp_node, children);
01322 }
01323 else
01324 {
01325 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01326 fprintf(TFile,
01327 "\nNormal partition: Parent--%d child1--%d child2--dummy",
01328 bp_node->Index (), p1_node->Index ());
01329 children->push_back(p1_node);
01330 children->push_back(_dummy_node);
01331 Add_Partition(bp_node, children);
01332
01333 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01334 fprintf(TFile,
01335 "\nNormal partition: Parent--%d child1--%d child2--dummy",
01336 bp_node->Index (), p2_node->Index ());
01337 children->push_back(p2_node);
01338 children->push_back(_dummy_node);
01339 Add_Partition(bp_node, children);
01340 }
01341 break;
01342 case COMPARE_TYPE_and:
01343 case COMPARE_TYPE_andcm:
01344 CXX_DELETE(children, PRDB_pool);
01345 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[0];
01346 Look_Partition_For_And_Type(OP_result(op, 0), bp_node, node,
01347 _dummy_node, op);
01348 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[1];
01349 Look_Partition_For_And_Type(OP_result(op, 1), bp_node, node,
01350 _dummy_node, op);
01351 break;
01352 case COMPARE_TYPE_or:
01353 case COMPARE_TYPE_orcm:
01354 CXX_DELETE(children, PRDB_pool);
01355 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[0];
01356 Look_Partition_For_Or_Type(OP_result(op, 0), bp_node, node,
01357 _dummy_node, op);
01358 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[1];
01359 Look_Partition_For_Or_Type(OP_result(op, 1), bp_node, node,
01360 _dummy_node, op);
01361 break;
01362 case COMPARE_TYPE_and_orcm:
01363 CXX_DELETE(children, PRDB_pool);
01364 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[0];
01365 Look_Partition_For_And_Type(OP_result(op, 0), bp_node, node,
01366 _dummy_node, op);
01367 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[1];
01368 Look_Partition_For_Or_Type(OP_result(op, 1), bp_node, node,
01369 _dummy_node, op);
01370 break;
01371 case COMPARE_TYPE_or_andcm:
01372 CXX_DELETE(children, PRDB_pool);
01373 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[1];
01374 Look_Partition_For_Or_Type(OP_result(op, 1), bp_node, node,
01375 _dummy_node, op);
01376 node = (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op)))[0];
01377 Look_Partition_For_And_Type(OP_result(op, 0), bp_node, node,
01378 _dummy_node, op);
01379 break;
01380 default:
01381 Is_True(FALSE, ("unexpected compare type!"));
01382 }
01383 }
01384 }
01385 }
01386
01387
01388 void
01389 PARTITION_GRAPH::Look_Partition_For_Or_Type(TN* tn, PARTITION_GRAPH_NODE*
01390 parent, PARTITION_GRAPH_NODE* child1, PARTITION_GRAPH_NODE* child2, OP* op)
01391 {
01392 if(tn == True_TN) return;
01393 DEF_KIND kind;
01394 INT i;
01395 TN* ref_tn;
01396 OP* ref_op=TN_Reaching_Value_At_Op(tn, op, &kind, FALSE);
01397 if (!ref_op || OP_bb(ref_op) != OP_bb(op))
01398 {
01399 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01400 children->push_back(child1);
01401 children->push_back(child2);
01402 Add_Partition(parent, children);
01403 }
01404 else
01405 {
01406 while (ref_op && OP_bb(ref_op) == OP_bb(op))
01407 {
01408 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01409 for(i=0; i<OP_opnds(ref_op); i++)
01410 {
01411 ref_tn = OP_opnd(ref_op, i);
01412 if(TNs_Are_Equivalent(tn, ref_tn))
01413 break;
01414 }
01415 PARTITION_GRAPH_NODE* node;
01416 node = (*((PG_CONTAINER*)OP_MAP_Get
01417 (_tn_node_map, ref_op)))[i+OP_results(ref_op)];
01418 children->push_back(node);
01419 children->push_back(child2);
01420 Add_Partition(parent, children);
01421
01422 PG_CONTAINER* sub_children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01423 sub_children->push_back(child1);
01424 sub_children->push_back(child2);
01425 Add_Partition(node, sub_children);
01426 op = ref_op;
01427 tn = ref_tn;
01428 ref_op = TN_Reaching_Value_At_Op(ref_tn, op, &kind, FALSE);
01429 }
01430 }
01431 OP* init_op = NULL;
01432 if(init_op_info) init_op = (OP*)hTN_MAP_Get(init_op_info, tn);
01433 if (init_op && OP_bb(init_op) == OP_bb(op))
01434 {
01435 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01436 children->push_back(
01437 (*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, init_op)))[0]);
01438 children->push_back(child2);
01439 Add_Partition(child1, children);
01440 }
01441 }
01442
01443
01444 void
01445 PARTITION_GRAPH::Look_Partition_For_And_Type(TN* tn, PARTITION_GRAPH_NODE*
01446 parent, PARTITION_GRAPH_NODE* child1, PARTITION_GRAPH_NODE* child2, OP* op)
01447 {
01448 if(tn == True_TN) return;
01449 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01450 OP* init_op = NULL;
01451 if(init_op_info) init_op = (OP*)hTN_MAP_Get(init_op_info, tn);
01452 children->push_back(child1);
01453 children->push_back(child2);
01454 if (init_op && OP_bb(init_op) == OP_bb(op))
01455 {
01456 Add_Partition((*((PG_CONTAINER*)OP_MAP_Get(_tn_node_map, init_op)))[0],
01457 children);
01458 }
01459 else
01460 {
01461 Add_Partition(parent, children);
01462 }
01463 DEF_KIND kind;
01464 PARTITION_GRAPH_NODE* node;
01465 INT i;
01466 TN* ref_tn;
01467 OP* ref_op=TN_Reaching_Value_At_Op(tn, op, &kind, FALSE);
01468 while (ref_op && OP_bb(ref_op) == OP_bb(op))
01469 {
01470 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01471 for(i=0; i<OP_opnds(ref_op); i++)
01472 {
01473 ref_tn = OP_opnd(ref_op, i);
01474 if(TNs_Are_Equivalent(tn, ref_tn))
01475 break;
01476 }
01477 node = (*((PG_CONTAINER*)OP_MAP_Get
01478 (_tn_node_map, ref_op)))[i+OP_results(ref_op)];
01479 children->push_back(node);
01480 children->push_back(child2);
01481 Add_Partition(child1, children);
01482 op = ref_op;
01483 tn = ref_tn;
01484 ref_op = TN_Reaching_Value_At_Op(ref_tn, op, &kind, FALSE);
01485 }
01486 }
01487
01488
01489 void
01490 PARTITION_GRAPH::Complete_Partition_Graph()
01491 {
01492 fflush(TFile);
01493 PG_CONTAINER::iterator iter;
01494 for (iter = _nodes.begin (); iter != _nodes.end (); ++iter)
01495 {
01496 PARTITION_GRAPH_NODE* node = *iter;
01497 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01498 fprintf(TFile, "\n\nStart to scan unreachable node!");
01499
01500 if ( !node -> Is_Reachable() && node->Index ()!=0
01501 && node ->Child_Partitions().empty())
01502 {
01503 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01504 fprintf(TFile, "\nunreachable node--%d!",(node)->Index());
01505 PG_CONTAINER rch_des_set(PRDB_pool);
01506 BOOL success = Find_Reachable_Descendant(&rch_des_set,node);
01507 PG_CONTAINER::iterator rch_iter;
01508 if(!success)
01509 {
01510 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01511 children->push_back(node);
01512 children->push_back(_dummy_node);
01513 Add_Partition(_root, children);
01514 continue;
01515 }
01516
01517 PARTITION_GRAPH_NODE* lca_node = NULL;
01518 for ( rch_iter = rch_des_set.begin();
01519 rch_iter != rch_des_set.end();
01520 rch_iter++) {
01521 lca_node = Get_Lca (lca_node,*rch_iter);
01522 }
01523 PG_CONTAINER comp(PRDB_pool);
01524 comp.clear();
01525 comp.push_back(lca_node);
01526 FmtAssert(Subtract(&comp, &rch_des_set),
01527 ("Unreachable node!!"));
01528 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
01529 children->push_back(node);
01530 for (rch_iter = comp.begin (); rch_iter!=comp.end (); rch_iter++)
01531 {
01532 children->push_back(*rch_iter);
01533 }
01534 if(children->size() == 1)
01535 children->push_back(_dummy_node);
01536 Add_Partition(lca_node, children);
01537 CXX_DELETE(&rch_des_set, PRDB_pool);
01538 CXX_DELETE(&comp, PRDB_pool);
01539 }
01540 }
01541
01542 }
01543
01544
01545 BOOL
01546 PARTITION_GRAPH::Find_Reachable_Descendant(PG_CONTAINER* result,
01547 PARTITION_GRAPH_NODE* node)
01548 {
01549 PT_CONTAINER partitions = node -> Parent_Partitions();
01550 if (!partitions.size()) return FALSE;
01551 PT_CONTAINER::iterator iter;
01552 for (iter = partitions.begin (); iter != partitions.end (); iter++)
01553 {
01554 BOOL success = TRUE;
01555 PG_CONTAINER tmp_res;
01556 PG_CONTAINER* children = &((*iter)-> Child());
01557 PG_CONTAINER::iterator iter1;
01558 for (iter1 = children->begin();
01559 iter1 != children->end ();
01560 iter1++)
01561 {
01562
01563 PARTITION_GRAPH_NODE* child = *iter1;
01564 if(child == _dummy_node)
01565 {
01566 success = FALSE;
01567 break;
01568 }
01569 if( child ->Is_Reachable())
01570 {
01571 if(child->Child_Partitions().size() <= 1)
01572 {
01573 success = FALSE;
01574 break;
01575 }
01576 tmp_res.push_back(child);
01577 }else {
01578 success &= Find_Reachable_Descendant(&tmp_res,child);
01579 if (!success)
01580 {
01581 tmp_res.clear();
01582 break;
01583 }
01584 }
01585 }
01586 if (success)
01587 {
01588 for(iter1 = tmp_res.begin(); iter1 != tmp_res.end(); iter1++)
01589 result->push_back(*iter1);
01590 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01591 fprintf(TFile, "\nReachable descendants found!!");
01592 return TRUE;
01593 }
01594 }
01595 return FALSE;
01596 }
01597
01598
01599 PARTITION_GRAPH_NODE*
01600 PARTITION_GRAPH::Get_Gcd(PARTITION_GRAPH_NODE* node1,
01601 PARTITION_GRAPH_NODE* node2)
01602 {
01603 if(node1 == _dummy_node || node2 == _dummy_node) return NULL;
01604 PT_CONTAINER partitions;
01605 PT_CONTAINER::iterator iter;
01606 partitions = node2->Child_Partitions();
01607 for(iter = partitions.begin();iter!=partitions.end();iter++)
01608 {
01609 if(node1 == (*iter)->Parent()) return node2;
01610 }
01611 partitions = node1->Child_Partitions();
01612 for(iter = partitions.begin();iter!=partitions.end();iter++)
01613 {
01614 if(node2 == (*iter)->Parent()) return node1;
01615 }
01616 partitions = node1->Parent_Partitions ();
01617 INT level = -1;
01618 PARTITION_GRAPH_NODE* gcd = NULL;
01619 for (iter = partitions.begin (); iter!=partitions.end (); iter++)
01620 {
01621 PG_CONTAINER node_set = (*iter)->Child();
01622 PG_CONTAINER::iterator pg_iter;
01623 for (pg_iter=node_set.begin (); pg_iter!=node_set.end (); pg_iter++)
01624 {
01625 PARTITION_GRAPH_NODE* child = *pg_iter;
01626 if ( !child->Is_Reachable ()) continue;
01627 PARTITION_GRAPH_NODE* descendant = Get_Gcd(node2, child);
01628 if(descendant)
01629 {
01630 if(level == -1 || descendant->Level ()<level)
01631 {
01632 level = descendant->Level ();
01633 gcd = descendant;
01634 }
01635 }
01636 }
01637 }
01638 if(partitions.size() == 0)
01639 {
01640 partitions = node2->Parent_Partitions();
01641 for (iter = partitions.begin (); iter!=partitions.end (); iter++)
01642 {
01643 PG_CONTAINER node_set = (*iter)->Child();
01644 PG_CONTAINER::iterator pg_iter;
01645 for (pg_iter=node_set.begin (); pg_iter!=node_set.end (); pg_iter++)
01646 {
01647 PARTITION_GRAPH_NODE* child = *pg_iter;
01648 if ( !child->Is_Reachable ()) continue;
01649 PARTITION_GRAPH_NODE* descendant = Get_Gcd(node1, child);
01650 if(descendant)
01651 {
01652 if(level == -1 || descendant->Level ()<level)
01653 {
01654 level = descendant->Level ();
01655 gcd = descendant;
01656 }
01657 }
01658 }
01659 }
01660 }
01661 return gcd;
01662 }
01663
01664 PARTITION_GRAPH_NODE*
01665 PARTITION_GRAPH::Get_Lca(PARTITION_GRAPH_NODE* node1,
01666 PARTITION_GRAPH_NODE* node2)
01667 {
01668 if(node1 == NULL) return node2;
01669 if(node2 == NULL) return node1;
01670 if(node1 == node2) return node1;
01671 PT_CONTAINER partitions;
01672 PT_CONTAINER::iterator iter;
01673 partitions = node1->Child_Partitions();
01674 INT level = -1;
01675 PARTITION_GRAPH_NODE* lca = NULL;
01676 for (iter = partitions.begin (); iter!=partitions.end (); iter++)
01677 {
01678 PARTITION_GRAPH_NODE* node = (*iter)->Parent();
01679 if(!node->Is_Reachable()) continue;
01680 PARTITION_GRAPH_NODE* ancestor = Get_Lca(node2, node);
01681 if(ancestor)
01682 {
01683 if(ancestor->Level ()>level)
01684 {
01685 level = ancestor->Level ();
01686 lca = ancestor;
01687 }
01688 }
01689 }
01690 if(partitions.size() == 0)
01691 {
01692 partitions = node2->Child_Partitions();
01693 for (iter = partitions.begin (); iter!=partitions.end (); iter++)
01694 {
01695 PARTITION_GRAPH_NODE* node = (*iter)->Parent();
01696 if(!node->Is_Reachable()) continue;
01697 PARTITION_GRAPH_NODE* ancestor = Get_Lca(node1, node);
01698 if(ancestor)
01699 {
01700 if(ancestor->Level ()>level)
01701 {
01702 level = ancestor->Level ();
01703 lca = ancestor;
01704 }
01705 }
01706 }
01707 }
01708 return lca;
01709 }
01710
01711
01712 void
01713 PARTITION_GRAPH::Add_Partition(PARTITION_GRAPH_NODE* parent,
01714 PG_CONTAINER* children)
01715 {
01716 PARTITION* partition = CXX_NEW(PARTITION(), PRDB_pool);
01717 partition->Parent(parent);
01718 PG_CONTAINER::iterator iter;
01719 for(iter = children->begin(); iter != children->end(); iter++)
01720 {
01721 Is_True(parent->Index()!=(*iter)->Index(), ("Illegal partition"));
01722 partition->Add_Child(*iter);
01723 }
01724 PT_CONTAINER par_list = parent->Parent_Partitions();
01725 for (INT i = 0; i<par_list.size (); i++)
01726 {
01727 if (*partition == par_list[i])
01728 {
01729 CXX_DELETE(partition, PRDB_pool);
01730 return;
01731 }
01732 }
01733 parent -> Add_Parent_Partition(partition);
01734
01735 for (iter = children->begin(); iter != children->end(); iter++)
01736 {
01737 PARTITION_GRAPH_NODE* child = *iter;
01738 child -> Add_Child_Partition(partition);
01739 if(parent->Is_Reachable())
01740 {
01741 if ( child -> Level() < (parent -> Level() +1))
01742 child -> Level(parent -> Level() +1);
01743 }
01744 }
01745 }
01746
01747 PG_CONTAINER*
01748 PARTITION_GRAPH::Get_Subset_Nodes(PARTITION_GRAPH_NODE* node)
01749 {
01750 PG_CONTAINER* result = CXX_NEW(PG_CONTAINER, PRDB_pool);
01751 result->push_back(node);
01752 PT_CONTAINER partitions = node->Parent_Partitions();
01753 PT_CONTAINER::iterator iter;
01754 for(iter = partitions.begin(); iter != partitions.end();++iter)
01755 {
01756 PARTITION* part = *iter;
01757 PG_CONTAINER children = part->Child();
01758 PG_CONTAINER::iterator pg_iter;
01759 for(pg_iter = children.begin(); pg_iter != children.end();++pg_iter)
01760 {
01761 if(*pg_iter == _dummy_node) continue;
01762 PG_CONTAINER *tmp_res = Get_Subset_Nodes(*pg_iter);
01763 PG_CONTAINER::iterator tmp_iter;
01764 for(tmp_iter = tmp_res->begin(); tmp_iter != tmp_res->end(); ++tmp_iter)
01765 result->push_back(*tmp_iter);
01766 }
01767 }
01768 if(result->size() > 1) Reduce(result, FALSE);
01769 return result;
01770 }
01771
01772
01773 void
01774 PARTITION_GRAPH::Pre_Computing(){
01775
01776
01777
01778 for (INT i=0; i<partition_graph_node_number; i++)
01779 {
01780 BV_VECTOR bvector(PRDB_pool);
01781 for(INT j=0; j<partition_graph_node_number; j++)
01782 {
01783 bvector.push_back(FALSE);
01784 }
01785 _disjoint_relation.push_back (bvector);
01786 _subset_relation.push_back (bvector);
01787
01788
01789 if (i != 0) _subset_relation[i][i] = TRUE;
01790 }
01791 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)) {
01792 fprintf(TFile, "number_of_ptn_node is %d!\n", partition_graph_node_number);
01793 fprintf(TFile, "\nInitialization accomplished!\n");
01794 }
01795
01796
01797 for (INT i=0; i<partition_graph_node_number; i++){
01798 PARTITION_GRAPH_NODE* node = _nodes[i];
01799
01800
01801 if ( node == _dummy_node) continue;
01802 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01803 fprintf(TFile, "\nReady to set subset relation node-%d!", node->Index());
01804 PG_CONTAINER* subset = Get_Subset_Nodes(node);
01805 PG_CONTAINER:: iterator iter;
01806 for(iter = subset->begin(), ++iter; iter != subset->end(); ++iter)
01807 Set_Subset(*iter, node);
01808 CXX_DELETE(subset, PRDB_pool);
01809 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01810 fprintf(TFile, "\nsubset relation accomplished !");
01811
01812 PT_CONTAINER& partitions = node -> Parent_Partitions();
01813 PT_CONTAINER::iterator pt_iter;
01814 for (pt_iter = partitions.begin ();
01815 pt_iter != partitions.end ();
01816 pt_iter++)
01817 {
01818 PARTITION* partition = (*pt_iter);
01819 PG_CONTAINER& children = partition -> Child();
01820 PG_CONTAINER::iterator pg_iter;
01821 for (pg_iter = children.begin();
01822 pg_iter != children.end();
01823 pg_iter++){
01824 PARTITION_GRAPH_NODE* child1 = *pg_iter;
01825 if ( child1 == _dummy_node ) continue;
01826
01827
01828 PG_CONTAINER::iterator pg_iter1;
01829 for (pg_iter1 = pg_iter;
01830 pg_iter1 != children.end();
01831 pg_iter1++){
01832 if (pg_iter == pg_iter1 || *pg_iter1 == _dummy_node)
01833 continue;
01834 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01835 fprintf(TFile, "\nReady to set disjoint relation!");
01836 Set_Disjoint(child1, *pg_iter1);
01837 Rec_Set_Disjoint(child1, *pg_iter1);
01838 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01839 fprintf(TFile, "\nDisjoint relation accomplished!");
01840 }
01841
01842 }
01843 }
01844 }
01845
01846 }
01847
01848
01849 PARTITION_GRAPH_NODE*
01850 PARTITION_GRAPH::Find_Node_In_OP(TN_OP_PAIR* tn_op)
01851 {
01852 Is_True(tn_op, ("Input is NULL tn_op and can't get its node"));
01853 TN* tn = tn_op->first;
01854 const OP* op = tn_op->second;
01855 PG_CONTAINER* node_set = (PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op);
01856 if(!node_set){
01857
01858
01859 return NULL;
01860 }
01861
01862 INT i;
01863 for(i=0;i<(OP_results(op)+OP_opnds(op));i++)
01864 {
01865 if(i<OP_results(op))
01866 {
01867 if(tn == OP_result(op, i))
01868 break;
01869 }
01870 else
01871 {
01872 if(tn == OP_opnd(op, i-OP_results(op)))
01873 break;
01874 }
01875 }
01876 Is_True(i<(OP_results(op)+OP_opnds(op)), ("Invalid OP and TN!"));
01877 return (*node_set)[i];
01878 }
01879
01880
01881 void
01882 PARTITION_GRAPH::Rec_Set_Disjoint(PARTITION_GRAPH_NODE* child1,
01883 PARTITION_GRAPH_NODE* child2)
01884 {
01885 PG_CONTAINER* nodes1 = Get_Subset_Nodes(child1);
01886 PG_CONTAINER* nodes2 = Get_Subset_Nodes(child2);
01887 PG_CONTAINER::iterator iter1, iter2;
01888 for(iter1 = nodes1->begin(); iter1 != nodes1->end(); ++iter1)
01889 {
01890 if(*iter1 == _dummy_node) continue;
01891 for(iter2 = nodes2->begin(); iter2 != nodes2->end();++iter2)
01892 {
01893 if(*iter2 == _dummy_node) continue;
01894 Set_Disjoint(*iter1, *iter2);
01895 }
01896 }
01897 CXX_DELETE(nodes1, PRDB_pool);
01898 CXX_DELETE(nodes2, PRDB_pool);
01899
01900 }
01901
01902 void
01903 PARTITION_GRAPH::Set_Disjoint(PARTITION_GRAPH_NODE* child1,
01904 PARTITION_GRAPH_NODE* child2)
01905 {
01906 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE)) {
01907 fprintf(TFile, "true_disjoint_relation found!\n");
01908 fprintf(TFile, "\tnode-%d and node-%d are disjoint!\t",
01909 child1->Index (), child2->Index ());
01910 }
01911 _disjoint_relation[child1 -> Index()][child2 -> Index()] = TRUE;
01912 _disjoint_relation[child2 -> Index()][child1 -> Index()] = TRUE;
01913 }
01914
01915 void
01916 PARTITION_GRAPH::Set_Subset(PARTITION_GRAPH_NODE* child,
01917 PARTITION_GRAPH_NODE* node)
01918 {
01919 if(Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
01920 fprintf(TFile, "\tnode-%d and node-%d are subset!\t",
01921 child->Index (), node->Index ());
01922 Is_True(!_subset_relation[node->Index()][child->Index()],
01923 ("cycle partition!"));
01924 _subset_relation[child -> Index()][node -> Index()] = TRUE;
01925 }
01926
01927 BOOL
01928 PARTITION_GRAPH::Subtract(PG_CONTAINER* result, PARTITION_GRAPH_NODE* des)
01929 {
01930 PG_CONTAINER::iterator iter;
01931 PARTITION_GRAPH_NODE* node;
01932 for(iter = result->begin(); iter != result->end(); iter++)
01933 {
01934 if(*iter == des)
01935 {
01936 iter = result->erase(iter);
01937 return TRUE;
01938 }
01939 }
01940 PT_CONTAINER prt_set = des->Child_Partitions ();
01941 PT_CONTAINER::iterator pt_iter;
01942 for (pt_iter = prt_set.begin (); pt_iter!=prt_set.end (); pt_iter++)
01943 {
01944 node = (*pt_iter)->Parent();
01945 if(!node->Is_Reachable()) continue;
01946 if(Subtract(result, node))
01947 {
01948 PG_CONTAINER tmp_result;
01949 tmp_result.clear();
01950 Find_Sibling(&tmp_result, node, des);
01951 PG_CONTAINER::iterator pg_iter;
01952 for(pg_iter=tmp_result.begin();pg_iter!=tmp_result.end();pg_iter++)
01953 result->push_back(*pg_iter);
01954 return TRUE;
01955 }
01956 }
01957 return FALSE;
01958 }
01959
01960 BOOL
01961 PARTITION_GRAPH::Subtract(PG_CONTAINER* result, PG_CONTAINER* set)
01962 {
01963 PG_CONTAINER::iterator iter;
01964 for (iter=set->begin (); iter!=set->end (); iter++)
01965 {
01966 if(!Subtract(result, *iter))
01967 {
01968 result->clear();
01969 if(iter == set->begin()) return FALSE;
01970 else {
01971 result->push_back(_dummy_node);
01972 return TRUE;
01973 }
01974 }
01975 }
01976 return TRUE;
01977 }
01978
01979 void
01980 PARTITION_GRAPH::Find_Sibling(PG_CONTAINER *result,
01981 PARTITION_GRAPH_NODE *anc, PARTITION_GRAPH_NODE *des)
01982 {
01983 if(des == _dummy_node) return;
01984
01985 PT_CONTAINER part_set = des->Child_Partitions ();
01986 PT_CONTAINER::iterator iter;
01987 PARTITION_GRAPH_NODE* node;
01988 for (iter = part_set.begin (); iter != part_set.end (); iter++)
01989 {
01990 node = (*iter)->Parent();
01991 if (node == anc) break;
01992 }
01993 if (iter == part_set.end ()) return;
01994 PARTITION* part = *iter;
01995 PG_CONTAINER node_set = part->Child ();
01996 PG_CONTAINER::iterator pg_iter;
01997 for (pg_iter = node_set.begin (); pg_iter!=node_set.end (); pg_iter++)
01998 {
01999 if ((*pg_iter) == des || (*pg_iter) == _dummy_node) continue;
02000 result->push_back (*pg_iter);
02001 }
02002 }
02003
02004 void PARTITION_GRAPH::Mark_Level(PARTITION_GRAPH_NODE *node)
02005 {
02006 _visited[node->Index()] = TRUE;
02007
02008 if(node == _dummy_node) return;
02009 PT_CONTAINER partitions = node->Child_Partitions ();
02010 PT_CONTAINER::iterator iter;
02011 PARTITION_GRAPH_NODE* pnode;
02012
02013 if (node->Level ()<0)
02014 {
02015 for(iter = partitions.begin (); iter!=partitions.end (); ++iter)
02016 {
02017 pnode = (*iter)->Parent();
02018 if(pnode->Level ()>node->Level ()+1)
02019 node->Level (pnode->Level ()+1);
02020 }
02021 }
02022 partitions = node->Parent_Partitions ();
02023 if(!partitions.size()) return;
02024 for (iter = partitions.begin (); iter!=partitions.end (); ++iter)
02025 {
02026 PG_CONTAINER nd_set = (*iter)->Child();
02027 PG_CONTAINER::iterator piter;
02028 for (piter = nd_set.begin (); piter != nd_set.end (); ++piter)
02029 {
02030 pnode = (*piter);
02031 if(pnode == _dummy_node) continue;
02032 if(pnode->Level ()<node->Level ()+1)
02033 pnode->Level (node->Level ()+1);
02034 if (!_visited[pnode->Index()])
02035 Mark_Level(pnode);
02036 }
02037 }
02038
02039 }
02040
02041 BOOL
02042 PARTITION_GRAPH::Is_Disjoint(TN_OP_PAIR tp1, TN_OP_PAIR tp2)
02043 {
02044 Is_True(tp1.first&&tp2.first&&tp1.second&&tp2.second,
02045 ("Illegal input with NULL TN or OP for disjoint!"));
02046 if(tp1.first == True_TN || tp2.first == True_TN) return FALSE;
02047 if(Compare_Type(OP_code(tp1.second)) == COMPARE_TYPE_unc ||
02048 Compare_Type(OP_code(tp2.second)) == COMPARE_TYPE_unc) return FALSE;
02049 INT index1,index2;
02050 PARTITION_GRAPH_NODE* node = NULL;
02051 node = Find_Node_In_OP(&tp1);
02052 if(!node) return FALSE;
02053 Is_True(node, ("Can't get tp1's tn node!"));
02054 index1 = node->Index ();
02055
02056 node = Find_Node_In_OP(&tp2);
02057 if(!node) return FALSE;
02058 Is_True(node, ("Can't get tp2's tn node!"));
02059 index2 = node->Index ();
02060 if(Get_Trace(TP_A_PRDB, TT_PRDB_APP)) {
02061 const OP* op1, *op2;
02062 op1 = tp1.second;
02063 op2 = tp2.second;
02064 fprintf(TFile, "number_of_query_PU_%d\n", Current_PU_Count());
02065 if(OP_opnd(op1, OP_PREDICATE_OPND) != True_TN && OP_opnd(op2, OP_PREDICATE_OPND) != True_TN)
02066 {
02067 fprintf(TFile, "non_pr0_predicate_query_PU_%d\n", Current_PU_Count());
02068 if(_disjoint_relation[index1][index2])
02069 fprintf(TFile, "true_disjoint_PU_%d\n", Current_PU_Count());
02070 else
02071 {
02072 fprintf(TFile, "non_disjoint_PU_%d :", Current_PU_Count());
02073 Print_OP(op1);
02074 Print_OP(op2);
02075 fprintf(TFile, "\n");
02076 }
02077 }
02078 }
02079
02080 return _disjoint_relation[index1][index2];
02081
02082 }
02083
02084 void
02085 PARTITION_GRAPH::Add_Relation(PARTITION_GRAPH_NODE* child,
02086 PARTITION_GRAPH_NODE* parent)
02087 {
02088 INT index1, index2;
02089 index1 = parent->Index();
02090 index2 = child->Index();
02091 PG_CONTAINER::iterator iter;
02092 BV_VECTOR bvector(PRDB_pool);
02093 INT i = _disjoint_relation.size()-1;
02094 for(; i >= 0; i--)
02095 {
02096 _disjoint_relation[i].push_back(FALSE);
02097 _subset_relation[i].push_back(FALSE);
02098 bvector.push_back(FALSE);
02099 }
02100 bvector.push_back(TRUE);
02101 _disjoint_relation.push_back (bvector);
02102 _subset_relation.push_back (bvector);
02103 for(iter=_nodes.begin();iter!=_nodes.end();iter++)
02104 {
02105 if(_disjoint_relation[index1][(*iter)->Index()])
02106 {
02107 _disjoint_relation[index2][(*iter)->Index()]=TRUE;
02108 _disjoint_relation[(*iter)->Index()][index2]=TRUE;
02109 }
02110 if(_subset_relation[(*iter)->Index()][index1])
02111 _subset_relation[(*iter)->Index()][index2] = TRUE;
02112 }
02113 _subset_relation[index1][index2] = TRUE;
02114 }
02115
02116 BOOL
02117 PARTITION_GRAPH::Is_Disjoint(BB* bb1, BB* bb2)
02118 {
02119 Is_True(bb1&&bb2,("Illegal input with NULL BB for disjoint!"));
02120 INT index1,index2;
02121 PARTITION_GRAPH_NODE* node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb1);
02122 index1 = node->Index ();
02123 node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb2);
02124 index2 = node->Index ();
02125 return _disjoint_relation[index1][index2];
02126 }
02127
02128 BOOL
02129 PARTITION_GRAPH::Is_Subset(TN_OP_PAIR tp1, TN_OP_PAIR tp2)
02130 {
02131 Is_True(tp1.first&&tp2.first&&tp1.second&&tp2.second,
02132 ("Illegal input with NULL TN or OP for subset!"));
02133 INT index1,index2;
02134 PARTITION_GRAPH_NODE* node = NULL;
02135 node = Find_Node_In_OP(&tp1);
02136 if(!node) return FALSE;
02137 Is_True(node, ("Can't get tp1's tn node!"));
02138 index1 = node->Index ();
02139
02140 node = Find_Node_In_OP(&tp2);
02141 if(!node) return FALSE;
02142 Is_True(node, ("Can't get tp2's tn node!"));
02143 index2 = node->Index ();
02144 return _subset_relation[index1][index2];
02145
02146 }
02147
02148 BOOL
02149 PARTITION_GRAPH::Is_Subset(BB* bb1, BB* bb2)
02150 {
02151 Is_True(bb1&&bb2,("Illegal input with NULL BB for subset!"));
02152 INT index1,index2;
02153 PARTITION_GRAPH_NODE* node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb1);
02154 index1 = node->Index ();
02155 node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb2);
02156 index2 = node->Index ();
02157 return _subset_relation[index1][index2];
02158 }
02159
02160 BOOL
02161 PARTITION_GRAPH::Is_Superset(TN_OP_PAIR tp1, TN_OP_PAIR tp2)
02162 {
02163 Is_True(tp1.first&&tp2.first&&tp1.second&&tp2.second,
02164 ("Illegal input with NULL TN or OP for superset!"));
02165 INT index1,index2;
02166 PARTITION_GRAPH_NODE* node = NULL;
02167 node = Find_Node_In_OP(&tp1);
02168 Is_True(node, ("Can't get tp1's tn node!"));
02169 index1 = node->Index ();
02170
02171 node = Find_Node_In_OP(&tp2);
02172 Is_True(node, ("Can't get tp2's tn node!"));
02173 index2 = node->Index ();
02174 return _subset_relation[index2][index1];
02175
02176 }
02177
02178 BOOL
02179 PARTITION_GRAPH::Is_Superset(BB* bb1, BB* bb2)
02180 {
02181 Is_True(bb1&&bb2,("Illegal input with NULL BB for superset!"));
02182 INT index1,index2;
02183 PARTITION_GRAPH_NODE* node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb1);
02184 index1 = node->Index ();
02185 node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb2);
02186 index2 = node->Index ();
02187 return _subset_relation[index2][index1];
02188 }
02189
02190 BOOL
02191 PARTITION_GRAPH::Get_Complementary(TP_CONTAINER* result, TN_OP_PAIR tp,
02192 TN_OP_PAIR base_tp)
02193 {
02194 Is_True(result&&tp.first&&tp.second&&base_tp.first&&base_tp.second,
02195 ("Illegal input with NULL value for complementary!"));
02196 PG_CONTAINER::iterator iter;
02197 PARTITION_GRAPH_NODE* node, *base_node;
02198 node = Find_Node_In_OP(&tp);
02199 Is_True(node, ("Can't get tp's tn node!"));
02200 base_node = Find_Node_In_OP(&base_tp);
02201 Is_True(base_node, ("Can't get base_tp's tn node!"));
02202 PG_CONTAINER tmp_result;
02203 tmp_result.clear();
02204 tmp_result.push_back(base_node);
02205 if(Subtract(&tmp_result, node))
02206 {
02207 for(iter = tmp_result.begin ();iter!=tmp_result.end ();iter++)
02208 {
02209 node = *iter;
02210 if(node->Get_TNs().empty()) continue;
02211 result->push_back(node->Get_TNs ()[0]);
02212 }
02213 return TRUE;
02214 }
02215 return FALSE;
02216 }
02217
02218 BOOL
02219 PARTITION_GRAPH::Get_Complementary(TP_CONTAINER* result, TN_OP_PAIR tp,
02220 BB* base_bb)
02221 {
02222 PG_CONTAINER::iterator iter;
02223 PARTITION_GRAPH_NODE* node, *base_node;
02224 node = Find_Node_In_OP(&tp);
02225 Is_True(node, ("Can't get tp's tn node!"));
02226 base_node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, base_bb);
02227 PG_CONTAINER tmp_result;
02228 tmp_result.clear();
02229 tmp_result.push_back(base_node);
02230 if(Subtract(&tmp_result, node))
02231 {
02232 for(iter = tmp_result.begin ();iter!=tmp_result.end ();iter++)
02233 {
02234 node = *iter;
02235 if(node->Get_TNs().empty()) continue;
02236 result->push_back(node->Get_TNs ()[0]);
02237 }
02238 return TRUE;
02239 }
02240 return FALSE;
02241 }
02242
02243 TN*
02244 PARTITION_GRAPH::Get_Complementary(TN_OP_PAIR tp, BB* base_bb)
02245 {
02246 if(BB_succs_len(base_bb) == 2 && BB_kind(base_bb) == BBKIND_LOGIF) {
02247 TN* tn = tp.first;
02248 BBLIST* succs = BB_succs(base_bb);
02249 BB* fall_bb = BBLIST_item(succs);
02250 BB* targ_bb = BBLIST_item(BBLIST_next(succs));
02251 if(fall_bb && targ_bb && BB_preds_len(fall_bb) == 1 && BB_preds_len(targ_bb) == 1
02252 && Home_Region(base_bb) == Home_Region(fall_bb) &&
02253 Home_Region(base_bb) == Home_Region(targ_bb)) {
02254 PARTITION_GRAPH_NODE* fall_node = (PARTITION_GRAPH_NODE*) BB_MAP_Get(_bb_node_map, fall_bb);
02255 PARTITION_GRAPH_NODE* targ_node = (PARTITION_GRAPH_NODE*) BB_MAP_Get(_bb_node_map, targ_bb);
02256 if(tn == fall_node->Control_Pred()) return targ_node->Control_Pred();
02257 if(tn == targ_node->Control_Pred()) return fall_node->Control_Pred();
02258 }
02259 }
02260 PARTITION_GRAPH_NODE* node, *base_node;
02261 node = Find_Node_In_OP(&tp);
02262 Is_True(node, ("Can't get tp's tn node!"));
02263 base_node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, base_bb);
02264 PG_ALLOC res_mem(PRDB_pool);
02265 PG_CONTAINER tmp_result(res_mem);
02266 Find_Sibling(&tmp_result, base_node, node);
02267 if(tmp_result.size() != 1 ) return NULL;
02268 PARTITION_GRAPH_NODE* com_node = *tmp_result.begin();
02269 TN_OP_PAIR* tn_op = *com_node->Get_TNs().begin();
02270 Is_True(tn_op->second, ("TN's complement should exist!"));
02271 return tn_op->first;
02272 }
02273
02274 BOOL
02275 PARTITION_GRAPH::Is_Complementary(TN_OP_PAIR tp1,TN_OP_PAIR tp2,
02276 TN_OP_PAIR tp3)
02277 {
02278 Is_True(tp1.first&&tp2.first&&tp3.first&&tp1.second&&tp2.second&&tp3.second,
02279 ("Illegal input with NULL TN or OP for comlementary!"));
02280 PG_CONTAINER* node_set;
02281 PG_CONTAINER::iterator iter;
02282 PT_CONTAINER partitions;
02283 PT_CONTAINER::iterator pt_iter;
02284 PARTITION_GRAPH_NODE* node1, *node2, *base_node;
02285 node1 = Find_Node_In_OP(&tp1);
02286 Is_True(node1, ("Can't get tp1's tn node!"));
02287 node2 = Find_Node_In_OP(&tp2);
02288 Is_True(node2, ("Can't get tp2's tn node!"));
02289 base_node = Find_Node_In_OP(&tp3);
02290 Is_True(base_node, ("Can't get tp3's tn node!"));
02291 if(node1 == node2) return FALSE;
02292 partitions = base_node->Parent_Partitions ();
02293 for (pt_iter=partitions.begin (); pt_iter!=partitions.end (); pt_iter++)
02294 {
02295 BOOL Ex_node1 = FALSE;
02296 BOOL Ex_node2 = FALSE;
02297 node_set = &((*pt_iter)->Child());
02298 for(iter = node_set->begin (); iter!=node_set->end (); iter++)
02299 {
02300 if ((*iter) == node1) Ex_node1 = TRUE;
02301 if ((*iter) == node2) Ex_node2 = TRUE;
02302 }
02303 if (Ex_node1 && Ex_node2) return TRUE;
02304 }
02305 return FALSE;
02306 }
02307
02308
02309 BOOL
02310 PARTITION_GRAPH::Is_Complementary(TN_OP_PAIR tp1,TN_OP_PAIR tp2, BB* bb)
02311 {
02312 Is_True(tp1.first&&tp1.second&&tp2.first&&tp2.second&&bb,
02313 ("Illegal input with NULL value for complementary!"));
02314 PG_CONTAINER* node_set;
02315 PG_CONTAINER::iterator iter;
02316 PT_CONTAINER partitions;
02317 PT_CONTAINER::iterator pt_iter;
02318 PARTITION_GRAPH_NODE* node1, *node2, *base_node;
02319 base_node = (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, bb);
02320 node1 = Find_Node_In_OP(&tp1);
02321 Is_True(node1, ("Can't get tp1's tn node!"));
02322 node2 = Find_Node_In_OP(&tp2);
02323 Is_True(node2, ("Can't get tp2's tn node!"));
02324 if(node1 == node2) return FALSE;
02325 partitions = base_node->Parent_Partitions ();
02326 for (pt_iter=partitions.begin (); pt_iter!=partitions.end (); pt_iter++)
02327 {
02328 BOOL Ex_node1 = FALSE;
02329 BOOL Ex_node2 = FALSE;
02330 node_set = &((*pt_iter)->Child());
02331 for(iter = node_set->begin (); iter!=node_set->end (); iter++)
02332 {
02333 if ((*iter) == node1) Ex_node1 = TRUE;
02334 if ((*iter) == node2) Ex_node2 = TRUE;
02335 }
02336 if (Ex_node1 && Ex_node2) return TRUE;
02337 }
02338 return FALSE;
02339 }
02340
02341 BOOL
02342 PARTITION_GRAPH::Is_Complementary(PARTITION_GRAPH_NODE* node1,
02343 PARTITION_GRAPH_NODE* node2,
02344 PARTITION_GRAPH_NODE* base_node)
02345 {
02346 Is_True(node1&&node2&&base_node, ("Illegal input with NULL for complementary!"));
02347 if(node1 == node2) return FALSE;
02348 PG_CONTAINER* node_set;
02349 PG_CONTAINER::iterator iter;
02350 PT_CONTAINER partitions;
02351 PT_CONTAINER::iterator pt_iter;
02352 partitions = base_node->Parent_Partitions ();
02353 for (pt_iter=partitions.begin (); pt_iter!=partitions.end (); pt_iter++)
02354 {
02355 BOOL Ex_node1 = FALSE;
02356 BOOL Ex_node2 = FALSE;
02357 node_set = &((*pt_iter)->Child());
02358 for(iter = node_set->begin (); iter!=node_set->end (); iter++)
02359 {
02360 if ((*iter) == node1) Ex_node1 = TRUE;
02361 if ((*iter) == node2) Ex_node2 = TRUE;
02362 }
02363 if (Ex_node1 && Ex_node2) return TRUE;
02364 }
02365 return FALSE;
02366 }
02367
02368 BOOL
02369 PARTITION_GRAPH::Cycle_Detector()
02370 {
02371 PG_CONTAINER::iterator iter;
02372 for (iter = _nodes.begin (); iter != _nodes.end (); iter++)
02373 {
02374 PARTITION_GRAPH_NODE* node = *iter;
02375 if(node == _dummy_node) continue;
02376 PT_CONTAINER* partitions = &(node->Child_Partitions ());
02377 PT_CONTAINER::iterator pt_iter;
02378 for (pt_iter=partitions->begin();pt_iter!=partitions->end();pt_iter++)
02379 {
02380 PARTITION_GRAPH_NODE* parent = (*pt_iter)->Parent();
02381 if (_subset_relation[parent->Index ()][node->Index ()])
02382 {
02383 printf("\nNode-%d and Node-%d are cycle!!\n",
02384 node->Index(),parent->Index());
02385 return TRUE;
02386 }
02387 }
02388 }
02389 return FALSE;
02390 }
02391
02392 BOOL
02393 PARTITION_GRAPH::Illegal_Partition()
02394 {
02395 PG_CONTAINER::iterator iter;
02396 for (iter = _nodes.begin (); iter != _nodes.end (); iter++)
02397 {
02398 PARTITION_GRAPH_NODE* node = *iter;
02399 if(node == _dummy_node) continue;
02400 PT_CONTAINER* partitions = &(node->Child_Partitions ());
02401 PT_CONTAINER::iterator pt_iter1, pt_iter2;
02402 for (pt_iter1=partitions->begin();pt_iter1!=partitions->end();pt_iter1++)
02403 {
02404 PARTITION_GRAPH_NODE* father = (*pt_iter1)->Parent();
02405 for(pt_iter2=pt_iter1;pt_iter2!=partitions->end ();pt_iter2++)
02406 {
02407 PARTITION_GRAPH_NODE* mother = (*pt_iter2)->Parent();
02408 if (_disjoint_relation[father->Index ()][mother->Index ()])
02409 {
02410 printf("\nNode-%d and node-%d are illegal!!\n",
02411 father->Index(),mother->Index());
02412 return TRUE;
02413 }
02414 }
02415 }
02416 }
02417 return FALSE;
02418 }
02419
02420 float
02421 PARTITION_GRAPH::Get_Probability(TN* tn)
02422 {
02423 float rt_freq,tn_freq;
02424 BB* bb = BB_SET_Choose(_root->Get_BBs());
02425 if(bb == BB_SET_CHOOSE_FAILURE) return 0.0;
02426 rt_freq = BB_freq(bb);
02427 if(!frequency_of_predicates)
02428 return 0.0;
02429 else
02430 {
02431 tn_freq = hTN_MAPf_Get(frequency_of_predicates, tn);
02432 return (tn_freq/rt_freq);
02433 }
02434 }
02435
02436 float
02437 PARTITION_GRAPH::Get_Probability(TN* tn1, TN* tn2)
02438 {
02439 float tn_prob1, tn_prob2;
02440 tn_prob1 = Get_Probability(tn1);
02441 tn_prob2 = Get_Probability(tn2);
02442 if(tn_prob2 > 0)
02443 return (tn_prob1/tn_prob2);
02444 else
02445 return 0.0;
02446 }
02447
02448 void
02449 PARTITION_GRAPH::Update(OP* op, BB* tgt_BB,CODE_MOTION_TYPE type)
02450 {
02451 TOP opcode = OP_code(op);
02452 if(Compare_Type(opcode) == -1 && !OP_has_predicate(op)) return;
02453 switch(type) {
02454 case COPY_TO:
02455 Copy_To(op, tgt_BB);
02456 break;
02457 case MOVE_TO:
02458 Move_To(op, tgt_BB);
02459 break;
02460 case DELETE:
02461 Delete(op);
02462 break;
02463 default:
02464 Is_True(FALSE, ("Unknown code motion type!"));
02465 return;
02466 }
02467 }
02468
02469 void
02470 PARTITION_GRAPH::Copy_To(OP* op, BB* tgt_BB)
02471 {
02472 Is_True(tgt_BB, ("move op to NULL BB!"));
02473 TOP opcode = OP_code(op);
02474 PARTITION_GRAPH_NODE* qp_parent = NULL;
02475 PARTITION_GRAPH_NODE* tgt_node =
02476 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, tgt_BB);
02477 PG_CONTAINER* op_node_set = CXX_NEW(PG_CONTAINER, PRDB_pool);
02478 if(!OP_has_predicate(op)) return;
02479 if(OP_opnd(op, OP_PREDICATE_OPND) == True_TN)
02480 qp_parent = tgt_node;
02481 else
02482 {
02483 DEF_KIND kind;
02484 TN* qp = OP_opnd(op,OP_PREDICATE_OPND);
02485 OP* def_op = TN_Reaching_Value_At_Op(qp, op, &kind, TRUE);
02486 BB* bb = def_op ? OP_bb(def_op) : NULL;
02487 if(bb == tgt_BB || (bb && BB_MAP_Get(_bb_node_map, bb) == BB_MAP_Get(_bb_node_map, tgt_BB)))
02488 {
02489 TN_OP_PAIR* tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02490 tn_op->first = qp;
02491 tn_op->second = def_op;
02492 qp_parent = Find_Node_In_OP(tn_op);
02493 Is_True(qp_parent, ("copy op's def_op should have partition graph node!!"));
02494 tn_op->second = op;
02495 qp_parent->Add_Related_TN(tn_op);
02496 }
02497 else
02498 {
02499 qp_parent = CXX_NEW(PARTITION_GRAPH_NODE(), PRDB_pool);
02500 qp_parent -> Index(partition_graph_node_number++);
02501 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
02502 children->push_back(qp_parent);
02503 children->push_back(_dummy_node);
02504 Add_Partition(tgt_node, children);
02505
02506
02507 Add_Relation(qp_parent, tgt_node);
02508 }
02509 }
02510
02511 if(Compare_Type(opcode) >= 0 && OP_result(op, 0) != True_TN
02512 && OP_result(op, 1) != True_TN)
02513 {
02514 PARTITION_GRAPH_NODE* p1_new = CXX_NEW(PARTITION_GRAPH_NODE(),
02515 PRDB_pool);
02516 p1_new-> Index(partition_graph_node_number++);
02517 TN_OP_PAIR* tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02518 tn_op->first = OP_result(op, 0);
02519 tn_op->second = op;
02520 p1_new->Add_Related_TN (tn_op);
02521 PARTITION_GRAPH_NODE* p2_new = CXX_NEW(PARTITION_GRAPH_NODE(),
02522 PRDB_pool);
02523 p2_new-> Index(partition_graph_node_number++);
02524 tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02525 tn_op->first = OP_result(op, 1);
02526 p2_new->Add_Related_TN (tn_op);
02527 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
02528 children->push_back(p1_new);
02529 children->push_back(p2_new);
02530 Add_Partition(qp_parent, children);
02531 Add_Relation(p1_new, qp_parent);
02532 Add_Relation(p2_new, qp_parent);
02533 _disjoint_relation[p1_new->Index()][p2_new->Index()] = TRUE;
02534 op_node_set->push_back(p1_new);
02535 op_node_set->push_back(p2_new);
02536 }
02537 else {
02538 PG_CONTAINER* children = CXX_NEW(PG_CONTAINER, PRDB_pool);
02539 for(INT i = 0; i<OP_results(op); i++) {
02540 if(TN_is_constant(OP_result(op,i))||TN_is_true_pred(OP_result(op, i))||
02541 TN_register_class(OP_result(op,i)) != ISA_REGISTER_CLASS_predicate)
02542 {
02543 op_node_set->push_back(NULL);
02544 continue;
02545 }
02546 PARTITION_GRAPH_NODE* p_new = CXX_NEW(PARTITION_GRAPH_NODE(),
02547 PRDB_pool);
02548 p_new-> Index(partition_graph_node_number++);
02549 TN_OP_PAIR* tn_op = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02550 tn_op->first = OP_result(op, i);
02551 tn_op->second = op;
02552 p_new->Add_Related_TN (tn_op);
02553 children->push_back(p_new);
02554 op_node_set->push_back(p_new);
02555 }
02556 if(children->size() == 1) {
02557 children->push_back(_dummy_node);
02558 Add_Partition(qp_parent, children);
02559 Add_Relation(*children->begin(), qp_parent);
02560 }
02561 }
02562 op_node_set->push_back(qp_parent);
02563 OP_MAP_Set(_tn_node_map, op, op_node_set);
02564
02565 }
02566
02567 void
02568 PARTITION_GRAPH::Move_To(OP* op, BB* tgt_BB)
02569 {
02570 BB* op_bb = OP_bb(op);
02571 PARTITION_GRAPH_NODE* src_node =
02572 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, op_bb);
02573 PARTITION_GRAPH_NODE* tgt_node =
02574 (PARTITION_GRAPH_NODE*)BB_MAP_Get(_bb_node_map, tgt_BB);
02575 if(src_node == tgt_node) return;
02576 Copy_To(op, tgt_BB);
02577 Delete(op);
02578 }
02579
02580 void
02581 PARTITION_GRAPH::Delete(OP* op)
02582 {
02583 TOP opcode = OP_code(op);
02584 INT index;
02585 PG_CONTAINER* node_set = (PG_CONTAINER*)OP_MAP_Get(_tn_node_map, op);
02586 if(Compare_Type(opcode) != -1)
02587 {
02588 PARTITION_GRAPH_NODE* p1_node = (*node_set)[0];
02589 PARTITION_GRAPH_NODE* p2_node = (*node_set)[1];
02590 TN* tn1 = OP_result(op, 0);
02591 TN* tn2 = OP_result(op, 1);
02592 p1_node->Del_Related_TN (tn1, op);
02593 if(BB_SET_EmptyP(p1_node->Get_BBs ())
02594 && p1_node->Get_TNs ().empty())
02595 {
02596 index = p1_node->Index ();
02597 Del_Relation(index);
02598 CXX_DELETE(p1_node, PRDB_pool);
02599 }
02600 p2_node->Del_Related_TN (tn2, op);
02601 if(BB_SET_EmptyP(p2_node->Get_BBs ())
02602 && p2_node->Get_TNs ().empty())
02603 {
02604 index = p2_node->Index ();
02605 Del_Relation(index);
02606 CXX_DELETE(p2_node, PRDB_pool);
02607 }
02608 }
02609 PARTITION_GRAPH_NODE* qp_node = (*node_set)[OP_results(op)];
02610 TN* qp = OP_opnd(op, OP_PREDICATE_OPND);
02611 qp_node->Del_Related_TN (qp, op);
02612 }
02613
02614 void
02615 PARTITION_GRAPH::Sum(TN_OP_PAIR* tp,TP_CONTAINER* tp_set)
02616 {
02617 TN* tn = tp->first;
02618 const OP* op = tp->second;
02619 PARTITION_GRAPH_NODE* node = Find_Node_In_OP(tp);
02620 TP_CONTAINER::iterator iter;
02621 for ( iter = tp_set->begin(); iter != tp_set->end(); iter++)
02622 {
02623 PARTITION_GRAPH_NODE* temp_nd = Find_Node_In_OP((*iter));
02624 if(_subset_relation[node->Index()][temp_nd->Index()]) return;
02625 if(_subset_relation[temp_nd->Index()][node->Index()])
02626 {
02627 iter = tp_set->erase(iter);
02628 iter = tp_set->insert(iter, tp);
02629 return;
02630 }
02631 if(Get_Lca(node, temp_nd)
02632 && Is_Complementary(node, temp_nd, Get_Lca(node, temp_nd)))
02633 {
02634 TN_OP_PAIR* ret_tp = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02635 if(Get_Lca(node, temp_nd)->Get_TNs().empty())
02636 ret_tp->first = True_TN;
02637 else ret_tp = (Get_Lca(node, temp_nd)->Get_TNs())[0];
02638 iter = tp_set->erase(iter);
02639 iter = tp_set->insert(iter, ret_tp);
02640 return;
02641 }
02642 }
02643 tp_set->push_back(tp);
02644 }
02645
02646 void
02647 PARTITION_GRAPH::Diff(TN_OP_PAIR tp,TP_CONTAINER* tp_set )
02648 {
02649 TN* tn = tp.first;
02650 PARTITION_GRAPH_NODE* node = Find_Node_In_OP(&tp);
02651 TP_CONTAINER::iterator iter;
02652 for ( iter = tp_set->begin(); iter != tp_set->end(); iter++)
02653 {
02654 if(tn == (*iter)->first)
02655 {
02656 iter = tp_set->erase(iter);
02657 break;
02658 }
02659 }
02660 for ( iter = tp_set->begin(); iter != tp_set->end(); iter++)
02661 {
02662 PARTITION_GRAPH_NODE* temp_nd =Find_Node_In_OP((*iter));
02663 if(_disjoint_relation[temp_nd->Index()][node->Index()]) continue;
02664 if(_subset_relation[node->Index()][temp_nd->Index()])
02665 {
02666 iter = tp_set->erase(iter);
02667 PG_CONTAINER* result;
02668 result->clear();
02669 result->push_back(temp_nd);
02670 if(Subtract(result, node))
02671 {
02672 PG_CONTAINER::iterator pg_iter;
02673 for(pg_iter=result->begin();pg_iter!=result->end();pg_iter++)
02674 {
02675 TN_OP_PAIR* ret_tp = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02676 if((*pg_iter)->Get_TNs().empty())
02677 ret_tp->first = True_TN;
02678 else ret_tp = (*pg_iter)->Get_TNs()[0];
02679 iter = tp_set->insert(iter, ret_tp);
02680 }
02681 }
02682 continue;
02683 }
02684 if(_subset_relation[temp_nd->Index()][node->Index()])
02685 {
02686 iter = tp_set->erase(iter);
02687 continue;
02688 }
02689 if(Get_Gcd(node, temp_nd))
02690 {
02691 iter = tp_set->erase(iter);
02692 PG_CONTAINER* result;
02693 result->clear();
02694 result->push_back(temp_nd);
02695 if(Subtract(result, Get_Gcd(node, temp_nd)))
02696 {
02697 PG_CONTAINER::iterator pg_iter;
02698 for(pg_iter=result->begin();pg_iter!=result->end();pg_iter++)
02699 {
02700 TN_OP_PAIR* ret_tp = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02701 if((*pg_iter)->Get_TNs().empty())
02702 ret_tp->first = True_TN;
02703 else ret_tp = (*pg_iter)->Get_TNs()[0];
02704 iter = tp_set->insert(iter, ret_tp);
02705 }
02706 }
02707 continue;
02708 }
02709 }
02710 }
02711
02712 void
02713 PARTITION_GRAPH::Lub_Diff(TN_OP_PAIR tp,TP_CONTAINER* tp_set )
02714 {
02715 Is_True(tp_set&&tp.first,("Illegal input with NULL value for Lub_Diff!"));
02716 Diff(tp, tp_set);
02717 Reduce(tp_set, TRUE);
02718 }
02719
02720 void
02721 PARTITION_GRAPH::Glb_Diff(TN_OP_PAIR tp,TP_CONTAINER* tp_set )
02722 {
02723 Is_True(tp_set&&tp.first,("Illegal input with NULL value for Glb_Diff!"));
02724 Diff(tp, tp_set);
02725 Reduce(tp_set, FALSE);
02726 }
02727
02728 void PARTITION_GRAPH::Lub_Sum(TN_OP_PAIR* tp, TP_CONTAINER* tp_set)
02729 {
02730 Is_True(tp_set&&tp->first,("Illegal input with NULL value for Lub_Sum!"));
02731 PARTITION_GRAPH_NODE* node = Find_Node_In_OP(tp);
02732 if(!node)
02733 {
02734 tp_set->clear();
02735 TN_OP_PAIR* ret_tp = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02736 ret_tp->first = True_TN;
02737 tp_set->push_back(ret_tp);
02738 return;
02739 }
02740 Sum(tp, tp_set);
02741 Reduce(tp_set, TRUE);
02742 }
02743
02744 void PARTITION_GRAPH::Glb_Sum(TN_OP_PAIR* tp, TP_CONTAINER* tp_set)
02745 {
02746 Is_True(tp_set&&tp->first,("Illegal input with NULL value for Glb_Sum!"));
02747 PARTITION_GRAPH_NODE* node = Find_Node_In_OP(tp);
02748 if(!node)
02749 {
02750 return;
02751 }
02752 Sum(tp, tp_set);
02753 Reduce(tp_set, FALSE);
02754 }
02755
02756
02757
02758 void PARTITION_GRAPH::Reduce(TP_CONTAINER* tp_set, BOOL is_dum)
02759 {
02760 Is_True(!tp_set->empty(), ("Empty tp_set can't be reduced!"));
02761 TP_CONTAINER::iterator iter1, iter2;
02762 BOOL has_dum = FALSE;
02763 PARTITION_GRAPH_NODE *node1, *node2;
02764 for(iter1 = tp_set->begin(); iter1 != tp_set->end(); )
02765 {
02766 node1 = Find_Node_In_OP((*iter1));
02767 Is_True(node1, ("No ptn_node for tp1!"));
02768 if(node1 == _dummy_node)
02769 {
02770 if(is_dum && !has_dum) has_dum = TRUE;
02771 else iter1 = tp_set->erase(iter1);
02772 continue;
02773 }
02774 for(iter2 = iter1++; iter2 != tp_set->end(); iter2++)
02775 {
02776 node2 = Find_Node_In_OP((*iter2));
02777 Is_True(node2, ("No ptn_node for tp2!"));
02778 if(node2 == _dummy_node)
02779 {
02780 if(is_dum && !has_dum) has_dum = TRUE;
02781 else iter2 = tp_set->erase(iter2);
02782 continue;
02783 }
02784 if(_subset_relation[node1->Index()][node2->Index()])
02785 {
02786 iter1 = tp_set->erase(iter1);
02787 }else if(_subset_relation[node2->Index()][node1->Index()])
02788 {
02789 iter2 = tp_set->erase(iter2);
02790 }else if(Get_Lca(node1, node2) &&
02791 Is_Complementary(node1, node2, Get_Lca(node1, node2)))
02792 {
02793 TN_OP_PAIR* ret_tp = CXX_NEW(TN_OP_PAIR, PRDB_pool);
02794 if(Get_Lca(node1,node2)->Get_TNs().empty())
02795 ret_tp->first = True_TN;
02796 else ret_tp = Get_Lca(node1,node2)->Get_TNs()[0];
02797 iter1 = tp_set->erase(iter1);
02798 iter2 = tp_set->erase(iter2);
02799 iter2 = tp_set->insert(iter2, ret_tp);
02800 }
02801 }
02802 }
02803 }
02804
02805
02806
02807 void PARTITION_GRAPH::Reduce(PG_CONTAINER* pg_set, BOOL is_dum)
02808 {
02809 Is_True(!pg_set->empty(), ("Empty pg_set can't be reduced!"));
02810 PG_CONTAINER::iterator iter1, iter2;
02811 BOOL has_dum = FALSE;
02812 PARTITION_GRAPH_NODE *node1, *node2;
02813 for(iter1 = pg_set->begin(); iter1 != pg_set->end(); )
02814 {
02815 if(*iter1 == _dummy_node)
02816 {
02817 if(is_dum && !has_dum) has_dum = TRUE;
02818 else iter1 = pg_set->erase(iter1);
02819 continue;
02820 }
02821 for(iter2 = iter1++; iter2 != pg_set->end(); )
02822 {
02823 if(node2 == _dummy_node)
02824 {
02825 if(is_dum && !has_dum) has_dum = TRUE;
02826 else iter2 = pg_set->erase(iter2);
02827 continue;
02828 }
02829 if(*iter1 == *iter2) {
02830 iter2 = pg_set->erase(iter2);
02831 continue;
02832 }
02833 iter2++;
02834 }
02835 }
02836 }
02837
02838
02839
02840
02841 PRDB_GEN::PRDB_GEN(REGION_TREE* region_tree)
02842 {
02843 const char* prev_phase = Get_Error_Phase();
02844 Set_Error_Phase("Ipfec predicate relation database");
02845 Start_Timer(T_Ipfec_PRDB_CU);
02846
02847 if (Get_Trace(TKIND_IR, TP_A_PRDB, REGION_First_BB))
02848 Trace_IR(TP_A_PRDB, "PRDB", NULL, FALSE);
02849
02850 PRDB_pool = &_m;
02851
02852 if(VT_Enable_Global_CFG) draw_global_cfg("right before region Edge_Split");
02853 for (INNERMOST_REGION_FIRST_ITER iter(region_tree);
02854 iter != 0;
02855 ++iter)
02856 {
02857 REGION* region = *iter;
02858 if(region->Region_Type() == IMPROPER ||
02859 region->Is_No_Further_Opt())
02860 continue;
02861 region -> Edge_Splitting();
02862 }
02863
02864 if(VT_Enable_Global_CFG) draw_global_cfg("Right after region Edge_splitt");
02865 Calculate_Dominators();
02866
02867 _region_graph = REGION_MAP_Create(region_tree->Seq_Num());
02868
02869 for (INNERMOST_REGION_FIRST_ITER iter(region_tree);
02870 iter != 0;
02871 ++iter)
02872 {
02873 REGION* region = *iter;
02874 if(region->Region_Type() == IMPROPER ||
02875 region->Is_No_Further_Opt())
02876 continue;
02877 if(Is_No_BB_Region(region)){
02878 DevWarn("A region doesn't have a bb node!");
02879 continue;
02880 }
02881
02882 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
02883 fprintf(TFile, " ===== region %d.\n", region -> Id());
02884
02885 REGIONAL_CFG_NODE *node = region->Entries()[0];
02886
02887 if(VT_Enable_Regional_CFG) draw_regional_cfg(region);
02888 PARTITION_GRAPH* graph = CXX_NEW(PARTITION_GRAPH(region), PRDB_pool);
02889 REGION_MAP_Set(_region_graph, region,graph);
02890
02891 if(VT_Enable_Partition_Graph)
02892 draw_partition_graph(graph);
02893 }
02894 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
02895 Print(TFile, region_tree);
02896
02897 Free_Dominators_Memory();
02898
02899 if (Get_Trace(TKIND_IR, TP_A_PRDB, REGION_First_BB))
02900 Trace_IR(TP_A_PRDB, "PRDB", NULL);
02901
02902 Stop_Timer(T_Ipfec_PRDB_CU);
02903
02904 Set_Error_Phase(prev_phase);
02905 }
02906
02907 PRDB_GEN::PRDB_GEN(REGION* region)
02908 {
02909 const char* prev_phase = Get_Error_Phase();
02910 Set_Error_Phase("Ipfec predicate relation database");
02911 Start_Timer(T_Ipfec_PRDB_CU);
02912 Is_True(!(region->Region_Type() == IMPROPER ||
02913 region->Is_No_Further_Opt()), ("unexpected region!"));
02914
02915 if (Get_Trace(TKIND_IR, TP_A_PRDB, REGION_First_BB))
02916 Trace_IR(TP_A_PRDB, "PRDB", NULL, FALSE);
02917
02918 PRDB_pool = &_m;
02919
02920 region->Edge_Splitting();
02921 Calculate_Dominators();
02922
02923 _region_graph = REGION_MAP_Create(1);
02924 if (Get_Trace(TP_A_PRDB, TT_PRDB_VERBOSE))
02925 fprintf(TFile, " ===== region %d.\n", region -> Id());
02926 Is_True(!Is_No_BB_Region(region), ("A region doesn't have a bb node!"));
02927
02928 if(VT_Enable_Regional_CFG) draw_regional_cfg(region);
02929 PARTITION_GRAPH* graph = CXX_NEW(PARTITION_GRAPH(region), PRDB_pool);
02930 REGION_MAP_Set(_region_graph, region,graph);
02931
02932 if(VT_Enable_Partition_Graph)
02933 draw_partition_graph(graph);
02934 Free_Dominators_Memory();
02935
02936 if (Get_Trace(TKIND_IR, TP_A_PRDB, REGION_First_BB))
02937 Trace_IR(TP_A_PRDB, "PRDB", NULL);
02938
02939 Stop_Timer(T_Ipfec_PRDB_CU);
02940
02941 Set_Error_Phase(prev_phase);
02942 }
02943
02944 PARTITION_GRAPH*
02945 PRDB_GEN::Partition_Graph(REGION* region)
02946 {
02947 Is_True(!Is_No_BB_Region(region), ("A region doesn't have a bb node!"));
02948 Is_True(!(region->Region_Type() == IMPROPER ||
02949 region->Is_No_Further_Opt()), ("unexpected region!"));
02950 return((PARTITION_GRAPH*)REGION_MAP_Get(_region_graph, region));
02951 }
02952
02953 inline PRDB_GEN* Generate_PRDB(REGION_TREE* region_tree)
02954 {
02955 return CXX_NEW(PRDB_GEN(region_tree), &MEM_pu_pool);
02956 }
02957
02958 inline PRDB_GEN* Generate_PRDB(REGION* region)
02959 {
02960 return CXX_NEW(PRDB_GEN(region), &MEM_pu_pool);
02961 }
02962
02963 void Delete_PRDB()
02964 {
02965 if(prdb){
02966 CXX_DELETE(prdb, &MEM_pu_pool);
02967 prdb = NULL;
02968 }
02969 }
02970
02971 PRDB_GEN* PRDB_Init(REGION_TREE* rgn_tree)
02972 {
02973 Delete_PRDB();
02974 return prdb = Generate_PRDB(rgn_tree);
02975 }
02976
02977 PRDB_GEN* PRDB_Init(REGION* region)
02978 {
02979 Delete_PRDB();
02980 return prdb = Generate_PRDB(region);
02981 }
02982
02983 PRDB_GEN* Get_PRDB()
02984 {
02985 return prdb;
02986
02987 }
02988
02989 BOOL PRDB_Valid()
02990 {
02991 return prdb != NULL;
02992 }
02993
02994 void
02995 PARTITION::Print(FILE* file)
02996 {
02997 fprintf(file, " === partition ===\n");
02998 fprintf(file, " = its parent is : %d \n", _parent -> Index());
02999 fprintf(file, " = its children are :");
03000 PG_CONTAINER::iterator iter;
03001 for (iter = _child.begin(); iter != _child.end(); iter++)
03002 {
03003 fprintf(file," %d ,", (*iter) -> Index());
03004 }
03005 fprintf(file, "\n");
03006 }
03007 void
03008 PARTITION_GRAPH_NODE::Print(FILE* file)
03009 {
03010 fprintf(file, " PARTITION GRAPH NODE : %d \n", _index);
03011 fprintf(file, " = its level is %d \n", _level);
03012
03013 fprintf(file, " = its related tns :");
03014 TP_CONTAINER::iterator iter;
03015 for (iter = _related_tns.begin();
03016 iter != _related_tns.end();
03017 iter++)
03018 {
03019 fPrint_TN(file, " %s,", (*iter)->first);
03020 }
03021 fprintf(file, "\n");
03022
03023 fprintf(file," = its related bbs:");
03024 BB* bb;
03025 FOR_ALL_BB_SET_members( _related_bbs, bb){
03026 fprintf(file," %d,", BB_id(bb));
03027 }
03028 fprintf(file, "\n");
03029
03030 fprintf(file," = its predecessor :");
03031 PT_CONTAINER:: iterator iter1;
03032 for (iter1 = _child_partitions.begin();
03033 iter1 != _child_partitions.end();
03034 iter1++)
03035 {
03036 fprintf(file, " %d,",(*iter1) -> Parent() -> Index());
03037 }
03038 fprintf(file, "\n");
03039
03040 fprintf(file," = its successor :");
03041 for (iter1 = _parent_partitions.begin();
03042 iter1 != _parent_partitions.end();
03043 iter1++)
03044 {
03045 PARTITION *par = *iter1;
03046 PG_CONTAINER::iterator iter2;
03047 for (iter2 = par -> Child().begin();
03048 iter2 != par -> Child().end();
03049 iter2++)
03050 {
03051 fprintf(file, " %d,",(*iter2) -> Index());
03052 }
03053 }
03054 fprintf(file, "\n");
03055
03056 }
03057
03058
03059 void
03060 PARTITION_GRAPH::Print(FILE* file)
03061 {
03062 fprintf(file, "======== included nodes of the graph\n");
03063 PG_CONTAINER::iterator iter;
03064 for ( iter = _nodes.begin(); iter != _nodes.end(); iter++){
03065 (*iter)-> Print(file);
03066 }
03067
03068 fprintf(file, "======== the root node is %d\n", _root -> Index());
03069 fprintf(file, "======== the dummy node is %d\n", _dummy_node -> Index());
03070
03071 }
03072
03073 void
03074 PRDB_GEN::Print(FILE* file, REGION_TREE* region_tree)
03075 {
03076 for (INNERMOST_REGION_FIRST_ITER iter(region_tree);
03077 iter != 0;
03078 ++iter)
03079 {
03080 REGION* region = *iter;
03081 if(region->Region_Type() == IMPROPER ||
03082 region->Is_No_Further_Opt())
03083 {
03084 continue;
03085 }
03086 if(Is_No_BB_Region(region)){
03087 DevWarn("A region doesn't have a bb node!");
03088 continue;
03089 }
03090
03091 PARTITION_GRAPH* graph =(PARTITION_GRAPH*)
03092 REGION_MAP_Get(_region_graph, region);
03093 graph -> Print(file);
03094
03095 }
03096 }
03097
03098
