* c-c++-common/ubsan/float-cast-overflow-6.c: Add i?86-*-* target.
[official-gcc.git] / gcc / tree-ssa-loop-im.c
blob85d811868b758480eb75908a2d9fd6ae0735ec93
1 /* Loop invariant motion.
2 Copyright (C) 2003-2014 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 "predict.h"
27 #include "vec.h"
28 #include "hashtab.h"
29 #include "hash-set.h"
30 #include "machmode.h"
31 #include "hard-reg-set.h"
32 #include "input.h"
33 #include "function.h"
34 #include "dominance.h"
35 #include "cfg.h"
36 #include "cfganal.h"
37 #include "basic-block.h"
38 #include "gimple-pretty-print.h"
39 #include "hash-map.h"
40 #include "hash-table.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "tree-eh.h"
44 #include "gimple-expr.h"
45 #include "is-a.h"
46 #include "gimple.h"
47 #include "gimplify.h"
48 #include "gimple-iterator.h"
49 #include "gimple-ssa.h"
50 #include "tree-cfg.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-into-ssa.h"
58 #include "cfgloop.h"
59 #include "domwalk.h"
60 #include "params.h"
61 #include "tree-pass.h"
62 #include "flags.h"
63 #include "tree-affine.h"
64 #include "tree-ssa-propagate.h"
65 #include "trans-mem.h"
66 #include "gimple-fold.h"
68 /* TODO: Support for predicated code motion. I.e.
70 while (1)
72 if (cond)
74 a = inv;
75 something;
79 Where COND and INV are invariants, but evaluating INV may trap or be
80 invalid from some other reason if !COND. This may be transformed to
82 if (cond)
83 a = inv;
84 while (1)
86 if (cond)
87 something;
88 } */
90 /* The auxiliary data kept for each statement. */
92 struct lim_aux_data
94 struct loop *max_loop; /* The outermost loop in that the statement
95 is invariant. */
97 struct loop *tgt_loop; /* The loop out of that we want to move the
98 invariant. */
100 struct loop *always_executed_in;
101 /* The outermost loop for that we are sure
102 the statement is executed if the loop
103 is entered. */
105 unsigned cost; /* Cost of the computation performed by the
106 statement. */
108 vec<gimple> depends; /* Vector of statements that must be also
109 hoisted out of the loop when this statement
110 is hoisted; i.e. those that define the
111 operands of the statement and are inside of
112 the MAX_LOOP loop. */
115 /* Maps statements to their lim_aux_data. */
117 static hash_map<gimple, lim_aux_data *> *lim_aux_data_map;
119 /* Description of a memory reference location. */
121 typedef struct mem_ref_loc
123 tree *ref; /* The reference itself. */
124 gimple stmt; /* The statement in that it occurs. */
125 } *mem_ref_loc_p;
128 /* Description of a memory reference. */
130 typedef struct im_mem_ref
132 unsigned id; /* ID assigned to the memory reference
133 (its index in memory_accesses.refs_list) */
134 hashval_t hash; /* Its hash value. */
136 /* The memory access itself and associated caching of alias-oracle
137 query meta-data. */
138 ao_ref mem;
140 bitmap stored; /* The set of loops in that this memory location
141 is stored to. */
142 vec<mem_ref_loc> accesses_in_loop;
143 /* The locations of the accesses. Vector
144 indexed by the loop number. */
146 /* The following sets are computed on demand. We keep both set and
147 its complement, so that we know whether the information was
148 already computed or not. */
149 bitmap_head indep_loop; /* The set of loops in that the memory
150 reference is independent, meaning:
151 If it is stored in the loop, this store
152 is independent on all other loads and
153 stores.
154 If it is only loaded, then it is independent
155 on all stores in the loop. */
156 bitmap_head dep_loop; /* The complement of INDEP_LOOP. */
157 } *mem_ref_p;
159 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
160 to record (in)dependence against stores in the loop and its subloops, the
161 second to record (in)dependence against all references in the loop
162 and its subloops. */
163 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
165 /* Mem_ref hashtable helpers. */
167 struct mem_ref_hasher : typed_noop_remove <im_mem_ref>
169 typedef im_mem_ref value_type;
170 typedef tree_node compare_type;
171 static inline hashval_t hash (const value_type *);
172 static inline bool equal (const value_type *, const compare_type *);
175 /* A hash function for struct im_mem_ref object OBJ. */
177 inline hashval_t
178 mem_ref_hasher::hash (const value_type *mem)
180 return mem->hash;
183 /* An equality function for struct im_mem_ref object MEM1 with
184 memory reference OBJ2. */
186 inline bool
187 mem_ref_hasher::equal (const value_type *mem1, const compare_type *obj2)
189 return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
193 /* Description of memory accesses in loops. */
195 static struct
197 /* The hash table of memory references accessed in loops. */
198 hash_table<mem_ref_hasher> *refs;
200 /* The list of memory references. */
201 vec<mem_ref_p> refs_list;
203 /* The set of memory references accessed in each loop. */
204 vec<bitmap_head> refs_in_loop;
206 /* The set of memory references stored in each loop. */
207 vec<bitmap_head> refs_stored_in_loop;
209 /* The set of memory references stored in each loop, including subloops . */
210 vec<bitmap_head> all_refs_stored_in_loop;
212 /* Cache for expanding memory addresses. */
213 hash_map<tree, name_expansion *> *ttae_cache;
214 } memory_accesses;
216 /* Obstack for the bitmaps in the above data structures. */
217 static bitmap_obstack lim_bitmap_obstack;
218 static obstack mem_ref_obstack;
220 static bool ref_indep_loop_p (struct loop *, mem_ref_p);
222 /* Minimum cost of an expensive expression. */
223 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
225 /* The outermost loop for which execution of the header guarantees that the
226 block will be executed. */
227 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
228 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
230 /* ID of the shared unanalyzable mem. */
231 #define UNANALYZABLE_MEM_ID 0
233 /* Whether the reference was analyzable. */
234 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
236 static struct lim_aux_data *
237 init_lim_data (gimple stmt)
239 lim_aux_data *p = XCNEW (struct lim_aux_data);
240 lim_aux_data_map->put (stmt, p);
242 return p;
245 static struct lim_aux_data *
246 get_lim_data (gimple stmt)
248 lim_aux_data **p = lim_aux_data_map->get (stmt);
249 if (!p)
250 return NULL;
252 return *p;
255 /* Releases the memory occupied by DATA. */
257 static void
258 free_lim_aux_data (struct lim_aux_data *data)
260 data->depends.release ();
261 free (data);
264 static void
265 clear_lim_data (gimple stmt)
267 lim_aux_data **p = lim_aux_data_map->get (stmt);
268 if (!p)
269 return;
271 free_lim_aux_data (*p);
272 *p = NULL;
276 /* The possibilities of statement movement. */
277 enum move_pos
279 MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
280 MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
281 become executed -- memory accesses, ... */
282 MOVE_POSSIBLE /* Unlimited movement. */
286 /* If it is possible to hoist the statement STMT unconditionally,
287 returns MOVE_POSSIBLE.
288 If it is possible to hoist the statement STMT, but we must avoid making
289 it executed if it would not be executed in the original program (e.g.
290 because it may trap), return MOVE_PRESERVE_EXECUTION.
291 Otherwise return MOVE_IMPOSSIBLE. */
293 enum move_pos
294 movement_possibility (gimple stmt)
296 tree lhs;
297 enum move_pos ret = MOVE_POSSIBLE;
299 if (flag_unswitch_loops
300 && gimple_code (stmt) == GIMPLE_COND)
302 /* If we perform unswitching, force the operands of the invariant
303 condition to be moved out of the loop. */
304 return MOVE_POSSIBLE;
307 if (gimple_code (stmt) == GIMPLE_PHI
308 && gimple_phi_num_args (stmt) <= 2
309 && !virtual_operand_p (gimple_phi_result (stmt))
310 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
311 return MOVE_POSSIBLE;
313 if (gimple_get_lhs (stmt) == NULL_TREE)
314 return MOVE_IMPOSSIBLE;
316 if (gimple_vdef (stmt))
317 return MOVE_IMPOSSIBLE;
319 if (stmt_ends_bb_p (stmt)
320 || gimple_has_volatile_ops (stmt)
321 || gimple_has_side_effects (stmt)
322 || stmt_could_throw_p (stmt))
323 return MOVE_IMPOSSIBLE;
325 if (is_gimple_call (stmt))
327 /* While pure or const call is guaranteed to have no side effects, we
328 cannot move it arbitrarily. Consider code like
330 char *s = something ();
332 while (1)
334 if (s)
335 t = strlen (s);
336 else
337 t = 0;
340 Here the strlen call cannot be moved out of the loop, even though
341 s is invariant. In addition to possibly creating a call with
342 invalid arguments, moving out a function call that is not executed
343 may cause performance regressions in case the call is costly and
344 not executed at all. */
345 ret = MOVE_PRESERVE_EXECUTION;
346 lhs = gimple_call_lhs (stmt);
348 else if (is_gimple_assign (stmt))
349 lhs = gimple_assign_lhs (stmt);
350 else
351 return MOVE_IMPOSSIBLE;
353 if (TREE_CODE (lhs) == SSA_NAME
354 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
355 return MOVE_IMPOSSIBLE;
357 if (TREE_CODE (lhs) != SSA_NAME
358 || gimple_could_trap_p (stmt))
359 return MOVE_PRESERVE_EXECUTION;
361 /* Non local loads in a transaction cannot be hoisted out. Well,
362 unless the load happens on every path out of the loop, but we
363 don't take this into account yet. */
364 if (flag_tm
365 && gimple_in_transaction (stmt)
366 && gimple_assign_single_p (stmt))
368 tree rhs = gimple_assign_rhs1 (stmt);
369 if (DECL_P (rhs) && is_global_var (rhs))
371 if (dump_file)
373 fprintf (dump_file, "Cannot hoist conditional load of ");
374 print_generic_expr (dump_file, rhs, TDF_SLIM);
375 fprintf (dump_file, " because it is in a transaction.\n");
377 return MOVE_IMPOSSIBLE;
381 return ret;
384 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
385 loop to that we could move the expression using DEF if it did not have
386 other operands, i.e. the outermost loop enclosing LOOP in that the value
387 of DEF is invariant. */
389 static struct loop *
390 outermost_invariant_loop (tree def, struct loop *loop)
392 gimple def_stmt;
393 basic_block def_bb;
394 struct loop *max_loop;
395 struct lim_aux_data *lim_data;
397 if (!def)
398 return superloop_at_depth (loop, 1);
400 if (TREE_CODE (def) != SSA_NAME)
402 gcc_assert (is_gimple_min_invariant (def));
403 return superloop_at_depth (loop, 1);
406 def_stmt = SSA_NAME_DEF_STMT (def);
407 def_bb = gimple_bb (def_stmt);
408 if (!def_bb)
409 return superloop_at_depth (loop, 1);
411 max_loop = find_common_loop (loop, def_bb->loop_father);
413 lim_data = get_lim_data (def_stmt);
414 if (lim_data != NULL && lim_data->max_loop != NULL)
415 max_loop = find_common_loop (max_loop,
416 loop_outer (lim_data->max_loop));
417 if (max_loop == loop)
418 return NULL;
419 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
421 return max_loop;
424 /* DATA is a structure containing information associated with a statement
425 inside LOOP. DEF is one of the operands of this statement.
427 Find the outermost loop enclosing LOOP in that value of DEF is invariant
428 and record this in DATA->max_loop field. If DEF itself is defined inside
429 this loop as well (i.e. we need to hoist it out of the loop if we want
430 to hoist the statement represented by DATA), record the statement in that
431 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
432 add the cost of the computation of DEF to the DATA->cost.
434 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
436 static bool
437 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
438 bool add_cost)
440 gimple def_stmt = SSA_NAME_DEF_STMT (def);
441 basic_block def_bb = gimple_bb (def_stmt);
442 struct loop *max_loop;
443 struct lim_aux_data *def_data;
445 if (!def_bb)
446 return true;
448 max_loop = outermost_invariant_loop (def, loop);
449 if (!max_loop)
450 return false;
452 if (flow_loop_nested_p (data->max_loop, max_loop))
453 data->max_loop = max_loop;
455 def_data = get_lim_data (def_stmt);
456 if (!def_data)
457 return true;
459 if (add_cost
460 /* Only add the cost if the statement defining DEF is inside LOOP,
461 i.e. if it is likely that by moving the invariants dependent
462 on it, we will be able to avoid creating a new register for
463 it (since it will be only used in these dependent invariants). */
464 && def_bb->loop_father == loop)
465 data->cost += def_data->cost;
467 data->depends.safe_push (def_stmt);
469 return true;
472 /* Returns an estimate for a cost of statement STMT. The values here
473 are just ad-hoc constants, similar to costs for inlining. */
475 static unsigned
476 stmt_cost (gimple stmt)
478 /* Always try to create possibilities for unswitching. */
479 if (gimple_code (stmt) == GIMPLE_COND
480 || gimple_code (stmt) == GIMPLE_PHI)
481 return LIM_EXPENSIVE;
483 /* We should be hoisting calls if possible. */
484 if (is_gimple_call (stmt))
486 tree fndecl;
488 /* Unless the call is a builtin_constant_p; this always folds to a
489 constant, so moving it is useless. */
490 fndecl = gimple_call_fndecl (stmt);
491 if (fndecl
492 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
493 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
494 return 0;
496 return LIM_EXPENSIVE;
499 /* Hoisting memory references out should almost surely be a win. */
500 if (gimple_references_memory_p (stmt))
501 return LIM_EXPENSIVE;
503 if (gimple_code (stmt) != GIMPLE_ASSIGN)
504 return 1;
506 switch (gimple_assign_rhs_code (stmt))
508 case MULT_EXPR:
509 case WIDEN_MULT_EXPR:
510 case WIDEN_MULT_PLUS_EXPR:
511 case WIDEN_MULT_MINUS_EXPR:
512 case DOT_PROD_EXPR:
513 case FMA_EXPR:
514 case TRUNC_DIV_EXPR:
515 case CEIL_DIV_EXPR:
516 case FLOOR_DIV_EXPR:
517 case ROUND_DIV_EXPR:
518 case EXACT_DIV_EXPR:
519 case CEIL_MOD_EXPR:
520 case FLOOR_MOD_EXPR:
521 case ROUND_MOD_EXPR:
522 case TRUNC_MOD_EXPR:
523 case RDIV_EXPR:
524 /* Division and multiplication are usually expensive. */
525 return LIM_EXPENSIVE;
527 case LSHIFT_EXPR:
528 case RSHIFT_EXPR:
529 case WIDEN_LSHIFT_EXPR:
530 case LROTATE_EXPR:
531 case RROTATE_EXPR:
532 /* Shifts and rotates are usually expensive. */
533 return LIM_EXPENSIVE;
535 case CONSTRUCTOR:
536 /* Make vector construction cost proportional to the number
537 of elements. */
538 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
540 case SSA_NAME:
541 case PAREN_EXPR:
542 /* Whether or not something is wrapped inside a PAREN_EXPR
543 should not change move cost. Nor should an intermediate
544 unpropagated SSA name copy. */
545 return 0;
547 default:
548 return 1;
552 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
553 REF is independent. If REF is not independent in LOOP, NULL is returned
554 instead. */
556 static struct loop *
557 outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
559 struct loop *aloop;
561 if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
562 return NULL;
564 for (aloop = outer;
565 aloop != loop;
566 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
567 if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
568 && ref_indep_loop_p (aloop, ref))
569 return aloop;
571 if (ref_indep_loop_p (loop, ref))
572 return loop;
573 else
574 return NULL;
577 /* If there is a simple load or store to a memory reference in STMT, returns
578 the location of the memory reference, and sets IS_STORE according to whether
579 it is a store or load. Otherwise, returns NULL. */
581 static tree *
582 simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
584 tree *lhs, *rhs;
586 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
587 if (!gimple_assign_single_p (stmt))
588 return NULL;
590 lhs = gimple_assign_lhs_ptr (stmt);
591 rhs = gimple_assign_rhs1_ptr (stmt);
593 if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
595 *is_store = false;
596 return rhs;
598 else if (gimple_vdef (stmt)
599 && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
601 *is_store = true;
602 return lhs;
604 else
605 return NULL;
608 /* Returns the memory reference contained in STMT. */
610 static mem_ref_p
611 mem_ref_in_stmt (gimple stmt)
613 bool store;
614 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
615 hashval_t hash;
616 mem_ref_p ref;
618 if (!mem)
619 return NULL;
620 gcc_assert (!store);
622 hash = iterative_hash_expr (*mem, 0);
623 ref = memory_accesses.refs->find_with_hash (*mem, hash);
625 gcc_assert (ref != NULL);
626 return ref;
629 /* From a controlling predicate in DOM determine the arguments from
630 the PHI node PHI that are chosen if the predicate evaluates to
631 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
632 they are non-NULL. Returns true if the arguments can be determined,
633 else return false. */
635 static bool
636 extract_true_false_args_from_phi (basic_block dom, gimple phi,
637 tree *true_arg_p, tree *false_arg_p)
639 basic_block bb = gimple_bb (phi);
640 edge true_edge, false_edge, tem;
641 tree arg0 = NULL_TREE, arg1 = NULL_TREE;
643 /* We have to verify that one edge into the PHI node is dominated
644 by the true edge of the predicate block and the other edge
645 dominated by the false edge. This ensures that the PHI argument
646 we are going to take is completely determined by the path we
647 take from the predicate block.
648 We can only use BB dominance checks below if the destination of
649 the true/false edges are dominated by their edge, thus only
650 have a single predecessor. */
651 extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
652 tem = EDGE_PRED (bb, 0);
653 if (tem == true_edge
654 || (single_pred_p (true_edge->dest)
655 && (tem->src == true_edge->dest
656 || dominated_by_p (CDI_DOMINATORS,
657 tem->src, true_edge->dest))))
658 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
659 else if (tem == false_edge
660 || (single_pred_p (false_edge->dest)
661 && (tem->src == false_edge->dest
662 || dominated_by_p (CDI_DOMINATORS,
663 tem->src, false_edge->dest))))
664 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
665 else
666 return false;
667 tem = EDGE_PRED (bb, 1);
668 if (tem == true_edge
669 || (single_pred_p (true_edge->dest)
670 && (tem->src == true_edge->dest
671 || dominated_by_p (CDI_DOMINATORS,
672 tem->src, true_edge->dest))))
673 arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
674 else if (tem == false_edge
675 || (single_pred_p (false_edge->dest)
676 && (tem->src == false_edge->dest
677 || dominated_by_p (CDI_DOMINATORS,
678 tem->src, false_edge->dest))))
679 arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
680 else
681 return false;
682 if (!arg0 || !arg1)
683 return false;
685 if (true_arg_p)
686 *true_arg_p = arg0;
687 if (false_arg_p)
688 *false_arg_p = arg1;
690 return true;
693 /* Determine the outermost loop to that it is possible to hoist a statement
694 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
695 the outermost loop in that the value computed by STMT is invariant.
696 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
697 we preserve the fact whether STMT is executed. It also fills other related
698 information to LIM_DATA (STMT).
700 The function returns false if STMT cannot be hoisted outside of the loop it
701 is defined in, and true otherwise. */
703 static bool
704 determine_max_movement (gimple stmt, bool must_preserve_exec)
706 basic_block bb = gimple_bb (stmt);
707 struct loop *loop = bb->loop_father;
708 struct loop *level;
709 struct lim_aux_data *lim_data = get_lim_data (stmt);
710 tree val;
711 ssa_op_iter iter;
713 if (must_preserve_exec)
714 level = ALWAYS_EXECUTED_IN (bb);
715 else
716 level = superloop_at_depth (loop, 1);
717 lim_data->max_loop = level;
719 if (gimple_code (stmt) == GIMPLE_PHI)
721 use_operand_p use_p;
722 unsigned min_cost = UINT_MAX;
723 unsigned total_cost = 0;
724 struct lim_aux_data *def_data;
726 /* We will end up promoting dependencies to be unconditionally
727 evaluated. For this reason the PHI cost (and thus the
728 cost we remove from the loop by doing the invariant motion)
729 is that of the cheapest PHI argument dependency chain. */
730 FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
732 val = USE_FROM_PTR (use_p);
734 if (TREE_CODE (val) != SSA_NAME)
736 /* Assign const 1 to constants. */
737 min_cost = MIN (min_cost, 1);
738 total_cost += 1;
739 continue;
741 if (!add_dependency (val, lim_data, loop, false))
742 return false;
744 gimple def_stmt = SSA_NAME_DEF_STMT (val);
745 if (gimple_bb (def_stmt)
746 && gimple_bb (def_stmt)->loop_father == loop)
748 def_data = get_lim_data (def_stmt);
749 if (def_data)
751 min_cost = MIN (min_cost, def_data->cost);
752 total_cost += def_data->cost;
757 min_cost = MIN (min_cost, total_cost);
758 lim_data->cost += min_cost;
760 if (gimple_phi_num_args (stmt) > 1)
762 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
763 gimple cond;
764 if (gsi_end_p (gsi_last_bb (dom)))
765 return false;
766 cond = gsi_stmt (gsi_last_bb (dom));
767 if (gimple_code (cond) != GIMPLE_COND)
768 return false;
769 /* Verify that this is an extended form of a diamond and
770 the PHI arguments are completely controlled by the
771 predicate in DOM. */
772 if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL))
773 return false;
775 /* Fold in dependencies and cost of the condition. */
776 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
778 if (!add_dependency (val, lim_data, loop, false))
779 return false;
780 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
781 if (def_data)
782 total_cost += def_data->cost;
785 /* We want to avoid unconditionally executing very expensive
786 operations. As costs for our dependencies cannot be
787 negative just claim we are not invariand for this case.
788 We also are not sure whether the control-flow inside the
789 loop will vanish. */
790 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
791 && !(min_cost != 0
792 && total_cost / min_cost <= 2))
793 return false;
795 /* Assume that the control-flow in the loop will vanish.
796 ??? We should verify this and not artificially increase
797 the cost if that is not the case. */
798 lim_data->cost += stmt_cost (stmt);
801 return true;
803 else
804 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
805 if (!add_dependency (val, lim_data, loop, true))
806 return false;
808 if (gimple_vuse (stmt))
810 mem_ref_p ref = mem_ref_in_stmt (stmt);
812 if (ref)
814 lim_data->max_loop
815 = outermost_indep_loop (lim_data->max_loop, loop, ref);
816 if (!lim_data->max_loop)
817 return false;
819 else
821 if ((val = gimple_vuse (stmt)) != NULL_TREE)
823 if (!add_dependency (val, lim_data, loop, false))
824 return false;
829 lim_data->cost += stmt_cost (stmt);
831 return true;
834 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
835 and that one of the operands of this statement is computed by STMT.
836 Ensure that STMT (together with all the statements that define its
837 operands) is hoisted at least out of the loop LEVEL. */
839 static void
840 set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
842 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
843 struct lim_aux_data *lim_data;
844 gimple dep_stmt;
845 unsigned i;
847 stmt_loop = find_common_loop (orig_loop, stmt_loop);
848 lim_data = get_lim_data (stmt);
849 if (lim_data != NULL && lim_data->tgt_loop != NULL)
850 stmt_loop = find_common_loop (stmt_loop,
851 loop_outer (lim_data->tgt_loop));
852 if (flow_loop_nested_p (stmt_loop, level))
853 return;
855 gcc_assert (level == lim_data->max_loop
856 || flow_loop_nested_p (lim_data->max_loop, level));
858 lim_data->tgt_loop = level;
859 FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
860 set_level (dep_stmt, orig_loop, level);
863 /* Determines an outermost loop from that we want to hoist the statement STMT.
864 For now we chose the outermost possible loop. TODO -- use profiling
865 information to set it more sanely. */
867 static void
868 set_profitable_level (gimple stmt)
870 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
873 /* Returns true if STMT is a call that has side effects. */
875 static bool
876 nonpure_call_p (gimple stmt)
878 if (gimple_code (stmt) != GIMPLE_CALL)
879 return false;
881 return gimple_has_side_effects (stmt);
884 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
886 static gimple
887 rewrite_reciprocal (gimple_stmt_iterator *bsi)
889 gimple stmt, stmt1, stmt2;
890 tree name, lhs, type;
891 tree real_one;
892 gimple_stmt_iterator gsi;
894 stmt = gsi_stmt (*bsi);
895 lhs = gimple_assign_lhs (stmt);
896 type = TREE_TYPE (lhs);
898 real_one = build_one_cst (type);
900 name = make_temp_ssa_name (type, NULL, "reciptmp");
901 stmt1 = gimple_build_assign_with_ops (RDIV_EXPR, name, real_one,
902 gimple_assign_rhs2 (stmt));
904 stmt2 = gimple_build_assign_with_ops (MULT_EXPR, lhs, name,
905 gimple_assign_rhs1 (stmt));
907 /* Replace division stmt with reciprocal and multiply stmts.
908 The multiply stmt is not invariant, so update iterator
909 and avoid rescanning. */
910 gsi = *bsi;
911 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
912 gsi_replace (&gsi, stmt2, true);
914 /* Continue processing with invariant reciprocal statement. */
915 return stmt1;
918 /* Check if the pattern at *BSI is a bittest of the form
919 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
921 static gimple
922 rewrite_bittest (gimple_stmt_iterator *bsi)
924 gimple stmt, use_stmt, stmt1, stmt2;
925 tree lhs, name, t, a, b;
926 use_operand_p use;
928 stmt = gsi_stmt (*bsi);
929 lhs = gimple_assign_lhs (stmt);
931 /* Verify that the single use of lhs is a comparison against zero. */
932 if (TREE_CODE (lhs) != SSA_NAME
933 || !single_imm_use (lhs, &use, &use_stmt)
934 || gimple_code (use_stmt) != GIMPLE_COND)
935 return stmt;
936 if (gimple_cond_lhs (use_stmt) != lhs
937 || (gimple_cond_code (use_stmt) != NE_EXPR
938 && gimple_cond_code (use_stmt) != EQ_EXPR)
939 || !integer_zerop (gimple_cond_rhs (use_stmt)))
940 return stmt;
942 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
943 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
944 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
945 return stmt;
947 /* There is a conversion in between possibly inserted by fold. */
948 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
950 t = gimple_assign_rhs1 (stmt1);
951 if (TREE_CODE (t) != SSA_NAME
952 || !has_single_use (t))
953 return stmt;
954 stmt1 = SSA_NAME_DEF_STMT (t);
955 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
956 return stmt;
959 /* Verify that B is loop invariant but A is not. Verify that with
960 all the stmt walking we are still in the same loop. */
961 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
962 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
963 return stmt;
965 a = gimple_assign_rhs1 (stmt1);
966 b = gimple_assign_rhs2 (stmt1);
968 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
969 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
971 gimple_stmt_iterator rsi;
973 /* 1 << B */
974 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
975 build_int_cst (TREE_TYPE (a), 1), b);
976 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
977 stmt1 = gimple_build_assign (name, t);
979 /* A & (1 << B) */
980 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
981 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
982 stmt2 = gimple_build_assign (name, t);
984 /* Replace the SSA_NAME we compare against zero. Adjust
985 the type of zero accordingly. */
986 SET_USE (use, name);
987 gimple_cond_set_rhs (use_stmt, build_int_cst_type (TREE_TYPE (name), 0));
989 /* Don't use gsi_replace here, none of the new assignments sets
990 the variable originally set in stmt. Move bsi to stmt1, and
991 then remove the original stmt, so that we get a chance to
992 retain debug info for it. */
993 rsi = *bsi;
994 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
995 gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
996 gsi_remove (&rsi, true);
998 return stmt1;
1001 return stmt;
1004 /* For each statement determines the outermost loop in that it is invariant,
1005 - statements on whose motion it depends and the cost of the computation.
1006 - This information is stored to the LIM_DATA structure associated with
1007 - each statement. */
1008 class invariantness_dom_walker : public dom_walker
1010 public:
1011 invariantness_dom_walker (cdi_direction direction)
1012 : dom_walker (direction) {}
1014 virtual void before_dom_children (basic_block);
1017 /* Determine the outermost loops in that statements in basic block BB are
1018 invariant, and record them to the LIM_DATA associated with the statements.
1019 Callback for dom_walker. */
1021 void
1022 invariantness_dom_walker::before_dom_children (basic_block bb)
1024 enum move_pos pos;
1025 gimple_stmt_iterator bsi;
1026 gimple stmt;
1027 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
1028 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
1029 struct lim_aux_data *lim_data;
1031 if (!loop_outer (bb->loop_father))
1032 return;
1034 if (dump_file && (dump_flags & TDF_DETAILS))
1035 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
1036 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
1038 /* Look at PHI nodes, but only if there is at most two.
1039 ??? We could relax this further by post-processing the inserted
1040 code and transforming adjacent cond-exprs with the same predicate
1041 to control flow again. */
1042 bsi = gsi_start_phis (bb);
1043 if (!gsi_end_p (bsi)
1044 && ((gsi_next (&bsi), gsi_end_p (bsi))
1045 || (gsi_next (&bsi), gsi_end_p (bsi))))
1046 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1048 stmt = gsi_stmt (bsi);
1050 pos = movement_possibility (stmt);
1051 if (pos == MOVE_IMPOSSIBLE)
1052 continue;
1054 lim_data = init_lim_data (stmt);
1055 lim_data->always_executed_in = outermost;
1057 if (!determine_max_movement (stmt, false))
1059 lim_data->max_loop = NULL;
1060 continue;
1063 if (dump_file && (dump_flags & TDF_DETAILS))
1065 print_gimple_stmt (dump_file, stmt, 2, 0);
1066 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1067 loop_depth (lim_data->max_loop),
1068 lim_data->cost);
1071 if (lim_data->cost >= LIM_EXPENSIVE)
1072 set_profitable_level (stmt);
1075 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1077 stmt = gsi_stmt (bsi);
1079 pos = movement_possibility (stmt);
1080 if (pos == MOVE_IMPOSSIBLE)
1082 if (nonpure_call_p (stmt))
1084 maybe_never = true;
1085 outermost = NULL;
1087 /* Make sure to note always_executed_in for stores to make
1088 store-motion work. */
1089 else if (stmt_makes_single_store (stmt))
1091 struct lim_aux_data *lim_data = init_lim_data (stmt);
1092 lim_data->always_executed_in = outermost;
1094 continue;
1097 if (is_gimple_assign (stmt)
1098 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1099 == GIMPLE_BINARY_RHS))
1101 tree op0 = gimple_assign_rhs1 (stmt);
1102 tree op1 = gimple_assign_rhs2 (stmt);
1103 struct loop *ol1 = outermost_invariant_loop (op1,
1104 loop_containing_stmt (stmt));
1106 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1107 to be hoisted out of loop, saving expensive divide. */
1108 if (pos == MOVE_POSSIBLE
1109 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
1110 && flag_unsafe_math_optimizations
1111 && !flag_trapping_math
1112 && ol1 != NULL
1113 && outermost_invariant_loop (op0, ol1) == NULL)
1114 stmt = rewrite_reciprocal (&bsi);
1116 /* If the shift count is invariant, convert (A >> B) & 1 to
1117 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1118 saving an expensive shift. */
1119 if (pos == MOVE_POSSIBLE
1120 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
1121 && integer_onep (op1)
1122 && TREE_CODE (op0) == SSA_NAME
1123 && has_single_use (op0))
1124 stmt = rewrite_bittest (&bsi);
1127 lim_data = init_lim_data (stmt);
1128 lim_data->always_executed_in = outermost;
1130 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1131 continue;
1133 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1135 lim_data->max_loop = NULL;
1136 continue;
1139 if (dump_file && (dump_flags & TDF_DETAILS))
1141 print_gimple_stmt (dump_file, stmt, 2, 0);
1142 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1143 loop_depth (lim_data->max_loop),
1144 lim_data->cost);
1147 if (lim_data->cost >= LIM_EXPENSIVE)
1148 set_profitable_level (stmt);
1152 class move_computations_dom_walker : public dom_walker
1154 public:
1155 move_computations_dom_walker (cdi_direction direction)
1156 : dom_walker (direction), todo_ (0) {}
1158 virtual void before_dom_children (basic_block);
1160 unsigned int todo_;
1163 /* Hoist the statements in basic block BB out of the loops prescribed by
1164 data stored in LIM_DATA structures associated with each statement. Callback
1165 for walk_dominator_tree. */
1167 void
1168 move_computations_dom_walker::before_dom_children (basic_block bb)
1170 struct loop *level;
1171 gimple_stmt_iterator bsi;
1172 gimple stmt;
1173 unsigned cost = 0;
1174 struct lim_aux_data *lim_data;
1176 if (!loop_outer (bb->loop_father))
1177 return;
1179 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1181 gimple new_stmt;
1182 stmt = gsi_stmt (bsi);
1184 lim_data = get_lim_data (stmt);
1185 if (lim_data == NULL)
1187 gsi_next (&bsi);
1188 continue;
1191 cost = lim_data->cost;
1192 level = lim_data->tgt_loop;
1193 clear_lim_data (stmt);
1195 if (!level)
1197 gsi_next (&bsi);
1198 continue;
1201 if (dump_file && (dump_flags & TDF_DETAILS))
1203 fprintf (dump_file, "Moving PHI node\n");
1204 print_gimple_stmt (dump_file, stmt, 0, 0);
1205 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1206 cost, level->num);
1209 if (gimple_phi_num_args (stmt) == 1)
1211 tree arg = PHI_ARG_DEF (stmt, 0);
1212 new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
1213 gimple_phi_result (stmt),
1214 arg, NULL_TREE);
1216 else
1218 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
1219 gimple cond = gsi_stmt (gsi_last_bb (dom));
1220 tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
1221 /* Get the PHI arguments corresponding to the true and false
1222 edges of COND. */
1223 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
1224 gcc_assert (arg0 && arg1);
1225 t = build2 (gimple_cond_code (cond), boolean_type_node,
1226 gimple_cond_lhs (cond), gimple_cond_rhs (cond));
1227 new_stmt = gimple_build_assign_with_ops (COND_EXPR,
1228 gimple_phi_result (stmt),
1229 t, arg0, arg1);
1230 todo_ |= TODO_cleanup_cfg;
1232 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1233 remove_phi_node (&bsi, false);
1236 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1238 edge e;
1240 stmt = gsi_stmt (bsi);
1242 lim_data = get_lim_data (stmt);
1243 if (lim_data == NULL)
1245 gsi_next (&bsi);
1246 continue;
1249 cost = lim_data->cost;
1250 level = lim_data->tgt_loop;
1251 clear_lim_data (stmt);
1253 if (!level)
1255 gsi_next (&bsi);
1256 continue;
1259 /* We do not really want to move conditionals out of the loop; we just
1260 placed it here to force its operands to be moved if necessary. */
1261 if (gimple_code (stmt) == GIMPLE_COND)
1262 continue;
1264 if (dump_file && (dump_flags & TDF_DETAILS))
1266 fprintf (dump_file, "Moving statement\n");
1267 print_gimple_stmt (dump_file, stmt, 0, 0);
1268 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1269 cost, level->num);
1272 e = loop_preheader_edge (level);
1273 gcc_assert (!gimple_vdef (stmt));
1274 if (gimple_vuse (stmt))
1276 /* The new VUSE is the one from the virtual PHI in the loop
1277 header or the one already present. */
1278 gimple_stmt_iterator gsi2;
1279 for (gsi2 = gsi_start_phis (e->dest);
1280 !gsi_end_p (gsi2); gsi_next (&gsi2))
1282 gimple phi = gsi_stmt (gsi2);
1283 if (virtual_operand_p (gimple_phi_result (phi)))
1285 gimple_set_vuse (stmt, PHI_ARG_DEF_FROM_EDGE (phi, e));
1286 break;
1290 gsi_remove (&bsi, false);
1291 /* In case this is a stmt that is not unconditionally executed
1292 when the target loop header is executed and the stmt may
1293 invoke undefined integer or pointer overflow rewrite it to
1294 unsigned arithmetic. */
1295 if (is_gimple_assign (stmt)
1296 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
1297 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
1298 && arith_code_with_undefined_signed_overflow
1299 (gimple_assign_rhs_code (stmt))
1300 && (!ALWAYS_EXECUTED_IN (bb)
1301 || !(ALWAYS_EXECUTED_IN (bb) == level
1302 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1303 gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
1304 else
1305 gsi_insert_on_edge (e, stmt);
1309 /* Hoist the statements out of the loops prescribed by data stored in
1310 LIM_DATA structures associated with each statement.*/
1312 static unsigned int
1313 move_computations (void)
1315 move_computations_dom_walker walker (CDI_DOMINATORS);
1316 walker.walk (cfun->cfg->x_entry_block_ptr);
1318 gsi_commit_edge_inserts ();
1319 if (need_ssa_update_p (cfun))
1320 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1322 return walker.todo_;
1325 /* Checks whether the statement defining variable *INDEX can be hoisted
1326 out of the loop passed in DATA. Callback for for_each_index. */
1328 static bool
1329 may_move_till (tree ref, tree *index, void *data)
1331 struct loop *loop = (struct loop *) data, *max_loop;
1333 /* If REF is an array reference, check also that the step and the lower
1334 bound is invariant in LOOP. */
1335 if (TREE_CODE (ref) == ARRAY_REF)
1337 tree step = TREE_OPERAND (ref, 3);
1338 tree lbound = TREE_OPERAND (ref, 2);
1340 max_loop = outermost_invariant_loop (step, loop);
1341 if (!max_loop)
1342 return false;
1344 max_loop = outermost_invariant_loop (lbound, loop);
1345 if (!max_loop)
1346 return false;
1349 max_loop = outermost_invariant_loop (*index, loop);
1350 if (!max_loop)
1351 return false;
1353 return true;
1356 /* If OP is SSA NAME, force the statement that defines it to be
1357 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1359 static void
1360 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1362 gimple stmt;
1364 if (!op
1365 || is_gimple_min_invariant (op))
1366 return;
1368 gcc_assert (TREE_CODE (op) == SSA_NAME);
1370 stmt = SSA_NAME_DEF_STMT (op);
1371 if (gimple_nop_p (stmt))
1372 return;
1374 set_level (stmt, orig_loop, loop);
1377 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1378 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1379 for_each_index. */
1381 struct fmt_data
1383 struct loop *loop;
1384 struct loop *orig_loop;
1387 static bool
1388 force_move_till (tree ref, tree *index, void *data)
1390 struct fmt_data *fmt_data = (struct fmt_data *) data;
1392 if (TREE_CODE (ref) == ARRAY_REF)
1394 tree step = TREE_OPERAND (ref, 3);
1395 tree lbound = TREE_OPERAND (ref, 2);
1397 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1398 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1401 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1403 return true;
1406 /* A function to free the mem_ref object OBJ. */
1408 static void
1409 memref_free (struct im_mem_ref *mem)
1411 mem->accesses_in_loop.release ();
1414 /* Allocates and returns a memory reference description for MEM whose hash
1415 value is HASH and id is ID. */
1417 static mem_ref_p
1418 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1420 mem_ref_p ref = XOBNEW (&mem_ref_obstack, struct im_mem_ref);
1421 ao_ref_init (&ref->mem, mem);
1422 ref->id = id;
1423 ref->hash = hash;
1424 ref->stored = NULL;
1425 bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
1426 bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
1427 ref->accesses_in_loop.create (1);
1429 return ref;
1432 /* Records memory reference location *LOC in LOOP to the memory reference
1433 description REF. The reference occurs in statement STMT. */
1435 static void
1436 record_mem_ref_loc (mem_ref_p ref, gimple stmt, tree *loc)
1438 mem_ref_loc aref;
1439 aref.stmt = stmt;
1440 aref.ref = loc;
1441 ref->accesses_in_loop.safe_push (aref);
1444 /* Set the LOOP bit in REF stored bitmap and allocate that if
1445 necessary. Return whether a bit was changed. */
1447 static bool
1448 set_ref_stored_in_loop (mem_ref_p ref, struct loop *loop)
1450 if (!ref->stored)
1451 ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
1452 return bitmap_set_bit (ref->stored, loop->num);
1455 /* Marks reference REF as stored in LOOP. */
1457 static void
1458 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1460 while (loop != current_loops->tree_root
1461 && set_ref_stored_in_loop (ref, loop))
1462 loop = loop_outer (loop);
1465 /* Gathers memory references in statement STMT in LOOP, storing the
1466 information about them in the memory_accesses structure. Marks
1467 the vops accessed through unrecognized statements there as
1468 well. */
1470 static void
1471 gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1473 tree *mem = NULL;
1474 hashval_t hash;
1475 im_mem_ref **slot;
1476 mem_ref_p ref;
1477 bool is_stored;
1478 unsigned id;
1480 if (!gimple_vuse (stmt))
1481 return;
1483 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1484 if (!mem)
1486 /* We use the shared mem_ref for all unanalyzable refs. */
1487 id = UNANALYZABLE_MEM_ID;
1488 ref = memory_accesses.refs_list[id];
1489 if (dump_file && (dump_flags & TDF_DETAILS))
1491 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
1492 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1494 is_stored = gimple_vdef (stmt);
1496 else
1498 hash = iterative_hash_expr (*mem, 0);
1499 slot = memory_accesses.refs->find_slot_with_hash (*mem, hash, INSERT);
1500 if (*slot)
1502 ref = (mem_ref_p) *slot;
1503 id = ref->id;
1505 else
1507 id = memory_accesses.refs_list.length ();
1508 ref = mem_ref_alloc (*mem, hash, id);
1509 memory_accesses.refs_list.safe_push (ref);
1510 *slot = ref;
1512 if (dump_file && (dump_flags & TDF_DETAILS))
1514 fprintf (dump_file, "Memory reference %u: ", id);
1515 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
1516 fprintf (dump_file, "\n");
1520 record_mem_ref_loc (ref, stmt, mem);
1522 bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
1523 if (is_stored)
1525 bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
1526 mark_ref_stored (ref, loop);
1528 return;
1531 static unsigned *bb_loop_postorder;
1533 /* qsort sort function to sort blocks after their loop fathers postorder. */
1535 static int
1536 sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
1538 basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
1539 basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
1540 struct loop *loop1 = bb1->loop_father;
1541 struct loop *loop2 = bb2->loop_father;
1542 if (loop1->num == loop2->num)
1543 return 0;
1544 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1547 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1549 static int
1550 sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
1552 mem_ref_loc *loc1 = (mem_ref_loc *)const_cast<void *>(loc1_);
1553 mem_ref_loc *loc2 = (mem_ref_loc *)const_cast<void *>(loc2_);
1554 struct loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
1555 struct loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
1556 if (loop1->num == loop2->num)
1557 return 0;
1558 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1561 /* Gathers memory references in loops. */
1563 static void
1564 analyze_memory_references (void)
1566 gimple_stmt_iterator bsi;
1567 basic_block bb, *bbs;
1568 struct loop *loop, *outer;
1569 unsigned i, n;
1571 /* Collect all basic-blocks in loops and sort them after their
1572 loops postorder. */
1573 i = 0;
1574 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
1575 FOR_EACH_BB_FN (bb, cfun)
1576 if (bb->loop_father != current_loops->tree_root)
1577 bbs[i++] = bb;
1578 n = i;
1579 qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
1581 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1582 That results in better locality for all the bitmaps. */
1583 for (i = 0; i < n; ++i)
1585 basic_block bb = bbs[i];
1586 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1587 gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
1590 /* Sort the location list of gathered memory references after their
1591 loop postorder number. */
1592 im_mem_ref *ref;
1593 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
1594 ref->accesses_in_loop.qsort (sort_locs_in_loop_postorder_cmp);
1596 free (bbs);
1597 // free (bb_loop_postorder);
1599 /* Propagate the information about accessed memory references up
1600 the loop hierarchy. */
1601 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1603 /* Finalize the overall touched references (including subloops). */
1604 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
1605 &memory_accesses.refs_stored_in_loop[loop->num]);
1607 /* Propagate the information about accessed memory references up
1608 the loop hierarchy. */
1609 outer = loop_outer (loop);
1610 if (outer == current_loops->tree_root)
1611 continue;
1613 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
1614 &memory_accesses.all_refs_stored_in_loop[loop->num]);
1618 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1619 tree_to_aff_combination_expand. */
1621 static bool
1622 mem_refs_may_alias_p (mem_ref_p mem1, mem_ref_p mem2,
1623 hash_map<tree, name_expansion *> **ttae_cache)
1625 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1626 object and their offset differ in such a way that the locations cannot
1627 overlap, then they cannot alias. */
1628 widest_int size1, size2;
1629 aff_tree off1, off2;
1631 /* Perform basic offset and type-based disambiguation. */
1632 if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
1633 return false;
1635 /* The expansion of addresses may be a bit expensive, thus we only do
1636 the check at -O2 and higher optimization levels. */
1637 if (optimize < 2)
1638 return true;
1640 get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
1641 get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
1642 aff_combination_expand (&off1, ttae_cache);
1643 aff_combination_expand (&off2, ttae_cache);
1644 aff_combination_scale (&off1, -1);
1645 aff_combination_add (&off2, &off1);
1647 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1648 return false;
1650 return true;
1653 /* Compare function for bsearch searching for reference locations
1654 in a loop. */
1656 static int
1657 find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
1659 struct loop *loop = (struct loop *)const_cast<void *>(loop_);
1660 mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
1661 struct loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
1662 if (loop->num == loc_loop->num
1663 || flow_loop_nested_p (loop, loc_loop))
1664 return 0;
1665 return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
1666 ? -1 : 1);
1669 /* Iterates over all locations of REF in LOOP and its subloops calling
1670 fn.operator() with the location as argument. When that operator
1671 returns true the iteration is stopped and true is returned.
1672 Otherwise false is returned. */
1674 template <typename FN>
1675 static bool
1676 for_all_locs_in_loop (struct loop *loop, mem_ref_p ref, FN fn)
1678 unsigned i;
1679 mem_ref_loc_p loc;
1681 /* Search for the cluster of locs in the accesses_in_loop vector
1682 which is sorted after postorder index of the loop father. */
1683 loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp);
1684 if (!loc)
1685 return false;
1687 /* We have found one location inside loop or its sub-loops. Iterate
1688 both forward and backward to cover the whole cluster. */
1689 i = loc - ref->accesses_in_loop.address ();
1690 while (i > 0)
1692 --i;
1693 mem_ref_loc_p l = &ref->accesses_in_loop[i];
1694 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1695 break;
1696 if (fn (l))
1697 return true;
1699 for (i = loc - ref->accesses_in_loop.address ();
1700 i < ref->accesses_in_loop.length (); ++i)
1702 mem_ref_loc_p l = &ref->accesses_in_loop[i];
1703 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1704 break;
1705 if (fn (l))
1706 return true;
1709 return false;
1712 /* Rewrites location LOC by TMP_VAR. */
1714 struct rewrite_mem_ref_loc
1716 rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
1717 bool operator () (mem_ref_loc_p loc);
1718 tree tmp_var;
1721 bool
1722 rewrite_mem_ref_loc::operator () (mem_ref_loc_p loc)
1724 *loc->ref = tmp_var;
1725 update_stmt (loc->stmt);
1726 return false;
1729 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1731 static void
1732 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1734 for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1737 /* Stores the first reference location in LOCP. */
1739 struct first_mem_ref_loc_1
1741 first_mem_ref_loc_1 (mem_ref_loc_p *locp_) : locp (locp_) {}
1742 bool operator () (mem_ref_loc_p loc);
1743 mem_ref_loc_p *locp;
1746 bool
1747 first_mem_ref_loc_1::operator () (mem_ref_loc_p loc)
1749 *locp = loc;
1750 return true;
1753 /* Returns the first reference location to REF in LOOP. */
1755 static mem_ref_loc_p
1756 first_mem_ref_loc (struct loop *loop, mem_ref_p ref)
1758 mem_ref_loc_p locp = NULL;
1759 for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
1760 return locp;
1763 struct prev_flag_edges {
1764 /* Edge to insert new flag comparison code. */
1765 edge append_cond_position;
1767 /* Edge for fall through from previous flag comparison. */
1768 edge last_cond_fallthru;
1771 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1772 MEM along edge EX.
1774 The store is only done if MEM has changed. We do this so no
1775 changes to MEM occur on code paths that did not originally store
1776 into it.
1778 The common case for execute_sm will transform:
1780 for (...) {
1781 if (foo)
1782 stuff;
1783 else
1784 MEM = TMP_VAR;
1787 into:
1789 lsm = MEM;
1790 for (...) {
1791 if (foo)
1792 stuff;
1793 else
1794 lsm = TMP_VAR;
1796 MEM = lsm;
1798 This function will generate:
1800 lsm = MEM;
1802 lsm_flag = false;
1804 for (...) {
1805 if (foo)
1806 stuff;
1807 else {
1808 lsm = TMP_VAR;
1809 lsm_flag = true;
1812 if (lsm_flag) <--
1813 MEM = lsm; <--
1816 static void
1817 execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag)
1819 basic_block new_bb, then_bb, old_dest;
1820 bool loop_has_only_one_exit;
1821 edge then_old_edge, orig_ex = ex;
1822 gimple_stmt_iterator gsi;
1823 gimple stmt;
1824 struct prev_flag_edges *prev_edges = (struct prev_flag_edges *) ex->aux;
1825 bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;
1827 /* ?? Insert store after previous store if applicable. See note
1828 below. */
1829 if (prev_edges)
1830 ex = prev_edges->append_cond_position;
1832 loop_has_only_one_exit = single_pred_p (ex->dest);
1834 if (loop_has_only_one_exit)
1835 ex = split_block_after_labels (ex->dest);
1837 old_dest = ex->dest;
1838 new_bb = split_edge (ex);
1839 then_bb = create_empty_bb (new_bb);
1840 if (irr)
1841 then_bb->flags = BB_IRREDUCIBLE_LOOP;
1842 add_bb_to_loop (then_bb, new_bb->loop_father);
1844 gsi = gsi_start_bb (new_bb);
1845 stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
1846 NULL_TREE, NULL_TREE);
1847 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1849 gsi = gsi_start_bb (then_bb);
1850 /* Insert actual store. */
1851 stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
1852 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1854 make_edge (new_bb, then_bb,
1855 EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1856 make_edge (new_bb, old_dest,
1857 EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1858 then_old_edge = make_edge (then_bb, old_dest,
1859 EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1861 set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
1863 if (prev_edges)
1865 basic_block prevbb = prev_edges->last_cond_fallthru->src;
1866 redirect_edge_succ (prev_edges->last_cond_fallthru, new_bb);
1867 set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
1868 set_immediate_dominator (CDI_DOMINATORS, old_dest,
1869 recompute_dominator (CDI_DOMINATORS, old_dest));
1872 /* ?? Because stores may alias, they must happen in the exact
1873 sequence they originally happened. Save the position right after
1874 the (_lsm) store we just created so we can continue appending after
1875 it and maintain the original order. */
1877 struct prev_flag_edges *p;
1879 if (orig_ex->aux)
1880 orig_ex->aux = NULL;
1881 alloc_aux_for_edge (orig_ex, sizeof (struct prev_flag_edges));
1882 p = (struct prev_flag_edges *) orig_ex->aux;
1883 p->append_cond_position = then_old_edge;
1884 p->last_cond_fallthru = find_edge (new_bb, old_dest);
1885 orig_ex->aux = (void *) p;
1888 if (!loop_has_only_one_exit)
1889 for (gsi = gsi_start_phis (old_dest); !gsi_end_p (gsi); gsi_next (&gsi))
1891 gimple phi = gsi_stmt (gsi);
1892 unsigned i;
1894 for (i = 0; i < gimple_phi_num_args (phi); i++)
1895 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
1897 tree arg = gimple_phi_arg_def (phi, i);
1898 add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
1899 update_stmt (phi);
1902 /* Remove the original fall through edge. This was the
1903 single_succ_edge (new_bb). */
1904 EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
1907 /* When REF is set on the location, set flag indicating the store. */
1909 struct sm_set_flag_if_changed
1911 sm_set_flag_if_changed (tree flag_) : flag (flag_) {}
1912 bool operator () (mem_ref_loc_p loc);
1913 tree flag;
1916 bool
1917 sm_set_flag_if_changed::operator () (mem_ref_loc_p loc)
1919 /* Only set the flag for writes. */
1920 if (is_gimple_assign (loc->stmt)
1921 && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
1923 gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
1924 gimple stmt = gimple_build_assign (flag, boolean_true_node);
1925 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1927 return false;
1930 /* Helper function for execute_sm. On every location where REF is
1931 set, set an appropriate flag indicating the store. */
1933 static tree
1934 execute_sm_if_changed_flag_set (struct loop *loop, mem_ref_p ref)
1936 tree flag;
1937 char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
1938 flag = create_tmp_reg (boolean_type_node, str);
1939 for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag));
1940 return flag;
1943 /* Executes store motion of memory reference REF from LOOP.
1944 Exits from the LOOP are stored in EXITS. The initialization of the
1945 temporary variable is put to the preheader of the loop, and assignments
1946 to the reference from the temporary variable are emitted to exits. */
1948 static void
1949 execute_sm (struct loop *loop, vec<edge> exits, mem_ref_p ref)
1951 tree tmp_var, store_flag = NULL_TREE;
1952 unsigned i;
1953 gimple load;
1954 struct fmt_data fmt_data;
1955 edge ex;
1956 struct lim_aux_data *lim_data;
1957 bool multi_threaded_model_p = false;
1958 gimple_stmt_iterator gsi;
1960 if (dump_file && (dump_flags & TDF_DETAILS))
1962 fprintf (dump_file, "Executing store motion of ");
1963 print_generic_expr (dump_file, ref->mem.ref, 0);
1964 fprintf (dump_file, " from loop %d\n", loop->num);
1967 tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
1968 get_lsm_tmp_name (ref->mem.ref, ~0));
1970 fmt_data.loop = loop;
1971 fmt_data.orig_loop = loop;
1972 for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
1974 if (bb_in_transaction (loop_preheader_edge (loop)->src)
1975 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES))
1976 multi_threaded_model_p = true;
1978 if (multi_threaded_model_p)
1979 store_flag = execute_sm_if_changed_flag_set (loop, ref);
1981 rewrite_mem_refs (loop, ref, tmp_var);
1983 /* Emit the load code on a random exit edge or into the latch if
1984 the loop does not exit, so that we are sure it will be processed
1985 by move_computations after all dependencies. */
1986 gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
1988 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
1989 load altogether, since the store is predicated by a flag. We
1990 could, do the load only if it was originally in the loop. */
1991 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
1992 lim_data = init_lim_data (load);
1993 lim_data->max_loop = loop;
1994 lim_data->tgt_loop = loop;
1995 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1997 if (multi_threaded_model_p)
1999 load = gimple_build_assign (store_flag, boolean_false_node);
2000 lim_data = init_lim_data (load);
2001 lim_data->max_loop = loop;
2002 lim_data->tgt_loop = loop;
2003 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
2006 /* Sink the store to every exit from the loop. */
2007 FOR_EACH_VEC_ELT (exits, i, ex)
2008 if (!multi_threaded_model_p)
2010 gimple store;
2011 store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
2012 gsi_insert_on_edge (ex, store);
2014 else
2015 execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag);
2018 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2019 edges of the LOOP. */
2021 static void
2022 hoist_memory_references (struct loop *loop, bitmap mem_refs,
2023 vec<edge> exits)
2025 mem_ref_p ref;
2026 unsigned i;
2027 bitmap_iterator bi;
2029 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2031 ref = memory_accesses.refs_list[i];
2032 execute_sm (loop, exits, ref);
2036 struct ref_always_accessed
2038 ref_always_accessed (struct loop *loop_, bool stored_p_)
2039 : loop (loop_), stored_p (stored_p_) {}
2040 bool operator () (mem_ref_loc_p loc);
2041 struct loop *loop;
2042 bool stored_p;
2045 bool
2046 ref_always_accessed::operator () (mem_ref_loc_p loc)
2048 struct loop *must_exec;
2050 if (!get_lim_data (loc->stmt))
2051 return false;
2053 /* If we require an always executed store make sure the statement
2054 stores to the reference. */
2055 if (stored_p)
2057 tree lhs = gimple_get_lhs (loc->stmt);
2058 if (!lhs
2059 || lhs != *loc->ref)
2060 return false;
2063 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2064 if (!must_exec)
2065 return false;
2067 if (must_exec == loop
2068 || flow_loop_nested_p (must_exec, loop))
2069 return true;
2071 return false;
2074 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2075 make sure REF is always stored to in LOOP. */
2077 static bool
2078 ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
2080 return for_all_locs_in_loop (loop, ref,
2081 ref_always_accessed (loop, stored_p));
2084 /* Returns true if REF1 and REF2 are independent. */
2086 static bool
2087 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
2089 if (ref1 == ref2)
2090 return true;
2092 if (dump_file && (dump_flags & TDF_DETAILS))
2093 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2094 ref1->id, ref2->id);
2096 if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
2098 if (dump_file && (dump_flags & TDF_DETAILS))
2099 fprintf (dump_file, "dependent.\n");
2100 return false;
2102 else
2104 if (dump_file && (dump_flags & TDF_DETAILS))
2105 fprintf (dump_file, "independent.\n");
2106 return true;
2110 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2111 and its super-loops. */
2113 static void
2114 record_dep_loop (struct loop *loop, mem_ref_p ref, bool stored_p)
2116 /* We can propagate dependent-in-loop bits up the loop
2117 hierarchy to all outer loops. */
2118 while (loop != current_loops->tree_root
2119 && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2120 loop = loop_outer (loop);
2123 /* Returns true if REF is independent on all other memory references in
2124 LOOP. */
2126 static bool
2127 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref, bool stored_p)
2129 bitmap refs_to_check;
2130 unsigned i;
2131 bitmap_iterator bi;
2132 mem_ref_p aref;
2134 if (stored_p)
2135 refs_to_check = &memory_accesses.refs_in_loop[loop->num];
2136 else
2137 refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
2139 if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
2140 return false;
2142 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2144 aref = memory_accesses.refs_list[i];
2145 if (!refs_independent_p (ref, aref))
2146 return false;
2149 return true;
2152 /* Returns true if REF is independent on all other memory references in
2153 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2155 static bool
2156 ref_indep_loop_p_2 (struct loop *loop, mem_ref_p ref, bool stored_p)
2158 stored_p |= (ref->stored && bitmap_bit_p (ref->stored, loop->num));
2160 if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2161 return true;
2162 if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2163 return false;
2165 struct loop *inner = loop->inner;
2166 while (inner)
2168 if (!ref_indep_loop_p_2 (inner, ref, stored_p))
2169 return false;
2170 inner = inner->next;
2173 bool indep_p = ref_indep_loop_p_1 (loop, ref, stored_p);
2175 if (dump_file && (dump_flags & TDF_DETAILS))
2176 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2177 ref->id, loop->num, indep_p ? "independent" : "dependent");
2179 /* Record the computed result in the cache. */
2180 if (indep_p)
2182 if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
2183 && stored_p)
2185 /* If it's independend against all refs then it's independent
2186 against stores, too. */
2187 bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
2190 else
2192 record_dep_loop (loop, ref, stored_p);
2193 if (!stored_p)
2195 /* If it's dependent against stores it's dependent against
2196 all refs, too. */
2197 record_dep_loop (loop, ref, true);
2201 return indep_p;
2204 /* Returns true if REF is independent on all other memory references in
2205 LOOP. */
2207 static bool
2208 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2210 gcc_checking_assert (MEM_ANALYZABLE (ref));
2212 return ref_indep_loop_p_2 (loop, ref, false);
2215 /* Returns true if we can perform store motion of REF from LOOP. */
2217 static bool
2218 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2220 tree base;
2222 /* Can't hoist unanalyzable refs. */
2223 if (!MEM_ANALYZABLE (ref))
2224 return false;
2226 /* It should be movable. */
2227 if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
2228 || TREE_THIS_VOLATILE (ref->mem.ref)
2229 || !for_each_index (&ref->mem.ref, may_move_till, loop))
2230 return false;
2232 /* If it can throw fail, we do not properly update EH info. */
2233 if (tree_could_throw_p (ref->mem.ref))
2234 return false;
2236 /* If it can trap, it must be always executed in LOOP.
2237 Readonly memory locations may trap when storing to them, but
2238 tree_could_trap_p is a predicate for rvalues, so check that
2239 explicitly. */
2240 base = get_base_address (ref->mem.ref);
2241 if ((tree_could_trap_p (ref->mem.ref)
2242 || (DECL_P (base) && TREE_READONLY (base)))
2243 && !ref_always_accessed_p (loop, ref, true))
2244 return false;
2246 /* And it must be independent on all other memory references
2247 in LOOP. */
2248 if (!ref_indep_loop_p (loop, ref))
2249 return false;
2251 return true;
2254 /* Marks the references in LOOP for that store motion should be performed
2255 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2256 motion was performed in one of the outer loops. */
2258 static void
2259 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2261 bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
2262 unsigned i;
2263 bitmap_iterator bi;
2264 mem_ref_p ref;
2266 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2268 ref = memory_accesses.refs_list[i];
2269 if (can_sm_ref_p (loop, ref))
2270 bitmap_set_bit (refs_to_sm, i);
2274 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2275 for a store motion optimization (i.e. whether we can insert statement
2276 on its exits). */
2278 static bool
2279 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2280 vec<edge> exits)
2282 unsigned i;
2283 edge ex;
2285 FOR_EACH_VEC_ELT (exits, i, ex)
2286 if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
2287 return false;
2289 return true;
2292 /* Try to perform store motion for all memory references modified inside
2293 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2294 store motion was executed in one of the outer loops. */
2296 static void
2297 store_motion_loop (struct loop *loop, bitmap sm_executed)
2299 vec<edge> exits = get_loop_exit_edges (loop);
2300 struct loop *subloop;
2301 bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
2303 if (loop_suitable_for_sm (loop, exits))
2305 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2306 hoist_memory_references (loop, sm_in_loop, exits);
2308 exits.release ();
2310 bitmap_ior_into (sm_executed, sm_in_loop);
2311 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2312 store_motion_loop (subloop, sm_executed);
2313 bitmap_and_compl_into (sm_executed, sm_in_loop);
2314 BITMAP_FREE (sm_in_loop);
2317 /* Try to perform store motion for all memory references modified inside
2318 loops. */
2320 static void
2321 store_motion (void)
2323 struct loop *loop;
2324 bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
2326 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2327 store_motion_loop (loop, sm_executed);
2329 BITMAP_FREE (sm_executed);
2330 gsi_commit_edge_inserts ();
2333 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2334 for each such basic block bb records the outermost loop for that execution
2335 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2336 blocks that contain a nonpure call. */
2338 static void
2339 fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
2341 basic_block bb = NULL, *bbs, last = NULL;
2342 unsigned i;
2343 edge e;
2344 struct loop *inn_loop = loop;
2346 if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
2348 bbs = get_loop_body_in_dom_order (loop);
2350 for (i = 0; i < loop->num_nodes; i++)
2352 edge_iterator ei;
2353 bb = bbs[i];
2355 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2356 last = bb;
2358 if (bitmap_bit_p (contains_call, bb->index))
2359 break;
2361 FOR_EACH_EDGE (e, ei, bb->succs)
2362 if (!flow_bb_inside_loop_p (loop, e->dest))
2363 break;
2364 if (e)
2365 break;
2367 /* A loop might be infinite (TODO use simple loop analysis
2368 to disprove this if possible). */
2369 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2370 break;
2372 if (!flow_bb_inside_loop_p (inn_loop, bb))
2373 break;
2375 if (bb->loop_father->header == bb)
2377 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2378 break;
2380 /* In a loop that is always entered we may proceed anyway.
2381 But record that we entered it and stop once we leave it. */
2382 inn_loop = bb->loop_father;
2386 while (1)
2388 SET_ALWAYS_EXECUTED_IN (last, loop);
2389 if (last == loop->header)
2390 break;
2391 last = get_immediate_dominator (CDI_DOMINATORS, last);
2394 free (bbs);
2397 for (loop = loop->inner; loop; loop = loop->next)
2398 fill_always_executed_in_1 (loop, contains_call);
2401 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2402 for each such basic block bb records the outermost loop for that execution
2403 of its header implies execution of bb. */
2405 static void
2406 fill_always_executed_in (void)
2408 sbitmap contains_call = sbitmap_alloc (last_basic_block_for_fn (cfun));
2409 basic_block bb;
2410 struct loop *loop;
2412 bitmap_clear (contains_call);
2413 FOR_EACH_BB_FN (bb, cfun)
2415 gimple_stmt_iterator gsi;
2416 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2418 if (nonpure_call_p (gsi_stmt (gsi)))
2419 break;
2422 if (!gsi_end_p (gsi))
2423 bitmap_set_bit (contains_call, bb->index);
2426 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2427 fill_always_executed_in_1 (loop, contains_call);
2429 sbitmap_free (contains_call);
2433 /* Compute the global information needed by the loop invariant motion pass. */
2435 static void
2436 tree_ssa_lim_initialize (void)
2438 struct loop *loop;
2439 unsigned i;
2441 bitmap_obstack_initialize (&lim_bitmap_obstack);
2442 gcc_obstack_init (&mem_ref_obstack);
2443 lim_aux_data_map = new hash_map<gimple, lim_aux_data *>;
2445 if (flag_tm)
2446 compute_transaction_bits ();
2448 alloc_aux_for_edges (0);
2450 memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
2451 memory_accesses.refs_list.create (100);
2452 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2453 memory_accesses.refs_list.quick_push
2454 (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
2456 memory_accesses.refs_in_loop.create (number_of_loops (cfun));
2457 memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
2458 memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
2459 memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2460 memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
2461 memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2463 for (i = 0; i < number_of_loops (cfun); i++)
2465 bitmap_initialize (&memory_accesses.refs_in_loop[i],
2466 &lim_bitmap_obstack);
2467 bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
2468 &lim_bitmap_obstack);
2469 bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
2470 &lim_bitmap_obstack);
2473 memory_accesses.ttae_cache = NULL;
2475 /* Initialize bb_loop_postorder with a mapping from loop->num to
2476 its postorder index. */
2477 i = 0;
2478 bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
2479 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2480 bb_loop_postorder[loop->num] = i++;
2483 /* Cleans up after the invariant motion pass. */
2485 static void
2486 tree_ssa_lim_finalize (void)
2488 basic_block bb;
2489 unsigned i;
2490 mem_ref_p ref;
2492 free_aux_for_edges ();
2494 FOR_EACH_BB_FN (bb, cfun)
2495 SET_ALWAYS_EXECUTED_IN (bb, NULL);
2497 bitmap_obstack_release (&lim_bitmap_obstack);
2498 delete lim_aux_data_map;
2500 delete memory_accesses.refs;
2501 memory_accesses.refs = NULL;
2503 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
2504 memref_free (ref);
2505 memory_accesses.refs_list.release ();
2506 obstack_free (&mem_ref_obstack, NULL);
2508 memory_accesses.refs_in_loop.release ();
2509 memory_accesses.refs_stored_in_loop.release ();
2510 memory_accesses.all_refs_stored_in_loop.release ();
2512 if (memory_accesses.ttae_cache)
2513 free_affine_expand_cache (&memory_accesses.ttae_cache);
2515 free (bb_loop_postorder);
2518 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2519 i.e. those that are likely to be win regardless of the register pressure. */
2521 unsigned int
2522 tree_ssa_lim (void)
2524 unsigned int todo;
2526 tree_ssa_lim_initialize ();
2528 /* Gathers information about memory accesses in the loops. */
2529 analyze_memory_references ();
2531 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2532 fill_always_executed_in ();
2534 /* For each statement determine the outermost loop in that it is
2535 invariant and cost for computing the invariant. */
2536 invariantness_dom_walker (CDI_DOMINATORS)
2537 .walk (cfun->cfg->x_entry_block_ptr);
2539 /* Execute store motion. Force the necessary invariants to be moved
2540 out of the loops as well. */
2541 store_motion ();
2543 /* Move the expressions that are expensive enough. */
2544 todo = move_computations ();
2546 tree_ssa_lim_finalize ();
2548 return todo;
2551 /* Loop invariant motion pass. */
2553 namespace {
2555 const pass_data pass_data_lim =
2557 GIMPLE_PASS, /* type */
2558 "lim", /* name */
2559 OPTGROUP_LOOP, /* optinfo_flags */
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 virtual bool gate (function *) { return flag_tree_loop_im != 0; }
2578 virtual unsigned int execute (function *);
2580 }; // class pass_lim
2582 unsigned int
2583 pass_lim::execute (function *fun)
2585 if (number_of_loops (fun) <= 1)
2586 return 0;
2588 return tree_ssa_lim ();
2591 } // anon namespace
2593 gimple_opt_pass *
2594 make_pass_lim (gcc::context *ctxt)
2596 return new pass_lim (ctxt);