1 /* Detect paths through the CFG which can never be executed in a conforming 2 program and isolate them. 3 4 Copyright (C) 2013-2018 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "backend.h" 26 #include "tree.h" 27 #include "gimple.h" 28 #include "cfghooks.h" 29 #include "tree-pass.h" 30 #include "ssa.h" 31 #include "diagnostic-core.h" 32 #include "fold-const.h" 33 #include "gimple-iterator.h" 34 #include "gimple-walk.h" 35 #include "tree-ssa.h" 36 #include "cfgloop.h" 37 #include "tree-cfg.h" 38 #include "cfganal.h" 39 #include "intl.h" 40 41 42 static bool cfg_altered; 43 44 /* Callback for walk_stmt_load_store_ops. 45 46 Return TRUE if OP will dereference the tree stored in DATA, FALSE 47 otherwise. 48 49 This routine only makes a superficial check for a dereference. Thus, 50 it must only be used if it is safe to return a false negative. */ 51 static bool 52 check_loadstore (gimple *stmt, tree op, tree, void *data) 53 { 54 if ((TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) 55 && operand_equal_p (TREE_OPERAND (op, 0), (tree)data, 0)) 56 { 57 TREE_THIS_VOLATILE (op) = 1; 58 TREE_SIDE_EFFECTS (op) = 1; 59 update_stmt (stmt); 60 return true; 61 } 62 return false; 63 } 64 65 /* Insert a trap after SI and split the block after the trap. */ 66 67 static void 68 insert_trap (gimple_stmt_iterator *si_p, tree op) 69 { 70 /* We want the NULL pointer dereference to actually occur so that 71 code that wishes to catch the signal can do so. 72 73 If the dereference is a load, then there's nothing to do as the 74 LHS will be a throw-away SSA_NAME and the RHS is the NULL dereference. 75 76 If the dereference is a store and we can easily transform the RHS, 77 then simplify the RHS to enable more DCE. Note that we require the 78 statement to be a GIMPLE_ASSIGN which filters out calls on the RHS. */ 79 gimple *stmt = gsi_stmt (*si_p); 80 if (walk_stmt_load_store_ops (stmt, (void *)op, NULL, check_loadstore) 81 && is_gimple_assign (stmt) 82 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))) 83 { 84 /* We just need to turn the RHS into zero converted to the proper 85 type. */ 86 tree type = TREE_TYPE (gimple_assign_lhs (stmt)); 87 gimple_assign_set_rhs_code (stmt, INTEGER_CST); 88 gimple_assign_set_rhs1 (stmt, fold_convert (type, integer_zero_node)); 89 update_stmt (stmt); 90 } 91 92 gcall *new_stmt 93 = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0); 94 gimple_seq seq = NULL; 95 gimple_seq_add_stmt (&seq, new_stmt); 96 97 /* If we had a NULL pointer dereference, then we want to insert the 98 __builtin_trap after the statement, for the other cases we want 99 to insert before the statement. */ 100 if (walk_stmt_load_store_ops (stmt, (void *)op, 101 check_loadstore, 102 check_loadstore)) 103 { 104 gsi_insert_after (si_p, seq, GSI_NEW_STMT); 105 if (stmt_ends_bb_p (stmt)) 106 { 107 split_block (gimple_bb (stmt), stmt); 108 return; 109 } 110 } 111 else 112 gsi_insert_before (si_p, seq, GSI_NEW_STMT); 113 114 split_block (gimple_bb (new_stmt), new_stmt); 115 *si_p = gsi_for_stmt (stmt); 116 } 117 118 /* BB when reached via incoming edge E will exhibit undefined behavior 119 at STMT. Isolate and optimize the path which exhibits undefined 120 behavior. 121 122 Isolation is simple. Duplicate BB and redirect E to BB'. 123 124 Optimization is simple as well. Replace STMT in BB' with an 125 unconditional trap and remove all outgoing edges from BB'. 126 127 If RET_ZERO, do not trap, only return NULL. 128 129 DUPLICATE is a pre-existing duplicate, use it as BB' if it exists. 130 131 Return BB'. */ 132 133 basic_block 134 isolate_path (basic_block bb, basic_block duplicate, 135 edge e, gimple *stmt, tree op, bool ret_zero) 136 { 137 gimple_stmt_iterator si, si2; 138 edge_iterator ei; 139 edge e2; 140 bool impossible = true; 141 profile_count count = e->count (); 142 143 for (si = gsi_start_bb (bb); gsi_stmt (si) != stmt; gsi_next (&si)) 144 if (stmt_can_terminate_bb_p (gsi_stmt (si))) 145 { 146 impossible = false; 147 break; 148 } 149 force_edge_cold (e, impossible); 150 151 /* First duplicate BB if we have not done so already and remove all 152 the duplicate's outgoing edges as duplicate is going to unconditionally 153 trap. Removing the outgoing edges is both an optimization and ensures 154 we don't need to do any PHI node updates. */ 155 if (!duplicate) 156 { 157 duplicate = duplicate_block (bb, NULL, NULL); 158 duplicate->count = profile_count::zero (); 159 if (!ret_zero) 160 for (ei = ei_start (duplicate->succs); (e2 = ei_safe_edge (ei)); ) 161 remove_edge (e2); 162 } 163 bb->count -= count; 164 165 /* Complete the isolation step by redirecting E to reach DUPLICATE. */ 166 e2 = redirect_edge_and_branch (e, duplicate); 167 if (e2) 168 { 169 flush_pending_stmts (e2); 170 171 /* Update profile only when redirection is really processed. */ 172 bb->count += e->count (); 173 } 174 175 /* There may be more than one statement in DUPLICATE which exhibits 176 undefined behavior. Ultimately we want the first such statement in 177 DUPLCIATE so that we're able to delete as much code as possible. 178 179 So each time we discover undefined behavior in DUPLICATE, search for 180 the statement which triggers undefined behavior. If found, then 181 transform the statement into a trap and delete everything after the 182 statement. If not found, then this particular instance was subsumed by 183 an earlier instance of undefined behavior and there's nothing to do. 184 185 This is made more complicated by the fact that we have STMT, which is in 186 BB rather than in DUPLICATE. So we set up two iterators, one for each 187 block and walk forward looking for STMT in BB, advancing each iterator at 188 each step. 189 190 When we find STMT the second iterator should point to STMT's equivalent in 191 duplicate. If DUPLICATE ends before STMT is found in BB, then there's 192 nothing to do. 193 194 Ignore labels and debug statements. */ 195 si = gsi_start_nondebug_after_labels_bb (bb); 196 si2 = gsi_start_nondebug_after_labels_bb (duplicate); 197 while (!gsi_end_p (si) && !gsi_end_p (si2) && gsi_stmt (si) != stmt) 198 { 199 gsi_next_nondebug (&si); 200 gsi_next_nondebug (&si2); 201 } 202 203 /* This would be an indicator that we never found STMT in BB, which should 204 never happen. */ 205 gcc_assert (!gsi_end_p (si)); 206 207 /* If we did not run to the end of DUPLICATE, then SI points to STMT and 208 SI2 points to the duplicate of STMT in DUPLICATE. Insert a trap 209 before SI2 and remove SI2 and all trailing statements. */ 210 if (!gsi_end_p (si2)) 211 { 212 if (ret_zero) 213 { 214 greturn *ret = as_a <greturn *> (gsi_stmt (si2)); 215 tree zero = build_zero_cst (TREE_TYPE (gimple_return_retval (ret))); 216 gimple_return_set_retval (ret, zero); 217 update_stmt (ret); 218 } 219 else 220 insert_trap (&si2, op); 221 } 222 223 return duplicate; 224 } 225 226 /* Return TRUE if STMT is a div/mod operation using DIVISOR as the divisor. 227 FALSE otherwise. */ 228 229 static bool 230 is_divmod_with_given_divisor (gimple *stmt, tree divisor) 231 { 232 /* Only assignments matter. */ 233 if (!is_gimple_assign (stmt)) 234 return false; 235 236 /* Check for every DIV/MOD expression. */ 237 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 238 if (rhs_code == TRUNC_DIV_EXPR 239 || rhs_code == FLOOR_DIV_EXPR 240 || rhs_code == CEIL_DIV_EXPR 241 || rhs_code == EXACT_DIV_EXPR 242 || rhs_code == ROUND_DIV_EXPR 243 || rhs_code == TRUNC_MOD_EXPR 244 || rhs_code == FLOOR_MOD_EXPR 245 || rhs_code == CEIL_MOD_EXPR 246 || rhs_code == ROUND_MOD_EXPR) 247 { 248 /* Pointer equality is fine when DIVISOR is an SSA_NAME, but 249 not sufficient for constants which may have different types. */ 250 if (operand_equal_p (gimple_assign_rhs2 (stmt), divisor, 0)) 251 return true; 252 } 253 return false; 254 } 255 256 /* NAME is an SSA_NAME that we have already determined has the value 0 or NULL. 257 258 Return TRUE if USE_STMT uses NAME in a way where a 0 or NULL value results 259 in undefined behavior, FALSE otherwise 260 261 LOC is used for issuing diagnostics. This case represents potential 262 undefined behavior exposed by path splitting and that's reflected in 263 the diagnostic. */ 264 265 bool 266 stmt_uses_name_in_undefined_way (gimple *use_stmt, tree name, location_t loc) 267 { 268 /* If we are working with a non pointer type, then see 269 if this use is a DIV/MOD operation using NAME as the 270 divisor. */ 271 if (!POINTER_TYPE_P (TREE_TYPE (name))) 272 { 273 if (!cfun->can_throw_non_call_exceptions) 274 return is_divmod_with_given_divisor (use_stmt, name); 275 return false; 276 } 277 278 /* NAME is a pointer, so see if it's used in a context where it must 279 be non-NULL. */ 280 bool by_dereference 281 = infer_nonnull_range_by_dereference (use_stmt, name); 282 283 if (by_dereference 284 || infer_nonnull_range_by_attribute (use_stmt, name)) 285 { 286 287 if (by_dereference) 288 { 289 warning_at (loc, OPT_Wnull_dereference, 290 "potential null pointer dereference"); 291 if (!flag_isolate_erroneous_paths_dereference) 292 return false; 293 } 294 else 295 { 296 if (!flag_isolate_erroneous_paths_attribute) 297 return false; 298 } 299 return true; 300 } 301 return false; 302 } 303 304 /* Return TRUE if USE_STMT uses 0 or NULL in a context which results in 305 undefined behavior, FALSE otherwise. 306 307 These cases are explicit in the IL. */ 308 309 bool 310 stmt_uses_0_or_null_in_undefined_way (gimple *stmt) 311 { 312 if (!cfun->can_throw_non_call_exceptions 313 && is_divmod_with_given_divisor (stmt, integer_zero_node)) 314 return true; 315 316 /* By passing null_pointer_node, we can use the 317 infer_nonnull_range functions to detect explicit NULL 318 pointer dereferences and other uses where a non-NULL 319 value is required. */ 320 321 bool by_dereference 322 = infer_nonnull_range_by_dereference (stmt, null_pointer_node); 323 if (by_dereference 324 || infer_nonnull_range_by_attribute (stmt, null_pointer_node)) 325 { 326 if (by_dereference) 327 { 328 location_t loc = gimple_location (stmt); 329 warning_at (loc, OPT_Wnull_dereference, 330 "null pointer dereference"); 331 if (!flag_isolate_erroneous_paths_dereference) 332 return false; 333 } 334 else 335 { 336 if (!flag_isolate_erroneous_paths_attribute) 337 return false; 338 } 339 return true; 340 } 341 return false; 342 } 343 344 /* Look for PHI nodes which feed statements in the same block where 345 the value of the PHI node implies the statement is erroneous. 346 347 For example, a NULL PHI arg value which then feeds a pointer 348 dereference. 349 350 When found isolate and optimize the path associated with the PHI 351 argument feeding the erroneous statement. */ 352 static void 353 find_implicit_erroneous_behavior (void) 354 { 355 basic_block bb; 356 357 FOR_EACH_BB_FN (bb, cfun) 358 { 359 gphi_iterator si; 360 361 /* Out of an abundance of caution, do not isolate paths to a 362 block where the block has any abnormal outgoing edges. 363 364 We might be able to relax this in the future. We have to detect 365 when we have to split the block with the NULL dereference and 366 the trap we insert. We have to preserve abnormal edges out 367 of the isolated block which in turn means updating PHIs at 368 the targets of those abnormal outgoing edges. */ 369 if (has_abnormal_or_eh_outgoing_edge_p (bb)) 370 continue; 371 372 373 /* If BB has an edge to itself, then duplication of BB below 374 could result in reallocation of BB's PHI nodes. If that happens 375 then the loop below over the PHIs would use the old PHI and 376 thus invalid information. We don't have a good way to know 377 if a PHI has been reallocated, so just avoid isolation in 378 this case. */ 379 if (find_edge (bb, bb)) 380 continue; 381 382 /* First look for a PHI which sets a pointer to NULL and which 383 is then dereferenced within BB. This is somewhat overly 384 conservative, but probably catches most of the interesting 385 cases. */ 386 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) 387 { 388 gphi *phi = si.phi (); 389 tree lhs = gimple_phi_result (phi); 390 391 /* PHI produces a pointer result. See if any of the PHI's 392 arguments are NULL. 393 394 When we remove an edge, we want to reprocess the current 395 index, hence the ugly way we update I for each iteration. */ 396 basic_block duplicate = NULL; 397 for (unsigned i = 0, next_i = 0; 398 i < gimple_phi_num_args (phi); 399 i = next_i) 400 { 401 tree op = gimple_phi_arg_def (phi, i); 402 edge e = gimple_phi_arg_edge (phi, i); 403 imm_use_iterator iter; 404 gimple *use_stmt; 405 406 next_i = i + 1; 407 408 if (TREE_CODE (op) == ADDR_EXPR) 409 { 410 tree valbase = get_base_address (TREE_OPERAND (op, 0)); 411 if ((VAR_P (valbase) && !is_global_var (valbase)) 412 || TREE_CODE (valbase) == PARM_DECL) 413 { 414 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 415 { 416 greturn *return_stmt 417 = dyn_cast <greturn *> (use_stmt); 418 if (!return_stmt) 419 continue; 420 421 if (gimple_return_retval (return_stmt) != lhs) 422 continue; 423 424 if (warning_at (gimple_location (use_stmt), 425 OPT_Wreturn_local_addr, 426 "function may return address " 427 "of local variable")) 428 inform (DECL_SOURCE_LOCATION(valbase), 429 "declared here"); 430 431 if (gimple_bb (use_stmt) == bb) 432 { 433 duplicate = isolate_path (bb, duplicate, e, 434 use_stmt, lhs, true); 435 436 /* When we remove an incoming edge, we need to 437 reprocess the Ith element. */ 438 next_i = i; 439 cfg_altered = true; 440 } 441 } 442 } 443 } 444 445 if (!integer_zerop (op)) 446 continue; 447 448 location_t phi_arg_loc = gimple_phi_arg_location (phi, i); 449 450 /* We've got a NULL PHI argument. Now see if the 451 PHI's result is dereferenced within BB. */ 452 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 453 { 454 /* We only care about uses in BB. Catching cases in 455 in other blocks would require more complex path 456 isolation code. */ 457 if (gimple_bb (use_stmt) != bb) 458 continue; 459 460 location_t loc = gimple_location (use_stmt) 461 ? gimple_location (use_stmt) 462 : phi_arg_loc; 463 464 if (stmt_uses_name_in_undefined_way (use_stmt, lhs, loc)) 465 { 466 duplicate = isolate_path (bb, duplicate, e, 467 use_stmt, lhs, false); 468 469 /* When we remove an incoming edge, we need to 470 reprocess the Ith element. */ 471 next_i = i; 472 cfg_altered = true; 473 } 474 } 475 } 476 } 477 } 478 } 479 480 /* Look for statements which exhibit erroneous behavior. For example 481 a NULL pointer dereference. 482 483 When found, optimize the block containing the erroneous behavior. */ 484 static void 485 find_explicit_erroneous_behavior (void) 486 { 487 basic_block bb; 488 489 FOR_EACH_BB_FN (bb, cfun) 490 { 491 gimple_stmt_iterator si; 492 493 /* Out of an abundance of caution, do not isolate paths to a 494 block where the block has any abnormal outgoing edges. 495 496 We might be able to relax this in the future. We have to detect 497 when we have to split the block with the NULL dereference and 498 the trap we insert. We have to preserve abnormal edges out 499 of the isolated block which in turn means updating PHIs at 500 the targets of those abnormal outgoing edges. */ 501 if (has_abnormal_or_eh_outgoing_edge_p (bb)) 502 continue; 503 504 /* Now look at the statements in the block and see if any of 505 them explicitly dereference a NULL pointer. This happens 506 because of jump threading and constant propagation. */ 507 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 508 { 509 gimple *stmt = gsi_stmt (si); 510 511 if (stmt_uses_0_or_null_in_undefined_way (stmt)) 512 { 513 insert_trap (&si, null_pointer_node); 514 bb = gimple_bb (gsi_stmt (si)); 515 516 /* Ignore any more operands on this statement and 517 continue the statement iterator (which should 518 terminate its loop immediately. */ 519 cfg_altered = true; 520 break; 521 } 522 523 /* Detect returning the address of a local variable. This only 524 becomes undefined behavior if the result is used, so we do not 525 insert a trap and only return NULL instead. */ 526 if (greturn *return_stmt = dyn_cast <greturn *> (stmt)) 527 { 528 tree val = gimple_return_retval (return_stmt); 529 if (val && TREE_CODE (val) == ADDR_EXPR) 530 { 531 tree valbase = get_base_address (TREE_OPERAND (val, 0)); 532 if ((VAR_P (valbase) && !is_global_var (valbase)) 533 || TREE_CODE (valbase) == PARM_DECL) 534 { 535 /* We only need it for this particular case. */ 536 calculate_dominance_info (CDI_POST_DOMINATORS); 537 const char* msg; 538 bool always_executed = dominated_by_p 539 (CDI_POST_DOMINATORS, 540 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb); 541 if (always_executed) 542 msg = N_("function returns address of local variable"); 543 else 544 msg = N_("function may return address of " 545 "local variable"); 546 547 if (warning_at (gimple_location (stmt), 548 OPT_Wreturn_local_addr, msg)) 549 inform (DECL_SOURCE_LOCATION(valbase), "declared here"); 550 tree zero = build_zero_cst (TREE_TYPE (val)); 551 gimple_return_set_retval (return_stmt, zero); 552 update_stmt (stmt); 553 } 554 } 555 } 556 } 557 } 558 } 559 560 /* Search the function for statements which, if executed, would cause 561 the program to fault such as a dereference of a NULL pointer. 562 563 Such a program can't be valid if such a statement was to execute 564 according to ISO standards. 565 566 We detect explicit NULL pointer dereferences as well as those implied 567 by a PHI argument having a NULL value which unconditionally flows into 568 a dereference in the same block as the PHI. 569 570 In the former case we replace the offending statement with an 571 unconditional trap and eliminate the outgoing edges from the statement's 572 basic block. This may expose secondary optimization opportunities. 573 574 In the latter case, we isolate the path(s) with the NULL PHI 575 feeding the dereference. We can then replace the offending statement 576 and eliminate the outgoing edges in the duplicate. Again, this may 577 expose secondary optimization opportunities. 578 579 A warning for both cases may be advisable as well. 580 581 Other statically detectable violations of the ISO standard could be 582 handled in a similar way, such as out-of-bounds array indexing. */ 583 584 static unsigned int 585 gimple_ssa_isolate_erroneous_paths (void) 586 { 587 initialize_original_copy_tables (); 588 589 /* Search all the blocks for edges which, if traversed, will 590 result in undefined behavior. */ 591 cfg_altered = false; 592 593 /* First handle cases where traversal of a particular edge 594 triggers undefined behavior. These cases require creating 595 duplicate blocks and thus new SSA_NAMEs. 596 597 We want that process complete prior to the phase where we start 598 removing edges from the CFG. Edge removal may ultimately result in 599 removal of PHI nodes and thus releasing SSA_NAMEs back to the 600 name manager. 601 602 If the two processes run in parallel we could release an SSA_NAME 603 back to the manager but we could still have dangling references 604 to the released SSA_NAME in unreachable blocks. 605 that any released names not have dangling references in the IL. */ 606 find_implicit_erroneous_behavior (); 607 find_explicit_erroneous_behavior (); 608 609 free_original_copy_tables (); 610 611 /* We scramble the CFG and loop structures a bit, clean up 612 appropriately. We really should incrementally update the 613 loop structures, in theory it shouldn't be that hard. */ 614 free_dominance_info (CDI_POST_DOMINATORS); 615 if (cfg_altered) 616 { 617 free_dominance_info (CDI_DOMINATORS); 618 loops_state_set (LOOPS_NEED_FIXUP); 619 return TODO_cleanup_cfg | TODO_update_ssa; 620 } 621 return 0; 622 } 623 624 namespace { 625 const pass_data pass_data_isolate_erroneous_paths = 626 { 627 GIMPLE_PASS, /* type */ 628 "isolate-paths", /* name */ 629 OPTGROUP_NONE, /* optinfo_flags */ 630 TV_ISOLATE_ERRONEOUS_PATHS, /* tv_id */ 631 ( PROP_cfg | PROP_ssa ), /* properties_required */ 632 0, /* properties_provided */ 633 0, /* properties_destroyed */ 634 0, /* todo_flags_start */ 635 0, /* todo_flags_finish */ 636 }; 637 638 class pass_isolate_erroneous_paths : public gimple_opt_pass 639 { 640 public: 641 pass_isolate_erroneous_paths (gcc::context *ctxt) 642 : gimple_opt_pass (pass_data_isolate_erroneous_paths, ctxt) 643 {} 644 645 /* opt_pass methods: */ 646 opt_pass * clone () { return new pass_isolate_erroneous_paths (m_ctxt); } 647 virtual bool gate (function *) 648 { 649 /* If we do not have a suitable builtin function for the trap statement, 650 then do not perform the optimization. */ 651 return (flag_isolate_erroneous_paths_dereference != 0 652 || flag_isolate_erroneous_paths_attribute != 0 653 || warn_null_dereference); 654 } 655 656 virtual unsigned int execute (function *) 657 { 658 return gimple_ssa_isolate_erroneous_paths (); 659 } 660 661 }; // class pass_isolate_erroneous_paths 662 } 663 664 gimple_opt_pass * 665 make_pass_isolate_erroneous_paths (gcc::context *ctxt) 666 { 667 return new pass_isolate_erroneous_paths (ctxt); 668 } 669