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