llvm dev - Feb 2020 - Questions about jump threading optimization and what we can do

I am not convinced this is a jump-threading issue, but in the domain
of ScalarEvolution. ScEv would need to find out which of the exits are
taken or whether it loops infinitely. One can see that it exits after
10000 iterations, but ScalarEvolution cannot tell:
https://godbolt.org/z/dCqdvv

Michael

Am Mo., 3. Feb. 2020 um 11:56 Uhr schrieb Karl Rehm <klrehm123 at
gmail.com>:
>
> Well ideally it'd do the same thing as before (with two if statements).
Something like:
> ret i64 4
>
> It's not really about needing to be as good as gcc, it's more that
I wonder why the same concept with just two if-else blocks gets optimized yet
more doesn't.
> An interesting point to make is that I don't think it's jump
threading optimizing the original example fully: https://godbolt.org/z/rGvHJk
>
> -Karl
>
> On Mon, Feb 3, 2020 at 12:29 PM Michael Kruse <llvmdev at
meinersbur.de> wrote:
>>
>> How does the code you would like to have look like? I don't see a
>> relevant difference compared to gcc:
>> https://godbolt.org/z/F-oah4
>> (clang unnecessarily introduces another temporary register, but that
>> seems unrelated)
>>
>> Michael
>>
>> Am So., 2. Feb. 2020 um 18:24 Uhr schrieb Karl Rehm via llvm-dev
>> <llvm-dev at lists.llvm.org>:
>> >
>> > Here's a better example. https://godbolt.org/z/fpTyFS
>> > I don't know what exactly you would need to change in
JumpThreading to improve this, but I'm open to ideas.
>> >
>> > On Sun, Feb 2, 2020 at 12:45 PM Karl Rehm <klrehm123 at
gmail.com> wrote:
>> >>
>> >> Holy crap, I completely missed that. I'm sorry! That's
my fault.
>> >>
>> >> On Sun, Feb 2, 2020 at 12:15 PM Johannes Doerfert
<jdoerfert at anl.gov> wrote:
>> >>>
>> >>> On 01/30, Karl Rehm via llvm-dev wrote:
>> >>> > Since the bug report here:
https://bugs.llvm.org/show_bug.cgi?id=44679 I've
>> >>> > been thinking about cases like it, such as:
https://godbolt.org/z/Fwq8mn
>> >>> >
>> >>> > I wonder what we can do about this in a general
sense. As far as I can
>> >>> > tell, the jump threading algorithm is *really*
conservative, which is one
>> >>> > reason this isn't working as well as I'd
hope; however, we don't want to
>> >>> > produce irreducible control flow that the other
passes would work less
>> >>> > effectively on. Thoughts?
>> >>>
>> >>> I'm confused. In your godbold link you run it with O0
which disables
>> >>> almost all transformations. If we take the IR, remove the
optnone
>> >>> attribute, run mem2reg and jump-threading we get what I
think is
>> >>> reasonable:
>> >>>   https://godbolt.org/z/u3fcTZ
>> >>>
>> >>> Please correct me if I misunderstand anything here.
>> >>>
>> >>> Cheers,
>> >>>   Johannes
>> >
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Ah, I see. I think there's something else going on here too, though.
https://godbolt.org/z/dCqdvv is optimized away but ScEv doesn't know
whether this loop terminates either.

On Mon, Feb 3, 2020 at 1:36 PM Michael Kruse <llvmdev at meinersbur.de>
wrote:
> I am not convinced this is a jump-threading issue, but in the domain
> of ScalarEvolution. ScEv would need to find out which of the exits are
> taken or whether it loops infinitely. One can see that it exits after
> 10000 iterations, but ScalarEvolution cannot tell:
> https://godbolt.org/z/dCqdvv
>
> Michael
>
> Am Mo., 3. Feb. 2020 um 11:56 Uhr schrieb Karl Rehm <klrehm123 at
gmail.com>:
> >
> > Well ideally it'd do the same thing as before (with two if
statements).
> Something like:
> > ret i64 4
> >
> > It's not really about needing to be as good as gcc, it's more
that I
> wonder why the same concept with just two if-else blocks gets optimized yet
> more doesn't.
> > An interesting point to make is that I don't think it's jump
threading
> optimizing the original example fully: https://godbolt.org/z/rGvHJk
> >
> > -Karl
> >
> > On Mon, Feb 3, 2020 at 12:29 PM Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
> >>
> >> How does the code you would like to have look like? I don't
see a
> >> relevant difference compared to gcc:
> >> https://godbolt.org/z/F-oah4
> >> (clang unnecessarily introduces another temporary register, but
that
> >> seems unrelated)
> >>
> >> Michael
> >>
> >> Am So., 2. Feb. 2020 um 18:24 Uhr schrieb Karl Rehm via llvm-dev
> >> <llvm-dev at lists.llvm.org>:
> >> >
> >> > Here's a better example. https://godbolt.org/z/fpTyFS
> >> > I don't know what exactly you would need to change in
JumpThreading
> to improve this, but I'm open to ideas.
> >> >
> >> > On Sun, Feb 2, 2020 at 12:45 PM Karl Rehm <klrehm123 at
gmail.com>
> wrote:
> >> >>
> >> >> Holy crap, I completely missed that. I'm sorry!
That's my fault.
> >> >>
> >> >> On Sun, Feb 2, 2020 at 12:15 PM Johannes Doerfert
<jdoerfert at anl.gov>
> wrote:
> >> >>>
> >> >>> On 01/30, Karl Rehm via llvm-dev wrote:
> >> >>> > Since the bug report here:
> https://bugs.llvm.org/show_bug.cgi?id=44679 I've
> >> >>> > been thinking about cases like it, such as:
> https://godbolt.org/z/Fwq8mn
> >> >>> >
> >> >>> > I wonder what we can do about this in a general
sense. As far as
> I can
> >> >>> > tell, the jump threading algorithm is *really*
conservative,
> which is one
> >> >>> > reason this isn't working as well as I'd
hope; however, we don't
> want to
> >> >>> > produce irreducible control flow that the other
passes would work
> less
> >> >>> > effectively on. Thoughts?
> >> >>>
> >> >>> I'm confused. In your godbold link you run it
with O0 which disables
> >> >>> almost all transformations. If we take the IR, remove
the optnone
> >> >>> attribute, run mem2reg and jump-threading we get what
I think is
> >> >>> reasonable:
> >> >>>   https://godbolt.org/z/u3fcTZ
> >> >>>
> >> >>> Please correct me if I misunderstand anything here.
> >> >>>
> >> >>> Cheers,
> >> >>>   Johannes
> >> >
> >> > _______________________________________________
> >> > LLVM Developers mailing list
> >> > llvm-dev at lists.llvm.org
> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200203/a24ddff0/attachment.html>

Wait, you used the same example as I did. I'm confused then; if ScEv is
having troubles but it still gets optimized away somewhere, what do you
think is doing it?

On Mon, Feb 3, 2020 at 2:16 PM Karl Rehm <klrehm123 at gmail.com> wrote:
> Ah, I see. I think there's something else going on here too, though.
> https://godbolt.org/z/dCqdvv is optimized away but ScEv doesn't know
> whether this loop terminates either.
>
> On Mon, Feb 3, 2020 at 1:36 PM Michael Kruse <llvmdev at
meinersbur.de>
> wrote:
>
>> I am not convinced this is a jump-threading issue, but in the domain
>> of ScalarEvolution. ScEv would need to find out which of the exits are
>> taken or whether it loops infinitely. One can see that it exits after
>> 10000 iterations, but ScalarEvolution cannot tell:
>> https://godbolt.org/z/dCqdvv
>>
>> Michael
>>
>> Am Mo., 3. Feb. 2020 um 11:56 Uhr schrieb Karl Rehm <klrehm123 at
gmail.com
>> >:
>> >
>> > Well ideally it'd do the same thing as before (with two if
statements).
>> Something like:
>> > ret i64 4
>> >
>> > It's not really about needing to be as good as gcc, it's
more that I
>> wonder why the same concept with just two if-else blocks gets optimized
yet
>> more doesn't.
>> > An interesting point to make is that I don't think it's
jump threading
>> optimizing the original example fully: https://godbolt.org/z/rGvHJk
>> >
>> > -Karl
>> >
>> > On Mon, Feb 3, 2020 at 12:29 PM Michael Kruse <llvmdev at
meinersbur.de>
>> wrote:
>> >>
>> >> How does the code you would like to have look like? I
don't see a
>> >> relevant difference compared to gcc:
>> >> https://godbolt.org/z/F-oah4
>> >> (clang unnecessarily introduces another temporary register,
but that
>> >> seems unrelated)
>> >>
>> >> Michael
>> >>
>> >> Am So., 2. Feb. 2020 um 18:24 Uhr schrieb Karl Rehm via
llvm-dev
>> >> <llvm-dev at lists.llvm.org>:
>> >> >
>> >> > Here's a better example. https://godbolt.org/z/fpTyFS
>> >> > I don't know what exactly you would need to change in
JumpThreading
>> to improve this, but I'm open to ideas.
>> >> >
>> >> > On Sun, Feb 2, 2020 at 12:45 PM Karl Rehm <klrehm123
at gmail.com>
>> wrote:
>> >> >>
>> >> >> Holy crap, I completely missed that. I'm sorry!
That's my fault.
>> >> >>
>> >> >> On Sun, Feb 2, 2020 at 12:15 PM Johannes Doerfert
<
>> jdoerfert at anl.gov> wrote:
>> >> >>>
>> >> >>> On 01/30, Karl Rehm via llvm-dev wrote:
>> >> >>> > Since the bug report here:
>> https://bugs.llvm.org/show_bug.cgi?id=44679 I've
>> >> >>> > been thinking about cases like it, such as:
>> https://godbolt.org/z/Fwq8mn
>> >> >>> >
>> >> >>> > I wonder what we can do about this in a
general sense. As far as
>> I can
>> >> >>> > tell, the jump threading algorithm is
*really* conservative,
>> which is one
>> >> >>> > reason this isn't working as well as
I'd hope; however, we don't
>> want to
>> >> >>> > produce irreducible control flow that the
other passes would
>> work less
>> >> >>> > effectively on. Thoughts?
>> >> >>>
>> >> >>> I'm confused. In your godbold link you run it
with O0 which
>> disables
>> >> >>> almost all transformations. If we take the IR,
remove the optnone
>> >> >>> attribute, run mem2reg and jump-threading we get
what I think is
>> >> >>> reasonable:
>> >> >>>   https://godbolt.org/z/u3fcTZ
>> >> >>>
>> >> >>> Please correct me if I misunderstand anything
here.
>> >> >>>
>> >> >>> Cheers,
>> >> >>>   Johannes
>> >> >
>> >> > _______________________________________________
>> >> > LLVM Developers mailing list
>> >> > llvm-dev at lists.llvm.org
>> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200203/20294d53/attachment.html>