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 that execution of the header guarantees that the
201 block will be executed. */
202 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
204 static struct lim_aux_data
*
205 init_lim_data (gimple stmt
)
207 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
209 *p
= XCNEW (struct lim_aux_data
);
210 return (struct lim_aux_data
*) *p
;
213 static struct lim_aux_data
*
214 get_lim_data (gimple stmt
)
216 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
220 return (struct lim_aux_data
*) *p
;
223 /* Releases the memory occupied by DATA. */
226 free_lim_aux_data (struct lim_aux_data
*data
)
228 struct depend
*dep
, *next
;
230 for (dep
= data
->depends
; dep
; dep
= next
)
239 clear_lim_data (gimple stmt
)
241 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
245 free_lim_aux_data ((struct lim_aux_data
*) *p
);
249 /* Calls CBCK for each index in memory reference ADDR_P. There are two
250 kinds situations handled; in each of these cases, the memory reference
251 and DATA are passed to the callback:
253 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
254 pass the pointer to the index to the callback.
256 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
257 pointer to addr to the callback.
259 If the callback returns false, the whole search stops and false is returned.
260 Otherwise the function returns true after traversing through the whole
261 reference *ADDR_P. */
264 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
268 for (; ; addr_p
= nxt
)
270 switch (TREE_CODE (*addr_p
))
273 return cbck (*addr_p
, addr_p
, data
);
276 nxt
= &TREE_OPERAND (*addr_p
, 0);
277 return cbck (*addr_p
, nxt
, data
);
280 case VIEW_CONVERT_EXPR
:
283 nxt
= &TREE_OPERAND (*addr_p
, 0);
287 /* If the component has varying offset, it behaves like index
289 idx
= &TREE_OPERAND (*addr_p
, 2);
291 && !cbck (*addr_p
, idx
, data
))
294 nxt
= &TREE_OPERAND (*addr_p
, 0);
298 case ARRAY_RANGE_REF
:
299 nxt
= &TREE_OPERAND (*addr_p
, 0);
300 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
317 gcc_assert (is_gimple_min_invariant (*addr_p
));
321 idx
= &TMR_BASE (*addr_p
);
323 && !cbck (*addr_p
, idx
, data
))
325 idx
= &TMR_INDEX (*addr_p
);
327 && !cbck (*addr_p
, idx
, data
))
329 idx
= &TMR_INDEX2 (*addr_p
);
331 && !cbck (*addr_p
, idx
, data
))
341 /* If it is possible to hoist the statement STMT unconditionally,
342 returns MOVE_POSSIBLE.
343 If it is possible to hoist the statement STMT, but we must avoid making
344 it executed if it would not be executed in the original program (e.g.
345 because it may trap), return MOVE_PRESERVE_EXECUTION.
346 Otherwise return MOVE_IMPOSSIBLE. */
349 movement_possibility (gimple stmt
)
352 enum move_pos ret
= MOVE_POSSIBLE
;
354 if (flag_unswitch_loops
355 && gimple_code (stmt
) == GIMPLE_COND
)
357 /* If we perform unswitching, force the operands of the invariant
358 condition to be moved out of the loop. */
359 return MOVE_POSSIBLE
;
362 if (gimple_code (stmt
) == GIMPLE_PHI
363 && gimple_phi_num_args (stmt
) <= 2
364 && is_gimple_reg (gimple_phi_result (stmt
))
365 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
366 return MOVE_POSSIBLE
;
368 if (gimple_get_lhs (stmt
) == NULL_TREE
)
369 return MOVE_IMPOSSIBLE
;
371 if (gimple_vdef (stmt
))
372 return MOVE_IMPOSSIBLE
;
374 if (stmt_ends_bb_p (stmt
)
375 || gimple_has_volatile_ops (stmt
)
376 || gimple_has_side_effects (stmt
)
377 || stmt_could_throw_p (stmt
))
378 return MOVE_IMPOSSIBLE
;
380 if (is_gimple_call (stmt
))
382 /* While pure or const call is guaranteed to have no side effects, we
383 cannot move it arbitrarily. Consider code like
385 char *s = something ();
395 Here the strlen call cannot be moved out of the loop, even though
396 s is invariant. In addition to possibly creating a call with
397 invalid arguments, moving out a function call that is not executed
398 may cause performance regressions in case the call is costly and
399 not executed at all. */
400 ret
= MOVE_PRESERVE_EXECUTION
;
401 lhs
= gimple_call_lhs (stmt
);
403 else if (is_gimple_assign (stmt
))
404 lhs
= gimple_assign_lhs (stmt
);
406 return MOVE_IMPOSSIBLE
;
408 if (TREE_CODE (lhs
) == SSA_NAME
409 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
410 return MOVE_IMPOSSIBLE
;
412 if (TREE_CODE (lhs
) != SSA_NAME
413 || gimple_could_trap_p (stmt
))
414 return MOVE_PRESERVE_EXECUTION
;
419 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
420 loop to that we could move the expression using DEF if it did not have
421 other operands, i.e. the outermost loop enclosing LOOP in that the value
422 of DEF is invariant. */
425 outermost_invariant_loop (tree def
, struct loop
*loop
)
429 struct loop
*max_loop
;
430 struct lim_aux_data
*lim_data
;
433 return superloop_at_depth (loop
, 1);
435 if (TREE_CODE (def
) != SSA_NAME
)
437 gcc_assert (is_gimple_min_invariant (def
));
438 return superloop_at_depth (loop
, 1);
441 def_stmt
= SSA_NAME_DEF_STMT (def
);
442 def_bb
= gimple_bb (def_stmt
);
444 return superloop_at_depth (loop
, 1);
446 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
448 lim_data
= get_lim_data (def_stmt
);
449 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
450 max_loop
= find_common_loop (max_loop
,
451 loop_outer (lim_data
->max_loop
));
452 if (max_loop
== loop
)
454 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
459 /* DATA is a structure containing information associated with a statement
460 inside LOOP. DEF is one of the operands of this statement.
462 Find the outermost loop enclosing LOOP in that value of DEF is invariant
463 and record this in DATA->max_loop field. If DEF itself is defined inside
464 this loop as well (i.e. we need to hoist it out of the loop if we want
465 to hoist the statement represented by DATA), record the statement in that
466 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
467 add the cost of the computation of DEF to the DATA->cost.
469 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
472 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
475 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
476 basic_block def_bb
= gimple_bb (def_stmt
);
477 struct loop
*max_loop
;
479 struct lim_aux_data
*def_data
;
484 max_loop
= outermost_invariant_loop (def
, loop
);
488 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
489 data
->max_loop
= max_loop
;
491 def_data
= get_lim_data (def_stmt
);
496 /* Only add the cost if the statement defining DEF is inside LOOP,
497 i.e. if it is likely that by moving the invariants dependent
498 on it, we will be able to avoid creating a new register for
499 it (since it will be only used in these dependent invariants). */
500 && def_bb
->loop_father
== loop
)
501 data
->cost
+= def_data
->cost
;
503 dep
= XNEW (struct depend
);
504 dep
->stmt
= def_stmt
;
505 dep
->next
= data
->depends
;
511 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
512 are just ad-hoc constants. The estimates should be based on target-specific
516 stmt_cost (gimple stmt
)
521 /* Always try to create possibilities for unswitching. */
522 if (gimple_code (stmt
) == GIMPLE_COND
523 || gimple_code (stmt
) == GIMPLE_PHI
)
524 return LIM_EXPENSIVE
;
526 /* Hoisting memory references out should almost surely be a win. */
527 if (gimple_references_memory_p (stmt
))
530 if (is_gimple_call (stmt
))
532 /* We should be hoisting calls if possible. */
534 /* Unless the call is a builtin_constant_p; this always folds to a
535 constant, so moving it is useless. */
536 fndecl
= gimple_call_fndecl (stmt
);
538 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
539 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
545 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
548 switch (gimple_assign_rhs_code (stmt
))
561 /* Division and multiplication are usually expensive. */
577 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
578 REF is independent. If REF is not independent in LOOP, NULL is returned
582 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
586 if (bitmap_bit_p (ref
->stored
, loop
->num
))
591 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
592 if (!bitmap_bit_p (ref
->stored
, aloop
->num
)
593 && ref_indep_loop_p (aloop
, ref
))
596 if (ref_indep_loop_p (loop
, ref
))
602 /* If there is a simple load or store to a memory reference in STMT, returns
603 the location of the memory reference, and sets IS_STORE according to whether
604 it is a store or load. Otherwise, returns NULL. */
607 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
612 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
613 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
616 code
= gimple_assign_rhs_code (stmt
);
618 lhs
= gimple_assign_lhs_ptr (stmt
);
620 if (TREE_CODE (*lhs
) == SSA_NAME
)
622 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
623 || !is_gimple_addressable (gimple_assign_rhs1 (stmt
)))
627 return gimple_assign_rhs1_ptr (stmt
);
629 else if (code
== SSA_NAME
630 || (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
631 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
640 /* Returns the memory reference contained in STMT. */
643 mem_ref_in_stmt (gimple stmt
)
646 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
654 hash
= iterative_hash_expr (*mem
, 0);
655 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
657 gcc_assert (ref
!= NULL
);
661 /* From a controlling predicate in DOM determine the arguments from
662 the PHI node PHI that are chosen if the predicate evaluates to
663 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
664 they are non-NULL. Returns true if the arguments can be determined,
665 else return false. */
668 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
669 tree
*true_arg_p
, tree
*false_arg_p
)
671 basic_block bb
= gimple_bb (phi
);
672 edge true_edge
, false_edge
, tem
;
673 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
675 /* We have to verify that one edge into the PHI node is dominated
676 by the true edge of the predicate block and the other edge
677 dominated by the false edge. This ensures that the PHI argument
678 we are going to take is completely determined by the path we
679 take from the predicate block. */
680 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
681 tem
= EDGE_PRED (bb
, 0);
683 || tem
->src
== true_edge
->dest
684 || dominated_by_p (CDI_DOMINATORS
,
685 tem
->src
, true_edge
->dest
))
686 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
687 else if (tem
== false_edge
688 || tem
->src
== false_edge
->dest
689 || dominated_by_p (CDI_DOMINATORS
,
690 tem
->src
, false_edge
->dest
))
691 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
694 tem
= EDGE_PRED (bb
, 1);
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 || tem
->src
== false_edge
->dest
702 || dominated_by_p (CDI_DOMINATORS
,
703 tem
->src
, false_edge
->dest
))
704 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
718 /* Determine the outermost loop to that it is possible to hoist a statement
719 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
720 the outermost loop in that the value computed by STMT is invariant.
721 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
722 we preserve the fact whether STMT is executed. It also fills other related
723 information to LIM_DATA (STMT).
725 The function returns false if STMT cannot be hoisted outside of the loop it
726 is defined in, and true otherwise. */
729 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
731 basic_block bb
= gimple_bb (stmt
);
732 struct loop
*loop
= bb
->loop_father
;
734 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
738 if (must_preserve_exec
)
739 level
= ALWAYS_EXECUTED_IN (bb
);
741 level
= superloop_at_depth (loop
, 1);
742 lim_data
->max_loop
= level
;
744 if (gimple_code (stmt
) == GIMPLE_PHI
)
747 unsigned min_cost
= UINT_MAX
;
748 unsigned total_cost
= 0;
749 struct lim_aux_data
*def_data
;
751 /* We will end up promoting dependencies to be unconditionally
752 evaluated. For this reason the PHI cost (and thus the
753 cost we remove from the loop by doing the invariant motion)
754 is that of the cheapest PHI argument dependency chain. */
755 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
757 val
= USE_FROM_PTR (use_p
);
758 if (TREE_CODE (val
) != SSA_NAME
)
760 if (!add_dependency (val
, lim_data
, loop
, false))
762 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
765 min_cost
= MIN (min_cost
, def_data
->cost
);
766 total_cost
+= def_data
->cost
;
770 lim_data
->cost
+= min_cost
;
772 if (gimple_phi_num_args (stmt
) > 1)
774 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
776 if (gsi_end_p (gsi_last_bb (dom
)))
778 cond
= gsi_stmt (gsi_last_bb (dom
));
779 if (gimple_code (cond
) != GIMPLE_COND
)
781 /* Verify that this is an extended form of a diamond and
782 the PHI arguments are completely controlled by the
784 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
787 /* Fold in dependencies and cost of the condition. */
788 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
790 if (!add_dependency (val
, lim_data
, loop
, false))
792 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
794 total_cost
+= def_data
->cost
;
797 /* We want to avoid unconditionally executing very expensive
798 operations. As costs for our dependencies cannot be
799 negative just claim we are not invariand for this case.
800 We also are not sure whether the control-flow inside the
802 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
804 && total_cost
/ min_cost
<= 2))
807 /* Assume that the control-flow in the loop will vanish.
808 ??? We should verify this and not artificially increase
809 the cost if that is not the case. */
810 lim_data
->cost
+= stmt_cost (stmt
);
816 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
817 if (!add_dependency (val
, lim_data
, loop
, true))
820 if (gimple_vuse (stmt
))
822 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
827 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
828 if (!lim_data
->max_loop
)
833 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
835 if (!add_dependency (val
, lim_data
, loop
, false))
841 lim_data
->cost
+= stmt_cost (stmt
);
846 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
847 and that one of the operands of this statement is computed by STMT.
848 Ensure that STMT (together with all the statements that define its
849 operands) is hoisted at least out of the loop LEVEL. */
852 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
854 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
856 struct lim_aux_data
*lim_data
;
858 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
859 lim_data
= get_lim_data (stmt
);
860 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
861 stmt_loop
= find_common_loop (stmt_loop
,
862 loop_outer (lim_data
->tgt_loop
));
863 if (flow_loop_nested_p (stmt_loop
, level
))
866 gcc_assert (level
== lim_data
->max_loop
867 || flow_loop_nested_p (lim_data
->max_loop
, level
));
869 lim_data
->tgt_loop
= level
;
870 for (dep
= lim_data
->depends
; dep
; dep
= dep
->next
)
871 set_level (dep
->stmt
, orig_loop
, level
);
874 /* Determines an outermost loop from that we want to hoist the statement STMT.
875 For now we chose the outermost possible loop. TODO -- use profiling
876 information to set it more sanely. */
879 set_profitable_level (gimple stmt
)
881 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
884 /* Returns true if STMT is a call that has side effects. */
887 nonpure_call_p (gimple stmt
)
889 if (gimple_code (stmt
) != GIMPLE_CALL
)
892 return gimple_has_side_effects (stmt
);
895 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
898 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
900 gimple stmt
, stmt1
, stmt2
;
901 tree var
, name
, lhs
, type
;
903 gimple_stmt_iterator gsi
;
905 stmt
= gsi_stmt (*bsi
);
906 lhs
= gimple_assign_lhs (stmt
);
907 type
= TREE_TYPE (lhs
);
909 var
= create_tmp_var (type
, "reciptmp");
910 add_referenced_var (var
);
911 DECL_GIMPLE_REG_P (var
) = 1;
913 /* For vectors, create a VECTOR_CST full of 1's. */
914 if (TREE_CODE (type
) == VECTOR_TYPE
)
917 tree list
= NULL_TREE
;
918 real_one
= build_real (TREE_TYPE (type
), dconst1
);
919 len
= TYPE_VECTOR_SUBPARTS (type
);
920 for (i
= 0; i
< len
; i
++)
921 list
= tree_cons (NULL
, real_one
, list
);
922 real_one
= build_vector (type
, list
);
925 real_one
= build_real (type
, dconst1
);
927 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
,
928 var
, real_one
, gimple_assign_rhs2 (stmt
));
929 name
= make_ssa_name (var
, stmt1
);
930 gimple_assign_set_lhs (stmt1
, name
);
932 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
933 gimple_assign_rhs1 (stmt
));
935 /* Replace division stmt with reciprocal and multiply stmts.
936 The multiply stmt is not invariant, so update iterator
937 and avoid rescanning. */
939 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
940 gsi_replace (&gsi
, stmt2
, true);
942 /* Continue processing with invariant reciprocal statement. */
946 /* Check if the pattern at *BSI is a bittest of the form
947 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
950 rewrite_bittest (gimple_stmt_iterator
*bsi
)
952 gimple stmt
, use_stmt
, stmt1
, stmt2
;
953 tree lhs
, var
, name
, t
, a
, b
;
956 stmt
= gsi_stmt (*bsi
);
957 lhs
= gimple_assign_lhs (stmt
);
959 /* Verify that the single use of lhs is a comparison against zero. */
960 if (TREE_CODE (lhs
) != SSA_NAME
961 || !single_imm_use (lhs
, &use
, &use_stmt
)
962 || gimple_code (use_stmt
) != GIMPLE_COND
)
964 if (gimple_cond_lhs (use_stmt
) != lhs
965 || (gimple_cond_code (use_stmt
) != NE_EXPR
966 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
967 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
970 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
971 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
972 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
975 /* There is a conversion in between possibly inserted by fold. */
976 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
978 t
= gimple_assign_rhs1 (stmt1
);
979 if (TREE_CODE (t
) != SSA_NAME
980 || !has_single_use (t
))
982 stmt1
= SSA_NAME_DEF_STMT (t
);
983 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
987 /* Verify that B is loop invariant but A is not. Verify that with
988 all the stmt walking we are still in the same loop. */
989 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
990 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
993 a
= gimple_assign_rhs1 (stmt1
);
994 b
= gimple_assign_rhs2 (stmt1
);
996 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
997 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
999 gimple_stmt_iterator rsi
;
1002 var
= create_tmp_var (TREE_TYPE (a
), "shifttmp");
1003 add_referenced_var (var
);
1004 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
1005 build_int_cst (TREE_TYPE (a
), 1), b
);
1006 stmt1
= gimple_build_assign (var
, t
);
1007 name
= make_ssa_name (var
, stmt1
);
1008 gimple_assign_set_lhs (stmt1
, name
);
1011 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
1012 stmt2
= gimple_build_assign (var
, t
);
1013 name
= make_ssa_name (var
, stmt2
);
1014 gimple_assign_set_lhs (stmt2
, name
);
1016 /* Replace the SSA_NAME we compare against zero. Adjust
1017 the type of zero accordingly. */
1018 SET_USE (use
, name
);
1019 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
1021 /* Don't use gsi_replace here, none of the new assignments sets
1022 the variable originally set in stmt. Move bsi to stmt1, and
1023 then remove the original stmt, so that we get a chance to
1024 retain debug info for it. */
1026 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
1027 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
1028 gsi_remove (&rsi
, true);
1037 /* Determine the outermost loops in that statements in basic block BB are
1038 invariant, and record them to the LIM_DATA associated with the statements.
1039 Callback for walk_dominator_tree. */
1042 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1046 gimple_stmt_iterator bsi
;
1048 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1049 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1050 struct lim_aux_data
*lim_data
;
1052 if (!loop_outer (bb
->loop_father
))
1055 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1056 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1057 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1059 /* Look at PHI nodes, but only if there is at most two.
1060 ??? We could relax this further by post-processing the inserted
1061 code and transforming adjacent cond-exprs with the same predicate
1062 to control flow again. */
1063 bsi
= gsi_start_phis (bb
);
1064 if (!gsi_end_p (bsi
)
1065 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1066 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1067 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1069 stmt
= gsi_stmt (bsi
);
1071 pos
= movement_possibility (stmt
);
1072 if (pos
== MOVE_IMPOSSIBLE
)
1075 lim_data
= init_lim_data (stmt
);
1076 lim_data
->always_executed_in
= outermost
;
1078 if (!determine_max_movement (stmt
, false))
1080 lim_data
->max_loop
= NULL
;
1084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1086 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1087 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1088 loop_depth (lim_data
->max_loop
),
1092 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1093 set_profitable_level (stmt
);
1096 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1098 stmt
= gsi_stmt (bsi
);
1100 pos
= movement_possibility (stmt
);
1101 if (pos
== MOVE_IMPOSSIBLE
)
1103 if (nonpure_call_p (stmt
))
1108 /* Make sure to note always_executed_in for stores to make
1109 store-motion work. */
1110 else if (stmt_makes_single_store (stmt
))
1112 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1113 lim_data
->always_executed_in
= outermost
;
1118 if (is_gimple_assign (stmt
)
1119 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1120 == GIMPLE_BINARY_RHS
))
1122 tree op0
= gimple_assign_rhs1 (stmt
);
1123 tree op1
= gimple_assign_rhs2 (stmt
);
1124 struct loop
*ol1
= outermost_invariant_loop (op1
,
1125 loop_containing_stmt (stmt
));
1127 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1128 to be hoisted out of loop, saving expensive divide. */
1129 if (pos
== MOVE_POSSIBLE
1130 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1131 && flag_unsafe_math_optimizations
1132 && !flag_trapping_math
1134 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1135 stmt
= rewrite_reciprocal (&bsi
);
1137 /* If the shift count is invariant, convert (A >> B) & 1 to
1138 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1139 saving an expensive shift. */
1140 if (pos
== MOVE_POSSIBLE
1141 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1142 && integer_onep (op1
)
1143 && TREE_CODE (op0
) == SSA_NAME
1144 && has_single_use (op0
))
1145 stmt
= rewrite_bittest (&bsi
);
1148 lim_data
= init_lim_data (stmt
);
1149 lim_data
->always_executed_in
= outermost
;
1151 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1154 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1156 lim_data
->max_loop
= NULL
;
1160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1162 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1163 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1164 loop_depth (lim_data
->max_loop
),
1168 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1169 set_profitable_level (stmt
);
1173 /* For each statement determines the outermost loop in that it is invariant,
1174 statements on whose motion it depends and the cost of the computation.
1175 This information is stored to the LIM_DATA structure associated with
1179 determine_invariantness (void)
1181 struct dom_walk_data walk_data
;
1183 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1184 walk_data
.dom_direction
= CDI_DOMINATORS
;
1185 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1187 init_walk_dominator_tree (&walk_data
);
1188 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1189 fini_walk_dominator_tree (&walk_data
);
1192 /* Hoist the statements in basic block BB out of the loops prescribed by
1193 data stored in LIM_DATA structures associated with each statement. Callback
1194 for walk_dominator_tree. */
1197 move_computations_stmt (struct dom_walk_data
*dw_data
,
1201 gimple_stmt_iterator bsi
;
1204 struct lim_aux_data
*lim_data
;
1206 if (!loop_outer (bb
->loop_father
))
1209 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1212 stmt
= gsi_stmt (bsi
);
1214 lim_data
= get_lim_data (stmt
);
1215 if (lim_data
== NULL
)
1221 cost
= lim_data
->cost
;
1222 level
= lim_data
->tgt_loop
;
1223 clear_lim_data (stmt
);
1231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1233 fprintf (dump_file
, "Moving PHI node\n");
1234 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1235 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1239 if (gimple_phi_num_args (stmt
) == 1)
1241 tree arg
= PHI_ARG_DEF (stmt
, 0);
1242 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1243 gimple_phi_result (stmt
),
1245 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1249 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1250 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1251 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1252 /* Get the PHI arguments corresponding to the true and false
1254 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1255 gcc_assert (arg0
&& arg1
);
1256 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1257 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1258 t
= build3 (COND_EXPR
, TREE_TYPE (gimple_phi_result (stmt
)),
1260 new_stmt
= gimple_build_assign_with_ops (COND_EXPR
,
1261 gimple_phi_result (stmt
),
1263 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1264 *((unsigned int *)(dw_data
->global_data
)) |= TODO_cleanup_cfg
;
1266 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1267 remove_phi_node (&bsi
, false);
1270 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1272 stmt
= gsi_stmt (bsi
);
1274 lim_data
= get_lim_data (stmt
);
1275 if (lim_data
== NULL
)
1281 cost
= lim_data
->cost
;
1282 level
= lim_data
->tgt_loop
;
1283 clear_lim_data (stmt
);
1291 /* We do not really want to move conditionals out of the loop; we just
1292 placed it here to force its operands to be moved if necessary. */
1293 if (gimple_code (stmt
) == GIMPLE_COND
)
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1298 fprintf (dump_file
, "Moving statement\n");
1299 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1300 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1304 mark_virtual_ops_for_renaming (stmt
);
1305 gsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
1306 gsi_remove (&bsi
, false);
1310 /* Hoist the statements out of the loops prescribed by data stored in
1311 LIM_DATA structures associated with each statement.*/
1314 move_computations (void)
1316 struct dom_walk_data walk_data
;
1317 unsigned int todo
= 0;
1319 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1320 walk_data
.global_data
= &todo
;
1321 walk_data
.dom_direction
= CDI_DOMINATORS
;
1322 walk_data
.before_dom_children
= move_computations_stmt
;
1324 init_walk_dominator_tree (&walk_data
);
1325 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1326 fini_walk_dominator_tree (&walk_data
);
1328 gsi_commit_edge_inserts ();
1329 if (need_ssa_update_p (cfun
))
1330 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1335 /* Checks whether the statement defining variable *INDEX can be hoisted
1336 out of the loop passed in DATA. Callback for for_each_index. */
1339 may_move_till (tree ref
, tree
*index
, void *data
)
1341 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1343 /* If REF is an array reference, check also that the step and the lower
1344 bound is invariant in LOOP. */
1345 if (TREE_CODE (ref
) == ARRAY_REF
)
1347 tree step
= TREE_OPERAND (ref
, 3);
1348 tree lbound
= TREE_OPERAND (ref
, 2);
1350 max_loop
= outermost_invariant_loop (step
, loop
);
1354 max_loop
= outermost_invariant_loop (lbound
, loop
);
1359 max_loop
= outermost_invariant_loop (*index
, loop
);
1366 /* If OP is SSA NAME, force the statement that defines it to be
1367 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1370 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1375 || is_gimple_min_invariant (op
))
1378 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1380 stmt
= SSA_NAME_DEF_STMT (op
);
1381 if (gimple_nop_p (stmt
))
1384 set_level (stmt
, orig_loop
, loop
);
1387 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1388 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1394 struct loop
*orig_loop
;
1398 force_move_till (tree ref
, tree
*index
, void *data
)
1400 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1402 if (TREE_CODE (ref
) == ARRAY_REF
)
1404 tree step
= TREE_OPERAND (ref
, 3);
1405 tree lbound
= TREE_OPERAND (ref
, 2);
1407 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1408 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1411 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1416 /* A hash function for struct mem_ref object OBJ. */
1419 memref_hash (const void *obj
)
1421 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1426 /* An equality function for struct mem_ref object OBJ1 with
1427 memory reference OBJ2. */
1430 memref_eq (const void *obj1
, const void *obj2
)
1432 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1434 return operand_equal_p (mem1
->mem
, (const_tree
) obj2
, 0);
1437 /* Releases list of memory reference locations ACCS. */
1440 free_mem_ref_locs (mem_ref_locs_p accs
)
1448 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1450 VEC_free (mem_ref_loc_p
, heap
, accs
->locs
);
1454 /* A function to free the mem_ref object OBJ. */
1457 memref_free (void *obj
)
1459 struct mem_ref
*const mem
= (struct mem_ref
*) obj
;
1461 mem_ref_locs_p accs
;
1463 BITMAP_FREE (mem
->stored
);
1464 BITMAP_FREE (mem
->indep_loop
);
1465 BITMAP_FREE (mem
->dep_loop
);
1466 BITMAP_FREE (mem
->indep_ref
);
1467 BITMAP_FREE (mem
->dep_ref
);
1469 FOR_EACH_VEC_ELT (mem_ref_locs_p
, mem
->accesses_in_loop
, i
, accs
)
1470 free_mem_ref_locs (accs
);
1471 VEC_free (mem_ref_locs_p
, heap
, mem
->accesses_in_loop
);
1473 BITMAP_FREE (mem
->vops
);
1477 /* Allocates and returns a memory reference description for MEM whose hash
1478 value is HASH and id is ID. */
1481 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1483 mem_ref_p ref
= XNEW (struct mem_ref
);
1487 ref
->stored
= BITMAP_ALLOC (NULL
);
1488 ref
->indep_loop
= BITMAP_ALLOC (NULL
);
1489 ref
->dep_loop
= BITMAP_ALLOC (NULL
);
1490 ref
->indep_ref
= BITMAP_ALLOC (NULL
);
1491 ref
->dep_ref
= BITMAP_ALLOC (NULL
);
1492 ref
->accesses_in_loop
= NULL
;
1493 ref
->vops
= BITMAP_ALLOC (NULL
);
1498 /* Allocates and returns the new list of locations. */
1500 static mem_ref_locs_p
1501 mem_ref_locs_alloc (void)
1503 mem_ref_locs_p accs
= XNEW (struct mem_ref_locs
);
1508 /* Records memory reference location *LOC in LOOP to the memory reference
1509 description REF. The reference occurs in statement STMT. */
1512 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1514 mem_ref_loc_p aref
= XNEW (struct mem_ref_loc
);
1515 mem_ref_locs_p accs
;
1516 bitmap ril
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1518 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1519 <= (unsigned) loop
->num
)
1520 VEC_safe_grow_cleared (mem_ref_locs_p
, heap
, ref
->accesses_in_loop
,
1522 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1525 accs
= mem_ref_locs_alloc ();
1526 VEC_replace (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
, accs
);
1532 VEC_safe_push (mem_ref_loc_p
, heap
, accs
->locs
, aref
);
1533 bitmap_set_bit (ril
, ref
->id
);
1536 /* Marks reference REF as stored in LOOP. */
1539 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1542 loop
!= current_loops
->tree_root
1543 && !bitmap_bit_p (ref
->stored
, loop
->num
);
1544 loop
= loop_outer (loop
))
1545 bitmap_set_bit (ref
->stored
, loop
->num
);
1548 /* Gathers memory references in statement STMT in LOOP, storing the
1549 information about them in the memory_accesses structure. Marks
1550 the vops accessed through unrecognized statements there as
1554 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1565 if (!gimple_vuse (stmt
))
1568 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1572 hash
= iterative_hash_expr (*mem
, 0);
1573 slot
= htab_find_slot_with_hash (memory_accesses
.refs
, *mem
, hash
, INSERT
);
1577 ref
= (mem_ref_p
) *slot
;
1582 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1583 ref
= mem_ref_alloc (*mem
, hash
, id
);
1584 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1589 fprintf (dump_file
, "Memory reference %u: ", id
);
1590 print_generic_expr (dump_file
, ref
->mem
, TDF_SLIM
);
1591 fprintf (dump_file
, "\n");
1595 mark_ref_stored (ref
, loop
);
1597 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1598 bitmap_set_bit (ref
->vops
, DECL_UID (SSA_NAME_VAR (vname
)));
1599 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1603 clvops
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1604 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1605 bitmap_set_bit (clvops
, DECL_UID (SSA_NAME_VAR (vname
)));
1608 /* Gathers memory references in loops. */
1611 gather_mem_refs_in_loops (void)
1613 gimple_stmt_iterator bsi
;
1618 bitmap lrefs
, alrefs
, alrefso
;
1622 loop
= bb
->loop_father
;
1623 if (loop
== current_loops
->tree_root
)
1626 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1627 gather_mem_refs_stmt (loop
, gsi_stmt (bsi
));
1630 /* Propagate the information about clobbered vops and accessed memory
1631 references up the loop hierarchy. */
1632 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1634 lrefs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1635 alrefs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
, loop
->num
);
1636 bitmap_ior_into (alrefs
, lrefs
);
1638 if (loop_outer (loop
) == current_loops
->tree_root
)
1641 clvi
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1642 clvo
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1643 loop_outer (loop
)->num
);
1644 bitmap_ior_into (clvo
, clvi
);
1646 alrefso
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1647 loop_outer (loop
)->num
);
1648 bitmap_ior_into (alrefso
, alrefs
);
1652 /* Element of the hash table that maps vops to memory references. */
1654 struct vop_to_refs_elt
1656 /* DECL_UID of the vop. */
1659 /* List of the all references. */
1662 /* List of stored references. */
1666 /* A hash function for struct vop_to_refs_elt object OBJ. */
1669 vtoe_hash (const void *obj
)
1671 const struct vop_to_refs_elt
*const vtoe
=
1672 (const struct vop_to_refs_elt
*) obj
;
1677 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1678 uid of a vop OBJ2. */
1681 vtoe_eq (const void *obj1
, const void *obj2
)
1683 const struct vop_to_refs_elt
*const vtoe
=
1684 (const struct vop_to_refs_elt
*) obj1
;
1685 const unsigned *const uid
= (const unsigned *) obj2
;
1687 return vtoe
->uid
== *uid
;
1690 /* A function to free the struct vop_to_refs_elt object. */
1693 vtoe_free (void *obj
)
1695 struct vop_to_refs_elt
*const vtoe
=
1696 (struct vop_to_refs_elt
*) obj
;
1698 BITMAP_FREE (vtoe
->refs_all
);
1699 BITMAP_FREE (vtoe
->refs_stored
);
1703 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1704 if the reference REF is stored. */
1707 record_vop_access (htab_t vop_to_refs
, unsigned vop
, unsigned ref
, bool stored
)
1709 void **slot
= htab_find_slot_with_hash (vop_to_refs
, &vop
, vop
, INSERT
);
1710 struct vop_to_refs_elt
*vtoe
;
1714 vtoe
= XNEW (struct vop_to_refs_elt
);
1716 vtoe
->refs_all
= BITMAP_ALLOC (NULL
);
1717 vtoe
->refs_stored
= BITMAP_ALLOC (NULL
);
1721 vtoe
= (struct vop_to_refs_elt
*) *slot
;
1723 bitmap_set_bit (vtoe
->refs_all
, ref
);
1725 bitmap_set_bit (vtoe
->refs_stored
, ref
);
1728 /* Returns the set of references that access VOP according to the table
1732 get_vop_accesses (htab_t vop_to_refs
, unsigned vop
)
1734 struct vop_to_refs_elt
*const vtoe
=
1735 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1736 return vtoe
->refs_all
;
1739 /* Returns the set of stores that access VOP according to the table
1743 get_vop_stores (htab_t vop_to_refs
, unsigned vop
)
1745 struct vop_to_refs_elt
*const vtoe
=
1746 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1747 return vtoe
->refs_stored
;
1750 /* Adds REF to mapping from virtual operands to references in LOOP. */
1753 add_vop_ref_mapping (struct loop
*loop
, mem_ref_p ref
)
1755 htab_t map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
1756 bool stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
1757 bitmap clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1762 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, vop
, bi
)
1764 record_vop_access (map
, vop
, ref
->id
, stored
);
1768 /* Create a mapping from virtual operands to references that touch them
1772 create_vop_ref_mapping_loop (struct loop
*loop
)
1774 bitmap refs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1780 EXECUTE_IF_SET_IN_BITMAP (refs
, 0, i
, bi
)
1782 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1783 for (sloop
= loop
; sloop
!= current_loops
->tree_root
; sloop
= loop_outer (sloop
))
1784 add_vop_ref_mapping (sloop
, ref
);
1788 /* For each non-clobbered virtual operand and each loop, record the memory
1789 references in this loop that touch the operand. */
1792 create_vop_ref_mapping (void)
1797 FOR_EACH_LOOP (li
, loop
, 0)
1799 create_vop_ref_mapping_loop (loop
);
1803 /* Gathers information about memory accesses in the loops. */
1806 analyze_memory_references (void)
1812 memory_accesses
.refs
1813 = htab_create (100, memref_hash
, memref_eq
, memref_free
);
1814 memory_accesses
.refs_list
= NULL
;
1815 memory_accesses
.refs_in_loop
= VEC_alloc (bitmap
, heap
,
1816 number_of_loops ());
1817 memory_accesses
.all_refs_in_loop
= VEC_alloc (bitmap
, heap
,
1818 number_of_loops ());
1819 memory_accesses
.clobbered_vops
= VEC_alloc (bitmap
, heap
,
1820 number_of_loops ());
1821 memory_accesses
.vop_ref_map
= VEC_alloc (htab_t
, heap
,
1822 number_of_loops ());
1824 for (i
= 0; i
< number_of_loops (); i
++)
1826 empty
= BITMAP_ALLOC (NULL
);
1827 VEC_quick_push (bitmap
, memory_accesses
.refs_in_loop
, empty
);
1828 empty
= BITMAP_ALLOC (NULL
);
1829 VEC_quick_push (bitmap
, memory_accesses
.all_refs_in_loop
, empty
);
1830 empty
= BITMAP_ALLOC (NULL
);
1831 VEC_quick_push (bitmap
, memory_accesses
.clobbered_vops
, empty
);
1832 hempty
= htab_create (10, vtoe_hash
, vtoe_eq
, vtoe_free
);
1833 VEC_quick_push (htab_t
, memory_accesses
.vop_ref_map
, hempty
);
1836 memory_accesses
.ttae_cache
= NULL
;
1838 gather_mem_refs_in_loops ();
1839 create_vop_ref_mapping ();
1842 /* Returns true if a region of size SIZE1 at position 0 and a region of
1843 size SIZE2 at position DIFF cannot overlap. */
1846 cannot_overlap_p (aff_tree
*diff
, double_int size1
, double_int size2
)
1848 double_int d
, bound
;
1850 /* Unless the difference is a constant, we fail. */
1855 if (double_int_negative_p (d
))
1857 /* The second object is before the first one, we succeed if the last
1858 element of the second object is before the start of the first one. */
1859 bound
= double_int_add (d
, double_int_add (size2
, double_int_minus_one
));
1860 return double_int_negative_p (bound
);
1864 /* We succeed if the second object starts after the first one ends. */
1865 return double_int_scmp (size1
, d
) <= 0;
1869 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1870 tree_to_aff_combination_expand. */
1873 mem_refs_may_alias_p (tree mem1
, tree mem2
, struct pointer_map_t
**ttae_cache
)
1875 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1876 object and their offset differ in such a way that the locations cannot
1877 overlap, then they cannot alias. */
1878 double_int size1
, size2
;
1879 aff_tree off1
, off2
;
1881 /* Perform basic offset and type-based disambiguation. */
1882 if (!refs_may_alias_p (mem1
, mem2
))
1885 /* The expansion of addresses may be a bit expensive, thus we only do
1886 the check at -O2 and higher optimization levels. */
1890 get_inner_reference_aff (mem1
, &off1
, &size1
);
1891 get_inner_reference_aff (mem2
, &off2
, &size2
);
1892 aff_combination_expand (&off1
, ttae_cache
);
1893 aff_combination_expand (&off2
, ttae_cache
);
1894 aff_combination_scale (&off1
, double_int_minus_one
);
1895 aff_combination_add (&off2
, &off1
);
1897 if (cannot_overlap_p (&off2
, size1
, size2
))
1903 /* Rewrites location LOC by TMP_VAR. */
1906 rewrite_mem_ref_loc (mem_ref_loc_p loc
, tree tmp_var
)
1908 mark_virtual_ops_for_renaming (loc
->stmt
);
1909 *loc
->ref
= tmp_var
;
1910 update_stmt (loc
->stmt
);
1913 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1916 get_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
,
1917 VEC (mem_ref_loc_p
, heap
) **locs
)
1919 mem_ref_locs_p accs
;
1922 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1924 struct loop
*subloop
;
1926 if (!bitmap_bit_p (refs
, ref
->id
))
1929 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1930 > (unsigned) loop
->num
)
1932 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1935 FOR_EACH_VEC_ELT (mem_ref_loc_p
, accs
->locs
, i
, loc
)
1936 VEC_safe_push (mem_ref_loc_p
, heap
, *locs
, loc
);
1940 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1941 get_all_locs_in_loop (subloop
, ref
, locs
);
1944 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1947 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1951 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1953 get_all_locs_in_loop (loop
, ref
, &locs
);
1954 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
1955 rewrite_mem_ref_loc (loc
, tmp_var
);
1956 VEC_free (mem_ref_loc_p
, heap
, locs
);
1959 /* The name and the length of the currently generated variable
1961 #define MAX_LSM_NAME_LENGTH 40
1962 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1963 static int lsm_tmp_name_length
;
1965 /* Adds S to lsm_tmp_name. */
1968 lsm_tmp_name_add (const char *s
)
1970 int l
= strlen (s
) + lsm_tmp_name_length
;
1971 if (l
> MAX_LSM_NAME_LENGTH
)
1974 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1975 lsm_tmp_name_length
= l
;
1978 /* Stores the name for temporary variable that replaces REF to
1982 gen_lsm_tmp_name (tree ref
)
1986 switch (TREE_CODE (ref
))
1989 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1990 lsm_tmp_name_add ("_");
1994 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1998 case VIEW_CONVERT_EXPR
:
1999 case ARRAY_RANGE_REF
:
2000 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2004 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2005 lsm_tmp_name_add ("_RE");
2009 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2010 lsm_tmp_name_add ("_IM");
2014 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2015 lsm_tmp_name_add ("_");
2016 name
= get_name (TREE_OPERAND (ref
, 1));
2019 lsm_tmp_name_add (name
);
2023 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
2024 lsm_tmp_name_add ("_I");
2028 ref
= SSA_NAME_VAR (ref
);
2033 name
= get_name (ref
);
2036 lsm_tmp_name_add (name
);
2040 lsm_tmp_name_add ("S");
2044 lsm_tmp_name_add ("R");
2056 /* Determines name for temporary variable that replaces REF.
2057 The name is accumulated into the lsm_tmp_name variable.
2058 N is added to the name of the temporary. */
2061 get_lsm_tmp_name (tree ref
, unsigned n
)
2065 lsm_tmp_name_length
= 0;
2066 gen_lsm_tmp_name (ref
);
2067 lsm_tmp_name_add ("_lsm");
2072 lsm_tmp_name_add (ns
);
2074 return lsm_tmp_name
;
2077 /* Executes store motion of memory reference REF from LOOP.
2078 Exits from the LOOP are stored in EXITS. The initialization of the
2079 temporary variable is put to the preheader of the loop, and assignments
2080 to the reference from the temporary variable are emitted to exits. */
2083 execute_sm (struct loop
*loop
, VEC (edge
, heap
) *exits
, mem_ref_p ref
)
2088 struct fmt_data fmt_data
;
2090 struct lim_aux_data
*lim_data
;
2092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2094 fprintf (dump_file
, "Executing store motion of ");
2095 print_generic_expr (dump_file
, ref
->mem
, 0);
2096 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2099 tmp_var
= make_rename_temp (TREE_TYPE (ref
->mem
),
2100 get_lsm_tmp_name (ref
->mem
, ~0));
2102 fmt_data
.loop
= loop
;
2103 fmt_data
.orig_loop
= loop
;
2104 for_each_index (&ref
->mem
, force_move_till
, &fmt_data
);
2106 rewrite_mem_refs (loop
, ref
, tmp_var
);
2108 /* Emit the load & stores. */
2109 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
));
2110 lim_data
= init_lim_data (load
);
2111 lim_data
->max_loop
= loop
;
2112 lim_data
->tgt_loop
= loop
;
2114 /* Put this into the latch, so that we are sure it will be processed after
2115 all dependencies. */
2116 gsi_insert_on_edge (loop_latch_edge (loop
), load
);
2118 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2120 store
= gimple_build_assign (unshare_expr (ref
->mem
), tmp_var
);
2121 gsi_insert_on_edge (ex
, store
);
2125 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2126 edges of the LOOP. */
2129 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2130 VEC (edge
, heap
) *exits
)
2136 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2138 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2139 execute_sm (loop
, exits
, ref
);
2143 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2144 make sure REF is always stored to in LOOP. */
2147 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2149 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
2153 struct loop
*must_exec
;
2156 base
= get_base_address (ref
->mem
);
2157 if (INDIRECT_REF_P (base
)
2158 || TREE_CODE (base
) == MEM_REF
)
2159 base
= TREE_OPERAND (base
, 0);
2161 get_all_locs_in_loop (loop
, ref
, &locs
);
2162 FOR_EACH_VEC_ELT (mem_ref_loc_p
, locs
, i
, loc
)
2164 if (!get_lim_data (loc
->stmt
))
2167 /* If we require an always executed store make sure the statement
2168 stores to the reference. */
2172 if (!gimple_get_lhs (loc
->stmt
))
2174 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2177 if (INDIRECT_REF_P (lhs
)
2178 || TREE_CODE (lhs
) == MEM_REF
)
2179 lhs
= TREE_OPERAND (lhs
, 0);
2184 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2188 if (must_exec
== loop
2189 || flow_loop_nested_p (must_exec
, loop
))
2195 VEC_free (mem_ref_loc_p
, heap
, locs
);
2200 /* Returns true if REF1 and REF2 are independent. */
2203 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2206 || bitmap_bit_p (ref1
->indep_ref
, ref2
->id
))
2208 if (bitmap_bit_p (ref1
->dep_ref
, ref2
->id
))
2211 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2212 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2213 ref1
->id
, ref2
->id
);
2215 if (mem_refs_may_alias_p (ref1
->mem
, ref2
->mem
,
2216 &memory_accesses
.ttae_cache
))
2218 bitmap_set_bit (ref1
->dep_ref
, ref2
->id
);
2219 bitmap_set_bit (ref2
->dep_ref
, ref1
->id
);
2220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2221 fprintf (dump_file
, "dependent.\n");
2226 bitmap_set_bit (ref1
->indep_ref
, ref2
->id
);
2227 bitmap_set_bit (ref2
->indep_ref
, ref1
->id
);
2228 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2229 fprintf (dump_file
, "independent.\n");
2234 /* Records the information whether REF is independent in LOOP (according
2238 record_indep_loop (struct loop
*loop
, mem_ref_p ref
, bool indep
)
2241 bitmap_set_bit (ref
->indep_loop
, loop
->num
);
2243 bitmap_set_bit (ref
->dep_loop
, loop
->num
);
2246 /* Returns true if REF is independent on all other memory references in
2250 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
)
2252 bitmap clobbers
, refs_to_check
, refs
;
2255 bool ret
= true, stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
2259 /* If the reference is clobbered, it is not independent. */
2260 clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
2261 if (bitmap_intersect_p (ref
->vops
, clobbers
))
2264 refs_to_check
= BITMAP_ALLOC (NULL
);
2266 map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
2267 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, i
, bi
)
2270 refs
= get_vop_accesses (map
, i
);
2272 refs
= get_vop_stores (map
, i
);
2274 bitmap_ior_into (refs_to_check
, refs
);
2277 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2279 aref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2280 if (!refs_independent_p (ref
, aref
))
2283 record_indep_loop (loop
, aref
, false);
2288 BITMAP_FREE (refs_to_check
);
2292 /* Returns true if REF is independent on all other memory references in
2293 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2296 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2300 if (bitmap_bit_p (ref
->indep_loop
, loop
->num
))
2302 if (bitmap_bit_p (ref
->dep_loop
, loop
->num
))
2305 ret
= ref_indep_loop_p_1 (loop
, ref
);
2307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2308 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2309 ref
->id
, loop
->num
, ret
? "independent" : "dependent");
2311 record_indep_loop (loop
, ref
, ret
);
2316 /* Returns true if we can perform store motion of REF from LOOP. */
2319 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2323 /* Unless the reference is stored in the loop, there is nothing to do. */
2324 if (!bitmap_bit_p (ref
->stored
, loop
->num
))
2327 /* It should be movable. */
2328 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
))
2329 || TREE_THIS_VOLATILE (ref
->mem
)
2330 || !for_each_index (&ref
->mem
, may_move_till
, loop
))
2333 /* If it can trap, it must be always executed in LOOP.
2334 Readonly memory locations may trap when storing to them, but
2335 tree_could_trap_p is a predicate for rvalues, so check that
2337 base
= get_base_address (ref
->mem
);
2338 if ((tree_could_trap_p (ref
->mem
)
2339 || (DECL_P (base
) && TREE_READONLY (base
)))
2340 && !ref_always_accessed_p (loop
, ref
, true))
2343 /* And it must be independent on all other memory references
2345 if (!ref_indep_loop_p (loop
, ref
))
2351 /* Marks the references in LOOP for that store motion should be performed
2352 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2353 motion was performed in one of the outer loops. */
2356 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2358 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
2364 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2366 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2367 if (can_sm_ref_p (loop
, ref
))
2368 bitmap_set_bit (refs_to_sm
, i
);
2372 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2373 for a store motion optimization (i.e. whether we can insert statement
2377 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2378 VEC (edge
, heap
) *exits
)
2383 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2384 if (ex
->flags
& EDGE_ABNORMAL
)
2390 /* Try to perform store motion for all memory references modified inside
2391 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2392 store motion was executed in one of the outer loops. */
2395 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2397 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2398 struct loop
*subloop
;
2399 bitmap sm_in_loop
= BITMAP_ALLOC (NULL
);
2401 if (loop_suitable_for_sm (loop
, exits
))
2403 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2404 hoist_memory_references (loop
, sm_in_loop
, exits
);
2406 VEC_free (edge
, heap
, exits
);
2408 bitmap_ior_into (sm_executed
, sm_in_loop
);
2409 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2410 store_motion_loop (subloop
, sm_executed
);
2411 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2412 BITMAP_FREE (sm_in_loop
);
2415 /* Try to perform store motion for all memory references modified inside
2422 bitmap sm_executed
= BITMAP_ALLOC (NULL
);
2424 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2425 store_motion_loop (loop
, sm_executed
);
2427 BITMAP_FREE (sm_executed
);
2428 gsi_commit_edge_inserts ();
2431 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2432 for each such basic block bb records the outermost loop for that execution
2433 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2434 blocks that contain a nonpure call. */
2437 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
2439 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2442 struct loop
*inn_loop
= loop
;
2444 if (!loop
->header
->aux
)
2446 bbs
= get_loop_body_in_dom_order (loop
);
2448 for (i
= 0; i
< loop
->num_nodes
; i
++)
2453 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2456 if (TEST_BIT (contains_call
, bb
->index
))
2459 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2460 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2465 /* A loop might be infinite (TODO use simple loop analysis
2466 to disprove this if possible). */
2467 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2470 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2473 if (bb
->loop_father
->header
== bb
)
2475 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2478 /* In a loop that is always entered we may proceed anyway.
2479 But record that we entered it and stop once we leave it. */
2480 inn_loop
= bb
->loop_father
;
2487 if (last
== loop
->header
)
2489 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2495 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2496 fill_always_executed_in (loop
, contains_call
);
2499 /* Compute the global information needed by the loop invariant motion pass. */
2502 tree_ssa_lim_initialize (void)
2504 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2505 gimple_stmt_iterator bsi
;
2509 sbitmap_zero (contains_call
);
2512 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2514 if (nonpure_call_p (gsi_stmt (bsi
)))
2518 if (!gsi_end_p (bsi
))
2519 SET_BIT (contains_call
, bb
->index
);
2522 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2523 fill_always_executed_in (loop
, contains_call
);
2525 sbitmap_free (contains_call
);
2527 lim_aux_data_map
= pointer_map_create ();
2530 /* Cleans up after the invariant motion pass. */
2533 tree_ssa_lim_finalize (void)
2545 pointer_map_destroy (lim_aux_data_map
);
2547 VEC_free (mem_ref_p
, heap
, memory_accesses
.refs_list
);
2548 htab_delete (memory_accesses
.refs
);
2550 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.refs_in_loop
, i
, b
)
2552 VEC_free (bitmap
, heap
, memory_accesses
.refs_in_loop
);
2554 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.all_refs_in_loop
, i
, b
)
2556 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_in_loop
);
2558 FOR_EACH_VEC_ELT (bitmap
, memory_accesses
.clobbered_vops
, i
, b
)
2560 VEC_free (bitmap
, heap
, memory_accesses
.clobbered_vops
);
2562 FOR_EACH_VEC_ELT (htab_t
, memory_accesses
.vop_ref_map
, i
, h
)
2564 VEC_free (htab_t
, heap
, memory_accesses
.vop_ref_map
);
2566 if (memory_accesses
.ttae_cache
)
2567 pointer_map_destroy (memory_accesses
.ttae_cache
);
2570 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2571 i.e. those that are likely to be win regardless of the register pressure. */
2578 tree_ssa_lim_initialize ();
2580 /* Gathers information about memory accesses in the loops. */
2581 analyze_memory_references ();
2583 /* For each statement determine the outermost loop in that it is
2584 invariant and cost for computing the invariant. */
2585 determine_invariantness ();
2587 /* Execute store motion. Force the necessary invariants to be moved
2588 out of the loops as well. */
2591 /* Move the expressions that are expensive enough. */
2592 todo
= move_computations ();
2594 tree_ssa_lim_finalize ();