[gcc r13-2170] Split uninit analysis from predicate analysis

[gcc r13-2170] Split uninit analysis from predicate analysis

[Richard Biener]

https://gcc.gnu.org/g:cd1216d581b44f14b93a427bf2e95ee37e394b8b

commit r13-2170-gcd1216d581b44f14b93a427bf2e95ee37e394b8b
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Aug 24 11:22:55 2022 +0200

    Split uninit analysis from predicate analysis
    
    This splits the API collected in gimple-predicate-analysis.h into
    what I'd call a predicate and assorted functionality plus utility
    used by the uninit pass that happens to use that.  I've tried to
    be minimalistic with refactoring, there's still recursive
    instantiation of uninit_analysis, the new class encapsulating a
    series of uninit analysis queries from the uninit pass.  But it
    at least should make the predicate part actually reusable and
    what predicate is dealt with is a little bit more clear in the
    uninit_analysis part.
    
    I will followup with moving the predicate implementation bits
    together in the gimple-predicate-analysis.cc file.
    
            * gimple-predicate-analysis.h (predicate): Split out
            non-predicate related functionality into ..
            (uninit_analysis): .. this new class.
            * gimple-predicate-analysis.cc: Refactor into two classes.
            * tree-ssa-uninit.cc (find_uninit_use): Use uninit_analysis.

Diff:
---
 gcc/gimple-predicate-analysis.cc | 116 ++++++++++++++++++++-------------------
 gcc/gimple-predicate-analysis.h  | 101 ++++++++++++++++++++--------------
 gcc/tree-ssa-uninit.cc           |   6 +-
 3 files changed, 121 insertions(+), 102 deletions(-)

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index f7170a8d068..8995c11a45c 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -483,19 +483,18 @@ find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
    Checking recursively into (1), the compiler can find out that only
    some_val (which is defined) can flow into (3) which is OK.  */
 
-static bool
-prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
-		 tree boundary_cst, tree_code cmp_code,
-		 predicate::func_t &eval,
-		 hash_set<gphi *> *visited_phis,
-		 bitmap *visited_flag_phis)
+bool
+uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
+				  tree boundary_cst, tree_code cmp_code,
+				  hash_set<gphi *> *visited_phis,
+				  bitmap *visited_flag_phis)
 {
   /* The Boolean predicate guarding the PHI definition.  Initialized
      lazily from PHI in the first call to is_use_guarded() and cached
      for subsequent iterations.  */
-  predicate def_preds (eval);
+  uninit_analysis def_preds (m_eval);
 
-  unsigned n = MIN (eval.max_phi_args, gimple_phi_num_args (flag_def));
+  unsigned n = MIN (m_eval.max_phi_args, gimple_phi_num_args (flag_def));
   for (unsigned i = 0; i < n; i++)
     {
       if (!MASK_TEST_BIT (opnds, i))
@@ -532,9 +531,9 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
 	  bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
 
 	  /* Now recursively try to prune the interesting phi args.  */
-	  unsigned opnds_arg_phi = eval.phi_arg_set (phi_arg_def);
+	  unsigned opnds_arg_phi = m_eval.phi_arg_set (phi_arg_def);
 	  if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def,
-				boundary_cst, cmp_code, eval, visited_phis,
+				boundary_cst, cmp_code, visited_phis,
 				visited_flag_phis))
 	    return false;
 
@@ -554,7 +553,7 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
 	  gimple *opnd_def = SSA_NAME_DEF_STMT (opnd);
 	  if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
 	    {
-	      unsigned opnds2 = eval.phi_arg_set (opnd_def_phi);
+	      unsigned opnds2 = m_eval.phi_arg_set (opnd_def_phi);
 	      if (!MASK_EMPTY (opnds2))
 		{
 		  edge opnd_edge = gimple_phi_arg_edge (phi, i);
@@ -578,9 +577,10 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
    up the CFG nodes that it's dominated by.  *EDGES holds the result, and
    VISITED is used for detecting cycles.  */
 
-static void
-collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec<edge> *edges,
-		       predicate::func_t &eval, hash_set<gimple *> *visited)
+void
+uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
+					vec<edge> *edges,
+					hash_set<gimple *> *visited)
 {
   if (visited->elements () == 0
       && DEBUG_PREDICATE_ANALYZER
@@ -607,9 +607,9 @@ collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec<edge> *edges,
 
 	  if (gimple_code (def) == GIMPLE_PHI
 	      && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
-	    collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges, eval,
+	    collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
 				   visited);
-	  else if (!eval (opnd))
+	  else if (!m_eval (opnd))
 	    {
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		{
@@ -635,7 +635,7 @@ collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec<edge> *edges,
 	      print_gimple_stmt (dump_file, phi, 0);
 	    }
 
-	  if (!eval (opnd))
+	  if (!m_eval (opnd))
 	    edges->safe_push (opnd_edge);
 	}
     }
@@ -689,7 +689,7 @@ build_pred_expr (const pred_chain_union &preds, bool invert = false)
 /* Return a bitset of all PHI arguments or zero if there are too many.  */
 
 unsigned
-predicate::func_t::phi_arg_set (gphi *phi)
+uninit_analysis::func_t::phi_arg_set (gphi *phi)
 {
   unsigned n = gimple_phi_num_args (phi);
 
@@ -772,7 +772,8 @@ predicate::func_t::phi_arg_set (gphi *phi)
      checked.  */
 
 bool
-predicate::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited)
+uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited,
+			  const predicate &use_preds)
 {
   gimple *flag_def = NULL;
   tree boundary_cst = NULL_TREE;
@@ -781,7 +782,7 @@ predicate::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited)
   /* Find within the common prefix of multiple predicate chains
      a predicate that is a comparison of a flag variable against
      a constant.  */
-  tree_code cmp_code = find_var_cmp_const (m_preds, phi, &flag_def,
+  tree_code cmp_code = find_var_cmp_const (use_preds.chain (), phi, &flag_def,
 					   &boundary_cst);
   if (cmp_code == ERROR_MARK)
     return true;
@@ -790,7 +791,7 @@ predicate::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited)
      value that is in conflict with the use guard/predicate.  */
   gphi *phi_def = as_a<gphi *> (flag_def);
   bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst,
-				     cmp_code, m_eval, visited,
+				     cmp_code, visited,
 				     &visited_flag_phis);
 
   if (visited_flag_phis)
@@ -1255,7 +1256,7 @@ can_be_invalidated_p (const pred_chain_union &preds, const pred_chain &guard)
    the use guards in *THIS that guard the PHI's use.  */
 
 bool
-predicate::use_cannot_happen (gphi *phi, unsigned opnds)
+uninit_analysis::use_cannot_happen (gphi *phi, unsigned opnds, const predicate &use_preds)
 {
   if (!m_eval.phi_arg_set (phi))
     return false;
@@ -1264,22 +1265,22 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
      possible guard, there's no way of knowing which guard was true.
      In that case compute the intersection of all use predicates
      and use that.  */
-  const pred_chain_union &phi_use_guards = m_preds;
-  const pred_chain *use_guard = &phi_use_guards[0];
+  const predicate &phi_use_guards = use_preds;
+  const pred_chain *use_guard = &phi_use_guards.chain() [0];
   pred_chain phi_use_guard_intersection = vNULL;
-  if (phi_use_guards.length () != 1)
+  if (phi_use_guards.chain ().length () != 1)
     {
       phi_use_guard_intersection = use_guard->copy ();
-      for (unsigned i = 1; i < phi_use_guards.length (); ++i)
+      for (unsigned i = 1; i < phi_use_guards.chain ().length (); ++i)
 	{
 	  for (unsigned j = 0; j < phi_use_guard_intersection.length ();)
 	    {
 	      unsigned k;
-	      for (k = 0; k < phi_use_guards[i].length (); ++k)
-		if (pred_equal_p (phi_use_guards[i][k],
+	      for (k = 0; k < phi_use_guards.chain ()[i].length (); ++k)
+		if (pred_equal_p (phi_use_guards.chain ()[i][k],
 				  phi_use_guard_intersection[j]))
 		  break;
-	      if (k == phi_use_guards[i].length ())
+	      if (k == phi_use_guards.chain ()[i].length ())
 		phi_use_guard_intersection.unordered_remove (j);
 	      else
 		j++;
@@ -1341,7 +1342,7 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
 
       /* ...and convert it into a set of predicates guarding its
 	 definition.  */
-      predicate def_preds (m_eval);
+      predicate def_preds;
       def_preds.init_from_control_deps (dep_chains, num_chains);
       if (def_preds.is_empty ())
 	/* If there's no predicate there's no basis to rule the use out.  */
@@ -1745,13 +1746,16 @@ predicate::dump (gimple *stmt, const char *msg) const
   fputc ('\n', dump_file);
 }
 
-/* Initialize *THIS with the predicates of the control dependence chains
+/* Initialize USE_PREDS with the predicates of the control dependence chains
    between the basic block DEF_BB that defines a variable of interst and
    USE_BB that uses the variable, respectively.  */
 
-predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
-  : m_preds (vNULL), m_eval (eval)
+bool
+uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
+				 basic_block use_bb)
 {
+  gcc_assert (use_preds.is_empty ());
+
   /* Set CD_ROOT to the basic block closest to USE_BB that is the control
      equivalent of (is guarded by the same predicate as) DEF_BB that also
      dominates USE_BB.  */
@@ -1799,7 +1803,8 @@ predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval)
      condition under which the definition in DEF_BB is used in USE_BB.
      Each OR subexpression is represented by one element of DEP_CHAINS,
      where each element consists of a series of AND subexpressions.  */
-  init_from_control_deps (dep_chains, num_chains);
+  use_preds.init_from_control_deps (dep_chains, num_chains);
+  return !use_preds.is_empty ();
 }
 
 /* Release resources in *THIS.  */
@@ -1820,9 +1825,6 @@ predicate::operator= (const predicate &rhs)
   if (this == &rhs)
     return *this;
 
-  /* FIXME: Make this a compile-time constraint?  */
-  gcc_assert (&m_eval == &rhs.m_eval);
-
   unsigned n = m_preds.length ();
   for (unsigned i = 0; i != n; ++i)
     m_preds[i].release ();
@@ -1843,9 +1845,9 @@ predicate::operator= (const predicate &rhs)
    Return true if a nonempty predicate has been obtained.  */
 
 bool
-predicate::init_from_phi_def (gphi *phi)
+uninit_analysis::init_from_phi_def (gphi *phi)
 {
-  gcc_assert (is_empty ());
+  gcc_assert (m_phi_def_preds.is_empty ());
 
   basic_block phi_bb = gimple_bb (phi);
   /* Find the closest dominating bb to be the control dependence root.  */
@@ -1857,7 +1859,7 @@ predicate::init_from_phi_def (gphi *phi)
      definitions of each of the PHI operands for which M_EVAL is false.  */
   auto_vec<edge> def_edges;
   hash_set<gimple *> visited_phis;
-  collect_phi_def_edges (phi, cd_root, &def_edges, m_eval, &visited_phis);
+  collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
 
   unsigned nedges = def_edges.length ();
   if (nedges == 0)
@@ -1887,8 +1889,8 @@ predicate::init_from_phi_def (gphi *phi)
   /* Convert control dependence chains to the predicate in *THIS under
      which the PHI operands are defined to values for which M_EVAL is
      false.  */
-  init_from_control_deps (dep_chains, num_chains);
-  return !is_empty ();
+  m_phi_def_preds.init_from_control_deps (dep_chains, num_chains);
+  return !m_phi_def_preds.is_empty ();
 }
 
 /* Compute the predicates that guard the use USE_STMT and check if
@@ -1911,9 +1913,9 @@ predicate::init_from_phi_def (gphi *phi)
    VISITED_PHIS is a pointer set of phis being visited.  */
 
 bool
-predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
-			   gphi *phi, unsigned opnds,
-			   hash_set<gphi *> *visited)
+uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
+				 gphi *phi, unsigned opnds,
+				 hash_set<gphi *> *visited)
 {
   if (visited->add (phi))
     return false;
@@ -1928,12 +1930,12 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
   /* Try to build the predicate expression under which the PHI flows
      into its use.  This will be empty if the PHI is defined and used
      in the same bb.  */
-  predicate use_preds (def_bb, use_bb, m_eval);
-  if (use_preds.is_empty ())
+  predicate use_preds;
+  if (!init_use_preds (use_preds, def_bb, use_bb))
     return false;
 
   /* Try to prune the dead incoming phi edges.  */
-  if (!use_preds.overlap (phi, opnds, visited))
+  if (!overlap (phi, opnds, visited, use_preds))
     {
       if (DEBUG_PREDICATE_ANALYZER && dump_file)
 	fputs ("found predicate overlap\n", dump_file);
@@ -1943,17 +1945,17 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
 
   /* We might be able to prove that if the control dependencies for OPNDS
      are true, the control dependencies for USE_STMT can never be true.  */
-  if (use_preds.use_cannot_happen (phi, opnds))
+  if (use_cannot_happen (phi, opnds, use_preds))
     return true;
 
-  if (is_empty ())
+  if (m_phi_def_preds.is_empty ())
     {
       /* Lazily initialize *THIS from PHI.  */
       if (!init_from_phi_def (phi))
 	return false;
 
-      simplify (phi);
-      normalize (phi);
+      m_phi_def_preds.simplify (phi);
+      m_phi_def_preds.normalize (phi);
     }
 
   use_preds.simplify (use_stmt, /*is_use=*/true);
@@ -1962,7 +1964,7 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
   /* Return true if the predicate guarding the valid definition (i.e.,
      *THIS) is a superset of the predicate guarding the use (i.e.,
      USE_PREDS).  */
-  if (superset_of (use_preds))
+  if (m_phi_def_preds.superset_of (use_preds))
     return true;
 
   return false;
@@ -1971,8 +1973,8 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb,
 /* Public interface to the above. */
 
 bool
-predicate::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
-			   unsigned opnds)
+uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
+				 unsigned opnds)
 {
   hash_set<gphi *> visited;
   return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
@@ -2141,7 +2143,7 @@ predicate::normalize (const pred_chain &chain)
   while (!work_list.is_empty ())
     {
       pred_info pi = work_list.pop ();
-      predicate pred (m_eval);
+      predicate pred;
       /* The predicate object is not modified here, only NORM_CHAIN and
 	 WORK_LIST are appended to.  */
       pred.normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
@@ -2162,7 +2164,7 @@ predicate::normalize (gimple *use_or_def, bool is_use)
       dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
     }
 
-  predicate norm_preds (m_eval);
+  predicate norm_preds;
   for (unsigned i = 0; i < m_preds.length (); i++)
     {
       if (m_preds[i].length () != 1)
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 77672291c36..b4aa5de7e7b 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -44,37 +44,11 @@ typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
 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) { }
+  predicate () : m_preds (vNULL) { }
 
   /* Copy.  */
-  predicate (const predicate &rhs)
-    : m_preds (vNULL), m_eval (rhs.m_eval)
-    {
-      *this = rhs;
-    }
-
-  predicate (basic_block, basic_block, func_t &);
+  predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; }
 
   ~predicate ();
 
@@ -91,10 +65,6 @@ class predicate
     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;
@@ -102,23 +72,16 @@ class predicate
   void normalize (gimple * = NULL, bool = false);
   void simplify (gimple * = NULL, bool = false);
 
-  bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
-		       hash_set<gphi *> *);
-
-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 *);
+private:
 
+  bool includes (const pred_chain &) const;
   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 &);
 
@@ -127,9 +90,63 @@ private:
   bool simplify_3 ();
   bool simplify_4 ();
 
-private:
   /* Representation of the predicate expression(s).  */
   pred_chain_union m_preds;
+};
+
+/* Represents a complex Boolean predicate expression.  */
+class uninit_analysis
+{
+ 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.  */
+  uninit_analysis (func_t &eval)
+    : m_phi_def_preds (), m_eval (eval) { }
+
+  /* Copy.  */
+  uninit_analysis (const uninit_analysis &rhs) = delete;
+
+  /* Assign.  */
+  uninit_analysis& operator= (const uninit_analysis&) = delete;
+
+  /* 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);
+
+private:
+  bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
+		       hash_set<gphi *> *);
+  bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code,
+			hash_set<gphi *> *, bitmap *);
+  bool overlap (gphi *, unsigned, hash_set<gphi *> *, const predicate &);
+  bool use_cannot_happen (gphi *, unsigned, const predicate &);
+
+  void collect_phi_def_edges (gphi *, basic_block, vec<edge> *,
+			      hash_set<gimple *> *);
+  bool init_from_phi_def (gphi *);
+  bool init_use_preds (predicate &, basic_block, basic_block);
+
+
+  /* Representation of the predicate expression(s).  */
+  predicate m_phi_def_preds;
   /* Callback to evaluate an operand.  Return true if it's interesting.  */
   func_t &m_eval;
 };
diff --git a/gcc/tree-ssa-uninit.cc b/gcc/tree-ssa-uninit.cc
index 7074c9117b2..450ff0fd062 100644
--- a/gcc/tree-ssa-uninit.cc
+++ b/gcc/tree-ssa-uninit.cc
@@ -1111,7 +1111,7 @@ compute_uninit_opnds_pos (gphi *phi)
 
   unsigned n = gimple_phi_num_args (phi);
   /* Bail out for phi with too many args.  */
-  if (n > predicate::func_t::max_phi_args)
+  if (n > uninit_analysis::func_t::max_phi_args)
     return 0;
 
   for (unsigned i = 0; i < n; ++i)
@@ -1137,7 +1137,7 @@ compute_uninit_opnds_pos (gphi *phi)
 /* Function object type used to determine whether an expression
    is of interest to the predicate analyzer.  */
 
-struct uninit_undef_val_t: public predicate::func_t
+struct uninit_undef_val_t: public uninit_analysis::func_t
 {
   virtual bool operator()(tree) override;
   virtual unsigned phi_arg_set (gphi *) override;
@@ -1179,7 +1179,7 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds,
      lazily from PHI in the first call to is_use_guarded() and cached
      for subsequent iterations.  */
   uninit_undef_val_t eval;
-  predicate def_preds (eval);
+  uninit_analysis def_preds (eval);
 
   use_operand_p use_p;
   imm_use_iterator iter;