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