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