OSDN Git Service

738249445b0288df7d7f1f9ae49adec1ad2710a3
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-im.c
1 /* Loop invariant motion.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
3    Foundation, Inc.
4    
5 This file is part of GCC.
6    
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11    
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16    
17 You should have received a copy of the GNU General Public License
18 along 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
71 struct depend
72 {
73   gimple stmt;
74   struct depend *next;
75 };
76
77 /* The auxiliary data kept for each statement.  */
78
79 struct 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
104 static struct pointer_map_t *lim_aux_data_map;
105
106 /* Description of a memory reference location.  */
107
108 typedef 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
114 DEF_VEC_P(mem_ref_loc_p);
115 DEF_VEC_ALLOC_P(mem_ref_loc_p, heap);
116
117 /* The list of memory reference locations in a loop.  */
118
119 typedef struct mem_ref_locs
120 {
121   VEC (mem_ref_loc_p, heap) *locs;
122 } *mem_ref_locs_p;
123
124 DEF_VEC_P(mem_ref_locs_p);
125 DEF_VEC_ALLOC_P(mem_ref_locs_p, heap);
126
127 /* Description of a memory reference.  */
128
129 typedef 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
160 DEF_VEC_P(mem_ref_p);
161 DEF_VEC_ALLOC_P(mem_ref_p, heap);
162
163 DEF_VEC_P(bitmap);
164 DEF_VEC_ALLOC_P(bitmap, heap);
165
166 DEF_VEC_P(htab_t);
167 DEF_VEC_ALLOC_P(htab_t, heap);
168
169 /* Description of memory accesses in loops.  */
170
171 static 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
197 static 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
206 static struct lim_aux_data *
207 init_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
215 static struct lim_aux_data *
216 get_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
227 static void
228 free_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
240 static void
241 clear_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
265 bool
266 for_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
348 enum move_pos
349 movement_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 (gimple_vdef (stmt))
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
418 static struct loop *
419 outermost_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
465 static bool
466 add_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
509 static unsigned
510 stmt_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
574 static struct loop *
575 outermost_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
599 static tree *
600 simple_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
635 static mem_ref_p
636 mem_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
664 static bool
665 determine_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 (gimple_vuse (stmt))
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           if ((val = gimple_vuse (stmt)) != NULL_TREE)
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
715 static void
716 set_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
742 static void
743 set_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
750 static bool
751 nonpure_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
761 static gimple
762 rewrite_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
811 static gimple
812 rewrite_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       propagate_defs_into_debug_stmts (gsi_stmt (*bsi), NULL, NULL);
883       gsi_replace (bsi, stmt2, true);
884
885       return stmt1;
886     }
887
888   return stmt;
889 }
890
891
892 /* Determine the outermost loops in that statements in basic block BB are
893    invariant, and record them to the LIM_DATA associated with the statements.
894    Callback for walk_dominator_tree.  */
895
896 static void
897 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
898                               basic_block bb)
899 {
900   enum move_pos pos;
901   gimple_stmt_iterator bsi;
902   gimple stmt;
903   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
904   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
905   struct lim_aux_data *lim_data;
906
907   if (!loop_outer (bb->loop_father))
908     return;
909
910   if (dump_file && (dump_flags & TDF_DETAILS))
911     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
912              bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
913
914   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
915     {
916       stmt = gsi_stmt (bsi);
917
918       pos = movement_possibility (stmt);
919       if (pos == MOVE_IMPOSSIBLE)
920         {
921           if (nonpure_call_p (stmt))
922             {
923               maybe_never = true;
924               outermost = NULL;
925             }
926           /* Make sure to note always_executed_in for stores to make
927              store-motion work.  */
928           else if (stmt_makes_single_store (stmt))
929             {
930               struct lim_aux_data *lim_data = init_lim_data (stmt);
931               lim_data->always_executed_in = outermost;
932             }
933           continue;
934         }
935
936       if (is_gimple_assign (stmt)
937           && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
938               == GIMPLE_BINARY_RHS))
939         {
940           tree op0 = gimple_assign_rhs1 (stmt);
941           tree op1 = gimple_assign_rhs2 (stmt);
942           struct loop *ol1 = outermost_invariant_loop (op1,
943                                         loop_containing_stmt (stmt));
944
945           /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
946              to be hoisted out of loop, saving expensive divide.  */
947           if (pos == MOVE_POSSIBLE
948               && gimple_assign_rhs_code (stmt) == RDIV_EXPR
949               && flag_unsafe_math_optimizations
950               && !flag_trapping_math
951               && ol1 != NULL
952               && outermost_invariant_loop (op0, ol1) == NULL)
953             stmt = rewrite_reciprocal (&bsi);
954
955           /* If the shift count is invariant, convert (A >> B) & 1 to
956              A & (1 << B) allowing the bit mask to be hoisted out of the loop
957              saving an expensive shift.  */
958           if (pos == MOVE_POSSIBLE
959               && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
960               && integer_onep (op1)
961               && TREE_CODE (op0) == SSA_NAME
962               && has_single_use (op0))
963             stmt = rewrite_bittest (&bsi);
964         }
965
966       lim_data = init_lim_data (stmt);
967       lim_data->always_executed_in = outermost;
968
969       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
970         continue;
971
972       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
973         {
974           lim_data->max_loop = NULL;
975           continue;
976         }
977
978       if (dump_file && (dump_flags & TDF_DETAILS))
979         {
980           print_gimple_stmt (dump_file, stmt, 2, 0);
981           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
982                    loop_depth (lim_data->max_loop),
983                    lim_data->cost);
984         }
985
986       if (lim_data->cost >= LIM_EXPENSIVE)
987         set_profitable_level (stmt);
988     }
989 }
990
991 /* For each statement determines the outermost loop in that it is invariant,
992    statements on whose motion it depends and the cost of the computation.
993    This information is stored to the LIM_DATA structure associated with
994    each statement.  */
995
996 static void
997 determine_invariantness (void)
998 {
999   struct dom_walk_data walk_data;
1000
1001   memset (&walk_data, 0, sizeof (struct dom_walk_data));
1002   walk_data.dom_direction = CDI_DOMINATORS;
1003   walk_data.before_dom_children = determine_invariantness_stmt;
1004
1005   init_walk_dominator_tree (&walk_data);
1006   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1007   fini_walk_dominator_tree (&walk_data);
1008 }
1009
1010 /* Hoist the statements in basic block BB out of the loops prescribed by
1011    data stored in LIM_DATA structures associated with each statement.  Callback
1012    for walk_dominator_tree.  */
1013
1014 static void
1015 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
1016                         basic_block bb)
1017 {
1018   struct loop *level;
1019   gimple_stmt_iterator bsi;
1020   gimple stmt;
1021   unsigned cost = 0;
1022   struct lim_aux_data *lim_data;
1023
1024   if (!loop_outer (bb->loop_father))
1025     return;
1026
1027   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
1028     {
1029       stmt = gsi_stmt (bsi);
1030
1031       lim_data = get_lim_data (stmt);
1032       if (lim_data == NULL)
1033         {
1034           gsi_next (&bsi);
1035           continue;
1036         }
1037
1038       cost = lim_data->cost;
1039       level = lim_data->tgt_loop;
1040       clear_lim_data (stmt);
1041
1042       if (!level)
1043         {
1044           gsi_next (&bsi);
1045           continue;
1046         }
1047
1048       /* We do not really want to move conditionals out of the loop; we just
1049          placed it here to force its operands to be moved if necessary.  */
1050       if (gimple_code (stmt) == GIMPLE_COND)
1051         continue;
1052
1053       if (dump_file && (dump_flags & TDF_DETAILS))
1054         {
1055           fprintf (dump_file, "Moving statement\n");
1056           print_gimple_stmt (dump_file, stmt, 0, 0);
1057           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
1058                    cost, level->num);
1059         }
1060
1061       mark_virtual_ops_for_renaming (stmt);
1062       gsi_insert_on_edge (loop_preheader_edge (level), stmt);
1063       propagate_defs_into_debug_stmts (gsi_stmt (bsi), NULL, NULL);
1064       gsi_remove (&bsi, false);
1065     }
1066 }
1067
1068 /* Hoist the statements out of the loops prescribed by data stored in
1069    LIM_DATA structures associated with each statement.*/
1070
1071 static void
1072 move_computations (void)
1073 {
1074   struct dom_walk_data walk_data;
1075
1076   memset (&walk_data, 0, sizeof (struct dom_walk_data));
1077   walk_data.dom_direction = CDI_DOMINATORS;
1078   walk_data.before_dom_children = move_computations_stmt;
1079
1080   init_walk_dominator_tree (&walk_data);
1081   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1082   fini_walk_dominator_tree (&walk_data);
1083
1084   gsi_commit_edge_inserts ();
1085   if (need_ssa_update_p (cfun))
1086     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1087 }
1088
1089 /* Checks whether the statement defining variable *INDEX can be hoisted
1090    out of the loop passed in DATA.  Callback for for_each_index.  */
1091
1092 static bool
1093 may_move_till (tree ref, tree *index, void *data)
1094 {
1095   struct loop *loop = (struct loop *) data, *max_loop;
1096
1097   /* If REF is an array reference, check also that the step and the lower
1098      bound is invariant in LOOP.  */
1099   if (TREE_CODE (ref) == ARRAY_REF)
1100     {
1101       tree step = TREE_OPERAND (ref, 3);
1102       tree lbound = TREE_OPERAND (ref, 2);
1103
1104       max_loop = outermost_invariant_loop (step, loop);
1105       if (!max_loop)
1106         return false;
1107
1108       max_loop = outermost_invariant_loop (lbound, loop);
1109       if (!max_loop)
1110         return false;
1111     }
1112
1113   max_loop = outermost_invariant_loop (*index, loop);
1114   if (!max_loop)
1115     return false;
1116
1117   return true;
1118 }
1119
1120 /* If OP is SSA NAME, force the statement that defines it to be
1121    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
1122
1123 static void
1124 force_move_till_op (tree op, struct loop *orig_loop, struct loop *loop)
1125 {
1126   gimple stmt;
1127
1128   if (!op
1129       || is_gimple_min_invariant (op))
1130     return;
1131
1132   gcc_assert (TREE_CODE (op) == SSA_NAME);
1133       
1134   stmt = SSA_NAME_DEF_STMT (op);
1135   if (gimple_nop_p (stmt))
1136     return;
1137
1138   set_level (stmt, orig_loop, loop);
1139 }
1140
1141 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
1142    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
1143    for_each_index.  */
1144
1145 struct fmt_data
1146 {
1147   struct loop *loop;
1148   struct loop *orig_loop;
1149 };
1150
1151 static bool
1152 force_move_till (tree ref, tree *index, void *data)
1153 {
1154   struct fmt_data *fmt_data = (struct fmt_data *) data;
1155
1156   if (TREE_CODE (ref) == ARRAY_REF)
1157     {
1158       tree step = TREE_OPERAND (ref, 3);
1159       tree lbound = TREE_OPERAND (ref, 2);
1160
1161       force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
1162       force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
1163     }
1164
1165   force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
1166
1167   return true;
1168 }
1169
1170 /* A hash function for struct mem_ref object OBJ.  */
1171
1172 static hashval_t
1173 memref_hash (const void *obj)
1174 {
1175   const struct mem_ref *const mem = (const struct mem_ref *) obj;
1176
1177   return mem->hash;
1178 }
1179
1180 /* An equality function for struct mem_ref object OBJ1 with
1181    memory reference OBJ2.  */
1182
1183 static int
1184 memref_eq (const void *obj1, const void *obj2)
1185 {
1186   const struct mem_ref *const mem1 = (const struct mem_ref *) obj1;
1187
1188   return operand_equal_p (mem1->mem, (const_tree) obj2, 0);
1189 }
1190
1191 /* Releases list of memory reference locations ACCS.  */
1192
1193 static void
1194 free_mem_ref_locs (mem_ref_locs_p accs)
1195 {
1196   unsigned i;
1197   mem_ref_loc_p loc;
1198
1199   if (!accs)
1200     return;
1201
1202   for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1203     free (loc);
1204   VEC_free (mem_ref_loc_p, heap, accs->locs);
1205   free (accs);
1206 }
1207
1208 /* A function to free the mem_ref object OBJ.  */
1209
1210 static void
1211 memref_free (void *obj)
1212 {
1213   struct mem_ref *const mem = (struct mem_ref *) obj;
1214   unsigned i;
1215   mem_ref_locs_p accs;
1216
1217   BITMAP_FREE (mem->stored);
1218   BITMAP_FREE (mem->indep_loop);
1219   BITMAP_FREE (mem->dep_loop);
1220   BITMAP_FREE (mem->indep_ref);
1221   BITMAP_FREE (mem->dep_ref);
1222
1223   for (i = 0; VEC_iterate (mem_ref_locs_p, mem->accesses_in_loop, i, accs); i++)
1224     free_mem_ref_locs (accs);
1225   VEC_free (mem_ref_locs_p, heap, mem->accesses_in_loop);
1226
1227   BITMAP_FREE (mem->vops);
1228   free (mem);
1229 }
1230
1231 /* Allocates and returns a memory reference description for MEM whose hash
1232    value is HASH and id is ID.  */
1233
1234 static mem_ref_p
1235 mem_ref_alloc (tree mem, unsigned hash, unsigned id)
1236 {
1237   mem_ref_p ref = XNEW (struct mem_ref);
1238   ref->mem = mem;
1239   ref->id = id;
1240   ref->hash = hash;
1241   ref->stored = BITMAP_ALLOC (NULL);
1242   ref->indep_loop = BITMAP_ALLOC (NULL);
1243   ref->dep_loop = BITMAP_ALLOC (NULL);
1244   ref->indep_ref = BITMAP_ALLOC (NULL);
1245   ref->dep_ref = BITMAP_ALLOC (NULL);
1246   ref->accesses_in_loop = NULL;
1247   ref->vops = BITMAP_ALLOC (NULL);
1248
1249   return ref;
1250 }
1251
1252 /* Allocates and returns the new list of locations.  */
1253
1254 static mem_ref_locs_p
1255 mem_ref_locs_alloc (void)
1256 {
1257   mem_ref_locs_p accs = XNEW (struct mem_ref_locs);
1258   accs->locs = NULL;
1259   return accs;
1260 }
1261
1262 /* Records memory reference location *LOC in LOOP to the memory reference
1263    description REF.  The reference occurs in statement STMT.  */
1264
1265 static void
1266 record_mem_ref_loc (mem_ref_p ref, struct loop *loop, gimple stmt, tree *loc)
1267 {
1268   mem_ref_loc_p aref = XNEW (struct mem_ref_loc);
1269   mem_ref_locs_p accs;
1270   bitmap ril = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1271
1272   if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1273       <= (unsigned) loop->num)
1274     VEC_safe_grow_cleared (mem_ref_locs_p, heap, ref->accesses_in_loop,
1275                            loop->num + 1);
1276   accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1277   if (!accs)
1278     {
1279       accs = mem_ref_locs_alloc ();
1280       VEC_replace (mem_ref_locs_p, ref->accesses_in_loop, loop->num, accs);
1281     }
1282
1283   aref->stmt = stmt;
1284   aref->ref = loc;
1285
1286   VEC_safe_push (mem_ref_loc_p, heap, accs->locs, aref);
1287   bitmap_set_bit (ril, ref->id);
1288 }
1289
1290 /* Marks reference REF as stored in LOOP.  */
1291
1292 static void
1293 mark_ref_stored (mem_ref_p ref, struct loop *loop)
1294 {
1295   for (;
1296        loop != current_loops->tree_root
1297        && !bitmap_bit_p (ref->stored, loop->num);
1298        loop = loop_outer (loop))
1299     bitmap_set_bit (ref->stored, loop->num);
1300 }
1301
1302 /* Gathers memory references in statement STMT in LOOP, storing the
1303    information about them in the memory_accesses structure.  Marks
1304    the vops accessed through unrecognized statements there as
1305    well.  */
1306
1307 static void
1308 gather_mem_refs_stmt (struct loop *loop, gimple stmt)
1309 {
1310   tree *mem = NULL;
1311   hashval_t hash;
1312   PTR *slot;
1313   mem_ref_p ref;
1314   tree vname;
1315   bool is_stored;
1316   bitmap clvops;
1317   unsigned id;
1318
1319   if (!gimple_vuse (stmt))
1320     return;
1321
1322   mem = simple_mem_ref_in_stmt (stmt, &is_stored);
1323   if (!mem)
1324     goto fail;
1325
1326   hash = iterative_hash_expr (*mem, 0);
1327   slot = htab_find_slot_with_hash (memory_accesses.refs, *mem, hash, INSERT);
1328
1329   if (*slot)
1330     {
1331       ref = (mem_ref_p) *slot;
1332       id = ref->id;
1333     }
1334   else
1335     {
1336       id = VEC_length (mem_ref_p, memory_accesses.refs_list);
1337       ref = mem_ref_alloc (*mem, hash, id);
1338       VEC_safe_push (mem_ref_p, heap, memory_accesses.refs_list, ref);
1339       *slot = ref;
1340
1341       if (dump_file && (dump_flags & TDF_DETAILS))
1342         {
1343           fprintf (dump_file, "Memory reference %u: ", id);
1344           print_generic_expr (dump_file, ref->mem, TDF_SLIM);
1345           fprintf (dump_file, "\n");
1346         }
1347     }
1348   if (is_stored)
1349     mark_ref_stored (ref, loop);
1350
1351   if ((vname = gimple_vuse (stmt)) != NULL_TREE)
1352     bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1353   record_mem_ref_loc (ref, loop, stmt, mem);
1354   return;
1355
1356 fail:
1357   clvops = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1358   if ((vname = gimple_vuse (stmt)) != NULL_TREE)
1359     bitmap_set_bit (clvops, DECL_UID (SSA_NAME_VAR (vname)));
1360 }
1361
1362 /* Gathers memory references in loops.  */
1363
1364 static void
1365 gather_mem_refs_in_loops (void)
1366 {
1367   gimple_stmt_iterator bsi;
1368   basic_block bb;
1369   struct loop *loop;
1370   loop_iterator li;
1371   bitmap clvo, clvi;
1372   bitmap lrefs, alrefs, alrefso;
1373
1374   FOR_EACH_BB (bb)
1375     {
1376       loop = bb->loop_father;
1377       if (loop == current_loops->tree_root)
1378         continue;
1379
1380       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1381         gather_mem_refs_stmt (loop, gsi_stmt (bsi));
1382     }
1383
1384   /* Propagate the information about clobbered vops and accessed memory
1385      references up the loop hierarchy.  */
1386   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1387     {
1388       lrefs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1389       alrefs = VEC_index (bitmap, memory_accesses.all_refs_in_loop, loop->num);
1390       bitmap_ior_into (alrefs, lrefs);
1391
1392       if (loop_outer (loop) == current_loops->tree_root)
1393         continue;
1394
1395       clvi = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1396       clvo = VEC_index (bitmap, memory_accesses.clobbered_vops,
1397                         loop_outer (loop)->num);
1398       bitmap_ior_into (clvo, clvi);
1399
1400       alrefso = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1401                            loop_outer (loop)->num);
1402       bitmap_ior_into (alrefso, alrefs);
1403     }
1404 }
1405
1406 /* Element of the hash table that maps vops to memory references.  */
1407
1408 struct vop_to_refs_elt
1409 {
1410   /* DECL_UID of the vop.  */
1411   unsigned uid;
1412
1413   /* List of the all references.  */
1414   bitmap refs_all;
1415
1416   /* List of stored references.  */
1417   bitmap refs_stored;
1418 };
1419
1420 /* A hash function for struct vop_to_refs_elt object OBJ.  */
1421
1422 static hashval_t
1423 vtoe_hash (const void *obj)
1424 {
1425   const struct vop_to_refs_elt *const vtoe =
1426     (const struct vop_to_refs_elt *) obj;
1427
1428   return vtoe->uid;
1429 }
1430
1431 /* An equality function for struct vop_to_refs_elt object OBJ1 with
1432    uid of a vop OBJ2.  */
1433
1434 static int
1435 vtoe_eq (const void *obj1, const void *obj2)
1436 {
1437   const struct vop_to_refs_elt *const vtoe =
1438     (const struct vop_to_refs_elt *) obj1;
1439   const unsigned *const uid = (const unsigned *) obj2;
1440
1441   return vtoe->uid == *uid;
1442 }
1443
1444 /* A function to free the struct vop_to_refs_elt object.  */
1445
1446 static void
1447 vtoe_free (void *obj)
1448 {
1449   struct vop_to_refs_elt *const vtoe =
1450     (struct vop_to_refs_elt *) obj;
1451
1452   BITMAP_FREE (vtoe->refs_all);
1453   BITMAP_FREE (vtoe->refs_stored);
1454   free (vtoe);
1455 }
1456
1457 /* Records REF to hashtable VOP_TO_REFS for the index VOP.  STORED is true
1458    if the reference REF is stored.  */
1459
1460 static void
1461 record_vop_access (htab_t vop_to_refs, unsigned vop, unsigned ref, bool stored)
1462 {
1463   void **slot = htab_find_slot_with_hash (vop_to_refs, &vop, vop, INSERT);
1464   struct vop_to_refs_elt *vtoe;
1465
1466   if (!*slot)
1467     {
1468       vtoe = XNEW (struct vop_to_refs_elt);
1469       vtoe->uid = vop;
1470       vtoe->refs_all = BITMAP_ALLOC (NULL);
1471       vtoe->refs_stored = BITMAP_ALLOC (NULL);
1472       *slot = vtoe;
1473     }
1474   else
1475     vtoe = (struct vop_to_refs_elt *) *slot;
1476
1477   bitmap_set_bit (vtoe->refs_all, ref);
1478   if (stored)
1479     bitmap_set_bit (vtoe->refs_stored, ref);
1480 }
1481
1482 /* Returns the set of references that access VOP according to the table
1483    VOP_TO_REFS.  */
1484
1485 static bitmap
1486 get_vop_accesses (htab_t vop_to_refs, unsigned vop)
1487 {
1488   struct vop_to_refs_elt *const vtoe =
1489     (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1490   return vtoe->refs_all;
1491 }
1492
1493 /* Returns the set of stores that access VOP according to the table
1494    VOP_TO_REFS.  */
1495
1496 static bitmap
1497 get_vop_stores (htab_t vop_to_refs, unsigned vop)
1498 {
1499   struct vop_to_refs_elt *const vtoe =
1500     (struct vop_to_refs_elt *) htab_find_with_hash (vop_to_refs, &vop, vop);
1501   return vtoe->refs_stored;
1502 }
1503
1504 /* Adds REF to mapping from virtual operands to references in LOOP.  */
1505
1506 static void
1507 add_vop_ref_mapping (struct loop *loop, mem_ref_p ref)
1508 {
1509   htab_t map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1510   bool stored = bitmap_bit_p (ref->stored, loop->num);
1511   bitmap clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops,
1512                                loop->num);
1513   bitmap_iterator bi;
1514   unsigned vop;
1515
1516   EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, vop, bi)
1517     {
1518       record_vop_access (map, vop, ref->id, stored);
1519     }
1520 }
1521
1522 /* Create a mapping from virtual operands to references that touch them
1523    in LOOP.  */
1524
1525 static void
1526 create_vop_ref_mapping_loop (struct loop *loop)
1527 {
1528   bitmap refs = VEC_index (bitmap, memory_accesses.refs_in_loop, loop->num);
1529   struct loop *sloop;
1530   bitmap_iterator bi;
1531   unsigned i;
1532   mem_ref_p ref;
1533
1534   EXECUTE_IF_SET_IN_BITMAP (refs, 0, i, bi)
1535     {
1536       ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1537       for (sloop = loop; sloop != current_loops->tree_root; sloop = loop_outer (sloop))
1538         add_vop_ref_mapping (sloop, ref);
1539     }
1540 }
1541
1542 /* For each non-clobbered virtual operand and each loop, record the memory
1543    references in this loop that touch the operand.  */
1544
1545 static void
1546 create_vop_ref_mapping (void)
1547 {
1548   loop_iterator li;
1549   struct loop *loop;
1550
1551   FOR_EACH_LOOP (li, loop, 0)
1552     {
1553       create_vop_ref_mapping_loop (loop);
1554     }
1555 }
1556
1557 /* Gathers information about memory accesses in the loops.  */
1558
1559 static void
1560 analyze_memory_references (void)
1561 {
1562   unsigned i;
1563   bitmap empty;
1564   htab_t hempty;
1565
1566   memory_accesses.refs
1567           = htab_create (100, memref_hash, memref_eq, memref_free);
1568   memory_accesses.refs_list = NULL;
1569   memory_accesses.refs_in_loop = VEC_alloc (bitmap, heap,
1570                                             number_of_loops ());
1571   memory_accesses.all_refs_in_loop = VEC_alloc (bitmap, heap,
1572                                                 number_of_loops ());
1573   memory_accesses.clobbered_vops = VEC_alloc (bitmap, heap,
1574                                               number_of_loops ());
1575   memory_accesses.vop_ref_map = VEC_alloc (htab_t, heap,
1576                                            number_of_loops ());
1577
1578   for (i = 0; i < number_of_loops (); i++)
1579     {
1580       empty = BITMAP_ALLOC (NULL);
1581       VEC_quick_push (bitmap, memory_accesses.refs_in_loop, empty);
1582       empty = BITMAP_ALLOC (NULL);
1583       VEC_quick_push (bitmap, memory_accesses.all_refs_in_loop, empty);
1584       empty = BITMAP_ALLOC (NULL);
1585       VEC_quick_push (bitmap, memory_accesses.clobbered_vops, empty);
1586       hempty = htab_create (10, vtoe_hash, vtoe_eq, vtoe_free);
1587       VEC_quick_push (htab_t, memory_accesses.vop_ref_map, hempty);
1588     }
1589
1590   memory_accesses.ttae_cache = NULL;
1591
1592   gather_mem_refs_in_loops ();
1593   create_vop_ref_mapping ();
1594 }
1595
1596 /* Returns true if a region of size SIZE1 at position 0 and a region of
1597    size SIZE2 at position DIFF cannot overlap.  */
1598
1599 static bool
1600 cannot_overlap_p (aff_tree *diff, double_int size1, double_int size2)
1601 {
1602   double_int d, bound;
1603
1604   /* Unless the difference is a constant, we fail.  */
1605   if (diff->n != 0)
1606     return false;
1607
1608   d = diff->offset;
1609   if (double_int_negative_p (d))
1610     {
1611       /* The second object is before the first one, we succeed if the last
1612          element of the second object is before the start of the first one.  */
1613       bound = double_int_add (d, double_int_add (size2, double_int_minus_one));
1614       return double_int_negative_p (bound);
1615     }
1616   else
1617     {
1618       /* We succeed if the second object starts after the first one ends.  */
1619       return double_int_scmp (size1, d) <= 0;
1620     }
1621 }
1622
1623 /* Returns true if MEM1 and MEM2 may alias.  TTAE_CACHE is used as a cache in
1624    tree_to_aff_combination_expand.  */
1625
1626 static bool
1627 mem_refs_may_alias_p (tree mem1, tree mem2, struct pointer_map_t **ttae_cache)
1628 {
1629   /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
1630      object and their offset differ in such a way that the locations cannot
1631      overlap, then they cannot alias.  */
1632   double_int size1, size2;
1633   aff_tree off1, off2;
1634
1635   /* Perform basic offset and type-based disambiguation.  */
1636   if (!refs_may_alias_p (mem1, mem2))
1637     return false;
1638
1639   /* The expansion of addresses may be a bit expensive, thus we only do
1640      the check at -O2 and higher optimization levels.  */
1641   if (optimize < 2)
1642     return true;
1643
1644   get_inner_reference_aff (mem1, &off1, &size1);
1645   get_inner_reference_aff (mem2, &off2, &size2);
1646   aff_combination_expand (&off1, ttae_cache);
1647   aff_combination_expand (&off2, ttae_cache);
1648   aff_combination_scale (&off1, double_int_minus_one);
1649   aff_combination_add (&off2, &off1);
1650
1651   if (cannot_overlap_p (&off2, size1, size2))
1652     return false;
1653
1654   return true;
1655 }
1656
1657 /* Rewrites location LOC by TMP_VAR.  */
1658
1659 static void
1660 rewrite_mem_ref_loc (mem_ref_loc_p loc, tree tmp_var)
1661 {
1662   mark_virtual_ops_for_renaming (loc->stmt);
1663   *loc->ref = tmp_var;
1664   update_stmt (loc->stmt);
1665 }
1666
1667 /* Adds all locations of REF in LOOP and its subloops to LOCS.  */
1668
1669 static void
1670 get_all_locs_in_loop (struct loop *loop, mem_ref_p ref,
1671                       VEC (mem_ref_loc_p, heap) **locs)
1672 {
1673   mem_ref_locs_p accs;
1674   unsigned i;
1675   mem_ref_loc_p loc;
1676   bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
1677                            loop->num);
1678   struct loop *subloop;
1679
1680   if (!bitmap_bit_p (refs, ref->id))
1681     return;
1682
1683   if (VEC_length (mem_ref_locs_p, ref->accesses_in_loop)
1684       > (unsigned) loop->num)
1685     {
1686       accs = VEC_index (mem_ref_locs_p, ref->accesses_in_loop, loop->num);
1687       if (accs)
1688         {
1689           for (i = 0; VEC_iterate (mem_ref_loc_p, accs->locs, i, loc); i++)
1690             VEC_safe_push (mem_ref_loc_p, heap, *locs, loc);
1691         }
1692     }
1693
1694   for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
1695     get_all_locs_in_loop (subloop, ref, locs);
1696 }
1697
1698 /* Rewrites all references to REF in LOOP by variable TMP_VAR.  */
1699
1700 static void
1701 rewrite_mem_refs (struct loop *loop, mem_ref_p ref, tree tmp_var)
1702 {
1703   unsigned i;
1704   mem_ref_loc_p loc;
1705   VEC (mem_ref_loc_p, heap) *locs = NULL;
1706
1707   get_all_locs_in_loop (loop, ref, &locs);
1708   for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1709     rewrite_mem_ref_loc (loc, tmp_var);
1710   VEC_free (mem_ref_loc_p, heap, locs);
1711 }
1712
1713 /* The name and the length of the currently generated variable
1714    for lsm.  */
1715 #define MAX_LSM_NAME_LENGTH 40
1716 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
1717 static int lsm_tmp_name_length;
1718
1719 /* Adds S to lsm_tmp_name.  */
1720
1721 static void
1722 lsm_tmp_name_add (const char *s)
1723 {
1724   int l = strlen (s) + lsm_tmp_name_length;
1725   if (l > MAX_LSM_NAME_LENGTH)
1726     return;
1727
1728   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
1729   lsm_tmp_name_length = l;
1730 }
1731
1732 /* Stores the name for temporary variable that replaces REF to
1733    lsm_tmp_name.  */
1734
1735 static void
1736 gen_lsm_tmp_name (tree ref)
1737 {
1738   const char *name;
1739
1740   switch (TREE_CODE (ref))
1741     {
1742     case MISALIGNED_INDIRECT_REF:
1743     case ALIGN_INDIRECT_REF:
1744     case INDIRECT_REF:
1745       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1746       lsm_tmp_name_add ("_");
1747       break;
1748
1749     case BIT_FIELD_REF:
1750     case VIEW_CONVERT_EXPR:
1751     case ARRAY_RANGE_REF:
1752       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1753       break;
1754
1755     case REALPART_EXPR:
1756       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1757       lsm_tmp_name_add ("_RE");
1758       break;
1759       
1760     case IMAGPART_EXPR:
1761       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1762       lsm_tmp_name_add ("_IM");
1763       break;
1764
1765     case COMPONENT_REF:
1766       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1767       lsm_tmp_name_add ("_");
1768       name = get_name (TREE_OPERAND (ref, 1));
1769       if (!name)
1770         name = "F";
1771       lsm_tmp_name_add ("_");
1772       lsm_tmp_name_add (name);
1773
1774     case ARRAY_REF:
1775       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
1776       lsm_tmp_name_add ("_I");
1777       break;
1778
1779     case SSA_NAME:
1780       ref = SSA_NAME_VAR (ref);
1781       /* Fallthru.  */
1782
1783     case VAR_DECL:
1784     case PARM_DECL:
1785       name = get_name (ref);
1786       if (!name)
1787         name = "D";
1788       lsm_tmp_name_add (name);
1789       break;
1790
1791     case STRING_CST:
1792       lsm_tmp_name_add ("S");
1793       break;
1794
1795     case RESULT_DECL:
1796       lsm_tmp_name_add ("R");
1797       break;
1798
1799     case INTEGER_CST:
1800       /* Nothing.  */
1801       break;
1802
1803     default:
1804       gcc_unreachable ();
1805     }
1806 }
1807
1808 /* Determines name for temporary variable that replaces REF.
1809    The name is accumulated into the lsm_tmp_name variable.
1810    N is added to the name of the temporary.  */
1811
1812 char *
1813 get_lsm_tmp_name (tree ref, unsigned n)
1814 {
1815   char ns[2];
1816
1817   lsm_tmp_name_length = 0;
1818   gen_lsm_tmp_name (ref);
1819   lsm_tmp_name_add ("_lsm");
1820   if (n < 10)
1821     {
1822       ns[0] = '0' + n;
1823       ns[1] = 0;
1824       lsm_tmp_name_add (ns);
1825     }
1826   return lsm_tmp_name;
1827 }
1828
1829 /* Executes store motion of memory reference REF from LOOP.
1830    Exits from the LOOP are stored in EXITS.  The initialization of the
1831    temporary variable is put to the preheader of the loop, and assignments
1832    to the reference from the temporary variable are emitted to exits.  */
1833
1834 static void
1835 execute_sm (struct loop *loop, VEC (edge, heap) *exits, mem_ref_p ref)
1836 {
1837   tree tmp_var;
1838   unsigned i;
1839   gimple load, store;
1840   struct fmt_data fmt_data;
1841   edge ex;
1842   struct lim_aux_data *lim_data;
1843
1844   if (dump_file && (dump_flags & TDF_DETAILS))
1845     {
1846       fprintf (dump_file, "Executing store motion of ");
1847       print_generic_expr (dump_file, ref->mem, 0);
1848       fprintf (dump_file, " from loop %d\n", loop->num);
1849     }
1850
1851   tmp_var = make_rename_temp (TREE_TYPE (ref->mem),
1852                               get_lsm_tmp_name (ref->mem, ~0));
1853
1854   fmt_data.loop = loop;
1855   fmt_data.orig_loop = loop;
1856   for_each_index (&ref->mem, force_move_till, &fmt_data);
1857
1858   rewrite_mem_refs (loop, ref, tmp_var);
1859
1860   /* Emit the load & stores.  */
1861   load = gimple_build_assign (tmp_var, unshare_expr (ref->mem));
1862   lim_data = init_lim_data (load);
1863   lim_data->max_loop = loop;
1864   lim_data->tgt_loop = loop;
1865
1866   /* Put this into the latch, so that we are sure it will be processed after
1867      all dependencies.  */
1868   gsi_insert_on_edge (loop_latch_edge (loop), load);
1869
1870   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1871     {
1872       store = gimple_build_assign (unshare_expr (ref->mem), tmp_var);
1873       gsi_insert_on_edge (ex, store);
1874     }
1875 }
1876
1877 /* Hoists memory references MEM_REFS out of LOOP.  EXITS is the list of exit
1878    edges of the LOOP.  */
1879
1880 static void
1881 hoist_memory_references (struct loop *loop, bitmap mem_refs,
1882                          VEC (edge, heap) *exits)
1883 {
1884   mem_ref_p ref;
1885   unsigned  i;
1886   bitmap_iterator bi;
1887
1888   EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
1889     {
1890       ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
1891       execute_sm (loop, exits, ref);
1892     }
1893 }
1894
1895 /* Returns true if REF is always accessed in LOOP.  */
1896
1897 static bool
1898 ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
1899 {
1900   VEC (mem_ref_loc_p, heap) *locs = NULL;
1901   unsigned i;
1902   mem_ref_loc_p loc;
1903   bool ret = false;
1904   struct loop *must_exec;
1905
1906   get_all_locs_in_loop (loop, ref, &locs);
1907   for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
1908     {
1909       if (!get_lim_data (loc->stmt))
1910         continue;
1911
1912       must_exec = get_lim_data (loc->stmt)->always_executed_in;
1913       if (!must_exec)
1914         continue;
1915
1916       if (must_exec == loop
1917           || flow_loop_nested_p (must_exec, loop))
1918         {
1919           ret = true;
1920           break;
1921         }
1922     }
1923   VEC_free (mem_ref_loc_p, heap, locs);
1924
1925   return ret;
1926 }
1927
1928 /* Returns true if REF1 and REF2 are independent.  */
1929
1930 static bool
1931 refs_independent_p (mem_ref_p ref1, mem_ref_p ref2)
1932 {
1933   if (ref1 == ref2
1934       || bitmap_bit_p (ref1->indep_ref, ref2->id))
1935     return true;
1936   if (bitmap_bit_p (ref1->dep_ref, ref2->id))
1937     return false;
1938
1939   if (dump_file && (dump_flags & TDF_DETAILS))
1940     fprintf (dump_file, "Querying dependency of refs %u and %u: ",
1941              ref1->id, ref2->id);
1942
1943   if (mem_refs_may_alias_p (ref1->mem, ref2->mem,
1944                             &memory_accesses.ttae_cache))
1945     {
1946       bitmap_set_bit (ref1->dep_ref, ref2->id);
1947       bitmap_set_bit (ref2->dep_ref, ref1->id);
1948       if (dump_file && (dump_flags & TDF_DETAILS))
1949         fprintf (dump_file, "dependent.\n");
1950       return false;
1951     }
1952   else
1953     {
1954       bitmap_set_bit (ref1->indep_ref, ref2->id);
1955       bitmap_set_bit (ref2->indep_ref, ref1->id);
1956       if (dump_file && (dump_flags & TDF_DETAILS))
1957         fprintf (dump_file, "independent.\n");
1958       return true;
1959     }
1960 }
1961
1962 /* Records the information whether REF is independent in LOOP (according
1963    to INDEP).  */
1964
1965 static void
1966 record_indep_loop (struct loop *loop, mem_ref_p ref, bool indep)
1967 {
1968   if (indep)
1969     bitmap_set_bit (ref->indep_loop, loop->num);
1970   else
1971     bitmap_set_bit (ref->dep_loop, loop->num);
1972 }
1973
1974 /* Returns true if REF is independent on all other memory references in
1975    LOOP.  */
1976
1977 static bool
1978 ref_indep_loop_p_1 (struct loop *loop, mem_ref_p ref)
1979 {
1980   bitmap clobbers, refs_to_check, refs;
1981   unsigned i;
1982   bitmap_iterator bi;
1983   bool ret = true, stored = bitmap_bit_p (ref->stored, loop->num);
1984   htab_t map;
1985   mem_ref_p aref;
1986
1987   /* If the reference is clobbered, it is not independent.  */
1988   clobbers = VEC_index (bitmap, memory_accesses.clobbered_vops, loop->num);
1989   if (bitmap_intersect_p (ref->vops, clobbers))
1990     return false;
1991
1992   refs_to_check = BITMAP_ALLOC (NULL);
1993
1994   map = VEC_index (htab_t, memory_accesses.vop_ref_map, loop->num);
1995   EXECUTE_IF_AND_COMPL_IN_BITMAP (ref->vops, clobbers, 0, i, bi)
1996     {
1997       if (stored)
1998         refs = get_vop_accesses (map, i);
1999       else
2000         refs = get_vop_stores (map, i);
2001
2002       bitmap_ior_into (refs_to_check, refs);
2003     }
2004
2005   EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
2006     {
2007       aref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2008       if (!refs_independent_p (ref, aref))
2009         {
2010           ret = false;
2011           record_indep_loop (loop, aref, false);
2012           break;
2013         }
2014     }
2015
2016   BITMAP_FREE (refs_to_check);
2017   return ret;
2018 }
2019
2020 /* Returns true if REF is independent on all other memory references in
2021    LOOP.  Wrapper over ref_indep_loop_p_1, caching its results.  */
2022
2023 static bool
2024 ref_indep_loop_p (struct loop *loop, mem_ref_p ref)
2025 {
2026   bool ret;
2027
2028   if (bitmap_bit_p (ref->indep_loop, loop->num))
2029     return true;
2030   if (bitmap_bit_p (ref->dep_loop, loop->num))
2031     return false;
2032
2033   ret = ref_indep_loop_p_1 (loop, ref);
2034
2035   if (dump_file && (dump_flags & TDF_DETAILS))
2036     fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
2037              ref->id, loop->num, ret ? "independent" : "dependent");
2038
2039   record_indep_loop (loop, ref, ret);
2040
2041   return ret;
2042 }
2043
2044 /* Returns true if we can perform store motion of REF from LOOP.  */
2045
2046 static bool
2047 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
2048 {
2049   /* Unless the reference is stored in the loop, there is nothing to do.  */
2050   if (!bitmap_bit_p (ref->stored, loop->num))
2051     return false;
2052
2053   /* It should be movable.  */
2054   if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
2055       || TREE_THIS_VOLATILE (ref->mem)
2056       || !for_each_index (&ref->mem, may_move_till, loop))
2057     return false;
2058
2059   /* If it can trap, it must be always executed in LOOP.  */
2060   if (tree_could_trap_p (ref->mem)
2061       && !ref_always_accessed_p (loop, ref))
2062     return false;
2063
2064   /* And it must be independent on all other memory references
2065      in LOOP.  */
2066   if (!ref_indep_loop_p (loop, ref))
2067     return false;
2068
2069   return true;
2070 }
2071
2072 /* Marks the references in LOOP for that store motion should be performed
2073    in REFS_TO_SM.  SM_EXECUTED is the set of references for that store
2074    motion was performed in one of the outer loops.  */
2075
2076 static void
2077 find_refs_for_sm (struct loop *loop, bitmap sm_executed, bitmap refs_to_sm)
2078 {
2079   bitmap refs = VEC_index (bitmap, memory_accesses.all_refs_in_loop,
2080                            loop->num);
2081   unsigned i;
2082   bitmap_iterator bi;
2083   mem_ref_p ref;
2084
2085   EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
2086     {
2087       ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
2088       if (can_sm_ref_p (loop, ref))
2089         bitmap_set_bit (refs_to_sm, i);
2090     }
2091 }
2092
2093 /* Checks whether LOOP (with exits stored in EXITS array) is suitable
2094    for a store motion optimization (i.e. whether we can insert statement
2095    on its exits).  */
2096
2097 static bool
2098 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED,
2099                       VEC (edge, heap) *exits)
2100 {
2101   unsigned i;
2102   edge ex;
2103
2104   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2105     if (ex->flags & EDGE_ABNORMAL)
2106       return false;
2107
2108   return true;
2109 }
2110
2111 /* Try to perform store motion for all memory references modified inside
2112    LOOP.  SM_EXECUTED is the bitmap of the memory references for that
2113    store motion was executed in one of the outer loops.  */
2114
2115 static void
2116 store_motion_loop (struct loop *loop, bitmap sm_executed)
2117 {
2118   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2119   struct loop *subloop;
2120   bitmap sm_in_loop = BITMAP_ALLOC (NULL);
2121
2122   if (loop_suitable_for_sm (loop, exits))
2123     {
2124       find_refs_for_sm (loop, sm_executed, sm_in_loop);
2125       hoist_memory_references (loop, sm_in_loop, exits);
2126     }
2127   VEC_free (edge, heap, exits);
2128
2129   bitmap_ior_into (sm_executed, sm_in_loop);
2130   for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
2131     store_motion_loop (subloop, sm_executed);
2132   bitmap_and_compl_into (sm_executed, sm_in_loop);
2133   BITMAP_FREE (sm_in_loop);
2134 }
2135
2136 /* Try to perform store motion for all memory references modified inside
2137    loops.  */
2138
2139 static void
2140 store_motion (void)
2141 {
2142   struct loop *loop;
2143   bitmap sm_executed = BITMAP_ALLOC (NULL);
2144
2145   for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
2146     store_motion_loop (loop, sm_executed);
2147
2148   BITMAP_FREE (sm_executed);
2149   gsi_commit_edge_inserts ();
2150 }
2151
2152 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
2153    for each such basic block bb records the outermost loop for that execution
2154    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
2155    blocks that contain a nonpure call.  */
2156
2157 static void
2158 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
2159 {
2160   basic_block bb = NULL, *bbs, last = NULL;
2161   unsigned i;
2162   edge e;
2163   struct loop *inn_loop = loop;
2164
2165   if (!loop->header->aux)
2166     {
2167       bbs = get_loop_body_in_dom_order (loop);
2168
2169       for (i = 0; i < loop->num_nodes; i++)
2170         {
2171           edge_iterator ei;
2172           bb = bbs[i];
2173
2174           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2175             last = bb;
2176
2177           if (TEST_BIT (contains_call, bb->index))
2178             break;
2179
2180           FOR_EACH_EDGE (e, ei, bb->succs)
2181             if (!flow_bb_inside_loop_p (loop, e->dest))
2182               break;
2183           if (e)
2184             break;
2185
2186           /* A loop might be infinite (TODO use simple loop analysis
2187              to disprove this if possible).  */
2188           if (bb->flags & BB_IRREDUCIBLE_LOOP)
2189             break;
2190
2191           if (!flow_bb_inside_loop_p (inn_loop, bb))
2192             break;
2193
2194           if (bb->loop_father->header == bb)
2195             {
2196               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
2197                 break;
2198
2199               /* In a loop that is always entered we may proceed anyway.
2200                  But record that we entered it and stop once we leave it.  */
2201               inn_loop = bb->loop_father;
2202             }
2203         }
2204
2205       while (1)
2206         {
2207           last->aux = loop;
2208           if (last == loop->header)
2209             break;
2210           last = get_immediate_dominator (CDI_DOMINATORS, last);
2211         }
2212
2213       free (bbs);
2214     }
2215
2216   for (loop = loop->inner; loop; loop = loop->next)
2217     fill_always_executed_in (loop, contains_call);
2218 }
2219
2220 /* Compute the global information needed by the loop invariant motion pass.  */
2221
2222 static void
2223 tree_ssa_lim_initialize (void)
2224 {
2225   sbitmap contains_call = sbitmap_alloc (last_basic_block);
2226   gimple_stmt_iterator bsi;
2227   struct loop *loop;
2228   basic_block bb;
2229
2230   sbitmap_zero (contains_call);
2231   FOR_EACH_BB (bb)
2232     {
2233       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2234         {
2235           if (nonpure_call_p (gsi_stmt (bsi)))
2236             break;
2237         }
2238
2239       if (!gsi_end_p (bsi))
2240         SET_BIT (contains_call, bb->index);
2241     }
2242
2243   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
2244     fill_always_executed_in (loop, contains_call);
2245
2246   sbitmap_free (contains_call);
2247
2248   lim_aux_data_map = pointer_map_create ();
2249 }
2250
2251 /* Cleans up after the invariant motion pass.  */
2252
2253 static void
2254 tree_ssa_lim_finalize (void)
2255 {
2256   basic_block bb;
2257   unsigned i;
2258   bitmap b;
2259   htab_t h;
2260
2261   FOR_EACH_BB (bb)
2262     {
2263       bb->aux = NULL;
2264     }
2265
2266   pointer_map_destroy (lim_aux_data_map);
2267
2268   VEC_free (mem_ref_p, heap, memory_accesses.refs_list);
2269   htab_delete (memory_accesses.refs);
2270
2271   for (i = 0; VEC_iterate (bitmap, memory_accesses.refs_in_loop, i, b); i++)
2272     BITMAP_FREE (b);
2273   VEC_free (bitmap, heap, memory_accesses.refs_in_loop);
2274
2275   for (i = 0; VEC_iterate (bitmap, memory_accesses.all_refs_in_loop, i, b); i++)
2276     BITMAP_FREE (b);
2277   VEC_free (bitmap, heap, memory_accesses.all_refs_in_loop);
2278
2279   for (i = 0; VEC_iterate (bitmap, memory_accesses.clobbered_vops, i, b); i++)
2280     BITMAP_FREE (b);
2281   VEC_free (bitmap, heap, memory_accesses.clobbered_vops);
2282
2283   for (i = 0; VEC_iterate (htab_t, memory_accesses.vop_ref_map, i, h); i++)
2284     htab_delete (h);
2285   VEC_free (htab_t, heap, memory_accesses.vop_ref_map);
2286
2287   if (memory_accesses.ttae_cache)
2288     pointer_map_destroy (memory_accesses.ttae_cache);
2289 }
2290
2291 /* Moves invariants from loops.  Only "expensive" invariants are moved out --
2292    i.e. those that are likely to be win regardless of the register pressure.  */
2293
2294 void
2295 tree_ssa_lim (void)
2296 {
2297   tree_ssa_lim_initialize ();
2298
2299   /* Gathers information about memory accesses in the loops.  */
2300   analyze_memory_references ();
2301
2302   /* For each statement determine the outermost loop in that it is
2303      invariant and cost for computing the invariant.  */
2304   determine_invariantness ();
2305
2306   /* Execute store motion.  Force the necessary invariants to be moved
2307      out of the loops as well.  */
2308   store_motion ();
2309
2310   /* Move the expressions that are expensive enough.  */
2311   move_computations ();
2312
2313   tree_ssa_lim_finalize ();
2314 }