]>
Commit | Line | Data |
---|---|---|
62b180e1 | 1 | /* SSA Jump Threading |
3aea1f79 | 2 | Copyright (C) 2005-2014 Free Software Foundation, Inc. |
62b180e1 | 3 | Contributed by Jeff Law <law@redhat.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
62b180e1 | 10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
62b180e1 | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "flags.h" | |
62b180e1 | 27 | #include "tm_p.h" |
62b180e1 | 28 | #include "basic-block.h" |
29 | #include "cfgloop.h" | |
62b180e1 | 30 | #include "function.h" |
62b180e1 | 31 | #include "timevar.h" |
b9ed1410 | 32 | #include "dumpfile.h" |
bc61cadb | 33 | #include "pointer-set.h" |
34 | #include "tree-ssa-alias.h" | |
35 | #include "internal-fn.h" | |
36 | #include "gimple-expr.h" | |
37 | #include "is-a.h" | |
073c1fd5 | 38 | #include "gimple.h" |
dcf1a1ec | 39 | #include "gimple-iterator.h" |
073c1fd5 | 40 | #include "gimple-ssa.h" |
41 | #include "tree-cfg.h" | |
42 | #include "tree-phinodes.h" | |
43 | #include "ssa-iterators.h" | |
9ed99284 | 44 | #include "stringpool.h" |
073c1fd5 | 45 | #include "tree-ssanames.h" |
62b180e1 | 46 | #include "tree-ssa-propagate.h" |
0c5b289a | 47 | #include "tree-ssa-threadupdate.h" |
62b180e1 | 48 | #include "langhooks.h" |
49 | #include "params.h" | |
424a4a92 | 50 | #include "tree-ssa-threadedge.h" |
f7715905 | 51 | #include "builtins.h" |
62b180e1 | 52 | |
53 | /* To avoid code explosion due to jump threading, we limit the | |
54 | number of statements we are going to copy. This variable | |
55 | holds the number of statements currently seen that we'll have | |
56 | to copy as part of the jump threading process. */ | |
57 | static int stmt_count; | |
58 | ||
f003f9fd | 59 | /* Array to record value-handles per SSA_NAME. */ |
f1f41a6c | 60 | vec<tree> ssa_name_values; |
f003f9fd | 61 | |
62 | /* Set the value for the SSA name NAME to VALUE. */ | |
63 | ||
64 | void | |
65 | set_ssa_name_value (tree name, tree value) | |
66 | { | |
f1f41a6c | 67 | if (SSA_NAME_VERSION (name) >= ssa_name_values.length ()) |
68 | ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1); | |
f5faab84 | 69 | if (value && TREE_OVERFLOW_P (value)) |
70 | value = drop_tree_overflow (value); | |
f1f41a6c | 71 | ssa_name_values[SSA_NAME_VERSION (name)] = value; |
f003f9fd | 72 | } |
73 | ||
74 | /* Initialize the per SSA_NAME value-handles array. Returns it. */ | |
75 | void | |
76 | threadedge_initialize_values (void) | |
77 | { | |
f1f41a6c | 78 | gcc_assert (!ssa_name_values.exists ()); |
79 | ssa_name_values.create (num_ssa_names); | |
f003f9fd | 80 | } |
81 | ||
82 | /* Free the per SSA_NAME value-handle array. */ | |
83 | void | |
84 | threadedge_finalize_values (void) | |
85 | { | |
f1f41a6c | 86 | ssa_name_values.release (); |
f003f9fd | 87 | } |
88 | ||
62b180e1 | 89 | /* Return TRUE if we may be able to thread an incoming edge into |
90 | BB to an outgoing edge from BB. Return FALSE otherwise. */ | |
91 | ||
92 | bool | |
93 | potentially_threadable_block (basic_block bb) | |
94 | { | |
75a70cf9 | 95 | gimple_stmt_iterator gsi; |
62b180e1 | 96 | |
97 | /* If BB has a single successor or a single predecessor, then | |
98 | there is no threading opportunity. */ | |
99 | if (single_succ_p (bb) || single_pred_p (bb)) | |
100 | return false; | |
101 | ||
102 | /* If BB does not end with a conditional, switch or computed goto, | |
103 | then there is no threading opportunity. */ | |
75a70cf9 | 104 | gsi = gsi_last_bb (bb); |
105 | if (gsi_end_p (gsi) | |
106 | || ! gsi_stmt (gsi) | |
107 | || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND | |
108 | && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO | |
109 | && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH)) | |
62b180e1 | 110 | return false; |
111 | ||
112 | return true; | |
113 | } | |
114 | ||
115 | /* Return the LHS of any ASSERT_EXPR where OP appears as the first | |
116 | argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates | |
117 | BB. If no such ASSERT_EXPR is found, return OP. */ | |
118 | ||
119 | static tree | |
75a70cf9 | 120 | lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt) |
62b180e1 | 121 | { |
122 | imm_use_iterator imm_iter; | |
75a70cf9 | 123 | gimple use_stmt; |
09aca5bc | 124 | use_operand_p use_p; |
62b180e1 | 125 | |
09aca5bc | 126 | FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op) |
62b180e1 | 127 | { |
09aca5bc | 128 | use_stmt = USE_STMT (use_p); |
62b180e1 | 129 | if (use_stmt != stmt |
75a70cf9 | 130 | && gimple_assign_single_p (use_stmt) |
131 | && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ASSERT_EXPR | |
132 | && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == op | |
133 | && dominated_by_p (CDI_DOMINATORS, bb, gimple_bb (use_stmt))) | |
09aca5bc | 134 | { |
75a70cf9 | 135 | return gimple_assign_lhs (use_stmt); |
09aca5bc | 136 | } |
62b180e1 | 137 | } |
138 | return op; | |
139 | } | |
140 | ||
62b180e1 | 141 | /* We record temporary equivalences created by PHI nodes or |
142 | statements within the target block. Doing so allows us to | |
143 | identify more jump threading opportunities, even in blocks | |
144 | with side effects. | |
145 | ||
146 | We keep track of those temporary equivalences in a stack | |
147 | structure so that we can unwind them when we're done processing | |
148 | a particular edge. This routine handles unwinding the data | |
149 | structures. */ | |
150 | ||
151 | static void | |
f1f41a6c | 152 | remove_temporary_equivalences (vec<tree> *stack) |
62b180e1 | 153 | { |
f1f41a6c | 154 | while (stack->length () > 0) |
62b180e1 | 155 | { |
156 | tree prev_value, dest; | |
157 | ||
f1f41a6c | 158 | dest = stack->pop (); |
62b180e1 | 159 | |
334ec2d8 | 160 | /* A NULL value indicates we should stop unwinding, otherwise |
62b180e1 | 161 | pop off the next entry as they're recorded in pairs. */ |
162 | if (dest == NULL) | |
163 | break; | |
164 | ||
f1f41a6c | 165 | prev_value = stack->pop (); |
f003f9fd | 166 | set_ssa_name_value (dest, prev_value); |
62b180e1 | 167 | } |
168 | } | |
169 | ||
170 | /* Record a temporary equivalence, saving enough information so that | |
171 | we can restore the state of recorded equivalences when we're | |
172 | done processing the current edge. */ | |
173 | ||
174 | static void | |
f1f41a6c | 175 | record_temporary_equivalence (tree x, tree y, vec<tree> *stack) |
62b180e1 | 176 | { |
177 | tree prev_x = SSA_NAME_VALUE (x); | |
178 | ||
c294418d | 179 | /* Y may be NULL if we are invalidating entries in the table. */ |
180 | if (y && TREE_CODE (y) == SSA_NAME) | |
62b180e1 | 181 | { |
182 | tree tmp = SSA_NAME_VALUE (y); | |
183 | y = tmp ? tmp : y; | |
184 | } | |
185 | ||
f003f9fd | 186 | set_ssa_name_value (x, y); |
f1f41a6c | 187 | stack->reserve (2); |
188 | stack->quick_push (prev_x); | |
189 | stack->quick_push (x); | |
62b180e1 | 190 | } |
191 | ||
192 | /* Record temporary equivalences created by PHIs at the target of the | |
48e1416a | 193 | edge E. Record unwind information for the equivalences onto STACK. |
62b180e1 | 194 | |
195 | If a PHI which prevents threading is encountered, then return FALSE | |
c294418d | 196 | indicating we should not thread this edge, else return TRUE. |
197 | ||
198 | If SRC_MAP/DST_MAP exist, then mark the source and destination SSA_NAMEs | |
199 | of any equivalences recorded. We use this to make invalidation after | |
200 | traversing back edges less painful. */ | |
62b180e1 | 201 | |
202 | static bool | |
c294418d | 203 | record_temporary_equivalences_from_phis (edge e, vec<tree> *stack, |
204 | bool backedge_seen, | |
205 | bitmap src_map, bitmap dst_map) | |
62b180e1 | 206 | { |
75a70cf9 | 207 | gimple_stmt_iterator gsi; |
62b180e1 | 208 | |
209 | /* Each PHI creates a temporary equivalence, record them. | |
210 | These are context sensitive equivalences and will be removed | |
211 | later. */ | |
75a70cf9 | 212 | for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
62b180e1 | 213 | { |
75a70cf9 | 214 | gimple phi = gsi_stmt (gsi); |
62b180e1 | 215 | tree src = PHI_ARG_DEF_FROM_EDGE (phi, e); |
75a70cf9 | 216 | tree dst = gimple_phi_result (phi); |
62b180e1 | 217 | |
48e1416a | 218 | /* If the desired argument is not the same as this PHI's result |
62b180e1 | 219 | and it is set by a PHI in E->dest, then we can not thread |
220 | through E->dest. */ | |
221 | if (src != dst | |
222 | && TREE_CODE (src) == SSA_NAME | |
75a70cf9 | 223 | && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI |
224 | && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest) | |
62b180e1 | 225 | return false; |
226 | ||
227 | /* We consider any non-virtual PHI as a statement since it | |
228 | count result in a constant assignment or copy operation. */ | |
7c782c9b | 229 | if (!virtual_operand_p (dst)) |
62b180e1 | 230 | stmt_count++; |
231 | ||
232 | record_temporary_equivalence (dst, src, stack); | |
c294418d | 233 | |
234 | /* If we have crossed a backedge, then start recording equivalences | |
235 | we might need to invalidate. */ | |
236 | if (backedge_seen && TREE_CODE (src) == SSA_NAME) | |
237 | { | |
238 | bitmap_set_bit (src_map, SSA_NAME_VERSION (src)); | |
239 | bitmap_set_bit (dst_map, SSA_NAME_VERSION (dst)); | |
240 | } | |
62b180e1 | 241 | } |
242 | return true; | |
243 | } | |
244 | ||
75a70cf9 | 245 | /* Fold the RHS of an assignment statement and return it as a tree. |
246 | May return NULL_TREE if no simplification is possible. */ | |
247 | ||
248 | static tree | |
249 | fold_assignment_stmt (gimple stmt) | |
250 | { | |
251 | enum tree_code subcode = gimple_assign_rhs_code (stmt); | |
252 | ||
253 | switch (get_gimple_rhs_class (subcode)) | |
254 | { | |
255 | case GIMPLE_SINGLE_RHS: | |
8a2caf10 | 256 | return fold (gimple_assign_rhs1 (stmt)); |
00f4f705 | 257 | |
75a70cf9 | 258 | case GIMPLE_UNARY_RHS: |
259 | { | |
260 | tree lhs = gimple_assign_lhs (stmt); | |
261 | tree op0 = gimple_assign_rhs1 (stmt); | |
262 | return fold_unary (subcode, TREE_TYPE (lhs), op0); | |
263 | } | |
00f4f705 | 264 | |
75a70cf9 | 265 | case GIMPLE_BINARY_RHS: |
266 | { | |
267 | tree lhs = gimple_assign_lhs (stmt); | |
268 | tree op0 = gimple_assign_rhs1 (stmt); | |
269 | tree op1 = gimple_assign_rhs2 (stmt); | |
270 | return fold_binary (subcode, TREE_TYPE (lhs), op0, op1); | |
271 | } | |
00f4f705 | 272 | |
273 | case GIMPLE_TERNARY_RHS: | |
274 | { | |
275 | tree lhs = gimple_assign_lhs (stmt); | |
276 | tree op0 = gimple_assign_rhs1 (stmt); | |
277 | tree op1 = gimple_assign_rhs2 (stmt); | |
278 | tree op2 = gimple_assign_rhs3 (stmt); | |
8a2caf10 | 279 | |
280 | /* Sadly, we have to handle conditional assignments specially | |
281 | here, because fold expects all the operands of an expression | |
282 | to be folded before the expression itself is folded, but we | |
283 | can't just substitute the folded condition here. */ | |
284 | if (gimple_assign_rhs_code (stmt) == COND_EXPR) | |
285 | op0 = fold (op0); | |
286 | ||
00f4f705 | 287 | return fold_ternary (subcode, TREE_TYPE (lhs), op0, op1, op2); |
288 | } | |
289 | ||
75a70cf9 | 290 | default: |
291 | gcc_unreachable (); | |
292 | } | |
293 | } | |
294 | ||
c294418d | 295 | /* A new value has been assigned to LHS. If necessary, invalidate any |
296 | equivalences that are no longer valid. */ | |
297 | static void | |
298 | invalidate_equivalences (tree lhs, vec<tree> *stack, | |
299 | bitmap src_map, bitmap dst_map) | |
300 | { | |
301 | /* SRC_MAP contains the source SSA_NAMEs for equivalences created by PHI | |
302 | nodes. If an entry in SRC_MAP changes, there's some destination that | |
303 | has been recorded as equivalent to the source and that equivalency | |
304 | needs to be eliminated. */ | |
305 | if (bitmap_bit_p (src_map, SSA_NAME_VERSION (lhs))) | |
306 | { | |
307 | unsigned int i; | |
308 | bitmap_iterator bi; | |
309 | ||
310 | /* We know that the LHS of STMT was used as the RHS in an equivalency | |
311 | created by a PHI. All the LHS of such PHIs were recorded into DST_MAP. | |
312 | So we can iterate over them to see if any have the LHS of STMT as | |
313 | an equivalence, and if so, remove the equivalence as it is no longer | |
314 | valid. */ | |
315 | EXECUTE_IF_SET_IN_BITMAP (dst_map, 0, i, bi) | |
316 | { | |
317 | if (SSA_NAME_VALUE (ssa_name (i)) == lhs) | |
318 | record_temporary_equivalence (ssa_name (i), NULL_TREE, stack); | |
319 | } | |
320 | } | |
321 | } | |
322 | ||
62b180e1 | 323 | /* Try to simplify each statement in E->dest, ultimately leading to |
324 | a simplification of the COND_EXPR at the end of E->dest. | |
325 | ||
326 | Record unwind information for temporary equivalences onto STACK. | |
327 | ||
328 | Use SIMPLIFY (a pointer to a callback function) to further simplify | |
48e1416a | 329 | statements using pass specific information. |
62b180e1 | 330 | |
331 | We might consider marking just those statements which ultimately | |
332 | feed the COND_EXPR. It's not clear if the overhead of bookkeeping | |
333 | would be recovered by trying to simplify fewer statements. | |
334 | ||
335 | If we are able to simplify a statement into the form | |
336 | SSA_NAME = (SSA_NAME | gimple invariant), then we can record | |
75a70cf9 | 337 | a context sensitive equivalence which may help us simplify |
62b180e1 | 338 | later statements in E->dest. */ |
339 | ||
75a70cf9 | 340 | static gimple |
62b180e1 | 341 | record_temporary_equivalences_from_stmts_at_dest (edge e, |
f1f41a6c | 342 | vec<tree> *stack, |
75a70cf9 | 343 | tree (*simplify) (gimple, |
c294418d | 344 | gimple), |
345 | bool backedge_seen, | |
346 | bitmap src_map, | |
347 | bitmap dst_map) | |
62b180e1 | 348 | { |
75a70cf9 | 349 | gimple stmt = NULL; |
350 | gimple_stmt_iterator gsi; | |
62b180e1 | 351 | int max_stmt_count; |
352 | ||
353 | max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS); | |
354 | ||
355 | /* Walk through each statement in the block recording equivalences | |
356 | we discover. Note any equivalences we discover are context | |
357 | sensitive (ie, are dependent on traversing E) and must be unwound | |
358 | when we're finished processing E. */ | |
75a70cf9 | 359 | for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
62b180e1 | 360 | { |
361 | tree cached_lhs = NULL; | |
362 | ||
75a70cf9 | 363 | stmt = gsi_stmt (gsi); |
62b180e1 | 364 | |
365 | /* Ignore empty statements and labels. */ | |
9845d120 | 366 | if (gimple_code (stmt) == GIMPLE_NOP |
367 | || gimple_code (stmt) == GIMPLE_LABEL | |
368 | || is_gimple_debug (stmt)) | |
62b180e1 | 369 | continue; |
370 | ||
62b180e1 | 371 | /* If the statement has volatile operands, then we assume we |
372 | can not thread through this block. This is overly | |
373 | conservative in some ways. */ | |
75a70cf9 | 374 | if (gimple_code (stmt) == GIMPLE_ASM && gimple_asm_volatile_p (stmt)) |
62b180e1 | 375 | return NULL; |
376 | ||
377 | /* If duplicating this block is going to cause too much code | |
378 | expansion, then do not thread through this block. */ | |
379 | stmt_count++; | |
380 | if (stmt_count > max_stmt_count) | |
381 | return NULL; | |
382 | ||
75a70cf9 | 383 | /* If this is not a statement that sets an SSA_NAME to a new |
62b180e1 | 384 | value, then do not try to simplify this statement as it will |
385 | not simplify in any way that is helpful for jump threading. */ | |
75a70cf9 | 386 | if ((gimple_code (stmt) != GIMPLE_ASSIGN |
387 | || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) | |
388 | && (gimple_code (stmt) != GIMPLE_CALL | |
389 | || gimple_call_lhs (stmt) == NULL_TREE | |
390 | || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME)) | |
bb3a8839 | 391 | { |
392 | /* STMT might still have DEFS and we need to invalidate any known | |
393 | equivalences for them. | |
394 | ||
395 | Consider if STMT is a GIMPLE_ASM with one or more outputs that | |
396 | feeds a conditional inside a loop. We might derive an equivalence | |
397 | due to the conditional. */ | |
398 | tree op; | |
399 | ssa_op_iter iter; | |
400 | ||
401 | if (backedge_seen) | |
96902209 | 402 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) |
bb3a8839 | 403 | { |
404 | /* This call only invalidates equivalences created by | |
405 | PHI nodes. This is by design to keep the cost of | |
406 | of invalidation reasonable. */ | |
407 | invalidate_equivalences (op, stack, src_map, dst_map); | |
408 | ||
409 | /* However, conditionals can imply values for real | |
410 | operands as well. And those won't be recorded in the | |
411 | maps. In fact, those equivalences may be recorded totally | |
412 | outside the threading code. We can just create a new | |
413 | temporary NULL equivalence here. */ | |
414 | record_temporary_equivalence (op, NULL_TREE, stack); | |
415 | } | |
416 | ||
417 | continue; | |
418 | } | |
62b180e1 | 419 | |
55c10931 | 420 | /* The result of __builtin_object_size depends on all the arguments |
421 | of a phi node. Temporarily using only one edge produces invalid | |
422 | results. For example | |
423 | ||
424 | if (x < 6) | |
425 | goto l; | |
426 | else | |
427 | goto l; | |
428 | ||
429 | l: | |
430 | r = PHI <&w[2].a[1](2), &a.a[6](3)> | |
431 | __builtin_object_size (r, 0) | |
432 | ||
433 | The result of __builtin_object_size is defined to be the maximum of | |
434 | remaining bytes. If we use only one edge on the phi, the result will | |
99e2edfd | 435 | change to be the remaining bytes for the corresponding phi argument. |
436 | ||
437 | Similarly for __builtin_constant_p: | |
438 | ||
439 | r = PHI <1(2), 2(3)> | |
440 | __builtin_constant_p (r) | |
441 | ||
442 | Both PHI arguments are constant, but x ? 1 : 2 is still not | |
443 | constant. */ | |
55c10931 | 444 | |
75a70cf9 | 445 | if (is_gimple_call (stmt)) |
55c10931 | 446 | { |
75a70cf9 | 447 | tree fndecl = gimple_call_fndecl (stmt); |
99e2edfd | 448 | if (fndecl |
449 | && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE | |
450 | || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)) | |
c294418d | 451 | { |
452 | if (backedge_seen) | |
453 | { | |
454 | tree lhs = gimple_get_lhs (stmt); | |
455 | record_temporary_equivalence (lhs, NULL_TREE, stack); | |
456 | invalidate_equivalences (lhs, stack, src_map, dst_map); | |
457 | } | |
458 | continue; | |
459 | } | |
55c10931 | 460 | } |
461 | ||
62b180e1 | 462 | /* At this point we have a statement which assigns an RHS to an |
463 | SSA_VAR on the LHS. We want to try and simplify this statement | |
464 | to expose more context sensitive equivalences which in turn may | |
48e1416a | 465 | allow us to simplify the condition at the end of the loop. |
62b180e1 | 466 | |
467 | Handle simple copy operations as well as implied copies from | |
468 | ASSERT_EXPRs. */ | |
75a70cf9 | 469 | if (gimple_assign_single_p (stmt) |
470 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
471 | cached_lhs = gimple_assign_rhs1 (stmt); | |
472 | else if (gimple_assign_single_p (stmt) | |
473 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) | |
474 | cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
62b180e1 | 475 | else |
476 | { | |
477 | /* A statement that is not a trivial copy or ASSERT_EXPR. | |
478 | We're going to temporarily copy propagate the operands | |
479 | and see if that allows us to simplify this statement. */ | |
75a70cf9 | 480 | tree *copy; |
62b180e1 | 481 | ssa_op_iter iter; |
482 | use_operand_p use_p; | |
483 | unsigned int num, i = 0; | |
484 | ||
485 | num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE)); | |
486 | copy = XCNEWVEC (tree, num); | |
487 | ||
488 | /* Make a copy of the uses & vuses into USES_COPY, then cprop into | |
489 | the operands. */ | |
490 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE) | |
491 | { | |
492 | tree tmp = NULL; | |
493 | tree use = USE_FROM_PTR (use_p); | |
494 | ||
495 | copy[i++] = use; | |
496 | if (TREE_CODE (use) == SSA_NAME) | |
497 | tmp = SSA_NAME_VALUE (use); | |
f6c33c78 | 498 | if (tmp) |
62b180e1 | 499 | SET_USE (use_p, tmp); |
500 | } | |
501 | ||
502 | /* Try to fold/lookup the new expression. Inserting the | |
75a70cf9 | 503 | expression into the hash table is unlikely to help. */ |
504 | if (is_gimple_call (stmt)) | |
505 | cached_lhs = fold_call_stmt (stmt, false); | |
62b180e1 | 506 | else |
75a70cf9 | 507 | cached_lhs = fold_assignment_stmt (stmt); |
62b180e1 | 508 | |
75a70cf9 | 509 | if (!cached_lhs |
510 | || (TREE_CODE (cached_lhs) != SSA_NAME | |
511 | && !is_gimple_min_invariant (cached_lhs))) | |
512 | cached_lhs = (*simplify) (stmt, stmt); | |
48e1416a | 513 | |
62b180e1 | 514 | /* Restore the statement's original uses/defs. */ |
515 | i = 0; | |
516 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE) | |
517 | SET_USE (use_p, copy[i++]); | |
518 | ||
519 | free (copy); | |
520 | } | |
521 | ||
522 | /* Record the context sensitive equivalence if we were able | |
c294418d | 523 | to simplify this statement. |
524 | ||
525 | If we have traversed a backedge at some point during threading, | |
526 | then always enter something here. Either a real equivalence, | |
527 | or a NULL_TREE equivalence which is effectively invalidation of | |
528 | prior equivalences. */ | |
62b180e1 | 529 | if (cached_lhs |
530 | && (TREE_CODE (cached_lhs) == SSA_NAME | |
531 | || is_gimple_min_invariant (cached_lhs))) | |
75a70cf9 | 532 | record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack); |
c294418d | 533 | else if (backedge_seen) |
534 | record_temporary_equivalence (gimple_get_lhs (stmt), NULL_TREE, stack); | |
535 | ||
536 | if (backedge_seen) | |
537 | invalidate_equivalences (gimple_get_lhs (stmt), stack, | |
538 | src_map, dst_map); | |
62b180e1 | 539 | } |
540 | return stmt; | |
541 | } | |
542 | ||
c294418d | 543 | /* Once we have passed a backedge in the CFG when threading, we do not want to |
544 | utilize edge equivalences for simplification purpose. They are no longer | |
545 | necessarily valid. We use this callback rather than the ones provided by | |
546 | DOM/VRP to achieve that effect. */ | |
547 | static tree | |
548 | dummy_simplify (gimple stmt1 ATTRIBUTE_UNUSED, gimple stmt2 ATTRIBUTE_UNUSED) | |
549 | { | |
550 | return NULL_TREE; | |
551 | } | |
552 | ||
62b180e1 | 553 | /* Simplify the control statement at the end of the block E->dest. |
554 | ||
75a70cf9 | 555 | To avoid allocating memory unnecessarily, a scratch GIMPLE_COND |
62b180e1 | 556 | is available to use/clobber in DUMMY_COND. |
557 | ||
558 | Use SIMPLIFY (a pointer to a callback function) to further simplify | |
559 | a condition using pass specific information. | |
560 | ||
561 | Return the simplified condition or NULL if simplification could | |
562 | not be performed. */ | |
563 | ||
564 | static tree | |
565 | simplify_control_stmt_condition (edge e, | |
75a70cf9 | 566 | gimple stmt, |
567 | gimple dummy_cond, | |
568 | tree (*simplify) (gimple, gimple), | |
62b180e1 | 569 | bool handle_dominating_asserts) |
570 | { | |
571 | tree cond, cached_lhs; | |
75a70cf9 | 572 | enum gimple_code code = gimple_code (stmt); |
62b180e1 | 573 | |
574 | /* For comparisons, we have to update both operands, then try | |
575 | to simplify the comparison. */ | |
75a70cf9 | 576 | if (code == GIMPLE_COND) |
62b180e1 | 577 | { |
578 | tree op0, op1; | |
579 | enum tree_code cond_code; | |
580 | ||
75a70cf9 | 581 | op0 = gimple_cond_lhs (stmt); |
582 | op1 = gimple_cond_rhs (stmt); | |
583 | cond_code = gimple_cond_code (stmt); | |
62b180e1 | 584 | |
585 | /* Get the current value of both operands. */ | |
586 | if (TREE_CODE (op0) == SSA_NAME) | |
587 | { | |
588 | tree tmp = SSA_NAME_VALUE (op0); | |
f6c33c78 | 589 | if (tmp) |
62b180e1 | 590 | op0 = tmp; |
591 | } | |
592 | ||
593 | if (TREE_CODE (op1) == SSA_NAME) | |
594 | { | |
595 | tree tmp = SSA_NAME_VALUE (op1); | |
f6c33c78 | 596 | if (tmp) |
62b180e1 | 597 | op1 = tmp; |
598 | } | |
599 | ||
600 | if (handle_dominating_asserts) | |
601 | { | |
602 | /* Now see if the operand was consumed by an ASSERT_EXPR | |
603 | which dominates E->src. If so, we want to replace the | |
604 | operand with the LHS of the ASSERT_EXPR. */ | |
605 | if (TREE_CODE (op0) == SSA_NAME) | |
606 | op0 = lhs_of_dominating_assert (op0, e->src, stmt); | |
607 | ||
608 | if (TREE_CODE (op1) == SSA_NAME) | |
609 | op1 = lhs_of_dominating_assert (op1, e->src, stmt); | |
610 | } | |
611 | ||
612 | /* We may need to canonicalize the comparison. For | |
613 | example, op0 might be a constant while op1 is an | |
614 | SSA_NAME. Failure to canonicalize will cause us to | |
615 | miss threading opportunities. */ | |
75a70cf9 | 616 | if (tree_swap_operands_p (op0, op1, false)) |
62b180e1 | 617 | { |
618 | tree tmp; | |
75a70cf9 | 619 | cond_code = swap_tree_comparison (cond_code); |
62b180e1 | 620 | tmp = op0; |
621 | op0 = op1; | |
622 | op1 = tmp; | |
623 | } | |
624 | ||
625 | /* Stuff the operator and operands into our dummy conditional | |
626 | expression. */ | |
75a70cf9 | 627 | gimple_cond_set_code (dummy_cond, cond_code); |
628 | gimple_cond_set_lhs (dummy_cond, op0); | |
629 | gimple_cond_set_rhs (dummy_cond, op1); | |
62b180e1 | 630 | |
631 | /* We absolutely do not care about any type conversions | |
632 | we only care about a zero/nonzero value. */ | |
add6ee5e | 633 | fold_defer_overflow_warnings (); |
634 | ||
75a70cf9 | 635 | cached_lhs = fold_binary (cond_code, boolean_type_node, op0, op1); |
636 | if (cached_lhs) | |
d9659041 | 637 | while (CONVERT_EXPR_P (cached_lhs)) |
75a70cf9 | 638 | cached_lhs = TREE_OPERAND (cached_lhs, 0); |
add6ee5e | 639 | |
75a70cf9 | 640 | fold_undefer_overflow_warnings ((cached_lhs |
641 | && is_gimple_min_invariant (cached_lhs)), | |
add6ee5e | 642 | stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); |
643 | ||
62b180e1 | 644 | /* If we have not simplified the condition down to an invariant, |
645 | then use the pass specific callback to simplify the condition. */ | |
75a70cf9 | 646 | if (!cached_lhs |
647 | || !is_gimple_min_invariant (cached_lhs)) | |
648 | cached_lhs = (*simplify) (dummy_cond, stmt); | |
649 | ||
650 | return cached_lhs; | |
62b180e1 | 651 | } |
652 | ||
75a70cf9 | 653 | if (code == GIMPLE_SWITCH) |
654 | cond = gimple_switch_index (stmt); | |
655 | else if (code == GIMPLE_GOTO) | |
656 | cond = gimple_goto_dest (stmt); | |
657 | else | |
658 | gcc_unreachable (); | |
659 | ||
62b180e1 | 660 | /* We can have conditionals which just test the state of a variable |
661 | rather than use a relational operator. These are simpler to handle. */ | |
75a70cf9 | 662 | if (TREE_CODE (cond) == SSA_NAME) |
62b180e1 | 663 | { |
664 | cached_lhs = cond; | |
665 | ||
75a70cf9 | 666 | /* Get the variable's current value from the equivalence chains. |
2a5af6bf | 667 | |
668 | It is possible to get loops in the SSA_NAME_VALUE chains | |
669 | (consider threading the backedge of a loop where we have | |
670 | a loop invariant SSA_NAME used in the condition. */ | |
671 | if (cached_lhs | |
672 | && TREE_CODE (cached_lhs) == SSA_NAME | |
673 | && SSA_NAME_VALUE (cached_lhs)) | |
62b180e1 | 674 | cached_lhs = SSA_NAME_VALUE (cached_lhs); |
675 | ||
676 | /* If we're dominated by a suitable ASSERT_EXPR, then | |
677 | update CACHED_LHS appropriately. */ | |
678 | if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME) | |
679 | cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt); | |
680 | ||
681 | /* If we haven't simplified to an invariant yet, then use the | |
682 | pass specific callback to try and simplify it further. */ | |
683 | if (cached_lhs && ! is_gimple_min_invariant (cached_lhs)) | |
a2a1fde2 | 684 | cached_lhs = (*simplify) (stmt, stmt); |
62b180e1 | 685 | } |
686 | else | |
687 | cached_lhs = NULL; | |
688 | ||
689 | return cached_lhs; | |
690 | } | |
691 | ||
1ea5fe8f | 692 | /* Copy debug stmts from DEST's chain of single predecessors up to |
693 | SRC, so that we don't lose the bindings as PHI nodes are introduced | |
694 | when DEST gains new predecessors. */ | |
80ed2d81 | 695 | void |
1ea5fe8f | 696 | propagate_threaded_block_debug_into (basic_block dest, basic_block src) |
697 | { | |
698 | if (!MAY_HAVE_DEBUG_STMTS) | |
699 | return; | |
700 | ||
701 | if (!single_pred_p (dest)) | |
702 | return; | |
703 | ||
704 | gcc_checking_assert (dest != src); | |
705 | ||
706 | gimple_stmt_iterator gsi = gsi_after_labels (dest); | |
9f27dbc3 | 707 | int i = 0; |
708 | const int alloc_count = 16; // ?? Should this be a PARAM? | |
1ea5fe8f | 709 | |
9f27dbc3 | 710 | /* Estimate the number of debug vars overridden in the beginning of |
711 | DEST, to tell how many we're going to need to begin with. */ | |
1ea5fe8f | 712 | for (gimple_stmt_iterator si = gsi; |
9f27dbc3 | 713 | i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si)) |
714 | { | |
715 | gimple stmt = gsi_stmt (si); | |
716 | if (!is_gimple_debug (stmt)) | |
717 | break; | |
718 | i++; | |
719 | } | |
720 | ||
4997014d | 721 | auto_vec<tree, alloc_count> fewvars; |
9f27dbc3 | 722 | pointer_set_t *vars = NULL; |
723 | ||
724 | /* If we're already starting with 3/4 of alloc_count, go for a | |
725 | pointer_set, otherwise start with an unordered stack-allocated | |
726 | VEC. */ | |
727 | if (i * 4 > alloc_count * 3) | |
728 | vars = pointer_set_create (); | |
9f27dbc3 | 729 | |
730 | /* Now go through the initial debug stmts in DEST again, this time | |
731 | actually inserting in VARS or FEWVARS. Don't bother checking for | |
732 | duplicates in FEWVARS. */ | |
733 | for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si)) | |
1ea5fe8f | 734 | { |
735 | gimple stmt = gsi_stmt (si); | |
736 | if (!is_gimple_debug (stmt)) | |
737 | break; | |
738 | ||
739 | tree var; | |
740 | ||
741 | if (gimple_debug_bind_p (stmt)) | |
742 | var = gimple_debug_bind_get_var (stmt); | |
743 | else if (gimple_debug_source_bind_p (stmt)) | |
744 | var = gimple_debug_source_bind_get_var (stmt); | |
745 | else | |
746 | gcc_unreachable (); | |
747 | ||
9f27dbc3 | 748 | if (vars) |
749 | pointer_set_insert (vars, var); | |
750 | else | |
f1f41a6c | 751 | fewvars.quick_push (var); |
1ea5fe8f | 752 | } |
753 | ||
754 | basic_block bb = dest; | |
755 | ||
756 | do | |
757 | { | |
758 | bb = single_pred (bb); | |
759 | for (gimple_stmt_iterator si = gsi_last_bb (bb); | |
760 | !gsi_end_p (si); gsi_prev (&si)) | |
761 | { | |
762 | gimple stmt = gsi_stmt (si); | |
763 | if (!is_gimple_debug (stmt)) | |
764 | continue; | |
765 | ||
766 | tree var; | |
767 | ||
768 | if (gimple_debug_bind_p (stmt)) | |
769 | var = gimple_debug_bind_get_var (stmt); | |
770 | else if (gimple_debug_source_bind_p (stmt)) | |
771 | var = gimple_debug_source_bind_get_var (stmt); | |
772 | else | |
773 | gcc_unreachable (); | |
774 | ||
775 | /* Discard debug bind overlaps. ??? Unlike stmts from src, | |
776 | copied into a new block that will precede BB, debug bind | |
777 | stmts in bypassed BBs may actually be discarded if | |
778 | they're overwritten by subsequent debug bind stmts, which | |
779 | might be a problem once we introduce stmt frontier notes | |
780 | or somesuch. Adding `&& bb == src' to the condition | |
781 | below will preserve all potentially relevant debug | |
782 | notes. */ | |
9f27dbc3 | 783 | if (vars && pointer_set_insert (vars, var)) |
1ea5fe8f | 784 | continue; |
9f27dbc3 | 785 | else if (!vars) |
786 | { | |
f1f41a6c | 787 | int i = fewvars.length (); |
9f27dbc3 | 788 | while (i--) |
f1f41a6c | 789 | if (fewvars[i] == var) |
9f27dbc3 | 790 | break; |
791 | if (i >= 0) | |
792 | continue; | |
793 | ||
c2496a02 | 794 | if (fewvars.length () < (unsigned) alloc_count) |
f1f41a6c | 795 | fewvars.quick_push (var); |
9f27dbc3 | 796 | else |
797 | { | |
798 | vars = pointer_set_create (); | |
799 | for (i = 0; i < alloc_count; i++) | |
f1f41a6c | 800 | pointer_set_insert (vars, fewvars[i]); |
801 | fewvars.release (); | |
9f27dbc3 | 802 | pointer_set_insert (vars, var); |
803 | } | |
804 | } | |
1ea5fe8f | 805 | |
806 | stmt = gimple_copy (stmt); | |
807 | /* ??? Should we drop the location of the copy to denote | |
808 | they're artificial bindings? */ | |
809 | gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); | |
810 | } | |
811 | } | |
812 | while (bb != src && single_pred_p (bb)); | |
813 | ||
9f27dbc3 | 814 | if (vars) |
815 | pointer_set_destroy (vars); | |
f1f41a6c | 816 | else if (fewvars.exists ()) |
817 | fewvars.release (); | |
1ea5fe8f | 818 | } |
819 | ||
afdb7338 | 820 | /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it |
821 | need not be duplicated as part of the CFG/SSA updating process). | |
822 | ||
823 | If it is threadable, add it to PATH and VISITED and recurse, ultimately | |
824 | returning TRUE from the toplevel call. Otherwise do nothing and | |
825 | return false. | |
826 | ||
827 | DUMMY_COND, HANDLE_DOMINATING_ASSERTS and SIMPLIFY are used to | |
828 | try and simplify the condition at the end of TAKEN_EDGE->dest. */ | |
829 | static bool | |
830 | thread_around_empty_blocks (edge taken_edge, | |
831 | gimple dummy_cond, | |
832 | bool handle_dominating_asserts, | |
833 | tree (*simplify) (gimple, gimple), | |
834 | bitmap visited, | |
f3980d64 | 835 | vec<jump_thread_edge *> *path, |
836 | bool *backedge_seen_p) | |
42b013bc | 837 | { |
838 | basic_block bb = taken_edge->dest; | |
839 | gimple_stmt_iterator gsi; | |
840 | gimple stmt; | |
841 | tree cond; | |
842 | ||
afdb7338 | 843 | /* The key property of these blocks is that they need not be duplicated |
844 | when threading. Thus they can not have visible side effects such | |
845 | as PHI nodes. */ | |
42b013bc | 846 | if (!gsi_end_p (gsi_start_phis (bb))) |
e2b72d6c | 847 | return false; |
42b013bc | 848 | |
849 | /* Skip over DEBUG statements at the start of the block. */ | |
850 | gsi = gsi_start_nondebug_bb (bb); | |
851 | ||
afdb7338 | 852 | /* If the block has no statements, but does have a single successor, then |
f7deb33d | 853 | it's just a forwarding block and we can thread through it trivially. |
bb66e2d1 | 854 | |
855 | However, note that just threading through empty blocks with single | |
856 | successors is not inherently profitable. For the jump thread to | |
857 | be profitable, we must avoid a runtime conditional. | |
858 | ||
859 | By taking the return value from the recursive call, we get the | |
860 | desired effect of returning TRUE when we found a profitable jump | |
f7deb33d | 861 | threading opportunity and FALSE otherwise. |
bb66e2d1 | 862 | |
863 | This is particularly important when this routine is called after | |
864 | processing a joiner block. Returning TRUE too aggressively in | |
865 | that case results in pointless duplication of the joiner block. */ | |
42b013bc | 866 | if (gsi_end_p (gsi)) |
afdb7338 | 867 | { |
868 | if (single_succ_p (bb)) | |
869 | { | |
870 | taken_edge = single_succ_edge (bb); | |
f3980d64 | 871 | if (!bitmap_bit_p (visited, taken_edge->dest->index)) |
afdb7338 | 872 | { |
0c5b289a | 873 | jump_thread_edge *x |
874 | = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); | |
875 | path->safe_push (x); | |
afdb7338 | 876 | bitmap_set_bit (visited, taken_edge->dest->index); |
f3980d64 | 877 | *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); |
c294418d | 878 | if (*backedge_seen_p) |
879 | simplify = dummy_simplify; | |
bb66e2d1 | 880 | return thread_around_empty_blocks (taken_edge, |
881 | dummy_cond, | |
882 | handle_dominating_asserts, | |
883 | simplify, | |
884 | visited, | |
f3980d64 | 885 | path, |
886 | backedge_seen_p); | |
afdb7338 | 887 | } |
888 | } | |
bb66e2d1 | 889 | |
890 | /* We have a block with no statements, but multiple successors? */ | |
afdb7338 | 891 | return false; |
892 | } | |
42b013bc | 893 | |
afdb7338 | 894 | /* The only real statements this block can have are a control |
895 | flow altering statement. Anything else stops the thread. */ | |
42b013bc | 896 | stmt = gsi_stmt (gsi); |
897 | if (gimple_code (stmt) != GIMPLE_COND | |
898 | && gimple_code (stmt) != GIMPLE_GOTO | |
899 | && gimple_code (stmt) != GIMPLE_SWITCH) | |
afdb7338 | 900 | return false; |
42b013bc | 901 | |
c294418d | 902 | /* If we have traversed a backedge, then we do not want to look |
903 | at certain expressions in the table that can not be relied upon. | |
904 | Luckily the only code that looked at those expressions is the | |
905 | SIMPLIFY callback, which we replace if we can no longer use it. */ | |
906 | if (*backedge_seen_p) | |
907 | simplify = dummy_simplify; | |
908 | ||
42b013bc | 909 | /* Extract and simplify the condition. */ |
910 | cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond, | |
911 | simplify, handle_dominating_asserts); | |
912 | ||
913 | /* If the condition can be statically computed and we have not already | |
914 | visited the destination edge, then add the taken edge to our thread | |
915 | path. */ | |
916 | if (cond && is_gimple_min_invariant (cond)) | |
917 | { | |
afdb7338 | 918 | taken_edge = find_taken_edge (bb, cond); |
42b013bc | 919 | |
920 | if (bitmap_bit_p (visited, taken_edge->dest->index)) | |
afdb7338 | 921 | return false; |
42b013bc | 922 | bitmap_set_bit (visited, taken_edge->dest->index); |
0c5b289a | 923 | |
924 | jump_thread_edge *x | |
925 | = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); | |
926 | path->safe_push (x); | |
f3980d64 | 927 | *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); |
c294418d | 928 | if (*backedge_seen_p) |
929 | simplify = dummy_simplify; | |
0c5b289a | 930 | |
afdb7338 | 931 | thread_around_empty_blocks (taken_edge, |
932 | dummy_cond, | |
933 | handle_dominating_asserts, | |
934 | simplify, | |
935 | visited, | |
f3980d64 | 936 | path, |
937 | backedge_seen_p); | |
afdb7338 | 938 | return true; |
42b013bc | 939 | } |
f7deb33d | 940 | |
afdb7338 | 941 | return false; |
42b013bc | 942 | } |
f7deb33d | 943 | |
62b180e1 | 944 | /* We are exiting E->src, see if E->dest ends with a conditional |
48e1416a | 945 | jump which has a known value when reached via E. |
62b180e1 | 946 | |
f7deb33d | 947 | E->dest can have arbitrary side effects which, if threading is |
948 | successful, will be maintained. | |
949 | ||
62b180e1 | 950 | Special care is necessary if E is a back edge in the CFG as we |
951 | may have already recorded equivalences for E->dest into our | |
952 | various tables, including the result of the conditional at | |
953 | the end of E->dest. Threading opportunities are severely | |
954 | limited in that case to avoid short-circuiting the loop | |
955 | incorrectly. | |
956 | ||
d8a0d6b8 | 957 | DUMMY_COND is a shared cond_expr used by condition simplification as scratch, |
958 | to avoid allocating memory. | |
48e1416a | 959 | |
d8a0d6b8 | 960 | HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of |
961 | the simplified condition with left-hand sides of ASSERT_EXPRs they are | |
962 | used in. | |
48e1416a | 963 | |
d8a0d6b8 | 964 | STACK is used to undo temporary equivalences created during the walk of |
965 | E->dest. | |
966 | ||
f7deb33d | 967 | SIMPLIFY is a pass-specific function used to simplify statements. |
62b180e1 | 968 | |
f7deb33d | 969 | Our caller is responsible for restoring the state of the expression |
80ede13b | 970 | and const_and_copies stacks. |
62b180e1 | 971 | |
80ede13b | 972 | Positive return value is success. Zero return value is failure, but |
973 | the block can still be duplicated as a joiner in a jump thread path, | |
974 | negative indicates the block should not be duplicated and thus is not | |
975 | suitable for a joiner in a jump threading path. */ | |
976 | ||
977 | static int | |
f7deb33d | 978 | thread_through_normal_block (edge e, |
979 | gimple dummy_cond, | |
980 | bool handle_dominating_asserts, | |
981 | vec<tree> *stack, | |
982 | tree (*simplify) (gimple, gimple), | |
4bc0f16e | 983 | vec<jump_thread_edge *> *path, |
f3980d64 | 984 | bitmap visited, |
c294418d | 985 | bool *backedge_seen_p, |
986 | bitmap src_map, | |
987 | bitmap dst_map) | |
f7deb33d | 988 | { |
c294418d | 989 | /* If we have traversed a backedge, then we do not want to look |
990 | at certain expressions in the table that can not be relied upon. | |
991 | Luckily the only code that looked at those expressions is the | |
992 | SIMPLIFY callback, which we replace if we can no longer use it. */ | |
993 | if (*backedge_seen_p) | |
994 | simplify = dummy_simplify; | |
48e1416a | 995 | |
62b180e1 | 996 | /* PHIs create temporary equivalences. */ |
c294418d | 997 | if (!record_temporary_equivalences_from_phis (e, stack, *backedge_seen_p, |
998 | src_map, dst_map)) | |
80ede13b | 999 | return 0; |
62b180e1 | 1000 | |
1001 | /* Now walk each statement recording any context sensitive | |
1002 | temporary equivalences we can detect. */ | |
f7deb33d | 1003 | gimple stmt |
c294418d | 1004 | = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify, |
1005 | *backedge_seen_p, | |
1006 | src_map, dst_map); | |
80ede13b | 1007 | |
1008 | /* If we didn't look at all the statements, the most likely reason is | |
1009 | there were too many and thus duplicating this block is not profitable. | |
1010 | ||
1011 | Also note if we do not look at all the statements, then we may not | |
1012 | have invalidated equivalences that are no longer valid if we threaded | |
1013 | around a loop. Thus we must signal to our caller that this block | |
1014 | is not suitable for use as a joiner in a threading path. */ | |
62b180e1 | 1015 | if (!stmt) |
80ede13b | 1016 | return -1; |
62b180e1 | 1017 | |
1018 | /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm | |
1019 | will be taken. */ | |
75a70cf9 | 1020 | if (gimple_code (stmt) == GIMPLE_COND |
1021 | || gimple_code (stmt) == GIMPLE_GOTO | |
1022 | || gimple_code (stmt) == GIMPLE_SWITCH) | |
62b180e1 | 1023 | { |
1024 | tree cond; | |
1025 | ||
1026 | /* Extract and simplify the condition. */ | |
42b013bc | 1027 | cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, |
1028 | handle_dominating_asserts); | |
62b180e1 | 1029 | |
1030 | if (cond && is_gimple_min_invariant (cond)) | |
1031 | { | |
1032 | edge taken_edge = find_taken_edge (e->dest, cond); | |
1033 | basic_block dest = (taken_edge ? taken_edge->dest : NULL); | |
1034 | ||
afdb7338 | 1035 | /* DEST could be NULL for a computed jump to an absolute |
1036 | address. */ | |
f3980d64 | 1037 | if (dest == NULL |
1038 | || dest == e->dest | |
1039 | || bitmap_bit_p (visited, dest->index)) | |
80ede13b | 1040 | return 0; |
62b180e1 | 1041 | |
85309e9d | 1042 | /* Only push the EDGE_START_JUMP_THREAD marker if this is |
1043 | first edge on the path. */ | |
1044 | if (path->length () == 0) | |
1045 | { | |
1046 | jump_thread_edge *x | |
1047 | = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); | |
1048 | path->safe_push (x); | |
1049 | *backedge_seen_p |= ((e->flags & EDGE_DFS_BACK) != 0); | |
1050 | } | |
0c5b289a | 1051 | |
85309e9d | 1052 | jump_thread_edge *x |
1053 | = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK); | |
f2981b08 | 1054 | path->safe_push (x); |
f3980d64 | 1055 | *backedge_seen_p |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); |
c294418d | 1056 | if (*backedge_seen_p) |
1057 | simplify = dummy_simplify; | |
631d940c | 1058 | |
afdb7338 | 1059 | /* See if we can thread through DEST as well, this helps capture |
1060 | secondary effects of threading without having to re-run DOM or | |
c294418d | 1061 | VRP. |
1062 | ||
1063 | We don't want to thread back to a block we have already | |
1064 | visited. This may be overly conservative. */ | |
1065 | bitmap_set_bit (visited, dest->index); | |
1066 | bitmap_set_bit (visited, e->dest->index); | |
1067 | thread_around_empty_blocks (taken_edge, | |
1068 | dummy_cond, | |
1069 | handle_dominating_asserts, | |
1070 | simplify, | |
1071 | visited, | |
1072 | path, | |
1073 | backedge_seen_p); | |
80ede13b | 1074 | return 1; |
62b180e1 | 1075 | } |
1076 | } | |
80ede13b | 1077 | return 0; |
f7deb33d | 1078 | } |
1079 | ||
1080 | /* We are exiting E->src, see if E->dest ends with a conditional | |
1081 | jump which has a known value when reached via E. | |
1082 | ||
1083 | Special care is necessary if E is a back edge in the CFG as we | |
1084 | may have already recorded equivalences for E->dest into our | |
1085 | various tables, including the result of the conditional at | |
1086 | the end of E->dest. Threading opportunities are severely | |
1087 | limited in that case to avoid short-circuiting the loop | |
1088 | incorrectly. | |
1089 | ||
1090 | Note it is quite common for the first block inside a loop to | |
1091 | end with a conditional which is either always true or always | |
1092 | false when reached via the loop backedge. Thus we do not want | |
1093 | to blindly disable threading across a loop backedge. | |
1094 | ||
1095 | DUMMY_COND is a shared cond_expr used by condition simplification as scratch, | |
1096 | to avoid allocating memory. | |
1097 | ||
1098 | HANDLE_DOMINATING_ASSERTS is true if we should try to replace operands of | |
1099 | the simplified condition with left-hand sides of ASSERT_EXPRs they are | |
1100 | used in. | |
1101 | ||
1102 | STACK is used to undo temporary equivalences created during the walk of | |
1103 | E->dest. | |
1104 | ||
1105 | SIMPLIFY is a pass-specific function used to simplify statements. */ | |
1106 | ||
1107 | void | |
1108 | thread_across_edge (gimple dummy_cond, | |
1109 | edge e, | |
1110 | bool handle_dominating_asserts, | |
1111 | vec<tree> *stack, | |
1112 | tree (*simplify) (gimple, gimple)) | |
1113 | { | |
4bc0f16e | 1114 | bitmap visited = BITMAP_ALLOC (NULL); |
c294418d | 1115 | bitmap src_map = BITMAP_ALLOC (NULL); |
1116 | bitmap dst_map = BITMAP_ALLOC (NULL); | |
f3980d64 | 1117 | bool backedge_seen; |
4bc0f16e | 1118 | |
f7deb33d | 1119 | stmt_count = 0; |
1120 | ||
1121 | vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); | |
4bc0f16e | 1122 | bitmap_clear (visited); |
1123 | bitmap_set_bit (visited, e->src->index); | |
1124 | bitmap_set_bit (visited, e->dest->index); | |
f3980d64 | 1125 | backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); |
c294418d | 1126 | if (backedge_seen) |
1127 | simplify = dummy_simplify; | |
1128 | ||
80ede13b | 1129 | int threaded = thread_through_normal_block (e, dummy_cond, |
1130 | handle_dominating_asserts, | |
1131 | stack, simplify, path, | |
1132 | visited, &backedge_seen, | |
1133 | src_map, dst_map); | |
1134 | if (threaded > 0) | |
f7deb33d | 1135 | { |
1136 | propagate_threaded_block_debug_into (path->last ()->e->dest, | |
1137 | e->dest); | |
1138 | remove_temporary_equivalences (stack); | |
4bc0f16e | 1139 | BITMAP_FREE (visited); |
c294418d | 1140 | BITMAP_FREE (src_map); |
1141 | BITMAP_FREE (dst_map); | |
f7deb33d | 1142 | register_jump_thread (path); |
1143 | return; | |
1144 | } | |
1145 | else | |
1146 | { | |
80ede13b | 1147 | /* Negative and zero return values indicate no threading was possible, |
1148 | thus there should be no edges on the thread path and no need to walk | |
1149 | through the vector entries. */ | |
f7deb33d | 1150 | gcc_assert (path->length () == 0); |
1151 | path->release (); | |
80ede13b | 1152 | |
1153 | /* A negative status indicates the target block was deemed too big to | |
1154 | duplicate. Just quit now rather than trying to use the block as | |
1155 | a joiner in a jump threading path. | |
1156 | ||
1157 | This prevents unnecessary code growth, but more importantly if we | |
1158 | do not look at all the statements in the block, then we may have | |
1159 | missed some invalidations if we had traversed a backedge! */ | |
1160 | if (threaded < 0) | |
1161 | { | |
1162 | BITMAP_FREE (visited); | |
1163 | BITMAP_FREE (src_map); | |
1164 | BITMAP_FREE (dst_map); | |
1165 | remove_temporary_equivalences (stack); | |
1166 | return; | |
1167 | } | |
f7deb33d | 1168 | } |
62b180e1 | 1169 | |
da81e0c5 | 1170 | /* We were unable to determine what out edge from E->dest is taken. However, |
1171 | we might still be able to thread through successors of E->dest. This | |
1172 | often occurs when E->dest is a joiner block which then fans back out | |
1173 | based on redundant tests. | |
1174 | ||
1175 | If so, we'll copy E->dest and redirect the appropriate predecessor to | |
1176 | the copy. Within the copy of E->dest, we'll thread one or more edges | |
1177 | to points deeper in the CFG. | |
1178 | ||
1179 | This is a stopgap until we have a more structured approach to path | |
1180 | isolation. */ | |
1181 | { | |
afdb7338 | 1182 | edge taken_edge; |
da81e0c5 | 1183 | edge_iterator ei; |
6da68a0a | 1184 | bool found; |
da81e0c5 | 1185 | |
ed4feca1 | 1186 | /* If E->dest has abnormal outgoing edges, then there's no guarantee |
1187 | we can safely redirect any of the edges. Just punt those cases. */ | |
1188 | FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) | |
1189 | if (taken_edge->flags & EDGE_ABNORMAL) | |
1190 | { | |
1191 | remove_temporary_equivalences (stack); | |
1192 | BITMAP_FREE (visited); | |
c294418d | 1193 | BITMAP_FREE (src_map); |
1194 | BITMAP_FREE (dst_map); | |
ed4feca1 | 1195 | return; |
1196 | } | |
1197 | ||
c294418d | 1198 | /* We need to restore the state of the maps to this point each loop |
1199 | iteration. */ | |
1200 | bitmap src_map_copy = BITMAP_ALLOC (NULL); | |
1201 | bitmap dst_map_copy = BITMAP_ALLOC (NULL); | |
1202 | bitmap_copy (src_map_copy, src_map); | |
1203 | bitmap_copy (dst_map_copy, dst_map); | |
1204 | ||
da81e0c5 | 1205 | /* Look at each successor of E->dest to see if we can thread through it. */ |
1206 | FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) | |
1207 | { | |
1a1e103f | 1208 | /* Push a fresh marker so we can unwind the equivalences created |
1209 | for each of E->dest's successors. */ | |
1210 | stack->safe_push (NULL_TREE); | |
c294418d | 1211 | bitmap_copy (src_map, src_map_copy); |
1212 | bitmap_copy (dst_map, dst_map_copy); | |
1a1e103f | 1213 | |
da81e0c5 | 1214 | /* Avoid threading to any block we have already visited. */ |
1215 | bitmap_clear (visited); | |
baec912e | 1216 | bitmap_set_bit (visited, e->src->index); |
da81e0c5 | 1217 | bitmap_set_bit (visited, e->dest->index); |
baec912e | 1218 | bitmap_set_bit (visited, taken_edge->dest->index); |
f2981b08 | 1219 | vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); |
da81e0c5 | 1220 | |
1221 | /* Record whether or not we were able to thread through a successor | |
1222 | of E->dest. */ | |
0c5b289a | 1223 | jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); |
f2981b08 | 1224 | path->safe_push (x); |
0c5b289a | 1225 | |
1226 | x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK); | |
f2981b08 | 1227 | path->safe_push (x); |
6da68a0a | 1228 | found = false; |
f3980d64 | 1229 | backedge_seen = ((e->flags & EDGE_DFS_BACK) != 0); |
1230 | backedge_seen |= ((taken_edge->flags & EDGE_DFS_BACK) != 0); | |
c294418d | 1231 | if (backedge_seen) |
1232 | simplify = dummy_simplify; | |
1233 | found = thread_around_empty_blocks (taken_edge, | |
1234 | dummy_cond, | |
1235 | handle_dominating_asserts, | |
1236 | simplify, | |
1237 | visited, | |
1238 | path, | |
1239 | &backedge_seen); | |
1240 | ||
1241 | if (backedge_seen) | |
1242 | simplify = dummy_simplify; | |
1243 | ||
1244 | if (!found) | |
559685be | 1245 | found = thread_through_normal_block (path->last ()->e, dummy_cond, |
1246 | handle_dominating_asserts, | |
1247 | stack, simplify, path, visited, | |
c294418d | 1248 | &backedge_seen, |
80ede13b | 1249 | src_map, dst_map) > 0; |
559685be | 1250 | |
da81e0c5 | 1251 | /* If we were able to thread through a successor of E->dest, then |
1252 | record the jump threading opportunity. */ | |
1253 | if (found) | |
1254 | { | |
f2981b08 | 1255 | propagate_threaded_block_debug_into (path->last ()->e->dest, |
b99a7d6d | 1256 | taken_edge->dest); |
0c5b289a | 1257 | register_jump_thread (path); |
da81e0c5 | 1258 | } |
f2981b08 | 1259 | else |
1260 | { | |
6d1fdbf9 | 1261 | delete_jump_thread_path (path); |
f2981b08 | 1262 | } |
1a1e103f | 1263 | |
1264 | /* And unwind the equivalence table. */ | |
1265 | remove_temporary_equivalences (stack); | |
da81e0c5 | 1266 | } |
1267 | BITMAP_FREE (visited); | |
c294418d | 1268 | BITMAP_FREE (src_map); |
1269 | BITMAP_FREE (dst_map); | |
1270 | BITMAP_FREE (src_map_copy); | |
1271 | BITMAP_FREE (dst_map_copy); | |
da81e0c5 | 1272 | } |
1273 | ||
62b180e1 | 1274 | remove_temporary_equivalences (stack); |
1275 | } |