1 /* Loop invariant motion.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
29 #include "gimple-ssa.h"
31 #include "tree-phinodes.h"
32 #include "ssa-iterators.h"
33 #include "tree-ssanames.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop.h"
36 #include "tree-into-ssa.h"
40 #include "tree-pass.h"
42 #include "hash-table.h"
43 #include "tree-affine.h"
44 #include "pointer-set.h"
45 #include "tree-ssa-propagate.h"
47 /* TODO: Support for predicated code motion. I.e.
58 Where COND and INV are invariants, but evaluating INV may trap or be
59 invalid from some other reason if !COND. This may be transformed to
69 /* The auxiliary data kept for each statement. */
73 struct loop
*max_loop
; /* The outermost loop in that the statement
76 struct loop
*tgt_loop
; /* The loop out of that we want to move the
79 struct loop
*always_executed_in
;
80 /* The outermost loop for that we are sure
81 the statement is executed if the loop
84 unsigned cost
; /* Cost of the computation performed by the
87 vec
<gimple
> depends
; /* Vector of statements that must be also
88 hoisted out of the loop when this statement
89 is hoisted; i.e. those that define the
90 operands of the statement and are inside of
94 /* Maps statements to their lim_aux_data. */
96 static struct pointer_map_t
*lim_aux_data_map
;
98 /* Description of a memory reference location. */
100 typedef struct mem_ref_loc
102 tree
*ref
; /* The reference itself. */
103 gimple stmt
; /* The statement in that it occurs. */
107 /* Description of a memory reference. */
109 typedef struct mem_ref
111 unsigned id
; /* ID assigned to the memory reference
112 (its index in memory_accesses.refs_list) */
113 hashval_t hash
; /* Its hash value. */
115 /* The memory access itself and associated caching of alias-oracle
119 bitmap_head stored
; /* The set of loops in that this memory location
121 vec
<vec
<mem_ref_loc
> > accesses_in_loop
;
122 /* The locations of the accesses. Vector
123 indexed by the loop number. */
125 /* The following sets are computed on demand. We keep both set and
126 its complement, so that we know whether the information was
127 already computed or not. */
128 bitmap_head indep_loop
; /* The set of loops in that the memory
129 reference is independent, meaning:
130 If it is stored in the loop, this store
131 is independent on all other loads and
133 If it is only loaded, then it is independent
134 on all stores in the loop. */
135 bitmap_head dep_loop
; /* The complement of INDEP_LOOP. */
138 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
139 to record (in)dependence against stores in the loop and its subloops, the
140 second to record (in)dependence against all references in the loop
142 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
144 /* Mem_ref hashtable helpers. */
146 struct mem_ref_hasher
: typed_noop_remove
<mem_ref
>
148 typedef mem_ref value_type
;
149 typedef tree_node compare_type
;
150 static inline hashval_t
hash (const value_type
*);
151 static inline bool equal (const value_type
*, const compare_type
*);
154 /* A hash function for struct mem_ref object OBJ. */
157 mem_ref_hasher::hash (const value_type
*mem
)
162 /* An equality function for struct mem_ref object MEM1 with
163 memory reference OBJ2. */
166 mem_ref_hasher::equal (const value_type
*mem1
, const compare_type
*obj2
)
168 return operand_equal_p (mem1
->mem
.ref
, (const_tree
) obj2
, 0);
172 /* Description of memory accesses in loops. */
176 /* The hash table of memory references accessed in loops. */
177 hash_table
<mem_ref_hasher
> refs
;
179 /* The list of memory references. */
180 vec
<mem_ref_p
> refs_list
;
182 /* The set of memory references accessed in each loop. */
183 vec
<bitmap_head
> refs_in_loop
;
185 /* The set of memory references stored in each loop. */
186 vec
<bitmap_head
> refs_stored_in_loop
;
188 /* The set of memory references stored in each loop, including subloops . */
189 vec
<bitmap_head
> all_refs_stored_in_loop
;
191 /* Cache for expanding memory addresses. */
192 struct pointer_map_t
*ttae_cache
;
195 /* Obstack for the bitmaps in the above data structures. */
196 static bitmap_obstack lim_bitmap_obstack
;
198 static bool ref_indep_loop_p (struct loop
*, mem_ref_p
);
200 /* Minimum cost of an expensive expression. */
201 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
203 /* The outermost loop for which execution of the header guarantees that the
204 block will be executed. */
205 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
206 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
208 /* ID of the shared unanalyzable mem. */
209 #define UNANALYZABLE_MEM_ID 0
211 /* Whether the reference was analyzable. */
212 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
214 static struct lim_aux_data
*
215 init_lim_data (gimple stmt
)
217 void **p
= pointer_map_insert (lim_aux_data_map
, stmt
);
219 *p
= XCNEW (struct lim_aux_data
);
220 return (struct lim_aux_data
*) *p
;
223 static struct lim_aux_data
*
224 get_lim_data (gimple stmt
)
226 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
230 return (struct lim_aux_data
*) *p
;
233 /* Releases the memory occupied by DATA. */
236 free_lim_aux_data (struct lim_aux_data
*data
)
238 data
->depends
.release ();
243 clear_lim_data (gimple stmt
)
245 void **p
= pointer_map_contains (lim_aux_data_map
, stmt
);
249 free_lim_aux_data ((struct lim_aux_data
*) *p
);
254 /* The possibilities of statement movement. */
257 MOVE_IMPOSSIBLE
, /* No movement -- side effect expression. */
258 MOVE_PRESERVE_EXECUTION
, /* Must not cause the non-executed statement
259 become executed -- memory accesses, ... */
260 MOVE_POSSIBLE
/* Unlimited movement. */
264 /* If it is possible to hoist the statement STMT unconditionally,
265 returns MOVE_POSSIBLE.
266 If it is possible to hoist the statement STMT, but we must avoid making
267 it executed if it would not be executed in the original program (e.g.
268 because it may trap), return MOVE_PRESERVE_EXECUTION.
269 Otherwise return MOVE_IMPOSSIBLE. */
272 movement_possibility (gimple stmt
)
275 enum move_pos ret
= MOVE_POSSIBLE
;
277 if (flag_unswitch_loops
278 && gimple_code (stmt
) == GIMPLE_COND
)
280 /* If we perform unswitching, force the operands of the invariant
281 condition to be moved out of the loop. */
282 return MOVE_POSSIBLE
;
285 if (gimple_code (stmt
) == GIMPLE_PHI
286 && gimple_phi_num_args (stmt
) <= 2
287 && !virtual_operand_p (gimple_phi_result (stmt
))
288 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt
)))
289 return MOVE_POSSIBLE
;
291 if (gimple_get_lhs (stmt
) == NULL_TREE
)
292 return MOVE_IMPOSSIBLE
;
294 if (gimple_vdef (stmt
))
295 return MOVE_IMPOSSIBLE
;
297 if (stmt_ends_bb_p (stmt
)
298 || gimple_has_volatile_ops (stmt
)
299 || gimple_has_side_effects (stmt
)
300 || stmt_could_throw_p (stmt
))
301 return MOVE_IMPOSSIBLE
;
303 if (is_gimple_call (stmt
))
305 /* While pure or const call is guaranteed to have no side effects, we
306 cannot move it arbitrarily. Consider code like
308 char *s = something ();
318 Here the strlen call cannot be moved out of the loop, even though
319 s is invariant. In addition to possibly creating a call with
320 invalid arguments, moving out a function call that is not executed
321 may cause performance regressions in case the call is costly and
322 not executed at all. */
323 ret
= MOVE_PRESERVE_EXECUTION
;
324 lhs
= gimple_call_lhs (stmt
);
326 else if (is_gimple_assign (stmt
))
327 lhs
= gimple_assign_lhs (stmt
);
329 return MOVE_IMPOSSIBLE
;
331 if (TREE_CODE (lhs
) == SSA_NAME
332 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
333 return MOVE_IMPOSSIBLE
;
335 if (TREE_CODE (lhs
) != SSA_NAME
336 || gimple_could_trap_p (stmt
))
337 return MOVE_PRESERVE_EXECUTION
;
339 /* Non local loads in a transaction cannot be hoisted out. Well,
340 unless the load happens on every path out of the loop, but we
341 don't take this into account yet. */
343 && gimple_in_transaction (stmt
)
344 && gimple_assign_single_p (stmt
))
346 tree rhs
= gimple_assign_rhs1 (stmt
);
347 if (DECL_P (rhs
) && is_global_var (rhs
))
351 fprintf (dump_file
, "Cannot hoist conditional load of ");
352 print_generic_expr (dump_file
, rhs
, TDF_SLIM
);
353 fprintf (dump_file
, " because it is in a transaction.\n");
355 return MOVE_IMPOSSIBLE
;
362 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
363 loop to that we could move the expression using DEF if it did not have
364 other operands, i.e. the outermost loop enclosing LOOP in that the value
365 of DEF is invariant. */
368 outermost_invariant_loop (tree def
, struct loop
*loop
)
372 struct loop
*max_loop
;
373 struct lim_aux_data
*lim_data
;
376 return superloop_at_depth (loop
, 1);
378 if (TREE_CODE (def
) != SSA_NAME
)
380 gcc_assert (is_gimple_min_invariant (def
));
381 return superloop_at_depth (loop
, 1);
384 def_stmt
= SSA_NAME_DEF_STMT (def
);
385 def_bb
= gimple_bb (def_stmt
);
387 return superloop_at_depth (loop
, 1);
389 max_loop
= find_common_loop (loop
, def_bb
->loop_father
);
391 lim_data
= get_lim_data (def_stmt
);
392 if (lim_data
!= NULL
&& lim_data
->max_loop
!= NULL
)
393 max_loop
= find_common_loop (max_loop
,
394 loop_outer (lim_data
->max_loop
));
395 if (max_loop
== loop
)
397 max_loop
= superloop_at_depth (loop
, loop_depth (max_loop
) + 1);
402 /* DATA is a structure containing information associated with a statement
403 inside LOOP. DEF is one of the operands of this statement.
405 Find the outermost loop enclosing LOOP in that value of DEF is invariant
406 and record this in DATA->max_loop field. If DEF itself is defined inside
407 this loop as well (i.e. we need to hoist it out of the loop if we want
408 to hoist the statement represented by DATA), record the statement in that
409 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
410 add the cost of the computation of DEF to the DATA->cost.
412 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
415 add_dependency (tree def
, struct lim_aux_data
*data
, struct loop
*loop
,
418 gimple def_stmt
= SSA_NAME_DEF_STMT (def
);
419 basic_block def_bb
= gimple_bb (def_stmt
);
420 struct loop
*max_loop
;
421 struct lim_aux_data
*def_data
;
426 max_loop
= outermost_invariant_loop (def
, loop
);
430 if (flow_loop_nested_p (data
->max_loop
, max_loop
))
431 data
->max_loop
= max_loop
;
433 def_data
= get_lim_data (def_stmt
);
438 /* Only add the cost if the statement defining DEF is inside LOOP,
439 i.e. if it is likely that by moving the invariants dependent
440 on it, we will be able to avoid creating a new register for
441 it (since it will be only used in these dependent invariants). */
442 && def_bb
->loop_father
== loop
)
443 data
->cost
+= def_data
->cost
;
445 data
->depends
.safe_push (def_stmt
);
450 /* Returns an estimate for a cost of statement STMT. The values here
451 are just ad-hoc constants, similar to costs for inlining. */
454 stmt_cost (gimple stmt
)
456 /* Always try to create possibilities for unswitching. */
457 if (gimple_code (stmt
) == GIMPLE_COND
458 || gimple_code (stmt
) == GIMPLE_PHI
)
459 return LIM_EXPENSIVE
;
461 /* We should be hoisting calls if possible. */
462 if (is_gimple_call (stmt
))
466 /* Unless the call is a builtin_constant_p; this always folds to a
467 constant, so moving it is useless. */
468 fndecl
= gimple_call_fndecl (stmt
);
470 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
471 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_CONSTANT_P
)
474 return LIM_EXPENSIVE
;
477 /* Hoisting memory references out should almost surely be a win. */
478 if (gimple_references_memory_p (stmt
))
479 return LIM_EXPENSIVE
;
481 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
484 switch (gimple_assign_rhs_code (stmt
))
487 case WIDEN_MULT_EXPR
:
488 case WIDEN_MULT_PLUS_EXPR
:
489 case WIDEN_MULT_MINUS_EXPR
:
502 /* Division and multiplication are usually expensive. */
503 return LIM_EXPENSIVE
;
507 case WIDEN_LSHIFT_EXPR
:
510 /* Shifts and rotates are usually expensive. */
511 return LIM_EXPENSIVE
;
514 /* Make vector construction cost proportional to the number
516 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt
));
520 /* Whether or not something is wrapped inside a PAREN_EXPR
521 should not change move cost. Nor should an intermediate
522 unpropagated SSA name copy. */
530 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
531 REF is independent. If REF is not independent in LOOP, NULL is returned
535 outermost_indep_loop (struct loop
*outer
, struct loop
*loop
, mem_ref_p ref
)
539 if (bitmap_bit_p (&ref
->stored
, loop
->num
))
544 aloop
= superloop_at_depth (loop
, loop_depth (aloop
) + 1))
545 if (!bitmap_bit_p (&ref
->stored
, aloop
->num
)
546 && ref_indep_loop_p (aloop
, ref
))
549 if (ref_indep_loop_p (loop
, ref
))
555 /* If there is a simple load or store to a memory reference in STMT, returns
556 the location of the memory reference, and sets IS_STORE according to whether
557 it is a store or load. Otherwise, returns NULL. */
560 simple_mem_ref_in_stmt (gimple stmt
, bool *is_store
)
564 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
565 if (!gimple_assign_single_p (stmt
))
568 lhs
= gimple_assign_lhs_ptr (stmt
);
569 rhs
= gimple_assign_rhs1_ptr (stmt
);
571 if (TREE_CODE (*lhs
) == SSA_NAME
&& gimple_vuse (stmt
))
576 else if (gimple_vdef (stmt
)
577 && (TREE_CODE (*rhs
) == SSA_NAME
|| is_gimple_min_invariant (*rhs
)))
586 /* Returns the memory reference contained in STMT. */
589 mem_ref_in_stmt (gimple stmt
)
592 tree
*mem
= simple_mem_ref_in_stmt (stmt
, &store
);
600 hash
= iterative_hash_expr (*mem
, 0);
601 ref
= memory_accesses
.refs
.find_with_hash (*mem
, hash
);
603 gcc_assert (ref
!= NULL
);
607 /* From a controlling predicate in DOM determine the arguments from
608 the PHI node PHI that are chosen if the predicate evaluates to
609 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
610 they are non-NULL. Returns true if the arguments can be determined,
611 else return false. */
614 extract_true_false_args_from_phi (basic_block dom
, gimple phi
,
615 tree
*true_arg_p
, tree
*false_arg_p
)
617 basic_block bb
= gimple_bb (phi
);
618 edge true_edge
, false_edge
, tem
;
619 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
;
621 /* We have to verify that one edge into the PHI node is dominated
622 by the true edge of the predicate block and the other edge
623 dominated by the false edge. This ensures that the PHI argument
624 we are going to take is completely determined by the path we
625 take from the predicate block.
626 We can only use BB dominance checks below if the destination of
627 the true/false edges are dominated by their edge, thus only
628 have a single predecessor. */
629 extract_true_false_edges_from_block (dom
, &true_edge
, &false_edge
);
630 tem
= EDGE_PRED (bb
, 0);
632 || (single_pred_p (true_edge
->dest
)
633 && (tem
->src
== true_edge
->dest
634 || dominated_by_p (CDI_DOMINATORS
,
635 tem
->src
, true_edge
->dest
))))
636 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
637 else if (tem
== false_edge
638 || (single_pred_p (false_edge
->dest
)
639 && (tem
->src
== false_edge
->dest
640 || dominated_by_p (CDI_DOMINATORS
,
641 tem
->src
, false_edge
->dest
))))
642 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
645 tem
= EDGE_PRED (bb
, 1);
647 || (single_pred_p (true_edge
->dest
)
648 && (tem
->src
== true_edge
->dest
649 || dominated_by_p (CDI_DOMINATORS
,
650 tem
->src
, true_edge
->dest
))))
651 arg0
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
652 else if (tem
== false_edge
653 || (single_pred_p (false_edge
->dest
)
654 && (tem
->src
== false_edge
->dest
655 || dominated_by_p (CDI_DOMINATORS
,
656 tem
->src
, false_edge
->dest
))))
657 arg1
= PHI_ARG_DEF (phi
, tem
->dest_idx
);
671 /* Determine the outermost loop to that it is possible to hoist a statement
672 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
673 the outermost loop in that the value computed by STMT is invariant.
674 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
675 we preserve the fact whether STMT is executed. It also fills other related
676 information to LIM_DATA (STMT).
678 The function returns false if STMT cannot be hoisted outside of the loop it
679 is defined in, and true otherwise. */
682 determine_max_movement (gimple stmt
, bool must_preserve_exec
)
684 basic_block bb
= gimple_bb (stmt
);
685 struct loop
*loop
= bb
->loop_father
;
687 struct lim_aux_data
*lim_data
= get_lim_data (stmt
);
691 if (must_preserve_exec
)
692 level
= ALWAYS_EXECUTED_IN (bb
);
694 level
= superloop_at_depth (loop
, 1);
695 lim_data
->max_loop
= level
;
697 if (gimple_code (stmt
) == GIMPLE_PHI
)
700 unsigned min_cost
= UINT_MAX
;
701 unsigned total_cost
= 0;
702 struct lim_aux_data
*def_data
;
704 /* We will end up promoting dependencies to be unconditionally
705 evaluated. For this reason the PHI cost (and thus the
706 cost we remove from the loop by doing the invariant motion)
707 is that of the cheapest PHI argument dependency chain. */
708 FOR_EACH_PHI_ARG (use_p
, stmt
, iter
, SSA_OP_USE
)
710 val
= USE_FROM_PTR (use_p
);
711 if (TREE_CODE (val
) != SSA_NAME
)
713 if (!add_dependency (val
, lim_data
, loop
, false))
715 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
718 min_cost
= MIN (min_cost
, def_data
->cost
);
719 total_cost
+= def_data
->cost
;
723 lim_data
->cost
+= min_cost
;
725 if (gimple_phi_num_args (stmt
) > 1)
727 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
729 if (gsi_end_p (gsi_last_bb (dom
)))
731 cond
= gsi_stmt (gsi_last_bb (dom
));
732 if (gimple_code (cond
) != GIMPLE_COND
)
734 /* Verify that this is an extended form of a diamond and
735 the PHI arguments are completely controlled by the
737 if (!extract_true_false_args_from_phi (dom
, stmt
, NULL
, NULL
))
740 /* Fold in dependencies and cost of the condition. */
741 FOR_EACH_SSA_TREE_OPERAND (val
, cond
, iter
, SSA_OP_USE
)
743 if (!add_dependency (val
, lim_data
, loop
, false))
745 def_data
= get_lim_data (SSA_NAME_DEF_STMT (val
));
747 total_cost
+= def_data
->cost
;
750 /* We want to avoid unconditionally executing very expensive
751 operations. As costs for our dependencies cannot be
752 negative just claim we are not invariand for this case.
753 We also are not sure whether the control-flow inside the
755 if (total_cost
- min_cost
>= 2 * LIM_EXPENSIVE
757 && total_cost
/ min_cost
<= 2))
760 /* Assume that the control-flow in the loop will vanish.
761 ??? We should verify this and not artificially increase
762 the cost if that is not the case. */
763 lim_data
->cost
+= stmt_cost (stmt
);
769 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_USE
)
770 if (!add_dependency (val
, lim_data
, loop
, true))
773 if (gimple_vuse (stmt
))
775 mem_ref_p ref
= mem_ref_in_stmt (stmt
);
780 = outermost_indep_loop (lim_data
->max_loop
, loop
, ref
);
781 if (!lim_data
->max_loop
)
786 if ((val
= gimple_vuse (stmt
)) != NULL_TREE
)
788 if (!add_dependency (val
, lim_data
, loop
, false))
794 lim_data
->cost
+= stmt_cost (stmt
);
799 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
800 and that one of the operands of this statement is computed by STMT.
801 Ensure that STMT (together with all the statements that define its
802 operands) is hoisted at least out of the loop LEVEL. */
805 set_level (gimple stmt
, struct loop
*orig_loop
, struct loop
*level
)
807 struct loop
*stmt_loop
= gimple_bb (stmt
)->loop_father
;
808 struct lim_aux_data
*lim_data
;
812 stmt_loop
= find_common_loop (orig_loop
, stmt_loop
);
813 lim_data
= get_lim_data (stmt
);
814 if (lim_data
!= NULL
&& lim_data
->tgt_loop
!= NULL
)
815 stmt_loop
= find_common_loop (stmt_loop
,
816 loop_outer (lim_data
->tgt_loop
));
817 if (flow_loop_nested_p (stmt_loop
, level
))
820 gcc_assert (level
== lim_data
->max_loop
821 || flow_loop_nested_p (lim_data
->max_loop
, level
));
823 lim_data
->tgt_loop
= level
;
824 FOR_EACH_VEC_ELT (lim_data
->depends
, i
, dep_stmt
)
825 set_level (dep_stmt
, orig_loop
, level
);
828 /* Determines an outermost loop from that we want to hoist the statement STMT.
829 For now we chose the outermost possible loop. TODO -- use profiling
830 information to set it more sanely. */
833 set_profitable_level (gimple stmt
)
835 set_level (stmt
, gimple_bb (stmt
)->loop_father
, get_lim_data (stmt
)->max_loop
);
838 /* Returns true if STMT is a call that has side effects. */
841 nonpure_call_p (gimple stmt
)
843 if (gimple_code (stmt
) != GIMPLE_CALL
)
846 return gimple_has_side_effects (stmt
);
849 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
852 rewrite_reciprocal (gimple_stmt_iterator
*bsi
)
854 gimple stmt
, stmt1
, stmt2
;
855 tree name
, lhs
, type
;
857 gimple_stmt_iterator gsi
;
859 stmt
= gsi_stmt (*bsi
);
860 lhs
= gimple_assign_lhs (stmt
);
861 type
= TREE_TYPE (lhs
);
863 real_one
= build_one_cst (type
);
865 name
= make_temp_ssa_name (type
, NULL
, "reciptmp");
866 stmt1
= gimple_build_assign_with_ops (RDIV_EXPR
, name
, real_one
,
867 gimple_assign_rhs2 (stmt
));
869 stmt2
= gimple_build_assign_with_ops (MULT_EXPR
, lhs
, name
,
870 gimple_assign_rhs1 (stmt
));
872 /* Replace division stmt with reciprocal and multiply stmts.
873 The multiply stmt is not invariant, so update iterator
874 and avoid rescanning. */
876 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
877 gsi_replace (&gsi
, stmt2
, true);
879 /* Continue processing with invariant reciprocal statement. */
883 /* Check if the pattern at *BSI is a bittest of the form
884 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
887 rewrite_bittest (gimple_stmt_iterator
*bsi
)
889 gimple stmt
, use_stmt
, stmt1
, stmt2
;
890 tree lhs
, name
, t
, a
, b
;
893 stmt
= gsi_stmt (*bsi
);
894 lhs
= gimple_assign_lhs (stmt
);
896 /* Verify that the single use of lhs is a comparison against zero. */
897 if (TREE_CODE (lhs
) != SSA_NAME
898 || !single_imm_use (lhs
, &use
, &use_stmt
)
899 || gimple_code (use_stmt
) != GIMPLE_COND
)
901 if (gimple_cond_lhs (use_stmt
) != lhs
902 || (gimple_cond_code (use_stmt
) != NE_EXPR
903 && gimple_cond_code (use_stmt
) != EQ_EXPR
)
904 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
907 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
908 stmt1
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt
));
909 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
912 /* There is a conversion in between possibly inserted by fold. */
913 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1
)))
915 t
= gimple_assign_rhs1 (stmt1
);
916 if (TREE_CODE (t
) != SSA_NAME
917 || !has_single_use (t
))
919 stmt1
= SSA_NAME_DEF_STMT (t
);
920 if (gimple_code (stmt1
) != GIMPLE_ASSIGN
)
924 /* Verify that B is loop invariant but A is not. Verify that with
925 all the stmt walking we are still in the same loop. */
926 if (gimple_assign_rhs_code (stmt1
) != RSHIFT_EXPR
927 || loop_containing_stmt (stmt1
) != loop_containing_stmt (stmt
))
930 a
= gimple_assign_rhs1 (stmt1
);
931 b
= gimple_assign_rhs2 (stmt1
);
933 if (outermost_invariant_loop (b
, loop_containing_stmt (stmt1
)) != NULL
934 && outermost_invariant_loop (a
, loop_containing_stmt (stmt1
)) == NULL
)
936 gimple_stmt_iterator rsi
;
939 t
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (a
),
940 build_int_cst (TREE_TYPE (a
), 1), b
);
941 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
942 stmt1
= gimple_build_assign (name
, t
);
945 t
= fold_build2 (BIT_AND_EXPR
, TREE_TYPE (a
), a
, name
);
946 name
= make_temp_ssa_name (TREE_TYPE (a
), NULL
, "shifttmp");
947 stmt2
= gimple_build_assign (name
, t
);
949 /* Replace the SSA_NAME we compare against zero. Adjust
950 the type of zero accordingly. */
952 gimple_cond_set_rhs (use_stmt
, build_int_cst_type (TREE_TYPE (name
), 0));
954 /* Don't use gsi_replace here, none of the new assignments sets
955 the variable originally set in stmt. Move bsi to stmt1, and
956 then remove the original stmt, so that we get a chance to
957 retain debug info for it. */
959 gsi_insert_before (bsi
, stmt1
, GSI_NEW_STMT
);
960 gsi_insert_before (&rsi
, stmt2
, GSI_SAME_STMT
);
961 gsi_remove (&rsi
, true);
969 /* For each statement determines the outermost loop in that it is invariant,
970 - statements on whose motion it depends and the cost of the computation.
971 - This information is stored to the LIM_DATA structure associated with
973 class invariantness_dom_walker
: public dom_walker
976 invariantness_dom_walker (cdi_direction direction
)
977 : dom_walker (direction
) {}
979 virtual void before_dom_children (basic_block
);
982 /* Determine the outermost loops in that statements in basic block BB are
983 invariant, and record them to the LIM_DATA associated with the statements.
984 Callback for dom_walker. */
987 invariantness_dom_walker::before_dom_children (basic_block bb
)
990 gimple_stmt_iterator bsi
;
992 bool maybe_never
= ALWAYS_EXECUTED_IN (bb
) == NULL
;
993 struct loop
*outermost
= ALWAYS_EXECUTED_IN (bb
);
994 struct lim_aux_data
*lim_data
;
996 if (!loop_outer (bb
->loop_father
))
999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1000 fprintf (dump_file
, "Basic block %d (loop %d -- depth %d):\n\n",
1001 bb
->index
, bb
->loop_father
->num
, loop_depth (bb
->loop_father
));
1003 /* Look at PHI nodes, but only if there is at most two.
1004 ??? We could relax this further by post-processing the inserted
1005 code and transforming adjacent cond-exprs with the same predicate
1006 to control flow again. */
1007 bsi
= gsi_start_phis (bb
);
1008 if (!gsi_end_p (bsi
)
1009 && ((gsi_next (&bsi
), gsi_end_p (bsi
))
1010 || (gsi_next (&bsi
), gsi_end_p (bsi
))))
1011 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1013 stmt
= gsi_stmt (bsi
);
1015 pos
= movement_possibility (stmt
);
1016 if (pos
== MOVE_IMPOSSIBLE
)
1019 lim_data
= init_lim_data (stmt
);
1020 lim_data
->always_executed_in
= outermost
;
1022 if (!determine_max_movement (stmt
, false))
1024 lim_data
->max_loop
= NULL
;
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1031 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1032 loop_depth (lim_data
->max_loop
),
1036 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1037 set_profitable_level (stmt
);
1040 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1042 stmt
= gsi_stmt (bsi
);
1044 pos
= movement_possibility (stmt
);
1045 if (pos
== MOVE_IMPOSSIBLE
)
1047 if (nonpure_call_p (stmt
))
1052 /* Make sure to note always_executed_in for stores to make
1053 store-motion work. */
1054 else if (stmt_makes_single_store (stmt
))
1056 struct lim_aux_data
*lim_data
= init_lim_data (stmt
);
1057 lim_data
->always_executed_in
= outermost
;
1062 if (is_gimple_assign (stmt
)
1063 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1064 == GIMPLE_BINARY_RHS
))
1066 tree op0
= gimple_assign_rhs1 (stmt
);
1067 tree op1
= gimple_assign_rhs2 (stmt
);
1068 struct loop
*ol1
= outermost_invariant_loop (op1
,
1069 loop_containing_stmt (stmt
));
1071 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1072 to be hoisted out of loop, saving expensive divide. */
1073 if (pos
== MOVE_POSSIBLE
1074 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
1075 && flag_unsafe_math_optimizations
1076 && !flag_trapping_math
1078 && outermost_invariant_loop (op0
, ol1
) == NULL
)
1079 stmt
= rewrite_reciprocal (&bsi
);
1081 /* If the shift count is invariant, convert (A >> B) & 1 to
1082 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1083 saving an expensive shift. */
1084 if (pos
== MOVE_POSSIBLE
1085 && gimple_assign_rhs_code (stmt
) == BIT_AND_EXPR
1086 && integer_onep (op1
)
1087 && TREE_CODE (op0
) == SSA_NAME
1088 && has_single_use (op0
))
1089 stmt
= rewrite_bittest (&bsi
);
1092 lim_data
= init_lim_data (stmt
);
1093 lim_data
->always_executed_in
= outermost
;
1095 if (maybe_never
&& pos
== MOVE_PRESERVE_EXECUTION
)
1098 if (!determine_max_movement (stmt
, pos
== MOVE_PRESERVE_EXECUTION
))
1100 lim_data
->max_loop
= NULL
;
1104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1106 print_gimple_stmt (dump_file
, stmt
, 2, 0);
1107 fprintf (dump_file
, " invariant up to level %d, cost %d.\n\n",
1108 loop_depth (lim_data
->max_loop
),
1112 if (lim_data
->cost
>= LIM_EXPENSIVE
)
1113 set_profitable_level (stmt
);
1117 class move_computations_dom_walker
: public dom_walker
1120 move_computations_dom_walker (cdi_direction direction
)
1121 : dom_walker (direction
), todo_ (0) {}
1123 virtual void before_dom_children (basic_block
);
1128 /* Return true if CODE is an operation that when operating on signed
1129 integer types involves undefined behavior on overflow and the
1130 operation can be expressed with unsigned arithmetic. */
1133 arith_code_with_undefined_signed_overflow (tree_code code
)
1141 case POINTER_PLUS_EXPR
:
1148 /* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
1149 operation that can be transformed to unsigned arithmetic by converting
1150 its operand, carrying out the operation in the corresponding unsigned
1151 type and converting the result back to the original type.
1153 Returns a sequence of statements that replace STMT and also contain
1154 a modified form of STMT itself. */
1157 rewrite_to_defined_overflow (gimple stmt
)
1159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1161 fprintf (dump_file
, "rewriting stmt with undefined signed "
1163 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1166 tree lhs
= gimple_assign_lhs (stmt
);
1167 tree type
= unsigned_type_for (TREE_TYPE (lhs
));
1168 gimple_seq stmts
= NULL
;
1169 for (unsigned i
= 1; i
< gimple_num_ops (stmt
); ++i
)
1171 gimple_seq stmts2
= NULL
;
1172 gimple_set_op (stmt
, i
,
1173 force_gimple_operand (fold_convert (type
,
1174 gimple_op (stmt
, i
)),
1175 &stmts2
, true, NULL_TREE
));
1176 gimple_seq_add_seq (&stmts
, stmts2
);
1178 gimple_assign_set_lhs (stmt
, make_ssa_name (type
, stmt
));
1179 if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1180 gimple_assign_set_rhs_code (stmt
, PLUS_EXPR
);
1181 gimple_seq_add_stmt (&stmts
, stmt
);
1182 gimple cvt
= gimple_build_assign_with_ops
1183 (NOP_EXPR
, lhs
, gimple_assign_lhs (stmt
), NULL_TREE
);
1184 gimple_seq_add_stmt (&stmts
, cvt
);
1189 /* Hoist the statements in basic block BB out of the loops prescribed by
1190 data stored in LIM_DATA structures associated with each statement. Callback
1191 for walk_dominator_tree. */
1194 move_computations_dom_walker::before_dom_children (basic_block bb
)
1197 gimple_stmt_iterator bsi
;
1200 struct lim_aux_data
*lim_data
;
1202 if (!loop_outer (bb
->loop_father
))
1205 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); )
1208 stmt
= gsi_stmt (bsi
);
1210 lim_data
= get_lim_data (stmt
);
1211 if (lim_data
== NULL
)
1217 cost
= lim_data
->cost
;
1218 level
= lim_data
->tgt_loop
;
1219 clear_lim_data (stmt
);
1227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1229 fprintf (dump_file
, "Moving PHI node\n");
1230 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1231 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1235 if (gimple_phi_num_args (stmt
) == 1)
1237 tree arg
= PHI_ARG_DEF (stmt
, 0);
1238 new_stmt
= gimple_build_assign_with_ops (TREE_CODE (arg
),
1239 gimple_phi_result (stmt
),
1241 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1245 basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1246 gimple cond
= gsi_stmt (gsi_last_bb (dom
));
1247 tree arg0
= NULL_TREE
, arg1
= NULL_TREE
, t
;
1248 /* Get the PHI arguments corresponding to the true and false
1250 extract_true_false_args_from_phi (dom
, stmt
, &arg0
, &arg1
);
1251 gcc_assert (arg0
&& arg1
);
1252 t
= build2 (gimple_cond_code (cond
), boolean_type_node
,
1253 gimple_cond_lhs (cond
), gimple_cond_rhs (cond
));
1254 new_stmt
= gimple_build_assign_with_ops (COND_EXPR
,
1255 gimple_phi_result (stmt
),
1257 SSA_NAME_DEF_STMT (gimple_phi_result (stmt
)) = new_stmt
;
1258 todo_
|= TODO_cleanup_cfg
;
1260 gsi_insert_on_edge (loop_preheader_edge (level
), new_stmt
);
1261 remove_phi_node (&bsi
, false);
1264 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); )
1268 stmt
= gsi_stmt (bsi
);
1270 lim_data
= get_lim_data (stmt
);
1271 if (lim_data
== NULL
)
1277 cost
= lim_data
->cost
;
1278 level
= lim_data
->tgt_loop
;
1279 clear_lim_data (stmt
);
1287 /* We do not really want to move conditionals out of the loop; we just
1288 placed it here to force its operands to be moved if necessary. */
1289 if (gimple_code (stmt
) == GIMPLE_COND
)
1292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1294 fprintf (dump_file
, "Moving statement\n");
1295 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1296 fprintf (dump_file
, "(cost %u) out of loop %d.\n\n",
1300 e
= loop_preheader_edge (level
);
1301 gcc_assert (!gimple_vdef (stmt
));
1302 if (gimple_vuse (stmt
))
1304 /* The new VUSE is the one from the virtual PHI in the loop
1305 header or the one already present. */
1306 gimple_stmt_iterator gsi2
;
1307 for (gsi2
= gsi_start_phis (e
->dest
);
1308 !gsi_end_p (gsi2
); gsi_next (&gsi2
))
1310 gimple phi
= gsi_stmt (gsi2
);
1311 if (virtual_operand_p (gimple_phi_result (phi
)))
1313 gimple_set_vuse (stmt
, PHI_ARG_DEF_FROM_EDGE (phi
, e
));
1318 gsi_remove (&bsi
, false);
1319 /* In case this is a stmt that is not unconditionally executed
1320 when the target loop header is executed and the stmt may
1321 invoke undefined integer or pointer overflow rewrite it to
1322 unsigned arithmetic. */
1323 if (is_gimple_assign (stmt
)
1324 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
)))
1325 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt
)))
1326 && arith_code_with_undefined_signed_overflow
1327 (gimple_assign_rhs_code (stmt
))
1328 && (!ALWAYS_EXECUTED_IN (bb
)
1329 || !(ALWAYS_EXECUTED_IN (bb
) == level
1330 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb
), level
))))
1331 gsi_insert_seq_on_edge (e
, rewrite_to_defined_overflow (stmt
));
1333 gsi_insert_on_edge (e
, stmt
);
1337 /* Hoist the statements out of the loops prescribed by data stored in
1338 LIM_DATA structures associated with each statement.*/
1341 move_computations (void)
1343 move_computations_dom_walker
walker (CDI_DOMINATORS
);
1344 walker
.walk (cfun
->cfg
->x_entry_block_ptr
);
1346 gsi_commit_edge_inserts ();
1347 if (need_ssa_update_p (cfun
))
1348 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1350 return walker
.todo_
;
1353 /* Checks whether the statement defining variable *INDEX can be hoisted
1354 out of the loop passed in DATA. Callback for for_each_index. */
1357 may_move_till (tree ref
, tree
*index
, void *data
)
1359 struct loop
*loop
= (struct loop
*) data
, *max_loop
;
1361 /* If REF is an array reference, check also that the step and the lower
1362 bound is invariant in LOOP. */
1363 if (TREE_CODE (ref
) == ARRAY_REF
)
1365 tree step
= TREE_OPERAND (ref
, 3);
1366 tree lbound
= TREE_OPERAND (ref
, 2);
1368 max_loop
= outermost_invariant_loop (step
, loop
);
1372 max_loop
= outermost_invariant_loop (lbound
, loop
);
1377 max_loop
= outermost_invariant_loop (*index
, loop
);
1384 /* If OP is SSA NAME, force the statement that defines it to be
1385 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1388 force_move_till_op (tree op
, struct loop
*orig_loop
, struct loop
*loop
)
1393 || is_gimple_min_invariant (op
))
1396 gcc_assert (TREE_CODE (op
) == SSA_NAME
);
1398 stmt
= SSA_NAME_DEF_STMT (op
);
1399 if (gimple_nop_p (stmt
))
1402 set_level (stmt
, orig_loop
, loop
);
1405 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1406 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1412 struct loop
*orig_loop
;
1416 force_move_till (tree ref
, tree
*index
, void *data
)
1418 struct fmt_data
*fmt_data
= (struct fmt_data
*) data
;
1420 if (TREE_CODE (ref
) == ARRAY_REF
)
1422 tree step
= TREE_OPERAND (ref
, 3);
1423 tree lbound
= TREE_OPERAND (ref
, 2);
1425 force_move_till_op (step
, fmt_data
->orig_loop
, fmt_data
->loop
);
1426 force_move_till_op (lbound
, fmt_data
->orig_loop
, fmt_data
->loop
);
1429 force_move_till_op (*index
, fmt_data
->orig_loop
, fmt_data
->loop
);
1434 /* A function to free the mem_ref object OBJ. */
1437 memref_free (struct mem_ref
*mem
)
1440 vec
<mem_ref_loc
> *accs
;
1442 FOR_EACH_VEC_ELT (mem
->accesses_in_loop
, i
, accs
)
1444 mem
->accesses_in_loop
.release ();
1449 /* Allocates and returns a memory reference description for MEM whose hash
1450 value is HASH and id is ID. */
1453 mem_ref_alloc (tree mem
, unsigned hash
, unsigned id
)
1455 mem_ref_p ref
= XNEW (struct mem_ref
);
1456 ao_ref_init (&ref
->mem
, mem
);
1459 bitmap_initialize (&ref
->stored
, &lim_bitmap_obstack
);
1460 bitmap_initialize (&ref
->indep_loop
, &lim_bitmap_obstack
);
1461 bitmap_initialize (&ref
->dep_loop
, &lim_bitmap_obstack
);
1462 ref
->accesses_in_loop
.create (0);
1467 /* Records memory reference location *LOC in LOOP to the memory reference
1468 description REF. The reference occurs in statement STMT. */
1471 record_mem_ref_loc (mem_ref_p ref
, struct loop
*loop
, gimple stmt
, tree
*loc
)
1475 if (ref
->accesses_in_loop
.length ()
1476 <= (unsigned) loop
->num
)
1477 ref
->accesses_in_loop
.safe_grow_cleared (loop
->num
+ 1);
1481 ref
->accesses_in_loop
[loop
->num
].safe_push (aref
);
1484 /* Marks reference REF as stored in LOOP. */
1487 mark_ref_stored (mem_ref_p ref
, struct loop
*loop
)
1489 while (loop
!= current_loops
->tree_root
1490 && bitmap_set_bit (&ref
->stored
, loop
->num
))
1491 loop
= loop_outer (loop
);
1494 /* Gathers memory references in statement STMT in LOOP, storing the
1495 information about them in the memory_accesses structure. Marks
1496 the vops accessed through unrecognized statements there as
1500 gather_mem_refs_stmt (struct loop
*loop
, gimple stmt
)
1509 if (!gimple_vuse (stmt
))
1512 mem
= simple_mem_ref_in_stmt (stmt
, &is_stored
);
1515 /* We use the shared mem_ref for all unanalyzable refs. */
1516 id
= UNANALYZABLE_MEM_ID
;
1517 ref
= memory_accesses
.refs_list
[id
];
1518 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1520 fprintf (dump_file
, "Unanalyzed memory reference %u: ", id
);
1521 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1523 is_stored
= gimple_vdef (stmt
);
1527 hash
= iterative_hash_expr (*mem
, 0);
1528 slot
= memory_accesses
.refs
.find_slot_with_hash (*mem
, hash
, INSERT
);
1531 ref
= (mem_ref_p
) *slot
;
1536 id
= memory_accesses
.refs_list
.length ();
1537 ref
= mem_ref_alloc (*mem
, hash
, id
);
1538 memory_accesses
.refs_list
.safe_push (ref
);
1541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1543 fprintf (dump_file
, "Memory reference %u: ", id
);
1544 print_generic_expr (dump_file
, ref
->mem
.ref
, TDF_SLIM
);
1545 fprintf (dump_file
, "\n");
1549 record_mem_ref_loc (ref
, loop
, stmt
, mem
);
1551 bitmap_set_bit (&memory_accesses
.refs_in_loop
[loop
->num
], ref
->id
);
1554 bitmap_set_bit (&memory_accesses
.refs_stored_in_loop
[loop
->num
], ref
->id
);
1555 mark_ref_stored (ref
, loop
);
1560 static unsigned *bb_loop_postorder
;
1562 /* qsort sort function to sort blocks after their loop fathers postorder. */
1565 sort_bbs_in_loop_postorder_cmp (const void *bb1_
, const void *bb2_
)
1567 basic_block bb1
= *(basic_block
*)const_cast<void *>(bb1_
);
1568 basic_block bb2
= *(basic_block
*)const_cast<void *>(bb2_
);
1569 struct loop
*loop1
= bb1
->loop_father
;
1570 struct loop
*loop2
= bb2
->loop_father
;
1571 if (loop1
->num
== loop2
->num
)
1573 return bb_loop_postorder
[loop1
->num
] < bb_loop_postorder
[loop2
->num
] ? -1 : 1;
1576 /* Gathers memory references in loops. */
1579 analyze_memory_references (void)
1581 gimple_stmt_iterator bsi
;
1582 basic_block bb
, *bbs
;
1583 struct loop
*loop
, *outer
;
1587 /* Initialize bb_loop_postorder with a mapping from loop->num to
1588 its postorder index. */
1590 bb_loop_postorder
= XNEWVEC (unsigned, number_of_loops (cfun
));
1591 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1592 bb_loop_postorder
[loop
->num
] = i
++;
1593 /* Collect all basic-blocks in loops and sort them after their
1596 bbs
= XNEWVEC (basic_block
, n_basic_blocks
- NUM_FIXED_BLOCKS
);
1598 if (bb
->loop_father
!= current_loops
->tree_root
)
1601 qsort (bbs
, n
, sizeof (basic_block
), sort_bbs_in_loop_postorder_cmp
);
1602 free (bb_loop_postorder
);
1604 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1605 That results in better locality for all the bitmaps. */
1606 for (i
= 0; i
< n
; ++i
)
1608 basic_block bb
= bbs
[i
];
1609 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1610 gather_mem_refs_stmt (bb
->loop_father
, gsi_stmt (bsi
));
1615 /* Propagate the information about accessed memory references up
1616 the loop hierarchy. */
1617 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1619 /* Finalize the overall touched references (including subloops). */
1620 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[loop
->num
],
1621 &memory_accesses
.refs_stored_in_loop
[loop
->num
]);
1623 /* Propagate the information about accessed memory references up
1624 the loop hierarchy. */
1625 outer
= loop_outer (loop
);
1626 if (outer
== current_loops
->tree_root
)
1629 bitmap_ior_into (&memory_accesses
.all_refs_stored_in_loop
[outer
->num
],
1630 &memory_accesses
.all_refs_stored_in_loop
[loop
->num
]);
1634 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1635 tree_to_aff_combination_expand. */
1638 mem_refs_may_alias_p (mem_ref_p mem1
, mem_ref_p mem2
,
1639 struct pointer_map_t
**ttae_cache
)
1641 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1642 object and their offset differ in such a way that the locations cannot
1643 overlap, then they cannot alias. */
1644 double_int size1
, size2
;
1645 aff_tree off1
, off2
;
1647 /* Perform basic offset and type-based disambiguation. */
1648 if (!refs_may_alias_p_1 (&mem1
->mem
, &mem2
->mem
, true))
1651 /* The expansion of addresses may be a bit expensive, thus we only do
1652 the check at -O2 and higher optimization levels. */
1656 get_inner_reference_aff (mem1
->mem
.ref
, &off1
, &size1
);
1657 get_inner_reference_aff (mem2
->mem
.ref
, &off2
, &size2
);
1658 aff_combination_expand (&off1
, ttae_cache
);
1659 aff_combination_expand (&off2
, ttae_cache
);
1660 aff_combination_scale (&off1
, double_int_minus_one
);
1661 aff_combination_add (&off2
, &off1
);
1663 if (aff_comb_cannot_overlap_p (&off2
, size1
, size2
))
1669 /* Iterates over all locations of REF in LOOP and its subloops calling
1670 fn.operator() with the location as argument. When that operator
1671 returns true the iteration is stopped and true is returned.
1672 Otherwise false is returned. */
1674 template <typename FN
>
1676 for_all_locs_in_loop (struct loop
*loop
, mem_ref_p ref
, FN fn
)
1680 struct loop
*subloop
;
1682 if (ref
->accesses_in_loop
.length () > (unsigned) loop
->num
)
1683 FOR_EACH_VEC_ELT (ref
->accesses_in_loop
[loop
->num
], i
, loc
)
1687 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
1688 if (for_all_locs_in_loop (subloop
, ref
, fn
))
1694 /* Rewrites location LOC by TMP_VAR. */
1696 struct rewrite_mem_ref_loc
1698 rewrite_mem_ref_loc (tree tmp_var_
) : tmp_var (tmp_var_
) {}
1699 bool operator () (mem_ref_loc_p loc
);
1704 rewrite_mem_ref_loc::operator () (mem_ref_loc_p loc
)
1706 *loc
->ref
= tmp_var
;
1707 update_stmt (loc
->stmt
);
1711 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1714 rewrite_mem_refs (struct loop
*loop
, mem_ref_p ref
, tree tmp_var
)
1716 for_all_locs_in_loop (loop
, ref
, rewrite_mem_ref_loc (tmp_var
));
1719 /* Stores the first reference location in LOCP. */
1721 struct first_mem_ref_loc_1
1723 first_mem_ref_loc_1 (mem_ref_loc_p
*locp_
) : locp (locp_
) {}
1724 bool operator () (mem_ref_loc_p loc
);
1725 mem_ref_loc_p
*locp
;
1729 first_mem_ref_loc_1::operator () (mem_ref_loc_p loc
)
1735 /* Returns the first reference location to REF in LOOP. */
1737 static mem_ref_loc_p
1738 first_mem_ref_loc (struct loop
*loop
, mem_ref_p ref
)
1740 mem_ref_loc_p locp
= NULL
;
1741 for_all_locs_in_loop (loop
, ref
, first_mem_ref_loc_1 (&locp
));
1745 struct prev_flag_edges
{
1746 /* Edge to insert new flag comparison code. */
1747 edge append_cond_position
;
1749 /* Edge for fall through from previous flag comparison. */
1750 edge last_cond_fallthru
;
1753 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1756 The store is only done if MEM has changed. We do this so no
1757 changes to MEM occur on code paths that did not originally store
1760 The common case for execute_sm will transform:
1780 This function will generate:
1799 execute_sm_if_changed (edge ex
, tree mem
, tree tmp_var
, tree flag
)
1801 basic_block new_bb
, then_bb
, old_dest
;
1802 bool loop_has_only_one_exit
;
1803 edge then_old_edge
, orig_ex
= ex
;
1804 gimple_stmt_iterator gsi
;
1806 struct prev_flag_edges
*prev_edges
= (struct prev_flag_edges
*) ex
->aux
;
1808 /* ?? Insert store after previous store if applicable. See note
1811 ex
= prev_edges
->append_cond_position
;
1813 loop_has_only_one_exit
= single_pred_p (ex
->dest
);
1815 if (loop_has_only_one_exit
)
1816 ex
= split_block_after_labels (ex
->dest
);
1818 old_dest
= ex
->dest
;
1819 new_bb
= split_edge (ex
);
1820 then_bb
= create_empty_bb (new_bb
);
1821 if (current_loops
&& new_bb
->loop_father
)
1822 add_bb_to_loop (then_bb
, new_bb
->loop_father
);
1824 gsi
= gsi_start_bb (new_bb
);
1825 stmt
= gimple_build_cond (NE_EXPR
, flag
, boolean_false_node
,
1826 NULL_TREE
, NULL_TREE
);
1827 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1829 gsi
= gsi_start_bb (then_bb
);
1830 /* Insert actual store. */
1831 stmt
= gimple_build_assign (unshare_expr (mem
), tmp_var
);
1832 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1834 make_edge (new_bb
, then_bb
, EDGE_TRUE_VALUE
);
1835 make_edge (new_bb
, old_dest
, EDGE_FALSE_VALUE
);
1836 then_old_edge
= make_edge (then_bb
, old_dest
, EDGE_FALLTHRU
);
1838 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, new_bb
);
1842 basic_block prevbb
= prev_edges
->last_cond_fallthru
->src
;
1843 redirect_edge_succ (prev_edges
->last_cond_fallthru
, new_bb
);
1844 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, prevbb
);
1845 set_immediate_dominator (CDI_DOMINATORS
, old_dest
,
1846 recompute_dominator (CDI_DOMINATORS
, old_dest
));
1849 /* ?? Because stores may alias, they must happen in the exact
1850 sequence they originally happened. Save the position right after
1851 the (_lsm) store we just created so we can continue appending after
1852 it and maintain the original order. */
1854 struct prev_flag_edges
*p
;
1857 orig_ex
->aux
= NULL
;
1858 alloc_aux_for_edge (orig_ex
, sizeof (struct prev_flag_edges
));
1859 p
= (struct prev_flag_edges
*) orig_ex
->aux
;
1860 p
->append_cond_position
= then_old_edge
;
1861 p
->last_cond_fallthru
= find_edge (new_bb
, old_dest
);
1862 orig_ex
->aux
= (void *) p
;
1865 if (!loop_has_only_one_exit
)
1866 for (gsi
= gsi_start_phis (old_dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1868 gimple phi
= gsi_stmt (gsi
);
1871 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1872 if (gimple_phi_arg_edge (phi
, i
)->src
== new_bb
)
1874 tree arg
= gimple_phi_arg_def (phi
, i
);
1875 add_phi_arg (phi
, arg
, then_old_edge
, UNKNOWN_LOCATION
);
1879 /* Remove the original fall through edge. This was the
1880 single_succ_edge (new_bb). */
1881 EDGE_SUCC (new_bb
, 0)->flags
&= ~EDGE_FALLTHRU
;
1884 /* When REF is set on the location, set flag indicating the store. */
1886 struct sm_set_flag_if_changed
1888 sm_set_flag_if_changed (tree flag_
) : flag (flag_
) {}
1889 bool operator () (mem_ref_loc_p loc
);
1894 sm_set_flag_if_changed::operator () (mem_ref_loc_p loc
)
1896 /* Only set the flag for writes. */
1897 if (is_gimple_assign (loc
->stmt
)
1898 && gimple_assign_lhs_ptr (loc
->stmt
) == loc
->ref
)
1900 gimple_stmt_iterator gsi
= gsi_for_stmt (loc
->stmt
);
1901 gimple stmt
= gimple_build_assign (flag
, boolean_true_node
);
1902 gsi_insert_after (&gsi
, stmt
, GSI_CONTINUE_LINKING
);
1907 /* Helper function for execute_sm. On every location where REF is
1908 set, set an appropriate flag indicating the store. */
1911 execute_sm_if_changed_flag_set (struct loop
*loop
, mem_ref_p ref
)
1914 char *str
= get_lsm_tmp_name (ref
->mem
.ref
, ~0, "_flag");
1915 flag
= create_tmp_reg (boolean_type_node
, str
);
1916 for_all_locs_in_loop (loop
, ref
, sm_set_flag_if_changed (flag
));
1920 /* Executes store motion of memory reference REF from LOOP.
1921 Exits from the LOOP are stored in EXITS. The initialization of the
1922 temporary variable is put to the preheader of the loop, and assignments
1923 to the reference from the temporary variable are emitted to exits. */
1926 execute_sm (struct loop
*loop
, vec
<edge
> exits
, mem_ref_p ref
)
1928 tree tmp_var
, store_flag
;
1931 struct fmt_data fmt_data
;
1933 struct lim_aux_data
*lim_data
;
1934 bool multi_threaded_model_p
= false;
1935 gimple_stmt_iterator gsi
;
1937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1939 fprintf (dump_file
, "Executing store motion of ");
1940 print_generic_expr (dump_file
, ref
->mem
.ref
, 0);
1941 fprintf (dump_file
, " from loop %d\n", loop
->num
);
1944 tmp_var
= create_tmp_reg (TREE_TYPE (ref
->mem
.ref
),
1945 get_lsm_tmp_name (ref
->mem
.ref
, ~0));
1947 fmt_data
.loop
= loop
;
1948 fmt_data
.orig_loop
= loop
;
1949 for_each_index (&ref
->mem
.ref
, force_move_till
, &fmt_data
);
1951 if (bb_in_transaction (loop_preheader_edge (loop
)->src
)
1952 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
))
1953 multi_threaded_model_p
= true;
1955 if (multi_threaded_model_p
)
1956 store_flag
= execute_sm_if_changed_flag_set (loop
, ref
);
1958 rewrite_mem_refs (loop
, ref
, tmp_var
);
1960 /* Emit the load code on a random exit edge or into the latch if
1961 the loop does not exit, so that we are sure it will be processed
1962 by move_computations after all dependencies. */
1963 gsi
= gsi_for_stmt (first_mem_ref_loc (loop
, ref
)->stmt
);
1965 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
1966 load altogether, since the store is predicated by a flag. We
1967 could, do the load only if it was originally in the loop. */
1968 load
= gimple_build_assign (tmp_var
, unshare_expr (ref
->mem
.ref
));
1969 lim_data
= init_lim_data (load
);
1970 lim_data
->max_loop
= loop
;
1971 lim_data
->tgt_loop
= loop
;
1972 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1974 if (multi_threaded_model_p
)
1976 load
= gimple_build_assign (store_flag
, boolean_false_node
);
1977 lim_data
= init_lim_data (load
);
1978 lim_data
->max_loop
= loop
;
1979 lim_data
->tgt_loop
= loop
;
1980 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1983 /* Sink the store to every exit from the loop. */
1984 FOR_EACH_VEC_ELT (exits
, i
, ex
)
1985 if (!multi_threaded_model_p
)
1988 store
= gimple_build_assign (unshare_expr (ref
->mem
.ref
), tmp_var
);
1989 gsi_insert_on_edge (ex
, store
);
1992 execute_sm_if_changed (ex
, ref
->mem
.ref
, tmp_var
, store_flag
);
1995 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
1996 edges of the LOOP. */
1999 hoist_memory_references (struct loop
*loop
, bitmap mem_refs
,
2006 EXECUTE_IF_SET_IN_BITMAP (mem_refs
, 0, i
, bi
)
2008 ref
= memory_accesses
.refs_list
[i
];
2009 execute_sm (loop
, exits
, ref
);
2013 struct ref_always_accessed
2015 ref_always_accessed (struct loop
*loop_
, tree base_
, bool stored_p_
)
2016 : loop (loop_
), base (base_
), stored_p (stored_p_
) {}
2017 bool operator () (mem_ref_loc_p loc
);
2024 ref_always_accessed::operator () (mem_ref_loc_p loc
)
2026 struct loop
*must_exec
;
2028 if (!get_lim_data (loc
->stmt
))
2031 /* If we require an always executed store make sure the statement
2032 stores to the reference. */
2036 if (!gimple_get_lhs (loc
->stmt
))
2038 lhs
= get_base_address (gimple_get_lhs (loc
->stmt
));
2041 if (INDIRECT_REF_P (lhs
)
2042 || TREE_CODE (lhs
) == MEM_REF
)
2043 lhs
= TREE_OPERAND (lhs
, 0);
2048 must_exec
= get_lim_data (loc
->stmt
)->always_executed_in
;
2052 if (must_exec
== loop
2053 || flow_loop_nested_p (must_exec
, loop
))
2059 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2060 make sure REF is always stored to in LOOP. */
2063 ref_always_accessed_p (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2065 tree base
= ao_ref_base (&ref
->mem
);
2066 if (TREE_CODE (base
) == MEM_REF
)
2067 base
= TREE_OPERAND (base
, 0);
2069 return for_all_locs_in_loop (loop
, ref
,
2070 ref_always_accessed (loop
, base
, stored_p
));
2073 /* Returns true if REF1 and REF2 are independent. */
2076 refs_independent_p (mem_ref_p ref1
, mem_ref_p ref2
)
2081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2082 fprintf (dump_file
, "Querying dependency of refs %u and %u: ",
2083 ref1
->id
, ref2
->id
);
2085 if (mem_refs_may_alias_p (ref1
, ref2
, &memory_accesses
.ttae_cache
))
2087 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2088 fprintf (dump_file
, "dependent.\n");
2093 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2094 fprintf (dump_file
, "independent.\n");
2099 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2100 and its super-loops. */
2103 record_dep_loop (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2105 /* We can propagate dependent-in-loop bits up the loop
2106 hierarchy to all outer loops. */
2107 while (loop
!= current_loops
->tree_root
2108 && bitmap_set_bit (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2109 loop
= loop_outer (loop
);
2112 /* Returns true if REF is independent on all other memory references in
2116 ref_indep_loop_p_1 (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2118 bitmap refs_to_check
;
2124 refs_to_check
= &memory_accesses
.refs_in_loop
[loop
->num
];
2126 refs_to_check
= &memory_accesses
.refs_stored_in_loop
[loop
->num
];
2128 if (bitmap_bit_p (refs_to_check
, UNANALYZABLE_MEM_ID
))
2131 EXECUTE_IF_SET_IN_BITMAP (refs_to_check
, 0, i
, bi
)
2133 aref
= memory_accesses
.refs_list
[i
];
2134 if (!refs_independent_p (ref
, aref
))
2141 /* Returns true if REF is independent on all other memory references in
2142 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2145 ref_indep_loop_p_2 (struct loop
*loop
, mem_ref_p ref
, bool stored_p
)
2147 stored_p
|= bitmap_bit_p (&ref
->stored
, loop
->num
);
2149 if (bitmap_bit_p (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2151 if (bitmap_bit_p (&ref
->dep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
)))
2154 struct loop
*inner
= loop
->inner
;
2157 if (!ref_indep_loop_p_2 (inner
, ref
, stored_p
))
2159 inner
= inner
->next
;
2162 bool indep_p
= ref_indep_loop_p_1 (loop
, ref
, stored_p
);
2164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2165 fprintf (dump_file
, "Querying dependencies of ref %u in loop %d: %s\n",
2166 ref
->id
, loop
->num
, indep_p
? "independent" : "dependent");
2168 /* Record the computed result in the cache. */
2171 if (bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, stored_p
))
2174 /* If it's independend against all refs then it's independent
2175 against stores, too. */
2176 bitmap_set_bit (&ref
->indep_loop
, LOOP_DEP_BIT (loop
->num
, false));
2181 record_dep_loop (loop
, ref
, stored_p
);
2184 /* If it's dependent against stores it's dependent against
2186 record_dep_loop (loop
, ref
, true);
2193 /* Returns true if REF is independent on all other memory references in
2197 ref_indep_loop_p (struct loop
*loop
, mem_ref_p ref
)
2199 gcc_checking_assert (MEM_ANALYZABLE (ref
));
2201 return ref_indep_loop_p_2 (loop
, ref
, false);
2204 /* Returns true if we can perform store motion of REF from LOOP. */
2207 can_sm_ref_p (struct loop
*loop
, mem_ref_p ref
)
2211 /* Can't hoist unanalyzable refs. */
2212 if (!MEM_ANALYZABLE (ref
))
2215 /* It should be movable. */
2216 if (!is_gimple_reg_type (TREE_TYPE (ref
->mem
.ref
))
2217 || TREE_THIS_VOLATILE (ref
->mem
.ref
)
2218 || !for_each_index (&ref
->mem
.ref
, may_move_till
, loop
))
2221 /* If it can throw fail, we do not properly update EH info. */
2222 if (tree_could_throw_p (ref
->mem
.ref
))
2225 /* If it can trap, it must be always executed in LOOP.
2226 Readonly memory locations may trap when storing to them, but
2227 tree_could_trap_p is a predicate for rvalues, so check that
2229 base
= get_base_address (ref
->mem
.ref
);
2230 if ((tree_could_trap_p (ref
->mem
.ref
)
2231 || (DECL_P (base
) && TREE_READONLY (base
)))
2232 && !ref_always_accessed_p (loop
, ref
, true))
2235 /* And it must be independent on all other memory references
2237 if (!ref_indep_loop_p (loop
, ref
))
2243 /* Marks the references in LOOP for that store motion should be performed
2244 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2245 motion was performed in one of the outer loops. */
2248 find_refs_for_sm (struct loop
*loop
, bitmap sm_executed
, bitmap refs_to_sm
)
2250 bitmap refs
= &memory_accesses
.all_refs_stored_in_loop
[loop
->num
];
2255 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs
, sm_executed
, 0, i
, bi
)
2257 ref
= memory_accesses
.refs_list
[i
];
2258 if (can_sm_ref_p (loop
, ref
))
2259 bitmap_set_bit (refs_to_sm
, i
);
2263 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2264 for a store motion optimization (i.e. whether we can insert statement
2268 loop_suitable_for_sm (struct loop
*loop ATTRIBUTE_UNUSED
,
2274 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2275 if (ex
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2281 /* Try to perform store motion for all memory references modified inside
2282 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2283 store motion was executed in one of the outer loops. */
2286 store_motion_loop (struct loop
*loop
, bitmap sm_executed
)
2288 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2289 struct loop
*subloop
;
2290 bitmap sm_in_loop
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2292 if (loop_suitable_for_sm (loop
, exits
))
2294 find_refs_for_sm (loop
, sm_executed
, sm_in_loop
);
2295 hoist_memory_references (loop
, sm_in_loop
, exits
);
2299 bitmap_ior_into (sm_executed
, sm_in_loop
);
2300 for (subloop
= loop
->inner
; subloop
!= NULL
; subloop
= subloop
->next
)
2301 store_motion_loop (subloop
, sm_executed
);
2302 bitmap_and_compl_into (sm_executed
, sm_in_loop
);
2303 BITMAP_FREE (sm_in_loop
);
2306 /* Try to perform store motion for all memory references modified inside
2313 bitmap sm_executed
= BITMAP_ALLOC (&lim_bitmap_obstack
);
2315 for (loop
= current_loops
->tree_root
->inner
; loop
!= NULL
; loop
= loop
->next
)
2316 store_motion_loop (loop
, sm_executed
);
2318 BITMAP_FREE (sm_executed
);
2319 gsi_commit_edge_inserts ();
2322 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2323 for each such basic block bb records the outermost loop for that execution
2324 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2325 blocks that contain a nonpure call. */
2328 fill_always_executed_in_1 (struct loop
*loop
, sbitmap contains_call
)
2330 basic_block bb
= NULL
, *bbs
, last
= NULL
;
2333 struct loop
*inn_loop
= loop
;
2335 if (ALWAYS_EXECUTED_IN (loop
->header
) == NULL
)
2337 bbs
= get_loop_body_in_dom_order (loop
);
2339 for (i
= 0; i
< loop
->num_nodes
; i
++)
2344 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2347 if (bitmap_bit_p (contains_call
, bb
->index
))
2350 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2351 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
2356 /* A loop might be infinite (TODO use simple loop analysis
2357 to disprove this if possible). */
2358 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
2361 if (!flow_bb_inside_loop_p (inn_loop
, bb
))
2364 if (bb
->loop_father
->header
== bb
)
2366 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2369 /* In a loop that is always entered we may proceed anyway.
2370 But record that we entered it and stop once we leave it. */
2371 inn_loop
= bb
->loop_father
;
2377 SET_ALWAYS_EXECUTED_IN (last
, loop
);
2378 if (last
== loop
->header
)
2380 last
= get_immediate_dominator (CDI_DOMINATORS
, last
);
2386 for (loop
= loop
->inner
; loop
; loop
= loop
->next
)
2387 fill_always_executed_in_1 (loop
, contains_call
);
2390 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2391 for each such basic block bb records the outermost loop for that execution
2392 of its header implies execution of bb. */
2395 fill_always_executed_in (void)
2397 sbitmap contains_call
= sbitmap_alloc (last_basic_block
);
2401 bitmap_clear (contains_call
);
2404 gimple_stmt_iterator gsi
;
2405 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2407 if (nonpure_call_p (gsi_stmt (gsi
)))
2411 if (!gsi_end_p (gsi
))
2412 bitmap_set_bit (contains_call
, bb
->index
);
2415 for (loop
= current_loops
->tree_root
->inner
; loop
; loop
= loop
->next
)
2416 fill_always_executed_in_1 (loop
, contains_call
);
2418 sbitmap_free (contains_call
);
2422 /* Compute the global information needed by the loop invariant motion pass. */
2425 tree_ssa_lim_initialize (void)
2429 bitmap_obstack_initialize (&lim_bitmap_obstack
);
2430 lim_aux_data_map
= pointer_map_create ();
2433 compute_transaction_bits ();
2435 alloc_aux_for_edges (0);
2437 memory_accesses
.refs
.create (100);
2438 memory_accesses
.refs_list
.create (100);
2439 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2440 memory_accesses
.refs_list
.quick_push
2441 (mem_ref_alloc (error_mark_node
, 0, UNANALYZABLE_MEM_ID
));
2443 memory_accesses
.refs_in_loop
.create (number_of_loops (cfun
));
2444 memory_accesses
.refs_in_loop
.quick_grow (number_of_loops (cfun
));
2445 memory_accesses
.refs_stored_in_loop
.create (number_of_loops (cfun
));
2446 memory_accesses
.refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2447 memory_accesses
.all_refs_stored_in_loop
.create (number_of_loops (cfun
));
2448 memory_accesses
.all_refs_stored_in_loop
.quick_grow (number_of_loops (cfun
));
2450 for (i
= 0; i
< number_of_loops (cfun
); i
++)
2452 bitmap_initialize (&memory_accesses
.refs_in_loop
[i
],
2453 &lim_bitmap_obstack
);
2454 bitmap_initialize (&memory_accesses
.refs_stored_in_loop
[i
],
2455 &lim_bitmap_obstack
);
2456 bitmap_initialize (&memory_accesses
.all_refs_stored_in_loop
[i
],
2457 &lim_bitmap_obstack
);
2460 memory_accesses
.ttae_cache
= NULL
;
2463 /* Cleans up after the invariant motion pass. */
2466 tree_ssa_lim_finalize (void)
2472 free_aux_for_edges ();
2475 SET_ALWAYS_EXECUTED_IN (bb
, NULL
);
2477 bitmap_obstack_release (&lim_bitmap_obstack
);
2478 pointer_map_destroy (lim_aux_data_map
);
2480 memory_accesses
.refs
.dispose ();
2482 FOR_EACH_VEC_ELT (memory_accesses
.refs_list
, i
, ref
)
2484 memory_accesses
.refs_list
.release ();
2486 memory_accesses
.refs_in_loop
.release ();
2487 memory_accesses
.refs_stored_in_loop
.release ();
2488 memory_accesses
.all_refs_stored_in_loop
.release ();
2490 if (memory_accesses
.ttae_cache
)
2491 free_affine_expand_cache (&memory_accesses
.ttae_cache
);
2494 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2495 i.e. those that are likely to be win regardless of the register pressure. */
2502 tree_ssa_lim_initialize ();
2504 /* Gathers information about memory accesses in the loops. */
2505 analyze_memory_references ();
2507 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2508 fill_always_executed_in ();
2510 /* For each statement determine the outermost loop in that it is
2511 invariant and cost for computing the invariant. */
2512 invariantness_dom_walker (CDI_DOMINATORS
)
2513 .walk (cfun
->cfg
->x_entry_block_ptr
);
2515 /* Execute store motion. Force the necessary invariants to be moved
2516 out of the loops as well. */
2519 /* Move the expressions that are expensive enough. */
2520 todo
= move_computations ();
2522 tree_ssa_lim_finalize ();
2527 /* Loop invariant motion pass. */
2530 tree_ssa_loop_im (void)
2532 if (number_of_loops (cfun
) <= 1)
2535 return tree_ssa_lim ();
2539 gate_tree_ssa_loop_im (void)
2541 return flag_tree_loop_im
!= 0;
2546 const pass_data pass_data_lim
=
2548 GIMPLE_PASS
, /* type */
2550 OPTGROUP_LOOP
, /* optinfo_flags */
2551 true, /* has_gate */
2552 true, /* has_execute */
2554 PROP_cfg
, /* properties_required */
2555 0, /* properties_provided */
2556 0, /* properties_destroyed */
2557 0, /* todo_flags_start */
2558 0, /* todo_flags_finish */
2561 class pass_lim
: public gimple_opt_pass
2564 pass_lim (gcc::context
*ctxt
)
2565 : gimple_opt_pass (pass_data_lim
, ctxt
)
2568 /* opt_pass methods: */
2569 opt_pass
* clone () { return new pass_lim (m_ctxt
); }
2570 bool gate () { return gate_tree_ssa_loop_im (); }
2571 unsigned int execute () { return tree_ssa_loop_im (); }
2573 }; // class pass_lim
2578 make_pass_lim (gcc::context
*ctxt
)
2580 return new pass_lim (ctxt
);