OSDN Git Service

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