Import gcc-4.4.2
[dragonfly.git] / contrib / gcc-4.4 / gcc / tree-ssa-loop-im.c
CommitLineData
c251ad9e
SS
1/* Loop invariant motion.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
3 Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by the
9Free Software Foundation; either version 3, or (at your option) any
10later version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT
13ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "hard-reg-set.h"
29#include "basic-block.h"
30#include "output.h"
31#include "diagnostic.h"
32#include "tree-flow.h"
33#include "tree-dump.h"
34#include "timevar.h"
35#include "cfgloop.h"
36#include "domwalk.h"
37#include "params.h"
38#include "tree-pass.h"
39#include "flags.h"
40#include "real.h"
41#include "hashtab.h"
42#include "tree-affine.h"
43#include "pointer-set.h"
44#include "tree-ssa-propagate.h"
45
46/* TODO: Support for predicated code motion. I.e.
47
48 while (1)
49 {
50 if (cond)
51 {
52 a = inv;
53 something;
54 }
55 }
56
57 Where COND and INV are is invariants, but evaluating INV may trap or be
58 invalid from some other reason if !COND. This may be transformed to
59
60 if (cond)
61 a = inv;
62 while (1)
63 {
64 if (cond)
65 something;
66 } */
67
68/* A type for the list of statements that have to be moved in order to be able
69 to hoist an invariant computation. */
70
71struct depend
72{
73 gimple stmt;
74 struct depend *next;
75};
76
77/* The auxiliary data kept for each statement. */
78
79struct lim_aux_data
80{
81 struct loop *max_loop; /* The outermost loop in that the statement
82 is invariant. */
83
84 struct loop *tgt_loop; /* The loop out of that we want to move the
85 invariant. */
86
87 struct loop *always_executed_in;
88 /* The outermost loop for that we are sure
89 the statement is executed if the loop
90 is entered. */
91
92 unsigned cost; /* Cost of the computation performed by the
93 statement. */
94
95 struct depend *depends; /* List of statements that must be also hoisted
96 out of the loop when this statement is
97 hoisted; i.e. those that define the operands
98 of the statement and are inside of the
99 MAX_LOOP loop. */
100};
101
102/* Maps statements to their lim_aux_data. */
103
104static struct pointer_map_t *lim_aux_data_map;
105
106/* Description of a memory reference location. */
107
108typedef struct mem_ref_loc
109{
110 tree *ref; /* The reference itself. */
111 gimple stmt; /* The statement in that it occurs. */
112} *mem_ref_loc_p;
113
114DEF_VEC_P(mem_ref_loc_p);
115DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
116
117/* The list of memory reference locations in a loop. */
118
119typedef struct mem_ref_locs
120{
121 VEC (mem_ref_loc_p, heap) *locs;
122} *mem_ref_locs_p;
123
124DEF_VEC_P(mem_ref_locs_p);
125DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
126
127/* Description of a memory reference. */
128
129typedef struct mem_ref
130{
131 tree mem; /* The memory itself. */
132 unsigned id; /* ID assigned to the memory reference
133 (its index in memory_accesses.refs_list) */
134 hashval_t hash; /* Its hash value. */
135 bitmap stored; /* The set of loops in that this memory location
136 is stored to. */
137 VEC (mem_ref_locs_p, heap) *accesses_in_loop;
138 /* The locations of the accesses. Vector
139 indexed by the loop number. */
140 bitmap vops; /* Vops corresponding to this memory
141 location. */
142
143 /* The following sets are computed on demand. We keep both set and
144 its complement, so that we know whether the information was
145 already computed or not. */
146 bitmap indep_loop; /* The set of loops in that the memory
147 reference is independent, meaning:
148 If it is stored in the loop, this store
149 is independent on all other loads and
150 stores.
151 If it is only loaded, then it is independent
152 on all stores in the loop. */
153 bitmap dep_loop; /* The complement of INDEP_LOOP. */
154
155 bitmap indep_ref; /* The set of memory references on that
156 this reference is independent. */
157 bitmap dep_ref; /* The complement of DEP_REF. */
158} *mem_ref_p;
159
160DEF_VEC_P(mem_ref_p);
161DEF_VEC_ALLOC_P(mem_ref_p, heap);
162
163DEF_VEC_P(bitmap);
164DEF_VEC_ALLOC_P(bitmap, heap);
165
166DEF_VEC_P(htab_t);
167DEF_VEC_ALLOC_P(htab_t, heap);
168
169/* Description of memory accesses in loops. */
170
171static struct
172{
173 /* The hash table of memory references accessed in loops. */
174 htab_t refs;
175
176 /* The list of memory references. */
177 VEC (mem_ref_p, heap) *refs_list;
178
179 /* The set of memory references accessed in each loop. */
180 VEC (bitmap, heap) *refs_in_loop;
181
182 /* The set of memory references accessed in each loop, including
183 subloops. */
184 VEC (bitmap, heap) *all_refs_in_loop;
185
186 /* The set of virtual operands clobbered in a given loop. */
187 VEC (bitmap, heap) *clobbered_vops;
188
189 /* Map from the pair (loop, virtual operand) to the set of refs that
190 touch the virtual operand in the loop. */
191 VEC (htab_t, heap) *vop_ref_map;
192
193 /* Cache for expanding memory addresses. */
194 struct pointer_map_t *ttae_cache;
195} memory_accesses;
196
197static bool ref_indep_loop_p (struct loop *, mem_ref_p);
198
199/* Minimum cost of an expensive expression. */
200#define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
201
202/* The outermost loop for that execution of the header guarantees that the
203 block will be executed. */
204#define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
205
206static struct lim_aux_data *
207init_lim_data (gimple stmt)
208{
209 void **p = pointer_map_insert (lim_aux_data_map, stmt);
210
211 *p = XCNEW (struct lim_aux_data);
212 return (struct lim_aux_data *) *p;
213}
214
215static struct lim_aux_data *
216get_lim_data (gimple stmt)
217{
218 void **p = pointer_map_contains (lim_aux_data_map, stmt);
219 if (!p)
220 return NULL;
221
222 return (struct lim_aux_data *) *p;
223}
224
225/* Releases the memory occupied by DATA. */
226
227static void
228free_lim_aux_data (struct lim_aux_data *data)
229{
230 struct depend *dep, *next;
231
232 for (dep = data->depends; dep; dep = next)
233 {
234 next = dep->next;
235 free (dep);
236 }
237 free (data);
238}
239
240static void
241clear_lim_data (gimple stmt)
242{
243 void **p = pointer_map_contains (lim_aux_data_map, stmt);
244 if (!p)
245 return;
246
247 free_lim_aux_data ((struct lim_aux_data *) *p);
248 *p = NULL;
249}
250
251/* Calls CBCK for each index in memory reference ADDR_P. There are two
252 kinds situations handled; in each of these cases, the memory reference
253 and DATA are passed to the callback:
254
255 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
256 pass the pointer to the index to the callback.
257
258 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
259 pointer to addr to the callback.
260
261 If the callback returns false, the whole search stops and false is returned.
262 Otherwise the function returns true after traversing through the whole
263 reference *ADDR_P. */
264
265bool
266for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
267{
268 tree *nxt, *idx;
269
270 for (; ; addr_p = nxt)
271 {
272 switch (TREE_CODE (*addr_p))
273 {
274 case SSA_NAME:
275 return cbck (*addr_p, addr_p, data);
276
277 case MISALIGNED_INDIRECT_REF:
278 case ALIGN_INDIRECT_REF:
279 case INDIRECT_REF:
280 nxt = &TREE_OPERAND (*addr_p, 0);
281 return cbck (*addr_p, nxt, data);
282
283 case BIT_FIELD_REF:
284 case VIEW_CONVERT_EXPR:
285 case REALPART_EXPR:
286 case IMAGPART_EXPR:
287 nxt = &TREE_OPERAND (*addr_p, 0);
288 break;
289
290 case COMPONENT_REF:
291 /* If the component has varying offset, it behaves like index
292 as well. */
293 idx = &TREE_OPERAND (*addr_p, 2);
294 if (*idx
295 && !cbck (*addr_p, idx, data))
296 return false;
297
298 nxt = &TREE_OPERAND (*addr_p, 0);
299 break;
300
301 case ARRAY_REF:
302 case ARRAY_RANGE_REF:
303 nxt = &TREE_OPERAND (*addr_p, 0);
304 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
305 return false;
306 break;
307
308 case VAR_DECL:
309 case PARM_DECL:
310 case STRING_CST:
311 case RESULT_DECL:
312 case VECTOR_CST:
313 case COMPLEX_CST:
314 case INTEGER_CST:
315 case REAL_CST:
316 case FIXED_CST:
317 case CONSTRUCTOR:
318 return true;
319
320 case ADDR_EXPR:
321 gcc_assert (is_gimple_min_invariant (*addr_p));
322 return true;
323
324 case TARGET_MEM_REF:
325 idx = &TMR_BASE (*addr_p);
326 if (*idx
327 && !cbck (*addr_p, idx, data))
328 return false;
329 idx = &TMR_INDEX (*addr_p);
330 if (*idx
331 && !cbck (*addr_p, idx, data))
332 return false;
333 return true;
334
335 default:
336 gcc_unreachable ();
337 }
338 }
339}
340
341/* If it is possible to hoist the statement STMT unconditionally,
342 returns MOVE_POSSIBLE.
343 If it is possible to hoist the statement STMT, but we must avoid making
344 it executed if it would not be executed in the original program (e.g.
345 because it may trap), return MOVE_PRESERVE_EXECUTION.
346 Otherwise return MOVE_IMPOSSIBLE. */
347
348enum move_pos
349movement_possibility (gimple stmt)
350{
351 tree lhs;
352 enum move_pos ret = MOVE_POSSIBLE;
353
354 if (flag_unswitch_loops
355 && gimple_code (stmt) == GIMPLE_COND)
356 {
357 /* If we perform unswitching, force the operands of the invariant
358 condition to be moved out of the loop. */
359 return MOVE_POSSIBLE;
360 }
361
362 if (gimple_get_lhs (stmt) == NULL_TREE)
363 return MOVE_IMPOSSIBLE;
364
365 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
366 return MOVE_IMPOSSIBLE;
367
368 if (stmt_ends_bb_p (stmt)
369 || gimple_has_volatile_ops (stmt)
370 || gimple_has_side_effects (stmt)
371 || stmt_could_throw_p (stmt))
372 return MOVE_IMPOSSIBLE;
373
374 if (is_gimple_call (stmt))
375 {
376 /* While pure or const call is guaranteed to have no side effects, we
377 cannot move it arbitrarily. Consider code like
378
379 char *s = something ();
380
381 while (1)
382 {
383 if (s)
384 t = strlen (s);
385 else
386 t = 0;
387 }
388
389 Here the strlen call cannot be moved out of the loop, even though
390 s is invariant. In addition to possibly creating a call with
391 invalid arguments, moving out a function call that is not executed
392 may cause performance regressions in case the call is costly and
393 not executed at all. */
394 ret = MOVE_PRESERVE_EXECUTION;
395 lhs = gimple_call_lhs (stmt);
396 }
397 else if (is_gimple_assign (stmt))
398 lhs = gimple_assign_lhs (stmt);
399 else
400 return MOVE_IMPOSSIBLE;
401
402 if (TREE_CODE (lhs) == SSA_NAME
403 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
404 return MOVE_IMPOSSIBLE;
405
406 if (TREE_CODE (lhs) != SSA_NAME
407 || gimple_could_trap_p (stmt))
408 return MOVE_PRESERVE_EXECUTION;
409
410 return ret;
411}
412
413/* Suppose that operand DEF is used inside the LOOP. Returns the outermost
414 loop to that we could move the expression using DEF if it did not have
415 other operands, i.e. the outermost loop enclosing LOOP in that the value
416 of DEF is invariant. */
417
418static struct loop *
419outermost_invariant_loop (tree def, struct loop *loop)
420{
421 gimple def_stmt;
422 basic_block def_bb;
423 struct loop *max_loop;
424 struct lim_aux_data *lim_data;
425
426 if (!def)
427 return superloop_at_depth (loop, 1);
428
429 if (TREE_CODE (def) != SSA_NAME)
430 {
431 gcc_assert (is_gimple_min_invariant (def));
432 return superloop_at_depth (loop, 1);
433 }
434
435 def_stmt = SSA_NAME_DEF_STMT (def);
436 def_bb = gimple_bb (def_stmt);
437 if (!def_bb)
438 return superloop_at_depth (loop, 1);
439
440 max_loop = find_common_loop (loop, def_bb->loop_father);
441
442 lim_data = get_lim_data (def_stmt);
443 if (lim_data != NULL && lim_data->max_loop != NULL)
444 max_loop = find_common_loop (max_loop,
445 loop_outer (lim_data->max_loop));
446 if (max_loop == loop)
447 return NULL;
448 max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
449
450 return max_loop;
451}
452
453/* DATA is a structure containing information associated with a statement
454 inside LOOP. DEF is one of the operands of this statement.
455
456 Find the outermost loop enclosing LOOP in that value of DEF is invariant
457 and record this in DATA->max_loop field. If DEF itself is defined inside
458 this loop as well (i.e. we need to hoist it out of the loop if we want
459 to hoist the statement represented by DATA), record the statement in that
460 DEF is defined to the DATA->depends list. Additionally if ADD_COST is true,
461 add the cost of the computation of DEF to the DATA->cost.
462
463 If DEF is not invariant in LOOP, return false. Otherwise return TRUE. */
464
465static bool
466add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
467 bool add_cost)
468{
469 gimple def_stmt = SSA_NAME_DEF_STMT (def);
470 basic_block def_bb = gimple_bb (def_stmt);
471 struct loop *max_loop;
472 struct depend *dep;
473 struct lim_aux_data *def_data;
474
475 if (!def_bb)
476 return true;
477
478 max_loop = outermost_invariant_loop (def, loop);
479 if (!max_loop)
480 return false;
481
482 if (flow_loop_nested_p (data->max_loop, max_loop))
483 data->max_loop = max_loop;
484
485 def_data = get_lim_data (def_stmt);
486 if (!def_data)
487 return true;
488
489 if (add_cost
490 /* Only add the cost if the statement defining DEF is inside LOOP,
491 i.e. if it is likely that by moving the invariants dependent
492 on it, we will be able to avoid creating a new register for
493 it (since it will be only used in these dependent invariants). */
494 && def_bb->loop_father == loop)
495 data->cost += def_data->cost;
496
497 dep = XNEW (struct depend);
498 dep->stmt = def_stmt;
499 dep->next = data->depends;
500 data->depends = dep;
501
502 return true;
503}
504
505/* Returns an estimate for a cost of statement STMT. TODO -- the values here
506 are just ad-hoc constants. The estimates should be based on target-specific
507 values. */
508
509static unsigned
510stmt_cost (gimple stmt)
511{
512 tree fndecl;
513 unsigned cost = 1;
514
515 /* Always try to create possibilities for unswitching. */
516 if (gimple_code (stmt) == GIMPLE_COND)
517 return LIM_EXPENSIVE;
518
519 /* Hoisting memory references out should almost surely be a win. */
520 if (gimple_references_memory_p (stmt))
521 cost += 20;
522
523 if (is_gimple_call (stmt))
524 {
525 /* We should be hoisting calls if possible. */
526
527 /* Unless the call is a builtin_constant_p; this always folds to a
528 constant, so moving it is useless. */
529 fndecl = gimple_call_fndecl (stmt);
530 if (fndecl
531 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
532 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_CONSTANT_P)
533 return 0;
534
535 return cost + 20;
536 }
537
538 if (gimple_code (stmt) != GIMPLE_ASSIGN)
539 return cost;
540
541 switch (gimple_assign_rhs_code (stmt))
542 {
543 case MULT_EXPR:
544 case TRUNC_DIV_EXPR:
545 case CEIL_DIV_EXPR:
546 case FLOOR_DIV_EXPR:
547 case ROUND_DIV_EXPR:
548 case EXACT_DIV_EXPR:
549 case CEIL_MOD_EXPR:
550 case FLOOR_MOD_EXPR:
551 case ROUND_MOD_EXPR:
552 case TRUNC_MOD_EXPR:
553 case RDIV_EXPR:
554 /* Division and multiplication are usually expensive. */
555 cost += 20;
556 break;
557
558 case LSHIFT_EXPR:
559 case RSHIFT_EXPR:
560 cost += 20;
561 break;
562
563 default:
564 break;
565 }
566
567 return cost;
568}
569
570/* Finds the outermost loop between OUTER and LOOP in that the memory reference
571 REF is independent. If REF is not independent in LOOP, NULL is returned
572 instead. */
573
574static struct loop *
575outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
576{
577 struct loop *aloop;
578
579 if (bitmap_bit_p (ref->stored, loop->num))
580 return NULL;
581
582 for (aloop = outer;
583 aloop != loop;
584 aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
585 if (!bitmap_bit_p (ref->stored, aloop->num)
586 && ref_indep_loop_p (aloop, ref))
587 return aloop;
588
589 if (ref_indep_loop_p (loop, ref))
590 return loop;
591 else
592 return NULL;
593}
594
595/* If there is a simple load or store to a memory reference in STMT, returns
596 the location of the memory reference, and sets IS_STORE according to whether
597 it is a store or load. Otherwise, returns NULL. */
598
599static tree *
600simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
601{
602 tree *lhs;
603 enum tree_code code;
604
605 /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
606 if (gimple_code (stmt) != GIMPLE_ASSIGN)
607 return NULL;
608
609 code = gimple_assign_rhs_code (stmt);
610
611 lhs = gimple_assign_lhs_ptr (stmt);
612
613 if (TREE_CODE (*lhs) == SSA_NAME)
614 {
615 if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
616 || !is_gimple_addressable (gimple_assign_rhs1 (stmt)))
617 return NULL;
618
619 *is_store = false;
620 return gimple_assign_rhs1_ptr (stmt);
621 }
622 else if (code == SSA_NAME
623 || (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
624 && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
625 {
626 *is_store = true;
627 return lhs;
628 }
629 else
630 return NULL;
631}
632
633/* Returns the memory reference contained in STMT. */
634
635static mem_ref_p
636mem_ref_in_stmt (gimple stmt)
637{
638 bool store;
639 tree *mem = simple_mem_ref_in_stmt (stmt, &store);
640 hashval_t hash;
641 mem_ref_p ref;
642
643 if (!mem)
644 return NULL;
645 gcc_assert (!store);
646
647 hash = iterative_hash_expr (*mem, 0);
648 ref = (mem_ref_p) htab_find_with_hash (memory_accesses.refs, *mem, hash);
649
650 gcc_assert (ref != NULL);
651 return ref;
652}
653
654/* Determine the outermost loop to that it is possible to hoist a statement
655 STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
656 the outermost loop in that the value computed by STMT is invariant.
657 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
658 we preserve the fact whether STMT is executed. It also fills other related
659 information to LIM_DATA (STMT).
660
661 The function returns false if STMT cannot be hoisted outside of the loop it
662 is defined in, and true otherwise. */
663
664static bool
665determine_max_movement (gimple stmt, bool must_preserve_exec)
666{
667 basic_block bb = gimple_bb (stmt);
668 struct loop *loop = bb->loop_father;
669 struct loop *level;
670 struct lim_aux_data *lim_data = get_lim_data (stmt);
671 tree val;
672 ssa_op_iter iter;
673
674 if (must_preserve_exec)
675 level = ALWAYS_EXECUTED_IN (bb);
676 else
677 level = superloop_at_depth (loop, 1);
678 lim_data->max_loop = level;
679
680 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
681 if (!add_dependency (val, lim_data, loop, true))
682 return false;
683
684 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
685 {
686 mem_ref_p ref = mem_ref_in_stmt (stmt);
687
688 if (ref)
689 {
690 lim_data->max_loop
691 = outermost_indep_loop (lim_data->max_loop, loop, ref);
692 if (!lim_data->max_loop)
693 return false;
694 }
695 else
696 {
697 FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
698 {
699 if (!add_dependency (val, lim_data, loop, false))
700 return false;
701 }
702 }
703 }
704
705 lim_data->cost += stmt_cost (stmt);
706
707 return true;
708}
709
710/* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
711 and that one of the operands of this statement is computed by STMT.
712 Ensure that STMT (together with all the statements that define its
713 operands) is hoisted at least out of the loop LEVEL. */
714
715static void
716set_level (gimple stmt, struct loop *orig_loop, struct loop *level)
717{
718 struct loop *stmt_loop = gimple_bb (stmt)->loop_father;
719 struct depend *dep;
720 struct lim_aux_data *lim_data;
721
722 stmt_loop = find_common_loop (orig_loop, stmt_loop);
723 lim_data = get_lim_data (stmt);
724 if (lim_data != NULL && lim_data->tgt_loop != NULL)
725 stmt_loop = find_common_loop (stmt_loop,
726 loop_outer (lim_data->tgt_loop));
727 if (flow_loop_nested_p (stmt_loop, level))
728 return;
729
730 gcc_assert (level == lim_data->max_loop
731 || flow_loop_nested_p (lim_data->max_loop, level));
732
733 lim_data->tgt_loop = level;
734 for (dep = lim_data->depends; dep; dep = dep->next)
735 set_level (dep->stmt, orig_loop, level);
736}
737
738/* Determines an outermost loop from that we want to hoist the statement STMT.
739 For now we chose the outermost possible loop. TODO -- use profiling
740 information to set it more sanely. */
741
742static void
743set_profitable_level (gimple stmt)
744{
745 set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
746}
747
748/* Returns true if STMT is a call that has side effects. */
749
750static bool
751nonpure_call_p (gimple stmt)
752{
753 if (gimple_code (stmt) != GIMPLE_CALL)
754 return false;
755
756 return gimple_has_side_effects (stmt);
757}
758
759/* Rewrite a/b to a*(1/b). Return the invariant stmt to process. */
760
761static gimple
762rewrite_reciprocal (gimple_stmt_iterator *bsi)
763{
764 gimple stmt, stmt1, stmt2;
765 tree var, name, lhs, type;
766 tree real_one;
767
768 stmt = gsi_stmt (*bsi);
769 lhs = gimple_assign_lhs (stmt);
770 type = TREE_TYPE (lhs);
771
772 var = create_tmp_var (type, "reciptmp");
773 add_referenced_var (var);
774 DECL_GIMPLE_REG_P (var) = 1;
775
776 /* For vectors, create a VECTOR_CST full of 1's. */
777 if (TREE_CODE (type) == VECTOR_TYPE)
778 {
779 int i, len;
780 tree list = NULL_TREE;
781 real_one = build_real (TREE_TYPE (type), dconst1);
782 len = TYPE_VECTOR_SUBPARTS (type);
783 for (i = 0; i < len; i++)
784 list = tree_cons (NULL, real_one, list);
785 real_one = build_vector (type, list);
786 }
787 else
788 real_one = build_real (type, dconst1);
789
790 stmt1 = gimple_build_assign_with_ops (RDIV_EXPR,
791 var, real_one, gimple_assign_rhs2 (stmt));
792 name = make_ssa_name (var, stmt1);
793 gimple_assign_set_lhs (stmt1, name);
794
795 stmt2 = gimple_build_assign_with_ops (MULT_EXPR, lhs, name,
796 gimple_assign_rhs1 (stmt));
797
798 /* Replace division stmt with reciprocal and multiply stmts.
799 The multiply stmt is not invariant, so update iterator
800 and avoid rescanning. */
801 gsi_replace (bsi, stmt1, true);
802 gsi_insert_after (bsi, stmt2, GSI_NEW_STMT);
803
804 /* Continue processing with invariant reciprocal statement. */
805 return stmt1;
806}
807
808/* Check if the pattern at *BSI is a bittest of the form
809 (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0. */
810
811static gimple
812rewrite_bittest (gimple_stmt_iterator *bsi)
813{
814 gimple stmt, use_stmt, stmt1, stmt2;
815 tree lhs, var, name, t, a, b;
816 use_operand_p use;
817
818 stmt = gsi_stmt (*bsi);
819 lhs = gimple_assign_lhs (stmt);
820
821 /* Verify that the single use of lhs is a comparison against zero. */
822 if (TREE_CODE (lhs) != SSA_NAME
823 || !single_imm_use (lhs, &use, &use_stmt)
824 || gimple_code (use_stmt) != GIMPLE_COND)
825 return stmt;
826 if (gimple_cond_lhs (use_stmt) != lhs
827 || (gimple_cond_code (use_stmt) != NE_EXPR
828 && gimple_cond_code (use_stmt) != EQ_EXPR)
829 || !integer_zerop (gimple_cond_rhs (use_stmt)))
830 return stmt;
831
832 /* Get at the operands of the shift. The rhs is TMP1 & 1. */
833 stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
834 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
835 return stmt;
836
837 /* There is a conversion in between possibly inserted by fold. */
838 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
839 {
840 t = gimple_assign_rhs1 (stmt1);
841 if (TREE_CODE (t) != SSA_NAME
842 || !has_single_use (t))
843 return stmt;
844 stmt1 = SSA_NAME_DEF_STMT (t);
845 if (gimple_code (stmt1) != GIMPLE_ASSIGN)
846 return stmt;
847 }
848
849 /* Verify that B is loop invariant but A is not. Verify that with
850 all the stmt walking we are still in the same loop. */
851 if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
852 || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
853 return stmt;
854
855 a = gimple_assign_rhs1 (stmt1);
856 b = gimple_assign_rhs2 (stmt1);
857
858 if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
859 && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
860 {
861 /* 1 << B */
862 var = create_tmp_var (TREE_TYPE (a), "shifttmp");
863 add_referenced_var (var);
864 t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
865 build_int_cst (TREE_TYPE (a), 1), b);
866 stmt1 = gimple_build_assign (var, t);
867 name = make_ssa_name (var, stmt1);
868 gimple_assign_set_lhs (stmt1, name);
869
870 /* A & (1 << B) */
871 t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
872 stmt2 = gimple_build_assign (var, t);
873 name = make_ssa_name (var, stmt2);
874 gimple_assign_set_lhs (stmt2, name);
875
876 /* Replace the SSA_NAME we compare against zero. Adjust
877 the type of zero accordingly. */
878 SET_USE (use, name);
879 gimple_cond_set_rhs (use_stmt, build_int_cst_type (TREE_TYPE (name), 0));
880
881 gsi_insert_before (bsi, stmt1, GSI_SAME_STMT);
882 gsi_replace (bsi, stmt2, true);
883
884 return stmt1;
885 }
886
887 return stmt;
888}
889
890
891/* Determine the outermost loops in that statements in basic block BB are
892 invariant, and record them to the LIM_DATA associated with the statements.
893 Callback for walk_dominator_tree. */
894
895static void
896determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
897 basic_block bb)
898{
899 enum move_pos pos;
900 gimple_stmt_iterator bsi;
901 gimple stmt;
902 bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
903 struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
904 struct lim_aux_data *lim_data;
905
906 if (!loop_outer (bb->loop_father))
907 return;
908
909 if (dump_file && (dump_flags & TDF_DETAILS))
910 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
911 bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
912
913 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
914 {
915 stmt = gsi_stmt (bsi);
916
917 pos = movement_possibility (stmt);
918 if (pos == MOVE_IMPOSSIBLE)
919 {
920 if (nonpure_call_p (stmt))
921 {
922 maybe_never = true;
923 outermost = NULL;
924 }
925 /* Make sure to note always_executed_in for stores to make
926 store-motion work. */
927 else if (stmt_makes_single_store (stmt))
928 {
929 struct lim_aux_data *lim_data = init_lim_data (stmt);
930 lim_data->always_executed_in = outermost;
931 }
932 continue;
933 }
934
935 if (is_gimple_assign (stmt)
936 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
937 == GIMPLE_BINARY_RHS))
938 {
939 tree op0 = gimple_assign_rhs1 (stmt);
940 tree op1 = gimple_assign_rhs2 (stmt);
941 struct loop *ol1 = outermost_invariant_loop (op1,
942 loop_containing_stmt (stmt));
943
944 /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
945 to be hoisted out of loop, saving expensive divide. */
946 if (pos == MOVE_POSSIBLE
947 && gimple_assign_rhs_code (stmt) == RDIV_EXPR
948 && flag_unsafe_math_optimizations
949 && !flag_trapping_math
950 && ol1 != NULL
951 && outermost_invariant_loop (op0, ol1) == NULL)
952 stmt = rewrite_reciprocal (&bsi);
953
954 /* If the shift count is invariant, convert (A >> B) & 1 to
955 A & (1 << B) allowing the bit mask to be hoisted out of the loop
956 saving an expensive shift. */
957 if (pos == MOVE_POSSIBLE
958 && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
959 && integer_onep (op1)
960 && TREE_CODE (op0) == SSA_NAME
961 && has_single_use (op0))
962 stmt = rewrite_bittest (&bsi);
963 }
964
965 lim_data = init_lim_data (stmt);
966 lim_data->always_executed_in = outermost;
967
968 if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
969 continue;
970
971 if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
972 {
973 lim_data->max_loop = NULL;
974 continue;
975 }
976
977 if (dump_file && (dump_flags & TDF_DETAILS))
978 {
979 print_gimple_stmt (dump_file, stmt, 2, 0);
980 fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
981 loop_depth (lim_data->max_loop),
982 lim_data->cost);
983 }
984
985 if (lim_data->cost >= LIM_EXPENSIVE)
986 set_profitable_level (stmt);
987 }
988}
989
990/* For each statement determines the outermost loop in that it is invariant,
991 statements on whose motion it depends and the cost of the computation.
992 This information is stored to the LIM_DATA structure associated with
993 each statement. */
994
995static void
996determine_invariantness (void)
997{
998 struct dom_walk_data walk_data;
999
1000 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1001 walk_data.dom_direction = CDI_DOMINATORS;
1002 walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
1003
1004 init_walk_dominator_tree (&walk_data);
1005 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1006 fini_walk_dominator_tree (&walk_data);
1007}
1008
1009/* Hoist the statements in basic block BB out of the loops prescribed by
1010 data stored in LIM_DATA structures associated with each statement. Callback
1011 for walk_dominator_tree. */
1012
1013static void
1014move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
1015 basic_block bb)
1016{
1017 struct loop *level;
1018 gimple_stmt_iterator bsi;
1019 gimple stmt;
1020 unsigned cost = 0;
1021 struct lim_aux_data *lim_data;
1022
1023 if (!loop_outer (bb->loop_father))
1024 return;
1025
1026 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1027 {
1028 stmt = gsi_stmt (bsi);
1029
1030 lim_data = get_lim_data (stmt);
1031 if (lim_data == NULL)
1032 {
1033 gsi_next (&bsi);
1034 continue;
1035 }
1036
1037 cost = lim_data->cost;
1038 level = lim_data->tgt_loop;
1039 clear_lim_data (stmt);
1040
1041 if (!level)
1042 {
1043 gsi_next (&bsi);
1044 continue;
1045 }
1046
1047 /* We do not really want to move conditionals out of the loop; we just
1048 placed it here to force its operands to be moved if necessary. */
1049 if (gimple_code (stmt) == GIMPLE_COND)
1050 continue;
1051
1052 if (dump_file && (dump_flags & TDF_DETAILS))
1053 {
1054 fprintf (dump_file, "Moving statement\n");
1055 print_gimple_stmt (dump_file, stmt, 0, 0);
1056 fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1057 cost, level->num);
1058 }
1059
1060 mark_virtual_ops_for_renaming (stmt);
1061 gsi_insert_on_edge (loop_preheader_edge (level), stmt);
1062 gsi_remove (&bsi, false);
1063 }
1064}
1065
1066/* Hoist the statements out of the loops prescribed by data stored in
1067 LIM_DATA structures associated with each statement.*/
1068
1069static void
1070move_computations (void)
1071{
1072 struct dom_walk_data walk_data;
1073
1074 memset (&walk_data, 0, sizeof (struct dom_walk_data));
1075 walk_data.dom_direction = CDI_DOMINATORS;
1076 walk_data.before_dom_children_before_stmts = move_computations_stmt;
1077
1078 init_walk_dominator_tree (&walk_data);
1079 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1080 fini_walk_dominator_tree (&walk_data);
1081
1082 gsi_commit_edge_inserts ();
1083 if (need_ssa_update_p ())
1084 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1085}
1086
1087/* Checks whether the statement defining variable *INDEX can be hoisted
1088 out of the loop passed in DATA. Callback for for_each_index. */
1089
1090static bool
1091may_move_till (tree ref, tree *index, void *data)
1092{
1093 struct loop *loop = (struct loop *) data, *max_loop;
1094
1095 /* If REF is an array reference, check also that the step and the lower
1096 bound is invariant in LOOP. */
1097 if (TREE_CODE (ref) == ARRAY_REF)
1098 {
1099 tree step = TREE_OPERAND (ref, 3);
1100 tree lbound = TREE_OPERAND (ref, 2);
1101
1102 max_loop = outermost_invariant_loop (step, loop);
1103 if (!max_loop)
1104 return false;
1105
1106 max_loop = outermost_invariant_loop (lbound, loop);
1107 if (!max_loop)
1108 return false;
1109 }
1110
1111 max_loop = outermost_invariant_loop (*index, loop);
1112 if (!max_loop)
1113 return false;
1114
1115 return true;
1116}
1117
1118/* If OP is SSA NAME, force the statement that defines it to be
1119 moved out of the LOOP. ORIG_LOOP is the loop in that EXPR is used. */
1120
1121static void
1122force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1123{
1124 gimple stmt;
1125
1126 if (!op
1127 || is_gimple_min_invariant (op))
1128 return;
1129
1130 gcc_assert (TREE_CODE (op) == SSA_NAME);
1131
1132 stmt = SSA_NAME_DEF_STMT (op);
1133 if (gimple_nop_p (stmt))
1134 return;
1135
1136 set_level (stmt, orig_loop, loop);
1137}
1138
1139/* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1140 the LOOP. The reference REF is used in the loop ORIG_LOOP. Callback for
1141 for_each_index. */
1142
1143struct fmt_data
1144{
1145 struct loop *loop;
1146 struct loop *orig_loop;
1147};
1148
1149static bool
1150force_move_till (tree ref, tree *index, void *data)
1151{
1152 struct fmt_data *fmt_data = (struct fmt_data *) data;
1153
1154 if (TREE_CODE (ref) == ARRAY_REF)
1155 {
1156 tree step = TREE_OPERAND (ref, 3);
1157 tree lbound = TREE_OPERAND (ref, 2);
1158
1159 force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1160 force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1161 }
1162
1163 force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1164
1165 return true;
1166}
1167
1168/* A hash function for struct mem_ref object OBJ. */
1169
1170static hashval_t
1171memref_hash (const void *obj)
1172{
1173 const struct mem_ref *const mem = (const struct mem_ref *) obj;
1174
1175 return mem->hash;
1176}
1177
1178/* An equality function for struct mem_ref object OBJ1 with
1179 memory reference OBJ2. */
1180
1181static int
1182memref_eq (const void *obj1, const void *obj2)
1183{
1184 const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
1185
1186 return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
1187}
1188
1189/* Releases list of memory reference locations ACCS. */
1190
1191static void
1192free_mem_ref_locs (mem_ref_locs_p accs)
1193{
1194 unsigned i;
1195 mem_ref_loc_p loc;
1196
1197 if (!accs)
1198 return;
1199
1200 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1201 free (loc);
1202 VEC_free (mem_ref_loc_p, heap, accs->locs);
1203 free (accs);
1204}
1205
1206/* A function to free the mem_ref object OBJ. */
1207
1208static void
1209memref_free (void *obj)
1210{
1211 struct mem_ref *const mem = (struct mem_ref *) obj;
1212 unsigned i;
1213 mem_ref_locs_p accs;
1214
1215 BITMAP_FREE (mem->stored);
1216 BITMAP_FREE (mem->indep_loop);
1217 BITMAP_FREE (mem->dep_loop);
1218 BITMAP_FREE (mem->indep_ref);
1219 BITMAP_FREE (mem->dep_ref);
1220
1221 for (i = 0; VEC_iterate (mem_ref_locs_p, mem->accesses_in_loop, i, accs); i++)
1222 free_mem_ref_locs (accs);
1223 VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
1224
1225 BITMAP_FREE (mem->vops);
1226 free (mem);
1227}
1228
1229/* Allocates and returns a memory reference description for MEM whose hash
1230 value is HASH and id is ID. */
1231
1232static mem_ref_p
1233mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1234{
1235 mem_ref_p ref = XNEW (struct mem_ref);
1236 ref->mem = mem;
1237 ref->id = id;
1238 ref->hash = hash;
1239 ref->stored = BITMAP_ALLOC (NULL);
1240 ref->indep_loop = BITMAP_ALLOC (NULL);
1241 ref->dep_loop = BITMAP_ALLOC (NULL);
1242 ref->indep_ref = BITMAP_ALLOC (NULL);
1243 ref->dep_ref = BITMAP_ALLOC (NULL);
1244 ref->accesses_in_loop = NULL;
1245 ref->vops = BITMAP_ALLOC (NULL);
1246
1247 return ref;
1248}
1249
1250/* Allocates and returns the new list of locations. */
1251
1252static mem_ref_locs_p
1253mem_ref_locs_alloc (void)
1254{
1255 mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
1256 accs->locs = NULL;
1257 return accs;
1258}
1259
1260/* Records memory reference location *LOC in LOOP to the memory reference
1261 description REF. The reference occurs in statement STMT. */
1262
1263static void
1264record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
1265{
1266 mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
1267 mem_ref_locs_p accs;
1268 bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1269
1270 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1271 <= (unsigned) loop->num)
1272 VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
1273 loop->num + 1);
1274 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1275 if (!accs)
1276 {
1277 accs = mem_ref_locs_alloc ();
1278 VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
1279 }
1280
1281 aref->stmt = stmt;
1282 aref->ref = loc;
1283
1284 VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
1285 bitmap_set_bit (ril, ref->id);
1286}
1287
1288/* Marks reference REF as stored in LOOP. */
1289
1290static void
1291mark_ref_stored (mem_ref_p ref, struct loop *loop)
1292{
1293 for (;
1294 loop != current_loops->tree_root
1295 && !bitmap_bit_p (ref->stored, loop->num);
1296 loop = loop_outer (loop))
1297 bitmap_set_bit (ref->stored, loop->num);
1298}
1299
1300/* Gathers memory references in statement STMT in LOOP, storing the
1301 information about them in the memory_accesses structure. Marks
1302 the vops accessed through unrecognized statements there as
1303 well. */
1304
1305static void
1306gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1307{
1308 tree *mem = NULL;
1309 hashval_t hash;
1310 PTR *slot;
1311 mem_ref_p ref;
1312 ssa_op_iter oi;
1313 tree vname;
1314 bool is_stored;
1315 bitmap clvops;
1316 unsigned id;
1317
1318 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1319 return;
1320
1321 mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1322 if (!mem)
1323 goto fail;
1324
1325 hash = iterative_hash_expr (*mem, 0);
1326 slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
1327
1328 if (*slot)
1329 {
1330 ref = (mem_ref_p) *slot;
1331 id = ref->id;
1332 }
1333 else
1334 {
1335 id = VEC_length (mem_ref_p, memory_accesses.refs_list);
1336 ref = mem_ref_alloc (*mem, hash, id);
1337 VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
1338 *slot = ref;
1339
1340 if (dump_file && (dump_flags & TDF_DETAILS))
1341 {
1342 fprintf (dump_file, "Memory reference %u: ", id);
1343 print_generic_expr (dump_file, ref->mem, TDF_SLIM);
1344 fprintf (dump_file, "\n");
1345 }
1346 }
1347 if (is_stored)
1348 mark_ref_stored (ref, loop);
1349
1350 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1351 bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1352 record_mem_ref_loc (ref, loop, stmt, mem);
1353 return;
1354
1355fail:
1356 clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1357 FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi, SSA_OP_VIRTUAL_USES)
1358 bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
1359}
1360
1361/* Gathers memory references in loops. */
1362
1363static void
1364gather_mem_refs_in_loops (void)
1365{
1366 gimple_stmt_iterator bsi;
1367 basic_block bb;
1368 struct loop *loop;
1369 loop_iterator li;
1370 bitmap clvo, clvi;
1371 bitmap lrefs, alrefs, alrefso;
1372
1373 FOR_EACH_BB (bb)
1374 {
1375 loop = bb->loop_father;
1376 if (loop == current_loops->tree_root)
1377 continue;
1378
1379 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1380 gather_mem_refs_stmt (loop, gsi_stmt (bsi));
1381 }
1382
1383 /* Propagate the information about clobbered vops and accessed memory
1384 references up the loop hierarchy. */
1385 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1386 {
1387 lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1388 alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
1389 bitmap_ior_into (alrefs, lrefs);
1390
1391 if (loop_outer (loop) == current_loops->tree_root)
1392 continue;
1393
1394 clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1395 clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
1396 loop_outer (loop)->num);
1397 bitmap_ior_into (clvo, clvi);
1398
1399 alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1400 loop_outer (loop)->num);
1401 bitmap_ior_into (alrefso, alrefs);
1402 }
1403}
1404
1405/* Element of the hash table that maps vops to memory references. */
1406
1407struct vop_to_refs_elt
1408{
1409 /* DECL_UID of the vop. */
1410 unsigned uid;
1411
1412 /* List of the all references. */
1413 bitmap refs_all;
1414
1415 /* List of stored references. */
1416 bitmap refs_stored;
1417};
1418
1419/* A hash function for struct vop_to_refs_elt object OBJ. */
1420
1421static hashval_t
1422vtoe_hash (const void *obj)
1423{
1424 const struct vop_to_refs_elt *const vtoe =
1425 (const struct vop_to_refs_elt *) obj;
1426
1427 return vtoe->uid;
1428}
1429
1430/* An equality function for struct vop_to_refs_elt object OBJ1 with
1431 uid of a vop OBJ2. */
1432
1433static int
1434vtoe_eq (const void *obj1, const void *obj2)
1435{
1436 const struct vop_to_refs_elt *const vtoe =
1437 (const struct vop_to_refs_elt *) obj1;
1438 const unsigned *const uid = (const unsigned *) obj2;
1439
1440 return vtoe->uid == *uid;
1441}
1442
1443/* A function to free the struct vop_to_refs_elt object. */
1444
1445static void
1446vtoe_free (void *obj)
1447{
1448 struct vop_to_refs_elt *const vtoe =
1449 (struct vop_to_refs_elt *) obj;
1450
1451 BITMAP_FREE (vtoe->refs_all);
1452 BITMAP_FREE (vtoe->refs_stored);
1453 free (vtoe);
1454}
1455
1456/* Records REF to hashtable VOP_TO_REFS for the index VOP. STORED is true
1457 if the reference REF is stored. */
1458
1459static void
1460record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool stored)
1461{
1462 void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
1463 struct vop_to_refs_elt *vtoe;
1464
1465 if (!*slot)
1466 {
1467 vtoe = XNEW (struct vop_to_refs_elt);
1468 vtoe->uid = vop;
1469 vtoe->refs_all = BITMAP_ALLOC (NULL);
1470 vtoe->refs_stored = BITMAP_ALLOC (NULL);
1471 *slot = vtoe;
1472 }
1473 else
1474 vtoe = (struct vop_to_refs_elt *) *slot;
1475
1476 bitmap_set_bit (vtoe->refs_all, ref);
1477 if (stored)
1478 bitmap_set_bit (vtoe->refs_stored, ref);
1479}
1480
1481/* Returns the set of references that access VOP according to the table
1482 VOP_TO_REFS. */
1483
1484static bitmap
1485get_vop_accesses (htab_t vop_to_refs, unsigned vop)
1486{
1487 struct vop_to_refs_elt *const vtoe =
1488 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1489 return vtoe->refs_all;
1490}
1491
1492/* Returns the set of stores that access VOP according to the table
1493 VOP_TO_REFS. */
1494
1495static bitmap
1496get_vop_stores (htab_t vop_to_refs, unsigned vop)
1497{
1498 struct vop_to_refs_elt *const vtoe =
1499 (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1500 return vtoe->refs_stored;
1501}
1502
1503/* Adds REF to mapping from virtual operands to references in LOOP. */
1504
1505static void
1506add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
1507{
1508 htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1509 bool stored = bitmap_bit_p (ref->stored, loop->num);
1510 bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
1511 loop->num);
1512 bitmap_iterator bi;
1513 unsigned vop;
1514
1515 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
1516 {
1517 record_vop_access (map, vop, ref->id, stored);
1518 }
1519}
1520
1521/* Create a mapping from virtual operands to references that touch them
1522 in LOOP. */
1523
1524static void
1525create_vop_ref_mapping_loop (struct loop *loop)
1526{
1527 bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1528 struct loop *sloop;
1529 bitmap_iterator bi;
1530 unsigned i;
1531 mem_ref_p ref;
1532
1533 EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
1534 {
1535 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1536 for (sloop = loop; sloop != current_loops->tree_root; sloop = loop_outer (sloop))
1537 add_vop_ref_mapping (sloop, ref);
1538 }
1539}
1540
1541/* For each non-clobbered virtual operand and each loop, record the memory
1542 references in this loop that touch the operand. */
1543
1544static void
1545create_vop_ref_mapping (void)
1546{
1547 loop_iterator li;
1548 struct loop *loop;
1549
1550 FOR_EACH_LOOP (li, loop, 0)
1551 {
1552 create_vop_ref_mapping_loop (loop);
1553 }
1554}
1555
1556/* Gathers information about memory accesses in the loops. */
1557
1558static void
1559analyze_memory_references (void)
1560{
1561 unsigned i;
1562 bitmap empty;
1563 htab_t hempty;
1564
1565 memory_accesses.refs
1566 = htab_create (100, memref_hash, memref_eq, memref_free);
1567 memory_accesses.refs_list = NULL;
1568 memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
1569 number_of_loops ());
1570 memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
1571 number_of_loops ());
1572 memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
1573 number_of_loops ());
1574 memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
1575 number_of_loops ());
1576
1577 for (i = 0; i < number_of_loops (); i++)
1578 {
1579 empty = BITMAP_ALLOC (NULL);
1580 VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
1581 empty = BITMAP_ALLOC (NULL);
1582 VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
1583 empty = BITMAP_ALLOC (NULL);
1584 VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
1585 hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
1586 VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
1587 }
1588
1589 memory_accesses.ttae_cache = NULL;
1590
1591 gather_mem_refs_in_loops ();
1592 create_vop_ref_mapping ();
1593}
1594
1595/* Returns true if a region of size SIZE1 at position 0 and a region of
1596 size SIZE2 at position DIFF cannot overlap. */
1597
1598static bool
1599cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
1600{
1601 double_int d, bound;
1602
1603 /* Unless the difference is a constant, we fail. */
1604 if (diff->n != 0)
1605 return false;
1606
1607 d = diff->offset;
1608 if (double_int_negative_p (d))
1609 {
1610 /* The second object is before the first one, we succeed if the last
1611 element of the second object is before the start of the first one. */
1612 bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
1613 return double_int_negative_p (bound);
1614 }
1615 else
1616 {
1617 /* We succeed if the second object starts after the first one ends. */
1618 return double_int_scmp (size1, d) <= 0;
1619 }
1620}
1621
1622/* Returns true if MEM1 and MEM2 may alias. TTAE_CACHE is used as a cache in
1623 tree_to_aff_combination_expand. */
1624
1625static bool
1626mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
1627{
1628 /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1629 object and their offset differ in such a way that the locations cannot
1630 overlap, then they cannot alias. */
1631 double_int size1, size2;
1632 aff_tree off1, off2;
1633
1634 /* Perform basic offset and type-based disambiguation. */
1635 if (!refs_may_alias_p (mem1, mem2))
1636 return false;
1637
1638 /* The expansion of addresses may be a bit expensive, thus we only do
1639 the check at -O2 and higher optimization levels. */
1640 if (optimize < 2)
1641 return true;
1642
1643 get_inner_reference_aff (mem1, &off1, &size1);
1644 get_inner_reference_aff (mem2, &off2, &size2);
1645 aff_combination_expand (&off1, ttae_cache);
1646 aff_combination_expand (&off2, ttae_cache);
1647 aff_combination_scale (&off1, double_int_minus_one);
1648 aff_combination_add (&off2, &off1);
1649
1650 if (cannot_overlap_p (&off2, size1, size2))
1651 return false;
1652
1653 return true;
1654}
1655
1656/* Rewrites location LOC by TMP_VAR. */
1657
1658static void
1659rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
1660{
1661 mark_virtual_ops_for_renaming (loc->stmt);
1662 *loc->ref = tmp_var;
1663 update_stmt (loc->stmt);
1664}
1665
1666/* Adds all locations of REF in LOOP and its subloops to LOCS. */
1667
1668static void
1669get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
1670 VEC (mem_ref_loc_p, heap) **locs)
1671{
1672 mem_ref_locs_p accs;
1673 unsigned i;
1674 mem_ref_loc_p loc;
1675 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1676 loop->num);
1677 struct loop *subloop;
1678
1679 if (!bitmap_bit_p (refs, ref->id))
1680 return;
1681
1682 if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1683 > (unsigned) loop->num)
1684 {
1685 accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1686 if (accs)
1687 {
1688 for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1689 VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
1690 }
1691 }
1692
1693 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1694 get_all_locs_in_loop (subloop, ref, locs);
1695}
1696
1697/* Rewrites all references to REF in LOOP by variable TMP_VAR. */
1698
1699static void
1700rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1701{
1702 unsigned i;
1703 mem_ref_loc_p loc;
1704 VEC (mem_ref_loc_p, heap) *locs = NULL;
1705
1706 get_all_locs_in_loop (loop, ref, &locs);
1707 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1708 rewrite_mem_ref_loc (loc, tmp_var);
1709 VEC_free (mem_ref_loc_p, heap, locs);
1710}
1711
1712/* The name and the length of the currently generated variable
1713 for lsm. */
1714#define MAX_LSM_NAME_LENGTH 40
1715static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1716static int lsm_tmp_name_length;
1717
1718/* Adds S to lsm_tmp_name. */
1719
1720static void
1721lsm_tmp_name_add (const char *s)
1722{
1723 int l = strlen (s) + lsm_tmp_name_length;
1724 if (l > MAX_LSM_NAME_LENGTH)
1725 return;
1726
1727 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1728 lsm_tmp_name_length = l;
1729}
1730
1731/* Stores the name for temporary variable that replaces REF to
1732 lsm_tmp_name. */
1733
1734static void
1735gen_lsm_tmp_name (tree ref)
1736{
1737 const char *name;
1738
1739 switch (TREE_CODE (ref))
1740 {
1741 case MISALIGNED_INDIRECT_REF:
1742 case ALIGN_INDIRECT_REF:
1743 case INDIRECT_REF:
1744 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1745 lsm_tmp_name_add ("_");
1746 break;
1747
1748 case BIT_FIELD_REF:
1749 case VIEW_CONVERT_EXPR:
1750 case ARRAY_RANGE_REF:
1751 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1752 break;
1753
1754 case REALPART_EXPR:
1755 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1756 lsm_tmp_name_add ("_RE");
1757 break;
1758
1759 case IMAGPART_EXPR:
1760 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1761 lsm_tmp_name_add ("_IM");
1762 break;
1763
1764 case COMPONENT_REF:
1765 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1766 lsm_tmp_name_add ("_");
1767 name = get_name (TREE_OPERAND (ref, 1));
1768 if (!name)
1769 name = "F";
1770 lsm_tmp_name_add ("_");
1771 lsm_tmp_name_add (name);
1772
1773 case ARRAY_REF:
1774 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1775 lsm_tmp_name_add ("_I");
1776 break;
1777
1778 case SSA_NAME:
1779 ref = SSA_NAME_VAR (ref);
1780 /* Fallthru. */
1781
1782 case VAR_DECL:
1783 case PARM_DECL:
1784 name = get_name (ref);
1785 if (!name)
1786 name = "D";
1787 lsm_tmp_name_add (name);
1788 break;
1789
1790 case STRING_CST:
1791 lsm_tmp_name_add ("S");
1792 break;
1793
1794 case RESULT_DECL:
1795 lsm_tmp_name_add ("R");
1796 break;
1797
1798 default:
1799 gcc_unreachable ();
1800 }
1801}
1802
1803/* Determines name for temporary variable that replaces REF.
1804 The name is accumulated into the lsm_tmp_name variable.
1805 N is added to the name of the temporary. */
1806
1807char *
1808get_lsm_tmp_name (tree ref, unsigned n)
1809{
1810 char ns[2];
1811
1812 lsm_tmp_name_length = 0;
1813 gen_lsm_tmp_name (ref);
1814 lsm_tmp_name_add ("_lsm");
1815 if (n < 10)
1816 {
1817 ns[0] = '0' + n;
1818 ns[1] = 0;
1819 lsm_tmp_name_add (ns);
1820 }
1821 return lsm_tmp_name;
1822}
1823
1824/* Executes store motion of memory reference REF from LOOP.
1825 Exits from the LOOP are stored in EXITS. The initialization of the
1826 temporary variable is put to the preheader of the loop, and assignments
1827 to the reference from the temporary variable are emitted to exits. */
1828
1829static void
1830execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
1831{
1832 tree tmp_var;
1833 unsigned i;
1834 gimple load, store;
1835 struct fmt_data fmt_data;
1836 edge ex;
1837 struct lim_aux_data *lim_data;
1838
1839 if (dump_file && (dump_flags & TDF_DETAILS))
1840 {
1841 fprintf (dump_file, "Executing store motion of ");
1842 print_generic_expr (dump_file, ref->mem, 0);
1843 fprintf (dump_file, " from loop %d\n", loop->num);
1844 }
1845
1846 tmp_var = make_rename_temp (TREE_TYPE (ref->mem),
1847 get_lsm_tmp_name (ref->mem, ~0));
1848
1849 fmt_data.loop = loop;
1850 fmt_data.orig_loop = loop;
1851 for_each_index (&ref->mem, force_move_till, &fmt_data);
1852
1853 rewrite_mem_refs (loop, ref, tmp_var);
1854
1855 /* Emit the load & stores. */
1856 load = gimple_build_assign (tmp_var, unshare_expr (ref->mem));
1857 lim_data = init_lim_data (load);
1858 lim_data->max_loop = loop;
1859 lim_data->tgt_loop = loop;
1860
1861 /* Put this into the latch, so that we are sure it will be processed after
1862 all dependencies. */
1863 gsi_insert_on_edge (loop_latch_edge (loop), load);
1864
1865 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1866 {
1867 store = gimple_build_assign (unshare_expr (ref->mem), tmp_var);
1868 gsi_insert_on_edge (ex, store);
1869 }
1870}
1871
1872/* Hoists memory references MEM_REFS out of LOOP. EXITS is the list of exit
1873 edges of the LOOP. */
1874
1875static void
1876hoist_memory_references (struct loop *loop, bitmap mem_refs,
1877 VEC (edge, heap) *exits)
1878{
1879 mem_ref_p ref;
1880 unsigned i;
1881 bitmap_iterator bi;
1882
1883 EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
1884 {
1885 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1886 execute_sm (loop, exits, ref);
1887 }
1888}
1889
1890/* Returns true if REF is always accessed in LOOP. */
1891
1892static bool
1893ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
1894{
1895 VEC (mem_ref_loc_p, heap) *locs = NULL;
1896 unsigned i;
1897 mem_ref_loc_p loc;
1898 bool ret = false;
1899 struct loop *must_exec;
1900
1901 get_all_locs_in_loop (loop, ref, &locs);
1902 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1903 {
1904 if (!get_lim_data (loc->stmt))
1905 continue;
1906
1907 must_exec = get_lim_data (loc->stmt)->always_executed_in;
1908 if (!must_exec)
1909 continue;
1910
1911 if (must_exec == loop
1912 || flow_loop_nested_p (must_exec, loop))
1913 {
1914 ret = true;
1915 break;
1916 }
1917 }
1918 VEC_free (mem_ref_loc_p, heap, locs);
1919
1920 return ret;
1921}
1922
1923/* Returns true if REF1 and REF2 are independent. */
1924
1925static bool
1926refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
1927{
1928 if (ref1 == ref2
1929 || bitmap_bit_p (ref1->indep_ref, ref2->id))
1930 return true;
1931 if (bitmap_bit_p (ref1->dep_ref, ref2->id))
1932 return false;
1933
1934 if (dump_file && (dump_flags & TDF_DETAILS))
1935 fprintf (dump_file, "Querying dependency of refs %u and %u: ",
1936 ref1->id, ref2->id);
1937
1938 if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
1939 &memory_accesses.ttae_cache))
1940 {
1941 bitmap_set_bit (ref1->dep_ref, ref2->id);
1942 bitmap_set_bit (ref2->dep_ref, ref1->id);
1943 if (dump_file && (dump_flags & TDF_DETAILS))
1944 fprintf (dump_file, "dependent.\n");
1945 return false;
1946 }
1947 else
1948 {
1949 bitmap_set_bit (ref1->indep_ref, ref2->id);
1950 bitmap_set_bit (ref2->indep_ref, ref1->id);
1951 if (dump_file && (dump_flags & TDF_DETAILS))
1952 fprintf (dump_file, "independent.\n");
1953 return true;
1954 }
1955}
1956
1957/* Records the information whether REF is independent in LOOP (according
1958 to INDEP). */
1959
1960static void
1961record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
1962{
1963 if (indep)
1964 bitmap_set_bit (ref->indep_loop, loop->num);
1965 else
1966 bitmap_set_bit (ref->dep_loop, loop->num);
1967}
1968
1969/* Returns true if REF is independent on all other memory references in
1970 LOOP. */
1971
1972static bool
1973ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
1974{
1975 bitmap clobbers, refs_to_check, refs;
1976 unsigned i;
1977 bitmap_iterator bi;
1978 bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
1979 htab_t map;
1980 mem_ref_p aref;
1981
1982 /* If the reference is clobbered, it is not independent. */
1983 clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1984 if (bitmap_intersect_p (ref->vops, clobbers))
1985 return false;
1986
1987 refs_to_check = BITMAP_ALLOC (NULL);
1988
1989 map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1990 EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
1991 {
1992 if (stored)
1993 refs = get_vop_accesses (map, i);
1994 else
1995 refs = get_vop_stores (map, i);
1996
1997 bitmap_ior_into (refs_to_check, refs);
1998 }
1999
2000 EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2001 {
2002 aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2003 if (!refs_independent_p (ref, aref))
2004 {
2005 ret = false;
2006 record_indep_loop (loop, aref, false);
2007 break;
2008 }
2009 }
2010
2011 BITMAP_FREE (refs_to_check);
2012 return ret;
2013}
2014
2015/* Returns true if REF is independent on all other memory references in
2016 LOOP. Wrapper over ref_indep_loop_p_1, caching its results. */
2017
2018static bool
2019ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2020{
2021 bool ret;
2022
2023 if (bitmap_bit_p (ref->indep_loop, loop->num))
2024 return true;
2025 if (bitmap_bit_p (ref->dep_loop, loop->num))
2026 return false;
2027
2028 ret = ref_indep_loop_p_1 (loop, ref);
2029
2030 if (dump_file && (dump_flags & TDF_DETAILS))
2031 fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2032 ref->id, loop->num, ret ? "independent" : "dependent");
2033
2034 record_indep_loop (loop, ref, ret);
2035
2036 return ret;
2037}
2038
2039/* Returns true if we can perform store motion of REF from LOOP. */
2040
2041static bool
2042can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2043{
2044 /* Unless the reference is stored in the loop, there is nothing to do. */
2045 if (!bitmap_bit_p (ref->stored, loop->num))
2046 return false;
2047
2048 /* It should be movable. */
2049 if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
2050 || TREE_THIS_VOLATILE (ref->mem)
2051 || !for_each_index (&ref->mem, may_move_till, loop))
2052 return false;
2053
2054 /* If it can trap, it must be always executed in LOOP. */
2055 if (tree_could_trap_p (ref->mem)
2056 && !ref_always_accessed_p (loop, ref))
2057 return false;
2058
2059 /* And it must be independent on all other memory references
2060 in LOOP. */
2061 if (!ref_indep_loop_p (loop, ref))
2062 return false;
2063
2064 return true;
2065}
2066
2067/* Marks the references in LOOP for that store motion should be performed
2068 in REFS_TO_SM. SM_EXECUTED is the set of references for that store
2069 motion was performed in one of the outer loops. */
2070
2071static void
2072find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2073{
2074 bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
2075 loop->num);
2076 unsigned i;
2077 bitmap_iterator bi;
2078 mem_ref_p ref;
2079
2080 EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2081 {
2082 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2083 if (can_sm_ref_p (loop, ref))
2084 bitmap_set_bit (refs_to_sm, i);
2085 }
2086}
2087
2088/* Checks whether LOOP (with exits stored in EXITS array) is suitable
2089 for a store motion optimization (i.e. whether we can insert statement
2090 on its exits). */
2091
2092static bool
2093loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2094 VEC (edge, heap) *exits)
2095{
2096 unsigned i;
2097 edge ex;
2098
2099 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2100 if (ex->flags & EDGE_ABNORMAL)
2101 return false;
2102
2103 return true;
2104}
2105
2106/* Try to perform store motion for all memory references modified inside
2107 LOOP. SM_EXECUTED is the bitmap of the memory references for that
2108 store motion was executed in one of the outer loops. */
2109
2110static void
2111store_motion_loop (struct loop *loop, bitmap sm_executed)
2112{
2113 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2114 struct loop *subloop;
2115 bitmap sm_in_loop = BITMAP_ALLOC (NULL);
2116
2117 if (loop_suitable_for_sm (loop, exits))
2118 {
2119 find_refs_for_sm (loop, sm_executed, sm_in_loop);
2120 hoist_memory_references (loop, sm_in_loop, exits);
2121 }
2122 VEC_free (edge, heap, exits);
2123
2124 bitmap_ior_into (sm_executed, sm_in_loop);
2125 for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2126 store_motion_loop (subloop, sm_executed);
2127 bitmap_and_compl_into (sm_executed, sm_in_loop);
2128 BITMAP_FREE (sm_in_loop);
2129}
2130
2131/* Try to perform store motion for all memory references modified inside
2132 loops. */
2133
2134static void
2135store_motion (void)
2136{
2137 struct loop *loop;
2138 bitmap sm_executed = BITMAP_ALLOC (NULL);
2139
2140 for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2141 store_motion_loop (loop, sm_executed);
2142
2143 BITMAP_FREE (sm_executed);
2144 gsi_commit_edge_inserts ();
2145}
2146
2147/* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2148 for each such basic block bb records the outermost loop for that execution
2149 of its header implies execution of bb. CONTAINS_CALL is the bitmap of
2150 blocks that contain a nonpure call. */
2151
2152static void
2153fill_always_executed_in (struct loop *loop, sbitmap contains_call)
2154{
2155 basic_block bb = NULL, *bbs, last = NULL;
2156 unsigned i;
2157 edge e;
2158 struct loop *inn_loop = loop;
2159
2160 if (!loop->header->aux)
2161 {
2162 bbs = get_loop_body_in_dom_order (loop);
2163
2164 for (i = 0; i < loop->num_nodes; i++)
2165 {
2166 edge_iterator ei;
2167 bb = bbs[i];
2168
2169 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2170 last = bb;
2171
2172 if (TEST_BIT (contains_call, bb->index))
2173 break;
2174
2175 FOR_EACH_EDGE (e, ei, bb->succs)
2176 if (!flow_bb_inside_loop_p (loop, e->dest))
2177 break;
2178 if (e)
2179 break;
2180
2181 /* A loop might be infinite (TODO use simple loop analysis
2182 to disprove this if possible). */
2183 if (bb->flags & BB_IRREDUCIBLE_LOOP)
2184 break;
2185
2186 if (!flow_bb_inside_loop_p (inn_loop, bb))
2187 break;
2188
2189 if (bb->loop_father->header == bb)
2190 {
2191 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2192 break;
2193
2194 /* In a loop that is always entered we may proceed anyway.
2195 But record that we entered it and stop once we leave it. */
2196 inn_loop = bb->loop_father;
2197 }
2198 }
2199
2200 while (1)
2201 {
2202 last->aux = loop;
2203 if (last == loop->header)
2204 break;
2205 last = get_immediate_dominator (CDI_DOMINATORS, last);
2206 }
2207
2208 free (bbs);
2209 }
2210
2211 for (loop = loop->inner; loop; loop = loop->next)
2212 fill_always_executed_in (loop, contains_call);
2213}
2214
2215/* Compute the global information needed by the loop invariant motion pass. */
2216
2217static void
2218tree_ssa_lim_initialize (void)
2219{
2220 sbitmap contains_call = sbitmap_alloc (last_basic_block);
2221 gimple_stmt_iterator bsi;
2222 struct loop *loop;
2223 basic_block bb;
2224
2225 sbitmap_zero (contains_call);
2226 FOR_EACH_BB (bb)
2227 {
2228 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2229 {
2230 if (nonpure_call_p (gsi_stmt (bsi)))
2231 break;
2232 }
2233
2234 if (!gsi_end_p (bsi))
2235 SET_BIT (contains_call, bb->index);
2236 }
2237
2238 for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2239 fill_always_executed_in (loop, contains_call);
2240
2241 sbitmap_free (contains_call);
2242
2243 lim_aux_data_map = pointer_map_create ();
2244}
2245
2246/* Cleans up after the invariant motion pass. */
2247
2248static void
2249tree_ssa_lim_finalize (void)
2250{
2251 basic_block bb;
2252 unsigned i;
2253 bitmap b;
2254 htab_t h;
2255
2256 FOR_EACH_BB (bb)
2257 {
2258 bb->aux = NULL;
2259 }
2260
2261 pointer_map_destroy (lim_aux_data_map);
2262
2263 VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
2264 htab_delete (memory_accesses.refs);
2265
2266 for (i = 0; VEC_iterate (bitmap, memory_accesses.refs_in_loop, i, b); i++)
2267 BITMAP_FREE (b);
2268 VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
2269
2270 for (i = 0; VEC_iterate (bitmap, memory_accesses.all_refs_in_loop, i, b); i++)
2271 BITMAP_FREE (b);
2272 VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
2273
2274 for (i = 0; VEC_iterate (bitmap, memory_accesses.clobbered_vops, i, b); i++)
2275 BITMAP_FREE (b);
2276 VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
2277
2278 for (i = 0; VEC_iterate (htab_t, memory_accesses.vop_ref_map, i, h); i++)
2279 htab_delete (h);
2280 VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
2281
2282 if (memory_accesses.ttae_cache)
2283 pointer_map_destroy (memory_accesses.ttae_cache);
2284}
2285
2286/* Moves invariants from loops. Only "expensive" invariants are moved out --
2287 i.e. those that are likely to be win regardless of the register pressure. */
2288
2289void
2290tree_ssa_lim (void)
2291{
2292 tree_ssa_lim_initialize ();
2293
2294 /* Gathers information about memory accesses in the loops. */
2295 analyze_memory_references ();
2296
2297 /* For each statement determine the outermost loop in that it is
2298 invariant and cost for computing the invariant. */
2299 determine_invariantness ();
2300
2301 /* Execute store motion. Force the necessary invariants to be moved
2302 out of the loops as well. */
2303 store_motion ();
2304
2305 /* Move the expressions that are expensive enough. */
2306 move_computations ();
2307
2308 tree_ssa_lim_finalize ();
2309}