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 ESMTP id B346B3858414 for ; Wed, 8 Sep 2021 16:19:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B346B3858414 Received: from mail-wm1-f72.google.com (mail-wm1-f72.google.com [209.85.128.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-154-kVVVTzBqMM6mgPakwZx9mQ-1; Wed, 08 Sep 2021 12:19:50 -0400 X-MC-Unique: kVVVTzBqMM6mgPakwZx9mQ-1 Received: by mail-wm1-f72.google.com with SMTP id s197-20020a1ca9ce000000b002e72ba822dcso1292399wme.6 for ; Wed, 08 Sep 2021 09:19:50 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=2ZvKh8T6uVnVc2kVGcWiJmmXQz4derCRGQxB+SNRYNE=; b=ZSahooBie5rG7aseLNLzEMVhUUzbnTlyZhNaZdph8o9JyCZOP9p4US3oiDEE0YnhjZ qKrDZMnxJe+C86rAwYj5ic1qTwnAydswhdE4Z8hGIGlXCd2assNoFpFCEOUlRtfW9vx5 4GZbfUaQqkmRj2afBw5ZCDeTx5uXaqvS8TslMrW+o3sfbdUwUNSYJnDhCbIpXFld0EMj zKtFGP+kVDrwgbBHmlHr3UVhd2U/9RodDElXYTNm9cNzqHgJN+69MEGdh4l3lJdAEyjO qYthBDdv24+VitZLVoUqTAo8ega9F91hJ3mt2kzToP+1YcHNO0pFT928NnoR3iCp+pZU 4KYA== X-Gm-Message-State: AOAM532ChhPNZ5oXDb0NkipfpjmGnW3fAJktULunyEBVKG0g43LlZcrf 6qU+TORc5bpLZ+AnMXypOUZ3ffGzAbO72SseHyzKzjpja3KQKVV/874faonrS1bsuNU+jMJI8dC FwbRvKIo= X-Received: by 2002:adf:e74a:: with SMTP id c10mr5054547wrn.350.1631117989171; Wed, 08 Sep 2021 09:19:49 -0700 (PDT) X-Google-Smtp-Source: ABdhPJw2EOjqMCaaOhENK35xe5guX3+qb4yxUzH3ZXTZIWiZWmpBfeh+KYyrdavMFTDtAV8LZbPJiA== X-Received: by 2002:adf:e74a:: with SMTP id c10mr5054513wrn.350.1631117988880; Wed, 08 Sep 2021 09:19:48 -0700 (PDT) Received: from abulafia.quesejoda.com ([139.47.33.227]) by smtp.gmail.com with ESMTPSA id v9sm2419261wml.46.2021.09.08.09.19.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 08 Sep 2021 09:19:48 -0700 (PDT) Subject: Re: More aggressive threading causing loop-interchange-9.c regression To: Richard Biener Cc: Michael Matz , Jeff Law , GCC Mailing List , Andrew MacLeod References: <09e48b82-bc51-405e-7680-89a5f08e4e8f@redhat.com> From: Aldy Hernandez Message-ID: <6d5695e4-e4eb-14a5-46a6-f425d1514008@redhat.com> Date: Wed, 8 Sep 2021 18:19:47 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 MIME-Version: 1.0 In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, 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@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 Sep 2021 16:19:53 -0000 On 9/8/21 3:49 PM, Richard Biener wrote: > On Wed, Sep 8, 2021 at 3:25 PM Aldy Hernandez wrote: >> >>> It would be helpful to have the patch causing the issue to look at the IL. >>> But as Micha said, there needs to be a perfect loop nest for interchange >>> to work. >>> >>> Richard. >> >> Absolutely! I'm attaching the reduced testcase, as well as the patch. >> >> The problematic thread shows up in the thread2 dump: >> >> Checking profitability of path (backwards): bb:3 (4 insns) bb:9 (0 >> insns) bb:5 >> Control statement insns: 2 >> Overall: 2 insns >> Registering FSM jump thread: (5, 9) incoming edge; (9, 3) (3, 8) >> nocopy; (3, 8) > > Well, so as Micha said, the threading destroys the outer loop by > making it have two entries - we actually _do_ recover from this > but it results in a non-empty latch of the outer loop and thus > the loop is no longer a perfect nest. The interchange pass has > special-sauce to recover from the loop store motion applied > but not to handle the kind of loop rotation the jump threading > caused. Understood. The backedge into BB8 and the non-empty latch seem to cause problems. > > The forward threader guards against this by simply disallowing > threadings that involve different loops. As I see The thread in question (5->9->3) is all within the same outer loop, though. BTW, the backward threader also disallows threading across different loops (see path_crosses_loops variable). > the threading done here should be 7->3 (outer loop entry) to bb 8 > rather than one involving the backedge. Also note the condition > is invariant in the loop and in fact subsumed by the condition > outside of the loop and it should have been simplified by > VRP after pass_ch but I see there's a jump threading pass > inbetween pass_ch and the next VRP which is likely the > problem. A 7->3->8 thread would cross loops though, because 7 is outside the outer loop. > > Why does jump threading not try to simplify a condition before > attempting to thread through it? After all ranger should be around? That's a very good question ;-). The current code does not use the ranger to solve unknowns. Anything further back than the first block in a path will return varying. The plan was to add this ranger solving functionality as a follow-up. I have a whole slew of pending patches adding precisely this functionality. We should be able to solve ranges outside the path with ranger, as well as relationals occurring in a path. However, even if there are alternate ways of threading this IL, something like 5->9->3 could still happen. We need a way to disallow this. I'm having a hard time determining the hammer for this. I would vote for disabling threading through latches, but it seems the backward threader is aware of this scenario and allows it anyhow (see threaded_through_latch variable). Ughh. Thanks for looking into this. Aldy