summaryrefslogtreecommitdiff
path: root/gcc/tree-ssa-scopedtables.h
blob: df304aedbf4f05a7523e4cbaae7777a2ab51172f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
/* Header file for SSA dominator optimizations.
   Copyright (C) 2013-2017 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_TREE_SSA_SCOPED_TABLES_H
#define GCC_TREE_SSA_SCOPED_TABLES_H

/* Representation of a "naked" right-hand-side expression, to be used
   in recording available expressions in the expression hash table.  */

enum expr_kind
{
  EXPR_SINGLE,
  EXPR_UNARY,
  EXPR_BINARY,
  EXPR_TERNARY,
  EXPR_CALL,
  EXPR_PHI
};

struct hashable_expr
{
  tree type;
  enum expr_kind kind;
  union {
    struct { tree rhs; } single;
    struct { enum tree_code op;  tree opnd; } unary;
    struct { enum tree_code op;  tree opnd0, opnd1; } binary;
    struct { enum tree_code op;  tree opnd0, opnd1, opnd2; } ternary;
    struct { gcall *fn_from; bool pure; size_t nargs; tree *args; } call;
    struct { size_t nargs; tree *args; } phi;
  } ops;
};

/* Structure for recording known value of a conditional expression.

   Clients build vectors of these objects to record known values
   that occur on edges.  */

struct cond_equivalence
{
  /* The condition, in a HASHABLE_EXPR form.  */
  struct hashable_expr cond;

  /* The result of the condition (true or false.  */
  tree value;
};

/* Structure for entries in the expression hash table.  */

typedef class expr_hash_elt * expr_hash_elt_t;

class expr_hash_elt
{
 public:
  expr_hash_elt (gimple *, tree);
  expr_hash_elt (tree);
  expr_hash_elt (struct hashable_expr *, tree);
  expr_hash_elt (class expr_hash_elt &);
  ~expr_hash_elt ();
  void print (FILE *);
  tree vop (void) { return m_vop; }
  tree lhs (void) { return m_lhs; }
  struct hashable_expr *expr (void) { return &m_expr; }
  expr_hash_elt *stamp (void) { return m_stamp; }
  hashval_t hash (void) { return m_hash; }

 private:
  /* The expression (rhs) we want to record.  */
  struct hashable_expr m_expr;

  /* The value (lhs) of this expression.  */
  tree m_lhs;

  /* The virtual operand associated with the nearest dominating stmt
     loading from or storing to expr.  */
  tree m_vop;

  /* The hash value for RHS.  */
  hashval_t m_hash;

  /* A unique stamp, typically the address of the hash
     element itself, used in removing entries from the table.  */
  struct expr_hash_elt *m_stamp;

  /* We should never be making assignments between objects in this class.
     Though it might allow us to exploit C++11 move semantics if we
     defined the move constructor and move assignment operator.  */
  expr_hash_elt& operator= (const expr_hash_elt&);
};

/* Hashtable helpers.  */

struct expr_elt_hasher : pointer_hash <expr_hash_elt>
{
  static inline hashval_t hash (const value_type &p)
    { return p->hash (); }
  static bool equal (const value_type &, const compare_type &);
  static inline void remove (value_type &element)
    { delete element; }
};


/* This class defines a unwindable expression equivalence table
   layered on top of the expression hash table.

   Essentially it's just a stack of available expression value pairs with
   a special marker (NULL, NULL) to indicate unwind points.   */

class avail_exprs_stack
{
 public:
  /* We need access to the AVAIL_EXPR hash table so that we can
     remove entries from the hash table when unwinding the stack.  */
  avail_exprs_stack (hash_table<expr_elt_hasher> *table)
    { m_stack.create (20); m_avail_exprs = table; }
  ~avail_exprs_stack (void) { m_stack.release (); }

  /* Push the unwinding marker onto the stack.  */
  void push_marker (void) { record_expr (NULL, NULL, 'M'); }

  /* Restore the AVAIL_EXPRs table to its state when the last marker
     was pushed.  */
  void pop_to_marker (void);

  /* Record a single available expression that can be unwound.  */
  void record_expr (expr_hash_elt_t, expr_hash_elt_t, char);

  /* Get the underlying hash table.  Would this be better as
     class inheritance?  */
  hash_table<expr_elt_hasher> *avail_exprs (void)
    { return m_avail_exprs; }

  /* Lookup and conditionally insert an expression into the table,
     recording enough information to unwind as needed.  */
  tree lookup_avail_expr (gimple *, bool, bool);

  void record_cond (cond_equivalence *);

 private:
  vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
  hash_table<expr_elt_hasher> *m_avail_exprs;

  /* We do not allow copying this object or initializing one
     from another.  */
  avail_exprs_stack& operator= (const avail_exprs_stack&);
  avail_exprs_stack (class avail_exprs_stack &);
};

/* This class defines an unwindable const/copy equivalence table
   layered on top of SSA_NAME_VALUE/set_ssa_name_value.

   Essentially it's just a stack of name,prev value pairs with a
   special marker (NULL) to indicate unwind points.  */

class const_and_copies
{
 public:
  const_and_copies (void) { m_stack.create (20); };
  ~const_and_copies (void) { m_stack.release (); }

  /* Push the unwinding marker onto the stack.  */
  void push_marker (void) { m_stack.safe_push (NULL_TREE); }

  /* Restore the const/copies table to its state when the last marker
     was pushed.  */
  void pop_to_marker (void);

  /* Record a single const/copy pair that can be unwound.  This version
     may follow the value chain for the RHS.  */
  void record_const_or_copy (tree, tree);

  /* Record a single const/copy pair that can be unwound.  This version
     does not follow the value chain for the RHS.  */
  void record_const_or_copy_raw (tree, tree, tree);

  /* Special entry point when we want to provide an explicit previous
     value for the first argument.  Try to get rid of this in the future. 

     This version may also follow the value chain for the RHS.  */
  void record_const_or_copy (tree, tree, tree);

 private:
  vec<tree> m_stack;
  const_and_copies& operator= (const const_and_copies&);
  const_and_copies (class const_and_copies &);
};

void initialize_expr_from_cond (tree cond, struct hashable_expr *expr);
void record_conditions (vec<cond_equivalence> *p, tree, tree);

#endif /* GCC_TREE_SSA_SCOPED_TABLES_H */