|
0
|
1 /* Loop header copying on trees.
|
|
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 3, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY 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 COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "tm_p.h"
|
|
|
27 #include "hard-reg-set.h"
|
|
|
28 #include "basic-block.h"
|
|
|
29 #include "output.h"
|
|
|
30 #include "diagnostic.h"
|
|
|
31 #include "tree-flow.h"
|
|
|
32 #include "tree-dump.h"
|
|
|
33 #include "tree-pass.h"
|
|
|
34 #include "timevar.h"
|
|
|
35 #include "cfgloop.h"
|
|
|
36 #include "tree-inline.h"
|
|
|
37 #include "flags.h"
|
|
|
38 #include "tree-inline.h"
|
|
|
39
|
|
|
40 /* Duplicates headers of loops if they are small enough, so that the statements
|
|
|
41 in the loop body are always executed when the loop is entered. This
|
|
|
42 increases effectiveness of code motion optimizations, and reduces the need
|
|
|
43 for loop preconditioning. */
|
|
|
44
|
|
|
45 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
|
|
|
46 instructions should be duplicated, limit is decreased by the actual
|
|
|
47 amount. */
|
|
|
48
|
|
|
49 static bool
|
|
|
50 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
|
|
|
51 int *limit)
|
|
|
52 {
|
|
|
53 gimple_stmt_iterator bsi;
|
|
|
54 gimple last;
|
|
|
55
|
|
|
56 /* Do not copy one block more than once (we do not really want to do
|
|
|
57 loop peeling here). */
|
|
|
58 if (header->aux)
|
|
|
59 return false;
|
|
|
60
|
|
|
61 /* Loop header copying usually increases size of the code. This used not to
|
|
|
62 be true, since quite often it is possible to verify that the condition is
|
|
|
63 satisfied in the first iteration and therefore to eliminate it. Jump
|
|
|
64 threading handles these cases now. */
|
|
|
65 if (optimize_loop_for_size_p (loop))
|
|
|
66 return false;
|
|
|
67
|
|
|
68 gcc_assert (EDGE_COUNT (header->succs) > 0);
|
|
|
69 if (single_succ_p (header))
|
|
|
70 return false;
|
|
|
71 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
|
|
|
72 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
|
|
|
73 return false;
|
|
|
74
|
|
|
75 /* If this is not the original loop header, we want it to have just
|
|
|
76 one predecessor in order to match the && pattern. */
|
|
|
77 if (header != loop->header && !single_pred_p (header))
|
|
|
78 return false;
|
|
|
79
|
|
|
80 last = last_stmt (header);
|
|
|
81 if (gimple_code (last) != GIMPLE_COND)
|
|
|
82 return false;
|
|
|
83
|
|
|
84 /* Approximately copy the conditions that used to be used in jump.c --
|
|
|
85 at most 20 insns and no calls. */
|
|
|
86 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
|
|
|
87 {
|
|
|
88 last = gsi_stmt (bsi);
|
|
|
89
|
|
|
90 if (gimple_code (last) == GIMPLE_LABEL)
|
|
|
91 continue;
|
|
|
92
|
|
|
93 if (is_gimple_call (last))
|
|
|
94 return false;
|
|
|
95
|
|
|
96 *limit -= estimate_num_insns (last, &eni_size_weights);
|
|
|
97 if (*limit < 0)
|
|
|
98 return false;
|
|
|
99 }
|
|
|
100
|
|
|
101 return true;
|
|
|
102 }
|
|
|
103
|
|
|
104 /* Checks whether LOOP is a do-while style loop. */
|
|
|
105
|
|
|
106 static bool
|
|
|
107 do_while_loop_p (struct loop *loop)
|
|
|
108 {
|
|
|
109 gimple stmt = last_stmt (loop->latch);
|
|
|
110
|
|
|
111 /* If the latch of the loop is not empty, it is not a do-while loop. */
|
|
|
112 if (stmt
|
|
|
113 && gimple_code (stmt) != GIMPLE_LABEL)
|
|
|
114 return false;
|
|
|
115
|
|
|
116 /* If the header contains just a condition, it is not a do-while loop. */
|
|
|
117 stmt = last_and_only_stmt (loop->header);
|
|
|
118 if (stmt
|
|
|
119 && gimple_code (stmt) == GIMPLE_COND)
|
|
|
120 return false;
|
|
|
121
|
|
|
122 return true;
|
|
|
123 }
|
|
|
124
|
|
|
125 /* For all loops, copy the condition at the end of the loop body in front
|
|
|
126 of the loop. This is beneficial since it increases efficiency of
|
|
|
127 code motion optimizations. It also saves one jump on entry to the loop. */
|
|
|
128
|
|
|
129 static unsigned int
|
|
|
130 copy_loop_headers (void)
|
|
|
131 {
|
|
|
132 loop_iterator li;
|
|
|
133 struct loop *loop;
|
|
|
134 basic_block header;
|
|
|
135 edge exit, entry;
|
|
|
136 basic_block *bbs, *copied_bbs;
|
|
|
137 unsigned n_bbs;
|
|
|
138 unsigned bbs_size;
|
|
|
139
|
|
|
140 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
|
|
|
141 | LOOPS_HAVE_SIMPLE_LATCHES);
|
|
|
142 if (number_of_loops () <= 1)
|
|
|
143 {
|
|
|
144 loop_optimizer_finalize ();
|
|
|
145 return 0;
|
|
|
146 }
|
|
|
147
|
|
|
148 #ifdef ENABLE_CHECKING
|
|
|
149 verify_loop_structure ();
|
|
|
150 #endif
|
|
|
151
|
|
|
152 bbs = XNEWVEC (basic_block, n_basic_blocks);
|
|
|
153 copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
|
|
|
154 bbs_size = n_basic_blocks;
|
|
|
155
|
|
|
156 FOR_EACH_LOOP (li, loop, 0)
|
|
|
157 {
|
|
|
158 /* Copy at most 20 insns. */
|
|
|
159 int limit = 20;
|
|
|
160
|
|
|
161 header = loop->header;
|
|
|
162
|
|
|
163 /* If the loop is already a do-while style one (either because it was
|
|
|
164 written as such, or because jump threading transformed it into one),
|
|
|
165 we might be in fact peeling the first iteration of the loop. This
|
|
|
166 in general is not a good idea. */
|
|
|
167 if (do_while_loop_p (loop))
|
|
|
168 continue;
|
|
|
169
|
|
|
170 /* Iterate the header copying up to limit; this takes care of the cases
|
|
|
171 like while (a && b) {...}, where we want to have both of the conditions
|
|
|
172 copied. TODO -- handle while (a || b) - like cases, by not requiring
|
|
|
173 the header to have just a single successor and copying up to
|
|
|
174 postdominator. */
|
|
|
175
|
|
|
176 exit = NULL;
|
|
|
177 n_bbs = 0;
|
|
|
178 while (should_duplicate_loop_header_p (header, loop, &limit))
|
|
|
179 {
|
|
|
180 /* Find a successor of header that is inside a loop; i.e. the new
|
|
|
181 header after the condition is copied. */
|
|
|
182 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
|
|
|
183 exit = EDGE_SUCC (header, 0);
|
|
|
184 else
|
|
|
185 exit = EDGE_SUCC (header, 1);
|
|
|
186 bbs[n_bbs++] = header;
|
|
|
187 gcc_assert (bbs_size > n_bbs);
|
|
|
188 header = exit->dest;
|
|
|
189 }
|
|
|
190
|
|
|
191 if (!exit)
|
|
|
192 continue;
|
|
|
193
|
|
|
194 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
195 fprintf (dump_file,
|
|
|
196 "Duplicating header of the loop %d up to edge %d->%d.\n",
|
|
|
197 loop->num, exit->src->index, exit->dest->index);
|
|
|
198
|
|
|
199 /* Ensure that the header will have just the latch as a predecessor
|
|
|
200 inside the loop. */
|
|
|
201 if (!single_pred_p (exit->dest))
|
|
|
202 exit = single_pred_edge (split_edge (exit));
|
|
|
203
|
|
|
204 entry = loop_preheader_edge (loop);
|
|
|
205
|
|
|
206 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
|
|
|
207 {
|
|
|
208 fprintf (dump_file, "Duplication failed.\n");
|
|
|
209 continue;
|
|
|
210 }
|
|
|
211
|
|
|
212 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
|
|
|
213 this copying can introduce a case where we rely on undefined
|
|
|
214 signed overflow to eliminate the preheader condition, because
|
|
|
215 we assume that "j < j + 10" is true. We don't want to warn
|
|
|
216 about that case for -Wstrict-overflow, because in general we
|
|
|
217 don't warn about overflow involving loops. Prevent the
|
|
|
218 warning by setting the no_warning flag in the condition. */
|
|
|
219 if (warn_strict_overflow > 0)
|
|
|
220 {
|
|
|
221 unsigned int i;
|
|
|
222
|
|
|
223 for (i = 0; i < n_bbs; ++i)
|
|
|
224 {
|
|
|
225 gimple_stmt_iterator bsi;
|
|
|
226
|
|
|
227 for (bsi = gsi_start_bb (copied_bbs[i]);
|
|
|
228 !gsi_end_p (bsi);
|
|
|
229 gsi_next (&bsi))
|
|
|
230 {
|
|
|
231 gimple stmt = gsi_stmt (bsi);
|
|
|
232 if (gimple_code (stmt) == GIMPLE_COND)
|
|
|
233 gimple_set_no_warning (stmt, true);
|
|
|
234 else if (is_gimple_assign (stmt))
|
|
|
235 {
|
|
|
236 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
|
|
|
237 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
|
|
|
238 gimple_set_no_warning (stmt, true);
|
|
|
239 }
|
|
|
240 }
|
|
|
241 }
|
|
|
242 }
|
|
|
243
|
|
|
244 /* Ensure that the latch and the preheader is simple (we know that they
|
|
|
245 are not now, since there was the loop exit condition. */
|
|
|
246 split_edge (loop_preheader_edge (loop));
|
|
|
247 split_edge (loop_latch_edge (loop));
|
|
|
248 }
|
|
|
249
|
|
|
250 free (bbs);
|
|
|
251 free (copied_bbs);
|
|
|
252
|
|
|
253 loop_optimizer_finalize ();
|
|
|
254 return 0;
|
|
|
255 }
|
|
|
256
|
|
|
257 static bool
|
|
|
258 gate_ch (void)
|
|
|
259 {
|
|
|
260 return flag_tree_ch != 0;
|
|
|
261 }
|
|
|
262
|
|
|
263 struct gimple_opt_pass pass_ch =
|
|
|
264 {
|
|
|
265 {
|
|
|
266 GIMPLE_PASS,
|
|
|
267 "ch", /* name */
|
|
|
268 gate_ch, /* gate */
|
|
|
269 copy_loop_headers, /* execute */
|
|
|
270 NULL, /* sub */
|
|
|
271 NULL, /* next */
|
|
|
272 0, /* static_pass_number */
|
|
|
273 TV_TREE_CH, /* tv_id */
|
|
|
274 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
275 0, /* properties_provided */
|
|
|
276 0, /* properties_destroyed */
|
|
|
277 0, /* todo_flags_start */
|
|
|
278 TODO_cleanup_cfg | TODO_dump_func
|
|
|
279 | TODO_verify_ssa /* todo_flags_finish */
|
|
|
280 }
|
|
|
281 };
|
