]>
Commit | Line | Data |
---|---|---|
92fc4a2f ZD |
1 | /* Loop unswitching. |
2 | Copyright (C) 2004 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 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 | ||
110 | #if 0 | |
111 | /* The necessary infrastructure is not in yet. */ | |
112 | if (changed) | |
113 | cleanup_tree_cfg_loop (); | |
114 | #endif | |
115 | } | |
116 | ||
117 | /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its | |
118 | basic blocks (for what it means see comments below). */ | |
119 | ||
120 | static tree | |
121 | tree_may_unswitch_on (basic_block bb, struct loop *loop) | |
122 | { | |
123 | tree stmt, def, cond; | |
124 | basic_block def_bb; | |
125 | use_optype uses; | |
126 | unsigned i; | |
127 | ||
128 | /* BB must end in a simple conditional jump. */ | |
129 | stmt = last_stmt (bb); | |
130 | if (!stmt || TREE_CODE (stmt) != COND_EXPR) | |
131 | return NULL_TREE; | |
132 | ||
133 | /* Condition must be invariant. */ | |
134 | get_stmt_operands (stmt); | |
135 | uses = STMT_USE_OPS (stmt); | |
136 | for (i = 0; i < NUM_USES (uses); i++) | |
137 | { | |
138 | def = SSA_NAME_DEF_STMT (USE_OP (uses, i)); | |
139 | def_bb = bb_for_stmt (def); | |
140 | if (def_bb | |
141 | && flow_bb_inside_loop_p (loop, def_bb)) | |
142 | return NULL_TREE; | |
143 | } | |
144 | ||
145 | cond = COND_EXPR_COND (stmt); | |
146 | /* To keep the things simple, we do not directly remove the conditions, | |
147 | but just replace tests with 0/1. Prevent the infinite loop where we | |
148 | would unswitch again on such a condition. */ | |
149 | if (integer_zerop (cond) || integer_nonzerop (cond)) | |
150 | return NULL_TREE; | |
151 | ||
152 | return cond; | |
153 | } | |
154 | ||
155 | /* Simplifies COND using checks in front of the entry of the LOOP. Just very | |
156 | simplish (sufficient to prevent us from duplicating loop in unswitching | |
e75220c8 | 157 | unnecessarily). */ |
92fc4a2f ZD |
158 | |
159 | static tree | |
160 | simplify_using_entry_checks (struct loop *loop, tree cond) | |
161 | { | |
162 | edge e = loop_preheader_edge (loop); | |
163 | tree stmt; | |
164 | ||
165 | while (1) | |
166 | { | |
167 | stmt = last_stmt (e->src); | |
168 | if (stmt | |
169 | && TREE_CODE (stmt) == COND_EXPR | |
170 | && operand_equal_p (COND_EXPR_COND (stmt), cond, 0)) | |
171 | return (e->flags & EDGE_TRUE_VALUE | |
172 | ? boolean_true_node | |
173 | : boolean_false_node); | |
174 | ||
628f6a4e | 175 | if (EDGE_COUNT (e->src->preds) > 1) |
92fc4a2f ZD |
176 | return cond; |
177 | ||
628f6a4e | 178 | e = EDGE_PRED (e->src, 0); |
92fc4a2f ZD |
179 | if (e->src == ENTRY_BLOCK_PTR) |
180 | return cond; | |
181 | } | |
182 | } | |
183 | ||
184 | /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow | |
185 | it to grow too much, it is too easy to create example on that the code would | |
186 | grow exponentially. */ | |
187 | ||
188 | static bool | |
189 | tree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num) | |
190 | { | |
191 | basic_block *bbs; | |
192 | struct loop *nloop; | |
193 | unsigned i; | |
194 | tree cond = NULL_TREE, stmt; | |
195 | bool changed = false; | |
196 | ||
197 | /* Do not unswitch too much. */ | |
198 | if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) | |
199 | { | |
200 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
201 | fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); | |
202 | return false; | |
203 | } | |
204 | ||
205 | /* Only unswitch innermost loops. */ | |
206 | if (loop->inner) | |
207 | { | |
208 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
209 | fprintf (dump_file, ";; Not unswitching, not innermost loop\n"); | |
210 | return false; | |
211 | } | |
212 | ||
213 | /* The loop should not be too large, to limit code growth. */ | |
214 | if (tree_num_loop_insns (loop) | |
215 | > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS)) | |
216 | { | |
217 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
218 | fprintf (dump_file, ";; Not unswitching, loop too big\n"); | |
219 | return false; | |
220 | } | |
221 | ||
222 | i = 0; | |
223 | bbs = get_loop_body (loop); | |
224 | ||
225 | while (1) | |
226 | { | |
227 | /* Find a bb to unswitch on. */ | |
228 | for (; i < loop->num_nodes; i++) | |
229 | if ((cond = tree_may_unswitch_on (bbs[i], loop))) | |
230 | break; | |
231 | ||
232 | if (i == loop->num_nodes) | |
233 | { | |
234 | free (bbs); | |
235 | return changed; | |
236 | } | |
237 | ||
238 | cond = simplify_using_entry_checks (loop, cond); | |
239 | stmt = last_stmt (bbs[i]); | |
240 | if (integer_nonzerop (cond)) | |
241 | { | |
242 | /* Remove false path. */ | |
243 | COND_EXPR_COND (stmt) = boolean_true_node; | |
244 | changed = true; | |
245 | } | |
246 | else if (integer_zerop (cond)) | |
247 | { | |
248 | /* Remove true path. */ | |
249 | COND_EXPR_COND (stmt) = boolean_false_node; | |
250 | changed = true; | |
251 | } | |
252 | else | |
253 | break; | |
254 | ||
255 | modify_stmt (stmt); | |
256 | i++; | |
257 | } | |
258 | ||
259 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
260 | fprintf (dump_file, ";; Unswitching loop\n"); | |
261 | ||
262 | /* Unswitch the loop on this condition. */ | |
263 | nloop = tree_unswitch_loop (loops, loop, bbs[i], cond); | |
264 | if (!nloop) | |
265 | return changed; | |
266 | ||
267 | /* Invoke itself on modified loops. */ | |
268 | tree_unswitch_single_loop (loops, nloop, num + 1); | |
269 | tree_unswitch_single_loop (loops, loop, num + 1); | |
270 | return true; | |
271 | } | |
272 | ||
273 | /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support | |
274 | unswitching of innermost loops. COND is the condition determining which | |
275 | loop is entered -- the new loop is entered if COND is true. Returns NULL | |
276 | if impossible, new loop otherwise. */ | |
277 | ||
278 | static struct loop * | |
279 | tree_unswitch_loop (struct loops *loops, struct loop *loop, | |
280 | basic_block unswitch_on, tree cond) | |
281 | { | |
282 | basic_block condition_bb; | |
283 | ||
284 | /* Some sanity checking. */ | |
285 | gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on)); | |
628f6a4e | 286 | gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2); |
92fc4a2f ZD |
287 | gcc_assert (loop->inner == NULL); |
288 | ||
289 | return tree_ssa_loop_version (loops, loop, unshare_expr (cond), | |
290 | &condition_bb); | |
291 | } |