The state-of-art at Instruction selection

Project Infrastructure LLVM Dev List Archives
1

Dear LLVMer

I read the Instruction selection in LLVM recently.
I find the most important two frameworks “SelectionDAG” and “GlobalISel”.
As far as I know, the “SelectionDAG” is the default framework and GlobalISel is ongoing now!

Can someone give some detailed information about the Instruction selection frameworks?
such as（including but not limited to） :

  1. What’s the plan for “GlobalISel” to replace the “SelectionDAG”?
  2. GlobalISel uses its own instruction pattern matcher,
    how will the target instruction description be with tablegen, especially the DAG type in tablegen?
  3. “SelectionDAG” is the framework in the trunk,
    what’s the suggestion to following the upcoming “GlobalISel” if we maintain a downstream project?
  4. Can someone share some detailed docs or design paper except the following docs
    https://llvm.org/docs/GlobalISel/index.html

Thanks.

2

Hi Yao,

Dear LLVMer

I read the Instruction selection in LLVM recently.
I find the most important two frameworks “SelectionDAG” and “GlobalISel”.
As far as I know, the “SelectionDAG” is the default framework and GlobalISel is ongoing now!

Can someone give some detailed information about the Instruction selection frameworks?
such as（including but not limited to） :

  1. What’s the plan for “GlobalISel” to replace the “SelectionDAG”?

The plan is for GlobalISel to replace SelectionDAG in the future. The main hurdle for GlobalISel adoption right now is that the work around providing better tablegen support is progressing at a slow pace.
That’s not a blocker, but that means more hand written code for adopters.

  1. GlobalISel uses its own instruction pattern matcher,
    how will the target instruction description be with tablegen, especially the DAG type in tablegen?

GlobalISel has an importer mechanism that automatically reuse the existing SDISel patterns from tablegen. The importer is not complete though and in particular, some patterns are currently not possible to import or require a bit of help from the developer (see the documentation around GINodeEquiv).

You can see what is currently supported or not for your target by using -debug-only gisel-emitter and -warn-on-skipped-patterns on your tablegen command when generating the selection tables.
This could be improved of course!

As far as describing the types and such, GISel uses LLT. The main place where you have to do that is in the LegalizerInfo where you describe what is and what is not legal. Take a look at llvm/lib/Target/AArch64/GISel/AArch64LegalizerInfo.cpp for example.

Take a look at the tutorial we made a few years ago for more details about how to do the targeting:
2017 LLVM Developers’ Meeting: J. Bogner & A. Nandakumar & D. Sanders “Tutorial: GlobalISel ”

And more recently:
2019 LLVM Developers’ Meeting: V. Keles & D. Sanders “Generating Optimized Code with GlobalISel”

  1. “SelectionDAG” is the framework in the trunk,
    what’s the suggestion to following the upcoming “GlobalISel” if we maintain a downstream project?

I would recommend to use GlobalISel. It is faster, more testable, more flexible, and offers optimization opportunities that are just impossible with SDISel.
The downsides are missing proper tablegen support and it can be rough on the edges since it hasn’t been as widely use yet. Both these downsides will improve as time goes by and as always, patch welcome :).

  1. Can someone share some detailed docs or design paper except the following docs
    https://llvm.org/docs/GlobalISel/index.html

I think the closest thing to a design/spec doc that is not completely out of date is probably this talk:
2016 LLVM Developers’ Meeting: A. Bougacha & Q. Colombet & T. Northover “Global Instr…"

If you have specific questions feel free to reach out.

Cheers,
-Quentin

3

Hi Yao,

Dear LLVMer

I read the Instruction selection in LLVM recently.
I find the most important two frameworks “SelectionDAG” and “GlobalISel”.
As far as I know, the “SelectionDAG” is the default framework and GlobalISel is ongoing now!

Can someone give some detailed information about the Instruction selection frameworks?
such as（including but not limited to） :

  1. What’s the plan for “GlobalISel” to replace the “SelectionDAG”?

The plan is for GlobalISel to replace SelectionDAG in the future. The main hurdle for GlobalISel adoption right now is that the work around providing better tablegen support is progressing at a slow pace.
That’s not a blocker, but that means more hand written code for adopters.

  1. GlobalISel uses its own instruction pattern matcher,
    how will the target instruction description be with tablegen, especially the DAG type in tablegen?

GlobalISel has an importer mechanism that automatically reuse the existing SDISel patterns from tablegen. The importer is not complete though and in particular, some patterns are currently not possible to import or require a bit of help from the developer (see the documentation around GINodeEquiv).

You can see what is currently supported or not for your target by using -debug-only gisel-emitter and -warn-on-skipped-patterns on your tablegen command when generating the selection tables.
This could be improved of course!

As far as describing the types and such, GISel uses LLT. The main place where you have to do that is in the LegalizerInfo where you describe what is and what is not legal. Take a look at llvm/lib/Target/AArch64/GISel/AArch64LegalizerInfo.cpp for example.

Take a look at the tutorial we made a few years ago for more details about how to do the targeting:
2017 LLVM Developers’ Meeting: J. Bogner & A. Nandakumar & D. Sanders “Tutorial: GlobalISel ”

And more recently:
2019 LLVM Developers’ Meeting: V. Keles & D. Sanders “Generating Optimized Code with GlobalISel”

  1. “SelectionDAG” is the framework in the trunk,
    what’s the suggestion to following the upcoming “GlobalISel” if we maintain a downstream project?

I would recommend to use GlobalISel. It is faster, more testable, more flexible, and offers optimization opportunities that are just impossible with SDISel.
The downsides are missing proper tablegen support and it can be rough on the edges since it hasn’t been as widely use yet. Both these downsides will improve as time goes by and as always, patch welcome :).

  1. Can someone share some detailed docs or design paper except the following docs
    https://llvm.org/docs/GlobalISel/index.html

I think the closest thing to a design/spec doc that is not completely out of date is probably this talk:
2016 LLVM Developers’ Meeting: A. Bougacha & Q. Colombet & T. Northover “Global Instr…"

Actually this one may be more accurate:
2017 LLVM Developers’ Meeting: “GlobalISel: Past, Present, and Future ”

4

Hi Yao,

I’m working on a downstream target that was built from the ground up using GlobalISel only. I can definitely confirm what Quentin already said. For us the most challenging part was the legalizer. You have to be careful not to introduce hidden infinite loops through conflicting legalization actions. Also because of some edge-cases that are not fully supported yet, it can sometimes be difficult to come up with a set of actions that can handle anything that is thrown at you or maybe you’ll even find that the current implementation cannot handle the edge-case your target presents. We certainly had to commit some patches in there to make everything work for us. That is something that will be solved the more adopters there are for it. You could say that it is in a working state for the existing upstream targets but if your target is something new, then it will most certainly uncover some edge-case that simply nobody thought of yet.

Don’t let that deter you from using GISel though. The advantages it offers over SelDAG definitely outweigh some of the pitfalls that come with “early” adoption and the amount of testability and flexibility you gain more than makes up for it.

As for TableGen selection support: we found that simple instructions and some of the more “straight-forward” complex ones could easily be done with TableGen. Things like memops or instructions where TableGen has difficulty to infer the correct types, also instructions with more than one definition, we had to do in C++. However none of us had worked with TableGen before and by now we have learned some more tricks that would certainly allow us to migrate more of our C++ patterns to TableGen.

Overall we are pretty happy with GlobalISel and recently I see more and more patches popping up on Phabricator for it. If you are planning to create a new backend, I can definitely recommend GlobalISel!

Cheers,

Dominik