@@ -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 ();
@@ -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]);
}
}
@@ -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