gcc/sanopt.c

   1 /* Optimize and expand sanitizer functions.
   2    Copyright (C) 2014-2017 Free Software Foundation, Inc.
   3    Contributed by Marek Polacek <polacek@redhat.com>
   4
   5 This file is part of GCC.
   6
   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
  10 version.
  11
  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
  15 for more details.
  16
  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/>.  */
  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 "asan.h"
  34 #include "ubsan.h"
  35 #include "params.h"
  36 #include "tree-hash-traits.h"
  37 #include "gimple-ssa.h"
  38 #include "tree-phinodes.h"
  39 #include "ssa-iterators.h"
  40
  41 /* This is used to carry information about basic blocks.  It is
  42    attached to the AUX field of the standard CFG block.  */
  43
  44 struct sanopt_info
  45 {
  46   /* True if this BB might call (directly or indirectly) free/munmap
  47      or similar operation.  */
  48   bool has_freeing_call_p;
  49
  50   /* True if HAS_FREEING_CALL_P flag has been computed.  */
  51   bool has_freeing_call_computed_p;
  52
  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
  55      imm(BB), and BB.  */
  56   bool imm_dom_path_with_freeing_call_p;
  57
  58   /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed.  */
  59   bool imm_dom_path_with_freeing_call_computed_p;
  60
  61   /* Number of possibly freeing calls encountered in this bb
  62      (so far).  */
  63   uint64_t freeing_call_events;
  64
  65   /* True if BB is currently being visited during computation
  66      of IMM_DOM_PATH_WITH_FREEING_CALL_P flag.  */
  67   bool being_visited_p;
  68
  69   /* True if this BB has been visited in the dominator walk.  */
  70   bool visited_p;
  71 };
  72
  73 /* If T has a single definition of form T = T2, return T2.  */
  74
  75 static tree
  76 maybe_get_single_definition (tree t)
  77 {
  78   if (TREE_CODE (t) == SSA_NAME)
  79     {
  80       gimple *g = SSA_NAME_DEF_STMT (t);
  81       if (gimple_assign_single_p (g))
  82         return gimple_assign_rhs1 (g);
  83     }
  84   return NULL_TREE;
  85 }
  86
  87 /* Tree triplet for vptr_check_map.  */
  88 struct sanopt_tree_triplet
  89 {
  90   tree t1, t2, t3;
  91 };
  92
  93 /* Traits class for tree triplet hash maps below.  */
  94
  95 struct sanopt_tree_triplet_hash : typed_noop_remove <sanopt_tree_triplet>
  96 {
  97   typedef sanopt_tree_triplet value_type;
  98   typedef sanopt_tree_triplet compare_type;
  99
 100   static inline hashval_t
 101   hash (const sanopt_tree_triplet &ref)
 102   {
 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 ();
 108   }
 109
 110   static inline bool
 111   equal (const sanopt_tree_triplet &ref1, const sanopt_tree_triplet &ref2)
 112   {
 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);
 116   }
 117
 118   static inline void
 119   mark_deleted (sanopt_tree_triplet &ref)
 120   {
 121     ref.t1 = reinterpret_cast<tree> (1);
 122   }
 123
 124   static inline void
 125   mark_empty (sanopt_tree_triplet &ref)
 126   {
 127     ref.t1 = NULL;
 128   }
 129
 130   static inline bool
 131   is_deleted (const sanopt_tree_triplet &ref)
 132   {
 133     return ref.t1 == (void *) 1;
 134   }
 135
 136   static inline bool
 137   is_empty (const sanopt_tree_triplet &ref)
 138   {
 139     return ref.t1 == NULL;
 140   }
 141 };
 142
 143 /* This is used to carry various hash maps and variables used
 144    in sanopt_optimize_walker.  */
 145
 146 struct sanopt_ctx
 147 {
 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;
 151
 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;
 155
 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;
 160
 161   /* Number of IFN_ASAN_CHECK statements.  */
 162   int asan_num_accesses;
 163
 164   /* True when the current functions constains an ASAN_MARK.  */
 165   bool contains_asan_mark;
 166 };
 167
 168 /* Return true if there might be any call to free/munmap operation
 169    on any path in between DOM (which should be imm(BB)) and BB.  */
 170
 171 static bool
 172 imm_dom_path_with_freeing_call (basic_block bb, basic_block dom)
 173 {
 174   sanopt_info *info = (sanopt_info *) bb->aux;
 175   edge e;
 176   edge_iterator ei;
 177
 178   if (info->imm_dom_path_with_freeing_call_computed_p)
 179     return info->imm_dom_path_with_freeing_call_p;
 180
 181   info->being_visited_p = true;
 182
 183   FOR_EACH_EDGE (e, ei, bb->preds)
 184     {
 185       sanopt_info *pred_info = (sanopt_info *) e->src->aux;
 186
 187       if (e->src == dom)
 188         continue;
 189
 190       if ((pred_info->imm_dom_path_with_freeing_call_computed_p
 191           && pred_info->imm_dom_path_with_freeing_call_p)
 192           || (pred_info->has_freeing_call_computed_p
 193               && pred_info->has_freeing_call_p))
 194         {
 195           info->imm_dom_path_with_freeing_call_computed_p = true;
 196           info->imm_dom_path_with_freeing_call_p = true;
 197           info->being_visited_p = false;
 198           return true;
 199         }
 200     }
 201
 202   FOR_EACH_EDGE (e, ei, bb->preds)
 203     {
 204       sanopt_info *pred_info = (sanopt_info *) e->src->aux;
 205
 206       if (e->src == dom)
 207         continue;
 208
 209       if (pred_info->has_freeing_call_computed_p)
 210         continue;
 211
 212       gimple_stmt_iterator gsi;
 213       for (gsi = gsi_start_bb (e->src); !gsi_end_p (gsi); gsi_next (&gsi))
 214         {
 215           gimple *stmt = gsi_stmt (gsi);
 216           gasm *asm_stmt;
 217
 218           if ((is_gimple_call (stmt) && !nonfreeing_call_p (stmt))
 219               || ((asm_stmt = dyn_cast <gasm *> (stmt))
 220                   && (gimple_asm_clobbers_memory_p (asm_stmt)
 221                       || gimple_asm_volatile_p (asm_stmt))))
 222             {
 223               pred_info->has_freeing_call_p = true;
 224               break;
 225             }
 226         }
 227
 228       pred_info->has_freeing_call_computed_p = true;
 229       if (pred_info->has_freeing_call_p)
 230         {
 231           info->imm_dom_path_with_freeing_call_computed_p = true;
 232           info->imm_dom_path_with_freeing_call_p = true;
 233           info->being_visited_p = false;
 234           return true;
 235         }
 236     }
 237
 238   FOR_EACH_EDGE (e, ei, bb->preds)
 239     {
 240       if (e->src == dom)
 241         continue;
 242
 243       basic_block src;
 244       for (src = e->src; src != dom; )
 245         {
 246           sanopt_info *pred_info = (sanopt_info *) src->aux;
 247           if (pred_info->being_visited_p)
 248             break;
 249           basic_block imm = get_immediate_dominator (CDI_DOMINATORS, src);
 250           if (imm_dom_path_with_freeing_call (src, imm))
 251             {
 252               info->imm_dom_path_with_freeing_call_computed_p = true;
 253               info->imm_dom_path_with_freeing_call_p = true;
 254               info->being_visited_p = false;
 255               return true;
 256             }
 257           src = imm;
 258         }
 259     }
 260
 261   info->imm_dom_path_with_freeing_call_computed_p = true;
 262   info->imm_dom_path_with_freeing_call_p = false;
 263   info->being_visited_p = false;
 264   return false;
 265 }
 266
 267 /* Get the first dominating check from the list of stored checks.
 268    Non-dominating checks are silently dropped.  */
 269
 270 static gimple *
 271 maybe_get_dominating_check (auto_vec<gimple *> &v)
 272 {
 273   for (; !v.is_empty (); v.pop ())
 274     {
 275       gimple *g = v.last ();
 276       sanopt_info *si = (sanopt_info *) gimple_bb (g)->aux;
 277       if (!si->visited_p)
 278         /* At this point we shouldn't have any statements
 279            that aren't dominating the current BB.  */
 280         return g;
 281     }
 282   return NULL;
 283 }
 284
 285 /* Optimize away redundant UBSAN_NULL calls.  */
 286
 287 static bool
 288 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx *ctx, gimple *stmt)
 289 {
 290   gcc_assert (gimple_call_num_args (stmt) == 3);
 291   tree ptr = gimple_call_arg (stmt, 0);
 292   tree cur_align = gimple_call_arg (stmt, 2);
 293   gcc_assert (TREE_CODE (cur_align) == INTEGER_CST);
 294   bool remove = false;
 295
 296   auto_vec<gimple *> &v = ctx->null_check_map.get_or_insert (ptr);
 297   gimple *g = maybe_get_dominating_check (v);
 298   if (!g)
 299     {
 300       /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
 301          nothing to optimize yet.  */
 302       v.safe_push (stmt);
 303       return false;
 304     }
 305
 306   /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
 307      can drop this one.  But only if this check doesn't specify stricter
 308      alignment.  */
 309
 310   tree align = gimple_call_arg (g, 2);
 311   int kind = tree_to_shwi (gimple_call_arg (g, 1));
 312   /* If this is a NULL pointer check where we had segv anyway, we can
 313      remove it.  */
 314   if (integer_zerop (align)
 315       && (kind == UBSAN_LOAD_OF
 316           || kind == UBSAN_STORE_OF
 317           || kind == UBSAN_MEMBER_ACCESS))
 318     remove = true;
 319   /* Otherwise remove the check in non-recovering mode, or if the
 320      stmts have same location.  */
 321   else if (integer_zerop (align))
 322     remove = (flag_sanitize_recover & SANITIZE_NULL) == 0
 323               || flag_sanitize_undefined_trap_on_error
 324               || gimple_location (g) == gimple_location (stmt);
 325   else if (tree_int_cst_le (cur_align, align))
 326     remove = (flag_sanitize_recover & SANITIZE_ALIGNMENT) == 0
 327               || flag_sanitize_undefined_trap_on_error
 328               || gimple_location (g) == gimple_location (stmt);
 329
 330   if (!remove && gimple_bb (g) == gimple_bb (stmt)
 331       && tree_int_cst_compare (cur_align, align) == 0)
 332     v.pop ();
 333
 334   if (!remove)
 335     v.safe_push (stmt);
 336   return remove;
 337 }
 338
 339 /* Optimize away redundant UBSAN_VPTR calls.  The second argument
 340    is the value loaded from the virtual table, so rely on FRE to find out
 341    when we can actually optimize.  */
 342
 343 static bool
 344 maybe_optimize_ubsan_vptr_ifn (struct sanopt_ctx *ctx, gimple *stmt)
 345 {
 346   gcc_assert (gimple_call_num_args (stmt) == 5);
 347   sanopt_tree_triplet triplet;
 348   triplet.t1 = gimple_call_arg (stmt, 0);
 349   triplet.t2 = gimple_call_arg (stmt, 1);
 350   triplet.t3 = gimple_call_arg (stmt, 3);
 351
 352   auto_vec<gimple *> &v = ctx->vptr_check_map.get_or_insert (triplet);
 353   gimple *g = maybe_get_dominating_check (v);
 354   if (!g)
 355     {
 356       /* For this PTR we don't have any UBSAN_VPTR stmts recorded, so there's
 357          nothing to optimize yet.  */
 358       v.safe_push (stmt);
 359       return false;
 360     }
 361
 362   return true;
 363 }
 364
 365 /* Returns TRUE if ASan check of length LEN in block BB can be removed
 366    if preceded by checks in V.  */
 367
 368 static bool
 369 can_remove_asan_check (auto_vec<gimple *> &v, tree len, basic_block bb)
 370 {
 371   unsigned int i;
 372   gimple *g;
 373   gimple *to_pop = NULL;
 374   bool remove = false;
 375   basic_block last_bb = bb;
 376   bool cleanup = false;
 377
 378   FOR_EACH_VEC_ELT_REVERSE (v, i, g)
 379     {
 380       basic_block gbb = gimple_bb (g);
 381       sanopt_info *si = (sanopt_info *) gbb->aux;
 382       if (gimple_uid (g) < si->freeing_call_events)
 383         {
 384           /* If there is a potentially freeing call after g in gbb, we should
 385              remove it from the vector, can't use in optimization.  */
 386           cleanup = true;
 387           continue;
 388         }
 389
 390       tree glen = gimple_call_arg (g, 2);
 391       gcc_assert (TREE_CODE (glen) == INTEGER_CST);
 392
 393       /* If we've checked only smaller length than we want to check now,
 394          we can't remove the current stmt.  If g is in the same basic block,
 395          we want to remove it though, as the current stmt is better.  */
 396       if (tree_int_cst_lt (glen, len))
 397         {
 398           if (gbb == bb)
 399             {
 400               to_pop = g;
 401               cleanup = true;
 402             }
 403           continue;
 404         }
 405
 406       while (last_bb != gbb)
 407         {
 408           /* Paths from last_bb to bb have been checked before.
 409              gbb is necessarily a dominator of last_bb, but not necessarily
 410              immediate dominator.  */
 411           if (((sanopt_info *) last_bb->aux)->freeing_call_events)
 412             break;
 413
 414           basic_block imm = get_immediate_dominator (CDI_DOMINATORS, last_bb);
 415           gcc_assert (imm);
 416           if (imm_dom_path_with_freeing_call (last_bb, imm))
 417             break;
 418
 419           last_bb = imm;
 420         }
 421       if (last_bb == gbb)
 422         remove = true;
 423       break;
 424     }
 425
 426   if (cleanup)
 427     {
 428       unsigned int j = 0, l = v.length ();
 429       for (i = 0; i < l; i++)
 430         if (v[i] != to_pop
 431             && (gimple_uid (v[i])
 432                 == ((sanopt_info *)
 433                     gimple_bb (v[i])->aux)->freeing_call_events))
 434           {
 435             if (i != j)
 436               v[j] = v[i];
 437             j++;
 438           }
 439       v.truncate (j);
 440     }
 441
 442   return remove;
 443 }
 444
 445 /* Optimize away redundant ASAN_CHECK calls.  */
 446
 447 static bool
 448 maybe_optimize_asan_check_ifn (struct sanopt_ctx *ctx, gimple *stmt)
 449 {
 450   gcc_assert (gimple_call_num_args (stmt) == 4);
 451   tree ptr = gimple_call_arg (stmt, 1);
 452   tree len = gimple_call_arg (stmt, 2);
 453   basic_block bb = gimple_bb (stmt);
 454   sanopt_info *info = (sanopt_info *) bb->aux;
 455
 456   if (TREE_CODE (len) != INTEGER_CST)
 457     return false;
 458   if (integer_zerop (len))
 459     return false;
 460
 461   gimple_set_uid (stmt, info->freeing_call_events);
 462
 463   auto_vec<gimple *> *ptr_checks = &ctx->asan_check_map.get_or_insert (ptr);
 464
 465   tree base_addr = maybe_get_single_definition (ptr);
 466   auto_vec<gimple *> *base_checks = NULL;
 467   if (base_addr)
 468     {
 469       base_checks = &ctx->asan_check_map.get_or_insert (base_addr);
 470       /* Original pointer might have been invalidated.  */
 471       ptr_checks = ctx->asan_check_map.get (ptr);
 472     }
 473
 474   gimple *g = maybe_get_dominating_check (*ptr_checks);
 475   gimple *g2 = NULL;
 476
 477   if (base_checks)
 478     /* Try with base address as well.  */
 479     g2 = maybe_get_dominating_check (*base_checks);
 480
 481   if (g == NULL && g2 == NULL)
 482     {
 483       /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
 484          nothing to optimize yet.  */
 485       ptr_checks->safe_push (stmt);
 486       if (base_checks)
 487         base_checks->safe_push (stmt);
 488       return false;
 489     }
 490
 491   bool remove = false;
 492
 493   if (ptr_checks)
 494     remove = can_remove_asan_check (*ptr_checks, len, bb);
 495
 496   if (!remove && base_checks)
 497     /* Try with base address as well.  */
 498     remove = can_remove_asan_check (*base_checks, len, bb);
 499
 500   if (!remove)
 501     {
 502       ptr_checks->safe_push (stmt);
 503       if (base_checks)
 504         base_checks->safe_push (stmt);
 505     }
 506
 507   return remove;
 508 }
 509
 510 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
 511
 512    We walk blocks in the CFG via a depth first search of the dominator
 513    tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
 514    in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
 515    blocks.  When leaving a block, we mark the block as visited; then
 516    when checking the statements in the vector, we ignore statements that
 517    are coming from already visited blocks, because these cannot dominate
 518    anything anymore.  CTX is a sanopt context.  */
 519
 520 static void
 521 sanopt_optimize_walker (basic_block bb, struct sanopt_ctx *ctx)
 522 {
 523   basic_block son;
 524   gimple_stmt_iterator gsi;
 525   sanopt_info *info = (sanopt_info *) bb->aux;
 526   bool asan_check_optimize = (flag_sanitize & SANITIZE_ADDRESS) != 0;
 527
 528   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 529     {
 530       gimple *stmt = gsi_stmt (gsi);
 531       bool remove = false;
 532
 533       if (!is_gimple_call (stmt))
 534         {
 535           /* Handle asm volatile or asm with "memory" clobber
 536              the same as potentionally freeing call.  */
 537           gasm *asm_stmt = dyn_cast <gasm *> (stmt);
 538           if (asm_stmt
 539               && asan_check_optimize
 540               && (gimple_asm_clobbers_memory_p (asm_stmt)
 541                   || gimple_asm_volatile_p (asm_stmt)))
 542             info->freeing_call_events++;
 543           gsi_next (&gsi);
 544           continue;
 545         }
 546
 547       if (asan_check_optimize && !nonfreeing_call_p (stmt))
 548         info->freeing_call_events++;
 549
 550       /* If __asan_before_dynamic_init ("module"); is followed by
 551          __asan_after_dynamic_init (); without intervening memory loads/stores,
 552          there is nothing to guard, so optimize both away.  */
 553       if (asan_check_optimize
 554           && gimple_call_builtin_p (stmt, BUILT_IN_ASAN_BEFORE_DYNAMIC_INIT))
 555         {
 556           use_operand_p use;
 557           gimple *use_stmt;
 558           if (single_imm_use (gimple_vdef (stmt), &use, &use_stmt))
 559             {
 560               if (is_gimple_call (use_stmt)
 561                   && gimple_call_builtin_p (use_stmt,
 562                                             BUILT_IN_ASAN_AFTER_DYNAMIC_INIT))
 563                 {
 564                   unlink_stmt_vdef (use_stmt);
 565                   gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
 566                   gsi_remove (&gsi2, true);
 567                   remove = true;
 568                 }
 569             }
 570         }
 571
 572       if (gimple_call_internal_p (stmt))
 573         switch (gimple_call_internal_fn (stmt))
 574           {
 575           case IFN_UBSAN_NULL:
 576             remove = maybe_optimize_ubsan_null_ifn (ctx, stmt);
 577             break;
 578           case IFN_UBSAN_VPTR:
 579             remove = maybe_optimize_ubsan_vptr_ifn (ctx, stmt);
 580             break;
 581           case IFN_ASAN_CHECK:
 582             if (asan_check_optimize)
 583               remove = maybe_optimize_asan_check_ifn (ctx, stmt);
 584             if (!remove)
 585               ctx->asan_num_accesses++;
 586             break;
 587           case IFN_ASAN_MARK:
 588             ctx->contains_asan_mark = true;
 589             break;
 590           default:
 591             break;
 592           }
 593
 594       if (remove)
 595         {
 596           /* Drop this check.  */
 597           if (dump_file && (dump_flags & TDF_DETAILS))
 598             {
 599               fprintf (dump_file, "Optimizing out\n  ");
 600               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 601               fprintf (dump_file, "\n");
 602             }
 603           unlink_stmt_vdef (stmt);
 604           gsi_remove (&gsi, true);
 605         }
 606       else
 607         gsi_next (&gsi);
 608     }
 609
 610   if (asan_check_optimize)
 611     {
 612       info->has_freeing_call_p = info->freeing_call_events != 0;
 613       info->has_freeing_call_computed_p = true;
 614     }
 615
 616   for (son = first_dom_son (CDI_DOMINATORS, bb);
 617        son;
 618        son = next_dom_son (CDI_DOMINATORS, son))
 619     sanopt_optimize_walker (son, ctx);
 620
 621   /* We're leaving this BB, so mark it to that effect.  */
 622   info->visited_p = true;
 623 }
 624
 625 /* Try to remove redundant sanitizer checks in function FUN.  */
 626
 627 static int
 628 sanopt_optimize (function *fun, bool *contains_asan_mark)
 629 {
 630   struct sanopt_ctx ctx;
 631   ctx.asan_num_accesses = 0;
 632   ctx.contains_asan_mark = false;
 633
 634   /* Set up block info for each basic block.  */
 635   alloc_aux_for_blocks (sizeof (sanopt_info));
 636
 637   /* We're going to do a dominator walk, so ensure that we have
 638      dominance information.  */
 639   calculate_dominance_info (CDI_DOMINATORS);
 640
 641   /* Recursively walk the dominator tree optimizing away
 642      redundant checks.  */
 643   sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun), &ctx);
 644
 645   free_aux_for_blocks ();
 646
 647   *contains_asan_mark = ctx.contains_asan_mark;
 648   return ctx.asan_num_accesses;
 649 }
 650
 651 /* Perform optimization of sanitize functions.  */
 652
 653 namespace {
 654
 655 const pass_data pass_data_sanopt =
 656 {
 657   GIMPLE_PASS, /* type */
 658   "sanopt", /* name */
 659   OPTGROUP_NONE, /* optinfo_flags */
 660   TV_NONE, /* tv_id */
 661   ( PROP_ssa | PROP_cfg | PROP_gimple_leh ), /* properties_required */
 662   0, /* properties_provided */
 663   0, /* properties_destroyed */
 664   0, /* todo_flags_start */
 665   TODO_update_ssa, /* todo_flags_finish */
 666 };
 667
 668 class pass_sanopt : public gimple_opt_pass
 669 {
 670 public:
 671   pass_sanopt (gcc::context *ctxt)
 672     : gimple_opt_pass (pass_data_sanopt, ctxt)
 673   {}
 674
 675   /* opt_pass methods: */
 676   virtual bool gate (function *) { return flag_sanitize; }
 677   virtual unsigned int execute (function *);
 678
 679 }; // class pass_sanopt
 680
 681 /* Sanitize all ASAN_MARK unpoison calls that are not reachable by a BB
 682    that contains an ASAN_MARK poison.  All these ASAN_MARK unpoison call
 683    can be removed as all variables are unpoisoned in a function prologue.  */
 684
 685 static void
 686 sanitize_asan_mark_unpoison (void)
 687 {
 688   /* 1) Find all BBs that contain an ASAN_MARK poison call.  */
 689   auto_sbitmap with_poison (last_basic_block_for_fn (cfun) + 1);
 690   bitmap_clear (with_poison);
 691   basic_block bb;
 692
 693   FOR_EACH_BB_FN (bb, cfun)
 694     {
 695       if (bitmap_bit_p (with_poison, bb->index))
 696         continue;
 697
 698       gimple_stmt_iterator gsi;
 699       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 700         {
 701           gimple *stmt = gsi_stmt (gsi);
 702           if (asan_mark_p (stmt, ASAN_MARK_POISON))
 703             {
 704               bitmap_set_bit (with_poison, bb->index);
 705               break;
 706             }
 707         }
 708     }
 709
 710   auto_sbitmap poisoned (last_basic_block_for_fn (cfun) + 1);
 711   bitmap_clear (poisoned);
 712   auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
 713   bitmap_copy (worklist, with_poison);
 714
 715   /* 2) Propagate the information to all reachable blocks.  */
 716   while (!bitmap_empty_p (worklist))
 717     {
 718       unsigned i = bitmap_first_set_bit (worklist);
 719       bitmap_clear_bit (worklist, i);
 720       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
 721       gcc_assert (bb);
 722
 723       edge e;
 724       edge_iterator ei;
 725       FOR_EACH_EDGE (e, ei, bb->succs)
 726         if (!bitmap_bit_p (poisoned, e->dest->index))
 727           {
 728             bitmap_set_bit (poisoned, e->dest->index);
 729             bitmap_set_bit (worklist, e->dest->index);
 730           }
 731     }
 732
 733   /* 3) Iterate all BBs not included in POISONED BBs and remove unpoison
 734         ASAN_MARK preceding an ASAN_MARK poison (which can still happen).  */
 735   FOR_EACH_BB_FN (bb, cfun)
 736     {
 737       if (bitmap_bit_p (poisoned, bb->index))
 738         continue;
 739
 740       gimple_stmt_iterator gsi;
 741       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 742         {
 743           gimple *stmt = gsi_stmt (gsi);
 744           if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
 745             {
 746               if (asan_mark_p (stmt, ASAN_MARK_POISON))
 747                 break;
 748               else
 749                 {
 750                   if (dump_file)
 751                     fprintf (dump_file, "Removing ASAN_MARK unpoison\n");
 752                   unlink_stmt_vdef (stmt);
 753                   release_defs (stmt);
 754                   gsi_remove (&gsi, true);
 755                   continue;
 756                 }
 757             }
 758
 759           gsi_next (&gsi);
 760         }
 761     }
 762 }
 763
 764 /* Return true when STMT is either ASAN_CHECK call or a call of a function
 765    that can contain an ASAN_CHECK.  */
 766
 767 static bool
 768 maybe_contains_asan_check (gimple *stmt)
 769 {
 770   if (is_gimple_call (stmt))
 771     {
 772       if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
 773         return false;
 774       else
 775         return !(gimple_call_flags (stmt) & ECF_CONST);
 776     }
 777   else if (is_a<gasm *> (stmt))
 778     return true;
 779
 780   return false;
 781 }
 782
 783 /* Sanitize all ASAN_MARK poison calls that are not followed by an ASAN_CHECK
 784    call.  These calls can be removed.  */
 785
 786 static void
 787 sanitize_asan_mark_poison (void)
 788 {
 789   /* 1) Find all BBs that possibly contain an ASAN_CHECK.  */
 790   auto_sbitmap with_check (last_basic_block_for_fn (cfun) + 1);
 791   bitmap_clear (with_check);
 792   basic_block bb;
 793
 794   FOR_EACH_BB_FN (bb, cfun)
 795     {
 796       gimple_stmt_iterator gsi;
 797       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 798         {
 799           gimple *stmt = gsi_stmt (gsi);
 800           if (maybe_contains_asan_check (stmt))
 801             {
 802               bitmap_set_bit (with_check, bb->index);
 803               break;
 804             }
 805         }
 806     }
 807
 808   auto_sbitmap can_reach_check (last_basic_block_for_fn (cfun) + 1);
 809   bitmap_clear (can_reach_check);
 810   auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
 811   bitmap_copy (worklist, with_check);
 812
 813   /* 2) Propagate the information to all definitions blocks.  */
 814   while (!bitmap_empty_p (worklist))
 815     {
 816       unsigned i = bitmap_first_set_bit (worklist);
 817       bitmap_clear_bit (worklist, i);
 818       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
 819       gcc_assert (bb);
 820
 821       edge e;
 822       edge_iterator ei;
 823       FOR_EACH_EDGE (e, ei, bb->preds)
 824         if (!bitmap_bit_p (can_reach_check, e->src->index))
 825           {
 826             bitmap_set_bit (can_reach_check, e->src->index);
 827             bitmap_set_bit (worklist, e->src->index);
 828           }
 829     }
 830
 831   /* 3) Iterate all BBs not included in CAN_REACH_CHECK BBs and remove poison
 832         ASAN_MARK not followed by a call to function having an ASAN_CHECK.  */
 833   FOR_EACH_BB_FN (bb, cfun)
 834     {
 835       if (bitmap_bit_p (can_reach_check, bb->index))
 836         continue;
 837
 838       gimple_stmt_iterator gsi;
 839       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 840         {
 841           gimple *stmt = gsi_stmt (gsi);
 842           if (maybe_contains_asan_check (stmt))
 843             break;
 844           else if (asan_mark_p (stmt, ASAN_MARK_POISON))
 845             {
 846               if (dump_file)
 847                 fprintf (dump_file, "Removing ASAN_MARK poison\n");
 848               unlink_stmt_vdef (stmt);
 849               release_defs (stmt);
 850               gimple_stmt_iterator gsi2 = gsi;
 851               gsi_prev (&gsi);
 852               gsi_remove (&gsi2, true);
 853               continue;
 854             }
 855
 856           gsi_prev (&gsi);
 857         }
 858     }
 859 }
 860
 861 unsigned int
 862 pass_sanopt::execute (function *fun)
 863 {
 864   basic_block bb;
 865   int asan_num_accesses = 0;
 866   bool contains_asan_mark = false;
 867
 868   /* Try to remove redundant checks.  */
 869   if (optimize
 870       && (flag_sanitize
 871           & (SANITIZE_NULL | SANITIZE_ALIGNMENT
 872              | SANITIZE_ADDRESS | SANITIZE_VPTR)))
 873     asan_num_accesses = sanopt_optimize (fun, &contains_asan_mark);
 874   else if (flag_sanitize & SANITIZE_ADDRESS)
 875     {
 876       gimple_stmt_iterator gsi;
 877       FOR_EACH_BB_FN (bb, fun)
 878         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 879           {
 880             gimple *stmt = gsi_stmt (gsi);
 881             if (gimple_call_internal_p (stmt, IFN_ASAN_CHECK))
 882               ++asan_num_accesses;
 883             else if (gimple_call_internal_p (stmt, IFN_ASAN_MARK))
 884               contains_asan_mark = true;
 885           }
 886     }
 887
 888   if (contains_asan_mark)
 889     {
 890       sanitize_asan_mark_unpoison ();
 891       sanitize_asan_mark_poison ();
 892     }
 893
 894   bool use_calls = ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD < INT_MAX
 895     && asan_num_accesses >= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD;
 896
 897   hash_map<tree, tree> shadow_vars_mapping;
 898   bool need_commit_edge_insert = false;
 899   FOR_EACH_BB_FN (bb, fun)
 900     {
 901       gimple_stmt_iterator gsi;
 902       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 903         {
 904           gimple *stmt = gsi_stmt (gsi);
 905           bool no_next = false;
 906
 907           if (!is_gimple_call (stmt))
 908             {
 909               gsi_next (&gsi);
 910               continue;
 911             }
 912
 913           if (gimple_call_internal_p (stmt))
 914             {
 915               enum internal_fn ifn = gimple_call_internal_fn (stmt);
 916               switch (ifn)
 917                 {
 918                 case IFN_UBSAN_NULL:
 919                   no_next = ubsan_expand_null_ifn (&gsi);
 920                   break;
 921                 case IFN_UBSAN_BOUNDS:
 922                   no_next = ubsan_expand_bounds_ifn (&gsi);
 923                   break;
 924                 case IFN_UBSAN_OBJECT_SIZE:
 925                   no_next = ubsan_expand_objsize_ifn (&gsi);
 926                   break;
 927                 case IFN_UBSAN_VPTR:
 928                   no_next = ubsan_expand_vptr_ifn (&gsi);
 929                   break;
 930                 case IFN_ASAN_CHECK:
 931                   no_next = asan_expand_check_ifn (&gsi, use_calls);
 932                   break;
 933                 case IFN_ASAN_MARK:
 934                   no_next = asan_expand_mark_ifn (&gsi);
 935                   break;
 936                 case IFN_ASAN_POISON:
 937                   no_next = asan_expand_poison_ifn (&gsi,
 938                                                     &need_commit_edge_insert,
 939                                                     shadow_vars_mapping);
 940                   break;
 941                 default:
 942                   break;
 943                 }
 944             }
 945           else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
 946             {
 947               tree callee = gimple_call_fndecl (stmt);
 948               switch (DECL_FUNCTION_CODE (callee))
 949                 {
 950                 case BUILT_IN_UNREACHABLE:
 951                   if (flag_sanitize & SANITIZE_UNREACHABLE
 952                       && !lookup_attribute ("no_sanitize_undefined",
 953                                             DECL_ATTRIBUTES (fun->decl)))
 954                     no_next = ubsan_instrument_unreachable (&gsi);
 955                   break;
 956                 default:
 957                   break;
 958                 }
 959             }
 960
 961           if (dump_file && (dump_flags & TDF_DETAILS))
 962             {
 963               fprintf (dump_file, "Expanded\n  ");
 964               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 965               fprintf (dump_file, "\n");
 966             }
 967
 968           if (!no_next)
 969             gsi_next (&gsi);
 970         }
 971     }
 972
 973   if (need_commit_edge_insert)
 974     gsi_commit_edge_inserts ();
 975
 976   return 0;
 977 }
 978
 979 } // anon namespace
 980
 981 gimple_opt_pass *
 982 make_pass_sanopt (gcc::context *ctxt)
 983 {
 984   return new pass_sanopt (ctxt);
 985 }