From patchwork Mon Jan 17 19:55:21 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1580946 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=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=qFOff/eo; 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 4Jd2hS4GRGz9sRR for ; Tue, 18 Jan 2022 06:55:51 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0CE8E385802E for ; Mon, 17 Jan 2022 19:55:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0CE8E385802E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1642449348; bh=FgYodPkI+eWcUghqtMl3Kw2RXjs3RLhymtzgYpzzJGk=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=qFOff/eoViRhwa1bNlTMe5+duw4f1KJFScraViffj/L5SuYBC368dJnonOuI3PWhc rP1QKjSVH5qHkZOiyXuYFZH3FkojbgyUdUQxeGCeBi5+AMhw3CZrLhgQcwQKQozAtY 6CVq4TUq9hG00AFvDTZvAVPNnWjATRFxTx8NBbuw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id EB2DA3858416 for ; Mon, 17 Jan 2022 19:55:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EB2DA3858416 Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-126-H5kgBnE_NO-9mvjjLbfz-A-1; Mon, 17 Jan 2022 14:55:26 -0500 X-MC-Unique: H5kgBnE_NO-9mvjjLbfz-A-1 Received: by mail-qt1-f199.google.com with SMTP id bb10-20020a05622a1b0a00b002cae750b213so2359317qtb.22 for ; Mon, 17 Jan 2022 11:55:26 -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:cc:from:subject; bh=HRp/bTWD14T3TdeXhUXYhozIv/bUHs31M18I2E/wXTM=; b=EN0uUeVDZXL2CFYkC64KVZnDZlhUDg6zBM4iwsvXMfxyO4LGzmylvu6wio7bqZWACB JSqi/XzmPcYwTxdMNlU4ZfsyJlnCz5jqatNit2Lsnu6Y/4bZKVN5jSLa2wTGbUGJQ6v6 k2O6kq9gzXVwVSejlbWN3UiES3RwtkMsrwQn73aq5wr2DzldoZzcqUvxinDXr9EQQ19c jqJk9Vs9i1t3cLGBofRzets4RtQ6eNLKwl7L3SLX7GVasLG1iiSABaojUw74AmwPpQHF v02SioPbYOEvMy8mEgFt5sEAA/mV2eVz6duiwsXchUStBmzEvzXM9xGfzovDsRR0kZdf 7SZw== X-Gm-Message-State: AOAM531r7dVW86AjohL++rMnK5njAfxtJ6VMydB0fxHgdx3b3ugv0uIm 5arY1omWn2GHSn0PGZT/BSIoglbPcmyTgAUPlNATl8QPiobzaUZhnpd7/N3fZ5OH3PLcSDwz/fn U6ys9B9MfHZ8Mt3Qhr8hLFJuaB3Xwj9R/BT5Em33osKE6scZJPKha2Cn3MDhFrpZ386fPUw== X-Received: by 2002:ac8:5993:: with SMTP id e19mr8899745qte.500.1642449325332; Mon, 17 Jan 2022 11:55:25 -0800 (PST) X-Google-Smtp-Source: ABdhPJx4ZxcRGTTwAtSCI8xh7WRIvor/5poZzH5PpH+xgjFYhzzhft85Ghk+tJnYmoVFEqKtfHHzIQ== X-Received: by 2002:ac8:5993:: with SMTP id e19mr8899733qte.500.1642449325063; Mon, 17 Jan 2022 11:55:25 -0800 (PST) Received: from ?IPV6:2607:fea8:a262:5f00:e36d:32da:80f:d4e1? ([2607:fea8:a262:5f00:e36d:32da:80f:d4e1]) by smtp.gmail.com with ESMTPSA id x10sm2770067qta.71.2022.01.17.11.55.22 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 17 Jan 2022 11:55:24 -0800 (PST) Message-ID: <665ba9fb-f543-1ed6-b54d-fea57dda1dd8@redhat.com> Date: Mon, 17 Jan 2022 14:55:21 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.1 To: gcc-patches Subject: [PATCH] tree-optimization/104038 - Limit the number of relations registered per basic block. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-CA X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, 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: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" As mentioned in the PR, this demonstrates the potentially quadratic performance behaviour of adding transitive relations over a series of cascading calculations. As the lookup in a basic block is also linear in nature, I think for this release it makes sense to simply limit the number of relations we can register in any given block. I compiled all the c++ files in gcc, and there was only one BB in fold-const that had more than 30 relations.. and it was a smaller case of this sort of transitive behaviour..  and it capped out at 120 relations. I added a new --param, and defaulted it to 200.  It has a range of 0-9999, choosing 0 would in effect turn off relations.. which is also handy.  Caveat: this flag does not affect equivalences since they are processed in a completely different way. I ran the testcase with the max 9999 and it finished fine. I couldn't create  a simple/smallish testcase to run, so I didn't include one. Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk? Andrew commit 33149a818e8ef25691a159b6f7903c982b22b541 Author: Andrew MacLeod Date: Mon Jan 17 12:03:18 2022 -0500 Limit the number of relations registered per basic block. In pathological cases, the number of transitive relations being added is potentially quadratic. Lookups for relations in a block is linear in nature, so simply limit the number of relations to some reasonable number. PR tree-optimization/104038 * doc/invoke.texi (relation-block-limit): New. * params.opt (relation-block-limit): New. * value-relation.cc (dom_oracle::register_relation): Check for NULL record before invoking transitive registery. (dom_oracle::set_one_relation): Check limit before creating record. (dom_oracle::register_transitives): Stop when no record created. * value-relation.h (relation_chain_head::m_num_relations): New. diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 7f2205e4a85..106f535dc51 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -15088,6 +15088,9 @@ per supernode, before terminating analysis. Maximum depth of logical expression evaluation ranger will look through when evaluating outgoing edge ranges. +@item relation-block-limit +Maximum number of relations the oracle will register in a basic block. + @item openacc-kernels Specify mode of OpenACC `kernels' constructs handling. With @option{--param=openacc-kernels=decompose}, OpenACC `kernels' diff --git a/gcc/params.opt b/gcc/params.opt index 665071fbed1..b07663daa05 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -915,6 +915,10 @@ Common Joined UInteger Var(param_ranger_logical_depth) Init(6) IntegerRange(1, 9 Maximum depth of logical expression evaluation ranger will look through when evaluating outgoing edge ranges. +-param=relation-block-limit= +Common Joined UInteger Var(param_relation_block_limit) Init(200) IntegerRange(0, 9999) Param Optimization +Maximum number of relations the oracle will register in a basic block. + -param=rpo-vn-max-loop-depth= Common Joined UInteger Var(param_rpo_vn_max_loop_depth) Init(7) IntegerRange(2, 65536) Param Optimization Maximum depth of a loop nest to fully value-number optimistically. diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 1e495bdf94c..32ca693c464 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -889,13 +889,14 @@ dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1, else { relation_chain *ptr = set_one_relation (bb, k, op1, op2); - register_transitives (bb, *ptr); + if (ptr) + register_transitives (bb, *ptr); } } // Register relation K between OP! and OP2 in block BB. // This creates the record and searches for existing records in the dominator -// tree to merge with. +// tree to merge with. Return the record, or NULL if no record was created. relation_chain * dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, @@ -940,6 +941,13 @@ dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1, } else { + if (m_relations[bbi].m_num_relations >= param_relation_block_limit) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Not registered due to bb being full\n"); + return NULL; + } + m_relations[bbi].m_num_relations++; // Check for an existing relation further up the DOM chain. // By including dominating relations, The first one found in any search // will be the aggregate of all the previous ones. @@ -1040,7 +1048,8 @@ dom_oracle::register_transitives (basic_block root_bb, value_relation nr (relation.kind (), r1, r2); if (nr.apply_transitive (*ptr)) { - set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()); + if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ())) + return; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " Registering transitive relation "); diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 207defa4b8e..44d0796d939 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -157,6 +157,7 @@ class relation_chain_head public: bitmap m_names; // ssa_names with relations in this block. class relation_chain *m_head; // List of relations in block. + int m_num_relations; // Number of relations in block. relation_kind find_relation (const_bitmap b1, const_bitmap b2) const; };