1 /* Loop invariant motion.
2 Copyright (C) 2003-2019 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 "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
34 #include "gimple-iterator.h"
36 #include "tree-ssa-loop-manip.h"
37 #include "tree-ssa-loop.h"
38 #include "tree-into-ssa.h"
42 #include "tree-affine.h"
43 #include "tree-ssa-propagate.h"
44 #include "trans-mem.h"
45 #include "gimple-fold.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-ssa-loop-niter.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 unsigned ref
; /* The simple_mem_ref in this stmt or 0. */
94 vec
<gimple
*> depends
; /* Vector of statements that must be also
95 hoisted out of the loop when this statement
96 is hoisted; i.e. those that define the
97 operands of the statement and are inside of
101 /* Maps statements to their lim_aux_data. */
103 static hash_map
<gimple
*, lim_aux_data
*> *lim_aux_data_map
;
105 /* Description of a memory reference location. */
109 tree
*ref
; /* The reference itself. */
110 gimple
*stmt
; /* The statement in that it occurs. */
114 /* Description of a memory reference. */
118 unsigned id
: 31; /* ID assigned to the memory reference
119 (its index in memory_accesses.refs_list) */
120 unsigned ref_canonical
: 1; /* Whether mem.ref was canonicalized. */
121 hashval_t hash
; /* Its hash value. */
123 /* The memory access itself and associated caching of alias-oracle
127 bitmap stored
; /* The set of loops in that this memory location
129 vec
<mem_ref_loc
> accesses_in_loop
;
130 /* The locations of the accesses. Vector
131 indexed by the loop number. */
133 /* The following sets are computed on demand. We keep both set and
134 its complement, so that we know whether the information was
135 already computed or not. */
136 bitmap_head indep_loop
; /* The set of loops in that the memory
137 reference is independent, meaning:
138 If it is stored in the loop, this store
139 is independent on all other loads and
141 If it is only loaded, then it is independent
142 on all stores in the loop. */
143 bitmap_head dep_loop
; /* The complement of INDEP_LOOP. */
146 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
147 to record (in)dependence against stores in the loop and its subloops, the
148 second to record (in)dependence against all references in the loop
150 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
152 /* Mem_ref hashtable helpers. */
154 struct mem_ref_hasher
: nofree_ptr_hash
<im_mem_ref
>
156 typedef ao_ref
*compare_type
;
157 static inline hashval_t
hash (const im_mem_ref
*);
158 static inline bool equal (const im_mem_ref
*, const ao_ref
*);
161 /* A hash function for struct im_mem_ref object OBJ. */
164 mem_ref_hasher::hash (const im_mem_ref
*mem
)
169 /* An equality function for struct im_mem_ref object MEM1 with
170 memory reference OBJ2. */
173 mem_ref_hasher::equal (const im_mem_ref
*mem1
, const ao_ref
*obj2
)
175 if (obj2
->max_size_known_p ())
176 return (operand_equal_p (mem1
->mem
.base
, obj2
->base
, 0)
177 && known_eq (mem1
->mem
.offset
, obj2
->offset
)
178 && known_eq (mem1
->mem
.size
, obj2
->size
)
179 && known_eq (mem1
->mem
.max_size
, obj2
->max_size
)
180 && mem1
->mem
.volatile_p
== obj2
->volatile_p
181 && mem1
->mem
.ref_alias_set
== obj2
->ref_alias_set
182 && types_compatible_p (TREE_TYPE (mem1
->mem
.ref
),
183 TREE_TYPE (obj2
->ref
)));
185 return operand_equal_p (mem1
->mem
.ref
, obj2
->ref
, 0);
189 /* Description of memory accesses in loops. */
193 /* The hash table of memory references accessed in loops. */
194 hash_table
<mem_ref_hasher
> *refs
;
196 /* The list of memory references. */
197 vec
<im_mem_ref
*> refs_list
;
199 /* The set of memory references accessed in each loop. */
200 vec
<bitmap_head
> refs_in_loop
;
202 /* The set of memory references stored in each loop. */
203 vec
<bitmap_head
> refs_stored_in_loop
;
205 /* The set of memory references stored in each loop, including subloops . */
206 vec
<bitmap_head
> all_refs_stored_in_loop
;
208 /* Cache for expanding memory addresses. */
209 hash_map
<tree
, name_expansion
*> *ttae_cache
;
212 /* Obstack for the bitmaps in the above data structures. */
213 static bitmap_obstack lim_bitmap_obstack
;
214 static obstack mem_ref_obstack
;
216 static bool ref_indep_loop_p (struct loop
*, im_mem_ref
*);
217 static bool ref_always_accessed_p (struct loop
*, im_mem_ref
*, bool);
219 /* Minimum cost of an expensive expression. */
220 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
222 /* The outermost loop for which execution of the header guarantees that the
223 block will be executed. */
224 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
225 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
227 /* ID of the shared unanalyzable mem. */
228 #define UNANALYZABLE_MEM_ID 0
230 /* Whether the reference was analyzable. */
231 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
233 static struct lim_aux_data
*
234 init_lim_data (gimple
*stmt
)
236 lim_aux_data
*p
= XCNEW (struct lim_aux_data
);
237 lim_aux_data_map
->put (stmt
, p
);
242 static struct lim_aux_data
*
243 get_lim_data (gimple
*stmt
)
245 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
252 /* Releases the memory occupied by DATA. */
255 free_lim_aux_data (struct lim_aux_data
*data
)
257 data
->depends
.release ();
262 clear_lim_data (gimple
*stmt
)
264 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
268 free_lim_aux_data (*p
);
273 /* The possibilities of statement movement. */
276 MOVE_IMPOSSIBLE
, /* No movement -- side effect expression. */
277 MOVE_PRESERVE_EXECUTION
, /* Must not cause the non-executed statement
278 become executed -- memory accesses, ... */
279 MOVE_POSSIBLE
/* Unlimited movement. */
283 /* If it is possible to hoist the statement STMT unconditionally,
284 returns MOVE_POSSIBLE.
285 If it is possible to hoist the statement STMT, but we must avoid making
286 it executed if it would not be executed in the original program (e.g.
287 because it may trap), return MOVE_PRESERVE_EXECUTION.
288 Otherwise return MOVE_IMPOSSIBLE. */
291 movement_possibility (gimple
*stmt
)
294 enum move_pos ret
= MOVE_POSSIBLE
;
296 if (flag_unswitch_loops
297 && gimple_code (stmt
) == GIMPLE_COND
)
299 /* If we perform unswitching, force the operands of the invariant
300 condition to be moved out of the loop. */
301 return MOVE_POSSIBLE
;
304 if (gimple_code (stmt
) == GIMPLE_PHI
305 && gimple_phi_num_args (stmt
) <= 2
306 && !virtual_operand_p (gimple_phi_result (stmt
))
307 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
308 return MOVE_POSSIBLE
;
310 if (gimple_get_lhs (stmt
) == NULL_TREE
)
311 return MOVE_IMPOSSIBLE
;
313 if (gimple_vdef (stmt
))
314 return MOVE_IMPOSSIBLE
;
316 if (stmt_ends_bb_p (stmt
)
317 || gimple_has_volatile_ops (stmt
)
318 || gimple_has_side_effects (stmt
)
319 || stmt_could_throw_p (cfun
, stmt
))
320 return MOVE_IMPOSSIBLE
;
322 if (is_gimple_call (stmt
))
324 /* While pure or const call is guaranteed to have no side effects, we
325 cannot move it arbitrarily. Consider code like
327 char *s = something ();
337 Here the strlen call cannot be moved out of the loop, even though
338 s is invariant. In addition to possibly creating a call with
339 invalid arguments, moving out a function call that is not executed
340 may cause performance regressions in case the call is costly and
341 not executed at all. */
342 ret
= MOVE_PRESERVE_EXECUTION
;
343 lhs
= gimple_call_lhs (stmt
);
345 else if (is_gimple_assign (stmt
))
346 lhs
= gimple_assign_lhs (stmt
);
348 return MOVE_IMPOSSIBLE
;
350 if (TREE_CODE (lhs
) == SSA_NAME
351 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
352 return MOVE_IMPOSSIBLE
;
354 if (TREE_CODE (lhs
) != SSA_NAME
355 || gimple_could_trap_p (stmt
))
356 return MOVE_PRESERVE_EXECUTION
;
358 /* Non local loads in a transaction cannot be hoisted out. Well,
359 unless the load happens on every path out of the loop, but we
360 don't take this into account yet. */
362 && gimple_in_transaction (stmt
)
363 && gimple_assign_single_p (stmt
))
365 tree rhs
= gimple_assign_rhs1 (stmt
);
366 if (DECL_P (rhs
) && is_global_var (rhs
))
370 fprintf (dump_file
, "Cannot hoist conditional load of ");
371 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
372 fprintf (dump_file
, " because it is in a transaction.\n");
374 return MOVE_IMPOSSIBLE
;
381 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
382 loop to that we could move the expression using DEF if it did not have
383 other operands, i.e. the outermost loop enclosing LOOP in that the value
384 of DEF is invariant. */
387 outermost_invariant_loop (tree def
, struct loop
*loop
)
391 struct loop
*max_loop
;
392 struct lim_aux_data
*lim_data
;
395 return superloop_at_depth (loop
, 1);
397 if (TREE_CODE (def
) != SSA_NAME
)
399 gcc_assert (is_gimple_min_invariant (def
));
400 return superloop_at_depth (loop
, 1);
403 def_stmt
= SSA_NAME_DEF_STMT (def
);
404 def_bb
= gimple_bb (def_stmt
);
406 return superloop_at_depth (loop
, 1);
408 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
410 lim_data
= get_lim_data (def_stmt
);
411 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
412 max_loop
= find_common_loop (max_loop
,
413 loop_outer (lim_data
->max_loop
));
414 if (max_loop
== loop
)
416 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
421 /* DATA is a structure containing information associated with a statement
422 inside LOOP. DEF is one of the operands of this statement.
424 Find the outermost loop enclosing LOOP in that value of DEF is invariant
425 and record this in DATA->max_loop field. If DEF itself is defined inside
426 this loop as well (i.e. we need to hoist it out of the loop if we want
427 to hoist the statement represented by DATA), record the statement in that
428 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
429 add the cost of the computation of DEF to the DATA->cost.
431 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
434 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
437 gimple
*def_stmt
= SSA_NAME_DEF_STMT (def
);
438 basic_block def_bb
= gimple_bb (def_stmt
);
439 struct loop
*max_loop
;
440 struct lim_aux_data
*def_data
;
445 max_loop
= outermost_invariant_loop (def
, loop
);
449 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
450 data
->max_loop
= max_loop
;
452 def_data
= get_lim_data (def_stmt
);
457 /* Only add the cost if the statement defining DEF is inside LOOP,
458 i.e. if it is likely that by moving the invariants dependent
459 on it, we will be able to avoid creating a new register for
460 it (since it will be only used in these dependent invariants). */
461 && def_bb
->loop_father
== loop
)
462 data
->cost
+= def_data
->cost
;
464 data
->depends
.safe_push (def_stmt
);
469 /* Returns an estimate for a cost of statement STMT. The values here
470 are just ad-hoc constants, similar to costs for inlining. */
473 stmt_cost (gimple
*stmt
)
475 /* Always try to create possibilities for unswitching. */
476 if (gimple_code (stmt
) == GIMPLE_COND
477 || gimple_code (stmt
) == GIMPLE_PHI
)
478 return LIM_EXPENSIVE
;
480 /* We should be hoisting calls if possible. */
481 if (is_gimple_call (stmt
))
485 /* Unless the call is a builtin_constant_p; this always folds to a
486 constant, so moving it is useless. */
487 fndecl
= gimple_call_fndecl (stmt
);
488 if (fndecl
&& fndecl_built_in_p (fndecl
, BUILT_IN_CONSTANT_P
))
491 return LIM_EXPENSIVE
;
494 /* Hoisting memory references out should almost surely be a win. */
495 if (gimple_references_memory_p (stmt
))
496 return LIM_EXPENSIVE
;
498 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
501 switch (gimple_assign_rhs_code (stmt
))
504 case WIDEN_MULT_EXPR
:
505 case WIDEN_MULT_PLUS_EXPR
:
506 case WIDEN_MULT_MINUS_EXPR
:
518 /* Division and multiplication are usually expensive. */
519 return LIM_EXPENSIVE
;
523 case WIDEN_LSHIFT_EXPR
:
526 /* Shifts and rotates are usually expensive. */
527 return LIM_EXPENSIVE
;
530 /* Make vector construction cost proportional to the number
532 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
536 /* Whether or not something is wrapped inside a PAREN_EXPR
537 should not change move cost. Nor should an intermediate
538 unpropagated SSA name copy. */
546 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
547 REF is independent. If REF is not independent in LOOP, NULL is returned
551 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, im_mem_ref
*ref
)
555 if (ref
->stored
&& bitmap_bit_p (ref
->stored
, loop
->num
))
560 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
561 if ((!ref
->stored
|| !bitmap_bit_p (ref
->stored
, aloop
->num
))
562 && ref_indep_loop_p (aloop
, ref
))
565 if (ref_indep_loop_p (loop
, ref
))
571 /* If there is a simple load or store to a memory reference in STMT, returns
572 the location of the memory reference, and sets IS_STORE according to whether
573 it is a store or load. Otherwise, returns NULL. */
576 simple_mem_ref_in_stmt (gimple
*stmt
, bool *is_store
)
580 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
581 if (!gimple_assign_single_p (stmt
))
584 lhs
= gimple_assign_lhs_ptr (stmt
);
585 rhs
= gimple_assign_rhs1_ptr (stmt
);
587 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
592 else if (gimple_vdef (stmt
)
593 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
602 /* From a controlling predicate in DOM determine the arguments from
603 the PHI node PHI that are chosen if the predicate evaluates to
604 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
605 they are non-NULL. Returns true if the arguments can be determined,
606 else return false. */
609 extract_true_false_args_from_phi (basic_block dom
, gphi
*phi
,
610 tree
*true_arg_p
, tree
*false_arg_p
)
613 if (! extract_true_false_controlled_edges (dom
, gimple_bb (phi
),
618 *true_arg_p
= PHI_ARG_DEF (phi
, te
->dest_idx
);
620 *false_arg_p
= PHI_ARG_DEF (phi
, fe
->dest_idx
);
625 /* Determine the outermost loop to that it is possible to hoist a statement
626 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
627 the outermost loop in that the value computed by STMT is invariant.
628 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
629 we preserve the fact whether STMT is executed. It also fills other related
630 information to LIM_DATA (STMT).
632 The function returns false if STMT cannot be hoisted outside of the loop it
633 is defined in, and true otherwise. */
636 determine_max_movement (gimple
*stmt
, bool must_preserve_exec
)
638 basic_block bb
= gimple_bb (stmt
);
639 struct loop
*loop
= bb
->loop_father
;
641 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
645 if (must_preserve_exec
)
646 level
= ALWAYS_EXECUTED_IN (bb
);
648 level
= superloop_at_depth (loop
, 1);
649 lim_data
->max_loop
= level
;
651 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
654 unsigned min_cost
= UINT_MAX
;
655 unsigned total_cost
= 0;
656 struct lim_aux_data
*def_data
;
658 /* We will end up promoting dependencies to be unconditionally
659 evaluated. For this reason the PHI cost (and thus the
660 cost we remove from the loop by doing the invariant motion)
661 is that of the cheapest PHI argument dependency chain. */
662 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
664 val
= USE_FROM_PTR (use_p
);
666 if (TREE_CODE (val
) != SSA_NAME
)
668 /* Assign const 1 to constants. */
669 min_cost
= MIN (min_cost
, 1);
673 if (!add_dependency (val
, lim_data
, loop
, false))
676 gimple
*def_stmt
= SSA_NAME_DEF_STMT (val
);
677 if (gimple_bb (def_stmt
)
678 && gimple_bb (def_stmt
)->loop_father
== loop
)
680 def_data
= get_lim_data (def_stmt
);
683 min_cost
= MIN (min_cost
, def_data
->cost
);
684 total_cost
+= def_data
->cost
;
689 min_cost
= MIN (min_cost
, total_cost
);
690 lim_data
->cost
+= min_cost
;
692 if (gimple_phi_num_args (phi
) > 1)
694 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
696 if (gsi_end_p (gsi_last_bb (dom
)))
698 cond
= gsi_stmt (gsi_last_bb (dom
));
699 if (gimple_code (cond
) != GIMPLE_COND
)
701 /* Verify that this is an extended form of a diamond and
702 the PHI arguments are completely controlled by the
704 if (!extract_true_false_args_from_phi (dom
, phi
, NULL
, NULL
))
707 /* Fold in dependencies and cost of the condition. */
708 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
710 if (!add_dependency (val
, lim_data
, loop
, false))
712 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
714 lim_data
->cost
+= def_data
->cost
;
717 /* We want to avoid unconditionally executing very expensive
718 operations. As costs for our dependencies cannot be
719 negative just claim we are not invariand for this case.
720 We also are not sure whether the control-flow inside the
722 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
724 && total_cost
/ min_cost
<= 2))
727 /* Assume that the control-flow in the loop will vanish.
728 ??? We should verify this and not artificially increase
729 the cost if that is not the case. */
730 lim_data
->cost
+= stmt_cost (stmt
);
736 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
737 if (!add_dependency (val
, lim_data
, loop
, true))
740 if (gimple_vuse (stmt
))
743 = lim_data
? memory_accesses
.refs_list
[lim_data
->ref
] : NULL
;
745 && MEM_ANALYZABLE (ref
))
747 lim_data
->max_loop
= outermost_indep_loop (lim_data
->max_loop
,
749 if (!lim_data
->max_loop
)
752 else if (! add_dependency (gimple_vuse (stmt
), lim_data
, loop
, false))
756 lim_data
->cost
+= stmt_cost (stmt
);
761 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
762 and that one of the operands of this statement is computed by STMT.
763 Ensure that STMT (together with all the statements that define its
764 operands) is hoisted at least out of the loop LEVEL. */
767 set_level (gimple
*stmt
, struct loop
*orig_loop
, struct loop
*level
)
769 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
770 struct lim_aux_data
*lim_data
;
774 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
775 lim_data
= get_lim_data (stmt
);
776 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
777 stmt_loop
= find_common_loop (stmt_loop
,
778 loop_outer (lim_data
->tgt_loop
));
779 if (flow_loop_nested_p (stmt_loop
, level
))
782 gcc_assert (level
== lim_data
->max_loop
783 || flow_loop_nested_p (lim_data
->max_loop
, level
));
785 lim_data
->tgt_loop
= level
;
786 FOR_EACH_VEC_ELT (lim_data
->depends
, i
, dep_stmt
)
787 set_level (dep_stmt
, orig_loop
, level
);
790 /* Determines an outermost loop from that we want to hoist the statement STMT.
791 For now we chose the outermost possible loop. TODO -- use profiling
792 information to set it more sanely. */
795 set_profitable_level (gimple
*stmt
)
797 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
800 /* Returns true if STMT is a call that has side effects. */
803 nonpure_call_p (gimple
*stmt
)
805 if (gimple_code (stmt
) != GIMPLE_CALL
)
808 return gimple_has_side_effects (stmt
);
811 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
814 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
816 gassign
*stmt
, *stmt1
, *stmt2
;
817 tree name
, lhs
, type
;
819 gimple_stmt_iterator gsi
;
821 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
822 lhs
= gimple_assign_lhs (stmt
);
823 type
= TREE_TYPE (lhs
);
825 real_one
= build_one_cst (type
);
827 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
828 stmt1
= gimple_build_assign (name
, RDIV_EXPR
, real_one
,
829 gimple_assign_rhs2 (stmt
));
830 stmt2
= gimple_build_assign (lhs
, MULT_EXPR
, name
,
831 gimple_assign_rhs1 (stmt
));
833 /* Replace division stmt with reciprocal and multiply stmts.
834 The multiply stmt is not invariant, so update iterator
835 and avoid rescanning. */
837 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
838 gsi_replace (&gsi
, stmt2
, true);
840 /* Continue processing with invariant reciprocal statement. */
844 /* Check if the pattern at *BSI is a bittest of the form
845 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
848 rewrite_bittest (gimple_stmt_iterator
*bsi
)
855 tree lhs
, name
, t
, a
, b
;
858 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
859 lhs
= gimple_assign_lhs (stmt
);
861 /* Verify that the single use of lhs is a comparison against zero. */
862 if (TREE_CODE (lhs
) != SSA_NAME
863 || !single_imm_use (lhs
, &use
, &use_stmt
))
865 cond_stmt
= dyn_cast
<gcond
*> (use_stmt
);
868 if (gimple_cond_lhs (cond_stmt
) != lhs
869 || (gimple_cond_code (cond_stmt
) != NE_EXPR
870 && gimple_cond_code (cond_stmt
) != EQ_EXPR
)
871 || !integer_zerop (gimple_cond_rhs (cond_stmt
)))
874 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
875 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
876 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
879 /* There is a conversion in between possibly inserted by fold. */
880 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
882 t
= gimple_assign_rhs1 (stmt1
);
883 if (TREE_CODE (t
) != SSA_NAME
884 || !has_single_use (t
))
886 stmt1
= SSA_NAME_DEF_STMT (t
);
887 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
891 /* Verify that B is loop invariant but A is not. Verify that with
892 all the stmt walking we are still in the same loop. */
893 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
894 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
897 a
= gimple_assign_rhs1 (stmt1
);
898 b
= gimple_assign_rhs2 (stmt1
);
900 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
901 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
903 gimple_stmt_iterator rsi
;
906 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
907 build_int_cst (TREE_TYPE (a
), 1), b
);
908 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
909 stmt1
= gimple_build_assign (name
, t
);
912 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
913 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
914 stmt2
= gimple_build_assign (name
, t
);
916 /* Replace the SSA_NAME we compare against zero. Adjust
917 the type of zero accordingly. */
919 gimple_cond_set_rhs (cond_stmt
,
920 build_int_cst_type (TREE_TYPE (name
),
923 /* Don't use gsi_replace here, none of the new assignments sets
924 the variable originally set in stmt. Move bsi to stmt1, and
925 then remove the original stmt, so that we get a chance to
926 retain debug info for it. */
928 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
929 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
930 gimple
*to_release
= gsi_stmt (rsi
);
931 gsi_remove (&rsi
, true);
932 release_defs (to_release
);
940 /* For each statement determines the outermost loop in that it is invariant,
941 - statements on whose motion it depends and the cost of the computation.
942 - This information is stored to the LIM_DATA structure associated with
944 class invariantness_dom_walker
: public dom_walker
947 invariantness_dom_walker (cdi_direction direction
)
948 : dom_walker (direction
) {}
950 virtual edge
before_dom_children (basic_block
);
953 /* Determine the outermost loops in that statements in basic block BB are
954 invariant, and record them to the LIM_DATA associated with the statements.
955 Callback for dom_walker. */
958 invariantness_dom_walker::before_dom_children (basic_block bb
)
961 gimple_stmt_iterator bsi
;
963 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
964 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
965 struct lim_aux_data
*lim_data
;
967 if (!loop_outer (bb
->loop_father
))
970 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
971 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
972 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
974 /* Look at PHI nodes, but only if there is at most two.
975 ??? We could relax this further by post-processing the inserted
976 code and transforming adjacent cond-exprs with the same predicate
977 to control flow again. */
978 bsi
= gsi_start_phis (bb
);
980 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
981 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
982 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
984 stmt
= gsi_stmt (bsi
);
986 pos
= movement_possibility (stmt
);
987 if (pos
== MOVE_IMPOSSIBLE
)
990 lim_data
= get_lim_data (stmt
);
992 lim_data
= init_lim_data (stmt
);
993 lim_data
->always_executed_in
= outermost
;
995 if (!determine_max_movement (stmt
, false))
997 lim_data
->max_loop
= NULL
;
1001 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1003 print_gimple_stmt (dump_file
, stmt
, 2);
1004 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1005 loop_depth (lim_data
->max_loop
),
1009 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1010 set_profitable_level (stmt
);
1013 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1015 stmt
= gsi_stmt (bsi
);
1017 pos
= movement_possibility (stmt
);
1018 if (pos
== MOVE_IMPOSSIBLE
)
1020 if (nonpure_call_p (stmt
))
1025 /* Make sure to note always_executed_in for stores to make
1026 store-motion work. */
1027 else if (stmt_makes_single_store (stmt
))
1029 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
1031 lim_data
= init_lim_data (stmt
);
1032 lim_data
->always_executed_in
= outermost
;
1037 if (is_gimple_assign (stmt
)
1038 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1039 == GIMPLE_BINARY_RHS
))
1041 tree op0
= gimple_assign_rhs1 (stmt
);
1042 tree op1
= gimple_assign_rhs2 (stmt
);
1043 struct loop
*ol1
= outermost_invariant_loop (op1
,
1044 loop_containing_stmt (stmt
));
1046 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1047 to be hoisted out of loop, saving expensive divide. */
1048 if (pos
== MOVE_POSSIBLE
1049 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1050 && flag_unsafe_math_optimizations
1051 && !flag_trapping_math
1053 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1054 stmt
= rewrite_reciprocal (&bsi
);
1056 /* If the shift count is invariant, convert (A >> B) & 1 to
1057 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1058 saving an expensive shift. */
1059 if (pos
== MOVE_POSSIBLE
1060 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1061 && integer_onep (op1
)
1062 && TREE_CODE (op0
) == SSA_NAME
1063 && has_single_use (op0
))
1064 stmt
= rewrite_bittest (&bsi
);
1067 lim_data
= get_lim_data (stmt
);
1069 lim_data
= init_lim_data (stmt
);
1070 lim_data
->always_executed_in
= outermost
;
1072 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1075 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1077 lim_data
->max_loop
= NULL
;
1081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1083 print_gimple_stmt (dump_file
, stmt
, 2);
1084 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1085 loop_depth (lim_data
->max_loop
),
1089 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1090 set_profitable_level (stmt
);
1095 /* Hoist the statements in basic block BB out of the loops prescribed by
1096 data stored in LIM_DATA structures associated with each statement. Callback
1097 for walk_dominator_tree. */
1100 move_computations_worker (basic_block bb
)
1104 struct lim_aux_data
*lim_data
;
1105 unsigned int todo
= 0;
1107 if (!loop_outer (bb
->loop_father
))
1110 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1113 gphi
*stmt
= bsi
.phi ();
1115 lim_data
= get_lim_data (stmt
);
1116 if (lim_data
== NULL
)
1122 cost
= lim_data
->cost
;
1123 level
= lim_data
->tgt_loop
;
1124 clear_lim_data (stmt
);
1132 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1134 fprintf (dump_file
, "Moving PHI node\n");
1135 print_gimple_stmt (dump_file
, stmt
, 0);
1136 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1140 if (gimple_phi_num_args (stmt
) == 1)
1142 tree arg
= PHI_ARG_DEF (stmt
, 0);
1143 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1144 TREE_CODE (arg
), arg
);
1148 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1149 gimple
*cond
= gsi_stmt (gsi_last_bb (dom
));
1150 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1151 /* Get the PHI arguments corresponding to the true and false
1153 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1154 gcc_assert (arg0
&& arg1
);
1155 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1156 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1157 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1158 COND_EXPR
, t
, arg0
, arg1
);
1159 todo
|= TODO_cleanup_cfg
;
1161 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt
)))
1162 && (!ALWAYS_EXECUTED_IN (bb
)
1163 || (ALWAYS_EXECUTED_IN (bb
) != level
1164 && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1166 tree lhs
= gimple_assign_lhs (new_stmt
);
1167 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1169 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1170 remove_phi_node (&bsi
, false);
1173 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1177 gimple
*stmt
= gsi_stmt (bsi
);
1179 lim_data
= get_lim_data (stmt
);
1180 if (lim_data
== NULL
)
1186 cost
= lim_data
->cost
;
1187 level
= lim_data
->tgt_loop
;
1188 clear_lim_data (stmt
);
1196 /* We do not really want to move conditionals out of the loop; we just
1197 placed it here to force its operands to be moved if necessary. */
1198 if (gimple_code (stmt
) == GIMPLE_COND
)
1201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1203 fprintf (dump_file
, "Moving statement\n");
1204 print_gimple_stmt (dump_file
, stmt
, 0);
1205 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1209 e
= loop_preheader_edge (level
);
1210 gcc_assert (!gimple_vdef (stmt
));
1211 if (gimple_vuse (stmt
))
1213 /* The new VUSE is the one from the virtual PHI in the loop
1214 header or the one already present. */
1216 for (gsi2
= gsi_start_phis (e
->dest
);
1217 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1219 gphi
*phi
= gsi2
.phi ();
1220 if (virtual_operand_p (gimple_phi_result (phi
)))
1222 gimple_set_vuse (stmt
, PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1227 gsi_remove (&bsi
, false);
1228 if (gimple_has_lhs (stmt
)
1229 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1230 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt
)))
1231 && (!ALWAYS_EXECUTED_IN (bb
)
1232 || !(ALWAYS_EXECUTED_IN (bb
) == level
1233 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1235 tree lhs
= gimple_get_lhs (stmt
);
1236 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1238 /* In case this is a stmt that is not unconditionally executed
1239 when the target loop header is executed and the stmt may
1240 invoke undefined integer or pointer overflow rewrite it to
1241 unsigned arithmetic. */
1242 if (is_gimple_assign (stmt
)
1243 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
)))
1244 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt
)))
1245 && arith_code_with_undefined_signed_overflow
1246 (gimple_assign_rhs_code (stmt
))
1247 && (!ALWAYS_EXECUTED_IN (bb
)
1248 || !(ALWAYS_EXECUTED_IN (bb
) == level
1249 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1250 gsi_insert_seq_on_edge (e
, rewrite_to_defined_overflow (stmt
));
1252 gsi_insert_on_edge (e
, stmt
);
1258 /* Hoist the statements out of the loops prescribed by data stored in
1259 LIM_DATA structures associated with each statement.*/
1262 move_computations (void)
1264 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
1265 int n
= pre_and_rev_post_order_compute_fn (cfun
, NULL
, rpo
, false);
1268 for (int i
= 0; i
< n
; ++i
)
1269 todo
|= move_computations_worker (BASIC_BLOCK_FOR_FN (cfun
, rpo
[i
]));
1273 gsi_commit_edge_inserts ();
1274 if (need_ssa_update_p (cfun
))
1275 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1280 /* Checks whether the statement defining variable *INDEX can be hoisted
1281 out of the loop passed in DATA. Callback for for_each_index. */
1284 may_move_till (tree ref
, tree
*index
, void *data
)
1286 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1288 /* If REF is an array reference, check also that the step and the lower
1289 bound is invariant in LOOP. */
1290 if (TREE_CODE (ref
) == ARRAY_REF
)
1292 tree step
= TREE_OPERAND (ref
, 3);
1293 tree lbound
= TREE_OPERAND (ref
, 2);
1295 max_loop
= outermost_invariant_loop (step
, loop
);
1299 max_loop
= outermost_invariant_loop (lbound
, loop
);
1304 max_loop
= outermost_invariant_loop (*index
, loop
);
1311 /* If OP is SSA NAME, force the statement that defines it to be
1312 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1315 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1320 || is_gimple_min_invariant (op
))
1323 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1325 stmt
= SSA_NAME_DEF_STMT (op
);
1326 if (gimple_nop_p (stmt
))
1329 set_level (stmt
, orig_loop
, loop
);
1332 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1333 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1339 struct loop
*orig_loop
;
1343 force_move_till (tree ref
, tree
*index
, void *data
)
1345 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1347 if (TREE_CODE (ref
) == ARRAY_REF
)
1349 tree step
= TREE_OPERAND (ref
, 3);
1350 tree lbound
= TREE_OPERAND (ref
, 2);
1352 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1353 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1356 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1361 /* A function to free the mem_ref object OBJ. */
1364 memref_free (struct im_mem_ref
*mem
)
1366 mem
->accesses_in_loop
.release ();
1369 /* Allocates and returns a memory reference description for MEM whose hash
1370 value is HASH and id is ID. */
1373 mem_ref_alloc (ao_ref
*mem
, unsigned hash
, unsigned id
)
1375 im_mem_ref
*ref
= XOBNEW (&mem_ref_obstack
, struct im_mem_ref
);
1379 ao_ref_init (&ref
->mem
, error_mark_node
);
1381 ref
->ref_canonical
= false;
1384 bitmap_initialize (&ref
->indep_loop
, &lim_bitmap_obstack
);
1385 bitmap_initialize (&ref
->dep_loop
, &lim_bitmap_obstack
);
1386 ref
->accesses_in_loop
.create (1);
1391 /* Records memory reference location *LOC in LOOP to the memory reference
1392 description REF. The reference occurs in statement STMT. */
1395 record_mem_ref_loc (im_mem_ref
*ref
, gimple
*stmt
, tree
*loc
)
1400 ref
->accesses_in_loop
.safe_push (aref
);
1403 /* Set the LOOP bit in REF stored bitmap and allocate that if
1404 necessary. Return whether a bit was changed. */
1407 set_ref_stored_in_loop (im_mem_ref
*ref
, struct loop
*loop
)
1410 ref
->stored
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1411 return bitmap_set_bit (ref
->stored
, loop
->num
);
1414 /* Marks reference REF as stored in LOOP. */
1417 mark_ref_stored (im_mem_ref
*ref
, struct loop
*loop
)
1419 while (loop
!= current_loops
->tree_root
1420 && set_ref_stored_in_loop (ref
, loop
))
1421 loop
= loop_outer (loop
);
1424 /* Gathers memory references in statement STMT in LOOP, storing the
1425 information about them in the memory_accesses structure. Marks
1426 the vops accessed through unrecognized statements there as
1430 gather_mem_refs_stmt (struct loop
*loop
, gimple
*stmt
)
1439 if (!gimple_vuse (stmt
))
1442 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1445 /* We use the shared mem_ref for all unanalyzable refs. */
1446 id
= UNANALYZABLE_MEM_ID
;
1447 ref
= memory_accesses
.refs_list
[id
];
1448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1450 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1451 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1453 is_stored
= gimple_vdef (stmt
);
1457 /* We are looking for equal refs that might differ in structure
1458 such as a.b vs. MEM[&a + 4]. So we key off the ao_ref but
1459 make sure we can canonicalize the ref in the hashtable if
1460 non-operand_equal_p refs are found. For the lookup we mark
1461 the case we want strict equality with aor.max_size == -1. */
1463 ao_ref_init (&aor
, *mem
);
1465 ao_ref_alias_set (&aor
);
1466 HOST_WIDE_INT offset
, size
, max_size
;
1467 poly_int64 saved_maxsize
= aor
.max_size
, mem_off
;
1469 if (aor
.max_size_known_p ()
1470 && aor
.offset
.is_constant (&offset
)
1471 && aor
.size
.is_constant (&size
)
1472 && aor
.max_size
.is_constant (&max_size
)
1474 && (size
% BITS_PER_UNIT
) == 0
1475 /* We're canonicalizing to a MEM where TYPE_SIZE specifies the
1476 size. Make sure this is consistent with the extraction. */
1477 && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (*mem
)))
1478 && known_eq (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (*mem
))),
1480 && (mem_base
= get_addr_base_and_unit_offset (aor
.ref
, &mem_off
)))
1482 hash
= iterative_hash_expr (ao_ref_base (&aor
), 0);
1483 hash
= iterative_hash_host_wide_int (offset
, hash
);
1484 hash
= iterative_hash_host_wide_int (size
, hash
);
1488 hash
= iterative_hash_expr (aor
.ref
, 0);
1491 slot
= memory_accesses
.refs
->find_slot_with_hash (&aor
, hash
, INSERT
);
1492 aor
.max_size
= saved_maxsize
;
1495 if (!(*slot
)->ref_canonical
1496 && !operand_equal_p (*mem
, (*slot
)->mem
.ref
, 0))
1498 /* If we didn't yet canonicalize the hashtable ref (which
1499 we'll end up using for code insertion) and hit a second
1500 equal ref that is not structurally equivalent create
1501 a canonical ref which is a bare MEM_REF. */
1502 if (TREE_CODE (*mem
) == MEM_REF
1503 || TREE_CODE (*mem
) == TARGET_MEM_REF
)
1505 (*slot
)->mem
.ref
= *mem
;
1506 (*slot
)->mem
.base_alias_set
= ao_ref_base_alias_set (&aor
);
1510 tree ref_alias_type
= reference_alias_ptr_type (*mem
);
1511 unsigned int ref_align
= get_object_alignment (*mem
);
1512 tree ref_type
= TREE_TYPE (*mem
);
1513 tree tmp
= build_fold_addr_expr (unshare_expr (mem_base
));
1514 if (TYPE_ALIGN (ref_type
) != ref_align
)
1515 ref_type
= build_aligned_type (ref_type
, ref_align
);
1517 = fold_build2 (MEM_REF
, ref_type
, tmp
,
1518 build_int_cst (ref_alias_type
, mem_off
));
1519 if ((*slot
)->mem
.volatile_p
)
1520 TREE_THIS_VOLATILE ((*slot
)->mem
.ref
) = 1;
1521 gcc_checking_assert (TREE_CODE ((*slot
)->mem
.ref
) == MEM_REF
1522 && is_gimple_mem_ref_addr
1523 (TREE_OPERAND ((*slot
)->mem
.ref
,
1525 (*slot
)->mem
.base_alias_set
= (*slot
)->mem
.ref_alias_set
;
1527 (*slot
)->ref_canonical
= true;
1534 id
= memory_accesses
.refs_list
.length ();
1535 ref
= mem_ref_alloc (&aor
, hash
, id
);
1536 memory_accesses
.refs_list
.safe_push (ref
);
1539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1541 fprintf (dump_file
, "Memory reference %u: ", id
);
1542 print_generic_expr (dump_file
, ref
->mem
.ref
, TDF_SLIM
);
1543 fprintf (dump_file
, "\n");
1547 record_mem_ref_loc (ref
, stmt
, mem
);
1549 bitmap_set_bit (&memory_accesses
.refs_in_loop
[loop
->num
], ref
->id
);
1552 bitmap_set_bit (&memory_accesses
.refs_stored_in_loop
[loop
->num
], ref
->id
);
1553 mark_ref_stored (ref
, loop
);
1555 init_lim_data (stmt
)->ref
= ref
->id
;
1559 static unsigned *bb_loop_postorder
;
1561 /* qsort sort function to sort blocks after their loop fathers postorder. */
1564 sort_bbs_in_loop_postorder_cmp (const void *bb1_
, const void *bb2_
)
1566 basic_block bb1
= *(basic_block
*)const_cast<void *>(bb1_
);
1567 basic_block bb2
= *(basic_block
*)const_cast<void *>(bb2_
);
1568 struct loop
*loop1
= bb1
->loop_father
;
1569 struct loop
*loop2
= bb2
->loop_father
;
1570 if (loop1
->num
== loop2
->num
)
1571 return bb1
->index
- bb2
->index
;
1572 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1575 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1578 sort_locs_in_loop_postorder_cmp (const void *loc1_
, const void *loc2_
)
1580 mem_ref_loc
*loc1
= (mem_ref_loc
*)const_cast<void *>(loc1_
);
1581 mem_ref_loc
*loc2
= (mem_ref_loc
*)const_cast<void *>(loc2_
);
1582 struct loop
*loop1
= gimple_bb (loc1
->stmt
)->loop_father
;
1583 struct loop
*loop2
= gimple_bb (loc2
->stmt
)->loop_father
;
1584 if (loop1
->num
== loop2
->num
)
1586 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1589 /* Gathers memory references in loops. */
1592 analyze_memory_references (void)
1594 gimple_stmt_iterator bsi
;
1595 basic_block bb
, *bbs
;
1596 struct loop
*loop
, *outer
;
1599 /* Collect all basic-blocks in loops and sort them after their
1602 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
1603 FOR_EACH_BB_FN (bb
, cfun
)
1604 if (bb
->loop_father
!= current_loops
->tree_root
)
1607 qsort (bbs
, n
, sizeof (basic_block
), sort_bbs_in_loop_postorder_cmp
);
1609 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1610 That results in better locality for all the bitmaps. */
1611 for (i
= 0; i
< n
; ++i
)
1613 basic_block bb
= bbs
[i
];
1614 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1615 gather_mem_refs_stmt (bb
->loop_father
, gsi_stmt (bsi
));
1618 /* Sort the location list of gathered memory references after their
1619 loop postorder number. */
1621 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
1622 ref
->accesses_in_loop
.qsort (sort_locs_in_loop_postorder_cmp
);
1625 // free (bb_loop_postorder);
1627 /* Propagate the information about accessed memory references up
1628 the loop hierarchy. */
1629 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1631 /* Finalize the overall touched references (including subloops). */
1632 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1633 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1635 /* Propagate the information about accessed memory references up
1636 the loop hierarchy. */
1637 outer
= loop_outer (loop
);
1638 if (outer
== current_loops
->tree_root
)
1641 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1642 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1646 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1647 tree_to_aff_combination_expand. */
1650 mem_refs_may_alias_p (im_mem_ref
*mem1
, im_mem_ref
*mem2
,
1651 hash_map
<tree
, name_expansion
*> **ttae_cache
)
1653 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1654 object and their offset differ in such a way that the locations cannot
1655 overlap, then they cannot alias. */
1656 poly_widest_int size1
, size2
;
1657 aff_tree off1
, off2
;
1659 /* Perform basic offset and type-based disambiguation. */
1660 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, true))
1663 /* The expansion of addresses may be a bit expensive, thus we only do
1664 the check at -O2 and higher optimization levels. */
1668 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1669 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1670 aff_combination_expand (&off1
, ttae_cache
);
1671 aff_combination_expand (&off2
, ttae_cache
);
1672 aff_combination_scale (&off1
, -1);
1673 aff_combination_add (&off2
, &off1
);
1675 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1681 /* Compare function for bsearch searching for reference locations
1685 find_ref_loc_in_loop_cmp (const void *loop_
, const void *loc_
)
1687 struct loop
*loop
= (struct loop
*)const_cast<void *>(loop_
);
1688 mem_ref_loc
*loc
= (mem_ref_loc
*)const_cast<void *>(loc_
);
1689 struct loop
*loc_loop
= gimple_bb (loc
->stmt
)->loop_father
;
1690 if (loop
->num
== loc_loop
->num
1691 || flow_loop_nested_p (loop
, loc_loop
))
1693 return (bb_loop_postorder
[loop
->num
] < bb_loop_postorder
[loc_loop
->num
]
1697 /* Iterates over all locations of REF in LOOP and its subloops calling
1698 fn.operator() with the location as argument. When that operator
1699 returns true the iteration is stopped and true is returned.
1700 Otherwise false is returned. */
1702 template <typename FN
>
1704 for_all_locs_in_loop (struct loop
*loop
, im_mem_ref
*ref
, FN fn
)
1709 /* Search for the cluster of locs in the accesses_in_loop vector
1710 which is sorted after postorder index of the loop father. */
1711 loc
= ref
->accesses_in_loop
.bsearch (loop
, find_ref_loc_in_loop_cmp
);
1715 /* We have found one location inside loop or its sub-loops. Iterate
1716 both forward and backward to cover the whole cluster. */
1717 i
= loc
- ref
->accesses_in_loop
.address ();
1721 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1722 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1727 for (i
= loc
- ref
->accesses_in_loop
.address ();
1728 i
< ref
->accesses_in_loop
.length (); ++i
)
1730 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1731 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1740 /* Rewrites location LOC by TMP_VAR. */
1742 struct rewrite_mem_ref_loc
1744 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1745 bool operator () (mem_ref_loc
*loc
);
1750 rewrite_mem_ref_loc::operator () (mem_ref_loc
*loc
)
1752 *loc
->ref
= tmp_var
;
1753 update_stmt (loc
->stmt
);
1757 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1760 rewrite_mem_refs (struct loop
*loop
, im_mem_ref
*ref
, tree tmp_var
)
1762 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1765 /* Stores the first reference location in LOCP. */
1767 struct first_mem_ref_loc_1
1769 first_mem_ref_loc_1 (mem_ref_loc
**locp_
) : locp (locp_
) {}
1770 bool operator () (mem_ref_loc
*loc
);
1775 first_mem_ref_loc_1::operator () (mem_ref_loc
*loc
)
1781 /* Returns the first reference location to REF in LOOP. */
1783 static mem_ref_loc
*
1784 first_mem_ref_loc (struct loop
*loop
, im_mem_ref
*ref
)
1786 mem_ref_loc
*locp
= NULL
;
1787 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1791 struct prev_flag_edges
{
1792 /* Edge to insert new flag comparison code. */
1793 edge append_cond_position
;
1795 /* Edge for fall through from previous flag comparison. */
1796 edge last_cond_fallthru
;
1799 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1802 The store is only done if MEM has changed. We do this so no
1803 changes to MEM occur on code paths that did not originally store
1806 The common case for execute_sm will transform:
1826 This function will generate:
1845 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
,
1846 edge preheader
, hash_set
<basic_block
> *flag_bbs
)
1848 basic_block new_bb
, then_bb
, old_dest
;
1849 bool loop_has_only_one_exit
;
1850 edge then_old_edge
, orig_ex
= ex
;
1851 gimple_stmt_iterator gsi
;
1853 struct prev_flag_edges
*prev_edges
= (struct prev_flag_edges
*) ex
->aux
;
1854 bool irr
= ex
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1856 profile_count count_sum
= profile_count::zero ();
1857 int nbbs
= 0, ncount
= 0;
1858 profile_probability flag_probability
= profile_probability::uninitialized ();
1860 /* Flag is set in FLAG_BBS. Determine probability that flag will be true
1863 This code may look fancy, but it cannot update profile very realistically
1864 because we do not know the probability that flag will be true at given
1867 We look for two interesting extremes
1868 - when exit is dominated by block setting the flag, we know it will
1869 always be true. This is a common case.
1870 - when all blocks setting the flag have very low frequency we know
1871 it will likely be false.
1872 In all other cases we default to 2/3 for flag being true. */
1874 for (hash_set
<basic_block
>::iterator it
= flag_bbs
->begin ();
1875 it
!= flag_bbs
->end (); ++it
)
1877 if ((*it
)->count
.initialized_p ())
1878 count_sum
+= (*it
)->count
, ncount
++;
1879 if (dominated_by_p (CDI_DOMINATORS
, ex
->src
, *it
))
1880 flag_probability
= profile_probability::always ();
1884 profile_probability cap
= profile_probability::always ().apply_scale (2, 3);
1886 if (flag_probability
.initialized_p ())
1888 else if (ncount
== nbbs
1889 && preheader
->count () >= count_sum
&& preheader
->count ().nonzero_p ())
1891 flag_probability
= count_sum
.probability_in (preheader
->count ());
1892 if (flag_probability
> cap
)
1893 flag_probability
= cap
;
1896 if (!flag_probability
.initialized_p ())
1897 flag_probability
= cap
;
1899 /* ?? Insert store after previous store if applicable. See note
1902 ex
= prev_edges
->append_cond_position
;
1904 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1906 if (loop_has_only_one_exit
)
1907 ex
= split_block_after_labels (ex
->dest
);
1910 for (gphi_iterator gpi
= gsi_start_phis (ex
->dest
);
1911 !gsi_end_p (gpi
); gsi_next (&gpi
))
1913 gphi
*phi
= gpi
.phi ();
1914 if (virtual_operand_p (gimple_phi_result (phi
)))
1917 /* When the destination has a non-virtual PHI node with multiple
1918 predecessors make sure we preserve the PHI structure by
1919 forcing a forwarder block so that hoisting of that PHI will
1926 old_dest
= ex
->dest
;
1927 new_bb
= split_edge (ex
);
1928 then_bb
= create_empty_bb (new_bb
);
1929 then_bb
->count
= new_bb
->count
.apply_probability (flag_probability
);
1931 then_bb
->flags
= BB_IRREDUCIBLE_LOOP
;
1932 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1934 gsi
= gsi_start_bb (new_bb
);
1935 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1936 NULL_TREE
, NULL_TREE
);
1937 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1939 gsi
= gsi_start_bb (then_bb
);
1940 /* Insert actual store. */
1941 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1942 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1944 edge e1
= single_succ_edge (new_bb
);
1945 edge e2
= make_edge (new_bb
, then_bb
,
1946 EDGE_TRUE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1947 e2
->probability
= flag_probability
;
1949 e1
->flags
|= EDGE_FALSE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0);
1950 e1
->flags
&= ~EDGE_FALLTHRU
;
1952 e1
->probability
= flag_probability
.invert ();
1954 then_old_edge
= make_single_succ_edge (then_bb
, old_dest
,
1955 EDGE_FALLTHRU
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1957 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
1961 basic_block prevbb
= prev_edges
->last_cond_fallthru
->src
;
1962 redirect_edge_succ (prev_edges
->last_cond_fallthru
, new_bb
);
1963 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
1964 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
1965 recompute_dominator (CDI_DOMINATORS
, old_dest
));
1968 /* ?? Because stores may alias, they must happen in the exact
1969 sequence they originally happened. Save the position right after
1970 the (_lsm) store we just created so we can continue appending after
1971 it and maintain the original order. */
1973 struct prev_flag_edges
*p
;
1976 orig_ex
->aux
= NULL
;
1977 alloc_aux_for_edge (orig_ex
, sizeof (struct prev_flag_edges
));
1978 p
= (struct prev_flag_edges
*) orig_ex
->aux
;
1979 p
->append_cond_position
= then_old_edge
;
1980 p
->last_cond_fallthru
= find_edge (new_bb
, old_dest
);
1981 orig_ex
->aux
= (void *) p
;
1984 if (!loop_has_only_one_exit
)
1985 for (gphi_iterator gpi
= gsi_start_phis (old_dest
);
1986 !gsi_end_p (gpi
); gsi_next (&gpi
))
1988 gphi
*phi
= gpi
.phi ();
1991 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1992 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
1994 tree arg
= gimple_phi_arg_def (phi
, i
);
1995 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
2001 /* When REF is set on the location, set flag indicating the store. */
2003 struct sm_set_flag_if_changed
2005 sm_set_flag_if_changed (tree flag_
, hash_set
<basic_block
> *bbs_
)
2006 : flag (flag_
), bbs (bbs_
) {}
2007 bool operator () (mem_ref_loc
*loc
);
2009 hash_set
<basic_block
> *bbs
;
2013 sm_set_flag_if_changed::operator () (mem_ref_loc
*loc
)
2015 /* Only set the flag for writes. */
2016 if (is_gimple_assign (loc
->stmt
)
2017 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
2019 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
2020 gimple
*stmt
= gimple_build_assign (flag
, boolean_true_node
);
2021 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2022 bbs
->add (gimple_bb (stmt
));
2027 /* Helper function for execute_sm. On every location where REF is
2028 set, set an appropriate flag indicating the store. */
2031 execute_sm_if_changed_flag_set (struct loop
*loop
, im_mem_ref
*ref
,
2032 hash_set
<basic_block
> *bbs
)
2035 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0, "_flag");
2036 flag
= create_tmp_reg (boolean_type_node
, str
);
2037 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
, bbs
));
2041 /* Executes store motion of memory reference REF from LOOP.
2042 Exits from the LOOP are stored in EXITS. The initialization of the
2043 temporary variable is put to the preheader of the loop, and assignments
2044 to the reference from the temporary variable are emitted to exits. */
2047 execute_sm (struct loop
*loop
, vec
<edge
> exits
, im_mem_ref
*ref
)
2049 tree tmp_var
, store_flag
= NULL_TREE
;
2052 struct fmt_data fmt_data
;
2054 struct lim_aux_data
*lim_data
;
2055 bool multi_threaded_model_p
= false;
2056 gimple_stmt_iterator gsi
;
2057 hash_set
<basic_block
> flag_bbs
;
2059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2061 fprintf (dump_file
, "Executing store motion of ");
2062 print_generic_expr (dump_file
, ref
->mem
.ref
);
2063 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2066 tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
2067 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
2069 fmt_data
.loop
= loop
;
2070 fmt_data
.orig_loop
= loop
;
2071 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
2073 if (bb_in_transaction (loop_preheader_edge (loop
)->src
)
2074 || (! PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
)
2075 && ! ref_always_accessed_p (loop
, ref
, true)))
2076 multi_threaded_model_p
= true;
2078 if (multi_threaded_model_p
)
2079 store_flag
= execute_sm_if_changed_flag_set (loop
, ref
, &flag_bbs
);
2081 rewrite_mem_refs (loop
, ref
, tmp_var
);
2083 /* Emit the load code on a random exit edge or into the latch if
2084 the loop does not exit, so that we are sure it will be processed
2085 by move_computations after all dependencies. */
2086 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
2088 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
2089 load altogether, since the store is predicated by a flag. We
2090 could, do the load only if it was originally in the loop. */
2091 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
.ref
));
2092 lim_data
= init_lim_data (load
);
2093 lim_data
->max_loop
= loop
;
2094 lim_data
->tgt_loop
= loop
;
2095 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2097 if (multi_threaded_model_p
)
2099 load
= gimple_build_assign (store_flag
, boolean_false_node
);
2100 lim_data
= init_lim_data (load
);
2101 lim_data
->max_loop
= loop
;
2102 lim_data
->tgt_loop
= loop
;
2103 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2106 /* Sink the store to every exit from the loop. */
2107 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2108 if (!multi_threaded_model_p
)
2111 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
), tmp_var
);
2112 gsi_insert_on_edge (ex
, store
);
2115 execute_sm_if_changed (ex
, ref
->mem
.ref
, tmp_var
, store_flag
,
2116 loop_preheader_edge (loop
), &flag_bbs
);
2119 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2120 edges of the LOOP. */
2123 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2130 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2132 ref
= memory_accesses
.refs_list
[i
];
2133 execute_sm (loop
, exits
, ref
);
2137 struct ref_always_accessed
2139 ref_always_accessed (struct loop
*loop_
, bool stored_p_
)
2140 : loop (loop_
), stored_p (stored_p_
) {}
2141 bool operator () (mem_ref_loc
*loc
);
2147 ref_always_accessed::operator () (mem_ref_loc
*loc
)
2149 struct loop
*must_exec
;
2151 if (!get_lim_data (loc
->stmt
))
2154 /* If we require an always executed store make sure the statement
2155 stores to the reference. */
2158 tree lhs
= gimple_get_lhs (loc
->stmt
);
2160 || lhs
!= *loc
->ref
)
2164 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2168 if (must_exec
== loop
2169 || flow_loop_nested_p (must_exec
, loop
))
2175 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2176 make sure REF is always stored to in LOOP. */
2179 ref_always_accessed_p (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2181 return for_all_locs_in_loop (loop
, ref
,
2182 ref_always_accessed (loop
, stored_p
));
2185 /* Returns true if REF1 and REF2 are independent. */
2188 refs_independent_p (im_mem_ref
*ref1
, im_mem_ref
*ref2
)
2193 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2194 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2195 ref1
->id
, ref2
->id
);
2197 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
))
2199 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2200 fprintf (dump_file
, "dependent.\n");
2205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2206 fprintf (dump_file
, "independent.\n");
2211 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2212 and its super-loops. */
2215 record_dep_loop (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2217 /* We can propagate dependent-in-loop bits up the loop
2218 hierarchy to all outer loops. */
2219 while (loop
!= current_loops
->tree_root
2220 && bitmap_set_bit (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2221 loop
= loop_outer (loop
);
2224 /* Returns true if REF is independent on all other memory
2225 references in LOOP. */
2228 ref_indep_loop_p_1 (struct loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2230 stored_p
|= (ref
->stored
&& bitmap_bit_p (ref
->stored
, loop
->num
));
2232 bool indep_p
= true;
2233 bitmap refs_to_check
;
2236 refs_to_check
= &memory_accesses
.refs_in_loop
[loop
->num
];
2238 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2240 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2244 if (bitmap_bit_p (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2246 if (bitmap_bit_p (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2249 struct loop
*inner
= loop
->inner
;
2252 if (!ref_indep_loop_p_1 (inner
, ref
, stored_p
))
2257 inner
= inner
->next
;
2264 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2266 im_mem_ref
*aref
= memory_accesses
.refs_list
[i
];
2267 if (!refs_independent_p (ref
, aref
))
2276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2277 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2278 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2280 /* Record the computed result in the cache. */
2283 if (bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
))
2286 /* If it's independend against all refs then it's independent
2287 against stores, too. */
2288 bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, false));
2293 record_dep_loop (loop
, ref
, stored_p
);
2296 /* If it's dependent against stores it's dependent against
2298 record_dep_loop (loop
, ref
, true);
2305 /* Returns true if REF is independent on all other memory references in
2309 ref_indep_loop_p (struct loop
*loop
, im_mem_ref
*ref
)
2311 gcc_checking_assert (MEM_ANALYZABLE (ref
));
2313 return ref_indep_loop_p_1 (loop
, ref
, false);
2316 /* Returns true if we can perform store motion of REF from LOOP. */
2319 can_sm_ref_p (struct loop
*loop
, im_mem_ref
*ref
)
2323 /* Can't hoist unanalyzable refs. */
2324 if (!MEM_ANALYZABLE (ref
))
2327 /* It should be movable. */
2328 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2329 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2330 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2333 /* If it can throw fail, we do not properly update EH info. */
2334 if (tree_could_throw_p (ref
->mem
.ref
))
2337 /* If it can trap, it must be always executed in LOOP.
2338 Readonly memory locations may trap when storing to them, but
2339 tree_could_trap_p is a predicate for rvalues, so check that
2341 base
= get_base_address (ref
->mem
.ref
);
2342 if ((tree_could_trap_p (ref
->mem
.ref
)
2343 || (DECL_P (base
) && TREE_READONLY (base
)))
2344 && !ref_always_accessed_p (loop
, ref
, true))
2347 /* And it must be independent on all other memory references
2349 if (!ref_indep_loop_p (loop
, ref
))
2355 /* Marks the references in LOOP for that store motion should be performed
2356 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2357 motion was performed in one of the outer loops. */
2360 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2362 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2367 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2369 ref
= memory_accesses
.refs_list
[i
];
2370 if (can_sm_ref_p (loop
, ref
))
2371 bitmap_set_bit (refs_to_sm
, i
);
2375 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2376 for a store motion optimization (i.e. whether we can insert statement
2380 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2386 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2387 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2393 /* Try to perform store motion for all memory references modified inside
2394 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2395 store motion was executed in one of the outer loops. */
2398 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2400 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2401 struct loop
*subloop
;
2402 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2404 if (loop_suitable_for_sm (loop
, exits
))
2406 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2407 hoist_memory_references (loop
, sm_in_loop
, exits
);
2411 bitmap_ior_into (sm_executed
, sm_in_loop
);
2412 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2413 store_motion_loop (subloop
, sm_executed
);
2414 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2415 BITMAP_FREE (sm_in_loop
);
2418 /* Try to perform store motion for all memory references modified inside
2425 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2427 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2428 store_motion_loop (loop
, sm_executed
);
2430 BITMAP_FREE (sm_executed
);
2431 gsi_commit_edge_inserts ();
2434 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2435 for each such basic block bb records the outermost loop for that execution
2436 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2437 blocks that contain a nonpure call. */
2440 fill_always_executed_in_1 (struct loop
*loop
, sbitmap contains_call
)
2442 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2445 struct loop
*inn_loop
= loop
;
2447 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2449 bbs
= get_loop_body_in_dom_order (loop
);
2451 for (i
= 0; i
< loop
->num_nodes
; i
++)
2456 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2459 if (bitmap_bit_p (contains_call
, bb
->index
))
2462 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2464 /* If there is an exit from this BB. */
2465 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2467 /* Or we enter a possibly non-finite loop. */
2468 if (flow_loop_nested_p (bb
->loop_father
,
2469 e
->dest
->loop_father
)
2470 && ! finite_loop_p (e
->dest
->loop_father
))
2476 /* A loop might be infinite (TODO use simple loop analysis
2477 to disprove this if possible). */
2478 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2481 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2484 if (bb
->loop_father
->header
== bb
)
2486 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2489 /* In a loop that is always entered we may proceed anyway.
2490 But record that we entered it and stop once we leave it. */
2491 inn_loop
= bb
->loop_father
;
2497 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2498 if (last
== loop
->header
)
2500 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2506 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2507 fill_always_executed_in_1 (loop
, contains_call
);
2510 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2511 for each such basic block bb records the outermost loop for that execution
2512 of its header implies execution of bb. */
2515 fill_always_executed_in (void)
2520 auto_sbitmap
contains_call (last_basic_block_for_fn (cfun
));
2521 bitmap_clear (contains_call
);
2522 FOR_EACH_BB_FN (bb
, cfun
)
2524 gimple_stmt_iterator gsi
;
2525 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2527 if (nonpure_call_p (gsi_stmt (gsi
)))
2531 if (!gsi_end_p (gsi
))
2532 bitmap_set_bit (contains_call
, bb
->index
);
2535 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2536 fill_always_executed_in_1 (loop
, contains_call
);
2540 /* Compute the global information needed by the loop invariant motion pass. */
2543 tree_ssa_lim_initialize (void)
2548 bitmap_obstack_initialize (&lim_bitmap_obstack
);
2549 gcc_obstack_init (&mem_ref_obstack
);
2550 lim_aux_data_map
= new hash_map
<gimple
*, lim_aux_data
*>;
2553 compute_transaction_bits ();
2555 alloc_aux_for_edges (0);
2557 memory_accesses
.refs
= new hash_table
<mem_ref_hasher
> (100);
2558 memory_accesses
.refs_list
.create (100);
2559 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2560 memory_accesses
.refs_list
.quick_push
2561 (mem_ref_alloc (NULL
, 0, UNANALYZABLE_MEM_ID
));
2563 memory_accesses
.refs_in_loop
.create (number_of_loops (cfun
));
2564 memory_accesses
.refs_in_loop
.quick_grow (number_of_loops (cfun
));
2565 memory_accesses
.refs_stored_in_loop
.create (number_of_loops (cfun
));
2566 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2567 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops (cfun
));
2568 memory_accesses
.all_refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2570 for (i
= 0; i
< number_of_loops (cfun
); i
++)
2572 bitmap_initialize (&memory_accesses
.refs_in_loop
[i
],
2573 &lim_bitmap_obstack
);
2574 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
2575 &lim_bitmap_obstack
);
2576 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
2577 &lim_bitmap_obstack
);
2580 memory_accesses
.ttae_cache
= NULL
;
2582 /* Initialize bb_loop_postorder with a mapping from loop->num to
2583 its postorder index. */
2585 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops (cfun
));
2586 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2587 bb_loop_postorder
[loop
->num
] = i
++;
2590 /* Cleans up after the invariant motion pass. */
2593 tree_ssa_lim_finalize (void)
2599 free_aux_for_edges ();
2601 FOR_EACH_BB_FN (bb
, cfun
)
2602 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2604 bitmap_obstack_release (&lim_bitmap_obstack
);
2605 delete lim_aux_data_map
;
2607 delete memory_accesses
.refs
;
2608 memory_accesses
.refs
= NULL
;
2610 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
2612 memory_accesses
.refs_list
.release ();
2613 obstack_free (&mem_ref_obstack
, NULL
);
2615 memory_accesses
.refs_in_loop
.release ();
2616 memory_accesses
.refs_stored_in_loop
.release ();
2617 memory_accesses
.all_refs_stored_in_loop
.release ();
2619 if (memory_accesses
.ttae_cache
)
2620 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
2622 free (bb_loop_postorder
);
2625 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2626 i.e. those that are likely to be win regardless of the register pressure. */
2633 tree_ssa_lim_initialize ();
2635 /* Gathers information about memory accesses in the loops. */
2636 analyze_memory_references ();
2638 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2639 fill_always_executed_in ();
2641 /* For each statement determine the outermost loop in that it is
2642 invariant and cost for computing the invariant. */
2643 invariantness_dom_walker (CDI_DOMINATORS
)
2644 .walk (cfun
->cfg
->x_entry_block_ptr
);
2646 /* Execute store motion. Force the necessary invariants to be moved
2647 out of the loops as well. */
2650 /* Move the expressions that are expensive enough. */
2651 todo
= move_computations ();
2653 tree_ssa_lim_finalize ();
2658 /* Loop invariant motion pass. */
2662 const pass_data pass_data_lim
=
2664 GIMPLE_PASS
, /* type */
2666 OPTGROUP_LOOP
, /* optinfo_flags */
2668 PROP_cfg
, /* properties_required */
2669 0, /* properties_provided */
2670 0, /* properties_destroyed */
2671 0, /* todo_flags_start */
2672 0, /* todo_flags_finish */
2675 class pass_lim
: public gimple_opt_pass
2678 pass_lim (gcc::context
*ctxt
)
2679 : gimple_opt_pass (pass_data_lim
, ctxt
)
2682 /* opt_pass methods: */
2683 opt_pass
* clone () { return new pass_lim (m_ctxt
); }
2684 virtual bool gate (function
*) { return flag_tree_loop_im
!= 0; }
2685 virtual unsigned int execute (function
*);
2687 }; // class pass_lim
2690 pass_lim::execute (function
*fun
)
2692 bool in_loop_pipeline
= scev_initialized_p ();
2693 if (!in_loop_pipeline
)
2694 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
2696 if (number_of_loops (fun
) <= 1)
2698 unsigned int todo
= tree_ssa_lim ();
2700 if (!in_loop_pipeline
)
2701 loop_optimizer_finalize ();
2710 make_pass_lim (gcc::context
*ctxt
)
2712 return new pass_lim (ctxt
);