|
0
|
1 /* Loop unswitching.
|
|
|
2 Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
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
|
|
|
9 later version.
|
|
|
10
|
|
|
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.
|
|
|
15
|
|
|
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/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "tm_p.h"
|
|
|
27 #include "hard-reg-set.h"
|
|
|
28 #include "basic-block.h"
|
|
|
29 #include "output.h"
|
|
|
30 #include "diagnostic.h"
|
|
|
31 #include "tree-flow.h"
|
|
|
32 #include "tree-dump.h"
|
|
|
33 #include "timevar.h"
|
|
|
34 #include "cfgloop.h"
|
|
|
35 #include "domwalk.h"
|
|
|
36 #include "params.h"
|
|
|
37 #include "tree-pass.h"
|
|
|
38 #include "tree-inline.h"
|
|
|
39
|
|
|
40 /* This file implements the loop unswitching, i.e. transformation of loops like
|
|
|
41
|
|
|
42 while (A)
|
|
|
43 {
|
|
|
44 if (inv)
|
|
|
45 B;
|
|
|
46
|
|
|
47 X;
|
|
|
48
|
|
|
49 if (!inv)
|
|
|
50 C;
|
|
|
51 }
|
|
|
52
|
|
|
53 where inv is the loop invariant, into
|
|
|
54
|
|
|
55 if (inv)
|
|
|
56 {
|
|
|
57 while (A)
|
|
|
58 {
|
|
|
59 B;
|
|
|
60 X;
|
|
|
61 }
|
|
|
62 }
|
|
|
63 else
|
|
|
64 {
|
|
|
65 while (A)
|
|
|
66 {
|
|
|
67 X;
|
|
|
68 C;
|
|
|
69 }
|
|
|
70 }
|
|
|
71
|
|
|
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. */
|
|
|
75
|
|
|
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 *);
|
|
|
79
|
|
|
80 /* Main entry point. Perform loop unswitching on all suitable loops. */
|
|
|
81
|
|
|
82 unsigned int
|
|
|
83 tree_ssa_unswitch_loops (void)
|
|
|
84 {
|
|
|
85 loop_iterator li;
|
|
|
86 struct loop *loop;
|
|
|
87 bool changed = false;
|
|
|
88
|
|
|
89 /* Go through inner loops (only original ones). */
|
|
|
90 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
|
|
|
91 {
|
|
|
92 changed |= tree_unswitch_single_loop (loop, 0);
|
|
|
93 }
|
|
|
94
|
|
|
95 if (changed)
|
|
|
96 return TODO_cleanup_cfg;
|
|
|
97 return 0;
|
|
|
98 }
|
|
|
99
|
|
|
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). */
|
|
|
102
|
|
|
103 static tree
|
|
|
104 tree_may_unswitch_on (basic_block bb, struct loop *loop)
|
|
|
105 {
|
|
|
106 gimple stmt, def;
|
|
|
107 tree cond, use;
|
|
|
108 basic_block def_bb;
|
|
|
109 ssa_op_iter iter;
|
|
|
110
|
|
|
111 /* BB must end in a simple conditional jump. */
|
|
|
112 stmt = last_stmt (bb);
|
|
|
113 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
|
|
|
114 return NULL_TREE;
|
|
|
115
|
|
|
116 /* Condition must be invariant. */
|
|
|
117 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
|
|
118 {
|
|
|
119 def = SSA_NAME_DEF_STMT (use);
|
|
|
120 def_bb = gimple_bb (def);
|
|
|
121 if (def_bb
|
|
|
122 && flow_bb_inside_loop_p (loop, def_bb))
|
|
|
123 return NULL_TREE;
|
|
|
124 }
|
|
|
125
|
|
|
126 cond = build2 (gimple_cond_code (stmt), boolean_type_node,
|
|
|
127 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
|
|
|
128
|
|
|
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))
|
|
|
133 return NULL_TREE;
|
|
|
134
|
|
|
135 return cond;
|
|
|
136 }
|
|
|
137
|
|
|
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
|
|
|
140 unnecessarily). */
|
|
|
141
|
|
|
142 static tree
|
|
|
143 simplify_using_entry_checks (struct loop *loop, tree cond)
|
|
|
144 {
|
|
|
145 edge e = loop_preheader_edge (loop);
|
|
|
146 gimple stmt;
|
|
|
147
|
|
|
148 while (1)
|
|
|
149 {
|
|
|
150 stmt = last_stmt (e->src);
|
|
|
151 if (stmt
|
|
|
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
|
|
|
159 ? boolean_true_node
|
|
|
160 : boolean_false_node);
|
|
|
161
|
|
|
162 if (!single_pred_p (e->src))
|
|
|
163 return cond;
|
|
|
164
|
|
|
165 e = single_pred_edge (e->src);
|
|
|
166 if (e->src == ENTRY_BLOCK_PTR)
|
|
|
167 return cond;
|
|
|
168 }
|
|
|
169 }
|
|
|
170
|
|
|
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. */
|
|
|
174
|
|
|
175 static bool
|
|
|
176 tree_unswitch_single_loop (struct loop *loop, int num)
|
|
|
177 {
|
|
|
178 basic_block *bbs;
|
|
|
179 struct loop *nloop;
|
|
|
180 unsigned i;
|
|
|
181 tree cond = NULL_TREE;
|
|
|
182 gimple stmt;
|
|
|
183 bool changed = false;
|
|
|
184
|
|
|
185 /* Do not unswitch too much. */
|
|
|
186 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
|
|
|
187 {
|
|
|
188 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
189 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
|
|
|
190 return false;
|
|
|
191 }
|
|
|
192
|
|
|
193 /* Only unswitch innermost loops. */
|
|
|
194 if (loop->inner)
|
|
|
195 {
|
|
|
196 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
197 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
|
|
|
198 return false;
|
|
|
199 }
|
|
|
200
|
|
|
201 /* Do not unswitch in cold regions. */
|
|
|
202 if (optimize_loop_for_size_p (loop))
|
|
|
203 {
|
|
|
204 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
205 fprintf (dump_file, ";; Not unswitching cold loops\n");
|
|
|
206 return false;
|
|
|
207 }
|
|
|
208
|
|
|
209 /* The loop should not be too large, to limit code growth. */
|
|
|
210 if (tree_num_loop_insns (loop, &eni_size_weights)
|
|
|
211 > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
|
|
|
212 {
|
|
|
213 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
214 fprintf (dump_file, ";; Not unswitching, loop too big\n");
|
|
|
215 return false;
|
|
|
216 }
|
|
|
217
|
|
|
218 i = 0;
|
|
|
219 bbs = get_loop_body (loop);
|
|
|
220
|
|
|
221 while (1)
|
|
|
222 {
|
|
|
223 /* Find a bb to unswitch on. */
|
|
|
224 for (; i < loop->num_nodes; i++)
|
|
|
225 if ((cond = tree_may_unswitch_on (bbs[i], loop)))
|
|
|
226 break;
|
|
|
227
|
|
|
228 if (i == loop->num_nodes)
|
|
|
229 {
|
|
|
230 free (bbs);
|
|
|
231 return changed;
|
|
|
232 }
|
|
|
233
|
|
|
234 cond = simplify_using_entry_checks (loop, cond);
|
|
|
235 stmt = last_stmt (bbs[i]);
|
|
|
236 if (integer_nonzerop (cond))
|
|
|
237 {
|
|
|
238 /* Remove false path. */
|
|
|
239 gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
|
|
|
240 changed = true;
|
|
|
241 }
|
|
|
242 else if (integer_zerop (cond))
|
|
|
243 {
|
|
|
244 /* Remove true path. */
|
|
|
245 gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
|
|
|
246 changed = true;
|
|
|
247 }
|
|
|
248 else
|
|
|
249 break;
|
|
|
250
|
|
|
251 update_stmt (stmt);
|
|
|
252 i++;
|
|
|
253 }
|
|
|
254
|
|
|
255 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
256 fprintf (dump_file, ";; Unswitching loop\n");
|
|
|
257
|
|
|
258 initialize_original_copy_tables ();
|
|
|
259 /* Unswitch the loop on this condition. */
|
|
|
260 nloop = tree_unswitch_loop (loop, bbs[i], cond);
|
|
|
261 if (!nloop)
|
|
|
262 {
|
|
|
263 free_original_copy_tables ();
|
|
|
264 free (bbs);
|
|
|
265 return changed;
|
|
|
266 }
|
|
|
267
|
|
|
268 /* Update the SSA form after unswitching. */
|
|
|
269 update_ssa (TODO_update_ssa);
|
|
|
270 free_original_copy_tables ();
|
|
|
271
|
|
|
272 /* Invoke itself on modified loops. */
|
|
|
273 tree_unswitch_single_loop (nloop, num + 1);
|
|
|
274 tree_unswitch_single_loop (loop, num + 1);
|
|
|
275 free (bbs);
|
|
|
276 return true;
|
|
|
277 }
|
|
|
278
|
|
|
279 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
|
|
|
280 unswitching of innermost loops. COND is the condition determining which
|
|
|
281 loop is entered -- the new loop is entered if COND is true. Returns NULL
|
|
|
282 if impossible, new loop otherwise. */
|
|
|
283
|
|
|
284 static struct loop *
|
|
|
285 tree_unswitch_loop (struct loop *loop,
|
|
|
286 basic_block unswitch_on, tree cond)
|
|
|
287 {
|
|
|
288 unsigned prob_true;
|
|
|
289 edge edge_true, edge_false;
|
|
|
290
|
|
|
291 /* Some sanity checking. */
|
|
|
292 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
|
|
|
293 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
|
|
|
294 gcc_assert (loop->inner == NULL);
|
|
|
295
|
|
|
296 extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
|
|
|
297 prob_true = edge_true->probability;
|
|
|
298 return loop_version (loop, unshare_expr (cond),
|
|
|
299 NULL, prob_true, prob_true,
|
|
|
300 REG_BR_PROB_BASE - prob_true, false);
|
|
|
301 }
|
