Factor predidacte analysis out of tree-ssa-uninit.c into its own module.

gcc/ChangeLog:

	* Makefile.in (OBJS): Add gimple-predicate-analysis.o.
	* tree-ssa-uninit.c (max_phi_args): Move to gimple-predicate-analysis.
	(MASK_SET_BIT, MASK_TEST_BIT, MASK_EMPTY): Same.
	(check_defs): Add comment.
	(can_skip_redundant_opnd): Update comment.
	(compute_uninit_opnds_pos): Adjust to namespace change.
	(find_pdom): Move to gimple-predicate-analysis.cc.
	(find_dom): Same.
	(struct uninit_undef_val_t): New.
	(is_non_loop_exit_postdominating): Move to gimple-predicate-analysis.cc.
	(find_control_equiv_block): Same.
	(MAX_NUM_CHAINS, MAX_CHAIN_LEN, MAX_POSTDOM_CHECK): Same.
	(MAX_SWITCH_CASES): Same.
	(compute_control_dep_chain): Same.
	(find_uninit_use): Use predicate analyzer.
	(struct pred_info): Move to gimple-predicate-analysis.
	(convert_control_dep_chain_into_preds): Same.
	(find_predicates): Same.
	(collect_phi_def_edges): Same.
	(warn_uninitialized_phi): Use predicate analyzer.
	(find_def_preds): Move to gimple-predicate-analysis.
	(dump_pred_info): Same.
	(dump_pred_chain): Same.
	(dump_predicates): Same.
	(destroy_predicate_vecs): Remove.
	(execute_late_warn_uninitialized): New.
	(get_cmp_code): Move to gimple-predicate-analysis.
	(is_value_included_in): Same.
	(value_sat_pred_p): Same.
	(find_matching_predicate_in_rest_chains): Same.
	(is_use_properly_guarded): Same.
	(prune_uninit_phi_opnds): Same.
	(find_var_cmp_const): Same.
	(use_pred_not_overlap_with_undef_path_pred): Same.
	(pred_equal_p): Same.
	(is_neq_relop_p): Same.
	(is_neq_zero_form_p): Same.
	(pred_expr_equal_p): Same.
	(is_pred_expr_subset_of): Same.
	(is_pred_chain_subset_of): Same.
	(is_included_in): Same.
	(is_superset_of): Same.
	(pred_neg_p): Same.
	(simplify_pred): Same.
	(simplify_preds_2): Same.
	(simplify_preds_3): Same.
	(simplify_preds_4): Same.
	(simplify_preds): Same.
	(push_pred): Same.
	(push_to_worklist): Same.
	(get_pred_info_from_cmp): Same.
	(is_degenerated_phi): Same.
	(normalize_one_pred_1): Same.
	(normalize_one_pred): Same.
	(normalize_one_pred_chain): Same.
	(normalize_preds): Same.
	(can_one_predicate_be_invalidated_p): Same.
	(can_chain_union_be_invalidated_p): Same.
	(uninit_uses_cannot_happen): Same.
	(pass_late_warn_uninitialized::execute): Define.
	* gimple-predicate-analysis.cc: New file.
	* gimple-predicate-analysis.h: New file.

1 files changed, 158 insertions, 0 deletions

diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
new file mode 100644
index 0000000..fbf6f8e
--- /dev/null
+++ b/gcc/gimple-predicate-analysis.h
@@ -0,0 +1,158 @@
+/* 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