1 /* SSA Jump Threading
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
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
9 the Free Software Foundation; either version 3, or (at your option)
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
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "predict.h"
28 #include "ssa.h"
29 #include "fold-const.h"
30 #include "cfgloop.h"
31 #include "gimple-iterator.h"
32 #include "tree-cfg.h"
33 #include "tree-ssa-threadupdate.h"
34 #include "params.h"
35 #include "tree-ssa-scopedtables.h"
36 #include "tree-ssa-threadedge.h"
37 #include "tree-ssa-dom.h"
38 #include "gimple-fold.h"
39 #include "cfganal.h"
40 #include "alloc-pool.h"
41 #include "vr-values.h"
42 #include "gimple-ssa-evrp-analyze.h"
43
44 /* To avoid code explosion due to jump threading, we limit the
45 number of statements we are going to copy. This variable
46 holds the number of statements currently seen that we'll have
47 to copy as part of the jump threading process. */
48 static int stmt_count;
49
50 /* Array to record value-handles per SSA_NAME. */
51 vec<tree> ssa_name_values;
52
53 typedef tree (pfn_simplify) (gimple *, gimple *,
54 class avail_exprs_stack *,
55 basic_block);
56
57 /* Set the value for the SSA name NAME to VALUE. */
58
59 void
set_ssa_name_value(tree name,tree value)60 set_ssa_name_value (tree name, tree value)
61 {
62 if (SSA_NAME_VERSION (name) >= ssa_name_values.length ())
63 ssa_name_values.safe_grow_cleared (SSA_NAME_VERSION (name) + 1);
64 if (value && TREE_OVERFLOW_P (value))
65 value = drop_tree_overflow (value);
66 ssa_name_values[SSA_NAME_VERSION (name)] = value;
67 }
68
69 /* Initialize the per SSA_NAME value-handles array. Returns it. */
70 void
threadedge_initialize_values(void)71 threadedge_initialize_values (void)
72 {
73 gcc_assert (!ssa_name_values.exists ());
74 ssa_name_values.create (num_ssa_names);
75 }
76
77 /* Free the per SSA_NAME value-handle array. */
78 void
threadedge_finalize_values(void)79 threadedge_finalize_values (void)
80 {
81 ssa_name_values.release ();
82 }
83
84 /* Return TRUE if we may be able to thread an incoming edge into
85 BB to an outgoing edge from BB. Return FALSE otherwise. */
86
87 bool
potentially_threadable_block(basic_block bb)88 potentially_threadable_block (basic_block bb)
89 {
90 gimple_stmt_iterator gsi;
91
92 /* Special case. We can get blocks that are forwarders, but are
93 not optimized away because they forward from outside a loop
94 to the loop header. We want to thread through them as we can
95 sometimes thread to the loop exit, which is obviously profitable.
96 the interesting case here is when the block has PHIs. */
97 if (gsi_end_p (gsi_start_nondebug_bb (bb))
98 && !gsi_end_p (gsi_start_phis (bb)))
99 return true;
100
101 /* If BB has a single successor or a single predecessor, then
102 there is no threading opportunity. */
103 if (single_succ_p (bb) || single_pred_p (bb))
104 return false;
105
106 /* If BB does not end with a conditional, switch or computed goto,
107 then there is no threading opportunity. */
108 gsi = gsi_last_bb (bb);
109 if (gsi_end_p (gsi)
110 || ! gsi_stmt (gsi)
111 || (gimple_code (gsi_stmt (gsi)) != GIMPLE_COND
112 && gimple_code (gsi_stmt (gsi)) != GIMPLE_GOTO
113 && gimple_code (gsi_stmt (gsi)) != GIMPLE_SWITCH))
114 return false;
115
116 return true;
117 }
118
119 /* Record temporary equivalences created by PHIs at the target of the
120 edge E. Record unwind information for the equivalences into
121 CONST_AND_COPIES and EVRP_RANGE_DATA.
122
123 If a PHI which prevents threading is encountered, then return FALSE
124 indicating we should not thread this edge, else return TRUE. */
125
126 static bool
record_temporary_equivalences_from_phis(edge e,const_and_copies * const_and_copies,evrp_range_analyzer * evrp_range_analyzer)127 record_temporary_equivalences_from_phis (edge e,
128 const_and_copies *const_and_copies,
129 evrp_range_analyzer *evrp_range_analyzer)
130 {
131 gphi_iterator gsi;
132
133 /* Each PHI creates a temporary equivalence, record them.
134 These are context sensitive equivalences and will be removed
135 later. */
136 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
137 {
138 gphi *phi = gsi.phi ();
139 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
140 tree dst = gimple_phi_result (phi);
141
142 /* If the desired argument is not the same as this PHI's result
143 and it is set by a PHI in E->dest, then we can not thread
144 through E->dest. */
145 if (src != dst
146 && TREE_CODE (src) == SSA_NAME
147 && gimple_code (SSA_NAME_DEF_STMT (src)) == GIMPLE_PHI
148 && gimple_bb (SSA_NAME_DEF_STMT (src)) == e->dest)
149 return false;
150
151 /* We consider any non-virtual PHI as a statement since it
152 count result in a constant assignment or copy operation. */
153 if (!virtual_operand_p (dst))
154 stmt_count++;
155
156 const_and_copies->record_const_or_copy (dst, src);
157
158 /* Also update the value range associated with DST, using
159 the range from SRC.
160
161 Note that even if SRC is a constant we need to set a suitable
162 output range so that VR_UNDEFINED ranges do not leak through. */
163 if (evrp_range_analyzer)
164 {
165 /* Get an empty new VR we can pass to update_value_range and save
166 away in the VR stack. */
167 vr_values *vr_values = evrp_range_analyzer->get_vr_values ();
168 value_range *new_vr = vr_values->allocate_value_range ();
169 memset (new_vr, 0, sizeof (value_range));
170
171 /* There are three cases to consider:
172
173 First if SRC is an SSA_NAME, then we can copy the value
174 range from SRC into NEW_VR.
175
176 Second if SRC is an INTEGER_CST, then we can just wet
177 NEW_VR to a singleton range.
178
179 Otherwise set NEW_VR to varying. This may be overly
180 conservative. */
181 if (TREE_CODE (src) == SSA_NAME)
182 copy_value_range (new_vr, vr_values->get_value_range (src));
183 else if (TREE_CODE (src) == INTEGER_CST)
184 set_value_range_to_value (new_vr, src, NULL);
185 else
186 set_value_range_to_varying (new_vr);
187
188 /* This is a temporary range for DST, so push it. */
189 evrp_range_analyzer->push_value_range (dst, new_vr);
190 }
191 }
192 return true;
193 }
194
195 /* Valueize hook for gimple_fold_stmt_to_constant_1. */
196
197 static tree
threadedge_valueize(tree t)198 threadedge_valueize (tree t)
199 {
200 if (TREE_CODE (t) == SSA_NAME)
201 {
202 tree tem = SSA_NAME_VALUE (t);
203 if (tem)
204 return tem;
205 }
206 return t;
207 }
208
209 /* Try to simplify each statement in E->dest, ultimately leading to
210 a simplification of the COND_EXPR at the end of E->dest.
211
212 Record unwind information for temporary equivalences onto STACK.
213
214 Use SIMPLIFY (a pointer to a callback function) to further simplify
215 statements using pass specific information.
216
217 We might consider marking just those statements which ultimately
218 feed the COND_EXPR. It's not clear if the overhead of bookkeeping
219 would be recovered by trying to simplify fewer statements.
220
221 If we are able to simplify a statement into the form
222 SSA_NAME = (SSA_NAME | gimple invariant), then we can record
223 a context sensitive equivalence which may help us simplify
224 later statements in E->dest. */
225
226 static gimple *
record_temporary_equivalences_from_stmts_at_dest(edge e,const_and_copies * const_and_copies,avail_exprs_stack * avail_exprs_stack,evrp_range_analyzer * evrp_range_analyzer,pfn_simplify simplify)227 record_temporary_equivalences_from_stmts_at_dest (edge e,
228 const_and_copies *const_and_copies,
229 avail_exprs_stack *avail_exprs_stack,
230 evrp_range_analyzer *evrp_range_analyzer,
231 pfn_simplify simplify)
232 {
233 gimple *stmt = NULL;
234 gimple_stmt_iterator gsi;
235 int max_stmt_count;
236
237 max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
238
239 /* Walk through each statement in the block recording equivalences
240 we discover. Note any equivalences we discover are context
241 sensitive (ie, are dependent on traversing E) and must be unwound
242 when we're finished processing E. */
243 for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
244 {
245 tree cached_lhs = NULL;
246
247 stmt = gsi_stmt (gsi);
248
249 /* Ignore empty statements and labels. */
250 if (gimple_code (stmt) == GIMPLE_NOP
251 || gimple_code (stmt) == GIMPLE_LABEL
252 || is_gimple_debug (stmt))
253 continue;
254
255 /* If the statement has volatile operands, then we assume we
256 can not thread through this block. This is overly
257 conservative in some ways. */
258 if (gimple_code (stmt) == GIMPLE_ASM
259 && gimple_asm_volatile_p (as_a <gasm *> (stmt)))
260 return NULL;
261
262 /* If the statement is a unique builtin, we can not thread
263 through here. */
264 if (gimple_code (stmt) == GIMPLE_CALL
265 && gimple_call_internal_p (stmt)
266 && gimple_call_internal_unique_p (stmt))
267 return NULL;
268
269 /* If duplicating this block is going to cause too much code
270 expansion, then do not thread through this block. */
271 stmt_count++;
272 if (stmt_count > max_stmt_count)
273 {
274 /* If any of the stmts in the PATH's dests are going to be
275 killed due to threading, grow the max count
276 accordingly. */
277 if (max_stmt_count
278 == PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS))
279 {
280 max_stmt_count += estimate_threading_killed_stmts (e->dest);
281 if (dump_file)
282 fprintf (dump_file, "threading bb %i up to %i stmts\n",
283 e->dest->index, max_stmt_count);
284 }
285 /* If we're still past the limit, we're done. */
286 if (stmt_count > max_stmt_count)
287 return NULL;
288 }
289
290 /* These are temporary ranges, do nto reflect them back into
291 the global range data. */
292 if (evrp_range_analyzer)
293 evrp_range_analyzer->record_ranges_from_stmt (stmt, true);
294
295 /* If this is not a statement that sets an SSA_NAME to a new
296 value, then do not try to simplify this statement as it will
297 not simplify in any way that is helpful for jump threading. */
298 if ((gimple_code (stmt) != GIMPLE_ASSIGN
299 || TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
300 && (gimple_code (stmt) != GIMPLE_CALL
301 || gimple_call_lhs (stmt) == NULL_TREE
302 || TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME))
303 continue;
304
305 /* The result of __builtin_object_size depends on all the arguments
306 of a phi node. Temporarily using only one edge produces invalid
307 results. For example
308
309 if (x < 6)
310 goto l;
311 else
312 goto l;
313
314 l:
315 r = PHI <&w[2].a[1](2), &a.a[6](3)>
316 __builtin_object_size (r, 0)
317
318 The result of __builtin_object_size is defined to be the maximum of
319 remaining bytes. If we use only one edge on the phi, the result will
320 change to be the remaining bytes for the corresponding phi argument.
321
322 Similarly for __builtin_constant_p:
323
324 r = PHI <1(2), 2(3)>
325 __builtin_constant_p (r)
326
327 Both PHI arguments are constant, but x ? 1 : 2 is still not
328 constant. */
329
330 if (is_gimple_call (stmt))
331 {
332 tree fndecl = gimple_call_fndecl (stmt);
333 if (fndecl
334 && (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_OBJECT_SIZE
335 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P))
336 continue;
337 }
338
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
342 allow us to simplify the condition at the end of the loop.
343
344 Handle simple copy operations as well as implied copies from
345 ASSERT_EXPRs. */
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);
352 else
353 {
354 /* A statement that is not a trivial copy or ASSERT_EXPR.
355 Try to fold the new expression. Inserting the
356 expression into the hash table is unlikely to help. */
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);
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))))
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 }
392
393 cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
394
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 }
400 }
401
402 /* Record the context sensitive equivalence if we were able
403 to simplify this statement. */
404 if (cached_lhs
405 && (TREE_CODE (cached_lhs) == SSA_NAME
406 || is_gimple_min_invariant (cached_lhs)))
407 const_and_copies->record_const_or_copy (gimple_get_lhs (stmt),
408 cached_lhs);
409 }
410 return stmt;
411 }
412
413 static tree simplify_control_stmt_condition_1 (edge, gimple *,
414 class avail_exprs_stack *,
415 tree, enum tree_code, tree,
416 gcond *, pfn_simplify,
417 unsigned);
418
419 /* Simplify the control statement at the end of the block E->dest.
420
421 To avoid allocating memory unnecessarily, a scratch GIMPLE_COND
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
428 not be performed. When simplifying a GIMPLE_SWITCH, we may return
429 the CASE_LABEL_EXPR that will be taken.
430
431 The available expression table is referenced via AVAIL_EXPRS_STACK. */
432
433 static tree
simplify_control_stmt_condition(edge e,gimple * stmt,class avail_exprs_stack * avail_exprs_stack,gcond * dummy_cond,pfn_simplify simplify)434 simplify_control_stmt_condition (edge e,
435 gimple *stmt,
436 class avail_exprs_stack *avail_exprs_stack,
437 gcond *dummy_cond,
438 pfn_simplify simplify)
439 {
440 tree cond, cached_lhs;
441 enum gimple_code code = gimple_code (stmt);
442
443 /* For comparisons, we have to update both operands, then try
444 to simplify the comparison. */
445 if (code == GIMPLE_COND)
446 {
447 tree op0, op1;
448 enum tree_code cond_code;
449
450 op0 = gimple_cond_lhs (stmt);
451 op1 = gimple_cond_rhs (stmt);
452 cond_code = gimple_cond_code (stmt);
453
454 /* Get the current value of both operands. */
455 if (TREE_CODE (op0) == SSA_NAME)
456 {
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 }
465 }
466
467 if (TREE_CODE (op1) == SSA_NAME)
468 {
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 }
477 }
478
479 const unsigned recursion_limit = 4;
480
481 cached_lhs
482 = simplify_control_stmt_condition_1 (e, stmt, avail_exprs_stack,
483 op0, cond_code, op1,
484 dummy_cond, simplify,
485 recursion_limit);
486
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)
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
501 if ((INTEGRAL_TYPE_P (TREE_TYPE (op0))
502 || POINTER_TYPE_P (TREE_TYPE (op0)))
503 && TREE_CODE (op0) == SSA_NAME
504 && TREE_CODE (op1) == INTEGER_CST)
505 return op0;
506 }
507
508 return cached_lhs;
509 }
510
511 if (code == GIMPLE_SWITCH)
512 cond = gimple_switch_index (as_a <gswitch *> (stmt));
513 else if (code == GIMPLE_GOTO)
514 cond = gimple_goto_dest (stmt);
515 else
516 gcc_unreachable ();
517
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. */
520 if (TREE_CODE (cond) == SSA_NAME)
521 {
522 tree original_lhs = cond;
523 cached_lhs = cond;
524
525 /* Get the variable's current value from the equivalence chains.
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
529 a loop invariant SSA_NAME used in the condition). */
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 }
541
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))
545 {
546 if (code == GIMPLE_SWITCH)
547 {
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. */
552 gswitch *dummy_switch = as_a<gswitch *> (gimple_copy (stmt));
553 gimple_switch_set_index (dummy_switch, cached_lhs);
554 cached_lhs = (*simplify) (dummy_switch, stmt,
555 avail_exprs_stack, e->src);
556 ggc_free (dummy_switch);
557 }
558 else
559 cached_lhs = (*simplify) (stmt, stmt, avail_exprs_stack, e->src);
560 }
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;
567 }
568 else
569 cached_lhs = NULL;
570
571 return cached_lhs;
572 }
573
574 /* Recursive helper for simplify_control_stmt_condition. */
575
576 static tree
simplify_control_stmt_condition_1(edge e,gimple * stmt,class avail_exprs_stack * avail_exprs_stack,tree op0,enum tree_code cond_code,tree op1,gcond * dummy_cond,pfn_simplify simplify,unsigned limit)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,
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. */
594 if (tree_swap_operands_p (op0, op1))
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. */
604 if ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
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);
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,
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)
630 return boolean_false_node;
631 /* If A == 0 then (A & B) == 0 is always true. */
632 if (cond_code == EQ_EXPR)
633 return boolean_true_node;
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)
639 return boolean_true_node;
640 /* If A != 0 then (A | B) == 0 is always false. */
641 if (cond_code == EQ_EXPR)
642 return boolean_false_node;
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,
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)
657 return boolean_false_node;
658 /* If B == 0 then (A & B) == 0 is always true. */
659 if (cond_code == EQ_EXPR)
660 return boolean_true_node;
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)
666 return boolean_true_node;
667 /* If B != 0 then (A | B) == 0 is always false. */
668 if (cond_code == EQ_EXPR)
669 return boolean_false_node;
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)
681 return boolean_true_node;
682 /* If A != 0 and B != 0 then (bool)(A & B) == 0 is false. */
683 if (cond_code == EQ_EXPR)
684 return boolean_false_node;
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)
693 return boolean_false_node;
694 /* If A == 0 and B == 0 then (A | B) == 0 is true. */
695 if (cond_code == EQ_EXPR)
696 return boolean_true_node;
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,
715 limit - 1);
716 if (res != NULL_TREE && is_gimple_min_invariant (res))
717 return res;
718 }
719 }
720
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))
741 res = (*simplify) (dummy_cond, stmt, avail_exprs_stack, e->src);
742
743 return res;
744 }
745
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. */
749 void
propagate_threaded_block_debug_into(basic_block dest,basic_block src)750 propagate_threaded_block_debug_into (basic_block dest, basic_block src)
751 {
752 if (!MAY_HAVE_DEBUG_BIND_STMTS)
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);
761 int i = 0;
762 const int alloc_count = 16; // ?? Should this be a PARAM?
763
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. */
766 for (gimple_stmt_iterator si = gsi;
767 i * 4 <= alloc_count * 3 && !gsi_end_p (si); gsi_next (&si))
768 {
769 gimple *stmt = gsi_stmt (si);
770 if (!is_gimple_debug (stmt))
771 break;
772 if (gimple_debug_nonbind_marker_p (stmt))
773 continue;
774 i++;
775 }
776
777 auto_vec<tree, alloc_count> fewvars;
778 hash_set<tree> *vars = NULL;
779
780 /* If we're already starting with 3/4 of alloc_count, go for a
781 hash_set, otherwise start with an unordered stack-allocated
782 VEC. */
783 if (i * 4 > alloc_count * 3)
784 vars = new hash_set<tree>;
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))
790 {
791 gimple *stmt = gsi_stmt (si);
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);
801 else if (gimple_debug_nonbind_marker_p (stmt))
802 continue;
803 else
804 gcc_unreachable ();
805
806 if (vars)
807 vars->add (var);
808 else
809 fewvars.quick_push (var);
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 {
820 gimple *stmt = gsi_stmt (si);
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);
830 else if (gimple_debug_nonbind_marker_p (stmt))
831 continue;
832 else
833 gcc_unreachable ();
834
835 /* Discard debug bind overlaps. Unlike stmts from src,
836 copied into a new block that will precede BB, debug bind
837 stmts in bypassed BBs may actually be discarded if
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. */
847 if (vars && vars->add (var))
848 continue;
849 else if (!vars)
850 {
851 int i = fewvars.length ();
852 while (i--)
853 if (fewvars[i] == var)
854 break;
855 if (i >= 0)
856 continue;
857 else if (fewvars.length () < (unsigned) alloc_count)
858 fewvars.quick_push (var);
859 else
860 {
861 vars = new hash_set<tree>;
862 for (i = 0; i < alloc_count; i++)
863 vars->add (fewvars[i]);
864 fewvars.release ();
865 vars->add (var);
866 }
867 }
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
877 if (vars)
878 delete vars;
879 else if (fewvars.exists ())
880 fewvars.release ();
881 }
882
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
890 DUMMY_COND, SIMPLIFY are used to try and simplify the condition at the
891 end of TAKEN_EDGE->dest.
892
893 The available expression table is referenced via AVAIL_EXPRS_STACK. */
894
895 static bool
thread_around_empty_blocks(edge taken_edge,gcond * dummy_cond,class avail_exprs_stack * avail_exprs_stack,pfn_simplify simplify,bitmap visited,vec<jump_thread_edge * > * path)896 thread_around_empty_blocks (edge taken_edge,
897 gcond *dummy_cond,
898 class avail_exprs_stack *avail_exprs_stack,
899 pfn_simplify simplify,
900 bitmap visited,
901 vec<jump_thread_edge *> *path)
902 {
903 basic_block bb = taken_edge->dest;
904 gimple_stmt_iterator gsi;
905 gimple *stmt;
906 tree cond;
907
908 /* The key property of these blocks is that they need not be duplicated
909 when threading. Thus they can not have visible side effects such
910 as PHI nodes. */
911 if (!gsi_end_p (gsi_start_phis (bb)))
912 return false;
913
914 /* Skip over DEBUG statements at the start of the block. */
915 gsi = gsi_start_nondebug_bb (bb);
916
917 /* If the block has no statements, but does have a single successor, then
918 it's just a forwarding block and we can thread through it trivially.
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
926 threading opportunity and FALSE otherwise.
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. */
931 if (gsi_end_p (gsi))
932 {
933 if (single_succ_p (bb))
934 {
935 taken_edge = single_succ_edge (bb);
936
937 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
938 return false;
939
940 if (!bitmap_bit_p (visited, taken_edge->dest->index))
941 {
942 jump_thread_edge *x
943 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
944 path->safe_push (x);
945 bitmap_set_bit (visited, taken_edge->dest->index);
946 return thread_around_empty_blocks (taken_edge,
947 dummy_cond,
948 avail_exprs_stack,
949 simplify,
950 visited,
951 path);
952 }
953 }
954
955 /* We have a block with no statements, but multiple successors? */
956 return false;
957 }
958
959 /* The only real statements this block can have are a control
960 flow altering statement. Anything else stops the thread. */
961 stmt = gsi_stmt (gsi);
962 if (gimple_code (stmt) != GIMPLE_COND
963 && gimple_code (stmt) != GIMPLE_GOTO
964 && gimple_code (stmt) != GIMPLE_SWITCH)
965 return false;
966
967 /* Extract and simplify the condition. */
968 cond = simplify_control_stmt_condition (taken_edge, stmt,
969 avail_exprs_stack, dummy_cond,
970 simplify);
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. */
975 if (cond != NULL_TREE
976 && (is_gimple_min_invariant (cond)
977 || TREE_CODE (cond) == CASE_LABEL_EXPR))
978 {
979 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
980 taken_edge = find_edge (bb, label_to_block (CASE_LABEL (cond)));
981 else
982 taken_edge = find_taken_edge (bb, cond);
983
984 if ((taken_edge->flags & EDGE_DFS_BACK) != 0)
985 return false;
986
987 if (bitmap_bit_p (visited, taken_edge->dest->index))
988 return false;
989 bitmap_set_bit (visited, taken_edge->dest->index);
990
991 jump_thread_edge *x
992 = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
993 path->safe_push (x);
994
995 thread_around_empty_blocks (taken_edge,
996 dummy_cond,
997 avail_exprs_stack,
998 simplify,
999 visited,
1000 path);
1001 return true;
1002 }
1003
1004 return false;
1005 }
1006
1007 /* We are exiting E->src, see if E->dest ends with a conditional
1008 jump which has a known value when reached via E.
1009
1010 E->dest can have arbitrary side effects which, if threading is
1011 successful, will be maintained.
1012
1013 Special care is necessary if E is a back edge in the CFG as we
1014 may have already recorded equivalences for E->dest into our
1015 various tables, including the result of the conditional at
1016 the end of E->dest. Threading opportunities are severely
1017 limited in that case to avoid short-circuiting the loop
1018 incorrectly.
1019
1020 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1021 to avoid allocating memory.
1022
1023 STACK is used to undo temporary equivalences created during the walk of
1024 E->dest.
1025
1026 SIMPLIFY is a pass-specific function used to simplify statements.
1027
1028 Our caller is responsible for restoring the state of the expression
1029 and const_and_copies stacks.
1030
1031 Positive return value is success. Zero return value is failure, but
1032 the block can still be duplicated as a joiner in a jump thread path,
1033 negative indicates the block should not be duplicated and thus is not
1034 suitable for a joiner in a jump threading path. */
1035
1036 static int
thread_through_normal_block(edge e,gcond * dummy_cond,const_and_copies * const_and_copies,avail_exprs_stack * avail_exprs_stack,evrp_range_analyzer * evrp_range_analyzer,pfn_simplify simplify,vec<jump_thread_edge * > * path,bitmap visited)1037 thread_through_normal_block (edge e,
1038 gcond *dummy_cond,
1039 const_and_copies *const_and_copies,
1040 avail_exprs_stack *avail_exprs_stack,
1041 evrp_range_analyzer *evrp_range_analyzer,
1042 pfn_simplify simplify,
1043 vec<jump_thread_edge *> *path,
1044 bitmap visited)
1045 {
1046 /* We want to record any equivalences created by traversing E. */
1047 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack);
1048
1049 /* PHIs create temporary equivalences.
1050 Note that if we found a PHI that made the block non-threadable, then
1051 we need to bubble that up to our caller in the same manner we do
1052 when we prematurely stop processing statements below. */
1053 if (!record_temporary_equivalences_from_phis (e, const_and_copies,
1054 evrp_range_analyzer))
1055 return -1;
1056
1057 /* Now walk each statement recording any context sensitive
1058 temporary equivalences we can detect. */
1059 gimple *stmt
1060 = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies,
1061 avail_exprs_stack,
1062 evrp_range_analyzer,
1063 simplify);
1064
1065 /* There's two reasons STMT might be null, and distinguishing
1066 between them is important.
1067
1068 First the block may not have had any statements. For example, it
1069 might have some PHIs and unconditionally transfer control elsewhere.
1070 Such blocks are suitable for jump threading, particularly as a
1071 joiner block.
1072
1073 The second reason would be if we did not process all the statements
1074 in the block (because there were too many to make duplicating the
1075 block profitable. If we did not look at all the statements, then
1076 we may not have invalidated everything needing invalidation. Thus
1077 we must signal to our caller that this block is not suitable for
1078 use as a joiner in a threading path. */
1079 if (!stmt)
1080 {
1081 /* First case. The statement simply doesn't have any instructions, but
1082 does have PHIs. */
1083 if (gsi_end_p (gsi_start_nondebug_bb (e->dest))
1084 && !gsi_end_p (gsi_start_phis (e->dest)))
1085 return 0;
1086
1087 /* Second case. */
1088 return -1;
1089 }
1090
1091 /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
1092 will be taken. */
1093 if (gimple_code (stmt) == GIMPLE_COND
1094 || gimple_code (stmt) == GIMPLE_GOTO
1095 || gimple_code (stmt) == GIMPLE_SWITCH)
1096 {
1097 tree cond;
1098
1099 /* Extract and simplify the condition. */
1100 cond = simplify_control_stmt_condition (e, stmt, avail_exprs_stack,
1101 dummy_cond, simplify);
1102
1103 if (!cond)
1104 return 0;
1105
1106 if (is_gimple_min_invariant (cond)
1107 || TREE_CODE (cond) == CASE_LABEL_EXPR)
1108 {
1109 edge taken_edge;
1110 if (TREE_CODE (cond) == CASE_LABEL_EXPR)
1111 taken_edge = find_edge (e->dest,
1112 label_to_block (CASE_LABEL (cond)));
1113 else
1114 taken_edge = find_taken_edge (e->dest, cond);
1115
1116 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
1117
1118 /* DEST could be NULL for a computed jump to an absolute
1119 address. */
1120 if (dest == NULL
1121 || dest == e->dest
1122 || (taken_edge->flags & EDGE_DFS_BACK) != 0
1123 || bitmap_bit_p (visited, dest->index))
1124 return 0;
1125
1126 /* Only push the EDGE_START_JUMP_THREAD marker if this is
1127 first edge on the path. */
1128 if (path->length () == 0)
1129 {
1130 jump_thread_edge *x
1131 = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1132 path->safe_push (x);
1133 }
1134
1135 jump_thread_edge *x
1136 = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_BLOCK);
1137 path->safe_push (x);
1138
1139 /* See if we can thread through DEST as well, this helps capture
1140 secondary effects of threading without having to re-run DOM or
1141 VRP.
1142
1143 We don't want to thread back to a block we have already
1144 visited. This may be overly conservative. */
1145 bitmap_set_bit (visited, dest->index);
1146 bitmap_set_bit (visited, e->dest->index);
1147 thread_around_empty_blocks (taken_edge,
1148 dummy_cond,
1149 avail_exprs_stack,
1150 simplify,
1151 visited,
1152 path);
1153 return 1;
1154 }
1155 }
1156 return 0;
1157 }
1158
1159 /* We are exiting E->src, see if E->dest ends with a conditional
1160 jump which has a known value when reached via E.
1161
1162 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1163 to avoid allocating memory.
1164
1165 CONST_AND_COPIES is used to undo temporary equivalences created during the
1166 walk of E->dest.
1167
1168 The available expression table is referenced vai AVAIL_EXPRS_STACK.
1169
1170 SIMPLIFY is a pass-specific function used to simplify statements. */
1171
1172 static void
thread_across_edge(gcond * dummy_cond,edge e,class const_and_copies * const_and_copies,class avail_exprs_stack * avail_exprs_stack,class evrp_range_analyzer * evrp_range_analyzer,pfn_simplify simplify)1173 thread_across_edge (gcond *dummy_cond,
1174 edge e,
1175 class const_and_copies *const_and_copies,
1176 class avail_exprs_stack *avail_exprs_stack,
1177 class evrp_range_analyzer *evrp_range_analyzer,
1178 pfn_simplify simplify)
1179 {
1180 bitmap visited = BITMAP_ALLOC (NULL);
1181
1182 const_and_copies->push_marker ();
1183 avail_exprs_stack->push_marker ();
1184 if (evrp_range_analyzer)
1185 evrp_range_analyzer->push_marker ();
1186
1187 stmt_count = 0;
1188
1189 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1190 bitmap_clear (visited);
1191 bitmap_set_bit (visited, e->src->index);
1192 bitmap_set_bit (visited, e->dest->index);
1193
1194 int threaded;
1195 if ((e->flags & EDGE_DFS_BACK) == 0)
1196 threaded = thread_through_normal_block (e, dummy_cond,
1197 const_and_copies,
1198 avail_exprs_stack,
1199 evrp_range_analyzer,
1200 simplify, path,
1201 visited);
1202 else
1203 threaded = 0;
1204
1205 if (threaded > 0)
1206 {
1207 propagate_threaded_block_debug_into (path->last ()->e->dest,
1208 e->dest);
1209 const_and_copies->pop_to_marker ();
1210 avail_exprs_stack->pop_to_marker ();
1211 if (evrp_range_analyzer)
1212 evrp_range_analyzer->pop_to_marker ();
1213 BITMAP_FREE (visited);
1214 register_jump_thread (path);
1215 return;
1216 }
1217 else
1218 {
1219 /* Negative and zero return values indicate no threading was possible,
1220 thus there should be no edges on the thread path and no need to walk
1221 through the vector entries. */
1222 gcc_assert (path->length () == 0);
1223 path->release ();
1224 delete path;
1225
1226 /* A negative status indicates the target block was deemed too big to
1227 duplicate. Just quit now rather than trying to use the block as
1228 a joiner in a jump threading path.
1229
1230 This prevents unnecessary code growth, but more importantly if we
1231 do not look at all the statements in the block, then we may have
1232 missed some invalidations if we had traversed a backedge! */
1233 if (threaded < 0)
1234 {
1235 BITMAP_FREE (visited);
1236 const_and_copies->pop_to_marker ();
1237 avail_exprs_stack->pop_to_marker ();
1238 if (evrp_range_analyzer)
1239 evrp_range_analyzer->pop_to_marker ();
1240 return;
1241 }
1242 }
1243
1244 /* We were unable to determine what out edge from E->dest is taken. However,
1245 we might still be able to thread through successors of E->dest. This
1246 often occurs when E->dest is a joiner block which then fans back out
1247 based on redundant tests.
1248
1249 If so, we'll copy E->dest and redirect the appropriate predecessor to
1250 the copy. Within the copy of E->dest, we'll thread one or more edges
1251 to points deeper in the CFG.
1252
1253 This is a stopgap until we have a more structured approach to path
1254 isolation. */
1255 {
1256 edge taken_edge;
1257 edge_iterator ei;
1258 bool found;
1259
1260 /* If E->dest has abnormal outgoing edges, then there's no guarantee
1261 we can safely redirect any of the edges. Just punt those cases. */
1262 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1263 if (taken_edge->flags & EDGE_ABNORMAL)
1264 {
1265 const_and_copies->pop_to_marker ();
1266 avail_exprs_stack->pop_to_marker ();
1267 if (evrp_range_analyzer)
1268 evrp_range_analyzer->pop_to_marker ();
1269 BITMAP_FREE (visited);
1270 return;
1271 }
1272
1273 /* Look at each successor of E->dest to see if we can thread through it. */
1274 FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
1275 {
1276 if ((e->flags & EDGE_DFS_BACK) != 0
1277 || (taken_edge->flags & EDGE_DFS_BACK) != 0)
1278 continue;
1279
1280 /* Push a fresh marker so we can unwind the equivalences created
1281 for each of E->dest's successors. */
1282 const_and_copies->push_marker ();
1283 avail_exprs_stack->push_marker ();
1284 if (evrp_range_analyzer)
1285 evrp_range_analyzer->push_marker ();
1286
1287 /* Avoid threading to any block we have already visited. */
1288 bitmap_clear (visited);
1289 bitmap_set_bit (visited, e->src->index);
1290 bitmap_set_bit (visited, e->dest->index);
1291 bitmap_set_bit (visited, taken_edge->dest->index);
1292 vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
1293
1294 /* Record whether or not we were able to thread through a successor
1295 of E->dest. */
1296 jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
1297 path->safe_push (x);
1298
1299 x = new jump_thread_edge (taken_edge, EDGE_COPY_SRC_JOINER_BLOCK);
1300 path->safe_push (x);
1301 found = false;
1302 found = thread_around_empty_blocks (taken_edge,
1303 dummy_cond,
1304 avail_exprs_stack,
1305 simplify,
1306 visited,
1307 path);
1308
1309 if (!found)
1310 found = thread_through_normal_block (path->last ()->e, dummy_cond,
1311 const_and_copies,
1312 avail_exprs_stack,
1313 evrp_range_analyzer,
1314 simplify, path,
1315 visited) > 0;
1316
1317 /* If we were able to thread through a successor of E->dest, then
1318 record the jump threading opportunity. */
1319 if (found)
1320 {
1321 propagate_threaded_block_debug_into (path->last ()->e->dest,
1322 taken_edge->dest);
1323 register_jump_thread (path);
1324 }
1325 else
1326 delete_jump_thread_path (path);
1327
1328 /* And unwind the equivalence table. */
1329 if (evrp_range_analyzer)
1330 evrp_range_analyzer->pop_to_marker ();
1331 avail_exprs_stack->pop_to_marker ();
1332 const_and_copies->pop_to_marker ();
1333 }
1334 BITMAP_FREE (visited);
1335 }
1336
1337 if (evrp_range_analyzer)
1338 evrp_range_analyzer->pop_to_marker ();
1339 const_and_copies->pop_to_marker ();
1340 avail_exprs_stack->pop_to_marker ();
1341 }
1342
1343 /* Examine the outgoing edges from BB and conditionally
1344 try to thread them.
1345
1346 DUMMY_COND is a shared cond_expr used by condition simplification as scratch,
1347 to avoid allocating memory.
1348
1349 CONST_AND_COPIES is used to undo temporary equivalences created during the
1350 walk of E->dest.
1351
1352 The available expression table is referenced vai AVAIL_EXPRS_STACK.
1353
1354 SIMPLIFY is a pass-specific function used to simplify statements. */
1355
1356 void
thread_outgoing_edges(basic_block bb,gcond * dummy_cond,class const_and_copies * const_and_copies,class avail_exprs_stack * avail_exprs_stack,class evrp_range_analyzer * evrp_range_analyzer,tree (* simplify)(gimple *,gimple *,class avail_exprs_stack *,basic_block))1357 thread_outgoing_edges (basic_block bb, gcond *dummy_cond,
1358 class const_and_copies *const_and_copies,
1359 class avail_exprs_stack *avail_exprs_stack,
1360 class evrp_range_analyzer *evrp_range_analyzer,
1361 tree (*simplify) (gimple *, gimple *,
1362 class avail_exprs_stack *,
1363 basic_block))
1364 {
1365 int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
1366 gimple *last;
1367
1368 /* If we have an outgoing edge to a block with multiple incoming and
1369 outgoing edges, then we may be able to thread the edge, i.e., we
1370 may be able to statically determine which of the outgoing edges
1371 will be traversed when the incoming edge from BB is traversed. */
1372 if (single_succ_p (bb)
1373 && (single_succ_edge (bb)->flags & flags) == 0
1374 && potentially_threadable_block (single_succ (bb)))
1375 {
1376 thread_across_edge (dummy_cond, single_succ_edge (bb),
1377 const_and_copies, avail_exprs_stack,
1378 evrp_range_analyzer, simplify);
1379 }
1380 else if ((last = last_stmt (bb))
1381 && gimple_code (last) == GIMPLE_COND
1382 && EDGE_COUNT (bb->succs) == 2
1383 && (EDGE_SUCC (bb, 0)->flags & flags) == 0
1384 && (EDGE_SUCC (bb, 1)->flags & flags) == 0)
1385 {
1386 edge true_edge, false_edge;
1387
1388 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1389
1390 /* Only try to thread the edge if it reaches a target block with
1391 more than one predecessor and more than one successor. */
1392 if (potentially_threadable_block (true_edge->dest))
1393 thread_across_edge (dummy_cond, true_edge,
1394 const_and_copies, avail_exprs_stack,
1395 evrp_range_analyzer, simplify);
1396
1397 /* Similarly for the ELSE arm. */
1398 if (potentially_threadable_block (false_edge->dest))
1399 thread_across_edge (dummy_cond, false_edge,
1400 const_and_copies, avail_exprs_stack,
1401 evrp_range_analyzer, simplify);
1402 }
1403 }
1404