From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 6C940385B533 for ; Tue, 21 Mar 2023 13:43:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6C940385B533 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1679406202; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=AOX3aRMsekKxT2TcW9DJEj071HYoUsAIr74op1Frhlo=; b=LBTsYZj7x1Mp24xJvzhk/TIXjfd2IAb7+xsDHZ0VqXOlsj5GQv1d08TN0qFd4UiYrC58v0 3aLOzWyM7LQjJIvPry6015qyk/1+WpnZcauNVQejIRuR7YRxsRphboQsAGS5LRvxbZekRt KFG/3UxGZzvVdn/OQzwvz1tRbri6ALA= 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-625-kgb_kQuNO8GImLwVN1oKMQ-1; Tue, 21 Mar 2023 09:43:20 -0400 X-MC-Unique: kgb_kQuNO8GImLwVN1oKMQ-1 Received: by mail-qv1-f69.google.com with SMTP id px9-20020a056214050900b005d510cdfc41so342296qvb.7 for ; Tue, 21 Mar 2023 06:43:20 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679406199; h=subject:from:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=TAdkUja1KUg3Cb8FkqVXNNIW9GcXs3YsqVBcvxsOhSk=; b=7eohjnjCgupu73oaV9FpVZqPW7+hXKISa33r8XrfpxzIpY7WBtJ5K+zoFGbhHB4O5w W95T+0jhccgZEQvFrCV9VlEwPdZ3+5U/M56TXKMJoULDc25R5+kvCTxDeogpH6wJ46+I s+DlC7tnDG2T3g4I81X9nQwmhIkMfmOkFD27Eg2kSg9Uw+WFjNm9yF6iK3lfgAO8QCOM abSbuVvNT+0G22CRcd9NubG8Q7F7YKW1KmqPoX0Dj8UtC/GDPAkvl2Yd3zVzs//tFDDh PAWnRPekOm1sSFNQl5mtPyX5DxKc8R7M3SJ0kv2nwu/6CHOPq2AX8ciVeKfbE47b5UFS Gk6A== X-Gm-Message-State: AO0yUKVgI5vRPWyAsG1nRs6pSoBhH8MmiRVFGZQmwYLrBhHvKcFvpJLk we3c92cD9fApOedn3aUjd1P8x8QchB0lIMdcSjhWbN8UchkTTIx7t5qHsFM6g07JFHTxGD+h4+3 v4xEncT15JWNFvX+YHoCZxHWXPsvNQ6ca5jqZS7hYyUCRSN36PKcjKmtsZRcFmTwFGS9/+dfsTZ HPyQ== X-Received: by 2002:a05:622a:1802:b0:3b9:bc8c:c1f6 with SMTP id t2-20020a05622a180200b003b9bc8cc1f6mr24677094qtc.1.1679406199624; Tue, 21 Mar 2023 06:43:19 -0700 (PDT) X-Google-Smtp-Source: AK7set9YXE8RP0KSONdUNtUt8TzLffLbEYpoyuFIkooZh+Im1YJ8d5Dtn9i63iK7Kw601z9zHdtahQ== X-Received: by 2002:a05:622a:1802:b0:3b9:bc8c:c1f6 with SMTP id t2-20020a05622a180200b003b9bc8cc1f6mr24677057qtc.1.1679406199203; Tue, 21 Mar 2023 06:43:19 -0700 (PDT) Received: from ?IPV6:2607:fea8:a263:f600::759b? ([2607:fea8:a263:f600::759b]) by smtp.gmail.com with ESMTPSA id 123-20020a370581000000b007456df35859sm4917249qkf.74.2023.03.21.06.43.18 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 21 Mar 2023 06:43:18 -0700 (PDT) Message-ID: Date: Tue, 21 Mar 2023 09:43:17 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches From: Andrew MacLeod Subject: [PATCH] PR tree-optimization/109192 - Terminate GORI calculations if a relation is not relevant. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="------------ZLcFgkwx0J0yIHfjWH1bwGHP" Content-Language: en-US X-Spam-Status: No, score=-11.2 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_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: This is a multi-part message in MIME format. --------------ZLcFgkwx0J0yIHfjWH1bwGHP Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit As mentioned in the PR, the originally GORI terminated calculation if the LHS was varying as it could not provide any additional useful information on an outgoing edge beyond what folding would give. The original patch  introduced relations, and aloowed GORI to keep going with the hope that the relation might provide new info.  This PR trips over a case where there are a lot of relations, and GORI is unbounded in the path query with is already quadratic. This patch first checks if the relation can have an effect on the outgoing calculation, and if not, terminates the calculation like we use to.  This prevents a lot of excessive checking.  there are 2 cases where the relation is considered relevant:  1- both argument to the relation are in the defchain of the operand currently being calculated: b_2 = x_3 < y_5 c_3 = b_2 != 0 if (c_3 &&  x_3 < y_5) on te true side, we will ge the relation x_3 < y_5,  both of which are in the defchain for c_3.  THis will enable use to evaluate that on the true side, c_3 must be [1,1], and therefore b_2 must be[1, 1], and the relation can be applied to the calculation [1,1] = x_3 < y_5    to establish that c_3 will indeed be [1,1] always if x_3