[PATCH] Fix PR79345, better uninit warnings for memory

[Richard Biener <rguenther@suse.de>]

The following addresses a regression in uninit warnings that happens
because clobber stmts preclude the very simple-minded support we have
for memory.  The patch fixes this by instead implementing uninit
warnings for memory properly, using the alias oracle walk_aliased_vdefs
helper.

The patch adds better limiting to that interface and fixes one
false positive in fixed-value.c.  Two other false positives are
fixed by the wide-int.h patch posted a few hours ago and a patch
to genemit from Jakub.

Bootstrap and regtest running on x86_64-unknown-linux-gnu with those
prerequesites included.

One issue with the patch is duplicate warnings as TREE_NO_WARNING
doesn't work very well on tcc_reference trees which are not
shared.  A followup could use some sort of hash table to mitigate
this a bit.  OTOH for maybe-uninit uses multiple locations may
be in need to be fixed to silence the warning.  Another thing is
that we walk the function in random (BB) order and thus the
alias oracle walk limiting may result in warnings popping up
and going away in less predictable order (and also be reported
in odd order, like not all must-uninits first).

Comments?  I realize this may introduce (a lot of?) false positives
quite late in the game, more aggressive limiting, like to 2
disambiguations, could solve the testcase in the PR and give up
most of the times while preserving the non-walking case of the
old code.

Richard.

2017-03-01  Richard Biener  <rguenther@suse.de>

	* tree-ssa-alias.c (walk_aliased_vdefs_1): Take a limit
	param and abort the walk, returning -1 if it is hit.
	(walk_aliased_vdefs): Take a limit param and pass it on.
	* tree-ssa-alias.h (walk_aliased_vdefs): Add a limit param,
	defaulting to 0 and return a signed int.
	* tree-ssa-uninit.c (struct check_defs_data): New struct.
	(check_defs): New helper.
	(warn_uninitialized_vars): Use walk_aliased_vdefs to warn
	about uninitialized memory.

	* fixed-value.c (fixed_from_string): Use ulow/uhigh to avoid
	bogus uninitialized warning.
	(fixed_convert_from_real): Likewise.

	* g++.dg/warn/Wuninitialized-7.C: New testcase.
	* c-c++-common/ubsan/bounds-2.c: Add -Wno-uninitialized.
	* gcc.dg/uninit-pr19430-2.c: Add expected warning.

Index: gcc/tree-ssa-alias.c
===================================================================
--- gcc/tree-ssa-alias.c	(revision 245803)
+++ gcc/tree-ssa-alias.c	(working copy)
@@ -2897,13 +2897,15 @@ walk_non_aliased_vuses (ao_ref *ref, tre
    PHI argument (but only one walk continues on merge points), the
    return value is true if any of the walks was successful.
 
-   The function returns the number of statements walked.  */
+   The function returns the number of statements walked or -1 if
+   LIMIT stmts were walked and the walk was aborted at this point.
+   If LIMIT is zero the walk is not aborted.  */
 
-static unsigned int
+static int
 walk_aliased_vdefs_1 (ao_ref *ref, tree vdef,
 		      bool (*walker)(ao_ref *, tree, void *), void *data,
 		      bitmap *visited, unsigned int cnt,
-		      bool *function_entry_reached)
+		      bool *function_entry_reached, unsigned limit)
 {
   do
     {
@@ -2925,14 +2927,22 @@ walk_aliased_vdefs_1 (ao_ref *ref, tree
 	  if (!*visited)
 	    *visited = BITMAP_ALLOC (NULL);
 	  for (i = 0; i < gimple_phi_num_args (def_stmt); ++i)
-	    cnt += walk_aliased_vdefs_1 (ref, gimple_phi_arg_def (def_stmt, i),
-					 walker, data, visited, 0,
-					 function_entry_reached);
+	    {
+	      int res = walk_aliased_vdefs_1 (ref,
+					      gimple_phi_arg_def (def_stmt, i),
+					      walker, data, visited, 0,
+					      function_entry_reached, limit);
+	      if (res == -1)
+		return -1;
+	      cnt += res;
+	    }
 	  return cnt;
 	}
 
       /* ???  Do we want to account this to TV_ALIAS_STMT_WALK?  */
       cnt++;
+      if (cnt == limit)
+	return -1;
       if ((!ref
 	   || stmt_may_clobber_ref_p_1 (def_stmt, ref))
 	  && (*walker) (ref, vdef, data))
@@ -2943,14 +2953,14 @@ walk_aliased_vdefs_1 (ao_ref *ref, tree
   while (1);
 }
 
-unsigned int
+int
 walk_aliased_vdefs (ao_ref *ref, tree vdef,
 		    bool (*walker)(ao_ref *, tree, void *), void *data,
 		    bitmap *visited,
-		    bool *function_entry_reached)
+		    bool *function_entry_reached, unsigned int limit)
 {
   bitmap local_visited = NULL;
-  unsigned int ret;
+  int ret;
 
   timevar_push (TV_ALIAS_STMT_WALK);
 
@@ -2959,7 +2969,7 @@ walk_aliased_vdefs (ao_ref *ref, tree vd
 
   ret = walk_aliased_vdefs_1 (ref, vdef, walker, data,
 			      visited ? visited : &local_visited, 0,
-			      function_entry_reached);
+			      function_entry_reached, limit);
   if (local_visited)
     BITMAP_FREE (local_visited);
 
Index: gcc/tree-ssa-alias.h
===================================================================
--- gcc/tree-ssa-alias.h	(revision 245803)
+++ gcc/tree-ssa-alias.h	(working copy)
@@ -131,10 +131,11 @@ extern void *walk_non_aliased_vuses (ao_
 				     void *(*)(ao_ref *, tree, void *, bool *),
 				     tree (*)(tree),
 				     void *);
-extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
-					bool (*)(ao_ref *, tree, void *),
-					void *, bitmap *,
-					bool *function_entry_reached = NULL);
+extern int walk_aliased_vdefs (ao_ref *, tree,
+			       bool (*)(ao_ref *, tree, void *),
+			       void *, bitmap *,
+			       bool *function_entry_reached = NULL,
+			       unsigned int limit = 0);
 extern void dump_alias_info (FILE *);
 extern void debug_alias_info (void);
 extern void dump_points_to_solution (FILE *, struct pt_solution *);
Index: gcc/testsuite/g++.dg/warn/Wuninitialized-7.C
===================================================================
--- gcc/testsuite/g++.dg/warn/Wuninitialized-7.C	(nonexistent)
+++ gcc/testsuite/g++.dg/warn/Wuninitialized-7.C	(working copy)
@@ -0,0 +1,20 @@
+// { dg-do compile }
+// { dg-require-effective-target c++11 }
+// { dg-options "-O -Wuninitialized" }
+
+struct A {
+    A (int);
+};
+
+struct B: A {
+    const bool x = true;
+
+    B (): A (x ? 3 : 7) { } // { dg-warning "x. is used uninitialized" }
+};
+
+void f (void*);
+void g ()
+{
+  B b;
+  f (&b);
+}
Index: gcc/fixed-value.c
===================================================================
--- gcc/fixed-value.c	(revision 245803)
+++ gcc/fixed-value.c	(working copy)
@@ -130,8 +130,8 @@ fixed_from_string (FIXED_VALUE_TYPE *f,
   real_arithmetic (&fixed_value, MULT_EXPR, &real_value, &base_value);
   wide_int w = real_to_integer (&fixed_value, &fail,
 				GET_MODE_PRECISION (mode));
-  f->data.low = w.elt (0);
-  f->data.high = w.elt (1);
+  f->data.low = w.ulow ();
+  f->data.high = w.uhigh ();
 
   if (temp == FIXED_MAX_EPS && ALL_FRACT_MODE_P (f->mode))
     {
@@ -1049,8 +1049,8 @@ fixed_convert_from_real (FIXED_VALUE_TYP
 
   wide_int w = real_to_integer (&fixed_value, &fail,
 				GET_MODE_PRECISION (mode));
-  f->data.low = w.elt (0);
-  f->data.high = w.elt (1);
+  f->data.low = w.ulow ();
+  f->data.high = w.uhigh ();
   temp = check_real_for_fixed_mode (&real_value, mode);
   if (temp == FIXED_UNDERFLOW) /* Minimum.  */
     {
Index: gcc/testsuite/c-c++-common/ubsan/bounds-2.c
===================================================================
--- gcc/testsuite/c-c++-common/ubsan/bounds-2.c	(revision 245803)
+++ gcc/testsuite/c-c++-common/ubsan/bounds-2.c	(working copy)
@@ -1,5 +1,5 @@
 /* { dg-do run } */
-/* { dg-options "-fsanitize=bounds -Wall -Wextra -Wno-unused -Wno-array-bounds" } */
+/* { dg-options "-fsanitize=bounds -Wall -Wextra -Wno-unused -Wno-array-bounds -Wno-uninitialized" } */
 
 /* Test runtime errors.  */
 
Index: gcc/testsuite/gcc.dg/uninit-pr19430-2.c
===================================================================
--- gcc/testsuite/gcc.dg/uninit-pr19430-2.c	(revision 245803)
+++ gcc/testsuite/gcc.dg/uninit-pr19430-2.c	(working copy)
@@ -10,7 +10,7 @@ int foo (int b)
   p = &i;
   q = &j;
   if (b)
-    x = p;
+    x = p;  /* { dg-warning "i. may be used uninitialized" } */
   else
     x = q;
   return *x;
Index: gcc/tree-ssa-uninit.c
===================================================================
--- gcc/tree-ssa-uninit.c	(revision 245803)
+++ gcc/tree-ssa-uninit.c	(working copy)
@@ -191,11 +191,39 @@ warn_uninit (enum opt_code wc, tree t, t
     }
 }
 
+struct check_defs_data
+{
+  /* If we found any may-defs besides must-def clobbers.  */
+  bool found_may_defs;
+};
+
+/* Callback for walk_aliased_vdefs.  */
+
+static bool
+check_defs (ao_ref *ref, tree vdef, void *data_)
+{
+  check_defs_data *data = (check_defs_data *)data_;
+  gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
+  /* If this is a clobber then if it is not a kill walk past it.  */
+  if (gimple_clobber_p (def_stmt))
+    {
+      if (stmt_kills_ref_p (def_stmt, ref))
+	return true;
+      return false;
+    }
+  /* Found a may-def on this path.  */
+  data->found_may_defs = true;
+  return true;
+}
+
 static unsigned int
 warn_uninitialized_vars (bool warn_possibly_uninitialized)
 {
   gimple_stmt_iterator gsi;
   basic_block bb;
+  unsigned int vdef_cnt = 0;
+  unsigned int oracle_cnt = 0;
+  unsigned limit = 0;
 
   FOR_EACH_BB_FN (bb, cfun)
     {
@@ -236,39 +264,73 @@ warn_uninitialized_vars (bool warn_possi
 			     stmt, UNKNOWN_LOCATION);
 	    }
 
-	  /* For memory the only cheap thing we can do is see if we
-	     have a use of the default def of the virtual operand.
-	     ???  Not so cheap would be to use the alias oracle via
-	     walk_aliased_vdefs, if we don't find any aliasing vdef
-	     warn as is-used-uninitialized, if we don't find an aliasing
-	     vdef that kills our use (stmt_kills_ref_p), warn as
-	     may-be-used-uninitialized.  But this walk is quadratic and
-	     so must be limited which means we would miss warning
-	     opportunities.  */
-	  use = gimple_vuse (stmt);
-	  if (use
-	      && gimple_assign_single_p (stmt)
-	      && !gimple_vdef (stmt)
-	      && SSA_NAME_IS_DEFAULT_DEF (use))
+	  /* For limiting the alias walk below we count all
+	     vdefs in the function.  We then give the alias walk an
+	     overall budget (and simply not warn for further stmts).
+	     ???  The interface doesn't give us the chance to assign
+	     a maximum cost to each walk (and abort the walk if hit).  */
+	  if (gimple_vdef (stmt))
+	    vdef_cnt++;
+
+	  if (gimple_assign_load_p (stmt)
+	      && gimple_has_location (stmt))
 	    {
 	      tree rhs = gimple_assign_rhs1 (stmt);
-	      tree base = get_base_address (rhs);
+	      if (TREE_NO_WARNING (rhs))
+		continue;
+
+	      ao_ref ref;
+	      ao_ref_init (&ref, rhs);
 
 	      /* Do not warn if it can be initialized outside this function.  */
+	      tree base = ao_ref_base (&ref);
 	      if (!VAR_P (base)
 		  || DECL_HARD_REGISTER (base)
-		  || is_global_var (base))
+		  || is_global_var (base)
+		  || TREE_NO_WARNING (base))
+		continue;
+
+	      /* Limit the walking to a constant number of stmts after
+	         we overcommit quadratic behavior for small functions
+		 and O(n) behavior.  */
+	      if (oracle_cnt > 128 * 128
+		  && oracle_cnt > vdef_cnt * 2)
+		limit = 32;
+	      check_defs_data data;
+	      data.found_may_defs = false;
+	      use = gimple_vuse (stmt);
+	      int res = walk_aliased_vdefs (&ref, use,
+					    check_defs, &data, NULL,
+					    NULL, limit);
+	      if (res == -1)
+		{
+		  oracle_cnt += limit;
+		  continue;
+		}
+	      oracle_cnt += res;
+	      if (data.found_may_defs)
 		continue;
 
+	      /* We didn't find any may-defs so on all paths either
+	         reached function entry or a killing clobber.  */
+	      location_t location
+		= linemap_resolve_location (line_table, gimple_location (stmt),
+					    LRK_SPELLING_LOCATION, NULL);
 	      if (always_executed)
-		warn_uninit (OPT_Wuninitialized, use, gimple_assign_rhs1 (stmt),
-			     base, "%qE is used uninitialized in this function",
-			     stmt, UNKNOWN_LOCATION);
+		{
+		  if (warning_at (location, OPT_Wuninitialized,
+				  "%qE is used uninitialized in this function",
+				  rhs))
+		    /* ???  This is only effective for decls as in
+		       gcc.dg/uninit-B-O0.c.  Avoid doing this for
+		       maybe-uninit uses as it may hide important
+		       locations.  */
+		    TREE_NO_WARNING (rhs) = 1;
+		}
 	      else if (warn_possibly_uninitialized)
-		warn_uninit (OPT_Wmaybe_uninitialized, use,
-			     gimple_assign_rhs1 (stmt), base,
-			     "%qE may be used uninitialized in this function",
-			     stmt, UNKNOWN_LOCATION);
+		warning_at (location, OPT_Wmaybe_uninitialized,
+			    "%qE may be used uninitialized in this function",
+			    rhs);
 	    }
 	}
     }