2 Copyright (C) 2004, 2005, 2007, 2008 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"
26 #include "basic-block.h"
28 #include "tree-flow.h"
29 #include "tree-dump.h"
33 #include "tree-pass.h"
34 #include "tree-inline.h"
36 /* This file implements the loop unswitching, i.e. transformation of loops like
49 where inv is the loop invariant, into
68 Inv is considered invariant iff the values it compares are both invariant;
69 tree-ssa-loop-im.c ensures that all the suitable conditions are in this
72 static struct loop
*tree_unswitch_loop (struct loop
*, basic_block
, tree
);
73 static bool tree_unswitch_single_loop (struct loop
*, int);
74 static tree
tree_may_unswitch_on (basic_block
, struct loop
*);
76 /* Main entry point. Perform loop unswitching on all suitable loops. */
79 tree_ssa_unswitch_loops (void)
85 /* Go through inner loops (only original ones). */
86 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
88 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
89 fprintf (dump_file
, ";; Considering loop %d\n", loop
->num
);
91 /* Do not unswitch in cold regions. */
92 if (optimize_loop_for_size_p (loop
))
94 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
95 fprintf (dump_file
, ";; Not unswitching cold loops\n");
99 /* The loop should not be too large, to limit code growth. */
100 if (tree_num_loop_insns (loop
, &eni_size_weights
)
101 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
104 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
108 changed
|= tree_unswitch_single_loop (loop
, 0);
112 return TODO_cleanup_cfg
;
116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
117 basic blocks (for what it means see comments below). */
120 tree_may_unswitch_on (basic_block bb
, struct loop
*loop
)
127 /* BB must end in a simple conditional jump. */
128 stmt
= last_stmt (bb
);
129 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
132 /* Condition must be invariant. */
133 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, iter
, SSA_OP_USE
)
135 def
= SSA_NAME_DEF_STMT (use
);
136 def_bb
= gimple_bb (def
);
138 && flow_bb_inside_loop_p (loop
, def_bb
))
142 cond
= build2 (gimple_cond_code (stmt
), boolean_type_node
,
143 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
145 /* To keep the things simple, we do not directly remove the conditions,
146 but just replace tests with 0/1. Prevent the infinite loop where we
147 would unswitch again on such a condition. */
148 if (integer_zerop (cond
) || integer_nonzerop (cond
))
154 /* Simplifies COND using checks in front of the entry of the LOOP. Just very
155 simplish (sufficient to prevent us from duplicating loop in unswitching
159 simplify_using_entry_checks (struct loop
*loop
, tree cond
)
161 edge e
= loop_preheader_edge (loop
);
166 stmt
= last_stmt (e
->src
);
168 && gimple_code (stmt
) == GIMPLE_COND
169 && gimple_cond_code (stmt
) == TREE_CODE (cond
)
170 && operand_equal_p (gimple_cond_lhs (stmt
),
171 TREE_OPERAND (cond
, 0), 0)
172 && operand_equal_p (gimple_cond_rhs (stmt
),
173 TREE_OPERAND (cond
, 1), 0))
174 return (e
->flags
& EDGE_TRUE_VALUE
176 : boolean_false_node
);
178 if (!single_pred_p (e
->src
))
181 e
= single_pred_edge (e
->src
);
182 if (e
->src
== ENTRY_BLOCK_PTR
)
187 /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
188 it to grow too much, it is too easy to create example on that the code would
189 grow exponentially. */
192 tree_unswitch_single_loop (struct loop
*loop
, int num
)
197 tree cond
= NULL_TREE
;
199 bool changed
= false;
201 /* Do not unswitch too much. */
202 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
205 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
210 bbs
= get_loop_body (loop
);
214 /* Find a bb to unswitch on. */
215 for (; i
< loop
->num_nodes
; i
++)
216 if ((cond
= tree_may_unswitch_on (bbs
[i
], loop
)))
219 if (i
== loop
->num_nodes
)
225 cond
= simplify_using_entry_checks (loop
, cond
);
226 stmt
= last_stmt (bbs
[i
]);
227 if (integer_nonzerop (cond
))
229 /* Remove false path. */
230 gimple_cond_set_condition_from_tree (stmt
, boolean_true_node
);
233 else if (integer_zerop (cond
))
235 /* Remove true path. */
236 gimple_cond_set_condition_from_tree (stmt
, boolean_false_node
);
246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
247 fprintf (dump_file
, ";; Unswitching loop\n");
249 initialize_original_copy_tables ();
250 /* Unswitch the loop on this condition. */
251 nloop
= tree_unswitch_loop (loop
, bbs
[i
], cond
);
254 free_original_copy_tables ();
259 /* Update the SSA form after unswitching. */
260 update_ssa (TODO_update_ssa
);
261 free_original_copy_tables ();
263 /* Invoke itself on modified loops. */
264 tree_unswitch_single_loop (nloop
, num
+ 1);
265 tree_unswitch_single_loop (loop
, num
+ 1);
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. */
276 tree_unswitch_loop (struct loop
*loop
,
277 basic_block unswitch_on
, tree cond
)
280 edge edge_true
, edge_false
;
282 /* Some sanity checking. */
283 gcc_assert (flow_bb_inside_loop_p (loop
, unswitch_on
));
284 gcc_assert (EDGE_COUNT (unswitch_on
->succs
) == 2);
285 gcc_assert (loop
->inner
== NULL
);
287 extract_true_false_edges_from_block (unswitch_on
, &edge_true
, &edge_false
);
288 prob_true
= edge_true
->probability
;
289 return loop_version (loop
, unshare_expr (cond
),
290 NULL
, prob_true
, prob_true
,
291 REG_BR_PROB_BASE
- prob_true
, false);