1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "tree-flow.h"
33 #include "tree-pass.h"
36 #include "tree-affine.h"
37 #include "pointer-set.h"
38 #include "tree-ssa-propagate.h"
40 /* TODO: Support for predicated code motion. I.e.
51 Where COND and INV are invariants, but evaluating INV may trap or be
52 invalid from some other reason if !COND. This may be transformed to
62 /* A type for the list of statements that have to be moved in order to be able
63 to hoist an invariant computation. */
71 /* The auxiliary data kept for each statement. */
75 struct loop
*max_loop
; /* The outermost loop in that the statement
78 struct loop
*tgt_loop
; /* The loop out of that we want to move the
81 struct loop
*always_executed_in
;
82 /* The outermost loop for that we are sure
83 the statement is executed if the loop
86 unsigned cost
; /* Cost of the computation performed by the
89 struct depend
*depends
; /* List of statements that must be also hoisted
90 out of the loop when this statement is
91 hoisted; i.e. those that define the operands
92 of the statement and are inside of the
96 /* Maps statements to their lim_aux_data. */
98 static struct pointer_map_t
*lim_aux_data_map
;
100 /* Description of a memory reference location. */
102 typedef struct mem_ref_loc
104 tree
*ref
; /* The reference itself. */
105 gimple stmt
; /* The statement in that it occurs. */
108 DEF_VEC_P(mem_ref_loc_p
);
109 DEF_VEC_ALLOC_P(mem_ref_loc_p
, heap
);
111 /* The list of memory reference locations in a loop. */
113 typedef struct mem_ref_locs
115 VEC (mem_ref_loc_p
, heap
) *locs
;
118 DEF_VEC_P(mem_ref_locs_p
);
119 DEF_VEC_ALLOC_P(mem_ref_locs_p
, heap
);
121 /* Description of a memory reference. */
123 typedef struct mem_ref
125 tree mem
; /* The memory itself. */
126 unsigned id
; /* ID assigned to the memory reference
127 (its index in memory_accesses.refs_list) */
128 hashval_t hash
; /* Its hash value. */
129 bitmap stored
; /* The set of loops in that this memory location
131 VEC (mem_ref_locs_p
, heap
) *accesses_in_loop
;
132 /* The locations of the accesses. Vector
133 indexed by the loop number. */
135 /* The following sets are computed on demand. We keep both set and
136 its complement, so that we know whether the information was
137 already computed or not. */
138 bitmap indep_loop
; /* The set of loops in that the memory
139 reference is independent, meaning:
140 If it is stored in the loop, this store
141 is independent on all other loads and
143 If it is only loaded, then it is independent
144 on all stores in the loop. */
145 bitmap dep_loop
; /* The complement of INDEP_LOOP. */
147 bitmap indep_ref
; /* The set of memory references on that
148 this reference is independent. */
149 bitmap dep_ref
; /* The complement of INDEP_REF. */
152 DEF_VEC_P(mem_ref_p
);
153 DEF_VEC_ALLOC_P(mem_ref_p
, heap
);
156 DEF_VEC_ALLOC_P(bitmap
, heap
);
159 DEF_VEC_ALLOC_P(htab_t
, heap
);
161 /* Description of memory accesses in loops. */
165 /* The hash table of memory references accessed in loops. */
168 /* The list of memory references. */
169 VEC (mem_ref_p
, heap
) *refs_list
;
171 /* The set of memory references accessed in each loop. */
172 VEC (bitmap
, heap
) *refs_in_loop
;
174 /* The set of memory references accessed in each loop, including
176 VEC (bitmap
, heap
) *all_refs_in_loop
;
178 /* The set of memory references stored in each loop, including
180 VEC (bitmap
, heap
) *all_refs_stored_in_loop
;
182 /* Cache for expanding memory addresses. */
183 struct pointer_map_t
*ttae_cache
;
186 /* Obstack for the bitmaps in the above data structures. */
187 static bitmap_obstack lim_bitmap_obstack
;
189 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
191 /* Minimum cost of an expensive expression. */
192 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
194 /* The outermost loop for which execution of the header guarantees that the
195 block will be executed. */
196 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
197 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
199 /* Whether the reference was analyzable. */
200 #define MEM_ANALYZABLE(REF) ((REF)->mem != error_mark_node)
202 static struct lim_aux_data
*
203 init_lim_data (gimple stmt
)
205 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
207 *p
= XCNEW (struct lim_aux_data
);
208 return (struct lim_aux_data
*) *p
;
211 static struct lim_aux_data
*
212 get_lim_data (gimple stmt
)
214 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
218 return (struct lim_aux_data
*) *p
;
221 /* Releases the memory occupied by DATA. */
224 free_lim_aux_data (struct lim_aux_data
*data
)
226 struct depend
*dep
, *next
;
228 for (dep
= data
->depends
; dep
; dep
= next
)
237 clear_lim_data (gimple stmt
)
239 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
243 free_lim_aux_data ((struct lim_aux_data
*) *p
);
247 /* Calls CBCK for each index in memory reference ADDR_P. There are two
248 kinds situations handled; in each of these cases, the memory reference
249 and DATA are passed to the callback:
251 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
252 pass the pointer to the index to the callback.
254 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
255 pointer to addr to the callback.
257 If the callback returns false, the whole search stops and false is returned.
258 Otherwise the function returns true after traversing through the whole
259 reference *ADDR_P. */
262 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
266 for (; ; addr_p
= nxt
)
268 switch (TREE_CODE (*addr_p
))
271 return cbck (*addr_p
, addr_p
, data
);
274 nxt
= &TREE_OPERAND (*addr_p
, 0);
275 return cbck (*addr_p
, nxt
, data
);
278 case VIEW_CONVERT_EXPR
:
281 nxt
= &TREE_OPERAND (*addr_p
, 0);
285 /* If the component has varying offset, it behaves like index
287 idx
= &TREE_OPERAND (*addr_p
, 2);
289 && !cbck (*addr_p
, idx
, data
))
292 nxt
= &TREE_OPERAND (*addr_p
, 0);
296 case ARRAY_RANGE_REF
:
297 nxt
= &TREE_OPERAND (*addr_p
, 0);
298 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
315 gcc_assert (is_gimple_min_invariant (*addr_p
));
319 idx
= &TMR_BASE (*addr_p
);
321 && !cbck (*addr_p
, idx
, data
))
323 idx
= &TMR_INDEX (*addr_p
);
325 && !cbck (*addr_p
, idx
, data
))
327 idx
= &TMR_INDEX2 (*addr_p
);
329 && !cbck (*addr_p
, idx
, data
))
339 /* If it is possible to hoist the statement STMT unconditionally,
340 returns MOVE_POSSIBLE.
341 If it is possible to hoist the statement STMT, but we must avoid making
342 it executed if it would not be executed in the original program (e.g.
343 because it may trap), return MOVE_PRESERVE_EXECUTION.
344 Otherwise return MOVE_IMPOSSIBLE. */
347 movement_possibility (gimple stmt
)
350 enum move_pos ret
= MOVE_POSSIBLE
;
352 if (flag_unswitch_loops
353 && gimple_code (stmt
) == GIMPLE_COND
)
355 /* If we perform unswitching, force the operands of the invariant
356 condition to be moved out of the loop. */
357 return MOVE_POSSIBLE
;
360 if (gimple_code (stmt
) == GIMPLE_PHI
361 && gimple_phi_num_args (stmt
) <= 2
362 && !virtual_operand_p (gimple_phi_result (stmt
))
363 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
364 return MOVE_POSSIBLE
;
366 if (gimple_get_lhs (stmt
) == NULL_TREE
)
367 return MOVE_IMPOSSIBLE
;
369 if (gimple_vdef (stmt
))
370 return MOVE_IMPOSSIBLE
;
372 if (stmt_ends_bb_p (stmt
)
373 || gimple_has_volatile_ops (stmt
)
374 || gimple_has_side_effects (stmt
)
375 || stmt_could_throw_p (stmt
))
376 return MOVE_IMPOSSIBLE
;
378 if (is_gimple_call (stmt
))
380 /* While pure or const call is guaranteed to have no side effects, we
381 cannot move it arbitrarily. Consider code like
383 char *s = something ();
393 Here the strlen call cannot be moved out of the loop, even though
394 s is invariant. In addition to possibly creating a call with
395 invalid arguments, moving out a function call that is not executed
396 may cause performance regressions in case the call is costly and
397 not executed at all. */
398 ret
= MOVE_PRESERVE_EXECUTION
;
399 lhs
= gimple_call_lhs (stmt
);
401 else if (is_gimple_assign (stmt
))
402 lhs
= gimple_assign_lhs (stmt
);
404 return MOVE_IMPOSSIBLE
;
406 if (TREE_CODE (lhs
) == SSA_NAME
407 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
408 return MOVE_IMPOSSIBLE
;
410 if (TREE_CODE (lhs
) != SSA_NAME
411 || gimple_could_trap_p (stmt
))
412 return MOVE_PRESERVE_EXECUTION
;
414 /* Non local loads in a transaction cannot be hoisted out. Well,
415 unless the load happens on every path out of the loop, but we
416 don't take this into account yet. */
418 && gimple_in_transaction (stmt
)
419 && gimple_assign_single_p (stmt
))
421 tree rhs
= gimple_assign_rhs1 (stmt
);
422 if (DECL_P (rhs
) && is_global_var (rhs
))
426 fprintf (dump_file
, "Cannot hoist conditional load of ");
427 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
428 fprintf (dump_file
, " because it is in a transaction.\n");
430 return MOVE_IMPOSSIBLE
;
437 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
438 loop to that we could move the expression using DEF if it did not have
439 other operands, i.e. the outermost loop enclosing LOOP in that the value
440 of DEF is invariant. */
443 outermost_invariant_loop (tree def
, struct loop
*loop
)
447 struct loop
*max_loop
;
448 struct lim_aux_data
*lim_data
;
451 return superloop_at_depth (loop
, 1);
453 if (TREE_CODE (def
) != SSA_NAME
)
455 gcc_assert (is_gimple_min_invariant (def
));
456 return superloop_at_depth (loop
, 1);
459 def_stmt
= SSA_NAME_DEF_STMT (def
);
460 def_bb
= gimple_bb (def_stmt
);
462 return superloop_at_depth (loop
, 1);
464 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
466 lim_data
= get_lim_data (def_stmt
);
467 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
468 max_loop
= find_common_loop (max_loop
,
469 loop_outer (lim_data
->max_loop
));
470 if (max_loop
== loop
)
472 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
477 /* DATA is a structure containing information associated with a statement
478 inside LOOP. DEF is one of the operands of this statement.
480 Find the outermost loop enclosing LOOP in that value of DEF is invariant
481 and record this in DATA->max_loop field. If DEF itself is defined inside
482 this loop as well (i.e. we need to hoist it out of the loop if we want
483 to hoist the statement represented by DATA), record the statement in that
484 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
485 add the cost of the computation of DEF to the DATA->cost.
487 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
490 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
493 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
494 basic_block def_bb
= gimple_bb (def_stmt
);
495 struct loop
*max_loop
;
497 struct lim_aux_data
*def_data
;
502 max_loop
= outermost_invariant_loop (def
, loop
);
506 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
507 data
->max_loop
= max_loop
;
509 def_data
= get_lim_data (def_stmt
);
514 /* Only add the cost if the statement defining DEF is inside LOOP,
515 i.e. if it is likely that by moving the invariants dependent
516 on it, we will be able to avoid creating a new register for
517 it (since it will be only used in these dependent invariants). */
518 && def_bb
->loop_father
== loop
)
519 data
->cost
+= def_data
->cost
;
521 dep
= XNEW (struct depend
);
522 dep
->stmt
= def_stmt
;
523 dep
->next
= data
->depends
;
529 /* Returns an estimate for a cost of statement STMT. The values here
530 are just ad-hoc constants, similar to costs for inlining. */
533 stmt_cost (gimple stmt
)
535 /* Always try to create possibilities for unswitching. */
536 if (gimple_code (stmt
) == GIMPLE_COND
537 || gimple_code (stmt
) == GIMPLE_PHI
)
538 return LIM_EXPENSIVE
;
540 /* We should be hoisting calls if possible. */
541 if (is_gimple_call (stmt
))
545 /* Unless the call is a builtin_constant_p; this always folds to a
546 constant, so moving it is useless. */
547 fndecl
= gimple_call_fndecl (stmt
);
549 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
550 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
553 return LIM_EXPENSIVE
;
556 /* Hoisting memory references out should almost surely be a win. */
557 if (gimple_references_memory_p (stmt
))
558 return LIM_EXPENSIVE
;
560 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
563 switch (gimple_assign_rhs_code (stmt
))
566 case WIDEN_MULT_EXPR
:
567 case WIDEN_MULT_PLUS_EXPR
:
568 case WIDEN_MULT_MINUS_EXPR
:
581 /* Division and multiplication are usually expensive. */
582 return LIM_EXPENSIVE
;
586 case WIDEN_LSHIFT_EXPR
:
589 /* Shifts and rotates are usually expensive. */
590 return LIM_EXPENSIVE
;
593 /* Make vector construction cost proportional to the number
595 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
599 /* Whether or not something is wrapped inside a PAREN_EXPR
600 should not change move cost. Nor should an intermediate
601 unpropagated SSA name copy. */
609 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
610 REF is independent. If REF is not independent in LOOP, NULL is returned
614 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
618 if (bitmap_bit_p (ref
->stored
, loop
->num
))
623 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
624 if (!bitmap_bit_p (ref
->stored
, aloop
->num
)
625 && ref_indep_loop_p (aloop
, ref
))
628 if (ref_indep_loop_p (loop
, ref
))
634 /* If there is a simple load or store to a memory reference in STMT, returns
635 the location of the memory reference, and sets IS_STORE according to whether
636 it is a store or load. Otherwise, returns NULL. */
639 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
643 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
644 if (!gimple_assign_single_p (stmt
))
647 lhs
= gimple_assign_lhs_ptr (stmt
);
648 rhs
= gimple_assign_rhs1_ptr (stmt
);
650 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
655 else if (gimple_vdef (stmt
)
656 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
665 /* Returns the memory reference contained in STMT. */
668 mem_ref_in_stmt (gimple stmt
)
671 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
679 hash
= iterative_hash_expr (*mem
, 0);
680 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
682 gcc_assert (ref
!= NULL
);
686 /* From a controlling predicate in DOM determine the arguments from
687 the PHI node PHI that are chosen if the predicate evaluates to
688 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
689 they are non-NULL. Returns true if the arguments can be determined,
690 else return false. */
693 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
694 tree
*true_arg_p
, tree
*false_arg_p
)
696 basic_block bb
= gimple_bb (phi
);
697 edge true_edge
, false_edge
, tem
;
698 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
700 /* We have to verify that one edge into the PHI node is dominated
701 by the true edge of the predicate block and the other edge
702 dominated by the false edge. This ensures that the PHI argument
703 we are going to take is completely determined by the path we
704 take from the predicate block.
705 We can only use BB dominance checks below if the destination of
706 the true/false edges are dominated by their edge, thus only
707 have a single predecessor. */
708 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
709 tem
= EDGE_PRED (bb
, 0);
711 || (single_pred_p (true_edge
->dest
)
712 && (tem
->src
== true_edge
->dest
713 || dominated_by_p (CDI_DOMINATORS
,
714 tem
->src
, true_edge
->dest
))))
715 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
716 else if (tem
== false_edge
717 || (single_pred_p (false_edge
->dest
)
718 && (tem
->src
== false_edge
->dest
719 || dominated_by_p (CDI_DOMINATORS
,
720 tem
->src
, false_edge
->dest
))))
721 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
724 tem
= EDGE_PRED (bb
, 1);
726 || (single_pred_p (true_edge
->dest
)
727 && (tem
->src
== true_edge
->dest
728 || dominated_by_p (CDI_DOMINATORS
,
729 tem
->src
, true_edge
->dest
))))
730 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
731 else if (tem
== false_edge
732 || (single_pred_p (false_edge
->dest
)
733 && (tem
->src
== false_edge
->dest
734 || dominated_by_p (CDI_DOMINATORS
,
735 tem
->src
, false_edge
->dest
))))
736 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
750 /* Determine the outermost loop to that it is possible to hoist a statement
751 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
752 the outermost loop in that the value computed by STMT is invariant.
753 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
754 we preserve the fact whether STMT is executed. It also fills other related
755 information to LIM_DATA (STMT).
757 The function returns false if STMT cannot be hoisted outside of the loop it
758 is defined in, and true otherwise. */
761 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
763 basic_block bb
= gimple_bb (stmt
);
764 struct loop
*loop
= bb
->loop_father
;
766 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
770 if (must_preserve_exec
)
771 level
= ALWAYS_EXECUTED_IN (bb
);
773 level
= superloop_at_depth (loop
, 1);
774 lim_data
->max_loop
= level
;
776 if (gimple_code (stmt
) == GIMPLE_PHI
)
779 unsigned min_cost
= UINT_MAX
;
780 unsigned total_cost
= 0;
781 struct lim_aux_data
*def_data
;
783 /* We will end up promoting dependencies to be unconditionally
784 evaluated. For this reason the PHI cost (and thus the
785 cost we remove from the loop by doing the invariant motion)
786 is that of the cheapest PHI argument dependency chain. */
787 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
789 val
= USE_FROM_PTR (use_p
);
790 if (TREE_CODE (val
) != SSA_NAME
)
792 if (!add_dependency (val
, lim_data
, loop
, false))
794 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
797 min_cost
= MIN (min_cost
, def_data
->cost
);
798 total_cost
+= def_data
->cost
;
802 lim_data
->cost
+= min_cost
;
804 if (gimple_phi_num_args (stmt
) > 1)
806 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
808 if (gsi_end_p (gsi_last_bb (dom
)))
810 cond
= gsi_stmt (gsi_last_bb (dom
));
811 if (gimple_code (cond
) != GIMPLE_COND
)
813 /* Verify that this is an extended form of a diamond and
814 the PHI arguments are completely controlled by the
816 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
819 /* Fold in dependencies and cost of the condition. */
820 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
822 if (!add_dependency (val
, lim_data
, loop
, false))
824 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
826 total_cost
+= def_data
->cost
;
829 /* We want to avoid unconditionally executing very expensive
830 operations. As costs for our dependencies cannot be
831 negative just claim we are not invariand for this case.
832 We also are not sure whether the control-flow inside the
834 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
836 && total_cost
/ min_cost
<= 2))
839 /* Assume that the control-flow in the loop will vanish.
840 ??? We should verify this and not artificially increase
841 the cost if that is not the case. */
842 lim_data
->cost
+= stmt_cost (stmt
);
848 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
849 if (!add_dependency (val
, lim_data
, loop
, true))
852 if (gimple_vuse (stmt
))
854 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
859 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
860 if (!lim_data
->max_loop
)
865 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
867 if (!add_dependency (val
, lim_data
, loop
, false))
873 lim_data
->cost
+= stmt_cost (stmt
);
878 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
879 and that one of the operands of this statement is computed by STMT.
880 Ensure that STMT (together with all the statements that define its
881 operands) is hoisted at least out of the loop LEVEL. */
884 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
886 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
888 struct lim_aux_data
*lim_data
;
890 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
891 lim_data
= get_lim_data (stmt
);
892 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
893 stmt_loop
= find_common_loop (stmt_loop
,
894 loop_outer (lim_data
->tgt_loop
));
895 if (flow_loop_nested_p (stmt_loop
, level
))
898 gcc_assert (level
== lim_data
->max_loop
899 || flow_loop_nested_p (lim_data
->max_loop
, level
));
901 lim_data
->tgt_loop
= level
;
902 for (dep
= lim_data
->depends
; dep
; dep
= dep
->next
)
903 set_level (dep
->stmt
, orig_loop
, level
);
906 /* Determines an outermost loop from that we want to hoist the statement STMT.
907 For now we chose the outermost possible loop. TODO -- use profiling
908 information to set it more sanely. */
911 set_profitable_level (gimple stmt
)
913 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
916 /* Returns true if STMT is a call that has side effects. */
919 nonpure_call_p (gimple stmt
)
921 if (gimple_code (stmt
) != GIMPLE_CALL
)
924 return gimple_has_side_effects (stmt
);
927 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
930 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
932 gimple stmt
, stmt1
, stmt2
;
933 tree name
, lhs
, type
;
935 gimple_stmt_iterator gsi
;
937 stmt
= gsi_stmt (*bsi
);
938 lhs
= gimple_assign_lhs (stmt
);
939 type
= TREE_TYPE (lhs
);
941 real_one
= build_one_cst (type
);
943 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
944 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
, name
, real_one
,
945 gimple_assign_rhs2 (stmt
));
947 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
948 gimple_assign_rhs1 (stmt
));
950 /* Replace division stmt with reciprocal and multiply stmts.
951 The multiply stmt is not invariant, so update iterator
952 and avoid rescanning. */
954 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
955 gsi_replace (&gsi
, stmt2
, true);
957 /* Continue processing with invariant reciprocal statement. */
961 /* Check if the pattern at *BSI is a bittest of the form
962 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
965 rewrite_bittest (gimple_stmt_iterator
*bsi
)
967 gimple stmt
, use_stmt
, stmt1
, stmt2
;
968 tree lhs
, name
, t
, a
, b
;
971 stmt
= gsi_stmt (*bsi
);
972 lhs
= gimple_assign_lhs (stmt
);
974 /* Verify that the single use of lhs is a comparison against zero. */
975 if (TREE_CODE (lhs
) != SSA_NAME
976 || !single_imm_use (lhs
, &use
, &use_stmt
)
977 || gimple_code (use_stmt
) != GIMPLE_COND
)
979 if (gimple_cond_lhs (use_stmt
) != lhs
980 || (gimple_cond_code (use_stmt
) != NE_EXPR
981 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
982 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
985 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
986 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
987 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
990 /* There is a conversion in between possibly inserted by fold. */
991 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
993 t
= gimple_assign_rhs1 (stmt1
);
994 if (TREE_CODE (t
) != SSA_NAME
995 || !has_single_use (t
))
997 stmt1
= SSA_NAME_DEF_STMT (t
);
998 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
1002 /* Verify that B is loop invariant but A is not. Verify that with
1003 all the stmt walking we are still in the same loop. */
1004 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
1005 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
1008 a
= gimple_assign_rhs1 (stmt1
);
1009 b
= gimple_assign_rhs2 (stmt1
);
1011 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
1012 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
1014 gimple_stmt_iterator rsi
;
1017 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
1018 build_int_cst (TREE_TYPE (a
), 1), b
);
1019 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
1020 stmt1
= gimple_build_assign (name
, t
);
1023 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
1024 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
1025 stmt2
= gimple_build_assign (name
, t
);
1027 /* Replace the SSA_NAME we compare against zero. Adjust
1028 the type of zero accordingly. */
1029 SET_USE (use
, name
);
1030 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
1032 /* Don't use gsi_replace here, none of the new assignments sets
1033 the variable originally set in stmt. Move bsi to stmt1, and
1034 then remove the original stmt, so that we get a chance to
1035 retain debug info for it. */
1037 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
1038 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
1039 gsi_remove (&rsi
, true);
1048 /* Determine the outermost loops in that statements in basic block BB are
1049 invariant, and record them to the LIM_DATA associated with the statements.
1050 Callback for walk_dominator_tree. */
1053 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1057 gimple_stmt_iterator bsi
;
1059 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1060 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1061 struct lim_aux_data
*lim_data
;
1063 if (!loop_outer (bb
->loop_father
))
1066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1067 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1068 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1070 /* Look at PHI nodes, but only if there is at most two.
1071 ??? We could relax this further by post-processing the inserted
1072 code and transforming adjacent cond-exprs with the same predicate
1073 to control flow again. */
1074 bsi
= gsi_start_phis (bb
);
1075 if (!gsi_end_p (bsi
)
1076 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1077 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1078 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1080 stmt
= gsi_stmt (bsi
);
1082 pos
= movement_possibility (stmt
);
1083 if (pos
== MOVE_IMPOSSIBLE
)
1086 lim_data
= init_lim_data (stmt
);
1087 lim_data
->always_executed_in
= outermost
;
1089 if (!determine_max_movement (stmt
, false))
1091 lim_data
->max_loop
= NULL
;
1095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1097 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1098 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1099 loop_depth (lim_data
->max_loop
),
1103 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1104 set_profitable_level (stmt
);
1107 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1109 stmt
= gsi_stmt (bsi
);
1111 pos
= movement_possibility (stmt
);
1112 if (pos
== MOVE_IMPOSSIBLE
)
1114 if (nonpure_call_p (stmt
))
1119 /* Make sure to note always_executed_in for stores to make
1120 store-motion work. */
1121 else if (stmt_makes_single_store (stmt
))
1123 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1124 lim_data
->always_executed_in
= outermost
;
1129 if (is_gimple_assign (stmt
)
1130 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1131 == GIMPLE_BINARY_RHS
))
1133 tree op0
= gimple_assign_rhs1 (stmt
);
1134 tree op1
= gimple_assign_rhs2 (stmt
);
1135 struct loop
*ol1
= outermost_invariant_loop (op1
,
1136 loop_containing_stmt (stmt
));
1138 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1139 to be hoisted out of loop, saving expensive divide. */
1140 if (pos
== MOVE_POSSIBLE
1141 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1142 && flag_unsafe_math_optimizations
1143 && !flag_trapping_math
1145 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1146 stmt
= rewrite_reciprocal (&bsi
);
1148 /* If the shift count is invariant, convert (A >> B) & 1 to
1149 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1150 saving an expensive shift. */
1151 if (pos
== MOVE_POSSIBLE
1152 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1153 && integer_onep (op1
)
1154 && TREE_CODE (op0
) == SSA_NAME
1155 && has_single_use (op0
))
1156 stmt
= rewrite_bittest (&bsi
);
1159 lim_data
= init_lim_data (stmt
);
1160 lim_data
->always_executed_in
= outermost
;
1162 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1165 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1167 lim_data
->max_loop
= NULL
;
1171 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1173 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1174 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1175 loop_depth (lim_data
->max_loop
),
1179 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1180 set_profitable_level (stmt
);
1184 /* For each statement determines the outermost loop in that it is invariant,
1185 statements on whose motion it depends and the cost of the computation.
1186 This information is stored to the LIM_DATA structure associated with
1190 determine_invariantness (void)
1192 struct dom_walk_data walk_data
;
1194 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1195 walk_data
.dom_direction
= CDI_DOMINATORS
;
1196 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1198 init_walk_dominator_tree (&walk_data
);
1199 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1200 fini_walk_dominator_tree (&walk_data
);
1203 /* Hoist the statements in basic block BB out of the loops prescribed by
1204 data stored in LIM_DATA structures associated with each statement. Callback
1205 for walk_dominator_tree. */
1208 move_computations_stmt (struct dom_walk_data
*dw_data
,
1212 gimple_stmt_iterator bsi
;
1215 struct lim_aux_data
*lim_data
;
1217 if (!loop_outer (bb
->loop_father
))
1220 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1223 stmt
= gsi_stmt (bsi
);
1225 lim_data
= get_lim_data (stmt
);
1226 if (lim_data
== NULL
)
1232 cost
= lim_data
->cost
;
1233 level
= lim_data
->tgt_loop
;
1234 clear_lim_data (stmt
);
1242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1244 fprintf (dump_file
, "Moving PHI node\n");
1245 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1246 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1250 if (gimple_phi_num_args (stmt
) == 1)
1252 tree arg
= PHI_ARG_DEF (stmt
, 0);
1253 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1254 gimple_phi_result (stmt
),
1256 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1260 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1261 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1262 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1263 /* Get the PHI arguments corresponding to the true and false
1265 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1266 gcc_assert (arg0
&& arg1
);
1267 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1268 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1269 new_stmt
= gimple_build_assign_with_ops (COND_EXPR
,
1270 gimple_phi_result (stmt
),
1272 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1273 *((unsigned int *)(dw_data
->global_data
)) |= TODO_cleanup_cfg
;
1275 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1276 remove_phi_node (&bsi
, false);
1279 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1283 stmt
= gsi_stmt (bsi
);
1285 lim_data
= get_lim_data (stmt
);
1286 if (lim_data
== NULL
)
1292 cost
= lim_data
->cost
;
1293 level
= lim_data
->tgt_loop
;
1294 clear_lim_data (stmt
);
1302 /* We do not really want to move conditionals out of the loop; we just
1303 placed it here to force its operands to be moved if necessary. */
1304 if (gimple_code (stmt
) == GIMPLE_COND
)
1307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1309 fprintf (dump_file
, "Moving statement\n");
1310 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1311 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1315 e
= loop_preheader_edge (level
);
1316 gcc_assert (!gimple_vdef (stmt
));
1317 if (gimple_vuse (stmt
))
1319 /* The new VUSE is the one from the virtual PHI in the loop
1320 header or the one already present. */
1321 gimple_stmt_iterator gsi2
;
1322 for (gsi2
= gsi_start_phis (e
->dest
);
1323 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1325 gimple phi
= gsi_stmt (gsi2
);
1326 if (virtual_operand_p (gimple_phi_result (phi
)))
1328 gimple_set_vuse (stmt
, PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1333 gsi_remove (&bsi
, false);
1334 gsi_insert_on_edge (e
, stmt
);
1338 /* Hoist the statements out of the loops prescribed by data stored in
1339 LIM_DATA structures associated with each statement.*/
1342 move_computations (void)
1344 struct dom_walk_data walk_data
;
1345 unsigned int todo
= 0;
1347 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1348 walk_data
.global_data
= &todo
;
1349 walk_data
.dom_direction
= CDI_DOMINATORS
;
1350 walk_data
.before_dom_children
= move_computations_stmt
;
1352 init_walk_dominator_tree (&walk_data
);
1353 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1354 fini_walk_dominator_tree (&walk_data
);
1356 gsi_commit_edge_inserts ();
1357 if (need_ssa_update_p (cfun
))
1358 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1363 /* Checks whether the statement defining variable *INDEX can be hoisted
1364 out of the loop passed in DATA. Callback for for_each_index. */
1367 may_move_till (tree ref
, tree
*index
, void *data
)
1369 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1371 /* If REF is an array reference, check also that the step and the lower
1372 bound is invariant in LOOP. */
1373 if (TREE_CODE (ref
) == ARRAY_REF
)
1375 tree step
= TREE_OPERAND (ref
, 3);
1376 tree lbound
= TREE_OPERAND (ref
, 2);
1378 max_loop
= outermost_invariant_loop (step
, loop
);
1382 max_loop
= outermost_invariant_loop (lbound
, loop
);
1387 max_loop
= outermost_invariant_loop (*index
, loop
);
1394 /* If OP is SSA NAME, force the statement that defines it to be
1395 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1398 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1403 || is_gimple_min_invariant (op
))
1406 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1408 stmt
= SSA_NAME_DEF_STMT (op
);
1409 if (gimple_nop_p (stmt
))
1412 set_level (stmt
, orig_loop
, loop
);
1415 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1416 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1422 struct loop
*orig_loop
;
1426 force_move_till (tree ref
, tree
*index
, void *data
)
1428 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1430 if (TREE_CODE (ref
) == ARRAY_REF
)
1432 tree step
= TREE_OPERAND (ref
, 3);
1433 tree lbound
= TREE_OPERAND (ref
, 2);
1435 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1436 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1439 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1444 /* A hash function for struct mem_ref object OBJ. */
1447 memref_hash (const void *obj
)
1449 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1454 /* An equality function for struct mem_ref object OBJ1 with
1455 memory reference OBJ2. */
1458 memref_eq (const void *obj1
, const void *obj2
)
1460 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1462 return operand_equal_p (mem1
->mem
, (const_tree
) obj2
, 0);
1465 /* Releases list of memory reference locations ACCS. */
1468 free_mem_ref_locs (mem_ref_locs_p accs
)
1476 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1478 VEC_free (mem_ref_loc_p
, heap
, accs
->locs
);
1482 /* A function to free the mem_ref object OBJ. */
1485 memref_free (struct mem_ref
*mem
)
1488 mem_ref_locs_p accs
;
1490 FOR_EACH_VEC_ELT (mem_ref_locs_p
, mem
->accesses_in_loop
, i
, accs
)
1491 free_mem_ref_locs (accs
);
1492 VEC_free (mem_ref_locs_p
, heap
, mem
->accesses_in_loop
);
1497 /* Allocates and returns a memory reference description for MEM whose hash
1498 value is HASH and id is ID. */
1501 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1503 mem_ref_p ref
= XNEW (struct mem_ref
);
1507 ref
->stored
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1508 ref
->indep_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1509 ref
->dep_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1510 ref
->indep_ref
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1511 ref
->dep_ref
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1512 ref
->accesses_in_loop
= NULL
;
1517 /* Allocates and returns the new list of locations. */
1519 static mem_ref_locs_p
1520 mem_ref_locs_alloc (void)
1522 mem_ref_locs_p accs
= XNEW (struct mem_ref_locs
);
1527 /* Records memory reference location *LOC in LOOP to the memory reference
1528 description REF. The reference occurs in statement STMT. */
1531 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1533 mem_ref_loc_p aref
= XNEW (struct mem_ref_loc
);
1534 mem_ref_locs_p accs
;
1535 bitmap ril
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1537 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1538 <= (unsigned) loop
->num
)
1539 VEC_safe_grow_cleared (mem_ref_locs_p
, heap
, ref
->accesses_in_loop
,
1541 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1544 accs
= mem_ref_locs_alloc ();
1545 VEC_replace (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
, accs
);
1551 VEC_safe_push (mem_ref_loc_p
, heap
, accs
->locs
, aref
);
1552 bitmap_set_bit (ril
, ref
->id
);
1555 /* Marks reference REF as stored in LOOP. */
1558 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1561 loop
!= current_loops
->tree_root
1562 && !bitmap_bit_p (ref
->stored
, loop
->num
);
1563 loop
= loop_outer (loop
))
1564 bitmap_set_bit (ref
->stored
, loop
->num
);
1567 /* Gathers memory references in statement STMT in LOOP, storing the
1568 information about them in the memory_accesses structure. Marks
1569 the vops accessed through unrecognized statements there as
1573 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1582 if (!gimple_vuse (stmt
))
1585 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1588 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1589 ref
= mem_ref_alloc (error_mark_node
, 0, id
);
1590 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1591 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1593 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1594 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1596 if (gimple_vdef (stmt
))
1597 mark_ref_stored (ref
, loop
);
1598 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1602 hash
= iterative_hash_expr (*mem
, 0);
1603 slot
= htab_find_slot_with_hash (memory_accesses
.refs
, *mem
, hash
, INSERT
);
1607 ref
= (mem_ref_p
) *slot
;
1612 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1613 ref
= mem_ref_alloc (*mem
, hash
, id
);
1614 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1617 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, "Memory reference %u: ", id
);
1620 print_generic_expr (dump_file
, ref
->mem
, TDF_SLIM
);
1621 fprintf (dump_file
, "\n");
1626 mark_ref_stored (ref
, loop
);
1628 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1632 /* Gathers memory references in loops. */
1635 gather_mem_refs_in_loops (void)
1637 gimple_stmt_iterator bsi
;
1641 bitmap lrefs
, alrefs
, alrefso
;
1645 loop
= bb
->loop_father
;
1646 if (loop
== current_loops
->tree_root
)
1649 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1650 gather_mem_refs_stmt (loop
, gsi_stmt (bsi
));
1653 /* Propagate the information about accessed memory references up
1654 the loop hierarchy. */
1655 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1657 lrefs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1658 alrefs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
, loop
->num
);
1659 bitmap_ior_into (alrefs
, lrefs
);
1661 if (loop_outer (loop
) == current_loops
->tree_root
)
1664 alrefso
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1665 loop_outer (loop
)->num
);
1666 bitmap_ior_into (alrefso
, alrefs
);
1670 /* Create a mapping from virtual operands to references that touch them
1674 create_vop_ref_mapping_loop (struct loop
*loop
)
1676 bitmap refs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1682 EXECUTE_IF_SET_IN_BITMAP (refs
, 0, i
, bi
)
1684 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1685 for (sloop
= loop
; sloop
!= current_loops
->tree_root
;
1686 sloop
= loop_outer (sloop
))
1687 if (bitmap_bit_p (ref
->stored
, loop
->num
))
1690 = VEC_index (bitmap
, memory_accesses
.all_refs_stored_in_loop
,
1692 bitmap_set_bit (refs_stored
, ref
->id
);
1697 /* For each non-clobbered virtual operand and each loop, record the memory
1698 references in this loop that touch the operand. */
1701 create_vop_ref_mapping (void)
1706 FOR_EACH_LOOP (li
, loop
, 0)
1708 create_vop_ref_mapping_loop (loop
);
1712 /* Gathers information about memory accesses in the loops. */
1715 analyze_memory_references (void)
1720 memory_accesses
.refs
= htab_create (100, memref_hash
, memref_eq
, NULL
);
1721 memory_accesses
.refs_list
= NULL
;
1722 memory_accesses
.refs_in_loop
= VEC_alloc (bitmap
, heap
,
1723 number_of_loops ());
1724 memory_accesses
.all_refs_in_loop
= VEC_alloc (bitmap
, heap
,
1725 number_of_loops ());
1726 memory_accesses
.all_refs_stored_in_loop
= VEC_alloc (bitmap
, heap
,
1727 number_of_loops ());
1729 for (i
= 0; i
< number_of_loops (); i
++)
1731 empty
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1732 VEC_quick_push (bitmap
, memory_accesses
.refs_in_loop
, empty
);
1733 empty
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1734 VEC_quick_push (bitmap
, memory_accesses
.all_refs_in_loop
, empty
);
1735 empty
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1736 VEC_quick_push (bitmap
, memory_accesses
.all_refs_stored_in_loop
, empty
);
1739 memory_accesses
.ttae_cache
= NULL
;
1741 gather_mem_refs_in_loops ();
1742 create_vop_ref_mapping ();
1745 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1746 tree_to_aff_combination_expand. */
1749 mem_refs_may_alias_p (tree mem1
, tree mem2
, struct pointer_map_t
**ttae_cache
)
1751 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1752 object and their offset differ in such a way that the locations cannot
1753 overlap, then they cannot alias. */
1754 double_int size1
, size2
;
1755 aff_tree off1
, off2
;
1757 /* Perform basic offset and type-based disambiguation. */
1758 if (!refs_may_alias_p (mem1
, mem2
))
1761 /* The expansion of addresses may be a bit expensive, thus we only do
1762 the check at -O2 and higher optimization levels. */
1766 get_inner_reference_aff (mem1
, &off1
, &size1
);
1767 get_inner_reference_aff (mem2
, &off2
, &size2
);
1768 aff_combination_expand (&off1
, ttae_cache
);
1769 aff_combination_expand (&off2
, ttae_cache
);
1770 aff_combination_scale (&off1
, double_int_minus_one
);
1771 aff_combination_add (&off2
, &off1
);
1773 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1779 /* Rewrites location LOC by TMP_VAR. */
1782 rewrite_mem_ref_loc (mem_ref_loc_p loc
, tree tmp_var
)
1784 *loc
->ref
= tmp_var
;
1785 update_stmt (loc
->stmt
);
1788 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1791 get_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
,
1792 VEC (mem_ref_loc_p
, heap
) **locs
)
1794 mem_ref_locs_p accs
;
1797 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1799 struct loop
*subloop
;
1801 if (!bitmap_bit_p (refs
, ref
->id
))
1804 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1805 > (unsigned) loop
->num
)
1807 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1810 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1811 VEC_safe_push (mem_ref_loc_p
, heap
, *locs
, loc
);
1815 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1816 get_all_locs_in_loop (subloop
, ref
, locs
);
1819 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1822 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1826 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1828 get_all_locs_in_loop (loop
, ref
, &locs
);
1829 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
1830 rewrite_mem_ref_loc (loc
, tmp_var
);
1831 VEC_free (mem_ref_loc_p
, heap
, locs
);
1834 /* The name and the length of the currently generated variable
1836 #define MAX_LSM_NAME_LENGTH 40
1837 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1838 static int lsm_tmp_name_length
;
1840 /* Adds S to lsm_tmp_name. */
1843 lsm_tmp_name_add (const char *s
)
1845 int l
= strlen (s
) + lsm_tmp_name_length
;
1846 if (l
> MAX_LSM_NAME_LENGTH
)
1849 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1850 lsm_tmp_name_length
= l
;
1853 /* Stores the name for temporary variable that replaces REF to
1857 gen_lsm_tmp_name (tree ref
)
1861 switch (TREE_CODE (ref
))
1864 case TARGET_MEM_REF
:
1865 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1866 lsm_tmp_name_add ("_");
1870 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1874 case VIEW_CONVERT_EXPR
:
1875 case ARRAY_RANGE_REF
:
1876 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1880 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1881 lsm_tmp_name_add ("_RE");
1885 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1886 lsm_tmp_name_add ("_IM");
1890 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1891 lsm_tmp_name_add ("_");
1892 name
= get_name (TREE_OPERAND (ref
, 1));
1895 lsm_tmp_name_add (name
);
1899 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1900 lsm_tmp_name_add ("_I");
1906 name
= get_name (ref
);
1909 lsm_tmp_name_add (name
);
1913 lsm_tmp_name_add ("S");
1917 lsm_tmp_name_add ("R");
1929 /* Determines name for temporary variable that replaces REF.
1930 The name is accumulated into the lsm_tmp_name variable.
1931 N is added to the name of the temporary. */
1934 get_lsm_tmp_name (tree ref
, unsigned n
)
1938 lsm_tmp_name_length
= 0;
1939 gen_lsm_tmp_name (ref
);
1940 lsm_tmp_name_add ("_lsm");
1945 lsm_tmp_name_add (ns
);
1947 return lsm_tmp_name
;
1950 struct prev_flag_edges
{
1951 /* Edge to insert new flag comparison code. */
1952 edge append_cond_position
;
1954 /* Edge for fall through from previous flag comparison. */
1955 edge last_cond_fallthru
;
1958 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1961 The store is only done if MEM has changed. We do this so no
1962 changes to MEM occur on code paths that did not originally store
1965 The common case for execute_sm will transform:
1985 This function will generate:
2004 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
)
2006 basic_block new_bb
, then_bb
, old_dest
;
2007 bool loop_has_only_one_exit
;
2008 edge then_old_edge
, orig_ex
= ex
;
2009 gimple_stmt_iterator gsi
;
2011 struct prev_flag_edges
*prev_edges
= (struct prev_flag_edges
*) ex
->aux
;
2013 /* ?? Insert store after previous store if applicable. See note
2016 ex
= prev_edges
->append_cond_position
;
2018 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
2020 if (loop_has_only_one_exit
)
2021 ex
= split_block_after_labels (ex
->dest
);
2023 old_dest
= ex
->dest
;
2024 new_bb
= split_edge (ex
);
2025 then_bb
= create_empty_bb (new_bb
);
2026 if (current_loops
&& new_bb
->loop_father
)
2027 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
2029 gsi
= gsi_start_bb (new_bb
);
2030 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
2031 NULL_TREE
, NULL_TREE
);
2032 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2034 gsi
= gsi_start_bb (then_bb
);
2035 /* Insert actual store. */
2036 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
2037 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2039 make_edge (new_bb
, then_bb
, EDGE_TRUE_VALUE
);
2040 make_edge (new_bb
, old_dest
, EDGE_FALSE_VALUE
);
2041 then_old_edge
= make_edge (then_bb
, old_dest
, EDGE_FALLTHRU
);
2043 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
2047 basic_block prevbb
= prev_edges
->last_cond_fallthru
->src
;
2048 redirect_edge_succ (prev_edges
->last_cond_fallthru
, new_bb
);
2049 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
2050 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
2051 recompute_dominator (CDI_DOMINATORS
, old_dest
));
2054 /* ?? Because stores may alias, they must happen in the exact
2055 sequence they originally happened. Save the position right after
2056 the (_lsm) store we just created so we can continue appending after
2057 it and maintain the original order. */
2059 struct prev_flag_edges
*p
;
2062 orig_ex
->aux
= NULL
;
2063 alloc_aux_for_edge (orig_ex
, sizeof (struct prev_flag_edges
));
2064 p
= (struct prev_flag_edges
*) orig_ex
->aux
;
2065 p
->append_cond_position
= then_old_edge
;
2066 p
->last_cond_fallthru
= find_edge (new_bb
, old_dest
);
2067 orig_ex
->aux
= (void *) p
;
2070 if (!loop_has_only_one_exit
)
2071 for (gsi
= gsi_start_phis (old_dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2073 gimple phi
= gsi_stmt (gsi
);
2076 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2077 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
2079 tree arg
= gimple_phi_arg_def (phi
, i
);
2080 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
2084 /* Remove the original fall through edge. This was the
2085 single_succ_edge (new_bb). */
2086 EDGE_SUCC (new_bb
, 0)->flags
&= ~EDGE_FALLTHRU
;
2089 /* Helper function for execute_sm. On every location where REF is
2090 set, set an appropriate flag indicating the store. */
2093 execute_sm_if_changed_flag_set (struct loop
*loop
, mem_ref_p ref
)
2098 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
2099 char *str
= get_lsm_tmp_name (ref
->mem
, ~0);
2101 lsm_tmp_name_add ("_flag");
2102 flag
= create_tmp_reg (boolean_type_node
, str
);
2103 get_all_locs_in_loop (loop
, ref
, &locs
);
2104 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
2106 gimple_stmt_iterator gsi
;
2109 /* Only set the flag for writes. */
2110 if (is_gimple_assign (loc
->stmt
)
2111 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
2113 gsi
= gsi_for_stmt (loc
->stmt
);
2114 stmt
= gimple_build_assign (flag
, boolean_true_node
);
2115 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2118 VEC_free (mem_ref_loc_p
, heap
, locs
);
2122 /* Executes store motion of memory reference REF from LOOP.
2123 Exits from the LOOP are stored in EXITS. The initialization of the
2124 temporary variable is put to the preheader of the loop, and assignments
2125 to the reference from the temporary variable are emitted to exits. */
2128 execute_sm (struct loop
*loop
, VEC (edge
, heap
) *exits
, mem_ref_p ref
)
2130 tree tmp_var
, store_flag
;
2133 struct fmt_data fmt_data
;
2134 edge ex
, latch_edge
;
2135 struct lim_aux_data
*lim_data
;
2136 bool multi_threaded_model_p
= false;
2138 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2140 fprintf (dump_file
, "Executing store motion of ");
2141 print_generic_expr (dump_file
, ref
->mem
, 0);
2142 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2145 tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
),
2146 get_lsm_tmp_name (ref
->mem
, ~0));
2148 fmt_data
.loop
= loop
;
2149 fmt_data
.orig_loop
= loop
;
2150 for_each_index (&ref
->mem
, force_move_till
, &fmt_data
);
2152 if (block_in_transaction (loop_preheader_edge (loop
)->src
)
2153 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
))
2154 multi_threaded_model_p
= true;
2156 if (multi_threaded_model_p
)
2157 store_flag
= execute_sm_if_changed_flag_set (loop
, ref
);
2159 rewrite_mem_refs (loop
, ref
, tmp_var
);
2161 /* Emit the load code into the latch, so that we are sure it will
2162 be processed after all dependencies. */
2163 latch_edge
= loop_latch_edge (loop
);
2165 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
2166 load altogether, since the store is predicated by a flag. We
2167 could, do the load only if it was originally in the loop. */
2168 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
));
2169 lim_data
= init_lim_data (load
);
2170 lim_data
->max_loop
= loop
;
2171 lim_data
->tgt_loop
= loop
;
2172 gsi_insert_on_edge (latch_edge
, load
);
2174 if (multi_threaded_model_p
)
2176 load
= gimple_build_assign (store_flag
, boolean_false_node
);
2177 lim_data
= init_lim_data (load
);
2178 lim_data
->max_loop
= loop
;
2179 lim_data
->tgt_loop
= loop
;
2180 gsi_insert_on_edge (latch_edge
, load
);
2183 /* Sink the store to every exit from the loop. */
2184 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2185 if (!multi_threaded_model_p
)
2188 store
= gimple_build_assign (unshare_expr (ref
->mem
), tmp_var
);
2189 gsi_insert_on_edge (ex
, store
);
2192 execute_sm_if_changed (ex
, ref
->mem
, tmp_var
, store_flag
);
2195 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2196 edges of the LOOP. */
2199 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2200 VEC (edge
, heap
) *exits
)
2206 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2208 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2209 execute_sm (loop
, exits
, ref
);
2213 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2214 make sure REF is always stored to in LOOP. */
2217 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2219 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
2223 struct loop
*must_exec
;
2226 base
= get_base_address (ref
->mem
);
2227 if (INDIRECT_REF_P (base
)
2228 || TREE_CODE (base
) == MEM_REF
)
2229 base
= TREE_OPERAND (base
, 0);
2231 get_all_locs_in_loop (loop
, ref
, &locs
);
2232 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
2234 if (!get_lim_data (loc
->stmt
))
2237 /* If we require an always executed store make sure the statement
2238 stores to the reference. */
2242 if (!gimple_get_lhs (loc
->stmt
))
2244 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2247 if (INDIRECT_REF_P (lhs
)
2248 || TREE_CODE (lhs
) == MEM_REF
)
2249 lhs
= TREE_OPERAND (lhs
, 0);
2254 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2258 if (must_exec
== loop
2259 || flow_loop_nested_p (must_exec
, loop
))
2265 VEC_free (mem_ref_loc_p
, heap
, locs
);
2270 /* Returns true if REF1 and REF2 are independent. */
2273 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2276 || bitmap_bit_p (ref1
->indep_ref
, ref2
->id
))
2278 if (bitmap_bit_p (ref1
->dep_ref
, ref2
->id
))
2280 if (!MEM_ANALYZABLE (ref1
)
2281 || !MEM_ANALYZABLE (ref2
))
2284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2285 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2286 ref1
->id
, ref2
->id
);
2288 if (mem_refs_may_alias_p (ref1
->mem
, ref2
->mem
,
2289 &memory_accesses
.ttae_cache
))
2291 bitmap_set_bit (ref1
->dep_ref
, ref2
->id
);
2292 bitmap_set_bit (ref2
->dep_ref
, ref1
->id
);
2293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2294 fprintf (dump_file
, "dependent.\n");
2299 bitmap_set_bit (ref1
->indep_ref
, ref2
->id
);
2300 bitmap_set_bit (ref2
->indep_ref
, ref1
->id
);
2301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2302 fprintf (dump_file
, "independent.\n");
2307 /* Records the information whether REF is independent in LOOP (according
2311 record_indep_loop (struct loop
*loop
, mem_ref_p ref
, bool indep
)
2314 bitmap_set_bit (ref
->indep_loop
, loop
->num
);
2316 bitmap_set_bit (ref
->dep_loop
, loop
->num
);
2319 /* Returns true if REF is independent on all other memory references in
2323 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
)
2325 bitmap refs_to_check
;
2328 bool ret
= true, stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
2332 refs_to_check
= VEC_index (bitmap
,
2333 memory_accesses
.all_refs_in_loop
, loop
->num
);
2335 refs_to_check
= VEC_index (bitmap
,
2336 memory_accesses
.all_refs_stored_in_loop
,
2339 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2341 aref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2342 if (!MEM_ANALYZABLE (aref
)
2343 || !refs_independent_p (ref
, aref
))
2346 record_indep_loop (loop
, aref
, false);
2354 /* Returns true if REF is independent on all other memory references in
2355 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2358 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2362 if (bitmap_bit_p (ref
->indep_loop
, loop
->num
))
2364 if (bitmap_bit_p (ref
->dep_loop
, loop
->num
))
2367 ret
= ref_indep_loop_p_1 (loop
, ref
);
2369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2370 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2371 ref
->id
, loop
->num
, ret
? "independent" : "dependent");
2373 record_indep_loop (loop
, ref
, ret
);
2378 /* Returns true if we can perform store motion of REF from LOOP. */
2381 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2385 /* Can't hoist unanalyzable refs. */
2386 if (!MEM_ANALYZABLE (ref
))
2389 /* Unless the reference is stored in the loop, there is nothing to do. */
2390 if (!bitmap_bit_p (ref
->stored
, loop
->num
))
2393 /* It should be movable. */
2394 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
))
2395 || TREE_THIS_VOLATILE (ref
->mem
)
2396 || !for_each_index (&ref
->mem
, may_move_till
, loop
))
2399 /* If it can throw fail, we do not properly update EH info. */
2400 if (tree_could_throw_p (ref
->mem
))
2403 /* If it can trap, it must be always executed in LOOP.
2404 Readonly memory locations may trap when storing to them, but
2405 tree_could_trap_p is a predicate for rvalues, so check that
2407 base
= get_base_address (ref
->mem
);
2408 if ((tree_could_trap_p (ref
->mem
)
2409 || (DECL_P (base
) && TREE_READONLY (base
)))
2410 && !ref_always_accessed_p (loop
, ref
, true))
2413 /* And it must be independent on all other memory references
2415 if (!ref_indep_loop_p (loop
, ref
))
2421 /* Marks the references in LOOP for that store motion should be performed
2422 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2423 motion was performed in one of the outer loops. */
2426 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2428 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
2434 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2436 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2437 if (can_sm_ref_p (loop
, ref
))
2438 bitmap_set_bit (refs_to_sm
, i
);
2442 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2443 for a store motion optimization (i.e. whether we can insert statement
2447 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2448 VEC (edge
, heap
) *exits
)
2453 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2454 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2460 /* Try to perform store motion for all memory references modified inside
2461 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2462 store motion was executed in one of the outer loops. */
2465 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2467 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2468 struct loop
*subloop
;
2469 bitmap sm_in_loop
= BITMAP_ALLOC (NULL
);
2471 if (loop_suitable_for_sm (loop
, exits
))
2473 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2474 hoist_memory_references (loop
, sm_in_loop
, exits
);
2476 VEC_free (edge
, heap
, exits
);
2478 bitmap_ior_into (sm_executed
, sm_in_loop
);
2479 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2480 store_motion_loop (subloop
, sm_executed
);
2481 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2482 BITMAP_FREE (sm_in_loop
);
2485 /* Try to perform store motion for all memory references modified inside
2492 bitmap sm_executed
= BITMAP_ALLOC (NULL
);
2494 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2495 store_motion_loop (loop
, sm_executed
);
2497 BITMAP_FREE (sm_executed
);
2498 gsi_commit_edge_inserts ();
2501 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2502 for each such basic block bb records the outermost loop for that execution
2503 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2504 blocks that contain a nonpure call. */
2507 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
2509 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2512 struct loop
*inn_loop
= loop
;
2514 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2516 bbs
= get_loop_body_in_dom_order (loop
);
2518 for (i
= 0; i
< loop
->num_nodes
; i
++)
2523 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2526 if (TEST_BIT (contains_call
, bb
->index
))
2529 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2530 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2535 /* A loop might be infinite (TODO use simple loop analysis
2536 to disprove this if possible). */
2537 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2540 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2543 if (bb
->loop_father
->header
== bb
)
2545 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2548 /* In a loop that is always entered we may proceed anyway.
2549 But record that we entered it and stop once we leave it. */
2550 inn_loop
= bb
->loop_father
;
2556 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2557 if (last
== loop
->header
)
2559 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2565 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2566 fill_always_executed_in (loop
, contains_call
);
2569 /* Compute the global information needed by the loop invariant motion pass. */
2572 tree_ssa_lim_initialize (void)
2574 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2575 gimple_stmt_iterator bsi
;
2579 bitmap_obstack_initialize (&lim_bitmap_obstack
);
2581 sbitmap_zero (contains_call
);
2584 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2586 if (nonpure_call_p (gsi_stmt (bsi
)))
2590 if (!gsi_end_p (bsi
))
2591 SET_BIT (contains_call
, bb
->index
);
2594 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2595 fill_always_executed_in (loop
, contains_call
);
2597 sbitmap_free (contains_call
);
2599 lim_aux_data_map
= pointer_map_create ();
2602 compute_transaction_bits ();
2604 alloc_aux_for_edges (0);
2607 /* Cleans up after the invariant motion pass. */
2610 tree_ssa_lim_finalize (void)
2616 free_aux_for_edges ();
2619 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2621 bitmap_obstack_release (&lim_bitmap_obstack
);
2622 pointer_map_destroy (lim_aux_data_map
);
2624 htab_delete (memory_accesses
.refs
);
2626 FOR_EACH_VEC_ELT (mem_ref_p
, memory_accesses
.refs_list
, i
, ref
)
2628 VEC_free (mem_ref_p
, heap
, memory_accesses
.refs_list
);
2630 VEC_free (bitmap
, heap
, memory_accesses
.refs_in_loop
);
2631 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_in_loop
);
2632 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_stored_in_loop
);
2634 if (memory_accesses
.ttae_cache
)
2635 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
2638 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2639 i.e. those that are likely to be win regardless of the register pressure. */
2646 tree_ssa_lim_initialize ();
2648 /* Gathers information about memory accesses in the loops. */
2649 analyze_memory_references ();
2651 /* For each statement determine the outermost loop in that it is
2652 invariant and cost for computing the invariant. */
2653 determine_invariantness ();
2655 /* Execute store motion. Force the necessary invariants to be moved
2656 out of the loops as well. */
2659 /* Move the expressions that are expensive enough. */
2660 todo
= move_computations ();
2662 tree_ssa_lim_finalize ();