Daily bump.
[official-gcc.git] / gcc / sanopt.c
blobce9fbcf604a8dbd3be0968316ccae9cc5daa5fcd
1 /* Optimize and expand sanitizer functions.
2 Copyright (C) 2014 Free Software Foundation, Inc.
3 Contributed by Marek Polacek <polacek@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "hash-table.h"
26 #include "predict.h"
27 #include "vec.h"
28 #include "hashtab.h"
29 #include "hash-set.h"
30 #include "tm.h"
31 #include "hard-reg-set.h"
32 #include "function.h"
33 #include "dominance.h"
34 #include "cfg.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
39 #include "is-a.h"
40 #include "gimple.h"
41 #include "gimplify.h"
42 #include "gimple-iterator.h"
43 #include "hash-map.h"
44 #include "plugin-api.h"
45 #include "tree-pass.h"
46 #include "asan.h"
47 #include "gimple-pretty-print.h"
48 #include "tm_p.h"
49 #include "langhooks.h"
50 #include "ubsan.h"
51 #include "params.h"
52 #include "tree-ssa-operands.h"
55 /* This is used to carry information about basic blocks. It is
56 attached to the AUX field of the standard CFG block. */
58 struct sanopt_info
60 /* True if this BB might call (directly or indirectly) free/munmap
61 or similar operation. */
62 bool has_freeing_call_p;
64 /* True if HAS_FREEING_CALL_P flag has been computed. */
65 bool has_freeing_call_computed_p;
67 /* True if there is a block with HAS_FREEING_CALL_P flag set
68 on any path between an immediate dominator of BB, denoted
69 imm(BB), and BB. */
70 bool imm_dom_path_with_freeing_call_p;
72 /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed. */
73 bool imm_dom_path_with_freeing_call_computed_p;
75 /* Number of possibly freeing calls encountered in this bb
76 (so far). */
77 uint64_t freeing_call_events;
79 /* True if BB is currently being visited during computation
80 of IMM_DOM_PATH_WITH_FREEING_CALL_P flag. */
81 bool being_visited_p;
83 /* True if this BB has been visited in the dominator walk. */
84 bool visited_p;
87 /* If T has a single definition of form T = T2, return T2. */
89 static tree
90 maybe_get_single_definition (tree t)
92 if (TREE_CODE (t) == SSA_NAME)
94 gimple g = SSA_NAME_DEF_STMT (t);
95 if (gimple_assign_single_p (g))
96 return gimple_assign_rhs1 (g);
98 return NULL_TREE;
101 /* Traits class for tree hash maps below. */
103 struct tree_map_traits : default_hashmap_traits
105 static inline hashval_t hash (const_tree ref)
107 return iterative_hash_expr (ref, 0);
110 static inline bool equal_keys (const_tree ref1, const_tree ref2)
112 return operand_equal_p (ref1, ref2, 0);
116 /* This is used to carry various hash maps and variables used
117 in sanopt_optimize_walker. */
119 struct sanopt_ctx
121 /* This map maps a pointer (the first argument of UBSAN_NULL) to
122 a vector of UBSAN_NULL call statements that check this pointer. */
123 hash_map<tree, auto_vec<gimple> > null_check_map;
125 /* This map maps a pointer (the second argument of ASAN_CHECK) to
126 a vector of ASAN_CHECK call statements that check the access. */
127 hash_map<tree, auto_vec<gimple>, tree_map_traits> asan_check_map;
129 /* Number of IFN_ASAN_CHECK statements. */
130 int asan_num_accesses;
134 /* Return true if there might be any call to free/munmap operation
135 on any path in between DOM (which should be imm(BB)) and BB. */
137 static bool
138 imm_dom_path_with_freeing_call (basic_block bb, basic_block dom)
140 sanopt_info *info = (sanopt_info *) bb->aux;
141 edge e;
142 edge_iterator ei;
144 if (info->imm_dom_path_with_freeing_call_computed_p)
145 return info->imm_dom_path_with_freeing_call_p;
147 info->being_visited_p = true;
149 FOR_EACH_EDGE (e, ei, bb->preds)
151 sanopt_info *pred_info = (sanopt_info *) e->src->aux;
153 if (e->src == dom)
154 continue;
156 if ((pred_info->imm_dom_path_with_freeing_call_computed_p
157 && pred_info->imm_dom_path_with_freeing_call_p)
158 || (pred_info->has_freeing_call_computed_p
159 && pred_info->has_freeing_call_p))
161 info->imm_dom_path_with_freeing_call_computed_p = true;
162 info->imm_dom_path_with_freeing_call_p = true;
163 info->being_visited_p = false;
164 return true;
168 FOR_EACH_EDGE (e, ei, bb->preds)
170 sanopt_info *pred_info = (sanopt_info *) e->src->aux;
172 if (e->src == dom)
173 continue;
175 if (pred_info->has_freeing_call_computed_p)
176 continue;
178 gimple_stmt_iterator gsi;
179 for (gsi = gsi_start_bb (e->src); !gsi_end_p (gsi); gsi_next (&gsi))
181 gimple stmt = gsi_stmt (gsi);
183 if (is_gimple_call (stmt) && !nonfreeing_call_p (stmt))
185 pred_info->has_freeing_call_p = true;
186 break;
190 pred_info->has_freeing_call_computed_p = true;
191 if (pred_info->has_freeing_call_p)
193 info->imm_dom_path_with_freeing_call_computed_p = true;
194 info->imm_dom_path_with_freeing_call_p = true;
195 info->being_visited_p = false;
196 return true;
200 FOR_EACH_EDGE (e, ei, bb->preds)
202 if (e->src == dom)
203 continue;
205 basic_block src;
206 for (src = e->src; src != dom; )
208 sanopt_info *pred_info = (sanopt_info *) src->aux;
209 if (pred_info->being_visited_p)
210 break;
211 basic_block imm = get_immediate_dominator (CDI_DOMINATORS, src);
212 if (imm_dom_path_with_freeing_call (src, imm))
214 info->imm_dom_path_with_freeing_call_computed_p = true;
215 info->imm_dom_path_with_freeing_call_p = true;
216 info->being_visited_p = false;
217 return true;
219 src = imm;
223 info->imm_dom_path_with_freeing_call_computed_p = true;
224 info->imm_dom_path_with_freeing_call_p = false;
225 info->being_visited_p = false;
226 return false;
229 /* Get the first dominating check from the list of stored checks.
230 Non-dominating checks are silently dropped. */
232 static gimple
233 maybe_get_dominating_check (auto_vec<gimple> &v)
235 for (; !v.is_empty (); v.pop ())
237 gimple g = v.last ();
238 sanopt_info *si = (sanopt_info *) gimple_bb (g)->aux;
239 if (!si->visited_p)
240 /* At this point we shouldn't have any statements
241 that aren't dominating the current BB. */
242 return g;
244 return NULL;
247 /* Optimize away redundant UBSAN_NULL calls. */
249 static bool
250 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx *ctx, gimple stmt)
252 gcc_assert (gimple_call_num_args (stmt) == 3);
253 tree ptr = gimple_call_arg (stmt, 0);
254 tree cur_align = gimple_call_arg (stmt, 2);
255 gcc_assert (TREE_CODE (cur_align) == INTEGER_CST);
256 bool remove = false;
258 auto_vec<gimple> &v = ctx->null_check_map.get_or_insert (ptr);
259 gimple g = maybe_get_dominating_check (v);
260 if (!g)
262 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
263 nothing to optimize yet. */
264 v.safe_push (stmt);
265 return false;
268 /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
269 can drop this one. But only if this check doesn't specify stricter
270 alignment. */
272 tree align = gimple_call_arg (g, 2);
273 int kind = tree_to_shwi (gimple_call_arg (g, 1));
274 /* If this is a NULL pointer check where we had segv anyway, we can
275 remove it. */
276 if (integer_zerop (align)
277 && (kind == UBSAN_LOAD_OF
278 || kind == UBSAN_STORE_OF
279 || kind == UBSAN_MEMBER_ACCESS))
280 remove = true;
281 /* Otherwise remove the check in non-recovering mode, or if the
282 stmts have same location. */
283 else if (integer_zerop (align))
284 remove = (flag_sanitize_recover & SANITIZE_NULL) == 0
285 || flag_sanitize_undefined_trap_on_error
286 || gimple_location (g) == gimple_location (stmt);
287 else if (tree_int_cst_le (cur_align, align))
288 remove = (flag_sanitize_recover & SANITIZE_ALIGNMENT) == 0
289 || flag_sanitize_undefined_trap_on_error
290 || gimple_location (g) == gimple_location (stmt);
292 if (!remove && gimple_bb (g) == gimple_bb (stmt)
293 && tree_int_cst_compare (cur_align, align) == 0)
294 v.pop ();
296 if (!remove)
297 v.safe_push (stmt);
298 return remove;
301 /* Returns TRUE if ASan check of length LEN in block BB can be removed
302 if preceded by checks in V. */
304 static bool
305 can_remove_asan_check (auto_vec<gimple> &v, tree len, basic_block bb)
307 unsigned int i;
308 gimple g;
309 gimple to_pop = NULL;
310 bool remove = false;
311 basic_block last_bb = bb;
312 bool cleanup = false;
314 FOR_EACH_VEC_ELT_REVERSE (v, i, g)
316 basic_block gbb = gimple_bb (g);
317 sanopt_info *si = (sanopt_info *) gbb->aux;
318 if (gimple_uid (g) < si->freeing_call_events)
320 /* If there is a potentially freeing call after g in gbb, we should
321 remove it from the vector, can't use in optimization. */
322 cleanup = true;
323 continue;
326 tree glen = gimple_call_arg (g, 2);
327 gcc_assert (TREE_CODE (glen) == INTEGER_CST);
329 /* If we've checked only smaller length than we want to check now,
330 we can't remove the current stmt. If g is in the same basic block,
331 we want to remove it though, as the current stmt is better. */
332 if (tree_int_cst_lt (glen, len))
334 if (gbb == bb)
336 to_pop = g;
337 cleanup = true;
339 continue;
342 while (last_bb != gbb)
344 /* Paths from last_bb to bb have been checked before.
345 gbb is necessarily a dominator of last_bb, but not necessarily
346 immediate dominator. */
347 if (((sanopt_info *) last_bb->aux)->freeing_call_events)
348 break;
350 basic_block imm = get_immediate_dominator (CDI_DOMINATORS, last_bb);
351 gcc_assert (imm);
352 if (imm_dom_path_with_freeing_call (last_bb, imm))
353 break;
355 last_bb = imm;
357 if (last_bb == gbb)
358 remove = true;
359 break;
362 if (cleanup)
364 unsigned int j = 0, l = v.length ();
365 for (i = 0; i < l; i++)
366 if (v[i] != to_pop
367 && (gimple_uid (v[i])
368 == ((sanopt_info *)
369 gimple_bb (v[i])->aux)->freeing_call_events))
371 if (i != j)
372 v[j] = v[i];
373 j++;
375 v.truncate (j);
378 return remove;
381 /* Optimize away redundant ASAN_CHECK calls. */
383 static bool
384 maybe_optimize_asan_check_ifn (struct sanopt_ctx *ctx, gimple stmt)
386 gcc_assert (gimple_call_num_args (stmt) == 4);
387 tree ptr = gimple_call_arg (stmt, 1);
388 tree len = gimple_call_arg (stmt, 2);
389 basic_block bb = gimple_bb (stmt);
390 sanopt_info *info = (sanopt_info *) bb->aux;
392 if (TREE_CODE (len) != INTEGER_CST)
393 return false;
394 if (integer_zerop (len))
395 return false;
397 gimple_set_uid (stmt, info->freeing_call_events);
399 auto_vec<gimple> *ptr_checks = &ctx->asan_check_map.get_or_insert (ptr);
401 tree base_addr = maybe_get_single_definition (ptr);
402 auto_vec<gimple> *base_checks = NULL;
403 if (base_addr)
405 base_checks = &ctx->asan_check_map.get_or_insert (base_addr);
406 /* Original pointer might have been invalidated. */
407 ptr_checks = ctx->asan_check_map.get (ptr);
410 gimple g = maybe_get_dominating_check (*ptr_checks);
411 gimple g2 = NULL;
413 if (base_checks)
414 /* Try with base address as well. */
415 g2 = maybe_get_dominating_check (*base_checks);
417 if (g == NULL && g2 == NULL)
419 /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
420 nothing to optimize yet. */
421 ptr_checks->safe_push (stmt);
422 if (base_checks)
423 base_checks->safe_push (stmt);
424 return false;
427 bool remove = false;
429 if (ptr_checks)
430 remove = can_remove_asan_check (*ptr_checks, len, bb);
432 if (!remove && base_checks)
433 /* Try with base address as well. */
434 remove = can_remove_asan_check (*base_checks, len, bb);
436 if (!remove)
438 ptr_checks->safe_push (stmt);
439 if (base_checks)
440 base_checks->safe_push (stmt);
443 return remove;
446 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
448 We walk blocks in the CFG via a depth first search of the dominator
449 tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
450 in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
451 blocks. When leaving a block, we mark the block as visited; then
452 when checking the statements in the vector, we ignore statements that
453 are coming from already visited blocks, because these cannot dominate
454 anything anymore. CTX is a sanopt context. */
456 static void
457 sanopt_optimize_walker (basic_block bb, struct sanopt_ctx *ctx)
459 basic_block son;
460 gimple_stmt_iterator gsi;
461 sanopt_info *info = (sanopt_info *) bb->aux;
462 bool asan_check_optimize = (flag_sanitize & SANITIZE_ADDRESS) != 0;
464 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
466 gimple stmt = gsi_stmt (gsi);
467 bool remove = false;
469 if (!is_gimple_call (stmt))
471 /* Handle asm volatile or asm with "memory" clobber
472 the same as potentionally freeing call. */
473 gasm *asm_stmt = dyn_cast <gasm *> (stmt);
474 if (asm_stmt
475 && asan_check_optimize
476 && (gimple_asm_clobbers_memory_p (asm_stmt)
477 || gimple_asm_volatile_p (asm_stmt)))
478 info->freeing_call_events++;
479 gsi_next (&gsi);
480 continue;
483 if (asan_check_optimize && !nonfreeing_call_p (stmt))
484 info->freeing_call_events++;
486 if (gimple_call_internal_p (stmt))
487 switch (gimple_call_internal_fn (stmt))
489 case IFN_UBSAN_NULL:
490 remove = maybe_optimize_ubsan_null_ifn (ctx, stmt);
491 break;
492 case IFN_ASAN_CHECK:
493 if (asan_check_optimize)
494 remove = maybe_optimize_asan_check_ifn (ctx, stmt);
495 if (!remove)
496 ctx->asan_num_accesses++;
497 break;
498 default:
499 break;
502 if (remove)
504 /* Drop this check. */
505 if (dump_file && (dump_flags & TDF_DETAILS))
507 fprintf (dump_file, "Optimizing out\n ");
508 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
509 fprintf (dump_file, "\n");
511 unlink_stmt_vdef (stmt);
512 gsi_remove (&gsi, true);
514 else
515 gsi_next (&gsi);
518 if (asan_check_optimize)
520 info->has_freeing_call_p = info->freeing_call_events != 0;
521 info->has_freeing_call_computed_p = true;
524 for (son = first_dom_son (CDI_DOMINATORS, bb);
525 son;
526 son = next_dom_son (CDI_DOMINATORS, son))
527 sanopt_optimize_walker (son, ctx);
529 /* We're leaving this BB, so mark it to that effect. */
530 info->visited_p = true;
533 /* Try to remove redundant sanitizer checks in function FUN. */
535 static int
536 sanopt_optimize (function *fun)
538 struct sanopt_ctx ctx;
539 ctx.asan_num_accesses = 0;
541 /* Set up block info for each basic block. */
542 alloc_aux_for_blocks (sizeof (sanopt_info));
544 /* We're going to do a dominator walk, so ensure that we have
545 dominance information. */
546 calculate_dominance_info (CDI_DOMINATORS);
548 /* Recursively walk the dominator tree optimizing away
549 redundant checks. */
550 sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun), &ctx);
552 free_aux_for_blocks ();
554 return ctx.asan_num_accesses;
557 /* Perform optimization of sanitize functions. */
559 namespace {
561 const pass_data pass_data_sanopt =
563 GIMPLE_PASS, /* type */
564 "sanopt", /* name */
565 OPTGROUP_NONE, /* optinfo_flags */
566 TV_NONE, /* tv_id */
567 ( PROP_ssa | PROP_cfg | PROP_gimple_leh ), /* properties_required */
568 0, /* properties_provided */
569 0, /* properties_destroyed */
570 0, /* todo_flags_start */
571 TODO_update_ssa, /* todo_flags_finish */
574 class pass_sanopt : public gimple_opt_pass
576 public:
577 pass_sanopt (gcc::context *ctxt)
578 : gimple_opt_pass (pass_data_sanopt, ctxt)
581 /* opt_pass methods: */
582 virtual bool gate (function *) { return flag_sanitize; }
583 virtual unsigned int execute (function *);
585 }; // class pass_sanopt
587 unsigned int
588 pass_sanopt::execute (function *fun)
590 basic_block bb;
591 int asan_num_accesses = 0;
593 /* Try to remove redundant checks. */
594 if (optimize
595 && (flag_sanitize
596 & (SANITIZE_NULL | SANITIZE_ALIGNMENT | SANITIZE_ADDRESS)))
597 asan_num_accesses = sanopt_optimize (fun);
598 else if (flag_sanitize & SANITIZE_ADDRESS)
600 gimple_stmt_iterator gsi;
601 FOR_EACH_BB_FN (bb, fun)
602 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
604 gimple stmt = gsi_stmt (gsi);
605 if (is_gimple_call (stmt) && gimple_call_internal_p (stmt)
606 && gimple_call_internal_fn (stmt) == IFN_ASAN_CHECK)
607 ++asan_num_accesses;
611 bool use_calls = ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD < INT_MAX
612 && asan_num_accesses >= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD;
614 FOR_EACH_BB_FN (bb, fun)
616 gimple_stmt_iterator gsi;
617 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
619 gimple stmt = gsi_stmt (gsi);
620 bool no_next = false;
622 if (!is_gimple_call (stmt))
624 gsi_next (&gsi);
625 continue;
628 if (gimple_call_internal_p (stmt))
630 enum internal_fn ifn = gimple_call_internal_fn (stmt);
631 switch (ifn)
633 case IFN_UBSAN_NULL:
634 no_next = ubsan_expand_null_ifn (&gsi);
635 break;
636 case IFN_UBSAN_BOUNDS:
637 no_next = ubsan_expand_bounds_ifn (&gsi);
638 break;
639 case IFN_UBSAN_OBJECT_SIZE:
640 no_next = ubsan_expand_objsize_ifn (&gsi);
641 break;
642 case IFN_ASAN_CHECK:
643 no_next = asan_expand_check_ifn (&gsi, use_calls);
644 break;
645 default:
646 break;
649 else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
651 tree callee = gimple_call_fndecl (stmt);
652 switch (DECL_FUNCTION_CODE (callee))
654 case BUILT_IN_UNREACHABLE:
655 if (flag_sanitize & SANITIZE_UNREACHABLE
656 && !lookup_attribute ("no_sanitize_undefined",
657 DECL_ATTRIBUTES (fun->decl)))
658 no_next = ubsan_instrument_unreachable (&gsi);
659 break;
660 default:
661 break;
665 if (dump_file && (dump_flags & TDF_DETAILS))
667 fprintf (dump_file, "Expanded\n ");
668 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
669 fprintf (dump_file, "\n");
672 if (!no_next)
673 gsi_next (&gsi);
676 return 0;
679 } // anon namespace
681 gimple_opt_pass *
682 make_pass_sanopt (gcc::context *ctxt)
684 return new pass_sanopt (ctxt);