1 /* Optimize and expand sanitizer functions.
2 Copyright (C) 2014-2016 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
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
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/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
28 #include "tree-ssa-operands.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
31 #include "gimple-iterator.h"
35 #include "tree-hash-traits.h"
36 #include "gimple-ssa.h"
37 #include "tree-phinodes.h"
38 #include "ssa-iterators.h"
41 /* This is used to carry information about basic blocks. It is
42 attached to the AUX field of the standard CFG block. */
46 /* True if this BB might call (directly or indirectly) free/munmap
47 or similar operation. */
48 bool has_freeing_call_p
;
50 /* True if HAS_FREEING_CALL_P flag has been computed. */
51 bool has_freeing_call_computed_p
;
53 /* True if there is a block with HAS_FREEING_CALL_P flag set
54 on any path between an immediate dominator of BB, denoted
56 bool imm_dom_path_with_freeing_call_p
;
58 /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed. */
59 bool imm_dom_path_with_freeing_call_computed_p
;
61 /* Number of possibly freeing calls encountered in this bb
63 uint64_t freeing_call_events
;
65 /* True if BB is currently being visited during computation
66 of IMM_DOM_PATH_WITH_FREEING_CALL_P flag. */
69 /* True if this BB has been visited in the dominator walk. */
73 /* If T has a single definition of form T = T2, return T2. */
76 maybe_get_single_definition (tree t
)
78 if (TREE_CODE (t
) == SSA_NAME
)
80 gimple
*g
= SSA_NAME_DEF_STMT (t
);
81 if (gimple_assign_single_p (g
))
82 return gimple_assign_rhs1 (g
);
87 /* Tree triplet for vptr_check_map. */
88 struct sanopt_tree_triplet
93 /* Traits class for tree triplet hash maps below. */
95 struct sanopt_tree_triplet_hash
: typed_noop_remove
<sanopt_tree_triplet
>
97 typedef sanopt_tree_triplet value_type
;
98 typedef sanopt_tree_triplet compare_type
;
100 static inline hashval_t
101 hash (const sanopt_tree_triplet
&ref
)
103 inchash::hash
hstate (0);
104 inchash::add_expr (ref
.t1
, hstate
);
105 inchash::add_expr (ref
.t2
, hstate
);
106 inchash::add_expr (ref
.t3
, hstate
);
107 return hstate
.end ();
111 equal (const sanopt_tree_triplet
&ref1
, const sanopt_tree_triplet
&ref2
)
113 return operand_equal_p (ref1
.t1
, ref2
.t1
, 0)
114 && operand_equal_p (ref1
.t2
, ref2
.t2
, 0)
115 && operand_equal_p (ref1
.t3
, ref2
.t3
, 0);
119 mark_deleted (sanopt_tree_triplet
&ref
)
121 ref
.t1
= reinterpret_cast<tree
> (1);
125 mark_empty (sanopt_tree_triplet
&ref
)
131 is_deleted (const sanopt_tree_triplet
&ref
)
133 return ref
.t1
== (void *) 1;
137 is_empty (const sanopt_tree_triplet
&ref
)
139 return ref
.t1
== NULL
;
143 /* This is used to carry various hash maps and variables used
144 in sanopt_optimize_walker. */
148 /* This map maps a pointer (the first argument of UBSAN_NULL) to
149 a vector of UBSAN_NULL call statements that check this pointer. */
150 hash_map
<tree
, auto_vec
<gimple
*> > null_check_map
;
152 /* This map maps a pointer (the second argument of ASAN_CHECK) to
153 a vector of ASAN_CHECK call statements that check the access. */
154 hash_map
<tree_operand_hash
, auto_vec
<gimple
*> > asan_check_map
;
156 /* This map maps a tree triplet (the first, second and fourth argument
157 of UBSAN_VPTR) to a vector of UBSAN_VPTR call statements that check
158 that virtual table pointer. */
159 hash_map
<sanopt_tree_triplet_hash
, auto_vec
<gimple
*> > vptr_check_map
;
161 /* Number of IFN_ASAN_CHECK statements. */
162 int asan_num_accesses
;
166 /* Return true if there might be any call to free/munmap operation
167 on any path in between DOM (which should be imm(BB)) and BB. */
170 imm_dom_path_with_freeing_call (basic_block bb
, basic_block dom
)
172 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
176 if (info
->imm_dom_path_with_freeing_call_computed_p
)
177 return info
->imm_dom_path_with_freeing_call_p
;
179 info
->being_visited_p
= true;
181 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
183 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
188 if ((pred_info
->imm_dom_path_with_freeing_call_computed_p
189 && pred_info
->imm_dom_path_with_freeing_call_p
)
190 || (pred_info
->has_freeing_call_computed_p
191 && 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;
200 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
202 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
207 if (pred_info
->has_freeing_call_computed_p
)
210 gimple_stmt_iterator gsi
;
211 for (gsi
= gsi_start_bb (e
->src
); !gsi_end_p (gsi
); gsi_next (&gsi
))
213 gimple
*stmt
= gsi_stmt (gsi
);
215 if (is_gimple_call (stmt
) && !nonfreeing_call_p (stmt
))
217 pred_info
->has_freeing_call_p
= true;
222 pred_info
->has_freeing_call_computed_p
= true;
223 if (pred_info
->has_freeing_call_p
)
225 info
->imm_dom_path_with_freeing_call_computed_p
= true;
226 info
->imm_dom_path_with_freeing_call_p
= true;
227 info
->being_visited_p
= false;
232 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
238 for (src
= e
->src
; src
!= dom
; )
240 sanopt_info
*pred_info
= (sanopt_info
*) src
->aux
;
241 if (pred_info
->being_visited_p
)
243 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, src
);
244 if (imm_dom_path_with_freeing_call (src
, imm
))
246 info
->imm_dom_path_with_freeing_call_computed_p
= true;
247 info
->imm_dom_path_with_freeing_call_p
= true;
248 info
->being_visited_p
= false;
255 info
->imm_dom_path_with_freeing_call_computed_p
= true;
256 info
->imm_dom_path_with_freeing_call_p
= false;
257 info
->being_visited_p
= false;
261 /* Get the first dominating check from the list of stored checks.
262 Non-dominating checks are silently dropped. */
265 maybe_get_dominating_check (auto_vec
<gimple
*> &v
)
267 for (; !v
.is_empty (); v
.pop ())
269 gimple
*g
= v
.last ();
270 sanopt_info
*si
= (sanopt_info
*) gimple_bb (g
)->aux
;
272 /* At this point we shouldn't have any statements
273 that aren't dominating the current BB. */
279 /* Optimize away redundant UBSAN_NULL calls. */
282 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx
*ctx
, gimple
*stmt
)
284 gcc_assert (gimple_call_num_args (stmt
) == 3);
285 tree ptr
= gimple_call_arg (stmt
, 0);
286 tree cur_align
= gimple_call_arg (stmt
, 2);
287 gcc_assert (TREE_CODE (cur_align
) == INTEGER_CST
);
290 auto_vec
<gimple
*> &v
= ctx
->null_check_map
.get_or_insert (ptr
);
291 gimple
*g
= maybe_get_dominating_check (v
);
294 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
295 nothing to optimize yet. */
300 /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
301 can drop this one. But only if this check doesn't specify stricter
304 tree align
= gimple_call_arg (g
, 2);
305 int kind
= tree_to_shwi (gimple_call_arg (g
, 1));
306 /* If this is a NULL pointer check where we had segv anyway, we can
308 if (integer_zerop (align
)
309 && (kind
== UBSAN_LOAD_OF
310 || kind
== UBSAN_STORE_OF
311 || kind
== UBSAN_MEMBER_ACCESS
))
313 /* Otherwise remove the check in non-recovering mode, or if the
314 stmts have same location. */
315 else if (integer_zerop (align
))
316 remove
= (flag_sanitize_recover
& SANITIZE_NULL
) == 0
317 || flag_sanitize_undefined_trap_on_error
318 || gimple_location (g
) == gimple_location (stmt
);
319 else if (tree_int_cst_le (cur_align
, align
))
320 remove
= (flag_sanitize_recover
& SANITIZE_ALIGNMENT
) == 0
321 || flag_sanitize_undefined_trap_on_error
322 || gimple_location (g
) == gimple_location (stmt
);
324 if (!remove
&& gimple_bb (g
) == gimple_bb (stmt
)
325 && tree_int_cst_compare (cur_align
, align
) == 0)
333 /* Optimize away redundant UBSAN_VPTR calls. The second argument
334 is the value loaded from the virtual table, so rely on FRE to find out
335 when we can actually optimize. */
338 maybe_optimize_ubsan_vptr_ifn (struct sanopt_ctx
*ctx
, gimple
*stmt
)
340 gcc_assert (gimple_call_num_args (stmt
) == 5);
341 sanopt_tree_triplet triplet
;
342 triplet
.t1
= gimple_call_arg (stmt
, 0);
343 triplet
.t2
= gimple_call_arg (stmt
, 1);
344 triplet
.t3
= gimple_call_arg (stmt
, 3);
346 auto_vec
<gimple
*> &v
= ctx
->vptr_check_map
.get_or_insert (triplet
);
347 gimple
*g
= maybe_get_dominating_check (v
);
350 /* For this PTR we don't have any UBSAN_VPTR stmts recorded, so there's
351 nothing to optimize yet. */
359 /* Returns TRUE if ASan check of length LEN in block BB can be removed
360 if preceded by checks in V. */
363 can_remove_asan_check (auto_vec
<gimple
*> &v
, tree len
, basic_block bb
)
367 gimple
*to_pop
= NULL
;
369 basic_block last_bb
= bb
;
370 bool cleanup
= false;
372 FOR_EACH_VEC_ELT_REVERSE (v
, i
, g
)
374 basic_block gbb
= gimple_bb (g
);
375 sanopt_info
*si
= (sanopt_info
*) gbb
->aux
;
376 if (gimple_uid (g
) < si
->freeing_call_events
)
378 /* If there is a potentially freeing call after g in gbb, we should
379 remove it from the vector, can't use in optimization. */
384 tree glen
= gimple_call_arg (g
, 2);
385 gcc_assert (TREE_CODE (glen
) == INTEGER_CST
);
387 /* If we've checked only smaller length than we want to check now,
388 we can't remove the current stmt. If g is in the same basic block,
389 we want to remove it though, as the current stmt is better. */
390 if (tree_int_cst_lt (glen
, len
))
400 while (last_bb
!= gbb
)
402 /* Paths from last_bb to bb have been checked before.
403 gbb is necessarily a dominator of last_bb, but not necessarily
404 immediate dominator. */
405 if (((sanopt_info
*) last_bb
->aux
)->freeing_call_events
)
408 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, last_bb
);
410 if (imm_dom_path_with_freeing_call (last_bb
, imm
))
422 unsigned int j
= 0, l
= v
.length ();
423 for (i
= 0; i
< l
; i
++)
425 && (gimple_uid (v
[i
])
427 gimple_bb (v
[i
])->aux
)->freeing_call_events
))
439 /* Optimize away redundant ASAN_CHECK calls. */
442 maybe_optimize_asan_check_ifn (struct sanopt_ctx
*ctx
, gimple
*stmt
)
444 gcc_assert (gimple_call_num_args (stmt
) == 4);
445 tree ptr
= gimple_call_arg (stmt
, 1);
446 tree len
= gimple_call_arg (stmt
, 2);
447 basic_block bb
= gimple_bb (stmt
);
448 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
450 if (TREE_CODE (len
) != INTEGER_CST
)
452 if (integer_zerop (len
))
455 gimple_set_uid (stmt
, info
->freeing_call_events
);
457 auto_vec
<gimple
*> *ptr_checks
= &ctx
->asan_check_map
.get_or_insert (ptr
);
459 tree base_addr
= maybe_get_single_definition (ptr
);
460 auto_vec
<gimple
*> *base_checks
= NULL
;
463 base_checks
= &ctx
->asan_check_map
.get_or_insert (base_addr
);
464 /* Original pointer might have been invalidated. */
465 ptr_checks
= ctx
->asan_check_map
.get (ptr
);
468 gimple
*g
= maybe_get_dominating_check (*ptr_checks
);
472 /* Try with base address as well. */
473 g2
= maybe_get_dominating_check (*base_checks
);
475 if (g
== NULL
&& g2
== NULL
)
477 /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
478 nothing to optimize yet. */
479 ptr_checks
->safe_push (stmt
);
481 base_checks
->safe_push (stmt
);
488 remove
= can_remove_asan_check (*ptr_checks
, len
, bb
);
490 if (!remove
&& base_checks
)
491 /* Try with base address as well. */
492 remove
= can_remove_asan_check (*base_checks
, len
, bb
);
496 ptr_checks
->safe_push (stmt
);
498 base_checks
->safe_push (stmt
);
504 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
506 We walk blocks in the CFG via a depth first search of the dominator
507 tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
508 in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
509 blocks. When leaving a block, we mark the block as visited; then
510 when checking the statements in the vector, we ignore statements that
511 are coming from already visited blocks, because these cannot dominate
512 anything anymore. CTX is a sanopt context. */
515 sanopt_optimize_walker (basic_block bb
, struct sanopt_ctx
*ctx
)
518 gimple_stmt_iterator gsi
;
519 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
520 bool asan_check_optimize
= (flag_sanitize
& SANITIZE_ADDRESS
) != 0;
522 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
524 gimple
*stmt
= gsi_stmt (gsi
);
527 if (!is_gimple_call (stmt
))
529 /* Handle asm volatile or asm with "memory" clobber
530 the same as potentionally freeing call. */
531 gasm
*asm_stmt
= dyn_cast
<gasm
*> (stmt
);
533 && asan_check_optimize
534 && (gimple_asm_clobbers_memory_p (asm_stmt
)
535 || gimple_asm_volatile_p (asm_stmt
)))
536 info
->freeing_call_events
++;
541 if (asan_check_optimize
&& !nonfreeing_call_p (stmt
))
542 info
->freeing_call_events
++;
544 /* If __asan_before_dynamic_init ("module"); is followed by
545 __asan_after_dynamic_init (); without intervening memory loads/stores,
546 there is nothing to guard, so optimize both away. */
547 if (asan_check_optimize
548 && gimple_call_builtin_p (stmt
, BUILT_IN_ASAN_BEFORE_DYNAMIC_INIT
))
552 if (single_imm_use (gimple_vdef (stmt
), &use
, &use_stmt
))
554 if (is_gimple_call (use_stmt
)
555 && gimple_call_builtin_p (use_stmt
,
556 BUILT_IN_ASAN_AFTER_DYNAMIC_INIT
))
558 unlink_stmt_vdef (use_stmt
);
559 gimple_stmt_iterator gsi2
= gsi_for_stmt (use_stmt
);
560 gsi_remove (&gsi2
, true);
566 if (gimple_call_internal_p (stmt
))
567 switch (gimple_call_internal_fn (stmt
))
570 remove
= maybe_optimize_ubsan_null_ifn (ctx
, stmt
);
573 remove
= maybe_optimize_ubsan_vptr_ifn (ctx
, stmt
);
576 if (asan_check_optimize
)
577 remove
= maybe_optimize_asan_check_ifn (ctx
, stmt
);
579 ctx
->asan_num_accesses
++;
587 /* Drop this check. */
588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
590 fprintf (dump_file
, "Optimizing out\n ");
591 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
592 fprintf (dump_file
, "\n");
594 unlink_stmt_vdef (stmt
);
595 gsi_remove (&gsi
, true);
601 if (asan_check_optimize
)
603 info
->has_freeing_call_p
= info
->freeing_call_events
!= 0;
604 info
->has_freeing_call_computed_p
= true;
607 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
609 son
= next_dom_son (CDI_DOMINATORS
, son
))
610 sanopt_optimize_walker (son
, ctx
);
612 /* We're leaving this BB, so mark it to that effect. */
613 info
->visited_p
= true;
616 /* Try to remove redundant sanitizer checks in function FUN. */
619 sanopt_optimize (function
*fun
)
621 struct sanopt_ctx ctx
;
622 ctx
.asan_num_accesses
= 0;
624 /* Set up block info for each basic block. */
625 alloc_aux_for_blocks (sizeof (sanopt_info
));
627 /* We're going to do a dominator walk, so ensure that we have
628 dominance information. */
629 calculate_dominance_info (CDI_DOMINATORS
);
631 /* Recursively walk the dominator tree optimizing away
633 sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun
), &ctx
);
635 free_aux_for_blocks ();
637 return ctx
.asan_num_accesses
;
640 /* Perform optimization of sanitize functions. */
644 const pass_data pass_data_sanopt
=
646 GIMPLE_PASS
, /* type */
648 OPTGROUP_NONE
, /* optinfo_flags */
650 ( PROP_ssa
| PROP_cfg
| PROP_gimple_leh
), /* properties_required */
651 0, /* properties_provided */
652 0, /* properties_destroyed */
653 0, /* todo_flags_start */
654 TODO_update_ssa
, /* todo_flags_finish */
657 class pass_sanopt
: public gimple_opt_pass
660 pass_sanopt (gcc::context
*ctxt
)
661 : gimple_opt_pass (pass_data_sanopt
, ctxt
)
664 /* opt_pass methods: */
665 virtual bool gate (function
*) { return flag_sanitize
; }
666 virtual unsigned int execute (function
*);
668 }; // class pass_sanopt
671 pass_sanopt::execute (function
*fun
)
674 int asan_num_accesses
= 0;
676 /* Try to remove redundant checks. */
679 & (SANITIZE_NULL
| SANITIZE_ALIGNMENT
680 | SANITIZE_ADDRESS
| SANITIZE_VPTR
)))
681 asan_num_accesses
= sanopt_optimize (fun
);
682 else if (flag_sanitize
& SANITIZE_ADDRESS
)
684 gimple_stmt_iterator gsi
;
685 FOR_EACH_BB_FN (bb
, fun
)
686 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
688 gimple
*stmt
= gsi_stmt (gsi
);
689 if (gimple_call_internal_p (stmt
, IFN_ASAN_CHECK
))
694 bool use_calls
= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
< INT_MAX
695 && asan_num_accesses
>= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
;
697 FOR_EACH_BB_FN (bb
, fun
)
699 gimple_stmt_iterator gsi
;
700 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
702 gimple
*stmt
= gsi_stmt (gsi
);
703 bool no_next
= false;
705 if (!is_gimple_call (stmt
))
711 if (gimple_call_internal_p (stmt
))
713 enum internal_fn ifn
= gimple_call_internal_fn (stmt
);
717 no_next
= ubsan_expand_null_ifn (&gsi
);
719 case IFN_UBSAN_BOUNDS
:
720 no_next
= ubsan_expand_bounds_ifn (&gsi
);
722 case IFN_UBSAN_OBJECT_SIZE
:
723 no_next
= ubsan_expand_objsize_ifn (&gsi
);
726 no_next
= ubsan_expand_vptr_ifn (&gsi
);
729 no_next
= asan_expand_check_ifn (&gsi
, use_calls
);
735 else if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
737 tree callee
= gimple_call_fndecl (stmt
);
738 switch (DECL_FUNCTION_CODE (callee
))
740 case BUILT_IN_UNREACHABLE
:
741 if (flag_sanitize
& SANITIZE_UNREACHABLE
742 && !lookup_attribute ("no_sanitize_undefined",
743 DECL_ATTRIBUTES (fun
->decl
)))
744 no_next
= ubsan_instrument_unreachable (&gsi
);
751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
753 fprintf (dump_file
, "Expanded\n ");
754 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
755 fprintf (dump_file
, "\n");
768 make_pass_sanopt (gcc::context
*ctxt
)
770 return new pass_sanopt (ctxt
);