Plenty of unnecessary contraint tests (Was: Size code Ada and C)

[pfk@schnecke.offl.uni-jena.de (Frank Klemm)]

robin wrote:
> <snip>
> It's never a good idea in a real-time system to
> avoid run-time checks.  A run-time check on the magnitude
> would have caught the error and would not have caused
> the total failure of Ariane 5.
> <snip>
>
Ada was designed to make it possible to do range checking.

Array index boundary checking is always a good idea, because out-of-boundary
write access is a very bad idea.

Arithmetic boundary checking is problem depending, it is dangerous on
arbitrary set boundaries (i.e. balance of an checking account for non
commercian usage: range -99_999.99 .. 999_999.99).

So on the security point of view array index checking should be always on.

Now another problem. Boundary checks cost CPU time. This CPU time can be
minimized. So I tested the behaviour of gnat. The main problem of gnat is, that the 
compiler do test the ranges of a value every time it needs this value.
That's a very time consumpting behaviour.

1. problem: unneccesary tests
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   Every variable need an internal boundary attribute to determine
   possible ranges of a variable to avoid this.

=========================================================================   
procedure a1 is

  j : integer range 1..10;
  s : integer;
  
begin

  s := 0;
  for i in 0 .. 9 loop
    j := i + 1;
    ...
  end loop;

end a1;
==========================================================================
	xorl %ecx,%ecx
	xorl %edx,%edx
	.align 4
.L5:
	incl %edx
	testl %edx,%edx		-- perfect nonsense
	jle .L8
	cmpl $10,%edx		-- perfect nonsense
	jle .L6
.L8:
	call __gnat_raise_constraint_error	-- never called at all
	.align 4
.L6:
        ...
	cmpl $9,%edx
	jle .L5
==========================================================================
Example was generated with -O2, 

Another example:
==========================================================================

  ...
  
  prim : array (0 .. 1_000_000) of boolean;
  
begin

  -- Initialisierung
  for i in prim'range loop
    prim(i) := true;	--  rep stosb  or  rep stosd is much more efficient
  end loop;
  
  prim(0) := false;
  prim(1) := false;
  
  -- Sieben
  for i in 0 .. 1_000 loop
    if prim(i) then	-- really unnecessary boundary test
      siebe:
        declare
          k : natural;
        begin
          k := 2*i;		-- k is > 0
          while k <= 1_000_000 loop
            prim(k) := false;	-- index test unneccesary, k *is* k<=1_000_000
            k := k + i;		-- increment
          end loop;
      end siebe;
    end if;
  end loop;
  
  -- Ausgabe
  for i in prim'range loop
    if prim(i) then		-- i *is* in range of of prim'range, no test necessary
      Put_Int(i);
      Put(" ");
    end if;
  end loop;

==========================================================================
   
I tested several examples and found out, that gnat never do such a compile
time checking for unneccesary boundray tests. Removing redundant tests
results in a speedup of 120% (x2.2) on my computer for some small programs.

You can always disable range checking in Ada, but was this the idea of Ada ???

var'cmin is in the following notation the smallest possible value, var'cmax
the largest.

Possible compile time range:

 i : integer range a..b;		-- i can only be in the range a..b;
 
 i := 12;				-- i can only be in the range 12..12;
 
 j := a + b;				-- j can only be in the range a'cmin+b'cmin..a'cmax+b'cmax
 j := c + 1;				-- j can only be in the range c'cmin+1..c'cmax+1
 
 j := nat1 * nat2;			-- j can only be in the range a'cmin*b'cmin..a'cmax*b'cmax
 k := int1 * int2;			-- if int1 and int2 can be <0 it's a little bit more difficult
 
 for i in arr'range loop		-- i can only in arr'range
 
 if i < 1000 then .... end fi;		-- for .... i must be <1000
 
 j := array[i]; ....			-- for .... i must be in array'range				
 
 if cond then a1; else a2; end fi; ....	-- for .... the variable ranges in a1 and a2 must be merged

 
2. problem: bad assembler code
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   * test of var in 0..max
   
     It will be tested, that (signed)var < 0 and (signed)var > max,
     faster is a simple test (unsigned)var > max .
   
     Why build one when you can build two for twice the price?
  
   * always jump around the exception call
   
     Extremly slow on CPUs with no jump prediction or if the jump prediction
     buffer overflows.

-- 
Frank Klemm

 /------\  /-----------------------------------------------------\
| eMail: || pfk@uni-jena.de | home: pfk@schnecke.offl.uni-jena.de |
| Tel:   ||                 | home: +49 (3641) 390545             |
| sMail: ||  Frank Klemm, Ziegesarstr. 1, D-07747 Jena, Germany   |
 \------/  \-----------------------------------------------------/