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
, sbitmap
));
35 static void flow_loop_pre_header_scan
PARAMS ((struct loop
*));
36 static basic_block flow_loop_pre_header_find
PARAMS ((basic_block
,
38 static void flow_loop_tree_node_add
PARAMS ((struct loop
*, struct loop
*));
39 static void flow_loops_tree_build
PARAMS ((struct loops
*));
40 static int flow_loop_level_compute
PARAMS ((struct loop
*, int));
41 static int flow_loops_level_compute
PARAMS ((struct loops
*));
43 /* Dump loop related CFG information. */
46 flow_loops_cfg_dump (loops
, file
)
47 const struct loops
*loops
;
52 if (! loops
->num
|| ! file
|| ! loops
->cfg
.dom
)
55 for (i
= 0; i
< n_basic_blocks
; i
++)
59 fprintf (file
, ";; %d succs { ", i
);
60 for (succ
= BASIC_BLOCK (i
)->succ
; succ
; succ
= succ
->succ_next
)
61 fprintf (file
, "%d ", succ
->dest
->index
);
62 flow_nodes_print ("} dom", loops
->cfg
.dom
[i
], file
);
65 /* Dump the DFS node order. */
66 if (loops
->cfg
.dfs_order
)
68 fputs (";; DFS order: ", file
);
69 for (i
= 0; i
< n_basic_blocks
; i
++)
70 fprintf (file
, "%d ", loops
->cfg
.dfs_order
[i
]);
73 /* Dump the reverse completion node order. */
74 if (loops
->cfg
.rc_order
)
76 fputs (";; RC order: ", file
);
77 for (i
= 0; i
< n_basic_blocks
; i
++)
78 fprintf (file
, "%d ", loops
->cfg
.rc_order
[i
]);
83 /* Return non-zero if the nodes of LOOP are a subset of OUTER. */
86 flow_loop_nested_p (outer
, loop
)
90 return sbitmap_a_subset_b_p (loop
->nodes
, outer
->nodes
);
93 /* Dump the loop information specified by LOOP to the stream FILE
94 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
97 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
)
98 const struct loop
*loop
;
100 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
103 if (! loop
|| ! loop
->header
)
106 if (loop
->first
->head
&& loop
->last
->end
)
107 fprintf (file
, ";;\n;; Loop %d (%d to %d):%s%s\n",
108 loop
->num
, INSN_UID (loop
->first
->head
),
109 INSN_UID (loop
->last
->end
),
110 loop
->shared
? " shared" : "",
111 loop
->invalid
? " invalid" : "");
113 fprintf (file
, ";;\n;; Loop %d:%s%s\n", loop
->num
,
114 loop
->shared
? " shared" : "",
115 loop
->invalid
? " invalid" : "");
117 fprintf (file
, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
118 loop
->header
->index
, loop
->latch
->index
,
119 loop
->pre_header
? loop
->pre_header
->index
: -1,
120 loop
->first
->index
, loop
->last
->index
);
121 fprintf (file
, ";; depth %d, level %d, outer %ld\n",
122 loop
->depth
, loop
->level
,
123 (long) (loop
->outer
? loop
->outer
->num
: -1));
125 if (loop
->pre_header_edges
)
126 flow_edge_list_print (";; pre-header edges", loop
->pre_header_edges
,
127 loop
->num_pre_header_edges
, file
);
128 flow_edge_list_print (";; entry edges", loop
->entry_edges
,
129 loop
->num_entries
, file
);
130 fprintf (file
, ";; %d", loop
->num_nodes
);
131 flow_nodes_print (" nodes", loop
->nodes
, file
);
132 flow_edge_list_print (";; exit edges", loop
->exit_edges
,
133 loop
->num_exits
, file
);
134 if (loop
->exits_doms
)
135 flow_nodes_print (";; exit doms", loop
->exits_doms
, file
);
137 loop_dump_aux (loop
, file
, verbose
);
140 /* Dump the loop information specified by LOOPS to the stream FILE,
141 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
144 flow_loops_dump (loops
, file
, loop_dump_aux
, verbose
)
145 const struct loops
*loops
;
147 void (*loop_dump_aux
) PARAMS((const struct loop
*, FILE *, int));
153 num_loops
= loops
->num
;
154 if (! num_loops
|| ! file
)
157 fprintf (file
, ";; %d loops found, %d levels\n",
158 num_loops
, loops
->levels
);
160 for (i
= 0; i
< num_loops
; i
++)
162 struct loop
*loop
= &loops
->array
[i
];
164 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
170 for (j
= 0; j
< i
; j
++)
172 struct loop
*oloop
= &loops
->array
[j
];
174 if (loop
->header
== oloop
->header
)
179 smaller
= loop
->num_nodes
< oloop
->num_nodes
;
181 /* If the union of LOOP and OLOOP is different than
182 the larger of LOOP and OLOOP then LOOP and OLOOP
184 disjoint
= ! flow_loop_nested_p (smaller
? loop
: oloop
,
185 smaller
? oloop
: loop
);
187 ";; loop header %d shared by loops %d, %d %s\n",
188 loop
->header
->index
, i
, j
,
189 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
);
232 sbitmap_vector_free (loops
->cfg
.dom
);
233 if (loops
->cfg
.dfs_order
)
234 free (loops
->cfg
.dfs_order
);
236 if (loops
->shared_headers
)
237 sbitmap_free (loops
->shared_headers
);
241 /* Find the entry edges into the loop with header HEADER and nodes
242 NODES and store in ENTRY_EDGES array. Return the number of entry
243 edges from the loop. */
246 flow_loop_entry_edges_find (header
, nodes
, entry_edges
)
257 for (e
= header
->pred
; e
; e
= e
->pred_next
)
259 basic_block src
= e
->src
;
261 if (src
== ENTRY_BLOCK_PTR
|| ! TEST_BIT (nodes
, src
->index
))
268 *entry_edges
= (edge
*) xmalloc (num_entries
* sizeof (edge
*));
271 for (e
= header
->pred
; e
; e
= e
->pred_next
)
273 basic_block src
= e
->src
;
275 if (src
== ENTRY_BLOCK_PTR
|| ! TEST_BIT (nodes
, src
->index
))
276 (*entry_edges
)[num_entries
++] = e
;
282 /* Find the exit edges from the loop using the bitmap of loop nodes
283 NODES and store in EXIT_EDGES array. Return the number of
284 exit edges from the loop. */
287 flow_loop_exit_edges_find (nodes
, exit_edges
)
297 /* Check all nodes within the loop to see if there are any
298 successors not in the loop. Note that a node may have multiple
299 exiting edges ????? A node can have one jumping edge and one fallthru
300 edge so only one of these can exit the loop. */
302 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
303 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
305 basic_block dest
= e
->dest
;
307 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
315 *exit_edges
= (edge
*) xmalloc (num_exits
* sizeof (edge
*));
317 /* Store all exiting edges into an array. */
319 EXECUTE_IF_SET_IN_SBITMAP (nodes
, 0, node
, {
320 for (e
= BASIC_BLOCK (node
)->succ
; e
; e
= e
->succ_next
)
322 basic_block dest
= e
->dest
;
324 if (dest
== EXIT_BLOCK_PTR
|| ! TEST_BIT (nodes
, dest
->index
))
325 (*exit_edges
)[num_exits
++] = e
;
332 /* Find the nodes contained within the loop with header HEADER and
333 latch LATCH and store in NODES. Return the number of nodes within
337 flow_loop_nodes_find (header
, latch
, nodes
)
346 stack
= (basic_block
*) xmalloc (n_basic_blocks
* sizeof (basic_block
));
349 /* Start with only the loop header in the set of loop nodes. */
350 sbitmap_zero (nodes
);
351 SET_BIT (nodes
, header
->index
);
353 header
->loop_depth
++;
355 /* Push the loop latch on to the stack. */
356 if (! TEST_BIT (nodes
, latch
->index
))
358 SET_BIT (nodes
, latch
->index
);
370 for (e
= node
->pred
; e
; e
= e
->pred_next
)
372 basic_block ancestor
= e
->src
;
374 /* If each ancestor not marked as part of loop, add to set of
375 loop nodes and push on to stack. */
376 if (ancestor
!= ENTRY_BLOCK_PTR
377 && ! TEST_BIT (nodes
, ancestor
->index
))
379 SET_BIT (nodes
, ancestor
->index
);
380 ancestor
->loop_depth
++;
382 stack
[sp
++] = ancestor
;
390 /* Find the root node of the loop pre-header extended basic block and
391 the edges along the trace from the root node to the loop header. */
394 flow_loop_pre_header_scan (loop
)
400 loop
->num_pre_header_edges
= 0;
402 if (loop
->num_entries
!= 1)
405 ebb
= loop
->entry_edges
[0]->src
;
407 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. */
415 while (ebb
->pred
->src
!= ENTRY_BLOCK_PTR
&& ! ebb
->pred
->pred_next
)
417 ebb
= ebb
->pred
->src
;
421 loop
->pre_header_edges
= (edge
*) xmalloc (num
* sizeof (edge
*));
422 loop
->num_pre_header_edges
= num
;
424 /* Store edges in order that they are followed. The source
425 of the first edge is the root node of the pre-header extended
426 basic block and the destination of the last last edge is
428 for (e
= loop
->entry_edges
[0]; num
; e
= e
->src
->pred
)
430 loop
->pre_header_edges
[--num
] = e
;
435 /* Return the block for the pre-header of the loop with header
436 HEADER where DOM specifies the dominator information. Return NULL if
437 there is no pre-header. */
440 flow_loop_pre_header_find (header
, dom
)
444 basic_block pre_header
;
447 /* If block p is a predecessor of the header and is the only block
448 that the header does not dominate, then it is the pre-header. */
450 for (e
= header
->pred
; e
; e
= e
->pred_next
)
452 basic_block node
= e
->src
;
454 if (node
!= ENTRY_BLOCK_PTR
455 && ! TEST_BIT (dom
[node
->index
], header
->index
))
457 if (pre_header
== NULL
)
461 /* There are multiple edges into the header from outside
462 the loop so there is no pre-header block. */
471 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
472 previously added. The insertion algorithm assumes that the loops
473 are added in the order found by a depth first search of the CFG. */
476 flow_loop_tree_node_add (prevloop
, loop
)
477 struct loop
*prevloop
;
481 if (flow_loop_nested_p (prevloop
, loop
))
483 prevloop
->inner
= loop
;
484 loop
->outer
= prevloop
;
488 while (prevloop
->outer
)
490 if (flow_loop_nested_p (prevloop
->outer
, loop
))
492 prevloop
->next
= loop
;
493 loop
->outer
= prevloop
->outer
;
496 prevloop
= prevloop
->outer
;
499 prevloop
->next
= loop
;
503 /* Build the loop hierarchy tree for LOOPS. */
506 flow_loops_tree_build (loops
)
512 num_loops
= loops
->num
;
516 /* Root the loop hierarchy tree with the first loop found.
517 Since we used a depth first search this should be the
519 loops
->tree_root
= &loops
->array
[0];
520 loops
->tree_root
->outer
= loops
->tree_root
->inner
= loops
->tree_root
->next
= NULL
;
522 /* Add the remaining loops to the tree. */
523 for (i
= 1; i
< num_loops
; i
++)
524 flow_loop_tree_node_add (&loops
->array
[i
- 1], &loops
->array
[i
]);
527 /* Helper function to compute loop nesting depth and enclosed loop level
528 for the natural loop specified by LOOP at the loop depth DEPTH.
529 Returns the loop level. */
532 flow_loop_level_compute (loop
, depth
)
542 /* Traverse loop tree assigning depth and computing level as the
543 maximum level of all the inner loops of this loop. The loop
544 level is equivalent to the height of the loop in the loop tree
545 and corresponds to the number of enclosed loop levels (including
547 for (inner
= loop
->inner
; inner
; inner
= inner
->next
)
551 ilevel
= flow_loop_level_compute (inner
, depth
+ 1) + 1;
561 /* Compute the loop nesting depth and enclosed loop level for the loop
562 hierarchy tree specfied by LOOPS. Return the maximum enclosed loop
566 flow_loops_level_compute (loops
)
573 /* Traverse all the outer level loops. */
574 for (loop
= loops
->tree_root
; loop
; loop
= loop
->next
)
576 level
= flow_loop_level_compute (loop
, 1);
583 /* Scan a single natural loop specified by LOOP collecting information
584 about it specified by FLAGS. */
587 flow_loop_scan (loops
, loop
, flags
)
592 /* Determine prerequisites. */
593 if ((flags
& LOOP_EXITS_DOMS
) && ! loop
->exit_edges
)
594 flags
|= LOOP_EXIT_EDGES
;
596 if (flags
& LOOP_ENTRY_EDGES
)
598 /* Find edges which enter the loop header.
599 Note that the entry edges should only
600 enter the header of a natural loop. */
602 = flow_loop_entry_edges_find (loop
->header
,
607 if (flags
& LOOP_EXIT_EDGES
)
609 /* Find edges which exit the loop. */
611 = flow_loop_exit_edges_find (loop
->nodes
,
615 if (flags
& LOOP_EXITS_DOMS
)
619 /* Determine which loop nodes dominate all the exits
621 loop
->exits_doms
= sbitmap_alloc (n_basic_blocks
);
622 sbitmap_copy (loop
->exits_doms
, loop
->nodes
);
623 for (j
= 0; j
< loop
->num_exits
; j
++)
624 sbitmap_a_and_b (loop
->exits_doms
, loop
->exits_doms
,
625 loops
->cfg
.dom
[loop
->exit_edges
[j
]->src
->index
]);
627 /* The header of a natural loop must dominate
629 if (! TEST_BIT (loop
->exits_doms
, loop
->header
->index
))
633 if (flags
& LOOP_PRE_HEADER
)
635 /* Look to see if the loop has a pre-header node. */
637 = flow_loop_pre_header_find (loop
->header
, loops
->cfg
.dom
);
639 /* Find the blocks within the extended basic block of
640 the loop pre-header. */
641 flow_loop_pre_header_scan (loop
);
646 /* Find all the natural loops in the function and save in LOOPS structure
647 and recalculate loop_depth information in basic block structures.
648 FLAGS controls which loop information is collected.
649 Return the number of natural loops found. */
652 flow_loops_find (loops
, flags
)
665 /* This function cannot be repeatedly called with different
666 flags to build up the loop information. The loop tree
667 must always be built if this function is called. */
668 if (! (flags
& LOOP_TREE
))
671 memset (loops
, 0, sizeof (*loops
));
673 /* Taking care of this degenerate case makes the rest of
674 this code simpler. */
675 if (n_basic_blocks
== 0)
681 /* Compute the dominators. */
682 dom
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
683 calculate_dominance_info (NULL
, dom
, CDI_DOMINATORS
);
685 /* Count the number of loop edges (back edges). This should be the
686 same as the number of natural loops. */
689 for (b
= 0; b
< n_basic_blocks
; b
++)
693 header
= BASIC_BLOCK (b
);
694 header
->loop_depth
= 0;
696 for (e
= header
->pred
; e
; e
= e
->pred_next
)
698 basic_block latch
= e
->src
;
700 /* Look for back edges where a predecessor is dominated
701 by this block. A natural loop has a single entry
702 node (header) that dominates all the nodes in the
703 loop. It also has single back edge to the header
704 from a latch node. Note that multiple natural loops
705 may share the same header. */
706 if (b
!= header
->index
)
709 if (latch
!= ENTRY_BLOCK_PTR
&& TEST_BIT (dom
[latch
->index
], b
))
716 /* Compute depth first search order of the CFG so that outer
717 natural loops will be found before inner natural loops. */
718 dfs_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
719 rc_order
= (int *) xmalloc (n_basic_blocks
* sizeof (int));
720 flow_depth_first_order_compute (dfs_order
, rc_order
);
722 /* Save CFG derived information to avoid recomputing it. */
723 loops
->cfg
.dom
= dom
;
724 loops
->cfg
.dfs_order
= dfs_order
;
725 loops
->cfg
.rc_order
= rc_order
;
727 /* Allocate loop structures. */
729 = (struct loop
*) xcalloc (num_loops
, sizeof (struct loop
));
731 headers
= sbitmap_alloc (n_basic_blocks
);
732 sbitmap_zero (headers
);
734 loops
->shared_headers
= sbitmap_alloc (n_basic_blocks
);
735 sbitmap_zero (loops
->shared_headers
);
737 /* Find and record information about all the natural loops
740 for (b
= 0; b
< n_basic_blocks
; b
++)
744 /* Search the nodes of the CFG in reverse completion order
745 so that we can find outer loops first. */
746 header
= BASIC_BLOCK (rc_order
[b
]);
748 /* Look for all the possible latch blocks for this header. */
749 for (e
= header
->pred
; e
; e
= e
->pred_next
)
751 basic_block latch
= e
->src
;
753 /* Look for back edges where a predecessor is dominated
754 by this block. A natural loop has a single entry
755 node (header) that dominates all the nodes in the
756 loop. It also has single back edge to the header
757 from a latch node. Note that multiple natural loops
758 may share the same header. */
759 if (latch
!= ENTRY_BLOCK_PTR
760 && TEST_BIT (dom
[latch
->index
], header
->index
))
764 loop
= loops
->array
+ num_loops
;
766 loop
->header
= header
;
768 loop
->num
= num_loops
;
775 for (i
= 0; i
< num_loops
; i
++)
777 struct loop
*loop
= &loops
->array
[i
];
779 /* Keep track of blocks that are loop headers so
780 that we can tell which loops should be merged. */
781 if (TEST_BIT (headers
, loop
->header
->index
))
782 SET_BIT (loops
->shared_headers
, loop
->header
->index
);
783 SET_BIT (headers
, loop
->header
->index
);
785 /* Find nodes contained within the loop. */
786 loop
->nodes
= sbitmap_alloc (n_basic_blocks
);
788 = flow_loop_nodes_find (loop
->header
, loop
->latch
, loop
->nodes
);
790 /* Compute first and last blocks within the loop.
791 These are often the same as the loop header and
792 loop latch respectively, but this is not always
795 = BASIC_BLOCK (sbitmap_first_set_bit (loop
->nodes
));
797 = BASIC_BLOCK (sbitmap_last_set_bit (loop
->nodes
));
799 flow_loop_scan (loops
, loop
, flags
);
802 /* Natural loops with shared headers may either be disjoint or
803 nested. Disjoint loops with shared headers cannot be inner
804 loops and should be merged. For now just mark loops that share
806 for (i
= 0; i
< num_loops
; i
++)
807 if (TEST_BIT (loops
->shared_headers
, loops
->array
[i
].header
->index
))
808 loops
->array
[i
].shared
= 1;
810 sbitmap_free (headers
);
814 sbitmap_vector_free (dom
);
817 loops
->num
= num_loops
;
819 /* Build the loop hierarchy tree. */
820 flow_loops_tree_build (loops
);
822 /* Assign the loop nesting depth and enclosed loop level for each
824 loops
->levels
= flow_loops_level_compute (loops
);
829 /* Update the information regarding the loops in the CFG
830 specified by LOOPS. */
832 flow_loops_update (loops
, flags
)
836 /* One day we may want to update the current loop data. For now
837 throw away the old stuff and rebuild what we need. */
839 flow_loops_free (loops
);
841 return flow_loops_find (loops
, flags
);
844 /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
847 flow_loop_outside_edge_p (loop
, e
)
848 const struct loop
*loop
;
851 if (e
->dest
!= loop
->header
)
853 return (e
->src
== ENTRY_BLOCK_PTR
) || ! TEST_BIT (loop
->nodes
, e
->src
->index
);