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 /* Maps statements to their lim_aux_data. */
102 static struct pointer_map_t
*lim_aux_data_map
;
104 /* Description of a memory reference location. */
106 typedef struct mem_ref_loc
108 tree
*ref
; /* The reference itself. */
109 gimple stmt
; /* The statement in that it occurs. */
112 DEF_VEC_P(mem_ref_loc_p
);
113 DEF_VEC_ALLOC_P(mem_ref_loc_p
, heap
);
115 /* The list of memory reference locations in a loop. */
117 typedef struct mem_ref_locs
119 VEC (mem_ref_loc_p
, heap
) *locs
;
122 DEF_VEC_P(mem_ref_locs_p
);
123 DEF_VEC_ALLOC_P(mem_ref_locs_p
, heap
);
125 /* Description of a memory reference. */
127 typedef struct mem_ref
129 tree mem
; /* The memory itself. */
130 unsigned id
; /* ID assigned to the memory reference
131 (its index in memory_accesses.refs_list) */
132 hashval_t hash
; /* Its hash value. */
133 bitmap stored
; /* The set of loops in that this memory location
135 VEC (mem_ref_locs_p
, heap
) *accesses_in_loop
;
136 /* The locations of the accesses. Vector
137 indexed by the loop number. */
138 bitmap vops
; /* Vops corresponding to this memory
141 /* The following sets are computed on demand. We keep both set and
142 its complement, so that we know whether the information was
143 already computed or not. */
144 bitmap indep_loop
; /* The set of loops in that the memory
145 reference is independent, meaning:
146 If it is stored in the loop, this store
147 is independent on all other loads and
149 If it is only loaded, then it is independent
150 on all stores in the loop. */
151 bitmap dep_loop
; /* The complement of INDEP_LOOP. */
153 bitmap indep_ref
; /* The set of memory references on that
154 this reference is independent. */
155 bitmap dep_ref
; /* The complement of DEP_REF. */
158 DEF_VEC_P(mem_ref_p
);
159 DEF_VEC_ALLOC_P(mem_ref_p
, heap
);
162 DEF_VEC_ALLOC_P(bitmap
, heap
);
165 DEF_VEC_ALLOC_P(htab_t
, heap
);
167 /* Description of memory accesses in loops. */
171 /* The hash table of memory references accessed in loops. */
174 /* The list of memory references. */
175 VEC (mem_ref_p
, heap
) *refs_list
;
177 /* The set of memory references accessed in each loop. */
178 VEC (bitmap
, heap
) *refs_in_loop
;
180 /* The set of memory references accessed in each loop, including
182 VEC (bitmap
, heap
) *all_refs_in_loop
;
184 /* The set of virtual operands clobbered in a given loop. */
185 VEC (bitmap
, heap
) *clobbered_vops
;
187 /* Map from the pair (loop, virtual operand) to the set of refs that
188 touch the virtual operand in the loop. */
189 VEC (htab_t
, heap
) *vop_ref_map
;
191 /* Cache for expanding memory addresses. */
192 struct pointer_map_t
*ttae_cache
;
195 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
197 /* Minimum cost of an expensive expression. */
198 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
200 /* The outermost loop for which execution of the header guarantees that the
201 block will be executed. */
202 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
203 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
205 static struct lim_aux_data
*
206 init_lim_data (gimple stmt
)
208 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
210 *p
= XCNEW (struct lim_aux_data
);
211 return (struct lim_aux_data
*) *p
;
214 static struct lim_aux_data
*
215 get_lim_data (gimple stmt
)
217 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
221 return (struct lim_aux_data
*) *p
;
224 /* Releases the memory occupied by DATA. */
227 free_lim_aux_data (struct lim_aux_data
*data
)
229 struct depend
*dep
, *next
;
231 for (dep
= data
->depends
; dep
; dep
= next
)
240 clear_lim_data (gimple stmt
)
242 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
246 free_lim_aux_data ((struct lim_aux_data
*) *p
);
250 /* Calls CBCK for each index in memory reference ADDR_P. There are two
251 kinds situations handled; in each of these cases, the memory reference
252 and DATA are passed to the callback:
254 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
255 pass the pointer to the index to the callback.
257 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
258 pointer to addr to the callback.
260 If the callback returns false, the whole search stops and false is returned.
261 Otherwise the function returns true after traversing through the whole
262 reference *ADDR_P. */
265 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
269 for (; ; addr_p
= nxt
)
271 switch (TREE_CODE (*addr_p
))
274 return cbck (*addr_p
, addr_p
, data
);
277 nxt
= &TREE_OPERAND (*addr_p
, 0);
278 return cbck (*addr_p
, nxt
, data
);
281 case VIEW_CONVERT_EXPR
:
284 nxt
= &TREE_OPERAND (*addr_p
, 0);
288 /* If the component has varying offset, it behaves like index
290 idx
= &TREE_OPERAND (*addr_p
, 2);
292 && !cbck (*addr_p
, idx
, data
))
295 nxt
= &TREE_OPERAND (*addr_p
, 0);
299 case ARRAY_RANGE_REF
:
300 nxt
= &TREE_OPERAND (*addr_p
, 0);
301 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
318 gcc_assert (is_gimple_min_invariant (*addr_p
));
322 idx
= &TMR_BASE (*addr_p
);
324 && !cbck (*addr_p
, idx
, data
))
326 idx
= &TMR_INDEX (*addr_p
);
328 && !cbck (*addr_p
, idx
, data
))
330 idx
= &TMR_INDEX2 (*addr_p
);
332 && !cbck (*addr_p
, idx
, data
))
342 /* If it is possible to hoist the statement STMT unconditionally,
343 returns MOVE_POSSIBLE.
344 If it is possible to hoist the statement STMT, but we must avoid making
345 it executed if it would not be executed in the original program (e.g.
346 because it may trap), return MOVE_PRESERVE_EXECUTION.
347 Otherwise return MOVE_IMPOSSIBLE. */
350 movement_possibility (gimple stmt
)
353 enum move_pos ret
= MOVE_POSSIBLE
;
355 if (flag_unswitch_loops
356 && gimple_code (stmt
) == GIMPLE_COND
)
358 /* If we perform unswitching, force the operands of the invariant
359 condition to be moved out of the loop. */
360 return MOVE_POSSIBLE
;
363 if (gimple_code (stmt
) == GIMPLE_PHI
364 && gimple_phi_num_args (stmt
) <= 2
365 && is_gimple_reg (gimple_phi_result (stmt
))
366 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
367 return MOVE_POSSIBLE
;
369 if (gimple_get_lhs (stmt
) == NULL_TREE
)
370 return MOVE_IMPOSSIBLE
;
372 if (gimple_vdef (stmt
))
373 return MOVE_IMPOSSIBLE
;
375 if (stmt_ends_bb_p (stmt
)
376 || gimple_has_volatile_ops (stmt
)
377 || gimple_has_side_effects (stmt
)
378 || stmt_could_throw_p (stmt
))
379 return MOVE_IMPOSSIBLE
;
381 if (is_gimple_call (stmt
))
383 /* While pure or const call is guaranteed to have no side effects, we
384 cannot move it arbitrarily. Consider code like
386 char *s = something ();
396 Here the strlen call cannot be moved out of the loop, even though
397 s is invariant. In addition to possibly creating a call with
398 invalid arguments, moving out a function call that is not executed
399 may cause performance regressions in case the call is costly and
400 not executed at all. */
401 ret
= MOVE_PRESERVE_EXECUTION
;
402 lhs
= gimple_call_lhs (stmt
);
404 else if (is_gimple_assign (stmt
))
405 lhs
= gimple_assign_lhs (stmt
);
407 return MOVE_IMPOSSIBLE
;
409 if (TREE_CODE (lhs
) == SSA_NAME
410 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
411 return MOVE_IMPOSSIBLE
;
413 if (TREE_CODE (lhs
) != SSA_NAME
414 || gimple_could_trap_p (stmt
))
415 return MOVE_PRESERVE_EXECUTION
;
420 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
421 loop to that we could move the expression using DEF if it did not have
422 other operands, i.e. the outermost loop enclosing LOOP in that the value
423 of DEF is invariant. */
426 outermost_invariant_loop (tree def
, struct loop
*loop
)
430 struct loop
*max_loop
;
431 struct lim_aux_data
*lim_data
;
434 return superloop_at_depth (loop
, 1);
436 if (TREE_CODE (def
) != SSA_NAME
)
438 gcc_assert (is_gimple_min_invariant (def
));
439 return superloop_at_depth (loop
, 1);
442 def_stmt
= SSA_NAME_DEF_STMT (def
);
443 def_bb
= gimple_bb (def_stmt
);
445 return superloop_at_depth (loop
, 1);
447 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
449 lim_data
= get_lim_data (def_stmt
);
450 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
451 max_loop
= find_common_loop (max_loop
,
452 loop_outer (lim_data
->max_loop
));
453 if (max_loop
== loop
)
455 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
460 /* DATA is a structure containing information associated with a statement
461 inside LOOP. DEF is one of the operands of this statement.
463 Find the outermost loop enclosing LOOP in that value of DEF is invariant
464 and record this in DATA->max_loop field. If DEF itself is defined inside
465 this loop as well (i.e. we need to hoist it out of the loop if we want
466 to hoist the statement represented by DATA), record the statement in that
467 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
468 add the cost of the computation of DEF to the DATA->cost.
470 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
473 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
476 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
477 basic_block def_bb
= gimple_bb (def_stmt
);
478 struct loop
*max_loop
;
480 struct lim_aux_data
*def_data
;
485 max_loop
= outermost_invariant_loop (def
, loop
);
489 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
490 data
->max_loop
= max_loop
;
492 def_data
= get_lim_data (def_stmt
);
497 /* Only add the cost if the statement defining DEF is inside LOOP,
498 i.e. if it is likely that by moving the invariants dependent
499 on it, we will be able to avoid creating a new register for
500 it (since it will be only used in these dependent invariants). */
501 && def_bb
->loop_father
== loop
)
502 data
->cost
+= def_data
->cost
;
504 dep
= XNEW (struct depend
);
505 dep
->stmt
= def_stmt
;
506 dep
->next
= data
->depends
;
512 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
513 are just ad-hoc constants. The estimates should be based on target-specific
517 stmt_cost (gimple stmt
)
522 /* Always try to create possibilities for unswitching. */
523 if (gimple_code (stmt
) == GIMPLE_COND
524 || gimple_code (stmt
) == GIMPLE_PHI
)
525 return LIM_EXPENSIVE
;
527 /* Hoisting memory references out should almost surely be a win. */
528 if (gimple_references_memory_p (stmt
))
531 if (is_gimple_call (stmt
))
533 /* We should be hoisting calls if possible. */
535 /* Unless the call is a builtin_constant_p; this always folds to a
536 constant, so moving it is useless. */
537 fndecl
= gimple_call_fndecl (stmt
);
539 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
540 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
546 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
549 switch (gimple_assign_rhs_code (stmt
))
552 case WIDEN_MULT_EXPR
:
553 case WIDEN_MULT_PLUS_EXPR
:
554 case WIDEN_MULT_MINUS_EXPR
:
567 /* Division and multiplication are usually expensive. */
573 case WIDEN_LSHIFT_EXPR
:
586 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
587 REF is independent. If REF is not independent in LOOP, NULL is returned
591 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
595 if (bitmap_bit_p (ref
->stored
, loop
->num
))
600 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
601 if (!bitmap_bit_p (ref
->stored
, aloop
->num
)
602 && ref_indep_loop_p (aloop
, ref
))
605 if (ref_indep_loop_p (loop
, ref
))
611 /* If there is a simple load or store to a memory reference in STMT, returns
612 the location of the memory reference, and sets IS_STORE according to whether
613 it is a store or load. Otherwise, returns NULL. */
616 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
621 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
622 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
625 code
= gimple_assign_rhs_code (stmt
);
627 lhs
= gimple_assign_lhs_ptr (stmt
);
629 if (TREE_CODE (*lhs
) == SSA_NAME
)
631 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
632 || !is_gimple_addressable (gimple_assign_rhs1 (stmt
)))
636 return gimple_assign_rhs1_ptr (stmt
);
638 else if (code
== SSA_NAME
639 || (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
640 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
649 /* Returns the memory reference contained in STMT. */
652 mem_ref_in_stmt (gimple stmt
)
655 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
663 hash
= iterative_hash_expr (*mem
, 0);
664 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
666 gcc_assert (ref
!= NULL
);
670 /* From a controlling predicate in DOM determine the arguments from
671 the PHI node PHI that are chosen if the predicate evaluates to
672 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
673 they are non-NULL. Returns true if the arguments can be determined,
674 else return false. */
677 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
678 tree
*true_arg_p
, tree
*false_arg_p
)
680 basic_block bb
= gimple_bb (phi
);
681 edge true_edge
, false_edge
, tem
;
682 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
684 /* We have to verify that one edge into the PHI node is dominated
685 by the true edge of the predicate block and the other edge
686 dominated by the false edge. This ensures that the PHI argument
687 we are going to take is completely determined by the path we
688 take from the predicate block.
689 We can only use BB dominance checks below if the destination of
690 the true/false edges are dominated by their edge, thus only
691 have a single predecessor. */
692 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
693 tem
= EDGE_PRED (bb
, 0);
695 || (single_pred_p (true_edge
->dest
)
696 && (tem
->src
== true_edge
->dest
697 || dominated_by_p (CDI_DOMINATORS
,
698 tem
->src
, true_edge
->dest
))))
699 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
700 else if (tem
== false_edge
701 || (single_pred_p (false_edge
->dest
)
702 && (tem
->src
== false_edge
->dest
703 || dominated_by_p (CDI_DOMINATORS
,
704 tem
->src
, false_edge
->dest
))))
705 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
708 tem
= EDGE_PRED (bb
, 1);
710 || (single_pred_p (true_edge
->dest
)
711 && (tem
->src
== true_edge
->dest
712 || dominated_by_p (CDI_DOMINATORS
,
713 tem
->src
, true_edge
->dest
))))
714 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
715 else if (tem
== false_edge
716 || (single_pred_p (false_edge
->dest
)
717 && (tem
->src
== false_edge
->dest
718 || dominated_by_p (CDI_DOMINATORS
,
719 tem
->src
, false_edge
->dest
))))
720 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
734 /* Determine the outermost loop to that it is possible to hoist a statement
735 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
736 the outermost loop in that the value computed by STMT is invariant.
737 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
738 we preserve the fact whether STMT is executed. It also fills other related
739 information to LIM_DATA (STMT).
741 The function returns false if STMT cannot be hoisted outside of the loop it
742 is defined in, and true otherwise. */
745 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
747 basic_block bb
= gimple_bb (stmt
);
748 struct loop
*loop
= bb
->loop_father
;
750 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
754 if (must_preserve_exec
)
755 level
= ALWAYS_EXECUTED_IN (bb
);
757 level
= superloop_at_depth (loop
, 1);
758 lim_data
->max_loop
= level
;
760 if (gimple_code (stmt
) == GIMPLE_PHI
)
763 unsigned min_cost
= UINT_MAX
;
764 unsigned total_cost
= 0;
765 struct lim_aux_data
*def_data
;
767 /* We will end up promoting dependencies to be unconditionally
768 evaluated. For this reason the PHI cost (and thus the
769 cost we remove from the loop by doing the invariant motion)
770 is that of the cheapest PHI argument dependency chain. */
771 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
773 val
= USE_FROM_PTR (use_p
);
774 if (TREE_CODE (val
) != SSA_NAME
)
776 if (!add_dependency (val
, lim_data
, loop
, false))
778 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
781 min_cost
= MIN (min_cost
, def_data
->cost
);
782 total_cost
+= def_data
->cost
;
786 lim_data
->cost
+= min_cost
;
788 if (gimple_phi_num_args (stmt
) > 1)
790 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
792 if (gsi_end_p (gsi_last_bb (dom
)))
794 cond
= gsi_stmt (gsi_last_bb (dom
));
795 if (gimple_code (cond
) != GIMPLE_COND
)
797 /* Verify that this is an extended form of a diamond and
798 the PHI arguments are completely controlled by the
800 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
803 /* Fold in dependencies and cost of the condition. */
804 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
806 if (!add_dependency (val
, lim_data
, loop
, false))
808 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
810 total_cost
+= def_data
->cost
;
813 /* We want to avoid unconditionally executing very expensive
814 operations. As costs for our dependencies cannot be
815 negative just claim we are not invariand for this case.
816 We also are not sure whether the control-flow inside the
818 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
820 && total_cost
/ min_cost
<= 2))
823 /* Assume that the control-flow in the loop will vanish.
824 ??? We should verify this and not artificially increase
825 the cost if that is not the case. */
826 lim_data
->cost
+= stmt_cost (stmt
);
832 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
833 if (!add_dependency (val
, lim_data
, loop
, true))
836 if (gimple_vuse (stmt
))
838 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
843 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
844 if (!lim_data
->max_loop
)
849 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
851 if (!add_dependency (val
, lim_data
, loop
, false))
857 lim_data
->cost
+= stmt_cost (stmt
);
862 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
863 and that one of the operands of this statement is computed by STMT.
864 Ensure that STMT (together with all the statements that define its
865 operands) is hoisted at least out of the loop LEVEL. */
868 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
870 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
872 struct lim_aux_data
*lim_data
;
874 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
875 lim_data
= get_lim_data (stmt
);
876 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
877 stmt_loop
= find_common_loop (stmt_loop
,
878 loop_outer (lim_data
->tgt_loop
));
879 if (flow_loop_nested_p (stmt_loop
, level
))
882 gcc_assert (level
== lim_data
->max_loop
883 || flow_loop_nested_p (lim_data
->max_loop
, level
));
885 lim_data
->tgt_loop
= level
;
886 for (dep
= lim_data
->depends
; dep
; dep
= dep
->next
)
887 set_level (dep
->stmt
, orig_loop
, level
);
890 /* Determines an outermost loop from that we want to hoist the statement STMT.
891 For now we chose the outermost possible loop. TODO -- use profiling
892 information to set it more sanely. */
895 set_profitable_level (gimple stmt
)
897 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
900 /* Returns true if STMT is a call that has side effects. */
903 nonpure_call_p (gimple stmt
)
905 if (gimple_code (stmt
) != GIMPLE_CALL
)
908 return gimple_has_side_effects (stmt
);
911 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
914 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
916 gimple stmt
, stmt1
, stmt2
;
917 tree var
, name
, lhs
, type
;
919 gimple_stmt_iterator gsi
;
921 stmt
= gsi_stmt (*bsi
);
922 lhs
= gimple_assign_lhs (stmt
);
923 type
= TREE_TYPE (lhs
);
925 var
= create_tmp_var (type
, "reciptmp");
926 add_referenced_var (var
);
927 DECL_GIMPLE_REG_P (var
) = 1;
929 real_one
= build_one_cst (type
);
931 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
,
932 var
, real_one
, gimple_assign_rhs2 (stmt
));
933 name
= make_ssa_name (var
, stmt1
);
934 gimple_assign_set_lhs (stmt1
, name
);
936 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
937 gimple_assign_rhs1 (stmt
));
939 /* Replace division stmt with reciprocal and multiply stmts.
940 The multiply stmt is not invariant, so update iterator
941 and avoid rescanning. */
943 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
944 gsi_replace (&gsi
, stmt2
, true);
946 /* Continue processing with invariant reciprocal statement. */
950 /* Check if the pattern at *BSI is a bittest of the form
951 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
954 rewrite_bittest (gimple_stmt_iterator
*bsi
)
956 gimple stmt
, use_stmt
, stmt1
, stmt2
;
957 tree lhs
, var
, name
, t
, a
, b
;
960 stmt
= gsi_stmt (*bsi
);
961 lhs
= gimple_assign_lhs (stmt
);
963 /* Verify that the single use of lhs is a comparison against zero. */
964 if (TREE_CODE (lhs
) != SSA_NAME
965 || !single_imm_use (lhs
, &use
, &use_stmt
)
966 || gimple_code (use_stmt
) != GIMPLE_COND
)
968 if (gimple_cond_lhs (use_stmt
) != lhs
969 || (gimple_cond_code (use_stmt
) != NE_EXPR
970 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
971 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
974 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
975 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
976 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
979 /* There is a conversion in between possibly inserted by fold. */
980 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
982 t
= gimple_assign_rhs1 (stmt1
);
983 if (TREE_CODE (t
) != SSA_NAME
984 || !has_single_use (t
))
986 stmt1
= SSA_NAME_DEF_STMT (t
);
987 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
991 /* Verify that B is loop invariant but A is not. Verify that with
992 all the stmt walking we are still in the same loop. */
993 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
994 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
997 a
= gimple_assign_rhs1 (stmt1
);
998 b
= gimple_assign_rhs2 (stmt1
);
1000 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
1001 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
1003 gimple_stmt_iterator rsi
;
1006 var
= create_tmp_var (TREE_TYPE (a
), "shifttmp");
1007 add_referenced_var (var
);
1008 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
1009 build_int_cst (TREE_TYPE (a
), 1), b
);
1010 stmt1
= gimple_build_assign (var
, t
);
1011 name
= make_ssa_name (var
, stmt1
);
1012 gimple_assign_set_lhs (stmt1
, name
);
1015 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
1016 stmt2
= gimple_build_assign (var
, t
);
1017 name
= make_ssa_name (var
, stmt2
);
1018 gimple_assign_set_lhs (stmt2
, name
);
1020 /* Replace the SSA_NAME we compare against zero. Adjust
1021 the type of zero accordingly. */
1022 SET_USE (use
, name
);
1023 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
1025 /* Don't use gsi_replace here, none of the new assignments sets
1026 the variable originally set in stmt. Move bsi to stmt1, and
1027 then remove the original stmt, so that we get a chance to
1028 retain debug info for it. */
1030 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
1031 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
1032 gsi_remove (&rsi
, true);
1041 /* Determine the outermost loops in that statements in basic block BB are
1042 invariant, and record them to the LIM_DATA associated with the statements.
1043 Callback for walk_dominator_tree. */
1046 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1050 gimple_stmt_iterator bsi
;
1052 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1053 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1054 struct lim_aux_data
*lim_data
;
1056 if (!loop_outer (bb
->loop_father
))
1059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1060 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1061 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1063 /* Look at PHI nodes, but only if there is at most two.
1064 ??? We could relax this further by post-processing the inserted
1065 code and transforming adjacent cond-exprs with the same predicate
1066 to control flow again. */
1067 bsi
= gsi_start_phis (bb
);
1068 if (!gsi_end_p (bsi
)
1069 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1070 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1071 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1073 stmt
= gsi_stmt (bsi
);
1075 pos
= movement_possibility (stmt
);
1076 if (pos
== MOVE_IMPOSSIBLE
)
1079 lim_data
= init_lim_data (stmt
);
1080 lim_data
->always_executed_in
= outermost
;
1082 if (!determine_max_movement (stmt
, false))
1084 lim_data
->max_loop
= NULL
;
1088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1090 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1091 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1092 loop_depth (lim_data
->max_loop
),
1096 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1097 set_profitable_level (stmt
);
1100 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1102 stmt
= gsi_stmt (bsi
);
1104 pos
= movement_possibility (stmt
);
1105 if (pos
== MOVE_IMPOSSIBLE
)
1107 if (nonpure_call_p (stmt
))
1112 /* Make sure to note always_executed_in for stores to make
1113 store-motion work. */
1114 else if (stmt_makes_single_store (stmt
))
1116 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1117 lim_data
->always_executed_in
= outermost
;
1122 if (is_gimple_assign (stmt
)
1123 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1124 == GIMPLE_BINARY_RHS
))
1126 tree op0
= gimple_assign_rhs1 (stmt
);
1127 tree op1
= gimple_assign_rhs2 (stmt
);
1128 struct loop
*ol1
= outermost_invariant_loop (op1
,
1129 loop_containing_stmt (stmt
));
1131 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1132 to be hoisted out of loop, saving expensive divide. */
1133 if (pos
== MOVE_POSSIBLE
1134 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1135 && flag_unsafe_math_optimizations
1136 && !flag_trapping_math
1138 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1139 stmt
= rewrite_reciprocal (&bsi
);
1141 /* If the shift count is invariant, convert (A >> B) & 1 to
1142 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1143 saving an expensive shift. */
1144 if (pos
== MOVE_POSSIBLE
1145 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1146 && integer_onep (op1
)
1147 && TREE_CODE (op0
) == SSA_NAME
1148 && has_single_use (op0
))
1149 stmt
= rewrite_bittest (&bsi
);
1152 lim_data
= init_lim_data (stmt
);
1153 lim_data
->always_executed_in
= outermost
;
1155 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1158 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1160 lim_data
->max_loop
= NULL
;
1164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1166 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1167 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1168 loop_depth (lim_data
->max_loop
),
1172 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1173 set_profitable_level (stmt
);
1177 /* For each statement determines the outermost loop in that it is invariant,
1178 statements on whose motion it depends and the cost of the computation.
1179 This information is stored to the LIM_DATA structure associated with
1183 determine_invariantness (void)
1185 struct dom_walk_data walk_data
;
1187 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1188 walk_data
.dom_direction
= CDI_DOMINATORS
;
1189 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1191 init_walk_dominator_tree (&walk_data
);
1192 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1193 fini_walk_dominator_tree (&walk_data
);
1196 /* Hoist the statements in basic block BB out of the loops prescribed by
1197 data stored in LIM_DATA structures associated with each statement. Callback
1198 for walk_dominator_tree. */
1201 move_computations_stmt (struct dom_walk_data
*dw_data
,
1205 gimple_stmt_iterator bsi
;
1208 struct lim_aux_data
*lim_data
;
1210 if (!loop_outer (bb
->loop_father
))
1213 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1216 stmt
= gsi_stmt (bsi
);
1218 lim_data
= get_lim_data (stmt
);
1219 if (lim_data
== NULL
)
1225 cost
= lim_data
->cost
;
1226 level
= lim_data
->tgt_loop
;
1227 clear_lim_data (stmt
);
1235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1237 fprintf (dump_file
, "Moving PHI node\n");
1238 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1239 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1243 if (gimple_phi_num_args (stmt
) == 1)
1245 tree arg
= PHI_ARG_DEF (stmt
, 0);
1246 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1247 gimple_phi_result (stmt
),
1249 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1253 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1254 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1255 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1256 /* Get the PHI arguments corresponding to the true and false
1258 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1259 gcc_assert (arg0
&& arg1
);
1260 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1261 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1262 new_stmt
= gimple_build_assign_with_ops3 (COND_EXPR
,
1263 gimple_phi_result (stmt
),
1265 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1266 *((unsigned int *)(dw_data
->global_data
)) |= TODO_cleanup_cfg
;
1268 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1269 remove_phi_node (&bsi
, false);
1272 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1274 stmt
= gsi_stmt (bsi
);
1276 lim_data
= get_lim_data (stmt
);
1277 if (lim_data
== NULL
)
1283 cost
= lim_data
->cost
;
1284 level
= lim_data
->tgt_loop
;
1285 clear_lim_data (stmt
);
1293 /* We do not really want to move conditionals out of the loop; we just
1294 placed it here to force its operands to be moved if necessary. */
1295 if (gimple_code (stmt
) == GIMPLE_COND
)
1298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1300 fprintf (dump_file
, "Moving statement\n");
1301 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1302 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1306 mark_virtual_ops_for_renaming (stmt
);
1307 gsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
1308 gsi_remove (&bsi
, false);
1312 /* Hoist the statements out of the loops prescribed by data stored in
1313 LIM_DATA structures associated with each statement.*/
1316 move_computations (void)
1318 struct dom_walk_data walk_data
;
1319 unsigned int todo
= 0;
1321 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1322 walk_data
.global_data
= &todo
;
1323 walk_data
.dom_direction
= CDI_DOMINATORS
;
1324 walk_data
.before_dom_children
= move_computations_stmt
;
1326 init_walk_dominator_tree (&walk_data
);
1327 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1328 fini_walk_dominator_tree (&walk_data
);
1330 gsi_commit_edge_inserts ();
1331 if (need_ssa_update_p (cfun
))
1332 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1337 /* Checks whether the statement defining variable *INDEX can be hoisted
1338 out of the loop passed in DATA. Callback for for_each_index. */
1341 may_move_till (tree ref
, tree
*index
, void *data
)
1343 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1345 /* If REF is an array reference, check also that the step and the lower
1346 bound is invariant in LOOP. */
1347 if (TREE_CODE (ref
) == ARRAY_REF
)
1349 tree step
= TREE_OPERAND (ref
, 3);
1350 tree lbound
= TREE_OPERAND (ref
, 2);
1352 max_loop
= outermost_invariant_loop (step
, loop
);
1356 max_loop
= outermost_invariant_loop (lbound
, loop
);
1361 max_loop
= outermost_invariant_loop (*index
, loop
);
1368 /* If OP is SSA NAME, force the statement that defines it to be
1369 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1372 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1377 || is_gimple_min_invariant (op
))
1380 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1382 stmt
= SSA_NAME_DEF_STMT (op
);
1383 if (gimple_nop_p (stmt
))
1386 set_level (stmt
, orig_loop
, loop
);
1389 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1390 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1396 struct loop
*orig_loop
;
1400 force_move_till (tree ref
, tree
*index
, void *data
)
1402 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1404 if (TREE_CODE (ref
) == ARRAY_REF
)
1406 tree step
= TREE_OPERAND (ref
, 3);
1407 tree lbound
= TREE_OPERAND (ref
, 2);
1409 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1410 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1413 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1418 /* A hash function for struct mem_ref object OBJ. */
1421 memref_hash (const void *obj
)
1423 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1428 /* An equality function for struct mem_ref object OBJ1 with
1429 memory reference OBJ2. */
1432 memref_eq (const void *obj1
, const void *obj2
)
1434 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1436 return operand_equal_p (mem1
->mem
, (const_tree
) obj2
, 0);
1439 /* Releases list of memory reference locations ACCS. */
1442 free_mem_ref_locs (mem_ref_locs_p accs
)
1450 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1452 VEC_free (mem_ref_loc_p
, heap
, accs
->locs
);
1456 /* A function to free the mem_ref object OBJ. */
1459 memref_free (void *obj
)
1461 struct mem_ref
*const mem
= (struct mem_ref
*) obj
;
1463 mem_ref_locs_p accs
;
1465 BITMAP_FREE (mem
->stored
);
1466 BITMAP_FREE (mem
->indep_loop
);
1467 BITMAP_FREE (mem
->dep_loop
);
1468 BITMAP_FREE (mem
->indep_ref
);
1469 BITMAP_FREE (mem
->dep_ref
);
1471 FOR_EACH_VEC_ELT (mem_ref_locs_p
, mem
->accesses_in_loop
, i
, accs
)
1472 free_mem_ref_locs (accs
);
1473 VEC_free (mem_ref_locs_p
, heap
, mem
->accesses_in_loop
);
1475 BITMAP_FREE (mem
->vops
);
1479 /* Allocates and returns a memory reference description for MEM whose hash
1480 value is HASH and id is ID. */
1483 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1485 mem_ref_p ref
= XNEW (struct mem_ref
);
1489 ref
->stored
= BITMAP_ALLOC (NULL
);
1490 ref
->indep_loop
= BITMAP_ALLOC (NULL
);
1491 ref
->dep_loop
= BITMAP_ALLOC (NULL
);
1492 ref
->indep_ref
= BITMAP_ALLOC (NULL
);
1493 ref
->dep_ref
= BITMAP_ALLOC (NULL
);
1494 ref
->accesses_in_loop
= NULL
;
1495 ref
->vops
= BITMAP_ALLOC (NULL
);
1500 /* Allocates and returns the new list of locations. */
1502 static mem_ref_locs_p
1503 mem_ref_locs_alloc (void)
1505 mem_ref_locs_p accs
= XNEW (struct mem_ref_locs
);
1510 /* Records memory reference location *LOC in LOOP to the memory reference
1511 description REF. The reference occurs in statement STMT. */
1514 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1516 mem_ref_loc_p aref
= XNEW (struct mem_ref_loc
);
1517 mem_ref_locs_p accs
;
1518 bitmap ril
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1520 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1521 <= (unsigned) loop
->num
)
1522 VEC_safe_grow_cleared (mem_ref_locs_p
, heap
, ref
->accesses_in_loop
,
1524 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1527 accs
= mem_ref_locs_alloc ();
1528 VEC_replace (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
, accs
);
1534 VEC_safe_push (mem_ref_loc_p
, heap
, accs
->locs
, aref
);
1535 bitmap_set_bit (ril
, ref
->id
);
1538 /* Marks reference REF as stored in LOOP. */
1541 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1544 loop
!= current_loops
->tree_root
1545 && !bitmap_bit_p (ref
->stored
, loop
->num
);
1546 loop
= loop_outer (loop
))
1547 bitmap_set_bit (ref
->stored
, loop
->num
);
1550 /* Gathers memory references in statement STMT in LOOP, storing the
1551 information about them in the memory_accesses structure. Marks
1552 the vops accessed through unrecognized statements there as
1556 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1567 if (!gimple_vuse (stmt
))
1570 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1574 hash
= iterative_hash_expr (*mem
, 0);
1575 slot
= htab_find_slot_with_hash (memory_accesses
.refs
, *mem
, hash
, INSERT
);
1579 ref
= (mem_ref_p
) *slot
;
1584 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1585 ref
= mem_ref_alloc (*mem
, hash
, id
);
1586 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1589 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1591 fprintf (dump_file
, "Memory reference %u: ", id
);
1592 print_generic_expr (dump_file
, ref
->mem
, TDF_SLIM
);
1593 fprintf (dump_file
, "\n");
1597 mark_ref_stored (ref
, loop
);
1599 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1600 bitmap_set_bit (ref
->vops
, DECL_UID (SSA_NAME_VAR (vname
)));
1601 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1605 clvops
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1606 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1607 bitmap_set_bit (clvops
, DECL_UID (SSA_NAME_VAR (vname
)));
1610 /* Gathers memory references in loops. */
1613 gather_mem_refs_in_loops (void)
1615 gimple_stmt_iterator bsi
;
1620 bitmap lrefs
, alrefs
, alrefso
;
1624 loop
= bb
->loop_father
;
1625 if (loop
== current_loops
->tree_root
)
1628 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1629 gather_mem_refs_stmt (loop
, gsi_stmt (bsi
));
1632 /* Propagate the information about clobbered vops and accessed memory
1633 references up the loop hierarchy. */
1634 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1636 lrefs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1637 alrefs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
, loop
->num
);
1638 bitmap_ior_into (alrefs
, lrefs
);
1640 if (loop_outer (loop
) == current_loops
->tree_root
)
1643 clvi
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1644 clvo
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1645 loop_outer (loop
)->num
);
1646 bitmap_ior_into (clvo
, clvi
);
1648 alrefso
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1649 loop_outer (loop
)->num
);
1650 bitmap_ior_into (alrefso
, alrefs
);
1654 /* Element of the hash table that maps vops to memory references. */
1656 struct vop_to_refs_elt
1658 /* DECL_UID of the vop. */
1661 /* List of the all references. */
1664 /* List of stored references. */
1668 /* A hash function for struct vop_to_refs_elt object OBJ. */
1671 vtoe_hash (const void *obj
)
1673 const struct vop_to_refs_elt
*const vtoe
=
1674 (const struct vop_to_refs_elt
*) obj
;
1679 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1680 uid of a vop OBJ2. */
1683 vtoe_eq (const void *obj1
, const void *obj2
)
1685 const struct vop_to_refs_elt
*const vtoe
=
1686 (const struct vop_to_refs_elt
*) obj1
;
1687 const unsigned *const uid
= (const unsigned *) obj2
;
1689 return vtoe
->uid
== *uid
;
1692 /* A function to free the struct vop_to_refs_elt object. */
1695 vtoe_free (void *obj
)
1697 struct vop_to_refs_elt
*const vtoe
=
1698 (struct vop_to_refs_elt
*) obj
;
1700 BITMAP_FREE (vtoe
->refs_all
);
1701 BITMAP_FREE (vtoe
->refs_stored
);
1705 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1706 if the reference REF is stored. */
1709 record_vop_access (htab_t vop_to_refs
, unsigned vop
, unsigned ref
, bool stored
)
1711 void **slot
= htab_find_slot_with_hash (vop_to_refs
, &vop
, vop
, INSERT
);
1712 struct vop_to_refs_elt
*vtoe
;
1716 vtoe
= XNEW (struct vop_to_refs_elt
);
1718 vtoe
->refs_all
= BITMAP_ALLOC (NULL
);
1719 vtoe
->refs_stored
= BITMAP_ALLOC (NULL
);
1723 vtoe
= (struct vop_to_refs_elt
*) *slot
;
1725 bitmap_set_bit (vtoe
->refs_all
, ref
);
1727 bitmap_set_bit (vtoe
->refs_stored
, ref
);
1730 /* Returns the set of references that access VOP according to the table
1734 get_vop_accesses (htab_t vop_to_refs
, unsigned vop
)
1736 struct vop_to_refs_elt
*const vtoe
=
1737 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1738 return vtoe
->refs_all
;
1741 /* Returns the set of stores that access VOP according to the table
1745 get_vop_stores (htab_t vop_to_refs
, unsigned vop
)
1747 struct vop_to_refs_elt
*const vtoe
=
1748 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1749 return vtoe
->refs_stored
;
1752 /* Adds REF to mapping from virtual operands to references in LOOP. */
1755 add_vop_ref_mapping (struct loop
*loop
, mem_ref_p ref
)
1757 htab_t map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
1758 bool stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
1759 bitmap clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1764 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, vop
, bi
)
1766 record_vop_access (map
, vop
, ref
->id
, stored
);
1770 /* Create a mapping from virtual operands to references that touch them
1774 create_vop_ref_mapping_loop (struct loop
*loop
)
1776 bitmap refs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1782 EXECUTE_IF_SET_IN_BITMAP (refs
, 0, i
, bi
)
1784 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1785 for (sloop
= loop
; sloop
!= current_loops
->tree_root
; sloop
= loop_outer (sloop
))
1786 add_vop_ref_mapping (sloop
, ref
);
1790 /* For each non-clobbered virtual operand and each loop, record the memory
1791 references in this loop that touch the operand. */
1794 create_vop_ref_mapping (void)
1799 FOR_EACH_LOOP (li
, loop
, 0)
1801 create_vop_ref_mapping_loop (loop
);
1805 /* Gathers information about memory accesses in the loops. */
1808 analyze_memory_references (void)
1814 memory_accesses
.refs
1815 = htab_create (100, memref_hash
, memref_eq
, memref_free
);
1816 memory_accesses
.refs_list
= NULL
;
1817 memory_accesses
.refs_in_loop
= VEC_alloc (bitmap
, heap
,
1818 number_of_loops ());
1819 memory_accesses
.all_refs_in_loop
= VEC_alloc (bitmap
, heap
,
1820 number_of_loops ());
1821 memory_accesses
.clobbered_vops
= VEC_alloc (bitmap
, heap
,
1822 number_of_loops ());
1823 memory_accesses
.vop_ref_map
= VEC_alloc (htab_t
, heap
,
1824 number_of_loops ());
1826 for (i
= 0; i
< number_of_loops (); i
++)
1828 empty
= BITMAP_ALLOC (NULL
);
1829 VEC_quick_push (bitmap
, memory_accesses
.refs_in_loop
, empty
);
1830 empty
= BITMAP_ALLOC (NULL
);
1831 VEC_quick_push (bitmap
, memory_accesses
.all_refs_in_loop
, empty
);
1832 empty
= BITMAP_ALLOC (NULL
);
1833 VEC_quick_push (bitmap
, memory_accesses
.clobbered_vops
, empty
);
1834 hempty
= htab_create (10, vtoe_hash
, vtoe_eq
, vtoe_free
);
1835 VEC_quick_push (htab_t
, memory_accesses
.vop_ref_map
, hempty
);
1838 memory_accesses
.ttae_cache
= NULL
;
1840 gather_mem_refs_in_loops ();
1841 create_vop_ref_mapping ();
1844 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1845 tree_to_aff_combination_expand. */
1848 mem_refs_may_alias_p (tree mem1
, tree mem2
, struct pointer_map_t
**ttae_cache
)
1850 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1851 object and their offset differ in such a way that the locations cannot
1852 overlap, then they cannot alias. */
1853 double_int size1
, size2
;
1854 aff_tree off1
, off2
;
1856 /* Perform basic offset and type-based disambiguation. */
1857 if (!refs_may_alias_p (mem1
, mem2
))
1860 /* The expansion of addresses may be a bit expensive, thus we only do
1861 the check at -O2 and higher optimization levels. */
1865 get_inner_reference_aff (mem1
, &off1
, &size1
);
1866 get_inner_reference_aff (mem2
, &off2
, &size2
);
1867 aff_combination_expand (&off1
, ttae_cache
);
1868 aff_combination_expand (&off2
, ttae_cache
);
1869 aff_combination_scale (&off1
, double_int_minus_one
);
1870 aff_combination_add (&off2
, &off1
);
1872 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1878 /* Rewrites location LOC by TMP_VAR. */
1881 rewrite_mem_ref_loc (mem_ref_loc_p loc
, tree tmp_var
)
1883 mark_virtual_ops_for_renaming (loc
->stmt
);
1884 *loc
->ref
= tmp_var
;
1885 update_stmt (loc
->stmt
);
1888 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1891 get_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
,
1892 VEC (mem_ref_loc_p
, heap
) **locs
)
1894 mem_ref_locs_p accs
;
1897 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1899 struct loop
*subloop
;
1901 if (!bitmap_bit_p (refs
, ref
->id
))
1904 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1905 > (unsigned) loop
->num
)
1907 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1910 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1911 VEC_safe_push (mem_ref_loc_p
, heap
, *locs
, loc
);
1915 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1916 get_all_locs_in_loop (subloop
, ref
, locs
);
1919 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1922 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1926 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1928 get_all_locs_in_loop (loop
, ref
, &locs
);
1929 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
1930 rewrite_mem_ref_loc (loc
, tmp_var
);
1931 VEC_free (mem_ref_loc_p
, heap
, locs
);
1934 /* The name and the length of the currently generated variable
1936 #define MAX_LSM_NAME_LENGTH 40
1937 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1938 static int lsm_tmp_name_length
;
1940 /* Adds S to lsm_tmp_name. */
1943 lsm_tmp_name_add (const char *s
)
1945 int l
= strlen (s
) + lsm_tmp_name_length
;
1946 if (l
> MAX_LSM_NAME_LENGTH
)
1949 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1950 lsm_tmp_name_length
= l
;
1953 /* Stores the name for temporary variable that replaces REF to
1957 gen_lsm_tmp_name (tree ref
)
1961 switch (TREE_CODE (ref
))
1964 case TARGET_MEM_REF
:
1965 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1966 lsm_tmp_name_add ("_");
1970 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1974 case VIEW_CONVERT_EXPR
:
1975 case ARRAY_RANGE_REF
:
1976 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1980 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1981 lsm_tmp_name_add ("_RE");
1985 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1986 lsm_tmp_name_add ("_IM");
1990 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1991 lsm_tmp_name_add ("_");
1992 name
= get_name (TREE_OPERAND (ref
, 1));
1995 lsm_tmp_name_add (name
);
1999 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2000 lsm_tmp_name_add ("_I");
2004 ref
= SSA_NAME_VAR (ref
);
2009 name
= get_name (ref
);
2012 lsm_tmp_name_add (name
);
2016 lsm_tmp_name_add ("S");
2020 lsm_tmp_name_add ("R");
2032 /* Determines name for temporary variable that replaces REF.
2033 The name is accumulated into the lsm_tmp_name variable.
2034 N is added to the name of the temporary. */
2037 get_lsm_tmp_name (tree ref
, unsigned n
)
2041 lsm_tmp_name_length
= 0;
2042 gen_lsm_tmp_name (ref
);
2043 lsm_tmp_name_add ("_lsm");
2048 lsm_tmp_name_add (ns
);
2050 return lsm_tmp_name
;
2053 /* Executes store motion of memory reference REF from LOOP.
2054 Exits from the LOOP are stored in EXITS. The initialization of the
2055 temporary variable is put to the preheader of the loop, and assignments
2056 to the reference from the temporary variable are emitted to exits. */
2059 execute_sm (struct loop
*loop
, VEC (edge
, heap
) *exits
, mem_ref_p ref
)
2064 struct fmt_data fmt_data
;
2066 struct lim_aux_data
*lim_data
;
2068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2070 fprintf (dump_file
, "Executing store motion of ");
2071 print_generic_expr (dump_file
, ref
->mem
, 0);
2072 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2075 tmp_var
= make_rename_temp (TREE_TYPE (ref
->mem
),
2076 get_lsm_tmp_name (ref
->mem
, ~0));
2078 fmt_data
.loop
= loop
;
2079 fmt_data
.orig_loop
= loop
;
2080 for_each_index (&ref
->mem
, force_move_till
, &fmt_data
);
2082 rewrite_mem_refs (loop
, ref
, tmp_var
);
2084 /* Emit the load & stores. */
2085 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
));
2086 lim_data
= init_lim_data (load
);
2087 lim_data
->max_loop
= loop
;
2088 lim_data
->tgt_loop
= loop
;
2090 /* Put this into the latch, so that we are sure it will be processed after
2091 all dependencies. */
2092 gsi_insert_on_edge (loop_latch_edge (loop
), load
);
2094 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2096 store
= gimple_build_assign (unshare_expr (ref
->mem
), tmp_var
);
2097 gsi_insert_on_edge (ex
, store
);
2101 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2102 edges of the LOOP. */
2105 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2106 VEC (edge
, heap
) *exits
)
2112 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2114 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2115 execute_sm (loop
, exits
, ref
);
2119 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2120 make sure REF is always stored to in LOOP. */
2123 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2125 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
2129 struct loop
*must_exec
;
2132 base
= get_base_address (ref
->mem
);
2133 if (INDIRECT_REF_P (base
)
2134 || TREE_CODE (base
) == MEM_REF
)
2135 base
= TREE_OPERAND (base
, 0);
2137 get_all_locs_in_loop (loop
, ref
, &locs
);
2138 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
2140 if (!get_lim_data (loc
->stmt
))
2143 /* If we require an always executed store make sure the statement
2144 stores to the reference. */
2148 if (!gimple_get_lhs (loc
->stmt
))
2150 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2153 if (INDIRECT_REF_P (lhs
)
2154 || TREE_CODE (lhs
) == MEM_REF
)
2155 lhs
= TREE_OPERAND (lhs
, 0);
2160 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2164 if (must_exec
== loop
2165 || flow_loop_nested_p (must_exec
, loop
))
2171 VEC_free (mem_ref_loc_p
, heap
, locs
);
2176 /* Returns true if REF1 and REF2 are independent. */
2179 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2182 || bitmap_bit_p (ref1
->indep_ref
, ref2
->id
))
2184 if (bitmap_bit_p (ref1
->dep_ref
, ref2
->id
))
2187 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2188 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2189 ref1
->id
, ref2
->id
);
2191 if (mem_refs_may_alias_p (ref1
->mem
, ref2
->mem
,
2192 &memory_accesses
.ttae_cache
))
2194 bitmap_set_bit (ref1
->dep_ref
, ref2
->id
);
2195 bitmap_set_bit (ref2
->dep_ref
, ref1
->id
);
2196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2197 fprintf (dump_file
, "dependent.\n");
2202 bitmap_set_bit (ref1
->indep_ref
, ref2
->id
);
2203 bitmap_set_bit (ref2
->indep_ref
, ref1
->id
);
2204 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2205 fprintf (dump_file
, "independent.\n");
2210 /* Records the information whether REF is independent in LOOP (according
2214 record_indep_loop (struct loop
*loop
, mem_ref_p ref
, bool indep
)
2217 bitmap_set_bit (ref
->indep_loop
, loop
->num
);
2219 bitmap_set_bit (ref
->dep_loop
, loop
->num
);
2222 /* Returns true if REF is independent on all other memory references in
2226 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
)
2228 bitmap clobbers
, refs_to_check
, refs
;
2231 bool ret
= true, stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
2235 /* If the reference is clobbered, it is not independent. */
2236 clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
2237 if (bitmap_intersect_p (ref
->vops
, clobbers
))
2240 refs_to_check
= BITMAP_ALLOC (NULL
);
2242 map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
2243 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, i
, bi
)
2246 refs
= get_vop_accesses (map
, i
);
2248 refs
= get_vop_stores (map
, i
);
2250 bitmap_ior_into (refs_to_check
, refs
);
2253 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2255 aref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2256 if (!refs_independent_p (ref
, aref
))
2259 record_indep_loop (loop
, aref
, false);
2264 BITMAP_FREE (refs_to_check
);
2268 /* Returns true if REF is independent on all other memory references in
2269 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2272 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2276 if (bitmap_bit_p (ref
->indep_loop
, loop
->num
))
2278 if (bitmap_bit_p (ref
->dep_loop
, loop
->num
))
2281 ret
= ref_indep_loop_p_1 (loop
, ref
);
2283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2284 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2285 ref
->id
, loop
->num
, ret
? "independent" : "dependent");
2287 record_indep_loop (loop
, ref
, ret
);
2292 /* Returns true if we can perform store motion of REF from LOOP. */
2295 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2299 /* Unless the reference is stored in the loop, there is nothing to do. */
2300 if (!bitmap_bit_p (ref
->stored
, loop
->num
))
2303 /* It should be movable. */
2304 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
))
2305 || TREE_THIS_VOLATILE (ref
->mem
)
2306 || !for_each_index (&ref
->mem
, may_move_till
, loop
))
2309 /* If it can throw fail, we do not properly update EH info. */
2310 if (tree_could_throw_p (ref
->mem
))
2313 /* If it can trap, it must be always executed in LOOP.
2314 Readonly memory locations may trap when storing to them, but
2315 tree_could_trap_p is a predicate for rvalues, so check that
2317 base
= get_base_address (ref
->mem
);
2318 if ((tree_could_trap_p (ref
->mem
)
2319 || (DECL_P (base
) && TREE_READONLY (base
)))
2320 && !ref_always_accessed_p (loop
, ref
, true))
2323 /* And it must be independent on all other memory references
2325 if (!ref_indep_loop_p (loop
, ref
))
2331 /* Marks the references in LOOP for that store motion should be performed
2332 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2333 motion was performed in one of the outer loops. */
2336 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2338 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
2344 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2346 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2347 if (can_sm_ref_p (loop
, ref
))
2348 bitmap_set_bit (refs_to_sm
, i
);
2352 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2353 for a store motion optimization (i.e. whether we can insert statement
2357 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2358 VEC (edge
, heap
) *exits
)
2363 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2364 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2370 /* Try to perform store motion for all memory references modified inside
2371 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2372 store motion was executed in one of the outer loops. */
2375 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2377 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2378 struct loop
*subloop
;
2379 bitmap sm_in_loop
= BITMAP_ALLOC (NULL
);
2381 if (loop_suitable_for_sm (loop
, exits
))
2383 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2384 hoist_memory_references (loop
, sm_in_loop
, exits
);
2386 VEC_free (edge
, heap
, exits
);
2388 bitmap_ior_into (sm_executed
, sm_in_loop
);
2389 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2390 store_motion_loop (subloop
, sm_executed
);
2391 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2392 BITMAP_FREE (sm_in_loop
);
2395 /* Try to perform store motion for all memory references modified inside
2402 bitmap sm_executed
= BITMAP_ALLOC (NULL
);
2404 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2405 store_motion_loop (loop
, sm_executed
);
2407 BITMAP_FREE (sm_executed
);
2408 gsi_commit_edge_inserts ();
2411 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2412 for each such basic block bb records the outermost loop for that execution
2413 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2414 blocks that contain a nonpure call. */
2417 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
2419 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2422 struct loop
*inn_loop
= loop
;
2424 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2426 bbs
= get_loop_body_in_dom_order (loop
);
2428 for (i
= 0; i
< loop
->num_nodes
; i
++)
2433 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2436 if (TEST_BIT (contains_call
, bb
->index
))
2439 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2440 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2445 /* A loop might be infinite (TODO use simple loop analysis
2446 to disprove this if possible). */
2447 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2450 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2453 if (bb
->loop_father
->header
== bb
)
2455 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2458 /* In a loop that is always entered we may proceed anyway.
2459 But record that we entered it and stop once we leave it. */
2460 inn_loop
= bb
->loop_father
;
2466 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2467 if (last
== loop
->header
)
2469 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2475 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2476 fill_always_executed_in (loop
, contains_call
);
2479 /* Compute the global information needed by the loop invariant motion pass. */
2482 tree_ssa_lim_initialize (void)
2484 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2485 gimple_stmt_iterator bsi
;
2489 sbitmap_zero (contains_call
);
2492 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2494 if (nonpure_call_p (gsi_stmt (bsi
)))
2498 if (!gsi_end_p (bsi
))
2499 SET_BIT (contains_call
, bb
->index
);
2502 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2503 fill_always_executed_in (loop
, contains_call
);
2505 sbitmap_free (contains_call
);
2507 lim_aux_data_map
= pointer_map_create ();
2510 /* Cleans up after the invariant motion pass. */
2513 tree_ssa_lim_finalize (void)
2521 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2523 pointer_map_destroy (lim_aux_data_map
);
2525 VEC_free (mem_ref_p
, heap
, memory_accesses
.refs_list
);
2526 htab_delete (memory_accesses
.refs
);
2528 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.refs_in_loop
, i
, b
)
2530 VEC_free (bitmap
, heap
, memory_accesses
.refs_in_loop
);
2532 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.all_refs_in_loop
, i
, b
)
2534 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_in_loop
);
2536 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.clobbered_vops
, i
, b
)
2538 VEC_free (bitmap
, heap
, memory_accesses
.clobbered_vops
);
2540 FOR_EACH_VEC_ELT (htab_t
, memory_accesses
.vop_ref_map
, i
, h
)
2542 VEC_free (htab_t
, heap
, memory_accesses
.vop_ref_map
);
2544 if (memory_accesses
.ttae_cache
)
2545 pointer_map_destroy (memory_accesses
.ttae_cache
);
2548 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2549 i.e. those that are likely to be win regardless of the register pressure. */
2556 tree_ssa_lim_initialize ();
2558 /* Gathers information about memory accesses in the loops. */
2559 analyze_memory_references ();
2561 /* For each statement determine the outermost loop in that it is
2562 invariant and cost for computing the invariant. */
2563 determine_invariantness ();
2565 /* Execute store motion. Force the necessary invariants to be moved
2566 out of the loops as well. */
2569 /* Move the expressions that are expensive enough. */
2570 todo
= move_computations ();
2572 tree_ssa_lim_finalize ();