]>
Commit | Line | Data |
---|---|---|
402209ff | 1 | /* Natural loop discovery code for GNU compiler. |
d329e058 | 2 | Copyright (C) 2000, 2001, 2003 Free Software Foundation, Inc. |
402209ff JH |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
8 | Software Foundation; either version 2, or (at your option) any later | |
9 | version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
402209ff JH |
25 | #include "rtl.h" |
26 | #include "hard-reg-set.h" | |
27 | #include "basic-block.h" | |
2ecfd709 | 28 | #include "toplev.h" |
3d436d2a ZD |
29 | #include "cfgloop.h" |
30 | #include "flags.h" | |
2ecfd709 ZD |
31 | |
32 | /* Ratio of frequencies of edges so that one of more latch edges is | |
33 | considered to belong to inner loop with same header. */ | |
34 | #define HEAVY_EDGE_RATIO 8 | |
402209ff | 35 | |
d329e058 AJ |
36 | static void flow_loops_cfg_dump (const struct loops *, FILE *); |
37 | static void flow_loop_entry_edges_find (struct loop *); | |
38 | static void flow_loop_exit_edges_find (struct loop *); | |
39 | static int flow_loop_nodes_find (basic_block, struct loop *); | |
40 | static void flow_loop_pre_header_scan (struct loop *); | |
41 | static basic_block flow_loop_pre_header_find (basic_block, dominance_info); | |
42 | static int flow_loop_level_compute (struct loop *); | |
43 | static int flow_loops_level_compute (struct loops *); | |
44 | static void establish_preds (struct loop *); | |
45 | static basic_block make_forwarder_block (basic_block, int, int, edge, int); | |
46 | static void canonicalize_loop_headers (void); | |
47 | static bool glb_enum_p (basic_block, void *); | |
48 | static void redirect_edge_with_latch_update (edge, basic_block); | |
402209ff JH |
49 | \f |
50 | /* Dump loop related CFG information. */ | |
51 | ||
52 | static void | |
d329e058 | 53 | flow_loops_cfg_dump (const struct loops *loops, FILE *file) |
402209ff JH |
54 | { |
55 | int i; | |
e0082a72 | 56 | basic_block bb; |
402209ff JH |
57 | |
58 | if (! loops->num || ! file || ! loops->cfg.dom) | |
59 | return; | |
60 | ||
e0082a72 | 61 | FOR_EACH_BB (bb) |
402209ff JH |
62 | { |
63 | edge succ; | |
64 | ||
e0082a72 ZD |
65 | fprintf (file, ";; %d succs { ", bb->index); |
66 | for (succ = bb->succ; succ; succ = succ->succ_next) | |
0b17ab2f | 67 | fprintf (file, "%d ", succ->dest->index); |
2ecfd709 | 68 | fprintf (file, "}\n"); |
402209ff JH |
69 | } |
70 | ||
71 | /* Dump the DFS node order. */ | |
72 | if (loops->cfg.dfs_order) | |
73 | { | |
74 | fputs (";; DFS order: ", file); | |
0b17ab2f | 75 | for (i = 0; i < n_basic_blocks; i++) |
402209ff | 76 | fprintf (file, "%d ", loops->cfg.dfs_order[i]); |
5f0d2358 | 77 | |
402209ff JH |
78 | fputs ("\n", file); |
79 | } | |
5f0d2358 | 80 | |
402209ff JH |
81 | /* Dump the reverse completion node order. */ |
82 | if (loops->cfg.rc_order) | |
83 | { | |
84 | fputs (";; RC order: ", file); | |
0b17ab2f | 85 | for (i = 0; i < n_basic_blocks; i++) |
402209ff | 86 | fprintf (file, "%d ", loops->cfg.rc_order[i]); |
5f0d2358 | 87 | |
402209ff JH |
88 | fputs ("\n", file); |
89 | } | |
90 | } | |
91 | ||
da7d8304 | 92 | /* Return nonzero if the nodes of LOOP are a subset of OUTER. */ |
402209ff | 93 | |
2ecfd709 | 94 | bool |
d329e058 | 95 | flow_loop_nested_p (const struct loop *outer, const struct loop *loop) |
402209ff | 96 | { |
2ecfd709 ZD |
97 | return loop->depth > outer->depth |
98 | && loop->pred[outer->depth] == outer; | |
402209ff JH |
99 | } |
100 | ||
101 | /* Dump the loop information specified by LOOP to the stream FILE | |
102 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
103 | ||
104 | void | |
d329e058 AJ |
105 | flow_loop_dump (const struct loop *loop, FILE *file, |
106 | void (*loop_dump_aux) (const struct loop *, FILE *, int), | |
107 | int verbose) | |
402209ff | 108 | { |
2ecfd709 | 109 | basic_block *bbs; |
3d436d2a | 110 | unsigned i; |
2ecfd709 | 111 | |
402209ff JH |
112 | if (! loop || ! loop->header) |
113 | return; | |
114 | ||
2ecfd709 ZD |
115 | fprintf (file, ";;\n;; Loop %d:%s\n", loop->num, |
116 | loop->invalid ? " invalid" : ""); | |
402209ff | 117 | |
2ecfd709 | 118 | fprintf (file, ";; header %d, latch %d, pre-header %d\n", |
0b17ab2f | 119 | loop->header->index, loop->latch->index, |
2ecfd709 | 120 | loop->pre_header ? loop->pre_header->index : -1); |
402209ff JH |
121 | fprintf (file, ";; depth %d, level %d, outer %ld\n", |
122 | loop->depth, loop->level, | |
123 | (long) (loop->outer ? loop->outer->num : -1)); | |
124 | ||
125 | if (loop->pre_header_edges) | |
126 | flow_edge_list_print (";; pre-header edges", loop->pre_header_edges, | |
127 | loop->num_pre_header_edges, file); | |
5f0d2358 | 128 | |
402209ff JH |
129 | flow_edge_list_print (";; entry edges", loop->entry_edges, |
130 | loop->num_entries, file); | |
2ecfd709 ZD |
131 | fprintf (file, ";; nodes:"); |
132 | bbs = get_loop_body (loop); | |
133 | for (i = 0; i < loop->num_nodes; i++) | |
134 | fprintf (file, " %d", bbs[i]->index); | |
135 | free (bbs); | |
136 | fprintf (file, "\n"); | |
402209ff JH |
137 | flow_edge_list_print (";; exit edges", loop->exit_edges, |
138 | loop->num_exits, file); | |
5f0d2358 | 139 | |
402209ff JH |
140 | if (loop_dump_aux) |
141 | loop_dump_aux (loop, file, verbose); | |
142 | } | |
143 | ||
144 | /* Dump the loop information specified by LOOPS to the stream FILE, | |
145 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
146 | ||
147 | void | |
d329e058 | 148 | flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) |
402209ff | 149 | { |
2ecfd709 | 150 | int i; |
402209ff JH |
151 | int num_loops; |
152 | ||
153 | num_loops = loops->num; | |
154 | if (! num_loops || ! file) | |
155 | return; | |
156 | ||
2ecfd709 ZD |
157 | fprintf (file, ";; %d loops found, %d levels\n", |
158 | num_loops, loops->levels); | |
159 | ||
402209ff JH |
160 | for (i = 0; i < num_loops; i++) |
161 | { | |
2ecfd709 | 162 | struct loop *loop = loops->parray[i]; |
402209ff | 163 | |
2ecfd709 ZD |
164 | if (!loop) |
165 | continue; | |
5f0d2358 | 166 | |
2ecfd709 | 167 | flow_loop_dump (loop, file, loop_dump_aux, verbose); |
402209ff JH |
168 | } |
169 | ||
170 | if (verbose) | |
171 | flow_loops_cfg_dump (loops, file); | |
172 | } | |
173 | ||
2ecfd709 | 174 | /* Free data allocated for LOOP. */ |
35b07080 | 175 | void |
d329e058 | 176 | flow_loop_free (struct loop *loop) |
2ecfd709 ZD |
177 | { |
178 | if (loop->pre_header_edges) | |
179 | free (loop->pre_header_edges); | |
180 | if (loop->entry_edges) | |
181 | free (loop->entry_edges); | |
182 | if (loop->exit_edges) | |
183 | free (loop->exit_edges); | |
184 | if (loop->pred) | |
185 | free (loop->pred); | |
186 | free (loop); | |
187 | } | |
188 | ||
402209ff JH |
189 | /* Free all the memory allocated for LOOPS. */ |
190 | ||
191 | void | |
d329e058 | 192 | flow_loops_free (struct loops *loops) |
402209ff | 193 | { |
2ecfd709 | 194 | if (loops->parray) |
402209ff | 195 | { |
3d436d2a | 196 | unsigned i; |
402209ff JH |
197 | |
198 | if (! loops->num) | |
199 | abort (); | |
200 | ||
201 | /* Free the loop descriptors. */ | |
202 | for (i = 0; i < loops->num; i++) | |
203 | { | |
2ecfd709 ZD |
204 | struct loop *loop = loops->parray[i]; |
205 | ||
206 | if (!loop) | |
207 | continue; | |
208 | ||
209 | flow_loop_free (loop); | |
402209ff | 210 | } |
5f0d2358 | 211 | |
2ecfd709 ZD |
212 | free (loops->parray); |
213 | loops->parray = NULL; | |
402209ff JH |
214 | |
215 | if (loops->cfg.dom) | |
355be0dc | 216 | free_dominance_info (loops->cfg.dom); |
5f0d2358 | 217 | |
402209ff JH |
218 | if (loops->cfg.dfs_order) |
219 | free (loops->cfg.dfs_order); | |
2ecfd709 ZD |
220 | if (loops->cfg.rc_order) |
221 | free (loops->cfg.rc_order); | |
402209ff | 222 | |
402209ff JH |
223 | } |
224 | } | |
225 | ||
2ecfd709 | 226 | /* Find the entry edges into the LOOP. */ |
402209ff | 227 | |
d329e058 AJ |
228 | static void |
229 | flow_loop_entry_edges_find (struct loop *loop) | |
402209ff JH |
230 | { |
231 | edge e; | |
232 | int num_entries; | |
233 | ||
402209ff | 234 | num_entries = 0; |
2ecfd709 | 235 | for (e = loop->header->pred; e; e = e->pred_next) |
402209ff | 236 | { |
2ecfd709 | 237 | if (flow_loop_outside_edge_p (loop, e)) |
402209ff JH |
238 | num_entries++; |
239 | } | |
240 | ||
241 | if (! num_entries) | |
242 | abort (); | |
243 | ||
2ecfd709 | 244 | loop->entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *)); |
402209ff JH |
245 | |
246 | num_entries = 0; | |
2ecfd709 | 247 | for (e = loop->header->pred; e; e = e->pred_next) |
402209ff | 248 | { |
2ecfd709 ZD |
249 | if (flow_loop_outside_edge_p (loop, e)) |
250 | loop->entry_edges[num_entries++] = e; | |
402209ff JH |
251 | } |
252 | ||
2ecfd709 | 253 | loop->num_entries = num_entries; |
402209ff JH |
254 | } |
255 | ||
2ecfd709 | 256 | /* Find the exit edges from the LOOP. */ |
402209ff | 257 | |
2ecfd709 | 258 | static void |
d329e058 | 259 | flow_loop_exit_edges_find (struct loop *loop) |
402209ff JH |
260 | { |
261 | edge e; | |
2ecfd709 | 262 | basic_block node, *bbs; |
3d436d2a | 263 | unsigned num_exits, i; |
402209ff | 264 | |
2ecfd709 ZD |
265 | loop->exit_edges = NULL; |
266 | loop->num_exits = 0; | |
402209ff JH |
267 | |
268 | /* Check all nodes within the loop to see if there are any | |
269 | successors not in the loop. Note that a node may have multiple | |
2ecfd709 | 270 | exiting edges. */ |
402209ff | 271 | num_exits = 0; |
2ecfd709 ZD |
272 | bbs = get_loop_body (loop); |
273 | for (i = 0; i < loop->num_nodes; i++) | |
274 | { | |
275 | node = bbs[i]; | |
276 | for (e = node->succ; e; e = e->succ_next) | |
277 | { | |
278 | basic_block dest = e->dest; | |
402209ff | 279 | |
2ecfd709 | 280 | if (!flow_bb_inside_loop_p (loop, dest)) |
402209ff | 281 | num_exits++; |
2ecfd709 ZD |
282 | } |
283 | } | |
402209ff JH |
284 | |
285 | if (! num_exits) | |
2ecfd709 ZD |
286 | { |
287 | free (bbs); | |
288 | return; | |
289 | } | |
402209ff | 290 | |
2ecfd709 | 291 | loop->exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *)); |
402209ff JH |
292 | |
293 | /* Store all exiting edges into an array. */ | |
294 | num_exits = 0; | |
2ecfd709 ZD |
295 | for (i = 0; i < loop->num_nodes; i++) |
296 | { | |
297 | node = bbs[i]; | |
298 | for (e = node->succ; e; e = e->succ_next) | |
299 | { | |
300 | basic_block dest = e->dest; | |
402209ff | 301 | |
2ecfd709 ZD |
302 | if (!flow_bb_inside_loop_p (loop, dest)) |
303 | loop->exit_edges[num_exits++] = e; | |
402209ff | 304 | } |
2ecfd709 ZD |
305 | } |
306 | free (bbs); | |
307 | loop->num_exits = num_exits; | |
402209ff JH |
308 | } |
309 | ||
2ecfd709 ZD |
310 | /* Find the nodes contained within the LOOP with header HEADER. |
311 | Return the number of nodes within the loop. */ | |
402209ff JH |
312 | |
313 | static int | |
d329e058 | 314 | flow_loop_nodes_find (basic_block header, struct loop *loop) |
402209ff JH |
315 | { |
316 | basic_block *stack; | |
317 | int sp; | |
2ecfd709 | 318 | int num_nodes = 1; |
402209ff | 319 | |
2ecfd709 ZD |
320 | header->loop_father = loop; |
321 | header->loop_depth = loop->depth; | |
402209ff | 322 | |
2ecfd709 | 323 | if (loop->latch->loop_father != loop) |
402209ff | 324 | { |
2ecfd709 ZD |
325 | stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block)); |
326 | sp = 0; | |
402209ff | 327 | num_nodes++; |
2ecfd709 ZD |
328 | stack[sp++] = loop->latch; |
329 | loop->latch->loop_father = loop; | |
330 | loop->latch->loop_depth = loop->depth; | |
d329e058 | 331 | |
2ecfd709 | 332 | while (sp) |
402209ff | 333 | { |
2ecfd709 ZD |
334 | basic_block node; |
335 | edge e; | |
402209ff | 336 | |
2ecfd709 | 337 | node = stack[--sp]; |
d329e058 | 338 | |
2ecfd709 | 339 | for (e = node->pred; e; e = e->pred_next) |
402209ff | 340 | { |
2ecfd709 ZD |
341 | basic_block ancestor = e->src; |
342 | ||
343 | if (ancestor != ENTRY_BLOCK_PTR | |
344 | && ancestor->loop_father != loop) | |
345 | { | |
346 | ancestor->loop_father = loop; | |
347 | ancestor->loop_depth = loop->depth; | |
348 | num_nodes++; | |
349 | stack[sp++] = ancestor; | |
350 | } | |
402209ff JH |
351 | } |
352 | } | |
2ecfd709 | 353 | free (stack); |
402209ff | 354 | } |
402209ff JH |
355 | return num_nodes; |
356 | } | |
357 | ||
358 | /* Find the root node of the loop pre-header extended basic block and | |
359 | the edges along the trace from the root node to the loop header. */ | |
360 | ||
361 | static void | |
d329e058 | 362 | flow_loop_pre_header_scan (struct loop *loop) |
402209ff | 363 | { |
5f0d2358 | 364 | int num; |
402209ff | 365 | basic_block ebb; |
5f0d2358 | 366 | edge e; |
402209ff JH |
367 | |
368 | loop->num_pre_header_edges = 0; | |
402209ff | 369 | if (loop->num_entries != 1) |
5f0d2358 | 370 | return; |
402209ff JH |
371 | |
372 | ebb = loop->entry_edges[0]->src; | |
5f0d2358 RK |
373 | if (ebb == ENTRY_BLOCK_PTR) |
374 | return; | |
402209ff | 375 | |
5f0d2358 RK |
376 | /* Count number of edges along trace from loop header to |
377 | root of pre-header extended basic block. Usually this is | |
378 | only one or two edges. */ | |
379 | for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next; | |
380 | num++) | |
381 | ebb = ebb->pred->src; | |
382 | ||
6b6996b8 | 383 | loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge)); |
5f0d2358 RK |
384 | loop->num_pre_header_edges = num; |
385 | ||
386 | /* Store edges in order that they are followed. The source of the first edge | |
387 | is the root node of the pre-header extended basic block and the | |
388 | destination of the last last edge is the loop header. */ | |
389 | for (e = loop->entry_edges[0]; num; e = e->src->pred) | |
390 | loop->pre_header_edges[--num] = e; | |
402209ff JH |
391 | } |
392 | ||
393 | /* Return the block for the pre-header of the loop with header | |
394 | HEADER where DOM specifies the dominator information. Return NULL if | |
395 | there is no pre-header. */ | |
396 | ||
397 | static basic_block | |
d329e058 | 398 | flow_loop_pre_header_find (basic_block header, dominance_info dom) |
402209ff JH |
399 | { |
400 | basic_block pre_header; | |
401 | edge e; | |
402 | ||
403 | /* If block p is a predecessor of the header and is the only block | |
404 | that the header does not dominate, then it is the pre-header. */ | |
405 | pre_header = NULL; | |
406 | for (e = header->pred; e; e = e->pred_next) | |
407 | { | |
408 | basic_block node = e->src; | |
409 | ||
410 | if (node != ENTRY_BLOCK_PTR | |
355be0dc | 411 | && ! dominated_by_p (dom, node, header)) |
402209ff JH |
412 | { |
413 | if (pre_header == NULL) | |
414 | pre_header = node; | |
415 | else | |
416 | { | |
417 | /* There are multiple edges into the header from outside | |
418 | the loop so there is no pre-header block. */ | |
419 | pre_header = NULL; | |
420 | break; | |
421 | } | |
422 | } | |
423 | } | |
5f0d2358 | 424 | |
402209ff JH |
425 | return pre_header; |
426 | } | |
427 | ||
35b07080 | 428 | static void |
d329e058 | 429 | establish_preds (struct loop *loop) |
35b07080 ZD |
430 | { |
431 | struct loop *ploop, *father = loop->outer; | |
432 | ||
433 | loop->depth = father->depth + 1; | |
434 | if (loop->pred) | |
435 | free (loop->pred); | |
436 | loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); | |
437 | memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); | |
438 | loop->pred[father->depth] = father; | |
439 | ||
440 | for (ploop = loop->inner; ploop; ploop = ploop->next) | |
441 | establish_preds (ploop); | |
442 | } | |
443 | ||
2ecfd709 | 444 | /* Add LOOP to the loop hierarchy tree where FATHER is father of the |
35b07080 ZD |
445 | added loop. If LOOP has some children, take care of that their |
446 | pred field will be initialized correctly. */ | |
402209ff | 447 | |
2ecfd709 | 448 | void |
d329e058 | 449 | flow_loop_tree_node_add (struct loop *father, struct loop *loop) |
402209ff | 450 | { |
2ecfd709 ZD |
451 | loop->next = father->inner; |
452 | father->inner = loop; | |
453 | loop->outer = father; | |
454 | ||
35b07080 | 455 | establish_preds (loop); |
402209ff JH |
456 | } |
457 | ||
2ecfd709 | 458 | /* Remove LOOP from the loop hierarchy tree. */ |
402209ff | 459 | |
2ecfd709 | 460 | void |
d329e058 | 461 | flow_loop_tree_node_remove (struct loop *loop) |
402209ff | 462 | { |
2ecfd709 | 463 | struct loop *prev, *father; |
402209ff | 464 | |
2ecfd709 ZD |
465 | father = loop->outer; |
466 | loop->outer = NULL; | |
402209ff | 467 | |
2ecfd709 ZD |
468 | /* Remove loop from the list of sons. */ |
469 | if (father->inner == loop) | |
470 | father->inner = loop->next; | |
471 | else | |
472 | { | |
473 | for (prev = father->inner; prev->next != loop; prev = prev->next); | |
474 | prev->next = loop->next; | |
475 | } | |
402209ff | 476 | |
2ecfd709 ZD |
477 | loop->depth = -1; |
478 | free (loop->pred); | |
479 | loop->pred = NULL; | |
402209ff JH |
480 | } |
481 | ||
482 | /* Helper function to compute loop nesting depth and enclosed loop level | |
2ecfd709 | 483 | for the natural loop specified by LOOP. Returns the loop level. */ |
402209ff JH |
484 | |
485 | static int | |
d329e058 | 486 | flow_loop_level_compute (struct loop *loop) |
402209ff JH |
487 | { |
488 | struct loop *inner; | |
489 | int level = 1; | |
490 | ||
491 | if (! loop) | |
492 | return 0; | |
493 | ||
494 | /* Traverse loop tree assigning depth and computing level as the | |
495 | maximum level of all the inner loops of this loop. The loop | |
496 | level is equivalent to the height of the loop in the loop tree | |
497 | and corresponds to the number of enclosed loop levels (including | |
498 | itself). */ | |
499 | for (inner = loop->inner; inner; inner = inner->next) | |
500 | { | |
2ecfd709 | 501 | int ilevel = flow_loop_level_compute (inner) + 1; |
402209ff | 502 | |
2ecfd709 ZD |
503 | if (ilevel > level) |
504 | level = ilevel; | |
402209ff | 505 | } |
5f0d2358 | 506 | |
402209ff | 507 | loop->level = level; |
402209ff JH |
508 | return level; |
509 | } | |
510 | ||
511 | /* Compute the loop nesting depth and enclosed loop level for the loop | |
eaec9b3d | 512 | hierarchy tree specified by LOOPS. Return the maximum enclosed loop |
402209ff JH |
513 | level. */ |
514 | ||
515 | static int | |
d329e058 | 516 | flow_loops_level_compute (struct loops *loops) |
402209ff | 517 | { |
2ecfd709 | 518 | return flow_loop_level_compute (loops->tree_root); |
402209ff JH |
519 | } |
520 | ||
521 | /* Scan a single natural loop specified by LOOP collecting information | |
522 | about it specified by FLAGS. */ | |
523 | ||
524 | int | |
d329e058 | 525 | flow_loop_scan (struct loops *loops, struct loop *loop, int flags) |
402209ff | 526 | { |
402209ff | 527 | if (flags & LOOP_ENTRY_EDGES) |
2ecfd709 ZD |
528 | { |
529 | /* Find edges which enter the loop header. | |
530 | Note that the entry edges should only | |
531 | enter the header of a natural loop. */ | |
532 | flow_loop_entry_edges_find (loop); | |
533 | } | |
402209ff JH |
534 | |
535 | if (flags & LOOP_EXIT_EDGES) | |
402209ff | 536 | { |
2ecfd709 ZD |
537 | /* Find edges which exit the loop. */ |
538 | flow_loop_exit_edges_find (loop); | |
402209ff JH |
539 | } |
540 | ||
541 | if (flags & LOOP_PRE_HEADER) | |
542 | { | |
543 | /* Look to see if the loop has a pre-header node. */ | |
544 | loop->pre_header | |
545 | = flow_loop_pre_header_find (loop->header, loops->cfg.dom); | |
546 | ||
547 | /* Find the blocks within the extended basic block of | |
548 | the loop pre-header. */ | |
549 | flow_loop_pre_header_scan (loop); | |
550 | } | |
5f0d2358 | 551 | |
402209ff JH |
552 | return 1; |
553 | } | |
554 | ||
2ecfd709 ZD |
555 | #define HEADER_BLOCK(B) (* (int *) (B)->aux) |
556 | #define LATCH_EDGE(E) (*(int *) (E)->aux) | |
557 | ||
558 | /* Redirect edge and update latch and header info. */ | |
559 | static void | |
d329e058 | 560 | redirect_edge_with_latch_update (edge e, basic_block to) |
2ecfd709 ZD |
561 | { |
562 | basic_block jump; | |
563 | ||
564 | jump = redirect_edge_and_branch_force (e, to); | |
565 | if (jump) | |
566 | { | |
567 | alloc_aux_for_block (jump, sizeof (int)); | |
568 | HEADER_BLOCK (jump) = 0; | |
569 | alloc_aux_for_edge (jump->pred, sizeof (int)); | |
570 | LATCH_EDGE (jump->succ) = LATCH_EDGE (e); | |
571 | LATCH_EDGE (jump->pred) = 0; | |
572 | } | |
573 | } | |
574 | ||
575 | /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges | |
576 | marked as latch into entry part, analogically for REDIRECT_NONLATCH. | |
577 | In both of these cases, ignore edge EXCEPT. If CONN_LATCH, set edge | |
578 | between created entry part and BB as latch one. Return created entry | |
579 | part. */ | |
580 | ||
581 | static basic_block | |
d329e058 | 582 | make_forwarder_block (basic_block bb, int redirect_latch, int redirect_nonlatch, edge except, int conn_latch) |
2ecfd709 ZD |
583 | { |
584 | edge e, next_e, fallthru; | |
585 | basic_block dummy; | |
586 | rtx insn; | |
587 | ||
588 | insn = PREV_INSN (first_insn_after_basic_block_note (bb)); | |
589 | ||
3d436d2a ZD |
590 | /* For empty block split_block will return NULL. */ |
591 | if (bb->end == insn) | |
592 | emit_note_after (NOTE_INSN_DELETED, insn); | |
593 | ||
2ecfd709 ZD |
594 | fallthru = split_block (bb, insn); |
595 | dummy = fallthru->src; | |
596 | bb = fallthru->dest; | |
597 | ||
598 | bb->aux = xmalloc (sizeof (int)); | |
599 | HEADER_BLOCK (dummy) = 0; | |
600 | HEADER_BLOCK (bb) = 1; | |
601 | ||
4b7e68e7 | 602 | /* Redirect back edges we want to keep. */ |
2ecfd709 ZD |
603 | for (e = dummy->pred; e; e = next_e) |
604 | { | |
605 | next_e = e->pred_next; | |
606 | if (e == except | |
607 | || !((redirect_latch && LATCH_EDGE (e)) | |
608 | || (redirect_nonlatch && !LATCH_EDGE (e)))) | |
609 | { | |
610 | dummy->frequency -= EDGE_FREQUENCY (e); | |
611 | dummy->count -= e->count; | |
612 | if (dummy->frequency < 0) | |
613 | dummy->frequency = 0; | |
614 | if (dummy->count < 0) | |
615 | dummy->count = 0; | |
616 | redirect_edge_with_latch_update (e, bb); | |
617 | } | |
618 | } | |
619 | ||
620 | alloc_aux_for_edge (fallthru, sizeof (int)); | |
621 | LATCH_EDGE (fallthru) = conn_latch; | |
622 | ||
623 | return dummy; | |
624 | } | |
625 | ||
626 | /* Takes care of merging natural loops with shared headers. */ | |
627 | static void | |
d329e058 | 628 | canonicalize_loop_headers (void) |
2ecfd709 | 629 | { |
355be0dc | 630 | dominance_info dom; |
2ecfd709 ZD |
631 | basic_block header; |
632 | edge e; | |
d329e058 | 633 | |
2ecfd709 | 634 | /* Compute the dominators. */ |
355be0dc | 635 | dom = calculate_dominance_info (CDI_DOMINATORS); |
2ecfd709 ZD |
636 | |
637 | alloc_aux_for_blocks (sizeof (int)); | |
638 | alloc_aux_for_edges (sizeof (int)); | |
639 | ||
640 | /* Split blocks so that each loop has only single latch. */ | |
641 | FOR_EACH_BB (header) | |
642 | { | |
643 | int num_latches = 0; | |
644 | int have_abnormal_edge = 0; | |
645 | ||
646 | for (e = header->pred; e; e = e->pred_next) | |
647 | { | |
648 | basic_block latch = e->src; | |
649 | ||
650 | if (e->flags & EDGE_ABNORMAL) | |
651 | have_abnormal_edge = 1; | |
652 | ||
653 | if (latch != ENTRY_BLOCK_PTR | |
355be0dc | 654 | && dominated_by_p (dom, latch, header)) |
2ecfd709 ZD |
655 | { |
656 | num_latches++; | |
657 | LATCH_EDGE (e) = 1; | |
658 | } | |
659 | } | |
660 | if (have_abnormal_edge) | |
661 | HEADER_BLOCK (header) = 0; | |
662 | else | |
663 | HEADER_BLOCK (header) = num_latches; | |
664 | } | |
665 | ||
666 | if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest)) | |
667 | { | |
668 | basic_block bb; | |
669 | ||
670 | /* We could not redirect edges freely here. On the other hand, | |
671 | we can simply split the edge from entry block. */ | |
672 | bb = split_edge (ENTRY_BLOCK_PTR->succ); | |
d329e058 | 673 | |
2ecfd709 ZD |
674 | alloc_aux_for_edge (bb->succ, sizeof (int)); |
675 | LATCH_EDGE (bb->succ) = 0; | |
676 | alloc_aux_for_block (bb, sizeof (int)); | |
677 | HEADER_BLOCK (bb) = 0; | |
678 | } | |
679 | ||
680 | FOR_EACH_BB (header) | |
681 | { | |
682 | int num_latch; | |
683 | int want_join_latch; | |
684 | int max_freq, is_heavy; | |
685 | edge heavy; | |
686 | ||
687 | if (!HEADER_BLOCK (header)) | |
688 | continue; | |
689 | ||
690 | num_latch = HEADER_BLOCK (header); | |
691 | ||
692 | want_join_latch = (num_latch > 1); | |
693 | ||
694 | if (!want_join_latch) | |
695 | continue; | |
696 | ||
697 | /* Find a heavy edge. */ | |
698 | is_heavy = 1; | |
699 | heavy = NULL; | |
700 | max_freq = 0; | |
701 | for (e = header->pred; e; e = e->pred_next) | |
702 | if (LATCH_EDGE (e) && | |
703 | EDGE_FREQUENCY (e) > max_freq) | |
704 | max_freq = EDGE_FREQUENCY (e); | |
705 | for (e = header->pred; e; e = e->pred_next) | |
706 | if (LATCH_EDGE (e) && | |
707 | EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO) | |
708 | { | |
709 | if (heavy) | |
710 | { | |
711 | is_heavy = 0; | |
712 | break; | |
713 | } | |
714 | else | |
715 | heavy = e; | |
716 | } | |
717 | ||
718 | if (is_heavy) | |
719 | { | |
720 | basic_block new_header = | |
721 | make_forwarder_block (header, true, true, heavy, 0); | |
722 | if (num_latch > 2) | |
723 | make_forwarder_block (new_header, true, false, NULL, 1); | |
724 | } | |
725 | else | |
726 | make_forwarder_block (header, true, false, NULL, 1); | |
727 | } | |
728 | ||
729 | free_aux_for_blocks (); | |
730 | free_aux_for_edges (); | |
355be0dc | 731 | free_dominance_info (dom); |
2ecfd709 ZD |
732 | } |
733 | ||
5f0d2358 RK |
734 | /* Find all the natural loops in the function and save in LOOPS structure and |
735 | recalculate loop_depth information in basic block structures. FLAGS | |
736 | controls which loop information is collected. Return the number of natural | |
737 | loops found. */ | |
402209ff JH |
738 | |
739 | int | |
d329e058 | 740 | flow_loops_find (struct loops *loops, int flags) |
402209ff | 741 | { |
0b17ab2f RH |
742 | int i; |
743 | int b; | |
402209ff JH |
744 | int num_loops; |
745 | edge e; | |
746 | sbitmap headers; | |
355be0dc | 747 | dominance_info dom; |
402209ff JH |
748 | int *dfs_order; |
749 | int *rc_order; | |
355be0dc JH |
750 | basic_block header; |
751 | basic_block bb; | |
402209ff JH |
752 | |
753 | /* This function cannot be repeatedly called with different | |
754 | flags to build up the loop information. The loop tree | |
755 | must always be built if this function is called. */ | |
756 | if (! (flags & LOOP_TREE)) | |
757 | abort (); | |
758 | ||
5f0d2358 | 759 | memset (loops, 0, sizeof *loops); |
402209ff JH |
760 | |
761 | /* Taking care of this degenerate case makes the rest of | |
762 | this code simpler. */ | |
0b17ab2f | 763 | if (n_basic_blocks == 0) |
402209ff JH |
764 | return 0; |
765 | ||
766 | dfs_order = NULL; | |
767 | rc_order = NULL; | |
768 | ||
2ecfd709 ZD |
769 | /* Join loops with shared headers. */ |
770 | canonicalize_loop_headers (); | |
771 | ||
402209ff | 772 | /* Compute the dominators. */ |
355be0dc | 773 | dom = loops->cfg.dom = calculate_dominance_info (CDI_DOMINATORS); |
402209ff | 774 | |
2ecfd709 | 775 | /* Count the number of loop headers. This should be the |
402209ff | 776 | same as the number of natural loops. */ |
2ecfd709 ZD |
777 | headers = sbitmap_alloc (last_basic_block); |
778 | sbitmap_zero (headers); | |
779 | ||
402209ff | 780 | num_loops = 0; |
e0082a72 | 781 | FOR_EACH_BB (header) |
402209ff | 782 | { |
2ecfd709 | 783 | int more_latches = 0; |
d329e058 | 784 | |
402209ff JH |
785 | header->loop_depth = 0; |
786 | ||
16f2b86a ZD |
787 | /* If we have an abnormal predecessor, do not consider the |
788 | loop (not worth the problems). */ | |
789 | for (e = header->pred; e; e = e->pred_next) | |
790 | if (e->flags & EDGE_ABNORMAL) | |
791 | break; | |
792 | if (e) | |
793 | continue; | |
794 | ||
402209ff JH |
795 | for (e = header->pred; e; e = e->pred_next) |
796 | { | |
797 | basic_block latch = e->src; | |
798 | ||
2ecfd709 | 799 | if (e->flags & EDGE_ABNORMAL) |
16f2b86a | 800 | abort (); |
2ecfd709 | 801 | |
402209ff JH |
802 | /* Look for back edges where a predecessor is dominated |
803 | by this block. A natural loop has a single entry | |
804 | node (header) that dominates all the nodes in the | |
805 | loop. It also has single back edge to the header | |
2ecfd709 | 806 | from a latch node. */ |
355be0dc | 807 | if (latch != ENTRY_BLOCK_PTR && dominated_by_p (dom, latch, header)) |
2ecfd709 ZD |
808 | { |
809 | /* Shared headers should be eliminated by now. */ | |
810 | if (more_latches) | |
811 | abort (); | |
812 | more_latches = 1; | |
813 | SET_BIT (headers, header->index); | |
814 | num_loops++; | |
815 | } | |
402209ff JH |
816 | } |
817 | } | |
818 | ||
2ecfd709 ZD |
819 | /* Allocate loop structures. */ |
820 | loops->parray = (struct loop **) xcalloc (num_loops + 1, sizeof (struct loop *)); | |
821 | ||
822 | /* Dummy loop containing whole function. */ | |
823 | loops->parray[0] = xcalloc (1, sizeof (struct loop)); | |
824 | loops->parray[0]->next = NULL; | |
825 | loops->parray[0]->inner = NULL; | |
826 | loops->parray[0]->outer = NULL; | |
827 | loops->parray[0]->depth = 0; | |
828 | loops->parray[0]->pred = NULL; | |
829 | loops->parray[0]->num_nodes = n_basic_blocks + 2; | |
830 | loops->parray[0]->latch = EXIT_BLOCK_PTR; | |
831 | loops->parray[0]->header = ENTRY_BLOCK_PTR; | |
832 | ENTRY_BLOCK_PTR->loop_father = loops->parray[0]; | |
833 | EXIT_BLOCK_PTR->loop_father = loops->parray[0]; | |
834 | ||
835 | loops->tree_root = loops->parray[0]; | |
836 | ||
837 | /* Find and record information about all the natural loops | |
838 | in the CFG. */ | |
839 | loops->num = 1; | |
840 | FOR_EACH_BB (bb) | |
841 | bb->loop_father = loops->tree_root; | |
842 | ||
402209ff JH |
843 | if (num_loops) |
844 | { | |
845 | /* Compute depth first search order of the CFG so that outer | |
846 | natural loops will be found before inner natural loops. */ | |
0b17ab2f RH |
847 | dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); |
848 | rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); | |
402209ff JH |
849 | flow_depth_first_order_compute (dfs_order, rc_order); |
850 | ||
851 | /* Save CFG derived information to avoid recomputing it. */ | |
852 | loops->cfg.dom = dom; | |
853 | loops->cfg.dfs_order = dfs_order; | |
854 | loops->cfg.rc_order = rc_order; | |
855 | ||
2ecfd709 | 856 | num_loops = 1; |
402209ff | 857 | |
2ecfd709 | 858 | for (b = 0; b < n_basic_blocks; b++) |
402209ff | 859 | { |
2ecfd709 | 860 | struct loop *loop; |
402209ff JH |
861 | |
862 | /* Search the nodes of the CFG in reverse completion order | |
863 | so that we can find outer loops first. */ | |
2ecfd709 ZD |
864 | if (!TEST_BIT (headers, rc_order[b])) |
865 | continue; | |
866 | ||
867 | header = BASIC_BLOCK (rc_order[b]); | |
d329e058 | 868 | |
2ecfd709 | 869 | loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); |
402209ff | 870 | |
2ecfd709 ZD |
871 | loop->header = header; |
872 | loop->num = num_loops; | |
873 | num_loops++; | |
874 | ||
875 | /* Look for the latch for this header block. */ | |
876 | for (e = header->pred; e; e = e->pred_next) | |
402209ff | 877 | { |
2ecfd709 ZD |
878 | basic_block latch = e->src; |
879 | ||
880 | if (latch != ENTRY_BLOCK_PTR | |
355be0dc | 881 | && dominated_by_p (dom, latch, header)) |
402209ff | 882 | { |
402209ff | 883 | loop->latch = latch; |
2ecfd709 | 884 | break; |
402209ff JH |
885 | } |
886 | } | |
402209ff | 887 | |
2ecfd709 ZD |
888 | flow_loop_tree_node_add (header->loop_father, loop); |
889 | loop->num_nodes = flow_loop_nodes_find (loop->header, loop); | |
402209ff JH |
890 | } |
891 | ||
402209ff | 892 | sbitmap_free (headers); |
402209ff | 893 | |
2ecfd709 ZD |
894 | /* Assign the loop nesting depth and enclosed loop level for each |
895 | loop. */ | |
896 | loops->levels = flow_loops_level_compute (loops); | |
402209ff | 897 | |
2ecfd709 ZD |
898 | /* Scan the loops. */ |
899 | for (i = 1; i < num_loops; i++) | |
900 | flow_loop_scan (loops, loops->parray[i], flags); | |
402209ff | 901 | |
2ecfd709 ZD |
902 | loops->num = num_loops; |
903 | } | |
904 | else | |
905 | { | |
906 | loops->cfg.dom = NULL; | |
355be0dc | 907 | free_dominance_info (dom); |
2ecfd709 | 908 | } |
3d436d2a ZD |
909 | |
910 | loops->state = 0; | |
2ecfd709 ZD |
911 | #ifdef ENABLE_CHECKING |
912 | verify_flow_info (); | |
3d436d2a | 913 | verify_loop_structure (loops); |
2ecfd709 | 914 | #endif |
402209ff | 915 | |
2ecfd709 | 916 | return loops->num; |
402209ff JH |
917 | } |
918 | ||
919 | /* Update the information regarding the loops in the CFG | |
920 | specified by LOOPS. */ | |
5f0d2358 | 921 | |
402209ff | 922 | int |
d329e058 | 923 | flow_loops_update (struct loops *loops, int flags) |
402209ff JH |
924 | { |
925 | /* One day we may want to update the current loop data. For now | |
926 | throw away the old stuff and rebuild what we need. */ | |
2ecfd709 | 927 | if (loops->parray) |
402209ff JH |
928 | flow_loops_free (loops); |
929 | ||
930 | return flow_loops_find (loops, flags); | |
931 | } | |
932 | ||
da7d8304 | 933 | /* Return nonzero if basic block BB belongs to LOOP. */ |
2ecfd709 | 934 | bool |
d329e058 | 935 | flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) |
2ecfd709 ZD |
936 | { |
937 | struct loop *source_loop; | |
938 | ||
939 | if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) | |
940 | return 0; | |
941 | ||
942 | source_loop = bb->loop_father; | |
943 | return loop == source_loop || flow_loop_nested_p (loop, source_loop); | |
944 | } | |
945 | ||
da7d8304 | 946 | /* Return nonzero if edge E enters header of LOOP from outside of LOOP. */ |
402209ff | 947 | |
2ecfd709 | 948 | bool |
d329e058 | 949 | flow_loop_outside_edge_p (const struct loop *loop, edge e) |
402209ff JH |
950 | { |
951 | if (e->dest != loop->header) | |
952 | abort (); | |
2ecfd709 ZD |
953 | return !flow_bb_inside_loop_p (loop, e->src); |
954 | } | |
955 | ||
956 | /* Enumeration predicate for get_loop_body. */ | |
957 | static bool | |
d329e058 | 958 | glb_enum_p (basic_block bb, void *glb_header) |
2ecfd709 ZD |
959 | { |
960 | return bb != (basic_block) glb_header; | |
961 | } | |
962 | ||
963 | /* Gets basic blocks of a loop. */ | |
964 | basic_block * | |
d329e058 | 965 | get_loop_body (const struct loop *loop) |
2ecfd709 ZD |
966 | { |
967 | basic_block *tovisit, bb; | |
3d436d2a | 968 | unsigned tv = 0; |
2ecfd709 ZD |
969 | |
970 | if (!loop->num_nodes) | |
971 | abort (); | |
972 | ||
973 | tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); | |
974 | tovisit[tv++] = loop->header; | |
975 | ||
976 | if (loop->latch == EXIT_BLOCK_PTR) | |
977 | { | |
978 | /* There may be blocks unreachable from EXIT_BLOCK. */ | |
3d436d2a | 979 | if (loop->num_nodes != (unsigned) n_basic_blocks + 2) |
2ecfd709 ZD |
980 | abort (); |
981 | FOR_EACH_BB (bb) | |
982 | tovisit[tv++] = bb; | |
983 | tovisit[tv++] = EXIT_BLOCK_PTR; | |
984 | } | |
985 | else if (loop->latch != loop->header) | |
986 | { | |
987 | tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p, | |
988 | tovisit + 1, loop->num_nodes - 1, | |
989 | loop->header) + 1; | |
990 | } | |
991 | ||
992 | if (tv != loop->num_nodes) | |
993 | abort (); | |
994 | return tovisit; | |
995 | } | |
996 | ||
35b07080 ZD |
997 | /* Gets exit edges of a LOOP, returning their number in N_EDGES. */ |
998 | edge * | |
d329e058 | 999 | get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges) |
35b07080 ZD |
1000 | { |
1001 | edge *edges, e; | |
1002 | unsigned i, n; | |
1003 | basic_block * body; | |
1004 | ||
1005 | if (loop->latch == EXIT_BLOCK_PTR) | |
1006 | abort (); | |
1007 | ||
1008 | body = get_loop_body (loop); | |
1009 | n = 0; | |
1010 | for (i = 0; i < loop->num_nodes; i++) | |
1011 | for (e = body[i]->succ; e; e = e->succ_next) | |
1012 | if (!flow_bb_inside_loop_p (loop, e->dest)) | |
1013 | n++; | |
1014 | edges = xmalloc (n * sizeof (edge)); | |
1015 | *n_edges = n; | |
1016 | n = 0; | |
1017 | for (i = 0; i < loop->num_nodes; i++) | |
1018 | for (e = body[i]->succ; e; e = e->succ_next) | |
1019 | if (!flow_bb_inside_loop_p (loop, e->dest)) | |
1020 | edges[n++] = e; | |
1021 | free (body); | |
1022 | ||
1023 | return edges; | |
1024 | } | |
1025 | ||
2ecfd709 ZD |
1026 | /* Adds basic block BB to LOOP. */ |
1027 | void | |
d329e058 AJ |
1028 | add_bb_to_loop (basic_block bb, struct loop *loop) |
1029 | { | |
2ecfd709 | 1030 | int i; |
d329e058 | 1031 | |
2ecfd709 ZD |
1032 | bb->loop_father = loop; |
1033 | bb->loop_depth = loop->depth; | |
1034 | loop->num_nodes++; | |
1035 | for (i = 0; i < loop->depth; i++) | |
1036 | loop->pred[i]->num_nodes++; | |
1037 | } | |
1038 | ||
1039 | /* Remove basic block BB from loops. */ | |
1040 | void | |
d329e058 AJ |
1041 | remove_bb_from_loops (basic_block bb) |
1042 | { | |
2ecfd709 ZD |
1043 | int i; |
1044 | struct loop *loop = bb->loop_father; | |
1045 | ||
1046 | loop->num_nodes--; | |
1047 | for (i = 0; i < loop->depth; i++) | |
1048 | loop->pred[i]->num_nodes--; | |
1049 | bb->loop_father = NULL; | |
1050 | bb->loop_depth = 0; | |
1051 | } | |
1052 | ||
1053 | /* Finds nearest common ancestor in loop tree for given loops. */ | |
1054 | struct loop * | |
d329e058 | 1055 | find_common_loop (struct loop *loop_s, struct loop *loop_d) |
2ecfd709 ZD |
1056 | { |
1057 | if (!loop_s) return loop_d; | |
1058 | if (!loop_d) return loop_s; | |
d329e058 | 1059 | |
2ecfd709 ZD |
1060 | if (loop_s->depth < loop_d->depth) |
1061 | loop_d = loop_d->pred[loop_s->depth]; | |
1062 | else if (loop_s->depth > loop_d->depth) | |
1063 | loop_s = loop_s->pred[loop_d->depth]; | |
1064 | ||
1065 | while (loop_s != loop_d) | |
1066 | { | |
1067 | loop_s = loop_s->outer; | |
1068 | loop_d = loop_d->outer; | |
1069 | } | |
1070 | return loop_s; | |
1071 | } | |
1072 | ||
3d436d2a ZD |
1073 | /* Cancels the LOOP; it must be innermost one. */ |
1074 | void | |
d329e058 | 1075 | cancel_loop (struct loops *loops, struct loop *loop) |
3d436d2a ZD |
1076 | { |
1077 | basic_block *bbs; | |
1078 | unsigned i; | |
1079 | ||
1080 | if (loop->inner) | |
1081 | abort (); | |
1082 | ||
1083 | /* Move blocks up one level (they should be removed as soon as possible). */ | |
1084 | bbs = get_loop_body (loop); | |
1085 | for (i = 0; i < loop->num_nodes; i++) | |
1086 | bbs[i]->loop_father = loop->outer; | |
1087 | ||
1088 | /* Remove the loop from structure. */ | |
1089 | flow_loop_tree_node_remove (loop); | |
1090 | ||
1091 | /* Remove loop from loops array. */ | |
1092 | loops->parray[loop->num] = NULL; | |
1093 | ||
1094 | /* Free loop data. */ | |
1095 | flow_loop_free (loop); | |
1096 | } | |
1097 | ||
1098 | /* Cancels LOOP and all its subloops. */ | |
1099 | void | |
d329e058 | 1100 | cancel_loop_tree (struct loops *loops, struct loop *loop) |
3d436d2a ZD |
1101 | { |
1102 | while (loop->inner) | |
1103 | cancel_loop_tree (loops, loop->inner); | |
1104 | cancel_loop (loops, loop); | |
1105 | } | |
1106 | ||
e0bb17a8 KH |
1107 | /* Checks that LOOPS are all right: |
1108 | -- sizes of loops are all right | |
2ecfd709 ZD |
1109 | -- results of get_loop_body really belong to the loop |
1110 | -- loop header have just single entry edge and single latch edge | |
1111 | -- loop latches have only single successor that is header of their loop | |
3d436d2a | 1112 | -- irreducible loops are correctly marked |
2ecfd709 ZD |
1113 | */ |
1114 | void | |
d329e058 | 1115 | verify_loop_structure (struct loops *loops) |
2ecfd709 | 1116 | { |
3d436d2a ZD |
1117 | unsigned *sizes, i, j; |
1118 | sbitmap irreds; | |
2ecfd709 ZD |
1119 | basic_block *bbs, bb; |
1120 | struct loop *loop; | |
1121 | int err = 0; | |
35b07080 | 1122 | edge e; |
2ecfd709 ZD |
1123 | |
1124 | /* Check sizes. */ | |
1125 | sizes = xcalloc (loops->num, sizeof (int)); | |
1126 | sizes[0] = 2; | |
1127 | ||
1128 | FOR_EACH_BB (bb) | |
1129 | for (loop = bb->loop_father; loop; loop = loop->outer) | |
1130 | sizes[loop->num]++; | |
1131 | ||
1132 | for (i = 0; i < loops->num; i++) | |
1133 | { | |
1134 | if (!loops->parray[i]) | |
1135 | continue; | |
1136 | ||
1137 | if (loops->parray[i]->num_nodes != sizes[i]) | |
1138 | { | |
1139 | error ("Size of loop %d should be %d, not %d.", | |
1140 | i, sizes[i], loops->parray[i]->num_nodes); | |
1141 | err = 1; | |
1142 | } | |
1143 | } | |
1144 | ||
1145 | free (sizes); | |
1146 | ||
1147 | /* Check get_loop_body. */ | |
1148 | for (i = 1; i < loops->num; i++) | |
1149 | { | |
1150 | loop = loops->parray[i]; | |
1151 | if (!loop) | |
1152 | continue; | |
1153 | bbs = get_loop_body (loop); | |
1154 | ||
1155 | for (j = 0; j < loop->num_nodes; j++) | |
1156 | if (!flow_bb_inside_loop_p (loop, bbs[j])) | |
1157 | { | |
1158 | error ("Bb %d do not belong to loop %d.", | |
1159 | bbs[j]->index, i); | |
1160 | err = 1; | |
1161 | } | |
1162 | free (bbs); | |
1163 | } | |
1164 | ||
1165 | /* Check headers and latches. */ | |
1166 | for (i = 1; i < loops->num; i++) | |
1167 | { | |
1168 | loop = loops->parray[i]; | |
1169 | if (!loop) | |
1170 | continue; | |
1171 | ||
3d436d2a | 1172 | if ((loops->state & LOOPS_HAVE_PREHEADERS) |
2ecfd709 ZD |
1173 | && (!loop->header->pred->pred_next |
1174 | || loop->header->pred->pred_next->pred_next)) | |
1175 | { | |
1176 | error ("Loop %d's header does not have exactly 2 entries.", i); | |
1177 | err = 1; | |
1178 | } | |
3d436d2a | 1179 | if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) |
2ecfd709 ZD |
1180 | { |
1181 | if (!loop->latch->succ | |
1182 | || loop->latch->succ->succ_next) | |
1183 | { | |
1184 | error ("Loop %d's latch does not have exactly 1 successor.", i); | |
1185 | err = 1; | |
1186 | } | |
1187 | if (loop->latch->succ->dest != loop->header) | |
1188 | { | |
1189 | error ("Loop %d's latch does not have header as successor.", i); | |
1190 | err = 1; | |
1191 | } | |
1192 | if (loop->latch->loop_father != loop) | |
1193 | { | |
1194 | error ("Loop %d's latch does not belong directly to it.", i); | |
1195 | err = 1; | |
1196 | } | |
1197 | } | |
1198 | if (loop->header->loop_father != loop) | |
1199 | { | |
1200 | error ("Loop %d's header does not belong directly to it.", i); | |
1201 | err = 1; | |
1202 | } | |
35b07080 ZD |
1203 | if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) |
1204 | && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) | |
1205 | { | |
1206 | error ("Loop %d's latch is marked as part of irreducible region.", i); | |
1207 | err = 1; | |
1208 | } | |
2ecfd709 ZD |
1209 | } |
1210 | ||
3d436d2a ZD |
1211 | /* Check irreducible loops. */ |
1212 | if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) | |
1213 | { | |
1214 | /* Record old info. */ | |
1215 | irreds = sbitmap_alloc (last_basic_block); | |
1216 | FOR_EACH_BB (bb) | |
35b07080 ZD |
1217 | { |
1218 | if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
1219 | SET_BIT (irreds, bb->index); | |
1220 | else | |
1221 | RESET_BIT (irreds, bb->index); | |
1222 | for (e = bb->succ; e; e = e->succ_next) | |
1223 | if (e->flags & EDGE_IRREDUCIBLE_LOOP) | |
d329e058 | 1224 | e->flags |= EDGE_ALL_FLAGS + 1; |
35b07080 | 1225 | } |
3d436d2a ZD |
1226 | |
1227 | /* Recount it. */ | |
1228 | mark_irreducible_loops (loops); | |
1229 | ||
1230 | /* Compare. */ | |
1231 | FOR_EACH_BB (bb) | |
1232 | { | |
1233 | if ((bb->flags & BB_IRREDUCIBLE_LOOP) | |
1234 | && !TEST_BIT (irreds, bb->index)) | |
1235 | { | |
1236 | error ("Basic block %d should be marked irreducible.", bb->index); | |
1237 | err = 1; | |
1238 | } | |
1239 | else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) | |
1240 | && TEST_BIT (irreds, bb->index)) | |
1241 | { | |
1242 | error ("Basic block %d should not be marked irreducible.", bb->index); | |
1243 | err = 1; | |
1244 | } | |
35b07080 ZD |
1245 | for (e = bb->succ; e; e = e->succ_next) |
1246 | { | |
1247 | if ((e->flags & EDGE_IRREDUCIBLE_LOOP) | |
1248 | && !(e->flags & (EDGE_ALL_FLAGS + 1))) | |
1249 | { | |
1250 | error ("Edge from %d to %d should be marked irreducible.", | |
1251 | e->src->index, e->dest->index); | |
1252 | err = 1; | |
1253 | } | |
1254 | else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) | |
1255 | && (e->flags & (EDGE_ALL_FLAGS + 1))) | |
1256 | { | |
1257 | error ("Edge from %d to %d should not be marked irreducible.", | |
1258 | e->src->index, e->dest->index); | |
1259 | err = 1; | |
1260 | } | |
1261 | e->flags &= ~(EDGE_ALL_FLAGS + 1); | |
1262 | } | |
3d436d2a ZD |
1263 | } |
1264 | free (irreds); | |
1265 | } | |
1266 | ||
2ecfd709 ZD |
1267 | if (err) |
1268 | abort (); | |
1269 | } | |
1270 | ||
1271 | /* Returns latch edge of LOOP. */ | |
1272 | edge | |
d329e058 | 1273 | loop_latch_edge (const struct loop *loop) |
2ecfd709 ZD |
1274 | { |
1275 | edge e; | |
1276 | ||
1277 | for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next) | |
1278 | continue; | |
5f0d2358 | 1279 | |
2ecfd709 | 1280 | return e; |
402209ff | 1281 | } |
2ecfd709 ZD |
1282 | |
1283 | /* Returns preheader edge of LOOP. */ | |
1284 | edge | |
d329e058 | 1285 | loop_preheader_edge (const struct loop *loop) |
2ecfd709 ZD |
1286 | { |
1287 | edge e; | |
1288 | ||
1289 | for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next) | |
1290 | continue; | |
1291 | ||
1292 | return e; | |
1293 | } |