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