2 Copyright (C) 2004, 2005, 2007 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
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
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/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
37 #include "tree-pass.h"
38 #include "tree-inline.h"
40 /* This file implements the loop unswitching, i.e. transformation of loops like
53 where inv is the loop invariant, into
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
76 static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
77 static bool tree_unswitch_single_loop (struct loop *, int);
78 static tree tree_may_unswitch_on (basic_block, struct loop *);
80 /* Main entry point. Perform loop unswitching on all suitable loops. */
83 tree_ssa_unswitch_loops (void)
89 /* Go through inner loops (only original ones). */
90 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
92 changed |= tree_unswitch_single_loop (loop, 0);
96 return TODO_cleanup_cfg;
100 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
101 basic blocks (for what it means see comments below). */
104 tree_may_unswitch_on (basic_block bb, struct loop *loop)
111 /* BB must end in a simple conditional jump. */
112 stmt = last_stmt (bb);
113 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
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 = gimple_bb (def);
122 && flow_bb_inside_loop_p (loop, def_bb))
126 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
127 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
129 /* To keep the things simple, we do not directly remove the conditions,
130 but just replace tests with 0/1. Prevent the infinite loop where we
131 would unswitch again on such a condition. */
132 if (integer_zerop (cond) || integer_nonzerop (cond))
138 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
139 simplish (sufficient to prevent us from duplicating loop in unswitching
143 simplify_using_entry_checks (struct loop *loop, tree cond)
145 edge e = loop_preheader_edge (loop);
150 stmt = last_stmt (e->src);
152 && gimple_code (stmt) == GIMPLE_COND
153 && gimple_cond_code (stmt) == TREE_CODE (cond)
154 && operand_equal_p (gimple_cond_lhs (stmt),
155 TREE_OPERAND (cond, 0), 0)
156 && operand_equal_p (gimple_cond_rhs (stmt),
157 TREE_OPERAND (cond, 1), 0))
158 return (e->flags & EDGE_TRUE_VALUE
160 : boolean_false_node);
162 if (!single_pred_p (e->src))
165 e = single_pred_edge (e->src);
166 if (e->src == ENTRY_BLOCK_PTR)
171 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
172 it to grow too much, it is too easy to create example on that the code would
173 grow exponentially. */
176 tree_unswitch_single_loop (struct loop *loop, int num)
181 tree cond = NULL_TREE;
183 bool changed = false;
185 /* Do not unswitch too much. */
186 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
188 if (dump_file && (dump_flags & TDF_DETAILS))
189 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
193 /* Only unswitch innermost loops. */
196 if (dump_file && (dump_flags & TDF_DETAILS))
197 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
201 /* The loop should not be too large, to limit code growth. */
202 if (tree_num_loop_insns (loop, &eni_size_weights)
203 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
205 if (dump_file && (dump_flags & TDF_DETAILS))
206 fprintf (dump_file, ";; Not unswitching, loop too big\n");
211 bbs = get_loop_body (loop);
215 /* Find a bb to unswitch on. */
216 for (; i < loop->num_nodes; i++)
217 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
220 if (i == loop->num_nodes)
226 cond = simplify_using_entry_checks (loop, cond);
227 stmt = last_stmt (bbs[i]);
228 if (integer_nonzerop (cond))
230 /* Remove false path. */
231 gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
234 else if (integer_zerop (cond))
236 /* Remove true path. */
237 gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
247 if (dump_file && (dump_flags & TDF_DETAILS))
248 fprintf (dump_file, ";; Unswitching loop\n");
250 initialize_original_copy_tables ();
251 /* Unswitch the loop on this condition. */
252 nloop = tree_unswitch_loop (loop, bbs[i], cond);
255 free_original_copy_tables ();
260 /* Update the SSA form after unswitching. */
261 update_ssa (TODO_update_ssa);
262 free_original_copy_tables ();
264 /* Invoke itself on modified loops. */
265 tree_unswitch_single_loop (nloop, num + 1);
266 tree_unswitch_single_loop (loop, num + 1);
271 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
272 unswitching of innermost loops. COND is the condition determining which
273 loop is entered -- the new loop is entered if COND is true. Returns NULL
274 if impossible, new loop otherwise. */
277 tree_unswitch_loop (struct loop *loop,
278 basic_block unswitch_on, tree cond)
281 edge edge_true, edge_false;
283 /* Some sanity checking. */
284 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
285 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
286 gcc_assert (loop->inner == NULL);
288 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
289 prob_true = edge_true->probability;
290 return loop_version (loop, unshare_expr (cond),
291 NULL, prob_true, prob_true,
292 REG_BR_PROB_BASE - prob_true, false);