gcc/
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blob0be9142561e078ce0932ed8f82cb280b065cd72d
1 /* Loop unswitching.
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 "gimplify.h"
40 #include "gimple-ssa.h"
41 #include "tree-cfg.h"
42 #include "tree-phinodes.h"
43 #include "ssa-iterators.h"
44 #include "tree-ssa-loop-niter.h"
45 #include "tree-ssa-loop.h"
46 #include "tree-into-ssa.h"
47 #include "cfgloop.h"
48 #include "params.h"
49 #include "tree-pass.h"
50 #include "tree-inline.h"
52 /* This file implements the loop unswitching, i.e. transformation of loops like
54 while (A)
56 if (inv)
61 if (!inv)
65 where inv is the loop invariant, into
67 if (inv)
69 while (A)
75 else
77 while (A)
84 Inv is considered invariant iff the values it compares are both invariant;
85 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
86 shape. */
88 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
89 static bool tree_unswitch_single_loop (struct loop *, int);
90 static tree tree_may_unswitch_on (basic_block, struct loop *);
92 /* Main entry point. Perform loop unswitching on all suitable loops. */
94 unsigned int
95 tree_ssa_unswitch_loops (void)
97 struct loop *loop;
98 bool changed = false;
99 HOST_WIDE_INT iterations;
101 /* Go through inner loops (only original ones). */
102 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
104 if (dump_file && (dump_flags & TDF_DETAILS))
105 fprintf (dump_file, ";; Considering loop %d\n", loop->num);
107 /* Do not unswitch in cold regions. */
108 if (optimize_loop_for_size_p (loop))
110 if (dump_file && (dump_flags & TDF_DETAILS))
111 fprintf (dump_file, ";; Not unswitching cold loops\n");
112 continue;
115 /* The loop should not be too large, to limit code growth. */
116 if (tree_num_loop_insns (loop, &eni_size_weights)
117 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
119 if (dump_file && (dump_flags & TDF_DETAILS))
120 fprintf (dump_file, ";; Not unswitching, loop too big\n");
121 continue;
124 /* If the loop is not expected to iterate, there is no need
125 for unswitching. */
126 iterations = estimated_loop_iterations_int (loop);
127 if (iterations >= 0 && iterations <= 1)
129 if (dump_file && (dump_flags & TDF_DETAILS))
130 fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n");
131 continue;
134 changed |= tree_unswitch_single_loop (loop, 0);
137 if (changed)
138 return TODO_cleanup_cfg;
139 return 0;
142 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
143 basic blocks (for what it means see comments below). */
145 static tree
146 tree_may_unswitch_on (basic_block bb, struct loop *loop)
148 gimple last, def;
149 gcond *stmt;
150 tree cond, use;
151 basic_block def_bb;
152 ssa_op_iter iter;
154 /* BB must end in a simple conditional jump. */
155 last = last_stmt (bb);
156 if (!last || gimple_code (last) != GIMPLE_COND)
157 return NULL_TREE;
158 stmt = as_a <gcond *> (last);
160 /* To keep the things simple, we do not directly remove the conditions,
161 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
162 loop where we would unswitch again on such a condition. */
163 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
164 return NULL_TREE;
166 /* Condition must be invariant. */
167 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
169 def = SSA_NAME_DEF_STMT (use);
170 def_bb = gimple_bb (def);
171 if (def_bb
172 && flow_bb_inside_loop_p (loop, def_bb))
173 return NULL_TREE;
176 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
177 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
179 return cond;
182 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
183 simplish (sufficient to prevent us from duplicating loop in unswitching
184 unnecessarily). */
186 static tree
187 simplify_using_entry_checks (struct loop *loop, tree cond)
189 edge e = loop_preheader_edge (loop);
190 gimple stmt;
192 while (1)
194 stmt = last_stmt (e->src);
195 if (stmt
196 && gimple_code (stmt) == GIMPLE_COND
197 && gimple_cond_code (stmt) == TREE_CODE (cond)
198 && operand_equal_p (gimple_cond_lhs (stmt),
199 TREE_OPERAND (cond, 0), 0)
200 && operand_equal_p (gimple_cond_rhs (stmt),
201 TREE_OPERAND (cond, 1), 0))
202 return (e->flags & EDGE_TRUE_VALUE
203 ? boolean_true_node
204 : boolean_false_node);
206 if (!single_pred_p (e->src))
207 return cond;
209 e = single_pred_edge (e->src);
210 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
211 return cond;
215 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
216 it to grow too much, it is too easy to create example on that the code would
217 grow exponentially. */
219 static bool
220 tree_unswitch_single_loop (struct loop *loop, int num)
222 basic_block *bbs;
223 struct loop *nloop;
224 unsigned i, found;
225 tree cond = NULL_TREE;
226 gimple stmt;
227 bool changed = false;
229 i = 0;
230 bbs = get_loop_body (loop);
231 found = loop->num_nodes;
233 while (1)
235 /* Find a bb to unswitch on. */
236 for (; i < loop->num_nodes; i++)
237 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
238 break;
240 if (i == loop->num_nodes)
242 if (dump_file
243 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
244 && (dump_flags & TDF_DETAILS))
245 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
247 if (found == loop->num_nodes)
249 free (bbs);
250 return changed;
252 break;
255 cond = simplify_using_entry_checks (loop, cond);
256 stmt = last_stmt (bbs[i]);
257 if (integer_nonzerop (cond))
259 /* Remove false path. */
260 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
261 boolean_true_node);
262 changed = true;
264 else if (integer_zerop (cond))
266 /* Remove true path. */
267 gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
268 boolean_false_node);
269 changed = true;
271 /* Do not unswitch too much. */
272 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
274 i++;
275 continue;
277 /* In nested tree_unswitch_single_loop first optimize all conditions
278 using entry checks, then discover still reachable blocks in the
279 loop and find the condition only among those still reachable bbs. */
280 else if (num != 0)
282 if (found == loop->num_nodes)
283 found = i;
284 i++;
285 continue;
287 else
289 found = i;
290 break;
293 update_stmt (stmt);
294 i++;
297 if (num != 0)
299 basic_block *tos, *worklist;
301 /* When called recursively, first do a quick discovery
302 of reachable bbs after the above changes and only
303 consider conditions in still reachable bbs. */
304 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
306 for (i = 0; i < loop->num_nodes; i++)
307 bbs[i]->flags &= ~BB_REACHABLE;
309 /* Start with marking header. */
310 *tos++ = bbs[0];
311 bbs[0]->flags |= BB_REACHABLE;
313 /* Iterate: find everything reachable from what we've already seen
314 within the same innermost loop. Don't look through false edges
315 if condition is always true or true edges if condition is
316 always false. */
317 while (tos != worklist)
319 basic_block b = *--tos;
320 edge e;
321 edge_iterator ei;
322 int flags = 0;
324 if (EDGE_COUNT (b->succs) == 2)
326 gimple stmt = last_stmt (b);
327 if (stmt
328 && gimple_code (stmt) == GIMPLE_COND)
330 gcond *cond_stmt = as_a <gcond *> (stmt);
331 if (gimple_cond_true_p (cond_stmt))
332 flags = EDGE_FALSE_VALUE;
333 else if (gimple_cond_false_p (cond_stmt))
334 flags = EDGE_TRUE_VALUE;
338 FOR_EACH_EDGE (e, ei, b->succs)
340 basic_block dest = e->dest;
342 if (dest->loop_father == loop
343 && !(dest->flags & BB_REACHABLE)
344 && !(e->flags & flags))
346 *tos++ = dest;
347 dest->flags |= BB_REACHABLE;
352 free (worklist);
354 /* Find a bb to unswitch on. */
355 for (; found < loop->num_nodes; found++)
356 if ((bbs[found]->flags & BB_REACHABLE)
357 && (cond = tree_may_unswitch_on (bbs[found], loop)))
358 break;
360 if (found == loop->num_nodes)
362 free (bbs);
363 return changed;
367 if (dump_file && (dump_flags & TDF_DETAILS))
368 fprintf (dump_file, ";; Unswitching loop\n");
370 initialize_original_copy_tables ();
371 /* Unswitch the loop on this condition. */
372 nloop = tree_unswitch_loop (loop, bbs[found], cond);
373 if (!nloop)
375 free_original_copy_tables ();
376 free (bbs);
377 return changed;
380 /* Update the SSA form after unswitching. */
381 update_ssa (TODO_update_ssa);
382 free_original_copy_tables ();
384 /* Invoke itself on modified loops. */
385 tree_unswitch_single_loop (nloop, num + 1);
386 tree_unswitch_single_loop (loop, num + 1);
387 free (bbs);
388 return true;
391 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
392 unswitching of innermost loops. COND is the condition determining which
393 loop is entered -- the new loop is entered if COND is true. Returns NULL
394 if impossible, new loop otherwise. */
396 static struct loop *
397 tree_unswitch_loop (struct loop *loop,
398 basic_block unswitch_on, tree cond)
400 unsigned prob_true;
401 edge edge_true, edge_false;
403 /* Some sanity checking. */
404 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
405 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
406 gcc_assert (loop->inner == NULL);
408 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
409 prob_true = edge_true->probability;
410 return loop_version (loop, unshare_expr (cond),
411 NULL, prob_true, prob_true,
412 REG_BR_PROB_BASE - prob_true, false);
415 /* Loop unswitching pass. */
417 namespace {
419 const pass_data pass_data_tree_unswitch =
421 GIMPLE_PASS, /* type */
422 "unswitch", /* name */
423 OPTGROUP_LOOP, /* optinfo_flags */
424 TV_TREE_LOOP_UNSWITCH, /* tv_id */
425 PROP_cfg, /* properties_required */
426 0, /* properties_provided */
427 0, /* properties_destroyed */
428 0, /* todo_flags_start */
429 0, /* todo_flags_finish */
432 class pass_tree_unswitch : public gimple_opt_pass
434 public:
435 pass_tree_unswitch (gcc::context *ctxt)
436 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
439 /* opt_pass methods: */
440 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
441 virtual unsigned int execute (function *);
443 }; // class pass_tree_unswitch
445 unsigned int
446 pass_tree_unswitch::execute (function *fun)
448 if (number_of_loops (fun) <= 1)
449 return 0;
451 return tree_ssa_unswitch_loops ();
454 } // anon namespace
456 gimple_opt_pass *
457 make_pass_tree_unswitch (gcc::context *ctxt)
459 return new pass_tree_unswitch (ctxt);