From patchwork Thu Oct 7 22:14:28 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Siddhesh Poyarekar X-Patchwork-Id: 1538046 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gotplt.org header.i=@gotplt.org header.a=rsa-sha1 header.s=gotplt.org header.b=LizX6vta; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4HQQgW1MKbz9sRN for ; Fri, 8 Oct 2021 09:17:59 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CDC3D3857C73 for ; Thu, 7 Oct 2021 22:17:56 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from quail.birch.relay.mailchannels.net (quail.birch.relay.mailchannels.net [23.83.209.151]) by sourceware.org (Postfix) with ESMTPS id 66D3E3857825 for ; Thu, 7 Oct 2021 22:15:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 66D3E3857825 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=gotplt.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gotplt.org X-Sender-Id: dreamhost|x-authsender|siddhesh@gotplt.org Received: from relay.mailchannels.net (localhost [127.0.0.1]) by relay.mailchannels.net (Postfix) with ESMTP id 0D9F0922E92; Thu, 7 Oct 2021 22:15:12 +0000 (UTC) Received: from pdx1-sub0-mail-a17.g.dreamhost.com (100-96-18-141.trex.outbound.svc.cluster.local [100.96.18.141]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 08799922E91; Thu, 7 Oct 2021 22:15:08 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|siddhesh@gotplt.org Received: from pdx1-sub0-mail-a17.g.dreamhost.com (pop.dreamhost.com [64.90.62.162]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384) by 100.96.18.141 (trex/6.4.3); Thu, 07 Oct 2021 22:15:12 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|siddhesh@gotplt.org X-MailChannels-Auth-Id: dreamhost X-Cellar-Macabre: 76f9bfeb1ea48ef1_1633644908323_3643191777 X-MC-Loop-Signature: 1633644908323:3941454572 X-MC-Ingress-Time: 1633644908323 Received: from pdx1-sub0-mail-a17.g.dreamhost.com (localhost [127.0.0.1]) by pdx1-sub0-mail-a17.g.dreamhost.com (Postfix) with ESMTP id BAB5683495; Thu, 7 Oct 2021 15:15:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gotplt.org; h=from:to:cc :subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; s=gotplt.org; bh=xoCTAd2pCRh0oKsJbHZ VOPSANtU=; b=LizX6vtaIbGzWmbKrKDT1fcM+z7sgnoZ2xVwqrqQjM9rsf5ghlO X22Jx6ZJMYJsde1/ohgjZE1W7W38++V6VvuMESr7EU8Tj8N5AON/LCUZoGAaHDpC MhUvyjq+Uhc2OlO26sZkKmzRKuP5mK7S0C7rJcqchlhmWeInWUk7Feb0= Received: from rhbox.redhat.com (unknown [1.186.223.58]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) (Authenticated sender: siddhesh@gotplt.org) by pdx1-sub0-mail-a17.g.dreamhost.com (Postfix) with ESMTPSA id 5D2748348D; Thu, 7 Oct 2021 15:15:01 -0700 (PDT) X-DH-BACKEND: pdx1-sub0-mail-a17 From: Siddhesh Poyarekar To: gcc-patches@gcc.gnu.org Subject: [PATCH 4/8] tree-dynamic-object-size: Support ADDR_EXPR Date: Fri, 8 Oct 2021 03:44:28 +0530 Message-Id: <20211007221432.1029249-5-siddhesh@gotplt.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20211007221432.1029249-1-siddhesh@gotplt.org> References: <20211007221432.1029249-1-siddhesh@gotplt.org> MIME-Version: 1.0 X-Spam-Status: No, score=-3039.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: jakub@redhat.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This is the beginnings of support for ADDR_EXPR objects and is partly based on the implementation in tree-object-size, splitting out functions for readability. One key difference from constant-size ADDR_EXPR computation is the computation of residual sizes based on offset. This pass attempts to compute an expression with guards to try and not overflow. This is however still rudimentary and a subsequent patch for subobject support makes it more comprehensive by handling negative offsets as well. The size expressions based on offsets may look arbitrarily complex but in practice most parts of the expression tend to fold away due to being constants. Despite that it is still a potential bottleneck and may need some artifical backstop (such as bailing out on computation if the size expression nests more than an arbitrarily chosen N levels) to reduce compile time as well as avoid adding too much of a performance overhead to generated code. gcc/ChangeLog: * builtins.c (fold_builtin_dyn_object_size): Handle ADDR_EXPR. * tree-dynamic-object-size.c (compute_object_offset, size_for_offset, get_whole_var, whole_var_size, addr_dyn_object_size): New functions. (compute_builtin_dyn_object_size): Handle ADDR_EXPR. (expr_object_size): New function. (collect_object_sizes_for): Use it. gcc/testsuite/ChangeLog: * gcc.dg/builtin-dynamic-object-size-0.c (test_builtin_malloc_condphi4, test_builtin_malloc_condphi5, test_passthrough_nonssa): New tests. (main): Call them. Signed-off-by: Siddhesh Poyarekar --- gcc/builtins.c | 2 +- .../gcc.dg/builtin-dynamic-object-size-0.c | 37 +++ gcc/tree-dynamic-object-size.c | 255 +++++++++++++++++- 3 files changed, 287 insertions(+), 7 deletions(-) diff --git a/gcc/builtins.c b/gcc/builtins.c index d015029765b..c1e23324552 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -10339,7 +10339,7 @@ fold_builtin_dyn_object_size (tree ptr, tree ost) /* 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 + if ((TREE_CODE (ptr) == SSA_NAME || TREE_CODE (ptr) == ADDR_EXPR) && compute_builtin_dyn_object_size (ptr, object_size_type, &bytes)) return bytes; 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 7098ef485c6..22c86190341 100644 --- a/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c +++ b/gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c @@ -105,6 +105,25 @@ test_builtin_malloc_condphi3 (int cond, size_t in, size_t in2) return __builtin_dynamic_object_size (ret, 0); } +size_t +__attribute__ ((noinline)) +test_builtin_malloc_condphi4 (size_t sz, int cond) +{ + char *a = __builtin_malloc (sz); + char b[sz / 2]; + + return __builtin_dynamic_object_size (cond ? b : (void *) &a, 0); +} + +size_t +__attribute__ ((noinline)) +test_builtin_malloc_condphi5 (size_t sz, int cond, char *c) +{ + char *a = __builtin_malloc (sz); + + return __builtin_dynamic_object_size (cond ? c : (void *) &a, 0); +} + /* Calloc-like allocator. */ size_t @@ -158,6 +177,16 @@ test_passthrough (size_t sz, char *in) return __builtin_dynamic_object_size (dest, 0); } +size_t +__attribute__ ((noinline)) +test_passthrough_nonssa (char *in) +{ + char bin[__builtin_strlen (in) + 1]; + char *dest = __builtin_memcpy (bin, in, __builtin_strlen (in) + 1); + + return __builtin_dynamic_object_size (dest, 0); +} + /* Variable length arrays. */ size_t __attribute__ ((noinline)) @@ -223,6 +252,12 @@ main (int argc, char **argv) FAIL (); if (test_builtin_malloc_condphi3 (0, 128, 256) != 256) FAIL (); + if (test_builtin_malloc_condphi4 (128, 1) != 64) + FAIL (); + if (test_builtin_malloc_condphi4 (128, 0) != sizeof (void *)) + FAIL (); + if (test_builtin_malloc_condphi5 (128, 0, argv[0]) != -1) + FAIL (); if (test_calloc (2048, 4) != 2048 * 4) FAIL (); if (test_builtin_calloc (2048, 8) != 2048 * 8) @@ -240,6 +275,8 @@ main (int argc, char **argv) if (test_passthrough (__builtin_strlen (argv[0]) + 1, argv[0]) != __builtin_strlen (argv[0]) + 1) FAIL (); + if (test_passthrough_nonssa (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) diff --git a/gcc/tree-dynamic-object-size.c b/gcc/tree-dynamic-object-size.c index 483d6782d49..6cc63abd010 100644 --- a/gcc/tree-dynamic-object-size.c +++ b/gcc/tree-dynamic-object-size.c @@ -93,6 +93,212 @@ static vecobject_size_exprs[4]; /* Bitmaps what object sizes have been computed already. */ static bitmap computed[4]; +bool compute_builtin_dyn_object_size (tree, int, tree *, + struct function *fun = NULL); + +/* Compute offset of EXPR within VAR. Return error_mark_node if unknown. */ + +static tree +compute_object_offset (const_tree expr, const_tree var) +{ + enum tree_code code = PLUS_EXPR; + tree base, off, t; + + if (expr == var) + return size_zero_node; + + switch (TREE_CODE (expr)) + { + case COMPONENT_REF: + base = compute_object_offset (TREE_OPERAND (expr, 0), var); + if (base == error_mark_node) + return base; + + t = TREE_OPERAND (expr, 1); + off = fold_build2 (PLUS_EXPR, sizetype, DECL_FIELD_OFFSET (t), + size_int (tree_to_uhwi (DECL_FIELD_BIT_OFFSET (t)) + / BITS_PER_UNIT)); + break; + + case REALPART_EXPR: + CASE_CONVERT: + case VIEW_CONVERT_EXPR: + case NON_LVALUE_EXPR: + return compute_object_offset (TREE_OPERAND (expr, 0), var); + + case IMAGPART_EXPR: + base = compute_object_offset (TREE_OPERAND (expr, 0), var); + if (base == error_mark_node) + return base; + + off = TYPE_SIZE_UNIT (TREE_TYPE (expr)); + break; + + case ARRAY_REF: + base = compute_object_offset (TREE_OPERAND (expr, 0), var); + if (base == error_mark_node) + return base; + + t = TREE_OPERAND (expr, 1); + tree low_bound, unit_size; + low_bound = array_ref_low_bound (CONST_CAST_TREE (expr)); + unit_size = array_ref_element_size (CONST_CAST_TREE (expr)); + if (! integer_zerop (low_bound)) + t = fold_build2 (MINUS_EXPR, TREE_TYPE (t), t, low_bound); + if (TREE_CODE (t) == INTEGER_CST && tree_int_cst_sgn (t) < 0) + { + code = MINUS_EXPR; + t = fold_build1 (NEGATE_EXPR, TREE_TYPE (t), t); + } + t = fold_convert (sizetype, t); + off = fold_build2 (MULT_EXPR, sizetype, unit_size, t); + break; + + case MEM_REF: + gcc_assert (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR); + return wide_int_to_tree (sizetype, mem_ref_offset (expr)); + + default: + return error_mark_node; + } + + return fold_build2 (code, sizetype, base, off); +} + +/* Given an object size SZ and offset OFF into it, compute the usable object + size. The expression returns 0 for all offsets that invoke undefined + behaviour. */ + +static tree +size_for_offset (tree sz, tree off) +{ + /* A MEM_REF offset may be a pointer, where we need to figure out the + multiplier based on the base type. */ + if (POINTER_TYPE_P (TREE_TYPE (off))) + { + tree typesize = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (off))); + + if (typesize) + { + /* SZ < TYPESIZE ? SZ : TYPESIZE * MIN (SZ / TYPESIZE, OFF) */ + tree cond = fold_build2 (LT_EXPR, sizetype, sz, typesize); + + tree tmp = fold_build2 (EXACT_DIV_EXPR, sizetype, sz, typesize); + tmp = fold_build2 (MIN_EXPR, sizetype, tmp, off); + tmp = fold_build2 (MULT_EXPR, sizetype, tmp, typesize); + + off = fold_build3 (COND_EXPR, sizetype, cond, sz, tmp); + + return fold_build2 (MINUS_EXPR, sizetype, sz, off); + } + else + off = fold_convert (sizetype, off); + } + + off = fold_build2 (MIN_EXPR, sizetype, sz, off); + return fold_build2 (MINUS_EXPR, sizetype, sz, off); +} + +/* Peek through ADDR_EXPR operands to get the definition of the whole variable + PTR points in. Write the result expression into PT_VARP and its size into + PT_VAR_SIZEP. Return true if the object is found. */ + +static tree +get_whole_var (const_tree ptr) +{ + tree pt_var; + + pt_var = TREE_OPERAND (ptr, 0); + while (handled_component_p (pt_var)) + pt_var = TREE_OPERAND (pt_var, 0); + + return pt_var; +} + +static bool +whole_var_size (struct object_size_info *osi, tree pt_var, + int object_size_type, tree *pt_var_sizep) +{ + tree pt_var_size = NULL_TREE; + int subobject = object_size_type & 1; + int min = object_size_type & 2; + + if (TREE_CODE (pt_var) == MEM_REF) + { + tree var = TREE_OPERAND (pt_var, 0); + if (!osi || subobject || TREE_CODE (var) != SSA_NAME) + compute_builtin_dyn_object_size (var, min, &pt_var_size); + else + { + collect_object_sizes_for (osi, var); + pt_var_size = object_sizes[object_size_type][SSA_NAME_VERSION (var)]; + } + + if (pt_var_size != NULL_TREE) + { + tree offset = wide_int_to_tree (size_type_node, + mem_ref_offset (pt_var)); + + pt_var_size = size_for_offset (pt_var_size, offset); + } + } + else if (DECL_P (pt_var)) + { + pt_var_size = decl_init_size (pt_var, min); + if (!pt_var_size) + return false; + } + else if (TREE_CODE (pt_var) == STRING_CST) + pt_var_size = TYPE_SIZE_UNIT (TREE_TYPE (pt_var)); + else + return false; + + *pt_var_sizep = pt_var_size; + return true; +} + +/* Compute an object size estimate for PTR, which is a ADDR_EXPR. + OBJECT_SIZE_TYPE is the second argument from __builtin_dynamic_object_size. + If unknown, return false, setting PSIZE to NULL_TREE. */ + +static bool +addr_dyn_object_size (struct object_size_info *osi, const_tree ptr, + int object_size_type, tree *psize) +{ + tree pt_var, pt_var_size = NULL_TREE, bytes; + + gcc_assert (TREE_CODE (ptr) == ADDR_EXPR); + + /* Set to unknown and overwrite just before returning if the size + could be determined. */ + *psize = NULL_TREE; + + pt_var = get_whole_var (ptr); + + if (!pt_var) + return false; + + if (!whole_var_size (osi, pt_var, object_size_type, &pt_var_size)) + return false; + + if (!pt_var_size) + return false; + + /* PTR points to a subobject of whole variable PT_VAR. */ + if (pt_var != TREE_OPERAND (ptr, 0)) + { + bytes = compute_object_offset (TREE_OPERAND (ptr, 0), pt_var); + if (bytes != error_mark_node) + bytes = size_for_offset (pt_var_size, bytes); + } + else + bytes = pt_var_size; + + *psize = bytes == error_mark_node ? NULL_TREE : bytes; + return true; +} + + /* 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. @@ -299,6 +505,13 @@ compute_builtin_dyn_object_size (tree ptr, int object_size_type, tree *psize, could be determined. */ *psize = NULL_TREE; + if (TREE_CODE (ptr) == ADDR_EXPR) + /* We assume that the caller will gimplify the expression. If the + expression depends on any SSA objects, its size expression is gimplified + and returned, so the expression will definitely not depend on the cached + objects. */ + return addr_dyn_object_size (NULL, ptr, object_size_type, psize); + if (TREE_CODE (ptr) != SSA_NAME || !POINTER_TYPE_P (TREE_TYPE (ptr))) return false; @@ -359,6 +572,27 @@ out: return *psize != NULL_TREE; } +/* Compute object_sizes an object defined to VALUE, which is not an + SSA_NAME. */ + +static void +expr_object_size (struct object_size_info *osi, tree value, tree *sz) +{ + int object_size_type = osi->object_size_type; + tree bytes = NULL_TREE; + + if (TREE_CODE (value) == WITH_SIZE_EXPR) + value = TREE_OPERAND (value, 0); + + if (TREE_CODE (value) == ADDR_EXPR) + addr_dyn_object_size (osi, value, object_size_type, &bytes); + + if (bytes) + STRIP_NOPS (bytes); + + *sz = bytes; +} + static void maybe_update_dependency_loop (struct object_size_info *osi, unsigned name, tree sz) @@ -506,6 +740,12 @@ collect_object_sizes_for (struct object_size_info *osi, tree var) { if (TREE_CODE (arg) == SSA_NAME) set_object_size_ssa (osi, var, arg); + else + { + tree ret; + expr_object_size (osi, arg, &ret); + cache_object_size_copy (osi, varno, ret); + } } else call_object_size (osi, var, call_stmt); @@ -517,17 +757,20 @@ collect_object_sizes_for (struct object_size_info *osi, tree var) 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. */ + /* Bail out if the size of any of the PHI arguments cannot be + determined. */ for (i = 0; i < gimple_phi_num_args (stmt); i++) { tree rhs = gimple_phi_arg_def (stmt, i); + tree sz; if (TREE_CODE (rhs) != SSA_NAME) - break; - - collect_object_sizes_for (osi, rhs); - tree sz = object_sizes[object_size_type][SSA_NAME_VERSION (rhs)]; + expr_object_size (osi, rhs, &sz); + else + { + collect_object_sizes_for (osi, rhs); + sz = object_sizes[object_size_type][SSA_NAME_VERSION (rhs)]; + } if (sz == NULL_TREE) break;