1 /* Header file for SSA dominator optimizations. 2 Copyright (C) 2013-2016 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #ifndef GCC_TREE_SSA_SCOPED_TABLES_H 21 #define GCC_TREE_SSA_SCOPED_TABLES_H 22 23 /* Representation of a "naked" right-hand-side expression, to be used 24 in recording available expressions in the expression hash table. */ 25 26 enum expr_kind 27 { 28 EXPR_SINGLE, 29 EXPR_UNARY, 30 EXPR_BINARY, 31 EXPR_TERNARY, 32 EXPR_CALL, 33 EXPR_PHI 34 }; 35 36 struct hashable_expr 37 { 38 tree type; 39 enum expr_kind kind; 40 union { 41 struct { tree rhs; } single; 42 struct { enum tree_code op; tree opnd; } unary; 43 struct { enum tree_code op; tree opnd0, opnd1; } binary; 44 struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary; 45 struct { gcall *fn_from; bool pure; size_t nargs; tree *args; } call; 46 struct { size_t nargs; tree *args; } phi; 47 } ops; 48 }; 49 50 /* Structure for entries in the expression hash table. */ 51 52 typedef class expr_hash_elt * expr_hash_elt_t; 53 54 class expr_hash_elt 55 { 56 public: 57 expr_hash_elt (gimple *, tree); 58 expr_hash_elt (tree); 59 expr_hash_elt (struct hashable_expr *, tree); 60 expr_hash_elt (class expr_hash_elt &); 61 ~expr_hash_elt (); 62 void print (FILE *); vop(void)63 tree vop (void) { return m_vop; } lhs(void)64 tree lhs (void) { return m_lhs; } expr(void)65 struct hashable_expr *expr (void) { return &m_expr; } stamp(void)66 expr_hash_elt *stamp (void) { return m_stamp; } hash(void)67 hashval_t hash (void) { return m_hash; } 68 69 private: 70 /* The expression (rhs) we want to record. */ 71 struct hashable_expr m_expr; 72 73 /* The value (lhs) of this expression. */ 74 tree m_lhs; 75 76 /* The virtual operand associated with the nearest dominating stmt 77 loading from or storing to expr. */ 78 tree m_vop; 79 80 /* The hash value for RHS. */ 81 hashval_t m_hash; 82 83 /* A unique stamp, typically the address of the hash 84 element itself, used in removing entries from the table. */ 85 struct expr_hash_elt *m_stamp; 86 87 /* We should never be making assignments between objects in this class. 88 Though it might allow us to exploit C++11 move semantics if we 89 defined the move constructor and move assignment operator. */ 90 expr_hash_elt& operator= (const expr_hash_elt&); 91 }; 92 93 /* Hashtable helpers. */ 94 95 struct expr_elt_hasher : pointer_hash <expr_hash_elt> 96 { hashexpr_elt_hasher97 static inline hashval_t hash (const value_type &p) 98 { return p->hash (); } 99 static bool equal (const value_type &, const compare_type &); removeexpr_elt_hasher100 static inline void remove (value_type &element) 101 { delete element; } 102 }; 103 104 105 /* This class defines a unwindable expression equivalence table 106 layered on top of the expression hash table. 107 108 Essentially it's just a stack of available expression value pairs with 109 a special marker (NULL, NULL) to indicate unwind points. */ 110 111 class avail_exprs_stack 112 { 113 public: 114 /* We need access to the AVAIL_EXPR hash table so that we can 115 remove entries from the hash table when unwinding the stack. */ avail_exprs_stack(hash_table<expr_elt_hasher> * table)116 avail_exprs_stack (hash_table<expr_elt_hasher> *table) 117 { m_stack.create (20); m_avail_exprs = table; } ~avail_exprs_stack(void)118 ~avail_exprs_stack (void) { m_stack.release (); } 119 120 /* Push the unwinding marker onto the stack. */ push_marker(void)121 void push_marker (void) { record_expr (NULL, NULL, 'M'); } 122 123 /* Restore the AVAIL_EXPRs table to its state when the last marker 124 was pushed. */ 125 void pop_to_marker (void); 126 127 /* Record a single available expression that can be unwound. */ 128 void record_expr (expr_hash_elt_t, expr_hash_elt_t, char); 129 130 /* Get the underlying hash table. Would this be better as 131 class inheritance? */ avail_exprs(void)132 hash_table<expr_elt_hasher> *avail_exprs (void) 133 { return m_avail_exprs; } 134 135 private: 136 vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack; 137 hash_table<expr_elt_hasher> *m_avail_exprs; 138 139 /* We do not allow copying this object or initializing one 140 from another. */ 141 avail_exprs_stack& operator= (const avail_exprs_stack&); 142 avail_exprs_stack (class avail_exprs_stack &); 143 }; 144 145 /* This class defines an unwindable const/copy equivalence table 146 layered on top of SSA_NAME_VALUE/set_ssa_name_value. 147 148 Essentially it's just a stack of name,prev value pairs with a 149 special marker (NULL) to indicate unwind points. */ 150 151 class const_and_copies 152 { 153 public: const_and_copies(void)154 const_and_copies (void) { m_stack.create (20); }; ~const_and_copies(void)155 ~const_and_copies (void) { m_stack.release (); } 156 157 /* Push the unwinding marker onto the stack. */ push_marker(void)158 void push_marker (void) { m_stack.safe_push (NULL_TREE); } 159 160 /* Restore the const/copies table to its state when the last marker 161 was pushed. */ 162 void pop_to_marker (void); 163 164 /* Record a single const/copy pair that can be unwound. This version 165 may follow the value chain for the RHS. */ 166 void record_const_or_copy (tree, tree); 167 168 /* Record a single const/copy pair that can be unwound. This version 169 does not follow the value chain for the RHS. */ 170 void record_const_or_copy_raw (tree, tree, tree); 171 172 /* Special entry point when we want to provide an explicit previous 173 value for the first argument. Try to get rid of this in the future. 174 175 This version may also follow the value chain for the RHS. */ 176 void record_const_or_copy (tree, tree, tree); 177 178 private: 179 vec<tree> m_stack; 180 const_and_copies& operator= (const const_and_copies&); 181 const_and_copies (class const_and_copies &); 182 }; 183 184 void initialize_expr_from_cond (tree cond, struct hashable_expr *expr); 185 186 #endif /* GCC_TREE_SSA_SCOPED_TABLES_H */ 187