Re: Need advice on bounds checking approaches

[Greg McGary <gkm at eng dot ascend dot com>]

Jeffrey A Law <law@cygnus.com> writes:

>   >       tree crash = build_compound_expr (tree_cons (NULL_TREE,
>   > 						   build_function_call (trap_fn
>   > decl, NULL_TREE),
>   > 						   tree_cons (NULL_TREE, intege
>   > r_zero_node,
>   > 							      NULL_TREE)));
>   >       tree maybe_crash = fold (build_binary_op (TRUTH_ANDIF_EXPR, compare, 
>   > crash, 1));
> I don't understand this -- it looks like you're expecting the trap function
> to return a value.  Is that correct?  Presumably it will be a runtime value,
> not a compile-time value?

The thing is that __builtin_trap doesn't return a value, but the
expression I'm building wants a value, so I wrap it in `(__builtin_trap (), 0)'.

The whole expansion is this:

(((p.value < p.base || p.value >= p.extent)
  && (__builtin_trap (), 0)),
 p.value)

Without the compound expr around __builtin_trap, it's this:

(((p.value < p.base || p.value >= p.extent)
  && __builtin_trap),
 p.value)

but here gcc complains about the truth_andif_expr not returning a
value, even though we ignore the value anyway, since I'm just using
the short-circuit behavior of `&&' to evaluate __builtin_trap trap if
the predicate is true.  The value of the entire check expression
wants to be p.value.

>   >       tree check = fold (build_compound_expr (tree_cons (NULL_TREE, maybe_c
>   > rash,
>   > 							 tree_cons (NULL_TREE, 
>   > value,
>   > 								    NULL_TREE))
>   > ));
>   >       if (integer_onep (compare))
>   > 	warning ("bounds violation");
>   >       return check;
> Seems to me check will never be integer_onep unless we know trap_fn always
> returns a nonzero value.

The variable `compare' represents the bounds tests:

	(p.value < p.base || p.value >= p.extent)

The variable `maybe_crash' represents bounds tests & the conditional trap:

	((p.value < p.base || p.value >= p.extent)
	 && (__builtin_trap (), 0))

The variable `check' represents the whole package, which returns the pointer value:

	(((p.value < p.base || p.value >= p.extent)
	  && __builtin_trap),
	 p.value)

Obviously, I should comment better, or choose better variable names.

>   > (Should I somehow mark conditional traps as being generated
>   > automatically by bounds checking, and only optimize those away, or
>   > should I just document the as yet undocumented __builtin_trap as
>   > subject to this optimization?)
> I don't think so.

There are two questions here.  Which one are you answering?
(a) only optimize away redundant trap_if associate with BPs?
(b) optimize away all redundant trap_if, and document that behavior
    for __builtin_trap?  (incidentally, __builtin_trap is undocumented)

>   > It is very easy to eliminate redundant checks at the end of the main
>   > loop in combine_instructions:
> This looks very compile-time expensive since you have to walk the LOG_LINKs
> chain all the way back to the top of the dependency chain.

I'll instrument it, but from limited observation, I have see that we
only walk back one or two level, since pointers are usually not
subjected to complicated arithmetic with many subexpressions.

> Presumably you're trying to delete one conditional trap that is subsumed by
> an earlier conditional trap?  If so, that might be best modeled after an
> identical optimization we do on jumps.   See jump.c

OK.  Thanks for the tips.

Greg