[gcc]
[official-gcc.git] / gcc / gimple-ssa-isolate-paths.c
blob7ad39b4e09bb9f69189ba3d40c270bb116725709
1 /* Detect paths through the CFG which can never be executed in a conforming
2 program and isolate them.
4 Copyright (C) 2013-2017 Free Software Foundation, Inc.
6 This file is part of GCC.
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.
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.
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/>. */
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"
42 static bool cfg_altered;
44 /* Callback for walk_stmt_load_store_ops.
46 Return TRUE if OP will dereference the tree stored in DATA, FALSE
47 otherwise.
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)
54 if ((TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
55 && operand_equal_p (TREE_OPERAND (op, 0), (tree)data, 0))
57 TREE_THIS_VOLATILE (op) = 1;
58 TREE_SIDE_EFFECTS (op) = 1;
59 update_stmt (stmt);
60 return true;
62 return false;
65 /* Insert a trap after SI and split the block after the trap. */
67 static void
68 insert_trap (gimple_stmt_iterator *si_p, tree op)
70 /* We want the NULL pointer dereference to actually occur so that
71 code that wishes to catch the signal can do so.
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.
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))))
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);
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);
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))
104 gsi_insert_after (si_p, seq, GSI_NEW_STMT);
105 if (stmt_ends_bb_p (stmt))
107 split_block (gimple_bb (stmt), stmt);
108 return;
111 else
112 gsi_insert_before (si_p, seq, GSI_NEW_STMT);
114 split_block (gimple_bb (new_stmt), new_stmt);
115 *si_p = gsi_for_stmt (stmt);
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.
122 Isolation is simple. Duplicate BB and redirect E to BB'.
124 Optimization is simple as well. Replace STMT in BB' with an
125 unconditional trap and remove all outgoing edges from BB'.
127 If RET_ZERO, do not trap, only return NULL.
129 DUPLICATE is a pre-existing duplicate, use it as BB' if it exists.
131 Return BB'. */
133 basic_block
134 isolate_path (basic_block bb, basic_block duplicate,
135 edge e, gimple *stmt, tree op, bool ret_zero)
137 gimple_stmt_iterator si, si2;
138 edge_iterator ei;
139 edge e2;
140 bool impossible = true;
142 for (si = gsi_start_bb (bb); gsi_stmt (si) != stmt; gsi_next (&si))
143 if (stmt_can_terminate_bb_p (gsi_stmt (si)))
145 impossible = false;
146 break;
148 force_edge_cold (e, impossible);
150 /* First duplicate BB if we have not done so already and remove all
151 the duplicate's outgoing edges as duplicate is going to unconditionally
152 trap. Removing the outgoing edges is both an optimization and ensures
153 we don't need to do any PHI node updates. */
154 if (!duplicate)
156 duplicate = duplicate_block (bb, NULL, NULL);
157 bb->frequency = 0;
158 bb->count = profile_count::zero ();
159 if (!ret_zero)
160 for (ei = ei_start (duplicate->succs); (e2 = ei_safe_edge (ei)); )
161 remove_edge (e2);
163 bb->frequency += EDGE_FREQUENCY (e);
164 bb->count += e->count;
166 /* Complete the isolation step by redirecting E to reach DUPLICATE. */
167 e2 = redirect_edge_and_branch (e, duplicate);
168 if (e2)
169 flush_pending_stmts (e2);
172 /* There may be more than one statement in DUPLICATE which exhibits
173 undefined behavior. Ultimately we want the first such statement in
174 DUPLCIATE so that we're able to delete as much code as possible.
176 So each time we discover undefined behavior in DUPLICATE, search for
177 the statement which triggers undefined behavior. If found, then
178 transform the statement into a trap and delete everything after the
179 statement. If not found, then this particular instance was subsumed by
180 an earlier instance of undefined behavior and there's nothing to do.
182 This is made more complicated by the fact that we have STMT, which is in
183 BB rather than in DUPLICATE. So we set up two iterators, one for each
184 block and walk forward looking for STMT in BB, advancing each iterator at
185 each step.
187 When we find STMT the second iterator should point to STMT's equivalent in
188 duplicate. If DUPLICATE ends before STMT is found in BB, then there's
189 nothing to do.
191 Ignore labels and debug statements. */
192 si = gsi_start_nondebug_after_labels_bb (bb);
193 si2 = gsi_start_nondebug_after_labels_bb (duplicate);
194 while (!gsi_end_p (si) && !gsi_end_p (si2) && gsi_stmt (si) != stmt)
196 gsi_next_nondebug (&si);
197 gsi_next_nondebug (&si2);
200 /* This would be an indicator that we never found STMT in BB, which should
201 never happen. */
202 gcc_assert (!gsi_end_p (si));
204 /* If we did not run to the end of DUPLICATE, then SI points to STMT and
205 SI2 points to the duplicate of STMT in DUPLICATE. Insert a trap
206 before SI2 and remove SI2 and all trailing statements. */
207 if (!gsi_end_p (si2))
209 if (ret_zero)
211 greturn *ret = as_a <greturn *> (gsi_stmt (si2));
212 tree zero = build_zero_cst (TREE_TYPE (gimple_return_retval (ret)));
213 gimple_return_set_retval (ret, zero);
214 update_stmt (ret);
216 else
217 insert_trap (&si2, op);
220 return duplicate;
223 /* Return TRUE if STMT is a div/mod operation using DIVISOR as the divisor.
224 FALSE otherwise. */
226 static bool
227 is_divmod_with_given_divisor (gimple *stmt, tree divisor)
229 /* Only assignments matter. */
230 if (!is_gimple_assign (stmt))
231 return false;
233 /* Check for every DIV/MOD expression. */
234 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
235 if (rhs_code == TRUNC_DIV_EXPR
236 || rhs_code == FLOOR_DIV_EXPR
237 || rhs_code == CEIL_DIV_EXPR
238 || rhs_code == EXACT_DIV_EXPR
239 || rhs_code == ROUND_DIV_EXPR
240 || rhs_code == TRUNC_MOD_EXPR
241 || rhs_code == FLOOR_MOD_EXPR
242 || rhs_code == CEIL_MOD_EXPR
243 || rhs_code == ROUND_MOD_EXPR)
245 /* Pointer equality is fine when DIVISOR is an SSA_NAME, but
246 not sufficient for constants which may have different types. */
247 if (operand_equal_p (gimple_assign_rhs2 (stmt), divisor, 0))
248 return true;
250 return false;
253 /* NAME is an SSA_NAME that we have already determined has the value 0 or NULL.
255 Return TRUE if USE_STMT uses NAME in a way where a 0 or NULL value results
256 in undefined behavior, FALSE otherwise
258 LOC is used for issuing diagnostics. This case represents potential
259 undefined behavior exposed by path splitting and that's reflected in
260 the diagnostic. */
262 bool
263 stmt_uses_name_in_undefined_way (gimple *use_stmt, tree name, location_t loc)
265 /* If we are working with a non pointer type, then see
266 if this use is a DIV/MOD operation using NAME as the
267 divisor. */
268 if (!POINTER_TYPE_P (TREE_TYPE (name)))
270 if (!flag_non_call_exceptions)
271 return is_divmod_with_given_divisor (use_stmt, name);
272 return false;
275 /* NAME is a pointer, so see if it's used in a context where it must
276 be non-NULL. */
277 bool by_dereference
278 = infer_nonnull_range_by_dereference (use_stmt, name);
280 if (by_dereference
281 || infer_nonnull_range_by_attribute (use_stmt, name))
284 if (by_dereference)
286 warning_at (loc, OPT_Wnull_dereference,
287 "potential null pointer dereference");
288 if (!flag_isolate_erroneous_paths_dereference)
289 return false;
291 else
293 if (!flag_isolate_erroneous_paths_attribute)
294 return false;
296 return true;
298 return false;
301 /* Return TRUE if USE_STMT uses 0 or NULL in a context which results in
302 undefined behavior, FALSE otherwise.
304 These cases are explicit in the IL. */
306 bool
307 stmt_uses_0_or_null_in_undefined_way (gimple *stmt)
309 if (!flag_non_call_exceptions
310 && is_divmod_with_given_divisor (stmt, integer_zero_node))
311 return true;
313 /* By passing null_pointer_node, we can use the
314 infer_nonnull_range functions to detect explicit NULL
315 pointer dereferences and other uses where a non-NULL
316 value is required. */
318 bool by_dereference
319 = infer_nonnull_range_by_dereference (stmt, null_pointer_node);
320 if (by_dereference
321 || infer_nonnull_range_by_attribute (stmt, null_pointer_node))
323 if (by_dereference)
325 location_t loc = gimple_location (stmt);
326 warning_at (loc, OPT_Wnull_dereference,
327 "null pointer dereference");
328 if (!flag_isolate_erroneous_paths_dereference)
329 return false;
331 else
333 if (!flag_isolate_erroneous_paths_attribute)
334 return false;
336 return true;
338 return false;
341 /* Look for PHI nodes which feed statements in the same block where
342 the value of the PHI node implies the statement is erroneous.
344 For example, a NULL PHI arg value which then feeds a pointer
345 dereference.
347 When found isolate and optimize the path associated with the PHI
348 argument feeding the erroneous statement. */
349 static void
350 find_implicit_erroneous_behavior (void)
352 basic_block bb;
354 FOR_EACH_BB_FN (bb, cfun)
356 gphi_iterator si;
358 /* Out of an abundance of caution, do not isolate paths to a
359 block where the block has any abnormal outgoing edges.
361 We might be able to relax this in the future. We have to detect
362 when we have to split the block with the NULL dereference and
363 the trap we insert. We have to preserve abnormal edges out
364 of the isolated block which in turn means updating PHIs at
365 the targets of those abnormal outgoing edges. */
366 if (has_abnormal_or_eh_outgoing_edge_p (bb))
367 continue;
370 /* If BB has an edge to itself, then duplication of BB below
371 could result in reallocation of BB's PHI nodes. If that happens
372 then the loop below over the PHIs would use the old PHI and
373 thus invalid information. We don't have a good way to know
374 if a PHI has been reallocated, so just avoid isolation in
375 this case. */
376 if (find_edge (bb, bb))
377 continue;
379 /* First look for a PHI which sets a pointer to NULL and which
380 is then dereferenced within BB. This is somewhat overly
381 conservative, but probably catches most of the interesting
382 cases. */
383 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
385 gphi *phi = si.phi ();
386 tree lhs = gimple_phi_result (phi);
388 /* PHI produces a pointer result. See if any of the PHI's
389 arguments are NULL.
391 When we remove an edge, we want to reprocess the current
392 index, hence the ugly way we update I for each iteration. */
393 basic_block duplicate = NULL;
394 for (unsigned i = 0, next_i = 0;
395 i < gimple_phi_num_args (phi);
396 i = next_i)
398 tree op = gimple_phi_arg_def (phi, i);
399 edge e = gimple_phi_arg_edge (phi, i);
400 imm_use_iterator iter;
401 gimple *use_stmt;
403 next_i = i + 1;
405 if (TREE_CODE (op) == ADDR_EXPR)
407 tree valbase = get_base_address (TREE_OPERAND (op, 0));
408 if ((VAR_P (valbase) && !is_global_var (valbase))
409 || TREE_CODE (valbase) == PARM_DECL)
411 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
413 greturn *return_stmt
414 = dyn_cast <greturn *> (use_stmt);
415 if (!return_stmt)
416 continue;
418 if (gimple_return_retval (return_stmt) != lhs)
419 continue;
421 if (warning_at (gimple_location (use_stmt),
422 OPT_Wreturn_local_addr,
423 "function may return address "
424 "of local variable"))
425 inform (DECL_SOURCE_LOCATION(valbase),
426 "declared here");
428 if (gimple_bb (use_stmt) == bb)
430 duplicate = isolate_path (bb, duplicate, e,
431 use_stmt, lhs, true);
433 /* When we remove an incoming edge, we need to
434 reprocess the Ith element. */
435 next_i = i;
436 cfg_altered = true;
442 if (!integer_zerop (op))
443 continue;
445 /* We've got a NULL PHI argument. Now see if the
446 PHI's result is dereferenced within BB. */
447 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
449 /* We only care about uses in BB. Catching cases in
450 in other blocks would require more complex path
451 isolation code. */
452 if (gimple_bb (use_stmt) != bb)
453 continue;
455 location_t loc = gimple_location (use_stmt)
456 ? gimple_location (use_stmt)
457 : gimple_phi_arg_location (phi, i);
459 if (stmt_uses_name_in_undefined_way (use_stmt, lhs, loc))
461 duplicate = isolate_path (bb, duplicate, e,
462 use_stmt, lhs, false);
464 /* When we remove an incoming edge, we need to
465 reprocess the Ith element. */
466 next_i = i;
467 cfg_altered = true;
475 /* Look for statements which exhibit erroneous behavior. For example
476 a NULL pointer dereference.
478 When found, optimize the block containing the erroneous behavior. */
479 static void
480 find_explicit_erroneous_behavior (void)
482 basic_block bb;
484 FOR_EACH_BB_FN (bb, cfun)
486 gimple_stmt_iterator si;
488 /* Out of an abundance of caution, do not isolate paths to a
489 block where the block has any abnormal outgoing edges.
491 We might be able to relax this in the future. We have to detect
492 when we have to split the block with the NULL dereference and
493 the trap we insert. We have to preserve abnormal edges out
494 of the isolated block which in turn means updating PHIs at
495 the targets of those abnormal outgoing edges. */
496 if (has_abnormal_or_eh_outgoing_edge_p (bb))
497 continue;
499 /* Now look at the statements in the block and see if any of
500 them explicitly dereference a NULL pointer. This happens
501 because of jump threading and constant propagation. */
502 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
504 gimple *stmt = gsi_stmt (si);
506 if (stmt_uses_0_or_null_in_undefined_way (stmt))
508 insert_trap (&si, null_pointer_node);
509 bb = gimple_bb (gsi_stmt (si));
511 /* Ignore any more operands on this statement and
512 continue the statement iterator (which should
513 terminate its loop immediately. */
514 cfg_altered = true;
515 break;
518 /* Detect returning the address of a local variable. This only
519 becomes undefined behavior if the result is used, so we do not
520 insert a trap and only return NULL instead. */
521 if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
523 tree val = gimple_return_retval (return_stmt);
524 if (val && TREE_CODE (val) == ADDR_EXPR)
526 tree valbase = get_base_address (TREE_OPERAND (val, 0));
527 if ((VAR_P (valbase) && !is_global_var (valbase))
528 || TREE_CODE (valbase) == PARM_DECL)
530 /* We only need it for this particular case. */
531 calculate_dominance_info (CDI_POST_DOMINATORS);
532 const char* msg;
533 bool always_executed = dominated_by_p
534 (CDI_POST_DOMINATORS,
535 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb);
536 if (always_executed)
537 msg = N_("function returns address of local variable");
538 else
539 msg = N_("function may return address of "
540 "local variable");
542 if (warning_at (gimple_location (stmt),
543 OPT_Wreturn_local_addr, msg))
544 inform (DECL_SOURCE_LOCATION(valbase), "declared here");
545 tree zero = build_zero_cst (TREE_TYPE (val));
546 gimple_return_set_retval (return_stmt, zero);
547 update_stmt (stmt);
555 /* Search the function for statements which, if executed, would cause
556 the program to fault such as a dereference of a NULL pointer.
558 Such a program can't be valid if such a statement was to execute
559 according to ISO standards.
561 We detect explicit NULL pointer dereferences as well as those implied
562 by a PHI argument having a NULL value which unconditionally flows into
563 a dereference in the same block as the PHI.
565 In the former case we replace the offending statement with an
566 unconditional trap and eliminate the outgoing edges from the statement's
567 basic block. This may expose secondary optimization opportunities.
569 In the latter case, we isolate the path(s) with the NULL PHI
570 feeding the dereference. We can then replace the offending statement
571 and eliminate the outgoing edges in the duplicate. Again, this may
572 expose secondary optimization opportunities.
574 A warning for both cases may be advisable as well.
576 Other statically detectable violations of the ISO standard could be
577 handled in a similar way, such as out-of-bounds array indexing. */
579 static unsigned int
580 gimple_ssa_isolate_erroneous_paths (void)
582 initialize_original_copy_tables ();
584 /* Search all the blocks for edges which, if traversed, will
585 result in undefined behavior. */
586 cfg_altered = false;
588 /* First handle cases where traversal of a particular edge
589 triggers undefined behavior. These cases require creating
590 duplicate blocks and thus new SSA_NAMEs.
592 We want that process complete prior to the phase where we start
593 removing edges from the CFG. Edge removal may ultimately result in
594 removal of PHI nodes and thus releasing SSA_NAMEs back to the
595 name manager.
597 If the two processes run in parallel we could release an SSA_NAME
598 back to the manager but we could still have dangling references
599 to the released SSA_NAME in unreachable blocks.
600 that any released names not have dangling references in the IL. */
601 find_implicit_erroneous_behavior ();
602 find_explicit_erroneous_behavior ();
604 free_original_copy_tables ();
606 /* We scramble the CFG and loop structures a bit, clean up
607 appropriately. We really should incrementally update the
608 loop structures, in theory it shouldn't be that hard. */
609 free_dominance_info (CDI_POST_DOMINATORS);
610 if (cfg_altered)
612 free_dominance_info (CDI_DOMINATORS);
613 loops_state_set (LOOPS_NEED_FIXUP);
614 return TODO_cleanup_cfg | TODO_update_ssa;
616 return 0;
619 namespace {
620 const pass_data pass_data_isolate_erroneous_paths =
622 GIMPLE_PASS, /* type */
623 "isolate-paths", /* name */
624 OPTGROUP_NONE, /* optinfo_flags */
625 TV_ISOLATE_ERRONEOUS_PATHS, /* tv_id */
626 ( PROP_cfg | PROP_ssa ), /* properties_required */
627 0, /* properties_provided */
628 0, /* properties_destroyed */
629 0, /* todo_flags_start */
630 0, /* todo_flags_finish */
633 class pass_isolate_erroneous_paths : public gimple_opt_pass
635 public:
636 pass_isolate_erroneous_paths (gcc::context *ctxt)
637 : gimple_opt_pass (pass_data_isolate_erroneous_paths, ctxt)
640 /* opt_pass methods: */
641 opt_pass * clone () { return new pass_isolate_erroneous_paths (m_ctxt); }
642 virtual bool gate (function *)
644 /* If we do not have a suitable builtin function for the trap statement,
645 then do not perform the optimization. */
646 return (flag_isolate_erroneous_paths_dereference != 0
647 || flag_isolate_erroneous_paths_attribute != 0
648 || warn_null_dereference);
651 virtual unsigned int execute (function *)
653 return gimple_ssa_isolate_erroneous_paths ();
656 }; // class pass_isolate_erroneous_paths
659 gimple_opt_pass *
660 make_pass_isolate_erroneous_paths (gcc::context *ctxt)
662 return new pass_isolate_erroneous_paths (ctxt);