gcc/tree-ssa-scopedtables.h

   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   /* 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:
 179   const_and_copies (void) { m_stack.create (20); };
 180   ~const_and_copies (void) { m_stack.release (); }
 181
 182   /* Push the unwinding marker onto the stack.  */
 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 */