llvm dev - Nov 2018 - [RFC] Tablegen-erated GlobalISel Combine Rules

Hi Nicolai,

Le ven. 9 nov. 2018 à 09:24, Nicolai Hähnle <nhaehnle at gmail.com> a
écrit :
>
> Hi Quentin,
>
> On 09.11.18 18:16, Quentin Colombet via llvm-dev wrote:
> > Disclaimer: Haven't read the proposal yet.
> >
> >>   TL;DR: We're planning to define GlobalISel Combine Rules
using MIR syntax with a few bits glued on to interface with the algorithm and
escape into C++ when we need to. Eventually, ISel rules may follow suit.
> >
> > I would rather avoid adding a dependency on yet another tablegen
> > backend to the project unless we are confident it is here to stay.
> > At a high level, I am not fan of the proposal because it will box us
> > in a stricter framework that pure C++ that may impede our ability to
> > prototype different approaches quickly. Longer term, I would like to
> > have a common framework to IR and MIR to describe combines and I am
> > afraid that MIR is not the right abstraction for that.
>
> What do you mean by "prototype different approaches quickly"?
I mean exploring different combine strategies :).
With a model we are stuck with what it was designed to express.
For instance, currently with SDISel there are no way to express
something like paired loads, i.e., patterns like this:
load @a, load @a + 4 => loadpair @a

Because the DAGs needs to be single rooted.
In C++ we do whatever we want (I am not saying it is easy ;).)
>
> It's funny, because I always thought the exact opposite: I felt like
> there are constraints in the freedom to explore different approaches
> precisely because the combines are not described declaratively, and too
> much of how everything fits together is de facto hardcoded in C++.
>
> But maybe we mean different things?
I think we meant the same think and I admit I don't see how C++ could
be more constrained than a declarative description that rely on C++
code to be executed :).
I agree that declarative syntax is easier to express and rewrite though.
>
> I do agree with you that MIR code blocks seem like the wrong model for
> describing combines.
>
> Cheers,
> Nicolai
>

On 09.11.18 18:47, Quentin Colombet wrote:
> Le ven. 9 nov. 2018 à 09:24, Nicolai Hähnle <nhaehnle at gmail.com> a
écrit :
>>
>> Hi Quentin,
>>
>> On 09.11.18 18:16, Quentin Colombet via llvm-dev wrote:
>>> Disclaimer: Haven't read the proposal yet.
>>>
>>>>    TL;DR: We're planning to define GlobalISel Combine Rules
using MIR syntax with a few bits glued on to interface with the algorithm and
escape into C++ when we need to. Eventually, ISel rules may follow suit.
>>>
>>> I would rather avoid adding a dependency on yet another tablegen
>>> backend to the project unless we are confident it is here to stay.
>>> At a high level, I am not fan of the proposal because it will box
us
>>> in a stricter framework that pure C++ that may impede our ability
to
>>> prototype different approaches quickly. Longer term, I would like
to
>>> have a common framework to IR and MIR to describe combines and I am
>>> afraid that MIR is not the right abstraction for that.
>>
>> What do you mean by "prototype different approaches quickly"?
> 
> I mean exploring different combine strategies :).
> With a model we are stuck with what it was designed to express.
> For instance, currently with SDISel there are no way to express
> something like paired loads, i.e., patterns like this:
> load @a, load @a + 4 => loadpair @a
> 
> Because the DAGs needs to be single rooted.
> In C++ we do whatever we want (I am not saying it is easy ;).)
Of course that particular example may not be the best since Daniel is 
already talking about multi-root rules ;)

>> It's funny, because I always thought the exact opposite: I felt
like
>> there are constraints in the freedom to explore different approaches
>> precisely because the combines are not described declaratively, and too
>> much of how everything fits together is de facto hardcoded in C++.
>>
>> But maybe we mean different things?
> 
> I think we meant the same think and I admit I don't see how C++ could
> be more constrained than a declarative description that rely on C++
> code to be executed :).
> I agree that declarative syntax is easier to express and rewrite though.
C++ is less restrictive, but that's precisely why it makes it harder to 
do certain experiments :)

I was thinking of experiments along the lines of semi-automatically 
combining rewrite rules for something similar to super-optimization. 
With a declarative description of rewrite rules, you might be able to 
combine them algorithmically to go beyond simple local improvements.

I admit that's a bit speculative, but the point is that if all the rules 
are hidden in C++, there's not even a place to start from.

I'll grant you that there are other kinds of experiments that are easier 
in C++. The proposal does suggest escape hatches for that...

Cheers,
Nicolai
> 
>>
>> I do agree with you that MIR code blocks seem like the wrong model for
>> describing combines.
>>
>> Cheers,
>> Nicolai
>>
-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.

Thanks Quentin!
> On Nov 9, 2018, at 09:47, Quentin Colombet via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi Nicolai,
> 
> Le ven. 9 nov. 2018 à 09:24, Nicolai Hähnle <nhaehnle at gmail.com
<mailto:nhaehnle at gmail.com>> a écrit :
>> 
>> Hi Quentin,
>> 
>> On 09.11.18 18:16, Quentin Colombet via llvm-dev wrote:
>>> Disclaimer: Haven't read the proposal yet.
>>> 
>>>>  TL;DR: We're planning to define GlobalISel Combine Rules
using MIR syntax with a few bits glued on to interface with the algorithm and
escape into C++ when we need to. Eventually, ISel rules may follow suit.
>>> 
>>> I would rather avoid adding a dependency on yet another tablegen
>>> backend to the project unless we are confident it is here to stay.
>>> At a high level, I am not fan of the proposal because it will box
us
>>> in a stricter framework that pure C++ that may impede our ability
to
>>> prototype different approaches quickly. Longer term, I would like
to
>>> have a common framework to IR and MIR to describe combines and I am
>>> afraid that MIR is not the right abstraction for that.
>> 
>> What do you mean by "prototype different approaches quickly"?
> 
> I mean exploring different combine strategies :).
That's actually my motivation for making it (mostly) declarative now rather
than later :-). It's also easier to do it while there's only two rules
rather than letting it build up and having to migrate it to something else.

I have some plans for the Combine algorithm to make it more aware of the impact
of its changes and able to choose not to make a change if it's going to be
harmful to the overall performance. Assuming I can make the plan work,
there's a few nice benefits that come along with it. In particular I want to
be able to pull the apply step away from the match step and look into delaying
the apply until it's seen enough of the MIR to make an informed decision
about the cost/benefit of the apply. While I'm looking into this, others
will start building up the combine library using the current algorithm.
> With a model we are stuck with what it was designed to express.
> For instance, currently with SDISel there are no way to express
> something like paired loads, i.e., patterns like this:
> load @a, load @a + 4 => loadpair @a
> 
> Because the DAGs needs to be single rooted.
> In C++ we do whatever we want (I am not saying it is easy ;).)
This particular case is was one of the ones I was thinking of when I was
thinking about multi-root matches. The same idea that drives the better decision
making should also enable matching of things like ARM's ldm instruction. I
think it should also be able to match non-overlapping operations too.
>> It's funny, because I always thought the exact opposite: I felt
like
>> there are constraints in the freedom to explore different approaches
>> precisely because the combines are not described declaratively, and too
>> much of how everything fits together is de facto hardcoded in C++.
>> 
>> But maybe we mean different things?
> 
> I think we meant the same think and I admit I don't see how C++ could
> be more constrained than a declarative description that rely on C++
> code to be executed :).
> I agree that declarative syntax is easier to express and rewrite though.
> 
>> 
>> I do agree with you that MIR code blocks seem like the wrong model for
>> describing combines.
>> 
>> Cheers,
>> Nicolai
>> 
> _______________________________________________
> 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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181109/a731b6fb/attachment.html>

Le ven. 9 nov. 2018 à 18:47, Daniel Sanders <daniel_l_sanders at
apple.com> a
écrit :
> Thanks Quentin!
>
> On Nov 9, 2018, at 09:47, Quentin Colombet via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>
> What do you mean by "prototype different approaches quickly"?
>
>
> I mean exploring different combine strategies :).
>
>
> That's actually my motivation for making it (mostly) declarative now
> rather than later :-). It's also easier to do it while there's only
two
> rules rather than letting it build up and having to migrate it to something
> else.
>
As soon as we believe we won’t have to rewrite the rules (or anything to be
fair) we already narrowing the options we can try.

I am not saying this is the wrong approach, but we certainly have not
pushed it far enough for me to be confident that pushing a whole table gen
backend behind the mir rules is worth it. If you were scripting around that
and thus being consciously okay to just drop it if it doesn’t work that
would be a different discussion :).

The more we invest into an approach the more difficult it is to move away
from it even if that would be the right thing to do (e.g., SDISel).

Anyway, at the end of the day, you’re the ones doing the work.

> I have some plans for the Combine algorithm to make it more aware of the
> impact of its changes and able to choose not to make a change if it's
going
> to be harmful to the overall performance. Assuming I can make the plan
> work, there's a few nice benefits that come along with it. In
particular I
> want to be able to pull the apply step away from the match step and look
> into delaying the apply until it's seen enough of the MIR to make an
> informed decision about the cost/benefit of the apply. While I'm
looking
> into this, others will start building up the combine library using the
> current algorithm.
>
> With a model we are stuck with what it was designed to express.
> For instance, currently with SDISel there are no way to express
> something like paired loads, i.e., patterns like this:
> load @a, load @a + 4 => loadpair @a
>
> Because the DAGs needs to be single rooted.
> In C++ we do whatever we want (I am not saying it is easy ;).)
>
>
> This particular case is was one of the ones I was thinking of when I was
> thinking about multi-root matches. The same idea that drives the better
> decision making should also enable matching of things like ARM's ldm
> instruction. I think it should also be able to match non-overlapping
> operations too.
>
> It's funny, because I always thought the exact opposite: I felt like
> there are constraints in the freedom to explore different approaches
> precisely because the combines are not described declaratively, and too
> much of how everything fits together is de facto hardcoded in C++.
>
> But maybe we mean different things?
>
>
> I think we meant the same think and I admit I don't see how C++ could
> be more constrained than a declarative description that rely on C++
> code to be executed :).
> I agree that declarative syntax is easier to express and rewrite though.
>
>
> I do agree with you that MIR code blocks seem like the wrong model for
> describing combines.
>
> Cheers,
> Nicolai
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://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/20181109/31f0a0a4/attachment.html>