]>
Commit | Line | Data |
---|---|---|
2090d6a0 | 1 | /* SSA Jump Threading |
8d9254fc | 2 | Copyright (C) 2005-2020 Free Software Foundation, Inc. |
2090d6a0 JL |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
2090d6a0 JL |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
2090d6a0 JL |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
c7131fb2 | 24 | #include "backend.h" |
2090d6a0 | 25 | #include "tree.h" |
c7131fb2 | 26 | #include "gimple.h" |
957060b5 | 27 | #include "predict.h" |
c7131fb2 | 28 | #include "ssa.h" |
40e23961 | 29 | #include "fold-const.h" |
60393bbc | 30 | #include "cfgloop.h" |
5be5c238 | 31 | #include "gimple-iterator.h" |
442b4905 | 32 | #include "tree-cfg.h" |
5254eac4 | 33 | #include "tree-ssa-threadupdate.h" |
f6c72af4 | 34 | #include "tree-ssa-scopedtables.h" |
4484a35a | 35 | #include "tree-ssa-threadedge.h" |
7c3e7056 | 36 | #include "tree-ssa-dom.h" |
1e080ab4 | 37 | #include "gimple-fold.h" |
5c3e5002 | 38 | #include "cfganal.h" |
df80fc53 JL |
39 | #include "alloc-pool.h" |
40 | #include "vr-values.h" | |
41 | #include "gimple-ssa-evrp-analyze.h" | |
2090d6a0 JL |
42 | |
43 | /* To avoid code explosion due to jump threading, we limit the | |
44 | number of statements we are going to copy. This variable | |
45 | holds the number of statements currently seen that we'll have | |
46 | to copy as part of the jump threading process. */ | |
47 | static int stmt_count; | |
48 | ||
448ee662 | 49 | /* Array to record value-handles per SSA_NAME. */ |
9771b263 | 50 | vec<tree> ssa_name_values; |
448ee662 | 51 | |
8d7437be JL |
52 | typedef tree (pfn_simplify) (gimple *, gimple *, |
53 | class avail_exprs_stack *, | |
54 | basic_block); | |
8e33db8f | 55 | |
448ee662 RG |
56 | /* Set the value for the SSA name NAME to VALUE. */ |
57 | ||
58 | void | |
59 | set_ssa_name_value (tree name, tree value) | |
60 | { | |
9771b263 DN |
61 | if (SSA_NAME_VERSION (name) >= ssa_name_values.length ()) |
62 | ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1); | |
846abd0d RB |
63 | if (value && TREE_OVERFLOW_P (value)) |
64 | value = drop_tree_overflow (value); | |
9771b263 | 65 | ssa_name_values[SSA_NAME_VERSION (name)] = value; |
448ee662 RG |
66 | } |
67 | ||
68 | /* Initialize the per SSA_NAME value-handles array. Returns it. */ | |
69 | void | |
70 | threadedge_initialize_values (void) | |
71 | { | |
9771b263 DN |
72 | gcc_assert (!ssa_name_values.exists ()); |
73 | ssa_name_values.create (num_ssa_names); | |
448ee662 RG |
74 | } |
75 | ||
76 | /* Free the per SSA_NAME value-handle array. */ | |
77 | void | |
78 | threadedge_finalize_values (void) | |
79 | { | |
9771b263 | 80 | ssa_name_values.release (); |
448ee662 RG |
81 | } |
82 | ||
2090d6a0 JL |
83 | /* Return TRUE if we may be able to thread an incoming edge into |
84 | BB to an outgoing edge from BB. Return FALSE otherwise. */ | |
85 | ||
86 | bool | |
87 | potentially_threadable_block (basic_block bb) | |
88 | { | |
726a989a | 89 | gimple_stmt_iterator gsi; |
2090d6a0 | 90 | |
215f8d9e JL |
91 | /* Special case. We can get blocks that are forwarders, but are |
92 | not optimized away because they forward from outside a loop | |
93 | to the loop header. We want to thread through them as we can | |
1b2fe7d3 | 94 | sometimes thread to the loop exit, which is obviously profitable. |
215f8d9e JL |
95 | the interesting case here is when the block has PHIs. */ |
96 | if (gsi_end_p (gsi_start_nondebug_bb (bb)) | |
97 | && !gsi_end_p (gsi_start_phis (bb))) | |
98 | return true; | |
1b2fe7d3 | 99 | |
2090d6a0 JL |
100 | /* If BB has a single successor or a single predecessor, then |
101 | there is no threading opportunity. */ | |
102 | if (single_succ_p (bb) || single_pred_p (bb)) | |
103 | return false; | |
104 | ||
105 | /* If BB does not end with a conditional, switch or computed goto, | |
106 | then there is no threading opportunity. */ | |
726a989a RB |
107 | gsi = gsi_last_bb (bb); |
108 | if (gsi_end_p (gsi) | |
109 | || ! gsi_stmt (gsi) | |
110 | || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND | |
111 | && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO | |
112 | && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH)) | |
2090d6a0 JL |
113 | return false; |
114 | ||
115 | return true; | |
116 | } | |
117 | ||
2090d6a0 | 118 | /* Record temporary equivalences created by PHIs at the target of the |
df80fc53 JL |
119 | edge E. Record unwind information for the equivalences into |
120 | CONST_AND_COPIES and EVRP_RANGE_DATA. | |
2090d6a0 JL |
121 | |
122 | If a PHI which prevents threading is encountered, then return FALSE | |
df80fc53 | 123 | indicating we should not thread this edge, else return TRUE. */ |
2090d6a0 JL |
124 | |
125 | static bool | |
df80fc53 JL |
126 | record_temporary_equivalences_from_phis (edge e, |
127 | const_and_copies *const_and_copies, | |
128 | evrp_range_analyzer *evrp_range_analyzer) | |
2090d6a0 | 129 | { |
538dd0b7 | 130 | gphi_iterator gsi; |
2090d6a0 JL |
131 | |
132 | /* Each PHI creates a temporary equivalence, record them. | |
133 | These are context sensitive equivalences and will be removed | |
134 | later. */ | |
726a989a | 135 | for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
2090d6a0 | 136 | { |
538dd0b7 | 137 | gphi *phi = gsi.phi (); |
2090d6a0 | 138 | tree src = PHI_ARG_DEF_FROM_EDGE (phi, e); |
726a989a | 139 | tree dst = gimple_phi_result (phi); |
2090d6a0 | 140 | |
b8698a0f | 141 | /* If the desired argument is not the same as this PHI's result |
67914693 | 142 | and it is set by a PHI in E->dest, then we cannot thread |
2090d6a0 JL |
143 | through E->dest. */ |
144 | if (src != dst | |
145 | && TREE_CODE (src) == SSA_NAME | |
726a989a RB |
146 | && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI |
147 | && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest) | |
2090d6a0 JL |
148 | return false; |
149 | ||
150 | /* We consider any non-virtual PHI as a statement since it | |
151 | count result in a constant assignment or copy operation. */ | |
ea057359 | 152 | if (!virtual_operand_p (dst)) |
2090d6a0 JL |
153 | stmt_count++; |
154 | ||
f6c72af4 | 155 | const_and_copies->record_const_or_copy (dst, src); |
df80fc53 JL |
156 | |
157 | /* Also update the value range associated with DST, using | |
72de3b78 JL |
158 | the range from SRC. |
159 | ||
160 | Note that even if SRC is a constant we need to set a suitable | |
161 | output range so that VR_UNDEFINED ranges do not leak through. */ | |
162 | if (evrp_range_analyzer) | |
df80fc53 | 163 | { |
72de3b78 JL |
164 | /* Get an empty new VR we can pass to update_value_range and save |
165 | away in the VR stack. */ | |
166 | vr_values *vr_values = evrp_range_analyzer->get_vr_values (); | |
028d81b1 AH |
167 | value_range_equiv *new_vr = vr_values->allocate_value_range_equiv (); |
168 | new (new_vr) value_range_equiv (); | |
72de3b78 JL |
169 | |
170 | /* There are three cases to consider: | |
171 | ||
172 | First if SRC is an SSA_NAME, then we can copy the value | |
173 | range from SRC into NEW_VR. | |
174 | ||
175 | Second if SRC is an INTEGER_CST, then we can just wet | |
176 | NEW_VR to a singleton range. | |
177 | ||
178 | Otherwise set NEW_VR to varying. This may be overly | |
179 | conservative. */ | |
180 | if (TREE_CODE (src) == SSA_NAME) | |
54994253 | 181 | new_vr->deep_copy (vr_values->get_value_range (src)); |
72de3b78 | 182 | else if (TREE_CODE (src) == INTEGER_CST) |
27922d51 | 183 | new_vr->set (src); |
72de3b78 | 184 | else |
97ecc8d5 | 185 | new_vr->set_varying (TREE_TYPE (src)); |
72de3b78 JL |
186 | |
187 | /* This is a temporary range for DST, so push it. */ | |
188 | evrp_range_analyzer->push_value_range (dst, new_vr); | |
df80fc53 | 189 | } |
2090d6a0 JL |
190 | } |
191 | return true; | |
192 | } | |
193 | ||
1e080ab4 | 194 | /* Valueize hook for gimple_fold_stmt_to_constant_1. */ |
726a989a RB |
195 | |
196 | static tree | |
1e080ab4 | 197 | threadedge_valueize (tree t) |
726a989a | 198 | { |
1e080ab4 | 199 | if (TREE_CODE (t) == SSA_NAME) |
726a989a | 200 | { |
1e080ab4 RB |
201 | tree tem = SSA_NAME_VALUE (t); |
202 | if (tem) | |
203 | return tem; | |
726a989a | 204 | } |
1e080ab4 | 205 | return t; |
726a989a RB |
206 | } |
207 | ||
2090d6a0 JL |
208 | /* Try to simplify each statement in E->dest, ultimately leading to |
209 | a simplification of the COND_EXPR at the end of E->dest. | |
210 | ||
211 | Record unwind information for temporary equivalences onto STACK. | |
212 | ||
213 | Use SIMPLIFY (a pointer to a callback function) to further simplify | |
b8698a0f | 214 | statements using pass specific information. |
2090d6a0 JL |
215 | |
216 | We might consider marking just those statements which ultimately | |
217 | feed the COND_EXPR. It's not clear if the overhead of bookkeeping | |
218 | would be recovered by trying to simplify fewer statements. | |
219 | ||
220 | If we are able to simplify a statement into the form | |
221 | SSA_NAME = (SSA_NAME | gimple invariant), then we can record | |
726a989a | 222 | a context sensitive equivalence which may help us simplify |
2090d6a0 JL |
223 | later statements in E->dest. */ |
224 | ||
355fe088 | 225 | static gimple * |
2090d6a0 | 226 | record_temporary_equivalences_from_stmts_at_dest (edge e, |
8e33db8f JL |
227 | const_and_copies *const_and_copies, |
228 | avail_exprs_stack *avail_exprs_stack, | |
df80fc53 | 229 | evrp_range_analyzer *evrp_range_analyzer, |
334b4842 | 230 | pfn_simplify simplify) |
2090d6a0 | 231 | { |
355fe088 | 232 | gimple *stmt = NULL; |
726a989a | 233 | gimple_stmt_iterator gsi; |
2090d6a0 JL |
234 | int max_stmt_count; |
235 | ||
028d4092 | 236 | max_stmt_count = param_max_jump_thread_duplication_stmts; |
2090d6a0 JL |
237 | |
238 | /* Walk through each statement in the block recording equivalences | |
239 | we discover. Note any equivalences we discover are context | |
240 | sensitive (ie, are dependent on traversing E) and must be unwound | |
241 | when we're finished processing E. */ | |
726a989a | 242 | for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
2090d6a0 JL |
243 | { |
244 | tree cached_lhs = NULL; | |
245 | ||
726a989a | 246 | stmt = gsi_stmt (gsi); |
2090d6a0 JL |
247 | |
248 | /* Ignore empty statements and labels. */ | |
b5b8b0ac AO |
249 | if (gimple_code (stmt) == GIMPLE_NOP |
250 | || gimple_code (stmt) == GIMPLE_LABEL | |
251 | || is_gimple_debug (stmt)) | |
2090d6a0 JL |
252 | continue; |
253 | ||
2090d6a0 | 254 | /* If the statement has volatile operands, then we assume we |
67914693 | 255 | cannot thread through this block. This is overly |
2090d6a0 | 256 | conservative in some ways. */ |
538dd0b7 DM |
257 | if (gimple_code (stmt) == GIMPLE_ASM |
258 | && gimple_asm_volatile_p (as_a <gasm *> (stmt))) | |
2090d6a0 JL |
259 | return NULL; |
260 | ||
67914693 | 261 | /* If the statement is a unique builtin, we cannot thread |
8ab78162 NS |
262 | through here. */ |
263 | if (gimple_code (stmt) == GIMPLE_CALL | |
264 | && gimple_call_internal_p (stmt) | |
265 | && gimple_call_internal_unique_p (stmt)) | |
266 | return NULL; | |
267 | ||
2090d6a0 JL |
268 | /* If duplicating this block is going to cause too much code |
269 | expansion, then do not thread through this block. */ | |
270 | stmt_count++; | |
271 | if (stmt_count > max_stmt_count) | |
5806e062 JL |
272 | { |
273 | /* If any of the stmts in the PATH's dests are going to be | |
274 | killed due to threading, grow the max count | |
275 | accordingly. */ | |
276 | if (max_stmt_count | |
028d4092 | 277 | == param_max_jump_thread_duplication_stmts) |
5806e062 JL |
278 | { |
279 | max_stmt_count += estimate_threading_killed_stmts (e->dest); | |
280 | if (dump_file) | |
281 | fprintf (dump_file, "threading bb %i up to %i stmts\n", | |
282 | e->dest->index, max_stmt_count); | |
283 | } | |
284 | /* If we're still past the limit, we're done. */ | |
285 | if (stmt_count > max_stmt_count) | |
286 | return NULL; | |
287 | } | |
2090d6a0 | 288 | |
df80fc53 JL |
289 | /* These are temporary ranges, do nto reflect them back into |
290 | the global range data. */ | |
291 | if (evrp_range_analyzer) | |
292 | evrp_range_analyzer->record_ranges_from_stmt (stmt, true); | |
293 | ||
726a989a | 294 | /* If this is not a statement that sets an SSA_NAME to a new |
2090d6a0 JL |
295 | value, then do not try to simplify this statement as it will |
296 | not simplify in any way that is helpful for jump threading. */ | |
726a989a RB |
297 | if ((gimple_code (stmt) != GIMPLE_ASSIGN |
298 | || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) | |
299 | && (gimple_code (stmt) != GIMPLE_CALL | |
300 | || gimple_call_lhs (stmt) == NULL_TREE | |
301 | || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME)) | |
334b4842 | 302 | continue; |
2090d6a0 | 303 | |
45e18420 RAE |
304 | /* The result of __builtin_object_size depends on all the arguments |
305 | of a phi node. Temporarily using only one edge produces invalid | |
306 | results. For example | |
307 | ||
308 | if (x < 6) | |
309 | goto l; | |
310 | else | |
311 | goto l; | |
312 | ||
313 | l: | |
314 | r = PHI <&w[2].a[1](2), &a.a[6](3)> | |
315 | __builtin_object_size (r, 0) | |
316 | ||
317 | The result of __builtin_object_size is defined to be the maximum of | |
318 | remaining bytes. If we use only one edge on the phi, the result will | |
56c6a499 JJ |
319 | change to be the remaining bytes for the corresponding phi argument. |
320 | ||
321 | Similarly for __builtin_constant_p: | |
322 | ||
323 | r = PHI <1(2), 2(3)> | |
324 | __builtin_constant_p (r) | |
325 | ||
326 | Both PHI arguments are constant, but x ? 1 : 2 is still not | |
327 | constant. */ | |
45e18420 | 328 | |
726a989a | 329 | if (is_gimple_call (stmt)) |
45e18420 | 330 | { |
726a989a | 331 | tree fndecl = gimple_call_fndecl (stmt); |
56c6a499 | 332 | if (fndecl |
cb1180d5 | 333 | && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL) |
56c6a499 JJ |
334 | && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE |
335 | || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)) | |
334b4842 | 336 | continue; |
45e18420 RAE |
337 | } |
338 | ||
2090d6a0 JL |
339 | /* At this point we have a statement which assigns an RHS to an |
340 | SSA_VAR on the LHS. We want to try and simplify this statement | |
341 | to expose more context sensitive equivalences which in turn may | |
b8698a0f | 342 | allow us to simplify the condition at the end of the loop. |
2090d6a0 JL |
343 | |
344 | Handle simple copy operations as well as implied copies from | |
345 | ASSERT_EXPRs. */ | |
726a989a RB |
346 | if (gimple_assign_single_p (stmt) |
347 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) | |
348 | cached_lhs = gimple_assign_rhs1 (stmt); | |
349 | else if (gimple_assign_single_p (stmt) | |
350 | && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR) | |
351 | cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); | |
2090d6a0 JL |
352 | else |
353 | { | |
354 | /* A statement that is not a trivial copy or ASSERT_EXPR. | |
1e080ab4 | 355 | Try to fold the new expression. Inserting the |
726a989a | 356 | expression into the hash table is unlikely to help. */ |
1e080ab4 RB |
357 | /* ??? The DOM callback below can be changed to setting |
358 | the mprts_hook around the call to thread_across_edge, | |
359 | avoiding the use substitution. The VRP hook should be | |
360 | changed to properly valueize operands itself using | |
361 | SSA_NAME_VALUE in addition to its own lattice. */ | |
362 | cached_lhs = gimple_fold_stmt_to_constant_1 (stmt, | |
363 | threadedge_valueize); | |
b06496b1 JL |
364 | if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0 |
365 | && (!cached_lhs | |
366 | || (TREE_CODE (cached_lhs) != SSA_NAME | |
367 | && !is_gimple_min_invariant (cached_lhs)))) | |
1e080ab4 RB |
368 | { |
369 | /* We're going to temporarily copy propagate the operands | |
370 | and see if that allows us to simplify this statement. */ | |
371 | tree *copy; | |
372 | ssa_op_iter iter; | |
373 | use_operand_p use_p; | |
374 | unsigned int num, i = 0; | |
375 | ||
376 | num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES); | |
377 | copy = XALLOCAVEC (tree, num); | |
378 | ||
379 | /* Make a copy of the uses & vuses into USES_COPY, then cprop into | |
380 | the operands. */ | |
381 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
382 | { | |
383 | tree tmp = NULL; | |
384 | tree use = USE_FROM_PTR (use_p); | |
385 | ||
386 | copy[i++] = use; | |
387 | if (TREE_CODE (use) == SSA_NAME) | |
388 | tmp = SSA_NAME_VALUE (use); | |
389 | if (tmp) | |
390 | SET_USE (use_p, tmp); | |
391 | } | |
b8698a0f | 392 | |
8d7437be | 393 | cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src); |
2090d6a0 | 394 | |
1e080ab4 RB |
395 | /* Restore the statement's original uses/defs. */ |
396 | i = 0; | |
397 | FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) | |
398 | SET_USE (use_p, copy[i++]); | |
399 | } | |
2090d6a0 JL |
400 | } |
401 | ||
402 | /* Record the context sensitive equivalence if we were able | |
334b4842 | 403 | to simplify this statement. */ |
2090d6a0 JL |
404 | if (cached_lhs |
405 | && (TREE_CODE (cached_lhs) == SSA_NAME | |
406 | || is_gimple_min_invariant (cached_lhs))) | |
a12cbc57 JL |
407 | const_and_copies->record_const_or_copy (gimple_get_lhs (stmt), |
408 | cached_lhs); | |
2090d6a0 JL |
409 | } |
410 | return stmt; | |
411 | } | |
412 | ||
5a956111 PP |
413 | static tree simplify_control_stmt_condition_1 (edge, gimple *, |
414 | class avail_exprs_stack *, | |
415 | tree, enum tree_code, tree, | |
8d7437be | 416 | gcond *, pfn_simplify, |
5a956111 PP |
417 | unsigned); |
418 | ||
2090d6a0 JL |
419 | /* Simplify the control statement at the end of the block E->dest. |
420 | ||
726a989a | 421 | To avoid allocating memory unnecessarily, a scratch GIMPLE_COND |
2090d6a0 JL |
422 | is available to use/clobber in DUMMY_COND. |
423 | ||
424 | Use SIMPLIFY (a pointer to a callback function) to further simplify | |
425 | a condition using pass specific information. | |
426 | ||
427 | Return the simplified condition or NULL if simplification could | |
5c3e5002 PP |
428 | not be performed. When simplifying a GIMPLE_SWITCH, we may return |
429 | the CASE_LABEL_EXPR that will be taken. | |
8e33db8f JL |
430 | |
431 | The available expression table is referenced via AVAIL_EXPRS_STACK. */ | |
2090d6a0 JL |
432 | |
433 | static tree | |
434 | simplify_control_stmt_condition (edge e, | |
355fe088 | 435 | gimple *stmt, |
8e33db8f | 436 | class avail_exprs_stack *avail_exprs_stack, |
538dd0b7 | 437 | gcond *dummy_cond, |
8d7437be | 438 | pfn_simplify simplify) |
2090d6a0 JL |
439 | { |
440 | tree cond, cached_lhs; | |
726a989a | 441 | enum gimple_code code = gimple_code (stmt); |
2090d6a0 JL |
442 | |
443 | /* For comparisons, we have to update both operands, then try | |
444 | to simplify the comparison. */ | |
726a989a | 445 | if (code == GIMPLE_COND) |
2090d6a0 JL |
446 | { |
447 | tree op0, op1; | |
448 | enum tree_code cond_code; | |
449 | ||
726a989a RB |
450 | op0 = gimple_cond_lhs (stmt); |
451 | op1 = gimple_cond_rhs (stmt); | |
452 | cond_code = gimple_cond_code (stmt); | |
2090d6a0 JL |
453 | |
454 | /* Get the current value of both operands. */ | |
455 | if (TREE_CODE (op0) == SSA_NAME) | |
456 | { | |
4f82fed2 JL |
457 | for (int i = 0; i < 2; i++) |
458 | { | |
459 | if (TREE_CODE (op0) == SSA_NAME | |
460 | && SSA_NAME_VALUE (op0)) | |
461 | op0 = SSA_NAME_VALUE (op0); | |
462 | else | |
463 | break; | |
464 | } | |
2090d6a0 JL |
465 | } |
466 | ||
467 | if (TREE_CODE (op1) == SSA_NAME) | |
468 | { | |
4f82fed2 JL |
469 | for (int i = 0; i < 2; i++) |
470 | { | |
471 | if (TREE_CODE (op1) == SSA_NAME | |
472 | && SSA_NAME_VALUE (op1)) | |
473 | op1 = SSA_NAME_VALUE (op1); | |
474 | else | |
475 | break; | |
476 | } | |
2090d6a0 JL |
477 | } |
478 | ||
5a956111 | 479 | const unsigned recursion_limit = 4; |
2090d6a0 | 480 | |
5a956111 PP |
481 | cached_lhs |
482 | = simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack, | |
483 | op0, cond_code, op1, | |
484 | dummy_cond, simplify, | |
5a956111 | 485 | recursion_limit); |
726a989a | 486 | |
3d466672 JL |
487 | /* If we were testing an integer/pointer against a constant, then |
488 | we can use the FSM code to trace the value of the SSA_NAME. If | |
489 | a value is found, then the condition will collapse to a constant. | |
490 | ||
491 | Return the SSA_NAME we want to trace back rather than the full | |
492 | expression and give the FSM threader a chance to find its value. */ | |
493 | if (cached_lhs == NULL) | |
636351f9 JL |
494 | { |
495 | /* Recover the original operands. They may have been simplified | |
496 | using context sensitive equivalences. Those context sensitive | |
497 | equivalences may not be valid on paths found by the FSM optimizer. */ | |
498 | tree op0 = gimple_cond_lhs (stmt); | |
499 | tree op1 = gimple_cond_rhs (stmt); | |
500 | ||
3d466672 JL |
501 | if ((INTEGRAL_TYPE_P (TREE_TYPE (op0)) |
502 | || POINTER_TYPE_P (TREE_TYPE (op0))) | |
636351f9 | 503 | && TREE_CODE (op0) == SSA_NAME |
3d466672 | 504 | && TREE_CODE (op1) == INTEGER_CST) |
636351f9 JL |
505 | return op0; |
506 | } | |
507 | ||
726a989a | 508 | return cached_lhs; |
2090d6a0 JL |
509 | } |
510 | ||
726a989a | 511 | if (code == GIMPLE_SWITCH) |
538dd0b7 | 512 | cond = gimple_switch_index (as_a <gswitch *> (stmt)); |
726a989a RB |
513 | else if (code == GIMPLE_GOTO) |
514 | cond = gimple_goto_dest (stmt); | |
515 | else | |
516 | gcc_unreachable (); | |
517 | ||
2090d6a0 JL |
518 | /* We can have conditionals which just test the state of a variable |
519 | rather than use a relational operator. These are simpler to handle. */ | |
726a989a | 520 | if (TREE_CODE (cond) == SSA_NAME) |
2090d6a0 | 521 | { |
50e9ff83 | 522 | tree original_lhs = cond; |
2090d6a0 JL |
523 | cached_lhs = cond; |
524 | ||
726a989a | 525 | /* Get the variable's current value from the equivalence chains. |
61864771 JL |
526 | |
527 | It is possible to get loops in the SSA_NAME_VALUE chains | |
528 | (consider threading the backedge of a loop where we have | |
21f0717a | 529 | a loop invariant SSA_NAME used in the condition). */ |
4f82fed2 JL |
530 | if (cached_lhs) |
531 | { | |
532 | for (int i = 0; i < 2; i++) | |
533 | { | |
534 | if (TREE_CODE (cached_lhs) == SSA_NAME | |
535 | && SSA_NAME_VALUE (cached_lhs)) | |
536 | cached_lhs = SSA_NAME_VALUE (cached_lhs); | |
537 | else | |
538 | break; | |
539 | } | |
540 | } | |
2090d6a0 | 541 | |
2090d6a0 JL |
542 | /* If we haven't simplified to an invariant yet, then use the |
543 | pass specific callback to try and simplify it further. */ | |
544 | if (cached_lhs && ! is_gimple_min_invariant (cached_lhs)) | |
5c3e5002 | 545 | { |
8d7437be | 546 | if (code == GIMPLE_SWITCH) |
5c3e5002 | 547 | { |
8d7437be JL |
548 | /* Replace the index operand of the GIMPLE_SWITCH with any LHS |
549 | we found before handing off to VRP. If simplification is | |
550 | possible, the simplified value will be a CASE_LABEL_EXPR of | |
551 | the label that is proven to be taken. */ | |
5c3e5002 PP |
552 | gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt)); |
553 | gimple_switch_set_index (dummy_switch, cached_lhs); | |
8d7437be JL |
554 | cached_lhs = (*simplify) (dummy_switch, stmt, |
555 | avail_exprs_stack, e->src); | |
5c3e5002 PP |
556 | ggc_free (dummy_switch); |
557 | } | |
558 | else | |
8d7437be | 559 | cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src); |
5c3e5002 | 560 | } |
50e9ff83 JG |
561 | |
562 | /* We couldn't find an invariant. But, callers of this | |
563 | function may be able to do something useful with the | |
564 | unmodified destination. */ | |
565 | if (!cached_lhs) | |
566 | cached_lhs = original_lhs; | |
2090d6a0 JL |
567 | } |
568 | else | |
569 | cached_lhs = NULL; | |
570 | ||
571 | return cached_lhs; | |
572 | } | |
573 | ||
5a956111 PP |
574 | /* Recursive helper for simplify_control_stmt_condition. */ |
575 | ||
576 | static tree | |
577 | simplify_control_stmt_condition_1 (edge e, | |
578 | gimple *stmt, | |
579 | class avail_exprs_stack *avail_exprs_stack, | |
580 | tree op0, | |
581 | enum tree_code cond_code, | |
582 | tree op1, | |
583 | gcond *dummy_cond, | |
584 | pfn_simplify simplify, | |
5a956111 PP |
585 | unsigned limit) |
586 | { | |
587 | if (limit == 0) | |
588 | return NULL_TREE; | |
589 | ||
590 | /* We may need to canonicalize the comparison. For | |
591 | example, op0 might be a constant while op1 is an | |
592 | SSA_NAME. Failure to canonicalize will cause us to | |
593 | miss threading opportunities. */ | |
14e72812 | 594 | if (tree_swap_operands_p (op0, op1)) |
5a956111 PP |
595 | { |
596 | cond_code = swap_tree_comparison (cond_code); | |
597 | std::swap (op0, op1); | |
598 | } | |
599 | ||
600 | /* If the condition has the form (A & B) CMP 0 or (A | B) CMP 0 then | |
601 | recurse into the LHS to see if there is a dominating ASSERT_EXPR | |
602 | of A or of B that makes this condition always true or always false | |
603 | along the edge E. */ | |
8d7437be | 604 | if ((cond_code == EQ_EXPR || cond_code == NE_EXPR) |
5a956111 PP |
605 | && TREE_CODE (op0) == SSA_NAME |
606 | && integer_zerop (op1)) | |
607 | { | |
608 | gimple *def_stmt = SSA_NAME_DEF_STMT (op0); | |
609 | if (gimple_code (def_stmt) != GIMPLE_ASSIGN) | |
610 | ; | |
611 | else if (gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR | |
612 | || gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR) | |
613 | { | |
614 | enum tree_code rhs_code = gimple_assign_rhs_code (def_stmt); | |
615 | const tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
616 | const tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
5a956111 PP |
617 | |
618 | /* Is A != 0 ? */ | |
619 | const tree res1 | |
620 | = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, | |
621 | rhs1, NE_EXPR, op1, | |
622 | dummy_cond, simplify, | |
5a956111 PP |
623 | limit - 1); |
624 | if (res1 == NULL_TREE) | |
625 | ; | |
626 | else if (rhs_code == BIT_AND_EXPR && integer_zerop (res1)) | |
627 | { | |
628 | /* If A == 0 then (A & B) != 0 is always false. */ | |
629 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 630 | return boolean_false_node; |
5a956111 PP |
631 | /* If A == 0 then (A & B) == 0 is always true. */ |
632 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 633 | return boolean_true_node; |
5a956111 PP |
634 | } |
635 | else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res1)) | |
636 | { | |
637 | /* If A != 0 then (A | B) != 0 is always true. */ | |
638 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 639 | return boolean_true_node; |
5a956111 PP |
640 | /* If A != 0 then (A | B) == 0 is always false. */ |
641 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 642 | return boolean_false_node; |
5a956111 PP |
643 | } |
644 | ||
645 | /* Is B != 0 ? */ | |
646 | const tree res2 | |
647 | = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, | |
648 | rhs2, NE_EXPR, op1, | |
649 | dummy_cond, simplify, | |
5a956111 PP |
650 | limit - 1); |
651 | if (res2 == NULL_TREE) | |
652 | ; | |
653 | else if (rhs_code == BIT_AND_EXPR && integer_zerop (res2)) | |
654 | { | |
655 | /* If B == 0 then (A & B) != 0 is always false. */ | |
656 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 657 | return boolean_false_node; |
5a956111 PP |
658 | /* If B == 0 then (A & B) == 0 is always true. */ |
659 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 660 | return boolean_true_node; |
5a956111 PP |
661 | } |
662 | else if (rhs_code == BIT_IOR_EXPR && integer_nonzerop (res2)) | |
663 | { | |
664 | /* If B != 0 then (A | B) != 0 is always true. */ | |
665 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 666 | return boolean_true_node; |
5a956111 PP |
667 | /* If B != 0 then (A | B) == 0 is always false. */ |
668 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 669 | return boolean_false_node; |
5a956111 PP |
670 | } |
671 | ||
672 | if (res1 != NULL_TREE && res2 != NULL_TREE) | |
673 | { | |
674 | if (rhs_code == BIT_AND_EXPR | |
675 | && TYPE_PRECISION (TREE_TYPE (op0)) == 1 | |
676 | && integer_nonzerop (res1) | |
677 | && integer_nonzerop (res2)) | |
678 | { | |
679 | /* If A != 0 and B != 0 then (bool)(A & B) != 0 is true. */ | |
680 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 681 | return boolean_true_node; |
5a956111 PP |
682 | /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */ |
683 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 684 | return boolean_false_node; |
5a956111 PP |
685 | } |
686 | ||
687 | if (rhs_code == BIT_IOR_EXPR | |
688 | && integer_zerop (res1) | |
689 | && integer_zerop (res2)) | |
690 | { | |
691 | /* If A == 0 and B == 0 then (A | B) != 0 is false. */ | |
692 | if (cond_code == NE_EXPR) | |
ff66f6e8 | 693 | return boolean_false_node; |
5a956111 PP |
694 | /* If A == 0 and B == 0 then (A | B) == 0 is true. */ |
695 | if (cond_code == EQ_EXPR) | |
ff66f6e8 | 696 | return boolean_true_node; |
5a956111 PP |
697 | } |
698 | } | |
699 | } | |
700 | /* Handle (A CMP B) CMP 0. */ | |
701 | else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) | |
702 | == tcc_comparison) | |
703 | { | |
704 | tree rhs1 = gimple_assign_rhs1 (def_stmt); | |
705 | tree rhs2 = gimple_assign_rhs2 (def_stmt); | |
706 | ||
707 | tree_code new_cond = gimple_assign_rhs_code (def_stmt); | |
708 | if (cond_code == EQ_EXPR) | |
709 | new_cond = invert_tree_comparison (new_cond, false); | |
710 | ||
711 | tree res | |
712 | = simplify_control_stmt_condition_1 (e, def_stmt, avail_exprs_stack, | |
713 | rhs1, new_cond, rhs2, | |
714 | dummy_cond, simplify, | |
5a956111 PP |
715 | limit - 1); |
716 | if (res != NULL_TREE && is_gimple_min_invariant (res)) | |
717 | return res; | |
718 | } | |
719 | } | |
720 | ||
5a956111 PP |
721 | gimple_cond_set_code (dummy_cond, cond_code); |
722 | gimple_cond_set_lhs (dummy_cond, op0); | |
723 | gimple_cond_set_rhs (dummy_cond, op1); | |
724 | ||
725 | /* We absolutely do not care about any type conversions | |
726 | we only care about a zero/nonzero value. */ | |
727 | fold_defer_overflow_warnings (); | |
728 | ||
729 | tree res = fold_binary (cond_code, boolean_type_node, op0, op1); | |
730 | if (res) | |
731 | while (CONVERT_EXPR_P (res)) | |
732 | res = TREE_OPERAND (res, 0); | |
733 | ||
734 | fold_undefer_overflow_warnings ((res && is_gimple_min_invariant (res)), | |
735 | stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); | |
736 | ||
737 | /* If we have not simplified the condition down to an invariant, | |
738 | then use the pass specific callback to simplify the condition. */ | |
739 | if (!res | |
740 | || !is_gimple_min_invariant (res)) | |
8d7437be | 741 | res = (*simplify) (dummy_cond, stmt, avail_exprs_stack, e->src); |
5a956111 PP |
742 | |
743 | return res; | |
744 | } | |
745 | ||
447a7045 AO |
746 | /* Copy debug stmts from DEST's chain of single predecessors up to |
747 | SRC, so that we don't lose the bindings as PHI nodes are introduced | |
748 | when DEST gains new predecessors. */ | |
6e02b5f5 | 749 | void |
447a7045 AO |
750 | propagate_threaded_block_debug_into (basic_block dest, basic_block src) |
751 | { | |
36f52e8f | 752 | if (!MAY_HAVE_DEBUG_BIND_STMTS) |
447a7045 AO |
753 | return; |
754 | ||
755 | if (!single_pred_p (dest)) | |
756 | return; | |
757 | ||
758 | gcc_checking_assert (dest != src); | |
759 | ||
760 | gimple_stmt_iterator gsi = gsi_after_labels (dest); | |
fe77e0ed AO |
761 | int i = 0; |
762 | const int alloc_count = 16; // ?? Should this be a PARAM? | |
447a7045 | 763 | |
fe77e0ed AO |
764 | /* Estimate the number of debug vars overridden in the beginning of |
765 | DEST, to tell how many we're going to need to begin with. */ | |
447a7045 | 766 | for (gimple_stmt_iterator si = gsi; |
fe77e0ed AO |
767 | i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si)) |
768 | { | |
355fe088 | 769 | gimple *stmt = gsi_stmt (si); |
fe77e0ed AO |
770 | if (!is_gimple_debug (stmt)) |
771 | break; | |
96a95ac1 AO |
772 | if (gimple_debug_nonbind_marker_p (stmt)) |
773 | continue; | |
fe77e0ed AO |
774 | i++; |
775 | } | |
776 | ||
00f96dc9 | 777 | auto_vec<tree, alloc_count> fewvars; |
6e2830c3 | 778 | hash_set<tree> *vars = NULL; |
fe77e0ed AO |
779 | |
780 | /* If we're already starting with 3/4 of alloc_count, go for a | |
6e2830c3 | 781 | hash_set, otherwise start with an unordered stack-allocated |
fe77e0ed AO |
782 | VEC. */ |
783 | if (i * 4 > alloc_count * 3) | |
6e2830c3 | 784 | vars = new hash_set<tree>; |
fe77e0ed AO |
785 | |
786 | /* Now go through the initial debug stmts in DEST again, this time | |
787 | actually inserting in VARS or FEWVARS. Don't bother checking for | |
788 | duplicates in FEWVARS. */ | |
789 | for (gimple_stmt_iterator si = gsi; !gsi_end_p (si); gsi_next (&si)) | |
447a7045 | 790 | { |
355fe088 | 791 | gimple *stmt = gsi_stmt (si); |
447a7045 AO |
792 | if (!is_gimple_debug (stmt)) |
793 | break; | |
794 | ||
795 | tree var; | |
796 | ||
797 | if (gimple_debug_bind_p (stmt)) | |
798 | var = gimple_debug_bind_get_var (stmt); | |
799 | else if (gimple_debug_source_bind_p (stmt)) | |
800 | var = gimple_debug_source_bind_get_var (stmt); | |
96a95ac1 AO |
801 | else if (gimple_debug_nonbind_marker_p (stmt)) |
802 | continue; | |
447a7045 AO |
803 | else |
804 | gcc_unreachable (); | |
805 | ||
fe77e0ed | 806 | if (vars) |
6e2830c3 | 807 | vars->add (var); |
fe77e0ed | 808 | else |
9771b263 | 809 | fewvars.quick_push (var); |
447a7045 AO |
810 | } |
811 | ||
812 | basic_block bb = dest; | |
813 | ||
814 | do | |
815 | { | |
816 | bb = single_pred (bb); | |
817 | for (gimple_stmt_iterator si = gsi_last_bb (bb); | |
818 | !gsi_end_p (si); gsi_prev (&si)) | |
819 | { | |
355fe088 | 820 | gimple *stmt = gsi_stmt (si); |
447a7045 AO |
821 | if (!is_gimple_debug (stmt)) |
822 | continue; | |
823 | ||
824 | tree var; | |
825 | ||
826 | if (gimple_debug_bind_p (stmt)) | |
827 | var = gimple_debug_bind_get_var (stmt); | |
828 | else if (gimple_debug_source_bind_p (stmt)) | |
829 | var = gimple_debug_source_bind_get_var (stmt); | |
96a95ac1 AO |
830 | else if (gimple_debug_nonbind_marker_p (stmt)) |
831 | continue; | |
447a7045 AO |
832 | else |
833 | gcc_unreachable (); | |
834 | ||
96a95ac1 | 835 | /* Discard debug bind overlaps. Unlike stmts from src, |
447a7045 AO |
836 | copied into a new block that will precede BB, debug bind |
837 | stmts in bypassed BBs may actually be discarded if | |
96a95ac1 AO |
838 | they're overwritten by subsequent debug bind stmts. We |
839 | want to copy binds for all modified variables, so that we | |
840 | retain a bind to the shared def if there is one, or to a | |
841 | newly introduced PHI node if there is one. Our bind will | |
842 | end up reset if the value is dead, but that implies the | |
843 | variable couldn't have survived, so it's fine. We are | |
844 | not actually running the code that performed the binds at | |
845 | this point, we're just adding binds so that they survive | |
846 | the new confluence, so markers should not be copied. */ | |
6e2830c3 | 847 | if (vars && vars->add (var)) |
447a7045 | 848 | continue; |
fe77e0ed AO |
849 | else if (!vars) |
850 | { | |
9771b263 | 851 | int i = fewvars.length (); |
fe77e0ed | 852 | while (i--) |
9771b263 | 853 | if (fewvars[i] == var) |
fe77e0ed AO |
854 | break; |
855 | if (i >= 0) | |
856 | continue; | |
96a95ac1 | 857 | else if (fewvars.length () < (unsigned) alloc_count) |
9771b263 | 858 | fewvars.quick_push (var); |
fe77e0ed AO |
859 | else |
860 | { | |
6e2830c3 | 861 | vars = new hash_set<tree>; |
fe77e0ed | 862 | for (i = 0; i < alloc_count; i++) |
6e2830c3 | 863 | vars->add (fewvars[i]); |
9771b263 | 864 | fewvars.release (); |
6e2830c3 | 865 | vars->add (var); |
fe77e0ed AO |
866 | } |
867 | } | |
447a7045 AO |
868 | |
869 | stmt = gimple_copy (stmt); | |
870 | /* ??? Should we drop the location of the copy to denote | |
871 | they're artificial bindings? */ | |
872 | gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); | |
873 | } | |
874 | } | |
875 | while (bb != src && single_pred_p (bb)); | |
876 | ||
fe77e0ed | 877 | if (vars) |
6e2830c3 | 878 | delete vars; |
9771b263 DN |
879 | else if (fewvars.exists ()) |
880 | fewvars.release (); | |
447a7045 AO |
881 | } |
882 | ||
770da076 JL |
883 | /* See if TAKEN_EDGE->dest is a threadable block with no side effecs (ie, it |
884 | need not be duplicated as part of the CFG/SSA updating process). | |
885 | ||
886 | If it is threadable, add it to PATH and VISITED and recurse, ultimately | |
887 | returning TRUE from the toplevel call. Otherwise do nothing and | |
888 | return false. | |
889 | ||
8d7437be JL |
890 | DUMMY_COND, SIMPLIFY are used to try and simplify the condition at the |
891 | end of TAKEN_EDGE->dest. | |
8e33db8f JL |
892 | |
893 | The available expression table is referenced via AVAIL_EXPRS_STACK. */ | |
894 | ||
770da076 JL |
895 | static bool |
896 | thread_around_empty_blocks (edge taken_edge, | |
538dd0b7 | 897 | gcond *dummy_cond, |
8e33db8f | 898 | class avail_exprs_stack *avail_exprs_stack, |
8e33db8f | 899 | pfn_simplify simplify, |
770da076 | 900 | bitmap visited, |
88419b52 | 901 | vec<jump_thread_edge *> *path) |
520af9ec JL |
902 | { |
903 | basic_block bb = taken_edge->dest; | |
904 | gimple_stmt_iterator gsi; | |
355fe088 | 905 | gimple *stmt; |
520af9ec JL |
906 | tree cond; |
907 | ||
770da076 | 908 | /* The key property of these blocks is that they need not be duplicated |
67914693 | 909 | when threading. Thus they cannot have visible side effects such |
770da076 | 910 | as PHI nodes. */ |
520af9ec | 911 | if (!gsi_end_p (gsi_start_phis (bb))) |
581aedec | 912 | return false; |
520af9ec JL |
913 | |
914 | /* Skip over DEBUG statements at the start of the block. */ | |
915 | gsi = gsi_start_nondebug_bb (bb); | |
916 | ||
770da076 | 917 | /* If the block has no statements, but does have a single successor, then |
45d99234 | 918 | it's just a forwarding block and we can thread through it trivially. |
9e1376e9 JL |
919 | |
920 | However, note that just threading through empty blocks with single | |
921 | successors is not inherently profitable. For the jump thread to | |
922 | be profitable, we must avoid a runtime conditional. | |
923 | ||
924 | By taking the return value from the recursive call, we get the | |
925 | desired effect of returning TRUE when we found a profitable jump | |
45d99234 | 926 | threading opportunity and FALSE otherwise. |
9e1376e9 JL |
927 | |
928 | This is particularly important when this routine is called after | |
929 | processing a joiner block. Returning TRUE too aggressively in | |
930 | that case results in pointless duplication of the joiner block. */ | |
520af9ec | 931 | if (gsi_end_p (gsi)) |
770da076 JL |
932 | { |
933 | if (single_succ_p (bb)) | |
934 | { | |
935 | taken_edge = single_succ_edge (bb); | |
88419b52 JL |
936 | |
937 | if ((taken_edge->flags & EDGE_DFS_BACK) != 0) | |
938 | return false; | |
939 | ||
3eae202f | 940 | if (!bitmap_bit_p (visited, taken_edge->dest->index)) |
770da076 | 941 | { |
5254eac4 JL |
942 | jump_thread_edge *x |
943 | = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); | |
944 | path->safe_push (x); | |
770da076 | 945 | bitmap_set_bit (visited, taken_edge->dest->index); |
9e1376e9 JL |
946 | return thread_around_empty_blocks (taken_edge, |
947 | dummy_cond, | |
8e33db8f | 948 | avail_exprs_stack, |
9e1376e9 JL |
949 | simplify, |
950 | visited, | |
88419b52 | 951 | path); |
770da076 JL |
952 | } |
953 | } | |
9e1376e9 JL |
954 | |
955 | /* We have a block with no statements, but multiple successors? */ | |
770da076 JL |
956 | return false; |
957 | } | |
520af9ec | 958 | |
770da076 JL |
959 | /* The only real statements this block can have are a control |
960 | flow altering statement. Anything else stops the thread. */ | |
520af9ec JL |
961 | stmt = gsi_stmt (gsi); |
962 | if (gimple_code (stmt) != GIMPLE_COND | |
963 | && gimple_code (stmt) != GIMPLE_GOTO | |
964 | && gimple_code (stmt) != GIMPLE_SWITCH) | |
770da076 | 965 | return false; |
520af9ec JL |
966 | |
967 | /* Extract and simplify the condition. */ | |
8e33db8f JL |
968 | cond = simplify_control_stmt_condition (taken_edge, stmt, |
969 | avail_exprs_stack, dummy_cond, | |
8d7437be | 970 | simplify); |
520af9ec JL |
971 | |
972 | /* If the condition can be statically computed and we have not already | |
973 | visited the destination edge, then add the taken edge to our thread | |
974 | path. */ | |
5c3e5002 PP |
975 | if (cond != NULL_TREE |
976 | && (is_gimple_min_invariant (cond) | |
977 | || TREE_CODE (cond) == CASE_LABEL_EXPR)) | |
520af9ec | 978 | { |
5c3e5002 | 979 | if (TREE_CODE (cond) == CASE_LABEL_EXPR) |
61ff5d6f | 980 | taken_edge = find_edge (bb, label_to_block (cfun, CASE_LABEL (cond))); |
5c3e5002 PP |
981 | else |
982 | taken_edge = find_taken_edge (bb, cond); | |
520af9ec | 983 | |
a26eaf98 RB |
984 | if (!taken_edge |
985 | || (taken_edge->flags & EDGE_DFS_BACK) != 0) | |
88419b52 JL |
986 | return false; |
987 | ||
520af9ec | 988 | if (bitmap_bit_p (visited, taken_edge->dest->index)) |
770da076 | 989 | return false; |
520af9ec | 990 | bitmap_set_bit (visited, taken_edge->dest->index); |
5254eac4 JL |
991 | |
992 | jump_thread_edge *x | |
993 | = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK); | |
994 | path->safe_push (x); | |
995 | ||
770da076 JL |
996 | thread_around_empty_blocks (taken_edge, |
997 | dummy_cond, | |
8e33db8f | 998 | avail_exprs_stack, |
770da076 JL |
999 | simplify, |
1000 | visited, | |
88419b52 | 1001 | path); |
770da076 | 1002 | return true; |
520af9ec | 1003 | } |
45d99234 | 1004 | |
770da076 | 1005 | return false; |
520af9ec | 1006 | } |
45d99234 | 1007 | |
2090d6a0 | 1008 | /* We are exiting E->src, see if E->dest ends with a conditional |
b8698a0f | 1009 | jump which has a known value when reached via E. |
2090d6a0 | 1010 | |
45d99234 JL |
1011 | E->dest can have arbitrary side effects which, if threading is |
1012 | successful, will be maintained. | |
1013 | ||
2090d6a0 JL |
1014 | Special care is necessary if E is a back edge in the CFG as we |
1015 | may have already recorded equivalences for E->dest into our | |
1016 | various tables, including the result of the conditional at | |
1017 | the end of E->dest. Threading opportunities are severely | |
1018 | limited in that case to avoid short-circuiting the loop | |
1019 | incorrectly. | |
1020 | ||
c7b852c8 ZD |
1021 | DUMMY_COND is a shared cond_expr used by condition simplification as scratch, |
1022 | to avoid allocating memory. | |
b8698a0f | 1023 | |
c7b852c8 ZD |
1024 | STACK is used to undo temporary equivalences created during the walk of |
1025 | E->dest. | |
1026 | ||
45d99234 | 1027 | SIMPLIFY is a pass-specific function used to simplify statements. |
2090d6a0 | 1028 | |
45d99234 | 1029 | Our caller is responsible for restoring the state of the expression |
0600049c | 1030 | and const_and_copies stacks. |
2090d6a0 | 1031 | |
0600049c JL |
1032 | Positive return value is success. Zero return value is failure, but |
1033 | the block can still be duplicated as a joiner in a jump thread path, | |
1034 | negative indicates the block should not be duplicated and thus is not | |
1035 | suitable for a joiner in a jump threading path. */ | |
1036 | ||
1037 | static int | |
45d99234 | 1038 | thread_through_normal_block (edge e, |
538dd0b7 | 1039 | gcond *dummy_cond, |
f6c72af4 | 1040 | const_and_copies *const_and_copies, |
8e33db8f | 1041 | avail_exprs_stack *avail_exprs_stack, |
df80fc53 | 1042 | evrp_range_analyzer *evrp_range_analyzer, |
8e33db8f | 1043 | pfn_simplify simplify, |
b5c4ff78 | 1044 | vec<jump_thread_edge *> *path, |
88419b52 | 1045 | bitmap visited) |
45d99234 | 1046 | { |
7c3e7056 | 1047 | /* We want to record any equivalences created by traversing E. */ |
8d7437be | 1048 | record_temporary_equivalences (e, const_and_copies, avail_exprs_stack); |
7c3e7056 | 1049 | |
551a6341 JL |
1050 | /* PHIs create temporary equivalences. |
1051 | Note that if we found a PHI that made the block non-threadable, then | |
1052 | we need to bubble that up to our caller in the same manner we do | |
1053 | when we prematurely stop processing statements below. */ | |
df80fc53 JL |
1054 | if (!record_temporary_equivalences_from_phis (e, const_and_copies, |
1055 | evrp_range_analyzer)) | |
551a6341 | 1056 | return -1; |
2090d6a0 JL |
1057 | |
1058 | /* Now walk each statement recording any context sensitive | |
1059 | temporary equivalences we can detect. */ | |
355fe088 | 1060 | gimple *stmt |
a12cbc57 | 1061 | = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies, |
8e33db8f | 1062 | avail_exprs_stack, |
df80fc53 | 1063 | evrp_range_analyzer, |
334b4842 | 1064 | simplify); |
0600049c | 1065 | |
215f8d9e JL |
1066 | /* There's two reasons STMT might be null, and distinguishing |
1067 | between them is important. | |
0600049c | 1068 | |
215f8d9e JL |
1069 | First the block may not have had any statements. For example, it |
1070 | might have some PHIs and unconditionally transfer control elsewhere. | |
1071 | Such blocks are suitable for jump threading, particularly as a | |
1072 | joiner block. | |
c7a28c1b | 1073 | |
215f8d9e JL |
1074 | The second reason would be if we did not process all the statements |
1075 | in the block (because there were too many to make duplicating the | |
1076 | block profitable. If we did not look at all the statements, then | |
1077 | we may not have invalidated everything needing invalidation. Thus | |
1078 | we must signal to our caller that this block is not suitable for | |
1079 | use as a joiner in a threading path. */ | |
1080 | if (!stmt) | |
1081 | { | |
1082 | /* First case. The statement simply doesn't have any instructions, but | |
1083 | does have PHIs. */ | |
1084 | if (gsi_end_p (gsi_start_nondebug_bb (e->dest)) | |
1085 | && !gsi_end_p (gsi_start_phis (e->dest))) | |
1086 | return 0; | |
1087 | ||
1088 | /* Second case. */ | |
1089 | return -1; | |
1090 | } | |
1b2fe7d3 | 1091 | |
2090d6a0 JL |
1092 | /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm |
1093 | will be taken. */ | |
726a989a RB |
1094 | if (gimple_code (stmt) == GIMPLE_COND |
1095 | || gimple_code (stmt) == GIMPLE_GOTO | |
1096 | || gimple_code (stmt) == GIMPLE_SWITCH) | |
2090d6a0 JL |
1097 | { |
1098 | tree cond; | |
1099 | ||
1100 | /* Extract and simplify the condition. */ | |
8e33db8f | 1101 | cond = simplify_control_stmt_condition (e, stmt, avail_exprs_stack, |
8d7437be | 1102 | dummy_cond, simplify); |
2090d6a0 | 1103 | |
50e9ff83 JG |
1104 | if (!cond) |
1105 | return 0; | |
1106 | ||
5c3e5002 PP |
1107 | if (is_gimple_min_invariant (cond) |
1108 | || TREE_CODE (cond) == CASE_LABEL_EXPR) | |
2090d6a0 | 1109 | { |
5c3e5002 PP |
1110 | edge taken_edge; |
1111 | if (TREE_CODE (cond) == CASE_LABEL_EXPR) | |
1112 | taken_edge = find_edge (e->dest, | |
61ff5d6f | 1113 | label_to_block (cfun, CASE_LABEL (cond))); |
5c3e5002 PP |
1114 | else |
1115 | taken_edge = find_taken_edge (e->dest, cond); | |
1116 | ||
2090d6a0 JL |
1117 | basic_block dest = (taken_edge ? taken_edge->dest : NULL); |
1118 | ||
770da076 JL |
1119 | /* DEST could be NULL for a computed jump to an absolute |
1120 | address. */ | |
3eae202f JL |
1121 | if (dest == NULL |
1122 | || dest == e->dest | |
88419b52 | 1123 | || (taken_edge->flags & EDGE_DFS_BACK) != 0 |
3eae202f | 1124 | || bitmap_bit_p (visited, dest->index)) |
0600049c | 1125 | return 0; |
2090d6a0 | 1126 | |
6eeef4cc JL |
1127 | /* Only push the EDGE_START_JUMP_THREAD marker if this is |
1128 | first edge on the path. */ | |
1129 | if (path->length () == 0) | |
1130 | { | |
1131 | jump_thread_edge *x | |
1132 | = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); | |
1133 | path->safe_push (x); | |
6eeef4cc | 1134 | } |
5254eac4 | 1135 | |
6eeef4cc JL |
1136 | jump_thread_edge *x |
1137 | = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK); | |
aee2d611 | 1138 | path->safe_push (x); |
3b18bc42 | 1139 | |
770da076 JL |
1140 | /* See if we can thread through DEST as well, this helps capture |
1141 | secondary effects of threading without having to re-run DOM or | |
1b2fe7d3 | 1142 | VRP. |
d4fdb4df JL |
1143 | |
1144 | We don't want to thread back to a block we have already | |
1145 | visited. This may be overly conservative. */ | |
1146 | bitmap_set_bit (visited, dest->index); | |
1147 | bitmap_set_bit (visited, e->dest->index); | |
1148 | thread_around_empty_blocks (taken_edge, | |
1149 | dummy_cond, | |
8e33db8f | 1150 | avail_exprs_stack, |
d4fdb4df JL |
1151 | simplify, |
1152 | visited, | |
88419b52 | 1153 | path); |
0600049c | 1154 | return 1; |
2090d6a0 JL |
1155 | } |
1156 | } | |
0600049c | 1157 | return 0; |
45d99234 JL |
1158 | } |
1159 | ||
1d53751d JG |
1160 | /* There are basic blocks look like: |
1161 | <P0> | |
1162 | p0 = a CMP b ; or p0 = (INT) (a CMP b) | |
1163 | goto <X>; | |
1164 | ||
1165 | <P1> | |
1166 | p1 = c CMP d | |
1167 | goto <X>; | |
1168 | ||
1169 | <X> | |
1170 | # phi = PHI <p0 (P0), p1 (P1)> | |
1171 | if (phi != 0) goto <Y>; else goto <Z>; | |
1172 | ||
1173 | Then, edge (P0,X) or (P1,X) could be marked as EDGE_START_JUMP_THREAD | |
1174 | And edge (X,Y), (X,Z) is EDGE_COPY_SRC_JOINER_BLOCK | |
1175 | ||
1176 | Return true if E is (P0,X) or (P1,X) */ | |
1177 | ||
1178 | bool | |
1179 | edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (edge e) | |
1180 | { | |
1181 | /* See if there is only one stmt which is gcond. */ | |
1182 | gcond *gs; | |
1183 | if (!(gs = safe_dyn_cast<gcond *> (last_and_only_stmt (e->dest)))) | |
1184 | return false; | |
1185 | ||
1186 | /* See if gcond's cond is "(phi !=/== 0/1)" in the basic block. */ | |
1187 | tree cond = gimple_cond_lhs (gs); | |
1188 | enum tree_code code = gimple_cond_code (gs); | |
1189 | tree rhs = gimple_cond_rhs (gs); | |
1190 | if (TREE_CODE (cond) != SSA_NAME | |
1191 | || (code != NE_EXPR && code != EQ_EXPR) | |
1192 | || (!integer_onep (rhs) && !integer_zerop (rhs))) | |
1193 | return false; | |
1194 | gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (cond)); | |
1195 | if (phi == NULL || gimple_bb (phi) != e->dest) | |
1196 | return false; | |
1197 | ||
1198 | /* Check if phi's incoming value is CMP. */ | |
1199 | gassign *def; | |
1200 | tree value = PHI_ARG_DEF_FROM_EDGE (phi, e); | |
1201 | if (TREE_CODE (value) != SSA_NAME | |
1202 | || !has_single_use (value) | |
1203 | || !(def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (value)))) | |
1204 | return false; | |
1205 | ||
1206 | /* Or if it is (INT) (a CMP b). */ | |
1207 | if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))) | |
1208 | { | |
1209 | value = gimple_assign_rhs1 (def); | |
1210 | if (TREE_CODE (value) != SSA_NAME | |
1211 | || !has_single_use (value) | |
1212 | || !(def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (value)))) | |
1213 | return false; | |
1214 | } | |
1215 | ||
1216 | if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison) | |
1217 | return false; | |
1218 | ||
1219 | return true; | |
1220 | } | |
1221 | ||
45d99234 JL |
1222 | /* We are exiting E->src, see if E->dest ends with a conditional |
1223 | jump which has a known value when reached via E. | |
1224 | ||
45d99234 JL |
1225 | DUMMY_COND is a shared cond_expr used by condition simplification as scratch, |
1226 | to avoid allocating memory. | |
1227 | ||
8e33db8f JL |
1228 | CONST_AND_COPIES is used to undo temporary equivalences created during the |
1229 | walk of E->dest. | |
1230 | ||
1231 | The available expression table is referenced vai AVAIL_EXPRS_STACK. | |
45d99234 JL |
1232 | |
1233 | SIMPLIFY is a pass-specific function used to simplify statements. */ | |
1234 | ||
c8755022 | 1235 | static void |
538dd0b7 | 1236 | thread_across_edge (gcond *dummy_cond, |
45d99234 | 1237 | edge e, |
8e33db8f JL |
1238 | class const_and_copies *const_and_copies, |
1239 | class avail_exprs_stack *avail_exprs_stack, | |
df80fc53 | 1240 | class evrp_range_analyzer *evrp_range_analyzer, |
c8755022 | 1241 | pfn_simplify simplify) |
45d99234 | 1242 | { |
b5c4ff78 JL |
1243 | bitmap visited = BITMAP_ALLOC (NULL); |
1244 | ||
c8755022 JL |
1245 | const_and_copies->push_marker (); |
1246 | avail_exprs_stack->push_marker (); | |
df80fc53 JL |
1247 | if (evrp_range_analyzer) |
1248 | evrp_range_analyzer->push_marker (); | |
c8755022 | 1249 | |
45d99234 JL |
1250 | stmt_count = 0; |
1251 | ||
1252 | vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); | |
b5c4ff78 JL |
1253 | bitmap_clear (visited); |
1254 | bitmap_set_bit (visited, e->src->index); | |
1255 | bitmap_set_bit (visited, e->dest->index); | |
88419b52 JL |
1256 | |
1257 | int threaded; | |
1258 | if ((e->flags & EDGE_DFS_BACK) == 0) | |
1259 | threaded = thread_through_normal_block (e, dummy_cond, | |
88419b52 JL |
1260 | const_and_copies, |
1261 | avail_exprs_stack, | |
df80fc53 | 1262 | evrp_range_analyzer, |
88419b52 JL |
1263 | simplify, path, |
1264 | visited); | |
1265 | else | |
1266 | threaded = 0; | |
1267 | ||
0600049c | 1268 | if (threaded > 0) |
45d99234 JL |
1269 | { |
1270 | propagate_threaded_block_debug_into (path->last ()->e->dest, | |
1271 | e->dest); | |
f6c72af4 | 1272 | const_and_copies->pop_to_marker (); |
c8755022 | 1273 | avail_exprs_stack->pop_to_marker (); |
df80fc53 JL |
1274 | if (evrp_range_analyzer) |
1275 | evrp_range_analyzer->pop_to_marker (); | |
b5c4ff78 | 1276 | BITMAP_FREE (visited); |
45d99234 JL |
1277 | register_jump_thread (path); |
1278 | return; | |
1279 | } | |
1280 | else | |
1281 | { | |
0600049c JL |
1282 | /* Negative and zero return values indicate no threading was possible, |
1283 | thus there should be no edges on the thread path and no need to walk | |
1284 | through the vector entries. */ | |
45d99234 JL |
1285 | gcc_assert (path->length () == 0); |
1286 | path->release (); | |
89bd38d3 | 1287 | delete path; |
0600049c JL |
1288 | |
1289 | /* A negative status indicates the target block was deemed too big to | |
1290 | duplicate. Just quit now rather than trying to use the block as | |
1291 | a joiner in a jump threading path. | |
1292 | ||
1293 | This prevents unnecessary code growth, but more importantly if we | |
1294 | do not look at all the statements in the block, then we may have | |
1295 | missed some invalidations if we had traversed a backedge! */ | |
1296 | if (threaded < 0) | |
1297 | { | |
1298 | BITMAP_FREE (visited); | |
f6c72af4 | 1299 | const_and_copies->pop_to_marker (); |
c8755022 | 1300 | avail_exprs_stack->pop_to_marker (); |
df80fc53 JL |
1301 | if (evrp_range_analyzer) |
1302 | evrp_range_analyzer->pop_to_marker (); | |
0600049c JL |
1303 | return; |
1304 | } | |
45d99234 | 1305 | } |
2090d6a0 | 1306 | |
361b51c0 JL |
1307 | /* We were unable to determine what out edge from E->dest is taken. However, |
1308 | we might still be able to thread through successors of E->dest. This | |
1309 | often occurs when E->dest is a joiner block which then fans back out | |
1310 | based on redundant tests. | |
1311 | ||
1312 | If so, we'll copy E->dest and redirect the appropriate predecessor to | |
1313 | the copy. Within the copy of E->dest, we'll thread one or more edges | |
1314 | to points deeper in the CFG. | |
1315 | ||
1316 | This is a stopgap until we have a more structured approach to path | |
1317 | isolation. */ | |
1318 | { | |
770da076 | 1319 | edge taken_edge; |
361b51c0 | 1320 | edge_iterator ei; |
4f4b0b73 | 1321 | bool found; |
361b51c0 | 1322 | |
b1149e84 JL |
1323 | /* If E->dest has abnormal outgoing edges, then there's no guarantee |
1324 | we can safely redirect any of the edges. Just punt those cases. */ | |
1325 | FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) | |
98181563 | 1326 | if (taken_edge->flags & EDGE_COMPLEX) |
b1149e84 | 1327 | { |
f6c72af4 | 1328 | const_and_copies->pop_to_marker (); |
c8755022 | 1329 | avail_exprs_stack->pop_to_marker (); |
df80fc53 JL |
1330 | if (evrp_range_analyzer) |
1331 | evrp_range_analyzer->pop_to_marker (); | |
b1149e84 JL |
1332 | BITMAP_FREE (visited); |
1333 | return; | |
1334 | } | |
1335 | ||
361b51c0 JL |
1336 | /* Look at each successor of E->dest to see if we can thread through it. */ |
1337 | FOR_EACH_EDGE (taken_edge, ei, e->dest->succs) | |
1338 | { | |
88419b52 JL |
1339 | if ((e->flags & EDGE_DFS_BACK) != 0 |
1340 | || (taken_edge->flags & EDGE_DFS_BACK) != 0) | |
8b2ef235 | 1341 | continue; |
88419b52 | 1342 | |
a6094705 JL |
1343 | /* Push a fresh marker so we can unwind the equivalences created |
1344 | for each of E->dest's successors. */ | |
f6c72af4 | 1345 | const_and_copies->push_marker (); |
c8755022 | 1346 | avail_exprs_stack->push_marker (); |
df80fc53 JL |
1347 | if (evrp_range_analyzer) |
1348 | evrp_range_analyzer->push_marker (); | |
1b2fe7d3 | 1349 | |
361b51c0 JL |
1350 | /* Avoid threading to any block we have already visited. */ |
1351 | bitmap_clear (visited); | |
e44a45c6 | 1352 | bitmap_set_bit (visited, e->src->index); |
361b51c0 | 1353 | bitmap_set_bit (visited, e->dest->index); |
e44a45c6 | 1354 | bitmap_set_bit (visited, taken_edge->dest->index); |
aee2d611 | 1355 | vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> (); |
361b51c0 JL |
1356 | |
1357 | /* Record whether or not we were able to thread through a successor | |
1358 | of E->dest. */ | |
5254eac4 | 1359 | jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD); |
aee2d611 | 1360 | path->safe_push (x); |
5254eac4 JL |
1361 | |
1362 | x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK); | |
aee2d611 | 1363 | path->safe_push (x); |
d4fdb4df JL |
1364 | found = thread_around_empty_blocks (taken_edge, |
1365 | dummy_cond, | |
8e33db8f | 1366 | avail_exprs_stack, |
d4fdb4df JL |
1367 | simplify, |
1368 | visited, | |
88419b52 | 1369 | path); |
d4fdb4df JL |
1370 | |
1371 | if (!found) | |
5f51d006 | 1372 | found = thread_through_normal_block (path->last ()->e, dummy_cond, |
8e33db8f JL |
1373 | const_and_copies, |
1374 | avail_exprs_stack, | |
df80fc53 | 1375 | evrp_range_analyzer, |
8e33db8f | 1376 | simplify, path, |
88419b52 | 1377 | visited) > 0; |
5f51d006 | 1378 | |
361b51c0 JL |
1379 | /* If we were able to thread through a successor of E->dest, then |
1380 | record the jump threading opportunity. */ | |
1d53751d JG |
1381 | if (found |
1382 | || edge_forwards_cmp_to_conditional_jump_through_empty_bb_p (e)) | |
361b51c0 | 1383 | { |
1d53751d JG |
1384 | if (taken_edge->dest != path->last ()->e->dest) |
1385 | propagate_threaded_block_debug_into (path->last ()->e->dest, | |
1386 | taken_edge->dest); | |
5254eac4 | 1387 | register_jump_thread (path); |
361b51c0 | 1388 | } |
aee2d611 | 1389 | else |
8b2ef235 | 1390 | delete_jump_thread_path (path); |
a6094705 JL |
1391 | |
1392 | /* And unwind the equivalence table. */ | |
df80fc53 JL |
1393 | if (evrp_range_analyzer) |
1394 | evrp_range_analyzer->pop_to_marker (); | |
c8755022 | 1395 | avail_exprs_stack->pop_to_marker (); |
f6c72af4 | 1396 | const_and_copies->pop_to_marker (); |
361b51c0 JL |
1397 | } |
1398 | BITMAP_FREE (visited); | |
1399 | } | |
1400 | ||
df80fc53 JL |
1401 | if (evrp_range_analyzer) |
1402 | evrp_range_analyzer->pop_to_marker (); | |
f6c72af4 | 1403 | const_and_copies->pop_to_marker (); |
c8755022 JL |
1404 | avail_exprs_stack->pop_to_marker (); |
1405 | } | |
1406 | ||
1407 | /* Examine the outgoing edges from BB and conditionally | |
1408 | try to thread them. | |
1409 | ||
1410 | DUMMY_COND is a shared cond_expr used by condition simplification as scratch, | |
1411 | to avoid allocating memory. | |
1412 | ||
1413 | CONST_AND_COPIES is used to undo temporary equivalences created during the | |
1414 | walk of E->dest. | |
1415 | ||
1416 | The available expression table is referenced vai AVAIL_EXPRS_STACK. | |
1417 | ||
1418 | SIMPLIFY is a pass-specific function used to simplify statements. */ | |
1419 | ||
1420 | void | |
1421 | thread_outgoing_edges (basic_block bb, gcond *dummy_cond, | |
1422 | class const_and_copies *const_and_copies, | |
1423 | class avail_exprs_stack *avail_exprs_stack, | |
df80fc53 | 1424 | class evrp_range_analyzer *evrp_range_analyzer, |
c8755022 JL |
1425 | tree (*simplify) (gimple *, gimple *, |
1426 | class avail_exprs_stack *, | |
1427 | basic_block)) | |
1428 | { | |
1429 | int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL); | |
1430 | gimple *last; | |
1431 | ||
1432 | /* If we have an outgoing edge to a block with multiple incoming and | |
1433 | outgoing edges, then we may be able to thread the edge, i.e., we | |
1434 | may be able to statically determine which of the outgoing edges | |
1435 | will be traversed when the incoming edge from BB is traversed. */ | |
1436 | if (single_succ_p (bb) | |
1437 | && (single_succ_edge (bb)->flags & flags) == 0 | |
1438 | && potentially_threadable_block (single_succ (bb))) | |
1439 | { | |
1440 | thread_across_edge (dummy_cond, single_succ_edge (bb), | |
1441 | const_and_copies, avail_exprs_stack, | |
df80fc53 | 1442 | evrp_range_analyzer, simplify); |
c8755022 JL |
1443 | } |
1444 | else if ((last = last_stmt (bb)) | |
1445 | && gimple_code (last) == GIMPLE_COND | |
1446 | && EDGE_COUNT (bb->succs) == 2 | |
1447 | && (EDGE_SUCC (bb, 0)->flags & flags) == 0 | |
1448 | && (EDGE_SUCC (bb, 1)->flags & flags) == 0) | |
1449 | { | |
1450 | edge true_edge, false_edge; | |
1451 | ||
1452 | extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
1453 | ||
1454 | /* Only try to thread the edge if it reaches a target block with | |
1455 | more than one predecessor and more than one successor. */ | |
1456 | if (potentially_threadable_block (true_edge->dest)) | |
1457 | thread_across_edge (dummy_cond, true_edge, | |
df80fc53 JL |
1458 | const_and_copies, avail_exprs_stack, |
1459 | evrp_range_analyzer, simplify); | |
c8755022 JL |
1460 | |
1461 | /* Similarly for the ELSE arm. */ | |
1462 | if (potentially_threadable_block (false_edge->dest)) | |
1463 | thread_across_edge (dummy_cond, false_edge, | |
df80fc53 JL |
1464 | const_and_copies, avail_exprs_stack, |
1465 | evrp_range_analyzer, simplify); | |
c8755022 | 1466 | } |
2090d6a0 | 1467 | } |