From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 86900 invoked by alias); 30 Apr 2015 10:45:26 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 86883 invoked by uid 89); 30 Apr 2015 10:45:25 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-oi0-f41.google.com Received: from mail-oi0-f41.google.com (HELO mail-oi0-f41.google.com) (209.85.218.41) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Thu, 30 Apr 2015 10:45:24 +0000 Received: by oift201 with SMTP id t201so44528381oif.3 for ; Thu, 30 Apr 2015 03:45:22 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.202.228.71 with SMTP id b68mr2804172oih.58.1430390722123; Thu, 30 Apr 2015 03:45:22 -0700 (PDT) Received: by 10.76.115.167 with HTTP; Thu, 30 Apr 2015 03:45:22 -0700 (PDT) In-Reply-To: <5542054B.3080400@arm.com> References: <553F916C.30609@arm.com> <5542054B.3080400@arm.com> Date: Thu, 30 Apr 2015 11:07:00 -0000 Message-ID: Subject: Re: [PATCH] Remove some restrictions on loop shape in tree-if-conv.c From: Richard Biener To: Alan Lawrence Cc: "gcc-patches@gcc.gnu.org" , "law@redhat.com" Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2015-04/txt/msg01997.txt.bz2 On Thu, Apr 30, 2015 at 12:34 PM, Alan Lawrence wrote: > Richard Biener wrote: >> >> On Tue, Apr 28, 2015 at 3:55 PM, Alan Lawrence >> wrote: >>> >>> Tree if-conversion currently bails out for loops that (a) contain nested >>> loops; (b) have more than one exit; (c) where the exit block (source of >>> the >>> exit edge) does not dominate the loop latch; (d) where the exit block is >>> the >>> loop header, or there are statements after the exit. >>> >>> This patch removes restrictions (c) and (d). The intuition is that, for >>> (c), >>> "if (P) {... if (Q) break;}" is equivalent to "if (P) {...}; if (P&&Q) >>> break;" and this is mostly handled by existing code for propagating >>> conditions. For (d), "if (P) break; stmts" is equivalent to "if (!P) >>> stmts; >>> if (P) break;" - this requires inserting the predicated stmts before the >>> branch rather than after. >> >> >> Hum - so you empty the latch by conditionalizing code on the exit >> condition? > > > Well, !(exit condition), but yes. > >> So you still restrict loop form to two blocks - just the latch may now be >> non-empty? Thus I'd say keeping the existing check but amending it by >> && bb != loop->latch would be better. > > > The idea was to try to end up with a loop with exactly two blocks, a main > block with a condition at the end, and an empty latch; but to convert more > bad-loop-form loops into this form. > >> Otherwise the patch looks good to me. >> >> Can you please add at least one testcase for c) and d) where we now >> vectorize something after the patch but not before? > > > So I think I have made an inconsistency, by changing the logic for > dominance-of-latch to postdominance-of-header, in one place but not another > (where it deals with conditional stores) - but I haven't managed to tickle > that yet. > > However, I'm struggling to find a case where this patch enables > vectorization; the fancy if-converted loops tend to have other problems > preventing vectorization, e.g. location of PHI nodes. In contrast, your > suggestion of putting in another loop-header-copying pass, enables both > if-conversion (with the existing tree-if-conv.c) and vectorization of a > bunch of things (including the example I posted of this patch if-converting > but still not vectorizing). So (short of massive changes to the vectorizer) > that approach now feels more promising, although there are a good bunch of > scan-tree-dump test failures that I need to look into... Heh. I would have said the loop header copying could be done by the vectorizer itself when it detects the non-empty latch simply call a factored function from loop header copying that forcefully duplicates the header (well, or simply inline the short relevant portion). We'd eventually want to undo this if vectorization fails but that's possibly a secondary concern. Another possibility is to piggy-back that onto the if-conversion pass and force the use of versioning for that. Moving the CH pass is sth entirely different and I'd rather not do that. Richard. > Where (something like) this patch might be useful, could be as a first step > to handling loops with multiple exits, that is, changing > > for (;;) > { > S1; > if (P) break; > S2; > if (Q) break; > S3; > } > > into the equivalent of > > for (;;) > { > S1; > if (!P) S2; > if (!P && !Q) S3; > if (P || Q) break; > } > > But that's more work, and another patch, and I'm not yet clear how many > loops of that form the vectorizer would do anything with anyway (let alone > profitably!)... > > Cheers, Alan >