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