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
)
439 /* Division and multiplication are usually expensive. */
450 /* Determine the outermost loop to that it is possible to hoist a statement
451 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
452 the outermost loop in that the value computed by STMT is invariant.
453 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
454 we preserve the fact whether STMT is executed. It also fills other related
455 information to LIM_DATA (STMT).
457 The function returns false if STMT cannot be hoisted outside of the loop it
458 is defined in, and true otherwise. */
461 determine_max_movement (tree stmt
, bool must_preserve_exec
)
463 basic_block bb
= bb_for_stmt (stmt
);
464 struct loop
*loop
= bb
->loop_father
;
466 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
470 if (must_preserve_exec
)
471 level
= ALWAYS_EXECUTED_IN (bb
);
473 level
= superloop_at_depth (loop
, 1);
474 lim_data
->max_loop
= level
;
476 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
477 if (!add_dependency (val
, lim_data
, loop
, true))
480 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
481 if (!add_dependency (val
, lim_data
, loop
, false))
484 lim_data
->cost
+= stmt_cost (stmt
);
489 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
490 and that one of the operands of this statement is computed by STMT.
491 Ensure that STMT (together with all the statements that define its
492 operands) is hoisted at least out of the loop LEVEL. */
495 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
497 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
500 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
501 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
502 stmt_loop
= find_common_loop (stmt_loop
,
503 LIM_DATA (stmt
)->tgt_loop
->outer
);
504 if (flow_loop_nested_p (stmt_loop
, level
))
507 gcc_assert (LIM_DATA (stmt
));
508 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
509 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
511 LIM_DATA (stmt
)->tgt_loop
= level
;
512 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
513 set_level (dep
->stmt
, orig_loop
, level
);
516 /* Determines an outermost loop from that we want to hoist the statement STMT.
517 For now we chose the outermost possible loop. TODO -- use profiling
518 information to set it more sanely. */
521 set_profitable_level (tree stmt
)
523 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
526 /* Returns true if STMT is not a pure call. */
529 nonpure_call_p (tree stmt
)
531 tree call
= get_call_expr_in (stmt
);
536 return TREE_SIDE_EFFECTS (call
) != 0;
539 /* Releases the memory occupied by DATA. */
542 free_lim_aux_data (struct lim_aux_data
*data
)
544 struct depend
*dep
, *next
;
546 for (dep
= data
->depends
; dep
; dep
= next
)
554 /* Determine the outermost loops in that statements in basic block BB are
555 invariant, and record them to the LIM_DATA associated with the statements.
556 Callback for walk_dominator_tree. */
559 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
563 block_stmt_iterator bsi
;
565 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
566 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
568 if (!bb
->loop_father
->outer
)
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
572 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
573 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
575 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
577 stmt
= bsi_stmt (bsi
);
579 pos
= movement_possibility (stmt
);
580 if (pos
== MOVE_IMPOSSIBLE
)
582 if (nonpure_call_p (stmt
))
590 stmt_ann (stmt
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
591 LIM_DATA (stmt
)->always_executed_in
= outermost
;
593 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
596 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
598 LIM_DATA (stmt
)->max_loop
= NULL
;
602 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
604 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
605 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
606 LIM_DATA (stmt
)->max_loop
->depth
,
607 LIM_DATA (stmt
)->cost
);
610 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
611 set_profitable_level (stmt
);
615 /* For each statement determines the outermost loop in that it is invariant,
616 statements on whose motion it depends and the cost of the computation.
617 This information is stored to the LIM_DATA structure associated with
621 determine_invariantness (void)
623 struct dom_walk_data walk_data
;
625 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
626 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
628 init_walk_dominator_tree (&walk_data
);
629 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
630 fini_walk_dominator_tree (&walk_data
);
633 /* Commits edge insertions and updates loop structures. */
636 loop_commit_inserts (void)
638 unsigned old_last_basic_block
, i
;
641 old_last_basic_block
= last_basic_block
;
642 bsi_commit_edge_inserts ();
643 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
645 bb
= BASIC_BLOCK (i
);
647 find_common_loop (single_pred (bb
)->loop_father
,
648 single_succ (bb
)->loop_father
));
652 /* Hoist the statements in basic block BB out of the loops prescribed by
653 data stored in LIM_DATA structures associated with each statement. Callback
654 for walk_dominator_tree. */
657 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
661 block_stmt_iterator bsi
;
665 if (!bb
->loop_father
->outer
)
668 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
670 stmt
= bsi_stmt (bsi
);
672 if (!LIM_DATA (stmt
))
678 cost
= LIM_DATA (stmt
)->cost
;
679 level
= LIM_DATA (stmt
)->tgt_loop
;
680 free_lim_aux_data (LIM_DATA (stmt
));
681 stmt_ann (stmt
)->common
.aux
= NULL
;
689 /* We do not really want to move conditionals out of the loop; we just
690 placed it here to force its operands to be moved if necessary. */
691 if (TREE_CODE (stmt
) == COND_EXPR
)
694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
696 fprintf (dump_file
, "Moving statement\n");
697 print_generic_stmt (dump_file
, stmt
, 0);
698 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
701 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
706 /* Hoist the statements out of the loops prescribed by data stored in
707 LIM_DATA structures associated with each statement.*/
710 move_computations (void)
712 struct dom_walk_data walk_data
;
714 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
715 walk_data
.before_dom_children_before_stmts
= move_computations_stmt
;
717 init_walk_dominator_tree (&walk_data
);
718 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
719 fini_walk_dominator_tree (&walk_data
);
721 loop_commit_inserts ();
722 rewrite_into_ssa (false);
723 if (!bitmap_empty_p (vars_to_rename
))
725 /* The rewrite of ssa names may cause violation of loop closed ssa
726 form invariants. TODO -- avoid these rewrites completely.
727 Information in virtual phi nodes is sufficient for it. */
728 rewrite_into_loop_closed_ssa (NULL
);
730 bitmap_clear (vars_to_rename
);
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;
975 struct sra_data sra_data
;
983 sra_data
.mem_refs
= mem_refs
;
984 sra_data
.common_ref
= NULL_TREE
;
987 SET_BIT (seen
, get_stmt_uid (stmt
));
988 *seen_call_stmt
= false;
992 stmt
= queue
[--in_queue
];
993 sra_data
.stmt
= stmt
;
996 && LIM_DATA (stmt
)->sm_done
)
999 switch (TREE_CODE (stmt
))
1004 if (!for_each_memref (stmt
, fem_single_reachable_address
,
1008 /* If this is a function that may depend on the memory location,
1009 record the fact. We cannot directly refuse call clobbered
1010 operands here, since sra_data.common_ref did not have
1012 call
= get_call_expr_in (stmt
);
1014 && !(call_expr_flags (call
) & ECF_CONST
))
1015 *seen_call_stmt
= true;
1017 /* Traverse also definitions of the VUSES (there may be other
1018 distinct from the one we used to get to this statement). */
1019 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1020 maybe_queue_var (val
, loop
, seen
, queue
, &in_queue
);
1025 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (stmt
); i
++)
1026 if (TREE_CODE (PHI_ARG_DEF (stmt
, i
)) == SSA_NAME
)
1027 maybe_queue_var (PHI_ARG_DEF (stmt
, i
), loop
,
1028 seen
, queue
, &in_queue
);
1035 /* Find uses of virtual names. */
1036 df
= get_immediate_uses (stmt
);
1037 n
= num_immediate_uses (df
);
1039 for (i
= 0; i
< n
; i
++)
1041 stmt
= immediate_use (df
, i
);
1043 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (stmt
)))
1046 if (TEST_BIT (seen
, get_stmt_uid (stmt
)))
1048 SET_BIT (seen
, get_stmt_uid (stmt
));
1050 queue
[in_queue
++] = stmt
;
1055 sbitmap_free (seen
);
1057 return sra_data
.common_ref
;
1060 free_mem_refs (*mem_refs
);
1063 sbitmap_free (seen
);
1068 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1071 rewrite_mem_refs (tree tmp_var
, struct mem_ref
*mem_refs
)
1076 for (; mem_refs
; mem_refs
= mem_refs
->next
)
1078 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1080 var
= SSA_NAME_VAR (var
);
1081 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1084 *mem_refs
->ref
= tmp_var
;
1085 modify_stmt (mem_refs
->stmt
);
1089 /* Records request for store motion of memory reference REF from LOOP.
1090 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1091 these references are rewritten by a new temporary variable.
1092 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1093 The initialization of the temporary variable is put to the preheader
1094 of the loop, and assignments to the reference from the temporary variable
1095 are emitted to exits. */
1098 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
1099 struct mem_ref
*mem_refs
)
1101 struct mem_ref
*aref
;
1105 struct fmt_data fmt_data
;
1107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1109 fprintf (dump_file
, "Executing store motion of ");
1110 print_generic_expr (dump_file
, ref
, 0);
1111 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1114 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
1116 fmt_data
.loop
= loop
;
1117 fmt_data
.orig_loop
= loop
;
1118 for_each_index (&ref
, force_move_till
, &fmt_data
);
1120 rewrite_mem_refs (tmp_var
, mem_refs
);
1121 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1122 if (LIM_DATA (aref
->stmt
))
1123 LIM_DATA (aref
->stmt
)->sm_done
= true;
1125 /* Emit the load & stores. */
1126 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
1127 get_stmt_ann (load
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
1128 LIM_DATA (load
)->max_loop
= loop
;
1129 LIM_DATA (load
)->tgt_loop
= loop
;
1131 /* Put this into the latch, so that we are sure it will be processed after
1132 all dependencies. */
1133 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
1135 for (i
= 0; i
< n_exits
; i
++)
1137 store
= build (MODIFY_EXPR
, void_type_node
,
1138 unshare_expr (ref
), tmp_var
);
1139 bsi_insert_on_edge (exits
[i
], store
);
1143 /* Returns true if REF may be clobbered by calls. */
1146 is_call_clobbered_ref (tree ref
)
1150 base
= get_base_address (ref
);
1155 return is_call_clobbered (base
);
1157 if (INDIRECT_REF_P (base
))
1159 /* Check whether the alias tags associated with the pointer
1160 are call clobbered. */
1161 tree ptr
= TREE_OPERAND (base
, 0);
1162 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1163 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
1164 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
1166 if ((nmt
&& is_call_clobbered (nmt
))
1167 || (tmt
&& is_call_clobbered (tmt
)))
1176 /* Determine whether all memory references inside LOOP corresponding to the
1177 virtual ssa name REG are equal to each other, and whether the address of
1178 this common reference can be hoisted outside of the loop. If this is true,
1179 prepare the statements that load the value of the memory reference to a
1180 temporary variable in the loop preheader, store it back on the loop exits,
1181 and replace all the references inside LOOP by this temporary variable.
1182 LOOP has N_EXITS stored in EXITS. */
1185 determine_lsm_reg (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree reg
)
1188 struct mem_ref
*mem_refs
, *aref
;
1189 struct loop
*must_exec
;
1192 if (is_gimple_reg (reg
))
1195 ref
= single_reachable_address (loop
, SSA_NAME_DEF_STMT (reg
), &mem_refs
,
1200 /* If we cannot create a ssa name for the result, give up. */
1201 if (!is_gimple_reg_type (TREE_TYPE (ref
))
1202 || TREE_THIS_VOLATILE (ref
))
1205 /* If there is a call that may use the location, give up as well. */
1207 && is_call_clobbered_ref (ref
))
1210 if (!for_each_index (&ref
, may_move_till
, loop
))
1213 if (tree_could_trap_p (ref
))
1215 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1216 of the statements in that it occurs is always executed when the loop
1217 is entered. This way we know that by moving the load from the
1218 reference out of the loop we will not cause the error that would not
1221 TODO -- in fact we would like to check for anticipability of the
1222 reference, i.e. that on each path from loop entry to loop exit at
1223 least one of the statements containing the memory reference is
1226 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1228 if (!LIM_DATA (aref
->stmt
))
1231 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1235 if (must_exec
== loop
1236 || flow_loop_nested_p (must_exec
, loop
))
1244 schedule_sm (loop
, exits
, n_exits
, ref
, mem_refs
);
1247 free_mem_refs (mem_refs
);
1250 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1251 for a store motion optimization (i.e. whether we can insert statement
1255 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1260 for (i
= 0; i
< n_exits
; i
++)
1261 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1267 /* Try to perform store motion for all memory references modified inside
1271 determine_lsm_loop (struct loop
*loop
)
1275 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1277 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1283 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
1284 determine_lsm_reg (loop
, exits
, n_exits
, PHI_RESULT (phi
));
1289 /* Try to perform store motion for all memory references modified inside
1293 determine_lsm (struct loops
*loops
)
1298 if (!loops
->tree_root
->inner
)
1301 /* Create a UID for each statement in the function. Ordering of the
1302 UIDs is not important for this pass. */
1306 block_stmt_iterator bsi
;
1308 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1309 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
1312 compute_immediate_uses (TDFA_USE_VOPS
, NULL
);
1314 /* Pass the loops from the outermost. For each virtual operand loop phi node
1315 check whether all the references inside the loop correspond to a single
1316 address, and if so, move them. */
1318 loop
= loops
->tree_root
->inner
;
1321 determine_lsm_loop (loop
);
1331 if (loop
== loops
->tree_root
)
1334 loop_commit_inserts ();
1342 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1343 for each such basic block bb records the outermost loop for that execution
1344 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1345 blocks that contain a nonpure call. */
1348 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1350 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1353 struct loop
*inn_loop
= loop
;
1355 if (!loop
->header
->aux
)
1357 bbs
= get_loop_body_in_dom_order (loop
);
1359 for (i
= 0; i
< loop
->num_nodes
; i
++)
1364 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1367 if (TEST_BIT (contains_call
, bb
->index
))
1370 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1371 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1376 /* A loop might be infinite (TODO use simple loop analysis
1377 to disprove this if possible). */
1378 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1381 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1384 if (bb
->loop_father
->header
== bb
)
1386 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1389 /* In a loop that is always entered we may proceed anyway.
1390 But record that we entered it and stop once we leave it. */
1391 inn_loop
= bb
->loop_father
;
1398 if (last
== loop
->header
)
1400 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1406 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1407 fill_always_executed_in (loop
, contains_call
);
1410 /* Compute the global information needed by the loop invariant motion pass.
1411 LOOPS is the loop tree. */
1414 tree_ssa_lim_initialize (struct loops
*loops
)
1416 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1417 block_stmt_iterator bsi
;
1421 sbitmap_zero (contains_call
);
1424 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1426 if (nonpure_call_p (bsi_stmt (bsi
)))
1430 if (!bsi_end_p (bsi
))
1431 SET_BIT (contains_call
, bb
->index
);
1434 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1435 fill_always_executed_in (loop
, contains_call
);
1437 sbitmap_free (contains_call
);
1440 /* Cleans up after the invariant motion pass. */
1443 tree_ssa_lim_finalize (void)
1453 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1454 i.e. those that are likely to be win regardless of the register pressure. */
1457 tree_ssa_lim (struct loops
*loops
)
1459 tree_ssa_lim_initialize (loops
);
1461 /* For each statement determine the outermost loop in that it is
1462 invariant and cost for computing the invariant. */
1463 determine_invariantness ();
1465 /* For each memory reference determine whether it is possible to hoist it
1466 out of the loop. Force the necessary invariants to be moved out of the
1468 determine_lsm (loops
);
1470 /* Move the expressions that are expensive enough. */
1471 move_computations ();
1473 tree_ssa_lim_finalize ();