1 /* Loop invariant motion.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "tree-flow.h"
32 #include "tree-pass.h"
35 #include "tree-affine.h"
36 #include "pointer-set.h"
37 #include "tree-ssa-propagate.h"
39 /* TODO: Support for predicated code motion. I.e.
50 Where COND and INV are invariants, but evaluating INV may trap or be
51 invalid from some other reason if !COND. This may be transformed to
61 /* The auxiliary data kept for each statement. */
65 struct loop
*max_loop
; /* The outermost loop in that the statement
68 struct loop
*tgt_loop
; /* The loop out of that we want to move the
71 struct loop
*always_executed_in
;
72 /* The outermost loop for that we are sure
73 the statement is executed if the loop
76 unsigned cost
; /* Cost of the computation performed by the
79 vec
<gimple
> depends
; /* Vector of statements that must be also
80 hoisted out of the loop when this statement
81 is hoisted; i.e. those that define the
82 operands of the statement and are inside of
86 /* Maps statements to their lim_aux_data. */
88 static struct pointer_map_t
*lim_aux_data_map
;
90 /* Description of a memory reference location. */
92 typedef struct mem_ref_loc
94 tree
*ref
; /* The reference itself. */
95 gimple stmt
; /* The statement in that it occurs. */
99 /* Description of a memory reference. */
101 typedef struct mem_ref
103 unsigned id
; /* ID assigned to the memory reference
104 (its index in memory_accesses.refs_list) */
105 hashval_t hash
; /* Its hash value. */
107 /* The memory access itself and associated caching of alias-oracle
111 bitmap_head stored
; /* The set of loops in that this memory location
113 vec
<vec
<mem_ref_loc
> > accesses_in_loop
;
114 /* The locations of the accesses. Vector
115 indexed by the loop number. */
117 /* The following sets are computed on demand. We keep both set and
118 its complement, so that we know whether the information was
119 already computed or not. */
120 bitmap_head indep_loop
; /* The set of loops in that the memory
121 reference is independent, meaning:
122 If it is stored in the loop, this store
123 is independent on all other loads and
125 If it is only loaded, then it is independent
126 on all stores in the loop. */
127 bitmap_head dep_loop
; /* The complement of INDEP_LOOP. */
130 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
131 to record (in)dependence against stores in the loop and its subloops, the
132 second to record (in)dependence against all references in the loop
134 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
138 /* Description of memory accesses in loops. */
142 /* The hash table of memory references accessed in loops. */
145 /* The list of memory references. */
146 vec
<mem_ref_p
> refs_list
;
148 /* The set of memory references accessed in each loop. */
149 vec
<bitmap_head
> refs_in_loop
;
151 /* The set of memory references stored in each loop. */
152 vec
<bitmap_head
> refs_stored_in_loop
;
154 /* The set of memory references stored in each loop, including subloops . */
155 vec
<bitmap_head
> all_refs_stored_in_loop
;
157 /* Cache for expanding memory addresses. */
158 struct pointer_map_t
*ttae_cache
;
161 /* Obstack for the bitmaps in the above data structures. */
162 static bitmap_obstack lim_bitmap_obstack
;
164 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
166 /* Minimum cost of an expensive expression. */
167 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
169 /* The outermost loop for which execution of the header guarantees that the
170 block will be executed. */
171 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
172 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
174 /* ID of the shared unanalyzable mem. */
175 #define UNANALYZABLE_MEM_ID 0
177 /* Whether the reference was analyzable. */
178 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
180 static struct lim_aux_data
*
181 init_lim_data (gimple stmt
)
183 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
185 *p
= XCNEW (struct lim_aux_data
);
186 return (struct lim_aux_data
*) *p
;
189 static struct lim_aux_data
*
190 get_lim_data (gimple stmt
)
192 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
196 return (struct lim_aux_data
*) *p
;
199 /* Releases the memory occupied by DATA. */
202 free_lim_aux_data (struct lim_aux_data
*data
)
204 data
->depends
.release();
209 clear_lim_data (gimple stmt
)
211 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
215 free_lim_aux_data ((struct lim_aux_data
*) *p
);
219 /* Calls CBCK for each index in memory reference ADDR_P. There are two
220 kinds situations handled; in each of these cases, the memory reference
221 and DATA are passed to the callback:
223 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
224 pass the pointer to the index to the callback.
226 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
227 pointer to addr to the callback.
229 If the callback returns false, the whole search stops and false is returned.
230 Otherwise the function returns true after traversing through the whole
231 reference *ADDR_P. */
234 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
238 for (; ; addr_p
= nxt
)
240 switch (TREE_CODE (*addr_p
))
243 return cbck (*addr_p
, addr_p
, data
);
246 nxt
= &TREE_OPERAND (*addr_p
, 0);
247 return cbck (*addr_p
, nxt
, data
);
250 case VIEW_CONVERT_EXPR
:
253 nxt
= &TREE_OPERAND (*addr_p
, 0);
257 /* If the component has varying offset, it behaves like index
259 idx
= &TREE_OPERAND (*addr_p
, 2);
261 && !cbck (*addr_p
, idx
, data
))
264 nxt
= &TREE_OPERAND (*addr_p
, 0);
268 case ARRAY_RANGE_REF
:
269 nxt
= &TREE_OPERAND (*addr_p
, 0);
270 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
288 gcc_assert (is_gimple_min_invariant (*addr_p
));
292 idx
= &TMR_BASE (*addr_p
);
294 && !cbck (*addr_p
, idx
, data
))
296 idx
= &TMR_INDEX (*addr_p
);
298 && !cbck (*addr_p
, idx
, data
))
300 idx
= &TMR_INDEX2 (*addr_p
);
302 && !cbck (*addr_p
, idx
, data
))
312 /* If it is possible to hoist the statement STMT unconditionally,
313 returns MOVE_POSSIBLE.
314 If it is possible to hoist the statement STMT, but we must avoid making
315 it executed if it would not be executed in the original program (e.g.
316 because it may trap), return MOVE_PRESERVE_EXECUTION.
317 Otherwise return MOVE_IMPOSSIBLE. */
320 movement_possibility (gimple stmt
)
323 enum move_pos ret
= MOVE_POSSIBLE
;
325 if (flag_unswitch_loops
326 && gimple_code (stmt
) == GIMPLE_COND
)
328 /* If we perform unswitching, force the operands of the invariant
329 condition to be moved out of the loop. */
330 return MOVE_POSSIBLE
;
333 if (gimple_code (stmt
) == GIMPLE_PHI
334 && gimple_phi_num_args (stmt
) <= 2
335 && !virtual_operand_p (gimple_phi_result (stmt
))
336 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
337 return MOVE_POSSIBLE
;
339 if (gimple_get_lhs (stmt
) == NULL_TREE
)
340 return MOVE_IMPOSSIBLE
;
342 if (gimple_vdef (stmt
))
343 return MOVE_IMPOSSIBLE
;
345 if (stmt_ends_bb_p (stmt
)
346 || gimple_has_volatile_ops (stmt
)
347 || gimple_has_side_effects (stmt
)
348 || stmt_could_throw_p (stmt
))
349 return MOVE_IMPOSSIBLE
;
351 if (is_gimple_call (stmt
))
353 /* While pure or const call is guaranteed to have no side effects, we
354 cannot move it arbitrarily. Consider code like
356 char *s = something ();
366 Here the strlen call cannot be moved out of the loop, even though
367 s is invariant. In addition to possibly creating a call with
368 invalid arguments, moving out a function call that is not executed
369 may cause performance regressions in case the call is costly and
370 not executed at all. */
371 ret
= MOVE_PRESERVE_EXECUTION
;
372 lhs
= gimple_call_lhs (stmt
);
374 else if (is_gimple_assign (stmt
))
375 lhs
= gimple_assign_lhs (stmt
);
377 return MOVE_IMPOSSIBLE
;
379 if (TREE_CODE (lhs
) == SSA_NAME
380 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
381 return MOVE_IMPOSSIBLE
;
383 if (TREE_CODE (lhs
) != SSA_NAME
384 || gimple_could_trap_p (stmt
))
385 return MOVE_PRESERVE_EXECUTION
;
387 /* Non local loads in a transaction cannot be hoisted out. Well,
388 unless the load happens on every path out of the loop, but we
389 don't take this into account yet. */
391 && gimple_in_transaction (stmt
)
392 && gimple_assign_single_p (stmt
))
394 tree rhs
= gimple_assign_rhs1 (stmt
);
395 if (DECL_P (rhs
) && is_global_var (rhs
))
399 fprintf (dump_file
, "Cannot hoist conditional load of ");
400 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
401 fprintf (dump_file
, " because it is in a transaction.\n");
403 return MOVE_IMPOSSIBLE
;
410 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
411 loop to that we could move the expression using DEF if it did not have
412 other operands, i.e. the outermost loop enclosing LOOP in that the value
413 of DEF is invariant. */
416 outermost_invariant_loop (tree def
, struct loop
*loop
)
420 struct loop
*max_loop
;
421 struct lim_aux_data
*lim_data
;
424 return superloop_at_depth (loop
, 1);
426 if (TREE_CODE (def
) != SSA_NAME
)
428 gcc_assert (is_gimple_min_invariant (def
));
429 return superloop_at_depth (loop
, 1);
432 def_stmt
= SSA_NAME_DEF_STMT (def
);
433 def_bb
= gimple_bb (def_stmt
);
435 return superloop_at_depth (loop
, 1);
437 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
439 lim_data
= get_lim_data (def_stmt
);
440 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
441 max_loop
= find_common_loop (max_loop
,
442 loop_outer (lim_data
->max_loop
));
443 if (max_loop
== loop
)
445 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
450 /* DATA is a structure containing information associated with a statement
451 inside LOOP. DEF is one of the operands of this statement.
453 Find the outermost loop enclosing LOOP in that value of DEF is invariant
454 and record this in DATA->max_loop field. If DEF itself is defined inside
455 this loop as well (i.e. we need to hoist it out of the loop if we want
456 to hoist the statement represented by DATA), record the statement in that
457 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
458 add the cost of the computation of DEF to the DATA->cost.
460 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
463 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
466 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
467 basic_block def_bb
= gimple_bb (def_stmt
);
468 struct loop
*max_loop
;
469 struct lim_aux_data
*def_data
;
474 max_loop
= outermost_invariant_loop (def
, loop
);
478 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
479 data
->max_loop
= max_loop
;
481 def_data
= get_lim_data (def_stmt
);
486 /* Only add the cost if the statement defining DEF is inside LOOP,
487 i.e. if it is likely that by moving the invariants dependent
488 on it, we will be able to avoid creating a new register for
489 it (since it will be only used in these dependent invariants). */
490 && def_bb
->loop_father
== loop
)
491 data
->cost
+= def_data
->cost
;
493 data
->depends
.safe_push (def_stmt
);
498 /* Returns an estimate for a cost of statement STMT. The values here
499 are just ad-hoc constants, similar to costs for inlining. */
502 stmt_cost (gimple stmt
)
504 /* Always try to create possibilities for unswitching. */
505 if (gimple_code (stmt
) == GIMPLE_COND
506 || gimple_code (stmt
) == GIMPLE_PHI
)
507 return LIM_EXPENSIVE
;
509 /* We should be hoisting calls if possible. */
510 if (is_gimple_call (stmt
))
514 /* Unless the call is a builtin_constant_p; this always folds to a
515 constant, so moving it is useless. */
516 fndecl
= gimple_call_fndecl (stmt
);
518 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
519 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
522 return LIM_EXPENSIVE
;
525 /* Hoisting memory references out should almost surely be a win. */
526 if (gimple_references_memory_p (stmt
))
527 return LIM_EXPENSIVE
;
529 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
532 switch (gimple_assign_rhs_code (stmt
))
535 case WIDEN_MULT_EXPR
:
536 case WIDEN_MULT_PLUS_EXPR
:
537 case WIDEN_MULT_MINUS_EXPR
:
550 /* Division and multiplication are usually expensive. */
551 return LIM_EXPENSIVE
;
555 case WIDEN_LSHIFT_EXPR
:
558 /* Shifts and rotates are usually expensive. */
559 return LIM_EXPENSIVE
;
562 /* Make vector construction cost proportional to the number
564 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
568 /* Whether or not something is wrapped inside a PAREN_EXPR
569 should not change move cost. Nor should an intermediate
570 unpropagated SSA name copy. */
578 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
579 REF is independent. If REF is not independent in LOOP, NULL is returned
583 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
587 if (bitmap_bit_p (&ref
->stored
, loop
->num
))
592 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
593 if (!bitmap_bit_p (&ref
->stored
, aloop
->num
)
594 && ref_indep_loop_p (aloop
, ref
))
597 if (ref_indep_loop_p (loop
, ref
))
603 /* If there is a simple load or store to a memory reference in STMT, returns
604 the location of the memory reference, and sets IS_STORE according to whether
605 it is a store or load. Otherwise, returns NULL. */
608 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
612 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
613 if (!gimple_assign_single_p (stmt
))
616 lhs
= gimple_assign_lhs_ptr (stmt
);
617 rhs
= gimple_assign_rhs1_ptr (stmt
);
619 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
624 else if (gimple_vdef (stmt
)
625 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
634 /* Returns the memory reference contained in STMT. */
637 mem_ref_in_stmt (gimple stmt
)
640 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
648 hash
= iterative_hash_expr (*mem
, 0);
649 ref
= (mem_ref_p
) htab_find_with_hash (memory_accesses
.refs
, *mem
, hash
);
651 gcc_assert (ref
!= NULL
);
655 /* From a controlling predicate in DOM determine the arguments from
656 the PHI node PHI that are chosen if the predicate evaluates to
657 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
658 they are non-NULL. Returns true if the arguments can be determined,
659 else return false. */
662 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
663 tree
*true_arg_p
, tree
*false_arg_p
)
665 basic_block bb
= gimple_bb (phi
);
666 edge true_edge
, false_edge
, tem
;
667 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
669 /* We have to verify that one edge into the PHI node is dominated
670 by the true edge of the predicate block and the other edge
671 dominated by the false edge. This ensures that the PHI argument
672 we are going to take is completely determined by the path we
673 take from the predicate block.
674 We can only use BB dominance checks below if the destination of
675 the true/false edges are dominated by their edge, thus only
676 have a single predecessor. */
677 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
678 tem
= EDGE_PRED (bb
, 0);
680 || (single_pred_p (true_edge
->dest
)
681 && (tem
->src
== true_edge
->dest
682 || dominated_by_p (CDI_DOMINATORS
,
683 tem
->src
, true_edge
->dest
))))
684 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
685 else if (tem
== false_edge
686 || (single_pred_p (false_edge
->dest
)
687 && (tem
->src
== false_edge
->dest
688 || dominated_by_p (CDI_DOMINATORS
,
689 tem
->src
, false_edge
->dest
))))
690 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
693 tem
= EDGE_PRED (bb
, 1);
695 || (single_pred_p (true_edge
->dest
)
696 && (tem
->src
== true_edge
->dest
697 || dominated_by_p (CDI_DOMINATORS
,
698 tem
->src
, true_edge
->dest
))))
699 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
700 else if (tem
== false_edge
701 || (single_pred_p (false_edge
->dest
)
702 && (tem
->src
== false_edge
->dest
703 || dominated_by_p (CDI_DOMINATORS
,
704 tem
->src
, false_edge
->dest
))))
705 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
719 /* Determine the outermost loop to that it is possible to hoist a statement
720 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
721 the outermost loop in that the value computed by STMT is invariant.
722 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
723 we preserve the fact whether STMT is executed. It also fills other related
724 information to LIM_DATA (STMT).
726 The function returns false if STMT cannot be hoisted outside of the loop it
727 is defined in, and true otherwise. */
730 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
732 basic_block bb
= gimple_bb (stmt
);
733 struct loop
*loop
= bb
->loop_father
;
735 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
739 if (must_preserve_exec
)
740 level
= ALWAYS_EXECUTED_IN (bb
);
742 level
= superloop_at_depth (loop
, 1);
743 lim_data
->max_loop
= level
;
745 if (gimple_code (stmt
) == GIMPLE_PHI
)
748 unsigned min_cost
= UINT_MAX
;
749 unsigned total_cost
= 0;
750 struct lim_aux_data
*def_data
;
752 /* We will end up promoting dependencies to be unconditionally
753 evaluated. For this reason the PHI cost (and thus the
754 cost we remove from the loop by doing the invariant motion)
755 is that of the cheapest PHI argument dependency chain. */
756 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
758 val
= USE_FROM_PTR (use_p
);
759 if (TREE_CODE (val
) != SSA_NAME
)
761 if (!add_dependency (val
, lim_data
, loop
, false))
763 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
766 min_cost
= MIN (min_cost
, def_data
->cost
);
767 total_cost
+= def_data
->cost
;
771 lim_data
->cost
+= min_cost
;
773 if (gimple_phi_num_args (stmt
) > 1)
775 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
777 if (gsi_end_p (gsi_last_bb (dom
)))
779 cond
= gsi_stmt (gsi_last_bb (dom
));
780 if (gimple_code (cond
) != GIMPLE_COND
)
782 /* Verify that this is an extended form of a diamond and
783 the PHI arguments are completely controlled by the
785 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
788 /* Fold in dependencies and cost of the condition. */
789 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
791 if (!add_dependency (val
, lim_data
, loop
, false))
793 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
795 total_cost
+= def_data
->cost
;
798 /* We want to avoid unconditionally executing very expensive
799 operations. As costs for our dependencies cannot be
800 negative just claim we are not invariand for this case.
801 We also are not sure whether the control-flow inside the
803 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
805 && total_cost
/ min_cost
<= 2))
808 /* Assume that the control-flow in the loop will vanish.
809 ??? We should verify this and not artificially increase
810 the cost if that is not the case. */
811 lim_data
->cost
+= stmt_cost (stmt
);
817 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
818 if (!add_dependency (val
, lim_data
, loop
, true))
821 if (gimple_vuse (stmt
))
823 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
828 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
829 if (!lim_data
->max_loop
)
834 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
836 if (!add_dependency (val
, lim_data
, loop
, false))
842 lim_data
->cost
+= stmt_cost (stmt
);
847 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
848 and that one of the operands of this statement is computed by STMT.
849 Ensure that STMT (together with all the statements that define its
850 operands) is hoisted at least out of the loop LEVEL. */
853 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
855 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
856 struct lim_aux_data
*lim_data
;
860 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
861 lim_data
= get_lim_data (stmt
);
862 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
863 stmt_loop
= find_common_loop (stmt_loop
,
864 loop_outer (lim_data
->tgt_loop
));
865 if (flow_loop_nested_p (stmt_loop
, level
))
868 gcc_assert (level
== lim_data
->max_loop
869 || flow_loop_nested_p (lim_data
->max_loop
, level
));
871 lim_data
->tgt_loop
= level
;
872 FOR_EACH_VEC_ELT (lim_data
->depends
, i
, dep_stmt
)
873 set_level (dep_stmt
, orig_loop
, level
);
876 /* Determines an outermost loop from that we want to hoist the statement STMT.
877 For now we chose the outermost possible loop. TODO -- use profiling
878 information to set it more sanely. */
881 set_profitable_level (gimple stmt
)
883 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
886 /* Returns true if STMT is a call that has side effects. */
889 nonpure_call_p (gimple stmt
)
891 if (gimple_code (stmt
) != GIMPLE_CALL
)
894 return gimple_has_side_effects (stmt
);
897 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
900 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
902 gimple stmt
, stmt1
, stmt2
;
903 tree name
, lhs
, type
;
905 gimple_stmt_iterator gsi
;
907 stmt
= gsi_stmt (*bsi
);
908 lhs
= gimple_assign_lhs (stmt
);
909 type
= TREE_TYPE (lhs
);
911 real_one
= build_one_cst (type
);
913 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
914 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
, name
, real_one
,
915 gimple_assign_rhs2 (stmt
));
917 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
918 gimple_assign_rhs1 (stmt
));
920 /* Replace division stmt with reciprocal and multiply stmts.
921 The multiply stmt is not invariant, so update iterator
922 and avoid rescanning. */
924 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
925 gsi_replace (&gsi
, stmt2
, true);
927 /* Continue processing with invariant reciprocal statement. */
931 /* Check if the pattern at *BSI is a bittest of the form
932 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
935 rewrite_bittest (gimple_stmt_iterator
*bsi
)
937 gimple stmt
, use_stmt
, stmt1
, stmt2
;
938 tree lhs
, name
, t
, a
, b
;
941 stmt
= gsi_stmt (*bsi
);
942 lhs
= gimple_assign_lhs (stmt
);
944 /* Verify that the single use of lhs is a comparison against zero. */
945 if (TREE_CODE (lhs
) != SSA_NAME
946 || !single_imm_use (lhs
, &use
, &use_stmt
)
947 || gimple_code (use_stmt
) != GIMPLE_COND
)
949 if (gimple_cond_lhs (use_stmt
) != lhs
950 || (gimple_cond_code (use_stmt
) != NE_EXPR
951 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
952 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
955 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
956 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
957 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
960 /* There is a conversion in between possibly inserted by fold. */
961 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
963 t
= gimple_assign_rhs1 (stmt1
);
964 if (TREE_CODE (t
) != SSA_NAME
965 || !has_single_use (t
))
967 stmt1
= SSA_NAME_DEF_STMT (t
);
968 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
972 /* Verify that B is loop invariant but A is not. Verify that with
973 all the stmt walking we are still in the same loop. */
974 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
975 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
978 a
= gimple_assign_rhs1 (stmt1
);
979 b
= gimple_assign_rhs2 (stmt1
);
981 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
982 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
984 gimple_stmt_iterator rsi
;
987 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
988 build_int_cst (TREE_TYPE (a
), 1), b
);
989 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
990 stmt1
= gimple_build_assign (name
, t
);
993 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
994 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
995 stmt2
= gimple_build_assign (name
, t
);
997 /* Replace the SSA_NAME we compare against zero. Adjust
998 the type of zero accordingly. */
1000 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
1002 /* Don't use gsi_replace here, none of the new assignments sets
1003 the variable originally set in stmt. Move bsi to stmt1, and
1004 then remove the original stmt, so that we get a chance to
1005 retain debug info for it. */
1007 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
1008 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
1009 gsi_remove (&rsi
, true);
1018 /* Determine the outermost loops in that statements in basic block BB are
1019 invariant, and record them to the LIM_DATA associated with the statements.
1020 Callback for walk_dominator_tree. */
1023 determine_invariantness_stmt (struct dom_walk_data
*dw_data ATTRIBUTE_UNUSED
,
1027 gimple_stmt_iterator bsi
;
1029 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1030 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1031 struct lim_aux_data
*lim_data
;
1033 if (!loop_outer (bb
->loop_father
))
1036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1037 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1038 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1040 /* Look at PHI nodes, but only if there is at most two.
1041 ??? We could relax this further by post-processing the inserted
1042 code and transforming adjacent cond-exprs with the same predicate
1043 to control flow again. */
1044 bsi
= gsi_start_phis (bb
);
1045 if (!gsi_end_p (bsi
)
1046 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1047 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1048 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1050 stmt
= gsi_stmt (bsi
);
1052 pos
= movement_possibility (stmt
);
1053 if (pos
== MOVE_IMPOSSIBLE
)
1056 lim_data
= init_lim_data (stmt
);
1057 lim_data
->always_executed_in
= outermost
;
1059 if (!determine_max_movement (stmt
, false))
1061 lim_data
->max_loop
= NULL
;
1065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1067 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1068 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1069 loop_depth (lim_data
->max_loop
),
1073 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1074 set_profitable_level (stmt
);
1077 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1079 stmt
= gsi_stmt (bsi
);
1081 pos
= movement_possibility (stmt
);
1082 if (pos
== MOVE_IMPOSSIBLE
)
1084 if (nonpure_call_p (stmt
))
1089 /* Make sure to note always_executed_in for stores to make
1090 store-motion work. */
1091 else if (stmt_makes_single_store (stmt
))
1093 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1094 lim_data
->always_executed_in
= outermost
;
1099 if (is_gimple_assign (stmt
)
1100 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1101 == GIMPLE_BINARY_RHS
))
1103 tree op0
= gimple_assign_rhs1 (stmt
);
1104 tree op1
= gimple_assign_rhs2 (stmt
);
1105 struct loop
*ol1
= outermost_invariant_loop (op1
,
1106 loop_containing_stmt (stmt
));
1108 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1109 to be hoisted out of loop, saving expensive divide. */
1110 if (pos
== MOVE_POSSIBLE
1111 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1112 && flag_unsafe_math_optimizations
1113 && !flag_trapping_math
1115 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1116 stmt
= rewrite_reciprocal (&bsi
);
1118 /* If the shift count is invariant, convert (A >> B) & 1 to
1119 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1120 saving an expensive shift. */
1121 if (pos
== MOVE_POSSIBLE
1122 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1123 && integer_onep (op1
)
1124 && TREE_CODE (op0
) == SSA_NAME
1125 && has_single_use (op0
))
1126 stmt
= rewrite_bittest (&bsi
);
1129 lim_data
= init_lim_data (stmt
);
1130 lim_data
->always_executed_in
= outermost
;
1132 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1135 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1137 lim_data
->max_loop
= NULL
;
1141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1143 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1144 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1145 loop_depth (lim_data
->max_loop
),
1149 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1150 set_profitable_level (stmt
);
1154 /* For each statement determines the outermost loop in that it is invariant,
1155 statements on whose motion it depends and the cost of the computation.
1156 This information is stored to the LIM_DATA structure associated with
1160 determine_invariantness (void)
1162 struct dom_walk_data walk_data
;
1164 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1165 walk_data
.dom_direction
= CDI_DOMINATORS
;
1166 walk_data
.before_dom_children
= determine_invariantness_stmt
;
1168 init_walk_dominator_tree (&walk_data
);
1169 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1170 fini_walk_dominator_tree (&walk_data
);
1173 /* Hoist the statements in basic block BB out of the loops prescribed by
1174 data stored in LIM_DATA structures associated with each statement. Callback
1175 for walk_dominator_tree. */
1178 move_computations_stmt (struct dom_walk_data
*dw_data
,
1182 gimple_stmt_iterator bsi
;
1185 struct lim_aux_data
*lim_data
;
1187 if (!loop_outer (bb
->loop_father
))
1190 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1193 stmt
= gsi_stmt (bsi
);
1195 lim_data
= get_lim_data (stmt
);
1196 if (lim_data
== NULL
)
1202 cost
= lim_data
->cost
;
1203 level
= lim_data
->tgt_loop
;
1204 clear_lim_data (stmt
);
1212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1214 fprintf (dump_file
, "Moving PHI node\n");
1215 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1216 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1220 if (gimple_phi_num_args (stmt
) == 1)
1222 tree arg
= PHI_ARG_DEF (stmt
, 0);
1223 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1224 gimple_phi_result (stmt
),
1226 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1230 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1231 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1232 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1233 /* Get the PHI arguments corresponding to the true and false
1235 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1236 gcc_assert (arg0
&& arg1
);
1237 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1238 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1239 new_stmt
= gimple_build_assign_with_ops (COND_EXPR
,
1240 gimple_phi_result (stmt
),
1242 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1243 *((unsigned int *)(dw_data
->global_data
)) |= TODO_cleanup_cfg
;
1245 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1246 remove_phi_node (&bsi
, false);
1249 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1253 stmt
= gsi_stmt (bsi
);
1255 lim_data
= get_lim_data (stmt
);
1256 if (lim_data
== NULL
)
1262 cost
= lim_data
->cost
;
1263 level
= lim_data
->tgt_loop
;
1264 clear_lim_data (stmt
);
1272 /* We do not really want to move conditionals out of the loop; we just
1273 placed it here to force its operands to be moved if necessary. */
1274 if (gimple_code (stmt
) == GIMPLE_COND
)
1277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1279 fprintf (dump_file
, "Moving statement\n");
1280 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1281 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1285 e
= loop_preheader_edge (level
);
1286 gcc_assert (!gimple_vdef (stmt
));
1287 if (gimple_vuse (stmt
))
1289 /* The new VUSE is the one from the virtual PHI in the loop
1290 header or the one already present. */
1291 gimple_stmt_iterator gsi2
;
1292 for (gsi2
= gsi_start_phis (e
->dest
);
1293 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1295 gimple phi
= gsi_stmt (gsi2
);
1296 if (virtual_operand_p (gimple_phi_result (phi
)))
1298 gimple_set_vuse (stmt
, PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1303 gsi_remove (&bsi
, false);
1304 gsi_insert_on_edge (e
, stmt
);
1308 /* Hoist the statements out of the loops prescribed by data stored in
1309 LIM_DATA structures associated with each statement.*/
1312 move_computations (void)
1314 struct dom_walk_data walk_data
;
1315 unsigned int todo
= 0;
1317 memset (&walk_data
, 0, sizeof (struct dom_walk_data
));
1318 walk_data
.global_data
= &todo
;
1319 walk_data
.dom_direction
= CDI_DOMINATORS
;
1320 walk_data
.before_dom_children
= move_computations_stmt
;
1322 init_walk_dominator_tree (&walk_data
);
1323 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1324 fini_walk_dominator_tree (&walk_data
);
1326 gsi_commit_edge_inserts ();
1327 if (need_ssa_update_p (cfun
))
1328 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1333 /* Checks whether the statement defining variable *INDEX can be hoisted
1334 out of the loop passed in DATA. Callback for for_each_index. */
1337 may_move_till (tree ref
, tree
*index
, void *data
)
1339 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1341 /* If REF is an array reference, check also that the step and the lower
1342 bound is invariant in LOOP. */
1343 if (TREE_CODE (ref
) == ARRAY_REF
)
1345 tree step
= TREE_OPERAND (ref
, 3);
1346 tree lbound
= TREE_OPERAND (ref
, 2);
1348 max_loop
= outermost_invariant_loop (step
, loop
);
1352 max_loop
= outermost_invariant_loop (lbound
, loop
);
1357 max_loop
= outermost_invariant_loop (*index
, loop
);
1364 /* If OP is SSA NAME, force the statement that defines it to be
1365 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1368 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1373 || is_gimple_min_invariant (op
))
1376 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1378 stmt
= SSA_NAME_DEF_STMT (op
);
1379 if (gimple_nop_p (stmt
))
1382 set_level (stmt
, orig_loop
, loop
);
1385 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1386 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1392 struct loop
*orig_loop
;
1396 force_move_till (tree ref
, tree
*index
, void *data
)
1398 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1400 if (TREE_CODE (ref
) == ARRAY_REF
)
1402 tree step
= TREE_OPERAND (ref
, 3);
1403 tree lbound
= TREE_OPERAND (ref
, 2);
1405 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1406 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1409 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1414 /* A hash function for struct mem_ref object OBJ. */
1417 memref_hash (const void *obj
)
1419 const struct mem_ref
*const mem
= (const struct mem_ref
*) obj
;
1424 /* An equality function for struct mem_ref object OBJ1 with
1425 memory reference OBJ2. */
1428 memref_eq (const void *obj1
, const void *obj2
)
1430 const struct mem_ref
*const mem1
= (const struct mem_ref
*) obj1
;
1432 return operand_equal_p (mem1
->mem
.ref
, (const_tree
) obj2
, 0);
1435 /* A function to free the mem_ref object OBJ. */
1438 memref_free (struct mem_ref
*mem
)
1441 vec
<mem_ref_loc
> *accs
;
1443 FOR_EACH_VEC_ELT (mem
->accesses_in_loop
, i
, accs
)
1445 mem
->accesses_in_loop
.release ();
1450 /* Allocates and returns a memory reference description for MEM whose hash
1451 value is HASH and id is ID. */
1454 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1456 mem_ref_p ref
= XNEW (struct mem_ref
);
1457 ao_ref_init (&ref
->mem
, mem
);
1460 bitmap_initialize (&ref
->stored
, &lim_bitmap_obstack
);
1461 bitmap_initialize (&ref
->indep_loop
, &lim_bitmap_obstack
);
1462 bitmap_initialize (&ref
->dep_loop
, &lim_bitmap_obstack
);
1463 ref
->accesses_in_loop
.create (0);
1468 /* Records memory reference location *LOC in LOOP to the memory reference
1469 description REF. The reference occurs in statement STMT. */
1472 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1476 if (ref
->accesses_in_loop
.length ()
1477 <= (unsigned) loop
->num
)
1478 ref
->accesses_in_loop
.safe_grow_cleared (loop
->num
+ 1);
1482 ref
->accesses_in_loop
[loop
->num
].safe_push (aref
);
1485 /* Marks reference REF as stored in LOOP. */
1488 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1490 while (loop
!= current_loops
->tree_root
1491 && bitmap_set_bit (&ref
->stored
, loop
->num
))
1492 loop
= loop_outer (loop
);
1495 /* Gathers memory references in statement STMT in LOOP, storing the
1496 information about them in the memory_accesses structure. Marks
1497 the vops accessed through unrecognized statements there as
1501 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1510 if (!gimple_vuse (stmt
))
1513 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1516 /* We use the shared mem_ref for all unanalyzable refs. */
1517 id
= UNANALYZABLE_MEM_ID
;
1518 ref
= memory_accesses
.refs_list
[id
];
1519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1521 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1522 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1524 is_stored
= gimple_vdef (stmt
);
1528 hash
= iterative_hash_expr (*mem
, 0);
1529 slot
= htab_find_slot_with_hash (memory_accesses
.refs
,
1530 *mem
, hash
, INSERT
);
1533 ref
= (mem_ref_p
) *slot
;
1538 id
= memory_accesses
.refs_list
.length ();
1539 ref
= mem_ref_alloc (*mem
, hash
, id
);
1540 memory_accesses
.refs_list
.safe_push (ref
);
1543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1545 fprintf (dump_file
, "Memory reference %u: ", id
);
1546 print_generic_expr (dump_file
, ref
->mem
.ref
, TDF_SLIM
);
1547 fprintf (dump_file
, "\n");
1551 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1553 bitmap_set_bit (&memory_accesses
.refs_in_loop
[loop
->num
], ref
->id
);
1556 bitmap_set_bit (&memory_accesses
.refs_stored_in_loop
[loop
->num
], ref
->id
);
1557 mark_ref_stored (ref
, loop
);
1562 static unsigned *bb_loop_postorder
;
1564 /* qsort sort function to sort blocks after their loop fathers postorder. */
1567 sort_bbs_in_loop_postorder_cmp (const void *bb1_
, const void *bb2_
)
1569 basic_block bb1
= *(basic_block
*)const_cast<void *>(bb1_
);
1570 basic_block bb2
= *(basic_block
*)const_cast<void *>(bb2_
);
1571 struct loop
*loop1
= bb1
->loop_father
;
1572 struct loop
*loop2
= bb2
->loop_father
;
1573 if (loop1
->num
== loop2
->num
)
1575 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1578 /* Gathers memory references in loops. */
1581 analyze_memory_references (void)
1583 gimple_stmt_iterator bsi
;
1584 basic_block bb
, *bbs
;
1585 struct loop
*loop
, *outer
;
1589 /* Initialize bb_loop_postorder with a mapping from loop->num to
1590 its postorder index. */
1592 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops ());
1593 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1594 bb_loop_postorder
[loop
->num
] = i
++;
1595 /* Collect all basic-blocks in loops and sort them after their
1598 bbs
= XNEWVEC (basic_block
, n_basic_blocks
- NUM_FIXED_BLOCKS
);
1600 if (bb
->loop_father
!= current_loops
->tree_root
)
1603 qsort (bbs
, n
, sizeof (basic_block
), sort_bbs_in_loop_postorder_cmp
);
1604 free (bb_loop_postorder
);
1606 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1607 That results in better locality for all the bitmaps. */
1608 for (i
= 0; i
< n
; ++i
)
1610 basic_block bb
= bbs
[i
];
1611 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1612 gather_mem_refs_stmt (bb
->loop_father
, gsi_stmt (bsi
));
1617 /* Propagate the information about accessed memory references up
1618 the loop hierarchy. */
1619 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1621 /* Finalize the overall touched references (including subloops). */
1622 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1623 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1625 /* Propagate the information about accessed memory references up
1626 the loop hierarchy. */
1627 outer
= loop_outer (loop
);
1628 if (outer
== current_loops
->tree_root
)
1631 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1632 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1636 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1637 tree_to_aff_combination_expand. */
1640 mem_refs_may_alias_p (mem_ref_p mem1
, mem_ref_p mem2
,
1641 struct pointer_map_t
**ttae_cache
)
1643 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1644 object and their offset differ in such a way that the locations cannot
1645 overlap, then they cannot alias. */
1646 double_int size1
, size2
;
1647 aff_tree off1
, off2
;
1649 /* Perform basic offset and type-based disambiguation. */
1650 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, true))
1653 /* The expansion of addresses may be a bit expensive, thus we only do
1654 the check at -O2 and higher optimization levels. */
1658 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1659 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1660 aff_combination_expand (&off1
, ttae_cache
);
1661 aff_combination_expand (&off2
, ttae_cache
);
1662 aff_combination_scale (&off1
, double_int_minus_one
);
1663 aff_combination_add (&off2
, &off1
);
1665 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1671 /* Iterates over all locations of REF in LOOP and its subloops calling
1672 fn.operator() with the location as argument. When that operator
1673 returns true the iteration is stopped and true is returned.
1674 Otherwise false is returned. */
1676 template <typename FN
>
1678 for_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
, FN fn
)
1682 struct loop
*subloop
;
1684 if (ref
->accesses_in_loop
.length () > (unsigned) loop
->num
)
1685 FOR_EACH_VEC_ELT (ref
->accesses_in_loop
[loop
->num
], i
, loc
)
1689 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1690 if (for_all_locs_in_loop (subloop
, ref
, fn
))
1696 /* Rewrites location LOC by TMP_VAR. */
1698 struct rewrite_mem_ref_loc
1700 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1701 bool operator()(mem_ref_loc_p loc
);
1706 rewrite_mem_ref_loc::operator()(mem_ref_loc_p loc
)
1708 *loc
->ref
= tmp_var
;
1709 update_stmt (loc
->stmt
);
1713 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1716 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1718 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1721 /* Stores the first reference location in LOCP. */
1723 struct first_mem_ref_loc_1
1725 first_mem_ref_loc_1 (mem_ref_loc_p
*locp_
) : locp (locp_
) {}
1726 bool operator()(mem_ref_loc_p loc
);
1727 mem_ref_loc_p
*locp
;
1731 first_mem_ref_loc_1::operator()(mem_ref_loc_p loc
)
1737 /* Returns the first reference location to REF in LOOP. */
1739 static mem_ref_loc_p
1740 first_mem_ref_loc (struct loop
*loop
, mem_ref_p ref
)
1742 mem_ref_loc_p locp
= NULL
;
1743 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1747 /* The name and the length of the currently generated variable
1749 #define MAX_LSM_NAME_LENGTH 40
1750 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
1751 static int lsm_tmp_name_length
;
1753 /* Adds S to lsm_tmp_name. */
1756 lsm_tmp_name_add (const char *s
)
1758 int l
= strlen (s
) + lsm_tmp_name_length
;
1759 if (l
> MAX_LSM_NAME_LENGTH
)
1762 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
1763 lsm_tmp_name_length
= l
;
1766 /* Stores the name for temporary variable that replaces REF to
1770 gen_lsm_tmp_name (tree ref
)
1774 switch (TREE_CODE (ref
))
1777 case TARGET_MEM_REF
:
1778 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1779 lsm_tmp_name_add ("_");
1783 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1787 case VIEW_CONVERT_EXPR
:
1788 case ARRAY_RANGE_REF
:
1789 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1793 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1794 lsm_tmp_name_add ("_RE");
1798 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1799 lsm_tmp_name_add ("_IM");
1803 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1804 lsm_tmp_name_add ("_");
1805 name
= get_name (TREE_OPERAND (ref
, 1));
1808 lsm_tmp_name_add (name
);
1812 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
1813 lsm_tmp_name_add ("_I");
1819 name
= get_name (ref
);
1822 lsm_tmp_name_add (name
);
1826 lsm_tmp_name_add ("S");
1830 lsm_tmp_name_add ("R");
1842 /* Determines name for temporary variable that replaces REF.
1843 The name is accumulated into the lsm_tmp_name variable.
1844 N is added to the name of the temporary. */
1847 get_lsm_tmp_name (tree ref
, unsigned n
)
1851 lsm_tmp_name_length
= 0;
1852 gen_lsm_tmp_name (ref
);
1853 lsm_tmp_name_add ("_lsm");
1858 lsm_tmp_name_add (ns
);
1860 return lsm_tmp_name
;
1863 struct prev_flag_edges
{
1864 /* Edge to insert new flag comparison code. */
1865 edge append_cond_position
;
1867 /* Edge for fall through from previous flag comparison. */
1868 edge last_cond_fallthru
;
1871 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1874 The store is only done if MEM has changed. We do this so no
1875 changes to MEM occur on code paths that did not originally store
1878 The common case for execute_sm will transform:
1898 This function will generate:
1917 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
)
1919 basic_block new_bb
, then_bb
, old_dest
;
1920 bool loop_has_only_one_exit
;
1921 edge then_old_edge
, orig_ex
= ex
;
1922 gimple_stmt_iterator gsi
;
1924 struct prev_flag_edges
*prev_edges
= (struct prev_flag_edges
*) ex
->aux
;
1926 /* ?? Insert store after previous store if applicable. See note
1929 ex
= prev_edges
->append_cond_position
;
1931 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1933 if (loop_has_only_one_exit
)
1934 ex
= split_block_after_labels (ex
->dest
);
1936 old_dest
= ex
->dest
;
1937 new_bb
= split_edge (ex
);
1938 then_bb
= create_empty_bb (new_bb
);
1939 if (current_loops
&& new_bb
->loop_father
)
1940 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1942 gsi
= gsi_start_bb (new_bb
);
1943 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1944 NULL_TREE
, NULL_TREE
);
1945 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1947 gsi
= gsi_start_bb (then_bb
);
1948 /* Insert actual store. */
1949 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1950 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1952 make_edge (new_bb
, then_bb
, EDGE_TRUE_VALUE
);
1953 make_edge (new_bb
, old_dest
, EDGE_FALSE_VALUE
);
1954 then_old_edge
= make_edge (then_bb
, old_dest
, EDGE_FALLTHRU
);
1956 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
1960 basic_block prevbb
= prev_edges
->last_cond_fallthru
->src
;
1961 redirect_edge_succ (prev_edges
->last_cond_fallthru
, new_bb
);
1962 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
1963 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
1964 recompute_dominator (CDI_DOMINATORS
, old_dest
));
1967 /* ?? Because stores may alias, they must happen in the exact
1968 sequence they originally happened. Save the position right after
1969 the (_lsm) store we just created so we can continue appending after
1970 it and maintain the original order. */
1972 struct prev_flag_edges
*p
;
1975 orig_ex
->aux
= NULL
;
1976 alloc_aux_for_edge (orig_ex
, sizeof (struct prev_flag_edges
));
1977 p
= (struct prev_flag_edges
*) orig_ex
->aux
;
1978 p
->append_cond_position
= then_old_edge
;
1979 p
->last_cond_fallthru
= find_edge (new_bb
, old_dest
);
1980 orig_ex
->aux
= (void *) p
;
1983 if (!loop_has_only_one_exit
)
1984 for (gsi
= gsi_start_phis (old_dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1986 gimple phi
= gsi_stmt (gsi
);
1989 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1990 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
1992 tree arg
= gimple_phi_arg_def (phi
, i
);
1993 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
1997 /* Remove the original fall through edge. This was the
1998 single_succ_edge (new_bb). */
1999 EDGE_SUCC (new_bb
, 0)->flags
&= ~EDGE_FALLTHRU
;
2002 /* When REF is set on the location, set flag indicating the store. */
2004 struct sm_set_flag_if_changed
2006 sm_set_flag_if_changed (tree flag_
) : flag (flag_
) {}
2007 bool operator()(mem_ref_loc_p loc
);
2012 sm_set_flag_if_changed::operator()(mem_ref_loc_p loc
)
2014 /* Only set the flag for writes. */
2015 if (is_gimple_assign (loc
->stmt
)
2016 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
2018 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
2019 gimple stmt
= gimple_build_assign (flag
, boolean_true_node
);
2020 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2025 /* Helper function for execute_sm. On every location where REF is
2026 set, set an appropriate flag indicating the store. */
2029 execute_sm_if_changed_flag_set (struct loop
*loop
, mem_ref_p ref
)
2032 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0);
2033 lsm_tmp_name_add ("_flag");
2034 flag
= create_tmp_reg (boolean_type_node
, str
);
2035 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
));
2039 /* Executes store motion of memory reference REF from LOOP.
2040 Exits from the LOOP are stored in EXITS. The initialization of the
2041 temporary variable is put to the preheader of the loop, and assignments
2042 to the reference from the temporary variable are emitted to exits. */
2045 execute_sm (struct loop
*loop
, vec
<edge
> exits
, mem_ref_p ref
)
2047 tree tmp_var
, store_flag
;
2050 struct fmt_data fmt_data
;
2052 struct lim_aux_data
*lim_data
;
2053 bool multi_threaded_model_p
= false;
2054 gimple_stmt_iterator gsi
;
2056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2058 fprintf (dump_file
, "Executing store motion of ");
2059 print_generic_expr (dump_file
, ref
->mem
.ref
, 0);
2060 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2063 tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
2064 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
2066 fmt_data
.loop
= loop
;
2067 fmt_data
.orig_loop
= loop
;
2068 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
2070 if (block_in_transaction (loop_preheader_edge (loop
)->src
)
2071 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
))
2072 multi_threaded_model_p
= true;
2074 if (multi_threaded_model_p
)
2075 store_flag
= execute_sm_if_changed_flag_set (loop
, ref
);
2077 rewrite_mem_refs (loop
, ref
, tmp_var
);
2079 /* Emit the load code on a random exit edge or into the latch if
2080 the loop does not exit, so that we are sure it will be processed
2081 by move_computations after all dependencies. */
2082 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
2084 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
2085 load altogether, since the store is predicated by a flag. We
2086 could, do the load only if it was originally in the loop. */
2087 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
.ref
));
2088 lim_data
= init_lim_data (load
);
2089 lim_data
->max_loop
= loop
;
2090 lim_data
->tgt_loop
= loop
;
2091 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2093 if (multi_threaded_model_p
)
2095 load
= gimple_build_assign (store_flag
, boolean_false_node
);
2096 lim_data
= init_lim_data (load
);
2097 lim_data
->max_loop
= loop
;
2098 lim_data
->tgt_loop
= loop
;
2099 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2102 /* Sink the store to every exit from the loop. */
2103 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2104 if (!multi_threaded_model_p
)
2107 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
), tmp_var
);
2108 gsi_insert_on_edge (ex
, store
);
2111 execute_sm_if_changed (ex
, ref
->mem
.ref
, tmp_var
, store_flag
);
2114 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2115 edges of the LOOP. */
2118 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2125 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2127 ref
= memory_accesses
.refs_list
[i
];
2128 execute_sm (loop
, exits
, ref
);
2132 struct ref_always_accessed
2134 ref_always_accessed (struct loop
*loop_
, tree base_
, bool stored_p_
)
2135 : loop (loop_
), base (base_
), stored_p (stored_p_
) {}
2136 bool operator()(mem_ref_loc_p loc
);
2143 ref_always_accessed::operator()(mem_ref_loc_p loc
)
2145 struct loop
*must_exec
;
2147 if (!get_lim_data (loc
->stmt
))
2150 /* If we require an always executed store make sure the statement
2151 stores to the reference. */
2155 if (!gimple_get_lhs (loc
->stmt
))
2157 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2160 if (INDIRECT_REF_P (lhs
)
2161 || TREE_CODE (lhs
) == MEM_REF
)
2162 lhs
= TREE_OPERAND (lhs
, 0);
2167 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2171 if (must_exec
== loop
2172 || flow_loop_nested_p (must_exec
, loop
))
2178 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2179 make sure REF is always stored to in LOOP. */
2182 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2184 tree base
= ao_ref_base (&ref
->mem
);
2185 if (TREE_CODE (base
) == MEM_REF
)
2186 base
= TREE_OPERAND (base
, 0);
2188 return for_all_locs_in_loop (loop
, ref
,
2189 ref_always_accessed (loop
, base
, stored_p
));
2192 /* Returns true if REF1 and REF2 are independent. */
2195 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2200 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2201 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2202 ref1
->id
, ref2
->id
);
2204 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
))
2206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2207 fprintf (dump_file
, "dependent.\n");
2212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2213 fprintf (dump_file
, "independent.\n");
2218 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2219 and its super-loops. */
2222 record_dep_loop (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2224 /* We can propagate dependent-in-loop bits up the loop
2225 hierarchy to all outer loops. */
2226 while (loop
!= current_loops
->tree_root
2227 && bitmap_set_bit (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2228 loop
= loop_outer (loop
);
2231 /* Returns true if REF is independent on all other memory references in
2235 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2237 bitmap refs_to_check
;
2243 refs_to_check
= &memory_accesses
.refs_in_loop
[loop
->num
];
2245 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2247 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2250 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2252 aref
= memory_accesses
.refs_list
[i
];
2253 if (!refs_independent_p (ref
, aref
))
2260 /* Returns true if REF is independent on all other memory references in
2261 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2264 ref_indep_loop_p_2 (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2266 stored_p
|= bitmap_bit_p (&ref
->stored
, loop
->num
);
2268 if (bitmap_bit_p (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2270 if (bitmap_bit_p (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2273 struct loop
*inner
= loop
->inner
;
2276 if (!ref_indep_loop_p_2 (inner
, ref
, stored_p
))
2278 inner
= inner
->next
;
2281 bool indep_p
= ref_indep_loop_p_1 (loop
, ref
, stored_p
);
2283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2284 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2285 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2287 /* Record the computed result in the cache. */
2290 if (bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
))
2293 /* If it's independend against all refs then it's independent
2294 against stores, too. */
2295 bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, false));
2300 record_dep_loop (loop
, ref
, stored_p
);
2303 /* If it's dependent against stores it's dependent against
2305 record_dep_loop (loop
, ref
, true);
2312 /* Returns true if REF is independent on all other memory references in
2316 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2318 gcc_checking_assert (MEM_ANALYZABLE (ref
));
2320 return ref_indep_loop_p_2 (loop
, ref
, false);
2323 /* Returns true if we can perform store motion of REF from LOOP. */
2326 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2330 /* Can't hoist unanalyzable refs. */
2331 if (!MEM_ANALYZABLE (ref
))
2334 /* It should be movable. */
2335 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2336 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2337 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2340 /* If it can throw fail, we do not properly update EH info. */
2341 if (tree_could_throw_p (ref
->mem
.ref
))
2344 /* If it can trap, it must be always executed in LOOP.
2345 Readonly memory locations may trap when storing to them, but
2346 tree_could_trap_p is a predicate for rvalues, so check that
2348 base
= get_base_address (ref
->mem
.ref
);
2349 if ((tree_could_trap_p (ref
->mem
.ref
)
2350 || (DECL_P (base
) && TREE_READONLY (base
)))
2351 && !ref_always_accessed_p (loop
, ref
, true))
2354 /* And it must be independent on all other memory references
2356 if (!ref_indep_loop_p (loop
, ref
))
2362 /* Marks the references in LOOP for that store motion should be performed
2363 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2364 motion was performed in one of the outer loops. */
2367 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2369 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2374 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2376 ref
= memory_accesses
.refs_list
[i
];
2377 if (can_sm_ref_p (loop
, ref
))
2378 bitmap_set_bit (refs_to_sm
, i
);
2382 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2383 for a store motion optimization (i.e. whether we can insert statement
2387 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2393 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2394 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2400 /* Try to perform store motion for all memory references modified inside
2401 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2402 store motion was executed in one of the outer loops. */
2405 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2407 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2408 struct loop
*subloop
;
2409 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2411 if (loop_suitable_for_sm (loop
, exits
))
2413 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2414 hoist_memory_references (loop
, sm_in_loop
, exits
);
2418 bitmap_ior_into (sm_executed
, sm_in_loop
);
2419 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2420 store_motion_loop (subloop
, sm_executed
);
2421 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2422 BITMAP_FREE (sm_in_loop
);
2425 /* Try to perform store motion for all memory references modified inside
2432 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2434 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2435 store_motion_loop (loop
, sm_executed
);
2437 BITMAP_FREE (sm_executed
);
2438 gsi_commit_edge_inserts ();
2441 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2442 for each such basic block bb records the outermost loop for that execution
2443 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2444 blocks that contain a nonpure call. */
2447 fill_always_executed_in_1 (struct loop
*loop
, sbitmap contains_call
)
2449 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2452 struct loop
*inn_loop
= loop
;
2454 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2456 bbs
= get_loop_body_in_dom_order (loop
);
2458 for (i
= 0; i
< loop
->num_nodes
; i
++)
2463 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2466 if (bitmap_bit_p (contains_call
, bb
->index
))
2469 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2470 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2475 /* A loop might be infinite (TODO use simple loop analysis
2476 to disprove this if possible). */
2477 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2480 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2483 if (bb
->loop_father
->header
== bb
)
2485 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2488 /* In a loop that is always entered we may proceed anyway.
2489 But record that we entered it and stop once we leave it. */
2490 inn_loop
= bb
->loop_father
;
2496 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2497 if (last
== loop
->header
)
2499 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2505 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2506 fill_always_executed_in_1 (loop
, contains_call
);
2509 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2510 for each such basic block bb records the outermost loop for that execution
2511 of its header implies execution of bb. */
2514 fill_always_executed_in (void)
2516 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2520 bitmap_clear (contains_call
);
2523 gimple_stmt_iterator gsi
;
2524 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2526 if (nonpure_call_p (gsi_stmt (gsi
)))
2530 if (!gsi_end_p (gsi
))
2531 bitmap_set_bit (contains_call
, bb
->index
);
2534 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2535 fill_always_executed_in_1 (loop
, contains_call
);
2537 sbitmap_free (contains_call
);
2541 /* Compute the global information needed by the loop invariant motion pass. */
2544 tree_ssa_lim_initialize (void)
2548 bitmap_obstack_initialize (&lim_bitmap_obstack
);
2549 lim_aux_data_map
= pointer_map_create ();
2552 compute_transaction_bits ();
2554 alloc_aux_for_edges (0);
2556 memory_accesses
.refs
= htab_create (100, memref_hash
, memref_eq
, NULL
);
2557 memory_accesses
.refs_list
.create (100);
2558 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2559 memory_accesses
.refs_list
.quick_push
2560 (mem_ref_alloc (error_mark_node
, 0, UNANALYZABLE_MEM_ID
));
2562 memory_accesses
.refs_in_loop
.create (number_of_loops ());
2563 memory_accesses
.refs_in_loop
.quick_grow (number_of_loops ());
2564 memory_accesses
.refs_stored_in_loop
.create (number_of_loops ());
2565 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops ());
2566 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops ());
2567 memory_accesses
.all_refs_stored_in_loop
.quick_grow (number_of_loops ());
2569 for (i
= 0; i
< number_of_loops (); i
++)
2571 bitmap_initialize (&memory_accesses
.refs_in_loop
[i
],
2572 &lim_bitmap_obstack
);
2573 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
2574 &lim_bitmap_obstack
);
2575 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
2576 &lim_bitmap_obstack
);
2579 memory_accesses
.ttae_cache
= NULL
;
2582 /* Cleans up after the invariant motion pass. */
2585 tree_ssa_lim_finalize (void)
2591 free_aux_for_edges ();
2594 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2596 bitmap_obstack_release (&lim_bitmap_obstack
);
2597 pointer_map_destroy (lim_aux_data_map
);
2599 htab_delete (memory_accesses
.refs
);
2601 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
2603 memory_accesses
.refs_list
.release ();
2605 memory_accesses
.refs_in_loop
.release ();
2606 memory_accesses
.refs_stored_in_loop
.release ();
2607 memory_accesses
.all_refs_stored_in_loop
.release ();
2609 if (memory_accesses
.ttae_cache
)
2610 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
2613 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2614 i.e. those that are likely to be win regardless of the register pressure. */
2621 tree_ssa_lim_initialize ();
2623 /* Gathers information about memory accesses in the loops. */
2624 analyze_memory_references ();
2626 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2627 fill_always_executed_in ();
2629 /* For each statement determine the outermost loop in that it is
2630 invariant and cost for computing the invariant. */
2631 determine_invariantness ();
2633 /* Execute store motion. Force the necessary invariants to be moved
2634 out of the loops as well. */
2637 /* Move the expressions that are expensive enough. */
2638 todo
= move_computations ();
2640 tree_ssa_lim_finalize ();