1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
42 /* TODO: Support for predicated code motion. I.e.
53 Where COND and INV are is invariants, but evaluating INV may trap or be
54 invalid from some other reason if !COND. This may be transformed to
64 /* A type for the list of statements that have to be moved in order to be able
65 to hoist an invariant computation. */
73 /* The auxiliary data kept for each statement. */
77 struct loop
*max_loop
; /* The outermost loop in that the statement
80 struct loop
*tgt_loop
; /* The loop out of that we want to move the
83 struct loop
*always_executed_in
;
84 /* The outermost loop for that we are sure
85 the statement is executed if the loop
88 bool sm_done
; /* True iff the store motion for a memory
89 reference in the statement has already
92 unsigned cost
; /* Cost of the computation performed by the
95 struct depend
*depends
; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
102 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
104 : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
106 /* Description of a memory reference for store motion. */
110 tree
*ref
; /* The reference itself. */
111 tree stmt
; /* The statement in that it occurs. */
112 struct mem_ref
*next
; /* Next use in the chain. */
115 /* Minimum cost of an expensive expression. */
116 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
118 /* The outermost loop for that execution of the header guarantees that the
119 block will be executed. */
120 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
122 static unsigned max_stmt_uid
; /* Maximal uid of a statement. Uids to phi
123 nodes are assigned using the versions of
124 ssa names they define. */
126 /* Returns uid of statement STMT. */
129 get_stmt_uid (tree stmt
)
131 if (TREE_CODE (stmt
) == PHI_NODE
)
132 return SSA_NAME_VERSION (PHI_RESULT (stmt
)) + max_stmt_uid
;
134 return stmt_ann (stmt
)->uid
;
137 /* Calls CBCK for each index in memory reference ADDR_P. There are two
138 kinds situations handled; in each of these cases, the memory reference
139 and DATA are passed to the callback:
141 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
142 pass the pointer to the index to the callback.
144 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
145 pointer to addr to the callback.
147 If the callback returns false, the whole search stops and false is returned.
148 Otherwise the function returns true after traversing through the whole
149 reference *ADDR_P. */
152 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
156 for (; ; addr_p
= nxt
)
158 switch (TREE_CODE (*addr_p
))
161 return cbck (*addr_p
, addr_p
, data
);
163 case MISALIGNED_INDIRECT_REF
:
164 case ALIGN_INDIRECT_REF
:
166 nxt
= &TREE_OPERAND (*addr_p
, 0);
167 return cbck (*addr_p
, nxt
, data
);
170 case VIEW_CONVERT_EXPR
:
171 case ARRAY_RANGE_REF
:
174 nxt
= &TREE_OPERAND (*addr_p
, 0);
178 /* If the component has varying offset, it behaves like index
180 idx
= &TREE_OPERAND (*addr_p
, 2);
182 && !cbck (*addr_p
, idx
, data
))
185 nxt
= &TREE_OPERAND (*addr_p
, 0);
189 nxt
= &TREE_OPERAND (*addr_p
, 0);
190 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
206 /* If it is possible to hoist the statement STMT unconditionally,
207 returns MOVE_POSSIBLE.
208 If it is possible to hoist the statement STMT, but we must avoid making
209 it executed if it would not be executed in the original program (e.g.
210 because it may trap), return MOVE_PRESERVE_EXECUTION.
211 Otherwise return MOVE_IMPOSSIBLE. */
214 movement_possibility (tree stmt
)
218 if (flag_unswitch_loops
219 && TREE_CODE (stmt
) == COND_EXPR
)
221 /* If we perform unswitching, force the operands of the invariant
222 condition to be moved out of the loop. */
223 get_stmt_operands (stmt
);
225 return MOVE_POSSIBLE
;
228 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
229 return MOVE_IMPOSSIBLE
;
231 if (stmt_ends_bb_p (stmt
))
232 return MOVE_IMPOSSIBLE
;
234 get_stmt_operands (stmt
);
236 if (stmt_ann (stmt
)->has_volatile_ops
)
237 return MOVE_IMPOSSIBLE
;
239 lhs
= TREE_OPERAND (stmt
, 0);
240 if (TREE_CODE (lhs
) == SSA_NAME
241 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
242 return MOVE_IMPOSSIBLE
;
244 rhs
= TREE_OPERAND (stmt
, 1);
246 if (TREE_SIDE_EFFECTS (rhs
))
247 return MOVE_IMPOSSIBLE
;
249 if (TREE_CODE (lhs
) != SSA_NAME
250 || tree_could_trap_p (rhs
))
251 return MOVE_PRESERVE_EXECUTION
;
253 if (get_call_expr_in (stmt
))
255 /* While pure or const call is guaranteed to have no side effects, we
256 cannot move it arbitrarily. Consider code like
258 char *s = something ();
268 Here the strlen call cannot be moved out of the loop, even though
269 s is invariant. In addition to possibly creating a call with
270 invalid arguments, moving out a function call that is not executed
271 may cause performance regressions in case the call is costly and
272 not executed at all. */
273 return MOVE_PRESERVE_EXECUTION
;
275 return MOVE_POSSIBLE
;
278 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
279 loop to that we could move the expression using DEF if it did not have
280 other operands, i.e. the outermost loop enclosing LOOP in that the value
281 of DEF is invariant. */
284 outermost_invariant_loop (tree def
, struct loop
*loop
)
288 struct loop
*max_loop
;
290 if (TREE_CODE (def
) != SSA_NAME
)
291 return superloop_at_depth (loop
, 1);
293 def_stmt
= SSA_NAME_DEF_STMT (def
);
294 def_bb
= bb_for_stmt (def_stmt
);
296 return superloop_at_depth (loop
, 1);
298 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
300 if (LIM_DATA (def_stmt
) && LIM_DATA (def_stmt
)->max_loop
)
301 max_loop
= find_common_loop (max_loop
,
302 LIM_DATA (def_stmt
)->max_loop
->outer
);
303 if (max_loop
== loop
)
305 max_loop
= superloop_at_depth (loop
, max_loop
->depth
+ 1);
310 /* Returns the outermost superloop of LOOP in that the expression EXPR is
314 outermost_invariant_loop_expr (tree expr
, struct loop
*loop
)
316 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
318 struct loop
*max_loop
= superloop_at_depth (loop
, 1), *aloop
;
320 if (TREE_CODE (expr
) == SSA_NAME
321 || TREE_CODE (expr
) == INTEGER_CST
322 || is_gimple_min_invariant (expr
))
323 return outermost_invariant_loop (expr
, loop
);
325 if (class != tcc_unary
326 && class != tcc_binary
327 && class != tcc_expression
328 && class != tcc_comparison
)
331 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
332 for (i
= 0; i
< nops
; i
++)
334 aloop
= outermost_invariant_loop_expr (TREE_OPERAND (expr
, i
), loop
);
338 if (flow_loop_nested_p (max_loop
, aloop
))
345 /* DATA is a structure containing information associated with a statement
346 inside LOOP. DEF is one of the operands of this statement.
348 Find the outermost loop enclosing LOOP in that value of DEF is invariant
349 and record this in DATA->max_loop field. If DEF itself is defined inside
350 this loop as well (i.e. we need to hoist it out of the loop if we want
351 to hoist the statement represented by DATA), record the statement in that
352 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
353 add the cost of the computation of DEF to the DATA->cost.
355 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
358 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
361 tree def_stmt
= SSA_NAME_DEF_STMT (def
);
362 basic_block def_bb
= bb_for_stmt (def_stmt
);
363 struct loop
*max_loop
;
369 max_loop
= outermost_invariant_loop (def
, loop
);
373 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
374 data
->max_loop
= max_loop
;
376 if (!LIM_DATA (def_stmt
))
380 /* Only add the cost if the statement defining DEF is inside LOOP,
381 i.e. if it is likely that by moving the invariants dependent
382 on it, we will be able to avoid creating a new register for
383 it (since it will be only used in these dependent invariants). */
384 && def_bb
->loop_father
== loop
)
385 data
->cost
+= LIM_DATA (def_stmt
)->cost
;
387 dep
= xmalloc (sizeof (struct depend
));
388 dep
->stmt
= def_stmt
;
389 dep
->next
= data
->depends
;
395 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
396 are just ad-hoc constants. The estimates should be based on target-specific
400 stmt_cost (tree stmt
)
405 /* Always try to create possibilities for unswitching. */
406 if (TREE_CODE (stmt
) == COND_EXPR
)
407 return LIM_EXPENSIVE
;
409 rhs
= TREE_OPERAND (stmt
, 1);
411 /* Hoisting memory references out should almost surely be a win. */
412 if (stmt_references_memory_p (stmt
))
415 switch (TREE_CODE (rhs
))
418 /* We should be hoisting calls if possible. */
420 /* Unless the call is a builtin_constant_p; this always folds to a
421 constant, so moving it is useless. */
422 rhs
= get_callee_fndecl (rhs
);
423 if (DECL_BUILT_IN_CLASS (rhs
) == BUILT_IN_NORMAL
424 && DECL_FUNCTION_CODE (rhs
) == BUILT_IN_CONSTANT_P
)
441 /* Division and multiplication are usually expensive. */
452 /* Determine the outermost loop to that it is possible to hoist a statement
453 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
454 the outermost loop in that the value computed by STMT is invariant.
455 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
456 we preserve the fact whether STMT is executed. It also fills other related
457 information to LIM_DATA (STMT).
459 The function returns false if STMT cannot be hoisted outside of the loop it
460 is defined in, and true otherwise. */
463 determine_max_movement (tree stmt
, bool must_preserve_exec
)
465 basic_block bb
= bb_for_stmt (stmt
);
466 struct loop
*loop
= bb
->loop_father
;
468 struct lim_aux_data
*lim_data
= LIM_DATA (stmt
);
472 if (must_preserve_exec
)
473 level
= ALWAYS_EXECUTED_IN (bb
);
475 level
= superloop_at_depth (loop
, 1);
476 lim_data
->max_loop
= level
;
478 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
479 if (!add_dependency (val
, lim_data
, loop
, true))
482 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
| SSA_OP_VIRTUAL_KILLS
)
483 if (!add_dependency (val
, lim_data
, loop
, false))
486 lim_data
->cost
+= stmt_cost (stmt
);
491 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
492 and that one of the operands of this statement is computed by STMT.
493 Ensure that STMT (together with all the statements that define its
494 operands) is hoisted at least out of the loop LEVEL. */
497 set_level (tree stmt
, struct loop
*orig_loop
, struct loop
*level
)
499 struct loop
*stmt_loop
= bb_for_stmt (stmt
)->loop_father
;
502 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
503 if (LIM_DATA (stmt
) && LIM_DATA (stmt
)->tgt_loop
)
504 stmt_loop
= find_common_loop (stmt_loop
,
505 LIM_DATA (stmt
)->tgt_loop
->outer
);
506 if (flow_loop_nested_p (stmt_loop
, level
))
509 gcc_assert (LIM_DATA (stmt
));
510 gcc_assert (level
== LIM_DATA (stmt
)->max_loop
511 || flow_loop_nested_p (LIM_DATA (stmt
)->max_loop
, level
));
513 LIM_DATA (stmt
)->tgt_loop
= level
;
514 for (dep
= LIM_DATA (stmt
)->depends
; dep
; dep
= dep
->next
)
515 set_level (dep
->stmt
, orig_loop
, level
);
518 /* Determines an outermost loop from that we want to hoist the statement STMT.
519 For now we chose the outermost possible loop. TODO -- use profiling
520 information to set it more sanely. */
523 set_profitable_level (tree stmt
)
525 set_level (stmt
, bb_for_stmt (stmt
)->loop_father
, LIM_DATA (stmt
)->max_loop
);
528 /* Returns true if STMT is not a pure call. */
531 nonpure_call_p (tree stmt
)
533 tree call
= get_call_expr_in (stmt
);
538 return TREE_SIDE_EFFECTS (call
) != 0;
541 /* Releases the memory occupied by DATA. */
544 free_lim_aux_data (struct lim_aux_data
*data
)
546 struct depend
*dep
, *next
;
548 for (dep
= data
->depends
; dep
; dep
= next
)
556 /* Determine the outermost loops in that statements in basic block BB are
557 invariant, and record them to the LIM_DATA associated with the statements.
558 Callback for walk_dominator_tree. */
561 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
565 block_stmt_iterator bsi
;
567 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
568 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
570 if (!bb
->loop_father
->outer
)
573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
574 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
575 bb
->index
, bb
->loop_father
->num
, bb
->loop_father
->depth
);
577 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
579 stmt
= bsi_stmt (bsi
);
581 pos
= movement_possibility (stmt
);
582 if (pos
== MOVE_IMPOSSIBLE
)
584 if (nonpure_call_p (stmt
))
592 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
593 to be hoisted out of loop, saving expensive divide. */
594 if (pos
== MOVE_POSSIBLE
595 && (rhs
= TREE_OPERAND (stmt
, 1)) != NULL
596 && TREE_CODE (rhs
) == RDIV_EXPR
597 && flag_unsafe_math_optimizations
598 && outermost_invariant_loop_expr (TREE_OPERAND (rhs
, 1),
599 loop_containing_stmt (stmt
)) != NULL
600 && outermost_invariant_loop_expr (rhs
,
601 loop_containing_stmt (stmt
)) == NULL
)
603 tree lhs
, stmt1
, stmt2
, var
, name
;
605 lhs
= TREE_OPERAND (stmt
, 0);
607 /* stmt must be MODIFY_EXPR. */
608 var
= create_tmp_var (TREE_TYPE (rhs
), "reciptmp");
609 add_referenced_tmp_var (var
);
611 stmt1
= build2 (MODIFY_EXPR
, void_type_node
, var
,
612 build2 (RDIV_EXPR
, TREE_TYPE (rhs
),
613 build_real (TREE_TYPE (rhs
), dconst1
),
614 TREE_OPERAND (rhs
, 1)));
615 name
= make_ssa_name (var
, stmt1
);
616 TREE_OPERAND (stmt1
, 0) = name
;
617 stmt2
= build2 (MODIFY_EXPR
, void_type_node
, lhs
,
618 build2 (MULT_EXPR
, TREE_TYPE (rhs
),
619 name
, TREE_OPERAND (rhs
, 0)));
621 /* Replace division stmt with reciprocal and multiply stmts.
622 The multiply stmt is not invariant, so update iterator
623 and avoid rescanning. */
624 bsi_replace (&bsi
, stmt1
, true);
625 get_stmt_operands (stmt1
); /* Should not be necessary. */
626 bsi_insert_after (&bsi
, stmt2
, BSI_NEW_STMT
);
627 SSA_NAME_DEF_STMT (lhs
) = stmt2
;
629 /* Continue processing with invariant reciprocal statment. */
633 stmt_ann (stmt
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
634 LIM_DATA (stmt
)->always_executed_in
= outermost
;
636 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
639 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
641 LIM_DATA (stmt
)->max_loop
= NULL
;
645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
647 print_generic_stmt_indented (dump_file
, stmt
, 0, 2);
648 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
649 LIM_DATA (stmt
)->max_loop
->depth
,
650 LIM_DATA (stmt
)->cost
);
653 if (LIM_DATA (stmt
)->cost
>= LIM_EXPENSIVE
)
654 set_profitable_level (stmt
);
658 /* For each statement determines the outermost loop in that it is invariant,
659 statements on whose motion it depends and the cost of the computation.
660 This information is stored to the LIM_DATA structure associated with
664 determine_invariantness (void)
666 struct dom_walk_data walk_data
;
668 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
669 walk_data
.before_dom_children_before_stmts
= determine_invariantness_stmt
;
671 init_walk_dominator_tree (&walk_data
);
672 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
673 fini_walk_dominator_tree (&walk_data
);
676 /* Commits edge insertions and updates loop structures. */
679 loop_commit_inserts (void)
681 unsigned old_last_basic_block
, i
;
684 old_last_basic_block
= last_basic_block
;
685 bsi_commit_edge_inserts ();
686 for (i
= old_last_basic_block
; i
< (unsigned) last_basic_block
; i
++)
688 bb
= BASIC_BLOCK (i
);
690 find_common_loop (single_pred (bb
)->loop_father
,
691 single_succ (bb
)->loop_father
));
695 /* Hoist the statements in basic block BB out of the loops prescribed by
696 data stored in LIM_DATA structures associated with each statement. Callback
697 for walk_dominator_tree. */
700 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
704 block_stmt_iterator bsi
;
708 if (!bb
->loop_father
->outer
)
711 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
713 stmt
= bsi_stmt (bsi
);
715 if (!LIM_DATA (stmt
))
721 cost
= LIM_DATA (stmt
)->cost
;
722 level
= LIM_DATA (stmt
)->tgt_loop
;
723 free_lim_aux_data (LIM_DATA (stmt
));
724 stmt_ann (stmt
)->common
.aux
= NULL
;
732 /* We do not really want to move conditionals out of the loop; we just
733 placed it here to force its operands to be moved if necessary. */
734 if (TREE_CODE (stmt
) == COND_EXPR
)
737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
739 fprintf (dump_file
, "Moving statement\n");
740 print_generic_stmt (dump_file
, stmt
, 0);
741 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
744 bsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
749 /* Hoist the statements out of the loops prescribed by data stored in
750 LIM_DATA structures associated with each statement.*/
753 move_computations (void)
755 struct dom_walk_data walk_data
;
757 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
758 walk_data
.before_dom_children_before_stmts
= move_computations_stmt
;
760 init_walk_dominator_tree (&walk_data
);
761 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
762 fini_walk_dominator_tree (&walk_data
);
764 loop_commit_inserts ();
766 if (need_ssa_update_p ())
767 update_ssa (TODO_update_ssa
);
769 /* The movement of LI code may cause violation of loop closed SSA
770 form invariants. TODO -- avoid these rewrites completely.
771 Information in virtual phi nodes is sufficient for it. */
772 rewrite_into_loop_closed_ssa (NULL
);
775 /* Checks whether the statement defining variable *INDEX can be hoisted
776 out of the loop passed in DATA. Callback for for_each_index. */
779 may_move_till (tree ref
, tree
*index
, void *data
)
781 struct loop
*loop
= data
, *max_loop
;
783 /* If REF is an array reference, check also that the step and the lower
784 bound is invariant in LOOP. */
785 if (TREE_CODE (ref
) == ARRAY_REF
)
787 tree step
= array_ref_element_size (ref
);
788 tree lbound
= array_ref_low_bound (ref
);
790 max_loop
= outermost_invariant_loop_expr (step
, loop
);
794 max_loop
= outermost_invariant_loop_expr (lbound
, loop
);
799 max_loop
= outermost_invariant_loop (*index
, loop
);
806 /* Forces statements defining (invariant) SSA names in expression EXPR to be
807 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
810 force_move_till_expr (tree expr
, struct loop
*orig_loop
, struct loop
*loop
)
812 enum tree_code_class
class = TREE_CODE_CLASS (TREE_CODE (expr
));
815 if (TREE_CODE (expr
) == SSA_NAME
)
817 tree stmt
= SSA_NAME_DEF_STMT (expr
);
818 if (IS_EMPTY_STMT (stmt
))
821 set_level (stmt
, orig_loop
, loop
);
825 if (class != tcc_unary
826 && class != tcc_binary
827 && class != tcc_expression
828 && class != tcc_comparison
)
831 nops
= TREE_CODE_LENGTH (TREE_CODE (expr
));
832 for (i
= 0; i
< nops
; i
++)
833 force_move_till_expr (TREE_OPERAND (expr
, i
), orig_loop
, loop
);
836 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
837 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
843 struct loop
*orig_loop
;
847 force_move_till (tree ref
, tree
*index
, void *data
)
850 struct fmt_data
*fmt_data
= data
;
852 if (TREE_CODE (ref
) == ARRAY_REF
)
854 tree step
= array_ref_element_size (ref
);
855 tree lbound
= array_ref_low_bound (ref
);
857 force_move_till_expr (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
858 force_move_till_expr (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
861 if (TREE_CODE (*index
) != SSA_NAME
)
864 stmt
= SSA_NAME_DEF_STMT (*index
);
865 if (IS_EMPTY_STMT (stmt
))
868 set_level (stmt
, fmt_data
->orig_loop
, fmt_data
->loop
);
873 /* Records memory reference *REF (that occurs in statement STMT)
874 to the list MEM_REFS. */
877 record_mem_ref (struct mem_ref
**mem_refs
, tree stmt
, tree
*ref
)
879 struct mem_ref
*aref
= xmalloc (sizeof (struct mem_ref
));
884 aref
->next
= *mem_refs
;
888 /* Releases list of memory references MEM_REFS. */
891 free_mem_refs (struct mem_ref
*mem_refs
)
898 mem_refs
= mem_refs
->next
;
903 /* If VAR is defined in LOOP and the statement it is defined in does not belong
904 to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
908 maybe_queue_var (tree var
, struct loop
*loop
,
909 sbitmap seen
, tree
*queue
, unsigned *in_queue
)
911 tree stmt
= SSA_NAME_DEF_STMT (var
);
912 basic_block def_bb
= bb_for_stmt (stmt
);
915 || !flow_bb_inside_loop_p (loop
, def_bb
)
916 || TEST_BIT (seen
, get_stmt_uid (stmt
)))
919 SET_BIT (seen
, get_stmt_uid (stmt
));
920 queue
[(*in_queue
)++] = stmt
;
923 /* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
924 Otherwise return true if the memory reference *OP is equal to COMMON_REF.
925 Record the reference OP to list MEM_REFS. STMT is the statement in that
926 the reference occurs. */
930 struct mem_ref
**mem_refs
;
936 fem_single_reachable_address (tree
*op
, void *data
)
938 struct sra_data
*sra_data
= data
;
940 if (sra_data
->common_ref
941 && !operand_equal_p (*op
, sra_data
->common_ref
, 0))
943 sra_data
->common_ref
= *op
;
945 record_mem_ref (sra_data
->mem_refs
, sra_data
->stmt
, op
);
949 /* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
950 is passed to the CALLBACK as well. The traversal stops if CALLBACK
951 returns false, for_each_memref then returns false as well. Otherwise
952 for_each_memref returns true. */
955 for_each_memref (tree stmt
, bool (*callback
)(tree
*, void *), void *data
)
959 if (TREE_CODE (stmt
) == RETURN_EXPR
)
960 stmt
= TREE_OPERAND (stmt
, 1);
962 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
964 op
= &TREE_OPERAND (stmt
, 0);
965 if (TREE_CODE (*op
) != SSA_NAME
966 && !callback (op
, data
))
969 op
= &TREE_OPERAND (stmt
, 1);
970 if (TREE_CODE (*op
) != SSA_NAME
971 && is_gimple_lvalue (*op
)
972 && !callback (op
, data
))
975 stmt
= TREE_OPERAND (stmt
, 1);
978 if (TREE_CODE (stmt
) == WITH_SIZE_EXPR
)
979 stmt
= TREE_OPERAND (stmt
, 0);
981 if (TREE_CODE (stmt
) == CALL_EXPR
)
985 for (args
= TREE_OPERAND (stmt
, 1); args
; args
= TREE_CHAIN (args
))
987 op
= &TREE_VALUE (args
);
989 if (TREE_CODE (*op
) != SSA_NAME
990 && is_gimple_lvalue (*op
)
991 && !callback (op
, data
))
999 /* Determine whether all memory references inside the LOOP that correspond
1000 to virtual ssa names defined in statement STMT are equal.
1001 If so, store the list of the references to MEM_REFS, and return one
1002 of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
1003 *SEEN_CALL_STMT is set to true if the virtual operands suggest
1004 that the reference might be clobbered by a call inside the LOOP. */
1007 single_reachable_address (struct loop
*loop
, tree stmt
,
1008 struct mem_ref
**mem_refs
,
1009 bool *seen_call_stmt
)
1011 unsigned max_uid
= max_stmt_uid
+ num_ssa_names
;
1012 tree
*queue
= xmalloc (sizeof (tree
) * max_uid
);
1013 sbitmap seen
= sbitmap_alloc (max_uid
);
1014 unsigned in_queue
= 1;
1016 struct sra_data sra_data
;
1020 imm_use_iterator imm_iter
;
1021 use_operand_p use_p
;
1023 sbitmap_zero (seen
);
1026 sra_data
.mem_refs
= mem_refs
;
1027 sra_data
.common_ref
= NULL_TREE
;
1030 SET_BIT (seen
, get_stmt_uid (stmt
));
1031 *seen_call_stmt
= false;
1035 stmt
= queue
[--in_queue
];
1036 sra_data
.stmt
= stmt
;
1039 && LIM_DATA (stmt
)->sm_done
)
1042 switch (TREE_CODE (stmt
))
1047 if (!for_each_memref (stmt
, fem_single_reachable_address
,
1051 /* If this is a function that may depend on the memory location,
1052 record the fact. We cannot directly refuse call clobbered
1053 operands here, since sra_data.common_ref did not have
1055 call
= get_call_expr_in (stmt
);
1057 && !(call_expr_flags (call
) & ECF_CONST
))
1058 *seen_call_stmt
= true;
1060 /* Traverse also definitions of the VUSES (there may be other
1061 distinct from the one we used to get to this statement). */
1062 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
1063 maybe_queue_var (val
, loop
, seen
, queue
, &in_queue
);
1068 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (stmt
); i
++)
1069 if (TREE_CODE (PHI_ARG_DEF (stmt
, i
)) == SSA_NAME
)
1070 maybe_queue_var (PHI_ARG_DEF (stmt
, i
), loop
,
1071 seen
, queue
, &in_queue
);
1078 /* Find uses of virtual names. */
1079 if (TREE_CODE (stmt
) == PHI_NODE
)
1081 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (stmt
))))
1082 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, PHI_RESULT (stmt
))
1084 tree imm_stmt
= USE_STMT (use_p
);
1086 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1089 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1092 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1094 queue
[in_queue
++] = imm_stmt
;
1098 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
1099 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
1101 tree imm_stmt
= USE_STMT (use_p
);
1103 if (TEST_BIT (seen
, get_stmt_uid (imm_stmt
)))
1106 if (!flow_bb_inside_loop_p (loop
, bb_for_stmt (imm_stmt
)))
1109 SET_BIT (seen
, get_stmt_uid (imm_stmt
));
1111 queue
[in_queue
++] = imm_stmt
;
1116 sbitmap_free (seen
);
1118 return sra_data
.common_ref
;
1121 free_mem_refs (*mem_refs
);
1124 sbitmap_free (seen
);
1129 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR. */
1132 rewrite_mem_refs (tree tmp_var
, struct mem_ref
*mem_refs
)
1137 for (; mem_refs
; mem_refs
= mem_refs
->next
)
1139 FOR_EACH_SSA_TREE_OPERAND (var
, mem_refs
->stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1140 mark_sym_for_renaming (SSA_NAME_VAR (var
));
1142 *mem_refs
->ref
= tmp_var
;
1143 update_stmt (mem_refs
->stmt
);
1147 /* Records request for store motion of memory reference REF from LOOP.
1148 MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1149 these references are rewritten by a new temporary variable.
1150 Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1151 The initialization of the temporary variable is put to the preheader
1152 of the loop, and assignments to the reference from the temporary variable
1153 are emitted to exits. */
1156 schedule_sm (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree ref
,
1157 struct mem_ref
*mem_refs
)
1159 struct mem_ref
*aref
;
1163 struct fmt_data fmt_data
;
1165 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1167 fprintf (dump_file
, "Executing store motion of ");
1168 print_generic_expr (dump_file
, ref
, 0);
1169 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1172 tmp_var
= make_rename_temp (TREE_TYPE (ref
), "lsm_tmp");
1174 fmt_data
.loop
= loop
;
1175 fmt_data
.orig_loop
= loop
;
1176 for_each_index (&ref
, force_move_till
, &fmt_data
);
1178 rewrite_mem_refs (tmp_var
, mem_refs
);
1179 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1180 if (LIM_DATA (aref
->stmt
))
1181 LIM_DATA (aref
->stmt
)->sm_done
= true;
1183 /* Emit the load & stores. */
1184 load
= build (MODIFY_EXPR
, void_type_node
, tmp_var
, ref
);
1185 get_stmt_ann (load
)->common
.aux
= xcalloc (1, sizeof (struct lim_aux_data
));
1186 LIM_DATA (load
)->max_loop
= loop
;
1187 LIM_DATA (load
)->tgt_loop
= loop
;
1189 /* Put this into the latch, so that we are sure it will be processed after
1190 all dependencies. */
1191 bsi_insert_on_edge (loop_latch_edge (loop
), load
);
1193 for (i
= 0; i
< n_exits
; i
++)
1195 store
= build (MODIFY_EXPR
, void_type_node
,
1196 unshare_expr (ref
), tmp_var
);
1197 bsi_insert_on_edge (exits
[i
], store
);
1201 /* Returns true if REF may be clobbered by calls. */
1204 is_call_clobbered_ref (tree ref
)
1207 HOST_WIDE_INT offset
, size
;
1212 if (TREE_CODE (sref
) == COMPONENT_REF
1213 && (sref
= okay_component_ref_for_subvars (sref
, &offset
, &size
)))
1215 svars
= get_subvars_for_var (sref
);
1216 for (sv
= svars
; sv
; sv
= sv
->next
)
1218 if (overlap_subvar (offset
, size
, sv
, NULL
)
1219 && is_call_clobbered (sv
->var
))
1224 base
= get_base_address (ref
);
1230 if (var_can_have_subvars (base
)
1231 && (svars
= get_subvars_for_var (base
)))
1233 for (sv
= svars
; sv
; sv
= sv
->next
)
1234 if (is_call_clobbered (sv
->var
))
1239 return is_call_clobbered (base
);
1242 if (INDIRECT_REF_P (base
))
1244 /* Check whether the alias tags associated with the pointer
1245 are call clobbered. */
1246 tree ptr
= TREE_OPERAND (base
, 0);
1247 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1248 tree nmt
= (pi
) ? pi
->name_mem_tag
: NULL_TREE
;
1249 tree tmt
= var_ann (SSA_NAME_VAR (ptr
))->type_mem_tag
;
1251 if ((nmt
&& is_call_clobbered (nmt
))
1252 || (tmt
&& is_call_clobbered (tmt
)))
1261 /* Determine whether all memory references inside LOOP corresponding to the
1262 virtual ssa name REG are equal to each other, and whether the address of
1263 this common reference can be hoisted outside of the loop. If this is true,
1264 prepare the statements that load the value of the memory reference to a
1265 temporary variable in the loop preheader, store it back on the loop exits,
1266 and replace all the references inside LOOP by this temporary variable.
1267 LOOP has N_EXITS stored in EXITS. */
1270 determine_lsm_reg (struct loop
*loop
, edge
*exits
, unsigned n_exits
, tree reg
)
1273 struct mem_ref
*mem_refs
, *aref
;
1274 struct loop
*must_exec
;
1277 if (is_gimple_reg (reg
))
1280 ref
= single_reachable_address (loop
, SSA_NAME_DEF_STMT (reg
), &mem_refs
,
1285 /* If we cannot create a ssa name for the result, give up. */
1286 if (!is_gimple_reg_type (TREE_TYPE (ref
))
1287 || TREE_THIS_VOLATILE (ref
))
1290 /* If there is a call that may use the location, give up as well. */
1292 && is_call_clobbered_ref (ref
))
1295 if (!for_each_index (&ref
, may_move_till
, loop
))
1298 if (tree_could_trap_p (ref
))
1300 /* If the memory access is unsafe (i.e. it might trap), ensure that some
1301 of the statements in that it occurs is always executed when the loop
1302 is entered. This way we know that by moving the load from the
1303 reference out of the loop we will not cause the error that would not
1306 TODO -- in fact we would like to check for anticipability of the
1307 reference, i.e. that on each path from loop entry to loop exit at
1308 least one of the statements containing the memory reference is
1311 for (aref
= mem_refs
; aref
; aref
= aref
->next
)
1313 if (!LIM_DATA (aref
->stmt
))
1316 must_exec
= LIM_DATA (aref
->stmt
)->always_executed_in
;
1320 if (must_exec
== loop
1321 || flow_loop_nested_p (must_exec
, loop
))
1329 schedule_sm (loop
, exits
, n_exits
, ref
, mem_refs
);
1332 free_mem_refs (mem_refs
);
1335 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1336 for a store motion optimization (i.e. whether we can insert statement
1340 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
, edge
*exits
,
1345 for (i
= 0; i
< n_exits
; i
++)
1346 if (exits
[i
]->flags
& EDGE_ABNORMAL
)
1352 /* Try to perform store motion for all memory references modified inside
1356 determine_lsm_loop (struct loop
*loop
)
1360 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1362 if (!loop_suitable_for_sm (loop
, exits
, n_exits
))
1368 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
1369 determine_lsm_reg (loop
, exits
, n_exits
, PHI_RESULT (phi
));
1374 /* Try to perform store motion for all memory references modified inside
1378 determine_lsm (struct loops
*loops
)
1383 if (!loops
->tree_root
->inner
)
1386 /* Create a UID for each statement in the function. Ordering of the
1387 UIDs is not important for this pass. */
1391 block_stmt_iterator bsi
;
1393 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1394 stmt_ann (bsi_stmt (bsi
))->uid
= max_stmt_uid
++;
1397 /* Pass the loops from the outermost. For each virtual operand loop phi node
1398 check whether all the references inside the loop correspond to a single
1399 address, and if so, move them. */
1401 loop
= loops
->tree_root
->inner
;
1404 determine_lsm_loop (loop
);
1414 if (loop
== loops
->tree_root
)
1416 loop_commit_inserts ();
1424 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1425 for each such basic block bb records the outermost loop for that execution
1426 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
1427 blocks that contain a nonpure call. */
1430 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
1432 basic_block bb
= NULL
, *bbs
, last
= NULL
;
1435 struct loop
*inn_loop
= loop
;
1437 if (!loop
->header
->aux
)
1439 bbs
= get_loop_body_in_dom_order (loop
);
1441 for (i
= 0; i
< loop
->num_nodes
; i
++)
1446 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1449 if (TEST_BIT (contains_call
, bb
->index
))
1452 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1453 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1458 /* A loop might be infinite (TODO use simple loop analysis
1459 to disprove this if possible). */
1460 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1463 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
1466 if (bb
->loop_father
->header
== bb
)
1468 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1471 /* In a loop that is always entered we may proceed anyway.
1472 But record that we entered it and stop once we leave it. */
1473 inn_loop
= bb
->loop_father
;
1480 if (last
== loop
->header
)
1482 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
1488 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
1489 fill_always_executed_in (loop
, contains_call
);
1492 /* Compute the global information needed by the loop invariant motion pass.
1493 LOOPS is the loop tree. */
1496 tree_ssa_lim_initialize (struct loops
*loops
)
1498 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
1499 block_stmt_iterator bsi
;
1503 sbitmap_zero (contains_call
);
1506 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1508 if (nonpure_call_p (bsi_stmt (bsi
)))
1512 if (!bsi_end_p (bsi
))
1513 SET_BIT (contains_call
, bb
->index
);
1516 for (loop
= loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
1517 fill_always_executed_in (loop
, contains_call
);
1519 sbitmap_free (contains_call
);
1522 /* Cleans up after the invariant motion pass. */
1525 tree_ssa_lim_finalize (void)
1535 /* Moves invariants from LOOPS. Only "expensive" invariants are moved out --
1536 i.e. those that are likely to be win regardless of the register pressure. */
1539 tree_ssa_lim (struct loops
*loops
)
1541 tree_ssa_lim_initialize (loops
);
1543 /* For each statement determine the outermost loop in that it is
1544 invariant and cost for computing the invariant. */
1545 determine_invariantness ();
1547 /* For each memory reference determine whether it is possible to hoist it
1548 out of the loop. Force the necessary invariants to be moved out of the
1550 determine_lsm (loops
);
1552 /* Move the expressions that are expensive enough. */
1553 move_computations ();
1555 tree_ssa_lim_finalize ();