Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-im.c
blob83ad70c2890528843160a4c26b7a1903c9bc5420
1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
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 3, or (at your option) any
9 later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
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"
38 #include "flags.h"
39 #include "real.h"
40 #include "hashtab.h"
42 /* TODO: Support for predicated code motion. I.e.
44 while (1)
46 if (cond)
48 a = inv;
49 something;
53 Where COND and INV are is invariants, but evaluating INV may trap or be
54 invalid from some other reason if !COND. This may be transformed to
56 if (cond)
57 a = inv;
58 while (1)
60 if (cond)
61 something;
62 } */
64 /* A type for the list of statements that have to be moved in order to be able
65 to hoist an invariant computation. */
67 struct depend
69 tree stmt;
70 struct depend *next;
73 /* The auxiliary data kept for each statement. */
75 struct lim_aux_data
77 struct loop *max_loop; /* The outermost loop in that the statement
78 is invariant. */
80 struct loop *tgt_loop; /* The loop out of that we want to move the
81 invariant. */
83 struct loop *always_executed_in;
84 /* The outermost loop for that we are sure
85 the statement is executed if the loop
86 is entered. */
88 bool sm_done; /* True iff the store motion for a memory
89 reference in the statement has already
90 been executed. */
92 unsigned cost; /* Cost of the computation performed by the
93 statement. */
95 struct depend *depends; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
99 MAX_LOOP loop. */
102 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
103 ? NULL \
104 : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
106 /* Description of a memory reference location for store motion. */
108 struct mem_ref_loc
110 tree *ref; /* The reference itself. */
111 tree stmt; /* The statement in that it occurs. */
112 struct mem_ref_loc *next; /* Next use in the chain. */
115 /* Description of a memory reference for store motion. */
117 struct mem_ref
119 tree mem; /* The memory itself. */
120 hashval_t hash; /* Its hash value. */
121 bool is_stored; /* True if there is a store to the location
122 in the loop. */
123 struct mem_ref_loc *locs; /* The locations where it is found. */
124 bitmap vops; /* Vops corresponding to this memory
125 location. */
126 struct mem_ref *next; /* Next memory reference in the list.
127 Memory references are stored in a hash
128 table, but the hash function depends
129 on values of pointers. Thus we cannot use
130 htab_traverse, since then we would get
131 miscompares during bootstrap (although the
132 produced code would be correct). */
135 /* Minimum cost of an expensive expression. */
136 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
138 /* The outermost loop for that execution of the header guarantees that the
139 block will be executed. */
140 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
142 /* Calls CBCK for each index in memory reference ADDR_P. There are two
143 kinds situations handled; in each of these cases, the memory reference
144 and DATA are passed to the callback:
146 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
147 pass the pointer to the index to the callback.
149 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
150 pointer to addr to the callback.
152 If the callback returns false, the whole search stops and false is returned.
153 Otherwise the function returns true after traversing through the whole
154 reference *ADDR_P. */
156 bool
157 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
159 tree *nxt, *idx;
161 for (; ; addr_p = nxt)
163 switch (TREE_CODE (*addr_p))
165 case SSA_NAME:
166 return cbck (*addr_p, addr_p, data);
168 case MISALIGNED_INDIRECT_REF:
169 case ALIGN_INDIRECT_REF:
170 case INDIRECT_REF:
171 nxt = &TREE_OPERAND (*addr_p, 0);
172 return cbck (*addr_p, nxt, data);
174 case BIT_FIELD_REF:
175 case VIEW_CONVERT_EXPR:
176 case REALPART_EXPR:
177 case IMAGPART_EXPR:
178 nxt = &TREE_OPERAND (*addr_p, 0);
179 break;
181 case COMPONENT_REF:
182 /* If the component has varying offset, it behaves like index
183 as well. */
184 idx = &TREE_OPERAND (*addr_p, 2);
185 if (*idx
186 && !cbck (*addr_p, idx, data))
187 return false;
189 nxt = &TREE_OPERAND (*addr_p, 0);
190 break;
192 case ARRAY_REF:
193 case ARRAY_RANGE_REF:
194 nxt = &TREE_OPERAND (*addr_p, 0);
195 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
196 return false;
197 break;
199 case VAR_DECL:
200 case PARM_DECL:
201 case STRING_CST:
202 case RESULT_DECL:
203 case VECTOR_CST:
204 case COMPLEX_CST:
205 case INTEGER_CST:
206 case REAL_CST:
207 case FIXED_CST:
208 return true;
210 case TARGET_MEM_REF:
211 idx = &TMR_BASE (*addr_p);
212 if (*idx
213 && !cbck (*addr_p, idx, data))
214 return false;
215 idx = &TMR_INDEX (*addr_p);
216 if (*idx
217 && !cbck (*addr_p, idx, data))
218 return false;
219 return true;
221 default:
222 gcc_unreachable ();
227 /* If it is possible to hoist the statement STMT unconditionally,
228 returns MOVE_POSSIBLE.
229 If it is possible to hoist the statement STMT, but we must avoid making
230 it executed if it would not be executed in the original program (e.g.
231 because it may trap), return MOVE_PRESERVE_EXECUTION.
232 Otherwise return MOVE_IMPOSSIBLE. */
234 enum move_pos
235 movement_possibility (tree stmt)
237 tree lhs, rhs;
239 if (flag_unswitch_loops
240 && TREE_CODE (stmt) == COND_EXPR)
242 /* If we perform unswitching, force the operands of the invariant
243 condition to be moved out of the loop. */
244 return MOVE_POSSIBLE;
247 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
248 return MOVE_IMPOSSIBLE;
250 if (stmt_ends_bb_p (stmt))
251 return MOVE_IMPOSSIBLE;
253 if (stmt_ann (stmt)->has_volatile_ops)
254 return MOVE_IMPOSSIBLE;
256 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
257 if (TREE_CODE (lhs) == SSA_NAME
258 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
259 return MOVE_IMPOSSIBLE;
261 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
263 if (TREE_SIDE_EFFECTS (rhs)
264 || tree_could_throw_p (rhs))
265 return MOVE_IMPOSSIBLE;
267 if (TREE_CODE (lhs) != SSA_NAME
268 || tree_could_trap_p (rhs))
269 return MOVE_PRESERVE_EXECUTION;
271 if (get_call_expr_in (stmt))
273 /* While pure or const call is guaranteed to have no side effects, we
274 cannot move it arbitrarily. Consider code like
276 char *s = something ();
278 while (1)
280 if (s)
281 t = strlen (s);
282 else
283 t = 0;
286 Here the strlen call cannot be moved out of the loop, even though
287 s is invariant. In addition to possibly creating a call with
288 invalid arguments, moving out a function call that is not executed
289 may cause performance regressions in case the call is costly and
290 not executed at all. */
291 return MOVE_PRESERVE_EXECUTION;
293 return MOVE_POSSIBLE;
296 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
297 loop to that we could move the expression using DEF if it did not have
298 other operands, i.e. the outermost loop enclosing LOOP in that the value
299 of DEF is invariant. */
301 static struct loop *
302 outermost_invariant_loop (tree def, struct loop *loop)
304 tree def_stmt;
305 basic_block def_bb;
306 struct loop *max_loop;
308 if (TREE_CODE (def) != SSA_NAME)
309 return superloop_at_depth (loop, 1);
311 def_stmt = SSA_NAME_DEF_STMT (def);
312 def_bb = bb_for_stmt (def_stmt);
313 if (!def_bb)
314 return superloop_at_depth (loop, 1);
316 max_loop = find_common_loop (loop, def_bb->loop_father);
318 if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
319 max_loop = find_common_loop (max_loop,
320 loop_outer (LIM_DATA (def_stmt)->max_loop));
321 if (max_loop == loop)
322 return NULL;
323 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
325 return max_loop;
328 /* Returns the outermost superloop of LOOP in that the expression EXPR is
329 invariant. */
331 static struct loop *
332 outermost_invariant_loop_expr (tree expr, struct loop *loop)
334 enum tree_code_class codeclass = TREE_CODE_CLASS (TREE_CODE (expr));
335 unsigned i, nops;
336 struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
338 if (TREE_CODE (expr) == SSA_NAME
339 || TREE_CODE (expr) == INTEGER_CST
340 || is_gimple_min_invariant (expr))
341 return outermost_invariant_loop (expr, loop);
343 if (codeclass != tcc_unary
344 && codeclass != tcc_binary
345 && codeclass != tcc_expression
346 && codeclass != tcc_vl_exp
347 && codeclass != tcc_comparison)
348 return NULL;
350 nops = TREE_OPERAND_LENGTH (expr);
351 for (i = 0; i < nops; i++)
353 aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
354 if (!aloop)
355 return NULL;
357 if (flow_loop_nested_p (max_loop, aloop))
358 max_loop = aloop;
361 return max_loop;
364 /* DATA is a structure containing information associated with a statement
365 inside LOOP. DEF is one of the operands of this statement.
367 Find the outermost loop enclosing LOOP in that value of DEF is invariant
368 and record this in DATA->max_loop field. If DEF itself is defined inside
369 this loop as well (i.e. we need to hoist it out of the loop if we want
370 to hoist the statement represented by DATA), record the statement in that
371 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
372 add the cost of the computation of DEF to the DATA->cost.
374 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
376 static bool
377 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
378 bool add_cost)
380 tree def_stmt = SSA_NAME_DEF_STMT (def);
381 basic_block def_bb = bb_for_stmt (def_stmt);
382 struct loop *max_loop;
383 struct depend *dep;
385 if (!def_bb)
386 return true;
388 max_loop = outermost_invariant_loop (def, loop);
389 if (!max_loop)
390 return false;
392 if (flow_loop_nested_p (data->max_loop, max_loop))
393 data->max_loop = max_loop;
395 if (!LIM_DATA (def_stmt))
396 return true;
398 if (add_cost
399 /* Only add the cost if the statement defining DEF is inside LOOP,
400 i.e. if it is likely that by moving the invariants dependent
401 on it, we will be able to avoid creating a new register for
402 it (since it will be only used in these dependent invariants). */
403 && def_bb->loop_father == loop)
404 data->cost += LIM_DATA (def_stmt)->cost;
406 dep = XNEW (struct depend);
407 dep->stmt = def_stmt;
408 dep->next = data->depends;
409 data->depends = dep;
411 return true;
414 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
415 are just ad-hoc constants. The estimates should be based on target-specific
416 values. */
418 static unsigned
419 stmt_cost (tree stmt)
421 tree rhs;
422 unsigned cost = 1;
424 /* Always try to create possibilities for unswitching. */
425 if (TREE_CODE (stmt) == COND_EXPR)
426 return LIM_EXPENSIVE;
428 rhs = GENERIC_TREE_OPERAND (stmt, 1);
430 /* Hoisting memory references out should almost surely be a win. */
431 if (stmt_references_memory_p (stmt))
432 cost += 20;
434 switch (TREE_CODE (rhs))
436 case CALL_EXPR:
437 /* We should be hoisting calls if possible. */
439 /* Unless the call is a builtin_constant_p; this always folds to a
440 constant, so moving it is useless. */
441 rhs = get_callee_fndecl (rhs);
442 if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
443 && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
444 return 0;
446 cost += 20;
447 break;
449 case MULT_EXPR:
450 case TRUNC_DIV_EXPR:
451 case CEIL_DIV_EXPR:
452 case FLOOR_DIV_EXPR:
453 case ROUND_DIV_EXPR:
454 case EXACT_DIV_EXPR:
455 case CEIL_MOD_EXPR:
456 case FLOOR_MOD_EXPR:
457 case ROUND_MOD_EXPR:
458 case TRUNC_MOD_EXPR:
459 case RDIV_EXPR:
460 /* Division and multiplication are usually expensive. */
461 cost += 20;
462 break;
464 case LSHIFT_EXPR:
465 case RSHIFT_EXPR:
466 cost += 20;
467 break;
469 default:
470 break;
473 return cost;
476 /* Determine the outermost loop to that it is possible to hoist a statement
477 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
478 the outermost loop in that the value computed by STMT is invariant.
479 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
480 we preserve the fact whether STMT is executed. It also fills other related
481 information to LIM_DATA (STMT).
483 The function returns false if STMT cannot be hoisted outside of the loop it
484 is defined in, and true otherwise. */
486 static bool
487 determine_max_movement (tree stmt, bool must_preserve_exec)
489 basic_block bb = bb_for_stmt (stmt);
490 struct loop *loop = bb->loop_father;
491 struct loop *level;
492 struct lim_aux_data *lim_data = LIM_DATA (stmt);
493 tree val;
494 ssa_op_iter iter;
496 if (must_preserve_exec)
497 level = ALWAYS_EXECUTED_IN (bb);
498 else
499 level = superloop_at_depth (loop, 1);
500 lim_data->max_loop = level;
502 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
503 if (!add_dependency (val, lim_data, loop, true))
504 return false;
506 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
507 if (!add_dependency (val, lim_data, loop, false))
508 return false;
510 lim_data->cost += stmt_cost (stmt);
512 return true;
515 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
516 and that one of the operands of this statement is computed by STMT.
517 Ensure that STMT (together with all the statements that define its
518 operands) is hoisted at least out of the loop LEVEL. */
520 static void
521 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
523 struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
524 struct depend *dep;
526 stmt_loop = find_common_loop (orig_loop, stmt_loop);
527 if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
528 stmt_loop = find_common_loop (stmt_loop,
529 loop_outer (LIM_DATA (stmt)->tgt_loop));
530 if (flow_loop_nested_p (stmt_loop, level))
531 return;
533 gcc_assert (LIM_DATA (stmt));
534 gcc_assert (level == LIM_DATA (stmt)->max_loop
535 || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
537 LIM_DATA (stmt)->tgt_loop = level;
538 for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
539 set_level (dep->stmt, orig_loop, level);
542 /* Determines an outermost loop from that we want to hoist the statement STMT.
543 For now we chose the outermost possible loop. TODO -- use profiling
544 information to set it more sanely. */
546 static void
547 set_profitable_level (tree stmt)
549 set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
552 /* Returns true if STMT is not a pure call. */
554 static bool
555 nonpure_call_p (tree stmt)
557 tree call = get_call_expr_in (stmt);
559 if (!call)
560 return false;
562 return TREE_SIDE_EFFECTS (call) != 0;
565 /* Releases the memory occupied by DATA. */
567 static void
568 free_lim_aux_data (struct lim_aux_data *data)
570 struct depend *dep, *next;
572 for (dep = data->depends; dep; dep = next)
574 next = dep->next;
575 free (dep);
577 free (data);
580 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
582 static tree
583 rewrite_reciprocal (block_stmt_iterator *bsi)
585 tree stmt, lhs, rhs, stmt1, stmt2, var, name, tmp;
587 stmt = bsi_stmt (*bsi);
588 lhs = GENERIC_TREE_OPERAND (stmt, 0);
589 rhs = GENERIC_TREE_OPERAND (stmt, 1);
591 /* stmt must be GIMPLE_MODIFY_STMT. */
592 var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
593 add_referenced_var (var);
595 tmp = build2 (RDIV_EXPR, TREE_TYPE (rhs),
596 build_real (TREE_TYPE (rhs), dconst1),
597 TREE_OPERAND (rhs, 1));
598 stmt1 = build_gimple_modify_stmt (var, tmp);
599 name = make_ssa_name (var, stmt1);
600 GIMPLE_STMT_OPERAND (stmt1, 0) = name;
601 tmp = build2 (MULT_EXPR, TREE_TYPE (rhs),
602 name, TREE_OPERAND (rhs, 0));
603 stmt2 = build_gimple_modify_stmt (lhs, tmp);
605 /* Replace division stmt with reciprocal and multiply stmts.
606 The multiply stmt is not invariant, so update iterator
607 and avoid rescanning. */
608 bsi_replace (bsi, stmt1, true);
609 bsi_insert_after (bsi, stmt2, BSI_NEW_STMT);
610 SSA_NAME_DEF_STMT (lhs) = stmt2;
612 /* Continue processing with invariant reciprocal statement. */
613 return stmt1;
616 /* Check if the pattern at *BSI is a bittest of the form
617 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
619 static tree
620 rewrite_bittest (block_stmt_iterator *bsi)
622 tree stmt, lhs, rhs, var, name, use_stmt, stmt1, stmt2, t;
623 use_operand_p use;
625 stmt = bsi_stmt (*bsi);
626 lhs = GENERIC_TREE_OPERAND (stmt, 0);
627 rhs = GENERIC_TREE_OPERAND (stmt, 1);
629 /* Verify that the single use of lhs is a comparison against zero. */
630 if (TREE_CODE (lhs) != SSA_NAME
631 || !single_imm_use (lhs, &use, &use_stmt)
632 || TREE_CODE (use_stmt) != COND_EXPR)
633 return stmt;
634 t = COND_EXPR_COND (use_stmt);
635 if (TREE_OPERAND (t, 0) != lhs
636 || (TREE_CODE (t) != NE_EXPR
637 && TREE_CODE (t) != EQ_EXPR)
638 || !integer_zerop (TREE_OPERAND (t, 1)))
639 return stmt;
641 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
642 stmt1 = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
643 if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
644 return stmt;
646 /* There is a conversion in between possibly inserted by fold. */
647 t = GIMPLE_STMT_OPERAND (stmt1, 1);
648 if (TREE_CODE (t) == NOP_EXPR
649 || TREE_CODE (t) == CONVERT_EXPR)
651 t = TREE_OPERAND (t, 0);
652 if (TREE_CODE (t) != SSA_NAME
653 || !has_single_use (t))
654 return stmt;
655 stmt1 = SSA_NAME_DEF_STMT (t);
656 if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
657 return stmt;
658 t = GIMPLE_STMT_OPERAND (stmt1, 1);
661 /* Verify that B is loop invariant but A is not. Verify that with
662 all the stmt walking we are still in the same loop. */
663 if (TREE_CODE (t) == RSHIFT_EXPR
664 && loop_containing_stmt (stmt1) == loop_containing_stmt (stmt)
665 && outermost_invariant_loop_expr (TREE_OPERAND (t, 1),
666 loop_containing_stmt (stmt1)) != NULL
667 && outermost_invariant_loop_expr (TREE_OPERAND (t, 0),
668 loop_containing_stmt (stmt1)) == NULL)
670 tree a = TREE_OPERAND (t, 0);
671 tree b = TREE_OPERAND (t, 1);
673 /* 1 << B */
674 var = create_tmp_var (TREE_TYPE (a), "shifttmp");
675 add_referenced_var (var);
676 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
677 build_int_cst (TREE_TYPE (a), 1), b);
678 stmt1 = build_gimple_modify_stmt (var, t);
679 name = make_ssa_name (var, stmt1);
680 GIMPLE_STMT_OPERAND (stmt1, 0) = name;
682 /* A & (1 << B) */
683 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
684 stmt2 = build_gimple_modify_stmt (var, t);
685 name = make_ssa_name (var, stmt2);
686 GIMPLE_STMT_OPERAND (stmt2, 0) = name;
687 SET_USE (use, name);
689 bsi_insert_before (bsi, stmt1, BSI_SAME_STMT);
690 bsi_replace (bsi, stmt2, true);
692 return stmt1;
695 return stmt;
699 /* Determine the outermost loops in that statements in basic block BB are
700 invariant, and record them to the LIM_DATA associated with the statements.
701 Callback for walk_dominator_tree. */
703 static void
704 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
705 basic_block bb)
707 enum move_pos pos;
708 block_stmt_iterator bsi;
709 tree stmt, rhs;
710 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
711 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
713 if (!loop_outer (bb->loop_father))
714 return;
716 if (dump_file && (dump_flags & TDF_DETAILS))
717 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
718 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
720 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
722 stmt = bsi_stmt (bsi);
724 pos = movement_possibility (stmt);
725 if (pos == MOVE_IMPOSSIBLE)
727 if (nonpure_call_p (stmt))
729 maybe_never = true;
730 outermost = NULL;
732 continue;
735 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
737 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
739 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
740 to be hoisted out of loop, saving expensive divide. */
741 if (pos == MOVE_POSSIBLE
742 && TREE_CODE (rhs) == RDIV_EXPR
743 && flag_unsafe_math_optimizations
744 && !flag_trapping_math
745 && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
746 loop_containing_stmt (stmt)) != NULL
747 && outermost_invariant_loop_expr (rhs,
748 loop_containing_stmt (stmt)) == NULL)
749 stmt = rewrite_reciprocal (&bsi);
751 /* If the shift count is invariant, convert (A >> B) & 1 to
752 A & (1 << B) allowing the bit mask to be hoisted out of the loop
753 saving an expensive shift. */
754 if (pos == MOVE_POSSIBLE
755 && TREE_CODE (rhs) == BIT_AND_EXPR
756 && integer_onep (TREE_OPERAND (rhs, 1))
757 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
758 && has_single_use (TREE_OPERAND (rhs, 0)))
759 stmt = rewrite_bittest (&bsi);
762 stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
763 LIM_DATA (stmt)->always_executed_in = outermost;
765 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
766 continue;
768 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
770 LIM_DATA (stmt)->max_loop = NULL;
771 continue;
774 if (dump_file && (dump_flags & TDF_DETAILS))
776 print_generic_stmt_indented (dump_file, stmt, 0, 2);
777 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
778 loop_depth (LIM_DATA (stmt)->max_loop),
779 LIM_DATA (stmt)->cost);
782 if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
783 set_profitable_level (stmt);
787 /* For each statement determines the outermost loop in that it is invariant,
788 statements on whose motion it depends and the cost of the computation.
789 This information is stored to the LIM_DATA structure associated with
790 each statement. */
792 static void
793 determine_invariantness (void)
795 struct dom_walk_data walk_data;
797 memset (&walk_data, 0, sizeof (struct dom_walk_data));
798 walk_data.dom_direction = CDI_DOMINATORS;
799 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
801 init_walk_dominator_tree (&walk_data);
802 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
803 fini_walk_dominator_tree (&walk_data);
806 /* Hoist the statements in basic block BB out of the loops prescribed by
807 data stored in LIM_DATA structures associated with each statement. Callback
808 for walk_dominator_tree. */
810 static void
811 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
812 basic_block bb)
814 struct loop *level;
815 block_stmt_iterator bsi;
816 tree stmt;
817 unsigned cost = 0;
819 if (!loop_outer (bb->loop_father))
820 return;
822 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
824 stmt = bsi_stmt (bsi);
826 if (!LIM_DATA (stmt))
828 bsi_next (&bsi);
829 continue;
832 cost = LIM_DATA (stmt)->cost;
833 level = LIM_DATA (stmt)->tgt_loop;
834 free_lim_aux_data (LIM_DATA (stmt));
835 stmt_ann (stmt)->common.aux = NULL;
837 if (!level)
839 bsi_next (&bsi);
840 continue;
843 /* We do not really want to move conditionals out of the loop; we just
844 placed it here to force its operands to be moved if necessary. */
845 if (TREE_CODE (stmt) == COND_EXPR)
846 continue;
848 if (dump_file && (dump_flags & TDF_DETAILS))
850 fprintf (dump_file, "Moving statement\n");
851 print_generic_stmt (dump_file, stmt, 0);
852 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
853 cost, level->num);
855 bsi_insert_on_edge (loop_preheader_edge (level), stmt);
856 bsi_remove (&bsi, false);
860 /* Hoist the statements out of the loops prescribed by data stored in
861 LIM_DATA structures associated with each statement.*/
863 static void
864 move_computations (void)
866 struct dom_walk_data walk_data;
868 memset (&walk_data, 0, sizeof (struct dom_walk_data));
869 walk_data.dom_direction = CDI_DOMINATORS;
870 walk_data.before_dom_children_before_stmts = move_computations_stmt;
872 init_walk_dominator_tree (&walk_data);
873 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
874 fini_walk_dominator_tree (&walk_data);
876 bsi_commit_edge_inserts ();
877 if (need_ssa_update_p ())
878 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
881 /* Checks whether the statement defining variable *INDEX can be hoisted
882 out of the loop passed in DATA. Callback for for_each_index. */
884 static bool
885 may_move_till (tree ref, tree *index, void *data)
887 struct loop *loop = (struct loop*) data, *max_loop;
889 /* If REF is an array reference, check also that the step and the lower
890 bound is invariant in LOOP. */
891 if (TREE_CODE (ref) == ARRAY_REF)
893 tree step = array_ref_element_size (ref);
894 tree lbound = array_ref_low_bound (ref);
896 max_loop = outermost_invariant_loop_expr (step, loop);
897 if (!max_loop)
898 return false;
900 max_loop = outermost_invariant_loop_expr (lbound, loop);
901 if (!max_loop)
902 return false;
905 max_loop = outermost_invariant_loop (*index, loop);
906 if (!max_loop)
907 return false;
909 return true;
912 /* Forces statements defining (invariant) SSA names in expression EXPR to be
913 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
915 static void
916 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
918 enum tree_code_class codeclass = TREE_CODE_CLASS (TREE_CODE (expr));
919 unsigned i, nops;
921 if (TREE_CODE (expr) == SSA_NAME)
923 tree stmt = SSA_NAME_DEF_STMT (expr);
924 if (IS_EMPTY_STMT (stmt))
925 return;
927 set_level (stmt, orig_loop, loop);
928 return;
931 if (codeclass != tcc_unary
932 && codeclass != tcc_binary
933 && codeclass != tcc_expression
934 && codeclass != tcc_vl_exp
935 && codeclass != tcc_comparison)
936 return;
938 nops = TREE_OPERAND_LENGTH (expr);
939 for (i = 0; i < nops; i++)
940 force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
943 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
944 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
945 for_each_index. */
947 struct fmt_data
949 struct loop *loop;
950 struct loop *orig_loop;
953 static bool
954 force_move_till (tree ref, tree *index, void *data)
956 tree stmt;
957 struct fmt_data *fmt_data = (struct fmt_data *) data;
959 if (TREE_CODE (ref) == ARRAY_REF)
961 tree step = array_ref_element_size (ref);
962 tree lbound = array_ref_low_bound (ref);
964 force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
965 force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
968 if (TREE_CODE (*index) != SSA_NAME)
969 return true;
971 stmt = SSA_NAME_DEF_STMT (*index);
972 if (IS_EMPTY_STMT (stmt))
973 return true;
975 set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
977 return true;
980 /* Records memory reference location *REF to the list MEM_REFS. The reference
981 occurs in statement STMT. */
983 static void
984 record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref)
986 struct mem_ref_loc *aref = XNEW (struct mem_ref_loc);
988 aref->stmt = stmt;
989 aref->ref = ref;
991 aref->next = *mem_refs;
992 *mem_refs = aref;
995 /* Releases list of memory reference locations MEM_REFS. */
997 static void
998 free_mem_ref_locs (struct mem_ref_loc *mem_refs)
1000 struct mem_ref_loc *act;
1002 while (mem_refs)
1004 act = mem_refs;
1005 mem_refs = mem_refs->next;
1006 free (act);
1010 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1012 static void
1013 rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs)
1015 tree var;
1016 ssa_op_iter iter;
1018 for (; mem_refs; mem_refs = mem_refs->next)
1020 FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
1021 mark_sym_for_renaming (SSA_NAME_VAR (var));
1023 *mem_refs->ref = tmp_var;
1024 update_stmt (mem_refs->stmt);
1028 /* The name and the length of the currently generated variable
1029 for lsm. */
1030 #define MAX_LSM_NAME_LENGTH 40
1031 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1032 static int lsm_tmp_name_length;
1034 /* Adds S to lsm_tmp_name. */
1036 static void
1037 lsm_tmp_name_add (const char *s)
1039 int l = strlen (s) + lsm_tmp_name_length;
1040 if (l > MAX_LSM_NAME_LENGTH)
1041 return;
1043 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1044 lsm_tmp_name_length = l;
1047 /* Stores the name for temporary variable that replaces REF to
1048 lsm_tmp_name. */
1050 static void
1051 gen_lsm_tmp_name (tree ref)
1053 const char *name;
1055 switch (TREE_CODE (ref))
1057 case MISALIGNED_INDIRECT_REF:
1058 case ALIGN_INDIRECT_REF:
1059 case INDIRECT_REF:
1060 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1061 lsm_tmp_name_add ("_");
1062 break;
1064 case BIT_FIELD_REF:
1065 case VIEW_CONVERT_EXPR:
1066 case ARRAY_RANGE_REF:
1067 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1068 break;
1070 case REALPART_EXPR:
1071 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1072 lsm_tmp_name_add ("_RE");
1073 break;
1075 case IMAGPART_EXPR:
1076 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1077 lsm_tmp_name_add ("_IM");
1078 break;
1080 case COMPONENT_REF:
1081 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1082 lsm_tmp_name_add ("_");
1083 name = get_name (TREE_OPERAND (ref, 1));
1084 if (!name)
1085 name = "F";
1086 lsm_tmp_name_add ("_");
1087 lsm_tmp_name_add (name);
1089 case ARRAY_REF:
1090 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1091 lsm_tmp_name_add ("_I");
1092 break;
1094 case SSA_NAME:
1095 ref = SSA_NAME_VAR (ref);
1096 /* Fallthru. */
1098 case VAR_DECL:
1099 case PARM_DECL:
1100 name = get_name (ref);
1101 if (!name)
1102 name = "D";
1103 lsm_tmp_name_add (name);
1104 break;
1106 case STRING_CST:
1107 lsm_tmp_name_add ("S");
1108 break;
1110 case RESULT_DECL:
1111 lsm_tmp_name_add ("R");
1112 break;
1114 default:
1115 gcc_unreachable ();
1119 /* Determines name for temporary variable that replaces REF.
1120 The name is accumulated into the lsm_tmp_name variable.
1121 N is added to the name of the temporary. */
1123 char *
1124 get_lsm_tmp_name (tree ref, unsigned n)
1126 char ns[2];
1128 lsm_tmp_name_length = 0;
1129 gen_lsm_tmp_name (ref);
1130 lsm_tmp_name_add ("_lsm");
1131 if (n < 10)
1133 ns[0] = '0' + n;
1134 ns[1] = 0;
1135 lsm_tmp_name_add (ns);
1137 return lsm_tmp_name;
1140 /* Records request for store motion of memory reference REF from LOOP.
1141 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1142 these references are rewritten by a new temporary variable.
1143 Exits from the LOOP are stored in EXITS. The initialization of the
1144 temporary variable is put to the preheader of the loop, and assignments
1145 to the reference from the temporary variable are emitted to exits. */
1147 static void
1148 schedule_sm (struct loop *loop, VEC (edge, heap) *exits, tree ref,
1149 struct mem_ref_loc *mem_refs)
1151 struct mem_ref_loc *aref;
1152 tree tmp_var;
1153 unsigned i;
1154 tree load, store;
1155 struct fmt_data fmt_data;
1156 edge ex;
1158 if (dump_file && (dump_flags & TDF_DETAILS))
1160 fprintf (dump_file, "Executing store motion of ");
1161 print_generic_expr (dump_file, ref, 0);
1162 fprintf (dump_file, " from loop %d\n", loop->num);
1165 tmp_var = make_rename_temp (TREE_TYPE (ref),
1166 get_lsm_tmp_name (ref, ~0));
1168 fmt_data.loop = loop;
1169 fmt_data.orig_loop = loop;
1170 for_each_index (&ref, force_move_till, &fmt_data);
1172 rewrite_mem_refs (tmp_var, mem_refs);
1173 for (aref = mem_refs; aref; aref = aref->next)
1174 if (LIM_DATA (aref->stmt))
1175 LIM_DATA (aref->stmt)->sm_done = true;
1177 /* Emit the load & stores. */
1178 load = build_gimple_modify_stmt (tmp_var, ref);
1179 get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1180 LIM_DATA (load)->max_loop = loop;
1181 LIM_DATA (load)->tgt_loop = loop;
1183 /* Put this into the latch, so that we are sure it will be processed after
1184 all dependencies. */
1185 bsi_insert_on_edge (loop_latch_edge (loop), load);
1187 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1189 store = build_gimple_modify_stmt (unshare_expr (ref), tmp_var);
1190 bsi_insert_on_edge (ex, store);
1194 /* Check whether memory reference REF can be hoisted out of the LOOP. If this
1195 is true, prepare the statements that load the value of the memory reference
1196 to a temporary variable in the loop preheader, store it back on the loop
1197 exits, and replace all the references inside LOOP by this temporary variable.
1198 EXITS is the list of exits of LOOP. CLOBBERED_VOPS is the bitmap of virtual
1199 operands that are clobbered by a call or accessed through multiple references
1200 in loop. */
1202 static void
1203 determine_lsm_ref (struct loop *loop, VEC (edge, heap) *exits,
1204 bitmap clobbered_vops, struct mem_ref *ref)
1206 struct mem_ref_loc *aref;
1207 struct loop *must_exec;
1209 /* In case the memory is not stored to, there is nothing for SM to do. */
1210 if (!ref->is_stored)
1211 return;
1213 /* If the reference is aliased with any different ref, or killed by call
1214 in function, then fail. */
1215 if (bitmap_intersect_p (ref->vops, clobbered_vops))
1216 return;
1218 if (tree_could_trap_p (ref->mem))
1220 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1221 of the statements in that it occurs is always executed when the loop
1222 is entered. This way we know that by moving the load from the
1223 reference out of the loop we will not cause the error that would not
1224 occur otherwise.
1226 TODO -- in fact we would like to check for anticipability of the
1227 reference, i.e. that on each path from loop entry to loop exit at
1228 least one of the statements containing the memory reference is
1229 executed. */
1231 for (aref = ref->locs; aref; aref = aref->next)
1233 if (!LIM_DATA (aref->stmt))
1234 continue;
1236 must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1237 if (!must_exec)
1238 continue;
1240 if (must_exec == loop
1241 || flow_loop_nested_p (must_exec, loop))
1242 break;
1245 if (!aref)
1246 return;
1249 schedule_sm (loop, exits, ref->mem, ref->locs);
1252 /* Hoists memory references MEM_REFS out of LOOP. CLOBBERED_VOPS is the list
1253 of vops clobbered by call in loop or accessed by multiple memory references.
1254 EXITS is the list of exit edges of the LOOP. */
1256 static void
1257 hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
1258 bitmap clobbered_vops, VEC (edge, heap) *exits)
1260 struct mem_ref *ref;
1262 for (ref = mem_refs; ref; ref = ref->next)
1263 determine_lsm_ref (loop, exits, clobbered_vops, ref);
1266 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
1267 for a store motion optimization (i.e. whether we can insert statement
1268 on its exits). */
1270 static bool
1271 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
1272 VEC (edge, heap) *exits)
1274 unsigned i;
1275 edge ex;
1277 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1278 if (ex->flags & EDGE_ABNORMAL)
1279 return false;
1281 return true;
1284 /* A hash function for struct mem_ref object OBJ. */
1286 static hashval_t
1287 memref_hash (const void *obj)
1289 return ((const struct mem_ref *) obj)->hash;
1292 /* An equality function for struct mem_ref object OBJ1 with
1293 memory reference OBJ2. */
1295 static int
1296 memref_eq (const void *obj1, const void *obj2)
1298 const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
1300 return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
1303 /* Gathers memory references in statement STMT in LOOP, storing the
1304 information about them in MEM_REFS hash table. Note vops accessed through
1305 unrecognized statements in CLOBBERED_VOPS. The newly created references
1306 are also stored to MEM_REF_LIST. */
1308 static void
1309 gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs,
1310 bitmap clobbered_vops, tree stmt,
1311 struct mem_ref **mem_ref_list)
1313 tree *lhs, *rhs, *mem = NULL;
1314 hashval_t hash;
1315 PTR *slot;
1316 struct mem_ref *ref = NULL;
1317 ssa_op_iter oi;
1318 tree vname;
1319 bool is_stored;
1321 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1322 return;
1324 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
1325 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1326 goto fail;
1328 lhs = &GIMPLE_STMT_OPERAND (stmt, 0);
1329 rhs = &GIMPLE_STMT_OPERAND (stmt, 1);
1331 if (TREE_CODE (*lhs) == SSA_NAME)
1333 if (!is_gimple_addressable (*rhs))
1334 goto fail;
1336 mem = rhs;
1337 is_stored = false;
1339 else if (TREE_CODE (*rhs) == SSA_NAME
1340 || is_gimple_min_invariant (*rhs))
1342 mem = lhs;
1343 is_stored = true;
1345 else
1346 goto fail;
1348 /* If we cannot create an SSA name for the result, give up. */
1349 if (!is_gimple_reg_type (TREE_TYPE (*mem))
1350 || TREE_THIS_VOLATILE (*mem))
1351 goto fail;
1353 /* If we cannot move the reference out of the loop, fail. */
1354 if (!for_each_index (mem, may_move_till, loop))
1355 goto fail;
1357 hash = iterative_hash_expr (*mem, 0);
1358 slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT);
1360 if (*slot)
1361 ref = (struct mem_ref *) *slot;
1362 else
1364 ref = XNEW (struct mem_ref);
1365 ref->mem = *mem;
1366 ref->hash = hash;
1367 ref->locs = NULL;
1368 ref->is_stored = false;
1369 ref->vops = BITMAP_ALLOC (NULL);
1370 ref->next = *mem_ref_list;
1371 *mem_ref_list = ref;
1372 *slot = ref;
1374 ref->is_stored |= is_stored;
1376 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1377 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1378 record_mem_ref_loc (&ref->locs, stmt, mem);
1379 return;
1381 fail:
1382 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1383 bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname)));
1386 /* Gathers memory references in LOOP. Notes vops accessed through unrecognized
1387 statements in CLOBBERED_VOPS. The list of the references found by
1388 the function is returned. */
1390 static struct mem_ref *
1391 gather_mem_refs (struct loop *loop, bitmap clobbered_vops)
1393 basic_block *body = get_loop_body (loop);
1394 block_stmt_iterator bsi;
1395 unsigned i;
1396 struct mem_ref *mem_ref_list = NULL;
1397 htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL);
1399 for (i = 0; i < loop->num_nodes; i++)
1401 for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
1402 gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi),
1403 &mem_ref_list);
1406 free (body);
1408 htab_delete (mem_refs);
1409 return mem_ref_list;
1412 /* Finds the vops accessed by more than one of the memory references described
1413 in MEM_REFS and marks them in CLOBBERED_VOPS. */
1415 static void
1416 find_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops)
1418 bitmap_head tmp, all_vops;
1419 struct mem_ref *ref;
1421 bitmap_initialize (&tmp, &bitmap_default_obstack);
1422 bitmap_initialize (&all_vops, &bitmap_default_obstack);
1424 for (ref = mem_refs; ref; ref = ref->next)
1426 /* The vops that are already in all_vops are accessed by more than
1427 one memory reference. */
1428 bitmap_and (&tmp, &all_vops, ref->vops);
1429 bitmap_ior_into (clobbered_vops, &tmp);
1430 bitmap_clear (&tmp);
1432 bitmap_ior_into (&all_vops, ref->vops);
1435 bitmap_clear (&all_vops);
1438 /* Releases the memory occupied by REF. */
1440 static void
1441 free_mem_ref (struct mem_ref *ref)
1443 free_mem_ref_locs (ref->locs);
1444 BITMAP_FREE (ref->vops);
1445 free (ref);
1448 /* Releases the memory occupied by REFS. */
1450 static void
1451 free_mem_refs (struct mem_ref *refs)
1453 struct mem_ref *ref, *next;
1455 for (ref = refs; ref; ref = next)
1457 next = ref->next;
1458 free_mem_ref (ref);
1462 /* Try to perform store motion for all memory references modified inside
1463 LOOP. */
1465 static void
1466 determine_lsm_loop (struct loop *loop)
1468 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1469 bitmap clobbered_vops;
1470 struct mem_ref *mem_refs;
1472 if (!loop_suitable_for_sm (loop, exits))
1474 VEC_free (edge, heap, exits);
1475 return;
1478 /* Find the memory references in LOOP. */
1479 clobbered_vops = BITMAP_ALLOC (NULL);
1480 mem_refs = gather_mem_refs (loop, clobbered_vops);
1482 /* Find the vops that are used for more than one reference. */
1483 find_more_ref_vops (mem_refs, clobbered_vops);
1485 /* Hoist all suitable memory references. */
1486 hoist_memory_references (loop, mem_refs, clobbered_vops, exits);
1488 free_mem_refs (mem_refs);
1489 VEC_free (edge, heap, exits);
1490 BITMAP_FREE (clobbered_vops);
1493 /* Try to perform store motion for all memory references modified inside
1494 loops. */
1496 static void
1497 determine_lsm (void)
1499 struct loop *loop;
1500 loop_iterator li;
1502 /* Pass the loops from the outermost and perform the store motion as
1503 suitable. */
1505 FOR_EACH_LOOP (li, loop, 0)
1507 determine_lsm_loop (loop);
1510 bsi_commit_edge_inserts ();
1513 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1514 for each such basic block bb records the outermost loop for that execution
1515 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1516 blocks that contain a nonpure call. */
1518 static void
1519 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1521 basic_block bb = NULL, *bbs, last = NULL;
1522 unsigned i;
1523 edge e;
1524 struct loop *inn_loop = loop;
1526 if (!loop->header->aux)
1528 bbs = get_loop_body_in_dom_order (loop);
1530 for (i = 0; i < loop->num_nodes; i++)
1532 edge_iterator ei;
1533 bb = bbs[i];
1535 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1536 last = bb;
1538 if (TEST_BIT (contains_call, bb->index))
1539 break;
1541 FOR_EACH_EDGE (e, ei, bb->succs)
1542 if (!flow_bb_inside_loop_p (loop, e->dest))
1543 break;
1544 if (e)
1545 break;
1547 /* A loop might be infinite (TODO use simple loop analysis
1548 to disprove this if possible). */
1549 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1550 break;
1552 if (!flow_bb_inside_loop_p (inn_loop, bb))
1553 break;
1555 if (bb->loop_father->header == bb)
1557 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1558 break;
1560 /* In a loop that is always entered we may proceed anyway.
1561 But record that we entered it and stop once we leave it. */
1562 inn_loop = bb->loop_father;
1566 while (1)
1568 last->aux = loop;
1569 if (last == loop->header)
1570 break;
1571 last = get_immediate_dominator (CDI_DOMINATORS, last);
1574 free (bbs);
1577 for (loop = loop->inner; loop; loop = loop->next)
1578 fill_always_executed_in (loop, contains_call);
1581 /* Compute the global information needed by the loop invariant motion pass. */
1583 static void
1584 tree_ssa_lim_initialize (void)
1586 sbitmap contains_call = sbitmap_alloc (last_basic_block);
1587 block_stmt_iterator bsi;
1588 struct loop *loop;
1589 basic_block bb;
1591 sbitmap_zero (contains_call);
1592 FOR_EACH_BB (bb)
1594 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1596 if (nonpure_call_p (bsi_stmt (bsi)))
1597 break;
1600 if (!bsi_end_p (bsi))
1601 SET_BIT (contains_call, bb->index);
1604 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
1605 fill_always_executed_in (loop, contains_call);
1607 sbitmap_free (contains_call);
1610 /* Cleans up after the invariant motion pass. */
1612 static void
1613 tree_ssa_lim_finalize (void)
1615 basic_block bb;
1617 FOR_EACH_BB (bb)
1619 bb->aux = NULL;
1623 /* Moves invariants from loops. Only "expensive" invariants are moved out --
1624 i.e. those that are likely to be win regardless of the register pressure. */
1626 void
1627 tree_ssa_lim (void)
1629 tree_ssa_lim_initialize ();
1631 /* For each statement determine the outermost loop in that it is
1632 invariant and cost for computing the invariant. */
1633 determine_invariantness ();
1635 /* For each memory reference determine whether it is possible to hoist it
1636 out of the loop. Force the necessary invariants to be moved out of the
1637 loops as well. */
1638 determine_lsm ();
1640 /* Move the expressions that are expensive enough. */
1641 move_computations ();
1643 tree_ssa_lim_finalize ();