Opened 5 years ago

Closed 4 years ago

Last modified 4 years ago

#9430 closed feature request (fixed)

implement more arithmetic operations natively in the LLVM backend

Reported by: rwbarton Owned by: michalt
Priority: normal Milestone: 8.0.1
Component: Compiler (LLVM) Version: 7.9
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case: primops/should_run/T9430
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

There are a number of arithmetic operations that have native implementations on x86 but use the generic fallback on LLVM. Implementing these with LLVM intrinsics could improve small Integer performance on ARM substantially!

MO_Add2         @llvm.uadd.with.overflow.*
MO_AddIntC      @llvm.sadd.with.overflow.*
MO_SubIntC      @llvm.ssub.with.overflow.*
MO_U_Mul2       mul i64/i128?
MO_U_QuotRem2   udiv i64/i128?

Change History (17)

comment:1 Changed 5 years ago by rwbarton

I probably won't get around to this myself in the near future.

comment:2 Changed 5 years ago by rwbarton

In fact, with these changes it may end up making sense to build integer-gmp with LLVM anywhere we can. (At least if split-objs worked with LLVM: #8300.)

comment:3 Changed 4 years ago by michalt

Owner: set to michalt

This looks like a nice way to learn more about LLVM backend, so I've started working on adding support for: MO_Add2 and MO_{Add,Sub}IntC. I hope to send something out within the next few days.

comment:4 Changed 4 years ago by michalt

Sent out Phab:D991

comment:5 Changed 4 years ago by Ben Gamari <ben@…>

In b1d1c652908ecd7bfcf13cf2e5dd06ac7926992c/ghc:

Support MO_{Add,Sub}IntC and MO_Add2 in the LLVM backend

This includes:

- Adding new LlvmType called LMStructP that represents an unpacked
  struct (this is necessary since LLVM's instructions the
  llvm.sadd.with.overflow.* return an unpacked struct).

- Modifications to LlvmCodeGen.CodeGen to generate the LLVM
  instructions for the primops.

- Modifications to StgCmmPrim to actually use those three instructions
  if we use the LLVM backend (so far they were only used for NCG).

Test Plan: validate

Reviewers: austin, rwbarton, bgamari

Reviewed By: bgamari

Subscribers: thomie, bgamari

Differential Revision: https://phabricator.haskell.org/D991

GHC Trac Issues: #9430

comment:6 Changed 4 years ago by bgamari

It looks like we're still looking for someone to contribute support for MO_U_Mul2 and MO_U_QuotRem2.

comment:7 Changed 4 years ago by michalt

Sorry I wasn't clear in the previous message - I'm actually planning to implement support for the two remaining operations as well (hopefully I'll have some time over the weekend). I just wanted to split the work into two parts since I'm not very familiar with the codebase.

comment:8 Changed 4 years ago by bgamari

Ahh, great! Looking forward to reviewing the next patch.

comment:9 Changed 4 years ago by Ben Gamari <ben@…>

In 82ffc80d/ghc:

LlvmCodeGen: add support for MO_U_Mul2 CallishMachOp

This adds support MO_U_Mul2 to the LLVM backend by simply using 'mul'
instruction but operating at twice the bit width (e.g., for 64 bit
words we will generate mul that operates on 128 bits and then extract
the two 64 bit values for the result of the CallishMachOp).

Test Plan: validate

Reviewers: rwbarton, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1068

GHC Trac Issues: #9430

comment:10 Changed 4 years ago by thomie

Milestone: 7.12.1
Resolution: fixed
Status: newclosed
Test Case: primops/should_run/T9430

comment:11 Changed 4 years ago by michalt

Milestone: 7.12.1
Owner: michalt deleted
Resolution: fixed
Status: closednew

I was also planning to add support for MO_U_QuotRem2 (using udiv and urem), so let's not close this just yet.

comment:12 Changed 4 years ago by michalt

Owner: set to michalt

comment:13 Changed 4 years ago by Ben Gamari <ben@…>

In 92f5385/ghc:

Support MO_U_QuotRem2 in LLVM backend

This adds support for MO_U_QuotRem2 in LLVM backend.  Similarly to
MO_U_Mul2 we use the standard LLVM instructions (in this case 'udiv'
and 'urem') but do the computation on double the word width (e.g., for
64-bit we will do them on 128 registers).

Test Plan: validate

Reviewers: rwbarton, austin, bgamari

Reviewed By: bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1100

GHC Trac Issues: #9430

comment:14 Changed 4 years ago by bgamari

Here is the current state of things as I understand them.

MachOp LLVM construct commit
MO_Add2 @llvm.uadd.with.overflow.* b1d1c652908ecd7bfcf13cf2e5dd06ac7926992c/ghc
MO_AddIntC @llvm.sadd.with.overflow.* b1d1c652908ecd7bfcf13cf2e5dd06ac7926992c/ghc
MO_SubIntC @llvm.ssub.with.overflow.* b1d1c652908ecd7bfcf13cf2e5dd06ac7926992c/ghc
MO_U_Mul2 mul i64/i128? TODO
MO_U_QuotRem2 udiv i64/i128? 92f5385d8b2be50848a2496199a481f299f4b53a/ghc

comment:15 Changed 4 years ago by rwbarton

But MO_U_Mul2 was done in 82ffc80d (comment:9) right?

comment:16 in reply to:  15 Changed 4 years ago by michalt

Resolution: fixed
Status: newclosed

Replying to rwbarton:

But MO_U_Mul2 was done in 82ffc80d (comment:9) right?

Yes, I think the 3 commits now cover all the ops in the ticket (first commit for the llvm.*.with.overflow ones, and then one for each of MO_U_{Mul2,QuotRem2}). So I hope it's ok to close it. :-)

comment:17 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.