[llvm-dev] GlobalISel: Very limited pattern matching?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

[llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
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.

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
+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 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.

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 <[hidden email]> 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.

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
Hi Quentin,

Thank you for the peace of mind, it was really hard to know I hadn't missed an "EnableConstantFolding=1" line somewhere.

I'll apply a dirty hack at my end to make it work - there's quite a bit of legalization on this target.

Another quick one if I may. Is there a better Legalizer-like pass for reducing constant ranges? I find if I have a call at the top of a single-basic-block function, the register allocator will use every single callee-saved reg to store constants across the function call necessitating a heap of spilling. I note the Legalizer is described as only really being useful on allocators that do not rematerialize, but none of the register allocators I've tried seem to attempt to reduce callee-saved-spilling by narrowing constant ranges. The Legalizer itself also does not move within the same basic block, so it does nothing to prevent this problem either

Missing a pass/setting, or is this for future improvement?

Cheers!

----- Original Message -----
From:
"Quentin Colombet" <[hidden email]>

To:
<[hidden email]>
Cc:
"llvm-dev" <[hidden email]>, "Daniel Sanders" <[hidden email]>, "Amara Emerson" <[hidden email]>, "Matt Arsenault" <[hidden email]>, "Aditya Nandakumar" <[hidden email]>, "Volkan Keles" <[hidden email]>, "Jessica Paquette" <[hidden email]>
Sent:
Mon, 20 May 2019 10:04:56 -0700
Subject:
Re: [llvm-dev] GlobalISel: Very limited pattern matching?


+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 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.

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 <[hidden email]> 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.

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev


On May 20, 2019, at 10:04, Quentin Colombet <[hidden email]> 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 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 <[hidden email]> 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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev


On May 20, 2019, at 11:58 AM, Daniel Sanders <[hidden email]> wrote:



On May 20, 2019, at 10:04, Quentin Colombet <[hidden email]> 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 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 <[hidden email]> 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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev


On May 20, 2019, at 11:19, via llvm-dev <[hidden email]> wrote:

Hi Quentin,

Thank you for the peace of mind, it was really hard to know I hadn't missed an "EnableConstantFolding=1" line somewhere.

I'll apply a dirty hack at my end to make it work - there's quite a bit of legalization on this target.

Another quick one if I may. Is there a better Legalizer-like pass for reducing constant ranges? I find if I have a call at the top of a single-basic-block function, the register allocator will use every single callee-saved reg to store constants across the function call necessitating a heap of spilling. I note the Legalizer is described as only really being useful on allocators that do not rematerialize, but none of the register allocators I've tried seem to attempt to reduce callee-saved-spilling by narrowing constant ranges. The Legalizer itself also does not move within the same basic block, so it does nothing to prevent this problem either

Missing a pass/setting, or is this for future improvement?

The constants being in the first block is part of a memory optimization to minimize the number of duplicate constants. The intent is that since matches can reach across blocks, they are effectively sunk by a successful match and hopefully end up dead as a result. If that doesn't happen then we'll rely on other MIR passes sinking them to sensible places. Off-hand, I'm not sure which pass normally does the sinking of the remaining constants. I think it's probably RegisterCoalescer or something along those lines

Cheers!

----- Original Message -----
From:
"Quentin Colombet" <[hidden email]>

To:
<[hidden email]>
Cc:
"llvm-dev" <[hidden email]>, "Daniel Sanders" <[hidden email]>, "Amara Emerson" <[hidden email]>, "Matt Arsenault" <[hidden email]>, "Aditya Nandakumar" <[hidden email]>, "Volkan Keles" <[hidden email]>, "Jessica Paquette" <[hidden email]>
Sent:
Mon, 20 May 2019 10:04:56 -0700
Subject:
Re: [llvm-dev] GlobalISel: Very limited pattern matching?


+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 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.

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 <[hidden email]> 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.

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev


On May 20, 2019, at 11:19 AM, [hidden email] wrote:

Hi Quentin,

Thank you for the peace of mind, it was really hard to know I hadn't missed an "EnableConstantFolding=1" line somewhere.

I'll apply a dirty hack at my end to make it work - there's quite a bit of legalization on this target.

Another quick one if I may. Is there a better Legalizer-like pass for reducing constant ranges? I find if I have a call at the top of a single-basic-block function, the register allocator will use every single callee-saved reg to store constants across the function call necessitating a heap of spilling. I note the Legalizer is described as only really being useful on allocators that do not rematerialize, but none of the register allocators I've tried seem to attempt to reduce callee-saved-spilling by narrowing constant ranges. The Legalizer itself also does not move within the same basic block, so it does nothing to prevent this problem either

There is the localizer (lib/CodeGen/GlobalISel/Localizer.cpp) that was specifically designed to paper over the limitations of the allocators, but we should definitely come up with a better strategy!
In the meantime, you can add this pass in your pipeline and hopefully you’ll get what you want :)


Missing a pass/setting, or is this for future improvement?

Cheers!

----- Original Message -----
From:
"Quentin Colombet" <[hidden email]>

To:
<[hidden email]>
Cc:
"llvm-dev" <[hidden email]>, "Daniel Sanders" <[hidden email]>, "Amara Emerson" <[hidden email]>, "Matt Arsenault" <[hidden email]>, "Aditya Nandakumar" <[hidden email]>, "Volkan Keles" <[hidden email]>, "Jessica Paquette" <[hidden email]>
Sent:
Mon, 20 May 2019 10:04:56 -0700
Subject:
Re: [llvm-dev] GlobalISel: Very limited pattern matching?


+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 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.

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 <[hidden email]> 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.

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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] GlobalISel: Very limited pattern matching?

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev


On May 20, 2019, at 12:54, Quentin Colombet <[hidden email]> wrote:



On May 20, 2019, at 11:58 AM, Daniel Sanders <[hidden email]> wrote:



On May 20, 2019, at 10:04, Quentin Colombet <[hidden email]> 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 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 <[hidden email]> 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
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev