llvm dev - May 2019 - GlobalISel: Very limited pattern matching?

> On May 20, 2019, at 10:04, Quentin Colombet <qcolombet at apple.com>
wrote:
> 
> +gisel folks
> 
> Hi Alex,
> 
> You’re doing the right thing.
> That’s a known limitation that we’ve discussed in
https://reviews.llvm.org/D59227 <https://reviews.llvm.org/D59227> but we
didn’t really reach a conclusion back them.
> Short term, I believe you’re right, we should patch up the GISel emitter to
use getConstantVRegVal instead of looking directly for G_CONSTANT.
That's not as easy as you make it sound :-) but let's suppose we can
recognize enough of the underlying pattern to be able to use
getConstantVRegVal() instead of needing to do a direct translation of the
SelectionDAG pattern. In the SelectionDAG patterns an ImmLeaf is an `imm` node
with arbitrary C++ predicate(s) attached. There's no practical way to
programatically fold a sext/zext/trunc node into the arbitrary C++ code to allow
it to match a plain G_CONSTANT, as well as a zexted/sexted/trunced G_CONSTANT.
For example, `isUInt<16>(Imm)` will fail if you want it to match (sext
(imm):<<Predicate>>) as if it were (sext
(imm)):<<Predicate>> because there's no way to understand that
we need to replace the isUInt<16> with isInt<16> when we hoist the
predicate up.
> Long term, this is something we need to discuss. I personally think that we
shouldn’t consider G_CONSTANT as true instructions and we should always extend
them in place, but this is not a generally belief.
> 
> Cheers,
> -Quentin
> 
>> On May 20, 2019, at 5:49 AM, via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> 
>> Hi all,
>> 
>> I'm trying to get GlobalISel up and running on an off-tree
architecture and am thinking I must be doing something wrong, given by how few
things actually work.
>> 
>> Namely, any ImmLeaf<> pattern will fail to match if there is a
(TRUNC/ZEXT/SEXT) applied to the constant operand, all of which are commonly
created through Legalization. This is due to G_CONSTANT being explicitly looked
for by the tablegened code, rather than code that makes use of
getConstantVRegVal.
As Quentin notes, getConstantVRegVal() can't look through trunc/zext/sext
either so that change by itself wouldn't resolve the issue by itself. The
main issue here is that the the SelectionDAG pattern importer is following the
semantics of SelectionDAG patterns which in this case is that each node in the
pattern (after expanding PatFrag) corresponds to a SelectionDAG node. If the
patterns rely on optimizations happening prior to instruction selection then
those either same optimizations need implementing or the patterns need extending
to support the additional cases. At the moment, it's fairly common to have
some C++ instruction selection or additional patterns (usually C++ as many of
the targets pre-date the SelectionDAG importer) filling in the gaps in the
imported rules.

There's fairly limited support for constant folding at the moment.
There's a ConstantFoldingMIRBuilder which folds when instructions are
created and a CSEMIRBuilder which also constant folds at the same time as
CSE'ing. I just had a quick look at them and it seems we only constant fold
binary operations. I just asked Aditya (who added it) about this and the main
issue is identifying that a new G_CONSTANT is legal for unary operations that
change the type of the constant like G_ZEXT/G_SEXT/G_TRUNC.
>> Is there supposed to be a constant folding pass before Instruction
Selection? CSE does not fold past unaries applied to operands, I'm surely
missing a pass somewhere...
>> 
>> Thanks,
>> - Alex Davies
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto: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/20190520/cf23280d/attachment.html>

> On May 20, 2019, at 11:58 AM, Daniel Sanders <daniel_l_sanders at
apple.com> wrote:
> 
> 
> 
>> On May 20, 2019, at 10:04, Quentin Colombet <qcolombet at apple.com
<mailto:qcolombet at apple.com>> wrote:
>> 
>> +gisel folks
>> 
>> Hi Alex,
>> 
>> You’re doing the right thing.
>> That’s a known limitation that we’ve discussed in
https://reviews.llvm.org/D59227 <https://reviews.llvm.org/D59227> but we
didn’t really reach a conclusion back them.
>> Short term, I believe you’re right, we should patch up the GISel
emitter to use getConstantVRegVal instead of looking directly for G_CONSTANT.
> 
> That's not as easy as you make it sound :-) but let's suppose we
can recognize enough of the underlying pattern to be able to use
getConstantVRegVal() instead of needing to do a direct translation of the
SelectionDAG pattern. In the SelectionDAG patterns an ImmLeaf is an `imm` node
with arbitrary C++ predicate(s) attached. There's no practical way to
programatically fold a sext/zext/trunc node into the arbitrary C++ code to allow
it to match a plain G_CONSTANT, as well as a zexted/sexted/trunced G_CONSTANT.
For example, `isUInt<16>(Imm)` will fail if you want it to match (sext
(imm):<<Predicate>>) as if it were (sext
(imm)):<<Predicate>> because there's no way to understand that
we need to replace the isUInt<16> with isInt<16> when we hoist the
predicate up.
I was naively thinking we could replace any check of G_CONSTANT with
getConstantVRegValWithLookThrough, but indeed, I have no idea what it would take
:).
> 
>> Long term, this is something we need to discuss. I personally think
that we shouldn’t consider G_CONSTANT as true instructions and we should always
extend them in place, but this is not a generally belief.
>> 
>> Cheers,
>> -Quentin
>> 
>>> On May 20, 2019, at 5:49 AM, via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>> 
>>> Hi all,
>>> 
>>> I'm trying to get GlobalISel up and running on an off-tree
architecture and am thinking I must be doing something wrong, given by how few
things actually work.
>>> 
>>> Namely, any ImmLeaf<> pattern will fail to match if there is
a (TRUNC/ZEXT/SEXT) applied to the constant operand, all of which are commonly
created through Legalization. This is due to G_CONSTANT being explicitly looked
for by the tablegened code, rather than code that makes use of
getConstantVRegVal.
> 
> As Quentin notes, getConstantVRegVal() can't look through
trunc/zext/sext
But getConstantVRegValWithLookThrough can (with the right arguments, IIRC).
> either so that change by itself wouldn't resolve the issue by itself.
The main issue here is that the the SelectionDAG pattern importer is following
the semantics of SelectionDAG patterns which in this case is that each node in
the pattern (after expanding PatFrag) corresponds to a SelectionDAG node. If the
patterns rely on optimizations happening prior to instruction selection then
those either same optimizations need implementing or the patterns need extending
to support the additional cases. At the moment, it's fairly common to have
some C++ instruction selection or additional patterns (usually C++ as many of
the targets pre-date the SelectionDAG importer) filling in the gaps in the
imported rules.
> 
> There's fairly limited support for constant folding at the moment.
There's a ConstantFoldingMIRBuilder which folds when instructions are
created and a CSEMIRBuilder which also constant folds at the same time as
CSE'ing. I just had a quick look at them and it seems we only constant fold
binary operations. I just asked Aditya (who added it) about this and the main
issue is identifying that a new G_CONSTANT is legal for unary operations that
change the type of the constant like G_ZEXT/G_SEXT/G_TRUNC.
> 
>>> Is there supposed to be a constant folding pass before Instruction
Selection? CSE does not fold past unaries applied to operands, I'm surely
missing a pass somewhere...
>>> 
>>> Thanks,
>>> - Alex Davies
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<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/20190520/2c17118a/attachment.html>

> On May 20, 2019, at 12:54, Quentin Colombet <qcolombet at apple.com>
wrote:
> 
> 
> 
>> On May 20, 2019, at 11:58 AM, Daniel Sanders <daniel_l_sanders at
apple.com <mailto:daniel_l_sanders at apple.com>> wrote:
>> 
>> 
>> 
>>> On May 20, 2019, at 10:04, Quentin Colombet <qcolombet at
apple.com <mailto:qcolombet at apple.com>> wrote:
>>> 
>>> +gisel folks
>>> 
>>> Hi Alex,
>>> 
>>> You’re doing the right thing.
>>> That’s a known limitation that we’ve discussed in
https://reviews.llvm.org/D59227 <https://reviews.llvm.org/D59227> but we
didn’t really reach a conclusion back them.
>>> Short term, I believe you’re right, we should patch up the GISel
emitter to use getConstantVRegVal instead of looking directly for G_CONSTANT.
>> 
>> That's not as easy as you make it sound :-) but let's suppose
we can recognize enough of the underlying pattern to be able to use
getConstantVRegVal() instead of needing to do a direct translation of the
SelectionDAG pattern. In the SelectionDAG patterns an ImmLeaf is an `imm` node
with arbitrary C++ predicate(s) attached. There's no practical way to
programatically fold a sext/zext/trunc node into the arbitrary C++ code to allow
it to match a plain G_CONSTANT, as well as a zexted/sexted/trunced G_CONSTANT.
For example, `isUInt<16>(Imm)` will fail if you want it to match (sext
(imm):<<Predicate>>) as if it were (sext
(imm)):<<Predicate>> because there's no way to understand that
we need to replace the isUInt<16> with isInt<16> when we hoist the
predicate up.
> 
> I was naively thinking we could replace any check of G_CONSTANT with
getConstantVRegValWithLookThrough, but indeed, I have no idea what it would take
:).
Mutating the C++ is the only insurmountable problem that I can think of. The
others are just tricky. The biggest of the tricky problems is probably linking
the operand renderers up to the matched operands. We currently do it by
recording the visited instructions and then referencing the matched operands by
instruction id and operand index but that only works if the state machine is the
one that visited the node. If getConstantVRegValWithLookThrough() visits it
outside the view of the state machine then the instruction recorded in the
matcher state isn't the right one and we'd need to resolve that somehow.
>>> Long term, this is something we need to discuss. I personally think
that we shouldn’t consider G_CONSTANT as true instructions and we should always
extend them in place, but this is not a generally belief.
>>> 
>>> Cheers,
>>> -Quentin
>>> 
>>>> On May 20, 2019, at 5:49 AM, via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>>> 
>>>> Hi all,
>>>> 
>>>> I'm trying to get GlobalISel up and running on an off-tree
architecture and am thinking I must be doing something wrong, given by how few
things actually work.
>>>> 
>>>> Namely, any ImmLeaf<> pattern will fail to match if there
is a (TRUNC/ZEXT/SEXT) applied to the constant operand, all of which are
commonly created through Legalization. This is due to G_CONSTANT being
explicitly looked for by the tablegened code, rather than code that makes use of
getConstantVRegVal.
>> 
>> As Quentin notes, getConstantVRegVal() can't look through
trunc/zext/sext
> 
> But getConstantVRegValWithLookThrough can (with the right arguments, IIRC).
Ah, I didn't know about that version. It doesn't look like it's
being used much but it looks like it does get used for simple immediates in
tablegen patterns where there's no arbitrary C++ involved.
>> either so that change by itself wouldn't resolve the issue by
itself. The main issue here is that the the SelectionDAG pattern importer is
following the semantics of SelectionDAG patterns which in this case is that each
node in the pattern (after expanding PatFrag) corresponds to a SelectionDAG
node. If the patterns rely on optimizations happening prior to instruction
selection then those either same optimizations need implementing or the patterns
need extending to support the additional cases. At the moment, it's fairly
common to have some C++ instruction selection or additional patterns (usually
C++ as many of the targets pre-date the SelectionDAG importer) filling in the
gaps in the imported rules.
>> 
>> There's fairly limited support for constant folding at the moment.
There's a ConstantFoldingMIRBuilder which folds when instructions are
created and a CSEMIRBuilder which also constant folds at the same time as
CSE'ing. I just had a quick look at them and it seems we only constant fold
binary operations. I just asked Aditya (who added it) about this and the main
issue is identifying that a new G_CONSTANT is legal for unary operations that
change the type of the constant like G_ZEXT/G_SEXT/G_TRUNC.
>> 
>>>> Is there supposed to be a constant folding pass before
Instruction Selection? CSE does not fold past unaries applied to operands,
I'm surely missing a pass somewhere...
>>>> 
>>>> Thanks,
>>>> - Alex Davies
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<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/20190520/3ac9964e/attachment-0001.html>