//-*-c++-*- // ==================================================================== // ==================================================================== // // Module: opt_vn_expr.h // $Revision: 1.2 $ // $Date: 2003/03/04 06:16:04 $ // $Author: wychen $ // $Source: bitbucket.org:berkeleylab/upc-translator.git/open64/osprey1.0/be/opt/opt_vn_expr.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 // // ==================================================================== // // INCLUSION DEPENDENCIES: // // Before including this file, you must also include the following // files directly or indirectly: // // common/com/defs.h // common/util/errors.h // common/com/targ_const.h // // // INTERFACE DESCRIPTION: // // This file defines three classes: // // VN_VALNUM: Our value-number representation. Value numbering // is an abstract program interpretation mechanism which will // use VN_VALNUM as its value domain. We take two different // views of value numbers. For hashing purposes we view two // value numbers as identical (operator '==') only if they are // truly exactly the same. // // For VN_EXPR:simplify() purposes we view the range of value // numbers as a lattice, where a Bottom() value is different from // any value, even other bottom values), while a Top() value // matches any other value except a Bottom() value. Literals // match only identical literals. This lattice view of equality // is embodied by the "equivalent_to()" method. // // VN_EXPR: Our representation of expressions formed from // value numbers. This is the domain of expressions over // which value numbering operates. We provide mechanisms // for folding value number expressions into simpler ones // (fold method) and to hash them into a hash-table. Note // that we have included a notion of memory locations (MEMLOC) // in our expression taxonomy, which can be viewed as a form of // lvalue expression that allows us to handle indirect loads // and stores. // // VN_EXPR_MAP: A mapping from each value number to its defining // value number expression. Bottom() and Top() always map to // a NULL expression, and cannot be changed. When a value number // is intrinsically defined (ENTRY_STMT or Chi node), then the // mapping should map the VN_VALNUM to a NULL expression. Such // use of NULL maps should obviate any need for a special kind // of VN_EXPR for Chi nodes or ENTRY_STMT nodes. // // This map automatically grows to accommodate any value number it // is set (set_map) for, so be careful to only define maps for // valid value numbers. If the NULL valued holes in the map turn // out to be very large, it may be better to use a more compact // representation for this map (TODO?). // // Note that we only export methods to create mempool allocated // VN_EXPR objects. This is because the VN_EXPR class really // represents a taxonomy of expression kinds (literal, unary, binary, // phi, etc.), and this taxonomy and associated memory management // is easiest maintained in terms of object references. As a // consequence, the client of a VN_EXPR can never create stack // allocated VN_EXPR objects or an array of allocated VN_EXPR objects, // only a stack or array of VN_EXPR object pointers. // // From a client's perspective, a VN_EXPR should be viewed as a union // of the various kinds (VN_EXPR::KIND). Some accessors are only valid // for certain kinds of expression and we assert when accessors are // called for the wrong kinds of expressions. // // We do allow creation and simplification of VN_EXPR objects with Top() // or Bottom() value numbers as operands, but we *never* allow hashing // of such objects (the hash() method will assert!). // // Each public method is described in further detail at its point // of declaration below. // // // IMPLEMENTATION DETAILS: // // We divide the VN_EXPR objects into different subclasses of // expressions depending on the kind of expression (VN_EXPR::KIND) // we are dealing with. This is best expressed using an inheritance // hierarchy, and we therefore take the liberty here of creating an // inheritance hierarchy to represent this expression taxonomy. // // The user of a VN_EXPR need never be concerned with this taxonomy, // since it is made completely transparant through the class and object // interface provided through VN_EXPR. One consequence of this is that // we only export a means for a user to create a pointer to a VN_EXPR, // where the VN_EXPR is allocated using a given mempool. A VN_EXPR // may be deleted by means of the free() class method, which in an // implementation defined manner may or may not actually free up the // memory. To free up all allocated VN_EXPR memory (i.e. any free-lists // kept around), we provide the method VN_EXPR::Reclaim_Free_Lists(). // This should be done even when the memory reclamation is automatic // (e.g. by means of popping a mempool), since the free-lists is an // odd mix if malloc'ed and CXX_ALLOC'ed memory. // // POSSIBLE IMPROVEMENTS (TODO): // // If the NULL valued holes in the VN_EXPR_MAP turn out to be very // large, it may be better to use a more compact representation for // this map. // // Currently, we never expect to see Top() operands in any expressions // other than phi nodes, and as such the optimistic simplification of // other kinds of expressions is just there for generality and to support // potential future functionality. We can add more aggressive // simplification incrementally, while leaving open the possibility // that simplified VN_EXPRs may have Top() operands. // Ideally we should have various degrees of simplification. The most // aggressive version should always reduces an expression into a form // without any Top() values, since *any* value can be substituted for // a Top() value. Conceivably, there may be cases, however, where a // less agressive simplification algorithm is desirable (e.g. to keep // the simplification implementation simpler, or to delay the folding // of Top() values until more context is available). // This is then a note to keep adding more aggressive rules of // simplification, and perhaps allow various degrees of simplification. // // CONSTRAINTS: // // A UNARY VN_EXPR should never be a PARM expression, except when returned // as a result of "simplify()". // // A BINARY VN_EXPR cannot be a COMMA or RCOMMA expression. // // SEE ALSO: // // opt_vn_hashtab.h : A mapping from VN_EXPR::PTR to VN_VALNUM, based on // a hashing algorithm. // // opt_vn.h : Top level interface to the value-numbering // algorithms, and associated resultant maps. // // ==================================================================== // ==================================================================== #ifndef opt_vn_expr_INCLUDED #define opt_vn_expr_INCLUDED "opt_vn_expr.h" #include "segmented_array.h" // Some common universally applicable number for the chunksizes used in // segmented arrays, mainly used to minimize the number of instantiations // of SEGMENTED_ARRAY. // #define VN_BUFFER_CHUNKSIZE 256 //---------------------- A Value Number ------------------------ //-------------------------------------------------------------- // class VN_VALNUM { private: UINT32 _num; VN_VALNUM(UINT32 v): _num(v) {} static UINT32 _top() {return UINT32_MAX;} static UINT32 _bottom() {return 0U;} public: static VN_VALNUM First() {return VN_VALNUM(1);} static VN_VALNUM Next(const VN_VALNUM prev) { return VN_VALNUM(prev._num + 1); } static VN_VALNUM Top() {return VN_VALNUM(_top());} // Matches all static VN_VALNUM Bottom() {return VN_VALNUM(_bottom());} // Matches none static VN_VALNUM Vn(UINT32 i) {return VN_VALNUM(i);} // For internal use! VN_VALNUM() : _num(_bottom()) {} VN_VALNUM(const VN_VALNUM &v) : _num(v._num) {} VN_VALNUM &operator= (const VN_VALNUM &v) {_num = v._num; return *this;} BOOL operator< (const VN_VALNUM &v) const {return _num < v._num;} BOOL operator> (const VN_VALNUM &v) const {return _num > v._num;} BOOL operator<= (const VN_VALNUM &v) const {return _num <= v._num;} BOOL operator>= (const VN_VALNUM &v) const {return _num >= v._num;} BOOL operator== (const VN_VALNUM &v) const {return _num == v._num;} BOOL operator!= (const VN_VALNUM &v) const {return _num != v._num;} BOOL is_bottom() const {return _num == _bottom();} BOOL is_top() const {return _num == _top();} BOOL equivalent_to(const VN_VALNUM &v) const { return (!(is_bottom() || v.is_bottom()) && (_num == v._num || is_top() || v.is_top())); } UINT32 ordinal() const {return _num;} // Only for use by VN_EXPR_MAP! void print(FILE *fp = stderr) const; INT32 sprint(char *buf) const; // buf must be large enough to hold "vnNNN"! }; // VN_VALNUM //---------------- A Value Number Expression ------------------- //-------------------------------------------------------------- // class VN; // Defined in opt_vn.h class VN_EXPR { public: typedef VN_EXPR *PTR; typedef const VN_EXPR *CONST_PTR; protected: static MEM_POOL *_Mpool; public: // This enumeration should be replaced by an enumeration in PHI_NODE // when we upgrade our intermediate representatiojn to support gated // phi nodes. I just insert it here now as a temporary placeholder. // enum PHI_TAG {PHI_TAG_UNKNOWN}; // The kinds of expressions a VN_EXPR may represent. // enum KIND {LITERAL, // Constant value UNARY, // One operand BINARY, // Two operands TERNARY, // Three operands INTR_OP, // Intrinsic function call PHI, // SSA Phi node LDA_ADDR, // A symbol's address ARRAY_ADDR, // An array element's address MEMLOC}; // The value of a memory location // A call to activate the memory allocation scheme for VN_EXPR // objects. Such objects should always be created using one of // the Create_xxx() methods, and should always be deleted using the // "free()" method. This method MUST be called before any other // method of the VN_EXPR class. If there is already a free-list // active when this method is called, then the old one will be // discarded but not reclaimed. // static void Init_Free_Lists(MEM_POOL *mpool = Malloc_Mem_Pool); // The following method will reclaim memory for all VN_EXPR nodes // currently accumulated on free lists, and it will reclaim memory // for the free-list itself. This is the ONLY way to reclaim // VN_EXPR memory! Following this call, a new call to Init_Free_Lists() // is needed before any call to Create_xxx() methods. Never call this // method before all VN_EXPR objects are free()'ed (i.e. until they are // all on the free-list). // static void Reclaim_Free_Lists(); // The following are constructors for the various kinds of expressions // we handle. The operands for expressions with a variable number of // operands (INTRINISC_OP, PHI and ARRAY_ADDR objects) must be set with // separate calls to "set_opnd()"; initially such operands are // VN_VALNUM::Bottom(). // // The value number operands to an ARRAY_ADDR should always be set in // the following order (same order as for an OPR_ARRAY whirl node): // // opnd(0) == base_address // opnd(1..num_dims()) == dimension_size // opnd(num_dims()+1..num_dims()+num_dims()) == index // static PTR Create_Literal(const TCON &tcon); static PTR Create_Unary(OPCODE opc, const VN_VALNUM &vn1); static PTR Create_Binary(OPCODE opc, const VN_VALNUM &vn1, const VN_VALNUM &vn2); static PTR Create_Ternary(OPCODE opc, const VN_VALNUM &vn1, const VN_VALNUM &vn2, const VN_VALNUM &vn3); static PTR Create_Intr_Op(INTRINSIC intr_opc, UINT32 num_opnds); static PTR Create_Phi(UINT32 num_opnds, IDTYPE block_id, PHI_TAG phi_tag = PHI_TAG_UNKNOWN); static PTR Create_Lda_Addr(INT32 lda_cr_id); static PTR Create_Array_Addr(WN_ESIZE esize, INT32 num_dims); static PTR Create_Memloc(MTYPE dsctype, const VN_VALNUM &bytesize, const VN_VALNUM &offset, const VN_VALNUM &base_addr, const VN_VALNUM &vsym_valnum); // The following will put "this" on a free list, and is the only // way to set a VN_EXPR object up for memory deallocation. // virtual void free() = 0; // Accessors: The kind() and num_opnds() determine which of the following // accessors are valid for a VN_EXPR. Note that operands are enumerated // starting at i=0. The default implementations, for those that have one, // will assert when the method is called. // virtual KIND get_kind() const = 0; virtual UINT32 get_num_opnds() const = 0; virtual VN_VALNUM get_opnd(UINT i=0) const; // All, but LITERAL/LDA/MEMLOC virtual BOOL has_top_opnd() const = 0; virtual BOOL has_bottom_opnd() const = 0; virtual OPCODE get_opc() const; // UNARY,BINARY,TERNARY virtual INTRINSIC get_intr_opc() const; // INTR_OP virtual PHI_TAG get_phi_tag() const; // PHI virtual IDTYPE get_block_id() const; // PHI virtual const TCON &get_tcon() const; // LITERAL virtual INT32 get_lda_cr_id() const; // LDA virtual INT32 get_num_dims() const; // ARRAY_ADDR virtual WN_ESIZE get_esize() const; // ARRAY_ADDR virtual MTYPE get_dsctype() const; // MEMLOC virtual VN_VALNUM get_bytesize() const; // MEMLOC virtual VN_VALNUM get_offset() const; // MEMLOC virtual VN_VALNUM get_base_addr() const; // MEMLOC virtual VN_VALNUM get_vsym(UINT i=0) const; // MEMLOC/INTR_OP (ivar mu) // Modifiers: // // set_opnd() will change the given operand of "this" expression, where // operand numbers are zero (0) based. set_opnd_vsym() will change // the vsym associated with the given parameter of "this" INTR_OP // expression, where the parameter numbers (i) are zero based. // // simplify() will try to fold "this" expression into a simpler // new expression or into a value number. When successful, "this" // expression will be freed up (this->free()), and a new expression // will be returned; otherwise, this is returned. Note that simplify // always returns a new expression with fewer operands than "this" // expression (except when a unary expression folds into a value-number). // When the expression folds into a single value number, a unary // OPC_VPARM expression is returned. Such an expression cannot be // hashed, and MUST BE SPECIALLY RECOGNIZED BY THE CLIENT of this // class. An expression with a Bottom() operand will always simplify // to a Bottom() value number. // virtual void set_opnd(UINT32 i, VN_VALNUM vn); virtual void set_opnd_vsym(UINT32 i, VN_VALNUM vn); // INTR_OP virtual PTR simplify(VN *v) = 0; // Any VN_EXPR can be hashed into a value suited for distribution // across a hash-table (see opt_vn_hashtab.h). Hashing will apply // canonicalization rules such as commutativity to catch as many // equivalences as possible, which means this expression may change // as a side-effect. This method should never be called when // this->has_top_opnd() || this->has_bottom_opnd()! // virtual size_t hash() = 0; // Inequality/Equality tests: // virtual BOOL is_equal_to(CONST_PTR expr) const = 0; virtual void print(FILE *fp = stderr) const = 0; }; // VN_EXPR //-------------- A Value Number Expression Map ----------------- //-------------------------------------------------------------- // class VN_EXPR_MAP { private: SEGMENTED_ARRAY _map; public: VN_EXPR_MAP(MEM_POOL *mpool): _map(mpool) {} ~VN_EXPR_MAP() { for (INT32 i = _map.Size() - 1; i >= 0; i--) if (_map[i] != NULL) _map[i]->free(); _map.Delete_last(_map.Size()); } // Resets all expressions referenced in the map (puts them on free- // lists) between the two given value numbers provided (inclusively), // where is_true(from_vn < to_vn) for the call to have any effect. // void reset_exprs(VN_VALNUM from_vn, VN_VALNUM to_vn) { INT32 max = (to_vn.ordinal() < _map.Size()? to_vn.ordinal() : _map.Size() - 1); for (INT32 i = from_vn.ordinal(); i <= max; i++) if (_map[i] != NULL) { _map[i]->free(); _map[i] = NULL; } } // Resets all expressions referenced in the map (puts them on free- // lists), and sets all value numbers to map to NULL expressions. // void reset_all_exprs() { reset_exprs(first(), last()); } // First value number in the mapping. Use VN_VALNUM::Next() to iterate. // Returns VN_VALNUM::Bottom() when the mapping is empty. // VN_VALNUM first() const { return (_map.Size() > 0? VN_VALNUM::First() : VN_VALNUM::Bottom()); } // Last value number in the mapping. Returns VN_VALNUM::Bottom() // when the mapping is empty. // VN_VALNUM last() const { return (_map.Size() > 0? VN_VALNUM::Vn(_map.Size() - 1) : VN_VALNUM::Bottom()); } // Always NULL for Top() and Bottom(). // VN_EXPR::PTR operator[] (const VN_VALNUM& v) const { if (v.is_top() || v.is_bottom()) return NULL; else { const UINT32 i = v.ordinal(); return ((i >= _map.Size())? NULL : _map[i]); } } // operator[] // Never call this for a Top() or Bottom() value number. Sets // a mapping as indicated (creating a new one if none exists). // void set_map(const VN_VALNUM& v, VN_EXPR::PTR expr) { FmtAssert(!(v.is_top() || v.is_bottom()), ("Illegal value number in call to VN_EXPR_MAP::set_map")); { const UINT32 i = v.ordinal(); for (UINT32 sz = _map.Size(); sz <= (i+1); _map.New_entry(sz) = NULL); _map[i] = expr; } } // set_map }; // VN_EXPR_MAP #endif // opt_vn_expr_INCLUDED