OSDN Git Service

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