]>
Commit | Line | Data |
---|---|---|
8fdc414d JL |
1 | /* Detect paths through the CFG which can never be executed in a conforming |
2 | program and isolate them. | |
3 | ||
4 | Copyright (C) 2013 | |
5 | Free Software Foundation, Inc. | |
6 | ||
7 | This file is part of GCC. | |
8 | ||
9 | GCC is free software; you can redistribute it and/or modify | |
10 | it under the terms of the GNU General Public License as published by | |
11 | the Free Software Foundation; either version 3, or (at your option) | |
12 | any later version. | |
13 | ||
14 | GCC is distributed in the hope that it will be useful, | |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | GNU General Public License for more details. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
20 | along with GCC; see the file COPYING3. If not see | |
21 | <http://www.gnu.org/licenses/>. */ | |
22 | ||
23 | #include "config.h" | |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "tree.h" | |
27 | #include "flags.h" | |
28 | #include "basic-block.h" | |
2fb9a547 AM |
29 | #include "tree-ssa-alias.h" |
30 | #include "internal-fn.h" | |
31 | #include "gimple-expr.h" | |
32 | #include "is-a.h" | |
8fdc414d | 33 | #include "gimple.h" |
5be5c238 AM |
34 | #include "gimple-iterator.h" |
35 | #include "gimple-walk.h" | |
8fdc414d | 36 | #include "tree-ssa.h" |
d8a2d370 | 37 | #include "stringpool.h" |
8fdc414d JL |
38 | #include "tree-ssanames.h" |
39 | #include "gimple-ssa.h" | |
40 | #include "tree-ssa-operands.h" | |
41 | #include "tree-phinodes.h" | |
42 | #include "ssa-iterators.h" | |
43 | #include "cfgloop.h" | |
44 | #include "tree-pass.h" | |
5e94175f | 45 | #include "tree-cfg.h" |
8fdc414d JL |
46 | |
47 | ||
48 | static bool cfg_altered; | |
49 | ||
6ab7a3d7 | 50 | /* Callback for walk_stmt_load_store_ops. |
ae93744d | 51 | |
6ab7a3d7 JL |
52 | Return TRUE if OP will dereference the tree stored in DATA, FALSE |
53 | otherwise. | |
54 | ||
55 | This routine only makes a superficial check for a dereference. Thus, | |
56 | it must only be used if it is safe to return a false negative. */ | |
57 | static bool | |
58 | check_loadstore (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data) | |
59 | { | |
60 | if ((TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF) | |
61 | && operand_equal_p (TREE_OPERAND (op, 0), (tree)data, 0)) | |
115d1851 JL |
62 | { |
63 | TREE_THIS_VOLATILE (op) = 1; | |
64 | TREE_SIDE_EFFECTS (op) = 1; | |
65 | update_stmt (stmt); | |
66 | return true; | |
67 | } | |
6ab7a3d7 JL |
68 | return false; |
69 | } | |
70 | ||
71 | /* Insert a trap after SI and remove SI and all statements after the trap. */ | |
8fdc414d JL |
72 | |
73 | static void | |
6ab7a3d7 | 74 | insert_trap_and_remove_trailing_statements (gimple_stmt_iterator *si_p, tree op) |
8fdc414d | 75 | { |
6ab7a3d7 JL |
76 | /* We want the NULL pointer dereference to actually occur so that |
77 | code that wishes to catch the signal can do so. | |
78 | ||
79 | If the dereference is a load, then there's nothing to do as the | |
115d1851 | 80 | LHS will be a throw-away SSA_NAME and the RHS is the NULL dereference. |
8fdc414d | 81 | |
6ab7a3d7 | 82 | If the dereference is a store and we can easily transform the RHS, |
46dfed65 JL |
83 | then simplify the RHS to enable more DCE. Note that we require the |
84 | statement to be a GIMPLE_ASSIGN which filters out calls on the RHS. */ | |
6ab7a3d7 JL |
85 | gimple stmt = gsi_stmt (*si_p); |
86 | if (walk_stmt_load_store_ops (stmt, (void *)op, NULL, check_loadstore) | |
46dfed65 | 87 | && is_gimple_assign (stmt) |
6ab7a3d7 JL |
88 | && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))) |
89 | { | |
90 | /* We just need to turn the RHS into zero converted to the proper | |
91 | type. */ | |
92 | tree type = TREE_TYPE (gimple_assign_lhs (stmt)); | |
93 | gimple_assign_set_rhs_code (stmt, INTEGER_CST); | |
94 | gimple_assign_set_rhs1 (stmt, fold_convert (type, integer_zero_node)); | |
95 | update_stmt (stmt); | |
96 | } | |
97 | ||
98 | gimple new_stmt | |
99 | = gimple_build_call (builtin_decl_explicit (BUILT_IN_TRAP), 0); | |
100 | gimple_seq seq = NULL; | |
101 | gimple_seq_add_stmt (&seq, new_stmt); | |
102 | ||
103 | /* If we had a NULL pointer dereference, then we want to insert the | |
104 | __builtin_trap after the statement, for the other cases we want | |
105 | to insert before the statement. */ | |
106 | if (walk_stmt_load_store_ops (stmt, (void *)op, | |
107 | check_loadstore, | |
108 | check_loadstore)) | |
109 | gsi_insert_after (si_p, seq, GSI_NEW_STMT); | |
110 | else | |
111 | gsi_insert_before (si_p, seq, GSI_NEW_STMT); | |
112 | ||
56d338c9 JL |
113 | /* We must remove statements from the end of the block so that we |
114 | never reference a released SSA_NAME. */ | |
115 | basic_block bb = gimple_bb (gsi_stmt (*si_p)); | |
116 | for (gimple_stmt_iterator si = gsi_last_bb (bb); | |
117 | gsi_stmt (si) != gsi_stmt (*si_p); | |
118 | si = gsi_last_bb (bb)) | |
8fdc414d | 119 | { |
56d338c9 | 120 | stmt = gsi_stmt (si); |
8fdc414d | 121 | unlink_stmt_vdef (stmt); |
56d338c9 | 122 | gsi_remove (&si, true); |
8fdc414d JL |
123 | release_defs (stmt); |
124 | } | |
125 | } | |
126 | ||
127 | /* BB when reached via incoming edge E will exhibit undefined behaviour | |
128 | at STMT. Isolate and optimize the path which exhibits undefined | |
129 | behaviour. | |
130 | ||
131 | Isolation is simple. Duplicate BB and redirect E to BB'. | |
132 | ||
133 | Optimization is simple as well. Replace STMT in BB' with an | |
134 | unconditional trap and remove all outgoing edges from BB'. | |
135 | ||
136 | DUPLICATE is a pre-existing duplicate, use it as BB' if it exists. | |
137 | ||
138 | Return BB'. */ | |
139 | ||
140 | basic_block | |
6ab7a3d7 JL |
141 | isolate_path (basic_block bb, basic_block duplicate, |
142 | edge e, gimple stmt, tree op) | |
8fdc414d JL |
143 | { |
144 | gimple_stmt_iterator si, si2; | |
145 | edge_iterator ei; | |
146 | edge e2; | |
8fdc414d JL |
147 | |
148 | /* First duplicate BB if we have not done so already and remove all | |
149 | the duplicate's outgoing edges as duplicate is going to unconditionally | |
150 | trap. Removing the outgoing edges is both an optimization and ensures | |
151 | we don't need to do any PHI node updates. */ | |
152 | if (!duplicate) | |
153 | { | |
154 | duplicate = duplicate_block (bb, NULL, NULL); | |
155 | for (ei = ei_start (duplicate->succs); (e2 = ei_safe_edge (ei)); ) | |
156 | remove_edge (e2); | |
157 | } | |
158 | ||
159 | /* Complete the isolation step by redirecting E to reach DUPLICATE. */ | |
160 | e2 = redirect_edge_and_branch (e, duplicate); | |
161 | if (e2) | |
162 | flush_pending_stmts (e2); | |
163 | ||
164 | ||
165 | /* There may be more than one statement in DUPLICATE which exhibits | |
166 | undefined behaviour. Ultimately we want the first such statement in | |
167 | DUPLCIATE so that we're able to delete as much code as possible. | |
168 | ||
169 | So each time we discover undefined behaviour in DUPLICATE, search for | |
170 | the statement which triggers undefined behaviour. If found, then | |
171 | transform the statement into a trap and delete everything after the | |
172 | statement. If not found, then this particular instance was subsumed by | |
ae93744d | 173 | an earlier instance of undefined behaviour and there's nothing to do. |
8fdc414d JL |
174 | |
175 | This is made more complicated by the fact that we have STMT, which is in | |
176 | BB rather than in DUPLICATE. So we set up two iterators, one for each | |
177 | block and walk forward looking for STMT in BB, advancing each iterator at | |
178 | each step. | |
179 | ||
180 | When we find STMT the second iterator should point to STMT's equivalent in | |
181 | duplicate. If DUPLICATE ends before STMT is found in BB, then there's | |
ae93744d | 182 | nothing to do. |
8fdc414d JL |
183 | |
184 | Ignore labels and debug statements. */ | |
185 | si = gsi_start_nondebug_after_labels_bb (bb); | |
186 | si2 = gsi_start_nondebug_after_labels_bb (duplicate); | |
187 | while (!gsi_end_p (si) && !gsi_end_p (si2) && gsi_stmt (si) != stmt) | |
188 | { | |
189 | gsi_next_nondebug (&si); | |
190 | gsi_next_nondebug (&si2); | |
191 | } | |
192 | ||
193 | /* This would be an indicator that we never found STMT in BB, which should | |
194 | never happen. */ | |
195 | gcc_assert (!gsi_end_p (si)); | |
196 | ||
197 | /* If we did not run to the end of DUPLICATE, then SI points to STMT and | |
198 | SI2 points to the duplicate of STMT in DUPLICATE. Insert a trap | |
199 | before SI2 and remove SI2 and all trailing statements. */ | |
200 | if (!gsi_end_p (si2)) | |
6ab7a3d7 | 201 | insert_trap_and_remove_trailing_statements (&si2, op); |
8fdc414d JL |
202 | |
203 | return duplicate; | |
204 | } | |
205 | ||
56d338c9 JL |
206 | /* Look for PHI nodes which feed statements in the same block where |
207 | the value of the PHI node implies the statement is erroneous. | |
8fdc414d | 208 | |
56d338c9 JL |
209 | For example, a NULL PHI arg value which then feeds a pointer |
210 | dereference. | |
8fdc414d | 211 | |
56d338c9 JL |
212 | When found isolate and optimize the path associated with the PHI |
213 | argument feeding the erroneous statement. */ | |
214 | static void | |
215 | find_implicit_erroneous_behaviour (void) | |
8fdc414d JL |
216 | { |
217 | basic_block bb; | |
218 | ||
11cd3bed | 219 | FOR_EACH_BB_FN (bb, cfun) |
8fdc414d JL |
220 | { |
221 | gimple_stmt_iterator si; | |
222 | ||
5e94175f JL |
223 | /* Out of an abundance of caution, do not isolate paths to a |
224 | block where the block has any abnormal outgoing edges. | |
225 | ||
226 | We might be able to relax this in the future. We have to detect | |
227 | when we have to split the block with the NULL dereference and | |
228 | the trap we insert. We have to preserve abnormal edges out | |
229 | of the isolated block which in turn means updating PHIs at | |
230 | the targets of those abnormal outgoing edges. */ | |
6efe83b2 | 231 | if (has_abnormal_or_eh_outgoing_edge_p (bb)) |
5e94175f JL |
232 | continue; |
233 | ||
8fdc414d JL |
234 | /* First look for a PHI which sets a pointer to NULL and which |
235 | is then dereferenced within BB. This is somewhat overly | |
236 | conservative, but probably catches most of the interesting | |
237 | cases. */ | |
238 | for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si)) | |
239 | { | |
240 | gimple phi = gsi_stmt (si); | |
241 | tree lhs = gimple_phi_result (phi); | |
242 | ||
243 | /* If the result is not a pointer, then there is no need to | |
244 | examine the arguments. */ | |
245 | if (!POINTER_TYPE_P (TREE_TYPE (lhs))) | |
246 | continue; | |
247 | ||
248 | /* PHI produces a pointer result. See if any of the PHI's | |
ae93744d | 249 | arguments are NULL. |
8fdc414d JL |
250 | |
251 | When we remove an edge, we want to reprocess the current | |
252 | index, hence the ugly way we update I for each iteration. */ | |
253 | basic_block duplicate = NULL; | |
254 | for (unsigned i = 0, next_i = 0; | |
255 | i < gimple_phi_num_args (phi); | |
256 | i = next_i) | |
257 | { | |
258 | tree op = gimple_phi_arg_def (phi, i); | |
259 | ||
260 | next_i = i + 1; | |
ae93744d | 261 | |
8fdc414d JL |
262 | if (!integer_zerop (op)) |
263 | continue; | |
264 | ||
265 | edge e = gimple_phi_arg_edge (phi, i); | |
266 | imm_use_iterator iter; | |
267 | gimple use_stmt; | |
268 | ||
269 | /* We've got a NULL PHI argument. Now see if the | |
270 | PHI's result is dereferenced within BB. */ | |
271 | FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) | |
272 | { | |
273 | /* We only care about uses in BB. Catching cases in | |
274 | in other blocks would require more complex path | |
6efe83b2 JL |
275 | isolation code. */ |
276 | if (gimple_bb (use_stmt) != bb) | |
8fdc414d JL |
277 | continue; |
278 | ||
ae93744d JL |
279 | if (infer_nonnull_range (use_stmt, lhs, |
280 | flag_isolate_erroneous_paths_dereference, | |
281 | flag_isolate_erroneous_paths_attribute)) | |
282 | ||
8fdc414d JL |
283 | { |
284 | duplicate = isolate_path (bb, duplicate, | |
6ab7a3d7 | 285 | e, use_stmt, lhs); |
8fdc414d JL |
286 | |
287 | /* When we remove an incoming edge, we need to | |
288 | reprocess the Ith element. */ | |
289 | next_i = i; | |
290 | cfg_altered = true; | |
291 | } | |
292 | } | |
293 | } | |
294 | } | |
56d338c9 JL |
295 | } |
296 | } | |
297 | ||
298 | /* Look for statements which exhibit erroneous behaviour. For example | |
ae93744d | 299 | a NULL pointer dereference. |
56d338c9 JL |
300 | |
301 | When found, optimize the block containing the erroneous behaviour. */ | |
302 | static void | |
303 | find_explicit_erroneous_behaviour (void) | |
304 | { | |
305 | basic_block bb; | |
306 | ||
11cd3bed | 307 | FOR_EACH_BB_FN (bb, cfun) |
56d338c9 JL |
308 | { |
309 | gimple_stmt_iterator si; | |
8fdc414d | 310 | |
5e94175f JL |
311 | /* Out of an abundance of caution, do not isolate paths to a |
312 | block where the block has any abnormal outgoing edges. | |
313 | ||
314 | We might be able to relax this in the future. We have to detect | |
315 | when we have to split the block with the NULL dereference and | |
316 | the trap we insert. We have to preserve abnormal edges out | |
317 | of the isolated block which in turn means updating PHIs at | |
318 | the targets of those abnormal outgoing edges. */ | |
6efe83b2 | 319 | if (has_abnormal_or_eh_outgoing_edge_p (bb)) |
5e94175f JL |
320 | continue; |
321 | ||
8fdc414d JL |
322 | /* Now look at the statements in the block and see if any of |
323 | them explicitly dereference a NULL pointer. This happens | |
324 | because of jump threading and constant propagation. */ | |
325 | for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) | |
326 | { | |
327 | gimple stmt = gsi_stmt (si); | |
328 | ||
329 | /* By passing null_pointer_node, we can use infer_nonnull_range | |
330 | to detect explicit NULL pointer dereferences and other uses | |
331 | where a non-NULL value is required. */ | |
ae93744d JL |
332 | if (infer_nonnull_range (stmt, null_pointer_node, |
333 | flag_isolate_erroneous_paths_dereference, | |
334 | flag_isolate_erroneous_paths_attribute)) | |
8fdc414d | 335 | { |
6ab7a3d7 JL |
336 | insert_trap_and_remove_trailing_statements (&si, |
337 | null_pointer_node); | |
8fdc414d JL |
338 | |
339 | /* And finally, remove all outgoing edges from BB. */ | |
340 | edge e; | |
341 | for (edge_iterator ei = ei_start (bb->succs); | |
342 | (e = ei_safe_edge (ei)); ) | |
343 | remove_edge (e); | |
344 | ||
345 | /* Ignore any more operands on this statement and | |
346 | continue the statement iterator (which should | |
347 | terminate its loop immediately. */ | |
348 | cfg_altered = true; | |
349 | break; | |
350 | } | |
351 | } | |
352 | } | |
56d338c9 JL |
353 | } |
354 | /* Search the function for statements which, if executed, would cause | |
355 | the program to fault such as a dereference of a NULL pointer. | |
356 | ||
357 | Such a program can't be valid if such a statement was to execute | |
358 | according to ISO standards. | |
359 | ||
360 | We detect explicit NULL pointer dereferences as well as those implied | |
361 | by a PHI argument having a NULL value which unconditionally flows into | |
362 | a dereference in the same block as the PHI. | |
363 | ||
364 | In the former case we replace the offending statement with an | |
365 | unconditional trap and eliminate the outgoing edges from the statement's | |
366 | basic block. This may expose secondary optimization opportunities. | |
367 | ||
ae93744d | 368 | In the latter case, we isolate the path(s) with the NULL PHI |
56d338c9 JL |
369 | feeding the dereference. We can then replace the offending statement |
370 | and eliminate the outgoing edges in the duplicate. Again, this may | |
371 | expose secondary optimization opportunities. | |
372 | ||
373 | A warning for both cases may be advisable as well. | |
374 | ||
375 | Other statically detectable violations of the ISO standard could be | |
376 | handled in a similar way, such as out-of-bounds array indexing. */ | |
377 | ||
378 | static unsigned int | |
379 | gimple_ssa_isolate_erroneous_paths (void) | |
380 | { | |
381 | initialize_original_copy_tables (); | |
382 | ||
383 | /* Search all the blocks for edges which, if traversed, will | |
384 | result in undefined behaviour. */ | |
385 | cfg_altered = false; | |
386 | ||
387 | /* First handle cases where traversal of a particular edge | |
388 | triggers undefined behaviour. These cases require creating | |
389 | duplicate blocks and thus new SSA_NAMEs. | |
390 | ||
391 | We want that process complete prior to the phase where we start | |
392 | removing edges from the CFG. Edge removal may ultimately result in | |
393 | removal of PHI nodes and thus releasing SSA_NAMEs back to the | |
394 | name manager. | |
395 | ||
396 | If the two processes run in parallel we could release an SSA_NAME | |
397 | back to the manager but we could still have dangling references | |
398 | to the released SSA_NAME in unreachable blocks. | |
399 | that any released names not have dangling references in the IL. */ | |
400 | find_implicit_erroneous_behaviour (); | |
401 | find_explicit_erroneous_behaviour (); | |
402 | ||
8fdc414d JL |
403 | free_original_copy_tables (); |
404 | ||
ae93744d | 405 | /* We scramble the CFG and loop structures a bit, clean up |
8fdc414d JL |
406 | appropriately. We really should incrementally update the |
407 | loop structures, in theory it shouldn't be that hard. */ | |
408 | if (cfg_altered) | |
409 | { | |
410 | free_dominance_info (CDI_DOMINATORS); | |
411 | free_dominance_info (CDI_POST_DOMINATORS); | |
412 | loops_state_set (LOOPS_NEED_FIXUP); | |
413 | return TODO_cleanup_cfg | TODO_update_ssa; | |
414 | } | |
415 | return 0; | |
416 | } | |
417 | ||
418 | static bool | |
419 | gate_isolate_erroneous_paths (void) | |
420 | { | |
421 | /* If we do not have a suitable builtin function for the trap statement, | |
422 | then do not perform the optimization. */ | |
ae93744d JL |
423 | return (flag_isolate_erroneous_paths_dereference != 0 |
424 | || flag_isolate_erroneous_paths_attribute != 0); | |
8fdc414d JL |
425 | } |
426 | ||
427 | namespace { | |
428 | const pass_data pass_data_isolate_erroneous_paths = | |
429 | { | |
430 | GIMPLE_PASS, /* type */ | |
431 | "isolate-paths", /* name */ | |
432 | OPTGROUP_NONE, /* optinfo_flags */ | |
433 | true, /* has_gate */ | |
434 | true, /* has_execute */ | |
435 | TV_ISOLATE_ERRONEOUS_PATHS, /* tv_id */ | |
436 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
437 | 0, /* properties_provided */ | |
438 | 0, /* properties_destroyed */ | |
439 | 0, /* todo_flags_start */ | |
440 | TODO_verify_ssa, /* todo_flags_finish */ | |
441 | }; | |
442 | ||
443 | class pass_isolate_erroneous_paths : public gimple_opt_pass | |
444 | { | |
445 | public: | |
446 | pass_isolate_erroneous_paths (gcc::context *ctxt) | |
447 | : gimple_opt_pass (pass_data_isolate_erroneous_paths, ctxt) | |
448 | {} | |
449 | ||
450 | /* opt_pass methods: */ | |
451 | opt_pass * clone () { return new pass_isolate_erroneous_paths (m_ctxt); } | |
452 | bool gate () { return gate_isolate_erroneous_paths (); } | |
453 | unsigned int execute () { return gimple_ssa_isolate_erroneous_paths (); } | |
454 | ||
d35e43b9 | 455 | }; // class pass_isolate_erroneous_paths |
8fdc414d JL |
456 | } |
457 | ||
458 | gimple_opt_pass * | |
459 | make_pass_isolate_erroneous_paths (gcc::context *ctxt) | |
460 | { | |
461 | return new pass_isolate_erroneous_paths (ctxt); | |
462 | } |