re PR tree-optimization/63747 (icf mis-compares switch gimple)
[gcc.git] / gcc / ipa-chkp.c
1 /* Pointer Bounds Checker IPA passes.
2 Copyright (C) 2014 Free Software Foundation, Inc.
3 Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree-core.h"
25 #include "stor-layout.h"
26 #include "tree.h"
27 #include "tree-pass.h"
28 #include "stringpool.h"
29 #include "bitmap.h"
30 #include "gimple-expr.h"
31 #include "tm.h"
32 #include "hard-reg-set.h"
33 #include "function.h"
34 #include "is-a.h"
35 #include "tree-ssa-alias.h"
36 #include "predict.h"
37 #include "basic-block.h"
38 #include "gimple.h"
39 #include "ipa-ref.h"
40 #include "lto-streamer.h"
41 #include "cgraph.h"
42 #include "tree-chkp.h"
43 #include "ipa-chkp.h"
44 #include <string>
45
46 /* Pointer Bounds Checker has two IPA passes to support code instrumentation.
47
48 In instrumented code each pointer is provided with bounds. For input
49 pointer parameters it means we also have bounds passed. For calls it
50 means we have additional bounds arguments for pointer arguments.
51
52 To have all IPA optimizations working correctly we have to express
53 dataflow between passed and received bounds explicitly via additional
54 entries in function declaration arguments list and in function type.
55 Since we may have both instrumented and not instrumented code at the
56 same time, we cannot replace all original functions with their
57 instrumented variants. Therefore we create clones (versions) instead.
58
59 Instrumentation clones creation is a separate IPA pass which is a part
60 of early local passes. Clones are created after SSA is built (because
61 instrumentation pass works on SSA) and before any transformations
62 which may change pointer flow and therefore lead to incorrect code
63 instrumentation (possibly causing false bounds check failures).
64
65 Instrumentation clones have pointer bounds arguments added right after
66 pointer arguments. Clones have assembler name of the original
67 function with suffix added. New assembler name is in transparent
68 alias chain with the original name. Thus we expect all calls to the
69 original and instrumented functions look similar in assembler.
70
71 During instrumentation versioning pass we create instrumented versions
72 of all function with body and also for all their aliases and thunks.
73 Clones for functions with no body are created on demand (usually
74 during call instrumentation).
75
76 Original and instrumented function nodes are connected with IPA
77 reference IPA_REF_CHKP. It is mostly done to have reachability
78 analysis working correctly. We may have no references to the
79 instrumented function in the code but it still should be counted
80 as reachable if the original function is reachable.
81
82 When original function bodies are not needed anymore we release
83 them and transform functions into a special kind of thunks. Each
84 thunk has a call edge to the instrumented version. These thunks
85 help to keep externally visible instrumented functions visible
86 when linker resolution files are used. Linker has no info about
87 connection between original and instrumented function and
88 therefore we may wrongly decide (due to difference in assembler
89 names) that instrumented function version is local and can be
90 removed. */
91
92 #define CHKP_BOUNDS_OF_SYMBOL_PREFIX "__chkp_bounds_of_"
93
94 /* Build a clone of FNDECL with a modified name. */
95
96 static tree
97 chkp_build_instrumented_fndecl (tree fndecl)
98 {
99 tree new_decl = copy_node (fndecl);
100 tree new_name;
101 std::string s;
102
103 /* called_as_built_in checks DECL_NAME to identify calls to
104 builtins. We want instrumented calls to builtins to be
105 recognized by called_as_built_in. Therefore use original
106 DECL_NAME for cloning with no prefixes. */
107 s = IDENTIFIER_POINTER (DECL_NAME (fndecl));
108 s += ".chkp";
109 DECL_NAME (new_decl) = get_identifier (s.c_str ());
110
111 /* References to the original and to the instrumented version
112 should look the same in the output assembly. And we cannot
113 use the same assembler name for the instrumented version
114 because it conflicts with decl merging algorithms in LTO.
115 Achieve the result by using transparent alias name for the
116 instrumented version. */
117 s = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl));
118 s += ".chkp";
119 new_name = get_identifier (s.c_str ());
120 IDENTIFIER_TRANSPARENT_ALIAS (new_name) = 1;
121 TREE_CHAIN (new_name) = DECL_ASSEMBLER_NAME (fndecl);
122 SET_DECL_ASSEMBLER_NAME (new_decl, new_name);
123
124 /* For functions with body versioning will make a copy of arguments.
125 For functions with no body we need to do it here. */
126 if (!gimple_has_body_p (fndecl))
127 DECL_ARGUMENTS (new_decl) = copy_list (DECL_ARGUMENTS (fndecl));
128
129 /* We are going to modify attributes list and therefore should
130 make own copy. */
131 DECL_ATTRIBUTES (new_decl) = copy_list (DECL_ATTRIBUTES (fndecl));
132
133 return new_decl;
134 }
135
136
137 /* Fix operands of attribute from ATTRS list named ATTR_NAME.
138 Integer operands are replaced with values according to
139 INDEXES map having LEN elements. For operands out of len
140 we just add DELTA. */
141
142 static void
143 chkp_map_attr_arg_indexes (tree attrs, const char *attr_name,
144 unsigned *indexes, int len, int delta)
145 {
146 tree attr = lookup_attribute (attr_name, attrs);
147 tree op;
148
149 if (!attr)
150 return;
151
152 TREE_VALUE (attr) = copy_list (TREE_VALUE (attr));
153 for (op = TREE_VALUE (attr); op; op = TREE_CHAIN (op))
154 {
155 int idx;
156
157 if (TREE_CODE (TREE_VALUE (op)) != INTEGER_CST)
158 continue;
159
160 idx = TREE_INT_CST_LOW (TREE_VALUE (op));
161
162 /* If idx exceeds indexes length then we just
163 keep it at the same distance from the last
164 known arg. */
165 if (idx > len)
166 idx += delta;
167 else
168 idx = indexes[idx - 1] + 1;
169 TREE_VALUE (op) = build_int_cst (TREE_TYPE (TREE_VALUE (op)), idx);
170 }
171 }
172
173 /* Make a copy of function type ORIG_TYPE adding pointer
174 bounds as additional arguments. */
175
176 tree
177 chkp_copy_function_type_adding_bounds (tree orig_type)
178 {
179 tree type;
180 tree arg_type, attrs, t;
181 unsigned len = list_length (TYPE_ARG_TYPES (orig_type));
182 unsigned *indexes = XALLOCAVEC (unsigned, len);
183 unsigned idx = 0, new_idx = 0;
184
185 for (arg_type = TYPE_ARG_TYPES (orig_type);
186 arg_type;
187 arg_type = TREE_CHAIN (arg_type))
188 if (TREE_VALUE (arg_type) == void_type_node)
189 continue;
190 else if (BOUNDED_TYPE_P (TREE_VALUE (arg_type))
191 || pass_by_reference (NULL, TYPE_MODE (TREE_VALUE (arg_type)),
192 TREE_VALUE (arg_type), true)
193 || chkp_type_has_pointer (TREE_VALUE (arg_type)))
194 break;
195
196 /* We may use original type if there are no bounds passed. */
197 if (!arg_type)
198 return orig_type;
199
200 type = copy_node (orig_type);
201 TYPE_ARG_TYPES (type) = copy_list (TYPE_ARG_TYPES (type));
202
203 for (arg_type = TYPE_ARG_TYPES (type);
204 arg_type;
205 arg_type = TREE_CHAIN (arg_type))
206 {
207 indexes[idx++] = new_idx++;
208
209 /* pass_by_reference returns 1 for void type,
210 so check for it first. */
211 if (TREE_VALUE (arg_type) == void_type_node)
212 continue;
213 else if (BOUNDED_TYPE_P (TREE_VALUE (arg_type))
214 || pass_by_reference (NULL, TYPE_MODE (TREE_VALUE (arg_type)),
215 TREE_VALUE (arg_type), true))
216 {
217 tree new_type = build_tree_list (NULL_TREE,
218 pointer_bounds_type_node);
219 TREE_CHAIN (new_type) = TREE_CHAIN (arg_type);
220 TREE_CHAIN (arg_type) = new_type;
221
222 arg_type = TREE_CHAIN (arg_type);
223 new_idx++;
224 }
225 else if (chkp_type_has_pointer (TREE_VALUE (arg_type)))
226 {
227 bitmap slots = BITMAP_ALLOC (NULL);
228 bitmap_iterator bi;
229 unsigned bnd_no;
230
231 chkp_find_bound_slots (TREE_VALUE (arg_type), slots);
232
233 EXECUTE_IF_SET_IN_BITMAP (slots, 0, bnd_no, bi)
234 {
235 tree new_type = build_tree_list (NULL_TREE,
236 pointer_bounds_type_node);
237 TREE_CHAIN (new_type) = TREE_CHAIN (arg_type);
238 TREE_CHAIN (arg_type) = new_type;
239
240 arg_type = TREE_CHAIN (arg_type);
241 new_idx++;
242 }
243 BITMAP_FREE (slots);
244 }
245 }
246
247 /* If function type has attribute with arg indexes then
248 we have to copy it fixing attribute ops. Map for
249 fixing is in indexes array. */
250 attrs = TYPE_ATTRIBUTES (type);
251 if (lookup_attribute ("nonnull", attrs)
252 || lookup_attribute ("format", attrs)
253 || lookup_attribute ("format_arg", attrs))
254 {
255 int delta = new_idx - len;
256 attrs = copy_list (TYPE_ATTRIBUTES (type));
257 chkp_map_attr_arg_indexes (attrs, "nonnull", indexes, len, delta);
258 chkp_map_attr_arg_indexes (attrs, "format", indexes, len, delta);
259 chkp_map_attr_arg_indexes (attrs, "format_arg", indexes, len, delta);
260 TYPE_ATTRIBUTES (type) = attrs;
261 }
262
263 t = TYPE_MAIN_VARIANT (orig_type);
264 if (orig_type != t)
265 {
266 TYPE_MAIN_VARIANT (type) = t;
267 TYPE_NEXT_VARIANT (type) = TYPE_NEXT_VARIANT (t);
268 TYPE_NEXT_VARIANT (t) = type;
269 }
270 else
271 {
272 TYPE_MAIN_VARIANT (type) = type;
273 TYPE_NEXT_VARIANT (type) = NULL;
274 }
275
276
277 return type;
278 }
279
280 /* For given function FNDECL add bounds arguments to arguments
281 list. */
282
283 static void
284 chkp_add_bounds_params_to_function (tree fndecl)
285 {
286 tree arg;
287
288 for (arg = DECL_ARGUMENTS (fndecl); arg; arg = DECL_CHAIN (arg))
289 if (BOUNDED_P (arg))
290 {
291 std::string new_name = CHKP_BOUNDS_OF_SYMBOL_PREFIX;
292 tree new_arg;
293
294 if (DECL_NAME (arg))
295 new_name += IDENTIFIER_POINTER (DECL_NAME (arg));
296 else
297 {
298 char uid[25];
299 snprintf (uid, 25, "D.%u", DECL_UID (arg));
300 new_name += uid;
301 }
302
303 new_arg = build_decl (DECL_SOURCE_LOCATION (arg), PARM_DECL,
304 get_identifier (new_name.c_str ()),
305 pointer_bounds_type_node);
306 DECL_ARG_TYPE (new_arg) = pointer_bounds_type_node;
307 DECL_CONTEXT (new_arg) = DECL_CONTEXT (arg);
308 DECL_ARTIFICIAL (new_arg) = 1;
309 DECL_CHAIN (new_arg) = DECL_CHAIN (arg);
310 DECL_CHAIN (arg) = new_arg;
311
312 arg = DECL_CHAIN (arg);
313
314 }
315 else if (chkp_type_has_pointer (TREE_TYPE (arg)))
316 {
317 tree orig_arg = arg;
318 bitmap slots = BITMAP_ALLOC (NULL);
319 bitmap_iterator bi;
320 unsigned bnd_no;
321
322 chkp_find_bound_slots (TREE_TYPE (arg), slots);
323
324 EXECUTE_IF_SET_IN_BITMAP (slots, 0, bnd_no, bi)
325 {
326 std::string new_name = CHKP_BOUNDS_OF_SYMBOL_PREFIX;
327 tree new_arg;
328 char offs[25];
329
330 if (DECL_NAME (orig_arg))
331 new_name += IDENTIFIER_POINTER (DECL_NAME (orig_arg));
332 else
333 {
334 snprintf (offs, 25, "D.%u", DECL_UID (arg));
335 new_name += offs;
336 }
337 snprintf (offs, 25, "__%u", bnd_no * POINTER_SIZE / BITS_PER_UNIT);
338
339 new_arg = build_decl (DECL_SOURCE_LOCATION (orig_arg),
340 PARM_DECL,
341 get_identifier (new_name.c_str ()),
342 pointer_bounds_type_node);
343 DECL_ARG_TYPE (new_arg) = pointer_bounds_type_node;
344 DECL_CONTEXT (new_arg) = DECL_CONTEXT (orig_arg);
345 DECL_ARTIFICIAL (new_arg) = 1;
346 DECL_CHAIN (new_arg) = DECL_CHAIN (arg);
347 DECL_CHAIN (arg) = new_arg;
348
349 arg = DECL_CHAIN (arg);
350 }
351 BITMAP_FREE (slots);
352 }
353
354 TREE_TYPE (fndecl) =
355 chkp_copy_function_type_adding_bounds (TREE_TYPE (fndecl));
356 }
357
358 /* Return clone created for instrumentation of NODE or NULL. */
359
360 cgraph_node *
361 chkp_maybe_create_clone (tree fndecl)
362 {
363 cgraph_node *node = cgraph_node::get_create (fndecl);
364 cgraph_node *clone = node->instrumented_version;
365
366 gcc_assert (!node->instrumentation_clone);
367
368 if (!clone)
369 {
370 tree new_decl = chkp_build_instrumented_fndecl (fndecl);
371 struct cgraph_edge *e;
372 struct ipa_ref *ref;
373 int i;
374
375 clone = node->create_version_clone (new_decl, vNULL, NULL);
376 clone->externally_visible = node->externally_visible;
377 clone->local = node->local;
378 clone->address_taken = node->address_taken;
379 clone->thunk = node->thunk;
380 clone->alias = node->alias;
381 clone->weakref = node->weakref;
382 clone->cpp_implicit_alias = node->cpp_implicit_alias;
383 clone->instrumented_version = node;
384 clone->orig_decl = fndecl;
385 clone->instrumentation_clone = true;
386 node->instrumented_version = clone;
387
388 if (gimple_has_body_p (fndecl))
389 {
390 /* If function will not be instrumented, then it's instrumented
391 version is a thunk for the original. */
392 if (lookup_attribute ("bnd_legacy", DECL_ATTRIBUTES (fndecl))
393 || (flag_chkp_instrument_marked_only
394 && !lookup_attribute ("bnd_instrument", DECL_ATTRIBUTES (fndecl))))
395 {
396 clone->thunk.thunk_p = true;
397 clone->thunk.add_pointer_bounds_args = true;
398 clone->create_edge (node, NULL, 0, CGRAPH_FREQ_BASE);
399 }
400 else
401 {
402 tree_function_versioning (fndecl, new_decl, NULL, false,
403 NULL, false, NULL, NULL);
404 clone->lowered = true;
405 }
406 }
407
408 /* New params are inserted after versioning because it
409 actually copies args list from the original decl. */
410 chkp_add_bounds_params_to_function (new_decl);
411
412 /* Clones have the same comdat group as originals. */
413 if (node->same_comdat_group
414 || DECL_ONE_ONLY (node->decl))
415 clone->add_to_same_comdat_group (node);
416
417 if (gimple_has_body_p (fndecl))
418 symtab->call_cgraph_insertion_hooks (clone);
419
420 /* Clone all aliases. */
421 for (i = 0; node->iterate_referring (i, ref); i++)
422 if (ref->use == IPA_REF_ALIAS)
423 {
424 struct cgraph_node *alias = dyn_cast <cgraph_node *> (ref->referring);
425 struct cgraph_node *chkp_alias
426 = chkp_maybe_create_clone (alias->decl);
427 chkp_alias->create_reference (clone, IPA_REF_ALIAS, NULL);
428 }
429
430 /* Clone all thunks. */
431 for (e = node->callers; e; e = e->next_caller)
432 if (e->caller->thunk.thunk_p)
433 {
434 struct cgraph_node *thunk
435 = chkp_maybe_create_clone (e->caller->decl);
436 /* Redirect thunk clone edge to the node clone. */
437 thunk->callees->redirect_callee (clone);
438 }
439
440 /* For aliases and thunks we should make sure target is cloned
441 to have proper references and edges. */
442 if (node->thunk.thunk_p)
443 chkp_maybe_create_clone (node->callees->callee->decl);
444 else if (node->alias)
445 {
446 struct cgraph_node *target;
447
448 ref = node->ref_list.first_reference ();
449 if (ref)
450 chkp_maybe_create_clone (ref->referred->decl);
451
452 if (node->alias_target)
453 {
454 if (TREE_CODE (node->alias_target) == FUNCTION_DECL)
455 {
456 target = chkp_maybe_create_clone (node->alias_target);
457 clone->alias_target = target->decl;
458 }
459 else
460 clone->alias_target = node->alias_target;
461 }
462 }
463
464 /* Add IPA reference. It's main role is to keep instrumented
465 version reachable while original node is reachable. */
466 ref = node->create_reference (clone, IPA_REF_CHKP, NULL);
467 }
468
469 return clone;
470 }
471
472 /* Create clone for all functions to be instrumented. */
473
474 static unsigned int
475 chkp_versioning (void)
476 {
477 struct cgraph_node *node;
478
479 bitmap_obstack_initialize (NULL);
480
481 FOR_EACH_DEFINED_FUNCTION (node)
482 {
483 if (!node->instrumentation_clone
484 && !node->instrumented_version
485 && !node->alias
486 && !node->thunk.thunk_p
487 && !lookup_attribute ("bnd_legacy", DECL_ATTRIBUTES (node->decl))
488 && (!flag_chkp_instrument_marked_only
489 || lookup_attribute ("bnd_instrument",
490 DECL_ATTRIBUTES (node->decl)))
491 /* No builtins instrumentation for now. */
492 && DECL_BUILT_IN_CLASS (node->decl) == NOT_BUILT_IN)
493 chkp_maybe_create_clone (node->decl);
494 }
495
496 /* Mark all aliases and thunks of functions with no instrumented
497 version as legacy function. */
498 FOR_EACH_DEFINED_FUNCTION (node)
499 {
500 if (!node->instrumentation_clone
501 && !node->instrumented_version
502 && (node->alias || node->thunk.thunk_p)
503 && !lookup_attribute ("bnd_legacy", DECL_ATTRIBUTES (node->decl)))
504 DECL_ATTRIBUTES (node->decl)
505 = tree_cons (get_identifier ("bnd_legacy"), NULL,
506 DECL_ATTRIBUTES (node->decl));
507 }
508
509 bitmap_obstack_release (NULL);
510
511 return 0;
512 }
513
514 /* In this pass we remove bodies of functions having
515 instrumented version. Functions with removed bodies
516 become a special kind of thunks to provide a connection
517 between calls to the original version and instrumented
518 function. */
519
520 static unsigned int
521 chkp_produce_thunks (void)
522 {
523 struct cgraph_node *node;
524
525 FOR_EACH_DEFINED_FUNCTION (node)
526 {
527 if (!node->instrumentation_clone
528 && node->instrumented_version
529 && gimple_has_body_p (node->decl)
530 && gimple_has_body_p (node->instrumented_version->decl))
531 {
532 node->release_body ();
533 node->remove_callees ();
534 node->remove_all_references ();
535
536 node->thunk.thunk_p = true;
537 node->thunk.add_pointer_bounds_args = true;
538 node->create_edge (node->instrumented_version, NULL,
539 0, CGRAPH_FREQ_BASE);
540 node->create_reference (node->instrumented_version,
541 IPA_REF_CHKP, NULL);
542 }
543 }
544
545 /* Mark instrumentation clones created for aliases and thunks
546 as insttrumented so they could be removed as unreachable
547 now. */
548 FOR_EACH_DEFINED_FUNCTION (node)
549 {
550 if (node->instrumentation_clone
551 && (node->alias || node->thunk.thunk_p)
552 && !chkp_function_instrumented_p (node->decl))
553 chkp_function_mark_instrumented (node->decl);
554 }
555
556 symtab->remove_unreachable_nodes (true, dump_file);
557
558 return 0;
559 }
560
561 const pass_data pass_data_ipa_chkp_versioning =
562 {
563 SIMPLE_IPA_PASS, /* type */
564 "chkp_versioning", /* name */
565 OPTGROUP_NONE, /* optinfo_flags */
566 TV_NONE, /* tv_id */
567 0, /* properties_required */
568 0, /* properties_provided */
569 0, /* properties_destroyed */
570 0, /* todo_flags_start */
571 0 /* todo_flags_finish */
572 };
573
574 const pass_data pass_data_ipa_chkp_produce_thunks =
575 {
576 SIMPLE_IPA_PASS, /* type */
577 "chkp_cleanup", /* name */
578 OPTGROUP_NONE, /* optinfo_flags */
579 TV_NONE, /* tv_id */
580 0, /* properties_required */
581 0, /* properties_provided */
582 0, /* properties_destroyed */
583 0, /* todo_flags_start */
584 0 /* todo_flags_finish */
585 };
586
587 class pass_ipa_chkp_versioning : public simple_ipa_opt_pass
588 {
589 public:
590 pass_ipa_chkp_versioning (gcc::context *ctxt)
591 : simple_ipa_opt_pass (pass_data_ipa_chkp_versioning, ctxt)
592 {}
593
594 /* opt_pass methods: */
595 virtual opt_pass * clone ()
596 {
597 return new pass_ipa_chkp_versioning (m_ctxt);
598 }
599
600 virtual bool gate (function *)
601 {
602 return flag_check_pointer_bounds;
603 }
604
605 virtual unsigned int execute (function *)
606 {
607 return chkp_versioning ();
608 }
609
610 }; // class pass_ipa_chkp_versioning
611
612 class pass_ipa_chkp_produce_thunks : public simple_ipa_opt_pass
613 {
614 public:
615 pass_ipa_chkp_produce_thunks (gcc::context *ctxt)
616 : simple_ipa_opt_pass (pass_data_ipa_chkp_produce_thunks, ctxt)
617 {}
618
619 /* opt_pass methods: */
620 virtual opt_pass * clone ()
621 {
622 return new pass_ipa_chkp_produce_thunks (m_ctxt);
623 }
624
625 virtual bool gate (function *)
626 {
627 return flag_check_pointer_bounds;
628 }
629
630 virtual unsigned int execute (function *)
631 {
632 return chkp_produce_thunks ();
633 }
634
635 }; // class pass_chkp_produce_thunks
636
637 simple_ipa_opt_pass *
638 make_pass_ipa_chkp_versioning (gcc::context *ctxt)
639 {
640 return new pass_ipa_chkp_versioning (ctxt);
641 }
642
643 simple_ipa_opt_pass *
644 make_pass_ipa_chkp_produce_thunks (gcc::context *ctxt)
645 {
646 return new pass_ipa_chkp_produce_thunks (ctxt);
647 }