On Nov 24, 2010, at 3:58 PM, Owen Anderson wrote:> > On Nov 24, 2010, at 1:23 PM, Andrew Clinton wrote: >> >> FYI, removing the ScalarEvolution conditional in the LoopDeletion code >> (and copying the algorithm to my own loop deletion pass) seems to >> correctly handle the elimination of infinite loops. However I'd still >> like to find a way to do this with standard passes if possible. > > There is no way to do this with the standard pass set, because removing an infinite loop is > an invalid transformation. John Regehr wrote a pretty good exposé about why it's illegal > here: http://blog.regehr.org/archives/140FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1. In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: for (unsigned i = 0; i <= N; ++i) class of problems. I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions. -Chris
Hi Chris,>>> FYI, removing the ScalarEvolution conditional in the LoopDeletion code >>> (and copying the algorithm to my own loop deletion pass) seems to >>> correctly handle the elimination of infinite loops. However I'd still >>> like to find a way to do this with standard passes if possible. >> >> There is no way to do this with the standard pass set, because removing an infinite loop is >> an invalid transformation. John Regehr wrote a pretty good exposé about why it's illegal >> here: http://blog.regehr.org/archives/140 > > FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1.the C++/C standards are not relevant to other languages, such as Ada.> In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: > > for (unsigned i = 0; i<= N; ++i) > > class of problems.Also not relevant to Ada! I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions. Do you have a suggestion for how best to enable this optimization for some languages and disable it for others? Ciao, Duncan.
> Do you have a suggestion for how best to enable this optimization for some > languages and disable it for others?Function attribute or metadata to let the optimizer know that all loops in the given function are finite? That should allow mixing IL files from different languages.> Ciao, > > Duncan.Cheers, Rafael
>> In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: >> >> for (unsigned i = 0; i<= N; ++i) >> >> class of problems. > > Also not relevant to Ada!Ada? What's that? ;-)> Do you have a suggestion for how best to enable this optimization for some > languages and disable it for others?Sure, there are two ways to go: 1. Assume that loops are never infinite and add IR support to say that a loop *is*. 2. Assume that loops are possibly infinite and add IR support to say that a loop *isn't*. I'm just saying I'm in favor of #1. This could take the form of an intrinsic that gets called in loop headers or something. -Chris
On Sun, Nov 28, 2010 at 12:12, Chris Lattner <clattner at apple.com> wrote:> > FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1. > > In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: > > for (unsigned i = 0; i <= N; ++i) > > class of problems. I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions. >Does that mean that for (unsigned i = 0; i <= N; ++i) {} and for (unsigned i = 0; ; ++i) { if (i <= N) break; } would then have different semantics? ~ Scott
On Nov 29, 2010, at 1:52 PM, me22 wrote:> On Sun, Nov 28, 2010 at 12:12, Chris Lattner <clattner at apple.com> wrote: >> >> FWIW, this is currently a discussion in the C++ and C committees, and my understanding is that this has changed (or is changing soon) in the C'1x draft. Assuming it happens, it will make it valid to assume that loops always terminate unless they are written with a condition that is an integer constant expression that folds to 1. >> >> In addition to being able to delete noop loops that traverse over pointer-based data structures, this will also solve the: >> >> for (unsigned i = 0; i <= N; ++i) >> >> class of problems. I'm obviously strongly in favor of this, and I also think we should apply it to all C languages. I don't see any reason for people to write infinite loops with non-trivial conditions. >> > > Does that mean that > for (unsigned i = 0; i <= N; ++i) {} > and > for (unsigned i = 0; ; ++i) { if (i <= N) break; } > would then have different semantics?I don't know the details of the proposal, sorry. comp.lang.c[++] would be a good place to ask. -Chris