1 /* Loop optimizer initialization routines.
2 Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "cfglayout.h"
30
31 static void fixup_loop_exit_succesor (basic_block, basic_block);
32
33 /* Initialize loop optimizer. */
34
35 struct loops *
loop_optimizer_init(FILE * dumpfile)36 loop_optimizer_init (FILE *dumpfile)
37 {
38 struct loops *loops = xcalloc (1, sizeof (struct loops));
39 edge e;
40
41 /* Initialize structures for layout changes. */
42 cfg_layout_initialize (0);
43
44 /* Avoid annoying special cases of edges going to exit
45 block. */
46 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
47 if ((e->flags & EDGE_FALLTHRU) && e->src->succ->succ_next)
48 split_edge (e);
49
50 /* Find the loops. */
51
52 if (flow_loops_find (loops, LOOP_TREE) <= 1)
53 {
54 basic_block bb;
55
56 /* No loops. */
57 flow_loops_free (loops);
58 free_dominance_info (CDI_DOMINATORS);
59 free (loops);
60
61 /* Make chain. */
62 FOR_EACH_BB (bb)
63 if (bb->next_bb != EXIT_BLOCK_PTR)
64 bb->rbi->next = bb->next_bb;
65 cfg_layout_finalize ();
66 return NULL;
67 }
68
69 /* Not going to update these. */
70 free (loops->cfg.rc_order);
71 loops->cfg.rc_order = NULL;
72 free (loops->cfg.dfs_order);
73 loops->cfg.dfs_order = NULL;
74
75 /* Create pre-headers. */
76 create_preheaders (loops, CP_SIMPLE_PREHEADERS);
77
78 /* Force all latches to have only single successor. */
79 force_single_succ_latches (loops);
80
81 /* Mark irreducible loops. */
82 mark_irreducible_loops (loops);
83
84 /* Dump loops. */
85 flow_loops_dump (loops, dumpfile, NULL, 1);
86
87 #ifdef ENABLE_CHECKING
88 verify_dominators (CDI_DOMINATORS);
89 verify_loop_structure (loops);
90 #endif
91
92 return loops;
93 }
94
95 /* The first basic block is moved after the second in the reorder chain. */
96 static void
fixup_loop_exit_succesor(basic_block exit_succ,basic_block latch)97 fixup_loop_exit_succesor (basic_block exit_succ, basic_block latch)
98 {
99 basic_block bb = exit_succ;
100 basic_block bb1 = latch;
101
102 if (!(bb && bb->rbi->next))
103 return;
104
105 if (!bb1)
106 return;
107
108
109 if (bb && bb->rbi->next)
110 {
111 basic_block c = ENTRY_BLOCK_PTR->next_bb;
112
113 while (c->rbi->next != bb)
114 c = c->rbi->next;
115
116 c->rbi->next = bb->rbi->next;
117 }
118
119 if(bb1->rbi->next == NULL)
120 {
121 bb1->rbi->next=bb;
122 bb->rbi->next=NULL;
123 }
124 else
125
126 {
127 basic_block tmp;
128
129 tmp = bb1->rbi->next;
130 bb1->rbi->next = bb;
131 bb->rbi->next = tmp;
132 }
133 }
134
135 /* Finalize loop optimizer. */
136 void
loop_optimizer_finalize(struct loops * loops,FILE * dumpfile)137 loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
138 {
139 basic_block bb;
140 unsigned int i;
141
142 /* Finalize layout changes. */
143 /* Make chain. */
144 FOR_EACH_BB (bb)
145 if (bb->next_bb != EXIT_BLOCK_PTR)
146 bb->rbi->next = bb->next_bb;
147
148 /* Another dump. */
149 flow_loops_dump (loops, dumpfile, NULL, 1);
150
151 /* For loops ending with a branch and count instruction, move the basic
152 block found before the unrolling on the fallthru path of this branch,
153 after the unrolled code. This will allow branch simplification. */
154 for (i = 1; i < loops->num; i++)
155 {
156 struct loop *loop = loops->parray[i];
157 struct loop_desc *desc;
158 basic_block loop_real_latch, bb, bb_exit;
159 edge e;
160
161 if (loop == NULL)
162 continue;
163 if (!loop->simple)
164 continue;
165 if (!loop->has_desc)
166 continue;
167
168 if (loop->lpt_decision.decision != LPT_UNROLL_RUNTIME)
169 continue;
170
171 desc = &loop->desc;
172 if (desc == NULL)
173 continue;
174 if (loop->latch->pred == NULL)
175 continue;
176
177 loop_real_latch = loop->latch->pred->src;
178
179
180 if (desc->postincr)
181 continue;
182 if (!is_bct_cond (BB_END (loop_real_latch)))
183 continue;
184
185 for (e = loop_real_latch->succ; e ; e = e->succ_next)
186 if (e->flags & EDGE_FALLTHRU)
187 break;
188
189 if (e == NULL)
190 continue;
191
192 bb_exit = e->dest;
193
194 bb = NULL;
195
196 /* Leave the case of the bb_exit falling through to exit to
197 fixed_fallthru_exit_predecessor */
198 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
199 if (e->flags & EDGE_FALLTHRU)
200 bb = e->src;
201
202 if (bb_exit == bb)
203 continue;
204
205 fixup_loop_exit_succesor (bb_exit, loop->latch);
206 }
207
208 /* Clean up. */
209 flow_loops_free (loops);
210 free_dominance_info (CDI_DOMINATORS);
211 free (loops);
212
213 /* Finalize changes. */
214 cfg_layout_finalize ();
215
216 /* Checking. */
217 #ifdef ENABLE_CHECKING
218 verify_flow_info ();
219 #endif
220 }
221