* config/alpha/alpha.c, config/alpha/alpha.md,
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blobb9bd3724ba9a1a79f09ffd16677b17d5f8b4bc89
1 /* Loop unswitching.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "domwalk.h"
37 #include "params.h"
38 #include "tree-pass.h"
39 #include "tree-inline.h"
41 /* This file implements the loop unswitching, i.e. transformation of loops like
43 while (A)
45 if (inv)
50 if (!inv)
54 where inv is the loop invariant, into
56 if (inv)
58 while (A)
64 else
66 while (A)
73 Inv is considered invariant iff the values it compares are both invariant;
74 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
75 shape. */
77 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
78 static bool tree_unswitch_single_loop (struct loop *, int);
79 static tree tree_may_unswitch_on (basic_block, struct loop *);
81 /* Main entry point. Perform loop unswitching on all suitable loops. */
83 unsigned int
84 tree_ssa_unswitch_loops (void)
86 loop_iterator li;
87 struct loop *loop;
88 bool changed = false;
90 /* Go through inner loops (only original ones). */
91 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
93 changed |= tree_unswitch_single_loop (loop, 0);
96 if (changed)
97 return TODO_cleanup_cfg;
98 return 0;
101 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
102 basic blocks (for what it means see comments below). */
104 static tree
105 tree_may_unswitch_on (basic_block bb, struct loop *loop)
107 tree stmt, def, cond, use;
108 basic_block def_bb;
109 ssa_op_iter iter;
111 /* BB must end in a simple conditional jump. */
112 stmt = last_stmt (bb);
113 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
114 return NULL_TREE;
116 /* Condition must be invariant. */
117 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
119 def = SSA_NAME_DEF_STMT (use);
120 def_bb = bb_for_stmt (def);
121 if (def_bb
122 && flow_bb_inside_loop_p (loop, def_bb))
123 return NULL_TREE;
126 cond = COND_EXPR_COND (stmt);
127 /* To keep the things simple, we do not directly remove the conditions,
128 but just replace tests with 0/1. Prevent the infinite loop where we
129 would unswitch again on such a condition. */
130 if (integer_zerop (cond) || integer_nonzerop (cond))
131 return NULL_TREE;
133 return cond;
136 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
137 simplish (sufficient to prevent us from duplicating loop in unswitching
138 unnecessarily). */
140 static tree
141 simplify_using_entry_checks (struct loop *loop, tree cond)
143 edge e = loop_preheader_edge (loop);
144 tree stmt;
146 while (1)
148 stmt = last_stmt (e->src);
149 if (stmt
150 && TREE_CODE (stmt) == COND_EXPR
151 && operand_equal_p (COND_EXPR_COND (stmt), cond, 0))
152 return (e->flags & EDGE_TRUE_VALUE
153 ? boolean_true_node
154 : boolean_false_node);
156 if (!single_pred_p (e->src))
157 return cond;
159 e = single_pred_edge (e->src);
160 if (e->src == ENTRY_BLOCK_PTR)
161 return cond;
165 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
166 it to grow too much, it is too easy to create example on that the code would
167 grow exponentially. */
169 static bool
170 tree_unswitch_single_loop (struct loop *loop, int num)
172 basic_block *bbs;
173 struct loop *nloop;
174 unsigned i;
175 tree cond = NULL_TREE, stmt;
176 bool changed = false;
178 /* Do not unswitch too much. */
179 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
181 if (dump_file && (dump_flags & TDF_DETAILS))
182 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
183 return false;
186 /* Only unswitch innermost loops. */
187 if (loop->inner)
189 if (dump_file && (dump_flags & TDF_DETAILS))
190 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
191 return false;
194 /* The loop should not be too large, to limit code growth. */
195 if (tree_num_loop_insns (loop, &eni_size_weights)
196 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
198 if (dump_file && (dump_flags & TDF_DETAILS))
199 fprintf (dump_file, ";; Not unswitching, loop too big\n");
200 return false;
203 i = 0;
204 bbs = get_loop_body (loop);
206 while (1)
208 /* Find a bb to unswitch on. */
209 for (; i < loop->num_nodes; i++)
210 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
211 break;
213 if (i == loop->num_nodes)
215 free (bbs);
216 return changed;
219 cond = simplify_using_entry_checks (loop, cond);
220 stmt = last_stmt (bbs[i]);
221 if (integer_nonzerop (cond))
223 /* Remove false path. */
224 COND_EXPR_COND (stmt) = boolean_true_node;
225 changed = true;
227 else if (integer_zerop (cond))
229 /* Remove true path. */
230 COND_EXPR_COND (stmt) = boolean_false_node;
231 changed = true;
233 else
234 break;
236 update_stmt (stmt);
237 i++;
240 if (dump_file && (dump_flags & TDF_DETAILS))
241 fprintf (dump_file, ";; Unswitching loop\n");
243 initialize_original_copy_tables ();
244 /* Unswitch the loop on this condition. */
245 nloop = tree_unswitch_loop (loop, bbs[i], cond);
246 if (!nloop)
248 free_original_copy_tables ();
249 free (bbs);
250 return changed;
253 /* Update the SSA form after unswitching. */
254 update_ssa (TODO_update_ssa);
255 free_original_copy_tables ();
257 /* Invoke itself on modified loops. */
258 tree_unswitch_single_loop (nloop, num + 1);
259 tree_unswitch_single_loop (loop, num + 1);
260 free (bbs);
261 return true;
264 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
265 unswitching of innermost loops. COND is the condition determining which
266 loop is entered -- the new loop is entered if COND is true. Returns NULL
267 if impossible, new loop otherwise. */
269 static struct loop *
270 tree_unswitch_loop (struct loop *loop,
271 basic_block unswitch_on, tree cond)
273 unsigned prob_true;
274 edge edge_true, edge_false;
276 /* Some sanity checking. */
277 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
278 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
279 gcc_assert (loop->inner == NULL);
281 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
282 prob_true = edge_true->probability;
283 return loop_version (loop, unshare_expr (cond),
284 NULL, prob_true, prob_true,
285 REG_BR_PROB_BASE - prob_true, false);