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
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"
25 #include "hash-table.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"
42 #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 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. */
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. */
138 imm_dom_path_with_freeing_call (basic_block bb
, basic_block dom
)
140 sanopt_info
*info
= (sanopt_info
*) bb
->aux
;
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
;
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;
168 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
170 sanopt_info
*pred_info
= (sanopt_info
*) e
->src
->aux
;
175 if (pred_info
->has_freeing_call_computed_p
)
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;
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;
200 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
206 for (src
= e
->src
; src
!= dom
; )
208 sanopt_info
*pred_info
= (sanopt_info
*) src
->aux
;
209 if (pred_info
->being_visited_p
)
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;
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;
229 /* Get the first dominating check from the list of stored checks.
230 Non-dominating checks are silently dropped. */
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
;
240 /* At this point we shouldn't have any statements
241 that aren't dominating the current BB. */
247 /* Optimize away redundant UBSAN_NULL calls. */
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
);
258 auto_vec
<gimple
> &v
= ctx
->null_check_map
.get_or_insert (ptr
);
259 gimple g
= maybe_get_dominating_check (v
);
262 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
263 nothing to optimize yet. */
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
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
276 if (integer_zerop (align
)
277 && (kind
== UBSAN_LOAD_OF
278 || kind
== UBSAN_STORE_OF
279 || kind
== UBSAN_MEMBER_ACCESS
))
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)
301 /* Returns TRUE if ASan check of length LEN in block BB can be removed
302 if preceded by checks in V. */
305 can_remove_asan_check (auto_vec
<gimple
> &v
, tree len
, basic_block bb
)
309 gimple to_pop
= NULL
;
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. */
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
))
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
)
350 basic_block imm
= get_immediate_dominator (CDI_DOMINATORS
, last_bb
);
352 if (imm_dom_path_with_freeing_call (last_bb
, imm
))
364 unsigned int j
= 0, l
= v
.length ();
365 for (i
= 0; i
< l
; i
++)
367 && (gimple_uid (v
[i
])
369 gimple_bb (v
[i
])->aux
)->freeing_call_events
))
381 /* Optimize away redundant ASAN_CHECK calls. */
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
)
394 if (integer_zerop (len
))
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
;
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
);
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
);
423 base_checks
->safe_push (stmt
);
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
);
438 ptr_checks
->safe_push (stmt
);
440 base_checks
->safe_push (stmt
);
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. */
457 sanopt_optimize_walker (basic_block bb
, struct sanopt_ctx
*ctx
)
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
);
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
);
475 && asan_check_optimize
476 && (gimple_asm_clobbers_memory_p (asm_stmt
)
477 || gimple_asm_volatile_p (asm_stmt
)))
478 info
->freeing_call_events
++;
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
))
490 remove
= maybe_optimize_ubsan_null_ifn (ctx
, stmt
);
493 if (asan_check_optimize
)
494 remove
= maybe_optimize_asan_check_ifn (ctx
, stmt
);
496 ctx
->asan_num_accesses
++;
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);
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
);
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. */
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
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. */
561 const pass_data pass_data_sanopt
=
563 GIMPLE_PASS
, /* type */
565 OPTGROUP_NONE
, /* optinfo_flags */
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
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
588 pass_sanopt::execute (function
*fun
)
591 int asan_num_accesses
= 0;
593 /* Try to remove redundant checks. */
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
)
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
))
628 if (gimple_call_internal_p (stmt
))
630 enum internal_fn ifn
= gimple_call_internal_fn (stmt
);
634 no_next
= ubsan_expand_null_ifn (&gsi
);
636 case IFN_UBSAN_BOUNDS
:
637 no_next
= ubsan_expand_bounds_ifn (&gsi
);
639 case IFN_UBSAN_OBJECT_SIZE
:
640 no_next
= ubsan_expand_objsize_ifn (&gsi
);
643 no_next
= asan_expand_check_ifn (&gsi
, use_calls
);
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
);
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");
682 make_pass_sanopt (gcc::context
*ctxt
)
684 return new pass_sanopt (ctxt
);