From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 809 invoked by alias); 20 May 2019 13:04:14 -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 800 invoked by uid 89); 20 May 2019 13:04:13 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.8 required=5.0 tests=AWL,BAYES_00,SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mail2-relais-roc.national.inria.fr Received: from mail2-relais-roc.national.inria.fr (HELO mail2-relais-roc.national.inria.fr) (192.134.164.83) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 20 May 2019 13:04:11 +0000 Received: from grove.saclay.inria.fr ([193.55.177.244]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 20 May 2019 15:04:08 +0200 Date: Mon, 20 May 2019 13:04:00 -0000 From: Marc Glisse Reply-To: gcc-patches@gcc.gnu.org To: Richard Biener cc: "gcc-patches@gcc.gnu.org" , Jeff Law , Feng Xue OS Subject: Re: [PATCH] Remove empty loop with assumed finiteness (PR tree-optimization/89713) In-Reply-To: Message-ID: References: <334e4382-d393-4a83-0fa6-abd80a949f44@redhat.com> User-Agent: Alpine 2.21 (DEB 202 2017-01-01) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed X-SW-Source: 2019-05/txt/msg01247.txt.bz2 On Mon, 20 May 2019, Richard Biener wrote: > On Sat, May 18, 2019 at 4:00 PM Marc Glisse wrote: >> >> (@Feng Xue, it is better to include testcases in your patches) >> >>>> I'm not a big fan of this patch. I'd rather be looking at either >>>> improving our analysis >> >> Better analysis cannot hurt. >> >>>> or adding attributes to the loops to help the analysis bits prove >>>> termination. >> >> There may not be a loop in the source code, it may be a recursive function >> call that gcc turned into a loop. Plus, I know that it applies to all >> loops in my program. >> >> We could have a function to compute the length of a linked list: >> struct A { A*p; }; >> unsigned l(A*a){return a?l(a->p)+1:0;} >> >> and because of other optimizations, it turns out that we do not actually >> use this length >> void g(A*a){l(a);} >> >> wouldn't it be nice if gcc could remove all that useless code, instead of >> keeping a useless loop on the off chance that it might be infinite? >> >>> And we had sth similar in the past and ended up removing it. -funsafe-loop-optimizations IIRC. >> >> IIUC that was slightly different: "This option tells the loop optimizer to >> assume that loop indices do not overflow, and that loops with nontrivial >> exit condition are not infinite." >> >> The assumption on indices looks unsafe indeed if it applied to unsigned >> indices in non-empty loops. > > The question is of couse what a "nontrivial exit condition" is. Indeed > the general handling of unsigned wrapping was what made the option > useless in practice. > > But we thoroughly need to specify "nontrivial exit condition", if going > as far as non-constant exit condition, that is, only do {} while (1) is required > to be detected as infinite then this breaks down to unsigned wrapping IVs > not be infinite. Otherwise it requires the compiler to be able to correctly > analyze all unsigned IVs which I know we do not at the moment (SCEV > has limits). We also want to handle pointer-chasing loops (lists, trees), not specifically unsigned IV. > So - any suggestion as to how define "nontrivial exit condition"? > >> But the C++ standard went to the trouble of banning infinite loops without >> side effects specifically to enable DCE on this type of code... Actually, >> an infinite loop with a trivial exit condition looks like a great >> opportunity to use __builtin_unreachable() to me ;-) (I have been wanting >> a -fmain-does-return -fno-funny-business for years, since I looked at >> replacing some malloc with stack allocations, but that's all out of scope >> for this patch) >> >> Why exactly are we trying so hard to preserve no-side-effect, infinite >> loops? What are they good for? Note that reading an atomic or volatile >> variable counts as a side effect for this purpose. It looks like some kind >> of busy waiting, but without checking a flag, so it can only be stopped by >> some external action (say a signal), so if the OS has any notion of sleep >> for a thread, blocking would be better. Or maybe it is running through a >> circular list, ensuring that it stays in RAM? Anyway it seems specific >> enough that that strange code should be the one needing an annotation. > > I guess we preserve them because we have to? > > I suppose we could add a flag that allows us to elide > loops with no side-effect and non-constant exit condition > (so only preserve do{}while (1))? The C++ standard says that do{}while(1) is __builtin_unreachable(), we don't have to preserve it. There is no mention of anything like a "nontrivial exit condition". Other languages may have a different opinion though, so it would probably need a flag indeed... But I am curious what the point of such a loop is. -- Marc Glisse