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))
205 /* If it is possible to hoist the statement STMT unconditionally,
206 returns MOVE_POSSIBLE.
207 If it is possible to hoist the statement STMT, but we must avoid making
208 it executed if it would not be executed in the original program (e.g.
209 because it may trap), return MOVE_PRESERVE_EXECUTION.
210 Otherwise return MOVE_IMPOSSIBLE. */
213 movement_possibility (tree stmt)
217 if (flag_unswitch_loops
218 && TREE_CODE (stmt) == COND_EXPR)
220 /* If we perform unswitching, force the operands of the invariant
221 condition to be moved out of the loop. */
222 get_stmt_operands (stmt);
224 return MOVE_POSSIBLE;
227 if (TREE_CODE (stmt) != MODIFY_EXPR)
228 return MOVE_IMPOSSIBLE;
230 if (stmt_ends_bb_p (stmt))
231 return MOVE_IMPOSSIBLE;
233 get_stmt_operands (stmt);
235 if (stmt_ann (stmt)->has_volatile_ops)
236 return MOVE_IMPOSSIBLE;
238 lhs = TREE_OPERAND (stmt, 0);
239 if (TREE_CODE (lhs) == SSA_NAME
240 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
241 return MOVE_IMPOSSIBLE;
243 rhs = TREE_OPERAND (stmt, 1);
245 if (TREE_SIDE_EFFECTS (rhs))
246 return MOVE_IMPOSSIBLE;
248 if (TREE_CODE (lhs) != SSA_NAME
249 || tree_could_trap_p (rhs))
250 return MOVE_PRESERVE_EXECUTION;
252 if (get_call_expr_in (stmt))
254 /* While pure or const call is guaranteed to have no side effects, we
255 cannot move it arbitrarily. Consider code like
257 char *s = something ();
267 Here the strlen call cannot be moved out of the loop, even though
268 s is invariant. In addition to possibly creating a call with
269 invalid arguments, moving out a function call that is not executed
270 may cause performance regressions in case the call is costly and
271 not executed at all. */
272 return MOVE_PRESERVE_EXECUTION;
274 return MOVE_POSSIBLE;
277 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
278 loop to that we could move the expression using DEF if it did not have
279 other operands, i.e. the outermost loop enclosing LOOP in that the value
280 of DEF is invariant. */
283 outermost_invariant_loop (tree def, struct loop *loop)
287 struct loop *max_loop;
289 if (TREE_CODE (def) != SSA_NAME)
290 return superloop_at_depth (loop, 1);
292 def_stmt = SSA_NAME_DEF_STMT (def);
293 def_bb = bb_for_stmt (def_stmt);
295 return superloop_at_depth (loop, 1);
297 max_loop = find_common_loop (loop, def_bb->loop_father);
299 if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
300 max_loop = find_common_loop (max_loop,
301 LIM_DATA (def_stmt)->max_loop->outer);
302 if (max_loop == loop)
304 max_loop = superloop_at_depth (loop, max_loop->depth + 1);
309 /* Returns the outermost superloop of LOOP in that the expression EXPR is
313 outermost_invariant_loop_expr (tree expr, struct loop *loop)
315 enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
317 struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
319 if (TREE_CODE (expr) == SSA_NAME
320 || TREE_CODE (expr) == INTEGER_CST
321 || is_gimple_min_invariant (expr))
322 return outermost_invariant_loop (expr, loop);
324 if (class != tcc_unary
325 && class != tcc_binary
326 && class != tcc_expression
327 && class != tcc_comparison)
330 nops = TREE_CODE_LENGTH (TREE_CODE (expr));
331 for (i = 0; i < nops; i++)
333 aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
337 if (flow_loop_nested_p (max_loop, aloop))
344 /* DATA is a structure containing information associated with a statement
345 inside LOOP. DEF is one of the operands of this statement.
347 Find the outermost loop enclosing LOOP in that value of DEF is invariant
348 and record this in DATA->max_loop field. If DEF itself is defined inside
349 this loop as well (i.e. we need to hoist it out of the loop if we want
350 to hoist the statement represented by DATA), record the statement in that
351 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
352 add the cost of the computation of DEF to the DATA->cost.
354 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
357 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
360 tree def_stmt = SSA_NAME_DEF_STMT (def);
361 basic_block def_bb = bb_for_stmt (def_stmt);
362 struct loop *max_loop;
368 max_loop = outermost_invariant_loop (def, loop);
372 if (flow_loop_nested_p (data->max_loop, max_loop))
373 data->max_loop = max_loop;
375 if (!LIM_DATA (def_stmt))
379 /* Only add the cost if the statement defining DEF is inside LOOP,
380 i.e. if it is likely that by moving the invariants dependent
381 on it, we will be able to avoid creating a new register for
382 it (since it will be only used in these dependent invariants). */
383 && def_bb->loop_father == loop)
384 data->cost += LIM_DATA (def_stmt)->cost;
386 dep = xmalloc (sizeof (struct depend));
387 dep->stmt = def_stmt;
388 dep->next = data->depends;
394 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
395 are just ad-hoc constants. The estimates should be based on target-specific
399 stmt_cost (tree stmt)
404 /* Always try to create possibilities for unswitching. */
405 if (TREE_CODE (stmt) == COND_EXPR)
406 return LIM_EXPENSIVE;
408 rhs = TREE_OPERAND (stmt, 1);
410 /* Hoisting memory references out should almost surely be a win. */
411 if (stmt_references_memory_p (stmt))
414 switch (TREE_CODE (rhs))
417 /* We should be hoisting calls if possible. */
419 /* Unless the call is a builtin_constant_p; this always folds to a
420 constant, so moving it is useless. */
421 rhs = get_callee_fndecl (rhs);
422 if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
423 && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
440 /* Division and multiplication are usually expensive. */
451 /* Determine the outermost loop to that it is possible to hoist a statement
452 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
453 the outermost loop in that the value computed by STMT is invariant.
454 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
455 we preserve the fact whether STMT is executed. It also fills other related
456 information to LIM_DATA (STMT).
458 The function returns false if STMT cannot be hoisted outside of the loop it
459 is defined in, and true otherwise. */
462 determine_max_movement (tree stmt, bool must_preserve_exec)
464 basic_block bb = bb_for_stmt (stmt);
465 struct loop *loop = bb->loop_father;
467 struct lim_aux_data *lim_data = LIM_DATA (stmt);
471 if (must_preserve_exec)
472 level = ALWAYS_EXECUTED_IN (bb);
474 level = superloop_at_depth (loop, 1);
475 lim_data->max_loop = level;
477 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
478 if (!add_dependency (val, lim_data, loop, true))
481 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
482 if (!add_dependency (val, lim_data, loop, false))
485 lim_data->cost += stmt_cost (stmt);
490 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
491 and that one of the operands of this statement is computed by STMT.
492 Ensure that STMT (together with all the statements that define its
493 operands) is hoisted at least out of the loop LEVEL. */
496 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
498 struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
501 stmt_loop = find_common_loop (orig_loop, stmt_loop);
502 if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
503 stmt_loop = find_common_loop (stmt_loop,
504 LIM_DATA (stmt)->tgt_loop->outer);
505 if (flow_loop_nested_p (stmt_loop, level))
508 gcc_assert (LIM_DATA (stmt));
509 gcc_assert (level == LIM_DATA (stmt)->max_loop
510 || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
512 LIM_DATA (stmt)->tgt_loop = level;
513 for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
514 set_level (dep->stmt, orig_loop, level);
517 /* Determines an outermost loop from that we want to hoist the statement STMT.
518 For now we chose the outermost possible loop. TODO -- use profiling
519 information to set it more sanely. */
522 set_profitable_level (tree stmt)
524 set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
527 /* Returns true if STMT is not a pure call. */
530 nonpure_call_p (tree stmt)
532 tree call = get_call_expr_in (stmt);
537 return TREE_SIDE_EFFECTS (call) != 0;
540 /* Releases the memory occupied by DATA. */
543 free_lim_aux_data (struct lim_aux_data *data)
545 struct depend *dep, *next;
547 for (dep = data->depends; dep; dep = next)
555 /* Determine the outermost loops in that statements in basic block BB are
556 invariant, and record them to the LIM_DATA associated with the statements.
557 Callback for walk_dominator_tree. */
560 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
564 block_stmt_iterator bsi;
566 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
567 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
569 if (!bb->loop_father->outer)
572 if (dump_file && (dump_flags & TDF_DETAILS))
573 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
574 bb->index, bb->loop_father->num, bb->loop_father->depth);
576 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
578 stmt = bsi_stmt (bsi);
580 pos = movement_possibility (stmt);
581 if (pos == MOVE_IMPOSSIBLE)
583 if (nonpure_call_p (stmt))
591 stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
592 LIM_DATA (stmt)->always_executed_in = outermost;
594 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
597 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
599 LIM_DATA (stmt)->max_loop = NULL;
603 if (dump_file && (dump_flags & TDF_DETAILS))
605 print_generic_stmt_indented (dump_file, stmt, 0, 2);
606 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
607 LIM_DATA (stmt)->max_loop->depth,
608 LIM_DATA (stmt)->cost);
611 if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
612 set_profitable_level (stmt);
616 /* For each statement determines the outermost loop in that it is invariant,
617 statements on whose motion it depends and the cost of the computation.
618 This information is stored to the LIM_DATA structure associated with
622 determine_invariantness (void)
624 struct dom_walk_data walk_data;
626 memset (&walk_data, 0, sizeof (struct dom_walk_data));
627 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
629 init_walk_dominator_tree (&walk_data);
630 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
631 fini_walk_dominator_tree (&walk_data);
634 /* Commits edge insertions and updates loop structures. */
637 loop_commit_inserts (void)
639 unsigned old_last_basic_block, i;
642 old_last_basic_block = last_basic_block;
643 bsi_commit_edge_inserts ();
644 for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
646 bb = BASIC_BLOCK (i);
648 find_common_loop (single_pred (bb)->loop_father,
649 single_succ (bb)->loop_father));
653 /* Hoist the statements in basic block BB out of the loops prescribed by
654 data stored in LIM_DATA structures associated with each statement. Callback
655 for walk_dominator_tree. */
658 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
662 block_stmt_iterator bsi;
666 if (!bb->loop_father->outer)
669 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
671 stmt = bsi_stmt (bsi);
673 if (!LIM_DATA (stmt))
679 cost = LIM_DATA (stmt)->cost;
680 level = LIM_DATA (stmt)->tgt_loop;
681 free_lim_aux_data (LIM_DATA (stmt));
682 stmt_ann (stmt)->common.aux = NULL;
690 /* We do not really want to move conditionals out of the loop; we just
691 placed it here to force its operands to be moved if necessary. */
692 if (TREE_CODE (stmt) == COND_EXPR)
695 if (dump_file && (dump_flags & TDF_DETAILS))
697 fprintf (dump_file, "Moving statement\n");
698 print_generic_stmt (dump_file, stmt, 0);
699 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
702 bsi_insert_on_edge (loop_preheader_edge (level), stmt);
707 /* Hoist the statements out of the loops prescribed by data stored in
708 LIM_DATA structures associated with each statement.*/
711 move_computations (void)
713 struct dom_walk_data walk_data;
715 memset (&walk_data, 0, sizeof (struct dom_walk_data));
716 walk_data.before_dom_children_before_stmts = move_computations_stmt;
718 init_walk_dominator_tree (&walk_data);
719 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
720 fini_walk_dominator_tree (&walk_data);
722 loop_commit_inserts ();
724 if (need_ssa_update_p ())
725 update_ssa (TODO_update_ssa);
727 /* The movement of LI code 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 (NULL);
733 /* Checks whether the statement defining variable *INDEX can be hoisted
734 out of the loop passed in DATA. Callback for for_each_index. */
737 may_move_till (tree ref, tree *index, void *data)
739 struct loop *loop = data, *max_loop;
741 /* If REF is an array reference, check also that the step and the lower
742 bound is invariant in LOOP. */
743 if (TREE_CODE (ref) == ARRAY_REF)
745 tree step = array_ref_element_size (ref);
746 tree lbound = array_ref_low_bound (ref);
748 max_loop = outermost_invariant_loop_expr (step, loop);
752 max_loop = outermost_invariant_loop_expr (lbound, loop);
757 max_loop = outermost_invariant_loop (*index, loop);
764 /* Forces statements defining (invariant) SSA names in expression EXPR to be
765 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
768 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
770 enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
773 if (TREE_CODE (expr) == SSA_NAME)
775 tree stmt = SSA_NAME_DEF_STMT (expr);
776 if (IS_EMPTY_STMT (stmt))
779 set_level (stmt, orig_loop, loop);
783 if (class != tcc_unary
784 && class != tcc_binary
785 && class != tcc_expression
786 && class != tcc_comparison)
789 nops = TREE_CODE_LENGTH (TREE_CODE (expr));
790 for (i = 0; i < nops; i++)
791 force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
794 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
795 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
801 struct loop *orig_loop;
805 force_move_till (tree ref, tree *index, void *data)
808 struct fmt_data *fmt_data = data;
810 if (TREE_CODE (ref) == ARRAY_REF)
812 tree step = array_ref_element_size (ref);
813 tree lbound = array_ref_low_bound (ref);
815 force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
816 force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
819 if (TREE_CODE (*index) != SSA_NAME)
822 stmt = SSA_NAME_DEF_STMT (*index);
823 if (IS_EMPTY_STMT (stmt))
826 set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
831 /* Records memory reference *REF (that occurs in statement STMT)
832 to the list MEM_REFS. */
835 record_mem_ref (struct mem_ref **mem_refs, tree stmt, tree *ref)
837 struct mem_ref *aref = xmalloc (sizeof (struct mem_ref));
842 aref->next = *mem_refs;
846 /* Releases list of memory references MEM_REFS. */
849 free_mem_refs (struct mem_ref *mem_refs)
856 mem_refs = mem_refs->next;
861 /* If VAR is defined in LOOP and the statement it is defined in does not belong
862 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
866 maybe_queue_var (tree var, struct loop *loop,
867 sbitmap seen, tree *queue, unsigned *in_queue)
869 tree stmt = SSA_NAME_DEF_STMT (var);
870 basic_block def_bb = bb_for_stmt (stmt);
873 || !flow_bb_inside_loop_p (loop, def_bb)
874 || TEST_BIT (seen, get_stmt_uid (stmt)))
877 SET_BIT (seen, get_stmt_uid (stmt));
878 queue[(*in_queue)++] = stmt;
881 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
882 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
883 Record the reference OP to list MEM_REFS. STMT is the statement in that
884 the reference occurs. */
888 struct mem_ref **mem_refs;
894 fem_single_reachable_address (tree *op, void *data)
896 struct sra_data *sra_data = data;
898 if (sra_data->common_ref
899 && !operand_equal_p (*op, sra_data->common_ref, 0))
901 sra_data->common_ref = *op;
903 record_mem_ref (sra_data->mem_refs, sra_data->stmt, op);
907 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
908 is passed to the CALLBACK as well. The traversal stops if CALLBACK
909 returns false, for_each_memref then returns false as well. Otherwise
910 for_each_memref returns true. */
913 for_each_memref (tree stmt, bool (*callback)(tree *, void *), void *data)
917 if (TREE_CODE (stmt) == RETURN_EXPR)
918 stmt = TREE_OPERAND (stmt, 1);
920 if (TREE_CODE (stmt) == MODIFY_EXPR)
922 op = &TREE_OPERAND (stmt, 0);
923 if (TREE_CODE (*op) != SSA_NAME
924 && !callback (op, data))
927 op = &TREE_OPERAND (stmt, 1);
928 if (TREE_CODE (*op) != SSA_NAME
929 && is_gimple_lvalue (*op)
930 && !callback (op, data))
933 stmt = TREE_OPERAND (stmt, 1);
936 if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
937 stmt = TREE_OPERAND (stmt, 0);
939 if (TREE_CODE (stmt) == CALL_EXPR)
943 for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
945 op = &TREE_VALUE (args);
947 if (TREE_CODE (*op) != SSA_NAME
948 && is_gimple_lvalue (*op)
949 && !callback (op, data))
957 /* Determine whether all memory references inside the LOOP that correspond
958 to virtual ssa names defined in statement STMT are equal.
959 If so, store the list of the references to MEM_REFS, and return one
960 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
961 *SEEN_CALL_STMT is set to true if the virtual operands suggest
962 that the reference might be clobbered by a call inside the LOOP. */
965 single_reachable_address (struct loop *loop, tree stmt,
966 struct mem_ref **mem_refs,
967 bool *seen_call_stmt)
969 unsigned max_uid = max_stmt_uid + num_ssa_names;
970 tree *queue = xmalloc (sizeof (tree) * max_uid);
971 sbitmap seen = sbitmap_alloc (max_uid);
972 unsigned in_queue = 1;
974 struct sra_data sra_data;
978 imm_use_iterator imm_iter;
984 sra_data.mem_refs = mem_refs;
985 sra_data.common_ref = NULL_TREE;
988 SET_BIT (seen, get_stmt_uid (stmt));
989 *seen_call_stmt = false;
993 stmt = queue[--in_queue];
994 sra_data.stmt = stmt;
997 && LIM_DATA (stmt)->sm_done)
1000 switch (TREE_CODE (stmt))
1005 if (!for_each_memref (stmt, fem_single_reachable_address,
1009 /* If this is a function that may depend on the memory location,
1010 record the fact. We cannot directly refuse call clobbered
1011 operands here, since sra_data.common_ref did not have
1013 call = get_call_expr_in (stmt);
1015 && !(call_expr_flags (call) & ECF_CONST))
1016 *seen_call_stmt = true;
1018 /* Traverse also definitions of the VUSES (there may be other
1019 distinct from the one we used to get to this statement). */
1020 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
1021 maybe_queue_var (val, loop, seen, queue, &in_queue);
1026 for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
1027 if (TREE_CODE (PHI_ARG_DEF (stmt, i)) == SSA_NAME)
1028 maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
1029 seen, queue, &in_queue);
1036 /* Find uses of virtual names. */
1037 if (TREE_CODE (stmt) == PHI_NODE)
1039 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (stmt))))
1040 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (stmt))
1042 tree imm_stmt = USE_STMT (use_p);
1044 if (TEST_BIT (seen, get_stmt_uid (imm_stmt)))
1047 if (!flow_bb_inside_loop_p (loop, bb_for_stmt (imm_stmt)))
1050 SET_BIT (seen, get_stmt_uid (imm_stmt));
1052 queue[in_queue++] = imm_stmt;
1056 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_DEFS)
1057 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
1059 tree imm_stmt = USE_STMT (use_p);
1061 if (TEST_BIT (seen, get_stmt_uid (imm_stmt)))
1064 if (!flow_bb_inside_loop_p (loop, bb_for_stmt (imm_stmt)))
1067 SET_BIT (seen, get_stmt_uid (imm_stmt));
1069 queue[in_queue++] = imm_stmt;
1074 sbitmap_free (seen);
1076 return sra_data.common_ref;
1079 free_mem_refs (*mem_refs);
1082 sbitmap_free (seen);
1087 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1090 rewrite_mem_refs (tree tmp_var, struct mem_ref *mem_refs)
1095 for (; mem_refs; mem_refs = mem_refs->next)
1097 FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
1098 mark_sym_for_renaming (SSA_NAME_VAR (var));
1100 *mem_refs->ref = tmp_var;
1101 update_stmt (mem_refs->stmt);
1105 /* Records request for store motion of memory reference REF from LOOP.
1106 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1107 these references are rewritten by a new temporary variable.
1108 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1109 The initialization of the temporary variable is put to the preheader
1110 of the loop, and assignments to the reference from the temporary variable
1111 are emitted to exits. */
1114 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
1115 struct mem_ref *mem_refs)
1117 struct mem_ref *aref;
1121 struct fmt_data fmt_data;
1123 if (dump_file && (dump_flags & TDF_DETAILS))
1125 fprintf (dump_file, "Executing store motion of ");
1126 print_generic_expr (dump_file, ref, 0);
1127 fprintf (dump_file, " from loop %d\n", loop->num);
1130 tmp_var = make_rename_temp (TREE_TYPE (ref), "lsm_tmp");
1132 fmt_data.loop = loop;
1133 fmt_data.orig_loop = loop;
1134 for_each_index (&ref, force_move_till, &fmt_data);
1136 rewrite_mem_refs (tmp_var, mem_refs);
1137 for (aref = mem_refs; aref; aref = aref->next)
1138 if (LIM_DATA (aref->stmt))
1139 LIM_DATA (aref->stmt)->sm_done = true;
1141 /* Emit the load & stores. */
1142 load = build (MODIFY_EXPR, void_type_node, tmp_var, ref);
1143 get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1144 LIM_DATA (load)->max_loop = loop;
1145 LIM_DATA (load)->tgt_loop = loop;
1147 /* Put this into the latch, so that we are sure it will be processed after
1148 all dependencies. */
1149 bsi_insert_on_edge (loop_latch_edge (loop), load);
1151 for (i = 0; i < n_exits; i++)
1153 store = build (MODIFY_EXPR, void_type_node,
1154 unshare_expr (ref), tmp_var);
1155 bsi_insert_on_edge (exits[i], store);
1159 /* Returns true if REF may be clobbered by calls. */
1162 is_call_clobbered_ref (tree ref)
1165 HOST_WIDE_INT offset, size;
1170 if (TREE_CODE (sref) == COMPONENT_REF
1171 && (sref = okay_component_ref_for_subvars (sref, &offset, &size)))
1173 svars = get_subvars_for_var (sref);
1174 for (sv = svars; sv; sv = sv->next)
1176 if (overlap_subvar (offset, size, sv, NULL)
1177 && is_call_clobbered (sv->var))
1182 base = get_base_address (ref);
1188 if (var_can_have_subvars (base)
1189 && (svars = get_subvars_for_var (base)))
1191 for (sv = svars; sv; sv = sv->next)
1192 if (is_call_clobbered (sv->var))
1197 return is_call_clobbered (base);
1200 if (INDIRECT_REF_P (base))
1202 /* Check whether the alias tags associated with the pointer
1203 are call clobbered. */
1204 tree ptr = TREE_OPERAND (base, 0);
1205 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1206 tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
1207 tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
1209 if ((nmt && is_call_clobbered (nmt))
1210 || (tmt && is_call_clobbered (tmt)))
1219 /* Determine whether all memory references inside LOOP corresponding to the
1220 virtual ssa name REG are equal to each other, and whether the address of
1221 this common reference can be hoisted outside of the loop. If this is true,
1222 prepare the statements that load the value of the memory reference to a
1223 temporary variable in the loop preheader, store it back on the loop exits,
1224 and replace all the references inside LOOP by this temporary variable.
1225 LOOP has N_EXITS stored in EXITS. */
1228 determine_lsm_reg (struct loop *loop, edge *exits, unsigned n_exits, tree reg)
1231 struct mem_ref *mem_refs, *aref;
1232 struct loop *must_exec;
1235 if (is_gimple_reg (reg))
1238 ref = single_reachable_address (loop, SSA_NAME_DEF_STMT (reg), &mem_refs,
1243 /* If we cannot create a ssa name for the result, give up. */
1244 if (!is_gimple_reg_type (TREE_TYPE (ref))
1245 || TREE_THIS_VOLATILE (ref))
1248 /* If there is a call that may use the location, give up as well. */
1250 && is_call_clobbered_ref (ref))
1253 if (!for_each_index (&ref, may_move_till, loop))
1256 if (tree_could_trap_p (ref))
1258 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1259 of the statements in that it occurs is always executed when the loop
1260 is entered. This way we know that by moving the load from the
1261 reference out of the loop we will not cause the error that would not
1264 TODO -- in fact we would like to check for anticipability of the
1265 reference, i.e. that on each path from loop entry to loop exit at
1266 least one of the statements containing the memory reference is
1269 for (aref = mem_refs; aref; aref = aref->next)
1271 if (!LIM_DATA (aref->stmt))
1274 must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1278 if (must_exec == loop
1279 || flow_loop_nested_p (must_exec, loop))
1287 schedule_sm (loop, exits, n_exits, ref, mem_refs);
1290 free_mem_refs (mem_refs);
1293 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1294 for a store motion optimization (i.e. whether we can insert statement
1298 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1303 for (i = 0; i < n_exits; i++)
1304 if (exits[i]->flags & EDGE_ABNORMAL)
1310 /* Try to perform store motion for all memory references modified inside
1314 determine_lsm_loop (struct loop *loop)
1318 edge *exits = get_loop_exit_edges (loop, &n_exits);
1320 if (!loop_suitable_for_sm (loop, exits, n_exits))
1326 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1327 determine_lsm_reg (loop, exits, n_exits, PHI_RESULT (phi));
1332 /* Try to perform store motion for all memory references modified inside
1336 determine_lsm (struct loops *loops)
1341 if (!loops->tree_root->inner)
1344 /* Create a UID for each statement in the function. Ordering of the
1345 UIDs is not important for this pass. */
1349 block_stmt_iterator bsi;
1351 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1352 stmt_ann (bsi_stmt (bsi))->uid = max_stmt_uid++;
1355 /* Pass the loops from the outermost. For each virtual operand loop phi node
1356 check whether all the references inside the loop correspond to a single
1357 address, and if so, move them. */
1359 loop = loops->tree_root->inner;
1362 determine_lsm_loop (loop);
1372 if (loop == loops->tree_root)
1374 loop_commit_inserts ();
1382 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1383 for each such basic block bb records the outermost loop for that execution
1384 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1385 blocks that contain a nonpure call. */
1388 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1390 basic_block bb = NULL, *bbs, last = NULL;
1393 struct loop *inn_loop = loop;
1395 if (!loop->header->aux)
1397 bbs = get_loop_body_in_dom_order (loop);
1399 for (i = 0; i < loop->num_nodes; i++)
1404 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1407 if (TEST_BIT (contains_call, bb->index))
1410 FOR_EACH_EDGE (e, ei, bb->succs)
1411 if (!flow_bb_inside_loop_p (loop, e->dest))
1416 /* A loop might be infinite (TODO use simple loop analysis
1417 to disprove this if possible). */
1418 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1421 if (!flow_bb_inside_loop_p (inn_loop, bb))
1424 if (bb->loop_father->header == bb)
1426 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1429 /* In a loop that is always entered we may proceed anyway.
1430 But record that we entered it and stop once we leave it. */
1431 inn_loop = bb->loop_father;
1438 if (last == loop->header)
1440 last = get_immediate_dominator (CDI_DOMINATORS, last);
1446 for (loop = loop->inner; loop; loop = loop->next)
1447 fill_always_executed_in (loop, contains_call);
1450 /* Compute the global information needed by the loop invariant motion pass.
1451 LOOPS is the loop tree. */
1454 tree_ssa_lim_initialize (struct loops *loops)
1456 sbitmap contains_call = sbitmap_alloc (last_basic_block);
1457 block_stmt_iterator bsi;
1461 sbitmap_zero (contains_call);
1464 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1466 if (nonpure_call_p (bsi_stmt (bsi)))
1470 if (!bsi_end_p (bsi))
1471 SET_BIT (contains_call, bb->index);
1474 for (loop = loops->tree_root->inner; loop; loop = loop->next)
1475 fill_always_executed_in (loop, contains_call);
1477 sbitmap_free (contains_call);
1480 /* Cleans up after the invariant motion pass. */
1483 tree_ssa_lim_finalize (void)
1493 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1494 i.e. those that are likely to be win regardless of the register pressure. */
1497 tree_ssa_lim (struct loops *loops)
1499 tree_ssa_lim_initialize (loops);
1501 /* For each statement determine the outermost loop in that it is
1502 invariant and cost for computing the invariant. */
1503 determine_invariantness ();
1505 /* For each memory reference determine whether it is possible to hoist it
1506 out of the loop. Force the necessary invariants to be moved out of the
1508 determine_lsm (loops);
1510 /* Move the expressions that are expensive enough. */
1511 move_computations ();
1513 tree_ssa_lim_finalize ();