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
127 struct mem_ref
*next
; /* Next memory reference in the list.
128 Memory references are stored in a hash
129 table, but the hash function depends
130 on values of pointers. Thus we cannot use
131 htab_traverse, since then we would get
132 miscompares during bootstrap (although the
133 produced code would be correct). */
136 /* Minimum cost of an expensive expression. */
137 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
139 /* The outermost loop for that execution of the header guarantees that the
140 block will be executed. */
141 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
143 /* Calls CBCK for each index in memory reference ADDR_P. There are two
144 kinds situations handled; in each of these cases, the memory reference
145 and DATA are passed to the callback:
147 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
148 pass the pointer to the index to the callback.
150 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
151 pointer to addr to the callback.
153 If the callback returns false, the whole search stops and false is returned.
154 Otherwise the function returns true after traversing through the whole
155 reference *ADDR_P. */
158 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
162 for (; ; addr_p
= nxt
)
164 switch (TREE_CODE (*addr_p
))
167 return cbck (*addr_p
, addr_p
, data
);
169 case MISALIGNED_INDIRECT_REF
:
170 case ALIGN_INDIRECT_REF
:
172 nxt
= &TREE_OPERAND (*addr_p
, 0);
173 return cbck (*addr_p
, nxt
, data
);
176 case VIEW_CONVERT_EXPR
:
177 case ARRAY_RANGE_REF
:
180 nxt
= &TREE_OPERAND (*addr_p
, 0);
184 /* If the component has varying offset, it behaves like index
186 idx
= &TREE_OPERAND (*addr_p
, 2);
188 && !cbck (*addr_p
, idx
, data
))
191 nxt
= &TREE_OPERAND (*addr_p
, 0);
195 nxt
= &TREE_OPERAND (*addr_p
, 0);
196 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
212 /* If it is possible to hoist the statement STMT unconditionally,
213 returns MOVE_POSSIBLE.
214 If it is possible to hoist the statement STMT, but we must avoid making
215 it executed if it would not be executed in the original program (e.g.
216 because it may trap), return MOVE_PRESERVE_EXECUTION.
217 Otherwise return MOVE_IMPOSSIBLE. */
220 movement_possibility (tree stmt
)
224 if (flag_unswitch_loops
225 && TREE_CODE (stmt
) == COND_EXPR
)
227 /* If we perform unswitching, force the operands of the invariant
228 condition to be moved out of the loop. */
229 return MOVE_POSSIBLE
;
232 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
233 return MOVE_IMPOSSIBLE
;
235 if (stmt_ends_bb_p (stmt
))
236 return MOVE_IMPOSSIBLE
;
238 if (stmt_ann (stmt
)->has_volatile_ops
)
239 return MOVE_IMPOSSIBLE
;
241 lhs
= TREE_OPERAND (stmt
, 0);
242 if (TREE_CODE (lhs
) == SSA_NAME
243 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
244 return MOVE_IMPOSSIBLE
;
246 rhs
= TREE_OPERAND (stmt
, 1);
248 if (TREE_SIDE_EFFECTS (rhs
))
249 return MOVE_IMPOSSIBLE
;
251 if (TREE_CODE (lhs
) != SSA_NAME
252 || tree_could_trap_p (rhs
))
253 return MOVE_PRESERVE_EXECUTION
;
255 if (get_call_expr_in (stmt
))
257 /* While pure or const call is guaranteed to have no side effects, we
258 cannot move it arbitrarily. Consider code like
260 char *s = something ();
270 Here the strlen call cannot be moved out of the loop, even though
271 s is invariant. In addition to possibly creating a call with
272 invalid arguments, moving out a function call that is not executed
273 may cause performance regressions in case the call is costly and
274 not executed at all. */
275 return MOVE_PRESERVE_EXECUTION
;
277 return MOVE_POSSIBLE
;
280 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
281 loop to that we could move the expression using DEF if it did not have
282 other operands, i.e. the outermost loop enclosing LOOP in that the value
283 of DEF is invariant. */
286 outermost_invariant_loop (tree def
, struct loop
*loop
)
290 struct loop
*max_loop
;
292 if (TREE_CODE (def
) != SSA_NAME
)
293 return superloop_at_depth (loop
, 1);
295 def_stmt
= SSA_NAME_DEF_STMT (def
);
296 def_bb
= bb_for_stmt (def_stmt
);
298 return superloop_at_depth (loop
, 1);
300 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
302 if (LIM_DATA (def_stmt
) && LIM_DATA (def_stmt
)->max_loop
)
303 max_loop
= find_common_loop (max_loop
,
304 LIM_DATA (def_stmt
)->max_loop
->outer
);
305 if (max_loop
== loop
)
307 max_loop
= superloop_at_depth (loop
, max_loop
->depth
+ 1);
312 /* Returns the outermost superloop of LOOP in that the expression EXPR is
316 outermost_invariant_loop_expr (tree expr
, struct loop
*loop
)
318 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
320 struct loop
*max_loop
= superloop_at_depth (loop
, 1), *aloop
;
322 if (TREE_CODE (expr
) == SSA_NAME
323 || TREE_CODE (expr
) == INTEGER_CST
324 || is_gimple_min_invariant (expr
))
325 return outermost_invariant_loop (expr
, loop
);
327 if (class != tcc_unary
328 && class != tcc_binary
329 && class != tcc_expression
330 && class != tcc_comparison
)
333 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
334 for (i
= 0; i
< nops
; i
++)
336 aloop
= outermost_invariant_loop_expr (TREE_OPERAND (expr
, i
), loop
);
340 if (flow_loop_nested_p (max_loop
, aloop
))
347 /* DATA is a structure containing information associated with a statement
348 inside LOOP. DEF is one of the operands of this statement.
350 Find the outermost loop enclosing LOOP in that value of DEF is invariant
351 and record this in DATA->max_loop field. If DEF itself is defined inside
352 this loop as well (i.e. we need to hoist it out of the loop if we want
353 to hoist the statement represented by DATA), record the statement in that
354 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
355 add the cost of the computation of DEF to the DATA->cost.
357 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
360 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
363 tree def_stmt
= SSA_NAME_DEF_STMT (def
);
364 basic_block def_bb
= bb_for_stmt (def_stmt
);
365 struct loop
*max_loop
;
371 max_loop
= outermost_invariant_loop (def
, loop
);
375 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
376 data
->max_loop
= max_loop
;
378 if (!LIM_DATA (def_stmt
))
382 /* Only add the cost if the statement defining DEF is inside LOOP,
383 i.e. if it is likely that by moving the invariants dependent
384 on it, we will be able to avoid creating a new register for
385 it (since it will be only used in these dependent invariants). */
386 && def_bb
->loop_father
== loop
)
387 data
->cost
+= LIM_DATA (def_stmt
)->cost
;
389 dep
= xmalloc (sizeof (struct depend
));
390 dep
->stmt
= def_stmt
;
391 dep
->next
= data
->depends
;
397 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
398 are just ad-hoc constants. The estimates should be based on target-specific
402 stmt_cost (tree stmt
)
407 /* Always try to create possibilities for unswitching. */
408 if (TREE_CODE (stmt
) == COND_EXPR
)
409 return LIM_EXPENSIVE
;
411 rhs
= TREE_OPERAND (stmt
, 1);
413 /* Hoisting memory references out should almost surely be a win. */
414 if (stmt_references_memory_p (stmt
))
417 switch (TREE_CODE (rhs
))
420 /* We should be hoisting calls if possible. */
422 /* Unless the call is a builtin_constant_p; this always folds to a
423 constant, so moving it is useless. */
424 rhs
= get_callee_fndecl (rhs
);
425 if (DECL_BUILT_IN_CLASS (rhs
) == BUILT_IN_NORMAL
426 && DECL_FUNCTION_CODE (rhs
) == BUILT_IN_CONSTANT_P
)
443 /* Division and multiplication are usually expensive. */
454 /* Determine the outermost loop to that it is possible to hoist a statement
455 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
456 the outermost loop in that the value computed by STMT is invariant.
457 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
458 we preserve the fact whether STMT is executed. It also fills other related
459 information to LIM_DATA (STMT).
461 The function returns false if STMT cannot be hoisted outside of the loop it
462 is defined in, and true otherwise. */
465 determine_max_movement (tree stmt
, bool must_preserve_exec
)
467 basic_block bb
= bb_for_stmt (stmt
);
468 struct loop
*loop
= bb
->loop_father
;
470 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
474 if (must_preserve_exec
)
475 level
= ALWAYS_EXECUTED_IN (bb
);
477 level
= superloop_at_depth (loop
, 1);
478 lim_data
->max_loop
= level
;
480 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
481 if (!add_dependency (val
, lim_data
, loop
, true))
484 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
485 if (!add_dependency (val
, lim_data
, loop
, false))
488 lim_data
->cost
+= stmt_cost (stmt
);
493 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
494 and that one of the operands of this statement is computed by STMT.
495 Ensure that STMT (together with all the statements that define its
496 operands) is hoisted at least out of the loop LEVEL. */
499 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
501 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
504 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
505 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
506 stmt_loop
= find_common_loop (stmt_loop
,
507 LIM_DATA (stmt
)->tgt_loop
->outer
);
508 if (flow_loop_nested_p (stmt_loop
, level
))
511 gcc_assert (LIM_DATA (stmt
));
512 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
513 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
515 LIM_DATA (stmt
)->tgt_loop
= level
;
516 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
517 set_level (dep
->stmt
, orig_loop
, level
);
520 /* Determines an outermost loop from that we want to hoist the statement STMT.
521 For now we chose the outermost possible loop. TODO -- use profiling
522 information to set it more sanely. */
525 set_profitable_level (tree stmt
)
527 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
530 /* Returns true if STMT is not a pure call. */
533 nonpure_call_p (tree stmt
)
535 tree call
= get_call_expr_in (stmt
);
540 return TREE_SIDE_EFFECTS (call
) != 0;
543 /* Releases the memory occupied by DATA. */
546 free_lim_aux_data (struct lim_aux_data
*data
)
548 struct depend
*dep
, *next
;
550 for (dep
= data
->depends
; dep
; dep
= next
)
558 /* Determine the outermost loops in that statements in basic block BB are
559 invariant, and record them to the LIM_DATA associated with the statements.
560 Callback for walk_dominator_tree. */
563 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
567 block_stmt_iterator bsi
;
569 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
570 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
572 if (!bb
->loop_father
->outer
)
575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
576 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
577 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
579 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
581 stmt
= bsi_stmt (bsi
);
583 pos
= movement_possibility (stmt
);
584 if (pos
== MOVE_IMPOSSIBLE
)
586 if (nonpure_call_p (stmt
))
594 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
595 to be hoisted out of loop, saving expensive divide. */
596 if (pos
== MOVE_POSSIBLE
597 && (rhs
= TREE_OPERAND (stmt
, 1)) != NULL
598 && TREE_CODE (rhs
) == RDIV_EXPR
599 && flag_unsafe_math_optimizations
600 && outermost_invariant_loop_expr (TREE_OPERAND (rhs
, 1),
601 loop_containing_stmt (stmt
)) != NULL
602 && outermost_invariant_loop_expr (rhs
,
603 loop_containing_stmt (stmt
)) == NULL
)
605 tree lhs
, stmt1
, stmt2
, var
, name
;
607 lhs
= TREE_OPERAND (stmt
, 0);
609 /* stmt must be MODIFY_EXPR. */
610 var
= create_tmp_var (TREE_TYPE (rhs
), "reciptmp");
611 add_referenced_tmp_var (var
);
613 stmt1
= build2 (MODIFY_EXPR
, void_type_node
, var
,
614 build2 (RDIV_EXPR
, TREE_TYPE (rhs
),
615 build_real (TREE_TYPE (rhs
), dconst1
),
616 TREE_OPERAND (rhs
, 1)));
617 name
= make_ssa_name (var
, stmt1
);
618 TREE_OPERAND (stmt1
, 0) = name
;
619 stmt2
= build2 (MODIFY_EXPR
, void_type_node
, lhs
,
620 build2 (MULT_EXPR
, TREE_TYPE (rhs
),
621 name
, TREE_OPERAND (rhs
, 0)));
623 /* Replace division stmt with reciprocal and multiply stmts.
624 The multiply stmt is not invariant, so update iterator
625 and avoid rescanning. */
626 bsi_replace (&bsi
, stmt1
, true);
627 bsi_insert_after (&bsi
, stmt2
, BSI_NEW_STMT
);
628 SSA_NAME_DEF_STMT (lhs
) = stmt2
;
630 /* Continue processing with invariant reciprocal statement. */
634 stmt_ann (stmt
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
635 LIM_DATA (stmt
)->always_executed_in
= outermost
;
637 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
640 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
642 LIM_DATA (stmt
)->max_loop
= NULL
;
646 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
648 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
649 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
650 LIM_DATA (stmt
)->max_loop
->depth
,
651 LIM_DATA (stmt
)->cost
);
654 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
655 set_profitable_level (stmt
);
659 /* For each statement determines the outermost loop in that it is invariant,
660 statements on whose motion it depends and the cost of the computation.
661 This information is stored to the LIM_DATA structure associated with
665 determine_invariantness (void)
667 struct dom_walk_data walk_data
;
669 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
670 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
672 init_walk_dominator_tree (&walk_data
);
673 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
674 fini_walk_dominator_tree (&walk_data
);
677 /* Commits edge insertions and updates loop structures. */
680 loop_commit_inserts (void)
682 unsigned old_last_basic_block
, i
;
685 old_last_basic_block
= last_basic_block
;
686 bsi_commit_edge_inserts ();
687 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
689 bb
= BASIC_BLOCK (i
);
691 find_common_loop (single_pred (bb
)->loop_father
,
692 single_succ (bb
)->loop_father
));
696 /* Hoist the statements in basic block BB out of the loops prescribed by
697 data stored in LIM_DATA structures associated with each statement. Callback
698 for walk_dominator_tree. */
701 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
705 block_stmt_iterator bsi
;
709 if (!bb
->loop_father
->outer
)
712 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
714 stmt
= bsi_stmt (bsi
);
716 if (!LIM_DATA (stmt
))
722 cost
= LIM_DATA (stmt
)->cost
;
723 level
= LIM_DATA (stmt
)->tgt_loop
;
724 free_lim_aux_data (LIM_DATA (stmt
));
725 stmt_ann (stmt
)->aux
= NULL
;
733 /* We do not really want to move conditionals out of the loop; we just
734 placed it here to force its operands to be moved if necessary. */
735 if (TREE_CODE (stmt
) == COND_EXPR
)
738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
740 fprintf (dump_file
, "Moving statement\n");
741 print_generic_stmt (dump_file
, stmt
, 0);
742 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
745 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
750 /* Hoist the statements out of the loops prescribed by data stored in
751 LIM_DATA structures associated with each statement.*/
754 move_computations (void)
756 struct dom_walk_data walk_data
;
758 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
759 walk_data
.before_dom_children_before_stmts
= move_computations_stmt
;
761 init_walk_dominator_tree (&walk_data
);
762 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
763 fini_walk_dominator_tree (&walk_data
);
765 loop_commit_inserts ();
766 if (need_ssa_update_p ())
767 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
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 location *REF to the list MEM_REFS. The reference
869 occurs in statement STMT. */
872 record_mem_ref_loc (struct mem_ref_loc
**mem_refs
, tree stmt
, tree
*ref
)
874 struct mem_ref_loc
*aref
= xmalloc (sizeof (struct mem_ref_loc
));
879 aref
->next
= *mem_refs
;
883 /* Releases list of memory reference locations MEM_REFS. */
886 free_mem_ref_locs (struct mem_ref_loc
*mem_refs
)
888 struct mem_ref_loc
*act
;
893 mem_refs
= mem_refs
->next
;
898 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
901 rewrite_mem_refs (tree tmp_var
, struct mem_ref_loc
*mem_refs
)
906 for (; mem_refs
; mem_refs
= mem_refs
->next
)
908 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
909 mark_sym_for_renaming (SSA_NAME_VAR (var
));
911 *mem_refs
->ref
= tmp_var
;
912 update_stmt (mem_refs
->stmt
);
916 /* Records request for store motion of memory reference REF from LOOP.
917 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
918 these references are rewritten by a new temporary variable.
919 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
920 The initialization of the temporary variable is put to the preheader
921 of the loop, and assignments to the reference from the temporary variable
922 are emitted to exits. */
925 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
926 struct mem_ref_loc
*mem_refs
)
928 struct mem_ref_loc
*aref
;
932 struct fmt_data fmt_data
;
934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
936 fprintf (dump_file
, "Executing store motion of ");
937 print_generic_expr (dump_file
, ref
, 0);
938 fprintf (dump_file
, " from loop %d\n", loop
->num
);
941 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
943 fmt_data
.loop
= loop
;
944 fmt_data
.orig_loop
= loop
;
945 for_each_index (&ref
, force_move_till
, &fmt_data
);
947 rewrite_mem_refs (tmp_var
, mem_refs
);
948 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
949 if (LIM_DATA (aref
->stmt
))
950 LIM_DATA (aref
->stmt
)->sm_done
= true;
952 /* Emit the load & stores. */
953 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
954 get_stmt_ann (load
)->aux
= xcalloc (1, sizeof (struct lim_aux_data
));
955 LIM_DATA (load
)->max_loop
= loop
;
956 LIM_DATA (load
)->tgt_loop
= loop
;
958 /* Put this into the latch, so that we are sure it will be processed after
960 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
962 for (i
= 0; i
< n_exits
; i
++)
964 store
= build (MODIFY_EXPR
, void_type_node
,
965 unshare_expr (ref
), tmp_var
);
966 bsi_insert_on_edge (exits
[i
], store
);
970 /* Check whether memory reference REF can be hoisted out of the LOOP. If this
971 is true, prepare the statements that load the value of the memory reference
972 to a temporary variable in the loop preheader, store it back on the loop
973 exits, and replace all the references inside LOOP by this temporary variable.
974 LOOP has N_EXITS stored in EXITS. CLOBBERED_VOPS is the bitmap of virtual
975 operands that are clobbered by a call or accessed through multiple references
979 determine_lsm_ref (struct loop
*loop
, edge
*exits
, unsigned n_exits
,
980 bitmap clobbered_vops
, struct mem_ref
*ref
)
982 struct mem_ref_loc
*aref
;
983 struct loop
*must_exec
;
985 /* In case the memory is not stored to, there is nothing for SM to do. */
989 /* If the reference is aliased with any different ref, or killed by call
990 in function, then fail. */
991 if (bitmap_intersect_p (ref
->vops
, clobbered_vops
))
994 if (tree_could_trap_p (ref
->mem
))
996 /* If the memory access is unsafe (i.e. it might trap), ensure that some
997 of the statements in that it occurs is always executed when the loop
998 is entered. This way we know that by moving the load from the
999 reference out of the loop we will not cause the error that would not
1002 TODO -- in fact we would like to check for anticipability of the
1003 reference, i.e. that on each path from loop entry to loop exit at
1004 least one of the statements containing the memory reference is
1007 for (aref
= ref
->locs
; aref
; aref
= aref
->next
)
1009 if (!LIM_DATA (aref
->stmt
))
1012 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1016 if (must_exec
== loop
1017 || flow_loop_nested_p (must_exec
, loop
))
1025 schedule_sm (loop
, exits
, n_exits
, ref
->mem
, ref
->locs
);
1028 /* Hoists memory references MEM_REFS out of LOOP. CLOBBERED_VOPS is the list
1029 of vops clobbered by call in loop or accessed by multiple memory references.
1030 EXITS is the list of N_EXITS exit edges of the LOOP. */
1033 hoist_memory_references (struct loop
*loop
, struct mem_ref
*mem_refs
,
1034 bitmap clobbered_vops
, edge
*exits
, unsigned n_exits
)
1036 struct mem_ref
*ref
;
1038 for (ref
= mem_refs
; ref
; ref
= ref
->next
)
1039 determine_lsm_ref (loop
, exits
, n_exits
, clobbered_vops
, ref
);
1042 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1043 for a store motion optimization (i.e. whether we can insert statement
1047 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1052 for (i
= 0; i
< n_exits
; i
++)
1053 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1059 /* A hash function for struct mem_ref object OBJ. */
1062 memref_hash (const void *obj
)
1064 const struct mem_ref
*mem
= obj
;
1069 /* An equality function for struct mem_ref object OBJ1 with
1070 memory reference OBJ2. */
1073 memref_eq (const void *obj1
, const void *obj2
)
1075 const struct mem_ref
*mem1
= obj1
;
1077 return operand_equal_p (mem1
->mem
, (tree
) obj2
, 0);
1080 /* Gathers memory references in statement STMT in LOOP, storing the
1081 information about them in MEM_REFS hash table. Note vops accessed through
1082 unrecognized statements in CLOBBERED_VOPS. The newly created references
1083 are also stored to MEM_REF_LIST. */
1086 gather_mem_refs_stmt (struct loop
*loop
, htab_t mem_refs
,
1087 bitmap clobbered_vops
, tree stmt
,
1088 struct mem_ref
**mem_ref_list
)
1090 tree
*lhs
, *rhs
, *mem
= NULL
;
1093 struct mem_ref
*ref
= NULL
;
1098 if (ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1101 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
1102 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1105 lhs
= &TREE_OPERAND (stmt
, 0);
1106 rhs
= &TREE_OPERAND (stmt
, 1);
1108 if (TREE_CODE (*lhs
) == SSA_NAME
)
1110 if (!is_gimple_addressable (*rhs
))
1116 else if (TREE_CODE (*rhs
) == SSA_NAME
1117 || is_gimple_min_invariant (*rhs
))
1125 /* If we cannot create an SSA name for the result, give up. */
1126 if (!is_gimple_reg_type (TREE_TYPE (*mem
))
1127 || TREE_THIS_VOLATILE (*mem
))
1130 /* If we cannot move the reference out of the loop, fail. */
1131 if (!for_each_index (mem
, may_move_till
, loop
))
1134 hash
= iterative_hash_expr (*mem
, 0);
1135 slot
= htab_find_slot_with_hash (mem_refs
, *mem
, hash
, INSERT
);
1141 ref
= xmalloc (sizeof (struct mem_ref
));
1145 ref
->is_stored
= false;
1146 ref
->vops
= BITMAP_ALLOC (NULL
);
1147 ref
->next
= *mem_ref_list
;
1148 *mem_ref_list
= ref
;
1151 ref
->is_stored
|= is_stored
;
1153 FOR_EACH_SSA_TREE_OPERAND (vname
, stmt
, oi
,
1154 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1156 bitmap_set_bit (ref
->vops
,
1157 var_ann (SSA_NAME_VAR (vname
))->uid
);
1159 record_mem_ref_loc (&ref
->locs
, stmt
, mem
);
1163 FOR_EACH_SSA_TREE_OPERAND (vname
, stmt
, oi
,
1164 SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
1166 bitmap_set_bit (clobbered_vops
,
1167 var_ann (SSA_NAME_VAR (vname
))->uid
);
1171 /* Gathers memory references in LOOP. Notes vops accessed through unrecognized
1172 statements in CLOBBERED_VOPS. The list of the references found by
1173 the function is returned. */
1175 static struct mem_ref
*
1176 gather_mem_refs (struct loop
*loop
, bitmap clobbered_vops
)
1178 basic_block
*body
= get_loop_body (loop
);
1179 block_stmt_iterator bsi
;
1181 struct mem_ref
*mem_ref_list
= NULL
;
1182 htab_t mem_refs
= htab_create (100, memref_hash
, memref_eq
, NULL
);
1184 for (i
= 0; i
< loop
->num_nodes
; i
++)
1186 for (bsi
= bsi_start (body
[i
]); !bsi_end_p (bsi
); bsi_next (&bsi
))
1187 gather_mem_refs_stmt (loop
, mem_refs
, clobbered_vops
, bsi_stmt (bsi
),
1193 htab_delete (mem_refs
);
1194 return mem_ref_list
;
1197 /* Finds the vops accessed by more than one of the memory references described
1198 in MEM_REFS and marks them in CLOBBERED_VOPS. */
1201 find_more_ref_vops (struct mem_ref
*mem_refs
, bitmap clobbered_vops
)
1203 bitmap_head tmp
, all_vops
;
1204 struct mem_ref
*ref
;
1206 bitmap_initialize (&tmp
, &bitmap_default_obstack
);
1207 bitmap_initialize (&all_vops
, &bitmap_default_obstack
);
1209 for (ref
= mem_refs
; ref
; ref
= ref
->next
)
1211 /* The vops that are already in all_vops are accessed by more than
1212 one memory reference. */
1213 bitmap_and (&tmp
, &all_vops
, ref
->vops
);
1214 bitmap_ior_into (clobbered_vops
, &tmp
);
1215 bitmap_clear (&tmp
);
1217 bitmap_ior_into (&all_vops
, ref
->vops
);
1220 bitmap_clear (&all_vops
);
1223 /* Releases the memory occupied by REF. */
1226 free_mem_ref (struct mem_ref
*ref
)
1228 free_mem_ref_locs (ref
->locs
);
1229 BITMAP_FREE (ref
->vops
);
1233 /* Releases the memory occupied by REFS. */
1236 free_mem_refs (struct mem_ref
*refs
)
1238 struct mem_ref
*ref
, *next
;
1240 for (ref
= refs
; ref
; ref
= next
)
1247 /* Try to perform store motion for all memory references modified inside
1251 determine_lsm_loop (struct loop
*loop
)
1254 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1255 bitmap clobbered_vops
;
1256 struct mem_ref
*mem_refs
;
1258 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1264 /* Find the memory references in LOOP. */
1265 clobbered_vops
= BITMAP_ALLOC (NULL
);
1266 mem_refs
= gather_mem_refs (loop
, clobbered_vops
);
1268 /* Find the vops that are used for more than one reference. */
1269 find_more_ref_vops (mem_refs
, clobbered_vops
);
1271 /* Hoist all suitable memory references. */
1272 hoist_memory_references (loop
, mem_refs
, clobbered_vops
, exits
, n_exits
);
1274 free_mem_refs (mem_refs
);
1276 BITMAP_FREE (clobbered_vops
);
1279 /* Try to perform store motion for all memory references modified inside
1283 determine_lsm (struct loops
*loops
)
1287 if (!loops
->tree_root
->inner
)
1290 /* Pass the loops from the outermost and perform the store motion as
1293 loop
= loops
->tree_root
->inner
;
1296 determine_lsm_loop (loop
);
1306 if (loop
== loops
->tree_root
)
1308 loop_commit_inserts ();
1316 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1317 for each such basic block bb records the outermost loop for that execution
1318 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1319 blocks that contain a nonpure call. */
1322 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1324 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1327 struct loop
*inn_loop
= loop
;
1329 if (!loop
->header
->aux
)
1331 bbs
= get_loop_body_in_dom_order (loop
);
1333 for (i
= 0; i
< loop
->num_nodes
; i
++)
1338 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1341 if (TEST_BIT (contains_call
, bb
->index
))
1344 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1345 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1350 /* A loop might be infinite (TODO use simple loop analysis
1351 to disprove this if possible). */
1352 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1355 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1358 if (bb
->loop_father
->header
== bb
)
1360 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1363 /* In a loop that is always entered we may proceed anyway.
1364 But record that we entered it and stop once we leave it. */
1365 inn_loop
= bb
->loop_father
;
1372 if (last
== loop
->header
)
1374 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1380 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1381 fill_always_executed_in (loop
, contains_call
);
1384 /* Compute the global information needed by the loop invariant motion pass.
1385 LOOPS is the loop tree. */
1388 tree_ssa_lim_initialize (struct loops
*loops
)
1390 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1391 block_stmt_iterator bsi
;
1395 sbitmap_zero (contains_call
);
1398 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1400 if (nonpure_call_p (bsi_stmt (bsi
)))
1404 if (!bsi_end_p (bsi
))
1405 SET_BIT (contains_call
, bb
->index
);
1408 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1409 fill_always_executed_in (loop
, contains_call
);
1411 sbitmap_free (contains_call
);
1414 /* Cleans up after the invariant motion pass. */
1417 tree_ssa_lim_finalize (void)
1427 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1428 i.e. those that are likely to be win regardless of the register pressure. */
1431 tree_ssa_lim (struct loops
*loops
)
1433 tree_ssa_lim_initialize (loops
);
1435 /* For each statement determine the outermost loop in that it is
1436 invariant and cost for computing the invariant. */
1437 determine_invariantness ();
1439 /* For each memory reference determine whether it is possible to hoist it
1440 out of the loop. Force the necessary invariants to be moved out of the
1442 determine_lsm (loops
);
1444 /* Move the expressions that are expensive enough. */
1445 move_computations ();
1447 tree_ssa_lim_finalize ();