1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
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"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
42 #include "tree-affine.h"
43 #include "pointer-set.h"
44 #include "tree-ssa-propagate.h"
46 /* TODO: Support for predicated code motion. I.e.
57 Where COND and INV are is invariants, but evaluating INV may trap or be
58 invalid from some other reason if !COND. This may be transformed to
68 /* A type for the list of statements that have to be moved in order to be able
69 to hoist an invariant computation. */
77 /* The auxiliary data kept for each statement. */
81 struct loop
*max_loop
; /* The outermost loop in that the statement
84 struct loop
*tgt_loop
; /* The loop out of that we want to move the
87 struct loop
*always_executed_in
;
88 /* The outermost loop for that we are sure
89 the statement is executed if the loop
92 unsigned cost
; /* Cost of the computation performed by the
95 struct depend
*depends
; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
102 /* Maps statements to their lim_aux_data. */
104 static struct pointer_map_t
*lim_aux_data_map
;
106 /* Description of a memory reference location. */
108 typedef struct mem_ref_loc
110 tree
*ref
; /* The reference itself. */
111 gimple stmt
; /* The statement in that it occurs. */
114 DEF_VEC_P(mem_ref_loc_p
);
115 DEF_VEC_ALLOC_P(mem_ref_loc_p
, heap
);
117 /* The list of memory reference locations in a loop. */
119 typedef struct mem_ref_locs
121 VEC (mem_ref_loc_p
, heap
) *locs
;
124 DEF_VEC_P(mem_ref_locs_p
);
125 DEF_VEC_ALLOC_P(mem_ref_locs_p
, heap
);
127 /* Description of a memory reference. */
129 typedef struct mem_ref
131 tree mem
; /* The memory itself. */
132 unsigned id
; /* ID assigned to the memory reference
133 (its index in memory_accesses.refs_list) */
134 hashval_t hash
; /* Its hash value. */
135 bitmap stored
; /* The set of loops in that this memory location
137 VEC (mem_ref_locs_p
, heap
) *accesses_in_loop
;
138 /* The locations of the accesses. Vector
139 indexed by the loop number. */
140 bitmap vops
; /* Vops corresponding to this memory
143 /* The following sets are computed on demand. We keep both set and
144 its complement, so that we know whether the information was
145 already computed or not. */
146 bitmap indep_loop
; /* The set of loops in that the memory
147 reference is independent, meaning:
148 If it is stored in the loop, this store
149 is independent on all other loads and
151 If it is only loaded, then it is independent
152 on all stores in the loop. */
153 bitmap dep_loop
; /* The complement of INDEP_LOOP. */
155 bitmap indep_ref
; /* The set of memory references on that
156 this reference is independent. */
157 bitmap dep_ref
; /* The complement of DEP_REF. */
160 DEF_VEC_P(mem_ref_p
);
161 DEF_VEC_ALLOC_P(mem_ref_p
, heap
);
164 DEF_VEC_ALLOC_P(bitmap
, heap
);
167 DEF_VEC_ALLOC_P(htab_t
, heap
);
169 /* Description of memory accesses in loops. */
173 /* The hash table of memory references accessed in loops. */
176 /* The list of memory references. */
177 VEC (mem_ref_p
, heap
) *refs_list
;
179 /* The set of memory references accessed in each loop. */
180 VEC (bitmap
, heap
) *refs_in_loop
;
182 /* The set of memory references accessed in each loop, including
184 VEC (bitmap
, heap
) *all_refs_in_loop
;
186 /* The set of virtual operands clobbered in a given loop. */
187 VEC (bitmap
, heap
) *clobbered_vops
;
189 /* Map from the pair (loop, virtual operand) to the set of refs that
190 touch the virtual operand in the loop. */
191 VEC (htab_t
, heap
) *vop_ref_map
;
193 /* Cache for expanding memory addresses. */
194 struct pointer_map_t
*ttae_cache
;
197 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
199 /* Minimum cost of an expensive expression. */
200 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
202 /* The outermost loop for that execution of the header guarantees that the
203 block will be executed. */
204 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
206 static struct lim_aux_data
*
207 init_lim_data (gimple stmt
)
209 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
211 *p
= XCNEW (struct lim_aux_data
);
212 return (struct lim_aux_data
*) *p
;
215 static struct lim_aux_data
*
216 get_lim_data (gimple stmt
)
218 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
222 return (struct lim_aux_data
*) *p
;
225 /* Releases the memory occupied by DATA. */
228 free_lim_aux_data (struct lim_aux_data
*data
)
230 struct depend
*dep
, *next
;
232 for (dep
= data
->depends
; dep
; dep
= next
)
241 clear_lim_data (gimple stmt
)
243 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
247 free_lim_aux_data ((struct lim_aux_data
*) *p
);
251 /* Calls CBCK for each index in memory reference ADDR_P. There are two
252 kinds situations handled; in each of these cases, the memory reference
253 and DATA are passed to the callback:
255 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
256 pass the pointer to the index to the callback.
258 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
259 pointer to addr to the callback.
261 If the callback returns false, the whole search stops and false is returned.
262 Otherwise the function returns true after traversing through the whole
263 reference *ADDR_P. */
266 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
270 for (; ; addr_p
= nxt
)
272 switch (TREE_CODE (*addr_p
))
275 return cbck (*addr_p
, addr_p
, data
);
277 case MISALIGNED_INDIRECT_REF
:
278 case ALIGN_INDIRECT_REF
:
280 nxt
= &TREE_OPERAND (*addr_p
, 0);
281 return cbck (*addr_p
, nxt
, data
);
284 case VIEW_CONVERT_EXPR
:
287 nxt
= &TREE_OPERAND (*addr_p
, 0);
291 /* If the component has varying offset, it behaves like index
293 idx
= &TREE_OPERAND (*addr_p
, 2);
295 && !cbck (*addr_p
, idx
, data
))
298 nxt
= &TREE_OPERAND (*addr_p
, 0);
302 case ARRAY_RANGE_REF
:
303 nxt
= &TREE_OPERAND (*addr_p
, 0);
304 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
321 gcc_assert (is_gimple_min_invariant (*addr_p
));
325 idx
= &TMR_BASE (*addr_p
);
327 && !cbck (*addr_p
, idx
, data
))
329 idx
= &TMR_INDEX (*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_get_lhs (stmt
) == NULL_TREE
)
363 return MOVE_IMPOSSIBLE
;
365 if (gimple_vdef (stmt
))
366 return MOVE_IMPOSSIBLE
;
368 if (stmt_ends_bb_p (stmt
)
369 || gimple_has_volatile_ops (stmt
)
370 || gimple_has_side_effects (stmt
)
371 || stmt_could_throw_p (stmt
))
372 return MOVE_IMPOSSIBLE
;
374 if (is_gimple_call (stmt
))
376 /* While pure or const call is guaranteed to have no side effects, we
377 cannot move it arbitrarily. Consider code like
379 char *s = something ();
389 Here the strlen call cannot be moved out of the loop, even though
390 s is invariant. In addition to possibly creating a call with
391 invalid arguments, moving out a function call that is not executed
392 may cause performance regressions in case the call is costly and
393 not executed at all. */
394 ret
= MOVE_PRESERVE_EXECUTION
;
395 lhs
= gimple_call_lhs (stmt
);
397 else if (is_gimple_assign (stmt
))
398 lhs
= gimple_assign_lhs (stmt
);
400 return MOVE_IMPOSSIBLE
;
402 if (TREE_CODE (lhs
) == SSA_NAME
403 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
404 return MOVE_IMPOSSIBLE
;
406 if (TREE_CODE (lhs
) != SSA_NAME
407 || gimple_could_trap_p (stmt
))
408 return MOVE_PRESERVE_EXECUTION
;
413 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
414 loop to that we could move the expression using DEF if it did not have
415 other operands, i.e. the outermost loop enclosing LOOP in that the value
416 of DEF is invariant. */
419 outermost_invariant_loop (tree def
, struct loop
*loop
)
423 struct loop
*max_loop
;
424 struct lim_aux_data
*lim_data
;
427 return superloop_at_depth (loop
, 1);
429 if (TREE_CODE (def
) != SSA_NAME
)
431 gcc_assert (is_gimple_min_invariant (def
));
432 return superloop_at_depth (loop
, 1);
435 def_stmt
= SSA_NAME_DEF_STMT (def
);
436 def_bb
= gimple_bb (def_stmt
);
438 return superloop_at_depth (loop
, 1);
440 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
442 lim_data
= get_lim_data (def_stmt
);
443 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
444 max_loop
= find_common_loop (max_loop
,
445 loop_outer (lim_data
->max_loop
));
446 if (max_loop
== loop
)
448 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
453 /* DATA is a structure containing information associated with a statement
454 inside LOOP. DEF is one of the operands of this statement.
456 Find the outermost loop enclosing LOOP in that value of DEF is invariant
457 and record this in DATA->max_loop field. If DEF itself is defined inside
458 this loop as well (i.e. we need to hoist it out of the loop if we want
459 to hoist the statement represented by DATA), record the statement in that
460 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
461 add the cost of the computation of DEF to the DATA->cost.
463 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
466 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
469 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
470 basic_block def_bb
= gimple_bb (def_stmt
);
471 struct loop
*max_loop
;
473 struct lim_aux_data
*def_data
;
478 max_loop
= outermost_invariant_loop (def
, loop
);
482 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
483 data
->max_loop
= max_loop
;
485 def_data
= get_lim_data (def_stmt
);
490 /* Only add the cost if the statement defining DEF is inside LOOP,
491 i.e. if it is likely that by moving the invariants dependent
492 on it, we will be able to avoid creating a new register for
493 it (since it will be only used in these dependent invariants). */
494 && def_bb
->loop_father
== loop
)
495 data
->cost
+= def_data
->cost
;
497 dep
= XNEW (struct depend
);
498 dep
->stmt
= def_stmt
;
499 dep
->next
= data
->depends
;
505 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
506 are just ad-hoc constants. The estimates should be based on target-specific
510 stmt_cost (gimple stmt
)
515 /* Always try to create possibilities for unswitching. */
516 if (gimple_code (stmt
) == GIMPLE_COND
)
517 return LIM_EXPENSIVE
;
519 /* Hoisting memory references out should almost surely be a win. */
520 if (gimple_references_memory_p (stmt
))
523 if (is_gimple_call (stmt
))
525 /* We should be hoisting calls if possible. */
527 /* Unless the call is a builtin_constant_p; this always folds to a
528 constant, so moving it is useless. */
529 fndecl
= gimple_call_fndecl (stmt
);
531 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
532 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
538 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
541 switch (gimple_assign_rhs_code (stmt
))
554 /* Division and multiplication are usually expensive. */
570 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
571 REF is independent. If REF is not independent in LOOP, NULL is returned
575 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
579 if (bitmap_bit_p (ref
->stored
, loop
->num
))
584 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
585 if (!bitmap_bit_p (ref
->stored
, aloop
->num
)
586 && ref_indep_loop_p (aloop
, ref
))
589 if (ref_indep_loop_p (loop
, ref
))
595 /* If there is a simple load or store to a memory reference in STMT, returns
596 the location of the memory reference, and sets IS_STORE according to whether
597 it is a store or load. Otherwise, returns NULL. */
600 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
605 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
606 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
609 code
= gimple_assign_rhs_code (stmt
);
611 lhs
= gimple_assign_lhs_ptr (stmt
);
613 if (TREE_CODE (*lhs
) == SSA_NAME
)
615 if (get_gimple_rhs_class (code
) != GIMPLE_SINGLE_RHS
616 || !is_gimple_addressable (gimple_assign_rhs1 (stmt
)))
620 return gimple_assign_rhs1_ptr (stmt
);
622 else if (code
== SSA_NAME
623 || (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
624 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
633 /* Returns the memory reference contained in STMT. */
636 mem_ref_in_stmt (gimple stmt
)
639 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
647 hash
= iterative_hash_expr (*mem
, 0);
648 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
650 gcc_assert (ref
!= NULL
);
654 /* Determine the outermost loop to that it is possible to hoist a statement
655 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
656 the outermost loop in that the value computed by STMT is invariant.
657 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
658 we preserve the fact whether STMT is executed. It also fills other related
659 information to LIM_DATA (STMT).
661 The function returns false if STMT cannot be hoisted outside of the loop it
662 is defined in, and true otherwise. */
665 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
667 basic_block bb
= gimple_bb (stmt
);
668 struct loop
*loop
= bb
->loop_father
;
670 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
674 if (must_preserve_exec
)
675 level
= ALWAYS_EXECUTED_IN (bb
);
677 level
= superloop_at_depth (loop
, 1);
678 lim_data
->max_loop
= level
;
680 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
681 if (!add_dependency (val
, lim_data
, loop
, true))
684 if (gimple_vuse (stmt
))
686 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
691 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
692 if (!lim_data
->max_loop
)
697 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
699 if (!add_dependency (val
, lim_data
, loop
, false))
705 lim_data
->cost
+= stmt_cost (stmt
);
710 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
711 and that one of the operands of this statement is computed by STMT.
712 Ensure that STMT (together with all the statements that define its
713 operands) is hoisted at least out of the loop LEVEL. */
716 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
718 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
720 struct lim_aux_data
*lim_data
;
722 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
723 lim_data
= get_lim_data (stmt
);
724 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
725 stmt_loop
= find_common_loop (stmt_loop
,
726 loop_outer (lim_data
->tgt_loop
));
727 if (flow_loop_nested_p (stmt_loop
, level
))
730 gcc_assert (level
== lim_data
->max_loop
731 || flow_loop_nested_p (lim_data
->max_loop
, level
));
733 lim_data
->tgt_loop
= level
;
734 for (dep
= lim_data
->depends
; dep
; dep
= dep
->next
)
735 set_level (dep
->stmt
, orig_loop
, level
);
738 /* Determines an outermost loop from that we want to hoist the statement STMT.
739 For now we chose the outermost possible loop. TODO -- use profiling
740 information to set it more sanely. */
743 set_profitable_level (gimple stmt
)
745 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
748 /* Returns true if STMT is a call that has side effects. */
751 nonpure_call_p (gimple stmt
)
753 if (gimple_code (stmt
) != GIMPLE_CALL
)
756 return gimple_has_side_effects (stmt
);
759 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
762 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
764 gimple stmt
, stmt1
, stmt2
;
765 tree var
, name
, lhs
, type
;
768 stmt
= gsi_stmt (*bsi
);
769 lhs
= gimple_assign_lhs (stmt
);
770 type
= TREE_TYPE (lhs
);
772 var
= create_tmp_var (type
, "reciptmp");
773 add_referenced_var (var
);
774 DECL_GIMPLE_REG_P (var
) = 1;
776 /* For vectors, create a VECTOR_CST full of 1's. */
777 if (TREE_CODE (type
) == VECTOR_TYPE
)
780 tree list
= NULL_TREE
;
781 real_one
= build_real (TREE_TYPE (type
), dconst1
);
782 len
= TYPE_VECTOR_SUBPARTS (type
);
783 for (i
= 0; i
< len
; i
++)
784 list
= tree_cons (NULL
, real_one
, list
);
785 real_one
= build_vector (type
, list
);
788 real_one
= build_real (type
, dconst1
);
790 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
,
791 var
, real_one
, gimple_assign_rhs2 (stmt
));
792 name
= make_ssa_name (var
, stmt1
);
793 gimple_assign_set_lhs (stmt1
, name
);
795 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
796 gimple_assign_rhs1 (stmt
));
798 /* Replace division stmt with reciprocal and multiply stmts.
799 The multiply stmt is not invariant, so update iterator
800 and avoid rescanning. */
801 gsi_replace (bsi
, stmt1
, true);
802 gsi_insert_after (bsi
, stmt2
, GSI_NEW_STMT
);
804 /* Continue processing with invariant reciprocal statement. */
808 /* Check if the pattern at *BSI is a bittest of the form
809 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
812 rewrite_bittest (gimple_stmt_iterator
*bsi
)
814 gimple stmt
, use_stmt
, stmt1
, stmt2
;
815 tree lhs
, var
, name
, t
, a
, b
;
818 stmt
= gsi_stmt (*bsi
);
819 lhs
= gimple_assign_lhs (stmt
);
821 /* Verify that the single use of lhs is a comparison against zero. */
822 if (TREE_CODE (lhs
) != SSA_NAME
823 || !single_imm_use (lhs
, &use
, &use_stmt
)
824 || gimple_code (use_stmt
) != GIMPLE_COND
)
826 if (gimple_cond_lhs (use_stmt
) != lhs
827 || (gimple_cond_code (use_stmt
) != NE_EXPR
828 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
829 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
832 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
833 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
834 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
837 /* There is a conversion in between possibly inserted by fold. */
838 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
840 t
= gimple_assign_rhs1 (stmt1
);
841 if (TREE_CODE (t
) != SSA_NAME
842 || !has_single_use (t
))
844 stmt1
= SSA_NAME_DEF_STMT (t
);
845 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
849 /* Verify that B is loop invariant but A is not. Verify that with
850 all the stmt walking we are still in the same loop. */
851 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
852 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
855 a
= gimple_assign_rhs1 (stmt1
);
856 b
= gimple_assign_rhs2 (stmt1
);
858 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
859 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
862 var
= create_tmp_var (TREE_TYPE (a
), "shifttmp");
863 add_referenced_var (var
);
864 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
865 build_int_cst (TREE_TYPE (a
), 1), b
);
866 stmt1
= gimple_build_assign (var
, t
);
867 name
= make_ssa_name (var
, stmt1
);
868 gimple_assign_set_lhs (stmt1
, name
);
871 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
872 stmt2
= gimple_build_assign (var
, t
);
873 name
= make_ssa_name (var
, stmt2
);
874 gimple_assign_set_lhs (stmt2
, name
);
876 /* Replace the SSA_NAME we compare against zero. Adjust
877 the type of zero accordingly. */
879 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
881 gsi_insert_before (bsi
, stmt1
, GSI_SAME_STMT
);
882 propagate_defs_into_debug_stmts (gsi_stmt (*bsi
), NULL
, NULL
);
883 gsi_replace (bsi
, stmt2
, true);
892 /* Determine the outermost loops in that statements in basic block BB are
893 invariant, and record them to the LIM_DATA associated with the statements.
894 Callback for walk_dominator_tree. */
897 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
901 gimple_stmt_iterator bsi
;
903 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
904 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
905 struct lim_aux_data
*lim_data
;
907 if (!loop_outer (bb
->loop_father
))
910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
911 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
912 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
914 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
916 stmt
= gsi_stmt (bsi
);
918 pos
= movement_possibility (stmt
);
919 if (pos
== MOVE_IMPOSSIBLE
)
921 if (nonpure_call_p (stmt
))
926 /* Make sure to note always_executed_in for stores to make
927 store-motion work. */
928 else if (stmt_makes_single_store (stmt
))
930 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
931 lim_data
->always_executed_in
= outermost
;
936 if (is_gimple_assign (stmt
)
937 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
938 == GIMPLE_BINARY_RHS
))
940 tree op0
= gimple_assign_rhs1 (stmt
);
941 tree op1
= gimple_assign_rhs2 (stmt
);
942 struct loop
*ol1
= outermost_invariant_loop (op1
,
943 loop_containing_stmt (stmt
));
945 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
946 to be hoisted out of loop, saving expensive divide. */
947 if (pos
== MOVE_POSSIBLE
948 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
949 && flag_unsafe_math_optimizations
950 && !flag_trapping_math
952 && outermost_invariant_loop (op0
, ol1
) == NULL
)
953 stmt
= rewrite_reciprocal (&bsi
);
955 /* If the shift count is invariant, convert (A >> B) & 1 to
956 A & (1 << B) allowing the bit mask to be hoisted out of the loop
957 saving an expensive shift. */
958 if (pos
== MOVE_POSSIBLE
959 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
960 && integer_onep (op1
)
961 && TREE_CODE (op0
) == SSA_NAME
962 && has_single_use (op0
))
963 stmt
= rewrite_bittest (&bsi
);
966 lim_data
= init_lim_data (stmt
);
967 lim_data
->always_executed_in
= outermost
;
969 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
972 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
974 lim_data
->max_loop
= NULL
;
978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
980 print_gimple_stmt (dump_file
, stmt
, 2, 0);
981 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
982 loop_depth (lim_data
->max_loop
),
986 if (lim_data
->cost
>= LIM_EXPENSIVE
)
987 set_profitable_level (stmt
);
991 /* For each statement determines the outermost loop in that it is invariant,
992 statements on whose motion it depends and the cost of the computation.
993 This information is stored to the LIM_DATA structure associated with
997 determine_invariantness (void)
999 struct dom_walk_data walk_data
;
1001 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1002 walk_data
.dom_direction
= CDI_DOMINATORS
;
1003 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1005 init_walk_dominator_tree (&walk_data
);
1006 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1007 fini_walk_dominator_tree (&walk_data
);
1010 /* Hoist the statements in basic block BB out of the loops prescribed by
1011 data stored in LIM_DATA structures associated with each statement. Callback
1012 for walk_dominator_tree. */
1015 move_computations_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1019 gimple_stmt_iterator bsi
;
1022 struct lim_aux_data
*lim_data
;
1024 if (!loop_outer (bb
->loop_father
))
1027 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1029 stmt
= gsi_stmt (bsi
);
1031 lim_data
= get_lim_data (stmt
);
1032 if (lim_data
== NULL
)
1038 cost
= lim_data
->cost
;
1039 level
= lim_data
->tgt_loop
;
1040 clear_lim_data (stmt
);
1048 /* We do not really want to move conditionals out of the loop; we just
1049 placed it here to force its operands to be moved if necessary. */
1050 if (gimple_code (stmt
) == GIMPLE_COND
)
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1055 fprintf (dump_file
, "Moving statement\n");
1056 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1057 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1061 mark_virtual_ops_for_renaming (stmt
);
1062 gsi_insert_on_edge (loop_preheader_edge (level
), stmt
);
1063 propagate_defs_into_debug_stmts (gsi_stmt (bsi
), NULL
, NULL
);
1064 gsi_remove (&bsi
, false);
1068 /* Hoist the statements out of the loops prescribed by data stored in
1069 LIM_DATA structures associated with each statement.*/
1072 move_computations (void)
1074 struct dom_walk_data walk_data
;
1076 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1077 walk_data
.dom_direction
= CDI_DOMINATORS
;
1078 walk_data
.before_dom_children
= move_computations_stmt
;
1080 init_walk_dominator_tree (&walk_data
);
1081 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1082 fini_walk_dominator_tree (&walk_data
);
1084 gsi_commit_edge_inserts ();
1085 if (need_ssa_update_p (cfun
))
1086 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1089 /* Checks whether the statement defining variable *INDEX can be hoisted
1090 out of the loop passed in DATA. Callback for for_each_index. */
1093 may_move_till (tree ref
, tree
*index
, void *data
)
1095 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1097 /* If REF is an array reference, check also that the step and the lower
1098 bound is invariant in LOOP. */
1099 if (TREE_CODE (ref
) == ARRAY_REF
)
1101 tree step
= TREE_OPERAND (ref
, 3);
1102 tree lbound
= TREE_OPERAND (ref
, 2);
1104 max_loop
= outermost_invariant_loop (step
, loop
);
1108 max_loop
= outermost_invariant_loop (lbound
, loop
);
1113 max_loop
= outermost_invariant_loop (*index
, loop
);
1120 /* If OP is SSA NAME, force the statement that defines it to be
1121 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1124 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1129 || is_gimple_min_invariant (op
))
1132 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1134 stmt
= SSA_NAME_DEF_STMT (op
);
1135 if (gimple_nop_p (stmt
))
1138 set_level (stmt
, orig_loop
, loop
);
1141 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1142 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1148 struct loop
*orig_loop
;
1152 force_move_till (tree ref
, tree
*index
, void *data
)
1154 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1156 if (TREE_CODE (ref
) == ARRAY_REF
)
1158 tree step
= TREE_OPERAND (ref
, 3);
1159 tree lbound
= TREE_OPERAND (ref
, 2);
1161 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1162 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1165 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1170 /* A hash function for struct mem_ref object OBJ. */
1173 memref_hash (const void *obj
)
1175 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1180 /* An equality function for struct mem_ref object OBJ1 with
1181 memory reference OBJ2. */
1184 memref_eq (const void *obj1
, const void *obj2
)
1186 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1188 return operand_equal_p (mem1
->mem
, (const_tree
) obj2
, 0);
1191 /* Releases list of memory reference locations ACCS. */
1194 free_mem_ref_locs (mem_ref_locs_p accs
)
1202 for (i
= 0; VEC_iterate (mem_ref_loc_p
, accs
->locs
, i
, loc
); i
++)
1204 VEC_free (mem_ref_loc_p
, heap
, accs
->locs
);
1208 /* A function to free the mem_ref object OBJ. */
1211 memref_free (void *obj
)
1213 struct mem_ref
*const mem
= (struct mem_ref
*) obj
;
1215 mem_ref_locs_p accs
;
1217 BITMAP_FREE (mem
->stored
);
1218 BITMAP_FREE (mem
->indep_loop
);
1219 BITMAP_FREE (mem
->dep_loop
);
1220 BITMAP_FREE (mem
->indep_ref
);
1221 BITMAP_FREE (mem
->dep_ref
);
1223 for (i
= 0; VEC_iterate (mem_ref_locs_p
, mem
->accesses_in_loop
, i
, accs
); i
++)
1224 free_mem_ref_locs (accs
);
1225 VEC_free (mem_ref_locs_p
, heap
, mem
->accesses_in_loop
);
1227 BITMAP_FREE (mem
->vops
);
1231 /* Allocates and returns a memory reference description for MEM whose hash
1232 value is HASH and id is ID. */
1235 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1237 mem_ref_p ref
= XNEW (struct mem_ref
);
1241 ref
->stored
= BITMAP_ALLOC (NULL
);
1242 ref
->indep_loop
= BITMAP_ALLOC (NULL
);
1243 ref
->dep_loop
= BITMAP_ALLOC (NULL
);
1244 ref
->indep_ref
= BITMAP_ALLOC (NULL
);
1245 ref
->dep_ref
= BITMAP_ALLOC (NULL
);
1246 ref
->accesses_in_loop
= NULL
;
1247 ref
->vops
= BITMAP_ALLOC (NULL
);
1252 /* Allocates and returns the new list of locations. */
1254 static mem_ref_locs_p
1255 mem_ref_locs_alloc (void)
1257 mem_ref_locs_p accs
= XNEW (struct mem_ref_locs
);
1262 /* Records memory reference location *LOC in LOOP to the memory reference
1263 description REF. The reference occurs in statement STMT. */
1266 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1268 mem_ref_loc_p aref
= XNEW (struct mem_ref_loc
);
1269 mem_ref_locs_p accs
;
1270 bitmap ril
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1272 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1273 <= (unsigned) loop
->num
)
1274 VEC_safe_grow_cleared (mem_ref_locs_p
, heap
, ref
->accesses_in_loop
,
1276 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1279 accs
= mem_ref_locs_alloc ();
1280 VEC_replace (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
, accs
);
1286 VEC_safe_push (mem_ref_loc_p
, heap
, accs
->locs
, aref
);
1287 bitmap_set_bit (ril
, ref
->id
);
1290 /* Marks reference REF as stored in LOOP. */
1293 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1296 loop
!= current_loops
->tree_root
1297 && !bitmap_bit_p (ref
->stored
, loop
->num
);
1298 loop
= loop_outer (loop
))
1299 bitmap_set_bit (ref
->stored
, loop
->num
);
1302 /* Gathers memory references in statement STMT in LOOP, storing the
1303 information about them in the memory_accesses structure. Marks
1304 the vops accessed through unrecognized statements there as
1308 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1319 if (!gimple_vuse (stmt
))
1322 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1326 hash
= iterative_hash_expr (*mem
, 0);
1327 slot
= htab_find_slot_with_hash (memory_accesses
.refs
, *mem
, hash
, INSERT
);
1331 ref
= (mem_ref_p
) *slot
;
1336 id
= VEC_length (mem_ref_p
, memory_accesses
.refs_list
);
1337 ref
= mem_ref_alloc (*mem
, hash
, id
);
1338 VEC_safe_push (mem_ref_p
, heap
, memory_accesses
.refs_list
, ref
);
1341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1343 fprintf (dump_file
, "Memory reference %u: ", id
);
1344 print_generic_expr (dump_file
, ref
->mem
, TDF_SLIM
);
1345 fprintf (dump_file
, "\n");
1349 mark_ref_stored (ref
, loop
);
1351 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1352 bitmap_set_bit (ref
->vops
, DECL_UID (SSA_NAME_VAR (vname
)));
1353 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1357 clvops
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1358 if ((vname
= gimple_vuse (stmt
)) != NULL_TREE
)
1359 bitmap_set_bit (clvops
, DECL_UID (SSA_NAME_VAR (vname
)));
1362 /* Gathers memory references in loops. */
1365 gather_mem_refs_in_loops (void)
1367 gimple_stmt_iterator bsi
;
1372 bitmap lrefs
, alrefs
, alrefso
;
1376 loop
= bb
->loop_father
;
1377 if (loop
== current_loops
->tree_root
)
1380 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1381 gather_mem_refs_stmt (loop
, gsi_stmt (bsi
));
1384 /* Propagate the information about clobbered vops and accessed memory
1385 references up the loop hierarchy. */
1386 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1388 lrefs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1389 alrefs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
, loop
->num
);
1390 bitmap_ior_into (alrefs
, lrefs
);
1392 if (loop_outer (loop
) == current_loops
->tree_root
)
1395 clvi
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1396 clvo
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1397 loop_outer (loop
)->num
);
1398 bitmap_ior_into (clvo
, clvi
);
1400 alrefso
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1401 loop_outer (loop
)->num
);
1402 bitmap_ior_into (alrefso
, alrefs
);
1406 /* Element of the hash table that maps vops to memory references. */
1408 struct vop_to_refs_elt
1410 /* DECL_UID of the vop. */
1413 /* List of the all references. */
1416 /* List of stored references. */
1420 /* A hash function for struct vop_to_refs_elt object OBJ. */
1423 vtoe_hash (const void *obj
)
1425 const struct vop_to_refs_elt
*const vtoe
=
1426 (const struct vop_to_refs_elt
*) obj
;
1431 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1432 uid of a vop OBJ2. */
1435 vtoe_eq (const void *obj1
, const void *obj2
)
1437 const struct vop_to_refs_elt
*const vtoe
=
1438 (const struct vop_to_refs_elt
*) obj1
;
1439 const unsigned *const uid
= (const unsigned *) obj2
;
1441 return vtoe
->uid
== *uid
;
1444 /* A function to free the struct vop_to_refs_elt object. */
1447 vtoe_free (void *obj
)
1449 struct vop_to_refs_elt
*const vtoe
=
1450 (struct vop_to_refs_elt
*) obj
;
1452 BITMAP_FREE (vtoe
->refs_all
);
1453 BITMAP_FREE (vtoe
->refs_stored
);
1457 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1458 if the reference REF is stored. */
1461 record_vop_access (htab_t vop_to_refs
, unsigned vop
, unsigned ref
, bool stored
)
1463 void **slot
= htab_find_slot_with_hash (vop_to_refs
, &vop
, vop
, INSERT
);
1464 struct vop_to_refs_elt
*vtoe
;
1468 vtoe
= XNEW (struct vop_to_refs_elt
);
1470 vtoe
->refs_all
= BITMAP_ALLOC (NULL
);
1471 vtoe
->refs_stored
= BITMAP_ALLOC (NULL
);
1475 vtoe
= (struct vop_to_refs_elt
*) *slot
;
1477 bitmap_set_bit (vtoe
->refs_all
, ref
);
1479 bitmap_set_bit (vtoe
->refs_stored
, ref
);
1482 /* Returns the set of references that access VOP according to the table
1486 get_vop_accesses (htab_t vop_to_refs
, unsigned vop
)
1488 struct vop_to_refs_elt
*const vtoe
=
1489 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1490 return vtoe
->refs_all
;
1493 /* Returns the set of stores that access VOP according to the table
1497 get_vop_stores (htab_t vop_to_refs
, unsigned vop
)
1499 struct vop_to_refs_elt
*const vtoe
=
1500 (struct vop_to_refs_elt
*) htab_find_with_hash (vop_to_refs
, &vop
, vop
);
1501 return vtoe
->refs_stored
;
1504 /* Adds REF to mapping from virtual operands to references in LOOP. */
1507 add_vop_ref_mapping (struct loop
*loop
, mem_ref_p ref
)
1509 htab_t map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
1510 bool stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
1511 bitmap clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
,
1516 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, vop
, bi
)
1518 record_vop_access (map
, vop
, ref
->id
, stored
);
1522 /* Create a mapping from virtual operands to references that touch them
1526 create_vop_ref_mapping_loop (struct loop
*loop
)
1528 bitmap refs
= VEC_index (bitmap
, memory_accesses
.refs_in_loop
, loop
->num
);
1534 EXECUTE_IF_SET_IN_BITMAP (refs
, 0, i
, bi
)
1536 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1537 for (sloop
= loop
; sloop
!= current_loops
->tree_root
; sloop
= loop_outer (sloop
))
1538 add_vop_ref_mapping (sloop
, ref
);
1542 /* For each non-clobbered virtual operand and each loop, record the memory
1543 references in this loop that touch the operand. */
1546 create_vop_ref_mapping (void)
1551 FOR_EACH_LOOP (li
, loop
, 0)
1553 create_vop_ref_mapping_loop (loop
);
1557 /* Gathers information about memory accesses in the loops. */
1560 analyze_memory_references (void)
1566 memory_accesses
.refs
1567 = htab_create (100, memref_hash
, memref_eq
, memref_free
);
1568 memory_accesses
.refs_list
= NULL
;
1569 memory_accesses
.refs_in_loop
= VEC_alloc (bitmap
, heap
,
1570 number_of_loops ());
1571 memory_accesses
.all_refs_in_loop
= VEC_alloc (bitmap
, heap
,
1572 number_of_loops ());
1573 memory_accesses
.clobbered_vops
= VEC_alloc (bitmap
, heap
,
1574 number_of_loops ());
1575 memory_accesses
.vop_ref_map
= VEC_alloc (htab_t
, heap
,
1576 number_of_loops ());
1578 for (i
= 0; i
< number_of_loops (); i
++)
1580 empty
= BITMAP_ALLOC (NULL
);
1581 VEC_quick_push (bitmap
, memory_accesses
.refs_in_loop
, empty
);
1582 empty
= BITMAP_ALLOC (NULL
);
1583 VEC_quick_push (bitmap
, memory_accesses
.all_refs_in_loop
, empty
);
1584 empty
= BITMAP_ALLOC (NULL
);
1585 VEC_quick_push (bitmap
, memory_accesses
.clobbered_vops
, empty
);
1586 hempty
= htab_create (10, vtoe_hash
, vtoe_eq
, vtoe_free
);
1587 VEC_quick_push (htab_t
, memory_accesses
.vop_ref_map
, hempty
);
1590 memory_accesses
.ttae_cache
= NULL
;
1592 gather_mem_refs_in_loops ();
1593 create_vop_ref_mapping ();
1596 /* Returns true if a region of size SIZE1 at position 0 and a region of
1597 size SIZE2 at position DIFF cannot overlap. */
1600 cannot_overlap_p (aff_tree
*diff
, double_int size1
, double_int size2
)
1602 double_int d
, bound
;
1604 /* Unless the difference is a constant, we fail. */
1609 if (double_int_negative_p (d
))
1611 /* The second object is before the first one, we succeed if the last
1612 element of the second object is before the start of the first one. */
1613 bound
= double_int_add (d
, double_int_add (size2
, double_int_minus_one
));
1614 return double_int_negative_p (bound
);
1618 /* We succeed if the second object starts after the first one ends. */
1619 return double_int_scmp (size1
, d
) <= 0;
1623 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1624 tree_to_aff_combination_expand. */
1627 mem_refs_may_alias_p (tree mem1
, tree mem2
, struct pointer_map_t
**ttae_cache
)
1629 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1630 object and their offset differ in such a way that the locations cannot
1631 overlap, then they cannot alias. */
1632 double_int size1
, size2
;
1633 aff_tree off1
, off2
;
1635 /* Perform basic offset and type-based disambiguation. */
1636 if (!refs_may_alias_p (mem1
, mem2
))
1639 /* The expansion of addresses may be a bit expensive, thus we only do
1640 the check at -O2 and higher optimization levels. */
1644 get_inner_reference_aff (mem1
, &off1
, &size1
);
1645 get_inner_reference_aff (mem2
, &off2
, &size2
);
1646 aff_combination_expand (&off1
, ttae_cache
);
1647 aff_combination_expand (&off2
, ttae_cache
);
1648 aff_combination_scale (&off1
, double_int_minus_one
);
1649 aff_combination_add (&off2
, &off1
);
1651 if (cannot_overlap_p (&off2
, size1
, size2
))
1657 /* Rewrites location LOC by TMP_VAR. */
1660 rewrite_mem_ref_loc (mem_ref_loc_p loc
, tree tmp_var
)
1662 mark_virtual_ops_for_renaming (loc
->stmt
);
1663 *loc
->ref
= tmp_var
;
1664 update_stmt (loc
->stmt
);
1667 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1670 get_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
,
1671 VEC (mem_ref_loc_p
, heap
) **locs
)
1673 mem_ref_locs_p accs
;
1676 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
1678 struct loop
*subloop
;
1680 if (!bitmap_bit_p (refs
, ref
->id
))
1683 if (VEC_length (mem_ref_locs_p
, ref
->accesses_in_loop
)
1684 > (unsigned) loop
->num
)
1686 accs
= VEC_index (mem_ref_locs_p
, ref
->accesses_in_loop
, loop
->num
);
1689 for (i
= 0; VEC_iterate (mem_ref_loc_p
, accs
->locs
, i
, loc
); i
++)
1690 VEC_safe_push (mem_ref_loc_p
, heap
, *locs
, loc
);
1694 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1695 get_all_locs_in_loop (subloop
, ref
, locs
);
1698 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1701 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1705 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1707 get_all_locs_in_loop (loop
, ref
, &locs
);
1708 for (i
= 0; VEC_iterate (mem_ref_loc_p
, locs
, i
, loc
); i
++)
1709 rewrite_mem_ref_loc (loc
, tmp_var
);
1710 VEC_free (mem_ref_loc_p
, heap
, locs
);
1713 /* The name and the length of the currently generated variable
1715 #define MAX_LSM_NAME_LENGTH 40
1716 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1717 static int lsm_tmp_name_length
;
1719 /* Adds S to lsm_tmp_name. */
1722 lsm_tmp_name_add (const char *s
)
1724 int l
= strlen (s
) + lsm_tmp_name_length
;
1725 if (l
> MAX_LSM_NAME_LENGTH
)
1728 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1729 lsm_tmp_name_length
= l
;
1732 /* Stores the name for temporary variable that replaces REF to
1736 gen_lsm_tmp_name (tree ref
)
1740 switch (TREE_CODE (ref
))
1742 case MISALIGNED_INDIRECT_REF
:
1743 case ALIGN_INDIRECT_REF
:
1745 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1746 lsm_tmp_name_add ("_");
1750 case VIEW_CONVERT_EXPR
:
1751 case ARRAY_RANGE_REF
:
1752 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1756 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1757 lsm_tmp_name_add ("_RE");
1761 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1762 lsm_tmp_name_add ("_IM");
1766 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1767 lsm_tmp_name_add ("_");
1768 name
= get_name (TREE_OPERAND (ref
, 1));
1771 lsm_tmp_name_add ("_");
1772 lsm_tmp_name_add (name
);
1775 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1776 lsm_tmp_name_add ("_I");
1780 ref
= SSA_NAME_VAR (ref
);
1785 name
= get_name (ref
);
1788 lsm_tmp_name_add (name
);
1792 lsm_tmp_name_add ("S");
1796 lsm_tmp_name_add ("R");
1808 /* Determines name for temporary variable that replaces REF.
1809 The name is accumulated into the lsm_tmp_name variable.
1810 N is added to the name of the temporary. */
1813 get_lsm_tmp_name (tree ref
, unsigned n
)
1817 lsm_tmp_name_length
= 0;
1818 gen_lsm_tmp_name (ref
);
1819 lsm_tmp_name_add ("_lsm");
1824 lsm_tmp_name_add (ns
);
1826 return lsm_tmp_name
;
1829 /* Executes store motion of memory reference REF from LOOP.
1830 Exits from the LOOP are stored in EXITS. The initialization of the
1831 temporary variable is put to the preheader of the loop, and assignments
1832 to the reference from the temporary variable are emitted to exits. */
1835 execute_sm (struct loop
*loop
, VEC (edge
, heap
) *exits
, mem_ref_p ref
)
1840 struct fmt_data fmt_data
;
1842 struct lim_aux_data
*lim_data
;
1844 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1846 fprintf (dump_file
, "Executing store motion of ");
1847 print_generic_expr (dump_file
, ref
->mem
, 0);
1848 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1851 tmp_var
= make_rename_temp (TREE_TYPE (ref
->mem
),
1852 get_lsm_tmp_name (ref
->mem
, ~0));
1854 fmt_data
.loop
= loop
;
1855 fmt_data
.orig_loop
= loop
;
1856 for_each_index (&ref
->mem
, force_move_till
, &fmt_data
);
1858 rewrite_mem_refs (loop
, ref
, tmp_var
);
1860 /* Emit the load & stores. */
1861 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
));
1862 lim_data
= init_lim_data (load
);
1863 lim_data
->max_loop
= loop
;
1864 lim_data
->tgt_loop
= loop
;
1866 /* Put this into the latch, so that we are sure it will be processed after
1867 all dependencies. */
1868 gsi_insert_on_edge (loop_latch_edge (loop
), load
);
1870 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1872 store
= gimple_build_assign (unshare_expr (ref
->mem
), tmp_var
);
1873 gsi_insert_on_edge (ex
, store
);
1877 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
1878 edges of the LOOP. */
1881 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
1882 VEC (edge
, heap
) *exits
)
1888 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
1890 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
1891 execute_sm (loop
, exits
, ref
);
1895 /* Returns true if REF is always accessed in LOOP. */
1898 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
)
1900 VEC (mem_ref_loc_p
, heap
) *locs
= NULL
;
1904 struct loop
*must_exec
;
1906 get_all_locs_in_loop (loop
, ref
, &locs
);
1907 for (i
= 0; VEC_iterate (mem_ref_loc_p
, locs
, i
, loc
); i
++)
1909 if (!get_lim_data (loc
->stmt
))
1912 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
1916 if (must_exec
== loop
1917 || flow_loop_nested_p (must_exec
, loop
))
1923 VEC_free (mem_ref_loc_p
, heap
, locs
);
1928 /* Returns true if REF1 and REF2 are independent. */
1931 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
1934 || bitmap_bit_p (ref1
->indep_ref
, ref2
->id
))
1936 if (bitmap_bit_p (ref1
->dep_ref
, ref2
->id
))
1939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1940 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
1941 ref1
->id
, ref2
->id
);
1943 if (mem_refs_may_alias_p (ref1
->mem
, ref2
->mem
,
1944 &memory_accesses
.ttae_cache
))
1946 bitmap_set_bit (ref1
->dep_ref
, ref2
->id
);
1947 bitmap_set_bit (ref2
->dep_ref
, ref1
->id
);
1948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1949 fprintf (dump_file
, "dependent.\n");
1954 bitmap_set_bit (ref1
->indep_ref
, ref2
->id
);
1955 bitmap_set_bit (ref2
->indep_ref
, ref1
->id
);
1956 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1957 fprintf (dump_file
, "independent.\n");
1962 /* Records the information whether REF is independent in LOOP (according
1966 record_indep_loop (struct loop
*loop
, mem_ref_p ref
, bool indep
)
1969 bitmap_set_bit (ref
->indep_loop
, loop
->num
);
1971 bitmap_set_bit (ref
->dep_loop
, loop
->num
);
1974 /* Returns true if REF is independent on all other memory references in
1978 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
)
1980 bitmap clobbers
, refs_to_check
, refs
;
1983 bool ret
= true, stored
= bitmap_bit_p (ref
->stored
, loop
->num
);
1987 /* If the reference is clobbered, it is not independent. */
1988 clobbers
= VEC_index (bitmap
, memory_accesses
.clobbered_vops
, loop
->num
);
1989 if (bitmap_intersect_p (ref
->vops
, clobbers
))
1992 refs_to_check
= BITMAP_ALLOC (NULL
);
1994 map
= VEC_index (htab_t
, memory_accesses
.vop_ref_map
, loop
->num
);
1995 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref
->vops
, clobbers
, 0, i
, bi
)
1998 refs
= get_vop_accesses (map
, i
);
2000 refs
= get_vop_stores (map
, i
);
2002 bitmap_ior_into (refs_to_check
, refs
);
2005 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2007 aref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2008 if (!refs_independent_p (ref
, aref
))
2011 record_indep_loop (loop
, aref
, false);
2016 BITMAP_FREE (refs_to_check
);
2020 /* Returns true if REF is independent on all other memory references in
2021 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2024 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2028 if (bitmap_bit_p (ref
->indep_loop
, loop
->num
))
2030 if (bitmap_bit_p (ref
->dep_loop
, loop
->num
))
2033 ret
= ref_indep_loop_p_1 (loop
, ref
);
2035 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2036 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2037 ref
->id
, loop
->num
, ret
? "independent" : "dependent");
2039 record_indep_loop (loop
, ref
, ret
);
2044 /* Returns true if we can perform store motion of REF from LOOP. */
2047 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2049 /* Unless the reference is stored in the loop, there is nothing to do. */
2050 if (!bitmap_bit_p (ref
->stored
, loop
->num
))
2053 /* It should be movable. */
2054 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
))
2055 || TREE_THIS_VOLATILE (ref
->mem
)
2056 || !for_each_index (&ref
->mem
, may_move_till
, loop
))
2059 /* If it can trap, it must be always executed in LOOP. */
2060 if (tree_could_trap_p (ref
->mem
)
2061 && !ref_always_accessed_p (loop
, ref
))
2064 /* And it must be independent on all other memory references
2066 if (!ref_indep_loop_p (loop
, ref
))
2072 /* Marks the references in LOOP for that store motion should be performed
2073 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2074 motion was performed in one of the outer loops. */
2077 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2079 bitmap refs
= VEC_index (bitmap
, memory_accesses
.all_refs_in_loop
,
2085 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2087 ref
= VEC_index (mem_ref_p
, memory_accesses
.refs_list
, i
);
2088 if (can_sm_ref_p (loop
, ref
))
2089 bitmap_set_bit (refs_to_sm
, i
);
2093 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2094 for a store motion optimization (i.e. whether we can insert statement
2098 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2099 VEC (edge
, heap
) *exits
)
2104 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2105 if (ex
->flags
& EDGE_ABNORMAL
)
2111 /* Try to perform store motion for all memory references modified inside
2112 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2113 store motion was executed in one of the outer loops. */
2116 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2118 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2119 struct loop
*subloop
;
2120 bitmap sm_in_loop
= BITMAP_ALLOC (NULL
);
2122 if (loop_suitable_for_sm (loop
, exits
))
2124 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2125 hoist_memory_references (loop
, sm_in_loop
, exits
);
2127 VEC_free (edge
, heap
, exits
);
2129 bitmap_ior_into (sm_executed
, sm_in_loop
);
2130 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2131 store_motion_loop (subloop
, sm_executed
);
2132 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2133 BITMAP_FREE (sm_in_loop
);
2136 /* Try to perform store motion for all memory references modified inside
2143 bitmap sm_executed
= BITMAP_ALLOC (NULL
);
2145 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2146 store_motion_loop (loop
, sm_executed
);
2148 BITMAP_FREE (sm_executed
);
2149 gsi_commit_edge_inserts ();
2152 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2153 for each such basic block bb records the outermost loop for that execution
2154 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2155 blocks that contain a nonpure call. */
2158 fill_always_executed_in (struct loop
*loop
, sbitmap contains_call
)
2160 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2163 struct loop
*inn_loop
= loop
;
2165 if (!loop
->header
->aux
)
2167 bbs
= get_loop_body_in_dom_order (loop
);
2169 for (i
= 0; i
< loop
->num_nodes
; i
++)
2174 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2177 if (TEST_BIT (contains_call
, bb
->index
))
2180 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2181 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2186 /* A loop might be infinite (TODO use simple loop analysis
2187 to disprove this if possible). */
2188 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2191 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2194 if (bb
->loop_father
->header
== bb
)
2196 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2199 /* In a loop that is always entered we may proceed anyway.
2200 But record that we entered it and stop once we leave it. */
2201 inn_loop
= bb
->loop_father
;
2208 if (last
== loop
->header
)
2210 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2216 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2217 fill_always_executed_in (loop
, contains_call
);
2220 /* Compute the global information needed by the loop invariant motion pass. */
2223 tree_ssa_lim_initialize (void)
2225 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2226 gimple_stmt_iterator bsi
;
2230 sbitmap_zero (contains_call
);
2233 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2235 if (nonpure_call_p (gsi_stmt (bsi
)))
2239 if (!gsi_end_p (bsi
))
2240 SET_BIT (contains_call
, bb
->index
);
2243 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2244 fill_always_executed_in (loop
, contains_call
);
2246 sbitmap_free (contains_call
);
2248 lim_aux_data_map
= pointer_map_create ();
2251 /* Cleans up after the invariant motion pass. */
2254 tree_ssa_lim_finalize (void)
2266 pointer_map_destroy (lim_aux_data_map
);
2268 VEC_free (mem_ref_p
, heap
, memory_accesses
.refs_list
);
2269 htab_delete (memory_accesses
.refs
);
2271 for (i
= 0; VEC_iterate (bitmap
, memory_accesses
.refs_in_loop
, i
, b
); i
++)
2273 VEC_free (bitmap
, heap
, memory_accesses
.refs_in_loop
);
2275 for (i
= 0; VEC_iterate (bitmap
, memory_accesses
.all_refs_in_loop
, i
, b
); i
++)
2277 VEC_free (bitmap
, heap
, memory_accesses
.all_refs_in_loop
);
2279 for (i
= 0; VEC_iterate (bitmap
, memory_accesses
.clobbered_vops
, i
, b
); i
++)
2281 VEC_free (bitmap
, heap
, memory_accesses
.clobbered_vops
);
2283 for (i
= 0; VEC_iterate (htab_t
, memory_accesses
.vop_ref_map
, i
, h
); i
++)
2285 VEC_free (htab_t
, heap
, memory_accesses
.vop_ref_map
);
2287 if (memory_accesses
.ttae_cache
)
2288 pointer_map_destroy (memory_accesses
.ttae_cache
);
2291 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2292 i.e. those that are likely to be win regardless of the register pressure. */
2297 tree_ssa_lim_initialize ();
2299 /* Gathers information about memory accesses in the loops. */
2300 analyze_memory_references ();
2302 /* For each statement determine the outermost loop in that it is
2303 invariant and cost for computing the invariant. */
2304 determine_invariantness ();
2306 /* Execute store motion. Force the necessary invariants to be moved
2307 out of the loops as well. */
2310 /* Move the expressions that are expensive enough. */
2311 move_computations ();
2313 tree_ssa_lim_finalize ();