1 /* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
37 #include "tree-pass.h"
41 #include "tree-affine.h"
42 #include "pointer-set.h"
44 /* TODO: Support for predicated code motion. I.e.
55 Where COND and INV are is invariants, but evaluating INV may trap or be
56 invalid from some other reason if !COND. This may be transformed to
66 /* A type for the list of statements that have to be moved in order to be able
67 to hoist an invariant computation. */
75 /* The auxiliary data kept for each statement. */
79 struct loop *max_loop; /* The outermost loop in that the statement
82 struct loop *tgt_loop; /* The loop out of that we want to move the
85 struct loop *always_executed_in;
86 /* The outermost loop for that we are sure
87 the statement is executed if the loop
90 unsigned cost; /* Cost of the computation performed by the
93 struct depend *depends; /* List of statements that must be also hoisted
94 out of the loop when this statement is
95 hoisted; i.e. those that define the operands
96 of the statement and are inside of the
100 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
102 : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
104 /* Description of a memory reference location. */
106 typedef struct mem_ref_loc
108 tree *ref; /* The reference itself. */
109 tree stmt; /* The statement in that it occurs. */
112 DEF_VEC_P(mem_ref_loc_p);
113 DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
115 /* The list of memory reference locations in a loop. */
117 typedef struct mem_ref_locs
119 VEC (mem_ref_loc_p, heap) *locs;
122 DEF_VEC_P(mem_ref_locs_p);
123 DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
125 /* Description of a memory reference. */
127 typedef struct mem_ref
129 tree mem; /* The memory itself. */
130 unsigned id; /* ID assigned to the memory reference
131 (its index in memory_accesses.refs_list) */
132 hashval_t hash; /* Its hash value. */
133 bitmap stored; /* The set of loops in that this memory locatio
135 VEC (mem_ref_locs_p, heap) *accesses_in_loop;
136 /* The locations of the accesses. Vector
137 indexed by the loop number. */
138 bitmap vops; /* Vops corresponding to this memory
141 /* The following sets are computed on demand. We keep both set and
142 its complement, so that we know whether the information was
143 already computed or not. */
144 bitmap indep_loop; /* The set of loops in that the memory
145 reference is independent, meaning:
146 If it is stored in the loop, this store
147 is independent on all other loads and
149 If it is only loaded, then it is independent
150 on all stores in the loop. */
151 bitmap dep_loop; /* The complement of INDEP_LOOP. */
153 bitmap indep_ref; /* The set of memory references on that
154 this reference is independent. */
155 bitmap dep_ref; /* The complement of DEP_REF. */
158 DEF_VEC_P(mem_ref_p);
159 DEF_VEC_ALLOC_P(mem_ref_p, heap);
162 DEF_VEC_ALLOC_P(bitmap, heap);
165 DEF_VEC_ALLOC_P(htab_t, heap);
167 /* Description of memory accesses in loops. */
171 /* The hash table of memory references accessed in loops. */
174 /* The list of memory references. */
175 VEC (mem_ref_p, heap) *refs_list;
177 /* The set of memory references accessed in each loop. */
178 VEC (bitmap, heap) *refs_in_loop;
180 /* The set of memory references accessed in each loop, including
182 VEC (bitmap, heap) *all_refs_in_loop;
184 /* The set of virtual operands clobbered in a given loop. */
185 VEC (bitmap, heap) *clobbered_vops;
187 /* Map from the pair (loop, virtual operand) to the set of refs that
188 touch the virtual operand in the loop. */
189 VEC (htab_t, heap) *vop_ref_map;
191 /* Cache for expanding memory addresses. */
192 struct pointer_map_t *ttae_cache;
195 static bool ref_indep_loop_p (struct loop *, mem_ref_p);
197 /* Minimum cost of an expensive expression. */
198 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
200 /* The outermost loop for that execution of the header guarantees that the
201 block will be executed. */
202 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
204 /* Calls CBCK for each index in memory reference ADDR_P. There are two
205 kinds situations handled; in each of these cases, the memory reference
206 and DATA are passed to the callback:
208 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
209 pass the pointer to the index to the callback.
211 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
212 pointer to addr to the callback.
214 If the callback returns false, the whole search stops and false is returned.
215 Otherwise the function returns true after traversing through the whole
216 reference *ADDR_P. */
219 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
223 for (; ; addr_p = nxt)
225 switch (TREE_CODE (*addr_p))
228 return cbck (*addr_p, addr_p, data);
230 case MISALIGNED_INDIRECT_REF:
231 case ALIGN_INDIRECT_REF:
233 nxt = &TREE_OPERAND (*addr_p, 0);
234 return cbck (*addr_p, nxt, data);
237 case VIEW_CONVERT_EXPR:
240 nxt = &TREE_OPERAND (*addr_p, 0);
244 /* If the component has varying offset, it behaves like index
246 idx = &TREE_OPERAND (*addr_p, 2);
248 && !cbck (*addr_p, idx, data))
251 nxt = &TREE_OPERAND (*addr_p, 0);
255 case ARRAY_RANGE_REF:
256 nxt = &TREE_OPERAND (*addr_p, 0);
257 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
274 gcc_assert (is_gimple_min_invariant (*addr_p));
278 idx = &TMR_BASE (*addr_p);
280 && !cbck (*addr_p, idx, data))
282 idx = &TMR_INDEX (*addr_p);
284 && !cbck (*addr_p, idx, data))
294 /* If it is possible to hoist the statement STMT unconditionally,
295 returns MOVE_POSSIBLE.
296 If it is possible to hoist the statement STMT, but we must avoid making
297 it executed if it would not be executed in the original program (e.g.
298 because it may trap), return MOVE_PRESERVE_EXECUTION.
299 Otherwise return MOVE_IMPOSSIBLE. */
302 movement_possibility (tree stmt)
306 if (flag_unswitch_loops
307 && TREE_CODE (stmt) == COND_EXPR)
309 /* If we perform unswitching, force the operands of the invariant
310 condition to be moved out of the loop. */
311 return MOVE_POSSIBLE;
314 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
315 return MOVE_IMPOSSIBLE;
317 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
318 return MOVE_IMPOSSIBLE;
320 if (stmt_ends_bb_p (stmt))
321 return MOVE_IMPOSSIBLE;
323 if (stmt_ann (stmt)->has_volatile_ops)
324 return MOVE_IMPOSSIBLE;
326 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
327 if (TREE_CODE (lhs) == SSA_NAME
328 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
329 return MOVE_IMPOSSIBLE;
331 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
333 if (TREE_SIDE_EFFECTS (rhs)
334 || tree_could_throw_p (rhs))
335 return MOVE_IMPOSSIBLE;
337 if (TREE_CODE (lhs) != SSA_NAME
338 || tree_could_trap_p (rhs))
339 return MOVE_PRESERVE_EXECUTION;
341 if (get_call_expr_in (stmt))
343 /* While pure or const call is guaranteed to have no side effects, we
344 cannot move it arbitrarily. Consider code like
346 char *s = something ();
356 Here the strlen call cannot be moved out of the loop, even though
357 s is invariant. In addition to possibly creating a call with
358 invalid arguments, moving out a function call that is not executed
359 may cause performance regressions in case the call is costly and
360 not executed at all. */
361 return MOVE_PRESERVE_EXECUTION;
363 return MOVE_POSSIBLE;
366 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
367 loop to that we could move the expression using DEF if it did not have
368 other operands, i.e. the outermost loop enclosing LOOP in that the value
369 of DEF is invariant. */
372 outermost_invariant_loop (tree def, struct loop *loop)
376 struct loop *max_loop;
378 if (TREE_CODE (def) != SSA_NAME)
379 return superloop_at_depth (loop, 1);
381 def_stmt = SSA_NAME_DEF_STMT (def);
382 def_bb = bb_for_stmt (def_stmt);
384 return superloop_at_depth (loop, 1);
386 max_loop = find_common_loop (loop, def_bb->loop_father);
388 if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
389 max_loop = find_common_loop (max_loop,
390 loop_outer (LIM_DATA (def_stmt)->max_loop));
391 if (max_loop == loop)
393 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
398 /* Returns the outermost superloop of LOOP in that the expression EXPR is
402 outermost_invariant_loop_expr (tree expr, struct loop *loop)
404 enum tree_code_class codeclass = TREE_CODE_CLASS (TREE_CODE (expr));
406 struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
408 if (TREE_CODE (expr) == SSA_NAME
409 || TREE_CODE (expr) == INTEGER_CST
410 || is_gimple_min_invariant (expr))
411 return outermost_invariant_loop (expr, loop);
413 if (codeclass != tcc_unary
414 && codeclass != tcc_binary
415 && codeclass != tcc_expression
416 && codeclass != tcc_vl_exp
417 && codeclass != tcc_comparison)
420 nops = TREE_OPERAND_LENGTH (expr);
421 for (i = 0; i < nops; i++)
423 aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
427 if (flow_loop_nested_p (max_loop, aloop))
434 /* DATA is a structure containing information associated with a statement
435 inside LOOP. DEF is one of the operands of this statement.
437 Find the outermost loop enclosing LOOP in that value of DEF is invariant
438 and record this in DATA->max_loop field. If DEF itself is defined inside
439 this loop as well (i.e. we need to hoist it out of the loop if we want
440 to hoist the statement represented by DATA), record the statement in that
441 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
442 add the cost of the computation of DEF to the DATA->cost.
444 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
447 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
450 tree def_stmt = SSA_NAME_DEF_STMT (def);
451 basic_block def_bb = bb_for_stmt (def_stmt);
452 struct loop *max_loop;
458 max_loop = outermost_invariant_loop (def, loop);
462 if (flow_loop_nested_p (data->max_loop, max_loop))
463 data->max_loop = max_loop;
465 if (!LIM_DATA (def_stmt))
469 /* Only add the cost if the statement defining DEF is inside LOOP,
470 i.e. if it is likely that by moving the invariants dependent
471 on it, we will be able to avoid creating a new register for
472 it (since it will be only used in these dependent invariants). */
473 && def_bb->loop_father == loop)
474 data->cost += LIM_DATA (def_stmt)->cost;
476 dep = XNEW (struct depend);
477 dep->stmt = def_stmt;
478 dep->next = data->depends;
484 /* Returns an estimate for a cost of statement STMT. TODO -- the values here
485 are just ad-hoc constants. The estimates should be based on target-specific
489 stmt_cost (tree stmt)
494 /* Always try to create possibilities for unswitching. */
495 if (TREE_CODE (stmt) == COND_EXPR)
496 return LIM_EXPENSIVE;
498 rhs = GENERIC_TREE_OPERAND (stmt, 1);
500 /* Hoisting memory references out should almost surely be a win. */
501 if (stmt_references_memory_p (stmt))
504 switch (TREE_CODE (rhs))
507 /* We should be hoisting calls if possible. */
509 /* Unless the call is a builtin_constant_p; this always folds to a
510 constant, so moving it is useless. */
511 rhs = get_callee_fndecl (rhs);
512 if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
513 && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
530 /* Division and multiplication are usually expensive. */
546 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
547 REF is independent. If REF is not independent in LOOP, NULL is returned
551 outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
555 if (bitmap_bit_p (ref->stored, loop->num))
560 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
561 if (!bitmap_bit_p (ref->stored, aloop->num)
562 && ref_indep_loop_p (aloop, ref))
565 if (ref_indep_loop_p (loop, ref))
571 /* If there is a simple load or store to a memory reference in STMT, returns
572 the location of the memory reference, and sets IS_STORE accoring to whether
573 it is a store or load. Otherwise, returns NULL. */
576 simple_mem_ref_in_stmt (tree stmt, bool *is_store)
580 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
581 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
584 lhs = &GIMPLE_STMT_OPERAND (stmt, 0);
585 rhs = &GIMPLE_STMT_OPERAND (stmt, 1);
587 if (TREE_CODE (*lhs) == SSA_NAME)
589 if (!is_gimple_addressable (*rhs))
595 else if (TREE_CODE (*rhs) == SSA_NAME
596 || is_gimple_min_invariant (*rhs))
605 /* Returns the memory reference contained in STMT. */
608 mem_ref_in_stmt (tree stmt)
611 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
619 hash = iterative_hash_expr (*mem, 0);
620 ref = htab_find_with_hash (memory_accesses.refs, *mem, hash);
622 gcc_assert (ref != NULL);
626 /* Determine the outermost loop to that it is possible to hoist a statement
627 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
628 the outermost loop in that the value computed by STMT is invariant.
629 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
630 we preserve the fact whether STMT is executed. It also fills other related
631 information to LIM_DATA (STMT).
633 The function returns false if STMT cannot be hoisted outside of the loop it
634 is defined in, and true otherwise. */
637 determine_max_movement (tree stmt, bool must_preserve_exec)
639 basic_block bb = bb_for_stmt (stmt);
640 struct loop *loop = bb->loop_father;
642 struct lim_aux_data *lim_data = LIM_DATA (stmt);
646 if (must_preserve_exec)
647 level = ALWAYS_EXECUTED_IN (bb);
649 level = superloop_at_depth (loop, 1);
650 lim_data->max_loop = level;
652 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
653 if (!add_dependency (val, lim_data, loop, true))
656 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
658 mem_ref_p ref = mem_ref_in_stmt (stmt);
663 = outermost_indep_loop (lim_data->max_loop, loop, ref);
664 if (!lim_data->max_loop)
669 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
671 if (!add_dependency (val, lim_data, loop, false))
677 lim_data->cost += stmt_cost (stmt);
682 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
683 and that one of the operands of this statement is computed by STMT.
684 Ensure that STMT (together with all the statements that define its
685 operands) is hoisted at least out of the loop LEVEL. */
688 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
690 struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
693 stmt_loop = find_common_loop (orig_loop, stmt_loop);
694 if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
695 stmt_loop = find_common_loop (stmt_loop,
696 loop_outer (LIM_DATA (stmt)->tgt_loop));
697 if (flow_loop_nested_p (stmt_loop, level))
700 gcc_assert (LIM_DATA (stmt));
701 gcc_assert (level == LIM_DATA (stmt)->max_loop
702 || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
704 LIM_DATA (stmt)->tgt_loop = level;
705 for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
706 set_level (dep->stmt, orig_loop, level);
709 /* Determines an outermost loop from that we want to hoist the statement STMT.
710 For now we chose the outermost possible loop. TODO -- use profiling
711 information to set it more sanely. */
714 set_profitable_level (tree stmt)
716 set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
719 /* Returns true if STMT is not a pure call. */
722 nonpure_call_p (tree stmt)
724 tree call = get_call_expr_in (stmt);
729 return TREE_SIDE_EFFECTS (call) != 0;
732 /* Releases the memory occupied by DATA. */
735 free_lim_aux_data (struct lim_aux_data *data)
737 struct depend *dep, *next;
739 for (dep = data->depends; dep; dep = next)
747 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
750 rewrite_reciprocal (block_stmt_iterator *bsi)
752 tree stmt, lhs, rhs, stmt1, stmt2, var, name, tmp;
754 stmt = bsi_stmt (*bsi);
755 lhs = GENERIC_TREE_OPERAND (stmt, 0);
756 rhs = GENERIC_TREE_OPERAND (stmt, 1);
758 /* stmt must be GIMPLE_MODIFY_STMT. */
759 var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
760 add_referenced_var (var);
762 tmp = build2 (RDIV_EXPR, TREE_TYPE (rhs),
763 build_real (TREE_TYPE (rhs), dconst1),
764 TREE_OPERAND (rhs, 1));
765 stmt1 = build_gimple_modify_stmt (var, tmp);
766 name = make_ssa_name (var, stmt1);
767 GIMPLE_STMT_OPERAND (stmt1, 0) = name;
768 tmp = build2 (MULT_EXPR, TREE_TYPE (rhs),
769 name, TREE_OPERAND (rhs, 0));
770 stmt2 = build_gimple_modify_stmt (lhs, tmp);
772 /* Replace division stmt with reciprocal and multiply stmts.
773 The multiply stmt is not invariant, so update iterator
774 and avoid rescanning. */
775 bsi_replace (bsi, stmt1, true);
776 bsi_insert_after (bsi, stmt2, BSI_NEW_STMT);
777 SSA_NAME_DEF_STMT (lhs) = stmt2;
779 /* Continue processing with invariant reciprocal statement. */
783 /* Check if the pattern at *BSI is a bittest of the form
784 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
787 rewrite_bittest (block_stmt_iterator *bsi)
789 tree stmt, lhs, rhs, var, name, use_stmt, stmt1, stmt2, t;
792 stmt = bsi_stmt (*bsi);
793 lhs = GENERIC_TREE_OPERAND (stmt, 0);
794 rhs = GENERIC_TREE_OPERAND (stmt, 1);
796 /* Verify that the single use of lhs is a comparison against zero. */
797 if (TREE_CODE (lhs) != SSA_NAME
798 || !single_imm_use (lhs, &use, &use_stmt)
799 || TREE_CODE (use_stmt) != COND_EXPR)
801 t = COND_EXPR_COND (use_stmt);
802 if (TREE_OPERAND (t, 0) != lhs
803 || (TREE_CODE (t) != NE_EXPR
804 && TREE_CODE (t) != EQ_EXPR)
805 || !integer_zerop (TREE_OPERAND (t, 1)))
808 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
809 stmt1 = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
810 if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
813 /* There is a conversion in between possibly inserted by fold. */
814 t = GIMPLE_STMT_OPERAND (stmt1, 1);
815 if (TREE_CODE (t) == NOP_EXPR
816 || TREE_CODE (t) == CONVERT_EXPR)
818 t = TREE_OPERAND (t, 0);
819 if (TREE_CODE (t) != SSA_NAME
820 || !has_single_use (t))
822 stmt1 = SSA_NAME_DEF_STMT (t);
823 if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
825 t = GIMPLE_STMT_OPERAND (stmt1, 1);
828 /* Verify that B is loop invariant but A is not. Verify that with
829 all the stmt walking we are still in the same loop. */
830 if (TREE_CODE (t) == RSHIFT_EXPR
831 && loop_containing_stmt (stmt1) == loop_containing_stmt (stmt)
832 && outermost_invariant_loop_expr (TREE_OPERAND (t, 1),
833 loop_containing_stmt (stmt1)) != NULL
834 && outermost_invariant_loop_expr (TREE_OPERAND (t, 0),
835 loop_containing_stmt (stmt1)) == NULL)
837 tree a = TREE_OPERAND (t, 0);
838 tree b = TREE_OPERAND (t, 1);
841 var = create_tmp_var (TREE_TYPE (a), "shifttmp");
842 add_referenced_var (var);
843 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
844 build_int_cst (TREE_TYPE (a), 1), b);
845 stmt1 = build_gimple_modify_stmt (var, t);
846 name = make_ssa_name (var, stmt1);
847 GIMPLE_STMT_OPERAND (stmt1, 0) = name;
850 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
851 stmt2 = build_gimple_modify_stmt (var, t);
852 name = make_ssa_name (var, stmt2);
853 GIMPLE_STMT_OPERAND (stmt2, 0) = name;
855 /* Replace the SSA_NAME we compare against zero. Adjust
856 the type of zero accordingly. */
858 TREE_OPERAND (COND_EXPR_COND (use_stmt), 1)
859 = build_int_cst_type (TREE_TYPE (name), 0);
861 bsi_insert_before (bsi, stmt1, BSI_SAME_STMT);
862 bsi_replace (bsi, stmt2, true);
871 /* Determine the outermost loops in that statements in basic block BB are
872 invariant, and record them to the LIM_DATA associated with the statements.
873 Callback for walk_dominator_tree. */
876 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
880 block_stmt_iterator bsi;
882 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
883 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
885 if (!loop_outer (bb->loop_father))
888 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
890 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
892 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
894 stmt = bsi_stmt (bsi);
896 pos = movement_possibility (stmt);
897 if (pos == MOVE_IMPOSSIBLE)
899 if (nonpure_call_p (stmt))
907 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
909 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
911 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
912 to be hoisted out of loop, saving expensive divide. */
913 if (pos == MOVE_POSSIBLE
914 && TREE_CODE (rhs) == RDIV_EXPR
915 && flag_unsafe_math_optimizations
916 && !flag_trapping_math
917 && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
918 loop_containing_stmt (stmt)) != NULL
919 && outermost_invariant_loop_expr (rhs,
920 loop_containing_stmt (stmt)) == NULL)
921 stmt = rewrite_reciprocal (&bsi);
923 /* If the shift count is invariant, convert (A >> B) & 1 to
924 A & (1 << B) allowing the bit mask to be hoisted out of the loop
925 saving an expensive shift. */
926 if (pos == MOVE_POSSIBLE
927 && TREE_CODE (rhs) == BIT_AND_EXPR
928 && integer_onep (TREE_OPERAND (rhs, 1))
929 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
930 && has_single_use (TREE_OPERAND (rhs, 0)))
931 stmt = rewrite_bittest (&bsi);
934 stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
935 LIM_DATA (stmt)->always_executed_in = outermost;
937 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
940 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
942 LIM_DATA (stmt)->max_loop = NULL;
946 if (dump_file && (dump_flags & TDF_DETAILS))
948 print_generic_stmt_indented (dump_file, stmt, 0, 2);
949 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
950 loop_depth (LIM_DATA (stmt)->max_loop),
951 LIM_DATA (stmt)->cost);
954 if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
955 set_profitable_level (stmt);
959 /* For each statement determines the outermost loop in that it is invariant,
960 statements on whose motion it depends and the cost of the computation.
961 This information is stored to the LIM_DATA structure associated with
965 determine_invariantness (void)
967 struct dom_walk_data walk_data;
969 memset (&walk_data, 0, sizeof (struct dom_walk_data));
970 walk_data.dom_direction = CDI_DOMINATORS;
971 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
973 init_walk_dominator_tree (&walk_data);
974 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
975 fini_walk_dominator_tree (&walk_data);
978 /* Hoist the statements in basic block BB out of the loops prescribed by
979 data stored in LIM_DATA structures associated with each statement. Callback
980 for walk_dominator_tree. */
983 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
987 block_stmt_iterator bsi;
991 if (!loop_outer (bb->loop_father))
994 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
996 stmt = bsi_stmt (bsi);
998 if (!LIM_DATA (stmt))
1004 cost = LIM_DATA (stmt)->cost;
1005 level = LIM_DATA (stmt)->tgt_loop;
1006 free_lim_aux_data (LIM_DATA (stmt));
1007 stmt_ann (stmt)->common.aux = NULL;
1015 /* We do not really want to move conditionals out of the loop; we just
1016 placed it here to force its operands to be moved if necessary. */
1017 if (TREE_CODE (stmt) == COND_EXPR)
1020 if (dump_file && (dump_flags & TDF_DETAILS))
1022 fprintf (dump_file, "Moving statement\n");
1023 print_generic_stmt (dump_file, stmt, 0);
1024 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1028 mark_virtual_ops_for_renaming (stmt);
1029 bsi_insert_on_edge (loop_preheader_edge (level), stmt);
1030 bsi_remove (&bsi, false);
1034 /* Hoist the statements out of the loops prescribed by data stored in
1035 LIM_DATA structures associated with each statement.*/
1038 move_computations (void)
1040 struct dom_walk_data walk_data;
1042 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1043 walk_data.dom_direction = CDI_DOMINATORS;
1044 walk_data.before_dom_children_before_stmts = move_computations_stmt;
1046 init_walk_dominator_tree (&walk_data);
1047 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1048 fini_walk_dominator_tree (&walk_data);
1050 bsi_commit_edge_inserts ();
1051 if (need_ssa_update_p ())
1052 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1055 /* Checks whether the statement defining variable *INDEX can be hoisted
1056 out of the loop passed in DATA. Callback for for_each_index. */
1059 may_move_till (tree ref, tree *index, void *data)
1061 struct loop *loop = (struct loop*) data, *max_loop;
1063 /* If REF is an array reference, check also that the step and the lower
1064 bound is invariant in LOOP. */
1065 if (TREE_CODE (ref) == ARRAY_REF)
1067 tree step = array_ref_element_size (ref);
1068 tree lbound = array_ref_low_bound (ref);
1070 max_loop = outermost_invariant_loop_expr (step, loop);
1074 max_loop = outermost_invariant_loop_expr (lbound, loop);
1079 max_loop = outermost_invariant_loop (*index, loop);
1086 /* Forces statements defining (invariant) SSA names in expression EXPR to be
1087 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1090 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
1092 enum tree_code_class codeclass = TREE_CODE_CLASS (TREE_CODE (expr));
1095 if (TREE_CODE (expr) == SSA_NAME)
1097 tree stmt = SSA_NAME_DEF_STMT (expr);
1098 if (IS_EMPTY_STMT (stmt))
1101 set_level (stmt, orig_loop, loop);
1105 if (codeclass != tcc_unary
1106 && codeclass != tcc_binary
1107 && codeclass != tcc_expression
1108 && codeclass != tcc_vl_exp
1109 && codeclass != tcc_comparison)
1112 nops = TREE_OPERAND_LENGTH (expr);
1113 for (i = 0; i < nops; i++)
1114 force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
1117 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1118 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1124 struct loop *orig_loop;
1128 force_move_till (tree ref, tree *index, void *data)
1131 struct fmt_data *fmt_data = (struct fmt_data *) data;
1133 if (TREE_CODE (ref) == ARRAY_REF)
1135 tree step = array_ref_element_size (ref);
1136 tree lbound = array_ref_low_bound (ref);
1138 force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
1139 force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
1142 if (TREE_CODE (*index) != SSA_NAME)
1145 stmt = SSA_NAME_DEF_STMT (*index);
1146 if (IS_EMPTY_STMT (stmt))
1149 set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
1154 /* A hash function for struct mem_ref object OBJ. */
1157 memref_hash (const void *obj)
1159 const struct mem_ref *mem = obj;
1164 /* An equality function for struct mem_ref object OBJ1 with
1165 memory reference OBJ2. */
1168 memref_eq (const void *obj1, const void *obj2)
1170 const struct mem_ref *mem1 = obj1;
1172 return operand_equal_p (mem1->mem, (tree) obj2, 0);
1175 /* Releases list of memory reference locations ACCS. */
1178 free_mem_ref_locs (mem_ref_locs_p accs)
1186 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1188 VEC_free (mem_ref_loc_p, heap, accs->locs);
1192 /* A function to free the mem_ref object OBJ. */
1195 memref_free (void *obj)
1197 struct mem_ref *mem = obj;
1199 mem_ref_locs_p accs;
1201 BITMAP_FREE (mem->stored);
1202 BITMAP_FREE (mem->indep_loop);
1203 BITMAP_FREE (mem->dep_loop);
1204 BITMAP_FREE (mem->indep_ref);
1205 BITMAP_FREE (mem->dep_ref);
1207 for (i = 0; VEC_iterate (mem_ref_locs_p, mem->accesses_in_loop, i, accs); i++)
1208 free_mem_ref_locs (accs);
1209 VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
1211 BITMAP_FREE (mem->vops);
1215 /* Allocates and returns a memory reference description for MEM whose hash
1216 value is HASH and id is ID. */
1219 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1221 mem_ref_p ref = XNEW (struct mem_ref);
1225 ref->stored = BITMAP_ALLOC (NULL);
1226 ref->indep_loop = BITMAP_ALLOC (NULL);
1227 ref->dep_loop = BITMAP_ALLOC (NULL);
1228 ref->indep_ref = BITMAP_ALLOC (NULL);
1229 ref->dep_ref = BITMAP_ALLOC (NULL);
1230 ref->accesses_in_loop = NULL;
1231 ref->vops = BITMAP_ALLOC (NULL);
1236 /* Allocates and returns the new list of locations. */
1238 static mem_ref_locs_p
1239 mem_ref_locs_alloc (void)
1241 mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
1246 /* Records memory reference location *LOC in LOOP to the memory reference
1247 description REF. The reference occurs in statement STMT. */
1250 record_mem_ref_loc (mem_ref_p ref, struct loop *loop, tree stmt, tree *loc)
1252 mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
1253 mem_ref_locs_p accs;
1254 bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1256 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1257 <= (unsigned) loop->num)
1258 VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
1260 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1263 accs = mem_ref_locs_alloc ();
1264 VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
1270 VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
1271 bitmap_set_bit (ril, ref->id);
1274 /* Marks reference REF as stored in LOOP. */
1277 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1280 loop != current_loops->tree_root
1281 && !bitmap_bit_p (ref->stored, loop->num);
1282 loop = loop_outer (loop))
1283 bitmap_set_bit (ref->stored, loop->num);
1286 /* Gathers memory references in statement STMT in LOOP, storing the
1287 information about them in the memory_accesses structure. Marks
1288 the vops accessed through unrecognized statements there as
1292 gather_mem_refs_stmt (struct loop *loop, tree stmt)
1304 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1307 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1311 hash = iterative_hash_expr (*mem, 0);
1312 slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
1321 id = VEC_length (mem_ref_p, memory_accesses.refs_list);
1322 ref = mem_ref_alloc (*mem, hash, id);
1323 VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
1326 if (dump_file && (dump_flags & TDF_DETAILS))
1328 fprintf (dump_file, "Memory reference %u: ", id);
1329 print_generic_expr (dump_file, ref->mem, TDF_SLIM);
1330 fprintf (dump_file, "\n");
1334 mark_ref_stored (ref, loop);
1336 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1337 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1338 record_mem_ref_loc (ref, loop, stmt, mem);
1342 clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1343 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1344 bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
1347 /* Gathers memory references in loops. */
1350 gather_mem_refs_in_loops (void)
1352 block_stmt_iterator bsi;
1357 bitmap lrefs, alrefs, alrefso;
1361 loop = bb->loop_father;
1362 if (loop == current_loops->tree_root)
1365 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1366 gather_mem_refs_stmt (loop, bsi_stmt (bsi));
1369 /* Propagate the information about clobbered vops and accessed memory
1370 references up the loop hierarchy. */
1371 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1373 lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1374 alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
1375 bitmap_ior_into (alrefs, lrefs);
1377 if (loop_outer (loop) == current_loops->tree_root)
1380 clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1381 clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
1382 loop_outer (loop)->num);
1383 bitmap_ior_into (clvo, clvi);
1385 alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1386 loop_outer (loop)->num);
1387 bitmap_ior_into (alrefso, alrefs);
1391 /* Element of the hash table that maps vops to memory references. */
1393 struct vop_to_refs_elt
1395 /* DECL_UID of the vop. */
1398 /* List of the all references. */
1401 /* List of stored references. */
1405 /* A hash function for struct vop_to_refs_elt object OBJ. */
1408 vtoe_hash (const void *obj)
1410 const struct vop_to_refs_elt *vtoe = 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 *vtoe = obj1;
1422 const unsigned *uid = obj2;
1424 return vtoe->uid == *uid;
1427 /* A function to free the struct vop_to_refs_elt object. */
1430 vtoe_free (void *obj)
1432 struct vop_to_refs_elt *vtoe = obj;
1434 BITMAP_FREE (vtoe->refs_all);
1435 BITMAP_FREE (vtoe->refs_stored);
1439 /* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1440 if the reference REF is stored. */
1443 record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool stored)
1445 void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
1446 struct vop_to_refs_elt *vtoe;
1450 vtoe = XNEW (struct vop_to_refs_elt);
1452 vtoe->refs_all = BITMAP_ALLOC (NULL);
1453 vtoe->refs_stored = BITMAP_ALLOC (NULL);
1459 bitmap_set_bit (vtoe->refs_all, ref);
1461 bitmap_set_bit (vtoe->refs_stored, ref);
1464 /* Returns the set of references that access VOP according to the table
1468 get_vop_accesses (htab_t vop_to_refs, unsigned vop)
1470 struct vop_to_refs_elt *vtoe = htab_find_with_hash (vop_to_refs, &vop, vop);
1471 return vtoe->refs_all;
1474 /* Returns the set of stores that access VOP according to the table
1478 get_vop_stores (htab_t vop_to_refs, unsigned vop)
1480 struct vop_to_refs_elt *vtoe = htab_find_with_hash (vop_to_refs, &vop, vop);
1481 return vtoe->refs_stored;
1484 /* Adds REF to mapping from virtual operands to references in LOOP. */
1487 add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
1489 htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1490 bool stored = bitmap_bit_p (ref->stored, loop->num);
1491 bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
1496 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
1498 record_vop_access (map, vop, ref->id, stored);
1502 /* Create a mapping from virtual operands to references that touch them
1506 create_vop_ref_mapping_loop (struct loop *loop)
1508 bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1514 EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
1516 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1517 for (sloop = loop; sloop != current_loops->tree_root; sloop = loop_outer (sloop))
1518 add_vop_ref_mapping (sloop, ref);
1522 /* For each non-clobbered virtual operand and each loop, record the memory
1523 references in this loop that touch the operand. */
1526 create_vop_ref_mapping (void)
1531 FOR_EACH_LOOP (li, loop, 0)
1533 create_vop_ref_mapping_loop (loop);
1537 /* Gathers information about memory accesses in the loops. */
1540 analyze_memory_references (void)
1546 memory_accesses.refs
1547 = htab_create (100, memref_hash, memref_eq, memref_free);
1548 memory_accesses.refs_list = NULL;
1549 memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
1550 number_of_loops ());
1551 memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
1552 number_of_loops ());
1553 memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
1554 number_of_loops ());
1555 memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
1556 number_of_loops ());
1558 for (i = 0; i < number_of_loops (); i++)
1560 empty = BITMAP_ALLOC (NULL);
1561 VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
1562 empty = BITMAP_ALLOC (NULL);
1563 VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
1564 empty = BITMAP_ALLOC (NULL);
1565 VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
1566 hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
1567 VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
1570 memory_accesses.ttae_cache = NULL;
1572 gather_mem_refs_in_loops ();
1573 create_vop_ref_mapping ();
1576 /* Returns true if a region of size SIZE1 at position 0 and a region of
1577 size SIZE2 at position DIFF cannot overlap. */
1580 cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
1582 double_int d, bound;
1584 /* Unless the difference is a constant, we fail. */
1589 if (double_int_negative_p (d))
1591 /* The second object is before the first one, we succeed if the last
1592 element of the second object is before the start of the first one. */
1593 bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
1594 return double_int_negative_p (bound);
1598 /* We succeed if the second object starts after the first one ends. */
1599 return double_int_scmp (size1, d) <= 0;
1603 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1604 tree_to_aff_combination_expand. */
1607 mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
1609 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1610 object and their offset differ in such a way that the locations cannot
1611 overlap, then they cannot alias. */
1612 aff_tree off1, off2;
1613 double_int size1, size2;
1616 /* If MEM1 and MEM2 are based on different variables, they cannot alias. */
1617 base1 = get_base_address (mem1);
1618 base2 = get_base_address (mem2);
1621 && !INDIRECT_REF_P (base1)
1623 && !INDIRECT_REF_P (base2)
1624 && !operand_equal_p (base1, base2, 0))
1627 /* With strict aliasing, it is impossible to access a scalar variable through
1628 anything but a pointer dereference or through a union (gcc extension). */
1629 if (flag_strict_aliasing)
1631 if (!INDIRECT_REF_P (mem1)
1633 && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE
1635 && !AGGREGATE_TYPE_P (TREE_TYPE (mem2)))
1637 if (!INDIRECT_REF_P (mem2)
1639 && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE
1641 && !AGGREGATE_TYPE_P (TREE_TYPE (mem1)))
1643 if (!alias_sets_conflict_p (get_alias_set (mem1), get_alias_set (mem2)))
1647 /* The expansion of addresses may be a bit expensive, thus we only do
1648 the check at -O2 and higher optimization levels. */
1652 get_inner_reference_aff (mem1, &off1, &size1);
1653 get_inner_reference_aff (mem2, &off2, &size2);
1654 aff_combination_expand (&off1, ttae_cache);
1655 aff_combination_expand (&off2, ttae_cache);
1656 aff_combination_scale (&off1, double_int_minus_one);
1657 aff_combination_add (&off2, &off1);
1659 if (cannot_overlap_p (&off2, size1, size2))
1665 /* Rewrites location LOC by TMP_VAR. */
1668 rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
1670 mark_virtual_ops_for_renaming (loc->stmt);
1671 *loc->ref = tmp_var;
1672 update_stmt (loc->stmt);
1675 /* Adds all locations of REF in LOOP and its subloops to LOCS. */
1678 get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
1679 VEC (mem_ref_loc_p, heap) **locs)
1681 mem_ref_locs_p accs;
1684 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1686 struct loop *subloop;
1688 if (!bitmap_bit_p (refs, ref->id))
1691 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1692 > (unsigned) loop->num)
1694 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1697 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1698 VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
1702 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1703 get_all_locs_in_loop (subloop, ref, locs);
1706 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1709 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1713 VEC (mem_ref_loc_p, heap) *locs = NULL;
1715 get_all_locs_in_loop (loop, ref, &locs);
1716 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1717 rewrite_mem_ref_loc (loc, tmp_var);
1718 VEC_free (mem_ref_loc_p, heap, locs);
1721 /* The name and the length of the currently generated variable
1723 #define MAX_LSM_NAME_LENGTH 40
1724 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1725 static int lsm_tmp_name_length;
1727 /* Adds S to lsm_tmp_name. */
1730 lsm_tmp_name_add (const char *s)
1732 int l = strlen (s) + lsm_tmp_name_length;
1733 if (l > MAX_LSM_NAME_LENGTH)
1736 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1737 lsm_tmp_name_length = l;
1740 /* Stores the name for temporary variable that replaces REF to
1744 gen_lsm_tmp_name (tree ref)
1748 switch (TREE_CODE (ref))
1750 case MISALIGNED_INDIRECT_REF:
1751 case ALIGN_INDIRECT_REF:
1753 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1754 lsm_tmp_name_add ("_");
1758 case VIEW_CONVERT_EXPR:
1759 case ARRAY_RANGE_REF:
1760 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1764 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1765 lsm_tmp_name_add ("_RE");
1769 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1770 lsm_tmp_name_add ("_IM");
1774 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1775 lsm_tmp_name_add ("_");
1776 name = get_name (TREE_OPERAND (ref, 1));
1779 lsm_tmp_name_add ("_");
1780 lsm_tmp_name_add (name);
1783 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1784 lsm_tmp_name_add ("_I");
1788 ref = SSA_NAME_VAR (ref);
1793 name = get_name (ref);
1796 lsm_tmp_name_add (name);
1800 lsm_tmp_name_add ("S");
1804 lsm_tmp_name_add ("R");
1812 /* Determines name for temporary variable that replaces REF.
1813 The name is accumulated into the lsm_tmp_name variable.
1814 N is added to the name of the temporary. */
1817 get_lsm_tmp_name (tree ref, unsigned n)
1821 lsm_tmp_name_length = 0;
1822 gen_lsm_tmp_name (ref);
1823 lsm_tmp_name_add ("_lsm");
1828 lsm_tmp_name_add (ns);
1830 return lsm_tmp_name;
1833 /* Executes store motion of memory reference REF from LOOP.
1834 Exits from the LOOP are stored in EXITS. The initialization of the
1835 temporary variable is put to the preheader of the loop, and assignments
1836 to the reference from the temporary variable are emitted to exits. */
1839 execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
1844 struct fmt_data fmt_data;
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1849 fprintf (dump_file, "Executing store motion of ");
1850 print_generic_expr (dump_file, ref->mem, 0);
1851 fprintf (dump_file, " from loop %d\n", loop->num);
1854 tmp_var = make_rename_temp (TREE_TYPE (ref->mem),
1855 get_lsm_tmp_name (ref->mem, ~0));
1857 fmt_data.loop = loop;
1858 fmt_data.orig_loop = loop;
1859 for_each_index (&ref->mem, force_move_till, &fmt_data);
1861 rewrite_mem_refs (loop, ref, tmp_var);
1863 /* Emit the load & stores. */
1864 load = build_gimple_modify_stmt (tmp_var, unshare_expr (ref->mem));
1865 get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1866 LIM_DATA (load)->max_loop = loop;
1867 LIM_DATA (load)->tgt_loop = loop;
1869 /* Put this into the latch, so that we are sure it will be processed after
1870 all dependencies. */
1871 bsi_insert_on_edge (loop_latch_edge (loop), load);
1873 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1875 store = build_gimple_modify_stmt (unshare_expr (ref->mem), tmp_var);
1876 bsi_insert_on_edge (ex, store);
1880 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
1881 edges of the LOOP. */
1884 hoist_memory_references (struct loop *loop, bitmap mem_refs,
1885 VEC (edge, heap) *exits)
1891 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
1893 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1894 execute_sm (loop, exits, ref);
1898 /* Returns true if REF is always accessed in LOOP. */
1901 ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
1903 VEC (mem_ref_loc_p, heap) *locs = NULL;
1907 struct loop *must_exec;
1909 get_all_locs_in_loop (loop, ref, &locs);
1910 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1912 if (!LIM_DATA (loc->stmt))
1915 must_exec = LIM_DATA (loc->stmt)->always_executed_in;
1919 if (must_exec == loop
1920 || flow_loop_nested_p (must_exec, loop))
1926 VEC_free (mem_ref_loc_p, heap, locs);
1931 /* Returns true if REF1 and REF2 are independent. */
1934 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
1937 || bitmap_bit_p (ref1->indep_ref, ref2->id))
1939 if (bitmap_bit_p (ref1->dep_ref, ref2->id))
1942 if (dump_file && (dump_flags & TDF_DETAILS))
1943 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
1944 ref1->id, ref2->id);
1946 if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
1947 &memory_accesses.ttae_cache))
1949 bitmap_set_bit (ref1->dep_ref, ref2->id);
1950 bitmap_set_bit (ref2->dep_ref, ref1->id);
1951 if (dump_file && (dump_flags & TDF_DETAILS))
1952 fprintf (dump_file, "dependent.\n");
1957 bitmap_set_bit (ref1->indep_ref, ref2->id);
1958 bitmap_set_bit (ref2->indep_ref, ref1->id);
1959 if (dump_file && (dump_flags & TDF_DETAILS))
1960 fprintf (dump_file, "independent.\n");
1965 /* Records the information whether REF is independent in LOOP (according
1969 record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
1972 bitmap_set_bit (ref->indep_loop, loop->num);
1974 bitmap_set_bit (ref->dep_loop, loop->num);
1977 /* Returns true if REF is independent on all other memory references in
1981 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
1983 bitmap clobbers, refs_to_check, refs;
1986 bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
1990 /* If the reference is clobbered, it is not independent. */
1991 clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1992 if (bitmap_intersect_p (ref->vops, clobbers))
1995 refs_to_check = BITMAP_ALLOC (NULL);
1997 map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1998 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
2001 refs = get_vop_accesses (map, i);
2003 refs = get_vop_stores (map, i);
2005 bitmap_ior_into (refs_to_check, refs);
2008 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2010 aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2011 if (!refs_independent_p (ref, aref))
2014 record_indep_loop (loop, aref, false);
2019 BITMAP_FREE (refs_to_check);
2023 /* Returns true if REF is independent on all other memory references in
2024 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2027 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2031 if (bitmap_bit_p (ref->indep_loop, loop->num))
2033 if (bitmap_bit_p (ref->dep_loop, loop->num))
2036 ret = ref_indep_loop_p_1 (loop, ref);
2038 if (dump_file && (dump_flags & TDF_DETAILS))
2039 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2040 ref->id, loop->num, ret ? "independent" : "dependent");
2042 record_indep_loop (loop, ref, ret);
2047 /* Returns true if we can perform store motion of REF from LOOP. */
2050 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2052 /* Unless the reference is stored in the loop, there is nothing to do. */
2053 if (!bitmap_bit_p (ref->stored, loop->num))
2056 /* It should be movable. */
2057 if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
2058 || TREE_THIS_VOLATILE (ref->mem)
2059 || !for_each_index (&ref->mem, may_move_till, loop))
2062 /* If it can trap, it must be always executed in LOOP. */
2063 if (tree_could_trap_p (ref->mem)
2064 && !ref_always_accessed_p (loop, ref))
2067 /* And it must be independent on all other memory references
2069 if (!ref_indep_loop_p (loop, ref))
2075 /* Marks the references in LOOP for that store motion should be performed
2076 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2077 motion was performed in one of the outer loops. */
2080 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2082 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
2088 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2090 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2091 if (can_sm_ref_p (loop, ref))
2092 bitmap_set_bit (refs_to_sm, i);
2096 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2097 for a store motion optimization (i.e. whether we can insert statement
2101 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2102 VEC (edge, heap) *exits)
2107 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2108 if (ex->flags & EDGE_ABNORMAL)
2114 /* Try to perform store motion for all memory references modified inside
2115 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2116 store motion was executed in one of the outer loops. */
2119 store_motion_loop (struct loop *loop, bitmap sm_executed)
2121 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2122 struct loop *subloop;
2123 bitmap sm_in_loop = BITMAP_ALLOC (NULL);
2125 if (loop_suitable_for_sm (loop, exits))
2127 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2128 hoist_memory_references (loop, sm_in_loop, exits);
2130 VEC_free (edge, heap, exits);
2132 bitmap_ior_into (sm_executed, sm_in_loop);
2133 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2134 store_motion_loop (subloop, sm_executed);
2135 bitmap_and_compl_into (sm_executed, sm_in_loop);
2136 BITMAP_FREE (sm_in_loop);
2139 /* Try to perform store motion for all memory references modified inside
2146 bitmap sm_executed = BITMAP_ALLOC (NULL);
2148 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2149 store_motion_loop (loop, sm_executed);
2151 BITMAP_FREE (sm_executed);
2152 bsi_commit_edge_inserts ();
2155 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2156 for each such basic block bb records the outermost loop for that execution
2157 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2158 blocks that contain a nonpure call. */
2161 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
2163 basic_block bb = NULL, *bbs, last = NULL;
2166 struct loop *inn_loop = loop;
2168 if (!loop->header->aux)
2170 bbs = get_loop_body_in_dom_order (loop);
2172 for (i = 0; i < loop->num_nodes; i++)
2177 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2180 if (TEST_BIT (contains_call, bb->index))
2183 FOR_EACH_EDGE (e, ei, bb->succs)
2184 if (!flow_bb_inside_loop_p (loop, e->dest))
2189 /* A loop might be infinite (TODO use simple loop analysis
2190 to disprove this if possible). */
2191 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2194 if (!flow_bb_inside_loop_p (inn_loop, bb))
2197 if (bb->loop_father->header == bb)
2199 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2202 /* In a loop that is always entered we may proceed anyway.
2203 But record that we entered it and stop once we leave it. */
2204 inn_loop = bb->loop_father;
2211 if (last == loop->header)
2213 last = get_immediate_dominator (CDI_DOMINATORS, last);
2219 for (loop = loop->inner; loop; loop = loop->next)
2220 fill_always_executed_in (loop, contains_call);
2223 /* Compute the global information needed by the loop invariant motion pass. */
2226 tree_ssa_lim_initialize (void)
2228 sbitmap contains_call = sbitmap_alloc (last_basic_block);
2229 block_stmt_iterator bsi;
2233 sbitmap_zero (contains_call);
2236 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2238 if (nonpure_call_p (bsi_stmt (bsi)))
2242 if (!bsi_end_p (bsi))
2243 SET_BIT (contains_call, bb->index);
2246 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2247 fill_always_executed_in (loop, contains_call);
2249 sbitmap_free (contains_call);
2252 /* Cleans up after the invariant motion pass. */
2255 tree_ssa_lim_finalize (void)
2267 VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
2268 htab_delete (memory_accesses.refs);
2270 for (i = 0; VEC_iterate (bitmap, memory_accesses.refs_in_loop, i, b); i++)
2272 VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
2274 for (i = 0; VEC_iterate (bitmap, memory_accesses.all_refs_in_loop, i, b); i++)
2276 VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
2278 for (i = 0; VEC_iterate (bitmap, memory_accesses.clobbered_vops, i, b); i++)
2280 VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
2282 for (i = 0; VEC_iterate (htab_t, memory_accesses.vop_ref_map, i, h); i++)
2284 VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
2286 if (memory_accesses.ttae_cache)
2287 pointer_map_destroy (memory_accesses.ttae_cache);
2290 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2291 i.e. those that are likely to be win regardless of the register pressure. */
2296 tree_ssa_lim_initialize ();
2298 /* Gathers information about memory accesses in the loops. */
2299 analyze_memory_references ();
2301 /* For each statement determine the outermost loop in that it is
2302 invariant and cost for computing the invariant. */
2303 determine_invariantness ();
2305 /* Execute store motion. Force the necessary invariants to be moved
2306 out of the loops as well. */
2309 /* Move the expressions that are expensive enough. */
2310 move_computations ();
2312 tree_ssa_lim_finalize ();