[LLVM] Add 3-way comparison intrinsics

Community GSoC
1

Description of the project: 3-way comparisons return the values -1, 0 or 1 depending on whether the values compare lower, equal or greater. They are exposed in C++ via the spaceship operator (operator<=>) and in Rust via the PartialOrd and Ord traits. Currently, such comparisons produce sub-optimal codegen and optimization results in some cases.

The goal of this project is to resolve these optimization issues by implementing new 3-way comparison intrinsics, as described in [RFC] Add 3-way comparison intrinsics. The implementation steps are broadly:

  1. Add the intrinsics to LLVM IR.
  2. Implement legalization/expansion support in SelectionDAG and GlobalISel.
  3. Implement optimization support in ConstantFolding, InstSimplify, InstCombine, CorrelatedValuePropagation, IndVarSimplify, ConstraintElimination, IPSCCP, and other relevant transforms.
  4. Make use of the intrinsics via InstCombine canonicalization or direct emission in clang/rustc.

Adding new target-independent intrinsics is a good way of becoming familiar with a broad slice of LLVM!

Expected results: Support for the intrinsics in the backend and the most important optimization passes. Ideally full integration starting at the frontend.

Desirable skills: Intermediate C++

Project size: Medium or large

Difficulty: Medium

Confirmed Mentors: @nikic, @0xdc03

11 Likes
2

Hello @nikic,
First, Thatā€™s what I was waiting for (Something that covers a broad slice of LLVM).
Recently I Started Contributing to LLVM.
I contributed to InstCombine (@elhewaty on GitHub).

I am interested in this project, I am good at C++, and I also have a good understanding
of compiler optimization theories, and data-flow analysis.
Do you think I can work on this project?
I will start by gathering information about the steps you mentioned above.
Please mention some resources or starting points that I can start with now.

Thanks
Mohamed

3

Probably a good starting point is to look at how the bring-up for some other intrinsics looked like.

For example, here is the initial SelectionDAG support for the (usub|uadd|ssub|sadd).sat intrinsics:

4

Hello @nikic ,

Myself Shourya Goel, An undergrad student pursuing Computer Science. I have a decent understanding of compilers, C++, and system programs. Apart from that I have won several hackathons and contributed to Open source projects like Googleā€™s Zerocopy. I also made my very own language using LLVM a few months back.

Apart from that, I have been busy working on several issues in LLVM and have raised PRs for the same. In general, I have a pretty decent understanding of the codebase now.

This project is quite interesting and would love to work on this. I have started looking into the implementation of other intrinsics and will post any doubts about the same here. For a more practical experience, can you please point me toward any open issues solving which would help me in implementing the required feature?

5

Hey Nikita,
I am working on this issue: Issues Ā· llvm/llvm-project Ā· GitHub

Is there a way I can work on this afterwords: The LLVM Compiler Infrastructure Project

6

Hello,
I am Kiung, a graduate student in Computer Science at Yonsei University, South Korea. I am thrilled to come across such an intriguing project!

As I delve into researching related resources, I find myself filled with curiosity and a few questions arise.

Regarding the discussion on [RFC] Add 3-way comparison intrinsic, itā€™s noted that option 3 is favored for RISC-V architectures. I am interested to know what specific properties of RISC-V lead to this preference. (Is it derived from the lack sophisticated branch prediction mechanisms?)

Furthermore, I anticipate that additional intrinsics might be introduced in the future based on similar considerations. How can I identify instances where the compiler does not fully align with the characteristics of the target hardware like this?

Thanks :slight_smile:

7

This statement is based on a comparison of codegen for some common targets: Compiler Explorer Generally, the difference between the two lowerings tends to be small, itā€™s usually a matter of plus or minus a single instruction.

The special thing about RISCV is that it can directly write a comparison result into a register, which makes for a particularly short slt,slt,sub sequence.

For x86 a separate cmp instruction is necessary first, and if the result is larger than 8 bits, itā€™s also necessary to zero registers first. So for 8 bit results the subtraction form is clearly better, for other sizes itā€™s not so clear. The select form has one less instruction but actually encodes to one byte more.

For aarch64 the select form seems to always be better thanks to the csinv (conditional inverse) instruction.

This is a tricky question. The thing to keep in mind here is that adding an intrinsic for a specific pattern has both advantages and disadvantages. The advantage is that itā€™s very easy to isel / cost model / optimize the pattern. The disadvantage is that it cannot make use of generic optimizations.

For example, for this particular intrinsic, if it is represented using plain instructions, it will automatically benefit from all optimizations that work on comparisons. Once we introduce an intrinsic, it is necessary for us to explicitly apply all those optimizations to the intrinsic as well, it will not happen automatically.

For this reason, we usually prefer to use plain instructions, and then match an instruction sequence to a target specific instruction during isel. (Actually, we go so far as to implement vendor SIMD intrinsics using plain instructions that hopefully get matched back to the correct target instruction, because this allows the compiler to optimize them more.)

Intrinsics only get introduced if there is some specific reason to do so. A common reason is that patterns fail to be preserved until the backend due to optimizations. A commonality between all the major integer intrinsics that have been introduced in recent years (saturating add/sub, min/max, abs) is that they were previously represented using icmp+select patterns. Such patterns are particularly susceptible to being optimized in ways that break pattern recognition.

2 Likes
8

Hi @nikic ,
Iā€™m Hongyu Chen (@XChy on Github), an undergraduate student in Nanjing University, China. Iā€™m interested in this project and passionate to create an intrinsic from scratch.

Iā€™m interested in middle-end optimization and have worked on LLVM in my free time for about half a year. And Iā€™m learning about ISel/DAG and something close to backend.

Since this intrinsic is not very orthogonal to other integer instructions, we may come across regression frequently when bringing up this intrinsic. Obivously itā€™s important to implement optimizations for it.

However, Iā€™m wondering why we implement optimization support before implementing canonicalization/direct-emission of the intrinsic. My first thought is to raise a pending patch for canonicalization firstly and then look into regression. And after resolving the regression, the pending patch can then be merged.

Or how can I know the cases where I need to optimize the intrinsic, before canonicalizing the intrinsics indeed?

Thanks

9

We should implement optimizations before we merge any canonicalization changes, but itā€™s of course fine to implement canonicalization earlier for testing purposes.

If you look at previous intrinsic canonicalizations like āš™ D98152 [InstCombine] Canonicalize SPF to min/max intrinsics, these basically start out by reviewing all the test changes for regressions, and then fixing regressions and rebasing the patch until everything is addressed. For the 3-way comparison intrinsics, I donā€™t think we have much in-tree test coverage, and probably have to rely more on external coverage like llvm-opt-benchmark.

A good chunk of the optimization work will be simple parity with icmp optimizations though (that is, passes that can optimize icmp to true/false should also optimize the intrinsics to -1/0/1), and we donā€™t really need regression analysis to identify most of these cases.

2 Likes
10

Hello @nikic ! :wave: Iā€™m also interested in this project.

Iā€™ve put up a draft PR and Iā€™ve been chipping away at the project now.

Feedback very much welcome - Iā€™m pretty sure Iā€™m running into all the walls headfirst.

11

Hello @nikic
I am interested in project.
I have decent experience coding in c++ and took a rudimentary compiler course in my college. The course was more focused on front-end though and I didnā€™t have any exposure to LLVM yet. Do you I would be eligible to work on this project as a complete new beginner? If so, where should I start? I am currently going through some materials mentioned in Beginner Resources + Documentation

Thank you very much

12

Generally speaking, I think this project is suitable for beginners, as youā€™ll naturally learn about all the important parts of LLVM along the way. Having said that, it seems like there is a lot of interest in this project, and having some prior contribution to LLVM is often a deciding factor in such cases.

Next to the resources you linked, the only relevant documentation I can think of is The LLVM Target-Independent Code Generator ā€” LLVM 19.0.0git documentation, in particular the ā€œInstruction Selectionā€ section talking about SelectionDAG.

To get started working on LLVM in general, taking a look at good first issues is probably worth a shot.

13

(post deleted by author)

14

Iā€™m sorry but is this the output of a Large Language Model? This GSoC proposal is for a spaceship operator intrinsic that aims to canonicalize the operator so optimization passes can easily recognize it, handle it in their specific scenarios, and, if it survives, pass it through to a target backend for optimal lowering there. There is nothing about packing, as far as I understand, in this GSoC. I get a certain feeling reading that proposal.

15

I thought this project was about adding new intrinsics, and that the <=> operator was an example of one of them. Looking at it again now, I guess that was my misunderstanding. Thanks for the clarification!

16

Hi, @nikic
Iā€™m very interested in this project.
Iā€™m also good at c++ and curious about llvm. But Iā€™m not that familiar with llvm. I just learned about My First Language Frontend with LLVM Tutorial and browsed some documentations about Pass while I have no practical experience in contributing. Do you think Iā€™m suitable for this project? If ok, where should I begin? Same as your reply above?