Re: Matrix Multiplication

[Gautier <Gautier.deMontmollin@maths.unine.ch>]

> It would seem that if the compiler were smart, it would compute I and J
> once and find the position once, then reuse it throughout the loop.

GNAT does reuse adresses. A bright proof in c.l.a (by Samuel Tardieu):

<< [a(b(c,d+e(f,g)).h(i,j)) :=  a(b(c,d+e(f,g)).h(i,j)) + 1;]

Where did you get the impression that the optimizer would miss this? 
 For example, using GNAT, the following expression generates: (ix86 code) 
                           
 t__pXb: movl t__jXb,%edx                             |
         decl %edx                                    |
         movl t__iXb,%eax                             |
         decl %eax                                    |
         leal (%eax,%eax,4),%eax                      |
         sall $3,%eax                                 |
         leal (%eax,%edx,4),%edx                      |
         movl t__gXb,%ecx                             |
         decl %ecx                                    | Address computation
         movl t__fXb,%eax                             |
         decl %eax                                    |
         leal (%eax,%eax,4),%eax                      |
         sall $3,%eax                                 |
         movl t__eXb(%eax,%ecx,4),%eax                |
         addl t__dXb,%eax                             |
         imull $400,%eax,%eax                         |
         leal -400(%edx,%eax),%eax                    |
         imull $4000,t__cXb,%edx                      |
         movl t__bXb-4000(%eax,%edx),%eax             |
         decl %eax                                    |
         incl t__aXb(,%eax,4)            <--- Increment done here!
         ret
                           
 The code used to generate this was: (-O3 -fomit-frame-pointer -gnatp) 
                           
 package T is
   pragma Elaborate_Body;
 end T;
                           
 package body T is
   pragma Warnings (Off); -- Uninitialized variables
                           
   type Two_Ints is array (Integer range <>, Integer range <>) of Integer; 
                           
   type Rec is record
     H : Two_Ints (1 .. 10, 1 .. 10);
   end record;
                           
   type Two_Recs is array (Integer range <>, Integer range <>) of Rec; 
                           
   A : array (1 .. 10) of Integer;
   B : Two_Recs (1 .. 10, 1 .. 10);
   C : Integer;
   D : Integer;
   E : Two_Ints (1 .. 10, 1 .. 10);
   F : Integer;
   G : Integer;
   I : Integer;
   J : Integer;
                           
   procedure P is
     begin
       a(b(c,d+e(f,g)).h(i,j)) :=  a(b(c,d+e(f,g)).h(i,j)) + 1;
     end P;
                           
 end T;

>>

But there are *rare* cases where such "invariants" are not provable as such,
and a renames helps, even with GNAT. On the other side, some Ada 83 compilers
do not seem to optimize these things (Compaq Ada, Alsys).

-- 
Gautier

_____\\________________\_______\_________
http://members.xoom.com/gdemont/gsoft.htm