1 /* Header file for SSA dominator optimizations. 2 Copyright (C) 2013-2017 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 *); 77 tree vop (void) { return m_vop; } 78 tree lhs (void) { return m_lhs; } 79 struct hashable_expr *expr (void) { return &m_expr; } 80 expr_hash_elt *stamp (void) { return m_stamp; } 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 { 111 static inline hashval_t hash (const value_type &p) 112 { return p->hash (); } 113 static bool equal (const value_type &, const compare_type &); 114 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. */ 130 avail_exprs_stack (hash_table<expr_elt_hasher> *table) 131 { m_stack.create (20); m_avail_exprs = table; } 132 ~avail_exprs_stack (void) { m_stack.release (); } 133 134 /* Push the unwinding marker onto the stack. */ 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? */ 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 /* We do not allow copying this object or initializing one 160 from another. */ 161 avail_exprs_stack& operator= (const avail_exprs_stack&); 162 avail_exprs_stack (class avail_exprs_stack &); 163 }; 164 165 /* This class defines an unwindable const/copy equivalence table 166 layered on top of SSA_NAME_VALUE/set_ssa_name_value. 167 168 Essentially it's just a stack of name,prev value pairs with a 169 special marker (NULL) to indicate unwind points. */ 170 171 class const_and_copies 172 { 173 public: 174 const_and_copies (void) { m_stack.create (20); }; 175 ~const_and_copies (void) { m_stack.release (); } 176 177 /* Push the unwinding marker onto the stack. */ 178 void push_marker (void) { m_stack.safe_push (NULL_TREE); } 179 180 /* Restore the const/copies table to its state when the last marker 181 was pushed. */ 182 void pop_to_marker (void); 183 184 /* Record a single const/copy pair that can be unwound. This version 185 may follow the value chain for the RHS. */ 186 void record_const_or_copy (tree, tree); 187 188 /* Record a single const/copy pair that can be unwound. This version 189 does not follow the value chain for the RHS. */ 190 void record_const_or_copy_raw (tree, tree, tree); 191 192 /* Special entry point when we want to provide an explicit previous 193 value for the first argument. Try to get rid of this in the future. 194 195 This version may also follow the value chain for the RHS. */ 196 void record_const_or_copy (tree, tree, tree); 197 198 private: 199 vec<tree> m_stack; 200 const_and_copies& operator= (const const_and_copies&); 201 const_and_copies (class const_and_copies &); 202 }; 203 204 void initialize_expr_from_cond (tree cond, struct hashable_expr *expr); 205 void record_conditions (vec<cond_equivalence> *p, tree, tree); 206 207 #endif /* GCC_TREE_SSA_SCOPED_TABLES_H */ 208