[3/8] tree-dynamic-object-size: Handle GIMPLE_PHI

diff --git a/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c b/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
index 620e8cbc611..7098ef485c6 100644
--- a/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
+++ b/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
@@ -63,6 +63,48 @@  test_builtin_malloc_cond (int cond)
   return __builtin_dynamic_object_size (ret, 0);
 }
 
+size_t
+__attribute__ ((noinline))
+test_builtin_malloc_condphi (int cond)
+{
+  void *ret;
+ 
+  if (cond)
+    ret = __builtin_malloc (32);
+  else
+    ret = __builtin_malloc (64);
+
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_malloc_condphi2 (int cond, size_t in)
+{
+  void *ret;
+ 
+  if (cond)
+    ret = __builtin_malloc (in);
+  else
+    ret = __builtin_malloc (64);
+
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_malloc_condphi3 (int cond, size_t in, size_t in2)
+{
+  void *ret;
+ 
+  if (cond)
+    ret = __builtin_malloc (in);
+  else
+    ret = __builtin_malloc (in2);
+
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
 /* Calloc-like allocator.  */
 
 size_t
@@ -89,6 +131,21 @@  test_builtin_calloc_cond (int cond1, int cond2)
   return __builtin_dynamic_object_size (ret, 0);
 }
 
+size_t
+__attribute__ ((noinline))
+test_builtin_calloc_condphi (size_t cnt, size_t sz, int cond)
+{
+  struct
+    {
+      int a;
+      char b;
+    } bin[cnt];
+
+  char *ch = __builtin_calloc (cnt, sz);
+
+  return __builtin_dynamic_object_size (cond ? ch : (void *) &bin, 0);
+}
+
 /* Passthrough functions.  */
 
 size_t
@@ -120,6 +177,19 @@  test_dynarray_cond (int cond)
   return __builtin_dynamic_object_size (bin, 0);
 }
 
+size_t
+__attribute__ ((noinline))
+test_deploop (size_t sz, size_t cond)
+{
+  char *bin = __builtin_alloca (32);
+
+  for (size_t i = 0; i < sz; i++)
+    if (i == cond)
+      bin = __builtin_alloca (sz);
+
+  return __builtin_dynamic_object_size (bin, 0);
+}
+
 int
 main (int argc, char **argv)
 {
@@ -141,6 +211,18 @@  main (int argc, char **argv)
     FAIL ();
   if (test_builtin_malloc_cond (0) != 64)
     FAIL ();
+  if (test_builtin_malloc_condphi (1) != 32)
+    FAIL ();
+  if (test_builtin_malloc_condphi (0) != 64)
+    FAIL ();
+  if (test_builtin_malloc_condphi2 (1, 128) != 128)
+    FAIL ();
+  if (test_builtin_malloc_condphi2 (0, 128) != 64)
+    FAIL ();
+  if (test_builtin_malloc_condphi3 (1, 128, 256) != 128)
+    FAIL ();
+  if (test_builtin_malloc_condphi3 (0, 128, 256) != 256)
+    FAIL ();
   if (test_calloc (2048, 4) != 2048 * 4)
     FAIL ();
   if (test_builtin_calloc (2048, 8) != 2048 * 8)
@@ -149,6 +231,12 @@  main (int argc, char **argv)
     FAIL ();
   if (test_builtin_calloc_cond (1, 1) != 32 * 1024)
     FAIL ();
+  if (test_builtin_calloc_condphi (128, 1, 1) != 128)
+    FAIL ();
+  if (test_builtin_calloc_condphi (128, 1, 0) == 128)
+    FAIL ();
+  if (test_builtin_calloc_condphi (128, 1, 0) == -1)
+    FAIL ();
   if (test_passthrough (__builtin_strlen (argv[0]) + 1, argv[0])
       != __builtin_strlen (argv[0]) + 1)
     FAIL ();
@@ -158,6 +246,10 @@  main (int argc, char **argv)
     FAIL ();
   if (test_dynarray_cond (1) != 8)
     FAIL ();
+  if (test_deploop (128, 4) != 128)
+    FAIL ();
+  if (test_deploop (128, 129) != 32)
+    FAIL ();
 
   if (nfails > 0)
     __builtin_abort ();
diff --git a/gcc/tree-dynamic-object-size.c b/gcc/tree-dynamic-object-size.c
index 8e52dd46c03..483d6782d49 100644
--- a/gcc/tree-dynamic-object-size.c
+++ b/gcc/tree-dynamic-object-size.c
@@ -62,11 +62,14 @@  along with GCC; see the file COPYING3.  If not see
 #include "attribs.h"
 #include "builtins.h"
 #include "print-tree.h"
+#include "gimplify-me.h"
 
 struct object_size_info
 {
+  struct function *fun;
   int object_size_type;
   bitmap visited;
+  unsigned deploop;
 };
 
 static tree alloc_object_size (const gcall *);
@@ -78,9 +81,15 @@  static void collect_object_sizes_for (struct object_size_info *, tree);
    object_sizes[1] is upper bound for number of bytes till the end of
    the subobject (innermost array or field with address taken).
    object_sizes[2] is lower bound for number of bytes till the end of
-   the object and object_sizes[3] lower bound for subobject.  */
+   the object and object_sizes[3] lower bound for subobject.
+
+   These are merely SSA names of the sizes.  The actual size expressions are in
+   object_size_exprs and they need not be SSA.  */
 static vec<tree> object_sizes[4];
 
+/* The actual size expressions, indexed by the object SSA names.  */
+static vec<tree *>object_size_exprs[4];
+
 /* Bitmaps what object sizes have been computed already.  */
 static bitmap computed[4];
 
@@ -166,13 +175,123 @@  pass_through_call (const gcall *call)
   return NULL_TREE;
 }
 
+static void
+emit_size_stmts (gimple *stmt, tree size_ssa, tree size_expr)
+{
+  gimple_seq seq = NULL;
+
+  if (!is_gimple_variable (size_expr))
+    size_expr = force_gimple_operand (size_expr, &seq, true, NULL);
+
+  gassign *assign = gimple_build_assign (size_ssa, size_expr);
+  gimple_seq_add_stmt (&seq, assign);
+
+  /* Define object size right after the object is defined.  */
+  gimple_stmt_iterator i = gsi_for_stmt (stmt);
+  gsi_insert_seq_after (&i, seq, GSI_CONTINUE_LINKING);
+}
+
+static void
+emit_size_phi_stmts (gimple *stmt, tree size_ssa, tree *sizes)
+{
+  gphi *newphi = create_phi_node (size_ssa, gimple_bb (stmt));
+  gphi *obj_phi =  as_a <gphi *> (stmt);
+
+  for (unsigned i = 0; i < gimple_phi_num_args (stmt); i++)
+    {
+      if (!is_gimple_variable (sizes[i]))
+	{
+	  gimple_seq seq;
+	  edge e = gimple_phi_arg_edge (obj_phi, i);
+	  sizes[i] = force_gimple_operand (sizes[i], &seq, true, NULL);
+
+	  /* Put the size definition before the last statement of the source
+	     block of the PHI edge.  This ensures that any branches at the end
+	     of the source block remain the last statement.  We are OK even if
+	     the last statement is the definition of the object since it will
+	     succeed any definitions that contribute to its size and the size
+	     expression will succeed them too.  */
+	  gimple_stmt_iterator gsi = gsi_last_bb (e->src);
+	  gsi_insert_seq_before (&gsi, seq, GSI_CONTINUE_LINKING);
+	}
+
+      add_phi_arg (newphi, sizes[i],
+		   gimple_phi_arg_edge (obj_phi, i),
+		   gimple_phi_arg_location (obj_phi, i));
+    }
+}
+
+static void
+eval_size_expr (tree var, tree size, tree *size_expr)
+{
+  if (size_expr != NULL)
+    {
+      gcc_assert (*size_expr != error_mark_node);
+
+      gimple *stmt = SSA_NAME_DEF_STMT (var);
+
+      if (gimple_code (stmt) == GIMPLE_PHI)
+	{
+	  emit_size_phi_stmts (stmt, size, size_expr);
+	  delete[] size_expr;
+	}
+      else
+	{
+	  emit_size_stmts (stmt, size, *size_expr);
+	  delete size_expr;
+	}
+    }
+}
+
+static void
+gimplify_size_exprs (object_size_info *osi, tree ptr)
+{
+  bitmap_iterator bi;
+  unsigned i;
+
+  /* If the size lookup was not successful and we were left with unresolved
+     loop dependencies, then invalidate all size computations.  This is
+     suboptimal and should eventually try to remove only size expressions that
+     depend on the unresolved dependencies, but it's unclear whether
+     maintaining the extra state to manage that is worthwhile.  */
+  if (object_sizes[osi->object_size_type][SSA_NAME_VERSION (ptr)] == NULL_TREE
+      && osi->deploop)
+    {
+      for (int object_size_type = 0; object_size_type <= 3; object_size_type++)
+	{
+	  EXECUTE_IF_SET_IN_BITMAP (computed[object_size_type], 0, i, bi)
+	    {
+	      release_ssa_name (object_sizes[object_size_type][i]);
+	      if (gimple_code (SSA_NAME_DEF_STMT (ssa_name (i))) == GIMPLE_PHI
+		  && object_size_exprs[object_size_type][i])
+		delete [] object_size_exprs[object_size_type][i];
+	      else
+		delete object_size_exprs[object_size_type][i];
+	      object_size_exprs[object_size_type][i] = NULL;
+	    }
+	  bitmap_clear (computed[object_size_type]);
+	}
+      return;
+    }
+
+  /* Gimplify and emit code for all computed size expressions.  */
+  for (int object_size_type = 0; object_size_type <= 3; object_size_type++)
+    EXECUTE_IF_SET_IN_BITMAP (computed[object_size_type], 0, i, bi)
+      {
+	eval_size_expr (ssa_name (i), object_sizes[object_size_type][i],
+			object_size_exprs[object_size_type][i]);
+	object_size_exprs[object_size_type][i] = NULL;
+      }
+}
+
 /* Compute object size estimate for PTR and set *PSIZE to the resulting value.
    OBJECT_SIZE_TYPE is the second argument to __builtin_dynamic_object_size.
    Returns true on success and false when the object size could not be
    determined.  */
 
 bool
-compute_builtin_dyn_object_size (tree ptr, int object_size_type, tree *psize)
+compute_builtin_dyn_object_size (tree ptr, int object_size_type, tree *psize,
+				 struct function *fun)
 {
   gcc_assert (object_size_type >= 0 && object_size_type <= 3);
 
@@ -195,7 +314,10 @@  compute_builtin_dyn_object_size (tree ptr, int object_size_type, tree *psize)
   unsigned int i;
 
   if (num_ssa_names > object_sizes[object_size_type].length ())
-    object_sizes[object_size_type].safe_grow (num_ssa_names, true);
+    {
+      object_sizes[object_size_type].safe_grow (num_ssa_names, true);
+      object_size_exprs[object_size_type].safe_grow (num_ssa_names, true);
+    }
   if (dump_file)
     {
       fprintf (dump_file, "Computing %s dynamic %sobject size for ",
@@ -206,9 +328,12 @@  compute_builtin_dyn_object_size (tree ptr, int object_size_type, tree *psize)
     }
 
   osi.visited = BITMAP_ALLOC (NULL);
+  osi.deploop = 0;
   osi.object_size_type = object_size_type;
+  osi.fun = fun != NULL ? fun : cfun;
 
   collect_object_sizes_for (&osi, ptr);
+  gimplify_size_exprs (&osi, ptr);
 
   /* Debugging dumps.  */
   if (dump_file)
@@ -234,6 +359,73 @@  out:
   return *psize != NULL_TREE;
 }
 
+static void
+maybe_update_dependency_loop (struct object_size_info *osi, unsigned name,
+			      tree sz)
+{
+  if (sz == error_mark_node)
+    osi->deploop++;
+  else if (object_sizes[osi->object_size_type][name]
+	   && (*object_size_exprs[osi->object_size_type][name]
+	       == error_mark_node))
+    osi->deploop--;
+}
+
+/* Add object size to the cache so that it can be reused.  */
+
+static void
+cache_object_size (struct object_size_info *osi, unsigned name, tree *sz)
+{
+  int object_size_type = osi->object_size_type;
+  struct function *fun = osi->fun;
+
+  gcc_assert (sz);
+
+  maybe_update_dependency_loop (osi, name, *sz);
+
+  /* Reuse SSA name if it was created for a dependency loop.  */
+  if (object_sizes[object_size_type][name] != NULL_TREE)
+    gcc_assert (*object_size_exprs[object_size_type][name] == error_mark_node);
+  else
+    object_sizes[object_size_type][name] = make_ssa_name_fn (fun, sizetype, 0);
+  object_size_exprs[object_size_type][name] = sz;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Caching size for ");
+      print_generic_expr (dump_file, ssa_name (name), dump_flags);
+      fprintf (dump_file, ":: Object size: ");
+      print_generic_expr (dump_file, object_sizes[object_size_type][name],
+			  dump_flags);
+      fprintf (dump_file, " = ");
+      print_generic_expr (dump_file,
+			  *object_size_exprs[object_size_type][name],
+			  dump_flags);
+      fprintf (dump_file, "\n");
+    }
+
+  bitmap_set_bit (computed[object_size_type], name);
+}
+
+/* Copy SZ and then call cache_object_size above.  */
+
+static void
+cache_object_size_copy (struct object_size_info *osi, unsigned name, tree sz)
+{
+  int object_size_type = osi->object_size_type;
+
+  if (sz == NULL_TREE)
+    {
+      if (object_sizes[object_size_type][name] != NULL_TREE)
+	release_ssa_name (object_sizes[object_size_type][name]);
+      object_sizes[object_size_type][name] = NULL_TREE;
+      object_size_exprs[object_size_type][name] = NULL;
+      bitmap_set_bit (computed[object_size_type], name);
+      return;
+    }
+
+  cache_object_size (osi, name, new tree (sz));
+}
 
 /* Use size of ORIG for DEST and return it.  */
 
@@ -241,8 +433,9 @@  static void
 set_object_size_ssa (struct object_size_info *osi, tree dest, tree orig)
 {
   collect_object_sizes_for (osi, orig);
-  object_sizes[osi->object_size_type][SSA_NAME_VERSION (dest)] =
-    object_sizes[osi->object_size_type][SSA_NAME_VERSION (orig)];
+
+  tree sz = object_sizes[osi->object_size_type][SSA_NAME_VERSION (orig)];
+  cache_object_size_copy (osi, SSA_NAME_VERSION (dest), sz);
 }
 
 
@@ -251,11 +444,10 @@  set_object_size_ssa (struct object_size_info *osi, tree dest, tree orig)
 static void
 call_object_size (struct object_size_info *osi, tree ptr, gcall *call)
 {
-  unsigned int varno = SSA_NAME_VERSION (ptr);
-
   gcc_assert (is_gimple_call (call));
 
-  object_sizes[osi->object_size_type][varno] = alloc_object_size (call);
+  cache_object_size_copy (osi, SSA_NAME_VERSION (ptr),
+			  alloc_object_size (call));
 }
 
 
@@ -264,7 +456,9 @@  call_object_size (struct object_size_info *osi, tree ptr, gcall *call)
    - For allocation GIMPLE_CALL like malloc or calloc object size is the size
      of the allocation.
    - For a memcpy like GIMPLE_CALL that always returns one of its arguments,
-     the object size is object size of that argument.  */
+     the object size is object size of that argument.
+   - For GIMPLE_PHI, compute a PHI node with sizes of all branches in the PHI
+     node of the object.  */
 
 static void
 collect_object_sizes_for (struct object_size_info *osi, tree var)
@@ -280,7 +474,10 @@  collect_object_sizes_for (struct object_size_info *osi, tree var)
     object_sizes[object_size_type][varno] = NULL_TREE;
   else
     {
-      /* No dependency loop handling at the moment.  */
+      /* Add an SSA name but mark the expression as being an error_mark_node.
+	 When we go back up the stack, the error_mark_node should get
+	 overwritten by a proper expression.  */
+      cache_object_size (osi, varno, &error_mark_node);
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "Found a dependency loop at ");
@@ -315,18 +512,51 @@  collect_object_sizes_for (struct object_size_info *osi, tree var)
 	break;
       }
 
+    case GIMPLE_PHI:
+      {
+	unsigned i, num_args = gimple_phi_num_args (stmt);
+	tree *sizes = new tree[num_args] ();
+
+	/* Bail out if any of the PHI arguments are non-SSA expressions or
+	   if size of an argument cannot be determined.  */
+	for (i = 0; i < gimple_phi_num_args (stmt); i++)
+	  {
+	    tree rhs = gimple_phi_arg_def (stmt, i);
+
+	    if (TREE_CODE (rhs) != SSA_NAME)
+	      break;
+
+	    collect_object_sizes_for (osi, rhs);
+	    tree sz = object_sizes[object_size_type][SSA_NAME_VERSION (rhs)];
+
+	    if (sz == NULL_TREE)
+	      break;
+
+	    sizes[i] = sz;
+	  }
+
+	/* Record all possible sizes to build our PHI node later.  */
+	if (i == gimple_phi_num_args (stmt))
+	  {
+	    cache_object_size (osi, varno, sizes);
+	    break;
+	  }
+	else
+	  delete[] sizes;
+      }
+    /* FALLTHROUGH */
+
     /* Bail out for all other cases.  */
     case GIMPLE_NOP:
-    case GIMPLE_PHI:
     case GIMPLE_ASSIGN:
     case GIMPLE_ASM:
+      cache_object_size_copy (osi, varno, NULL_TREE);
       break;
 
     default:
       gcc_unreachable ();
     }
-
-  bitmap_set_bit (computed[object_size_type], varno);
+  gcc_assert (bitmap_bit_p (computed[object_size_type], varno));
 }
 
 
@@ -343,6 +573,7 @@  init_dynamic_object_sizes (void)
   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
     {
       object_sizes[object_size_type].safe_grow (num_ssa_names, true);
+      object_size_exprs[object_size_type].safe_grow (num_ssa_names, true);
       computed[object_size_type] = BITMAP_ALLOC (NULL);
     }
 }
@@ -358,6 +589,7 @@  fini_dynamic_object_sizes (void)
   for (object_size_type = 0; object_size_type <= 3; object_size_type++)
     {
       object_sizes[object_size_type].release ();
+      object_size_exprs[object_size_type].release ();
       BITMAP_FREE (computed[object_size_type]);
     }
 }
diff --git a/gcc/tree-dynamic-object-size.h b/gcc/tree-dynamic-object-size.h
index 145b4b88bca..a4e0236e43e 100644
--- a/gcc/tree-dynamic-object-size.h
+++ b/gcc/tree-dynamic-object-size.h
@@ -20,6 +20,7 @@  along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TREE_DYNAMIC_OBJECT_SIZE_H
 #define GCC_TREE_DYNAMIC_OBJECT_SIZE_H
 
-extern bool compute_builtin_dyn_object_size (tree, int, tree *);
+extern bool compute_builtin_dyn_object_size (tree, int, tree *,
+					     struct function * = NULL);
 
 #endif  // GCC_TREE_DYNAMIC_OBJECT_SIZE_H