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