1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "hard-reg-set.h"
25 #include "basic-block.h"
27 static void flow_loops_cfg_dump
PARAMS ((const struct loops
*,
29 static int flow_loop_nested_p
PARAMS ((struct loop
*,
31 static int flow_loop_entry_edges_find
PARAMS ((basic_block
, const sbitmap
,
33 static int flow_loop_exit_edges_find
PARAMS ((const sbitmap
, edge
**));
34 static int flow_loop_nodes_find
PARAMS ((basic_block
, basic_block
,
36 static void flow_loop_pre_header_scan
PARAMS ((struct loop
*));
37 static basic_block flow_loop_pre_header_find
PARAMS ((basic_block
,
39 static void flow_loop_tree_node_add
PARAMS ((struct loop
*,
41 static void flow_loops_tree_build
PARAMS ((struct loops
*));
42 static int flow_loop_level_compute
PARAMS ((struct loop
*, int));
43 static int flow_loops_level_compute
PARAMS ((struct loops
*));
45 /* Dump loop related CFG information. */
48 flow_loops_cfg_dump (loops
, file
)
49 const struct loops
*loops
;
55 if (! loops
->num
|| ! file
|| ! loops
->cfg
.dom
)
62 fprintf (file
, ";; %d succs { ", bb
->index
);
63 for (succ
= bb
->succ
; succ
; succ
= succ
->succ_next
)
64 fprintf (file
, "%d ", succ
->dest
->index
);
65 flow_nodes_print ("} dom", loops
->cfg
.dom
[i
], file
);
68 /* Dump the DFS node order. */
69 if (loops
->cfg
.dfs_order
)
71 fputs (";; DFS order: ", file
);
72 for (i
= 0; i
< n_basic_blocks
; i
++)
73 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
78 /* Dump the reverse completion node order. */
79 if (loops
->cfg
.rc_order
)
81 fputs (";; RC order: ", file
);
82 for (i
= 0; i
< n_basic_blocks
; i
++)
83 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
89 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
92 flow_loop_nested_p (outer
, loop
)
96 return sbitmap_a_subset_b_p (loop
->nodes
, outer
->nodes
);
99 /* Dump the loop information specified by LOOP to the stream FILE
100 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
103 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
)
104 const struct loop
*loop
;
106 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
109 if (! loop
|| ! loop
->header
)
112 if (loop
->first
->head
&& loop
->last
->end
)
113 fprintf (file
, ";;\n;; Loop %d (%d to %d):%s%s\n",
114 loop
->num
, INSN_UID (loop
->first
->head
),
115 INSN_UID (loop
->last
->end
),
116 loop
->shared
? " shared" : "", loop
->invalid
? " invalid" : "");
118 fprintf (file
, ";;\n;; Loop %d:%s%s\n", loop
->num
,
119 loop
->shared
? " shared" : "", loop
->invalid
? " invalid" : "");
121 fprintf (file
, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
122 loop
->header
->index
, loop
->latch
->index
,
123 loop
->pre_header
? loop
->pre_header
->index
: -1,
124 loop
->first
->index
, loop
->last
->index
);
125 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
126 loop
->depth
, loop
->level
,
127 (long) (loop
->outer
? loop
->outer
->num
: -1));
129 if (loop
->pre_header_edges
)
130 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
131 loop
->num_pre_header_edges
, file
);
133 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
134 loop
->num_entries
, file
);
135 fprintf (file
, ";; %d", loop
->num_nodes
);
136 flow_nodes_print (" nodes", loop
->nodes
, file
);
137 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
138 loop
->num_exits
, file
);
140 if (loop
->exits_doms
)
141 flow_nodes_print (";; exit doms", loop
->exits_doms
, file
);
144 loop_dump_aux (loop
, file
, verbose
);
147 /* Dump the loop information specified by LOOPS to the stream FILE,
148 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
151 flow_loops_dump (loops
, file
, loop_dump_aux
, verbose
)
152 const struct loops
*loops
;
154 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
160 num_loops
= loops
->num
;
161 if (! num_loops
|| ! file
)
164 fprintf (file
, ";; %d loops found, %d levels\n", num_loops
, loops
->levels
);
165 for (i
= 0; i
< num_loops
; i
++)
167 struct loop
*loop
= &loops
->array
[i
];
169 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
171 for (j
= 0; j
< i
; j
++)
173 struct loop
*oloop
= &loops
->array
[j
];
175 if (loop
->header
== oloop
->header
)
180 smaller
= loop
->num_nodes
< oloop
->num_nodes
;
182 /* If the union of LOOP and OLOOP is different than
183 the larger of LOOP and OLOOP then LOOP and OLOOP
185 disjoint
= ! flow_loop_nested_p (smaller
? loop
: oloop
,
186 smaller
? oloop
: loop
);
188 ";; loop header %d shared by loops %d, %d %s\n",
189 loop
->header
->index
, i
, j
,
190 disjoint
? "disjoint" : "nested");
196 flow_loops_cfg_dump (loops
, file
);
199 /* Free all the memory allocated for LOOPS. */
202 flow_loops_free (loops
)
212 /* Free the loop descriptors. */
213 for (i
= 0; i
< loops
->num
; i
++)
215 struct loop
*loop
= &loops
->array
[i
];
217 if (loop
->pre_header_edges
)
218 free (loop
->pre_header_edges
);
220 sbitmap_free (loop
->nodes
);
221 if (loop
->entry_edges
)
222 free (loop
->entry_edges
);
223 if (loop
->exit_edges
)
224 free (loop
->exit_edges
);
225 if (loop
->exits_doms
)
226 sbitmap_free (loop
->exits_doms
);
233 sbitmap_vector_free (loops
->cfg
.dom
);
235 if (loops
->cfg
.dfs_order
)
236 free (loops
->cfg
.dfs_order
);
238 if (loops
->shared_headers
)
239 sbitmap_free (loops
->shared_headers
);
243 /* Find the entry edges into the loop with header HEADER and nodes
244 NODES and store in ENTRY_EDGES array. Return the number of entry
245 edges from the loop. */
248 flow_loop_entry_edges_find (header
, nodes
, entry_edges
)
259 for (e
= header
->pred
; e
; e
= e
->pred_next
)
261 basic_block src
= e
->src
;
263 if (src
== ENTRY_BLOCK_PTR
|| ! TEST_BIT (nodes
, src
->index
))
270 *entry_edges
= (edge
*) xmalloc (num_entries
* sizeof (edge
));
273 for (e
= header
->pred
; e
; e
= e
->pred_next
)
275 basic_block src
= e
->src
;
277 if (src
== ENTRY_BLOCK_PTR
|| ! TEST_BIT (nodes
, src
->index
))
278 (*entry_edges
)[num_entries
++] = e
;
284 /* Find the exit edges from the loop using the bitmap of loop nodes
285 NODES and store in EXIT_EDGES array. Return the number of
286 exit edges from the loop. */
289 flow_loop_exit_edges_find (nodes
, exit_edges
)
299 /* Check all nodes within the loop to see if there are any
300 successors not in the loop. Note that a node may have multiple
301 exiting edges ????? A node can have one jumping edge and one fallthru
302 edge so only one of these can exit the loop. */
304 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
305 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
307 basic_block dest
= e
->dest
;
309 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
317 *exit_edges
= (edge
*) xmalloc (num_exits
* sizeof (edge
));
319 /* Store all exiting edges into an array. */
321 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
322 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
324 basic_block dest
= e
->dest
;
326 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
327 (*exit_edges
)[num_exits
++] = e
;
334 /* Find the nodes contained within the loop with header HEADER and
335 latch LATCH and store in NODES. Return the number of nodes within
339 flow_loop_nodes_find (header
, latch
, nodes
)
348 stack
= (basic_block
*) xmalloc (n_basic_blocks
* sizeof (basic_block
));
351 /* Start with only the loop header in the set of loop nodes. */
352 sbitmap_zero (nodes
);
353 SET_BIT (nodes
, header
->index
);
355 header
->loop_depth
++;
357 /* Push the loop latch on to the stack. */
358 if (! TEST_BIT (nodes
, latch
->index
))
360 SET_BIT (nodes
, latch
->index
);
372 for (e
= node
->pred
; e
; e
= e
->pred_next
)
374 basic_block ancestor
= e
->src
;
376 /* If each ancestor not marked as part of loop, add to set of
377 loop nodes and push on to stack. */
378 if (ancestor
!= ENTRY_BLOCK_PTR
379 && ! TEST_BIT (nodes
, ancestor
->index
))
381 SET_BIT (nodes
, ancestor
->index
);
382 ancestor
->loop_depth
++;
384 stack
[sp
++] = ancestor
;
392 /* Find the root node of the loop pre-header extended basic block and
393 the edges along the trace from the root node to the loop header. */
396 flow_loop_pre_header_scan (loop
)
403 loop
->num_pre_header_edges
= 0;
404 if (loop
->num_entries
!= 1)
407 ebb
= loop
->entry_edges
[0]->src
;
408 if (ebb
== ENTRY_BLOCK_PTR
)
411 /* Count number of edges along trace from loop header to
412 root of pre-header extended basic block. Usually this is
413 only one or two edges. */
414 for (num
= 1; ebb
->pred
->src
!= ENTRY_BLOCK_PTR
&& ! ebb
->pred
->pred_next
;
416 ebb
= ebb
->pred
->src
;
418 loop
->pre_header_edges
= (edge
*) xmalloc (num
* sizeof (edge
));
419 loop
->num_pre_header_edges
= num
;
421 /* Store edges in order that they are followed. The source of the first edge
422 is the root node of the pre-header extended basic block and the
423 destination of the last last edge is the loop header. */
424 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
425 loop
->pre_header_edges
[--num
] = e
;
428 /* Return the block for the pre-header of the loop with header
429 HEADER where DOM specifies the dominator information. Return NULL if
430 there is no pre-header. */
433 flow_loop_pre_header_find (header
, dom
)
437 basic_block pre_header
;
440 /* If block p is a predecessor of the header and is the only block
441 that the header does not dominate, then it is the pre-header. */
443 for (e
= header
->pred
; e
; e
= e
->pred_next
)
445 basic_block node
= e
->src
;
447 if (node
!= ENTRY_BLOCK_PTR
448 && ! TEST_BIT (dom
[node
->index
], header
->index
))
450 if (pre_header
== NULL
)
454 /* There are multiple edges into the header from outside
455 the loop so there is no pre-header block. */
465 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
466 previously added. The insertion algorithm assumes that the loops
467 are added in the order found by a depth first search of the CFG. */
470 flow_loop_tree_node_add (prevloop
, loop
)
471 struct loop
*prevloop
;
475 if (flow_loop_nested_p (prevloop
, loop
))
477 prevloop
->inner
= loop
;
478 loop
->outer
= prevloop
;
482 for (; prevloop
->outer
; prevloop
= prevloop
->outer
)
483 if (flow_loop_nested_p (prevloop
->outer
, loop
))
485 prevloop
->next
= loop
;
486 loop
->outer
= prevloop
->outer
;
490 prevloop
->next
= loop
;
494 /* Build the loop hierarchy tree for LOOPS. */
497 flow_loops_tree_build (loops
)
503 num_loops
= loops
->num
;
507 /* Root the loop hierarchy tree with the first loop found.
508 Since we used a depth first search this should be the
510 loops
->tree_root
= &loops
->array
[0];
511 loops
->tree_root
->outer
= loops
->tree_root
->inner
512 = loops
->tree_root
->next
= NULL
;
514 /* Add the remaining loops to the tree. */
515 for (i
= 1; i
< num_loops
; i
++)
516 flow_loop_tree_node_add (&loops
->array
[i
- 1], &loops
->array
[i
]);
519 /* Helper function to compute loop nesting depth and enclosed loop level
520 for the natural loop specified by LOOP at the loop depth DEPTH.
521 Returns the loop level. */
524 flow_loop_level_compute (loop
, depth
)
534 /* Traverse loop tree assigning depth and computing level as the
535 maximum level of all the inner loops of this loop. The loop
536 level is equivalent to the height of the loop in the loop tree
537 and corresponds to the number of enclosed loop levels (including
539 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
541 int ilevel
= flow_loop_level_compute (inner
, depth
+ 1) + 1;
543 level
= MAX (ilevel
, level
);
551 /* Compute the loop nesting depth and enclosed loop level for the loop
552 hierarchy tree specified by LOOPS. Return the maximum enclosed loop
556 flow_loops_level_compute (loops
)
563 /* Traverse all the outer level loops. */
564 for (loop
= loops
->tree_root
; loop
; loop
= loop
->next
)
566 level
= flow_loop_level_compute (loop
, 1);
567 levels
= MAX (levels
, level
);
573 /* Scan a single natural loop specified by LOOP collecting information
574 about it specified by FLAGS. */
577 flow_loop_scan (loops
, loop
, flags
)
582 /* Determine prerequisites. */
583 if ((flags
& LOOP_EXITS_DOMS
) && ! loop
->exit_edges
)
584 flags
|= LOOP_EXIT_EDGES
;
586 if (flags
& LOOP_ENTRY_EDGES
)
587 /* Find edges which enter the loop header. Note that the entry edges
588 should only enter the header of a natural loop. */
589 loop
->num_entries
= flow_loop_entry_edges_find (loop
->header
, loop
->nodes
,
592 if (flags
& LOOP_EXIT_EDGES
)
593 /* Find edges which exit the loop. */
595 = flow_loop_exit_edges_find (loop
->nodes
, &loop
->exit_edges
);
597 if (flags
& LOOP_EXITS_DOMS
)
601 /* Determine which loop nodes dominate all the exits
603 loop
->exits_doms
= sbitmap_alloc (last_basic_block
);
604 sbitmap_copy (loop
->exits_doms
, loop
->nodes
);
605 for (j
= 0; j
< loop
->num_exits
; j
++)
606 sbitmap_a_and_b (loop
->exits_doms
, loop
->exits_doms
,
607 loops
->cfg
.dom
[loop
->exit_edges
[j
]->src
->index
]);
609 /* The header of a natural loop must dominate
611 if (! TEST_BIT (loop
->exits_doms
, loop
->header
->index
))
615 if (flags
& LOOP_PRE_HEADER
)
617 /* Look to see if the loop has a pre-header node. */
619 = flow_loop_pre_header_find (loop
->header
, loops
->cfg
.dom
);
621 /* Find the blocks within the extended basic block of
622 the loop pre-header. */
623 flow_loop_pre_header_scan (loop
);
629 /* Find all the natural loops in the function and save in LOOPS structure and
630 recalculate loop_depth information in basic block structures. FLAGS
631 controls which loop information is collected. Return the number of natural
635 flow_loops_find (loops
, flags
)
649 /* This function cannot be repeatedly called with different
650 flags to build up the loop information. The loop tree
651 must always be built if this function is called. */
652 if (! (flags
& LOOP_TREE
))
655 memset (loops
, 0, sizeof *loops
);
657 /* Taking care of this degenerate case makes the rest of
658 this code simpler. */
659 if (n_basic_blocks
== 0)
665 /* Compute the dominators. */
666 dom
= sbitmap_vector_alloc (last_basic_block
, last_basic_block
);
667 calculate_dominance_info (NULL
, dom
, CDI_DOMINATORS
);
669 /* Count the number of loop edges (back edges). This should be the
670 same as the number of natural loops. */
674 header
->loop_depth
= 0;
676 for (e
= header
->pred
; e
; e
= e
->pred_next
)
678 basic_block latch
= e
->src
;
680 /* Look for back edges where a predecessor is dominated
681 by this block. A natural loop has a single entry
682 node (header) that dominates all the nodes in the
683 loop. It also has single back edge to the header
684 from a latch node. Note that multiple natural loops
685 may share the same header. */
686 if (latch
!= ENTRY_BLOCK_PTR
&& TEST_BIT (dom
[latch
->index
], header
->index
))
693 /* Compute depth first search order of the CFG so that outer
694 natural loops will be found before inner natural loops. */
695 dfs_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
696 rc_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
697 flow_depth_first_order_compute (dfs_order
, rc_order
);
699 /* Save CFG derived information to avoid recomputing it. */
700 loops
->cfg
.dom
= dom
;
701 loops
->cfg
.dfs_order
= dfs_order
;
702 loops
->cfg
.rc_order
= rc_order
;
704 /* Allocate loop structures. */
706 = (struct loop
*) xcalloc (num_loops
, sizeof (struct loop
));
708 headers
= sbitmap_alloc (last_basic_block
);
709 sbitmap_zero (headers
);
711 loops
->shared_headers
= sbitmap_alloc (last_basic_block
);
712 sbitmap_zero (loops
->shared_headers
);
714 /* Find and record information about all the natural loops
717 for (b
= n_basic_blocks
- 1; b
>= 0; b
--)
721 /* Search the nodes of the CFG in reverse completion order
722 so that we can find outer loops first. */
723 latch
= BASIC_BLOCK (rc_order
[b
]);
725 /* Look for all the possible headers for this latch block. */
726 for (e
= latch
->succ
; e
; e
= e
->succ_next
)
728 basic_block header
= e
->dest
;
730 /* Look for forward edges where this block is dominated by
731 a successor of this block. A natural loop has a single
732 entry node (header) that dominates all the nodes in the
733 loop. It also has single back edge to the header from a
734 latch node. Note that multiple natural loops may share
736 if (header
!= EXIT_BLOCK_PTR
737 && TEST_BIT (dom
[latch
->index
], header
->index
))
741 loop
= loops
->array
+ num_loops
;
743 loop
->header
= header
;
745 loop
->num
= num_loops
;
752 for (i
= 0; i
< num_loops
; i
++)
754 struct loop
*loop
= &loops
->array
[i
];
756 /* Keep track of blocks that are loop headers so
757 that we can tell which loops should be merged. */
758 if (TEST_BIT (headers
, loop
->header
->index
))
759 SET_BIT (loops
->shared_headers
, loop
->header
->index
);
760 SET_BIT (headers
, loop
->header
->index
);
762 /* Find nodes contained within the loop. */
763 loop
->nodes
= sbitmap_alloc (last_basic_block
);
765 = flow_loop_nodes_find (loop
->header
, loop
->latch
, loop
->nodes
);
767 /* Compute first and last blocks within the loop.
768 These are often the same as the loop header and
769 loop latch respectively, but this is not always
772 = BASIC_BLOCK (sbitmap_first_set_bit (loop
->nodes
));
774 = BASIC_BLOCK (sbitmap_last_set_bit (loop
->nodes
));
776 flow_loop_scan (loops
, loop
, flags
);
779 /* Natural loops with shared headers may either be disjoint or
780 nested. Disjoint loops with shared headers cannot be inner
781 loops and should be merged. For now just mark loops that share
783 for (i
= 0; i
< num_loops
; i
++)
784 if (TEST_BIT (loops
->shared_headers
, loops
->array
[i
].header
->index
))
785 loops
->array
[i
].shared
= 1;
787 sbitmap_free (headers
);
790 sbitmap_vector_free (dom
);
792 loops
->num
= num_loops
;
794 /* Build the loop hierarchy tree. */
795 flow_loops_tree_build (loops
);
797 /* Assign the loop nesting depth and enclosed loop level for each
799 loops
->levels
= flow_loops_level_compute (loops
);
804 /* Update the information regarding the loops in the CFG
805 specified by LOOPS. */
808 flow_loops_update (loops
, flags
)
812 /* One day we may want to update the current loop data. For now
813 throw away the old stuff and rebuild what we need. */
815 flow_loops_free (loops
);
817 return flow_loops_find (loops
, flags
);
820 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
823 flow_loop_outside_edge_p (loop
, e
)
824 const struct loop
*loop
;
827 if (e
->dest
!= loop
->header
)
830 return (e
->src
== ENTRY_BLOCK_PTR
)
831 || ! TEST_BIT (loop
->nodes
, e
->src
->index
);