1 /* Loop invariant motion.
2 Copyright (C) 2003-2021 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"
40 #include "tree-affine.h"
41 #include "tree-ssa-propagate.h"
42 #include "trans-mem.h"
43 #include "gimple-fold.h"
44 #include "tree-scalar-evolution.h"
45 #include "tree-ssa-loop-niter.h"
51 /* TODO: Support for predicated code motion. I.e.
62 Where COND and INV are invariants, but evaluating INV may trap or be
63 invalid from some other reason if !COND. This may be transformed to
73 /* The auxiliary data kept for each statement. */
77 class loop
*max_loop
; /* The outermost loop in that the statement
80 class loop
*tgt_loop
; /* The loop out of that we want to move the
83 class loop
*always_executed_in
;
84 /* The outermost loop for that we are sure
85 the statement is executed if the loop
88 unsigned cost
; /* Cost of the computation performed by the
91 unsigned ref
; /* The simple_mem_ref in this stmt or 0. */
93 vec
<gimple
*> depends
; /* Vector of statements that must be also
94 hoisted out of the loop when this statement
95 is hoisted; i.e. those that define the
96 operands of the statement and are inside of
100 /* Maps statements to their lim_aux_data. */
102 static hash_map
<gimple
*, lim_aux_data
*> *lim_aux_data_map
;
104 /* Description of a memory reference location. */
108 tree
*ref
; /* The reference itself. */
109 gimple
*stmt
; /* The statement in that it occurs. */
113 /* Description of a memory reference. */
118 unsigned id
: 30; /* 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 unsigned ref_decomposed
: 1; /* Whether the ref was hashed from mem. */
122 hashval_t hash
; /* Its hash value. */
124 /* The memory access itself and associated caching of alias-oracle
128 bitmap stored
; /* The set of loops in that this memory location
130 bitmap loaded
; /* The set of loops in that this memory location
132 vec
<mem_ref_loc
> accesses_in_loop
;
133 /* The locations of the accesses. Vector
134 indexed by the loop number. */
136 /* The following set is computed on demand. */
137 bitmap_head dep_loop
; /* The set of loops in that the memory
138 reference is {in,}dependent in
142 /* We use six bits per loop in the ref->dep_loop bitmap to record
143 the dep_kind x dep_state combinations. */
145 enum dep_kind
{ lim_raw
, sm_war
, sm_waw
};
146 enum dep_state
{ dep_unknown
, dep_independent
, dep_dependent
};
148 /* Populate the loop dependence cache of REF for LOOP, KIND with STATE. */
151 record_loop_dependence (class loop
*loop
, im_mem_ref
*ref
,
152 dep_kind kind
, dep_state state
)
154 gcc_assert (state
!= dep_unknown
);
155 unsigned bit
= 6 * loop
->num
+ kind
* 2 + state
== dep_dependent
? 1 : 0;
156 bitmap_set_bit (&ref
->dep_loop
, bit
);
159 /* Query the loop dependence cache of REF for LOOP, KIND. */
162 query_loop_dependence (class loop
*loop
, im_mem_ref
*ref
, dep_kind kind
)
164 unsigned first_bit
= 6 * loop
->num
+ kind
* 2;
165 if (bitmap_bit_p (&ref
->dep_loop
, first_bit
))
166 return dep_independent
;
167 else if (bitmap_bit_p (&ref
->dep_loop
, first_bit
+ 1))
168 return dep_dependent
;
172 /* Mem_ref hashtable helpers. */
174 struct mem_ref_hasher
: nofree_ptr_hash
<im_mem_ref
>
176 typedef ao_ref
*compare_type
;
177 static inline hashval_t
hash (const im_mem_ref
*);
178 static inline bool equal (const im_mem_ref
*, const ao_ref
*);
181 /* A hash function for class im_mem_ref object OBJ. */
184 mem_ref_hasher::hash (const im_mem_ref
*mem
)
189 /* An equality function for class im_mem_ref object MEM1 with
190 memory reference OBJ2. */
193 mem_ref_hasher::equal (const im_mem_ref
*mem1
, const ao_ref
*obj2
)
195 if (obj2
->max_size_known_p ())
196 return (mem1
->ref_decomposed
197 && operand_equal_p (mem1
->mem
.base
, obj2
->base
, 0)
198 && known_eq (mem1
->mem
.offset
, obj2
->offset
)
199 && known_eq (mem1
->mem
.size
, obj2
->size
)
200 && known_eq (mem1
->mem
.max_size
, obj2
->max_size
)
201 && mem1
->mem
.volatile_p
== obj2
->volatile_p
202 && (mem1
->mem
.ref_alias_set
== obj2
->ref_alias_set
203 /* We are not canonicalizing alias-sets but for the
204 special-case we didn't canonicalize yet and the
205 incoming ref is a alias-set zero MEM we pick
206 the correct one already. */
207 || (!mem1
->ref_canonical
208 && (TREE_CODE (obj2
->ref
) == MEM_REF
209 || TREE_CODE (obj2
->ref
) == TARGET_MEM_REF
)
210 && obj2
->ref_alias_set
== 0)
211 /* Likewise if there's a canonical ref with alias-set zero. */
212 || (mem1
->ref_canonical
&& mem1
->mem
.ref_alias_set
== 0))
213 && types_compatible_p (TREE_TYPE (mem1
->mem
.ref
),
214 TREE_TYPE (obj2
->ref
)));
216 return operand_equal_p (mem1
->mem
.ref
, obj2
->ref
, 0);
220 /* Description of memory accesses in loops. */
224 /* The hash table of memory references accessed in loops. */
225 hash_table
<mem_ref_hasher
> *refs
;
227 /* The list of memory references. */
228 vec
<im_mem_ref
*> refs_list
;
230 /* The set of memory references accessed in each loop. */
231 vec
<bitmap_head
> refs_loaded_in_loop
;
233 /* The set of memory references stored in each loop. */
234 vec
<bitmap_head
> refs_stored_in_loop
;
236 /* The set of memory references stored in each loop, including subloops . */
237 vec
<bitmap_head
> all_refs_stored_in_loop
;
239 /* Cache for expanding memory addresses. */
240 hash_map
<tree
, name_expansion
*> *ttae_cache
;
243 /* Obstack for the bitmaps in the above data structures. */
244 static bitmap_obstack lim_bitmap_obstack
;
245 static obstack mem_ref_obstack
;
247 static bool ref_indep_loop_p (class loop
*, im_mem_ref
*, dep_kind
);
248 static bool ref_always_accessed_p (class loop
*, im_mem_ref
*, bool);
249 static bool refs_independent_p (im_mem_ref
*, im_mem_ref
*, bool = true);
251 /* Minimum cost of an expensive expression. */
252 #define LIM_EXPENSIVE ((unsigned) param_lim_expensive)
254 /* The outermost loop for which execution of the header guarantees that the
255 block will be executed. */
256 #define ALWAYS_EXECUTED_IN(BB) ((class loop *) (BB)->aux)
257 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
259 /* ID of the shared unanalyzable mem. */
260 #define UNANALYZABLE_MEM_ID 0
262 /* Whether the reference was analyzable. */
263 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
265 static struct lim_aux_data
*
266 init_lim_data (gimple
*stmt
)
268 lim_aux_data
*p
= XCNEW (struct lim_aux_data
);
269 lim_aux_data_map
->put (stmt
, p
);
274 static struct lim_aux_data
*
275 get_lim_data (gimple
*stmt
)
277 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
284 /* Releases the memory occupied by DATA. */
287 free_lim_aux_data (struct lim_aux_data
*data
)
289 data
->depends
.release ();
294 clear_lim_data (gimple
*stmt
)
296 lim_aux_data
**p
= lim_aux_data_map
->get (stmt
);
300 free_lim_aux_data (*p
);
305 /* The possibilities of statement movement. */
308 MOVE_IMPOSSIBLE
, /* No movement -- side effect expression. */
309 MOVE_PRESERVE_EXECUTION
, /* Must not cause the non-executed statement
310 become executed -- memory accesses, ... */
311 MOVE_POSSIBLE
/* Unlimited movement. */
315 /* If it is possible to hoist the statement STMT unconditionally,
316 returns MOVE_POSSIBLE.
317 If it is possible to hoist the statement STMT, but we must avoid making
318 it executed if it would not be executed in the original program (e.g.
319 because it may trap), return MOVE_PRESERVE_EXECUTION.
320 Otherwise return MOVE_IMPOSSIBLE. */
323 movement_possibility (gimple
*stmt
)
326 enum move_pos ret
= MOVE_POSSIBLE
;
328 if (flag_unswitch_loops
329 && gimple_code (stmt
) == GIMPLE_COND
)
331 /* If we perform unswitching, force the operands of the invariant
332 condition to be moved out of the loop. */
333 return MOVE_POSSIBLE
;
336 if (gimple_code (stmt
) == GIMPLE_PHI
337 && gimple_phi_num_args (stmt
) <= 2
338 && !virtual_operand_p (gimple_phi_result (stmt
))
339 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
340 return MOVE_POSSIBLE
;
342 if (gimple_get_lhs (stmt
) == NULL_TREE
)
343 return MOVE_IMPOSSIBLE
;
345 if (gimple_vdef (stmt
))
346 return MOVE_IMPOSSIBLE
;
348 if (stmt_ends_bb_p (stmt
)
349 || gimple_has_volatile_ops (stmt
)
350 || gimple_has_side_effects (stmt
)
351 || stmt_could_throw_p (cfun
, stmt
))
352 return MOVE_IMPOSSIBLE
;
354 if (is_gimple_call (stmt
))
356 /* While pure or const call is guaranteed to have no side effects, we
357 cannot move it arbitrarily. Consider code like
359 char *s = something ();
369 Here the strlen call cannot be moved out of the loop, even though
370 s is invariant. In addition to possibly creating a call with
371 invalid arguments, moving out a function call that is not executed
372 may cause performance regressions in case the call is costly and
373 not executed at all. */
374 ret
= MOVE_PRESERVE_EXECUTION
;
375 lhs
= gimple_call_lhs (stmt
);
377 else if (is_gimple_assign (stmt
))
378 lhs
= gimple_assign_lhs (stmt
);
380 return MOVE_IMPOSSIBLE
;
382 if (TREE_CODE (lhs
) == SSA_NAME
383 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
384 return MOVE_IMPOSSIBLE
;
386 if (TREE_CODE (lhs
) != SSA_NAME
387 || gimple_could_trap_p (stmt
))
388 return MOVE_PRESERVE_EXECUTION
;
390 /* Non local loads in a transaction cannot be hoisted out. Well,
391 unless the load happens on every path out of the loop, but we
392 don't take this into account yet. */
394 && gimple_in_transaction (stmt
)
395 && gimple_assign_single_p (stmt
))
397 tree rhs
= gimple_assign_rhs1 (stmt
);
398 if (DECL_P (rhs
) && is_global_var (rhs
))
402 fprintf (dump_file
, "Cannot hoist conditional load of ");
403 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
404 fprintf (dump_file
, " because it is in a transaction.\n");
406 return MOVE_IMPOSSIBLE
;
413 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
414 loop to that we could move the expression using DEF if it did not have
415 other operands, i.e. the outermost loop enclosing LOOP in that the value
416 of DEF is invariant. */
419 outermost_invariant_loop (tree def
, class loop
*loop
)
423 class loop
*max_loop
;
424 struct lim_aux_data
*lim_data
;
427 return superloop_at_depth (loop
, 1);
429 if (TREE_CODE (def
) != SSA_NAME
)
431 gcc_assert (is_gimple_min_invariant (def
));
432 return superloop_at_depth (loop
, 1);
435 def_stmt
= SSA_NAME_DEF_STMT (def
);
436 def_bb
= gimple_bb (def_stmt
);
438 return superloop_at_depth (loop
, 1);
440 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
442 lim_data
= get_lim_data (def_stmt
);
443 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
444 max_loop
= find_common_loop (max_loop
,
445 loop_outer (lim_data
->max_loop
));
446 if (max_loop
== loop
)
448 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
453 /* DATA is a structure containing information associated with a statement
454 inside LOOP. DEF is one of the operands of this statement.
456 Find the outermost loop enclosing LOOP in that value of DEF is invariant
457 and record this in DATA->max_loop field. If DEF itself is defined inside
458 this loop as well (i.e. we need to hoist it out of the loop if we want
459 to hoist the statement represented by DATA), record the statement in that
460 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
461 add the cost of the computation of DEF to the DATA->cost.
463 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
466 add_dependency (tree def
, struct lim_aux_data
*data
, class loop
*loop
,
469 gimple
*def_stmt
= SSA_NAME_DEF_STMT (def
);
470 basic_block def_bb
= gimple_bb (def_stmt
);
471 class loop
*max_loop
;
472 struct lim_aux_data
*def_data
;
477 max_loop
= outermost_invariant_loop (def
, loop
);
481 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
482 data
->max_loop
= max_loop
;
484 def_data
= get_lim_data (def_stmt
);
489 /* Only add the cost if the statement defining DEF is inside LOOP,
490 i.e. if it is likely that by moving the invariants dependent
491 on it, we will be able to avoid creating a new register for
492 it (since it will be only used in these dependent invariants). */
493 && def_bb
->loop_father
== loop
)
494 data
->cost
+= def_data
->cost
;
496 data
->depends
.safe_push (def_stmt
);
501 /* Returns an estimate for a cost of statement STMT. The values here
502 are just ad-hoc constants, similar to costs for inlining. */
505 stmt_cost (gimple
*stmt
)
507 /* Always try to create possibilities for unswitching. */
508 if (gimple_code (stmt
) == GIMPLE_COND
509 || gimple_code (stmt
) == GIMPLE_PHI
)
510 return LIM_EXPENSIVE
;
512 /* We should be hoisting calls if possible. */
513 if (is_gimple_call (stmt
))
517 /* Unless the call is a builtin_constant_p; this always folds to a
518 constant, so moving it is useless. */
519 fndecl
= gimple_call_fndecl (stmt
);
520 if (fndecl
&& fndecl_built_in_p (fndecl
, BUILT_IN_CONSTANT_P
))
523 return LIM_EXPENSIVE
;
526 /* Hoisting memory references out should almost surely be a win. */
527 if (gimple_references_memory_p (stmt
))
528 return LIM_EXPENSIVE
;
530 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
533 switch (gimple_assign_rhs_code (stmt
))
536 case WIDEN_MULT_EXPR
:
537 case WIDEN_MULT_PLUS_EXPR
:
538 case WIDEN_MULT_MINUS_EXPR
:
550 /* Division and multiplication are usually expensive. */
551 return LIM_EXPENSIVE
;
555 case WIDEN_LSHIFT_EXPR
:
558 /* Shifts and rotates are usually expensive. */
559 return LIM_EXPENSIVE
;
562 /* Make vector construction cost proportional to the number
564 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
568 /* Whether or not something is wrapped inside a PAREN_EXPR
569 should not change move cost. Nor should an intermediate
570 unpropagated SSA name copy. */
578 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
579 REF is independent. If REF is not independent in LOOP, NULL is returned
583 outermost_indep_loop (class loop
*outer
, class loop
*loop
, im_mem_ref
*ref
)
587 if (ref
->stored
&& bitmap_bit_p (ref
->stored
, loop
->num
))
592 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
593 if ((!ref
->stored
|| !bitmap_bit_p (ref
->stored
, aloop
->num
))
594 && ref_indep_loop_p (aloop
, ref
, lim_raw
))
597 if (ref_indep_loop_p (loop
, ref
, lim_raw
))
603 /* If there is a simple load or store to a memory reference in STMT, returns
604 the location of the memory reference, and sets IS_STORE according to whether
605 it is a store or load. Otherwise, returns NULL. */
608 simple_mem_ref_in_stmt (gimple
*stmt
, bool *is_store
)
612 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
613 if (!gimple_assign_single_p (stmt
))
616 lhs
= gimple_assign_lhs_ptr (stmt
);
617 rhs
= gimple_assign_rhs1_ptr (stmt
);
619 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
624 else if (gimple_vdef (stmt
)
625 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
634 /* From a controlling predicate in DOM determine the arguments from
635 the PHI node PHI that are chosen if the predicate evaluates to
636 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
637 they are non-NULL. Returns true if the arguments can be determined,
638 else return false. */
641 extract_true_false_args_from_phi (basic_block dom
, gphi
*phi
,
642 tree
*true_arg_p
, tree
*false_arg_p
)
645 if (! extract_true_false_controlled_edges (dom
, gimple_bb (phi
),
650 *true_arg_p
= PHI_ARG_DEF (phi
, te
->dest_idx
);
652 *false_arg_p
= PHI_ARG_DEF (phi
, fe
->dest_idx
);
657 /* Determine the outermost loop to that it is possible to hoist a statement
658 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
659 the outermost loop in that the value computed by STMT is invariant.
660 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
661 we preserve the fact whether STMT is executed. It also fills other related
662 information to LIM_DATA (STMT).
664 The function returns false if STMT cannot be hoisted outside of the loop it
665 is defined in, and true otherwise. */
668 determine_max_movement (gimple
*stmt
, bool must_preserve_exec
)
670 basic_block bb
= gimple_bb (stmt
);
671 class loop
*loop
= bb
->loop_father
;
673 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
677 if (must_preserve_exec
)
678 level
= ALWAYS_EXECUTED_IN (bb
);
680 level
= superloop_at_depth (loop
, 1);
681 lim_data
->max_loop
= level
;
683 if (gphi
*phi
= dyn_cast
<gphi
*> (stmt
))
686 unsigned min_cost
= UINT_MAX
;
687 unsigned total_cost
= 0;
688 struct lim_aux_data
*def_data
;
690 /* We will end up promoting dependencies to be unconditionally
691 evaluated. For this reason the PHI cost (and thus the
692 cost we remove from the loop by doing the invariant motion)
693 is that of the cheapest PHI argument dependency chain. */
694 FOR_EACH_PHI_ARG (use_p
, phi
, iter
, SSA_OP_USE
)
696 val
= USE_FROM_PTR (use_p
);
698 if (TREE_CODE (val
) != SSA_NAME
)
700 /* Assign const 1 to constants. */
701 min_cost
= MIN (min_cost
, 1);
705 if (!add_dependency (val
, lim_data
, loop
, false))
708 gimple
*def_stmt
= SSA_NAME_DEF_STMT (val
);
709 if (gimple_bb (def_stmt
)
710 && gimple_bb (def_stmt
)->loop_father
== loop
)
712 def_data
= get_lim_data (def_stmt
);
715 min_cost
= MIN (min_cost
, def_data
->cost
);
716 total_cost
+= def_data
->cost
;
721 min_cost
= MIN (min_cost
, total_cost
);
722 lim_data
->cost
+= min_cost
;
724 if (gimple_phi_num_args (phi
) > 1)
726 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
728 if (gsi_end_p (gsi_last_bb (dom
)))
730 cond
= gsi_stmt (gsi_last_bb (dom
));
731 if (gimple_code (cond
) != GIMPLE_COND
)
733 /* Verify that this is an extended form of a diamond and
734 the PHI arguments are completely controlled by the
736 if (!extract_true_false_args_from_phi (dom
, phi
, NULL
, NULL
))
739 /* Fold in dependencies and cost of the condition. */
740 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
742 if (!add_dependency (val
, lim_data
, loop
, false))
744 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
746 lim_data
->cost
+= def_data
->cost
;
749 /* We want to avoid unconditionally executing very expensive
750 operations. As costs for our dependencies cannot be
751 negative just claim we are not invariand for this case.
752 We also are not sure whether the control-flow inside the
754 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
756 && total_cost
/ min_cost
<= 2))
759 /* Assume that the control-flow in the loop will vanish.
760 ??? We should verify this and not artificially increase
761 the cost if that is not the case. */
762 lim_data
->cost
+= stmt_cost (stmt
);
768 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
769 if (!add_dependency (val
, lim_data
, loop
, true))
772 if (gimple_vuse (stmt
))
775 = lim_data
? memory_accesses
.refs_list
[lim_data
->ref
] : NULL
;
777 && MEM_ANALYZABLE (ref
))
779 lim_data
->max_loop
= outermost_indep_loop (lim_data
->max_loop
,
781 if (!lim_data
->max_loop
)
784 else if (! add_dependency (gimple_vuse (stmt
), lim_data
, loop
, false))
788 lim_data
->cost
+= stmt_cost (stmt
);
793 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
794 and that one of the operands of this statement is computed by STMT.
795 Ensure that STMT (together with all the statements that define its
796 operands) is hoisted at least out of the loop LEVEL. */
799 set_level (gimple
*stmt
, class loop
*orig_loop
, class loop
*level
)
801 class loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
802 struct lim_aux_data
*lim_data
;
806 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
807 lim_data
= get_lim_data (stmt
);
808 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
809 stmt_loop
= find_common_loop (stmt_loop
,
810 loop_outer (lim_data
->tgt_loop
));
811 if (flow_loop_nested_p (stmt_loop
, level
))
814 gcc_assert (level
== lim_data
->max_loop
815 || flow_loop_nested_p (lim_data
->max_loop
, level
));
817 lim_data
->tgt_loop
= level
;
818 FOR_EACH_VEC_ELT (lim_data
->depends
, i
, dep_stmt
)
819 set_level (dep_stmt
, orig_loop
, level
);
822 /* Determines an outermost loop from that we want to hoist the statement STMT.
823 For now we chose the outermost possible loop. TODO -- use profiling
824 information to set it more sanely. */
827 set_profitable_level (gimple
*stmt
)
829 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
832 /* Returns true if STMT is a call that has side effects. */
835 nonpure_call_p (gimple
*stmt
)
837 if (gimple_code (stmt
) != GIMPLE_CALL
)
840 return gimple_has_side_effects (stmt
);
843 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
846 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
848 gassign
*stmt
, *stmt1
, *stmt2
;
849 tree name
, lhs
, type
;
851 gimple_stmt_iterator gsi
;
853 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
854 lhs
= gimple_assign_lhs (stmt
);
855 type
= TREE_TYPE (lhs
);
857 real_one
= build_one_cst (type
);
859 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
860 stmt1
= gimple_build_assign (name
, RDIV_EXPR
, real_one
,
861 gimple_assign_rhs2 (stmt
));
862 stmt2
= gimple_build_assign (lhs
, MULT_EXPR
, name
,
863 gimple_assign_rhs1 (stmt
));
865 /* Replace division stmt with reciprocal and multiply stmts.
866 The multiply stmt is not invariant, so update iterator
867 and avoid rescanning. */
869 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
870 gsi_replace (&gsi
, stmt2
, true);
872 /* Continue processing with invariant reciprocal statement. */
876 /* Check if the pattern at *BSI is a bittest of the form
877 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
880 rewrite_bittest (gimple_stmt_iterator
*bsi
)
887 tree lhs
, name
, t
, a
, b
;
890 stmt
= as_a
<gassign
*> (gsi_stmt (*bsi
));
891 lhs
= gimple_assign_lhs (stmt
);
893 /* Verify that the single use of lhs is a comparison against zero. */
894 if (TREE_CODE (lhs
) != SSA_NAME
895 || !single_imm_use (lhs
, &use
, &use_stmt
))
897 cond_stmt
= dyn_cast
<gcond
*> (use_stmt
);
900 if (gimple_cond_lhs (cond_stmt
) != lhs
901 || (gimple_cond_code (cond_stmt
) != NE_EXPR
902 && gimple_cond_code (cond_stmt
) != EQ_EXPR
)
903 || !integer_zerop (gimple_cond_rhs (cond_stmt
)))
906 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
907 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
908 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
911 /* There is a conversion in between possibly inserted by fold. */
912 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
914 t
= gimple_assign_rhs1 (stmt1
);
915 if (TREE_CODE (t
) != SSA_NAME
916 || !has_single_use (t
))
918 stmt1
= SSA_NAME_DEF_STMT (t
);
919 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
923 /* Verify that B is loop invariant but A is not. Verify that with
924 all the stmt walking we are still in the same loop. */
925 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
926 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
929 a
= gimple_assign_rhs1 (stmt1
);
930 b
= gimple_assign_rhs2 (stmt1
);
932 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
933 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
935 gimple_stmt_iterator rsi
;
938 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
939 build_int_cst (TREE_TYPE (a
), 1), b
);
940 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
941 stmt1
= gimple_build_assign (name
, t
);
944 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
945 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
946 stmt2
= gimple_build_assign (name
, t
);
948 /* Replace the SSA_NAME we compare against zero. Adjust
949 the type of zero accordingly. */
951 gimple_cond_set_rhs (cond_stmt
,
952 build_int_cst_type (TREE_TYPE (name
),
955 /* Don't use gsi_replace here, none of the new assignments sets
956 the variable originally set in stmt. Move bsi to stmt1, and
957 then remove the original stmt, so that we get a chance to
958 retain debug info for it. */
960 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
961 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
962 gimple
*to_release
= gsi_stmt (rsi
);
963 gsi_remove (&rsi
, true);
964 release_defs (to_release
);
972 /* Determine the outermost loops in that statements in basic block BB are
973 invariant, and record them to the LIM_DATA associated with the
977 compute_invariantness (basic_block bb
)
980 gimple_stmt_iterator bsi
;
982 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
983 class loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
984 struct lim_aux_data
*lim_data
;
986 if (!loop_outer (bb
->loop_father
))
989 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
990 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
991 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
993 /* Look at PHI nodes, but only if there is at most two.
994 ??? We could relax this further by post-processing the inserted
995 code and transforming adjacent cond-exprs with the same predicate
996 to control flow again. */
997 bsi
= gsi_start_phis (bb
);
999 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1000 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1001 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1003 stmt
= gsi_stmt (bsi
);
1005 pos
= movement_possibility (stmt
);
1006 if (pos
== MOVE_IMPOSSIBLE
)
1009 lim_data
= get_lim_data (stmt
);
1011 lim_data
= init_lim_data (stmt
);
1012 lim_data
->always_executed_in
= outermost
;
1014 if (!determine_max_movement (stmt
, false))
1016 lim_data
->max_loop
= NULL
;
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1022 print_gimple_stmt (dump_file
, stmt
, 2);
1023 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1024 loop_depth (lim_data
->max_loop
),
1028 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1029 set_profitable_level (stmt
);
1032 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1034 stmt
= gsi_stmt (bsi
);
1036 pos
= movement_possibility (stmt
);
1037 if (pos
== MOVE_IMPOSSIBLE
)
1039 if (nonpure_call_p (stmt
))
1044 /* Make sure to note always_executed_in for stores to make
1045 store-motion work. */
1046 else if (stmt_makes_single_store (stmt
))
1048 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
1050 lim_data
= init_lim_data (stmt
);
1051 lim_data
->always_executed_in
= outermost
;
1056 if (is_gimple_assign (stmt
)
1057 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1058 == GIMPLE_BINARY_RHS
))
1060 tree op0
= gimple_assign_rhs1 (stmt
);
1061 tree op1
= gimple_assign_rhs2 (stmt
);
1062 class loop
*ol1
= outermost_invariant_loop (op1
,
1063 loop_containing_stmt (stmt
));
1065 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1066 to be hoisted out of loop, saving expensive divide. */
1067 if (pos
== MOVE_POSSIBLE
1068 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1069 && flag_unsafe_math_optimizations
1070 && !flag_trapping_math
1072 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1073 stmt
= rewrite_reciprocal (&bsi
);
1075 /* If the shift count is invariant, convert (A >> B) & 1 to
1076 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1077 saving an expensive shift. */
1078 if (pos
== MOVE_POSSIBLE
1079 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1080 && integer_onep (op1
)
1081 && TREE_CODE (op0
) == SSA_NAME
1082 && has_single_use (op0
))
1083 stmt
= rewrite_bittest (&bsi
);
1086 lim_data
= get_lim_data (stmt
);
1088 lim_data
= init_lim_data (stmt
);
1089 lim_data
->always_executed_in
= outermost
;
1091 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1094 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1096 lim_data
->max_loop
= NULL
;
1100 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1102 print_gimple_stmt (dump_file
, stmt
, 2);
1103 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1104 loop_depth (lim_data
->max_loop
),
1108 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1109 set_profitable_level (stmt
);
1113 /* Hoist the statements in basic block BB out of the loops prescribed by
1114 data stored in LIM_DATA structures associated with each statement. Callback
1115 for walk_dominator_tree. */
1118 move_computations_worker (basic_block bb
)
1122 struct lim_aux_data
*lim_data
;
1123 unsigned int todo
= 0;
1125 if (!loop_outer (bb
->loop_father
))
1128 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1131 gphi
*stmt
= bsi
.phi ();
1133 lim_data
= get_lim_data (stmt
);
1134 if (lim_data
== NULL
)
1140 cost
= lim_data
->cost
;
1141 level
= lim_data
->tgt_loop
;
1142 clear_lim_data (stmt
);
1150 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1152 fprintf (dump_file
, "Moving PHI node\n");
1153 print_gimple_stmt (dump_file
, stmt
, 0);
1154 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1158 if (gimple_phi_num_args (stmt
) == 1)
1160 tree arg
= PHI_ARG_DEF (stmt
, 0);
1161 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1162 TREE_CODE (arg
), arg
);
1166 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1167 gimple
*cond
= gsi_stmt (gsi_last_bb (dom
));
1168 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1169 /* Get the PHI arguments corresponding to the true and false
1171 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1172 gcc_assert (arg0
&& arg1
);
1173 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1174 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1175 new_stmt
= gimple_build_assign (gimple_phi_result (stmt
),
1176 COND_EXPR
, t
, arg0
, arg1
);
1177 todo
|= TODO_cleanup_cfg
;
1179 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt
)))
1180 && (!ALWAYS_EXECUTED_IN (bb
)
1181 || (ALWAYS_EXECUTED_IN (bb
) != level
1182 && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1184 tree lhs
= gimple_assign_lhs (new_stmt
);
1185 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1187 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1188 remove_phi_node (&bsi
, false);
1191 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1195 gimple
*stmt
= gsi_stmt (bsi
);
1197 lim_data
= get_lim_data (stmt
);
1198 if (lim_data
== NULL
)
1204 cost
= lim_data
->cost
;
1205 level
= lim_data
->tgt_loop
;
1206 clear_lim_data (stmt
);
1214 /* We do not really want to move conditionals out of the loop; we just
1215 placed it here to force its operands to be moved if necessary. */
1216 if (gimple_code (stmt
) == GIMPLE_COND
)
1219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1221 fprintf (dump_file
, "Moving statement\n");
1222 print_gimple_stmt (dump_file
, stmt
, 0);
1223 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1227 e
= loop_preheader_edge (level
);
1228 gcc_assert (!gimple_vdef (stmt
));
1229 if (gimple_vuse (stmt
))
1231 /* The new VUSE is the one from the virtual PHI in the loop
1232 header or the one already present. */
1234 for (gsi2
= gsi_start_phis (e
->dest
);
1235 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1237 gphi
*phi
= gsi2
.phi ();
1238 if (virtual_operand_p (gimple_phi_result (phi
)))
1240 SET_USE (gimple_vuse_op (stmt
),
1241 PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1246 gsi_remove (&bsi
, false);
1247 if (gimple_has_lhs (stmt
)
1248 && TREE_CODE (gimple_get_lhs (stmt
)) == SSA_NAME
1249 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt
)))
1250 && (!ALWAYS_EXECUTED_IN (bb
)
1251 || !(ALWAYS_EXECUTED_IN (bb
) == level
1252 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1254 tree lhs
= gimple_get_lhs (stmt
);
1255 SSA_NAME_RANGE_INFO (lhs
) = NULL
;
1257 /* In case this is a stmt that is not unconditionally executed
1258 when the target loop header is executed and the stmt may
1259 invoke undefined integer or pointer overflow rewrite it to
1260 unsigned arithmetic. */
1261 if (is_gimple_assign (stmt
)
1262 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
)))
1263 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt
)))
1264 && arith_code_with_undefined_signed_overflow
1265 (gimple_assign_rhs_code (stmt
))
1266 && (!ALWAYS_EXECUTED_IN (bb
)
1267 || !(ALWAYS_EXECUTED_IN (bb
) == level
1268 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1269 gsi_insert_seq_on_edge (e
, rewrite_to_defined_overflow (stmt
));
1271 gsi_insert_on_edge (e
, stmt
);
1277 /* Checks whether the statement defining variable *INDEX can be hoisted
1278 out of the loop passed in DATA. Callback for for_each_index. */
1281 may_move_till (tree ref
, tree
*index
, void *data
)
1283 class loop
*loop
= (class loop
*) data
, *max_loop
;
1285 /* If REF is an array reference, check also that the step and the lower
1286 bound is invariant in LOOP. */
1287 if (TREE_CODE (ref
) == ARRAY_REF
)
1289 tree step
= TREE_OPERAND (ref
, 3);
1290 tree lbound
= TREE_OPERAND (ref
, 2);
1292 max_loop
= outermost_invariant_loop (step
, loop
);
1296 max_loop
= outermost_invariant_loop (lbound
, loop
);
1301 max_loop
= outermost_invariant_loop (*index
, loop
);
1308 /* If OP is SSA NAME, force the statement that defines it to be
1309 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1312 force_move_till_op (tree op
, class loop
*orig_loop
, class loop
*loop
)
1317 || is_gimple_min_invariant (op
))
1320 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1322 stmt
= SSA_NAME_DEF_STMT (op
);
1323 if (gimple_nop_p (stmt
))
1326 set_level (stmt
, orig_loop
, loop
);
1329 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1330 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1336 class loop
*orig_loop
;
1340 force_move_till (tree ref
, tree
*index
, void *data
)
1342 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1344 if (TREE_CODE (ref
) == ARRAY_REF
)
1346 tree step
= TREE_OPERAND (ref
, 3);
1347 tree lbound
= TREE_OPERAND (ref
, 2);
1349 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1350 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1353 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1358 /* A function to free the mem_ref object OBJ. */
1361 memref_free (class im_mem_ref
*mem
)
1363 mem
->accesses_in_loop
.release ();
1366 /* Allocates and returns a memory reference description for MEM whose hash
1367 value is HASH and id is ID. */
1370 mem_ref_alloc (ao_ref
*mem
, unsigned hash
, unsigned id
)
1372 im_mem_ref
*ref
= XOBNEW (&mem_ref_obstack
, class im_mem_ref
);
1376 ao_ref_init (&ref
->mem
, error_mark_node
);
1378 ref
->ref_canonical
= false;
1379 ref
->ref_decomposed
= false;
1383 bitmap_initialize (&ref
->dep_loop
, &lim_bitmap_obstack
);
1384 ref
->accesses_in_loop
.create (1);
1389 /* Records memory reference location *LOC in LOOP to the memory reference
1390 description REF. The reference occurs in statement STMT. */
1393 record_mem_ref_loc (im_mem_ref
*ref
, gimple
*stmt
, tree
*loc
)
1398 ref
->accesses_in_loop
.safe_push (aref
);
1401 /* Set the LOOP bit in REF stored bitmap and allocate that if
1402 necessary. Return whether a bit was changed. */
1405 set_ref_stored_in_loop (im_mem_ref
*ref
, class loop
*loop
)
1408 ref
->stored
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1409 return bitmap_set_bit (ref
->stored
, loop
->num
);
1412 /* Marks reference REF as stored in LOOP. */
1415 mark_ref_stored (im_mem_ref
*ref
, class loop
*loop
)
1417 while (loop
!= current_loops
->tree_root
1418 && set_ref_stored_in_loop (ref
, loop
))
1419 loop
= loop_outer (loop
);
1422 /* Set the LOOP bit in REF loaded bitmap and allocate that if
1423 necessary. Return whether a bit was changed. */
1426 set_ref_loaded_in_loop (im_mem_ref
*ref
, class loop
*loop
)
1429 ref
->loaded
= BITMAP_ALLOC (&lim_bitmap_obstack
);
1430 return bitmap_set_bit (ref
->loaded
, loop
->num
);
1433 /* Marks reference REF as loaded in LOOP. */
1436 mark_ref_loaded (im_mem_ref
*ref
, class loop
*loop
)
1438 while (loop
!= current_loops
->tree_root
1439 && set_ref_loaded_in_loop (ref
, loop
))
1440 loop
= loop_outer (loop
);
1443 /* Gathers memory references in statement STMT in LOOP, storing the
1444 information about them in the memory_accesses structure. Marks
1445 the vops accessed through unrecognized statements there as
1449 gather_mem_refs_stmt (class loop
*loop
, gimple
*stmt
)
1458 if (!gimple_vuse (stmt
))
1461 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1464 /* We use the shared mem_ref for all unanalyzable refs. */
1465 id
= UNANALYZABLE_MEM_ID
;
1466 ref
= memory_accesses
.refs_list
[id
];
1467 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1469 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1470 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1472 is_stored
= gimple_vdef (stmt
);
1476 /* We are looking for equal refs that might differ in structure
1477 such as a.b vs. MEM[&a + 4]. So we key off the ao_ref but
1478 make sure we can canonicalize the ref in the hashtable if
1479 non-operand_equal_p refs are found. For the lookup we mark
1480 the case we want strict equality with aor.max_size == -1. */
1482 ao_ref_init (&aor
, *mem
);
1484 ao_ref_alias_set (&aor
);
1485 HOST_WIDE_INT offset
, size
, max_size
;
1486 poly_int64 saved_maxsize
= aor
.max_size
, mem_off
;
1488 bool ref_decomposed
;
1489 if (aor
.max_size_known_p ()
1490 && aor
.offset
.is_constant (&offset
)
1491 && aor
.size
.is_constant (&size
)
1492 && aor
.max_size
.is_constant (&max_size
)
1494 && (size
% BITS_PER_UNIT
) == 0
1495 /* We're canonicalizing to a MEM where TYPE_SIZE specifies the
1496 size. Make sure this is consistent with the extraction. */
1497 && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (*mem
)))
1498 && known_eq (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (*mem
))),
1500 && (mem_base
= get_addr_base_and_unit_offset (aor
.ref
, &mem_off
)))
1502 ref_decomposed
= true;
1503 hash
= iterative_hash_expr (ao_ref_base (&aor
), 0);
1504 hash
= iterative_hash_host_wide_int (offset
, hash
);
1505 hash
= iterative_hash_host_wide_int (size
, hash
);
1509 ref_decomposed
= false;
1510 hash
= iterative_hash_expr (aor
.ref
, 0);
1513 slot
= memory_accesses
.refs
->find_slot_with_hash (&aor
, hash
, INSERT
);
1514 aor
.max_size
= saved_maxsize
;
1517 if (!(*slot
)->ref_canonical
1518 && !operand_equal_p (*mem
, (*slot
)->mem
.ref
, 0))
1520 /* If we didn't yet canonicalize the hashtable ref (which
1521 we'll end up using for code insertion) and hit a second
1522 equal ref that is not structurally equivalent create
1523 a canonical ref which is a bare MEM_REF. */
1524 if (TREE_CODE (*mem
) == MEM_REF
1525 || TREE_CODE (*mem
) == TARGET_MEM_REF
)
1527 (*slot
)->mem
.ref
= *mem
;
1528 (*slot
)->mem
.base_alias_set
= ao_ref_base_alias_set (&aor
);
1532 tree ref_alias_type
= reference_alias_ptr_type (*mem
);
1533 unsigned int ref_align
= get_object_alignment (*mem
);
1534 tree ref_type
= TREE_TYPE (*mem
);
1535 tree tmp
= build1 (ADDR_EXPR
, ptr_type_node
,
1536 unshare_expr (mem_base
));
1537 if (TYPE_ALIGN (ref_type
) != ref_align
)
1538 ref_type
= build_aligned_type (ref_type
, ref_align
);
1540 = fold_build2 (MEM_REF
, ref_type
, tmp
,
1541 build_int_cst (ref_alias_type
, mem_off
));
1542 if ((*slot
)->mem
.volatile_p
)
1543 TREE_THIS_VOLATILE ((*slot
)->mem
.ref
) = 1;
1544 gcc_checking_assert (TREE_CODE ((*slot
)->mem
.ref
) == MEM_REF
1545 && is_gimple_mem_ref_addr
1546 (TREE_OPERAND ((*slot
)->mem
.ref
,
1548 (*slot
)->mem
.base_alias_set
= (*slot
)->mem
.ref_alias_set
;
1550 (*slot
)->ref_canonical
= true;
1557 id
= memory_accesses
.refs_list
.length ();
1558 ref
= mem_ref_alloc (&aor
, hash
, id
);
1559 ref
->ref_decomposed
= ref_decomposed
;
1560 memory_accesses
.refs_list
.safe_push (ref
);
1563 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1565 fprintf (dump_file
, "Memory reference %u: ", id
);
1566 print_generic_expr (dump_file
, ref
->mem
.ref
, TDF_SLIM
);
1567 fprintf (dump_file
, "\n");
1571 record_mem_ref_loc (ref
, stmt
, mem
);
1575 bitmap_set_bit (&memory_accesses
.refs_stored_in_loop
[loop
->num
], ref
->id
);
1576 mark_ref_stored (ref
, loop
);
1578 /* A not simple memory op is also a read when it is a write. */
1579 if (!is_stored
|| id
== UNANALYZABLE_MEM_ID
)
1581 bitmap_set_bit (&memory_accesses
.refs_loaded_in_loop
[loop
->num
], ref
->id
);
1582 mark_ref_loaded (ref
, loop
);
1584 init_lim_data (stmt
)->ref
= ref
->id
;
1588 static unsigned *bb_loop_postorder
;
1590 /* qsort sort function to sort blocks after their loop fathers postorder. */
1593 sort_bbs_in_loop_postorder_cmp (const void *bb1_
, const void *bb2_
,
1594 void *bb_loop_postorder_
)
1596 unsigned *bb_loop_postorder
= (unsigned *)bb_loop_postorder_
;
1597 basic_block bb1
= *(const basic_block
*)bb1_
;
1598 basic_block bb2
= *(const basic_block
*)bb2_
;
1599 class loop
*loop1
= bb1
->loop_father
;
1600 class loop
*loop2
= bb2
->loop_father
;
1601 if (loop1
->num
== loop2
->num
)
1602 return bb1
->index
- bb2
->index
;
1603 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1606 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1609 sort_locs_in_loop_postorder_cmp (const void *loc1_
, const void *loc2_
,
1610 void *bb_loop_postorder_
)
1612 unsigned *bb_loop_postorder
= (unsigned *)bb_loop_postorder_
;
1613 const mem_ref_loc
*loc1
= (const mem_ref_loc
*)loc1_
;
1614 const mem_ref_loc
*loc2
= (const mem_ref_loc
*)loc2_
;
1615 class loop
*loop1
= gimple_bb (loc1
->stmt
)->loop_father
;
1616 class loop
*loop2
= gimple_bb (loc2
->stmt
)->loop_father
;
1617 if (loop1
->num
== loop2
->num
)
1619 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1622 /* Gathers memory references in loops. */
1625 analyze_memory_references (bool store_motion
)
1627 gimple_stmt_iterator bsi
;
1628 basic_block bb
, *bbs
;
1629 class loop
*loop
, *outer
;
1632 /* Collect all basic-blocks in loops and sort them after their
1635 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
1636 FOR_EACH_BB_FN (bb
, cfun
)
1637 if (bb
->loop_father
!= current_loops
->tree_root
)
1640 gcc_sort_r (bbs
, n
, sizeof (basic_block
), sort_bbs_in_loop_postorder_cmp
,
1643 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1644 That results in better locality for all the bitmaps. It also
1645 automatically sorts the location list of gathered memory references
1646 after their loop postorder number allowing to binary-search it. */
1647 for (i
= 0; i
< n
; ++i
)
1649 basic_block bb
= bbs
[i
];
1650 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1651 gather_mem_refs_stmt (bb
->loop_father
, gsi_stmt (bsi
));
1654 /* Verify the list of gathered memory references is sorted after their
1655 loop postorder number. */
1659 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
1660 for (unsigned j
= 1; j
< ref
->accesses_in_loop
.length (); ++j
)
1661 gcc_assert (sort_locs_in_loop_postorder_cmp
1662 (&ref
->accesses_in_loop
[j
-1], &ref
->accesses_in_loop
[j
],
1663 bb_loop_postorder
) <= 0);
1671 /* Propagate the information about accessed memory references up
1672 the loop hierarchy. */
1673 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1675 /* Finalize the overall touched references (including subloops). */
1676 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1677 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1679 /* Propagate the information about accessed memory references up
1680 the loop hierarchy. */
1681 outer
= loop_outer (loop
);
1682 if (outer
== current_loops
->tree_root
)
1685 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1686 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1690 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1691 tree_to_aff_combination_expand. */
1694 mem_refs_may_alias_p (im_mem_ref
*mem1
, im_mem_ref
*mem2
,
1695 hash_map
<tree
, name_expansion
*> **ttae_cache
,
1698 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1699 object and their offset differ in such a way that the locations cannot
1700 overlap, then they cannot alias. */
1701 poly_widest_int size1
, size2
;
1702 aff_tree off1
, off2
;
1704 /* Perform basic offset and type-based disambiguation. */
1705 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, tbaa_p
))
1708 /* The expansion of addresses may be a bit expensive, thus we only do
1709 the check at -O2 and higher optimization levels. */
1713 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1714 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1715 aff_combination_expand (&off1
, ttae_cache
);
1716 aff_combination_expand (&off2
, ttae_cache
);
1717 aff_combination_scale (&off1
, -1);
1718 aff_combination_add (&off2
, &off1
);
1720 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1726 /* Compare function for bsearch searching for reference locations
1730 find_ref_loc_in_loop_cmp (const void *loop_
, const void *loc_
,
1731 void *bb_loop_postorder_
)
1733 unsigned *bb_loop_postorder
= (unsigned *)bb_loop_postorder_
;
1734 class loop
*loop
= (class loop
*)const_cast<void *>(loop_
);
1735 mem_ref_loc
*loc
= (mem_ref_loc
*)const_cast<void *>(loc_
);
1736 class loop
*loc_loop
= gimple_bb (loc
->stmt
)->loop_father
;
1737 if (loop
->num
== loc_loop
->num
1738 || flow_loop_nested_p (loop
, loc_loop
))
1740 return (bb_loop_postorder
[loop
->num
] < bb_loop_postorder
[loc_loop
->num
]
1744 /* Iterates over all locations of REF in LOOP and its subloops calling
1745 fn.operator() with the location as argument. When that operator
1746 returns true the iteration is stopped and true is returned.
1747 Otherwise false is returned. */
1749 template <typename FN
>
1751 for_all_locs_in_loop (class loop
*loop
, im_mem_ref
*ref
, FN fn
)
1756 /* Search for the cluster of locs in the accesses_in_loop vector
1757 which is sorted after postorder index of the loop father. */
1758 loc
= ref
->accesses_in_loop
.bsearch (loop
, find_ref_loc_in_loop_cmp
,
1763 /* We have found one location inside loop or its sub-loops. Iterate
1764 both forward and backward to cover the whole cluster. */
1765 i
= loc
- ref
->accesses_in_loop
.address ();
1769 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1770 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1775 for (i
= loc
- ref
->accesses_in_loop
.address ();
1776 i
< ref
->accesses_in_loop
.length (); ++i
)
1778 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1779 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1788 /* Rewrites location LOC by TMP_VAR. */
1790 class rewrite_mem_ref_loc
1793 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1794 bool operator () (mem_ref_loc
*loc
);
1799 rewrite_mem_ref_loc::operator () (mem_ref_loc
*loc
)
1801 *loc
->ref
= tmp_var
;
1802 update_stmt (loc
->stmt
);
1806 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1809 rewrite_mem_refs (class loop
*loop
, im_mem_ref
*ref
, tree tmp_var
)
1811 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1814 /* Stores the first reference location in LOCP. */
1816 class first_mem_ref_loc_1
1819 first_mem_ref_loc_1 (mem_ref_loc
**locp_
) : locp (locp_
) {}
1820 bool operator () (mem_ref_loc
*loc
);
1825 first_mem_ref_loc_1::operator () (mem_ref_loc
*loc
)
1831 /* Returns the first reference location to REF in LOOP. */
1833 static mem_ref_loc
*
1834 first_mem_ref_loc (class loop
*loop
, im_mem_ref
*ref
)
1836 mem_ref_loc
*locp
= NULL
;
1837 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1841 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1844 The store is only done if MEM has changed. We do this so no
1845 changes to MEM occur on code paths that did not originally store
1848 The common case for execute_sm will transform:
1868 This function will generate:
1887 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
,
1888 edge preheader
, hash_set
<basic_block
> *flag_bbs
,
1889 edge
&append_cond_position
, edge
&last_cond_fallthru
)
1891 basic_block new_bb
, then_bb
, old_dest
;
1892 bool loop_has_only_one_exit
;
1894 gimple_stmt_iterator gsi
;
1896 bool irr
= ex
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1898 profile_count count_sum
= profile_count::zero ();
1899 int nbbs
= 0, ncount
= 0;
1900 profile_probability flag_probability
= profile_probability::uninitialized ();
1902 /* Flag is set in FLAG_BBS. Determine probability that flag will be true
1905 This code may look fancy, but it cannot update profile very realistically
1906 because we do not know the probability that flag will be true at given
1909 We look for two interesting extremes
1910 - when exit is dominated by block setting the flag, we know it will
1911 always be true. This is a common case.
1912 - when all blocks setting the flag have very low frequency we know
1913 it will likely be false.
1914 In all other cases we default to 2/3 for flag being true. */
1916 for (hash_set
<basic_block
>::iterator it
= flag_bbs
->begin ();
1917 it
!= flag_bbs
->end (); ++it
)
1919 if ((*it
)->count
.initialized_p ())
1920 count_sum
+= (*it
)->count
, ncount
++;
1921 if (dominated_by_p (CDI_DOMINATORS
, ex
->src
, *it
))
1922 flag_probability
= profile_probability::always ();
1926 profile_probability cap
= profile_probability::always ().apply_scale (2, 3);
1928 if (flag_probability
.initialized_p ())
1930 else if (ncount
== nbbs
1931 && preheader
->count () >= count_sum
&& preheader
->count ().nonzero_p ())
1933 flag_probability
= count_sum
.probability_in (preheader
->count ());
1934 if (flag_probability
> cap
)
1935 flag_probability
= cap
;
1938 if (!flag_probability
.initialized_p ())
1939 flag_probability
= cap
;
1941 /* ?? Insert store after previous store if applicable. See note
1943 if (append_cond_position
)
1944 ex
= append_cond_position
;
1946 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1948 if (loop_has_only_one_exit
)
1949 ex
= split_block_after_labels (ex
->dest
);
1952 for (gphi_iterator gpi
= gsi_start_phis (ex
->dest
);
1953 !gsi_end_p (gpi
); gsi_next (&gpi
))
1955 gphi
*phi
= gpi
.phi ();
1956 if (virtual_operand_p (gimple_phi_result (phi
)))
1959 /* When the destination has a non-virtual PHI node with multiple
1960 predecessors make sure we preserve the PHI structure by
1961 forcing a forwarder block so that hoisting of that PHI will
1968 old_dest
= ex
->dest
;
1969 new_bb
= split_edge (ex
);
1970 then_bb
= create_empty_bb (new_bb
);
1971 then_bb
->count
= new_bb
->count
.apply_probability (flag_probability
);
1973 then_bb
->flags
= BB_IRREDUCIBLE_LOOP
;
1974 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1976 gsi
= gsi_start_bb (new_bb
);
1977 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1978 NULL_TREE
, NULL_TREE
);
1979 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1981 gsi
= gsi_start_bb (then_bb
);
1982 /* Insert actual store. */
1983 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1984 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1986 edge e1
= single_succ_edge (new_bb
);
1987 edge e2
= make_edge (new_bb
, then_bb
,
1988 EDGE_TRUE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1989 e2
->probability
= flag_probability
;
1991 e1
->flags
|= EDGE_FALSE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0);
1992 e1
->flags
&= ~EDGE_FALLTHRU
;
1994 e1
->probability
= flag_probability
.invert ();
1996 then_old_edge
= make_single_succ_edge (then_bb
, old_dest
,
1997 EDGE_FALLTHRU
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1999 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
2001 if (append_cond_position
)
2003 basic_block prevbb
= last_cond_fallthru
->src
;
2004 redirect_edge_succ (last_cond_fallthru
, new_bb
);
2005 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
2006 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
2007 recompute_dominator (CDI_DOMINATORS
, old_dest
));
2010 /* ?? Because stores may alias, they must happen in the exact
2011 sequence they originally happened. Save the position right after
2012 the (_lsm) store we just created so we can continue appending after
2013 it and maintain the original order. */
2014 append_cond_position
= then_old_edge
;
2015 last_cond_fallthru
= find_edge (new_bb
, old_dest
);
2017 if (!loop_has_only_one_exit
)
2018 for (gphi_iterator gpi
= gsi_start_phis (old_dest
);
2019 !gsi_end_p (gpi
); gsi_next (&gpi
))
2021 gphi
*phi
= gpi
.phi ();
2024 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2025 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
2027 tree arg
= gimple_phi_arg_def (phi
, i
);
2028 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
2034 /* When REF is set on the location, set flag indicating the store. */
2036 class sm_set_flag_if_changed
2039 sm_set_flag_if_changed (tree flag_
, hash_set
<basic_block
> *bbs_
)
2040 : flag (flag_
), bbs (bbs_
) {}
2041 bool operator () (mem_ref_loc
*loc
);
2043 hash_set
<basic_block
> *bbs
;
2047 sm_set_flag_if_changed::operator () (mem_ref_loc
*loc
)
2049 /* Only set the flag for writes. */
2050 if (is_gimple_assign (loc
->stmt
)
2051 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
2053 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
2054 gimple
*stmt
= gimple_build_assign (flag
, boolean_true_node
);
2055 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2056 bbs
->add (gimple_bb (stmt
));
2061 /* Helper function for execute_sm. On every location where REF is
2062 set, set an appropriate flag indicating the store. */
2065 execute_sm_if_changed_flag_set (class loop
*loop
, im_mem_ref
*ref
,
2066 hash_set
<basic_block
> *bbs
)
2069 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0, "_flag");
2070 flag
= create_tmp_reg (boolean_type_node
, str
);
2071 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
, bbs
));
2079 hash_set
<basic_block
> flag_bbs
;
2082 /* Executes store motion of memory reference REF from LOOP.
2083 Exits from the LOOP are stored in EXITS. The initialization of the
2084 temporary variable is put to the preheader of the loop, and assignments
2085 to the reference from the temporary variable are emitted to exits. */
2088 execute_sm (class loop
*loop
, im_mem_ref
*ref
,
2089 hash_map
<im_mem_ref
*, sm_aux
*> &aux_map
, bool maybe_mt
)
2092 struct fmt_data fmt_data
;
2093 struct lim_aux_data
*lim_data
;
2094 bool multi_threaded_model_p
= false;
2095 gimple_stmt_iterator gsi
;
2096 sm_aux
*aux
= new sm_aux
;
2098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2100 fprintf (dump_file
, "Executing store motion of ");
2101 print_generic_expr (dump_file
, ref
->mem
.ref
);
2102 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2105 aux
->tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
2106 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
2108 fmt_data
.loop
= loop
;
2109 fmt_data
.orig_loop
= loop
;
2110 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
2112 bool always_stored
= ref_always_accessed_p (loop
, ref
, true);
2114 && (bb_in_transaction (loop_preheader_edge (loop
)->src
)
2115 || (! flag_store_data_races
&& ! always_stored
)))
2116 multi_threaded_model_p
= true;
2118 if (multi_threaded_model_p
)
2120 = execute_sm_if_changed_flag_set (loop
, ref
, &aux
->flag_bbs
);
2122 aux
->store_flag
= NULL_TREE
;
2124 /* Remember variable setup. */
2125 aux_map
.put (ref
, aux
);
2127 rewrite_mem_refs (loop
, ref
, aux
->tmp_var
);
2129 /* Emit the load code on a random exit edge or into the latch if
2130 the loop does not exit, so that we are sure it will be processed
2131 by move_computations after all dependencies. */
2132 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
2134 /* Avoid doing a load if there was no load of the ref in the loop.
2135 Esp. when the ref is not always stored we cannot optimize it
2136 away later. But when it is not always stored we must use a conditional
2138 if ((!always_stored
&& !multi_threaded_model_p
)
2139 || (ref
->loaded
&& bitmap_bit_p (ref
->loaded
, loop
->num
)))
2140 load
= gimple_build_assign (aux
->tmp_var
, unshare_expr (ref
->mem
.ref
));
2143 /* If not emitting a load mark the uninitialized state on the
2144 loop entry as not to be warned for. */
2145 tree uninit
= create_tmp_reg (TREE_TYPE (aux
->tmp_var
));
2146 TREE_NO_WARNING (uninit
) = 1;
2147 load
= gimple_build_assign (aux
->tmp_var
, uninit
);
2149 lim_data
= init_lim_data (load
);
2150 lim_data
->max_loop
= loop
;
2151 lim_data
->tgt_loop
= loop
;
2152 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2154 if (multi_threaded_model_p
)
2156 load
= gimple_build_assign (aux
->store_flag
, boolean_false_node
);
2157 lim_data
= init_lim_data (load
);
2158 lim_data
->max_loop
= loop
;
2159 lim_data
->tgt_loop
= loop
;
2160 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2164 /* sm_ord is used for ordinary stores we can retain order with respect
2166 sm_unord is used for conditional executed stores which need to be
2167 able to execute in arbitrary order with respect to other stores
2168 sm_other is used for stores we do not try to apply store motion to. */
2169 enum sm_kind
{ sm_ord
, sm_unord
, sm_other
};
2172 seq_entry (unsigned f
, sm_kind k
, tree fr
= NULL
)
2173 : first (f
), second (k
), from (fr
) {}
2180 execute_sm_exit (class loop
*loop
, edge ex
, vec
<seq_entry
> &seq
,
2181 hash_map
<im_mem_ref
*, sm_aux
*> &aux_map
, sm_kind kind
,
2182 edge
&append_cond_position
, edge
&last_cond_fallthru
)
2184 /* Sink the stores to exit from the loop. */
2185 for (unsigned i
= seq
.length (); i
> 0; --i
)
2187 im_mem_ref
*ref
= memory_accesses
.refs_list
[seq
[i
-1].first
];
2188 if (seq
[i
-1].second
== sm_other
)
2190 gcc_assert (kind
== sm_ord
&& seq
[i
-1].from
!= NULL_TREE
);
2191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2193 fprintf (dump_file
, "Re-issueing dependent store of ");
2194 print_generic_expr (dump_file
, ref
->mem
.ref
);
2195 fprintf (dump_file
, " from loop %d on exit %d -> %d\n",
2196 loop
->num
, ex
->src
->index
, ex
->dest
->index
);
2198 gassign
*store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
),
2200 gsi_insert_on_edge (ex
, store
);
2204 sm_aux
*aux
= *aux_map
.get (ref
);
2205 if (!aux
->store_flag
|| kind
== sm_ord
)
2208 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
),
2210 gsi_insert_on_edge (ex
, store
);
2213 execute_sm_if_changed (ex
, ref
->mem
.ref
, aux
->tmp_var
,
2215 loop_preheader_edge (loop
), &aux
->flag_bbs
,
2216 append_cond_position
, last_cond_fallthru
);
2221 /* Push the SM candidate at index PTR in the sequence SEQ down until
2222 we hit the next SM candidate. Return true if that went OK and
2223 false if we could not disambiguate agains another unrelated ref.
2224 Update *AT to the index where the candidate now resides. */
2227 sm_seq_push_down (vec
<seq_entry
> &seq
, unsigned ptr
, unsigned *at
)
2230 for (; ptr
> 0; --ptr
)
2232 seq_entry
&new_cand
= seq
[ptr
];
2233 seq_entry
&against
= seq
[ptr
-1];
2234 if (against
.second
== sm_ord
2235 || (against
.second
== sm_other
&& against
.from
!= NULL_TREE
))
2236 /* Found the tail of the sequence. */
2238 /* We may not ignore self-dependences here. */
2239 if (new_cand
.first
== against
.first
2240 || !refs_independent_p (memory_accesses
.refs_list
[new_cand
.first
],
2241 memory_accesses
.refs_list
[against
.first
],
2243 /* ??? Prune new_cand from the list of refs to apply SM to. */
2245 std::swap (new_cand
, against
);
2251 /* Computes the sequence of stores from candidates in REFS_NOT_IN_SEQ to SEQ
2252 walking backwards from VDEF (or the end of BB if VDEF is NULL). */
2255 sm_seq_valid_bb (class loop
*loop
, basic_block bb
, tree vdef
,
2256 vec
<seq_entry
> &seq
, bitmap refs_not_in_seq
,
2257 bitmap refs_not_supported
, bool forked
,
2258 bitmap fully_visited
)
2261 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
2264 vdef
= gimple_vdef (gsi_stmt (gsi
));
2270 gphi
*vphi
= get_virtual_phi (bb
);
2272 vdef
= gimple_phi_result (vphi
);
2276 if (single_pred_p (bb
))
2277 /* This handles the perfect nest case. */
2278 return sm_seq_valid_bb (loop
, single_pred (bb
), vdef
,
2279 seq
, refs_not_in_seq
, refs_not_supported
,
2280 forked
, fully_visited
);
2285 gimple
*def
= SSA_NAME_DEF_STMT (vdef
);
2286 if (gimple_bb (def
) != bb
)
2288 /* If we forked by processing a PHI do not allow our walk to
2289 merge again until we handle that robustly. */
2292 /* Mark refs_not_in_seq as unsupported. */
2293 bitmap_ior_into (refs_not_supported
, refs_not_in_seq
);
2296 /* Otherwise it doesn't really matter if we end up in different
2298 bb
= gimple_bb (def
);
2300 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
2302 /* Handle CFG merges. Until we handle forks (gimple_bb (def) != bb)
2303 this is still linear.
2304 Eventually we want to cache intermediate results per BB
2305 (but we can't easily cache for different exits?). */
2306 /* Stop at PHIs with possible backedges. */
2307 if (bb
== bb
->loop_father
->header
2308 || bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2310 /* Mark refs_not_in_seq as unsupported. */
2311 bitmap_ior_into (refs_not_supported
, refs_not_in_seq
);
2314 if (gimple_phi_num_args (phi
) == 1)
2315 return sm_seq_valid_bb (loop
, gimple_phi_arg_edge (phi
, 0)->src
,
2316 gimple_phi_arg_def (phi
, 0), seq
,
2317 refs_not_in_seq
, refs_not_supported
,
2318 false, fully_visited
);
2319 if (bitmap_bit_p (fully_visited
,
2320 SSA_NAME_VERSION (gimple_phi_result (phi
))))
2322 auto_vec
<seq_entry
> first_edge_seq
;
2323 auto_bitmap
tem_refs_not_in_seq (&lim_bitmap_obstack
);
2325 bitmap_copy (tem_refs_not_in_seq
, refs_not_in_seq
);
2326 eret
= sm_seq_valid_bb (loop
, gimple_phi_arg_edge (phi
, 0)->src
,
2327 gimple_phi_arg_def (phi
, 0),
2329 tem_refs_not_in_seq
, refs_not_supported
,
2330 true, fully_visited
);
2333 /* Simplify our lives by pruning the sequence of !sm_ord. */
2334 while (!first_edge_seq
.is_empty ()
2335 && first_edge_seq
.last ().second
!= sm_ord
)
2336 first_edge_seq
.pop ();
2337 for (unsigned int i
= 1; i
< gimple_phi_num_args (phi
); ++i
)
2339 tree vuse
= gimple_phi_arg_def (phi
, i
);
2340 edge e
= gimple_phi_arg_edge (phi
, i
);
2341 auto_vec
<seq_entry
> edge_seq
;
2342 bitmap_copy (tem_refs_not_in_seq
, refs_not_in_seq
);
2343 eret
= sm_seq_valid_bb (loop
, e
->src
, vuse
, edge_seq
,
2344 tem_refs_not_in_seq
, refs_not_supported
,
2345 true, fully_visited
);
2348 /* Simplify our lives by pruning the sequence of !sm_ord. */
2349 while (!edge_seq
.is_empty ()
2350 && edge_seq
.last ().second
!= sm_ord
)
2352 unsigned min_len
= MIN(first_edge_seq
.length (),
2353 edge_seq
.length ());
2354 /* Incrementally merge seqs into first_edge_seq. */
2355 for (unsigned int i
= 0; i
< min_len
; ++i
)
2357 /* ??? We can more intelligently merge when we face different
2358 order by additional sinking operations in one sequence.
2359 For now we simply mark them as to be processed by the
2360 not order-preserving SM code. */
2361 if (first_edge_seq
[i
].first
!= edge_seq
[i
].first
)
2363 if (first_edge_seq
[i
].second
== sm_ord
)
2364 bitmap_set_bit (refs_not_supported
,
2365 first_edge_seq
[i
].first
);
2366 if (edge_seq
[i
].second
== sm_ord
)
2367 bitmap_set_bit (refs_not_supported
, edge_seq
[i
].first
);
2368 first_edge_seq
[i
].second
= sm_other
;
2369 first_edge_seq
[i
].from
= NULL_TREE
;
2371 /* sm_other prevails. */
2372 else if (first_edge_seq
[i
].second
!= edge_seq
[i
].second
)
2374 /* This is just an optimization. */
2375 gcc_assert (bitmap_bit_p (refs_not_supported
,
2376 first_edge_seq
[i
].first
));
2377 first_edge_seq
[i
].second
= sm_other
;
2378 first_edge_seq
[i
].from
= NULL_TREE
;
2380 else if (first_edge_seq
[i
].second
== sm_other
2381 && first_edge_seq
[i
].from
!= NULL_TREE
2382 && (edge_seq
[i
].from
== NULL_TREE
2383 || !operand_equal_p (first_edge_seq
[i
].from
,
2384 edge_seq
[i
].from
, 0)))
2385 first_edge_seq
[i
].from
= NULL_TREE
;
2387 /* Any excess elements become sm_other since they are now
2388 coonditionally executed. */
2389 if (first_edge_seq
.length () > edge_seq
.length ())
2391 for (unsigned i
= edge_seq
.length ();
2392 i
< first_edge_seq
.length (); ++i
)
2394 if (first_edge_seq
[i
].second
== sm_ord
)
2395 bitmap_set_bit (refs_not_supported
,
2396 first_edge_seq
[i
].first
);
2397 first_edge_seq
[i
].second
= sm_other
;
2400 else if (edge_seq
.length () > first_edge_seq
.length ())
2402 for (unsigned i
= first_edge_seq
.length ();
2403 i
< edge_seq
.length (); ++i
)
2404 if (edge_seq
[i
].second
== sm_ord
)
2405 bitmap_set_bit (refs_not_supported
, edge_seq
[i
].first
);
2408 /* Use the sequence from the first edge and push SMs down. */
2409 for (unsigned i
= 0; i
< first_edge_seq
.length (); ++i
)
2411 unsigned id
= first_edge_seq
[i
].first
;
2412 seq
.safe_push (first_edge_seq
[i
]);
2414 if ((first_edge_seq
[i
].second
== sm_ord
2415 || (first_edge_seq
[i
].second
== sm_other
2416 && first_edge_seq
[i
].from
!= NULL_TREE
))
2417 && !sm_seq_push_down (seq
, seq
.length () - 1, &new_idx
))
2419 if (first_edge_seq
[i
].second
== sm_ord
)
2420 bitmap_set_bit (refs_not_supported
, id
);
2421 /* Mark it sm_other. */
2422 seq
[new_idx
].second
= sm_other
;
2423 seq
[new_idx
].from
= NULL_TREE
;
2426 bitmap_set_bit (fully_visited
,
2427 SSA_NAME_VERSION (gimple_phi_result (phi
)));
2430 lim_aux_data
*data
= get_lim_data (def
);
2432 if (data
->ref
== UNANALYZABLE_MEM_ID
)
2434 /* One of the stores we want to apply SM to and we've not yet seen. */
2435 else if (bitmap_clear_bit (refs_not_in_seq
, data
->ref
))
2437 seq
.safe_push (seq_entry (data
->ref
, sm_ord
));
2439 /* 1) push it down the queue until a SMed
2440 and not ignored ref is reached, skipping all not SMed refs
2441 and ignored refs via non-TBAA disambiguation. */
2443 if (!sm_seq_push_down (seq
, seq
.length () - 1, &new_idx
)
2444 /* If that fails but we did not fork yet continue, we'll see
2445 to re-materialize all of the stores in the sequence then.
2446 Further stores will only be pushed up to this one. */
2449 bitmap_set_bit (refs_not_supported
, data
->ref
);
2450 /* Mark it sm_other. */
2451 seq
[new_idx
].second
= sm_other
;
2454 /* 2) check whether we've seen all refs we want to SM and if so
2455 declare success for the active exit */
2456 if (bitmap_empty_p (refs_not_in_seq
))
2460 /* Another store not part of the final sequence. Simply push it. */
2461 seq
.safe_push (seq_entry (data
->ref
, sm_other
,
2462 gimple_assign_rhs1 (def
)));
2464 vdef
= gimple_vuse (def
);
2469 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2470 edges of the LOOP. */
2473 hoist_memory_references (class loop
*loop
, bitmap mem_refs
,
2480 /* To address PR57359 before actually applying store-motion check
2481 the candidates found for validity with regards to reordering
2482 relative to other stores which we until here disambiguated using
2483 TBAA which isn't valid.
2484 What matters is the order of the last stores to the mem_refs
2485 with respect to the other stores of the loop at the point of the
2488 /* For each exit compute the store order, pruning from mem_refs
2490 /* The complexity of this is at least
2491 O(number of exits * number of SM refs) but more approaching
2492 O(number of exits * number of SM refs * number of stores). */
2493 /* ??? Somehow do this in a single sweep over the loop body. */
2494 auto_vec
<std::pair
<edge
, vec
<seq_entry
> > > sms
;
2495 auto_bitmap
refs_not_supported (&lim_bitmap_obstack
);
2497 FOR_EACH_VEC_ELT (exits
, i
, e
)
2501 auto_bitmap
refs_not_in_seq (&lim_bitmap_obstack
);
2502 bitmap_copy (refs_not_in_seq
, mem_refs
);
2503 auto_bitmap fully_visited
;
2504 int res
= sm_seq_valid_bb (loop
, e
->src
, NULL_TREE
,
2505 seq
, refs_not_in_seq
,
2506 refs_not_supported
, false,
2510 bitmap_copy (refs_not_supported
, mem_refs
);
2513 sms
.safe_push (std::make_pair (e
, seq
));
2516 /* Prune pruned mem_refs from earlier processed exits. */
2517 bool changed
= !bitmap_empty_p (refs_not_supported
);
2521 std::pair
<edge
, vec
<seq_entry
> > *seq
;
2522 FOR_EACH_VEC_ELT (sms
, i
, seq
)
2524 bool need_to_push
= false;
2525 for (unsigned i
= 0; i
< seq
->second
.length (); ++i
)
2527 sm_kind kind
= seq
->second
[i
].second
;
2528 if (kind
== sm_other
&& seq
->second
[i
].from
== NULL_TREE
)
2530 unsigned id
= seq
->second
[i
].first
;
2533 && bitmap_bit_p (refs_not_supported
, id
))
2535 seq
->second
[i
].second
= sm_other
;
2536 gcc_assert (seq
->second
[i
].from
== NULL_TREE
);
2537 need_to_push
= true;
2539 else if (need_to_push
2540 && !sm_seq_push_down (seq
->second
, i
, &new_idx
))
2542 /* We need to push down both sm_ord and sm_other
2543 but for the latter we need to disqualify all
2547 if (bitmap_set_bit (refs_not_supported
, id
))
2549 seq
->second
[new_idx
].second
= sm_other
;
2553 for (unsigned j
= seq
->second
.length () - 1;
2555 if (seq
->second
[j
].second
== sm_ord
2556 && bitmap_set_bit (refs_not_supported
,
2557 seq
->second
[j
].first
))
2559 seq
->second
.truncate (new_idx
);
2566 std::pair
<edge
, vec
<seq_entry
> > *seq
;
2567 FOR_EACH_VEC_ELT (sms
, i
, seq
)
2569 /* Prune sm_other from the end. */
2570 while (!seq
->second
.is_empty ()
2571 && seq
->second
.last ().second
== sm_other
)
2573 /* Prune duplicates from the start. */
2574 auto_bitmap
seen (&lim_bitmap_obstack
);
2576 for (j
= k
= 0; j
< seq
->second
.length (); ++j
)
2577 if (bitmap_set_bit (seen
, seq
->second
[j
].first
))
2580 seq
->second
[k
] = seq
->second
[j
];
2583 seq
->second
.truncate (k
);
2586 FOR_EACH_VEC_ELT (seq
->second
, j
, e
)
2587 gcc_assert (e
->second
== sm_ord
2588 || (e
->second
== sm_other
&& e
->from
!= NULL_TREE
));
2591 /* Verify dependence for refs we cannot handle with the order preserving
2592 code (refs_not_supported) or prune them from mem_refs. */
2593 auto_vec
<seq_entry
> unord_refs
;
2594 EXECUTE_IF_SET_IN_BITMAP (refs_not_supported
, 0, i
, bi
)
2596 ref
= memory_accesses
.refs_list
[i
];
2597 if (!ref_indep_loop_p (loop
, ref
, sm_waw
))
2598 bitmap_clear_bit (mem_refs
, i
);
2599 /* We've now verified store order for ref with respect to all other
2600 stores in the loop does not matter. */
2602 unord_refs
.safe_push (seq_entry (i
, sm_unord
));
2605 hash_map
<im_mem_ref
*, sm_aux
*> aux_map
;
2607 /* Execute SM but delay the store materialization for ordered
2608 sequences on exit. */
2609 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2611 ref
= memory_accesses
.refs_list
[i
];
2612 execute_sm (loop
, ref
, aux_map
, bitmap_bit_p (refs_not_supported
, i
));
2615 /* Materialize ordered store sequences on exits. */
2616 FOR_EACH_VEC_ELT (exits
, i
, e
)
2618 edge append_cond_position
= NULL
;
2619 edge last_cond_fallthru
= NULL
;
2620 if (i
< sms
.length ())
2622 gcc_assert (sms
[i
].first
== e
);
2623 execute_sm_exit (loop
, e
, sms
[i
].second
, aux_map
, sm_ord
,
2624 append_cond_position
, last_cond_fallthru
);
2625 sms
[i
].second
.release ();
2627 if (!unord_refs
.is_empty ())
2628 execute_sm_exit (loop
, e
, unord_refs
, aux_map
, sm_unord
,
2629 append_cond_position
, last_cond_fallthru
);
2630 /* Commit edge inserts here to preserve the order of stores
2631 when an exit exits multiple loops. */
2632 gsi_commit_one_edge_insert (e
, NULL
);
2635 for (hash_map
<im_mem_ref
*, sm_aux
*>::iterator iter
= aux_map
.begin ();
2636 iter
!= aux_map
.end (); ++iter
)
2637 delete (*iter
).second
;
2640 class ref_always_accessed
2643 ref_always_accessed (class loop
*loop_
, bool stored_p_
)
2644 : loop (loop_
), stored_p (stored_p_
) {}
2645 bool operator () (mem_ref_loc
*loc
);
2651 ref_always_accessed::operator () (mem_ref_loc
*loc
)
2653 class loop
*must_exec
;
2655 struct lim_aux_data
*lim_data
= get_lim_data (loc
->stmt
);
2659 /* If we require an always executed store make sure the statement
2663 tree lhs
= gimple_get_lhs (loc
->stmt
);
2665 || !(DECL_P (lhs
) || REFERENCE_CLASS_P (lhs
)))
2669 must_exec
= lim_data
->always_executed_in
;
2673 if (must_exec
== loop
2674 || flow_loop_nested_p (must_exec
, loop
))
2680 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2681 make sure REF is always stored to in LOOP. */
2684 ref_always_accessed_p (class loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2686 return for_all_locs_in_loop (loop
, ref
,
2687 ref_always_accessed (loop
, stored_p
));
2690 /* Returns true if REF1 and REF2 are independent. */
2693 refs_independent_p (im_mem_ref
*ref1
, im_mem_ref
*ref2
, bool tbaa_p
)
2698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2699 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2700 ref1
->id
, ref2
->id
);
2702 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
, tbaa_p
))
2704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2705 fprintf (dump_file
, "dependent.\n");
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2711 fprintf (dump_file
, "independent.\n");
2716 /* Returns true if REF is independent on all other accessess in LOOP.
2717 KIND specifies the kind of dependence to consider.
2718 lim_raw assumes REF is not stored in LOOP and disambiguates RAW
2719 dependences so if true REF can be hoisted out of LOOP
2720 sm_war disambiguates a store REF against all other loads to see
2721 whether the store can be sunk across loads out of LOOP
2722 sm_waw disambiguates a store REF against all other stores to see
2723 whether the store can be sunk across stores out of LOOP. */
2726 ref_indep_loop_p (class loop
*loop
, im_mem_ref
*ref
, dep_kind kind
)
2728 bool indep_p
= true;
2729 bitmap refs_to_check
;
2732 refs_to_check
= &memory_accesses
.refs_loaded_in_loop
[loop
->num
];
2734 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2736 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2740 /* tri-state, { unknown, independent, dependent } */
2741 dep_state state
= query_loop_dependence (loop
, ref
, kind
);
2742 if (state
!= dep_unknown
)
2743 return state
== dep_independent
? true : false;
2745 class loop
*inner
= loop
->inner
;
2748 if (!ref_indep_loop_p (inner
, ref
, kind
))
2753 inner
= inner
->next
;
2760 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2762 im_mem_ref
*aref
= memory_accesses
.refs_list
[i
];
2763 if (!refs_independent_p (ref
, aref
, kind
!= sm_waw
))
2772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2773 fprintf (dump_file
, "Querying %s dependencies of ref %u in loop %d: %s\n",
2774 kind
== lim_raw
? "RAW" : (kind
== sm_war
? "SM WAR" : "SM WAW"),
2775 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2777 /* Record the computed result in the cache. */
2778 record_loop_dependence (loop
, ref
, kind
,
2779 indep_p
? dep_independent
: dep_dependent
);
2785 /* Returns true if we can perform store motion of REF from LOOP. */
2788 can_sm_ref_p (class loop
*loop
, im_mem_ref
*ref
)
2792 /* Can't hoist unanalyzable refs. */
2793 if (!MEM_ANALYZABLE (ref
))
2796 /* It should be movable. */
2797 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2798 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2799 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2802 /* If it can throw fail, we do not properly update EH info. */
2803 if (tree_could_throw_p (ref
->mem
.ref
))
2806 /* If it can trap, it must be always executed in LOOP.
2807 Readonly memory locations may trap when storing to them, but
2808 tree_could_trap_p is a predicate for rvalues, so check that
2810 base
= get_base_address (ref
->mem
.ref
);
2811 if ((tree_could_trap_p (ref
->mem
.ref
)
2812 || (DECL_P (base
) && TREE_READONLY (base
)))
2813 /* ??? We can at least use false here, allowing loads? We
2814 are forcing conditional stores if the ref is not always
2815 stored to later anyway. So this would only guard
2816 the load we need to emit. Thus when the ref is not
2817 loaded we can elide this completely? */
2818 && !ref_always_accessed_p (loop
, ref
, true))
2821 /* Verify all loads of ref can be hoisted. */
2823 && bitmap_bit_p (ref
->loaded
, loop
->num
)
2824 && !ref_indep_loop_p (loop
, ref
, lim_raw
))
2827 /* Verify the candidate can be disambiguated against all loads,
2828 that is, we can elide all in-loop stores. Disambiguation
2829 against stores is done later when we cannot guarantee preserving
2830 the order of stores. */
2831 if (!ref_indep_loop_p (loop
, ref
, sm_war
))
2837 /* Marks the references in LOOP for that store motion should be performed
2838 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2839 motion was performed in one of the outer loops. */
2842 find_refs_for_sm (class loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2844 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2849 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2851 ref
= memory_accesses
.refs_list
[i
];
2852 if (can_sm_ref_p (loop
, ref
) && dbg_cnt (lim
))
2853 bitmap_set_bit (refs_to_sm
, i
);
2857 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2858 for a store motion optimization (i.e. whether we can insert statement
2862 loop_suitable_for_sm (class loop
*loop ATTRIBUTE_UNUSED
,
2868 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2869 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2875 /* Try to perform store motion for all memory references modified inside
2876 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2877 store motion was executed in one of the outer loops. */
2880 store_motion_loop (class loop
*loop
, bitmap sm_executed
)
2882 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2883 class loop
*subloop
;
2884 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2886 if (loop_suitable_for_sm (loop
, exits
))
2888 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2889 if (!bitmap_empty_p (sm_in_loop
))
2890 hoist_memory_references (loop
, sm_in_loop
, exits
);
2893 bitmap_ior_into (sm_executed
, sm_in_loop
);
2894 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2895 store_motion_loop (subloop
, sm_executed
);
2896 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2897 BITMAP_FREE (sm_in_loop
);
2900 /* Try to perform store motion for all memory references modified inside
2904 do_store_motion (void)
2907 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2909 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2910 store_motion_loop (loop
, sm_executed
);
2912 BITMAP_FREE (sm_executed
);
2915 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2916 for each such basic block bb records the outermost loop for that execution
2917 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2918 blocks that contain a nonpure call. */
2921 fill_always_executed_in_1 (class loop
*loop
, sbitmap contains_call
)
2923 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2926 class loop
*inn_loop
= loop
;
2928 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2930 bbs
= get_loop_body_in_dom_order (loop
);
2932 for (i
= 0; i
< loop
->num_nodes
; i
++)
2937 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2940 if (bitmap_bit_p (contains_call
, bb
->index
))
2943 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2945 /* If there is an exit from this BB. */
2946 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2948 /* Or we enter a possibly non-finite loop. */
2949 if (flow_loop_nested_p (bb
->loop_father
,
2950 e
->dest
->loop_father
)
2951 && ! finite_loop_p (e
->dest
->loop_father
))
2957 /* A loop might be infinite (TODO use simple loop analysis
2958 to disprove this if possible). */
2959 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2962 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2965 if (bb
->loop_father
->header
== bb
)
2967 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2970 /* In a loop that is always entered we may proceed anyway.
2971 But record that we entered it and stop once we leave it. */
2972 inn_loop
= bb
->loop_father
;
2978 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2979 if (last
== loop
->header
)
2981 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2987 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2988 fill_always_executed_in_1 (loop
, contains_call
);
2991 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2992 for each such basic block bb records the outermost loop for that execution
2993 of its header implies execution of bb. */
2996 fill_always_executed_in (void)
3001 auto_sbitmap
contains_call (last_basic_block_for_fn (cfun
));
3002 bitmap_clear (contains_call
);
3003 FOR_EACH_BB_FN (bb
, cfun
)
3005 gimple_stmt_iterator gsi
;
3006 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3008 if (nonpure_call_p (gsi_stmt (gsi
)))
3012 if (!gsi_end_p (gsi
))
3013 bitmap_set_bit (contains_call
, bb
->index
);
3016 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
3017 fill_always_executed_in_1 (loop
, contains_call
);
3021 /* Compute the global information needed by the loop invariant motion pass. */
3024 tree_ssa_lim_initialize (bool store_motion
)
3029 bitmap_obstack_initialize (&lim_bitmap_obstack
);
3030 gcc_obstack_init (&mem_ref_obstack
);
3031 lim_aux_data_map
= new hash_map
<gimple
*, lim_aux_data
*>;
3034 compute_transaction_bits ();
3036 memory_accesses
.refs
= new hash_table
<mem_ref_hasher
> (100);
3037 memory_accesses
.refs_list
.create (100);
3038 /* Allocate a special, unanalyzable mem-ref with ID zero. */
3039 memory_accesses
.refs_list
.quick_push
3040 (mem_ref_alloc (NULL
, 0, UNANALYZABLE_MEM_ID
));
3042 memory_accesses
.refs_loaded_in_loop
.create (number_of_loops (cfun
));
3043 memory_accesses
.refs_loaded_in_loop
.quick_grow (number_of_loops (cfun
));
3044 memory_accesses
.refs_stored_in_loop
.create (number_of_loops (cfun
));
3045 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
3048 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops (cfun
));
3049 memory_accesses
.all_refs_stored_in_loop
.quick_grow
3050 (number_of_loops (cfun
));
3053 for (i
= 0; i
< number_of_loops (cfun
); i
++)
3055 bitmap_initialize (&memory_accesses
.refs_loaded_in_loop
[i
],
3056 &lim_bitmap_obstack
);
3057 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
3058 &lim_bitmap_obstack
);
3060 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
3061 &lim_bitmap_obstack
);
3064 memory_accesses
.ttae_cache
= NULL
;
3066 /* Initialize bb_loop_postorder with a mapping from loop->num to
3067 its postorder index. */
3069 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops (cfun
));
3070 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3071 bb_loop_postorder
[loop
->num
] = i
++;
3074 /* Cleans up after the invariant motion pass. */
3077 tree_ssa_lim_finalize (void)
3083 FOR_EACH_BB_FN (bb
, cfun
)
3084 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
3086 bitmap_obstack_release (&lim_bitmap_obstack
);
3087 delete lim_aux_data_map
;
3089 delete memory_accesses
.refs
;
3090 memory_accesses
.refs
= NULL
;
3092 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
3094 memory_accesses
.refs_list
.release ();
3095 obstack_free (&mem_ref_obstack
, NULL
);
3097 memory_accesses
.refs_loaded_in_loop
.release ();
3098 memory_accesses
.refs_stored_in_loop
.release ();
3099 memory_accesses
.all_refs_stored_in_loop
.release ();
3101 if (memory_accesses
.ttae_cache
)
3102 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
3104 free (bb_loop_postorder
);
3107 /* Moves invariants from loops. Only "expensive" invariants are moved out --
3108 i.e. those that are likely to be win regardless of the register pressure.
3109 Only perform store motion if STORE_MOTION is true. */
3112 loop_invariant_motion_in_fun (function
*fun
, bool store_motion
)
3114 unsigned int todo
= 0;
3116 tree_ssa_lim_initialize (store_motion
);
3118 /* Gathers information about memory accesses in the loops. */
3119 analyze_memory_references (store_motion
);
3121 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
3122 fill_always_executed_in ();
3124 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (fun
));
3125 int n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
3127 /* For each statement determine the outermost loop in that it is
3128 invariant and cost for computing the invariant. */
3129 for (int i
= 0; i
< n
; ++i
)
3130 compute_invariantness (BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]));
3132 /* Execute store motion. Force the necessary invariants to be moved
3133 out of the loops as well. */
3138 rpo
= XNEWVEC (int, last_basic_block_for_fn (fun
));
3139 n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
3141 /* Move the expressions that are expensive enough. */
3142 for (int i
= 0; i
< n
; ++i
)
3143 todo
|= move_computations_worker (BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]));
3147 gsi_commit_edge_inserts ();
3148 if (need_ssa_update_p (fun
))
3149 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3151 tree_ssa_lim_finalize ();
3156 /* Loop invariant motion pass. */
3160 const pass_data pass_data_lim
=
3162 GIMPLE_PASS
, /* type */
3164 OPTGROUP_LOOP
, /* optinfo_flags */
3166 PROP_cfg
, /* properties_required */
3167 0, /* properties_provided */
3168 0, /* properties_destroyed */
3169 0, /* todo_flags_start */
3170 0, /* todo_flags_finish */
3173 class pass_lim
: public gimple_opt_pass
3176 pass_lim (gcc::context
*ctxt
)
3177 : gimple_opt_pass (pass_data_lim
, ctxt
)
3180 /* opt_pass methods: */
3181 opt_pass
* clone () { return new pass_lim (m_ctxt
); }
3182 virtual bool gate (function
*) { return flag_tree_loop_im
!= 0; }
3183 virtual unsigned int execute (function
*);
3185 }; // class pass_lim
3188 pass_lim::execute (function
*fun
)
3190 bool in_loop_pipeline
= scev_initialized_p ();
3191 if (!in_loop_pipeline
)
3192 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
3194 if (number_of_loops (fun
) <= 1)
3196 unsigned int todo
= loop_invariant_motion_in_fun (fun
, true);
3198 if (!in_loop_pipeline
)
3199 loop_optimizer_finalize ();
3208 make_pass_lim (gcc::context
*ctxt
)
3210 return new pass_lim (ctxt
);