Re: Need advice on bounds checking approaches

[Jeffrey A Law <law@cygnus.com>]

  In message < ms7le93l40.fsf@tucson-net-82.eng.ascend.com >you write:
   > > We can do without a special pass.  CSE seems the best place to
  > > eliminate redundant checks, so we'd just need a little bit of code to
  > > handle the new check_bounds_rtx.  We can just forget about doing
  > > default translation of check_bounds_rtx into primitive RTL, and
  > > require that targets supporting bounds checking handle it in the
  > > machine description.  So far, all of the targets I want to support
  > > initially (i960, PowerPC, i386, MIPS) will benefit from special
  > > handling in the MD file anyway.
  > 
  > Happy news: this turned out to be less intrusive than I feared it
  > might become.  
Cool.

  > ---------------------------------------------------------------------------
  > ---
  >   value = build_bounded_ptr_value_ref (bp);
  >   base = build_bounded_ptr_base_ref (bp);
  >   extent = build_bounded_ptr_extent_ref (bp);
  > 
  >   /* GKM FIXME: fold needs to be enhanced to evaluate expressions of
  >      the form (a >= (a + i)) ==> 0, where `a' is an address and `i' is
  >      a positive integer.  */
I'm surprised fold doesn't already do that kind of transformation.  There
may be obscure issues with signed vs unsigned pointers and such here.

Anyway, it would seem relatively straightforward to me to add that class of
optimizations to fold.  We'd probably need to restrict them to cases where
'a' is a pointer type though.

  >   compare = fold (build_binary_op (TRUTH_ORIF_EXPR,
  > 				   fold (build_binary_op (LT_EXPR, value, base,
  >  1)),
  > 				   fold (build_binary_op (GE_EXPR, value, exten
  > t, 1)), 1));
  >   if (integer_zerop (compare))
I wonder if this can be done via a call into the range optimizers.  Their
job is to optimize range checking.

  >       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?

  >       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 integer_zerop check isn't really necessary since fold will do the
  > same thing...  Should I bother with such micro-efficiencies?)
I don't follow exactly, possibly because I don't know where you propose
to insert this code.

  > The jump optimizer already automagically converts conditional jumps
  > around traps into conditional traps, if they're defined for the
  > machine, otherwise they remain as unconditional traps.
Right.


  > ;;; ix86 doesn't have conditional traps, but we fake them for the sake
  > ;;; of bounds checking.  By emitting bounds checks as conditional
  > ;;; traps rather than as conditional jumps around unconditional traps
  > ;;; we avoid introducing spurious basic-block boundaries and facilitate
  > ;;; elimination of redundant checks.
This style may end up being the recommended approach; not really sure.  Maybe
we just leave it up to the backend folks for each port with a note that
this kind of approach might be more efficient.


  > (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.


  > 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.

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

jeff