1 /* Header file for SSA dominator optimizations.
2    Copyright (C) 2013-2020 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   class 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, expr_hash_elt ** = NULL);
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