|
0
|
1 /* Natural loop discovery code for GNU compiler.
|
|
|
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under
|
|
|
8 the terms of the GNU General Public License as published by the Free
|
|
|
9 Software Foundation; either version 3, or (at your option) any later
|
|
|
10 version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "hard-reg-set.h"
|
|
|
27 #include "obstack.h"
|
|
|
28 #include "function.h"
|
|
|
29 #include "basic-block.h"
|
|
|
30 #include "toplev.h"
|
|
|
31 #include "cfgloop.h"
|
|
|
32 #include "flags.h"
|
|
|
33 #include "tree.h"
|
|
|
34 #include "tree-flow.h"
|
|
|
35 #include "pointer-set.h"
|
|
|
36 #include "output.h"
|
|
|
37 #include "ggc.h"
|
|
|
38
|
|
|
39 static void flow_loops_cfg_dump (FILE *);
|
|
|
40
|
|
|
41 /* Dump loop related CFG information. */
|
|
|
42
|
|
|
43 static void
|
|
|
44 flow_loops_cfg_dump (FILE *file)
|
|
|
45 {
|
|
|
46 basic_block bb;
|
|
|
47
|
|
|
48 if (!file)
|
|
|
49 return;
|
|
|
50
|
|
|
51 FOR_EACH_BB (bb)
|
|
|
52 {
|
|
|
53 edge succ;
|
|
|
54 edge_iterator ei;
|
|
|
55
|
|
|
56 fprintf (file, ";; %d succs { ", bb->index);
|
|
|
57 FOR_EACH_EDGE (succ, ei, bb->succs)
|
|
|
58 fprintf (file, "%d ", succ->dest->index);
|
|
|
59 fprintf (file, "}\n");
|
|
|
60 }
|
|
|
61 }
|
|
|
62
|
|
|
63 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
|
|
|
64
|
|
|
65 bool
|
|
|
66 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
|
|
|
67 {
|
|
|
68 unsigned odepth = loop_depth (outer);
|
|
|
69
|
|
|
70 return (loop_depth (loop) > odepth
|
|
|
71 && VEC_index (loop_p, loop->superloops, odepth) == outer);
|
|
|
72 }
|
|
|
73
|
|
|
74 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
|
|
|
75 loops within LOOP. */
|
|
|
76
|
|
|
77 struct loop *
|
|
|
78 superloop_at_depth (struct loop *loop, unsigned depth)
|
|
|
79 {
|
|
|
80 unsigned ldepth = loop_depth (loop);
|
|
|
81
|
|
|
82 gcc_assert (depth <= ldepth);
|
|
|
83
|
|
|
84 if (depth == ldepth)
|
|
|
85 return loop;
|
|
|
86
|
|
|
87 return VEC_index (loop_p, loop->superloops, depth);
|
|
|
88 }
|
|
|
89
|
|
|
90 /* Returns the list of the latch edges of LOOP. */
|
|
|
91
|
|
|
92 static VEC (edge, heap) *
|
|
|
93 get_loop_latch_edges (const struct loop *loop)
|
|
|
94 {
|
|
|
95 edge_iterator ei;
|
|
|
96 edge e;
|
|
|
97 VEC (edge, heap) *ret = NULL;
|
|
|
98
|
|
|
99 FOR_EACH_EDGE (e, ei, loop->header->preds)
|
|
|
100 {
|
|
|
101 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
|
|
|
102 VEC_safe_push (edge, heap, ret, e);
|
|
|
103 }
|
|
|
104
|
|
|
105 return ret;
|
|
|
106 }
|
|
|
107
|
|
|
108 /* Dump the loop information specified by LOOP to the stream FILE
|
|
|
109 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
|
|
110
|
|
|
111 void
|
|
|
112 flow_loop_dump (const struct loop *loop, FILE *file,
|
|
|
113 void (*loop_dump_aux) (const struct loop *, FILE *, int),
|
|
|
114 int verbose)
|
|
|
115 {
|
|
|
116 basic_block *bbs;
|
|
|
117 unsigned i;
|
|
|
118 VEC (edge, heap) *latches;
|
|
|
119 edge e;
|
|
|
120
|
|
|
121 if (! loop || ! loop->header)
|
|
|
122 return;
|
|
|
123
|
|
|
124 fprintf (file, ";;\n;; Loop %d\n", loop->num);
|
|
|
125
|
|
|
126 fprintf (file, ";; header %d, ", loop->header->index);
|
|
|
127 if (loop->latch)
|
|
|
128 fprintf (file, "latch %d\n", loop->latch->index);
|
|
|
129 else
|
|
|
130 {
|
|
|
131 fprintf (file, "multiple latches:");
|
|
|
132 latches = get_loop_latch_edges (loop);
|
|
|
133 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
|
|
|
134 fprintf (file, " %d", e->src->index);
|
|
|
135 VEC_free (edge, heap, latches);
|
|
|
136 fprintf (file, "\n");
|
|
|
137 }
|
|
|
138
|
|
|
139 fprintf (file, ";; depth %d, outer %ld\n",
|
|
|
140 loop_depth (loop), (long) (loop_outer (loop)
|
|
|
141 ? loop_outer (loop)->num : -1));
|
|
|
142
|
|
|
143 fprintf (file, ";; nodes:");
|
|
|
144 bbs = get_loop_body (loop);
|
|
|
145 for (i = 0; i < loop->num_nodes; i++)
|
|
|
146 fprintf (file, " %d", bbs[i]->index);
|
|
|
147 free (bbs);
|
|
|
148 fprintf (file, "\n");
|
|
|
149
|
|
|
150 if (loop_dump_aux)
|
|
|
151 loop_dump_aux (loop, file, verbose);
|
|
|
152 }
|
|
|
153
|
|
|
154 /* Dump the loop information about loops to the stream FILE,
|
|
|
155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
|
|
|
156
|
|
|
157 void
|
|
|
158 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
|
|
|
159 {
|
|
|
160 loop_iterator li;
|
|
|
161 struct loop *loop;
|
|
|
162
|
|
|
163 if (!current_loops || ! file)
|
|
|
164 return;
|
|
|
165
|
|
|
166 fprintf (file, ";; %d loops found\n", number_of_loops ());
|
|
|
167
|
|
|
168 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
|
|
|
169 {
|
|
|
170 flow_loop_dump (loop, file, loop_dump_aux, verbose);
|
|
|
171 }
|
|
|
172
|
|
|
173 if (verbose)
|
|
|
174 flow_loops_cfg_dump (file);
|
|
|
175 }
|
|
|
176
|
|
|
177 /* Free data allocated for LOOP. */
|
|
|
178
|
|
|
179 void
|
|
|
180 flow_loop_free (struct loop *loop)
|
|
|
181 {
|
|
|
182 struct loop_exit *exit, *next;
|
|
|
183
|
|
|
184 VEC_free (loop_p, gc, loop->superloops);
|
|
|
185
|
|
|
186 /* Break the list of the loop exit records. They will be freed when the
|
|
|
187 corresponding edge is rescanned or removed, and this avoids
|
|
|
188 accessing the (already released) head of the list stored in the
|
|
|
189 loop structure. */
|
|
|
190 for (exit = loop->exits->next; exit != loop->exits; exit = next)
|
|
|
191 {
|
|
|
192 next = exit->next;
|
|
|
193 exit->next = exit;
|
|
|
194 exit->prev = exit;
|
|
|
195 }
|
|
|
196
|
|
|
197 ggc_free (loop->exits);
|
|
|
198 ggc_free (loop);
|
|
|
199 }
|
|
|
200
|
|
|
201 /* Free all the memory allocated for LOOPS. */
|
|
|
202
|
|
|
203 void
|
|
|
204 flow_loops_free (struct loops *loops)
|
|
|
205 {
|
|
|
206 if (loops->larray)
|
|
|
207 {
|
|
|
208 unsigned i;
|
|
|
209 loop_p loop;
|
|
|
210
|
|
|
211 /* Free the loop descriptors. */
|
|
|
212 for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
|
|
|
213 {
|
|
|
214 if (!loop)
|
|
|
215 continue;
|
|
|
216
|
|
|
217 flow_loop_free (loop);
|
|
|
218 }
|
|
|
219
|
|
|
220 VEC_free (loop_p, gc, loops->larray);
|
|
|
221 }
|
|
|
222 }
|
|
|
223
|
|
|
224 /* Find the nodes contained within the LOOP with header HEADER.
|
|
|
225 Return the number of nodes within the loop. */
|
|
|
226
|
|
|
227 int
|
|
|
228 flow_loop_nodes_find (basic_block header, struct loop *loop)
|
|
|
229 {
|
|
|
230 VEC (basic_block, heap) *stack = NULL;
|
|
|
231 int num_nodes = 1;
|
|
|
232 edge latch;
|
|
|
233 edge_iterator latch_ei;
|
|
|
234 unsigned depth = loop_depth (loop);
|
|
|
235
|
|
|
236 header->loop_father = loop;
|
|
|
237 header->loop_depth = depth;
|
|
|
238
|
|
|
239 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
|
|
|
240 {
|
|
|
241 if (latch->src->loop_father == loop
|
|
|
242 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
|
|
|
243 continue;
|
|
|
244
|
|
|
245 num_nodes++;
|
|
|
246 VEC_safe_push (basic_block, heap, stack, latch->src);
|
|
|
247 latch->src->loop_father = loop;
|
|
|
248 latch->src->loop_depth = depth;
|
|
|
249
|
|
|
250 while (!VEC_empty (basic_block, stack))
|
|
|
251 {
|
|
|
252 basic_block node;
|
|
|
253 edge e;
|
|
|
254 edge_iterator ei;
|
|
|
255
|
|
|
256 node = VEC_pop (basic_block, stack);
|
|
|
257
|
|
|
258 FOR_EACH_EDGE (e, ei, node->preds)
|
|
|
259 {
|
|
|
260 basic_block ancestor = e->src;
|
|
|
261
|
|
|
262 if (ancestor->loop_father != loop)
|
|
|
263 {
|
|
|
264 ancestor->loop_father = loop;
|
|
|
265 ancestor->loop_depth = depth;
|
|
|
266 num_nodes++;
|
|
|
267 VEC_safe_push (basic_block, heap, stack, ancestor);
|
|
|
268 }
|
|
|
269 }
|
|
|
270 }
|
|
|
271 }
|
|
|
272 VEC_free (basic_block, heap, stack);
|
|
|
273
|
|
|
274 return num_nodes;
|
|
|
275 }
|
|
|
276
|
|
|
277 /* Records the vector of superloops of the loop LOOP, whose immediate
|
|
|
278 superloop is FATHER. */
|
|
|
279
|
|
|
280 static void
|
|
|
281 establish_preds (struct loop *loop, struct loop *father)
|
|
|
282 {
|
|
|
283 loop_p ploop;
|
|
|
284 unsigned depth = loop_depth (father) + 1;
|
|
|
285 unsigned i;
|
|
|
286
|
|
|
287 VEC_truncate (loop_p, loop->superloops, 0);
|
|
|
288 VEC_reserve (loop_p, gc, loop->superloops, depth);
|
|
|
289 for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
|
|
|
290 VEC_quick_push (loop_p, loop->superloops, ploop);
|
|
|
291 VEC_quick_push (loop_p, loop->superloops, father);
|
|
|
292
|
|
|
293 for (ploop = loop->inner; ploop; ploop = ploop->next)
|
|
|
294 establish_preds (ploop, loop);
|
|
|
295 }
|
|
|
296
|
|
|
297 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
|
|
|
298 added loop. If LOOP has some children, take care of that their
|
|
|
299 pred field will be initialized correctly. */
|
|
|
300
|
|
|
301 void
|
|
|
302 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
|
|
|
303 {
|
|
|
304 loop->next = father->inner;
|
|
|
305 father->inner = loop;
|
|
|
306
|
|
|
307 establish_preds (loop, father);
|
|
|
308 }
|
|
|
309
|
|
|
310 /* Remove LOOP from the loop hierarchy tree. */
|
|
|
311
|
|
|
312 void
|
|
|
313 flow_loop_tree_node_remove (struct loop *loop)
|
|
|
314 {
|
|
|
315 struct loop *prev, *father;
|
|
|
316
|
|
|
317 father = loop_outer (loop);
|
|
|
318
|
|
|
319 /* Remove loop from the list of sons. */
|
|
|
320 if (father->inner == loop)
|
|
|
321 father->inner = loop->next;
|
|
|
322 else
|
|
|
323 {
|
|
|
324 for (prev = father->inner; prev->next != loop; prev = prev->next)
|
|
|
325 continue;
|
|
|
326 prev->next = loop->next;
|
|
|
327 }
|
|
|
328
|
|
|
329 VEC_truncate (loop_p, loop->superloops, 0);
|
|
|
330 }
|
|
|
331
|
|
|
332 /* Allocates and returns new loop structure. */
|
|
|
333
|
|
|
334 struct loop *
|
|
|
335 alloc_loop (void)
|
|
|
336 {
|
|
|
337 struct loop *loop = GGC_CNEW (struct loop);
|
|
|
338
|
|
|
339 loop->exits = GGC_CNEW (struct loop_exit);
|
|
|
340 loop->exits->next = loop->exits->prev = loop->exits;
|
|
|
341
|
|
|
342 return loop;
|
|
|
343 }
|
|
|
344
|
|
|
345 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
|
|
|
346 (including the root of the loop tree). */
|
|
|
347
|
|
|
348 static void
|
|
|
349 init_loops_structure (struct loops *loops, unsigned num_loops)
|
|
|
350 {
|
|
|
351 struct loop *root;
|
|
|
352
|
|
|
353 memset (loops, 0, sizeof *loops);
|
|
|
354 loops->larray = VEC_alloc (loop_p, gc, num_loops);
|
|
|
355
|
|
|
356 /* Dummy loop containing whole function. */
|
|
|
357 root = alloc_loop ();
|
|
|
358 root->num_nodes = n_basic_blocks;
|
|
|
359 root->latch = EXIT_BLOCK_PTR;
|
|
|
360 root->header = ENTRY_BLOCK_PTR;
|
|
|
361 ENTRY_BLOCK_PTR->loop_father = root;
|
|
|
362 EXIT_BLOCK_PTR->loop_father = root;
|
|
|
363
|
|
|
364 VEC_quick_push (loop_p, loops->larray, root);
|
|
|
365 loops->tree_root = root;
|
|
|
366 }
|
|
|
367
|
|
|
368 /* Find all the natural loops in the function and save in LOOPS structure and
|
|
|
369 recalculate loop_depth information in basic block structures.
|
|
|
370 Return the number of natural loops found. */
|
|
|
371
|
|
|
372 int
|
|
|
373 flow_loops_find (struct loops *loops)
|
|
|
374 {
|
|
|
375 int b;
|
|
|
376 int num_loops;
|
|
|
377 edge e;
|
|
|
378 sbitmap headers;
|
|
|
379 int *dfs_order;
|
|
|
380 int *rc_order;
|
|
|
381 basic_block header;
|
|
|
382 basic_block bb;
|
|
|
383
|
|
|
384 /* Ensure that the dominators are computed. */
|
|
|
385 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
386
|
|
|
387 /* Taking care of this degenerate case makes the rest of
|
|
|
388 this code simpler. */
|
|
|
389 if (n_basic_blocks == NUM_FIXED_BLOCKS)
|
|
|
390 {
|
|
|
391 init_loops_structure (loops, 1);
|
|
|
392 return 1;
|
|
|
393 }
|
|
|
394
|
|
|
395 dfs_order = NULL;
|
|
|
396 rc_order = NULL;
|
|
|
397
|
|
|
398 /* Count the number of loop headers. This should be the
|
|
|
399 same as the number of natural loops. */
|
|
|
400 headers = sbitmap_alloc (last_basic_block);
|
|
|
401 sbitmap_zero (headers);
|
|
|
402
|
|
|
403 num_loops = 0;
|
|
|
404 FOR_EACH_BB (header)
|
|
|
405 {
|
|
|
406 edge_iterator ei;
|
|
|
407
|
|
|
408 header->loop_depth = 0;
|
|
|
409
|
|
|
410 /* If we have an abnormal predecessor, do not consider the
|
|
|
411 loop (not worth the problems). */
|
|
|
412 FOR_EACH_EDGE (e, ei, header->preds)
|
|
|
413 if (e->flags & EDGE_ABNORMAL)
|
|
|
414 break;
|
|
|
415 if (e)
|
|
|
416 continue;
|
|
|
417
|
|
|
418 FOR_EACH_EDGE (e, ei, header->preds)
|
|
|
419 {
|
|
|
420 basic_block latch = e->src;
|
|
|
421
|
|
|
422 gcc_assert (!(e->flags & EDGE_ABNORMAL));
|
|
|
423
|
|
|
424 /* Look for back edges where a predecessor is dominated
|
|
|
425 by this block. A natural loop has a single entry
|
|
|
426 node (header) that dominates all the nodes in the
|
|
|
427 loop. It also has single back edge to the header
|
|
|
428 from a latch node. */
|
|
|
429 if (latch != ENTRY_BLOCK_PTR
|
|
|
430 && dominated_by_p (CDI_DOMINATORS, latch, header))
|
|
|
431 {
|
|
|
432 /* Shared headers should be eliminated by now. */
|
|
|
433 SET_BIT (headers, header->index);
|
|
|
434 num_loops++;
|
|
|
435 }
|
|
|
436 }
|
|
|
437 }
|
|
|
438
|
|
|
439 /* Allocate loop structures. */
|
|
|
440 init_loops_structure (loops, num_loops + 1);
|
|
|
441
|
|
|
442 /* Find and record information about all the natural loops
|
|
|
443 in the CFG. */
|
|
|
444 FOR_EACH_BB (bb)
|
|
|
445 bb->loop_father = loops->tree_root;
|
|
|
446
|
|
|
447 if (num_loops)
|
|
|
448 {
|
|
|
449 /* Compute depth first search order of the CFG so that outer
|
|
|
450 natural loops will be found before inner natural loops. */
|
|
|
451 dfs_order = XNEWVEC (int, n_basic_blocks);
|
|
|
452 rc_order = XNEWVEC (int, n_basic_blocks);
|
|
|
453 pre_and_rev_post_order_compute (dfs_order, rc_order, false);
|
|
|
454
|
|
|
455 num_loops = 1;
|
|
|
456
|
|
|
457 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
|
|
|
458 {
|
|
|
459 struct loop *loop;
|
|
|
460 edge_iterator ei;
|
|
|
461
|
|
|
462 /* Search the nodes of the CFG in reverse completion order
|
|
|
463 so that we can find outer loops first. */
|
|
|
464 if (!TEST_BIT (headers, rc_order[b]))
|
|
|
465 continue;
|
|
|
466
|
|
|
467 header = BASIC_BLOCK (rc_order[b]);
|
|
|
468
|
|
|
469 loop = alloc_loop ();
|
|
|
470 VEC_quick_push (loop_p, loops->larray, loop);
|
|
|
471
|
|
|
472 loop->header = header;
|
|
|
473 loop->num = num_loops;
|
|
|
474 num_loops++;
|
|
|
475
|
|
|
476 flow_loop_tree_node_add (header->loop_father, loop);
|
|
|
477 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
|
|
|
478
|
|
|
479 /* Look for the latch for this header block, if it has just a
|
|
|
480 single one. */
|
|
|
481 FOR_EACH_EDGE (e, ei, header->preds)
|
|
|
482 {
|
|
|
483 basic_block latch = e->src;
|
|
|
484
|
|
|
485 if (flow_bb_inside_loop_p (loop, latch))
|
|
|
486 {
|
|
|
487 if (loop->latch != NULL)
|
|
|
488 {
|
|
|
489 /* More than one latch edge. */
|
|
|
490 loop->latch = NULL;
|
|
|
491 break;
|
|
|
492 }
|
|
|
493 loop->latch = latch;
|
|
|
494 }
|
|
|
495 }
|
|
|
496 }
|
|
|
497
|
|
|
498 free (dfs_order);
|
|
|
499 free (rc_order);
|
|
|
500 }
|
|
|
501
|
|
|
502 sbitmap_free (headers);
|
|
|
503
|
|
|
504 loops->exits = NULL;
|
|
|
505 return VEC_length (loop_p, loops->larray);
|
|
|
506 }
|
|
|
507
|
|
|
508 /* Ratio of frequencies of edges so that one of more latch edges is
|
|
|
509 considered to belong to inner loop with same header. */
|
|
|
510 #define HEAVY_EDGE_RATIO 8
|
|
|
511
|
|
|
512 /* Minimum number of samples for that we apply
|
|
|
513 find_subloop_latch_edge_by_profile heuristics. */
|
|
|
514 #define HEAVY_EDGE_MIN_SAMPLES 10
|
|
|
515
|
|
|
516 /* If the profile info is available, finds an edge in LATCHES that much more
|
|
|
517 frequent than the remaining edges. Returns such an edge, or NULL if we do
|
|
|
518 not find one.
|
|
|
519
|
|
|
520 We do not use guessed profile here, only the measured one. The guessed
|
|
|
521 profile is usually too flat and unreliable for this (and it is mostly based
|
|
|
522 on the loop structure of the program, so it does not make much sense to
|
|
|
523 derive the loop structure from it). */
|
|
|
524
|
|
|
525 static edge
|
|
|
526 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
|
|
|
527 {
|
|
|
528 unsigned i;
|
|
|
529 edge e, me = NULL;
|
|
|
530 gcov_type mcount = 0, tcount = 0;
|
|
|
531
|
|
|
532 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
|
|
|
533 {
|
|
|
534 if (e->count > mcount)
|
|
|
535 {
|
|
|
536 me = e;
|
|
|
537 mcount = e->count;
|
|
|
538 }
|
|
|
539 tcount += e->count;
|
|
|
540 }
|
|
|
541
|
|
|
542 if (tcount < HEAVY_EDGE_MIN_SAMPLES
|
|
|
543 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
|
|
|
544 return NULL;
|
|
|
545
|
|
|
546 if (dump_file)
|
|
|
547 fprintf (dump_file,
|
|
|
548 "Found latch edge %d -> %d using profile information.\n",
|
|
|
549 me->src->index, me->dest->index);
|
|
|
550 return me;
|
|
|
551 }
|
|
|
552
|
|
|
553 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
|
|
|
554 on the structure of induction variables. Returns this edge, or NULL if we
|
|
|
555 do not find any.
|
|
|
556
|
|
|
557 We are quite conservative, and look just for an obvious simple innermost
|
|
|
558 loop (which is the case where we would lose the most performance by not
|
|
|
559 disambiguating the loop). More precisely, we look for the following
|
|
|
560 situation: The source of the chosen latch edge dominates sources of all
|
|
|
561 the other latch edges. Additionally, the header does not contain a phi node
|
|
|
562 such that the argument from the chosen edge is equal to the argument from
|
|
|
563 another edge. */
|
|
|
564
|
|
|
565 static edge
|
|
|
566 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches)
|
|
|
567 {
|
|
|
568 edge e, latch = VEC_index (edge, latches, 0);
|
|
|
569 unsigned i;
|
|
|
570 gimple phi;
|
|
|
571 gimple_stmt_iterator psi;
|
|
|
572 tree lop;
|
|
|
573 basic_block bb;
|
|
|
574
|
|
|
575 /* Find the candidate for the latch edge. */
|
|
|
576 for (i = 1; VEC_iterate (edge, latches, i, e); i++)
|
|
|
577 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
|
|
|
578 latch = e;
|
|
|
579
|
|
|
580 /* Verify that it dominates all the latch edges. */
|
|
|
581 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
|
|
|
582 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
|
|
|
583 return NULL;
|
|
|
584
|
|
|
585 /* Check for a phi node that would deny that this is a latch edge of
|
|
|
586 a subloop. */
|
|
|
587 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
|
|
|
588 {
|
|
|
589 phi = gsi_stmt (psi);
|
|
|
590 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
|
|
|
591
|
|
|
592 /* Ignore the values that are not changed inside the subloop. */
|
|
|
593 if (TREE_CODE (lop) != SSA_NAME
|
|
|
594 || SSA_NAME_DEF_STMT (lop) == phi)
|
|
|
595 continue;
|
|
|
596 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
|
|
|
597 if (!bb || !flow_bb_inside_loop_p (loop, bb))
|
|
|
598 continue;
|
|
|
599
|
|
|
600 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
|
|
|
601 if (e != latch
|
|
|
602 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
|
|
|
603 return NULL;
|
|
|
604 }
|
|
|
605
|
|
|
606 if (dump_file)
|
|
|
607 fprintf (dump_file,
|
|
|
608 "Found latch edge %d -> %d using iv structure.\n",
|
|
|
609 latch->src->index, latch->dest->index);
|
|
|
610 return latch;
|
|
|
611 }
|
|
|
612
|
|
|
613 /* If we can determine that one of the several latch edges of LOOP behaves
|
|
|
614 as a latch edge of a separate subloop, returns this edge. Otherwise
|
|
|
615 returns NULL. */
|
|
|
616
|
|
|
617 static edge
|
|
|
618 find_subloop_latch_edge (struct loop *loop)
|
|
|
619 {
|
|
|
620 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
|
|
|
621 edge latch = NULL;
|
|
|
622
|
|
|
623 if (VEC_length (edge, latches) > 1)
|
|
|
624 {
|
|
|
625 latch = find_subloop_latch_edge_by_profile (latches);
|
|
|
626
|
|
|
627 if (!latch
|
|
|
628 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
|
|
|
629 should use cfghook for this, but it is hard to imagine it would
|
|
|
630 be useful elsewhere. */
|
|
|
631 && current_ir_type () == IR_GIMPLE)
|
|
|
632 latch = find_subloop_latch_edge_by_ivs (loop, latches);
|
|
|
633 }
|
|
|
634
|
|
|
635 VEC_free (edge, heap, latches);
|
|
|
636 return latch;
|
|
|
637 }
|
|
|
638
|
|
|
639 /* Callback for make_forwarder_block. Returns true if the edge E is marked
|
|
|
640 in the set MFB_REIS_SET. */
|
|
|
641
|
|
|
642 static struct pointer_set_t *mfb_reis_set;
|
|
|
643 static bool
|
|
|
644 mfb_redirect_edges_in_set (edge e)
|
|
|
645 {
|
|
|
646 return pointer_set_contains (mfb_reis_set, e);
|
|
|
647 }
|
|
|
648
|
|
|
649 /* Creates a subloop of LOOP with latch edge LATCH. */
|
|
|
650
|
|
|
651 static void
|
|
|
652 form_subloop (struct loop *loop, edge latch)
|
|
|
653 {
|
|
|
654 edge_iterator ei;
|
|
|
655 edge e, new_entry;
|
|
|
656 struct loop *new_loop;
|
|
|
657
|
|
|
658 mfb_reis_set = pointer_set_create ();
|
|
|
659 FOR_EACH_EDGE (e, ei, loop->header->preds)
|
|
|
660 {
|
|
|
661 if (e != latch)
|
|
|
662 pointer_set_insert (mfb_reis_set, e);
|
|
|
663 }
|
|
|
664 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
|
|
|
665 NULL);
|
|
|
666 pointer_set_destroy (mfb_reis_set);
|
|
|
667
|
|
|
668 loop->header = new_entry->src;
|
|
|
669
|
|
|
670 /* Find the blocks and subloops that belong to the new loop, and add it to
|
|
|
671 the appropriate place in the loop tree. */
|
|
|
672 new_loop = alloc_loop ();
|
|
|
673 new_loop->header = new_entry->dest;
|
|
|
674 new_loop->latch = latch->src;
|
|
|
675 add_loop (new_loop, loop);
|
|
|
676 }
|
|
|
677
|
|
|
678 /* Make all the latch edges of LOOP to go to a single forwarder block --
|
|
|
679 a new latch of LOOP. */
|
|
|
680
|
|
|
681 static void
|
|
|
682 merge_latch_edges (struct loop *loop)
|
|
|
683 {
|
|
|
684 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
|
|
|
685 edge latch, e;
|
|
|
686 unsigned i;
|
|
|
687
|
|
|
688 gcc_assert (VEC_length (edge, latches) > 0);
|
|
|
689
|
|
|
690 if (VEC_length (edge, latches) == 1)
|
|
|
691 loop->latch = VEC_index (edge, latches, 0)->src;
|
|
|
692 else
|
|
|
693 {
|
|
|
694 if (dump_file)
|
|
|
695 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
|
|
|
696
|
|
|
697 mfb_reis_set = pointer_set_create ();
|
|
|
698 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
|
|
|
699 pointer_set_insert (mfb_reis_set, e);
|
|
|
700 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
|
|
|
701 NULL);
|
|
|
702 pointer_set_destroy (mfb_reis_set);
|
|
|
703
|
|
|
704 loop->header = latch->dest;
|
|
|
705 loop->latch = latch->src;
|
|
|
706 }
|
|
|
707
|
|
|
708 VEC_free (edge, heap, latches);
|
|
|
709 }
|
|
|
710
|
|
|
711 /* LOOP may have several latch edges. Transform it into (possibly several)
|
|
|
712 loops with single latch edge. */
|
|
|
713
|
|
|
714 static void
|
|
|
715 disambiguate_multiple_latches (struct loop *loop)
|
|
|
716 {
|
|
|
717 edge e;
|
|
|
718
|
|
|
719 /* We eliminate the multiple latches by splitting the header to the forwarder
|
|
|
720 block F and the rest R, and redirecting the edges. There are two cases:
|
|
|
721
|
|
|
722 1) If there is a latch edge E that corresponds to a subloop (we guess
|
|
|
723 that based on profile -- if it is taken much more often than the
|
|
|
724 remaining edges; and on trees, using the information about induction
|
|
|
725 variables of the loops), we redirect E to R, all the remaining edges to
|
|
|
726 F, then rescan the loops and try again for the outer loop.
|
|
|
727 2) If there is no such edge, we redirect all latch edges to F, and the
|
|
|
728 entry edges to R, thus making F the single latch of the loop. */
|
|
|
729
|
|
|
730 if (dump_file)
|
|
|
731 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
|
|
|
732 loop->num);
|
|
|
733
|
|
|
734 /* During latch merging, we may need to redirect the entry edges to a new
|
|
|
735 block. This would cause problems if the entry edge was the one from the
|
|
|
736 entry block. To avoid having to handle this case specially, split
|
|
|
737 such entry edge. */
|
|
|
738 e = find_edge (ENTRY_BLOCK_PTR, loop->header);
|
|
|
739 if (e)
|
|
|
740 split_edge (e);
|
|
|
741
|
|
|
742 while (1)
|
|
|
743 {
|
|
|
744 e = find_subloop_latch_edge (loop);
|
|
|
745 if (!e)
|
|
|
746 break;
|
|
|
747
|
|
|
748 form_subloop (loop, e);
|
|
|
749 }
|
|
|
750
|
|
|
751 merge_latch_edges (loop);
|
|
|
752 }
|
|
|
753
|
|
|
754 /* Split loops with multiple latch edges. */
|
|
|
755
|
|
|
756 void
|
|
|
757 disambiguate_loops_with_multiple_latches (void)
|
|
|
758 {
|
|
|
759 loop_iterator li;
|
|
|
760 struct loop *loop;
|
|
|
761
|
|
|
762 FOR_EACH_LOOP (li, loop, 0)
|
|
|
763 {
|
|
|
764 if (!loop->latch)
|
|
|
765 disambiguate_multiple_latches (loop);
|
|
|
766 }
|
|
|
767 }
|
|
|
768
|
|
|
769 /* Return nonzero if basic block BB belongs to LOOP. */
|
|
|
770 bool
|
|
|
771 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
|
|
|
772 {
|
|
|
773 struct loop *source_loop;
|
|
|
774
|
|
|
775 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
|
|
|
776 return 0;
|
|
|
777
|
|
|
778 source_loop = bb->loop_father;
|
|
|
779 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
|
|
|
780 }
|
|
|
781
|
|
|
782 /* Enumeration predicate for get_loop_body_with_size. */
|
|
|
783 static bool
|
|
|
784 glb_enum_p (const_basic_block bb, const void *glb_loop)
|
|
|
785 {
|
|
|
786 const struct loop *const loop = (const struct loop *) glb_loop;
|
|
|
787 return (bb != loop->header
|
|
|
788 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
|
|
|
789 }
|
|
|
790
|
|
|
791 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
|
|
|
792 order against direction of edges from latch. Specially, if
|
|
|
793 header != latch, latch is the 1-st block. LOOP cannot be the fake
|
|
|
794 loop tree root, and its size must be at most MAX_SIZE. The blocks
|
|
|
795 in the LOOP body are stored to BODY, and the size of the LOOP is
|
|
|
796 returned. */
|
|
|
797
|
|
|
798 unsigned
|
|
|
799 get_loop_body_with_size (const struct loop *loop, basic_block *body,
|
|
|
800 unsigned max_size)
|
|
|
801 {
|
|
|
802 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
|
|
|
803 body, max_size, loop);
|
|
|
804 }
|
|
|
805
|
|
|
806 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
|
|
|
807 order against direction of edges from latch. Specially, if
|
|
|
808 header != latch, latch is the 1-st block. */
|
|
|
809
|
|
|
810 basic_block *
|
|
|
811 get_loop_body (const struct loop *loop)
|
|
|
812 {
|
|
|
813 basic_block *body, bb;
|
|
|
814 unsigned tv = 0;
|
|
|
815
|
|
|
816 gcc_assert (loop->num_nodes);
|
|
|
817
|
|
|
818 body = XCNEWVEC (basic_block, loop->num_nodes);
|
|
|
819
|
|
|
820 if (loop->latch == EXIT_BLOCK_PTR)
|
|
|
821 {
|
|
|
822 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
|
|
|
823 special-case the fake loop that contains the whole function. */
|
|
|
824 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
|
|
|
825 body[tv++] = loop->header;
|
|
|
826 body[tv++] = EXIT_BLOCK_PTR;
|
|
|
827 FOR_EACH_BB (bb)
|
|
|
828 body[tv++] = bb;
|
|
|
829 }
|
|
|
830 else
|
|
|
831 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
|
|
|
832
|
|
|
833 gcc_assert (tv == loop->num_nodes);
|
|
|
834 return body;
|
|
|
835 }
|
|
|
836
|
|
|
837 /* Fills dominance descendants inside LOOP of the basic block BB into
|
|
|
838 array TOVISIT from index *TV. */
|
|
|
839
|
|
|
840 static void
|
|
|
841 fill_sons_in_loop (const struct loop *loop, basic_block bb,
|
|
|
842 basic_block *tovisit, int *tv)
|
|
|
843 {
|
|
|
844 basic_block son, postpone = NULL;
|
|
|
845
|
|
|
846 tovisit[(*tv)++] = bb;
|
|
|
847 for (son = first_dom_son (CDI_DOMINATORS, bb);
|
|
|
848 son;
|
|
|
849 son = next_dom_son (CDI_DOMINATORS, son))
|
|
|
850 {
|
|
|
851 if (!flow_bb_inside_loop_p (loop, son))
|
|
|
852 continue;
|
|
|
853
|
|
|
854 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
|
|
|
855 {
|
|
|
856 postpone = son;
|
|
|
857 continue;
|
|
|
858 }
|
|
|
859 fill_sons_in_loop (loop, son, tovisit, tv);
|
|
|
860 }
|
|
|
861
|
|
|
862 if (postpone)
|
|
|
863 fill_sons_in_loop (loop, postpone, tovisit, tv);
|
|
|
864 }
|
|
|
865
|
|
|
866 /* Gets body of a LOOP (that must be different from the outermost loop)
|
|
|
867 sorted by dominance relation. Additionally, if a basic block s dominates
|
|
|
868 the latch, then only blocks dominated by s are be after it. */
|
|
|
869
|
|
|
870 basic_block *
|
|
|
871 get_loop_body_in_dom_order (const struct loop *loop)
|
|
|
872 {
|
|
|
873 basic_block *tovisit;
|
|
|
874 int tv;
|
|
|
875
|
|
|
876 gcc_assert (loop->num_nodes);
|
|
|
877
|
|
|
878 tovisit = XCNEWVEC (basic_block, loop->num_nodes);
|
|
|
879
|
|
|
880 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
881
|
|
|
882 tv = 0;
|
|
|
883 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
|
|
|
884
|
|
|
885 gcc_assert (tv == (int) loop->num_nodes);
|
|
|
886
|
|
|
887 return tovisit;
|
|
|
888 }
|
|
|
889
|
|
|
890 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
|
|
|
891
|
|
|
892 basic_block *
|
|
|
893 get_loop_body_in_custom_order (const struct loop *loop,
|
|
|
894 int (*bb_comparator) (const void *, const void *))
|
|
|
895 {
|
|
|
896 basic_block *bbs = get_loop_body (loop);
|
|
|
897
|
|
|
898 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
|
|
|
899
|
|
|
900 return bbs;
|
|
|
901 }
|
|
|
902
|
|
|
903 /* Get body of a LOOP in breadth first sort order. */
|
|
|
904
|
|
|
905 basic_block *
|
|
|
906 get_loop_body_in_bfs_order (const struct loop *loop)
|
|
|
907 {
|
|
|
908 basic_block *blocks;
|
|
|
909 basic_block bb;
|
|
|
910 bitmap visited;
|
|
|
911 unsigned int i = 0;
|
|
|
912 unsigned int vc = 1;
|
|
|
913
|
|
|
914 gcc_assert (loop->num_nodes);
|
|
|
915 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
916
|
|
|
917 blocks = XCNEWVEC (basic_block, loop->num_nodes);
|
|
|
918 visited = BITMAP_ALLOC (NULL);
|
|
|
919
|
|
|
920 bb = loop->header;
|
|
|
921 while (i < loop->num_nodes)
|
|
|
922 {
|
|
|
923 edge e;
|
|
|
924 edge_iterator ei;
|
|
|
925
|
|
|
926 if (!bitmap_bit_p (visited, bb->index))
|
|
|
927 {
|
|
|
928 /* This basic block is now visited */
|
|
|
929 bitmap_set_bit (visited, bb->index);
|
|
|
930 blocks[i++] = bb;
|
|
|
931 }
|
|
|
932
|
|
|
933 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
934 {
|
|
|
935 if (flow_bb_inside_loop_p (loop, e->dest))
|
|
|
936 {
|
|
|
937 if (!bitmap_bit_p (visited, e->dest->index))
|
|
|
938 {
|
|
|
939 bitmap_set_bit (visited, e->dest->index);
|
|
|
940 blocks[i++] = e->dest;
|
|
|
941 }
|
|
|
942 }
|
|
|
943 }
|
|
|
944
|
|
|
945 gcc_assert (i >= vc);
|
|
|
946
|
|
|
947 bb = blocks[vc++];
|
|
|
948 }
|
|
|
949
|
|
|
950 BITMAP_FREE (visited);
|
|
|
951 return blocks;
|
|
|
952 }
|
|
|
953
|
|
|
954 /* Hash function for struct loop_exit. */
|
|
|
955
|
|
|
956 static hashval_t
|
|
|
957 loop_exit_hash (const void *ex)
|
|
|
958 {
|
|
|
959 const struct loop_exit *const exit = (const struct loop_exit *) ex;
|
|
|
960
|
|
|
961 return htab_hash_pointer (exit->e);
|
|
|
962 }
|
|
|
963
|
|
|
964 /* Equality function for struct loop_exit. Compares with edge. */
|
|
|
965
|
|
|
966 static int
|
|
|
967 loop_exit_eq (const void *ex, const void *e)
|
|
|
968 {
|
|
|
969 const struct loop_exit *const exit = (const struct loop_exit *) ex;
|
|
|
970
|
|
|
971 return exit->e == e;
|
|
|
972 }
|
|
|
973
|
|
|
974 /* Frees the list of loop exit descriptions EX. */
|
|
|
975
|
|
|
976 static void
|
|
|
977 loop_exit_free (void *ex)
|
|
|
978 {
|
|
|
979 struct loop_exit *exit = (struct loop_exit *) ex, *next;
|
|
|
980
|
|
|
981 for (; exit; exit = next)
|
|
|
982 {
|
|
|
983 next = exit->next_e;
|
|
|
984
|
|
|
985 exit->next->prev = exit->prev;
|
|
|
986 exit->prev->next = exit->next;
|
|
|
987
|
|
|
988 ggc_free (exit);
|
|
|
989 }
|
|
|
990 }
|
|
|
991
|
|
|
992 /* Returns the list of records for E as an exit of a loop. */
|
|
|
993
|
|
|
994 static struct loop_exit *
|
|
|
995 get_exit_descriptions (edge e)
|
|
|
996 {
|
|
|
997 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
|
|
|
998 htab_hash_pointer (e));
|
|
|
999 }
|
|
|
1000
|
|
|
1001 /* Updates the lists of loop exits in that E appears.
|
|
|
1002 If REMOVED is true, E is being removed, and we
|
|
|
1003 just remove it from the lists of exits.
|
|
|
1004 If NEW_EDGE is true and E is not a loop exit, we
|
|
|
1005 do not try to remove it from loop exit lists. */
|
|
|
1006
|
|
|
1007 void
|
|
|
1008 rescan_loop_exit (edge e, bool new_edge, bool removed)
|
|
|
1009 {
|
|
|
1010 void **slot;
|
|
|
1011 struct loop_exit *exits = NULL, *exit;
|
|
|
1012 struct loop *aloop, *cloop;
|
|
|
1013
|
|
|
1014 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1015 return;
|
|
|
1016
|
|
|
1017 if (!removed
|
|
|
1018 && e->src->loop_father != NULL
|
|
|
1019 && e->dest->loop_father != NULL
|
|
|
1020 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
|
|
|
1021 {
|
|
|
1022 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
|
|
|
1023 for (aloop = e->src->loop_father;
|
|
|
1024 aloop != cloop;
|
|
|
1025 aloop = loop_outer (aloop))
|
|
|
1026 {
|
|
|
1027 exit = GGC_NEW (struct loop_exit);
|
|
|
1028 exit->e = e;
|
|
|
1029
|
|
|
1030 exit->next = aloop->exits->next;
|
|
|
1031 exit->prev = aloop->exits;
|
|
|
1032 exit->next->prev = exit;
|
|
|
1033 exit->prev->next = exit;
|
|
|
1034
|
|
|
1035 exit->next_e = exits;
|
|
|
1036 exits = exit;
|
|
|
1037 }
|
|
|
1038 }
|
|
|
1039
|
|
|
1040 if (!exits && new_edge)
|
|
|
1041 return;
|
|
|
1042
|
|
|
1043 slot = htab_find_slot_with_hash (current_loops->exits, e,
|
|
|
1044 htab_hash_pointer (e),
|
|
|
1045 exits ? INSERT : NO_INSERT);
|
|
|
1046 if (!slot)
|
|
|
1047 return;
|
|
|
1048
|
|
|
1049 if (exits)
|
|
|
1050 {
|
|
|
1051 if (*slot)
|
|
|
1052 loop_exit_free (*slot);
|
|
|
1053 *slot = exits;
|
|
|
1054 }
|
|
|
1055 else
|
|
|
1056 htab_clear_slot (current_loops->exits, slot);
|
|
|
1057 }
|
|
|
1058
|
|
|
1059 /* For each loop, record list of exit edges, and start maintaining these
|
|
|
1060 lists. */
|
|
|
1061
|
|
|
1062 void
|
|
|
1063 record_loop_exits (void)
|
|
|
1064 {
|
|
|
1065 basic_block bb;
|
|
|
1066 edge_iterator ei;
|
|
|
1067 edge e;
|
|
|
1068
|
|
|
1069 if (!current_loops)
|
|
|
1070 return;
|
|
|
1071
|
|
|
1072 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1073 return;
|
|
|
1074 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
|
|
|
1075
|
|
|
1076 gcc_assert (current_loops->exits == NULL);
|
|
|
1077 current_loops->exits = htab_create_alloc (2 * number_of_loops (),
|
|
|
1078 loop_exit_hash,
|
|
|
1079 loop_exit_eq,
|
|
|
1080 loop_exit_free,
|
|
|
1081 ggc_calloc, ggc_free);
|
|
|
1082
|
|
|
1083 FOR_EACH_BB (bb)
|
|
|
1084 {
|
|
|
1085 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1086 {
|
|
|
1087 rescan_loop_exit (e, true, false);
|
|
|
1088 }
|
|
|
1089 }
|
|
|
1090 }
|
|
|
1091
|
|
|
1092 /* Dumps information about the exit in *SLOT to FILE.
|
|
|
1093 Callback for htab_traverse. */
|
|
|
1094
|
|
|
1095 static int
|
|
|
1096 dump_recorded_exit (void **slot, void *file)
|
|
|
1097 {
|
|
|
1098 struct loop_exit *exit = (struct loop_exit *) *slot;
|
|
|
1099 unsigned n = 0;
|
|
|
1100 edge e = exit->e;
|
|
|
1101
|
|
|
1102 for (; exit != NULL; exit = exit->next_e)
|
|
|
1103 n++;
|
|
|
1104
|
|
|
1105 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
|
|
|
1106 e->src->index, e->dest->index, n);
|
|
|
1107
|
|
|
1108 return 1;
|
|
|
1109 }
|
|
|
1110
|
|
|
1111 /* Dumps the recorded exits of loops to FILE. */
|
|
|
1112
|
|
|
1113 extern void dump_recorded_exits (FILE *);
|
|
|
1114 void
|
|
|
1115 dump_recorded_exits (FILE *file)
|
|
|
1116 {
|
|
|
1117 if (!current_loops->exits)
|
|
|
1118 return;
|
|
|
1119 htab_traverse (current_loops->exits, dump_recorded_exit, file);
|
|
|
1120 }
|
|
|
1121
|
|
|
1122 /* Releases lists of loop exits. */
|
|
|
1123
|
|
|
1124 void
|
|
|
1125 release_recorded_exits (void)
|
|
|
1126 {
|
|
|
1127 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
|
|
|
1128 htab_delete (current_loops->exits);
|
|
|
1129 current_loops->exits = NULL;
|
|
|
1130 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
|
|
|
1131 }
|
|
|
1132
|
|
|
1133 /* Returns the list of the exit edges of a LOOP. */
|
|
|
1134
|
|
|
1135 VEC (edge, heap) *
|
|
|
1136 get_loop_exit_edges (const struct loop *loop)
|
|
|
1137 {
|
|
|
1138 VEC (edge, heap) *edges = NULL;
|
|
|
1139 edge e;
|
|
|
1140 unsigned i;
|
|
|
1141 basic_block *body;
|
|
|
1142 edge_iterator ei;
|
|
|
1143 struct loop_exit *exit;
|
|
|
1144
|
|
|
1145 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
1146
|
|
|
1147 /* If we maintain the lists of exits, use them. Otherwise we must
|
|
|
1148 scan the body of the loop. */
|
|
|
1149 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1150 {
|
|
|
1151 for (exit = loop->exits->next; exit->e; exit = exit->next)
|
|
|
1152 VEC_safe_push (edge, heap, edges, exit->e);
|
|
|
1153 }
|
|
|
1154 else
|
|
|
1155 {
|
|
|
1156 body = get_loop_body (loop);
|
|
|
1157 for (i = 0; i < loop->num_nodes; i++)
|
|
|
1158 FOR_EACH_EDGE (e, ei, body[i]->succs)
|
|
|
1159 {
|
|
|
1160 if (!flow_bb_inside_loop_p (loop, e->dest))
|
|
|
1161 VEC_safe_push (edge, heap, edges, e);
|
|
|
1162 }
|
|
|
1163 free (body);
|
|
|
1164 }
|
|
|
1165
|
|
|
1166 return edges;
|
|
|
1167 }
|
|
|
1168
|
|
|
1169 /* Counts the number of conditional branches inside LOOP. */
|
|
|
1170
|
|
|
1171 unsigned
|
|
|
1172 num_loop_branches (const struct loop *loop)
|
|
|
1173 {
|
|
|
1174 unsigned i, n;
|
|
|
1175 basic_block * body;
|
|
|
1176
|
|
|
1177 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
|
|
|
1178
|
|
|
1179 body = get_loop_body (loop);
|
|
|
1180 n = 0;
|
|
|
1181 for (i = 0; i < loop->num_nodes; i++)
|
|
|
1182 if (EDGE_COUNT (body[i]->succs) >= 2)
|
|
|
1183 n++;
|
|
|
1184 free (body);
|
|
|
1185
|
|
|
1186 return n;
|
|
|
1187 }
|
|
|
1188
|
|
|
1189 /* Adds basic block BB to LOOP. */
|
|
|
1190 void
|
|
|
1191 add_bb_to_loop (basic_block bb, struct loop *loop)
|
|
|
1192 {
|
|
|
1193 unsigned i;
|
|
|
1194 loop_p ploop;
|
|
|
1195 edge_iterator ei;
|
|
|
1196 edge e;
|
|
|
1197
|
|
|
1198 gcc_assert (bb->loop_father == NULL);
|
|
|
1199 bb->loop_father = loop;
|
|
|
1200 bb->loop_depth = loop_depth (loop);
|
|
|
1201 loop->num_nodes++;
|
|
|
1202 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
|
|
|
1203 ploop->num_nodes++;
|
|
|
1204
|
|
|
1205 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1206 {
|
|
|
1207 rescan_loop_exit (e, true, false);
|
|
|
1208 }
|
|
|
1209 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1210 {
|
|
|
1211 rescan_loop_exit (e, true, false);
|
|
|
1212 }
|
|
|
1213 }
|
|
|
1214
|
|
|
1215 /* Remove basic block BB from loops. */
|
|
|
1216 void
|
|
|
1217 remove_bb_from_loops (basic_block bb)
|
|
|
1218 {
|
|
|
1219 int i;
|
|
|
1220 struct loop *loop = bb->loop_father;
|
|
|
1221 loop_p ploop;
|
|
|
1222 edge_iterator ei;
|
|
|
1223 edge e;
|
|
|
1224
|
|
|
1225 gcc_assert (loop != NULL);
|
|
|
1226 loop->num_nodes--;
|
|
|
1227 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
|
|
|
1228 ploop->num_nodes--;
|
|
|
1229 bb->loop_father = NULL;
|
|
|
1230 bb->loop_depth = 0;
|
|
|
1231
|
|
|
1232 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1233 {
|
|
|
1234 rescan_loop_exit (e, false, true);
|
|
|
1235 }
|
|
|
1236 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1237 {
|
|
|
1238 rescan_loop_exit (e, false, true);
|
|
|
1239 }
|
|
|
1240 }
|
|
|
1241
|
|
|
1242 /* Finds nearest common ancestor in loop tree for given loops. */
|
|
|
1243 struct loop *
|
|
|
1244 find_common_loop (struct loop *loop_s, struct loop *loop_d)
|
|
|
1245 {
|
|
|
1246 unsigned sdepth, ddepth;
|
|
|
1247
|
|
|
1248 if (!loop_s) return loop_d;
|
|
|
1249 if (!loop_d) return loop_s;
|
|
|
1250
|
|
|
1251 sdepth = loop_depth (loop_s);
|
|
|
1252 ddepth = loop_depth (loop_d);
|
|
|
1253
|
|
|
1254 if (sdepth < ddepth)
|
|
|
1255 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
|
|
|
1256 else if (sdepth > ddepth)
|
|
|
1257 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
|
|
|
1258
|
|
|
1259 while (loop_s != loop_d)
|
|
|
1260 {
|
|
|
1261 loop_s = loop_outer (loop_s);
|
|
|
1262 loop_d = loop_outer (loop_d);
|
|
|
1263 }
|
|
|
1264 return loop_s;
|
|
|
1265 }
|
|
|
1266
|
|
|
1267 /* Removes LOOP from structures and frees its data. */
|
|
|
1268
|
|
|
1269 void
|
|
|
1270 delete_loop (struct loop *loop)
|
|
|
1271 {
|
|
|
1272 /* Remove the loop from structure. */
|
|
|
1273 flow_loop_tree_node_remove (loop);
|
|
|
1274
|
|
|
1275 /* Remove loop from loops array. */
|
|
|
1276 VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
|
|
|
1277
|
|
|
1278 /* Free loop data. */
|
|
|
1279 flow_loop_free (loop);
|
|
|
1280 }
|
|
|
1281
|
|
|
1282 /* Cancels the LOOP; it must be innermost one. */
|
|
|
1283
|
|
|
1284 static void
|
|
|
1285 cancel_loop (struct loop *loop)
|
|
|
1286 {
|
|
|
1287 basic_block *bbs;
|
|
|
1288 unsigned i;
|
|
|
1289 struct loop *outer = loop_outer (loop);
|
|
|
1290
|
|
|
1291 gcc_assert (!loop->inner);
|
|
|
1292
|
|
|
1293 /* Move blocks up one level (they should be removed as soon as possible). */
|
|
|
1294 bbs = get_loop_body (loop);
|
|
|
1295 for (i = 0; i < loop->num_nodes; i++)
|
|
|
1296 bbs[i]->loop_father = outer;
|
|
|
1297
|
|
|
1298 delete_loop (loop);
|
|
|
1299 }
|
|
|
1300
|
|
|
1301 /* Cancels LOOP and all its subloops. */
|
|
|
1302 void
|
|
|
1303 cancel_loop_tree (struct loop *loop)
|
|
|
1304 {
|
|
|
1305 while (loop->inner)
|
|
|
1306 cancel_loop_tree (loop->inner);
|
|
|
1307 cancel_loop (loop);
|
|
|
1308 }
|
|
|
1309
|
|
|
1310 /* Checks that information about loops is correct
|
|
|
1311 -- sizes of loops are all right
|
|
|
1312 -- results of get_loop_body really belong to the loop
|
|
|
1313 -- loop header have just single entry edge and single latch edge
|
|
|
1314 -- loop latches have only single successor that is header of their loop
|
|
|
1315 -- irreducible loops are correctly marked
|
|
|
1316 */
|
|
|
1317 void
|
|
|
1318 verify_loop_structure (void)
|
|
|
1319 {
|
|
|
1320 unsigned *sizes, i, j;
|
|
|
1321 sbitmap irreds;
|
|
|
1322 basic_block *bbs, bb;
|
|
|
1323 struct loop *loop;
|
|
|
1324 int err = 0;
|
|
|
1325 edge e;
|
|
|
1326 unsigned num = number_of_loops ();
|
|
|
1327 loop_iterator li;
|
|
|
1328 struct loop_exit *exit, *mexit;
|
|
|
1329
|
|
|
1330 /* Check sizes. */
|
|
|
1331 sizes = XCNEWVEC (unsigned, num);
|
|
|
1332 sizes[0] = 2;
|
|
|
1333
|
|
|
1334 FOR_EACH_BB (bb)
|
|
|
1335 for (loop = bb->loop_father; loop; loop = loop_outer (loop))
|
|
|
1336 sizes[loop->num]++;
|
|
|
1337
|
|
|
1338 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
|
|
|
1339 {
|
|
|
1340 i = loop->num;
|
|
|
1341
|
|
|
1342 if (loop->num_nodes != sizes[i])
|
|
|
1343 {
|
|
|
1344 error ("size of loop %d should be %d, not %d",
|
|
|
1345 i, sizes[i], loop->num_nodes);
|
|
|
1346 err = 1;
|
|
|
1347 }
|
|
|
1348 }
|
|
|
1349
|
|
|
1350 /* Check get_loop_body. */
|
|
|
1351 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1352 {
|
|
|
1353 bbs = get_loop_body (loop);
|
|
|
1354
|
|
|
1355 for (j = 0; j < loop->num_nodes; j++)
|
|
|
1356 if (!flow_bb_inside_loop_p (loop, bbs[j]))
|
|
|
1357 {
|
|
|
1358 error ("bb %d do not belong to loop %d",
|
|
|
1359 bbs[j]->index, loop->num);
|
|
|
1360 err = 1;
|
|
|
1361 }
|
|
|
1362 free (bbs);
|
|
|
1363 }
|
|
|
1364
|
|
|
1365 /* Check headers and latches. */
|
|
|
1366 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1367 {
|
|
|
1368 i = loop->num;
|
|
|
1369
|
|
|
1370 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
|
|
|
1371 && EDGE_COUNT (loop->header->preds) != 2)
|
|
|
1372 {
|
|
|
1373 error ("loop %d's header does not have exactly 2 entries", i);
|
|
|
1374 err = 1;
|
|
|
1375 }
|
|
|
1376 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
|
|
|
1377 {
|
|
|
1378 if (!single_succ_p (loop->latch))
|
|
|
1379 {
|
|
|
1380 error ("loop %d's latch does not have exactly 1 successor", i);
|
|
|
1381 err = 1;
|
|
|
1382 }
|
|
|
1383 if (single_succ (loop->latch) != loop->header)
|
|
|
1384 {
|
|
|
1385 error ("loop %d's latch does not have header as successor", i);
|
|
|
1386 err = 1;
|
|
|
1387 }
|
|
|
1388 if (loop->latch->loop_father != loop)
|
|
|
1389 {
|
|
|
1390 error ("loop %d's latch does not belong directly to it", i);
|
|
|
1391 err = 1;
|
|
|
1392 }
|
|
|
1393 }
|
|
|
1394 if (loop->header->loop_father != loop)
|
|
|
1395 {
|
|
|
1396 error ("loop %d's header does not belong directly to it", i);
|
|
|
1397 err = 1;
|
|
|
1398 }
|
|
|
1399 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
|
|
|
1400 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
|
|
|
1401 {
|
|
|
1402 error ("loop %d's latch is marked as part of irreducible region", i);
|
|
|
1403 err = 1;
|
|
|
1404 }
|
|
|
1405 }
|
|
|
1406
|
|
|
1407 /* Check irreducible loops. */
|
|
|
1408 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
|
|
|
1409 {
|
|
|
1410 /* Record old info. */
|
|
|
1411 irreds = sbitmap_alloc (last_basic_block);
|
|
|
1412 FOR_EACH_BB (bb)
|
|
|
1413 {
|
|
|
1414 edge_iterator ei;
|
|
|
1415 if (bb->flags & BB_IRREDUCIBLE_LOOP)
|
|
|
1416 SET_BIT (irreds, bb->index);
|
|
|
1417 else
|
|
|
1418 RESET_BIT (irreds, bb->index);
|
|
|
1419 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1420 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
|
|
|
1421 e->flags |= EDGE_ALL_FLAGS + 1;
|
|
|
1422 }
|
|
|
1423
|
|
|
1424 /* Recount it. */
|
|
|
1425 mark_irreducible_loops ();
|
|
|
1426
|
|
|
1427 /* Compare. */
|
|
|
1428 FOR_EACH_BB (bb)
|
|
|
1429 {
|
|
|
1430 edge_iterator ei;
|
|
|
1431
|
|
|
1432 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
|
|
|
1433 && !TEST_BIT (irreds, bb->index))
|
|
|
1434 {
|
|
|
1435 error ("basic block %d should be marked irreducible", bb->index);
|
|
|
1436 err = 1;
|
|
|
1437 }
|
|
|
1438 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
|
|
|
1439 && TEST_BIT (irreds, bb->index))
|
|
|
1440 {
|
|
|
1441 error ("basic block %d should not be marked irreducible", bb->index);
|
|
|
1442 err = 1;
|
|
|
1443 }
|
|
|
1444 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1445 {
|
|
|
1446 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
|
|
|
1447 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
|
|
|
1448 {
|
|
|
1449 error ("edge from %d to %d should be marked irreducible",
|
|
|
1450 e->src->index, e->dest->index);
|
|
|
1451 err = 1;
|
|
|
1452 }
|
|
|
1453 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
|
|
|
1454 && (e->flags & (EDGE_ALL_FLAGS + 1)))
|
|
|
1455 {
|
|
|
1456 error ("edge from %d to %d should not be marked irreducible",
|
|
|
1457 e->src->index, e->dest->index);
|
|
|
1458 err = 1;
|
|
|
1459 }
|
|
|
1460 e->flags &= ~(EDGE_ALL_FLAGS + 1);
|
|
|
1461 }
|
|
|
1462 }
|
|
|
1463 free (irreds);
|
|
|
1464 }
|
|
|
1465
|
|
|
1466 /* Check the recorded loop exits. */
|
|
|
1467 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1468 {
|
|
|
1469 if (!loop->exits || loop->exits->e != NULL)
|
|
|
1470 {
|
|
|
1471 error ("corrupted head of the exits list of loop %d",
|
|
|
1472 loop->num);
|
|
|
1473 err = 1;
|
|
|
1474 }
|
|
|
1475 else
|
|
|
1476 {
|
|
|
1477 /* Check that the list forms a cycle, and all elements except
|
|
|
1478 for the head are nonnull. */
|
|
|
1479 for (mexit = loop->exits, exit = mexit->next, i = 0;
|
|
|
1480 exit->e && exit != mexit;
|
|
|
1481 exit = exit->next)
|
|
|
1482 {
|
|
|
1483 if (i++ & 1)
|
|
|
1484 mexit = mexit->next;
|
|
|
1485 }
|
|
|
1486
|
|
|
1487 if (exit != loop->exits)
|
|
|
1488 {
|
|
|
1489 error ("corrupted exits list of loop %d", loop->num);
|
|
|
1490 err = 1;
|
|
|
1491 }
|
|
|
1492 }
|
|
|
1493
|
|
|
1494 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1495 {
|
|
|
1496 if (loop->exits->next != loop->exits)
|
|
|
1497 {
|
|
|
1498 error ("nonempty exits list of loop %d, but exits are not recorded",
|
|
|
1499 loop->num);
|
|
|
1500 err = 1;
|
|
|
1501 }
|
|
|
1502 }
|
|
|
1503 }
|
|
|
1504
|
|
|
1505 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1506 {
|
|
|
1507 unsigned n_exits = 0, eloops;
|
|
|
1508
|
|
|
1509 memset (sizes, 0, sizeof (unsigned) * num);
|
|
|
1510 FOR_EACH_BB (bb)
|
|
|
1511 {
|
|
|
1512 edge_iterator ei;
|
|
|
1513 if (bb->loop_father == current_loops->tree_root)
|
|
|
1514 continue;
|
|
|
1515 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
1516 {
|
|
|
1517 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
|
|
|
1518 continue;
|
|
|
1519
|
|
|
1520 n_exits++;
|
|
|
1521 exit = get_exit_descriptions (e);
|
|
|
1522 if (!exit)
|
|
|
1523 {
|
|
|
1524 error ("Exit %d->%d not recorded",
|
|
|
1525 e->src->index, e->dest->index);
|
|
|
1526 err = 1;
|
|
|
1527 }
|
|
|
1528 eloops = 0;
|
|
|
1529 for (; exit; exit = exit->next_e)
|
|
|
1530 eloops++;
|
|
|
1531
|
|
|
1532 for (loop = bb->loop_father;
|
|
|
1533 loop != e->dest->loop_father;
|
|
|
1534 loop = loop_outer (loop))
|
|
|
1535 {
|
|
|
1536 eloops--;
|
|
|
1537 sizes[loop->num]++;
|
|
|
1538 }
|
|
|
1539
|
|
|
1540 if (eloops != 0)
|
|
|
1541 {
|
|
|
1542 error ("Wrong list of exited loops for edge %d->%d",
|
|
|
1543 e->src->index, e->dest->index);
|
|
|
1544 err = 1;
|
|
|
1545 }
|
|
|
1546 }
|
|
|
1547 }
|
|
|
1548
|
|
|
1549 if (n_exits != htab_elements (current_loops->exits))
|
|
|
1550 {
|
|
|
1551 error ("Too many loop exits recorded");
|
|
|
1552 err = 1;
|
|
|
1553 }
|
|
|
1554
|
|
|
1555 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1556 {
|
|
|
1557 eloops = 0;
|
|
|
1558 for (exit = loop->exits->next; exit->e; exit = exit->next)
|
|
|
1559 eloops++;
|
|
|
1560 if (eloops != sizes[loop->num])
|
|
|
1561 {
|
|
|
1562 error ("%d exits recorded for loop %d (having %d exits)",
|
|
|
1563 eloops, loop->num, sizes[loop->num]);
|
|
|
1564 err = 1;
|
|
|
1565 }
|
|
|
1566 }
|
|
|
1567 }
|
|
|
1568
|
|
|
1569 gcc_assert (!err);
|
|
|
1570
|
|
|
1571 free (sizes);
|
|
|
1572 }
|
|
|
1573
|
|
|
1574 /* Returns latch edge of LOOP. */
|
|
|
1575 edge
|
|
|
1576 loop_latch_edge (const struct loop *loop)
|
|
|
1577 {
|
|
|
1578 return find_edge (loop->latch, loop->header);
|
|
|
1579 }
|
|
|
1580
|
|
|
1581 /* Returns preheader edge of LOOP. */
|
|
|
1582 edge
|
|
|
1583 loop_preheader_edge (const struct loop *loop)
|
|
|
1584 {
|
|
|
1585 edge e;
|
|
|
1586 edge_iterator ei;
|
|
|
1587
|
|
|
1588 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
|
|
|
1589
|
|
|
1590 FOR_EACH_EDGE (e, ei, loop->header->preds)
|
|
|
1591 if (e->src != loop->latch)
|
|
|
1592 break;
|
|
|
1593
|
|
|
1594 return e;
|
|
|
1595 }
|
|
|
1596
|
|
|
1597 /* Returns true if E is an exit of LOOP. */
|
|
|
1598
|
|
|
1599 bool
|
|
|
1600 loop_exit_edge_p (const struct loop *loop, const_edge e)
|
|
|
1601 {
|
|
|
1602 return (flow_bb_inside_loop_p (loop, e->src)
|
|
|
1603 && !flow_bb_inside_loop_p (loop, e->dest));
|
|
|
1604 }
|
|
|
1605
|
|
|
1606 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
|
|
|
1607 or more than one exit. If loops do not have the exits recorded, NULL
|
|
|
1608 is returned always. */
|
|
|
1609
|
|
|
1610 edge
|
|
|
1611 single_exit (const struct loop *loop)
|
|
|
1612 {
|
|
|
1613 struct loop_exit *exit = loop->exits->next;
|
|
|
1614
|
|
|
1615 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
|
|
|
1616 return NULL;
|
|
|
1617
|
|
|
1618 if (exit->e && exit->next == loop->exits)
|
|
|
1619 return exit->e;
|
|
|
1620 else
|
|
|
1621 return NULL;
|
|
|
1622 }
|
|
|
1623
|
|
|
1624 /* Returns true when BB has an edge exiting LOOP. */
|
|
|
1625
|
|
|
1626 bool
|
|
|
1627 is_loop_exit (struct loop *loop, basic_block bb)
|
|
|
1628 {
|
|
|
1629 edge e;
|
|
|
1630 edge_iterator ei;
|
|
|
1631
|
|
|
1632 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
1633 if (loop_exit_edge_p (loop, e))
|
|
|
1634 return true;
|
|
|
1635
|
|
|
1636 return false;
|
|
|
1637 }
|
