GlobalISel should have G_POISON

[arsenm]

Currently GlobalISel has G_IMPLICIT_DEF, which acts like undef. This is used to lower both poison and undef from the IR. To mirror the semantics of the IR, we need a separate representation of poison. We should introduce G_POISON to enable better optimizations, particularly when legalization introduces padding vector elements.

This change would mostly be finding all the places G_IMPLICIT_DEF is handled, and equivalently handling G_POISON. We should then migrate vector widening and other transforms to introduce poison instead of undef.

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Matt Arsenault (arsenm)

Currently GlobalISel has G_IMPLICIT_DEF, which acts like `undef`. This is used to lower both `poison` and `undef` from the IR. To mirror the semantics of the IR, we need a separate representation of poison. We should introduce G_POISON to enable better optimizations, particularly when legalization introduces padding vector elements.

This change would mostly be finding all the places G_IMPLICIT_DEF is handled, and equivalently handling G_POISON. We should then migrate vector widening and other transforms to introduce poison instead of undef.

[mtsokol]

Hi! If nobody is assigned to it I can give it a try this week!

[mtsokol]

@arsenm I'm going back with some findings.

• My understanding is that GlobalISel lives on top of SelectionDAG's logic, and relies on SelectionDAGBuilder which is responsible for building a DAG out of LLVM IR.
• There's a mapping of GlobalISel instructions to SelectionDAG instructions link.
• It looks like G_IMPLICIT_DEF, that GlobalISel uses, maps to SelectionDAG's undef. There is no poison instruction in the SelectionDAG's DSL.
• SelectionDAG's instructions are based on SDNode class link.
• The SelectionDAG is build from LLVM IR with a SelectionDAGBuilder.
• LLVM IR has both PoisonValue and UndefValue but in the SelectionDAGBuilder internals both of them are mapped to undef (SDNode) because of UndefValue's classof implementation, as isa<UndefValue>(C), where C is PoisonValue, yields true.
• GlobalISel reuses and relies on SelectionDAGBuilder so my understanding is that it's impossible to get G_POISON into DAG which GlobalISel receives without overhaul of SelectionDAG (and introduction of a new poison SDNode).
• Also, my understanding is that Poison LLVM IR objects are entirely handled at LLVM IR stage, and in SelectionDAG processing and further steps they are already gone (it's still one of my first contributions so I have rather scarce grasp of the whole pipeline).

Does it make sense to:

• introduce a new poison SDNode in the SelectionDAG/Builder domain;
• remove PoisonValueVal from UndefValue's classof, especially that PoisonValue class inherits from UndefValue, not the other way around;
• and treat/lower new poison (in SelectionDAG) and G_POISON (in GlobalISel) the same way as undef is lowered? This way the existing functionality should be retained.

Or is it too disruptive? This extends SelectionDAG functionality and introduces poison constant into target-independent code generation. WDYT? (let me know if I made any fundamental errors in my reasoning, and I expect that the devil is in the details.)

[arsenm]

@arsenm I'm going back with some findings.

• My understanding is that GlobalISel lives on top of SelectionDAG's logic, and relies on SelectionDAGBuilder which is responsible for building a DAG out of LLVM IR.

No, GlobalIsel is not built on top of SelectionDAG. It has no relation to SelectionDAGBuilder. It is still using some pieces of DAG infrastructure as a crutch though.

• There's a mapping of GlobalISel instructions to SelectionDAG instructions link.

That's only for the tablegen patterns.

• It looks like G_IMPLICIT_DEF, that GlobalISel uses, maps to SelectionDAG's undef. There is no poison instruction in the SelectionDAG's DSL.

There should be/ will be (#125883).

• SelectionDAG's instructions are based on SDNode class link.
• The SelectionDAG is build from LLVM IR with a SelectionDAGBuilder.

Yes, but doesn't matter for globalisel.

• GlobalISel reuses and relies on SelectionDAGBuilder so my understanding is that it's impossible to get G_POISON into DAG which GlobalISel receives without overhaul of SelectionDAG (and introduction of a new poison SDNode).

It does not, GlobalISel starts at IRTranslator and does not use SelectionDAGBuilder

• Also, my understanding is that Poison LLVM IR objects are entirely handled at LLVM IR stage, and in SelectionDAG processing and further steps they are already gone (it's still one of my first contributions so I have rather scarce grasp of the whole pipeline).

Poison is an in-progress migration, the DAG work hasn't been done yet. The ideal end state removes undef, and replaces undef uses with freeze poison

Does it make sense to:

• introduce a new poison SDNode in the SelectionDAG/Builder domain;

There's already an open PR to do that, but the globalisel part can be done independently.

• remove PoisonValueVal from UndefValue's classof, especially that PoisonValue class inherits from UndefValue, not the other way around;

You don't need to touch the IR for this

• and treat/lower new poison (in SelectionDAG) and G_POISON (in GlobalISel) the same way as undef is lowered? This way the existing functionality should be retained.

Mechanically the handling of G_POISON will be the same as G_IMPLICIT_DEF

[mtsokol]

Thank you for an explanation! I missed IRTranslator.cpp where LLVM IR is converted to MIR, now I see that it's separate from the SelectionDAG.

I opened a WIP PR here: #127825