1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
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"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
42 #include "tree-affine.h"
43 #include "pointer-set.h"
44 #include "tree-ssa-propagate.h"
46 /* TODO: Support for predicated code motion. I.e.
57 Where COND and INV are is invariants, but evaluating INV may trap or be
58 invalid from some other reason if !COND. This may be transformed to
68 /* A type for the list of statements that have to be moved in order to be able
69 to hoist an invariant computation. */
77 /* The auxiliary data kept for each statement. */
81 struct loop *max_loop; /* The outermost loop in that the statement
84 struct loop *tgt_loop; /* The loop out of that we want to move the
87 struct loop *always_executed_in;
88 /* The outermost loop for that we are sure
89 the statement is executed if the loop
92 unsigned cost; /* Cost of the computation performed by the
95 struct depend *depends; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
102 /* Maps statements to their lim_aux_data. */
104 static struct pointer_map_t *lim_aux_data_map;
106 /* Description of a memory reference location. */
108 typedef struct mem_ref_loc
110 tree *ref; /* The reference itself. */
111 gimple stmt; /* The statement in that it occurs. */
114 DEF_VEC_P(mem_ref_loc_p);
115 DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
117 /* The list of memory reference locations in a loop. */
119 typedef struct mem_ref_locs
121 VEC (mem_ref_loc_p, heap) *locs;
124 DEF_VEC_P(mem_ref_locs_p);
125 DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
127 /* Description of a memory reference. */
129 typedef struct mem_ref
131 tree mem; /* The memory itself. */
132 unsigned id; /* ID assigned to the memory reference
133 (its index in memory_accesses.refs_list) */
134 hashval_t hash; /* Its hash value. */
135 bitmap stored; /* The set of loops in that this memory location
137 VEC (mem_ref_locs_p, heap) *accesses_in_loop;
138 /* The locations of the accesses. Vector
139 indexed by the loop number. */
140 bitmap vops; /* Vops corresponding to this memory
143 /* The following sets are computed on demand. We keep both set and
144 its complement, so that we know whether the information was
145 already computed or not. */
146 bitmap indep_loop; /* The set of loops in that the memory
147 reference is independent, meaning:
148 If it is stored in the loop, this store
149 is independent on all other loads and
151 If it is only loaded, then it is independent
152 on all stores in the loop. */
153 bitmap dep_loop; /* The complement of INDEP_LOOP. */
155 bitmap indep_ref; /* The set of memory references on that
156 this reference is independent. */
157 bitmap dep_ref; /* The complement of DEP_REF. */
160 DEF_VEC_P(mem_ref_p);
161 DEF_VEC_ALLOC_P(mem_ref_p, heap);
164 DEF_VEC_ALLOC_P(bitmap, heap);
167 DEF_VEC_ALLOC_P(htab_t, heap);
169 /* Description of memory accesses in loops. */
173 /* The hash table of memory references accessed in loops. */
176 /* The list of memory references. */
177 VEC (mem_ref_p, heap) *refs_list;
179 /* The set of memory references accessed in each loop. */
180 VEC (bitmap, heap) *refs_in_loop;
182 /* The set of memory references accessed in each loop, including
184 VEC (bitmap, heap) *all_refs_in_loop;
186 /* The set of virtual operands clobbered in a given loop. */
187 VEC (bitmap, heap) *clobbered_vops;
189 /* Map from the pair (loop, virtual operand) to the set of refs that
190 touch the virtual operand in the loop. */
191 VEC (htab_t, heap) *vop_ref_map;
193 /* Cache for expanding memory addresses. */
194 struct pointer_map_t *ttae_cache;
197 static bool ref_indep_loop_p (struct loop *, mem_ref_p);
199 /* Minimum cost of an expensive expression. */
200 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
202 /* The outermost loop for that execution of the header guarantees that the
203 block will be executed. */
204 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
206 static struct lim_aux_data *
207 init_lim_data (gimple stmt)
209 void **p = pointer_map_insert (lim_aux_data_map, stmt);
211 *p = XCNEW (struct lim_aux_data);
212 return (struct lim_aux_data *) *p;
215 static struct lim_aux_data *
216 get_lim_data (gimple stmt)
218 void **p = pointer_map_contains (lim_aux_data_map, stmt);
222 return (struct lim_aux_data *) *p;
225 /* Releases the memory occupied by DATA. */
228 free_lim_aux_data (struct lim_aux_data *data)
230 struct depend *dep, *next;
232 for (dep = data->depends; dep; dep = next)
241 clear_lim_data (gimple stmt)
243 void **p = pointer_map_contains (lim_aux_data_map, stmt);
247 free_lim_aux_data ((struct lim_aux_data *) *p);
251 /* Calls CBCK for each index in memory reference ADDR_P. There are two
252 kinds situations handled; in each of these cases, the memory reference
253 and DATA are passed to the callback:
255 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
256 pass the pointer to the index to the callback.
258 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
259 pointer to addr to the callback.
261 If the callback returns false, the whole search stops and false is returned.
262 Otherwise the function returns true after traversing through the whole
263 reference *ADDR_P. */
266 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
270 for (; ; addr_p = nxt)
272 switch (TREE_CODE (*addr_p))
275 return cbck (*addr_p, addr_p, data);
277 case MISALIGNED_INDIRECT_REF:
278 case ALIGN_INDIRECT_REF:
280 nxt = &TREE_OPERAND (*addr_p, 0);
281 return cbck (*addr_p, nxt, data);
284 case VIEW_CONVERT_EXPR:
287 nxt = &TREE_OPERAND (*addr_p, 0);
291 /* If the component has varying offset, it behaves like index
293 idx = &TREE_OPERAND (*addr_p, 2);
295 && !cbck (*addr_p, idx, data))
298 nxt = &TREE_OPERAND (*addr_p, 0);
302 case ARRAY_RANGE_REF:
303 nxt = &TREE_OPERAND (*addr_p, 0);
304 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
321 gcc_assert (is_gimple_min_invariant (*addr_p));
325 idx = &TMR_BASE (*addr_p);
327 && !cbck (*addr_p, idx, data))
329 idx = &TMR_INDEX (*addr_p);
331 && !cbck (*addr_p, idx, data))
341 /* If it is possible to hoist the statement STMT unconditionally,
342 returns MOVE_POSSIBLE.
343 If it is possible to hoist the statement STMT, but we must avoid making
344 it executed if it would not be executed in the original program (e.g.
345 because it may trap), return MOVE_PRESERVE_EXECUTION.
346 Otherwise return MOVE_IMPOSSIBLE. */
349 movement_possibility (gimple stmt)
352 enum move_pos ret = MOVE_POSSIBLE;
354 if (flag_unswitch_loops
355 && gimple_code (stmt) == GIMPLE_COND)
357 /* If we perform unswitching, force the operands of the invariant
358 condition to be moved out of the loop. */
359 return MOVE_POSSIBLE;
362 if (gimple_get_lhs (stmt) == NULL_TREE)
363 return MOVE_IMPOSSIBLE;
365 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
366 return MOVE_IMPOSSIBLE;
368 if (stmt_ends_bb_p (stmt)
369 || gimple_has_volatile_ops (stmt)
370 || gimple_has_side_effects (stmt)
371 || stmt_could_throw_p (stmt))
372 return MOVE_IMPOSSIBLE;
374 if (is_gimple_call (stmt))
376 /* While pure or const call is guaranteed to have no side effects, we
377 cannot move it arbitrarily. Consider code like
379 char *s = something ();
389 Here the strlen call cannot be moved out of the loop, even though
390 s is invariant. In addition to possibly creating a call with
391 invalid arguments, moving out a function call that is not executed
392 may cause performance regressions in case the call is costly and
393 not executed at all. */
394 ret = MOVE_PRESERVE_EXECUTION;
395 lhs = gimple_call_lhs (stmt);
397 else if (is_gimple_assign (stmt))
398 lhs = gimple_assign_lhs (stmt);
400 return MOVE_IMPOSSIBLE;
402 if (TREE_CODE (lhs) == SSA_NAME
403 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
404 return MOVE_IMPOSSIBLE;
406 if (TREE_CODE (lhs) != SSA_NAME
407 || gimple_could_trap_p (stmt))
408 return MOVE_PRESERVE_EXECUTION;
413 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
414 loop to that we could move the expression using DEF if it did not have
415 other operands, i.e. the outermost loop enclosing LOOP in that the value
416 of DEF is invariant. */
419 outermost_invariant_loop (tree def, struct loop *loop)
423 struct loop *max_loop;
424 struct lim_aux_data *lim_data;
427 return superloop_at_depth (loop, 1);
429 if (TREE_CODE (def) != SSA_NAME)
431 gcc_assert (is_gimple_min_invariant (def));
432 return superloop_at_depth (loop, 1);
435 def_stmt = SSA_NAME_DEF_STMT (def);
436 def_bb = gimple_bb (def_stmt);
438 return superloop_at_depth (loop, 1);
440 max_loop = find_common_loop (loop, def_bb->loop_father);
442 lim_data = get_lim_data (def_stmt);
443 if (lim_data != NULL && lim_data->max_loop != NULL)
444 max_loop = find_common_loop (max_loop,
445 loop_outer (lim_data->max_loop));
446 if (max_loop == loop)
448 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
453 /* DATA is a structure containing information associated with a statement
454 inside LOOP. DEF is one of the operands of this statement.
456 Find the outermost loop enclosing LOOP in that value of DEF is invariant
457 and record this in DATA->max_loop field. If DEF itself is defined inside
458 this loop as well (i.e. we need to hoist it out of the loop if we want
459 to hoist the statement represented by DATA), record the statement in that
460 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
461 add the cost of the computation of DEF to the DATA->cost.
463 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
466 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
469 gimple def_stmt = SSA_NAME_DEF_STMT (def);
470 basic_block def_bb = gimple_bb (def_stmt);
471 struct loop *max_loop;
473 struct lim_aux_data *def_data;
478 max_loop = outermost_invariant_loop (def, loop);
482 if (flow_loop_nested_p (data->max_loop, max_loop))
483 data->max_loop = max_loop;
485 def_data = get_lim_data (def_stmt);
490 /* Only add the cost if the statement defining DEF is inside LOOP,
491 i.e. if it is likely that by moving the invariants dependent
492 on it, we will be able to avoid creating a new register for
493 it (since it will be only used in these dependent invariants). */
494 && def_bb->loop_father == loop)
495 data->cost += def_data->cost;
497 dep = XNEW (struct depend);
498 dep->stmt = def_stmt;
499 dep->next = data->depends;
505 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
506 are just ad-hoc constants. The estimates should be based on target-specific
510 stmt_cost (gimple stmt)
515 /* Always try to create possibilities for unswitching. */
516 if (gimple_code (stmt) == GIMPLE_COND)
517 return LIM_EXPENSIVE;
519 /* Hoisting memory references out should almost surely be a win. */
520 if (gimple_references_memory_p (stmt))
523 if (is_gimple_call (stmt))
525 /* We should be hoisting calls if possible. */
527 /* Unless the call is a builtin_constant_p; this always folds to a
528 constant, so moving it is useless. */
529 fndecl = gimple_call_fndecl (stmt);
531 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
532 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
538 if (gimple_code (stmt) != GIMPLE_ASSIGN)
541 switch (gimple_assign_rhs_code (stmt))
554 /* Division and multiplication are usually expensive. */
570 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
571 REF is independent. If REF is not independent in LOOP, NULL is returned
575 outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
579 if (bitmap_bit_p (ref->stored, loop->num))
584 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
585 if (!bitmap_bit_p (ref->stored, aloop->num)
586 && ref_indep_loop_p (aloop, ref))
589 if (ref_indep_loop_p (loop, ref))
595 /* If there is a simple load or store to a memory reference in STMT, returns
596 the location of the memory reference, and sets IS_STORE according to whether
597 it is a store or load. Otherwise, returns NULL. */
600 simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
605 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
606 if (gimple_code (stmt) != GIMPLE_ASSIGN)
609 code = gimple_assign_rhs_code (stmt);
611 lhs = gimple_assign_lhs_ptr (stmt);
613 if (TREE_CODE (*lhs) == SSA_NAME)
615 if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
616 || !is_gimple_addressable (gimple_assign_rhs1 (stmt)))
620 return gimple_assign_rhs1_ptr (stmt);
622 else if (code == SSA_NAME
623 || (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
624 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
633 /* Returns the memory reference contained in STMT. */
636 mem_ref_in_stmt (gimple stmt)
639 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
647 hash = iterative_hash_expr (*mem, 0);
648 ref = (mem_ref_p) htab_find_with_hash (memory_accesses.refs, *mem, hash);
650 gcc_assert (ref != NULL);
654 /* Determine the outermost loop to that it is possible to hoist a statement
655 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
656 the outermost loop in that the value computed by STMT is invariant.
657 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
658 we preserve the fact whether STMT is executed. It also fills other related
659 information to LIM_DATA (STMT).
661 The function returns false if STMT cannot be hoisted outside of the loop it
662 is defined in, and true otherwise. */
665 determine_max_movement (gimple stmt, bool must_preserve_exec)
667 basic_block bb = gimple_bb (stmt);
668 struct loop *loop = bb->loop_father;
670 struct lim_aux_data *lim_data = get_lim_data (stmt);
674 if (must_preserve_exec)
675 level = ALWAYS_EXECUTED_IN (bb);
677 level = superloop_at_depth (loop, 1);
678 lim_data->max_loop = level;
680 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
681 if (!add_dependency (val, lim_data, loop, true))
684 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
686 mem_ref_p ref = mem_ref_in_stmt (stmt);
691 = outermost_indep_loop (lim_data->max_loop, loop, ref);
692 if (!lim_data->max_loop)
697 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
699 if (!add_dependency (val, lim_data, loop, false))
705 lim_data->cost += stmt_cost (stmt);
710 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
711 and that one of the operands of this statement is computed by STMT.
712 Ensure that STMT (together with all the statements that define its
713 operands) is hoisted at least out of the loop LEVEL. */
716 set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
718 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
720 struct lim_aux_data *lim_data;
722 stmt_loop = find_common_loop (orig_loop, stmt_loop);
723 lim_data = get_lim_data (stmt);
724 if (lim_data != NULL && lim_data->tgt_loop != NULL)
725 stmt_loop = find_common_loop (stmt_loop,
726 loop_outer (lim_data->tgt_loop));
727 if (flow_loop_nested_p (stmt_loop, level))
730 gcc_assert (level == lim_data->max_loop
731 || flow_loop_nested_p (lim_data->max_loop, level));
733 lim_data->tgt_loop = level;
734 for (dep = lim_data->depends; dep; dep = dep->next)
735 set_level (dep->stmt, orig_loop, level);
738 /* Determines an outermost loop from that we want to hoist the statement STMT.
739 For now we chose the outermost possible loop. TODO -- use profiling
740 information to set it more sanely. */
743 set_profitable_level (gimple stmt)
745 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
748 /* Returns true if STMT is a call that has side effects. */
751 nonpure_call_p (gimple stmt)
753 if (gimple_code (stmt) != GIMPLE_CALL)
756 return gimple_has_side_effects (stmt);
759 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
762 rewrite_reciprocal (gimple_stmt_iterator *bsi)
764 gimple stmt, stmt1, stmt2;
765 tree var, name, lhs, type;
767 stmt = gsi_stmt (*bsi);
768 lhs = gimple_assign_lhs (stmt);
769 type = TREE_TYPE (lhs);
771 var = create_tmp_var (type, "reciptmp");
772 add_referenced_var (var);
774 stmt1 = gimple_build_assign_with_ops (RDIV_EXPR,
775 var, build_real (type, dconst1), gimple_assign_rhs2 (stmt));
776 name = make_ssa_name (var, stmt1);
777 gimple_assign_set_lhs (stmt1, name);
779 stmt2 = gimple_build_assign_with_ops (MULT_EXPR, lhs, name,
780 gimple_assign_rhs1 (stmt));
782 /* Replace division stmt with reciprocal and multiply stmts.
783 The multiply stmt is not invariant, so update iterator
784 and avoid rescanning. */
785 gsi_replace (bsi, stmt1, true);
786 gsi_insert_after (bsi, stmt2, GSI_NEW_STMT);
788 /* Continue processing with invariant reciprocal statement. */
792 /* Check if the pattern at *BSI is a bittest of the form
793 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
796 rewrite_bittest (gimple_stmt_iterator *bsi)
798 gimple stmt, use_stmt, stmt1, stmt2;
799 tree lhs, var, name, t, a, b;
802 stmt = gsi_stmt (*bsi);
803 lhs = gimple_assign_lhs (stmt);
805 /* Verify that the single use of lhs is a comparison against zero. */
806 if (TREE_CODE (lhs) != SSA_NAME
807 || !single_imm_use (lhs, &use, &use_stmt)
808 || gimple_code (use_stmt) != GIMPLE_COND)
810 if (gimple_cond_lhs (use_stmt) != lhs
811 || (gimple_cond_code (use_stmt) != NE_EXPR
812 && gimple_cond_code (use_stmt) != EQ_EXPR)
813 || !integer_zerop (gimple_cond_rhs (use_stmt)))
816 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
817 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
818 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
821 /* There is a conversion in between possibly inserted by fold. */
822 if (gimple_assign_rhs_code (stmt1) == NOP_EXPR
823 || gimple_assign_rhs_code (stmt1) == CONVERT_EXPR)
825 t = gimple_assign_rhs1 (stmt1);
826 if (TREE_CODE (t) != SSA_NAME
827 || !has_single_use (t))
829 stmt1 = SSA_NAME_DEF_STMT (t);
830 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
834 /* Verify that B is loop invariant but A is not. Verify that with
835 all the stmt walking we are still in the same loop. */
836 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
837 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
840 a = gimple_assign_rhs1 (stmt1);
841 b = gimple_assign_rhs2 (stmt1);
843 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
844 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
847 var = create_tmp_var (TREE_TYPE (a), "shifttmp");
848 add_referenced_var (var);
849 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
850 build_int_cst (TREE_TYPE (a), 1), b);
851 stmt1 = gimple_build_assign (var, t);
852 name = make_ssa_name (var, stmt1);
853 gimple_assign_set_lhs (stmt1, name);
856 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
857 stmt2 = gimple_build_assign (var, t);
858 name = make_ssa_name (var, stmt2);
859 gimple_assign_set_lhs (stmt2, name);
861 /* Replace the SSA_NAME we compare against zero. Adjust
862 the type of zero accordingly. */
864 gimple_cond_set_rhs (use_stmt, build_int_cst_type (TREE_TYPE (name), 0));
866 gsi_insert_before (bsi, stmt1, GSI_SAME_STMT);
867 gsi_replace (bsi, stmt2, true);
876 /* Determine the outermost loops in that statements in basic block BB are
877 invariant, and record them to the LIM_DATA associated with the statements.
878 Callback for walk_dominator_tree. */
881 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
885 gimple_stmt_iterator bsi;
887 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
888 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
889 struct lim_aux_data *lim_data;
891 if (!loop_outer (bb->loop_father))
894 if (dump_file && (dump_flags & TDF_DETAILS))
895 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
896 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
898 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
900 stmt = gsi_stmt (bsi);
902 pos = movement_possibility (stmt);
903 if (pos == MOVE_IMPOSSIBLE)
905 if (nonpure_call_p (stmt))
910 /* Make sure to note always_executed_in for stores to make
911 store-motion work. */
912 else if (stmt_makes_single_store (stmt))
914 struct lim_aux_data *lim_data = init_lim_data (stmt);
915 lim_data->always_executed_in = outermost;
920 if (is_gimple_assign (stmt)
921 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
922 == GIMPLE_BINARY_RHS))
924 tree op0 = gimple_assign_rhs1 (stmt);
925 tree op1 = gimple_assign_rhs2 (stmt);
926 struct loop *ol1 = outermost_invariant_loop (op1,
927 loop_containing_stmt (stmt));
929 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
930 to be hoisted out of loop, saving expensive divide. */
931 if (pos == MOVE_POSSIBLE
932 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
933 && flag_unsafe_math_optimizations
934 && !flag_trapping_math
936 && outermost_invariant_loop (op0, ol1) == NULL)
937 stmt = rewrite_reciprocal (&bsi);
939 /* If the shift count is invariant, convert (A >> B) & 1 to
940 A & (1 << B) allowing the bit mask to be hoisted out of the loop
941 saving an expensive shift. */
942 if (pos == MOVE_POSSIBLE
943 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
944 && integer_onep (op1)
945 && TREE_CODE (op0) == SSA_NAME
946 && has_single_use (op0))
947 stmt = rewrite_bittest (&bsi);
950 lim_data = init_lim_data (stmt);
951 lim_data->always_executed_in = outermost;
953 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
956 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
958 lim_data->max_loop = NULL;
962 if (dump_file && (dump_flags & TDF_DETAILS))
964 print_gimple_stmt (dump_file, stmt, 2, 0);
965 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
966 loop_depth (lim_data->max_loop),
970 if (lim_data->cost >= LIM_EXPENSIVE)
971 set_profitable_level (stmt);
975 /* For each statement determines the outermost loop in that it is invariant,
976 statements on whose motion it depends and the cost of the computation.
977 This information is stored to the LIM_DATA structure associated with
981 determine_invariantness (void)
983 struct dom_walk_data walk_data;
985 memset (&walk_data, 0, sizeof (struct dom_walk_data));
986 walk_data.dom_direction = CDI_DOMINATORS;
987 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
989 init_walk_dominator_tree (&walk_data);
990 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
991 fini_walk_dominator_tree (&walk_data);
994 /* Hoist the statements in basic block BB out of the loops prescribed by
995 data stored in LIM_DATA structures associated with each statement. Callback
996 for walk_dominator_tree. */
999 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
1003 gimple_stmt_iterator bsi;
1006 struct lim_aux_data *lim_data;
1008 if (!loop_outer (bb->loop_father))
1011 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1013 stmt = gsi_stmt (bsi);
1015 lim_data = get_lim_data (stmt);
1016 if (lim_data == NULL)
1022 cost = lim_data->cost;
1023 level = lim_data->tgt_loop;
1024 clear_lim_data (stmt);
1032 /* We do not really want to move conditionals out of the loop; we just
1033 placed it here to force its operands to be moved if necessary. */
1034 if (gimple_code (stmt) == GIMPLE_COND)
1037 if (dump_file && (dump_flags & TDF_DETAILS))
1039 fprintf (dump_file, "Moving statement\n");
1040 print_gimple_stmt (dump_file, stmt, 0, 0);
1041 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1045 mark_virtual_ops_for_renaming (stmt);
1046 gsi_insert_on_edge (loop_preheader_edge (level), stmt);
1047 gsi_remove (&bsi, false);
1051 /* Hoist the statements out of the loops prescribed by data stored in
1052 LIM_DATA structures associated with each statement.*/
1055 move_computations (void)
1057 struct dom_walk_data walk_data;
1059 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1060 walk_data.dom_direction = CDI_DOMINATORS;
1061 walk_data.before_dom_children_before_stmts = move_computations_stmt;
1063 init_walk_dominator_tree (&walk_data);
1064 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1065 fini_walk_dominator_tree (&walk_data);
1067 gsi_commit_edge_inserts ();
1068 if (need_ssa_update_p ())
1069 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1072 /* Checks whether the statement defining variable *INDEX can be hoisted
1073 out of the loop passed in DATA. Callback for for_each_index. */
1076 may_move_till (tree ref, tree *index, void *data)
1078 struct loop *loop = (struct loop *) data, *max_loop;
1080 /* If REF is an array reference, check also that the step and the lower
1081 bound is invariant in LOOP. */
1082 if (TREE_CODE (ref) == ARRAY_REF)
1084 tree step = TREE_OPERAND (ref, 3);
1085 tree lbound = TREE_OPERAND (ref, 2);
1087 max_loop = outermost_invariant_loop (step, loop);
1091 max_loop = outermost_invariant_loop (lbound, loop);
1096 max_loop = outermost_invariant_loop (*index, loop);
1103 /* If OP is SSA NAME, force the statement that defines it to be
1104 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1107 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1112 || is_gimple_min_invariant (op))
1115 gcc_assert (TREE_CODE (op) == SSA_NAME);
1117 stmt = SSA_NAME_DEF_STMT (op);
1118 if (gimple_nop_p (stmt))
1121 set_level (stmt, orig_loop, loop);
1124 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1125 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1131 struct loop *orig_loop;
1135 force_move_till (tree ref, tree *index, void *data)
1137 struct fmt_data *fmt_data = (struct fmt_data *) data;
1139 if (TREE_CODE (ref) == ARRAY_REF)
1141 tree step = TREE_OPERAND (ref, 3);
1142 tree lbound = TREE_OPERAND (ref, 2);
1144 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1145 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1148 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1153 /* A hash function for struct mem_ref object OBJ. */
1156 memref_hash (const void *obj)
1158 const struct mem_ref *const mem = (const struct mem_ref *) obj;
1163 /* An equality function for struct mem_ref object OBJ1 with
1164 memory reference OBJ2. */
1167 memref_eq (const void *obj1, const void *obj2)
1169 const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
1171 return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
1174 /* Releases list of memory reference locations ACCS. */
1177 free_mem_ref_locs (mem_ref_locs_p accs)
1185 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1187 VEC_free (mem_ref_loc_p, heap, accs->locs);
1191 /* A function to free the mem_ref object OBJ. */
1194 memref_free (void *obj)
1196 struct mem_ref *const mem = (struct mem_ref *) obj;
1198 mem_ref_locs_p accs;
1200 BITMAP_FREE (mem->stored);
1201 BITMAP_FREE (mem->indep_loop);
1202 BITMAP_FREE (mem->dep_loop);
1203 BITMAP_FREE (mem->indep_ref);
1204 BITMAP_FREE (mem->dep_ref);
1206 for (i = 0; VEC_iterate (mem_ref_locs_p, mem->accesses_in_loop, i, accs); i++)
1207 free_mem_ref_locs (accs);
1208 VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
1210 BITMAP_FREE (mem->vops);
1214 /* Allocates and returns a memory reference description for MEM whose hash
1215 value is HASH and id is ID. */
1218 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1220 mem_ref_p ref = XNEW (struct mem_ref);
1224 ref->stored = BITMAP_ALLOC (NULL);
1225 ref->indep_loop = BITMAP_ALLOC (NULL);
1226 ref->dep_loop = BITMAP_ALLOC (NULL);
1227 ref->indep_ref = BITMAP_ALLOC (NULL);
1228 ref->dep_ref = BITMAP_ALLOC (NULL);
1229 ref->accesses_in_loop = NULL;
1230 ref->vops = BITMAP_ALLOC (NULL);
1235 /* Allocates and returns the new list of locations. */
1237 static mem_ref_locs_p
1238 mem_ref_locs_alloc (void)
1240 mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
1245 /* Records memory reference location *LOC in LOOP to the memory reference
1246 description REF. The reference occurs in statement STMT. */
1249 record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
1251 mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
1252 mem_ref_locs_p accs;
1253 bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1255 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1256 <= (unsigned) loop->num)
1257 VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
1259 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1262 accs = mem_ref_locs_alloc ();
1263 VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
1269 VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
1270 bitmap_set_bit (ril, ref->id);
1273 /* Marks reference REF as stored in LOOP. */
1276 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1279 loop != current_loops->tree_root
1280 && !bitmap_bit_p (ref->stored, loop->num);
1281 loop = loop_outer (loop))
1282 bitmap_set_bit (ref->stored, loop->num);
1285 /* Gathers memory references in statement STMT in LOOP, storing the
1286 information about them in the memory_accesses structure. Marks
1287 the vops accessed through unrecognized statements there as
1291 gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1303 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1306 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1310 hash = iterative_hash_expr (*mem, 0);
1311 slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
1315 ref = (mem_ref_p) *slot;
1320 id = VEC_length (mem_ref_p, memory_accesses.refs_list);
1321 ref = mem_ref_alloc (*mem, hash, id);
1322 VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
1325 if (dump_file && (dump_flags & TDF_DETAILS))
1327 fprintf (dump_file, "Memory reference %u: ", id);
1328 print_generic_expr (dump_file, ref->mem, TDF_SLIM);
1329 fprintf (dump_file, "\n");
1333 mark_ref_stored (ref, loop);
1335 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1336 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1337 record_mem_ref_loc (ref, loop, stmt, mem);
1341 clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1342 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1343 bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
1346 /* Gathers memory references in loops. */
1349 gather_mem_refs_in_loops (void)
1351 gimple_stmt_iterator bsi;
1356 bitmap lrefs, alrefs, alrefso;
1360 loop = bb->loop_father;
1361 if (loop == current_loops->tree_root)
1364 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1365 gather_mem_refs_stmt (loop, gsi_stmt (bsi));
1368 /* Propagate the information about clobbered vops and accessed memory
1369 references up the loop hierarchy. */
1370 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1372 lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1373 alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
1374 bitmap_ior_into (alrefs, lrefs);
1376 if (loop_outer (loop) == current_loops->tree_root)
1379 clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1380 clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
1381 loop_outer (loop)->num);
1382 bitmap_ior_into (clvo, clvi);
1384 alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1385 loop_outer (loop)->num);
1386 bitmap_ior_into (alrefso, alrefs);
1390 /* Element of the hash table that maps vops to memory references. */
1392 struct vop_to_refs_elt
1394 /* DECL_UID of the vop. */
1397 /* List of the all references. */
1400 /* List of stored references. */
1404 /* A hash function for struct vop_to_refs_elt object OBJ. */
1407 vtoe_hash (const void *obj)
1409 const struct vop_to_refs_elt *const vtoe =
1410 (const struct vop_to_refs_elt *) obj;
1415 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1416 uid of a vop OBJ2. */
1419 vtoe_eq (const void *obj1, const void *obj2)
1421 const struct vop_to_refs_elt *const vtoe =
1422 (const struct vop_to_refs_elt *) obj1;
1423 const unsigned *const uid = (const unsigned *) obj2;
1425 return vtoe->uid == *uid;
1428 /* A function to free the struct vop_to_refs_elt object. */
1431 vtoe_free (void *obj)
1433 struct vop_to_refs_elt *const vtoe =
1434 (struct vop_to_refs_elt *) obj;
1436 BITMAP_FREE (vtoe->refs_all);
1437 BITMAP_FREE (vtoe->refs_stored);
1441 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1442 if the reference REF is stored. */
1445 record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool stored)
1447 void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
1448 struct vop_to_refs_elt *vtoe;
1452 vtoe = XNEW (struct vop_to_refs_elt);
1454 vtoe->refs_all = BITMAP_ALLOC (NULL);
1455 vtoe->refs_stored = BITMAP_ALLOC (NULL);
1459 vtoe = (struct vop_to_refs_elt *) *slot;
1461 bitmap_set_bit (vtoe->refs_all, ref);
1463 bitmap_set_bit (vtoe->refs_stored, ref);
1466 /* Returns the set of references that access VOP according to the table
1470 get_vop_accesses (htab_t vop_to_refs, unsigned vop)
1472 struct vop_to_refs_elt *const vtoe =
1473 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1474 return vtoe->refs_all;
1477 /* Returns the set of stores that access VOP according to the table
1481 get_vop_stores (htab_t vop_to_refs, unsigned vop)
1483 struct vop_to_refs_elt *const vtoe =
1484 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1485 return vtoe->refs_stored;
1488 /* Adds REF to mapping from virtual operands to references in LOOP. */
1491 add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
1493 htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1494 bool stored = bitmap_bit_p (ref->stored, loop->num);
1495 bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
1500 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
1502 record_vop_access (map, vop, ref->id, stored);
1506 /* Create a mapping from virtual operands to references that touch them
1510 create_vop_ref_mapping_loop (struct loop *loop)
1512 bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1518 EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
1520 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1521 for (sloop = loop; sloop != current_loops->tree_root; sloop = loop_outer (sloop))
1522 add_vop_ref_mapping (sloop, ref);
1526 /* For each non-clobbered virtual operand and each loop, record the memory
1527 references in this loop that touch the operand. */
1530 create_vop_ref_mapping (void)
1535 FOR_EACH_LOOP (li, loop, 0)
1537 create_vop_ref_mapping_loop (loop);
1541 /* Gathers information about memory accesses in the loops. */
1544 analyze_memory_references (void)
1550 memory_accesses.refs
1551 = htab_create (100, memref_hash, memref_eq, memref_free);
1552 memory_accesses.refs_list = NULL;
1553 memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
1554 number_of_loops ());
1555 memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
1556 number_of_loops ());
1557 memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
1558 number_of_loops ());
1559 memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
1560 number_of_loops ());
1562 for (i = 0; i < number_of_loops (); i++)
1564 empty = BITMAP_ALLOC (NULL);
1565 VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
1566 empty = BITMAP_ALLOC (NULL);
1567 VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
1568 empty = BITMAP_ALLOC (NULL);
1569 VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
1570 hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
1571 VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
1574 memory_accesses.ttae_cache = NULL;
1576 gather_mem_refs_in_loops ();
1577 create_vop_ref_mapping ();
1580 /* Returns true if a region of size SIZE1 at position 0 and a region of
1581 size SIZE2 at position DIFF cannot overlap. */
1584 cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
1586 double_int d, bound;
1588 /* Unless the difference is a constant, we fail. */
1593 if (double_int_negative_p (d))
1595 /* The second object is before the first one, we succeed if the last
1596 element of the second object is before the start of the first one. */
1597 bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
1598 return double_int_negative_p (bound);
1602 /* We succeed if the second object starts after the first one ends. */
1603 return double_int_scmp (size1, d) <= 0;
1607 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1608 tree_to_aff_combination_expand. */
1611 mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
1613 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1614 object and their offset differ in such a way that the locations cannot
1615 overlap, then they cannot alias. */
1616 double_int size1, size2;
1617 aff_tree off1, off2;
1619 /* Perform basic offset and type-based disambiguation. */
1620 if (!refs_may_alias_p (mem1, mem2))
1623 /* The expansion of addresses may be a bit expensive, thus we only do
1624 the check at -O2 and higher optimization levels. */
1628 get_inner_reference_aff (mem1, &off1, &size1);
1629 get_inner_reference_aff (mem2, &off2, &size2);
1630 aff_combination_expand (&off1, ttae_cache);
1631 aff_combination_expand (&off2, ttae_cache);
1632 aff_combination_scale (&off1, double_int_minus_one);
1633 aff_combination_add (&off2, &off1);
1635 if (cannot_overlap_p (&off2, size1, size2))
1641 /* Rewrites location LOC by TMP_VAR. */
1644 rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
1646 mark_virtual_ops_for_renaming (loc->stmt);
1647 *loc->ref = tmp_var;
1648 update_stmt (loc->stmt);
1651 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1654 get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
1655 VEC (mem_ref_loc_p, heap) **locs)
1657 mem_ref_locs_p accs;
1660 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1662 struct loop *subloop;
1664 if (!bitmap_bit_p (refs, ref->id))
1667 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1668 > (unsigned) loop->num)
1670 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1673 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1674 VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
1678 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1679 get_all_locs_in_loop (subloop, ref, locs);
1682 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1685 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1689 VEC (mem_ref_loc_p, heap) *locs = NULL;
1691 get_all_locs_in_loop (loop, ref, &locs);
1692 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1693 rewrite_mem_ref_loc (loc, tmp_var);
1694 VEC_free (mem_ref_loc_p, heap, locs);
1697 /* The name and the length of the currently generated variable
1699 #define MAX_LSM_NAME_LENGTH 40
1700 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1701 static int lsm_tmp_name_length;
1703 /* Adds S to lsm_tmp_name. */
1706 lsm_tmp_name_add (const char *s)
1708 int l = strlen (s) + lsm_tmp_name_length;
1709 if (l > MAX_LSM_NAME_LENGTH)
1712 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1713 lsm_tmp_name_length = l;
1716 /* Stores the name for temporary variable that replaces REF to
1720 gen_lsm_tmp_name (tree ref)
1724 switch (TREE_CODE (ref))
1726 case MISALIGNED_INDIRECT_REF:
1727 case ALIGN_INDIRECT_REF:
1729 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1730 lsm_tmp_name_add ("_");
1734 case VIEW_CONVERT_EXPR:
1735 case ARRAY_RANGE_REF:
1736 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1740 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1741 lsm_tmp_name_add ("_RE");
1745 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1746 lsm_tmp_name_add ("_IM");
1750 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1751 lsm_tmp_name_add ("_");
1752 name = get_name (TREE_OPERAND (ref, 1));
1755 lsm_tmp_name_add ("_");
1756 lsm_tmp_name_add (name);
1759 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1760 lsm_tmp_name_add ("_I");
1764 ref = SSA_NAME_VAR (ref);
1769 name = get_name (ref);
1772 lsm_tmp_name_add (name);
1776 lsm_tmp_name_add ("S");
1780 lsm_tmp_name_add ("R");
1788 /* Determines name for temporary variable that replaces REF.
1789 The name is accumulated into the lsm_tmp_name variable.
1790 N is added to the name of the temporary. */
1793 get_lsm_tmp_name (tree ref, unsigned n)
1797 lsm_tmp_name_length = 0;
1798 gen_lsm_tmp_name (ref);
1799 lsm_tmp_name_add ("_lsm");
1804 lsm_tmp_name_add (ns);
1806 return lsm_tmp_name;
1809 /* Executes store motion of memory reference REF from LOOP.
1810 Exits from the LOOP are stored in EXITS. The initialization of the
1811 temporary variable is put to the preheader of the loop, and assignments
1812 to the reference from the temporary variable are emitted to exits. */
1815 execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
1820 struct fmt_data fmt_data;
1822 struct lim_aux_data *lim_data;
1824 if (dump_file && (dump_flags & TDF_DETAILS))
1826 fprintf (dump_file, "Executing store motion of ");
1827 print_generic_expr (dump_file, ref->mem, 0);
1828 fprintf (dump_file, " from loop %d\n", loop->num);
1831 tmp_var = make_rename_temp (TREE_TYPE (ref->mem),
1832 get_lsm_tmp_name (ref->mem, ~0));
1834 fmt_data.loop = loop;
1835 fmt_data.orig_loop = loop;
1836 for_each_index (&ref->mem, force_move_till, &fmt_data);
1838 rewrite_mem_refs (loop, ref, tmp_var);
1840 /* Emit the load & stores. */
1841 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem));
1842 lim_data = init_lim_data (load);
1843 lim_data->max_loop = loop;
1844 lim_data->tgt_loop = loop;
1846 /* Put this into the latch, so that we are sure it will be processed after
1847 all dependencies. */
1848 gsi_insert_on_edge (loop_latch_edge (loop), load);
1850 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1852 store = gimple_build_assign (unshare_expr (ref->mem), tmp_var);
1853 gsi_insert_on_edge (ex, store);
1857 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
1858 edges of the LOOP. */
1861 hoist_memory_references (struct loop *loop, bitmap mem_refs,
1862 VEC (edge, heap) *exits)
1868 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
1870 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1871 execute_sm (loop, exits, ref);
1875 /* Returns true if REF is always accessed in LOOP. */
1878 ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
1880 VEC (mem_ref_loc_p, heap) *locs = NULL;
1884 struct loop *must_exec;
1886 get_all_locs_in_loop (loop, ref, &locs);
1887 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1889 if (!get_lim_data (loc->stmt))
1892 must_exec = get_lim_data (loc->stmt)->always_executed_in;
1896 if (must_exec == loop
1897 || flow_loop_nested_p (must_exec, loop))
1903 VEC_free (mem_ref_loc_p, heap, locs);
1908 /* Returns true if REF1 and REF2 are independent. */
1911 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
1914 || bitmap_bit_p (ref1->indep_ref, ref2->id))
1916 if (bitmap_bit_p (ref1->dep_ref, ref2->id))
1919 if (dump_file && (dump_flags & TDF_DETAILS))
1920 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
1921 ref1->id, ref2->id);
1923 if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
1924 &memory_accesses.ttae_cache))
1926 bitmap_set_bit (ref1->dep_ref, ref2->id);
1927 bitmap_set_bit (ref2->dep_ref, ref1->id);
1928 if (dump_file && (dump_flags & TDF_DETAILS))
1929 fprintf (dump_file, "dependent.\n");
1934 bitmap_set_bit (ref1->indep_ref, ref2->id);
1935 bitmap_set_bit (ref2->indep_ref, ref1->id);
1936 if (dump_file && (dump_flags & TDF_DETAILS))
1937 fprintf (dump_file, "independent.\n");
1942 /* Records the information whether REF is independent in LOOP (according
1946 record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
1949 bitmap_set_bit (ref->indep_loop, loop->num);
1951 bitmap_set_bit (ref->dep_loop, loop->num);
1954 /* Returns true if REF is independent on all other memory references in
1958 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
1960 bitmap clobbers, refs_to_check, refs;
1963 bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
1967 /* If the reference is clobbered, it is not independent. */
1968 clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1969 if (bitmap_intersect_p (ref->vops, clobbers))
1972 refs_to_check = BITMAP_ALLOC (NULL);
1974 map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1975 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
1978 refs = get_vop_accesses (map, i);
1980 refs = get_vop_stores (map, i);
1982 bitmap_ior_into (refs_to_check, refs);
1985 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
1987 aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1988 if (!refs_independent_p (ref, aref))
1991 record_indep_loop (loop, aref, false);
1996 BITMAP_FREE (refs_to_check);
2000 /* Returns true if REF is independent on all other memory references in
2001 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2004 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2008 if (bitmap_bit_p (ref->indep_loop, loop->num))
2010 if (bitmap_bit_p (ref->dep_loop, loop->num))
2013 ret = ref_indep_loop_p_1 (loop, ref);
2015 if (dump_file && (dump_flags & TDF_DETAILS))
2016 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2017 ref->id, loop->num, ret ? "independent" : "dependent");
2019 record_indep_loop (loop, ref, ret);
2024 /* Returns true if we can perform store motion of REF from LOOP. */
2027 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2029 /* Unless the reference is stored in the loop, there is nothing to do. */
2030 if (!bitmap_bit_p (ref->stored, loop->num))
2033 /* It should be movable. */
2034 if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
2035 || TREE_THIS_VOLATILE (ref->mem)
2036 || !for_each_index (&ref->mem, may_move_till, loop))
2039 /* If it can trap, it must be always executed in LOOP. */
2040 if (tree_could_trap_p (ref->mem)
2041 && !ref_always_accessed_p (loop, ref))
2044 /* And it must be independent on all other memory references
2046 if (!ref_indep_loop_p (loop, ref))
2052 /* Marks the references in LOOP for that store motion should be performed
2053 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2054 motion was performed in one of the outer loops. */
2057 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2059 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
2065 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2067 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2068 if (can_sm_ref_p (loop, ref))
2069 bitmap_set_bit (refs_to_sm, i);
2073 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2074 for a store motion optimization (i.e. whether we can insert statement
2078 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2079 VEC (edge, heap) *exits)
2084 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2085 if (ex->flags & EDGE_ABNORMAL)
2091 /* Try to perform store motion for all memory references modified inside
2092 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2093 store motion was executed in one of the outer loops. */
2096 store_motion_loop (struct loop *loop, bitmap sm_executed)
2098 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2099 struct loop *subloop;
2100 bitmap sm_in_loop = BITMAP_ALLOC (NULL);
2102 if (loop_suitable_for_sm (loop, exits))
2104 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2105 hoist_memory_references (loop, sm_in_loop, exits);
2107 VEC_free (edge, heap, exits);
2109 bitmap_ior_into (sm_executed, sm_in_loop);
2110 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2111 store_motion_loop (subloop, sm_executed);
2112 bitmap_and_compl_into (sm_executed, sm_in_loop);
2113 BITMAP_FREE (sm_in_loop);
2116 /* Try to perform store motion for all memory references modified inside
2123 bitmap sm_executed = BITMAP_ALLOC (NULL);
2125 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2126 store_motion_loop (loop, sm_executed);
2128 BITMAP_FREE (sm_executed);
2129 gsi_commit_edge_inserts ();
2132 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2133 for each such basic block bb records the outermost loop for that execution
2134 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2135 blocks that contain a nonpure call. */
2138 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
2140 basic_block bb = NULL, *bbs, last = NULL;
2143 struct loop *inn_loop = loop;
2145 if (!loop->header->aux)
2147 bbs = get_loop_body_in_dom_order (loop);
2149 for (i = 0; i < loop->num_nodes; i++)
2154 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2157 if (TEST_BIT (contains_call, bb->index))
2160 FOR_EACH_EDGE (e, ei, bb->succs)
2161 if (!flow_bb_inside_loop_p (loop, e->dest))
2166 /* A loop might be infinite (TODO use simple loop analysis
2167 to disprove this if possible). */
2168 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2171 if (!flow_bb_inside_loop_p (inn_loop, bb))
2174 if (bb->loop_father->header == bb)
2176 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2179 /* In a loop that is always entered we may proceed anyway.
2180 But record that we entered it and stop once we leave it. */
2181 inn_loop = bb->loop_father;
2188 if (last == loop->header)
2190 last = get_immediate_dominator (CDI_DOMINATORS, last);
2196 for (loop = loop->inner; loop; loop = loop->next)
2197 fill_always_executed_in (loop, contains_call);
2200 /* Compute the global information needed by the loop invariant motion pass. */
2203 tree_ssa_lim_initialize (void)
2205 sbitmap contains_call = sbitmap_alloc (last_basic_block);
2206 gimple_stmt_iterator bsi;
2210 sbitmap_zero (contains_call);
2213 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2215 if (nonpure_call_p (gsi_stmt (bsi)))
2219 if (!gsi_end_p (bsi))
2220 SET_BIT (contains_call, bb->index);
2223 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2224 fill_always_executed_in (loop, contains_call);
2226 sbitmap_free (contains_call);
2228 lim_aux_data_map = pointer_map_create ();
2231 /* Cleans up after the invariant motion pass. */
2234 tree_ssa_lim_finalize (void)
2246 pointer_map_destroy (lim_aux_data_map);
2248 VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
2249 htab_delete (memory_accesses.refs);
2251 for (i = 0; VEC_iterate (bitmap, memory_accesses.refs_in_loop, i, b); i++)
2253 VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
2255 for (i = 0; VEC_iterate (bitmap, memory_accesses.all_refs_in_loop, i, b); i++)
2257 VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
2259 for (i = 0; VEC_iterate (bitmap, memory_accesses.clobbered_vops, i, b); i++)
2261 VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
2263 for (i = 0; VEC_iterate (htab_t, memory_accesses.vop_ref_map, i, h); i++)
2265 VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
2267 if (memory_accesses.ttae_cache)
2268 pointer_map_destroy (memory_accesses.ttae_cache);
2271 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2272 i.e. those that are likely to be win regardless of the register pressure. */
2277 tree_ssa_lim_initialize ();
2279 /* Gathers information about memory accesses in the loops. */
2280 analyze_memory_references ();
2282 /* For each statement determine the outermost loop in that it is
2283 invariant and cost for computing the invariant. */
2284 determine_invariantness ();
2286 /* Execute store motion. Force the necessary invariants to be moved
2287 out of the loops as well. */
2290 /* Move the expressions that are expensive enough. */
2291 move_computations ();
2293 tree_ssa_lim_finalize ();