re PR tree-optimization/67781 (wrong code generated on big-endian with -O1 -fexpensiv...
[gcc.git] / gcc / tree-ssa-loop-im.c
1 /* Loop invariant motion.
2 Copyright (C) 2003-2016 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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
48 /* TODO: Support for predicated code motion. I.e.
49
50 while (1)
51 {
52 if (cond)
53 {
54 a = inv;
55 something;
56 }
57 }
58
59 Where COND and INV are invariants, but evaluating INV may trap or be
60 invalid from some other reason if !COND. This may be transformed to
61
62 if (cond)
63 a = inv;
64 while (1)
65 {
66 if (cond)
67 something;
68 } */
69
70 /* The auxiliary data kept for each statement. */
71
72 struct lim_aux_data
73 {
74 struct loop *max_loop; /* The outermost loop in that the statement
75 is invariant. */
76
77 struct loop *tgt_loop; /* The loop out of that we want to move the
78 invariant. */
79
80 struct loop *always_executed_in;
81 /* The outermost loop for that we are sure
82 the statement is executed if the loop
83 is entered. */
84
85 unsigned cost; /* Cost of the computation performed by the
86 statement. */
87
88 vec<gimple *> depends; /* Vector of statements that must be also
89 hoisted out of the loop when this statement
90 is hoisted; i.e. those that define the
91 operands of the statement and are inside of
92 the MAX_LOOP loop. */
93 };
94
95 /* Maps statements to their lim_aux_data. */
96
97 static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;
98
99 /* Description of a memory reference location. */
100
101 struct mem_ref_loc
102 {
103 tree *ref; /* The reference itself. */
104 gimple *stmt; /* The statement in that it occurs. */
105 };
106
107
108 /* Description of a memory reference. */
109
110 struct im_mem_ref
111 {
112 unsigned id; /* ID assigned to the memory reference
113 (its index in memory_accesses.refs_list) */
114 hashval_t hash; /* Its hash value. */
115
116 /* The memory access itself and associated caching of alias-oracle
117 query meta-data. */
118 ao_ref mem;
119
120 bitmap stored; /* The set of loops in that this memory location
121 is stored to. */
122 vec<mem_ref_loc> accesses_in_loop;
123 /* The locations of the accesses. Vector
124 indexed by the loop number. */
125
126 /* The following sets are computed on demand. We keep both set and
127 its complement, so that we know whether the information was
128 already computed or not. */
129 bitmap_head indep_loop; /* The set of loops in that the memory
130 reference is independent, meaning:
131 If it is stored in the loop, this store
132 is independent on all other loads and
133 stores.
134 If it is only loaded, then it is independent
135 on all stores in the loop. */
136 bitmap_head dep_loop; /* The complement of INDEP_LOOP. */
137 };
138
139 /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
140 to record (in)dependence against stores in the loop and its subloops, the
141 second to record (in)dependence against all references in the loop
142 and its subloops. */
143 #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
144
145 /* Mem_ref hashtable helpers. */
146
147 struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
148 {
149 typedef tree_node *compare_type;
150 static inline hashval_t hash (const im_mem_ref *);
151 static inline bool equal (const im_mem_ref *, const tree_node *);
152 };
153
154 /* A hash function for struct im_mem_ref object OBJ. */
155
156 inline hashval_t
157 mem_ref_hasher::hash (const im_mem_ref *mem)
158 {
159 return mem->hash;
160 }
161
162 /* An equality function for struct im_mem_ref object MEM1 with
163 memory reference OBJ2. */
164
165 inline bool
166 mem_ref_hasher::equal (const im_mem_ref *mem1, const tree_node *obj2)
167 {
168 return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
169 }
170
171
172 /* Description of memory accesses in loops. */
173
174 static struct
175 {
176 /* The hash table of memory references accessed in loops. */
177 hash_table<mem_ref_hasher> *refs;
178
179 /* The list of memory references. */
180 vec<im_mem_ref *> refs_list;
181
182 /* The set of memory references accessed in each loop. */
183 vec<bitmap_head> refs_in_loop;
184
185 /* The set of memory references stored in each loop. */
186 vec<bitmap_head> refs_stored_in_loop;
187
188 /* The set of memory references stored in each loop, including subloops . */
189 vec<bitmap_head> all_refs_stored_in_loop;
190
191 /* Cache for expanding memory addresses. */
192 hash_map<tree, name_expansion *> *ttae_cache;
193 } memory_accesses;
194
195 /* Obstack for the bitmaps in the above data structures. */
196 static bitmap_obstack lim_bitmap_obstack;
197 static obstack mem_ref_obstack;
198
199 static bool ref_indep_loop_p (struct loop *, im_mem_ref *);
200
201 /* Minimum cost of an expensive expression. */
202 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
203
204 /* The outermost loop for which execution of the header guarantees that the
205 block will be executed. */
206 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
207 #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
208
209 /* ID of the shared unanalyzable mem. */
210 #define UNANALYZABLE_MEM_ID 0
211
212 /* Whether the reference was analyzable. */
213 #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
214
215 static struct lim_aux_data *
216 init_lim_data (gimple *stmt)
217 {
218 lim_aux_data *p = XCNEW (struct lim_aux_data);
219 lim_aux_data_map->put (stmt, p);
220
221 return p;
222 }
223
224 static struct lim_aux_data *
225 get_lim_data (gimple *stmt)
226 {
227 lim_aux_data **p = lim_aux_data_map->get (stmt);
228 if (!p)
229 return NULL;
230
231 return *p;
232 }
233
234 /* Releases the memory occupied by DATA. */
235
236 static void
237 free_lim_aux_data (struct lim_aux_data *data)
238 {
239 data->depends.release ();
240 free (data);
241 }
242
243 static void
244 clear_lim_data (gimple *stmt)
245 {
246 lim_aux_data **p = lim_aux_data_map->get (stmt);
247 if (!p)
248 return;
249
250 free_lim_aux_data (*p);
251 *p = NULL;
252 }
253
254
255 /* The possibilities of statement movement. */
256 enum move_pos
257 {
258 MOVE_IMPOSSIBLE, /* No movement -- side effect expression. */
259 MOVE_PRESERVE_EXECUTION, /* Must not cause the non-executed statement
260 become executed -- memory accesses, ... */
261 MOVE_POSSIBLE /* Unlimited movement. */
262 };
263
264
265 /* If it is possible to hoist the statement STMT unconditionally,
266 returns MOVE_POSSIBLE.
267 If it is possible to hoist the statement STMT, but we must avoid making
268 it executed if it would not be executed in the original program (e.g.
269 because it may trap), return MOVE_PRESERVE_EXECUTION.
270 Otherwise return MOVE_IMPOSSIBLE. */
271
272 enum move_pos
273 movement_possibility (gimple *stmt)
274 {
275 tree lhs;
276 enum move_pos ret = MOVE_POSSIBLE;
277
278 if (flag_unswitch_loops
279 && gimple_code (stmt) == GIMPLE_COND)
280 {
281 /* If we perform unswitching, force the operands of the invariant
282 condition to be moved out of the loop. */
283 return MOVE_POSSIBLE;
284 }
285
286 if (gimple_code (stmt) == GIMPLE_PHI
287 && gimple_phi_num_args (stmt) <= 2
288 && !virtual_operand_p (gimple_phi_result (stmt))
289 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
290 return MOVE_POSSIBLE;
291
292 if (gimple_get_lhs (stmt) == NULL_TREE)
293 return MOVE_IMPOSSIBLE;
294
295 if (gimple_vdef (stmt))
296 return MOVE_IMPOSSIBLE;
297
298 if (stmt_ends_bb_p (stmt)
299 || gimple_has_volatile_ops (stmt)
300 || gimple_has_side_effects (stmt)
301 || stmt_could_throw_p (stmt))
302 return MOVE_IMPOSSIBLE;
303
304 if (is_gimple_call (stmt))
305 {
306 /* While pure or const call is guaranteed to have no side effects, we
307 cannot move it arbitrarily. Consider code like
308
309 char *s = something ();
310
311 while (1)
312 {
313 if (s)
314 t = strlen (s);
315 else
316 t = 0;
317 }
318
319 Here the strlen call cannot be moved out of the loop, even though
320 s is invariant. In addition to possibly creating a call with
321 invalid arguments, moving out a function call that is not executed
322 may cause performance regressions in case the call is costly and
323 not executed at all. */
324 ret = MOVE_PRESERVE_EXECUTION;
325 lhs = gimple_call_lhs (stmt);
326 }
327 else if (is_gimple_assign (stmt))
328 lhs = gimple_assign_lhs (stmt);
329 else
330 return MOVE_IMPOSSIBLE;
331
332 if (TREE_CODE (lhs) == SSA_NAME
333 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
334 return MOVE_IMPOSSIBLE;
335
336 if (TREE_CODE (lhs) != SSA_NAME
337 || gimple_could_trap_p (stmt))
338 return MOVE_PRESERVE_EXECUTION;
339
340 /* Non local loads in a transaction cannot be hoisted out. Well,
341 unless the load happens on every path out of the loop, but we
342 don't take this into account yet. */
343 if (flag_tm
344 && gimple_in_transaction (stmt)
345 && gimple_assign_single_p (stmt))
346 {
347 tree rhs = gimple_assign_rhs1 (stmt);
348 if (DECL_P (rhs) && is_global_var (rhs))
349 {
350 if (dump_file)
351 {
352 fprintf (dump_file, "Cannot hoist conditional load of ");
353 print_generic_expr (dump_file, rhs, TDF_SLIM);
354 fprintf (dump_file, " because it is in a transaction.\n");
355 }
356 return MOVE_IMPOSSIBLE;
357 }
358 }
359
360 return ret;
361 }
362
363 /* Suppose that operand DEF is used inside the LOOP. Returns the outermost
364 loop to that we could move the expression using DEF if it did not have
365 other operands, i.e. the outermost loop enclosing LOOP in that the value
366 of DEF is invariant. */
367
368 static struct loop *
369 outermost_invariant_loop (tree def, struct loop *loop)
370 {
371 gimple *def_stmt;
372 basic_block def_bb;
373 struct loop *max_loop;
374 struct lim_aux_data *lim_data;
375
376 if (!def)
377 return superloop_at_depth (loop, 1);
378
379 if (TREE_CODE (def) != SSA_NAME)
380 {
381 gcc_assert (is_gimple_min_invariant (def));
382 return superloop_at_depth (loop, 1);
383 }
384
385 def_stmt = SSA_NAME_DEF_STMT (def);
386 def_bb = gimple_bb (def_stmt);
387 if (!def_bb)
388 return superloop_at_depth (loop, 1);
389
390 max_loop = find_common_loop (loop, def_bb->loop_father);
391
392 lim_data = get_lim_data (def_stmt);
393 if (lim_data != NULL && lim_data->max_loop != NULL)
394 max_loop = find_common_loop (max_loop,
395 loop_outer (lim_data->max_loop));
396 if (max_loop == loop)
397 return NULL;
398 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
399
400 return max_loop;
401 }
402
403 /* DATA is a structure containing information associated with a statement
404 inside LOOP. DEF is one of the operands of this statement.
405
406 Find the outermost loop enclosing LOOP in that value of DEF is invariant
407 and record this in DATA->max_loop field. If DEF itself is defined inside
408 this loop as well (i.e. we need to hoist it out of the loop if we want
409 to hoist the statement represented by DATA), record the statement in that
410 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
411 add the cost of the computation of DEF to the DATA->cost.
412
413 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
414
415 static bool
416 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
417 bool add_cost)
418 {
419 gimple *def_stmt = SSA_NAME_DEF_STMT (def);
420 basic_block def_bb = gimple_bb (def_stmt);
421 struct loop *max_loop;
422 struct lim_aux_data *def_data;
423
424 if (!def_bb)
425 return true;
426
427 max_loop = outermost_invariant_loop (def, loop);
428 if (!max_loop)
429 return false;
430
431 if (flow_loop_nested_p (data->max_loop, max_loop))
432 data->max_loop = max_loop;
433
434 def_data = get_lim_data (def_stmt);
435 if (!def_data)
436 return true;
437
438 if (add_cost
439 /* Only add the cost if the statement defining DEF is inside LOOP,
440 i.e. if it is likely that by moving the invariants dependent
441 on it, we will be able to avoid creating a new register for
442 it (since it will be only used in these dependent invariants). */
443 && def_bb->loop_father == loop)
444 data->cost += def_data->cost;
445
446 data->depends.safe_push (def_stmt);
447
448 return true;
449 }
450
451 /* Returns an estimate for a cost of statement STMT. The values here
452 are just ad-hoc constants, similar to costs for inlining. */
453
454 static unsigned
455 stmt_cost (gimple *stmt)
456 {
457 /* Always try to create possibilities for unswitching. */
458 if (gimple_code (stmt) == GIMPLE_COND
459 || gimple_code (stmt) == GIMPLE_PHI)
460 return LIM_EXPENSIVE;
461
462 /* We should be hoisting calls if possible. */
463 if (is_gimple_call (stmt))
464 {
465 tree fndecl;
466
467 /* Unless the call is a builtin_constant_p; this always folds to a
468 constant, so moving it is useless. */
469 fndecl = gimple_call_fndecl (stmt);
470 if (fndecl
471 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
472 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
473 return 0;
474
475 return LIM_EXPENSIVE;
476 }
477
478 /* Hoisting memory references out should almost surely be a win. */
479 if (gimple_references_memory_p (stmt))
480 return LIM_EXPENSIVE;
481
482 if (gimple_code (stmt) != GIMPLE_ASSIGN)
483 return 1;
484
485 switch (gimple_assign_rhs_code (stmt))
486 {
487 case MULT_EXPR:
488 case WIDEN_MULT_EXPR:
489 case WIDEN_MULT_PLUS_EXPR:
490 case WIDEN_MULT_MINUS_EXPR:
491 case DOT_PROD_EXPR:
492 case FMA_EXPR:
493 case TRUNC_DIV_EXPR:
494 case CEIL_DIV_EXPR:
495 case FLOOR_DIV_EXPR:
496 case ROUND_DIV_EXPR:
497 case EXACT_DIV_EXPR:
498 case CEIL_MOD_EXPR:
499 case FLOOR_MOD_EXPR:
500 case ROUND_MOD_EXPR:
501 case TRUNC_MOD_EXPR:
502 case RDIV_EXPR:
503 /* Division and multiplication are usually expensive. */
504 return LIM_EXPENSIVE;
505
506 case LSHIFT_EXPR:
507 case RSHIFT_EXPR:
508 case WIDEN_LSHIFT_EXPR:
509 case LROTATE_EXPR:
510 case RROTATE_EXPR:
511 /* Shifts and rotates are usually expensive. */
512 return LIM_EXPENSIVE;
513
514 case CONSTRUCTOR:
515 /* Make vector construction cost proportional to the number
516 of elements. */
517 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
518
519 case SSA_NAME:
520 case PAREN_EXPR:
521 /* Whether or not something is wrapped inside a PAREN_EXPR
522 should not change move cost. Nor should an intermediate
523 unpropagated SSA name copy. */
524 return 0;
525
526 default:
527 return 1;
528 }
529 }
530
531 /* Finds the outermost loop between OUTER and LOOP in that the memory reference
532 REF is independent. If REF is not independent in LOOP, NULL is returned
533 instead. */
534
535 static struct loop *
536 outermost_indep_loop (struct loop *outer, struct loop *loop, im_mem_ref *ref)
537 {
538 struct loop *aloop;
539
540 if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
541 return NULL;
542
543 for (aloop = outer;
544 aloop != loop;
545 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
546 if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
547 && ref_indep_loop_p (aloop, ref))
548 return aloop;
549
550 if (ref_indep_loop_p (loop, ref))
551 return loop;
552 else
553 return NULL;
554 }
555
556 /* If there is a simple load or store to a memory reference in STMT, returns
557 the location of the memory reference, and sets IS_STORE according to whether
558 it is a store or load. Otherwise, returns NULL. */
559
560 static tree *
561 simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
562 {
563 tree *lhs, *rhs;
564
565 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
566 if (!gimple_assign_single_p (stmt))
567 return NULL;
568
569 lhs = gimple_assign_lhs_ptr (stmt);
570 rhs = gimple_assign_rhs1_ptr (stmt);
571
572 if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
573 {
574 *is_store = false;
575 return rhs;
576 }
577 else if (gimple_vdef (stmt)
578 && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
579 {
580 *is_store = true;
581 return lhs;
582 }
583 else
584 return NULL;
585 }
586
587 /* Returns the memory reference contained in STMT. */
588
589 static im_mem_ref *
590 mem_ref_in_stmt (gimple *stmt)
591 {
592 bool store;
593 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
594 hashval_t hash;
595 im_mem_ref *ref;
596
597 if (!mem)
598 return NULL;
599 gcc_assert (!store);
600
601 hash = iterative_hash_expr (*mem, 0);
602 ref = memory_accesses.refs->find_with_hash (*mem, hash);
603
604 gcc_assert (ref != NULL);
605 return ref;
606 }
607
608 /* From a controlling predicate in DOM determine the arguments from
609 the PHI node PHI that are chosen if the predicate evaluates to
610 true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
611 they are non-NULL. Returns true if the arguments can be determined,
612 else return false. */
613
614 static bool
615 extract_true_false_args_from_phi (basic_block dom, gphi *phi,
616 tree *true_arg_p, tree *false_arg_p)
617 {
618 edge te, fe;
619 if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
620 &te, &fe))
621 return false;
622
623 if (true_arg_p)
624 *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
625 if (false_arg_p)
626 *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
627
628 return true;
629 }
630
631 /* Determine the outermost loop to that it is possible to hoist a statement
632 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
633 the outermost loop in that the value computed by STMT is invariant.
634 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
635 we preserve the fact whether STMT is executed. It also fills other related
636 information to LIM_DATA (STMT).
637
638 The function returns false if STMT cannot be hoisted outside of the loop it
639 is defined in, and true otherwise. */
640
641 static bool
642 determine_max_movement (gimple *stmt, bool must_preserve_exec)
643 {
644 basic_block bb = gimple_bb (stmt);
645 struct loop *loop = bb->loop_father;
646 struct loop *level;
647 struct lim_aux_data *lim_data = get_lim_data (stmt);
648 tree val;
649 ssa_op_iter iter;
650
651 if (must_preserve_exec)
652 level = ALWAYS_EXECUTED_IN (bb);
653 else
654 level = superloop_at_depth (loop, 1);
655 lim_data->max_loop = level;
656
657 if (gphi *phi = dyn_cast <gphi *> (stmt))
658 {
659 use_operand_p use_p;
660 unsigned min_cost = UINT_MAX;
661 unsigned total_cost = 0;
662 struct lim_aux_data *def_data;
663
664 /* We will end up promoting dependencies to be unconditionally
665 evaluated. For this reason the PHI cost (and thus the
666 cost we remove from the loop by doing the invariant motion)
667 is that of the cheapest PHI argument dependency chain. */
668 FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
669 {
670 val = USE_FROM_PTR (use_p);
671
672 if (TREE_CODE (val) != SSA_NAME)
673 {
674 /* Assign const 1 to constants. */
675 min_cost = MIN (min_cost, 1);
676 total_cost += 1;
677 continue;
678 }
679 if (!add_dependency (val, lim_data, loop, false))
680 return false;
681
682 gimple *def_stmt = SSA_NAME_DEF_STMT (val);
683 if (gimple_bb (def_stmt)
684 && gimple_bb (def_stmt)->loop_father == loop)
685 {
686 def_data = get_lim_data (def_stmt);
687 if (def_data)
688 {
689 min_cost = MIN (min_cost, def_data->cost);
690 total_cost += def_data->cost;
691 }
692 }
693 }
694
695 min_cost = MIN (min_cost, total_cost);
696 lim_data->cost += min_cost;
697
698 if (gimple_phi_num_args (phi) > 1)
699 {
700 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
701 gimple *cond;
702 if (gsi_end_p (gsi_last_bb (dom)))
703 return false;
704 cond = gsi_stmt (gsi_last_bb (dom));
705 if (gimple_code (cond) != GIMPLE_COND)
706 return false;
707 /* Verify that this is an extended form of a diamond and
708 the PHI arguments are completely controlled by the
709 predicate in DOM. */
710 if (!extract_true_false_args_from_phi (dom, phi, NULL, NULL))
711 return false;
712
713 /* Fold in dependencies and cost of the condition. */
714 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
715 {
716 if (!add_dependency (val, lim_data, loop, false))
717 return false;
718 def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
719 if (def_data)
720 total_cost += def_data->cost;
721 }
722
723 /* We want to avoid unconditionally executing very expensive
724 operations. As costs for our dependencies cannot be
725 negative just claim we are not invariand for this case.
726 We also are not sure whether the control-flow inside the
727 loop will vanish. */
728 if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
729 && !(min_cost != 0
730 && total_cost / min_cost <= 2))
731 return false;
732
733 /* Assume that the control-flow in the loop will vanish.
734 ??? We should verify this and not artificially increase
735 the cost if that is not the case. */
736 lim_data->cost += stmt_cost (stmt);
737 }
738
739 return true;
740 }
741 else
742 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
743 if (!add_dependency (val, lim_data, loop, true))
744 return false;
745
746 if (gimple_vuse (stmt))
747 {
748 im_mem_ref *ref = mem_ref_in_stmt (stmt);
749
750 if (ref)
751 {
752 lim_data->max_loop
753 = outermost_indep_loop (lim_data->max_loop, loop, ref);
754 if (!lim_data->max_loop)
755 return false;
756 }
757 else
758 {
759 if ((val = gimple_vuse (stmt)) != NULL_TREE)
760 {
761 if (!add_dependency (val, lim_data, loop, false))
762 return false;
763 }
764 }
765 }
766
767 lim_data->cost += stmt_cost (stmt);
768
769 return true;
770 }
771
772 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
773 and that one of the operands of this statement is computed by STMT.
774 Ensure that STMT (together with all the statements that define its
775 operands) is hoisted at least out of the loop LEVEL. */
776
777 static void
778 set_level (gimple *stmt, struct loop *orig_loop, struct loop *level)
779 {
780 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
781 struct lim_aux_data *lim_data;
782 gimple *dep_stmt;
783 unsigned i;
784
785 stmt_loop = find_common_loop (orig_loop, stmt_loop);
786 lim_data = get_lim_data (stmt);
787 if (lim_data != NULL && lim_data->tgt_loop != NULL)
788 stmt_loop = find_common_loop (stmt_loop,
789 loop_outer (lim_data->tgt_loop));
790 if (flow_loop_nested_p (stmt_loop, level))
791 return;
792
793 gcc_assert (level == lim_data->max_loop
794 || flow_loop_nested_p (lim_data->max_loop, level));
795
796 lim_data->tgt_loop = level;
797 FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
798 set_level (dep_stmt, orig_loop, level);
799 }
800
801 /* Determines an outermost loop from that we want to hoist the statement STMT.
802 For now we chose the outermost possible loop. TODO -- use profiling
803 information to set it more sanely. */
804
805 static void
806 set_profitable_level (gimple *stmt)
807 {
808 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
809 }
810
811 /* Returns true if STMT is a call that has side effects. */
812
813 static bool
814 nonpure_call_p (gimple *stmt)
815 {
816 if (gimple_code (stmt) != GIMPLE_CALL)
817 return false;
818
819 return gimple_has_side_effects (stmt);
820 }
821
822 /* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
823
824 static gimple *
825 rewrite_reciprocal (gimple_stmt_iterator *bsi)
826 {
827 gassign *stmt, *stmt1, *stmt2;
828 tree name, lhs, type;
829 tree real_one;
830 gimple_stmt_iterator gsi;
831
832 stmt = as_a <gassign *> (gsi_stmt (*bsi));
833 lhs = gimple_assign_lhs (stmt);
834 type = TREE_TYPE (lhs);
835
836 real_one = build_one_cst (type);
837
838 name = make_temp_ssa_name (type, NULL, "reciptmp");
839 stmt1 = gimple_build_assign (name, RDIV_EXPR, real_one,
840 gimple_assign_rhs2 (stmt));
841 stmt2 = gimple_build_assign (lhs, MULT_EXPR, name,
842 gimple_assign_rhs1 (stmt));
843
844 /* Replace division stmt with reciprocal and multiply stmts.
845 The multiply stmt is not invariant, so update iterator
846 and avoid rescanning. */
847 gsi = *bsi;
848 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
849 gsi_replace (&gsi, stmt2, true);
850
851 /* Continue processing with invariant reciprocal statement. */
852 return stmt1;
853 }
854
855 /* Check if the pattern at *BSI is a bittest of the form
856 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
857
858 static gimple *
859 rewrite_bittest (gimple_stmt_iterator *bsi)
860 {
861 gassign *stmt;
862 gimple *stmt1;
863 gassign *stmt2;
864 gimple *use_stmt;
865 gcond *cond_stmt;
866 tree lhs, name, t, a, b;
867 use_operand_p use;
868
869 stmt = as_a <gassign *> (gsi_stmt (*bsi));
870 lhs = gimple_assign_lhs (stmt);
871
872 /* Verify that the single use of lhs is a comparison against zero. */
873 if (TREE_CODE (lhs) != SSA_NAME
874 || !single_imm_use (lhs, &use, &use_stmt))
875 return stmt;
876 cond_stmt = dyn_cast <gcond *> (use_stmt);
877 if (!cond_stmt)
878 return stmt;
879 if (gimple_cond_lhs (cond_stmt) != lhs
880 || (gimple_cond_code (cond_stmt) != NE_EXPR
881 && gimple_cond_code (cond_stmt) != EQ_EXPR)
882 || !integer_zerop (gimple_cond_rhs (cond_stmt)))
883 return stmt;
884
885 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
886 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
887 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
888 return stmt;
889
890 /* There is a conversion in between possibly inserted by fold. */
891 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
892 {
893 t = gimple_assign_rhs1 (stmt1);
894 if (TREE_CODE (t) != SSA_NAME
895 || !has_single_use (t))
896 return stmt;
897 stmt1 = SSA_NAME_DEF_STMT (t);
898 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
899 return stmt;
900 }
901
902 /* Verify that B is loop invariant but A is not. Verify that with
903 all the stmt walking we are still in the same loop. */
904 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
905 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
906 return stmt;
907
908 a = gimple_assign_rhs1 (stmt1);
909 b = gimple_assign_rhs2 (stmt1);
910
911 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
912 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
913 {
914 gimple_stmt_iterator rsi;
915
916 /* 1 << B */
917 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
918 build_int_cst (TREE_TYPE (a), 1), b);
919 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
920 stmt1 = gimple_build_assign (name, t);
921
922 /* A & (1 << B) */
923 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
924 name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
925 stmt2 = gimple_build_assign (name, t);
926
927 /* Replace the SSA_NAME we compare against zero. Adjust
928 the type of zero accordingly. */
929 SET_USE (use, name);
930 gimple_cond_set_rhs (cond_stmt,
931 build_int_cst_type (TREE_TYPE (name),
932 0));
933
934 /* Don't use gsi_replace here, none of the new assignments sets
935 the variable originally set in stmt. Move bsi to stmt1, and
936 then remove the original stmt, so that we get a chance to
937 retain debug info for it. */
938 rsi = *bsi;
939 gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
940 gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
941 gimple *to_release = gsi_stmt (rsi);
942 gsi_remove (&rsi, true);
943 release_defs (to_release);
944
945 return stmt1;
946 }
947
948 return stmt;
949 }
950
951 /* For each statement determines the outermost loop in that it is invariant,
952 - statements on whose motion it depends and the cost of the computation.
953 - This information is stored to the LIM_DATA structure associated with
954 - each statement. */
955 class invariantness_dom_walker : public dom_walker
956 {
957 public:
958 invariantness_dom_walker (cdi_direction direction)
959 : dom_walker (direction) {}
960
961 virtual edge before_dom_children (basic_block);
962 };
963
964 /* Determine the outermost loops in that statements in basic block BB are
965 invariant, and record them to the LIM_DATA associated with the statements.
966 Callback for dom_walker. */
967
968 edge
969 invariantness_dom_walker::before_dom_children (basic_block bb)
970 {
971 enum move_pos pos;
972 gimple_stmt_iterator bsi;
973 gimple *stmt;
974 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
975 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
976 struct lim_aux_data *lim_data;
977
978 if (!loop_outer (bb->loop_father))
979 return NULL;
980
981 if (dump_file && (dump_flags & TDF_DETAILS))
982 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
983 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
984
985 /* Look at PHI nodes, but only if there is at most two.
986 ??? We could relax this further by post-processing the inserted
987 code and transforming adjacent cond-exprs with the same predicate
988 to control flow again. */
989 bsi = gsi_start_phis (bb);
990 if (!gsi_end_p (bsi)
991 && ((gsi_next (&bsi), gsi_end_p (bsi))
992 || (gsi_next (&bsi), gsi_end_p (bsi))))
993 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
994 {
995 stmt = gsi_stmt (bsi);
996
997 pos = movement_possibility (stmt);
998 if (pos == MOVE_IMPOSSIBLE)
999 continue;
1000
1001 lim_data = init_lim_data (stmt);
1002 lim_data->always_executed_in = outermost;
1003
1004 if (!determine_max_movement (stmt, false))
1005 {
1006 lim_data->max_loop = NULL;
1007 continue;
1008 }
1009
1010 if (dump_file && (dump_flags & TDF_DETAILS))
1011 {
1012 print_gimple_stmt (dump_file, stmt, 2, 0);
1013 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1014 loop_depth (lim_data->max_loop),
1015 lim_data->cost);
1016 }
1017
1018 if (lim_data->cost >= LIM_EXPENSIVE)
1019 set_profitable_level (stmt);
1020 }
1021
1022 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1023 {
1024 stmt = gsi_stmt (bsi);
1025
1026 pos = movement_possibility (stmt);
1027 if (pos == MOVE_IMPOSSIBLE)
1028 {
1029 if (nonpure_call_p (stmt))
1030 {
1031 maybe_never = true;
1032 outermost = NULL;
1033 }
1034 /* Make sure to note always_executed_in for stores to make
1035 store-motion work. */
1036 else if (stmt_makes_single_store (stmt))
1037 {
1038 struct lim_aux_data *lim_data = init_lim_data (stmt);
1039 lim_data->always_executed_in = outermost;
1040 }
1041 continue;
1042 }
1043
1044 if (is_gimple_assign (stmt)
1045 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1046 == GIMPLE_BINARY_RHS))
1047 {
1048 tree op0 = gimple_assign_rhs1 (stmt);
1049 tree op1 = gimple_assign_rhs2 (stmt);
1050 struct loop *ol1 = outermost_invariant_loop (op1,
1051 loop_containing_stmt (stmt));
1052
1053 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
1054 to be hoisted out of loop, saving expensive divide. */
1055 if (pos == MOVE_POSSIBLE
1056 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
1057 && flag_unsafe_math_optimizations
1058 && !flag_trapping_math
1059 && ol1 != NULL
1060 && outermost_invariant_loop (op0, ol1) == NULL)
1061 stmt = rewrite_reciprocal (&bsi);
1062
1063 /* If the shift count is invariant, convert (A >> B) & 1 to
1064 A & (1 << B) allowing the bit mask to be hoisted out of the loop
1065 saving an expensive shift. */
1066 if (pos == MOVE_POSSIBLE
1067 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
1068 && integer_onep (op1)
1069 && TREE_CODE (op0) == SSA_NAME
1070 && has_single_use (op0))
1071 stmt = rewrite_bittest (&bsi);
1072 }
1073
1074 lim_data = init_lim_data (stmt);
1075 lim_data->always_executed_in = outermost;
1076
1077 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1078 continue;
1079
1080 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1081 {
1082 lim_data->max_loop = NULL;
1083 continue;
1084 }
1085
1086 if (dump_file && (dump_flags & TDF_DETAILS))
1087 {
1088 print_gimple_stmt (dump_file, stmt, 2, 0);
1089 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
1090 loop_depth (lim_data->max_loop),
1091 lim_data->cost);
1092 }
1093
1094 if (lim_data->cost >= LIM_EXPENSIVE)
1095 set_profitable_level (stmt);
1096 }
1097 return NULL;
1098 }
1099
1100 class move_computations_dom_walker : public dom_walker
1101 {
1102 public:
1103 move_computations_dom_walker (cdi_direction direction)
1104 : dom_walker (direction), todo_ (0) {}
1105
1106 virtual edge before_dom_children (basic_block);
1107
1108 unsigned int todo_;
1109 };
1110
1111 /* Hoist the statements in basic block BB out of the loops prescribed by
1112 data stored in LIM_DATA structures associated with each statement. Callback
1113 for walk_dominator_tree. */
1114
1115 edge
1116 move_computations_dom_walker::before_dom_children (basic_block bb)
1117 {
1118 struct loop *level;
1119 unsigned cost = 0;
1120 struct lim_aux_data *lim_data;
1121
1122 if (!loop_outer (bb->loop_father))
1123 return NULL;
1124
1125 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1126 {
1127 gassign *new_stmt;
1128 gphi *stmt = bsi.phi ();
1129
1130 lim_data = get_lim_data (stmt);
1131 if (lim_data == NULL)
1132 {
1133 gsi_next (&bsi);
1134 continue;
1135 }
1136
1137 cost = lim_data->cost;
1138 level = lim_data->tgt_loop;
1139 clear_lim_data (stmt);
1140
1141 if (!level)
1142 {
1143 gsi_next (&bsi);
1144 continue;
1145 }
1146
1147 if (dump_file && (dump_flags & TDF_DETAILS))
1148 {
1149 fprintf (dump_file, "Moving PHI node\n");
1150 print_gimple_stmt (dump_file, stmt, 0, 0);
1151 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1152 cost, level->num);
1153 }
1154
1155 if (gimple_phi_num_args (stmt) == 1)
1156 {
1157 tree arg = PHI_ARG_DEF (stmt, 0);
1158 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
1159 TREE_CODE (arg), arg);
1160 }
1161 else
1162 {
1163 basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
1164 gimple *cond = gsi_stmt (gsi_last_bb (dom));
1165 tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
1166 /* Get the PHI arguments corresponding to the true and false
1167 edges of COND. */
1168 extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
1169 gcc_assert (arg0 && arg1);
1170 t = build2 (gimple_cond_code (cond), boolean_type_node,
1171 gimple_cond_lhs (cond), gimple_cond_rhs (cond));
1172 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
1173 COND_EXPR, t, arg0, arg1);
1174 todo_ |= TODO_cleanup_cfg;
1175 }
1176 if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt)))
1177 && (!ALWAYS_EXECUTED_IN (bb)
1178 || (ALWAYS_EXECUTED_IN (bb) != level
1179 && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1180 {
1181 tree lhs = gimple_assign_lhs (new_stmt);
1182 SSA_NAME_RANGE_INFO (lhs) = NULL;
1183 }
1184 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1185 remove_phi_node (&bsi, false);
1186 }
1187
1188 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1189 {
1190 edge e;
1191
1192 gimple *stmt = gsi_stmt (bsi);
1193
1194 lim_data = get_lim_data (stmt);
1195 if (lim_data == NULL)
1196 {
1197 gsi_next (&bsi);
1198 continue;
1199 }
1200
1201 cost = lim_data->cost;
1202 level = lim_data->tgt_loop;
1203 clear_lim_data (stmt);
1204
1205 if (!level)
1206 {
1207 gsi_next (&bsi);
1208 continue;
1209 }
1210
1211 /* We do not really want to move conditionals out of the loop; we just
1212 placed it here to force its operands to be moved if necessary. */
1213 if (gimple_code (stmt) == GIMPLE_COND)
1214 continue;
1215
1216 if (dump_file && (dump_flags & TDF_DETAILS))
1217 {
1218 fprintf (dump_file, "Moving statement\n");
1219 print_gimple_stmt (dump_file, stmt, 0, 0);
1220 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1221 cost, level->num);
1222 }
1223
1224 e = loop_preheader_edge (level);
1225 gcc_assert (!gimple_vdef (stmt));
1226 if (gimple_vuse (stmt))
1227 {
1228 /* The new VUSE is the one from the virtual PHI in the loop
1229 header or the one already present. */
1230 gphi_iterator gsi2;
1231 for (gsi2 = gsi_start_phis (e->dest);
1232 !gsi_end_p (gsi2); gsi_next (&gsi2))
1233 {
1234 gphi *phi = gsi2.phi ();
1235 if (virtual_operand_p (gimple_phi_result (phi)))
1236 {
1237 gimple_set_vuse (stmt, PHI_ARG_DEF_FROM_EDGE (phi, e));
1238 break;
1239 }
1240 }
1241 }
1242 gsi_remove (&bsi, false);
1243 if (gimple_has_lhs (stmt)
1244 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
1245 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt)))
1246 && (!ALWAYS_EXECUTED_IN (bb)
1247 || !(ALWAYS_EXECUTED_IN (bb) == level
1248 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1249 {
1250 tree lhs = gimple_get_lhs (stmt);
1251 SSA_NAME_RANGE_INFO (lhs) = NULL;
1252 }
1253 /* In case this is a stmt that is not unconditionally executed
1254 when the target loop header is executed and the stmt may
1255 invoke undefined integer or pointer overflow rewrite it to
1256 unsigned arithmetic. */
1257 if (is_gimple_assign (stmt)
1258 && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
1259 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
1260 && arith_code_with_undefined_signed_overflow
1261 (gimple_assign_rhs_code (stmt))
1262 && (!ALWAYS_EXECUTED_IN (bb)
1263 || !(ALWAYS_EXECUTED_IN (bb) == level
1264 || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
1265 gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
1266 else
1267 gsi_insert_on_edge (e, stmt);
1268 }
1269 return NULL;
1270 }
1271
1272 /* Hoist the statements out of the loops prescribed by data stored in
1273 LIM_DATA structures associated with each statement.*/
1274
1275 static unsigned int
1276 move_computations (void)
1277 {
1278 move_computations_dom_walker walker (CDI_DOMINATORS);
1279 walker.walk (cfun->cfg->x_entry_block_ptr);
1280
1281 gsi_commit_edge_inserts ();
1282 if (need_ssa_update_p (cfun))
1283 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1284
1285 return walker.todo_;
1286 }
1287
1288 /* Checks whether the statement defining variable *INDEX can be hoisted
1289 out of the loop passed in DATA. Callback for for_each_index. */
1290
1291 static bool
1292 may_move_till (tree ref, tree *index, void *data)
1293 {
1294 struct loop *loop = (struct loop *) data, *max_loop;
1295
1296 /* If REF is an array reference, check also that the step and the lower
1297 bound is invariant in LOOP. */
1298 if (TREE_CODE (ref) == ARRAY_REF)
1299 {
1300 tree step = TREE_OPERAND (ref, 3);
1301 tree lbound = TREE_OPERAND (ref, 2);
1302
1303 max_loop = outermost_invariant_loop (step, loop);
1304 if (!max_loop)
1305 return false;
1306
1307 max_loop = outermost_invariant_loop (lbound, loop);
1308 if (!max_loop)
1309 return false;
1310 }
1311
1312 max_loop = outermost_invariant_loop (*index, loop);
1313 if (!max_loop)
1314 return false;
1315
1316 return true;
1317 }
1318
1319 /* If OP is SSA NAME, force the statement that defines it to be
1320 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1321
1322 static void
1323 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1324 {
1325 gimple *stmt;
1326
1327 if (!op
1328 || is_gimple_min_invariant (op))
1329 return;
1330
1331 gcc_assert (TREE_CODE (op) == SSA_NAME);
1332
1333 stmt = SSA_NAME_DEF_STMT (op);
1334 if (gimple_nop_p (stmt))
1335 return;
1336
1337 set_level (stmt, orig_loop, loop);
1338 }
1339
1340 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1341 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1342 for_each_index. */
1343
1344 struct fmt_data
1345 {
1346 struct loop *loop;
1347 struct loop *orig_loop;
1348 };
1349
1350 static bool
1351 force_move_till (tree ref, tree *index, void *data)
1352 {
1353 struct fmt_data *fmt_data = (struct fmt_data *) data;
1354
1355 if (TREE_CODE (ref) == ARRAY_REF)
1356 {
1357 tree step = TREE_OPERAND (ref, 3);
1358 tree lbound = TREE_OPERAND (ref, 2);
1359
1360 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1361 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1362 }
1363
1364 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1365
1366 return true;
1367 }
1368
1369 /* A function to free the mem_ref object OBJ. */
1370
1371 static void
1372 memref_free (struct im_mem_ref *mem)
1373 {
1374 mem->accesses_in_loop.release ();
1375 }
1376
1377 /* Allocates and returns a memory reference description for MEM whose hash
1378 value is HASH and id is ID. */
1379
1380 static im_mem_ref *
1381 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1382 {
1383 im_mem_ref *ref = XOBNEW (&mem_ref_obstack, struct im_mem_ref);
1384 ao_ref_init (&ref->mem, mem);
1385 ref->id = id;
1386 ref->hash = hash;
1387 ref->stored = NULL;
1388 bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
1389 bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
1390 ref->accesses_in_loop.create (1);
1391
1392 return ref;
1393 }
1394
1395 /* Records memory reference location *LOC in LOOP to the memory reference
1396 description REF. The reference occurs in statement STMT. */
1397
1398 static void
1399 record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
1400 {
1401 mem_ref_loc aref;
1402 aref.stmt = stmt;
1403 aref.ref = loc;
1404 ref->accesses_in_loop.safe_push (aref);
1405 }
1406
1407 /* Set the LOOP bit in REF stored bitmap and allocate that if
1408 necessary. Return whether a bit was changed. */
1409
1410 static bool
1411 set_ref_stored_in_loop (im_mem_ref *ref, struct loop *loop)
1412 {
1413 if (!ref->stored)
1414 ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
1415 return bitmap_set_bit (ref->stored, loop->num);
1416 }
1417
1418 /* Marks reference REF as stored in LOOP. */
1419
1420 static void
1421 mark_ref_stored (im_mem_ref *ref, struct loop *loop)
1422 {
1423 while (loop != current_loops->tree_root
1424 && set_ref_stored_in_loop (ref, loop))
1425 loop = loop_outer (loop);
1426 }
1427
1428 /* Gathers memory references in statement STMT in LOOP, storing the
1429 information about them in the memory_accesses structure. Marks
1430 the vops accessed through unrecognized statements there as
1431 well. */
1432
1433 static void
1434 gather_mem_refs_stmt (struct loop *loop, gimple *stmt)
1435 {
1436 tree *mem = NULL;
1437 hashval_t hash;
1438 im_mem_ref **slot;
1439 im_mem_ref *ref;
1440 bool is_stored;
1441 unsigned id;
1442
1443 if (!gimple_vuse (stmt))
1444 return;
1445
1446 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1447 if (!mem)
1448 {
1449 /* We use the shared mem_ref for all unanalyzable refs. */
1450 id = UNANALYZABLE_MEM_ID;
1451 ref = memory_accesses.refs_list[id];
1452 if (dump_file && (dump_flags & TDF_DETAILS))
1453 {
1454 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
1455 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1456 }
1457 is_stored = gimple_vdef (stmt);
1458 }
1459 else
1460 {
1461 hash = iterative_hash_expr (*mem, 0);
1462 slot = memory_accesses.refs->find_slot_with_hash (*mem, hash, INSERT);
1463 if (*slot)
1464 {
1465 ref = *slot;
1466 id = ref->id;
1467 }
1468 else
1469 {
1470 id = memory_accesses.refs_list.length ();
1471 ref = mem_ref_alloc (*mem, hash, id);
1472 memory_accesses.refs_list.safe_push (ref);
1473 *slot = ref;
1474
1475 if (dump_file && (dump_flags & TDF_DETAILS))
1476 {
1477 fprintf (dump_file, "Memory reference %u: ", id);
1478 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
1479 fprintf (dump_file, "\n");
1480 }
1481 }
1482
1483 record_mem_ref_loc (ref, stmt, mem);
1484 }
1485 bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
1486 if (is_stored)
1487 {
1488 bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
1489 mark_ref_stored (ref, loop);
1490 }
1491 return;
1492 }
1493
1494 static unsigned *bb_loop_postorder;
1495
1496 /* qsort sort function to sort blocks after their loop fathers postorder. */
1497
1498 static int
1499 sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
1500 {
1501 basic_block bb1 = *(basic_block *)const_cast<void *>(bb1_);
1502 basic_block bb2 = *(basic_block *)const_cast<void *>(bb2_);
1503 struct loop *loop1 = bb1->loop_father;
1504 struct loop *loop2 = bb2->loop_father;
1505 if (loop1->num == loop2->num)
1506 return 0;
1507 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1508 }
1509
1510 /* qsort sort function to sort ref locs after their loop fathers postorder. */
1511
1512 static int
1513 sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
1514 {
1515 mem_ref_loc *loc1 = (mem_ref_loc *)const_cast<void *>(loc1_);
1516 mem_ref_loc *loc2 = (mem_ref_loc *)const_cast<void *>(loc2_);
1517 struct loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
1518 struct loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
1519 if (loop1->num == loop2->num)
1520 return 0;
1521 return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
1522 }
1523
1524 /* Gathers memory references in loops. */
1525
1526 static void
1527 analyze_memory_references (void)
1528 {
1529 gimple_stmt_iterator bsi;
1530 basic_block bb, *bbs;
1531 struct loop *loop, *outer;
1532 unsigned i, n;
1533
1534 /* Collect all basic-blocks in loops and sort them after their
1535 loops postorder. */
1536 i = 0;
1537 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
1538 FOR_EACH_BB_FN (bb, cfun)
1539 if (bb->loop_father != current_loops->tree_root)
1540 bbs[i++] = bb;
1541 n = i;
1542 qsort (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp);
1543
1544 /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
1545 That results in better locality for all the bitmaps. */
1546 for (i = 0; i < n; ++i)
1547 {
1548 basic_block bb = bbs[i];
1549 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1550 gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
1551 }
1552
1553 /* Sort the location list of gathered memory references after their
1554 loop postorder number. */
1555 im_mem_ref *ref;
1556 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
1557 ref->accesses_in_loop.qsort (sort_locs_in_loop_postorder_cmp);
1558
1559 free (bbs);
1560 // free (bb_loop_postorder);
1561
1562 /* Propagate the information about accessed memory references up
1563 the loop hierarchy. */
1564 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1565 {
1566 /* Finalize the overall touched references (including subloops). */
1567 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
1568 &memory_accesses.refs_stored_in_loop[loop->num]);
1569
1570 /* Propagate the information about accessed memory references up
1571 the loop hierarchy. */
1572 outer = loop_outer (loop);
1573 if (outer == current_loops->tree_root)
1574 continue;
1575
1576 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
1577 &memory_accesses.all_refs_stored_in_loop[loop->num]);
1578 }
1579 }
1580
1581 /* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1582 tree_to_aff_combination_expand. */
1583
1584 static bool
1585 mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
1586 hash_map<tree, name_expansion *> **ttae_cache)
1587 {
1588 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1589 object and their offset differ in such a way that the locations cannot
1590 overlap, then they cannot alias. */
1591 widest_int size1, size2;
1592 aff_tree off1, off2;
1593
1594 /* Perform basic offset and type-based disambiguation. */
1595 if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
1596 return false;
1597
1598 /* The expansion of addresses may be a bit expensive, thus we only do
1599 the check at -O2 and higher optimization levels. */
1600 if (optimize < 2)
1601 return true;
1602
1603 get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
1604 get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
1605 aff_combination_expand (&off1, ttae_cache);
1606 aff_combination_expand (&off2, ttae_cache);
1607 aff_combination_scale (&off1, -1);
1608 aff_combination_add (&off2, &off1);
1609
1610 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1611 return false;
1612
1613 return true;
1614 }
1615
1616 /* Compare function for bsearch searching for reference locations
1617 in a loop. */
1618
1619 static int
1620 find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
1621 {
1622 struct loop *loop = (struct loop *)const_cast<void *>(loop_);
1623 mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
1624 struct loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
1625 if (loop->num == loc_loop->num
1626 || flow_loop_nested_p (loop, loc_loop))
1627 return 0;
1628 return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
1629 ? -1 : 1);
1630 }
1631
1632 /* Iterates over all locations of REF in LOOP and its subloops calling
1633 fn.operator() with the location as argument. When that operator
1634 returns true the iteration is stopped and true is returned.
1635 Otherwise false is returned. */
1636
1637 template <typename FN>
1638 static bool
1639 for_all_locs_in_loop (struct loop *loop, im_mem_ref *ref, FN fn)
1640 {
1641 unsigned i;
1642 mem_ref_loc *loc;
1643
1644 /* Search for the cluster of locs in the accesses_in_loop vector
1645 which is sorted after postorder index of the loop father. */
1646 loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp);
1647 if (!loc)
1648 return false;
1649
1650 /* We have found one location inside loop or its sub-loops. Iterate
1651 both forward and backward to cover the whole cluster. */
1652 i = loc - ref->accesses_in_loop.address ();
1653 while (i > 0)
1654 {
1655 --i;
1656 mem_ref_loc *l = &ref->accesses_in_loop[i];
1657 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1658 break;
1659 if (fn (l))
1660 return true;
1661 }
1662 for (i = loc - ref->accesses_in_loop.address ();
1663 i < ref->accesses_in_loop.length (); ++i)
1664 {
1665 mem_ref_loc *l = &ref->accesses_in_loop[i];
1666 if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
1667 break;
1668 if (fn (l))
1669 return true;
1670 }
1671
1672 return false;
1673 }
1674
1675 /* Rewrites location LOC by TMP_VAR. */
1676
1677 struct rewrite_mem_ref_loc
1678 {
1679 rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
1680 bool operator () (mem_ref_loc *loc);
1681 tree tmp_var;
1682 };
1683
1684 bool
1685 rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
1686 {
1687 *loc->ref = tmp_var;
1688 update_stmt (loc->stmt);
1689 return false;
1690 }
1691
1692 /* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1693
1694 static void
1695 rewrite_mem_refs (struct loop *loop, im_mem_ref *ref, tree tmp_var)
1696 {
1697 for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1698 }
1699
1700 /* Stores the first reference location in LOCP. */
1701
1702 struct first_mem_ref_loc_1
1703 {
1704 first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
1705 bool operator () (mem_ref_loc *loc);
1706 mem_ref_loc **locp;
1707 };
1708
1709 bool
1710 first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
1711 {
1712 *locp = loc;
1713 return true;
1714 }
1715
1716 /* Returns the first reference location to REF in LOOP. */
1717
1718 static mem_ref_loc *
1719 first_mem_ref_loc (struct loop *loop, im_mem_ref *ref)
1720 {
1721 mem_ref_loc *locp = NULL;
1722 for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
1723 return locp;
1724 }
1725
1726 struct prev_flag_edges {
1727 /* Edge to insert new flag comparison code. */
1728 edge append_cond_position;
1729
1730 /* Edge for fall through from previous flag comparison. */
1731 edge last_cond_fallthru;
1732 };
1733
1734 /* Helper function for execute_sm. Emit code to store TMP_VAR into
1735 MEM along edge EX.
1736
1737 The store is only done if MEM has changed. We do this so no
1738 changes to MEM occur on code paths that did not originally store
1739 into it.
1740
1741 The common case for execute_sm will transform:
1742
1743 for (...) {
1744 if (foo)
1745 stuff;
1746 else
1747 MEM = TMP_VAR;
1748 }
1749
1750 into:
1751
1752 lsm = MEM;
1753 for (...) {
1754 if (foo)
1755 stuff;
1756 else
1757 lsm = TMP_VAR;
1758 }
1759 MEM = lsm;
1760
1761 This function will generate:
1762
1763 lsm = MEM;
1764
1765 lsm_flag = false;
1766 ...
1767 for (...) {
1768 if (foo)
1769 stuff;
1770 else {
1771 lsm = TMP_VAR;
1772 lsm_flag = true;
1773 }
1774 }
1775 if (lsm_flag) <--
1776 MEM = lsm; <--
1777 */
1778
1779 static void
1780 execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag)
1781 {
1782 basic_block new_bb, then_bb, old_dest;
1783 bool loop_has_only_one_exit;
1784 edge then_old_edge, orig_ex = ex;
1785 gimple_stmt_iterator gsi;
1786 gimple *stmt;
1787 struct prev_flag_edges *prev_edges = (struct prev_flag_edges *) ex->aux;
1788 bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;
1789
1790 /* ?? Insert store after previous store if applicable. See note
1791 below. */
1792 if (prev_edges)
1793 ex = prev_edges->append_cond_position;
1794
1795 loop_has_only_one_exit = single_pred_p (ex->dest);
1796
1797 if (loop_has_only_one_exit)
1798 ex = split_block_after_labels (ex->dest);
1799 else
1800 {
1801 for (gphi_iterator gpi = gsi_start_phis (ex->dest);
1802 !gsi_end_p (gpi); gsi_next (&gpi))
1803 {
1804 gphi *phi = gpi.phi ();
1805 if (virtual_operand_p (gimple_phi_result (phi)))
1806 continue;
1807
1808 /* When the destination has a non-virtual PHI node with multiple
1809 predecessors make sure we preserve the PHI structure by
1810 forcing a forwarder block so that hoisting of that PHI will
1811 still work. */
1812 split_edge (ex);
1813 break;
1814 }
1815 }
1816
1817 old_dest = ex->dest;
1818 new_bb = split_edge (ex);
1819 then_bb = create_empty_bb (new_bb);
1820 if (irr)
1821 then_bb->flags = BB_IRREDUCIBLE_LOOP;
1822 add_bb_to_loop (then_bb, new_bb->loop_father);
1823
1824 gsi = gsi_start_bb (new_bb);
1825 stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
1826 NULL_TREE, NULL_TREE);
1827 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1828
1829 gsi = gsi_start_bb (then_bb);
1830 /* Insert actual store. */
1831 stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
1832 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1833
1834 make_edge (new_bb, then_bb,
1835 EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1836 make_edge (new_bb, old_dest,
1837 EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1838 then_old_edge = make_edge (then_bb, old_dest,
1839 EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1840
1841 set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
1842
1843 if (prev_edges)
1844 {
1845 basic_block prevbb = prev_edges->last_cond_fallthru->src;
1846 redirect_edge_succ (prev_edges->last_cond_fallthru, new_bb);
1847 set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
1848 set_immediate_dominator (CDI_DOMINATORS, old_dest,
1849 recompute_dominator (CDI_DOMINATORS, old_dest));
1850 }
1851
1852 /* ?? Because stores may alias, they must happen in the exact
1853 sequence they originally happened. Save the position right after
1854 the (_lsm) store we just created so we can continue appending after
1855 it and maintain the original order. */
1856 {
1857 struct prev_flag_edges *p;
1858
1859 if (orig_ex->aux)
1860 orig_ex->aux = NULL;
1861 alloc_aux_for_edge (orig_ex, sizeof (struct prev_flag_edges));
1862 p = (struct prev_flag_edges *) orig_ex->aux;
1863 p->append_cond_position = then_old_edge;
1864 p->last_cond_fallthru = find_edge (new_bb, old_dest);
1865 orig_ex->aux = (void *) p;
1866 }
1867
1868 if (!loop_has_only_one_exit)
1869 for (gphi_iterator gpi = gsi_start_phis (old_dest);
1870 !gsi_end_p (gpi); gsi_next (&gpi))
1871 {
1872 gphi *phi = gpi.phi ();
1873 unsigned i;
1874
1875 for (i = 0; i < gimple_phi_num_args (phi); i++)
1876 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
1877 {
1878 tree arg = gimple_phi_arg_def (phi, i);
1879 add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
1880 update_stmt (phi);
1881 }
1882 }
1883 /* Remove the original fall through edge. This was the
1884 single_succ_edge (new_bb). */
1885 EDGE_SUCC (new_bb, 0)->flags &= ~EDGE_FALLTHRU;
1886 }
1887
1888 /* When REF is set on the location, set flag indicating the store. */
1889
1890 struct sm_set_flag_if_changed
1891 {
1892 sm_set_flag_if_changed (tree flag_) : flag (flag_) {}
1893 bool operator () (mem_ref_loc *loc);
1894 tree flag;
1895 };
1896
1897 bool
1898 sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
1899 {
1900 /* Only set the flag for writes. */
1901 if (is_gimple_assign (loc->stmt)
1902 && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
1903 {
1904 gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
1905 gimple *stmt = gimple_build_assign (flag, boolean_true_node);
1906 gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
1907 }
1908 return false;
1909 }
1910
1911 /* Helper function for execute_sm. On every location where REF is
1912 set, set an appropriate flag indicating the store. */
1913
1914 static tree
1915 execute_sm_if_changed_flag_set (struct loop *loop, im_mem_ref *ref)
1916 {
1917 tree flag;
1918 char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
1919 flag = create_tmp_reg (boolean_type_node, str);
1920 for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag));
1921 return flag;
1922 }
1923
1924 /* Executes store motion of memory reference REF from LOOP.
1925 Exits from the LOOP are stored in EXITS. The initialization of the
1926 temporary variable is put to the preheader of the loop, and assignments
1927 to the reference from the temporary variable are emitted to exits. */
1928
1929 static void
1930 execute_sm (struct loop *loop, vec<edge> exits, im_mem_ref *ref)
1931 {
1932 tree tmp_var, store_flag = NULL_TREE;
1933 unsigned i;
1934 gassign *load;
1935 struct fmt_data fmt_data;
1936 edge ex;
1937 struct lim_aux_data *lim_data;
1938 bool multi_threaded_model_p = false;
1939 gimple_stmt_iterator gsi;
1940
1941 if (dump_file && (dump_flags & TDF_DETAILS))
1942 {
1943 fprintf (dump_file, "Executing store motion of ");
1944 print_generic_expr (dump_file, ref->mem.ref, 0);
1945 fprintf (dump_file, " from loop %d\n", loop->num);
1946 }
1947
1948 tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
1949 get_lsm_tmp_name (ref->mem.ref, ~0));
1950
1951 fmt_data.loop = loop;
1952 fmt_data.orig_loop = loop;
1953 for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
1954
1955 if (bb_in_transaction (loop_preheader_edge (loop)->src)
1956 || !PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES))
1957 multi_threaded_model_p = true;
1958
1959 if (multi_threaded_model_p)
1960 store_flag = execute_sm_if_changed_flag_set (loop, ref);
1961
1962 rewrite_mem_refs (loop, ref, tmp_var);
1963
1964 /* Emit the load code on a random exit edge or into the latch if
1965 the loop does not exit, so that we are sure it will be processed
1966 by move_computations after all dependencies. */
1967 gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
1968
1969 /* FIXME/TODO: For the multi-threaded variant, we could avoid this
1970 load altogether, since the store is predicated by a flag. We
1971 could, do the load only if it was originally in the loop. */
1972 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
1973 lim_data = init_lim_data (load);
1974 lim_data->max_loop = loop;
1975 lim_data->tgt_loop = loop;
1976 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1977
1978 if (multi_threaded_model_p)
1979 {
1980 load = gimple_build_assign (store_flag, boolean_false_node);
1981 lim_data = init_lim_data (load);
1982 lim_data->max_loop = loop;
1983 lim_data->tgt_loop = loop;
1984 gsi_insert_before (&gsi, load, GSI_SAME_STMT);
1985 }
1986
1987 /* Sink the store to every exit from the loop. */
1988 FOR_EACH_VEC_ELT (exits, i, ex)
1989 if (!multi_threaded_model_p)
1990 {
1991 gassign *store;
1992 store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
1993 gsi_insert_on_edge (ex, store);
1994 }
1995 else
1996 execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag);
1997 }
1998
1999 /* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2000 edges of the LOOP. */
2001
2002 static void
2003 hoist_memory_references (struct loop *loop, bitmap mem_refs,
2004 vec<edge> exits)
2005 {
2006 im_mem_ref *ref;
2007 unsigned i;
2008 bitmap_iterator bi;
2009
2010 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2011 {
2012 ref = memory_accesses.refs_list[i];
2013 execute_sm (loop, exits, ref);
2014 }
2015 }
2016
2017 struct ref_always_accessed
2018 {
2019 ref_always_accessed (struct loop *loop_, bool stored_p_)
2020 : loop (loop_), stored_p (stored_p_) {}
2021 bool operator () (mem_ref_loc *loc);
2022 struct loop *loop;
2023 bool stored_p;
2024 };
2025
2026 bool
2027 ref_always_accessed::operator () (mem_ref_loc *loc)
2028 {
2029 struct loop *must_exec;
2030
2031 if (!get_lim_data (loc->stmt))
2032 return false;
2033
2034 /* If we require an always executed store make sure the statement
2035 stores to the reference. */
2036 if (stored_p)
2037 {
2038 tree lhs = gimple_get_lhs (loc->stmt);
2039 if (!lhs
2040 || lhs != *loc->ref)
2041 return false;
2042 }
2043
2044 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2045 if (!must_exec)
2046 return false;
2047
2048 if (must_exec == loop
2049 || flow_loop_nested_p (must_exec, loop))
2050 return true;
2051
2052 return false;
2053 }
2054
2055 /* Returns true if REF is always accessed in LOOP. If STORED_P is true
2056 make sure REF is always stored to in LOOP. */
2057
2058 static bool
2059 ref_always_accessed_p (struct loop *loop, im_mem_ref *ref, bool stored_p)
2060 {
2061 return for_all_locs_in_loop (loop, ref,
2062 ref_always_accessed (loop, stored_p));
2063 }
2064
2065 /* Returns true if REF1 and REF2 are independent. */
2066
2067 static bool
2068 refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2)
2069 {
2070 if (ref1 == ref2)
2071 return true;
2072
2073 if (dump_file && (dump_flags & TDF_DETAILS))
2074 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2075 ref1->id, ref2->id);
2076
2077 if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
2078 {
2079 if (dump_file && (dump_flags & TDF_DETAILS))
2080 fprintf (dump_file, "dependent.\n");
2081 return false;
2082 }
2083 else
2084 {
2085 if (dump_file && (dump_flags & TDF_DETAILS))
2086 fprintf (dump_file, "independent.\n");
2087 return true;
2088 }
2089 }
2090
2091 /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2092 and its super-loops. */
2093
2094 static void
2095 record_dep_loop (struct loop *loop, im_mem_ref *ref, bool stored_p)
2096 {
2097 /* We can propagate dependent-in-loop bits up the loop
2098 hierarchy to all outer loops. */
2099 while (loop != current_loops->tree_root
2100 && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2101 loop = loop_outer (loop);
2102 }
2103
2104 /* Returns true if REF is independent on all other memory references in
2105 LOOP. */
2106
2107 static bool
2108 ref_indep_loop_p_1 (struct loop *loop, im_mem_ref *ref, bool stored_p)
2109 {
2110 bitmap refs_to_check;
2111 unsigned i;
2112 bitmap_iterator bi;
2113 im_mem_ref *aref;
2114
2115 if (stored_p)
2116 refs_to_check = &memory_accesses.refs_in_loop[loop->num];
2117 else
2118 refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
2119
2120 if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
2121 return false;
2122
2123 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2124 {
2125 aref = memory_accesses.refs_list[i];
2126 if (!refs_independent_p (ref, aref))
2127 return false;
2128 }
2129
2130 return true;
2131 }
2132
2133 /* Returns true if REF is independent on all other memory references in
2134 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2135
2136 static bool
2137 ref_indep_loop_p_2 (struct loop *loop, im_mem_ref *ref, bool stored_p)
2138 {
2139 stored_p |= (ref->stored && bitmap_bit_p (ref->stored, loop->num));
2140
2141 if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2142 return true;
2143 if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2144 return false;
2145
2146 struct loop *inner = loop->inner;
2147 while (inner)
2148 {
2149 if (!ref_indep_loop_p_2 (inner, ref, stored_p))
2150 return false;
2151 inner = inner->next;
2152 }
2153
2154 bool indep_p = ref_indep_loop_p_1 (loop, ref, stored_p);
2155
2156 if (dump_file && (dump_flags & TDF_DETAILS))
2157 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2158 ref->id, loop->num, indep_p ? "independent" : "dependent");
2159
2160 /* Record the computed result in the cache. */
2161 if (indep_p)
2162 {
2163 if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
2164 && stored_p)
2165 {
2166 /* If it's independend against all refs then it's independent
2167 against stores, too. */
2168 bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
2169 }
2170 }
2171 else
2172 {
2173 record_dep_loop (loop, ref, stored_p);
2174 if (!stored_p)
2175 {
2176 /* If it's dependent against stores it's dependent against
2177 all refs, too. */
2178 record_dep_loop (loop, ref, true);
2179 }
2180 }
2181
2182 return indep_p;
2183 }
2184
2185 /* Returns true if REF is independent on all other memory references in
2186 LOOP. */
2187
2188 static bool
2189 ref_indep_loop_p (struct loop *loop, im_mem_ref *ref)
2190 {
2191 gcc_checking_assert (MEM_ANALYZABLE (ref));
2192
2193 return ref_indep_loop_p_2 (loop, ref, false);
2194 }
2195
2196 /* Returns true if we can perform store motion of REF from LOOP. */
2197
2198 static bool
2199 can_sm_ref_p (struct loop *loop, im_mem_ref *ref)
2200 {
2201 tree base;
2202
2203 /* Can't hoist unanalyzable refs. */
2204 if (!MEM_ANALYZABLE (ref))
2205 return false;
2206
2207 /* It should be movable. */
2208 if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
2209 || TREE_THIS_VOLATILE (ref->mem.ref)
2210 || !for_each_index (&ref->mem.ref, may_move_till, loop))
2211 return false;
2212
2213 /* If it can throw fail, we do not properly update EH info. */
2214 if (tree_could_throw_p (ref->mem.ref))
2215 return false;
2216
2217 /* If it can trap, it must be always executed in LOOP.
2218 Readonly memory locations may trap when storing to them, but
2219 tree_could_trap_p is a predicate for rvalues, so check that
2220 explicitly. */
2221 base = get_base_address (ref->mem.ref);
2222 if ((tree_could_trap_p (ref->mem.ref)
2223 || (DECL_P (base) && TREE_READONLY (base)))
2224 && !ref_always_accessed_p (loop, ref, true))
2225 return false;
2226
2227 /* And it must be independent on all other memory references
2228 in LOOP. */
2229 if (!ref_indep_loop_p (loop, ref))
2230 return false;
2231
2232 return true;
2233 }
2234
2235 /* Marks the references in LOOP for that store motion should be performed
2236 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2237 motion was performed in one of the outer loops. */
2238
2239 static void
2240 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2241 {
2242 bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
2243 unsigned i;
2244 bitmap_iterator bi;
2245 im_mem_ref *ref;
2246
2247 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2248 {
2249 ref = memory_accesses.refs_list[i];
2250 if (can_sm_ref_p (loop, ref))
2251 bitmap_set_bit (refs_to_sm, i);
2252 }
2253 }
2254
2255 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2256 for a store motion optimization (i.e. whether we can insert statement
2257 on its exits). */
2258
2259 static bool
2260 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2261 vec<edge> exits)
2262 {
2263 unsigned i;
2264 edge ex;
2265
2266 FOR_EACH_VEC_ELT (exits, i, ex)
2267 if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
2268 return false;
2269
2270 return true;
2271 }
2272
2273 /* Try to perform store motion for all memory references modified inside
2274 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2275 store motion was executed in one of the outer loops. */
2276
2277 static void
2278 store_motion_loop (struct loop *loop, bitmap sm_executed)
2279 {
2280 vec<edge> exits = get_loop_exit_edges (loop);
2281 struct loop *subloop;
2282 bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
2283
2284 if (loop_suitable_for_sm (loop, exits))
2285 {
2286 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2287 hoist_memory_references (loop, sm_in_loop, exits);
2288 }
2289 exits.release ();
2290
2291 bitmap_ior_into (sm_executed, sm_in_loop);
2292 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2293 store_motion_loop (subloop, sm_executed);
2294 bitmap_and_compl_into (sm_executed, sm_in_loop);
2295 BITMAP_FREE (sm_in_loop);
2296 }
2297
2298 /* Try to perform store motion for all memory references modified inside
2299 loops. */
2300
2301 static void
2302 store_motion (void)
2303 {
2304 struct loop *loop;
2305 bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
2306
2307 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2308 store_motion_loop (loop, sm_executed);
2309
2310 BITMAP_FREE (sm_executed);
2311 gsi_commit_edge_inserts ();
2312 }
2313
2314 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2315 for each such basic block bb records the outermost loop for that execution
2316 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2317 blocks that contain a nonpure call. */
2318
2319 static void
2320 fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
2321 {
2322 basic_block bb = NULL, *bbs, last = NULL;
2323 unsigned i;
2324 edge e;
2325 struct loop *inn_loop = loop;
2326
2327 if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
2328 {
2329 bbs = get_loop_body_in_dom_order (loop);
2330
2331 for (i = 0; i < loop->num_nodes; i++)
2332 {
2333 edge_iterator ei;
2334 bb = bbs[i];
2335
2336 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2337 last = bb;
2338
2339 if (bitmap_bit_p (contains_call, bb->index))
2340 break;
2341
2342 FOR_EACH_EDGE (e, ei, bb->succs)
2343 if (!flow_bb_inside_loop_p (loop, e->dest))
2344 break;
2345 if (e)
2346 break;
2347
2348 /* A loop might be infinite (TODO use simple loop analysis
2349 to disprove this if possible). */
2350 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2351 break;
2352
2353 if (!flow_bb_inside_loop_p (inn_loop, bb))
2354 break;
2355
2356 if (bb->loop_father->header == bb)
2357 {
2358 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2359 break;
2360
2361 /* In a loop that is always entered we may proceed anyway.
2362 But record that we entered it and stop once we leave it. */
2363 inn_loop = bb->loop_father;
2364 }
2365 }
2366
2367 while (1)
2368 {
2369 SET_ALWAYS_EXECUTED_IN (last, loop);
2370 if (last == loop->header)
2371 break;
2372 last = get_immediate_dominator (CDI_DOMINATORS, last);
2373 }
2374
2375 free (bbs);
2376 }
2377
2378 for (loop = loop->inner; loop; loop = loop->next)
2379 fill_always_executed_in_1 (loop, contains_call);
2380 }
2381
2382 /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2383 for each such basic block bb records the outermost loop for that execution
2384 of its header implies execution of bb. */
2385
2386 static void
2387 fill_always_executed_in (void)
2388 {
2389 sbitmap contains_call = sbitmap_alloc (last_basic_block_for_fn (cfun));
2390 basic_block bb;
2391 struct loop *loop;
2392
2393 bitmap_clear (contains_call);
2394 FOR_EACH_BB_FN (bb, cfun)
2395 {
2396 gimple_stmt_iterator gsi;
2397 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2398 {
2399 if (nonpure_call_p (gsi_stmt (gsi)))
2400 break;
2401 }
2402
2403 if (!gsi_end_p (gsi))
2404 bitmap_set_bit (contains_call, bb->index);
2405 }
2406
2407 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2408 fill_always_executed_in_1 (loop, contains_call);
2409
2410 sbitmap_free (contains_call);
2411 }
2412
2413
2414 /* Compute the global information needed by the loop invariant motion pass. */
2415
2416 static void
2417 tree_ssa_lim_initialize (void)
2418 {
2419 struct loop *loop;
2420 unsigned i;
2421
2422 bitmap_obstack_initialize (&lim_bitmap_obstack);
2423 gcc_obstack_init (&mem_ref_obstack);
2424 lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;
2425
2426 if (flag_tm)
2427 compute_transaction_bits ();
2428
2429 alloc_aux_for_edges (0);
2430
2431 memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
2432 memory_accesses.refs_list.create (100);
2433 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2434 memory_accesses.refs_list.quick_push
2435 (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
2436
2437 memory_accesses.refs_in_loop.create (number_of_loops (cfun));
2438 memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
2439 memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
2440 memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2441 memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
2442 memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2443
2444 for (i = 0; i < number_of_loops (cfun); i++)
2445 {
2446 bitmap_initialize (&memory_accesses.refs_in_loop[i],
2447 &lim_bitmap_obstack);
2448 bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
2449 &lim_bitmap_obstack);
2450 bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
2451 &lim_bitmap_obstack);
2452 }
2453
2454 memory_accesses.ttae_cache = NULL;
2455
2456 /* Initialize bb_loop_postorder with a mapping from loop->num to
2457 its postorder index. */
2458 i = 0;
2459 bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
2460 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2461 bb_loop_postorder[loop->num] = i++;
2462 }
2463
2464 /* Cleans up after the invariant motion pass. */
2465
2466 static void
2467 tree_ssa_lim_finalize (void)
2468 {
2469 basic_block bb;
2470 unsigned i;
2471 im_mem_ref *ref;
2472
2473 free_aux_for_edges ();
2474
2475 FOR_EACH_BB_FN (bb, cfun)
2476 SET_ALWAYS_EXECUTED_IN (bb, NULL);
2477
2478 bitmap_obstack_release (&lim_bitmap_obstack);
2479 delete lim_aux_data_map;
2480
2481 delete memory_accesses.refs;
2482 memory_accesses.refs = NULL;
2483
2484 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
2485 memref_free (ref);
2486 memory_accesses.refs_list.release ();
2487 obstack_free (&mem_ref_obstack, NULL);
2488
2489 memory_accesses.refs_in_loop.release ();
2490 memory_accesses.refs_stored_in_loop.release ();
2491 memory_accesses.all_refs_stored_in_loop.release ();
2492
2493 if (memory_accesses.ttae_cache)
2494 free_affine_expand_cache (&memory_accesses.ttae_cache);
2495
2496 free (bb_loop_postorder);
2497 }
2498
2499 /* Moves invariants from loops. Only "expensive" invariants are moved out --
2500 i.e. those that are likely to be win regardless of the register pressure. */
2501
2502 static unsigned int
2503 tree_ssa_lim (void)
2504 {
2505 unsigned int todo;
2506
2507 tree_ssa_lim_initialize ();
2508
2509 /* Gathers information about memory accesses in the loops. */
2510 analyze_memory_references ();
2511
2512 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2513 fill_always_executed_in ();
2514
2515 /* For each statement determine the outermost loop in that it is
2516 invariant and cost for computing the invariant. */
2517 invariantness_dom_walker (CDI_DOMINATORS)
2518 .walk (cfun->cfg->x_entry_block_ptr);
2519
2520 /* Execute store motion. Force the necessary invariants to be moved
2521 out of the loops as well. */
2522 store_motion ();
2523
2524 /* Move the expressions that are expensive enough. */
2525 todo = move_computations ();
2526
2527 tree_ssa_lim_finalize ();
2528
2529 return todo;
2530 }
2531
2532 /* Loop invariant motion pass. */
2533
2534 namespace {
2535
2536 const pass_data pass_data_lim =
2537 {
2538 GIMPLE_PASS, /* type */
2539 "lim", /* name */
2540 OPTGROUP_LOOP, /* optinfo_flags */
2541 TV_LIM, /* tv_id */
2542 PROP_cfg, /* properties_required */
2543 0, /* properties_provided */
2544 0, /* properties_destroyed */
2545 0, /* todo_flags_start */
2546 0, /* todo_flags_finish */
2547 };
2548
2549 class pass_lim : public gimple_opt_pass
2550 {
2551 public:
2552 pass_lim (gcc::context *ctxt)
2553 : gimple_opt_pass (pass_data_lim, ctxt)
2554 {}
2555
2556 /* opt_pass methods: */
2557 opt_pass * clone () { return new pass_lim (m_ctxt); }
2558 virtual bool gate (function *) { return flag_tree_loop_im != 0; }
2559 virtual unsigned int execute (function *);
2560
2561 }; // class pass_lim
2562
2563 unsigned int
2564 pass_lim::execute (function *fun)
2565 {
2566 bool in_loop_pipeline = scev_initialized_p ();
2567 if (!in_loop_pipeline)
2568 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
2569
2570 if (number_of_loops (fun) <= 1)
2571 return 0;
2572 unsigned int todo = tree_ssa_lim ();
2573
2574 if (!in_loop_pipeline)
2575 loop_optimizer_finalize ();
2576 return todo;
2577 }
2578
2579 } // anon namespace
2580
2581 gimple_opt_pass *
2582 make_pass_lim (gcc::context *ctxt)
2583 {
2584 return new pass_lim (ctxt);
2585 }
2586
2587