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"
29 #include "tree-pretty-print.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
37 #include "tree-pass.h"
40 #include "tree-affine.h"
41 #include "pointer-set.h"
42 #include "tree-ssa-propagate.h"
44 /* TODO: Support for predicated code motion. I.e.
55 Where COND and INV are is invariants, but evaluating INV may trap or be
56 invalid from some other reason if !COND. This may be transformed to
66 /* A type for the list of statements that have to be moved in order to be able
67 to hoist an invariant computation. */
75 /* The auxiliary data kept for each statement. */
79 struct loop
*max_loop
; /* The outermost loop in that the statement
82 struct loop
*tgt_loop
; /* The loop out of that we want to move the
85 struct loop
*always_executed_in
;
86 /* The outermost loop for that we are sure
87 the statement is executed if the loop
90 unsigned cost
; /* Cost of the computation performed by the
93 struct depend
*depends
; /* List of statements that must be also hoisted
94 out of the loop when this statement is
95 hoisted; i.e. those that define the operands
96 of the statement and are inside of the
100 /* limit for lsm that can be performed for one loop. */
101 static unsigned maximum_lsm
;
103 /* Maps statements to their lim_aux_data. */
105 static struct pointer_map_t
*lim_aux_data_map
;
107 /* Description of a memory reference location. */
109 typedef struct mem_ref_loc
111 tree
*ref
; /* The reference itself. */
112 gimple stmt
; /* The statement in that it occurs. */
115 DEF_VEC_P(mem_ref_loc_p
);
116 DEF_VEC_ALLOC_P(mem_ref_loc_p
, heap
);
118 /* The list of memory reference locations in a loop. */
120 typedef struct mem_ref_locs
122 VEC (mem_ref_loc_p
, heap
) *locs
;
125 DEF_VEC_P(mem_ref_locs_p
);
126 DEF_VEC_ALLOC_P(mem_ref_locs_p
, heap
);
128 /* Description of a memory reference. */
130 typedef struct mem_ref
132 tree mem
; /* The memory itself. */
133 unsigned id
; /* ID assigned to the memory reference
134 (its index in memory_accesses.refs_list) */
135 hashval_t hash
; /* Its hash value. */
136 bitmap stored
; /* The set of loops in that this memory location
138 VEC (mem_ref_locs_p
, heap
) *accesses_in_loop
;
139 /* The locations of the accesses. Vector
140 indexed by the loop number. */
141 bitmap vops
; /* Vops corresponding to this memory
144 /* The following sets are computed on demand. We keep both set and
145 its complement, so that we know whether the information was
146 already computed or not. */
147 bitmap indep_loop
; /* The set of loops in that the memory
148 reference is independent, meaning:
149 If it is stored in the loop, this store
150 is independent on all other loads and
152 If it is only loaded, then it is independent
153 on all stores in the loop. */
154 bitmap dep_loop
; /* The complement of INDEP_LOOP. */
156 bitmap indep_ref
; /* The set of memory references on that
157 this reference is independent. */
158 bitmap dep_ref
; /* The complement of DEP_REF. */
161 DEF_VEC_P(mem_ref_p
);
162 DEF_VEC_ALLOC_P(mem_ref_p
, heap
);
165 DEF_VEC_ALLOC_P(bitmap
, heap
);
168 DEF_VEC_ALLOC_P(htab_t
, heap
);
170 /* Description of memory accesses in loops. */
174 /* The hash table of memory references accessed in loops. */
177 /* The list of memory references. */
178 VEC (mem_ref_p
, heap
) *refs_list
;
180 /* The set of memory references accessed in each loop. */
181 VEC (bitmap
, heap
) *refs_in_loop
;
183 /* The set of memory references accessed in each loop, including
185 VEC (bitmap
, heap
) *all_refs_in_loop
;
187 /* The set of virtual operands clobbered in a given loop. */
188 VEC (bitmap
, heap
) *clobbered_vops
;
190 /* Map from the pair (loop, virtual operand) to the set of refs that
191 touch the virtual operand in the loop. */
192 VEC (htab_t
, heap
) *vop_ref_map
;
194 /* Cache for expanding memory addresses. */
195 struct pointer_map_t
*ttae_cache
;
198 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
200 /* Minimum cost of an expensive expression. */
201 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
203 /* The outermost loop for that execution of the header guarantees that the
204 block will be executed. */
205 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
207 static struct lim_aux_data
*
208 init_lim_data (gimple stmt
)
210 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
212 *p
= XCNEW (struct lim_aux_data
);
213 return (struct lim_aux_data
*) *p
;
216 static struct lim_aux_data
*
217 get_lim_data (gimple stmt
)
219 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
223 return (struct lim_aux_data
*) *p
;
226 /* Releases the memory occupied by DATA. */
229 free_lim_aux_data (struct lim_aux_data
*data
)
231 struct depend
*dep
, *next
;
233 for (dep
= data
->depends
; dep
; dep
= next
)
242 clear_lim_data (gimple stmt
)
244 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
248 free_lim_aux_data ((struct lim_aux_data
*) *p
);
252 /* Calls CBCK for each index in memory reference ADDR_P. There are two
253 kinds situations handled; in each of these cases, the memory reference
254 and DATA are passed to the callback:
256 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
257 pass the pointer to the index to the callback.
259 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
260 pointer to addr to the callback.
262 If the callback returns false, the whole search stops and false is returned.
263 Otherwise the function returns true after traversing through the whole
264 reference *ADDR_P. */
267 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
271 for (; ; addr_p
= nxt
)
273 switch (TREE_CODE (*addr_p
))
276 return cbck (*addr_p
, addr_p
, data
);
279 nxt
= &TREE_OPERAND (*addr_p
, 0);
280 return cbck (*addr_p
, nxt
, data
);
283 case VIEW_CONVERT_EXPR
:
286 nxt
= &TREE_OPERAND (*addr_p
, 0);
290 /* If the component has varying offset, it behaves like index
292 idx
= &TREE_OPERAND (*addr_p
, 2);
294 && !cbck (*addr_p
, idx
, data
))
297 nxt
= &TREE_OPERAND (*addr_p
, 0);
301 case ARRAY_RANGE_REF
:
302 nxt
= &TREE_OPERAND (*addr_p
, 0);
303 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
320 gcc_assert (is_gimple_min_invariant (*addr_p
));
324 idx
= &TMR_BASE (*addr_p
);
326 && !cbck (*addr_p
, idx
, data
))
328 idx
= &TMR_INDEX (*addr_p
);
330 && !cbck (*addr_p
, idx
, data
))
332 idx
= &TMR_INDEX2 (*addr_p
);
334 && !cbck (*addr_p
, idx
, data
))
344 /* If it is possible to hoist the statement STMT unconditionally,
345 returns MOVE_POSSIBLE.
346 If it is possible to hoist the statement STMT, but we must avoid making
347 it executed if it would not be executed in the original program (e.g.
348 because it may trap), return MOVE_PRESERVE_EXECUTION.
349 Otherwise return MOVE_IMPOSSIBLE. */
352 movement_possibility (gimple stmt
)
355 enum move_pos ret
= MOVE_POSSIBLE
;
357 if (flag_unswitch_loops
358 && gimple_code (stmt
) == GIMPLE_COND
)
360 /* If we perform unswitching, force the operands of the invariant
361 condition to be moved out of the loop. */
362 return MOVE_POSSIBLE
;
365 if (gimple_code (stmt
) == GIMPLE_PHI
366 && gimple_phi_num_args (stmt
) <= 2
367 && is_gimple_reg (gimple_phi_result (stmt
))
368 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
369 return MOVE_POSSIBLE
;
371 if (gimple_get_lhs (stmt
) == NULL_TREE
)
372 return MOVE_IMPOSSIBLE
;
374 if (gimple_vdef (stmt
))
375 return MOVE_IMPOSSIBLE
;
377 if (stmt_ends_bb_p (stmt
)
378 || gimple_has_volatile_ops (stmt
)
379 || gimple_has_side_effects (stmt
)
380 || stmt_could_throw_p (stmt
))
381 return MOVE_IMPOSSIBLE
;
383 if (is_gimple_call (stmt
))
385 /* While pure or const call is guaranteed to have no side effects, we
386 cannot move it arbitrarily. Consider code like
388 char *s = something ();
398 Here the strlen call cannot be moved out of the loop, even though
399 s is invariant. In addition to possibly creating a call with
400 invalid arguments, moving out a function call that is not executed
401 may cause performance regressions in case the call is costly and
402 not executed at all. */
403 ret
= MOVE_PRESERVE_EXECUTION
;
404 lhs
= gimple_call_lhs (stmt
);
406 else if (is_gimple_assign (stmt
))
407 lhs
= gimple_assign_lhs (stmt
);
409 return MOVE_IMPOSSIBLE
;
411 if (TREE_CODE (lhs
) == SSA_NAME
412 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
413 return MOVE_IMPOSSIBLE
;
415 if (TREE_CODE (lhs
) != SSA_NAME
416 || gimple_could_trap_p (stmt
))
417 return MOVE_PRESERVE_EXECUTION
;
422 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
423 loop to that we could move the expression using DEF if it did not have
424 other operands, i.e. the outermost loop enclosing LOOP in that the value
425 of DEF is invariant. */
428 outermost_invariant_loop (tree def
, struct loop
*loop
)
432 struct loop
*max_loop
;
433 struct lim_aux_data
*lim_data
;
436 return superloop_at_depth (loop
, 1);
438 if (TREE_CODE (def
) != SSA_NAME
)
440 gcc_assert (is_gimple_min_invariant (def
));
441 return superloop_at_depth (loop
, 1);
444 def_stmt
= SSA_NAME_DEF_STMT (def
);
445 def_bb
= gimple_bb (def_stmt
);
447 return superloop_at_depth (loop
, 1);
449 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
451 lim_data
= get_lim_data (def_stmt
);
452 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
453 max_loop
= find_common_loop (max_loop
,
454 loop_outer (lim_data
->max_loop
));
455 if (max_loop
== loop
)
457 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
462 /* DATA is a structure containing information associated with a statement
463 inside LOOP. DEF is one of the operands of this statement.
465 Find the outermost loop enclosing LOOP in that value of DEF is invariant
466 and record this in DATA->max_loop field. If DEF itself is defined inside
467 this loop as well (i.e. we need to hoist it out of the loop if we want
468 to hoist the statement represented by DATA), record the statement in that
469 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
470 add the cost of the computation of DEF to the DATA->cost.
472 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
475 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
478 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
479 basic_block def_bb
= gimple_bb (def_stmt
);
480 struct loop
*max_loop
;
482 struct lim_aux_data
*def_data
;
487 max_loop
= outermost_invariant_loop (def
, loop
);
491 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
492 data
->max_loop
= max_loop
;
494 def_data
= get_lim_data (def_stmt
);
499 /* Only add the cost if the statement defining DEF is inside LOOP,
500 i.e. if it is likely that by moving the invariants dependent
501 on it, we will be able to avoid creating a new register for
502 it (since it will be only used in these dependent invariants). */
503 && def_bb
->loop_father
== loop
)
504 data
->cost
+= def_data
->cost
;
506 dep
= XNEW (struct depend
);
507 dep
->stmt
= def_stmt
;
508 dep
->next
= data
->depends
;
514 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
515 are just ad-hoc constants. The estimates should be based on target-specific
519 stmt_cost (gimple stmt
)
524 /* Always try to create possibilities for unswitching. */
525 if (gimple_code (stmt
) == GIMPLE_COND
526 || gimple_code (stmt
) == GIMPLE_PHI
)
527 return LIM_EXPENSIVE
;
529 /* Hoisting memory references out should almost surely be a win. */
530 if (gimple_references_memory_p (stmt
))
533 if (is_gimple_call (stmt
))
535 /* We should be hoisting calls if possible. */
537 /* Unless the call is a builtin_constant_p; this always folds to a
538 constant, so moving it is useless. */
539 fndecl
= gimple_call_fndecl (stmt
);
541 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
542 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
548 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
551 switch (gimple_assign_rhs_code (stmt
))
564 /* Division and multiplication are usually expensive. */
580 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
581 REF is independent. If REF is not independent in LOOP, NULL is returned
585 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
589 if (bitmap_bit_p (ref
->stored
, loop
->num
))
594 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
595 if (!bitmap_bit_p (ref
->stored
, aloop
->num
)
596 && ref_indep_loop_p (aloop
, ref
))
599 if (ref_indep_loop_p (loop
, ref
))
605 /* If there is a simple load or store to a memory reference in STMT, returns
606 the location of the memory reference, and sets IS_STORE according to whether
607 it is a store or load. Otherwise, returns NULL. */
610 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
615 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
616 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
619 code
= gimple_assign_rhs_code (stmt
);
621 lhs
= gimple_assign_lhs_ptr (stmt
);
623 if (TREE_CODE (*lhs
) == SSA_NAME
)
625 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
626 || !is_gimple_addressable (gimple_assign_rhs1 (stmt
)))
630 return gimple_assign_rhs1_ptr (stmt
);
632 else if (code
== SSA_NAME
633 || (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
634 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
643 /* Returns the memory reference contained in STMT. */
646 mem_ref_in_stmt (gimple stmt
)
649 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
657 hash
= iterative_hash_expr (*mem
, 0);
658 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
660 gcc_assert (ref
!= NULL
);
664 /* From a controlling predicate in DOM determine the arguments from
665 the PHI node PHI that are chosen if the predicate evaluates to
666 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
667 they are non-NULL. Returns true if the arguments can be determined,
668 else return false. */
671 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
672 tree
*true_arg_p
, tree
*false_arg_p
)
674 basic_block bb
= gimple_bb (phi
);
675 edge true_edge
, false_edge
, tem
;
676 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
678 /* We have to verify that one edge into the PHI node is dominated
679 by the true edge of the predicate block and the other edge
680 dominated by the false edge. This ensures that the PHI argument
681 we are going to take is completely determined by the path we
682 take from the predicate block.
683 We can only use BB dominance checks below if the destination of
684 the true/false edges are dominated by their edge, thus only
685 have a single predecessor. */
686 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
687 tem
= EDGE_PRED (bb
, 0);
689 || (single_pred_p (true_edge
->dest
)
690 && (tem
->src
== true_edge
->dest
691 || dominated_by_p (CDI_DOMINATORS
,
692 tem
->src
, true_edge
->dest
))))
693 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
694 else if (tem
== false_edge
695 || (single_pred_p (false_edge
->dest
)
696 && (tem
->src
== false_edge
->dest
697 || dominated_by_p (CDI_DOMINATORS
,
698 tem
->src
, false_edge
->dest
))))
699 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
702 tem
= EDGE_PRED (bb
, 1);
704 || (single_pred_p (true_edge
->dest
)
705 && (tem
->src
== true_edge
->dest
706 || dominated_by_p (CDI_DOMINATORS
,
707 tem
->src
, true_edge
->dest
))))
708 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
709 else if (tem
== false_edge
710 || (single_pred_p (false_edge
->dest
)
711 && (tem
->src
== false_edge
->dest
712 || dominated_by_p (CDI_DOMINATORS
,
713 tem
->src
, false_edge
->dest
))))
714 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
728 /* Determine the outermost loop to that it is possible to hoist a statement
729 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
730 the outermost loop in that the value computed by STMT is invariant.
731 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
732 we preserve the fact whether STMT is executed. It also fills other related
733 information to LIM_DATA (STMT).
735 The function returns false if STMT cannot be hoisted outside of the loop it
736 is defined in, and true otherwise. */
739 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
741 basic_block bb
= gimple_bb (stmt
);
742 struct loop
*loop
= bb
->loop_father
;
744 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
748 if (must_preserve_exec
)
749 level
= ALWAYS_EXECUTED_IN (bb
);
751 level
= superloop_at_depth (loop
, 1);
752 lim_data
->max_loop
= level
;
754 if (gimple_code (stmt
) == GIMPLE_PHI
)
757 unsigned min_cost
= UINT_MAX
;
758 unsigned total_cost
= 0;
759 struct lim_aux_data
*def_data
;
761 /* We will end up promoting dependencies to be unconditionally
762 evaluated. For this reason the PHI cost (and thus the
763 cost we remove from the loop by doing the invariant motion)
764 is that of the cheapest PHI argument dependency chain. */
765 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
767 val
= USE_FROM_PTR (use_p
);
768 if (TREE_CODE (val
) != SSA_NAME
)
770 if (!add_dependency (val
, lim_data
, loop
, false))
772 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
775 min_cost
= MIN (min_cost
, def_data
->cost
);
776 total_cost
+= def_data
->cost
;
780 lim_data
->cost
+= min_cost
;
782 if (gimple_phi_num_args (stmt
) > 1)
784 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
786 if (gsi_end_p (gsi_last_bb (dom
)))
788 cond
= gsi_stmt (gsi_last_bb (dom
));
789 if (gimple_code (cond
) != GIMPLE_COND
)
791 /* Verify that this is an extended form of a diamond and
792 the PHI arguments are completely controlled by the
794 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
797 /* Fold in dependencies and cost of the condition. */
798 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
800 if (!add_dependency (val
, lim_data
, loop
, false))
802 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
804 total_cost
+= def_data
->cost
;
807 /* We want to avoid unconditionally executing very expensive
808 operations. As costs for our dependencies cannot be
809 negative just claim we are not invariand for this case.
810 We also are not sure whether the control-flow inside the
812 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
814 && total_cost
/ min_cost
<= 2))
817 /* Assume that the control-flow in the loop will vanish.
818 ??? We should verify this and not artificially increase
819 the cost if that is not the case. */
820 lim_data
->cost
+= stmt_cost (stmt
);
826 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
827 if (!add_dependency (val
, lim_data
, loop
, true))
830 if (gimple_vuse (stmt
))
832 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
837 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
838 if (!lim_data
->max_loop
)
843 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
845 if (!add_dependency (val
, lim_data
, loop
, false))
851 lim_data
->cost
+= stmt_cost (stmt
);
856 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
857 and that one of the operands of this statement is computed by STMT.
858 Ensure that STMT (together with all the statements that define its
859 operands) is hoisted at least out of the loop LEVEL. */
862 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
864 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
866 struct lim_aux_data
*lim_data
;
868 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
869 lim_data
= get_lim_data (stmt
);
870 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
871 stmt_loop
= find_common_loop (stmt_loop
,
872 loop_outer (lim_data
->tgt_loop
));
873 if (flow_loop_nested_p (stmt_loop
, level
))
876 gcc_assert (level
== lim_data
->max_loop
877 || flow_loop_nested_p (lim_data
->max_loop
, level
));
879 lim_data
->tgt_loop
= level
;
880 for (dep
= lim_data
->depends
; dep
; dep
= dep
->next
)
881 set_level (dep
->stmt
, orig_loop
, level
);
884 /* Determines an outermost loop from that we want to hoist the statement STMT.
885 For now we chose the outermost possible loop. TODO -- use profiling
886 information to set it more sanely. */
889 set_profitable_level (gimple stmt
)
891 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
894 /* Returns true if STMT is a call that has side effects. */
897 nonpure_call_p (gimple stmt
)
899 if (gimple_code (stmt
) != GIMPLE_CALL
)
902 return gimple_has_side_effects (stmt
);
905 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
908 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
910 gimple stmt
, stmt1
, stmt2
;
911 tree var
, name
, lhs
, type
;
913 gimple_stmt_iterator gsi
;
915 stmt
= gsi_stmt (*bsi
);
916 lhs
= gimple_assign_lhs (stmt
);
917 type
= TREE_TYPE (lhs
);
919 var
= create_tmp_var (type
, "reciptmp");
920 add_referenced_var (var
);
921 DECL_GIMPLE_REG_P (var
) = 1;
923 real_one
= build_one_cst (type
);
925 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
,
926 var
, real_one
, gimple_assign_rhs2 (stmt
));
927 name
= make_ssa_name (var
, stmt1
);
928 gimple_assign_set_lhs (stmt1
, name
);
930 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
931 gimple_assign_rhs1 (stmt
));
933 /* Replace division stmt with reciprocal and multiply stmts.
934 The multiply stmt is not invariant, so update iterator
935 and avoid rescanning. */
937 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
938 gsi_replace (&gsi
, stmt2
, true);
940 /* Continue processing with invariant reciprocal statement. */
944 /* Check if the pattern at *BSI is a bittest of the form
945 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
948 rewrite_bittest (gimple_stmt_iterator
*bsi
)
950 gimple stmt
, use_stmt
, stmt1
, stmt2
;
951 tree lhs
, var
, name
, t
, a
, b
;
954 stmt
= gsi_stmt (*bsi
);
955 lhs
= gimple_assign_lhs (stmt
);
957 /* Verify that the single use of lhs is a comparison against zero. */
958 if (TREE_CODE (lhs
) != SSA_NAME
959 || !single_imm_use (lhs
, &use
, &use_stmt
)
960 || gimple_code (use_stmt
) != GIMPLE_COND
)
962 if (gimple_cond_lhs (use_stmt
) != lhs
963 || (gimple_cond_code (use_stmt
) != NE_EXPR
964 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
965 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
968 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
969 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
970 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
973 /* There is a conversion in between possibly inserted by fold. */
974 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
976 t
= gimple_assign_rhs1 (stmt1
);
977 if (TREE_CODE (t
) != SSA_NAME
978 || !has_single_use (t
))
980 stmt1
= SSA_NAME_DEF_STMT (t
);
981 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
985 /* Verify that B is loop invariant but A is not. Verify that with
986 all the stmt walking we are still in the same loop. */
987 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
988 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
991 a
= gimple_assign_rhs1 (stmt1
);
992 b
= gimple_assign_rhs2 (stmt1
);
994 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
995 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
997 gimple_stmt_iterator rsi
;
1000 var
= create_tmp_var (TREE_TYPE (a
), "shifttmp");
1001 add_referenced_var (var
);
1002 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
1003 build_int_cst (TREE_TYPE (a
), 1), b
);
1004 stmt1
= gimple_build_assign (var
, t
);
1005 name
= make_ssa_name (var
, stmt1
);
1006 gimple_assign_set_lhs (stmt1
, name
);
1009 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
1010 stmt2
= gimple_build_assign (var
, t
);
1011 name
= make_ssa_name (var
, stmt2
);
1012 gimple_assign_set_lhs (stmt2
, name
);
1014 /* Replace the SSA_NAME we compare against zero. Adjust
1015 the type of zero accordingly. */
1016 SET_USE (use
, name
);
1017 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
1019 /* Don't use gsi_replace here, none of the new assignments sets
1020 the variable originally set in stmt. Move bsi to stmt1, and
1021 then remove the original stmt, so that we get a chance to
1022 retain debug info for it. */
1024 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
1025 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
1026 gsi_remove (&rsi
, true);
1035 /* Determine the outermost loops in that statements in basic block BB are
1036 invariant, and record them to the LIM_DATA associated with the statements.
1037 Callback for walk_dominator_tree. */
1040 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1044 gimple_stmt_iterator bsi
;
1046 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1047 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1048 struct lim_aux_data
*lim_data
;
1050 if (!loop_outer (bb
->loop_father
))
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1054 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1055 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1057 /* Look at PHI nodes, but only if there is at most two.
1058 ??? We could relax this further by post-processing the inserted
1059 code and transforming adjacent cond-exprs with the same predicate
1060 to control flow again. */
1061 bsi
= gsi_start_phis (bb
);
1062 if (!gsi_end_p (bsi
)
1063 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1064 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1065 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1067 stmt
= gsi_stmt (bsi
);
1069 pos
= movement_possibility (stmt
);
1070 if (pos
== MOVE_IMPOSSIBLE
)
1073 lim_data
= init_lim_data (stmt
);
1074 lim_data
->always_executed_in
= outermost
;
1076 if (!determine_max_movement (stmt
, false))
1078 lim_data
->max_loop
= NULL
;
1082 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1084 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1085 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1086 loop_depth (lim_data
->max_loop
),
1090 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1091 set_profitable_level (stmt
);
1094 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1096 stmt
= gsi_stmt (bsi
);
1098 pos
= movement_possibility (stmt
);
1099 if (pos
== MOVE_IMPOSSIBLE
)
1101 if (nonpure_call_p (stmt
))
1106 /* Make sure to note always_executed_in for stores to make
1107 store-motion work. */
1108 else if (stmt_makes_single_store (stmt
))
1110 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1111 lim_data
->always_executed_in
= outermost
;
1116 if (is_gimple_assign (stmt
)
1117 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1118 == GIMPLE_BINARY_RHS
))
1120 tree op0
= gimple_assign_rhs1 (stmt
);
1121 tree op1
= gimple_assign_rhs2 (stmt
);
1122 struct loop
*ol1
= outermost_invariant_loop (op1
,
1123 loop_containing_stmt (stmt
));
1125 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1126 to be hoisted out of loop, saving expensive divide. */
1127 if (pos
== MOVE_POSSIBLE
1128 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1129 && flag_unsafe_math_optimizations
1130 && !flag_trapping_math
1132 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1133 stmt
= rewrite_reciprocal (&bsi
);
1135 /* If the shift count is invariant, convert (A >> B) & 1 to
1136 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1137 saving an expensive shift. */
1138 if (pos
== MOVE_POSSIBLE
1139 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1140 && integer_onep (op1
)
1141 && TREE_CODE (op0
) == SSA_NAME
1142 && has_single_use (op0
))
1143 stmt
= rewrite_bittest (&bsi
);
1146 lim_data
= init_lim_data (stmt
);
1147 lim_data
->always_executed_in
= outermost
;
1149 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1152 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1154 lim_data
->max_loop
= NULL
;
1158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1160 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1161 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1162 loop_depth (lim_data
->max_loop
),
1166 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1167 set_profitable_level (stmt
);
1171 /* For each statement determines the outermost loop in that it is invariant,
1172 statements on whose motion it depends and the cost of the computation.
1173 This information is stored to the LIM_DATA structure associated with
1177 determine_invariantness (void)
1179 struct dom_walk_data walk_data
;
1181 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1182 walk_data
.dom_direction
= CDI_DOMINATORS
;
1183 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1185 init_walk_dominator_tree (&walk_data
);
1186 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1187 fini_walk_dominator_tree (&walk_data
);
1190 /* Hoist the statements in basic block BB out of the loops prescribed by
1191 data stored in LIM_DATA structures associated with each statement. Callback
1192 for walk_dominator_tree. */
1195 move_computations_stmt (struct dom_walk_data
*dw_data
,
1199 gimple_stmt_iterator bsi
;
1202 struct lim_aux_data
*lim_data
;
1204 if (!loop_outer (bb
->loop_father
))
1207 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1210 stmt
= gsi_stmt (bsi
);
1212 lim_data
= get_lim_data (stmt
);
1213 if (lim_data
== NULL
)
1219 cost
= lim_data
->cost
;
1220 level
= lim_data
->tgt_loop
;
1221 clear_lim_data (stmt
);
1229 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1231 fprintf (dump_file
, "Moving PHI node\n");
1232 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1233 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1237 if (gimple_phi_num_args (stmt
) == 1)
1239 tree arg
= PHI_ARG_DEF (stmt
, 0);
1240 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1241 gimple_phi_result (stmt
),
1243 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1247 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1248 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1249 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1250 /* Get the PHI arguments corresponding to the true and false
1252 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1253 gcc_assert (arg0
&& arg1
);
1254 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1255 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1256 t
= build3 (COND_EXPR
, TREE_TYPE (gimple_phi_result (stmt
)),
1258 new_stmt
= gimple_build_assign_with_ops (COND_EXPR
,
1259 gimple_phi_result (stmt
),
1261 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1262 *((unsigned int *)(dw_data
->global_data
)) |= TODO_cleanup_cfg
;
1264 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1265 remove_phi_node (&bsi
, false);
1268 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1270 stmt
= gsi_stmt (bsi
);
1272 lim_data
= get_lim_data (stmt
);
1273 if (lim_data
== NULL
)
1279 cost
= lim_data
->cost
;
1280 level
= lim_data
->tgt_loop
;
1281 clear_lim_data (stmt
);
1289 /* We do not really want to move conditionals out of the loop; we just
1290 placed it here to force its operands to be moved if necessary. */
1291 if (gimple_code (stmt
) == GIMPLE_COND
)
1294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1296 fprintf (dump_file
, "Moving statement\n");
1297 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1298 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1302 mark_virtual_ops_for_renaming (stmt
);
1303 gsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
1304 gsi_remove (&bsi
, false);
1308 /* Hoist the statements out of the loops prescribed by data stored in
1309 LIM_DATA structures associated with each statement.*/
1312 move_computations (void)
1314 struct dom_walk_data walk_data
;
1315 unsigned int todo
= 0;
1317 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1318 walk_data
.global_data
= &todo
;
1319 walk_data
.dom_direction
= CDI_DOMINATORS
;
1320 walk_data
.before_dom_children
= move_computations_stmt
;
1322 init_walk_dominator_tree (&walk_data
);
1323 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1324 fini_walk_dominator_tree (&walk_data
);
1326 gsi_commit_edge_inserts ();
1327 if (need_ssa_update_p (cfun
))
1328 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1333 /* Checks whether the statement defining variable *INDEX can be hoisted
1334 out of the loop passed in DATA. Callback for for_each_index. */
1337 may_move_till (tree ref
, tree
*index
, void *data
)
1339 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1341 /* If REF is an array reference, check also that the step and the lower
1342 bound is invariant in LOOP. */
1343 if (TREE_CODE (ref
) == ARRAY_REF
)
1345 tree step
= TREE_OPERAND (ref
, 3);
1346 tree lbound
= TREE_OPERAND (ref
, 2);
1348 max_loop
= outermost_invariant_loop (step
, loop
);
1352 max_loop
= outermost_invariant_loop (lbound
, loop
);
1357 max_loop
= outermost_invariant_loop (*index
, loop
);
1364 /* If OP is SSA NAME, force the statement that defines it to be
1365 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1368 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1373 || is_gimple_min_invariant (op
))
1376 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1378 stmt
= SSA_NAME_DEF_STMT (op
);
1379 if (gimple_nop_p (stmt
))
1382 set_level (stmt
, orig_loop
, loop
);
1385 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1386 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1392 struct loop
*orig_loop
;
1396 force_move_till (tree ref
, tree
*index
, void *data
)
1398 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1400 if (TREE_CODE (ref
) == ARRAY_REF
)
1402 tree step
= TREE_OPERAND (ref
, 3);
1403 tree lbound
= TREE_OPERAND (ref
, 2);
1405 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1406 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1409 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1414 /* A hash function for struct mem_ref object OBJ. */
1417 memref_hash (const void *obj
)
1419 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1424 /* An equality function for struct mem_ref object OBJ1 with
1425 memory reference OBJ2. */
1428 memref_eq (const void *obj1
, const void *obj2
)
1430 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1432 return operand_equal_p (mem1
->mem
, (const_tree
) obj2
, 0);
1435 /* Releases list of memory reference locations ACCS. */
1438 free_mem_ref_locs (mem_ref_locs_p accs
)
1446 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1448 VEC_free (mem_ref_loc_p
, heap
, accs
->locs
);
1452 /* A function to free the mem_ref object OBJ. */
1455 memref_free (void *obj
)
1457 struct mem_ref
*const mem
= (struct mem_ref
*) obj
;
1459 mem_ref_locs_p accs
;
1461 BITMAP_FREE (mem
->stored
);
1462 BITMAP_FREE (mem
->indep_loop
);
1463 BITMAP_FREE (mem
->dep_loop
);
1464 BITMAP_FREE (mem
->indep_ref
);
1465 BITMAP_FREE (mem
->dep_ref
);
1467 FOR_EACH_VEC_ELT (mem_ref_locs_p
, mem
->accesses_in_loop
, i
, accs
)
1468 free_mem_ref_locs (accs
);
1469 VEC_free (mem_ref_locs_p
, heap
, mem
->accesses_in_loop
);
1471 BITMAP_FREE (mem
->vops
);
1475 /* Allocates and returns a memory reference description for MEM whose hash
1476 value is HASH and id is ID. */
1479 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1481 mem_ref_p ref
= XNEW (struct mem_ref
);
1485 ref
->stored
= BITMAP_ALLOC (NULL
);
1486 ref
->indep_loop
= BITMAP_ALLOC (NULL
);
1487 ref
->dep_loop
= BITMAP_ALLOC (NULL
);
1488 ref
->indep_ref
= BITMAP_ALLOC (NULL
);
1489 ref
->dep_ref
= BITMAP_ALLOC (NULL
);
1490 ref
->accesses_in_loop
= NULL
;
1491 ref
->vops
= BITMAP_ALLOC (NULL
);
1496 /* Allocates and returns the new list of locations. */
1498 static mem_ref_locs_p
1499 mem_ref_locs_alloc (void)
1501 mem_ref_locs_p accs
= XNEW (struct mem_ref_locs
);
1506 /* Records memory reference location *LOC in LOOP to the memory reference
1507 description REF. The reference occurs in statement STMT. */
1510 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1512 mem_ref_loc_p aref
= XNEW (struct mem_ref_loc
);
1513 mem_ref_locs_p accs
;
1514 bitmap ril
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1516 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1517 <= (unsigned) loop
->num
)
1518 VEC_safe_grow_cleared (mem_ref_locs_p
, heap
, ref
->accesses_in_loop
,
1520 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1523 accs
= mem_ref_locs_alloc ();
1524 VEC_replace (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
, accs
);
1530 VEC_safe_push (mem_ref_loc_p
, heap
, accs
->locs
, aref
);
1531 bitmap_set_bit (ril
, ref
->id
);
1534 /* Marks reference REF as stored in LOOP. */
1537 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1540 loop
!= current_loops
->tree_root
1541 && !bitmap_bit_p (ref
->stored
, loop
->num
);
1542 loop
= loop_outer (loop
))
1543 bitmap_set_bit (ref
->stored
, loop
->num
);
1546 /* Gathers memory references in statement STMT in LOOP, storing the
1547 information about them in the memory_accesses structure. Marks
1548 the vops accessed through unrecognized statements there as
1552 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1563 if (!gimple_vuse (stmt
))
1566 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1570 hash
= iterative_hash_expr (*mem
, 0);
1571 slot
= htab_find_slot_with_hash (memory_accesses
.refs
, *mem
, hash
, INSERT
);
1575 ref
= (mem_ref_p
) *slot
;
1580 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1581 ref
= mem_ref_alloc (*mem
, hash
, id
);
1582 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1587 fprintf (dump_file
, "Memory reference %u: ", id
);
1588 print_generic_expr (dump_file
, ref
->mem
, TDF_SLIM
);
1589 fprintf (dump_file
, "\n");
1593 mark_ref_stored (ref
, loop
);
1595 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1596 bitmap_set_bit (ref
->vops
, DECL_UID (SSA_NAME_VAR (vname
)));
1597 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1601 clvops
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1602 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1603 bitmap_set_bit (clvops
, DECL_UID (SSA_NAME_VAR (vname
)));
1606 /* Gathers memory references in loops. */
1609 gather_mem_refs_in_loops (void)
1611 gimple_stmt_iterator bsi
;
1616 bitmap lrefs
, alrefs
, alrefso
;
1620 loop
= bb
->loop_father
;
1621 if (loop
== current_loops
->tree_root
)
1624 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1625 gather_mem_refs_stmt (loop
, gsi_stmt (bsi
));
1628 /* Propagate the information about clobbered vops and accessed memory
1629 references up the loop hierarchy. */
1630 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1632 lrefs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1633 alrefs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
, loop
->num
);
1634 bitmap_ior_into (alrefs
, lrefs
);
1636 if (loop_outer (loop
) == current_loops
->tree_root
)
1639 clvi
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1640 clvo
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1641 loop_outer (loop
)->num
);
1642 bitmap_ior_into (clvo
, clvi
);
1644 alrefso
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1645 loop_outer (loop
)->num
);
1646 bitmap_ior_into (alrefso
, alrefs
);
1650 /* Element of the hash table that maps vops to memory references. */
1652 struct vop_to_refs_elt
1654 /* DECL_UID of the vop. */
1657 /* List of the all references. */
1660 /* List of stored references. */
1664 /* A hash function for struct vop_to_refs_elt object OBJ. */
1667 vtoe_hash (const void *obj
)
1669 const struct vop_to_refs_elt
*const vtoe
=
1670 (const struct vop_to_refs_elt
*) obj
;
1675 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1676 uid of a vop OBJ2. */
1679 vtoe_eq (const void *obj1
, const void *obj2
)
1681 const struct vop_to_refs_elt
*const vtoe
=
1682 (const struct vop_to_refs_elt
*) obj1
;
1683 const unsigned *const uid
= (const unsigned *) obj2
;
1685 return vtoe
->uid
== *uid
;
1688 /* A function to free the struct vop_to_refs_elt object. */
1691 vtoe_free (void *obj
)
1693 struct vop_to_refs_elt
*const vtoe
=
1694 (struct vop_to_refs_elt
*) obj
;
1696 BITMAP_FREE (vtoe
->refs_all
);
1697 BITMAP_FREE (vtoe
->refs_stored
);
1701 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1702 if the reference REF is stored. */
1705 record_vop_access (htab_t vop_to_refs
, unsigned vop
, unsigned ref
, bool stored
)
1707 void **slot
= htab_find_slot_with_hash (vop_to_refs
, &vop
, vop
, INSERT
);
1708 struct vop_to_refs_elt
*vtoe
;
1712 vtoe
= XNEW (struct vop_to_refs_elt
);
1714 vtoe
->refs_all
= BITMAP_ALLOC (NULL
);
1715 vtoe
->refs_stored
= BITMAP_ALLOC (NULL
);
1719 vtoe
= (struct vop_to_refs_elt
*) *slot
;
1721 bitmap_set_bit (vtoe
->refs_all
, ref
);
1723 bitmap_set_bit (vtoe
->refs_stored
, ref
);
1726 /* Returns the set of references that access VOP according to the table
1730 get_vop_accesses (htab_t vop_to_refs
, unsigned vop
)
1732 struct vop_to_refs_elt
*const vtoe
=
1733 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1734 return vtoe
->refs_all
;
1737 /* Returns the set of stores that access VOP according to the table
1741 get_vop_stores (htab_t vop_to_refs
, unsigned vop
)
1743 struct vop_to_refs_elt
*const vtoe
=
1744 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1745 return vtoe
->refs_stored
;
1748 /* Adds REF to mapping from virtual operands to references in LOOP. */
1751 add_vop_ref_mapping (struct loop
*loop
, mem_ref_p ref
)
1753 htab_t map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
1754 bool stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
1755 bitmap clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1760 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, vop
, bi
)
1762 record_vop_access (map
, vop
, ref
->id
, stored
);
1766 /* Create a mapping from virtual operands to references that touch them
1770 create_vop_ref_mapping_loop (struct loop
*loop
)
1772 bitmap refs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1778 EXECUTE_IF_SET_IN_BITMAP (refs
, 0, i
, bi
)
1780 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1781 for (sloop
= loop
; sloop
!= current_loops
->tree_root
; sloop
= loop_outer (sloop
))
1782 add_vop_ref_mapping (sloop
, ref
);
1786 /* For each non-clobbered virtual operand and each loop, record the memory
1787 references in this loop that touch the operand. */
1790 create_vop_ref_mapping (void)
1795 FOR_EACH_LOOP (li
, loop
, 0)
1797 create_vop_ref_mapping_loop (loop
);
1801 /* Gathers information about memory accesses in the loops. */
1804 analyze_memory_references (void)
1810 memory_accesses
.refs
1811 = htab_create (100, memref_hash
, memref_eq
, memref_free
);
1812 memory_accesses
.refs_list
= NULL
;
1813 memory_accesses
.refs_in_loop
= VEC_alloc (bitmap
, heap
,
1814 number_of_loops ());
1815 memory_accesses
.all_refs_in_loop
= VEC_alloc (bitmap
, heap
,
1816 number_of_loops ());
1817 memory_accesses
.clobbered_vops
= VEC_alloc (bitmap
, heap
,
1818 number_of_loops ());
1819 memory_accesses
.vop_ref_map
= VEC_alloc (htab_t
, heap
,
1820 number_of_loops ());
1822 for (i
= 0; i
< number_of_loops (); i
++)
1824 empty
= BITMAP_ALLOC (NULL
);
1825 VEC_quick_push (bitmap
, memory_accesses
.refs_in_loop
, empty
);
1826 empty
= BITMAP_ALLOC (NULL
);
1827 VEC_quick_push (bitmap
, memory_accesses
.all_refs_in_loop
, empty
);
1828 empty
= BITMAP_ALLOC (NULL
);
1829 VEC_quick_push (bitmap
, memory_accesses
.clobbered_vops
, empty
);
1830 hempty
= htab_create (10, vtoe_hash
, vtoe_eq
, vtoe_free
);
1831 VEC_quick_push (htab_t
, memory_accesses
.vop_ref_map
, hempty
);
1834 memory_accesses
.ttae_cache
= NULL
;
1836 gather_mem_refs_in_loops ();
1837 create_vop_ref_mapping ();
1840 /* Returns true if a region of size SIZE1 at position 0 and a region of
1841 size SIZE2 at position DIFF cannot overlap. */
1844 cannot_overlap_p (aff_tree
*diff
, double_int size1
, double_int size2
)
1846 double_int d
, bound
;
1848 /* Unless the difference is a constant, we fail. */
1853 if (double_int_negative_p (d
))
1855 /* The second object is before the first one, we succeed if the last
1856 element of the second object is before the start of the first one. */
1857 bound
= double_int_add (d
, double_int_add (size2
, double_int_minus_one
));
1858 return double_int_negative_p (bound
);
1862 /* We succeed if the second object starts after the first one ends. */
1863 return double_int_scmp (size1
, d
) <= 0;
1867 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1868 tree_to_aff_combination_expand. */
1871 mem_refs_may_alias_p (tree mem1
, tree mem2
, struct pointer_map_t
**ttae_cache
)
1873 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1874 object and their offset differ in such a way that the locations cannot
1875 overlap, then they cannot alias. */
1876 double_int size1
, size2
;
1877 aff_tree off1
, off2
;
1879 /* Perform basic offset and type-based disambiguation. */
1880 if (!refs_may_alias_p (mem1
, mem2
))
1883 /* The expansion of addresses may be a bit expensive, thus we only do
1884 the check at -O2 and higher optimization levels. */
1888 get_inner_reference_aff (mem1
, &off1
, &size1
);
1889 get_inner_reference_aff (mem2
, &off2
, &size2
);
1890 aff_combination_expand (&off1
, ttae_cache
);
1891 aff_combination_expand (&off2
, ttae_cache
);
1892 aff_combination_scale (&off1
, double_int_minus_one
);
1893 aff_combination_add (&off2
, &off1
);
1895 if (cannot_overlap_p (&off2
, size1
, size2
))
1901 /* Rewrites location LOC by TMP_VAR. */
1904 rewrite_mem_ref_loc (mem_ref_loc_p loc
, tree tmp_var
)
1906 mark_virtual_ops_for_renaming (loc
->stmt
);
1907 *loc
->ref
= tmp_var
;
1908 update_stmt (loc
->stmt
);
1911 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1914 get_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
,
1915 VEC (mem_ref_loc_p
, heap
) **locs
)
1917 mem_ref_locs_p accs
;
1920 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1922 struct loop
*subloop
;
1924 if (!bitmap_bit_p (refs
, ref
->id
))
1927 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1928 > (unsigned) loop
->num
)
1930 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1933 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1934 VEC_safe_push (mem_ref_loc_p
, heap
, *locs
, loc
);
1938 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1939 get_all_locs_in_loop (subloop
, ref
, locs
);
1942 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1945 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1949 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1951 get_all_locs_in_loop (loop
, ref
, &locs
);
1952 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
1953 rewrite_mem_ref_loc (loc
, tmp_var
);
1954 VEC_free (mem_ref_loc_p
, heap
, locs
);
1957 /* The name and the length of the currently generated variable
1959 #define MAX_LSM_NAME_LENGTH 40
1960 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1961 static int lsm_tmp_name_length
;
1963 /* Adds S to lsm_tmp_name. */
1966 lsm_tmp_name_add (const char *s
)
1968 int l
= strlen (s
) + lsm_tmp_name_length
;
1969 if (l
> MAX_LSM_NAME_LENGTH
)
1972 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1973 lsm_tmp_name_length
= l
;
1976 /* Stores the name for temporary variable that replaces REF to
1980 gen_lsm_tmp_name (tree ref
)
1984 switch (TREE_CODE (ref
))
1987 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1988 lsm_tmp_name_add ("_");
1992 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1996 case VIEW_CONVERT_EXPR
:
1997 case ARRAY_RANGE_REF
:
1998 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2002 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2003 lsm_tmp_name_add ("_RE");
2007 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2008 lsm_tmp_name_add ("_IM");
2012 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2013 lsm_tmp_name_add ("_");
2014 name
= get_name (TREE_OPERAND (ref
, 1));
2017 lsm_tmp_name_add (name
);
2021 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2022 lsm_tmp_name_add ("_I");
2026 ref
= SSA_NAME_VAR (ref
);
2031 name
= get_name (ref
);
2034 lsm_tmp_name_add (name
);
2038 lsm_tmp_name_add ("S");
2042 lsm_tmp_name_add ("R");
2054 /* Determines name for temporary variable that replaces REF.
2055 The name is accumulated into the lsm_tmp_name variable.
2056 N is added to the name of the temporary. */
2059 get_lsm_tmp_name (tree ref
, unsigned n
)
2063 lsm_tmp_name_length
= 0;
2064 gen_lsm_tmp_name (ref
);
2065 lsm_tmp_name_add ("_lsm");
2070 lsm_tmp_name_add (ns
);
2072 return lsm_tmp_name
;
2075 /* Executes store motion of memory reference REF from LOOP.
2076 Exits from the LOOP are stored in EXITS. The initialization of the
2077 temporary variable is put to the preheader of the loop, and assignments
2078 to the reference from the temporary variable are emitted to exits. */
2081 execute_sm (struct loop
*loop
, VEC (edge
, heap
) *exits
, mem_ref_p ref
)
2086 struct fmt_data fmt_data
;
2088 struct lim_aux_data
*lim_data
;
2090 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2092 fprintf (dump_file
, "Executing store motion of ");
2093 print_generic_expr (dump_file
, ref
->mem
, 0);
2094 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2097 tmp_var
= make_rename_temp (TREE_TYPE (ref
->mem
),
2098 get_lsm_tmp_name (ref
->mem
, ~0));
2100 fmt_data
.loop
= loop
;
2101 fmt_data
.orig_loop
= loop
;
2102 for_each_index (&ref
->mem
, force_move_till
, &fmt_data
);
2104 rewrite_mem_refs (loop
, ref
, tmp_var
);
2106 /* Emit the load & stores. */
2107 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
));
2108 lim_data
= init_lim_data (load
);
2109 lim_data
->max_loop
= loop
;
2110 lim_data
->tgt_loop
= loop
;
2112 /* Put this into the latch, so that we are sure it will be processed after
2113 all dependencies. */
2114 gsi_insert_on_edge (loop_latch_edge (loop
), load
);
2116 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2118 store
= gimple_build_assign (unshare_expr (ref
->mem
), tmp_var
);
2119 gsi_insert_on_edge (ex
, store
);
2123 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2124 edges of the LOOP. */
2127 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2128 VEC (edge
, heap
) *exits
)
2134 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2136 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2137 execute_sm (loop
, exits
, ref
);
2141 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2142 make sure REF is always stored to in LOOP. */
2145 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2147 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
2151 struct loop
*must_exec
;
2154 base
= get_base_address (ref
->mem
);
2155 if (INDIRECT_REF_P (base
)
2156 || TREE_CODE (base
) == MEM_REF
)
2157 base
= TREE_OPERAND (base
, 0);
2159 get_all_locs_in_loop (loop
, ref
, &locs
);
2160 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
2162 if (!get_lim_data (loc
->stmt
))
2165 /* If we require an always executed store make sure the statement
2166 stores to the reference. */
2170 if (!gimple_get_lhs (loc
->stmt
))
2172 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2175 if (INDIRECT_REF_P (lhs
)
2176 || TREE_CODE (lhs
) == MEM_REF
)
2177 lhs
= TREE_OPERAND (lhs
, 0);
2182 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2186 if (must_exec
== loop
2187 || flow_loop_nested_p (must_exec
, loop
))
2193 VEC_free (mem_ref_loc_p
, heap
, locs
);
2198 /* Returns true if REF1 and REF2 are independent. */
2201 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2204 || bitmap_bit_p (ref1
->indep_ref
, ref2
->id
))
2206 if (bitmap_bit_p (ref1
->dep_ref
, ref2
->id
))
2209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2210 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2211 ref1
->id
, ref2
->id
);
2213 if (mem_refs_may_alias_p (ref1
->mem
, ref2
->mem
,
2214 &memory_accesses
.ttae_cache
))
2216 bitmap_set_bit (ref1
->dep_ref
, ref2
->id
);
2217 bitmap_set_bit (ref2
->dep_ref
, ref1
->id
);
2218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2219 fprintf (dump_file
, "dependent.\n");
2224 bitmap_set_bit (ref1
->indep_ref
, ref2
->id
);
2225 bitmap_set_bit (ref2
->indep_ref
, ref1
->id
);
2226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2227 fprintf (dump_file
, "independent.\n");
2232 /* Records the information whether REF is independent in LOOP (according
2236 record_indep_loop (struct loop
*loop
, mem_ref_p ref
, bool indep
)
2239 bitmap_set_bit (ref
->indep_loop
, loop
->num
);
2241 bitmap_set_bit (ref
->dep_loop
, loop
->num
);
2244 /* Returns true if REF is independent on all other memory references in
2248 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
)
2250 bitmap clobbers
, refs_to_check
, refs
;
2253 bool ret
= true, stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
2257 /* If the reference is clobbered, it is not independent. */
2258 clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
2259 if (bitmap_intersect_p (ref
->vops
, clobbers
))
2262 refs_to_check
= BITMAP_ALLOC (NULL
);
2264 map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
2265 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, i
, bi
)
2268 refs
= get_vop_accesses (map
, i
);
2270 refs
= get_vop_stores (map
, i
);
2272 bitmap_ior_into (refs_to_check
, refs
);
2275 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2277 aref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2278 if (!refs_independent_p (ref
, aref
))
2281 record_indep_loop (loop
, aref
, false);
2286 BITMAP_FREE (refs_to_check
);
2290 /* Returns true if REF is independent on all other memory references in
2291 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2294 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2298 if (bitmap_bit_p (ref
->indep_loop
, loop
->num
))
2300 if (bitmap_bit_p (ref
->dep_loop
, loop
->num
))
2303 ret
= ref_indep_loop_p_1 (loop
, ref
);
2305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2306 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2307 ref
->id
, loop
->num
, ret
? "independent" : "dependent");
2309 record_indep_loop (loop
, ref
, ret
);
2314 /* Returns true if we can perform store motion of REF from LOOP. */
2317 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2321 /* Unless the reference is stored in the loop, there is nothing to do. */
2322 if (!bitmap_bit_p (ref
->stored
, loop
->num
))
2325 /* It should be movable. */
2326 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
))
2327 || TREE_THIS_VOLATILE (ref
->mem
)
2328 || !for_each_index (&ref
->mem
, may_move_till
, loop
))
2331 /* If it can throw fail, we do not properly update EH info. */
2332 if (tree_could_throw_p (ref
->mem
))
2335 /* If it can trap, it must be always executed in LOOP.
2336 Readonly memory locations may trap when storing to them, but
2337 tree_could_trap_p is a predicate for rvalues, so check that
2339 base
= get_base_address (ref
->mem
);
2340 if ((tree_could_trap_p (ref
->mem
)
2341 || (DECL_P (base
) && TREE_READONLY (base
)))
2342 && !ref_always_accessed_p (loop
, ref
, true))
2345 /* And it must be independent on all other memory references
2347 if (!ref_indep_loop_p (loop
, ref
))
2353 /* Marks the references in LOOP for that store motion should be performed
2354 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2355 motion was performed in one of the outer loops. */
2358 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2360 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
2365 unsigned sm_count
= 0;
2367 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2369 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2370 if (sm_count
< maximum_lsm
&& can_sm_ref_p (loop
, ref
))
2372 bitmap_set_bit (refs_to_sm
, i
);
2378 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2379 for a store motion optimization (i.e. whether we can insert statement
2383 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2384 VEC (edge
, heap
) *exits
)
2389 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2390 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2396 /* Try to perform store motion for all memory references modified inside
2397 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2398 store motion was executed in one of the outer loops. */
2401 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2403 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2404 struct loop
*subloop
;
2405 bitmap sm_in_loop
= BITMAP_ALLOC (NULL
);
2407 if (loop_suitable_for_sm (loop
, exits
))
2409 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2410 hoist_memory_references (loop
, sm_in_loop
, exits
);
2412 VEC_free (edge
, heap
, exits
);
2414 bitmap_ior_into (sm_executed
, sm_in_loop
);
2415 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2416 store_motion_loop (subloop
, sm_executed
);
2417 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2418 BITMAP_FREE (sm_in_loop
);
2421 /* Try to perform store motion for all memory references modified inside
2428 bitmap sm_executed
= BITMAP_ALLOC (NULL
);
2430 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2431 store_motion_loop (loop
, sm_executed
);
2433 BITMAP_FREE (sm_executed
);
2434 gsi_commit_edge_inserts ();
2437 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2438 for each such basic block bb records the outermost loop for that execution
2439 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2440 blocks that contain a nonpure call. */
2443 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
2445 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2448 struct loop
*inn_loop
= loop
;
2450 if (!loop
->header
->aux
)
2452 bbs
= get_loop_body_in_dom_order (loop
);
2454 for (i
= 0; i
< loop
->num_nodes
; i
++)
2459 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2462 if (TEST_BIT (contains_call
, bb
->index
))
2465 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2466 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2471 /* A loop might be infinite (TODO use simple loop analysis
2472 to disprove this if possible). */
2473 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2476 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2479 if (bb
->loop_father
->header
== bb
)
2481 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2484 /* In a loop that is always entered we may proceed anyway.
2485 But record that we entered it and stop once we leave it. */
2486 inn_loop
= bb
->loop_father
;
2493 if (last
== loop
->header
)
2495 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2501 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2502 fill_always_executed_in (loop
, contains_call
);
2505 /* Compute the global information needed by the loop invariant motion pass. */
2508 tree_ssa_lim_initialize (void)
2510 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2511 gimple_stmt_iterator bsi
;
2515 sbitmap_zero (contains_call
);
2518 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2520 if (nonpure_call_p (gsi_stmt (bsi
)))
2524 if (!gsi_end_p (bsi
))
2525 SET_BIT (contains_call
, bb
->index
);
2528 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2529 fill_always_executed_in (loop
, contains_call
);
2531 sbitmap_free (contains_call
);
2533 lim_aux_data_map
= pointer_map_create ();
2535 /* Supress execeesive store-motion. Minus target_avail_regs by 1
2536 for the induction varialbe. Maybe we should use even less? */
2537 maximum_lsm
= (target_avail_regs
< 1 ? 0 : target_avail_regs
- 1);
2540 /* Cleans up after the invariant motion pass. */
2543 tree_ssa_lim_finalize (void)
2555 pointer_map_destroy (lim_aux_data_map
);
2557 VEC_free (mem_ref_p
, heap
, memory_accesses
.refs_list
);
2558 htab_delete (memory_accesses
.refs
);
2560 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.refs_in_loop
, i
, b
)
2562 VEC_free (bitmap
, heap
, memory_accesses
.refs_in_loop
);
2564 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.all_refs_in_loop
, i
, b
)
2566 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_in_loop
);
2568 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.clobbered_vops
, i
, b
)
2570 VEC_free (bitmap
, heap
, memory_accesses
.clobbered_vops
);
2572 FOR_EACH_VEC_ELT (htab_t
, memory_accesses
.vop_ref_map
, i
, h
)
2574 VEC_free (htab_t
, heap
, memory_accesses
.vop_ref_map
);
2576 if (memory_accesses
.ttae_cache
)
2577 pointer_map_destroy (memory_accesses
.ttae_cache
);
2580 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2581 i.e. those that are likely to be win regardless of the register pressure. */
2588 tree_ssa_lim_initialize ();
2590 /* Gathers information about memory accesses in the loops. */
2591 analyze_memory_references ();
2593 /* For each statement determine the outermost loop in that it is
2594 invariant and cost for computing the invariant. */
2595 determine_invariantness ();
2597 /* Execute store motion. Force the necessary invariants to be moved
2598 out of the loops as well. */
2601 /* Move the expressions that are expensive enough. */
2602 todo
= move_computations ();
2604 tree_ssa_lim_finalize ();