Need advice on bounds checking approaches

[Greg McGary]

Geoff Keating <geoffk@cygnus.com> writes:

> Note that you can do (3) with a subtraction and a single conditional
> trap instruction---eg. if you want to check whether 'r3' is between 4
> and 10, you can do
> 
>     tmp = r3 - 4
>     if ((unsigned)r3 > 6)  trap;

you meant:
      if ((unsigned)tmp > 6)  trap;

> or
> 
>     tmp = r3 - 4 + MIN_INT;
>     if ((int)r3 > MIN_INT + 6)  trap;

you meant:
      if ((int)tmp > MIN_INT + 6)  trap;

> depending on what's available.  The machine-independent code should be
> able to work this out.

In practice, you can't do the 10-4 subtraction at compile time.  You
need two runtime subtractions (rV = value reg, rB = base reg, rX =
extent reg):

	rB = rV - rB
	rX = rX - rB
	trap_if rB > rX

> Of course, this only makes sense if a conditional trap is slower than
> a subtraction,

For an untaken conditional trap that is 2x slower than a subtraction,
the times are even for 2 traps vs. 2 subtractions + 1 trap, with the
advantage to the 2 traps because it doesn't clobber rB.  Untaken
conditional traps would need to be at least 3x slower to justify doing
the subtraction trick.  I'd bet dollars to donuts that there are is no
RISC that has untaken conditional traps that take 3+ clocks.

> ... If there are no conditional traps, probably
> gcc should already be trying to do this for conditional branches.

I don't think the subtractions win for ix86, which is the only CISC
having no conditional traps that most people care about.  In order to
do the extent-base subtraction, you have to load the extent into a
register which you would not need to do otherwise.  Also, you need to
do the value-base subtraction in a temporary, in order to preserve rV.
With the subtraction approach you need to do this (in pseudo asm;
rV, rX and rT are registers holding value, extent and temp; `base' and
`extent' are references to those quantities in memory):

	load extent to rX
	subtract base from rX
	copy rV to rT
	subtract base from rT
	compare rT and rX
	branch to 0f if <=
	trap
    0:

With integrated simple compares & conditional branches:

	compare rV with base
	branch to 0f if >=
	compare rV with extent
	branch to 1f if <
    0:  trap
    1:

With independent compares & conditional branches:

	compare rV with base
	branch to 0f if >=
	trap
    0:
	...
	compare rV with extent
	branch to 1f if <
        trap
    1:

Both of the simpler compare/branch sequences are as good as or better
than the subtractions for time & space, and they consume fewer
registers.

Greg