diff mbox series

[2/8] tree-dynamic-object-size: New pass

Message ID 20211007221432.1029249-3-siddhesh@gotplt.org
State Superseded
Headers show
Series __builtin_dynamic_object_size and more | expand

Commit Message

Siddhesh Poyarekar Oct. 7, 2021, 10:14 p.m. UTC
A new pass is added to execute just before the tree-object-size pass
to recognize and simplify __builtin_dynamic_object_size.  Some key
ideas (such as multipass object size collection to detect reference
loops) have been taken from tree-object-size but is distinct from it
to ensure minimal impact on existing code.

At the moment, the pass only recognizes allocators and passthrough
functions to attempt to derive object size expressions, and replaces
the call site with those expressions.  On failure, it replaces the
__builtin_dynamic_object_size with __builtin_object_size as a
fallback.

gcc/ChangeLog:

	* Makefile.in (OBJS): Add tree-dynamic-object-size.o.
	(PLUGIN_HEADERS): Add tree-dynamic-object-size.h.
	* tree-dynamic-object-size.c: New file.
	* tree-dynamic-object-size.h: New file.
	* builtins.c: Use it.
	(fold_builtin_dyn_object_size): Call
	compute_builtin_dyn_object_size for
	__builtin_dynamic_object_size builtin.
	(passes.def): Add pass_dynamic_object_sizes.
	* tree-pass.h: Add ake_pass_dynamic_object_sizes.

gcc/testsuite/ChangeLog:

	* gcc.dg/builtin-dynamic-object-size-0.c: New test.

Signed-off-by: Siddhesh Poyarekar <siddhesh@gotplt.org>
---
 gcc/Makefile.in                               |  19 +-
 gcc/builtins.c                                |   8 +
 gcc/doc/extend.texi                           |  11 +
 gcc/passes.def                                |   3 +
 .../gcc.dg/builtin-dynamic-object-size-0.c    | 166 ++++++
 gcc/tree-dynamic-object-size.c                | 517 ++++++++++++++++++
 gcc/tree-dynamic-object-size.h                |  25 +
 gcc/tree-pass.h                               |   2 +
 8 files changed, 742 insertions(+), 9 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
 create mode 100644 gcc/tree-dynamic-object-size.c
 create mode 100644 gcc/tree-dynamic-object-size.h

Comments

Siddhesh Poyarekar Oct. 8, 2021, 4:05 a.m. UTC | #1
On 10/8/21 03:44, Siddhesh Poyarekar wrote:
> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
> index 133b82eef38..082d167cd65 100644
> --- a/gcc/doc/extend.texi
> +++ b/gcc/doc/extend.texi
> @@ -12777,6 +12777,17 @@ assert (__builtin_object_size (q, 1) == sizeof (var.b));
>   @end smallexample
>   @end deftypefn
>   
> +@deftypefn {Built-in Function} {size_t} __builtin_dynamic_object_size (const void * @var{ptr}, int @var{type})
> +is similar to @code{__builtin_object_size} in that it returns a number of bytes
> +from @var{ptr} to the end of the object @var{ptr} pointer points to, except
> +that the size returned may not be a constant.  This results in successful
> +evaluation of object size estimates in a wider range of use cases and can be
> +more precise than @code{__builtin_object_size}, but it incurs a performance
> +penalty since it may add a runtime overhead on size computation.  Semantics of
> +@var{type} as well as return values in case it is not possible to determine
> +which objects @var{ptr} points to at compile time are the same as in the case
> +of @code{__builtin_object_size}.
> +

Looks like I had pushed my scratch build without this doc update; this 
fails because I didn't terminate the @deftypefn.  I've fixed it locally 
and will post an updated series along with resolution of feedback I 
receive on the series.

Thanks,
Siddhesh
Jakub Jelinek Oct. 12, 2021, 1:58 p.m. UTC | #2
On Fri, Oct 08, 2021 at 03:44:26AM +0530, Siddhesh Poyarekar wrote:
> A new pass is added to execute just before the tree-object-size pass
> to recognize and simplify __builtin_dynamic_object_size.  Some key
> ideas (such as multipass object size collection to detect reference
> loops) have been taken from tree-object-size but is distinct from it
> to ensure minimal impact on existing code.
> 
> At the moment, the pass only recognizes allocators and passthrough
> functions to attempt to derive object size expressions, and replaces
> the call site with those expressions.  On failure, it replaces the
> __builtin_dynamic_object_size with __builtin_object_size as a
> fallback.

Not full review, just nits for now:
I don't really like using separate passes for this, whether
it should be done in the same source or different source file
is something less clear, I guess it depends on how much from
tree-object-size.[ch] can be reused, how much could be e.g. done
by pretending the 0-3 operands of __builtin_dynamic_object_size
are actually 4-7 and have [8] arrays in tree-object-size.[ch]
to track that and how much is separate.
I think the common case is either that a function won't
contain any of the builtin calls (most likely on non-glibc targets,
but even on glibc targets for most of the code that doesn't use any
of the fortified APIs), or it uses just one of them and not both
(e.g. glibc -D_FORTIFY_SOURCE={1,2} vs. -D_FORTIFY_SOURCE=3),
so either one or the other pass would just uselessly walk the whole
IL.
The objsz passes are walk over the whole IL, if they see
__bos calls, do something and call something in the end
and your pass is similar, so hooking it into the current pass
is trivial, just if
if (!gimple_call_builtin_p (call, BUILT_IN_OBJECT_SIZE))
before doing continue; check for the other builtin and call
a function to handle it, either from the same or different file,
and then at the end destruct what is needed too.
Especially on huge functions, each IL traversal may need to page into
caches (and out of them) lots of statements...

> 	* Makefile.in (OBJS): Add tree-dynamic-object-size.o.
> 	(PLUGIN_HEADERS): Add tree-dynamic-object-size.h.
> 	* tree-dynamic-object-size.c: New file.
> 	* tree-dynamic-object-size.h: New file.
> 	* builtins.c: Use it.
> 	(fold_builtin_dyn_object_size): Call
> 	compute_builtin_dyn_object_size for
> 	__builtin_dynamic_object_size builtin.
> 	(passes.def): Add pass_dynamic_object_sizes.
> 	* tree-pass.h: Add ake_pass_dynamic_object_sizes.

Missing m in ake

> +  if (TREE_CODE (ptr) == SSA_NAME
> +      && compute_builtin_dyn_object_size (ptr, object_size_type, &bytes))

Please don't abbreviate.

> +  object_sizes[osi->object_size_type][SSA_NAME_VERSION (dest)] =
> +    object_sizes[osi->object_size_type][SSA_NAME_VERSION (orig)];

GCC coding convention don't want to see the = at the end of line, it should
be at the start of the next line after indentation.

> +/* Initialize data structures for the object size computation.  */
> +
> +void
> +init_dynamic_object_sizes (void)
> +{
> +  int object_size_type;
> +
> +  if (computed[0])
> +    return;
> +
> +  for (object_size_type = 0; object_size_type <= 3; object_size_type++)
> +    {
> +      object_sizes[object_size_type].safe_grow (num_ssa_names, true);
> +      computed[object_size_type] = BITMAP_ALLOC (NULL);
> +    }
> +}
> +
> +
> +unsigned int
> +dynamic_object_sizes_execute (function *fun, bool lower_to_bos)
> +{
> +  basic_block bb;
> +
> +  init_dynamic_object_sizes ();
> +

I'd prefer if the initialization could be done only lazily if
it sees at least one such call like the objsz pass does.  That is why
there is the if (computed[0]) return; at the start...

	Jakub
Siddhesh Poyarekar Oct. 12, 2021, 2:28 p.m. UTC | #3
On 10/12/21 19:28, Jakub Jelinek wrote:
> On Fri, Oct 08, 2021 at 03:44:26AM +0530, Siddhesh Poyarekar wrote:
>> A new pass is added to execute just before the tree-object-size pass
>> to recognize and simplify __builtin_dynamic_object_size.  Some key
>> ideas (such as multipass object size collection to detect reference
>> loops) have been taken from tree-object-size but is distinct from it
>> to ensure minimal impact on existing code.
>>
>> At the moment, the pass only recognizes allocators and passthrough
>> functions to attempt to derive object size expressions, and replaces
>> the call site with those expressions.  On failure, it replaces the
>> __builtin_dynamic_object_size with __builtin_object_size as a
>> fallback.
> 
> Not full review, just nits for now:
> I don't really like using separate passes for this, whether
> it should be done in the same source or different source file
> is something less clear, I guess it depends on how much from
> tree-object-size.[ch] can be reused, how much could be e.g. done
> by pretending the 0-3 operands of __builtin_dynamic_object_size
> are actually 4-7 and have [8] arrays in tree-object-size.[ch]
> to track that and how much is separate.
> I think the common case is either that a function won't
> contain any of the builtin calls (most likely on non-glibc targets,
> but even on glibc targets for most of the code that doesn't use any
> of the fortified APIs), or it uses just one of them and not both
> (e.g. glibc -D_FORTIFY_SOURCE={1,2} vs. -D_FORTIFY_SOURCE=3),
> so either one or the other pass would just uselessly walk the whole
> IL.

Thanks, that makes sense, I'll make it into a single pass.  My main 
motivation was to keep the code separate to have minimal impact but I 
can do that in the same pass too.  The secondary motivation (or more 
like ambition), i.e. deprecating the __bos pass can be done even if it 
were all one pass, maybe even simpler.

> The objsz passes are walk over the whole IL, if they see
> __bos calls, do something and call something in the end
> and your pass is similar, so hooking it into the current pass
> is trivial, just if
> if (!gimple_call_builtin_p (call, BUILT_IN_OBJECT_SIZE))
> before doing continue; check for the other builtin and call
> a function to handle it, either from the same or different file,
> and then at the end destruct what is needed too.
> Especially on huge functions, each IL traversal may need to page into
> caches (and out of them) lots of statements...

Agreed, I'll work the entry points into tree-object-size.

> 
>> 	* Makefile.in (OBJS): Add tree-dynamic-object-size.o.
>> 	(PLUGIN_HEADERS): Add tree-dynamic-object-size.h.
>> 	* tree-dynamic-object-size.c: New file.
>> 	* tree-dynamic-object-size.h: New file.
>> 	* builtins.c: Use it.
>> 	(fold_builtin_dyn_object_size): Call
>> 	compute_builtin_dyn_object_size for
>> 	__builtin_dynamic_object_size builtin.
>> 	(passes.def): Add pass_dynamic_object_sizes.
>> 	* tree-pass.h: Add ake_pass_dynamic_object_sizes.
> 
> Missing m in ake
> 
>> +  if (TREE_CODE (ptr) == SSA_NAME
>> +      && compute_builtin_dyn_object_size (ptr, object_size_type, &bytes))
> 
> Please don't abbreviate.
> 
>> +  object_sizes[osi->object_size_type][SSA_NAME_VERSION (dest)] =
>> +    object_sizes[osi->object_size_type][SSA_NAME_VERSION (orig)];
> 
> GCC coding convention don't want to see the = at the end of line, it should
> be at the start of the next line after indentation.
> 
>> +/* Initialize data structures for the object size computation.  */
>> +
>> +void
>> +init_dynamic_object_sizes (void)
>> +{
>> +  int object_size_type;
>> +
>> +  if (computed[0])
>> +    return;
>> +
>> +  for (object_size_type = 0; object_size_type <= 3; object_size_type++)
>> +    {
>> +      object_sizes[object_size_type].safe_grow (num_ssa_names, true);
>> +      computed[object_size_type] = BITMAP_ALLOC (NULL);
>> +    }
>> +}
>> +
>> +
>> +unsigned int
>> +dynamic_object_sizes_execute (function *fun, bool lower_to_bos)
>> +{
>> +  basic_block bb;
>> +
>> +  init_dynamic_object_sizes ();
>> +
> 
> I'd prefer if the initialization could be done only lazily if
> it sees at least one such call like the objsz pass does.  That is why
> there is the if (computed[0]) return; at the start...

OK, will fix all these nits too.

Thanks,
Siddhesh
diff mbox series

Patch

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f36ffa4740b..5189dcfcc0d 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1608,6 +1608,7 @@  OBJS = \
 	tree-diagnostic.o \
 	tree-diagnostic-path.o \
 	tree-dump.o \
+	tree-dynamic-object-size.o \
 	tree-eh.o \
 	tree-emutls.o \
 	tree-if-conv.o \
@@ -3647,15 +3648,15 @@  PLUGIN_HEADERS = $(TREE_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
   ssa-iterators.h $(RESOURCE_H) tree-cfgcleanup.h attribs.h calls.h \
   cfgexpand.h diagnostic-color.h gcc-symtab.h gimple-builder.h gimple-low.h \
   gimple-walk.h gimplify-me.h pass_manager.h print-rtl.h stmt.h \
-  tree-dfa.h tree-hasher.h tree-nested.h tree-object-size.h tree-outof-ssa.h \
-  tree-parloops.h tree-ssa-address.h tree-ssa-coalesce.h tree-ssa-dom.h \
-  tree-ssa-loop.h tree-ssa-loop-ivopts.h tree-ssa-loop-manip.h \
-  tree-ssa-loop-niter.h tree-ssa-ter.h tree-ssa-threadedge.h \
-  tree-ssa-threadupdate.h inchash.h wide-int.h signop.h hash-map.h \
-  hash-set.h dominance.h cfg.h cfgrtl.h cfganal.h cfgbuild.h cfgcleanup.h \
-  lcm.h cfgloopmanip.h file-prefix-map.h builtins.def $(INSN_ATTR_H) \
-  pass-instances.def params.list $(srcdir)/../include/gomp-constants.h \
-  $(EXPR_H)
+  tree-dfa.h tree-dynamic-object-size.h tree-hasher.h tree-nested.h \
+  tree-object-size.h tree-outof-ssa.h tree-parloops.h tree-ssa-address.h \
+  tree-ssa-coalesce.h tree-ssa-dom.h tree-ssa-loop.h tree-ssa-loop-ivopts.h \
+  tree-ssa-loop-manip.h tree-ssa-loop-niter.h tree-ssa-ter.h \
+  tree-ssa-threadedge.h tree-ssa-threadupdate.h inchash.h wide-int.h signop.h \
+  hash-map.h hash-set.h dominance.h cfg.h cfgrtl.h cfganal.h cfgbuild.h \
+  cfgcleanup.h lcm.h cfgloopmanip.h file-prefix-map.h builtins.def \
+  $(INSN_ATTR_H) pass-instances.def params.list \
+  $(srcdir)/../include/gomp-constants.h $(EXPR_H)
 
 # generate the 'build fragment' b-header-vars
 s-header-vars: Makefile
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 894d62359b4..d015029765b 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -48,6 +48,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "calls.h"
 #include "varasm.h"
 #include "tree-object-size.h"
+#include "tree-dynamic-object-size.h"
 #include "tree-ssa-strlen.h"
 #include "realmpfr.h"
 #include "cfgrtl.h"
@@ -10325,6 +10326,7 @@  static tree
 fold_builtin_dyn_object_size (tree ptr, tree ost)
 {
   int object_size_type;
+  tree bytes;
 
   if (!valid_object_size_args (ptr, ost, &object_size_type))
     return NULL_TREE;
@@ -10335,6 +10337,12 @@  fold_builtin_dyn_object_size (tree ptr, tree ost)
   if (TREE_SIDE_EFFECTS (ptr))
     return build_int_cst_type (size_type_node, object_size_type < 2 ? -1 : 0);
 
+  /* If object size expression cannot be evaluated yet, delay folding until
+     later.  Maybe subsequent passes will help determining it.  */
+  if (TREE_CODE (ptr) == SSA_NAME
+      && compute_builtin_dyn_object_size (ptr, object_size_type, &bytes))
+    return bytes;
+
   return NULL_TREE;
 }
 
diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
index 133b82eef38..082d167cd65 100644
--- a/gcc/doc/extend.texi
+++ b/gcc/doc/extend.texi
@@ -12777,6 +12777,17 @@  assert (__builtin_object_size (q, 1) == sizeof (var.b));
 @end smallexample
 @end deftypefn
 
+@deftypefn {Built-in Function} {size_t} __builtin_dynamic_object_size (const void * @var{ptr}, int @var{type})
+is similar to @code{__builtin_object_size} in that it returns a number of bytes
+from @var{ptr} to the end of the object @var{ptr} pointer points to, except
+that the size returned may not be a constant.  This results in successful
+evaluation of object size estimates in a wider range of use cases and can be
+more precise than @code{__builtin_object_size}, but it incurs a performance
+penalty since it may add a runtime overhead on size computation.  Semantics of
+@var{type} as well as return values in case it is not possible to determine
+which objects @var{ptr} points to at compile time are the same as in the case
+of @code{__builtin_object_size}.
+
 There are built-in functions added for many common string operation
 functions, e.g., for @code{memcpy} @code{__builtin___memcpy_chk}
 built-in is provided.  This built-in has an additional last argument,
diff --git a/gcc/passes.def b/gcc/passes.def
index c11c237f6d2..7dc55cc6ba0 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -74,6 +74,7 @@  along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_all_early_optimizations);
       PUSH_INSERT_PASSES_WITHIN (pass_all_early_optimizations)
 	  NEXT_PASS (pass_remove_cgraph_callee_edges);
+	  NEXT_PASS (pass_early_dynamic_object_sizes);
 	  NEXT_PASS (pass_early_object_sizes);
 	  /* Don't record nonzero bits before IPA to avoid
 	     using too much memory.  */
@@ -198,6 +199,7 @@  along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_ccp, true /* nonzero_p */);
       /* After CCP we rewrite no longer addressed locals into SSA
 	 form if possible.  */
+      NEXT_PASS (pass_dynamic_object_sizes);
       NEXT_PASS (pass_object_sizes);
       NEXT_PASS (pass_post_ipa_warn);
       NEXT_PASS (pass_complete_unrolli);
@@ -379,6 +381,7 @@  along with GCC; see the file COPYING3.  If not see
       /* Perform simple scalar cleanup which is constant/copy propagation.  */
       NEXT_PASS (pass_ccp, true /* nonzero_p */);
       NEXT_PASS (pass_post_ipa_warn);
+      NEXT_PASS (pass_dynamic_object_sizes);
       NEXT_PASS (pass_object_sizes);
       /* Fold remaining builtins.  */
       NEXT_PASS (pass_fold_builtins);
diff --git a/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c b/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
new file mode 100644
index 00000000000..620e8cbc611
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c
@@ -0,0 +1,166 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+typedef __SIZE_TYPE__ size_t;
+#define abort __builtin_abort
+
+void *
+__attribute__ ((alloc_size (1)))
+__attribute__ ((__nothrow__ , __leaf__))
+__attribute__ ((noinline))
+alloc_func (size_t sz)
+{
+  return __builtin_malloc (sz);
+}
+
+void *
+__attribute__ ((alloc_size (1, 2)))
+__attribute__ ((__nothrow__ , __leaf__))
+__attribute__ ((noinline))
+calloc_func (size_t cnt, size_t sz)
+{
+  return __builtin_calloc (cnt, sz);
+}
+
+void *
+__attribute__ ((noinline))
+unknown_allocator (size_t cnt, size_t sz)
+{
+  return __builtin_calloc (cnt, sz);
+}
+
+size_t
+__attribute__ ((noinline))
+test_unknown (size_t cnt, size_t sz)
+{
+  void *ret = unknown_allocator (cnt, sz);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+/* Malloc-like allocator.  */
+
+size_t
+__attribute__ ((noinline))
+test_malloc (size_t sz)
+{
+  void *ret = alloc_func (sz);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_malloc (size_t sz)
+{
+  void *ret = __builtin_malloc (sz);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_malloc_cond (int cond)
+{
+  void *ret = __builtin_malloc (cond ? 32 : 64);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+/* Calloc-like allocator.  */
+
+size_t
+__attribute__ ((noinline))
+test_calloc (size_t cnt, size_t sz)
+{
+  void *ret = calloc_func (cnt, sz);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_calloc (size_t cnt, size_t sz)
+{
+  void *ret = __builtin_calloc (cnt, sz);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_builtin_calloc_cond (int cond1, int cond2)
+{
+  void *ret = __builtin_calloc (cond1 ? 32 : 64, cond2 ? 1024 : 16);
+  return __builtin_dynamic_object_size (ret, 0);
+}
+
+/* Passthrough functions.  */
+
+size_t
+__attribute__ ((noinline))
+test_passthrough (size_t sz, char *in)
+{
+  char *bin = __builtin_malloc (sz);
+  char *dest = __builtin_memcpy (bin, in, sz);
+
+  return __builtin_dynamic_object_size (dest, 0);
+}
+
+/* Variable length arrays.  */
+size_t
+__attribute__ ((noinline))
+test_dynarray (size_t sz)
+{
+  char bin[sz];
+
+  return __builtin_dynamic_object_size (bin, 0);
+}
+
+size_t
+__attribute__ ((noinline))
+test_dynarray_cond (int cond)
+{
+  char bin[cond ? 8 : 16];
+
+  return __builtin_dynamic_object_size (bin, 0);
+}
+
+int
+main (int argc, char **argv)
+{
+  unsigned nfails = 0;
+
+#define FAIL() ({ \
+  __builtin_printf ("Failure at line: %d\n", __LINE__);			      \
+  nfails++;								      \
+})
+
+  size_t outsz = test_unknown (32, 42);
+  if (outsz != -1 && outsz != 32)
+    FAIL ();
+  if (test_malloc (2048) != 2048)
+    FAIL ();
+  if (test_builtin_malloc (2048) != 2048)
+    FAIL ();
+  if (test_builtin_malloc_cond (1) != 32)
+    FAIL ();
+  if (test_builtin_malloc_cond (0) != 64)
+    FAIL ();
+  if (test_calloc (2048, 4) != 2048 * 4)
+    FAIL ();
+  if (test_builtin_calloc (2048, 8) != 2048 * 8)
+    FAIL ();
+  if (test_builtin_calloc_cond (0, 0) != 64 * 16)
+    FAIL ();
+  if (test_builtin_calloc_cond (1, 1) != 32 * 1024)
+    FAIL ();
+  if (test_passthrough (__builtin_strlen (argv[0]) + 1, argv[0])
+      != __builtin_strlen (argv[0]) + 1)
+    FAIL ();
+  if (test_dynarray (__builtin_strlen (argv[0])) != __builtin_strlen (argv[0]))
+    FAIL ();
+  if (test_dynarray_cond (0) != 16)
+    FAIL ();
+  if (test_dynarray_cond (1) != 8)
+    FAIL ();
+
+  if (nfails > 0)
+    __builtin_abort ();
+
+  return 0;
+}
diff --git a/gcc/tree-dynamic-object-size.c b/gcc/tree-dynamic-object-size.c
new file mode 100644
index 00000000000..8e52dd46c03
--- /dev/null
+++ b/gcc/tree-dynamic-object-size.c
@@ -0,0 +1,517 @@ 
+/* __builtin_dynamic_object_size (ptr, object_size_type) computation
+   Copyright (C) 2021 Siddhesh Poyarekar <siddhesh@gotplt.org>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* __builtin_dynamic_object_size returns richer object size information with
+   the intent of improving precision of checks that depend on object sizes.  It
+   is a drop-in replacement for __builtin_object_size due to having the
+   following common semantics:
+
+   * Both take the same arguments.
+   * Like __builtin_object_size, __builtin_dynamic_object_size also provides an
+     estimate (either lower or higher, based on the second argument) of the
+     object size and not the precise object size.
+   * On failure, both return either (size_t)-1 or (size_t)0 depending on the
+     second byte of the TYPE argument.
+
+   There are minor semantic differences in both builtins:
+
+   * On success, __builtin_dynamic_object_size is more likely to return the
+     closest object size, since it may return one of the following:
+     - An expression that evaluates to the exact object size
+     - When the exact size is not available, an expression that evaluates to
+       the maximum or minimum estimate of the size of the object.  Currently
+       this is a constant since the pass simplifies
+       __builtin_dynamic_object_size to __builtin_object_size if it cannot
+       determine a size expression.  However in future it could be a
+       non-constant expression.
+
+   See definition of collect_object_sizes_for to know what patterns are
+   currently recognized.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "tree-object-size.h"
+#include "gimple-fold.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "stringpool.h"
+#include "attribs.h"
+#include "builtins.h"
+#include "print-tree.h"
+
+struct object_size_info
+{
+  int object_size_type;
+  bitmap visited;
+};
+
+static tree alloc_object_size (const gcall *);
+static tree pass_through_call (const gcall *);
+static void collect_object_sizes_for (struct object_size_info *, tree);
+
+/* object_sizes[0] is upper bound for number of bytes till the end of
+   the object.
+   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.  */
+static vec<tree> object_sizes[4];
+
+/* Bitmaps what object sizes have been computed already.  */
+static bitmap computed[4];
+
+/* Compute __builtin_dynamic_object_size for CALL, which is a GIMPLE_CALL.
+   Handles calls to functions declared with attribute alloc_size.
+   OBJECT_SIZE_TYPE is the second argument from __builtin_dynamic_object_size.
+   If unknown, return NULL_TREE.  */
+
+static tree
+alloc_object_size (const gcall *call)
+{
+  gcc_assert (is_gimple_call (call));
+
+  tree calltype;
+  tree callfn = gimple_call_fndecl (call);
+
+  if (callfn)
+    calltype = TREE_TYPE (callfn);
+  else
+    calltype = gimple_call_fntype (call);
+
+  if (!calltype)
+    return NULL_TREE;
+
+  /* Set to positions of alloc_size arguments.  */
+  int arg1 = -1, arg2 = -1;
+  tree alloc_size = lookup_attribute ("alloc_size",
+				      TYPE_ATTRIBUTES (calltype));
+  if (alloc_size && TREE_VALUE (alloc_size))
+    {
+      tree p = TREE_VALUE (alloc_size);
+
+      arg1 = TREE_INT_CST_LOW (TREE_VALUE (p))-1;
+      if (TREE_CHAIN (p))
+	arg2 = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (p)))-1;
+    }
+  else if (gimple_call_builtin_p (call, BUILT_IN_NORMAL)
+	   && callfn && ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callfn)))
+    arg1 = 0;
+
+  if (arg1 < 0 || arg1 >= (int)gimple_call_num_args (call)
+      || arg2 >= (int)gimple_call_num_args (call))
+    return NULL_TREE;
+
+  if (arg2 >= 0)
+    {
+      tree ret = fold_build2 (MULT_EXPR, sizetype,
+			      fold_convert (sizetype, gimple_call_arg (call,
+								       arg1)),
+			      fold_convert (sizetype, gimple_call_arg (call,
+								       arg2)));
+      return STRIP_NOPS (ret);
+    }
+  else if (arg1 >= 0)
+    {
+      tree ret = fold_convert (sizetype, gimple_call_arg (call, arg1));
+      return STRIP_NOPS (ret);
+    }
+
+  return NULL_TREE;
+}
+
+
+/* If object size is propagated from one of function's arguments directly
+   to its return value, return that argument for GIMPLE_CALL statement CALL.
+   Otherwise return NULL.  */
+
+static tree
+pass_through_call (const gcall *call)
+{
+  unsigned rf = gimple_call_return_flags (call);
+  if (rf & ERF_RETURNS_ARG)
+    {
+      unsigned argnum = rf & ERF_RETURN_ARG_MASK;
+      if (argnum < gimple_call_num_args (call))
+	return gimple_call_arg (call, argnum);
+    }
+
+  /* __builtin_assume_aligned is intentionally not marked RET1.  */
+  if (gimple_call_builtin_p (call, BUILT_IN_ASSUME_ALIGNED))
+    return gimple_call_arg (call, 0);
+
+  return NULL_TREE;
+}
+
+/* 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)
+{
+  gcc_assert (object_size_type >= 0 && object_size_type <= 3);
+
+  /* Set to unknown and overwrite just before returning if the size
+     could be determined.  */
+  *psize = NULL_TREE;
+
+  if (TREE_CODE (ptr) != SSA_NAME
+      || !POINTER_TYPE_P (TREE_TYPE (ptr)))
+      return false;
+
+  if (computed[object_size_type] == NULL)
+    return false;
+
+  if (bitmap_bit_p (computed[object_size_type], SSA_NAME_VERSION (ptr)))
+    goto out;
+
+  struct object_size_info osi;
+  bitmap_iterator bi;
+  unsigned int i;
+
+  if (num_ssa_names > object_sizes[object_size_type].length ())
+    object_sizes[object_size_type].safe_grow (num_ssa_names, true);
+  if (dump_file)
+    {
+      fprintf (dump_file, "Computing %s dynamic %sobject size for ",
+	       (object_size_type & 2) ? "minimum" : "maximum",
+	       (object_size_type & 1) ? "sub" : "");
+      print_generic_expr (dump_file, ptr, dump_flags);
+      fprintf (dump_file, ":\n");
+    }
+
+  osi.visited = BITMAP_ALLOC (NULL);
+  osi.object_size_type = object_size_type;
+
+  collect_object_sizes_for (&osi, ptr);
+
+  /* Debugging dumps.  */
+  if (dump_file)
+    {
+      EXECUTE_IF_SET_IN_BITMAP (osi.visited, 0, i, bi)
+	if (object_sizes[object_size_type][i] != NULL_TREE)
+	  {
+	    print_generic_expr (dump_file, ssa_name (i),
+				dump_flags);
+	    fprintf (dump_file, ": %s dynamic %sobject size ",
+		     (object_size_type & 2) ? "minimum" : "maximum",
+		     (object_size_type & 1) ? "sub" : "");
+	    print_generic_expr (dump_file, object_sizes[object_size_type][i],
+				dump_flags);
+	    fprintf (dump_file, ":\n");
+	  }
+    }
+
+  BITMAP_FREE (osi.visited);
+
+out:
+  *psize = object_sizes[object_size_type][SSA_NAME_VERSION (ptr)];
+  return *psize != NULL_TREE;
+}
+
+
+/* Use size of ORIG for DEST and return it.  */
+
+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)];
+}
+
+
+/* Compute object_sizes for PTR, defined to the result of a call.  */
+
+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);
+}
+
+
+/* Compute object sizes for VAR.
+
+   - 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.  */
+
+static void
+collect_object_sizes_for (struct object_size_info *osi, tree var)
+{
+  int object_size_type = osi->object_size_type;
+  unsigned int varno = SSA_NAME_VERSION (var);
+  gimple *stmt;
+
+  if (bitmap_bit_p (computed[object_size_type], varno))
+    return;
+
+  if (bitmap_set_bit (osi->visited, varno))
+    object_sizes[object_size_type][varno] = NULL_TREE;
+  else
+    {
+      /* No dependency loop handling at the moment.  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Found a dependency loop at ");
+	  print_generic_expr (dump_file, var, dump_flags);
+	  fprintf (dump_file, "\n");
+	}
+      return;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Visiting use-def links for ");
+      print_generic_expr (dump_file, var, dump_flags);
+      fprintf (dump_file, "\n");
+    }
+
+  stmt = SSA_NAME_DEF_STMT (var);
+
+  switch (gimple_code (stmt))
+    {
+    case GIMPLE_CALL:
+      {
+	gcall *call_stmt = as_a <gcall *> (stmt);
+	tree arg = pass_through_call (call_stmt);
+	if (arg)
+	  {
+	    if (TREE_CODE (arg) == SSA_NAME)
+	      set_object_size_ssa (osi, var, arg);
+	  }
+	else
+	  call_object_size (osi, var, call_stmt);
+	break;
+      }
+
+    /* Bail out for all other cases.  */
+    case GIMPLE_NOP:
+    case GIMPLE_PHI:
+    case GIMPLE_ASSIGN:
+    case GIMPLE_ASM:
+      break;
+
+    default:
+      gcc_unreachable ();
+    }
+
+  bitmap_set_bit (computed[object_size_type], varno);
+}
+
+
+/* Initialize data structures for the object size computation.  */
+
+void
+init_dynamic_object_sizes (void)
+{
+  int object_size_type;
+
+  if (computed[0])
+    return;
+
+  for (object_size_type = 0; object_size_type <= 3; object_size_type++)
+    {
+      object_sizes[object_size_type].safe_grow (num_ssa_names, true);
+      computed[object_size_type] = BITMAP_ALLOC (NULL);
+    }
+}
+
+
+/* Destroy data structures after the object size computation.  */
+
+void
+fini_dynamic_object_sizes (void)
+{
+  int object_size_type;
+
+  for (object_size_type = 0; object_size_type <= 3; object_size_type++)
+    {
+      object_sizes[object_size_type].release ();
+      BITMAP_FREE (computed[object_size_type]);
+    }
+}
+
+unsigned int
+dynamic_object_sizes_execute (function *fun, bool lower_to_bos)
+{
+  basic_block bb;
+
+  init_dynamic_object_sizes ();
+
+  FOR_EACH_BB_FN (bb, fun)
+    {
+      gimple_stmt_iterator i;
+      for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
+	{
+	  gimple *call = gsi_stmt (i);
+
+	  if (!gimple_call_builtin_p (call, BUILT_IN_DYN_OBJECT_SIZE))
+	    continue;
+
+	  tree lhs = gimple_call_lhs (call);
+	  if (!lhs)
+	    continue;
+
+	  unsigned numargs = gimple_call_num_args (call);
+	  tree *args = XALLOCAVEC (tree, numargs);
+	  args[0] = gimple_call_arg (call, 0);
+	  args[1] = gimple_call_arg (call, 1);
+
+	  location_t loc = EXPR_LOC_OR_LOC (args[0], input_location);
+	  tree result_type = gimple_call_return_type (as_a <gcall *> (call));
+	  tree result = fold_builtin_call_array (loc, result_type,
+						 gimple_call_fn (call),
+						 numargs, args);
+
+	  if (result)
+	    {
+	      /* fold_builtin_call_array may wrap the result inside a
+		 NOP_EXPR.  */
+	      STRIP_NOPS (result);
+	      gimplify_and_update_call_from_tree (&i, result);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Simplified builtin in\n  ");
+		  print_gimple_stmt (dump_file, call, 0, dump_flags);
+		  fprintf (dump_file, " to ");
+		  print_generic_expr (dump_file, result);
+		  fprintf (dump_file, "\n");
+		}
+	    }
+	  else if (lower_to_bos)
+	    {
+	      /* If we could not find a suitable size expression, lower to
+		 __builtin_object_size so that we may at least get a constant
+		 lower or higher estimate.  */
+	      tree bosfn = builtin_decl_implicit (BUILT_IN_OBJECT_SIZE);
+	      gimple_call_set_fndecl (call, bosfn);
+	      gimple_call_set_arg (call, 0, args[0]);
+	      gimple_call_set_arg (call, 1, args[1]);
+	      update_stmt (call);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  print_generic_expr (dump_file, args[0], dump_flags);
+		  fprintf (dump_file,
+			   ": Simplified to __builtin_object_size\n");
+		}
+	    }
+	}
+    }
+
+  fini_dynamic_object_sizes ();
+  return 0;
+}
+
+/* Evaluate __builtin_dynamic_object_size () builtins early.  */
+
+namespace {
+
+const pass_data pass_data_early_dynamic_object_sizes =
+{
+  GIMPLE_PASS, /* type */
+  "early_dynobjsz", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_NONE, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_early_dynamic_object_sizes : public gimple_opt_pass
+{
+public:
+  pass_early_dynamic_object_sizes (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_early_dynamic_object_sizes, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_early_dynamic_object_sizes (m_ctxt); }
+  virtual unsigned int execute (function *fun)
+  {
+    return dynamic_object_sizes_execute (fun, false);
+  }
+}; // class pass_early_dynamic_object_sizes
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_early_dynamic_object_sizes (gcc::context *ctxt)
+{
+  return new pass_early_dynamic_object_sizes (ctxt);
+}
+
+/* Evaluate __builtin_dynamic_object_size () builtins, simplifying to
+   __builtin_object_size () if a size expression cannot be produced.  */
+
+namespace {
+
+const pass_data pass_data_dynamic_object_sizes =
+{
+  GIMPLE_PASS, /* type */
+  "dynobjsz", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_NONE, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  0, /* todo_flags_finish */
+};
+
+class pass_dynamic_object_sizes : public gimple_opt_pass
+{
+public:
+  pass_dynamic_object_sizes (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_dynamic_object_sizes, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  opt_pass * clone () { return new pass_dynamic_object_sizes (m_ctxt); }
+  virtual unsigned int execute (function *fun)
+  {
+    return dynamic_object_sizes_execute (fun, true);
+  }
+}; // class pass_dynamic_object_sizes
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_dynamic_object_sizes (gcc::context *ctxt)
+{
+  return new pass_dynamic_object_sizes (ctxt);
+}
diff --git a/gcc/tree-dynamic-object-size.h b/gcc/tree-dynamic-object-size.h
new file mode 100644
index 00000000000..145b4b88bca
--- /dev/null
+++ b/gcc/tree-dynamic-object-size.h
@@ -0,0 +1,25 @@ 
+/* Declarations for tree-dynamic-object-size.c.
+   Copyright (C) 2021 Siddhesh Poyarekar <siddhesh@gotplt.org>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_TREE_DYNAMIC_OBJECT_SIZE_H
+#define GCC_TREE_DYNAMIC_OBJECT_SIZE_H
+
+extern bool compute_builtin_dyn_object_size (tree, int, tree *);
+
+#endif  // GCC_TREE_DYNAMIC_OBJECT_SIZE_H
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 84477a47b88..d81460d0703 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -430,7 +430,9 @@  extern gimple_opt_pass *make_pass_oacc_loop_designation (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_omp_oacc_neuter_broadcast (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_oacc_device_lower (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_omp_device_lower (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_dynamic_object_sizes (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_object_sizes (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_early_dynamic_object_sizes (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_early_object_sizes (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_warn_access (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_warn_printf (gcc::context *ctxt);