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 #ifdef USE_PCH
00048 #include "opt_pch.h"
00049 #endif // USE_PCH
00050 #pragma hdrstop
00051
00052
00053 #include "id_map.h"
00054
00055 #include "opt_etable.h"
00056 #include "opt_vertab.h"
00057 #include "opt_htable.h"
00058 #include "opt_ssa.h"
00059 #include "opt_mu_chi.h"
00060 #include "opt_fold.h"
00061 #include "tracing.h"
00062
00063 #include "opt_config.h"
00064
00065
00066 void
00067 EXP_WORKLST::SPRE_Determine_inserts_saves_deletions(CODEMAP *htable,
00068 ETABLE *etable,
00069 E_VER_TAB *e_ver_tab)
00070 {
00071
00072
00073
00074
00075 EXP_ALL_OCCURS_ITER occ_iter(Real_occurs().Head(),
00076 NULL,
00077 Phi_occurs().Head(),
00078 Phi_pred_occurs().Head(),
00079 NULL);
00080 EXP_OCCURS *occ;
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091 FOR_ALL_NODE(occ, occ_iter, Init()) {
00092 switch (occ->Occ_kind()) {
00093 case EXP_OCCURS::OCC_PHI_OCCUR:
00094 if (occ->Exp_phi()->Will_b_avail()) {
00095
00096
00097
00098 Is_True(e_ver_tab->Avail_def(occ->E_version()) == NULL,
00099 ("SPRE: e-version %d already has an available definition",
00100 occ->E_version()));
00101 e_ver_tab->Set_avail_def(occ->E_version(), occ);
00102 }
00103 else {
00104
00105
00106 }
00107 break;
00108 case EXP_OCCURS::OCC_REAL_OCCUR:
00109 {
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126 EXP_OCCURS *def = e_ver_tab->Avail_def(occ->E_version());
00127
00128 if (def == NULL || !def->Bb()->Postdominates(occ->Bb())) {
00129
00130
00131
00132
00133
00134
00135
00136 e_ver_tab->Set_real_avail_def(occ->E_version(), occ);
00137 occ->Set_def_occur(NULL);
00138 }
00139 else {
00140
00141
00142
00143
00144
00145 Is_True(def->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR ||
00146 (def->Occ_kind() == EXP_OCCURS::OCC_REAL_OCCUR &&
00147 e_ver_tab->Occ_count(occ->E_version()) >= 1),
00148 ("SPRE: Inconsistent occurrence count for e-version %d",
00149 occ->E_version()));
00150
00151
00152
00153
00154 Is_Trace(etable->Tracing(),
00155 (TFile, "SPRE: delete one operand at BB%d\n", occ->Bb()->Id()));
00156 occ->Set_delete_comp();
00157 occ->Set_def_occur(def);
00158 e_ver_tab->Note_version_use(occ->E_version(), 1);
00159 }
00160 }
00161 break;
00162 case EXP_OCCURS::OCC_PHI_PRED_OCCUR:
00163 {
00164
00165
00166
00167
00168
00169
00170
00171 BB_LIST_ITER pred_bb_iter;
00172 BB_NODE *pred_bb;
00173 BB_NODE *occ_bb = occ->Bb();
00174 #if Is_True_On
00175 BOOL found_phi = FALSE;
00176 #endif
00177 FOR_ALL_ELEM(pred_bb, pred_bb_iter, Init(occ_bb->Pred())) {
00178 EXP_PHI *phi = etable->Lookup_exp_phi(pred_bb, Exp());
00179
00180 if (phi != NULL) {
00181 Is_True(phi->Bb() == pred_bb,
00182 ("EXP_WORKLST::SPRE_Determine_inserts_saves_deletions: "
00183 "ETABLE::Lookup_exp_phi failed"));
00184
00185
00186 #if Is_True_On
00187 found_phi = TRUE;
00188 #endif
00189 if (phi->Will_b_avail()) {
00190
00191
00192
00193 const INT32 opnd_num = pred_bb->Succ()->Pos(occ_bb);
00194 const EXP_OCCURS *const opnd = phi->Opnd(opnd_num);
00195
00196 Is_True(phi->Succ(opnd_num) == occ,
00197 ("EXP_WORKLST::SPRE_Determine_inserts_saves_deletions: "
00198 "phi->Succ() / phi-pred inconsistency"));
00199
00200 if (phi->Need_insertion(opnd_num)) {
00201
00202 occ->Set_inserted();
00203
00204
00205
00206 Is_Trace(etable->Tracing(),
00207 (TFile, "SPRE: insert one operand at BB%d\n", occ_bb->Id()));
00208 }
00209 else {
00210
00211
00212
00213
00214
00215
00216
00217 e_ver_tab->Note_version_use(opnd->E_version());
00218 phi->Set_opnd(opnd_num,
00219 e_ver_tab->Avail_def(opnd->E_version()));
00220 }
00221 }
00222 }
00223 }
00224 Is_True(found_phi,
00225 ("EXP_WORKLST::SPR_Determine_inserts_saves_deletions: "
00226 "phi-pred must have successor phi"));
00227 }
00228 break;
00229 default:
00230 FmtAssert(FALSE, ("EXP_WORKLST::SPRE_Determine_inserts_saves_deletions: "
00231 "Bad occurrence kind"));
00232 }
00233 }
00234 }
00235
00236
00237
00238 void
00239 EXP_WORKLST::SPRE_compute_insert_delete(
00240 CODEMAP *htable,
00241
00242
00243 ETABLE *etable)
00244 {
00245
00246 OPT_POOL_Push(etable->Etable_local_pool(), SPRE_DUMP_FLAG+1);
00247
00248 E_VER_TAB *e_ver_tab =
00249 CXX_NEW(E_VER_TAB(etable->Etable_local_pool(),
00250 Cur_e_version(),
00251 etable->Tracing()),
00252 etable->Etable_local_pool());
00253
00254 SPRE_Determine_inserts_saves_deletions(htable, etable, e_ver_tab);
00255
00256 Is_Trace(etable->Tracing(),
00257 (TFile, "==== After EXP_WORKLST::SPRE_Determine_inserts_saves_deletions\n"));
00258 Is_Trace_cmd(etable->Tracing(), Print(TFile));
00259
00260 CXX_DELETE(e_ver_tab, etable->Etable_local_pool());
00261
00262 OPT_POOL_Pop(etable->Etable_local_pool(), SPRE_DUMP_FLAG+1);
00263 }
00264
00265
00266
00267
00268 CODEREP *
00269 ETABLE::SPRE_rename_var(CODEREP *cr, BOOL allow_zero_ver)
00270 {
00271 if (cr->Is_var_volatile())
00272 return NULL;
00273
00274 AUX_ID auxid = cr->Aux_id();
00275 if (Opt_stab()->NULL_coderep(auxid)) {
00276
00277 Is_Trace(Tracing(),
00278 (TFile, "SPRE_rename_ver: pushing zero version cr onto stack for auxid %d.\n", auxid));
00279 CODEREP *zcr = Htable()->Ssa()->Get_zero_version_CR(auxid, Opt_stab(), 0);
00280 Opt_stab()->Push_coderep(auxid, zcr);
00281 }
00282
00283 CODEREP *top = Opt_stab()->Top_coderep(auxid);
00284
00285 Is_True(top != NULL, ("ETABLE::SPRE_rename_var: stack top is null."));
00286
00287 #ifdef Is_True_On
00288 if (!allow_zero_ver) {
00289 Is_True(!top->Is_flag_set(CF_IS_ZERO_VERSION),
00290 ("ETABLE::SPRE_rename_var: sym%dv%d(cr%d) is zero ver.",
00291 top->Aux_id(), top->Version(), top->Coderep_id()));
00292 }
00293 #endif
00294
00295 return (top != cr) ? top : NULL;
00296 }
00297
00298
00299 CODEREP *
00300 ETABLE::SPRE_rename_expr(CODEREP *cr, BB_NODE *bb)
00301 {
00302 switch (cr->Kind()) {
00303 case CK_LDA:
00304 case CK_CONST:
00305 case CK_RCONST:
00306 return NULL;
00307
00308 case CK_VAR:
00309 return SPRE_rename_var(cr, FALSE);
00310
00311 case CK_IVAR:
00312 {
00313 CODEREP *newcr = Alloc_stack_cr(cr->Extra_ptrs_used());
00314 MU_NODE *mnode = cr->Ivar_mu_node();
00315 CODEREP *m_cr = NULL;
00316 CODEREP *ilod_base = NULL;
00317 CODEREP *mload_size = NULL;
00318 CODEREP *iloadx_index = NULL;
00319
00320 if (mnode) {
00321 if (cr->Ivar_defstmt() &&
00322 OPERATOR_is_scalar_istore (cr->Ivar_defstmt()->Opr()) &&
00323 cr->Ivar_defstmt()->Lhs() == cr) {
00324
00325
00326
00327 } else {
00328 m_cr = SPRE_rename_var(mnode->OPND(), TRUE);
00329 #ifdef KEY // bug 11739
00330 if (m_cr && m_cr->Is_flag_set(CF_IS_ZERO_VERSION))
00331 m_cr = NULL;
00332 #endif
00333 }
00334 }
00335
00336 ilod_base = SPRE_rename_expr(cr->Ilod_base(), bb);
00337
00338 if (cr->Opr() == OPR_MLOAD)
00339 mload_size = SPRE_rename_expr(cr->Mload_size(), bb);
00340 else if (cr->Opr() == OPR_ILOADX)
00341 iloadx_index = SPRE_rename_expr(cr->Index(), bb);
00342
00343 if (m_cr || ilod_base || mload_size || iloadx_index) {
00344 newcr->Copy(*cr);
00345 if (m_cr) {
00346
00347
00348
00349 MU_NODE *mnode = (MU_NODE*) CXX_NEW(MU_NODE, Htable()->Mem_pool());
00350 mnode->Clone(cr->Ivar_mu_node());
00351 newcr->Set_ivar_mu_node(mnode);
00352 mnode->Set_OPND(m_cr);
00353 }
00354 if (ilod_base)
00355 newcr->Set_ilod_base(ilod_base);
00356 newcr->Set_istr_base(NULL);
00357 newcr->Set_usecnt(0);
00358 if (mload_size)
00359 newcr->Set_mload_size(mload_size);
00360 if (iloadx_index)
00361 newcr->Set_index(iloadx_index);
00362 newcr->Set_ivar_occ(cr->Ivar_occ());
00363 cr->DecUsecnt();
00364 return Htable()->Rehash(newcr);
00365 }
00366 return NULL;
00367 }
00368
00369 case CK_OP:
00370 {
00371 CODEREP *newcr = Alloc_stack_cr(cr->Extra_ptrs_used());
00372 newcr->Copy(*cr);
00373 BOOL need_rehash = FALSE;
00374 newcr->Set_usecnt(0);
00375
00376 for (INT32 i = 0; i < cr->Kid_count(); i++) {
00377 CODEREP *expr = SPRE_rename_expr(cr->Opnd(i), bb);
00378 if (expr) {
00379 need_rehash = TRUE;
00380 newcr->Set_opnd(i, expr);
00381 }
00382 }
00383
00384 if (need_rehash)
00385 return Htable()->Rehash(newcr);
00386 return NULL;
00387 }
00388
00389 default:
00390 Is_True(FALSE, ("ETABLE::SPRE_rename_expr: unexpected CK_KIND."));
00391 return NULL;
00392 }
00393 }
00394
00395
00396 void
00397 ETABLE::SPRE_rename_stmt(STMTREP *stmt, BB_NODE *bb)
00398 {
00399 CODEREP *newcr;
00400
00401 if (stmt->Rhs()) {
00402 newcr = SPRE_rename_expr(stmt->Rhs(), bb);
00403 if (newcr)
00404 stmt->Set_rhs(newcr);
00405 }
00406 switch (stmt->Opr()) {
00407 case OPR_ISTORE:
00408 case OPR_ISTBITS:
00409 newcr = SPRE_rename_expr(stmt->Lhs()->Istr_base(), bb);
00410 if (newcr)
00411 stmt->Lhs()->Set_istr_base(newcr);
00412 break;
00413 case OPR_MSTORE:
00414 {
00415 newcr = SPRE_rename_expr(stmt->Lhs()->Istr_base(), bb);
00416 if (newcr)
00417 stmt->Lhs()->Set_istr_base(newcr);
00418
00419 CODEREP *num_bytes = (CODEREP *)stmt->Lhs()->Mstore_size();
00420 newcr = SPRE_rename_expr(num_bytes, bb);
00421 if (newcr)
00422 stmt->Lhs()->Set_mstore_size(newcr);
00423 break;
00424 }
00425 default: ;
00426 }
00427 }
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438 BOOL
00439 ETABLE::RHS_is_fully_avail(CODEREP *lhs, CODEREP *rhs)
00440 {
00441 if (lhs->Is_flag_set(CF_IS_ZERO_VERSION) ||
00442 rhs->Is_flag_set(CF_IS_ZERO_VERSION))
00443 return FALSE;
00444
00445 if (lhs->Is_flag_set(CF_DEF_BY_CHI)) {
00446 return FALSE;
00447
00448 } else if (lhs->Is_flag_set(CF_DEF_BY_PHI)) {
00449 PHI_NODE *phi = lhs->Defphi();
00450 if (phi->Visited())
00451 return FALSE;
00452
00453 PHI_NODE *rhs_phi = Lookup_var_phi(phi->Bb(), rhs->Aux_id());
00454 PHI_OPND_ITER phi_opnd_iter(phi);
00455
00456 phi->Set_visited();
00457 if (rhs_phi == NULL) {
00458 CODEREP *opnd;
00459 FOR_ALL_ELEM(opnd, phi_opnd_iter, Init()) {
00460 if (!RHS_is_fully_avail(opnd, rhs))
00461 return FALSE;
00462 }
00463 } else {
00464 if (rhs_phi->RESULT() != rhs)
00465 return FALSE;
00466 INT i = 0;
00467 CODEREP *opnd;
00468 FOR_ALL_ELEM(opnd, phi_opnd_iter, Init()) {
00469 if (!RHS_is_fully_avail(opnd, rhs_phi->OPND(i++)))
00470 return FALSE;
00471 }
00472 }
00473 phi->Reset_visited();
00474 return TRUE;
00475 } else {
00476 return lhs->Defstmt()->Rhs() == rhs;
00477 }
00478 }
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489 BOOL
00490 ETABLE::Stmt_is_redundant(STMTREP *stmt)
00491 {
00492 Is_True(stmt->Live_stmt(), ("ETABLE::Delete_redundant_stmt: stmt already dead."));
00493
00494
00495 if (! OPERATOR_is_scalar_store (stmt->Opr()))
00496 return FALSE;
00497
00498 AUX_ID aux = stmt->Lhs()->Aux_id();
00499
00500
00501 if (Opt_stab()->NULL_coderep(aux))
00502 return FALSE;
00503
00504
00505
00506
00507
00508 CODEREP *top = Opt_stab()->Top_coderep(aux);
00509 if (top->Is_flag_set(CF_IS_ZERO_VERSION))
00510 return FALSE;
00511 if (top->Defbb() != stmt->Bb()) {
00512 Warn_todo("ETABLE::Stmt_is_redundant: need dead phi for SPRE vars.");
00513 return FALSE;
00514 }
00515
00516
00517 if (ST_sclass(Opt_stab()->Aux_stab_entry(aux)->St()) != SCLASS_REG)
00518 return FALSE;
00519
00520
00521
00522
00523
00524
00525
00526 if (stmt->Rhs()->Kind() != CK_VAR)
00527 return FALSE;
00528
00529
00530 if (Opt_stab()->Aux_stab_entry(aux)->Is_dedicated_preg() ||
00531 Opt_stab()->Aux_stab_entry(stmt->Rhs()->Aux_id())->Is_dedicated_preg())
00532 return FALSE;
00533
00534 return RHS_is_fully_avail(Opt_stab()->Top_coderep(aux), stmt->Rhs());
00535 }
00536
00537
00538
00539
00540
00541 void
00542 ETABLE::SPRE_rename(BB_NODE *bb)
00543 {
00544 CODEREP *cr;
00545 PHI_NODE *phi;
00546 PHI_LIST_ITER phi_iter;
00547
00548 if (bb->Kind() == BB_ENTRY && bb != Cfg()->Fake_entry_bb()) {
00549 STMTREP *entry_chi = bb->Stmtlist()->Head();
00550 Is_True(entry_chi->Opr() == OPR_OPT_CHI, ("cannot find entry chi."));
00551 Set_entry_chi(entry_chi);
00552 }
00553
00554
00555 FOR_ALL_ELEM (phi, phi_iter, Init(bb->Phi_list())) {
00556 if (phi->Live())
00557 Opt_stab()->Push_coderep(phi->Aux_id(), phi->RESULT());
00558 else {
00559 CODEREP *zcr = Htable()->Ssa()->Get_zero_version_CR(phi->Aux_id(), Opt_stab(), 0);
00560 Opt_stab()->Push_coderep(phi->Aux_id(), zcr);
00561 }
00562 }
00563
00564 BOOL some_stmt_deleted = FALSE;
00565
00566 STMTREP_ITER stmt_iter(bb->Stmtlist());
00567 STMTREP *stmt;
00568 FOR_ALL_NODE(stmt, stmt_iter, Init()) {
00569
00570 SPRE_rename_stmt(stmt, bb);
00571
00572
00573
00574 if (Stmt_is_redundant(stmt)) {
00575 some_stmt_deleted = TRUE;
00576 stmt->Reset_live_stmt();
00577 if (Tracing()) {
00578 fprintf(TFile, "SPRE_rename: found a redundant statement.");
00579 Htable()->Print_SR(stmt, TFile);
00580 }
00581 continue;
00582 }
00583
00584 if (OPERATOR_is_scalar_store (stmt->Opr())) {
00585 CODEREP *lhs = stmt->Lhs();
00586 Opt_stab()->Push_coderep(lhs->Aux_id(), lhs);
00587 }
00588
00589 if (stmt->Has_mu()) {
00590 MU_LIST_ITER mu_iter;
00591 MU_NODE *mnode;
00592 FOR_ALL_NODE( mnode, mu_iter, Init(stmt->Mu_list())) {
00593 cr = SPRE_rename_var(mnode->OPND(), TRUE);
00594 if (cr)
00595 mnode->Set_OPND(cr);
00596 }
00597 }
00598 if (stmt->Has_chi()) {
00599 CHI_LIST_ITER chi_iter;
00600 CHI_NODE *cnode;
00601 CHI_LIST *chi_list = stmt->Chi_list();
00602 if (stmt->Opr() == OPR_OPT_CHI) {
00603 FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00604 if (!cnode->Dse_dead())
00605 Opt_stab()->Push_coderep(cnode->Aux_id(), cnode->RESULT());
00606 else {
00607 CODEREP *zcr = Htable()->Ssa()->Get_zero_version_CR(cnode->Aux_id(), Opt_stab(), 0);
00608 Opt_stab()->Push_coderep(cnode->Aux_id(), zcr);
00609 }
00610 }
00611 } else {
00612 FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00613 if (cnode->Live()) {
00614 cr = SPRE_rename_var(cnode->OPND(), TRUE);
00615 if (cr)
00616 cnode->Set_OPND(cr);
00617 Opt_stab()->Push_coderep(cnode->Aux_id(), cnode->RESULT());
00618 }
00619 }
00620 }
00621 }
00622 }
00623
00624 if (some_stmt_deleted) {
00625 STMTREP *nextstmt;
00626 for ( stmt = bb->First_stmtrep(), nextstmt = NULL;
00627 stmt != NULL;
00628 stmt = nextstmt ) {
00629 nextstmt = stmt->Next();
00630 if ( ! stmt->Live_stmt() ) {
00631 if (Tracing()) {
00632 fprintf(TFile, "SPRE_rename: remove a redundant statement.");
00633 }
00634 bb->Remove_stmtrep(stmt);
00635 }
00636 }
00637 }
00638
00639 BB_NODE *succ; BB_LIST_ITER bb_iter;
00640 FOR_ALL_ELEM (succ, bb_iter, Init(bb->Succ())) {
00641 INT32 pos = succ->Pred()->Pos(bb);
00642 FOR_ALL_ELEM (phi, phi_iter, Init(succ->Phi_list())) {
00643 if (phi->Live()) {
00644 cr = SPRE_rename_var(phi->OPND(pos), TRUE);
00645 if (cr) {
00646 phi->Set_opnd(pos, cr);
00647 }
00648 }
00649 }
00650 }
00651
00652
00653 BB_NODE *dom_bb;
00654 BB_LIST_ITER dom_bb_iter;
00655 FOR_ALL_ELEM(dom_bb, dom_bb_iter, Init(bb->Dom_bbs()))
00656 SPRE_rename(dom_bb);
00657
00658
00659 FOR_ALL_NODE_REVERSE(stmt, stmt_iter, Init()) {
00660 if (stmt->Has_chi()) {
00661 CHI_LIST_ITER chi_iter;
00662 CHI_NODE *cnode;
00663 CHI_LIST *chi_list = stmt->Chi_list();
00664 if (stmt->Opr() == OPR_OPT_CHI) {
00665 FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00666 Opt_stab()->Pop_coderep(cnode->Aux_id());
00667 }
00668 } else {
00669 FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00670 if (cnode->Live())
00671 Opt_stab()->Pop_coderep(cnode->Aux_id());
00672 }
00673 }
00674 }
00675 if (OPERATOR_is_scalar_store (stmt->Opr()))
00676 Opt_stab()->Pop_coderep(stmt->Lhs()->Aux_id());
00677 }
00678
00679 FOR_ALL_ELEM (phi, phi_iter, Init(bb->Phi_list())) {
00680 Opt_stab()->Pop_coderep(phi->Aux_id());
00681 }
00682 }
00683
00684
00685 void
00686 ETABLE::SPRE_update_ssa(void)
00687 {
00688 OPT_POOL_Push(Etable_local_pool(), SPRE_DUMP_FLAG+2);
00689 Opt_stab()->New_coderep(Etable_local_pool());
00690 Opt_stab()->Clear_coderep();
00691 SPRE_rename(Cfg()->Entry_bb());
00692 OPT_POOL_Pop(Etable_local_pool(), SPRE_DUMP_FLAG+2);
00693 }