8-bit and 16-bit arithmetic

newer
Alpha-equivalence for recursive...

Norman Ramsey

28 Oct 2021 28 Oct '21

4:57 p.m.

On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this? (One of my students did some nice work on implementing this transformation with a minimal set of sign-extension and zero-extension operations: https://www.cs.tufts.edu/~nr/pubs/widen.pdf.) Norman

Show replies by date

Carter Schonwald

28 Oct 28 Oct

5:12 p.m.

I think thats done on a per backend basis (though theres been a lot of changes since i last looked at some of the relevent pieces). (i'm actually based in Cambridge MA for the next 1-2 years if you wanna brain storm IRL sometime) On Thu, Oct 28, 2021 at 4:59 PM Norman Ramsey wrote:

...

On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this?

(One of my students did some nice work on implementing this transformation with a minimal set of sign-extension and zero-extension operations: https://www.cs.tufts.edu/~nr/pubs/widen.pdf.)

Norman _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Andreas Klebinger

5:29 p.m.

I think carter has it still right that it happens in the backends. If a new backend doesn't support these we could move this up into Cmm though without much issue I think. Am 28/10/2021 um 23:12 schrieb Carter Schonwald:

...

I think thats done on a per backend basis (though theres been a lot of changes since i last looked at some of the relevent pieces). (i'm actually based in Cambridge MA for the next 1-2 years if you wanna brain storm IRL sometime)

On Thu, Oct 28, 2021 at 4:59 PM Norman Ramsey wrote:

On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this?

(One of my students did some nice work on implementing this transformation with a minimal set of sign-extension and zero-extension operations: https://www.cs.tufts.edu/~nr/pubs/widen.pdf.)

Norman _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Ben Gamari

5:37 p.m.

Norman Ramsey writes:

...

On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this?

(One of my students did some nice work on implementing this transformation with a minimal set of sign-extension and zero-extension operations: https://www.cs.tufts.edu/~nr/pubs/widen.pdf.)

As Carter indicated, this is currently done on a per-backend basis. This could indeed probably be consolidated, although we would want to make sure that in so doing we do not leave easy money on the table: It seems plausible to me that the backend may be able to generate better code than a naive lowering to wide arithmetic might otherwise generate. Cheers, - Ben

Carter Schonwald

6 p.m.

yeah, like, currently the XOR for setting registers to zero trick / code optimization (first implemented in ghc backend by reid barton) is done as part of the pretty printer on X86/AMD_64 targets this and a lot of other easy win peephole optimizations that are platform /target dependent happen in the pretty printer atm I thnk On Thu, Oct 28, 2021 at 5:38 PM Ben Gamari wrote:

...

Norman Ramsey writes:

...
On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this?

(One of my students did some nice work on implementing this transformation with a minimal set of sign-extension and zero-extension operations: https://www.cs.tufts.edu/~nr/pubs/widen.pdf.)

As Carter indicated, this is currently done on a per-backend basis. This could indeed probably be consolidated, although we would want to make sure that in so doing we do not leave easy money on the table: It seems plausible to me that the backend may be able to generate better code than a naive lowering to wide arithmetic might otherwise generate.

Cheers,

- Ben _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Norman Ramsey

29 Oct 29 Oct

1:29 p.m.

...

Norman Ramsey writes:

...
On x86, GHC can translate 8-bit and 16-bit operations directly into the 8-bit and 16-bit machine instructions that the hardware supports. But there are other platforms on which the smallest unit of arithmetic may be 32 or even 64 bits. Is there a central module in GHC that can take care of rewriting 8-bit and 16-bit operations into 32-bit or 64-bit operations? Or is each back end on its own for this?

As Carter indicated, this is currently done on a per-backend basis. This could indeed probably be consolidated, although we would want to make sure that in so doing we do not leave easy money on the table: It seems plausible to me that the backend may be able to generate better code than a naive lowering to wide arithmetic might otherwise generate.

The main opportunity here is the opportunity to leave garbage in the high bits of a machine register---that is, the opportunity to avoid sign extension or zero extension, which on most relevant platforms costs two instructions. The more context you have, the more likely it is that you can allow intermediate results to hold garbage. We built the context using a little type system, which would probably be easiest to apply at a high level: STG or even Core. There may also be opportunities in allowing the back end to decide how to implement "sign extend" and "zero extend," although in my experience these are less likely. (In a quick trawl through the source tree, I didn't find a definition of `PrimOp`, so I don't know whether "sign extend" and "zero extend" are already available as primitives.) Norman

1299

Age (days ago)

1300

Last active (days ago)

List overview

Download

5 comments

4 participants

participants (4)

Andreas Klebinger
Ben Gamari
Carter Schonwald
Norman Ramsey