1/* Loop invariant motion.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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#include "tree-ssa-loop-niter.h"
48
49/* TODO: Support for predicated code motion. I.e.
50
51 while (1)
52 {
53 if (cond)
54 {
55 a = inv;
56 something;
57 }
58 }
59
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
62
63 if (cond)
64 a = inv;
65 while (1)
66 {
67 if (cond)
68 something;
69 } */
70
71/* The auxiliary data kept for each statement. */
72
73struct lim_aux_data
74{
75 struct loop *max_loop; /* The outermost loop in that the statement
76 is invariant. */
77
78 struct loop *tgt_loop; /* The loop out of that we want to move the
79 invariant. */
80
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. */
85
86 unsigned cost; /* Cost of the computation performed by the
87 statement. */
88
89 unsigned ref; /* The simple_mem_ref in this stmt or 0. */
90
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. */
96};
97
98/* Maps statements to their lim_aux_data. */
99
100static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;
101
102/* Description of a memory reference location. */
103
104struct mem_ref_loc
105{
106 tree *ref; /* The reference itself. */
107 gimple *stmt; /* The statement in that it occurs. */
108};
109
110
111/* Description of a memory reference. */
112
113struct im_mem_ref
114{
115 unsigned id; /* ID assigned to the memory reference
116 (its index in memory_accesses.refs_list) */
117 hashval_t hash; /* Its hash value. */
118
119 /* The memory access itself and associated caching of alias-oracle
120 query meta-data. */
121 ao_ref mem;
122
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. */
128
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. */
140};
141
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))
147
148/* Mem_ref hashtable helpers. */
149
150struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
151{
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 *);
155};
156
157/* A hash function for struct im_mem_ref object OBJ. */
158
159inline hashval_t
160mem_ref_hasher::hash (const im_mem_ref *mem)
161{
162 return mem->hash;
163}
164
165/* An equality function for struct im_mem_ref object MEM1 with
166 memory reference OBJ2. */
167
168inline bool
169mem_ref_hasher::equal (const im_mem_ref *mem1, const tree_node *obj2)
170{
171 return operand_equal_p (mem1->mem.ref, (const_tree) obj2, 0);
172}
173
174
175/* Description of memory accesses in loops. */
176
177static struct
178{
179 /* The hash table of memory references accessed in loops. */
180 hash_table<mem_ref_hasher> *refs;
181
182 /* The list of memory references. */
183 vec<im_mem_ref *> refs_list;
184
185 /* The set of memory references accessed in each loop. */
186 vec<bitmap_head> refs_in_loop;
187
188 /* The set of memory references stored in each loop. */
189 vec<bitmap_head> refs_stored_in_loop;
190
191 /* The set of memory references stored in each loop, including subloops . */
192 vec<bitmap_head> all_refs_stored_in_loop;
193
194 /* Cache for expanding memory addresses. */
195 hash_map<tree, name_expansion *> *ttae_cache;
196} memory_accesses;
197
198/* Obstack for the bitmaps in the above data structures. */
199static bitmap_obstack lim_bitmap_obstack;
200static obstack mem_ref_obstack;
201
202static bool ref_indep_loop_p (struct loop *, im_mem_ref *, struct loop *);
203static bool ref_always_accessed_p (struct loop *, im_mem_ref *, bool);
204
205/* Minimum cost of an expensive expression. */
206#define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
207
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))
212
213/* ID of the shared unanalyzable mem. */
214#define UNANALYZABLE_MEM_ID 0
215
216/* Whether the reference was analyzable. */
217#define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
218
219static struct lim_aux_data *
220init_lim_data (gimple *stmt)
221{
222 lim_aux_data *p = XCNEW (struct lim_aux_data);
223 lim_aux_data_map->put (stmt, p);
224
225 return p;
226}
227
228static struct lim_aux_data *
229get_lim_data (gimple *stmt)
230{
231 lim_aux_data **p = lim_aux_data_map->get (stmt);
232 if (!p)
233 return NULL;
234
235 return *p;
236}
237
238/* Releases the memory occupied by DATA. */
239
240static void
241free_lim_aux_data (struct lim_aux_data *data)
242{
243 data->depends.release ();
244 free (data);
245}
246
247static void
248clear_lim_data (gimple *stmt)
249{
250 lim_aux_data **p = lim_aux_data_map->get (stmt);
251 if (!p)
252 return;
253
254 free_lim_aux_data (*p);
255 *p = NULL;
256}
257
258
259/* The possibilities of statement movement. */
260enum move_pos
261 {
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. */
266 };
267
268
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. */
275
276enum move_pos
277movement_possibility (gimple *stmt)
278{
279 tree lhs;
280 enum move_pos ret = MOVE_POSSIBLE;
281
282 if (flag_unswitch_loops
283 && gimple_code (stmt) == GIMPLE_COND)
284 {
285 /* If we perform unswitching, force the operands of the invariant
286 condition to be moved out of the loop. */
287 return MOVE_POSSIBLE;
288 }
289
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;
295
296 if (gimple_get_lhs (stmt) == NULL_TREE)
297 return MOVE_IMPOSSIBLE;
298
299 if (gimple_vdef (stmt))
300 return MOVE_IMPOSSIBLE;
301
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;
307
308 if (is_gimple_call (stmt))
309 {
310 /* While pure or const call is guaranteed to have no side effects, we
311 cannot move it arbitrarily. Consider code like
312
313 char *s = something ();
314
315 while (1)
316 {
317 if (s)
318 t = strlen (s);
319 else
320 t = 0;
321 }
322
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);
330 }
331 else if (is_gimple_assign (stmt))
332 lhs = gimple_assign_lhs (stmt);
333 else
334 return MOVE_IMPOSSIBLE;
335
336 if (TREE_CODE (lhs) == SSA_NAME
337 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
338 return MOVE_IMPOSSIBLE;
339
340 if (TREE_CODE (lhs) != SSA_NAME
341 || gimple_could_trap_p (stmt))
342 return MOVE_PRESERVE_EXECUTION;
343
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))
350 {
351 tree rhs = gimple_assign_rhs1 (stmt);
352 if (DECL_P (rhs) && is_global_var (rhs))
353 {
354 if (dump_file)
355 {
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");
359 }
360 return MOVE_IMPOSSIBLE;
361 }
362 }
363
364 return ret;
365}
366
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. */
371
372static struct loop *
373outermost_invariant_loop (tree def, struct loop *loop)
374{
375 gimple *def_stmt;
376 basic_block def_bb;
377 struct loop *max_loop;
378 struct lim_aux_data *lim_data;
379
380 if (!def)
381 return superloop_at_depth (loop, 1);
382
383 if (TREE_CODE (def) != SSA_NAME)
384 {
385 gcc_assert (is_gimple_min_invariant (def));
386 return superloop_at_depth (loop, 1);
387 }
388
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);
393
394 max_loop = find_common_loop (loop, def_bb->loop_father);
395
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);
403
404 return max_loop;
405}
406
407/* DATA is a structure containing information associated with a statement
408 inside LOOP. DEF is one of the operands of this statement.
409
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.
416
417 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
418
419static bool
420add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
421 bool add_cost)
422{
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;
427
428 if (!def_bb)
429 return true;
430
431 max_loop = outermost_invariant_loop (def, loop);
432 if (!max_loop)
433 return false;
434
435 if (flow_loop_nested_p (data->max_loop, max_loop))
436 data->max_loop = max_loop;
437
438 def_data = get_lim_data (def_stmt);
439 if (!def_data)
440 return true;
441
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;
449
450 data->depends.safe_push (def_stmt);
451
452 return true;
453}
454
455/* Returns an estimate for a cost of statement STMT. The values here
456 are just ad-hoc constants, similar to costs for inlining. */
457
458static unsigned
459stmt_cost (gimple *stmt)
460{
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;
465
466 /* We should be hoisting calls if possible. */
467 if (is_gimple_call (stmt))
468 {
469 tree fndecl;
470
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;
478
479 return LIM_EXPENSIVE;
480 }
481
482 /* Hoisting memory references out should almost surely be a win. */
483 if (gimple_references_memory_p (stmt))
484 return LIM_EXPENSIVE;
485
486 if (gimple_code (stmt) != GIMPLE_ASSIGN)
487 return 1;
488
489 switch (gimple_assign_rhs_code (stmt))
490 {
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;
509
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;
517
518 case CONSTRUCTOR:
519 /* Make vector construction cost proportional to the number
520 of elements. */
521 return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
522
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;
529
530 default:
531 return 1;
532 }
533}
534
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. */
538
539static struct loop *
540outermost_indep_loop (struct loop *outer, struct loop *loop, im_mem_ref *ref)
541{
542 struct loop *aloop;
543
544 if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
545 return NULL;
546
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, loop))
552 return aloop;
553
554 if (ref_indep_loop_p (loop, ref, loop))
555 return loop;
556 else
557 return NULL;
558}
559
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. */
563
564static tree *
565simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
566{
567 tree *lhs, *rhs;
568
569 /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns. */
570 if (!gimple_assign_single_p (stmt))
571 return NULL;
572
573 lhs = gimple_assign_lhs_ptr (stmt);
574 rhs = gimple_assign_rhs1_ptr (stmt);
575
576 if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
577 {
578 *is_store = false;
579 return rhs;
580 }
581 else if (gimple_vdef (stmt)
582 && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
583 {
584 *is_store = true;
585 return lhs;
586 }
587 else
588 return NULL;
589}
590
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. */
596
597static bool
598extract_true_false_args_from_phi (basic_block dom, gphi *phi,
599 tree *true_arg_p, tree *false_arg_p)
600{
601 edge te, fe;
602 if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
603 &te, &fe))
604 return false;
605
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);
610
611 return true;
612}
613
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).
620
621 The function returns false if STMT cannot be hoisted outside of the loop it
622 is defined in, and true otherwise. */
623
624static bool
625determine_max_movement (gimple *stmt, bool must_preserve_exec)
626{
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;
633
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;
639
640 if (gphi *phi = dyn_cast <gphi *> (stmt))
641 {
642 use_operand_p use_p;
643 unsigned min_cost = UINT_MAX;
644 unsigned total_cost = 0;
645 struct lim_aux_data *def_data;
646
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)
652 {
653 val = USE_FROM_PTR (use_p);
654
655 if (TREE_CODE (val) != SSA_NAME)
656 {
657 /* Assign const 1 to constants. */
658 min_cost = MIN (min_cost, 1);
659 total_cost += 1;
660 continue;
661 }
662 if (!add_dependency (val, lim_data, loop, false))
663 return false;
664
665 gimple *def_stmt = SSA_NAME_DEF_STMT (val);
666 if (gimple_bb (def_stmt)
667 && gimple_bb (def_stmt)->loop_father == loop)
668 {
669 def_data = get_lim_data (def_stmt);
670 if (def_data)
671 {
672 min_cost = MIN (min_cost, def_data->cost);
673 total_cost += def_data->cost;
674 }
675 }
676 }
677
678 min_cost = MIN (min_cost, total_cost);
679 lim_data->cost += min_cost;
680
681 if (gimple_phi_num_args (phi) > 1)
682 {
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;
695
696 /* Fold in dependencies and cost of the condition. */
697 FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
698 {
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;
704 }
705
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;
715
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);
720 }
721
722 return true;
723 }
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;
728
729 if (gimple_vuse (stmt))
730 {
731 im_mem_ref *ref
732 = lim_data ? memory_accesses.refs_list[lim_data->ref] : NULL;
733 if (ref
734 && MEM_ANALYZABLE (ref))
735 {
736 lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
737 loop, ref);
738 if (!lim_data->max_loop)
739 return false;
740 }
741 else if (! add_dependency (gimple_vuse (stmt), lim_data, loop, false))
742 return false;
743 }
744
745 lim_data->cost += stmt_cost (stmt);
746
747 return true;
748}
749
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. */
754
755static void
756set_level (gimple *stmt, struct loop *orig_loop, struct loop *level)
757{
758 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
759 struct lim_aux_data *lim_data;
760 gimple *dep_stmt;
761 unsigned i;
762
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;
770
771 gcc_assert (level == lim_data->max_loop
772 || flow_loop_nested_p (lim_data->max_loop, level));
773
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);
777}
778
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. */
782
783static void
784set_profitable_level (gimple *stmt)
785{
786 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
787}
788
789/* Returns true if STMT is a call that has side effects. */
790
791static bool
792nonpure_call_p (gimple *stmt)
793{
794 if (gimple_code (stmt) != GIMPLE_CALL)
795 return false;
796
797 return gimple_has_side_effects (stmt);
798}
799
800/* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
801
802static gimple *
803rewrite_reciprocal (gimple_stmt_iterator *bsi)
804{
805 gassign *stmt, *stmt1, *stmt2;
806 tree name, lhs, type;
807 tree real_one;
808 gimple_stmt_iterator gsi;
809
810 stmt = as_a <gassign *> (gsi_stmt (*bsi));
811 lhs = gimple_assign_lhs (stmt);
812 type = TREE_TYPE (lhs);
813
814 real_one = build_one_cst (type);
815
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));
821
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);
828
829 /* Continue processing with invariant reciprocal statement. */
830 return stmt1;
831}
832
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. */
835
836static gimple *
837rewrite_bittest (gimple_stmt_iterator *bsi)
838{
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;
846
847 stmt = as_a <gassign *> (gsi_stmt (*bsi));
848 lhs = gimple_assign_lhs (stmt);
849
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;
862
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;
867
868 /* There is a conversion in between possibly inserted by fold. */
869 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
870 {
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;
878 }
879
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;
885
886 a = gimple_assign_rhs1 (stmt1);
887 b = gimple_assign_rhs2 (stmt1);
888
889 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
890 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
891 {
892 gimple_stmt_iterator rsi;
893
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);
899
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);
904
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));
911
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);
922
923 return stmt1;
924 }
925
926 return stmt;
927}
928
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. */
933class invariantness_dom_walker : public dom_walker
934{
935public:
936 invariantness_dom_walker (cdi_direction direction)
937 : dom_walker (direction) {}
938
939 virtual edge before_dom_children (basic_block);
940};
941
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. */
945
946edge
947invariantness_dom_walker::before_dom_children (basic_block bb)
948{
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;
955
956 if (!loop_outer (bb->loop_father))
957 return NULL;
958
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));
962
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))
972 {
973 stmt = gsi_stmt (bsi);
974
975 pos = movement_possibility (stmt);
976 if (pos == MOVE_IMPOSSIBLE)
977 continue;
978
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;
983
984 if (!determine_max_movement (stmt, false))
985 {
986 lim_data->max_loop = NULL;
987 continue;
988 }
989
990 if (dump_file && (dump_flags & TDF_DETAILS))
991 {
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);
996 }
997
998 if (lim_data->cost >= LIM_EXPENSIVE)
999 set_profitable_level (stmt);
1000 }
1001
1002 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1003 {
1004 stmt = gsi_stmt (bsi);
1005
1006 pos = movement_possibility (stmt);
1007 if (pos == MOVE_IMPOSSIBLE)
1008 {
1009 if (nonpure_call_p (stmt))
1010 {
1011 maybe_never = true;
1012 outermost = NULL;
1013 }
1014 /* Make sure to note always_executed_in for stores to make
1015 store-motion work. */
1016 else if (stmt_makes_single_store (stmt))
1017 {
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;
1022 }
1023 continue;
1024 }
1025
1026 if (is_gimple_assign (stmt)
1027 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1028 == GIMPLE_BINARY_RHS))
1029 {
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));
1034
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);
1044
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);
1054 }
1055
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;
1060
1061 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
1062 continue;
1063
1064 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
1065 {
1066 lim_data->max_loop = NULL;
1067 continue;
1068 }
1069
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1071 {
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);
1076 }
1077
1078 if (lim_data->cost >= LIM_EXPENSIVE)
1079 set_profitable_level (stmt);
1080 }
1081 return NULL;
1082}
1083
1084class move_computations_dom_walker : public dom_walker
1085{
1086public:
1087 move_computations_dom_walker (cdi_direction direction)
1088 : dom_walker (direction), todo_ (0) {}
1089
1090 virtual edge before_dom_children (basic_block);
1091
1092 unsigned int todo_;
1093};
1094
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. */
1098
1099unsigned int
1100move_computations_worker (basic_block bb)
1101{
1102 struct loop *level;
1103 unsigned cost = 0;
1104 struct lim_aux_data *lim_data;
1105 unsigned int todo = 0;
1106
1107 if (!loop_outer (bb->loop_father))
1108 return todo;
1109
1110 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
1111 {
1112 gassign *new_stmt;
1113 gphi *stmt = bsi.phi ();
1114
1115 lim_data = get_lim_data (stmt);
1116 if (lim_data == NULL)
1117 {
1118 gsi_next (&bsi);
1119 continue;
1120 }
1121
1122 cost = lim_data->cost;
1123 level = lim_data->tgt_loop;
1124 clear_lim_data (stmt);
1125
1126 if (!level)
1127 {
1128 gsi_next (&bsi);
1129 continue;
1130 }
1131
1132 if (dump_file && (dump_flags & TDF_DETAILS))
1133 {
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);
1138 }
1139
1140 if (gimple_phi_num_args (stmt) == 1)
1141 {
1142 tree arg = PHI_ARG_DEF (stmt, 0);
1143 new_stmt = gimple_build_assign (gimple_phi_result (stmt),
1144 TREE_CODE (arg), arg);
1145 }
1146 else
1147 {
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;
1160 }
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))))
1165 {
1166 tree lhs = gimple_assign_lhs (new_stmt);
1167 SSA_NAME_RANGE_INFO (lhs) = NULL;
1168 }
1169 gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
1170 remove_phi_node (&bsi, false);
1171 }
1172
1173 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1174 {
1175 edge e;
1176
1177 gimple *stmt = gsi_stmt (bsi);
1178
1179 lim_data = get_lim_data (stmt);
1180 if (lim_data == NULL)
1181 {
1182 gsi_next (&bsi);
1183 continue;
1184 }
1185
1186 cost = lim_data->cost;
1187 level = lim_data->tgt_loop;
1188 clear_lim_data (stmt);
1189
1190 if (!level)
1191 {
1192 gsi_next (&bsi);
1193 continue;
1194 }
1195
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;
1200
1201 if (dump_file && (dump_flags & TDF_DETAILS))
1202 {
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);
1207 }
1208
1209 e = loop_preheader_edge (level);
1210 gcc_assert (!gimple_vdef (stmt));
1211 if (gimple_vuse (stmt))
1212 {
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))
1218 {
1219 gphi *phi = gsi2.phi ();
1220 if (virtual_operand_p (gimple_phi_result (phi)))
1221 {
1222 gimple_set_vuse (stmt, PHI_ARG_DEF_FROM_EDGE (phi, e));
1223 break;
1224 }
1225 }
1226 }
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))))
1234 {
1235 tree lhs = gimple_get_lhs (stmt);
1236 SSA_NAME_RANGE_INFO (lhs) = NULL;
1237 }
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);
1253 }
1254
1255 return todo;
1256}
1257
1258/* Hoist the statements out of the loops prescribed by data stored in
1259 LIM_DATA structures associated with each statement.*/
1260
1261static unsigned int
1262move_computations (void)
1263{
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;
1267
1268 for (int i = 0; i < n; ++i)
1269 todo |= move_computations_worker (BASIC_BLOCK_FOR_FN (cfun, rpo[i]));
1270
1271 free (rpo);
1272
1273 gsi_commit_edge_inserts ();
1274 if (need_ssa_update_p (cfun))
1275 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1276
1277 return todo;
1278}
1279
1280/* Checks whether the statement defining variable *INDEX can be hoisted
1281 out of the loop passed in DATA. Callback for for_each_index. */
1282
1283static bool
1284may_move_till (tree ref, tree *index, void *data)
1285{
1286 struct loop *loop = (struct loop *) data, *max_loop;
1287
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)
1291 {
1292 tree step = TREE_OPERAND (ref, 3);
1293 tree lbound = TREE_OPERAND (ref, 2);
1294
1295 max_loop = outermost_invariant_loop (step, loop);
1296 if (!max_loop)
1297 return false;
1298
1299 max_loop = outermost_invariant_loop (lbound, loop);
1300 if (!max_loop)
1301 return false;
1302 }
1303
1304 max_loop = outermost_invariant_loop (*index, loop);
1305 if (!max_loop)
1306 return false;
1307
1308 return true;
1309}
1310
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. */
1313
1314static void
1315force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1316{
1317 gimple *stmt;
1318
1319 if (!op
1320 || is_gimple_min_invariant (op))
1321 return;
1322
1323 gcc_assert (TREE_CODE (op) == SSA_NAME);
1324
1325 stmt = SSA_NAME_DEF_STMT (op);
1326 if (gimple_nop_p (stmt))
1327 return;
1328
1329 set_level (stmt, orig_loop, loop);
1330}
1331
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. */
1335
1336struct fmt_data
1337{
1338 struct loop *loop;
1339 struct loop *orig_loop;
1340};
1341
1342static bool
1343force_move_till (tree ref, tree *index, void *data)
1344{
1345 struct fmt_data *fmt_data = (struct fmt_data *) data;
1346
1347 if (TREE_CODE (ref) == ARRAY_REF)
1348 {
1349 tree step = TREE_OPERAND (ref, 3);
1350 tree lbound = TREE_OPERAND (ref, 2);
1351
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);
1354 }
1355
1356 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1357
1358 return true;
1359}
1360
1361/* A function to free the mem_ref object OBJ. */
1362
1363static void
1364memref_free (struct im_mem_ref *mem)
1365{
1366 mem->accesses_in_loop.release ();
1367}
1368
1369/* Allocates and returns a memory reference description for MEM whose hash
1370 value is HASH and id is ID. */
1371
1372static im_mem_ref *
1373mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1374{
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);
1383
1384 return ref;
1385}
1386
1387/* Records memory reference location *LOC in LOOP to the memory reference
1388 description REF. The reference occurs in statement STMT. */
1389
1390static void
1391record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
1392{
1393 mem_ref_loc aref;
1394 aref.stmt = stmt;
1395 aref.ref = loc;
1396 ref->accesses_in_loop.safe_push (aref);
1397}
1398
1399/* Set the LOOP bit in REF stored bitmap and allocate that if
1400 necessary. Return whether a bit was changed. */
1401
1402static bool
1403set_ref_stored_in_loop (im_mem_ref *ref, struct loop *loop)
1404{
1405 if (!ref->stored)
1406 ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
1407 return bitmap_set_bit (ref->stored, loop->num);
1408}
1409
1410/* Marks reference REF as stored in LOOP. */
1411
1412static void
1413mark_ref_stored (im_mem_ref *ref, struct loop *loop)
1414{
1415 while (loop != current_loops->tree_root
1416 && set_ref_stored_in_loop (ref, loop))
1417 loop = loop_outer (loop);
1418}
1419
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. */
1424
1425static void
1426gather_mem_refs_stmt (struct loop *loop, gimple *stmt)
1427{
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;
1434
1435 if (!gimple_vuse (stmt))
1436 return;
1437
1438 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1439 if (!mem)
1440 {
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))
1445 {
1446 fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
1447 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1448 }
1449 is_stored = gimple_vdef (stmt);
1450 }
1451 else
1452 {
1453 hash = iterative_hash_expr (*mem, 0);
1454 slot = memory_accesses.refs->find_slot_with_hash (*mem, hash, INSERT);
1455 if (*slot)
1456 {
1457 ref = *slot;
1458 id = ref->id;
1459 }
1460 else
1461 {
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;
1466
1467 if (dump_file && (dump_flags & TDF_DETAILS))
1468 {
1469 fprintf (dump_file, "Memory reference %u: ", id);
1470 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
1471 fprintf (dump_file, "\n");
1472 }
1473 }
1474
1475 record_mem_ref_loc (ref, stmt, mem);
1476 }
1477 bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
1478 if (is_stored)
1479 {
1480 bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
1481 mark_ref_stored (ref, loop);
1482 }
1483 init_lim_data (stmt)->ref = ref->id;
1484 return;
1485}
1486
1487static unsigned *bb_loop_postorder;
1488
1489/* qsort sort function to sort blocks after their loop fathers postorder. */
1490
1491static int
1492sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_)
1493{
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;
1501}
1502
1503/* qsort sort function to sort ref locs after their loop fathers postorder. */
1504
1505static int
1506sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_)
1507{
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;
1515}
1516
1517/* Gathers memory references in loops. */
1518
1519static void
1520analyze_memory_references (void)
1521{
1522 gimple_stmt_iterator bsi;
1523 basic_block bb, *bbs;
1524 struct loop *loop, *outer;
1525 unsigned i, n;
1526
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);
1536
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)
1540 {
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));
1544 }
1545
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);
1551
1552 free (bbs);
1553// free (bb_loop_postorder);
1554
1555 /* Propagate the information about accessed memory references up
1556 the loop hierarchy. */
1557 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1558 {
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]);
1562
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;
1568
1569 bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
1570 &memory_accesses.all_refs_stored_in_loop[loop->num]);
1571 }
1572}
1573
1574/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1575 tree_to_aff_combination_expand. */
1576
1577static bool
1578mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
1579 hash_map<tree, name_expansion *> **ttae_cache)
1580{
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 widest_int size1, size2;
1585 aff_tree off1, off2;
1586
1587 /* Perform basic offset and type-based disambiguation. */
1588 if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
1589 return false;
1590
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;
1595
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);
1602
1603 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1604 return false;
1605
1606 return true;
1607}
1608
1609/* Compare function for bsearch searching for reference locations
1610 in a loop. */
1611
1612static int
1613find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_)
1614{
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);
1623}
1624
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. */
1629
1630template <typename FN>
1631static bool
1632for_all_locs_in_loop (struct loop *loop, im_mem_ref *ref, FN fn)
1633{
1634 unsigned i;
1635 mem_ref_loc *loc;
1636
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;
1642
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)
1647 {
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;
1654 }
1655 for (i = loc - ref->accesses_in_loop.address ();
1656 i < ref->accesses_in_loop.length (); ++i)
1657 {
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;
1663 }
1664
1665 return false;
1666}
1667
1668/* Rewrites location LOC by TMP_VAR. */
1669
1670struct rewrite_mem_ref_loc
1671{
1672 rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
1673 bool operator () (mem_ref_loc *loc);
1674 tree tmp_var;
1675};
1676
1677bool
1678rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
1679{
1680 *loc->ref = tmp_var;
1681 update_stmt (loc->stmt);
1682 return false;
1683}
1684
1685/* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1686
1687static void
1688rewrite_mem_refs (struct loop *loop, im_mem_ref *ref, tree tmp_var)
1689{
1690 for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
1691}
1692
1693/* Stores the first reference location in LOCP. */
1694
1695struct first_mem_ref_loc_1
1696{
1697 first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
1698 bool operator () (mem_ref_loc *loc);
1699 mem_ref_loc **locp;
1700};
1701
1702bool
1703first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
1704{
1705 *locp = loc;
1706 return true;
1707}
1708
1709/* Returns the first reference location to REF in LOOP. */
1710
1711static mem_ref_loc *
1712first_mem_ref_loc (struct loop *loop, im_mem_ref *ref)
1713{
1714 mem_ref_loc *locp = NULL;
1715 for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
1716 return locp;
1717}
1718
1719struct prev_flag_edges {
1720 /* Edge to insert new flag comparison code. */
1721 edge append_cond_position;
1722
1723 /* Edge for fall through from previous flag comparison. */
1724 edge last_cond_fallthru;
1725};
1726
1727/* Helper function for execute_sm. Emit code to store TMP_VAR into
1728 MEM along edge EX.
1729
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.
1733
1734 The common case for execute_sm will transform:
1735
1736 for (...) {
1737 if (foo)
1738 stuff;
1739 else
1740 MEM = TMP_VAR;
1741 }
1742
1743 into:
1744
1745 lsm = MEM;
1746 for (...) {
1747 if (foo)
1748 stuff;
1749 else
1750 lsm = TMP_VAR;
1751 }
1752 MEM = lsm;
1753
1754 This function will generate:
1755
1756 lsm = MEM;
1757
1758 lsm_flag = false;
1759 ...
1760 for (...) {
1761 if (foo)
1762 stuff;
1763 else {
1764 lsm = TMP_VAR;
1765 lsm_flag = true;
1766 }
1767 }
1768 if (lsm_flag) <--
1769 MEM = lsm; <--
1770*/
1771
1772static void
1773execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag,
1774 edge preheader, hash_set <basic_block> *flag_bbs)
1775{
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;
1783
1784 profile_count count_sum = profile_count::zero ();
1785 int nbbs = 0, ncount = 0;
1786 profile_probability flag_probability = profile_probability::uninitialized ();
1787
1788 /* Flag is set in FLAG_BBS. Determine probability that flag will be true
1789 at loop exit.
1790
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.
1794
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. */
1801
1802 for (hash_set<basic_block>::iterator it = flag_bbs->begin ();
1803 it != flag_bbs->end (); ++it)
1804 {
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++;
1810 }
1811
1812 profile_probability cap = profile_probability::always ().apply_scale (2, 3);
1813
1814 if (flag_probability.initialized_p ())
1815 ;
1816 else if (ncount == nbbs
1817 && preheader->count () >= count_sum && preheader->count ().nonzero_p ())
1818 {
1819 flag_probability = count_sum.probability_in (preheader->count ());
1820 if (flag_probability > cap)
1821 flag_probability = cap;
1822 }
1823
1824 if (!flag_probability.initialized_p ())
1825 flag_probability = cap;
1826
1827 /* ?? Insert store after previous store if applicable. See note
1828 below. */
1829 if (prev_edges)
1830 ex = prev_edges->append_cond_position;
1831
1832 loop_has_only_one_exit = single_pred_p (ex->dest);
1833
1834 if (loop_has_only_one_exit)
1835 ex = split_block_after_labels (ex->dest);
1836 else
1837 {
1838 for (gphi_iterator gpi = gsi_start_phis (ex->dest);
1839 !gsi_end_p (gpi); gsi_next (&gpi))
1840 {
1841 gphi *phi = gpi.phi ();
1842 if (virtual_operand_p (gimple_phi_result (phi)))
1843 continue;
1844
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;
1851 }
1852 }
1853
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);
1861
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);
1866
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);
1871
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;
1876
1877 e1->flags |= EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0);
1878 e1->flags &= ~EDGE_FALLTHRU;
1879
1880 e1->probability = flag_probability.invert ();
1881
1882 then_old_edge = make_single_succ_edge (then_bb, old_dest,
1883 EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
1884
1885 set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
1886
1887 if (prev_edges)
1888 {
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));
1894 }
1895
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. */
1900 {
1901 struct prev_flag_edges *p;
1902
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;
1910 }
1911
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))
1915 {
1916 gphi *phi = gpi.phi ();
1917 unsigned i;
1918
1919 for (i = 0; i < gimple_phi_num_args (phi); i++)
1920 if (gimple_phi_arg_edge (phi, i)->src == new_bb)
1921 {
1922 tree arg = gimple_phi_arg_def (phi, i);
1923 add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
1924 update_stmt (phi);
1925 }
1926 }
1927}
1928
1929/* When REF is set on the location, set flag indicating the store. */
1930
1931struct sm_set_flag_if_changed
1932{
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;
1938};
1939
1940bool
1941sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
1942{
1943 /* Only set the flag for writes. */
1944 if (is_gimple_assign (loc->stmt)
1945 && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
1946 {
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));
1951 }
1952 return false;
1953}
1954
1955/* Helper function for execute_sm. On every location where REF is
1956 set, set an appropriate flag indicating the store. */
1957
1958static tree
1959execute_sm_if_changed_flag_set (struct loop *loop, im_mem_ref *ref,
1960 hash_set <basic_block> *bbs)
1961{
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;
1967}
1968
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. */
1973
1974static void
1975execute_sm (struct loop *loop, vec<edge> exits, im_mem_ref *ref)
1976{
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;
1986
1987 if (dump_file && (dump_flags & TDF_DETAILS))
1988 {
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);
1992 }
1993
1994 tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
1995 get_lsm_tmp_name (ref->mem.ref, ~0));
1996
1997 fmt_data.loop = loop;
1998 fmt_data.orig_loop = loop;
1999 for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
2000
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;
2005
2006 if (multi_threaded_model_p)
2007 store_flag = execute_sm_if_changed_flag_set (loop, ref, &flag_bbs);
2008
2009 rewrite_mem_refs (loop, ref, tmp_var);
2010
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);
2015
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);
2024
2025 if (multi_threaded_model_p)
2026 {
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);
2032 }
2033
2034 /* Sink the store to every exit from the loop. */
2035 FOR_EACH_VEC_ELT (exits, i, ex)
2036 if (!multi_threaded_model_p)
2037 {
2038 gassign *store;
2039 store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
2040 gsi_insert_on_edge (ex, store);
2041 }
2042 else
2043 execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag,
2044 loop_preheader_edge (loop), &flag_bbs);
2045}
2046
2047/* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
2048 edges of the LOOP. */
2049
2050static void
2051hoist_memory_references (struct loop *loop, bitmap mem_refs,
2052 vec<edge> exits)
2053{
2054 im_mem_ref *ref;
2055 unsigned i;
2056 bitmap_iterator bi;
2057
2058 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
2059 {
2060 ref = memory_accesses.refs_list[i];
2061 execute_sm (loop, exits, ref);
2062 }
2063}
2064
2065struct ref_always_accessed
2066{
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;
2072};
2073
2074bool
2075ref_always_accessed::operator () (mem_ref_loc *loc)
2076{
2077 struct loop *must_exec;
2078
2079 if (!get_lim_data (loc->stmt))
2080 return false;
2081
2082 /* If we require an always executed store make sure the statement
2083 stores to the reference. */
2084 if (stored_p)
2085 {
2086 tree lhs = gimple_get_lhs (loc->stmt);
2087 if (!lhs
2088 || lhs != *loc->ref)
2089 return false;
2090 }
2091
2092 must_exec = get_lim_data (loc->stmt)->always_executed_in;
2093 if (!must_exec)
2094 return false;
2095
2096 if (must_exec == loop
2097 || flow_loop_nested_p (must_exec, loop))
2098 return true;
2099
2100 return false;
2101}
2102
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. */
2105
2106static bool
2107ref_always_accessed_p (struct loop *loop, im_mem_ref *ref, bool stored_p)
2108{
2109 return for_all_locs_in_loop (loop, ref,
2110 ref_always_accessed (loop, stored_p));
2111}
2112
2113/* Returns true if REF1 and REF2 are independent. */
2114
2115static bool
2116refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2)
2117{
2118 if (ref1 == ref2)
2119 return true;
2120
2121 if (dump_file && (dump_flags & TDF_DETAILS))
2122 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
2123 ref1->id, ref2->id);
2124
2125 if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
2126 {
2127 if (dump_file && (dump_flags & TDF_DETAILS))
2128 fprintf (dump_file, "dependent.\n");
2129 return false;
2130 }
2131 else
2132 {
2133 if (dump_file && (dump_flags & TDF_DETAILS))
2134 fprintf (dump_file, "independent.\n");
2135 return true;
2136 }
2137}
2138
2139/* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
2140 and its super-loops. */
2141
2142static void
2143record_dep_loop (struct loop *loop, im_mem_ref *ref, bool stored_p)
2144{
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);
2150}
2151
2152/* Returns true if REF is independent on all other memory
2153 references in LOOP. REF_LOOP is where REF is accessed, SAFELEN is the
2154 safelen to apply. */
2155
2156static bool
2157ref_indep_loop_p_1 (int safelen, struct loop *loop, im_mem_ref *ref,
2158 bool stored_p, struct loop *ref_loop)
2159{
2160 stored_p |= (ref->stored && bitmap_bit_p (ref->stored, loop->num));
2161
2162 if (loop->safelen > safelen
2163 /* Check that REF is accessed inside LOOP. */
2164 && (loop == ref_loop || flow_loop_nested_p (loop, ref_loop)))
2165 safelen = loop->safelen;
2166
2167 bool indep_p = true;
2168 bitmap refs_to_check;
2169
2170 if (stored_p)
2171 refs_to_check = &memory_accesses.refs_in_loop[loop->num];
2172 else
2173 refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
2174
2175 if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
2176 indep_p = false;
2177 else if (safelen > 1)
2178 {
2179 if (dump_file && (dump_flags & TDF_DETAILS))
2180 {
2181 fprintf (dump_file,"REF is independent due to safelen %d\n",
2182 safelen);
2183 print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
2184 fprintf (dump_file, "\n");
2185 }
2186
2187 /* We need to recurse to properly handle UNANALYZABLE_MEM_ID. */
2188 struct loop *inner = loop->inner;
2189 while (inner)
2190 {
2191 if (!ref_indep_loop_p_1 (safelen, inner, ref, stored_p, ref_loop))
2192 {
2193 indep_p = false;
2194 break;
2195 }
2196 inner = inner->next;
2197 }
2198
2199 /* Avoid caching here as safelen depends on context and refs
2200 are shared between different contexts. */
2201 return indep_p;
2202 }
2203 else
2204 {
2205 if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2206 return true;
2207 if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
2208 return false;
2209
2210 struct loop *inner = loop->inner;
2211 while (inner)
2212 {
2213 if (!ref_indep_loop_p_1 (safelen, inner, ref, stored_p, ref_loop))
2214 {
2215 indep_p = false;
2216 break;
2217 }
2218 inner = inner->next;
2219 }
2220
2221 if (indep_p)
2222 {
2223 unsigned i;
2224 bitmap_iterator bi;
2225 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2226 {
2227 im_mem_ref *aref = memory_accesses.refs_list[i];
2228 if (!refs_independent_p (ref, aref))
2229 {
2230 indep_p = false;
2231 break;
2232 }
2233 }
2234 }
2235 }
2236
2237 if (dump_file && (dump_flags & TDF_DETAILS))
2238 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2239 ref->id, loop->num, indep_p ? "independent" : "dependent");
2240
2241 /* Record the computed result in the cache. */
2242 if (indep_p)
2243 {
2244 if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
2245 && stored_p)
2246 {
2247 /* If it's independend against all refs then it's independent
2248 against stores, too. */
2249 bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
2250 }
2251 }
2252 else
2253 {
2254 record_dep_loop (loop, ref, stored_p);
2255 if (!stored_p)
2256 {
2257 /* If it's dependent against stores it's dependent against
2258 all refs, too. */
2259 record_dep_loop (loop, ref, true);
2260 }
2261 }
2262
2263 return indep_p;
2264}
2265
2266/* Returns true if REF is independent on all other memory references in
2267 LOOP. REF_LOOP is the loop where REF is accessed. */
2268
2269static bool
2270ref_indep_loop_p (struct loop *loop, im_mem_ref *ref, struct loop *ref_loop)
2271{
2272 gcc_checking_assert (MEM_ANALYZABLE (ref));
2273
2274 return ref_indep_loop_p_1 (0, loop, ref, false, ref_loop);
2275}
2276
2277/* Returns true if we can perform store motion of REF from LOOP. */
2278
2279static bool
2280can_sm_ref_p (struct loop *loop, im_mem_ref *ref)
2281{
2282 tree base;
2283
2284 /* Can't hoist unanalyzable refs. */
2285 if (!MEM_ANALYZABLE (ref))
2286 return false;
2287
2288 /* It should be movable. */
2289 if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
2290 || TREE_THIS_VOLATILE (ref->mem.ref)
2291 || !for_each_index (&ref->mem.ref, may_move_till, loop))
2292 return false;
2293
2294 /* If it can throw fail, we do not properly update EH info. */
2295 if (tree_could_throw_p (ref->mem.ref))
2296 return false;
2297
2298 /* If it can trap, it must be always executed in LOOP.
2299 Readonly memory locations may trap when storing to them, but
2300 tree_could_trap_p is a predicate for rvalues, so check that
2301 explicitly. */
2302 base = get_base_address (ref->mem.ref);
2303 if ((tree_could_trap_p (ref->mem.ref)
2304 || (DECL_P (base) && TREE_READONLY (base)))
2305 && !ref_always_accessed_p (loop, ref, true))
2306 return false;
2307
2308 /* And it must be independent on all other memory references
2309 in LOOP. */
2310 if (!ref_indep_loop_p (loop, ref, loop))
2311 return false;
2312
2313 return true;
2314}
2315
2316/* Marks the references in LOOP for that store motion should be performed
2317 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2318 motion was performed in one of the outer loops. */
2319
2320static void
2321find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2322{
2323 bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
2324 unsigned i;
2325 bitmap_iterator bi;
2326 im_mem_ref *ref;
2327
2328 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2329 {
2330 ref = memory_accesses.refs_list[i];
2331 if (can_sm_ref_p (loop, ref))
2332 bitmap_set_bit (refs_to_sm, i);
2333 }
2334}
2335
2336/* Checks whether LOOP (with exits stored in EXITS array) is suitable
2337 for a store motion optimization (i.e. whether we can insert statement
2338 on its exits). */
2339
2340static bool
2341loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2342 vec<edge> exits)
2343{
2344 unsigned i;
2345 edge ex;
2346
2347 FOR_EACH_VEC_ELT (exits, i, ex)
2348 if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
2349 return false;
2350
2351 return true;
2352}
2353
2354/* Try to perform store motion for all memory references modified inside
2355 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2356 store motion was executed in one of the outer loops. */
2357
2358static void
2359store_motion_loop (struct loop *loop, bitmap sm_executed)
2360{
2361 vec<edge> exits = get_loop_exit_edges (loop);
2362 struct loop *subloop;
2363 bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
2364
2365 if (loop_suitable_for_sm (loop, exits))
2366 {
2367 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2368 hoist_memory_references (loop, sm_in_loop, exits);
2369 }
2370 exits.release ();
2371
2372 bitmap_ior_into (sm_executed, sm_in_loop);
2373 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2374 store_motion_loop (subloop, sm_executed);
2375 bitmap_and_compl_into (sm_executed, sm_in_loop);
2376 BITMAP_FREE (sm_in_loop);
2377}
2378
2379/* Try to perform store motion for all memory references modified inside
2380 loops. */
2381
2382static void
2383store_motion (void)
2384{
2385 struct loop *loop;
2386 bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
2387
2388 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2389 store_motion_loop (loop, sm_executed);
2390
2391 BITMAP_FREE (sm_executed);
2392 gsi_commit_edge_inserts ();
2393}
2394
2395/* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2396 for each such basic block bb records the outermost loop for that execution
2397 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2398 blocks that contain a nonpure call. */
2399
2400static void
2401fill_always_executed_in_1 (struct loop *loop, sbitmap contains_call)
2402{
2403 basic_block bb = NULL, *bbs, last = NULL;
2404 unsigned i;
2405 edge e;
2406 struct loop *inn_loop = loop;
2407
2408 if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
2409 {
2410 bbs = get_loop_body_in_dom_order (loop);
2411
2412 for (i = 0; i < loop->num_nodes; i++)
2413 {
2414 edge_iterator ei;
2415 bb = bbs[i];
2416
2417 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2418 last = bb;
2419
2420 if (bitmap_bit_p (contains_call, bb->index))
2421 break;
2422
2423 FOR_EACH_EDGE (e, ei, bb->succs)
2424 {
2425 /* If there is an exit from this BB. */
2426 if (!flow_bb_inside_loop_p (loop, e->dest))
2427 break;
2428 /* Or we enter a possibly non-finite loop. */
2429 if (flow_loop_nested_p (bb->loop_father,
2430 e->dest->loop_father)
2431 && ! finite_loop_p (e->dest->loop_father))
2432 break;
2433 }
2434 if (e)
2435 break;
2436
2437 /* A loop might be infinite (TODO use simple loop analysis
2438 to disprove this if possible). */
2439 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2440 break;
2441
2442 if (!flow_bb_inside_loop_p (inn_loop, bb))
2443 break;
2444
2445 if (bb->loop_father->header == bb)
2446 {
2447 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2448 break;
2449
2450 /* In a loop that is always entered we may proceed anyway.
2451 But record that we entered it and stop once we leave it. */
2452 inn_loop = bb->loop_father;
2453 }
2454 }
2455
2456 while (1)
2457 {
2458 SET_ALWAYS_EXECUTED_IN (last, loop);
2459 if (last == loop->header)
2460 break;
2461 last = get_immediate_dominator (CDI_DOMINATORS, last);
2462 }
2463
2464 free (bbs);
2465 }
2466
2467 for (loop = loop->inner; loop; loop = loop->next)
2468 fill_always_executed_in_1 (loop, contains_call);
2469}
2470
2471/* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
2472 for each such basic block bb records the outermost loop for that execution
2473 of its header implies execution of bb. */
2474
2475static void
2476fill_always_executed_in (void)
2477{
2478 basic_block bb;
2479 struct loop *loop;
2480
2481 auto_sbitmap contains_call (last_basic_block_for_fn (cfun));
2482 bitmap_clear (contains_call);
2483 FOR_EACH_BB_FN (bb, cfun)
2484 {
2485 gimple_stmt_iterator gsi;
2486 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2487 {
2488 if (nonpure_call_p (gsi_stmt (gsi)))
2489 break;
2490 }
2491
2492 if (!gsi_end_p (gsi))
2493 bitmap_set_bit (contains_call, bb->index);
2494 }
2495
2496 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2497 fill_always_executed_in_1 (loop, contains_call);
2498}
2499
2500
2501/* Compute the global information needed by the loop invariant motion pass. */
2502
2503static void
2504tree_ssa_lim_initialize (void)
2505{
2506 struct loop *loop;
2507 unsigned i;
2508
2509 bitmap_obstack_initialize (&lim_bitmap_obstack);
2510 gcc_obstack_init (&mem_ref_obstack);
2511 lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;
2512
2513 if (flag_tm)
2514 compute_transaction_bits ();
2515
2516 alloc_aux_for_edges (0);
2517
2518 memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
2519 memory_accesses.refs_list.create (100);
2520 /* Allocate a special, unanalyzable mem-ref with ID zero. */
2521 memory_accesses.refs_list.quick_push
2522 (mem_ref_alloc (error_mark_node, 0, UNANALYZABLE_MEM_ID));
2523
2524 memory_accesses.refs_in_loop.create (number_of_loops (cfun));
2525 memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
2526 memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
2527 memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2528 memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
2529 memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
2530
2531 for (i = 0; i < number_of_loops (cfun); i++)
2532 {
2533 bitmap_initialize (&memory_accesses.refs_in_loop[i],
2534 &lim_bitmap_obstack);
2535 bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
2536 &lim_bitmap_obstack);
2537 bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
2538 &lim_bitmap_obstack);
2539 }
2540
2541 memory_accesses.ttae_cache = NULL;
2542
2543 /* Initialize bb_loop_postorder with a mapping from loop->num to
2544 its postorder index. */
2545 i = 0;
2546 bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
2547 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2548 bb_loop_postorder[loop->num] = i++;
2549}
2550
2551/* Cleans up after the invariant motion pass. */
2552
2553static void
2554tree_ssa_lim_finalize (void)
2555{
2556 basic_block bb;
2557 unsigned i;
2558 im_mem_ref *ref;
2559
2560 free_aux_for_edges ();
2561
2562 FOR_EACH_BB_FN (bb, cfun)
2563 SET_ALWAYS_EXECUTED_IN (bb, NULL);
2564
2565 bitmap_obstack_release (&lim_bitmap_obstack);
2566 delete lim_aux_data_map;
2567
2568 delete memory_accesses.refs;
2569 memory_accesses.refs = NULL;
2570
2571 FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
2572 memref_free (ref);
2573 memory_accesses.refs_list.release ();
2574 obstack_free (&mem_ref_obstack, NULL);
2575
2576 memory_accesses.refs_in_loop.release ();
2577 memory_accesses.refs_stored_in_loop.release ();
2578 memory_accesses.all_refs_stored_in_loop.release ();
2579
2580 if (memory_accesses.ttae_cache)
2581 free_affine_expand_cache (&memory_accesses.ttae_cache);
2582
2583 free (bb_loop_postorder);
2584}
2585
2586/* Moves invariants from loops. Only "expensive" invariants are moved out --
2587 i.e. those that are likely to be win regardless of the register pressure. */
2588
2589static unsigned int
2590tree_ssa_lim (void)
2591{
2592 unsigned int todo;
2593
2594 tree_ssa_lim_initialize ();
2595
2596 /* Gathers information about memory accesses in the loops. */
2597 analyze_memory_references ();
2598
2599 /* Fills ALWAYS_EXECUTED_IN information for basic blocks. */
2600 fill_always_executed_in ();
2601
2602 /* For each statement determine the outermost loop in that it is
2603 invariant and cost for computing the invariant. */
2604 invariantness_dom_walker (CDI_DOMINATORS)
2605 .walk (cfun->cfg->x_entry_block_ptr);
2606
2607 /* Execute store motion. Force the necessary invariants to be moved
2608 out of the loops as well. */
2609 store_motion ();
2610
2611 /* Move the expressions that are expensive enough. */
2612 todo = move_computations ();
2613
2614 tree_ssa_lim_finalize ();
2615
2616 return todo;
2617}
2618
2619/* Loop invariant motion pass. */
2620
2621namespace {
2622
2623const pass_data pass_data_lim =
2624{
2625 GIMPLE_PASS, /* type */
2626 "lim", /* name */
2627 OPTGROUP_LOOP, /* optinfo_flags */
2628 TV_LIM, /* tv_id */
2629 PROP_cfg, /* properties_required */
2630 0, /* properties_provided */
2631 0, /* properties_destroyed */
2632 0, /* todo_flags_start */
2633 0, /* todo_flags_finish */
2634};
2635
2636class pass_lim : public gimple_opt_pass
2637{
2638public:
2639 pass_lim (gcc::context *ctxt)
2640 : gimple_opt_pass (pass_data_lim, ctxt)
2641 {}
2642
2643 /* opt_pass methods: */
2644 opt_pass * clone () { return new pass_lim (m_ctxt); }
2645 virtual bool gate (function *) { return flag_tree_loop_im != 0; }
2646 virtual unsigned int execute (function *);
2647
2648}; // class pass_lim
2649
2650unsigned int
2651pass_lim::execute (function *fun)
2652{
2653 bool in_loop_pipeline = scev_initialized_p ();
2654 if (!in_loop_pipeline)
2655 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
2656
2657 if (number_of_loops (fun) <= 1)
2658 return 0;
2659 unsigned int todo = tree_ssa_lim ();
2660
2661 if (!in_loop_pipeline)
2662 loop_optimizer_finalize ();
2663 return todo;
2664}
2665
2666} // anon namespace
2667
2668gimple_opt_pass *
2669make_pass_lim (gcc::context *ctxt)
2670{
2671 return new pass_lim (ctxt);
2672}
2673
2674
2675