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"
42 /* TODO: Support for predicated code motion. I.e.
53 Where COND and INV are is invariants, but evaluating INV may trap or be
54 invalid from some other reason if !COND. This may be transformed to
64 /* A type for the list of statements that have to be moved in order to be able
65 to hoist an invariant computation. */
73 /* The auxiliary data kept for each statement. */
77 struct loop
*max_loop
; /* The outermost loop in that the statement
80 struct loop
*tgt_loop
; /* The loop out of that we want to move the
83 struct loop
*always_executed_in
;
84 /* The outermost loop for that we are sure
85 the statement is executed if the loop
88 bool sm_done
; /* True iff the store motion for a memory
89 reference in the statement has already
92 unsigned cost
; /* Cost of the computation performed by the
95 struct depend
*depends
; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
102 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
104 : (struct lim_aux_data *) (stmt_ann (STMT)->aux))
106 /* Description of a memory reference for store motion. */
110 tree
*ref
; /* The reference itself. */
111 tree stmt
; /* The statement in that it occurs. */
112 struct mem_ref
*next
; /* Next use in the chain. */
115 /* Minimum cost of an expensive expression. */
116 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
118 /* The outermost loop for that execution of the header guarantees that the
119 block will be executed. */
120 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
122 static unsigned max_stmt_uid
; /* Maximal uid of a statement. Uids to phi
123 nodes are assigned using the versions of
124 ssa names they define. */
126 /* Returns uid of statement STMT. */
129 get_stmt_uid (tree stmt
)
131 if (TREE_CODE (stmt
) == PHI_NODE
)
132 return SSA_NAME_VERSION (PHI_RESULT (stmt
)) + max_stmt_uid
;
134 return stmt_ann (stmt
)->uid
;
137 /* Calls CBCK for each index in memory reference ADDR_P. There are two
138 kinds situations handled; in each of these cases, the memory reference
139 and DATA are passed to the callback:
141 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
142 pass the pointer to the index to the callback.
144 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
145 pointer to addr to the callback.
147 If the callback returns false, the whole search stops and false is returned.
148 Otherwise the function returns true after traversing through the whole
149 reference *ADDR_P. */
152 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
156 for (; ; addr_p
= nxt
)
158 switch (TREE_CODE (*addr_p
))
161 return cbck (*addr_p
, addr_p
, data
);
163 case MISALIGNED_INDIRECT_REF
:
164 case ALIGN_INDIRECT_REF
:
166 nxt
= &TREE_OPERAND (*addr_p
, 0);
167 return cbck (*addr_p
, nxt
, data
);
170 case VIEW_CONVERT_EXPR
:
171 case ARRAY_RANGE_REF
:
174 nxt
= &TREE_OPERAND (*addr_p
, 0);
178 /* If the component has varying offset, it behaves like index
180 idx
= &TREE_OPERAND (*addr_p
, 2);
182 && !cbck (*addr_p
, idx
, data
))
185 nxt
= &TREE_OPERAND (*addr_p
, 0);
189 nxt
= &TREE_OPERAND (*addr_p
, 0);
190 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 return MOVE_POSSIBLE
;
226 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
227 return MOVE_IMPOSSIBLE
;
229 if (stmt_ends_bb_p (stmt
))
230 return MOVE_IMPOSSIBLE
;
232 if (stmt_ann (stmt
)->has_volatile_ops
)
233 return MOVE_IMPOSSIBLE
;
235 lhs
= TREE_OPERAND (stmt
, 0);
236 if (TREE_CODE (lhs
) == SSA_NAME
237 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
238 return MOVE_IMPOSSIBLE
;
240 rhs
= TREE_OPERAND (stmt
, 1);
242 if (TREE_SIDE_EFFECTS (rhs
))
243 return MOVE_IMPOSSIBLE
;
245 if (TREE_CODE (lhs
) != SSA_NAME
246 || tree_could_trap_p (rhs
))
247 return MOVE_PRESERVE_EXECUTION
;
249 if (get_call_expr_in (stmt
))
251 /* While pure or const call is guaranteed to have no side effects, we
252 cannot move it arbitrarily. Consider code like
254 char *s = something ();
264 Here the strlen call cannot be moved out of the loop, even though
265 s is invariant. In addition to possibly creating a call with
266 invalid arguments, moving out a function call that is not executed
267 may cause performance regressions in case the call is costly and
268 not executed at all. */
269 return MOVE_PRESERVE_EXECUTION
;
271 return MOVE_POSSIBLE
;
274 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
275 loop to that we could move the expression using DEF if it did not have
276 other operands, i.e. the outermost loop enclosing LOOP in that the value
277 of DEF is invariant. */
280 outermost_invariant_loop (tree def
, struct loop
*loop
)
284 struct loop
*max_loop
;
286 if (TREE_CODE (def
) != SSA_NAME
)
287 return superloop_at_depth (loop
, 1);
289 def_stmt
= SSA_NAME_DEF_STMT (def
);
290 def_bb
= bb_for_stmt (def_stmt
);
292 return superloop_at_depth (loop
, 1);
294 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
296 if (LIM_DATA (def_stmt
) && LIM_DATA (def_stmt
)->max_loop
)
297 max_loop
= find_common_loop (max_loop
,
298 LIM_DATA (def_stmt
)->max_loop
->outer
);
299 if (max_loop
== loop
)
301 max_loop
= superloop_at_depth (loop
, max_loop
->depth
+ 1);
306 /* Returns the outermost superloop of LOOP in that the expression EXPR is
310 outermost_invariant_loop_expr (tree expr
, struct loop
*loop
)
312 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
314 struct loop
*max_loop
= superloop_at_depth (loop
, 1), *aloop
;
316 if (TREE_CODE (expr
) == SSA_NAME
317 || TREE_CODE (expr
) == INTEGER_CST
318 || is_gimple_min_invariant (expr
))
319 return outermost_invariant_loop (expr
, loop
);
321 if (class != tcc_unary
322 && class != tcc_binary
323 && class != tcc_expression
324 && class != tcc_comparison
)
327 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
328 for (i
= 0; i
< nops
; i
++)
330 aloop
= outermost_invariant_loop_expr (TREE_OPERAND (expr
, i
), loop
);
334 if (flow_loop_nested_p (max_loop
, aloop
))
341 /* DATA is a structure containing information associated with a statement
342 inside LOOP. DEF is one of the operands of this statement.
344 Find the outermost loop enclosing LOOP in that value of DEF is invariant
345 and record this in DATA->max_loop field. If DEF itself is defined inside
346 this loop as well (i.e. we need to hoist it out of the loop if we want
347 to hoist the statement represented by DATA), record the statement in that
348 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
349 add the cost of the computation of DEF to the DATA->cost.
351 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
354 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
357 tree def_stmt
= SSA_NAME_DEF_STMT (def
);
358 basic_block def_bb
= bb_for_stmt (def_stmt
);
359 struct loop
*max_loop
;
365 max_loop
= outermost_invariant_loop (def
, loop
);
369 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
370 data
->max_loop
= max_loop
;
372 if (!LIM_DATA (def_stmt
))
376 /* Only add the cost if the statement defining DEF is inside LOOP,
377 i.e. if it is likely that by moving the invariants dependent
378 on it, we will be able to avoid creating a new register for
379 it (since it will be only used in these dependent invariants). */
380 && def_bb
->loop_father
== loop
)
381 data
->cost
+= LIM_DATA (def_stmt
)->cost
;
383 dep
= xmalloc (sizeof (struct depend
));
384 dep
->stmt
= def_stmt
;
385 dep
->next
= data
->depends
;
391 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
392 are just ad-hoc constants. The estimates should be based on target-specific
396 stmt_cost (tree stmt
)
401 /* Always try to create possibilities for unswitching. */
402 if (TREE_CODE (stmt
) == COND_EXPR
)
403 return LIM_EXPENSIVE
;
405 rhs
= TREE_OPERAND (stmt
, 1);
407 /* Hoisting memory references out should almost surely be a win. */
408 if (stmt_references_memory_p (stmt
))
411 switch (TREE_CODE (rhs
))
414 /* We should be hoisting calls if possible. */
416 /* Unless the call is a builtin_constant_p; this always folds to a
417 constant, so moving it is useless. */
418 rhs
= get_callee_fndecl (rhs
);
419 if (DECL_BUILT_IN_CLASS (rhs
) == BUILT_IN_NORMAL
420 && DECL_FUNCTION_CODE (rhs
) == BUILT_IN_CONSTANT_P
)
437 /* Division and multiplication are usually expensive. */
448 /* Determine the outermost loop to that it is possible to hoist a statement
449 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
450 the outermost loop in that the value computed by STMT is invariant.
451 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
452 we preserve the fact whether STMT is executed. It also fills other related
453 information to LIM_DATA (STMT).
455 The function returns false if STMT cannot be hoisted outside of the loop it
456 is defined in, and true otherwise. */
459 determine_max_movement (tree stmt
, bool must_preserve_exec
)
461 basic_block bb
= bb_for_stmt (stmt
);
462 struct loop
*loop
= bb
->loop_father
;
464 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
468 if (must_preserve_exec
)
469 level
= ALWAYS_EXECUTED_IN (bb
);
471 level
= superloop_at_depth (loop
, 1);
472 lim_data
->max_loop
= level
;
474 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
475 if (!add_dependency (val
, lim_data
, loop
, true))
478 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
479 if (!add_dependency (val
, lim_data
, loop
, false))
482 lim_data
->cost
+= stmt_cost (stmt
);
487 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
488 and that one of the operands of this statement is computed by STMT.
489 Ensure that STMT (together with all the statements that define its
490 operands) is hoisted at least out of the loop LEVEL. */
493 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
495 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
498 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
499 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
500 stmt_loop
= find_common_loop (stmt_loop
,
501 LIM_DATA (stmt
)->tgt_loop
->outer
);
502 if (flow_loop_nested_p (stmt_loop
, level
))
505 gcc_assert (LIM_DATA (stmt
));
506 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
507 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
509 LIM_DATA (stmt
)->tgt_loop
= level
;
510 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
511 set_level (dep
->stmt
, orig_loop
, level
);
514 /* Determines an outermost loop from that we want to hoist the statement STMT.
515 For now we chose the outermost possible loop. TODO -- use profiling
516 information to set it more sanely. */
519 set_profitable_level (tree stmt
)
521 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
524 /* Returns true if STMT is not a pure call. */
527 nonpure_call_p (tree stmt
)
529 tree call
= get_call_expr_in (stmt
);
534 return TREE_SIDE_EFFECTS (call
) != 0;
537 /* Releases the memory occupied by DATA. */
540 free_lim_aux_data (struct lim_aux_data
*data
)
542 struct depend
*dep
, *next
;
544 for (dep
= data
->depends
; dep
; dep
= next
)
552 /* Determine the outermost loops in that statements in basic block BB are
553 invariant, and record them to the LIM_DATA associated with the statements.
554 Callback for walk_dominator_tree. */
557 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
561 block_stmt_iterator bsi
;
563 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
564 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
566 if (!bb
->loop_father
->outer
)
569 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
570 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
571 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
573 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
575 stmt
= bsi_stmt (bsi
);
577 pos
= movement_possibility (stmt
);
578 if (pos
== MOVE_IMPOSSIBLE
)
580 if (nonpure_call_p (stmt
))
588 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
589 to be hoisted out of loop, saving expensive divide. */
590 if (pos
== MOVE_POSSIBLE
591 && (rhs
= TREE_OPERAND (stmt
, 1)) != NULL
592 && TREE_CODE (rhs
) == RDIV_EXPR
593 && flag_unsafe_math_optimizations
594 && outermost_invariant_loop_expr (TREE_OPERAND (rhs
, 1),
595 loop_containing_stmt (stmt
)) != NULL
596 && outermost_invariant_loop_expr (rhs
,
597 loop_containing_stmt (stmt
)) == NULL
)
599 tree lhs
, stmt1
, stmt2
, var
, name
;
601 lhs
= TREE_OPERAND (stmt
, 0);
603 /* stmt must be MODIFY_EXPR. */
604 var
= create_tmp_var (TREE_TYPE (rhs
), "reciptmp");
605 add_referenced_tmp_var (var
);
607 stmt1
= build2 (MODIFY_EXPR
, void_type_node
, var
,
608 build2 (RDIV_EXPR
, TREE_TYPE (rhs
),
609 build_real (TREE_TYPE (rhs
), dconst1
),
610 TREE_OPERAND (rhs
, 1)));
611 name
= make_ssa_name (var
, stmt1
);
612 TREE_OPERAND (stmt1
, 0) = name
;
613 stmt2
= build2 (MODIFY_EXPR
, void_type_node
, lhs
,
614 build2 (MULT_EXPR
, TREE_TYPE (rhs
),
615 name
, TREE_OPERAND (rhs
, 0)));
617 /* Replace division stmt with reciprocal and multiply stmts.
618 The multiply stmt is not invariant, so update iterator
619 and avoid rescanning. */
620 bsi_replace (&bsi
, stmt1
, true);
621 bsi_insert_after (&bsi
, stmt2
, BSI_NEW_STMT
);
622 SSA_NAME_DEF_STMT (lhs
) = stmt2
;
624 /* Continue processing with invariant reciprocal statment. */
628 stmt_ann (stmt
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
629 LIM_DATA (stmt
)->always_executed_in
= outermost
;
631 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
634 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
636 LIM_DATA (stmt
)->max_loop
= NULL
;
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
642 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
643 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
644 LIM_DATA (stmt
)->max_loop
->depth
,
645 LIM_DATA (stmt
)->cost
);
648 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
649 set_profitable_level (stmt
);
653 /* For each statement determines the outermost loop in that it is invariant,
654 statements on whose motion it depends and the cost of the computation.
655 This information is stored to the LIM_DATA structure associated with
659 determine_invariantness (void)
661 struct dom_walk_data walk_data
;
663 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
664 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
666 init_walk_dominator_tree (&walk_data
);
667 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
668 fini_walk_dominator_tree (&walk_data
);
671 /* Commits edge insertions and updates loop structures. */
674 loop_commit_inserts (void)
676 unsigned old_last_basic_block
, i
;
679 old_last_basic_block
= last_basic_block
;
680 bsi_commit_edge_inserts ();
681 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
683 bb
= BASIC_BLOCK (i
);
685 find_common_loop (single_pred (bb
)->loop_father
,
686 single_succ (bb
)->loop_father
));
690 /* Hoist the statements in basic block BB out of the loops prescribed by
691 data stored in LIM_DATA structures associated with each statement. Callback
692 for walk_dominator_tree. */
695 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
699 block_stmt_iterator bsi
;
703 if (!bb
->loop_father
->outer
)
706 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
708 stmt
= bsi_stmt (bsi
);
710 if (!LIM_DATA (stmt
))
716 cost
= LIM_DATA (stmt
)->cost
;
717 level
= LIM_DATA (stmt
)->tgt_loop
;
718 free_lim_aux_data (LIM_DATA (stmt
));
719 stmt_ann (stmt
)->aux
= NULL
;
727 /* We do not really want to move conditionals out of the loop; we just
728 placed it here to force its operands to be moved if necessary. */
729 if (TREE_CODE (stmt
) == COND_EXPR
)
732 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
734 fprintf (dump_file
, "Moving statement\n");
735 print_generic_stmt (dump_file
, stmt
, 0);
736 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
739 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
744 /* Hoist the statements out of the loops prescribed by data stored in
745 LIM_DATA structures associated with each statement.*/
748 move_computations (void)
750 struct dom_walk_data walk_data
;
752 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
753 walk_data
.before_dom_children_before_stmts
= move_computations_stmt
;
755 init_walk_dominator_tree (&walk_data
);
756 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
757 fini_walk_dominator_tree (&walk_data
);
759 loop_commit_inserts ();
760 if (need_ssa_update_p ())
761 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
764 /* Checks whether the statement defining variable *INDEX can be hoisted
765 out of the loop passed in DATA. Callback for for_each_index. */
768 may_move_till (tree ref
, tree
*index
, void *data
)
770 struct loop
*loop
= data
, *max_loop
;
772 /* If REF is an array reference, check also that the step and the lower
773 bound is invariant in LOOP. */
774 if (TREE_CODE (ref
) == ARRAY_REF
)
776 tree step
= array_ref_element_size (ref
);
777 tree lbound
= array_ref_low_bound (ref
);
779 max_loop
= outermost_invariant_loop_expr (step
, loop
);
783 max_loop
= outermost_invariant_loop_expr (lbound
, loop
);
788 max_loop
= outermost_invariant_loop (*index
, loop
);
795 /* Forces statements defining (invariant) SSA names in expression EXPR to be
796 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
799 force_move_till_expr (tree expr
, struct loop
*orig_loop
, struct loop
*loop
)
801 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
804 if (TREE_CODE (expr
) == SSA_NAME
)
806 tree stmt
= SSA_NAME_DEF_STMT (expr
);
807 if (IS_EMPTY_STMT (stmt
))
810 set_level (stmt
, orig_loop
, loop
);
814 if (class != tcc_unary
815 && class != tcc_binary
816 && class != tcc_expression
817 && class != tcc_comparison
)
820 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
821 for (i
= 0; i
< nops
; i
++)
822 force_move_till_expr (TREE_OPERAND (expr
, i
), orig_loop
, loop
);
825 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
826 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
832 struct loop
*orig_loop
;
836 force_move_till (tree ref
, tree
*index
, void *data
)
839 struct fmt_data
*fmt_data
= data
;
841 if (TREE_CODE (ref
) == ARRAY_REF
)
843 tree step
= array_ref_element_size (ref
);
844 tree lbound
= array_ref_low_bound (ref
);
846 force_move_till_expr (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
847 force_move_till_expr (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
850 if (TREE_CODE (*index
) != SSA_NAME
)
853 stmt
= SSA_NAME_DEF_STMT (*index
);
854 if (IS_EMPTY_STMT (stmt
))
857 set_level (stmt
, fmt_data
->orig_loop
, fmt_data
->loop
);
862 /* Records memory reference *REF (that occurs in statement STMT)
863 to the list MEM_REFS. */
866 record_mem_ref (struct mem_ref
**mem_refs
, tree stmt
, tree
*ref
)
868 struct mem_ref
*aref
= xmalloc (sizeof (struct mem_ref
));
873 aref
->next
= *mem_refs
;
877 /* Releases list of memory references MEM_REFS. */
880 free_mem_refs (struct mem_ref
*mem_refs
)
887 mem_refs
= mem_refs
->next
;
892 /* If VAR is defined in LOOP and the statement it is defined in does not belong
893 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
897 maybe_queue_var (tree var
, struct loop
*loop
,
898 sbitmap seen
, tree
*queue
, unsigned *in_queue
)
900 tree stmt
= SSA_NAME_DEF_STMT (var
);
901 basic_block def_bb
= bb_for_stmt (stmt
);
904 || !flow_bb_inside_loop_p (loop
, def_bb
)
905 || TEST_BIT (seen
, get_stmt_uid (stmt
)))
908 SET_BIT (seen
, get_stmt_uid (stmt
));
909 queue
[(*in_queue
)++] = stmt
;
912 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
913 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
914 Record the reference OP to list MEM_REFS. STMT is the statement in that
915 the reference occurs. */
919 struct mem_ref
**mem_refs
;
925 fem_single_reachable_address (tree
*op
, void *data
)
927 struct sra_data
*sra_data
= data
;
929 if (sra_data
->common_ref
930 && !operand_equal_p (*op
, sra_data
->common_ref
, 0))
932 sra_data
->common_ref
= *op
;
934 record_mem_ref (sra_data
->mem_refs
, sra_data
->stmt
, op
);
938 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
939 is passed to the CALLBACK as well. The traversal stops if CALLBACK
940 returns false, for_each_memref then returns false as well. Otherwise
941 for_each_memref returns true. */
944 for_each_memref (tree stmt
, bool (*callback
)(tree
*, void *), void *data
)
948 if (TREE_CODE (stmt
) == RETURN_EXPR
)
949 stmt
= TREE_OPERAND (stmt
, 1);
951 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
953 op
= &TREE_OPERAND (stmt
, 0);
954 if (TREE_CODE (*op
) != SSA_NAME
955 && !callback (op
, data
))
958 op
= &TREE_OPERAND (stmt
, 1);
959 if (TREE_CODE (*op
) != SSA_NAME
960 && is_gimple_lvalue (*op
)
961 && !callback (op
, data
))
964 stmt
= TREE_OPERAND (stmt
, 1);
967 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
968 stmt
= TREE_OPERAND (stmt
, 0);
970 if (TREE_CODE (stmt
) == CALL_EXPR
)
974 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
976 op
= &TREE_VALUE (args
);
978 if (TREE_CODE (*op
) != SSA_NAME
979 && is_gimple_lvalue (*op
)
980 && !callback (op
, data
))
988 /* Determine whether all memory references inside the LOOP that correspond
989 to virtual ssa names defined in statement STMT are equal.
990 If so, store the list of the references to MEM_REFS, and return one
991 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
992 *SEEN_CALL_STMT is set to true if the virtual operands suggest
993 that the reference might be clobbered by a call inside the LOOP. */
996 single_reachable_address (struct loop
*loop
, tree stmt
,
997 struct mem_ref
**mem_refs
,
998 bool *seen_call_stmt
)
1000 unsigned max_uid
= max_stmt_uid
+ num_ssa_names
;
1001 tree
*queue
= xmalloc (sizeof (tree
) * max_uid
);
1002 sbitmap seen
= sbitmap_alloc (max_uid
);
1003 unsigned in_queue
= 1;
1005 struct sra_data sra_data
;
1009 imm_use_iterator imm_iter
;
1010 use_operand_p use_p
;
1012 sbitmap_zero (seen
);
1015 sra_data
.mem_refs
= mem_refs
;
1016 sra_data
.common_ref
= NULL_TREE
;
1019 SET_BIT (seen
, get_stmt_uid (stmt
));
1020 *seen_call_stmt
= false;
1024 stmt
= queue
[--in_queue
];
1025 sra_data
.stmt
= stmt
;
1028 && LIM_DATA (stmt
)->sm_done
)
1031 switch (TREE_CODE (stmt
))
1036 if (!for_each_memref (stmt
, fem_single_reachable_address
,
1040 /* If this is a function that may depend on the memory location,
1041 record the fact. We cannot directly refuse call clobbered
1042 operands here, since sra_data.common_ref did not have
1044 call
= get_call_expr_in (stmt
);
1046 && !(call_expr_flags (call
) & ECF_CONST
))
1047 *seen_call_stmt
= true;
1049 /* Traverse also definitions of the VUSES (there may be other
1050 distinct from the one we used to get to this statement). */
1051 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1052 maybe_queue_var (val
, loop
, seen
, queue
, &in_queue
);
1057 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (stmt
); i
++)
1058 if (TREE_CODE (PHI_ARG_DEF (stmt
, i
)) == SSA_NAME
)
1059 maybe_queue_var (PHI_ARG_DEF (stmt
, i
), loop
,
1060 seen
, queue
, &in_queue
);
1067 /* Find uses of virtual names. */
1068 if (TREE_CODE (stmt
) == PHI_NODE
)
1070 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (stmt
))))
1071 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, PHI_RESULT (stmt
))
1073 tree imm_stmt
= USE_STMT (use_p
);
1075 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1078 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1081 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1083 queue
[in_queue
++] = imm_stmt
;
1087 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
1088 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
1090 tree imm_stmt
= USE_STMT (use_p
);
1092 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1095 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1098 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1100 queue
[in_queue
++] = imm_stmt
;
1105 sbitmap_free (seen
);
1107 return sra_data
.common_ref
;
1110 free_mem_refs (*mem_refs
);
1113 sbitmap_free (seen
);
1118 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1121 rewrite_mem_refs (tree tmp_var
, struct mem_ref
*mem_refs
)
1126 for (; mem_refs
; mem_refs
= mem_refs
->next
)
1128 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1129 mark_sym_for_renaming (SSA_NAME_VAR (var
));
1131 *mem_refs
->ref
= tmp_var
;
1132 update_stmt (mem_refs
->stmt
);
1136 /* Records request for store motion of memory reference REF from LOOP.
1137 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1138 these references are rewritten by a new temporary variable.
1139 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1140 The initialization of the temporary variable is put to the preheader
1141 of the loop, and assignments to the reference from the temporary variable
1142 are emitted to exits. */
1145 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
1146 struct mem_ref
*mem_refs
)
1148 struct mem_ref
*aref
;
1152 struct fmt_data fmt_data
;
1154 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1156 fprintf (dump_file
, "Executing store motion of ");
1157 print_generic_expr (dump_file
, ref
, 0);
1158 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1161 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
1163 fmt_data
.loop
= loop
;
1164 fmt_data
.orig_loop
= loop
;
1165 for_each_index (&ref
, force_move_till
, &fmt_data
);
1167 rewrite_mem_refs (tmp_var
, mem_refs
);
1168 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1169 if (LIM_DATA (aref
->stmt
))
1170 LIM_DATA (aref
->stmt
)->sm_done
= true;
1172 /* Emit the load & stores. */
1173 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
1174 get_stmt_ann (load
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
1175 LIM_DATA (load
)->max_loop
= loop
;
1176 LIM_DATA (load
)->tgt_loop
= loop
;
1178 /* Put this into the latch, so that we are sure it will be processed after
1179 all dependencies. */
1180 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
1182 for (i
= 0; i
< n_exits
; i
++)
1184 store
= build (MODIFY_EXPR
, void_type_node
,
1185 unshare_expr (ref
), tmp_var
);
1186 bsi_insert_on_edge (exits
[i
], store
);
1190 /* Returns true if REF may be clobbered by calls. */
1193 is_call_clobbered_ref (tree ref
)
1196 HOST_WIDE_INT offset
, size
;
1201 if (TREE_CODE (sref
) == COMPONENT_REF
1202 && (sref
= okay_component_ref_for_subvars (sref
, &offset
, &size
)))
1204 svars
= get_subvars_for_var (sref
);
1205 for (sv
= svars
; sv
; sv
= sv
->next
)
1207 if (overlap_subvar (offset
, size
, sv
, NULL
)
1208 && is_call_clobbered (sv
->var
))
1213 base
= get_base_address (ref
);
1219 if (var_can_have_subvars (base
)
1220 && (svars
= get_subvars_for_var (base
)))
1222 for (sv
= svars
; sv
; sv
= sv
->next
)
1223 if (is_call_clobbered (sv
->var
))
1228 return is_call_clobbered (base
);
1231 if (INDIRECT_REF_P (base
))
1233 /* Check whether the alias tags associated with the pointer
1234 are call clobbered. */
1235 tree ptr
= TREE_OPERAND (base
, 0);
1236 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1237 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
1238 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
1240 if ((nmt
&& is_call_clobbered (nmt
))
1241 || (tmt
&& is_call_clobbered (tmt
)))
1250 /* Determine whether all memory references inside LOOP corresponding to the
1251 virtual ssa name REG are equal to each other, and whether the address of
1252 this common reference can be hoisted outside of the loop. If this is true,
1253 prepare the statements that load the value of the memory reference to a
1254 temporary variable in the loop preheader, store it back on the loop exits,
1255 and replace all the references inside LOOP by this temporary variable.
1256 LOOP has N_EXITS stored in EXITS. */
1259 determine_lsm_reg (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree reg
)
1262 struct mem_ref
*mem_refs
, *aref
;
1263 struct loop
*must_exec
;
1266 if (is_gimple_reg (reg
))
1269 ref
= single_reachable_address (loop
, SSA_NAME_DEF_STMT (reg
), &mem_refs
,
1274 /* If we cannot create a ssa name for the result, give up. */
1275 if (!is_gimple_reg_type (TREE_TYPE (ref
))
1276 || TREE_THIS_VOLATILE (ref
))
1279 /* If there is a call that may use the location, give up as well. */
1281 && is_call_clobbered_ref (ref
))
1284 if (!for_each_index (&ref
, may_move_till
, loop
))
1287 if (tree_could_trap_p (ref
))
1289 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1290 of the statements in that it occurs is always executed when the loop
1291 is entered. This way we know that by moving the load from the
1292 reference out of the loop we will not cause the error that would not
1295 TODO -- in fact we would like to check for anticipability of the
1296 reference, i.e. that on each path from loop entry to loop exit at
1297 least one of the statements containing the memory reference is
1300 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1302 if (!LIM_DATA (aref
->stmt
))
1305 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1309 if (must_exec
== loop
1310 || flow_loop_nested_p (must_exec
, loop
))
1318 schedule_sm (loop
, exits
, n_exits
, ref
, mem_refs
);
1321 free_mem_refs (mem_refs
);
1324 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1325 for a store motion optimization (i.e. whether we can insert statement
1329 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1334 for (i
= 0; i
< n_exits
; i
++)
1335 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1341 /* Try to perform store motion for all memory references modified inside
1345 determine_lsm_loop (struct loop
*loop
)
1349 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1351 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1357 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
1358 determine_lsm_reg (loop
, exits
, n_exits
, PHI_RESULT (phi
));
1363 /* Try to perform store motion for all memory references modified inside
1367 determine_lsm (struct loops
*loops
)
1372 if (!loops
->tree_root
->inner
)
1375 /* Create a UID for each statement in the function. Ordering of the
1376 UIDs is not important for this pass. */
1380 block_stmt_iterator bsi
;
1382 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1383 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
1386 /* Pass the loops from the outermost. For each virtual operand loop phi node
1387 check whether all the references inside the loop correspond to a single
1388 address, and if so, move them. */
1390 loop
= loops
->tree_root
->inner
;
1393 determine_lsm_loop (loop
);
1403 if (loop
== loops
->tree_root
)
1405 loop_commit_inserts ();
1413 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1414 for each such basic block bb records the outermost loop for that execution
1415 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1416 blocks that contain a nonpure call. */
1419 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1421 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1424 struct loop
*inn_loop
= loop
;
1426 if (!loop
->header
->aux
)
1428 bbs
= get_loop_body_in_dom_order (loop
);
1430 for (i
= 0; i
< loop
->num_nodes
; i
++)
1435 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1438 if (TEST_BIT (contains_call
, bb
->index
))
1441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1442 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1447 /* A loop might be infinite (TODO use simple loop analysis
1448 to disprove this if possible). */
1449 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1452 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1455 if (bb
->loop_father
->header
== bb
)
1457 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1460 /* In a loop that is always entered we may proceed anyway.
1461 But record that we entered it and stop once we leave it. */
1462 inn_loop
= bb
->loop_father
;
1469 if (last
== loop
->header
)
1471 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1477 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1478 fill_always_executed_in (loop
, contains_call
);
1481 /* Compute the global information needed by the loop invariant motion pass.
1482 LOOPS is the loop tree. */
1485 tree_ssa_lim_initialize (struct loops
*loops
)
1487 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1488 block_stmt_iterator bsi
;
1492 sbitmap_zero (contains_call
);
1495 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1497 if (nonpure_call_p (bsi_stmt (bsi
)))
1501 if (!bsi_end_p (bsi
))
1502 SET_BIT (contains_call
, bb
->index
);
1505 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1506 fill_always_executed_in (loop
, contains_call
);
1508 sbitmap_free (contains_call
);
1511 /* Cleans up after the invariant motion pass. */
1514 tree_ssa_lim_finalize (void)
1524 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1525 i.e. those that are likely to be win regardless of the register pressure. */
1528 tree_ssa_lim (struct loops
*loops
)
1530 tree_ssa_lim_initialize (loops
);
1532 /* For each statement determine the outermost loop in that it is
1533 invariant and cost for computing the invariant. */
1534 determine_invariantness ();
1536 /* For each memory reference determine whether it is possible to hoist it
1537 out of the loop. Force the necessary invariants to be moved out of the
1539 determine_lsm (loops
);
1541 /* Move the expressions that are expensive enough. */
1542 move_computations ();
1544 tree_ssa_lim_finalize ();