]>
Commit | Line | Data |
---|---|---|
a8046f60 | 1 | /* Thread edges through blocks and update the control flow and SSA graphs. |
d91f7526 | 2 | Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 Free Software Foundation, |
f0b5f617 | 3 | Inc. |
a8046f60 | 4 | |
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
a8046f60 | 10 | any later version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
a8046f60 | 20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "flags.h" | |
a8046f60 | 27 | #include "tm_p.h" |
a8046f60 | 28 | #include "basic-block.h" |
29 | #include "output.h" | |
a8046f60 | 30 | #include "function.h" |
a8046f60 | 31 | #include "tree-flow.h" |
32 | #include "tree-dump.h" | |
33 | #include "tree-pass.h" | |
388d1fc1 | 34 | #include "cfgloop.h" |
a8046f60 | 35 | |
36 | /* Given a block B, update the CFG and SSA graph to reflect redirecting | |
37 | one or more in-edges to B to instead reach the destination of an | |
38 | out-edge from B while preserving any side effects in B. | |
39 | ||
0c6d8c36 | 40 | i.e., given A->B and B->C, change A->B to be A->C yet still preserve the |
a8046f60 | 41 | side effects of executing B. |
42 | ||
43 | 1. Make a copy of B (including its outgoing edges and statements). Call | |
44 | the copy B'. Note B' has no incoming edges or PHIs at this time. | |
45 | ||
46 | 2. Remove the control statement at the end of B' and all outgoing edges | |
47 | except B'->C. | |
48 | ||
49 | 3. Add a new argument to each PHI in C with the same value as the existing | |
50 | argument associated with edge B->C. Associate the new PHI arguments | |
51 | with the edge B'->C. | |
52 | ||
53 | 4. For each PHI in B, find or create a PHI in B' with an identical | |
7a635e9c | 54 | PHI_RESULT. Add an argument to the PHI in B' which has the same |
a8046f60 | 55 | value as the PHI in B associated with the edge A->B. Associate |
56 | the new argument in the PHI in B' with the edge A->B. | |
57 | ||
58 | 5. Change the edge A->B to A->B'. | |
59 | ||
60 | 5a. This automatically deletes any PHI arguments associated with the | |
61 | edge A->B in B. | |
62 | ||
63 | 5b. This automatically associates each new argument added in step 4 | |
64 | with the edge A->B'. | |
65 | ||
66 | 6. Repeat for other incoming edges into B. | |
67 | ||
68 | 7. Put the duplicated resources in B and all the B' blocks into SSA form. | |
69 | ||
70 | Note that block duplication can be minimized by first collecting the | |
f0b5f617 | 71 | set of unique destination blocks that the incoming edges should |
778182c1 | 72 | be threaded to. Block duplication can be further minimized by using |
a8046f60 | 73 | B instead of creating B' for one destination if all edges into B are |
778182c1 | 74 | going to be threaded to a successor of B. |
a8046f60 | 75 | |
778182c1 | 76 | We further reduce the number of edges and statements we create by |
77 | not copying all the outgoing edges and the control statement in | |
78 | step #1. We instead create a template block without the outgoing | |
79 | edges and duplicate the template. */ | |
80 | ||
81 | ||
82 | /* Steps #5 and #6 of the above algorithm are best implemented by walking | |
83 | all the incoming edges which thread to the same destination edge at | |
84 | the same time. That avoids lots of table lookups to get information | |
85 | for the destination edge. | |
86 | ||
87 | To realize that implementation we create a list of incoming edges | |
88 | which thread to the same outgoing edge. Thus to implement steps | |
89 | #5 and #6 we traverse our hash table of outgoing edge information. | |
90 | For each entry we walk the list of incoming edges which thread to | |
91 | the current outgoing edge. */ | |
92 | ||
93 | struct el | |
94 | { | |
95 | edge e; | |
96 | struct el *next; | |
97 | }; | |
a8046f60 | 98 | |
99 | /* Main data structure recording information regarding B's duplicate | |
100 | blocks. */ | |
101 | ||
778182c1 | 102 | /* We need to efficiently record the unique thread destinations of this |
103 | block and specific information associated with those destinations. We | |
104 | may have many incoming edges threaded to the same outgoing edge. This | |
c5d4a10b | 105 | can be naturally implemented with a hash table. */ |
778182c1 | 106 | |
a8046f60 | 107 | struct redirection_data |
108 | { | |
109 | /* A duplicate of B with the trailing control statement removed and which | |
110 | targets a single successor of B. */ | |
111 | basic_block dup_block; | |
112 | ||
113 | /* An outgoing edge from B. DUP_BLOCK will have OUTGOING_EDGE->dest as | |
114 | its single successor. */ | |
115 | edge outgoing_edge; | |
778182c1 | 116 | |
117 | /* A list of incoming edges which we want to thread to | |
118 | OUTGOING_EDGE->dest. */ | |
119 | struct el *incoming_edges; | |
120 | ||
121 | /* Flag indicating whether or not we should create a duplicate block | |
122 | for this thread destination. This is only true if we are threading | |
123 | all incoming edges and thus are using BB itself as a duplicate block. */ | |
124 | bool do_not_duplicate; | |
a8046f60 | 125 | }; |
126 | ||
a3d0fd80 | 127 | /* Main data structure to hold information for duplicates of BB. */ |
778182c1 | 128 | static htab_t redirection_data; |
129 | ||
130 | /* Data structure of information to pass to hash table traversal routines. */ | |
131 | struct local_info | |
132 | { | |
133 | /* The current block we are working on. */ | |
134 | basic_block bb; | |
135 | ||
136 | /* A template copy of BB with no outgoing edges or control statement that | |
137 | we use for creating copies. */ | |
138 | basic_block template_block; | |
388d1fc1 | 139 | |
140 | /* TRUE if we thread one or more jumps, FALSE otherwise. */ | |
141 | bool jumps_threaded; | |
778182c1 | 142 | }; |
a3d0fd80 | 143 | |
3cebc9d2 | 144 | /* Passes which use the jump threading code register jump threading |
145 | opportunities as they are discovered. We keep the registered | |
146 | jump threading opportunities in this vector as edge pairs | |
147 | (original_edge, target_edge). */ | |
3cebc9d2 | 148 | static VEC(edge,heap) *threaded_edges; |
149 | ||
150 | ||
5236b8bb | 151 | /* Jump threading statistics. */ |
152 | ||
153 | struct thread_stats_d | |
154 | { | |
155 | unsigned long num_threaded_edges; | |
156 | }; | |
157 | ||
158 | struct thread_stats_d thread_stats; | |
159 | ||
160 | ||
f582bb6c | 161 | /* Remove the last statement in block BB if it is a control statement |
162 | Also remove all outgoing edges except the edge which reaches DEST_BB. | |
163 | If DEST_BB is NULL, then remove all outgoing edges. */ | |
a8046f60 | 164 | |
165 | static void | |
f582bb6c | 166 | remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb) |
a8046f60 | 167 | { |
75a70cf9 | 168 | gimple_stmt_iterator gsi; |
cd665a06 | 169 | edge e; |
170 | edge_iterator ei; | |
a8046f60 | 171 | |
75a70cf9 | 172 | gsi = gsi_last_bb (bb); |
a8046f60 | 173 | |
f582bb6c | 174 | /* If the duplicate ends with a control statement, then remove it. |
a8046f60 | 175 | |
f582bb6c | 176 | Note that if we are duplicating the template block rather than the |
177 | original basic block, then the duplicate might not have any real | |
178 | statements in it. */ | |
75a70cf9 | 179 | if (!gsi_end_p (gsi) |
180 | && gsi_stmt (gsi) | |
181 | && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND | |
182 | || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO | |
183 | || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH)) | |
184 | gsi_remove (&gsi, true); | |
a8046f60 | 185 | |
cd665a06 | 186 | for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) |
a8046f60 | 187 | { |
a8046f60 | 188 | if (e->dest != dest_bb) |
0891994d | 189 | remove_edge (e); |
cd665a06 | 190 | else |
191 | ei_next (&ei); | |
a8046f60 | 192 | } |
a8046f60 | 193 | } |
194 | ||
195 | /* Create a duplicate of BB which only reaches the destination of the edge | |
196 | stored in RD. Record the duplicate block in RD. */ | |
197 | ||
198 | static void | |
199 | create_block_for_threading (basic_block bb, struct redirection_data *rd) | |
200 | { | |
a8046f60 | 201 | /* We can use the generic block duplication code and simply remove |
202 | the stuff we do not need. */ | |
c4d867e0 | 203 | rd->dup_block = duplicate_block (bb, NULL, NULL); |
a8046f60 | 204 | |
615dd397 | 205 | /* Zero out the profile, since the block is unreachable for now. */ |
206 | rd->dup_block->frequency = 0; | |
207 | rd->dup_block->count = 0; | |
208 | ||
a8046f60 | 209 | /* The call to duplicate_block will copy everything, including the |
f582bb6c | 210 | useless COND_EXPR or SWITCH_EXPR at the end of BB. We just remove |
a8046f60 | 211 | the useless COND_EXPR or SWITCH_EXPR here rather than having a |
f582bb6c | 212 | specialized block copier. We also remove all outgoing edges |
213 | from the duplicate block. The appropriate edge will be created | |
214 | later. */ | |
215 | remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL); | |
a8046f60 | 216 | } |
217 | ||
778182c1 | 218 | /* Hashing and equality routines for our hash table. */ |
219 | static hashval_t | |
220 | redirection_data_hash (const void *p) | |
221 | { | |
aae87fc3 | 222 | edge e = ((const struct redirection_data *)p)->outgoing_edge; |
8824bd28 | 223 | return e->dest->index; |
778182c1 | 224 | } |
225 | ||
226 | static int | |
227 | redirection_data_eq (const void *p1, const void *p2) | |
228 | { | |
aae87fc3 | 229 | edge e1 = ((const struct redirection_data *)p1)->outgoing_edge; |
230 | edge e2 = ((const struct redirection_data *)p2)->outgoing_edge; | |
778182c1 | 231 | |
232 | return e1 == e2; | |
233 | } | |
234 | ||
235 | /* Given an outgoing edge E lookup and return its entry in our hash table. | |
236 | ||
237 | If INSERT is true, then we insert the entry into the hash table if | |
238 | it is not already present. INCOMING_EDGE is added to the list of incoming | |
239 | edges associated with E in the hash table. */ | |
240 | ||
241 | static struct redirection_data * | |
6d7413d8 | 242 | lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert) |
778182c1 | 243 | { |
244 | void **slot; | |
245 | struct redirection_data *elt; | |
246 | ||
247 | /* Build a hash table element so we can see if E is already | |
248 | in the table. */ | |
4c36ffe6 | 249 | elt = XNEW (struct redirection_data); |
778182c1 | 250 | elt->outgoing_edge = e; |
251 | elt->dup_block = NULL; | |
252 | elt->do_not_duplicate = false; | |
253 | elt->incoming_edges = NULL; | |
254 | ||
255 | slot = htab_find_slot (redirection_data, elt, insert); | |
256 | ||
257 | /* This will only happen if INSERT is false and the entry is not | |
258 | in the hash table. */ | |
259 | if (slot == NULL) | |
260 | { | |
261 | free (elt); | |
262 | return NULL; | |
263 | } | |
264 | ||
265 | /* This will only happen if E was not in the hash table and | |
266 | INSERT is true. */ | |
267 | if (*slot == NULL) | |
268 | { | |
269 | *slot = (void *)elt; | |
4c36ffe6 | 270 | elt->incoming_edges = XNEW (struct el); |
778182c1 | 271 | elt->incoming_edges->e = incoming_edge; |
272 | elt->incoming_edges->next = NULL; | |
273 | return elt; | |
274 | } | |
275 | /* E was in the hash table. */ | |
276 | else | |
277 | { | |
278 | /* Free ELT as we do not need it anymore, we will extract the | |
279 | relevant entry from the hash table itself. */ | |
280 | free (elt); | |
281 | ||
282 | /* Get the entry stored in the hash table. */ | |
283 | elt = (struct redirection_data *) *slot; | |
284 | ||
285 | /* If insertion was requested, then we need to add INCOMING_EDGE | |
286 | to the list of incoming edges associated with E. */ | |
287 | if (insert) | |
288 | { | |
4c36ffe6 | 289 | struct el *el = XNEW (struct el); |
778182c1 | 290 | el->next = elt->incoming_edges; |
291 | el->e = incoming_edge; | |
292 | elt->incoming_edges = el; | |
293 | } | |
294 | ||
295 | return elt; | |
296 | } | |
297 | } | |
298 | ||
299 | /* Given a duplicate block and its single destination (both stored | |
300 | in RD). Create an edge between the duplicate and its single | |
301 | destination. | |
302 | ||
303 | Add an additional argument to any PHI nodes at the single | |
304 | destination. */ | |
305 | ||
306 | static void | |
42b013bc | 307 | create_edge_and_update_destination_phis (struct redirection_data *rd, |
308 | basic_block bb) | |
778182c1 | 309 | { |
42b013bc | 310 | edge e = make_edge (bb, rd->outgoing_edge->dest, EDGE_FALLTHRU); |
75a70cf9 | 311 | gimple_stmt_iterator gsi; |
778182c1 | 312 | |
f9614b84 | 313 | rescan_loop_exit (e, true, false); |
421e19dd | 314 | e->probability = REG_BR_PROB_BASE; |
42b013bc | 315 | e->count = bb->count; |
7e0311ae | 316 | e->aux = rd->outgoing_edge->aux; |
421e19dd | 317 | |
778182c1 | 318 | /* If there are any PHI nodes at the destination of the outgoing edge |
319 | from the duplicate block, then we will need to add a new argument | |
320 | to them. The argument should have the same value as the argument | |
321 | associated with the outgoing edge stored in RD. */ | |
75a70cf9 | 322 | for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) |
778182c1 | 323 | { |
75a70cf9 | 324 | gimple phi = gsi_stmt (gsi); |
efbcb6de | 325 | source_location locus; |
77ae8b0f | 326 | int indx = rd->outgoing_edge->dest_idx; |
efbcb6de | 327 | |
328 | locus = gimple_phi_arg_location (phi, indx); | |
329 | add_phi_arg (phi, gimple_phi_arg_def (phi, indx), e, locus); | |
778182c1 | 330 | } |
331 | } | |
332 | ||
333 | /* Hash table traversal callback routine to create duplicate blocks. */ | |
334 | ||
335 | static int | |
336 | create_duplicates (void **slot, void *data) | |
337 | { | |
338 | struct redirection_data *rd = (struct redirection_data *) *slot; | |
339 | struct local_info *local_info = (struct local_info *)data; | |
340 | ||
341 | /* If this entry should not have a duplicate created, then there's | |
342 | nothing to do. */ | |
343 | if (rd->do_not_duplicate) | |
344 | return 1; | |
345 | ||
346 | /* Create a template block if we have not done so already. Otherwise | |
347 | use the template to create a new block. */ | |
348 | if (local_info->template_block == NULL) | |
349 | { | |
350 | create_block_for_threading (local_info->bb, rd); | |
351 | local_info->template_block = rd->dup_block; | |
352 | ||
353 | /* We do not create any outgoing edges for the template. We will | |
354 | take care of that in a later traversal. That way we do not | |
355 | create edges that are going to just be deleted. */ | |
356 | } | |
357 | else | |
358 | { | |
359 | create_block_for_threading (local_info->template_block, rd); | |
360 | ||
361 | /* Go ahead and wire up outgoing edges and update PHIs for the duplicate | |
362 | block. */ | |
42b013bc | 363 | create_edge_and_update_destination_phis (rd, rd->dup_block); |
778182c1 | 364 | } |
365 | ||
366 | /* Keep walking the hash table. */ | |
367 | return 1; | |
368 | } | |
369 | ||
370 | /* We did not create any outgoing edges for the template block during | |
371 | block creation. This hash table traversal callback creates the | |
372 | outgoing edge for the template block. */ | |
373 | ||
374 | static int | |
375 | fixup_template_block (void **slot, void *data) | |
376 | { | |
377 | struct redirection_data *rd = (struct redirection_data *) *slot; | |
378 | struct local_info *local_info = (struct local_info *)data; | |
379 | ||
380 | /* If this is the template block, then create its outgoing edges | |
381 | and halt the hash table traversal. */ | |
382 | if (rd->dup_block && rd->dup_block == local_info->template_block) | |
383 | { | |
42b013bc | 384 | create_edge_and_update_destination_phis (rd, rd->dup_block); |
778182c1 | 385 | return 0; |
386 | } | |
387 | ||
388 | return 1; | |
389 | } | |
390 | ||
391 | /* Hash table traversal callback to redirect each incoming edge | |
392 | associated with this hash table element to its new destination. */ | |
393 | ||
394 | static int | |
395 | redirect_edges (void **slot, void *data) | |
396 | { | |
397 | struct redirection_data *rd = (struct redirection_data *) *slot; | |
398 | struct local_info *local_info = (struct local_info *)data; | |
399 | struct el *next, *el; | |
400 | ||
401 | /* Walk over all the incoming edges associated associated with this | |
402 | hash table entry. */ | |
403 | for (el = rd->incoming_edges; el; el = next) | |
404 | { | |
405 | edge e = el->e; | |
406 | ||
407 | /* Go ahead and free this element from the list. Doing this now | |
408 | avoids the need for another list walk when we destroy the hash | |
409 | table. */ | |
410 | next = el->next; | |
411 | free (el); | |
412 | ||
413 | /* Go ahead and clear E->aux. It's not needed anymore and failure | |
414 | to clear it will cause all kinds of unpleasant problems later. */ | |
415 | e->aux = NULL; | |
416 | ||
5236b8bb | 417 | thread_stats.num_threaded_edges++; |
418 | ||
778182c1 | 419 | if (rd->dup_block) |
420 | { | |
421 | edge e2; | |
422 | ||
423 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
424 | fprintf (dump_file, " Threaded jump %d --> %d to %d\n", | |
425 | e->src->index, e->dest->index, rd->dup_block->index); | |
426 | ||
3ec32924 | 427 | rd->dup_block->count += e->count; |
428 | rd->dup_block->frequency += EDGE_FREQUENCY (e); | |
429 | EDGE_SUCC (rd->dup_block, 0)->count += e->count; | |
778182c1 | 430 | /* Redirect the incoming edge to the appropriate duplicate |
431 | block. */ | |
432 | e2 = redirect_edge_and_branch (e, rd->dup_block); | |
7e0311ae | 433 | gcc_assert (e == e2); |
778182c1 | 434 | flush_pending_stmts (e2); |
778182c1 | 435 | } |
436 | else | |
437 | { | |
438 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
439 | fprintf (dump_file, " Threaded jump %d --> %d to %d\n", | |
440 | e->src->index, e->dest->index, local_info->bb->index); | |
441 | ||
442 | /* We are using BB as the duplicate. Remove the unnecessary | |
443 | outgoing edges and statements from BB. */ | |
444 | remove_ctrl_stmt_and_useless_edges (local_info->bb, | |
445 | rd->outgoing_edge->dest); | |
446 | ||
42b013bc | 447 | /* If we are threading beyond the immediate successors of |
448 | the duplicate, then BB will have no edges, create one. */ | |
449 | if (EDGE_COUNT (local_info->bb->succs) == 0) | |
450 | create_edge_and_update_destination_phis (rd, local_info->bb); | |
451 | ||
8c09e55e | 452 | /* Fixup the flags on the single remaining edge. */ |
ea091dfd | 453 | single_succ_edge (local_info->bb)->flags |
388d1fc1 | 454 | &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); |
ea091dfd | 455 | single_succ_edge (local_info->bb)->flags |= EDGE_FALLTHRU; |
8c09e55e | 456 | |
457 | /* And adjust count and frequency on BB. */ | |
458 | local_info->bb->count = e->count; | |
459 | local_info->bb->frequency = EDGE_FREQUENCY (e); | |
778182c1 | 460 | } |
461 | } | |
388d1fc1 | 462 | |
463 | /* Indicate that we actually threaded one or more jumps. */ | |
464 | if (rd->incoming_edges) | |
465 | local_info->jumps_threaded = true; | |
466 | ||
778182c1 | 467 | return 1; |
468 | } | |
469 | ||
aed95130 | 470 | /* Return true if this block has no executable statements other than |
471 | a simple ctrl flow instruction. When the number of outgoing edges | |
472 | is one, this is equivalent to a "forwarder" block. */ | |
473 | ||
474 | static bool | |
47aaf6e6 | 475 | redirection_block_p (basic_block bb) |
aed95130 | 476 | { |
75a70cf9 | 477 | gimple_stmt_iterator gsi; |
aed95130 | 478 | |
479 | /* Advance to the first executable statement. */ | |
75a70cf9 | 480 | gsi = gsi_start_bb (bb); |
481 | while (!gsi_end_p (gsi) | |
482 | && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL | |
9845d120 | 483 | || is_gimple_debug (gsi_stmt (gsi)) |
75a70cf9 | 484 | || gimple_nop_p (gsi_stmt (gsi)))) |
485 | gsi_next (&gsi); | |
48e1416a | 486 | |
aed95130 | 487 | /* Check if this is an empty block. */ |
75a70cf9 | 488 | if (gsi_end_p (gsi)) |
aed95130 | 489 | return true; |
490 | ||
491 | /* Test that we've reached the terminating control statement. */ | |
75a70cf9 | 492 | return gsi_stmt (gsi) |
493 | && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND | |
494 | || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO | |
495 | || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH); | |
aed95130 | 496 | } |
497 | ||
a8046f60 | 498 | /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB |
499 | is reached via one or more specific incoming edges, we know which | |
500 | outgoing edge from BB will be traversed. | |
501 | ||
778182c1 | 502 | We want to redirect those incoming edges to the target of the |
a8046f60 | 503 | appropriate outgoing edge. Doing so avoids a conditional branch |
504 | and may expose new optimization opportunities. Note that we have | |
505 | to update dominator tree and SSA graph after such changes. | |
506 | ||
597ff315 | 507 | The key to keeping the SSA graph update manageable is to duplicate |
91275768 | 508 | the side effects occurring in BB so that those side effects still |
a8046f60 | 509 | occur on the paths which bypass BB after redirecting edges. |
510 | ||
511 | We accomplish this by creating duplicates of BB and arranging for | |
512 | the duplicates to unconditionally pass control to one specific | |
513 | successor of BB. We then revector the incoming edges into BB to | |
514 | the appropriate duplicate of BB. | |
515 | ||
7e0311ae | 516 | If NOLOOP_ONLY is true, we only perform the threading as long as it |
517 | does not affect the structure of the loops in a nontrivial way. */ | |
a8046f60 | 518 | |
388d1fc1 | 519 | static bool |
7e0311ae | 520 | thread_block (basic_block bb, bool noloop_only) |
a8046f60 | 521 | { |
522 | /* E is an incoming edge into BB that we may or may not want to | |
523 | redirect to a duplicate of BB. */ | |
7e0311ae | 524 | edge e, e2; |
cd665a06 | 525 | edge_iterator ei; |
778182c1 | 526 | struct local_info local_info; |
7e0311ae | 527 | struct loop *loop = bb->loop_father; |
388d1fc1 | 528 | |
a8046f60 | 529 | /* ALL indicates whether or not all incoming edges into BB should |
530 | be threaded to a duplicate of BB. */ | |
531 | bool all = true; | |
532 | ||
778182c1 | 533 | /* To avoid scanning a linear array for the element we need we instead |
c5d4a10b | 534 | use a hash table. For normal code there should be no noticeable |
778182c1 | 535 | difference. However, if we have a block with a large number of |
536 | incoming and outgoing edges such linear searches can get expensive. */ | |
537 | redirection_data = htab_create (EDGE_COUNT (bb->succs), | |
538 | redirection_data_hash, | |
539 | redirection_data_eq, | |
540 | free); | |
541 | ||
7e0311ae | 542 | /* If we thread the latch of the loop to its exit, the loop ceases to |
543 | exist. Make sure we do not restrict ourselves in order to preserve | |
544 | this loop. */ | |
7a3bf727 | 545 | if (loop->header == bb) |
7e0311ae | 546 | { |
547 | e = loop_latch_edge (loop); | |
f0d6e81c | 548 | e2 = (edge) e->aux; |
388d1fc1 | 549 | |
7e0311ae | 550 | if (e2 && loop_exit_edge_p (loop, e2)) |
551 | { | |
552 | loop->header = NULL; | |
553 | loop->latch = NULL; | |
554 | } | |
555 | } | |
388d1fc1 | 556 | |
778182c1 | 557 | /* Record each unique threaded destination into a hash table for |
558 | efficient lookups. */ | |
cd665a06 | 559 | FOR_EACH_EDGE (e, ei, bb->preds) |
a8046f60 | 560 | { |
f0d6e81c | 561 | e2 = (edge) e->aux; |
7e0311ae | 562 | |
563 | if (!e2 | |
564 | /* If NOLOOP_ONLY is true, we only allow threading through the | |
565 | header of a loop to exit edges. */ | |
566 | || (noloop_only | |
7e0311ae | 567 | && bb == bb->loop_father->header |
568 | && !loop_exit_edge_p (bb->loop_father, e2))) | |
a8046f60 | 569 | { |
570 | all = false; | |
7e0311ae | 571 | continue; |
a8046f60 | 572 | } |
778182c1 | 573 | |
42b013bc | 574 | if (e->dest == e2->src) |
575 | update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), | |
576 | e->count, (edge) e->aux); | |
7e0311ae | 577 | |
578 | /* Insert the outgoing edge into the hash table if it is not | |
579 | already in the hash table. */ | |
580 | lookup_redirection_data (e2, e, INSERT); | |
a8046f60 | 581 | } |
582 | ||
778182c1 | 583 | /* If we are going to thread all incoming edges to an outgoing edge, then |
584 | BB will become unreachable. Rather than just throwing it away, use | |
585 | it for one of the duplicates. Mark the first incoming edge with the | |
586 | DO_NOT_DUPLICATE attribute. */ | |
587 | if (all) | |
588 | { | |
f0d6e81c | 589 | edge e = (edge) EDGE_PRED (bb, 0)->aux; |
6d7413d8 | 590 | lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true; |
778182c1 | 591 | } |
592 | ||
3f9439d7 | 593 | /* We do not update dominance info. */ |
594 | free_dominance_info (CDI_DOMINATORS); | |
595 | ||
778182c1 | 596 | /* Now create duplicates of BB. |
f582bb6c | 597 | |
598 | Note that for a block with a high outgoing degree we can waste | |
599 | a lot of time and memory creating and destroying useless edges. | |
600 | ||
601 | So we first duplicate BB and remove the control structure at the | |
602 | tail of the duplicate as well as all outgoing edges from the | |
603 | duplicate. We then use that duplicate block as a template for | |
604 | the rest of the duplicates. */ | |
778182c1 | 605 | local_info.template_block = NULL; |
606 | local_info.bb = bb; | |
388d1fc1 | 607 | local_info.jumps_threaded = false; |
778182c1 | 608 | htab_traverse (redirection_data, create_duplicates, &local_info); |
f582bb6c | 609 | |
778182c1 | 610 | /* The template does not have an outgoing edge. Create that outgoing |
611 | edge and update PHI nodes as the edge's target as necessary. | |
f582bb6c | 612 | |
778182c1 | 613 | We do this after creating all the duplicates to avoid creating |
614 | unnecessary edges. */ | |
615 | htab_traverse (redirection_data, fixup_template_block, &local_info); | |
f582bb6c | 616 | |
778182c1 | 617 | /* The hash table traversals above created the duplicate blocks (and the |
618 | statements within the duplicate blocks). This loop creates PHI nodes for | |
619 | the duplicated blocks and redirects the incoming edges into BB to reach | |
620 | the duplicates of BB. */ | |
621 | htab_traverse (redirection_data, redirect_edges, &local_info); | |
a8046f60 | 622 | |
a3d0fd80 | 623 | /* Done with this block. Clear REDIRECTION_DATA. */ |
778182c1 | 624 | htab_delete (redirection_data); |
625 | redirection_data = NULL; | |
388d1fc1 | 626 | |
627 | /* Indicate to our caller whether or not any jumps were threaded. */ | |
628 | return local_info.jumps_threaded; | |
a8046f60 | 629 | } |
630 | ||
7e0311ae | 631 | /* Threads edge E through E->dest to the edge E->aux. Returns the copy |
632 | of E->dest created during threading, or E->dest if it was not necessary | |
633 | to copy it (E is its single predecessor). */ | |
634 | ||
635 | static basic_block | |
636 | thread_single_edge (edge e) | |
637 | { | |
638 | basic_block bb = e->dest; | |
f0d6e81c | 639 | edge eto = (edge) e->aux; |
7e0311ae | 640 | struct redirection_data rd; |
7e0311ae | 641 | |
642 | e->aux = NULL; | |
643 | ||
644 | thread_stats.num_threaded_edges++; | |
645 | ||
646 | if (single_pred_p (bb)) | |
647 | { | |
648 | /* If BB has just a single predecessor, we should only remove the | |
649 | control statements at its end, and successors except for ETO. */ | |
650 | remove_ctrl_stmt_and_useless_edges (bb, eto->dest); | |
ad330780 | 651 | |
652 | /* And fixup the flags on the single remaining edge. */ | |
653 | eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); | |
654 | eto->flags |= EDGE_FALLTHRU; | |
655 | ||
7e0311ae | 656 | return bb; |
657 | } | |
658 | ||
659 | /* Otherwise, we need to create a copy. */ | |
42b013bc | 660 | if (e->dest == eto->src) |
661 | update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto); | |
7e0311ae | 662 | |
7e0311ae | 663 | rd.outgoing_edge = eto; |
664 | ||
665 | create_block_for_threading (bb, &rd); | |
42b013bc | 666 | create_edge_and_update_destination_phis (&rd, rd.dup_block); |
7e0311ae | 667 | |
668 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
669 | fprintf (dump_file, " Threaded jump %d --> %d to %d\n", | |
670 | e->src->index, e->dest->index, rd.dup_block->index); | |
671 | ||
672 | rd.dup_block->count = e->count; | |
673 | rd.dup_block->frequency = EDGE_FREQUENCY (e); | |
674 | single_succ_edge (rd.dup_block)->count = e->count; | |
675 | redirect_edge_and_branch (e, rd.dup_block); | |
676 | flush_pending_stmts (e); | |
677 | ||
678 | return rd.dup_block; | |
679 | } | |
680 | ||
681 | /* Callback for dfs_enumerate_from. Returns true if BB is different | |
682 | from STOP and DBDS_CE_STOP. */ | |
683 | ||
684 | static basic_block dbds_ce_stop; | |
685 | static bool | |
7ecb5bb2 | 686 | dbds_continue_enumeration_p (const_basic_block bb, const void *stop) |
7e0311ae | 687 | { |
7ecb5bb2 | 688 | return (bb != (const_basic_block) stop |
7e0311ae | 689 | && bb != dbds_ce_stop); |
690 | } | |
691 | ||
692 | /* Evaluates the dominance relationship of latch of the LOOP and BB, and | |
693 | returns the state. */ | |
694 | ||
695 | enum bb_dom_status | |
696 | { | |
697 | /* BB does not dominate latch of the LOOP. */ | |
698 | DOMST_NONDOMINATING, | |
699 | /* The LOOP is broken (there is no path from the header to its latch. */ | |
700 | DOMST_LOOP_BROKEN, | |
701 | /* BB dominates the latch of the LOOP. */ | |
702 | DOMST_DOMINATING | |
703 | }; | |
704 | ||
705 | static enum bb_dom_status | |
706 | determine_bb_domination_status (struct loop *loop, basic_block bb) | |
707 | { | |
708 | basic_block *bblocks; | |
709 | unsigned nblocks, i; | |
710 | bool bb_reachable = false; | |
711 | edge_iterator ei; | |
712 | edge e; | |
713 | ||
714 | #ifdef ENABLE_CHECKING | |
42b013bc | 715 | /* This function assumes BB is a successor of LOOP->header. |
716 | If that is not the case return DOMST_NONDOMINATING which | |
717 | is always safe. */ | |
7e0311ae | 718 | { |
719 | bool ok = false; | |
720 | ||
721 | FOR_EACH_EDGE (e, ei, bb->preds) | |
722 | { | |
723 | if (e->src == loop->header) | |
724 | { | |
725 | ok = true; | |
726 | break; | |
727 | } | |
728 | } | |
729 | ||
42b013bc | 730 | if (!ok) |
731 | return DOMST_NONDOMINATING; | |
7e0311ae | 732 | } |
733 | #endif | |
734 | ||
735 | if (bb == loop->latch) | |
736 | return DOMST_DOMINATING; | |
737 | ||
738 | /* Check that BB dominates LOOP->latch, and that it is back-reachable | |
739 | from it. */ | |
740 | ||
741 | bblocks = XCNEWVEC (basic_block, loop->num_nodes); | |
742 | dbds_ce_stop = loop->header; | |
743 | nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p, | |
744 | bblocks, loop->num_nodes, bb); | |
745 | for (i = 0; i < nblocks; i++) | |
746 | FOR_EACH_EDGE (e, ei, bblocks[i]->preds) | |
747 | { | |
748 | if (e->src == loop->header) | |
749 | { | |
750 | free (bblocks); | |
751 | return DOMST_NONDOMINATING; | |
752 | } | |
753 | if (e->src == bb) | |
754 | bb_reachable = true; | |
755 | } | |
756 | ||
757 | free (bblocks); | |
758 | return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN); | |
759 | } | |
760 | ||
761 | /* Thread jumps through the header of LOOP. Returns true if cfg changes. | |
762 | If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges | |
763 | to the inside of the loop. */ | |
764 | ||
765 | static bool | |
766 | thread_through_loop_header (struct loop *loop, bool may_peel_loop_headers) | |
767 | { | |
768 | basic_block header = loop->header; | |
769 | edge e, tgt_edge, latch = loop_latch_edge (loop); | |
770 | edge_iterator ei; | |
771 | basic_block tgt_bb, atgt_bb; | |
772 | enum bb_dom_status domst; | |
773 | ||
774 | /* We have already threaded through headers to exits, so all the threading | |
775 | requests now are to the inside of the loop. We need to avoid creating | |
776 | irreducible regions (i.e., loops with more than one entry block), and | |
777 | also loop with several latch edges, or new subloops of the loop (although | |
778 | there are cases where it might be appropriate, it is difficult to decide, | |
779 | and doing it wrongly may confuse other optimizers). | |
780 | ||
781 | We could handle more general cases here. However, the intention is to | |
782 | preserve some information about the loop, which is impossible if its | |
783 | structure changes significantly, in a way that is not well understood. | |
784 | Thus we only handle few important special cases, in which also updating | |
785 | of the loop-carried information should be feasible: | |
786 | ||
787 | 1) Propagation of latch edge to a block that dominates the latch block | |
788 | of a loop. This aims to handle the following idiom: | |
789 | ||
790 | first = 1; | |
791 | while (1) | |
792 | { | |
793 | if (first) | |
794 | initialize; | |
795 | first = 0; | |
796 | body; | |
797 | } | |
798 | ||
799 | After threading the latch edge, this becomes | |
800 | ||
801 | first = 1; | |
802 | if (first) | |
803 | initialize; | |
804 | while (1) | |
805 | { | |
806 | first = 0; | |
807 | body; | |
808 | } | |
809 | ||
810 | The original header of the loop is moved out of it, and we may thread | |
811 | the remaining edges through it without further constraints. | |
812 | ||
813 | 2) All entry edges are propagated to a single basic block that dominates | |
814 | the latch block of the loop. This aims to handle the following idiom | |
815 | (normally created for "for" loops): | |
816 | ||
817 | i = 0; | |
818 | while (1) | |
819 | { | |
820 | if (i >= 100) | |
821 | break; | |
822 | body; | |
823 | i++; | |
824 | } | |
825 | ||
826 | This becomes | |
827 | ||
828 | i = 0; | |
829 | while (1) | |
830 | { | |
831 | body; | |
832 | i++; | |
833 | if (i >= 100) | |
834 | break; | |
835 | } | |
836 | */ | |
837 | ||
838 | /* Threading through the header won't improve the code if the header has just | |
839 | one successor. */ | |
840 | if (single_succ_p (header)) | |
841 | goto fail; | |
842 | ||
843 | if (latch->aux) | |
844 | { | |
f0d6e81c | 845 | tgt_edge = (edge) latch->aux; |
7e0311ae | 846 | tgt_bb = tgt_edge->dest; |
847 | } | |
848 | else if (!may_peel_loop_headers | |
849 | && !redirection_block_p (loop->header)) | |
850 | goto fail; | |
851 | else | |
852 | { | |
853 | tgt_bb = NULL; | |
854 | tgt_edge = NULL; | |
855 | FOR_EACH_EDGE (e, ei, header->preds) | |
856 | { | |
857 | if (!e->aux) | |
858 | { | |
859 | if (e == latch) | |
860 | continue; | |
861 | ||
862 | /* If latch is not threaded, and there is a header | |
863 | edge that is not threaded, we would create loop | |
864 | with multiple entries. */ | |
865 | goto fail; | |
866 | } | |
867 | ||
f0d6e81c | 868 | tgt_edge = (edge) e->aux; |
7e0311ae | 869 | atgt_bb = tgt_edge->dest; |
870 | if (!tgt_bb) | |
871 | tgt_bb = atgt_bb; | |
872 | /* Two targets of threading would make us create loop | |
873 | with multiple entries. */ | |
874 | else if (tgt_bb != atgt_bb) | |
875 | goto fail; | |
876 | } | |
877 | ||
878 | if (!tgt_bb) | |
879 | { | |
880 | /* There are no threading requests. */ | |
881 | return false; | |
882 | } | |
883 | ||
884 | /* Redirecting to empty loop latch is useless. */ | |
885 | if (tgt_bb == loop->latch | |
886 | && empty_block_p (loop->latch)) | |
887 | goto fail; | |
888 | } | |
889 | ||
890 | /* The target block must dominate the loop latch, otherwise we would be | |
891 | creating a subloop. */ | |
892 | domst = determine_bb_domination_status (loop, tgt_bb); | |
893 | if (domst == DOMST_NONDOMINATING) | |
894 | goto fail; | |
895 | if (domst == DOMST_LOOP_BROKEN) | |
896 | { | |
897 | /* If the loop ceased to exist, mark it as such, and thread through its | |
898 | original header. */ | |
899 | loop->header = NULL; | |
900 | loop->latch = NULL; | |
901 | return thread_block (header, false); | |
902 | } | |
903 | ||
904 | if (tgt_bb->loop_father->header == tgt_bb) | |
905 | { | |
906 | /* If the target of the threading is a header of a subloop, we need | |
907 | to create a preheader for it, so that the headers of the two loops | |
908 | do not merge. */ | |
909 | if (EDGE_COUNT (tgt_bb->preds) > 2) | |
910 | { | |
911 | tgt_bb = create_preheader (tgt_bb->loop_father, 0); | |
912 | gcc_assert (tgt_bb != NULL); | |
913 | } | |
914 | else | |
915 | tgt_bb = split_edge (tgt_edge); | |
916 | } | |
48e1416a | 917 | |
7e0311ae | 918 | if (latch->aux) |
919 | { | |
920 | /* First handle the case latch edge is redirected. */ | |
921 | loop->latch = thread_single_edge (latch); | |
922 | gcc_assert (single_succ (loop->latch) == tgt_bb); | |
923 | loop->header = tgt_bb; | |
924 | ||
925 | /* Thread the remaining edges through the former header. */ | |
926 | thread_block (header, false); | |
927 | } | |
928 | else | |
929 | { | |
930 | basic_block new_preheader; | |
931 | ||
932 | /* Now consider the case entry edges are redirected to the new entry | |
933 | block. Remember one entry edge, so that we can find the new | |
934 | preheader (its destination after threading). */ | |
935 | FOR_EACH_EDGE (e, ei, header->preds) | |
936 | { | |
937 | if (e->aux) | |
938 | break; | |
939 | } | |
940 | ||
941 | /* The duplicate of the header is the new preheader of the loop. Ensure | |
942 | that it is placed correctly in the loop hierarchy. */ | |
96c90e5e | 943 | set_loop_copy (loop, loop_outer (loop)); |
7e0311ae | 944 | |
945 | thread_block (header, false); | |
96c90e5e | 946 | set_loop_copy (loop, NULL); |
7e0311ae | 947 | new_preheader = e->dest; |
948 | ||
949 | /* Create the new latch block. This is always necessary, as the latch | |
950 | must have only a single successor, but the original header had at | |
951 | least two successors. */ | |
952 | loop->latch = NULL; | |
953 | mfb_kj_edge = single_succ_edge (new_preheader); | |
954 | loop->header = mfb_kj_edge->dest; | |
955 | latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL); | |
956 | loop->header = latch->dest; | |
957 | loop->latch = latch->src; | |
958 | } | |
48e1416a | 959 | |
7e0311ae | 960 | return true; |
961 | ||
962 | fail: | |
963 | /* We failed to thread anything. Cancel the requests. */ | |
964 | FOR_EACH_EDGE (e, ei, header->preds) | |
965 | { | |
966 | e->aux = NULL; | |
967 | } | |
968 | return false; | |
969 | } | |
970 | ||
3cebc9d2 | 971 | /* Walk through the registered jump threads and convert them into a |
334ec2d8 | 972 | form convenient for this pass. |
3cebc9d2 | 973 | |
974 | Any block which has incoming edges threaded to outgoing edges | |
975 | will have its entry in THREADED_BLOCK set. | |
a8046f60 | 976 | |
3cebc9d2 | 977 | Any threaded edge will have its new outgoing edge stored in the |
978 | original edge's AUX field. | |
a8046f60 | 979 | |
3cebc9d2 | 980 | This form avoids the need to walk all the edges in the CFG to |
981 | discover blocks which need processing and avoids unnecessary | |
982 | hash table lookups to map from threaded edge to new target. */ | |
a8046f60 | 983 | |
3cebc9d2 | 984 | static void |
985 | mark_threaded_blocks (bitmap threaded_blocks) | |
986 | { | |
987 | unsigned int i; | |
7e0311ae | 988 | bitmap_iterator bi; |
989 | bitmap tmp = BITMAP_ALLOC (NULL); | |
990 | basic_block bb; | |
991 | edge e; | |
992 | edge_iterator ei; | |
3cebc9d2 | 993 | |
994 | for (i = 0; i < VEC_length (edge, threaded_edges); i += 2) | |
995 | { | |
996 | edge e = VEC_index (edge, threaded_edges, i); | |
997 | edge e2 = VEC_index (edge, threaded_edges, i + 1); | |
998 | ||
999 | e->aux = e2; | |
7e0311ae | 1000 | bitmap_set_bit (tmp, e->dest->index); |
1001 | } | |
1002 | ||
1003 | /* If optimizing for size, only thread through block if we don't have | |
1004 | to duplicate it or it's an otherwise empty redirection block. */ | |
0bfd8d5c | 1005 | if (optimize_function_for_size_p (cfun)) |
7e0311ae | 1006 | { |
1007 | EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi) | |
1008 | { | |
1009 | bb = BASIC_BLOCK (i); | |
1010 | if (EDGE_COUNT (bb->preds) > 1 | |
1011 | && !redirection_block_p (bb)) | |
1012 | { | |
1013 | FOR_EACH_EDGE (e, ei, bb->preds) | |
1014 | e->aux = NULL; | |
1015 | } | |
1016 | else | |
1017 | bitmap_set_bit (threaded_blocks, i); | |
1018 | } | |
3cebc9d2 | 1019 | } |
7e0311ae | 1020 | else |
1021 | bitmap_copy (threaded_blocks, tmp); | |
1022 | ||
1023 | BITMAP_FREE(tmp); | |
3cebc9d2 | 1024 | } |
1025 | ||
1026 | ||
1027 | /* Walk through all blocks and thread incoming edges to the appropriate | |
1028 | outgoing edge for each edge pair recorded in THREADED_EDGES. | |
a8046f60 | 1029 | |
1030 | It is the caller's responsibility to fix the dominance information | |
1031 | and rewrite duplicated SSA_NAMEs back into SSA form. | |
1032 | ||
7e0311ae | 1033 | If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through |
1034 | loop headers if it does not simplify the loop. | |
1035 | ||
dac49aa5 | 1036 | Returns true if one or more edges were threaded, false otherwise. */ |
a8046f60 | 1037 | |
1038 | bool | |
7e0311ae | 1039 | thread_through_all_blocks (bool may_peel_loop_headers) |
a8046f60 | 1040 | { |
a8046f60 | 1041 | bool retval = false; |
7ea47fbd | 1042 | unsigned int i; |
1043 | bitmap_iterator bi; | |
3cebc9d2 | 1044 | bitmap threaded_blocks; |
7e0311ae | 1045 | struct loop *loop; |
1046 | loop_iterator li; | |
3cebc9d2 | 1047 | |
7a3bf727 | 1048 | /* We must know about loops in order to preserve them. */ |
1049 | gcc_assert (current_loops != NULL); | |
1050 | ||
3cebc9d2 | 1051 | if (threaded_edges == NULL) |
1052 | return false; | |
a8046f60 | 1053 | |
3cebc9d2 | 1054 | threaded_blocks = BITMAP_ALLOC (NULL); |
5236b8bb | 1055 | memset (&thread_stats, 0, sizeof (thread_stats)); |
388d1fc1 | 1056 | |
3cebc9d2 | 1057 | mark_threaded_blocks (threaded_blocks); |
1058 | ||
96c90e5e | 1059 | initialize_original_copy_tables (); |
7e0311ae | 1060 | |
1061 | /* First perform the threading requests that do not affect | |
1062 | loop structure. */ | |
7ea47fbd | 1063 | EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi) |
a8046f60 | 1064 | { |
7ea47fbd | 1065 | basic_block bb = BASIC_BLOCK (i); |
1066 | ||
1067 | if (EDGE_COUNT (bb->preds) > 0) | |
7e0311ae | 1068 | retval |= thread_block (bb, true); |
1069 | } | |
1070 | ||
1071 | /* Then perform the threading through loop headers. We start with the | |
1072 | innermost loop, so that the changes in cfg we perform won't affect | |
1073 | further threading. */ | |
7a3bf727 | 1074 | FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) |
7e0311ae | 1075 | { |
7a3bf727 | 1076 | if (!loop->header |
1077 | || !bitmap_bit_p (threaded_blocks, loop->header->index)) | |
1078 | continue; | |
7e0311ae | 1079 | |
7a3bf727 | 1080 | retval |= thread_through_loop_header (loop, may_peel_loop_headers); |
a8046f60 | 1081 | } |
388d1fc1 | 1082 | |
581f8050 | 1083 | statistics_counter_event (cfun, "Jumps threaded", |
1084 | thread_stats.num_threaded_edges); | |
5236b8bb | 1085 | |
96c90e5e | 1086 | free_original_copy_tables (); |
1087 | ||
3cebc9d2 | 1088 | BITMAP_FREE (threaded_blocks); |
1089 | threaded_blocks = NULL; | |
1090 | VEC_free (edge, heap, threaded_edges); | |
1091 | threaded_edges = NULL; | |
7e0311ae | 1092 | |
eb2a640e | 1093 | if (retval) |
f24ec26f | 1094 | loops_state_set (LOOPS_NEED_FIXUP); |
eb2a640e | 1095 | |
a8046f60 | 1096 | return retval; |
1097 | } | |
3cebc9d2 | 1098 | |
1099 | /* Register a jump threading opportunity. We queue up all the jump | |
1100 | threading opportunities discovered by a pass and update the CFG | |
1101 | and SSA form all at once. | |
1102 | ||
f0b5f617 | 1103 | E is the edge we can thread, E2 is the new target edge, i.e., we |
3cebc9d2 | 1104 | are effectively recording that E->dest can be changed to E2->dest |
1105 | after fixing the SSA graph. */ | |
1106 | ||
1107 | void | |
1108 | register_jump_thread (edge e, edge e2) | |
1109 | { | |
1110 | if (threaded_edges == NULL) | |
1111 | threaded_edges = VEC_alloc (edge, heap, 10); | |
1112 | ||
42b013bc | 1113 | if (dump_file && (dump_flags & TDF_DETAILS) |
1114 | && e->dest != e2->src) | |
1115 | fprintf (dump_file, | |
1116 | " Registering jump thread around one or more intermediate blocks\n"); | |
1117 | ||
3cebc9d2 | 1118 | VEC_safe_push (edge, heap, threaded_edges, e); |
1119 | VEC_safe_push (edge, heap, threaded_edges, e2); | |
1120 | } |