]>
Commit | Line | Data |
---|---|---|
92fc4a2f | 1 | /* Loop unswitching. |
9dcd6f09 | 2 | Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc. |
92fc4a2f ZD |
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 | |
9dcd6f09 | 8 | Free Software Foundation; either version 3, or (at your option) any |
92fc4a2f ZD |
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 | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
92fc4a2f ZD |
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" | |
7f9bc51b | 38 | #include "tree-inline.h" |
92fc4a2f ZD |
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 | ||
d73be268 ZD |
76 | static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); |
77 | static bool tree_unswitch_single_loop (struct loop *, int); | |
92fc4a2f ZD |
78 | static tree tree_may_unswitch_on (basic_block, struct loop *); |
79 | ||
d73be268 | 80 | /* Main entry point. Perform loop unswitching on all suitable loops. */ |
92fc4a2f | 81 | |
c7f965b6 | 82 | unsigned int |
d73be268 | 83 | tree_ssa_unswitch_loops (void) |
92fc4a2f | 84 | { |
42fd6772 | 85 | loop_iterator li; |
92fc4a2f ZD |
86 | struct loop *loop; |
87 | bool changed = false; | |
88 | ||
89 | /* Go through inner loops (only original ones). */ | |
677cc14d | 90 | FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) |
92fc4a2f | 91 | { |
d73be268 | 92 | changed |= tree_unswitch_single_loop (loop, 0); |
92fc4a2f ZD |
93 | } |
94 | ||
92fc4a2f | 95 | if (changed) |
c7f965b6 AP |
96 | return TODO_cleanup_cfg; |
97 | return 0; | |
92fc4a2f ZD |
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 | { | |
f47c96aa | 106 | tree stmt, def, cond, use; |
92fc4a2f | 107 | basic_block def_bb; |
f47c96aa | 108 | ssa_op_iter iter; |
92fc4a2f ZD |
109 | |
110 | /* BB must end in a simple conditional jump. */ | |
111 | stmt = last_stmt (bb); | |
112 | if (!stmt || TREE_CODE (stmt) != COND_EXPR) | |
113 | return NULL_TREE; | |
114 | ||
115 | /* Condition must be invariant. */ | |
f47c96aa | 116 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
92fc4a2f | 117 | { |
f47c96aa | 118 | def = SSA_NAME_DEF_STMT (use); |
92fc4a2f ZD |
119 | def_bb = bb_for_stmt (def); |
120 | if (def_bb | |
121 | && flow_bb_inside_loop_p (loop, def_bb)) | |
122 | return NULL_TREE; | |
123 | } | |
124 | ||
125 | cond = COND_EXPR_COND (stmt); | |
126 | /* To keep the things simple, we do not directly remove the conditions, | |
127 | but just replace tests with 0/1. Prevent the infinite loop where we | |
128 | would unswitch again on such a condition. */ | |
129 | if (integer_zerop (cond) || integer_nonzerop (cond)) | |
130 | return NULL_TREE; | |
131 | ||
132 | return cond; | |
133 | } | |
134 | ||
135 | /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
136 | simplish (sufficient to prevent us from duplicating loop in unswitching | |
e75220c8 | 137 | unnecessarily). */ |
92fc4a2f ZD |
138 | |
139 | static tree | |
140 | simplify_using_entry_checks (struct loop *loop, tree cond) | |
141 | { | |
142 | edge e = loop_preheader_edge (loop); | |
143 | tree stmt; | |
144 | ||
145 | while (1) | |
146 | { | |
147 | stmt = last_stmt (e->src); | |
148 | if (stmt | |
149 | && TREE_CODE (stmt) == COND_EXPR | |
150 | && operand_equal_p (COND_EXPR_COND (stmt), cond, 0)) | |
151 | return (e->flags & EDGE_TRUE_VALUE | |
152 | ? boolean_true_node | |
153 | : boolean_false_node); | |
154 | ||
c5cbcccf | 155 | if (!single_pred_p (e->src)) |
92fc4a2f ZD |
156 | return cond; |
157 | ||
c5cbcccf | 158 | e = single_pred_edge (e->src); |
92fc4a2f ZD |
159 | if (e->src == ENTRY_BLOCK_PTR) |
160 | return cond; | |
161 | } | |
162 | } | |
163 | ||
164 | /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
165 | it to grow too much, it is too easy to create example on that the code would | |
166 | grow exponentially. */ | |
167 | ||
168 | static bool | |
d73be268 | 169 | tree_unswitch_single_loop (struct loop *loop, int num) |
92fc4a2f ZD |
170 | { |
171 | basic_block *bbs; | |
172 | struct loop *nloop; | |
173 | unsigned i; | |
174 | tree cond = NULL_TREE, stmt; | |
175 | bool changed = false; | |
176 | ||
177 | /* Do not unswitch too much. */ | |
178 | if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
179 | { | |
180 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
181 | fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
182 | return false; | |
183 | } | |
184 | ||
185 | /* Only unswitch innermost loops. */ | |
186 | if (loop->inner) | |
187 | { | |
188 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
189 | fprintf (dump_file, ";; Not unswitching, not innermost loop\n"); | |
190 | return false; | |
191 | } | |
192 | ||
193 | /* The loop should not be too large, to limit code growth. */ | |
7f9bc51b | 194 | if (tree_num_loop_insns (loop, &eni_size_weights) |
92fc4a2f ZD |
195 | > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) |
196 | { | |
197 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
198 | fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
199 | return false; | |
200 | } | |
201 | ||
202 | i = 0; | |
203 | bbs = get_loop_body (loop); | |
204 | ||
205 | while (1) | |
206 | { | |
207 | /* Find a bb to unswitch on. */ | |
208 | for (; i < loop->num_nodes; i++) | |
209 | if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
210 | break; | |
211 | ||
212 | if (i == loop->num_nodes) | |
213 | { | |
214 | free (bbs); | |
215 | return changed; | |
216 | } | |
217 | ||
218 | cond = simplify_using_entry_checks (loop, cond); | |
219 | stmt = last_stmt (bbs[i]); | |
220 | if (integer_nonzerop (cond)) | |
221 | { | |
222 | /* Remove false path. */ | |
223 | COND_EXPR_COND (stmt) = boolean_true_node; | |
224 | changed = true; | |
225 | } | |
226 | else if (integer_zerop (cond)) | |
227 | { | |
228 | /* Remove true path. */ | |
229 | COND_EXPR_COND (stmt) = boolean_false_node; | |
230 | changed = true; | |
231 | } | |
232 | else | |
233 | break; | |
234 | ||
f430bae8 | 235 | update_stmt (stmt); |
92fc4a2f ZD |
236 | i++; |
237 | } | |
238 | ||
239 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
240 | fprintf (dump_file, ";; Unswitching loop\n"); | |
241 | ||
6580ee77 | 242 | initialize_original_copy_tables (); |
92fc4a2f | 243 | /* Unswitch the loop on this condition. */ |
d73be268 | 244 | nloop = tree_unswitch_loop (loop, bbs[i], cond); |
92fc4a2f | 245 | if (!nloop) |
094bb856 JH |
246 | { |
247 | free_original_copy_tables (); | |
77f6ec05 | 248 | free (bbs); |
094bb856 JH |
249 | return changed; |
250 | } | |
92fc4a2f | 251 | |
84d65814 DN |
252 | /* Update the SSA form after unswitching. */ |
253 | update_ssa (TODO_update_ssa); | |
6580ee77 | 254 | free_original_copy_tables (); |
84d65814 | 255 | |
92fc4a2f | 256 | /* Invoke itself on modified loops. */ |
d73be268 ZD |
257 | tree_unswitch_single_loop (nloop, num + 1); |
258 | tree_unswitch_single_loop (loop, num + 1); | |
77f6ec05 | 259 | free (bbs); |
92fc4a2f ZD |
260 | return true; |
261 | } | |
262 | ||
263 | /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
264 | unswitching of innermost loops. COND is the condition determining which | |
265 | loop is entered -- the new loop is entered if COND is true. Returns NULL | |
266 | if impossible, new loop otherwise. */ | |
267 | ||
268 | static struct loop * | |
d73be268 | 269 | tree_unswitch_loop (struct loop *loop, |
92fc4a2f ZD |
270 | basic_block unswitch_on, tree cond) |
271 | { | |
03cb2019 ZD |
272 | unsigned prob_true; |
273 | edge edge_true, edge_false; | |
92fc4a2f ZD |
274 | |
275 | /* Some sanity checking. */ | |
276 | gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
628f6a4e | 277 | gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); |
92fc4a2f ZD |
278 | gcc_assert (loop->inner == NULL); |
279 | ||
03cb2019 ZD |
280 | extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false); |
281 | prob_true = edge_true->probability; | |
d73be268 | 282 | return loop_version (loop, unshare_expr (cond), |
03cb2019 ZD |
283 | NULL, prob_true, prob_true, |
284 | REG_BR_PROB_BASE - prob_true, false); | |
92fc4a2f | 285 | } |