poly_int: expand_vector_ubsan_overflow
[official-gcc.git] / gcc / tree-ssa-loop-im.c
blobe62759b4bd4a551578af06a93d1a2ec58e7331d3
1 /* Loop invariant motion.
2 Copyright (C) 2003-2017 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 "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "cfghooks.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "fold-const.h"
31 #include "cfganal.h"
32 #include "tree-eh.h"
33 #include "gimplify.h"
34 #include "gimple-iterator.h"
35 #include "tree-cfg.h"
36 #include "tree-ssa-loop-manip.h"
37 #include "tree-ssa-loop.h"
38 #include "tree-into-ssa.h"
39 #include "cfgloop.h"
40 #include "domwalk.h"
41 #include "params.h"
42 #include "tree-affine.h"
43 #include "tree-ssa-propagate.h"
44 #include "trans-mem.h"
45 #include "gimple-fold.h"
46 #include "tree-scalar-evolution.h"
47 #include "tree-ssa-loop-niter.h"
49 /* TODO: Support for predicated code motion. I.e.
51 while (1)
53 if (cond)
55 a = inv;
56 something;
60 Where COND and INV are invariants, but evaluating INV may trap or be
61 invalid from some other reason if !COND. This may be transformed to
63 if (cond)
64 a = inv;
65 while (1)
67 if (cond)
68 something;
69 } */
71 /* The auxiliary data kept for each statement. */
73 struct lim_aux_data
75 struct loop *max_loop; /* The outermost loop in that the statement
76 is invariant. */
78 struct loop *tgt_loop; /* The loop out of that we want to move the
79 invariant. */
81 struct loop *always_executed_in;
82 /* The outermost loop for that we are sure
83 the statement is executed if the loop
84 is entered. */
86 unsigned cost; /* Cost of the computation performed by the
87 statement. */
89 unsigned ref; /* The simple_mem_ref in this stmt or 0. */
91 vec<gimple *> depends; /* Vector of statements that must be also
92 hoisted out of the loop when this statement
93 is hoisted; i.e. those that define the
94 operands of the statement and are inside of
95 the MAX_LOOP loop. */
98 /* Maps statements to their lim_aux_data. */
100 static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;
102 /* Description of a memory reference location. */
104 struct mem_ref_loc
106 tree *ref; /* The reference itself. */
107 gimple *stmt; /* The statement in that it occurs. */
111 /* Description of a memory reference. */
113 struct im_mem_ref
115 unsigned id; /* ID assigned to the memory reference
116 (its index in memory_accesses.refs_list) */
117 hashval_t hash; /* Its hash value. */
119 /* The memory access itself and associated caching of alias-oracle
120 query meta-data. */
121 ao_ref mem;
123 bitmap stored; /* The set of loops in that this memory location
124 is stored to. */
125 vec<mem_ref_loc> accesses_in_loop;
126 /* The locations of the accesses. Vector
127 indexed by the loop number. */
129 /* The following sets are computed on demand. We keep both set and
130 its complement, so that we know whether the information was
131 already computed or not. */
132 bitmap_head indep_loop; /* The set of loops in that the memory
133 reference is independent, meaning:
134 If it is stored in the loop, this store
135 is independent on all other loads and
136 stores.
137 If it is only loaded, then it is independent
138 on all stores in the loop. */
139 bitmap_head dep_loop; /* The complement of INDEP_LOOP. */
142 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
143 to record (in)dependence against stores in the loop and its subloops, the
144 second to record (in)dependence against all references in the loop
145 and its subloops. */
146 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
148 /* Mem_ref hashtable helpers. */
150 struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
152 typedef tree_node *compare_type;
153 static inline hashval_t hash (const im_mem_ref *);
154 static inline bool equal (const im_mem_ref *, const tree_node *);
157 /* A hash function for struct im_mem_ref object OBJ. */
159 inline hashval_t
160 mem_ref_hasher::hash (const im_mem_ref *mem)
162 return mem->hash;
165 /* An equality function for struct im_mem_ref object MEM1 with
166 memory reference OBJ2. */
168 inline bool
169 mem_ref_hasher::equal (const im_mem_ref *mem1, const tree_node *obj2)
171 return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
175 /* Description of memory accesses in loops. */
177 static struct
179 /* The hash table of memory references accessed in loops. */
180 hash_table<mem_ref_hasher> *refs;
182 /* The list of memory references. */
183 vec<im_mem_ref *> refs_list;
185 /* The set of memory references accessed in each loop. */
186 vec<bitmap_head> refs_in_loop;
188 /* The set of memory references stored in each loop. */
189 vec<bitmap_head> refs_stored_in_loop;
191 /* The set of memory references stored in each loop, including subloops . */
192 vec<bitmap_head> all_refs_stored_in_loop;
194 /* Cache for expanding memory addresses. */
195 hash_map<tree, name_expansion *> *ttae_cache;
196 } memory_accesses;
198 /* Obstack for the bitmaps in the above data structures. */
199 static bitmap_obstack lim_bitmap_obstack;
200 static obstack mem_ref_obstack;
202 static bool ref_indep_loop_p (struct loop *, im_mem_ref *);
203 static bool ref_always_accessed_p (struct loop *, im_mem_ref *, bool);
205 /* Minimum cost of an expensive expression. */
206 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
208 /* The outermost loop for which execution of the header guarantees that the
209 block will be executed. */
210 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
211 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
213 /* ID of the shared unanalyzable mem. */
214 #define UNANALYZABLE_MEM_ID 0
216 /* Whether the reference was analyzable. */
217 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
219 static struct lim_aux_data *
220 init_lim_data (gimple *stmt)
222 lim_aux_data *p = XCNEW (struct lim_aux_data);
223 lim_aux_data_map->put (stmt, p);
225 return p;
228 static struct lim_aux_data *
229 get_lim_data (gimple *stmt)
231 lim_aux_data **p = lim_aux_data_map->get (stmt);
232 if (!p)
233 return NULL;
235 return *p;
238 /* Releases the memory occupied by DATA. */
240 static void
241 free_lim_aux_data (struct lim_aux_data *data)
243 data->depends.release ();
244 free (data);
247 static void
248 clear_lim_data (gimple *stmt)
250 lim_aux_data **p = lim_aux_data_map->get (stmt);
251 if (!p)
252 return;
254 free_lim_aux_data (*p);
255 *p = NULL;
259 /* The possibilities of statement movement. */
260 enum move_pos
262 MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
263 MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
264 become executed -- memory accesses, ... */
265 MOVE_POSSIBLE /* Unlimited movement. */
269 /* If it is possible to hoist the statement STMT unconditionally,
270 returns MOVE_POSSIBLE.
271 If it is possible to hoist the statement STMT, but we must avoid making
272 it executed if it would not be executed in the original program (e.g.
273 because it may trap), return MOVE_PRESERVE_EXECUTION.
274 Otherwise return MOVE_IMPOSSIBLE. */
276 enum move_pos
277 movement_possibility (gimple *stmt)
279 tree lhs;
280 enum move_pos ret = MOVE_POSSIBLE;
282 if (flag_unswitch_loops
283 && gimple_code (stmt) == GIMPLE_COND)
285 /* If we perform unswitching, force the operands of the invariant
286 condition to be moved out of the loop. */
287 return MOVE_POSSIBLE;
290 if (gimple_code (stmt) == GIMPLE_PHI
291 && gimple_phi_num_args (stmt) <= 2
292 && !virtual_operand_p (gimple_phi_result (stmt))
293 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
294 return MOVE_POSSIBLE;
296 if (gimple_get_lhs (stmt) == NULL_TREE)
297 return MOVE_IMPOSSIBLE;
299 if (gimple_vdef (stmt))
300 return MOVE_IMPOSSIBLE;
302 if (stmt_ends_bb_p (stmt)
303 || gimple_has_volatile_ops (stmt)
304 || gimple_has_side_effects (stmt)
305 || stmt_could_throw_p (stmt))
306 return MOVE_IMPOSSIBLE;
308 if (is_gimple_call (stmt))
310 /* While pure or const call is guaranteed to have no side effects, we
311 cannot move it arbitrarily. Consider code like
313 char *s = something ();
315 while (1)
317 if (s)
318 t = strlen (s);
319 else
320 t = 0;
323 Here the strlen call cannot be moved out of the loop, even though
324 s is invariant. In addition to possibly creating a call with
325 invalid arguments, moving out a function call that is not executed
326 may cause performance regressions in case the call is costly and
327 not executed at all. */
328 ret = MOVE_PRESERVE_EXECUTION;
329 lhs = gimple_call_lhs (stmt);
331 else if (is_gimple_assign (stmt))
332 lhs = gimple_assign_lhs (stmt);
333 else
334 return MOVE_IMPOSSIBLE;
336 if (TREE_CODE (lhs) == SSA_NAME
337 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
338 return MOVE_IMPOSSIBLE;
340 if (TREE_CODE (lhs) != SSA_NAME
341 || gimple_could_trap_p (stmt))
342 return MOVE_PRESERVE_EXECUTION;
344 /* Non local loads in a transaction cannot be hoisted out. Well,
345 unless the load happens on every path out of the loop, but we
346 don't take this into account yet. */
347 if (flag_tm
348 && gimple_in_transaction (stmt)
349 && gimple_assign_single_p (stmt))
351 tree rhs = gimple_assign_rhs1 (stmt);
352 if (DECL_P (rhs) && is_global_var (rhs))
354 if (dump_file)
356 fprintf (dump_file, "Cannot hoist conditional load of ");
357 print_generic_expr (dump_file, rhs, TDF_SLIM);
358 fprintf (dump_file, " because it is in a transaction.\n");
360 return MOVE_IMPOSSIBLE;
364 return ret;
367 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
368 loop to that we could move the expression using DEF if it did not have
369 other operands, i.e. the outermost loop enclosing LOOP in that the value
370 of DEF is invariant. */
372 static struct loop *
373 outermost_invariant_loop (tree def, struct loop *loop)
375 gimple *def_stmt;
376 basic_block def_bb;
377 struct loop *max_loop;
378 struct lim_aux_data *lim_data;
380 if (!def)
381 return superloop_at_depth (loop, 1);
383 if (TREE_CODE (def) != SSA_NAME)
385 gcc_assert (is_gimple_min_invariant (def));
386 return superloop_at_depth (loop, 1);
389 def_stmt = SSA_NAME_DEF_STMT (def);
390 def_bb = gimple_bb (def_stmt);
391 if (!def_bb)
392 return superloop_at_depth (loop, 1);
394 max_loop = find_common_loop (loop, def_bb->loop_father);
396 lim_data = get_lim_data (def_stmt);
397 if (lim_data != NULL && lim_data->max_loop != NULL)
398 max_loop = find_common_loop (max_loop,
399 loop_outer (lim_data->max_loop));
400 if (max_loop == loop)
401 return NULL;
402 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
404 return max_loop;
407 /* DATA is a structure containing information associated with a statement
408 inside LOOP. DEF is one of the operands of this statement.
410 Find the outermost loop enclosing LOOP in that value of DEF is invariant
411 and record this in DATA->max_loop field. If DEF itself is defined inside
412 this loop as well (i.e. we need to hoist it out of the loop if we want
413 to hoist the statement represented by DATA), record the statement in that
414 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
415 add the cost of the computation of DEF to the DATA->cost.
417 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
419 static bool
420 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
421 bool add_cost)
423 gimple *def_stmt = SSA_NAME_DEF_STMT (def);
424 basic_block def_bb = gimple_bb (def_stmt);
425 struct loop *max_loop;
426 struct lim_aux_data *def_data;
428 if (!def_bb)
429 return true;
431 max_loop = outermost_invariant_loop (def, loop);
432 if (!max_loop)
433 return false;
435 if (flow_loop_nested_p (data->max_loop, max_loop))
436 data->max_loop = max_loop;
438 def_data = get_lim_data (def_stmt);
439 if (!def_data)
440 return true;
442 if (add_cost
443 /* Only add the cost if the statement defining DEF is inside LOOP,
444 i.e. if it is likely that by moving the invariants dependent
445 on it, we will be able to avoid creating a new register for
446 it (since it will be only used in these dependent invariants). */
447 && def_bb->loop_father == loop)
448 data->cost += def_data->cost;
450 data->depends.safe_push (def_stmt);
452 return true;
455 /* Returns an estimate for a cost of statement STMT. The values here
456 are just ad-hoc constants, similar to costs for inlining. */
458 static unsigned
459 stmt_cost (gimple *stmt)
461 /* Always try to create possibilities for unswitching. */
462 if (gimple_code (stmt) == GIMPLE_COND
463 || gimple_code (stmt) == GIMPLE_PHI)
464 return LIM_EXPENSIVE;
466 /* We should be hoisting calls if possible. */
467 if (is_gimple_call (stmt))
469 tree fndecl;
471 /* Unless the call is a builtin_constant_p; this always folds to a
472 constant, so moving it is useless. */
473 fndecl = gimple_call_fndecl (stmt);
474 if (fndecl
475 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
476 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
477 return 0;
479 return LIM_EXPENSIVE;
482 /* Hoisting memory references out should almost surely be a win. */
483 if (gimple_references_memory_p (stmt))
484 return LIM_EXPENSIVE;
486 if (gimple_code (stmt) != GIMPLE_ASSIGN)
487 return 1;
489 switch (gimple_assign_rhs_code (stmt))
491 case MULT_EXPR:
492 case WIDEN_MULT_EXPR:
493 case WIDEN_MULT_PLUS_EXPR:
494 case WIDEN_MULT_MINUS_EXPR:
495 case DOT_PROD_EXPR:
496 case FMA_EXPR:
497 case TRUNC_DIV_EXPR:
498 case CEIL_DIV_EXPR:
499 case FLOOR_DIV_EXPR:
500 case ROUND_DIV_EXPR:
501 case EXACT_DIV_EXPR:
502 case CEIL_MOD_EXPR:
503 case FLOOR_MOD_EXPR:
504 case ROUND_MOD_EXPR:
505 case TRUNC_MOD_EXPR:
506 case RDIV_EXPR:
507 /* Division and multiplication are usually expensive. */
508 return LIM_EXPENSIVE;
510 case LSHIFT_EXPR:
511 case RSHIFT_EXPR:
512 case WIDEN_LSHIFT_EXPR:
513 case LROTATE_EXPR:
514 case RROTATE_EXPR:
515 /* Shifts and rotates are usually expensive. */
516 return LIM_EXPENSIVE;
518 case CONSTRUCTOR:
519 /* Make vector construction cost proportional to the number
520 of elements. */
521 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
523 case SSA_NAME:
524 case PAREN_EXPR:
525 /* Whether or not something is wrapped inside a PAREN_EXPR
526 should not change move cost. Nor should an intermediate
527 unpropagated SSA name copy. */
528 return 0;
530 default:
531 return 1;
535 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
536 REF is independent. If REF is not independent in LOOP, NULL is returned
537 instead. */
539 static struct loop *
540 outermost_indep_loop (struct loop *outer, struct loop *loop, im_mem_ref *ref)
542 struct loop *aloop;
544 if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
545 return NULL;
547 for (aloop = outer;
548 aloop != loop;
549 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
550 if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
551 && ref_indep_loop_p (aloop, ref))
552 return aloop;
554 if (ref_indep_loop_p (loop, ref))
555 return loop;
556 else
557 return NULL;
560 /* If there is a simple load or store to a memory reference in STMT, returns
561 the location of the memory reference, and sets IS_STORE according to whether
562 it is a store or load. Otherwise, returns NULL. */
564 static tree *
565 simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
567 tree *lhs, *rhs;
569 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
570 if (!gimple_assign_single_p (stmt))
571 return NULL;
573 lhs = gimple_assign_lhs_ptr (stmt);
574 rhs = gimple_assign_rhs1_ptr (stmt);
576 if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
578 *is_store = false;
579 return rhs;
581 else if (gimple_vdef (stmt)
582 && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
584 *is_store = true;
585 return lhs;
587 else
588 return NULL;
591 /* From a controlling predicate in DOM determine the arguments from
592 the PHI node PHI that are chosen if the predicate evaluates to
593 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
594 they are non-NULL. Returns true if the arguments can be determined,
595 else return false. */
597 static bool
598 extract_true_false_args_from_phi (basic_block dom, gphi *phi,
599 tree *true_arg_p, tree *false_arg_p)
601 edge te, fe;
602 if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
603 &te, &fe))
604 return false;
606 if (true_arg_p)
607 *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
608 if (false_arg_p)
609 *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
611 return true;
614 /* Determine the outermost loop to that it is possible to hoist a statement
615 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
616 the outermost loop in that the value computed by STMT is invariant.
617 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
618 we preserve the fact whether STMT is executed. It also fills other related
619 information to LIM_DATA (STMT).
621 The function returns false if STMT cannot be hoisted outside of the loop it
622 is defined in, and true otherwise. */
624 static bool
625 determine_max_movement (gimple *stmt, bool must_preserve_exec)
627 basic_block bb = gimple_bb (stmt);
628 struct loop *loop = bb->loop_father;
629 struct loop *level;
630 struct lim_aux_data *lim_data = get_lim_data (stmt);
631 tree val;
632 ssa_op_iter iter;
634 if (must_preserve_exec)
635 level = ALWAYS_EXECUTED_IN (bb);
636 else
637 level = superloop_at_depth (loop, 1);
638 lim_data->max_loop = level;
640 if (gphi *phi = dyn_cast <gphi *> (stmt))
642 use_operand_p use_p;
643 unsigned min_cost = UINT_MAX;
644 unsigned total_cost = 0;
645 struct lim_aux_data *def_data;
647 /* We will end up promoting dependencies to be unconditionally
648 evaluated. For this reason the PHI cost (and thus the
649 cost we remove from the loop by doing the invariant motion)
650 is that of the cheapest PHI argument dependency chain. */
651 FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
653 val = USE_FROM_PTR (use_p);
655 if (TREE_CODE (val) != SSA_NAME)
657 /* Assign const 1 to constants. */
658 min_cost = MIN (min_cost, 1);
659 total_cost += 1;
660 continue;
662 if (!add_dependency (val, lim_data, loop, false))
663 return false;
665 gimple *def_stmt = SSA_NAME_DEF_STMT (val);
666 if (gimple_bb (def_stmt)
667 && gimple_bb (def_stmt)->loop_father == loop)
669 def_data = get_lim_data (def_stmt);
670 if (def_data)
672 min_cost = MIN (min_cost, def_data->cost);
673 total_cost += def_data->cost;
678 min_cost = MIN (min_cost, total_cost);
679 lim_data->cost += min_cost;
681 if (gimple_phi_num_args (phi) > 1)
683 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
684 gimple *cond;
685 if (gsi_end_p (gsi_last_bb (dom)))
686 return false;
687 cond = gsi_stmt (gsi_last_bb (dom));
688 if (gimple_code (cond) != GIMPLE_COND)
689 return false;
690 /* Verify that this is an extended form of a diamond and
691 the PHI arguments are completely controlled by the
692 predicate in DOM. */
693 if (!extract_true_false_args_from_phi (dom, phi, NULL, NULL))
694 return false;
696 /* Fold in dependencies and cost of the condition. */
697 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
699 if (!add_dependency (val, lim_data, loop, false))
700 return false;
701 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
702 if (def_data)
703 lim_data->cost += def_data->cost;
706 /* We want to avoid unconditionally executing very expensive
707 operations. As costs for our dependencies cannot be
708 negative just claim we are not invariand for this case.
709 We also are not sure whether the control-flow inside the
710 loop will vanish. */
711 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
712 && !(min_cost != 0
713 && total_cost / min_cost <= 2))
714 return false;
716 /* Assume that the control-flow in the loop will vanish.
717 ??? We should verify this and not artificially increase
718 the cost if that is not the case. */
719 lim_data->cost += stmt_cost (stmt);
722 return true;
724 else
725 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
726 if (!add_dependency (val, lim_data, loop, true))
727 return false;
729 if (gimple_vuse (stmt))
731 im_mem_ref *ref
732 = lim_data ? memory_accesses.refs_list[lim_data->ref] : NULL;
733 if (ref
734 && MEM_ANALYZABLE (ref))
736 lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
737 loop, ref);
738 if (!lim_data->max_loop)
739 return false;
741 else if (! add_dependency (gimple_vuse (stmt), lim_data, loop, false))
742 return false;
745 lim_data->cost += stmt_cost (stmt);
747 return true;
750 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
751 and that one of the operands of this statement is computed by STMT.
752 Ensure that STMT (together with all the statements that define its
753 operands) is hoisted at least out of the loop LEVEL. */
755 static void
756 set_level (gimple *stmt, struct loop *orig_loop, struct loop *level)
758 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
759 struct lim_aux_data *lim_data;
760 gimple *dep_stmt;
761 unsigned i;
763 stmt_loop = find_common_loop (orig_loop, stmt_loop);
764 lim_data = get_lim_data (stmt);
765 if (lim_data != NULL && lim_data->tgt_loop != NULL)
766 stmt_loop = find_common_loop (stmt_loop,
767 loop_outer (lim_data->tgt_loop));
768 if (flow_loop_nested_p (stmt_loop, level))
769 return;
771 gcc_assert (level == lim_data->max_loop
772 || flow_loop_nested_p (lim_data->max_loop, level));
774 lim_data->tgt_loop = level;
775 FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
776 set_level (dep_stmt, orig_loop, level);
779 /* Determines an outermost loop from that we want to hoist the statement STMT.
780 For now we chose the outermost possible loop. TODO -- use profiling
781 information to set it more sanely. */
783 static void
784 set_profitable_level (gimple *stmt)
786 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
789 /* Returns true if STMT is a call that has side effects. */
791 static bool
792 nonpure_call_p (gimple *stmt)
794 if (gimple_code (stmt) != GIMPLE_CALL)
795 return false;
797 return gimple_has_side_effects (stmt);
800 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
802 static gimple *
803 rewrite_reciprocal (gimple_stmt_iterator *bsi)
805 gassign *stmt, *stmt1, *stmt2;
806 tree name, lhs, type;
807 tree real_one;
808 gimple_stmt_iterator gsi;
810 stmt = as_a <gassign *> (gsi_stmt (*bsi));
811 lhs = gimple_assign_lhs (stmt);
812 type = TREE_TYPE (lhs);
814 real_one = build_one_cst (type);
816 name = make_temp_ssa_name (type, NULL, "reciptmp");
817 stmt1 = gimple_build_assign (name, RDIV_EXPR, real_one,
818 gimple_assign_rhs2 (stmt));
819 stmt2 = gimple_build_assign (lhs, MULT_EXPR, name,
820 gimple_assign_rhs1 (stmt));
822 /* Replace division stmt with reciprocal and multiply stmts.
823 The multiply stmt is not invariant, so update iterator
824 and avoid rescanning. */
825 gsi = *bsi;
826 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
827 gsi_replace (&gsi, stmt2, true);
829 /* Continue processing with invariant reciprocal statement. */
830 return stmt1;
833 /* Check if the pattern at *BSI is a bittest of the form
834 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
836 static gimple *
837 rewrite_bittest (gimple_stmt_iterator *bsi)
839 gassign *stmt;
840 gimple *stmt1;
841 gassign *stmt2;
842 gimple *use_stmt;
843 gcond *cond_stmt;
844 tree lhs, name, t, a, b;
845 use_operand_p use;
847 stmt = as_a <gassign *> (gsi_stmt (*bsi));
848 lhs = gimple_assign_lhs (stmt);
850 /* Verify that the single use of lhs is a comparison against zero. */
851 if (TREE_CODE (lhs) != SSA_NAME
852 || !single_imm_use (lhs, &use, &use_stmt))
853 return stmt;
854 cond_stmt = dyn_cast <gcond *> (use_stmt);
855 if (!cond_stmt)
856 return stmt;
857 if (gimple_cond_lhs (cond_stmt) != lhs
858 || (gimple_cond_code (cond_stmt) != NE_EXPR
859 && gimple_cond_code (cond_stmt) != EQ_EXPR)
860 || !integer_zerop (gimple_cond_rhs (cond_stmt)))
861 return stmt;
863 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
864 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
865 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
866 return stmt;
868 /* There is a conversion in between possibly inserted by fold. */
869 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
871 t = gimple_assign_rhs1 (stmt1);
872 if (TREE_CODE (t) != SSA_NAME
873 || !has_single_use (t))
874 return stmt;
875 stmt1 = SSA_NAME_DEF_STMT (t);
876 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
877 return stmt;
880 /* Verify that B is loop invariant but A is not. Verify that with
881 all the stmt walking we are still in the same loop. */
882 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
883 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
884 return stmt;
886 a = gimple_assign_rhs1 (stmt1);
887 b = gimple_assign_rhs2 (stmt1);
889 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
890 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
892 gimple_stmt_iterator rsi;
894 /* 1 << B */
895 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
896 build_int_cst (TREE_TYPE (a), 1), b);
897 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
898 stmt1 = gimple_build_assign (name, t);
900 /* A & (1 << B) */
901 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
902 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
903 stmt2 = gimple_build_assign (name, t);
905 /* Replace the SSA_NAME we compare against zero. Adjust
906 the type of zero accordingly. */
907 SET_USE (use, name);
908 gimple_cond_set_rhs (cond_stmt,
909 build_int_cst_type (TREE_TYPE (name),
910 0));
912 /* Don't use gsi_replace here, none of the new assignments sets
913 the variable originally set in stmt. Move bsi to stmt1, and
914 then remove the original stmt, so that we get a chance to
915 retain debug info for it. */
916 rsi = *bsi;
917 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
918 gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
919 gimple *to_release = gsi_stmt (rsi);
920 gsi_remove (&rsi, true);
921 release_defs (to_release);
923 return stmt1;
926 return stmt;
929 /* For each statement determines the outermost loop in that it is invariant,
930 - statements on whose motion it depends and the cost of the computation.
931 - This information is stored to the LIM_DATA structure associated with
932 - each statement. */
933 class invariantness_dom_walker : public dom_walker
935 public:
936 invariantness_dom_walker (cdi_direction direction)
937 : dom_walker (direction) {}
939 virtual edge before_dom_children (basic_block);
942 /* Determine the outermost loops in that statements in basic block BB are
943 invariant, and record them to the LIM_DATA associated with the statements.
944 Callback for dom_walker. */
946 edge
947 invariantness_dom_walker::before_dom_children (basic_block bb)
949 enum move_pos pos;
950 gimple_stmt_iterator bsi;
951 gimple *stmt;
952 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
953 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
954 struct lim_aux_data *lim_data;
956 if (!loop_outer (bb->loop_father))
957 return NULL;
959 if (dump_file && (dump_flags & TDF_DETAILS))
960 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
961 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
963 /* Look at PHI nodes, but only if there is at most two.
964 ??? We could relax this further by post-processing the inserted
965 code and transforming adjacent cond-exprs with the same predicate
966 to control flow again. */
967 bsi = gsi_start_phis (bb);
968 if (!gsi_end_p (bsi)
969 && ((gsi_next (&bsi), gsi_end_p (bsi))
970 || (gsi_next (&bsi), gsi_end_p (bsi))))
971 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
973 stmt = gsi_stmt (bsi);
975 pos = movement_possibility (stmt);
976 if (pos == MOVE_IMPOSSIBLE)
977 continue;
979 lim_data = get_lim_data (stmt);
980 if (! lim_data)
981 lim_data = init_lim_data (stmt);
982 lim_data->always_executed_in = outermost;
984 if (!determine_max_movement (stmt, false))
986 lim_data->max_loop = NULL;
987 continue;
990 if (dump_file && (dump_flags & TDF_DETAILS))
992 print_gimple_stmt (dump_file, stmt, 2);
993 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
994 loop_depth (lim_data->max_loop),
995 lim_data->cost);
998 if (lim_data->cost >= LIM_EXPENSIVE)
999 set_profitable_level (stmt);
1002 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1004 stmt = gsi_stmt (bsi);
1006 pos = movement_possibility (stmt);
1007 if (pos == MOVE_IMPOSSIBLE)
1009 if (nonpure_call_p (stmt))
1011 maybe_never = true;
1012 outermost = NULL;
1014 /* Make sure to note always_executed_in for stores to make
1015 store-motion work. */
1016 else if (stmt_makes_single_store (stmt))
1018 struct lim_aux_data *lim_data = get_lim_data (stmt);
1019 if (! lim_data)
1020 lim_data = init_lim_data (stmt);
1021 lim_data->always_executed_in = outermost;
1023 continue;
1026 if (is_gimple_assign (stmt)
1027 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1028 == GIMPLE_BINARY_RHS))
1030 tree op0 = gimple_assign_rhs1 (stmt);
1031 tree op1 = gimple_assign_rhs2 (stmt);
1032 struct loop *ol1 = outermost_invariant_loop (op1,
1033 loop_containing_stmt (stmt));
1035 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1036 to be hoisted out of loop, saving expensive divide. */
1037 if (pos == MOVE_POSSIBLE
1038 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
1039 && flag_unsafe_math_optimizations
1040 && !flag_trapping_math
1041 && ol1 != NULL
1042 && outermost_invariant_loop (op0, ol1) == NULL)
1043 stmt = rewrite_reciprocal (&bsi);
1045 /* If the shift count is invariant, convert (A >> B) & 1 to
1046 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1047 saving an expensive shift. */
1048 if (pos == MOVE_POSSIBLE
1049 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
1050 && integer_onep (op1)
1051 && TREE_CODE (op0) == SSA_NAME
1052 && has_single_use (op0))
1053 stmt = rewrite_bittest (&bsi);
1056 lim_data = get_lim_data (stmt);
1057 if (! lim_data)
1058 lim_data = init_lim_data (stmt);
1059 lim_data->always_executed_in = outermost;
1061 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1062 continue;
1064 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1066 lim_data->max_loop = NULL;
1067 continue;
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1072 print_gimple_stmt (dump_file, stmt, 2);
1073 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1074 loop_depth (lim_data->max_loop),
1075 lim_data->cost);
1078 if (lim_data->cost >= LIM_EXPENSIVE)
1079 set_profitable_level (stmt);
1081 return NULL;
1084 class move_computations_dom_walker : public dom_walker
1086 public:
1087 move_computations_dom_walker (cdi_direction direction)
1088 : dom_walker (direction), todo_ (0) {}
1090 virtual edge before_dom_children (basic_block);
1092 unsigned int todo_;
1095 /* Hoist the statements in basic block BB out of the loops prescribed by
1096 data stored in LIM_DATA structures associated with each statement. Callback
1097 for walk_dominator_tree. */
1099 unsigned int
1100 move_computations_worker (basic_block bb)
1102 struct loop *level;
1103 unsigned cost = 0;
1104 struct lim_aux_data *lim_data;
1105 unsigned int todo = 0;
1107 if (!loop_outer (bb->loop_father))
1108 return todo;
1110 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1112 gassign *new_stmt;
1113 gphi *stmt = bsi.phi ();
1115 lim_data = get_lim_data (stmt);
1116 if (lim_data == NULL)
1118 gsi_next (&bsi);
1119 continue;
1122 cost = lim_data->cost;
1123 level = lim_data->tgt_loop;
1124 clear_lim_data (stmt);
1126 if (!level)
1128 gsi_next (&bsi);
1129 continue;
1132 if (dump_file && (dump_flags & TDF_DETAILS))
1134 fprintf (dump_file, "Moving PHI node\n");
1135 print_gimple_stmt (dump_file, stmt, 0);
1136 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1137 cost, level->num);
1140 if (gimple_phi_num_args (stmt) == 1)
1142 tree arg = PHI_ARG_DEF (stmt, 0);
1143 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
1144 TREE_CODE (arg), arg);
1146 else
1148 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
1149 gimple *cond = gsi_stmt (gsi_last_bb (dom));
1150 tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
1151 /* Get the PHI arguments corresponding to the true and false
1152 edges of COND. */
1153 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
1154 gcc_assert (arg0 && arg1);
1155 t = build2 (gimple_cond_code (cond), boolean_type_node,
1156 gimple_cond_lhs (cond), gimple_cond_rhs (cond));
1157 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
1158 COND_EXPR, t, arg0, arg1);
1159 todo |= TODO_cleanup_cfg;
1161 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt)))
1162 && (!ALWAYS_EXECUTED_IN (bb)
1163 || (ALWAYS_EXECUTED_IN (bb) != level
1164 && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1166 tree lhs = gimple_assign_lhs (new_stmt);
1167 SSA_NAME_RANGE_INFO (lhs) = NULL;
1169 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1170 remove_phi_node (&bsi, false);
1173 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1175 edge e;
1177 gimple *stmt = gsi_stmt (bsi);
1179 lim_data = get_lim_data (stmt);
1180 if (lim_data == NULL)
1182 gsi_next (&bsi);
1183 continue;
1186 cost = lim_data->cost;
1187 level = lim_data->tgt_loop;
1188 clear_lim_data (stmt);
1190 if (!level)
1192 gsi_next (&bsi);
1193 continue;
1196 /* We do not really want to move conditionals out of the loop; we just
1197 placed it here to force its operands to be moved if necessary. */
1198 if (gimple_code (stmt) == GIMPLE_COND)
1199 continue;
1201 if (dump_file && (dump_flags & TDF_DETAILS))
1203 fprintf (dump_file, "Moving statement\n");
1204 print_gimple_stmt (dump_file, stmt, 0);
1205 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1206 cost, level->num);
1209 e = loop_preheader_edge (level);
1210 gcc_assert (!gimple_vdef (stmt));
1211 if (gimple_vuse (stmt))
1213 /* The new VUSE is the one from the virtual PHI in the loop
1214 header or the one already present. */
1215 gphi_iterator gsi2;
1216 for (gsi2 = gsi_start_phis (e->dest);
1217 !gsi_end_p (gsi2); gsi_next (&gsi2))
1219 gphi *phi = gsi2.phi ();
1220 if (virtual_operand_p (gimple_phi_result (phi)))
1222 gimple_set_vuse (stmt, PHI_ARG_DEF_FROM_EDGE (phi, e));
1223 break;
1227 gsi_remove (&bsi, false);
1228 if (gimple_has_lhs (stmt)
1229 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
1230 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt)))
1231 && (!ALWAYS_EXECUTED_IN (bb)
1232 || !(ALWAYS_EXECUTED_IN (bb) == level
1233 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1235 tree lhs = gimple_get_lhs (stmt);
1236 SSA_NAME_RANGE_INFO (lhs) = NULL;
1238 /* In case this is a stmt that is not unconditionally executed
1239 when the target loop header is executed and the stmt may
1240 invoke undefined integer or pointer overflow rewrite it to
1241 unsigned arithmetic. */
1242 if (is_gimple_assign (stmt)
1243 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
1244 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
1245 && arith_code_with_undefined_signed_overflow
1246 (gimple_assign_rhs_code (stmt))
1247 && (!ALWAYS_EXECUTED_IN (bb)
1248 || !(ALWAYS_EXECUTED_IN (bb) == level
1249 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1250 gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
1251 else
1252 gsi_insert_on_edge (e, stmt);
1255 return todo;
1258 /* Hoist the statements out of the loops prescribed by data stored in
1259 LIM_DATA structures associated with each statement.*/
1261 static unsigned int
1262 move_computations (void)
1264 int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
1265 int n = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, false);
1266 unsigned todo = 0;
1268 for (int i = 0; i < n; ++i)
1269 todo |= move_computations_worker (BASIC_BLOCK_FOR_FN (cfun, rpo[i]));
1271 free (rpo);
1273 gsi_commit_edge_inserts ();
1274 if (need_ssa_update_p (cfun))
1275 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1277 return todo;
1280 /* Checks whether the statement defining variable *INDEX can be hoisted
1281 out of the loop passed in DATA. Callback for for_each_index. */
1283 static bool
1284 may_move_till (tree ref, tree *index, void *data)
1286 struct loop *loop = (struct loop *) data, *max_loop;
1288 /* If REF is an array reference, check also that the step and the lower
1289 bound is invariant in LOOP. */
1290 if (TREE_CODE (ref) == ARRAY_REF)
1292 tree step = TREE_OPERAND (ref, 3);
1293 tree lbound = TREE_OPERAND (ref, 2);
1295 max_loop = outermost_invariant_loop (step, loop);
1296 if (!max_loop)
1297 return false;
1299 max_loop = outermost_invariant_loop (lbound, loop);
1300 if (!max_loop)
1301 return false;
1304 max_loop = outermost_invariant_loop (*index, loop);
1305 if (!max_loop)
1306 return false;
1308 return true;
1311 /* If OP is SSA NAME, force the statement that defines it to be
1312 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1314 static void
1315 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1317 gimple *stmt;
1319 if (!op
1320 || is_gimple_min_invariant (op))
1321 return;
1323 gcc_assert (TREE_CODE (op) == SSA_NAME);
1325 stmt = SSA_NAME_DEF_STMT (op);
1326 if (gimple_nop_p (stmt))
1327 return;
1329 set_level (stmt, orig_loop, loop);
1332 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1333 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1334 for_each_index. */
1336 struct fmt_data
1338 struct loop *loop;
1339 struct loop *orig_loop;
1342 static bool
1343 force_move_till (tree ref, tree *index, void *data)
1345 struct fmt_data *fmt_data = (struct fmt_data *) data;
1347 if (TREE_CODE (ref) == ARRAY_REF)
1349 tree step = TREE_OPERAND (ref, 3);
1350 tree lbound = TREE_OPERAND (ref, 2);
1352 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1353 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1356 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1358 return true;
1361 /* A function to free the mem_ref object OBJ. */
1363 static void
1364 memref_free (struct im_mem_ref *mem)
1366 mem->accesses_in_loop.release ();
1369 /* Allocates and returns a memory reference description for MEM whose hash
1370 value is HASH and id is ID. */
1372 static im_mem_ref *
1373 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1375 im_mem_ref *ref = XOBNEW (&mem_ref_obstack, struct im_mem_ref);
1376 ao_ref_init (&ref->mem, mem);
1377 ref->id = id;
1378 ref->hash = hash;
1379 ref->stored = NULL;
1380 bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
1381 bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
1382 ref->accesses_in_loop.create (1);
1384 return ref;
1387 /* Records memory reference location *LOC in LOOP to the memory reference
1388 description REF. The reference occurs in statement STMT. */
1390 static void
1391 record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
1393 mem_ref_loc aref;
1394 aref.stmt = stmt;
1395 aref.ref = loc;
1396 ref->accesses_in_loop.safe_push (aref);
1399 /* Set the LOOP bit in REF stored bitmap and allocate that if
1400 necessary. Return whether a bit was changed. */
1402 static bool
1403 set_ref_stored_in_loop (im_mem_ref *ref, struct loop *loop)
1405 if (!ref->stored)
1406 ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
1407 return bitmap_set_bit (ref->stored, loop->num);
1410 /* Marks reference REF as stored in LOOP. */
1412 static void
1413 mark_ref_stored (im_mem_ref *ref, struct loop *loop)
1415 while (loop != current_loops->tree_root
1416 && set_ref_stored_in_loop (ref, loop))
1417 loop = loop_outer (loop);
1420 /* Gathers memory references in statement STMT in LOOP, storing the
1421 information about them in the memory_accesses structure. Marks
1422 the vops accessed through unrecognized statements there as
1423 well. */
1425 static void
1426 gather_mem_refs_stmt (struct loop *loop, gimple *stmt)
1428 tree *mem = NULL;
1429 hashval_t hash;
1430 im_mem_ref **slot;
1431 im_mem_ref *ref;
1432 bool is_stored;
1433 unsigned id;
1435 if (!gimple_vuse (stmt))
1436 return;
1438 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1439 if (!mem)
1441 /* We use the shared mem_ref for all unanalyzable refs. */
1442 id = UNANALYZABLE_MEM_ID;
1443 ref = memory_accesses.refs_list[id];
1444 if (dump_file && (dump_flags & TDF_DETAILS))
1446 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
1447 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1449 is_stored = gimple_vdef (stmt);
1451 else
1453 hash = iterative_hash_expr (*mem, 0);
1454 slot = memory_accesses.refs->find_slot_with_hash (*mem, hash, INSERT);
1455 if (*slot)
1457 ref = *slot;
1458 id = ref->id;
1460 else
1462 id = memory_accesses.refs_list.length ();
1463 ref = mem_ref_alloc (*mem, hash, id);
1464 memory_accesses.refs_list.safe_push (ref);
1465 *slot = ref;
1467 if (dump_file && (dump_flags & TDF_DETAILS))
1469 fprintf (dump_file, "Memory reference %u: ", id);
1470 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
1471 fprintf (dump_file, "\n");
1475 record_mem_ref_loc (ref, stmt, mem);
1477 bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
1478 if (is_stored)
1480 bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
1481 mark_ref_stored (ref, loop);
1483 init_lim_data (stmt)->ref = ref->id;
1484 return;
1487 static unsigned *bb_loop_postorder;
1489 /* qsort sort function to sort blocks after their loop fathers postorder. */
1491 static int
1492 sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
1494 basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
1495 basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
1496 struct loop *loop1 = bb1->loop_father;
1497 struct loop *loop2 = bb2->loop_father;
1498 if (loop1->num == loop2->num)
1499 return 0;
1500 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1503 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1505 static int
1506 sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
1508 mem_ref_loc *loc1 = (mem_ref_loc *)const_cast<void *>(loc1_);
1509 mem_ref_loc *loc2 = (mem_ref_loc *)const_cast<void *>(loc2_);
1510 struct loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
1511 struct loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
1512 if (loop1->num == loop2->num)
1513 return 0;
1514 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1517 /* Gathers memory references in loops. */
1519 static void
1520 analyze_memory_references (void)
1522 gimple_stmt_iterator bsi;
1523 basic_block bb, *bbs;
1524 struct loop *loop, *outer;
1525 unsigned i, n;
1527 /* Collect all basic-blocks in loops and sort them after their
1528 loops postorder. */
1529 i = 0;
1530 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
1531 FOR_EACH_BB_FN (bb, cfun)
1532 if (bb->loop_father != current_loops->tree_root)
1533 bbs[i++] = bb;
1534 n = i;
1535 qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
1537 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1538 That results in better locality for all the bitmaps. */
1539 for (i = 0; i < n; ++i)
1541 basic_block bb = bbs[i];
1542 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1543 gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
1546 /* Sort the location list of gathered memory references after their
1547 loop postorder number. */
1548 im_mem_ref *ref;
1549 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
1550 ref->accesses_in_loop.qsort (sort_locs_in_loop_postorder_cmp);
1552 free (bbs);
1553 // free (bb_loop_postorder);
1555 /* Propagate the information about accessed memory references up
1556 the loop hierarchy. */
1557 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1559 /* Finalize the overall touched references (including subloops). */
1560 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
1561 &memory_accesses.refs_stored_in_loop[loop->num]);
1563 /* Propagate the information about accessed memory references up
1564 the loop hierarchy. */
1565 outer = loop_outer (loop);
1566 if (outer == current_loops->tree_root)
1567 continue;
1569 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
1570 &memory_accesses.all_refs_stored_in_loop[loop->num]);
1574 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1575 tree_to_aff_combination_expand. */
1577 static bool
1578 mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
1579 hash_map<tree, name_expansion *> **ttae_cache)
1581 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1582 object and their offset differ in such a way that the locations cannot
1583 overlap, then they cannot alias. */
1584 poly_widest_int size1, size2;
1585 aff_tree off1, off2;
1587 /* Perform basic offset and type-based disambiguation. */
1588 if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
1589 return false;
1591 /* The expansion of addresses may be a bit expensive, thus we only do
1592 the check at -O2 and higher optimization levels. */
1593 if (optimize < 2)
1594 return true;
1596 get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
1597 get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
1598 aff_combination_expand (&off1, ttae_cache);
1599 aff_combination_expand (&off2, ttae_cache);
1600 aff_combination_scale (&off1, -1);
1601 aff_combination_add (&off2, &off1);
1603 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1604 return false;
1606 return true;
1609 /* Compare function for bsearch searching for reference locations
1610 in a loop. */
1612 static int
1613 find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
1615 struct loop *loop = (struct loop *)const_cast<void *>(loop_);
1616 mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
1617 struct loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
1618 if (loop->num == loc_loop->num
1619 || flow_loop_nested_p (loop, loc_loop))
1620 return 0;
1621 return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
1622 ? -1 : 1);
1625 /* Iterates over all locations of REF in LOOP and its subloops calling
1626 fn.operator() with the location as argument. When that operator
1627 returns true the iteration is stopped and true is returned.
1628 Otherwise false is returned. */
1630 template <typename FN>
1631 static bool
1632 for_all_locs_in_loop (struct loop *loop, im_mem_ref *ref, FN fn)
1634 unsigned i;
1635 mem_ref_loc *loc;
1637 /* Search for the cluster of locs in the accesses_in_loop vector
1638 which is sorted after postorder index of the loop father. */
1639 loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp);
1640 if (!loc)
1641 return false;
1643 /* We have found one location inside loop or its sub-loops. Iterate
1644 both forward and backward to cover the whole cluster. */
1645 i = loc - ref->accesses_in_loop.address ();
1646 while (i > 0)
1648 --i;
1649 mem_ref_loc *l = &ref->accesses_in_loop[i];
1650 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1651 break;
1652 if (fn (l))
1653 return true;
1655 for (i = loc - ref->accesses_in_loop.address ();
1656 i < ref->accesses_in_loop.length (); ++i)
1658 mem_ref_loc *l = &ref->accesses_in_loop[i];
1659 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1660 break;
1661 if (fn (l))
1662 return true;
1665 return false;
1668 /* Rewrites location LOC by TMP_VAR. */
1670 struct rewrite_mem_ref_loc
1672 rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
1673 bool operator () (mem_ref_loc *loc);
1674 tree tmp_var;
1677 bool
1678 rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
1680 *loc->ref = tmp_var;
1681 update_stmt (loc->stmt);
1682 return false;
1685 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1687 static void
1688 rewrite_mem_refs (struct loop *loop, im_mem_ref *ref, tree tmp_var)
1690 for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1693 /* Stores the first reference location in LOCP. */
1695 struct first_mem_ref_loc_1
1697 first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
1698 bool operator () (mem_ref_loc *loc);
1699 mem_ref_loc **locp;
1702 bool
1703 first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
1705 *locp = loc;
1706 return true;
1709 /* Returns the first reference location to REF in LOOP. */
1711 static mem_ref_loc *
1712 first_mem_ref_loc (struct loop *loop, im_mem_ref *ref)
1714 mem_ref_loc *locp = NULL;
1715 for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
1716 return locp;
1719 struct prev_flag_edges {
1720 /* Edge to insert new flag comparison code. */
1721 edge append_cond_position;
1723 /* Edge for fall through from previous flag comparison. */
1724 edge last_cond_fallthru;
1727 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1728 MEM along edge EX.
1730 The store is only done if MEM has changed. We do this so no
1731 changes to MEM occur on code paths that did not originally store
1732 into it.
1734 The common case for execute_sm will transform:
1736 for (...) {
1737 if (foo)
1738 stuff;
1739 else
1740 MEM = TMP_VAR;
1743 into:
1745 lsm = MEM;
1746 for (...) {
1747 if (foo)
1748 stuff;
1749 else
1750 lsm = TMP_VAR;
1752 MEM = lsm;
1754 This function will generate:
1756 lsm = MEM;
1758 lsm_flag = false;
1760 for (...) {
1761 if (foo)
1762 stuff;
1763 else {
1764 lsm = TMP_VAR;
1765 lsm_flag = true;
1768 if (lsm_flag) <--
1769 MEM = lsm; <--
1772 static void
1773 execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag,
1774 edge preheader, hash_set <basic_block> *flag_bbs)
1776 basic_block new_bb, then_bb, old_dest;
1777 bool loop_has_only_one_exit;
1778 edge then_old_edge, orig_ex = ex;
1779 gimple_stmt_iterator gsi;
1780 gimple *stmt;
1781 struct prev_flag_edges *prev_edges = (struct prev_flag_edges *) ex->aux;
1782 bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;
1784 profile_count count_sum = profile_count::zero ();
1785 int nbbs = 0, ncount = 0;
1786 profile_probability flag_probability = profile_probability::uninitialized ();
1788 /* Flag is set in FLAG_BBS. Determine probability that flag will be true
1789 at loop exit.
1791 This code may look fancy, but it can not update profile very realistically
1792 because we do not know the probability that flag will be true at given
1793 loop exit.
1795 We look for two interesting extremes
1796 - when exit is dominated by block setting the flag, we know it will
1797 always be true. This is a common case.
1798 - when all blocks setting the flag have very low frequency we know
1799 it will likely be false.
1800 In all other cases we default to 2/3 for flag being true. */
1802 for (hash_set<basic_block>::iterator it = flag_bbs->begin ();
1803 it != flag_bbs->end (); ++it)
1805 if ((*it)->count.initialized_p ())
1806 count_sum += (*it)->count, ncount ++;
1807 if (dominated_by_p (CDI_DOMINATORS, ex->src, *it))
1808 flag_probability = profile_probability::always ();
1809 nbbs++;
1812 profile_probability cap = profile_probability::always ().apply_scale (2, 3);
1814 if (flag_probability.initialized_p ())
1816 else if (ncount == nbbs
1817 && preheader->count () >= count_sum && preheader->count ().nonzero_p ())
1819 flag_probability = count_sum.probability_in (preheader->count ());
1820 if (flag_probability > cap)
1821 flag_probability = cap;
1824 if (!flag_probability.initialized_p ())
1825 flag_probability = cap;
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);
1836 else
1838 for (gphi_iterator gpi = gsi_start_phis (ex->dest);
1839 !gsi_end_p (gpi); gsi_next (&gpi))
1841 gphi *phi = gpi.phi ();
1842 if (virtual_operand_p (gimple_phi_result (phi)))
1843 continue;
1845 /* When the destination has a non-virtual PHI node with multiple
1846 predecessors make sure we preserve the PHI structure by
1847 forcing a forwarder block so that hoisting of that PHI will
1848 still work. */
1849 split_edge (ex);
1850 break;
1854 old_dest = ex->dest;
1855 new_bb = split_edge (ex);
1856 then_bb = create_empty_bb (new_bb);
1857 then_bb->count = new_bb->count.apply_probability (flag_probability);
1858 if (irr)
1859 then_bb->flags = BB_IRREDUCIBLE_LOOP;
1860 add_bb_to_loop (then_bb, new_bb->loop_father);
1862 gsi = gsi_start_bb (new_bb);
1863 stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
1864 NULL_TREE, NULL_TREE);
1865 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1867 gsi = gsi_start_bb (then_bb);
1868 /* Insert actual store. */
1869 stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
1870 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1872 edge e1 = single_succ_edge (new_bb);
1873 edge e2 = make_edge (new_bb, then_bb,
1874 EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1875 e2->probability = flag_probability;
1877 e1->flags |= EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0);
1878 e1->flags &= ~EDGE_FALLTHRU;
1880 e1->probability = flag_probability.invert ();
1882 then_old_edge = make_single_succ_edge (then_bb, old_dest,
1883 EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1885 set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
1887 if (prev_edges)
1889 basic_block prevbb = prev_edges->last_cond_fallthru->src;
1890 redirect_edge_succ (prev_edges->last_cond_fallthru, new_bb);
1891 set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
1892 set_immediate_dominator (CDI_DOMINATORS, old_dest,
1893 recompute_dominator (CDI_DOMINATORS, old_dest));
1896 /* ?? Because stores may alias, they must happen in the exact
1897 sequence they originally happened. Save the position right after
1898 the (_lsm) store we just created so we can continue appending after
1899 it and maintain the original order. */
1901 struct prev_flag_edges *p;
1903 if (orig_ex->aux)
1904 orig_ex->aux = NULL;
1905 alloc_aux_for_edge (orig_ex, sizeof (struct prev_flag_edges));
1906 p = (struct prev_flag_edges *) orig_ex->aux;
1907 p->append_cond_position = then_old_edge;
1908 p->last_cond_fallthru = find_edge (new_bb, old_dest);
1909 orig_ex->aux = (void *) p;
1912 if (!loop_has_only_one_exit)
1913 for (gphi_iterator gpi = gsi_start_phis (old_dest);
1914 !gsi_end_p (gpi); gsi_next (&gpi))
1916 gphi *phi = gpi.phi ();
1917 unsigned i;
1919 for (i = 0; i < gimple_phi_num_args (phi); i++)
1920 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
1922 tree arg = gimple_phi_arg_def (phi, i);
1923 add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
1924 update_stmt (phi);
1929 /* When REF is set on the location, set flag indicating the store. */
1931 struct sm_set_flag_if_changed
1933 sm_set_flag_if_changed (tree flag_, hash_set <basic_block> *bbs_)
1934 : flag (flag_), bbs (bbs_) {}
1935 bool operator () (mem_ref_loc *loc);
1936 tree flag;
1937 hash_set <basic_block> *bbs;
1940 bool
1941 sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
1943 /* Only set the flag for writes. */
1944 if (is_gimple_assign (loc->stmt)
1945 && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
1947 gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
1948 gimple *stmt = gimple_build_assign (flag, boolean_true_node);
1949 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1950 bbs->add (gimple_bb (stmt));
1952 return false;
1955 /* Helper function for execute_sm. On every location where REF is
1956 set, set an appropriate flag indicating the store. */
1958 static tree
1959 execute_sm_if_changed_flag_set (struct loop *loop, im_mem_ref *ref,
1960 hash_set <basic_block> *bbs)
1962 tree flag;
1963 char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
1964 flag = create_tmp_reg (boolean_type_node, str);
1965 for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag, bbs));
1966 return flag;
1969 /* Executes store motion of memory reference REF from LOOP.
1970 Exits from the LOOP are stored in EXITS. The initialization of the
1971 temporary variable is put to the preheader of the loop, and assignments
1972 to the reference from the temporary variable are emitted to exits. */
1974 static void
1975 execute_sm (struct loop *loop, vec<edge> exits, im_mem_ref *ref)
1977 tree tmp_var, store_flag = NULL_TREE;
1978 unsigned i;
1979 gassign *load;
1980 struct fmt_data fmt_data;
1981 edge ex;
1982 struct lim_aux_data *lim_data;
1983 bool multi_threaded_model_p = false;
1984 gimple_stmt_iterator gsi;
1985 hash_set<basic_block> flag_bbs;
1987 if (dump_file && (dump_flags & TDF_DETAILS))
1989 fprintf (dump_file, "Executing store motion of ");
1990 print_generic_expr (dump_file, ref->mem.ref);
1991 fprintf (dump_file, " from loop %d\n", loop->num);
1994 tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
1995 get_lsm_tmp_name (ref->mem.ref, ~0));
1997 fmt_data.loop = loop;
1998 fmt_data.orig_loop = loop;
1999 for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
2001 if (bb_in_transaction (loop_preheader_edge (loop)->src)
2002 || (! PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES)
2003 && ! ref_always_accessed_p (loop, ref, true)))
2004 multi_threaded_model_p = true;
2006 if (multi_threaded_model_p)
2007 store_flag = execute_sm_if_changed_flag_set (loop, ref, &flag_bbs);
2009 rewrite_mem_refs (loop, ref, tmp_var);
2011 /* Emit the load code on a random exit edge or into the latch if
2012 the loop does not exit, so that we are sure it will be processed
2013 by move_computations after all dependencies. */
2014 gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
2016 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
2017 load altogether, since the store is predicated by a flag. We
2018 could, do the load only if it was originally in the loop. */
2019 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
2020 lim_data = init_lim_data (load);
2021 lim_data->max_loop = loop;
2022 lim_data->tgt_loop = loop;
2023 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
2025 if (multi_threaded_model_p)
2027 load = gimple_build_assign (store_flag, boolean_false_node);
2028 lim_data = init_lim_data (load);
2029 lim_data->max_loop = loop;
2030 lim_data->tgt_loop = loop;
2031 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
2034 /* Sink the store to every exit from the loop. */
2035 FOR_EACH_VEC_ELT (exits, i, ex)
2036 if (!multi_threaded_model_p)
2038 gassign *store;
2039 store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
2040 gsi_insert_on_edge (ex, store);
2042 else
2043 execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag,
2044 loop_preheader_edge (loop), &flag_bbs);
2047 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2048 edges of the LOOP. */
2050 static void
2051 hoist_memory_references (struct loop *loop, bitmap mem_refs,
2052 vec<edge> exits)
2054 im_mem_ref *ref;
2055 unsigned i;
2056 bitmap_iterator bi;
2058 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2060 ref = memory_accesses.refs_list[i];
2061 execute_sm (loop, exits, ref);
2065 struct ref_always_accessed
2067 ref_always_accessed (struct loop *loop_, bool stored_p_)
2068 : loop (loop_), stored_p (stored_p_) {}
2069 bool operator () (mem_ref_loc *loc);
2070 struct loop *loop;
2071 bool stored_p;
2074 bool
2075 ref_always_accessed::operator () (mem_ref_loc *loc)
2077 struct loop *must_exec;
2079 if (!get_lim_data (loc->stmt))
2080 return false;
2082 /* If we require an always executed store make sure the statement
2083 stores to the reference. */
2084 if (stored_p)
2086 tree lhs = gimple_get_lhs (loc->stmt);
2087 if (!lhs
2088 || lhs != *loc->ref)
2089 return false;
2092 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2093 if (!must_exec)
2094 return false;
2096 if (must_exec == loop
2097 || flow_loop_nested_p (must_exec, loop))
2098 return true;
2100 return false;
2103 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2104 make sure REF is always stored to in LOOP. */
2106 static bool
2107 ref_always_accessed_p (struct loop *loop, im_mem_ref *ref, bool stored_p)
2109 return for_all_locs_in_loop (loop, ref,
2110 ref_always_accessed (loop, stored_p));
2113 /* Returns true if REF1 and REF2 are independent. */
2115 static bool
2116 refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2)
2118 if (ref1 == ref2)
2119 return true;
2121 if (dump_file && (dump_flags & TDF_DETAILS))
2122 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2123 ref1->id, ref2->id);
2125 if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
2127 if (dump_file && (dump_flags & TDF_DETAILS))
2128 fprintf (dump_file, "dependent.\n");
2129 return false;
2131 else
2133 if (dump_file && (dump_flags & TDF_DETAILS))
2134 fprintf (dump_file, "independent.\n");
2135 return true;
2139 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2140 and its super-loops. */
2142 static void
2143 record_dep_loop (struct loop *loop, im_mem_ref *ref, bool stored_p)
2145 /* We can propagate dependent-in-loop bits up the loop
2146 hierarchy to all outer loops. */
2147 while (loop != current_loops->tree_root
2148 && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2149 loop = loop_outer (loop);
2152 /* Returns true if REF is independent on all other memory
2153 references in LOOP. */
2155 static bool
2156 ref_indep_loop_p_1 (struct loop *loop, im_mem_ref *ref, bool stored_p)
2158 stored_p |= (ref->stored && bitmap_bit_p (ref->stored, loop->num));
2160 bool indep_p = true;
2161 bitmap refs_to_check;
2163 if (stored_p)
2164 refs_to_check = &memory_accesses.refs_in_loop[loop->num];
2165 else
2166 refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
2168 if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
2169 indep_p = false;
2170 else
2172 if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2173 return true;
2174 if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2175 return false;
2177 struct loop *inner = loop->inner;
2178 while (inner)
2180 if (!ref_indep_loop_p_1 (inner, ref, stored_p))
2182 indep_p = false;
2183 break;
2185 inner = inner->next;
2188 if (indep_p)
2190 unsigned i;
2191 bitmap_iterator bi;
2192 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2194 im_mem_ref *aref = memory_accesses.refs_list[i];
2195 if (!refs_independent_p (ref, aref))
2197 indep_p = false;
2198 break;
2204 if (dump_file && (dump_flags & TDF_DETAILS))
2205 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2206 ref->id, loop->num, indep_p ? "independent" : "dependent");
2208 /* Record the computed result in the cache. */
2209 if (indep_p)
2211 if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
2212 && stored_p)
2214 /* If it's independend against all refs then it's independent
2215 against stores, too. */
2216 bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
2219 else
2221 record_dep_loop (loop, ref, stored_p);
2222 if (!stored_p)
2224 /* If it's dependent against stores it's dependent against
2225 all refs, too. */
2226 record_dep_loop (loop, ref, true);
2230 return indep_p;
2233 /* Returns true if REF is independent on all other memory references in
2234 LOOP. */
2236 static bool
2237 ref_indep_loop_p (struct loop *loop, im_mem_ref *ref)
2239 gcc_checking_assert (MEM_ANALYZABLE (ref));
2241 return ref_indep_loop_p_1 (loop, ref, false);
2244 /* Returns true if we can perform store motion of REF from LOOP. */
2246 static bool
2247 can_sm_ref_p (struct loop *loop, im_mem_ref *ref)
2249 tree base;
2251 /* Can't hoist unanalyzable refs. */
2252 if (!MEM_ANALYZABLE (ref))
2253 return false;
2255 /* It should be movable. */
2256 if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
2257 || TREE_THIS_VOLATILE (ref->mem.ref)
2258 || !for_each_index (&ref->mem.ref, may_move_till, loop))
2259 return false;
2261 /* If it can throw fail, we do not properly update EH info. */
2262 if (tree_could_throw_p (ref->mem.ref))
2263 return false;
2265 /* If it can trap, it must be always executed in LOOP.
2266 Readonly memory locations may trap when storing to them, but
2267 tree_could_trap_p is a predicate for rvalues, so check that
2268 explicitly. */
2269 base = get_base_address (ref->mem.ref);
2270 if ((tree_could_trap_p (ref->mem.ref)
2271 || (DECL_P (base) && TREE_READONLY (base)))
2272 && !ref_always_accessed_p (loop, ref, true))
2273 return false;
2275 /* And it must be independent on all other memory references
2276 in LOOP. */
2277 if (!ref_indep_loop_p (loop, ref))
2278 return false;
2280 return true;
2283 /* Marks the references in LOOP for that store motion should be performed
2284 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2285 motion was performed in one of the outer loops. */
2287 static void
2288 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2290 bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
2291 unsigned i;
2292 bitmap_iterator bi;
2293 im_mem_ref *ref;
2295 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2297 ref = memory_accesses.refs_list[i];
2298 if (can_sm_ref_p (loop, ref))
2299 bitmap_set_bit (refs_to_sm, i);
2303 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2304 for a store motion optimization (i.e. whether we can insert statement
2305 on its exits). */
2307 static bool
2308 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2309 vec<edge> exits)
2311 unsigned i;
2312 edge ex;
2314 FOR_EACH_VEC_ELT (exits, i, ex)
2315 if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
2316 return false;
2318 return true;
2321 /* Try to perform store motion for all memory references modified inside
2322 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2323 store motion was executed in one of the outer loops. */
2325 static void
2326 store_motion_loop (struct loop *loop, bitmap sm_executed)
2328 vec<edge> exits = get_loop_exit_edges (loop);
2329 struct loop *subloop;
2330 bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
2332 if (loop_suitable_for_sm (loop, exits))
2334 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2335 hoist_memory_references (loop, sm_in_loop, exits);
2337 exits.release ();
2339 bitmap_ior_into (sm_executed, sm_in_loop);
2340 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2341 store_motion_loop (subloop, sm_executed);
2342 bitmap_and_compl_into (sm_executed, sm_in_loop);
2343 BITMAP_FREE (sm_in_loop);
2346 /* Try to perform store motion for all memory references modified inside
2347 loops. */
2349 static void
2350 store_motion (void)
2352 struct loop *loop;
2353 bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
2355 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2356 store_motion_loop (loop, sm_executed);
2358 BITMAP_FREE (sm_executed);
2359 gsi_commit_edge_inserts ();
2362 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2363 for each such basic block bb records the outermost loop for that execution
2364 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2365 blocks that contain a nonpure call. */
2367 static void
2368 fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
2370 basic_block bb = NULL, *bbs, last = NULL;
2371 unsigned i;
2372 edge e;
2373 struct loop *inn_loop = loop;
2375 if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
2377 bbs = get_loop_body_in_dom_order (loop);
2379 for (i = 0; i < loop->num_nodes; i++)
2381 edge_iterator ei;
2382 bb = bbs[i];
2384 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2385 last = bb;
2387 if (bitmap_bit_p (contains_call, bb->index))
2388 break;
2390 FOR_EACH_EDGE (e, ei, bb->succs)
2392 /* If there is an exit from this BB. */
2393 if (!flow_bb_inside_loop_p (loop, e->dest))
2394 break;
2395 /* Or we enter a possibly non-finite loop. */
2396 if (flow_loop_nested_p (bb->loop_father,
2397 e->dest->loop_father)
2398 && ! finite_loop_p (e->dest->loop_father))
2399 break;
2401 if (e)
2402 break;
2404 /* A loop might be infinite (TODO use simple loop analysis
2405 to disprove this if possible). */
2406 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2407 break;
2409 if (!flow_bb_inside_loop_p (inn_loop, bb))
2410 break;
2412 if (bb->loop_father->header == bb)
2414 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2415 break;
2417 /* In a loop that is always entered we may proceed anyway.
2418 But record that we entered it and stop once we leave it. */
2419 inn_loop = bb->loop_father;
2423 while (1)
2425 SET_ALWAYS_EXECUTED_IN (last, loop);
2426 if (last == loop->header)
2427 break;
2428 last = get_immediate_dominator (CDI_DOMINATORS, last);
2431 free (bbs);
2434 for (loop = loop->inner; loop; loop = loop->next)
2435 fill_always_executed_in_1 (loop, contains_call);
2438 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2439 for each such basic block bb records the outermost loop for that execution
2440 of its header implies execution of bb. */
2442 static void
2443 fill_always_executed_in (void)
2445 basic_block bb;
2446 struct loop *loop;
2448 auto_sbitmap contains_call (last_basic_block_for_fn (cfun));
2449 bitmap_clear (contains_call);
2450 FOR_EACH_BB_FN (bb, cfun)
2452 gimple_stmt_iterator gsi;
2453 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2455 if (nonpure_call_p (gsi_stmt (gsi)))
2456 break;
2459 if (!gsi_end_p (gsi))
2460 bitmap_set_bit (contains_call, bb->index);
2463 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2464 fill_always_executed_in_1 (loop, contains_call);
2468 /* Compute the global information needed by the loop invariant motion pass. */
2470 static void
2471 tree_ssa_lim_initialize (void)
2473 struct loop *loop;
2474 unsigned i;
2476 bitmap_obstack_initialize (&lim_bitmap_obstack);
2477 gcc_obstack_init (&mem_ref_obstack);
2478 lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;
2480 if (flag_tm)
2481 compute_transaction_bits ();
2483 alloc_aux_for_edges (0);
2485 memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
2486 memory_accesses.refs_list.create (100);
2487 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2488 memory_accesses.refs_list.quick_push
2489 (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
2491 memory_accesses.refs_in_loop.create (number_of_loops (cfun));
2492 memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
2493 memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
2494 memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2495 memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
2496 memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2498 for (i = 0; i < number_of_loops (cfun); i++)
2500 bitmap_initialize (&memory_accesses.refs_in_loop[i],
2501 &lim_bitmap_obstack);
2502 bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
2503 &lim_bitmap_obstack);
2504 bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
2505 &lim_bitmap_obstack);
2508 memory_accesses.ttae_cache = NULL;
2510 /* Initialize bb_loop_postorder with a mapping from loop->num to
2511 its postorder index. */
2512 i = 0;
2513 bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
2514 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2515 bb_loop_postorder[loop->num] = i++;
2518 /* Cleans up after the invariant motion pass. */
2520 static void
2521 tree_ssa_lim_finalize (void)
2523 basic_block bb;
2524 unsigned i;
2525 im_mem_ref *ref;
2527 free_aux_for_edges ();
2529 FOR_EACH_BB_FN (bb, cfun)
2530 SET_ALWAYS_EXECUTED_IN (bb, NULL);
2532 bitmap_obstack_release (&lim_bitmap_obstack);
2533 delete lim_aux_data_map;
2535 delete memory_accesses.refs;
2536 memory_accesses.refs = NULL;
2538 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
2539 memref_free (ref);
2540 memory_accesses.refs_list.release ();
2541 obstack_free (&mem_ref_obstack, NULL);
2543 memory_accesses.refs_in_loop.release ();
2544 memory_accesses.refs_stored_in_loop.release ();
2545 memory_accesses.all_refs_stored_in_loop.release ();
2547 if (memory_accesses.ttae_cache)
2548 free_affine_expand_cache (&memory_accesses.ttae_cache);
2550 free (bb_loop_postorder);
2553 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2554 i.e. those that are likely to be win regardless of the register pressure. */
2556 static unsigned int
2557 tree_ssa_lim (void)
2559 unsigned int todo;
2561 tree_ssa_lim_initialize ();
2563 /* Gathers information about memory accesses in the loops. */
2564 analyze_memory_references ();
2566 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2567 fill_always_executed_in ();
2569 /* For each statement determine the outermost loop in that it is
2570 invariant and cost for computing the invariant. */
2571 invariantness_dom_walker (CDI_DOMINATORS)
2572 .walk (cfun->cfg->x_entry_block_ptr);
2574 /* Execute store motion. Force the necessary invariants to be moved
2575 out of the loops as well. */
2576 store_motion ();
2578 /* Move the expressions that are expensive enough. */
2579 todo = move_computations ();
2581 tree_ssa_lim_finalize ();
2583 return todo;
2586 /* Loop invariant motion pass. */
2588 namespace {
2590 const pass_data pass_data_lim =
2592 GIMPLE_PASS, /* type */
2593 "lim", /* name */
2594 OPTGROUP_LOOP, /* optinfo_flags */
2595 TV_LIM, /* tv_id */
2596 PROP_cfg, /* properties_required */
2597 0, /* properties_provided */
2598 0, /* properties_destroyed */
2599 0, /* todo_flags_start */
2600 0, /* todo_flags_finish */
2603 class pass_lim : public gimple_opt_pass
2605 public:
2606 pass_lim (gcc::context *ctxt)
2607 : gimple_opt_pass (pass_data_lim, ctxt)
2610 /* opt_pass methods: */
2611 opt_pass * clone () { return new pass_lim (m_ctxt); }
2612 virtual bool gate (function *) { return flag_tree_loop_im != 0; }
2613 virtual unsigned int execute (function *);
2615 }; // class pass_lim
2617 unsigned int
2618 pass_lim::execute (function *fun)
2620 bool in_loop_pipeline = scev_initialized_p ();
2621 if (!in_loop_pipeline)
2622 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
2624 if (number_of_loops (fun) <= 1)
2625 return 0;
2626 unsigned int todo = tree_ssa_lim ();
2628 if (!in_loop_pipeline)
2629 loop_optimizer_finalize ();
2630 return todo;
2633 } // anon namespace
2635 gimple_opt_pass *
2636 make_pass_lim (gcc::context *ctxt)
2638 return new pass_lim (ctxt);