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.133.124]) by sourceware.org (Postfix) with ESMTPS id 7EEC6385841D for ; Thu, 11 Nov 2021 10:33:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 7EEC6385841D Received: from mail-ot1-f70.google.com (mail-ot1-f70.google.com [209.85.210.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-372-D28awtxkMRKufte8gXMjoQ-1; Thu, 11 Nov 2021 05:33:56 -0500 X-MC-Unique: D28awtxkMRKufte8gXMjoQ-1 Received: by mail-ot1-f70.google.com with SMTP id l71-20020a9d1b4d000000b00553d78fb5c3so3016096otl.16 for ; Thu, 11 Nov 2021 02:33:56 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=yrKf71D52cYHkM51RJTgLLG6mXhwR0zVQ1kXhuJ6ijg=; b=EOpg2seIDFHPwovfxWAZm36o8WPVH4Yd9DGulyLLk1mUdylqIUa8cSgIOUyLn3LxjO IYd8qxRcoKAwZlgiPEbFpcWpxDbLUC7lkeF++ZUq/yArESp5mWGyip8w9Izd1oF6FQ7r wfSj7l9m/e4YqPLJRbxfh2cz0mHes4ovkx/LTNhvCEBbPqYtXBnz7iHyIlgmO6rbMXQ1 v4NrYvah7f8xBa7/TuTHVSpy67FrRSDMb8N36wn0xhTyFqR9zAACy8kli7TPeqHqtn9I gpBQ+jtLdcJk0JOISOnlWvNh0E2wBfYsfwm1r/uXW0XYqcsGEOXzJNwTeMKhrGRPY4gH /uJA== X-Gm-Message-State: AOAM531JFLnr1Nk/8Bhu+hHAVdED4eVR1OfGLM4lIts9tR66QaZCNEXU a46t4cOG9XHvDXntNyYWN1A9YsIg2kZ1Unk//EEGNXmVG01r82ULsAb13dOj/+E2b11yNUL4Yrf qs3KK4QjrcJwEdlr11UkJNKlBxtv6Hz872g== X-Received: by 2002:a05:6808:2091:: with SMTP id s17mr18407977oiw.127.1636626836089; Thu, 11 Nov 2021 02:33:56 -0800 (PST) X-Google-Smtp-Source: ABdhPJwGU/mdFnD8vRVgr9TDfhS4QhchjjNJRdRXbngj0RHY0WVHOvaHS9Dbe1z7vcYDfqaGA596dOoGcLu9z31qC3c= X-Received: by 2002:a05:6808:2091:: with SMTP id s17mr18407954oiw.127.1636626835891; Thu, 11 Nov 2021 02:33:55 -0800 (PST) MIME-Version: 1.0 References: <20211110182003.686241-1-aldyh@redhat.com> <9f11bb40-7769-ff6b-72bf-f1eb48944760@gmail.com> In-Reply-To: From: Aldy Hernandez Date: Thu, 11 Nov 2021 11:33:44 +0100 Message-ID: Subject: Re: [PATCH] Allow loop header copying when first iteration condition is known. To: Richard Biener Cc: Jeff Law , GCC patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="0000000000002f1ac405d080e13a" X-Spam-Status: No, score=-11.9 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_H2, 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-List-Received-Date: Thu, 11 Nov 2021 10:34:00 -0000 --0000000000002f1ac405d080e13a Content-Type: text/plain; charset="UTF-8" On Thu, Nov 11, 2021 at 8:30 AM Richard Biener wrote: > > On Wed, Nov 10, 2021 at 9:42 PM Jeff Law wrote: > > > > > > > > On 11/10/2021 11:20 AM, Aldy Hernandez via Gcc-patches wrote: > > > As discussed in the PR, the loop header copying pass avoids doing so > > > when optimizing for size. However, sometimes we can determine the > > > loop entry conditional statically for the first iteration of the loop. > > > > > > This patch uses the path solver to determine the outgoing edge > > > out of preheader->header->xx. If so, it allows header copying. Doing > > > this in the loop optimizer saves us from doing gymnastics in the > > > threader which doesn't have the context to determine if a loop > > > transformation is profitable. > > > > > > I am only returning true in entry_loop_condition_is_static for > > > a true conditional. Technically a false conditional is also > > > provably static, but allowing any boolean value causes a regression > > > in gfortran.dg/vector_subscript_1.f90. > > > > > > I would have preferred not passing around the query object, but the > > > layout of pass_ch and should_duplicate_loop_header_p make it a bit > > > awkward to get it right without an outright refactor to the > > > pass. > > > > > > Tested on x86-64 Linux. > > > > > > OK? > > > > > > gcc/ChangeLog: > > > > > > PR tree-optimization/102906 > > > * tree-ssa-loop-ch.c (entry_loop_condition_is_static): New. > > > (should_duplicate_loop_header_p): Call entry_loop_condition_is_static. > > > (class ch_base): Add m_ranger and m_query. > > > (ch_base::copy_headers): Pass m_query to > > > entry_loop_condition_is_static. > > > (pass_ch::execute): Allocate and deallocate m_ranger and > > > m_query. > > > (pass_ch_vect::execute): Same. > > > > > > gcc/testsuite/ChangeLog: > > > > > > * gcc.dg/tree-ssa/pr102906.c: New test. > > OK. It also makes a nice little example of how to use a Ranger within > > an existing pass. > > Note if you just test for the condition to be true it will only catch 50% > of the desired cases since we have no idea whether the 'true' edge > is the edge existing the loop or the edge remaining in the loop. > For loop header copying we like to resolve statically to the edge > remaining in the loop, so you want Ahh, I figured there was some block shuffling needed. I was cautious not to touch much because of the gfortran.dg/vector_subscript_1.f90 regression, but now I see that the test fails for all optimization levels except -Os. With this fix we properly fail for all levels. I assume this is expected ;-). > > extract_true_false_edges_from_block (gimple_bb (last), &true_e, &false_e); > > /* If neither edge is the exit edge this is not a case we'd like to > special-case. */ > if (!loop_exit_edge_p (l, true_e) && !loop_exit_edge_p (l, false_e)) > return false; > > tree desired_static_value; > if (loop_exit_edge_p (l, true_e)) > desired_static_value = boolean_false_node; > else > desired_static_value = boolean_true_node; > > and test for desired_static_value. Thanks for the code! OK pending tests? --0000000000002f1ac405d080e13a Content-Type: text/x-patch; charset="US-ASCII"; name="0001-Resolve-entry-loop-condition-for-the-edge-remaining-.patch" Content-Disposition: attachment; filename="0001-Resolve-entry-loop-condition-for-the-edge-remaining-.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_kvutbknj0 RnJvbSA5NjA5Y2ZmMjc4ZDNkZGVhOWY3NGI4MDViMzk1ZDVjMDI5M2ExMjZjIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBBbGR5IEhlcm5hbmRleiA8YWxkeWhAcmVkaGF0LmNvbT4KRGF0 ZTogVGh1LCAxMSBOb3YgMjAyMSAxMToyNzowNyArMDEwMApTdWJqZWN0OiBbUEFUQ0hdIFJlc29s dmUgZW50cnkgbG9vcCBjb25kaXRpb24gZm9yIHRoZSBlZGdlIHJlbWFpbmluZyBpbiB0aGUKIGxv b3AuCgpUaGVyZSBpcyBhIGtub3duIGZhaWx1cmUgZm9yIGdmb3J0cmFuLmRnL3ZlY3Rvcl9zdWJz Y3JpcHRfMS5mOTAuICBJdAp3YXMgcHJldmlvdXNseSBmYWlsaW5nIGZvciBhbGwgb3B0aW1pemF0 aW9uIGxldmVscyBleGNlcHQgLU9zLgpHZXR0aW5nIHRoZSBsb29wIGhlYWRlciBjb3B5aW5nIHJp Z2h0LCBub3cgbWFrZXMgaXQgZmFpbCBmb3IgYWxsCmxldmVscyA6LSkuCgpDby1hdXRob3JlZC1i eTogUmljaGFyZCBCaWVuZXIgPHJndWVudGhlckBzdXNlLmRlPgoKZ2NjL0NoYW5nZUxvZzoKCgkq IHRyZWUtc3NhLWxvb3AtY2guYyAoZW50cnlfbG9vcF9jb25kaXRpb25faXNfc3RhdGljKTogUmVz b2x2ZQoJc3RhdGljYWxseSB0byB0aGUgZWRnZSByZW1haW5pbmcgaW4gdGhlIGxvb3AuCi0tLQog Z2NjL3RyZWUtc3NhLWxvb3AtY2guYyB8IDE2ICsrKysrKysrKysrKysrKy0KIDEgZmlsZSBjaGFu Z2VkLCAxNSBpbnNlcnRpb25zKCspLCAxIGRlbGV0aW9uKC0pCgpkaWZmIC0tZ2l0IGEvZ2NjL3Ry ZWUtc3NhLWxvb3AtY2guYyBiL2djYy90cmVlLXNzYS1sb29wLWNoLmMKaW5kZXggYzdkODZkNzUx ZDQuLmFmMzQwMWYxMTJjIDEwMDY0NAotLS0gYS9nY2MvdHJlZS1zc2EtbG9vcC1jaC5jCisrKyBi L2djYy90cmVlLXNzYS1sb29wLWNoLmMKQEAgLTU3LDEwICs1NywyNCBAQCBlbnRyeV9sb29wX2Nv bmRpdGlvbl9pc19zdGF0aWMgKGNsYXNzIGxvb3AgKmwsIHBhdGhfcmFuZ2VfcXVlcnkgKnF1ZXJ5 KQogICAgICAgfHwgIWlyYW5nZTo6c3VwcG9ydHNfdHlwZV9wIChUUkVFX1RZUEUgKGdpbXBsZV9j b25kX2xocyAobGFzdCkpKSkKICAgICByZXR1cm4gZmFsc2U7CiAKKyAgZWRnZSB0cnVlX2UsIGZh bHNlX2U7CisgIGV4dHJhY3RfdHJ1ZV9mYWxzZV9lZGdlc19mcm9tX2Jsb2NrIChlLT5kZXN0LCAm dHJ1ZV9lLCAmZmFsc2VfZSk7CisKKyAgLyogSWYgbmVpdGhlciBlZGdlIGlzIHRoZSBleGl0IGVk Z2UsIHRoaXMgaXMgbm90IGEgY2FzZSB3ZSdkIGxpa2UgdG8KKyAgICAgc3BlY2lhbC1jYXNlLiAg Ki8KKyAgaWYgKCFsb29wX2V4aXRfZWRnZV9wIChsLCB0cnVlX2UpICYmICFsb29wX2V4aXRfZWRn ZV9wIChsLCBmYWxzZV9lKSkKKyAgICByZXR1cm4gZmFsc2U7CisKKyAgdHJlZSBkZXNpcmVkX3N0 YXRpY192YWx1ZTsKKyAgaWYgKGxvb3BfZXhpdF9lZGdlX3AgKGwsIHRydWVfZSkpCisgICAgZGVz aXJlZF9zdGF0aWNfdmFsdWUgPSBib29sZWFuX2ZhbHNlX25vZGU7CisgIGVsc2UKKyAgICBkZXNp cmVkX3N0YXRpY192YWx1ZSA9IGJvb2xlYW5fdHJ1ZV9ub2RlOworCiAgIGludF9yYW5nZTwyPiBy OwogICBxdWVyeS0+Y29tcHV0ZV9yYW5nZXMgKGUpOwogICBxdWVyeS0+cmFuZ2Vfb2Zfc3RtdCAo ciwgbGFzdCk7Ci0gIHJldHVybiByID09IGludF9yYW5nZTwyPiAoYm9vbGVhbl90cnVlX25vZGUs IGJvb2xlYW5fdHJ1ZV9ub2RlKTsKKyAgcmV0dXJuIHIgPT0gaW50X3JhbmdlPDI+IChkZXNpcmVk X3N0YXRpY192YWx1ZSwgZGVzaXJlZF9zdGF0aWNfdmFsdWUpOwogfQogCiAvKiBDaGVjayB3aGV0 aGVyIHdlIHNob3VsZCBkdXBsaWNhdGUgSEVBREVSIG9mIExPT1AuICBBdCBtb3N0ICpMSU1JVAot LSAKMi4zMS4xCgo= --0000000000002f1ac405d080e13a--