[thirdparty/gcc.git] / gcc / gimple-predicate-analysis.h

/* Support for simple predicate analysis.

   Copyright (C) 2021 Free Software Foundation, Inc.
   Contributed by Martin Sebor <msebor@redhat.com>

   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 GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
#define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED

#define MAX_NUM_CHAINS 8
#define MAX_CHAIN_LEN 5
#define MAX_POSTDOM_CHECK 8
#define MAX_SWITCH_CASES 40

/* Represents a simple Boolean predicate.  */
struct pred_info
{
  tree pred_lhs;
  tree pred_rhs;
  enum tree_code cond_code;
  bool invert;
};

/* The type to represent a sequence of predicates grouped
   with .AND. operation.  */
typedef vec<pred_info, va_heap, vl_ptr> pred_chain;

/* The type to represent a sequence of pred_chains grouped
   with .OR. operation.  */
typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;

/* Represents a complex Boolean predicate expression.  */
class predicate
{
 public:
  /* Base function object type used to determine whether an expression
     is of interest.  */
  struct func_t
  {
    typedef unsigned phi_arg_set_t;

    /* Return true if the argument is an expression of interest.  */
    virtual bool operator()(tree) = 0;
    /* Return a bitset of PHI arguments of interest.  By default returns
       bitset with a bit set for each argument.  Should be called in
       the overriden function first and, if nonzero, the result then
       refined as appropriate.  */
    virtual phi_arg_set_t phi_arg_set (gphi *);

    /* Maximum number of PHI arguments supported by phi_arg_set().  */
    static constexpr unsigned max_phi_args =
      sizeof (phi_arg_set_t) * CHAR_BIT;
  };

  /* Construct with the specified EVAL object.  */
  predicate (func_t &eval)
    : m_preds (vNULL), m_eval (eval), m_use_expr () { }

  /* Copy.  */
  predicate (const predicate &rhs)
    : m_preds (vNULL), m_eval (rhs.m_eval), m_use_expr ()
    {
      *this = rhs;
    }

  predicate (basic_block, basic_block, func_t &);

  ~predicate ();

  /* Assign.  */
  predicate& operator= (const predicate &);

  bool is_empty () const
  {
    return m_preds.is_empty ();
  }

  const pred_chain_union chain () const
  {
    return m_preds;
  }

  /* Return true if the use by a statement in the basic block of
     a PHI operand is ruled out (i.e., guarded) by *THIS.  */
  bool is_use_guarded (gimple *, basic_block, gphi *, unsigned);

  void init_from_control_deps (const vec<edge> *, unsigned);

  void dump (gimple *, const char *) const;

  void normalize (gimple * = NULL, bool = false);
  void simplify (gimple * = NULL, bool = false);

  bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
		       hash_set<gphi *> *);

  /* Return the predicate expression guarding the definition of
     the interesting variable, optionally inverted.  */
  tree def_expr (bool = false) const;
  /* Return the predicate expression guarding the use of the interesting
     variable.  */
  tree use_expr () const;

  tree expr (bool = false) const;

private:
  bool includes (const pred_chain &) const;
  bool superset_of (const predicate &) const;
  bool overlap (gphi *, unsigned, hash_set<gphi *> *);
  bool use_cannot_happen (gphi *, unsigned);

  bool init_from_phi_def (gphi *);

  void push_pred (const pred_info &);

  /* Normalization functions.  */
  void normalize (pred_chain *, pred_info, tree_code, pred_chain *,
		  hash_set<tree> *);

  void normalize (const pred_info &);
  void normalize (const pred_chain &);

  /* Simplification functions.  */
  bool simplify_2 ();
  bool simplify_3 ();
  bool simplify_4 ();

private:
  /* Representation of the predicate expression(s).  */
  pred_chain_union m_preds;
  /* Callback to evaluate an operand.  Return true if it's interesting.  */
  func_t &m_eval;
  /* The predicate expression guarding the use of the interesting
     variable.  */
  tree m_use_expr;
};

/* Bit mask handling macros.  */
#define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
#define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
#define MASK_EMPTY(mask) (mask == 0)

#endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
Commit	Line	Data
94c12ffa MS	1	/* Support for simple predicate analysis.
	2
	3	Copyright (C) 2021 Free Software Foundation, Inc.
	4	Contributed by Martin Sebor <msebor@redhat.com>
	5
	6	This file is part of GCC.
	7
	8	GCC is free software; you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 3, or (at your option)
	11	any later version.
	12
	13	GCC is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with GCC; see the file COPYING3. If not see
	20	<http://www.gnu.org/licenses/>. */
	21
	22	#ifndef GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
	23	#define GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED
	24
	25	#define MAX_NUM_CHAINS 8
	26	#define MAX_CHAIN_LEN 5
	27	#define MAX_POSTDOM_CHECK 8
	28	#define MAX_SWITCH_CASES 40
	29
	30	/* Represents a simple Boolean predicate. */
	31	struct pred_info
	32	{
	33	tree pred_lhs;
	34	tree pred_rhs;
	35	enum tree_code cond_code;
	36	bool invert;
	37	};
	38
	39	/* The type to represent a sequence of predicates grouped
	40	with .AND. operation. */
	41	typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
	42
	43	/* The type to represent a sequence of pred_chains grouped
	44	with .OR. operation. */
	45	typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
	46
	47	/* Represents a complex Boolean predicate expression. */
	48	class predicate
	49	{
	50	public:
	51	/* Base function object type used to determine whether an expression
	52	is of interest. */
	53	struct func_t
	54	{
	55	typedef unsigned phi_arg_set_t;
	56
	57	/* Return true if the argument is an expression of interest. */
	58	virtual bool operator()(tree) = 0;
	59	/* Return a bitset of PHI arguments of interest. By default returns
	60	bitset with a bit set for each argument. Should be called in
	61	the overriden function first and, if nonzero, the result then
	62	refined as appropriate. */
	63	virtual phi_arg_set_t phi_arg_set (gphi *);
	64
65	/* Maximum number of PHI arguments supported by phi_arg_set(). */
66	static constexpr unsigned max_phi_args =
67	sizeof (phi_arg_set_t) * CHAR_BIT;
68	};
69
70	/* Construct with the specified EVAL object. */
71	predicate (func_t &eval)
72	: m_preds (vNULL), m_eval (eval), m_use_expr () { }
73
74	/* Copy. */
75	predicate (const predicate &rhs)
76	: m_preds (vNULL), m_eval (rhs.m_eval), m_use_expr ()
77	{
78	*this = rhs;
79	}
80
81	predicate (basic_block, basic_block, func_t &);
82
83	~predicate ();
84
85	/* Assign. */
86	predicate& operator= (const predicate &);
87
88	bool is_empty () const
89	{
90	return m_preds.is_empty ();
91	}
92
93	const pred_chain_union chain () const
94	{
95	return m_preds;
96	}
97
98	/* Return true if the use by a statement in the basic block of
99	a PHI operand is ruled out (i.e., guarded) by THIS. /
100	bool is_use_guarded (gimple , basic_block, gphi , unsigned);
101
102	void init_from_control_deps (const vec<edge> *, unsigned);
103
104	void dump (gimple , const char ) const;
105
106	void normalize (gimple * = NULL, bool = false);
107	void simplify (gimple * = NULL, bool = false);
108
109	bool is_use_guarded (gimple , basic_block, gphi , unsigned,
110	hash_set<gphi > );
111
112	/* Return the predicate expression guarding the definition of
113	the interesting variable, optionally inverted. */
114	tree def_expr (bool = false) const;
115	/* Return the predicate expression guarding the use of the interesting
116	variable. */
117	tree use_expr () const;
118
119	tree expr (bool = false) const;
120
121	private:
122	bool includes (const pred_chain &) const;
123	bool superset_of (const predicate &) const;
124	bool overlap (gphi , unsigned, hash_set<gphi > *);
125	bool use_cannot_happen (gphi *, unsigned);
126
127	bool init_from_phi_def (gphi *);
128
129	void push_pred (const pred_info &);
130
131	/* Normalization functions. */
132	void normalize (pred_chain , pred_info, tree_code, pred_chain ,
133	hash_set<tree> *);
134
135	void normalize (const pred_info &);
136	void normalize (const pred_chain &);
137
138	/* Simplification functions. */
139	bool simplify_2 ();
140	bool simplify_3 ();
141	bool simplify_4 ();
142
143	private:
144	/* Representation of the predicate expression(s). */
145	pred_chain_union m_preds;
146	/* Callback to evaluate an operand. Return true if it's interesting. */
147	func_t &m_eval;
148	/* The predicate expression guarding the use of the interesting
149	variable. */
150	tree m_use_expr;
151	};
152
153	/* Bit mask handling macros. */
154	#define MASK_SET_BIT(mask, pos) mask \|= (1 << pos)
155	#define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
156	#define MASK_EMPTY(mask) (mask == 0)
157
158	#endif // GIMPLE_PREDICATE_ANALYSIS_H_INCLUDED