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
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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.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 loops *, struct loop *, basic_block,
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. */
84 tree_ssa_unswitch_loops (struct loops *loops)
90 /* Go through inner loops (only original ones). */
93 for (i = 1; i < num; i++)
96 loop = loops->parray[i];
103 changed |= tree_unswitch_single_loop (loops, loop, 0);
104 #ifdef ENABLE_CHECKING
105 verify_dominators (CDI_DOMINATORS);
106 verify_loop_structure (loops);
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). */
118 tree_may_unswitch_on (basic_block bb, struct loop *loop)
120 tree stmt, def, cond;
125 /* BB must end in a simple conditional jump. */
126 stmt = last_stmt (bb);
127 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
130 /* Condition must be invariant. */
131 uses = STMT_USE_OPS (stmt);
132 for (i = 0; i < NUM_USES (uses); i++)
134 def = SSA_NAME_DEF_STMT (USE_OP (uses, i));
135 def_bb = bb_for_stmt (def);
137 && flow_bb_inside_loop_p (loop, def_bb))
141 cond = COND_EXPR_COND (stmt);
142 /* To keep the things simple, we do not directly remove the conditions,
143 but just replace tests with 0/1. Prevent the infinite loop where we
144 would unswitch again on such a condition. */
145 if (integer_zerop (cond) || integer_nonzerop (cond))
151 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
152 simplish (sufficient to prevent us from duplicating loop in unswitching
156 simplify_using_entry_checks (struct loop *loop, tree cond)
158 edge e = loop_preheader_edge (loop);
163 stmt = last_stmt (e->src);
165 && TREE_CODE (stmt) == COND_EXPR
166 && operand_equal_p (COND_EXPR_COND (stmt), cond, 0))
167 return (e->flags & EDGE_TRUE_VALUE
169 : boolean_false_node);
171 if (!single_pred_p (e->src))
174 e = single_pred_edge (e->src);
175 if (e->src == ENTRY_BLOCK_PTR)
180 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
181 it to grow too much, it is too easy to create example on that the code would
182 grow exponentially. */
185 tree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num)
190 tree cond = NULL_TREE, stmt;
191 bool changed = false;
193 /* Do not unswitch too much. */
194 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
196 if (dump_file && (dump_flags & TDF_DETAILS))
197 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
201 /* Only unswitch innermost loops. */
204 if (dump_file && (dump_flags & TDF_DETAILS))
205 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
209 /* The loop should not be too large, to limit code growth. */
210 if (tree_num_loop_insns (loop)
211 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
213 if (dump_file && (dump_flags & TDF_DETAILS))
214 fprintf (dump_file, ";; Not unswitching, loop too big\n");
219 bbs = get_loop_body (loop);
223 /* Find a bb to unswitch on. */
224 for (; i < loop->num_nodes; i++)
225 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
228 if (i == loop->num_nodes)
234 cond = simplify_using_entry_checks (loop, cond);
235 stmt = last_stmt (bbs[i]);
236 if (integer_nonzerop (cond))
238 /* Remove false path. */
239 COND_EXPR_COND (stmt) = boolean_true_node;
242 else if (integer_zerop (cond))
244 /* Remove true path. */
245 COND_EXPR_COND (stmt) = boolean_false_node;
255 if (dump_file && (dump_flags & TDF_DETAILS))
256 fprintf (dump_file, ";; Unswitching loop\n");
258 /* Unswitch the loop on this condition. */
259 nloop = tree_unswitch_loop (loops, loop, bbs[i], cond);
263 /* Invoke itself on modified loops. */
264 tree_unswitch_single_loop (loops, nloop, num + 1);
265 tree_unswitch_single_loop (loops, loop, num + 1);
269 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
270 unswitching of innermost loops. COND is the condition determining which
271 loop is entered -- the new loop is entered if COND is true. Returns NULL
272 if impossible, new loop otherwise. */
275 tree_unswitch_loop (struct loops *loops, struct loop *loop,
276 basic_block unswitch_on, tree cond)
278 basic_block condition_bb;
280 /* Some sanity checking. */
281 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
282 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
283 gcc_assert (loop->inner == NULL);
285 return loop_version (loops, loop, unshare_expr (cond),