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