1 /* Optimize and expand sanitizer functions.
2 Copyright (C) 2014-2015 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"
29 #include "fold-const.h"
32 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
39 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "plugin-api.h"
45 #include "tree-pass.h"
47 #include "gimple-pretty-print.h"
49 #include "langhooks.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. */
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
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
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. */
83 /* True if this BB has been visited in the dominator walk. */
87 /* If T has a single definition of form T = T2, return T2. */
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
);
101 /* Traits class for tree hash maps below. */
103 struct sanopt_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 /* Tree triplet for vptr_check_map. */
117 struct sanopt_tree_triplet
122 /* Traits class for tree triplet hash maps below. */
124 struct sanopt_tree_triplet_map_traits
: default_hashmap_traits
126 static inline hashval_t
127 hash (const sanopt_tree_triplet
&ref
)
129 inchash::hash
hstate (0);
130 inchash::add_expr (ref
.t1
, hstate
);
131 inchash::add_expr (ref
.t2
, hstate
);
132 inchash::add_expr (ref
.t3
, hstate
);
133 return hstate
.end ();
137 equal_keys (const sanopt_tree_triplet
&ref1
, const sanopt_tree_triplet
&ref2
)
139 return operand_equal_p (ref1
.t1
, ref2
.t1
, 0)
140 && operand_equal_p (ref1
.t2
, ref2
.t2
, 0)
141 && operand_equal_p (ref1
.t3
, ref2
.t3
, 0);
148 e
.m_key
.t1
= reinterpret_cast<T
*> (1);
162 return e
.m_key
.t1
== (void *) 1;
169 return e
.m_key
.t1
== NULL
;
173 /* This is used to carry various hash maps and variables used
174 in sanopt_optimize_walker. */
178 /* This map maps a pointer (the first argument of UBSAN_NULL) to
179 a vector of UBSAN_NULL call statements that check this pointer. */
180 hash_map
<tree
, auto_vec
<gimple
> > null_check_map
;
182 /* This map maps a pointer (the second argument of ASAN_CHECK) to
183 a vector of ASAN_CHECK call statements that check the access. */
184 hash_map
<tree
, auto_vec
<gimple
>, sanopt_tree_map_traits
> asan_check_map
;
186 /* This map maps a tree triplet (the first, second and fourth argument
187 of UBSAN_VPTR) to a vector of UBSAN_VPTR call statements that check
188 that virtual table pointer. */
189 hash_map
<sanopt_tree_triplet
, auto_vec
<gimple
>,
190 sanopt_tree_triplet_map_traits
> vptr_check_map
;
192 /* Number of IFN_ASAN_CHECK statements. */
193 int asan_num_accesses
;
197 /* Return true if there might be any call to free/munmap operation
198 on any path in between DOM (which should be imm(BB)) and BB. */
201 imm_dom_path_with_freeing_call (basic_block bb
, basic_block dom
)
203 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
207 if (info
->imm_dom_path_with_freeing_call_computed_p
)
208 return info
->imm_dom_path_with_freeing_call_p
;
210 info
->being_visited_p
= true;
212 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
214 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
219 if ((pred_info
->imm_dom_path_with_freeing_call_computed_p
220 && pred_info
->imm_dom_path_with_freeing_call_p
)
221 || (pred_info
->has_freeing_call_computed_p
222 && pred_info
->has_freeing_call_p
))
224 info
->imm_dom_path_with_freeing_call_computed_p
= true;
225 info
->imm_dom_path_with_freeing_call_p
= true;
226 info
->being_visited_p
= false;
231 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
233 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
238 if (pred_info
->has_freeing_call_computed_p
)
241 gimple_stmt_iterator gsi
;
242 for (gsi
= gsi_start_bb (e
->src
); !gsi_end_p (gsi
); gsi_next (&gsi
))
244 gimple stmt
= gsi_stmt (gsi
);
246 if (is_gimple_call (stmt
) && !nonfreeing_call_p (stmt
))
248 pred_info
->has_freeing_call_p
= true;
253 pred_info
->has_freeing_call_computed_p
= true;
254 if (pred_info
->has_freeing_call_p
)
256 info
->imm_dom_path_with_freeing_call_computed_p
= true;
257 info
->imm_dom_path_with_freeing_call_p
= true;
258 info
->being_visited_p
= false;
263 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
269 for (src
= e
->src
; src
!= dom
; )
271 sanopt_info
*pred_info
= (sanopt_info
*) src
->aux
;
272 if (pred_info
->being_visited_p
)
274 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, src
);
275 if (imm_dom_path_with_freeing_call (src
, imm
))
277 info
->imm_dom_path_with_freeing_call_computed_p
= true;
278 info
->imm_dom_path_with_freeing_call_p
= true;
279 info
->being_visited_p
= false;
286 info
->imm_dom_path_with_freeing_call_computed_p
= true;
287 info
->imm_dom_path_with_freeing_call_p
= false;
288 info
->being_visited_p
= false;
292 /* Get the first dominating check from the list of stored checks.
293 Non-dominating checks are silently dropped. */
296 maybe_get_dominating_check (auto_vec
<gimple
> &v
)
298 for (; !v
.is_empty (); v
.pop ())
300 gimple g
= v
.last ();
301 sanopt_info
*si
= (sanopt_info
*) gimple_bb (g
)->aux
;
303 /* At this point we shouldn't have any statements
304 that aren't dominating the current BB. */
310 /* Optimize away redundant UBSAN_NULL calls. */
313 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
315 gcc_assert (gimple_call_num_args (stmt
) == 3);
316 tree ptr
= gimple_call_arg (stmt
, 0);
317 tree cur_align
= gimple_call_arg (stmt
, 2);
318 gcc_assert (TREE_CODE (cur_align
) == INTEGER_CST
);
321 auto_vec
<gimple
> &v
= ctx
->null_check_map
.get_or_insert (ptr
);
322 gimple g
= maybe_get_dominating_check (v
);
325 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
326 nothing to optimize yet. */
331 /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
332 can drop this one. But only if this check doesn't specify stricter
335 tree align
= gimple_call_arg (g
, 2);
336 int kind
= tree_to_shwi (gimple_call_arg (g
, 1));
337 /* If this is a NULL pointer check where we had segv anyway, we can
339 if (integer_zerop (align
)
340 && (kind
== UBSAN_LOAD_OF
341 || kind
== UBSAN_STORE_OF
342 || kind
== UBSAN_MEMBER_ACCESS
))
344 /* Otherwise remove the check in non-recovering mode, or if the
345 stmts have same location. */
346 else if (integer_zerop (align
))
347 remove
= (flag_sanitize_recover
& SANITIZE_NULL
) == 0
348 || flag_sanitize_undefined_trap_on_error
349 || gimple_location (g
) == gimple_location (stmt
);
350 else if (tree_int_cst_le (cur_align
, align
))
351 remove
= (flag_sanitize_recover
& SANITIZE_ALIGNMENT
) == 0
352 || flag_sanitize_undefined_trap_on_error
353 || gimple_location (g
) == gimple_location (stmt
);
355 if (!remove
&& gimple_bb (g
) == gimple_bb (stmt
)
356 && tree_int_cst_compare (cur_align
, align
) == 0)
364 /* Optimize away redundant UBSAN_VPTR calls. The second argument
365 is the value loaded from the virtual table, so rely on FRE to find out
366 when we can actually optimize. */
369 maybe_optimize_ubsan_vptr_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
371 gcc_assert (gimple_call_num_args (stmt
) == 5);
372 sanopt_tree_triplet triplet
;
373 triplet
.t1
= gimple_call_arg (stmt
, 0);
374 triplet
.t2
= gimple_call_arg (stmt
, 1);
375 triplet
.t3
= gimple_call_arg (stmt
, 3);
377 auto_vec
<gimple
> &v
= ctx
->vptr_check_map
.get_or_insert (triplet
);
378 gimple g
= maybe_get_dominating_check (v
);
381 /* For this PTR we don't have any UBSAN_VPTR stmts recorded, so there's
382 nothing to optimize yet. */
390 /* Returns TRUE if ASan check of length LEN in block BB can be removed
391 if preceded by checks in V. */
394 can_remove_asan_check (auto_vec
<gimple
> &v
, tree len
, basic_block bb
)
398 gimple to_pop
= NULL
;
400 basic_block last_bb
= bb
;
401 bool cleanup
= false;
403 FOR_EACH_VEC_ELT_REVERSE (v
, i
, g
)
405 basic_block gbb
= gimple_bb (g
);
406 sanopt_info
*si
= (sanopt_info
*) gbb
->aux
;
407 if (gimple_uid (g
) < si
->freeing_call_events
)
409 /* If there is a potentially freeing call after g in gbb, we should
410 remove it from the vector, can't use in optimization. */
415 tree glen
= gimple_call_arg (g
, 2);
416 gcc_assert (TREE_CODE (glen
) == INTEGER_CST
);
418 /* If we've checked only smaller length than we want to check now,
419 we can't remove the current stmt. If g is in the same basic block,
420 we want to remove it though, as the current stmt is better. */
421 if (tree_int_cst_lt (glen
, len
))
431 while (last_bb
!= gbb
)
433 /* Paths from last_bb to bb have been checked before.
434 gbb is necessarily a dominator of last_bb, but not necessarily
435 immediate dominator. */
436 if (((sanopt_info
*) last_bb
->aux
)->freeing_call_events
)
439 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, last_bb
);
441 if (imm_dom_path_with_freeing_call (last_bb
, imm
))
453 unsigned int j
= 0, l
= v
.length ();
454 for (i
= 0; i
< l
; i
++)
456 && (gimple_uid (v
[i
])
458 gimple_bb (v
[i
])->aux
)->freeing_call_events
))
470 /* Optimize away redundant ASAN_CHECK calls. */
473 maybe_optimize_asan_check_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
475 gcc_assert (gimple_call_num_args (stmt
) == 4);
476 tree ptr
= gimple_call_arg (stmt
, 1);
477 tree len
= gimple_call_arg (stmt
, 2);
478 basic_block bb
= gimple_bb (stmt
);
479 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
481 if (TREE_CODE (len
) != INTEGER_CST
)
483 if (integer_zerop (len
))
486 gimple_set_uid (stmt
, info
->freeing_call_events
);
488 auto_vec
<gimple
> *ptr_checks
= &ctx
->asan_check_map
.get_or_insert (ptr
);
490 tree base_addr
= maybe_get_single_definition (ptr
);
491 auto_vec
<gimple
> *base_checks
= NULL
;
494 base_checks
= &ctx
->asan_check_map
.get_or_insert (base_addr
);
495 /* Original pointer might have been invalidated. */
496 ptr_checks
= ctx
->asan_check_map
.get (ptr
);
499 gimple g
= maybe_get_dominating_check (*ptr_checks
);
503 /* Try with base address as well. */
504 g2
= maybe_get_dominating_check (*base_checks
);
506 if (g
== NULL
&& g2
== NULL
)
508 /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
509 nothing to optimize yet. */
510 ptr_checks
->safe_push (stmt
);
512 base_checks
->safe_push (stmt
);
519 remove
= can_remove_asan_check (*ptr_checks
, len
, bb
);
521 if (!remove
&& base_checks
)
522 /* Try with base address as well. */
523 remove
= can_remove_asan_check (*base_checks
, len
, bb
);
527 ptr_checks
->safe_push (stmt
);
529 base_checks
->safe_push (stmt
);
535 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
537 We walk blocks in the CFG via a depth first search of the dominator
538 tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
539 in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
540 blocks. When leaving a block, we mark the block as visited; then
541 when checking the statements in the vector, we ignore statements that
542 are coming from already visited blocks, because these cannot dominate
543 anything anymore. CTX is a sanopt context. */
546 sanopt_optimize_walker (basic_block bb
, struct sanopt_ctx
*ctx
)
549 gimple_stmt_iterator gsi
;
550 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
551 bool asan_check_optimize
= (flag_sanitize
& SANITIZE_ADDRESS
) != 0;
553 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
555 gimple stmt
= gsi_stmt (gsi
);
558 if (!is_gimple_call (stmt
))
560 /* Handle asm volatile or asm with "memory" clobber
561 the same as potentionally freeing call. */
562 gasm
*asm_stmt
= dyn_cast
<gasm
*> (stmt
);
564 && asan_check_optimize
565 && (gimple_asm_clobbers_memory_p (asm_stmt
)
566 || gimple_asm_volatile_p (asm_stmt
)))
567 info
->freeing_call_events
++;
572 if (asan_check_optimize
&& !nonfreeing_call_p (stmt
))
573 info
->freeing_call_events
++;
575 if (gimple_call_internal_p (stmt
))
576 switch (gimple_call_internal_fn (stmt
))
579 remove
= maybe_optimize_ubsan_null_ifn (ctx
, stmt
);
582 remove
= maybe_optimize_ubsan_vptr_ifn (ctx
, stmt
);
585 if (asan_check_optimize
)
586 remove
= maybe_optimize_asan_check_ifn (ctx
, stmt
);
588 ctx
->asan_num_accesses
++;
596 /* Drop this check. */
597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
599 fprintf (dump_file
, "Optimizing out\n ");
600 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
601 fprintf (dump_file
, "\n");
603 unlink_stmt_vdef (stmt
);
604 gsi_remove (&gsi
, true);
610 if (asan_check_optimize
)
612 info
->has_freeing_call_p
= info
->freeing_call_events
!= 0;
613 info
->has_freeing_call_computed_p
= true;
616 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
618 son
= next_dom_son (CDI_DOMINATORS
, son
))
619 sanopt_optimize_walker (son
, ctx
);
621 /* We're leaving this BB, so mark it to that effect. */
622 info
->visited_p
= true;
625 /* Try to remove redundant sanitizer checks in function FUN. */
628 sanopt_optimize (function
*fun
)
630 struct sanopt_ctx ctx
;
631 ctx
.asan_num_accesses
= 0;
633 /* Set up block info for each basic block. */
634 alloc_aux_for_blocks (sizeof (sanopt_info
));
636 /* We're going to do a dominator walk, so ensure that we have
637 dominance information. */
638 calculate_dominance_info (CDI_DOMINATORS
);
640 /* Recursively walk the dominator tree optimizing away
642 sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun
), &ctx
);
644 free_aux_for_blocks ();
646 return ctx
.asan_num_accesses
;
649 /* Perform optimization of sanitize functions. */
653 const pass_data pass_data_sanopt
=
655 GIMPLE_PASS
, /* type */
657 OPTGROUP_NONE
, /* optinfo_flags */
659 ( PROP_ssa
| PROP_cfg
| PROP_gimple_leh
), /* properties_required */
660 0, /* properties_provided */
661 0, /* properties_destroyed */
662 0, /* todo_flags_start */
663 TODO_update_ssa
, /* todo_flags_finish */
666 class pass_sanopt
: public gimple_opt_pass
669 pass_sanopt (gcc::context
*ctxt
)
670 : gimple_opt_pass (pass_data_sanopt
, ctxt
)
673 /* opt_pass methods: */
674 virtual bool gate (function
*) { return flag_sanitize
; }
675 virtual unsigned int execute (function
*);
677 }; // class pass_sanopt
680 pass_sanopt::execute (function
*fun
)
683 int asan_num_accesses
= 0;
685 /* Try to remove redundant checks. */
688 & (SANITIZE_NULL
| SANITIZE_ALIGNMENT
689 | SANITIZE_ADDRESS
| SANITIZE_VPTR
)))
690 asan_num_accesses
= sanopt_optimize (fun
);
691 else if (flag_sanitize
& SANITIZE_ADDRESS
)
693 gimple_stmt_iterator gsi
;
694 FOR_EACH_BB_FN (bb
, fun
)
695 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
697 gimple stmt
= gsi_stmt (gsi
);
698 if (is_gimple_call (stmt
) && gimple_call_internal_p (stmt
)
699 && gimple_call_internal_fn (stmt
) == IFN_ASAN_CHECK
)
704 bool use_calls
= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
< INT_MAX
705 && asan_num_accesses
>= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
;
707 FOR_EACH_BB_FN (bb
, fun
)
709 gimple_stmt_iterator gsi
;
710 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
712 gimple stmt
= gsi_stmt (gsi
);
713 bool no_next
= false;
715 if (!is_gimple_call (stmt
))
721 if (gimple_call_internal_p (stmt
))
723 enum internal_fn ifn
= gimple_call_internal_fn (stmt
);
727 no_next
= ubsan_expand_null_ifn (&gsi
);
729 case IFN_UBSAN_BOUNDS
:
730 no_next
= ubsan_expand_bounds_ifn (&gsi
);
732 case IFN_UBSAN_OBJECT_SIZE
:
733 no_next
= ubsan_expand_objsize_ifn (&gsi
);
736 no_next
= ubsan_expand_vptr_ifn (&gsi
);
739 no_next
= asan_expand_check_ifn (&gsi
, use_calls
);
745 else if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
747 tree callee
= gimple_call_fndecl (stmt
);
748 switch (DECL_FUNCTION_CODE (callee
))
750 case BUILT_IN_UNREACHABLE
:
751 if (flag_sanitize
& SANITIZE_UNREACHABLE
752 && !lookup_attribute ("no_sanitize_undefined",
753 DECL_ATTRIBUTES (fun
->decl
)))
754 no_next
= ubsan_instrument_unreachable (&gsi
);
761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
763 fprintf (dump_file
, "Expanded\n ");
764 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
765 fprintf (dump_file
, "\n");
778 make_pass_sanopt (gcc::context
*ctxt
)
780 return new pass_sanopt (ctxt
);