gcc/sanopt.c

   1 /* Optimize and expand sanitizer functions.
   2    Copyright (C) 2014 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 "tree.h"
  25 #include "hash-table.h"
  26 #include "predict.h"
  27 #include "vec.h"
  28 #include "hashtab.h"
  29 #include "hash-set.h"
  30 #include "tm.h"
  31 #include "hard-reg-set.h"
  32 #include "function.h"
  33 #include "dominance.h"
  34 #include "cfg.h"
  35 #include "basic-block.h"
  36 #include "tree-ssa-alias.h"
  37 #include "internal-fn.h"
  38 #include "gimple-expr.h"
  39 #include "is-a.h"
  40 #include "gimple.h"
  41 #include "gimplify.h"
  42 #include "gimple-iterator.h"
  43 #include "hash-map.h"
  44 #include "plugin-api.h"
  45 #include "tree-pass.h"
  46 #include "asan.h"
  47 #include "gimple-pretty-print.h"
  48 #include "tm_p.h"
  49 #include "langhooks.h"
  50 #include "ubsan.h"
  51 #include "params.h"
  52 #include "tree-ssa-operands.h"
  53
  54
  55 /* This is used to carry information about basic blocks.  It is
  56    attached to the AUX field of the standard CFG block.  */
  57
  58 struct sanopt_info
  59 {
  60   /* True if this BB might call (directly or indirectly) free/munmap
  61      or similar operation.  */
  62   bool has_freeing_call_p;
  63
  64   /* True if HAS_FREEING_CALL_P flag has been computed.  */
  65   bool has_freeing_call_computed_p;
  66
  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
  69      imm(BB), and BB.  */
  70   bool imm_dom_path_with_freeing_call_p;
  71
  72   /* True if IMM_DOM_PATH_WITH_FREEING_CALL_P has been computed.  */
  73   bool imm_dom_path_with_freeing_call_computed_p;
  74
  75   /* Number of possibly freeing calls encountered in this bb
  76      (so far).  */
  77   uint64_t freeing_call_events;
  78
  79   /* True if BB is currently being visited during computation
  80      of IMM_DOM_PATH_WITH_FREEING_CALL_P flag.  */
  81   bool being_visited_p;
  82
  83   /* True if this BB has been visited in the dominator walk.  */
  84   bool visited_p;
  85 };
  86
  87 /* This is used to carry various hash maps and variables used
  88    in sanopt_optimize_walker.  */
  89
  90 struct sanopt_ctx
  91 {
  92   /* This map maps a pointer (the first argument of UBSAN_NULL) to
  93      a vector of UBSAN_NULL call statements that check this pointer.  */
  94   hash_map<tree, auto_vec<gimple> > null_check_map;
  95
  96   /* This map maps a pointer (the second argument of ASAN_CHECK) to
  97      a vector of ASAN_CHECK call statements that check the access.  */
  98   hash_map<tree, auto_vec<gimple> > asan_check_map;
  99
 100   /* Number of IFN_ASAN_CHECK statements.  */
 101   int asan_num_accesses;
 102 };
 103
 104
 105 /* Return true if there might be any call to free/munmap operation
 106    on any path in between DOM (which should be imm(BB)) and BB.  */
 107
 108 static bool
 109 imm_dom_path_with_freeing_call (basic_block bb, basic_block dom)
 110 {
 111   sanopt_info *info = (sanopt_info *) bb->aux;
 112   edge e;
 113   edge_iterator ei;
 114
 115   if (info->imm_dom_path_with_freeing_call_computed_p)
 116     return info->imm_dom_path_with_freeing_call_p;
 117
 118   info->being_visited_p = true;
 119
 120   FOR_EACH_EDGE (e, ei, bb->preds)
 121     {
 122       sanopt_info *pred_info = (sanopt_info *) e->src->aux;
 123
 124       if (e->src == dom)
 125         continue;
 126
 127       if ((pred_info->imm_dom_path_with_freeing_call_computed_p
 128           && pred_info->imm_dom_path_with_freeing_call_p)
 129           || (pred_info->has_freeing_call_computed_p
 130               && pred_info->has_freeing_call_p))
 131         {
 132           info->imm_dom_path_with_freeing_call_computed_p = true;
 133           info->imm_dom_path_with_freeing_call_p = true;
 134           info->being_visited_p = false;
 135           return true;
 136         }
 137     }
 138
 139   FOR_EACH_EDGE (e, ei, bb->preds)
 140     {
 141       sanopt_info *pred_info = (sanopt_info *) e->src->aux;
 142
 143       if (e->src == dom)
 144         continue;
 145
 146       if (pred_info->has_freeing_call_computed_p)
 147         continue;
 148
 149       gimple_stmt_iterator gsi;
 150       for (gsi = gsi_start_bb (e->src); !gsi_end_p (gsi); gsi_next (&gsi))
 151         {
 152           gimple stmt = gsi_stmt (gsi);
 153
 154           if (is_gimple_call (stmt) && !nonfreeing_call_p (stmt))
 155             {
 156               pred_info->has_freeing_call_p = true;
 157               break;
 158             }
 159         }
 160
 161       pred_info->has_freeing_call_computed_p = true;
 162       if (pred_info->has_freeing_call_p)
 163         {
 164           info->imm_dom_path_with_freeing_call_computed_p = true;
 165           info->imm_dom_path_with_freeing_call_p = true;
 166           info->being_visited_p = false;
 167           return true;
 168         }
 169     }
 170
 171   FOR_EACH_EDGE (e, ei, bb->preds)
 172     {
 173       if (e->src == dom)
 174         continue;
 175
 176       basic_block src;
 177       for (src = e->src; src != dom; )
 178         {
 179           sanopt_info *pred_info = (sanopt_info *) src->aux;
 180           if (pred_info->being_visited_p)
 181             break;
 182           basic_block imm = get_immediate_dominator (CDI_DOMINATORS, src);
 183           if (imm_dom_path_with_freeing_call (src, imm))
 184             {
 185               info->imm_dom_path_with_freeing_call_computed_p = true;
 186               info->imm_dom_path_with_freeing_call_p = true;
 187               info->being_visited_p = false;
 188               return true;
 189             }
 190           src = imm;
 191         }
 192     }
 193
 194   info->imm_dom_path_with_freeing_call_computed_p = true;
 195   info->imm_dom_path_with_freeing_call_p = false;
 196   info->being_visited_p = false;
 197   return false;
 198 }
 199
 200 /* Optimize away redundant UBSAN_NULL calls.  */
 201
 202 static bool
 203 maybe_optimize_ubsan_null_ifn (struct sanopt_ctx *ctx, gimple stmt)
 204 {
 205   gcc_assert (gimple_call_num_args (stmt) == 3);
 206   tree ptr = gimple_call_arg (stmt, 0);
 207   tree cur_align = gimple_call_arg (stmt, 2);
 208   gcc_assert (TREE_CODE (cur_align) == INTEGER_CST);
 209   bool remove = false;
 210
 211   auto_vec<gimple> &v = ctx->null_check_map.get_or_insert (ptr);
 212   if (v.is_empty ())
 213     {
 214       /* For this PTR we don't have any UBSAN_NULL stmts recorded, so there's
 215          nothing to optimize yet.  */
 216       v.safe_push (stmt);
 217       return false;
 218     }
 219
 220   /* We already have recorded a UBSAN_NULL check for this pointer. Perhaps we
 221      can drop this one.  But only if this check doesn't specify stricter
 222      alignment.  */
 223   while (!v.is_empty ())
 224     {
 225       gimple g = v.last ();
 226       /* Remove statements for BBs that have been already processed.  */
 227       sanopt_info *si = (sanopt_info *) gimple_bb (g)->aux;
 228       if (si->visited_p)
 229         {
 230           v.pop ();
 231           continue;
 232         }
 233
 234       /* At this point we shouldn't have any statements that aren't dominating
 235          the current BB.  */
 236       tree align = gimple_call_arg (g, 2);
 237       int kind = tree_to_shwi (gimple_call_arg (g, 1));
 238       /* If this is a NULL pointer check where we had segv anyway, we can
 239          remove it.  */
 240       if (integer_zerop (align)
 241           && (kind == UBSAN_LOAD_OF
 242               || kind == UBSAN_STORE_OF
 243               || kind == UBSAN_MEMBER_ACCESS))
 244         remove = true;
 245       /* Otherwise remove the check in non-recovering mode, or if the
 246          stmts have same location.  */
 247       else if (integer_zerop (align))
 248         remove = (flag_sanitize_recover & SANITIZE_NULL) == 0
 249                  || flag_sanitize_undefined_trap_on_error
 250                  || gimple_location (g) == gimple_location (stmt);
 251       else if (tree_int_cst_le (cur_align, align))
 252         remove = (flag_sanitize_recover & SANITIZE_ALIGNMENT) == 0
 253                  || flag_sanitize_undefined_trap_on_error
 254                  || gimple_location (g) == gimple_location (stmt);
 255       if (!remove && gimple_bb (g) == gimple_bb (stmt)
 256           && tree_int_cst_compare (cur_align, align) == 0)
 257         v.pop ();
 258       break;
 259     }
 260
 261   if (!remove)
 262     v.safe_push (stmt);
 263   return remove;
 264 }
 265
 266 /* Optimize away redundant ASAN_CHECK calls.  */
 267
 268 static bool
 269 maybe_optimize_asan_check_ifn (struct sanopt_ctx *ctx, gimple stmt)
 270 {
 271   gcc_assert (gimple_call_num_args (stmt) == 4);
 272   tree ptr = gimple_call_arg (stmt, 1);
 273   tree len = gimple_call_arg (stmt, 2);
 274   basic_block bb = gimple_bb (stmt);
 275   sanopt_info *info = (sanopt_info *) bb->aux;
 276
 277   if (TREE_CODE (len) != INTEGER_CST)
 278     return false;
 279   if (integer_zerop (len))
 280     return false;
 281
 282   gimple_set_uid (stmt, info->freeing_call_events);
 283
 284   auto_vec<gimple> &v = ctx->asan_check_map.get_or_insert (ptr);
 285   if (v.is_empty ())
 286     {
 287       /* For this PTR we don't have any ASAN_CHECK stmts recorded, so there's
 288          nothing to optimize yet.  */
 289       v.safe_push (stmt);
 290       return false;
 291     }
 292
 293   /* We already have recorded a ASAN_CHECK check for this pointer.  Perhaps
 294      we can drop this one.  But only if this check doesn't specify larger
 295      size.  */
 296   while (!v.is_empty ())
 297     {
 298       gimple g = v.last ();
 299       /* Remove statements for BBs that have been already processed.  */
 300       sanopt_info *si = (sanopt_info *) gimple_bb (g)->aux;
 301       if (si->visited_p)
 302         v.pop ();
 303       else
 304         break;
 305     }
 306
 307   unsigned int i;
 308   gimple g;
 309   gimple to_pop = NULL;
 310   bool remove = false;
 311   basic_block last_bb = bb;
 312   bool cleanup = false;
 313
 314   FOR_EACH_VEC_ELT_REVERSE (v, i, g)
 315     {
 316       basic_block gbb = gimple_bb (g);
 317       sanopt_info *si = (sanopt_info *) gbb->aux;
 318       if (gimple_uid (g) < si->freeing_call_events)
 319         {
 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.  */
 322           cleanup = true;
 323           continue;
 324         }
 325
 326       if (TREE_CODE (len) != INTEGER_CST)
 327         {
 328           /* If there is some stmts not followed by freeing call event
 329              for ptr already in the current bb, no need to insert anything.
 330              Non-constant len is treated just as length 1.  */
 331           if (gbb == bb)
 332             return false;
 333           break;
 334         }
 335
 336       tree glen = gimple_call_arg (g, 2);
 337       /* If we've checked only smaller length than we want to check now,
 338          we can't remove the current stmt.  If g is in the same basic block,
 339          we want to remove it though, as the current stmt is better.  */
 340       if (tree_int_cst_lt (glen, len))
 341         {
 342           if (gbb == bb)
 343             {
 344               to_pop = g;
 345               cleanup = true;
 346             }
 347           continue;
 348         }
 349
 350       while (last_bb != gbb)
 351         {
 352           /* Paths from last_bb to bb have been checked before.
 353              gbb is necessarily a dominator of last_bb, but not necessarily
 354              immediate dominator.  */
 355           if (((sanopt_info *) last_bb->aux)->freeing_call_events)
 356             break;
 357
 358           basic_block imm = get_immediate_dominator (CDI_DOMINATORS, last_bb);
 359           gcc_assert (imm);
 360           if (imm_dom_path_with_freeing_call (last_bb, imm))
 361             break;
 362
 363           last_bb = imm;
 364         }
 365       if (last_bb == gbb)
 366         remove = true;
 367       break;
 368     }
 369
 370   if (cleanup)
 371     {
 372       unsigned int j = 0, l = v.length ();
 373       for (i = 0; i < l; i++)
 374         if (v[i] != to_pop
 375             && (gimple_uid (v[i])
 376                 == ((sanopt_info *)
 377                     gimple_bb (v[i])->aux)->freeing_call_events))
 378           {
 379             if (i != j)
 380               v[j] = v[i];
 381             j++;
 382           }
 383       v.truncate (j);
 384     }
 385
 386   if (!remove)
 387     v.safe_push (stmt);
 388   return remove;
 389 }
 390
 391 /* Try to optimize away redundant UBSAN_NULL and ASAN_CHECK calls.
 392
 393    We walk blocks in the CFG via a depth first search of the dominator
 394    tree; we push unique UBSAN_NULL or ASAN_CHECK statements into a vector
 395    in the NULL_CHECK_MAP or ASAN_CHECK_MAP hash maps as we enter the
 396    blocks.  When leaving a block, we mark the block as visited; then
 397    when checking the statements in the vector, we ignore statements that
 398    are coming from already visited blocks, because these cannot dominate
 399    anything anymore.  CTX is a sanopt context.  */
 400
 401 static void
 402 sanopt_optimize_walker (basic_block bb, struct sanopt_ctx *ctx)
 403 {
 404   basic_block son;
 405   gimple_stmt_iterator gsi;
 406   sanopt_info *info = (sanopt_info *) bb->aux;
 407   bool asan_check_optimize
 408     = (flag_sanitize & SANITIZE_ADDRESS)
 409       && ((flag_sanitize & flag_sanitize_recover
 410            & SANITIZE_KERNEL_ADDRESS) == 0);
 411
 412   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
 413     {
 414       gimple stmt = gsi_stmt (gsi);
 415       bool remove = false;
 416
 417       if (!is_gimple_call (stmt))
 418         {
 419           /* Handle asm volatile or asm with "memory" clobber
 420              the same as potentionally freeing call.  */
 421           gasm *asm_stmt = dyn_cast <gasm *> (stmt);
 422           if (asm_stmt
 423               && asan_check_optimize
 424               && (gimple_asm_clobbers_memory_p (asm_stmt)
 425                   || gimple_asm_volatile_p (asm_stmt)))
 426             info->freeing_call_events++;
 427           gsi_next (&gsi);
 428           continue;
 429         }
 430
 431       if (asan_check_optimize && !nonfreeing_call_p (stmt))
 432         info->freeing_call_events++;
 433
 434       if (gimple_call_internal_p (stmt))
 435         switch (gimple_call_internal_fn (stmt))
 436           {
 437           case IFN_UBSAN_NULL:
 438             remove = maybe_optimize_ubsan_null_ifn (ctx, stmt);
 439             break;
 440           case IFN_ASAN_CHECK:
 441             if (asan_check_optimize)
 442               remove = maybe_optimize_asan_check_ifn (ctx, stmt);
 443             if (!remove)
 444               ctx->asan_num_accesses++;
 445             break;
 446           default:
 447             break;
 448           }
 449
 450       if (remove)
 451         {
 452           /* Drop this check.  */
 453           if (dump_file && (dump_flags & TDF_DETAILS))
 454             {
 455               fprintf (dump_file, "Optimizing out\n  ");
 456               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 457               fprintf (dump_file, "\n");
 458             }
 459           unlink_stmt_vdef (stmt);
 460           gsi_remove (&gsi, true);
 461         }
 462       else
 463         gsi_next (&gsi);
 464     }
 465
 466   if (asan_check_optimize)
 467     {
 468       info->has_freeing_call_p = info->freeing_call_events != 0;
 469       info->has_freeing_call_computed_p = true;
 470     }
 471
 472   for (son = first_dom_son (CDI_DOMINATORS, bb);
 473        son;
 474        son = next_dom_son (CDI_DOMINATORS, son))
 475     sanopt_optimize_walker (son, ctx);
 476
 477   /* We're leaving this BB, so mark it to that effect.  */
 478   info->visited_p = true;
 479 }
 480
 481 /* Try to remove redundant sanitizer checks in function FUN.  */
 482
 483 static int
 484 sanopt_optimize (function *fun)
 485 {
 486   struct sanopt_ctx ctx;
 487   ctx.asan_num_accesses = 0;
 488
 489   /* Set up block info for each basic block.  */
 490   alloc_aux_for_blocks (sizeof (sanopt_info));
 491
 492   /* We're going to do a dominator walk, so ensure that we have
 493      dominance information.  */
 494   calculate_dominance_info (CDI_DOMINATORS);
 495
 496   /* Recursively walk the dominator tree optimizing away
 497      redundant checks.  */
 498   sanopt_optimize_walker (ENTRY_BLOCK_PTR_FOR_FN (fun), &ctx);
 499
 500   free_aux_for_blocks ();
 501
 502   return ctx.asan_num_accesses;
 503 }
 504
 505 /* Perform optimization of sanitize functions.  */
 506
 507 namespace {
 508
 509 const pass_data pass_data_sanopt =
 510 {
 511   GIMPLE_PASS, /* type */
 512   "sanopt", /* name */
 513   OPTGROUP_NONE, /* optinfo_flags */
 514   TV_NONE, /* tv_id */
 515   ( PROP_ssa | PROP_cfg | PROP_gimple_leh ), /* properties_required */
 516   0, /* properties_provided */
 517   0, /* properties_destroyed */
 518   0, /* todo_flags_start */
 519   TODO_update_ssa, /* todo_flags_finish */
 520 };
 521
 522 class pass_sanopt : public gimple_opt_pass
 523 {
 524 public:
 525   pass_sanopt (gcc::context *ctxt)
 526     : gimple_opt_pass (pass_data_sanopt, ctxt)
 527   {}
 528
 529   /* opt_pass methods: */
 530   virtual bool gate (function *) { return flag_sanitize; }
 531   virtual unsigned int execute (function *);
 532
 533 }; // class pass_sanopt
 534
 535 unsigned int
 536 pass_sanopt::execute (function *fun)
 537 {
 538   basic_block bb;
 539   int asan_num_accesses = 0;
 540
 541   /* Try to remove redundant checks.  */
 542   if (optimize
 543       && (flag_sanitize
 544           & (SANITIZE_NULL | SANITIZE_ALIGNMENT | SANITIZE_ADDRESS)))
 545     asan_num_accesses = sanopt_optimize (fun);
 546   else if (flag_sanitize & SANITIZE_ADDRESS)
 547     {
 548       gimple_stmt_iterator gsi;
 549       FOR_EACH_BB_FN (bb, fun)
 550         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 551           {
 552             gimple stmt = gsi_stmt (gsi);
 553             if (is_gimple_call (stmt) && gimple_call_internal_p (stmt)
 554                 && gimple_call_internal_fn (stmt) == IFN_ASAN_CHECK)
 555               ++asan_num_accesses;
 556           }
 557     }
 558
 559   bool use_calls = ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD < INT_MAX
 560     && asan_num_accesses >= ASAN_INSTRUMENTATION_WITH_CALL_THRESHOLD;
 561
 562   FOR_EACH_BB_FN (bb, fun)
 563     {
 564       gimple_stmt_iterator gsi;
 565       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 566         {
 567           gimple stmt = gsi_stmt (gsi);
 568           bool no_next = false;
 569
 570           if (!is_gimple_call (stmt))
 571             {
 572               gsi_next (&gsi);
 573               continue;
 574             }
 575
 576           if (gimple_call_internal_p (stmt))
 577             {
 578               enum internal_fn ifn = gimple_call_internal_fn (stmt);
 579               switch (ifn)
 580                 {
 581                 case IFN_UBSAN_NULL:
 582                   no_next = ubsan_expand_null_ifn (&gsi);
 583                   break;
 584                 case IFN_UBSAN_BOUNDS:
 585                   no_next = ubsan_expand_bounds_ifn (&gsi);
 586                   break;
 587                 case IFN_UBSAN_OBJECT_SIZE:
 588                   no_next = ubsan_expand_objsize_ifn (&gsi);
 589                   break;
 590                 case IFN_ASAN_CHECK:
 591                   no_next = asan_expand_check_ifn (&gsi, use_calls);
 592                   break;
 593                 default:
 594                   break;
 595                 }
 596             }
 597           else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
 598             {
 599               tree callee = gimple_call_fndecl (stmt);
 600               switch (DECL_FUNCTION_CODE (callee))
 601                 {
 602                 case BUILT_IN_UNREACHABLE:
 603                   if (flag_sanitize & SANITIZE_UNREACHABLE
 604                       && !lookup_attribute ("no_sanitize_undefined",
 605                                             DECL_ATTRIBUTES (fun->decl)))
 606                     no_next = ubsan_instrument_unreachable (&gsi);
 607                   break;
 608                 default:
 609                   break;
 610                 }
 611             }
 612
 613           if (dump_file && (dump_flags & TDF_DETAILS))
 614             {
 615               fprintf (dump_file, "Expanded\n  ");
 616               print_gimple_stmt (dump_file, stmt, 0, dump_flags);
 617               fprintf (dump_file, "\n");
 618             }
 619
 620           if (!no_next)
 621             gsi_next (&gsi);
 622         }
 623     }
 624   return 0;
 625 }
 626
 627 } // anon namespace
 628
 629 gimple_opt_pass *
 630 make_pass_sanopt (gcc::context *ctxt)
 631 {
 632   return new pass_sanopt (ctxt);
 633 }