]>
Commit | Line | Data |
---|---|---|
92fc4a2f | 1 | /* Loop unswitching. |
c6c81aa6 | 2 | Copyright (C) 2004, 2005 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 | |
8 | Free Software Foundation; either version 2, 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 COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "basic-block.h" | |
30 | #include "output.h" | |
31 | #include "diagnostic.h" | |
32 | #include "tree-flow.h" | |
33 | #include "tree-dump.h" | |
34 | #include "timevar.h" | |
35 | #include "cfgloop.h" | |
36 | #include "domwalk.h" | |
37 | #include "params.h" | |
38 | #include "tree-pass.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 loops *, struct loop *, basic_block, | |
77 | tree); | |
78 | static bool tree_unswitch_single_loop (struct loops *, struct loop *, int); | |
79 | static tree tree_may_unswitch_on (basic_block, struct loop *); | |
80 | ||
81 | /* Main entry point. Perform loop unswitching on all suitable LOOPS. */ | |
82 | ||
83 | void | |
84 | tree_ssa_unswitch_loops (struct loops *loops) | |
85 | { | |
86 | int i, num; | |
87 | struct loop *loop; | |
88 | bool changed = false; | |
89 | ||
90 | /* Go through inner loops (only original ones). */ | |
91 | num = loops->num; | |
92 | ||
93 | for (i = 1; i < num; i++) | |
94 | { | |
95 | /* Removed loop? */ | |
96 | loop = loops->parray[i]; | |
97 | if (!loop) | |
98 | continue; | |
99 | ||
100 | if (loop->inner) | |
101 | continue; | |
102 | ||
103 | changed |= tree_unswitch_single_loop (loops, loop, 0); | |
104 | #ifdef ENABLE_CHECKING | |
105 | verify_dominators (CDI_DOMINATORS); | |
106 | verify_loop_structure (loops); | |
107 | #endif | |
108 | } | |
109 | ||
92fc4a2f ZD |
110 | if (changed) |
111 | cleanup_tree_cfg_loop (); | |
92fc4a2f ZD |
112 | } |
113 | ||
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). */ | |
116 | ||
117 | static tree | |
118 | tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
119 | { | |
120 | tree stmt, def, cond; | |
121 | basic_block def_bb; | |
122 | use_optype uses; | |
123 | unsigned i; | |
124 | ||
125 | /* BB must end in a simple conditional jump. */ | |
126 | stmt = last_stmt (bb); | |
127 | if (!stmt || TREE_CODE (stmt) != COND_EXPR) | |
128 | return NULL_TREE; | |
129 | ||
130 | /* Condition must be invariant. */ | |
92fc4a2f ZD |
131 | uses = STMT_USE_OPS (stmt); |
132 | for (i = 0; i < NUM_USES (uses); i++) | |
133 | { | |
134 | def = SSA_NAME_DEF_STMT (USE_OP (uses, i)); | |
135 | def_bb = bb_for_stmt (def); | |
136 | if (def_bb | |
137 | && flow_bb_inside_loop_p (loop, def_bb)) | |
138 | return NULL_TREE; | |
139 | } | |
140 | ||
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)) | |
146 | return NULL_TREE; | |
147 | ||
148 | return cond; | |
149 | } | |
150 | ||
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 | |
e75220c8 | 153 | unnecessarily). */ |
92fc4a2f ZD |
154 | |
155 | static tree | |
156 | simplify_using_entry_checks (struct loop *loop, tree cond) | |
157 | { | |
158 | edge e = loop_preheader_edge (loop); | |
159 | tree stmt; | |
160 | ||
161 | while (1) | |
162 | { | |
163 | stmt = last_stmt (e->src); | |
164 | if (stmt | |
165 | && TREE_CODE (stmt) == COND_EXPR | |
166 | && operand_equal_p (COND_EXPR_COND (stmt), cond, 0)) | |
167 | return (e->flags & EDGE_TRUE_VALUE | |
168 | ? boolean_true_node | |
169 | : boolean_false_node); | |
170 | ||
c5cbcccf | 171 | if (!single_pred_p (e->src)) |
92fc4a2f ZD |
172 | return cond; |
173 | ||
c5cbcccf | 174 | e = single_pred_edge (e->src); |
92fc4a2f ZD |
175 | if (e->src == ENTRY_BLOCK_PTR) |
176 | return cond; | |
177 | } | |
178 | } | |
179 | ||
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. */ | |
183 | ||
184 | static bool | |
185 | tree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num) | |
186 | { | |
187 | basic_block *bbs; | |
188 | struct loop *nloop; | |
189 | unsigned i; | |
190 | tree cond = NULL_TREE, stmt; | |
191 | bool changed = false; | |
192 | ||
193 | /* Do not unswitch too much. */ | |
194 | if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
195 | { | |
196 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
197 | fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
198 | return false; | |
199 | } | |
200 | ||
201 | /* Only unswitch innermost loops. */ | |
202 | if (loop->inner) | |
203 | { | |
204 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
205 | fprintf (dump_file, ";; Not unswitching, not innermost loop\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) | |
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 | COND_EXPR_COND (stmt) = boolean_true_node; | |
240 | changed = true; | |
241 | } | |
242 | else if (integer_zerop (cond)) | |
243 | { | |
244 | /* Remove true path. */ | |
245 | COND_EXPR_COND (stmt) = boolean_false_node; | |
246 | changed = true; | |
247 | } | |
248 | else | |
249 | break; | |
250 | ||
f430bae8 | 251 | update_stmt (stmt); |
92fc4a2f ZD |
252 | i++; |
253 | } | |
254 | ||
255 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
256 | fprintf (dump_file, ";; Unswitching loop\n"); | |
257 | ||
258 | /* Unswitch the loop on this condition. */ | |
259 | nloop = tree_unswitch_loop (loops, loop, bbs[i], cond); | |
260 | if (!nloop) | |
261 | return changed; | |
262 | ||
263 | /* Invoke itself on modified loops. */ | |
264 | tree_unswitch_single_loop (loops, nloop, num + 1); | |
265 | tree_unswitch_single_loop (loops, loop, num + 1); | |
266 | return true; | |
267 | } | |
268 | ||
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. */ | |
273 | ||
274 | static struct loop * | |
275 | tree_unswitch_loop (struct loops *loops, struct loop *loop, | |
276 | basic_block unswitch_on, tree cond) | |
277 | { | |
278 | basic_block condition_bb; | |
279 | ||
280 | /* Some sanity checking. */ | |
281 | gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
628f6a4e | 282 | gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); |
92fc4a2f ZD |
283 | gcc_assert (loop->inner == NULL); |
284 | ||
1cb7dfc3 MH |
285 | return loop_version (loops, loop, unshare_expr (cond), |
286 | &condition_bb); | |
92fc4a2f | 287 | } |