Re: Need advice on bounds checking approaches

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

I wrote:

> 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.  I emit checks as trees like so:

------------------------------------------------------------------------------
  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.  */
  compare = fold (build_binary_op (TRUTH_ORIF_EXPR,
				   fold (build_binary_op (LT_EXPR, value, base, 1)),
				   fold (build_binary_op (GE_EXPR, value, extent, 1)), 1));
  if (integer_zerop (compare))
    return value;
  else
    {
      tree crash = build_compound_expr (tree_cons (NULL_TREE,
						   build_function_call (trap_fndecl, NULL_TREE),
						   tree_cons (NULL_TREE, integer_zero_node,
							      NULL_TREE)));
      tree maybe_crash = fold (build_binary_op (TRUTH_ANDIF_EXPR, compare, crash, 1));
      tree check = fold (build_compound_expr (tree_cons (NULL_TREE, maybe_crash,
							 tree_cons (NULL_TREE, value,
								    NULL_TREE))));
      if (integer_onep (compare))
	warning ("bounds violation");
      return check;
    }
------------------------------------------------------------------------------
(The integer_zerop check isn't really necessary since fold will do the
same thing...  Should I bother with such micro-efficiencies?)

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.

Conditional traps are much easier to deal with for optimization since
they hide branches that would otherwise chop up basic blocks and they
are readily identifiable as checks, so I defined pseudo conditional
trap insns for ix86, like so:

------------------------------------------------------------------------------
(define_insn "trap"
  [(trap_if (const_int 1) (const_int 5))]
  ""
  "int\\t%0")

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

(define_expand "conditional_trap"
  [(trap_if (match_operator 0 "comparison_operator"
	     [(match_dup 2) (const_int 0)])
	    (match_operand 1 "const_int_operand" ""))]
  ""
  "
{
  enum rtx_code code = GET_CODE (operands[0]);
  int unordered = (code == EQ || code == NE);
  emit_insn (gen_rtx_TRAP_IF (VOIDmode,
			      ix86_expand_compare (code, unordered),
			      operands[1]));
  DONE;
}")

(define_insn ""
  [(trap_if (match_operator 0 "comparison_operator"
	     [(reg 17) (const_int 0)])
	    (match_operand 1 "const_int_operand" ""))]
  ""
  "j%c0\\t1f\;int\\t%1\\n1:")
------------------------------------------------------------------------------
(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?)

It is very easy to eliminate redundant checks at the end of the main
loop in combine_instructions:

	  if (GET_CODE (insn) == INSN
	      && GET_CODE (PATTERN (insn)) == TRAP_IF)
	    {
	      for (links = trap_insns; links; links = XEXP (links, 1))
		{
		  rtx earlier = XEXP (links, 0);
		  if (rtx_and_links_equal_p (insn, earlier))
		    {
		      /* This conditional trap is redundant, so delete
			 it after giving its notes to the earlier insn.  */
		      distribute_notes (REG_NOTES (insn), insn, earlier, earlier,
					NULL_RTX, NULL_RTX);
		      PUT_CODE (insn, NOTE);
		      NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
		      NOTE_SOURCE_FILE (insn) = 0;
		      break;
		    }
		}
	      if (GET_CODE (insn) == INSN)
		/* This conditional trap is unique, so remember it.  */
		trap_insns = alloc_INSN_LIST (insn, trap_insns);


...

/* Compare two insns and all the REG assignments they depend upon for
   equality.  We use this in order to determine if two conditional traps
   are identical, so that we may eliminate redundancies.  */

static int
rtx_and_links_equal_p (insn1, insn2)
     rtx insn1;
     rtx insn2;
{
  if (rtx_equal_p (PATTERN (insn1), PATTERN (insn2)))
    {
      rtx links1 = LOG_LINKS (insn1);
      rtx links2 = LOG_LINKS (insn2);
      while (links1 && links2)
	{
	  if (! rtx_and_links_equal_p (XEXP (links1, 0), XEXP (links2, 0)))
	    return 0;
	  links1 = XEXP (links1, 1);
	  links2 = XEXP (links2, 1);
	}
      return 1;
    }
  return 0;
}
------------------------------------------------------------------------------

I can now build runnable GNU libc-2.1 + most of GNU fileutils &
textutils with -fbounded-pointers.  I even found a bounds-violation
bug in GNU pr today.

Greg