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)->common.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
)->common
.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
)->common
.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 ();
761 if (need_ssa_update_p ())
762 update_ssa (TODO_update_ssa
);
764 /* The movement of LI code may cause violation of loop closed SSA
765 form invariants. TODO -- avoid these rewrites completely.
766 Information in virtual phi nodes is sufficient for it. */
767 rewrite_into_loop_closed_ssa (NULL
);
770 /* Checks whether the statement defining variable *INDEX can be hoisted
771 out of the loop passed in DATA. Callback for for_each_index. */
774 may_move_till (tree ref
, tree
*index
, void *data
)
776 struct loop
*loop
= data
, *max_loop
;
778 /* If REF is an array reference, check also that the step and the lower
779 bound is invariant in LOOP. */
780 if (TREE_CODE (ref
) == ARRAY_REF
)
782 tree step
= array_ref_element_size (ref
);
783 tree lbound
= array_ref_low_bound (ref
);
785 max_loop
= outermost_invariant_loop_expr (step
, loop
);
789 max_loop
= outermost_invariant_loop_expr (lbound
, loop
);
794 max_loop
= outermost_invariant_loop (*index
, loop
);
801 /* Forces statements defining (invariant) SSA names in expression EXPR to be
802 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
805 force_move_till_expr (tree expr
, struct loop
*orig_loop
, struct loop
*loop
)
807 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
810 if (TREE_CODE (expr
) == SSA_NAME
)
812 tree stmt
= SSA_NAME_DEF_STMT (expr
);
813 if (IS_EMPTY_STMT (stmt
))
816 set_level (stmt
, orig_loop
, loop
);
820 if (class != tcc_unary
821 && class != tcc_binary
822 && class != tcc_expression
823 && class != tcc_comparison
)
826 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
827 for (i
= 0; i
< nops
; i
++)
828 force_move_till_expr (TREE_OPERAND (expr
, i
), orig_loop
, loop
);
831 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
832 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
838 struct loop
*orig_loop
;
842 force_move_till (tree ref
, tree
*index
, void *data
)
845 struct fmt_data
*fmt_data
= data
;
847 if (TREE_CODE (ref
) == ARRAY_REF
)
849 tree step
= array_ref_element_size (ref
);
850 tree lbound
= array_ref_low_bound (ref
);
852 force_move_till_expr (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
853 force_move_till_expr (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
856 if (TREE_CODE (*index
) != SSA_NAME
)
859 stmt
= SSA_NAME_DEF_STMT (*index
);
860 if (IS_EMPTY_STMT (stmt
))
863 set_level (stmt
, fmt_data
->orig_loop
, fmt_data
->loop
);
868 /* Records memory reference *REF (that occurs in statement STMT)
869 to the list MEM_REFS. */
872 record_mem_ref (struct mem_ref
**mem_refs
, tree stmt
, tree
*ref
)
874 struct mem_ref
*aref
= xmalloc (sizeof (struct mem_ref
));
879 aref
->next
= *mem_refs
;
883 /* Releases list of memory references MEM_REFS. */
886 free_mem_refs (struct mem_ref
*mem_refs
)
893 mem_refs
= mem_refs
->next
;
898 /* If VAR is defined in LOOP and the statement it is defined in does not belong
899 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
903 maybe_queue_var (tree var
, struct loop
*loop
,
904 sbitmap seen
, tree
*queue
, unsigned *in_queue
)
906 tree stmt
= SSA_NAME_DEF_STMT (var
);
907 basic_block def_bb
= bb_for_stmt (stmt
);
910 || !flow_bb_inside_loop_p (loop
, def_bb
)
911 || TEST_BIT (seen
, get_stmt_uid (stmt
)))
914 SET_BIT (seen
, get_stmt_uid (stmt
));
915 queue
[(*in_queue
)++] = stmt
;
918 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
919 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
920 Record the reference OP to list MEM_REFS. STMT is the statement in that
921 the reference occurs. */
925 struct mem_ref
**mem_refs
;
931 fem_single_reachable_address (tree
*op
, void *data
)
933 struct sra_data
*sra_data
= data
;
935 if (sra_data
->common_ref
936 && !operand_equal_p (*op
, sra_data
->common_ref
, 0))
938 sra_data
->common_ref
= *op
;
940 record_mem_ref (sra_data
->mem_refs
, sra_data
->stmt
, op
);
944 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
945 is passed to the CALLBACK as well. The traversal stops if CALLBACK
946 returns false, for_each_memref then returns false as well. Otherwise
947 for_each_memref returns true. */
950 for_each_memref (tree stmt
, bool (*callback
)(tree
*, void *), void *data
)
954 if (TREE_CODE (stmt
) == RETURN_EXPR
)
955 stmt
= TREE_OPERAND (stmt
, 1);
957 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
959 op
= &TREE_OPERAND (stmt
, 0);
960 if (TREE_CODE (*op
) != SSA_NAME
961 && !callback (op
, data
))
964 op
= &TREE_OPERAND (stmt
, 1);
965 if (TREE_CODE (*op
) != SSA_NAME
966 && is_gimple_lvalue (*op
)
967 && !callback (op
, data
))
970 stmt
= TREE_OPERAND (stmt
, 1);
973 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
974 stmt
= TREE_OPERAND (stmt
, 0);
976 if (TREE_CODE (stmt
) == CALL_EXPR
)
980 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
982 op
= &TREE_VALUE (args
);
984 if (TREE_CODE (*op
) != SSA_NAME
985 && is_gimple_lvalue (*op
)
986 && !callback (op
, data
))
994 /* Determine whether all memory references inside the LOOP that correspond
995 to virtual ssa names defined in statement STMT are equal.
996 If so, store the list of the references to MEM_REFS, and return one
997 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
998 *SEEN_CALL_STMT is set to true if the virtual operands suggest
999 that the reference might be clobbered by a call inside the LOOP. */
1002 single_reachable_address (struct loop
*loop
, tree stmt
,
1003 struct mem_ref
**mem_refs
,
1004 bool *seen_call_stmt
)
1006 unsigned max_uid
= max_stmt_uid
+ num_ssa_names
;
1007 tree
*queue
= xmalloc (sizeof (tree
) * max_uid
);
1008 sbitmap seen
= sbitmap_alloc (max_uid
);
1009 unsigned in_queue
= 1;
1011 struct sra_data sra_data
;
1015 imm_use_iterator imm_iter
;
1016 use_operand_p use_p
;
1018 sbitmap_zero (seen
);
1021 sra_data
.mem_refs
= mem_refs
;
1022 sra_data
.common_ref
= NULL_TREE
;
1025 SET_BIT (seen
, get_stmt_uid (stmt
));
1026 *seen_call_stmt
= false;
1030 stmt
= queue
[--in_queue
];
1031 sra_data
.stmt
= stmt
;
1034 && LIM_DATA (stmt
)->sm_done
)
1037 switch (TREE_CODE (stmt
))
1042 if (!for_each_memref (stmt
, fem_single_reachable_address
,
1046 /* If this is a function that may depend on the memory location,
1047 record the fact. We cannot directly refuse call clobbered
1048 operands here, since sra_data.common_ref did not have
1050 call
= get_call_expr_in (stmt
);
1052 && !(call_expr_flags (call
) & ECF_CONST
))
1053 *seen_call_stmt
= true;
1055 /* Traverse also definitions of the VUSES (there may be other
1056 distinct from the one we used to get to this statement). */
1057 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1058 maybe_queue_var (val
, loop
, seen
, queue
, &in_queue
);
1063 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (stmt
); i
++)
1064 if (TREE_CODE (PHI_ARG_DEF (stmt
, i
)) == SSA_NAME
)
1065 maybe_queue_var (PHI_ARG_DEF (stmt
, i
), loop
,
1066 seen
, queue
, &in_queue
);
1073 /* Find uses of virtual names. */
1074 if (TREE_CODE (stmt
) == PHI_NODE
)
1076 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (stmt
))))
1077 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, PHI_RESULT (stmt
))
1079 tree imm_stmt
= USE_STMT (use_p
);
1081 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1084 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1087 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1089 queue
[in_queue
++] = imm_stmt
;
1093 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
1094 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
1096 tree imm_stmt
= USE_STMT (use_p
);
1098 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1101 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1104 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1106 queue
[in_queue
++] = imm_stmt
;
1111 sbitmap_free (seen
);
1113 return sra_data
.common_ref
;
1116 free_mem_refs (*mem_refs
);
1119 sbitmap_free (seen
);
1124 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1127 rewrite_mem_refs (tree tmp_var
, struct mem_ref
*mem_refs
)
1132 for (; mem_refs
; mem_refs
= mem_refs
->next
)
1134 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1135 mark_sym_for_renaming (SSA_NAME_VAR (var
));
1137 *mem_refs
->ref
= tmp_var
;
1138 update_stmt (mem_refs
->stmt
);
1142 /* Records request for store motion of memory reference REF from LOOP.
1143 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1144 these references are rewritten by a new temporary variable.
1145 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1146 The initialization of the temporary variable is put to the preheader
1147 of the loop, and assignments to the reference from the temporary variable
1148 are emitted to exits. */
1151 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
1152 struct mem_ref
*mem_refs
)
1154 struct mem_ref
*aref
;
1158 struct fmt_data fmt_data
;
1160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1162 fprintf (dump_file
, "Executing store motion of ");
1163 print_generic_expr (dump_file
, ref
, 0);
1164 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1167 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
1169 fmt_data
.loop
= loop
;
1170 fmt_data
.orig_loop
= loop
;
1171 for_each_index (&ref
, force_move_till
, &fmt_data
);
1173 rewrite_mem_refs (tmp_var
, mem_refs
);
1174 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1175 if (LIM_DATA (aref
->stmt
))
1176 LIM_DATA (aref
->stmt
)->sm_done
= true;
1178 /* Emit the load & stores. */
1179 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
1180 get_stmt_ann (load
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
1181 LIM_DATA (load
)->max_loop
= loop
;
1182 LIM_DATA (load
)->tgt_loop
= loop
;
1184 /* Put this into the latch, so that we are sure it will be processed after
1185 all dependencies. */
1186 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
1188 for (i
= 0; i
< n_exits
; i
++)
1190 store
= build (MODIFY_EXPR
, void_type_node
,
1191 unshare_expr (ref
), tmp_var
);
1192 bsi_insert_on_edge (exits
[i
], store
);
1196 /* Returns true if REF may be clobbered by calls. */
1199 is_call_clobbered_ref (tree ref
)
1202 HOST_WIDE_INT offset
, size
;
1207 if (TREE_CODE (sref
) == COMPONENT_REF
1208 && (sref
= okay_component_ref_for_subvars (sref
, &offset
, &size
)))
1210 svars
= get_subvars_for_var (sref
);
1211 for (sv
= svars
; sv
; sv
= sv
->next
)
1213 if (overlap_subvar (offset
, size
, sv
, NULL
)
1214 && is_call_clobbered (sv
->var
))
1219 base
= get_base_address (ref
);
1225 if (var_can_have_subvars (base
)
1226 && (svars
= get_subvars_for_var (base
)))
1228 for (sv
= svars
; sv
; sv
= sv
->next
)
1229 if (is_call_clobbered (sv
->var
))
1234 return is_call_clobbered (base
);
1237 if (INDIRECT_REF_P (base
))
1239 /* Check whether the alias tags associated with the pointer
1240 are call clobbered. */
1241 tree ptr
= TREE_OPERAND (base
, 0);
1242 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1243 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
1244 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
1246 if ((nmt
&& is_call_clobbered (nmt
))
1247 || (tmt
&& is_call_clobbered (tmt
)))
1256 /* Determine whether all memory references inside LOOP corresponding to the
1257 virtual ssa name REG are equal to each other, and whether the address of
1258 this common reference can be hoisted outside of the loop. If this is true,
1259 prepare the statements that load the value of the memory reference to a
1260 temporary variable in the loop preheader, store it back on the loop exits,
1261 and replace all the references inside LOOP by this temporary variable.
1262 LOOP has N_EXITS stored in EXITS. */
1265 determine_lsm_reg (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree reg
)
1268 struct mem_ref
*mem_refs
, *aref
;
1269 struct loop
*must_exec
;
1272 if (is_gimple_reg (reg
))
1275 ref
= single_reachable_address (loop
, SSA_NAME_DEF_STMT (reg
), &mem_refs
,
1280 /* If we cannot create a ssa name for the result, give up. */
1281 if (!is_gimple_reg_type (TREE_TYPE (ref
))
1282 || TREE_THIS_VOLATILE (ref
))
1285 /* If there is a call that may use the location, give up as well. */
1287 && is_call_clobbered_ref (ref
))
1290 if (!for_each_index (&ref
, may_move_till
, loop
))
1293 if (tree_could_trap_p (ref
))
1295 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1296 of the statements in that it occurs is always executed when the loop
1297 is entered. This way we know that by moving the load from the
1298 reference out of the loop we will not cause the error that would not
1301 TODO -- in fact we would like to check for anticipability of the
1302 reference, i.e. that on each path from loop entry to loop exit at
1303 least one of the statements containing the memory reference is
1306 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1308 if (!LIM_DATA (aref
->stmt
))
1311 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1315 if (must_exec
== loop
1316 || flow_loop_nested_p (must_exec
, loop
))
1324 schedule_sm (loop
, exits
, n_exits
, ref
, mem_refs
);
1327 free_mem_refs (mem_refs
);
1330 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1331 for a store motion optimization (i.e. whether we can insert statement
1335 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1340 for (i
= 0; i
< n_exits
; i
++)
1341 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1347 /* Try to perform store motion for all memory references modified inside
1351 determine_lsm_loop (struct loop
*loop
)
1355 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1357 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1363 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
1364 determine_lsm_reg (loop
, exits
, n_exits
, PHI_RESULT (phi
));
1369 /* Try to perform store motion for all memory references modified inside
1373 determine_lsm (struct loops
*loops
)
1378 if (!loops
->tree_root
->inner
)
1381 /* Create a UID for each statement in the function. Ordering of the
1382 UIDs is not important for this pass. */
1386 block_stmt_iterator bsi
;
1388 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1389 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
1392 /* Pass the loops from the outermost. For each virtual operand loop phi node
1393 check whether all the references inside the loop correspond to a single
1394 address, and if so, move them. */
1396 loop
= loops
->tree_root
->inner
;
1399 determine_lsm_loop (loop
);
1409 if (loop
== loops
->tree_root
)
1411 loop_commit_inserts ();
1419 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1420 for each such basic block bb records the outermost loop for that execution
1421 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1422 blocks that contain a nonpure call. */
1425 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1427 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1430 struct loop
*inn_loop
= loop
;
1432 if (!loop
->header
->aux
)
1434 bbs
= get_loop_body_in_dom_order (loop
);
1436 for (i
= 0; i
< loop
->num_nodes
; i
++)
1441 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1444 if (TEST_BIT (contains_call
, bb
->index
))
1447 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1448 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1453 /* A loop might be infinite (TODO use simple loop analysis
1454 to disprove this if possible). */
1455 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1458 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1461 if (bb
->loop_father
->header
== bb
)
1463 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1466 /* In a loop that is always entered we may proceed anyway.
1467 But record that we entered it and stop once we leave it. */
1468 inn_loop
= bb
->loop_father
;
1475 if (last
== loop
->header
)
1477 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1483 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1484 fill_always_executed_in (loop
, contains_call
);
1487 /* Compute the global information needed by the loop invariant motion pass.
1488 LOOPS is the loop tree. */
1491 tree_ssa_lim_initialize (struct loops
*loops
)
1493 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1494 block_stmt_iterator bsi
;
1498 sbitmap_zero (contains_call
);
1501 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1503 if (nonpure_call_p (bsi_stmt (bsi
)))
1507 if (!bsi_end_p (bsi
))
1508 SET_BIT (contains_call
, bb
->index
);
1511 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1512 fill_always_executed_in (loop
, contains_call
);
1514 sbitmap_free (contains_call
);
1517 /* Cleans up after the invariant motion pass. */
1520 tree_ssa_lim_finalize (void)
1530 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1531 i.e. those that are likely to be win regardless of the register pressure. */
1534 tree_ssa_lim (struct loops
*loops
)
1536 tree_ssa_lim_initialize (loops
);
1538 /* For each statement determine the outermost loop in that it is
1539 invariant and cost for computing the invariant. */
1540 determine_invariantness ();
1542 /* For each memory reference determine whether it is possible to hoist it
1543 out of the loop. Force the necessary invariants to be moved out of the
1545 determine_lsm (loops
);
1547 /* Move the expressions that are expensive enough. */
1548 move_computations ();
1550 tree_ssa_lim_finalize ();