* gcc.dg/atomic/c11-atomic-exec-5.c (dg-additional-options): Use
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blob06f4a12d1d44577f48b669fa086f7dc9ef03babb
1 /* Loop unswitching.
2 Copyright (C) 2004-2014 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 "tree.h"
25 #include "tm_p.h"
26 #include "basic-block.h"
27 #include "tree-ssa-alias.h"
28 #include "internal-fn.h"
29 #include "gimple-expr.h"
30 #include "is-a.h"
31 #include "gimple.h"
32 #include "gimplify.h"
33 #include "gimple-ssa.h"
34 #include "tree-cfg.h"
35 #include "tree-phinodes.h"
36 #include "ssa-iterators.h"
37 #include "tree-ssa-loop-niter.h"
38 #include "tree-ssa-loop.h"
39 #include "tree-into-ssa.h"
40 #include "cfgloop.h"
41 #include "params.h"
42 #include "tree-pass.h"
43 #include "tree-inline.h"
45 /* This file implements the loop unswitching, i.e. transformation of loops like
47 while (A)
49 if (inv)
54 if (!inv)
58 where inv is the loop invariant, into
60 if (inv)
62 while (A)
68 else
70 while (A)
77 Inv is considered invariant iff the values it compares are both invariant;
78 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
79 shape. */
81 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
82 static bool tree_unswitch_single_loop (struct loop *, int);
83 static tree tree_may_unswitch_on (basic_block, struct loop *);
85 /* Main entry point. Perform loop unswitching on all suitable loops. */
87 unsigned int
88 tree_ssa_unswitch_loops (void)
90 struct loop *loop;
91 bool changed = false;
92 HOST_WIDE_INT iterations;
94 /* Go through inner loops (only original ones). */
95 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
97 if (dump_file && (dump_flags & TDF_DETAILS))
98 fprintf (dump_file, ";; Considering loop %d\n", loop->num);
100 /* Do not unswitch in cold regions. */
101 if (optimize_loop_for_size_p (loop))
103 if (dump_file && (dump_flags & TDF_DETAILS))
104 fprintf (dump_file, ";; Not unswitching cold loops\n");
105 continue;
108 /* The loop should not be too large, to limit code growth. */
109 if (tree_num_loop_insns (loop, &eni_size_weights)
110 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
112 if (dump_file && (dump_flags & TDF_DETAILS))
113 fprintf (dump_file, ";; Not unswitching, loop too big\n");
114 continue;
117 /* If the loop is not expected to iterate, there is no need
118 for unswitching. */
119 iterations = estimated_loop_iterations_int (loop);
120 if (iterations >= 0 && iterations <= 1)
122 if (dump_file && (dump_flags & TDF_DETAILS))
123 fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n");
124 continue;
127 changed |= tree_unswitch_single_loop (loop, 0);
130 if (changed)
131 return TODO_cleanup_cfg;
132 return 0;
135 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
136 basic blocks (for what it means see comments below). */
138 static tree
139 tree_may_unswitch_on (basic_block bb, struct loop *loop)
141 gimple stmt, def;
142 tree cond, use;
143 basic_block def_bb;
144 ssa_op_iter iter;
146 /* BB must end in a simple conditional jump. */
147 stmt = last_stmt (bb);
148 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
149 return NULL_TREE;
151 /* To keep the things simple, we do not directly remove the conditions,
152 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
153 loop where we would unswitch again on such a condition. */
154 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
155 return NULL_TREE;
157 /* Condition must be invariant. */
158 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
160 def = SSA_NAME_DEF_STMT (use);
161 def_bb = gimple_bb (def);
162 if (def_bb
163 && flow_bb_inside_loop_p (loop, def_bb))
164 return NULL_TREE;
167 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
168 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
170 return cond;
173 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
174 simplish (sufficient to prevent us from duplicating loop in unswitching
175 unnecessarily). */
177 static tree
178 simplify_using_entry_checks (struct loop *loop, tree cond)
180 edge e = loop_preheader_edge (loop);
181 gimple stmt;
183 while (1)
185 stmt = last_stmt (e->src);
186 if (stmt
187 && gimple_code (stmt) == GIMPLE_COND
188 && gimple_cond_code (stmt) == TREE_CODE (cond)
189 && operand_equal_p (gimple_cond_lhs (stmt),
190 TREE_OPERAND (cond, 0), 0)
191 && operand_equal_p (gimple_cond_rhs (stmt),
192 TREE_OPERAND (cond, 1), 0))
193 return (e->flags & EDGE_TRUE_VALUE
194 ? boolean_true_node
195 : boolean_false_node);
197 if (!single_pred_p (e->src))
198 return cond;
200 e = single_pred_edge (e->src);
201 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
202 return cond;
206 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
207 it to grow too much, it is too easy to create example on that the code would
208 grow exponentially. */
210 static bool
211 tree_unswitch_single_loop (struct loop *loop, int num)
213 basic_block *bbs;
214 struct loop *nloop;
215 unsigned i, found;
216 tree cond = NULL_TREE;
217 gimple stmt;
218 bool changed = false;
220 i = 0;
221 bbs = get_loop_body (loop);
222 found = loop->num_nodes;
224 while (1)
226 /* Find a bb to unswitch on. */
227 for (; i < loop->num_nodes; i++)
228 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
229 break;
231 if (i == loop->num_nodes)
233 if (dump_file
234 && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
235 && (dump_flags & TDF_DETAILS))
236 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
238 if (found == loop->num_nodes)
240 free (bbs);
241 return changed;
243 break;
246 cond = simplify_using_entry_checks (loop, cond);
247 stmt = last_stmt (bbs[i]);
248 if (integer_nonzerop (cond))
250 /* Remove false path. */
251 gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
252 changed = true;
254 else if (integer_zerop (cond))
256 /* Remove true path. */
257 gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
258 changed = true;
260 /* Do not unswitch too much. */
261 else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
263 i++;
264 continue;
266 /* In nested tree_unswitch_single_loop first optimize all conditions
267 using entry checks, then discover still reachable blocks in the
268 loop and find the condition only among those still reachable bbs. */
269 else if (num != 0)
271 if (found == loop->num_nodes)
272 found = i;
273 i++;
274 continue;
276 else
278 found = i;
279 break;
282 update_stmt (stmt);
283 i++;
286 if (num != 0)
288 basic_block *tos, *worklist;
290 /* When called recursively, first do a quick discovery
291 of reachable bbs after the above changes and only
292 consider conditions in still reachable bbs. */
293 tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
295 for (i = 0; i < loop->num_nodes; i++)
296 bbs[i]->flags &= ~BB_REACHABLE;
298 /* Start with marking header. */
299 *tos++ = bbs[0];
300 bbs[0]->flags |= BB_REACHABLE;
302 /* Iterate: find everything reachable from what we've already seen
303 within the same innermost loop. Don't look through false edges
304 if condition is always true or true edges if condition is
305 always false. */
306 while (tos != worklist)
308 basic_block b = *--tos;
309 edge e;
310 edge_iterator ei;
311 int flags = 0;
313 if (EDGE_COUNT (b->succs) == 2)
315 gimple stmt = last_stmt (b);
316 if (stmt
317 && gimple_code (stmt) == GIMPLE_COND)
319 if (gimple_cond_true_p (stmt))
320 flags = EDGE_FALSE_VALUE;
321 else if (gimple_cond_false_p (stmt))
322 flags = EDGE_TRUE_VALUE;
326 FOR_EACH_EDGE (e, ei, b->succs)
328 basic_block dest = e->dest;
330 if (dest->loop_father == loop
331 && !(dest->flags & BB_REACHABLE)
332 && !(e->flags & flags))
334 *tos++ = dest;
335 dest->flags |= BB_REACHABLE;
340 free (worklist);
342 /* Find a bb to unswitch on. */
343 for (; found < loop->num_nodes; found++)
344 if ((bbs[found]->flags & BB_REACHABLE)
345 && (cond = tree_may_unswitch_on (bbs[found], loop)))
346 break;
348 if (found == loop->num_nodes)
350 free (bbs);
351 return changed;
355 if (dump_file && (dump_flags & TDF_DETAILS))
356 fprintf (dump_file, ";; Unswitching loop\n");
358 initialize_original_copy_tables ();
359 /* Unswitch the loop on this condition. */
360 nloop = tree_unswitch_loop (loop, bbs[found], cond);
361 if (!nloop)
363 free_original_copy_tables ();
364 free (bbs);
365 return changed;
368 /* Update the SSA form after unswitching. */
369 update_ssa (TODO_update_ssa);
370 free_original_copy_tables ();
372 /* Invoke itself on modified loops. */
373 tree_unswitch_single_loop (nloop, num + 1);
374 tree_unswitch_single_loop (loop, num + 1);
375 free (bbs);
376 return true;
379 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
380 unswitching of innermost loops. COND is the condition determining which
381 loop is entered -- the new loop is entered if COND is true. Returns NULL
382 if impossible, new loop otherwise. */
384 static struct loop *
385 tree_unswitch_loop (struct loop *loop,
386 basic_block unswitch_on, tree cond)
388 unsigned prob_true;
389 edge edge_true, edge_false;
391 /* Some sanity checking. */
392 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
393 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
394 gcc_assert (loop->inner == NULL);
396 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
397 prob_true = edge_true->probability;
398 return loop_version (loop, unshare_expr (cond),
399 NULL, prob_true, prob_true,
400 REG_BR_PROB_BASE - prob_true, false);
403 /* Loop unswitching pass. */
405 namespace {
407 const pass_data pass_data_tree_unswitch =
409 GIMPLE_PASS, /* type */
410 "unswitch", /* name */
411 OPTGROUP_LOOP, /* optinfo_flags */
412 TV_TREE_LOOP_UNSWITCH, /* tv_id */
413 PROP_cfg, /* properties_required */
414 0, /* properties_provided */
415 0, /* properties_destroyed */
416 0, /* todo_flags_start */
417 0, /* todo_flags_finish */
420 class pass_tree_unswitch : public gimple_opt_pass
422 public:
423 pass_tree_unswitch (gcc::context *ctxt)
424 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
427 /* opt_pass methods: */
428 virtual bool gate (function *) { return flag_unswitch_loops != 0; }
429 virtual unsigned int execute (function *);
431 }; // class pass_tree_unswitch
433 unsigned int
434 pass_tree_unswitch::execute (function *fun)
436 if (number_of_loops (fun) <= 1)
437 return 0;
439 return tree_ssa_unswitch_loops ();
442 } // anon namespace
444 gimple_opt_pass *
445 make_pass_tree_unswitch (gcc::context *ctxt)
447 return new pass_tree_unswitch (ctxt);