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