Re: Ada on the super (packed arrays)

[Andi Kleen <ak@muc.de>]

mfb@mbunix.mitre.org (Michael F Brenner) writes:

> Mike > Gnat has good optimization. Gnat has good code generation
>      > except for packed arrays. Robert is right about bench
>      > marking your application with ALL of your data before
>      > deciding what is fast and what is slow.
> 
> Robert > Actually, this is probably an over-generalization. 
>        > Packed array stuff is notorious...a good challenge is Matt Weber's
>        
>        >     x := x(1 .. 31) & x(0);
>        
>        > to do a simple rotate. 
> 
> Andi > It is surprising that Gnat doesn't do this. 
>      > At least the C frontend of gcc does a very similar optimization:
> 
>         /* Expects sizeof(unsigned int) == 4 */
>         int rotate(unsigned int i)
>         {return (i << 1) | (i >> 31);}
> 
>         Compiled with -O2 on i386 Linux. Generated this code:
>            rotate:
>              pushl %ebp
>              movl %esp,%ebp
>              movl 8(%ebp),%eax
>              roll $1,%eax
>              ret
> 
> Robert (paraphrased) > [the Weber concatenation is more general than
>                         the integer rotate -- comparable Ada code
>                         would generate comparable assembler code]
> 
> I am trying to confirm this with comparable Ada code as follows:
> 
>     procedure tmp is
>       use interfaces;
>       x, y: unsigned_32 := 42;
>     
>       function rotate (i: unsigned_32) return unsigned_32 is
>       begin
>         return shift_left (i, 1) or shift_right (i, 31);
>       end rotate;
>     
>     begin
>       Y := rotate (x);
>     end tmp;
> 
> Compiling it with the parameters: gcc -c -dak -O3 -gnatn -gnatp tmp.adb
> for maximal optimization, the following code is generated:
> 
> File tmp.adb.sched2:

[...]
> 
> Robert, could you please show me how to rewrite this code and how to compile
> it so that it generates the rotate command instead of the two shifts
> and the OR command, like gcc generates for the C command?

I think the real Ada way would be to use interfaces.Rotate_Left(). The C optimization
is really only a hack to cover the lack of rotate support in C.


with Interfaces; use interfaces;
with Ada.Text_IO; use Ada.Text_IO;

procedure tmp is
   x, y: unsigned_32;

   function Xinit return Unsigned_32 is -- to fool constant propagation (don't use -O3)
   begin
      return 42;
   end;

begin
   X := Xinit;
   Y := Rotate_Left(X, 1);
   Put_Line(Unsigned_32'Image(Y)); -- so that Y is not dead.
end tmp;

Compiled with gcc -S -gnatdb -O2 tmp.ada

	.file	"tmp.ada"
	.version	"01.01"
gcc2_compiled.:
.text
	.align 4
	.type	 tmp__xinit.0,@function
tmp__xinit.0:
	pushl %ebp
	movl %esp,%ebp
	subl $4,%esp
	movl %ecx,-4(%ebp)
	movl $42,%eax
	leave
	ret
.Lfe1:
	.size	 tmp__xinit.0,.Lfe1-tmp__xinit.0
	.align 4
.globl _ada_tmp
	.type	 _ada_tmp,@function
_ada_tmp:
	pushl %ebp
	movl %esp,%ebp
	subl $8,%esp
	pushl %esi
	pushl %ebx
	movl %ebp,%ecx
	call tmp__xinit.0
	movl %eax,%ebx
	rorl $31,%ebx
	call system__secondary_stack__ss_mark
	movl %eax,%esi
	leal -8(%ebp),%edx
	pushl %ebx
	pushl %edx
	call system__img_uns__image_unsigned
	movl -4(%ebp),%edx
	movl -8(%ebp),%ecx
	pushl %edx
	pushl %ecx
	call ada__text_io__put_line__2
	pushl %esi
	call system__secondary_stack__ss_release
	leal -16(%ebp),%esp
	popl %ebx
	popl %esi
	leave
	ret
.Lfe2:
	.size	 _ada_tmp,.Lfe2-_ada_tmp
	.ident	"GCC: (GNU) 2.7.2.1"


-Andi