Shifts of modular type 2**K

General
1

The package Interfaces defines Shift_Left and Shift_Right for built in types like Unsigned_32.

My question is if there is a way to define them for a user modular type. Given:

type T is mod 2**64;
type S is mod 2**128;
X : T;
Y : S;

Is there is a way to beat:

X := T (Y / 2**64);
Y := S (X) * 2**64;

A combination of a representation clause for a record type like

type S_Record is record
   L : T;
   H : T;
end record;
for S_Record use record
   L at  ... -- A quite complicated expression involving Default_Bit_Order;
   H at ...
end record;

and Unchecked_Conversion has a disastrous performance.

Or, maybe, -O3 optimizes / 2 ** 64 and X * 2 ** 64 to shifts already?

2

In GNAT I have been able to define them for some modular types using Import, Convention => Intrinsic. I don’t know the breadth of the sizes it allows for that.

Example:

with Ada.Text_IO; use Ada.Text_IO;

procedure jdoodle is
    type T is mod 2**64;
    type S is mod 2**128;
    
    function Shift_Left(Value : T; Amount : Natural) return T
        with Import, Convention => Intrinsic;
    
    function Shift_Left(Value : S; Amount : Natural) return S
        with Import, Convention => Intrinsic;
        
    v1 : T := 16#000000010#;
    v2 : S := 16#000000010#;
begin
    Put_Line("v1:" & v1'Image);
    Put_Line("v2:" & v2'Image);
    Put_Line("v1:" & Shift_Left(v1,4)'Image);
    Put_Line("v2:" & Shift_Left(v2,5)'Image);
end jdoodle;

Output:

v1: 16
v2: 16
v1: 256
v2: 512
1 Like
3

Thanks, it worked! However shifts are twice slower than multiplication and division. So I stick to them,

4

I tried to follow the path of shift operations through GNAT and gcc’s optimization passes, here’s what I found:

The GNAT frontend tries to simplify modular operations before handing the tree off to gcc utils2.cc

GNAT’s documentation says the Shift and Rotate intrinsics work for 8, 16, 32, or 64 bit values though I believe this to be outdated as your example shows that larger values do work. intrinsic_subprograms.rst

gcc will optimize any divide by a power of 2 to a shift operation. combine.cc

If the shift is larger than a machine word, then GNAT might depend on architecture-specific routines in libgcc. trans.cc

2 Likes
5

Actually performance is basically same, optimization fooled me reducing loop to nothing. The bottom line is that GNAT/gcc indeed do a good job.

1 Like
6

I always recommend people to try out Godbolt. You can select GNAT, with several versions and several architectures available. Then you can take a peak at the asm generated. It is great for learning how compilers optimize and what architectures do behind the scenes. Of course you can also pass different compiler flags :slight_smile:

2 Likes
7

Nice, however x86 Assembly is not my thing.

P.S. I still have a virtual Windows 7 32-bit machine with GNAT GPL installed on it!

8

if it helps, it provides various architectures (ARM assembly for example,others). It’s not just x86

9

As Jere says, there are other arches. I personally like AVR and RISC-V ASM… It is basically what I know :stuck_out_tongue: Though I just saw that there is no AVR compiler in Godbolt, but we have one… We could ask for it to be added ^^