From patchwork Mon Nov 15 22:05:49 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Sebor X-Patchwork-Id: 47729 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2EA30385842E for ; Mon, 15 Nov 2021 22:06:22 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2EA30385842E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1637013982; bh=5yu/qDymJRlhsORyM/Xro+QjOTvrNx65FQRoOE+tPQQ=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=YhseZtSlhu1FNytGHmueMAjzrt9V3IXME7eGfPQYiNr08Ji2I+XTeAd9UGSzXxm3h 3T7OVqnKJNfrZShS4NCXdm2FcVmfnXIgXjbkrhzQqTcg2PT+NG0w/X5x1CCJ80zHPU XSzlIqCSAkIYU1pZktO06qy4erJXZ1YbZut/XjQc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pg1-x52e.google.com (mail-pg1-x52e.google.com [IPv6:2607:f8b0:4864:20::52e]) by sourceware.org (Postfix) with ESMTPS id 9BE1E3858405 for ; Mon, 15 Nov 2021 22:05:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9BE1E3858405 Received: by mail-pg1-x52e.google.com with SMTP id h63so8879530pgc.12 for ; Mon, 15 Nov 2021 14:05:51 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:from:subject:message-id:date:user-agent :mime-version:content-language; bh=5yu/qDymJRlhsORyM/Xro+QjOTvrNx65FQRoOE+tPQQ=; b=qjRuTV2KV6O5YO9Te+OcP+T+PgooKMTxi3YUUkdr+3rsRqHSguDGh3Q/+0Wae9W0SL I4JlQcKaPtOjT7THiZhD4yHXZ3U1w4AQ5bdUFgRR/QBe9YcaPlCWzbPgbfuael4synwb EeHwF/7/uWyn4WsFG9cUaflyXYgrgFsmdqpK/5WR37eeZYyz1I93oZTidwyxIo9ZeqKt hY0+gQzzN0teLU1QOEW4IwF8ayOt1pvj6CTLxU1wx5EATsaaKychdPVJfvuH+1u4mRGS 4bi5wQOXw46yn79wRzKd3EIP+YaRQ3plIOCBthjvijjdqGRBYPSEU1w3hEHBQPyjPSI3 F2GQ== X-Gm-Message-State: AOAM530JBXDLeZqoPPtimwMIMs3hkInuUEUJR3of/02suiioUxdZ2eki p65CoKELZh8h3Apf8hpafku0EqHINY0= X-Google-Smtp-Source: ABdhPJzfTCBLYUGNKaFt9dngRCKWQtbo+sqDs/PMyNG8Hh55Ye9HtjpVfoStXNv2gJYY/ji6WInpSQ== X-Received: by 2002:aa7:93aa:0:b0:4a2:bf77:b42f with SMTP id x10-20020aa793aa000000b004a2bf77b42fmr10782826pff.47.1637013950428; Mon, 15 Nov 2021 14:05:50 -0800 (PST) Received: from [192.168.0.41] (184-96-250-76.hlrn.qwest.net. [184.96.250.76]) by smtp.gmail.com with ESMTPSA id k13sm17364380pfc.197.2021.11.15.14.05.49 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 15 Nov 2021 14:05:50 -0800 (PST) To: gcc-patches Subject: [PATCH] simplify get_range_strlen interface Message-ID: <72f82121-dbd8-f457-06f3-19e4c5c9bf4f@gmail.com> Date: Mon, 15 Nov 2021 15:05:49 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 MIME-Version: 1.0 Content-Language: en-US X-Spam-Status: No, score=-10.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, 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: , X-Patchwork-Original-From: Martin Sebor via Gcc-patches From: Martin Sebor Reply-To: Martin Sebor Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" The deeply nested PHI handling in get_range_strlen_dynamic makes the code bigger and harder to follow than it would be if done in its own function. The attached patch does that. In addition, the get_range_strlen family of functions use a bitmap to avoid infinite recursion. Rather than dynamically allocating and freeing it on demand the attached patch simplifies the code by using an instance of auto_bitmap. This avoids the risk of neglecting to deallocate the bitmap. Tested on x86_64-linux. Martin Slightly simplify get_range_strlen interface. gcc/ChangeLog: * gimple-fold.c (get_range_strlen): Take bitmap as an argument rather than a pointer to it. (get_range_strlen_tree): Same. Remove bitmap allocation. Use an auto_bitmap. (get_maxval_strlen): Use an auto_bitmap. * tree-ssa-strlen.c (get_range_strlen_dynamic): Factor out PHI handling... (get_range_strlen_phi): ...into this function. (printf_strlen_execute): Dump pointer query cache contents when details are requisted. diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c index 6e25a7c05db..87c211c5e3f 100644 --- a/gcc/gimple-fold.c +++ b/gcc/gimple-fold.c @@ -86,7 +86,7 @@ enum strlen_range_kind { }; static bool -get_range_strlen (tree, bitmap *, strlen_range_kind, c_strlen_data *, unsigned); +get_range_strlen (tree, bitmap, strlen_range_kind, c_strlen_data *, unsigned); /* Return true when DECL can be referenced from current unit. FROM_DECL (if non-null) specify constructor of variable DECL was taken from. @@ -1525,7 +1525,7 @@ gimple_fold_builtin_memset (gimple_stmt_iterator *gsi, tree c, tree len) /* Helper of get_range_strlen for ARG that is not an SSA_NAME. */ static bool -get_range_strlen_tree (tree arg, bitmap *visited, strlen_range_kind rkind, +get_range_strlen_tree (tree arg, bitmap visited, strlen_range_kind rkind, c_strlen_data *pdata, unsigned eltsize) { gcc_assert (TREE_CODE (arg) != SSA_NAME); @@ -1849,7 +1849,7 @@ get_range_strlen_tree (tree arg, bitmap *visited, strlen_range_kind rkind, Return true if *PDATA was successfully populated and false otherwise. */ static bool -get_range_strlen (tree arg, bitmap *visited, +get_range_strlen (tree arg, bitmap visited, strlen_range_kind rkind, c_strlen_data *pdata, unsigned eltsize) { @@ -1863,9 +1863,7 @@ get_range_strlen (tree arg, bitmap *visited, return false; /* If we were already here, break the infinite cycle. */ - if (!*visited) - *visited = BITMAP_ALLOC (NULL); - if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (arg))) + if (!bitmap_set_bit (visited, SSA_NAME_VERSION (arg))) return true; tree var = arg; @@ -1962,10 +1960,10 @@ get_range_strlen (tree arg, bitmap *visited, bool get_range_strlen (tree arg, c_strlen_data *pdata, unsigned eltsize) { - bitmap visited = NULL; + auto_bitmap visited; tree maxbound = pdata->maxbound; - if (!get_range_strlen (arg, &visited, SRK_LENRANGE, pdata, eltsize)) + if (!get_range_strlen (arg, visited, SRK_LENRANGE, pdata, eltsize)) { /* On failure extend the length range to an impossible maximum (a valid MAXLEN must be less than PTRDIFF_MAX - 1). Other @@ -1981,9 +1979,6 @@ get_range_strlen (tree arg, c_strlen_data *pdata, unsigned eltsize) if (maxbound && pdata->maxbound == maxbound) pdata->maxbound = build_all_ones_cst (size_type_node); - if (visited) - BITMAP_FREE (visited); - return !integer_all_onesp (pdata->maxlen); } @@ -2005,19 +2000,16 @@ get_maxval_strlen (tree arg, strlen_range_kind rkind, tree *nonstr = NULL) /* ARG must have an integral type when RKIND says so. */ gcc_assert (rkind != SRK_INT_VALUE || INTEGRAL_TYPE_P (TREE_TYPE (arg))); - bitmap visited = NULL; + auto_bitmap visited; /* Reset DATA.MAXLEN if the call fails or when DATA.MAXLEN is unbounded. */ c_strlen_data lendata = { }; - if (!get_range_strlen (arg, &visited, rkind, &lendata, /* eltsize = */1)) + if (!get_range_strlen (arg, visited, rkind, &lendata, /* eltsize = */1)) lendata.maxlen = NULL_TREE; else if (lendata.maxlen && integer_all_onesp (lendata.maxlen)) lendata.maxlen = NULL_TREE; - if (visited) - BITMAP_FREE (visited); - if (nonstr) { /* For callers prepared to handle unterminated arrays set diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index c0ec7d20a60..536f796f82b 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -193,6 +193,8 @@ struct laststmt_struct } laststmt; static int get_stridx_plus_constant (strinfo *, unsigned HOST_WIDE_INT, tree); +static bool get_range_strlen_dynamic (tree, gimple *s, c_strlen_data *, + bitmap, range_query *, unsigned *); /* Sets MINMAX to either the constant value or the range VAL is in and returns either the constant value or VAL on success or null @@ -1087,6 +1089,76 @@ dump_strlen_info (FILE *fp, gimple *stmt, range_query *rvals) } } +/* Helper of get_range_strlen_dynamic(). See below. */ + +static bool +get_range_strlen_phi (tree src, gphi *phi, + c_strlen_data *pdata, bitmap visited, + range_query *rvals, unsigned *pssa_def_max) +{ + if (!bitmap_set_bit (visited, SSA_NAME_VERSION (src))) + return true; + + if (*pssa_def_max == 0) + return false; + + --*pssa_def_max; + + /* Iterate over the PHI arguments and determine the minimum and maximum + length/size of each and incorporate them into the overall result. */ + for (unsigned i = 0; i != gimple_phi_num_args (phi); ++i) + { + tree arg = gimple_phi_arg_def (phi, i); + if (arg == gimple_phi_result (phi)) + continue; + + c_strlen_data argdata = { }; + if (!get_range_strlen_dynamic (arg, phi, &argdata, visited, rvals, + pssa_def_max)) + { + pdata->maxlen = build_all_ones_cst (size_type_node); + continue; + } + + /* Set the DECL of an unterminated array this argument refers to + if one hasn't been found yet. */ + if (!pdata->decl && argdata.decl) + pdata->decl = argdata.decl; + + if (!argdata.minlen + || (integer_zerop (argdata.minlen) + && (!argdata.maxbound + || integer_all_onesp (argdata.maxbound)) + && integer_all_onesp (argdata.maxlen))) + { + /* Set the upper bound of the length to unbounded. */ + pdata->maxlen = build_all_ones_cst (size_type_node); + continue; + } + + /* Adjust the minimum and maximum length determined so far and + the upper bound on the array size. */ + if (!pdata->minlen + || tree_int_cst_lt (argdata.minlen, pdata->minlen)) + pdata->minlen = argdata.minlen; + + if (!pdata->maxlen + || (argdata.maxlen + && TREE_CODE (argdata.maxlen) == INTEGER_CST + && tree_int_cst_lt (pdata->maxlen, argdata.maxlen))) + pdata->maxlen = argdata.maxlen; + + if (!pdata->maxbound + || TREE_CODE (pdata->maxbound) != INTEGER_CST + || (argdata.maxbound + && tree_int_cst_lt (pdata->maxbound, argdata.maxbound) + && !integer_all_onesp (argdata.maxbound))) + pdata->maxbound = argdata.maxbound; + } + + return true; +} + /* Attempt to determine the length of the string SRC. On success, store the length in *PDATA and return true. Otherwise, return false. VISITED is a bitmap of visited PHI nodes. RVALS points to the valuation @@ -1095,7 +1167,7 @@ dump_strlen_info (FILE *fp, gimple *stmt, range_query *rvals) static bool get_range_strlen_dynamic (tree src, gimple *stmt, - c_strlen_data *pdata, bitmap *visited, + c_strlen_data *pdata, bitmap visited, range_query *rvals, unsigned *pssa_def_max) { int idx = get_stridx (src, stmt); @@ -1104,72 +1176,9 @@ get_range_strlen_dynamic (tree src, gimple *stmt, if (TREE_CODE (src) == SSA_NAME) { gimple *def_stmt = SSA_NAME_DEF_STMT (src); - if (gimple_code (def_stmt) == GIMPLE_PHI) - { - if (!*visited) - *visited = BITMAP_ALLOC (NULL); - - if (!bitmap_set_bit (*visited, SSA_NAME_VERSION (src))) - return true; - - if (*pssa_def_max == 0) - return false; - - --*pssa_def_max; - - /* Iterate over the PHI arguments and determine the minimum - and maximum length/size of each and incorporate them into - the overall result. */ - gphi *phi = as_a (def_stmt); - for (unsigned i = 0; i != gimple_phi_num_args (phi); ++i) - { - tree arg = gimple_phi_arg_def (phi, i); - if (arg == gimple_phi_result (def_stmt)) - continue; - - c_strlen_data argdata = { }; - if (get_range_strlen_dynamic (arg, phi, &argdata, visited, - rvals, pssa_def_max)) - { - /* Set the DECL of an unterminated array this argument - refers to if one hasn't been found yet. */ - if (!pdata->decl && argdata.decl) - pdata->decl = argdata.decl; - - if (!argdata.minlen - || (integer_zerop (argdata.minlen) - && (!argdata.maxbound - || integer_all_onesp (argdata.maxbound)) - && integer_all_onesp (argdata.maxlen))) - { - /* Set the upper bound of the length to unbounded. */ - pdata->maxlen = build_all_ones_cst (size_type_node); - continue; - } - - /* Adjust the minimum and maximum length determined - so far and the upper bound on the array size. */ - if (!pdata->minlen - || tree_int_cst_lt (argdata.minlen, pdata->minlen)) - pdata->minlen = argdata.minlen; - if (!pdata->maxlen - || (argdata.maxlen - && tree_int_cst_lt (pdata->maxlen, argdata.maxlen))) - pdata->maxlen = argdata.maxlen; - if (!pdata->maxbound - || TREE_CODE (pdata->maxbound) != INTEGER_CST - || (argdata.maxbound - && tree_int_cst_lt (pdata->maxbound, - argdata.maxbound) - && !integer_all_onesp (argdata.maxbound))) - pdata->maxbound = argdata.maxbound; - } - else - pdata->maxlen = build_all_ones_cst (size_type_node); - } - - return true; - } + if (gphi *phi = dyn_cast(def_stmt)) + return get_range_strlen_phi (src, phi, pdata, visited, rvals, + pssa_def_max); } /* Return success regardless of the result and handle *PDATA @@ -1286,11 +1295,11 @@ void get_range_strlen_dynamic (tree src, gimple *stmt, c_strlen_data *pdata, range_query *rvals) { - bitmap visited = NULL; + auto_bitmap visited; tree maxbound = pdata->maxbound; unsigned limit = param_ssa_name_def_chain_limit; - if (!get_range_strlen_dynamic (src, stmt, pdata, &visited, rvals, &limit)) + if (!get_range_strlen_dynamic (src, stmt, pdata, visited, rvals, &limit)) { /* On failure extend the length range to an impossible maximum (a valid MAXLEN must be less than PTRDIFF_MAX - 1). Other @@ -1305,9 +1314,6 @@ get_range_strlen_dynamic (tree src, gimple *stmt, c_strlen_data *pdata, MAXBOUND to SIZE_MAX. Otherwise leave it null (if it is null). */ if (maxbound && pdata->maxbound == maxbound) pdata->maxbound = build_all_ones_cst (size_type_node); - - if (visited) - BITMAP_FREE (visited); } /* Invalidate string length information for strings whose length might @@ -5831,7 +5837,7 @@ printf_strlen_execute (function *fun, bool warn_only) walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun)); if (dump_file && (dump_flags & TDF_DETAILS)) - walker.ptr_qry.dump (dump_file); + walker.ptr_qry.dump (dump_file, true); ssa_ver_to_stridx.release (); strinfo_pool.release ();