2015-06-23 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / tree-ssa-loop-ch.c
blob98534ba8f6cab7818c3072c4212196f2a2bbbdff
1 /* Loop header copying on trees.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "alias.h"
25 #include "symtab.h"
26 #include "tree.h"
27 #include "fold-const.h"
28 #include "tm_p.h"
29 #include "predict.h"
30 #include "hard-reg-set.h"
31 #include "function.h"
32 #include "dominance.h"
33 #include "cfg.h"
34 #include "basic-block.h"
35 #include "tree-ssa-alias.h"
36 #include "internal-fn.h"
37 #include "gimple-expr.h"
38 #include "gimple.h"
39 #include "gimple-iterator.h"
40 #include "gimple-ssa.h"
41 #include "tree-cfg.h"
42 #include "tree-into-ssa.h"
43 #include "tree-pass.h"
44 #include "cfgloop.h"
45 #include "tree-inline.h"
46 #include "flags.h"
47 #include "tree-ssa-scopedtables.h"
48 #include "tree-ssa-threadedge.h"
50 /* Duplicates headers of loops if they are small enough, so that the statements
51 in the loop body are always executed when the loop is entered. This
52 increases effectiveness of code motion optimizations, and reduces the need
53 for loop preconditioning. */
55 /* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
56 instructions should be duplicated, limit is decreased by the actual
57 amount. */
59 static bool
60 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
61 int *limit)
63 gimple_stmt_iterator bsi;
64 gimple last;
66 /* Do not copy one block more than once (we do not really want to do
67 loop peeling here). */
68 if (header->aux)
69 return false;
71 /* Loop header copying usually increases size of the code. This used not to
72 be true, since quite often it is possible to verify that the condition is
73 satisfied in the first iteration and therefore to eliminate it. Jump
74 threading handles these cases now. */
75 if (optimize_loop_for_size_p (loop))
76 return false;
78 gcc_assert (EDGE_COUNT (header->succs) > 0);
79 if (single_succ_p (header))
80 return false;
81 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
82 && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
83 return false;
85 /* If this is not the original loop header, we want it to have just
86 one predecessor in order to match the && pattern. */
87 if (header != loop->header && !single_pred_p (header))
88 return false;
90 last = last_stmt (header);
91 if (gimple_code (last) != GIMPLE_COND)
92 return false;
94 /* Approximately copy the conditions that used to be used in jump.c --
95 at most 20 insns and no calls. */
96 for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
98 last = gsi_stmt (bsi);
100 if (gimple_code (last) == GIMPLE_LABEL)
101 continue;
103 if (is_gimple_debug (last))
104 continue;
106 if (is_gimple_call (last))
107 return false;
109 *limit -= estimate_num_insns (last, &eni_size_weights);
110 if (*limit < 0)
111 return false;
114 return true;
117 /* Checks whether LOOP is a do-while style loop. */
119 static bool
120 do_while_loop_p (struct loop *loop)
122 gimple stmt = last_stmt (loop->latch);
124 /* If the latch of the loop is not empty, it is not a do-while loop. */
125 if (stmt
126 && gimple_code (stmt) != GIMPLE_LABEL)
127 return false;
129 /* If the header contains just a condition, it is not a do-while loop. */
130 stmt = last_and_only_stmt (loop->header);
131 if (stmt
132 && gimple_code (stmt) == GIMPLE_COND)
133 return false;
135 return true;
138 /* For all loops, copy the condition at the end of the loop body in front
139 of the loop. This is beneficial since it increases efficiency of
140 code motion optimizations. It also saves one jump on entry to the loop. */
142 namespace {
144 const pass_data pass_data_ch =
146 GIMPLE_PASS, /* type */
147 "ch", /* name */
148 OPTGROUP_LOOP, /* optinfo_flags */
149 TV_TREE_CH, /* tv_id */
150 ( PROP_cfg | PROP_ssa ), /* properties_required */
151 0, /* properties_provided */
152 0, /* properties_destroyed */
153 0, /* todo_flags_start */
154 0, /* todo_flags_finish */
157 class pass_ch : public gimple_opt_pass
159 public:
160 pass_ch (gcc::context *ctxt)
161 : gimple_opt_pass (pass_data_ch, ctxt)
164 /* opt_pass methods: */
165 virtual bool gate (function *) { return flag_tree_ch != 0; }
166 virtual unsigned int execute (function *);
168 }; // class pass_ch
170 unsigned int
171 pass_ch::execute (function *fun)
173 struct loop *loop;
174 basic_block header;
175 edge exit, entry;
176 basic_block *bbs, *copied_bbs;
177 unsigned n_bbs;
178 unsigned bbs_size;
179 bool changed = false;
181 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
182 | LOOPS_HAVE_SIMPLE_LATCHES);
183 if (number_of_loops (fun) <= 1)
185 loop_optimizer_finalize ();
186 return 0;
189 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
190 copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
191 bbs_size = n_basic_blocks_for_fn (fun);
193 FOR_EACH_LOOP (loop, 0)
195 /* Copy at most 20 insns. */
196 int limit = 20;
198 header = loop->header;
200 /* If the loop is already a do-while style one (either because it was
201 written as such, or because jump threading transformed it into one),
202 we might be in fact peeling the first iteration of the loop. This
203 in general is not a good idea. */
204 if (do_while_loop_p (loop))
205 continue;
207 /* Iterate the header copying up to limit; this takes care of the cases
208 like while (a && b) {...}, where we want to have both of the conditions
209 copied. TODO -- handle while (a || b) - like cases, by not requiring
210 the header to have just a single successor and copying up to
211 postdominator. */
213 exit = NULL;
214 n_bbs = 0;
215 while (should_duplicate_loop_header_p (header, loop, &limit))
217 /* Find a successor of header that is inside a loop; i.e. the new
218 header after the condition is copied. */
219 if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
220 exit = EDGE_SUCC (header, 0);
221 else
222 exit = EDGE_SUCC (header, 1);
223 bbs[n_bbs++] = header;
224 gcc_assert (bbs_size > n_bbs);
225 header = exit->dest;
228 if (!exit)
229 continue;
231 if (dump_file && (dump_flags & TDF_DETAILS))
232 fprintf (dump_file,
233 "Duplicating header of the loop %d up to edge %d->%d.\n",
234 loop->num, exit->src->index, exit->dest->index);
236 /* Ensure that the header will have just the latch as a predecessor
237 inside the loop. */
238 if (!single_pred_p (exit->dest))
239 exit = single_pred_edge (split_edge (exit));
241 entry = loop_preheader_edge (loop);
243 propagate_threaded_block_debug_into (exit->dest, entry->dest);
244 if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
245 true))
247 fprintf (dump_file, "Duplication failed.\n");
248 continue;
251 /* If the loop has the form "for (i = j; i < j + 10; i++)" then
252 this copying can introduce a case where we rely on undefined
253 signed overflow to eliminate the preheader condition, because
254 we assume that "j < j + 10" is true. We don't want to warn
255 about that case for -Wstrict-overflow, because in general we
256 don't warn about overflow involving loops. Prevent the
257 warning by setting the no_warning flag in the condition. */
258 if (warn_strict_overflow > 0)
260 unsigned int i;
262 for (i = 0; i < n_bbs; ++i)
264 gimple_stmt_iterator bsi;
266 for (bsi = gsi_start_bb (copied_bbs[i]);
267 !gsi_end_p (bsi);
268 gsi_next (&bsi))
270 gimple stmt = gsi_stmt (bsi);
271 if (gimple_code (stmt) == GIMPLE_COND)
272 gimple_set_no_warning (stmt, true);
273 else if (is_gimple_assign (stmt))
275 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
276 if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
277 gimple_set_no_warning (stmt, true);
283 /* Ensure that the latch and the preheader is simple (we know that they
284 are not now, since there was the loop exit condition. */
285 split_edge (loop_preheader_edge (loop));
286 split_edge (loop_latch_edge (loop));
288 changed = true;
291 update_ssa (TODO_update_ssa);
292 free (bbs);
293 free (copied_bbs);
295 loop_optimizer_finalize ();
296 return changed ? TODO_cleanup_cfg : 0;
299 } // anon namespace
301 gimple_opt_pass *
302 make_pass_ch (gcc::context *ctxt)
304 return new pass_ch (ctxt);