gcc/tree-mudflap.c

   1 /* Mudflap: narrow-pointer bounds-checking by tree rewriting.
   2    Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Frank Ch. Eigler <fche@redhat.com>
   4    and Graydon Hoare <graydon@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23
  24 #include "config.h"
  25 #include "errors.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "hard-reg-set.h"
  30 #include "rtl.h"
  31 #include "tree.h"
  32 #include "tm_p.h"
  33 #include "basic-block.h"
  34 #include "flags.h"
  35 #include "function.h"
  36 #include "tree-inline.h"
  37 #include "tree-gimple.h"
  38 #include "tree-flow.h"
  39 #include "tree-mudflap.h"
  40 #include "tree-dump.h"
  41 #include "tree-pass.h"
  42 #include "hashtab.h"
  43 #include "diagnostic.h"
  44 #include <demangle.h>
  45 #include "langhooks.h"
  46 #include "ggc.h"
  47
  48 /* Internal function decls */
  49
  50 /* Helpers.  */
  51 static tree mf_build_string (const char *string);
  52 static tree mf_varname_tree (tree);
  53 static tree mf_file_function_line_tree (location_t *);
  54
  55 /* Initialization of all the mf-runtime.h extern decls.  */
  56 static void mf_init_extern_trees (void);
  57
  58 /* Indirection-related instrumentation.  */
  59 static void mf_decl_cache_locals (void);
  60 static void mf_decl_clear_locals (void);
  61 static void mf_xform_derefs (void);
  62 static void execute_mudflap_function_ops (void);
  63
  64 /* Addressable variables instrumentation.  */
  65 static void mf_xform_decls (tree, tree);
  66 static tree mx_xfn_xform_decls (tree *, int *, void *);
  67 static void mx_register_decls (tree, tree *);
  68 static void execute_mudflap_function_decls (void);
  69
  70
  71 /* ------------------------------------------------------------------------ */
  72 /* Some generally helpful functions for mudflap instrumentation.  */
  73
  74 /* Build a reference to a literal string.  */
  75 static tree
  76 mf_build_string (const char *string)
  77 {
  78   size_t len = strlen (string);
  79   tree result = mf_mark (build_string (len + 1, string));
  80
  81   TREE_TYPE (result)
  82       = build_array_type (char_type_node,
  83                           build_index_type (build_int_2 (len, 0)));
  84   TREE_CONSTANT (result) = 1;
  85   TREE_INVARIANT (result) = 1;
  86   TREE_READONLY (result) = 1;
  87   TREE_STATIC (result) = 1;
  88
  89   result = build1 (ADDR_EXPR, build_pointer_type (char_type_node), result);
  90
  91   return mf_mark (result);
  92 }
  93
  94 /* Create a properly typed STRING_CST node that describes the given
  95    declaration.  It will be used as an argument for __mf_register().
  96    Try to construct a helpful string, including file/function/variable
  97    name.  */
  98
  99 static tree
 100 mf_varname_tree (tree decl)
 101 {
 102   static pretty_printer buf_rec;
 103   static int initialized = 0;
 104   pretty_printer *buf = & buf_rec;
 105   const char *buf_contents;
 106   tree result;
 107
 108   if (decl == NULL_TREE)
 109     abort ();
 110
 111   if (!initialized)
 112     {
 113       pp_construct (buf, /* prefix */ NULL, /* line-width */ 0);
 114       initialized = 1;
 115     }
 116   pp_clear_output_area (buf);
 117
 118   /* Add FILENAME[:LINENUMBER].  */
 119   {
 120     const char *sourcefile;
 121     unsigned sourceline;
 122
 123     sourcefile = DECL_SOURCE_FILE (decl);
 124     if (sourcefile == NULL && current_function_decl != NULL_TREE)
 125       sourcefile = DECL_SOURCE_FILE (current_function_decl);
 126     if (sourcefile == NULL)
 127       sourcefile = "<unknown file>";
 128
 129     pp_string (buf, sourcefile);
 130
 131     sourceline = DECL_SOURCE_LINE (decl);
 132     if (sourceline != 0)
 133       {
 134         pp_string (buf, ":");
 135         pp_decimal_int (buf, sourceline);
 136       }
 137   }
 138
 139   if (current_function_decl != NULL_TREE)
 140     {
 141       /* Add (FUNCTION): */
 142       pp_string (buf, " (");
 143       {
 144         const char *funcname = NULL;
 145         if (DECL_NAME (current_function_decl))
 146           funcname = lang_hooks.decl_printable_name (current_function_decl, 1);
 147         if (funcname == NULL)
 148           funcname = "anonymous fn";
 149
 150         pp_string (buf, funcname);
 151       }
 152       pp_string (buf, ") ");
 153     }
 154   else
 155     pp_string (buf, " ");
 156
 157   /* Add <variable-declaration>, possibly demangled.  */
 158   {
 159     const char *declname = NULL;
 160
 161     if (strcmp ("GNU C++", lang_hooks.name) == 0 &&
 162         DECL_NAME (decl) != NULL)
 163       {
 164         /* The gcc/cp decl_printable_name hook doesn't do as good a job as
 165            the libiberty demangler.  */
 166         declname = cplus_demangle (IDENTIFIER_POINTER (DECL_NAME (decl)),
 167                                    DMGL_AUTO | DMGL_VERBOSE);
 168       }
 169
 170     if (declname == NULL)
 171       declname = lang_hooks.decl_printable_name (decl, 3);
 172
 173     if (declname == NULL)
 174       declname = "<unnamed variable>";
 175
 176     pp_string (buf, declname);
 177   }
 178
 179   /* Return the lot as a new STRING_CST.  */
 180   buf_contents = pp_base_formatted_text (buf);
 181   result = mf_build_string (buf_contents);
 182   pp_clear_output_area (buf);
 183
 184   return result;
 185 }
 186
 187
 188 /* And another friend, for producing a simpler message.  */
 189
 190 static tree
 191 mf_file_function_line_tree (location_t *locus)
 192 {
 193   const char *file = NULL, *colon, *line, *op, *name, *cp;
 194   char linebuf[18];
 195   char *string;
 196   tree result;
 197
 198   /* Add FILENAME.  */
 199   if (locus != NULL)
 200     file = locus->file;
 201   if (file == NULL && current_function_decl != NULL_TREE)
 202     file = DECL_SOURCE_FILE (current_function_decl);
 203   if (file == NULL)
 204     file = "<unknown file>";
 205
 206   /* Add :LINENUMBER.  */
 207   if (locus != NULL && locus->line > 0)
 208     {
 209       sprintf (linebuf, "%d", locus->line);
 210       colon = ":";
 211       line = linebuf;
 212     }
 213   else
 214     colon = line = "";
 215
 216   /* Add (FUNCTION).  */
 217   name = lang_hooks.decl_printable_name (current_function_decl, 1);
 218   if (name)
 219     {
 220       op = " (";
 221       cp = ")";
 222     }
 223   else
 224     op = name = cp = "";
 225
 226   string = concat (file, colon, line, op, name, cp, NULL);
 227   result = mf_build_string (string);
 228   free (string);
 229
 230   return result;
 231 }
 232
 233
 234 /* global tree nodes */
 235
 236 /* Global tree objects for global variables and functions exported by
 237    mudflap runtime library.  mf_init_extern_trees must be called
 238    before using these.  */
 239
 240 /* uintptr_t (usually "unsigned long") */
 241 static GTY (()) tree mf_uintptr_type;
 242
 243 /* struct __mf_cache { uintptr_t low; uintptr_t high; }; */
 244 static GTY (()) tree mf_cache_struct_type;
 245
 246 /* struct __mf_cache * const */
 247 static GTY (()) tree mf_cache_structptr_type;
 248
 249 /* extern struct __mf_cache __mf_lookup_cache []; */
 250 static GTY (()) tree mf_cache_array_decl;
 251
 252 /* extern const unsigned char __mf_lc_shift; */
 253 static GTY (()) tree mf_cache_shift_decl;
 254
 255 /* extern const uintptr_t __mf_lc_mask; */
 256 static GTY (()) tree mf_cache_mask_decl;
 257
 258 /* Their function-scope local shadows, used in single-threaded mode only. */
 259
 260 /* auto const unsigned char __mf_lc_shift_l; */
 261 static GTY (()) tree mf_cache_shift_decl_l;
 262
 263 /* auto const uintptr_t __mf_lc_mask_l; */
 264 static GTY (()) tree mf_cache_mask_decl_l;
 265
 266 /* extern void __mf_check (void *ptr, size_t sz, int type, const char *); */
 267 static GTY (()) tree mf_check_fndecl;
 268
 269 /* extern void __mf_register (void *ptr, size_t sz, int type, const char *); */
 270 static GTY (()) tree mf_register_fndecl;
 271
 272 /* extern void __mf_unregister (void *ptr, size_t sz); */
 273 static GTY (()) tree mf_unregister_fndecl;
 274
 275
 276 /* Initialize the global tree nodes that correspond to mf-runtime.h
 277    declarations.  */
 278 static void
 279 mf_init_extern_trees (void)
 280 {
 281   static bool done = false;
 282
 283   if (done)
 284     return;
 285   done = true;
 286
 287   mf_uintptr_type = TREE_TYPE (mflang_lookup_decl ("uintptr_t"));
 288   mf_cache_array_decl = mf_mark (mflang_lookup_decl ("__mf_lookup_cache"));
 289   mf_cache_struct_type = TREE_TYPE (TREE_TYPE (mf_cache_array_decl));
 290   mf_cache_structptr_type = build_pointer_type (mf_cache_struct_type);
 291   mf_cache_shift_decl = mf_mark (mflang_lookup_decl ("__mf_lc_shift"));
 292   mf_cache_mask_decl = mf_mark (mflang_lookup_decl ("__mf_lc_mask"));
 293   mf_check_fndecl = mflang_lookup_decl ("__mf_check");
 294   mf_register_fndecl = mflang_lookup_decl ("__mf_register");
 295   mf_unregister_fndecl = mflang_lookup_decl ("__mf_unregister");
 296 }
 297
 298
 299 /* ------------------------------------------------------------------------ */
 300 /* Memory reference transforms. Perform the mudflap indirection-related
 301    tree transforms on the current function.
 302
 303    This is the second part of the mudflap instrumentation.  It works on
 304    low-level GIMPLE using the CFG, because we want to run this pass after
 305    tree optimizations have been performed, but we have to preserve the CFG
 306    for expansion from trees to RTL.  */
 307
 308 static void
 309 execute_mudflap_function_ops (void)
 310 {
 311   if (mf_marked_p (current_function_decl))
 312     return;
 313
 314   push_gimplify_context ();
 315
 316   /* In multithreaded mode, don't cache the lookup cache parameters.  */
 317   if (! flag_mudflap_threads)
 318     mf_decl_cache_locals ();
 319
 320   mf_xform_derefs ();
 321
 322   if (! flag_mudflap_threads)
 323     mf_decl_clear_locals ();
 324
 325   pop_gimplify_context (NULL);
 326 }
 327
 328 /* Create and initialize local shadow variables for the lookup cache
 329    globals.  Put their decls in the *_l globals for use by
 330    mf_build_check_statement_for. */
 331
 332 static void
 333 mf_decl_cache_locals (void)
 334 {
 335   tree t, shift_init_stmts, mask_init_stmts;
 336   tree_stmt_iterator tsi;
 337
 338   /* Build the cache vars.  */
 339   mf_cache_shift_decl_l
 340     = mf_mark (create_tmp_var (TREE_TYPE (mf_cache_shift_decl),
 341                                "__mf_lookup_shift_l"));
 342
 343   mf_cache_mask_decl_l
 344     = mf_mark (create_tmp_var (TREE_TYPE (mf_cache_mask_decl),
 345                                "__mf_lookup_mask_l"));
 346
 347   /* Build initialization nodes for the cache vars.  We just load the
 348      globals into the cache variables.  */
 349   t = build (MODIFY_EXPR, TREE_TYPE (mf_cache_shift_decl_l),
 350              mf_cache_shift_decl_l, mf_cache_shift_decl);
 351   annotate_with_locus (t, DECL_SOURCE_LOCATION (current_function_decl));
 352   gimplify_to_stmt_list (&t);
 353   shift_init_stmts = t;
 354
 355   t = build (MODIFY_EXPR, TREE_TYPE (mf_cache_mask_decl_l),
 356              mf_cache_mask_decl_l, mf_cache_mask_decl);
 357   annotate_with_locus (t, DECL_SOURCE_LOCATION (current_function_decl));
 358   gimplify_to_stmt_list (&t);
 359   mask_init_stmts = t;
 360
 361   /* Anticipating multiple entry points, we insert the cache vars
 362      initializers in each successor of the ENTRY_BLOCK_PTR.  */
 363   for (tsi = tsi_start (shift_init_stmts);
 364        ! tsi_end_p (tsi);
 365        tsi_next (&tsi))
 366     insert_edge_copies (tsi_stmt (tsi), ENTRY_BLOCK_PTR);
 367
 368   for (tsi = tsi_start (mask_init_stmts);
 369        ! tsi_end_p (tsi);
 370        tsi_next (&tsi))
 371     insert_edge_copies (tsi_stmt (tsi), ENTRY_BLOCK_PTR);
 372   bsi_commit_edge_inserts (NULL);
 373 }
 374
 375
 376 static void
 377 mf_decl_clear_locals (void)
 378 {
 379   /* Unset local shadows. */
 380   mf_cache_shift_decl_l = NULL_TREE;
 381   mf_cache_mask_decl_l = NULL_TREE;
 382 }
 383
 384 static void
 385 mf_build_check_statement_for (tree addr, tree size,
 386                               block_stmt_iterator *instr_bsi,
 387                               location_t *locus, tree dirflag)
 388 {
 389   tree_stmt_iterator head, tsi;
 390   tree ptrtype = TREE_TYPE (addr);
 391   block_stmt_iterator bsi;
 392   basic_block cond_bb, then_bb, join_bb;
 393   edge e;
 394   tree cond, t, u, v, l1, l2;
 395   tree mf_value;
 396   tree mf_base;
 397   tree mf_elem;
 398
 399   /* We first need to split the current basic block, and start altering
 400      the CFG.  This allows us to insert the statements we're about to
 401      construct into the right basic blocks.  The label l1 is the label
 402      of the block for the THEN clause of the conditional jump we're
 403      about to construct, and l2 is the ELSE clause, which is just the
 404      continuation of the old statement stream.  */
 405   l1 = create_artificial_label ();
 406   l2 = create_artificial_label ();
 407   cond_bb = bb_for_stmt (bsi_stmt (*instr_bsi));
 408   bsi = *instr_bsi;
 409   bsi_prev (&bsi);
 410   if (! bsi_end_p (bsi))
 411     {
 412       e = split_block (cond_bb, bsi_stmt (bsi));
 413       cond_bb = e->src;
 414       join_bb = e->dest;
 415     }
 416   else
 417     {
 418       join_bb = cond_bb;
 419       cond_bb = create_empty_bb (join_bb->prev_bb);
 420       e = make_edge (cond_bb, join_bb, 0);
 421     }
 422   e->flags = EDGE_FALSE_VALUE;
 423   then_bb = create_empty_bb (cond_bb);
 424   make_edge (cond_bb, then_bb, EDGE_TRUE_VALUE);
 425   make_edge (then_bb, join_bb, EDGE_FALLTHRU);
 426
 427   /* We expect that the conditional jump we will construct will not
 428      be taken very often as it basically is an exception condition.  */
 429   predict_edge_def (then_bb->pred, PRED_MUDFLAP, NOT_TAKEN);
 430
 431   /* Update dominance info.  Note that bb_join's data was
 432      updated by split_block.  */
 433   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
 434     {
 435       set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
 436       set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
 437     }
 438
 439   /* Build our local variables.  */
 440   mf_value = create_tmp_var (ptrtype, "__mf_value");
 441   mf_elem = create_tmp_var (mf_cache_structptr_type, "__mf_elem");
 442   mf_base = create_tmp_var (mf_uintptr_type, "__mf_base");
 443
 444   /* Build: __mf_value = <address expression>.  */
 445   t = build (MODIFY_EXPR, void_type_node, mf_value, unshare_expr (addr));
 446   SET_EXPR_LOCUS (t, locus);
 447   gimplify_to_stmt_list (&t);
 448   head = tsi_start (t);
 449   tsi = tsi_last (t);
 450
 451   /* Build: __mf_base = (uintptr_t)__mf_value.  */
 452   t = build (MODIFY_EXPR, void_type_node, mf_base,
 453              build1 (NOP_EXPR, mf_uintptr_type, mf_value));
 454   SET_EXPR_LOCUS (t, locus);
 455   gimplify_to_stmt_list (&t);
 456   tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 457
 458   /* Build: __mf_elem = &__mf_lookup_cache [(__mf_base >> __mf_shift)
 459                                             & __mf_mask].  */
 460   t = build (RSHIFT_EXPR, mf_uintptr_type, mf_base,
 461              (flag_mudflap_threads ? mf_cache_shift_decl : mf_cache_shift_decl_l));
 462   t = build (BIT_AND_EXPR, mf_uintptr_type, t,
 463              (flag_mudflap_threads ? mf_cache_mask_decl : mf_cache_mask_decl_l));
 464   t = build (ARRAY_REF,
 465              TREE_TYPE (TREE_TYPE (mf_cache_array_decl)),
 466              mf_cache_array_decl, t, NULL_TREE, NULL_TREE);
 467   t = build1 (ADDR_EXPR, mf_cache_structptr_type, t);
 468   t = build (MODIFY_EXPR, void_type_node, mf_elem, t);
 469   SET_EXPR_LOCUS (t, locus);
 470   gimplify_to_stmt_list (&t);
 471   tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 472
 473   /* Quick validity check.
 474
 475      if (__mf_elem->low > __mf_base
 476          || (__mf_elem_high < __mf_base + sizeof(T) - 1))
 477         {
 478           __mf_check ();
 479           ... and only if single-threaded:
 480           __mf_lookup_shift_1 = f...;
 481           __mf_lookup_mask_l = ...;
 482         }
 483
 484      It is expected that this body of code is rarely executed so we mark
 485      the edge to the THEN clause of the conditional jump as unlikely.  */
 486
 487   /* Construct t <-- '__mf_elem->low  > __mf_base'.  */
 488   t = build (COMPONENT_REF, mf_uintptr_type,
 489              build1 (INDIRECT_REF, mf_cache_struct_type, mf_elem),
 490              TYPE_FIELDS (mf_cache_struct_type), NULL_TREE);
 491   t = build (GT_EXPR, boolean_type_node, t, mf_base);
 492
 493   /* Construct '__mf_elem->high < __mf_base + sizeof(T) - 1'.
 494
 495      First build:
 496         1) u <--  '__mf_elem->high'
 497         2) v <--  '__mf_base + sizeof (T) - 1'.
 498
 499      Then build 'u <-- (u < v).  */
 500
 501
 502   u = build (COMPONENT_REF, mf_uintptr_type,
 503              build1 (INDIRECT_REF, mf_cache_struct_type, mf_elem),
 504              TREE_CHAIN (TYPE_FIELDS (mf_cache_struct_type)), NULL_TREE);
 505
 506   v = convert (mf_uintptr_type,
 507                size_binop (MINUS_EXPR, size, size_one_node));
 508   v = fold (build (PLUS_EXPR, mf_uintptr_type, mf_base, v));
 509
 510   u = build (LT_EXPR, boolean_type_node, u, v);
 511
 512   /* Build the composed conditional: t <-- 't || u'.  Then store the
 513      result of the evaluation of 't' in a temporary variable which we
 514      can use as the condition for the conditional jump.  */
 515   t = build (TRUTH_OR_EXPR, boolean_type_node, t, u);
 516   cond = create_tmp_var (boolean_type_node, "__mf_unlikely_cond");
 517   t = build (MODIFY_EXPR, boolean_type_node, cond, t);
 518   gimplify_to_stmt_list (&t);
 519   tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 520
 521   /* Build the conditional jump.  'cond' is just a temporary so we can
 522      simply build a void COND_EXPR.  We do need labels in both arms though.  */
 523   t = build (COND_EXPR, void_type_node, cond,
 524              build (GOTO_EXPR, void_type_node, tree_block_label (then_bb)),
 525              build (GOTO_EXPR, void_type_node, tree_block_label (join_bb)));
 526   SET_EXPR_LOCUS (t, locus);
 527   tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 528
 529   /* At this point, after so much hard work, we have only constructed
 530      the conditional jump,
 531
 532      if (__mf_elem->low > __mf_base
 533          || (__mf_elem_high < __mf_base + sizeof(T) - 1))
 534
 535      The lowered GIMPLE tree representing this code is in the statement
 536      list starting at 'head'.
 537
 538      We can insert this now in the current basic block, ie. the one that
 539      the statement we're instrumenting was originally in.  */
 540   bsi = bsi_last (cond_bb);
 541   for (tsi = head; ! tsi_end_p (tsi); tsi_next (&tsi))
 542     bsi_insert_after (&bsi, tsi_stmt (tsi), BSI_CONTINUE_LINKING);
 543
 544   /*  Now build up the body of the cache-miss handling:
 545
 546      __mf_check();
 547      refresh *_l vars.
 548
 549      This is the body of the conditional.  */
 550
 551   u = tree_cons (NULL_TREE, mf_file_function_line_tree (locus), NULL_TREE);
 552   u = tree_cons (NULL_TREE, dirflag, u);
 553   u = tree_cons (NULL_TREE, size, u);
 554   u = tree_cons (NULL_TREE, mf_value, u);
 555   t = build_function_call_expr (mf_check_fndecl, u);
 556   gimplify_to_stmt_list (&t);
 557   head = tsi_start (t);
 558   tsi = tsi_last (t);
 559
 560   if (! flag_mudflap_threads)
 561     {
 562       t = build (MODIFY_EXPR, void_type_node,
 563                  mf_cache_shift_decl_l, mf_cache_shift_decl);
 564       tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 565
 566       t = build (MODIFY_EXPR, void_type_node,
 567                  mf_cache_mask_decl_l, mf_cache_mask_decl);
 568       tsi_link_after (&tsi, t, TSI_CONTINUE_LINKING);
 569     }
 570
 571   /* Insert the check code in the THEN block.  */
 572   bsi = bsi_start (then_bb);
 573   for (tsi = head; ! tsi_end_p (tsi); tsi_next (&tsi))
 574     bsi_insert_after (&bsi, tsi_stmt (tsi), BSI_CONTINUE_LINKING);
 575
 576   *instr_bsi = bsi_start (join_bb);
 577   bsi_next (instr_bsi);
 578 }
 579
 580 static void
 581 mf_xform_derefs_1 (block_stmt_iterator *iter, tree *tp,
 582                    location_t *locus, tree dirflag)
 583 {
 584   tree type, ptr_type, addr, size, t;
 585
 586   /* Don't instrument read operations.  */
 587   if (dirflag == integer_zero_node && flag_mudflap_ignore_reads)
 588     return;
 589
 590   t = *tp;
 591   type = TREE_TYPE (t);
 592   size = TYPE_SIZE_UNIT (type);
 593
 594   switch (TREE_CODE (t))
 595     {
 596     case ARRAY_REF:
 597       {
 598         /* Omit checking if we can statically determine that the access is
 599            valid.  For non-addressable local arrays this is not optional,
 600            since we won't have called __mf_register for the object.  */
 601         tree op0, op1;
 602
 603         op0 = TREE_OPERAND (t, 0);
 604         op1 = TREE_OPERAND (t, 1);
 605         while (TREE_CODE (op1) == INTEGER_CST)
 606           {
 607             tree dom = TYPE_DOMAIN (TREE_TYPE (op0));
 608
 609             /* Test for index in range.  Break if not.  */
 610             if (!dom
 611                 || (! TYPE_MIN_VALUE (dom)
 612                     || ! really_constant_p (TYPE_MIN_VALUE (dom)))
 613                 || (! TYPE_MAX_VALUE (dom)
 614                     || ! really_constant_p (TYPE_MAX_VALUE (dom)))
 615                 || (tree_int_cst_lt (op1, TYPE_MIN_VALUE (dom))
 616                     || tree_int_cst_lt (TYPE_MAX_VALUE (dom), op1)))
 617               break;
 618
 619             /* If we're looking at a non-external VAR_DECL, then the
 620                access must be ok.  */
 621             if (TREE_CODE (op0) == VAR_DECL && !DECL_EXTERNAL (op0))
 622               return;
 623
 624             /* Only continue if we're still looking at an array.  */
 625             if (TREE_CODE (op0) != ARRAY_REF)
 626               break;
 627
 628             op1 = TREE_OPERAND (op0, 1);
 629             op0 = TREE_OPERAND (op0, 0);
 630           }
 631
 632         /* If we got here, we couldn't statically the check.  */
 633         ptr_type = build_pointer_type (type);
 634         addr = build1 (ADDR_EXPR, ptr_type, t);
 635       }
 636       break;
 637
 638     case INDIRECT_REF:
 639       addr = TREE_OPERAND (t, 0);
 640       ptr_type = TREE_TYPE (addr);
 641       break;
 642
 643     case ARRAY_RANGE_REF:
 644       warning ("mudflap checking not yet implemented for ARRAY_RANGE_REF");
 645       return;
 646
 647     case COMPONENT_REF:
 648       {
 649         tree field;
 650
 651         /* If we're not dereferencing something, then the access
 652            must be ok.  */
 653         if (TREE_CODE (TREE_OPERAND (t, 0)) != INDIRECT_REF)
 654           return;
 655
 656         field = TREE_OPERAND (t, 1);
 657
 658         /* If we're looking at a bit field, then we can't take its address
 659            with ADDR_EXPR -- lang_hooks.mark_addressable will error.  Do
 660            things the hard way with PLUS.  */
 661         if (DECL_BIT_FIELD_TYPE (field))
 662           {
 663             if (TREE_CODE (DECL_SIZE_UNIT (field)) == INTEGER_CST)
 664               size = DECL_SIZE_UNIT (field);
 665
 666             addr = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
 667             addr = fold_convert (ptr_type_node, addr);
 668             addr = fold (build (PLUS_EXPR, ptr_type_node,
 669                                 addr, fold_convert (ptr_type_node,
 670                                                     byte_position (field))));
 671           }
 672         else
 673           {
 674             ptr_type = build_pointer_type (type);
 675             addr = build1 (ADDR_EXPR, ptr_type, t);
 676           }
 677       }
 678       break;
 679
 680     case BIT_FIELD_REF:
 681       {
 682         tree ofs, rem, bpu;
 683
 684         /* If we're not dereferencing something, then the access
 685            must be ok.  */
 686         if (TREE_CODE (TREE_OPERAND (t, 0)) != INDIRECT_REF)
 687           return;
 688
 689         bpu = bitsize_int (BITS_PER_UNIT);
 690         ofs = convert (bitsizetype, TREE_OPERAND (t, 2));
 691         rem = size_binop (TRUNC_MOD_EXPR, ofs, bpu);
 692         ofs = size_binop (TRUNC_DIV_EXPR, ofs, bpu);
 693
 694         size = convert (bitsizetype, TREE_OPERAND (t, 1));
 695         size = size_binop (PLUS_EXPR, size, rem);
 696         size = size_binop (CEIL_DIV_EXPR, size, bpu);
 697         size = convert (sizetype, size);
 698
 699         addr = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
 700         addr = convert (ptr_type_node, addr);
 701         addr = fold (build (PLUS_EXPR, ptr_type_node, addr, ofs));
 702       }
 703       break;
 704
 705     default:
 706       return;
 707     }
 708
 709   mf_build_check_statement_for (addr, size, iter, locus, dirflag);
 710 }
 711
 712 static void
 713 mf_xform_derefs (void)
 714 {
 715   basic_block bb, next;
 716   block_stmt_iterator i;
 717   int saved_last_basic_block = last_basic_block;
 718
 719   bb = ENTRY_BLOCK_PTR ->next_bb;
 720   do
 721     {
 722       next = bb->next_bb;
 723       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 724         {
 725           tree s = bsi_stmt (i);
 726
 727           /* Only a few GIMPLE statements can reference memory.  */
 728           switch (TREE_CODE (s))
 729             {
 730             case MODIFY_EXPR:
 731               mf_xform_derefs_1 (&i, &TREE_OPERAND (s, 0), EXPR_LOCUS (s),
 732                                  integer_one_node);
 733               mf_xform_derefs_1 (&i, &TREE_OPERAND (s, 1), EXPR_LOCUS (s),
 734                                  integer_zero_node);
 735               break;
 736
 737             case RETURN_EXPR:
 738               if (TREE_OPERAND (s, 0) != NULL_TREE)
 739                 {
 740                   if (TREE_CODE (TREE_OPERAND (s, 0)) == MODIFY_EXPR)
 741                     mf_xform_derefs_1 (&i, &TREE_OPERAND (TREE_OPERAND (s, 0), 1),
 742                                        EXPR_LOCUS (s), integer_zero_node);
 743                   else
 744                     mf_xform_derefs_1 (&i, &TREE_OPERAND (s, 0), EXPR_LOCUS (s),
 745                                        integer_zero_node);
 746                 }
 747               break;
 748
 749             default:
 750               ;
 751             }
 752         }
 753       bb = next;
 754     }
 755   while (bb && bb->index <= saved_last_basic_block);
 756 }
 757
 758 /* ------------------------------------------------------------------------ */
 759 /* ADDR_EXPR transforms.  Perform the declaration-related mudflap tree
 760    transforms on the current function.
 761
 762    This is the first part of the mudflap instrumentation.  It works on
 763    high-level GIMPLE because after lowering, all variables are moved out
 764    of their BIND_EXPR binding context, and we lose liveness information
 765    for the declarations we wish to instrument.  */
 766
 767 static void
 768 execute_mudflap_function_decls (void)
 769 {
 770   if (mf_marked_p (current_function_decl))
 771     return;
 772
 773   push_gimplify_context ();
 774
 775   mf_init_extern_trees ();
 776   mf_xform_decls (DECL_SAVED_TREE (current_function_decl),
 777                   DECL_ARGUMENTS (current_function_decl));
 778
 779   pop_gimplify_context (NULL);
 780 }
 781
 782 /* This struct is passed between mf_xform_decls to store state needed
 783    during the traversal searching for objects that have their
 784    addresses taken.  */
 785 struct mf_xform_decls_data
 786 {
 787   tree param_decls;
 788 };
 789
 790
 791 /* Synthesize a CALL_EXPR and a TRY_FINALLY_EXPR, for this chain of
 792    _DECLs if appropriate.  Arrange to call the __mf_register function
 793    now, and the __mf_unregister function later for each.  */
 794 static void
 795 mx_register_decls (tree decl, tree *stmt_list)
 796 {
 797   tree finally_stmts = NULL_TREE;
 798   tree_stmt_iterator initially_stmts = tsi_start (*stmt_list);
 799
 800   while (decl != NULL_TREE)
 801     {
 802       /* Eligible decl?  */
 803       if ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == PARM_DECL)
 804           /* It must be a non-external, automatic variable.  */
 805           && ! DECL_EXTERNAL (decl)
 806           && ! TREE_STATIC (decl)
 807           /* The decl must have its address taken.  */
 808           && TREE_ADDRESSABLE (decl)
 809           /* The type of the variable must be complete.  */
 810           && COMPLETE_OR_VOID_TYPE_P (TREE_TYPE (decl))
 811           /* Don't process the same decl twice.  */
 812           && ! mf_marked_p (decl))
 813         {
 814           tree size = NULL_TREE, variable_name;
 815           tree unregister_fncall, unregister_fncall_params;
 816           tree register_fncall, register_fncall_params;
 817
 818           if (DECL_DEFER_OUTPUT (decl))
 819             {
 820               /* Oh no ... it's probably a variable-length array (VLA).
 821                  The size and address cannot be computed by merely
 822                  looking at the DECL.  See gimplify_decl_stmt for the
 823                  method by which VLA declarations turn into calls to
 824                  BUILT_IN_STACK_ALLOC.  We assume that multiple
 825                  VLAs declared later in the same block get allocation
 826                  code later than the others.  */
 827               tree stack_alloc_call = NULL_TREE;
 828
 829               while(! tsi_end_p (initially_stmts))
 830                 {
 831                   tree t = tsi_stmt (initially_stmts);
 832
 833                   tree call = NULL_TREE;
 834                   if (TREE_CODE (t) == CALL_EXPR)
 835                     call = t;
 836                   else if (TREE_CODE (t) == MODIFY_EXPR &&
 837                            TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
 838                     call = TREE_OPERAND (t, 1);
 839                   else if (TREE_CODE (t) == TRY_FINALLY_EXPR)
 840                     {
 841                       /* We hope that this is the try/finally block sometimes
 842                          constructed by gimplify_bind_expr() for a BIND_EXPR
 843                          that contains VLAs.  This very naive recursion
 844                          appears to be sufficient.  */
 845                       initially_stmts = tsi_start (TREE_OPERAND (t, 0));
 846                     }
 847
 848                   if (call != NULL_TREE)
 849                     {
 850                       if (TREE_CODE (TREE_OPERAND(call, 0)) == ADDR_EXPR &&
 851                           TREE_OPERAND (TREE_OPERAND (call, 0), 0) ==
 852                                 implicit_built_in_decls [BUILT_IN_STACK_ALLOC])
 853                         {
 854                           tree stack_alloc_args = TREE_OPERAND (call, 1);
 855                           tree stack_alloc_op1 = TREE_VALUE (stack_alloc_args);
 856                           tree stack_alloc_op2 = TREE_VALUE (TREE_CHAIN (stack_alloc_args));
 857
 858                           if (TREE_CODE (stack_alloc_op1) == ADDR_EXPR &&
 859                               TREE_OPERAND (stack_alloc_op1, 0) == decl)
 860                             {
 861                               /* Got it! */
 862                               size = stack_alloc_op2;
 863                               stack_alloc_call = call;
 864                               /* Advance iterator to point past this allocation call.  */
 865                               tsi_next (&initially_stmts);
 866                               break;
 867                             }
 868                         }
 869                     }
 870
 871                   tsi_next (&initially_stmts);
 872                 }
 873
 874               if (stack_alloc_call == NULL_TREE)
 875                 {
 876                   warning ("mudflap cannot handle variable-sized declaration `%s'",
 877                          IDENTIFIER_POINTER (DECL_NAME (decl)));
 878                   break;
 879                 }
 880             }
 881           else
 882             {
 883               size = convert (size_type_node, TYPE_SIZE_UNIT (TREE_TYPE (decl)));
 884             }
 885
 886           /* (& VARIABLE, sizeof (VARIABLE), __MF_TYPE_STACK) */
 887           unregister_fncall_params =
 888             tree_cons (NULL_TREE,
 889                        convert (ptr_type_node,
 890                                 mf_mark (build1 (ADDR_EXPR,
 891                                                  build_pointer_type (TREE_TYPE (decl)),
 892                                                  decl))),
 893                        tree_cons (NULL_TREE,
 894                                   size,
 895                                   tree_cons (NULL_TREE,
 896                                              build_int_2 (3, 0), /* __MF_TYPE_STACK */
 897                                              NULL_TREE)));
 898           /* __mf_unregister (...) */
 899           unregister_fncall = build_function_call_expr (mf_unregister_fndecl,
 900                                                         unregister_fncall_params);
 901
 902           /* (& VARIABLE, sizeof (VARIABLE), __MF_TYPE_STACK, "name") */
 903           variable_name = mf_varname_tree (decl);
 904           register_fncall_params =
 905             tree_cons (NULL_TREE,
 906                    convert (ptr_type_node,
 907                             mf_mark (build1 (ADDR_EXPR,
 908                                              build_pointer_type (TREE_TYPE (decl)),
 909                                              decl))),
 910                        tree_cons (NULL_TREE,
 911                                   size,
 912                                   tree_cons (NULL_TREE,
 913                                              build_int_2 (3, 0), /* __MF_TYPE_STACK */
 914                                              tree_cons (NULL_TREE,
 915                                                         variable_name,
 916                                                         NULL_TREE))));
 917
 918           /* __mf_register (...) */
 919           register_fncall = build_function_call_expr (mf_register_fndecl,
 920                                                       register_fncall_params);
 921
 922           /* Accumulate the two calls.  */
 923           /* ??? Set EXPR_LOCUS.  */
 924           gimplify_stmt (&register_fncall);
 925           gimplify_stmt (&unregister_fncall);
 926
 927           /* Add the __mf_register call at the current appending point.  */
 928           if (tsi_end_p (initially_stmts))
 929             internal_error ("mudflap ran off end of BIND_EXPR body");
 930           tsi_link_before (&initially_stmts, register_fncall, TSI_SAME_STMT);
 931
 932           /* Accumulate the FINALLY piece.  */
 933           append_to_statement_list (unregister_fncall, &finally_stmts);
 934
 935           mf_mark (decl);
 936         }
 937
 938       decl = TREE_CHAIN (decl);
 939     }
 940
 941   /* Actually, (initially_stmts!=NULL) <=> (finally_stmts!=NULL) */
 942   if (finally_stmts != NULL_TREE)
 943     {
 944       tree t = build (TRY_FINALLY_EXPR, void_type_node,
 945                       *stmt_list, finally_stmts);
 946       *stmt_list = NULL;
 947       append_to_statement_list (t, stmt_list);
 948     }
 949 }
 950
 951
 952 /* Process every variable mentioned in BIND_EXPRs.  */
 953 static tree
 954 mx_xfn_xform_decls (tree *t, int *continue_p, void *data)
 955 {
 956   struct mf_xform_decls_data* d = (struct mf_xform_decls_data*) data;
 957
 958   if (*t == NULL_TREE || *t == error_mark_node)
 959     {
 960       *continue_p = 0;
 961       return NULL_TREE;
 962     }
 963
 964   *continue_p = 1;
 965
 966   switch (TREE_CODE (*t))
 967     {
 968     case BIND_EXPR:
 969       {
 970         /* Process function parameters now (but only once).  */
 971         mx_register_decls (d->param_decls, &BIND_EXPR_BODY (*t));
 972         d->param_decls = NULL_TREE;
 973
 974         mx_register_decls (BIND_EXPR_VARS (*t), &BIND_EXPR_BODY (*t));
 975       }
 976       break;
 977
 978     default:
 979       break;
 980     }
 981
 982   return NULL;
 983 }
 984
 985 /* Perform the object lifetime tracking mudflap transform on the given function
 986    tree.  The tree is mutated in place, with possibly copied subtree nodes.
 987
 988    For every auto variable declared, if its address is ever taken
 989    within the function, then supply its lifetime to the mudflap
 990    runtime with the __mf_register and __mf_unregister calls.
 991 */
 992
 993 static void
 994 mf_xform_decls (tree fnbody, tree fnparams)
 995 {
 996   struct mf_xform_decls_data d;
 997   d.param_decls = fnparams;
 998   walk_tree_without_duplicates (&fnbody, mx_xfn_xform_decls, &d);
 999 }
1000
1001
1002 /* ------------------------------------------------------------------------ */
1003 /* Externally visible mudflap functions.  */
1004
1005
1006 /* Mark and return the given tree node to prevent further mudflap
1007    transforms.  */
1008 static GTY ((param_is (union tree_node))) htab_t marked_trees = NULL;
1009
1010 tree
1011 mf_mark (tree t)
1012 {
1013   void **slot;
1014
1015   if (marked_trees == NULL)
1016     marked_trees = htab_create_ggc (31, htab_hash_pointer, htab_eq_pointer, NULL);
1017
1018   slot = htab_find_slot (marked_trees, t, INSERT);
1019   *slot = t;
1020   return t;
1021 }
1022
1023 int
1024 mf_marked_p (tree t)
1025 {
1026   void *entry;
1027
1028   if (marked_trees == NULL)
1029     return 0;
1030
1031   entry = htab_find (marked_trees, t);
1032   return (entry != NULL);
1033 }
1034
1035 /* Remember given node as a static of some kind: global data,
1036    function-scope static, or an anonymous constant.  Its assembler
1037    label is given.  */
1038
1039 /* A list of globals whose incomplete declarations we encountered.
1040    Instead of emitting the __mf_register call for them here, it's
1041    delayed until program finish time.  If they're still incomplete by
1042    then, warnings are emitted.  */
1043
1044 static GTY (()) varray_type deferred_static_decls;
1045
1046 /* A list of statements for calling __mf_register() at startup time.  */
1047 static GTY (()) tree enqueued_call_stmt_chain;
1048
1049 static void
1050 mudflap_register_call (tree obj, tree object_size, tree varname)
1051 {
1052   tree arg, args, call_stmt;
1053
1054   args = tree_cons (NULL_TREE, varname, NULL_TREE);
1055
1056   arg = build_int_2 (4, 0); /* __MF_TYPE_STATIC */
1057   args = tree_cons (NULL_TREE, arg, args);
1058
1059   arg = convert (size_type_node, object_size);
1060   args = tree_cons (NULL_TREE, arg, args);
1061
1062   arg = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (obj)), obj);
1063   arg = convert (ptr_type_node, arg);
1064   args = tree_cons (NULL_TREE, arg, args);
1065
1066   mf_init_extern_trees ();
1067   call_stmt = build_function_call_expr (mf_register_fndecl, args);
1068
1069   append_to_statement_list (call_stmt, &enqueued_call_stmt_chain);
1070 }
1071
1072 void
1073 mudflap_enqueue_decl (tree obj)
1074 {
1075   if (mf_marked_p (obj))
1076     return;
1077
1078   /* We don't need to process variable decls that are internally
1079      generated extern.  If we did, we'd end up with warnings for them
1080      during mudflap_finish_file ().  That would confuse the user,
1081      since the text would refer to variables that don't show up in the
1082      user's source code.  */
1083   if (DECL_P (obj) && DECL_EXTERNAL (obj) && DECL_ARTIFICIAL (obj))
1084     return;
1085
1086   if (COMPLETE_TYPE_P (TREE_TYPE (obj)))
1087     {
1088       tree object_size;
1089
1090       mf_mark (obj);
1091
1092       object_size = size_in_bytes (TREE_TYPE (obj));
1093
1094       if (dump_file)
1095         {
1096           fprintf (dump_file, "enqueue_decl obj=`");
1097           print_generic_expr (dump_file, obj, dump_flags);
1098           fprintf (dump_file, "' size=");
1099           print_generic_expr (dump_file, object_size, dump_flags);
1100           fprintf (dump_file, "\n");
1101         }
1102
1103       /* NB: the above condition doesn't require TREE_USED or
1104          TREE_ADDRESSABLE.  That's because this object may be a global
1105          only used from other compilation units.  XXX: Maybe static
1106          objects could require those attributes being set.  */
1107
1108       mudflap_register_call (obj, object_size, mf_varname_tree (obj));
1109     }
1110   else
1111     {
1112       size_t i;
1113
1114       if (! deferred_static_decls)
1115         VARRAY_TREE_INIT (deferred_static_decls, 10, "deferred static list");
1116
1117       /* Ugh, linear search... */
1118       for (i = 0; i < VARRAY_ACTIVE_SIZE (deferred_static_decls); i++)
1119         if (VARRAY_TREE (deferred_static_decls, i) == obj)
1120           {
1121             warning ("mudflap cannot track lifetime of `%s'",
1122                      IDENTIFIER_POINTER (DECL_NAME (obj)));
1123             return;
1124           }
1125
1126       VARRAY_PUSH_TREE (deferred_static_decls, obj);
1127     }
1128 }
1129
1130 void
1131 mudflap_enqueue_constant (tree obj)
1132 {
1133   tree object_size, varname;
1134
1135   if (mf_marked_p (obj))
1136     return;
1137
1138   if (TREE_CODE (obj) == STRING_CST)
1139     object_size = build_int_2 (TREE_STRING_LENGTH (obj), 0);
1140   else
1141     object_size = size_in_bytes (TREE_TYPE (obj));
1142
1143   if (dump_file)
1144     {
1145       fprintf (dump_file, "enqueue_constant obj=`");
1146       print_generic_expr (dump_file, obj, dump_flags);
1147       fprintf (dump_file, "' size=");
1148       print_generic_expr (dump_file, object_size, dump_flags);
1149       fprintf (dump_file, "\n");
1150     }
1151
1152   if (TREE_CODE (obj) == STRING_CST)
1153     varname = mf_build_string ("string literal");
1154   else
1155     varname = mf_build_string ("constant");
1156
1157   mudflap_register_call (obj, object_size, varname);
1158 }
1159
1160
1161 /* Emit any file-wide instrumentation.  */
1162 void
1163 mudflap_finish_file (void)
1164 {
1165   /* Try to give the deferred objects one final try.  */
1166   if (deferred_static_decls)
1167     {
1168       size_t i;
1169
1170       for (i = 0; i < VARRAY_ACTIVE_SIZE (deferred_static_decls); i++)
1171         {
1172           tree obj = VARRAY_TREE (deferred_static_decls, i);
1173
1174           /* Call enqueue_decl again on the same object it has previously
1175              put into the table.  (It won't modify the table this time, so
1176              infinite iteration is not a problem.)  */
1177           mudflap_enqueue_decl (obj);
1178         }
1179
1180       VARRAY_CLEAR (deferred_static_decls);
1181     }
1182
1183   mflang_flush_calls (enqueued_call_stmt_chain);
1184 }
1185
1186
1187 static bool
1188 gate_mudflap (void)
1189 {
1190   return flag_mudflap != 0;
1191 }
1192
1193 struct tree_opt_pass pass_mudflap_1 =
1194 {
1195   "mudflap1",                           /* name */
1196   gate_mudflap,                         /* gate */
1197   execute_mudflap_function_decls,       /* execute */
1198   NULL,                                 /* sub */
1199   NULL,                                 /* next */
1200   0,                                    /* static_pass_number */
1201   0,                                    /* tv_id */
1202   PROP_gimple_any,                      /* properties_required */
1203   0,                                    /* properties_provided */
1204   0,                                    /* properties_destroyed */
1205   0,                                    /* todo_flags_start */
1206   TODO_dump_func                        /* todo_flags_finish */
1207 };
1208
1209 struct tree_opt_pass pass_mudflap_2 =
1210 {
1211   "mudflap2",                           /* name */
1212   gate_mudflap,                         /* gate */
1213   execute_mudflap_function_ops,         /* execute */
1214   NULL,                                 /* sub */
1215   NULL,                                 /* next */
1216   0,                                    /* static_pass_number */
1217   0,                                    /* tv_id */
1218   PROP_gimple_leh,                      /* properties_required */
1219   0,                                    /* properties_provided */
1220   0,                                    /* properties_destroyed */
1221   0,                                    /* todo_flags_start */
1222   TODO_verify_flow | TODO_verify_stmts
1223   | TODO_dump_func                      /* todo_flags_finish */
1224 };
1225
1226 #include "gt-tree-mudflap.h"