//-*-c++-*- // ==================================================================== // ==================================================================== // // Module: opt_vn.h // $Revision: 1.4 $ // $Date: 2004/08/31 07:39:16 $ // $Author: wychen $ // $Source: bitbucket.org:berkeleylab/upc-translator.git/open64/osprey1.0/be/opt/opt_vn.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 // // ==================================================================== // // INTERFACE DESCRIPTION: // ---------------------- // // This file introduces a class of object representing a value numbering. // The constructor will walk over the CFG and create the value numbering. // Once the value numbering (VN) object is constructed, the other exported // methods may be used to access the value numbering results. Note // that the cfg passed in to the constructor MUST already be in SSA // form. // // The following outlines characteristics of the results of a value // numbering: // // * The expr_cr() mapping maps a CODEREP::Coderep_id() to a CODEREP*. // Ideally this ought to be part of the codemap, but since it is not // we need to define this mapping as part of the value numbering. // TODO: get rid of this when it is created as part of a CODEMAP. // // * The expr_valnum() mapping maps a CODEREP::Coderep_id() to a value // number and should always be well defined and should never be // Bottom() or Top(), with a few exceptions: black boxes // may be Bottom() or Top(), OPR_CALL, OPR_PICCALL, OPR_ICALL, // OPR_INTRINSIC_CALL) and zero version VARs will be assigned // Bottom() values. OPR_PARM CK_IVAR codereps and OPR_PARM // CK_OP codereps will be assigned the same value number as the // argument expression (Base_opnd() and Opnd0() respectively). The // client of the interface exported here should assert if any // unexpected Top() or Bottom() value number is returned. // // * Note that we *do* value number dead statements, since no statement // is marked as live immediately after the CODEMAP is created, and we // may wish to employ offline value numbering before the "live" flags // are set reliably on STMTREPs. // // * The expr_stmts() is a mapping from each CODEREP::Coderep_id() to // the STMTREP* that contains it. The range of the mapping has to be // a list of STMTREPs, since our program representation allows a // CODEREP to be shared between different statements. We do not record // any STMTREP for CODEREPs that have no valid value number (e.g. _|_), // or when the CODEREP is a VAR or IVAR on the lhs of an assignment, // or when the value number denotes a LITERAL and the coderep is also // a literal value (on the assumption that no consumer of the STMT_LIST // ever need these). The current definition of a STMT_LIST as produced // by a VN is made to fit the needs of our redundancy elimination // algorithm. // // * The valnum_expr() mapping maps each value number to the VN_EXPR::PTR // used to derive the value number. This mapping will yield a NULL // value when VN_EXPR::PTR contained Bottom() operands or was arrived // at through a Chi node. All other cases should be non-NULL. // // * Integral VN_EXPR::LITERALs will all have type I8, and must be // coerced into the appropriate type if they are to be inserted // into our IR as part of an optimization. // // * The VALNUM_TO_EXPR_LIST class can be used to construct the reverse // mapping of the VN::expr_valnum() mapping. This reverse mapping // will be NULL for value numbers that are not well-defined (such // as Top() and Bottom()). // // USAGE: // ------ // // The VN class employs the given global memory pool (gpool) to allocate // data-structures for a constructed VN object, while it pushes and pops // the local memory pool (lpool) during construction (VN::VN) and while // performing object methods. We made the choice of separating the // decision as to what mempool is used for allocation of VN_EXPR objects // from the mempools used by a VN object. This requires a bit of care // from the user of the VN_EXPR and the VN interfaces: // // 1) Make sure you call VN_EXPR::Init_Free_Lists(mpool) before you // construct any VN object; otherwise VN construction will fail // with a segv fault. // // 2) Make sure the mpool for VN_EXPRs and the lpool for VNs are // either different, or they are both the Malloc_Mem_Pool. // // 3) Make sure you call VN_EXPR::Reclaim_Free_Lists() to reclaim // free-lists of VN_EXPR objects. Deletion of a VN object will // not delete the VN_EXPR free-lists. If you wish to allocate // VN_EXPR from a new mempool always call Reclaim_Free_Lists() // followed by Init_Free_Lists(mpool). // // The decoupling of the VN_EXPR mempool from the VN mempools allows // more freedom in the allocation scheme, and in particular it allows // repeated use of VN_EXPR free-lists, while constructing and deleting // multiple VN objects. // // Example: // // OPT_POOL_Push(gpool, -1); // { // VN_EXPR::Init_Free_Lists(gpool); // { // VN vn(VN::ITERATIVE, cfg, codemap, lpool, gpool); // ... // use first vn // } // ... // Do other stuff! // { // VN vn(VN::SINGLE_PASS, cfg, codemap, lpool, gpool); // ... // use second vn // } // VN_EXPR::Reclaim_Free_Lists(); // } // OPT_POOL_Pop(gpool, -1); // // Note that VALNUM_TO_EXPR_LIST also uses a mempool, which may or may // not be different from the VN mempools! // // // IMPLEMENTATION DETAILS AND RELATION OF ALGORITHM TO LITERATURE: // --------------------------------------------------------------- // // The algorithms implemented here are based on Taylor Simpson's // work, as documented in his Ph.D. thesis from Rice University entitled // "Value Driven Redundancy Elimination", April 1996. // // His thesis describes two methods of value numbering which we have // implemented here. One is the pessimistic one-pass "unified hash-table // algorithm"; and the other is the similar optimistic iterative // "Reverse Postorder" (RPO) algorithm. His SCC (strongly connected // components) algorithm is touted as the most efficient version of // the RPO algorithm, but it is sufficiently different in implementation // and hard to intuitively understand from the theoretically proven // RPO algorithm, that we instead opted to implement the straight-forward // RPO algorithm. The efficiency benefit of the SCC over the RPO // algorithm is not clear. // // Some characteristics of our SSA representation that affects the // algorithm and caused some changes in the way we do things are as // follows: // // 1) Instead of triplets, we have a program representation in terms // of CODEREPS, where the Coderep_id() can be viewed as the // notion of a "register" as used in Taylor's algorithms. // // 2) Since codereps may be shared between different expressions, // we need a is_numbered[] boolean array to denote whether or // not a Coderep_id[] has already been value numbered (in a // particular iteration of the RPO algorithm). This saves us // from having to construct a VN_EXPR, simplify, and hash an // expression twice. // // 3) We do not use Coderep_id() as a value number, instead assigning // consecutive numbers as value numbers, since there are likely // to be many more CODEREP nodes than value numbers. This reduces // the size of any maps we have from value numbers to other info, // such as the VN_VALNUM-->VN_EXPR::PTR map. // // 4) Our method for finding congruences between indirect loads and // stores is a little different from Taylor's method. We use // the regular hash-table to hash lvalues, and will map such lvalue // expressions (MEMLOC expressions) to the lhs of assignments. // We may see a load off an lvalue without seeing a store into // one beforehand, and will apply a unique value number to such // a load. When a store is seen into an lvalue, the fact that // we use the version of the virtual variable as part of the MEMLOC // guarantees that a load from the same location has not been seen // beforehand. The lvalue MEMLOC for a store will be mapped to // the same value number as the rhs expression's value number, and // this is the only case when two different expressions in the // hash-table may map to the same value number. // // 5) Taylor specifies that the iterative algorithm requires reverse // postorder traversal of the CFG, while the single-pass algorithm // requires a preorder (or reverse postorder) travesal of the // dominator tree with a CFG reverse postorder traversal of the // dominator tree kids. We simplify this to use a reverse postorder // traversal of the CFG in both cases. The algorithms are therefore // essentially the same in each pass over the CFG, except that // one of them starts off with optimistic assumptions, while the // other starts off with pessimistic assumptions. Given this order // of traversal, the only undefined values we *ever* encounter // are parameters of phi nodes representing data-flow up back-edges // in the CFG and indirect loads of lvalues (see point 4 concerning // lvalues). // // 6) We create a map from VN_VALNUMs to VN_EXPR:PTR in addition to the // Coderep_Id() to VN_VALNUM mapping. This is useful to any // subsequent optimizations (such as AVAIL based redundancy // elimination or partial redundancy elimination). // // 7) For phi nodes the value number will be assigned to the RESULT // coderep in the cr_to_vn mapping. For ivars (indirect loads/stores) // the value number will be assigned to the ivar coderep. // // 8) Our representation (CODEREPS) may have implicit conversion // operations (e.g. U8U4ILOAD for mips3), and we will also need // to associate these with an EXPRID. To handle this, and yet // have the iterative algorithm terminate we need a second cr_to_vn // mapping. // // SEE ALSO: // --------- // // opt_cfg.h: Control flow graph. // opt_ssa.h: Control flow graph in SSA form. // opt_htable.h: Utilities for creating the CODEREP form of the cfg. // // opt_vn_expr.h : Implementation of VN_VALNUM, VN_EXPR, and VN_EXPR_MAP. // // opt_vn_hashtab.h : Implementation of VN_HASHTAB, which maps a // VN_EXPR::PTR to VN_VALNUM, based on a hashing algorithm. // // ==================================================================== // ==================================================================== #ifndef opt_vn_INCLUDED #define opt_vn_INCLUDED "opt_vn.h" #include #include #include "segmented_array.h" #include "opt_vn_expr.h" // For VN_VALNUM, VN_EXPR, and VN_EXPR_MAP #include "opt_vn_hashtab.h" // For VN_HASHTAB //#ifdef __STL_USE_NAMESPACES #if defined(__GNUC__) using std::list; using std::vector; #endif class CODEREP; class STMTREP; class CFG; class CODEMAP; class VALNUM_TO_EXPR_LIST; class VN { public: typedef INT32 EXPRID; // CODEREP::Coderep_id() enum VN_ALGORITHM {SINGLE_PASS, ITERATIVE}; typedef mempool_allocator STMT_ALLOCATOR; typedef list STMT_LIST; // linked list typedef mempool_allocator VALNUM_ALLOCATOR; typedef vector VALNUM_VECTOR; typedef mempool_allocator BVECTOR_ALLOCATOR; typedef vector BIT_VECTOR; private: typedef mempool_allocator CODEREP_ALLOCATOR; //wei: this seems wrong, shouldn't the allocator be for coderep? //typedef vector CODEREP_VECTOR; typedef vector > CODEREP_VECTOR; typedef mempool_allocator STMTLIST_ALLOCATOR; typedef vector STMTLIST_VECTOR; struct VN_ALGORITHM_STATUS { VN_HASHTAB *expr_to_vn; // VN_EXPR->VN_VALNUM (used for callback) BIT_VECTOR *is_numbered; // VN_VALNUM->BOOL (for explicit ops) BIT_VECTOR *locked_to_vn; // VN_VALNUM->BOOL (for explicit ops) BIT_VECTOR *locked_to_vn2; // VN_VALNUM->BOOL (for implicit ops) VALNUM_VECTOR *exprid_to_vn2; // EXPRID->VN_VALNUM (for implicit ops) BOOL changed; // Any valnum changed in this iteration VN_ALGORITHM_STATUS(): expr_to_vn(NULL), is_numbered(NULL), locked_to_vn(NULL), locked_to_vn2(NULL), exprid_to_vn2(NULL), changed(FALSE) {} }; // struct VN_ALGORITHM_STATUS MEM_POOL *_lpool; // Pool used for internal algorithms MEM_POOL *_gpool; // Pool used for a "this" object STMTREP *_current_stmt; // For use during value numbering INT32 _no_of_iterations; // For debugging VN_VALNUM _zero_valnum; // For integer literals VN_VALNUM _next_valnum; VN_EXPR_MAP _vn_to_expr; // VN_VALNUM --> VN_EXPR VALNUM_VECTOR _exprid_to_vn; // Coderep_id --> VN_VALNUM STMTLIST_VECTOR _exprid_to_stmtlist; // Coderep_id --> STMT_LIST; CODEREP_VECTOR _exprid_to_cr; // Coderep_id --> (CODEREP*) VN_ALGORITHM_STATUS _status; // Needed only during construction static VN_VALNUM Initial_Valnum(VN_ALGORITHM algo) { return (algo == SINGLE_PASS? VN_VALNUM::Bottom() : VN_VALNUM::Top()); } void _grow_exprid_maps(EXPRID id); EXPRID _get_exprid(const CODEREP *cr) { const EXPRID exprid = cr->Coderep_id(); _exprid_to_cr[exprid] = (CODEREP *)cr; return exprid; } EXPRID _append_exprid(const CODEREP *cr) { // Only use this to modify an existing value numbering, such as // changes caused by VNFRE. // const EXPRID exprid = cr->Coderep_id(); _grow_exprid_maps(exprid); _exprid_to_cr[exprid] = (CODEREP *)cr; return exprid; } VN_VALNUM _unique_valnum(EXPRID exprid, const VALNUM_VECTOR &exprid_to_vn, const BIT_VECTOR &locked_to_vn) const { return (locked_to_vn[exprid]? exprid_to_vn[exprid] : _next_valnum); } VN_VALNUM _get_literal_valnum(INT64 i) const { return VN_VALNUM::Vn(i + _zero_valnum.ordinal()); } void _init_integer_valnum_map(); VN_VALNUM _valnum_integer(INT64 literal, BOOL is_signed); inline void _set_stmt_map(CODEKIND ck, EXPRID id, const VN_VALNUM &vn); void _set_valnum(EXPRID id, const VN_VALNUM &vn, VALNUM_VECTOR &exprid_to_vn, BIT_VECTOR &locked_to_vn); VN_VALNUM _valnum_vn_expr(EXPRID exprid, VN_EXPR::PTR expr, VALNUM_VECTOR &exprid_to_vn, BIT_VECTOR &locked_to_vn); VN_VALNUM _valnum_sym(CODEREP *sym); VN_VALNUM _valnum_op(CODEREP *cr); VN_VALNUM _valnum_expr(CODEREP *cr); VN_VALNUM _valnum_implicit_integral_cvt(EXPRID exprid, VN_VALNUM opnd_valnum, MTYPE from_mty, MTYPE to_mty, VALNUM_VECTOR &exprid_to_vn, BIT_VECTOR &locked_to_vn); VN_VALNUM _valnum_lhs(EXPRID lhs_exprid, VN_VALNUM valnum, MTYPE lhs_dty, MTYPE lhs_dscty, MTYPE rhs_dty); VN_VALNUM _valnum_memloc_load(CODEREP *cr); void _valnum_memloc_store(CODEREP *lhs, VN_VALNUM rhs_valnum, MTYPE rhs_mtype); void _valnum_phi_list(IDTYPE bb_id, PHI_LIST *phi_list); void _valnum_chi_list(CHI_LIST *chi_list); void _valnum_stmt(STMTREP *stmt); void _valnum_cfg(CFG *cfg); void _trace(EXPRID id, VN_VALNUM valnum, FILE *fp = stderr); void _print_exprid_to_vn(FILE *fp, EXPRID id, INT32 column_width) const; void _print_vn_to_exprid(FILE *fp, const VALNUM_TO_EXPR_LIST &vn_to_exprid, VN_VALNUM valnum) const; public: VN(VN_ALGORITHM algo, CFG *cfg, CODEMAP *codemap, MEM_POOL *lpool = Malloc_Mem_Pool, MEM_POOL *gpool = Malloc_Mem_Pool); ~VN(); CODEREP * expr_cr(EXPRID exprid) const { Is_True(exprid <_exprid_to_cr.size(), ("Out of bounds access to VN::expr_cr()")); return _exprid_to_cr[exprid]; } VN_VALNUM expr_valnum(EXPRID exprid) const { Is_True(exprid < _exprid_to_vn.size(), ("Out of bounds access to VN::expr_valnum()")); return (_exprid_to_vn[exprid] == VN_VALNUM::Top()? VN_VALNUM::Bottom() : _exprid_to_vn[exprid]); } const STMT_LIST *expr_stmts(EXPRID exprid) const { Is_True(exprid < _exprid_to_stmtlist.size(), ("Out of bounds access to VN::expr_stmts()")); return &_exprid_to_stmtlist[exprid]; } VN_EXPR::PTR valnum_expr(VN_VALNUM vn) const { return _vn_to_expr[vn]; } EXPRID last_exprid() const { return _exprid_to_vn.size() - 1; } VN_VALNUM last_valnum() const { return VN_VALNUM::Vn(_next_valnum.ordinal() - 1); } // Modifications to a computed value numbering. // void reset_valnum(const CODEREP *cr, VN_VALNUM valnum) { _exprid_to_vn[_get_exprid(cr)] = valnum; } void new_cr(const CODEREP *cr, VN_VALNUM valnum) { _exprid_to_vn[_append_exprid(cr)] = valnum; } // In addition to the expr_valnum() mapping, we also print out the // reverse valnum->exprid mapping for all value numbers that are // neither Bottom() nor Top(). This reverse mapping will also // show the value number expression associated with each value number. // void print(FILE *fp = stderr, BOOL emit_stmt_maps = FALSE) const; VN_VALNUM invent_unique_valnum() { VN_VALNUM unique = _next_valnum; _next_valnum = VN_VALNUM::Next(_next_valnum); return unique; } // The following is a callback routine used during VN construction, // but may also be called after VN construction, in which case we always // simply create a unique value number. // VN_VALNUM valnum_integer(TCON int_tcon) { Is_True(MTYPE_is_integral(TCON_ty(int_tcon)), ("Illegal argument to VN::valnum_integer")); if (_status.expr_to_vn != NULL) return _valnum_integer(Targ_To_Host(int_tcon), MTYPE_is_signed(TCON_ty(int_tcon))); else return invent_unique_valnum(); } }; // class VN //--------------------------------------------------------------------------- // VALNUM_TO_EXPR_LIST: Maps each VN_VALNUM to a list of Coderep_id() numbers, // except Bottom() and Top() values. Note that the "[]" operator returns // a NULL value for Top(), Bottom(), or an invalid value number; Iterate // over this mapping from VN_VALNUM::First() to last_valnum(). //--------------------------------------------------------------------------- // class VALNUM_TO_EXPR_LIST { public: typedef mempool_allocator EXPRID_ALLOCATOR; typedef list EXPR_LIST; // linked list typedef EXPR_LIST::const_iterator EXPR_ITERATOR; private: typedef mempool_allocator EXPRLIST_ALLOCATOR; vector _map; public: VALNUM_TO_EXPR_LIST(const VN &vn, MEM_POOL *mpool = Malloc_Mem_Pool); BOOL is_empty(const VN_VALNUM& v) const { return (v.is_top() || v.is_bottom() || _map[v.ordinal()].empty()); } INT32 size(const VN_VALNUM& v) const { return ((v.is_top() || v.is_bottom())? 0 : _map[v.ordinal()].size()); } VN::EXPRID front(const VN_VALNUM& v) const { if (v.is_top() || v.is_bottom() || _map[v.ordinal()].empty()) return 0; else return _map[v.ordinal()].front(); } EXPR_ITERATOR begin(const VN_VALNUM& v) const { return ((v.is_top() || v.is_bottom())? EXPR_ITERATOR() : _map[v.ordinal()].begin()); } EXPR_ITERATOR end(const VN_VALNUM& v) const { return ((v.is_top() || v.is_bottom())? EXPR_ITERATOR() : _map[v.ordinal()].end()); } }; // VALNUM_TO_EXPR_LIST #endif // opt_vn_INCLUDED