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

00001 //-*-c++-*-
00002 
00003 /*
00004  * Copyright 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
00005  */
00006 
00007 // ====================================================================
00008 // ====================================================================
00009 //
00010 // Module: opt_essa.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_essa.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 // Description:
00051 //
00052 // SSA PRE Step 3:
00053 //  Assign same e_version to the EXP_OCCURS that have the same value.
00054 //  It works on one worklist at a time.
00055 //
00056 // ====================================================================
00057 // ====================================================================
00058 
00059 
00060 #ifdef USE_PCH
00061 #include "opt_pch.h"
00062 #endif // USE_PCH
00063 #pragma hdrstop
00064 
00065 
00066 #define opt_essa_CXX  "opt_essa.cxx"
00067 
00068 #include "defs.h"
00069 #include "errors.h"
00070 #include "erglob.h"
00071 #include "tracing.h"
00072 #include "opt_defs.h"
00073 #include "opt_base.h"
00074 #include "opt_config.h"
00075 #include "cxx_memory.h"
00076 #include "bb_node_set.h"
00077 #include "opt_bb.h"
00078 #include "opt_htable.h"
00079 #include "opt_ssa.h"
00080 #include "opt_etable.h"
00081 #include "opt_estr.h"
00082 #include "opt_alias_rule.h"
00083 #include "opt_mu_chi.h"
00084 #include "opt_lftr2.h"
00085 
00086 
00087 // ESSA:  Expr SSA class
00088 //
00089 class ESSA {
00090 
00091 private:
00092   MEM_POOL            _mpool;           // ESSA private mempool
00093   STACK<EXP_OCCURS*> *_stack;           // Rename stack
00094   ETABLE             *_etable;          // Pointer to the etable
00095   STR_RED            *_str_red;         // Strength-reduction class
00096   EXP_WORKLST        *_worklist;        // current worklist
00097   const CODEREP      *_cur_e_expr;      // the expr corrs to the worklist
00098   const ALIAS_RULE   *_rule;        // alias rule
00099   OPT_STAB           *_opt_stab;        // opt_stab
00100  
00101   STACK<EXP_OCCURS*> *Stack(void) const      { return _stack; }
00102   ETABLE       *Etable(void) const     { return _etable; }
00103   STR_RED      *Str_red(void) const    { return _str_red; }
00104   EXP_WORKLST        *Worklist(void) const   { return _worklist; }
00105   const CODEREP      *Cur_e_expr(void) const { return _cur_e_expr; }
00106   const ALIAS_RULE   *Rule(void) const       { return _rule; }
00107   OPT_STAB           *Opt_stab(void) const   { return _opt_stab; }
00108   BOOL          Tracing(void) const    { return _etable->Tracing(); }
00109 
00110   inline BOOL         Lod_modified_real_occ_real_occ(const CODEREP *,
00111                  const CODEREP *) const;
00112   BOOL                Lod_modified_phi_result(const BB_NODE *,
00113                 const CODEREP *) const;
00114   BOOL                Lod_modified_real_occ_phi_opnd(const CODEREP *, 
00115                  const BB_NODE *,
00116                  INT) const;
00117 
00118   BOOL                Ilod_modified_phi_result(const BB_NODE *,
00119                  const CODEREP *) const;
00120   BOOL                Ilod_modified_real_occ_phi_opnd(const BB_NODE *,
00121                   const CODEREP *,
00122                   const BB_NODE *,
00123                   INT) const;
00124   BOOL                Ilod_modified_real_occ_real_occ(const BB_NODE *,
00125                   const CODEREP *,
00126                   const CODEREP *) const;
00127 
00128   BOOL                Same_e_version_real_occ_real_occ(const EXP_OCCURS *,
00129                    EXP_OCCURS *) const;
00130   BOOL                Same_e_version_phi_result(const EXP_OCCURS *,
00131             const CODEREP *,
00132             EXP_OCCURS *) const;
00133   BOOL                Same_e_version_real_occ_phi_opnd(const EXP_OCCURS *,
00134                    BB_NODE *,
00135                    INT,
00136                    const CODEREP *,
00137                    BOOL *) const;
00138 
00139   BOOL Injured_real_occ_real_occ(const EXP_OCCURS *def, EXP_OCCURS *use) const;
00140   BOOL Injured_phi_result_real_occ(const EXP_OCCURS *def,
00141            const CODEREP *use_cr,
00142            BB_NODE *use_bb) const;
00143   BOOL Injured_real_occ_phi_opnd( const EXP_OCCURS *def, 
00144           BB_NODE *use_bb, INT opnd_num ) const;
00145 
00146   void Canonicalize_operands( CODEREP *def0, CODEREP *def1,
00147             CODEREP **use0, CODEREP **use1 ) const;
00148 
00149   inline void         Create_new_version(EXP_OCCURS *);
00150   inline void         Reset_tos_downsafe(void);
00151 
00152   CODEREP            *Alloc_and_generate_injured_phi_res(const EXP_OCCURS *,
00153                const EXP_OCCURS *,
00154                MEM_POOL *) const;
00155   void                Process_delayed_rename(EXP_OCCURS *, CODEREP *) const;
00156   BOOL                Same_base_diff_offset(const CODEREP *,
00157               const CODEREP *) const;
00158   BOOL                Same_base_same_offset(const CODEREP *,
00159               const CODEREP *) const;
00160 public:
00161                     ESSA(ETABLE *etable, EXP_WORKLST *worklist,
00162        ALIAS_RULE *ar);
00163                    ~ESSA(void);
00164   void              Rename(void);
00165 
00166 };
00167 
00168 
00169 inline BOOL
00170 ESSA::Lod_modified_real_occ_real_occ(const CODEREP *def, const CODEREP *use) const
00171 {
00172   return (def != use);
00173 }
00174 
00175 
00176 // Returns TRUE if cr is modified anywhere between the
00177 // beginning of bb (not counting the phis) to its use point.
00178 BOOL
00179 ESSA::Lod_modified_phi_result(const BB_NODE *bb, const CODEREP *cr) const
00180 {
00181   if (cr->Is_flag_set(CF_IS_ZERO_VERSION))
00182     return TRUE;
00183 
00184   if (cr->Defbb() != bb) {
00185     // different BB, check dominance
00186     if (cr->Defbb()->Dominates(bb)) 
00187       return FALSE;
00188   } else {
00189     // same BB
00190     if (cr->Is_flag_set(CF_DEF_BY_PHI)) 
00191       return FALSE;
00192   }
00193   return TRUE;
00194 }
00195 
00196 
00197 // use_bb is the one associated with use exp_phi result.
00198 BOOL
00199 ESSA::Lod_modified_real_occ_phi_opnd(const CODEREP *cr, const BB_NODE *use_bb,
00200              INT opnd_num) const
00201 {
00202   const PHI_NODE *var_phi = _etable->Lookup_var_phi(use_bb, cr->Aux_id());
00203   if (var_phi == NULL) 
00204     return FALSE;
00205   if (!var_phi->Live())  // conservatively
00206     return TRUE;
00207 
00208   const CODEREP *newcr = var_phi->OPND(opnd_num);
00209   if (newcr->Is_flag_set(CF_IS_ZERO_VERSION))
00210     return TRUE;
00211 
00212   return (cr != newcr);
00213 }
00214 
00215 
00216 // Return TRUE if their base is the same, and the difference
00217 // in their offset is bigger than ilod_size.
00218 // Return FALSE otherwise and conservatively.
00219 //
00220 BOOL
00221 ESSA::Same_base_diff_offset(const CODEREP *cr1, const CODEREP *cr2) const
00222 {
00223   if (cr1->Kind() != CK_IVAR || cr2->Kind() != CK_IVAR)
00224     return FALSE;
00225 
00226   CODEREP *base1 = cr1->Ilod_base() ? cr1->Ilod_base() : cr1->Istr_base();
00227   CODEREP *base2 = cr2->Ilod_base() ? cr2->Ilod_base() : cr2->Istr_base();
00228   if (base1 == base2) {
00229     // make cr1 to be the one with smaller offset
00230     if (cr1->Offset() > cr2->Offset()) {
00231       const CODEREP *tcr = cr1;
00232       cr1 = cr2;
00233       cr2 = tcr;
00234     }
00235     INT32 size1 = (MTYPE_size_min(OPCODE_rtype(cr1->Op())) >> 3);
00236     if (cr1->Offset() + size1 > cr1->Offset()) { // overflow detection
00237       if (cr1->Offset() + size1 <= cr2->Offset())
00238   return TRUE;
00239     }
00240   }
00241   return FALSE;
00242 }
00243 
00244 
00245 // Return TRUE if their base and offset are the same
00246 BOOL
00247 ESSA::Same_base_same_offset(const CODEREP *cr1, const CODEREP *cr2) const
00248 {
00249   if (cr1->Kind() != CK_IVAR || cr2->Kind() != CK_IVAR)
00250     return FALSE;
00251 
00252   CODEREP *base1 = cr1->Ilod_base() ? cr1->Ilod_base() : cr1->Istr_base();
00253   CODEREP *base2 = cr2->Ilod_base() ? cr2->Ilod_base() : cr2->Istr_base();
00254   if (base1 == base2) {
00255     if (cr1->Offset() ==  cr2->Offset()) 
00256       return TRUE;
00257   }
00258   return FALSE;
00259 }
00260 
00261 
00262 BOOL
00263 ESSA::Ilod_modified_phi_result(const BB_NODE *phi_bb, const CODEREP *cr) const
00264 {
00265   const CODEREP *cr_vsym = cr->Ivar_mu_node()->OPND();
00266   if (cr_vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00267     return TRUE;
00268 
00269   for (const CODEREP *vsym = cr_vsym;
00270        vsym != NULL;
00271        vsym = vsym->Defchi()->OPND()) {
00272     
00273     if (vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00274       return TRUE;
00275 
00276     if (vsym->Defbb() != phi_bb && !phi_bb->Dominates(vsym->Defbb()))
00277       return FALSE;
00278 
00279     // Now we know the phi dominates the vsym's definition, since
00280     // either the phi and the vsym def are in the same bb, or the
00281     // phi_bb dominates the vsym's defbb.
00282 
00283     if (vsym->Is_flag_set(CF_DEF_BY_PHI))
00284       return FALSE;
00285 
00286     if (!vsym->Is_flag_set(CF_DEF_BY_CHI))
00287       return TRUE;
00288 
00289     STMTREP *sr = vsym->Defstmt();
00290     if (sr == NULL || !OPCODE_is_store(sr->Op())) return TRUE;
00291 
00292 #ifdef KEY // bug 7814
00293 #ifdef TARG_NVISA
00294 // bug 7814 is for a fortran program that was too aggressive in optimizing.
00295 // But for nvidia's bug 417551, this is a safe optimization that helps perf.
00296 // The root problem seems to be a weakness of alias analysis, as taking
00297 // the address of a temp is blocking the optimization.
00298 // Until we find a non-working program or come up with a better workaround,
00299 // put this check under a flag.
00300     if ( ! WOPT_Enable_Aggressive_Iload_CSE)
00301 #endif
00302     if (vsym->Aux_id() == Opt_stab()->Default_vsym())
00303       return TRUE;
00304 #endif
00305 
00306     //since the ansi rule is turned on by default, but now there're
00307     //still some unsafe things. we need to do a fix here
00308     //this's definite alias case, which we can do before apply the
00309     //the alias rule
00310     if(Same_base_same_offset(sr->Lhs(), cr))
00311       return TRUE;
00312 
00313     // Seems like the following can lead to use-before-def if the
00314     // defstmt's result is not aliased with the use (i.e., with
00315     // vsym). Why? Because we may say the phi result is the same
00316     // e-version as cr if the operations aren't aliased, and when that
00317     // happens we will set the phi's result occurrence to be cr. cr
00318     // has a mu for the version of the vsym that is the LHS of sr's
00319     // chi, and sr cannot dominate the phi!
00320     if (Rule()->Aliased_Memop(sr->Lhs()->Points_to(Opt_stab()),
00321             cr->Points_to(Opt_stab()),
00322             (sr->Lhs()->Kind() == CK_VAR) ?
00323             sr->Lhs()->Lod_ty() : sr->Lhs()->Ilod_ty(),
00324             cr->Ilod_ty(), TRUE) &&
00325   !Same_base_diff_offset(sr->Lhs(), cr))
00326       return TRUE;
00327     
00328 
00329     // Fix 459756.  Also see comments above.  Update the mu-node of the
00330     // CK_IVAR to point the chi of the aliased defstmt.  This fixed the
00331     // use-before-def assertion, but the best fix is *not* to check
00332     // Aliased_Memop() in ESSA, if the CODEREP in htable has already been
00333     // canonicalized.
00334     // cr->Ivar_mu_node()->Set_OPND(vsym->Defchi()->OPND());
00335 
00336     // Fix 461898.  The above fix is wrong if the new opnd is a zero version!
00337     if (vsym->Defchi()->OPND()->Is_flag_set(CF_IS_ZERO_VERSION))
00338       return TRUE;
00339 
00340     cr->Ivar_mu_node()->Set_OPND(vsym->Defchi()->OPND());
00341   }
00342 
00343   // if unable to follow the use-def chain, return TRUE.
00344   return TRUE;
00345 }
00346 
00347 
00348 BOOL
00349 ESSA::Ilod_modified_real_occ_phi_opnd(const BB_NODE *def_bb, const CODEREP *cr,
00350              const BB_NODE *use_bb, INT opnd_num) const
00351 {
00352   const PHI_NODE *var_phi = _etable->Lookup_var_phi(use_bb,
00353                 cr->Ivar_occ()->Aux_id());
00354   if (var_phi == NULL) 
00355     return FALSE;
00356   if (!var_phi->Live())  // conservatively
00357     return TRUE;
00358 
00359   const CODEREP *cr_vsym = cr->Get_ivar_vsym();
00360   if (cr_vsym == NULL || cr_vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00361     return TRUE;
00362   
00363   for (CODEREP *vsym = var_phi->OPND(opnd_num);
00364        vsym != NULL;
00365        vsym = vsym->Defchi()->OPND()) {
00366 
00367     if (vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00368       return TRUE;
00369 
00370     if (vsym == cr_vsym) // guarantee that we don't follow the use-def and pass the real-occ.
00371       return FALSE;
00372 
00373     if (vsym->Defbb() != def_bb && !def_bb->Dominates(vsym->Defbb()))
00374       return FALSE;
00375 
00376     if (vsym->Is_flag_set(CF_DEF_BY_PHI))
00377       return FALSE;
00378 
00379     if (!vsym->Is_flag_set(CF_DEF_BY_CHI))
00380       return TRUE;
00381 
00382     if (vsym->Defstmt() == cr->Ivar_defstmt())
00383       return FALSE;
00384 
00385     STMTREP *sr = vsym->Defstmt();
00386     if (sr == NULL || !OPCODE_is_store(sr->Op())) return TRUE;
00387 
00388 #ifdef KEY // bug 7814
00389     // NVISA:  this instance of the check so far seems to not cause a problem
00390     if (vsym->Aux_id() == Opt_stab()->Default_vsym())
00391       return TRUE;
00392 #endif
00393 
00394     if (Rule()->Aliased_Memop(sr->Lhs()->Points_to(Opt_stab()),
00395             cr->Points_to(Opt_stab()),
00396             sr->Lhs()->Kind() == CK_VAR ? sr->Lhs()->Lod_ty() : sr->Lhs()->Ilod_ty(),
00397             cr->Ilod_ty(), TRUE) &&
00398   !Same_base_diff_offset(sr->Lhs(), cr))
00399       return TRUE;
00400   }
00401 
00402   // if unable to follow the use-def chain, return TRUE.
00403   return TRUE;
00404 }
00405 
00406 
00407 BOOL
00408 ESSA::Ilod_modified_real_occ_real_occ(const BB_NODE *def_bb,
00409               const CODEREP *def_cr,
00410               const CODEREP *use_cr) const
00411 {
00412   CODEREP *def_vsym = def_cr->Get_ivar_vsym();
00413 
00414   if (def_vsym == NULL ||
00415       def_vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00416     return TRUE;
00417 
00418   for (CODEREP *vsym = use_cr->Ivar_mu_node()->OPND(); 
00419        vsym != NULL;
00420        vsym = vsym->Defchi()->OPND()) {
00421     
00422     if (vsym->Is_flag_set(CF_IS_ZERO_VERSION))
00423       return TRUE;
00424 
00425     if (def_vsym == vsym)
00426       return FALSE;
00427 
00428     if (vsym->Defbb() != def_bb && !def_bb->Dominates(vsym->Defbb()))
00429       return FALSE;
00430 
00431     if (vsym->Is_flag_set(CF_DEF_BY_PHI))
00432       return FALSE;
00433 
00434     if (!vsym->Is_flag_set(CF_DEF_BY_CHI))
00435       return TRUE;
00436 
00437     STMTREP *sr = vsym->Defstmt();
00438     if (sr == NULL || !OPCODE_is_store(sr->Op())) return TRUE;
00439 
00440 #ifdef KEY // bug 7814
00441     if (vsym->Aux_id() == Opt_stab()->Default_vsym())
00442       return TRUE;
00443 #endif
00444 
00445     if (Rule()->Aliased_Memop(sr->Lhs()->Points_to(Opt_stab()),
00446             use_cr->Points_to(Opt_stab()), 
00447             sr->Lhs()->Kind() == CK_VAR ? sr->Lhs()->Lod_ty() : sr->Lhs()->Ilod_ty(),
00448             use_cr->Ilod_ty(), TRUE) &&
00449   !Same_base_diff_offset(sr->Lhs(), use_cr))
00450       return TRUE;
00451   }
00452 
00453   // if unable to follow the use-def chain, return TRUE.
00454   return TRUE;
00455 }
00456 
00457 
00458 // See Rules for Assigning e-versions 
00459 //    INPUT:  def is either real occurrence or phi result
00460 //            use must be a real occurrence
00461 //    OUTPUT: true if both occurrences should have same version
00462 //
00463 BOOL 
00464 ESSA::Same_e_version_real_occ_real_occ(const EXP_OCCURS *def,
00465                EXP_OCCURS *use) const
00466 {
00467   Is_True(use->Occ_kind() == EXP_OCCURS::OCC_REAL_OCCUR,
00468     ("ESSA::Same_e_version_real_occ_rel_occ: use is not a real occur"));
00469   Is_True(def->Occ_kind() == EXP_OCCURS::OCC_REAL_OCCUR,
00470     ("ESSA::Same_e_version_real_occ_rel_occ: def is not a real occur"));
00471 
00472   //  Rule #1:  both are real occurrences
00473   if (def->Occurrence() == use->Occurrence()) {
00474     // propagate the injured flag
00475     if ( def->Injured_occ() )
00476       use->Set_injured_occ();
00477     return TRUE;
00478   }
00479 
00480   // Can do some extra analysis for CK_IVAR.
00481   // opt_htable.cxx should already hashed identical *p into same CR
00482   // in lieu of effects of optimizations.
00483   if (use->Occurrence()->Kind() == CK_IVAR) {
00484     CODEREP *def_base = def->Occurrence()->Ilod_base() ?
00485       def->Occurrence()->Ilod_base() :
00486       def->Occurrence()->Istr_base();
00487     CODEREP *use_base = use->Occurrence()->Ilod_base() ?
00488       use->Occurrence()->Ilod_base() :
00489       use->Occurrence()->Istr_base();
00490     if (!Lod_modified_real_occ_real_occ(def_base, use_base) &&
00491   !Ilod_modified_real_occ_real_occ(def->Bb(), def->Occurrence(),
00492            use->Occurrence())) 
00493       {
00494   Is_Trace(Tracing(),
00495      (TFile, "ESSA: identical iloads have different CR *:\n"));
00496   Is_Trace_cmd(Tracing(), def->Occurrence()->Print(4, TFile));
00497   Is_Trace(Tracing(), (TFile, " with Defstmt():\n"));
00498   if (def->Occurrence()->Ivar_defstmt() != NULL) {
00499     Is_Trace_cmd(Tracing(),
00500            def->Occurrence()->Ivar_defstmt()->Print(TFile));
00501   }
00502   else {
00503     Is_Trace(Tracing(), (TFile, "<NULL>\n"));
00504   }
00505   Is_Trace(Tracing(), (TFile, " with mu Defstmt():\n"));
00506   if (def->Occurrence()->Ivar_mu_node() != NULL &&
00507       def->Occurrence()->Ivar_mu_node()->OPND()->Defstmt() != NULL) {
00508     Is_Trace_cmd(Tracing(),
00509            def->Occurrence()->Ivar_mu_node()->OPND()->Defstmt()->Print(TFile));
00510   }
00511   else {
00512     Is_Trace(Tracing(), (TFile, "<NULL> mu node or mu node Defstmt()\n"));
00513   }
00514   Is_Trace(Tracing(), (TFile, "-----------------------------\n"));
00515   Is_Trace_cmd(Tracing(), use->Occurrence()->Print(4, TFile));
00516   Is_Trace(Tracing(), (TFile, " with Defstmt():\n"));
00517   if (use->Occurrence()->Ivar_defstmt() != NULL) {
00518     Is_Trace_cmd(Tracing(),
00519            use->Occurrence()->Ivar_defstmt()->Print(TFile));
00520   }
00521   else {
00522     Is_Trace(Tracing(), (TFile, "<NULL>\n"));
00523   }
00524   Is_Trace(Tracing(), (TFile, " with mu Defstmt():\n"));
00525   if (use->Occurrence()->Ivar_mu_node() != NULL &&
00526       use->Occurrence()->Ivar_mu_node()->OPND()->Defstmt() != NULL) {
00527     Is_Trace_cmd(Tracing(),
00528            use->Occurrence()->Ivar_mu_node()->OPND()->Defstmt()->Print(TFile));
00529   }
00530   else {
00531     Is_Trace(Tracing(), (TFile, "<NULL> mu node or mu node Defstmt()\n"));
00532   }
00533   Is_Trace(Tracing(), (TFile, "-----------------------------\n"));
00534   // This situation can arise because of unique (or
00535   // restricted?) pointers and copy-propagation. Unique
00536   // pointers and copy propagation can result in a situation
00537   // where the vsyms associated with two different ILOADs are
00538   // not said to alias. Usually this means an LNO problem, but
00539   // it is probably also possible for users to create this
00540   // situation in their source code.
00541   //
00542   // DevWarn("ESSA: found identical iloads that have different CR *.");
00543   return TRUE;
00544       } 
00545   } else if (use->Occurrence()->Kind() == CK_OP && 
00546        (OPCODE_operator(use->Occurrence()->Op()) == OPR_INTRINSIC_OP
00547 #ifdef KEY
00548         || OPCODE_operator(use->Occurrence()->Op()) == OPR_PURE_CALL_OP
00549 #endif
00550        )) {
00551       
00552     for (INT32 i = 0; i < use->Occurrence()->Kid_count(); i++) {
00553       CODEREP *opnd = use->Occurrence()->Opnd(i);
00554       if (opnd->Ivar_mu_node() != NULL ||
00555     (opnd->Ilod_base()->Kind() == CK_VAR &&
00556      Lod_modified_real_occ_real_occ(def->Occurrence()->Opnd(i)->Ilod_base(),
00557             use->Occurrence()->Opnd(i)->Ilod_base())))
00558   return FALSE;
00559     }
00560   }
00561 
00562   // Can we perform strength-reduction on this expression?
00563   if ( !Worklist()->Exclude_sr_cand() && 
00564        Injured_real_occ_real_occ( def, use ) ) {
00565     use->Set_injured_occ();
00566     Is_Trace(Tracing(),(TFile,"Injured occurrence\n"));
00567     return TRUE;
00568   }
00569   
00570   return FALSE;
00571 }
00572 
00573 //=====================================================================
00574 // Determine if the use occurrence is injured
00575 //=====================================================================
00576 
00577 BOOL 
00578 ESSA::Injured_real_occ_real_occ(const EXP_OCCURS *def, EXP_OCCURS *use) const
00579 {
00580   const CODEREP *def_cr = def->Occurrence();
00581   const CODEREP *use_cr = use->Occurrence();
00582 
00583   if ( use_cr->Kind() == CK_OP &&
00584        Str_red()->Candidate_opc( use_cr->Op() ) )
00585   {
00586     CODEREP *def_opnd0 = def_cr->Kid_count() > 0 ? 
00587              def_cr->Opnd(0) : NULL;
00588     CODEREP *def_opnd1 = def_cr->Kid_count() > 1 ? 
00589              def_cr->Opnd(1) : NULL;
00590     CODEREP *use_opnd0 = use_cr->Kid_count() > 0 ? 
00591              use_cr->Opnd(0) : NULL;
00592     CODEREP *use_opnd1 = use_cr->Kid_count() > 1 ? 
00593              use_cr->Opnd(1) : NULL;
00594 
00595     // we may need to swap operands if one of the codereps wasn't
00596     // canonicalized
00597     Canonicalize_operands( def_opnd0, def_opnd1,
00598         &use_opnd0,&use_opnd1 );
00599 
00600     if ( Str_red()->Candidate( use_cr,
00601              def_opnd0, def_opnd1, def->Bb(),
00602              use_opnd0, use_opnd1, use->Bb() ) )
00603     {
00604       return TRUE;
00605     }
00606   }
00607 
00608   return FALSE;
00609 }
00610 
00611 //=====================================================================
00612 // See Rules for Assigning e-versions 
00613 //=====================================================================
00614 //
00615 BOOL 
00616 ESSA::Same_e_version_phi_result(const EXP_OCCURS *def, const CODEREP *cr,
00617         EXP_OCCURS *use) const
00618 {
00619   Is_True(def->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR,
00620     ("ESSA::Same_e_version_phi_result: def is not a phi occur"));
00621 
00622   //  Rule #2:  def is phi occurrence and use is real occurrence
00623   //  Rule #4:  def is phi occurrence and use is phi-opnd
00624 
00625   switch (cr->Kind()) {
00626   case CK_IVAR:
00627     {
00628       CODEREP *addr = cr->Ilod_base() ? cr->Ilod_base() : cr->Istr_base();
00629       if (addr->Kind() == CK_VAR) {
00630   if (Lod_modified_phi_result(def->Bb(), addr))
00631     return FALSE;
00632       }
00633     }
00634     if (Ilod_modified_phi_result(def->Bb(), cr))
00635       return FALSE;
00636     return TRUE;
00637   case CK_OP:
00638     {
00639       BOOL not_mod = TRUE;
00640 
00641       for (INT i = 0; i < cr->Kid_count(); i++) {
00642   CODEREP *kid = cr->Opnd(i);
00643   switch (kid->Kind()) {
00644   case CK_VAR:
00645     if (Lod_modified_phi_result(def->Bb(), kid)) {
00646       not_mod = FALSE;
00647     }
00648     break;
00649   case CK_IVAR:  // should be OPR_PARM
00650     if (kid->Ivar_mu_node() != NULL ||
00651         (kid->Ilod_base()->Kind() == CK_VAR &&
00652          Lod_modified_phi_result(def->Bb(), kid->Ilod_base())))
00653       not_mod = FALSE;
00654     break;
00655   case CK_CONST:
00656   case CK_RCONST:
00657   case CK_LDA:
00658     break;
00659   default:
00660     Is_True(FALSE, ("unexpected CK_KIND."));
00661   }
00662       }
00663 
00664       if ( not_mod ) {
00665         // not modified, so all is fine
00666   return TRUE;
00667       }
00668       // modified, so see if simply injured
00669       else if ( !Worklist()->Exclude_sr_cand() && 
00670     Injured_phi_result_real_occ( def, cr, use->Bb())) 
00671       {
00672   use->Set_injured_occ();
00673   Is_Trace(Tracing(),
00674      (TFile,"Same_e_version_phi_result: Injured occurrence\n"));
00675   return TRUE;
00676       }
00677 
00678       // modified, and not injured
00679       return FALSE;
00680     }
00681   case CK_VAR: // LPRE
00682     return (! Lod_modified_phi_result(def->Bb(), cr));
00683   default:
00684     Is_True(FALSE, ("unexpected CK_KIND."));
00685   }
00686   return FALSE;
00687 }
00688 
00689 //=====================================================================
00690 // Determine if the use occurrence is injured
00691 //=====================================================================
00692 
00693 BOOL 
00694 ESSA::Injured_phi_result_real_occ(const EXP_OCCURS *def, const CODEREP *use_cr,
00695           BB_NODE *use_bb) const
00696 {
00697   if ( use_cr->Kind() == CK_OP &&
00698        Str_red()->Candidate_opc( use_cr->Op() ) )
00699   {
00700     CODEREP *use_opnd0 = use_cr->Kid_count() > 0 ? 
00701              use_cr->Opnd(0) : NULL;
00702     CODEREP *use_opnd1 = use_cr->Kid_count() > 1 ? 
00703              use_cr->Opnd(1) : NULL;
00704 
00705     if ( Str_red()->Candidate_phi_res( use_cr,
00706              def->Bb(),
00707              use_opnd0, use_opnd1, use_bb) )
00708     {
00709       return TRUE;
00710     }
00711   }
00712 
00713   return FALSE;
00714 }
00715 
00716 
00717 //=====================================================================
00718 // See Rule #3.
00719 //    INPUT:  eexpr is the expression corresponding to the e-number
00720 //            def is either real occurrence or phi result
00721 //            use is the phi node at bb, with opnd_num indicating which opnd.
00722 //    OUTPUT: true if both occurrences should have same version
00723 //        Set *injured=TRUE if injured occurrence.
00724 //=====================================================================
00725 
00726 BOOL 
00727 ESSA::Same_e_version_real_occ_phi_opnd(const EXP_OCCURS *def, 
00728                BB_NODE *use_bb,
00729                INT opnd_num, 
00730                const CODEREP *use_cr,
00731                BOOL *injured) const
00732 {
00733   Is_True(def->Occ_kind() == EXP_OCCURS::OCC_REAL_OCCUR, ("not real occur."));
00734   *injured = FALSE;
00735 
00736   const CODEREP *cr = def->Occurrence();
00737   switch (cr->Kind()) {
00738   case CK_IVAR:
00739     {
00740       CODEREP *def_addr = cr->Ilod_base() ? cr->Ilod_base() : cr->Istr_base();
00741       CODEREP *use_addr = use_cr->Ilod_base();
00742       if (def_addr->Kind() == CK_VAR) {
00743   if (Lod_modified_real_occ_real_occ(def_addr, use_addr))
00744     return FALSE;
00745       }
00746     }
00747     if (Ilod_modified_real_occ_real_occ(def->Bb(), cr, use_cr))
00748       return FALSE;
00749     return TRUE;
00750   case CK_OP:
00751     {
00752       BOOL not_mod = TRUE;
00753       for (INT i = 0; i < cr->Kid_count(); i++) {
00754   CODEREP *kid = cr->Opnd(i);
00755   switch (kid->Kind()) {
00756   case CK_VAR:
00757     if (Lod_modified_real_occ_real_occ(kid, use_cr->Opnd(i))) {
00758       not_mod = FALSE;
00759     }
00760     break;
00761   case CK_IVAR:  // should be OPR_PARM
00762     if (kid->Ivar_mu_node() != NULL ||
00763         (kid->Ilod_base()->Kind() == CK_VAR && 
00764          Lod_modified_real_occ_real_occ(kid->Ilod_base(), use_cr->Opnd(i)->Ilod_base())))
00765       not_mod = FALSE;
00766     break;
00767   case CK_CONST:
00768   case CK_RCONST:
00769   case CK_LDA:
00770     break;
00771   default:
00772     Is_True(FALSE, ("unexpected CK_KIND."));
00773   }
00774       }
00775 
00776       if ( not_mod ) {
00777   // all is well
00778   return TRUE;
00779       }
00780       // modified, so see if simply injured
00781       else if ( !Worklist()->Exclude_sr_cand() && 
00782     Injured_real_occ_phi_opnd( def, use_bb, opnd_num ) )
00783       {
00784   *injured = TRUE;
00785   Is_Trace(Tracing(),
00786        (TFile,"Same_e_version_real_occ_phi_opnd: Injured occurrence\n"));
00787   return TRUE;
00788       }
00789 
00790       // modified, and not injured
00791       return FALSE;
00792     }
00793   case CK_VAR: // LPRE
00794     return (! Lod_modified_real_occ_real_occ(cr, use_cr));
00795   default:
00796     Is_True(FALSE, ("unexpected CK_KIND."));
00797   }
00798   return FALSE;
00799 }
00800 
00801 //=====================================================================
00802 // Determine if the phi_opnd is injured
00803 //=====================================================================
00804 
00805 BOOL 
00806 ESSA::Injured_real_occ_phi_opnd( const EXP_OCCURS *def, 
00807          BB_NODE *use_bb, INT opnd_num ) const
00808 {
00809   const CODEREP *def_cr = def->Occurrence();
00810 
00811   if ( def_cr->Kind() == CK_OP &&
00812        Str_red()->Candidate_opc( def_cr->Op() ) )
00813   {
00814     CODEREP *opnd = Etable()->
00815       Alloc_and_generate_cur_expr(def->Occurrence(), 
00816           use_bb, opnd_num, Etable()->Per_expr_pool(),
00817           FALSE /* do not convert zero ver */);
00818 
00819     CODEREP *def_opnd0 = def_cr->Kid_count() > 0 ? 
00820              def_cr->Opnd(0) : NULL;
00821     CODEREP *def_opnd1 = def_cr->Kid_count() > 1 ? 
00822              def_cr->Opnd(1) : NULL;
00823     CODEREP *use_opnd0 = opnd->Kid_count() > 0 ? 
00824              opnd->Opnd(0) : NULL;
00825     CODEREP *use_opnd1 = opnd->Kid_count() > 1 ? 
00826              opnd->Opnd(1) : NULL;
00827 
00828     // we may need to swap operands if one of the codereps wasn't
00829     // canonicalized
00830     Canonicalize_operands( def_opnd0, def_opnd1,
00831         &use_opnd0,&use_opnd1 );
00832 
00833     if ( Str_red()->Candidate( def_cr,
00834              def_opnd0, def_opnd1, def->Bb(),
00835              use_opnd0, use_opnd1, use_bb->Nth_pred(opnd_num) ) )
00836     {
00837       return TRUE;
00838     }
00839   }
00840 
00841   return FALSE;
00842 }
00843 
00844 //=====================================================================
00845 // May need to get operands in right order for checking strength-
00846 // reduction candidates
00847 //=====================================================================
00848 
00849 void 
00850 ESSA::Canonicalize_operands( CODEREP *def0, CODEREP *def1,
00851            CODEREP **use0, CODEREP **use1 ) const
00852 {
00853   CODEREP *tuse0 = *use0;
00854 
00855   // see if the first kids don't match
00856   if ( def0->Kind() != tuse0->Kind() ||
00857        (def0->Kind() == CK_VAR && def0->Aux_id() != tuse0->Aux_id()) )
00858   {
00859     // swap the kids
00860     *use0 = *use1;
00861     *use1 = tuse0;
00862   }
00863   else {
00864 #ifdef Is_True_On
00865     CODEREP *tuse1 = *use1;
00866 
00867     // verify that the second kids match also
00868     if( tuse1 != NULL ) {
00869       Is_True( def1 != NULL,
00870   ("ESSA::Canonicalize_operands: non-null kids don't match") );
00871 
00872       Is_True( def1->Kind() == tuse1->Kind(),
00873   ("ESSA::Canonicalize_operands: kids kind don't match") );
00874 
00875       if ( def1->Kind() == CK_VAR ) {
00876   Is_True( def1->Aux_id() == tuse1->Aux_id(),
00877     ("ESSA::Canonicalize_operands: kids aux_id's don't match") );
00878       }
00879     }
00880     else {
00881       Is_True( def1 == NULL,
00882   ("ESSA::Canonicalize_operands: null kids don't match") );
00883     }
00884 #endif // Is_True_On
00885   }
00886 }
00887 
00888 //=====================================================================
00889 //  Create a new e-version and push it onto the stack.
00890 //=====================================================================
00891 
00892 inline void
00893 ESSA::Create_new_version(EXP_OCCURS *occur)
00894 {
00895   occur->Set_e_version(Worklist()->Cur_e_version());
00896   Worklist()->New_e_version();
00897   Stack()->Push(occur);
00898 }
00899 
00900 
00901 // If the TOS is a phi-occur, reset its downsafe bit.
00902 //
00903 inline void
00904 ESSA::Reset_tos_downsafe(void)
00905 {
00906   // Reset down-safe if the phi result does have any real use.
00907   // (if there is any real use, the stack top should be a real occur.)
00908   if (!Stack()->Is_Empty() &&
00909       Stack()->Top() != NULL &&
00910       Stack()->Top()->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR) 
00911     Stack()->Top()->Exp_phi()->Set_not_down_safe();
00912 }
00913 
00914 
00915 //======================================================================
00916 // Strength-reduction has injured the result of this phi.  Need to
00917 // create a valid coderep that represents this phi result rather than
00918 // using the use's occurrence which has wrong versions.
00919 //======================================================================
00920 
00921 CODEREP *
00922 ESSA::Alloc_and_generate_injured_phi_res( const EXP_OCCURS *def, 
00923         const EXP_OCCURS *use, MEM_POOL *mpool ) const
00924 {
00925   Is_True( def->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR,
00926     ("ESSA::Alloc_and_generate_injured_phi_res: not phi def") );
00927 
00928   // allocate and copy from def.
00929   CODEREP *oldcr = use->Occurrence();
00930   CODEREP *newcr = CXX_NEW_VARIANT(CODEREP(*oldcr),
00931            oldcr->Extra_space_used(), mpool);
00932 
00933   switch ( newcr->Kind() ) {
00934     case CK_OP:
00935       {
00936   for (INT i = 0; i < newcr->Kid_count(); i++) {
00937     CODEREP *kid = newcr->Opnd(i);
00938     switch (kid->Kind()) {
00939     case CK_VAR:
00940       {
00941         const PHI_NODE *var_phi = 
00942     Etable()->Lookup_var_phi(def->Bb(), kid->Aux_id());
00943 
00944         if (var_phi != NULL) {
00945           // we have a phi, so its result is the correct version
00946     Is_True(var_phi->Live(), 
00947       ("ESSA::Alloc_and_generate_injured_phi_res: "
00948        "encounter dead phi node bb:%d Aux:%d.",
00949        def->Bb()->Id(), kid->Aux_id()));
00950     newcr->Set_opnd(i, var_phi->RESULT());
00951         }
00952         else {
00953     // no phi, so we need to figure out based upon the
00954     // injuring statement what the valid version is
00955     CODEREP *iv_def, *iv_use, *dummy_mult;
00956     Str_red()->Find_iv_and_mult( def, &iv_def, use,
00957               &iv_use, &dummy_mult );
00958     // need to make sure the iv it found matches which one
00959     // we're interested in
00960     if ( kid->Aux_id() == iv_def->Aux_id() ) {
00961       newcr->Set_opnd( i, iv_def );
00962     }
00963         }
00964       }
00965       break;
00966 
00967     case CK_CONST:
00968     case CK_RCONST:
00969     case CK_LDA:
00970       break;
00971 
00972     case CK_IVAR:
00973     default:
00974       Is_True(FALSE, ("unexpected CK_KIND."));
00975     }
00976   }
00977       }
00978       break;
00979     
00980     default:
00981       FmtAssert( FALSE,
00982   ("ESSA::Alloc_and_generate_injured_phi_res: unexpected") );
00983       return NULL;
00984   }
00985 
00986   // Trace new expr generated
00987   if (Tracing()) {
00988     fprintf(TFile,
00989       "ESSA::Alloc_and_generate_injured_phi_res for phi res in BB%d\n",
00990       def->Bb()->Id());
00991     newcr->Print(10, TFile);
00992   }
00993 
00994   return newcr;
00995 }
00996 
00997 //======================================================================
00998 //======================================================================
00999 
01000 void
01001 ESSA::Process_delayed_rename(EXP_OCCURS *use, CODEREP *real_occ) const
01002 {
01003   Is_True(use->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR, 
01004     ("ESSA::Process_delayed_rename: not a phi occur."));
01005   EXP_PHI *exp_phi = use->Exp_phi();
01006 
01007   BOOL is_const_lpre = inCODEKIND(Cur_e_expr()->Kind(), CK_LDA|CK_RCONST|CK_CONST);
01008 
01009   for (INT opnd_num = 0; opnd_num < exp_phi->Opnd_count(); opnd_num++) {
01010     if (exp_phi->Delayed_rename(opnd_num)) {
01011       exp_phi->Reset_delayed_rename(opnd_num);
01012       EXP_OCCURS *def = exp_phi->Opnd(opnd_num);
01013 
01014       CODEREP *newcr = Etable()->
01015   Alloc_and_generate_cur_expr(real_occ, use->Bb(),
01016             opnd_num, Etable()->Per_expr_pool(),
01017             FALSE /* do not convert zero ver */);
01018 
01019       switch (def->Occ_kind()) {
01020       case EXP_OCCURS::OCC_PHI_OCCUR:
01021   {
01022     // come up with a use that looks valid
01023     EXP_OCCURS *tmp_use = exp_phi->Pred(opnd_num);
01024     Is_True(tmp_use->Occ_kind() == EXP_OCCURS::OCC_PHI_PRED_OCCUR,
01025       ("ESSA::Process_delayed_rename: Pred not phi-pred occur."));
01026     tmp_use->Set_occurrence( newcr );
01027 
01028     if (is_const_lpre ||
01029         Same_e_version_phi_result(def, newcr, tmp_use) ) {
01030 
01031       // transfer the injured flag to the phi 
01032       if (tmp_use->Injured_occ()) {
01033         tmp_use->Reset_injured_occ();
01034         exp_phi->Set_injured(opnd_num);
01035       }
01036 
01037       if (def->Occurrence() == NULL) {
01038 
01039         // propagate the current version to the phi result
01040         if ( exp_phi->Injured(opnd_num) ) {
01041     // injured phi operand, so need to come up with valid
01042     // phi result with correct versions
01043     newcr = Alloc_and_generate_injured_phi_res( def, 
01044       exp_phi->Pred(opnd_num), Etable()->Per_expr_pool());
01045         }
01046         def->Set_occurrence(newcr);
01047         Process_delayed_rename(def, newcr);
01048       }
01049 #ifdef Is_True_On
01050       Worklist()->Inc_dense_ssa_count();
01051 #endif
01052     } else {
01053       // Notice that if a (phi_result, phi_opnd) is delayed, there
01054       // must be no real occ between them, so it is ok to set 
01055       // not down safe.
01056       def->Exp_phi()->Set_not_down_safe();
01057       exp_phi->Set_opnd(opnd_num, NULL);
01058     }
01059   }
01060   break;
01061       case EXP_OCCURS::OCC_REAL_OCCUR:
01062   {
01063     BOOL injured = FALSE;
01064     if ( is_const_lpre ||
01065         Same_e_version_real_occ_phi_opnd
01066         (def, use->Bb(), opnd_num, newcr, &injured) )
01067     {
01068       EXP_OCCURS *tmp_use = exp_phi->Pred(opnd_num);
01069       exp_phi->Set_has_real_occ(opnd_num);
01070       if (injured || def->Injured_occ())
01071         exp_phi->Set_injured(opnd_num);
01072       if ((injured || def->Injured_occ()) && 
01073     ! def->Occurrence()->Match(newcr)) {
01074         tmp_use->Set_occurrence(newcr);         // update Phi_pred occurrence
01075       } else {
01076         tmp_use->Set_occurrence(def->Occurrence());        // update Phi_pred occurrence
01077       }
01078       // this real occ is defined by a phi
01079       if (def->Def_occur() != NULL)
01080         exp_phi->Set_opnd(opnd_num, def->Def_occur());
01081       else
01082         exp_phi->Set_opnd(opnd_num, def);
01083 #ifdef Is_True_On
01084       Worklist()->Inc_dense_ssa_count();
01085 #endif
01086     } else {
01087       exp_phi->Set_opnd(opnd_num, NULL);  
01088     }
01089   }
01090   break;
01091       default:
01092   Is_True(FALSE, ("unexpected occ_kind."));
01093       }
01094     }
01095   }
01096 }
01097 
01098 
01099 //  Pass1  Links up phi opnds to its potential def and
01100 //      renames the phi results and real occur
01101 //  Pass2  renames the phi opnd and phi result links.
01102 //
01103 void
01104 ESSA::Rename(void)
01105 {
01106   // Verify that the worklist Cur_e_expr() is in an acceptable form.
01107 #ifdef Is_True_On
01108   const CODEREP *cr = Cur_e_expr();
01109   switch (cr->Kind()) {
01110   case CK_VAR:
01111     break;
01112   case CK_IVAR:
01113     {
01114       Is_True(OPCODE_operator(cr->Op()) != OPR_PARM,("opr_parm not allowed."));
01115       const CODEREP *addr = cr->Ilod_base() ? cr->Ilod_base():cr->Istr_base();
01116       Is_True(addr->Kind() == CK_VAR ||
01117         addr->Kind() == CK_CONST ||
01118         addr->Kind() == CK_RCONST ||
01119         addr->Kind() == CK_LDA, ("expr form not acceptable."));
01120     }
01121     break;
01122   case CK_OP:
01123     {
01124       for (INT i = 0; i < cr->Kid_count(); i++) {
01125   CODEREP *kid = cr->Opnd(i);
01126   Is_True((kid->Kind() == CK_IVAR &&
01127      OPCODE_operator(kid->Op()) == OPR_PARM) ||
01128     kid->Kind() == CK_VAR ||
01129     kid->Kind() == CK_CONST ||
01130     kid->Kind() == CK_RCONST ||
01131     kid->Kind() == CK_LDA, ("expr form not acceptable."));
01132   if (kid->Kind() == CK_IVAR && OPCODE_operator(kid->Op()) == OPR_PARM)
01133       Is_True(kid->Ilod_base()->Kind() == CK_VAR ||
01134         kid->Ilod_base()->Kind() == CK_CONST ||
01135         kid->Ilod_base()->Kind() == CK_RCONST ||
01136         kid->Ilod_base()->Kind() == CK_LDA,
01137         ("expr form not acceptable."));
01138       }
01139     }
01140     break;
01141   case CK_LDA:
01142   case CK_RCONST:
01143   case CK_CONST:
01144     Is_True(Etable()->Pre_kind() != PK_EPRE, ("const is not acceptable in EPRE"));
01145     break;
01146   default:
01147     Is_True(FALSE, ("expr form not acceptable."));
01148   }
01149 #endif
01150 
01151   BOOL is_const_lpre = inCODEKIND(Cur_e_expr()->Kind(), CK_LDA|CK_RCONST|CK_CONST);
01152 
01153   // Set initial e-version to 1.
01154   Worklist()->Init_e_version();
01155 
01156   // Empty the stack
01157   Stack()->Clear();
01158 
01159   // Iterate over the occurences list in dominator preorder
01160   EXP_ALL_OCCURS_ITER exp_occ_iter(Worklist()->Real_occurs().Head(),
01161            _etable->Lftr() ? 
01162            _etable->Lftr()->Exp_hash(Worklist()) :
01163            NULL,
01164            Worklist()->Phi_occurs().Head(),
01165            Worklist()->Phi_pred_occurs().Head(),
01166            _etable->Exit_occurs().Head());
01167   EXP_OCCURS *occur;
01168   FOR_ALL_NODE(occur, exp_occ_iter, Init()) {
01169     // unwind the stack until all EXP_OCCUR on the stack dominates
01170     // the current EXP_OCCUR
01171     while (!Stack()->Is_Empty() &&
01172      !Stack()->Top()->Bb()->Dominates(occur->Bb())) 
01173       Stack()->Pop();
01174 
01175     if (Stack()->Is_Empty() || Stack()->Top() == NULL) {
01176 
01177       // TOS is nil
01178       switch (occur->Occ_kind()) {
01179       case EXP_OCCURS::OCC_PHI_OCCUR:        // create new ver
01180   Is_True(occur->Exp_phi()->Result() == occur,
01181     ("OCC_PHI_OCCUR phi result is wrong."));
01182 #ifdef Is_True_On
01183   Worklist()->Inc_phi_count();
01184   Worklist()->Inc_optimistic_ssa_count(occur->Bb()->Pred()->Len());
01185 #endif
01186   Create_new_version(occur);           
01187   break;
01188       case EXP_OCCURS::OCC_REAL_OCCUR:     
01189 #ifdef Is_True_On
01190   Worklist()->Inc_realocc_count();
01191   if (occur->Mult_real())
01192     Worklist()->Inc_realocc_count();
01193 #endif
01194   Create_new_version(occur);           
01195   break;
01196       case EXP_OCCURS::OCC_PHI_PRED_OCCUR:   // do nothing
01197       case EXP_OCCURS::OCC_EXIT_OCCUR:       // do nothing
01198   break;
01199       case EXP_OCCURS::OCC_COMP_OCCUR:       // reset comp version (shared)
01200   occur->Set_e_version(EXP_OCCURS::ILLEGAL_E_VERSION);
01201   break;
01202       default:
01203   Is_True(FALSE, ("ESSA::Rename, unknown occurrence kind: %d",
01204       occur->Occ_kind()));
01205   break;
01206       }
01207 
01208     } else {      // TOS is non-nil
01209 
01210       switch (occur->Occ_kind()) {
01211       case EXP_OCCURS::OCC_REAL_OCCUR:
01212   {
01213     // UGLINESS: The following doesn't really have anything to
01214     // do with SSAPRE renaming. Rename was just a convenient
01215     // place to put this initialization of the LOOP_HAS_REAL_OCC
01216     // flag. In principle, any pass before the CodeMotion step
01217     // would work.
01218     //
01219     // If the current expression is a candidate for strength
01220     // reduction in the presence of LFTR, we note that the
01221     // innermost loop containing *occur contains a real
01222     // occurrence. Comparisons whose innermost containing loop
01223     // does not contain a real occurrence whose innermost
01224     // containing loop is the same as the one for the comparison
01225     // will not be eligible for LFTR. This condition is
01226     // established to guarantee termination of
01227     // LFTR/SR/OCOPY/2OE. See the comments for
01228     // LFTR::Replace_comparison (in opt_lftr2.cxx) for more
01229     // details.
01230     if (WOPT_Enable_New_SR &&
01231         Etable()->Lftr()->Lftr_on() &&
01232         Str_red()->Candidate_opc(occur->Occurrence()->Op())) {
01233       BB_LOOP *loop = occur->Bb()->Innermost();
01234       if (loop != NULL) {
01235         Is_Trace(Etable()->Tracing(), (TFile, "Real occ: "));
01236         Is_Trace_cmd(Etable()->Tracing(), occur->Print(TFile));
01237         Is_Trace(Etable()->Tracing(), (TFile, " in loop headed "
01238                "at BB%d\n",
01239                loop->Header()->Id()));
01240         loop->Set_flag(LOOP_HAS_REAL_OCC);
01241       }
01242     }
01243     // End of UGLINESS. Back to your regularly-scheduled
01244     // renaming.
01245 
01246 #ifdef Is_True_On
01247     Worklist()->Inc_realocc_count();
01248     if (occur->Mult_real())
01249       Worklist()->Inc_realocc_count();
01250 #endif
01251 
01252     EXP_OCCURS *tos = Stack()->Top();
01253     switch (tos->Occ_kind()) {
01254     case EXP_OCCURS::OCC_REAL_OCCUR:
01255       if ( is_const_lpre || 
01256     ( !occur->Occurs_as_lvalue() &&
01257       Same_e_version_real_occ_real_occ(tos, occur) ) ) {
01258         occur->Set_e_version(tos->E_version());
01259         occur->Set_def_occur(tos->Def_occur() != NULL ? tos->Def_occur() : tos);
01260 #ifdef Is_True_On
01261         Worklist()->Inc_ssa_edge_count();
01262 #endif
01263       } else
01264         Create_new_version(occur);
01265       break;
01266     case EXP_OCCURS::OCC_PHI_OCCUR:
01267       if ( is_const_lpre ||
01268     ( !occur->Occurs_as_lvalue() &&
01269      Same_e_version_phi_result(tos, occur->Occurrence(), occur) ) )
01270       {
01271         occur->Set_e_version(tos->E_version());
01272         occur->Set_def_occur(tos);
01273 
01274         if ( !occur->Injured_occ() ) {
01275     tos->Set_occurrence(occur->Occurrence());
01276         }
01277         else {
01278     // the use is injured, so we need to come up with a
01279     // valid cr for this phi result.
01280     CODEREP *new_phi_res = Alloc_and_generate_injured_phi_res(
01281       tos, occur, Etable()->Per_expr_pool());
01282     tos->Set_occurrence( new_phi_res );
01283         }
01284         Stack()->Push(occur);   // push real occ to compute downsafety
01285 #ifdef Is_True_On
01286         Worklist()->Inc_ssa_edge_count();
01287 #endif
01288       } else {
01289         tos->Exp_phi()->Set_not_down_safe();
01290         Create_new_version(occur);
01291       }
01292       break;
01293     default:
01294       Is_True(FALSE, ("unexpected EXP_OCCURS kind."));
01295     }
01296   }
01297   break;
01298 
01299       case EXP_OCCURS::OCC_PHI_OCCUR:
01300   Is_True(occur->Exp_phi()->Result() == occur,
01301     ("OCC_PHI_OCCUR phi result is wrong."));
01302 #ifdef Is_True_On
01303   Worklist()->Inc_phi_count();
01304   Worklist()->Inc_optimistic_ssa_count(occur->Bb()->Pred()->Len());
01305 #endif
01306   Create_new_version(occur);
01307   break;
01308 
01309       case EXP_OCCURS::OCC_PHI_PRED_OCCUR:
01310   {
01311     BB_LIST_ITER bb_iter;
01312     BOOL updated = FALSE;  // for verification only
01313     EXP_OCCURS *tos = Stack()->Top();
01314     BB_NODE *use_bb;                    // BB of the EXP_PHI
01315     BB_NODE *pred_bb = occur->Bb();     // BB of the PHI_PRED node
01316 
01317     // A PHI_PRED to PHI mapping is a 1-many mapping!
01318     // So find all EXP_PHI that needs to be updated.
01319     //
01320     //  Notice that tos might be a real occurrence, and the real occurrence
01321     //  might be a use and points to another "def".
01322     //
01323     //  DO NOT CHANGE tos to the "def".  This is required for downsafety correctness.
01324     //
01325 
01326     FOR_ALL_ELEM (use_bb, bb_iter, Init(pred_bb->Succ())) {
01327       EXP_PHI *exp_phi = _etable->Lookup_exp_phi(use_bb, Cur_e_expr());
01328       if (exp_phi != NULL) {
01329         INT opnd_num = use_bb->Pred()->Pos(pred_bb);
01330         updated = TRUE;
01331         exp_phi->Set_opnd(opnd_num, (EXP_OCCURS *) tos);
01332         exp_phi->Set_delayed_rename(opnd_num);
01333 #ifdef Is_True_On
01334         Worklist()->Inc_ssa_edge_count();
01335 #endif
01336       }
01337     }
01338     Is_True(updated,
01339       ("OCC_PHI_OPND_OCC has no matching phi node for PREDBB%d.",
01340        pred_bb->Id()));
01341   }
01342   break;
01343       
01344       case EXP_OCCURS::OCC_EXIT_OCCUR:
01345   Is_True(occur->Bb()->Kind() == BB_EXIT, ("not an exit BB."));
01346   Reset_tos_downsafe();
01347   break;
01348 
01349       case EXP_OCCURS::OCC_COMP_OCCUR:
01350   occur->Set_e_version(Stack()->Top()->E_version());
01351   break;
01352 
01353       default:
01354   Is_True(FALSE, ("ESSA::Rename, unknown occurrence kind: %d",
01355       occur->Occ_kind()));
01356   break;
01357       }
01358     }
01359   }
01360 
01361   // TODO: need to rewrite the following with a real iterator
01362   //
01363   EXP_OCCURS_ITER    phi_occur_iter;
01364 
01365   FOR_ALL_NODE (occur, phi_occur_iter, Init(Worklist()->Phi_occurs().Head())) {
01366     if (occur->Occurrence() != NULL)
01367       Process_delayed_rename(occur, occur->Occurrence());
01368   }
01369   
01370   FOR_ALL_NODE (occur, phi_occur_iter, Init(Worklist()->Phi_occurs().Head())) {
01371     EXP_PHI *exp_phi = occur->Exp_phi();
01372     for (INT i = 0; i < exp_phi->Opnd_count(); i++) {
01373       if (exp_phi->Delayed_rename(i)) {
01374   EXP_OCCURS *def = exp_phi->Opnd(i);
01375   // Notice that if a (phi_result, phi_opnd) is delayed, there must
01376   // be no real occ between them, so it is ok to set not down safe.
01377   if (def && def->Occ_kind() == EXP_OCCURS::OCC_PHI_OCCUR) 
01378     def->Exp_phi()->Set_not_down_safe();
01379   exp_phi->Set_opnd(i, NULL);
01380       }
01381     }
01382   }
01383 }
01384 
01385 ESSA::ESSA(ETABLE *etable, EXP_WORKLST *worklist, ALIAS_RULE *ar)
01386 {
01387   OPT_POOL_Initialize(&_mpool, "pre rename mempool", FALSE, -1);
01388   OPT_POOL_Push(&_mpool, -1);
01389 
01390   _etable = etable;
01391   _str_red = etable->Str_red();
01392   _opt_stab = etable->Opt_stab();
01393   _worklist = worklist;
01394   _rule = ar;
01395   _cur_e_expr = worklist->Real_occurs().Head()->Occurrence();
01396   _stack = CXX_NEW(STACK<EXP_OCCURS *>(&_mpool), &_mpool);
01397 }
01398 
01399 ESSA::~ESSA(void)
01400 {
01401   OPT_POOL_Pop(&_mpool, -1);
01402   OPT_POOL_Delete(&_mpool, -1);
01403 }
01404 
01405 
01406 // ======================================================================
01407 // Expr SSA rename
01408 // ======================================================================
01409 void
01410 EXP_WORKLST::Rename_expression(ETABLE *etable)
01411 {
01412   ESSA essa(etable, this, etable->Arule());
01413   essa.Rename();
01414 
01415   Is_Trace(etable->Tracing(),(TFile,
01416       "====== After ETABLE::Rename_expression ======\n"));
01417   Is_Trace_cmd(etable->Tracing(),Print(TFile));
01418 }