From patchwork Mon Jun 26 14:02:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1799969 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.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=qU0zPu3b; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QqV1607Ldz1yhT for ; Tue, 27 Jun 2023 00:03:06 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C82F53858C31 for ; Mon, 26 Jun 2023 14:03:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C82F53858C31 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687788183; bh=etPTeV8qVp5hZezoo5SxWyspEu+MY6AwGlVsIgHAlvQ=; h=Date:Subject:To:Cc:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=qU0zPu3bj/MUVQj8XS60LIodVZSh2SvW5XNy5rBqwvYe0YQEEgH5eIyLVVf/1SDhs kIoXoiEATd4HzoVBxz/qEJyVzCx2yZ/Q093ewpEIs+OkKP1vZoWL8wGDb7PDE1CEvh /R9HGy4+CsNXQR6HbxolrrhveQE+Dy/cr+wjiwiU= 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 77C3B3858D1E for ; Mon, 26 Jun 2023 14:02:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 77C3B3858D1E Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-636-U8qeElseOdOxKmYJt7loLQ-1; Mon, 26 Jun 2023 10:02:36 -0400 X-MC-Unique: U8qeElseOdOxKmYJt7loLQ-1 Received: by mail-qv1-f69.google.com with SMTP id 6a1803df08f44-62fe5abe808so18049906d6.1 for ; Mon, 26 Jun 2023 07:02:35 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1687788155; x=1690380155; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=oqkb9lBpgyttmMam8MahQBnyzoUKMwcyERnws9Y7X6M=; b=AI9VlzebW8qIN0mPmBaBQBrH7g1vppVNETvzUBjvxgQI19ygwDnvwIN+DvQciS2NMz bY3c+S/mQywndOhy+f1GuBidry+ELgA01w3W7/Qg+/eKnAj2x6ueoSzejAws8JTs3I2X 0rtdMLQw3sy1FQzpoehmGgEo/HZ+B59k+tliAyaldFmul1NdvknG+edomBrDq13DfVvK /5xBOPHPGBAQHn96cY1/7k70pdyhIrGRxMLAW0BzOCP3tTT9Z4JheuHRTboyXvjy4fKd ObV5k6Aa265UZmS0o/HqZqmuN32q8lxRbAooelXBoA0sEhxg6dfGPUZI9A8bFheXnxzb heZQ== X-Gm-Message-State: AC+VfDz+qqaBMiIzz7gP3NFBWen9fKNIhXy7wSHfwzC590KALcAP4Bgr IKrkjXysmQdA0ks6xxbjf4yGPGgjNB8JkqrBjAT+0nPpYwIQDNDiv69N5EvKDPLhIu+7RjLZWiV dEEn12YkofnQrEPpWYZo3/crwMnYK+7df35Qsu9VWYwig1hXzeb4JJIVIfzU/XJwj1ha4EdG7C6 ezTg== X-Received: by 2002:a05:6214:250d:b0:635:e286:d4b with SMTP id gf13-20020a056214250d00b00635e2860d4bmr1975627qvb.18.1687788155069; Mon, 26 Jun 2023 07:02:35 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ6cBfeKaakJDHvnHF+DTBI0Xn6vMtmW2a0VlIPrbgT2WLczuKxClD29Eq3IsdtWlvMcwbmHbQ== X-Received: by 2002:a05:6214:250d:b0:635:e286:d4b with SMTP id gf13-20020a056214250d00b00635e2860d4bmr1975588qvb.18.1687788154677; Mon, 26 Jun 2023 07:02:34 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::ca58? ([2607:fea8:51df:4200::ca58]) by smtp.gmail.com with ESMTPSA id oo25-20020a05620a531900b0075c9abecdf8sm2753207qkn.1.2023.06.26.07.02.33 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 26 Jun 2023 07:02:34 -0700 (PDT) Message-ID: Date: Mon, 26 Jun 2023 10:02:32 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: [COMMITTED] PR tree-optimization/110251 - Avoid redundant GORI calcuations. To: gcc-patches Cc: "hernandez, aldy" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-10.7 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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" When calculating ranges, GORI evaluates the chain of definitions until it finds the desired name.   _4 = (short unsigned int) c.2_1;   _5 = _4 + 65535;   a_lsm.19_30 = a;   _49 = _4 + 65534;   _12 = _5 & _49;   _46 = _12 + 65535;   _48 = _12 & _46;        <<------   if (_48 != 0) When evaluating c.2_1 on the true edge, GORI starts with _48 with a range of [1, +INF] Looking at _48's operands (_12 and _46), note that it depends both  _12 and _46.  Also note that _46 is also dependent on _12. GORI currently simply calculates c.2_1 through both operands. this means _12 will be evaluates back thru to c.2_1, and then _46 will do the same and the results will be combined.  that means the statements from _12 back to c.2_1 are actually calculated twice. This PR produces a sequence of code which is quite long, with cascading chains of dependencies like this that feed each other. This becomes a geometric/exponential growth in calculation time, over and over. This patch identifies the situation of one operand depending on the other, and simply evaluates only  the one which includes the other.  In the above case, it simply winds back thru _46 ignoring the _12 operand in the definition of _48.    During the process of evaluating _46, we eventually get to evaluating _12 anyway, so we don't lose much, if anything.    This results in a much more consistently linear time evaluation. Bootstraps on x86_64-pc-linux-gnu with no regressions.   Pushed. Andrew commit 6246ee062062b53275c229daf8676ccaa535f419 Author: Andrew MacLeod Date: Thu Jun 22 10:00:12 2023 -0400 Avoid redundant GORI calcuations. When GORI evaluates a statement, if operand 1 and 2 are both in the dependency chain, GORI evaluates the name through both operands sequentially and combines the results. If either operand is in the dependency chain of the other, this evaluation will do the same work twice, for questionable gain. Instead, simple evaluate only the operand which depends on the other and keep the evaluation linear in time. * gimple-range-gori.cc (compute_operand1_and_operand2_range): Check for interdependence between operands 1 and 2. diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index abc70cd54ee..4ee0ae36014 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -1291,13 +1291,26 @@ gori_compute::compute_operand1_and_operand2_range (vrange &r, { Value_Range op_range (TREE_TYPE (name)); - // Calculate a good a range for op2. Since op1 == op2, this will - // have already included whatever the actual range of name is. - if (!compute_operand2_range (op_range, handler, lhs, name, src, rel)) + // If op1 is in the def chain of op2, we'll do the work twice to evalaute + // op1. This can result in an exponential time calculation. + // Instead just evaluate op2, which will eventualy get to op1. + if (in_chain_p (handler.operand1 (), handler.operand2 ())) + return compute_operand2_range (r, handler, lhs, name, src, rel); + + // Likewise if op2 is in the def chain of op1. + if (in_chain_p (handler.operand2 (), handler.operand1 ())) + return compute_operand1_range (r, handler, lhs, name, src, rel); + + // Calculate a good a range through op2. + if (!compute_operand2_range (r, handler, lhs, name, src, rel)) return false; + // If op1 == op2 there is again no need to go further. + if (handler.operand1 () == handler.operand2 ()) + return true; + // Now get the range thru op1. - if (!compute_operand1_range (r, handler, lhs, name, src, rel)) + if (!compute_operand1_range (op_range, handler, lhs, name, src, rel)) return false; // Both operands have to be simultaneously true, so perform an intersection.