Line data Source code
1 : /* Thread edges through blocks and update the control flow and SSA graphs.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "tree.h"
25 : #include "gimple.h"
26 : #include "cfghooks.h"
27 : #include "tree-pass.h"
28 : #include "ssa.h"
29 : #include "fold-const.h"
30 : #include "cfganal.h"
31 : #include "gimple-iterator.h"
32 : #include "tree-ssa.h"
33 : #include "tree-ssa-threadupdate.h"
34 : #include "cfgloop.h"
35 : #include "dbgcnt.h"
36 : #include "tree-cfg.h"
37 : #include "tree-vectorizer.h"
38 :
39 : /* Given a block B, update the CFG and SSA graph to reflect redirecting
40 : one or more in-edges to B to instead reach the destination of an
41 : out-edge from B while preserving any side effects in B.
42 :
43 : i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
44 : side effects of executing B.
45 :
46 : 1. Make a copy of B (including its outgoing edges and statements). Call
47 : the copy B'. Note B' has no incoming edges or PHIs at this time.
48 :
49 : 2. Remove the control statement at the end of B' and all outgoing edges
50 : except B'->C.
51 :
52 : 3. Add a new argument to each PHI in C with the same value as the existing
53 : argument associated with edge B->C. Associate the new PHI arguments
54 : with the edge B'->C.
55 :
56 : 4. For each PHI in B, find or create a PHI in B' with an identical
57 : PHI_RESULT. Add an argument to the PHI in B' which has the same
58 : value as the PHI in B associated with the edge A->B. Associate
59 : the new argument in the PHI in B' with the edge A->B.
60 :
61 : 5. Change the edge A->B to A->B'.
62 :
63 : 5a. This automatically deletes any PHI arguments associated with the
64 : edge A->B in B.
65 :
66 : 5b. This automatically associates each new argument added in step 4
67 : with the edge A->B'.
68 :
69 : 6. Repeat for other incoming edges into B.
70 :
71 : 7. Put the duplicated resources in B and all the B' blocks into SSA form.
72 :
73 : Note that block duplication can be minimized by first collecting the
74 : set of unique destination blocks that the incoming edges should
75 : be threaded to.
76 :
77 : We reduce the number of edges and statements we create by not copying all
78 : the outgoing edges and the control statement in step #1. We instead create
79 : a template block without the outgoing edges and duplicate the template.
80 :
81 : Another case this code handles is threading through a "joiner" block. In
82 : this case, we do not know the destination of the joiner block, but one
83 : of the outgoing edges from the joiner block leads to a threadable path. This
84 : case largely works as outlined above, except the duplicate of the joiner
85 : block still contains a full set of outgoing edges and its control statement.
86 : We just redirect one of its outgoing edges to our jump threading path. */
87 :
88 :
89 : /* Steps #5 and #6 of the above algorithm are best implemented by walking
90 : all the incoming edges which thread to the same destination edge at
91 : the same time. That avoids lots of table lookups to get information
92 : for the destination edge.
93 :
94 : To realize that implementation we create a list of incoming edges
95 : which thread to the same outgoing edge. Thus to implement steps
96 : #5 and #6 we traverse our hash table of outgoing edge information.
97 : For each entry we walk the list of incoming edges which thread to
98 : the current outgoing edge. */
99 :
100 : struct el
101 : {
102 : edge e;
103 : struct el *next;
104 : };
105 :
106 : /* Main data structure recording information regarding B's duplicate
107 : blocks. */
108 :
109 : /* We need to efficiently record the unique thread destinations of this
110 : block and specific information associated with those destinations. We
111 : may have many incoming edges threaded to the same outgoing edge. This
112 : can be naturally implemented with a hash table. */
113 :
114 : struct redirection_data : free_ptr_hash<redirection_data>
115 : {
116 : /* We support wiring up two block duplicates in a jump threading path.
117 :
118 : One is a normal block copy where we remove the control statement
119 : and wire up its single remaining outgoing edge to the thread path.
120 :
121 : The other is a joiner block where we leave the control statement
122 : in place, but wire one of the outgoing edges to a thread path.
123 :
124 : In theory we could have multiple block duplicates in a jump
125 : threading path, but I haven't tried that.
126 :
127 : The duplicate blocks appear in this array in the same order in
128 : which they appear in the jump thread path. */
129 : basic_block dup_blocks[2];
130 :
131 : vec<jump_thread_edge *> *path;
132 :
133 : /* A list of incoming edges which we want to thread to the
134 : same path. */
135 : struct el *incoming_edges;
136 :
137 : /* hash_table support. */
138 : static inline hashval_t hash (const redirection_data *);
139 : static inline int equal (const redirection_data *, const redirection_data *);
140 : };
141 :
142 8659979 : jump_thread_path_allocator::jump_thread_path_allocator ()
143 : {
144 8659979 : obstack_init (&m_obstack);
145 8659979 : }
146 :
147 8659979 : jump_thread_path_allocator::~jump_thread_path_allocator ()
148 : {
149 8659979 : obstack_free (&m_obstack, NULL);
150 8659979 : }
151 :
152 : jump_thread_edge *
153 28584892 : jump_thread_path_allocator::allocate_thread_edge (edge e,
154 : jump_thread_edge_type type)
155 : {
156 28584892 : void *r = obstack_alloc (&m_obstack, sizeof (jump_thread_edge));
157 28584892 : return new (r) jump_thread_edge (e, type);
158 : }
159 :
160 : vec<jump_thread_edge *> *
161 19825952 : jump_thread_path_allocator::allocate_thread_path ()
162 : {
163 : // ?? Since the paths live in an obstack, we should be able to remove all
164 : // references to path->release() throughout the code.
165 19825952 : void *r = obstack_alloc (&m_obstack, sizeof (vec <jump_thread_edge *>));
166 19825952 : return new (r) vec<jump_thread_edge *> ();
167 : }
168 :
169 8659979 : jt_path_registry::jt_path_registry (bool backedge_threads)
170 : {
171 8659979 : m_paths.create (5);
172 8659979 : m_num_threaded_edges = 0;
173 8659979 : m_backedge_threads = backedge_threads;
174 8659979 : }
175 :
176 8659979 : jt_path_registry::~jt_path_registry ()
177 : {
178 8659979 : m_paths.release ();
179 8659979 : }
180 :
181 : /* Drop path PATHNO, which started on FIRST, keeping the first-edge
182 : counts in step. For callers whose path has already been released. */
183 :
184 : void
185 1644825 : jt_path_registry::remove_path (unsigned pathno, edge first)
186 : {
187 1644825 : drop_first_edge (first);
188 1644825 : m_paths.unordered_remove (pathno);
189 1644825 : }
190 :
191 : /* Drop path PATHNO, keeping the first-edge counts in step. */
192 :
193 : void
194 282755 : jt_path_registry::remove_path (unsigned pathno)
195 : {
196 282755 : remove_path (pathno, (*m_paths[pathno])[0]->e);
197 282755 : }
198 :
199 : /* Note that one more registered path starts on E. */
200 :
201 : void
202 2051575 : jt_path_registry::add_first_edge (edge e)
203 : {
204 2051575 : ++m_first_edge_counts.get_or_insert (e);
205 2051575 : }
206 :
207 : /* Note that one fewer registered path starts on E. */
208 :
209 : void
210 1690344 : jt_path_registry::drop_first_edge (edge e)
211 : {
212 1690344 : unsigned *count = m_first_edge_counts.get (e);
213 1690344 : gcc_checking_assert (*count > 0);
214 1690344 : if (--*count == 0)
215 1534382 : m_first_edge_counts.remove (e);
216 1690344 : }
217 :
218 : /* How many registered paths start on E. */
219 :
220 : unsigned
221 1333948 : jt_path_registry::first_edge_count (edge e)
222 : {
223 1333948 : unsigned *count = m_first_edge_counts.get (e);
224 1333948 : gcc_checking_assert (*count > 0);
225 1333948 : return *count;
226 : }
227 :
228 2136688 : fwd_jt_path_registry::fwd_jt_path_registry ()
229 2136688 : : jt_path_registry (/*backedge_threads=*/false)
230 : {
231 2136688 : m_removed_edges = new hash_table<struct removed_edges> (17);
232 2136688 : m_redirection_data = NULL;
233 2136688 : }
234 :
235 4273376 : fwd_jt_path_registry::~fwd_jt_path_registry ()
236 : {
237 2136688 : delete m_removed_edges;
238 4273376 : }
239 :
240 6523291 : back_jt_path_registry::back_jt_path_registry ()
241 6523291 : : jt_path_registry (/*backedge_threads=*/true)
242 : {
243 6523291 : }
244 :
245 : void
246 28584892 : jt_path_registry::push_edge (vec<jump_thread_edge *> *path,
247 : edge e, jump_thread_edge_type type)
248 : {
249 28584892 : jump_thread_edge *x = m_allocator.allocate_thread_edge (e, type);
250 28584892 : path->safe_push (x);
251 28584892 : }
252 :
253 : vec<jump_thread_edge *> *
254 19825952 : jt_path_registry::allocate_thread_path ()
255 : {
256 19825952 : return m_allocator.allocate_thread_path ();
257 : }
258 :
259 : /* Dump a jump threading path, including annotations about each
260 : edge in the path. */
261 :
262 : static void
263 237 : dump_jump_thread_path (FILE *dump_file,
264 : const vec<jump_thread_edge *> &path,
265 : bool registering)
266 : {
267 237 : if (registering)
268 310 : fprintf (dump_file,
269 : " [%u] Registering jump thread: (%d, %d) incoming edge; ",
270 : dbg_cnt_counter (registered_jump_thread),
271 155 : path[0]->e->src->index, path[0]->e->dest->index);
272 : else
273 82 : fprintf (dump_file,
274 : " Cancelling jump thread: (%d, %d) incoming edge; ",
275 82 : path[0]->e->src->index, path[0]->e->dest->index);
276 :
277 731 : for (unsigned int i = 1; i < path.length (); i++)
278 : {
279 : /* We can get paths with a NULL edge when the final destination
280 : of a jump thread turns out to be a constant address. We dump
281 : those paths when debugging, so we have to be prepared for that
282 : possibility here. */
283 494 : if (path[i]->e == NULL)
284 0 : continue;
285 :
286 494 : fprintf (dump_file, " (%d, %d) ",
287 494 : path[i]->e->src->index, path[i]->e->dest->index);
288 494 : switch (path[i]->type)
289 : {
290 47 : case EDGE_COPY_SRC_JOINER_BLOCK:
291 47 : fprintf (dump_file, "joiner");
292 47 : break;
293 260 : case EDGE_COPY_SRC_BLOCK:
294 260 : fprintf (dump_file, "normal");
295 260 : break;
296 187 : case EDGE_NO_COPY_SRC_BLOCK:
297 187 : fprintf (dump_file, "nocopy");
298 187 : break;
299 0 : default:
300 0 : gcc_unreachable ();
301 : }
302 :
303 494 : if ((path[i]->e->flags & EDGE_DFS_BACK) != 0)
304 32 : fprintf (dump_file, " (back)");
305 : }
306 237 : fprintf (dump_file, "; \n");
307 237 : }
308 :
309 : DEBUG_FUNCTION void
310 0 : debug (const vec<jump_thread_edge *> &path)
311 : {
312 0 : dump_jump_thread_path (stderr, path, true);
313 0 : }
314 :
315 : DEBUG_FUNCTION void
316 0 : debug (const vec<jump_thread_edge *> *path)
317 : {
318 0 : debug (*path);
319 0 : }
320 :
321 : /* Release the memory associated with PATH, and if dumping is enabled,
322 : dump out the reason why the thread was canceled. */
323 :
324 : static void
325 2119819 : cancel_thread (vec<jump_thread_edge *> *path, const char *reason = NULL)
326 : {
327 2119819 : if (dump_file && (dump_flags & TDF_DETAILS))
328 : {
329 82 : if (reason)
330 72 : fprintf (dump_file, "%s: ", reason);
331 :
332 82 : dump_jump_thread_path (dump_file, *path, false);
333 82 : fprintf (dump_file, "\n");
334 : }
335 2119819 : path->release ();
336 2119819 : }
337 :
338 : /* Simple hashing function. For any given incoming edge E, we're going
339 : to be most concerned with the final destination of its jump thread
340 : path. So hash on the block index of the final edge in the path. */
341 :
342 : inline hashval_t
343 398435 : redirection_data::hash (const redirection_data *p)
344 : {
345 398435 : vec<jump_thread_edge *> *path = p->path;
346 398435 : return path->last ()->e->dest->index;
347 : }
348 :
349 : /* Given two hash table entries, return true if they have the same
350 : jump threading path. */
351 : inline int
352 105279 : redirection_data::equal (const redirection_data *p1, const redirection_data *p2)
353 : {
354 105279 : vec<jump_thread_edge *> *path1 = p1->path;
355 105279 : vec<jump_thread_edge *> *path2 = p2->path;
356 :
357 315837 : if (path1->length () != path2->length ())
358 : return false;
359 :
360 194221 : for (unsigned int i = 1; i < path1->length (); i++)
361 : {
362 139858 : if ((*path1)[i]->type != (*path2)[i]->type
363 139858 : || (*path1)[i]->e != (*path2)[i]->e)
364 : return false;
365 : }
366 :
367 : return true;
368 : }
369 :
370 : /* Data structure of information to pass to hash table traversal routines. */
371 : struct ssa_local_info_t
372 : {
373 : /* The current block we are working on. */
374 : basic_block bb;
375 :
376 : /* We only create a template block for the first duplicated block in a
377 : jump threading path as we may need many duplicates of that block.
378 :
379 : The second duplicate block in a path is specific to that path. Creating
380 : and sharing a template for that block is considerably more difficult. */
381 : basic_block template_block;
382 :
383 : /* If we append debug stmts to the template block after creating it,
384 : this iterator won't be the last one in the block, and further
385 : copies of the template block shouldn't get debug stmts after
386 : it. */
387 : gimple_stmt_iterator template_last_to_copy;
388 :
389 : /* Blocks duplicated for the thread. */
390 : bitmap duplicate_blocks;
391 :
392 : /* TRUE if we thread one or more jumps, FALSE otherwise. */
393 : bool jumps_threaded;
394 :
395 : /* When we have multiple paths through a joiner which reach different
396 : final destinations, then we may need to correct for potential
397 : profile insanities. */
398 : bool need_profile_correction;
399 :
400 : // Jump threading statistics.
401 : unsigned long num_threaded_edges;
402 : };
403 :
404 : /* When we start updating the CFG for threading, data necessary for jump
405 : threading is attached to the AUX field for the incoming edge. Use these
406 : macros to access the underlying structure attached to the AUX field. */
407 : #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
408 :
409 : /* Remove the last statement in block BB if it is a control statement
410 : Also remove all outgoing edges except the edge which reaches DEST_BB.
411 : If DEST_BB is NULL, then remove all outgoing edges. */
412 :
413 : static void
414 1559671 : remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
415 : {
416 1559671 : gimple_stmt_iterator gsi;
417 1559671 : edge e;
418 1559671 : edge_iterator ei;
419 :
420 1559671 : gsi = gsi_last_bb (bb);
421 :
422 : /* If the duplicate ends with a control statement, then remove it.
423 :
424 : Note that if we are duplicating the template block rather than the
425 : original basic block, then the duplicate might not have any real
426 : statements in it. */
427 1559671 : if (!gsi_end_p (gsi)
428 1559671 : && gsi_stmt (gsi)
429 1559671 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
430 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
431 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH))
432 1559671 : gsi_remove (&gsi, true);
433 :
434 4695226 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
435 : {
436 3135555 : if (e->dest != dest_bb)
437 : {
438 1801607 : free_dom_edge_info (e);
439 1801607 : remove_edge (e);
440 : }
441 : else
442 : {
443 1333948 : e->probability = profile_probability::always ();
444 1333948 : ei_next (&ei);
445 : }
446 : }
447 :
448 : /* If the remaining edge is a loop exit, there must have
449 : a removed edge that was not a loop exit.
450 :
451 : In that case BB and possibly other blocks were previously
452 : in the loop, but are now outside the loop. Thus, we need
453 : to update the loop structures. */
454 1559671 : if (single_succ_p (bb)
455 1333948 : && loop_outer (bb->loop_father)
456 1930124 : && loop_exit_edge_p (bb->loop_father, single_succ_edge (bb)))
457 62366 : loops_state_set (LOOPS_NEED_FIXUP);
458 1559671 : }
459 :
460 : /* Create a duplicate of BB. Record the duplicate block in an array
461 : indexed by COUNT stored in RD. */
462 :
463 : static void
464 283152 : create_block_for_threading (basic_block bb,
465 : struct redirection_data *rd,
466 : unsigned int count,
467 : bitmap *duplicate_blocks)
468 : {
469 283152 : edge_iterator ei;
470 283152 : edge e;
471 :
472 : /* We can use the generic block duplication code and simply remove
473 : the stuff we do not need. */
474 283152 : rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
475 :
476 861815 : FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
477 : {
478 578663 : e->aux = NULL;
479 :
480 : /* If we duplicate a block with an outgoing edge marked as
481 : EDGE_IGNORE, we must clear EDGE_IGNORE so that it doesn't
482 : leak out of the current pass.
483 :
484 : It would be better to simplify switch statements and remove
485 : the edges before we get here, but the sequencing is nontrivial. */
486 578663 : e->flags &= ~EDGE_IGNORE;
487 : }
488 :
489 : /* Zero out the profile, since the block is unreachable for now. */
490 283152 : rd->dup_blocks[count]->count = profile_count::uninitialized ();
491 283152 : if (duplicate_blocks)
492 283152 : bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
493 283152 : }
494 :
495 : /* Given an outgoing edge E lookup and return its entry in our hash table.
496 :
497 : If INSERT is true, then we insert the entry into the hash table if
498 : it is not already present. INCOMING_EDGE is added to the list of incoming
499 : edges associated with E in the hash table. */
500 :
501 : redirection_data *
502 294719 : fwd_jt_path_registry::lookup_redirection_data (edge e, insert_option insert)
503 : {
504 294719 : struct redirection_data **slot;
505 294719 : struct redirection_data *elt;
506 294719 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
507 :
508 : /* Build a hash table element so we can see if E is already
509 : in the table. */
510 294719 : elt = XNEW (struct redirection_data);
511 294719 : elt->path = path;
512 294719 : elt->dup_blocks[0] = NULL;
513 294719 : elt->dup_blocks[1] = NULL;
514 294719 : elt->incoming_edges = NULL;
515 :
516 294719 : slot = m_redirection_data->find_slot (elt, insert);
517 :
518 : /* This will only happen if INSERT is false and the entry is not
519 : in the hash table. */
520 294719 : if (slot == NULL)
521 : {
522 0 : free (elt);
523 0 : return NULL;
524 : }
525 :
526 : /* This will only happen if E was not in the hash table and
527 : INSERT is true. */
528 294719 : if (*slot == NULL)
529 : {
530 240356 : *slot = elt;
531 240356 : elt->incoming_edges = XNEW (struct el);
532 240356 : elt->incoming_edges->e = e;
533 240356 : elt->incoming_edges->next = NULL;
534 240356 : return elt;
535 : }
536 : /* E was in the hash table. */
537 : else
538 : {
539 : /* Free ELT as we do not need it anymore, we will extract the
540 : relevant entry from the hash table itself. */
541 54363 : free (elt);
542 :
543 : /* Get the entry stored in the hash table. */
544 54363 : elt = *slot;
545 :
546 : /* If insertion was requested, then we need to add INCOMING_EDGE
547 : to the list of incoming edges associated with E. */
548 54363 : if (insert)
549 : {
550 54363 : struct el *el = XNEW (struct el);
551 54363 : el->next = elt->incoming_edges;
552 54363 : el->e = e;
553 54363 : elt->incoming_edges = el;
554 : }
555 :
556 : return elt;
557 : }
558 : }
559 :
560 : /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
561 : to see if it has constant value in a flow sensitive manner. Set
562 : LOCUS to location of the constant phi arg and return the value.
563 : Return DEF directly if either PATH or idx is ZERO. */
564 :
565 : static tree
566 113486 : get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
567 : basic_block bb, int idx, location_t *locus)
568 : {
569 113486 : tree arg;
570 113486 : gphi *def_phi;
571 113486 : basic_block def_bb;
572 :
573 113486 : if (path == NULL || idx == 0)
574 : return def;
575 :
576 89795 : def_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (def));
577 64182 : if (!def_phi)
578 : return def;
579 :
580 64182 : def_bb = gimple_bb (def_phi);
581 : /* Don't propagate loop invariants into deeper loops. */
582 64182 : if (!def_bb || bb_loop_depth (def_bb) < bb_loop_depth (bb))
583 : return def;
584 :
585 : /* Backtrack jump threading path from IDX to see if def has constant
586 : value. */
587 78909 : for (int j = idx - 1; j >= 0; j--)
588 : {
589 68724 : edge e = (*path)[j]->e;
590 68724 : if (e->dest == def_bb)
591 : {
592 52168 : arg = gimple_phi_arg_def (def_phi, e->dest_idx);
593 52168 : if (is_gimple_min_invariant (arg))
594 : {
595 17416 : *locus = gimple_phi_arg_location (def_phi, e->dest_idx);
596 17416 : return arg;
597 : }
598 : break;
599 : }
600 : }
601 :
602 : return def;
603 : }
604 :
605 : /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
606 : Try to backtrack jump threading PATH from node IDX to see if the arg
607 : has constant value, copy constant value instead of argument itself
608 : if yes. */
609 :
610 : static void
611 364088 : copy_phi_args (basic_block bb, edge src_e, edge tgt_e,
612 : vec<jump_thread_edge *> *path, int idx)
613 : {
614 364088 : gphi_iterator gsi;
615 364088 : int src_indx = src_e->dest_idx;
616 :
617 618652 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
618 : {
619 254564 : gphi *phi = gsi.phi ();
620 254564 : tree def = gimple_phi_arg_def (phi, src_indx);
621 254564 : location_t locus = gimple_phi_arg_location (phi, src_indx);
622 :
623 254564 : if (TREE_CODE (def) == SSA_NAME
624 457191 : && !virtual_operand_p (gimple_phi_result (phi)))
625 113486 : def = get_value_locus_in_path (def, path, bb, idx, &locus);
626 :
627 254564 : add_phi_arg (phi, def, tgt_e, locus);
628 : }
629 364088 : }
630 :
631 : /* We have recently made a copy of ORIG_BB, including its outgoing
632 : edges. The copy is NEW_BB. Every PHI node in every direct successor of
633 : ORIG_BB has a new argument associated with edge from NEW_BB to the
634 : successor. Initialize the PHI argument so that it is equal to the PHI
635 : argument associated with the edge from ORIG_BB to the successor.
636 : PATH and IDX are used to check if the new PHI argument has constant
637 : value in a flow sensitive manner. */
638 :
639 : static void
640 57429 : update_destination_phis (basic_block orig_bb, basic_block new_bb,
641 : vec<jump_thread_edge *> *path, int idx)
642 : {
643 57429 : edge_iterator ei;
644 57429 : edge e;
645 :
646 182543 : FOR_EACH_EDGE (e, ei, orig_bb->succs)
647 : {
648 125114 : edge e2 = find_edge (new_bb, e->dest);
649 125114 : copy_phi_args (e->dest, e, e2, path, idx);
650 : }
651 57429 : }
652 :
653 : /* Given a duplicate block and its single destination (both stored
654 : in RD). Create an edge between the duplicate and its single
655 : destination.
656 :
657 : Add an additional argument to any PHI nodes at the single
658 : destination. IDX is the start node in jump threading path
659 : we start to check to see if the new PHI argument has constant
660 : value along the jump threading path. */
661 :
662 : static void
663 225723 : create_edge_and_update_destination_phis (struct redirection_data *rd,
664 : basic_block bb, int idx)
665 : {
666 225723 : edge e = make_single_succ_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
667 :
668 225723 : rescan_loop_exit (e, true, false);
669 :
670 : /* We used to copy the thread path here. That was added in 2007
671 : and dutifully updated through the representation changes in 2013.
672 :
673 : In 2013 we added code to thread from an interior node through
674 : the backedge to another interior node. That runs after the code
675 : to thread through loop headers from outside the loop.
676 :
677 : The latter may delete edges in the CFG, including those
678 : which appeared in the jump threading path we copied here. Thus
679 : we'd end up using a dangling pointer.
680 :
681 : After reviewing the 2007/2011 code, I can't see how anything
682 : depended on copying the AUX field and clearly copying the jump
683 : threading path is problematical due to embedded edge pointers.
684 : It has been removed. */
685 225723 : e->aux = NULL;
686 :
687 : /* If there are any PHI nodes at the destination of the outgoing edge
688 : from the duplicate block, then we will need to add a new argument
689 : to them. The argument should have the same value as the argument
690 : associated with the outgoing edge stored in RD. */
691 225723 : copy_phi_args (e->dest, rd->path->last ()->e, e, rd->path, idx);
692 225723 : }
693 :
694 : /* Look through PATH beginning at START and return TRUE if there are
695 : any additional blocks that need to be duplicated. Otherwise,
696 : return FALSE. */
697 : static bool
698 57429 : any_remaining_duplicated_blocks (vec<jump_thread_edge *> *path,
699 : unsigned int start)
700 : {
701 75398 : for (unsigned int i = start + 1; i < path->length (); i++)
702 : {
703 60765 : if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
704 60765 : || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
705 : return true;
706 : }
707 : return false;
708 : }
709 :
710 :
711 : /* Compute the amount of profile count coming into the jump threading
712 : path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
713 : PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
714 : duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
715 : identify blocks duplicated for jump threading, which have duplicated
716 : edges that need to be ignored in the analysis. Return true if path contains
717 : a joiner, false otherwise.
718 :
719 : In the non-joiner case, this is straightforward - all the counts
720 : flowing into the jump threading path should flow through the duplicated
721 : block and out of the duplicated path.
722 :
723 : In the joiner case, it is very tricky. Some of the counts flowing into
724 : the original path go offpath at the joiner. The problem is that while
725 : we know how much total count goes off-path in the original control flow,
726 : we don't know how many of the counts corresponding to just the jump
727 : threading path go offpath at the joiner.
728 :
729 : For example, assume we have the following control flow and identified
730 : jump threading paths:
731 :
732 : A B C
733 : \ | /
734 : Ea \ |Eb / Ec
735 : \ | /
736 : v v v
737 : J <-- Joiner
738 : / \
739 : Eoff/ \Eon
740 : / \
741 : v v
742 : Soff Son <--- Normal
743 : /\
744 : Ed/ \ Ee
745 : / \
746 : v v
747 : D E
748 :
749 : Jump threading paths: A -> J -> Son -> D (path 1)
750 : C -> J -> Son -> E (path 2)
751 :
752 : Note that the control flow could be more complicated:
753 : - Each jump threading path may have more than one incoming edge. I.e. A and
754 : Ea could represent multiple incoming blocks/edges that are included in
755 : path 1.
756 : - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
757 : before or after the "normal" copy block). These are not duplicated onto
758 : the jump threading path, as they are single-successor.
759 : - Any of the blocks along the path may have other incoming edges that
760 : are not part of any jump threading path, but add profile counts along
761 : the path.
762 :
763 : In the above example, after all jump threading is complete, we will
764 : end up with the following control flow:
765 :
766 : A B C
767 : | | |
768 : Ea| |Eb |Ec
769 : | | |
770 : v v v
771 : Ja J Jc
772 : / \ / \Eon' / \
773 : Eona/ \ ---/---\-------- \Eonc
774 : / \ / / \ \
775 : v v v v v
776 : Sona Soff Son Sonc
777 : \ /\ /
778 : \___________ / \ _____/
779 : \ / \/
780 : vv v
781 : D E
782 :
783 : The main issue to notice here is that when we are processing path 1
784 : (A->J->Son->D) we need to figure out the outgoing edge weights to
785 : the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
786 : sum of the incoming weights to D remain Ed. The problem with simply
787 : assuming that Ja (and Jc when processing path 2) has the same outgoing
788 : probabilities to its successors as the original block J, is that after
789 : all paths are processed and other edges/counts removed (e.g. none
790 : of Ec will reach D after processing path 2), we may end up with not
791 : enough count flowing along duplicated edge Sona->D.
792 :
793 : Therefore, in the case of a joiner, we keep track of all counts
794 : coming in along the current path, as well as from predecessors not
795 : on any jump threading path (Eb in the above example). While we
796 : first assume that the duplicated Eona for Ja->Sona has the same
797 : probability as the original, we later compensate for other jump
798 : threading paths that may eliminate edges. We do that by keep track
799 : of all counts coming into the original path that are not in a jump
800 : thread (Eb in the above example, but as noted earlier, there could
801 : be other predecessors incoming to the path at various points, such
802 : as at Son). Call this cumulative non-path count coming into the path
803 : before D as Enonpath. We then ensure that the count from Sona->D is as at
804 : least as big as (Ed - Enonpath), but no bigger than the minimum
805 : weight along the jump threading path. The probabilities of both the
806 : original and duplicated joiner block J and Ja will be adjusted
807 : accordingly after the updates. */
808 :
809 : static bool
810 240356 : compute_path_counts (struct redirection_data *rd,
811 : ssa_local_info_t *local_info,
812 : profile_count *path_in_count_ptr,
813 : profile_count *path_out_count_ptr)
814 : {
815 240356 : edge e = rd->incoming_edges->e;
816 240356 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
817 240356 : edge elast = path->last ()->e;
818 240356 : profile_count nonpath_count = profile_count::zero ();
819 240356 : bool has_joiner = false;
820 240356 : profile_count path_in_count = profile_count::zero ();
821 :
822 : /* Start by accumulating incoming edge counts to the path's first bb
823 : into a couple buckets:
824 : path_in_count: total count of incoming edges that flow into the
825 : current path.
826 : nonpath_count: total count of incoming edges that are not
827 : flowing along *any* path. These are the counts
828 : that will still flow along the original path after
829 : all path duplication is done by potentially multiple
830 : calls to this routine.
831 : (any other incoming edge counts are for a different jump threading
832 : path that will be handled by a later call to this routine.)
833 : To make this easier, start by recording all incoming edges that flow into
834 : the current path in a bitmap. We could add up the path's incoming edge
835 : counts here, but we still need to walk all the first bb's incoming edges
836 : below to add up the counts of the other edges not included in this jump
837 : threading path. */
838 240356 : struct el *next, *el;
839 240356 : auto_bitmap in_edge_srcs;
840 535075 : for (el = rd->incoming_edges; el; el = next)
841 : {
842 294719 : next = el->next;
843 294719 : bitmap_set_bit (in_edge_srcs, el->e->src->index);
844 : }
845 240356 : edge ein;
846 240356 : edge_iterator ei;
847 900370 : FOR_EACH_EDGE (ein, ei, e->dest->preds)
848 : {
849 660014 : vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
850 : /* Simply check the incoming edge src against the set captured above. */
851 660014 : if (ein_path
852 1050715 : && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
853 : {
854 : /* It is necessary but not sufficient that the last path edges
855 : are identical. There may be different paths that share the
856 : same last path edge in the case where the last edge has a nocopy
857 : source block. */
858 294719 : gcc_assert (ein_path->last ()->e == elast);
859 294719 : path_in_count += ein->count ();
860 : }
861 365295 : else if (!ein_path)
862 : {
863 : /* Keep track of the incoming edges that are not on any jump-threading
864 : path. These counts will still flow out of original path after all
865 : jump threading is complete. */
866 269313 : nonpath_count += ein->count ();
867 : }
868 : }
869 :
870 : /* Now compute the fraction of the total count coming into the first
871 : path bb that is from the current threading path. */
872 240356 : profile_count total_count = e->dest->count;
873 : /* Handle incoming profile insanities. */
874 240356 : if (total_count < path_in_count)
875 14420 : path_in_count = total_count;
876 240356 : profile_probability onpath_scale = path_in_count.probability_in (total_count);
877 :
878 : /* Walk the entire path to do some more computation in order to estimate
879 : how much of the path_in_count will flow out of the duplicated threading
880 : path. In the non-joiner case this is straightforward (it should be
881 : the same as path_in_count, although we will handle incoming profile
882 : insanities by setting it equal to the minimum count along the path).
883 :
884 : In the joiner case, we need to estimate how much of the path_in_count
885 : will stay on the threading path after the joiner's conditional branch.
886 : We don't really know for sure how much of the counts
887 : associated with this path go to each successor of the joiner, but we'll
888 : estimate based on the fraction of the total count coming into the path
889 : bb was from the threading paths (computed above in onpath_scale).
890 : Afterwards, we will need to do some fixup to account for other threading
891 : paths and possible profile insanities.
892 :
893 : In order to estimate the joiner case's counts we also need to update
894 : nonpath_count with any additional counts coming into the path. Other
895 : blocks along the path may have additional predecessors from outside
896 : the path. */
897 240356 : profile_count path_out_count = path_in_count;
898 240356 : profile_count min_path_count = path_in_count;
899 557403 : for (unsigned int i = 1; i < path->length (); i++)
900 : {
901 317047 : edge epath = (*path)[i]->e;
902 317047 : profile_count cur_count = epath->count ();
903 317047 : if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
904 : {
905 57429 : has_joiner = true;
906 57429 : cur_count = cur_count.apply_probability (onpath_scale);
907 : }
908 : /* In the joiner case we need to update nonpath_count for any edges
909 : coming into the path that will contribute to the count flowing
910 : into the path successor. */
911 317047 : if (has_joiner && epath != elast)
912 : {
913 : /* Look for other incoming edges after joiner. */
914 239571 : FOR_EACH_EDGE (ein, ei, epath->dest->preds)
915 : {
916 176508 : if (ein != epath
917 : /* Ignore in edges from blocks we have duplicated for a
918 : threading path, which have duplicated edge counts until
919 : they are redirected by an invocation of this routine. */
920 289953 : && !bitmap_bit_p (local_info->duplicate_blocks,
921 113445 : ein->src->index))
922 42132 : nonpath_count += ein->count ();
923 : }
924 : }
925 317047 : if (cur_count < path_out_count)
926 122208 : path_out_count = cur_count;
927 317047 : if (epath->count () < min_path_count)
928 105322 : min_path_count = epath->count ();
929 : }
930 :
931 : /* We computed path_out_count above assuming that this path targeted
932 : the joiner's on-path successor with the same likelihood as it
933 : reached the joiner. However, other thread paths through the joiner
934 : may take a different path through the normal copy source block
935 : (i.e. they have a different elast), meaning that they do not
936 : contribute any counts to this path's elast. As a result, it may
937 : turn out that this path must have more count flowing to the on-path
938 : successor of the joiner. Essentially, all of this path's elast
939 : count must be contributed by this path and any nonpath counts
940 : (since any path through the joiner with a different elast will not
941 : include a copy of this elast in its duplicated path).
942 : So ensure that this path's path_out_count is at least the
943 : difference between elast->count () and nonpath_count. Otherwise the edge
944 : counts after threading will not be sane. */
945 240356 : if (local_info->need_profile_correction
946 259740 : && has_joiner && path_out_count < elast->count () - nonpath_count)
947 : {
948 3869 : path_out_count = elast->count () - nonpath_count;
949 : /* But neither can we go above the minimum count along the path
950 : we are duplicating. This can be an issue due to profile
951 : insanities coming in to this pass. */
952 3869 : if (path_out_count > min_path_count)
953 2679 : path_out_count = min_path_count;
954 : }
955 :
956 240356 : *path_in_count_ptr = path_in_count;
957 240356 : *path_out_count_ptr = path_out_count;
958 240356 : return has_joiner;
959 240356 : }
960 :
961 :
962 : /* Update the counts and frequencies for both an original path
963 : edge EPATH and its duplicate EDUP. The duplicate source block
964 : will get a count of PATH_IN_COUNT and PATH_IN_FREQ,
965 : and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
966 : static void
967 317047 : update_profile (edge epath, edge edup, profile_count path_in_count,
968 : profile_count path_out_count)
969 : {
970 :
971 : /* First update the duplicated block's count. */
972 317047 : if (edup)
973 : {
974 283152 : basic_block dup_block = edup->src;
975 :
976 : /* Edup's count is reduced by path_out_count. We need to redistribute
977 : probabilities to the remaining edges. */
978 :
979 283152 : edge esucc;
980 283152 : edge_iterator ei;
981 283152 : profile_probability edup_prob
982 283152 : = path_out_count.probability_in (path_in_count);
983 :
984 : /* Either scale up or down the remaining edges.
985 : probabilities are always in range <0,1> and thus we can't do
986 : both by same loop. */
987 283152 : if (edup->probability > edup_prob)
988 : {
989 22401 : profile_probability rev_scale
990 22401 : = (profile_probability::always () - edup->probability)
991 44802 : / (profile_probability::always () - edup_prob);
992 68799 : FOR_EACH_EDGE (esucc, ei, dup_block->succs)
993 46398 : if (esucc != edup)
994 23997 : esucc->probability /= rev_scale;
995 : }
996 260751 : else if (edup->probability < edup_prob)
997 : {
998 13163 : profile_probability scale
999 13163 : = (profile_probability::always () - edup_prob)
1000 26326 : / (profile_probability::always () - edup->probability);
1001 39812 : FOR_EACH_EDGE (esucc, ei, dup_block->succs)
1002 26649 : if (esucc != edup)
1003 13486 : esucc->probability *= scale;
1004 : }
1005 283152 : if (edup_prob.initialized_p ())
1006 264489 : edup->probability = edup_prob;
1007 :
1008 283152 : gcc_assert (!dup_block->count.initialized_p ());
1009 283152 : dup_block->count = path_in_count;
1010 : }
1011 :
1012 317047 : if (path_in_count == profile_count::zero ())
1013 10705 : return;
1014 :
1015 306342 : profile_count final_count = epath->count () - path_out_count;
1016 :
1017 : /* Now update the original block's count in the
1018 : opposite manner - remove the counts/freq that will flow
1019 : into the duplicated block. Handle underflow due to precision/
1020 : rounding issues. */
1021 306342 : epath->src->count -= path_in_count;
1022 :
1023 : /* Next update this path edge's original and duplicated counts. We know
1024 : that the duplicated path will have path_out_count flowing
1025 : out of it (in the joiner case this is the count along the duplicated path
1026 : out of the duplicated joiner). This count can then be removed from the
1027 : original path edge. */
1028 :
1029 306342 : edge esucc;
1030 306342 : edge_iterator ei;
1031 306342 : profile_probability epath_prob = final_count.probability_in (epath->src->count);
1032 :
1033 306342 : if (epath->probability > epath_prob)
1034 : {
1035 184643 : profile_probability rev_scale
1036 184643 : = (profile_probability::always () - epath->probability)
1037 369286 : / (profile_probability::always () - epath_prob);
1038 557890 : FOR_EACH_EDGE (esucc, ei, epath->src->succs)
1039 373247 : if (esucc != epath)
1040 188604 : esucc->probability /= rev_scale;
1041 : }
1042 121699 : else if (epath->probability < epath_prob)
1043 : {
1044 20496 : profile_probability scale
1045 20496 : = (profile_probability::always () - epath_prob)
1046 40992 : / (profile_probability::always () - epath->probability);
1047 62727 : FOR_EACH_EDGE (esucc, ei, epath->src->succs)
1048 42231 : if (esucc != epath)
1049 21735 : esucc->probability *= scale;
1050 : }
1051 306342 : if (epath_prob.initialized_p ())
1052 283308 : epath->probability = epath_prob;
1053 : }
1054 :
1055 : /* Wire up the outgoing edges from the duplicate blocks and
1056 : update any PHIs as needed. Also update the profile counts
1057 : on the original and duplicate blocks and edges. */
1058 : void
1059 240356 : ssa_fix_duplicate_block_edges (struct redirection_data *rd,
1060 : ssa_local_info_t *local_info)
1061 : {
1062 240356 : bool multi_incomings = (rd->incoming_edges->next != NULL);
1063 240356 : edge e = rd->incoming_edges->e;
1064 240356 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
1065 240356 : edge elast = path->last ()->e;
1066 240356 : profile_count path_in_count = profile_count::zero ();
1067 240356 : profile_count path_out_count = profile_count::zero ();
1068 :
1069 : /* First determine how much profile count to move from original
1070 : path to the duplicate path. This is tricky in the presence of
1071 : a joiner (see comments for compute_path_counts), where some portion
1072 : of the path's counts will flow off-path from the joiner. In the
1073 : non-joiner case the path_in_count and path_out_count should be the
1074 : same. */
1075 240356 : bool has_joiner = compute_path_counts (rd, local_info,
1076 : &path_in_count, &path_out_count);
1077 :
1078 797759 : for (unsigned int count = 0, i = 1; i < path->length (); i++)
1079 : {
1080 317047 : edge epath = (*path)[i]->e;
1081 :
1082 : /* If we were threading through an joiner block, then we want
1083 : to keep its control statement and redirect an outgoing edge.
1084 : Else we want to remove the control statement & edges, then create
1085 : a new outgoing edge. In both cases we may need to update PHIs. */
1086 317047 : if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1087 : {
1088 57429 : edge victim;
1089 57429 : edge e2;
1090 :
1091 57429 : gcc_assert (has_joiner);
1092 :
1093 : /* This updates the PHIs at the destination of the duplicate
1094 : block. Pass 0 instead of i if we are threading a path which
1095 : has multiple incoming edges. */
1096 103951 : update_destination_phis (local_info->bb, rd->dup_blocks[count],
1097 : path, multi_incomings ? 0 : i);
1098 :
1099 : /* Find the edge from the duplicate block to the block we're
1100 : threading through. That's the edge we want to redirect. */
1101 57429 : victim = find_edge (rd->dup_blocks[count], (*path)[i]->e->dest);
1102 :
1103 : /* If there are no remaining blocks on the path to duplicate,
1104 : then redirect VICTIM to the final destination of the jump
1105 : threading path. */
1106 57429 : if (!any_remaining_duplicated_blocks (path, i))
1107 : {
1108 14633 : if (victim->dest != elast->dest)
1109 : {
1110 13466 : e2 = redirect_edge_and_branch (victim, elast->dest);
1111 : /* If we redirected the edge, then we need to copy PHI arguments
1112 : at the target. If the edge already existed (e2 != victim
1113 : case), then the PHIs in the target already have the correct
1114 : arguments. */
1115 13466 : if (e2 == victim)
1116 13251 : copy_phi_args (e2->dest, elast, e2,
1117 : path, multi_incomings ? 0 : i);
1118 : }
1119 : else
1120 : e2 = victim;
1121 : }
1122 : else
1123 : {
1124 : /* Redirect VICTIM to the next duplicated block in the path. */
1125 42796 : e2 = redirect_edge_and_branch (victim, rd->dup_blocks[count + 1]);
1126 :
1127 : /* We need to update the PHIs in the next duplicated block. We
1128 : want the new PHI args to have the same value as they had
1129 : in the source of the next duplicate block.
1130 :
1131 : Thus, we need to know which edge we traversed into the
1132 : source of the duplicate. Furthermore, we may have
1133 : traversed many edges to reach the source of the duplicate.
1134 :
1135 : Walk through the path starting at element I until we
1136 : hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
1137 : the edge from the prior element. */
1138 44497 : for (unsigned int j = i + 1; j < path->length (); j++)
1139 : {
1140 44497 : if ((*path)[j]->type == EDGE_COPY_SRC_BLOCK)
1141 : {
1142 42796 : copy_phi_arg_into_existing_phi ((*path)[j - 1]->e, e2);
1143 42796 : break;
1144 : }
1145 : }
1146 : }
1147 :
1148 : /* Update the counts of both the original block
1149 : and path edge, and the duplicates. The path duplicate's
1150 : incoming count are the totals for all edges
1151 : incoming to this jump threading path computed earlier.
1152 : And we know that the duplicated path will have path_out_count
1153 : flowing out of it (i.e. along the duplicated path out of the
1154 : duplicated joiner). */
1155 57429 : update_profile (epath, e2, path_in_count, path_out_count);
1156 : }
1157 259618 : else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1158 : {
1159 225723 : remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[count], NULL);
1160 421315 : create_edge_and_update_destination_phis (rd, rd->dup_blocks[count],
1161 : multi_incomings ? 0 : i);
1162 225723 : if (count == 1)
1163 42796 : single_succ_edge (rd->dup_blocks[1])->aux = NULL;
1164 :
1165 : /* Update the counts of both the original block
1166 : and path edge, and the duplicates. Since we are now after
1167 : any joiner that may have existed on the path, the count
1168 : flowing along the duplicated threaded path is path_out_count.
1169 : If we didn't have a joiner, then cur_path_freq was the sum
1170 : of the total frequencies along all incoming edges to the
1171 : thread path (path_in_freq). If we had a joiner, it would have
1172 : been updated at the end of that handling to the edge frequency
1173 : along the duplicated joiner path edge. */
1174 225723 : update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
1175 : path_out_count, path_out_count);
1176 : }
1177 : else
1178 : {
1179 : /* No copy case. In this case we don't have an equivalent block
1180 : on the duplicated thread path to update, but we do need
1181 : to remove the portion of the counts/freqs that were moved
1182 : to the duplicated path from the counts/freqs flowing through
1183 : this block on the original path. Since all the no-copy edges
1184 : are after any joiner, the removed count is the same as
1185 : path_out_count.
1186 :
1187 : If we didn't have a joiner, then cur_path_freq was the sum
1188 : of the total frequencies along all incoming edges to the
1189 : thread path (path_in_freq). If we had a joiner, it would have
1190 : been updated at the end of that handling to the edge frequency
1191 : along the duplicated joiner path edge. */
1192 33895 : update_profile (epath, NULL, path_out_count, path_out_count);
1193 : }
1194 :
1195 : /* Increment the index into the duplicated path when we processed
1196 : a duplicated block. */
1197 317047 : if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
1198 317047 : || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
1199 : {
1200 283152 : count++;
1201 : }
1202 : }
1203 240356 : }
1204 :
1205 : /* Hash table traversal callback routine to create duplicate blocks. */
1206 :
1207 : int
1208 240356 : ssa_create_duplicates (struct redirection_data **slot,
1209 : ssa_local_info_t *local_info)
1210 : {
1211 240356 : struct redirection_data *rd = *slot;
1212 :
1213 : /* The second duplicated block in a jump threading path is specific
1214 : to the path. So it gets stored in RD rather than in LOCAL_DATA.
1215 :
1216 : Each time we're called, we have to look through the path and see
1217 : if a second block needs to be duplicated.
1218 :
1219 : Note the search starts with the third edge on the path. The first
1220 : edge is the incoming edge, the second edge always has its source
1221 : duplicated. Thus we start our search with the third edge. */
1222 240356 : vec<jump_thread_edge *> *path = rd->path;
1223 271953 : for (unsigned int i = 2; i < path->length (); i++)
1224 : {
1225 74393 : if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
1226 74393 : || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1227 : {
1228 42796 : create_block_for_threading ((*path)[i]->e->src, rd, 1,
1229 : &local_info->duplicate_blocks);
1230 42796 : break;
1231 : }
1232 : }
1233 :
1234 : /* Create a template block if we have not done so already. Otherwise
1235 : use the template to create a new block. */
1236 240356 : if (local_info->template_block == NULL)
1237 : {
1238 208554 : create_block_for_threading ((*path)[1]->e->src, rd, 0,
1239 : &local_info->duplicate_blocks);
1240 208554 : local_info->template_block = rd->dup_blocks[0];
1241 208554 : local_info->template_last_to_copy
1242 417108 : = gsi_last_bb (local_info->template_block);
1243 :
1244 : /* We do not create any outgoing edges for the template. We will
1245 : take care of that in a later traversal. That way we do not
1246 : create edges that are going to just be deleted. */
1247 : }
1248 : else
1249 : {
1250 31802 : gimple_seq seq = NULL;
1251 31802 : if (gsi_stmt (local_info->template_last_to_copy)
1252 63604 : != gsi_stmt (gsi_last_bb (local_info->template_block)))
1253 : {
1254 0 : if (gsi_end_p (local_info->template_last_to_copy))
1255 : {
1256 0 : seq = bb_seq (local_info->template_block);
1257 0 : set_bb_seq (local_info->template_block, NULL);
1258 : }
1259 : else
1260 0 : seq = gsi_split_seq_after (local_info->template_last_to_copy);
1261 : }
1262 31802 : create_block_for_threading (local_info->template_block, rd, 0,
1263 : &local_info->duplicate_blocks);
1264 31802 : if (seq)
1265 : {
1266 0 : if (gsi_end_p (local_info->template_last_to_copy))
1267 0 : set_bb_seq (local_info->template_block, seq);
1268 : else
1269 0 : gsi_insert_seq_after (&local_info->template_last_to_copy,
1270 : seq, GSI_SAME_STMT);
1271 : }
1272 :
1273 : /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
1274 : block. */
1275 31802 : ssa_fix_duplicate_block_edges (rd, local_info);
1276 : }
1277 :
1278 240356 : if (MAY_HAVE_DEBUG_STMTS)
1279 : {
1280 : /* Copy debug stmts from each NO_COPY src block to the block
1281 : that would have been its predecessor, if we can append to it
1282 : (we can't add stmts after a block-ending stmt), or prepending
1283 : to the duplicate of the successor, if there is one. If
1284 : there's no duplicate successor, we'll mostly drop the blocks
1285 : on the floor; propagate_threaded_block_debug_into, called
1286 : elsewhere, will consolidate and preserve the effects of the
1287 : binds, but none of the markers. */
1288 186810 : gimple_stmt_iterator copy_to = gsi_last_bb (rd->dup_blocks[0]);
1289 186810 : if (!gsi_end_p (copy_to))
1290 : {
1291 186073 : if (stmt_ends_bb_p (gsi_stmt (copy_to)))
1292 : {
1293 174928 : if (rd->dup_blocks[1])
1294 35831 : copy_to = gsi_after_labels (rd->dup_blocks[1]);
1295 : else
1296 139097 : copy_to = gsi_none ();
1297 : }
1298 : else
1299 11145 : gsi_next (©_to);
1300 : }
1301 249791 : for (unsigned int i = 2, j = 0; i < path->length (); i++)
1302 62981 : if ((*path)[i]->type == EDGE_NO_COPY_SRC_BLOCK
1303 62981 : && gsi_bb (copy_to))
1304 : {
1305 6968 : for (gimple_stmt_iterator gsi = gsi_start_bb ((*path)[i]->e->src);
1306 12101 : !gsi_end_p (gsi); gsi_next (&gsi))
1307 : {
1308 8617 : if (!is_gimple_debug (gsi_stmt (gsi)))
1309 2090 : continue;
1310 6527 : gimple *stmt = gsi_stmt (gsi);
1311 6527 : gimple *copy = gimple_copy (stmt);
1312 6527 : gsi_insert_before (©_to, copy, GSI_SAME_STMT);
1313 : }
1314 : }
1315 59497 : else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
1316 59497 : || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1317 : {
1318 36131 : j++;
1319 36131 : gcc_assert (j < 2);
1320 36131 : copy_to = gsi_last_bb (rd->dup_blocks[j]);
1321 36131 : if (!gsi_end_p (copy_to))
1322 : {
1323 36045 : if (stmt_ends_bb_p (gsi_stmt (copy_to)))
1324 29568 : copy_to = gsi_none ();
1325 : else
1326 6477 : gsi_next (©_to);
1327 : }
1328 : }
1329 : }
1330 :
1331 : /* Keep walking the hash table. */
1332 240356 : return 1;
1333 : }
1334 :
1335 : /* We did not create any outgoing edges for the template block during
1336 : block creation. This hash table traversal callback creates the
1337 : outgoing edge for the template block. */
1338 :
1339 : inline int
1340 208554 : ssa_fixup_template_block (struct redirection_data **slot,
1341 : ssa_local_info_t *local_info)
1342 : {
1343 208554 : struct redirection_data *rd = *slot;
1344 :
1345 : /* If this is the template block halt the traversal after updating
1346 : it appropriately.
1347 :
1348 : If we were threading through an joiner block, then we want
1349 : to keep its control statement and redirect an outgoing edge.
1350 : Else we want to remove the control statement & edges, then create
1351 : a new outgoing edge. In both cases we may need to update PHIs. */
1352 208554 : if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block)
1353 : {
1354 208554 : ssa_fix_duplicate_block_edges (rd, local_info);
1355 208554 : return 0;
1356 : }
1357 :
1358 : return 1;
1359 : }
1360 :
1361 : /* Hash table traversal callback to redirect each incoming edge
1362 : associated with this hash table element to its new destination. */
1363 :
1364 : static int
1365 240356 : ssa_redirect_edges (struct redirection_data **slot,
1366 : ssa_local_info_t *local_info)
1367 : {
1368 240356 : struct redirection_data *rd = *slot;
1369 240356 : struct el *next, *el;
1370 :
1371 : /* Walk over all the incoming edges associated with this hash table
1372 : entry. */
1373 535075 : for (el = rd->incoming_edges; el; el = next)
1374 : {
1375 294719 : edge e = el->e;
1376 294719 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
1377 :
1378 : /* Go ahead and free this element from the list. Doing this now
1379 : avoids the need for another list walk when we destroy the hash
1380 : table. */
1381 294719 : next = el->next;
1382 294719 : free (el);
1383 :
1384 294719 : local_info->num_threaded_edges++;
1385 :
1386 294719 : if (rd->dup_blocks[0])
1387 : {
1388 294719 : edge e2;
1389 :
1390 294719 : if (dump_file && (dump_flags & TDF_DETAILS))
1391 28 : fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
1392 28 : e->src->index, e->dest->index, rd->dup_blocks[0]->index);
1393 :
1394 : /* Redirect the incoming edge (possibly to the joiner block) to the
1395 : appropriate duplicate block. */
1396 294719 : e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
1397 294719 : gcc_assert (e == e2);
1398 294719 : flush_pending_stmts (e2);
1399 : }
1400 :
1401 : /* Go ahead and clear E->aux. It's not needed anymore and failure
1402 : to clear it will cause all kinds of unpleasant problems later. */
1403 294719 : path->release ();
1404 294719 : e->aux = NULL;
1405 :
1406 : }
1407 :
1408 : /* Indicate that we actually threaded one or more jumps. */
1409 240356 : if (rd->incoming_edges)
1410 240356 : local_info->jumps_threaded = true;
1411 :
1412 240356 : return 1;
1413 : }
1414 :
1415 : /* Return true if this block has no executable statements other than
1416 : a simple ctrl flow instruction. When the number of outgoing edges
1417 : is one, this is equivalent to a "forwarder" block. */
1418 :
1419 : static bool
1420 41082 : redirection_block_p (basic_block bb)
1421 : {
1422 41082 : gimple_stmt_iterator gsi;
1423 :
1424 : /* Advance to the first executable statement. */
1425 41082 : gsi = gsi_start_bb (bb);
1426 41082 : while (!gsi_end_p (gsi)
1427 180057 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
1428 : || is_gimple_debug (gsi_stmt (gsi))
1429 : || gimple_nop_p (gsi_stmt (gsi))
1430 41029 : || gimple_clobber_p (gsi_stmt (gsi))))
1431 138975 : gsi_next (&gsi);
1432 :
1433 : /* Check if this is an empty block. */
1434 41082 : if (gsi_end_p (gsi))
1435 : return true;
1436 :
1437 : /* Test that we've reached the terminating control statement. */
1438 40769 : return gsi_stmt (gsi)
1439 40769 : && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
1440 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
1441 : || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH);
1442 : }
1443 :
1444 : /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
1445 : is reached via one or more specific incoming edges, we know which
1446 : outgoing edge from BB will be traversed.
1447 :
1448 : We want to redirect those incoming edges to the target of the
1449 : appropriate outgoing edge. Doing so avoids a conditional branch
1450 : and may expose new optimization opportunities. Note that we have
1451 : to update dominator tree and SSA graph after such changes.
1452 :
1453 : The key to keeping the SSA graph update manageable is to duplicate
1454 : the side effects occurring in BB so that those side effects still
1455 : occur on the paths which bypass BB after redirecting edges.
1456 :
1457 : We accomplish this by creating duplicates of BB and arranging for
1458 : the duplicates to unconditionally pass control to one specific
1459 : successor of BB. We then revector the incoming edges into BB to
1460 : the appropriate duplicate of BB.
1461 :
1462 : If NOLOOP_ONLY is true, we only perform the threading as long as it
1463 : does not affect the structure of the loops in a nontrivial way.
1464 :
1465 : If JOINERS is true, then thread through joiner blocks as well. */
1466 :
1467 : bool
1468 499874 : fwd_jt_path_registry::thread_block_1 (basic_block bb,
1469 : bool noloop_only,
1470 : bool joiners)
1471 : {
1472 : /* E is an incoming edge into BB that we may or may not want to
1473 : redirect to a duplicate of BB. */
1474 499874 : edge e, e2;
1475 499874 : edge_iterator ei;
1476 499874 : ssa_local_info_t local_info;
1477 :
1478 499874 : local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
1479 499874 : local_info.need_profile_correction = false;
1480 499874 : local_info.num_threaded_edges = 0;
1481 :
1482 : /* To avoid scanning a linear array for the element we need we instead
1483 : use a hash table. For normal code there should be no noticeable
1484 : difference. However, if we have a block with a large number of
1485 : incoming and outgoing edges such linear searches can get expensive. */
1486 499874 : m_redirection_data
1487 999748 : = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));
1488 :
1489 : /* Record each unique threaded destination into a hash table for
1490 : efficient lookups. */
1491 499874 : edge last = NULL;
1492 1587789 : FOR_EACH_EDGE (e, ei, bb->preds)
1493 : {
1494 1087915 : if (e->aux == NULL)
1495 595259 : continue;
1496 :
1497 492656 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
1498 :
1499 743018 : if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
1500 617837 : || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
1501 136380 : continue;
1502 :
1503 : /* When a NO_COPY_SRC block became non-empty cancel the path. */
1504 356276 : if (path->last ()->type == EDGE_NO_COPY_SRC_BLOCK)
1505 : {
1506 57202 : auto gsi = gsi_start_nondebug_bb (path->last ()->e->src);
1507 57202 : if (!gsi_end_p (gsi)
1508 57202 : && !is_ctrl_stmt (gsi_stmt (gsi)))
1509 : {
1510 0 : cancel_thread (path, "Non-empty EDGE_NO_COPY_SRC_BLOCK");
1511 0 : e->aux = NULL;
1512 0 : continue;
1513 : }
1514 : }
1515 :
1516 356276 : e2 = path->last ()->e;
1517 356276 : if (!e2 || noloop_only)
1518 : {
1519 : /* If NOLOOP_ONLY is true, we only allow threading through the
1520 : header of a loop to exit edges. */
1521 :
1522 : /* One case occurs when there was loop header buried in a jump
1523 : threading path that crosses loop boundaries. We do not try
1524 : and thread this elsewhere, so just cancel the jump threading
1525 : request by clearing the AUX field now. */
1526 393260 : if (bb->loop_father != e2->src->loop_father
1527 352430 : && (!loop_exit_edge_p (e2->src->loop_father, e2)
1528 770 : || flow_loop_nested_p (bb->loop_father,
1529 770 : e2->dest->loop_father)))
1530 : {
1531 : /* Since this case is not handled by our special code
1532 : to thread through a loop header, we must explicitly
1533 : cancel the threading request here. */
1534 40830 : cancel_thread (path, "Threading through unhandled loop header");
1535 40830 : e->aux = NULL;
1536 40830 : continue;
1537 : }
1538 :
1539 : /* Another case occurs when trying to thread through our
1540 : own loop header, possibly from inside the loop. We will
1541 : thread these later. */
1542 : unsigned int i;
1543 701745 : for (i = 1; i < path->length (); i++)
1544 : {
1545 410829 : if ((*path)[i]->e->src == bb->loop_father->header
1546 410829 : && (!loop_exit_edge_p (bb->loop_father, e2)
1547 2228 : || (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK))
1548 : break;
1549 : }
1550 :
1551 623200 : if (i != path->length ())
1552 20684 : continue;
1553 :
1554 : /* Loop parallelization can be confused by the result of
1555 : threading through the loop exit test back into the loop.
1556 : However, theading those jumps seems to help other codes.
1557 :
1558 : I have been unable to find anything related to the shape of
1559 : the CFG, the contents of the affected blocks, etc which would
1560 : allow a more sensible test than what we're using below which
1561 : merely avoids the optimization when parallelizing loops. */
1562 290916 : if (flag_tree_parallelize_loops > 1)
1563 : {
1564 176 : for (i = 1; i < path->length (); i++)
1565 115 : if (bb->loop_father == e2->src->loop_father
1566 115 : && loop_exits_from_bb_p (bb->loop_father,
1567 115 : (*path)[i]->e->src)
1568 163 : && !loop_exit_edge_p (bb->loop_father, e2))
1569 : break;
1570 :
1571 208 : if (i != path->length ())
1572 : {
1573 43 : cancel_thread (path, "Threading through loop exit");
1574 43 : e->aux = NULL;
1575 43 : continue;
1576 : }
1577 : }
1578 : }
1579 :
1580 : /* Insert the outgoing edge into the hash table if it is not
1581 : already in the hash table. */
1582 294719 : lookup_redirection_data (e, INSERT);
1583 :
1584 : /* When we have thread paths through a common joiner with different
1585 : final destinations, then we may need corrections to deal with
1586 : profile insanities. See the big comment before compute_path_counts. */
1587 294719 : if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1588 : {
1589 74944 : if (!last)
1590 : last = e2;
1591 27376 : else if (e2 != last)
1592 13677 : local_info.need_profile_correction = true;
1593 : }
1594 : }
1595 :
1596 : /* We do not update dominance info. */
1597 499874 : free_dominance_info (CDI_DOMINATORS);
1598 :
1599 : /* We know we only thread through the loop header to loop exits.
1600 : Let the basic block duplication hook know we are not creating
1601 : a multiple entry loop. */
1602 499874 : if (noloop_only
1603 492182 : && bb == bb->loop_father->header)
1604 72288 : set_loop_copy (bb->loop_father, loop_outer (bb->loop_father));
1605 :
1606 : /* Now create duplicates of BB.
1607 :
1608 : Note that for a block with a high outgoing degree we can waste
1609 : a lot of time and memory creating and destroying useless edges.
1610 :
1611 : So we first duplicate BB and remove the control structure at the
1612 : tail of the duplicate as well as all outgoing edges from the
1613 : duplicate. We then use that duplicate block as a template for
1614 : the rest of the duplicates. */
1615 499874 : local_info.template_block = NULL;
1616 499874 : local_info.bb = bb;
1617 499874 : local_info.jumps_threaded = false;
1618 499874 : m_redirection_data->traverse <ssa_local_info_t *, ssa_create_duplicates>
1619 740230 : (&local_info);
1620 :
1621 : /* The template does not have an outgoing edge. Create that outgoing
1622 : edge and update PHI nodes as the edge's target as necessary.
1623 :
1624 : We do this after creating all the duplicates to avoid creating
1625 : unnecessary edges. */
1626 499874 : m_redirection_data->traverse <ssa_local_info_t *, ssa_fixup_template_block>
1627 708428 : (&local_info);
1628 :
1629 : /* The hash table traversals above created the duplicate blocks (and the
1630 : statements within the duplicate blocks). This loop creates PHI nodes for
1631 : the duplicated blocks and redirects the incoming edges into BB to reach
1632 : the duplicates of BB. */
1633 499874 : m_redirection_data->traverse <ssa_local_info_t *, ssa_redirect_edges>
1634 740230 : (&local_info);
1635 :
1636 : /* Done with this block. Clear REDIRECTION_DATA. */
1637 499874 : delete m_redirection_data;
1638 499874 : m_redirection_data = NULL;
1639 :
1640 499874 : if (noloop_only
1641 492182 : && bb == bb->loop_father->header)
1642 72288 : set_loop_copy (bb->loop_father, NULL);
1643 :
1644 499874 : BITMAP_FREE (local_info.duplicate_blocks);
1645 499874 : local_info.duplicate_blocks = NULL;
1646 :
1647 499874 : m_num_threaded_edges += local_info.num_threaded_edges;
1648 :
1649 : /* Indicate to our caller whether or not any jumps were threaded. */
1650 499874 : return local_info.jumps_threaded;
1651 : }
1652 :
1653 : /* Wrapper for thread_block_1 so that we can first handle jump
1654 : thread paths which do not involve copying joiner blocks, then
1655 : handle jump thread paths which have joiner blocks.
1656 :
1657 : By doing things this way we can be as aggressive as possible and
1658 : not worry that copying a joiner block will create a jump threading
1659 : opportunity. */
1660 :
1661 : bool
1662 249937 : fwd_jt_path_registry::thread_block (basic_block bb, bool noloop_only)
1663 : {
1664 249937 : bool retval;
1665 249937 : retval = thread_block_1 (bb, noloop_only, false);
1666 249937 : retval |= thread_block_1 (bb, noloop_only, true);
1667 249937 : return retval;
1668 : }
1669 :
1670 : /* Callback for dfs_enumerate_from. Returns true if BB is different
1671 : from STOP and DBDS_CE_STOP. */
1672 :
1673 : static basic_block dbds_ce_stop;
1674 : static bool
1675 2238716 : dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
1676 : {
1677 2238716 : return (bb != (const_basic_block) stop
1678 2238716 : && bb != dbds_ce_stop);
1679 : }
1680 :
1681 : /* Evaluates the dominance relationship of latch of the LOOP and BB, and
1682 : returns the state. */
1683 :
1684 : enum bb_dom_status
1685 126821 : determine_bb_domination_status (class loop *loop, basic_block bb)
1686 : {
1687 126821 : basic_block *bblocks;
1688 126821 : unsigned nblocks, i;
1689 126821 : bool bb_reachable = false;
1690 126821 : edge_iterator ei;
1691 126821 : edge e;
1692 :
1693 : /* This function assumes BB is a successor of LOOP->header.
1694 : If that is not the case return DOMST_NONDOMINATING which
1695 : is always safe. */
1696 126821 : {
1697 126821 : bool ok = false;
1698 :
1699 198839 : FOR_EACH_EDGE (e, ei, bb->preds)
1700 : {
1701 155539 : if (e->src == loop->header)
1702 : {
1703 : ok = true;
1704 : break;
1705 : }
1706 : }
1707 :
1708 126821 : if (!ok)
1709 : return DOMST_NONDOMINATING;
1710 : }
1711 :
1712 83521 : if (bb == loop->latch)
1713 : return DOMST_DOMINATING;
1714 :
1715 : /* Check that BB dominates LOOP->latch, and that it is back-reachable
1716 : from it. */
1717 :
1718 81577 : bblocks = XCNEWVEC (basic_block, loop->num_nodes);
1719 81577 : dbds_ce_stop = loop->header;
1720 163154 : nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p,
1721 81577 : bblocks, loop->num_nodes, bb);
1722 1202824 : for (i = 0; i < nblocks; i++)
1723 3016009 : FOR_EACH_EDGE (e, ei, bblocks[i]->preds)
1724 : {
1725 1894762 : if (e->src == loop->header)
1726 : {
1727 44324 : free (bblocks);
1728 44324 : return DOMST_NONDOMINATING;
1729 : }
1730 1850438 : if (e->src == bb)
1731 79067 : bb_reachable = true;
1732 : }
1733 :
1734 37253 : free (bblocks);
1735 37253 : return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
1736 : }
1737 :
1738 : /* Thread jumps through the header of LOOP. Returns true if cfg changes.
1739 : If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1740 : to the inside of the loop. */
1741 :
1742 : bool
1743 36144 : fwd_jt_path_registry::thread_through_loop_header (class loop *loop,
1744 : bool may_peel_loop_headers)
1745 : {
1746 36144 : basic_block header = loop->header;
1747 36144 : edge e, tgt_edge, latch = loop_latch_edge (loop);
1748 36144 : edge_iterator ei;
1749 36144 : basic_block tgt_bb, atgt_bb;
1750 36144 : enum bb_dom_status domst;
1751 :
1752 : /* We have already threaded through headers to exits, so all the threading
1753 : requests now are to the inside of the loop. We need to avoid creating
1754 : irreducible regions (i.e., loops with more than one entry block), and
1755 : also loop with several latch edges, or new subloops of the loop (although
1756 : there are cases where it might be appropriate, it is difficult to decide,
1757 : and doing it wrongly may confuse other optimizers).
1758 :
1759 : We could handle more general cases here. However, the intention is to
1760 : preserve some information about the loop, which is impossible if its
1761 : structure changes significantly, in a way that is not well understood.
1762 : Thus we only handle few important special cases, in which also updating
1763 : of the loop-carried information should be feasible:
1764 :
1765 : 1) Propagation of latch edge to a block that dominates the latch block
1766 : of a loop. This aims to handle the following idiom:
1767 :
1768 : first = 1;
1769 : while (1)
1770 : {
1771 : if (first)
1772 : initialize;
1773 : first = 0;
1774 : body;
1775 : }
1776 :
1777 : After threading the latch edge, this becomes
1778 :
1779 : first = 1;
1780 : if (first)
1781 : initialize;
1782 : while (1)
1783 : {
1784 : first = 0;
1785 : body;
1786 : }
1787 :
1788 : The original header of the loop is moved out of it, and we may thread
1789 : the remaining edges through it without further constraints.
1790 :
1791 : 2) All entry edges are propagated to a single basic block that dominates
1792 : the latch block of the loop. This aims to handle the following idiom
1793 : (normally created for "for" loops):
1794 :
1795 : i = 0;
1796 : while (1)
1797 : {
1798 : if (i >= 100)
1799 : break;
1800 : body;
1801 : i++;
1802 : }
1803 :
1804 : This becomes
1805 :
1806 : i = 0;
1807 : while (1)
1808 : {
1809 : body;
1810 : i++;
1811 : if (i >= 100)
1812 : break;
1813 : }
1814 : */
1815 :
1816 : /* Threading through the header won't improve the code if the header has just
1817 : one successor. */
1818 36144 : if (single_succ_p (header))
1819 4327 : goto fail;
1820 :
1821 31817 : if (!may_peel_loop_headers && !redirection_block_p (loop->header))
1822 21861 : goto fail;
1823 : else
1824 : {
1825 9956 : tgt_bb = NULL;
1826 9956 : tgt_edge = NULL;
1827 22905 : FOR_EACH_EDGE (e, ei, header->preds)
1828 : {
1829 17392 : if (!e->aux)
1830 : {
1831 9743 : if (e == latch)
1832 8105 : continue;
1833 :
1834 : /* If latch is not threaded, and there is a header
1835 : edge that is not threaded, we would create loop
1836 : with multiple entries. */
1837 1638 : goto fail;
1838 : }
1839 :
1840 7649 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
1841 :
1842 7649 : if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
1843 2805 : goto fail;
1844 4844 : tgt_edge = (*path)[1]->e;
1845 4844 : atgt_bb = tgt_edge->dest;
1846 4844 : if (!tgt_bb)
1847 : tgt_bb = atgt_bb;
1848 : /* Two targets of threading would make us create loop
1849 : with multiple entries. */
1850 0 : else if (tgt_bb != atgt_bb)
1851 0 : goto fail;
1852 : }
1853 :
1854 5513 : if (!tgt_bb)
1855 : {
1856 : /* There are no threading requests. */
1857 : return false;
1858 : }
1859 :
1860 : /* Redirecting to empty loop latch is useless. */
1861 4825 : if (tgt_bb == loop->latch
1862 4825 : && empty_block_p (loop->latch))
1863 0 : goto fail;
1864 : }
1865 :
1866 : /* The target block must dominate the loop latch, otherwise we would be
1867 : creating a subloop. */
1868 4825 : domst = determine_bb_domination_status (loop, tgt_bb);
1869 4825 : if (domst == DOMST_NONDOMINATING)
1870 979 : goto fail;
1871 3846 : if (domst == DOMST_LOOP_BROKEN)
1872 : {
1873 : /* If the loop ceased to exist, mark it as such, and thread through its
1874 : original header. */
1875 0 : mark_loop_for_removal (loop);
1876 0 : return thread_block (header, false);
1877 : }
1878 :
1879 3846 : if (tgt_bb->loop_father->header == tgt_bb)
1880 : {
1881 : /* If the target of the threading is a header of a subloop, we need
1882 : to create a preheader for it, so that the headers of the two loops
1883 : do not merge. */
1884 0 : if (EDGE_COUNT (tgt_bb->preds) > 2)
1885 : {
1886 0 : tgt_bb = create_preheader (tgt_bb->loop_father, 0);
1887 0 : gcc_assert (tgt_bb != NULL);
1888 : }
1889 : else
1890 0 : tgt_bb = split_edge (tgt_edge);
1891 : }
1892 :
1893 3846 : basic_block new_preheader;
1894 :
1895 : /* Now consider the case entry edges are redirected to the new entry
1896 : block. Remember one entry edge, so that we can find the new
1897 : preheader (its destination after threading). */
1898 6533 : FOR_EACH_EDGE (e, ei, header->preds)
1899 : {
1900 6533 : if (e->aux)
1901 : break;
1902 : }
1903 :
1904 : /* The duplicate of the header is the new preheader of the loop. Ensure
1905 : that it is placed correctly in the loop hierarchy. */
1906 3846 : set_loop_copy (loop, loop_outer (loop));
1907 :
1908 3846 : thread_block (header, false);
1909 3846 : set_loop_copy (loop, NULL);
1910 3846 : new_preheader = e->dest;
1911 :
1912 : /* Create the new latch block. This is always necessary, as the latch
1913 : must have only a single successor, but the original header had at
1914 : least two successors. */
1915 3846 : loop->latch = NULL;
1916 3846 : edge keep_edge;
1917 3846 : keep_edge = single_succ_edge (new_preheader);
1918 3846 : loop->header = keep_edge->dest;
1919 3846 : latch = make_forwarder_block (tgt_bb, mfb_keep_just, keep_edge);
1920 3846 : loop->header = latch->dest;
1921 3846 : loop->latch = latch->src;
1922 3846 : return true;
1923 :
1924 31610 : fail:
1925 : /* We failed to thread anything. Cancel the requests. */
1926 94855 : FOR_EACH_EDGE (e, ei, header->preds)
1927 : {
1928 63245 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
1929 :
1930 63245 : if (path)
1931 : {
1932 16838 : cancel_thread (path, "Failure in thread_through_loop_header");
1933 16838 : e->aux = NULL;
1934 : }
1935 : }
1936 : return false;
1937 : }
1938 :
1939 : /* E1 and E2 are edges into the same basic block. Return TRUE if the
1940 : PHI arguments associated with those edges are equal or there are no
1941 : PHI arguments, otherwise return FALSE. */
1942 :
1943 : static bool
1944 4519 : phi_args_equal_on_edges (edge e1, edge e2)
1945 : {
1946 4519 : gphi_iterator gsi;
1947 4519 : int indx1 = e1->dest_idx;
1948 4519 : int indx2 = e2->dest_idx;
1949 :
1950 8214 : for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1951 : {
1952 4863 : gphi *phi = gsi.phi ();
1953 :
1954 4863 : if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
1955 4863 : gimple_phi_arg_def (phi, indx2), 0))
1956 : return false;
1957 : }
1958 : return true;
1959 : }
1960 :
1961 : /* Return the number of non-debug statements and non-virtual PHIs in a
1962 : block. */
1963 :
1964 : static unsigned int
1965 5648 : count_stmts_and_phis_in_block (basic_block bb)
1966 : {
1967 5648 : unsigned int num_stmts = 0;
1968 :
1969 5648 : gphi_iterator gpi;
1970 12189 : for (gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi))
1971 13082 : if (!virtual_operand_p (PHI_RESULT (gpi.phi ())))
1972 4038 : num_stmts++;
1973 :
1974 5648 : gimple_stmt_iterator gsi;
1975 47547 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1976 : {
1977 36251 : gimple *stmt = gsi_stmt (gsi);
1978 36251 : if (!is_gimple_debug (stmt))
1979 28974 : num_stmts++;
1980 : }
1981 :
1982 5648 : return num_stmts;
1983 : }
1984 :
1985 :
1986 : /* Walk through the registered jump threads and convert them into a
1987 : form convenient for this pass.
1988 :
1989 : Any block which has incoming edges threaded to outgoing edges
1990 : will have its entry in THREADED_BLOCK set.
1991 :
1992 : Any threaded edge will have its new outgoing edge stored in the
1993 : original edge's AUX field.
1994 :
1995 : This form avoids the need to walk all the edges in the CFG to
1996 : discover blocks which need processing and avoids unnecessary
1997 : hash table lookups to map from threaded edge to new target. */
1998 :
1999 : void
2000 116985 : fwd_jt_path_registry::mark_threaded_blocks (bitmap threaded_blocks)
2001 : {
2002 116985 : unsigned int i;
2003 116985 : bitmap_iterator bi;
2004 116985 : auto_bitmap tmp;
2005 116985 : basic_block bb;
2006 116985 : edge e;
2007 116985 : edge_iterator ei;
2008 :
2009 : /* It is possible to have jump threads in which one is a subpath
2010 : of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
2011 : block and (B, C), (C, D) where no joiner block exists.
2012 :
2013 : When this occurs ignore the jump thread request with the joiner
2014 : block. It's totally subsumed by the simpler jump thread request.
2015 :
2016 : This results in less block copying, simpler CFGs. More importantly,
2017 : when we duplicate the joiner block, B, in this case we will create
2018 : a new threading opportunity that we wouldn't be able to optimize
2019 : until the next jump threading iteration.
2020 :
2021 : So first convert the jump thread requests which do not require a
2022 : joiner block. */
2023 536284 : for (i = 0; i < m_paths.length (); i++)
2024 : {
2025 419299 : vec<jump_thread_edge *> *path = m_paths[i];
2026 :
2027 838598 : if (path->length () > 1
2028 838598 : && (*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
2029 : {
2030 231825 : edge e = (*path)[0]->e;
2031 231825 : e->aux = (void *)path;
2032 231825 : bitmap_set_bit (tmp, e->dest->index);
2033 : }
2034 : }
2035 :
2036 : /* Now iterate again, converting cases where we want to thread
2037 : through a joiner block, but only if no other edge on the path
2038 : already has a jump thread attached to it. We do this in two passes,
2039 : to avoid situations where the order in the paths vec can hide overlapping
2040 : threads (the path is recorded on the incoming edge, so we would miss
2041 : cases where the second path starts at a downstream edge on the same
2042 : path). First record all joiner paths, deleting any in the unexpected
2043 : case where there is already a path for that incoming edge. */
2044 536284 : for (i = 0; i < m_paths.length ();)
2045 : {
2046 419299 : vec<jump_thread_edge *> *path = m_paths[i];
2047 :
2048 419299 : if (path->length () > 1
2049 838598 : && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
2050 : {
2051 : /* Attach the path to the starting edge if none is yet recorded. */
2052 187474 : if ((*path)[0]->e->aux == NULL)
2053 : {
2054 175287 : (*path)[0]->e->aux = path;
2055 175287 : i++;
2056 : }
2057 : else
2058 : {
2059 12187 : remove_path (i);
2060 12187 : cancel_thread (path);
2061 : }
2062 : }
2063 : else
2064 : {
2065 231825 : i++;
2066 : }
2067 : }
2068 :
2069 : /* Second, look for paths that have any other jump thread attached to
2070 : them, and either finish converting them or cancel them. */
2071 524097 : for (i = 0; i < m_paths.length ();)
2072 : {
2073 407112 : vec<jump_thread_edge *> *path = m_paths[i];
2074 407112 : edge e = (*path)[0]->e;
2075 :
2076 407112 : if (path->length () > 1
2077 814224 : && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
2078 : {
2079 : unsigned int j;
2080 477803 : for (j = 1; j < path->length (); j++)
2081 348397 : if ((*path)[j]->e->aux != NULL)
2082 : break;
2083 :
2084 : /* If we iterated through the entire path without exiting the loop,
2085 : then we are good to go, record it. */
2086 175287 : if (j == path->length ())
2087 : {
2088 129406 : bitmap_set_bit (tmp, e->dest->index);
2089 129406 : i++;
2090 : }
2091 : else
2092 : {
2093 45881 : e->aux = NULL;
2094 45881 : remove_path (i);
2095 45881 : cancel_thread (path);
2096 : }
2097 : }
2098 : else
2099 : {
2100 231825 : i++;
2101 : }
2102 : }
2103 :
2104 : /* When optimizing for size, prune all thread paths where statement
2105 : duplication is necessary.
2106 :
2107 : We walk the jump thread path looking for copied blocks. There's
2108 : two types of copied blocks.
2109 :
2110 : EDGE_COPY_SRC_JOINER_BLOCK is always copied and thus we will
2111 : cancel the jump threading request when optimizing for size.
2112 :
2113 : EDGE_COPY_SRC_BLOCK which is copied, but some of its statements
2114 : will be killed by threading. If threading does not kill all of
2115 : its statements, then we should cancel the jump threading request
2116 : when optimizing for size. */
2117 116985 : if (optimize_function_for_size_p (cfun))
2118 : {
2119 10205 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2120 : {
2121 22806 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, i)->preds)
2122 16075 : if (e->aux)
2123 : {
2124 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
2125 :
2126 : unsigned int j;
2127 13518 : for (j = 1; j < path->length (); j++)
2128 : {
2129 11205 : bb = (*path)[j]->e->src;
2130 11205 : if (redirection_block_p (bb))
2131 : ;
2132 8344 : else if ((*path)[j]->type == EDGE_COPY_SRC_JOINER_BLOCK
2133 8344 : || ((*path)[j]->type == EDGE_COPY_SRC_BLOCK
2134 11296 : && (count_stmts_and_phis_in_block (bb)
2135 5648 : != estimate_threading_killed_stmts (bb))))
2136 : break;
2137 : }
2138 :
2139 19892 : if (j != path->length ())
2140 : {
2141 7633 : cancel_thread (path);
2142 7633 : e->aux = NULL;
2143 : }
2144 : else
2145 2313 : bitmap_set_bit (threaded_blocks, i);
2146 : }
2147 : }
2148 : }
2149 : else
2150 113511 : bitmap_copy (threaded_blocks, tmp);
2151 :
2152 : /* If we have a joiner block (J) which has two successors S1 and S2 and
2153 : we are threading though S1 and the final destination of the thread
2154 : is S2, then we must verify that any PHI nodes in S2 have the same
2155 : PHI arguments for the edge J->S2 and J->S1->...->S2.
2156 :
2157 : We used to detect this prior to registering the jump thread, but
2158 : that prohibits propagation of edge equivalences into non-dominated
2159 : PHI nodes as the equivalency test might occur before propagation.
2160 :
2161 : This must also occur after we truncate any jump threading paths
2162 : as this scenario may only show up after truncation.
2163 :
2164 : This works for now, but will need improvement as part of the FSA
2165 : optimization.
2166 :
2167 : Note since we've moved the thread request data to the edges,
2168 : we have to iterate on those rather than the threaded_edges vector. */
2169 368099 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2170 : {
2171 251114 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
2172 909224 : FOR_EACH_EDGE (e, ei, bb->preds)
2173 : {
2174 658110 : if (e->aux)
2175 : {
2176 353598 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
2177 353598 : bool have_joiner = ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK);
2178 :
2179 353598 : if (have_joiner)
2180 : {
2181 126349 : basic_block joiner = e->dest;
2182 126349 : edge final_edge = path->last ()->e;
2183 126349 : basic_block final_dest = final_edge->dest;
2184 126349 : edge e2 = find_edge (joiner, final_dest);
2185 :
2186 126349 : if (e2 && !phi_args_equal_on_edges (e2, final_edge))
2187 : {
2188 1168 : cancel_thread (path);
2189 1168 : e->aux = NULL;
2190 : }
2191 : }
2192 : }
2193 : }
2194 : }
2195 :
2196 : /* Look for jump threading paths which cross multiple loop headers.
2197 :
2198 : The code to thread through loop headers will change the CFG in ways
2199 : that invalidate the cached loop iteration information. So we must
2200 : detect that case and wipe the cached information. */
2201 368099 : EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
2202 : {
2203 251114 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
2204 909224 : FOR_EACH_EDGE (e, ei, bb->preds)
2205 : {
2206 658110 : if (e->aux)
2207 : {
2208 352430 : gcc_assert (loops_state_satisfies_p
2209 : (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS));
2210 : vec<jump_thread_edge *> *path = THREAD_PATH (e);
2211 :
2212 866742 : for (unsigned int i = 0, crossed_headers = 0;
2213 1534628 : i < path->length ();
2214 : i++)
2215 : {
2216 876518 : basic_block dest = (*path)[i]->e->dest;
2217 876518 : basic_block src = (*path)[i]->e->src;
2218 : /* If we enter a loop. */
2219 876518 : if (flow_loop_nested_p (src->loop_father, dest->loop_father))
2220 65166 : ++crossed_headers;
2221 : /* If we step from a block outside an irreducible region
2222 : to a block inside an irreducible region, then we have
2223 : crossed into a loop. */
2224 811352 : else if (! (src->flags & BB_IRREDUCIBLE_LOOP)
2225 807226 : && (dest->flags & BB_IRREDUCIBLE_LOOP))
2226 1743 : ++crossed_headers;
2227 876518 : if (crossed_headers > 1)
2228 : {
2229 9776 : vect_free_loop_info_assumptions
2230 19552 : ((*path)[path->length () - 1]->e->dest->loop_father);
2231 9776 : break;
2232 : }
2233 : }
2234 : }
2235 : }
2236 : }
2237 116985 : }
2238 :
2239 :
2240 : /* Verify that the REGION is a valid jump thread. A jump thread is a special
2241 : case of SEME Single Entry Multiple Exits region in which all nodes in the
2242 : REGION have exactly one incoming edge. The only exception is the first block
2243 : that may not have been connected to the rest of the cfg yet. */
2244 :
2245 : DEBUG_FUNCTION void
2246 1333928 : verify_jump_thread (basic_block *region, unsigned n_region)
2247 : {
2248 3149168 : for (unsigned i = 0; i < n_region; i++)
2249 1815240 : gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
2250 1333928 : }
2251 :
2252 : /* Return true when BB is one of the first N items in BBS. */
2253 :
2254 : static inline bool
2255 2681917 : bb_in_bbs (basic_block bb, basic_block *bbs, int n)
2256 : {
2257 6293156 : for (int i = 0; i < n; i++)
2258 3624874 : if (bb == bbs[i])
2259 : return true;
2260 :
2261 : return false;
2262 : }
2263 :
2264 : void
2265 29 : jt_path_registry::debug_path (FILE *dump_file, int pathno)
2266 : {
2267 29 : vec<jump_thread_edge *> *p = m_paths[pathno];
2268 29 : fprintf (dump_file, "path: ");
2269 185 : for (unsigned i = 0; i < p->length (); ++i)
2270 127 : fprintf (dump_file, "%d -> %d, ",
2271 127 : (*p)[i]->e->src->index, (*p)[i]->e->dest->index);
2272 29 : fprintf (dump_file, "\n");
2273 29 : }
2274 :
2275 : void
2276 0 : jt_path_registry::debug ()
2277 : {
2278 0 : for (unsigned i = 0; i < m_paths.length (); ++i)
2279 0 : debug_path (stderr, i);
2280 0 : }
2281 :
2282 : /* Rewire a jump_thread_edge so that the source block is now a
2283 : threaded source block.
2284 :
2285 : PATH_NUM is an index into the global path table PATHS.
2286 : EDGE_NUM is the jump thread edge number into said path.
2287 :
2288 : Returns TRUE if we were able to successfully rewire the edge. */
2289 :
2290 : bool
2291 87004 : back_jt_path_registry::rewire_first_differing_edge (unsigned path_num,
2292 : unsigned edge_num)
2293 : {
2294 87004 : vec<jump_thread_edge *> *path = m_paths[path_num];
2295 87004 : edge &e = (*path)[edge_num]->e;
2296 87004 : if (dump_file && (dump_flags & TDF_DETAILS))
2297 17 : fprintf (dump_file, "rewiring edge candidate: %d -> %d\n",
2298 17 : e->src->index, e->dest->index);
2299 87004 : basic_block src_copy = get_bb_copy (e->src);
2300 87004 : if (src_copy == NULL)
2301 : {
2302 20882 : if (dump_file && (dump_flags & TDF_DETAILS))
2303 9 : fprintf (dump_file, "ignoring candidate: there is no src COPY\n");
2304 : return false;
2305 : }
2306 66122 : edge new_edge = find_edge (src_copy, e->dest);
2307 : /* If the previously threaded paths created a flow graph where we
2308 : can no longer figure out where to go, give up. */
2309 66122 : if (new_edge == NULL)
2310 : {
2311 5573 : if (dump_file && (dump_flags & TDF_DETAILS))
2312 0 : fprintf (dump_file, "ignoring candidate: we lost our way\n");
2313 : return false;
2314 : }
2315 60549 : e = new_edge;
2316 60549 : return true;
2317 : }
2318 :
2319 : /* Adjust the candidate path CAND_PATH_NUM, which starts on the same
2320 : edge as the path we have just threaded, so it can be threaded within
2321 : the context of the copies that threading made. CURR_PATH is the
2322 : path that was threaded.
2323 :
2324 : Returns TRUE if the candidate survived. If it did not, it has been
2325 : removed from the registry and a different path now sits in its slot. */
2326 :
2327 : bool
2328 129846 : back_jt_path_registry::adjust_one_path (vec<jump_thread_edge *> *curr_path,
2329 : unsigned cand_path_num)
2330 : {
2331 129846 : vec<jump_thread_edge *> *cand_path = m_paths[cand_path_num];
2332 :
2333 129846 : if (dump_file && (dump_flags & TDF_DETAILS))
2334 : {
2335 21 : fprintf (dump_file, "adjusting candidate: ");
2336 21 : debug_path (dump_file, cand_path_num);
2337 : }
2338 :
2339 : /* Find where the candidate differs from the threaded path. Both start
2340 : on the same edge, so J is at least 1. */
2341 259692 : unsigned minlength = MIN (curr_path->length (), cand_path->length ());
2342 129846 : unsigned j;
2343 233566 : for (j = 1; j < minlength; ++j)
2344 169842 : if ((*cand_path)[j]->e != (*curr_path)[j]->e)
2345 : {
2346 66122 : gcc_assert ((*cand_path)[j]->e->src == (*curr_path)[j]->e->src);
2347 : break;
2348 : }
2349 :
2350 : /* If they never differ, the candidate is a prefix of what we threaded, and
2351 : there's nothing left to do. */
2352 259692 : if (j == cand_path->length ())
2353 : {
2354 42842 : remove_path (cand_path_num);
2355 42842 : cancel_thread (cand_path, "Adjusted candidate is EMPTY");
2356 42842 : return false;
2357 : }
2358 :
2359 : /* Edge J leaves a block we have just copied, so rewire it to come out
2360 : of the copy. */
2361 87004 : if (!rewire_first_differing_edge (cand_path_num, j))
2362 : {
2363 26455 : remove_path (cand_path_num);
2364 26455 : cancel_thread (cand_path, "Candidate could not be rewired");
2365 26455 : return false;
2366 : }
2367 :
2368 : /* Chop off from the candidate path any prefix it shares with the
2369 : recently threaded path. */
2370 121098 : if (cand_path->length () - j > 1)
2371 : {
2372 45519 : cand_path->block_remove (0, j);
2373 : /* The candidate started on the edge the threaded path did, and no
2374 : longer does, so remove it from the count. */
2375 45519 : drop_first_edge ((*curr_path)[0]->e);
2376 : /* However the candidate path still must be accounted for. */
2377 45519 : add_first_edge ((*cand_path)[0]->e);
2378 : }
2379 15030 : else if (dump_file && (dump_flags & TDF_DETAILS))
2380 0 : fprintf (dump_file, "Not chopping prefix: candidate would be too short.\n");
2381 :
2382 60549 : if (dump_file && (dump_flags & TDF_DETAILS))
2383 : {
2384 8 : fprintf (dump_file, "adjusted candidate: ");
2385 8 : debug_path (dump_file, cand_path_num);
2386 : }
2387 : return true;
2388 : }
2389 :
2390 : /* After a path has been jump threaded, adjust the remaining paths
2391 : that are subsets of this path, so these paths can be safely
2392 : threaded within the context of the new threaded path.
2393 :
2394 : For example, suppose we have just threaded:
2395 :
2396 : 5 -> 6 -> 7 -> 8 -> 12 => 5 -> 6' -> 7' -> 8' -> 12'
2397 :
2398 : And we have an upcoming threading candidate:
2399 : 5 -> 6 -> 7 -> 8 -> 15 -> 20
2400 :
2401 : This function adjusts the upcoming path into:
2402 : 8' -> 15 -> 20
2403 :
2404 : CURR_PATH_NUM is an index into the global paths table. It
2405 : specifies the path that was just threaded. */
2406 :
2407 : void
2408 1333948 : back_jt_path_registry::adjust_paths_after_duplication (unsigned curr_path_num)
2409 : {
2410 1333948 : vec<jump_thread_edge *> *curr_path = m_paths[curr_path_num];
2411 1333948 : edge curr_first = (*curr_path)[0]->e;
2412 :
2413 : /* CURR_PATH is itself registered, so a count of one means nothing else
2414 : starts here and the scan below won't find a candidate. */
2415 1333948 : if (first_edge_count (curr_first) == 1)
2416 : return;
2417 :
2418 : /* Adjust every other path starting on the edge this one did. */
2419 2536284 : for (unsigned i = 0; i < m_paths.length (); )
2420 : {
2421 : /* The path we just threaded is not a candidate for adjustment. */
2422 2435979 : if (i == curr_path_num)
2423 : {
2424 100305 : ++i;
2425 100305 : continue;
2426 : }
2427 :
2428 : /* Only a path starting where the threaded one did needs adjusting. */
2429 2335674 : if ((*m_paths[i])[0]->e != curr_first)
2430 : {
2431 2205828 : ++i;
2432 2205828 : continue;
2433 : }
2434 :
2435 : /* Adjusting can remove the candidate, and unordered_remove then puts
2436 : a different path in slot I, so look at I again. */
2437 129846 : if (adjust_one_path (curr_path, i))
2438 60549 : ++i;
2439 : }
2440 : }
2441 :
2442 : /* Duplicates a jump-thread path of N_REGION basic blocks.
2443 : The ENTRY edge is redirected to the duplicate of the region.
2444 :
2445 : Remove the last conditional statement in the last basic block in the REGION,
2446 : and create a single fallthru edge pointing to the same destination as the
2447 : EXIT edge.
2448 :
2449 : CURRENT_PATH_NO is an index into the global paths[] table
2450 : specifying the jump-thread path.
2451 :
2452 : Returns false if it is unable to copy the region, true otherwise.
2453 : On failure *FAILURE_REASON says why. */
2454 :
2455 : bool
2456 1362070 : back_jt_path_registry::duplicate_thread_path (edge entry,
2457 : edge exit,
2458 : basic_block *region,
2459 : unsigned n_region,
2460 : unsigned current_path_no,
2461 : const char **failure_reason)
2462 : {
2463 1362070 : unsigned i;
2464 1362070 : class loop *loop = entry->dest->loop_father;
2465 1362070 : edge redirected;
2466 1362070 : profile_count curr_count;
2467 :
2468 1362070 : gcc_checking_assert (n_region && region[n_region - 1] == exit->src);
2469 :
2470 : /* Let EXIT prevail only when its source ends in abnormal edges, which cannot
2471 : be redirected. Ordinary paths commonly thread back into themselves, which
2472 : the prevailing exit does not support as its copy would have to jump back
2473 : into the original region. An abnormal exit reentering the region is
2474 : refused by can_copy_bbs_p either way. */
2475 1362070 : edge prevailing_exit = NULL;
2476 6824482 : for (edge e : exit->src->succs)
2477 2738364 : if (e->flags & EDGE_ABNORMAL)
2478 : {
2479 : prevailing_exit = exit;
2480 : break;
2481 : }
2482 : /* Abnormal successors imply a computed goto, whose successors are
2483 : all abnormal, EXIT included. */
2484 1362070 : gcc_checking_assert (!prevailing_exit || (exit->flags & EDGE_ABNORMAL));
2485 :
2486 1362070 : if (!can_copy_bbs_p (region, n_region, prevailing_exit))
2487 : {
2488 177 : *failure_reason = "Cannot copy the blocks in the path";
2489 177 : return false;
2490 : }
2491 :
2492 : /* Some sanity checking. Note that we do not check for all possible
2493 : missuses of the functions. I.e. if you ask to copy something weird,
2494 : it will work, but the state of structures probably will not be
2495 : correct. */
2496 3191813 : for (i = 0; i < n_region; i++)
2497 : {
2498 : /* We do not handle subloops, i.e. all the blocks must belong to the
2499 : same loop. Unless we thread to the subloop exit and thus the
2500 : path will belong to loop after the threading. */
2501 1857865 : if ((region[i]->loop_father != loop
2502 17810 : && !(loop_exit_edge_p (region[i]->loop_father, exit)
2503 6383 : && exit->dest->loop_father == loop))
2504 : /* Avoid creating alternate entries into the original loop. */
2505 1864248 : || (loop->header == entry->dest
2506 39720 : && region[i] != exit->src
2507 1846438 : && EDGE_COUNT (region[i]->succs) > 1))
2508 : {
2509 27945 : *failure_reason = "Path crosses loops";
2510 27945 : return false;
2511 : }
2512 : }
2513 :
2514 1333948 : initialize_original_copy_tables ();
2515 :
2516 1333948 : set_loop_copy (loop, loop);
2517 :
2518 1333948 : basic_block *region_copy = XNEWVEC (basic_block, n_region);
2519 1333948 : copy_bbs (region, n_region, region_copy, NULL, 0, NULL, loop,
2520 : split_edge_bb_loc (entry), false, prevailing_exit);
2521 :
2522 : /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The
2523 : following code ensures that all the edges exiting the jump-thread path are
2524 : redirected back to the original code: these edges are exceptions
2525 : invalidating the property that is propagated by executing all the blocks of
2526 : the jump-thread path in order. */
2527 :
2528 1333948 : curr_count = entry->count ();
2529 :
2530 3149218 : for (i = 0; i < n_region; i++)
2531 : {
2532 1815270 : edge e;
2533 1815270 : edge_iterator ei;
2534 1815270 : basic_block bb = region_copy[i];
2535 :
2536 : /* Watch inconsistent profile. */
2537 1815270 : if (curr_count > region[i]->count)
2538 73060 : curr_count = region[i]->count;
2539 : /* Scale current BB. */
2540 3141048 : if (region[i]->count.nonzero_p () && curr_count.initialized_p ())
2541 : {
2542 : /* In the middle of the path we only scale the frequencies.
2543 : In last BB we need to update probabilities of outgoing edges
2544 : because we know which one is taken at the threaded path. */
2545 1325778 : if (i + 1 != n_region)
2546 462206 : scale_bbs_frequencies_profile_count (region + i, 1,
2547 : region[i]->count - curr_count,
2548 : region[i]->count);
2549 : else
2550 863572 : update_bb_profile_for_threading (region[i],
2551 : curr_count,
2552 : exit);
2553 1325778 : scale_bbs_frequencies_profile_count (region_copy + i, 1, curr_count,
2554 1325778 : region_copy[i]->count);
2555 : }
2556 :
2557 1815270 : if (single_succ_p (bb))
2558 : {
2559 : /* Make sure the successor is the next node in the path. */
2560 142962 : gcc_assert (i + 1 == n_region
2561 : || region_copy[i + 1] == single_succ_edge (bb)->dest);
2562 142962 : if (i + 1 != n_region)
2563 : {
2564 142873 : curr_count = single_succ_edge (bb)->count ();
2565 : }
2566 1476821 : continue;
2567 : }
2568 :
2569 : /* Special case the last block on the path: make sure that it does not
2570 : jump back on the copied path, including back to itself. */
2571 1672308 : if (i + 1 == n_region)
2572 : {
2573 4015776 : FOR_EACH_EDGE (e, ei, bb->succs)
2574 5363834 : if (bb_in_bbs (e->dest, region_copy, n_region))
2575 : {
2576 13635 : basic_block orig = get_bb_original (e->dest);
2577 13635 : if (orig)
2578 13635 : redirect_edge_and_branch_force (e, orig);
2579 : }
2580 1333859 : continue;
2581 1333859 : }
2582 :
2583 : /* Redirect all other edges jumping to non-adjacent blocks back to the
2584 : original code. */
2585 1015350 : FOR_EACH_EDGE (e, ei, bb->succs)
2586 676901 : if (region_copy[i + 1] != e->dest)
2587 : {
2588 338452 : basic_block orig = get_bb_original (e->dest);
2589 338452 : if (orig)
2590 13045 : redirect_edge_and_branch_force (e, orig);
2591 : }
2592 : else
2593 : {
2594 338449 : curr_count = e->count ();
2595 : }
2596 : }
2597 :
2598 :
2599 1333948 : if (flag_checking)
2600 1333928 : verify_jump_thread (region_copy, n_region);
2601 :
2602 : /* Remove the last branch in the jump thread path. */
2603 1333948 : remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
2604 :
2605 : /* And fixup the flags on the single remaining edge. */
2606 1333948 : edge fix_e = find_edge (region_copy[n_region - 1], exit->dest);
2607 1333948 : fix_e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
2608 1333948 : fix_e->flags |= EDGE_FALLTHRU;
2609 :
2610 1333948 : edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
2611 :
2612 1333948 : if (e)
2613 : {
2614 0 : rescan_loop_exit (e, true, false);
2615 0 : e->probability = profile_probability::always ();
2616 : }
2617 :
2618 : /* Redirect the entry and add the phi node arguments. */
2619 1333948 : if (entry->dest == loop->header)
2620 22237 : mark_loop_for_removal (loop);
2621 1333948 : redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
2622 1333948 : gcc_assert (redirected != NULL);
2623 1333948 : flush_pending_stmts (entry);
2624 :
2625 : /* Add the other PHI node arguments. */
2626 1333948 : add_phi_args_after_copy (region_copy, n_region, NULL);
2627 :
2628 1333948 : free (region_copy);
2629 :
2630 1333948 : adjust_paths_after_duplication (current_path_no);
2631 :
2632 1333948 : free_original_copy_tables ();
2633 1333948 : return true;
2634 : }
2635 :
2636 : /* Return true when PATH is a valid jump-thread path. */
2637 :
2638 : static bool
2639 1382732 : valid_jump_thread_path (vec<jump_thread_edge *> *path)
2640 : {
2641 1382732 : unsigned len = path->length ();
2642 :
2643 : /* Check that the path is connected. */
2644 3300695 : for (unsigned int j = 0; j < len - 1; j++)
2645 : {
2646 1938625 : edge e = (*path)[j]->e;
2647 1938625 : if (e->dest != (*path)[j+1]->e->src)
2648 : return false;
2649 : }
2650 : return true;
2651 : }
2652 :
2653 : /* Remove any queued jump threads that include edge E.
2654 :
2655 : We don't actually remove them here, just record the edges into ax
2656 : hash table. That way we can do the search once per iteration of
2657 : DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */
2658 :
2659 : void
2660 467425 : fwd_jt_path_registry::remove_jump_threads_including (edge_def *e)
2661 : {
2662 467425 : if (!m_paths.exists () || !flag_thread_jumps)
2663 : return;
2664 :
2665 467393 : edge *slot = m_removed_edges->find_slot (e, INSERT);
2666 467393 : *slot = e;
2667 : }
2668 :
2669 : /* Thread all paths that have been queued for jump threading, and
2670 : update the CFG accordingly.
2671 :
2672 : It is the caller's responsibility to fix the dominance information
2673 : and rewrite duplicated SSA_NAMEs back into SSA form.
2674 :
2675 : If PEEL_LOOP_HEADERS is false, avoid threading edges through loop
2676 : headers if it does not simplify the loop.
2677 :
2678 : Returns true if one or more edges were threaded. */
2679 :
2680 : bool
2681 8659979 : jt_path_registry::thread_through_all_blocks (bool peel_loop_headers)
2682 : {
2683 8659979 : if (m_paths.length () == 0)
2684 : return false;
2685 :
2686 435785 : m_num_threaded_edges = 0;
2687 :
2688 435785 : bool retval = update_cfg (peel_loop_headers);
2689 :
2690 435785 : statistics_counter_event (cfun, "Jumps threaded", m_num_threaded_edges);
2691 :
2692 435785 : if (retval)
2693 : {
2694 395888 : loops_state_set (LOOPS_NEED_FIXUP);
2695 395888 : return true;
2696 : }
2697 : return false;
2698 : }
2699 :
2700 : /* This is the backward threader version of thread_through_all_blocks
2701 : using a generic BB copier. */
2702 :
2703 : bool
2704 318800 : back_jt_path_registry::update_cfg (bool /*peel_loop_headers*/)
2705 : {
2706 318800 : bool retval = false;
2707 318800 : hash_set<edge> visited_starting_edges;
2708 :
2709 2035362 : while (m_paths.length ())
2710 : {
2711 1397762 : vec<jump_thread_edge *> *path = m_paths[0];
2712 1397762 : edge entry = (*path)[0]->e;
2713 :
2714 : /* Do not jump-thread twice from the same starting edge.
2715 :
2716 : Previously we only checked that we weren't threading twice
2717 : from the same BB, but that was too restrictive. Imagine a
2718 : path that starts from GIMPLE_COND(x_123 == 0,...), where both
2719 : edges out of this conditional yield paths that can be
2720 : threaded (for example, both lead to an x_123==0 or x_123!=0
2721 : conditional further down the line. */
2722 1397762 : if (visited_starting_edges.contains (entry)
2723 : /* We may not want to realize this jump thread path for
2724 : various reasons. So check it first. */
2725 1397762 : || !valid_jump_thread_path (path))
2726 : {
2727 : /* Remove invalid jump-thread paths. */
2728 35692 : remove_path (0);
2729 35692 : cancel_thread (path, "Avoiding threading twice from same edge");
2730 35692 : continue;
2731 : }
2732 :
2733 1362070 : unsigned len = path->length ();
2734 1362070 : edge exit = (*path)[len - 1]->e;
2735 1362070 : basic_block *region = XNEWVEC (basic_block, len - 1);
2736 :
2737 4613296 : for (unsigned int j = 0; j < len - 1; j++)
2738 1889156 : region[j] = (*path)[j]->e->dest;
2739 :
2740 1362070 : const char *failure_reason = NULL;
2741 1362070 : if (duplicate_thread_path (entry, exit, region, len - 1, 0,
2742 : &failure_reason))
2743 : {
2744 : /* We do not update dominance info. */
2745 1333948 : free_dominance_info (CDI_DOMINATORS);
2746 1333948 : visited_starting_edges.add (entry);
2747 1333948 : retval = true;
2748 1333948 : m_num_threaded_edges++;
2749 1333948 : path->release ();
2750 : }
2751 : else
2752 28122 : cancel_thread (path, failure_reason);
2753 :
2754 : /* Both arms above release PATH, so name the edge it started on. */
2755 1362070 : remove_path (0, entry);
2756 1362070 : free (region);
2757 : }
2758 318800 : return retval;
2759 318800 : }
2760 :
2761 : /* This is the forward threader version of thread_through_all_blocks,
2762 : using a custom BB copier. */
2763 :
2764 : bool
2765 116985 : fwd_jt_path_registry::update_cfg (bool may_peel_loop_headers)
2766 : {
2767 116985 : bool retval = false;
2768 :
2769 : /* Remove any paths that referenced removed edges. */
2770 116985 : if (m_removed_edges)
2771 655982 : for (unsigned i = 0; i < m_paths.length (); )
2772 : {
2773 538997 : unsigned int j;
2774 538997 : vec<jump_thread_edge *> *path = m_paths[i];
2775 :
2776 1764172 : for (j = 0; j < path->length (); j++)
2777 : {
2778 1344873 : edge e = (*path)[j]->e;
2779 1344873 : if (m_removed_edges->find_slot (e, NO_INSERT)
2780 2570048 : || (((*path)[j]->type == EDGE_COPY_SRC_BLOCK
2781 844539 : || (*path)[j]->type == EDGE_COPY_SRC_JOINER_BLOCK)
2782 602229 : && !can_duplicate_block_p (e->src)))
2783 : break;
2784 : }
2785 :
2786 1077994 : if (j != path->length ())
2787 : {
2788 119698 : remove_path (i);
2789 119698 : cancel_thread (path, "Thread references removed edge");
2790 119698 : continue;
2791 : }
2792 419299 : i++;
2793 : }
2794 :
2795 116985 : auto_bitmap threaded_blocks;
2796 116985 : mark_threaded_blocks (threaded_blocks);
2797 :
2798 116985 : initialize_original_copy_tables ();
2799 :
2800 : /* The order in which we process jump threads can be important.
2801 :
2802 : Consider if we have two jump threading paths A and B. If the
2803 : target edge of A is the starting edge of B and we thread path A
2804 : first, then we create an additional incoming edge into B->dest that
2805 : we cannot discover as a jump threading path on this iteration.
2806 :
2807 : If we instead thread B first, then the edge into B->dest will have
2808 : already been redirected before we process path A and path A will
2809 : natually, with no further work, target the redirected path for B.
2810 :
2811 : An post-order is sufficient here. Compute the ordering first, then
2812 : process the blocks. */
2813 116985 : if (!bitmap_empty_p (threaded_blocks))
2814 : {
2815 103237 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
2816 103237 : unsigned int postorder_num = post_order_compute (postorder, false, false);
2817 7358014 : for (unsigned int i = 0; i < postorder_num; i++)
2818 : {
2819 7254777 : unsigned int indx = postorder[i];
2820 7254777 : if (bitmap_bit_p (threaded_blocks, indx))
2821 : {
2822 246091 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, indx);
2823 246091 : retval |= thread_block (bb, true);
2824 : }
2825 : }
2826 103237 : free (postorder);
2827 : }
2828 :
2829 : /* Then perform the threading through loop headers. We start with the
2830 : innermost loop, so that the changes in cfg we perform won't affect
2831 : further threading. */
2832 786631 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
2833 : {
2834 835208 : if (!loop->header
2835 435676 : || !bitmap_bit_p (threaded_blocks, loop->header->index))
2836 399532 : continue;
2837 :
2838 36144 : retval |= thread_through_loop_header (loop, may_peel_loop_headers);
2839 116985 : }
2840 :
2841 : /* All jump threading paths should have been resolved at this
2842 : point. Verify that is the case. */
2843 116985 : basic_block bb;
2844 8389885 : FOR_EACH_BB_FN (bb, cfun)
2845 : {
2846 8272900 : edge_iterator ei;
2847 8272900 : edge e;
2848 20397863 : FOR_EACH_EDGE (e, ei, bb->preds)
2849 12124963 : gcc_assert (e->aux == NULL);
2850 : }
2851 :
2852 116985 : free_original_copy_tables ();
2853 :
2854 116985 : return retval;
2855 116985 : }
2856 :
2857 : bool
2858 3748486 : jt_path_registry::cancel_invalid_paths (vec<jump_thread_edge *> &path)
2859 : {
2860 3748486 : gcc_checking_assert (!path.is_empty ());
2861 3748486 : edge entry = path[0]->e;
2862 3748486 : edge exit = path[path.length () - 1]->e;
2863 3748486 : bool seen_latch = false;
2864 3748486 : int loops_crossed = 0;
2865 3748486 : bool crossed_latch = false;
2866 3748486 : bool crossed_loop_header = false;
2867 : // Use ->dest here instead of ->src to ignore the first block. The
2868 : // first block is allowed to be in a different loop, since it'll be
2869 : // redirected. See similar comment in profitable_path_p: "we don't
2870 : // care about that block...".
2871 3748486 : loop_p loop = entry->dest->loop_father;
2872 3748486 : loop_p curr_loop = loop;
2873 :
2874 12915708 : for (unsigned int i = 0; i < path.length (); i++)
2875 : {
2876 9167222 : edge e = path[i]->e;
2877 :
2878 9167222 : if (e == NULL)
2879 : {
2880 : // NULL outgoing edges on a path can happen for jumping to a
2881 : // constant address.
2882 0 : cancel_thread (&path, "Found NULL edge in jump threading path");
2883 0 : return true;
2884 : }
2885 :
2886 9167222 : if (loop->latch == e->src || loop->latch == e->dest)
2887 : {
2888 965631 : seen_latch = true;
2889 : // Like seen_latch, but excludes the first block.
2890 965631 : if (e->src != entry->src)
2891 916640 : crossed_latch = true;
2892 : }
2893 :
2894 9167222 : if (e->dest->loop_father != curr_loop)
2895 : {
2896 495552 : curr_loop = e->dest->loop_father;
2897 495552 : ++loops_crossed;
2898 : }
2899 :
2900 : // ?? Avoid threading through loop headers that remain in the
2901 : // loop, as such threadings tend to create sub-loops which
2902 : // _might_ be OK ??.
2903 9167222 : if (e->dest->loop_father->header == e->dest
2904 9167222 : && !flow_loop_nested_p (exit->dest->loop_father,
2905 : e->dest->loop_father))
2906 : crossed_loop_header = true;
2907 :
2908 9167222 : if (flag_checking && !m_backedge_threads)
2909 3047602 : gcc_assert ((path[i]->e->flags & EDGE_DFS_BACK) == 0);
2910 : }
2911 :
2912 : // If we crossed a loop into an outer loop without crossing the
2913 : // latch, this is just an early exit from the loop.
2914 3748486 : if (loops_crossed == 1
2915 3748486 : && !crossed_latch
2916 3748486 : && flow_loop_nested_p (exit->dest->loop_father, exit->src->loop_father))
2917 : return false;
2918 :
2919 3672718 : if (seen_latch && entry->dest == loop->header)
2920 : {
2921 758810 : cancel_thread (&path, "Threading through latch from loop header "
2922 : "peels loop");
2923 758810 : return true;
2924 : }
2925 :
2926 2913908 : if (cfun->curr_properties & PROP_loop_opts_done)
2927 : return false;
2928 :
2929 2319128 : if (seen_latch && empty_block_p (loop->latch))
2930 : {
2931 18093 : cancel_thread (&path, "Threading through latch before loop opts "
2932 : "would create non-empty latch");
2933 18093 : return true;
2934 : }
2935 2301035 : if (loops_crossed)
2936 : {
2937 278687 : cancel_thread (&path, "Path crosses loops");
2938 278687 : return true;
2939 : }
2940 : // The path should either start and end in the same loop or exit the
2941 : // loop it starts in but never enter a loop. This also catches
2942 : // creating irreducible loops, not only rotation.
2943 2022348 : if (entry->src->loop_father != exit->dest->loop_father
2944 2694581 : && !flow_loop_nested_p (exit->src->loop_father,
2945 672233 : entry->dest->loop_father))
2946 : {
2947 672233 : cancel_thread (&path, "Path rotates loop");
2948 672233 : return true;
2949 : }
2950 1350115 : if (crossed_loop_header)
2951 : {
2952 14607 : cancel_thread (&path, "Path crosses loop header but does not exit it");
2953 14607 : return true;
2954 : }
2955 : return false;
2956 : }
2957 :
2958 : /* Register a jump threading opportunity. We queue up all the jump
2959 : threading opportunities discovered by a pass and update the CFG
2960 : and SSA form all at once.
2961 :
2962 : E is the edge we can thread, E2 is the new target edge, i.e., we
2963 : are effectively recording that E->dest can be changed to E2->dest
2964 : after fixing the SSA graph.
2965 :
2966 : Return TRUE if PATH was successfully threaded. */
2967 :
2968 : bool
2969 3748486 : jt_path_registry::register_jump_thread (vec<jump_thread_edge *> *path)
2970 : {
2971 3748486 : gcc_checking_assert (flag_thread_jumps);
2972 :
2973 3748486 : if (!dbg_cnt (registered_jump_thread))
2974 : {
2975 0 : path->release ();
2976 0 : return false;
2977 : }
2978 :
2979 3748486 : if (cancel_invalid_paths (*path))
2980 : return false;
2981 :
2982 2006056 : if (dump_file && (dump_flags & TDF_DETAILS))
2983 155 : dump_jump_thread_path (dump_file, *path, true);
2984 :
2985 2006056 : m_paths.safe_push (path);
2986 2006056 : add_first_edge ((*path)[0]->e);
2987 2006056 : return true;
2988 : }
2989 :
2990 : /* Return how many uses of T there are within BB, as long as there
2991 : aren't any uses outside BB. If there are any uses outside BB,
2992 : return -1 if there's at most one use within BB, or -2 if there is
2993 : more than one use within BB. */
2994 :
2995 : static int
2996 1909852 : uses_in_bb (tree t, basic_block bb)
2997 : {
2998 1909852 : int uses = 0;
2999 1909852 : bool outside_bb = false;
3000 :
3001 1909852 : imm_use_iterator iter;
3002 1909852 : use_operand_p use_p;
3003 5909179 : FOR_EACH_IMM_USE_FAST (use_p, iter, t)
3004 : {
3005 4110197 : if (is_gimple_debug (USE_STMT (use_p)))
3006 735118 : continue;
3007 :
3008 3375079 : if (gimple_bb (USE_STMT (use_p)) != bb)
3009 : outside_bb = true;
3010 : else
3011 2234877 : uses++;
3012 :
3013 3375079 : if (outside_bb && uses > 1)
3014 110870 : return -2;
3015 110870 : }
3016 :
3017 1798982 : if (outside_bb)
3018 512459 : return -1;
3019 :
3020 : return uses;
3021 : }
3022 :
3023 : /* Starting from the final control flow stmt in BB, assuming it will
3024 : be removed, follow uses in to-be-removed stmts back to their defs
3025 : and count how many defs are to become dead and be removed as
3026 : well. */
3027 :
3028 : unsigned int
3029 1712121 : estimate_threading_killed_stmts (basic_block bb)
3030 : {
3031 1712121 : int killed_stmts = 0;
3032 1712121 : hash_map<tree, int> ssa_remaining_uses;
3033 1712121 : auto_vec<gimple *, 4> dead_worklist;
3034 :
3035 : /* If the block has only two predecessors, threading will turn phi
3036 : dsts into either src, so count them as dead stmts. */
3037 1712121 : bool drop_all_phis = EDGE_COUNT (bb->preds) == 2;
3038 :
3039 1712121 : if (drop_all_phis)
3040 737931 : for (gphi_iterator gsi = gsi_start_phis (bb);
3041 2510324 : !gsi_end_p (gsi); gsi_next (&gsi))
3042 : {
3043 1772393 : gphi *phi = gsi.phi ();
3044 1772393 : tree dst = gimple_phi_result (phi);
3045 :
3046 : /* We don't count virtual PHIs as stmts in
3047 : record_temporary_equivalences_from_phis. */
3048 3544786 : if (virtual_operand_p (dst))
3049 522927 : continue;
3050 :
3051 1249466 : killed_stmts++;
3052 : }
3053 :
3054 3424242 : if (gsi_end_p (gsi_last_bb (bb)))
3055 0 : return killed_stmts;
3056 :
3057 1712121 : gimple *stmt = gsi_stmt (gsi_last_bb (bb));
3058 1712121 : if (gimple_code (stmt) != GIMPLE_COND
3059 : && gimple_code (stmt) != GIMPLE_GOTO
3060 : && gimple_code (stmt) != GIMPLE_SWITCH)
3061 536473 : return killed_stmts;
3062 :
3063 : /* The control statement is always dead. */
3064 1175648 : killed_stmts++;
3065 1175648 : dead_worklist.quick_push (stmt);
3066 4648516 : while (!dead_worklist.is_empty ())
3067 : {
3068 2297220 : stmt = dead_worklist.pop ();
3069 :
3070 2297220 : ssa_op_iter iter;
3071 2297220 : use_operand_p use_p;
3072 5020798 : FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
3073 : {
3074 2723578 : tree t = USE_FROM_PTR (use_p);
3075 2723578 : gimple *def = SSA_NAME_DEF_STMT (t);
3076 :
3077 2723578 : if (gimple_bb (def) == bb
3078 2137261 : && (gimple_code (def) != GIMPLE_PHI
3079 141243 : || !drop_all_phis)
3080 4766288 : && !gimple_has_side_effects (def))
3081 : {
3082 1966302 : int *usesp = ssa_remaining_uses.get (t);
3083 1966302 : int uses;
3084 :
3085 1966302 : if (usesp)
3086 56450 : uses = *usesp;
3087 : else
3088 1909852 : uses = uses_in_bb (t, bb);
3089 :
3090 1966302 : gcc_assert (uses);
3091 :
3092 : /* Don't bother recording the expected use count if we
3093 : won't find any further uses within BB. */
3094 1966302 : if (!usesp && (uses < -1 || uses > 1))
3095 : {
3096 280755 : usesp = &ssa_remaining_uses.get_or_insert (t);
3097 280755 : *usesp = uses;
3098 : }
3099 :
3100 1966302 : if (uses < 0)
3101 656620 : continue;
3102 :
3103 1309682 : --uses;
3104 1309682 : if (usesp)
3105 193044 : *usesp = uses;
3106 :
3107 1309682 : if (!uses)
3108 : {
3109 1134516 : killed_stmts++;
3110 1134516 : if (usesp)
3111 17878 : ssa_remaining_uses.remove (t);
3112 1134516 : if (gimple_code (def) != GIMPLE_PHI)
3113 1121572 : dead_worklist.safe_push (def);
3114 : }
3115 : }
3116 : }
3117 : }
3118 :
3119 1175648 : if (dump_file)
3120 19 : fprintf (dump_file, "threading bb %i kills %i stmts\n",
3121 : bb->index, killed_stmts);
3122 :
3123 1175648 : return killed_stmts;
3124 1712121 : }
|
