1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "diagnostic.h"
30 #include "gimple-pretty-print.h"
31 #include "tree-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
41 #include "tree-affine.h"
42 #include "pointer-set.h"
43 #include "tree-ssa-propagate.h"
45 /* TODO: Support for predicated code motion. I.e.
56 Where COND and INV are is invariants, but evaluating INV may trap or be
57 invalid from some other reason if !COND. This may be transformed to
67 /* A type for the list of statements that have to be moved in order to be able
68 to hoist an invariant computation. */
76 /* The auxiliary data kept for each statement. */
80 struct loop *max_loop; /* The outermost loop in that the statement
83 struct loop *tgt_loop; /* The loop out of that we want to move the
86 struct loop *always_executed_in;
87 /* The outermost loop for that we are sure
88 the statement is executed if the loop
91 unsigned cost; /* Cost of the computation performed by the
94 struct depend *depends; /* List of statements that must be also hoisted
95 out of the loop when this statement is
96 hoisted; i.e. those that define the operands
97 of the statement and are inside of the
101 /* Maps statements to their lim_aux_data. */
103 static struct pointer_map_t *lim_aux_data_map;
105 /* Description of a memory reference location. */
107 typedef struct mem_ref_loc
109 tree *ref; /* The reference itself. */
110 gimple stmt; /* The statement in that it occurs. */
113 DEF_VEC_P(mem_ref_loc_p);
114 DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
116 /* The list of memory reference locations in a loop. */
118 typedef struct mem_ref_locs
120 VEC (mem_ref_loc_p, heap) *locs;
123 DEF_VEC_P(mem_ref_locs_p);
124 DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
126 /* Description of a memory reference. */
128 typedef struct mem_ref
130 tree mem; /* The memory itself. */
131 unsigned id; /* ID assigned to the memory reference
132 (its index in memory_accesses.refs_list) */
133 hashval_t hash; /* Its hash value. */
134 bitmap stored; /* The set of loops in that this memory location
136 VEC (mem_ref_locs_p, heap) *accesses_in_loop;
137 /* The locations of the accesses. Vector
138 indexed by the loop number. */
139 bitmap vops; /* Vops corresponding to this memory
142 /* The following sets are computed on demand. We keep both set and
143 its complement, so that we know whether the information was
144 already computed or not. */
145 bitmap indep_loop; /* The set of loops in that the memory
146 reference is independent, meaning:
147 If it is stored in the loop, this store
148 is independent on all other loads and
150 If it is only loaded, then it is independent
151 on all stores in the loop. */
152 bitmap dep_loop; /* The complement of INDEP_LOOP. */
154 bitmap indep_ref; /* The set of memory references on that
155 this reference is independent. */
156 bitmap dep_ref; /* The complement of DEP_REF. */
159 DEF_VEC_P(mem_ref_p);
160 DEF_VEC_ALLOC_P(mem_ref_p, heap);
163 DEF_VEC_ALLOC_P(bitmap, heap);
166 DEF_VEC_ALLOC_P(htab_t, heap);
168 /* Description of memory accesses in loops. */
172 /* The hash table of memory references accessed in loops. */
175 /* The list of memory references. */
176 VEC (mem_ref_p, heap) *refs_list;
178 /* The set of memory references accessed in each loop. */
179 VEC (bitmap, heap) *refs_in_loop;
181 /* The set of memory references accessed in each loop, including
183 VEC (bitmap, heap) *all_refs_in_loop;
185 /* The set of virtual operands clobbered in a given loop. */
186 VEC (bitmap, heap) *clobbered_vops;
188 /* Map from the pair (loop, virtual operand) to the set of refs that
189 touch the virtual operand in the loop. */
190 VEC (htab_t, heap) *vop_ref_map;
192 /* Cache for expanding memory addresses. */
193 struct pointer_map_t *ttae_cache;
196 static bool ref_indep_loop_p (struct loop *, mem_ref_p);
198 /* Minimum cost of an expensive expression. */
199 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
201 /* The outermost loop for that execution of the header guarantees that the
202 block will be executed. */
203 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
205 static struct lim_aux_data *
206 init_lim_data (gimple stmt)
208 void **p = pointer_map_insert (lim_aux_data_map, stmt);
210 *p = XCNEW (struct lim_aux_data);
211 return (struct lim_aux_data *) *p;
214 static struct lim_aux_data *
215 get_lim_data (gimple stmt)
217 void **p = pointer_map_contains (lim_aux_data_map, stmt);
221 return (struct lim_aux_data *) *p;
224 /* Releases the memory occupied by DATA. */
227 free_lim_aux_data (struct lim_aux_data *data)
229 struct depend *dep, *next;
231 for (dep = data->depends; dep; dep = next)
240 clear_lim_data (gimple stmt)
242 void **p = pointer_map_contains (lim_aux_data_map, stmt);
246 free_lim_aux_data ((struct lim_aux_data *) *p);
250 /* Calls CBCK for each index in memory reference ADDR_P. There are two
251 kinds situations handled; in each of these cases, the memory reference
252 and DATA are passed to the callback:
254 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
255 pass the pointer to the index to the callback.
257 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
258 pointer to addr to the callback.
260 If the callback returns false, the whole search stops and false is returned.
261 Otherwise the function returns true after traversing through the whole
262 reference *ADDR_P. */
265 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
269 for (; ; addr_p = nxt)
271 switch (TREE_CODE (*addr_p))
274 return cbck (*addr_p, addr_p, data);
276 case MISALIGNED_INDIRECT_REF:
277 case ALIGN_INDIRECT_REF:
279 nxt = &TREE_OPERAND (*addr_p, 0);
280 return cbck (*addr_p, nxt, data);
283 case VIEW_CONVERT_EXPR:
286 nxt = &TREE_OPERAND (*addr_p, 0);
290 /* If the component has varying offset, it behaves like index
292 idx = &TREE_OPERAND (*addr_p, 2);
294 && !cbck (*addr_p, idx, data))
297 nxt = &TREE_OPERAND (*addr_p, 0);
301 case ARRAY_RANGE_REF:
302 nxt = &TREE_OPERAND (*addr_p, 0);
303 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
320 gcc_assert (is_gimple_min_invariant (*addr_p));
324 idx = &TMR_BASE (*addr_p);
326 && !cbck (*addr_p, idx, data))
328 idx = &TMR_INDEX (*addr_p);
330 && !cbck (*addr_p, idx, data))
340 /* If it is possible to hoist the statement STMT unconditionally,
341 returns MOVE_POSSIBLE.
342 If it is possible to hoist the statement STMT, but we must avoid making
343 it executed if it would not be executed in the original program (e.g.
344 because it may trap), return MOVE_PRESERVE_EXECUTION.
345 Otherwise return MOVE_IMPOSSIBLE. */
348 movement_possibility (gimple stmt)
351 enum move_pos ret = MOVE_POSSIBLE;
353 if (flag_unswitch_loops
354 && gimple_code (stmt) == GIMPLE_COND)
356 /* If we perform unswitching, force the operands of the invariant
357 condition to be moved out of the loop. */
358 return MOVE_POSSIBLE;
361 if (gimple_code (stmt) == GIMPLE_PHI
362 && gimple_phi_num_args (stmt) <= 2
363 && is_gimple_reg (gimple_phi_result (stmt))
364 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
365 return MOVE_POSSIBLE;
367 if (gimple_get_lhs (stmt) == NULL_TREE)
368 return MOVE_IMPOSSIBLE;
370 if (gimple_vdef (stmt))
371 return MOVE_IMPOSSIBLE;
373 if (stmt_ends_bb_p (stmt)
374 || gimple_has_volatile_ops (stmt)
375 || gimple_has_side_effects (stmt)
376 || stmt_could_throw_p (stmt))
377 return MOVE_IMPOSSIBLE;
379 if (is_gimple_call (stmt))
381 /* While pure or const call is guaranteed to have no side effects, we
382 cannot move it arbitrarily. Consider code like
384 char *s = something ();
394 Here the strlen call cannot be moved out of the loop, even though
395 s is invariant. In addition to possibly creating a call with
396 invalid arguments, moving out a function call that is not executed
397 may cause performance regressions in case the call is costly and
398 not executed at all. */
399 ret = MOVE_PRESERVE_EXECUTION;
400 lhs = gimple_call_lhs (stmt);
402 else if (is_gimple_assign (stmt))
403 lhs = gimple_assign_lhs (stmt);
405 return MOVE_IMPOSSIBLE;
407 if (TREE_CODE (lhs) == SSA_NAME
408 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
409 return MOVE_IMPOSSIBLE;
411 if (TREE_CODE (lhs) != SSA_NAME
412 || gimple_could_trap_p (stmt))
413 return MOVE_PRESERVE_EXECUTION;
418 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
419 loop to that we could move the expression using DEF if it did not have
420 other operands, i.e. the outermost loop enclosing LOOP in that the value
421 of DEF is invariant. */
424 outermost_invariant_loop (tree def, struct loop *loop)
428 struct loop *max_loop;
429 struct lim_aux_data *lim_data;
432 return superloop_at_depth (loop, 1);
434 if (TREE_CODE (def) != SSA_NAME)
436 gcc_assert (is_gimple_min_invariant (def));
437 return superloop_at_depth (loop, 1);
440 def_stmt = SSA_NAME_DEF_STMT (def);
441 def_bb = gimple_bb (def_stmt);
443 return superloop_at_depth (loop, 1);
445 max_loop = find_common_loop (loop, def_bb->loop_father);
447 lim_data = get_lim_data (def_stmt);
448 if (lim_data != NULL && lim_data->max_loop != NULL)
449 max_loop = find_common_loop (max_loop,
450 loop_outer (lim_data->max_loop));
451 if (max_loop == loop)
453 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
458 /* DATA is a structure containing information associated with a statement
459 inside LOOP. DEF is one of the operands of this statement.
461 Find the outermost loop enclosing LOOP in that value of DEF is invariant
462 and record this in DATA->max_loop field. If DEF itself is defined inside
463 this loop as well (i.e. we need to hoist it out of the loop if we want
464 to hoist the statement represented by DATA), record the statement in that
465 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
466 add the cost of the computation of DEF to the DATA->cost.
468 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
471 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
474 gimple def_stmt = SSA_NAME_DEF_STMT (def);
475 basic_block def_bb = gimple_bb (def_stmt);
476 struct loop *max_loop;
478 struct lim_aux_data *def_data;
483 max_loop = outermost_invariant_loop (def, loop);
487 if (flow_loop_nested_p (data->max_loop, max_loop))
488 data->max_loop = max_loop;
490 def_data = get_lim_data (def_stmt);
495 /* Only add the cost if the statement defining DEF is inside LOOP,
496 i.e. if it is likely that by moving the invariants dependent
497 on it, we will be able to avoid creating a new register for
498 it (since it will be only used in these dependent invariants). */
499 && def_bb->loop_father == loop)
500 data->cost += def_data->cost;
502 dep = XNEW (struct depend);
503 dep->stmt = def_stmt;
504 dep->next = data->depends;
510 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
511 are just ad-hoc constants. The estimates should be based on target-specific
515 stmt_cost (gimple stmt)
520 /* Always try to create possibilities for unswitching. */
521 if (gimple_code (stmt) == GIMPLE_COND
522 || gimple_code (stmt) == GIMPLE_PHI)
523 return LIM_EXPENSIVE;
525 /* Hoisting memory references out should almost surely be a win. */
526 if (gimple_references_memory_p (stmt))
529 if (is_gimple_call (stmt))
531 /* We should be hoisting calls if possible. */
533 /* Unless the call is a builtin_constant_p; this always folds to a
534 constant, so moving it is useless. */
535 fndecl = gimple_call_fndecl (stmt);
537 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
538 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
544 if (gimple_code (stmt) != GIMPLE_ASSIGN)
547 switch (gimple_assign_rhs_code (stmt))
560 /* Division and multiplication are usually expensive. */
576 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
577 REF is independent. If REF is not independent in LOOP, NULL is returned
581 outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
585 if (bitmap_bit_p (ref->stored, loop->num))
590 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
591 if (!bitmap_bit_p (ref->stored, aloop->num)
592 && ref_indep_loop_p (aloop, ref))
595 if (ref_indep_loop_p (loop, ref))
601 /* If there is a simple load or store to a memory reference in STMT, returns
602 the location of the memory reference, and sets IS_STORE according to whether
603 it is a store or load. Otherwise, returns NULL. */
606 simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
611 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
612 if (gimple_code (stmt) != GIMPLE_ASSIGN)
615 code = gimple_assign_rhs_code (stmt);
617 lhs = gimple_assign_lhs_ptr (stmt);
619 if (TREE_CODE (*lhs) == SSA_NAME)
621 if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
622 || !is_gimple_addressable (gimple_assign_rhs1 (stmt)))
626 return gimple_assign_rhs1_ptr (stmt);
628 else if (code == SSA_NAME
629 || (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
630 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
639 /* Returns the memory reference contained in STMT. */
642 mem_ref_in_stmt (gimple stmt)
645 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
653 hash = iterative_hash_expr (*mem, 0);
654 ref = (mem_ref_p) htab_find_with_hash (memory_accesses.refs, *mem, hash);
656 gcc_assert (ref != NULL);
660 /* From a controlling predicate in DOM determine the arguments from
661 the PHI node PHI that are chosen if the predicate evaluates to
662 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
663 they are non-NULL. Returns true if the arguments can be determined,
664 else return false. */
667 extract_true_false_args_from_phi (basic_block dom, gimple phi,
668 tree *true_arg_p, tree *false_arg_p)
670 basic_block bb = gimple_bb (phi);
671 edge true_edge, false_edge, tem;
672 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
674 /* We have to verify that one edge into the PHI node is dominated
675 by the true edge of the predicate block and the other edge
676 dominated by the false edge. This ensures that the PHI argument
677 we are going to take is completely determined by the path we
678 take from the predicate block. */
679 extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
680 tem = EDGE_PRED (bb, 0);
682 || tem->src == true_edge->dest
683 || dominated_by_p (CDI_DOMINATORS,
684 tem->src, true_edge->dest))
685 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
686 else if (tem == false_edge
687 || tem->src == false_edge->dest
688 || dominated_by_p (CDI_DOMINATORS,
689 tem->src, false_edge->dest))
690 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
693 tem = EDGE_PRED (bb, 1);
695 || tem->src == true_edge->dest
696 || dominated_by_p (CDI_DOMINATORS,
697 tem->src, true_edge->dest))
698 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
699 else if (tem == false_edge
700 || tem->src == false_edge->dest
701 || dominated_by_p (CDI_DOMINATORS,
702 tem->src, false_edge->dest))
703 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
717 /* Determine the outermost loop to that it is possible to hoist a statement
718 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
719 the outermost loop in that the value computed by STMT is invariant.
720 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
721 we preserve the fact whether STMT is executed. It also fills other related
722 information to LIM_DATA (STMT).
724 The function returns false if STMT cannot be hoisted outside of the loop it
725 is defined in, and true otherwise. */
728 determine_max_movement (gimple stmt, bool must_preserve_exec)
730 basic_block bb = gimple_bb (stmt);
731 struct loop *loop = bb->loop_father;
733 struct lim_aux_data *lim_data = get_lim_data (stmt);
737 if (must_preserve_exec)
738 level = ALWAYS_EXECUTED_IN (bb);
740 level = superloop_at_depth (loop, 1);
741 lim_data->max_loop = level;
743 if (gimple_code (stmt) == GIMPLE_PHI)
746 unsigned min_cost = UINT_MAX;
747 unsigned total_cost = 0;
748 struct lim_aux_data *def_data;
750 /* We will end up promoting dependencies to be unconditionally
751 evaluated. For this reason the PHI cost (and thus the
752 cost we remove from the loop by doing the invariant motion)
753 is that of the cheapest PHI argument dependency chain. */
754 FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
756 val = USE_FROM_PTR (use_p);
757 if (TREE_CODE (val) != SSA_NAME)
759 if (!add_dependency (val, lim_data, loop, false))
761 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
764 min_cost = MIN (min_cost, def_data->cost);
765 total_cost += def_data->cost;
769 lim_data->cost += min_cost;
771 if (gimple_phi_num_args (stmt) > 1)
773 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
775 if (gsi_end_p (gsi_last_bb (dom)))
777 cond = gsi_stmt (gsi_last_bb (dom));
778 if (gimple_code (cond) != GIMPLE_COND)
780 /* Verify that this is an extended form of a diamond and
781 the PHI arguments are completely controlled by the
783 if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL))
786 /* Fold in dependencies and cost of the condition. */
787 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
789 if (!add_dependency (val, lim_data, loop, false))
791 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
793 total_cost += def_data->cost;
796 /* We want to avoid unconditionally executing very expensive
797 operations. As costs for our dependencies cannot be
798 negative just claim we are not invariand for this case.
799 We also are not sure whether the control-flow inside the
801 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
803 && total_cost / min_cost <= 2))
806 /* Assume that the control-flow in the loop will vanish.
807 ??? We should verify this and not artificially increase
808 the cost if that is not the case. */
809 lim_data->cost += stmt_cost (stmt);
815 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
816 if (!add_dependency (val, lim_data, loop, true))
819 if (gimple_vuse (stmt))
821 mem_ref_p ref = mem_ref_in_stmt (stmt);
826 = outermost_indep_loop (lim_data->max_loop, loop, ref);
827 if (!lim_data->max_loop)
832 if ((val = gimple_vuse (stmt)) != NULL_TREE)
834 if (!add_dependency (val, lim_data, loop, false))
840 lim_data->cost += stmt_cost (stmt);
845 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
846 and that one of the operands of this statement is computed by STMT.
847 Ensure that STMT (together with all the statements that define its
848 operands) is hoisted at least out of the loop LEVEL. */
851 set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
853 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
855 struct lim_aux_data *lim_data;
857 stmt_loop = find_common_loop (orig_loop, stmt_loop);
858 lim_data = get_lim_data (stmt);
859 if (lim_data != NULL && lim_data->tgt_loop != NULL)
860 stmt_loop = find_common_loop (stmt_loop,
861 loop_outer (lim_data->tgt_loop));
862 if (flow_loop_nested_p (stmt_loop, level))
865 gcc_assert (level == lim_data->max_loop
866 || flow_loop_nested_p (lim_data->max_loop, level));
868 lim_data->tgt_loop = level;
869 for (dep = lim_data->depends; dep; dep = dep->next)
870 set_level (dep->stmt, orig_loop, level);
873 /* Determines an outermost loop from that we want to hoist the statement STMT.
874 For now we chose the outermost possible loop. TODO -- use profiling
875 information to set it more sanely. */
878 set_profitable_level (gimple stmt)
880 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
883 /* Returns true if STMT is a call that has side effects. */
886 nonpure_call_p (gimple stmt)
888 if (gimple_code (stmt) != GIMPLE_CALL)
891 return gimple_has_side_effects (stmt);
894 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
897 rewrite_reciprocal (gimple_stmt_iterator *bsi)
899 gimple stmt, stmt1, stmt2;
900 tree var, name, lhs, type;
902 gimple_stmt_iterator gsi;
904 stmt = gsi_stmt (*bsi);
905 lhs = gimple_assign_lhs (stmt);
906 type = TREE_TYPE (lhs);
908 var = create_tmp_var (type, "reciptmp");
909 add_referenced_var (var);
910 DECL_GIMPLE_REG_P (var) = 1;
912 /* For vectors, create a VECTOR_CST full of 1's. */
913 if (TREE_CODE (type) == VECTOR_TYPE)
916 tree list = NULL_TREE;
917 real_one = build_real (TREE_TYPE (type), dconst1);
918 len = TYPE_VECTOR_SUBPARTS (type);
919 for (i = 0; i < len; i++)
920 list = tree_cons (NULL, real_one, list);
921 real_one = build_vector (type, list);
924 real_one = build_real (type, dconst1);
926 stmt1 = gimple_build_assign_with_ops (RDIV_EXPR,
927 var, real_one, gimple_assign_rhs2 (stmt));
928 name = make_ssa_name (var, stmt1);
929 gimple_assign_set_lhs (stmt1, name);
931 stmt2 = gimple_build_assign_with_ops (MULT_EXPR, lhs, name,
932 gimple_assign_rhs1 (stmt));
934 /* Replace division stmt with reciprocal and multiply stmts.
935 The multiply stmt is not invariant, so update iterator
936 and avoid rescanning. */
938 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
939 gsi_replace (&gsi, stmt2, true);
941 /* Continue processing with invariant reciprocal statement. */
945 /* Check if the pattern at *BSI is a bittest of the form
946 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
949 rewrite_bittest (gimple_stmt_iterator *bsi)
951 gimple stmt, use_stmt, stmt1, stmt2;
952 tree lhs, var, name, t, a, b;
955 stmt = gsi_stmt (*bsi);
956 lhs = gimple_assign_lhs (stmt);
958 /* Verify that the single use of lhs is a comparison against zero. */
959 if (TREE_CODE (lhs) != SSA_NAME
960 || !single_imm_use (lhs, &use, &use_stmt)
961 || gimple_code (use_stmt) != GIMPLE_COND)
963 if (gimple_cond_lhs (use_stmt) != lhs
964 || (gimple_cond_code (use_stmt) != NE_EXPR
965 && gimple_cond_code (use_stmt) != EQ_EXPR)
966 || !integer_zerop (gimple_cond_rhs (use_stmt)))
969 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
970 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
971 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
974 /* There is a conversion in between possibly inserted by fold. */
975 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
977 t = gimple_assign_rhs1 (stmt1);
978 if (TREE_CODE (t) != SSA_NAME
979 || !has_single_use (t))
981 stmt1 = SSA_NAME_DEF_STMT (t);
982 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
986 /* Verify that B is loop invariant but A is not. Verify that with
987 all the stmt walking we are still in the same loop. */
988 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
989 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
992 a = gimple_assign_rhs1 (stmt1);
993 b = gimple_assign_rhs2 (stmt1);
995 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
996 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
998 gimple_stmt_iterator rsi;
1001 var = create_tmp_var (TREE_TYPE (a), "shifttmp");
1002 add_referenced_var (var);
1003 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
1004 build_int_cst (TREE_TYPE (a), 1), b);
1005 stmt1 = gimple_build_assign (var, t);
1006 name = make_ssa_name (var, stmt1);
1007 gimple_assign_set_lhs (stmt1, name);
1010 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
1011 stmt2 = gimple_build_assign (var, t);
1012 name = make_ssa_name (var, stmt2);
1013 gimple_assign_set_lhs (stmt2, name);
1015 /* Replace the SSA_NAME we compare against zero. Adjust
1016 the type of zero accordingly. */
1017 SET_USE (use, name);
1018 gimple_cond_set_rhs (use_stmt, build_int_cst_type (TREE_TYPE (name), 0));
1020 /* Don't use gsi_replace here, none of the new assignments sets
1021 the variable originally set in stmt. Move bsi to stmt1, and
1022 then remove the original stmt, so that we get a chance to
1023 retain debug info for it. */
1025 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
1026 gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
1027 gsi_remove (&rsi, true);
1036 /* Determine the outermost loops in that statements in basic block BB are
1037 invariant, and record them to the LIM_DATA associated with the statements.
1038 Callback for walk_dominator_tree. */
1041 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
1045 gimple_stmt_iterator bsi;
1047 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
1048 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
1049 struct lim_aux_data *lim_data;
1051 if (!loop_outer (bb->loop_father))
1054 if (dump_file && (dump_flags & TDF_DETAILS))
1055 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
1056 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
1058 /* Look at PHI nodes, but only if there is at most two.
1059 ??? We could relax this further by post-processing the inserted
1060 code and transforming adjacent cond-exprs with the same predicate
1061 to control flow again. */
1062 bsi = gsi_start_phis (bb);
1063 if (!gsi_end_p (bsi)
1064 && ((gsi_next (&bsi), gsi_end_p (bsi))
1065 || (gsi_next (&bsi), gsi_end_p (bsi))))
1066 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1068 stmt = gsi_stmt (bsi);
1070 pos = movement_possibility (stmt);
1071 if (pos == MOVE_IMPOSSIBLE)
1074 lim_data = init_lim_data (stmt);
1075 lim_data->always_executed_in = outermost;
1077 if (!determine_max_movement (stmt, false))
1079 lim_data->max_loop = NULL;
1083 if (dump_file && (dump_flags & TDF_DETAILS))
1085 print_gimple_stmt (dump_file, stmt, 2, 0);
1086 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1087 loop_depth (lim_data->max_loop),
1091 if (lim_data->cost >= LIM_EXPENSIVE)
1092 set_profitable_level (stmt);
1095 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1097 stmt = gsi_stmt (bsi);
1099 pos = movement_possibility (stmt);
1100 if (pos == MOVE_IMPOSSIBLE)
1102 if (nonpure_call_p (stmt))
1107 /* Make sure to note always_executed_in for stores to make
1108 store-motion work. */
1109 else if (stmt_makes_single_store (stmt))
1111 struct lim_aux_data *lim_data = init_lim_data (stmt);
1112 lim_data->always_executed_in = outermost;
1117 if (is_gimple_assign (stmt)
1118 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1119 == GIMPLE_BINARY_RHS))
1121 tree op0 = gimple_assign_rhs1 (stmt);
1122 tree op1 = gimple_assign_rhs2 (stmt);
1123 struct loop *ol1 = outermost_invariant_loop (op1,
1124 loop_containing_stmt (stmt));
1126 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1127 to be hoisted out of loop, saving expensive divide. */
1128 if (pos == MOVE_POSSIBLE
1129 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
1130 && flag_unsafe_math_optimizations
1131 && !flag_trapping_math
1133 && outermost_invariant_loop (op0, ol1) == NULL)
1134 stmt = rewrite_reciprocal (&bsi);
1136 /* If the shift count is invariant, convert (A >> B) & 1 to
1137 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1138 saving an expensive shift. */
1139 if (pos == MOVE_POSSIBLE
1140 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
1141 && integer_onep (op1)
1142 && TREE_CODE (op0) == SSA_NAME
1143 && has_single_use (op0))
1144 stmt = rewrite_bittest (&bsi);
1147 lim_data = init_lim_data (stmt);
1148 lim_data->always_executed_in = outermost;
1150 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1153 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1155 lim_data->max_loop = NULL;
1159 if (dump_file && (dump_flags & TDF_DETAILS))
1161 print_gimple_stmt (dump_file, stmt, 2, 0);
1162 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1163 loop_depth (lim_data->max_loop),
1167 if (lim_data->cost >= LIM_EXPENSIVE)
1168 set_profitable_level (stmt);
1172 /* For each statement determines the outermost loop in that it is invariant,
1173 statements on whose motion it depends and the cost of the computation.
1174 This information is stored to the LIM_DATA structure associated with
1178 determine_invariantness (void)
1180 struct dom_walk_data walk_data;
1182 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1183 walk_data.dom_direction = CDI_DOMINATORS;
1184 walk_data.before_dom_children = determine_invariantness_stmt;
1186 init_walk_dominator_tree (&walk_data);
1187 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1188 fini_walk_dominator_tree (&walk_data);
1191 /* Hoist the statements in basic block BB out of the loops prescribed by
1192 data stored in LIM_DATA structures associated with each statement. Callback
1193 for walk_dominator_tree. */
1196 move_computations_stmt (struct dom_walk_data *dw_data,
1200 gimple_stmt_iterator bsi;
1203 struct lim_aux_data *lim_data;
1205 if (!loop_outer (bb->loop_father))
1208 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1211 stmt = gsi_stmt (bsi);
1213 lim_data = get_lim_data (stmt);
1214 if (lim_data == NULL)
1220 cost = lim_data->cost;
1221 level = lim_data->tgt_loop;
1222 clear_lim_data (stmt);
1230 if (dump_file && (dump_flags & TDF_DETAILS))
1232 fprintf (dump_file, "Moving PHI node\n");
1233 print_gimple_stmt (dump_file, stmt, 0, 0);
1234 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1238 if (gimple_phi_num_args (stmt) == 1)
1240 tree arg = PHI_ARG_DEF (stmt, 0);
1241 new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
1242 gimple_phi_result (stmt),
1244 SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
1248 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
1249 gimple cond = gsi_stmt (gsi_last_bb (dom));
1250 tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
1251 /* Get the PHI arguments corresponding to the true and false
1253 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
1254 gcc_assert (arg0 && arg1);
1255 t = build2 (gimple_cond_code (cond), boolean_type_node,
1256 gimple_cond_lhs (cond), gimple_cond_rhs (cond));
1257 t = build3 (COND_EXPR, TREE_TYPE (gimple_phi_result (stmt)),
1259 new_stmt = gimple_build_assign_with_ops (COND_EXPR,
1260 gimple_phi_result (stmt),
1262 SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
1263 *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg;
1265 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1266 remove_phi_node (&bsi, false);
1269 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1271 stmt = gsi_stmt (bsi);
1273 lim_data = get_lim_data (stmt);
1274 if (lim_data == NULL)
1280 cost = lim_data->cost;
1281 level = lim_data->tgt_loop;
1282 clear_lim_data (stmt);
1290 /* We do not really want to move conditionals out of the loop; we just
1291 placed it here to force its operands to be moved if necessary. */
1292 if (gimple_code (stmt) == GIMPLE_COND)
1295 if (dump_file && (dump_flags & TDF_DETAILS))
1297 fprintf (dump_file, "Moving statement\n");
1298 print_gimple_stmt (dump_file, stmt, 0, 0);
1299 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1303 mark_virtual_ops_for_renaming (stmt);
1304 gsi_insert_on_edge (loop_preheader_edge (level), stmt);
1305 gsi_remove (&bsi, false);
1309 /* Hoist the statements out of the loops prescribed by data stored in
1310 LIM_DATA structures associated with each statement.*/
1313 move_computations (void)
1315 struct dom_walk_data walk_data;
1316 unsigned int todo = 0;
1318 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1319 walk_data.global_data = &todo;
1320 walk_data.dom_direction = CDI_DOMINATORS;
1321 walk_data.before_dom_children = move_computations_stmt;
1323 init_walk_dominator_tree (&walk_data);
1324 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1325 fini_walk_dominator_tree (&walk_data);
1327 gsi_commit_edge_inserts ();
1328 if (need_ssa_update_p (cfun))
1329 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1334 /* Checks whether the statement defining variable *INDEX can be hoisted
1335 out of the loop passed in DATA. Callback for for_each_index. */
1338 may_move_till (tree ref, tree *index, void *data)
1340 struct loop *loop = (struct loop *) data, *max_loop;
1342 /* If REF is an array reference, check also that the step and the lower
1343 bound is invariant in LOOP. */
1344 if (TREE_CODE (ref) == ARRAY_REF)
1346 tree step = TREE_OPERAND (ref, 3);
1347 tree lbound = TREE_OPERAND (ref, 2);
1349 max_loop = outermost_invariant_loop (step, loop);
1353 max_loop = outermost_invariant_loop (lbound, loop);
1358 max_loop = outermost_invariant_loop (*index, loop);
1365 /* If OP is SSA NAME, force the statement that defines it to be
1366 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1369 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1374 || is_gimple_min_invariant (op))
1377 gcc_assert (TREE_CODE (op) == SSA_NAME);
1379 stmt = SSA_NAME_DEF_STMT (op);
1380 if (gimple_nop_p (stmt))
1383 set_level (stmt, orig_loop, loop);
1386 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1387 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1393 struct loop *orig_loop;
1397 force_move_till (tree ref, tree *index, void *data)
1399 struct fmt_data *fmt_data = (struct fmt_data *) data;
1401 if (TREE_CODE (ref) == ARRAY_REF)
1403 tree step = TREE_OPERAND (ref, 3);
1404 tree lbound = TREE_OPERAND (ref, 2);
1406 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1407 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1410 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1415 /* A hash function for struct mem_ref object OBJ. */
1418 memref_hash (const void *obj)
1420 const struct mem_ref *const mem = (const struct mem_ref *) obj;
1425 /* An equality function for struct mem_ref object OBJ1 with
1426 memory reference OBJ2. */
1429 memref_eq (const void *obj1, const void *obj2)
1431 const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
1433 return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
1436 /* Releases list of memory reference locations ACCS. */
1439 free_mem_ref_locs (mem_ref_locs_p accs)
1447 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1449 VEC_free (mem_ref_loc_p, heap, accs->locs);
1453 /* A function to free the mem_ref object OBJ. */
1456 memref_free (void *obj)
1458 struct mem_ref *const mem = (struct mem_ref *) obj;
1460 mem_ref_locs_p accs;
1462 BITMAP_FREE (mem->stored);
1463 BITMAP_FREE (mem->indep_loop);
1464 BITMAP_FREE (mem->dep_loop);
1465 BITMAP_FREE (mem->indep_ref);
1466 BITMAP_FREE (mem->dep_ref);
1468 for (i = 0; VEC_iterate (mem_ref_locs_p, mem->accesses_in_loop, i, accs); i++)
1469 free_mem_ref_locs (accs);
1470 VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
1472 BITMAP_FREE (mem->vops);
1476 /* Allocates and returns a memory reference description for MEM whose hash
1477 value is HASH and id is ID. */
1480 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1482 mem_ref_p ref = XNEW (struct mem_ref);
1486 ref->stored = BITMAP_ALLOC (NULL);
1487 ref->indep_loop = BITMAP_ALLOC (NULL);
1488 ref->dep_loop = BITMAP_ALLOC (NULL);
1489 ref->indep_ref = BITMAP_ALLOC (NULL);
1490 ref->dep_ref = BITMAP_ALLOC (NULL);
1491 ref->accesses_in_loop = NULL;
1492 ref->vops = BITMAP_ALLOC (NULL);
1497 /* Allocates and returns the new list of locations. */
1499 static mem_ref_locs_p
1500 mem_ref_locs_alloc (void)
1502 mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
1507 /* Records memory reference location *LOC in LOOP to the memory reference
1508 description REF. The reference occurs in statement STMT. */
1511 record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
1513 mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
1514 mem_ref_locs_p accs;
1515 bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1517 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1518 <= (unsigned) loop->num)
1519 VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
1521 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1524 accs = mem_ref_locs_alloc ();
1525 VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
1531 VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
1532 bitmap_set_bit (ril, ref->id);
1535 /* Marks reference REF as stored in LOOP. */
1538 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1541 loop != current_loops->tree_root
1542 && !bitmap_bit_p (ref->stored, loop->num);
1543 loop = loop_outer (loop))
1544 bitmap_set_bit (ref->stored, loop->num);
1547 /* Gathers memory references in statement STMT in LOOP, storing the
1548 information about them in the memory_accesses structure. Marks
1549 the vops accessed through unrecognized statements there as
1553 gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1564 if (!gimple_vuse (stmt))
1567 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1571 hash = iterative_hash_expr (*mem, 0);
1572 slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
1576 ref = (mem_ref_p) *slot;
1581 id = VEC_length (mem_ref_p, memory_accesses.refs_list);
1582 ref = mem_ref_alloc (*mem, hash, id);
1583 VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
1586 if (dump_file && (dump_flags & TDF_DETAILS))
1588 fprintf (dump_file, "Memory reference %u: ", id);
1589 print_generic_expr (dump_file, ref->mem, TDF_SLIM);
1590 fprintf (dump_file, "\n");
1594 mark_ref_stored (ref, loop);
1596 if ((vname = gimple_vuse (stmt)) != NULL_TREE)
1597 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1598 record_mem_ref_loc (ref, loop, stmt, mem);
1602 clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1603 if ((vname = gimple_vuse (stmt)) != NULL_TREE)
1604 bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
1607 /* Gathers memory references in loops. */
1610 gather_mem_refs_in_loops (void)
1612 gimple_stmt_iterator bsi;
1617 bitmap lrefs, alrefs, alrefso;
1621 loop = bb->loop_father;
1622 if (loop == current_loops->tree_root)
1625 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1626 gather_mem_refs_stmt (loop, gsi_stmt (bsi));
1629 /* Propagate the information about clobbered vops and accessed memory
1630 references up the loop hierarchy. */
1631 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1633 lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1634 alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
1635 bitmap_ior_into (alrefs, lrefs);
1637 if (loop_outer (loop) == current_loops->tree_root)
1640 clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1641 clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
1642 loop_outer (loop)->num);
1643 bitmap_ior_into (clvo, clvi);
1645 alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1646 loop_outer (loop)->num);
1647 bitmap_ior_into (alrefso, alrefs);
1651 /* Element of the hash table that maps vops to memory references. */
1653 struct vop_to_refs_elt
1655 /* DECL_UID of the vop. */
1658 /* List of the all references. */
1661 /* List of stored references. */
1665 /* A hash function for struct vop_to_refs_elt object OBJ. */
1668 vtoe_hash (const void *obj)
1670 const struct vop_to_refs_elt *const vtoe =
1671 (const struct vop_to_refs_elt *) obj;
1676 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1677 uid of a vop OBJ2. */
1680 vtoe_eq (const void *obj1, const void *obj2)
1682 const struct vop_to_refs_elt *const vtoe =
1683 (const struct vop_to_refs_elt *) obj1;
1684 const unsigned *const uid = (const unsigned *) obj2;
1686 return vtoe->uid == *uid;
1689 /* A function to free the struct vop_to_refs_elt object. */
1692 vtoe_free (void *obj)
1694 struct vop_to_refs_elt *const vtoe =
1695 (struct vop_to_refs_elt *) obj;
1697 BITMAP_FREE (vtoe->refs_all);
1698 BITMAP_FREE (vtoe->refs_stored);
1702 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1703 if the reference REF is stored. */
1706 record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool stored)
1708 void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
1709 struct vop_to_refs_elt *vtoe;
1713 vtoe = XNEW (struct vop_to_refs_elt);
1715 vtoe->refs_all = BITMAP_ALLOC (NULL);
1716 vtoe->refs_stored = BITMAP_ALLOC (NULL);
1720 vtoe = (struct vop_to_refs_elt *) *slot;
1722 bitmap_set_bit (vtoe->refs_all, ref);
1724 bitmap_set_bit (vtoe->refs_stored, ref);
1727 /* Returns the set of references that access VOP according to the table
1731 get_vop_accesses (htab_t vop_to_refs, unsigned vop)
1733 struct vop_to_refs_elt *const vtoe =
1734 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1735 return vtoe->refs_all;
1738 /* Returns the set of stores that access VOP according to the table
1742 get_vop_stores (htab_t vop_to_refs, unsigned vop)
1744 struct vop_to_refs_elt *const vtoe =
1745 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1746 return vtoe->refs_stored;
1749 /* Adds REF to mapping from virtual operands to references in LOOP. */
1752 add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
1754 htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1755 bool stored = bitmap_bit_p (ref->stored, loop->num);
1756 bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
1761 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
1763 record_vop_access (map, vop, ref->id, stored);
1767 /* Create a mapping from virtual operands to references that touch them
1771 create_vop_ref_mapping_loop (struct loop *loop)
1773 bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1779 EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
1781 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1782 for (sloop = loop; sloop != current_loops->tree_root; sloop = loop_outer (sloop))
1783 add_vop_ref_mapping (sloop, ref);
1787 /* For each non-clobbered virtual operand and each loop, record the memory
1788 references in this loop that touch the operand. */
1791 create_vop_ref_mapping (void)
1796 FOR_EACH_LOOP (li, loop, 0)
1798 create_vop_ref_mapping_loop (loop);
1802 /* Gathers information about memory accesses in the loops. */
1805 analyze_memory_references (void)
1811 memory_accesses.refs
1812 = htab_create (100, memref_hash, memref_eq, memref_free);
1813 memory_accesses.refs_list = NULL;
1814 memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
1815 number_of_loops ());
1816 memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
1817 number_of_loops ());
1818 memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
1819 number_of_loops ());
1820 memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
1821 number_of_loops ());
1823 for (i = 0; i < number_of_loops (); i++)
1825 empty = BITMAP_ALLOC (NULL);
1826 VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
1827 empty = BITMAP_ALLOC (NULL);
1828 VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
1829 empty = BITMAP_ALLOC (NULL);
1830 VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
1831 hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
1832 VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
1835 memory_accesses.ttae_cache = NULL;
1837 gather_mem_refs_in_loops ();
1838 create_vop_ref_mapping ();
1841 /* Returns true if a region of size SIZE1 at position 0 and a region of
1842 size SIZE2 at position DIFF cannot overlap. */
1845 cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
1847 double_int d, bound;
1849 /* Unless the difference is a constant, we fail. */
1854 if (double_int_negative_p (d))
1856 /* The second object is before the first one, we succeed if the last
1857 element of the second object is before the start of the first one. */
1858 bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
1859 return double_int_negative_p (bound);
1863 /* We succeed if the second object starts after the first one ends. */
1864 return double_int_scmp (size1, d) <= 0;
1868 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1869 tree_to_aff_combination_expand. */
1872 mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
1874 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1875 object and their offset differ in such a way that the locations cannot
1876 overlap, then they cannot alias. */
1877 double_int size1, size2;
1878 aff_tree off1, off2;
1880 /* Perform basic offset and type-based disambiguation. */
1881 if (!refs_may_alias_p (mem1, mem2))
1884 /* The expansion of addresses may be a bit expensive, thus we only do
1885 the check at -O2 and higher optimization levels. */
1889 get_inner_reference_aff (mem1, &off1, &size1);
1890 get_inner_reference_aff (mem2, &off2, &size2);
1891 aff_combination_expand (&off1, ttae_cache);
1892 aff_combination_expand (&off2, ttae_cache);
1893 aff_combination_scale (&off1, double_int_minus_one);
1894 aff_combination_add (&off2, &off1);
1896 if (cannot_overlap_p (&off2, size1, size2))
1902 /* Rewrites location LOC by TMP_VAR. */
1905 rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
1907 mark_virtual_ops_for_renaming (loc->stmt);
1908 *loc->ref = tmp_var;
1909 update_stmt (loc->stmt);
1912 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1915 get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
1916 VEC (mem_ref_loc_p, heap) **locs)
1918 mem_ref_locs_p accs;
1921 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1923 struct loop *subloop;
1925 if (!bitmap_bit_p (refs, ref->id))
1928 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1929 > (unsigned) loop->num)
1931 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1934 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1935 VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
1939 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1940 get_all_locs_in_loop (subloop, ref, locs);
1943 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1946 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1950 VEC (mem_ref_loc_p, heap) *locs = NULL;
1952 get_all_locs_in_loop (loop, ref, &locs);
1953 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1954 rewrite_mem_ref_loc (loc, tmp_var);
1955 VEC_free (mem_ref_loc_p, heap, locs);
1958 /* The name and the length of the currently generated variable
1960 #define MAX_LSM_NAME_LENGTH 40
1961 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1962 static int lsm_tmp_name_length;
1964 /* Adds S to lsm_tmp_name. */
1967 lsm_tmp_name_add (const char *s)
1969 int l = strlen (s) + lsm_tmp_name_length;
1970 if (l > MAX_LSM_NAME_LENGTH)
1973 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1974 lsm_tmp_name_length = l;
1977 /* Stores the name for temporary variable that replaces REF to
1981 gen_lsm_tmp_name (tree ref)
1985 switch (TREE_CODE (ref))
1987 case MISALIGNED_INDIRECT_REF:
1988 case ALIGN_INDIRECT_REF:
1990 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1991 lsm_tmp_name_add ("_");
1995 case VIEW_CONVERT_EXPR:
1996 case ARRAY_RANGE_REF:
1997 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
2001 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
2002 lsm_tmp_name_add ("_RE");
2006 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
2007 lsm_tmp_name_add ("_IM");
2011 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
2012 lsm_tmp_name_add ("_");
2013 name = get_name (TREE_OPERAND (ref, 1));
2016 lsm_tmp_name_add (name);
2020 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
2021 lsm_tmp_name_add ("_I");
2025 ref = SSA_NAME_VAR (ref);
2030 name = get_name (ref);
2033 lsm_tmp_name_add (name);
2037 lsm_tmp_name_add ("S");
2041 lsm_tmp_name_add ("R");
2053 /* Determines name for temporary variable that replaces REF.
2054 The name is accumulated into the lsm_tmp_name variable.
2055 N is added to the name of the temporary. */
2058 get_lsm_tmp_name (tree ref, unsigned n)
2062 lsm_tmp_name_length = 0;
2063 gen_lsm_tmp_name (ref);
2064 lsm_tmp_name_add ("_lsm");
2069 lsm_tmp_name_add (ns);
2071 return lsm_tmp_name;
2074 /* Executes store motion of memory reference REF from LOOP.
2075 Exits from the LOOP are stored in EXITS. The initialization of the
2076 temporary variable is put to the preheader of the loop, and assignments
2077 to the reference from the temporary variable are emitted to exits. */
2080 execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
2085 struct fmt_data fmt_data;
2087 struct lim_aux_data *lim_data;
2089 if (dump_file && (dump_flags & TDF_DETAILS))
2091 fprintf (dump_file, "Executing store motion of ");
2092 print_generic_expr (dump_file, ref->mem, 0);
2093 fprintf (dump_file, " from loop %d\n", loop->num);
2096 tmp_var = make_rename_temp (TREE_TYPE (ref->mem),
2097 get_lsm_tmp_name (ref->mem, ~0));
2099 fmt_data.loop = loop;
2100 fmt_data.orig_loop = loop;
2101 for_each_index (&ref->mem, force_move_till, &fmt_data);
2103 rewrite_mem_refs (loop, ref, tmp_var);
2105 /* Emit the load & stores. */
2106 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem));
2107 lim_data = init_lim_data (load);
2108 lim_data->max_loop = loop;
2109 lim_data->tgt_loop = loop;
2111 /* Put this into the latch, so that we are sure it will be processed after
2112 all dependencies. */
2113 gsi_insert_on_edge (loop_latch_edge (loop), load);
2115 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2117 store = gimple_build_assign (unshare_expr (ref->mem), tmp_var);
2118 gsi_insert_on_edge (ex, store);
2122 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2123 edges of the LOOP. */
2126 hoist_memory_references (struct loop *loop, bitmap mem_refs,
2127 VEC (edge, heap) *exits)
2133 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2135 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2136 execute_sm (loop, exits, ref);
2140 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2141 make sure REF is always stored to in LOOP. */
2144 ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
2146 VEC (mem_ref_loc_p, heap) *locs = NULL;
2150 struct loop *must_exec;
2153 base = get_base_address (ref->mem);
2154 if (INDIRECT_REF_P (base))
2155 base = TREE_OPERAND (base, 0);
2157 get_all_locs_in_loop (loop, ref, &locs);
2158 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
2160 if (!get_lim_data (loc->stmt))
2163 /* If we require an always executed store make sure the statement
2164 stores to the reference. */
2168 if (!gimple_get_lhs (loc->stmt))
2170 lhs = get_base_address (gimple_get_lhs (loc->stmt));
2173 if (INDIRECT_REF_P (lhs))
2174 lhs = TREE_OPERAND (lhs, 0);
2179 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2183 if (must_exec == loop
2184 || flow_loop_nested_p (must_exec, loop))
2190 VEC_free (mem_ref_loc_p, heap, locs);
2195 /* Returns true if REF1 and REF2 are independent. */
2198 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
2201 || bitmap_bit_p (ref1->indep_ref, ref2->id))
2203 if (bitmap_bit_p (ref1->dep_ref, ref2->id))
2206 if (dump_file && (dump_flags & TDF_DETAILS))
2207 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2208 ref1->id, ref2->id);
2210 if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
2211 &memory_accesses.ttae_cache))
2213 bitmap_set_bit (ref1->dep_ref, ref2->id);
2214 bitmap_set_bit (ref2->dep_ref, ref1->id);
2215 if (dump_file && (dump_flags & TDF_DETAILS))
2216 fprintf (dump_file, "dependent.\n");
2221 bitmap_set_bit (ref1->indep_ref, ref2->id);
2222 bitmap_set_bit (ref2->indep_ref, ref1->id);
2223 if (dump_file && (dump_flags & TDF_DETAILS))
2224 fprintf (dump_file, "independent.\n");
2229 /* Records the information whether REF is independent in LOOP (according
2233 record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
2236 bitmap_set_bit (ref->indep_loop, loop->num);
2238 bitmap_set_bit (ref->dep_loop, loop->num);
2241 /* Returns true if REF is independent on all other memory references in
2245 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
2247 bitmap clobbers, refs_to_check, refs;
2250 bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
2254 /* If the reference is clobbered, it is not independent. */
2255 clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
2256 if (bitmap_intersect_p (ref->vops, clobbers))
2259 refs_to_check = BITMAP_ALLOC (NULL);
2261 map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
2262 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
2265 refs = get_vop_accesses (map, i);
2267 refs = get_vop_stores (map, i);
2269 bitmap_ior_into (refs_to_check, refs);
2272 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2274 aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2275 if (!refs_independent_p (ref, aref))
2278 record_indep_loop (loop, aref, false);
2283 BITMAP_FREE (refs_to_check);
2287 /* Returns true if REF is independent on all other memory references in
2288 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2291 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2295 if (bitmap_bit_p (ref->indep_loop, loop->num))
2297 if (bitmap_bit_p (ref->dep_loop, loop->num))
2300 ret = ref_indep_loop_p_1 (loop, ref);
2302 if (dump_file && (dump_flags & TDF_DETAILS))
2303 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2304 ref->id, loop->num, ret ? "independent" : "dependent");
2306 record_indep_loop (loop, ref, ret);
2311 /* Returns true if we can perform store motion of REF from LOOP. */
2314 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2318 /* Unless the reference is stored in the loop, there is nothing to do. */
2319 if (!bitmap_bit_p (ref->stored, loop->num))
2322 /* It should be movable. */
2323 if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
2324 || TREE_THIS_VOLATILE (ref->mem)
2325 || !for_each_index (&ref->mem, may_move_till, loop))
2328 /* If it can trap, it must be always executed in LOOP.
2329 Readonly memory locations may trap when storing to them, but
2330 tree_could_trap_p is a predicate for rvalues, so check that
2332 base = get_base_address (ref->mem);
2333 if ((tree_could_trap_p (ref->mem)
2334 || (DECL_P (base) && TREE_READONLY (base)))
2335 && !ref_always_accessed_p (loop, ref, true))
2338 /* And it must be independent on all other memory references
2340 if (!ref_indep_loop_p (loop, ref))
2346 /* Marks the references in LOOP for that store motion should be performed
2347 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2348 motion was performed in one of the outer loops. */
2351 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2353 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
2359 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2361 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2362 if (can_sm_ref_p (loop, ref))
2363 bitmap_set_bit (refs_to_sm, i);
2367 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2368 for a store motion optimization (i.e. whether we can insert statement
2372 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2373 VEC (edge, heap) *exits)
2378 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2379 if (ex->flags & EDGE_ABNORMAL)
2385 /* Try to perform store motion for all memory references modified inside
2386 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2387 store motion was executed in one of the outer loops. */
2390 store_motion_loop (struct loop *loop, bitmap sm_executed)
2392 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2393 struct loop *subloop;
2394 bitmap sm_in_loop = BITMAP_ALLOC (NULL);
2396 if (loop_suitable_for_sm (loop, exits))
2398 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2399 hoist_memory_references (loop, sm_in_loop, exits);
2401 VEC_free (edge, heap, exits);
2403 bitmap_ior_into (sm_executed, sm_in_loop);
2404 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2405 store_motion_loop (subloop, sm_executed);
2406 bitmap_and_compl_into (sm_executed, sm_in_loop);
2407 BITMAP_FREE (sm_in_loop);
2410 /* Try to perform store motion for all memory references modified inside
2417 bitmap sm_executed = BITMAP_ALLOC (NULL);
2419 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2420 store_motion_loop (loop, sm_executed);
2422 BITMAP_FREE (sm_executed);
2423 gsi_commit_edge_inserts ();
2426 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2427 for each such basic block bb records the outermost loop for that execution
2428 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2429 blocks that contain a nonpure call. */
2432 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
2434 basic_block bb = NULL, *bbs, last = NULL;
2437 struct loop *inn_loop = loop;
2439 if (!loop->header->aux)
2441 bbs = get_loop_body_in_dom_order (loop);
2443 for (i = 0; i < loop->num_nodes; i++)
2448 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2451 if (TEST_BIT (contains_call, bb->index))
2454 FOR_EACH_EDGE (e, ei, bb->succs)
2455 if (!flow_bb_inside_loop_p (loop, e->dest))
2460 /* A loop might be infinite (TODO use simple loop analysis
2461 to disprove this if possible). */
2462 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2465 if (!flow_bb_inside_loop_p (inn_loop, bb))
2468 if (bb->loop_father->header == bb)
2470 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2473 /* In a loop that is always entered we may proceed anyway.
2474 But record that we entered it and stop once we leave it. */
2475 inn_loop = bb->loop_father;
2482 if (last == loop->header)
2484 last = get_immediate_dominator (CDI_DOMINATORS, last);
2490 for (loop = loop->inner; loop; loop = loop->next)
2491 fill_always_executed_in (loop, contains_call);
2494 /* Compute the global information needed by the loop invariant motion pass. */
2497 tree_ssa_lim_initialize (void)
2499 sbitmap contains_call = sbitmap_alloc (last_basic_block);
2500 gimple_stmt_iterator bsi;
2504 sbitmap_zero (contains_call);
2507 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2509 if (nonpure_call_p (gsi_stmt (bsi)))
2513 if (!gsi_end_p (bsi))
2514 SET_BIT (contains_call, bb->index);
2517 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2518 fill_always_executed_in (loop, contains_call);
2520 sbitmap_free (contains_call);
2522 lim_aux_data_map = pointer_map_create ();
2525 /* Cleans up after the invariant motion pass. */
2528 tree_ssa_lim_finalize (void)
2540 pointer_map_destroy (lim_aux_data_map);
2542 VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
2543 htab_delete (memory_accesses.refs);
2545 for (i = 0; VEC_iterate (bitmap, memory_accesses.refs_in_loop, i, b); i++)
2547 VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
2549 for (i = 0; VEC_iterate (bitmap, memory_accesses.all_refs_in_loop, i, b); i++)
2551 VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
2553 for (i = 0; VEC_iterate (bitmap, memory_accesses.clobbered_vops, i, b); i++)
2555 VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
2557 for (i = 0; VEC_iterate (htab_t, memory_accesses.vop_ref_map, i, h); i++)
2559 VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
2561 if (memory_accesses.ttae_cache)
2562 pointer_map_destroy (memory_accesses.ttae_cache);
2565 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2566 i.e. those that are likely to be win regardless of the register pressure. */
2573 tree_ssa_lim_initialize ();
2575 /* Gathers information about memory accesses in the loops. */
2576 analyze_memory_references ();
2578 /* For each statement determine the outermost loop in that it is
2579 invariant and cost for computing the invariant. */
2580 determine_invariantness ();
2582 /* Execute store motion. Force the necessary invariants to be moved
2583 out of the loops as well. */
2586 /* Move the expressions that are expensive enough. */
2587 todo = move_computations ();
2589 tree_ssa_lim_finalize ();