/* Header file for SSA dominator optimizations.
   Copyright (C) 2013-2015 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 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 ();

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

 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.  */
  void record_const_or_copy (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.  */
  void record_const_or_copy (tree, tree, tree);

  /* When threading we need to invalidate certain equivalences after
     following a loop backedge.  The entries we need to invalidate will
     always be in this unwindable stack.  This entry point handles
     finding and invalidating those entries.  */
  void invalidate (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);

#endif /* GCC_TREE_SSA_SCOPED_TABLES_H */