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"
28 #include "fold-const.h"
31 #include "hard-reg-set.h"
33 #include "dominance.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
41 #include "gimple-iterator.h"
42 #include "tree-pass.h"
44 #include "gimple-pretty-print.h"
46 #include "langhooks.h"
49 #include "tree-ssa-operands.h"
50 #include "tree-hash-traits.h"
53 /* This is used to carry information about basic blocks. It is
54 attached to the AUX field of the standard CFG block. */
58 /* True if this BB might call (directly or indirectly) free/munmap
59 or similar operation. */
60 bool has_freeing_call_p
;
62 /* True if HAS_FREEING_CALL_P flag has been computed. */
63 bool has_freeing_call_computed_p
;
65 /* True if there is a block with HAS_FREEING_CALL_P flag set
66 on any path between an immediate dominator of BB, denoted
68 bool imm_dom_path_with_freeing_call_p
;
70 /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed. */
71 bool imm_dom_path_with_freeing_call_computed_p
;
73 /* Number of possibly freeing calls encountered in this bb
75 uint64_t freeing_call_events
;
77 /* True if BB is currently being visited during computation
78 of IMM_DOM_PATH_WITH_FREEING_CALL_P flag. */
81 /* True if this BB has been visited in the dominator walk. */
85 /* If T has a single definition of form T = T2, return T2. */
88 maybe_get_single_definition (tree t
)
90 if (TREE_CODE (t
) == SSA_NAME
)
92 gimple g
= SSA_NAME_DEF_STMT (t
);
93 if (gimple_assign_single_p (g
))
94 return gimple_assign_rhs1 (g
);
99 /* Tree triplet for vptr_check_map. */
100 struct sanopt_tree_triplet
105 /* Traits class for tree triplet hash maps below. */
107 struct sanopt_tree_triplet_hash
: typed_noop_remove
<sanopt_tree_triplet
>
109 typedef sanopt_tree_triplet value_type
;
110 typedef sanopt_tree_triplet compare_type
;
112 static inline hashval_t
113 hash (const sanopt_tree_triplet
&ref
)
115 inchash::hash
hstate (0);
116 inchash::add_expr (ref
.t1
, hstate
);
117 inchash::add_expr (ref
.t2
, hstate
);
118 inchash::add_expr (ref
.t3
, hstate
);
119 return hstate
.end ();
123 equal (const sanopt_tree_triplet
&ref1
, const sanopt_tree_triplet
&ref2
)
125 return operand_equal_p (ref1
.t1
, ref2
.t1
, 0)
126 && operand_equal_p (ref1
.t2
, ref2
.t2
, 0)
127 && operand_equal_p (ref1
.t3
, ref2
.t3
, 0);
131 mark_deleted (sanopt_tree_triplet
&ref
)
133 ref
.t1
= reinterpret_cast<tree
> (1);
137 mark_empty (sanopt_tree_triplet
&ref
)
143 is_deleted (const sanopt_tree_triplet
&ref
)
145 return ref
.t1
== (void *) 1;
149 is_empty (const sanopt_tree_triplet
&ref
)
151 return ref
.t1
== NULL
;
155 /* This is used to carry various hash maps and variables used
156 in sanopt_optimize_walker. */
160 /* This map maps a pointer (the first argument of UBSAN_NULL) to
161 a vector of UBSAN_NULL call statements that check this pointer. */
162 hash_map
<tree
, auto_vec
<gimple
> > null_check_map
;
164 /* This map maps a pointer (the second argument of ASAN_CHECK) to
165 a vector of ASAN_CHECK call statements that check the access. */
166 hash_map
<tree_operand_hash
, auto_vec
<gimple
> > asan_check_map
;
168 /* This map maps a tree triplet (the first, second and fourth argument
169 of UBSAN_VPTR) to a vector of UBSAN_VPTR call statements that check
170 that virtual table pointer. */
171 hash_map
<sanopt_tree_triplet_hash
, auto_vec
<gimple
> > vptr_check_map
;
173 /* Number of IFN_ASAN_CHECK statements. */
174 int asan_num_accesses
;
178 /* Return true if there might be any call to free/munmap operation
179 on any path in between DOM (which should be imm(BB)) and BB. */
182 imm_dom_path_with_freeing_call (basic_block bb
, basic_block dom
)
184 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
188 if (info
->imm_dom_path_with_freeing_call_computed_p
)
189 return info
->imm_dom_path_with_freeing_call_p
;
191 info
->being_visited_p
= true;
193 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
195 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
200 if ((pred_info
->imm_dom_path_with_freeing_call_computed_p
201 && pred_info
->imm_dom_path_with_freeing_call_p
)
202 || (pred_info
->has_freeing_call_computed_p
203 && pred_info
->has_freeing_call_p
))
205 info
->imm_dom_path_with_freeing_call_computed_p
= true;
206 info
->imm_dom_path_with_freeing_call_p
= true;
207 info
->being_visited_p
= false;
212 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
214 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
219 if (pred_info
->has_freeing_call_computed_p
)
222 gimple_stmt_iterator gsi
;
223 for (gsi
= gsi_start_bb (e
->src
); !gsi_end_p (gsi
); gsi_next (&gsi
))
225 gimple stmt
= gsi_stmt (gsi
);
227 if (is_gimple_call (stmt
) && !nonfreeing_call_p (stmt
))
229 pred_info
->has_freeing_call_p
= true;
234 pred_info
->has_freeing_call_computed_p
= true;
235 if (pred_info
->has_freeing_call_p
)
237 info
->imm_dom_path_with_freeing_call_computed_p
= true;
238 info
->imm_dom_path_with_freeing_call_p
= true;
239 info
->being_visited_p
= false;
244 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
250 for (src
= e
->src
; src
!= dom
; )
252 sanopt_info
*pred_info
= (sanopt_info
*) src
->aux
;
253 if (pred_info
->being_visited_p
)
255 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, src
);
256 if (imm_dom_path_with_freeing_call (src
, imm
))
258 info
->imm_dom_path_with_freeing_call_computed_p
= true;
259 info
->imm_dom_path_with_freeing_call_p
= true;
260 info
->being_visited_p
= false;
267 info
->imm_dom_path_with_freeing_call_computed_p
= true;
268 info
->imm_dom_path_with_freeing_call_p
= false;
269 info
->being_visited_p
= false;
273 /* Get the first dominating check from the list of stored checks.
274 Non-dominating checks are silently dropped. */
277 maybe_get_dominating_check (auto_vec
<gimple
> &v
)
279 for (; !v
.is_empty (); v
.pop ())
281 gimple g
= v
.last ();
282 sanopt_info
*si
= (sanopt_info
*) gimple_bb (g
)->aux
;
284 /* At this point we shouldn't have any statements
285 that aren't dominating the current BB. */
291 /* Optimize away redundant UBSAN_NULL calls. */
294 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
296 gcc_assert (gimple_call_num_args (stmt
) == 3);
297 tree ptr
= gimple_call_arg (stmt
, 0);
298 tree cur_align
= gimple_call_arg (stmt
, 2);
299 gcc_assert (TREE_CODE (cur_align
) == INTEGER_CST
);
302 auto_vec
<gimple
> &v
= ctx
->null_check_map
.get_or_insert (ptr
);
303 gimple g
= maybe_get_dominating_check (v
);
306 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
307 nothing to optimize yet. */
312 /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
313 can drop this one. But only if this check doesn't specify stricter
316 tree align
= gimple_call_arg (g
, 2);
317 int kind
= tree_to_shwi (gimple_call_arg (g
, 1));
318 /* If this is a NULL pointer check where we had segv anyway, we can
320 if (integer_zerop (align
)
321 && (kind
== UBSAN_LOAD_OF
322 || kind
== UBSAN_STORE_OF
323 || kind
== UBSAN_MEMBER_ACCESS
))
325 /* Otherwise remove the check in non-recovering mode, or if the
326 stmts have same location. */
327 else if (integer_zerop (align
))
328 remove
= (flag_sanitize_recover
& SANITIZE_NULL
) == 0
329 || flag_sanitize_undefined_trap_on_error
330 || gimple_location (g
) == gimple_location (stmt
);
331 else if (tree_int_cst_le (cur_align
, align
))
332 remove
= (flag_sanitize_recover
& SANITIZE_ALIGNMENT
) == 0
333 || flag_sanitize_undefined_trap_on_error
334 || gimple_location (g
) == gimple_location (stmt
);
336 if (!remove
&& gimple_bb (g
) == gimple_bb (stmt
)
337 && tree_int_cst_compare (cur_align
, align
) == 0)
345 /* Optimize away redundant UBSAN_VPTR calls. The second argument
346 is the value loaded from the virtual table, so rely on FRE to find out
347 when we can actually optimize. */
350 maybe_optimize_ubsan_vptr_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
352 gcc_assert (gimple_call_num_args (stmt
) == 5);
353 sanopt_tree_triplet triplet
;
354 triplet
.t1
= gimple_call_arg (stmt
, 0);
355 triplet
.t2
= gimple_call_arg (stmt
, 1);
356 triplet
.t3
= gimple_call_arg (stmt
, 3);
358 auto_vec
<gimple
> &v
= ctx
->vptr_check_map
.get_or_insert (triplet
);
359 gimple g
= maybe_get_dominating_check (v
);
362 /* For this PTR we don't have any UBSAN_VPTR stmts recorded, so there's
363 nothing to optimize yet. */
371 /* Returns TRUE if ASan check of length LEN in block BB can be removed
372 if preceded by checks in V. */
375 can_remove_asan_check (auto_vec
<gimple
> &v
, tree len
, basic_block bb
)
379 gimple to_pop
= NULL
;
381 basic_block last_bb
= bb
;
382 bool cleanup
= false;
384 FOR_EACH_VEC_ELT_REVERSE (v
, i
, g
)
386 basic_block gbb
= gimple_bb (g
);
387 sanopt_info
*si
= (sanopt_info
*) gbb
->aux
;
388 if (gimple_uid (g
) < si
->freeing_call_events
)
390 /* If there is a potentially freeing call after g in gbb, we should
391 remove it from the vector, can't use in optimization. */
396 tree glen
= gimple_call_arg (g
, 2);
397 gcc_assert (TREE_CODE (glen
) == INTEGER_CST
);
399 /* If we've checked only smaller length than we want to check now,
400 we can't remove the current stmt. If g is in the same basic block,
401 we want to remove it though, as the current stmt is better. */
402 if (tree_int_cst_lt (glen
, len
))
412 while (last_bb
!= gbb
)
414 /* Paths from last_bb to bb have been checked before.
415 gbb is necessarily a dominator of last_bb, but not necessarily
416 immediate dominator. */
417 if (((sanopt_info
*) last_bb
->aux
)->freeing_call_events
)
420 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, last_bb
);
422 if (imm_dom_path_with_freeing_call (last_bb
, imm
))
434 unsigned int j
= 0, l
= v
.length ();
435 for (i
= 0; i
< l
; i
++)
437 && (gimple_uid (v
[i
])
439 gimple_bb (v
[i
])->aux
)->freeing_call_events
))
451 /* Optimize away redundant ASAN_CHECK calls. */
454 maybe_optimize_asan_check_ifn (struct sanopt_ctx
*ctx
, gimple stmt
)
456 gcc_assert (gimple_call_num_args (stmt
) == 4);
457 tree ptr
= gimple_call_arg (stmt
, 1);
458 tree len
= gimple_call_arg (stmt
, 2);
459 basic_block bb
= gimple_bb (stmt
);
460 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
462 if (TREE_CODE (len
) != INTEGER_CST
)
464 if (integer_zerop (len
))
467 gimple_set_uid (stmt
, info
->freeing_call_events
);
469 auto_vec
<gimple
> *ptr_checks
= &ctx
->asan_check_map
.get_or_insert (ptr
);
471 tree base_addr
= maybe_get_single_definition (ptr
);
472 auto_vec
<gimple
> *base_checks
= NULL
;
475 base_checks
= &ctx
->asan_check_map
.get_or_insert (base_addr
);
476 /* Original pointer might have been invalidated. */
477 ptr_checks
= ctx
->asan_check_map
.get (ptr
);
480 gimple g
= maybe_get_dominating_check (*ptr_checks
);
484 /* Try with base address as well. */
485 g2
= maybe_get_dominating_check (*base_checks
);
487 if (g
== NULL
&& g2
== NULL
)
489 /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
490 nothing to optimize yet. */
491 ptr_checks
->safe_push (stmt
);
493 base_checks
->safe_push (stmt
);
500 remove
= can_remove_asan_check (*ptr_checks
, len
, bb
);
502 if (!remove
&& base_checks
)
503 /* Try with base address as well. */
504 remove
= can_remove_asan_check (*base_checks
, len
, bb
);
508 ptr_checks
->safe_push (stmt
);
510 base_checks
->safe_push (stmt
);
516 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
518 We walk blocks in the CFG via a depth first search of the dominator
519 tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
520 in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
521 blocks. When leaving a block, we mark the block as visited; then
522 when checking the statements in the vector, we ignore statements that
523 are coming from already visited blocks, because these cannot dominate
524 anything anymore. CTX is a sanopt context. */
527 sanopt_optimize_walker (basic_block bb
, struct sanopt_ctx
*ctx
)
530 gimple_stmt_iterator gsi
;
531 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
532 bool asan_check_optimize
= (flag_sanitize
& SANITIZE_ADDRESS
) != 0;
534 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
536 gimple stmt
= gsi_stmt (gsi
);
539 if (!is_gimple_call (stmt
))
541 /* Handle asm volatile or asm with "memory" clobber
542 the same as potentionally freeing call. */
543 gasm
*asm_stmt
= dyn_cast
<gasm
*> (stmt
);
545 && asan_check_optimize
546 && (gimple_asm_clobbers_memory_p (asm_stmt
)
547 || gimple_asm_volatile_p (asm_stmt
)))
548 info
->freeing_call_events
++;
553 if (asan_check_optimize
&& !nonfreeing_call_p (stmt
))
554 info
->freeing_call_events
++;
556 if (gimple_call_internal_p (stmt
))
557 switch (gimple_call_internal_fn (stmt
))
560 remove
= maybe_optimize_ubsan_null_ifn (ctx
, stmt
);
563 remove
= maybe_optimize_ubsan_vptr_ifn (ctx
, stmt
);
566 if (asan_check_optimize
)
567 remove
= maybe_optimize_asan_check_ifn (ctx
, stmt
);
569 ctx
->asan_num_accesses
++;
577 /* Drop this check. */
578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
580 fprintf (dump_file
, "Optimizing out\n ");
581 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
582 fprintf (dump_file
, "\n");
584 unlink_stmt_vdef (stmt
);
585 gsi_remove (&gsi
, true);
591 if (asan_check_optimize
)
593 info
->has_freeing_call_p
= info
->freeing_call_events
!= 0;
594 info
->has_freeing_call_computed_p
= true;
597 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
599 son
= next_dom_son (CDI_DOMINATORS
, son
))
600 sanopt_optimize_walker (son
, ctx
);
602 /* We're leaving this BB, so mark it to that effect. */
603 info
->visited_p
= true;
606 /* Try to remove redundant sanitizer checks in function FUN. */
609 sanopt_optimize (function
*fun
)
611 struct sanopt_ctx ctx
;
612 ctx
.asan_num_accesses
= 0;
614 /* Set up block info for each basic block. */
615 alloc_aux_for_blocks (sizeof (sanopt_info
));
617 /* We're going to do a dominator walk, so ensure that we have
618 dominance information. */
619 calculate_dominance_info (CDI_DOMINATORS
);
621 /* Recursively walk the dominator tree optimizing away
623 sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun
), &ctx
);
625 free_aux_for_blocks ();
627 return ctx
.asan_num_accesses
;
630 /* Perform optimization of sanitize functions. */
634 const pass_data pass_data_sanopt
=
636 GIMPLE_PASS
, /* type */
638 OPTGROUP_NONE
, /* optinfo_flags */
640 ( PROP_ssa
| PROP_cfg
| PROP_gimple_leh
), /* properties_required */
641 0, /* properties_provided */
642 0, /* properties_destroyed */
643 0, /* todo_flags_start */
644 TODO_update_ssa
, /* todo_flags_finish */
647 class pass_sanopt
: public gimple_opt_pass
650 pass_sanopt (gcc::context
*ctxt
)
651 : gimple_opt_pass (pass_data_sanopt
, ctxt
)
654 /* opt_pass methods: */
655 virtual bool gate (function
*) { return flag_sanitize
; }
656 virtual unsigned int execute (function
*);
658 }; // class pass_sanopt
661 pass_sanopt::execute (function
*fun
)
664 int asan_num_accesses
= 0;
666 /* Try to remove redundant checks. */
669 & (SANITIZE_NULL
| SANITIZE_ALIGNMENT
670 | SANITIZE_ADDRESS
| SANITIZE_VPTR
)))
671 asan_num_accesses
= sanopt_optimize (fun
);
672 else if (flag_sanitize
& SANITIZE_ADDRESS
)
674 gimple_stmt_iterator gsi
;
675 FOR_EACH_BB_FN (bb
, fun
)
676 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
678 gimple stmt
= gsi_stmt (gsi
);
679 if (is_gimple_call (stmt
) && gimple_call_internal_p (stmt
)
680 && gimple_call_internal_fn (stmt
) == IFN_ASAN_CHECK
)
685 bool use_calls
= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
< INT_MAX
686 && asan_num_accesses
>= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD
;
688 FOR_EACH_BB_FN (bb
, fun
)
690 gimple_stmt_iterator gsi
;
691 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
693 gimple stmt
= gsi_stmt (gsi
);
694 bool no_next
= false;
696 if (!is_gimple_call (stmt
))
702 if (gimple_call_internal_p (stmt
))
704 enum internal_fn ifn
= gimple_call_internal_fn (stmt
);
708 no_next
= ubsan_expand_null_ifn (&gsi
);
710 case IFN_UBSAN_BOUNDS
:
711 no_next
= ubsan_expand_bounds_ifn (&gsi
);
713 case IFN_UBSAN_OBJECT_SIZE
:
714 no_next
= ubsan_expand_objsize_ifn (&gsi
);
717 no_next
= ubsan_expand_vptr_ifn (&gsi
);
720 no_next
= asan_expand_check_ifn (&gsi
, use_calls
);
726 else if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
728 tree callee
= gimple_call_fndecl (stmt
);
729 switch (DECL_FUNCTION_CODE (callee
))
731 case BUILT_IN_UNREACHABLE
:
732 if (flag_sanitize
& SANITIZE_UNREACHABLE
733 && !lookup_attribute ("no_sanitize_undefined",
734 DECL_ATTRIBUTES (fun
->decl
)))
735 no_next
= ubsan_instrument_unreachable (&gsi
);
742 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
744 fprintf (dump_file
, "Expanded\n ");
745 print_gimple_stmt (dump_file
, stmt
, 0, dump_flags
);
746 fprintf (dump_file
, "\n");
759 make_pass_sanopt (gcc::context
*ctxt
)
761 return new pass_sanopt (ctxt
);