Make uninit PHI processing more consistent

Currently the main working of the maybe-uninit pass is to scan over
all PHIs with possibly undefined arguments, diagnosing whether there's
a direct not guarded use.  For not guarded uses in PHIs those are queued for
later processing and to make the uninit analysis PHI def handling work,
mark the PHI def as possibly uninitialized.  But this happens only
for those PHI uses that happen to be seen before a direct not guarded
use and whether all arguments of a PHI node which are defined by a PHI
are properly marked as maybe uninitialized depends on the processing
order.

The following changes the uninit pass to perform an RPO walk over
the function, ensuring that PHI argument defs are visited before
the PHI node (besides backedge uses which we ignore already),
getting rid of the worklist.  It also makes sure to process all
PHI uses, but recording those that are properly guarded so they
are not treated as maybe undefined when processing the PHI use
later.

Overall this should make behavior more consistent, avoid some
false negative because of the previous early out and order issue,
and avoid some false positive because of the missed recording
of guarded PHI uses.

The patch correctly diagnoses an uninitalized use of 'regnum'
in store_bit_field_1 and also diagnoses an uninitialized use of
best_match::m_best_candidate_len in c-decl.cc which I've chosen to
silence by initializing m_best_candidate_len.  The warning is
a false positive but GCC cannot see that m_best_candidate_len is
initialized when m_best_candidate is not NULL so from this
perspective this was a false negative.  I've added
g++.dg/uninit-pred-5.C with a reduced testcase that nicely shows
how the previous behavior missed the diagnostic because the
worklist ended up visiting the PHI with the dependend uninit
value before visiting the PHIs producing it.

	* gimple-predicate-analysis.h (uninit_analysis::operator()):
	Remove.
	* gimple-predicate-analysis.cc
	(uninit_analysis::collect_phi_def_edges): Use phi_arg_set,
	simplify a bit.
	* tree-ssa-uninit.cc (defined_args): New global.
	(compute_uninit_opnds_pos): Mask with the recorded set
	of guarded maybe-uninitialized uses.
	(uninit_undef_val_t::operator()): Remove.
	(find_uninit_use): Process all PHI uses, recording the
	guarded ones and marking the PHI result as uninitialized
	consistently.
	(warn_uninitialized_phi): Adjust.
	(execute_late_warn_uninitialized): Get rid of the PHI worklist
	and instead walk the function in RPO order.
	* spellcheck.h (best_match::m_best_candidate_len): Initialize.

	* g++.dg/uninit-pred-5.C: New testcase.

5 files changed, 176 insertions, 121 deletions

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index e388bb3..3f9b80d 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -543,35 +543,13 @@ uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
     return;
 
   unsigned n = gimple_phi_num_args (phi);
+  unsigned opnds_arg_phi = m_eval.phi_arg_set (phi);
   for (unsigned i = 0; i < n; i++)
     {
-      edge opnd_edge = gimple_phi_arg_edge (phi, i);
-      tree opnd = gimple_phi_arg_def (phi, i);
-
-      if (TREE_CODE (opnd) == SSA_NAME)
-	{
-	  gimple *def = SSA_NAME_DEF_STMT (opnd);
-
-	  if (!m_eval (opnd))
-	    {
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		{
-		  fprintf (dump_file,
-			   "\tFound def edge %i -> %i for cd_root %i "
-			   "and operand %u of: ",
-			   opnd_edge->src->index, opnd_edge->dest->index,
-			   cd_root->index, i);
-		  print_gimple_stmt (dump_file, phi, 0);
-		}
-	      edges->safe_push (opnd_edge);
-	    }
-	  else 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,
-				   visited);
-	}
-      else
+      if (!MASK_TEST_BIT (opnds_arg_phi, i))
 	{
+	  /* Add the edge for a not maybe-undefined edge value.  */
+	  edge opnd_edge = gimple_phi_arg_edge (phi, i);
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file,
@@ -581,9 +559,22 @@ uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
 		       cd_root->index, i);
 	      print_gimple_stmt (dump_file, phi, 0);
 	    }
-
-	  if (!m_eval (opnd))
-	    edges->safe_push (opnd_edge);
+	  edges->safe_push (opnd_edge);
+	  continue;
+	}
+      else
+	{
+	  tree opnd = gimple_phi_arg_def (phi, i);
+	  if (TREE_CODE (opnd) == SSA_NAME)
+	    {
+	      gimple *def = SSA_NAME_DEF_STMT (opnd);
+	      if (gimple_code (def) == GIMPLE_PHI
+		  && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
+		/* Process PHI defs of maybe-undefined edge values
+		   recursively.  */
+		collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
+				       visited);
+	    }
 	}
     }
 }
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index 1ca6ab1..48da8f7 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -104,8 +104,6 @@ class uninit_analysis
   {
     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
diff --git a/gcc/spellcheck.h b/gcc/spellcheck.h
index 3706de3..1b76a54 100644
--- a/gcc/spellcheck.h
+++ b/gcc/spellcheck.h
@@ -95,7 +95,8 @@ class best_match
   : m_goal (goal_traits::get_string (goal)),
     m_goal_len (goal_traits::get_length (goal)),
     m_best_candidate (NULL),
-    m_best_distance (best_distance_so_far)
+    m_best_distance (best_distance_so_far),
+    m_best_candidate_len (0)
   {}
 
   /* Compare the edit distance between CANDIDATE and m_goal,
diff --git a/gcc/testsuite/g++.dg/uninit-pred-5.C b/gcc/testsuite/g++.dg/uninit-pred-5.C
new file mode 100644
index 0000000..8dfd987
--- /dev/null
+++ b/gcc/testsuite/g++.dg/uninit-pred-5.C
@@ -0,0 +1,94 @@
+// { dg-do compile }
+// { dg-options "-O2 -Wuninitialized" }
+
+typedef int size_t;
+typedef struct {
+} max_align_t;
+typedef struct tree_node *tree;
+struct ht_identifier {
+  char str;
+  int len;
+};
+struct cpp_hashnode {
+  ht_identifier ident;
+};
+tree get_identifier_with_length(char *, size_t);
+struct cpp_reader *parse_in;
+typedef int edit_distance_t;
+edit_distance_t get_edit_distance(char *);
+template < typename > struct edit_distance_traits;
+edit_distance_t get_edit_distance_cutoff(size_t);
+template < typename GOAL_TYPE, typename CANDIDATE_TYPE > class best_match {
+public:
+  typedef CANDIDATE_TYPE candidate_t;
+  typedef edit_distance_traits< candidate_t > candidate_traits;
+  best_match(GOAL_TYPE)
+      : m_goal(), m_goal_len(), m_best_candidate(), m_best_distance() {}
+  void consider(candidate_t candidate) {
+    size_t candidate_len = candidate_traits::get_length(candidate);
+    char candidate_str;
+    edit_distance_t dist = get_edit_distance(&candidate_str);
+    bool is_better = false;
+    if (dist)
+      is_better = true;
+    if (is_better) {
+      m_best_candidate = candidate;
+      m_best_candidate_len = candidate_len;
+    }
+  }
+  void set_best_so_far(CANDIDATE_TYPE) {}
+  candidate_t get_best_meaningful_candidate() {
+    edit_distance_t __trans_tmp_1;
+    if (m_best_candidate) {
+      size_t candidate_len = m_best_candidate_len;
+      __trans_tmp_1 = get_edit_distance_cutoff(candidate_len); // { dg-warning "may be used uninitialized" }
+    }
+    edit_distance_t cutoff = __trans_tmp_1;
+    if (cutoff)
+      ;
+    return m_best_candidate;
+  }
+  char m_goal;
+  size_t m_goal_len;
+  candidate_t m_best_candidate;
+  edit_distance_t m_best_distance;
+  size_t m_best_candidate_len;
+};
+template <> struct edit_distance_traits< tree > {
+  static size_t get_length(tree);
+};
+class name_hint {};
+class best_macro_match : public best_match< tree, cpp_hashnode * > {
+public:
+  best_macro_match(cpp_reader *);
+};
+struct c_binding {
+  tree id;
+  c_binding *prev;
+};
+struct c_scope {
+  c_scope *outer;
+  c_binding bindings;
+} * current_scope;
+tree lookup_name_fuzzy_name;
+void lookup_name_fuzzy() {
+  bool consider_implementation_names = 0;
+  best_match< tree, tree > bm(lookup_name_fuzzy_name);
+  for (c_scope *scope = current_scope; current_scope;
+       scope = scope->outer)
+    for (c_binding *binding = &scope->bindings; binding;
+         binding = binding->prev)
+      if (!consider_implementation_names)
+        bm.consider(binding->id);
+  best_macro_match bmm(parse_in);
+  cpp_hashnode *best_macro = bmm.get_best_meaningful_candidate();
+  if (best_macro) {
+    char id = best_macro->ident.str;
+    tree macro_as_identifier =
+        get_identifier_with_length(&id, best_macro->ident.len);
+    bm.set_best_so_far(macro_as_identifier);
+  }
+  tree best = bm.get_best_meaningful_candidate();
+  if (best)
+    name_hint();
+}
diff --git a/gcc/tree-ssa-uninit.cc b/gcc/tree-ssa-uninit.cc
index 450ff0f..3e5816f 100644
--- a/gcc/tree-ssa-uninit.cc
+++ b/gcc/tree-ssa-uninit.cc
@@ -56,7 +56,8 @@ along with GCC; see the file COPYING3.  If not see
 /* Pointer set of potentially undefined ssa names, i.e.,
    ssa names that are defined by phi with operands that
    are not defined or potentially undefined.  */
-static hash_set<tree> *possibly_undefined_names = 0;
+static hash_set<tree> *possibly_undefined_names;
+static hash_map<gphi *, uninit_analysis::func_t::phi_arg_set_t> *defined_args;
 
 /* Returns the first bit position (starting from LSB)
    in mask that is non zero.  Returns -1 if the mask is empty.  */
@@ -1131,6 +1132,9 @@ compute_uninit_opnds_pos (gphi *phi)
 	  MASK_SET_BIT (uninit_opnds, i);
 	}
     }
+  /* If we have recorded guarded uses of may-uninit values mask those.  */
+  if (auto *def_mask = defined_args->get (phi))
+    uninit_opnds &= ~*def_mask;
   return uninit_opnds;
 }
 
@@ -1139,21 +1143,9 @@ compute_uninit_opnds_pos (gphi *phi)
 
 struct uninit_undef_val_t: public uninit_analysis::func_t
 {
-  virtual bool operator()(tree) override;
   virtual unsigned phi_arg_set (gphi *) override;
 };
 
-/* Return true if the argument is an expression of interest.  */
-
-bool
-uninit_undef_val_t::operator()(tree val)
-{
-  if (TREE_CODE (val) == SSA_NAME)
-    return uninit_undefined_value_p (val);
-
-  return false;
-}
-
 /* Return a bitset of PHI arguments of interest.  */
 
 unsigned
@@ -1166,14 +1158,10 @@ uninit_undef_val_t::phi_arg_set (gphi *phi)
    uninitialized variable defined by PHI and returns a use
    statement if the use is not properly guarded.  It returns
    NULL if all uses are guarded.  UNINIT_OPNDS is a bitvector
-   holding the position(s) of uninit PHI operands.  WORKLIST
-   is the vector of candidate phis that may be updated by this
-   function.  ADDED_TO_WORKLIST is the pointer set tracking
-   if the new phi is already in the worklist.  */
+   holding the position(s) of uninit PHI operands.  */
 
 static gimple *
-find_uninit_use (gphi *phi, unsigned uninit_opnds,
-		 vec<gphi *> *worklist, hash_set<gphi *> *added_to_worklist)
+find_uninit_use (gphi *phi, unsigned uninit_opnds)
 {
   /* The Boolean predicate guarding the PHI definition.  Initialized
      lazily from PHI in the first call to is_use_guarded() and cached
@@ -1184,6 +1172,7 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds,
   use_operand_p use_p;
   imm_use_iterator iter;
   tree phi_result = gimple_phi_result (phi);
+  gimple *uninit_use = NULL;
   FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
     {
       gimple *use_stmt = USE_STMT (use_p);
@@ -1202,11 +1191,32 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds,
 	  if (e->flags & EDGE_DFS_BACK)
 	    continue;
 	}
+      else if (uninit_use)
+	/* Only process the first real uninitialized use, but continue
+	   looking for unguarded uses in PHIs.  */
+	continue;
       else
 	use_bb = gimple_bb (use_stmt);
 
       if (def_preds.is_use_guarded (use_stmt, use_bb, phi, uninit_opnds))
-	continue;
+	{
+	  /* For a guarded use in a PHI record the PHI argument as
+	     initialized.  */
+	  if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
+	    {
+	      unsigned idx = PHI_ARG_INDEX_FROM_USE (use_p);
+	      if (idx < uninit_analysis::func_t::max_phi_args)
+		{
+		  bool existed_p;
+		  auto &def_mask
+		    = defined_args->get_or_insert (use_phi, &existed_p);
+		  if (!existed_p)
+		    def_mask = 0;
+		  MASK_SET_BIT (def_mask, idx);
+		}
+	    }
+	  continue;
+	}
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
@@ -1214,59 +1224,35 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds,
 		   use_bb->index);
 	  print_gimple_stmt (dump_file, use_stmt, 0);
 	}
-      /* Found one real use, return.  */
-      if (gimple_code (use_stmt) != GIMPLE_PHI)
-	return use_stmt;
-
-      /* Found a phi use that is not guarded,
-	 add the phi to the worklist.  */
-      if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
-	{
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
-	      print_gimple_stmt (dump_file, use_stmt, 0);
-	    }
-
-	  worklist->safe_push (as_a<gphi *> (use_stmt));
-	  possibly_undefined_names->add (phi_result);
-	}
+      /* Found a phi use that is not guarded, mark the phi_result as
+	 possibly undefined.  */
+      if (is_a <gphi *> (use_stmt))
+	possibly_undefined_names->add (phi_result);
+      else
+	uninit_use = use_stmt;
     }
 
-  return NULL;
+  return uninit_use;
 }
 
 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
    and gives warning if there exists a runtime path from the entry to a
    use of the PHI def that does not contain a definition.  In other words,
    the warning is on the real use.  The more dead paths that can be pruned
-   by the compiler, the fewer false positives the warning is.  WORKLIST
-   is a vector of candidate phis to be examined.  ADDED_TO_WORKLIST is
-   a pointer set tracking if the new phi is added to the worklist or not.  */
+   by the compiler, the fewer false positives the warning is.  */
 
 static void
-warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
-			hash_set<gphi *> *added_to_worklist)
+warn_uninitialized_phi (gphi *phi, unsigned uninit_opnds)
 {
-  /* Don't look at virtual operands.  */
-  if (virtual_operand_p (gimple_phi_result (phi)))
-    return;
-
-  unsigned uninit_opnds = compute_uninit_opnds_pos (phi);
-  if (MASK_EMPTY (uninit_opnds))
-    return;
-
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Examining phi: ");
       print_gimple_stmt (dump_file, phi, 0);
     }
 
-  gimple *uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
-					     worklist, added_to_worklist);
+  gimple *uninit_use_stmt = find_uninit_use (phi, uninit_opnds);
 
-  /* All uses are properly guarded but a new PHI may have been added
-     to WORKLIST.  */
+  /* All uses are properly guarded.  */
   if (!uninit_use_stmt)
     return;
 
@@ -1341,10 +1327,6 @@ public:
 static void
 execute_late_warn_uninitialized (function *fun)
 {
-  basic_block bb;
-  gphi_iterator gsi;
-  vec<gphi *> worklist = vNULL;
-
   calculate_dominance_info (CDI_DOMINATORS);
   calculate_dominance_info (CDI_POST_DOMINATORS);
 
@@ -1352,6 +1334,8 @@ execute_late_warn_uninitialized (function *fun)
      unreachable blocks.  */
   set_all_edges_as_executable (fun);
   mark_dfs_back_edges (fun);
+  int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
+  int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
 
   /* Re-do the plain uninitialized variable check, as optimization may have
      straightened control flow.  Do this first so that we don't accidentally
@@ -1361,11 +1345,15 @@ execute_late_warn_uninitialized (function *fun)
   timevar_push (TV_TREE_UNINIT);
 
   possibly_undefined_names = new hash_set<tree>;
-  hash_set<gphi *> added_to_worklist;
-
-  /* Initialize worklist  */
-  FOR_EACH_BB_FN (bb, fun)
-    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  defined_args = new hash_map<gphi *, uninit_analysis::func_t::phi_arg_set_t>;
+
+  /* Walk the CFG in RPO order so we visit PHIs with defs that are
+     possibly uninitialized from other PHIs after those.  The uninit
+     predicate analysis will then expand the PHIs predicate with
+     the predicates of the edges from such PHI defs.  */
+  for (int i = 0; i < n; ++i)
+    for (auto gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (fun, rpo[i]));
+	 !gsi_end_p (gsi); gsi_next (&gsi))
       {
 	gphi *phi = gsi.phi ();
 
@@ -1373,35 +1361,18 @@ execute_late_warn_uninitialized (function *fun)
 	if (virtual_operand_p (gimple_phi_result (phi)))
 	  continue;
 
-	unsigned n = gimple_phi_num_args (phi);
-	for (unsigned i = 0; i < n; ++i)
-	  {
-	    tree op = gimple_phi_arg_def (phi, i);
-	    if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
-	      {
-		worklist.safe_push (phi);
-		added_to_worklist.add (phi);
-		if (dump_file && (dump_flags & TDF_DETAILS))
-		  {
-		    fprintf (dump_file, "[WORKLIST]: add to initial list "
-			     "for operand %u of: ", i);
-		    print_gimple_stmt (dump_file, phi, 0);
-		  }
-		break;
-	      }
-	  }
-      }
+	unsigned uninit_opnds = compute_uninit_opnds_pos (phi);
+	if (MASK_EMPTY (uninit_opnds))
+	  continue;
 
-  while (worklist.length () != 0)
-    {
-      gphi *cur_phi = 0;
-      cur_phi = worklist.pop ();
-      warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
-    }
+	warn_uninitialized_phi (phi, uninit_opnds);
+      }
 
-  worklist.release ();
+  free (rpo);
   delete possibly_undefined_names;
   possibly_undefined_names = NULL;
+  delete defined_args;
+  defined_args = NULL;
   free_dominance_info (CDI_POST_DOMINATORS);
   timevar_pop (TV_TREE_UNINIT);
 }