]>
Commit | Line | Data |
---|---|---|
c913f08a ZD |
1 | /* High-level loop manipulation functions. |
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 "tree-pass.h" | |
37 | #include "cfglayout.h" | |
38 | #include "tree-scalar-evolution.h" | |
39 | ||
40 | /* Add exit phis for the USE on EXIT. */ | |
41 | ||
42 | static void | |
43 | add_exit_phis_edge (basic_block exit, tree use) | |
44 | { | |
45 | tree phi, def_stmt = SSA_NAME_DEF_STMT (use); | |
46 | basic_block def_bb = bb_for_stmt (def_stmt); | |
47 | struct loop *def_loop; | |
48 | edge e; | |
49 | ||
50 | /* Check that some of the edges entering the EXIT block exits a loop in | |
51 | that USE is defined. */ | |
52 | for (e = exit->pred; e; e = e->pred_next) | |
53 | { | |
54 | def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father); | |
55 | if (!flow_bb_inside_loop_p (def_loop, e->dest)) | |
56 | break; | |
57 | } | |
58 | ||
59 | if (!e) | |
60 | return; | |
61 | ||
62 | phi = create_phi_node (use, exit); | |
63 | ||
64 | for (e = exit->pred; e; e = e->pred_next) | |
65 | add_phi_arg (&phi, use, e); | |
66 | ||
67 | SSA_NAME_DEF_STMT (use) = def_stmt; | |
68 | } | |
69 | ||
70 | /* Add exit phis for VAR that is used in LIVEIN. | |
71 | Exits of the loops are stored in EXITS. */ | |
72 | ||
73 | static void | |
74 | add_exit_phis_var (tree var, bitmap livein, bitmap exits) | |
75 | { | |
76 | bitmap def; | |
77 | int index; | |
78 | basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var)); | |
79 | ||
80 | bitmap_clear_bit (livein, def_bb->index); | |
81 | ||
82 | def = BITMAP_XMALLOC (); | |
83 | bitmap_set_bit (def, def_bb->index); | |
84 | compute_global_livein (livein, def); | |
85 | BITMAP_XFREE (def); | |
86 | ||
87 | EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, | |
88 | add_exit_phis_edge (BASIC_BLOCK (index), var)); | |
89 | } | |
90 | ||
91 | /* Add exit phis for the names marked in NAMES_TO_RENAME. | |
92 | Exits of the loops are stored in EXITS. Sets of blocks where the ssa | |
93 | names are used are stored in USE_BLOCKS. */ | |
94 | ||
95 | static void | |
96 | add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits) | |
97 | { | |
98 | unsigned i; | |
99 | ||
100 | EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, | |
101 | { | |
102 | add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits); | |
103 | }); | |
104 | } | |
105 | ||
106 | /* Returns a bitmap of all loop exit edge targets. */ | |
107 | ||
108 | static bitmap | |
109 | get_loops_exits (void) | |
110 | { | |
111 | bitmap exits = BITMAP_XMALLOC (); | |
112 | basic_block bb; | |
113 | edge e; | |
114 | ||
115 | FOR_EACH_BB (bb) | |
116 | { | |
117 | for (e = bb->pred; e; e = e->pred_next) | |
118 | if (e->src != ENTRY_BLOCK_PTR | |
119 | && !flow_bb_inside_loop_p (e->src->loop_father, bb)) | |
120 | { | |
121 | bitmap_set_bit (exits, bb->index); | |
122 | break; | |
123 | } | |
124 | } | |
125 | ||
126 | return exits; | |
127 | } | |
128 | ||
129 | /* For USE in BB, if it is used outside of the loop it is defined in, | |
130 | mark it for rewrite. Record basic block BB where it is used | |
131 | to USE_BLOCKS. */ | |
132 | ||
133 | static void | |
134 | find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks) | |
135 | { | |
136 | unsigned ver; | |
137 | basic_block def_bb; | |
138 | struct loop *def_loop; | |
139 | ||
140 | if (TREE_CODE (use) != SSA_NAME) | |
141 | return; | |
142 | ||
143 | ver = SSA_NAME_VERSION (use); | |
144 | def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use)); | |
145 | if (!def_bb) | |
146 | return; | |
147 | def_loop = def_bb->loop_father; | |
148 | ||
149 | /* If the definition is not inside loop, it is not interesting. */ | |
150 | if (!def_loop->outer) | |
151 | return; | |
152 | ||
153 | if (!use_blocks[ver]) | |
154 | use_blocks[ver] = BITMAP_XMALLOC (); | |
155 | bitmap_set_bit (use_blocks[ver], bb->index); | |
156 | ||
157 | if (!flow_bb_inside_loop_p (def_loop, bb)) | |
158 | mark_for_rewrite (use); | |
159 | } | |
160 | ||
161 | /* For uses in STMT, mark names that are used outside of the loop they are | |
162 | defined to rewrite. Record the set of blocks in that the ssa | |
163 | names are defined to USE_BLOCKS. */ | |
164 | ||
165 | static void | |
166 | find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks) | |
167 | { | |
168 | use_optype uses; | |
169 | vuse_optype vuses; | |
170 | v_may_def_optype v_may_defs; | |
171 | stmt_ann_t ann; | |
172 | unsigned i; | |
173 | basic_block bb = bb_for_stmt (stmt); | |
174 | ||
175 | get_stmt_operands (stmt); | |
176 | ann = stmt_ann (stmt); | |
177 | ||
178 | uses = USE_OPS (ann); | |
179 | for (i = 0; i < NUM_USES (uses); i++) | |
180 | find_uses_to_rename_use (bb, USE_OP (uses, i), use_blocks); | |
181 | ||
182 | vuses = VUSE_OPS (ann); | |
183 | for (i = 0; i < NUM_VUSES (vuses); i++) | |
184 | find_uses_to_rename_use (bb, VUSE_OP (vuses, i),use_blocks); | |
185 | ||
186 | v_may_defs = V_MAY_DEF_OPS (ann); | |
187 | for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) | |
188 | find_uses_to_rename_use (bb, V_MAY_DEF_OP (v_may_defs, i), use_blocks); | |
189 | } | |
190 | ||
191 | /* Marks names that are used outside of the loop they are defined in | |
192 | for rewrite. Records the set of blocks in that the ssa | |
193 | names are defined to USE_BLOCKS. */ | |
194 | ||
195 | static void | |
196 | find_uses_to_rename (bitmap *use_blocks) | |
197 | { | |
198 | basic_block bb; | |
199 | block_stmt_iterator bsi; | |
200 | tree phi; | |
201 | unsigned i; | |
202 | ||
203 | FOR_EACH_BB (bb) | |
204 | { | |
205 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
206 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) | |
207 | find_uses_to_rename_use (PHI_ARG_EDGE (phi, i)->src, | |
208 | PHI_ARG_DEF (phi, i), use_blocks); | |
209 | ||
210 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
211 | find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks); | |
212 | } | |
213 | } | |
214 | ||
215 | /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra | |
216 | phi nodes to ensure that no variable is used outside the loop it is | |
217 | defined in. | |
218 | ||
219 | This strengthening of the basic ssa form has several advantages: | |
220 | ||
221 | 1) Updating it during unrolling/peeling/versioning is trivial, since | |
222 | we do not need to care about the uses outside of the loop. | |
223 | 2) The behavior of all uses of an induction variable is the same. | |
224 | Without this, you need to distinguish the case when the variable | |
225 | is used outside of the loop it is defined in, for example | |
226 | ||
227 | for (i = 0; i < 100; i++) | |
228 | { | |
229 | for (j = 0; j < 100; j++) | |
230 | { | |
231 | k = i + j; | |
232 | use1 (k); | |
233 | } | |
234 | use2 (k); | |
235 | } | |
236 | ||
237 | Looking from the outer loop with the normal SSA form, the first use of k | |
238 | is not well-behaved, while the second one is an induction variable with | |
239 | base 99 and step 1. */ | |
240 | ||
241 | void | |
242 | rewrite_into_loop_closed_ssa (void) | |
243 | { | |
244 | bitmap loop_exits = get_loops_exits (); | |
245 | bitmap *use_blocks; | |
246 | unsigned i; | |
247 | bitmap names_to_rename; | |
248 | ||
249 | if (any_marked_for_rewrite_p ()) | |
250 | abort (); | |
251 | ||
252 | use_blocks = xcalloc (num_ssa_names, sizeof (bitmap)); | |
253 | ||
254 | /* Find the uses outside loops. */ | |
255 | find_uses_to_rename (use_blocks); | |
256 | ||
257 | /* Add the phi nodes on exits of the loops for the names we need to | |
258 | rewrite. */ | |
259 | names_to_rename = marked_ssa_names (); | |
260 | add_exit_phis (names_to_rename, use_blocks, loop_exits); | |
261 | ||
262 | for (i = 0; i < num_ssa_names; i++) | |
263 | BITMAP_XFREE (use_blocks[i]); | |
264 | free (use_blocks); | |
265 | BITMAP_XFREE (loop_exits); | |
266 | BITMAP_XFREE (names_to_rename); | |
267 | ||
268 | /* Do the rewriting. */ | |
269 | rewrite_ssa_into_ssa (); | |
270 | } | |
271 | ||
272 | /* Check invariants of the loop closed ssa form for the USE in BB. */ | |
273 | ||
274 | static void | |
275 | check_loop_closed_ssa_use (basic_block bb, tree use) | |
276 | { | |
277 | tree def; | |
278 | basic_block def_bb; | |
279 | ||
280 | if (TREE_CODE (use) != SSA_NAME) | |
281 | return; | |
282 | ||
283 | def = SSA_NAME_DEF_STMT (use); | |
284 | def_bb = bb_for_stmt (def); | |
285 | if (def_bb | |
286 | && !flow_bb_inside_loop_p (def_bb->loop_father, bb)) | |
287 | abort (); | |
288 | } | |
289 | ||
290 | /* Checks invariants of loop closed ssa form in statement STMT in BB. */ | |
291 | ||
292 | static void | |
293 | check_loop_closed_ssa_stmt (basic_block bb, tree stmt) | |
294 | { | |
295 | use_optype uses; | |
296 | vuse_optype vuses; | |
297 | v_may_def_optype v_may_defs; | |
298 | stmt_ann_t ann; | |
299 | unsigned i; | |
300 | ||
301 | get_stmt_operands (stmt); | |
302 | ann = stmt_ann (stmt); | |
303 | ||
304 | uses = USE_OPS (ann); | |
305 | for (i = 0; i < NUM_USES (uses); i++) | |
306 | check_loop_closed_ssa_use (bb, USE_OP (uses, i)); | |
307 | ||
308 | vuses = VUSE_OPS (ann); | |
309 | for (i = 0; i < NUM_VUSES (vuses); i++) | |
310 | check_loop_closed_ssa_use (bb, VUSE_OP (vuses, i)); | |
311 | ||
312 | v_may_defs = V_MAY_DEF_OPS (ann); | |
313 | for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) | |
314 | check_loop_closed_ssa_use (bb, V_MAY_DEF_OP (v_may_defs, i)); | |
315 | } | |
316 | ||
317 | /* Checks that invariants of the loop closed ssa form are preserved. */ | |
318 | ||
319 | void | |
320 | verify_loop_closed_ssa (void) | |
321 | { | |
322 | basic_block bb; | |
323 | block_stmt_iterator bsi; | |
324 | tree phi; | |
325 | unsigned i; | |
326 | ||
327 | verify_ssa (); | |
328 | ||
329 | FOR_EACH_BB (bb) | |
330 | { | |
331 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
332 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++) | |
333 | check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src, | |
334 | PHI_ARG_DEF (phi, i)); | |
335 | ||
336 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
337 | check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi)); | |
338 | } | |
339 | } |