1/* Optimize and expand sanitizer functions.
2 Copyright (C) 2014-2017 Free Software Foundation, Inc.
3 Contributed by Marek Polacek <polacek@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "backend.h"
25#include "tree.h"
26#include "gimple.h"
27#include "ssa.h"
28#include "tree-pass.h"
29#include "tree-ssa-operands.h"
30#include "gimple-pretty-print.h"
31#include "fold-const.h"
32#include "gimple-iterator.h"
33#include "stringpool.h"
34#include "attribs.h"
35#include "asan.h"
36#include "ubsan.h"
37#include "params.h"
38#include "tree-hash-traits.h"
39#include "gimple-ssa.h"
40#include "tree-phinodes.h"
41#include "ssa-iterators.h"
42#include "gimplify.h"
43#include "gimple-iterator.h"
44#include "gimple-walk.h"
45#include "cfghooks.h"
46#include "tree-dfa.h"
47#include "tree-ssa.h"
48#include "varasm.h"
49
50/* This is used to carry information about basic blocks. It is
51 attached to the AUX field of the standard CFG block. */
52
53struct sanopt_info
54{
55 /* True if this BB might call (directly or indirectly) free/munmap
56 or similar operation. */
57 bool has_freeing_call_p;
58
59 /* True if HAS_FREEING_CALL_P flag has been computed. */
60 bool has_freeing_call_computed_p;
61
62 /* True if there is a block with HAS_FREEING_CALL_P flag set
63 on any path between an immediate dominator of BB, denoted
64 imm(BB), and BB. */
65 bool imm_dom_path_with_freeing_call_p;
66
67 /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed. */
68 bool imm_dom_path_with_freeing_call_computed_p;
69
70 /* Number of possibly freeing calls encountered in this bb
71 (so far). */
72 uint64_t freeing_call_events;
73
74 /* True if BB is currently being visited during computation
75 of IMM_DOM_PATH_WITH_FREEING_CALL_P flag. */
76 bool being_visited_p;
77
78 /* True if this BB has been visited in the dominator walk. */
79 bool visited_p;
80};
81
82/* If T has a single definition of form T = T2, return T2. */
83
84static tree
85maybe_get_single_definition (tree t)
86{
87 if (TREE_CODE (t) == SSA_NAME)
88 {
89 gimple *g = SSA_NAME_DEF_STMT (t);
90 if (gimple_assign_single_p (g))
91 return gimple_assign_rhs1 (g);
92 }
93 return NULL_TREE;
94}
95
96/* Tree triplet for vptr_check_map. */
97struct sanopt_tree_triplet
98{
99 tree t1, t2, t3;
100};
101
102/* Traits class for tree triplet hash maps below. */
103
104struct sanopt_tree_triplet_hash : typed_noop_remove <sanopt_tree_triplet>
105{
106 typedef sanopt_tree_triplet value_type;
107 typedef sanopt_tree_triplet compare_type;
108
109 static hashval_t
110 hash (const sanopt_tree_triplet &ref)
111 {
112 inchash::hash hstate (0);
113 inchash::add_expr (ref.t1, hstate);
114 inchash::add_expr (ref.t2, hstate);
115 inchash::add_expr (ref.t3, hstate);
116 return hstate.end ();
117 }
118
119 static bool
120 equal (const sanopt_tree_triplet &ref1, const sanopt_tree_triplet &ref2)
121 {
122 return operand_equal_p (ref1.t1, ref2.t1, 0)
123 && operand_equal_p (ref1.t2, ref2.t2, 0)
124 && operand_equal_p (ref1.t3, ref2.t3, 0);
125 }
126
127 static void
128 mark_deleted (sanopt_tree_triplet &ref)
129 {
130 ref.t1 = reinterpret_cast<tree> (1);
131 }
132
133 static void
134 mark_empty (sanopt_tree_triplet &ref)
135 {
136 ref.t1 = NULL;
137 }
138
139 static bool
140 is_deleted (const sanopt_tree_triplet &ref)
141 {
142 return ref.t1 == reinterpret_cast<tree> (1);
143 }
144
145 static bool
146 is_empty (const sanopt_tree_triplet &ref)
147 {
148 return ref.t1 == NULL;
149 }
150};
151
152/* Tree couple for ptr_check_map. */
153struct sanopt_tree_couple
154{
155 tree ptr;
156 bool pos_p;
157};
158
159/* Traits class for tree triplet hash maps below. */
160
161struct sanopt_tree_couple_hash : typed_noop_remove <sanopt_tree_couple>
162{
163 typedef sanopt_tree_couple value_type;
164 typedef sanopt_tree_couple compare_type;
165
166 static hashval_t
167 hash (const sanopt_tree_couple &ref)
168 {
169 inchash::hash hstate (0);
170 inchash::add_expr (ref.ptr, hstate);
171 hstate.add_int (ref.pos_p);
172 return hstate.end ();
173 }
174
175 static bool
176 equal (const sanopt_tree_couple &ref1, const sanopt_tree_couple &ref2)
177 {
178 return operand_equal_p (ref1.ptr, ref2.ptr, 0)
179 && ref1.pos_p == ref2.pos_p;
180 }
181
182 static void
183 mark_deleted (sanopt_tree_couple &ref)
184 {
185 ref.ptr = reinterpret_cast<tree> (1);
186 }
187
188 static void
189 mark_empty (sanopt_tree_couple &ref)
190 {
191 ref.ptr = NULL;
192 }
193
194 static bool
195 is_deleted (const sanopt_tree_couple &ref)
196 {
197 return ref.ptr == reinterpret_cast<tree> (1);
198 }
199
200 static bool
201 is_empty (const sanopt_tree_couple &ref)
202 {
203 return ref.ptr == NULL;
204 }
205};
206
207/* This is used to carry various hash maps and variables used
208 in sanopt_optimize_walker. */
209
210struct sanopt_ctx
211{
212 /* This map maps a pointer (the first argument of UBSAN_NULL) to
213 a vector of UBSAN_NULL call statements that check this pointer. */
214 hash_map<tree, auto_vec<gimple *> > null_check_map;
215
216 /* This map maps a pointer (the second argument of ASAN_CHECK) to
217 a vector of ASAN_CHECK call statements that check the access. */
218 hash_map<tree_operand_hash, auto_vec<gimple *> > asan_check_map;
219
220 /* This map maps a tree triplet (the first, second and fourth argument
221 of UBSAN_VPTR) to a vector of UBSAN_VPTR call statements that check
222 that virtual table pointer. */
223 hash_map<sanopt_tree_triplet_hash, auto_vec<gimple *> > vptr_check_map;
224
225 /* This map maps a couple (tree and boolean) to a vector of UBSAN_PTR
226 call statements that check that pointer overflow. */
227 hash_map<sanopt_tree_couple_hash, auto_vec<gimple *> > ptr_check_map;
228
229 /* Number of IFN_ASAN_CHECK statements. */
230 int asan_num_accesses;
231
232 /* True when the current functions constains an ASAN_MARK. */
233 bool contains_asan_mark;
234};
235
236/* Return true if there might be any call to free/munmap operation
237 on any path in between DOM (which should be imm(BB)) and BB. */
238
239static bool
240imm_dom_path_with_freeing_call (basic_block bb, basic_block dom)
241{
242 sanopt_info *info = (sanopt_info *) bb->aux;
243 edge e;
244 edge_iterator ei;
245
246 if (info->imm_dom_path_with_freeing_call_computed_p)
247 return info->imm_dom_path_with_freeing_call_p;
248
249 info->being_visited_p = true;
250
251 FOR_EACH_EDGE (e, ei, bb->preds)
252 {
253 sanopt_info *pred_info = (sanopt_info *) e->src->aux;
254
255 if (e->src == dom)
256 continue;
257
258 if ((pred_info->imm_dom_path_with_freeing_call_computed_p
259 && pred_info->imm_dom_path_with_freeing_call_p)
260 || (pred_info->has_freeing_call_computed_p
261 && pred_info->has_freeing_call_p))
262 {
263 info->imm_dom_path_with_freeing_call_computed_p = true;
264 info->imm_dom_path_with_freeing_call_p = true;
265 info->being_visited_p = false;
266 return true;
267 }
268 }
269
270 FOR_EACH_EDGE (e, ei, bb->preds)
271 {
272 sanopt_info *pred_info = (sanopt_info *) e->src->aux;
273
274 if (e->src == dom)
275 continue;
276
277 if (pred_info->has_freeing_call_computed_p)
278 continue;
279
280 gimple_stmt_iterator gsi;
281 for (gsi = gsi_start_bb (e->src); !gsi_end_p (gsi); gsi_next (&gsi))
282 {
283 gimple *stmt = gsi_stmt (gsi);
284 gasm *asm_stmt;
285
286 if ((is_gimple_call (stmt) && !nonfreeing_call_p (stmt))
287 || ((asm_stmt = dyn_cast <gasm *> (stmt))
288 && (gimple_asm_clobbers_memory_p (asm_stmt)
289 || gimple_asm_volatile_p (asm_stmt))))
290 {
291 pred_info->has_freeing_call_p = true;
292 break;
293 }
294 }
295
296 pred_info->has_freeing_call_computed_p = true;
297 if (pred_info->has_freeing_call_p)
298 {
299 info->imm_dom_path_with_freeing_call_computed_p = true;
300 info->imm_dom_path_with_freeing_call_p = true;
301 info->being_visited_p = false;
302 return true;
303 }
304 }
305
306 FOR_EACH_EDGE (e, ei, bb->preds)
307 {
308 if (e->src == dom)
309 continue;
310
311 basic_block src;
312 for (src = e->src; src != dom; )
313 {
314 sanopt_info *pred_info = (sanopt_info *) src->aux;
315 if (pred_info->being_visited_p)
316 break;
317 basic_block imm = get_immediate_dominator (CDI_DOMINATORS, src);
318 if (imm_dom_path_with_freeing_call (src, imm))
319 {
320 info->imm_dom_path_with_freeing_call_computed_p = true;
321 info->imm_dom_path_with_freeing_call_p = true;
322 info->being_visited_p = false;
323 return true;
324 }
325 src = imm;
326 }
327 }
328
329 info->imm_dom_path_with_freeing_call_computed_p = true;
330 info->imm_dom_path_with_freeing_call_p = false;
331 info->being_visited_p = false;
332 return false;
333}
334
335/* Get the first dominating check from the list of stored checks.
336 Non-dominating checks are silently dropped. */
337
338static gimple *
339maybe_get_dominating_check (auto_vec<gimple *> &v)
340{
341 for (; !v.is_empty (); v.pop ())
342 {
343 gimple *g = v.last ();
344 sanopt_info *si = (sanopt_info *) gimple_bb (g)->aux;
345 if (!si->visited_p)
346 /* At this point we shouldn't have any statements
347 that aren't dominating the current BB. */
348 return g;
349 }
350 return NULL;
351}
352
353/* Optimize away redundant UBSAN_NULL calls. */
354
355static bool
356maybe_optimize_ubsan_null_ifn (struct sanopt_ctx *ctx, gimple *stmt)
357{
358 gcc_assert (gimple_call_num_args (stmt) == 3);
359 tree ptr = gimple_call_arg (stmt, 0);
360 tree cur_align = gimple_call_arg (stmt, 2);
361 gcc_assert (TREE_CODE (cur_align) == INTEGER_CST);
362 bool remove = false;
363
364 auto_vec<gimple *> &v = ctx->null_check_map.get_or_insert (ptr);
365 gimple *g = maybe_get_dominating_check (v);
366 if (!g)
367 {
368 /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
369 nothing to optimize yet. */
370 v.safe_push (stmt);
371 return false;
372 }
373
374 /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
375 can drop this one. But only if this check doesn't specify stricter
376 alignment. */
377
378 tree align = gimple_call_arg (g, 2);
379 int kind = tree_to_shwi (gimple_call_arg (g, 1));
380 /* If this is a NULL pointer check where we had segv anyway, we can
381 remove it. */
382 if (integer_zerop (align)
383 && (kind == UBSAN_LOAD_OF
384 || kind == UBSAN_STORE_OF
385 || kind == UBSAN_MEMBER_ACCESS))
386 remove = true;
387 /* Otherwise remove the check in non-recovering mode, or if the
388 stmts have same location. */
389 else if (integer_zerop (align))
390 remove = (flag_sanitize_recover & SANITIZE_NULL) == 0
391 || flag_sanitize_undefined_trap_on_error
392 || gimple_location (g) == gimple_location (stmt);
393 else if (tree_int_cst_le (cur_align, align))
394 remove = (flag_sanitize_recover & SANITIZE_ALIGNMENT) == 0
395 || flag_sanitize_undefined_trap_on_error
396 || gimple_location (g) == gimple_location (stmt);
397
398 if (!remove && gimple_bb (g) == gimple_bb (stmt)
399 && tree_int_cst_compare (cur_align, align) == 0)
400 v.pop ();
401
402 if (!remove)
403 v.safe_push (stmt);
404 return remove;
405}
406
407/* Return true when pointer PTR for a given CUR_OFFSET is already sanitized
408 in a given sanitization context CTX. */
409
410static bool
411has_dominating_ubsan_ptr_check (sanopt_ctx *ctx, tree ptr,
412 offset_int &cur_offset)
413{
414 bool pos_p = !wi::neg_p (cur_offset);
415 sanopt_tree_couple couple;
416 couple.ptr = ptr;
417 couple.pos_p = pos_p;
418
419 auto_vec<gimple *> &v = ctx->ptr_check_map.get_or_insert (couple);
420 gimple *g = maybe_get_dominating_check (v);
421 if (!g)
422 return false;
423
424 /* We already have recorded a UBSAN_PTR check for this pointer. Perhaps we
425 can drop this one. But only if this check doesn't specify larger offset.
426 */
427 tree offset = gimple_call_arg (g, 1);
428 gcc_assert (TREE_CODE (offset) == INTEGER_CST);
429 offset_int ooffset = wi::sext (wi::to_offset (offset), POINTER_SIZE);
430
431 if (pos_p)
432 {
433 if (wi::les_p (cur_offset, ooffset))
434 return true;
435 }
436 else if (!pos_p && wi::les_p (ooffset, cur_offset))
437 return true;
438
439 return false;
440}
441
442/* Record UBSAN_PTR check of given context CTX. Register pointer PTR on
443 a given OFFSET that it's handled by GIMPLE STMT. */
444
445static void
446record_ubsan_ptr_check_stmt (sanopt_ctx *ctx, gimple *stmt, tree ptr,
447 const offset_int &offset)
448{
449 sanopt_tree_couple couple;
450 couple.ptr = ptr;
451 couple.pos_p = !wi::neg_p (offset);
452
453 auto_vec<gimple *> &v = ctx->ptr_check_map.get_or_insert (couple);
454 v.safe_push (stmt);
455}
456
457/* Optimize away redundant UBSAN_PTR calls. */
458
459static bool
460maybe_optimize_ubsan_ptr_ifn (sanopt_ctx *ctx, gimple *stmt)
461{
462 HOST_WIDE_INT bitsize, bitpos;
463 machine_mode mode;
464 int volatilep = 0, reversep, unsignedp = 0;
465 tree offset;
466
467 gcc_assert (gimple_call_num_args (stmt) == 2);
468 tree ptr = gimple_call_arg (stmt, 0);
469 tree off = gimple_call_arg (stmt, 1);
470
471 if (TREE_CODE (off) != INTEGER_CST)
472 return false;
473
474 if (integer_zerop (off))
475 return true;
476
477 offset_int cur_offset = wi::sext (wi::to_offset (off), POINTER_SIZE);
478 if (has_dominating_ubsan_ptr_check (ctx, ptr, cur_offset))
479 return true;
480
481 tree base = ptr;
482 if (TREE_CODE (base) == ADDR_EXPR)
483 {
484 base = TREE_OPERAND (base, 0);
485
486 base = get_inner_reference (base, &bitsize, &bitpos, &offset, &mode,
487 &unsignedp, &reversep, &volatilep);
488 if (offset == NULL_TREE && DECL_P (base))
489 {
490 gcc_assert (!DECL_REGISTER (base));
491 offset_int expr_offset = bitpos / BITS_PER_UNIT;
492 offset_int total_offset = expr_offset + cur_offset;
493 if (total_offset != wi::sext (total_offset, POINTER_SIZE))
494 {
495 record_ubsan_ptr_check_stmt (ctx, stmt, ptr, cur_offset);
496 return false;
497 }
498
499 /* If BASE is a fixed size automatic variable or
500 global variable defined in the current TU, we don't have
501 to instrument anything if offset is within address
502 of the variable. */
503 if ((VAR_P (base)
504 || TREE_CODE (base) == PARM_DECL
505 || TREE_CODE (base) == RESULT_DECL)
506 && DECL_SIZE_UNIT (base)
507 && TREE_CODE (DECL_SIZE_UNIT (base)) == INTEGER_CST
508 && (!is_global_var (base) || decl_binds_to_current_def_p (base)))
509 {
510 offset_int base_size = wi::to_offset (DECL_SIZE_UNIT (base));
511 if (bitpos >= 0
512 && wi::les_p (total_offset, base_size))
513 {
514 if (!wi::neg_p (total_offset)
515 && wi::les_p (total_offset, base_size))
516 return true;
517 }
518 }
519
520 /* Following expression: UBSAN_PTR (&MEM_REF[ptr + x], y) can be
521 handled as follows:
522
523 1) sign (x) == sign (y), then check for dominating check of (x + y)
524 2) sign (x) != sign (y), then first check if we have a dominating
525 check for ptr + x. If so, then we have 2 situations:
526 a) sign (x) == sign (x + y), here we are done, example:
527 UBSAN_PTR (&MEM_REF[ptr + 100], -50)
528 b) check for dominating check of ptr + x + y.
529 */
530
531 bool sign_cur_offset = !wi::neg_p (cur_offset);
532 bool sign_expr_offset = bitpos >= 0;
533
534 tree base_addr
535 = build1 (ADDR_EXPR, build_pointer_type (TREE_TYPE (base)), base);
536
537 bool add = false;
538 if (sign_cur_offset == sign_expr_offset)
539 {
540 if (has_dominating_ubsan_ptr_check (ctx, base_addr, total_offset))
541 return true;
542 else
543 add = true;
544 }
545 else
546 {
547 if (!has_dominating_ubsan_ptr_check (ctx, base_addr, expr_offset))
548 ; /* Don't record base_addr + expr_offset, it's not a guarding
549 check. */
550 else
551 {
552 bool sign_total_offset = !wi::neg_p (total_offset);
553 if (sign_expr_offset == sign_total_offset)
554 return true;
555 else
556 {
557 if (has_dominating_ubsan_ptr_check (ctx, base_addr,
558 total_offset))
559 return true;
560 else
561 add = true;
562 }
563 }
564 }
565
566 /* Record a new dominating check for base_addr + total_offset. */
567 if (add && !operand_equal_p (base, base_addr, 0))
568 record_ubsan_ptr_check_stmt (ctx, stmt, base_addr,
569 total_offset);
570 }
571 }
572
573 /* For this PTR we don't have any UBSAN_PTR stmts recorded, so there's
574 nothing to optimize yet. */
575 record_ubsan_ptr_check_stmt (ctx, stmt, ptr, cur_offset);
576
577 return false;
578}
579
580/* Optimize away redundant UBSAN_VPTR calls. The second argument
581 is the value loaded from the virtual table, so rely on FRE to find out
582 when we can actually optimize. */
583
584static bool
585maybe_optimize_ubsan_vptr_ifn (struct sanopt_ctx *ctx, gimple *stmt)
586{
587 gcc_assert (gimple_call_num_args (stmt) == 5);
588 sanopt_tree_triplet triplet;
589 triplet.t1 = gimple_call_arg (stmt, 0);
590 triplet.t2 = gimple_call_arg (stmt, 1);
591 triplet.t3 = gimple_call_arg (stmt, 3);
592
593 auto_vec<gimple *> &v = ctx->vptr_check_map.get_or_insert (triplet);
594 gimple *g = maybe_get_dominating_check (v);
595 if (!g)
596 {
597 /* For this PTR we don't have any UBSAN_VPTR stmts recorded, so there's
598 nothing to optimize yet. */
599 v.safe_push (stmt);
600 return false;
601 }
602
603 return true;
604}
605
606/* Returns TRUE if ASan check of length LEN in block BB can be removed
607 if preceded by checks in V. */
608
609static bool
610can_remove_asan_check (auto_vec<gimple *> &v, tree len, basic_block bb)
611{
612 unsigned int i;
613 gimple *g;
614 gimple *to_pop = NULL;
615 bool remove = false;
616 basic_block last_bb = bb;
617 bool cleanup = false;
618
619 FOR_EACH_VEC_ELT_REVERSE (v, i, g)
620 {
621 basic_block gbb = gimple_bb (g);
622 sanopt_info *si = (sanopt_info *) gbb->aux;
623 if (gimple_uid (g) < si->freeing_call_events)
624 {
625 /* If there is a potentially freeing call after g in gbb, we should
626 remove it from the vector, can't use in optimization. */
627 cleanup = true;
628 continue;
629 }
630
631 tree glen = gimple_call_arg (g, 2);
632 gcc_assert (TREE_CODE (glen) == INTEGER_CST);
633
634 /* If we've checked only smaller length than we want to check now,
635 we can't remove the current stmt. If g is in the same basic block,
636 we want to remove it though, as the current stmt is better. */
637 if (tree_int_cst_lt (glen, len))
638 {
639 if (gbb == bb)
640 {
641 to_pop = g;
642 cleanup = true;
643 }
644 continue;
645 }
646
647 while (last_bb != gbb)
648 {
649 /* Paths from last_bb to bb have been checked before.
650 gbb is necessarily a dominator of last_bb, but not necessarily
651 immediate dominator. */
652 if (((sanopt_info *) last_bb->aux)->freeing_call_events)
653 break;
654
655 basic_block imm = get_immediate_dominator (CDI_DOMINATORS, last_bb);
656 gcc_assert (imm);
657 if (imm_dom_path_with_freeing_call (last_bb, imm))
658 break;
659
660 last_bb = imm;
661 }
662 if (last_bb == gbb)
663 remove = true;
664 break;
665 }
666
667 if (cleanup)
668 {
669 unsigned int j = 0, l = v.length ();
670 for (i = 0; i < l; i++)
671 if (v[i] != to_pop
672 && (gimple_uid (v[i])
673 == ((sanopt_info *)
674 gimple_bb (v[i])->aux)->freeing_call_events))
675 {
676 if (i != j)
677 v[j] = v[i];
678 j++;
679 }
680 v.truncate (j);
681 }
682
683 return remove;
684}
685
686/* Optimize away redundant ASAN_CHECK calls. */
687
688static bool
689maybe_optimize_asan_check_ifn (struct sanopt_ctx *ctx, gimple *stmt)
690{
691 gcc_assert (gimple_call_num_args (stmt) == 4);
692 tree ptr = gimple_call_arg (stmt, 1);
693 tree len = gimple_call_arg (stmt, 2);
694 basic_block bb = gimple_bb (stmt);
695 sanopt_info *info = (sanopt_info *) bb->aux;
696
697 if (TREE_CODE (len) != INTEGER_CST)
698 return false;
699 if (integer_zerop (len))
700 return false;
701
702 gimple_set_uid (stmt, info->freeing_call_events);
703
704 auto_vec<gimple *> *ptr_checks = &ctx->asan_check_map.get_or_insert (ptr);
705
706 tree base_addr = maybe_get_single_definition (ptr);
707 auto_vec<gimple *> *base_checks = NULL;
708 if (base_addr)
709 {
710 base_checks = &ctx->asan_check_map.get_or_insert (base_addr);
711 /* Original pointer might have been invalidated. */
712 ptr_checks = ctx->asan_check_map.get (ptr);
713 }
714
715 gimple *g = maybe_get_dominating_check (*ptr_checks);
716 gimple *g2 = NULL;
717
718 if (base_checks)
719 /* Try with base address as well. */
720 g2 = maybe_get_dominating_check (*base_checks);
721
722 if (g == NULL && g2 == NULL)
723 {
724 /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
725 nothing to optimize yet. */
726 ptr_checks->safe_push (stmt);
727 if (base_checks)
728 base_checks->safe_push (stmt);
729 return false;
730 }
731
732 bool remove = false;
733
734 if (ptr_checks)
735 remove = can_remove_asan_check (*ptr_checks, len, bb);
736
737 if (!remove && base_checks)
738 /* Try with base address as well. */
739 remove = can_remove_asan_check (*base_checks, len, bb);
740
741 if (!remove)
742 {
743 ptr_checks->safe_push (stmt);
744 if (base_checks)
745 base_checks->safe_push (stmt);
746 }
747
748 return remove;
749}
750
751/* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
752
753 We walk blocks in the CFG via a depth first search of the dominator
754 tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
755 in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
756 blocks. When leaving a block, we mark the block as visited; then
757 when checking the statements in the vector, we ignore statements that
758 are coming from already visited blocks, because these cannot dominate
759 anything anymore. CTX is a sanopt context. */
760
761static void
762sanopt_optimize_walker (basic_block bb, struct sanopt_ctx *ctx)
763{
764 basic_block son;
765 gimple_stmt_iterator gsi;
766 sanopt_info *info = (sanopt_info *) bb->aux;
767 bool asan_check_optimize = (flag_sanitize & SANITIZE_ADDRESS) != 0;
768
769 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
770 {
771 gimple *stmt = gsi_stmt (gsi);
772 bool remove = false;
773
774 if (!is_gimple_call (stmt))
775 {
776 /* Handle asm volatile or asm with "memory" clobber
777 the same as potentionally freeing call. */
778 gasm *asm_stmt = dyn_cast <gasm *> (stmt);
779 if (asm_stmt
780 && asan_check_optimize
781 && (gimple_asm_clobbers_memory_p (asm_stmt)
782 || gimple_asm_volatile_p (asm_stmt)))
783 info->freeing_call_events++;
784 gsi_next (&gsi);
785 continue;
786 }
787
788 if (asan_check_optimize && !nonfreeing_call_p (stmt))
789 info->freeing_call_events++;
790
791 /* If __asan_before_dynamic_init ("module"); is followed by
792 __asan_after_dynamic_init (); without intervening memory loads/stores,
793 there is nothing to guard, so optimize both away. */
794 if (asan_check_optimize
795 && gimple_call_builtin_p (stmt, BUILT_IN_ASAN_BEFORE_DYNAMIC_INIT))
796 {
797 use_operand_p use;
798 gimple *use_stmt;
799 if (single_imm_use (gimple_vdef (stmt), &use, &use_stmt))
800 {
801 if (is_gimple_call (use_stmt)
802 && gimple_call_builtin_p (use_stmt,
803 BUILT_IN_ASAN_AFTER_DYNAMIC_INIT))
804 {
805 unlink_stmt_vdef (use_stmt);
806 gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
807 gsi_remove (&gsi2, true);
808 remove = true;
809 }
810 }
811 }
812
813 if (gimple_call_internal_p (stmt))
814 switch (gimple_call_internal_fn (stmt))
815 {
816 case IFN_UBSAN_NULL:
817 remove = maybe_optimize_ubsan_null_ifn (ctx, stmt);
818 break;
819 case IFN_UBSAN_VPTR:
820 remove = maybe_optimize_ubsan_vptr_ifn (ctx, stmt);
821 break;
822 case IFN_UBSAN_PTR:
823 remove = maybe_optimize_ubsan_ptr_ifn (ctx, stmt);
824 break;
825 case IFN_ASAN_CHECK:
826 if (asan_check_optimize)
827 remove = maybe_optimize_asan_check_ifn (ctx, stmt);
828 if (!remove)
829 ctx->asan_num_accesses++;
830 break;
831 case IFN_ASAN_MARK:
832 ctx->contains_asan_mark = true;
833 break;
834 default:
835 break;
836 }
837
838 if (remove)
839 {
840 /* Drop this check. */
841 if (dump_file && (dump_flags & TDF_DETAILS))
842 {
843 fprintf (dump_file, "Optimizing out: ");
844 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
845 }
846 unlink_stmt_vdef (stmt);
847 gsi_remove (&gsi, true);
848 }
849 else
850 {
851 if (dump_file && (dump_flags & TDF_DETAILS))
852 {
853 fprintf (dump_file, "Leaving: ");
854 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
855 }
856
857 gsi_next (&gsi);
858 }
859 }
860
861 if (asan_check_optimize)
862 {
863 info->has_freeing_call_p = info->freeing_call_events != 0;
864 info->has_freeing_call_computed_p = true;
865 }
866
867 for (son = first_dom_son (CDI_DOMINATORS, bb);
868 son;
869 son = next_dom_son (CDI_DOMINATORS, son))
870 sanopt_optimize_walker (son, ctx);
871
872 /* We're leaving this BB, so mark it to that effect. */
873 info->visited_p = true;
874}
875
876/* Try to remove redundant sanitizer checks in function FUN. */
877
878static int
879sanopt_optimize (function *fun, bool *contains_asan_mark)
880{
881 struct sanopt_ctx ctx;
882 ctx.asan_num_accesses = 0;
883 ctx.contains_asan_mark = false;
884
885 /* Set up block info for each basic block. */
886 alloc_aux_for_blocks (sizeof (sanopt_info));
887
888 /* We're going to do a dominator walk, so ensure that we have
889 dominance information. */
890 calculate_dominance_info (CDI_DOMINATORS);
891
892 /* Recursively walk the dominator tree optimizing away
893 redundant checks. */
894 sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun), &ctx);
895
896 free_aux_for_blocks ();
897
898 *contains_asan_mark = ctx.contains_asan_mark;
899 return ctx.asan_num_accesses;
900}
901
902/* Perform optimization of sanitize functions. */
903
904namespace {
905
906const pass_data pass_data_sanopt =
907{
908 GIMPLE_PASS, /* type */
909 "sanopt", /* name */
910 OPTGROUP_NONE, /* optinfo_flags */
911 TV_NONE, /* tv_id */
912 ( PROP_ssa | PROP_cfg | PROP_gimple_leh ), /* properties_required */
913 0, /* properties_provided */
914 0, /* properties_destroyed */
915 0, /* todo_flags_start */
916 TODO_update_ssa, /* todo_flags_finish */
917};
918
919class pass_sanopt : public gimple_opt_pass
920{
921public:
922 pass_sanopt (gcc::context *ctxt)
923 : gimple_opt_pass (pass_data_sanopt, ctxt)
924 {}
925
926 /* opt_pass methods: */
927 virtual bool gate (function *) { return flag_sanitize; }
928 virtual unsigned int execute (function *);
929
930}; // class pass_sanopt
931
932/* Sanitize all ASAN_MARK unpoison calls that are not reachable by a BB
933 that contains an ASAN_MARK poison. All these ASAN_MARK unpoison call
934 can be removed as all variables are unpoisoned in a function prologue. */
935
936static void
937sanitize_asan_mark_unpoison (void)
938{
939 /* 1) Find all BBs that contain an ASAN_MARK poison call. */
940 auto_sbitmap with_poison (last_basic_block_for_fn (cfun) + 1);
941 bitmap_clear (with_poison);
942 basic_block bb;
943
944 FOR_EACH_BB_FN (bb, cfun)
945 {
946 if (bitmap_bit_p (with_poison, bb->index))
947 continue;
948
949 gimple_stmt_iterator gsi;
950 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
951 {
952 gimple *stmt = gsi_stmt (gsi);
953 if (asan_mark_p (stmt, ASAN_MARK_POISON))
954 {
955 bitmap_set_bit (with_poison, bb->index);
956 break;
957 }
958 }
959 }
960
961 auto_sbitmap poisoned (last_basic_block_for_fn (cfun) + 1);
962 bitmap_clear (poisoned);
963 auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
964 bitmap_copy (worklist, with_poison);
965
966 /* 2) Propagate the information to all reachable blocks. */
967 while (!bitmap_empty_p (worklist))
968 {
969 unsigned i = bitmap_first_set_bit (worklist);
970 bitmap_clear_bit (worklist, i);
971 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
972 gcc_assert (bb);
973
974 edge e;
975 edge_iterator ei;
976 FOR_EACH_EDGE (e, ei, bb->succs)
977 if (!bitmap_bit_p (poisoned, e->dest->index))
978 {
979 bitmap_set_bit (poisoned, e->dest->index);
980 bitmap_set_bit (worklist, e->dest->index);
981 }
982 }
983
984 /* 3) Iterate all BBs not included in POISONED BBs and remove unpoison
985 ASAN_MARK preceding an ASAN_MARK poison (which can still happen). */
986 FOR_EACH_BB_FN (bb, cfun)
987 {
988 if (bitmap_bit_p (poisoned, bb->index))
989 continue;
990
991 gimple_stmt_iterator gsi;
992 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
993 {
994 gimple *stmt = gsi_stmt (gsi);
995 if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
996 {
997 if (asan_mark_p (stmt, ASAN_MARK_POISON))
998 break;
999 else
1000 {
1001 if (dump_file)
1002 fprintf (dump_file, "Removing ASAN_MARK unpoison\n");
1003 unlink_stmt_vdef (stmt);
1004 release_defs (stmt);
1005 gsi_remove (&gsi, true);
1006 continue;
1007 }
1008 }
1009
1010 gsi_next (&gsi);
1011 }
1012 }
1013}
1014
1015/* Return true when STMT is either ASAN_CHECK call or a call of a function
1016 that can contain an ASAN_CHECK. */
1017
1018static bool
1019maybe_contains_asan_check (gimple *stmt)
1020{
1021 if (is_gimple_call (stmt))
1022 {
1023 if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
1024 return false;
1025 else
1026 return !(gimple_call_flags (stmt) & ECF_CONST);
1027 }
1028 else if (is_a<gasm *> (stmt))
1029 return true;
1030
1031 return false;
1032}
1033
1034/* Sanitize all ASAN_MARK poison calls that are not followed by an ASAN_CHECK
1035 call. These calls can be removed. */
1036
1037static void
1038sanitize_asan_mark_poison (void)
1039{
1040 /* 1) Find all BBs that possibly contain an ASAN_CHECK. */
1041 auto_sbitmap with_check (last_basic_block_for_fn (cfun) + 1);
1042 bitmap_clear (with_check);
1043 basic_block bb;
1044
1045 FOR_EACH_BB_FN (bb, cfun)
1046 {
1047 gimple_stmt_iterator gsi;
1048 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
1049 {
1050 gimple *stmt = gsi_stmt (gsi);
1051 if (maybe_contains_asan_check (stmt))
1052 {
1053 bitmap_set_bit (with_check, bb->index);
1054 break;
1055 }
1056 }
1057 }
1058
1059 auto_sbitmap can_reach_check (last_basic_block_for_fn (cfun) + 1);
1060 bitmap_clear (can_reach_check);
1061 auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
1062 bitmap_copy (worklist, with_check);
1063
1064 /* 2) Propagate the information to all definitions blocks. */
1065 while (!bitmap_empty_p (worklist))
1066 {
1067 unsigned i = bitmap_first_set_bit (worklist);
1068 bitmap_clear_bit (worklist, i);
1069 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1070 gcc_assert (bb);
1071
1072 edge e;
1073 edge_iterator ei;
1074 FOR_EACH_EDGE (e, ei, bb->preds)
1075 if (!bitmap_bit_p (can_reach_check, e->src->index))
1076 {
1077 bitmap_set_bit (can_reach_check, e->src->index);
1078 bitmap_set_bit (worklist, e->src->index);
1079 }
1080 }
1081
1082 /* 3) Iterate all BBs not included in CAN_REACH_CHECK BBs and remove poison
1083 ASAN_MARK not followed by a call to function having an ASAN_CHECK. */
1084 FOR_EACH_BB_FN (bb, cfun)
1085 {
1086 if (bitmap_bit_p (can_reach_check, bb->index))
1087 continue;
1088
1089 gimple_stmt_iterator gsi;
1090 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
1091 {
1092 gimple *stmt = gsi_stmt (gsi);
1093 if (maybe_contains_asan_check (stmt))
1094 break;
1095 else if (asan_mark_p (stmt, ASAN_MARK_POISON))
1096 {
1097 if (dump_file)
1098 fprintf (dump_file, "Removing ASAN_MARK poison\n");
1099 unlink_stmt_vdef (stmt);
1100 release_defs (stmt);
1101 gimple_stmt_iterator gsi2 = gsi;
1102 gsi_prev (&gsi);
1103 gsi_remove (&gsi2, true);
1104 continue;
1105 }
1106
1107 gsi_prev (&gsi);
1108 }
1109 }
1110}
1111
1112/* Rewrite all usages of tree OP which is a PARM_DECL with a VAR_DECL
1113 that is it's DECL_VALUE_EXPR. */
1114
1115static tree
1116rewrite_usage_of_param (tree *op, int *walk_subtrees, void *)
1117{
1118 if (TREE_CODE (*op) == PARM_DECL && DECL_HAS_VALUE_EXPR_P (*op))
1119 {
1120 *op = DECL_VALUE_EXPR (*op);
1121 *walk_subtrees = 0;
1122 }
1123
1124 return NULL;
1125}
1126
1127/* For a given function FUN, rewrite all addressable parameters so that
1128 a new automatic variable is introduced. Right after function entry
1129 a parameter is assigned to the variable. */
1130
1131static void
1132sanitize_rewrite_addressable_params (function *fun)
1133{
1134 gimple *g;
1135 gimple_seq stmts = NULL;
1136 bool has_any_addressable_param = false;
1137 auto_vec<tree> clear_value_expr_list;
1138
1139 for (tree arg = DECL_ARGUMENTS (current_function_decl);
1140 arg; arg = DECL_CHAIN (arg))
1141 {
1142 tree type = TREE_TYPE (arg);
1143 if (TREE_ADDRESSABLE (arg) && !TREE_ADDRESSABLE (type)
1144 && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST)
1145 {
1146 TREE_ADDRESSABLE (arg) = 0;
1147 /* The parameter is no longer addressable. */
1148 has_any_addressable_param = true;
1149
1150 /* Create a new automatic variable. */
1151 tree var = build_decl (DECL_SOURCE_LOCATION (arg),
1152 VAR_DECL, DECL_NAME (arg), type);
1153 TREE_ADDRESSABLE (var) = 1;
1154 DECL_IGNORED_P (var) = 1;
1155
1156 gimple_add_tmp_var (var);
1157
1158 if (dump_file)
1159 fprintf (dump_file,
1160 "Rewriting parameter whose address is taken: %s\n",
1161 IDENTIFIER_POINTER (DECL_NAME (arg)));
1162
1163 gcc_assert (!DECL_HAS_VALUE_EXPR_P (arg));
1164
1165 SET_DECL_PT_UID (var, DECL_PT_UID (arg));
1166
1167 /* Assign value of parameter to newly created variable. */
1168 if ((TREE_CODE (type) == COMPLEX_TYPE
1169 || TREE_CODE (type) == VECTOR_TYPE))
1170 {
1171 /* We need to create a SSA name that will be used for the
1172 assignment. */
1173 DECL_GIMPLE_REG_P (arg) = 1;
1174 tree tmp = get_or_create_ssa_default_def (cfun, arg);
1175 g = gimple_build_assign (var, tmp);
1176 gimple_set_location (g, DECL_SOURCE_LOCATION (arg));
1177 gimple_seq_add_stmt (&stmts, g);
1178 }
1179 else
1180 {
1181 g = gimple_build_assign (var, arg);
1182 gimple_set_location (g, DECL_SOURCE_LOCATION (arg));
1183 gimple_seq_add_stmt (&stmts, g);
1184 }
1185
1186 if (target_for_debug_bind (arg))
1187 {
1188 g = gimple_build_debug_bind (arg, var, NULL);
1189 gimple_seq_add_stmt (&stmts, g);
1190 clear_value_expr_list.safe_push (arg);
1191 }
1192
1193 DECL_HAS_VALUE_EXPR_P (arg) = 1;
1194 SET_DECL_VALUE_EXPR (arg, var);
1195 }
1196 }
1197
1198 if (!has_any_addressable_param)
1199 return;
1200
1201 /* Replace all usages of PARM_DECLs with the newly
1202 created variable VAR. */
1203 basic_block bb;
1204 FOR_EACH_BB_FN (bb, fun)
1205 {
1206 gimple_stmt_iterator gsi;
1207 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1208 {
1209 gimple *stmt = gsi_stmt (gsi);
1210 gimple_stmt_iterator it = gsi_for_stmt (stmt);
1211 walk_gimple_stmt (&it, NULL, rewrite_usage_of_param, NULL);
1212 }
1213 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1214 {
1215 gphi *phi = dyn_cast<gphi *> (gsi_stmt (gsi));
1216 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
1217 {
1218 hash_set<tree> visited_nodes;
1219 walk_tree (gimple_phi_arg_def_ptr (phi, i),
1220 rewrite_usage_of_param, NULL, &visited_nodes);
1221 }
1222 }
1223 }
1224
1225 /* Unset value expr for parameters for which we created debug bind
1226 expressions. */
1227 unsigned i;
1228 tree arg;
1229 FOR_EACH_VEC_ELT (clear_value_expr_list, i, arg)
1230 {
1231 DECL_HAS_VALUE_EXPR_P (arg) = 0;
1232 SET_DECL_VALUE_EXPR (arg, NULL_TREE);
1233 }
1234
1235 /* Insert default assignments at the beginning of a function. */
1236 basic_block entry_bb = ENTRY_BLOCK_PTR_FOR_FN (fun);
1237 entry_bb = split_edge (single_succ_edge (entry_bb));
1238
1239 gimple_stmt_iterator gsi = gsi_start_bb (entry_bb);
1240 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
1241}
1242
1243unsigned int
1244pass_sanopt::execute (function *fun)
1245{
1246 basic_block bb;
1247 int asan_num_accesses = 0;
1248 bool contains_asan_mark = false;
1249
1250 /* Try to remove redundant checks. */
1251 if (optimize
1252 && (flag_sanitize
1253 & (SANITIZE_NULL | SANITIZE_ALIGNMENT
1254 | SANITIZE_ADDRESS | SANITIZE_VPTR | SANITIZE_POINTER_OVERFLOW)))
1255 asan_num_accesses = sanopt_optimize (fun, &contains_asan_mark);
1256 else if (flag_sanitize & SANITIZE_ADDRESS)
1257 {
1258 gimple_stmt_iterator gsi;
1259 FOR_EACH_BB_FN (bb, fun)
1260 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1261 {
1262 gimple *stmt = gsi_stmt (gsi);
1263 if (gimple_call_internal_p (stmt, IFN_ASAN_CHECK))
1264 ++asan_num_accesses;
1265 else if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
1266 contains_asan_mark = true;
1267 }
1268 }
1269
1270 if (contains_asan_mark)
1271 {
1272 sanitize_asan_mark_unpoison ();
1273 sanitize_asan_mark_poison ();
1274 }
1275
1276 if (asan_sanitize_stack_p ())
1277 sanitize_rewrite_addressable_params (fun);
1278
1279 bool use_calls = ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD < INT_MAX
1280 && asan_num_accesses >= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD;
1281
1282 hash_map<tree, tree> shadow_vars_mapping;
1283 bool need_commit_edge_insert = false;
1284 FOR_EACH_BB_FN (bb, fun)
1285 {
1286 gimple_stmt_iterator gsi;
1287 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1288 {
1289 gimple *stmt = gsi_stmt (gsi);
1290 bool no_next = false;
1291
1292 if (!is_gimple_call (stmt))
1293 {
1294 gsi_next (&gsi);
1295 continue;
1296 }
1297
1298 if (gimple_call_internal_p (stmt))
1299 {
1300 enum internal_fn ifn = gimple_call_internal_fn (stmt);
1301 switch (ifn)
1302 {
1303 case IFN_UBSAN_NULL:
1304 no_next = ubsan_expand_null_ifn (&gsi);
1305 break;
1306 case IFN_UBSAN_BOUNDS:
1307 no_next = ubsan_expand_bounds_ifn (&gsi);
1308 break;
1309 case IFN_UBSAN_OBJECT_SIZE:
1310 no_next = ubsan_expand_objsize_ifn (&gsi);
1311 break;
1312 case IFN_UBSAN_PTR:
1313 no_next = ubsan_expand_ptr_ifn (&gsi);
1314 break;
1315 case IFN_UBSAN_VPTR:
1316 no_next = ubsan_expand_vptr_ifn (&gsi);
1317 break;
1318 case IFN_ASAN_CHECK:
1319 no_next = asan_expand_check_ifn (&gsi, use_calls);
1320 break;
1321 case IFN_ASAN_MARK:
1322 no_next = asan_expand_mark_ifn (&gsi);
1323 break;
1324 case IFN_ASAN_POISON:
1325 no_next = asan_expand_poison_ifn (&gsi,
1326 &need_commit_edge_insert,
1327 shadow_vars_mapping);
1328 break;
1329 default:
1330 break;
1331 }
1332 }
1333 else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
1334 {
1335 tree callee = gimple_call_fndecl (stmt);
1336 switch (DECL_FUNCTION_CODE (callee))
1337 {
1338 case BUILT_IN_UNREACHABLE:
1339 if (sanitize_flags_p (SANITIZE_UNREACHABLE))
1340 no_next = ubsan_instrument_unreachable (&gsi);
1341 break;
1342 default:
1343 break;
1344 }
1345 }
1346
1347 if (dump_file && (dump_flags & TDF_DETAILS))
1348 {
1349 fprintf (dump_file, "Expanded: ");
1350 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
1351 }
1352
1353 if (!no_next)
1354 gsi_next (&gsi);
1355 }
1356 }
1357
1358 if (need_commit_edge_insert)
1359 gsi_commit_edge_inserts ();
1360
1361 return 0;
1362}
1363
1364} // anon namespace
1365
1366gimple_opt_pass *
1367make_pass_sanopt (gcc::context *ctxt)
1368{
1369 return new pass_sanopt (ctxt);
1370}
1371