From mboxrd@z Thu Jan 1 00:00:00 1970 From: Greg McGary To: Geoff Keating Cc: law@cygnus.com, gcc@gcc.gnu.org Subject: Re: Need advice on bounds checking approaches Date: Tue, 28 Mar 2000 14:21:00 -0000 Message-id: References: <679.954265252@upchuck> <200003281930.LAA01001@localhost.cygnus.com> X-SW-Source: 2000-03/msg00745.html Geoff Keating 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