]>
Commit | Line | Data |
---|---|---|
a7e5372d ZD |
1 | /* Loop invariant motion. |
2 | Copyright (C) 2003 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 | #include "flags.h" | |
40 | ||
41 | /* A type for the list of statements that have to be moved in order to be able | |
42 | to hoist an invariant computation. */ | |
43 | ||
44 | struct depend | |
45 | { | |
46 | tree stmt; | |
47 | struct depend *next; | |
48 | }; | |
49 | ||
50 | /* The possibilities of statement movement. */ | |
51 | ||
52 | enum move_pos | |
53 | { | |
54 | MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */ | |
55 | MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement | |
56 | become executed -- memory accesses, ... */ | |
57 | MOVE_POSSIBLE /* Unlimited movement. */ | |
58 | }; | |
59 | ||
60 | /* The auxiliary data kept for each statement. */ | |
61 | ||
62 | struct lim_aux_data | |
63 | { | |
64 | struct loop *max_loop; /* The outermost loop in that the statement | |
65 | is invariant. */ | |
66 | ||
67 | struct loop *tgt_loop; /* The loop out of that we want to move the | |
68 | invariant. */ | |
69 | ||
70 | struct loop *always_executed_in; | |
71 | /* The outermost loop for that we are sure | |
72 | the statement is executed if the loop | |
73 | is entered. */ | |
74 | ||
75 | bool sm_done; /* True iff the store motion for a memory | |
76 | reference in the statement has already | |
77 | been executed. */ | |
78 | ||
79 | unsigned cost; /* Cost of the computation performed by the | |
80 | statement. */ | |
81 | ||
82 | struct depend *depends; /* List of statements that must be also hoisted | |
83 | out of the loop when this statement is | |
84 | hoisted; i.e. those that define the operands | |
85 | of the statement and are inside of the | |
86 | MAX_LOOP loop. */ | |
87 | }; | |
88 | ||
89 | #define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->common.aux)) | |
90 | ||
91 | /* Description of a memory reference for store motion. */ | |
92 | ||
93 | struct mem_ref | |
94 | { | |
95 | tree *ref; /* The reference itself. */ | |
96 | tree stmt; /* The statement in that it occurs. */ | |
97 | struct mem_ref *next; /* Next use in the chain. */ | |
98 | }; | |
99 | ||
100 | /* Minimum cost of an expensive expression. */ | |
101 | #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE)) | |
102 | ||
103 | /* The outermost loop for that execution of the header guarantees that the | |
104 | block will be executed. */ | |
105 | #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux) | |
106 | ||
107 | /* Maximum uid in the statement in the function. */ | |
108 | ||
109 | static unsigned max_uid; | |
110 | ||
111 | /* Calls CBCK for each index in memory reference ADDR_P. There are two | |
112 | kinds situations handled; in each of these cases, the memory reference | |
113 | and DATA are passed to the callback: | |
114 | ||
115 | Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also | |
116 | pass the pointer to the index to the callback. | |
117 | ||
118 | Pointer dereference: INDIRECT_REF (addr). In this case we also pass the | |
119 | pointer to addr to the callback. | |
120 | ||
121 | If the callback returns false, the whole search stops and false is returned. | |
122 | Otherwise the function returns true after traversing through the whole | |
123 | reference *ADDR_P. */ | |
124 | ||
125 | bool | |
126 | for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data) | |
127 | { | |
128 | tree *nxt; | |
129 | ||
130 | for (; ; addr_p = nxt) | |
131 | { | |
132 | switch (TREE_CODE (*addr_p)) | |
133 | { | |
134 | case SSA_NAME: | |
135 | return cbck (*addr_p, addr_p, data); | |
136 | ||
137 | case INDIRECT_REF: | |
138 | nxt = &TREE_OPERAND (*addr_p, 0); | |
139 | return cbck (*addr_p, nxt, data); | |
140 | ||
141 | case BIT_FIELD_REF: | |
142 | case COMPONENT_REF: | |
143 | case VIEW_CONVERT_EXPR: | |
144 | case ARRAY_RANGE_REF: | |
145 | nxt = &TREE_OPERAND (*addr_p, 0); | |
146 | break; | |
147 | ||
148 | case ARRAY_REF: | |
149 | nxt = &TREE_OPERAND (*addr_p, 0); | |
150 | if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data)) | |
151 | return false; | |
152 | break; | |
153 | ||
154 | case VAR_DECL: | |
155 | case PARM_DECL: | |
156 | case STRING_CST: | |
157 | case RESULT_DECL: | |
158 | return true; | |
159 | ||
160 | default: | |
161 | abort (); | |
162 | } | |
163 | } | |
164 | } | |
165 | ||
166 | /* If it is possible to hoist the statement STMT unconditionally, | |
167 | returns MOVE_POSSIBLE. | |
168 | If it is possible to hoist the statement STMT, but we must avoid making | |
169 | it executed if it would not be executed in the original program (e.g. | |
170 | because it may trap), return MOVE_PRESERVE_EXECUTION. | |
171 | Otherwise return MOVE_IMPOSSIBLE. */ | |
172 | ||
173 | static enum move_pos | |
174 | movement_possibility (tree stmt) | |
175 | { | |
176 | tree lhs, rhs; | |
177 | ||
178 | if (flag_unswitch_loops | |
179 | && TREE_CODE (stmt) == COND_EXPR) | |
180 | { | |
181 | /* If we perform unswitching, force the operands of the invariant | |
182 | condition to be moved out of the loop. */ | |
183 | get_stmt_operands (stmt); | |
184 | ||
185 | return MOVE_POSSIBLE; | |
186 | } | |
187 | ||
188 | if (TREE_CODE (stmt) != MODIFY_EXPR) | |
189 | return MOVE_IMPOSSIBLE; | |
190 | ||
191 | if (stmt_ends_bb_p (stmt)) | |
192 | return MOVE_IMPOSSIBLE; | |
193 | ||
194 | get_stmt_operands (stmt); | |
195 | ||
196 | if (stmt_ann (stmt)->has_volatile_ops) | |
197 | return MOVE_IMPOSSIBLE; | |
198 | ||
199 | lhs = TREE_OPERAND (stmt, 0); | |
200 | if (TREE_CODE (lhs) == SSA_NAME | |
201 | && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |
202 | return MOVE_IMPOSSIBLE; | |
203 | ||
204 | rhs = TREE_OPERAND (stmt, 1); | |
205 | ||
206 | if (TREE_SIDE_EFFECTS (rhs)) | |
207 | return MOVE_IMPOSSIBLE; | |
208 | ||
209 | if (TREE_CODE (lhs) != SSA_NAME | |
210 | || tree_could_trap_p (rhs)) | |
211 | return MOVE_PRESERVE_EXECUTION; | |
212 | ||
213 | return MOVE_POSSIBLE; | |
214 | } | |
215 | ||
216 | /* Suppose that operand DEF is used inside the LOOP. Returns the outermost | |
217 | loop to that we could move the expresion using DEF if it did not have | |
218 | other operands, i.e. the outermost loop enclosing LOOP in that the value | |
219 | of DEF is invariant. */ | |
220 | ||
221 | static struct loop * | |
222 | outermost_invariant_loop (tree def, struct loop *loop) | |
223 | { | |
224 | tree def_stmt; | |
225 | basic_block def_bb; | |
226 | struct loop *max_loop; | |
227 | ||
228 | if (TREE_CODE (def) != SSA_NAME) | |
229 | return superloop_at_depth (loop, 1); | |
230 | ||
231 | def_stmt = SSA_NAME_DEF_STMT (def); | |
232 | def_bb = bb_for_stmt (def_stmt); | |
233 | if (!def_bb) | |
234 | return superloop_at_depth (loop, 1); | |
235 | ||
236 | max_loop = find_common_loop (loop, def_bb->loop_father); | |
237 | ||
238 | if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop) | |
239 | max_loop = find_common_loop (max_loop, | |
240 | LIM_DATA (def_stmt)->max_loop->outer); | |
241 | if (max_loop == loop) | |
242 | return NULL; | |
243 | max_loop = superloop_at_depth (loop, max_loop->depth + 1); | |
244 | ||
245 | return max_loop; | |
246 | } | |
247 | ||
248 | /* Returns the outermost superloop of LOOP in that the expression EXPR is | |
249 | invariant. */ | |
250 | ||
251 | static struct loop * | |
252 | outermost_invariant_loop_expr (tree expr, struct loop *loop) | |
253 | { | |
254 | char class = TREE_CODE_CLASS (TREE_CODE (expr)); | |
255 | unsigned i, nops; | |
256 | struct loop *max_loop = superloop_at_depth (loop, 1), *aloop; | |
257 | ||
258 | if (TREE_CODE (expr) == SSA_NAME | |
259 | || TREE_CODE (expr) == INTEGER_CST | |
260 | || is_gimple_min_invariant (expr)) | |
261 | return outermost_invariant_loop (expr, loop); | |
262 | ||
263 | if (class != '1' | |
264 | && class != '2' | |
265 | && class != 'e' | |
266 | && class != '<') | |
267 | return NULL; | |
268 | ||
269 | nops = first_rtl_op (TREE_CODE (expr)); | |
270 | for (i = 0; i < nops; i++) | |
271 | { | |
272 | aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop); | |
273 | if (!aloop) | |
274 | return NULL; | |
275 | ||
276 | if (flow_loop_nested_p (max_loop, aloop)) | |
277 | max_loop = aloop; | |
278 | } | |
279 | ||
280 | return max_loop; | |
281 | } | |
282 | ||
283 | /* DATA is a structure containing information associated with a statement | |
284 | inside LOOP. DEF is one of the operands of this statement. | |
285 | ||
286 | Find the outermost loop enclosing LOOP in that value of DEF is invariant | |
287 | and record this in DATA->max_loop field. If DEF itself is defined inside | |
288 | this loop as well (i.e. we need to hoist it out of the loop if we want | |
289 | to hoist the statement represented by DATA), record the statement in that | |
290 | DEF is defined to the DATA->depends list. Additionally if ADD_COST is true, | |
291 | add the cost of the computation of DEF to the DATA->cost. | |
292 | ||
293 | If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */ | |
294 | ||
295 | static bool | |
296 | add_dependency (tree def, struct lim_aux_data *data, struct loop *loop, | |
297 | bool add_cost) | |
298 | { | |
299 | tree def_stmt = SSA_NAME_DEF_STMT (def); | |
300 | basic_block def_bb = bb_for_stmt (def_stmt); | |
301 | struct loop *max_loop; | |
302 | struct depend *dep; | |
303 | ||
304 | if (!def_bb) | |
305 | return true; | |
306 | ||
307 | max_loop = outermost_invariant_loop (def, loop); | |
308 | if (!max_loop) | |
309 | return false; | |
310 | ||
311 | if (flow_loop_nested_p (data->max_loop, max_loop)) | |
312 | data->max_loop = max_loop; | |
313 | ||
314 | if (!LIM_DATA (def_stmt)) | |
315 | return true; | |
316 | ||
317 | if (add_cost | |
318 | /* Only add the cost if the statement defining DEF is inside LOOP, | |
319 | i.e. if it is likely that by moving the invariants dependent | |
320 | on it, we will be able to avoid creating a new register for | |
321 | it (since it will be only used in these dependent invariants). */ | |
322 | && def_bb->loop_father == loop) | |
323 | data->cost += LIM_DATA (def_stmt)->cost; | |
324 | ||
325 | dep = xmalloc (sizeof (struct depend)); | |
326 | dep->stmt = def_stmt; | |
327 | dep->next = data->depends; | |
328 | data->depends = dep; | |
329 | ||
330 | return true; | |
331 | } | |
332 | ||
333 | /* Returns an estimate for a cost of statement STMT. TODO -- the values here | |
334 | are just ad-hoc constants. The estimates should be based on target-specific | |
335 | values. */ | |
336 | ||
337 | static unsigned | |
338 | stmt_cost (tree stmt) | |
339 | { | |
340 | tree lhs, rhs; | |
341 | unsigned cost = 1; | |
342 | ||
343 | /* Always try to create possibilities for unswitching. */ | |
344 | if (TREE_CODE (stmt) == COND_EXPR) | |
345 | return LIM_EXPENSIVE; | |
346 | ||
347 | lhs = TREE_OPERAND (stmt, 0); | |
348 | rhs = TREE_OPERAND (stmt, 1); | |
349 | ||
350 | /* Hoisting memory references out should almost surely be a win. */ | |
351 | if (!is_gimple_variable (lhs)) | |
352 | cost += 20; | |
e847cc68 | 353 | if (is_gimple_addressable (rhs) && !is_gimple_variable (rhs)) |
a7e5372d ZD |
354 | cost += 20; |
355 | ||
356 | switch (TREE_CODE (rhs)) | |
357 | { | |
358 | case CALL_EXPR: | |
359 | /* We should be hoisting calls if possible. */ | |
360 | ||
361 | /* Unless the call is a builtin_constant_p; this always folds to a | |
362 | constant, so moving it is useless. */ | |
363 | rhs = get_callee_fndecl (rhs); | |
364 | if (DECL_BUILT_IN (rhs) | |
365 | && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P) | |
366 | return 0; | |
367 | ||
368 | cost += 20; | |
369 | break; | |
370 | ||
371 | case MULT_EXPR: | |
372 | case TRUNC_DIV_EXPR: | |
373 | case CEIL_DIV_EXPR: | |
374 | case FLOOR_DIV_EXPR: | |
375 | case ROUND_DIV_EXPR: | |
376 | case EXACT_DIV_EXPR: | |
377 | case CEIL_MOD_EXPR: | |
378 | case FLOOR_MOD_EXPR: | |
379 | case ROUND_MOD_EXPR: | |
380 | case TRUNC_MOD_EXPR: | |
381 | /* Division and multiplication are usually expensive. */ | |
382 | cost += 20; | |
383 | break; | |
384 | ||
385 | default: | |
386 | break; | |
387 | } | |
388 | ||
389 | return cost; | |
390 | } | |
391 | ||
392 | /* Determine the outermost loop to that it is possible to hoist a statement | |
393 | STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine | |
394 | the outermost loop in that the value computed by STMT is invariant. | |
395 | If MUST_PRESERVE_EXEC is true, additionally choose such a loop that | |
396 | we preserve the fact whether STMT is executed. It also fills other related | |
397 | information to LIM_DATA (STMT). | |
398 | ||
399 | The function returns false if STMT cannot be hoisted outside of the loop it | |
400 | is defined in, and true otherwise. */ | |
401 | ||
402 | static bool | |
403 | determine_max_movement (tree stmt, bool must_preserve_exec) | |
404 | { | |
405 | basic_block bb = bb_for_stmt (stmt); | |
406 | struct loop *loop = bb->loop_father; | |
407 | struct loop *level; | |
408 | struct lim_aux_data *lim_data = LIM_DATA (stmt); | |
409 | use_optype uses; | |
410 | vuse_optype vuses; | |
411 | v_may_def_optype v_may_defs; | |
412 | stmt_ann_t ann = stmt_ann (stmt); | |
413 | unsigned i; | |
414 | ||
415 | if (must_preserve_exec) | |
416 | level = ALWAYS_EXECUTED_IN (bb); | |
417 | else | |
418 | level = superloop_at_depth (loop, 1); | |
419 | lim_data->max_loop = level; | |
420 | ||
421 | uses = USE_OPS (ann); | |
422 | for (i = 0; i < NUM_USES (uses); i++) | |
423 | if (!add_dependency (USE_OP (uses, i), lim_data, loop, true)) | |
424 | return false; | |
425 | ||
426 | vuses = VUSE_OPS (ann); | |
427 | for (i = 0; i < NUM_VUSES (vuses); i++) | |
428 | if (!add_dependency (VUSE_OP (vuses, i), lim_data, loop, false)) | |
429 | return false; | |
430 | ||
431 | v_may_defs = V_MAY_DEF_OPS (ann); | |
432 | for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) | |
433 | if (!add_dependency (V_MAY_DEF_OP (v_may_defs, i), lim_data, loop, false)) | |
434 | return false; | |
435 | ||
436 | lim_data->cost += stmt_cost (stmt); | |
437 | ||
438 | return true; | |
439 | } | |
440 | ||
441 | /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL, | |
442 | and that one of the operands of this statement is computed by STMT. | |
443 | Ensure that STMT (together with all the statements that define its | |
444 | operands) is hoisted at least out of the loop LEVEL. */ | |
445 | ||
446 | static void | |
447 | set_level (tree stmt, struct loop *orig_loop, struct loop *level) | |
448 | { | |
449 | struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father; | |
450 | struct depend *dep; | |
451 | ||
452 | stmt_loop = find_common_loop (orig_loop, stmt_loop); | |
453 | if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop) | |
454 | stmt_loop = find_common_loop (stmt_loop, | |
455 | LIM_DATA (stmt)->tgt_loop->outer); | |
456 | if (flow_loop_nested_p (stmt_loop, level)) | |
457 | return; | |
458 | ||
459 | if (!LIM_DATA (stmt)) | |
460 | abort (); | |
461 | ||
462 | if (level != LIM_DATA (stmt)->max_loop | |
463 | && !flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level)) | |
464 | abort (); | |
465 | ||
466 | LIM_DATA (stmt)->tgt_loop = level; | |
467 | for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next) | |
468 | set_level (dep->stmt, orig_loop, level); | |
469 | } | |
470 | ||
471 | /* Determines an outermost loop from that we want to hoist the statement STMT. | |
472 | For now we chose the outermost possible loop. TODO -- use profiling | |
473 | information to set it more sanely. */ | |
474 | ||
475 | static void | |
476 | set_profitable_level (tree stmt) | |
477 | { | |
478 | set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop); | |
479 | } | |
480 | ||
481 | /* Returns true if STMT is not a pure call. */ | |
482 | ||
483 | static bool | |
484 | nonpure_call_p (tree stmt) | |
485 | { | |
486 | tree call = get_call_expr_in (stmt); | |
487 | ||
488 | if (!call) | |
489 | return false; | |
490 | ||
491 | return TREE_SIDE_EFFECTS (call) != 0; | |
492 | } | |
493 | ||
494 | /* Releases the memory occupied by DATA. */ | |
495 | ||
496 | static void | |
497 | free_lim_aux_data (struct lim_aux_data *data) | |
498 | { | |
499 | struct depend *dep, *next; | |
500 | ||
501 | for (dep = data->depends; dep; dep = next) | |
502 | { | |
503 | next = dep->next; | |
504 | free (dep); | |
505 | } | |
506 | free (data); | |
507 | } | |
508 | ||
509 | /* Determine the outermost loops in that statements in basic block BB are | |
510 | invariant, and record them to the LIM_DATA associated with the statements. | |
511 | Callback for walk_dominator_tree. */ | |
512 | ||
513 | static void | |
514 | determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, | |
515 | basic_block bb) | |
516 | { | |
517 | enum move_pos pos; | |
518 | block_stmt_iterator bsi; | |
519 | tree stmt; | |
520 | bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL; | |
521 | struct loop *outermost = ALWAYS_EXECUTED_IN (bb); | |
522 | ||
523 | if (!bb->loop_father->outer) | |
524 | return; | |
525 | ||
526 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
527 | fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n", | |
528 | bb->index, bb->loop_father->num, bb->loop_father->depth); | |
529 | ||
530 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
531 | { | |
532 | stmt = bsi_stmt (bsi); | |
533 | ||
534 | pos = movement_possibility (stmt); | |
535 | if (pos == MOVE_IMPOSSIBLE) | |
536 | { | |
537 | if (nonpure_call_p (stmt)) | |
538 | { | |
539 | maybe_never = true; | |
540 | outermost = NULL; | |
541 | } | |
542 | continue; | |
543 | } | |
544 | ||
545 | stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); | |
546 | LIM_DATA (stmt)->always_executed_in = outermost; | |
547 | ||
548 | if (maybe_never && pos == MOVE_PRESERVE_EXECUTION) | |
549 | continue; | |
550 | ||
551 | if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION)) | |
552 | { | |
553 | LIM_DATA (stmt)->max_loop = NULL; | |
554 | continue; | |
555 | } | |
556 | ||
557 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
558 | { | |
559 | print_generic_stmt_indented (dump_file, stmt, 0, 2); | |
560 | fprintf (dump_file, " invariant up to level %d, cost %d.\n\n", | |
561 | LIM_DATA (stmt)->max_loop->depth, | |
562 | LIM_DATA (stmt)->cost); | |
563 | } | |
564 | ||
565 | if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE) | |
566 | set_profitable_level (stmt); | |
567 | } | |
568 | } | |
569 | ||
570 | /* For each statement determines the outermost loop in that it is invariant, | |
571 | statements on whose motion it depends and the cost of the computation. | |
572 | This information is stored to the LIM_DATA structure associated with | |
573 | each statement. */ | |
574 | ||
575 | static void | |
576 | determine_invariantness (void) | |
577 | { | |
578 | struct dom_walk_data walk_data; | |
579 | ||
580 | memset (&walk_data, 0, sizeof (struct dom_walk_data)); | |
581 | walk_data.before_dom_children_before_stmts = determine_invariantness_stmt; | |
582 | ||
583 | init_walk_dominator_tree (&walk_data); | |
584 | walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | |
585 | fini_walk_dominator_tree (&walk_data); | |
586 | } | |
587 | ||
588 | /* Commits edge insertions and updates loop structures. */ | |
589 | ||
590 | void | |
591 | loop_commit_inserts (void) | |
592 | { | |
593 | unsigned old_last_basic_block, i; | |
594 | basic_block bb; | |
595 | ||
596 | old_last_basic_block = last_basic_block; | |
597 | bsi_commit_edge_inserts (NULL); | |
598 | for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++) | |
599 | { | |
600 | bb = BASIC_BLOCK (i); | |
601 | add_bb_to_loop (bb, | |
602 | find_common_loop (bb->succ->dest->loop_father, | |
603 | bb->pred->src->loop_father)); | |
604 | } | |
605 | } | |
606 | ||
607 | /* Hoist the statements in basic block BB out of the loops prescribed by | |
608 | data stored in LIM_DATA structres associated with each statement. Callback | |
609 | for walk_dominator_tree. */ | |
610 | ||
611 | static void | |
612 | move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED, | |
613 | basic_block bb) | |
614 | { | |
615 | struct loop *level; | |
616 | block_stmt_iterator bsi; | |
617 | tree stmt; | |
618 | unsigned cost = 0; | |
619 | ||
620 | if (!bb->loop_father->outer) | |
621 | return; | |
622 | ||
623 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) | |
624 | { | |
625 | stmt = bsi_stmt (bsi); | |
626 | ||
627 | if (!LIM_DATA (stmt)) | |
628 | { | |
629 | bsi_next (&bsi); | |
630 | continue; | |
631 | } | |
632 | ||
633 | cost = LIM_DATA (stmt)->cost; | |
634 | level = LIM_DATA (stmt)->tgt_loop; | |
635 | free_lim_aux_data (LIM_DATA (stmt)); | |
636 | stmt_ann (stmt)->common.aux = NULL; | |
637 | ||
638 | if (!level) | |
639 | { | |
640 | bsi_next (&bsi); | |
641 | continue; | |
642 | } | |
643 | ||
644 | /* We do not really want to move conditionals out of the loop; we just | |
645 | placed it here to force its operands to be moved if necessary. */ | |
646 | if (TREE_CODE (stmt) == COND_EXPR) | |
647 | continue; | |
648 | ||
649 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
650 | { | |
651 | fprintf (dump_file, "Moving statement\n"); | |
652 | print_generic_stmt (dump_file, stmt, 0); | |
653 | fprintf (dump_file, "(cost %u) out of loop %d.\n\n", | |
654 | cost, level->num); | |
655 | } | |
656 | bsi_insert_on_edge (loop_preheader_edge (level), stmt); | |
657 | bsi_remove (&bsi); | |
658 | } | |
659 | } | |
660 | ||
661 | /* Hoist the statements out of the loops prescribed by data stored in | |
662 | LIM_DATA structres associated with each statement.*/ | |
663 | ||
664 | static void | |
665 | move_computations (void) | |
666 | { | |
667 | struct dom_walk_data walk_data; | |
668 | ||
669 | memset (&walk_data, 0, sizeof (struct dom_walk_data)); | |
670 | walk_data.before_dom_children_before_stmts = move_computations_stmt; | |
671 | ||
672 | init_walk_dominator_tree (&walk_data); | |
673 | walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | |
674 | fini_walk_dominator_tree (&walk_data); | |
675 | ||
676 | loop_commit_inserts (); | |
677 | rewrite_into_ssa (false); | |
678 | bitmap_clear (vars_to_rename); | |
679 | } | |
680 | ||
681 | /* Checks whether the statement defining variable *INDEX can be hoisted | |
682 | out of the loop passed in DATA. Callback for for_each_index. */ | |
683 | ||
684 | static bool | |
685 | may_move_till (tree ref, tree *index, void *data) | |
686 | { | |
687 | struct loop *loop = data, *max_loop; | |
688 | ||
689 | /* If REF is an array reference, check also that the step and the lower | |
690 | bound is invariant in LOOP. */ | |
691 | if (TREE_CODE (ref) == ARRAY_REF) | |
692 | { | |
693 | tree step = array_ref_element_size (ref); | |
694 | tree lbound = array_ref_low_bound (ref); | |
695 | ||
696 | max_loop = outermost_invariant_loop_expr (step, loop); | |
697 | if (!max_loop) | |
698 | return false; | |
699 | ||
700 | max_loop = outermost_invariant_loop_expr (lbound, loop); | |
701 | if (!max_loop) | |
702 | return false; | |
703 | } | |
704 | ||
705 | max_loop = outermost_invariant_loop (*index, loop); | |
706 | if (!max_loop) | |
707 | return false; | |
708 | ||
709 | return true; | |
710 | } | |
711 | ||
712 | /* Forces statements definining (invariant) SSA names in expression EXPR to be | |
b4042a03 | 713 | moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */ |
a7e5372d ZD |
714 | |
715 | static void | |
b4042a03 | 716 | force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop) |
a7e5372d ZD |
717 | { |
718 | char class = TREE_CODE_CLASS (TREE_CODE (expr)); | |
719 | unsigned i, nops; | |
720 | ||
721 | if (TREE_CODE (expr) == SSA_NAME) | |
722 | { | |
723 | tree stmt = SSA_NAME_DEF_STMT (expr); | |
724 | if (IS_EMPTY_STMT (stmt)) | |
725 | return; | |
726 | ||
b4042a03 | 727 | set_level (stmt, orig_loop, loop); |
a7e5372d ZD |
728 | return; |
729 | } | |
730 | ||
731 | if (class != '1' | |
732 | && class != '2' | |
733 | && class != 'e' | |
734 | && class != '<') | |
735 | return; | |
736 | ||
737 | nops = first_rtl_op (TREE_CODE (expr)); | |
738 | for (i = 0; i < nops; i++) | |
b4042a03 | 739 | force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop); |
a7e5372d ZD |
740 | } |
741 | ||
742 | /* Forces statement defining invariants in REF (and *INDEX) to be moved out of | |
b4042a03 ZD |
743 | the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for |
744 | for_each_index. */ | |
745 | ||
746 | struct fmt_data | |
747 | { | |
748 | struct loop *loop; | |
749 | struct loop *orig_loop; | |
750 | }; | |
a7e5372d ZD |
751 | |
752 | static bool | |
753 | force_move_till (tree ref, tree *index, void *data) | |
754 | { | |
755 | tree stmt; | |
b4042a03 | 756 | struct fmt_data *fmt_data = data; |
a7e5372d ZD |
757 | |
758 | if (TREE_CODE (ref) == ARRAY_REF) | |
759 | { | |
760 | tree step = array_ref_element_size (ref); | |
761 | tree lbound = array_ref_low_bound (ref); | |
762 | ||
b4042a03 ZD |
763 | force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop); |
764 | force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop); | |
a7e5372d ZD |
765 | } |
766 | ||
767 | if (TREE_CODE (*index) != SSA_NAME) | |
768 | return true; | |
769 | ||
770 | stmt = SSA_NAME_DEF_STMT (*index); | |
771 | if (IS_EMPTY_STMT (stmt)) | |
772 | return true; | |
773 | ||
b4042a03 | 774 | set_level (stmt, fmt_data->orig_loop, fmt_data->loop); |
a7e5372d ZD |
775 | |
776 | return true; | |
777 | } | |
778 | ||
779 | /* Records memory reference *REF (that occurs in statement STMT) | |
780 | to the list MEM_REFS. */ | |
781 | ||
782 | static void | |
783 | record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref) | |
784 | { | |
785 | struct mem_ref *aref = xmalloc (sizeof (struct mem_ref)); | |
786 | ||
787 | aref->stmt = stmt; | |
788 | aref->ref = ref; | |
789 | ||
790 | aref->next = *mem_refs; | |
791 | *mem_refs = aref; | |
792 | } | |
793 | ||
794 | /* Releases list of memory references MEM_REFS. */ | |
795 | ||
796 | static void | |
797 | free_mem_refs (struct mem_ref *mem_refs) | |
798 | { | |
799 | struct mem_ref *act; | |
800 | ||
801 | while (mem_refs) | |
802 | { | |
803 | act = mem_refs; | |
804 | mem_refs = mem_refs->next; | |
805 | free (act); | |
806 | } | |
807 | } | |
808 | ||
809 | /* If VAR is defined in LOOP and the statement it is defined in does not belong | |
810 | to the set SEEN, add the statement to QUEUE of length IN_QUEUE and | |
811 | to the set SEEN. */ | |
812 | ||
813 | static void | |
814 | maybe_queue_var (tree var, struct loop *loop, | |
815 | sbitmap seen, tree *queue, unsigned *in_queue) | |
816 | { | |
817 | tree stmt = SSA_NAME_DEF_STMT (var); | |
818 | basic_block def_bb = bb_for_stmt (stmt); | |
819 | ||
820 | if (!def_bb | |
821 | || !flow_bb_inside_loop_p (loop, def_bb) | |
822 | || TEST_BIT (seen, stmt_ann (stmt)->uid)) | |
823 | return; | |
824 | ||
825 | SET_BIT (seen, stmt_ann (stmt)->uid); | |
826 | queue[(*in_queue)++] = stmt; | |
827 | } | |
828 | ||
829 | /* Determine whether all memory references inside the LOOP that correspond | |
830 | to virtual ssa names defined in statement STMT are equal. | |
831 | If so, store the list of the references to MEM_REFS, and return one | |
832 | of them. Otherwise store NULL to MEM_REFS and return NULL_TREE. */ | |
833 | ||
834 | static tree | |
835 | single_reachable_address (struct loop *loop, tree stmt, | |
836 | struct mem_ref **mem_refs) | |
837 | { | |
838 | tree *queue = xmalloc (sizeof (tree) * max_uid); | |
839 | sbitmap seen = sbitmap_alloc (max_uid); | |
840 | tree common_ref = NULL, *aref; | |
841 | unsigned in_queue = 1; | |
842 | dataflow_t df; | |
843 | unsigned i, n; | |
844 | v_may_def_optype v_may_defs; | |
845 | vuse_optype vuses; | |
846 | ||
847 | sbitmap_zero (seen); | |
848 | ||
849 | *mem_refs = NULL; | |
850 | ||
851 | queue[0] = stmt; | |
852 | SET_BIT (seen, stmt_ann (stmt)->uid); | |
853 | ||
854 | while (in_queue) | |
855 | { | |
856 | stmt = queue[--in_queue]; | |
857 | ||
858 | if (LIM_DATA (stmt) | |
859 | && LIM_DATA (stmt)->sm_done) | |
860 | goto fail; | |
861 | ||
862 | switch (TREE_CODE (stmt)) | |
863 | { | |
864 | case MODIFY_EXPR: | |
865 | aref = &TREE_OPERAND (stmt, 0); | |
866 | if (is_gimple_reg (*aref) | |
867 | || !is_gimple_lvalue (*aref)) | |
868 | aref = &TREE_OPERAND (stmt, 1); | |
869 | if (is_gimple_reg (*aref) | |
870 | || !is_gimple_lvalue (*aref) | |
871 | || (common_ref && !operand_equal_p (*aref, common_ref, 0))) | |
872 | goto fail; | |
873 | common_ref = *aref; | |
874 | ||
875 | record_mem_ref (mem_refs, stmt, aref); | |
876 | ||
877 | /* Traverse also definitions of the VUSES (there may be other | |
878 | distinct from the one we used to get to this statement). */ | |
879 | v_may_defs = STMT_V_MAY_DEF_OPS (stmt); | |
880 | for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) | |
881 | maybe_queue_var (V_MAY_DEF_OP (v_may_defs, i), loop, | |
882 | seen, queue, &in_queue); | |
883 | ||
884 | vuses = STMT_VUSE_OPS (stmt); | |
885 | for (i = 0; i < NUM_VUSES (vuses); i++) | |
886 | maybe_queue_var (VUSE_OP (vuses, i), loop, | |
887 | seen, queue, &in_queue); | |
888 | break; | |
889 | ||
890 | case PHI_NODE: | |
891 | for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++) | |
892 | maybe_queue_var (PHI_ARG_DEF (stmt, i), loop, | |
893 | seen, queue, &in_queue); | |
894 | break; | |
895 | ||
896 | default: | |
897 | goto fail; | |
898 | } | |
899 | ||
900 | /* Find uses of virtual names. */ | |
901 | df = get_immediate_uses (stmt); | |
902 | n = num_immediate_uses (df); | |
903 | ||
904 | for (i = 0; i < n; i++) | |
905 | { | |
906 | stmt = immediate_use (df, i); | |
907 | ||
908 | if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt))) | |
909 | continue; | |
910 | ||
911 | if (TEST_BIT (seen, stmt_ann (stmt)->uid)) | |
912 | continue; | |
913 | SET_BIT (seen, stmt_ann (stmt)->uid); | |
914 | ||
915 | queue[in_queue++] = stmt; | |
916 | } | |
917 | } | |
918 | ||
919 | free (queue); | |
920 | sbitmap_free (seen); | |
921 | ||
922 | return common_ref; | |
923 | ||
924 | fail: | |
925 | free_mem_refs (*mem_refs); | |
926 | *mem_refs = NULL; | |
927 | free (queue); | |
928 | sbitmap_free (seen); | |
929 | ||
930 | return NULL; | |
931 | } | |
932 | ||
933 | /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */ | |
934 | ||
935 | static void | |
936 | rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs) | |
937 | { | |
938 | v_may_def_optype v_may_defs; | |
939 | v_must_def_optype v_must_defs; | |
940 | vuse_optype vuses; | |
941 | unsigned i; | |
942 | tree var; | |
943 | ||
944 | for (; mem_refs; mem_refs = mem_refs->next) | |
945 | { | |
946 | v_may_defs = STMT_V_MAY_DEF_OPS (mem_refs->stmt); | |
947 | for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++) | |
948 | { | |
949 | var = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, i)); | |
950 | bitmap_set_bit (vars_to_rename, var_ann (var)->uid); | |
951 | } | |
952 | ||
953 | v_must_defs = STMT_V_MUST_DEF_OPS (mem_refs->stmt); | |
954 | for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++) | |
955 | { | |
956 | var = SSA_NAME_VAR (V_MUST_DEF_OP (v_must_defs, i)); | |
957 | bitmap_set_bit (vars_to_rename, var_ann (var)->uid); | |
958 | } | |
959 | ||
960 | vuses = STMT_VUSE_OPS (mem_refs->stmt); | |
961 | for (i = 0; i < NUM_VUSES (vuses); i++) | |
962 | { | |
963 | var = SSA_NAME_VAR (VUSE_OP (vuses, i)); | |
964 | bitmap_set_bit (vars_to_rename, var_ann (var)->uid); | |
965 | } | |
966 | ||
967 | *mem_refs->ref = tmp_var; | |
968 | modify_stmt (mem_refs->stmt); | |
969 | } | |
970 | } | |
971 | ||
972 | /* Records request for store motion of memory reference REF from LOOP. | |
973 | MEM_REFS is the list of occurences of the reference REF inside LOOP; | |
974 | these references are rewritten by a new temporary variable. | |
975 | Exits from the LOOP are stored in EXITS, there are N_EXITS of them. | |
976 | The initialization of the temporary variable is put to the preheader | |
977 | of the loop, and assignments to the reference from the temporary variable | |
978 | are emitted to exits. */ | |
979 | ||
980 | static void | |
981 | schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref, | |
982 | struct mem_ref *mem_refs) | |
983 | { | |
984 | struct mem_ref *aref; | |
985 | tree tmp_var; | |
986 | unsigned i; | |
987 | tree load, store; | |
b4042a03 | 988 | struct fmt_data fmt_data; |
a7e5372d ZD |
989 | |
990 | tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp"); | |
991 | ||
b4042a03 ZD |
992 | fmt_data.loop = loop; |
993 | fmt_data.orig_loop = loop; | |
994 | for_each_index (&ref, force_move_till, &fmt_data); | |
a7e5372d ZD |
995 | |
996 | rewrite_mem_refs (tmp_var, mem_refs); | |
997 | for (aref = mem_refs; aref; aref = aref->next) | |
998 | if (LIM_DATA (aref->stmt)) | |
999 | LIM_DATA (aref->stmt)->sm_done = true; | |
1000 | ||
1001 | /* Emit the load & stores. */ | |
1002 | load = build (MODIFY_EXPR, void_type_node, tmp_var, ref); | |
1003 | modify_stmt (load); | |
1004 | stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data)); | |
1005 | LIM_DATA (load)->max_loop = loop; | |
1006 | LIM_DATA (load)->tgt_loop = loop; | |
1007 | ||
1008 | /* Put this into the latch, so that we are sure it will be processed after | |
1009 | all dependencies. */ | |
1010 | bsi_insert_on_edge (loop_latch_edge (loop), load); | |
1011 | ||
1012 | for (i = 0; i < n_exits; i++) | |
1013 | { | |
1014 | store = build (MODIFY_EXPR, void_type_node, | |
1015 | unshare_expr (ref), tmp_var); | |
1016 | bsi_insert_on_edge (exits[i], store); | |
1017 | } | |
1018 | } | |
1019 | ||
1020 | /* Determine whether all memory references inside LOOP corresponding to the | |
1021 | virtual ssa name REG are equal to each other, and whether the address of | |
1022 | this common reference can be hoisted outside of the loop. If this is true, | |
1023 | prepare the statements that load the value of the memory reference to a | |
1024 | temporary variable in the loop preheader, store it back on the loop exits, | |
1025 | and replace all the references inside LOOP by this temporary variable. | |
1026 | LOOP has N_EXITS stored in EXITS. */ | |
1027 | ||
1028 | static void | |
1029 | determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg) | |
1030 | { | |
1031 | tree ref; | |
1032 | struct mem_ref *mem_refs, *aref; | |
1033 | struct loop *must_exec; | |
1034 | ||
1035 | if (is_gimple_reg (reg)) | |
1036 | return; | |
1037 | ||
1038 | ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs); | |
1039 | if (!ref) | |
1040 | return; | |
1041 | ||
1042 | if (!for_each_index (&ref, may_move_till, loop)) | |
1043 | { | |
1044 | free_mem_refs (mem_refs); | |
1045 | return; | |
1046 | } | |
1047 | ||
1048 | if (tree_could_trap_p (ref)) | |
1049 | { | |
1050 | /* If the memory access is unsafe (i.e. it might trap), ensure that some | |
1051 | of the statements in that it occurs is always executed when the loop | |
1052 | is entered. This way we know that by moving the load from the | |
1053 | reference out of the loop we will not cause the error that would not | |
1054 | occur otherwise. | |
1055 | ||
1056 | TODO -- in fact we would like to check for anticipability of the | |
1057 | reference, i.e. that on each path from loop entry to loop exit at | |
1058 | least one of the statements containing the memory reference is | |
1059 | executed. */ | |
1060 | ||
1061 | for (aref = mem_refs; aref; aref = aref->next) | |
1062 | { | |
1063 | if (!LIM_DATA (aref->stmt)) | |
1064 | continue; | |
1065 | ||
1066 | must_exec = LIM_DATA (aref->stmt)->always_executed_in; | |
1067 | if (!must_exec) | |
1068 | continue; | |
1069 | ||
1070 | if (must_exec == loop | |
1071 | || flow_loop_nested_p (must_exec, loop)) | |
1072 | break; | |
1073 | } | |
1074 | ||
1075 | if (!aref) | |
1076 | { | |
1077 | free_mem_refs (mem_refs); | |
1078 | return; | |
1079 | } | |
1080 | } | |
1081 | ||
1082 | schedule_sm (loop, exits, n_exits, ref, mem_refs); | |
1083 | free_mem_refs (mem_refs); | |
1084 | } | |
1085 | ||
1086 | /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable | |
1087 | for a store motion optimization (i.e. whether we can insert statement | |
1088 | on its exits). */ | |
1089 | ||
1090 | static bool | |
1091 | loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits, | |
1092 | unsigned n_exits) | |
1093 | { | |
1094 | unsigned i; | |
1095 | ||
1096 | for (i = 0; i < n_exits; i++) | |
1097 | if (exits[i]->flags & EDGE_ABNORMAL) | |
1098 | return false; | |
1099 | ||
1100 | return true; | |
1101 | } | |
1102 | ||
1103 | /* Try to perform store motion for all memory references modified inside | |
1104 | LOOP. */ | |
1105 | ||
1106 | static void | |
1107 | determine_lsm_loop (struct loop *loop) | |
1108 | { | |
1109 | tree phi; | |
1110 | unsigned n_exits; | |
1111 | edge *exits = get_loop_exit_edges (loop, &n_exits); | |
1112 | ||
1113 | if (!loop_suitable_for_sm (loop, exits, n_exits)) | |
1114 | { | |
1115 | free (exits); | |
1116 | return; | |
1117 | } | |
1118 | ||
1119 | for (phi = phi_nodes (loop->header); phi; phi = TREE_CHAIN (phi)) | |
1120 | determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi)); | |
1121 | ||
1122 | free (exits); | |
1123 | } | |
1124 | ||
1125 | /* Try to perform store motion for all memory references modified inside | |
1126 | any of LOOPS. */ | |
1127 | ||
1128 | static void | |
1129 | determine_lsm (struct loops *loops) | |
1130 | { | |
1131 | struct loop *loop; | |
1132 | basic_block bb; | |
1133 | ||
1134 | /* Create a UID for each statement in the function. Ordering of the | |
1135 | UIDs is not important for this pass. */ | |
1136 | max_uid = 0; | |
1137 | FOR_EACH_BB (bb) | |
1138 | { | |
1139 | block_stmt_iterator bsi; | |
1140 | tree phi; | |
1141 | ||
1142 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
1143 | stmt_ann (bsi_stmt (bsi))->uid = max_uid++; | |
1144 | ||
1145 | for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) | |
1146 | stmt_ann (phi)->uid = max_uid++; | |
1147 | } | |
1148 | ||
1149 | compute_immediate_uses (TDFA_USE_VOPS, NULL); | |
1150 | ||
1151 | /* Pass the loops from the outermost. For each virtual operand loop phi node | |
1152 | check whether all the references inside the loop correspond to a single | |
1153 | address, and if so, move them. */ | |
1154 | ||
1155 | loop = loops->tree_root->inner; | |
1156 | while (1) | |
1157 | { | |
1158 | determine_lsm_loop (loop); | |
1159 | ||
1160 | if (loop->inner) | |
1161 | { | |
1162 | loop = loop->inner; | |
1163 | continue; | |
1164 | } | |
1165 | while (!loop->next) | |
1166 | { | |
1167 | loop = loop->outer; | |
1168 | if (loop == loops->tree_root) | |
1169 | { | |
1170 | free_df (); | |
1171 | loop_commit_inserts (); | |
1172 | return; | |
1173 | } | |
1174 | } | |
1175 | loop = loop->next; | |
1176 | } | |
1177 | } | |
1178 | ||
1179 | /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e. | |
1180 | for each such basic block bb records the outermost loop for that execution | |
1181 | of its header implies execution of bb. CONTAINS_CALL is the bitmap of | |
1182 | blocks that contain a nonpure call. */ | |
1183 | ||
1184 | static void | |
1185 | fill_always_executed_in (struct loop *loop, sbitmap contains_call) | |
1186 | { | |
1187 | basic_block bb = NULL, *bbs, last = NULL; | |
1188 | unsigned i; | |
1189 | edge e; | |
1190 | struct loop *inn_loop = loop; | |
1191 | ||
1192 | if (!loop->header->aux) | |
1193 | { | |
1194 | bbs = get_loop_body_in_dom_order (loop); | |
1195 | ||
1196 | for (i = 0; i < loop->num_nodes; i++) | |
1197 | { | |
1198 | bb = bbs[i]; | |
1199 | ||
1200 | if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) | |
1201 | last = bb; | |
1202 | ||
1203 | if (TEST_BIT (contains_call, bb->index)) | |
1204 | break; | |
1205 | ||
1206 | for (e = bb->succ; e; e = e->succ_next) | |
1207 | if (!flow_bb_inside_loop_p (loop, e->dest)) | |
1208 | break; | |
1209 | if (e) | |
1210 | break; | |
1211 | ||
1212 | /* A loop might be infinite (TODO use simple loop analysis | |
1213 | to disprove this if possible). */ | |
1214 | if (bb->flags & BB_IRREDUCIBLE_LOOP) | |
1215 | break; | |
1216 | ||
1217 | if (!flow_bb_inside_loop_p (inn_loop, bb)) | |
1218 | break; | |
1219 | ||
1220 | if (bb->loop_father->header == bb) | |
1221 | { | |
1222 | if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) | |
1223 | break; | |
1224 | ||
1225 | /* In a loop that is always entered we may proceed anyway. | |
1226 | But record that we entered it and stop once we leave it. */ | |
1227 | inn_loop = bb->loop_father; | |
1228 | } | |
1229 | } | |
1230 | ||
1231 | while (1) | |
1232 | { | |
1233 | last->aux = loop; | |
1234 | if (last == loop->header) | |
1235 | break; | |
1236 | last = get_immediate_dominator (CDI_DOMINATORS, last); | |
1237 | } | |
1238 | ||
1239 | free (bbs); | |
1240 | } | |
1241 | ||
1242 | for (loop = loop->inner; loop; loop = loop->next) | |
1243 | fill_always_executed_in (loop, contains_call); | |
1244 | } | |
1245 | ||
1246 | /* Compute the global information needed by the loop invariant motion pass. | |
1247 | LOOPS is the loop tree. */ | |
1248 | ||
1249 | static void | |
1250 | tree_ssa_lim_initialize (struct loops *loops) | |
1251 | { | |
1252 | sbitmap contains_call = sbitmap_alloc (last_basic_block); | |
1253 | block_stmt_iterator bsi; | |
1254 | struct loop *loop; | |
1255 | basic_block bb; | |
1256 | ||
1257 | sbitmap_zero (contains_call); | |
1258 | FOR_EACH_BB (bb) | |
1259 | { | |
1260 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
1261 | { | |
1262 | if (nonpure_call_p (bsi_stmt (bsi))) | |
1263 | break; | |
1264 | } | |
1265 | ||
1266 | if (!bsi_end_p (bsi)) | |
1267 | SET_BIT (contains_call, bb->index); | |
1268 | } | |
1269 | ||
1270 | for (loop = loops->tree_root->inner; loop; loop = loop->next) | |
1271 | fill_always_executed_in (loop, contains_call); | |
1272 | ||
1273 | sbitmap_free (contains_call); | |
1274 | } | |
1275 | ||
1276 | /* Cleans up after the invariant motion pass. */ | |
1277 | ||
1278 | static void | |
1279 | tree_ssa_lim_finalize (void) | |
1280 | { | |
1281 | basic_block bb; | |
1282 | ||
1283 | FOR_EACH_BB (bb) | |
1284 | { | |
1285 | bb->aux = NULL; | |
1286 | } | |
1287 | } | |
1288 | ||
1289 | /* Moves invariants from LOOPS. Only "expensive" invariants are moved out -- | |
1290 | i.e. those that are likely to be win regardless of the register pressure. */ | |
1291 | ||
1292 | void | |
1293 | tree_ssa_lim (struct loops *loops) | |
1294 | { | |
1295 | tree_ssa_lim_initialize (loops); | |
1296 | ||
1297 | /* For each statement determine the outermost loop in that it is | |
1298 | invariant and cost for computing the invariant. */ | |
1299 | determine_invariantness (); | |
1300 | ||
1301 | /* For each memory reference determine whether it is possible to hoist it | |
1302 | out of the loop. Force the necessary invariants to be moved out of the | |
1303 | loops as well. */ | |
1304 | determine_lsm (loops); | |
1305 | ||
1306 | /* Move the expressions that are expensive enough. */ | |
1307 | move_computations (); | |
1308 | ||
1309 | tree_ssa_lim_finalize (); | |
1310 | } |