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"
43 /* TODO: Support for predicated code motion. I.e.
54 Where COND and INV are is invariants, but evaluating INV may trap or be
55 invalid from some other reason if !COND. This may be transformed to
65 /* A type for the list of statements that have to be moved in order to be able
66 to hoist an invariant computation. */
74 /* The auxiliary data kept for each statement. */
78 struct loop
*max_loop
; /* The outermost loop in that the statement
81 struct loop
*tgt_loop
; /* The loop out of that we want to move the
84 struct loop
*always_executed_in
;
85 /* The outermost loop for that we are sure
86 the statement is executed if the loop
89 bool sm_done
; /* True iff the store motion for a memory
90 reference in the statement has already
93 unsigned cost
; /* Cost of the computation performed by the
96 struct depend
*depends
; /* List of statements that must be also hoisted
97 out of the loop when this statement is
98 hoisted; i.e. those that define the operands
99 of the statement and are inside of the
103 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
105 : (struct lim_aux_data *) (stmt_ann (STMT)->aux))
107 /* Description of a memory reference location for store motion. */
111 tree
*ref
; /* The reference itself. */
112 tree stmt
; /* The statement in that it occurs. */
113 struct mem_ref_loc
*next
; /* Next use in the chain. */
116 /* Description of a memory reference for store motion. */
120 tree mem
; /* The memory itself. */
121 hashval_t hash
; /* Its hash value. */
122 bool is_stored
; /* True if there is a store to the location
124 struct mem_ref_loc
*locs
; /* The locations where it is found. */
125 bitmap vops
; /* Vops corresponding to this memory
129 /* Minimum cost of an expensive expression. */
130 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
132 /* The outermost loop for that execution of the header guarantees that the
133 block will be executed. */
134 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
136 /* Calls CBCK for each index in memory reference ADDR_P. There are two
137 kinds situations handled; in each of these cases, the memory reference
138 and DATA are passed to the callback:
140 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
141 pass the pointer to the index to the callback.
143 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
144 pointer to addr to the callback.
146 If the callback returns false, the whole search stops and false is returned.
147 Otherwise the function returns true after traversing through the whole
148 reference *ADDR_P. */
151 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
155 for (; ; addr_p
= nxt
)
157 switch (TREE_CODE (*addr_p
))
160 return cbck (*addr_p
, addr_p
, data
);
162 case MISALIGNED_INDIRECT_REF
:
163 case ALIGN_INDIRECT_REF
:
165 nxt
= &TREE_OPERAND (*addr_p
, 0);
166 return cbck (*addr_p
, nxt
, data
);
169 case VIEW_CONVERT_EXPR
:
170 case ARRAY_RANGE_REF
:
173 nxt
= &TREE_OPERAND (*addr_p
, 0);
177 /* If the component has varying offset, it behaves like index
179 idx
= &TREE_OPERAND (*addr_p
, 2);
181 && !cbck (*addr_p
, idx
, data
))
184 nxt
= &TREE_OPERAND (*addr_p
, 0);
188 nxt
= &TREE_OPERAND (*addr_p
, 0);
189 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
205 /* If it is possible to hoist the statement STMT unconditionally,
206 returns MOVE_POSSIBLE.
207 If it is possible to hoist the statement STMT, but we must avoid making
208 it executed if it would not be executed in the original program (e.g.
209 because it may trap), return MOVE_PRESERVE_EXECUTION.
210 Otherwise return MOVE_IMPOSSIBLE. */
213 movement_possibility (tree stmt
)
217 if (flag_unswitch_loops
218 && TREE_CODE (stmt
) == COND_EXPR
)
220 /* If we perform unswitching, force the operands of the invariant
221 condition to be moved out of the loop. */
222 return MOVE_POSSIBLE
;
225 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
226 return MOVE_IMPOSSIBLE
;
228 if (stmt_ends_bb_p (stmt
))
229 return MOVE_IMPOSSIBLE
;
231 if (stmt_ann (stmt
)->has_volatile_ops
)
232 return MOVE_IMPOSSIBLE
;
234 lhs
= TREE_OPERAND (stmt
, 0);
235 if (TREE_CODE (lhs
) == SSA_NAME
236 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
237 return MOVE_IMPOSSIBLE
;
239 rhs
= TREE_OPERAND (stmt
, 1);
241 if (TREE_SIDE_EFFECTS (rhs
))
242 return MOVE_IMPOSSIBLE
;
244 if (TREE_CODE (lhs
) != SSA_NAME
245 || tree_could_trap_p (rhs
))
246 return MOVE_PRESERVE_EXECUTION
;
248 if (get_call_expr_in (stmt
))
250 /* While pure or const call is guaranteed to have no side effects, we
251 cannot move it arbitrarily. Consider code like
253 char *s = something ();
263 Here the strlen call cannot be moved out of the loop, even though
264 s is invariant. In addition to possibly creating a call with
265 invalid arguments, moving out a function call that is not executed
266 may cause performance regressions in case the call is costly and
267 not executed at all. */
268 return MOVE_PRESERVE_EXECUTION
;
270 return MOVE_POSSIBLE
;
273 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
274 loop to that we could move the expression using DEF if it did not have
275 other operands, i.e. the outermost loop enclosing LOOP in that the value
276 of DEF is invariant. */
279 outermost_invariant_loop (tree def
, struct loop
*loop
)
283 struct loop
*max_loop
;
285 if (TREE_CODE (def
) != SSA_NAME
)
286 return superloop_at_depth (loop
, 1);
288 def_stmt
= SSA_NAME_DEF_STMT (def
);
289 def_bb
= bb_for_stmt (def_stmt
);
291 return superloop_at_depth (loop
, 1);
293 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
295 if (LIM_DATA (def_stmt
) && LIM_DATA (def_stmt
)->max_loop
)
296 max_loop
= find_common_loop (max_loop
,
297 LIM_DATA (def_stmt
)->max_loop
->outer
);
298 if (max_loop
== loop
)
300 max_loop
= superloop_at_depth (loop
, max_loop
->depth
+ 1);
305 /* Returns the outermost superloop of LOOP in that the expression EXPR is
309 outermost_invariant_loop_expr (tree expr
, struct loop
*loop
)
311 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
313 struct loop
*max_loop
= superloop_at_depth (loop
, 1), *aloop
;
315 if (TREE_CODE (expr
) == SSA_NAME
316 || TREE_CODE (expr
) == INTEGER_CST
317 || is_gimple_min_invariant (expr
))
318 return outermost_invariant_loop (expr
, loop
);
320 if (class != tcc_unary
321 && class != tcc_binary
322 && class != tcc_expression
323 && class != tcc_comparison
)
326 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
327 for (i
= 0; i
< nops
; i
++)
329 aloop
= outermost_invariant_loop_expr (TREE_OPERAND (expr
, i
), loop
);
333 if (flow_loop_nested_p (max_loop
, aloop
))
340 /* DATA is a structure containing information associated with a statement
341 inside LOOP. DEF is one of the operands of this statement.
343 Find the outermost loop enclosing LOOP in that value of DEF is invariant
344 and record this in DATA->max_loop field. If DEF itself is defined inside
345 this loop as well (i.e. we need to hoist it out of the loop if we want
346 to hoist the statement represented by DATA), record the statement in that
347 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
348 add the cost of the computation of DEF to the DATA->cost.
350 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
353 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
356 tree def_stmt
= SSA_NAME_DEF_STMT (def
);
357 basic_block def_bb
= bb_for_stmt (def_stmt
);
358 struct loop
*max_loop
;
364 max_loop
= outermost_invariant_loop (def
, loop
);
368 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
369 data
->max_loop
= max_loop
;
371 if (!LIM_DATA (def_stmt
))
375 /* Only add the cost if the statement defining DEF is inside LOOP,
376 i.e. if it is likely that by moving the invariants dependent
377 on it, we will be able to avoid creating a new register for
378 it (since it will be only used in these dependent invariants). */
379 && def_bb
->loop_father
== loop
)
380 data
->cost
+= LIM_DATA (def_stmt
)->cost
;
382 dep
= xmalloc (sizeof (struct depend
));
383 dep
->stmt
= def_stmt
;
384 dep
->next
= data
->depends
;
390 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
391 are just ad-hoc constants. The estimates should be based on target-specific
395 stmt_cost (tree stmt
)
400 /* Always try to create possibilities for unswitching. */
401 if (TREE_CODE (stmt
) == COND_EXPR
)
402 return LIM_EXPENSIVE
;
404 rhs
= TREE_OPERAND (stmt
, 1);
406 /* Hoisting memory references out should almost surely be a win. */
407 if (stmt_references_memory_p (stmt
))
410 switch (TREE_CODE (rhs
))
413 /* We should be hoisting calls if possible. */
415 /* Unless the call is a builtin_constant_p; this always folds to a
416 constant, so moving it is useless. */
417 rhs
= get_callee_fndecl (rhs
);
418 if (DECL_BUILT_IN_CLASS (rhs
) == BUILT_IN_NORMAL
419 && DECL_FUNCTION_CODE (rhs
) == BUILT_IN_CONSTANT_P
)
436 /* Division and multiplication are usually expensive. */
447 /* Determine the outermost loop to that it is possible to hoist a statement
448 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
449 the outermost loop in that the value computed by STMT is invariant.
450 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
451 we preserve the fact whether STMT is executed. It also fills other related
452 information to LIM_DATA (STMT).
454 The function returns false if STMT cannot be hoisted outside of the loop it
455 is defined in, and true otherwise. */
458 determine_max_movement (tree stmt
, bool must_preserve_exec
)
460 basic_block bb
= bb_for_stmt (stmt
);
461 struct loop
*loop
= bb
->loop_father
;
463 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
467 if (must_preserve_exec
)
468 level
= ALWAYS_EXECUTED_IN (bb
);
470 level
= superloop_at_depth (loop
, 1);
471 lim_data
->max_loop
= level
;
473 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
474 if (!add_dependency (val
, lim_data
, loop
, true))
477 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
478 if (!add_dependency (val
, lim_data
, loop
, false))
481 lim_data
->cost
+= stmt_cost (stmt
);
486 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
487 and that one of the operands of this statement is computed by STMT.
488 Ensure that STMT (together with all the statements that define its
489 operands) is hoisted at least out of the loop LEVEL. */
492 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
494 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
497 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
498 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
499 stmt_loop
= find_common_loop (stmt_loop
,
500 LIM_DATA (stmt
)->tgt_loop
->outer
);
501 if (flow_loop_nested_p (stmt_loop
, level
))
504 gcc_assert (LIM_DATA (stmt
));
505 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
506 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
508 LIM_DATA (stmt
)->tgt_loop
= level
;
509 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
510 set_level (dep
->stmt
, orig_loop
, level
);
513 /* Determines an outermost loop from that we want to hoist the statement STMT.
514 For now we chose the outermost possible loop. TODO -- use profiling
515 information to set it more sanely. */
518 set_profitable_level (tree stmt
)
520 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
523 /* Returns true if STMT is not a pure call. */
526 nonpure_call_p (tree stmt
)
528 tree call
= get_call_expr_in (stmt
);
533 return TREE_SIDE_EFFECTS (call
) != 0;
536 /* Releases the memory occupied by DATA. */
539 free_lim_aux_data (struct lim_aux_data
*data
)
541 struct depend
*dep
, *next
;
543 for (dep
= data
->depends
; dep
; dep
= next
)
551 /* Determine the outermost loops in that statements in basic block BB are
552 invariant, and record them to the LIM_DATA associated with the statements.
553 Callback for walk_dominator_tree. */
556 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
560 block_stmt_iterator bsi
;
562 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
563 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
565 if (!bb
->loop_father
->outer
)
568 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
569 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
570 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
572 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
574 stmt
= bsi_stmt (bsi
);
576 pos
= movement_possibility (stmt
);
577 if (pos
== MOVE_IMPOSSIBLE
)
579 if (nonpure_call_p (stmt
))
587 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
588 to be hoisted out of loop, saving expensive divide. */
589 if (pos
== MOVE_POSSIBLE
590 && (rhs
= TREE_OPERAND (stmt
, 1)) != NULL
591 && TREE_CODE (rhs
) == RDIV_EXPR
592 && flag_unsafe_math_optimizations
593 && outermost_invariant_loop_expr (TREE_OPERAND (rhs
, 1),
594 loop_containing_stmt (stmt
)) != NULL
595 && outermost_invariant_loop_expr (rhs
,
596 loop_containing_stmt (stmt
)) == NULL
)
598 tree lhs
, stmt1
, stmt2
, var
, name
;
600 lhs
= TREE_OPERAND (stmt
, 0);
602 /* stmt must be MODIFY_EXPR. */
603 var
= create_tmp_var (TREE_TYPE (rhs
), "reciptmp");
604 add_referenced_tmp_var (var
);
606 stmt1
= build2 (MODIFY_EXPR
, void_type_node
, var
,
607 build2 (RDIV_EXPR
, TREE_TYPE (rhs
),
608 build_real (TREE_TYPE (rhs
), dconst1
),
609 TREE_OPERAND (rhs
, 1)));
610 name
= make_ssa_name (var
, stmt1
);
611 TREE_OPERAND (stmt1
, 0) = name
;
612 stmt2
= build2 (MODIFY_EXPR
, void_type_node
, lhs
,
613 build2 (MULT_EXPR
, TREE_TYPE (rhs
),
614 name
, TREE_OPERAND (rhs
, 0)));
616 /* Replace division stmt with reciprocal and multiply stmts.
617 The multiply stmt is not invariant, so update iterator
618 and avoid rescanning. */
619 bsi_replace (&bsi
, stmt1
, true);
620 bsi_insert_after (&bsi
, stmt2
, BSI_NEW_STMT
);
621 SSA_NAME_DEF_STMT (lhs
) = stmt2
;
623 /* Continue processing with invariant reciprocal statment. */
627 stmt_ann (stmt
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
628 LIM_DATA (stmt
)->always_executed_in
= outermost
;
630 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
633 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
635 LIM_DATA (stmt
)->max_loop
= NULL
;
639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
642 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
643 LIM_DATA (stmt
)->max_loop
->depth
,
644 LIM_DATA (stmt
)->cost
);
647 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
648 set_profitable_level (stmt
);
652 /* For each statement determines the outermost loop in that it is invariant,
653 statements on whose motion it depends and the cost of the computation.
654 This information is stored to the LIM_DATA structure associated with
658 determine_invariantness (void)
660 struct dom_walk_data walk_data
;
662 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
663 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
665 init_walk_dominator_tree (&walk_data
);
666 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
667 fini_walk_dominator_tree (&walk_data
);
670 /* Commits edge insertions and updates loop structures. */
673 loop_commit_inserts (void)
675 unsigned old_last_basic_block
, i
;
678 old_last_basic_block
= last_basic_block
;
679 bsi_commit_edge_inserts ();
680 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
682 bb
= BASIC_BLOCK (i
);
684 find_common_loop (single_pred (bb
)->loop_father
,
685 single_succ (bb
)->loop_father
));
689 /* Hoist the statements in basic block BB out of the loops prescribed by
690 data stored in LIM_DATA structures associated with each statement. Callback
691 for walk_dominator_tree. */
694 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
698 block_stmt_iterator bsi
;
702 if (!bb
->loop_father
->outer
)
705 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
707 stmt
= bsi_stmt (bsi
);
709 if (!LIM_DATA (stmt
))
715 cost
= LIM_DATA (stmt
)->cost
;
716 level
= LIM_DATA (stmt
)->tgt_loop
;
717 free_lim_aux_data (LIM_DATA (stmt
));
718 stmt_ann (stmt
)->aux
= NULL
;
726 /* We do not really want to move conditionals out of the loop; we just
727 placed it here to force its operands to be moved if necessary. */
728 if (TREE_CODE (stmt
) == COND_EXPR
)
731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
733 fprintf (dump_file
, "Moving statement\n");
734 print_generic_stmt (dump_file
, stmt
, 0);
735 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
738 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
743 /* Hoist the statements out of the loops prescribed by data stored in
744 LIM_DATA structures associated with each statement.*/
747 move_computations (void)
749 struct dom_walk_data walk_data
;
751 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
752 walk_data
.before_dom_children_before_stmts
= move_computations_stmt
;
754 init_walk_dominator_tree (&walk_data
);
755 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
756 fini_walk_dominator_tree (&walk_data
);
758 loop_commit_inserts ();
759 if (need_ssa_update_p ())
760 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
763 /* Checks whether the statement defining variable *INDEX can be hoisted
764 out of the loop passed in DATA. Callback for for_each_index. */
767 may_move_till (tree ref
, tree
*index
, void *data
)
769 struct loop
*loop
= data
, *max_loop
;
771 /* If REF is an array reference, check also that the step and the lower
772 bound is invariant in LOOP. */
773 if (TREE_CODE (ref
) == ARRAY_REF
)
775 tree step
= array_ref_element_size (ref
);
776 tree lbound
= array_ref_low_bound (ref
);
778 max_loop
= outermost_invariant_loop_expr (step
, loop
);
782 max_loop
= outermost_invariant_loop_expr (lbound
, loop
);
787 max_loop
= outermost_invariant_loop (*index
, loop
);
794 /* Forces statements defining (invariant) SSA names in expression EXPR to be
795 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
798 force_move_till_expr (tree expr
, struct loop
*orig_loop
, struct loop
*loop
)
800 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
803 if (TREE_CODE (expr
) == SSA_NAME
)
805 tree stmt
= SSA_NAME_DEF_STMT (expr
);
806 if (IS_EMPTY_STMT (stmt
))
809 set_level (stmt
, orig_loop
, loop
);
813 if (class != tcc_unary
814 && class != tcc_binary
815 && class != tcc_expression
816 && class != tcc_comparison
)
819 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
820 for (i
= 0; i
< nops
; i
++)
821 force_move_till_expr (TREE_OPERAND (expr
, i
), orig_loop
, loop
);
824 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
825 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
831 struct loop
*orig_loop
;
835 force_move_till (tree ref
, tree
*index
, void *data
)
838 struct fmt_data
*fmt_data
= data
;
840 if (TREE_CODE (ref
) == ARRAY_REF
)
842 tree step
= array_ref_element_size (ref
);
843 tree lbound
= array_ref_low_bound (ref
);
845 force_move_till_expr (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
846 force_move_till_expr (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
849 if (TREE_CODE (*index
) != SSA_NAME
)
852 stmt
= SSA_NAME_DEF_STMT (*index
);
853 if (IS_EMPTY_STMT (stmt
))
856 set_level (stmt
, fmt_data
->orig_loop
, fmt_data
->loop
);
861 /* Records memory reference location *REF to the list MEM_REFS. The reference
862 occurs in statement STMT. */
865 record_mem_ref_loc (struct mem_ref_loc
**mem_refs
, tree stmt
, tree
*ref
)
867 struct mem_ref_loc
*aref
= xmalloc (sizeof (struct mem_ref_loc
));
872 aref
->next
= *mem_refs
;
876 /* Releases list of memory reference locations MEM_REFS. */
879 free_mem_ref_locs (struct mem_ref_loc
*mem_refs
)
881 struct mem_ref_loc
*act
;
886 mem_refs
= mem_refs
->next
;
891 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
894 rewrite_mem_refs (tree tmp_var
, struct mem_ref_loc
*mem_refs
)
899 for (; mem_refs
; mem_refs
= mem_refs
->next
)
901 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
902 mark_sym_for_renaming (SSA_NAME_VAR (var
));
904 *mem_refs
->ref
= tmp_var
;
905 update_stmt (mem_refs
->stmt
);
909 /* Records request for store motion of memory reference REF from LOOP.
910 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
911 these references are rewritten by a new temporary variable.
912 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
913 The initialization of the temporary variable is put to the preheader
914 of the loop, and assignments to the reference from the temporary variable
915 are emitted to exits. */
918 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
919 struct mem_ref_loc
*mem_refs
)
921 struct mem_ref_loc
*aref
;
925 struct fmt_data fmt_data
;
927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
929 fprintf (dump_file
, "Executing store motion of ");
930 print_generic_expr (dump_file
, ref
, 0);
931 fprintf (dump_file
, " from loop %d\n", loop
->num
);
934 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
936 fmt_data
.loop
= loop
;
937 fmt_data
.orig_loop
= loop
;
938 for_each_index (&ref
, force_move_till
, &fmt_data
);
940 rewrite_mem_refs (tmp_var
, mem_refs
);
941 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
942 if (LIM_DATA (aref
->stmt
))
943 LIM_DATA (aref
->stmt
)->sm_done
= true;
945 /* Emit the load & stores. */
946 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
947 get_stmt_ann (load
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
948 LIM_DATA (load
)->max_loop
= loop
;
949 LIM_DATA (load
)->tgt_loop
= loop
;
951 /* Put this into the latch, so that we are sure it will be processed after
953 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
955 for (i
= 0; i
< n_exits
; i
++)
957 store
= build (MODIFY_EXPR
, void_type_node
,
958 unshare_expr (ref
), tmp_var
);
959 bsi_insert_on_edge (exits
[i
], store
);
963 /* Check whether memory reference REF can be hoisted out of the LOOP. If this
964 is true, prepare the statements that load the value of the memory reference
965 to a temporary variable in the loop preheader, store it back on the loop
966 exits, and replace all the references inside LOOP by this temporary variable.
967 LOOP has N_EXITS stored in EXITS. CLOBBERED_VOPS is the bitmap of virtual
968 operands that are clobbered by a call or accessed through multiple references
972 determine_lsm_ref (struct loop
*loop
, edge
*exits
, unsigned n_exits
,
973 bitmap clobbered_vops
, struct mem_ref
*ref
)
975 struct mem_ref_loc
*aref
;
976 struct loop
*must_exec
;
978 /* In case the memory is not stored to, there is nothing for SM to do. */
982 /* If the reference is aliased with any different ref, or killed by call
983 in function, then fail. */
984 if (bitmap_intersect_p (ref
->vops
, clobbered_vops
))
987 if (tree_could_trap_p (ref
->mem
))
989 /* If the memory access is unsafe (i.e. it might trap), ensure that some
990 of the statements in that it occurs is always executed when the loop
991 is entered. This way we know that by moving the load from the
992 reference out of the loop we will not cause the error that would not
995 TODO -- in fact we would like to check for anticipability of the
996 reference, i.e. that on each path from loop entry to loop exit at
997 least one of the statements containing the memory reference is
1000 for (aref
= ref
->locs
; aref
; aref
= aref
->next
)
1002 if (!LIM_DATA (aref
->stmt
))
1005 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1009 if (must_exec
== loop
1010 || flow_loop_nested_p (must_exec
, loop
))
1018 schedule_sm (loop
, exits
, n_exits
, ref
->mem
, ref
->locs
);
1021 /* Attempts to hoist memory reference described in SLOT out of loop
1022 described in DATA. Callback for htab_traverse. */
1026 struct loop
*loop
; /* Loop from that the reference should be hoisted. */
1027 edge
*exits
; /* Exits of the loop. */
1028 unsigned n_exits
; /* Length of the exits array. */
1029 bitmap clobbered_vops
;/* The vops clobbered by call in loop or accessed by
1030 multiple memory references. */
1034 hoist_memory_reference (void **slot
, void *data
)
1036 struct mem_ref
*ref
= *slot
;
1037 struct hmr_data
*hmr_data
= data
;
1039 determine_lsm_ref (hmr_data
->loop
, hmr_data
->exits
, hmr_data
->n_exits
,
1040 hmr_data
->clobbered_vops
, ref
);
1045 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1046 for a store motion optimization (i.e. whether we can insert statement
1050 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1055 for (i
= 0; i
< n_exits
; i
++)
1056 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1062 /* A hash function for struct mem_ref object OBJ. */
1065 memref_hash (const void *obj
)
1067 const struct mem_ref
*mem
= obj
;
1072 /* An equality function for struct mem_ref object OBJ1 with
1073 memory reference OBJ2. */
1076 memref_eq (const void *obj1
, const void *obj2
)
1078 const struct mem_ref
*mem1
= obj1
;
1080 return operand_equal_p (mem1
->mem
, (tree
) obj2
, 0);
1083 /* A function to free the struct mem_ref object OBJ. */
1086 memref_del (void *obj
)
1088 struct mem_ref
*mem
= obj
;
1090 free_mem_ref_locs (mem
->locs
);
1091 BITMAP_FREE (mem
->vops
);
1095 /* Gathers memory references in statement STMT in LOOP, storing the
1096 information about them in MEM_REFS hash table. Note vops accessed through
1097 unrecognized statements in CLOBBERED_VOPS. */
1100 gather_mem_refs_stmt (struct loop
*loop
, htab_t mem_refs
,
1101 bitmap clobbered_vops
, tree stmt
)
1103 tree
*lhs
, *rhs
, *mem
= NULL
;
1106 struct mem_ref
*ref
= NULL
;
1111 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1114 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
1115 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1118 lhs
= &TREE_OPERAND (stmt
, 0);
1119 rhs
= &TREE_OPERAND (stmt
, 1);
1121 if (TREE_CODE (*lhs
) == SSA_NAME
)
1123 if (!is_gimple_addressable (*rhs
))
1129 else if (TREE_CODE (*rhs
) == SSA_NAME
1130 || is_gimple_min_invariant (*rhs
))
1138 /* If we cannot create an SSA name for the result, give up. */
1139 if (!is_gimple_reg_type (TREE_TYPE (*mem
))
1140 || TREE_THIS_VOLATILE (*mem
))
1143 /* If we cannot move the reference out of the loop, fail. */
1144 if (!for_each_index (mem
, may_move_till
, loop
))
1147 hash
= iterative_hash_expr (*mem
, 0);
1148 slot
= htab_find_slot_with_hash (mem_refs
, *mem
, hash
, INSERT
);
1154 ref
= xmalloc (sizeof (struct mem_ref
));
1158 ref
->is_stored
= false;
1159 ref
->vops
= BITMAP_ALLOC (NULL
);
1162 ref
->is_stored
|= is_stored
;
1164 FOR_EACH_SSA_TREE_OPERAND (vname
, stmt
, oi
,
1165 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1167 bitmap_set_bit (ref
->vops
,
1168 var_ann (SSA_NAME_VAR (vname
))->uid
);
1170 record_mem_ref_loc (&ref
->locs
, stmt
, mem
);
1174 FOR_EACH_SSA_TREE_OPERAND (vname
, stmt
, oi
,
1175 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1177 bitmap_set_bit (clobbered_vops
,
1178 var_ann (SSA_NAME_VAR (vname
))->uid
);
1182 /* Gathers memory references in LOOP, storing the information about them
1183 in MEM_REFS hash table. Note vops accessed through unrecognized
1184 statements in CLOBBERED_VOPS. */
1187 gather_mem_refs (struct loop
*loop
, htab_t mem_refs
, bitmap clobbered_vops
)
1189 basic_block
*body
= get_loop_body (loop
);
1190 block_stmt_iterator bsi
;
1193 for (i
= 0; i
< loop
->num_nodes
; i
++)
1195 for (bsi
= bsi_start (body
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
1196 gather_mem_refs_stmt (loop
, mem_refs
, clobbered_vops
, bsi_stmt (bsi
));
1202 /* Finds the vops accessed by memory reference described in SLOT as well as
1203 some other reference(s) and marks them in DATA->clobbered_vops.
1204 Callback for htab_traverse. */
1208 bitmap clobbered_vops
; /* The vops clobbered by call in loop or accessed by
1209 multiple memory references. */
1210 bitmap all_vops
; /* All vops referenced in the loop. */
1214 find_more_ref_vops (void **slot
, void *data
)
1216 struct mem_ref
*ref
= *slot
;
1217 struct fmrv_data
*fmrv_data
= data
;
1220 /* The vops that are already in all_vops are accessed by more than
1221 one memory reference. */
1222 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1223 bitmap_and (&tmp
, fmrv_data
->all_vops
, ref
->vops
);
1224 bitmap_ior_into (fmrv_data
->clobbered_vops
, &tmp
);
1225 bitmap_clear (&tmp
);
1227 bitmap_ior_into (fmrv_data
->all_vops
, ref
->vops
);
1231 /* Try to perform store motion for all memory references modified inside
1235 determine_lsm_loop (struct loop
*loop
)
1238 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1240 struct hmr_data hmr_data
;
1241 struct fmrv_data fmrv_data
;
1242 bitmap clobbered_vops
;
1244 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1250 mem_refs
= htab_create (100, memref_hash
, memref_eq
, memref_del
);
1252 /* Find the memory references in LOOP. */
1253 clobbered_vops
= BITMAP_ALLOC (NULL
);
1254 gather_mem_refs (loop
, mem_refs
, clobbered_vops
);
1256 /* Find the vops that are used for more than one reference. */
1257 fmrv_data
.all_vops
= BITMAP_ALLOC (NULL
);
1258 fmrv_data
.clobbered_vops
= clobbered_vops
;
1259 htab_traverse (mem_refs
, find_more_ref_vops
, &fmrv_data
);
1260 BITMAP_FREE (fmrv_data
.all_vops
);
1262 /* Hoist all suitable memory references. */
1263 hmr_data
.loop
= loop
;
1264 hmr_data
.exits
= exits
;
1265 hmr_data
.n_exits
= n_exits
;
1266 hmr_data
.clobbered_vops
= clobbered_vops
;
1267 htab_traverse (mem_refs
, hoist_memory_reference
, &hmr_data
);
1269 htab_delete (mem_refs
);
1271 BITMAP_FREE (clobbered_vops
);
1274 /* Try to perform store motion for all memory references modified inside
1278 determine_lsm (struct loops
*loops
)
1282 if (!loops
->tree_root
->inner
)
1285 /* Pass the loops from the outermost and perform the store motion as
1288 loop
= loops
->tree_root
->inner
;
1291 determine_lsm_loop (loop
);
1301 if (loop
== loops
->tree_root
)
1303 loop_commit_inserts ();
1311 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1312 for each such basic block bb records the outermost loop for that execution
1313 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1314 blocks that contain a nonpure call. */
1317 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1319 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1322 struct loop
*inn_loop
= loop
;
1324 if (!loop
->header
->aux
)
1326 bbs
= get_loop_body_in_dom_order (loop
);
1328 for (i
= 0; i
< loop
->num_nodes
; i
++)
1333 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1336 if (TEST_BIT (contains_call
, bb
->index
))
1339 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1340 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1345 /* A loop might be infinite (TODO use simple loop analysis
1346 to disprove this if possible). */
1347 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1350 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1353 if (bb
->loop_father
->header
== bb
)
1355 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1358 /* In a loop that is always entered we may proceed anyway.
1359 But record that we entered it and stop once we leave it. */
1360 inn_loop
= bb
->loop_father
;
1367 if (last
== loop
->header
)
1369 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1375 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1376 fill_always_executed_in (loop
, contains_call
);
1379 /* Compute the global information needed by the loop invariant motion pass.
1380 LOOPS is the loop tree. */
1383 tree_ssa_lim_initialize (struct loops
*loops
)
1385 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1386 block_stmt_iterator bsi
;
1390 sbitmap_zero (contains_call
);
1393 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1395 if (nonpure_call_p (bsi_stmt (bsi
)))
1399 if (!bsi_end_p (bsi
))
1400 SET_BIT (contains_call
, bb
->index
);
1403 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1404 fill_always_executed_in (loop
, contains_call
);
1406 sbitmap_free (contains_call
);
1409 /* Cleans up after the invariant motion pass. */
1412 tree_ssa_lim_finalize (void)
1422 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1423 i.e. those that are likely to be win regardless of the register pressure. */
1426 tree_ssa_lim (struct loops
*loops
)
1428 tree_ssa_lim_initialize (loops
);
1430 /* For each statement determine the outermost loop in that it is
1431 invariant and cost for computing the invariant. */
1432 determine_invariantness ();
1434 /* For each memory reference determine whether it is possible to hoist it
1435 out of the loop. Force the necessary invariants to be moved out of the
1437 determine_lsm (loops
);
1439 /* Move the expressions that are expensive enough. */
1440 move_computations ();
1442 tree_ssa_lim_finalize ();