1 /* Loop invariant motion.
2 Copyright (C) 2003-2015 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"
27 #include "hard-reg-set.h"
30 #include "fold-const.h"
33 #include "gimple-pretty-print.h"
34 #include "internal-fn.h"
37 #include "gimple-iterator.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop.h"
41 #include "tree-into-ssa.h"
45 #include "tree-pass.h"
47 #include "tree-affine.h"
48 #include "tree-ssa-propagate.h"
49 #include "trans-mem.h"
50 #include "gimple-fold.h"
52 /* TODO: Support for predicated code motion. I.e.
63 Where COND and INV are invariants, but evaluating INV may trap or be
64 invalid from some other reason if !COND. This may be transformed to
74 /* The auxiliary data kept for each statement. */
78 struct loop
*max_loop
; /* The outermost loop in that the statement
81 struct loop
*tgt_loop
; /* The loop out of that we want to move the
84 struct loop
*always_executed_in
;
85 /* The outermost loop for that we are sure
86 the statement is executed if the loop
89 unsigned cost
; /* Cost of the computation performed by the
92 vec
<gimple
> depends
; /* Vector of statements that must be also
93 hoisted out of the loop when this statement
94 is hoisted; i.e. those that define the
95 operands of the statement and are inside of
99 /* Maps statements to their lim_aux_data. */
101 static hash_map
<gimple
, lim_aux_data
*> *lim_aux_data_map
;
103 /* Description of a memory reference location. */
107 tree
*ref
; /* The reference itself. */
108 gimple stmt
; /* The statement in that it occurs. */
112 /* Description of a memory reference. */
116 unsigned id
; /* ID assigned to the memory reference
117 (its index in memory_accesses.refs_list) */
118 hashval_t hash
; /* Its hash value. */
120 /* The memory access itself and associated caching of alias-oracle
124 bitmap stored
; /* The set of loops in that this memory location
126 vec
<mem_ref_loc
> accesses_in_loop
;
127 /* The locations of the accesses. Vector
128 indexed by the loop number. */
130 /* The following sets are computed on demand. We keep both set and
131 its complement, so that we know whether the information was
132 already computed or not. */
133 bitmap_head indep_loop
; /* The set of loops in that the memory
134 reference is independent, meaning:
135 If it is stored in the loop, this store
136 is independent on all other loads and
138 If it is only loaded, then it is independent
139 on all stores in the loop. */
140 bitmap_head dep_loop
; /* The complement of INDEP_LOOP. */
143 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
144 to record (in)dependence against stores in the loop and its subloops, the
145 second to record (in)dependence against all references in the loop
147 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
149 /* Mem_ref hashtable helpers. */
151 struct mem_ref_hasher
: nofree_ptr_hash
<im_mem_ref
>
153 typedef tree_node
*compare_type
;
154 static inline hashval_t
hash (const im_mem_ref
*);
155 static inline bool equal (const im_mem_ref
*, const tree_node
*);
158 /* A hash function for struct im_mem_ref object OBJ. */
161 mem_ref_hasher::hash (const im_mem_ref
*mem
)
166 /* An equality function for struct im_mem_ref object MEM1 with
167 memory reference OBJ2. */
170 mem_ref_hasher::equal (const im_mem_ref
*mem1
, const tree_node
*obj2
)
172 return operand_equal_p (mem1
->mem
.ref
, (const_tree
) obj2
, 0);
176 /* Description of memory accesses in loops. */
180 /* The hash table of memory references accessed in loops. */
181 hash_table
<mem_ref_hasher
> *refs
;
183 /* The list of memory references. */
184 vec
<im_mem_ref
*> refs_list
;
186 /* The set of memory references accessed in each loop. */
187 vec
<bitmap_head
> refs_in_loop
;
189 /* The set of memory references stored in each loop. */
190 vec
<bitmap_head
> refs_stored_in_loop
;
192 /* The set of memory references stored in each loop, including subloops . */
193 vec
<bitmap_head
> all_refs_stored_in_loop
;
195 /* Cache for expanding memory addresses. */
196 hash_map
<tree
, name_expansion
*> *ttae_cache
;
199 /* Obstack for the bitmaps in the above data structures. */
200 static bitmap_obstack lim_bitmap_obstack
;
201 static obstack mem_ref_obstack
;
203 static bool ref_indep_loop_p (struct loop
*, im_mem_ref
*);
205 /* Minimum cost of an expensive expression. */
206 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
208 /* The outermost loop for which execution of the header guarantees that the
209 block will be executed. */
210 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
211 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
213 /* ID of the shared unanalyzable mem. */
214 #define UNANALYZABLE_MEM_ID 0
216 /* Whether the reference was analyzable. */
217 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
219 static struct lim_aux_data
*
220 init_lim_data (gimple stmt
)
222 lim_aux_data
*p
= XCNEW (struct lim_aux_data
);
223 lim_aux_data_map
->put (stmt
, p
);
228 static struct lim_aux_data
*
229 get_lim_data (gimple stmt
)
231 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
238 /* Releases the memory occupied by DATA. */
241 free_lim_aux_data (struct lim_aux_data
*data
)
243 data
->depends
.release ();
248 clear_lim_data (gimple stmt
)
250 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
254 free_lim_aux_data (*p
);
259 /* The possibilities of statement movement. */
262 MOVE_IMPOSSIBLE
, /* No movement -- side effect expression. */
263 MOVE_PRESERVE_EXECUTION
, /* Must not cause the non-executed statement
264 become executed -- memory accesses, ... */
265 MOVE_POSSIBLE
/* Unlimited movement. */
269 /* If it is possible to hoist the statement STMT unconditionally,
270 returns MOVE_POSSIBLE.
271 If it is possible to hoist the statement STMT, but we must avoid making
272 it executed if it would not be executed in the original program (e.g.
273 because it may trap), return MOVE_PRESERVE_EXECUTION.
274 Otherwise return MOVE_IMPOSSIBLE. */
277 movement_possibility (gimple stmt
)
280 enum move_pos ret
= MOVE_POSSIBLE
;
282 if (flag_unswitch_loops
283 && gimple_code (stmt
) == GIMPLE_COND
)
285 /* If we perform unswitching, force the operands of the invariant
286 condition to be moved out of the loop. */
287 return MOVE_POSSIBLE
;
290 if (gimple_code (stmt
) == GIMPLE_PHI
291 && gimple_phi_num_args (stmt
) <= 2
292 && !virtual_operand_p (gimple_phi_result (stmt
))
293 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
294 return MOVE_POSSIBLE
;
296 if (gimple_get_lhs (stmt
) == NULL_TREE
)
297 return MOVE_IMPOSSIBLE
;
299 if (gimple_vdef (stmt
))
300 return MOVE_IMPOSSIBLE
;
302 if (stmt_ends_bb_p (stmt
)
303 || gimple_has_volatile_ops (stmt
)
304 || gimple_has_side_effects (stmt
)
305 || stmt_could_throw_p (stmt
))
306 return MOVE_IMPOSSIBLE
;
308 if (is_gimple_call (stmt
))
310 /* While pure or const call is guaranteed to have no side effects, we
311 cannot move it arbitrarily. Consider code like
313 char *s = something ();
323 Here the strlen call cannot be moved out of the loop, even though
324 s is invariant. In addition to possibly creating a call with
325 invalid arguments, moving out a function call that is not executed
326 may cause performance regressions in case the call is costly and
327 not executed at all. */
328 ret
= MOVE_PRESERVE_EXECUTION
;
329 lhs
= gimple_call_lhs (stmt
);
331 else if (is_gimple_assign (stmt
))
332 lhs
= gimple_assign_lhs (stmt
);
334 return MOVE_IMPOSSIBLE
;
336 if (TREE_CODE (lhs
) == SSA_NAME
337 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
338 return MOVE_IMPOSSIBLE
;
340 if (TREE_CODE (lhs
) != SSA_NAME
341 || gimple_could_trap_p (stmt
))
342 return MOVE_PRESERVE_EXECUTION
;
344 /* Non local loads in a transaction cannot be hoisted out. Well,
345 unless the load happens on every path out of the loop, but we
346 don't take this into account yet. */
348 && gimple_in_transaction (stmt
)
349 && gimple_assign_single_p (stmt
))
351 tree rhs
= gimple_assign_rhs1 (stmt
);
352 if (DECL_P (rhs
) && is_global_var (rhs
))
356 fprintf (dump_file
, "Cannot hoist conditional load of ");
357 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
358 fprintf (dump_file
, " because it is in a transaction.\n");
360 return MOVE_IMPOSSIBLE
;
367 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
368 loop to that we could move the expression using DEF if it did not have
369 other operands, i.e. the outermost loop enclosing LOOP in that the value
370 of DEF is invariant. */
373 outermost_invariant_loop (tree def
, struct loop
*loop
)
377 struct loop
*max_loop
;
378 struct lim_aux_data
*lim_data
;
381 return superloop_at_depth (loop
, 1);
383 if (TREE_CODE (def
) != SSA_NAME
)
385 gcc_assert (is_gimple_min_invariant (def
));
386 return superloop_at_depth (loop
, 1);
389 def_stmt
= SSA_NAME_DEF_STMT (def
);
390 def_bb
= gimple_bb (def_stmt
);
392 return superloop_at_depth (loop
, 1);
394 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
396 lim_data
= get_lim_data (def_stmt
);
397 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
398 max_loop
= find_common_loop (max_loop
,
399 loop_outer (lim_data
->max_loop
));
400 if (max_loop
== loop
)
402 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
407 /* DATA is a structure containing information associated with a statement
408 inside LOOP. DEF is one of the operands of this statement.
410 Find the outermost loop enclosing LOOP in that value of DEF is invariant
411 and record this in DATA->max_loop field. If DEF itself is defined inside
412 this loop as well (i.e. we need to hoist it out of the loop if we want
413 to hoist the statement represented by DATA), record the statement in that
414 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
415 add the cost of the computation of DEF to the DATA->cost.
417 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
420 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
423 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
424 basic_block def_bb
= gimple_bb (def_stmt
);
425 struct loop
*max_loop
;
426 struct lim_aux_data
*def_data
;
431 max_loop
= outermost_invariant_loop (def
, loop
);
435 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
436 data
->max_loop
= max_loop
;
438 def_data
= get_lim_data (def_stmt
);
443 /* Only add the cost if the statement defining DEF is inside LOOP,
444 i.e. if it is likely that by moving the invariants dependent
445 on it, we will be able to avoid creating a new register for
446 it (since it will be only used in these dependent invariants). */
447 && def_bb
->loop_father
== loop
)
448 data
->cost
+= def_data
->cost
;
450 data
->depends
.safe_push (def_stmt
);
455 /* Returns an estimate for a cost of statement STMT. The values here
456 are just ad-hoc constants, similar to costs for inlining. */
459 stmt_cost (gimple stmt
)
461 /* Always try to create possibilities for unswitching. */
462 if (gimple_code (stmt
) == GIMPLE_COND
463 || gimple_code (stmt
) == GIMPLE_PHI
)
464 return LIM_EXPENSIVE
;
466 /* We should be hoisting calls if possible. */
467 if (is_gimple_call (stmt
))
471 /* Unless the call is a builtin_constant_p; this always folds to a
472 constant, so moving it is useless. */
473 fndecl
= gimple_call_fndecl (stmt
);
475 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
476 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
479 return LIM_EXPENSIVE
;
482 /* Hoisting memory references out should almost surely be a win. */
483 if (gimple_references_memory_p (stmt
))
484 return LIM_EXPENSIVE
;
486 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
489 switch (gimple_assign_rhs_code (stmt
))
492 case WIDEN_MULT_EXPR
:
493 case WIDEN_MULT_PLUS_EXPR
:
494 case WIDEN_MULT_MINUS_EXPR
:
507 /* Division and multiplication are usually expensive. */
508 return LIM_EXPENSIVE
;
512 case WIDEN_LSHIFT_EXPR
:
515 /* Shifts and rotates are usually expensive. */
516 return LIM_EXPENSIVE
;
519 /* Make vector construction cost proportional to the number
521 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
525 /* Whether or not something is wrapped inside a PAREN_EXPR
526 should not change move cost. Nor should an intermediate
527 unpropagated SSA name copy. */
535 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
536 REF is independent. If REF is not independent in LOOP, NULL is returned
540 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, im_mem_ref
*ref
)
544 if (ref
->stored
&& bitmap_bit_p (ref
->stored
, loop
->num
))
549 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
550 if ((!ref
->stored
|| !bitmap_bit_p (ref
->stored
, aloop
->num
))
551 && ref_indep_loop_p (aloop
, ref
))
554 if (ref_indep_loop_p (loop
, ref
))
560 /* If there is a simple load or store to a memory reference in STMT, returns
561 the location of the memory reference, and sets IS_STORE according to whether
562 it is a store or load. Otherwise, returns NULL. */
565 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
569 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
570 if (!gimple_assign_single_p (stmt
))
573 lhs
= gimple_assign_lhs_ptr (stmt
);
574 rhs
= gimple_assign_rhs1_ptr (stmt
);
576 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
581 else if (gimple_vdef (stmt
)
582 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
591 /* Returns the memory reference contained in STMT. */
594 mem_ref_in_stmt (gimple stmt
)
597 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
605 hash
= iterative_hash_expr (*mem
, 0);
606 ref
= memory_accesses
.refs
->find_with_hash (*mem
, hash
);
608 gcc_assert (ref
!= NULL
);
612 /* From a controlling predicate in DOM determine the arguments from
613 the PHI node PHI that are chosen if the predicate evaluates to
614 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
615 they are non-NULL. Returns true if the arguments can be determined,
616 else return false. */
619 extract_true_false_args_from_phi (basic_block dom
, gphi
*phi
,
620 tree
*true_arg_p
, tree
*false_arg_p
)
622 basic_block bb
= gimple_bb (phi
);
623 edge true_edge
, false_edge
, tem
;
624 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
626 /* We have to verify that one edge into the PHI node is dominated
627 by the true edge of the predicate block and the other edge
628 dominated by the false edge. This ensures that the PHI argument
629 we are going to take is completely determined by the path we
630 take from the predicate block.
631 We can only use BB dominance checks below if the destination of
632 the true/false edges are dominated by their edge, thus only
633 have a single predecessor. */
634 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
635 tem
= EDGE_PRED (bb
, 0);
637 || (single_pred_p (true_edge
->dest
)
638 && (tem
->src
== true_edge
->dest
639 || dominated_by_p (CDI_DOMINATORS
,
640 tem
->src
, true_edge
->dest
))))
641 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
642 else if (tem
== false_edge
643 || (single_pred_p (false_edge
->dest
)
644 && (tem
->src
== false_edge
->dest
645 || dominated_by_p (CDI_DOMINATORS
,
646 tem
->src
, false_edge
->dest
))))
647 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
650 tem
= EDGE_PRED (bb
, 1);
652 || (single_pred_p (true_edge
->dest
)
653 && (tem
->src
== true_edge
->dest
654 || dominated_by_p (CDI_DOMINATORS
,
655 tem
->src
, true_edge
->dest
))))
656 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
657 else if (tem
== false_edge
658 || (single_pred_p (false_edge
->dest
)
659 && (tem
->src
== false_edge
->dest
660 || dominated_by_p (CDI_DOMINATORS
,
661 tem
->src
, false_edge
->dest
))))
662 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
676 /* Determine the outermost loop to that it is possible to hoist a statement
677 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
678 the outermost loop in that the value computed by STMT is invariant.
679 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
680 we preserve the fact whether STMT is executed. It also fills other related
681 information to LIM_DATA (STMT).
683 The function returns false if STMT cannot be hoisted outside of the loop it
684 is defined in, and true otherwise. */
687 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
689 basic_block bb
= gimple_bb (stmt
);
690 struct loop
*loop
= bb
->loop_father
;
692 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
696 if (must_preserve_exec
)
697 level
= ALWAYS_EXECUTED_IN (bb
);
699 level
= superloop_at_depth (loop
, 1);
700 lim_data
->max_loop
= level
;
702 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
705 unsigned min_cost
= UINT_MAX
;
706 unsigned total_cost
= 0;
707 struct lim_aux_data
*def_data
;
709 /* We will end up promoting dependencies to be unconditionally
710 evaluated. For this reason the PHI cost (and thus the
711 cost we remove from the loop by doing the invariant motion)
712 is that of the cheapest PHI argument dependency chain. */
713 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
715 val
= USE_FROM_PTR (use_p
);
717 if (TREE_CODE (val
) != SSA_NAME
)
719 /* Assign const 1 to constants. */
720 min_cost
= MIN (min_cost
, 1);
724 if (!add_dependency (val
, lim_data
, loop
, false))
727 gimple def_stmt
= SSA_NAME_DEF_STMT (val
);
728 if (gimple_bb (def_stmt
)
729 && gimple_bb (def_stmt
)->loop_father
== loop
)
731 def_data
= get_lim_data (def_stmt
);
734 min_cost
= MIN (min_cost
, def_data
->cost
);
735 total_cost
+= def_data
->cost
;
740 min_cost
= MIN (min_cost
, total_cost
);
741 lim_data
->cost
+= min_cost
;
743 if (gimple_phi_num_args (phi
) > 1)
745 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
747 if (gsi_end_p (gsi_last_bb (dom
)))
749 cond
= gsi_stmt (gsi_last_bb (dom
));
750 if (gimple_code (cond
) != GIMPLE_COND
)
752 /* Verify that this is an extended form of a diamond and
753 the PHI arguments are completely controlled by the
755 if (!extract_true_false_args_from_phi (dom
, phi
, NULL
, NULL
))
758 /* Fold in dependencies and cost of the condition. */
759 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
761 if (!add_dependency (val
, lim_data
, loop
, false))
763 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
765 total_cost
+= def_data
->cost
;
768 /* We want to avoid unconditionally executing very expensive
769 operations. As costs for our dependencies cannot be
770 negative just claim we are not invariand for this case.
771 We also are not sure whether the control-flow inside the
773 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
775 && total_cost
/ min_cost
<= 2))
778 /* Assume that the control-flow in the loop will vanish.
779 ??? We should verify this and not artificially increase
780 the cost if that is not the case. */
781 lim_data
->cost
+= stmt_cost (stmt
);
787 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
788 if (!add_dependency (val
, lim_data
, loop
, true))
791 if (gimple_vuse (stmt
))
793 im_mem_ref
*ref
= mem_ref_in_stmt (stmt
);
798 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
799 if (!lim_data
->max_loop
)
804 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
806 if (!add_dependency (val
, lim_data
, loop
, false))
812 lim_data
->cost
+= stmt_cost (stmt
);
817 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
818 and that one of the operands of this statement is computed by STMT.
819 Ensure that STMT (together with all the statements that define its
820 operands) is hoisted at least out of the loop LEVEL. */
823 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
825 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
826 struct lim_aux_data
*lim_data
;
830 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
831 lim_data
= get_lim_data (stmt
);
832 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
833 stmt_loop
= find_common_loop (stmt_loop
,
834 loop_outer (lim_data
->tgt_loop
));
835 if (flow_loop_nested_p (stmt_loop
, level
))
838 gcc_assert (level
== lim_data
->max_loop
839 || flow_loop_nested_p (lim_data
->max_loop
, level
));
841 lim_data
->tgt_loop
= level
;
842 FOR_EACH_VEC_ELT (lim_data
->depends
, i
, dep_stmt
)
843 set_level (dep_stmt
, orig_loop
, level
);
846 /* Determines an outermost loop from that we want to hoist the statement STMT.
847 For now we chose the outermost possible loop. TODO -- use profiling
848 information to set it more sanely. */
851 set_profitable_level (gimple stmt
)
853 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
856 /* Returns true if STMT is a call that has side effects. */
859 nonpure_call_p (gimple stmt
)
861 if (gimple_code (stmt
) != GIMPLE_CALL
)
864 return gimple_has_side_effects (stmt
);
867 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
870 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
872 gassign
*stmt
, *stmt1
, *stmt2
;
873 tree name
, lhs
, type
;
875 gimple_stmt_iterator gsi
;
877 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
878 lhs
= gimple_assign_lhs (stmt
);
879 type
= TREE_TYPE (lhs
);
881 real_one
= build_one_cst (type
);
883 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
884 stmt1
= gimple_build_assign (name
, RDIV_EXPR
, real_one
,
885 gimple_assign_rhs2 (stmt
));
886 stmt2
= gimple_build_assign (lhs
, MULT_EXPR
, name
,
887 gimple_assign_rhs1 (stmt
));
889 /* Replace division stmt with reciprocal and multiply stmts.
890 The multiply stmt is not invariant, so update iterator
891 and avoid rescanning. */
893 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
894 gsi_replace (&gsi
, stmt2
, true);
896 /* Continue processing with invariant reciprocal statement. */
900 /* Check if the pattern at *BSI is a bittest of the form
901 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
904 rewrite_bittest (gimple_stmt_iterator
*bsi
)
911 tree lhs
, name
, t
, a
, b
;
914 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
915 lhs
= gimple_assign_lhs (stmt
);
917 /* Verify that the single use of lhs is a comparison against zero. */
918 if (TREE_CODE (lhs
) != SSA_NAME
919 || !single_imm_use (lhs
, &use
, &use_stmt
))
921 cond_stmt
= dyn_cast
<gcond
*> (use_stmt
);
924 if (gimple_cond_lhs (cond_stmt
) != lhs
925 || (gimple_cond_code (cond_stmt
) != NE_EXPR
926 && gimple_cond_code (cond_stmt
) != EQ_EXPR
)
927 || !integer_zerop (gimple_cond_rhs (cond_stmt
)))
930 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
931 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
932 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
935 /* There is a conversion in between possibly inserted by fold. */
936 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
938 t
= gimple_assign_rhs1 (stmt1
);
939 if (TREE_CODE (t
) != SSA_NAME
940 || !has_single_use (t
))
942 stmt1
= SSA_NAME_DEF_STMT (t
);
943 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
947 /* Verify that B is loop invariant but A is not. Verify that with
948 all the stmt walking we are still in the same loop. */
949 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
950 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
953 a
= gimple_assign_rhs1 (stmt1
);
954 b
= gimple_assign_rhs2 (stmt1
);
956 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
957 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
959 gimple_stmt_iterator rsi
;
962 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
963 build_int_cst (TREE_TYPE (a
), 1), b
);
964 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
965 stmt1
= gimple_build_assign (name
, t
);
968 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
969 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
970 stmt2
= gimple_build_assign (name
, t
);
972 /* Replace the SSA_NAME we compare against zero. Adjust
973 the type of zero accordingly. */
975 gimple_cond_set_rhs (cond_stmt
,
976 build_int_cst_type (TREE_TYPE (name
),
979 /* Don't use gsi_replace here, none of the new assignments sets
980 the variable originally set in stmt. Move bsi to stmt1, and
981 then remove the original stmt, so that we get a chance to
982 retain debug info for it. */
984 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
985 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
986 gsi_remove (&rsi
, true);
994 /* For each statement determines the outermost loop in that it is invariant,
995 - statements on whose motion it depends and the cost of the computation.
996 - This information is stored to the LIM_DATA structure associated with
998 class invariantness_dom_walker
: public dom_walker
1001 invariantness_dom_walker (cdi_direction direction
)
1002 : dom_walker (direction
) {}
1004 virtual void before_dom_children (basic_block
);
1007 /* Determine the outermost loops in that statements in basic block BB are
1008 invariant, and record them to the LIM_DATA associated with the statements.
1009 Callback for dom_walker. */
1012 invariantness_dom_walker::before_dom_children (basic_block bb
)
1015 gimple_stmt_iterator bsi
;
1017 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
1018 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
1019 struct lim_aux_data
*lim_data
;
1021 if (!loop_outer (bb
->loop_father
))
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1025 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1026 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1028 /* Look at PHI nodes, but only if there is at most two.
1029 ??? We could relax this further by post-processing the inserted
1030 code and transforming adjacent cond-exprs with the same predicate
1031 to control flow again. */
1032 bsi
= gsi_start_phis (bb
);
1033 if (!gsi_end_p (bsi
)
1034 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1035 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1036 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1038 stmt
= gsi_stmt (bsi
);
1040 pos
= movement_possibility (stmt
);
1041 if (pos
== MOVE_IMPOSSIBLE
)
1044 lim_data
= init_lim_data (stmt
);
1045 lim_data
->always_executed_in
= outermost
;
1047 if (!determine_max_movement (stmt
, false))
1049 lim_data
->max_loop
= NULL
;
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1055 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1056 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1057 loop_depth (lim_data
->max_loop
),
1061 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1062 set_profitable_level (stmt
);
1065 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1067 stmt
= gsi_stmt (bsi
);
1069 pos
= movement_possibility (stmt
);
1070 if (pos
== MOVE_IMPOSSIBLE
)
1072 if (nonpure_call_p (stmt
))
1077 /* Make sure to note always_executed_in for stores to make
1078 store-motion work. */
1079 else if (stmt_makes_single_store (stmt
))
1081 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1082 lim_data
->always_executed_in
= outermost
;
1087 if (is_gimple_assign (stmt
)
1088 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1089 == GIMPLE_BINARY_RHS
))
1091 tree op0
= gimple_assign_rhs1 (stmt
);
1092 tree op1
= gimple_assign_rhs2 (stmt
);
1093 struct loop
*ol1
= outermost_invariant_loop (op1
,
1094 loop_containing_stmt (stmt
));
1096 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1097 to be hoisted out of loop, saving expensive divide. */
1098 if (pos
== MOVE_POSSIBLE
1099 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1100 && flag_unsafe_math_optimizations
1101 && !flag_trapping_math
1103 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1104 stmt
= rewrite_reciprocal (&bsi
);
1106 /* If the shift count is invariant, convert (A >> B) & 1 to
1107 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1108 saving an expensive shift. */
1109 if (pos
== MOVE_POSSIBLE
1110 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1111 && integer_onep (op1
)
1112 && TREE_CODE (op0
) == SSA_NAME
1113 && has_single_use (op0
))
1114 stmt
= rewrite_bittest (&bsi
);
1117 lim_data
= init_lim_data (stmt
);
1118 lim_data
->always_executed_in
= outermost
;
1120 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1123 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1125 lim_data
->max_loop
= NULL
;
1129 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1132 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1133 loop_depth (lim_data
->max_loop
),
1137 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1138 set_profitable_level (stmt
);
1142 class move_computations_dom_walker
: public dom_walker
1145 move_computations_dom_walker (cdi_direction direction
)
1146 : dom_walker (direction
), todo_ (0) {}
1148 virtual void before_dom_children (basic_block
);
1153 /* Hoist the statements in basic block BB out of the loops prescribed by
1154 data stored in LIM_DATA structures associated with each statement. Callback
1155 for walk_dominator_tree. */
1158 move_computations_dom_walker::before_dom_children (basic_block bb
)
1162 struct lim_aux_data
*lim_data
;
1164 if (!loop_outer (bb
->loop_father
))
1167 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1170 gphi
*stmt
= bsi
.phi ();
1172 lim_data
= get_lim_data (stmt
);
1173 if (lim_data
== NULL
)
1179 cost
= lim_data
->cost
;
1180 level
= lim_data
->tgt_loop
;
1181 clear_lim_data (stmt
);
1189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1191 fprintf (dump_file
, "Moving PHI node\n");
1192 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1193 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1197 if (gimple_phi_num_args (stmt
) == 1)
1199 tree arg
= PHI_ARG_DEF (stmt
, 0);
1200 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1201 TREE_CODE (arg
), arg
);
1205 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1206 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1207 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1208 /* Get the PHI arguments corresponding to the true and false
1210 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1211 gcc_assert (arg0
&& arg1
);
1212 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1213 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1214 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1215 COND_EXPR
, t
, arg0
, arg1
);
1216 todo_
|= TODO_cleanup_cfg
;
1218 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt
)))
1219 && (!ALWAYS_EXECUTED_IN (bb
)
1220 || (ALWAYS_EXECUTED_IN (bb
) != level
1221 && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1223 tree lhs
= gimple_assign_lhs (new_stmt
);
1224 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1225 SSA_NAME_ANTI_RANGE_P (lhs
) = 0;
1227 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1228 remove_phi_node (&bsi
, false);
1231 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1235 gimple stmt
= gsi_stmt (bsi
);
1237 lim_data
= get_lim_data (stmt
);
1238 if (lim_data
== NULL
)
1244 cost
= lim_data
->cost
;
1245 level
= lim_data
->tgt_loop
;
1246 clear_lim_data (stmt
);
1254 /* We do not really want to move conditionals out of the loop; we just
1255 placed it here to force its operands to be moved if necessary. */
1256 if (gimple_code (stmt
) == GIMPLE_COND
)
1259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1261 fprintf (dump_file
, "Moving statement\n");
1262 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1263 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1267 e
= loop_preheader_edge (level
);
1268 gcc_assert (!gimple_vdef (stmt
));
1269 if (gimple_vuse (stmt
))
1271 /* The new VUSE is the one from the virtual PHI in the loop
1272 header or the one already present. */
1274 for (gsi2
= gsi_start_phis (e
->dest
);
1275 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1277 gphi
*phi
= gsi2
.phi ();
1278 if (virtual_operand_p (gimple_phi_result (phi
)))
1280 gimple_set_vuse (stmt
, PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1285 gsi_remove (&bsi
, false);
1286 if (gimple_has_lhs (stmt
)
1287 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1288 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt
)))
1289 && (!ALWAYS_EXECUTED_IN (bb
)
1290 || !(ALWAYS_EXECUTED_IN (bb
) == level
1291 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1293 tree lhs
= gimple_get_lhs (stmt
);
1294 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1295 SSA_NAME_ANTI_RANGE_P (lhs
) = 0;
1297 /* In case this is a stmt that is not unconditionally executed
1298 when the target loop header is executed and the stmt may
1299 invoke undefined integer or pointer overflow rewrite it to
1300 unsigned arithmetic. */
1301 if (is_gimple_assign (stmt
)
1302 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
)))
1303 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt
)))
1304 && arith_code_with_undefined_signed_overflow
1305 (gimple_assign_rhs_code (stmt
))
1306 && (!ALWAYS_EXECUTED_IN (bb
)
1307 || !(ALWAYS_EXECUTED_IN (bb
) == level
1308 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1309 gsi_insert_seq_on_edge (e
, rewrite_to_defined_overflow (stmt
));
1311 gsi_insert_on_edge (e
, stmt
);
1315 /* Hoist the statements out of the loops prescribed by data stored in
1316 LIM_DATA structures associated with each statement.*/
1319 move_computations (void)
1321 move_computations_dom_walker
walker (CDI_DOMINATORS
);
1322 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
1324 gsi_commit_edge_inserts ();
1325 if (need_ssa_update_p (cfun
))
1326 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1328 return walker
.todo_
;
1331 /* Checks whether the statement defining variable *INDEX can be hoisted
1332 out of the loop passed in DATA. Callback for for_each_index. */
1335 may_move_till (tree ref
, tree
*index
, void *data
)
1337 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1339 /* If REF is an array reference, check also that the step and the lower
1340 bound is invariant in LOOP. */
1341 if (TREE_CODE (ref
) == ARRAY_REF
)
1343 tree step
= TREE_OPERAND (ref
, 3);
1344 tree lbound
= TREE_OPERAND (ref
, 2);
1346 max_loop
= outermost_invariant_loop (step
, loop
);
1350 max_loop
= outermost_invariant_loop (lbound
, loop
);
1355 max_loop
= outermost_invariant_loop (*index
, loop
);
1362 /* If OP is SSA NAME, force the statement that defines it to be
1363 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1366 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1371 || is_gimple_min_invariant (op
))
1374 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1376 stmt
= SSA_NAME_DEF_STMT (op
);
1377 if (gimple_nop_p (stmt
))
1380 set_level (stmt
, orig_loop
, loop
);
1383 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1384 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1390 struct loop
*orig_loop
;
1394 force_move_till (tree ref
, tree
*index
, void *data
)
1396 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1398 if (TREE_CODE (ref
) == ARRAY_REF
)
1400 tree step
= TREE_OPERAND (ref
, 3);
1401 tree lbound
= TREE_OPERAND (ref
, 2);
1403 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1404 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1407 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1412 /* A function to free the mem_ref object OBJ. */
1415 memref_free (struct im_mem_ref
*mem
)
1417 mem
->accesses_in_loop
.release ();
1420 /* Allocates and returns a memory reference description for MEM whose hash
1421 value is HASH and id is ID. */
1424 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1426 im_mem_ref
*ref
= XOBNEW (&mem_ref_obstack
, struct im_mem_ref
);
1427 ao_ref_init (&ref
->mem
, mem
);
1431 bitmap_initialize (&ref
->indep_loop
, &lim_bitmap_obstack
);
1432 bitmap_initialize (&ref
->dep_loop
, &lim_bitmap_obstack
);
1433 ref
->accesses_in_loop
.create (1);
1438 /* Records memory reference location *LOC in LOOP to the memory reference
1439 description REF. The reference occurs in statement STMT. */
1442 record_mem_ref_loc (im_mem_ref
*ref
, gimple stmt
, tree
*loc
)
1447 ref
->accesses_in_loop
.safe_push (aref
);
1450 /* Set the LOOP bit in REF stored bitmap and allocate that if
1451 necessary. Return whether a bit was changed. */
1454 set_ref_stored_in_loop (im_mem_ref
*ref
, struct loop
*loop
)
1457 ref
->stored
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1458 return bitmap_set_bit (ref
->stored
, loop
->num
);
1461 /* Marks reference REF as stored in LOOP. */
1464 mark_ref_stored (im_mem_ref
*ref
, struct loop
*loop
)
1466 while (loop
!= current_loops
->tree_root
1467 && set_ref_stored_in_loop (ref
, loop
))
1468 loop
= loop_outer (loop
);
1471 /* Gathers memory references in statement STMT in LOOP, storing the
1472 information about them in the memory_accesses structure. Marks
1473 the vops accessed through unrecognized statements there as
1477 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1486 if (!gimple_vuse (stmt
))
1489 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1492 /* We use the shared mem_ref for all unanalyzable refs. */
1493 id
= UNANALYZABLE_MEM_ID
;
1494 ref
= memory_accesses
.refs_list
[id
];
1495 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1497 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1498 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1500 is_stored
= gimple_vdef (stmt
);
1504 hash
= iterative_hash_expr (*mem
, 0);
1505 slot
= memory_accesses
.refs
->find_slot_with_hash (*mem
, hash
, INSERT
);
1513 id
= memory_accesses
.refs_list
.length ();
1514 ref
= mem_ref_alloc (*mem
, hash
, id
);
1515 memory_accesses
.refs_list
.safe_push (ref
);
1518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1520 fprintf (dump_file
, "Memory reference %u: ", id
);
1521 print_generic_expr (dump_file
, ref
->mem
.ref
, TDF_SLIM
);
1522 fprintf (dump_file
, "\n");
1526 record_mem_ref_loc (ref
, stmt
, mem
);
1528 bitmap_set_bit (&memory_accesses
.refs_in_loop
[loop
->num
], ref
->id
);
1531 bitmap_set_bit (&memory_accesses
.refs_stored_in_loop
[loop
->num
], ref
->id
);
1532 mark_ref_stored (ref
, loop
);
1537 static unsigned *bb_loop_postorder
;
1539 /* qsort sort function to sort blocks after their loop fathers postorder. */
1542 sort_bbs_in_loop_postorder_cmp (const void *bb1_
, const void *bb2_
)
1544 basic_block bb1
= *(basic_block
*)const_cast<void *>(bb1_
);
1545 basic_block bb2
= *(basic_block
*)const_cast<void *>(bb2_
);
1546 struct loop
*loop1
= bb1
->loop_father
;
1547 struct loop
*loop2
= bb2
->loop_father
;
1548 if (loop1
->num
== loop2
->num
)
1550 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1553 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1556 sort_locs_in_loop_postorder_cmp (const void *loc1_
, const void *loc2_
)
1558 mem_ref_loc
*loc1
= (mem_ref_loc
*)const_cast<void *>(loc1_
);
1559 mem_ref_loc
*loc2
= (mem_ref_loc
*)const_cast<void *>(loc2_
);
1560 struct loop
*loop1
= gimple_bb (loc1
->stmt
)->loop_father
;
1561 struct loop
*loop2
= gimple_bb (loc2
->stmt
)->loop_father
;
1562 if (loop1
->num
== loop2
->num
)
1564 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1567 /* Gathers memory references in loops. */
1570 analyze_memory_references (void)
1572 gimple_stmt_iterator bsi
;
1573 basic_block bb
, *bbs
;
1574 struct loop
*loop
, *outer
;
1577 /* Collect all basic-blocks in loops and sort them after their
1580 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
1581 FOR_EACH_BB_FN (bb
, cfun
)
1582 if (bb
->loop_father
!= current_loops
->tree_root
)
1585 qsort (bbs
, n
, sizeof (basic_block
), sort_bbs_in_loop_postorder_cmp
);
1587 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1588 That results in better locality for all the bitmaps. */
1589 for (i
= 0; i
< n
; ++i
)
1591 basic_block bb
= bbs
[i
];
1592 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1593 gather_mem_refs_stmt (bb
->loop_father
, gsi_stmt (bsi
));
1596 /* Sort the location list of gathered memory references after their
1597 loop postorder number. */
1599 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
1600 ref
->accesses_in_loop
.qsort (sort_locs_in_loop_postorder_cmp
);
1603 // free (bb_loop_postorder);
1605 /* Propagate the information about accessed memory references up
1606 the loop hierarchy. */
1607 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1609 /* Finalize the overall touched references (including subloops). */
1610 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1611 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1613 /* Propagate the information about accessed memory references up
1614 the loop hierarchy. */
1615 outer
= loop_outer (loop
);
1616 if (outer
== current_loops
->tree_root
)
1619 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1620 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1624 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1625 tree_to_aff_combination_expand. */
1628 mem_refs_may_alias_p (im_mem_ref
*mem1
, im_mem_ref
*mem2
,
1629 hash_map
<tree
, name_expansion
*> **ttae_cache
)
1631 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1632 object and their offset differ in such a way that the locations cannot
1633 overlap, then they cannot alias. */
1634 widest_int size1
, size2
;
1635 aff_tree off1
, off2
;
1637 /* Perform basic offset and type-based disambiguation. */
1638 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, true))
1641 /* The expansion of addresses may be a bit expensive, thus we only do
1642 the check at -O2 and higher optimization levels. */
1646 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1647 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1648 aff_combination_expand (&off1
, ttae_cache
);
1649 aff_combination_expand (&off2
, ttae_cache
);
1650 aff_combination_scale (&off1
, -1);
1651 aff_combination_add (&off2
, &off1
);
1653 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1659 /* Compare function for bsearch searching for reference locations
1663 find_ref_loc_in_loop_cmp (const void *loop_
, const void *loc_
)
1665 struct loop
*loop
= (struct loop
*)const_cast<void *>(loop_
);
1666 mem_ref_loc
*loc
= (mem_ref_loc
*)const_cast<void *>(loc_
);
1667 struct loop
*loc_loop
= gimple_bb (loc
->stmt
)->loop_father
;
1668 if (loop
->num
== loc_loop
->num
1669 || flow_loop_nested_p (loop
, loc_loop
))
1671 return (bb_loop_postorder
[loop
->num
] < bb_loop_postorder
[loc_loop
->num
]
1675 /* Iterates over all locations of REF in LOOP and its subloops calling
1676 fn.operator() with the location as argument. When that operator
1677 returns true the iteration is stopped and true is returned.
1678 Otherwise false is returned. */
1680 template <typename FN
>
1682 for_all_locs_in_loop (struct loop
*loop
, im_mem_ref
*ref
, FN fn
)
1687 /* Search for the cluster of locs in the accesses_in_loop vector
1688 which is sorted after postorder index of the loop father. */
1689 loc
= ref
->accesses_in_loop
.bsearch (loop
, find_ref_loc_in_loop_cmp
);
1693 /* We have found one location inside loop or its sub-loops. Iterate
1694 both forward and backward to cover the whole cluster. */
1695 i
= loc
- ref
->accesses_in_loop
.address ();
1699 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1700 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1705 for (i
= loc
- ref
->accesses_in_loop
.address ();
1706 i
< ref
->accesses_in_loop
.length (); ++i
)
1708 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1709 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1718 /* Rewrites location LOC by TMP_VAR. */
1720 struct rewrite_mem_ref_loc
1722 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1723 bool operator () (mem_ref_loc
*loc
);
1728 rewrite_mem_ref_loc::operator () (mem_ref_loc
*loc
)
1730 *loc
->ref
= tmp_var
;
1731 update_stmt (loc
->stmt
);
1735 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1738 rewrite_mem_refs (struct loop
*loop
, im_mem_ref
*ref
, tree tmp_var
)
1740 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1743 /* Stores the first reference location in LOCP. */
1745 struct first_mem_ref_loc_1
1747 first_mem_ref_loc_1 (mem_ref_loc
**locp_
) : locp (locp_
) {}
1748 bool operator () (mem_ref_loc
*loc
);
1753 first_mem_ref_loc_1::operator () (mem_ref_loc
*loc
)
1759 /* Returns the first reference location to REF in LOOP. */
1761 static mem_ref_loc
*
1762 first_mem_ref_loc (struct loop
*loop
, im_mem_ref
*ref
)
1764 mem_ref_loc
*locp
= NULL
;
1765 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1769 struct prev_flag_edges
{
1770 /* Edge to insert new flag comparison code. */
1771 edge append_cond_position
;
1773 /* Edge for fall through from previous flag comparison. */
1774 edge last_cond_fallthru
;
1777 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1780 The store is only done if MEM has changed. We do this so no
1781 changes to MEM occur on code paths that did not originally store
1784 The common case for execute_sm will transform:
1804 This function will generate:
1823 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
)
1825 basic_block new_bb
, then_bb
, old_dest
;
1826 bool loop_has_only_one_exit
;
1827 edge then_old_edge
, orig_ex
= ex
;
1828 gimple_stmt_iterator gsi
;
1830 struct prev_flag_edges
*prev_edges
= (struct prev_flag_edges
*) ex
->aux
;
1831 bool irr
= ex
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1833 /* ?? Insert store after previous store if applicable. See note
1836 ex
= prev_edges
->append_cond_position
;
1838 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1840 if (loop_has_only_one_exit
)
1841 ex
= split_block_after_labels (ex
->dest
);
1843 old_dest
= ex
->dest
;
1844 new_bb
= split_edge (ex
);
1845 then_bb
= create_empty_bb (new_bb
);
1847 then_bb
->flags
= BB_IRREDUCIBLE_LOOP
;
1848 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1850 gsi
= gsi_start_bb (new_bb
);
1851 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1852 NULL_TREE
, NULL_TREE
);
1853 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1855 gsi
= gsi_start_bb (then_bb
);
1856 /* Insert actual store. */
1857 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1858 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1860 make_edge (new_bb
, then_bb
,
1861 EDGE_TRUE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1862 make_edge (new_bb
, old_dest
,
1863 EDGE_FALSE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1864 then_old_edge
= make_edge (then_bb
, old_dest
,
1865 EDGE_FALLTHRU
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1867 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
1871 basic_block prevbb
= prev_edges
->last_cond_fallthru
->src
;
1872 redirect_edge_succ (prev_edges
->last_cond_fallthru
, new_bb
);
1873 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
1874 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
1875 recompute_dominator (CDI_DOMINATORS
, old_dest
));
1878 /* ?? Because stores may alias, they must happen in the exact
1879 sequence they originally happened. Save the position right after
1880 the (_lsm) store we just created so we can continue appending after
1881 it and maintain the original order. */
1883 struct prev_flag_edges
*p
;
1886 orig_ex
->aux
= NULL
;
1887 alloc_aux_for_edge (orig_ex
, sizeof (struct prev_flag_edges
));
1888 p
= (struct prev_flag_edges
*) orig_ex
->aux
;
1889 p
->append_cond_position
= then_old_edge
;
1890 p
->last_cond_fallthru
= find_edge (new_bb
, old_dest
);
1891 orig_ex
->aux
= (void *) p
;
1894 if (!loop_has_only_one_exit
)
1895 for (gphi_iterator gpi
= gsi_start_phis (old_dest
);
1896 !gsi_end_p (gpi
); gsi_next (&gpi
))
1898 gphi
*phi
= gpi
.phi ();
1901 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1902 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
1904 tree arg
= gimple_phi_arg_def (phi
, i
);
1905 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
1909 /* Remove the original fall through edge. This was the
1910 single_succ_edge (new_bb). */
1911 EDGE_SUCC (new_bb
, 0)->flags
&= ~EDGE_FALLTHRU
;
1914 /* When REF is set on the location, set flag indicating the store. */
1916 struct sm_set_flag_if_changed
1918 sm_set_flag_if_changed (tree flag_
) : flag (flag_
) {}
1919 bool operator () (mem_ref_loc
*loc
);
1924 sm_set_flag_if_changed::operator () (mem_ref_loc
*loc
)
1926 /* Only set the flag for writes. */
1927 if (is_gimple_assign (loc
->stmt
)
1928 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
1930 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
1931 gimple stmt
= gimple_build_assign (flag
, boolean_true_node
);
1932 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1937 /* Helper function for execute_sm. On every location where REF is
1938 set, set an appropriate flag indicating the store. */
1941 execute_sm_if_changed_flag_set (struct loop
*loop
, im_mem_ref
*ref
)
1944 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0, "_flag");
1945 flag
= create_tmp_reg (boolean_type_node
, str
);
1946 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
));
1950 /* Executes store motion of memory reference REF from LOOP.
1951 Exits from the LOOP are stored in EXITS. The initialization of the
1952 temporary variable is put to the preheader of the loop, and assignments
1953 to the reference from the temporary variable are emitted to exits. */
1956 execute_sm (struct loop
*loop
, vec
<edge
> exits
, im_mem_ref
*ref
)
1958 tree tmp_var
, store_flag
= NULL_TREE
;
1961 struct fmt_data fmt_data
;
1963 struct lim_aux_data
*lim_data
;
1964 bool multi_threaded_model_p
= false;
1965 gimple_stmt_iterator gsi
;
1967 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1969 fprintf (dump_file
, "Executing store motion of ");
1970 print_generic_expr (dump_file
, ref
->mem
.ref
, 0);
1971 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1974 tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
1975 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
1977 fmt_data
.loop
= loop
;
1978 fmt_data
.orig_loop
= loop
;
1979 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
1981 if (bb_in_transaction (loop_preheader_edge (loop
)->src
)
1982 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
))
1983 multi_threaded_model_p
= true;
1985 if (multi_threaded_model_p
)
1986 store_flag
= execute_sm_if_changed_flag_set (loop
, ref
);
1988 rewrite_mem_refs (loop
, ref
, tmp_var
);
1990 /* Emit the load code on a random exit edge or into the latch if
1991 the loop does not exit, so that we are sure it will be processed
1992 by move_computations after all dependencies. */
1993 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
1995 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
1996 load altogether, since the store is predicated by a flag. We
1997 could, do the load only if it was originally in the loop. */
1998 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
.ref
));
1999 lim_data
= init_lim_data (load
);
2000 lim_data
->max_loop
= loop
;
2001 lim_data
->tgt_loop
= loop
;
2002 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2004 if (multi_threaded_model_p
)
2006 load
= gimple_build_assign (store_flag
, boolean_false_node
);
2007 lim_data
= init_lim_data (load
);
2008 lim_data
->max_loop
= loop
;
2009 lim_data
->tgt_loop
= loop
;
2010 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2013 /* Sink the store to every exit from the loop. */
2014 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2015 if (!multi_threaded_model_p
)
2018 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
), tmp_var
);
2019 gsi_insert_on_edge (ex
, store
);
2022 execute_sm_if_changed (ex
, ref
->mem
.ref
, tmp_var
, store_flag
);
2025 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2026 edges of the LOOP. */
2029 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2036 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2038 ref
= memory_accesses
.refs_list
[i
];
2039 execute_sm (loop
, exits
, ref
);
2043 struct ref_always_accessed
2045 ref_always_accessed (struct loop
*loop_
, bool stored_p_
)
2046 : loop (loop_
), stored_p (stored_p_
) {}
2047 bool operator () (mem_ref_loc
*loc
);
2053 ref_always_accessed::operator () (mem_ref_loc
*loc
)
2055 struct loop
*must_exec
;
2057 if (!get_lim_data (loc
->stmt
))
2060 /* If we require an always executed store make sure the statement
2061 stores to the reference. */
2064 tree lhs
= gimple_get_lhs (loc
->stmt
);
2066 || lhs
!= *loc
->ref
)
2070 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2074 if (must_exec
== loop
2075 || flow_loop_nested_p (must_exec
, loop
))
2081 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2082 make sure REF is always stored to in LOOP. */
2085 ref_always_accessed_p (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2087 return for_all_locs_in_loop (loop
, ref
,
2088 ref_always_accessed (loop
, stored_p
));
2091 /* Returns true if REF1 and REF2 are independent. */
2094 refs_independent_p (im_mem_ref
*ref1
, im_mem_ref
*ref2
)
2099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2100 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2101 ref1
->id
, ref2
->id
);
2103 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
))
2105 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2106 fprintf (dump_file
, "dependent.\n");
2111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2112 fprintf (dump_file
, "independent.\n");
2117 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2118 and its super-loops. */
2121 record_dep_loop (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2123 /* We can propagate dependent-in-loop bits up the loop
2124 hierarchy to all outer loops. */
2125 while (loop
!= current_loops
->tree_root
2126 && bitmap_set_bit (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2127 loop
= loop_outer (loop
);
2130 /* Returns true if REF is independent on all other memory references in
2134 ref_indep_loop_p_1 (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2136 bitmap refs_to_check
;
2142 refs_to_check
= &memory_accesses
.refs_in_loop
[loop
->num
];
2144 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2146 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2149 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2151 aref
= memory_accesses
.refs_list
[i
];
2152 if (!refs_independent_p (ref
, aref
))
2159 /* Returns true if REF is independent on all other memory references in
2160 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2163 ref_indep_loop_p_2 (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2165 stored_p
|= (ref
->stored
&& bitmap_bit_p (ref
->stored
, loop
->num
));
2167 if (bitmap_bit_p (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2169 if (bitmap_bit_p (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2172 struct loop
*inner
= loop
->inner
;
2175 if (!ref_indep_loop_p_2 (inner
, ref
, stored_p
))
2177 inner
= inner
->next
;
2180 bool indep_p
= ref_indep_loop_p_1 (loop
, ref
, stored_p
);
2182 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2183 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2184 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2186 /* Record the computed result in the cache. */
2189 if (bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
))
2192 /* If it's independend against all refs then it's independent
2193 against stores, too. */
2194 bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, false));
2199 record_dep_loop (loop
, ref
, stored_p
);
2202 /* If it's dependent against stores it's dependent against
2204 record_dep_loop (loop
, ref
, true);
2211 /* Returns true if REF is independent on all other memory references in
2215 ref_indep_loop_p (struct loop
*loop
, im_mem_ref
*ref
)
2217 gcc_checking_assert (MEM_ANALYZABLE (ref
));
2219 return ref_indep_loop_p_2 (loop
, ref
, false);
2222 /* Returns true if we can perform store motion of REF from LOOP. */
2225 can_sm_ref_p (struct loop
*loop
, im_mem_ref
*ref
)
2229 /* Can't hoist unanalyzable refs. */
2230 if (!MEM_ANALYZABLE (ref
))
2233 /* It should be movable. */
2234 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2235 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2236 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2239 /* If it can throw fail, we do not properly update EH info. */
2240 if (tree_could_throw_p (ref
->mem
.ref
))
2243 /* If it can trap, it must be always executed in LOOP.
2244 Readonly memory locations may trap when storing to them, but
2245 tree_could_trap_p is a predicate for rvalues, so check that
2247 base
= get_base_address (ref
->mem
.ref
);
2248 if ((tree_could_trap_p (ref
->mem
.ref
)
2249 || (DECL_P (base
) && TREE_READONLY (base
)))
2250 && !ref_always_accessed_p (loop
, ref
, true))
2253 /* And it must be independent on all other memory references
2255 if (!ref_indep_loop_p (loop
, ref
))
2261 /* Marks the references in LOOP for that store motion should be performed
2262 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2263 motion was performed in one of the outer loops. */
2266 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2268 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2273 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2275 ref
= memory_accesses
.refs_list
[i
];
2276 if (can_sm_ref_p (loop
, ref
))
2277 bitmap_set_bit (refs_to_sm
, i
);
2281 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2282 for a store motion optimization (i.e. whether we can insert statement
2286 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2292 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2293 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2299 /* Try to perform store motion for all memory references modified inside
2300 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2301 store motion was executed in one of the outer loops. */
2304 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2306 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2307 struct loop
*subloop
;
2308 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2310 if (loop_suitable_for_sm (loop
, exits
))
2312 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2313 hoist_memory_references (loop
, sm_in_loop
, exits
);
2317 bitmap_ior_into (sm_executed
, sm_in_loop
);
2318 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2319 store_motion_loop (subloop
, sm_executed
);
2320 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2321 BITMAP_FREE (sm_in_loop
);
2324 /* Try to perform store motion for all memory references modified inside
2331 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2333 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2334 store_motion_loop (loop
, sm_executed
);
2336 BITMAP_FREE (sm_executed
);
2337 gsi_commit_edge_inserts ();
2340 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2341 for each such basic block bb records the outermost loop for that execution
2342 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2343 blocks that contain a nonpure call. */
2346 fill_always_executed_in_1 (struct loop
*loop
, sbitmap contains_call
)
2348 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2351 struct loop
*inn_loop
= loop
;
2353 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2355 bbs
= get_loop_body_in_dom_order (loop
);
2357 for (i
= 0; i
< loop
->num_nodes
; i
++)
2362 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2365 if (bitmap_bit_p (contains_call
, bb
->index
))
2368 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2369 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2374 /* A loop might be infinite (TODO use simple loop analysis
2375 to disprove this if possible). */
2376 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2379 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2382 if (bb
->loop_father
->header
== bb
)
2384 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2387 /* In a loop that is always entered we may proceed anyway.
2388 But record that we entered it and stop once we leave it. */
2389 inn_loop
= bb
->loop_father
;
2395 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2396 if (last
== loop
->header
)
2398 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2404 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2405 fill_always_executed_in_1 (loop
, contains_call
);
2408 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2409 for each such basic block bb records the outermost loop for that execution
2410 of its header implies execution of bb. */
2413 fill_always_executed_in (void)
2415 sbitmap contains_call
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
2419 bitmap_clear (contains_call
);
2420 FOR_EACH_BB_FN (bb
, cfun
)
2422 gimple_stmt_iterator gsi
;
2423 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2425 if (nonpure_call_p (gsi_stmt (gsi
)))
2429 if (!gsi_end_p (gsi
))
2430 bitmap_set_bit (contains_call
, bb
->index
);
2433 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2434 fill_always_executed_in_1 (loop
, contains_call
);
2436 sbitmap_free (contains_call
);
2440 /* Compute the global information needed by the loop invariant motion pass. */
2443 tree_ssa_lim_initialize (void)
2448 bitmap_obstack_initialize (&lim_bitmap_obstack
);
2449 gcc_obstack_init (&mem_ref_obstack
);
2450 lim_aux_data_map
= new hash_map
<gimple
, lim_aux_data
*>;
2453 compute_transaction_bits ();
2455 alloc_aux_for_edges (0);
2457 memory_accesses
.refs
= new hash_table
<mem_ref_hasher
> (100);
2458 memory_accesses
.refs_list
.create (100);
2459 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2460 memory_accesses
.refs_list
.quick_push
2461 (mem_ref_alloc (error_mark_node
, 0, UNANALYZABLE_MEM_ID
));
2463 memory_accesses
.refs_in_loop
.create (number_of_loops (cfun
));
2464 memory_accesses
.refs_in_loop
.quick_grow (number_of_loops (cfun
));
2465 memory_accesses
.refs_stored_in_loop
.create (number_of_loops (cfun
));
2466 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2467 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops (cfun
));
2468 memory_accesses
.all_refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2470 for (i
= 0; i
< number_of_loops (cfun
); i
++)
2472 bitmap_initialize (&memory_accesses
.refs_in_loop
[i
],
2473 &lim_bitmap_obstack
);
2474 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
2475 &lim_bitmap_obstack
);
2476 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
2477 &lim_bitmap_obstack
);
2480 memory_accesses
.ttae_cache
= NULL
;
2482 /* Initialize bb_loop_postorder with a mapping from loop->num to
2483 its postorder index. */
2485 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops (cfun
));
2486 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2487 bb_loop_postorder
[loop
->num
] = i
++;
2490 /* Cleans up after the invariant motion pass. */
2493 tree_ssa_lim_finalize (void)
2499 free_aux_for_edges ();
2501 FOR_EACH_BB_FN (bb
, cfun
)
2502 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2504 bitmap_obstack_release (&lim_bitmap_obstack
);
2505 delete lim_aux_data_map
;
2507 delete memory_accesses
.refs
;
2508 memory_accesses
.refs
= NULL
;
2510 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
2512 memory_accesses
.refs_list
.release ();
2513 obstack_free (&mem_ref_obstack
, NULL
);
2515 memory_accesses
.refs_in_loop
.release ();
2516 memory_accesses
.refs_stored_in_loop
.release ();
2517 memory_accesses
.all_refs_stored_in_loop
.release ();
2519 if (memory_accesses
.ttae_cache
)
2520 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
2522 free (bb_loop_postorder
);
2525 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2526 i.e. those that are likely to be win regardless of the register pressure. */
2533 tree_ssa_lim_initialize ();
2535 /* Gathers information about memory accesses in the loops. */
2536 analyze_memory_references ();
2538 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2539 fill_always_executed_in ();
2541 /* For each statement determine the outermost loop in that it is
2542 invariant and cost for computing the invariant. */
2543 invariantness_dom_walker (CDI_DOMINATORS
)
2544 .walk (cfun
->cfg
->x_entry_block_ptr
);
2546 /* Execute store motion. Force the necessary invariants to be moved
2547 out of the loops as well. */
2550 /* Move the expressions that are expensive enough. */
2551 todo
= move_computations ();
2553 tree_ssa_lim_finalize ();
2558 /* Loop invariant motion pass. */
2562 const pass_data pass_data_lim
=
2564 GIMPLE_PASS
, /* type */
2566 OPTGROUP_LOOP
, /* optinfo_flags */
2568 PROP_cfg
, /* properties_required */
2569 0, /* properties_provided */
2570 0, /* properties_destroyed */
2571 0, /* todo_flags_start */
2572 0, /* todo_flags_finish */
2575 class pass_lim
: public gimple_opt_pass
2578 pass_lim (gcc::context
*ctxt
)
2579 : gimple_opt_pass (pass_data_lim
, ctxt
)
2582 /* opt_pass methods: */
2583 opt_pass
* clone () { return new pass_lim (m_ctxt
); }
2584 virtual bool gate (function
*) { return flag_tree_loop_im
!= 0; }
2585 virtual unsigned int execute (function
*);
2587 }; // class pass_lim
2590 pass_lim::execute (function
*fun
)
2592 if (number_of_loops (fun
) <= 1)
2595 return tree_ssa_lim ();
2601 make_pass_lim (gcc::context
*ctxt
)
2603 return new pass_lim (ctxt
);