//-*-c++-*- // ==================================================================== // ==================================================================== // // Module: opt_etable.h // $Revision: 1.3 $ // $Date: 2004/10/28 22:54:11 $ // $Author: wychen $ // $Source: bitbucket.org:berkeleylab/upc-translator.git/open64/osprey1.0/be/opt/opt_etable.h $ // // ==================================================================== // // Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. // // This program is free software; you can redistribute it and/or modify // it under the terms of version 2 of the GNU General Public License as // published by the Free Software Foundation. // // This program is distributed in the hope that it would be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. // // Further, this software is distributed without any warranty that it // is free of the rightful claim of any third person regarding // infringement or the like. Any license provided herein, whether // implied or otherwise, applies only to this software file. Patent // licenses, if any, provided herein do not apply to combinations of // this program with other software, or any other product whatsoever. // // You should have received a copy of the GNU General Public License // along with this program; if not, write the Free Software Foundation, // Inc., 59 Temple Place - Suite 330, Boston MA 02111-1307, USA. // // Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, // Mountain View, CA 94043, or: // // http://www.sgi.com // // For further information regarding this notice, see: // // http://oss.sgi.com/projects/GenInfo/NoticeExplan // // ==================================================================== // // Description: // // Data structures and functions for PRE optimization based on // SSA. // // EXP_PHI: expression phi function; // the body of this class contains: // // _e_num: assigned expression number // _size: number of operand + 1 for the result // _bb: the basic block it belongs to // _vec: a fix length array contains _size of elements // each element contains: // // _occ: the expression occurrence (EXP_OCCURS) node // _flags: could contain multiple flags in EXP_PHI_FLAGS // _uses: holds a list of expression phi nodes that use // (as operand) the result of this phi. // // // Memory Management for major classes: // // Memory pool: _etable_pool // The routine that instantiate the ETABLE has to // create a dedicated memory pool and pushed // before passing it to ETABLE constructor. // // EXP_PHI: the node itself is recyclable after each // expression is processed. Since the lifecycle // of any EXP_PHI node is the same as the time we // process that expression, the MEM_Push/Pop works // just fine. // // EXP_OCCURS: recycled by EXP_WORKLST::Remove_occurs. All // extended real occurrences(real + phi result) // and all phi occurrences are freed by // ETABLE::Add_to_occ_freelist(). // // EXP_WORKLST: the node itself is an array element of the // segmented array ETABLE::_exp_worklst. These // nodes are not freed though out this phase, and // it is freed by the memory pool pop at the // ETABLE instantiator. // // ==================================================================== // ==================================================================== #ifndef opt_etable_INCLUDED #define opt_etable_INCLUDED "opt_etable.h" #include "defs.h" #include "mempool.h" #include "cxx_template.h" #include "opt_defs.h" #include "opt_array.h" #include "cxx_base.h" #include "opt_base.h" #include "bb_node_set.h" #include "opt_htable.h" #include "opt_vnfre.h" class ALIAS_RULE; class BB_NODE; class BB_NODE_SET; class CODEMAP; class CODEREP; class COMP_UNIT; class CFG; class ETABLE; class EXP_OCCURS; class EXP_ALL_REAL_ITER; class EXP_WORKLST; class LFTR; class OPT_STAB; class PHI_NODE; class STMTREP; class STR_RED; class E_VER_TAB; // Private to availability/insertion step class REHASH_CACHE_LIST; // list of rehashed expr class EXP_HOISTING; class SSU; class OCCUR_REPLACEMENT; // Private to opt_etable.cxx (for codemotion) enum PRE_KIND { PK_EPRE = 0, PK_LPRE = 1, PK_SPRE = 2, PK_VNFRE = 3, // Value numbering full redundancy elimination }; extern const char *pre_kind_name(PRE_KIND); class REHASH_INFO; template class ID_MAP; class EXP_OCCURS_LIST : public SLIST_NODE { private: EXP_OCCURS *_node; mINT32 _opnd_idx; EXP_OCCURS_LIST(const EXP_OCCURS_LIST&); EXP_OCCURS_LIST& operator = (const EXP_OCCURS_LIST&); public: EXP_OCCURS_LIST(void) { } EXP_OCCURS_LIST(EXP_OCCURS *node, mINT32 i) { Init(node, i); } ~EXP_OCCURS_LIST(void) { } DECLARE_SLIST_NODE_CLASS(EXP_OCCURS_LIST) void Init(EXP_OCCURS *nd, mINT32 i) { _node = nd; _opnd_idx = i; } EXP_OCCURS *Node(void) const { return _node; } mINT32 Opnd_idx(void) const { return _opnd_idx; } }; class USE_LIST_ENTRY : public SLIST_NODE { private: EXP_PHI *_node; mINT32 _opnd_idx; USE_LIST_ENTRY(const USE_LIST_ENTRY&); USE_LIST_ENTRY& operator = (const USE_LIST_ENTRY&); public: USE_LIST_ENTRY(void) { } USE_LIST_ENTRY(EXP_PHI *node, mINT32 i) { Init(node, i); } ~USE_LIST_ENTRY(void) { } DECLARE_SLIST_NODE_CLASS(USE_LIST_ENTRY) void Init(EXP_PHI *node, mINT32 i) { _node = node; _opnd_idx = i; } EXP_PHI *Node(void) const { return _node; } mINT32 Opnd_idx(void) const { return _opnd_idx; } }; class USE_LIST_ITER : public SLIST_ITER { public: // Declared by hand since DECLARE_SLIST_ITER_CLASS requires // extraneous garbage. USE_LIST_ITER(USE_LIST_ENTRY *nd) { SLIST_ITER::Init(nd); } USE_LIST_ITER(void) { SLIST_ITER::Init(); } USE_LIST_ENTRY *First(void) { return (USE_LIST_ENTRY *) SLIST_ITER::First(); } USE_LIST_ENTRY *Next(void) { return (USE_LIST_ENTRY *) SLIST_ITER::Next(); } }; class EXP_PHI : public SLIST_NODE { DECLARE_SLIST_NODE_CLASS(EXP_PHI) friend class ETABLE; public: // Current flag semantics: // // EPOF_HAS_REAL_OCC means that the corresponding phi operand has a // real occurrence on the path in the CFG from its point of // definition to this use as a phi operand. // // EPOF_DELAYED_RENAME means the renaming step for this opnd has // been delayed. (this bit should be not visible outside step 3). // // EPOF_INJURED means the phi operand is "injured" for strength- // reduction purposes. enum EXP_PHI_OPND_FLAGS { EPOF_NONE = 0x0, EPOF_HAS_REAL_OCC = 0x1, EPOF_DELAYED_RENAME = 0x2, EPOF_INJURED = 0x4, EPOF_OPND_STOPS = 0x8, EPOF_NULL_SSU_VERSION = 0x10,// set by SPRE iphi insertion and used in // SPRE SSU renaming phase }; // EPF_I_A_SEEN is used only within Identity_assignment in the // phi result to mark the phi as being processed, to avoid infinite // loop and to return a cached answer if the result is already known. // // EPF_NOT_DOWN_SAFE means that the phi's block in the CFG is not // down-safe, so insertion along the CFG arcs coming into this // phi is not safe (because the expression is not fully // anticipated at this point in the CFG). This flag is set in // step 3 (opt_essa.cxx) and step 4 (opt_eant.cxx), and is used in // step 4 (opt_eant.cxx) and step 5 (opt_epre.cxx). // // EPF_IDENTITY means that a variable phi for the temp need not be // generated in correspondence with this EXP_PHI. // // EPF_IDENT_INJURED is set for identity phi's in the SSA // minimization step whenever an injury repair is required between // the occurrence the present phi is Identical_to() and the present // phi. // // EPF_KNOW_REPLACEMENT is set for identity phi's in the SSA // minimization step once we know what the phi is Identical_to(). enum EXP_PHI_FLAGS { EPF_NONE = 0x0, EPF_I_A_SEEN = 0x1, EPF_NOT_DOWN_SAFE = 0x2, EPF_IS_LIVE = 0x4, // expr is PANT at this phi EPF_NOT_USER_AVAIL = 0x8, // expr is !AV at this phi EPF_CANT_BE_AVAIL = 0x10, // this phi result can't be made available EPF_STOPS = 0x20, // can't insert later than this phi EPF_IDENTITY = 0x40, // this phi need not become a temp phi EPF_KNOW_REPLACEMENT = 0x80, // this identity phi's replacement is known EPF_IDENT_INJURED = 0x100, // this phi's identity is injured EPF_REVERSE_PHI = 0x400, // used only in SPRE to represent SSU EPF_DEAD_PHI_REGION = 0x800, // used only in SPRE to prevent insertions in such regions EPF_PARTIAL_AVAIL = 0x1000, EPF_LOCAL_PRED = 0x2000 // used in local phases for various reasons }; private: EXP_ID _e_num; mINT32 _opnd_count; UINT16 _flags; UINT16 _saved_flags; union { EXP_OCCURS *_cached_identity_assignment; EXP_OCCURS *_identical_to; }; BB_NODE *_bb; EXP_OCCURS *_result; class PHI_ELEM { friend class EXP_PHI; EXP_OCCURS *_occ; UINT32 _flags; EXP_OCCURS *_pred_or_succ; // pointer to its predecessors if it is an EXP_PHI // pointer to its succ if it is an IPHI }; PHI_ELEM *_vec; // _uses: holds a list of phi occurrences that are // uses of the phi result of this occurrence. USE_LIST_ENTRY *_uses; // used only during // EXP_WORKLST::Compute_forward_attributes() and // EXP_WORKLST::Minimize_temp_ssa() EXP_PHI(void); EXP_PHI(const EXP_PHI&); EXP_PHI& operator = (const EXP_PHI&); void Set_result(EXP_OCCURS *o){ _result = o; } void Set_cached_identity_assignment(EXP_OCCURS *occ) { _cached_identity_assignment = occ; } EXP_OCCURS *Cached_identity_assignment(void) { return _cached_identity_assignment; } void Set_flag(EXP_PHI_FLAGS bit) { _flags |= bit; } void Reset_flag(EXP_PHI_FLAGS bit) { _flags &= ~bit; } BOOL Is_flag_set(EXP_PHI_FLAGS bit) const { return _flags & bit; } public: INT32 id; // unique exp-phi id to support feedback PRE EXP_PHI(EXP_ID e_num, INT opnd_count, BB_NODE *bb, MEM_POOL *pool) { Init(e_num,opnd_count,bb,pool); } ~EXP_PHI(void) { } void Init(EXP_ID e_num, INT size, BB_NODE *bb, MEM_POOL *pool); EXP_ID E_num(void) const { return _e_num; } EXP_OCCURS *Result(void) const { return _result; } EXP_OCCURS *Opnd(INT i) const { return _vec[i]._occ; } EXP_OCCURS *Pred(INT i) const { return _vec[i]._pred_or_succ; } EXP_OCCURS *Succ(INT i) const { return _vec[i]._pred_or_succ; } void Set_opnd(INT i, EXP_OCCURS *occ){ _vec[i]._occ = occ; } void Set_pred(INT i, EXP_OCCURS *occ){ _vec[i]._pred_or_succ = occ; } void Set_succ(INT i, EXP_OCCURS *occ){ _vec[i]._pred_or_succ = occ; } INT Opnd_count(void) const { return _opnd_count; } BB_NODE *Bb(void) const { return _bb; } void Set_not_down_safe(void) { Set_flag(EPF_NOT_DOWN_SAFE); } void Reset_not_down_safe(void){ Reset_flag(EPF_NOT_DOWN_SAFE); } BOOL Not_down_safe(void) const { return Is_flag_set(EPF_NOT_DOWN_SAFE); } void Set_not_user_avail(void) { Set_flag(EPF_NOT_USER_AVAIL); } BOOL Not_user_avail(void) const { return Is_flag_set(EPF_NOT_USER_AVAIL); } void Set_cant_be_avail(void) { Set_flag(EPF_CANT_BE_AVAIL); } BOOL Cant_be_avail(void) const { return Is_flag_set(EPF_CANT_BE_AVAIL); } void Set_live(void) { Set_flag(EPF_IS_LIVE); } BOOL Is_live(void) const { // return Is_flag_set(EPF_IS_LIVE); return TRUE; } void Set_has_real_occ(INT i) { _vec[i]._flags |= EPOF_HAS_REAL_OCC; } BOOL Has_real_occ(INT i) const { return (_vec[i]._flags & EPOF_HAS_REAL_OCC); } void Set_identity(void) { Set_flag(EPF_IDENTITY); } void Reset_identity(void) { Reset_flag(EPF_IDENTITY); } BOOL Identity(void) const { return Is_flag_set(EPF_IDENTITY); } void Set_reverse_phi(void) { Set_flag(EPF_REVERSE_PHI); } BOOL Reverse_phi(void) const { return Is_flag_set(EPF_REVERSE_PHI); } void Set_identical_to(EXP_OCCURS *const occ) { _identical_to = occ; } EXP_OCCURS *Identical_to(void) const { Is_True(Will_b_avail() && Identity(), ("EXP_PHI::Identical_to: availability and " "identity are required")); return _identical_to; } void Set_identity_injured(void) { Set_flag(EPF_IDENT_INJURED); } BOOL Identity_injured(void) const { return Is_flag_set(EPF_IDENT_INJURED); } void Set_replacing_occur_known(void) { Set_flag(EPF_KNOW_REPLACEMENT); } BOOL Replacing_occur_known(void) const { return Is_flag_set(EPF_KNOW_REPLACEMENT); } void Set_I_A_Seen(void) { Set_flag(EPF_I_A_SEEN); } void Reset_I_A_Seen(void) { Reset_flag(EPF_I_A_SEEN); } BOOL I_A_Seen(void)const { return Is_flag_set(EPF_I_A_SEEN); } void Set_stops(void) { Set_flag(EPF_STOPS); } BOOL Stops(void) const { return Is_flag_set(EPF_STOPS); } void Set_dead_phi_region(void) { Set_flag(EPF_DEAD_PHI_REGION); } BOOL Dead_phi_region(void) const { return Is_flag_set(EPF_DEAD_PHI_REGION); } BOOL Will_b_avail(void) const { return !Cant_be_avail() && Stops(); } BOOL Partial_avail() const { return Is_flag_set(EPF_PARTIAL_AVAIL); } void Set_partial_avail() { Set_flag(EPF_PARTIAL_AVAIL); } void Set_injured(INT i) { _vec[i]._flags |= EPOF_INJURED; } void Reset_injured(INT i) { _vec[i]._flags &= ~EPOF_INJURED; } BOOL Injured(INT i) const { return (_vec[i]._flags & EPOF_INJURED); } BOOL Any_opnd_injured(void) const; void Set_has_real_use() {Set_flag(EPF_LOCAL_PRED);} void Reset_has_real_use() {Reset_flag(EPF_LOCAL_PRED);} BOOL Has_real_use() {return Is_flag_set(EPF_LOCAL_PRED);} USE_LIST_ENTRY *Uses(void) const { return _uses; } void Set_uses(USE_LIST_ENTRY *use) { _uses = use; } void Add_use(EXP_PHI *use, INT opnd_idx, MEM_POOL *pool) { USE_LIST_ENTRY *new_ll_node = CXX_NEW(USE_LIST_ENTRY(use, opnd_idx), pool); if (Uses() == NULL) { Set_uses(new_ll_node); } else { Uses()->Insert_After(new_ll_node); } } BOOL Delayed_rename(INT i) const { return (_vec[i]._flags & EPOF_DELAYED_RENAME); } void Set_delayed_rename(INT i){ _vec[i]._flags |= EPOF_DELAYED_RENAME; } void Reset_delayed_rename(INT i) { _vec[i]._flags &= ~EPOF_DELAYED_RENAME; } void Set_opnd_stops(INT i) { _vec[i]._flags |= EPOF_OPND_STOPS; } BOOL Opnd_stops(INT i) const { return (_vec[i]._flags & EPOF_OPND_STOPS); } void Set_null_ssu_version(INT i) { _vec[i]._flags |= EPOF_NULL_SSU_VERSION; } BOOL Null_ssu_version(INT i) const { return (_vec[i]._flags & EPOF_NULL_SSU_VERSION); } BOOL Identity_assignment(BOOL &, EXP_PHI *, BOOL, STACK &); BOOL Need_insertion(INT) const; void Save_flags() { _saved_flags = _flags; } void Restore_flags() { _flags =_saved_flags; } // used in CANT_BE_AVAIL_SEARCH, after USER_AVAIL_SEARCH has been finished BOOL Phi_opnd_not_avail(INT) const; void Print(FILE *fp=stderr, BOOL show_preds = TRUE) const; }; class EXP_PHI_LIST : public SLIST { DECLARE_SLIST_CLASS (EXP_PHI_LIST, EXP_PHI) private: INT32 _out_degree; // for SPRE EXP_PHI_LIST(const EXP_PHI_LIST&); EXP_PHI_LIST& operator = (const EXP_PHI_LIST&); public: EXP_PHI_LIST(INT32 out_degree) { _out_degree = out_degree; } EXP_PHI_LIST(BB_NODE *bb); ~EXP_PHI_LIST(void) {} INT32 Out_degree() const { return _out_degree; } // Remove the i'th operand from the phi-nodes (0 is first opnd) void Remove_opnd(INT32 i); void Print(FILE *fp=stderr); }; class EXP_PHI_LIST_ITER : public SLIST_ITER { private: DECLARE_SLIST_ITER_CLASS (EXP_PHI_LIST_ITER, EXP_PHI, EXP_PHI_LIST) EXP_PHI_LIST_ITER(const EXP_PHI_LIST_ITER&); EXP_PHI_LIST_ITER& operator = (const EXP_PHI_LIST_ITER&); public: ~EXP_PHI_LIST_ITER(void) {} EXP_PHI *First_elem(void) { return First(); } EXP_PHI *Next_elem(void) { return Next(); } }; // ==================================================================== // EXP_OCCURS: This node represent one occurence of an expression as // the PRE candidate. Members of this class are: // _occurrence: the coderep node of this occurence. // _e_version: the version number assigned by rename phase // _temp_cr: coderep node of the temp corresponding to // _e_version // _enclosed_in: the enclosing statement, from where we // could find the BB it belongs to; or a // phi_node. // _kind: the kind of the occurrence // _flag: reserve the location for all kinds of // flags we might need. // _stmt_kid_num:for real occurrence, which kid of the // stmt has the occurrence // ==================================================================== class EXP_OCCURS : public SLIST_NODE { DECLARE_SLIST_NODE_CLASS( EXP_OCCURS ) private: // A note on flags and unions: Any flag or field that can pertain to // a real occurrence has the same meaning for a phi-pred occurrence // because the insertion scheme we use embeds inserted real // occurrences in phi-predecessors. enum OCC_FLAG { OCC_NONE = 0x000, OCC_MULT_REAL_OCCUR = 0x001, // multiple real occurrence in the same kid OCC_FAKE_STORE_OCCUR = 0x001,// used in SPRE to mark fake stores to locals // at CFG exit OCC_INSERTED_OCCUR = 0x002, // used only for OCC_PHI_PRED_OCCUR // kind; means that an insertion has // happened for the corresponding phi // operand. OVERLOADED: same bit as // OCC_CODEREP_OWNER. If you change // this overloading, make sure to // update the accessor functions, // too. OCC_CODEREP_OWNER = 0x002, // used only for OCC_REAL_OCCUR kind; // means this occurrence owns its // coderep and is allowed to // substitute without rehashing. // OVERLOADED: same bit as // OCC_INSERTED_OCCUR. If you change // this overloading, make sure to // update the accessor functions, // too. OCC_ENCL_STMT_SET = 0x004, // used only for OCC_PHI_PRED_OCCUR kind; // means this occurrence was a PRE // insertion and it didn't get // hoisted to a different place. OCC_AS_L_VALUE = 0x008, // occurrence of an ISTORE *p = ... in [EL]PRE // and r = x in SPRE OCC_REQUIRED_PRED = 0x008, // phi pred has a Will_b_avail() succ phi OCC_INJURED = 0x010, // used only for OCC_REAL_OCCUR kind; // modified by IV update statement OCC_DELETE_COMP = 0x020, // used only for OCC_REAL_OCCUR kind; // means this real occurrence will not // actually be computed in the // optimized program (load from temp) OCC_SAVE_TO_TEMP = 0x040, // used only for OCC_REAL_OCCUR kind // with OCC_DELETE_COMP == FALSE; means // this real occurrence will be saved // to a temp (preg) because its result // is used later. OCC_HOISTED = 0x080, // a hoisted occurrence OCC_REHASH_CHANGED = 0x100, // rehashing changed this inserted expr (CVT) OCC_FOR_SPRE = 0x200, // this node is used in SPRE phase OCC_OBSOLETE_COMPARISON = 0x400, // comp occur node is obsolete and is to be //ignored OCC_SUNK_L_VALUE = 0x800, // in LPRE, when doing live range shrinking; // if OCC_AS_L_VALUE is set, indicates the // sunk def; otherwise, indicates the first use // before which the sunk def is to be inserted }; UINT32 _kind:3; // the kind of occurence UINT32 _flag:13; // contains all kinds of flags UINT32 _stmt_kid_num:16; // for real occurrence, which kid // of the stmt has the occurrence UINT32 _saved_flags:13; union { CODEREP *_occurrence; // the occurence } _oc; IDTYPE _e_version:24; // the expression version number // Maximum representable rehash cost enum { OCC_REHASH_COST_LIMIT = 255 }; UINT32 _rehash_cost:8; // for real occurrences, a measure // of the cost of rehashing the // occurrence in the expression // tree. Currently, this is the // maximum depth in the expression // tree. union { EXP_OCCURS *_def_occur; // the OCC_PHI_OCCUR defines this // OCC_REAL_OCC node, used in step 3; // Also used in steps 5 and 6 for // a different purpose: set up by // step 5 to communicate the // available definition of each // real and comp occurrence to // step 6. CODEREP *_temp_cr; // coderep node of the temp; this field // is not allowed to be used whenver // _def_occur is set (i.e. the expression // occurrence is not a def); assertions // enforce this EXP_WORKLST *_spre_wk; // for SPRE only: point to worklist // node, and used by rename phase. // After rename phase, this field get // invalid value. } _temp; // corresponding to _e_version, used in step 6 union { STMTREP *_stmt; // inside this statement (real occ) EXP_PHI *_exp_phi; // defined by this phi node (phi occ) BB_NODE *_bb; // for exit occurrence or phi pred } _enclosed_in; EXP_OCCURS(const EXP_OCCURS&); EXP_OCCURS& operator = (const EXP_OCCURS&); void Reset_flag(void) { _flag = OCC_NONE; } void Reset_flag(OCC_FLAG f) { _flag = (_flag & (~f)); } void Set_flag(OCC_FLAG f) { _flag = (_flag|f); } BOOL Is_flag_set(OCC_FLAG f) const { return _flag & f; } public: // Don't change the order of the items in the following type // definition; the OCC_KIND ordering is used to distinguish // dominance for occurrences of different kinds within the same // block. To wit: PHI_OCCURs dominate REAL_OCCURs, which dominate // PHI_PRED_OCCURs and EXIT_OCCURs. COMP_OCCURs are a special case // since they can appear interspersed with REAL_OCCURs, and must be // distinguished by statement ordering within the block. enum OCC_KIND { OCC_UNKNOWN_OCCUR = 0, OCC_PHI_OCCUR = 1, // DO NOT CHANGE THE ORDER of phi, OCC_REAL_OCCUR = 2, // real, OCC_COMP_OCCUR = 3, // comparison occurrence for LFTR OCC_PHI_PRED_OCCUR = 4, // phi_pred OCC_EXIT_OCCUR = 5, // exit }; enum E_VERSION_VALUE { ILLEGAL_E_VERSION = 0, // illegal e-version }; EXP_OCCURS(CODEREP*, STMTREP*, EXP_PHI*, BOOL); void Init(void); EXP_OCCURS(void) { Init(); } ~EXP_OCCURS(void) { } OCC_KIND Occ_kind(void) const { return (OCC_KIND)_kind; } void Set_kind(OCC_KIND k) { _kind = k; } mINT16 Stmt_kid_num(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR, ("EXP_OCCURS::Stmt_kid_num: Must be real occ!")); return _stmt_kid_num; } CODEREP *Occurrence(void)const { return _oc._occurrence; } IDTYPE E_version(void) const { Is_True(Occ_kind() != OCC_PHI_PRED_OCCUR || Inserted_computation() || Sunk_lvalue(), ("EXP_OCCURS::E_version: Cannot be phi pred occ!")); return _e_version; } void Set_rehash_cost(UINT32 rehash_cost) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_UNKNOWN_OCCUR, // To allow initialization ("EXP_OCCURS::Set_rehash_cost: Must be real occ!")); if (rehash_cost <= OCC_REHASH_COST_LIMIT) { _rehash_cost = rehash_cost; } else { _rehash_cost = OCC_REHASH_COST_LIMIT; } } UINT32 Rehash_cost(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR, ("EXP_OCCURS::Rehash_cost: Must be real occ!")); return _rehash_cost; } CODEREP *Temp_cr(void) const { // It is not kosher to use temp_cr in the case of: Is_True(!Is_flag_set(OCC_DELETE_COMP) && (Occ_kind() == OCC_PHI_OCCUR || Is_flag_set(OCC_SAVE_TO_TEMP) || Is_flag_set(OCC_SUNK_L_VALUE) || _temp._temp_cr == NULL), // unless lftr is // on, in which case // we must return // NULL. ("EXP_OCCURS::Temp_cr: cannot use temp_cr field")); return _temp._temp_cr; } void Set_temp_cr(CODEREP *x) { Is_True(!Is_flag_set(OCC_DELETE_COMP) && !(Occ_kind() == OCC_REAL_OCCUR && !Is_flag_set(OCC_SAVE_TO_TEMP)), ("EXP_OCCURS::Set_temp_cr: cannot use temp_cr field")); _temp._temp_cr = x; } void Clear_temp_cr(void) { _temp._temp_cr = NULL; } // get a temporary code rep (or return existing one) CODEREP *Get_temp_cr(EXP_WORKLST *wk, CODEMAP *htable); EXP_OCCURS *Def_occur(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR || (Occ_kind() == OCC_PHI_PRED_OCCUR && Inserted_computation()), ("EXP_OCCURS::Def_occur: Must be real or comp occur.")); return _temp._def_occur; } void Set_def_occur(EXP_OCCURS *def_occur) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR || (Occ_kind() == OCC_PHI_PRED_OCCUR && def_occur == NULL), ("EXP_OCCURS::Set_def_occur: Must be real or comp occur.")); _temp._def_occur = def_occur; } // A member function to tell whether an occurrence is a real // available definition of its e-version, i.e., whether the // occurrence corresponds to a computation of the expression in the // optimized program. BOOL Is_real_avail_def(void) const { return ((Occ_kind() == OCC_PHI_PRED_OCCUR && (Inserted_computation() || Sunk_lvalue())) || (Occ_kind() == OCC_REAL_OCCUR && Def_occur() == NULL)); } EXP_WORKLST *Spre_wk(void) const { return _temp._spre_wk; } void Set_spre_wk(EXP_WORKLST *wk) { Is_True(Occ_kind() == OCC_PHI_OCCUR, ("EXP_OCCURS::Set_spre_wk: Must be phi occur")); _temp._spre_wk = wk; } STMTREP *Stmt(void) const; STMTREP *Enclosed_in_stmt(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR || (Occ_kind() == OCC_PHI_PRED_OCCUR && Inserted_computation() && Encl_stmt_set()), ("EXP_OCCURS::Enclosed_in_stmt: Must be real occ!")); return Stmt(); } STMTREP *Spre_store(void) const { return _enclosed_in._stmt; } STMTREP *Spre_kill_stmt(void) const { return _enclosed_in._stmt; } EXP_PHI *Exp_phi(void) const { Is_True(Occ_kind() == OCC_PHI_OCCUR, ("Must be phi occ!")); return _enclosed_in._exp_phi; } const BB_NODE *Enclosed_in_bb(void) const { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR || Occ_kind() == OCC_EXIT_OCCUR || (Occ_kind() == OCC_REAL_OCCUR && Inserted_computation()) || (Occ_kind() == OCC_REAL_OCCUR && Is_flag_set(OCC_HOISTED)), ("Must be fake or inserted real occ!")); return _enclosed_in._bb; } void Set_occurrence(CODEREP *cr) { _oc._occurrence = cr; } void Set_e_version(IDTYPE v) { _e_version = v; } void Set_stmt_kid_num(INT stmt_kid_num) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR || (Occ_kind() == OCC_PHI_PRED_OCCUR && Inserted_computation()), ("EXP_OCCURS::Set_stmt_kid_num: Must be real occ!")); FmtAssert((stmt_kid_num>=0) && (stmt_kid_num<=32767), ("Kid number < 0 or > 32767")); _stmt_kid_num = stmt_kid_num; } void Clear_flags(void) { Reset_flag(); } void Reset_enclosed_in(void) { _enclosed_in._stmt = NULL; } void Set_enclose_stmt(STMTREP *stmt) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_COMP_OCCUR || (Occ_kind() == OCC_PHI_PRED_OCCUR && (Inserted_computation() || Sunk_lvalue())), ("EXP_OCCURS::Set_enclose_stmt: Must be real occ!")); _enclosed_in._stmt = stmt; } void Set_exp_phi(EXP_PHI *exp_phi) { Is_True(Occ_kind() == OCC_PHI_OCCUR, ("EXP_OCCURS::Set_exp_phi: Must be phi occ!")); _enclosed_in._exp_phi = exp_phi; } void Set_enclose_bb(BB_NODE *bb) { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR || Occ_kind() == OCC_EXIT_OCCUR || (Occ_kind() == OCC_REAL_OCCUR && Inserted_computation()) || (Occ_kind() == OCC_REAL_OCCUR && Is_flag_set(OCC_HOISTED)), ("EXP_OCCURS::Set_enclose_bb: Must be fake or inserted" "real occ!")); _enclosed_in._bb = bb; } void Set_rehash_changed_expr(void) { Set_flag(OCC_REHASH_CHANGED); } void Set_mult_real(void) { Set_flag(OCC_MULT_REAL_OCCUR); } void Reset_mult_real(void) { Reset_flag(OCC_MULT_REAL_OCCUR); } void Set_fake_store(void) { Set_flag(OCC_FAKE_STORE_OCCUR); } void Reset_encl_stmt_set(void){ Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Reset_encl_stmt_set: bad occurrence kind")); Reset_flag(OCC_ENCL_STMT_SET); } void Set_encl_stmt_set(void) { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Set_encl_stmt_set: bad occurrence kind")); Set_flag(OCC_ENCL_STMT_SET); } void Reset_for_spre(void) { Reset_flag(OCC_FOR_SPRE); } void Set_for_spre(void) { Set_flag(OCC_FOR_SPRE); } void Set_delete_comp(void) { Set_flag(OCC_DELETE_COMP); } void Reset_save_to_temp(void) { Reset_flag(OCC_SAVE_TO_TEMP); } void Set_save_to_temp(void) { Set_flag(OCC_SAVE_TO_TEMP); } void Reset_inserted(void) { Reset_flag(OCC_INSERTED_OCCUR); } void Set_inserted(void) { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Set_inserted: bad occurrence kind")); Set_flag(OCC_INSERTED_OCCUR); } void Reset_t_ver_owns_coderep(void) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_PHI_OCCUR, ("EXP_OCCURS::Reset_t_ver_owns_coderep: bad occurrence kind")); Reset_flag(OCC_CODEREP_OWNER); } void Set_t_ver_owns_coderep(void) { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_PHI_OCCUR, ("EXP_OCCURS::Set_t_ver_owns_coderep: bad occurrence kind")); Set_flag(OCC_CODEREP_OWNER); } void Set_occurs_as_lvalue(void) { Is_True(OPERATOR_is_scalar_istore (Stmt()->Opr()) || OPERATOR_is_scalar_store (Stmt()->Opr()), ("EXP_OCCURS::Set_occurs_as_lvalue: not ISTORE")); Set_flag(OCC_AS_L_VALUE); } void Set_injured_occ(void) { // Someone in the know, please un-comment the following // assertion: // Is_True(Occ_kind() == OCC_COMP_OCCUR || // (Occ_kind() == OCC_REAL_OCCUR && // Delete_comp()), // ("EXP_OCCURS::Set_injured_occ: Occurrence must be " // "comparison or reload.")); Set_flag(OCC_INJURED); } void Reset_injured_occ(void) { Reset_flag(OCC_INJURED); } void Set_sunk_lvalue(void) { Set_flag(OCC_SUNK_L_VALUE); } BOOL Mult_real(void) const { return Is_flag_set (OCC_MULT_REAL_OCCUR); } BOOL Fake_store(void) const { return Is_flag_set (OCC_FAKE_STORE_OCCUR); } BOOL Encl_stmt_set(void) const{ return Is_flag_set (OCC_ENCL_STMT_SET); } BOOL For_spre(void) const { return Is_flag_set (OCC_FOR_SPRE); } BOOL Rehash_changed_expr(void) const { return Is_flag_set (OCC_REHASH_CHANGED); } BOOL Delete_comp(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR, ("Bad occurrence kind")); return Is_flag_set(OCC_DELETE_COMP); } BOOL Save_to_temp(void) const { Is_True(Occ_kind() == OCC_REAL_OCCUR || Occ_kind() == OCC_PHI_PRED_OCCUR, ("Bad occurrence kind")); return Is_flag_set(OCC_SAVE_TO_TEMP); } BOOL Inserted_computation(void) const { // The CSE/CodeMotion step is cleaner if we sometimes check a // real or phi occurrence for an insertion; this is OK as long // as we're going to return FALSE. Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR || Occ_kind() == OCC_PHI_OCCUR || Occ_kind() == OCC_REAL_OCCUR, ("EXP_OCCURS::Inserted_computation: Bad occurrence kind")); // Slightly convoluted code because of overloaded flag bits: if (Occ_kind() == OCC_REAL_OCCUR) { return FALSE; } else { return Is_flag_set(OCC_INSERTED_OCCUR); } } BOOL T_ver_owns_coderep(void) const { Is_True(Occ_kind() == OCC_PHI_OCCUR || Occ_kind() == OCC_REAL_OCCUR, ("EXP_OCCURS::T_ver_owns_coderep: Bad occurrence kind")); return Is_flag_set(OCC_CODEREP_OWNER); } void Bid_for_coderep(const ETABLE *const, ID_MAP &, const UINT32); void Render_coderep_unownable(const ETABLE *const, ID_MAP &); BOOL Occurs_as_lvalue(void) const { return Is_flag_set(OCC_AS_L_VALUE); } BOOL Sunk_lvalue(void) const { return Is_flag_set(OCC_SUNK_L_VALUE); } void Set_required_pred(void) { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Set_required_pred: Only preds can be required")); Set_flag(OCC_REQUIRED_PRED); } void Reset_required_pred(void) { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Set_required_pred: Only preds can be required")); Reset_flag(OCC_REQUIRED_PRED); } BOOL Required_pred(void) const { Is_True(Occ_kind() == OCC_PHI_PRED_OCCUR, ("EXP_OCCURS::Required_pred: Only preds can be required")); return Is_flag_set(OCC_REQUIRED_PRED); } BOOL Temp_eligible_as_owner(EXP_WORKLST *worklist) const; BOOL Occurs_as_hoisted(void) const { return Is_flag_set(OCC_HOISTED); } // Return a CR with necessary CVT/CVTL inserted CODEREP *Load_use_cr(ETABLE *etable, CODEREP *old_cr, CODEREP *cr); BOOL Injured_occ(void) const { // Please add assertion(s) here to verify invariants. return Is_flag_set(OCC_INJURED); } BOOL Obsolete_comparison(void) const { Is_True(Occ_kind() == OCC_COMP_OCCUR, ("EXP_OCCURS::Obsolete_comparison: Bad occurrence kind")); return Is_flag_set(OCC_OBSOLETE_COMPARISON); } void Set_obsolete_comparison(void) { Is_True(Occ_kind() == OCC_COMP_OCCUR, ("EXP_OCCURS::Set_obsolete_comparison: Bad occurrence kind")); Set_flag(OCC_OBSOLETE_COMPARISON); } // Test if 'this' is a descendant of 'anc' in the Dominator Tree(DT) BOOL Is_DT_descendant_of( EXP_OCCURS *anc ); // Test if the DPO of 'this' less than the DPO of 'x'. // Asserts if they are the same. [ No it doesn't. It returns FALSE -- RK ] BOOL Is_DPO_less_than(EXP_OCCURS *x); BOOL Stmt_order_less_or_equal(EXP_OCCURS *x) const { return Stmt()->Stmt_order_less_or_equal(x->Stmt()); } BB_NODE *Bb(void) const; // return the BB that contains this. void Print(FILE *fp = stderr, BOOL show_phi_preds = TRUE) const; // Set the real occurrence and hoisted occurrence flag void Set_hoisted_occ(void) { Set_kind(OCC_REAL_OCCUR); Set_flag(OCC_HOISTED); } // Reset the hoisted occ flag void Reset_hoisted(void) { Reset_flag(OCC_HOISTED); } void Save_flags() { _saved_flags = _flag; } void Restore_flags() { _flag = _saved_flags; } // A function used in SSA minimization and CodeMotion to tell what // occurrence *this is identical to. EXP_OCCURS *Occ_identical_to(void); bool Will_b_deleted() { return Occ_kind() == OCC_REAL_OCCUR && !Occurs_as_lvalue() && Def_occur() != NULL && (Def_occur()->Occ_kind() == OCC_REAL_OCCUR || (Def_occur()->Occ_kind() == OCC_PHI_OCCUR && Def_occur()->Exp_phi()->Will_b_avail())); } }; class EXP_OCCURS_CONTAINER : public SLIST { private: EXP_OCCURS_CONTAINER(const EXP_OCCURS_CONTAINER&); EXP_OCCURS_CONTAINER& operator = (const EXP_OCCURS_CONTAINER&); DECLARE_SLIST_CLASS( EXP_OCCURS_CONTAINER, EXP_OCCURS ) public: ~EXP_OCCURS_CONTAINER(void) { } void Init(void); void Print(FILE *fp = stderr); // used when deleting the first element from the list void Set_Head(EXP_OCCURS *exp) { SLIST::Set_Head(exp); } void Set_Tail(EXP_OCCURS *exp) { SLIST::Set_Tail(exp); } }; // single list of occurrences class EXP_OCCURS_ITER : public SLIST_ITER { DECLARE_SLIST_ITER_CLASS(EXP_OCCURS_ITER, EXP_OCCURS, EXP_OCCURS_CONTAINER ) public: void Init(void) { } }; class EXP_PHI_OPND_USE_ITER { private: EXP_PHI *_phi; mINT32 _cur; public: EXP_PHI_OPND_USE_ITER(void) { } EXP_PHI_OPND_USE_ITER(EXP_PHI *const phi) { Init(phi); } void Init(void) { _cur = 0; } void Init(EXP_PHI *const phi) { _cur = 0; _phi = phi; } void Init(EXP_PHI_OPND_USE_ITER *const iter) { Init(iter->_phi); } BOOL Is_Empty(void) const { return _cur >= _phi->Opnd_count(); } EXP_PHI_OPND_USE_ITER *First(void) { _cur = 0; while (!Is_Empty() && (_phi->Opnd(_cur) == NULL || _phi->Has_real_occ(_cur))) { ++_cur; } return this; } EXP_PHI_OPND_USE_ITER *Next(void) { ++_cur; while (!Is_Empty() && (_phi->Opnd(_cur) == NULL || _phi->Has_real_occ(_cur))) { ++_cur; } return this; } EXP_PHI *Node(void) const { Is_True(_phi->Opnd(_cur) != NULL, ("EXP_PHI_OPND_USE_ITER::Node: current operand " "must not be NULL")); return _phi->Opnd(_cur)->Exp_phi(); } // Placeholder member function; not useful in use-def DFS. INT Opnd_idx(void) const { return 0; } }; // The following iterator is useful only with FOR_ALL_NODE. It does // not support, e.g., FOR_ALL_NODE_REVERSE. class EXP_PHI_OCC_ITER { private: EXP_OCCURS_ITER _occ_iter; public: EXP_PHI_OCC_ITER(void) { }; EXP_PHI_OCC_ITER(EXP_OCCURS_CONTAINER &occs) : _occ_iter(occs.Head()) { } void Init(void) { }; void Init(EXP_OCCURS_CONTAINER &occs) { _occ_iter.Init(occs.Head()); } EXP_PHI *First(void) { EXP_OCCURS *phi_occ = _occ_iter.First(); return (phi_occ != NULL ? phi_occ->Exp_phi() : NULL); } EXP_PHI *Next(void) { EXP_OCCURS *phi_occ = _occ_iter.Next(); return (phi_occ != NULL ? phi_occ->Exp_phi() : NULL); } BOOL Is_Empty(void) { return _occ_iter.Is_Empty(); } }; class EXP_OCCURS_PAIR { private: EXP_OCCURS *_occ[2]; EXP_OCCURS_PAIR(const EXP_OCCURS_PAIR&); EXP_OCCURS_PAIR& operator = (const EXP_OCCURS_PAIR&); public: EXP_OCCURS_PAIR(void) { Clear(); } ~EXP_OCCURS_PAIR(void) {} void Clear(void) { _occ[0] = NULL; _occ[1] = NULL; } void Set_occ(INT i, EXP_OCCURS *occ) { _occ[i] = occ; } EXP_OCCURS *Occ1(void) const { return _occ[0]; } EXP_OCCURS *Occ2(void) const { return _occ[1]; } BOOL Is_Empty(void) const { return _occ[0] == NULL && _occ[1] == NULL; } }; // This is the iterator for each of the four entries in the master iterator // list. Each iterator in the list can be a normal iterator, or an iterator // that iterates over several lists. class OCC_ITER_LIST : public SLIST_NODE { private: union { EXP_OCCURS_ITER *_occ_iter; // PHI_OCCUR, PHI_PRED_OCCUR, EXIT_OCCUR EXP_ALL_REAL_ITER *_all_real_iter; // REAL_OCCUR, COMP_OCCUR } _node; BOOL _is_occ_iter; // TRUE for occ_iter, FALSE for all_real_iter BOOL Is_occ_iter(void) const { return _is_occ_iter; } EXP_OCCURS_ITER *Occ_iter(void) const { Is_True(_is_occ_iter, ("OCC_ITER_LIST::Occ_iter, _is_occ_iter incorrect")); return _node._occ_iter; } EXP_ALL_REAL_ITER *All_real_iter(void) const { Is_True(!_is_occ_iter, ("OCC_ITER_LIST::All_real_iter, _is_occ_iter incorrect")); return _node._all_real_iter; } OCC_ITER_LIST(const OCC_ITER_LIST&); OCC_ITER_LIST& operator = (const OCC_ITER_LIST&); public: OCC_ITER_LIST(void) { } OCC_ITER_LIST(EXP_OCCURS_ITER *occ_iter) { _node._occ_iter = occ_iter; _is_occ_iter = TRUE; } OCC_ITER_LIST(EXP_ALL_REAL_ITER *all_real_iter) { _node._all_real_iter = all_real_iter; _is_occ_iter = FALSE; } ~OCC_ITER_LIST(void) { } DECLARE_SLIST_NODE_CLASS( OCC_ITER_LIST ) // member access functions EXP_OCCURS *Get_cur(void) const; EXP_OCCURS *Next_occ(void) const; }; // end of class OCC_ITER_LIST // This is the container that holds the four iterators in the master list. class OCC_CONTAINER : public SLIST { private: OCC_CONTAINER(const OCC_CONTAINER&); OCC_CONTAINER& operator = (const OCC_CONTAINER&); DECLARE_SLIST_CLASS( OCC_CONTAINER, OCC_ITER_LIST ) public: ~OCC_CONTAINER(void) { } void Insert_sort(OCC_ITER_LIST *l); }; // This iterator iterates over the master iterator list. class OCC_ITER_LIST_ITER : public SLIST_ITER { DECLARE_SLIST_ITER_CLASS(OCC_ITER_LIST_ITER, OCC_ITER_LIST, OCC_CONTAINER ) public: void Init(void) { } }; // ==================================================================== // EXP_ALL_REAL_ITER: This is an iterator to scan two EXP_OCCURS // lists (one real occurrences, one comp occurrences) // according to the Dominator tree PreOrder. // ==================================================================== class EXP_ALL_REAL_ITER { private: // individual iterators over the lists of occurrence nodes EXP_OCCURS_ITER _real; EXP_OCCURS_ITER _comp1; EXP_OCCURS_ITER _comp2; // iterators for each element in the master iterator list OCC_ITER_LIST _real_iter; OCC_ITER_LIST _comp1_iter; OCC_ITER_LIST _comp2_iter; // the master iterator list OCC_CONTAINER _all_iter; EXP_ALL_REAL_ITER(void); EXP_ALL_REAL_ITER(const EXP_ALL_REAL_ITER&); EXP_ALL_REAL_ITER& operator=(const EXP_ALL_REAL_ITER&); EXP_OCCURS *Get_cur(void) const; public: EXP_ALL_REAL_ITER(EXP_OCCURS *, EXP_OCCURS_PAIR *); ~EXP_ALL_REAL_ITER(void) { } void Init(void) { } EXP_OCCURS *First(void); EXP_OCCURS *Next(void); EXP_OCCURS *Cur(void) { return Get_cur(); } BOOL Is_Empty(void) const; }; // ==================================================================== // EXP_ALL_OCCURS_ITER: This is an iterator to scan two EXP_OCCURS // lists (one real occurrences, one phi occurrences) // according to the Dominator tree PreOrder. // ==================================================================== class EXP_ALL_OCCURS_ITER { private: // individual iterators over the lists of occurrence nodes EXP_ALL_REAL_ITER _real; // real and comp occurs EXP_OCCURS_ITER _phi; EXP_OCCURS_ITER _phi_pred; EXP_OCCURS_ITER _exit; // iterators for each element in the master iterator list OCC_ITER_LIST _real_iter; // both REAL_OCCUR and COMP_OCCUR OCC_ITER_LIST _phi_iter; OCC_ITER_LIST _pred_iter; OCC_ITER_LIST _exit_iter; // the master iterator list OCC_CONTAINER _all_iter; // array of pointers to EXP_OCCURS for EXP_OCCURS **_fast_array; EXP_ALL_OCCURS_ITER(void); EXP_ALL_OCCURS_ITER(const EXP_ALL_OCCURS_ITER&); EXP_ALL_OCCURS_ITER& operator = (const EXP_ALL_OCCURS_ITER&); EXP_OCCURS *Get_cur(void) const; public: // constructor for normal iterator (some lists can be missing) EXP_ALL_OCCURS_ITER(EXP_OCCURS *real, EXP_OCCURS_PAIR *comp, EXP_OCCURS *phi, EXP_OCCURS *phi_pred, EXP_OCCURS *exit); // constructor for fast reuse iterator EXP_ALL_OCCURS_ITER(EXP_WORKLST *worklst, ETABLE *etable, LFTR *lftr); ~EXP_ALL_OCCURS_ITER(void) { } void Init(void) { } EXP_OCCURS *First(void); EXP_OCCURS *Next(void); BOOL Is_Empty(void) const; void Remove_iter(void); }; // ==================================================================== // EXP_WORKLST: This is a worklist entry for a specific expression. // Note: never include any expression contains volatile // memory access! It contains: // // _e_num: the E-Number for the expression we are // processing. // _exp: the first instance of the expression of this // specific syntactical order. // _preg: the preg aux_id assigned for this specific // exp. // _real_occurs: the list of all real occurrences of this // expression in this PU in DPO. // _phi_occurs: the list of all phi occurrences. // _phi_pred_occurs: the list of all phi occurrences. // _comp_occurs: the pair(possibly) of all comp occurrences. // // NOTE: EXP_WORKLST is an slist for it's use as a hash bucket list when // finding an expression. It also has another singly linked list // (_next) for use in the worklst itself. LFTR needs to be able to // insert at the beginning of the worklst. // ==================================================================== class EXP_WORKLST : public SLIST_NODE { DECLARE_SLIST_NODE_CLASS( EXP_WORKLST ) public: enum EXP_WORKLST_FLAG { EWF_NONE = 0x00, EWF_SIGN_EXTD = 0x01,// this CK_IVAR is sign extended hi/lo 32 bits EWF_EXCLUDE_SR_CAND = 0x02,// this expr won't be strength-reduced EWF_IS_PROCESSED = 0x04,// this worklist has been processed and // sits in processed_worklist EWF_IS_URGENT = 0x08,// this worklist is in urgent_worklist EWF_PHI_PREDS_PRUNED = 0x10,// inconsequential phi preds have been // recycled EWF_HAS_CONST = 0x20,// the expression contains constant node EWF_HAS_RCONST = 0x40,// the expression contains RCONST node EWF_HAS_LDA = 0x80,// the expression contains LDA node EWF_LR_SHRINK_CAND = 0x100,// live range shrinking candidate (LPRE only) EWF_IVC_CAND = 0x200,// induction variable coalescing candidate EWF_NO_LFTR = 0x400 // no LFTR for this expression (hack // around 665964) }; enum EXP_PREG_VALUE { ILLEGAL_PREG = 0, // illegal preg }; private: EXP_ID _e_num; // the e_num for _exp CODEREP *_exp; // the coderep node IDTYPE _preg; // the preg containing value of _exp; // in SPRE, preg assigned to variable UINT32 _flags:30; // EWF_... flags UINT32 _pre_kind:2; // PRE_KIND EXP_OCCURS_CONTAINER _real_occurs; // real occurrences EXP_OCCURS_CONTAINER _phi_occurs; // phi occurrences EXP_OCCURS_CONTAINER _phi_pred_occurs; // phi predecessor occurrences EXP_OCCURS_PAIR _comp_occurs; // comparison occurrences IDTYPE _temp_id; // has processed this var in this BB in SPRE's iphi insertion INT _cur_e_version; // next e-version to use EXP_ALL_OCCURS_ITER *_iterator; // occurrence iterator union { BB_NODE_SET *_iphi_bbs; // BBs with iphi inserted in SPRE STACK *_spre_stack; // stack used in step 3 of SPRE } _u1; INT _phi_cnt; // for statistics INT _realocc_cnt; // for statistics INT _ssa_edge_cnt; // for statistics INT _optimistic_ssa_cnt;// for statistics INT _dense_ssa_cnt; // for statistics INT _insert_cnt; // for statistics INT _save_cnt; // for statistics INT _reload_cnt; // for statistics INT _temp_phi_cnt; // for statistics INT _hoisted_cnt; // for statistics INT _temp_owner_cnt; // for statistics EXP_WORKLST(void); EXP_WORKLST(const EXP_WORKLST&); EXP_WORKLST& operator = (const EXP_WORKLST&); // verify if the occ is in dpo order of occ is the last in the worklist BOOL Verify_dpo_order(EXP_OCCURS_CONTAINER &worklist, EXP_OCCURS *occ); BOOL Verify_dpo_order(EXP_OCCURS_CONTAINER &worklist); void Compute_du_info(MEM_POOL *); void Compute_user_avail(BOOL); void Compute_avail(BOOL); void Compute_stops(BOOL); void Compute_partial_avail(BOOL); void Insert_one_operand(ETABLE *, CODEMAP *, EXP_PHI *, INT); BOOL Determine_inserts_saves_deletions(CODEMAP *, ETABLE *, E_VER_TAB *, EXP_OCCURS_PAIR *); void SPRE_Determine_inserts_saves_deletions(CODEMAP *, ETABLE *, E_VER_TAB *); #if Is_True_On void Verify_saved_occurs(E_VER_TAB *); #endif // helper of varible assignment induced phi-insertion void Generate_variable_phi_list(INT, BB_NODE_SET&, BOOL, ETABLE*); // helper of varible assignment induced phi-insertion for indirect load/store void Generate_ivariable_phi_list_addr(BB_NODE_SET&, BOOL, ETABLE*); void Generate_ivariable_phi_list_vsym(BB_NODE_SET&, BOOL); public: EXP_WORKLST(EXP_ID e_num, CODEREP *exp, PRE_KIND pre_kind) { _pre_kind = pre_kind; Init (e_num, exp); Exam_const(); } ~EXP_WORKLST(void) { } // Member access functions EXP_OCCURS_CONTAINER& Real_occurs(void) { return _real_occurs; } EXP_OCCURS_CONTAINER& Phi_occurs(void) { return _phi_occurs; } EXP_OCCURS_CONTAINER& Phi_pred_occurs(void) { return _phi_pred_occurs; } EXP_OCCURS_PAIR& Comp_occurs(void) { return _comp_occurs; } PRE_KIND Pre_kind(void) const { return (PRE_KIND)_pre_kind; } EXP_ID E_num(void) const { return _e_num; } void Set_e_num(EXP_ID n) { _e_num = n; } CODEREP *Exp(void) const { return _exp; } IDTYPE Preg(void) const { return _preg; } void Set_preg(IDTYPE s) { _preg = s; } STACK *Spre_stack(void) const { Is_True(_pre_kind == PK_SPRE, ("Spre_stack must be SPRE")); return _u1._spre_stack;} void Set_spre_stack (STACK *s){ Is_True(_pre_kind == PK_SPRE, ("Set_spre_stack must be SPRE")); _u1._spre_stack = s;} BB_NODE_SET *Iphi_bbs(void) const { Is_True(_pre_kind == PK_SPRE, ("Iphi_bbs must be SPRE")); return _u1._iphi_bbs;} void Set_iphi_bbs(BB_NODE_SET *s) { Is_True(_pre_kind == PK_SPRE, ("Set_iphi_bbs must be SPRE")); _u1._iphi_bbs = s;} IDTYPE Temp_id(void) const { Is_True(_pre_kind == PK_SPRE, ("temp_id must be SPRE")); return _temp_id; } void Set_temp_id(IDTYPE s) { Is_True(_pre_kind == PK_SPRE, ("Set_temp_id must be SPRE")); _temp_id = s; } INT Insert_count(void) const { return _insert_cnt; } void Inc_insert_count(void) { _insert_cnt++; } INT Save_count(void) const { return _save_cnt; } void Inc_save_count(void) { _save_cnt++; } INT Reload_count(void) const { return _reload_cnt; } void Inc_reload_count(void) { _reload_cnt++; } INT Temp_phi_count(void) const { return _temp_phi_cnt; } void Inc_temp_phi_count(void) { _temp_phi_cnt++; } INT Hoisted_count(void) const { return _hoisted_cnt; } void Inc_hoisted_count(void) { _hoisted_cnt++; } INT Temp_owner_count(void) const { return _temp_owner_cnt; } void Inc_temp_owner_count(void) { _temp_owner_cnt++; } void Reset_statistics(void) { _phi_cnt = 0; _realocc_cnt = 0; _ssa_edge_cnt = 0; _optimistic_ssa_cnt = 0; _dense_ssa_cnt = 0; _insert_cnt = 0; _save_cnt = 0; _reload_cnt = 0; _temp_phi_cnt = 0; _hoisted_cnt = 0; _temp_owner_cnt = 0; } INT Phi_count(void) const { return _phi_cnt; } INT Realocc_count(void) const { return _realocc_cnt; } INT Ssa_edge_count(void) const { return _ssa_edge_cnt; } INT Optimistic_ssa_count(void) const { return _optimistic_ssa_cnt; } INT Dense_ssa_count(void) const { return _dense_ssa_cnt; } void Inc_phi_count(void) { _phi_cnt++; } void Inc_realocc_count(void) { _realocc_cnt++; } void Inc_ssa_edge_count(void) { _ssa_edge_cnt++; } void Inc_optimistic_ssa_count(INT n) { _optimistic_ssa_cnt += n; } void Inc_dense_ssa_count(void) { _dense_ssa_cnt++; } // Cur_e_version() is the next version to use. After // Cur_e_version()'s return value has been saved somewhere, // New_e_version() should be called. INT Cur_e_version(void) const { return _cur_e_version; } void New_e_version(void) { ++_cur_e_version; } void Init_e_version(void) { _cur_e_version = EXP_OCCURS::ILLEGAL_E_VERSION + 1;} // fast occurrence iterator void Set_iterator(EXP_ALL_OCCURS_ITER *iter) { _iterator = iter; } EXP_ALL_OCCURS_ITER *Iterator(void) { return _iterator; } void Init(EXP_ID e_num, CODEREP *exp); void Exam_const(void); void Adjust_combined_types(CODEREP *cr); void Set_sign_extd( void ) { _flags |= EWF_SIGN_EXTD; } void Reset_sign_extd( void ) { _flags &= ~EWF_SIGN_EXTD; } BOOL Sign_extd( void ) { return _flags & EWF_SIGN_EXTD; } // various EWF_... flags // this expr is going to be excluded from being an strength-reduction // candidate void Clear_flags(void) { _flags = EWF_NONE; } BOOL Exclude_sr_cand(void)const{ return (Pre_kind()==PK_EPRE) && (_flags & EWF_EXCLUDE_SR_CAND);} void Set_exclude_sr_cand( void){ _flags |= EWF_EXCLUDE_SR_CAND; } void Reset_exclude_sr_cand(void){ _flags &= ~EWF_EXCLUDE_SR_CAND;} // this expr is processed BOOL Is_processed(void)const { return _flags&EWF_IS_PROCESSED;} void Set_is_processed( void ) { _flags |= EWF_IS_PROCESSED; } void Reset_is_processed( void ){ _flags &= ~EWF_IS_PROCESSED; } // this expr is urgent BOOL Is_urgent(void)const { return _flags & EWF_IS_URGENT;} void Set_is_urgent( void ) { _flags |= EWF_IS_URGENT; } void Reset_is_urgent( void ) { _flags &= ~EWF_IS_URGENT; } // this expr contains int constant BOOL Has_const(void)const { return _flags & EWF_HAS_CONST;} void Set_has_const( void ) { _flags |= EWF_HAS_CONST; } void Reset_has_const( void ) { _flags &= ~EWF_HAS_CONST; } // this expr contains floating constant BOOL Has_rconst(void)const { return _flags & EWF_HAS_RCONST;} void Set_has_rconst( void ) { _flags |= EWF_HAS_RCONST; } void Reset_has_rconst( void ) { _flags &= ~EWF_HAS_RCONST; } // this expr contains LDA node BOOL Has_lda(void)const { return _flags & EWF_HAS_LDA;} void Set_has_lda( void ) { _flags |= EWF_HAS_LDA; } void Reset_has_lda( void ) { _flags &= ~EWF_HAS_LDA; } // variable is a live range shrinking candidate (LPRE only) BOOL LR_shrink_cand(void) const { return _flags & EWF_LR_SHRINK_CAND;} void Set_LR_shrink_cand( void ) { _flags |= EWF_LR_SHRINK_CAND; } // variable is an induction variable coalesing candidate (VNFRE only) BOOL Ivc_cand(void) const { return _flags & EWF_IVC_CAND;} void Set_ivc_cand( void ) { _flags |= EWF_IVC_CAND; } void Reset_ivc_cand( void ) { _flags &= ~EWF_IVC_CAND; } // Defeat LFTR on a per-expr basis. This is Fred's hack to avoid // 665964 without doing anything intelligent. The flag is set in // EXP_WORKLST::Propagate_downsafe when we perform speculation. BOOL No_lftr(void) const { return _flags & EWF_NO_LFTR; } void Set_no_lftr(void) { _flags |= EWF_NO_LFTR; } void Reset_no_lftr(void) { _flags &= EWF_NO_LFTR; } BOOL Weight_less_than(EXP_WORKLST*); // this expr's phi-preds that precede only non-Will_b_avail() phi's // have been removed from the phi-pred occurrence list and recycled. BOOL Phi_preds_pruned(void) const { return _flags & EWF_PHI_PREDS_PRUNED; } void Set_phi_preds_pruned(void) { _flags |= EWF_PHI_PREDS_PRUNED; } // Remove all occurrences in the worklist void Remove_occurs(ETABLE *etable); // Append an occurrence node to one of the list. // Asserts if it is not the highest in DPO. void Append_occurrence(EXP_OCCURS *occ); // Insert occurrence node to one of the lists in the right slot to // keep the DPO. BB that determines DPO is derived through the // occurrence's Stmt() field. void Insert_occurrence(EXP_OCCURS *occ, ETABLE *etable); // Insert occurrence node to one of the lists in the right slot to // keep the DPO. BB that determines DPO is specified explicitly, so // insertion into the occurrence list can be made before the // assignment STMTREP is built. void Insert_occurrence(EXP_OCCURS *, BB_NODE *); // remove a single occurrence from one of the worklsts BOOL Remove_real_occurrence(STMTREP *stmt); // 'this' is the same as 'cr' BOOL Is_the_same_as(const CODEREP *cr); // Given a BB, find the phi occurrence (if any) in that BB EXP_OCCURS *Lookup_phi_occ(const BB_NODE *bb); // Insert necessary CVT/CVTL when save 'old_cr' to PREG CODEREP *Save_use_cr(const ETABLE *etable, CODEREP *old_cr); // Check for expressions that show up on rhs of iv-updates that // cannot be candidates for strength-reduction void Exclude_strength_reduction_cands(ETABLE *etable); void Remove_if_saved_to_preg(ETABLE *etable); // Insert phi functions BOOL Insert_exp_phi(ETABLE *etable); // Rename one expression worklst void Rename_expression(ETABLE *etable); // Rename one value numbering (vnfre) worklst void Rename_valnums(ETABLE *etable); // Backward down-safe propagation BOOL Propagate_downsafe(ETABLE *etable); // Backward determine live phi's void Determine_live_phi(ETABLE *etable); // Forward WILL-B-AVAILABLE/INSERT computation void Compute_forward_attributes(ETABLE *etable, BOOL compute_partial_avail = FALSE); // Forward USER_AVAIL computation void Compute_fully_avail(ETABLE *etable); void Compute_fully_avail_stops(ETABLE *etable, BOOL &found_redundancy); // Remove phi's that aren't Will_b_avail() and any preds that don't // have Will_b_avail() successors. void Prune_phi_phi_pred(ETABLE *); // Compute save/delete decisions and perform insertions BOOL Compute_save_delete(CODEMAP *htable, ETABLE *etable, EXP_OCCURS_PAIR *comp_occurs); // Perform code hoisting void Hoist_expression(EXP_HOISTING *); // Minimize SSA of the temp void Minimize_temp_ssa(const ETABLE *, BOOL); // Generate save-restore for CSE void Generate_save_reload(ETABLE *etable); void Verify(void); void Print(FILE *fp = stderr, EXP_OCCURS_PAIR *comp_occurs=NULL); // SPRE specific functions void SPRE_append_occurrence(EXP_OCCURS *occ) { occ->Set_for_spre(); Append_occurrence(occ); } void SPRE_create_iphi_succ(ETABLE *etable); void SPRE_determine_live_phi(ETABLE *etable); void SPRE_compute_backward_attributes(ETABLE *etable); void SPRE_compute_insert_delete(CODEMAP *htable, ETABLE *etable); void SPRE_perform_insert_delete(ETABLE *etable); void Estimate_cost(ETABLE *, PRE_KIND); void Save_flags(); }; // EXP_WORKLST_CONTAINER and EXP_WORKLST_ITER are used by the hash table class EXP_WORKLST_CONTAINER : public SLIST { DECLARE_SLIST_CLASS( EXP_WORKLST_CONTAINER, EXP_WORKLST ) private: EXP_WORKLST_CONTAINER(const EXP_WORKLST_CONTAINER&); EXP_WORKLST_CONTAINER& operator=(const EXP_WORKLST_CONTAINER&); public: ~EXP_WORKLST_CONTAINER(void){}; void Init(EXP_WORKLST *w) { SLIST::Set_Head(w); } void Clear(void) { SLIST::Clear(); } void Insert_sorted(EXP_WORKLST*); }; class EXP_WORKLST_ITER : public SLIST_ITER { DECLARE_SLIST_ITER_CLASS(EXP_WORKLST_ITER, EXP_WORKLST, EXP_WORKLST_CONTAINER ) public: void Init(void) { } }; // EXP_WORKLST_NODE, is a doubly linked list that contains only one // member such that we can create a list of EXP_WORKLST nodes. The // EXP_WORKLIST node itself is a singly linked list. It's link is // used by the Exp_worklst and Urgent_worklst in the ETABLE. The // EXP_WORKLST_NODE gives us the second next pointer to be used in // the ETABLE's expression hash function. class EXP_WORKLST_NODE : public SLIST_NODE { private: EXP_WORKLST *node; EXP_WORKLST_NODE(const EXP_WORKLST_NODE&); EXP_WORKLST_NODE& operator = (const EXP_WORKLST_NODE&); public: EXP_WORKLST_NODE(void) {} EXP_WORKLST_NODE (EXP_WORKLST *nd) { node = nd; } ~EXP_WORKLST_NODE(void) {} DECLARE_SLIST_NODE_CLASS( EXP_WORKLST_NODE ) void Init(EXP_WORKLST *nd) { node = nd; } BOOL Contains(EXP_WORKLST *); // check membership in list // member access functions EXP_WORKLST *Node(void) const { return node; } }; // end of class EXP_WORKLST_NODE // use the name EXP_WORKLST_NODE_CONTAINER in the rest of the program. #define EXP_WORKLST_NODE_CONTAINER EXP_WORKLST_NODE_CONT class EXP_WORKLST_NODE_CONT : public SLIST { private: EXP_WORKLST_NODE_CONT(const EXP_WORKLST_NODE_CONT&); EXP_WORKLST_NODE_CONT& operator = (const EXP_WORKLST_NODE_CONT&); DECLARE_SLIST_CLASS( EXP_WORKLST_NODE_CONT, EXP_WORKLST_NODE ) public: ~EXP_WORKLST_NODE_CONT(void){}; void Init(EXP_WORKLST_NODE *w){ SLIST::Set_Head(w); } void Clear(void) { SLIST::Clear(); } EXP_WORKLST_NODE *Find_exp_worklst(const CODEREP *cr); void Append (EXP_WORKLST_NODE *worklst, IDX_32 idx, ETABLE *etable); }; class EXP_WORKLST_NODE_ITER : public SLIST_ITER { DECLARE_SLIST_ITER_CLASS( EXP_WORKLST_NODE_ITER, EXP_WORKLST_NODE, EXP_WORKLST_NODE_CONT ) public: void Init(void) { } }; // EXP_WORKLST_ITER2 allows us to process on WORKLST at a time. It // takes etable as input. Actually, it works on the Exp_worklst and // the Urgent_worklst in the etable. // If there exist any entry inside the urgent list, the First() or // Next() function pick up the first entry in it, otherwise, the first // entry in the Exp_worklst is pulled out. Whatever the worklst get // chosen, this entry is removed from the etable. class EXP_WORKLST_ITER2 { private: EXP_WORKLST_CONTAINER *_exp_worklst; // the work list EXP_WORKLST_CONTAINER *_urgent_worklst; // the urgent list EXP_WORKLST *_cur; void Set_cur(EXP_WORKLST *c) { _cur = c; } public: EXP_WORKLST_ITER2(EXP_WORKLST_CONTAINER *exp_worklst, EXP_WORKLST_CONTAINER *urgent_worklst) { _exp_worklst = exp_worklst; _urgent_worklst = urgent_worklst; _cur = NULL; } void Init(void) { } EXP_WORKLST *Cur(void) { return _cur; } EXP_WORKLST *First(void); EXP_WORKLST *Next(void); BOOL Is_Empty(void) { return _cur == NULL; } }; // ==================================================================== // ETABLE: carries the essential data structure for PRE/SSA phase. // it contains one memory pool that is used for this phase // only. // // _cfg keeps the source code // _opt_stab keeps the variable info // _htable such that we could create new CODEREP and // STMTREP node. // _ssu SSU for SPRE // _etable_pool is set up by the function that creates the // instance of ETABLE. // _per_expr_pool is freed after each expr is done // _etable_local_pool // is used for each pass as local pool // _cur_e_num keeps track of the e-number. // _exit_occurs represents all the occurs at EXIT block // _dpo_exp_phi an array of pointers to the EXP_PHI for // each BB, if any. // _phi_pred_cr an array of pointers to the CODEREP for // each phi-pred BB, if any. Used by Rename // and Strength-reduction // _phi_work_set a bitvector set for inserting phi // _var_phi_set a bitvector set for inserting phi from variables // _exp_hash quickly finds the worklst for an expression. // _exp_worklst contains expressions to be processed. // _occ_freelist recycle pool for EXP_OCCURS nodes // ==================================================================== class ETABLE { friend class EXP_WORKLST; private: CFG *_cfg; OPT_STAB *_opt_stab; CODEMAP *_htable; SSU *_ssu; ALIAS_RULE *_arule; STR_RED *_str_red; LFTR *_lftr; MEM_POOL *_etable_pool; MEM_POOL *_per_expr_pool; MEM_POOL *_etable_local_pool; EXP_ID _cur_e_num; EXP_OCCURS_CONTAINER _exit_occurs; EXP_OCCURS **_dpo_exp_phi; CODEREP **_phi_pred_cr; BB_NODE_SET _phi_work_set; BB_NODE_SET _var_phi_set; ARRAY_exp_hash; EXP_WORKLST_CONTAINER _exp_worklst; // the work list EXP_WORKLST_CONTAINER _urgent_worklst; // the urgent list STACK _occ_freelist; STACK _deferred_ocopy_occurs; STACK _deferred_cfold_stmts; EXP_OCCURS _nil_exp_phi_opnd; // fake node to represent nil PRE_KIND _pre_kind; BOOL _tracing; BOOL _lpre_do_consts; // By default TRUE for LPRE BOOL _lpre_do_loads; // By default TRUE for LPRE INT32 _num_cse_reloads; // statistics INT32 _num_cse_saves; // statistics INT32 _num_inserted_saves; // statistics INT32 _num_temp_phis; // statistics INT32 _num_hoisted; // statistics INT32 _num_temp_owners; // statistics COMP_UNIT *_comp_unit; EXP_HOISTING *_exp_hoisting; // data structure for code hoisting STMTREP *_entry_chi; // used by SPRE rename // The following fields are for speeding up compile-time // INT32 _temp_id; // used by step 1 (moved to htable) REHASH_CACHE_LIST *_rehash_cache; // cache rehashed expressions // three functions required by coding convention ETABLE(void); ETABLE(const ETABLE&); ETABLE& operator = (const ETABLE&); // list of worklsts EXP_WORKLST_CONTAINER *Urgent_worklst(void) { return &_urgent_worklst; } STACK *Occ_freelist(void) { return &_occ_freelist; } EXP_ID Alloc_e_num(void) { return ++_cur_e_num; } void Clear_dpo_exp_phi(void); void Clear_dpo_exp_phi(EXP_OCCURS_CONTAINER &worklist); EXP_OCCURS *Set_exp_phi_bb(const BB_NODE *bb, EXP_OCCURS *exp_phi); EXP_OCCURS *Get_exp_phi_bb(const BB_NODE *bb); BB_NODE_SET &Phi_work_set(void) { return _phi_work_set; } BB_NODE_SET &Var_phi_set(void) { return _var_phi_set; } // any cleanup per expression goes in here void Per_worklst_cleanup(EXP_WORKLST *exp_worklst) const; // walk the PU, create initial work list void Init_worklst( void ); EXP_OCCURS *Alloc_occurs_node(void); // exp hash related routines IDX_32 Exp_hashvalue(const CODEREP *cr); IDX_32 Hash_exp(const CODEREP *cr); EXP_WORKLST_NODE*Exp_hash_bucket(IDX_32 idx) const { return _exp_hash[idx]; } // Generate temp_id for step 1 and step 6 void New_temp_id(void) { Htable()->New_temp_id(); } INT32 Cur_temp_id(void) const { return Htable()->Cur_temp_id(); } // Maintain a cache for rehashed expressions void Clear_rehash_cache(void) { _rehash_cache = NULL; } void Add_rehash_expr(CODEREP *cr, CODEREP *rehash_cr); CODEREP *Lookup_rehash_expr(CODEREP *); // Recursive replacement of real occurrences with a replacement (repl). // CODEREP *Recursive_rehash_and_replace( CODEREP *x, EXP_OCCURS *occur, OCCUR_REPLACEMENT *repl, const BOOL replacing_istr_base, UINT depth); CODEREP *Rehash_and_replace(CODEREP *x, EXP_OCCURS *occur, OCCUR_REPLACEMENT *repl, const BOOL replacing_istr_base); void Replace_occurs(EXP_OCCURS *occur, OCCUR_REPLACEMENT *repl); // remove a single occurrence from one of the worklsts BOOL Remove_real_occurrence(EXP_WORKLST_CONTAINER *worklist, CODEREP *old_cr, STMTREP *stmt); STMTREP *Entry_chi(void) const { return _entry_chi; } void Set_entry_chi(STMTREP *entry_chi) { _entry_chi = entry_chi; } public: ETABLE(CFG *cfg, OPT_STAB *opt_stab, CODEMAP *htable, ALIAS_RULE *ar, IDX_32 exp_hash_size, MEM_POOL *etable_pool, MEM_POOL *per_expr_pool, MEM_POOL *etable_local_pool, COMP_UNIT *comp_unit, PRE_KIND pre_kind); ~ETABLE(void); enum { ILLEGAL_E_NUMBER = 0, }; enum URGENCY { NOT_URGENT = 0, // append to non-urgent list URGENT_INSERT = 1, // insert in urgent list NOT_URGENT_INS= 2, // insert in non-urgent list }; CFG *Cfg(void) const { return _cfg; } OPT_STAB *Opt_stab(void) const { return _opt_stab; } CODEMAP *Htable(void) const { return _htable; } SSU *Ssu(void) const { return _ssu; } ALIAS_RULE *Arule(void) const { return _arule; } STR_RED *Str_red(void) const { return _str_red; } LFTR *Lftr(void) const { return _lftr; } MEM_POOL *Per_expr_pool(void) const{ return _per_expr_pool; } EXP_HOISTING *Exp_hoisting(void) const { return _exp_hoisting; } EXP_WORKLST_CONTAINER *Exp_worklst(void) { return &_exp_worklst; } void Count_lex_ident_exprs(INT32); // for statistics only // remove a single occurrence from one of the worklsts void Remove_real_occurrence(CODEREP *old_cr, STMTREP *stmt); // A version of Alloc_occurs_node to match the fancy // constructor. This is used for insertions, and is always for real // occurrences. EXP_OCCURS *Alloc_occurs_node(CODEREP *); // to get local pool of Etable MEM_POOL *Etable_pool(void) const { return _etable_pool; } MEM_POOL *Etable_local_pool(void) const { return _etable_local_pool; } // get the worklist from the hash table EXP_WORKLST *Get_worklst(CODEREP *cr, BOOL urgent = FALSE, BOOL lookup_only = FALSE); // Generate a temporary register independently of any worklist. CODEREP *New_temp_cr(MTYPE dtype, ADDRESSABILITY addressable); // used by EOCC, SR, LFTR void Check_lftr_non_candidate(STMTREP *stmt, CODEREP *cr, OPCODE opc); void Bottom_up_stmt(STMTREP *stmt); void Bottom_up_cr(STMTREP *stmt, INT stmt_kid_num, CODEREP *cr, // tree to be processed BOOL is_store, // LHS of assignment URGENCY urgent, // insert in urgent list UINT depth, // in the tree OPCODE opc, // operation on this node BOOL no_estr); // used by LPRE void LPRE_set_do_loads(BOOL truth) {_lpre_do_loads = truth;} void LPRE_set_do_consts(BOOL truth) {_lpre_do_consts = truth;} BOOL LPRE_do_loads() const {return _lpre_do_loads;} BOOL LPRE_do_consts() const {return _lpre_do_consts;} void LPRE_bottom_up_stmt(STMTREP *stmt); void LPRE_bottom_up_cr(STMTREP *stmt, INT stmt_kid_num, CODEREP *cr, BOOL is_store, UINT depth, CODEREP *parent, INT whichkid); // used by CSE STMTREP *Generate_stid_to_preg( CODEREP *lhs, CODEREP *rhs, MTYPE rhs_type, BB_NODE *bb, SRCPOS linenum ) const; STMTREP *Save_replace_rhs_by_preg(STMTREP *stmt, CODEREP *pregcr, EXP_WORKLST *wk); void Insert_stmtrep_after(STMTREP *new_stmt, STMTREP *old_stmt); void Replace_by_temp(EXP_OCCURS *occur, CODEREP *tempcr); void Replace_by_const(EXP_OCCURS *occur, TCON tcon); // Always use Rehash_exp() instead of Htable()->rehash() for an etable. CODEREP *Rehash_exp(CODEREP *cr, UINT32 gvn, BOOL canon=TRUE) const; void No_replace(EXP_OCCURS *occur, BOOL dont_rehash); void Find_1st_order_exprs_with_temp(STMTREP *stmt, INT stmt_kid_num, CODEREP *cr, CODEREP *tempcr, BOOL is_store, UINT depth); void Find_new_1st_order_exprs(EXP_OCCURS *occur, CODEREP *tempcr); CODEREP *Rehash_but_no_replace(CODEREP *x, EXP_OCCURS *occur, BOOL replacing_istr_base, INT32 orig_coderep_id); // to append a real occurrence into the worklst void Append_real_occurrence(CODEREP *cr, STMTREP *stmt, INT stmt_kid_num, UINT depth, BOOL is_istore = FALSE); // to insert a real occurrence into the worklst void Insert_real_occurrence(CODEREP *cr, STMTREP *stmt, INT stmt_kid_num, UINT depth, BOOL is_istore = FALSE, BOOL urgent = FALSE); // to append a phi occurence into the worklst EXP_OCCURS *Append_phi_occurrence(CODEREP *cr, EXP_PHI *phi, EXP_WORKLST *worklist); // to append a phi pred occurence into the worklst EXP_OCCURS *Append_phi_pred_occurrence(CODEREP *cr, BB_NODE *bb, EXP_WORKLST *worklist); // to append an exit occurence into the etable void Append_exit_occurrence(BB_NODE *bb); // to insert a phi occurence into the worklst void Insert_phi_occurrence(EXP_PHI *phi); EXP_OCCURS *Append_spre_real_occurrence(STMTREP *stmt, EXP_WORKLST *worklist); EXP_OCCURS *Append_iphi_succ_occurrence(BB_NODE *bb, EXP_WORKLST *worklist); void Set_exp_hash_bucket(IDX_32 idx, EXP_WORKLST_NODE *etmp) { _exp_hash[idx] = etmp; } EXP_PHI *Lookup_exp_phi(const BB_NODE *bb, const CODEREP *cr) const; // Be aware, the returning PHI_NODE could be !Live(). PHI_NODE *Lookup_var_phi(const BB_NODE *bb, const AUX_ID id) const { return Htable()->Lookup_var_phi(bb,id); } // provide an array of coderep's generated per expression void Set_phi_pred_cr(const BB_NODE *bb, CODEREP *cr) const { _phi_pred_cr[bb->Id()] = cr; } CODEREP *Phi_pred_cr(const BB_NODE *bb) const { return _phi_pred_cr[bb->Id()]; } // derive phi opnd codereps from result coderep CODEREP *Generate_cur_expr(const BB_NODE *, INT, CODEREP *, BOOL) const; CODEREP *Get_cached_cur_expr(const BB_NODE *, INT); void Update_cached_cur_expr(const BB_NODE *, INT, CODEREP *); CODEREP *Alloc_and_generate_cur_expr(const CODEREP *, const BB_NODE *, INT, MEM_POOL *, BOOL) const; STACK *Deferred_ocopy_occurs(void) { return &_deferred_ocopy_occurs; } STACK *Deferred_cfold_stmts(void) { return &_deferred_cfold_stmts; } void Schedule_for_ocopy(EXP_OCCURS *); void Perform_deferred_ocopy_and_get_new_exprs(EXP_WORKLST *); void Perform_deferred_cfold(); EXP_OCCURS_CONTAINER &Exit_occurs(void) { return _exit_occurs; } EXP_OCCURS *Nil_exp_phi_opnd(void) { return &_nil_exp_phi_opnd; } PRE_KIND Pre_kind(void) const { return _pre_kind; } BOOL Tracing(void) const { return _tracing; } void Inc_cse_reloads(INT32 n) { _num_cse_reloads += n; } void Inc_cse_saves(INT32 n) { _num_cse_saves += n; } void Inc_inserted_saves(INT32 n) { _num_inserted_saves += n; } void Inc_temp_phis(INT32 n) { _num_temp_phis += n; } void Inc_hoisted(INT32 n) { _num_hoisted += n; } void Inc_temp_owners(INT32 n) { _num_temp_owners += n; } // perform the PRE/SSA optimization void Perform_PRE_optimization(void); // perform the LPRE optimization void Perform_LPRE_optimization(void); // perform the VNFRE optimization void Perform_VNFRE_optimization(void); // SPRE specific functions void Perform_SPRE_optimization(void); void SPRE_update_ssa(void); EXP_OCCURS *New_phi_occurrence(EXP_WORKLST *worklst, MEM_POOL *pool, BB_NODE *bb); void Add_stmt(STMTREP *, BB_NODE *); void SPRE_rename(BB_NODE *); void SPRE_rename_stmt(STMTREP *, BB_NODE *); CODEREP *SPRE_rename_expr(CODEREP *, BB_NODE *); CODEREP *SPRE_rename_var(CODEREP *, BOOL); BOOL Stmt_is_redundant(STMTREP *); BOOL RHS_is_fully_avail(CODEREP *, CODEREP *); void Add_to_occ_freelist(EXP_OCCURS *node); // ----------------------- // VNFRE related utilities // ----------------------- UINT32 Gvn(const CODEREP *cr) const { return (Pre_kind() == PK_VNFRE? VNFRE::get_valnum(cr) : 0U); } void Init_vnfre_worklist(EXP_WORKLST *occurs, EXP_OCCURS_CONTAINER &exit_occurs) { Is_True(Pre_kind() == PK_VNFRE, ("Illegal call to ETABLE::Init_vnfre_worklist()")); Exit_occurs().Set_Head(exit_occurs.Head()); Exit_occurs().Set_Tail(exit_occurs.Tail()); Exp_worklst()->Init(occurs); // Sets head } void Reset_vnfre_worklist() { Is_True(Pre_kind() == PK_VNFRE, ("Illegal call to TABLE::Reset_vnfre_worklist()")); Exp_worklst()->Head()->Remove_occurs(this); Exp_worklst()->Clear(); // Resets head Exit_occurs().Set_Head(NULL); Exit_occurs().Set_Tail(NULL); } EXP_OCCURS *Alloc_vnfre_occurs_node() { // This may be called before _pre_kind == PK_VNFRE, and it alows // us to reuse occurrence nodes from EPRE or other optimization // that has used the same ETABLE. // return Alloc_occurs_node(); } BB_NODE_SET &Reuse_phi_list() { Phi_work_set().ClearD(); return Phi_work_set(); } void Set_phi_result(EXP_PHI *phi, EXP_OCCURS *occurs) const { phi->Set_result(occurs); } void Set_dpo_phi_occurs(const BB_NODE *bb, EXP_OCCURS *phi_occ) { (void) Set_exp_phi_bb(bb, phi_occ); } }; extern EXP_HOISTING *New_EXP_HOISTING(ETABLE *, MEM_POOL *); extern void Delete_EXP_HOISTING(EXP_HOISTING *); extern BOOL Subsumable_by_branch(CODEREP *cr); #endif // opt_etable_INCLUDED