Merge trunk version 206243 into gupc branch.
[official-gcc.git] / gcc / tree-ssa-loop-im.c
blobcbcdc37f91dadf6a7feb4b343fcf9928a4a1d663
1 /* Loop invariant motion.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "tm_p.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "pointer-set.h"
29 #include "hash-table.h"
30 #include "tree-ssa-alias.h"
31 #include "internal-fn.h"
32 #include "tree-eh.h"
33 #include "gimple-expr.h"
34 #include "is-a.h"
35 #include "gimple.h"
36 #include "gimplify.h"
37 #include "gimple-iterator.h"
38 #include "gimplify-me.h"
39 #include "gimple-ssa.h"
40 #include "tree-cfg.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop.h"
47 #include "tree-into-ssa.h"
48 #include "cfgloop.h"
49 #include "domwalk.h"
50 #include "params.h"
51 #include "tree-pass.h"
52 #include "flags.h"
53 #include "tree-affine.h"
54 #include "tree-ssa-propagate.h"
55 #include "trans-mem.h"
57 /* TODO: Support for predicated code motion. I.e.
59 while (1)
61 if (cond)
63 a = inv;
64 something;
68 Where COND and INV are invariants, but evaluating INV may trap or be
69 invalid from some other reason if !COND. This may be transformed to
71 if (cond)
72 a = inv;
73 while (1)
75 if (cond)
76 something;
77 } */
79 /* The auxiliary data kept for each statement. */
81 struct lim_aux_data
83 struct loop *max_loop; /* The outermost loop in that the statement
84 is invariant. */
86 struct loop *tgt_loop; /* The loop out of that we want to move the
87 invariant. */
89 struct loop *always_executed_in;
90 /* The outermost loop for that we are sure
91 the statement is executed if the loop
92 is entered. */
94 unsigned cost; /* Cost of the computation performed by the
95 statement. */
97 vec<gimple> depends; /* Vector of statements that must be also
98 hoisted out of the loop when this statement
99 is hoisted; i.e. those that define the
100 operands of the statement and are inside of
101 the MAX_LOOP loop. */
104 /* Maps statements to their lim_aux_data. */
106 static struct pointer_map_t *lim_aux_data_map;
108 /* Description of a memory reference location. */
110 typedef struct mem_ref_loc
112 tree *ref; /* The reference itself. */
113 gimple stmt; /* The statement in that it occurs. */
114 } *mem_ref_loc_p;
117 /* Description of a memory reference. */
119 typedef struct mem_ref
121 unsigned id; /* ID assigned to the memory reference
122 (its index in memory_accesses.refs_list) */
123 hashval_t hash; /* Its hash value. */
125 /* The memory access itself and associated caching of alias-oracle
126 query meta-data. */
127 ao_ref mem;
129 bitmap_head stored; /* The set of loops in that this memory location
130 is stored to. */
131 vec<vec<mem_ref_loc> > accesses_in_loop;
132 /* The locations of the accesses. Vector
133 indexed by the loop number. */
135 /* The following sets are computed on demand. We keep both set and
136 its complement, so that we know whether the information was
137 already computed or not. */
138 bitmap_head indep_loop; /* The set of loops in that the memory
139 reference is independent, meaning:
140 If it is stored in the loop, this store
141 is independent on all other loads and
142 stores.
143 If it is only loaded, then it is independent
144 on all stores in the loop. */
145 bitmap_head dep_loop; /* The complement of INDEP_LOOP. */
146 } *mem_ref_p;
148 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
149 to record (in)dependence against stores in the loop and its subloops, the
150 second to record (in)dependence against all references in the loop
151 and its subloops. */
152 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
154 /* Mem_ref hashtable helpers. */
156 struct mem_ref_hasher : typed_noop_remove <mem_ref>
158 typedef mem_ref value_type;
159 typedef tree_node compare_type;
160 static inline hashval_t hash (const value_type *);
161 static inline bool equal (const value_type *, const compare_type *);
164 /* A hash function for struct mem_ref object OBJ. */
166 inline hashval_t
167 mem_ref_hasher::hash (const value_type *mem)
169 return mem->hash;
172 /* An equality function for struct mem_ref object MEM1 with
173 memory reference OBJ2. */
175 inline bool
176 mem_ref_hasher::equal (const value_type *mem1, const compare_type *obj2)
178 return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
182 /* Description of memory accesses in loops. */
184 static struct
186 /* The hash table of memory references accessed in loops. */
187 hash_table <mem_ref_hasher> refs;
189 /* The list of memory references. */
190 vec<mem_ref_p> refs_list;
192 /* The set of memory references accessed in each loop. */
193 vec<bitmap_head> refs_in_loop;
195 /* The set of memory references stored in each loop. */
196 vec<bitmap_head> refs_stored_in_loop;
198 /* The set of memory references stored in each loop, including subloops . */
199 vec<bitmap_head> all_refs_stored_in_loop;
201 /* Cache for expanding memory addresses. */
202 struct pointer_map_t *ttae_cache;
203 } memory_accesses;
205 /* Obstack for the bitmaps in the above data structures. */
206 static bitmap_obstack lim_bitmap_obstack;
208 static bool ref_indep_loop_p (struct loop *, mem_ref_p);
210 /* Minimum cost of an expensive expression. */
211 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
213 /* The outermost loop for which execution of the header guarantees that the
214 block will be executed. */
215 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
216 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
218 /* ID of the shared unanalyzable mem. */
219 #define UNANALYZABLE_MEM_ID 0
221 /* Whether the reference was analyzable. */
222 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
224 static struct lim_aux_data *
225 init_lim_data (gimple stmt)
227 void **p = pointer_map_insert (lim_aux_data_map, stmt);
229 *p = XCNEW (struct lim_aux_data);
230 return (struct lim_aux_data *) *p;
233 static struct lim_aux_data *
234 get_lim_data (gimple stmt)
236 void **p = pointer_map_contains (lim_aux_data_map, stmt);
237 if (!p)
238 return NULL;
240 return (struct lim_aux_data *) *p;
243 /* Releases the memory occupied by DATA. */
245 static void
246 free_lim_aux_data (struct lim_aux_data *data)
248 data->depends.release ();
249 free (data);
252 static void
253 clear_lim_data (gimple stmt)
255 void **p = pointer_map_contains (lim_aux_data_map, stmt);
256 if (!p)
257 return;
259 free_lim_aux_data ((struct lim_aux_data *) *p);
260 *p = NULL;
264 /* The possibilities of statement movement. */
265 enum move_pos
267 MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
268 MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
269 become executed -- memory accesses, ... */
270 MOVE_POSSIBLE /* Unlimited movement. */
274 /* If it is possible to hoist the statement STMT unconditionally,
275 returns MOVE_POSSIBLE.
276 If it is possible to hoist the statement STMT, but we must avoid making
277 it executed if it would not be executed in the original program (e.g.
278 because it may trap), return MOVE_PRESERVE_EXECUTION.
279 Otherwise return MOVE_IMPOSSIBLE. */
281 enum move_pos
282 movement_possibility (gimple stmt)
284 tree lhs;
285 enum move_pos ret = MOVE_POSSIBLE;
287 if (flag_unswitch_loops
288 && gimple_code (stmt) == GIMPLE_COND)
290 /* If we perform unswitching, force the operands of the invariant
291 condition to be moved out of the loop. */
292 return MOVE_POSSIBLE;
295 if (gimple_code (stmt) == GIMPLE_PHI
296 && gimple_phi_num_args (stmt) <= 2
297 && !virtual_operand_p (gimple_phi_result (stmt))
298 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
299 return MOVE_POSSIBLE;
301 if (gimple_get_lhs (stmt) == NULL_TREE)
302 return MOVE_IMPOSSIBLE;
304 if (gimple_vdef (stmt))
305 return MOVE_IMPOSSIBLE;
307 if (stmt_ends_bb_p (stmt)
308 || gimple_has_volatile_ops (stmt)
309 || gimple_has_side_effects (stmt)
310 || stmt_could_throw_p (stmt))
311 return MOVE_IMPOSSIBLE;
313 if (is_gimple_call (stmt))
315 /* While pure or const call is guaranteed to have no side effects, we
316 cannot move it arbitrarily. Consider code like
318 char *s = something ();
320 while (1)
322 if (s)
323 t = strlen (s);
324 else
325 t = 0;
328 Here the strlen call cannot be moved out of the loop, even though
329 s is invariant. In addition to possibly creating a call with
330 invalid arguments, moving out a function call that is not executed
331 may cause performance regressions in case the call is costly and
332 not executed at all. */
333 ret = MOVE_PRESERVE_EXECUTION;
334 lhs = gimple_call_lhs (stmt);
336 else if (is_gimple_assign (stmt))
337 lhs = gimple_assign_lhs (stmt);
338 else
339 return MOVE_IMPOSSIBLE;
341 if (TREE_CODE (lhs) == SSA_NAME
342 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
343 return MOVE_IMPOSSIBLE;
345 if (TREE_CODE (lhs) != SSA_NAME
346 || gimple_could_trap_p (stmt))
347 return MOVE_PRESERVE_EXECUTION;
349 /* Non local loads in a transaction cannot be hoisted out. Well,
350 unless the load happens on every path out of the loop, but we
351 don't take this into account yet. */
352 if (flag_tm
353 && gimple_in_transaction (stmt)
354 && gimple_assign_single_p (stmt))
356 tree rhs = gimple_assign_rhs1 (stmt);
357 if (DECL_P (rhs) && is_global_var (rhs))
359 if (dump_file)
361 fprintf (dump_file, "Cannot hoist conditional load of ");
362 print_generic_expr (dump_file, rhs, TDF_SLIM);
363 fprintf (dump_file, " because it is in a transaction.\n");
365 return MOVE_IMPOSSIBLE;
369 return ret;
372 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
373 loop to that we could move the expression using DEF if it did not have
374 other operands, i.e. the outermost loop enclosing LOOP in that the value
375 of DEF is invariant. */
377 static struct loop *
378 outermost_invariant_loop (tree def, struct loop *loop)
380 gimple def_stmt;
381 basic_block def_bb;
382 struct loop *max_loop;
383 struct lim_aux_data *lim_data;
385 if (!def)
386 return superloop_at_depth (loop, 1);
388 if (TREE_CODE (def) != SSA_NAME)
390 gcc_assert (is_gimple_min_invariant (def));
391 return superloop_at_depth (loop, 1);
394 def_stmt = SSA_NAME_DEF_STMT (def);
395 def_bb = gimple_bb (def_stmt);
396 if (!def_bb)
397 return superloop_at_depth (loop, 1);
399 max_loop = find_common_loop (loop, def_bb->loop_father);
401 lim_data = get_lim_data (def_stmt);
402 if (lim_data != NULL && lim_data->max_loop != NULL)
403 max_loop = find_common_loop (max_loop,
404 loop_outer (lim_data->max_loop));
405 if (max_loop == loop)
406 return NULL;
407 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
409 return max_loop;
412 /* DATA is a structure containing information associated with a statement
413 inside LOOP. DEF is one of the operands of this statement.
415 Find the outermost loop enclosing LOOP in that value of DEF is invariant
416 and record this in DATA->max_loop field. If DEF itself is defined inside
417 this loop as well (i.e. we need to hoist it out of the loop if we want
418 to hoist the statement represented by DATA), record the statement in that
419 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
420 add the cost of the computation of DEF to the DATA->cost.
422 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
424 static bool
425 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
426 bool add_cost)
428 gimple def_stmt = SSA_NAME_DEF_STMT (def);
429 basic_block def_bb = gimple_bb (def_stmt);
430 struct loop *max_loop;
431 struct lim_aux_data *def_data;
433 if (!def_bb)
434 return true;
436 max_loop = outermost_invariant_loop (def, loop);
437 if (!max_loop)
438 return false;
440 if (flow_loop_nested_p (data->max_loop, max_loop))
441 data->max_loop = max_loop;
443 def_data = get_lim_data (def_stmt);
444 if (!def_data)
445 return true;
447 if (add_cost
448 /* Only add the cost if the statement defining DEF is inside LOOP,
449 i.e. if it is likely that by moving the invariants dependent
450 on it, we will be able to avoid creating a new register for
451 it (since it will be only used in these dependent invariants). */
452 && def_bb->loop_father == loop)
453 data->cost += def_data->cost;
455 data->depends.safe_push (def_stmt);
457 return true;
460 /* Returns an estimate for a cost of statement STMT. The values here
461 are just ad-hoc constants, similar to costs for inlining. */
463 static unsigned
464 stmt_cost (gimple stmt)
466 /* Always try to create possibilities for unswitching. */
467 if (gimple_code (stmt) == GIMPLE_COND
468 || gimple_code (stmt) == GIMPLE_PHI)
469 return LIM_EXPENSIVE;
471 /* We should be hoisting calls if possible. */
472 if (is_gimple_call (stmt))
474 tree fndecl;
476 /* Unless the call is a builtin_constant_p; this always folds to a
477 constant, so moving it is useless. */
478 fndecl = gimple_call_fndecl (stmt);
479 if (fndecl
480 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
481 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
482 return 0;
484 return LIM_EXPENSIVE;
487 /* Hoisting memory references out should almost surely be a win. */
488 if (gimple_references_memory_p (stmt))
489 return LIM_EXPENSIVE;
491 if (gimple_code (stmt) != GIMPLE_ASSIGN)
492 return 1;
494 switch (gimple_assign_rhs_code (stmt))
496 case MULT_EXPR:
497 case WIDEN_MULT_EXPR:
498 case WIDEN_MULT_PLUS_EXPR:
499 case WIDEN_MULT_MINUS_EXPR:
500 case DOT_PROD_EXPR:
501 case FMA_EXPR:
502 case TRUNC_DIV_EXPR:
503 case CEIL_DIV_EXPR:
504 case FLOOR_DIV_EXPR:
505 case ROUND_DIV_EXPR:
506 case EXACT_DIV_EXPR:
507 case CEIL_MOD_EXPR:
508 case FLOOR_MOD_EXPR:
509 case ROUND_MOD_EXPR:
510 case TRUNC_MOD_EXPR:
511 case RDIV_EXPR:
512 /* Division and multiplication are usually expensive. */
513 return LIM_EXPENSIVE;
515 case LSHIFT_EXPR:
516 case RSHIFT_EXPR:
517 case WIDEN_LSHIFT_EXPR:
518 case LROTATE_EXPR:
519 case RROTATE_EXPR:
520 /* Shifts and rotates are usually expensive. */
521 return LIM_EXPENSIVE;
523 case CONSTRUCTOR:
524 /* Make vector construction cost proportional to the number
525 of elements. */
526 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
528 case SSA_NAME:
529 case PAREN_EXPR:
530 /* Whether or not something is wrapped inside a PAREN_EXPR
531 should not change move cost. Nor should an intermediate
532 unpropagated SSA name copy. */
533 return 0;
535 default:
536 return 1;
540 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
541 REF is independent. If REF is not independent in LOOP, NULL is returned
542 instead. */
544 static struct loop *
545 outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
547 struct loop *aloop;
549 if (bitmap_bit_p (&ref->stored, loop->num))
550 return NULL;
552 for (aloop = outer;
553 aloop != loop;
554 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
555 if (!bitmap_bit_p (&ref->stored, aloop->num)
556 && ref_indep_loop_p (aloop, ref))
557 return aloop;
559 if (ref_indep_loop_p (loop, ref))
560 return loop;
561 else
562 return NULL;
565 /* If there is a simple load or store to a memory reference in STMT, returns
566 the location of the memory reference, and sets IS_STORE according to whether
567 it is a store or load. Otherwise, returns NULL. */
569 static tree *
570 simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
572 tree *lhs, *rhs;
574 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
575 if (!gimple_assign_single_p (stmt))
576 return NULL;
578 lhs = gimple_assign_lhs_ptr (stmt);
579 rhs = gimple_assign_rhs1_ptr (stmt);
581 if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
583 *is_store = false;
584 return rhs;
586 else if (gimple_vdef (stmt)
587 && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
589 *is_store = true;
590 return lhs;
592 else
593 return NULL;
596 /* Returns the memory reference contained in STMT. */
598 static mem_ref_p
599 mem_ref_in_stmt (gimple stmt)
601 bool store;
602 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
603 hashval_t hash;
604 mem_ref_p ref;
606 if (!mem)
607 return NULL;
608 gcc_assert (!store);
610 hash = iterative_hash_expr (*mem, 0);
611 ref = memory_accesses.refs.find_with_hash (*mem, hash);
613 gcc_assert (ref != NULL);
614 return ref;
617 /* From a controlling predicate in DOM determine the arguments from
618 the PHI node PHI that are chosen if the predicate evaluates to
619 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
620 they are non-NULL. Returns true if the arguments can be determined,
621 else return false. */
623 static bool
624 extract_true_false_args_from_phi (basic_block dom, gimple phi,
625 tree *true_arg_p, tree *false_arg_p)
627 basic_block bb = gimple_bb (phi);
628 edge true_edge, false_edge, tem;
629 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
631 /* We have to verify that one edge into the PHI node is dominated
632 by the true edge of the predicate block and the other edge
633 dominated by the false edge. This ensures that the PHI argument
634 we are going to take is completely determined by the path we
635 take from the predicate block.
636 We can only use BB dominance checks below if the destination of
637 the true/false edges are dominated by their edge, thus only
638 have a single predecessor. */
639 extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
640 tem = EDGE_PRED (bb, 0);
641 if (tem == true_edge
642 || (single_pred_p (true_edge->dest)
643 && (tem->src == true_edge->dest
644 || dominated_by_p (CDI_DOMINATORS,
645 tem->src, true_edge->dest))))
646 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
647 else if (tem == false_edge
648 || (single_pred_p (false_edge->dest)
649 && (tem->src == false_edge->dest
650 || dominated_by_p (CDI_DOMINATORS,
651 tem->src, false_edge->dest))))
652 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
653 else
654 return false;
655 tem = EDGE_PRED (bb, 1);
656 if (tem == true_edge
657 || (single_pred_p (true_edge->dest)
658 && (tem->src == true_edge->dest
659 || dominated_by_p (CDI_DOMINATORS,
660 tem->src, true_edge->dest))))
661 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
662 else if (tem == false_edge
663 || (single_pred_p (false_edge->dest)
664 && (tem->src == false_edge->dest
665 || dominated_by_p (CDI_DOMINATORS,
666 tem->src, false_edge->dest))))
667 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
668 else
669 return false;
670 if (!arg0 || !arg1)
671 return false;
673 if (true_arg_p)
674 *true_arg_p = arg0;
675 if (false_arg_p)
676 *false_arg_p = arg1;
678 return true;
681 /* Determine the outermost loop to that it is possible to hoist a statement
682 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
683 the outermost loop in that the value computed by STMT is invariant.
684 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
685 we preserve the fact whether STMT is executed. It also fills other related
686 information to LIM_DATA (STMT).
688 The function returns false if STMT cannot be hoisted outside of the loop it
689 is defined in, and true otherwise. */
691 static bool
692 determine_max_movement (gimple stmt, bool must_preserve_exec)
694 basic_block bb = gimple_bb (stmt);
695 struct loop *loop = bb->loop_father;
696 struct loop *level;
697 struct lim_aux_data *lim_data = get_lim_data (stmt);
698 tree val;
699 ssa_op_iter iter;
701 if (must_preserve_exec)
702 level = ALWAYS_EXECUTED_IN (bb);
703 else
704 level = superloop_at_depth (loop, 1);
705 lim_data->max_loop = level;
707 if (gimple_code (stmt) == GIMPLE_PHI)
709 use_operand_p use_p;
710 unsigned min_cost = UINT_MAX;
711 unsigned total_cost = 0;
712 struct lim_aux_data *def_data;
714 /* We will end up promoting dependencies to be unconditionally
715 evaluated. For this reason the PHI cost (and thus the
716 cost we remove from the loop by doing the invariant motion)
717 is that of the cheapest PHI argument dependency chain. */
718 FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
720 val = USE_FROM_PTR (use_p);
721 if (TREE_CODE (val) != SSA_NAME)
722 continue;
723 if (!add_dependency (val, lim_data, loop, false))
724 return false;
725 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
726 if (def_data)
728 min_cost = MIN (min_cost, def_data->cost);
729 total_cost += def_data->cost;
733 lim_data->cost += min_cost;
735 if (gimple_phi_num_args (stmt) > 1)
737 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
738 gimple cond;
739 if (gsi_end_p (gsi_last_bb (dom)))
740 return false;
741 cond = gsi_stmt (gsi_last_bb (dom));
742 if (gimple_code (cond) != GIMPLE_COND)
743 return false;
744 /* Verify that this is an extended form of a diamond and
745 the PHI arguments are completely controlled by the
746 predicate in DOM. */
747 if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL))
748 return false;
750 /* Fold in dependencies and cost of the condition. */
751 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
753 if (!add_dependency (val, lim_data, loop, false))
754 return false;
755 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
756 if (def_data)
757 total_cost += def_data->cost;
760 /* We want to avoid unconditionally executing very expensive
761 operations. As costs for our dependencies cannot be
762 negative just claim we are not invariand for this case.
763 We also are not sure whether the control-flow inside the
764 loop will vanish. */
765 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
766 && !(min_cost != 0
767 && total_cost / min_cost <= 2))
768 return false;
770 /* Assume that the control-flow in the loop will vanish.
771 ??? We should verify this and not artificially increase
772 the cost if that is not the case. */
773 lim_data->cost += stmt_cost (stmt);
776 return true;
778 else
779 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
780 if (!add_dependency (val, lim_data, loop, true))
781 return false;
783 if (gimple_vuse (stmt))
785 mem_ref_p ref = mem_ref_in_stmt (stmt);
787 if (ref)
789 lim_data->max_loop
790 = outermost_indep_loop (lim_data->max_loop, loop, ref);
791 if (!lim_data->max_loop)
792 return false;
794 else
796 if ((val = gimple_vuse (stmt)) != NULL_TREE)
798 if (!add_dependency (val, lim_data, loop, false))
799 return false;
804 lim_data->cost += stmt_cost (stmt);
806 return true;
809 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
810 and that one of the operands of this statement is computed by STMT.
811 Ensure that STMT (together with all the statements that define its
812 operands) is hoisted at least out of the loop LEVEL. */
814 static void
815 set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
817 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
818 struct lim_aux_data *lim_data;
819 gimple dep_stmt;
820 unsigned i;
822 stmt_loop = find_common_loop (orig_loop, stmt_loop);
823 lim_data = get_lim_data (stmt);
824 if (lim_data != NULL && lim_data->tgt_loop != NULL)
825 stmt_loop = find_common_loop (stmt_loop,
826 loop_outer (lim_data->tgt_loop));
827 if (flow_loop_nested_p (stmt_loop, level))
828 return;
830 gcc_assert (level == lim_data->max_loop
831 || flow_loop_nested_p (lim_data->max_loop, level));
833 lim_data->tgt_loop = level;
834 FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
835 set_level (dep_stmt, orig_loop, level);
838 /* Determines an outermost loop from that we want to hoist the statement STMT.
839 For now we chose the outermost possible loop. TODO -- use profiling
840 information to set it more sanely. */
842 static void
843 set_profitable_level (gimple stmt)
845 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
848 /* Returns true if STMT is a call that has side effects. */
850 static bool
851 nonpure_call_p (gimple stmt)
853 if (gimple_code (stmt) != GIMPLE_CALL)
854 return false;
856 return gimple_has_side_effects (stmt);
859 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
861 static gimple
862 rewrite_reciprocal (gimple_stmt_iterator *bsi)
864 gimple stmt, stmt1, stmt2;
865 tree name, lhs, type;
866 tree real_one;
867 gimple_stmt_iterator gsi;
869 stmt = gsi_stmt (*bsi);
870 lhs = gimple_assign_lhs (stmt);
871 type = TREE_TYPE (lhs);
873 real_one = build_one_cst (type);
875 name = make_temp_ssa_name (type, NULL, "reciptmp");
876 stmt1 = gimple_build_assign_with_ops (RDIV_EXPR, name, real_one,
877 gimple_assign_rhs2 (stmt));
879 stmt2 = gimple_build_assign_with_ops (MULT_EXPR, lhs, name,
880 gimple_assign_rhs1 (stmt));
882 /* Replace division stmt with reciprocal and multiply stmts.
883 The multiply stmt is not invariant, so update iterator
884 and avoid rescanning. */
885 gsi = *bsi;
886 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
887 gsi_replace (&gsi, stmt2, true);
889 /* Continue processing with invariant reciprocal statement. */
890 return stmt1;
893 /* Check if the pattern at *BSI is a bittest of the form
894 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
896 static gimple
897 rewrite_bittest (gimple_stmt_iterator *bsi)
899 gimple stmt, use_stmt, stmt1, stmt2;
900 tree lhs, name, t, a, b;
901 use_operand_p use;
903 stmt = gsi_stmt (*bsi);
904 lhs = gimple_assign_lhs (stmt);
906 /* Verify that the single use of lhs is a comparison against zero. */
907 if (TREE_CODE (lhs) != SSA_NAME
908 || !single_imm_use (lhs, &use, &use_stmt)
909 || gimple_code (use_stmt) != GIMPLE_COND)
910 return stmt;
911 if (gimple_cond_lhs (use_stmt) != lhs
912 || (gimple_cond_code (use_stmt) != NE_EXPR
913 && gimple_cond_code (use_stmt) != EQ_EXPR)
914 || !integer_zerop (gimple_cond_rhs (use_stmt)))
915 return stmt;
917 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
918 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
919 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
920 return stmt;
922 /* There is a conversion in between possibly inserted by fold. */
923 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
925 t = gimple_assign_rhs1 (stmt1);
926 if (TREE_CODE (t) != SSA_NAME
927 || !has_single_use (t))
928 return stmt;
929 stmt1 = SSA_NAME_DEF_STMT (t);
930 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
931 return stmt;
934 /* Verify that B is loop invariant but A is not. Verify that with
935 all the stmt walking we are still in the same loop. */
936 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
937 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
938 return stmt;
940 a = gimple_assign_rhs1 (stmt1);
941 b = gimple_assign_rhs2 (stmt1);
943 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
944 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
946 gimple_stmt_iterator rsi;
948 /* 1 << B */
949 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
950 build_int_cst (TREE_TYPE (a), 1), b);
951 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
952 stmt1 = gimple_build_assign (name, t);
954 /* A & (1 << B) */
955 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
956 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
957 stmt2 = gimple_build_assign (name, t);
959 /* Replace the SSA_NAME we compare against zero. Adjust
960 the type of zero accordingly. */
961 SET_USE (use, name);
962 gimple_cond_set_rhs (use_stmt, build_int_cst_type (TREE_TYPE (name), 0));
964 /* Don't use gsi_replace here, none of the new assignments sets
965 the variable originally set in stmt. Move bsi to stmt1, and
966 then remove the original stmt, so that we get a chance to
967 retain debug info for it. */
968 rsi = *bsi;
969 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
970 gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
971 gsi_remove (&rsi, true);
973 return stmt1;
976 return stmt;
979 /* For each statement determines the outermost loop in that it is invariant,
980 - statements on whose motion it depends and the cost of the computation.
981 - This information is stored to the LIM_DATA structure associated with
982 - each statement. */
983 class invariantness_dom_walker : public dom_walker
985 public:
986 invariantness_dom_walker (cdi_direction direction)
987 : dom_walker (direction) {}
989 virtual void before_dom_children (basic_block);
992 /* Determine the outermost loops in that statements in basic block BB are
993 invariant, and record them to the LIM_DATA associated with the statements.
994 Callback for dom_walker. */
996 void
997 invariantness_dom_walker::before_dom_children (basic_block bb)
999 enum move_pos pos;
1000 gimple_stmt_iterator bsi;
1001 gimple stmt;
1002 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
1003 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
1004 struct lim_aux_data *lim_data;
1006 if (!loop_outer (bb->loop_father))
1007 return;
1009 if (dump_file && (dump_flags & TDF_DETAILS))
1010 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
1011 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
1013 /* Look at PHI nodes, but only if there is at most two.
1014 ??? We could relax this further by post-processing the inserted
1015 code and transforming adjacent cond-exprs with the same predicate
1016 to control flow again. */
1017 bsi = gsi_start_phis (bb);
1018 if (!gsi_end_p (bsi)
1019 && ((gsi_next (&bsi), gsi_end_p (bsi))
1020 || (gsi_next (&bsi), gsi_end_p (bsi))))
1021 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1023 stmt = gsi_stmt (bsi);
1025 pos = movement_possibility (stmt);
1026 if (pos == MOVE_IMPOSSIBLE)
1027 continue;
1029 lim_data = init_lim_data (stmt);
1030 lim_data->always_executed_in = outermost;
1032 if (!determine_max_movement (stmt, false))
1034 lim_data->max_loop = NULL;
1035 continue;
1038 if (dump_file && (dump_flags & TDF_DETAILS))
1040 print_gimple_stmt (dump_file, stmt, 2, 0);
1041 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1042 loop_depth (lim_data->max_loop),
1043 lim_data->cost);
1046 if (lim_data->cost >= LIM_EXPENSIVE)
1047 set_profitable_level (stmt);
1050 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1052 stmt = gsi_stmt (bsi);
1054 pos = movement_possibility (stmt);
1055 if (pos == MOVE_IMPOSSIBLE)
1057 if (nonpure_call_p (stmt))
1059 maybe_never = true;
1060 outermost = NULL;
1062 /* Make sure to note always_executed_in for stores to make
1063 store-motion work. */
1064 else if (stmt_makes_single_store (stmt))
1066 struct lim_aux_data *lim_data = init_lim_data (stmt);
1067 lim_data->always_executed_in = outermost;
1069 continue;
1072 if (is_gimple_assign (stmt)
1073 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1074 == GIMPLE_BINARY_RHS))
1076 tree op0 = gimple_assign_rhs1 (stmt);
1077 tree op1 = gimple_assign_rhs2 (stmt);
1078 struct loop *ol1 = outermost_invariant_loop (op1,
1079 loop_containing_stmt (stmt));
1081 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1082 to be hoisted out of loop, saving expensive divide. */
1083 if (pos == MOVE_POSSIBLE
1084 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
1085 && flag_unsafe_math_optimizations
1086 && !flag_trapping_math
1087 && ol1 != NULL
1088 && outermost_invariant_loop (op0, ol1) == NULL)
1089 stmt = rewrite_reciprocal (&bsi);
1091 /* If the shift count is invariant, convert (A >> B) & 1 to
1092 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1093 saving an expensive shift. */
1094 if (pos == MOVE_POSSIBLE
1095 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
1096 && integer_onep (op1)
1097 && TREE_CODE (op0) == SSA_NAME
1098 && has_single_use (op0))
1099 stmt = rewrite_bittest (&bsi);
1102 lim_data = init_lim_data (stmt);
1103 lim_data->always_executed_in = outermost;
1105 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1106 continue;
1108 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1110 lim_data->max_loop = NULL;
1111 continue;
1114 if (dump_file && (dump_flags & TDF_DETAILS))
1116 print_gimple_stmt (dump_file, stmt, 2, 0);
1117 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1118 loop_depth (lim_data->max_loop),
1119 lim_data->cost);
1122 if (lim_data->cost >= LIM_EXPENSIVE)
1123 set_profitable_level (stmt);
1127 class move_computations_dom_walker : public dom_walker
1129 public:
1130 move_computations_dom_walker (cdi_direction direction)
1131 : dom_walker (direction), todo_ (0) {}
1133 virtual void before_dom_children (basic_block);
1135 unsigned int todo_;
1138 /* Return true if CODE is an operation that when operating on signed
1139 integer types involves undefined behavior on overflow and the
1140 operation can be expressed with unsigned arithmetic. */
1142 static bool
1143 arith_code_with_undefined_signed_overflow (tree_code code)
1145 switch (code)
1147 case PLUS_EXPR:
1148 case MINUS_EXPR:
1149 case MULT_EXPR:
1150 case NEGATE_EXPR:
1151 case POINTER_PLUS_EXPR:
1152 return true;
1153 default:
1154 return false;
1158 /* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
1159 operation that can be transformed to unsigned arithmetic by converting
1160 its operand, carrying out the operation in the corresponding unsigned
1161 type and converting the result back to the original type.
1163 Returns a sequence of statements that replace STMT and also contain
1164 a modified form of STMT itself. */
1166 static gimple_seq
1167 rewrite_to_defined_overflow (gimple stmt)
1169 if (dump_file && (dump_flags & TDF_DETAILS))
1171 fprintf (dump_file, "rewriting stmt with undefined signed "
1172 "overflow ");
1173 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1176 tree lhs = gimple_assign_lhs (stmt);
1177 tree type = unsigned_type_for (TREE_TYPE (lhs));
1178 gimple_seq stmts = NULL;
1179 for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
1181 gimple_seq stmts2 = NULL;
1182 gimple_set_op (stmt, i,
1183 force_gimple_operand (fold_convert (type,
1184 gimple_op (stmt, i)),
1185 &stmts2, true, NULL_TREE));
1186 gimple_seq_add_seq (&stmts, stmts2);
1188 gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt));
1189 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1190 gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
1191 gimple_seq_add_stmt (&stmts, stmt);
1192 gimple cvt = gimple_build_assign_with_ops
1193 (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE);
1194 gimple_seq_add_stmt (&stmts, cvt);
1196 return stmts;
1199 /* Hoist the statements in basic block BB out of the loops prescribed by
1200 data stored in LIM_DATA structures associated with each statement. Callback
1201 for walk_dominator_tree. */
1203 void
1204 move_computations_dom_walker::before_dom_children (basic_block bb)
1206 struct loop *level;
1207 gimple_stmt_iterator bsi;
1208 gimple stmt;
1209 unsigned cost = 0;
1210 struct lim_aux_data *lim_data;
1212 if (!loop_outer (bb->loop_father))
1213 return;
1215 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1217 gimple new_stmt;
1218 stmt = gsi_stmt (bsi);
1220 lim_data = get_lim_data (stmt);
1221 if (lim_data == NULL)
1223 gsi_next (&bsi);
1224 continue;
1227 cost = lim_data->cost;
1228 level = lim_data->tgt_loop;
1229 clear_lim_data (stmt);
1231 if (!level)
1233 gsi_next (&bsi);
1234 continue;
1237 if (dump_file && (dump_flags & TDF_DETAILS))
1239 fprintf (dump_file, "Moving PHI node\n");
1240 print_gimple_stmt (dump_file, stmt, 0, 0);
1241 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1242 cost, level->num);
1245 if (gimple_phi_num_args (stmt) == 1)
1247 tree arg = PHI_ARG_DEF (stmt, 0);
1248 new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
1249 gimple_phi_result (stmt),
1250 arg, NULL_TREE);
1252 else
1254 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
1255 gimple cond = gsi_stmt (gsi_last_bb (dom));
1256 tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
1257 /* Get the PHI arguments corresponding to the true and false
1258 edges of COND. */
1259 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
1260 gcc_assert (arg0 && arg1);
1261 t = build2 (gimple_cond_code (cond), boolean_type_node,
1262 gimple_cond_lhs (cond), gimple_cond_rhs (cond));
1263 new_stmt = gimple_build_assign_with_ops (COND_EXPR,
1264 gimple_phi_result (stmt),
1265 t, arg0, arg1);
1266 todo_ |= TODO_cleanup_cfg;
1268 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1269 remove_phi_node (&bsi, false);
1272 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1274 edge e;
1276 stmt = gsi_stmt (bsi);
1278 lim_data = get_lim_data (stmt);
1279 if (lim_data == NULL)
1281 gsi_next (&bsi);
1282 continue;
1285 cost = lim_data->cost;
1286 level = lim_data->tgt_loop;
1287 clear_lim_data (stmt);
1289 if (!level)
1291 gsi_next (&bsi);
1292 continue;
1295 /* We do not really want to move conditionals out of the loop; we just
1296 placed it here to force its operands to be moved if necessary. */
1297 if (gimple_code (stmt) == GIMPLE_COND)
1298 continue;
1300 if (dump_file && (dump_flags & TDF_DETAILS))
1302 fprintf (dump_file, "Moving statement\n");
1303 print_gimple_stmt (dump_file, stmt, 0, 0);
1304 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1305 cost, level->num);
1308 e = loop_preheader_edge (level);
1309 gcc_assert (!gimple_vdef (stmt));
1310 if (gimple_vuse (stmt))
1312 /* The new VUSE is the one from the virtual PHI in the loop
1313 header or the one already present. */
1314 gimple_stmt_iterator gsi2;
1315 for (gsi2 = gsi_start_phis (e->dest);
1316 !gsi_end_p (gsi2); gsi_next (&gsi2))
1318 gimple phi = gsi_stmt (gsi2);
1319 if (virtual_operand_p (gimple_phi_result (phi)))
1321 gimple_set_vuse (stmt, PHI_ARG_DEF_FROM_EDGE (phi, e));
1322 break;
1326 gsi_remove (&bsi, false);
1327 /* In case this is a stmt that is not unconditionally executed
1328 when the target loop header is executed and the stmt may
1329 invoke undefined integer or pointer overflow rewrite it to
1330 unsigned arithmetic. */
1331 if (is_gimple_assign (stmt)
1332 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
1333 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
1334 && arith_code_with_undefined_signed_overflow
1335 (gimple_assign_rhs_code (stmt))
1336 && (!ALWAYS_EXECUTED_IN (bb)
1337 || !(ALWAYS_EXECUTED_IN (bb) == level
1338 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1339 gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
1340 else
1341 gsi_insert_on_edge (e, stmt);
1345 /* Hoist the statements out of the loops prescribed by data stored in
1346 LIM_DATA structures associated with each statement.*/
1348 static unsigned int
1349 move_computations (void)
1351 move_computations_dom_walker walker (CDI_DOMINATORS);
1352 walker.walk (cfun->cfg->x_entry_block_ptr);
1354 gsi_commit_edge_inserts ();
1355 if (need_ssa_update_p (cfun))
1356 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1358 return walker.todo_;
1361 /* Checks whether the statement defining variable *INDEX can be hoisted
1362 out of the loop passed in DATA. Callback for for_each_index. */
1364 static bool
1365 may_move_till (tree ref, tree *index, void *data)
1367 struct loop *loop = (struct loop *) data, *max_loop;
1369 /* If REF is an array reference, check also that the step and the lower
1370 bound is invariant in LOOP. */
1371 if (TREE_CODE (ref) == ARRAY_REF)
1373 tree step = TREE_OPERAND (ref, 3);
1374 tree lbound = TREE_OPERAND (ref, 2);
1376 max_loop = outermost_invariant_loop (step, loop);
1377 if (!max_loop)
1378 return false;
1380 max_loop = outermost_invariant_loop (lbound, loop);
1381 if (!max_loop)
1382 return false;
1385 max_loop = outermost_invariant_loop (*index, loop);
1386 if (!max_loop)
1387 return false;
1389 return true;
1392 /* If OP is SSA NAME, force the statement that defines it to be
1393 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1395 static void
1396 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1398 gimple stmt;
1400 if (!op
1401 || is_gimple_min_invariant (op))
1402 return;
1404 gcc_assert (TREE_CODE (op) == SSA_NAME);
1406 stmt = SSA_NAME_DEF_STMT (op);
1407 if (gimple_nop_p (stmt))
1408 return;
1410 set_level (stmt, orig_loop, loop);
1413 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1414 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1415 for_each_index. */
1417 struct fmt_data
1419 struct loop *loop;
1420 struct loop *orig_loop;
1423 static bool
1424 force_move_till (tree ref, tree *index, void *data)
1426 struct fmt_data *fmt_data = (struct fmt_data *) data;
1428 if (TREE_CODE (ref) == ARRAY_REF)
1430 tree step = TREE_OPERAND (ref, 3);
1431 tree lbound = TREE_OPERAND (ref, 2);
1433 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1434 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1437 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1439 return true;
1442 /* A function to free the mem_ref object OBJ. */
1444 static void
1445 memref_free (struct mem_ref *mem)
1447 unsigned i;
1448 vec<mem_ref_loc> *accs;
1450 FOR_EACH_VEC_ELT (mem->accesses_in_loop, i, accs)
1451 accs->release ();
1452 mem->accesses_in_loop.release ();
1454 free (mem);
1457 /* Allocates and returns a memory reference description for MEM whose hash
1458 value is HASH and id is ID. */
1460 static mem_ref_p
1461 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1463 mem_ref_p ref = XNEW (struct mem_ref);
1464 ao_ref_init (&ref->mem, mem);
1465 ref->id = id;
1466 ref->hash = hash;
1467 bitmap_initialize (&ref->stored, &lim_bitmap_obstack);
1468 bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
1469 bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
1470 ref->accesses_in_loop.create (0);
1472 return ref;
1475 /* Records memory reference location *LOC in LOOP to the memory reference
1476 description REF. The reference occurs in statement STMT. */
1478 static void
1479 record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
1481 mem_ref_loc aref;
1483 if (ref->accesses_in_loop.length ()
1484 <= (unsigned) loop->num)
1485 ref->accesses_in_loop.safe_grow_cleared (loop->num + 1);
1487 aref.stmt = stmt;
1488 aref.ref = loc;
1489 ref->accesses_in_loop[loop->num].safe_push (aref);
1492 /* Marks reference REF as stored in LOOP. */
1494 static void
1495 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1497 while (loop != current_loops->tree_root
1498 && bitmap_set_bit (&ref->stored, loop->num))
1499 loop = loop_outer (loop);
1502 /* Gathers memory references in statement STMT in LOOP, storing the
1503 information about them in the memory_accesses structure. Marks
1504 the vops accessed through unrecognized statements there as
1505 well. */
1507 static void
1508 gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1510 tree *mem = NULL;
1511 hashval_t hash;
1512 mem_ref **slot;
1513 mem_ref_p ref;
1514 bool is_stored;
1515 unsigned id;
1517 if (!gimple_vuse (stmt))
1518 return;
1520 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1521 if (!mem)
1523 /* We use the shared mem_ref for all unanalyzable refs. */
1524 id = UNANALYZABLE_MEM_ID;
1525 ref = memory_accesses.refs_list[id];
1526 if (dump_file && (dump_flags & TDF_DETAILS))
1528 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
1529 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1531 is_stored = gimple_vdef (stmt);
1533 else
1535 hash = iterative_hash_expr (*mem, 0);
1536 slot = memory_accesses.refs.find_slot_with_hash (*mem, hash, INSERT);
1537 if (*slot)
1539 ref = (mem_ref_p) *slot;
1540 id = ref->id;
1542 else
1544 id = memory_accesses.refs_list.length ();
1545 ref = mem_ref_alloc (*mem, hash, id);
1546 memory_accesses.refs_list.safe_push (ref);
1547 *slot = ref;
1549 if (dump_file && (dump_flags & TDF_DETAILS))
1551 fprintf (dump_file, "Memory reference %u: ", id);
1552 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
1553 fprintf (dump_file, "\n");
1557 record_mem_ref_loc (ref, loop, stmt, mem);
1559 bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
1560 if (is_stored)
1562 bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
1563 mark_ref_stored (ref, loop);
1565 return;
1568 static unsigned *bb_loop_postorder;
1570 /* qsort sort function to sort blocks after their loop fathers postorder. */
1572 static int
1573 sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
1575 basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
1576 basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
1577 struct loop *loop1 = bb1->loop_father;
1578 struct loop *loop2 = bb2->loop_father;
1579 if (loop1->num == loop2->num)
1580 return 0;
1581 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1584 /* Gathers memory references in loops. */
1586 static void
1587 analyze_memory_references (void)
1589 gimple_stmt_iterator bsi;
1590 basic_block bb, *bbs;
1591 struct loop *loop, *outer;
1592 unsigned i, n;
1594 /* Initialize bb_loop_postorder with a mapping from loop->num to
1595 its postorder index. */
1596 i = 0;
1597 bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
1598 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1599 bb_loop_postorder[loop->num] = i++;
1600 /* Collect all basic-blocks in loops and sort them after their
1601 loops postorder. */
1602 i = 0;
1603 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
1604 FOR_EACH_BB_FN (bb, cfun)
1605 if (bb->loop_father != current_loops->tree_root)
1606 bbs[i++] = bb;
1607 n = i;
1608 qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
1609 free (bb_loop_postorder);
1611 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1612 That results in better locality for all the bitmaps. */
1613 for (i = 0; i < n; ++i)
1615 basic_block bb = bbs[i];
1616 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1617 gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
1620 free (bbs);
1622 /* Propagate the information about accessed memory references up
1623 the loop hierarchy. */
1624 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1626 /* Finalize the overall touched references (including subloops). */
1627 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
1628 &memory_accesses.refs_stored_in_loop[loop->num]);
1630 /* Propagate the information about accessed memory references up
1631 the loop hierarchy. */
1632 outer = loop_outer (loop);
1633 if (outer == current_loops->tree_root)
1634 continue;
1636 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
1637 &memory_accesses.all_refs_stored_in_loop[loop->num]);
1641 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1642 tree_to_aff_combination_expand. */
1644 static bool
1645 mem_refs_may_alias_p (mem_ref_p mem1, mem_ref_p mem2,
1646 struct pointer_map_t **ttae_cache)
1648 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1649 object and their offset differ in such a way that the locations cannot
1650 overlap, then they cannot alias. */
1651 double_int size1, size2;
1652 aff_tree off1, off2;
1654 /* Perform basic offset and type-based disambiguation. */
1655 if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
1656 return false;
1658 /* The expansion of addresses may be a bit expensive, thus we only do
1659 the check at -O2 and higher optimization levels. */
1660 if (optimize < 2)
1661 return true;
1663 get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
1664 get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
1665 aff_combination_expand (&off1, ttae_cache);
1666 aff_combination_expand (&off2, ttae_cache);
1667 aff_combination_scale (&off1, double_int_minus_one);
1668 aff_combination_add (&off2, &off1);
1670 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1671 return false;
1673 return true;
1676 /* Iterates over all locations of REF in LOOP and its subloops calling
1677 fn.operator() with the location as argument. When that operator
1678 returns true the iteration is stopped and true is returned.
1679 Otherwise false is returned. */
1681 template <typename FN>
1682 static bool
1683 for_all_locs_in_loop (struct loop *loop, mem_ref_p ref, FN fn)
1685 unsigned i;
1686 mem_ref_loc_p loc;
1687 struct loop *subloop;
1689 if (ref->accesses_in_loop.length () > (unsigned) loop->num)
1690 FOR_EACH_VEC_ELT (ref->accesses_in_loop[loop->num], i, loc)
1691 if (fn (loc))
1692 return true;
1694 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1695 if (for_all_locs_in_loop (subloop, ref, fn))
1696 return true;
1698 return false;
1701 /* Rewrites location LOC by TMP_VAR. */
1703 struct rewrite_mem_ref_loc
1705 rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
1706 bool operator () (mem_ref_loc_p loc);
1707 tree tmp_var;
1710 bool
1711 rewrite_mem_ref_loc::operator () (mem_ref_loc_p loc)
1713 *loc->ref = tmp_var;
1714 update_stmt (loc->stmt);
1715 return false;
1718 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1720 static void
1721 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1723 for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1726 /* Stores the first reference location in LOCP. */
1728 struct first_mem_ref_loc_1
1730 first_mem_ref_loc_1 (mem_ref_loc_p *locp_) : locp (locp_) {}
1731 bool operator () (mem_ref_loc_p loc);
1732 mem_ref_loc_p *locp;
1735 bool
1736 first_mem_ref_loc_1::operator () (mem_ref_loc_p loc)
1738 *locp = loc;
1739 return true;
1742 /* Returns the first reference location to REF in LOOP. */
1744 static mem_ref_loc_p
1745 first_mem_ref_loc (struct loop *loop, mem_ref_p ref)
1747 mem_ref_loc_p locp = NULL;
1748 for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
1749 return locp;
1752 struct prev_flag_edges {
1753 /* Edge to insert new flag comparison code. */
1754 edge append_cond_position;
1756 /* Edge for fall through from previous flag comparison. */
1757 edge last_cond_fallthru;
1760 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1761 MEM along edge EX.
1763 The store is only done if MEM has changed. We do this so no
1764 changes to MEM occur on code paths that did not originally store
1765 into it.
1767 The common case for execute_sm will transform:
1769 for (...) {
1770 if (foo)
1771 stuff;
1772 else
1773 MEM = TMP_VAR;
1776 into:
1778 lsm = MEM;
1779 for (...) {
1780 if (foo)
1781 stuff;
1782 else
1783 lsm = TMP_VAR;
1785 MEM = lsm;
1787 This function will generate:
1789 lsm = MEM;
1791 lsm_flag = false;
1793 for (...) {
1794 if (foo)
1795 stuff;
1796 else {
1797 lsm = TMP_VAR;
1798 lsm_flag = true;
1801 if (lsm_flag) <--
1802 MEM = lsm; <--
1805 static void
1806 execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag)
1808 basic_block new_bb, then_bb, old_dest;
1809 bool loop_has_only_one_exit;
1810 edge then_old_edge, orig_ex = ex;
1811 gimple_stmt_iterator gsi;
1812 gimple stmt;
1813 struct prev_flag_edges *prev_edges = (struct prev_flag_edges *) ex->aux;
1815 /* ?? Insert store after previous store if applicable. See note
1816 below. */
1817 if (prev_edges)
1818 ex = prev_edges->append_cond_position;
1820 loop_has_only_one_exit = single_pred_p (ex->dest);
1822 if (loop_has_only_one_exit)
1823 ex = split_block_after_labels (ex->dest);
1825 old_dest = ex->dest;
1826 new_bb = split_edge (ex);
1827 then_bb = create_empty_bb (new_bb);
1828 if (current_loops && new_bb->loop_father)
1829 add_bb_to_loop (then_bb, new_bb->loop_father);
1831 gsi = gsi_start_bb (new_bb);
1832 stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
1833 NULL_TREE, NULL_TREE);
1834 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1836 gsi = gsi_start_bb (then_bb);
1837 /* Insert actual store. */
1838 stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
1839 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1841 make_edge (new_bb, then_bb, EDGE_TRUE_VALUE);
1842 make_edge (new_bb, old_dest, EDGE_FALSE_VALUE);
1843 then_old_edge = make_edge (then_bb, old_dest, EDGE_FALLTHRU);
1845 set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
1847 if (prev_edges)
1849 basic_block prevbb = prev_edges->last_cond_fallthru->src;
1850 redirect_edge_succ (prev_edges->last_cond_fallthru, new_bb);
1851 set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
1852 set_immediate_dominator (CDI_DOMINATORS, old_dest,
1853 recompute_dominator (CDI_DOMINATORS, old_dest));
1856 /* ?? Because stores may alias, they must happen in the exact
1857 sequence they originally happened. Save the position right after
1858 the (_lsm) store we just created so we can continue appending after
1859 it and maintain the original order. */
1861 struct prev_flag_edges *p;
1863 if (orig_ex->aux)
1864 orig_ex->aux = NULL;
1865 alloc_aux_for_edge (orig_ex, sizeof (struct prev_flag_edges));
1866 p = (struct prev_flag_edges *) orig_ex->aux;
1867 p->append_cond_position = then_old_edge;
1868 p->last_cond_fallthru = find_edge (new_bb, old_dest);
1869 orig_ex->aux = (void *) p;
1872 if (!loop_has_only_one_exit)
1873 for (gsi = gsi_start_phis (old_dest); !gsi_end_p (gsi); gsi_next (&gsi))
1875 gimple phi = gsi_stmt (gsi);
1876 unsigned i;
1878 for (i = 0; i < gimple_phi_num_args (phi); i++)
1879 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
1881 tree arg = gimple_phi_arg_def (phi, i);
1882 add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
1883 update_stmt (phi);
1886 /* Remove the original fall through edge. This was the
1887 single_succ_edge (new_bb). */
1888 EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
1891 /* When REF is set on the location, set flag indicating the store. */
1893 struct sm_set_flag_if_changed
1895 sm_set_flag_if_changed (tree flag_) : flag (flag_) {}
1896 bool operator () (mem_ref_loc_p loc);
1897 tree flag;
1900 bool
1901 sm_set_flag_if_changed::operator () (mem_ref_loc_p loc)
1903 /* Only set the flag for writes. */
1904 if (is_gimple_assign (loc->stmt)
1905 && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
1907 gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
1908 gimple stmt = gimple_build_assign (flag, boolean_true_node);
1909 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1911 return false;
1914 /* Helper function for execute_sm. On every location where REF is
1915 set, set an appropriate flag indicating the store. */
1917 static tree
1918 execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref)
1920 tree flag;
1921 char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
1922 flag = create_tmp_reg (boolean_type_node, str);
1923 for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag));
1924 return flag;
1927 /* Executes store motion of memory reference REF from LOOP.
1928 Exits from the LOOP are stored in EXITS. The initialization of the
1929 temporary variable is put to the preheader of the loop, and assignments
1930 to the reference from the temporary variable are emitted to exits. */
1932 static void
1933 execute_sm (struct loop *loop, vec<edge> exits, mem_ref_p ref)
1935 tree tmp_var, store_flag;
1936 unsigned i;
1937 gimple load;
1938 struct fmt_data fmt_data;
1939 edge ex;
1940 struct lim_aux_data *lim_data;
1941 bool multi_threaded_model_p = false;
1942 gimple_stmt_iterator gsi;
1944 if (dump_file && (dump_flags & TDF_DETAILS))
1946 fprintf (dump_file, "Executing store motion of ");
1947 print_generic_expr (dump_file, ref->mem.ref, 0);
1948 fprintf (dump_file, " from loop %d\n", loop->num);
1951 tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
1952 get_lsm_tmp_name (ref->mem.ref, ~0));
1954 fmt_data.loop = loop;
1955 fmt_data.orig_loop = loop;
1956 for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
1958 if (bb_in_transaction (loop_preheader_edge (loop)->src)
1959 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES))
1960 multi_threaded_model_p = true;
1962 if (multi_threaded_model_p)
1963 store_flag = execute_sm_if_changed_flag_set (loop, ref);
1965 rewrite_mem_refs (loop, ref, tmp_var);
1967 /* Emit the load code on a random exit edge or into the latch if
1968 the loop does not exit, so that we are sure it will be processed
1969 by move_computations after all dependencies. */
1970 gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
1972 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
1973 load altogether, since the store is predicated by a flag. We
1974 could, do the load only if it was originally in the loop. */
1975 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
1976 lim_data = init_lim_data (load);
1977 lim_data->max_loop = loop;
1978 lim_data->tgt_loop = loop;
1979 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1981 if (multi_threaded_model_p)
1983 load = gimple_build_assign (store_flag, boolean_false_node);
1984 lim_data = init_lim_data (load);
1985 lim_data->max_loop = loop;
1986 lim_data->tgt_loop = loop;
1987 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1990 /* Sink the store to every exit from the loop. */
1991 FOR_EACH_VEC_ELT (exits, i, ex)
1992 if (!multi_threaded_model_p)
1994 gimple store;
1995 store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
1996 gsi_insert_on_edge (ex, store);
1998 else
1999 execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag);
2002 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2003 edges of the LOOP. */
2005 static void
2006 hoist_memory_references (struct loop *loop, bitmap mem_refs,
2007 vec<edge> exits)
2009 mem_ref_p ref;
2010 unsigned i;
2011 bitmap_iterator bi;
2013 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2015 ref = memory_accesses.refs_list[i];
2016 execute_sm (loop, exits, ref);
2020 struct ref_always_accessed
2022 ref_always_accessed (struct loop *loop_, tree base_, bool stored_p_)
2023 : loop (loop_), base (base_), stored_p (stored_p_) {}
2024 bool operator () (mem_ref_loc_p loc);
2025 struct loop *loop;
2026 tree base;
2027 bool stored_p;
2030 bool
2031 ref_always_accessed::operator () (mem_ref_loc_p loc)
2033 struct loop *must_exec;
2035 if (!get_lim_data (loc->stmt))
2036 return false;
2038 /* If we require an always executed store make sure the statement
2039 stores to the reference. */
2040 if (stored_p)
2042 tree lhs;
2043 if (!gimple_get_lhs (loc->stmt))
2044 return false;
2045 lhs = get_base_address (gimple_get_lhs (loc->stmt));
2046 if (!lhs)
2047 return false;
2048 if (INDIRECT_REF_P (lhs)
2049 || TREE_CODE (lhs) == MEM_REF)
2050 lhs = TREE_OPERAND (lhs, 0);
2051 if (lhs != base)
2052 return false;
2055 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2056 if (!must_exec)
2057 return false;
2059 if (must_exec == loop
2060 || flow_loop_nested_p (must_exec, loop))
2061 return true;
2063 return false;
2066 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2067 make sure REF is always stored to in LOOP. */
2069 static bool
2070 ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
2072 tree base = ao_ref_base (&ref->mem);
2073 if (TREE_CODE (base) == MEM_REF)
2074 base = TREE_OPERAND (base, 0);
2076 return for_all_locs_in_loop (loop, ref,
2077 ref_always_accessed (loop, base, stored_p));
2080 /* Returns true if REF1 and REF2 are independent. */
2082 static bool
2083 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
2085 if (ref1 == ref2)
2086 return true;
2088 if (dump_file && (dump_flags & TDF_DETAILS))
2089 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2090 ref1->id, ref2->id);
2092 if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
2094 if (dump_file && (dump_flags & TDF_DETAILS))
2095 fprintf (dump_file, "dependent.\n");
2096 return false;
2098 else
2100 if (dump_file && (dump_flags & TDF_DETAILS))
2101 fprintf (dump_file, "independent.\n");
2102 return true;
2106 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2107 and its super-loops. */
2109 static void
2110 record_dep_loop (struct loop *loop, mem_ref_p ref, bool stored_p)
2112 /* We can propagate dependent-in-loop bits up the loop
2113 hierarchy to all outer loops. */
2114 while (loop != current_loops->tree_root
2115 && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2116 loop = loop_outer (loop);
2119 /* Returns true if REF is independent on all other memory references in
2120 LOOP. */
2122 static bool
2123 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref, bool stored_p)
2125 bitmap refs_to_check;
2126 unsigned i;
2127 bitmap_iterator bi;
2128 mem_ref_p aref;
2130 if (stored_p)
2131 refs_to_check = &memory_accesses.refs_in_loop[loop->num];
2132 else
2133 refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
2135 if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
2136 return false;
2138 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2140 aref = memory_accesses.refs_list[i];
2141 if (!refs_independent_p (ref, aref))
2142 return false;
2145 return true;
2148 /* Returns true if REF is independent on all other memory references in
2149 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2151 static bool
2152 ref_indep_loop_p_2 (struct loop *loop, mem_ref_p ref, bool stored_p)
2154 stored_p |= bitmap_bit_p (&ref->stored, loop->num);
2156 if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2157 return true;
2158 if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2159 return false;
2161 struct loop *inner = loop->inner;
2162 while (inner)
2164 if (!ref_indep_loop_p_2 (inner, ref, stored_p))
2165 return false;
2166 inner = inner->next;
2169 bool indep_p = ref_indep_loop_p_1 (loop, ref, stored_p);
2171 if (dump_file && (dump_flags & TDF_DETAILS))
2172 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2173 ref->id, loop->num, indep_p ? "independent" : "dependent");
2175 /* Record the computed result in the cache. */
2176 if (indep_p)
2178 if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
2179 && stored_p)
2181 /* If it's independend against all refs then it's independent
2182 against stores, too. */
2183 bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
2186 else
2188 record_dep_loop (loop, ref, stored_p);
2189 if (!stored_p)
2191 /* If it's dependent against stores it's dependent against
2192 all refs, too. */
2193 record_dep_loop (loop, ref, true);
2197 return indep_p;
2200 /* Returns true if REF is independent on all other memory references in
2201 LOOP. */
2203 static bool
2204 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2206 gcc_checking_assert (MEM_ANALYZABLE (ref));
2208 return ref_indep_loop_p_2 (loop, ref, false);
2211 /* Returns true if we can perform store motion of REF from LOOP. */
2213 static bool
2214 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2216 tree base;
2218 /* Can't hoist unanalyzable refs. */
2219 if (!MEM_ANALYZABLE (ref))
2220 return false;
2222 /* It should be movable. */
2223 if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
2224 || TREE_THIS_VOLATILE (ref->mem.ref)
2225 || !for_each_index (&ref->mem.ref, may_move_till, loop))
2226 return false;
2228 /* If it can throw fail, we do not properly update EH info. */
2229 if (tree_could_throw_p (ref->mem.ref))
2230 return false;
2232 /* If it can trap, it must be always executed in LOOP.
2233 Readonly memory locations may trap when storing to them, but
2234 tree_could_trap_p is a predicate for rvalues, so check that
2235 explicitly. */
2236 base = get_base_address (ref->mem.ref);
2237 if ((tree_could_trap_p (ref->mem.ref)
2238 || (DECL_P (base) && TREE_READONLY (base)))
2239 && !ref_always_accessed_p (loop, ref, true))
2240 return false;
2242 /* And it must be independent on all other memory references
2243 in LOOP. */
2244 if (!ref_indep_loop_p (loop, ref))
2245 return false;
2247 return true;
2250 /* Marks the references in LOOP for that store motion should be performed
2251 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2252 motion was performed in one of the outer loops. */
2254 static void
2255 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2257 bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
2258 unsigned i;
2259 bitmap_iterator bi;
2260 mem_ref_p ref;
2262 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2264 ref = memory_accesses.refs_list[i];
2265 if (can_sm_ref_p (loop, ref))
2266 bitmap_set_bit (refs_to_sm, i);
2270 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2271 for a store motion optimization (i.e. whether we can insert statement
2272 on its exits). */
2274 static bool
2275 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2276 vec<edge> exits)
2278 unsigned i;
2279 edge ex;
2281 FOR_EACH_VEC_ELT (exits, i, ex)
2282 if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
2283 return false;
2285 return true;
2288 /* Try to perform store motion for all memory references modified inside
2289 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2290 store motion was executed in one of the outer loops. */
2292 static void
2293 store_motion_loop (struct loop *loop, bitmap sm_executed)
2295 vec<edge> exits = get_loop_exit_edges (loop);
2296 struct loop *subloop;
2297 bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
2299 if (loop_suitable_for_sm (loop, exits))
2301 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2302 hoist_memory_references (loop, sm_in_loop, exits);
2304 exits.release ();
2306 bitmap_ior_into (sm_executed, sm_in_loop);
2307 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2308 store_motion_loop (subloop, sm_executed);
2309 bitmap_and_compl_into (sm_executed, sm_in_loop);
2310 BITMAP_FREE (sm_in_loop);
2313 /* Try to perform store motion for all memory references modified inside
2314 loops. */
2316 static void
2317 store_motion (void)
2319 struct loop *loop;
2320 bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
2322 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2323 store_motion_loop (loop, sm_executed);
2325 BITMAP_FREE (sm_executed);
2326 gsi_commit_edge_inserts ();
2329 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2330 for each such basic block bb records the outermost loop for that execution
2331 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2332 blocks that contain a nonpure call. */
2334 static void
2335 fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
2337 basic_block bb = NULL, *bbs, last = NULL;
2338 unsigned i;
2339 edge e;
2340 struct loop *inn_loop = loop;
2342 if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
2344 bbs = get_loop_body_in_dom_order (loop);
2346 for (i = 0; i < loop->num_nodes; i++)
2348 edge_iterator ei;
2349 bb = bbs[i];
2351 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2352 last = bb;
2354 if (bitmap_bit_p (contains_call, bb->index))
2355 break;
2357 FOR_EACH_EDGE (e, ei, bb->succs)
2358 if (!flow_bb_inside_loop_p (loop, e->dest))
2359 break;
2360 if (e)
2361 break;
2363 /* A loop might be infinite (TODO use simple loop analysis
2364 to disprove this if possible). */
2365 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2366 break;
2368 if (!flow_bb_inside_loop_p (inn_loop, bb))
2369 break;
2371 if (bb->loop_father->header == bb)
2373 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2374 break;
2376 /* In a loop that is always entered we may proceed anyway.
2377 But record that we entered it and stop once we leave it. */
2378 inn_loop = bb->loop_father;
2382 while (1)
2384 SET_ALWAYS_EXECUTED_IN (last, loop);
2385 if (last == loop->header)
2386 break;
2387 last = get_immediate_dominator (CDI_DOMINATORS, last);
2390 free (bbs);
2393 for (loop = loop->inner; loop; loop = loop->next)
2394 fill_always_executed_in_1 (loop, contains_call);
2397 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2398 for each such basic block bb records the outermost loop for that execution
2399 of its header implies execution of bb. */
2401 static void
2402 fill_always_executed_in (void)
2404 sbitmap contains_call = sbitmap_alloc (last_basic_block_for_fn (cfun));
2405 basic_block bb;
2406 struct loop *loop;
2408 bitmap_clear (contains_call);
2409 FOR_EACH_BB_FN (bb, cfun)
2411 gimple_stmt_iterator gsi;
2412 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2414 if (nonpure_call_p (gsi_stmt (gsi)))
2415 break;
2418 if (!gsi_end_p (gsi))
2419 bitmap_set_bit (contains_call, bb->index);
2422 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2423 fill_always_executed_in_1 (loop, contains_call);
2425 sbitmap_free (contains_call);
2429 /* Compute the global information needed by the loop invariant motion pass. */
2431 static void
2432 tree_ssa_lim_initialize (void)
2434 unsigned i;
2436 bitmap_obstack_initialize (&lim_bitmap_obstack);
2437 lim_aux_data_map = pointer_map_create ();
2439 if (flag_tm)
2440 compute_transaction_bits ();
2442 alloc_aux_for_edges (0);
2444 memory_accesses.refs.create (100);
2445 memory_accesses.refs_list.create (100);
2446 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2447 memory_accesses.refs_list.quick_push
2448 (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
2450 memory_accesses.refs_in_loop.create (number_of_loops (cfun));
2451 memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
2452 memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
2453 memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2454 memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
2455 memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2457 for (i = 0; i < number_of_loops (cfun); i++)
2459 bitmap_initialize (&memory_accesses.refs_in_loop[i],
2460 &lim_bitmap_obstack);
2461 bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
2462 &lim_bitmap_obstack);
2463 bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
2464 &lim_bitmap_obstack);
2467 memory_accesses.ttae_cache = NULL;
2470 /* Cleans up after the invariant motion pass. */
2472 static void
2473 tree_ssa_lim_finalize (void)
2475 basic_block bb;
2476 unsigned i;
2477 mem_ref_p ref;
2479 free_aux_for_edges ();
2481 FOR_EACH_BB_FN (bb, cfun)
2482 SET_ALWAYS_EXECUTED_IN (bb, NULL);
2484 bitmap_obstack_release (&lim_bitmap_obstack);
2485 pointer_map_destroy (lim_aux_data_map);
2487 memory_accesses.refs.dispose ();
2489 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
2490 memref_free (ref);
2491 memory_accesses.refs_list.release ();
2493 memory_accesses.refs_in_loop.release ();
2494 memory_accesses.refs_stored_in_loop.release ();
2495 memory_accesses.all_refs_stored_in_loop.release ();
2497 if (memory_accesses.ttae_cache)
2498 free_affine_expand_cache (&memory_accesses.ttae_cache);
2501 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2502 i.e. those that are likely to be win regardless of the register pressure. */
2504 unsigned int
2505 tree_ssa_lim (void)
2507 unsigned int todo;
2509 tree_ssa_lim_initialize ();
2511 /* Gathers information about memory accesses in the loops. */
2512 analyze_memory_references ();
2514 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2515 fill_always_executed_in ();
2517 /* For each statement determine the outermost loop in that it is
2518 invariant and cost for computing the invariant. */
2519 invariantness_dom_walker (CDI_DOMINATORS)
2520 .walk (cfun->cfg->x_entry_block_ptr);
2522 /* Execute store motion. Force the necessary invariants to be moved
2523 out of the loops as well. */
2524 store_motion ();
2526 /* Move the expressions that are expensive enough. */
2527 todo = move_computations ();
2529 tree_ssa_lim_finalize ();
2531 return todo;
2534 /* Loop invariant motion pass. */
2536 static unsigned int
2537 tree_ssa_loop_im (void)
2539 if (number_of_loops (cfun) <= 1)
2540 return 0;
2542 return tree_ssa_lim ();
2545 static bool
2546 gate_tree_ssa_loop_im (void)
2548 return flag_tree_loop_im != 0;
2551 namespace {
2553 const pass_data pass_data_lim =
2555 GIMPLE_PASS, /* type */
2556 "lim", /* name */
2557 OPTGROUP_LOOP, /* optinfo_flags */
2558 true, /* has_gate */
2559 true, /* has_execute */
2560 TV_LIM, /* tv_id */
2561 PROP_cfg, /* properties_required */
2562 0, /* properties_provided */
2563 0, /* properties_destroyed */
2564 0, /* todo_flags_start */
2565 0, /* todo_flags_finish */
2568 class pass_lim : public gimple_opt_pass
2570 public:
2571 pass_lim (gcc::context *ctxt)
2572 : gimple_opt_pass (pass_data_lim, ctxt)
2575 /* opt_pass methods: */
2576 opt_pass * clone () { return new pass_lim (m_ctxt); }
2577 bool gate () { return gate_tree_ssa_loop_im (); }
2578 unsigned int execute () { return tree_ssa_loop_im (); }
2580 }; // class pass_lim
2582 } // anon namespace
2584 gimple_opt_pass *
2585 make_pass_lim (gcc::context *ctxt)
2587 return new pass_lim (ctxt);