OSDN Git Service

2005-12-02 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-im.c
1 /* Loop invariant motion.
2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3    
4 This file is part of GCC.
5    
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10    
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15    
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA.  */
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
43 /* TODO:  Support for predicated code motion.  I.e.
44
45    while (1)
46      {
47        if (cond)
48          {
49            a = inv;
50            something;
51          }
52      }
53
54    Where COND and INV are is invariants, but evaluating INV may trap or be
55    invalid from some other reason if !COND.  This may be transformed to
56
57    if (cond)
58      a = inv;
59    while (1)
60      {
61        if (cond)
62          something;
63      }  */
64
65 /* A type for the list of statements that have to be moved in order to be able
66    to hoist an invariant computation.  */
67
68 struct depend
69 {
70   tree stmt;
71   struct depend *next;
72 };
73
74 /* The auxiliary data kept for each statement.  */
75
76 struct lim_aux_data
77 {
78   struct loop *max_loop;        /* The outermost loop in that the statement
79                                    is invariant.  */
80
81   struct loop *tgt_loop;        /* The loop out of that we want to move the
82                                    invariant.  */
83
84   struct loop *always_executed_in;
85                                 /* The outermost loop for that we are sure
86                                    the statement is executed if the loop
87                                    is entered.  */
88
89   bool sm_done;                 /* True iff the store motion for a memory
90                                    reference in the statement has already
91                                    been executed.  */
92
93   unsigned cost;                /* Cost of the computation performed by the
94                                    statement.  */
95
96   struct depend *depends;       /* List of statements that must be also hoisted
97                                    out of the loop when this statement is
98                                    hoisted; i.e. those that define the operands
99                                    of the statement and are inside of the
100                                    MAX_LOOP loop.  */
101 };
102
103 #define LIM_DATA(STMT) (TREE_CODE (STMT) == PHI_NODE \
104                         ? NULL \
105                         : (struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
106
107 /* Description of a memory reference location for store motion.  */
108
109 struct mem_ref_loc
110 {
111   tree *ref;                    /* The reference itself.  */
112   tree stmt;                    /* The statement in that it occurs.  */
113   struct mem_ref_loc *next;     /* Next use in the chain.  */
114 };
115
116 /* Description of a memory reference for store motion.  */
117
118 struct mem_ref
119 {
120   tree mem;                     /* The memory itself.  */
121   hashval_t hash;               /* Its hash value.  */
122   bool is_stored;               /* True if there is a store to the location
123                                    in the loop.  */
124   struct mem_ref_loc *locs;     /* The locations where it is found.  */
125   bitmap vops;                  /* Vops corresponding to this memory
126                                    location.  */
127   struct mem_ref *next;         /* Next memory reference in the list.
128                                    Memory references are stored in a hash
129                                    table, but the hash function depends
130                                    on values of pointers. Thus we cannot use
131                                    htab_traverse, since then we would get
132                                    miscompares during bootstrap (although the
133                                    produced code would be correct).  */
134 };
135
136 /* Minimum cost of an expensive expression.  */
137 #define LIM_EXPENSIVE ((unsigned) PARAM_VALUE (PARAM_LIM_EXPENSIVE))
138
139 /* The outermost loop for that execution of the header guarantees that the
140    block will be executed.  */
141 #define ALWAYS_EXECUTED_IN(BB) ((struct loop *) (BB)->aux)
142
143 /* Calls CBCK for each index in memory reference ADDR_P.  There are two
144    kinds situations handled; in each of these cases, the memory reference
145    and DATA are passed to the callback:
146    
147    Access to an array: ARRAY_{RANGE_}REF (base, index).  In this case we also
148    pass the pointer to the index to the callback.
149
150    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
151    pointer to addr to the callback.
152    
153    If the callback returns false, the whole search stops and false is returned.
154    Otherwise the function returns true after traversing through the whole
155    reference *ADDR_P.  */
156
157 bool
158 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
159 {
160   tree *nxt, *idx;
161
162   for (; ; addr_p = nxt)
163     {
164       switch (TREE_CODE (*addr_p))
165         {
166         case SSA_NAME:
167           return cbck (*addr_p, addr_p, data);
168
169         case MISALIGNED_INDIRECT_REF:
170         case ALIGN_INDIRECT_REF:
171         case INDIRECT_REF:
172           nxt = &TREE_OPERAND (*addr_p, 0);
173           return cbck (*addr_p, nxt, data);
174
175         case BIT_FIELD_REF:
176         case VIEW_CONVERT_EXPR:
177         case ARRAY_RANGE_REF:
178         case REALPART_EXPR:
179         case IMAGPART_EXPR:
180           nxt = &TREE_OPERAND (*addr_p, 0);
181           break;
182
183         case COMPONENT_REF:
184           /* If the component has varying offset, it behaves like index
185              as well.  */
186           idx = &TREE_OPERAND (*addr_p, 2);
187           if (*idx
188               && !cbck (*addr_p, idx, data))
189             return false;
190
191           nxt = &TREE_OPERAND (*addr_p, 0);
192           break;
193
194         case ARRAY_REF:
195           nxt = &TREE_OPERAND (*addr_p, 0);
196           if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
197             return false;
198           break;
199
200         case VAR_DECL:
201         case PARM_DECL:
202         case STRING_CST:
203         case RESULT_DECL:
204         case VECTOR_CST:
205         case COMPLEX_CST:
206         case INTEGER_CST:
207         case REAL_CST:
208           return true;
209
210         case TARGET_MEM_REF:
211           idx = &TMR_BASE (*addr_p);
212           if (*idx
213               && !cbck (*addr_p, idx, data))
214             return false;
215           idx = &TMR_INDEX (*addr_p);
216           if (*idx
217               && !cbck (*addr_p, idx, data))
218             return false;
219           return true;
220
221         default:
222           gcc_unreachable ();
223         }
224     }
225 }
226
227 /* If it is possible to hoist the statement STMT unconditionally,
228    returns MOVE_POSSIBLE.
229    If it is possible to hoist the statement STMT, but we must avoid making
230    it executed if it would not be executed in the original program (e.g.
231    because it may trap), return MOVE_PRESERVE_EXECUTION.
232    Otherwise return MOVE_IMPOSSIBLE.  */
233
234 enum move_pos
235 movement_possibility (tree stmt)
236 {
237   tree lhs, rhs;
238
239   if (flag_unswitch_loops
240       && TREE_CODE (stmt) == COND_EXPR)
241     {
242       /* If we perform unswitching, force the operands of the invariant
243          condition to be moved out of the loop.  */
244       return MOVE_POSSIBLE;
245     }
246
247   if (TREE_CODE (stmt) != MODIFY_EXPR)
248     return MOVE_IMPOSSIBLE;
249
250   if (stmt_ends_bb_p (stmt))
251     return MOVE_IMPOSSIBLE;
252
253   if (stmt_ann (stmt)->has_volatile_ops)
254     return MOVE_IMPOSSIBLE;
255
256   lhs = TREE_OPERAND (stmt, 0);
257   if (TREE_CODE (lhs) == SSA_NAME
258       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
259     return MOVE_IMPOSSIBLE;
260
261   rhs = TREE_OPERAND (stmt, 1);
262
263   if (TREE_SIDE_EFFECTS (rhs))
264     return MOVE_IMPOSSIBLE;
265
266   if (TREE_CODE (lhs) != SSA_NAME
267       || tree_could_trap_p (rhs))
268     return MOVE_PRESERVE_EXECUTION;
269
270   if (get_call_expr_in (stmt))
271     {
272       /* While pure or const call is guaranteed to have no side effects, we
273          cannot move it arbitrarily.  Consider code like
274
275          char *s = something ();
276
277          while (1)
278            {
279              if (s)
280                t = strlen (s);
281              else
282                t = 0;
283            }
284
285          Here the strlen call cannot be moved out of the loop, even though
286          s is invariant.  In addition to possibly creating a call with
287          invalid arguments, moving out a function call that is not executed
288          may cause performance regressions in case the call is costly and
289          not executed at all.  */
290       return MOVE_PRESERVE_EXECUTION;
291     }
292   return MOVE_POSSIBLE;
293 }
294
295 /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
296    loop to that we could move the expression using DEF if it did not have
297    other operands, i.e. the outermost loop enclosing LOOP in that the value
298    of DEF is invariant.  */
299
300 static struct loop *
301 outermost_invariant_loop (tree def, struct loop *loop)
302 {
303   tree def_stmt;
304   basic_block def_bb;
305   struct loop *max_loop;
306
307   if (TREE_CODE (def) != SSA_NAME)
308     return superloop_at_depth (loop, 1);
309
310   def_stmt = SSA_NAME_DEF_STMT (def);
311   def_bb = bb_for_stmt (def_stmt);
312   if (!def_bb)
313     return superloop_at_depth (loop, 1);
314
315   max_loop = find_common_loop (loop, def_bb->loop_father);
316
317   if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
318     max_loop = find_common_loop (max_loop,
319                                  LIM_DATA (def_stmt)->max_loop->outer);
320   if (max_loop == loop)
321     return NULL;
322   max_loop = superloop_at_depth (loop, max_loop->depth + 1);
323
324   return max_loop;
325 }
326
327 /* Returns the outermost superloop of LOOP in that the expression EXPR is
328    invariant.  */
329
330 static struct loop *
331 outermost_invariant_loop_expr (tree expr, struct loop *loop)
332 {
333   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
334   unsigned i, nops;
335   struct loop *max_loop = superloop_at_depth (loop, 1), *aloop;
336
337   if (TREE_CODE (expr) == SSA_NAME
338       || TREE_CODE (expr) == INTEGER_CST
339       || is_gimple_min_invariant (expr))
340     return outermost_invariant_loop (expr, loop);
341
342   if (class != tcc_unary
343       && class != tcc_binary
344       && class != tcc_expression
345       && class != tcc_comparison)
346     return NULL;
347
348   nops = TREE_CODE_LENGTH (TREE_CODE (expr));
349   for (i = 0; i < nops; i++)
350     {
351       aloop = outermost_invariant_loop_expr (TREE_OPERAND (expr, i), loop);
352       if (!aloop)
353         return NULL;
354
355       if (flow_loop_nested_p (max_loop, aloop))
356         max_loop = aloop;
357     }
358
359   return max_loop;
360 }
361
362 /* DATA is a structure containing information associated with a statement
363    inside LOOP.  DEF is one of the operands of this statement.
364    
365    Find the outermost loop enclosing LOOP in that value of DEF is invariant
366    and record this in DATA->max_loop field.  If DEF itself is defined inside
367    this loop as well (i.e. we need to hoist it out of the loop if we want
368    to hoist the statement represented by DATA), record the statement in that
369    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
370    add the cost of the computation of DEF to the DATA->cost.
371    
372    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
373
374 static bool
375 add_dependency (tree def, struct lim_aux_data *data, struct loop *loop,
376                 bool add_cost)
377 {
378   tree def_stmt = SSA_NAME_DEF_STMT (def);
379   basic_block def_bb = bb_for_stmt (def_stmt);
380   struct loop *max_loop;
381   struct depend *dep;
382
383   if (!def_bb)
384     return true;
385
386   max_loop = outermost_invariant_loop (def, loop);
387   if (!max_loop)
388     return false;
389
390   if (flow_loop_nested_p (data->max_loop, max_loop))
391     data->max_loop = max_loop;
392
393   if (!LIM_DATA (def_stmt))
394     return true;
395
396   if (add_cost
397       /* Only add the cost if the statement defining DEF is inside LOOP,
398          i.e. if it is likely that by moving the invariants dependent
399          on it, we will be able to avoid creating a new register for
400          it (since it will be only used in these dependent invariants).  */
401       && def_bb->loop_father == loop)
402     data->cost += LIM_DATA (def_stmt)->cost;
403
404   dep = xmalloc (sizeof (struct depend));
405   dep->stmt = def_stmt;
406   dep->next = data->depends;
407   data->depends = dep;
408
409   return true;
410 }
411
412 /* Returns an estimate for a cost of statement STMT.  TODO -- the values here
413    are just ad-hoc constants.  The estimates should be based on target-specific
414    values.  */
415
416 static unsigned
417 stmt_cost (tree stmt)
418 {
419   tree rhs;
420   unsigned cost = 1;
421
422   /* Always try to create possibilities for unswitching.  */
423   if (TREE_CODE (stmt) == COND_EXPR)
424     return LIM_EXPENSIVE;
425
426   rhs = TREE_OPERAND (stmt, 1);
427
428   /* Hoisting memory references out should almost surely be a win.  */
429   if (stmt_references_memory_p (stmt))
430     cost += 20;
431
432   switch (TREE_CODE (rhs))
433     {
434     case CALL_EXPR:
435       /* We should be hoisting calls if possible.  */
436
437       /* Unless the call is a builtin_constant_p; this always folds to a
438          constant, so moving it is useless.  */
439       rhs = get_callee_fndecl (rhs);
440       if (DECL_BUILT_IN_CLASS (rhs) == BUILT_IN_NORMAL
441           && DECL_FUNCTION_CODE (rhs) == BUILT_IN_CONSTANT_P)
442         return 0;
443
444       cost += 20;
445       break;
446
447     case MULT_EXPR:
448     case TRUNC_DIV_EXPR:
449     case CEIL_DIV_EXPR:
450     case FLOOR_DIV_EXPR:
451     case ROUND_DIV_EXPR:
452     case EXACT_DIV_EXPR:
453     case CEIL_MOD_EXPR:
454     case FLOOR_MOD_EXPR:
455     case ROUND_MOD_EXPR:
456     case TRUNC_MOD_EXPR:
457     case RDIV_EXPR:
458       /* Division and multiplication are usually expensive.  */
459       cost += 20;
460       break;
461
462     default:
463       break;
464     }
465
466   return cost;
467 }
468
469 /* Determine the outermost loop to that it is possible to hoist a statement
470    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
471    the outermost loop in that the value computed by STMT is invariant.
472    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
473    we preserve the fact whether STMT is executed.  It also fills other related
474    information to LIM_DATA (STMT).
475    
476    The function returns false if STMT cannot be hoisted outside of the loop it
477    is defined in, and true otherwise.  */
478
479 static bool
480 determine_max_movement (tree stmt, bool must_preserve_exec)
481 {
482   basic_block bb = bb_for_stmt (stmt);
483   struct loop *loop = bb->loop_father;
484   struct loop *level;
485   struct lim_aux_data *lim_data = LIM_DATA (stmt);
486   tree val;
487   ssa_op_iter iter;
488   
489   if (must_preserve_exec)
490     level = ALWAYS_EXECUTED_IN (bb);
491   else
492     level = superloop_at_depth (loop, 1);
493   lim_data->max_loop = level;
494
495   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
496     if (!add_dependency (val, lim_data, loop, true))
497       return false;
498
499   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
500     if (!add_dependency (val, lim_data, loop, false))
501       return false;
502
503   lim_data->cost += stmt_cost (stmt);
504
505   return true;
506 }
507
508 /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
509    and that one of the operands of this statement is computed by STMT.
510    Ensure that STMT (together with all the statements that define its
511    operands) is hoisted at least out of the loop LEVEL.  */
512
513 static void
514 set_level (tree stmt, struct loop *orig_loop, struct loop *level)
515 {
516   struct loop *stmt_loop = bb_for_stmt (stmt)->loop_father;
517   struct depend *dep;
518
519   stmt_loop = find_common_loop (orig_loop, stmt_loop);
520   if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
521     stmt_loop = find_common_loop (stmt_loop,
522                                   LIM_DATA (stmt)->tgt_loop->outer);
523   if (flow_loop_nested_p (stmt_loop, level))
524     return;
525
526   gcc_assert (LIM_DATA (stmt));
527   gcc_assert (level == LIM_DATA (stmt)->max_loop
528               || flow_loop_nested_p (LIM_DATA (stmt)->max_loop, level));
529
530   LIM_DATA (stmt)->tgt_loop = level;
531   for (dep = LIM_DATA (stmt)->depends; dep; dep = dep->next)
532     set_level (dep->stmt, orig_loop, level);
533 }
534
535 /* Determines an outermost loop from that we want to hoist the statement STMT.
536    For now we chose the outermost possible loop.  TODO -- use profiling
537    information to set it more sanely.  */
538
539 static void
540 set_profitable_level (tree stmt)
541 {
542   set_level (stmt, bb_for_stmt (stmt)->loop_father, LIM_DATA (stmt)->max_loop);
543 }
544
545 /* Returns true if STMT is not a pure call.  */
546
547 static bool
548 nonpure_call_p (tree stmt)
549 {
550   tree call = get_call_expr_in (stmt);
551
552   if (!call)
553     return false;
554
555   return TREE_SIDE_EFFECTS (call) != 0;
556 }
557
558 /* Releases the memory occupied by DATA.  */
559
560 static void
561 free_lim_aux_data (struct lim_aux_data *data)
562 {
563   struct depend *dep, *next;
564
565   for (dep = data->depends; dep; dep = next)
566     {
567       next = dep->next;
568       free (dep);
569     }
570   free (data);
571 }
572
573 /* Determine the outermost loops in that statements in basic block BB are
574    invariant, and record them to the LIM_DATA associated with the statements.
575    Callback for walk_dominator_tree.  */
576
577 static void
578 determine_invariantness_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
579                               basic_block bb)
580 {
581   enum move_pos pos;
582   block_stmt_iterator bsi;
583   tree stmt, rhs;
584   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
585   struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
586
587   if (!bb->loop_father->outer)
588     return;
589
590   if (dump_file && (dump_flags & TDF_DETAILS))
591     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
592              bb->index, bb->loop_father->num, bb->loop_father->depth);
593
594   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
595     {
596       stmt = bsi_stmt (bsi);
597
598       pos = movement_possibility (stmt);
599       if (pos == MOVE_IMPOSSIBLE)
600         {
601           if (nonpure_call_p (stmt))
602             {
603               maybe_never = true;
604               outermost = NULL;
605             }
606           continue;
607         }
608
609       /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
610          to be hoisted out of loop, saving expensive divide.  */
611       if (pos == MOVE_POSSIBLE
612           && (rhs = TREE_OPERAND (stmt, 1)) != NULL
613           && TREE_CODE (rhs) == RDIV_EXPR
614           && flag_unsafe_math_optimizations
615           && !flag_trapping_math
616           && outermost_invariant_loop_expr (TREE_OPERAND (rhs, 1),
617                                             loop_containing_stmt (stmt)) != NULL
618           && outermost_invariant_loop_expr (rhs,
619                                             loop_containing_stmt (stmt)) == NULL)
620         {
621           tree lhs, stmt1, stmt2, var, name;
622
623           lhs = TREE_OPERAND (stmt, 0);
624
625           /* stmt must be MODIFY_EXPR.  */
626           var = create_tmp_var (TREE_TYPE (rhs), "reciptmp");
627           add_referenced_tmp_var (var);
628
629           stmt1 = build2 (MODIFY_EXPR, void_type_node, var,
630                           build2 (RDIV_EXPR, TREE_TYPE (rhs),
631                                   build_real (TREE_TYPE (rhs), dconst1),
632                                   TREE_OPERAND (rhs, 1)));
633           name = make_ssa_name (var, stmt1);
634           TREE_OPERAND (stmt1, 0) = name;
635           stmt2 = build2 (MODIFY_EXPR, void_type_node, lhs,
636                           build2 (MULT_EXPR, TREE_TYPE (rhs),
637                                   name, TREE_OPERAND (rhs, 0)));
638
639           /* Replace division stmt with reciprocal and multiply stmts.
640              The multiply stmt is not invariant, so update iterator
641              and avoid rescanning.  */
642           bsi_replace (&bsi, stmt1, true);
643           bsi_insert_after (&bsi, stmt2, BSI_NEW_STMT);
644           SSA_NAME_DEF_STMT (lhs) = stmt2;
645
646           /* Continue processing with invariant reciprocal statement.  */
647           stmt = stmt1;
648         }
649
650       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
651       LIM_DATA (stmt)->always_executed_in = outermost;
652
653       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
654         continue;
655
656       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
657         {
658           LIM_DATA (stmt)->max_loop = NULL;
659           continue;
660         }
661
662       if (dump_file && (dump_flags & TDF_DETAILS))
663         {
664           print_generic_stmt_indented (dump_file, stmt, 0, 2);
665           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
666                    LIM_DATA (stmt)->max_loop->depth,
667                    LIM_DATA (stmt)->cost);
668         }
669
670       if (LIM_DATA (stmt)->cost >= LIM_EXPENSIVE)
671         set_profitable_level (stmt);
672     }
673 }
674
675 /* For each statement determines the outermost loop in that it is invariant,
676    statements on whose motion it depends and the cost of the computation.
677    This information is stored to the LIM_DATA structure associated with
678    each statement.  */
679
680 static void
681 determine_invariantness (void)
682 {
683   struct dom_walk_data walk_data;
684
685   memset (&walk_data, 0, sizeof (struct dom_walk_data));
686   walk_data.before_dom_children_before_stmts = determine_invariantness_stmt;
687
688   init_walk_dominator_tree (&walk_data);
689   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
690   fini_walk_dominator_tree (&walk_data);
691 }
692
693 /* Commits edge insertions and updates loop structures.  */
694
695 void
696 loop_commit_inserts (void)
697 {
698   unsigned old_last_basic_block, i;
699   basic_block bb;
700
701   old_last_basic_block = last_basic_block;
702   bsi_commit_edge_inserts ();
703   for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
704     {
705       bb = BASIC_BLOCK (i);
706       add_bb_to_loop (bb,
707                       find_common_loop (single_pred (bb)->loop_father,
708                                         single_succ (bb)->loop_father));
709     }
710 }
711
712 /* Hoist the statements in basic block BB out of the loops prescribed by
713    data stored in LIM_DATA structures associated with each statement.  Callback
714    for walk_dominator_tree.  */
715
716 static void
717 move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
718                         basic_block bb)
719 {
720   struct loop *level;
721   block_stmt_iterator bsi;
722   tree stmt;
723   unsigned cost = 0;
724
725   if (!bb->loop_father->outer)
726     return;
727
728   for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
729     {
730       stmt = bsi_stmt (bsi);
731
732       if (!LIM_DATA (stmt))
733         {
734           bsi_next (&bsi);
735           continue;
736         }
737
738       cost = LIM_DATA (stmt)->cost;
739       level = LIM_DATA (stmt)->tgt_loop;
740       free_lim_aux_data (LIM_DATA (stmt));
741       stmt_ann (stmt)->common.aux = NULL;
742
743       if (!level)
744         {
745           bsi_next (&bsi);
746           continue;
747         }
748
749       /* We do not really want to move conditionals out of the loop; we just
750          placed it here to force its operands to be moved if necessary.  */
751       if (TREE_CODE (stmt) == COND_EXPR)
752         continue;
753
754       if (dump_file && (dump_flags & TDF_DETAILS))
755         {
756           fprintf (dump_file, "Moving statement\n");
757           print_generic_stmt (dump_file, stmt, 0);
758           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
759                    cost, level->num);
760         }
761       bsi_insert_on_edge (loop_preheader_edge (level), stmt);
762       bsi_remove (&bsi);
763     }
764 }
765
766 /* Hoist the statements out of the loops prescribed by data stored in
767    LIM_DATA structures associated with each statement.*/
768
769 static void
770 move_computations (void)
771 {
772   struct dom_walk_data walk_data;
773
774   memset (&walk_data, 0, sizeof (struct dom_walk_data));
775   walk_data.before_dom_children_before_stmts = move_computations_stmt;
776
777   init_walk_dominator_tree (&walk_data);
778   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
779   fini_walk_dominator_tree (&walk_data);
780
781   loop_commit_inserts ();
782   if (need_ssa_update_p ())
783     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
784 }
785
786 /* Checks whether the statement defining variable *INDEX can be hoisted
787    out of the loop passed in DATA.  Callback for for_each_index.  */
788
789 static bool
790 may_move_till (tree ref, tree *index, void *data)
791 {
792   struct loop *loop = data, *max_loop;
793
794   /* If REF is an array reference, check also that the step and the lower
795      bound is invariant in LOOP.  */
796   if (TREE_CODE (ref) == ARRAY_REF)
797     {
798       tree step = array_ref_element_size (ref);
799       tree lbound = array_ref_low_bound (ref);
800
801       max_loop = outermost_invariant_loop_expr (step, loop);
802       if (!max_loop)
803         return false;
804
805       max_loop = outermost_invariant_loop_expr (lbound, loop);
806       if (!max_loop)
807         return false;
808     }
809
810   max_loop = outermost_invariant_loop (*index, loop);
811   if (!max_loop)
812     return false;
813
814   return true;
815 }
816
817 /* Forces statements defining (invariant) SSA names in expression EXPR to be
818    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
819
820 static void
821 force_move_till_expr (tree expr, struct loop *orig_loop, struct loop *loop)
822 {
823   enum tree_code_class class = TREE_CODE_CLASS (TREE_CODE (expr));
824   unsigned i, nops;
825
826   if (TREE_CODE (expr) == SSA_NAME)
827     {
828       tree stmt = SSA_NAME_DEF_STMT (expr);
829       if (IS_EMPTY_STMT (stmt))
830         return;
831
832       set_level (stmt, orig_loop, loop);
833       return;
834     }
835
836   if (class != tcc_unary
837       && class != tcc_binary
838       && class != tcc_expression
839       && class != tcc_comparison)
840     return;
841
842   nops = TREE_CODE_LENGTH (TREE_CODE (expr));
843   for (i = 0; i < nops; i++)
844     force_move_till_expr (TREE_OPERAND (expr, i), orig_loop, loop);
845 }
846
847 /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
848    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
849    for_each_index.  */
850
851 struct fmt_data
852 {
853   struct loop *loop;
854   struct loop *orig_loop;
855 };
856
857 static bool
858 force_move_till (tree ref, tree *index, void *data)
859 {
860   tree stmt;
861   struct fmt_data *fmt_data = data;
862
863   if (TREE_CODE (ref) == ARRAY_REF)
864     {
865       tree step = array_ref_element_size (ref);
866       tree lbound = array_ref_low_bound (ref);
867
868       force_move_till_expr (step, fmt_data->orig_loop, fmt_data->loop);
869       force_move_till_expr (lbound, fmt_data->orig_loop, fmt_data->loop);
870     }
871
872   if (TREE_CODE (*index) != SSA_NAME)
873     return true;
874
875   stmt = SSA_NAME_DEF_STMT (*index);
876   if (IS_EMPTY_STMT (stmt))
877     return true;
878
879   set_level (stmt, fmt_data->orig_loop, fmt_data->loop);
880
881   return true;
882 }
883
884 /* Records memory reference location *REF to the list MEM_REFS.  The reference
885    occurs in statement STMT.  */
886
887 static void
888 record_mem_ref_loc (struct mem_ref_loc **mem_refs, tree stmt, tree *ref)
889 {
890   struct mem_ref_loc *aref = xmalloc (sizeof (struct mem_ref_loc));
891
892   aref->stmt = stmt;
893   aref->ref = ref;
894
895   aref->next = *mem_refs;
896   *mem_refs = aref;
897 }
898
899 /* Releases list of memory reference locations MEM_REFS.  */
900
901 static void
902 free_mem_ref_locs (struct mem_ref_loc *mem_refs)
903 {
904   struct mem_ref_loc *act;
905
906   while (mem_refs)
907     {
908       act = mem_refs;
909       mem_refs = mem_refs->next;
910       free (act);
911     }
912 }
913
914 /* Rewrites memory references in list MEM_REFS by variable TMP_VAR.  */
915
916 static void
917 rewrite_mem_refs (tree tmp_var, struct mem_ref_loc *mem_refs)
918 {
919   tree var;
920   ssa_op_iter iter;
921
922   for (; mem_refs; mem_refs = mem_refs->next)
923     {
924       FOR_EACH_SSA_TREE_OPERAND (var, mem_refs->stmt, iter, SSA_OP_ALL_VIRTUALS)
925         mark_sym_for_renaming (SSA_NAME_VAR (var));
926
927       *mem_refs->ref = tmp_var;
928       update_stmt (mem_refs->stmt);
929     }
930 }
931
932 /* The name and the length of the currently generated variable
933    for lsm.  */
934 #define MAX_LSM_NAME_LENGTH 40
935 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
936 static int lsm_tmp_name_length;
937
938 /* Adds S to lsm_tmp_name.  */
939
940 static void
941 lsm_tmp_name_add (const char *s)
942 {
943   int l = strlen (s) + lsm_tmp_name_length;
944   if (l > MAX_LSM_NAME_LENGTH)
945     return;
946
947   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
948   lsm_tmp_name_length = l;
949 }
950
951 /* Stores the name for temporary variable that replaces REF to
952    lsm_tmp_name.  */
953
954 static void
955 gen_lsm_tmp_name (tree ref)
956 {
957   const char *name;
958
959   switch (TREE_CODE (ref))
960     {
961     case MISALIGNED_INDIRECT_REF:
962     case ALIGN_INDIRECT_REF:
963     case INDIRECT_REF:
964       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
965       lsm_tmp_name_add ("_");
966       break;
967
968     case BIT_FIELD_REF:
969     case VIEW_CONVERT_EXPR:
970     case ARRAY_RANGE_REF:
971       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
972       break;
973
974     case REALPART_EXPR:
975       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
976       lsm_tmp_name_add ("_RE");
977       break;
978       
979     case IMAGPART_EXPR:
980       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
981       lsm_tmp_name_add ("_IM");
982       break;
983
984     case COMPONENT_REF:
985       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
986       lsm_tmp_name_add ("_");
987       name = get_name (TREE_OPERAND (ref, 1));
988       if (!name)
989         name = "F";
990       lsm_tmp_name_add ("_");
991       lsm_tmp_name_add (name);
992
993     case ARRAY_REF:
994       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
995       lsm_tmp_name_add ("_I");
996       break;
997
998     case SSA_NAME:
999       ref = SSA_NAME_VAR (ref);
1000       /* Fallthru.  */
1001
1002     case VAR_DECL:
1003     case PARM_DECL:
1004       name = get_name (ref);
1005       if (!name)
1006         name = "D";
1007       lsm_tmp_name_add (name);
1008       break;
1009
1010     case STRING_CST:
1011       lsm_tmp_name_add ("S");
1012       break;
1013
1014     case RESULT_DECL:
1015       lsm_tmp_name_add ("R");
1016       break;
1017
1018     default:
1019       gcc_unreachable ();
1020     }
1021 }
1022
1023 /* Determines name for temporary variable that replaces REF.
1024    The name is accumulated into the lsm_tmp_name variable.  */
1025
1026 static char *
1027 get_lsm_tmp_name (tree ref)
1028 {
1029   lsm_tmp_name_length = 0;
1030   gen_lsm_tmp_name (ref);
1031   lsm_tmp_name_add ("_lsm");
1032   return lsm_tmp_name;
1033 }
1034
1035 /* Records request for store motion of memory reference REF from LOOP.
1036    MEM_REFS is the list of occurrences of the reference REF inside LOOP;
1037    these references are rewritten by a new temporary variable.
1038    Exits from the LOOP are stored in EXITS, there are N_EXITS of them.
1039    The initialization of the temporary variable is put to the preheader
1040    of the loop, and assignments to the reference from the temporary variable
1041    are emitted to exits.  */
1042
1043 static void
1044 schedule_sm (struct loop *loop, edge *exits, unsigned n_exits, tree ref,
1045              struct mem_ref_loc *mem_refs)
1046 {
1047   struct mem_ref_loc *aref;
1048   tree tmp_var;
1049   unsigned i;
1050   tree load, store;
1051   struct fmt_data fmt_data;
1052
1053   if (dump_file && (dump_flags & TDF_DETAILS))
1054     {
1055       fprintf (dump_file, "Executing store motion of ");
1056       print_generic_expr (dump_file, ref, 0);
1057       fprintf (dump_file, " from loop %d\n", loop->num);
1058     }
1059
1060   tmp_var = make_rename_temp (TREE_TYPE (ref),
1061                               get_lsm_tmp_name (ref));
1062
1063   fmt_data.loop = loop;
1064   fmt_data.orig_loop = loop;
1065   for_each_index (&ref, force_move_till, &fmt_data);
1066
1067   rewrite_mem_refs (tmp_var, mem_refs);
1068   for (aref = mem_refs; aref; aref = aref->next)
1069     if (LIM_DATA (aref->stmt))
1070       LIM_DATA (aref->stmt)->sm_done = true;
1071
1072   /* Emit the load & stores.  */
1073   load = build2 (MODIFY_EXPR, void_type_node, tmp_var, ref);
1074   get_stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
1075   LIM_DATA (load)->max_loop = loop;
1076   LIM_DATA (load)->tgt_loop = loop;
1077
1078   /* Put this into the latch, so that we are sure it will be processed after
1079      all dependencies.  */
1080   bsi_insert_on_edge (loop_latch_edge (loop), load);
1081
1082   for (i = 0; i < n_exits; i++)
1083     {
1084       store = build2 (MODIFY_EXPR, void_type_node,
1085                       unshare_expr (ref), tmp_var);
1086       bsi_insert_on_edge (exits[i], store);
1087     }
1088 }
1089
1090 /* Check whether memory reference REF can be hoisted out of the LOOP.  If this
1091    is true, prepare the statements that load the value of the memory reference
1092    to a temporary variable in the loop preheader, store it back on the loop
1093    exits, and replace all the references inside LOOP by this temporary variable.
1094    LOOP has N_EXITS stored in EXITS.  CLOBBERED_VOPS is the bitmap of virtual
1095    operands that are clobbered by a call or accessed through multiple references
1096    in loop.  */
1097
1098 static void
1099 determine_lsm_ref (struct loop *loop, edge *exits, unsigned n_exits,
1100                    bitmap clobbered_vops, struct mem_ref *ref)
1101 {
1102   struct mem_ref_loc *aref;
1103   struct loop *must_exec;
1104
1105   /* In case the memory is not stored to, there is nothing for SM to do.  */
1106   if (!ref->is_stored)
1107     return;
1108
1109   /* If the reference is aliased with any different ref, or killed by call
1110      in function, then fail.  */
1111   if (bitmap_intersect_p (ref->vops, clobbered_vops))
1112     return;
1113
1114   if (tree_could_trap_p (ref->mem))
1115     {
1116       /* If the memory access is unsafe (i.e. it might trap), ensure that some
1117          of the statements in that it occurs is always executed when the loop
1118          is entered.  This way we know that by moving the load from the
1119          reference out of the loop we will not cause the error that would not
1120          occur otherwise.
1121
1122          TODO -- in fact we would like to check for anticipability of the
1123          reference, i.e. that on each path from loop entry to loop exit at
1124          least one of the statements containing the memory reference is
1125          executed.  */
1126
1127       for (aref = ref->locs; aref; aref = aref->next)
1128         {
1129           if (!LIM_DATA (aref->stmt))
1130             continue;
1131
1132           must_exec = LIM_DATA (aref->stmt)->always_executed_in;
1133           if (!must_exec)
1134             continue;
1135
1136           if (must_exec == loop
1137               || flow_loop_nested_p (must_exec, loop))
1138             break;
1139         }
1140
1141       if (!aref)
1142         return;
1143     }
1144
1145   schedule_sm (loop, exits, n_exits, ref->mem, ref->locs);
1146 }
1147
1148 /* Hoists memory references MEM_REFS out of LOOP.  CLOBBERED_VOPS is the list
1149    of vops clobbered by call in loop or accessed by multiple memory references.
1150    EXITS is the list of N_EXITS exit edges of the LOOP.  */
1151
1152 static void
1153 hoist_memory_references (struct loop *loop, struct mem_ref *mem_refs,
1154                          bitmap clobbered_vops, edge *exits, unsigned n_exits)
1155 {
1156   struct mem_ref *ref;
1157
1158   for (ref = mem_refs; ref; ref = ref->next)
1159     determine_lsm_ref (loop, exits, n_exits, clobbered_vops, ref);
1160 }
1161
1162 /* Checks whether LOOP (with N_EXITS exits stored in EXITS array) is suitable
1163    for a store motion optimization (i.e. whether we can insert statement
1164    on its exits).  */
1165
1166 static bool
1167 loop_suitable_for_sm (struct loop *loop ATTRIBUTE_UNUSED, edge *exits,
1168                       unsigned n_exits)
1169 {
1170   unsigned i;
1171
1172   for (i = 0; i < n_exits; i++)
1173     if (exits[i]->flags & EDGE_ABNORMAL)
1174       return false;
1175
1176   return true;
1177 }
1178
1179 /* A hash function for struct mem_ref object OBJ.  */
1180
1181 static hashval_t
1182 memref_hash (const void *obj)
1183 {
1184   const struct mem_ref *mem = obj;
1185
1186   return mem->hash;
1187 }
1188
1189 /* An equality function for struct mem_ref object OBJ1 with
1190    memory reference OBJ2.  */
1191
1192 static int
1193 memref_eq (const void *obj1, const void *obj2)
1194 {
1195   const struct mem_ref *mem1 = obj1;
1196
1197   return operand_equal_p (mem1->mem, (tree) obj2, 0);
1198 }
1199
1200 /* Gathers memory references in statement STMT in LOOP, storing the
1201    information about them in MEM_REFS hash table.  Note vops accessed through
1202    unrecognized statements in CLOBBERED_VOPS.  The newly created references
1203    are also stored to MEM_REF_LIST.  */
1204
1205 static void
1206 gather_mem_refs_stmt (struct loop *loop, htab_t mem_refs,
1207                       bitmap clobbered_vops, tree stmt,
1208                       struct mem_ref **mem_ref_list)
1209 {
1210   tree *lhs, *rhs, *mem = NULL;
1211   hashval_t hash;
1212   PTR *slot;
1213   struct mem_ref *ref = NULL;
1214   ssa_op_iter oi;
1215   tree vname;
1216   bool is_stored;
1217
1218   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1219     return;
1220
1221   /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns.  */
1222   if (TREE_CODE (stmt) != MODIFY_EXPR)
1223     goto fail;
1224
1225   lhs = &TREE_OPERAND (stmt, 0);
1226   rhs = &TREE_OPERAND (stmt, 1);
1227
1228   if (TREE_CODE (*lhs) == SSA_NAME)
1229     {
1230       if (!is_gimple_addressable (*rhs))
1231         goto fail;
1232
1233       mem = rhs;
1234       is_stored = false;
1235     }
1236   else if (TREE_CODE (*rhs) == SSA_NAME
1237            || is_gimple_min_invariant (*rhs))
1238     {
1239       mem = lhs;
1240       is_stored = true;
1241     }
1242   else
1243     goto fail;
1244
1245   /* If we cannot create an SSA name for the result, give up.  */
1246   if (!is_gimple_reg_type (TREE_TYPE (*mem))
1247       || TREE_THIS_VOLATILE (*mem))
1248     goto fail;
1249
1250   /* If we cannot move the reference out of the loop, fail.  */
1251   if (!for_each_index (mem, may_move_till, loop))
1252     goto fail;
1253
1254   hash = iterative_hash_expr (*mem, 0);
1255   slot = htab_find_slot_with_hash (mem_refs, *mem, hash, INSERT);
1256
1257   if (*slot)
1258     ref = *slot;
1259   else
1260     {
1261       ref = xmalloc (sizeof (struct mem_ref));
1262       ref->mem = *mem;
1263       ref->hash = hash;
1264       ref->locs = NULL;
1265       ref->is_stored = false;
1266       ref->vops = BITMAP_ALLOC (NULL);
1267       ref->next = *mem_ref_list;
1268       *mem_ref_list = ref;
1269       *slot = ref;
1270     }
1271   ref->is_stored |= is_stored;
1272
1273   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi,
1274                              SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1275     bitmap_set_bit (ref->vops, DECL_UID (SSA_NAME_VAR (vname)));
1276   record_mem_ref_loc (&ref->locs, stmt, mem);
1277   return;
1278
1279 fail:
1280   FOR_EACH_SSA_TREE_OPERAND (vname, stmt, oi,
1281                              SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1282     bitmap_set_bit (clobbered_vops, DECL_UID (SSA_NAME_VAR (vname)));
1283 }
1284
1285 /* Gathers memory references in LOOP.  Notes vops accessed through unrecognized
1286    statements in CLOBBERED_VOPS.  The list of the references found by
1287    the function is returned.  */
1288
1289 static struct mem_ref *
1290 gather_mem_refs (struct loop *loop, bitmap clobbered_vops)
1291 {
1292   basic_block *body = get_loop_body (loop);
1293   block_stmt_iterator bsi;
1294   unsigned i;
1295   struct mem_ref *mem_ref_list = NULL;
1296   htab_t mem_refs = htab_create (100, memref_hash, memref_eq, NULL);
1297
1298   for (i = 0; i < loop->num_nodes; i++)
1299     {
1300       for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
1301         gather_mem_refs_stmt (loop, mem_refs, clobbered_vops, bsi_stmt (bsi),
1302                               &mem_ref_list);
1303     }
1304
1305   free (body);
1306
1307   htab_delete (mem_refs);
1308   return mem_ref_list;
1309 }
1310
1311 /* Finds the vops accessed by more than one of the memory references described
1312    in MEM_REFS and marks them in CLOBBERED_VOPS.  */
1313
1314 static void
1315 find_more_ref_vops (struct mem_ref *mem_refs, bitmap clobbered_vops)
1316 {
1317   bitmap_head tmp, all_vops;
1318   struct mem_ref *ref;
1319
1320   bitmap_initialize (&tmp, &bitmap_default_obstack);
1321   bitmap_initialize (&all_vops, &bitmap_default_obstack);
1322
1323   for (ref = mem_refs; ref; ref = ref->next)
1324     {
1325       /* The vops that are already in all_vops are accessed by more than
1326          one memory reference.  */
1327       bitmap_and (&tmp, &all_vops, ref->vops);
1328       bitmap_ior_into (clobbered_vops, &tmp);
1329       bitmap_clear (&tmp);
1330
1331       bitmap_ior_into (&all_vops, ref->vops);
1332     }
1333
1334   bitmap_clear (&all_vops);
1335 }
1336
1337 /* Releases the memory occupied by REF.  */
1338
1339 static void
1340 free_mem_ref (struct mem_ref *ref)
1341 {
1342   free_mem_ref_locs (ref->locs);
1343   BITMAP_FREE (ref->vops);
1344   free (ref);
1345 }
1346
1347 /* Releases the memory occupied by REFS.  */
1348
1349 static void
1350 free_mem_refs (struct mem_ref *refs)
1351 {
1352   struct mem_ref *ref, *next;
1353
1354   for (ref = refs; ref; ref = next)
1355     {
1356       next = ref->next;
1357       free_mem_ref (ref);
1358     }
1359 }
1360
1361 /* Try to perform store motion for all memory references modified inside
1362    LOOP.  */
1363
1364 static void
1365 determine_lsm_loop (struct loop *loop)
1366 {
1367   unsigned n_exits;
1368   edge *exits = get_loop_exit_edges (loop, &n_exits);
1369   bitmap clobbered_vops;
1370   struct mem_ref *mem_refs;
1371
1372   if (!loop_suitable_for_sm (loop, exits, n_exits))
1373     {
1374       free (exits);
1375       return;
1376     }
1377
1378   /* Find the memory references in LOOP.  */
1379   clobbered_vops = BITMAP_ALLOC (NULL);
1380   mem_refs = gather_mem_refs (loop, clobbered_vops);
1381
1382   /* Find the vops that are used for more than one reference.  */
1383   find_more_ref_vops (mem_refs, clobbered_vops);
1384
1385   /* Hoist all suitable memory references.  */
1386   hoist_memory_references (loop, mem_refs, clobbered_vops, exits, n_exits);
1387
1388   free_mem_refs (mem_refs);
1389   free (exits);
1390   BITMAP_FREE (clobbered_vops);
1391 }
1392
1393 /* Try to perform store motion for all memory references modified inside
1394    any of LOOPS.  */
1395
1396 static void
1397 determine_lsm (struct loops *loops)
1398 {
1399   struct loop *loop;
1400
1401   if (!loops->tree_root->inner)
1402     return;
1403
1404   /* Pass the loops from the outermost and perform the store motion as
1405      suitable.  */
1406
1407   loop = loops->tree_root->inner;
1408   while (1)
1409     {
1410       determine_lsm_loop (loop);
1411
1412       if (loop->inner)
1413         {
1414           loop = loop->inner;
1415           continue;
1416         }
1417       while (!loop->next)
1418         {
1419           loop = loop->outer;
1420           if (loop == loops->tree_root)
1421             {
1422               loop_commit_inserts ();
1423               return;
1424             }
1425         }
1426       loop = loop->next;
1427     }
1428 }
1429
1430 /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
1431    for each such basic block bb records the outermost loop for that execution
1432    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
1433    blocks that contain a nonpure call.  */
1434
1435 static void
1436 fill_always_executed_in (struct loop *loop, sbitmap contains_call)
1437 {
1438   basic_block bb = NULL, *bbs, last = NULL;
1439   unsigned i;
1440   edge e;
1441   struct loop *inn_loop = loop;
1442
1443   if (!loop->header->aux)
1444     {
1445       bbs = get_loop_body_in_dom_order (loop);
1446
1447       for (i = 0; i < loop->num_nodes; i++)
1448         {
1449           edge_iterator ei;
1450           bb = bbs[i];
1451
1452           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1453             last = bb;
1454
1455           if (TEST_BIT (contains_call, bb->index))
1456             break;
1457
1458           FOR_EACH_EDGE (e, ei, bb->succs)
1459             if (!flow_bb_inside_loop_p (loop, e->dest))
1460               break;
1461           if (e)
1462             break;
1463
1464           /* A loop might be infinite (TODO use simple loop analysis
1465              to disprove this if possible).  */
1466           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1467             break;
1468
1469           if (!flow_bb_inside_loop_p (inn_loop, bb))
1470             break;
1471
1472           if (bb->loop_father->header == bb)
1473             {
1474               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1475                 break;
1476
1477               /* In a loop that is always entered we may proceed anyway.
1478                  But record that we entered it and stop once we leave it.  */
1479               inn_loop = bb->loop_father;
1480             }
1481         }
1482
1483       while (1)
1484         {
1485           last->aux = loop;
1486           if (last == loop->header)
1487             break;
1488           last = get_immediate_dominator (CDI_DOMINATORS, last);
1489         }
1490
1491       free (bbs);
1492     }
1493
1494   for (loop = loop->inner; loop; loop = loop->next)
1495     fill_always_executed_in (loop, contains_call);
1496 }
1497
1498 /* Compute the global information needed by the loop invariant motion pass.
1499    LOOPS is the loop tree.  */
1500
1501 static void
1502 tree_ssa_lim_initialize (struct loops *loops)
1503 {
1504   sbitmap contains_call = sbitmap_alloc (last_basic_block);
1505   block_stmt_iterator bsi;
1506   struct loop *loop;
1507   basic_block bb;
1508
1509   sbitmap_zero (contains_call);
1510   FOR_EACH_BB (bb)
1511     {
1512       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1513         {
1514           if (nonpure_call_p (bsi_stmt (bsi)))
1515             break;
1516         }
1517
1518       if (!bsi_end_p (bsi))
1519         SET_BIT (contains_call, bb->index);
1520     }
1521
1522   for (loop = loops->tree_root->inner; loop; loop = loop->next)
1523     fill_always_executed_in (loop, contains_call);
1524
1525   sbitmap_free (contains_call);
1526 }
1527
1528 /* Cleans up after the invariant motion pass.  */
1529
1530 static void
1531 tree_ssa_lim_finalize (void)
1532 {
1533   basic_block bb;
1534
1535   FOR_EACH_BB (bb)
1536     {
1537       bb->aux = NULL;
1538     }
1539 }
1540
1541 /* Moves invariants from LOOPS.  Only "expensive" invariants are moved out --
1542    i.e. those that are likely to be win regardless of the register pressure.  */
1543
1544 void
1545 tree_ssa_lim (struct loops *loops)
1546 {
1547   tree_ssa_lim_initialize (loops);
1548
1549   /* For each statement determine the outermost loop in that it is
1550      invariant and cost for computing the invariant.  */
1551   determine_invariantness ();
1552
1553   /* For each memory reference determine whether it is possible to hoist it
1554      out of the loop.  Force the necessary invariants to be moved out of the
1555      loops as well.  */
1556   determine_lsm (loops);
1557
1558   /* Move the expressions that are expensive enough.  */
1559   move_computations ();
1560
1561   tree_ssa_lim_finalize ();
1562 }