1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005 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 2, or (at your option) any
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
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
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
41 /* TODO: Support for predicated code motion. I.e.
52 Where COND and INV are is invariants, but evaluating INV may trap or be
53 invalid from some other reason if !COND. This may be transformed to
63 /* A type for the list of statements that have to be moved in order to be able
64 to hoist an invariant computation. */
72 /* The auxiliary data kept for each statement. */
76 struct loop *max_loop; /* The outermost loop in that the statement
79 struct loop *tgt_loop; /* The loop out of that we want to move the
82 struct loop *always_executed_in;
83 /* The outermost loop for that we are sure
84 the statement is executed if the loop
87 bool sm_done; /* True iff the store motion for a memory
88 reference in the statement has already
91 unsigned cost; /* Cost of the computation performed by the
94 struct depend *depends; /* List of statements that must be also hoisted
95 out of the loop when this statement is
96 hoisted; i.e. those that define the operands
97 of the statement and are inside of the
101 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
103 : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
105 /* Description of a memory reference for store motion. */
109 tree *ref; /* The reference itself. */
110 tree stmt; /* The statement in that it occurs. */
111 struct mem_ref *next; /* Next use in the chain. */
114 /* Minimum cost of an expensive expression. */
115 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
117 /* The outermost loop for that execution of the header guarantees that the
118 block will be executed. */
119 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
121 static unsigned max_stmt_uid; /* Maximal uid of a statement. Uids to phi
122 nodes are assigned using the versions of
123 ssa names they define. */
125 /* Returns uid of statement STMT. */
128 get_stmt_uid (tree stmt)
130 if (TREE_CODE (stmt) == PHI_NODE)
131 return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
133 return stmt_ann (stmt)->uid;
136 /* Calls CBCK for each index in memory reference ADDR_P. There are two
137 kinds situations handled; in each of these cases, the memory reference
138 and DATA are passed to the callback:
140 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
141 pass the pointer to the index to the callback.
143 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
144 pointer to addr to the callback.
146 If the callback returns false, the whole search stops and false is returned.
147 Otherwise the function returns true after traversing through the whole
148 reference *ADDR_P. */
151 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
155 for (; ; addr_p = nxt)
157 switch (TREE_CODE (*addr_p))
160 return cbck (*addr_p, addr_p, data);
162 case MISALIGNED_INDIRECT_REF:
163 case ALIGN_INDIRECT_REF:
165 nxt = &TREE_OPERAND (*addr_p, 0);
166 return cbck (*addr_p, nxt, data);
169 case VIEW_CONVERT_EXPR:
170 case ARRAY_RANGE_REF:
173 nxt = &TREE_OPERAND (*addr_p, 0);
177 /* If the component has varying offset, it behaves like index
179 idx = &TREE_OPERAND (*addr_p, 2);
181 && !cbck (*addr_p, idx, data))
184 nxt = &TREE_OPERAND (*addr_p, 0);
188 nxt = &TREE_OPERAND (*addr_p, 0);
189 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
206 /* If it is possible to hoist the statement STMT unconditionally,
207 returns MOVE_POSSIBLE.
208 If it is possible to hoist the statement STMT, but we must avoid making
209 it executed if it would not be executed in the original program (e.g.
210 because it may trap), return MOVE_PRESERVE_EXECUTION.
211 Otherwise return MOVE_IMPOSSIBLE. */
214 movement_possibility (tree stmt)
218 if (flag_unswitch_loops
219 && TREE_CODE (stmt) == COND_EXPR)
221 /* If we perform unswitching, force the operands of the invariant
222 condition to be moved out of the loop. */
223 get_stmt_operands (stmt);
225 return MOVE_POSSIBLE;
228 if (TREE_CODE (stmt) != MODIFY_EXPR)
229 return MOVE_IMPOSSIBLE;
231 if (stmt_ends_bb_p (stmt))
232 return MOVE_IMPOSSIBLE;
234 get_stmt_operands (stmt);
236 if (stmt_ann (stmt)->has_volatile_ops)
237 return MOVE_IMPOSSIBLE;
239 lhs = TREE_OPERAND (stmt, 0);
240 if (TREE_CODE (lhs) == SSA_NAME
241 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
242 return MOVE_IMPOSSIBLE;
244 rhs = TREE_OPERAND (stmt, 1);
246 if (TREE_SIDE_EFFECTS (rhs))
247 return MOVE_IMPOSSIBLE;
249 if (TREE_CODE (lhs) != SSA_NAME
250 || tree_could_trap_p (rhs))
251 return MOVE_PRESERVE_EXECUTION;
253 if (get_call_expr_in (stmt))
255 /* While pure or const call is guaranteed to have no side effects, we
256 cannot move it arbitrarily. Consider code like
258 char *s = something ();
268 Here the strlen call cannot be moved out of the loop, even though
269 s is invariant. In addition to possibly creating a call with
270 invalid arguments, moving out a function call that is not executed
271 may cause performance regressions in case the call is costly and
272 not executed at all. */
273 return MOVE_PRESERVE_EXECUTION;
275 return MOVE_POSSIBLE;
278 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
279 loop to that we could move the expression using DEF if it did not have
280 other operands, i.e. the outermost loop enclosing LOOP in that the value
281 of DEF is invariant. */
284 outermost_invariant_loop (tree def, struct loop *loop)
288 struct loop *max_loop;
290 if (TREE_CODE (def) != SSA_NAME)
291 return superloop_at_depth (loop, 1);
293 def_stmt = SSA_NAME_DEF_STMT (def);
294 def_bb = bb_for_stmt (def_stmt);
296 return superloop_at_depth (loop, 1);
298 max_loop = find_common_loop (loop, def_bb->loop_father);
300 if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
301 max_loop = find_common_loop (max_loop,
302 LIM_DATA (def_stmt)->max_loop->outer);
303 if (max_loop == loop)
305 max_loop = superloop_at_depth (loop, max_loop->depth + 1);
310 /* Returns the outermost superloop of LOOP in that the expression EXPR is
314 outermost_invariant_loop_expr (tree expr, struct loop *loop)
316 enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
318 struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
320 if (TREE_CODE (expr) == SSA_NAME
321 || TREE_CODE (expr) == INTEGER_CST
322 || is_gimple_min_invariant (expr))
323 return outermost_invariant_loop (expr, loop);
325 if (class != tcc_unary
326 && class != tcc_binary
327 && class != tcc_expression
328 && class != tcc_comparison)
331 nops = TREE_CODE_LENGTH (TREE_CODE (expr));
332 for (i = 0; i < nops; i++)
334 aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
338 if (flow_loop_nested_p (max_loop, aloop))
345 /* DATA is a structure containing information associated with a statement
346 inside LOOP. DEF is one of the operands of this statement.
348 Find the outermost loop enclosing LOOP in that value of DEF is invariant
349 and record this in DATA->max_loop field. If DEF itself is defined inside
350 this loop as well (i.e. we need to hoist it out of the loop if we want
351 to hoist the statement represented by DATA), record the statement in that
352 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
353 add the cost of the computation of DEF to the DATA->cost.
355 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
358 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
361 tree def_stmt = SSA_NAME_DEF_STMT (def);
362 basic_block def_bb = bb_for_stmt (def_stmt);
363 struct loop *max_loop;
369 max_loop = outermost_invariant_loop (def, loop);
373 if (flow_loop_nested_p (data->max_loop, max_loop))
374 data->max_loop = max_loop;
376 if (!LIM_DATA (def_stmt))
380 /* Only add the cost if the statement defining DEF is inside LOOP,
381 i.e. if it is likely that by moving the invariants dependent
382 on it, we will be able to avoid creating a new register for
383 it (since it will be only used in these dependent invariants). */
384 && def_bb->loop_father == loop)
385 data->cost += LIM_DATA (def_stmt)->cost;
387 dep = xmalloc (sizeof (struct depend));
388 dep->stmt = def_stmt;
389 dep->next = data->depends;
395 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
396 are just ad-hoc constants. The estimates should be based on target-specific
400 stmt_cost (tree stmt)
405 /* Always try to create possibilities for unswitching. */
406 if (TREE_CODE (stmt) == COND_EXPR)
407 return LIM_EXPENSIVE;
409 lhs = TREE_OPERAND (stmt, 0);
410 rhs = TREE_OPERAND (stmt, 1);
412 /* Hoisting memory references out should almost surely be a win. */
413 if (stmt_references_memory_p (stmt))
416 switch (TREE_CODE (rhs))
419 /* We should be hoisting calls if possible. */
421 /* Unless the call is a builtin_constant_p; this always folds to a
422 constant, so moving it is useless. */
423 rhs = get_callee_fndecl (rhs);
424 if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
425 && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
441 /* Division and multiplication are usually expensive. */
452 /* Determine the outermost loop to that it is possible to hoist a statement
453 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
454 the outermost loop in that the value computed by STMT is invariant.
455 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
456 we preserve the fact whether STMT is executed. It also fills other related
457 information to LIM_DATA (STMT).
459 The function returns false if STMT cannot be hoisted outside of the loop it
460 is defined in, and true otherwise. */
463 determine_max_movement (tree stmt, bool must_preserve_exec)
465 basic_block bb = bb_for_stmt (stmt);
466 struct loop *loop = bb->loop_father;
468 struct lim_aux_data *lim_data = LIM_DATA (stmt);
472 if (must_preserve_exec)
473 level = ALWAYS_EXECUTED_IN (bb);
475 level = superloop_at_depth (loop, 1);
476 lim_data->max_loop = level;
478 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
479 if (!add_dependency (val, lim_data, loop, true))
482 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
483 if (!add_dependency (val, lim_data, loop, false))
486 lim_data->cost += stmt_cost (stmt);
491 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
492 and that one of the operands of this statement is computed by STMT.
493 Ensure that STMT (together with all the statements that define its
494 operands) is hoisted at least out of the loop LEVEL. */
497 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
499 struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
502 stmt_loop = find_common_loop (orig_loop, stmt_loop);
503 if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
504 stmt_loop = find_common_loop (stmt_loop,
505 LIM_DATA (stmt)->tgt_loop->outer);
506 if (flow_loop_nested_p (stmt_loop, level))
509 gcc_assert (LIM_DATA (stmt));
510 gcc_assert (level == LIM_DATA (stmt)->max_loop
511 || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
513 LIM_DATA (stmt)->tgt_loop = level;
514 for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
515 set_level (dep->stmt, orig_loop, level);
518 /* Determines an outermost loop from that we want to hoist the statement STMT.
519 For now we chose the outermost possible loop. TODO -- use profiling
520 information to set it more sanely. */
523 set_profitable_level (tree stmt)
525 set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
528 /* Returns true if STMT is not a pure call. */
531 nonpure_call_p (tree stmt)
533 tree call = get_call_expr_in (stmt);
538 return TREE_SIDE_EFFECTS (call) != 0;
541 /* Releases the memory occupied by DATA. */
544 free_lim_aux_data (struct lim_aux_data *data)
546 struct depend *dep, *next;
548 for (dep = data->depends; dep; dep = next)
556 /* Determine the outermost loops in that statements in basic block BB are
557 invariant, and record them to the LIM_DATA associated with the statements.
558 Callback for walk_dominator_tree. */
561 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
565 block_stmt_iterator bsi;
567 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
568 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
570 if (!bb->loop_father->outer)
573 if (dump_file && (dump_flags & TDF_DETAILS))
574 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
575 bb->index, bb->loop_father->num, bb->loop_father->depth);
577 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
579 stmt = bsi_stmt (bsi);
581 pos = movement_possibility (stmt);
582 if (pos == MOVE_IMPOSSIBLE)
584 if (nonpure_call_p (stmt))
592 stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
593 LIM_DATA (stmt)->always_executed_in = outermost;
595 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
598 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
600 LIM_DATA (stmt)->max_loop = NULL;
604 if (dump_file && (dump_flags & TDF_DETAILS))
606 print_generic_stmt_indented (dump_file, stmt, 0, 2);
607 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
608 LIM_DATA (stmt)->max_loop->depth,
609 LIM_DATA (stmt)->cost);
612 if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
613 set_profitable_level (stmt);
617 /* For each statement determines the outermost loop in that it is invariant,
618 statements on whose motion it depends and the cost of the computation.
619 This information is stored to the LIM_DATA structure associated with
623 determine_invariantness (void)
625 struct dom_walk_data walk_data;
627 memset (&walk_data, 0, sizeof (struct dom_walk_data));
628 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
630 init_walk_dominator_tree (&walk_data);
631 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
632 fini_walk_dominator_tree (&walk_data);
635 /* Commits edge insertions and updates loop structures. */
638 loop_commit_inserts (void)
640 unsigned old_last_basic_block, i;
643 old_last_basic_block = last_basic_block;
644 bsi_commit_edge_inserts ();
645 for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
647 bb = BASIC_BLOCK (i);
649 find_common_loop (EDGE_SUCC (bb, 0)->dest->loop_father,
650 EDGE_PRED (bb, 0)->src->loop_father));
654 /* Hoist the statements in basic block BB out of the loops prescribed by
655 data stored in LIM_DATA structures associated with each statement. Callback
656 for walk_dominator_tree. */
659 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
663 block_stmt_iterator bsi;
667 if (!bb->loop_father->outer)
670 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
672 stmt = bsi_stmt (bsi);
674 if (!LIM_DATA (stmt))
680 cost = LIM_DATA (stmt)->cost;
681 level = LIM_DATA (stmt)->tgt_loop;
682 free_lim_aux_data (LIM_DATA (stmt));
683 stmt_ann (stmt)->common.aux = NULL;
691 /* We do not really want to move conditionals out of the loop; we just
692 placed it here to force its operands to be moved if necessary. */
693 if (TREE_CODE (stmt) == COND_EXPR)
696 if (dump_file && (dump_flags & TDF_DETAILS))
698 fprintf (dump_file, "Moving statement\n");
699 print_generic_stmt (dump_file, stmt, 0);
700 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
703 bsi_insert_on_edge (loop_preheader_edge (level), stmt);
708 /* Hoist the statements out of the loops prescribed by data stored in
709 LIM_DATA structures associated with each statement.*/
712 move_computations (void)
714 struct dom_walk_data walk_data;
716 memset (&walk_data, 0, sizeof (struct dom_walk_data));
717 walk_data.before_dom_children_before_stmts = move_computations_stmt;
719 init_walk_dominator_tree (&walk_data);
720 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
721 fini_walk_dominator_tree (&walk_data);
723 loop_commit_inserts ();
724 rewrite_into_ssa (false);
725 if (!bitmap_empty_p (vars_to_rename))
727 /* The rewrite of ssa names may cause violation of loop closed ssa
728 form invariants. TODO -- avoid these rewrites completely.
729 Information in virtual phi nodes is sufficient for it. */
730 rewrite_into_loop_closed_ssa ();
732 bitmap_clear (vars_to_rename);
735 /* Checks whether the statement defining variable *INDEX can be hoisted
736 out of the loop passed in DATA. Callback for for_each_index. */
739 may_move_till (tree ref, tree *index, void *data)
741 struct loop *loop = data, *max_loop;
743 /* If REF is an array reference, check also that the step and the lower
744 bound is invariant in LOOP. */
745 if (TREE_CODE (ref) == ARRAY_REF)
747 tree step = array_ref_element_size (ref);
748 tree lbound = array_ref_low_bound (ref);
750 max_loop = outermost_invariant_loop_expr (step, loop);
754 max_loop = outermost_invariant_loop_expr (lbound, loop);
759 max_loop = outermost_invariant_loop (*index, loop);
766 /* Forces statements defining (invariant) SSA names in expression EXPR to be
767 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
770 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
772 enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
775 if (TREE_CODE (expr) == SSA_NAME)
777 tree stmt = SSA_NAME_DEF_STMT (expr);
778 if (IS_EMPTY_STMT (stmt))
781 set_level (stmt, orig_loop, loop);
785 if (class != tcc_unary
786 && class != tcc_binary
787 && class != tcc_expression
788 && class != tcc_comparison)
791 nops = TREE_CODE_LENGTH (TREE_CODE (expr));
792 for (i = 0; i < nops; i++)
793 force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
796 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
797 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
803 struct loop *orig_loop;
807 force_move_till (tree ref, tree *index, void *data)
810 struct fmt_data *fmt_data = data;
812 if (TREE_CODE (ref) == ARRAY_REF)
814 tree step = array_ref_element_size (ref);
815 tree lbound = array_ref_low_bound (ref);
817 force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
818 force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
821 if (TREE_CODE (*index) != SSA_NAME)
824 stmt = SSA_NAME_DEF_STMT (*index);
825 if (IS_EMPTY_STMT (stmt))
828 set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
833 /* Records memory reference *REF (that occurs in statement STMT)
834 to the list MEM_REFS. */
837 record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
839 struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
844 aref->next = *mem_refs;
848 /* Releases list of memory references MEM_REFS. */
851 free_mem_refs (struct mem_ref *mem_refs)
858 mem_refs = mem_refs->next;
863 /* If VAR is defined in LOOP and the statement it is defined in does not belong
864 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
868 maybe_queue_var (tree var, struct loop *loop,
869 sbitmap seen, tree *queue, unsigned *in_queue)
871 tree stmt = SSA_NAME_DEF_STMT (var);
872 basic_block def_bb = bb_for_stmt (stmt);
875 || !flow_bb_inside_loop_p (loop, def_bb)
876 || TEST_BIT (seen, get_stmt_uid (stmt)))
879 SET_BIT (seen, get_stmt_uid (stmt));
880 queue[(*in_queue)++] = stmt;
883 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
884 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
885 Record the reference OP to list MEM_REFS. STMT is the statement in that
886 the reference occurs. */
890 struct mem_ref **mem_refs;
896 fem_single_reachable_address (tree *op, void *data)
898 struct sra_data *sra_data = data;
900 if (sra_data->common_ref
901 && !operand_equal_p (*op, sra_data->common_ref, 0))
903 sra_data->common_ref = *op;
905 record_mem_ref (sra_data->mem_refs, sra_data->stmt, op);
909 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
910 is passed to the CALLBACK as well. The traversal stops if CALLBACK
911 returns false, for_each_memref then returns false as well. Otherwise
912 for_each_memref returns true. */
915 for_each_memref (tree stmt, bool (*callback)(tree *, void *), void *data)
919 if (TREE_CODE (stmt) == RETURN_EXPR)
920 stmt = TREE_OPERAND (stmt, 1);
922 if (TREE_CODE (stmt) == MODIFY_EXPR)
924 op = &TREE_OPERAND (stmt, 0);
925 if (TREE_CODE (*op) != SSA_NAME
926 && !callback (op, data))
929 op = &TREE_OPERAND (stmt, 1);
930 if (TREE_CODE (*op) != SSA_NAME
931 && is_gimple_lvalue (*op)
932 && !callback (op, data))
935 stmt = TREE_OPERAND (stmt, 1);
938 if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
939 stmt = TREE_OPERAND (stmt, 0);
941 if (TREE_CODE (stmt) == CALL_EXPR)
945 for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
947 op = &TREE_VALUE (args);
949 if (TREE_CODE (*op) != SSA_NAME
950 && is_gimple_lvalue (*op)
951 && !callback (op, data))
959 /* Determine whether all memory references inside the LOOP that correspond
960 to virtual ssa names defined in statement STMT are equal.
961 If so, store the list of the references to MEM_REFS, and return one
962 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
963 *SEEN_CALL_STMT is set to true if the virtual operands suggest
964 that the reference might be clobbered by a call inside the LOOP. */
967 single_reachable_address (struct loop *loop, tree stmt,
968 struct mem_ref **mem_refs,
969 bool *seen_call_stmt)
971 unsigned max_uid = max_stmt_uid + num_ssa_names;
972 tree *queue = xmalloc (sizeof (tree) * max_uid);
973 sbitmap seen = sbitmap_alloc (max_uid);
974 unsigned in_queue = 1;
977 struct sra_data sra_data;
985 sra_data.mem_refs = mem_refs;
986 sra_data.common_ref = NULL_TREE;
989 SET_BIT (seen, get_stmt_uid (stmt));
990 *seen_call_stmt = false;
994 stmt = queue[--in_queue];
995 sra_data.stmt = stmt;
998 && LIM_DATA (stmt)->sm_done)
1001 switch (TREE_CODE (stmt))
1006 if (!for_each_memref (stmt, fem_single_reachable_address,
1010 /* If this is a function that may depend on the memory location,
1011 record the fact. We cannot directly refuse call clobbered
1012 operands here, since sra_data.common_ref did not have
1014 call = get_call_expr_in (stmt);
1016 && !(call_expr_flags (call) & ECF_CONST))
1017 *seen_call_stmt = true;
1019 /* Traverse also definitions of the VUSES (there may be other
1020 distinct from the one we used to get to this statement). */
1021 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
1022 maybe_queue_var (val, loop, seen, queue, &in_queue);
1027 for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
1028 if (TREE_CODE (PHI_ARG_DEF (stmt, i)) == SSA_NAME)
1029 maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
1030 seen, queue, &in_queue);
1037 /* Find uses of virtual names. */
1038 df = get_immediate_uses (stmt);
1039 n = num_immediate_uses (df);
1041 for (i = 0; i < n; i++)
1043 stmt = immediate_use (df, i);
1045 if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
1048 if (TEST_BIT (seen, get_stmt_uid (stmt)))
1050 SET_BIT (seen, get_stmt_uid (stmt));
1052 queue[in_queue++] = stmt;
1057 sbitmap_free (seen);
1059 return sra_data.common_ref;
1062 free_mem_refs (*mem_refs);
1065 sbitmap_free (seen);
1070 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1073 rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
1078 for (; mem_refs; mem_refs = mem_refs->next)
1080 FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
1082 var = SSA_NAME_VAR (var);
1083 bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
1086 *mem_refs->ref = tmp_var;
1087 modify_stmt (mem_refs->stmt);
1091 /* Records request for store motion of memory reference REF from LOOP.
1092 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1093 these references are rewritten by a new temporary variable.
1094 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1095 The initialization of the temporary variable is put to the preheader
1096 of the loop, and assignments to the reference from the temporary variable
1097 are emitted to exits. */
1100 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
1101 struct mem_ref *mem_refs)
1103 struct mem_ref *aref;
1107 struct fmt_data fmt_data;
1109 if (dump_file && (dump_flags & TDF_DETAILS))
1111 fprintf (dump_file, "Executing store motion of ");
1112 print_generic_expr (dump_file, ref, 0);
1113 fprintf (dump_file, " from loop %d\n", loop->num);
1116 tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
1118 fmt_data.loop = loop;
1119 fmt_data.orig_loop = loop;
1120 for_each_index (&ref, force_move_till, &fmt_data);
1122 rewrite_mem_refs (tmp_var, mem_refs);
1123 for (aref = mem_refs; aref; aref = aref->next)
1124 if (LIM_DATA (aref->stmt))
1125 LIM_DATA (aref->stmt)->sm_done = true;
1127 /* Emit the load & stores. */
1128 load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
1129 get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1130 LIM_DATA (load)->max_loop = loop;
1131 LIM_DATA (load)->tgt_loop = loop;
1133 /* Put this into the latch, so that we are sure it will be processed after
1134 all dependencies. */
1135 bsi_insert_on_edge (loop_latch_edge (loop), load);
1137 for (i = 0; i < n_exits; i++)
1139 store = build (MODIFY_EXPR, void_type_node,
1140 unshare_expr (ref), tmp_var);
1141 bsi_insert_on_edge (exits[i], store);
1145 /* Returns true if REF may be clobbered by calls. */
1148 is_call_clobbered_ref (tree ref)
1152 base = get_base_address (ref);
1157 return is_call_clobbered (base);
1159 if (INDIRECT_REF_P (base))
1161 /* Check whether the alias tags associated with the pointer
1162 are call clobbered. */
1163 tree ptr = TREE_OPERAND (base, 0);
1164 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1165 tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
1166 tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
1168 if ((nmt && is_call_clobbered (nmt))
1169 || (tmt && is_call_clobbered (tmt)))
1178 /* Determine whether all memory references inside LOOP corresponding to the
1179 virtual ssa name REG are equal to each other, and whether the address of
1180 this common reference can be hoisted outside of the loop. If this is true,
1181 prepare the statements that load the value of the memory reference to a
1182 temporary variable in the loop preheader, store it back on the loop exits,
1183 and replace all the references inside LOOP by this temporary variable.
1184 LOOP has N_EXITS stored in EXITS. */
1187 determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
1190 struct mem_ref *mem_refs, *aref;
1191 struct loop *must_exec;
1194 if (is_gimple_reg (reg))
1197 ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs,
1202 /* If we cannot create a ssa name for the result, give up. */
1203 if (!is_gimple_reg_type (TREE_TYPE (ref))
1204 || TREE_THIS_VOLATILE (ref))
1207 /* If there is a call that may use the location, give up as well. */
1209 && is_call_clobbered_ref (ref))
1212 if (!for_each_index (&ref, may_move_till, loop))
1215 if (tree_could_trap_p (ref))
1217 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1218 of the statements in that it occurs is always executed when the loop
1219 is entered. This way we know that by moving the load from the
1220 reference out of the loop we will not cause the error that would not
1223 TODO -- in fact we would like to check for anticipability of the
1224 reference, i.e. that on each path from loop entry to loop exit at
1225 least one of the statements containing the memory reference is
1228 for (aref = mem_refs; aref; aref = aref->next)
1230 if (!LIM_DATA (aref->stmt))
1233 must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1237 if (must_exec == loop
1238 || flow_loop_nested_p (must_exec, loop))
1246 schedule_sm (loop, exits, n_exits, ref, mem_refs);
1249 free_mem_refs (mem_refs);
1252 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1253 for a store motion optimization (i.e. whether we can insert statement
1257 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1262 for (i = 0; i < n_exits; i++)
1263 if (exits[i]->flags & EDGE_ABNORMAL)
1269 /* Try to perform store motion for all memory references modified inside
1273 determine_lsm_loop (struct loop *loop)
1277 edge *exits = get_loop_exit_edges (loop, &n_exits);
1279 if (!loop_suitable_for_sm (loop, exits, n_exits))
1285 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1286 determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
1291 /* Try to perform store motion for all memory references modified inside
1295 determine_lsm (struct loops *loops)
1300 if (!loops->tree_root->inner)
1303 /* Create a UID for each statement in the function. Ordering of the
1304 UIDs is not important for this pass. */
1308 block_stmt_iterator bsi;
1310 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1311 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
1314 compute_immediate_uses (TDFA_USE_VOPS, NULL);
1316 /* Pass the loops from the outermost. For each virtual operand loop phi node
1317 check whether all the references inside the loop correspond to a single
1318 address, and if so, move them. */
1320 loop = loops->tree_root->inner;
1323 determine_lsm_loop (loop);
1333 if (loop == loops->tree_root)
1336 loop_commit_inserts ();
1344 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1345 for each such basic block bb records the outermost loop for that execution
1346 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1347 blocks that contain a nonpure call. */
1350 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1352 basic_block bb = NULL, *bbs, last = NULL;
1355 struct loop *inn_loop = loop;
1357 if (!loop->header->aux)
1359 bbs = get_loop_body_in_dom_order (loop);
1361 for (i = 0; i < loop->num_nodes; i++)
1366 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1369 if (TEST_BIT (contains_call, bb->index))
1372 FOR_EACH_EDGE (e, ei, bb->succs)
1373 if (!flow_bb_inside_loop_p (loop, e->dest))
1378 /* A loop might be infinite (TODO use simple loop analysis
1379 to disprove this if possible). */
1380 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1383 if (!flow_bb_inside_loop_p (inn_loop, bb))
1386 if (bb->loop_father->header == bb)
1388 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1391 /* In a loop that is always entered we may proceed anyway.
1392 But record that we entered it and stop once we leave it. */
1393 inn_loop = bb->loop_father;
1400 if (last == loop->header)
1402 last = get_immediate_dominator (CDI_DOMINATORS, last);
1408 for (loop = loop->inner; loop; loop = loop->next)
1409 fill_always_executed_in (loop, contains_call);
1412 /* Compute the global information needed by the loop invariant motion pass.
1413 LOOPS is the loop tree. */
1416 tree_ssa_lim_initialize (struct loops *loops)
1418 sbitmap contains_call = sbitmap_alloc (last_basic_block);
1419 block_stmt_iterator bsi;
1423 sbitmap_zero (contains_call);
1426 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1428 if (nonpure_call_p (bsi_stmt (bsi)))
1432 if (!bsi_end_p (bsi))
1433 SET_BIT (contains_call, bb->index);
1436 for (loop = loops->tree_root->inner; loop; loop = loop->next)
1437 fill_always_executed_in (loop, contains_call);
1439 sbitmap_free (contains_call);
1442 /* Cleans up after the invariant motion pass. */
1445 tree_ssa_lim_finalize (void)
1455 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1456 i.e. those that are likely to be win regardless of the register pressure. */
1459 tree_ssa_lim (struct loops *loops)
1461 tree_ssa_lim_initialize (loops);
1463 /* For each statement determine the outermost loop in that it is
1464 invariant and cost for computing the invariant. */
1465 determine_invariantness ();
1467 /* For each memory reference determine whether it is possible to hoist it
1468 out of the loop. Force the necessary invariants to be moved out of the
1470 determine_lsm (loops);
1472 /* Move the expressions that are expensive enough. */
1473 move_computations ();
1475 tree_ssa_lim_finalize ();