1 /* Header file for SSA dominator optimizations. 2 Copyright (C) 2013-2019 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 recording known value of a conditional expression. 51 52 Clients build vectors of these objects to record known values 53 that occur on edges. */ 54 55 struct cond_equivalence 56 { 57 /* The condition, in a HASHABLE_EXPR form. */ 58 struct hashable_expr cond; 59 60 /* The result of the condition (true or false. */ 61 tree value; 62 }; 63 64 /* Structure for entries in the expression hash table. */ 65 66 typedef class expr_hash_elt * expr_hash_elt_t; 67 68 class expr_hash_elt 69 { 70 public: 71 expr_hash_elt (gimple *, tree); 72 expr_hash_elt (tree); 73 expr_hash_elt (struct hashable_expr *, tree); 74 expr_hash_elt (class expr_hash_elt &); 75 ~expr_hash_elt (); 76 void print (FILE *); vop(void)77 tree vop (void) { return m_vop; } lhs(void)78 tree lhs (void) { return m_lhs; } expr(void)79 struct hashable_expr *expr (void) { return &m_expr; } stamp(void)80 expr_hash_elt *stamp (void) { return m_stamp; } hash(void)81 hashval_t hash (void) { return m_hash; } 82 83 private: 84 /* The expression (rhs) we want to record. */ 85 struct hashable_expr m_expr; 86 87 /* The value (lhs) of this expression. */ 88 tree m_lhs; 89 90 /* The virtual operand associated with the nearest dominating stmt 91 loading from or storing to expr. */ 92 tree m_vop; 93 94 /* The hash value for RHS. */ 95 hashval_t m_hash; 96 97 /* A unique stamp, typically the address of the hash 98 element itself, used in removing entries from the table. */ 99 struct expr_hash_elt *m_stamp; 100 101 /* We should never be making assignments between objects in this class. 102 Though it might allow us to exploit C++11 move semantics if we 103 defined the move constructor and move assignment operator. */ 104 expr_hash_elt& operator= (const expr_hash_elt&); 105 }; 106 107 /* Hashtable helpers. */ 108 109 struct expr_elt_hasher : pointer_hash <expr_hash_elt> 110 { hashexpr_elt_hasher111 static inline hashval_t hash (const value_type &p) 112 { return p->hash (); } 113 static bool equal (const value_type &, const compare_type &); removeexpr_elt_hasher114 static inline void remove (value_type &element) 115 { delete element; } 116 }; 117 118 119 /* This class defines a unwindable expression equivalence table 120 layered on top of the expression hash table. 121 122 Essentially it's just a stack of available expression value pairs with 123 a special marker (NULL, NULL) to indicate unwind points. */ 124 125 class avail_exprs_stack 126 { 127 public: 128 /* We need access to the AVAIL_EXPR hash table so that we can 129 remove entries from the hash table when unwinding the stack. */ avail_exprs_stack(hash_table<expr_elt_hasher> * table)130 avail_exprs_stack (hash_table<expr_elt_hasher> *table) 131 { m_stack.create (20); m_avail_exprs = table; } ~avail_exprs_stack(void)132 ~avail_exprs_stack (void) { m_stack.release (); } 133 134 /* Push the unwinding marker onto the stack. */ push_marker(void)135 void push_marker (void) { record_expr (NULL, NULL, 'M'); } 136 137 /* Restore the AVAIL_EXPRs table to its state when the last marker 138 was pushed. */ 139 void pop_to_marker (void); 140 141 /* Record a single available expression that can be unwound. */ 142 void record_expr (expr_hash_elt_t, expr_hash_elt_t, char); 143 144 /* Get the underlying hash table. Would this be better as 145 class inheritance? */ avail_exprs(void)146 hash_table<expr_elt_hasher> *avail_exprs (void) 147 { return m_avail_exprs; } 148 149 /* Lookup and conditionally insert an expression into the table, 150 recording enough information to unwind as needed. */ 151 tree lookup_avail_expr (gimple *, bool, bool); 152 153 void record_cond (cond_equivalence *); 154 155 private: 156 vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack; 157 hash_table<expr_elt_hasher> *m_avail_exprs; 158 159 /* For some assignments where the RHS is a binary operator, if we know 160 a equality relationship between the operands, we may be able to compute 161 a result, even if we don't know the exact value of the operands. */ 162 tree simplify_binary_operation (gimple *, class expr_hash_elt); 163 164 /* We do not allow copying this object or initializing one 165 from another. */ 166 avail_exprs_stack& operator= (const avail_exprs_stack&); 167 avail_exprs_stack (class avail_exprs_stack &); 168 }; 169 170 /* This class defines an unwindable const/copy equivalence table 171 layered on top of SSA_NAME_VALUE/set_ssa_name_value. 172 173 Essentially it's just a stack of name,prev value pairs with a 174 special marker (NULL) to indicate unwind points. */ 175 176 class const_and_copies 177 { 178 public: const_and_copies(void)179 const_and_copies (void) { m_stack.create (20); }; ~const_and_copies(void)180 ~const_and_copies (void) { m_stack.release (); } 181 182 /* Push the unwinding marker onto the stack. */ push_marker(void)183 void push_marker (void) { m_stack.safe_push (NULL_TREE); } 184 185 /* Restore the const/copies table to its state when the last marker 186 was pushed. */ 187 void pop_to_marker (void); 188 189 /* Record a single const/copy pair that can be unwound. This version 190 may follow the value chain for the RHS. */ 191 void record_const_or_copy (tree, tree); 192 193 /* Special entry point when we want to provide an explicit previous 194 value for the first argument. Try to get rid of this in the future. 195 196 This version may also follow the value chain for the RHS. */ 197 void record_const_or_copy (tree, tree, tree); 198 199 private: 200 /* Record a single const/copy pair that can be unwound. This version 201 does not follow the value chain for the RHS. */ 202 void record_const_or_copy_raw (tree, tree, tree); 203 204 vec<tree> m_stack; 205 const_and_copies& operator= (const const_and_copies&); 206 const_and_copies (class const_and_copies &); 207 }; 208 209 void initialize_expr_from_cond (tree cond, struct hashable_expr *expr); 210 void record_conditions (vec<cond_equivalence> *p, tree, tree); 211 212 #endif /* GCC_TREE_SSA_SCOPED_TABLES_H */ 213