1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004 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 /* A type for the list of statements that have to be moved in order to be able
42 to hoist an invariant computation. */
50 /* The auxiliary data kept for each statement. */
54 struct loop
*max_loop
; /* The outermost loop in that the statement
57 struct loop
*tgt_loop
; /* The loop out of that we want to move the
60 struct loop
*always_executed_in
;
61 /* The outermost loop for that we are sure
62 the statement is executed if the loop
65 bool sm_done
; /* True iff the store motion for a memory
66 reference in the statement has already
69 unsigned cost
; /* Cost of the computation performed by the
72 struct depend
*depends
; /* List of statements that must be also hoisted
73 out of the loop when this statement is
74 hoisted; i.e. those that define the operands
75 of the statement and are inside of the
79 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
81 : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
83 /* Description of a memory reference for store motion. */
87 tree
*ref
; /* The reference itself. */
88 tree stmt
; /* The statement in that it occurs. */
89 struct mem_ref
*next
; /* Next use in the chain. */
92 /* Minimum cost of an expensive expression. */
93 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
95 /* The outermost loop for that execution of the header guarantees that the
96 block will be executed. */
97 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
99 static unsigned max_stmt_uid
; /* Maximal uid of a statement. Uids to phi
100 nodes are assigned using the versions of
101 ssa names they define. */
103 /* Returns uid of statement STMT. */
106 get_stmt_uid (tree stmt
)
108 if (TREE_CODE (stmt
) == PHI_NODE
)
109 return SSA_NAME_VERSION (PHI_RESULT (stmt
)) + max_stmt_uid
;
111 return stmt_ann (stmt
)->uid
;
114 /* Calls CBCK for each index in memory reference ADDR_P. There are two
115 kinds situations handled; in each of these cases, the memory reference
116 and DATA are passed to the callback:
118 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
119 pass the pointer to the index to the callback.
121 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
122 pointer to addr to the callback.
124 If the callback returns false, the whole search stops and false is returned.
125 Otherwise the function returns true after traversing through the whole
126 reference *ADDR_P. */
129 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
133 for (; ; addr_p
= nxt
)
135 switch (TREE_CODE (*addr_p
))
138 return cbck (*addr_p
, addr_p
, data
);
140 case MISALIGNED_INDIRECT_REF
:
141 case ALIGN_INDIRECT_REF
:
143 nxt
= &TREE_OPERAND (*addr_p
, 0);
144 return cbck (*addr_p
, nxt
, data
);
148 case VIEW_CONVERT_EXPR
:
149 case ARRAY_RANGE_REF
:
152 nxt
= &TREE_OPERAND (*addr_p
, 0);
156 nxt
= &TREE_OPERAND (*addr_p
, 0);
157 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
173 /* If it is possible to hoist the statement STMT unconditionally,
174 returns MOVE_POSSIBLE.
175 If it is possible to hoist the statement STMT, but we must avoid making
176 it executed if it would not be executed in the original program (e.g.
177 because it may trap), return MOVE_PRESERVE_EXECUTION.
178 Otherwise return MOVE_IMPOSSIBLE. */
181 movement_possibility (tree stmt
)
185 if (flag_unswitch_loops
186 && TREE_CODE (stmt
) == COND_EXPR
)
188 /* If we perform unswitching, force the operands of the invariant
189 condition to be moved out of the loop. */
190 get_stmt_operands (stmt
);
192 return MOVE_POSSIBLE
;
195 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
196 return MOVE_IMPOSSIBLE
;
198 if (stmt_ends_bb_p (stmt
))
199 return MOVE_IMPOSSIBLE
;
201 get_stmt_operands (stmt
);
203 if (stmt_ann (stmt
)->has_volatile_ops
)
204 return MOVE_IMPOSSIBLE
;
206 lhs
= TREE_OPERAND (stmt
, 0);
207 if (TREE_CODE (lhs
) == SSA_NAME
208 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
209 return MOVE_IMPOSSIBLE
;
211 rhs
= TREE_OPERAND (stmt
, 1);
213 if (TREE_SIDE_EFFECTS (rhs
))
214 return MOVE_IMPOSSIBLE
;
216 if (TREE_CODE (lhs
) != SSA_NAME
217 || tree_could_trap_p (rhs
))
218 return MOVE_PRESERVE_EXECUTION
;
220 return MOVE_POSSIBLE
;
223 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
224 loop to that we could move the expression using DEF if it did not have
225 other operands, i.e. the outermost loop enclosing LOOP in that the value
226 of DEF is invariant. */
229 outermost_invariant_loop (tree def
, struct loop
*loop
)
233 struct loop
*max_loop
;
235 if (TREE_CODE (def
) != SSA_NAME
)
236 return superloop_at_depth (loop
, 1);
238 def_stmt
= SSA_NAME_DEF_STMT (def
);
239 def_bb
= bb_for_stmt (def_stmt
);
241 return superloop_at_depth (loop
, 1);
243 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
245 if (LIM_DATA (def_stmt
) && LIM_DATA (def_stmt
)->max_loop
)
246 max_loop
= find_common_loop (max_loop
,
247 LIM_DATA (def_stmt
)->max_loop
->outer
);
248 if (max_loop
== loop
)
250 max_loop
= superloop_at_depth (loop
, max_loop
->depth
+ 1);
255 /* Returns the outermost superloop of LOOP in that the expression EXPR is
259 outermost_invariant_loop_expr (tree expr
, struct loop
*loop
)
261 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
263 struct loop
*max_loop
= superloop_at_depth (loop
, 1), *aloop
;
265 if (TREE_CODE (expr
) == SSA_NAME
266 || TREE_CODE (expr
) == INTEGER_CST
267 || is_gimple_min_invariant (expr
))
268 return outermost_invariant_loop (expr
, loop
);
270 if (class != tcc_unary
271 && class != tcc_binary
272 && class != tcc_expression
273 && class != tcc_comparison
)
276 nops
= first_rtl_op (TREE_CODE (expr
));
277 for (i
= 0; i
< nops
; i
++)
279 aloop
= outermost_invariant_loop_expr (TREE_OPERAND (expr
, i
), loop
);
283 if (flow_loop_nested_p (max_loop
, aloop
))
290 /* DATA is a structure containing information associated with a statement
291 inside LOOP. DEF is one of the operands of this statement.
293 Find the outermost loop enclosing LOOP in that value of DEF is invariant
294 and record this in DATA->max_loop field. If DEF itself is defined inside
295 this loop as well (i.e. we need to hoist it out of the loop if we want
296 to hoist the statement represented by DATA), record the statement in that
297 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
298 add the cost of the computation of DEF to the DATA->cost.
300 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
303 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
306 tree def_stmt
= SSA_NAME_DEF_STMT (def
);
307 basic_block def_bb
= bb_for_stmt (def_stmt
);
308 struct loop
*max_loop
;
314 max_loop
= outermost_invariant_loop (def
, loop
);
318 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
319 data
->max_loop
= max_loop
;
321 if (!LIM_DATA (def_stmt
))
325 /* Only add the cost if the statement defining DEF is inside LOOP,
326 i.e. if it is likely that by moving the invariants dependent
327 on it, we will be able to avoid creating a new register for
328 it (since it will be only used in these dependent invariants). */
329 && def_bb
->loop_father
== loop
)
330 data
->cost
+= LIM_DATA (def_stmt
)->cost
;
332 dep
= xmalloc (sizeof (struct depend
));
333 dep
->stmt
= def_stmt
;
334 dep
->next
= data
->depends
;
340 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
341 are just ad-hoc constants. The estimates should be based on target-specific
345 stmt_cost (tree stmt
)
350 /* Always try to create possibilities for unswitching. */
351 if (TREE_CODE (stmt
) == COND_EXPR
)
352 return LIM_EXPENSIVE
;
354 lhs
= TREE_OPERAND (stmt
, 0);
355 rhs
= TREE_OPERAND (stmt
, 1);
357 /* Hoisting memory references out should almost surely be a win. */
358 if (!is_gimple_variable (lhs
))
360 if (is_gimple_addressable (rhs
) && !is_gimple_variable (rhs
))
363 switch (TREE_CODE (rhs
))
366 /* We should be hoisting calls if possible. */
368 /* Unless the call is a builtin_constant_p; this always folds to a
369 constant, so moving it is useless. */
370 rhs
= get_callee_fndecl (rhs
);
371 if (DECL_BUILT_IN (rhs
)
372 && DECL_FUNCTION_CODE (rhs
) == BUILT_IN_CONSTANT_P
)
388 /* Division and multiplication are usually expensive. */
399 /* Determine the outermost loop to that it is possible to hoist a statement
400 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
401 the outermost loop in that the value computed by STMT is invariant.
402 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
403 we preserve the fact whether STMT is executed. It also fills other related
404 information to LIM_DATA (STMT).
406 The function returns false if STMT cannot be hoisted outside of the loop it
407 is defined in, and true otherwise. */
410 determine_max_movement (tree stmt
, bool must_preserve_exec
)
412 basic_block bb
= bb_for_stmt (stmt
);
413 struct loop
*loop
= bb
->loop_father
;
415 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
419 if (must_preserve_exec
)
420 level
= ALWAYS_EXECUTED_IN (bb
);
422 level
= superloop_at_depth (loop
, 1);
423 lim_data
->max_loop
= level
;
425 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
426 if (!add_dependency (val
, lim_data
, loop
, true))
429 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
430 if (!add_dependency (val
, lim_data
, loop
, false))
433 lim_data
->cost
+= stmt_cost (stmt
);
438 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
439 and that one of the operands of this statement is computed by STMT.
440 Ensure that STMT (together with all the statements that define its
441 operands) is hoisted at least out of the loop LEVEL. */
444 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
446 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
449 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
450 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
451 stmt_loop
= find_common_loop (stmt_loop
,
452 LIM_DATA (stmt
)->tgt_loop
->outer
);
453 if (flow_loop_nested_p (stmt_loop
, level
))
456 gcc_assert (LIM_DATA (stmt
));
457 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
458 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
460 LIM_DATA (stmt
)->tgt_loop
= level
;
461 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
462 set_level (dep
->stmt
, orig_loop
, level
);
465 /* Determines an outermost loop from that we want to hoist the statement STMT.
466 For now we chose the outermost possible loop. TODO -- use profiling
467 information to set it more sanely. */
470 set_profitable_level (tree stmt
)
472 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
475 /* Returns true if STMT is not a pure call. */
478 nonpure_call_p (tree stmt
)
480 tree call
= get_call_expr_in (stmt
);
485 return TREE_SIDE_EFFECTS (call
) != 0;
488 /* Releases the memory occupied by DATA. */
491 free_lim_aux_data (struct lim_aux_data
*data
)
493 struct depend
*dep
, *next
;
495 for (dep
= data
->depends
; dep
; dep
= next
)
503 /* Determine the outermost loops in that statements in basic block BB are
504 invariant, and record them to the LIM_DATA associated with the statements.
505 Callback for walk_dominator_tree. */
508 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
512 block_stmt_iterator bsi
;
514 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
515 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
517 if (!bb
->loop_father
->outer
)
520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
521 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
522 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
524 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
526 stmt
= bsi_stmt (bsi
);
528 pos
= movement_possibility (stmt
);
529 if (pos
== MOVE_IMPOSSIBLE
)
531 if (nonpure_call_p (stmt
))
539 stmt_ann (stmt
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
540 LIM_DATA (stmt
)->always_executed_in
= outermost
;
542 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
545 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
547 LIM_DATA (stmt
)->max_loop
= NULL
;
551 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
553 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
554 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
555 LIM_DATA (stmt
)->max_loop
->depth
,
556 LIM_DATA (stmt
)->cost
);
559 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
560 set_profitable_level (stmt
);
564 /* For each statement determines the outermost loop in that it is invariant,
565 statements on whose motion it depends and the cost of the computation.
566 This information is stored to the LIM_DATA structure associated with
570 determine_invariantness (void)
572 struct dom_walk_data walk_data
;
574 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
575 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
577 init_walk_dominator_tree (&walk_data
);
578 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
579 fini_walk_dominator_tree (&walk_data
);
582 /* Commits edge insertions and updates loop structures. */
585 loop_commit_inserts (void)
587 unsigned old_last_basic_block
, i
;
590 old_last_basic_block
= last_basic_block
;
591 bsi_commit_edge_inserts (NULL
);
592 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
594 bb
= BASIC_BLOCK (i
);
596 find_common_loop (bb
->succ
->dest
->loop_father
,
597 bb
->pred
->src
->loop_father
));
601 /* Hoist the statements in basic block BB out of the loops prescribed by
602 data stored in LIM_DATA structures associated with each statement. Callback
603 for walk_dominator_tree. */
606 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
610 block_stmt_iterator bsi
;
614 if (!bb
->loop_father
->outer
)
617 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
619 stmt
= bsi_stmt (bsi
);
621 if (!LIM_DATA (stmt
))
627 cost
= LIM_DATA (stmt
)->cost
;
628 level
= LIM_DATA (stmt
)->tgt_loop
;
629 free_lim_aux_data (LIM_DATA (stmt
));
630 stmt_ann (stmt
)->common
.aux
= NULL
;
638 /* We do not really want to move conditionals out of the loop; we just
639 placed it here to force its operands to be moved if necessary. */
640 if (TREE_CODE (stmt
) == COND_EXPR
)
643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
645 fprintf (dump_file
, "Moving statement\n");
646 print_generic_stmt (dump_file
, stmt
, 0);
647 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
650 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
655 /* Hoist the statements out of the loops prescribed by data stored in
656 LIM_DATA structures associated with each statement.*/
659 move_computations (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
= move_computations_stmt
;
666 init_walk_dominator_tree (&walk_data
);
667 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
668 fini_walk_dominator_tree (&walk_data
);
670 loop_commit_inserts ();
671 rewrite_into_ssa (false);
672 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
674 /* The rewrite of ssa names may cause violation of loop closed ssa
675 form invariants. TODO -- avoid these rewrites completely.
676 Information in virtual phi nodes is sufficient for it. */
677 rewrite_into_loop_closed_ssa ();
679 bitmap_clear (vars_to_rename
);
682 /* Checks whether the statement defining variable *INDEX can be hoisted
683 out of the loop passed in DATA. Callback for for_each_index. */
686 may_move_till (tree ref
, tree
*index
, void *data
)
688 struct loop
*loop
= data
, *max_loop
;
690 /* If REF is an array reference, check also that the step and the lower
691 bound is invariant in LOOP. */
692 if (TREE_CODE (ref
) == ARRAY_REF
)
694 tree step
= array_ref_element_size (ref
);
695 tree lbound
= array_ref_low_bound (ref
);
697 max_loop
= outermost_invariant_loop_expr (step
, loop
);
701 max_loop
= outermost_invariant_loop_expr (lbound
, loop
);
706 max_loop
= outermost_invariant_loop (*index
, loop
);
713 /* Forces statements defining (invariant) SSA names in expression EXPR to be
714 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
717 force_move_till_expr (tree expr
, struct loop
*orig_loop
, struct loop
*loop
)
719 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
722 if (TREE_CODE (expr
) == SSA_NAME
)
724 tree stmt
= SSA_NAME_DEF_STMT (expr
);
725 if (IS_EMPTY_STMT (stmt
))
728 set_level (stmt
, orig_loop
, loop
);
732 if (class != tcc_unary
733 && class != tcc_binary
734 && class != tcc_expression
735 && class != tcc_comparison
)
738 nops
= first_rtl_op (TREE_CODE (expr
));
739 for (i
= 0; i
< nops
; i
++)
740 force_move_till_expr (TREE_OPERAND (expr
, i
), orig_loop
, loop
);
743 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
744 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
750 struct loop
*orig_loop
;
754 force_move_till (tree ref
, tree
*index
, void *data
)
757 struct fmt_data
*fmt_data
= data
;
759 if (TREE_CODE (ref
) == ARRAY_REF
)
761 tree step
= array_ref_element_size (ref
);
762 tree lbound
= array_ref_low_bound (ref
);
764 force_move_till_expr (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
765 force_move_till_expr (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
768 if (TREE_CODE (*index
) != SSA_NAME
)
771 stmt
= SSA_NAME_DEF_STMT (*index
);
772 if (IS_EMPTY_STMT (stmt
))
775 set_level (stmt
, fmt_data
->orig_loop
, fmt_data
->loop
);
780 /* Records memory reference *REF (that occurs in statement STMT)
781 to the list MEM_REFS. */
784 record_mem_ref (struct mem_ref
**mem_refs
, tree stmt
, tree
*ref
)
786 struct mem_ref
*aref
= xmalloc (sizeof (struct mem_ref
));
791 aref
->next
= *mem_refs
;
795 /* Releases list of memory references MEM_REFS. */
798 free_mem_refs (struct mem_ref
*mem_refs
)
805 mem_refs
= mem_refs
->next
;
810 /* If VAR is defined in LOOP and the statement it is defined in does not belong
811 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
815 maybe_queue_var (tree var
, struct loop
*loop
,
816 sbitmap seen
, tree
*queue
, unsigned *in_queue
)
818 tree stmt
= SSA_NAME_DEF_STMT (var
);
819 basic_block def_bb
= bb_for_stmt (stmt
);
822 || !flow_bb_inside_loop_p (loop
, def_bb
)
823 || TEST_BIT (seen
, get_stmt_uid (stmt
)))
826 SET_BIT (seen
, get_stmt_uid (stmt
));
827 queue
[(*in_queue
)++] = stmt
;
830 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
831 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
832 Record the reference OP to list MEM_REFS. STMT is the statement in that
833 the reference occurs. */
837 struct mem_ref
**mem_refs
;
843 fem_single_reachable_address (tree
*op
, void *data
)
845 struct sra_data
*sra_data
= data
;
847 if (sra_data
->common_ref
848 && !operand_equal_p (*op
, sra_data
->common_ref
, 0))
850 sra_data
->common_ref
= *op
;
852 record_mem_ref (sra_data
->mem_refs
, sra_data
->stmt
, op
);
856 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
857 is passed to the CALLBACK as well. The traversal stops if CALLBACK
858 returns false, for_each_memref then returns false as well. Otherwise
859 for_each_memref returns true. */
862 for_each_memref (tree stmt
, bool (*callback
)(tree
*, void *), void *data
)
866 if (TREE_CODE (stmt
) == RETURN_EXPR
)
867 stmt
= TREE_OPERAND (stmt
, 1);
869 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
871 op
= &TREE_OPERAND (stmt
, 0);
872 if (TREE_CODE (*op
) != SSA_NAME
873 && !callback (op
, data
))
876 op
= &TREE_OPERAND (stmt
, 1);
877 if (TREE_CODE (*op
) != SSA_NAME
878 && is_gimple_lvalue (*op
)
879 && !callback (op
, data
))
882 stmt
= TREE_OPERAND (stmt
, 1);
885 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
886 stmt
= TREE_OPERAND (stmt
, 0);
888 if (TREE_CODE (stmt
) == CALL_EXPR
)
892 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
894 op
= &TREE_VALUE (args
);
896 if (TREE_CODE (*op
) != SSA_NAME
897 && is_gimple_lvalue (*op
)
898 && !callback (op
, data
))
906 /* Determine whether all memory references inside the LOOP that correspond
907 to virtual ssa names defined in statement STMT are equal.
908 If so, store the list of the references to MEM_REFS, and return one
909 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
910 *SEEN_CALL_STMT is set to true if the virtual operands suggest
911 that the reference might be clobbered by a call inside the LOOP. */
914 single_reachable_address (struct loop
*loop
, tree stmt
,
915 struct mem_ref
**mem_refs
,
916 bool *seen_call_stmt
)
918 unsigned max_uid
= max_stmt_uid
+ num_ssa_names
;
919 tree
*queue
= xmalloc (sizeof (tree
) * max_uid
);
920 sbitmap seen
= sbitmap_alloc (max_uid
);
921 unsigned in_queue
= 1;
924 struct sra_data sra_data
;
932 sra_data
.mem_refs
= mem_refs
;
933 sra_data
.common_ref
= NULL_TREE
;
936 SET_BIT (seen
, get_stmt_uid (stmt
));
937 *seen_call_stmt
= false;
941 stmt
= queue
[--in_queue
];
942 sra_data
.stmt
= stmt
;
945 && LIM_DATA (stmt
)->sm_done
)
948 switch (TREE_CODE (stmt
))
953 if (!for_each_memref (stmt
, fem_single_reachable_address
,
957 /* If this is a function that may depend on the memory location,
958 record the fact. We cannot directly refuse call clobbered
959 operands here, since sra_data.common_ref did not have
961 call
= get_call_expr_in (stmt
);
963 && !(call_expr_flags (call
) & ECF_CONST
))
964 *seen_call_stmt
= true;
966 /* Traverse also definitions of the VUSES (there may be other
967 distinct from the one we used to get to this statement). */
968 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
969 maybe_queue_var (val
, loop
, seen
, queue
, &in_queue
);
974 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (stmt
); i
++)
975 maybe_queue_var (PHI_ARG_DEF (stmt
, i
), loop
,
976 seen
, queue
, &in_queue
);
983 /* Find uses of virtual names. */
984 df
= get_immediate_uses (stmt
);
985 n
= num_immediate_uses (df
);
987 for (i
= 0; i
< n
; i
++)
989 stmt
= immediate_use (df
, i
);
991 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (stmt
)))
994 if (TEST_BIT (seen
, get_stmt_uid (stmt
)))
996 SET_BIT (seen
, get_stmt_uid (stmt
));
998 queue
[in_queue
++] = stmt
;
1003 sbitmap_free (seen
);
1005 return sra_data
.common_ref
;
1008 free_mem_refs (*mem_refs
);
1011 sbitmap_free (seen
);
1016 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1019 rewrite_mem_refs (tree tmp_var
, struct mem_ref
*mem_refs
)
1024 for (; mem_refs
; mem_refs
= mem_refs
->next
)
1026 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
,
1027 (SSA_OP_VIRTUAL_DEFS
| SSA_OP_VUSE
))
1029 var
= SSA_NAME_VAR (var
);
1030 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1033 *mem_refs
->ref
= tmp_var
;
1034 modify_stmt (mem_refs
->stmt
);
1038 /* Records request for store motion of memory reference REF from LOOP.
1039 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1040 these references are rewritten by a new temporary variable.
1041 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1042 The initialization of the temporary variable is put to the preheader
1043 of the loop, and assignments to the reference from the temporary variable
1044 are emitted to exits. */
1047 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
1048 struct mem_ref
*mem_refs
)
1050 struct mem_ref
*aref
;
1054 struct fmt_data fmt_data
;
1056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1058 fprintf (dump_file
, "Executing store motion of ");
1059 print_generic_expr (dump_file
, ref
, 0);
1060 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1063 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
1065 fmt_data
.loop
= loop
;
1066 fmt_data
.orig_loop
= loop
;
1067 for_each_index (&ref
, force_move_till
, &fmt_data
);
1069 rewrite_mem_refs (tmp_var
, mem_refs
);
1070 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1071 if (LIM_DATA (aref
->stmt
))
1072 LIM_DATA (aref
->stmt
)->sm_done
= true;
1074 /* Emit the load & stores. */
1075 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
1076 get_stmt_ann (load
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
1077 LIM_DATA (load
)->max_loop
= loop
;
1078 LIM_DATA (load
)->tgt_loop
= loop
;
1080 /* Put this into the latch, so that we are sure it will be processed after
1081 all dependencies. */
1082 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
1084 for (i
= 0; i
< n_exits
; i
++)
1086 store
= build (MODIFY_EXPR
, void_type_node
,
1087 unshare_expr (ref
), tmp_var
);
1088 bsi_insert_on_edge (exits
[i
], store
);
1092 /* Returns true if REF may be clobbered by calls. */
1095 is_call_clobbered_ref (tree ref
)
1099 base
= get_base_address (ref
);
1104 return is_call_clobbered (base
);
1106 if (TREE_CODE (base
) == INDIRECT_REF
1107 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
1108 || TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
)
1110 /* Check whether the alias tags associated with the pointer
1111 are call clobbered. */
1112 tree ptr
= TREE_OPERAND (base
, 0);
1113 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1114 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
1115 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
1117 if ((nmt
&& is_call_clobbered (nmt
))
1118 || (tmt
&& is_call_clobbered (tmt
)))
1127 /* Determine whether all memory references inside LOOP corresponding to the
1128 virtual ssa name REG are equal to each other, and whether the address of
1129 this common reference can be hoisted outside of the loop. If this is true,
1130 prepare the statements that load the value of the memory reference to a
1131 temporary variable in the loop preheader, store it back on the loop exits,
1132 and replace all the references inside LOOP by this temporary variable.
1133 LOOP has N_EXITS stored in EXITS. */
1136 determine_lsm_reg (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree reg
)
1139 struct mem_ref
*mem_refs
, *aref
;
1140 struct loop
*must_exec
;
1143 if (is_gimple_reg (reg
))
1146 ref
= single_reachable_address (loop
, SSA_NAME_DEF_STMT (reg
), &mem_refs
,
1151 /* If we cannot create a ssa name for the result, give up. */
1152 if (!is_gimple_reg_type (TREE_TYPE (ref
))
1153 || TREE_THIS_VOLATILE (ref
))
1156 /* If there is a call that may use the location, give up as well. */
1158 && is_call_clobbered_ref (ref
))
1161 if (!for_each_index (&ref
, may_move_till
, loop
))
1164 if (tree_could_trap_p (ref
))
1166 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1167 of the statements in that it occurs is always executed when the loop
1168 is entered. This way we know that by moving the load from the
1169 reference out of the loop we will not cause the error that would not
1172 TODO -- in fact we would like to check for anticipability of the
1173 reference, i.e. that on each path from loop entry to loop exit at
1174 least one of the statements containing the memory reference is
1177 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1179 if (!LIM_DATA (aref
->stmt
))
1182 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1186 if (must_exec
== loop
1187 || flow_loop_nested_p (must_exec
, loop
))
1195 schedule_sm (loop
, exits
, n_exits
, ref
, mem_refs
);
1198 free_mem_refs (mem_refs
);
1201 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1202 for a store motion optimization (i.e. whether we can insert statement
1206 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1211 for (i
= 0; i
< n_exits
; i
++)
1212 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1218 /* Try to perform store motion for all memory references modified inside
1222 determine_lsm_loop (struct loop
*loop
)
1226 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1228 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1234 for (phi
= phi_nodes (loop
->header
); phi
; phi
= TREE_CHAIN (phi
))
1235 determine_lsm_reg (loop
, exits
, n_exits
, PHI_RESULT (phi
));
1240 /* Try to perform store motion for all memory references modified inside
1244 determine_lsm (struct loops
*loops
)
1249 /* Create a UID for each statement in the function. Ordering of the
1250 UIDs is not important for this pass. */
1254 block_stmt_iterator bsi
;
1256 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1257 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
1260 compute_immediate_uses (TDFA_USE_VOPS
, NULL
);
1262 /* Pass the loops from the outermost. For each virtual operand loop phi node
1263 check whether all the references inside the loop correspond to a single
1264 address, and if so, move them. */
1266 loop
= loops
->tree_root
->inner
;
1269 determine_lsm_loop (loop
);
1279 if (loop
== loops
->tree_root
)
1282 loop_commit_inserts ();
1290 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1291 for each such basic block bb records the outermost loop for that execution
1292 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1293 blocks that contain a nonpure call. */
1296 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1298 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1301 struct loop
*inn_loop
= loop
;
1303 if (!loop
->header
->aux
)
1305 bbs
= get_loop_body_in_dom_order (loop
);
1307 for (i
= 0; i
< loop
->num_nodes
; i
++)
1311 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1314 if (TEST_BIT (contains_call
, bb
->index
))
1317 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1318 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1323 /* A loop might be infinite (TODO use simple loop analysis
1324 to disprove this if possible). */
1325 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1328 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1331 if (bb
->loop_father
->header
== bb
)
1333 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1336 /* In a loop that is always entered we may proceed anyway.
1337 But record that we entered it and stop once we leave it. */
1338 inn_loop
= bb
->loop_father
;
1345 if (last
== loop
->header
)
1347 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1353 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1354 fill_always_executed_in (loop
, contains_call
);
1357 /* Compute the global information needed by the loop invariant motion pass.
1358 LOOPS is the loop tree. */
1361 tree_ssa_lim_initialize (struct loops
*loops
)
1363 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1364 block_stmt_iterator bsi
;
1368 sbitmap_zero (contains_call
);
1371 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1373 if (nonpure_call_p (bsi_stmt (bsi
)))
1377 if (!bsi_end_p (bsi
))
1378 SET_BIT (contains_call
, bb
->index
);
1381 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1382 fill_always_executed_in (loop
, contains_call
);
1384 sbitmap_free (contains_call
);
1387 /* Cleans up after the invariant motion pass. */
1390 tree_ssa_lim_finalize (void)
1400 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1401 i.e. those that are likely to be win regardless of the register pressure. */
1404 tree_ssa_lim (struct loops
*loops
)
1406 tree_ssa_lim_initialize (loops
);
1408 /* For each statement determine the outermost loop in that it is
1409 invariant and cost for computing the invariant. */
1410 determine_invariantness ();
1412 /* For each memory reference determine whether it is possible to hoist it
1413 out of the loop. Force the necessary invariants to be moved out of the
1415 determine_lsm (loops
);
1417 /* Move the expressions that are expensive enough. */
1418 move_computations ();
1420 tree_ssa_lim_finalize ();