llvm dev - Sep 2017 - About LoopDeletion and infinite loops ... again! (RFC?)

I see the usecase for mixed language compilation (that’s probably why you fancy
something like the side-effect thing instead right?)

BTW if the other proposal passes can we basically assume that if a loop doesn’t
have the sideeffect intrinsic in it is then removable?

That patch seems to suggest that in its current state llvm is mostly broken for
languages that consider all infinite loops as unremovable ... (but I didn’t read
all the discussion)

Marcello

Sent from my iPhone
> On Sep 29, 2017, at 7:43 PM, Davide Italiano <davide at freebsd.org>
wrote:
> 
> On Fri, Sep 29, 2017 at 7:17 PM, Marcello Maggioni via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> Hello!
>> 
>> I read a bunch of discussions about the matter on this very
mailing-list
>> that are relatively recent or relatively old and I couldn’t find much
>> agreement on the matter, so … here again :D
>> 
>> LoopDeletion and infinite loops …
>> 
>> Currently LoopDeletion bails if non-detectable trip count loops are
>> encountered and that’s fine, there are languages where infinite loops
>> without side effects cannot be removed.
>> 
>> If I read the C++ spec right though N4527 (sec 1.10)  point 27 says:
>> 
>> 27  The implementation may assume that any thread will eventually do
one of
>> the following:
>> 
>> 27.1 — terminate,
>> 
>> 27.2 — make a call to a library I/O function
>> 
>> (27.3)— read or modify a volatile object, or
>> 
>> (27.4)— perform a synchronization operation or an atomic operation.
>> 
>> [Note: This is intended to allow compiler transformations such as
removal of
>> empty loops, even when
>> 
>> termination cannot be proven. — end note ]
>> 
>> 
>> So, the spec seems to be explicitly calling out that removing infinite
loops
>> is ok unless they do any of the things mentioned there (at least that
is my
>> interpretation, is that correct?).
>> 
>> 
>> If that is the case we could be missing out for languages that have
such a
>> behavior (and in particular in C++).
>> 
>> I was wondering how it would be viewed the possibility of adding a flag
to
>> loop deletion that allows the removal of loops with loop counts that
are not
>> SCEVable.
>> 
> 
> You probably have seen it, but, for reference
> https://reviews.llvm.org/D38336 (which goes in the exact opposite
direction).
> 
> I don't necessarily fancy the idea of having a flag, instead, maybe,
> the frontend could emit enough information to tell the optimizer
> whether it is safe to remove the loop?
> 
> Thanks,
> 
> --
> Davide

On 09/29/2017 10:02 PM, Marcello Maggioni via llvm-dev
wrote:
> I see the usecase for mixed language compilation (that’s probably why you
fancy something like the side-effect thing instead right?)
It's also about not having parameterized semantics for the IR. I'd 
certainly find that undesirable. We could make it part of datalayout, or 
similar, but that has problems with mixed-language compilation. It also 
has problems with C, where we generally get to assume that loops 
terminate, but loops with a constant controlling condition (at the 
source level) can be infinite. Whether or not something is a constant 
condition at the source level is something that we need the frontend to 
mark only for specific loops.
>
> BTW if the other proposal passes can we basically assume that if a loop
doesn’t have the sideeffect intrinsic in it is then removable?
If it does not have the sideeffect intrinsic, or some other actual side 
effect (or atomic, etc.), then yes.
>
> That patch seems to suggest that in its current state llvm is mostly broken
for languages that consider all infinite loops as unremovable ... (but I didn’t
read all the discussion)
As I understand it, it is broken in places, but we also don't take 
advantage of assuming that loops terminate as much as we could (assuming 
we fully commit to that assumption).

  -Hal
>
> Marcello
>
> Sent from my iPhone
>
>> On Sep 29, 2017, at 7:43 PM, Davide Italiano <davide at
freebsd.org> wrote:
>>
>> On Fri, Sep 29, 2017 at 7:17 PM, Marcello Maggioni via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>>> Hello!
>>>
>>> I read a bunch of discussions about the matter on this very
mailing-list
>>> that are relatively recent or relatively old and I couldn’t find
much
>>> agreement on the matter, so … here again :D
>>>
>>> LoopDeletion and infinite loops …
>>>
>>> Currently LoopDeletion bails if non-detectable trip count loops are
>>> encountered and that’s fine, there are languages where infinite
loops
>>> without side effects cannot be removed.
>>>
>>> If I read the C++ spec right though N4527 (sec 1.10)  point 27
says:
>>>
>>> 27  The implementation may assume that any thread will eventually
do one of
>>> the following:
>>>
>>> 27.1 — terminate,
>>>
>>> 27.2 — make a call to a library I/O function
>>>
>>> (27.3)— read or modify a volatile object, or
>>>
>>> (27.4)— perform a synchronization operation or an atomic operation.
>>>
>>> [Note: This is intended to allow compiler transformations such as
removal of
>>> empty loops, even when
>>>
>>> termination cannot be proven. — end note ]
>>>
>>>
>>> So, the spec seems to be explicitly calling out that removing
infinite loops
>>> is ok unless they do any of the things mentioned there (at least
that is my
>>> interpretation, is that correct?).
>>>
>>>
>>> If that is the case we could be missing out for languages that have
such a
>>> behavior (and in particular in C++).
>>>
>>> I was wondering how it would be viewed the possibility of adding a
flag to
>>> loop deletion that allows the removal of loops with loop counts
that are not
>>> SCEVable.
>>>
>> You probably have seen it, but, for reference
>> https://reviews.llvm.org/D38336 (which goes in the exact opposite
direction).
>>
>> I don't necessarily fancy the idea of having a flag, instead,
maybe,
>> the frontend could emit enough information to tell the optimizer
>> whether it is safe to remove the loop?
>>
>> Thanks,
>>
>> --
>> Davide
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

On Fri, Sep 29, 2017 at 8:02 PM, Marcello Maggioni <mmaggioni at
apple.com> wrote:
> I see the usecase for mixed language compilation (that’s probably why you
fancy something like the side-effect thing instead right?)
>
That could be a reason, but it wasn't my main motivation. Basically
I'm worried about having per-passes specific flags for non-debug
purposes.
Also, whether it's valid to perform some optimizations is something
that the source language rules should dictate, not something the user
should control. Exposing such flag is dangerous as people could just
add `-mllvm -remove-my-loops` with any frontend and then complain the
semantic of their code is not preserving. In some sense they are
shooting themselves in the foot, but I'm under the impression that
flags shouldn't really change the semantic (although some do, e.g.
-ffast-math, which many regret).
> BTW if the other proposal passes can we basically assume that if a loop
doesn’t have the sideeffect intrinsic in it is then removable?
>
The patch as far as I can tell blocks some optimizations in presence
of the intrinsic. The intrinsic itself doesn't really lower to
anything, as far as I can tell. I'm not sure the semantic has settled
down (and I still need to digest the whole proposal).
> That patch seems to suggest that in its current state llvm is mostly broken
for languages that consider all infinite loops as unremovable ... (but I didn’t
read all the discussion)
>
I think at least Rust (and maybe Java? but don't quote me on that) are
broken.
https://github.com/rust-lang/rust/issues/42009
The original bugzilla for this issue has 3 digits which says a lot
about how old the problem is :)
https://bugs.llvm.org//show_bug.cgi?id=965

Thanks,

--
Davide

> On Sep 29, 2017, at 9:02 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> 
> On 09/29/2017 10:02 PM, Marcello Maggioni via llvm-dev wrote:
>> I see the usecase for mixed language compilation (that’s probably why
you fancy something like the side-effect thing instead right?)
> 
> It's also about not having parameterized semantics for the IR. I'd
certainly find that undesirable. We could make it part of datalayout, or
similar, but that has problems with mixed-language compilation. It also has
problems with C, where we generally get to assume that loops terminate, but
loops with a constant controlling condition (at the source level) can be
infinite. Whether or not something is a constant condition at the source level
is something that we need the frontend to mark only for specific loops.
> 
>> 
>> BTW if the other proposal passes can we basically assume that if a loop
doesn’t have the sideeffect intrinsic in it is then removable?
> 
> If it does not have the sideeffect intrinsic, or some other actual side
effect (or atomic, etc.), then yes.
> 
Ok, great, that seems to match with my original understanding then!
>> 
>> That patch seems to suggest that in its current state llvm is mostly
broken for languages that consider all infinite loops as unremovable ... (but I
didn’t read all the discussion)
> 
> As I understand it, it is broken in places, but we also don't take
advantage of assuming that loops terminate as much as we could (assuming we
fully commit to that assumption).
> 
Yeah, that’s what I meant with “mostly”, but probably it would have been better
“sometimes” :P

Thanks!
Marcello
> -Hal
> 
>> 
>> Marcello
>> 
>> Sent from my iPhone
>> 
>>> On Sep 29, 2017, at 7:43 PM, Davide Italiano <davide at
freebsd.org> wrote:
>>> 
>>> On Fri, Sep 29, 2017 at 7:17 PM, Marcello Maggioni via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>>> Hello!
>>>> 
>>>> I read a bunch of discussions about the matter on this very
mailing-list
>>>> that are relatively recent or relatively old and I couldn’t
find much
>>>> agreement on the matter, so … here again :D
>>>> 
>>>> LoopDeletion and infinite loops …
>>>> 
>>>> Currently LoopDeletion bails if non-detectable trip count loops
are
>>>> encountered and that’s fine, there are languages where infinite
loops
>>>> without side effects cannot be removed.
>>>> 
>>>> If I read the C++ spec right though N4527 (sec 1.10)  point 27
says:
>>>> 
>>>> 27  The implementation may assume that any thread will
eventually do one of
>>>> the following:
>>>> 
>>>> 27.1 — terminate,
>>>> 
>>>> 27.2 — make a call to a library I/O function
>>>> 
>>>> (27.3)— read or modify a volatile object, or
>>>> 
>>>> (27.4)— perform a synchronization operation or an atomic
operation.
>>>> 
>>>> [Note: This is intended to allow compiler transformations such
as removal of
>>>> empty loops, even when
>>>> 
>>>> termination cannot be proven. — end note ]
>>>> 
>>>> 
>>>> So, the spec seems to be explicitly calling out that removing
infinite loops
>>>> is ok unless they do any of the things mentioned there (at
least that is my
>>>> interpretation, is that correct?).
>>>> 
>>>> 
>>>> If that is the case we could be missing out for languages that
have such a
>>>> behavior (and in particular in C++).
>>>> 
>>>> I was wondering how it would be viewed the possibility of
adding a flag to
>>>> loop deletion that allows the removal of loops with loop counts
that are not
>>>> SCEVable.
>>>> 
>>> You probably have seen it, but, for reference
>>> https://reviews.llvm.org/D38336 (which goes in the exact opposite
direction).
>>> 
>>> I don't necessarily fancy the idea of having a flag, instead,
maybe,
>>> the frontend could emit enough information to tell the optimizer
>>> whether it is safe to remove the loop?
>>> 
>>> Thanks,
>>> 
>>> --
>>> Davide
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171002/c9ddd130/attachment.html>

> On Sep 29, 2017, at 9:34 PM, Davide Italiano <davide at freebsd.org>
wrote:
> 
> On Fri, Sep 29, 2017 at 8:02 PM, Marcello Maggioni <mmaggioni at
apple.com> wrote:
>> I see the usecase for mixed language compilation (that’s probably why
you fancy something like the side-effect thing instead right?)
>> 
> 
> That could be a reason, but it wasn't my main motivation. Basically
> I'm worried about having per-passes specific flags for non-debug
> purposes.
> Also, whether it's valid to perform some optimizations is something
> that the source language rules should dictate, not something the user
> should control. Exposing such flag is dangerous as people could just
> add `-mllvm -remove-my-loops` with any frontend and then complain the
> semantic of their code is not preserving. In some sense they are
> shooting themselves in the foot, but I'm under the impression that
> flags shouldn't really change the semantic (although some do, e.g.
> -ffast-math, which many regret).
Yeah, I totally understand your point and is valid. Considering the work that is
being done in the other patch it totally makes sense to wait for that to be done
and then “fix” LoopDeletion to allow
non-sideeffected infinite loops to be removed … unless some other issues arise
with that.

Thanks,
Marcello
> 
>> BTW if the other proposal passes can we basically assume that if a loop
doesn’t have the sideeffect intrinsic in it is then removable?
>> 
> 
> The patch as far as I can tell blocks some optimizations in presence
> of the intrinsic. The intrinsic itself doesn't really lower to
> anything, as far as I can tell. I'm not sure the semantic has settled
> down (and I still need to digest the whole proposal).
> 
>> That patch seems to suggest that in its current state llvm is mostly
broken for languages that consider all infinite loops as unremovable ... (but I
didn’t read all the discussion)
>> 
> 
> I think at least Rust (and maybe Java? but don't quote me on that) are
broken.
> https://github.com/rust-lang/rust/issues/42009
> The original bugzilla for this issue has 3 digits which says a lot
> about how old the problem is :)
> https://bugs.llvm.org//show_bug.cgi?id=965
> 
> Thanks,
> 
> --
> Davide