Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-unswitch.c
blob29fab9aed3170bef3232641775f387481744c777
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, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, 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"
40 /* This file implements the loop unswitching, i.e. transformation of loops like
42 while (A)
44 if (inv)
49 if (!inv)
53 where inv is the loop invariant, into
55 if (inv)
57 while (A)
63 else
65 while (A)
72 Inv is considered invariant iff the values it compares are both invariant;
73 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
74 shape. */
76 static struct loop *tree_unswitch_loop (struct loops *, struct loop *, basic_block,
77 tree);
78 static bool tree_unswitch_single_loop (struct loops *, 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 void
84 tree_ssa_unswitch_loops (struct loops *loops)
86 int i, num;
87 struct loop *loop;
88 bool changed = false;
90 /* Go through inner loops (only original ones). */
91 num = loops->num;
93 for (i = 1; i < num; i++)
95 /* Removed loop? */
96 loop = loops->parray[i];
97 if (!loop)
98 continue;
100 if (loop->inner)
101 continue;
103 changed |= tree_unswitch_single_loop (loops, loop, 0);
104 #ifdef ENABLE_CHECKING
105 verify_dominators (CDI_DOMINATORS);
106 verify_loop_structure (loops);
107 #endif
110 if (changed)
111 cleanup_tree_cfg_loop ();
114 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
115 basic blocks (for what it means see comments below). */
117 static tree
118 tree_may_unswitch_on (basic_block bb, struct loop *loop)
120 tree stmt, def, cond;
121 basic_block def_bb;
122 use_optype uses;
123 unsigned i;
125 /* BB must end in a simple conditional jump. */
126 stmt = last_stmt (bb);
127 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
128 return NULL_TREE;
130 /* Condition must be invariant. */
131 get_stmt_operands (stmt);
132 uses = STMT_USE_OPS (stmt);
133 for (i = 0; i < NUM_USES (uses); i++)
135 def = SSA_NAME_DEF_STMT (USE_OP (uses, i));
136 def_bb = bb_for_stmt (def);
137 if (def_bb
138 && flow_bb_inside_loop_p (loop, def_bb))
139 return NULL_TREE;
142 cond = COND_EXPR_COND (stmt);
143 /* To keep the things simple, we do not directly remove the conditions,
144 but just replace tests with 0/1. Prevent the infinite loop where we
145 would unswitch again on such a condition. */
146 if (integer_zerop (cond) || integer_nonzerop (cond))
147 return NULL_TREE;
149 return cond;
152 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
153 simplish (sufficient to prevent us from duplicating loop in unswitching
154 unnecessarily). */
156 static tree
157 simplify_using_entry_checks (struct loop *loop, tree cond)
159 edge e = loop_preheader_edge (loop);
160 tree stmt;
162 while (1)
164 stmt = last_stmt (e->src);
165 if (stmt
166 && TREE_CODE (stmt) == COND_EXPR
167 && operand_equal_p (COND_EXPR_COND (stmt), cond, 0))
168 return (e->flags & EDGE_TRUE_VALUE
169 ? boolean_true_node
170 : boolean_false_node);
172 if (!single_pred_p (e->src))
173 return cond;
175 e = single_pred_edge (e->src);
176 if (e->src == ENTRY_BLOCK_PTR)
177 return cond;
181 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
182 it to grow too much, it is too easy to create example on that the code would
183 grow exponentially. */
185 static bool
186 tree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num)
188 basic_block *bbs;
189 struct loop *nloop;
190 unsigned i;
191 tree cond = NULL_TREE, stmt;
192 bool changed = false;
194 /* Do not unswitch too much. */
195 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
197 if (dump_file && (dump_flags & TDF_DETAILS))
198 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
199 return false;
202 /* Only unswitch innermost loops. */
203 if (loop->inner)
205 if (dump_file && (dump_flags & TDF_DETAILS))
206 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
207 return false;
210 /* The loop should not be too large, to limit code growth. */
211 if (tree_num_loop_insns (loop)
212 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
214 if (dump_file && (dump_flags & TDF_DETAILS))
215 fprintf (dump_file, ";; Not unswitching, loop too big\n");
216 return false;
219 i = 0;
220 bbs = get_loop_body (loop);
222 while (1)
224 /* Find a bb to unswitch on. */
225 for (; i < loop->num_nodes; i++)
226 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
227 break;
229 if (i == loop->num_nodes)
231 free (bbs);
232 return changed;
235 cond = simplify_using_entry_checks (loop, cond);
236 stmt = last_stmt (bbs[i]);
237 if (integer_nonzerop (cond))
239 /* Remove false path. */
240 COND_EXPR_COND (stmt) = boolean_true_node;
241 changed = true;
243 else if (integer_zerop (cond))
245 /* Remove true path. */
246 COND_EXPR_COND (stmt) = boolean_false_node;
247 changed = true;
249 else
250 break;
252 modify_stmt (stmt);
253 i++;
256 if (dump_file && (dump_flags & TDF_DETAILS))
257 fprintf (dump_file, ";; Unswitching loop\n");
259 /* Unswitch the loop on this condition. */
260 nloop = tree_unswitch_loop (loops, loop, bbs[i], cond);
261 if (!nloop)
262 return changed;
264 /* Invoke itself on modified loops. */
265 tree_unswitch_single_loop (loops, nloop, num + 1);
266 tree_unswitch_single_loop (loops, loop, num + 1);
267 return true;
270 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
271 unswitching of innermost loops. COND is the condition determining which
272 loop is entered -- the new loop is entered if COND is true. Returns NULL
273 if impossible, new loop otherwise. */
275 static struct loop *
276 tree_unswitch_loop (struct loops *loops, struct loop *loop,
277 basic_block unswitch_on, tree cond)
279 basic_block condition_bb;
281 /* Some sanity checking. */
282 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
283 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
284 gcc_assert (loop->inner == NULL);
286 return tree_ssa_loop_version (loops, loop, unshare_expr (cond),
287 &condition_bb);