Open64: osprey/be/opt/opt_rename.cxx Source File

00001 //-*-c++-*-
00002 
00003 /*
00004  * Copyright 2002, 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00005  */
00006 
00007 // ====================================================================
00008 // ====================================================================
00009 //
00010 // Module: opt_rename.cxx
00011 // $Revision: 1.1.1.1 $
00012 // $Date: 2005/10/21 19:00:00 $
00013 // $Author: marcel $
00014 // $Source: /proj/osprey/CVS/open64/osprey1.0/be/opt/opt_rename.cxx,v $
00015 //
00016 // ====================================================================
00017 //
00018 // Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.
00019 //
00020 // This program is free software; you can redistribute it and/or modify
00021 // it under the terms of version 2 of the GNU General Public License as
00022 // published by the Free Software Foundation.
00023 //
00024 // This program is distributed in the hope that it would be useful, but
00025 // WITHOUT ANY WARRANTY; without even the implied warranty of
00026 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00027 //
00028 // Further, this software is distributed without any warranty that it
00029 // is free of the rightful claim of any third person regarding
00030 // infringement  or the like.  Any license provided herein, whether
00031 // implied or otherwise, applies only to this software file.  Patent
00032 // licenses, if any, provided herein do not apply to combinations of
00033 // this program with other software, or any other product whatsoever.
00034 //
00035 // You should have received a copy of the GNU General Public License
00036 // along with this program; if not, write the Free Software Foundation,
00037 // Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, USA.
00038 //
00039 // Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
00040 // Mountain View, CA 94043, or:
00041 //
00042 // http://www.sgi.com
00043 //
00044 // For further information regarding this notice, see:
00045 //
00046 // http://oss.sgi.com/projects/GenInfo/NoticeExplan
00047 //
00048 // ====================================================================
00049 // ====================================================================
00050 
00051 
00052 #ifdef USE_PCH
00053 #include "opt_pch.h"
00054 #endif // USE_PCH
00055 #pragma hdrstop
00056 
00057 
00058 #include "opt_transform.h"
00059 #include "bb_node_set.h"
00060 
00061 #ifdef Is_True_On
00062 static int transform_stop_bb;
00063 static int transform_stop_stmt;
00064 void set_transform_stop_at(int bb_id, int stmt_id) 
00065 {
00066   transform_stop_bb = bb_id;
00067   transform_stop_stmt = stmt_id;
00068 }
00069 
00070 void transform_stopped()
00071 {
00072   printf("transform stopped at bb%d stmt%d\n", transform_stop_bb, transform_stop_stmt);
00073 }
00074 
00075 void check_transform_stop_at(int bb_id, int stmt_id)
00076 {
00077   if (bb_id == transform_stop_bb &&
00078       stmt_id == transform_stop_stmt) {
00079     transform_stopped();
00080   }
00081 }
00082 #endif
00083 
00084 //  Insert_var_phi
00085 //   -- mark required phi function visited and introduce new phi functions
00086 //  
00087 static void
00088 Insert_var_phi(CODEREP *lhs, BB_NODE *bb, COMP_UNIT *cu, BOOL trace)
00089 {
00090   AUX_ID aux = lhs->Aux_id();
00091   BB_NODE_SET_ITER    df_iter;
00092   BB_NODE *bb_phi;
00093   CODEMAP *htable = cu->Htable();
00094 
00095   FOR_ALL_ELEM (bb_phi, df_iter, Init(bb->Dom_frontier())) {
00096     PHI_NODE *phi = htable->Lookup_var_phi(bb_phi, aux);
00097 
00098     if (phi == NULL) {
00099       phi = bb_phi->Phi_list()->New_phi_node(aux, cu->Ssa()->Mem_pool(), bb_phi);
00100       
00101       // Enter into the var phi hash table.
00102       htable->Enter_var_phi_hash(phi);
00103 
00104       CODEREP *phi_res = htable->Add_def(aux, -1, 
00105            NULL, lhs->Dtyp(), lhs->Dsctyp(),
00106            lhs->Offset(), lhs->Lod_ty(),
00107            lhs->Field_id(), TRUE);
00108       phi_res->Set_flag(CF_DEF_BY_PHI);
00109       phi_res->Set_defphi(phi);
00110       phi->Set_live();
00111       phi->Set_result(phi_res);
00112       phi->Set_visited();
00113 
00114       Is_Trace(trace,
00115          (TFile, "SSA RENAME: insert new phi at BB%d for sym%d\n", bb->Id(),
00116     aux));
00117       
00118       // Put zero versions at the phi opnds.
00119       CODEREP *zcr = cu->Ssa()->Get_zero_version_CR(aux, cu->Opt_stab(), 0);
00120       BB_NODE *pred;
00121       BB_LIST_ITER bb_iter;
00122       INT opnd = 0;
00123       FOR_ALL_ELEM (pred, bb_iter, Init(bb_phi->Pred())) {
00124   phi->Set_opnd(opnd, zcr);
00125   opnd++;
00126       }
00127       
00128       // Recursively introduce phi nodes
00129       Insert_var_phi(lhs, bb_phi, cu, trace);
00130 
00131     } else if (!phi->Visited()) {
00132 
00133       phi->Set_visited(); 
00134 
00135       // Recursively introduce phi nodes
00136       Insert_var_phi(lhs, bb_phi, cu, trace);
00137     }
00138   }
00139 }
00140 
00141 
00142 static void
00143 delete_var_phi(PHI_NODE *phi, CODEMAP *htable, BOOL trace)
00144 {
00145   Is_Trace(trace,
00146      (TFile, "SSA RENAME: remove phi at BB%d for sym%d\n", phi->Bb()->Id(),
00147       phi->Aux_id()));
00148   
00149   // This phi function will be removed, the use of the phi result
00150   // will becomes one of its operands.   And the operand must not
00151   // be a zero-cr if the phi result isn't a zero version.
00152   if (phi->Live() &&
00153       !phi->RESULT()->Is_flag_set(CF_IS_ZERO_VERSION)) {
00154     for ( INT pkid = 0; pkid < phi->Size(); pkid++ ) {
00155       if (phi->OPND(pkid)->Is_flag_set(CF_IS_ZERO_VERSION)) {
00156   htable->Fix_zero_version(phi, pkid, true /*allow_real_def*/);
00157       }
00158       phi->OPND(pkid)->Reset_flag(CF_DONT_PROP);
00159     }
00160   }
00161   htable->Remove_var_phi_hash(phi);
00162 }
00163 
00164 
00165 //  Insert_delete_phi
00166 //   1. delete phi functions from BB that has a different number of predecessors
00167 //   2. mark all phi functions not visited
00168 //   3. insert new phi functions and mark required old phi visited
00169 //   4. delete phi that are not visited
00170 //      if the deleted phi has zero version, change the opnd to be
00171 //      non-zero versions.
00172 //
00173 static void
00174 Insert_delete_phi(COMP_UNIT *cu, BOOL trace)
00175 {
00176   BB_NODE *bb;
00177   CFG *cfg = cu->Cfg();
00178   CODEMAP *htable = cu->Htable();
00179   CFG_ITER cfg_iter;
00180 
00181   // Delete phi from BB that has a different number of pred.  For those
00182   // not deleted, mark them not visited
00183   FOR_ALL_ELEM (bb, cfg_iter, Init(cfg)) {
00184     PHI_NODE *phi; 
00185     PHI_LIST_ITER phi_iter;
00186     if (bb->Phi_list() != NULL) {
00187       if (bb->Phi_list()->In_degree() != bb->Pred()->Len()) {
00188   if (trace) {
00189     fprintf(TFile, "SSA rename: detect all phi nodes from BB%d "
00190       "because of the number of pred has changed.\n", bb->Id());
00191   }
00192 
00193   PHI_NODE *next_phi;
00194   for (PHI_NODE *phi = bb->Phi_list()->Head();
00195        phi != NULL;
00196        phi = next_phi) {
00197     next_phi = phi->Next();
00198     delete_var_phi(phi, htable, trace);
00199   }
00200   bb->Phi_list()->Set_Head(NULL);
00201   bb->Phi_list()->Set_Tail(NULL);
00202   bb->Phi_list()->Set_in_degree(bb->Pred()->Len());
00203       } else {
00204   FOR_ALL_ELEM (phi, phi_iter, Init(bb->Phi_list())) {
00205     phi->Reset_visited();
00206   }
00207       }
00208     }
00209   }
00210 
00211   // Run classical phi insertion algorithm to mark required phis.
00212   FOR_ALL_ELEM (bb, cfg_iter, Init(cfg)) {
00213     STMTREP_ITER stmt_iter(bb->Stmtlist());
00214     STMTREP *stmt;
00215     FOR_ALL_NODE(stmt, stmt_iter, Init()) {
00216       if (OPERATOR_is_scalar_store (stmt->Opr())) {
00217   CODEREP *lhs = stmt->Lhs();
00218   if (!lhs->Is_var_volatile())
00219     Insert_var_phi(lhs, bb, cu, trace);
00220       }
00221       if (stmt->Has_chi()) {
00222   CHI_LIST_ITER chi_iter;
00223   CHI_NODE *cnode;
00224   CHI_LIST *chi_list = stmt->Chi_list();
00225   FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00226     CODEREP *lhs = cnode->Live() ? cnode->RESULT() : 
00227       cu->Ssa()->Get_zero_version_CR(cnode->Aux_id(), cu->Opt_stab(), 0);
00228     if (!lhs->Is_var_volatile())
00229       Insert_var_phi(lhs, bb, cu, trace);
00230   }
00231       }
00232     }
00233   }
00234 
00235   // Delete phi that are not 'visited' by 'insert_var_phi'
00236   FOR_ALL_ELEM (bb, cfg_iter, Init(cfg)) {
00237     PHI_NODE *first = NULL;
00238     PHI_NODE *last = NULL;
00239     PHI_NODE *next_phi;
00240     if (bb->Phi_list() != NULL) {
00241       for (PHI_NODE *phi = bb->Phi_list()->Head();
00242      phi != NULL;
00243      phi = next_phi) {
00244   if (phi->Visited()) {
00245     if (first == NULL) first = phi;
00246     last = phi;
00247     next_phi = phi->Next();
00248     phi->Reset_visited();
00249   } else {
00250     next_phi = phi->Next();
00251     delete_var_phi(phi, htable, trace);
00252     if (last != NULL)
00253       last->Set_Next(next_phi);
00254     phi->Set_Next(NULL);
00255   }
00256       }
00257       bb->Phi_list()->Set_Head(first);
00258       bb->Phi_list()->Set_Tail(last);
00259     }
00260   }
00261 }
00262 
00263 static TRACK_CUR_VERSION *debug_rename_stack;
00264 
00265 extern "C" {
00266 void Print_version_stack(AUX_ID id, FILE *fp);
00267 }
00268 
00269 void Print_version_stack(AUX_ID id, FILE *fp) {
00270   STACK<CODEREP*> *s = debug_rename_stack->_vec_of_stack[id];
00271   for (int i = 0; i < s->Elements(); ++i) {
00272     CODEREP *top = s->Top_nth(i);
00273     if (top)
00274       fprintf(fp, "cr%d ", top->Coderep_id());
00275     else
00276       fprintf(fp, "null ");
00277   }
00278   fprintf(fp,"\n");
00279 }
00280 
00281 
00282 //  Apply SSA Rename on CODEREPs 
00283 
00284 struct SSA_RENAME : public NULL_TRANSFORM {
00285   COMP_UNIT         *cu;
00286   TRACK_CUR_VERSION *rename_stack;
00287 
00288   SSA_RENAME(COMP_UNIT *comp_unit): 
00289     NULL_TRANSFORM(), cu(comp_unit), rename_stack(NULL)
00290   {}
00291   
00292   const char *Name() const { return "SSA RENAME"; }
00293   CODEREP *cur_version(AUX_ID id, CODEREP *cr) const {
00294     if (!cr->Is_var_volatile())
00295       if (!rename_stack->Is_volatile(id))   // See opt_verify.cxx for comments
00296   if (rename_stack->Size(id) == 0)
00297     // Use without def (e.g. zero version phi opnd introduced during
00298     // Insert_var_phi()
00299     //
00300     return cu->Ssa()->Get_zero_version_CR(id, cu->Opt_stab(), 0);
00301   else
00302     return rename_stack->Top(id);
00303     return cr;
00304   }
00305   CODEREP *non_zero_cur_version(AUX_ID id, CODEREP *cr) const {
00306     if (!cr->Is_var_volatile())
00307       if (!rename_stack->Is_volatile(id))   // See opt_verify.cxx for comments
00308   return rename_stack->Non_zero_top(id);
00309     return cr;
00310   }
00311   void Print_stack(AUX_ID id, FILE *fp) {
00312     rename_stack->Print_stack(id, fp);
00313   }
00314   CODEREP *Apply_cr(CODEREP *cr, bool is_mu, STMTREP *stmt, BB_NODE *bb, CODEMAP *htable) const 
00315   {
00316     if (cr->Kind() == CK_VAR) {
00317       CODEREP *tmp = cur_version(cr->Aux_id(), cr);
00318       if (is_mu && tmp->Is_flag_set(CF_IS_ZERO_VERSION)) {
00319   tmp = non_zero_cur_version(cr->Aux_id(), cr);
00320   Is_True(tmp != NULL, ("Second rename: cannot find non-zero version."));
00321       }
00322       if (tmp->Is_flag_set((CR_FLAG)(CF_DEF_BY_CHI|CF_DEF_BY_PHI))) {
00323         tmp->Set_field_id(cr->Field_id());
00324         tmp->Set_lod_ty(cr->Lod_ty());
00325 #ifdef KEY
00326   if (cr->Dtyp() != MTYPE_UNKNOWN)
00327 #endif
00328           tmp->Set_dtyp(cr->Dtyp());
00329 #ifdef KEY
00330   if (cr->Dsctyp() != MTYPE_UNKNOWN)
00331 #endif
00332           tmp->Set_dsctyp(cr->Dsctyp());
00333 #ifdef KEY
00334   tmp->Set_sign_extension_flag(); // cr could be a non-real occurence node
00335                      // being converted to real the first time, so its 
00336          // sign_extd flag has never been set before
00337 #endif
00338       }
00339       if (cr->Dsctyp() == MTYPE_BS) 
00340         tmp->Set_offset(cr->Offset());  // cannot use offset out of opt_stab
00341       return ((tmp != cr) ? 
00342         (is_mu || cr->Dsctyp() == MTYPE_BS ? 
00343         tmp : 
00344         cr->Convert_type(htable, tmp, FALSE)) :
00345         NULL);
00346     }
00347     if (inCODEKIND(cr->Kind(), CK_IVAR|CK_OP)) {
00348       // do not reset CF_C_P_PROCESSED, i.e. same as CF_LDA_LABEL, for CK_LDA  
00349       cr->Reset_flag(CF_C_P_PROCESSED);
00350     }
00351     //  CF_C_P_REHASHED is same as CF_DONT_PROP
00352     cr->Reset_flag(CF_DONT_PROP);
00353     if (is_mu)
00354       cr->Set_flag(CF_DONT_PROP);
00355     return NULL;
00356   }
00357   void Apply_sr(STMTREP *sr, BB_NODE *bb, CODEMAP *htable) const
00358   {
00359     if (sr->Has_mu()) {
00360       MU_LIST_ITER mu_iter;
00361       MU_NODE *mnode;
00362       FOR_ALL_NODE( mnode, mu_iter, Init(sr->Mu_list())) {
00363   CODEREP *cur = cur_version(mnode->Aux_id(), mnode->OPND());
00364   mnode->Set_OPND(cur);
00365   cur->Set_flag(CF_DONT_PROP);
00366       }
00367     }
00368     if (sr->Has_chi() && sr->Opr() != OPR_OPT_CHI) {
00369       CHI_LIST_ITER chi_iter;
00370       CHI_NODE *cnode;
00371       CHI_LIST *chi_list = sr->Chi_list();
00372       if (OPERATOR_is_scalar_istore (sr->Opr())) {
00373   AUX_ID aux = sr->Lhs()->Ivar_occ()->Aux_id();
00374   FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00375     if (!cnode->Dse_dead()) {
00376       CODEREP *cur = cur_version(cnode->Aux_id(), cnode->OPND()); 
00377       cnode->Set_OPND(cur);
00378       if (cnode->Live())
00379         cur->Set_flag(CF_DONT_PROP);
00380       if (cnode->Aux_id() == aux && sr->Lhs()->Ivar_mu_node())
00381         sr->Lhs()->Ivar_mu_node()->Set_OPND(cnode->RESULT());
00382     }
00383   }
00384       } else {
00385   FOR_ALL_NODE( cnode, chi_iter, Init(chi_list)) {
00386     if (!cnode->Dse_dead()) {
00387       CODEREP *cur = cur_version(cnode->Aux_id(), cnode->OPND()); 
00388       cnode->Set_OPND(cur);
00389       if (cnode->Live())
00390         cur->Set_flag(CF_DONT_PROP);
00391     }
00392   }
00393       }
00394     }
00395   }
00396   void Apply_bb_post(BB_NODE *bb, CODEMAP *htable) const 
00397   {
00398     PHI_NODE *phi;
00399     PHI_LIST_ITER phi_iter;
00400     BB_NODE *succ; BB_LIST_ITER bb_iter;
00401     FOR_ALL_ELEM (succ, bb_iter, Init(bb->Succ())) {
00402       INT32 pos = succ->Pred()->Pos(bb);
00403       FOR_ALL_ELEM (phi, phi_iter, Init(succ->Phi_list())) {
00404   if (phi->Live()) {
00405     CODEREP *cur = cur_version(phi->Aux_id(), phi->OPND(pos));
00406     phi->Set_opnd(pos, cur);
00407     cur->Set_flag(CF_DONT_PROP);
00408   }
00409       }
00410     }
00411   }
00412   // Setup control which combinations are legal
00413   void Setup(PER_SR_CACHE *, TRACK_CUR_VERSION *ver) {
00414     rename_stack = ver;
00415     debug_rename_stack = rename_stack;
00416   }
00417 };
00418 
00419 
00420 //  Apply SSA rename to the CODEMAP.
00421 //    Insert and delete phi function as needed
00422 //
00423 void
00424 Rename_CODEMAP(COMP_UNIT *cu)
00425 {
00426   BOOL trace = Get_Trace(TP_WOPT2, SECOND_RENAME_FLAG);
00427   Insert_delete_phi(cu, trace);
00428 
00429   SSA_RENAME ssa_rename(cu);
00430   UPDATE<SSA_RENAME, PER_SR_CACHE, TRACK_CUR_VERSION>
00431     UPDATE_ssa(cu, &ssa_rename, trace);
00432   UPDATE_ssa.Process_PU();
00433 
00434   if (trace) {
00435     fprintf( TFile, "%sAfter COMP_UNIT::Rename_CODEMAP\n%s",
00436        DBar, DBar );
00437     cu->Cfg()->Print(TFile);
00438   }
00439 }