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

Hi Daniel,

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.

The bottom line is I believe there are too many unknown to go down
that road just yet, but I am not the one doing the work, so your call
:D.

Just my 2c :P.

Cheers,
-Quentin

Le ven. 9 nov. 2018 à 08:36, David Greene via llvm-dev
<llvm-dev at lists.llvm.org> a écrit :
>
> Daniel Sanders via llvm-dev <llvm-dev at lists.llvm.org> writes:
>
> > I've been working on the GlobalISel combiner recently and I'd
like to
> > share the plan for how Combine Rules will be defined in GlobalISel and
> > solicit feedback on it.
>
> This is really great stuff!  I agree with pretty much everything Nicolai
> said, particularly the use of DAGs.  That's seems much more natually
> TableGen-y to me.  Specific comments are below.
>
> But before that, I've been long pained that we have so much duplicated
> code in instcombine and dagcombine.  I know this is way beyond the scope
> of this work but do you think the basic concepts could be applied to
> produce TableGen-generated instcombine passes?  It would be nice to
> re-use many of the rules, for example, except they'd match LLVM IR
> rather than MIR.  As you go about implementation, maybe keep this idea
> in mind?
>
> > Here's a simple example that eliminates a redundant G_TRUNC.
> >
> > def : GICombineRule<(defs root:$D, operand:$S),
> > (match [{MIR %1(s32) = G_ZEXT %S(s8)
> > %D(s16) = G_TRUNC %1(s32) }]),
> > (apply [{MIR %D(s16) = G_ZEXT %S(s8) }])>;
>
> The use of '%' vs. '$' here really threw me for a loop.  I
would have
> expected '$D' and '$S' everywhere.  What's the
significance of '%'
> vs. '$'?  I know MIR uses '%' for names but must that be
the case in
> these match blocks?
>
> Of course if we go with Nicolai's use of DAGs this issue seems to go
> away.
>
> > * defs declares the interface for the rule. The definitions in the
> >   defs section are the glue between the Combine algorithm and the
> >   rule, as well as between the match and apply sections. In this case
> >   we only define the root of the match and that we have a register
> >   variable called $S.
>
> My understanding is that "root" means the sink here, but later in
the
> "upside-down" example, "root" means the source.  It
seems to me the use
> of "root" here is a misnomer/confusing.  I liked Nicolai's
ideas about
> specifying the insert point.  Why do users need to know about
"root" at
> all?  Is there some other special meaning attached to it?
>
>                                -David
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

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"?

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 do agree with you that MIR code blocks seem like the wrong model for 
describing combines.

Cheers,
Nicolai

> 
> The bottom line is I believe there are too many unknown to go down
> that road just yet, but I am not the one doing the work, so your call
> :D.
> 
> Just my 2c :P.
> 
> Cheers,
> -Quentin
> 
> Le ven. 9 nov. 2018 à 08:36, David Greene via llvm-dev
> <llvm-dev at lists.llvm.org> a écrit :
>>
>> Daniel Sanders via llvm-dev <llvm-dev at lists.llvm.org> writes:
>>
>>> I've been working on the GlobalISel combiner recently and
I'd like to
>>> share the plan for how Combine Rules will be defined in GlobalISel
and
>>> solicit feedback on it.
>>
>> This is really great stuff!  I agree with pretty much everything
Nicolai
>> said, particularly the use of DAGs.  That's seems much more
natually
>> TableGen-y to me.  Specific comments are below.
>>
>> But before that, I've been long pained that we have so much
duplicated
>> code in instcombine and dagcombine.  I know this is way beyond the
scope
>> of this work but do you think the basic concepts could be applied to
>> produce TableGen-generated instcombine passes?  It would be nice to
>> re-use many of the rules, for example, except they'd match LLVM IR
>> rather than MIR.  As you go about implementation, maybe keep this idea
>> in mind?
>>
>>> Here's a simple example that eliminates a redundant G_TRUNC.
>>>
>>> def : GICombineRule<(defs root:$D, operand:$S),
>>> (match [{MIR %1(s32) = G_ZEXT %S(s8)
>>> %D(s16) = G_TRUNC %1(s32) }]),
>>> (apply [{MIR %D(s16) = G_ZEXT %S(s8) }])>;
>>
>> The use of '%' vs. '$' here really threw me for a loop.
I would have
>> expected '$D' and '$S' everywhere.  What's the
significance of '%'
>> vs. '$'?  I know MIR uses '%' for names but must that
be the case in
>> these match blocks?
>>
>> Of course if we go with Nicolai's use of DAGs this issue seems to
go
>> away.
>>
>>> * defs declares the interface for the rule. The definitions in the
>>>    defs section are the glue between the Combine algorithm and the
>>>    rule, as well as between the match and apply sections. In this
case
>>>    we only define the root of the match and that we have a register
>>>    variable called $S.
>>
>> My understanding is that "root" means the sink here, but
later in the
>> "upside-down" example, "root" means the source.  It
seems to me the use
>> of "root" here is a misnomer/confusing.  I liked
Nicolai's ideas about
>> specifying the insert point.  Why do users need to know about
"root" at
>> all?  Is there some other special meaning attached to it?
>>
>>                                 -David
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.

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
>