From patchwork Mon Jan 24 22:55:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Sebor X-Patchwork-Id: 50420 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 6233D3858024 for ; Mon, 24 Jan 2022 22:56:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6233D3858024 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1643064964; bh=HmdJTuWokjhkiJp2umDZ4qCAV9jPQRPqqLR1Ga6CCHU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=FJBJHMeDQGjv+mVGv8kjX+aQjVUaw4oylNyyUpdC79Yw/MmNcXCAg+LhVZxdiW2LM JIV1HdjuCRM5k5xBWyOPH4Fw85+iFH7Ktm1ly7J0e5bRv6JcqDcyoXgfopvm8Qqh5G laVtU6Iet9Q2b5hc/6RfC/tjerOu3PIl4+FK3vU0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-io1-xd30.google.com (mail-io1-xd30.google.com [IPv6:2607:f8b0:4864:20::d30]) by sourceware.org (Postfix) with ESMTPS id A699B3858D3C for ; Mon, 24 Jan 2022 22:55:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A699B3858D3C Received: by mail-io1-xd30.google.com with SMTP id z199so7006377iof.10 for ; Mon, 24 Jan 2022 14:55:35 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent :content-language:to:from:subject; bh=HmdJTuWokjhkiJp2umDZ4qCAV9jPQRPqqLR1Ga6CCHU=; b=r/c5ZEebzzLJxgoCjsI73ePeI5WzPSVWYFhq1RZj76D5Ke/gZ4evNnDjuYB+wIn7OW Z6uISAHyuce8XSW+LnvOnLA/vVBm06axaDT0RPPchjTN9SP0JpUzTcwmUsabnsUU8sbV 7PjwqCdCR14NtyjmVZZaEIYZr1Edd0kH9yyQxsxSYmmNxVjtC6bJmWhQ6xtY4AS4nQtz Pgmswjaea5c2+vTSRmys6c/tbeozd+vErN8iBu/vdyjcXGzoDitSOVZ3E6l0QgFBZs6b uNMhu7AnPIPhCOTYFoqOvJp3eLxHvZ63h+TKc5rJOTUL662N867ghklbC6kFMPHxVRk0 E8bA== X-Gm-Message-State: AOAM530ceYwftJ5v4RHK0AZUX+Xea5oZAf/SYsDNS+lDfm5CZW9Ydi68 VYd+Wf23afFsanI6oNp7iblshiLSyUg= X-Google-Smtp-Source: ABdhPJz2vumDVWC2NAR3JdOHApOS4TVKn3b54H9ZN88ySml4f57p3UTKG7ON0ByT2us7Uyc3invPvA== X-Received: by 2002:a05:6638:ec7:: with SMTP id q7mr8514562jas.210.1643064934838; Mon, 24 Jan 2022 14:55:34 -0800 (PST) Received: from [192.168.0.41] (97-118-100-142.hlrn.qwest.net. [97.118.100.142]) by smtp.gmail.com with ESMTPSA id w19sm7402549iov.16.2022.01.24.14.55.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 24 Jan 2022 14:55:33 -0800 (PST) Message-ID: Date: Mon, 24 Jan 2022 15:55:32 -0700 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.0 Content-Language: en-US To: gcc-patches , Richard Biener Subject: [PATCH] avoid recomputing PHI results after failure (PR 104203) X-Spam-Status: No, score=-10.1 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 pointer_query algorithm fails when it's unable to determine the provenance of an pointer SSA variable. A failure prevents it from making a record of the variable in the cache. Although this doesn't happen often, one common cause of failures is PHI nodes: e.g., because one of its arguments references the PHI itself, or an undefined variable. Because a failed SSA_NAME isn't added to the cache, the computation that led up to its failure is repeated on each interesting use of the variable. This is computationally wasteful and can cause excessive CPU usage in pathological cases like in the test case in PR 104203. To avoid the problem the attached patch changes the logic for PHI arguments and nodes to cache the most conservative result on such a failure. It treats such a pointer as pointing into the middle of an object of maximum size (same as under some other conditions). In addition, the patch also adds a new timer variable to the warn_access pass to make these problems easier in the future to track down. There are a number of other conditions under which point_query fails. Even though the same approach could be used to replace all those, I did not make the change in this patch. Tested on x86_64-linux. Martin PS This solution relies on the pointer_query instance having caching enabled. Two warning passes run without a cache: -Warray-bounds in VRP and -Wrestrict in the wrestrict pass. I can look into enabling it for GCC 12 if there's concern that they might be impacted. PR tree-optimization/104203 - huge compile-time regression in pointer_query gcc/ChangeLog: PR tree-optimization/104203 * gimple-ssa-warn-access.cc (pass_data pass_data_waccess): Use TV_WARN_ACCESS. * pointer-query.cc (access_ref::merge_ref): Change return type. Convert failure to a conservative success. (access_ref::get_ref): Adjust to the change above. Short-circuit PHI evaluation after first failure turned into conservative success. * pointer-query.h (access_ref::merge_ref): Change return type. * timevar.def (TV_WARN_ACCESS): New timer variable. diff --git a/gcc/pointer-query.cc b/gcc/pointer-query.cc index a61ac8968f5..b092ef4fbdc 100644 --- a/gcc/pointer-query.cc +++ b/gcc/pointer-query.cc @@ -629,7 +629,7 @@ access_ref::phi () const ARG refers to the null pointer. Return true on success and false on failure. */ -bool +void access_ref::merge_ref (vec *all_refs, tree arg, gimple *stmt, int ostype, bool skip_null, ssa_name_limit_t &snlim, pointer_query &qry) @@ -637,8 +637,16 @@ access_ref::merge_ref (vec *all_refs, tree arg, gimple *stmt, access_ref aref; if (!compute_objsize_r (arg, stmt, false, ostype, &aref, snlim, &qry) || aref.sizrng[0] < 0) - /* This may be a PHI with all null pointer arguments. */ - return false; + { + /* This may be a PHI with all null pointer arguments. Handle it + conservatively by setting all properties to the most permissive + values. */ + base0 = false; + offrng[0] = offrng[1] = 0; + add_max_offset (); + set_max_size_range (); + return; + } if (all_refs) { @@ -675,13 +683,13 @@ access_ref::merge_ref (vec *all_refs, tree arg, gimple *stmt, if (arg_known_size) sizrng[0] = aref.sizrng[0]; - return true; + return; } /* Disregard null pointers in PHIs with two or more arguments. TODO: Handle this better! */ if (nullp) - return true; + return; const bool known_size = (sizrng[0] != 0 || sizrng[1] != maxobjsize); @@ -717,7 +725,7 @@ access_ref::merge_ref (vec *all_refs, tree arg, gimple *stmt, sizrng[0] = minsize; parmarray = merged_parmarray; - return true; + return; } /* Determine and return the largest object to which *THIS refers. If @@ -755,14 +763,12 @@ access_ref::get_ref (vec *all_refs, access_ref aref; tree arg1 = gimple_assign_rhs1 (def_stmt); - if (!aref.merge_ref (all_refs, arg1, def_stmt, ostype, false, - *psnlim, *qry)) - return NULL_TREE; + aref.merge_ref (all_refs, arg1, def_stmt, ostype, false, + *psnlim, *qry); tree arg2 = gimple_assign_rhs2 (def_stmt); - if (!aref.merge_ref (all_refs, arg2, def_stmt, ostype, false, - *psnlim, *qry)) - return NULL_TREE; + aref.merge_ref (all_refs, arg2, def_stmt, ostype, false, + *psnlim, *qry); if (pref && pref != this) { @@ -801,16 +807,24 @@ access_ref::get_ref (vec *all_refs, phi_ref = *pref; } + const offset_int maxobjsize = wi::to_offset (max_object_size ()); const unsigned nargs = gimple_phi_num_args (phi_stmt); for (unsigned i = 0; i < nargs; ++i) { access_ref phi_arg_ref; bool skip_null = i || i + 1 < nargs; tree arg = gimple_phi_arg_def (phi_stmt, i); - if (!phi_ref.merge_ref (all_refs, arg, phi_stmt, ostype, skip_null, - *psnlim, *qry)) - return NULL_TREE; + phi_ref.merge_ref (all_refs, arg, phi_stmt, ostype, skip_null, + *psnlim, *qry); + + if (!phi_ref.base0 + && phi_ref.sizrng[0] == 0 + && phi_ref.sizrng[1] >= maxobjsize) + /* When an argument results in the most permissive result, + the remaining arguments cannot constrain it. Short-circuit + the evaluation. */ + break; } if (phi_ref.sizrng[0] < 0) /* A helper of compute_objsize_r() to determine the size from an assignment diff --git a/gcc/pointer-query.h b/gcc/pointer-query.h index 7dc965bd150..dbdcd593b79 100644 --- a/gcc/pointer-query.h +++ b/gcc/pointer-query.h @@ -67,7 +67,7 @@ struct access_ref gphi *phi () const; /* Merge the result for a pointer with *THIS. */ - bool merge_ref (vec *all_refs, tree, gimple *, int, bool, + void merge_ref (vec *all_refs, tree, gimple *, int, bool, ssa_name_limit_t &, pointer_query &); /* Return the object to which REF refers. */ diff --git a/gcc/timevar.def b/gcc/timevar.def index c239e8e4592..2dae5e1c760 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -307,6 +307,7 @@ DEFTIMEVAR (TV_TREE_UBSAN , "tree ubsan") DEFTIMEVAR (TV_INITIALIZE_RTL , "initialize rtl") DEFTIMEVAR (TV_GIMPLE_LADDRESS , "address lowering") DEFTIMEVAR (TV_TREE_LOOP_IFCVT , "tree loop if-conversion") +DEFTIMEVAR (TV_WARN_ACCESS , "access analysis") /* Everything else in rest_of_compilation not included above. */ DEFTIMEVAR (TV_EARLY_LOCAL , "early local passes") diff --git a/gcc/gimple-ssa-warn-access.cc b/gcc/gimple-ssa-warn-access.cc index 8bc33eeb6fa..afcf0f71bec 100644 --- a/gcc/gimple-ssa-warn-access.cc +++ b/gcc/gimple-ssa-warn-access.cc @@ -2053,7 +2053,7 @@ const pass_data pass_data_waccess = { GIMPLE_PASS, "waccess", OPTGROUP_NONE, - TV_NONE, + TV_WARN_ACCESS, /* timer variable */ PROP_cfg, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */