1 /* Loop invariant motion.
2 Copyright (C) 2003-2020 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 (void)
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);
1668 /* Propagate the information about accessed memory references up
1669 the loop hierarchy. */
1670 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1672 /* Finalize the overall touched references (including subloops). */
1673 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1674 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1676 /* Propagate the information about accessed memory references up
1677 the loop hierarchy. */
1678 outer
= loop_outer (loop
);
1679 if (outer
== current_loops
->tree_root
)
1682 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1683 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1687 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1688 tree_to_aff_combination_expand. */
1691 mem_refs_may_alias_p (im_mem_ref
*mem1
, im_mem_ref
*mem2
,
1692 hash_map
<tree
, name_expansion
*> **ttae_cache
,
1695 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1696 object and their offset differ in such a way that the locations cannot
1697 overlap, then they cannot alias. */
1698 poly_widest_int size1
, size2
;
1699 aff_tree off1
, off2
;
1701 /* Perform basic offset and type-based disambiguation. */
1702 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, tbaa_p
))
1705 /* The expansion of addresses may be a bit expensive, thus we only do
1706 the check at -O2 and higher optimization levels. */
1710 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1711 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1712 aff_combination_expand (&off1
, ttae_cache
);
1713 aff_combination_expand (&off2
, ttae_cache
);
1714 aff_combination_scale (&off1
, -1);
1715 aff_combination_add (&off2
, &off1
);
1717 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1723 /* Compare function for bsearch searching for reference locations
1727 find_ref_loc_in_loop_cmp (const void *loop_
, const void *loc_
,
1728 void *bb_loop_postorder_
)
1730 unsigned *bb_loop_postorder
= (unsigned *)bb_loop_postorder_
;
1731 class loop
*loop
= (class loop
*)const_cast<void *>(loop_
);
1732 mem_ref_loc
*loc
= (mem_ref_loc
*)const_cast<void *>(loc_
);
1733 class loop
*loc_loop
= gimple_bb (loc
->stmt
)->loop_father
;
1734 if (loop
->num
== loc_loop
->num
1735 || flow_loop_nested_p (loop
, loc_loop
))
1737 return (bb_loop_postorder
[loop
->num
] < bb_loop_postorder
[loc_loop
->num
]
1741 /* Iterates over all locations of REF in LOOP and its subloops calling
1742 fn.operator() with the location as argument. When that operator
1743 returns true the iteration is stopped and true is returned.
1744 Otherwise false is returned. */
1746 template <typename FN
>
1748 for_all_locs_in_loop (class loop
*loop
, im_mem_ref
*ref
, FN fn
)
1753 /* Search for the cluster of locs in the accesses_in_loop vector
1754 which is sorted after postorder index of the loop father. */
1755 loc
= ref
->accesses_in_loop
.bsearch (loop
, find_ref_loc_in_loop_cmp
,
1760 /* We have found one location inside loop or its sub-loops. Iterate
1761 both forward and backward to cover the whole cluster. */
1762 i
= loc
- ref
->accesses_in_loop
.address ();
1766 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1767 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1772 for (i
= loc
- ref
->accesses_in_loop
.address ();
1773 i
< ref
->accesses_in_loop
.length (); ++i
)
1775 mem_ref_loc
*l
= &ref
->accesses_in_loop
[i
];
1776 if (!flow_bb_inside_loop_p (loop
, gimple_bb (l
->stmt
)))
1785 /* Rewrites location LOC by TMP_VAR. */
1787 class rewrite_mem_ref_loc
1790 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1791 bool operator () (mem_ref_loc
*loc
);
1796 rewrite_mem_ref_loc::operator () (mem_ref_loc
*loc
)
1798 *loc
->ref
= tmp_var
;
1799 update_stmt (loc
->stmt
);
1803 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1806 rewrite_mem_refs (class loop
*loop
, im_mem_ref
*ref
, tree tmp_var
)
1808 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1811 /* Stores the first reference location in LOCP. */
1813 class first_mem_ref_loc_1
1816 first_mem_ref_loc_1 (mem_ref_loc
**locp_
) : locp (locp_
) {}
1817 bool operator () (mem_ref_loc
*loc
);
1822 first_mem_ref_loc_1::operator () (mem_ref_loc
*loc
)
1828 /* Returns the first reference location to REF in LOOP. */
1830 static mem_ref_loc
*
1831 first_mem_ref_loc (class loop
*loop
, im_mem_ref
*ref
)
1833 mem_ref_loc
*locp
= NULL
;
1834 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1838 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1841 The store is only done if MEM has changed. We do this so no
1842 changes to MEM occur on code paths that did not originally store
1845 The common case for execute_sm will transform:
1865 This function will generate:
1884 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
,
1885 edge preheader
, hash_set
<basic_block
> *flag_bbs
,
1886 edge
&append_cond_position
, edge
&last_cond_fallthru
)
1888 basic_block new_bb
, then_bb
, old_dest
;
1889 bool loop_has_only_one_exit
;
1891 gimple_stmt_iterator gsi
;
1893 bool irr
= ex
->flags
& EDGE_IRREDUCIBLE_LOOP
;
1895 profile_count count_sum
= profile_count::zero ();
1896 int nbbs
= 0, ncount
= 0;
1897 profile_probability flag_probability
= profile_probability::uninitialized ();
1899 /* Flag is set in FLAG_BBS. Determine probability that flag will be true
1902 This code may look fancy, but it cannot update profile very realistically
1903 because we do not know the probability that flag will be true at given
1906 We look for two interesting extremes
1907 - when exit is dominated by block setting the flag, we know it will
1908 always be true. This is a common case.
1909 - when all blocks setting the flag have very low frequency we know
1910 it will likely be false.
1911 In all other cases we default to 2/3 for flag being true. */
1913 for (hash_set
<basic_block
>::iterator it
= flag_bbs
->begin ();
1914 it
!= flag_bbs
->end (); ++it
)
1916 if ((*it
)->count
.initialized_p ())
1917 count_sum
+= (*it
)->count
, ncount
++;
1918 if (dominated_by_p (CDI_DOMINATORS
, ex
->src
, *it
))
1919 flag_probability
= profile_probability::always ();
1923 profile_probability cap
= profile_probability::always ().apply_scale (2, 3);
1925 if (flag_probability
.initialized_p ())
1927 else if (ncount
== nbbs
1928 && preheader
->count () >= count_sum
&& preheader
->count ().nonzero_p ())
1930 flag_probability
= count_sum
.probability_in (preheader
->count ());
1931 if (flag_probability
> cap
)
1932 flag_probability
= cap
;
1935 if (!flag_probability
.initialized_p ())
1936 flag_probability
= cap
;
1938 /* ?? Insert store after previous store if applicable. See note
1940 if (append_cond_position
)
1941 ex
= append_cond_position
;
1943 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1945 if (loop_has_only_one_exit
)
1946 ex
= split_block_after_labels (ex
->dest
);
1949 for (gphi_iterator gpi
= gsi_start_phis (ex
->dest
);
1950 !gsi_end_p (gpi
); gsi_next (&gpi
))
1952 gphi
*phi
= gpi
.phi ();
1953 if (virtual_operand_p (gimple_phi_result (phi
)))
1956 /* When the destination has a non-virtual PHI node with multiple
1957 predecessors make sure we preserve the PHI structure by
1958 forcing a forwarder block so that hoisting of that PHI will
1965 old_dest
= ex
->dest
;
1966 new_bb
= split_edge (ex
);
1967 then_bb
= create_empty_bb (new_bb
);
1968 then_bb
->count
= new_bb
->count
.apply_probability (flag_probability
);
1970 then_bb
->flags
= BB_IRREDUCIBLE_LOOP
;
1971 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1973 gsi
= gsi_start_bb (new_bb
);
1974 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1975 NULL_TREE
, NULL_TREE
);
1976 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1978 gsi
= gsi_start_bb (then_bb
);
1979 /* Insert actual store. */
1980 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1981 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1983 edge e1
= single_succ_edge (new_bb
);
1984 edge e2
= make_edge (new_bb
, then_bb
,
1985 EDGE_TRUE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1986 e2
->probability
= flag_probability
;
1988 e1
->flags
|= EDGE_FALSE_VALUE
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0);
1989 e1
->flags
&= ~EDGE_FALLTHRU
;
1991 e1
->probability
= flag_probability
.invert ();
1993 then_old_edge
= make_single_succ_edge (then_bb
, old_dest
,
1994 EDGE_FALLTHRU
| (irr
? EDGE_IRREDUCIBLE_LOOP
: 0));
1996 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
1998 if (append_cond_position
)
2000 basic_block prevbb
= last_cond_fallthru
->src
;
2001 redirect_edge_succ (last_cond_fallthru
, new_bb
);
2002 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
2003 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
2004 recompute_dominator (CDI_DOMINATORS
, old_dest
));
2007 /* ?? Because stores may alias, they must happen in the exact
2008 sequence they originally happened. Save the position right after
2009 the (_lsm) store we just created so we can continue appending after
2010 it and maintain the original order. */
2011 append_cond_position
= then_old_edge
;
2012 last_cond_fallthru
= find_edge (new_bb
, old_dest
);
2014 if (!loop_has_only_one_exit
)
2015 for (gphi_iterator gpi
= gsi_start_phis (old_dest
);
2016 !gsi_end_p (gpi
); gsi_next (&gpi
))
2018 gphi
*phi
= gpi
.phi ();
2021 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2022 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
2024 tree arg
= gimple_phi_arg_def (phi
, i
);
2025 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
2031 /* When REF is set on the location, set flag indicating the store. */
2033 class sm_set_flag_if_changed
2036 sm_set_flag_if_changed (tree flag_
, hash_set
<basic_block
> *bbs_
)
2037 : flag (flag_
), bbs (bbs_
) {}
2038 bool operator () (mem_ref_loc
*loc
);
2040 hash_set
<basic_block
> *bbs
;
2044 sm_set_flag_if_changed::operator () (mem_ref_loc
*loc
)
2046 /* Only set the flag for writes. */
2047 if (is_gimple_assign (loc
->stmt
)
2048 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
2050 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
2051 gimple
*stmt
= gimple_build_assign (flag
, boolean_true_node
);
2052 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
2053 bbs
->add (gimple_bb (stmt
));
2058 /* Helper function for execute_sm. On every location where REF is
2059 set, set an appropriate flag indicating the store. */
2062 execute_sm_if_changed_flag_set (class loop
*loop
, im_mem_ref
*ref
,
2063 hash_set
<basic_block
> *bbs
)
2066 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0, "_flag");
2067 flag
= create_tmp_reg (boolean_type_node
, str
);
2068 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
, bbs
));
2076 hash_set
<basic_block
> flag_bbs
;
2079 /* Executes store motion of memory reference REF from LOOP.
2080 Exits from the LOOP are stored in EXITS. The initialization of the
2081 temporary variable is put to the preheader of the loop, and assignments
2082 to the reference from the temporary variable are emitted to exits. */
2085 execute_sm (class loop
*loop
, im_mem_ref
*ref
,
2086 hash_map
<im_mem_ref
*, sm_aux
*> &aux_map
, bool maybe_mt
)
2089 struct fmt_data fmt_data
;
2090 struct lim_aux_data
*lim_data
;
2091 bool multi_threaded_model_p
= false;
2092 gimple_stmt_iterator gsi
;
2093 sm_aux
*aux
= new sm_aux
;
2095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2097 fprintf (dump_file
, "Executing store motion of ");
2098 print_generic_expr (dump_file
, ref
->mem
.ref
);
2099 fprintf (dump_file
, " from loop %d\n", loop
->num
);
2102 aux
->tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
2103 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
2105 fmt_data
.loop
= loop
;
2106 fmt_data
.orig_loop
= loop
;
2107 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
2109 bool always_stored
= ref_always_accessed_p (loop
, ref
, true);
2111 && (bb_in_transaction (loop_preheader_edge (loop
)->src
)
2112 || (! flag_store_data_races
&& ! always_stored
)))
2113 multi_threaded_model_p
= true;
2115 if (multi_threaded_model_p
)
2117 = execute_sm_if_changed_flag_set (loop
, ref
, &aux
->flag_bbs
);
2119 aux
->store_flag
= NULL_TREE
;
2121 /* Remember variable setup. */
2122 aux_map
.put (ref
, aux
);
2124 rewrite_mem_refs (loop
, ref
, aux
->tmp_var
);
2126 /* Emit the load code on a random exit edge or into the latch if
2127 the loop does not exit, so that we are sure it will be processed
2128 by move_computations after all dependencies. */
2129 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
2131 /* Avoid doing a load if there was no load of the ref in the loop.
2132 Esp. when the ref is not always stored we cannot optimize it
2133 away later. But when it is not always stored we must use a conditional
2135 if ((!always_stored
&& !multi_threaded_model_p
)
2136 || (ref
->loaded
&& bitmap_bit_p (ref
->loaded
, loop
->num
)))
2137 load
= gimple_build_assign (aux
->tmp_var
, unshare_expr (ref
->mem
.ref
));
2140 /* If not emitting a load mark the uninitialized state on the
2141 loop entry as not to be warned for. */
2142 tree uninit
= create_tmp_reg (TREE_TYPE (aux
->tmp_var
));
2143 TREE_NO_WARNING (uninit
) = 1;
2144 load
= gimple_build_assign (aux
->tmp_var
, uninit
);
2146 lim_data
= init_lim_data (load
);
2147 lim_data
->max_loop
= loop
;
2148 lim_data
->tgt_loop
= loop
;
2149 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2151 if (multi_threaded_model_p
)
2153 load
= gimple_build_assign (aux
->store_flag
, boolean_false_node
);
2154 lim_data
= init_lim_data (load
);
2155 lim_data
->max_loop
= loop
;
2156 lim_data
->tgt_loop
= loop
;
2157 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
2161 /* sm_ord is used for ordinary stores we can retain order with respect
2163 sm_unord is used for conditional executed stores which need to be
2164 able to execute in arbitrary order with respect to other stores
2165 sm_other is used for stores we do not try to apply store motion to. */
2166 enum sm_kind
{ sm_ord
, sm_unord
, sm_other
};
2169 seq_entry (unsigned f
, sm_kind k
, tree fr
= NULL
)
2170 : first (f
), second (k
), from (fr
) {}
2177 execute_sm_exit (class loop
*loop
, edge ex
, vec
<seq_entry
> &seq
,
2178 hash_map
<im_mem_ref
*, sm_aux
*> &aux_map
, sm_kind kind
,
2179 edge
&append_cond_position
, edge
&last_cond_fallthru
)
2181 /* Sink the stores to exit from the loop. */
2182 for (unsigned i
= seq
.length (); i
> 0; --i
)
2184 im_mem_ref
*ref
= memory_accesses
.refs_list
[seq
[i
-1].first
];
2185 if (seq
[i
-1].second
== sm_other
)
2187 gcc_assert (kind
== sm_ord
&& seq
[i
-1].from
!= NULL_TREE
);
2188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2190 fprintf (dump_file
, "Re-issueing dependent store of ");
2191 print_generic_expr (dump_file
, ref
->mem
.ref
);
2192 fprintf (dump_file
, " from loop %d on exit %d -> %d\n",
2193 loop
->num
, ex
->src
->index
, ex
->dest
->index
);
2195 gassign
*store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
),
2197 gsi_insert_on_edge (ex
, store
);
2201 sm_aux
*aux
= *aux_map
.get (ref
);
2202 if (!aux
->store_flag
|| kind
== sm_ord
)
2205 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
),
2207 gsi_insert_on_edge (ex
, store
);
2210 execute_sm_if_changed (ex
, ref
->mem
.ref
, aux
->tmp_var
,
2212 loop_preheader_edge (loop
), &aux
->flag_bbs
,
2213 append_cond_position
, last_cond_fallthru
);
2218 /* Push the SM candidate at index PTR in the sequence SEQ down until
2219 we hit the next SM candidate. Return true if that went OK and
2220 false if we could not disambiguate agains another unrelated ref.
2221 Update *AT to the index where the candidate now resides. */
2224 sm_seq_push_down (vec
<seq_entry
> &seq
, unsigned ptr
, unsigned *at
)
2227 for (; ptr
> 0; --ptr
)
2229 seq_entry
&new_cand
= seq
[ptr
];
2230 seq_entry
&against
= seq
[ptr
-1];
2231 if (against
.second
== sm_ord
2232 || (against
.second
== sm_other
&& against
.from
!= NULL_TREE
))
2233 /* Found the tail of the sequence. */
2235 /* We may not ignore self-dependences here. */
2236 if (new_cand
.first
== against
.first
2237 || !refs_independent_p (memory_accesses
.refs_list
[new_cand
.first
],
2238 memory_accesses
.refs_list
[against
.first
],
2240 /* ??? Prune new_cand from the list of refs to apply SM to. */
2242 std::swap (new_cand
, against
);
2248 /* Computes the sequence of stores from candidates in REFS_NOT_IN_SEQ to SEQ
2249 walking backwards from VDEF (or the end of BB if VDEF is NULL). */
2252 sm_seq_valid_bb (class loop
*loop
, basic_block bb
, tree vdef
,
2253 vec
<seq_entry
> &seq
, bitmap refs_not_in_seq
,
2254 bitmap refs_not_supported
, bool forked
)
2257 for (gimple_stmt_iterator gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);
2260 vdef
= gimple_vdef (gsi_stmt (gsi
));
2266 gphi
*vphi
= get_virtual_phi (bb
);
2268 vdef
= gimple_phi_result (vphi
);
2272 if (single_pred_p (bb
))
2273 /* This handles the perfect nest case. */
2274 return sm_seq_valid_bb (loop
, single_pred (bb
), vdef
,
2275 seq
, refs_not_in_seq
, refs_not_supported
,
2281 gimple
*def
= SSA_NAME_DEF_STMT (vdef
);
2282 if (gimple_bb (def
) != bb
)
2284 /* If we forked by processing a PHI do not allow our walk to
2285 merge again until we handle that robustly. */
2288 /* Mark refs_not_in_seq as unsupported. */
2289 bitmap_ior_into (refs_not_supported
, refs_not_in_seq
);
2292 /* Otherwise it doesn't really matter if we end up in different
2294 bb
= gimple_bb (def
);
2296 if (gphi
*phi
= dyn_cast
<gphi
*> (def
))
2298 /* Handle CFG merges. Until we handle forks (gimple_bb (def) != bb)
2299 this is still linear.
2300 Eventually we want to cache intermediate results per BB
2301 (but we can't easily cache for different exits?). */
2302 /* Stop at PHIs with possible backedges. */
2303 if (bb
== bb
->loop_father
->header
2304 || bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2306 /* Mark refs_not_in_seq as unsupported. */
2307 bitmap_ior_into (refs_not_supported
, refs_not_in_seq
);
2310 if (gimple_phi_num_args (phi
) == 1)
2311 return sm_seq_valid_bb (loop
, gimple_phi_arg_edge (phi
, 0)->src
,
2312 gimple_phi_arg_def (phi
, 0), seq
,
2313 refs_not_in_seq
, refs_not_supported
,
2315 auto_vec
<seq_entry
> first_edge_seq
;
2316 auto_bitmap
tem_refs_not_in_seq (&lim_bitmap_obstack
);
2318 bitmap_copy (tem_refs_not_in_seq
, refs_not_in_seq
);
2319 eret
= sm_seq_valid_bb (loop
, gimple_phi_arg_edge (phi
, 0)->src
,
2320 gimple_phi_arg_def (phi
, 0),
2322 tem_refs_not_in_seq
, refs_not_supported
,
2326 /* Simplify our lives by pruning the sequence of !sm_ord. */
2327 while (!first_edge_seq
.is_empty ()
2328 && first_edge_seq
.last ().second
!= sm_ord
)
2329 first_edge_seq
.pop ();
2330 for (unsigned int i
= 1; i
< gimple_phi_num_args (phi
); ++i
)
2332 tree vuse
= gimple_phi_arg_def (phi
, i
);
2333 edge e
= gimple_phi_arg_edge (phi
, i
);
2334 auto_vec
<seq_entry
> edge_seq
;
2335 bitmap_copy (tem_refs_not_in_seq
, refs_not_in_seq
);
2336 eret
= sm_seq_valid_bb (loop
, e
->src
, vuse
, edge_seq
,
2337 tem_refs_not_in_seq
, refs_not_supported
,
2341 /* Simplify our lives by pruning the sequence of !sm_ord. */
2342 while (!edge_seq
.is_empty ()
2343 && edge_seq
.last ().second
!= sm_ord
)
2345 unsigned min_len
= MIN(first_edge_seq
.length (),
2346 edge_seq
.length ());
2347 /* Incrementally merge seqs into first_edge_seq. */
2348 for (unsigned int i
= 0; i
< min_len
; ++i
)
2350 /* ??? We can more intelligently merge when we face different
2351 order by additional sinking operations in one sequence.
2352 For now we simply mark them as to be processed by the
2353 not order-preserving SM code. */
2354 if (first_edge_seq
[i
].first
!= edge_seq
[i
].first
)
2356 if (first_edge_seq
[i
].second
== sm_ord
)
2357 bitmap_set_bit (refs_not_supported
,
2358 first_edge_seq
[i
].first
);
2359 if (edge_seq
[i
].second
== sm_ord
)
2360 bitmap_set_bit (refs_not_supported
, edge_seq
[i
].first
);
2361 first_edge_seq
[i
].second
= sm_other
;
2362 first_edge_seq
[i
].from
= NULL_TREE
;
2364 /* sm_other prevails. */
2365 else if (first_edge_seq
[i
].second
!= edge_seq
[i
].second
)
2367 /* This is just an optimization. */
2368 gcc_assert (bitmap_bit_p (refs_not_supported
,
2369 first_edge_seq
[i
].first
));
2370 first_edge_seq
[i
].second
= sm_other
;
2371 first_edge_seq
[i
].from
= NULL_TREE
;
2373 else if (first_edge_seq
[i
].second
== sm_other
2374 && first_edge_seq
[i
].from
!= NULL_TREE
2375 && (edge_seq
[i
].from
== NULL_TREE
2376 || !operand_equal_p (first_edge_seq
[i
].from
,
2377 edge_seq
[i
].from
, 0)))
2378 first_edge_seq
[i
].from
= NULL_TREE
;
2380 /* Any excess elements become sm_other since they are now
2381 coonditionally executed. */
2382 if (first_edge_seq
.length () > edge_seq
.length ())
2384 for (unsigned i
= edge_seq
.length ();
2385 i
< first_edge_seq
.length (); ++i
)
2387 if (first_edge_seq
[i
].second
== sm_ord
)
2388 bitmap_set_bit (refs_not_supported
,
2389 first_edge_seq
[i
].first
);
2390 first_edge_seq
[i
].second
= sm_other
;
2393 else if (edge_seq
.length () > first_edge_seq
.length ())
2395 for (unsigned i
= first_edge_seq
.length ();
2396 i
< edge_seq
.length (); ++i
)
2397 if (edge_seq
[i
].second
== sm_ord
)
2398 bitmap_set_bit (refs_not_supported
, edge_seq
[i
].first
);
2401 /* Use the sequence from the first edge and push SMs down. */
2402 for (unsigned i
= 0; i
< first_edge_seq
.length (); ++i
)
2404 unsigned id
= first_edge_seq
[i
].first
;
2405 seq
.safe_push (first_edge_seq
[i
]);
2407 if ((first_edge_seq
[i
].second
== sm_ord
2408 || (first_edge_seq
[i
].second
== sm_other
2409 && first_edge_seq
[i
].from
!= NULL_TREE
))
2410 && !sm_seq_push_down (seq
, seq
.length () - 1, &new_idx
))
2412 if (first_edge_seq
[i
].second
== sm_ord
)
2413 bitmap_set_bit (refs_not_supported
, id
);
2414 /* Mark it sm_other. */
2415 seq
[new_idx
].second
= sm_other
;
2416 seq
[new_idx
].from
= NULL_TREE
;
2421 lim_aux_data
*data
= get_lim_data (def
);
2423 if (data
->ref
== UNANALYZABLE_MEM_ID
)
2425 /* One of the stores we want to apply SM to and we've not yet seen. */
2426 else if (bitmap_clear_bit (refs_not_in_seq
, data
->ref
))
2428 seq
.safe_push (seq_entry (data
->ref
, sm_ord
));
2430 /* 1) push it down the queue until a SMed
2431 and not ignored ref is reached, skipping all not SMed refs
2432 and ignored refs via non-TBAA disambiguation. */
2434 if (!sm_seq_push_down (seq
, seq
.length () - 1, &new_idx
)
2435 /* If that fails but we did not fork yet continue, we'll see
2436 to re-materialize all of the stores in the sequence then.
2437 Further stores will only be pushed up to this one. */
2440 bitmap_set_bit (refs_not_supported
, data
->ref
);
2441 /* Mark it sm_other. */
2442 seq
[new_idx
].second
= sm_other
;
2445 /* 2) check whether we've seen all refs we want to SM and if so
2446 declare success for the active exit */
2447 if (bitmap_empty_p (refs_not_in_seq
))
2451 /* Another store not part of the final sequence. Simply push it. */
2452 seq
.safe_push (seq_entry (data
->ref
, sm_other
,
2453 gimple_assign_rhs1 (def
)));
2455 vdef
= gimple_vuse (def
);
2460 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2461 edges of the LOOP. */
2464 hoist_memory_references (class loop
*loop
, bitmap mem_refs
,
2471 /* To address PR57359 before actually applying store-motion check
2472 the candidates found for validity with regards to reordering
2473 relative to other stores which we until here disambiguated using
2474 TBAA which isn't valid.
2475 What matters is the order of the last stores to the mem_refs
2476 with respect to the other stores of the loop at the point of the
2479 /* For each exit compute the store order, pruning from mem_refs
2481 /* The complexity of this is at least
2482 O(number of exits * number of SM refs) but more approaching
2483 O(number of exits * number of SM refs * number of stores). */
2484 /* ??? Somehow do this in a single sweep over the loop body. */
2485 auto_vec
<std::pair
<edge
, vec
<seq_entry
> > > sms
;
2486 auto_bitmap
refs_not_supported (&lim_bitmap_obstack
);
2488 FOR_EACH_VEC_ELT (exits
, i
, e
)
2492 auto_bitmap
refs_not_in_seq (&lim_bitmap_obstack
);
2493 bitmap_copy (refs_not_in_seq
, mem_refs
);
2494 int res
= sm_seq_valid_bb (loop
, e
->src
, NULL_TREE
,
2495 seq
, refs_not_in_seq
,
2496 refs_not_supported
, false);
2499 bitmap_copy (refs_not_supported
, mem_refs
);
2502 sms
.safe_push (std::make_pair (e
, seq
));
2505 /* Prune pruned mem_refs from earlier processed exits. */
2506 bool changed
= !bitmap_empty_p (refs_not_supported
);
2510 std::pair
<edge
, vec
<seq_entry
> > *seq
;
2511 FOR_EACH_VEC_ELT (sms
, i
, seq
)
2513 bool need_to_push
= false;
2514 for (unsigned i
= 0; i
< seq
->second
.length (); ++i
)
2516 sm_kind kind
= seq
->second
[i
].second
;
2517 if (kind
== sm_other
&& seq
->second
[i
].from
== NULL_TREE
)
2519 unsigned id
= seq
->second
[i
].first
;
2522 && bitmap_bit_p (refs_not_supported
, id
))
2524 seq
->second
[i
].second
= sm_other
;
2525 gcc_assert (seq
->second
[i
].from
== NULL_TREE
);
2526 need_to_push
= true;
2528 else if (need_to_push
2529 && !sm_seq_push_down (seq
->second
, i
, &new_idx
))
2531 /* We need to push down both sm_ord and sm_other
2532 but for the latter we need to disqualify all
2536 if (bitmap_set_bit (refs_not_supported
, id
))
2538 seq
->second
[new_idx
].second
= sm_other
;
2542 for (unsigned j
= seq
->second
.length () - 1;
2544 if (seq
->second
[j
].second
== sm_ord
2545 && bitmap_set_bit (refs_not_supported
,
2546 seq
->second
[j
].first
))
2548 seq
->second
.truncate (new_idx
);
2555 std::pair
<edge
, vec
<seq_entry
> > *seq
;
2556 FOR_EACH_VEC_ELT (sms
, i
, seq
)
2558 /* Prune sm_other from the end. */
2559 while (!seq
->second
.is_empty ()
2560 && seq
->second
.last ().second
== sm_other
)
2562 /* Prune duplicates from the start. */
2563 auto_bitmap
seen (&lim_bitmap_obstack
);
2565 for (j
= k
= 0; j
< seq
->second
.length (); ++j
)
2566 if (bitmap_set_bit (seen
, seq
->second
[j
].first
))
2569 seq
->second
[k
] = seq
->second
[j
];
2572 seq
->second
.truncate (k
);
2575 FOR_EACH_VEC_ELT (seq
->second
, j
, e
)
2576 gcc_assert (e
->second
== sm_ord
2577 || (e
->second
== sm_other
&& e
->from
!= NULL_TREE
));
2580 /* Verify dependence for refs we cannot handle with the order preserving
2581 code (refs_not_supported) or prune them from mem_refs. */
2582 auto_vec
<seq_entry
> unord_refs
;
2583 EXECUTE_IF_SET_IN_BITMAP (refs_not_supported
, 0, i
, bi
)
2585 ref
= memory_accesses
.refs_list
[i
];
2586 if (!ref_indep_loop_p (loop
, ref
, sm_waw
))
2587 bitmap_clear_bit (mem_refs
, i
);
2588 /* We've now verified store order for ref with respect to all other
2589 stores in the loop does not matter. */
2591 unord_refs
.safe_push (seq_entry (i
, sm_unord
));
2594 hash_map
<im_mem_ref
*, sm_aux
*> aux_map
;
2596 /* Execute SM but delay the store materialization for ordered
2597 sequences on exit. */
2598 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2600 ref
= memory_accesses
.refs_list
[i
];
2601 execute_sm (loop
, ref
, aux_map
, bitmap_bit_p (refs_not_supported
, i
));
2604 /* Materialize ordered store sequences on exits. */
2605 FOR_EACH_VEC_ELT (exits
, i
, e
)
2607 edge append_cond_position
= NULL
;
2608 edge last_cond_fallthru
= NULL
;
2609 if (i
< sms
.length ())
2611 gcc_assert (sms
[i
].first
== e
);
2612 execute_sm_exit (loop
, e
, sms
[i
].second
, aux_map
, sm_ord
,
2613 append_cond_position
, last_cond_fallthru
);
2614 sms
[i
].second
.release ();
2616 if (!unord_refs
.is_empty ())
2617 execute_sm_exit (loop
, e
, unord_refs
, aux_map
, sm_unord
,
2618 append_cond_position
, last_cond_fallthru
);
2619 /* Commit edge inserts here to preserve the order of stores
2620 when an exit exits multiple loops. */
2621 gsi_commit_one_edge_insert (e
, NULL
);
2624 for (hash_map
<im_mem_ref
*, sm_aux
*>::iterator iter
= aux_map
.begin ();
2625 iter
!= aux_map
.end (); ++iter
)
2626 delete (*iter
).second
;
2629 class ref_always_accessed
2632 ref_always_accessed (class loop
*loop_
, bool stored_p_
)
2633 : loop (loop_
), stored_p (stored_p_
) {}
2634 bool operator () (mem_ref_loc
*loc
);
2640 ref_always_accessed::operator () (mem_ref_loc
*loc
)
2642 class loop
*must_exec
;
2644 struct lim_aux_data
*lim_data
= get_lim_data (loc
->stmt
);
2648 /* If we require an always executed store make sure the statement
2652 tree lhs
= gimple_get_lhs (loc
->stmt
);
2654 || !(DECL_P (lhs
) || REFERENCE_CLASS_P (lhs
)))
2658 must_exec
= lim_data
->always_executed_in
;
2662 if (must_exec
== loop
2663 || flow_loop_nested_p (must_exec
, loop
))
2669 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2670 make sure REF is always stored to in LOOP. */
2673 ref_always_accessed_p (class loop
*loop
, im_mem_ref
*ref
, bool stored_p
)
2675 return for_all_locs_in_loop (loop
, ref
,
2676 ref_always_accessed (loop
, stored_p
));
2679 /* Returns true if REF1 and REF2 are independent. */
2682 refs_independent_p (im_mem_ref
*ref1
, im_mem_ref
*ref2
, bool tbaa_p
)
2687 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2688 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2689 ref1
->id
, ref2
->id
);
2691 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
, tbaa_p
))
2693 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2694 fprintf (dump_file
, "dependent.\n");
2699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2700 fprintf (dump_file
, "independent.\n");
2705 /* Returns true if REF is independent on all other accessess in LOOP.
2706 KIND specifies the kind of dependence to consider.
2707 lim_raw assumes REF is not stored in LOOP and disambiguates RAW
2708 dependences so if true REF can be hoisted out of LOOP
2709 sm_war disambiguates a store REF against all other loads to see
2710 whether the store can be sunk across loads out of LOOP
2711 sm_waw disambiguates a store REF against all other stores to see
2712 whether the store can be sunk across stores out of LOOP. */
2715 ref_indep_loop_p (class loop
*loop
, im_mem_ref
*ref
, dep_kind kind
)
2717 bool indep_p
= true;
2718 bitmap refs_to_check
;
2721 refs_to_check
= &memory_accesses
.refs_loaded_in_loop
[loop
->num
];
2723 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2725 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2729 /* tri-state, { unknown, independent, dependent } */
2730 dep_state state
= query_loop_dependence (loop
, ref
, kind
);
2731 if (state
!= dep_unknown
)
2732 return state
== dep_independent
? true : false;
2734 class loop
*inner
= loop
->inner
;
2737 if (!ref_indep_loop_p (inner
, ref
, kind
))
2742 inner
= inner
->next
;
2749 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2751 im_mem_ref
*aref
= memory_accesses
.refs_list
[i
];
2752 if (!refs_independent_p (ref
, aref
, kind
!= sm_waw
))
2761 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2762 fprintf (dump_file
, "Querying %s dependencies of ref %u in loop %d: %s\n",
2763 kind
== lim_raw
? "RAW" : (kind
== sm_war
? "SM WAR" : "SM WAW"),
2764 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2766 /* Record the computed result in the cache. */
2767 record_loop_dependence (loop
, ref
, kind
,
2768 indep_p
? dep_independent
: dep_dependent
);
2774 /* Returns true if we can perform store motion of REF from LOOP. */
2777 can_sm_ref_p (class loop
*loop
, im_mem_ref
*ref
)
2781 /* Can't hoist unanalyzable refs. */
2782 if (!MEM_ANALYZABLE (ref
))
2785 /* It should be movable. */
2786 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2787 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2788 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2791 /* If it can throw fail, we do not properly update EH info. */
2792 if (tree_could_throw_p (ref
->mem
.ref
))
2795 /* If it can trap, it must be always executed in LOOP.
2796 Readonly memory locations may trap when storing to them, but
2797 tree_could_trap_p is a predicate for rvalues, so check that
2799 base
= get_base_address (ref
->mem
.ref
);
2800 if ((tree_could_trap_p (ref
->mem
.ref
)
2801 || (DECL_P (base
) && TREE_READONLY (base
)))
2802 /* ??? We can at least use false here, allowing loads? We
2803 are forcing conditional stores if the ref is not always
2804 stored to later anyway. So this would only guard
2805 the load we need to emit. Thus when the ref is not
2806 loaded we can elide this completely? */
2807 && !ref_always_accessed_p (loop
, ref
, true))
2810 /* Verify all loads of ref can be hoisted. */
2812 && bitmap_bit_p (ref
->loaded
, loop
->num
)
2813 && !ref_indep_loop_p (loop
, ref
, lim_raw
))
2816 /* Verify the candidate can be disambiguated against all loads,
2817 that is, we can elide all in-loop stores. Disambiguation
2818 against stores is done later when we cannot guarantee preserving
2819 the order of stores. */
2820 if (!ref_indep_loop_p (loop
, ref
, sm_war
))
2826 /* Marks the references in LOOP for that store motion should be performed
2827 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2828 motion was performed in one of the outer loops. */
2831 find_refs_for_sm (class loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2833 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2838 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2840 ref
= memory_accesses
.refs_list
[i
];
2841 if (can_sm_ref_p (loop
, ref
) && dbg_cnt (lim
))
2842 bitmap_set_bit (refs_to_sm
, i
);
2846 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2847 for a store motion optimization (i.e. whether we can insert statement
2851 loop_suitable_for_sm (class loop
*loop ATTRIBUTE_UNUSED
,
2857 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2858 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2864 /* Try to perform store motion for all memory references modified inside
2865 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2866 store motion was executed in one of the outer loops. */
2869 store_motion_loop (class loop
*loop
, bitmap sm_executed
)
2871 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2872 class loop
*subloop
;
2873 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2875 if (loop_suitable_for_sm (loop
, exits
))
2877 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2878 if (!bitmap_empty_p (sm_in_loop
))
2879 hoist_memory_references (loop
, sm_in_loop
, exits
);
2882 bitmap_ior_into (sm_executed
, sm_in_loop
);
2883 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2884 store_motion_loop (subloop
, sm_executed
);
2885 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2886 BITMAP_FREE (sm_in_loop
);
2889 /* Try to perform store motion for all memory references modified inside
2893 do_store_motion (void)
2896 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2898 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2899 store_motion_loop (loop
, sm_executed
);
2901 BITMAP_FREE (sm_executed
);
2904 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2905 for each such basic block bb records the outermost loop for that execution
2906 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2907 blocks that contain a nonpure call. */
2910 fill_always_executed_in_1 (class loop
*loop
, sbitmap contains_call
)
2912 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2915 class loop
*inn_loop
= loop
;
2917 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2919 bbs
= get_loop_body_in_dom_order (loop
);
2921 for (i
= 0; i
< loop
->num_nodes
; i
++)
2926 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2929 if (bitmap_bit_p (contains_call
, bb
->index
))
2932 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2934 /* If there is an exit from this BB. */
2935 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2937 /* Or we enter a possibly non-finite loop. */
2938 if (flow_loop_nested_p (bb
->loop_father
,
2939 e
->dest
->loop_father
)
2940 && ! finite_loop_p (e
->dest
->loop_father
))
2946 /* A loop might be infinite (TODO use simple loop analysis
2947 to disprove this if possible). */
2948 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2951 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2954 if (bb
->loop_father
->header
== bb
)
2956 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2959 /* In a loop that is always entered we may proceed anyway.
2960 But record that we entered it and stop once we leave it. */
2961 inn_loop
= bb
->loop_father
;
2967 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2968 if (last
== loop
->header
)
2970 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2976 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2977 fill_always_executed_in_1 (loop
, contains_call
);
2980 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2981 for each such basic block bb records the outermost loop for that execution
2982 of its header implies execution of bb. */
2985 fill_always_executed_in (void)
2990 auto_sbitmap
contains_call (last_basic_block_for_fn (cfun
));
2991 bitmap_clear (contains_call
);
2992 FOR_EACH_BB_FN (bb
, cfun
)
2994 gimple_stmt_iterator gsi
;
2995 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2997 if (nonpure_call_p (gsi_stmt (gsi
)))
3001 if (!gsi_end_p (gsi
))
3002 bitmap_set_bit (contains_call
, bb
->index
);
3005 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
3006 fill_always_executed_in_1 (loop
, contains_call
);
3010 /* Compute the global information needed by the loop invariant motion pass. */
3013 tree_ssa_lim_initialize (void)
3018 bitmap_obstack_initialize (&lim_bitmap_obstack
);
3019 gcc_obstack_init (&mem_ref_obstack
);
3020 lim_aux_data_map
= new hash_map
<gimple
*, lim_aux_data
*>;
3023 compute_transaction_bits ();
3025 memory_accesses
.refs
= new hash_table
<mem_ref_hasher
> (100);
3026 memory_accesses
.refs_list
.create (100);
3027 /* Allocate a special, unanalyzable mem-ref with ID zero. */
3028 memory_accesses
.refs_list
.quick_push
3029 (mem_ref_alloc (NULL
, 0, UNANALYZABLE_MEM_ID
));
3031 memory_accesses
.refs_loaded_in_loop
.create (number_of_loops (cfun
));
3032 memory_accesses
.refs_loaded_in_loop
.quick_grow (number_of_loops (cfun
));
3033 memory_accesses
.refs_stored_in_loop
.create (number_of_loops (cfun
));
3034 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
3035 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops (cfun
));
3036 memory_accesses
.all_refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
3038 for (i
= 0; i
< number_of_loops (cfun
); i
++)
3040 bitmap_initialize (&memory_accesses
.refs_loaded_in_loop
[i
],
3041 &lim_bitmap_obstack
);
3042 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
3043 &lim_bitmap_obstack
);
3044 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
3045 &lim_bitmap_obstack
);
3048 memory_accesses
.ttae_cache
= NULL
;
3050 /* Initialize bb_loop_postorder with a mapping from loop->num to
3051 its postorder index. */
3053 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops (cfun
));
3054 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3055 bb_loop_postorder
[loop
->num
] = i
++;
3058 /* Cleans up after the invariant motion pass. */
3061 tree_ssa_lim_finalize (void)
3067 FOR_EACH_BB_FN (bb
, cfun
)
3068 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
3070 bitmap_obstack_release (&lim_bitmap_obstack
);
3071 delete lim_aux_data_map
;
3073 delete memory_accesses
.refs
;
3074 memory_accesses
.refs
= NULL
;
3076 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
3078 memory_accesses
.refs_list
.release ();
3079 obstack_free (&mem_ref_obstack
, NULL
);
3081 memory_accesses
.refs_loaded_in_loop
.release ();
3082 memory_accesses
.refs_stored_in_loop
.release ();
3083 memory_accesses
.all_refs_stored_in_loop
.release ();
3085 if (memory_accesses
.ttae_cache
)
3086 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
3088 free (bb_loop_postorder
);
3091 /* Moves invariants from loops. Only "expensive" invariants are moved out --
3092 i.e. those that are likely to be win regardless of the register pressure. */
3095 tree_ssa_lim (function
*fun
)
3097 unsigned int todo
= 0;
3099 tree_ssa_lim_initialize ();
3101 /* Gathers information about memory accesses in the loops. */
3102 analyze_memory_references ();
3104 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
3105 fill_always_executed_in ();
3107 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (fun
));
3108 int n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
3110 /* For each statement determine the outermost loop in that it is
3111 invariant and cost for computing the invariant. */
3112 for (int i
= 0; i
< n
; ++i
)
3113 compute_invariantness (BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]));
3115 /* Execute store motion. Force the necessary invariants to be moved
3116 out of the loops as well. */
3120 rpo
= XNEWVEC (int, last_basic_block_for_fn (fun
));
3121 n
= pre_and_rev_post_order_compute_fn (fun
, NULL
, rpo
, false);
3123 /* Move the expressions that are expensive enough. */
3124 for (int i
= 0; i
< n
; ++i
)
3125 todo
|= move_computations_worker (BASIC_BLOCK_FOR_FN (fun
, rpo
[i
]));
3129 gsi_commit_edge_inserts ();
3130 if (need_ssa_update_p (fun
))
3131 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3133 tree_ssa_lim_finalize ();
3138 /* Loop invariant motion pass. */
3142 const pass_data pass_data_lim
=
3144 GIMPLE_PASS
, /* type */
3146 OPTGROUP_LOOP
, /* optinfo_flags */
3148 PROP_cfg
, /* properties_required */
3149 0, /* properties_provided */
3150 0, /* properties_destroyed */
3151 0, /* todo_flags_start */
3152 0, /* todo_flags_finish */
3155 class pass_lim
: public gimple_opt_pass
3158 pass_lim (gcc::context
*ctxt
)
3159 : gimple_opt_pass (pass_data_lim
, ctxt
)
3162 /* opt_pass methods: */
3163 opt_pass
* clone () { return new pass_lim (m_ctxt
); }
3164 virtual bool gate (function
*) { return flag_tree_loop_im
!= 0; }
3165 virtual unsigned int execute (function
*);
3167 }; // class pass_lim
3170 pass_lim::execute (function
*fun
)
3172 bool in_loop_pipeline
= scev_initialized_p ();
3173 if (!in_loop_pipeline
)
3174 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
3176 if (number_of_loops (fun
) <= 1)
3178 unsigned int todo
= tree_ssa_lim (fun
);
3180 if (!in_loop_pipeline
)
3181 loop_optimizer_finalize ();
3190 make_pass_lim (gcc::context
*ctxt
)
3192 return new pass_lim (ctxt
);