OSDN Git Service

* unroll.c: Removed.
[pf3gnuchains/gcc-fork.git] / gcc / loop.c
1 /* Perform various loop optimizations, including strength reduction.
2    Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
3    1998, 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 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 COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This is the loop optimization pass of the compiler.
23    It finds invariant computations within loops and moves them
24    to the beginning of the loop.  Then it identifies basic and
25    general induction variables.
26
27    Basic induction variables (BIVs) are a pseudo registers which are set within
28    a loop only by incrementing or decrementing its value.  General induction
29    variables (GIVs) are pseudo registers with a value which is a linear function
30    of a basic induction variable.  BIVs are recognized by `basic_induction_var';
31    GIVs by `general_induction_var'.
32
33    Once induction variables are identified, strength reduction is applied to the
34    general induction variables, and induction variable elimination is applied to
35    the basic induction variables.
36
37    It also finds cases where
38    a register is set within the loop by zero-extending a narrower value
39    and changes these to zero the entire register once before the loop
40    and merely copy the low part within the loop.
41
42    Most of the complexity is in heuristics to decide when it is worth
43    while to do these things.  */
44
45 #include "config.h"
46 #include "system.h"
47 #include "coretypes.h"
48 #include "tm.h"
49 #include "rtl.h"
50 #include "tm_p.h"
51 #include "function.h"
52 #include "expr.h"
53 #include "hard-reg-set.h"
54 #include "basic-block.h"
55 #include "insn-config.h"
56 #include "regs.h"
57 #include "recog.h"
58 #include "flags.h"
59 #include "real.h"
60 #include "cselib.h"
61 #include "except.h"
62 #include "toplev.h"
63 #include "predict.h"
64 #include "insn-flags.h"
65 #include "optabs.h"
66 #include "cfgloop.h"
67 #include "ggc.h"
68
69 /* Get the loop info pointer of a loop.  */
70 #define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux)
71
72 /* Get a pointer to the loop movables structure.  */
73 #define LOOP_MOVABLES(LOOP) (&LOOP_INFO (LOOP)->movables)
74
75 /* Get a pointer to the loop registers structure.  */
76 #define LOOP_REGS(LOOP) (&LOOP_INFO (LOOP)->regs)
77
78 /* Get a pointer to the loop induction variables structure.  */
79 #define LOOP_IVS(LOOP) (&LOOP_INFO (LOOP)->ivs)
80
81 /* Get the luid of an insn.  Catch the error of trying to reference the LUID
82    of an insn added during loop, since these don't have LUIDs.  */
83
84 #define INSN_LUID(INSN)                 \
85   (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \
86    : (abort (), -1))
87
88 #define REGNO_FIRST_LUID(REGNO)                 \
89   (REGNO_FIRST_UID (REGNO) < max_uid_for_loop   \
90         ? uid_luid[REGNO_FIRST_UID (REGNO)]     \
91         : 0)
92 #define REGNO_LAST_LUID(REGNO)                  \
93   (REGNO_LAST_UID (REGNO) < max_uid_for_loop    \
94         ? uid_luid[REGNO_LAST_UID (REGNO)]      \
95         : INT_MAX)
96
97 /* A "basic induction variable" or biv is a pseudo reg that is set
98    (within this loop) only by incrementing or decrementing it.  */
99 /* A "general induction variable" or giv is a pseudo reg whose
100    value is a linear function of a biv.  */
101
102 /* Bivs are recognized by `basic_induction_var';
103    Givs by `general_induction_var'.  */
104
105 /* An enum for the two different types of givs, those that are used
106    as memory addresses and those that are calculated into registers.  */
107 enum g_types
108 {
109   DEST_ADDR,
110   DEST_REG
111 };
112
113
114 /* A `struct induction' is created for every instruction that sets
115    an induction variable (either a biv or a giv).  */
116
117 struct induction
118 {
119   rtx insn;                     /* The insn that sets a biv or giv */
120   rtx new_reg;                  /* New register, containing strength reduced
121                                    version of this giv.  */
122   rtx src_reg;                  /* Biv from which this giv is computed.
123                                    (If this is a biv, then this is the biv.) */
124   enum g_types giv_type;        /* Indicate whether DEST_ADDR or DEST_REG */
125   rtx dest_reg;                 /* Destination register for insn: this is the
126                                    register which was the biv or giv.
127                                    For a biv, this equals src_reg.
128                                    For a DEST_ADDR type giv, this is 0.  */
129   rtx *location;                /* Place in the insn where this giv occurs.
130                                    If GIV_TYPE is DEST_REG, this is 0.  */
131                                 /* For a biv, this is the place where add_val
132                                    was found.  */
133   enum machine_mode mode;       /* The mode of this biv or giv */
134   rtx mem;                      /* For DEST_ADDR, the memory object.  */
135   rtx mult_val;                 /* Multiplicative factor for src_reg.  */
136   rtx add_val;                  /* Additive constant for that product.  */
137   int benefit;                  /* Gain from eliminating this insn.  */
138   rtx final_value;              /* If the giv is used outside the loop, and its
139                                    final value could be calculated, it is put
140                                    here, and the giv is made replaceable.  Set
141                                    the giv to this value before the loop.  */
142   unsigned combined_with;       /* The number of givs this giv has been
143                                    combined with.  If nonzero, this giv
144                                    cannot combine with any other giv.  */
145   unsigned replaceable : 1;     /* 1 if we can substitute the strength-reduced
146                                    variable for the original variable.
147                                    0 means they must be kept separate and the
148                                    new one must be copied into the old pseudo
149                                    reg each time the old one is set.  */
150   unsigned not_replaceable : 1; /* Used to prevent duplicating work.  This is
151                                    1 if we know that the giv definitely can
152                                    not be made replaceable, in which case we
153                                    don't bother checking the variable again
154                                    even if further info is available.
155                                    Both this and the above can be zero.  */
156   unsigned ignore : 1;          /* 1 prohibits further processing of giv */
157   unsigned always_computable : 1;/* 1 if this value is computable every
158                                     iteration.  */
159   unsigned always_executed : 1; /* 1 if this set occurs each iteration.  */
160   unsigned maybe_multiple : 1;  /* Only used for a biv and  1 if this biv
161                                    update may be done multiple times per
162                                    iteration.  */
163   unsigned cant_derive : 1;     /* For giv's, 1 if this giv cannot derive
164                                    another giv.  This occurs in many cases
165                                    where a giv's lifetime spans an update to
166                                    a biv.  */
167   unsigned maybe_dead : 1;      /* 1 if this giv might be dead.  In that case,
168                                    we won't use it to eliminate a biv, it
169                                    would probably lose.  */
170   unsigned auto_inc_opt : 1;    /* 1 if this giv had its increment output next
171                                    to it to try to form an auto-inc address.  */
172   unsigned shared : 1;
173   unsigned no_const_addval : 1; /* 1 if add_val does not contain a const.  */
174   int lifetime;                 /* Length of life of this giv */
175   rtx derive_adjustment;        /* If nonzero, is an adjustment to be
176                                    subtracted from add_val when this giv
177                                    derives another.  This occurs when the
178                                    giv spans a biv update by incrementation.  */
179   rtx ext_dependent;            /* If nonzero, is a sign or zero extension
180                                    if a biv on which this giv is dependent.  */
181   struct induction *next_iv;    /* For givs, links together all givs that are
182                                    based on the same biv.  For bivs, links
183                                    together all biv entries that refer to the
184                                    same biv register.  */
185   struct induction *same;       /* For givs, if the giv has been combined with
186                                    another giv, this points to the base giv.
187                                    The base giv will have COMBINED_WITH nonzero.
188                                    For bivs, if the biv has the same LOCATION
189                                    than another biv, this points to the base
190                                    biv.  */
191   struct induction *same_insn;  /* If there are multiple identical givs in
192                                    the same insn, then all but one have this
193                                    field set, and they all point to the giv
194                                    that doesn't have this field set.  */
195   rtx last_use;                 /* For a giv made from a biv increment, this is
196                                    a substitute for the lifetime information.  */
197 };
198
199
200 /* A `struct iv_class' is created for each biv.  */
201
202 struct iv_class
203 {
204   unsigned int regno;           /* Pseudo reg which is the biv.  */
205   int biv_count;                /* Number of insns setting this reg.  */
206   struct induction *biv;        /* List of all insns that set this reg.  */
207   int giv_count;                /* Number of DEST_REG givs computed from this
208                                    biv.  The resulting count is only used in
209                                    check_dbra_loop.  */
210   struct induction *giv;        /* List of all insns that compute a giv
211                                    from this reg.  */
212   int total_benefit;            /* Sum of BENEFITs of all those givs.  */
213   rtx initial_value;            /* Value of reg at loop start.  */
214   rtx initial_test;             /* Test performed on BIV before loop.  */
215   rtx final_value;              /* Value of reg at loop end, if known.  */
216   struct iv_class *next;        /* Links all class structures together.  */
217   rtx init_insn;                /* insn which initializes biv, 0 if none.  */
218   rtx init_set;                 /* SET of INIT_INSN, if any.  */
219   unsigned incremented : 1;     /* 1 if somewhere incremented/decremented */
220   unsigned eliminable : 1;      /* 1 if plausible candidate for
221                                    elimination.  */
222   unsigned nonneg : 1;          /* 1 if we added a REG_NONNEG note for
223                                    this.  */
224   unsigned reversed : 1;        /* 1 if we reversed the loop that this
225                                    biv controls.  */
226   unsigned all_reduced : 1;     /* 1 if all givs using this biv have
227                                    been reduced.  */
228 };
229
230
231 /* Definitions used by the basic induction variable discovery code.  */
232 enum iv_mode
233 {
234   UNKNOWN_INDUCT,
235   BASIC_INDUCT,
236   NOT_BASIC_INDUCT,
237   GENERAL_INDUCT
238 };
239
240
241 /* A `struct iv' is created for every register.  */
242
243 struct iv
244 {
245   enum iv_mode type;
246   union
247   {
248     struct iv_class *class;
249     struct induction *info;
250   } iv;
251 };
252
253
254 #define REG_IV_TYPE(ivs, n) ivs->regs[n].type
255 #define REG_IV_INFO(ivs, n) ivs->regs[n].iv.info
256 #define REG_IV_CLASS(ivs, n) ivs->regs[n].iv.class
257
258
259 struct loop_ivs
260 {
261   /* Indexed by register number, contains pointer to `struct
262      iv' if register is an induction variable.  */
263   struct iv *regs;
264
265   /* Size of regs array.  */
266   unsigned int n_regs;
267
268   /* The head of a list which links together (via the next field)
269      every iv class for the current loop.  */
270   struct iv_class *list;
271 };
272
273
274 typedef struct loop_mem_info
275 {
276   rtx mem;      /* The MEM itself.  */
277   rtx reg;      /* Corresponding pseudo, if any.  */
278   int optimize; /* Nonzero if we can optimize access to this MEM.  */
279 } loop_mem_info;
280
281
282
283 struct loop_reg
284 {
285   /* Number of times the reg is set during the loop being scanned.
286      During code motion, a negative value indicates a reg that has
287      been made a candidate; in particular -2 means that it is an
288      candidate that we know is equal to a constant and -1 means that
289      it is a candidate not known equal to a constant.  After code
290      motion, regs moved have 0 (which is accurate now) while the
291      failed candidates have the original number of times set.
292
293      Therefore, at all times, == 0 indicates an invariant register;
294      < 0 a conditionally invariant one.  */
295   int set_in_loop;
296
297   /* Original value of set_in_loop; same except that this value
298      is not set negative for a reg whose sets have been made candidates
299      and not set to 0 for a reg that is moved.  */
300   int n_times_set;
301
302   /* Contains the insn in which a register was used if it was used
303      exactly once; contains const0_rtx if it was used more than once.  */
304   rtx single_usage;
305
306   /* Nonzero indicates that the register cannot be moved or strength
307      reduced.  */
308   char may_not_optimize;
309
310   /* Nonzero means reg N has already been moved out of one loop.
311      This reduces the desire to move it out of another.  */
312   char moved_once;
313 };
314
315
316 struct loop_regs
317 {
318   int num;                      /* Number of regs used in table.  */
319   int size;                     /* Size of table.  */
320   struct loop_reg *array;       /* Register usage info. array.  */
321   int multiple_uses;            /* Nonzero if a reg has multiple uses.  */
322 };
323
324
325
326 struct loop_movables
327 {
328   /* Head of movable chain.  */
329   struct movable *head;
330   /* Last movable in chain.  */
331   struct movable *last;
332 };
333
334
335 /* Information pertaining to a loop.  */
336
337 struct loop_info
338 {
339   /* Nonzero if there is a subroutine call in the current loop.  */
340   int has_call;
341   /* Nonzero if there is a libcall in the current loop.  */
342   int has_libcall;
343   /* Nonzero if there is a non constant call in the current loop.  */
344   int has_nonconst_call;
345   /* Nonzero if there is a prefetch instruction in the current loop.  */
346   int has_prefetch;
347   /* Nonzero if there is a volatile memory reference in the current
348      loop.  */
349   int has_volatile;
350   /* Nonzero if there is a tablejump in the current loop.  */
351   int has_tablejump;
352   /* Nonzero if there are ways to leave the loop other than falling
353      off the end.  */
354   int has_multiple_exit_targets;
355   /* Nonzero if there is an indirect jump in the current function.  */
356   int has_indirect_jump;
357   /* Register or constant initial loop value.  */
358   rtx initial_value;
359   /* Register or constant value used for comparison test.  */
360   rtx comparison_value;
361   /* Register or constant approximate final value.  */
362   rtx final_value;
363   /* Register or constant initial loop value with term common to
364      final_value removed.  */
365   rtx initial_equiv_value;
366   /* Register or constant final loop value with term common to
367      initial_value removed.  */
368   rtx final_equiv_value;
369   /* Register corresponding to iteration variable.  */
370   rtx iteration_var;
371   /* Constant loop increment.  */
372   rtx increment;
373   enum rtx_code comparison_code;
374   /* Holds the number of loop iterations.  It is zero if the number
375      could not be calculated.  Must be unsigned since the number of
376      iterations can be as high as 2^wordsize - 1.  For loops with a
377      wider iterator, this number will be zero if the number of loop
378      iterations is too large for an unsigned integer to hold.  */
379   unsigned HOST_WIDE_INT n_iterations;
380   int used_count_register;
381   /* The loop iterator induction variable.  */
382   struct iv_class *iv;
383   /* List of MEMs that are stored in this loop.  */
384   rtx store_mems;
385   /* Array of MEMs that are used (read or written) in this loop, but
386      cannot be aliased by anything in this loop, except perhaps
387      themselves.  In other words, if mems[i] is altered during
388      the loop, it is altered by an expression that is rtx_equal_p to
389      it.  */
390   loop_mem_info *mems;
391   /* The index of the next available slot in MEMS.  */
392   int mems_idx;
393   /* The number of elements allocated in MEMS.  */
394   int mems_allocated;
395   /* Nonzero if we don't know what MEMs were changed in the current
396      loop.  This happens if the loop contains a call (in which case
397      `has_call' will also be set) or if we store into more than
398      NUM_STORES MEMs.  */
399   int unknown_address_altered;
400   /* The above doesn't count any readonly memory locations that are
401      stored.  This does.  */
402   int unknown_constant_address_altered;
403   /* Count of memory write instructions discovered in the loop.  */
404   int num_mem_sets;
405   /* The insn where the first of these was found.  */
406   rtx first_loop_store_insn;
407   /* The chain of movable insns in loop.  */
408   struct loop_movables movables;
409   /* The registers used the in loop.  */
410   struct loop_regs regs;
411   /* The induction variable information in loop.  */
412   struct loop_ivs ivs;
413   /* Nonzero if call is in pre_header extended basic block.  */
414   int pre_header_has_call;
415 };
416
417 /* Not really meaningful values, but at least something.  */
418 #ifndef SIMULTANEOUS_PREFETCHES
419 #define SIMULTANEOUS_PREFETCHES 3
420 #endif
421 #ifndef PREFETCH_BLOCK
422 #define PREFETCH_BLOCK 32
423 #endif
424 #ifndef HAVE_prefetch
425 #define HAVE_prefetch 0
426 #define CODE_FOR_prefetch 0
427 #define gen_prefetch(a,b,c) (abort(), NULL_RTX)
428 #endif
429
430 /* Give up the prefetch optimizations once we exceed a given threshold.
431    It is unlikely that we would be able to optimize something in a loop
432    with so many detected prefetches.  */
433 #define MAX_PREFETCHES 100
434 /* The number of prefetch blocks that are beneficial to fetch at once before
435    a loop with a known (and low) iteration count.  */
436 #define PREFETCH_BLOCKS_BEFORE_LOOP_MAX  6
437 /* For very tiny loops it is not worthwhile to prefetch even before the loop,
438    since it is likely that the data are already in the cache.  */
439 #define PREFETCH_BLOCKS_BEFORE_LOOP_MIN  2
440
441 /* Parameterize some prefetch heuristics so they can be turned on and off
442    easily for performance testing on new architectures.  These can be
443    defined in target-dependent files.  */
444
445 /* Prefetch is worthwhile only when loads/stores are dense.  */
446 #ifndef PREFETCH_ONLY_DENSE_MEM
447 #define PREFETCH_ONLY_DENSE_MEM 1
448 #endif
449
450 /* Define what we mean by "dense" loads and stores; This value divided by 256
451    is the minimum percentage of memory references that worth prefetching.  */
452 #ifndef PREFETCH_DENSE_MEM
453 #define PREFETCH_DENSE_MEM 220
454 #endif
455
456 /* Do not prefetch for a loop whose iteration count is known to be low.  */
457 #ifndef PREFETCH_NO_LOW_LOOPCNT
458 #define PREFETCH_NO_LOW_LOOPCNT 1
459 #endif
460
461 /* Define what we mean by a "low" iteration count.  */
462 #ifndef PREFETCH_LOW_LOOPCNT
463 #define PREFETCH_LOW_LOOPCNT 32
464 #endif
465
466 /* Do not prefetch for a loop that contains a function call; such a loop is
467    probably not an internal loop.  */
468 #ifndef PREFETCH_NO_CALL
469 #define PREFETCH_NO_CALL 1
470 #endif
471
472 /* Do not prefetch accesses with an extreme stride.  */
473 #ifndef PREFETCH_NO_EXTREME_STRIDE
474 #define PREFETCH_NO_EXTREME_STRIDE 1
475 #endif
476
477 /* Define what we mean by an "extreme" stride.  */
478 #ifndef PREFETCH_EXTREME_STRIDE
479 #define PREFETCH_EXTREME_STRIDE 4096
480 #endif
481
482 /* Define a limit to how far apart indices can be and still be merged
483    into a single prefetch.  */
484 #ifndef PREFETCH_EXTREME_DIFFERENCE
485 #define PREFETCH_EXTREME_DIFFERENCE 4096
486 #endif
487
488 /* Issue prefetch instructions before the loop to fetch data to be used
489    in the first few loop iterations.  */
490 #ifndef PREFETCH_BEFORE_LOOP
491 #define PREFETCH_BEFORE_LOOP 1
492 #endif
493
494 /* Do not handle reversed order prefetches (negative stride).  */
495 #ifndef PREFETCH_NO_REVERSE_ORDER
496 #define PREFETCH_NO_REVERSE_ORDER 1
497 #endif
498
499 /* Prefetch even if the GIV is in conditional code.  */
500 #ifndef PREFETCH_CONDITIONAL
501 #define PREFETCH_CONDITIONAL 1
502 #endif
503
504 #define LOOP_REG_LIFETIME(LOOP, REGNO) \
505 ((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
506
507 #define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
508 ((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
509  || REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
510
511 #define LOOP_REGNO_NREGS(REGNO, SET_DEST) \
512 ((REGNO) < FIRST_PSEUDO_REGISTER \
513  ? (int) hard_regno_nregs[(REGNO)][GET_MODE (SET_DEST)] : 1)
514
515
516 /* Vector mapping INSN_UIDs to luids.
517    The luids are like uids but increase monotonically always.
518    We use them to see whether a jump comes from outside a given loop.  */
519
520 static int *uid_luid;
521
522 /* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
523    number the insn is contained in.  */
524
525 static struct loop **uid_loop;
526
527 /* 1 + largest uid of any insn.  */
528
529 static int max_uid_for_loop;
530
531 /* Number of loops detected in current function.  Used as index to the
532    next few tables.  */
533
534 static int max_loop_num;
535
536 /* Bound on pseudo register number before loop optimization.
537    A pseudo has valid regscan info if its number is < max_reg_before_loop.  */
538 static unsigned int max_reg_before_loop;
539
540 /* The value to pass to the next call of reg_scan_update.  */
541 static int loop_max_reg;
542 \f
543 /* During the analysis of a loop, a chain of `struct movable's
544    is made to record all the movable insns found.
545    Then the entire chain can be scanned to decide which to move.  */
546
547 struct movable
548 {
549   rtx insn;                     /* A movable insn */
550   rtx set_src;                  /* The expression this reg is set from.  */
551   rtx set_dest;                 /* The destination of this SET.  */
552   rtx dependencies;             /* When INSN is libcall, this is an EXPR_LIST
553                                    of any registers used within the LIBCALL.  */
554   int consec;                   /* Number of consecutive following insns
555                                    that must be moved with this one.  */
556   unsigned int regno;           /* The register it sets */
557   short lifetime;               /* lifetime of that register;
558                                    may be adjusted when matching movables
559                                    that load the same value are found.  */
560   short savings;                /* Number of insns we can move for this reg,
561                                    including other movables that force this
562                                    or match this one.  */
563   ENUM_BITFIELD(machine_mode) savemode : 8;   /* Nonzero means it is a mode for
564                                    a low part that we should avoid changing when
565                                    clearing the rest of the reg.  */
566   unsigned int cond : 1;        /* 1 if only conditionally movable */
567   unsigned int force : 1;       /* 1 means MUST move this insn */
568   unsigned int global : 1;      /* 1 means reg is live outside this loop */
569                 /* If PARTIAL is 1, GLOBAL means something different:
570                    that the reg is live outside the range from where it is set
571                    to the following label.  */
572   unsigned int done : 1;        /* 1 inhibits further processing of this */
573
574   unsigned int partial : 1;     /* 1 means this reg is used for zero-extending.
575                                    In particular, moving it does not make it
576                                    invariant.  */
577   unsigned int move_insn : 1;   /* 1 means that we call emit_move_insn to
578                                    load SRC, rather than copying INSN.  */
579   unsigned int move_insn_first:1;/* Same as above, if this is necessary for the
580                                     first insn of a consecutive sets group.  */
581   unsigned int is_equiv : 1;    /* 1 means a REG_EQUIV is present on INSN.  */
582   unsigned int insert_temp : 1;  /* 1 means we copy to a new pseudo and replace
583                                     the original insn with a copy from that
584                                     pseudo, rather than deleting it.  */
585   struct movable *match;        /* First entry for same value */
586   struct movable *forces;       /* An insn that must be moved if this is */
587   struct movable *next;
588 };
589
590
591 static FILE *loop_dump_stream;
592
593 /* Forward declarations.  */
594
595 static void invalidate_loops_containing_label (rtx);
596 static void find_and_verify_loops (rtx, struct loops *);
597 static void mark_loop_jump (rtx, struct loop *);
598 static void prescan_loop (struct loop *);
599 static int reg_in_basic_block_p (rtx, rtx);
600 static int consec_sets_invariant_p (const struct loop *, rtx, int, rtx);
601 static int labels_in_range_p (rtx, int);
602 static void count_one_set (struct loop_regs *, rtx, rtx, rtx *);
603 static void note_addr_stored (rtx, rtx, void *);
604 static void note_set_pseudo_multiple_uses (rtx, rtx, void *);
605 static int loop_reg_used_before_p (const struct loop *, rtx, rtx);
606 static rtx find_regs_nested (rtx, rtx);
607 static void scan_loop (struct loop*, int);
608 #if 0
609 static void replace_call_address (rtx, rtx, rtx);
610 #endif
611 static rtx skip_consec_insns (rtx, int);
612 static int libcall_benefit (rtx);
613 static rtx libcall_other_reg (rtx, rtx);
614 static void record_excess_regs (rtx, rtx, rtx *);
615 static void ignore_some_movables (struct loop_movables *);
616 static void force_movables (struct loop_movables *);
617 static void combine_movables (struct loop_movables *, struct loop_regs *);
618 static int num_unmoved_movables (const struct loop *);
619 static int regs_match_p (rtx, rtx, struct loop_movables *);
620 static int rtx_equal_for_loop_p (rtx, rtx, struct loop_movables *,
621                                  struct loop_regs *);
622 static void add_label_notes (rtx, rtx);
623 static void move_movables (struct loop *loop, struct loop_movables *, int,
624                            int);
625 static void loop_movables_add (struct loop_movables *, struct movable *);
626 static void loop_movables_free (struct loop_movables *);
627 static int count_nonfixed_reads (const struct loop *, rtx);
628 static void loop_bivs_find (struct loop *);
629 static void loop_bivs_init_find (struct loop *);
630 static void loop_bivs_check (struct loop *);
631 static void loop_givs_find (struct loop *);
632 static void loop_givs_check (struct loop *);
633 static int loop_biv_eliminable_p (struct loop *, struct iv_class *, int, int);
634 static int loop_giv_reduce_benefit (struct loop *, struct iv_class *,
635                                     struct induction *, rtx);
636 static void loop_givs_dead_check (struct loop *, struct iv_class *);
637 static void loop_givs_reduce (struct loop *, struct iv_class *);
638 static void loop_givs_rescan (struct loop *, struct iv_class *, rtx *);
639 static void loop_ivs_free (struct loop *);
640 static void strength_reduce (struct loop *, int);
641 static void find_single_use_in_loop (struct loop_regs *, rtx, rtx);
642 static int valid_initial_value_p (rtx, rtx, int, rtx);
643 static void find_mem_givs (const struct loop *, rtx, rtx, int, int);
644 static void record_biv (struct loop *, struct induction *, rtx, rtx, rtx,
645                         rtx, rtx *, int, int);
646 static void check_final_value (const struct loop *, struct induction *);
647 static void loop_ivs_dump (const struct loop *, FILE *, int);
648 static void loop_iv_class_dump (const struct iv_class *, FILE *, int);
649 static void loop_biv_dump (const struct induction *, FILE *, int);
650 static void loop_giv_dump (const struct induction *, FILE *, int);
651 static void record_giv (const struct loop *, struct induction *, rtx, rtx,
652                         rtx, rtx, rtx, rtx, int, enum g_types, int, int,
653                         rtx *);
654 static void update_giv_derive (const struct loop *, rtx);
655 static void check_ext_dependent_givs (const struct loop *, struct iv_class *);
656 static int basic_induction_var (const struct loop *, rtx, enum machine_mode,
657                                 rtx, rtx, rtx *, rtx *, rtx **);
658 static rtx simplify_giv_expr (const struct loop *, rtx, rtx *, int *);
659 static int general_induction_var (const struct loop *loop, rtx, rtx *, rtx *,
660                                   rtx *, rtx *, int, int *, enum machine_mode);
661 static int consec_sets_giv (const struct loop *, int, rtx, rtx, rtx, rtx *,
662                             rtx *, rtx *, rtx *);
663 static int check_dbra_loop (struct loop *, int);
664 static rtx express_from_1 (rtx, rtx, rtx);
665 static rtx combine_givs_p (struct induction *, struct induction *);
666 static int cmp_combine_givs_stats (const void *, const void *);
667 static void combine_givs (struct loop_regs *, struct iv_class *);
668 static int product_cheap_p (rtx, rtx);
669 static int maybe_eliminate_biv (const struct loop *, struct iv_class *, int,
670                                 int, int);
671 static int maybe_eliminate_biv_1 (const struct loop *, rtx, rtx,
672                                   struct iv_class *, int, basic_block, rtx);
673 static int last_use_this_basic_block (rtx, rtx);
674 static void record_initial (rtx, rtx, void *);
675 static void update_reg_last_use (rtx, rtx);
676 static rtx next_insn_in_loop (const struct loop *, rtx);
677 static void loop_regs_scan (const struct loop *, int);
678 static int count_insns_in_loop (const struct loop *);
679 static int find_mem_in_note_1 (rtx *, void *);
680 static rtx find_mem_in_note (rtx);
681 static void load_mems (const struct loop *);
682 static int insert_loop_mem (rtx *, void *);
683 static int replace_loop_mem (rtx *, void *);
684 static void replace_loop_mems (rtx, rtx, rtx, int);
685 static int replace_loop_reg (rtx *, void *);
686 static void replace_loop_regs (rtx insn, rtx, rtx);
687 static void note_reg_stored (rtx, rtx, void *);
688 static void try_copy_prop (const struct loop *, rtx, unsigned int);
689 static void try_swap_copy_prop (const struct loop *, rtx, unsigned int);
690 static rtx check_insn_for_givs (struct loop *, rtx, int, int);
691 static rtx check_insn_for_bivs (struct loop *, rtx, int, int);
692 static rtx gen_add_mult (rtx, rtx, rtx, rtx);
693 static void loop_regs_update (const struct loop *, rtx);
694 static int iv_add_mult_cost (rtx, rtx, rtx, rtx);
695 static int loop_invariant_p (const struct loop *, rtx);
696 static rtx loop_insn_hoist (const struct loop *, rtx);
697 static void loop_iv_add_mult_emit_before (const struct loop *, rtx, rtx, rtx,
698                                           rtx, basic_block, rtx);
699 static rtx loop_insn_emit_before (const struct loop *, basic_block,
700                                   rtx, rtx);
701 static int loop_insn_first_p (rtx, rtx);
702 static rtx get_condition_for_loop (const struct loop *, rtx);
703 static void loop_iv_add_mult_sink (const struct loop *, rtx, rtx, rtx, rtx);
704 static void loop_iv_add_mult_hoist (const struct loop *, rtx, rtx, rtx, rtx);
705 static rtx extend_value_for_giv (struct induction *, rtx);
706 static rtx loop_insn_sink (const struct loop *, rtx);
707
708 static rtx loop_insn_emit_after (const struct loop *, basic_block, rtx, rtx);
709 static rtx loop_call_insn_emit_before (const struct loop *, basic_block,
710                                        rtx, rtx);
711 static rtx loop_call_insn_hoist (const struct loop *, rtx);
712 static rtx loop_insn_sink_or_swim (const struct loop *, rtx);
713
714 static void loop_dump_aux (const struct loop *, FILE *, int);
715 static void loop_delete_insns (rtx, rtx);
716 static HOST_WIDE_INT remove_constant_addition (rtx *);
717 static rtx gen_load_of_final_value (rtx, rtx);
718 void debug_ivs (const struct loop *);
719 void debug_iv_class (const struct iv_class *);
720 void debug_biv (const struct induction *);
721 void debug_giv (const struct induction *);
722 void debug_loop (const struct loop *);
723 void debug_loops (const struct loops *);
724
725 typedef struct loop_replace_args
726 {
727   rtx match;
728   rtx replacement;
729   rtx insn;
730 } loop_replace_args;
731
732 /* Nonzero iff INSN is between START and END, inclusive.  */
733 #define INSN_IN_RANGE_P(INSN, START, END)       \
734   (INSN_UID (INSN) < max_uid_for_loop           \
735    && INSN_LUID (INSN) >= INSN_LUID (START)     \
736    && INSN_LUID (INSN) <= INSN_LUID (END))
737
738 /* Indirect_jump_in_function is computed once per function.  */
739 static int indirect_jump_in_function;
740 static int indirect_jump_in_function_p (rtx);
741
742 static int compute_luids (rtx, rtx, int);
743
744 static int biv_elimination_giv_has_0_offset (struct induction *,
745                                              struct induction *, rtx);
746 \f
747 /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
748    copy the value of the strength reduced giv to its original register.  */
749 static int copy_cost;
750
751 /* Cost of using a register, to normalize the benefits of a giv.  */
752 static int reg_address_cost;
753
754 void
755 init_loop (void)
756 {
757   rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
758
759   reg_address_cost = address_cost (reg, SImode);
760
761   copy_cost = COSTS_N_INSNS (1);
762 }
763 \f
764 /* Compute the mapping from uids to luids.
765    LUIDs are numbers assigned to insns, like uids,
766    except that luids increase monotonically through the code.
767    Start at insn START and stop just before END.  Assign LUIDs
768    starting with PREV_LUID + 1.  Return the last assigned LUID + 1.  */
769 static int
770 compute_luids (rtx start, rtx end, int prev_luid)
771 {
772   int i;
773   rtx insn;
774
775   for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
776     {
777       if (INSN_UID (insn) >= max_uid_for_loop)
778         continue;
779       /* Don't assign luids to line-number NOTEs, so that the distance in
780          luids between two insns is not affected by -g.  */
781       if (!NOTE_P (insn)
782           || NOTE_LINE_NUMBER (insn) <= 0)
783         uid_luid[INSN_UID (insn)] = ++i;
784       else
785         /* Give a line number note the same luid as preceding insn.  */
786         uid_luid[INSN_UID (insn)] = i;
787     }
788   return i + 1;
789 }
790 \f
791 /* Entry point of this file.  Perform loop optimization
792    on the current function.  F is the first insn of the function
793    and DUMPFILE is a stream for output of a trace of actions taken
794    (or 0 if none should be output).  */
795
796 void
797 loop_optimize (rtx f, FILE *dumpfile, int flags)
798 {
799   rtx insn;
800   int i;
801   struct loops loops_data;
802   struct loops *loops = &loops_data;
803   struct loop_info *loops_info;
804
805   loop_dump_stream = dumpfile;
806
807   init_recog_no_volatile ();
808
809   max_reg_before_loop = max_reg_num ();
810   loop_max_reg = max_reg_before_loop;
811
812   regs_may_share = 0;
813
814   /* Count the number of loops.  */
815
816   max_loop_num = 0;
817   for (insn = f; insn; insn = NEXT_INSN (insn))
818     {
819       if (NOTE_P (insn)
820           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
821         max_loop_num++;
822     }
823
824   /* Don't waste time if no loops.  */
825   if (max_loop_num == 0)
826     return;
827
828   loops->num = max_loop_num;
829
830   /* Get size to use for tables indexed by uids.
831      Leave some space for labels allocated by find_and_verify_loops.  */
832   max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
833
834   uid_luid = xcalloc (max_uid_for_loop, sizeof (int));
835   uid_loop = xcalloc (max_uid_for_loop, sizeof (struct loop *));
836
837   /* Allocate storage for array of loops.  */
838   loops->array = xcalloc (loops->num, sizeof (struct loop));
839
840   /* Find and process each loop.
841      First, find them, and record them in order of their beginnings.  */
842   find_and_verify_loops (f, loops);
843
844   /* Allocate and initialize auxiliary loop information.  */
845   loops_info = xcalloc (loops->num, sizeof (struct loop_info));
846   for (i = 0; i < (int) loops->num; i++)
847     loops->array[i].aux = loops_info + i;
848
849   /* Now find all register lifetimes.  This must be done after
850      find_and_verify_loops, because it might reorder the insns in the
851      function.  */
852   reg_scan (f, max_reg_before_loop, 1);
853
854   /* This must occur after reg_scan so that registers created by gcse
855      will have entries in the register tables.
856
857      We could have added a call to reg_scan after gcse_main in toplev.c,
858      but moving this call to init_alias_analysis is more efficient.  */
859   init_alias_analysis ();
860
861   /* See if we went too far.  Note that get_max_uid already returns
862      one more that the maximum uid of all insn.  */
863   if (get_max_uid () > max_uid_for_loop)
864     abort ();
865   /* Now reset it to the actual size we need.  See above.  */
866   max_uid_for_loop = get_max_uid ();
867
868   /* find_and_verify_loops has already called compute_luids, but it
869      might have rearranged code afterwards, so we need to recompute
870      the luids now.  */
871   compute_luids (f, NULL_RTX, 0);
872
873   /* Don't leave gaps in uid_luid for insns that have been
874      deleted.  It is possible that the first or last insn
875      using some register has been deleted by cross-jumping.
876      Make sure that uid_luid for that former insn's uid
877      points to the general area where that insn used to be.  */
878   for (i = 0; i < max_uid_for_loop; i++)
879     {
880       uid_luid[0] = uid_luid[i];
881       if (uid_luid[0] != 0)
882         break;
883     }
884   for (i = 0; i < max_uid_for_loop; i++)
885     if (uid_luid[i] == 0)
886       uid_luid[i] = uid_luid[i - 1];
887
888   /* Determine if the function has indirect jump.  On some systems
889      this prevents low overhead loop instructions from being used.  */
890   indirect_jump_in_function = indirect_jump_in_function_p (f);
891
892   /* Now scan the loops, last ones first, since this means inner ones are done
893      before outer ones.  */
894   for (i = max_loop_num - 1; i >= 0; i--)
895     {
896       struct loop *loop = &loops->array[i];
897
898       if (! loop->invalid && loop->end)
899         {
900           scan_loop (loop, flags);
901           ggc_collect ();
902         }
903     }
904
905   end_alias_analysis ();
906
907   /* Clean up.  */
908   for (i = 0; i < (int) loops->num; i++)
909     free (loops_info[i].mems);
910   
911   free (uid_luid);
912   free (uid_loop);
913   free (loops_info);
914   free (loops->array);
915 }
916 \f
917 /* Returns the next insn, in execution order, after INSN.  START and
918    END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
919    respectively.  LOOP->TOP, if non-NULL, is the top of the loop in the
920    insn-stream; it is used with loops that are entered near the
921    bottom.  */
922
923 static rtx
924 next_insn_in_loop (const struct loop *loop, rtx insn)
925 {
926   insn = NEXT_INSN (insn);
927
928   if (insn == loop->end)
929     {
930       if (loop->top)
931         /* Go to the top of the loop, and continue there.  */
932         insn = loop->top;
933       else
934         /* We're done.  */
935         insn = NULL_RTX;
936     }
937
938   if (insn == loop->scan_start)
939     /* We're done.  */
940     insn = NULL_RTX;
941
942   return insn;
943 }
944
945 /* Find any register references hidden inside X and add them to
946    the dependency list DEPS.  This is used to look inside CLOBBER (MEM
947    when checking whether a PARALLEL can be pulled out of a loop.  */
948
949 static rtx
950 find_regs_nested (rtx deps, rtx x)
951 {
952   enum rtx_code code = GET_CODE (x);
953   if (code == REG)
954     deps = gen_rtx_EXPR_LIST (VOIDmode, x, deps);
955   else
956     {
957       const char *fmt = GET_RTX_FORMAT (code);
958       int i, j;
959       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
960         {
961           if (fmt[i] == 'e')
962             deps = find_regs_nested (deps, XEXP (x, i));
963           else if (fmt[i] == 'E')
964             for (j = 0; j < XVECLEN (x, i); j++)
965               deps = find_regs_nested (deps, XVECEXP (x, i, j));
966         }
967     }
968   return deps;
969 }
970
971 /* Optimize one loop described by LOOP.  */
972
973 /* ??? Could also move memory writes out of loops if the destination address
974    is invariant, the source is invariant, the memory write is not volatile,
975    and if we can prove that no read inside the loop can read this address
976    before the write occurs.  If there is a read of this address after the
977    write, then we can also mark the memory read as invariant.  */
978
979 static void
980 scan_loop (struct loop *loop, int flags)
981 {
982   struct loop_info *loop_info = LOOP_INFO (loop);
983   struct loop_regs *regs = LOOP_REGS (loop);
984   int i;
985   rtx loop_start = loop->start;
986   rtx loop_end = loop->end;
987   rtx p;
988   /* 1 if we are scanning insns that could be executed zero times.  */
989   int maybe_never = 0;
990   /* 1 if we are scanning insns that might never be executed
991      due to a subroutine call which might exit before they are reached.  */
992   int call_passed = 0;
993   /* Number of insns in the loop.  */
994   int insn_count;
995   int tem;
996   rtx temp, update_start, update_end;
997   /* The SET from an insn, if it is the only SET in the insn.  */
998   rtx set, set1;
999   /* Chain describing insns movable in current loop.  */
1000   struct loop_movables *movables = LOOP_MOVABLES (loop);
1001   /* Ratio of extra register life span we can justify
1002      for saving an instruction.  More if loop doesn't call subroutines
1003      since in that case saving an insn makes more difference
1004      and more registers are available.  */
1005   int threshold;
1006   int in_libcall;
1007
1008   loop->top = 0;
1009
1010   movables->head = 0;
1011   movables->last = 0;
1012
1013   /* Determine whether this loop starts with a jump down to a test at
1014      the end.  This will occur for a small number of loops with a test
1015      that is too complex to duplicate in front of the loop.
1016
1017      We search for the first insn or label in the loop, skipping NOTEs.
1018      However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
1019      (because we might have a loop executed only once that contains a
1020      loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
1021      (in case we have a degenerate loop).
1022
1023      Note that if we mistakenly think that a loop is entered at the top
1024      when, in fact, it is entered at the exit test, the only effect will be
1025      slightly poorer optimization.  Making the opposite error can generate
1026      incorrect code.  Since very few loops now start with a jump to the
1027      exit test, the code here to detect that case is very conservative.  */
1028
1029   for (p = NEXT_INSN (loop_start);
1030        p != loop_end
1031          && !LABEL_P (p) && ! INSN_P (p)
1032          && (!NOTE_P (p)
1033              || (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
1034                  && NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
1035        p = NEXT_INSN (p))
1036     ;
1037
1038   loop->scan_start = p;
1039
1040   /* If loop end is the end of the current function, then emit a
1041      NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
1042      note insn.  This is the position we use when sinking insns out of
1043      the loop.  */
1044   if (NEXT_INSN (loop->end) != 0)
1045     loop->sink = NEXT_INSN (loop->end);
1046   else
1047     loop->sink = emit_note_after (NOTE_INSN_DELETED, loop->end);
1048
1049   /* Set up variables describing this loop.  */
1050   prescan_loop (loop);
1051   threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
1052
1053   /* If loop has a jump before the first label,
1054      the true entry is the target of that jump.
1055      Start scan from there.
1056      But record in LOOP->TOP the place where the end-test jumps
1057      back to so we can scan that after the end of the loop.  */
1058   if (JUMP_P (p)
1059       /* Loop entry must be unconditional jump (and not a RETURN)  */
1060       && any_uncondjump_p (p)
1061       && JUMP_LABEL (p) != 0
1062       /* Check to see whether the jump actually
1063          jumps out of the loop (meaning it's no loop).
1064          This case can happen for things like
1065          do {..} while (0).  If this label was generated previously
1066          by loop, we can't tell anything about it and have to reject
1067          the loop.  */
1068       && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
1069     {
1070       loop->top = next_label (loop->scan_start);
1071       loop->scan_start = JUMP_LABEL (p);
1072     }
1073
1074   /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
1075      as required by loop_reg_used_before_p.  So skip such loops.  (This
1076      test may never be true, but it's best to play it safe.)
1077
1078      Also, skip loops where we do not start scanning at a label.  This
1079      test also rejects loops starting with a JUMP_INSN that failed the
1080      test above.  */
1081
1082   if (INSN_UID (loop->scan_start) >= max_uid_for_loop
1083       || !LABEL_P (loop->scan_start))
1084     {
1085       if (loop_dump_stream)
1086         fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
1087                  INSN_UID (loop_start), INSN_UID (loop_end));
1088       return;
1089     }
1090
1091   /* Allocate extra space for REGs that might be created by load_mems.
1092      We allocate a little extra slop as well, in the hopes that we
1093      won't have to reallocate the regs array.  */
1094   loop_regs_scan (loop, loop_info->mems_idx + 16);
1095   insn_count = count_insns_in_loop (loop);
1096
1097   if (loop_dump_stream)
1098     fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
1099              INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
1100
1101   /* Scan through the loop finding insns that are safe to move.
1102      Set REGS->ARRAY[I].SET_IN_LOOP negative for the reg I being set, so that
1103      this reg will be considered invariant for subsequent insns.
1104      We consider whether subsequent insns use the reg
1105      in deciding whether it is worth actually moving.
1106
1107      MAYBE_NEVER is nonzero if we have passed a conditional jump insn
1108      and therefore it is possible that the insns we are scanning
1109      would never be executed.  At such times, we must make sure
1110      that it is safe to execute the insn once instead of zero times.
1111      When MAYBE_NEVER is 0, all insns will be executed at least once
1112      so that is not a problem.  */
1113
1114   for (in_libcall = 0, p = next_insn_in_loop (loop, loop->scan_start);
1115        p != NULL_RTX;
1116        p = next_insn_in_loop (loop, p))
1117     {
1118       if (in_libcall && INSN_P (p) && find_reg_note (p, REG_RETVAL, NULL_RTX))
1119         in_libcall--;
1120       if (NONJUMP_INSN_P (p))
1121         {
1122           temp = find_reg_note (p, REG_LIBCALL, NULL_RTX);
1123           if (temp)
1124             in_libcall++;
1125           if (! in_libcall
1126               && (set = single_set (p))
1127               && REG_P (SET_DEST (set))
1128 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
1129               && SET_DEST (set) != pic_offset_table_rtx
1130 #endif
1131               && ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
1132             {
1133               int tem1 = 0;
1134               int tem2 = 0;
1135               int move_insn = 0;
1136               int insert_temp = 0;
1137               rtx src = SET_SRC (set);
1138               rtx dependencies = 0;
1139
1140               /* Figure out what to use as a source of this insn.  If a
1141                  REG_EQUIV note is given or if a REG_EQUAL note with a
1142                  constant operand is specified, use it as the source and
1143                  mark that we should move this insn by calling
1144                  emit_move_insn rather that duplicating the insn.
1145
1146                  Otherwise, only use the REG_EQUAL contents if a REG_RETVAL
1147                  note is present.  */
1148               temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
1149               if (temp)
1150                 src = XEXP (temp, 0), move_insn = 1;
1151               else
1152                 {
1153                   temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
1154                   if (temp && CONSTANT_P (XEXP (temp, 0)))
1155                     src = XEXP (temp, 0), move_insn = 1;
1156                   if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
1157                     {
1158                       src = XEXP (temp, 0);
1159                       /* A libcall block can use regs that don't appear in
1160                          the equivalent expression.  To move the libcall,
1161                          we must move those regs too.  */
1162                       dependencies = libcall_other_reg (p, src);
1163                     }
1164                 }
1165
1166               /* For parallels, add any possible uses to the dependencies, as
1167                  we can't move the insn without resolving them first.
1168                  MEMs inside CLOBBERs may also reference registers; these
1169                  count as implicit uses.  */
1170               if (GET_CODE (PATTERN (p)) == PARALLEL)
1171                 {
1172                   for (i = 0; i < XVECLEN (PATTERN (p), 0); i++)
1173                     {
1174                       rtx x = XVECEXP (PATTERN (p), 0, i);
1175                       if (GET_CODE (x) == USE)
1176                         dependencies
1177                           = gen_rtx_EXPR_LIST (VOIDmode, XEXP (x, 0),
1178                                                dependencies);
1179                       else if (GET_CODE (x) == CLOBBER 
1180                                && MEM_P (XEXP (x, 0)))
1181                         dependencies = find_regs_nested (dependencies, 
1182                                                   XEXP (XEXP (x, 0), 0));
1183                     }
1184                 }
1185
1186               if (/* The register is used in basic blocks other
1187                       than the one where it is set (meaning that
1188                       something after this point in the loop might
1189                       depend on its value before the set).  */
1190                    ! reg_in_basic_block_p (p, SET_DEST (set))
1191                    /* And the set is not guaranteed to be executed once
1192                       the loop starts, or the value before the set is
1193                       needed before the set occurs...
1194
1195                       ??? Note we have quadratic behavior here, mitigated
1196                       by the fact that the previous test will often fail for
1197                       large loops.  Rather than re-scanning the entire loop
1198                       each time for register usage, we should build tables
1199                       of the register usage and use them here instead.  */
1200                    && (maybe_never
1201                        || loop_reg_used_before_p (loop, set, p)))
1202                 /* It is unsafe to move the set.  However, it may be OK to
1203                    move the source into a new pseudo, and substitute a
1204                    reg-to-reg copy for the original insn.
1205
1206                    This code used to consider it OK to move a set of a variable
1207                    which was not created by the user and not used in an exit
1208                    test.
1209                    That behavior is incorrect and was removed.  */
1210                 insert_temp = 1;
1211
1212               /* Don't try to optimize a MODE_CC set with a constant
1213                  source.  It probably will be combined with a conditional
1214                  jump.  */
1215               if (GET_MODE_CLASS (GET_MODE (SET_DEST (set))) == MODE_CC
1216                   && CONSTANT_P (src))
1217                 ;
1218               /* Don't try to optimize a register that was made
1219                  by loop-optimization for an inner loop.
1220                  We don't know its life-span, so we can't compute
1221                  the benefit.  */
1222               else if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
1223                 ;
1224               /* Don't move the source and add a reg-to-reg copy:
1225                  - with -Os (this certainly increases size),
1226                  - if the mode doesn't support copy operations (obviously),
1227                  - if the source is already a reg (the motion will gain nothing),
1228                  - if the source is a legitimate constant (likewise).  */
1229               else if (insert_temp
1230                        && (optimize_size
1231                            || ! can_copy_p (GET_MODE (SET_SRC (set)))
1232                            || REG_P (SET_SRC (set))
1233                            || (CONSTANT_P (SET_SRC (set))
1234                                && LEGITIMATE_CONSTANT_P (SET_SRC (set)))))
1235                 ;
1236               else if ((tem = loop_invariant_p (loop, src))
1237                        && (dependencies == 0
1238                            || (tem2
1239                                = loop_invariant_p (loop, dependencies)) != 0)
1240                        && (regs->array[REGNO (SET_DEST (set))].set_in_loop == 1
1241                            || (tem1
1242                                = consec_sets_invariant_p
1243                                (loop, SET_DEST (set),
1244                                 regs->array[REGNO (SET_DEST (set))].set_in_loop,
1245                                 p)))
1246                        /* If the insn can cause a trap (such as divide by zero),
1247                           can't move it unless it's guaranteed to be executed
1248                           once loop is entered.  Even a function call might
1249                           prevent the trap insn from being reached
1250                           (since it might exit!)  */
1251                        && ! ((maybe_never || call_passed)
1252                              && may_trap_p (src)))
1253                 {
1254                   struct movable *m;
1255                   int regno = REGNO (SET_DEST (set));
1256
1257                   /* A potential lossage is where we have a case where two insns
1258                      can be combined as long as they are both in the loop, but
1259                      we move one of them outside the loop.  For large loops,
1260                      this can lose.  The most common case of this is the address
1261                      of a function being called.
1262
1263                      Therefore, if this register is marked as being used
1264                      exactly once if we are in a loop with calls
1265                      (a "large loop"), see if we can replace the usage of
1266                      this register with the source of this SET.  If we can,
1267                      delete this insn.
1268
1269                      Don't do this if P has a REG_RETVAL note or if we have
1270                      SMALL_REGISTER_CLASSES and SET_SRC is a hard register.  */
1271
1272                   if (loop_info->has_call
1273                       && regs->array[regno].single_usage != 0
1274                       && regs->array[regno].single_usage != const0_rtx
1275                       && REGNO_FIRST_UID (regno) == INSN_UID (p)
1276                       && (REGNO_LAST_UID (regno)
1277                           == INSN_UID (regs->array[regno].single_usage))
1278                       && regs->array[regno].set_in_loop == 1
1279                       && GET_CODE (SET_SRC (set)) != ASM_OPERANDS
1280                       && ! side_effects_p (SET_SRC (set))
1281                       && ! find_reg_note (p, REG_RETVAL, NULL_RTX)
1282                       && (! SMALL_REGISTER_CLASSES
1283                           || (! (REG_P (SET_SRC (set))
1284                                  && (REGNO (SET_SRC (set))
1285                                      < FIRST_PSEUDO_REGISTER))))
1286                       && regno >= FIRST_PSEUDO_REGISTER 
1287                       /* This test is not redundant; SET_SRC (set) might be
1288                          a call-clobbered register and the life of REGNO
1289                          might span a call.  */
1290                       && ! modified_between_p (SET_SRC (set), p,
1291                                                regs->array[regno].single_usage)
1292                       && no_labels_between_p (p,
1293                                               regs->array[regno].single_usage)
1294                       && validate_replace_rtx (SET_DEST (set), SET_SRC (set),
1295                                                regs->array[regno].single_usage))
1296                     {
1297                       /* Replace any usage in a REG_EQUAL note.  Must copy
1298                          the new source, so that we don't get rtx sharing
1299                          between the SET_SOURCE and REG_NOTES of insn p.  */
1300                       REG_NOTES (regs->array[regno].single_usage)
1301                         = (replace_rtx
1302                            (REG_NOTES (regs->array[regno].single_usage),
1303                             SET_DEST (set), copy_rtx (SET_SRC (set))));
1304
1305                       delete_insn (p);
1306                       for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set));
1307                            i++)
1308                         regs->array[regno+i].set_in_loop = 0;
1309                       continue;
1310                     }
1311
1312                   m = xmalloc (sizeof (struct movable));
1313                   m->next = 0;
1314                   m->insn = p;
1315                   m->set_src = src;
1316                   m->dependencies = dependencies;
1317                   m->set_dest = SET_DEST (set);
1318                   m->force = 0;
1319                   m->consec
1320                     = regs->array[REGNO (SET_DEST (set))].set_in_loop - 1;
1321                   m->done = 0;
1322                   m->forces = 0;
1323                   m->partial = 0;
1324                   m->move_insn = move_insn;
1325                   m->move_insn_first = 0;
1326                   m->insert_temp = insert_temp;
1327                   m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
1328                   m->savemode = VOIDmode;
1329                   m->regno = regno;
1330                   /* Set M->cond if either loop_invariant_p
1331                      or consec_sets_invariant_p returned 2
1332                      (only conditionally invariant).  */
1333                   m->cond = ((tem | tem1 | tem2) > 1);
1334                   m->global =  LOOP_REG_GLOBAL_P (loop, regno);
1335                   m->match = 0;
1336                   m->lifetime = LOOP_REG_LIFETIME (loop, regno);
1337                   m->savings = regs->array[regno].n_times_set;
1338                   if (find_reg_note (p, REG_RETVAL, NULL_RTX))
1339                     m->savings += libcall_benefit (p);
1340                   for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set)); i++)
1341                     regs->array[regno+i].set_in_loop = move_insn ? -2 : -1;
1342                   /* Add M to the end of the chain MOVABLES.  */
1343                   loop_movables_add (movables, m);
1344
1345                   if (m->consec > 0)
1346                     {
1347                       /* It is possible for the first instruction to have a
1348                          REG_EQUAL note but a non-invariant SET_SRC, so we must
1349                          remember the status of the first instruction in case
1350                          the last instruction doesn't have a REG_EQUAL note.  */
1351                       m->move_insn_first = m->move_insn;
1352
1353                       /* Skip this insn, not checking REG_LIBCALL notes.  */
1354                       p = next_nonnote_insn (p);
1355                       /* Skip the consecutive insns, if there are any.  */
1356                       p = skip_consec_insns (p, m->consec);
1357                       /* Back up to the last insn of the consecutive group.  */
1358                       p = prev_nonnote_insn (p);
1359
1360                       /* We must now reset m->move_insn, m->is_equiv, and
1361                          possibly m->set_src to correspond to the effects of
1362                          all the insns.  */
1363                       temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
1364                       if (temp)
1365                         m->set_src = XEXP (temp, 0), m->move_insn = 1;
1366                       else
1367                         {
1368                           temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
1369                           if (temp && CONSTANT_P (XEXP (temp, 0)))
1370                             m->set_src = XEXP (temp, 0), m->move_insn = 1;
1371                           else
1372                             m->move_insn = 0;
1373
1374                         }
1375                       m->is_equiv
1376                         = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
1377                     }
1378                 }
1379               /* If this register is always set within a STRICT_LOW_PART
1380                  or set to zero, then its high bytes are constant.
1381                  So clear them outside the loop and within the loop
1382                  just load the low bytes.
1383                  We must check that the machine has an instruction to do so.
1384                  Also, if the value loaded into the register
1385                  depends on the same register, this cannot be done.  */
1386               else if (SET_SRC (set) == const0_rtx
1387                        && NONJUMP_INSN_P (NEXT_INSN (p))
1388                        && (set1 = single_set (NEXT_INSN (p)))
1389                        && GET_CODE (set1) == SET
1390                        && (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
1391                        && (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
1392                        && (SUBREG_REG (XEXP (SET_DEST (set1), 0))
1393                            == SET_DEST (set))
1394                        && !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
1395                 {
1396                   int regno = REGNO (SET_DEST (set));
1397                   if (regs->array[regno].set_in_loop == 2)
1398                     {
1399                       struct movable *m;
1400                       m = xmalloc (sizeof (struct movable));
1401                       m->next = 0;
1402                       m->insn = p;
1403                       m->set_dest = SET_DEST (set);
1404                       m->dependencies = 0;
1405                       m->force = 0;
1406                       m->consec = 0;
1407                       m->done = 0;
1408                       m->forces = 0;
1409                       m->move_insn = 0;
1410                       m->move_insn_first = 0;
1411                       m->insert_temp = insert_temp;
1412                       m->partial = 1;
1413                       /* If the insn may not be executed on some cycles,
1414                          we can't clear the whole reg; clear just high part.
1415                          Not even if the reg is used only within this loop.
1416                          Consider this:
1417                          while (1)
1418                            while (s != t) {
1419                              if (foo ()) x = *s;
1420                              use (x);
1421                            }
1422                          Clearing x before the inner loop could clobber a value
1423                          being saved from the last time around the outer loop.
1424                          However, if the reg is not used outside this loop
1425                          and all uses of the register are in the same
1426                          basic block as the store, there is no problem.
1427
1428                          If this insn was made by loop, we don't know its
1429                          INSN_LUID and hence must make a conservative
1430                          assumption.  */
1431                       m->global = (INSN_UID (p) >= max_uid_for_loop
1432                                    || LOOP_REG_GLOBAL_P (loop, regno)
1433                                    || (labels_in_range_p
1434                                        (p, REGNO_FIRST_LUID (regno))));
1435                       if (maybe_never && m->global)
1436                         m->savemode = GET_MODE (SET_SRC (set1));
1437                       else
1438                         m->savemode = VOIDmode;
1439                       m->regno = regno;
1440                       m->cond = 0;
1441                       m->match = 0;
1442                       m->lifetime = LOOP_REG_LIFETIME (loop, regno);
1443                       m->savings = 1;
1444                       for (i = 0;
1445                            i < LOOP_REGNO_NREGS (regno, SET_DEST (set));
1446                            i++)
1447                         regs->array[regno+i].set_in_loop = -1;
1448                       /* Add M to the end of the chain MOVABLES.  */
1449                       loop_movables_add (movables, m);
1450                     }
1451                 }
1452             }
1453         }
1454       /* Past a call insn, we get to insns which might not be executed
1455          because the call might exit.  This matters for insns that trap.
1456          Constant and pure call insns always return, so they don't count.  */
1457       else if (CALL_P (p) && ! CONST_OR_PURE_CALL_P (p))
1458         call_passed = 1;
1459       /* Past a label or a jump, we get to insns for which we
1460          can't count on whether or how many times they will be
1461          executed during each iteration.  Therefore, we can
1462          only move out sets of trivial variables
1463          (those not used after the loop).  */
1464       /* Similar code appears twice in strength_reduce.  */
1465       else if ((LABEL_P (p) || JUMP_P (p))
1466                /* If we enter the loop in the middle, and scan around to the
1467                   beginning, don't set maybe_never for that.  This must be an
1468                   unconditional jump, otherwise the code at the top of the
1469                   loop might never be executed.  Unconditional jumps are
1470                   followed by a barrier then the loop_end.  */
1471                && ! (JUMP_P (p) && JUMP_LABEL (p) == loop->top
1472                      && NEXT_INSN (NEXT_INSN (p)) == loop_end
1473                      && any_uncondjump_p (p)))
1474         maybe_never = 1;
1475     }
1476
1477   /* If one movable subsumes another, ignore that other.  */
1478
1479   ignore_some_movables (movables);
1480
1481   /* For each movable insn, see if the reg that it loads
1482      leads when it dies right into another conditionally movable insn.
1483      If so, record that the second insn "forces" the first one,
1484      since the second can be moved only if the first is.  */
1485
1486   force_movables (movables);
1487
1488   /* See if there are multiple movable insns that load the same value.
1489      If there are, make all but the first point at the first one
1490      through the `match' field, and add the priorities of them
1491      all together as the priority of the first.  */
1492
1493   combine_movables (movables, regs);
1494
1495   /* Now consider each movable insn to decide whether it is worth moving.
1496      Store 0 in regs->array[I].set_in_loop for each reg I that is moved.
1497
1498      For machines with few registers this increases code size, so do not
1499      move moveables when optimizing for code size on such machines.
1500      (The 18 below is the value for i386.)  */
1501
1502   if (!optimize_size
1503       || (reg_class_size[GENERAL_REGS] > 18 && !loop_info->has_call))
1504     {
1505       move_movables (loop, movables, threshold, insn_count);
1506
1507       /* Recalculate regs->array if move_movables has created new
1508          registers.  */
1509       if (max_reg_num () > regs->num)
1510         {
1511           loop_regs_scan (loop, 0);
1512           for (update_start = loop_start;
1513                PREV_INSN (update_start)
1514                && !LABEL_P (PREV_INSN (update_start));
1515                update_start = PREV_INSN (update_start))
1516             ;
1517           update_end = NEXT_INSN (loop_end);
1518
1519           reg_scan_update (update_start, update_end, loop_max_reg);
1520           loop_max_reg = max_reg_num ();
1521         }
1522     }
1523
1524   /* Now candidates that still are negative are those not moved.
1525      Change regs->array[I].set_in_loop to indicate that those are not actually
1526      invariant.  */
1527   for (i = 0; i < regs->num; i++)
1528     if (regs->array[i].set_in_loop < 0)
1529       regs->array[i].set_in_loop = regs->array[i].n_times_set;
1530
1531   /* Now that we've moved some things out of the loop, we might be able to
1532      hoist even more memory references.  */
1533   load_mems (loop);
1534
1535   /* Recalculate regs->array if load_mems has created new registers.  */
1536   if (max_reg_num () > regs->num)
1537     loop_regs_scan (loop, 0);
1538
1539   for (update_start = loop_start;
1540        PREV_INSN (update_start)
1541          && !LABEL_P (PREV_INSN (update_start));
1542        update_start = PREV_INSN (update_start))
1543     ;
1544   update_end = NEXT_INSN (loop_end);
1545
1546   reg_scan_update (update_start, update_end, loop_max_reg);
1547   loop_max_reg = max_reg_num ();
1548
1549   if (flag_strength_reduce)
1550     {
1551       if (update_end && LABEL_P (update_end))
1552         /* Ensure our label doesn't go away.  */
1553         LABEL_NUSES (update_end)++;
1554
1555       strength_reduce (loop, flags);
1556
1557       reg_scan_update (update_start, update_end, loop_max_reg);
1558       loop_max_reg = max_reg_num ();
1559
1560       if (update_end && LABEL_P (update_end)
1561           && --LABEL_NUSES (update_end) == 0)
1562         delete_related_insns (update_end);
1563     }
1564
1565
1566   /* The movable information is required for strength reduction.  */
1567   loop_movables_free (movables);
1568
1569   free (regs->array);
1570   regs->array = 0;
1571   regs->num = 0;
1572 }
1573 \f
1574 /* Add elements to *OUTPUT to record all the pseudo-regs
1575    mentioned in IN_THIS but not mentioned in NOT_IN_THIS.  */
1576
1577 static void
1578 record_excess_regs (rtx in_this, rtx not_in_this, rtx *output)
1579 {
1580   enum rtx_code code;
1581   const char *fmt;
1582   int i;
1583
1584   code = GET_CODE (in_this);
1585
1586   switch (code)
1587     {
1588     case PC:
1589     case CC0:
1590     case CONST_INT:
1591     case CONST_DOUBLE:
1592     case CONST:
1593     case SYMBOL_REF:
1594     case LABEL_REF:
1595       return;
1596
1597     case REG:
1598       if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
1599           && ! reg_mentioned_p (in_this, not_in_this))
1600         *output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
1601       return;
1602
1603     default:
1604       break;
1605     }
1606
1607   fmt = GET_RTX_FORMAT (code);
1608   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1609     {
1610       int j;
1611
1612       switch (fmt[i])
1613         {
1614         case 'E':
1615           for (j = 0; j < XVECLEN (in_this, i); j++)
1616             record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
1617           break;
1618
1619         case 'e':
1620           record_excess_regs (XEXP (in_this, i), not_in_this, output);
1621           break;
1622         }
1623     }
1624 }
1625 \f
1626 /* Check what regs are referred to in the libcall block ending with INSN,
1627    aside from those mentioned in the equivalent value.
1628    If there are none, return 0.
1629    If there are one or more, return an EXPR_LIST containing all of them.  */
1630
1631 static rtx
1632 libcall_other_reg (rtx insn, rtx equiv)
1633 {
1634   rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1635   rtx p = XEXP (note, 0);
1636   rtx output = 0;
1637
1638   /* First, find all the regs used in the libcall block
1639      that are not mentioned as inputs to the result.  */
1640
1641   while (p != insn)
1642     {
1643       if (INSN_P (p))
1644         record_excess_regs (PATTERN (p), equiv, &output);
1645       p = NEXT_INSN (p);
1646     }
1647
1648   return output;
1649 }
1650 \f
1651 /* Return 1 if all uses of REG
1652    are between INSN and the end of the basic block.  */
1653
1654 static int
1655 reg_in_basic_block_p (rtx insn, rtx reg)
1656 {
1657   int regno = REGNO (reg);
1658   rtx p;
1659
1660   if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
1661     return 0;
1662
1663   /* Search this basic block for the already recorded last use of the reg.  */
1664   for (p = insn; p; p = NEXT_INSN (p))
1665     {
1666       switch (GET_CODE (p))
1667         {
1668         case NOTE:
1669           break;
1670
1671         case INSN:
1672         case CALL_INSN:
1673           /* Ordinary insn: if this is the last use, we win.  */
1674           if (REGNO_LAST_UID (regno) == INSN_UID (p))
1675             return 1;
1676           break;
1677
1678         case JUMP_INSN:
1679           /* Jump insn: if this is the last use, we win.  */
1680           if (REGNO_LAST_UID (regno) == INSN_UID (p))
1681             return 1;
1682           /* Otherwise, it's the end of the basic block, so we lose.  */
1683           return 0;
1684
1685         case CODE_LABEL:
1686         case BARRIER:
1687           /* It's the end of the basic block, so we lose.  */
1688           return 0;
1689
1690         default:
1691           break;
1692         }
1693     }
1694
1695   /* The "last use" that was recorded can't be found after the first
1696      use.  This can happen when the last use was deleted while
1697      processing an inner loop, this inner loop was then completely
1698      unrolled, and the outer loop is always exited after the inner loop,
1699      so that everything after the first use becomes a single basic block.  */
1700   return 1;
1701 }
1702 \f
1703 /* Compute the benefit of eliminating the insns in the block whose
1704    last insn is LAST.  This may be a group of insns used to compute a
1705    value directly or can contain a library call.  */
1706
1707 static int
1708 libcall_benefit (rtx last)
1709 {
1710   rtx insn;
1711   int benefit = 0;
1712
1713   for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
1714        insn != last; insn = NEXT_INSN (insn))
1715     {
1716       if (CALL_P (insn))
1717         benefit += 10;          /* Assume at least this many insns in a library
1718                                    routine.  */
1719       else if (NONJUMP_INSN_P (insn)
1720                && GET_CODE (PATTERN (insn)) != USE
1721                && GET_CODE (PATTERN (insn)) != CLOBBER)
1722         benefit++;
1723     }
1724
1725   return benefit;
1726 }
1727 \f
1728 /* Skip COUNT insns from INSN, counting library calls as 1 insn.  */
1729
1730 static rtx
1731 skip_consec_insns (rtx insn, int count)
1732 {
1733   for (; count > 0; count--)
1734     {
1735       rtx temp;
1736
1737       /* If first insn of libcall sequence, skip to end.  */
1738       /* Do this at start of loop, since INSN is guaranteed to
1739          be an insn here.  */
1740       if (!NOTE_P (insn)
1741           && (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
1742         insn = XEXP (temp, 0);
1743
1744       do
1745         insn = NEXT_INSN (insn);
1746       while (NOTE_P (insn));
1747     }
1748
1749   return insn;
1750 }
1751
1752 /* Ignore any movable whose insn falls within a libcall
1753    which is part of another movable.
1754    We make use of the fact that the movable for the libcall value
1755    was made later and so appears later on the chain.  */
1756
1757 static void
1758 ignore_some_movables (struct loop_movables *movables)
1759 {
1760   struct movable *m, *m1;
1761
1762   for (m = movables->head; m; m = m->next)
1763     {
1764       /* Is this a movable for the value of a libcall?  */
1765       rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
1766       if (note)
1767         {
1768           rtx insn;
1769           /* Check for earlier movables inside that range,
1770              and mark them invalid.  We cannot use LUIDs here because
1771              insns created by loop.c for prior loops don't have LUIDs.
1772              Rather than reject all such insns from movables, we just
1773              explicitly check each insn in the libcall (since invariant
1774              libcalls aren't that common).  */
1775           for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
1776             for (m1 = movables->head; m1 != m; m1 = m1->next)
1777               if (m1->insn == insn)
1778                 m1->done = 1;
1779         }
1780     }
1781 }
1782
1783 /* For each movable insn, see if the reg that it loads
1784    leads when it dies right into another conditionally movable insn.
1785    If so, record that the second insn "forces" the first one,
1786    since the second can be moved only if the first is.  */
1787
1788 static void
1789 force_movables (struct loop_movables *movables)
1790 {
1791   struct movable *m, *m1;
1792
1793   for (m1 = movables->head; m1; m1 = m1->next)
1794     /* Omit this if moving just the (SET (REG) 0) of a zero-extend.  */
1795     if (!m1->partial && !m1->done)
1796       {
1797         int regno = m1->regno;
1798         for (m = m1->next; m; m = m->next)
1799           /* ??? Could this be a bug?  What if CSE caused the
1800              register of M1 to be used after this insn?
1801              Since CSE does not update regno_last_uid,
1802              this insn M->insn might not be where it dies.
1803              But very likely this doesn't matter; what matters is
1804              that M's reg is computed from M1's reg.  */
1805           if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
1806               && !m->done)
1807             break;
1808         if (m != 0 && m->set_src == m1->set_dest
1809             /* If m->consec, m->set_src isn't valid.  */
1810             && m->consec == 0)
1811           m = 0;
1812
1813         /* Increase the priority of the moving the first insn
1814            since it permits the second to be moved as well.
1815            Likewise for insns already forced by the first insn.  */
1816         if (m != 0)
1817           {
1818             struct movable *m2;
1819
1820             m->forces = m1;
1821             for (m2 = m1; m2; m2 = m2->forces)
1822               {
1823                 m2->lifetime += m->lifetime;
1824                 m2->savings += m->savings;
1825               }
1826           }
1827       }
1828 }
1829 \f
1830 /* Find invariant expressions that are equal and can be combined into
1831    one register.  */
1832
1833 static void
1834 combine_movables (struct loop_movables *movables, struct loop_regs *regs)
1835 {
1836   struct movable *m;
1837   char *matched_regs = xmalloc (regs->num);
1838   enum machine_mode mode;
1839
1840   /* Regs that are set more than once are not allowed to match
1841      or be matched.  I'm no longer sure why not.  */
1842   /* Only pseudo registers are allowed to match or be matched,
1843      since move_movables does not validate the change.  */
1844   /* Perhaps testing m->consec_sets would be more appropriate here?  */
1845
1846   for (m = movables->head; m; m = m->next)
1847     if (m->match == 0 && regs->array[m->regno].n_times_set == 1
1848         && m->regno >= FIRST_PSEUDO_REGISTER
1849         && !m->insert_temp
1850         && !m->partial)
1851       {
1852         struct movable *m1;
1853         int regno = m->regno;
1854
1855         memset (matched_regs, 0, regs->num);
1856         matched_regs[regno] = 1;
1857
1858         /* We want later insns to match the first one.  Don't make the first
1859            one match any later ones.  So start this loop at m->next.  */
1860         for (m1 = m->next; m1; m1 = m1->next)
1861           if (m != m1 && m1->match == 0
1862               && !m1->insert_temp
1863               && regs->array[m1->regno].n_times_set == 1
1864               && m1->regno >= FIRST_PSEUDO_REGISTER
1865               /* A reg used outside the loop mustn't be eliminated.  */
1866               && !m1->global
1867               /* A reg used for zero-extending mustn't be eliminated.  */
1868               && !m1->partial
1869               && (matched_regs[m1->regno]
1870                   ||
1871                   (
1872                    /* Can combine regs with different modes loaded from the
1873                       same constant only if the modes are the same or
1874                       if both are integer modes with M wider or the same
1875                       width as M1.  The check for integer is redundant, but
1876                       safe, since the only case of differing destination
1877                       modes with equal sources is when both sources are
1878                       VOIDmode, i.e., CONST_INT.  */
1879                    (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
1880                     || (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
1881                         && GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
1882                         && (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
1883                             >= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
1884                    /* See if the source of M1 says it matches M.  */
1885                    && ((REG_P (m1->set_src)
1886                         && matched_regs[REGNO (m1->set_src)])
1887                        || rtx_equal_for_loop_p (m->set_src, m1->set_src,
1888                                                 movables, regs))))
1889               && ((m->dependencies == m1->dependencies)
1890                   || rtx_equal_p (m->dependencies, m1->dependencies)))
1891             {
1892               m->lifetime += m1->lifetime;
1893               m->savings += m1->savings;
1894               m1->done = 1;
1895               m1->match = m;
1896               matched_regs[m1->regno] = 1;
1897             }
1898       }
1899
1900   /* Now combine the regs used for zero-extension.
1901      This can be done for those not marked `global'
1902      provided their lives don't overlap.  */
1903
1904   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1905        mode = GET_MODE_WIDER_MODE (mode))
1906     {
1907       struct movable *m0 = 0;
1908
1909       /* Combine all the registers for extension from mode MODE.
1910          Don't combine any that are used outside this loop.  */
1911       for (m = movables->head; m; m = m->next)
1912         if (m->partial && ! m->global
1913             && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
1914           {
1915             struct movable *m1;
1916
1917             int first = REGNO_FIRST_LUID (m->regno);
1918             int last = REGNO_LAST_LUID (m->regno);
1919
1920             if (m0 == 0)
1921               {
1922                 /* First one: don't check for overlap, just record it.  */
1923                 m0 = m;
1924                 continue;
1925               }
1926
1927             /* Make sure they extend to the same mode.
1928                (Almost always true.)  */
1929             if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
1930               continue;
1931
1932             /* We already have one: check for overlap with those
1933                already combined together.  */
1934             for (m1 = movables->head; m1 != m; m1 = m1->next)
1935               if (m1 == m0 || (m1->partial && m1->match == m0))
1936                 if (! (REGNO_FIRST_LUID (m1->regno) > last
1937                        || REGNO_LAST_LUID (m1->regno) < first))
1938                   goto overlap;
1939
1940             /* No overlap: we can combine this with the others.  */
1941             m0->lifetime += m->lifetime;
1942             m0->savings += m->savings;
1943             m->done = 1;
1944             m->match = m0;
1945
1946           overlap:
1947             ;
1948           }
1949     }
1950
1951   /* Clean up.  */
1952   free (matched_regs);
1953 }
1954
1955 /* Returns the number of movable instructions in LOOP that were not
1956    moved outside the loop.  */
1957
1958 static int
1959 num_unmoved_movables (const struct loop *loop)
1960 {
1961   int num = 0;
1962   struct movable *m;
1963
1964   for (m = LOOP_MOVABLES (loop)->head; m; m = m->next)
1965     if (!m->done)
1966       ++num;
1967
1968   return num;
1969 }
1970
1971 \f
1972 /* Return 1 if regs X and Y will become the same if moved.  */
1973
1974 static int
1975 regs_match_p (rtx x, rtx y, struct loop_movables *movables)
1976 {
1977   unsigned int xn = REGNO (x);
1978   unsigned int yn = REGNO (y);
1979   struct movable *mx, *my;
1980
1981   for (mx = movables->head; mx; mx = mx->next)
1982     if (mx->regno == xn)
1983       break;
1984
1985   for (my = movables->head; my; my = my->next)
1986     if (my->regno == yn)
1987       break;
1988
1989   return (mx && my
1990           && ((mx->match == my->match && mx->match != 0)
1991               || mx->match == my
1992               || mx == my->match));
1993 }
1994
1995 /* Return 1 if X and Y are identical-looking rtx's.
1996    This is the Lisp function EQUAL for rtx arguments.
1997
1998    If two registers are matching movables or a movable register and an
1999    equivalent constant, consider them equal.  */
2000
2001 static int
2002 rtx_equal_for_loop_p (rtx x, rtx y, struct loop_movables *movables,
2003                       struct loop_regs *regs)
2004 {
2005   int i;
2006   int j;
2007   struct movable *m;
2008   enum rtx_code code;
2009   const char *fmt;
2010
2011   if (x == y)
2012     return 1;
2013   if (x == 0 || y == 0)
2014     return 0;
2015
2016   code = GET_CODE (x);
2017
2018   /* If we have a register and a constant, they may sometimes be
2019      equal.  */
2020   if (REG_P (x) && regs->array[REGNO (x)].set_in_loop == -2
2021       && CONSTANT_P (y))
2022     {
2023       for (m = movables->head; m; m = m->next)
2024         if (m->move_insn && m->regno == REGNO (x)
2025             && rtx_equal_p (m->set_src, y))
2026           return 1;
2027     }
2028   else if (REG_P (y) && regs->array[REGNO (y)].set_in_loop == -2
2029            && CONSTANT_P (x))
2030     {
2031       for (m = movables->head; m; m = m->next)
2032         if (m->move_insn && m->regno == REGNO (y)
2033             && rtx_equal_p (m->set_src, x))
2034           return 1;
2035     }
2036
2037   /* Otherwise, rtx's of different codes cannot be equal.  */
2038   if (code != GET_CODE (y))
2039     return 0;
2040
2041   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
2042      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
2043
2044   if (GET_MODE (x) != GET_MODE (y))
2045     return 0;
2046
2047   /* These three types of rtx's can be compared nonrecursively.  */
2048   if (code == REG)
2049     return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
2050
2051   if (code == LABEL_REF)
2052     return XEXP (x, 0) == XEXP (y, 0);
2053   if (code == SYMBOL_REF)
2054     return XSTR (x, 0) == XSTR (y, 0);
2055
2056   /* Compare the elements.  If any pair of corresponding elements
2057      fail to match, return 0 for the whole things.  */
2058
2059   fmt = GET_RTX_FORMAT (code);
2060   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2061     {
2062       switch (fmt[i])
2063         {
2064         case 'w':
2065           if (XWINT (x, i) != XWINT (y, i))
2066             return 0;
2067           break;
2068
2069         case 'i':
2070           if (XINT (x, i) != XINT (y, i))
2071             return 0;
2072           break;
2073
2074         case 'E':
2075           /* Two vectors must have the same length.  */
2076           if (XVECLEN (x, i) != XVECLEN (y, i))
2077             return 0;
2078
2079           /* And the corresponding elements must match.  */
2080           for (j = 0; j < XVECLEN (x, i); j++)
2081             if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
2082                                       movables, regs) == 0)
2083               return 0;
2084           break;
2085
2086         case 'e':
2087           if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
2088               == 0)
2089             return 0;
2090           break;
2091
2092         case 's':
2093           if (strcmp (XSTR (x, i), XSTR (y, i)))
2094             return 0;
2095           break;
2096
2097         case 'u':
2098           /* These are just backpointers, so they don't matter.  */
2099           break;
2100
2101         case '0':
2102           break;
2103
2104           /* It is believed that rtx's at this level will never
2105              contain anything but integers and other rtx's,
2106              except for within LABEL_REFs and SYMBOL_REFs.  */
2107         default:
2108           abort ();
2109         }
2110     }
2111   return 1;
2112 }
2113 \f
2114 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
2115    insns in INSNS which use the reference.  LABEL_NUSES for CODE_LABEL
2116    references is incremented once for each added note.  */
2117
2118 static void
2119 add_label_notes (rtx x, rtx insns)
2120 {
2121   enum rtx_code code = GET_CODE (x);
2122   int i, j;
2123   const char *fmt;
2124   rtx insn;
2125
2126   if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
2127     {
2128       /* This code used to ignore labels that referred to dispatch tables to
2129          avoid flow generating (slightly) worse code.
2130
2131          We no longer ignore such label references (see LABEL_REF handling in
2132          mark_jump_label for additional information).  */
2133       for (insn = insns; insn; insn = NEXT_INSN (insn))
2134         if (reg_mentioned_p (XEXP (x, 0), insn))
2135           {
2136             REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
2137                                                   REG_NOTES (insn));
2138             if (LABEL_P (XEXP (x, 0)))
2139               LABEL_NUSES (XEXP (x, 0))++;
2140           }
2141     }
2142
2143   fmt = GET_RTX_FORMAT (code);
2144   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2145     {
2146       if (fmt[i] == 'e')
2147         add_label_notes (XEXP (x, i), insns);
2148       else if (fmt[i] == 'E')
2149         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2150           add_label_notes (XVECEXP (x, i, j), insns);
2151     }
2152 }
2153 \f
2154 /* Scan MOVABLES, and move the insns that deserve to be moved.
2155    If two matching movables are combined, replace one reg with the
2156    other throughout.  */
2157
2158 static void
2159 move_movables (struct loop *loop, struct loop_movables *movables,
2160                int threshold, int insn_count)
2161 {
2162   struct loop_regs *regs = LOOP_REGS (loop);
2163   int nregs = regs->num;
2164   rtx new_start = 0;
2165   struct movable *m;
2166   rtx p;
2167   rtx loop_start = loop->start;
2168   rtx loop_end = loop->end;
2169   /* Map of pseudo-register replacements to handle combining
2170      when we move several insns that load the same value
2171      into different pseudo-registers.  */
2172   rtx *reg_map = xcalloc (nregs, sizeof (rtx));
2173   char *already_moved = xcalloc (nregs, sizeof (char));
2174
2175   for (m = movables->head; m; m = m->next)
2176     {
2177       /* Describe this movable insn.  */
2178
2179       if (loop_dump_stream)
2180         {
2181           fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
2182                    INSN_UID (m->insn), m->regno, m->lifetime);
2183           if (m->consec > 0)
2184             fprintf (loop_dump_stream, "consec %d, ", m->consec);
2185           if (m->cond)
2186             fprintf (loop_dump_stream, "cond ");
2187           if (m->force)
2188             fprintf (loop_dump_stream, "force ");
2189           if (m->global)
2190             fprintf (loop_dump_stream, "global ");
2191           if (m->done)
2192             fprintf (loop_dump_stream, "done ");
2193           if (m->move_insn)
2194             fprintf (loop_dump_stream, "move-insn ");
2195           if (m->match)
2196             fprintf (loop_dump_stream, "matches %d ",
2197                      INSN_UID (m->match->insn));
2198           if (m->forces)
2199             fprintf (loop_dump_stream, "forces %d ",
2200                      INSN_UID (m->forces->insn));
2201         }
2202
2203       /* Ignore the insn if it's already done (it matched something else).
2204          Otherwise, see if it is now safe to move.  */
2205
2206       if (!m->done
2207           && (! m->cond
2208               || (1 == loop_invariant_p (loop, m->set_src)
2209                   && (m->dependencies == 0
2210                       || 1 == loop_invariant_p (loop, m->dependencies))
2211                   && (m->consec == 0
2212                       || 1 == consec_sets_invariant_p (loop, m->set_dest,
2213                                                        m->consec + 1,
2214                                                        m->insn))))
2215           && (! m->forces || m->forces->done))
2216         {
2217           int regno;
2218           rtx p;
2219           int savings = m->savings;
2220
2221           /* We have an insn that is safe to move.
2222              Compute its desirability.  */
2223
2224           p = m->insn;
2225           regno = m->regno;
2226
2227           if (loop_dump_stream)
2228             fprintf (loop_dump_stream, "savings %d ", savings);
2229
2230           if (regs->array[regno].moved_once && loop_dump_stream)
2231             fprintf (loop_dump_stream, "halved since already moved ");
2232
2233           /* An insn MUST be moved if we already moved something else
2234              which is safe only if this one is moved too: that is,
2235              if already_moved[REGNO] is nonzero.  */
2236
2237           /* An insn is desirable to move if the new lifetime of the
2238              register is no more than THRESHOLD times the old lifetime.
2239              If it's not desirable, it means the loop is so big
2240              that moving won't speed things up much,
2241              and it is liable to make register usage worse.  */
2242
2243           /* It is also desirable to move if it can be moved at no
2244              extra cost because something else was already moved.  */
2245
2246           if (already_moved[regno]
2247               || (threshold * savings * m->lifetime) >=
2248                  (regs->array[regno].moved_once ? insn_count * 2 : insn_count)
2249               || (m->forces && m->forces->done
2250                   && regs->array[m->forces->regno].n_times_set == 1))
2251             {
2252               int count;
2253               struct movable *m1;
2254               rtx first = NULL_RTX;
2255               rtx newreg = NULL_RTX;
2256
2257               if (m->insert_temp)
2258                 newreg = gen_reg_rtx (GET_MODE (m->set_dest));
2259
2260               /* Now move the insns that set the reg.  */
2261
2262               if (m->partial && m->match)
2263                 {
2264                   rtx newpat, i1;
2265                   rtx r1, r2;
2266                   /* Find the end of this chain of matching regs.
2267                      Thus, we load each reg in the chain from that one reg.
2268                      And that reg is loaded with 0 directly,
2269                      since it has ->match == 0.  */
2270                   for (m1 = m; m1->match; m1 = m1->match);
2271                   newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
2272                                           SET_DEST (PATTERN (m1->insn)));
2273                   i1 = loop_insn_hoist (loop, newpat);
2274
2275                   /* Mark the moved, invariant reg as being allowed to
2276                      share a hard reg with the other matching invariant.  */
2277                   REG_NOTES (i1) = REG_NOTES (m->insn);
2278                   r1 = SET_DEST (PATTERN (m->insn));
2279                   r2 = SET_DEST (PATTERN (m1->insn));
2280                   regs_may_share
2281                     = gen_rtx_EXPR_LIST (VOIDmode, r1,
2282                                          gen_rtx_EXPR_LIST (VOIDmode, r2,
2283                                                             regs_may_share));
2284                   delete_insn (m->insn);
2285
2286                   if (new_start == 0)
2287                     new_start = i1;
2288
2289                   if (loop_dump_stream)
2290                     fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
2291                 }
2292               /* If we are to re-generate the item being moved with a
2293                  new move insn, first delete what we have and then emit
2294                  the move insn before the loop.  */
2295               else if (m->move_insn)
2296                 {
2297                   rtx i1, temp, seq;
2298
2299                   for (count = m->consec; count >= 0; count--)
2300                     {
2301                       /* If this is the first insn of a library call sequence,
2302                          something is very wrong.  */
2303                       if (!NOTE_P (p)
2304                           && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
2305                         abort ();
2306
2307                       /* If this is the last insn of a libcall sequence, then
2308                          delete every insn in the sequence except the last.
2309                          The last insn is handled in the normal manner.  */
2310                       if (!NOTE_P (p)
2311                           && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
2312                         {
2313                           temp = XEXP (temp, 0);
2314                           while (temp != p)
2315                             temp = delete_insn (temp);
2316                         }
2317
2318                       temp = p;
2319                       p = delete_insn (p);
2320
2321                       /* simplify_giv_expr expects that it can walk the insns
2322                          at m->insn forwards and see this old sequence we are
2323                          tossing here.  delete_insn does preserve the next
2324                          pointers, but when we skip over a NOTE we must fix
2325                          it up.  Otherwise that code walks into the non-deleted
2326                          insn stream.  */
2327                       while (p && NOTE_P (p))
2328                         p = NEXT_INSN (temp) = NEXT_INSN (p);
2329
2330                       if (m->insert_temp)
2331                         {
2332                           /* Replace the original insn with a move from
2333                              our newly created temp.  */
2334                           start_sequence ();
2335                           emit_move_insn (m->set_dest, newreg);
2336                           seq = get_insns ();
2337                           end_sequence ();
2338                           emit_insn_before (seq, p);
2339                         }
2340                     }
2341
2342                   start_sequence ();
2343                   emit_move_insn (m->insert_temp ? newreg : m->set_dest,
2344                                   m->set_src);
2345                   seq = get_insns ();
2346                   end_sequence ();
2347
2348                   add_label_notes (m->set_src, seq);
2349
2350                   i1 = loop_insn_hoist (loop, seq);
2351                   if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
2352                     set_unique_reg_note (i1,
2353                                          m->is_equiv ? REG_EQUIV : REG_EQUAL,
2354                                          m->set_src);
2355
2356                   if (loop_dump_stream)
2357                     fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
2358
2359                   /* The more regs we move, the less we like moving them.  */
2360                   threshold -= 3;
2361                 }
2362               else
2363                 {
2364                   for (count = m->consec; count >= 0; count--)
2365                     {
2366                       rtx i1, temp;
2367
2368                       /* If first insn of libcall sequence, skip to end.  */
2369                       /* Do this at start of loop, since p is guaranteed to
2370                          be an insn here.  */
2371                       if (!NOTE_P (p)
2372                           && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
2373                         p = XEXP (temp, 0);
2374
2375                       /* If last insn of libcall sequence, move all
2376                          insns except the last before the loop.  The last
2377                          insn is handled in the normal manner.  */
2378                       if (!NOTE_P (p)
2379                           && (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
2380                         {
2381                           rtx fn_address = 0;
2382                           rtx fn_reg = 0;
2383                           rtx fn_address_insn = 0;
2384
2385                           first = 0;
2386                           for (temp = XEXP (temp, 0); temp != p;
2387                                temp = NEXT_INSN (temp))
2388                             {
2389                               rtx body;
2390                               rtx n;
2391                               rtx next;
2392
2393                               if (NOTE_P (temp))
2394                                 continue;
2395
2396                               body = PATTERN (temp);
2397
2398                               /* Find the next insn after TEMP,
2399                                  not counting USE or NOTE insns.  */
2400                               for (next = NEXT_INSN (temp); next != p;
2401                                    next = NEXT_INSN (next))
2402                                 if (! (NONJUMP_INSN_P (next)
2403                                        && GET_CODE (PATTERN (next)) == USE)
2404                                     && !NOTE_P (next))
2405                                   break;
2406
2407                               /* If that is the call, this may be the insn
2408                                  that loads the function address.
2409
2410                                  Extract the function address from the insn
2411                                  that loads it into a register.
2412                                  If this insn was cse'd, we get incorrect code.
2413
2414                                  So emit a new move insn that copies the
2415                                  function address into the register that the
2416                                  call insn will use.  flow.c will delete any
2417                                  redundant stores that we have created.  */
2418                               if (CALL_P (next)
2419                                   && GET_CODE (body) == SET
2420                                   && REG_P (SET_DEST (body))
2421                                   && (n = find_reg_note (temp, REG_EQUAL,
2422                                                          NULL_RTX)))
2423                                 {
2424                                   fn_reg = SET_SRC (body);
2425                                   if (!REG_P (fn_reg))
2426                                     fn_reg = SET_DEST (body);
2427                                   fn_address = XEXP (n, 0);
2428                                   fn_address_insn = temp;
2429                                 }
2430                               /* We have the call insn.
2431                                  If it uses the register we suspect it might,
2432                                  load it with the correct address directly.  */
2433                               if (CALL_P (temp)
2434                                   && fn_address != 0
2435                                   && reg_referenced_p (fn_reg, body))
2436                                 loop_insn_emit_after (loop, 0, fn_address_insn,
2437                                                       gen_move_insn
2438                                                       (fn_reg, fn_address));
2439
2440                               if (CALL_P (temp))
2441                                 {
2442                                   i1 = loop_call_insn_hoist (loop, body);
2443                                   /* Because the USAGE information potentially
2444                                      contains objects other than hard registers
2445                                      we need to copy it.  */
2446                                   if (CALL_INSN_FUNCTION_USAGE (temp))
2447                                     CALL_INSN_FUNCTION_USAGE (i1)
2448                                       = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
2449                                 }
2450                               else
2451                                 i1 = loop_insn_hoist (loop, body);
2452                               if (first == 0)
2453                                 first = i1;
2454                               if (temp == fn_address_insn)
2455                                 fn_address_insn = i1;
2456                               REG_NOTES (i1) = REG_NOTES (temp);
2457                               REG_NOTES (temp) = NULL;
2458                               delete_insn (temp);
2459                             }
2460                           if (new_start == 0)
2461                             new_start = first;
2462                         }
2463                       if (m->savemode != VOIDmode)
2464                         {
2465                           /* P sets REG to zero; but we should clear only
2466                              the bits that are not covered by the mode
2467                              m->savemode.  */
2468                           rtx reg = m->set_dest;
2469                           rtx sequence;
2470                           rtx tem;
2471
2472                           start_sequence ();
2473                           tem = expand_simple_binop
2474                             (GET_MODE (reg), AND, reg,
2475                              GEN_INT ((((HOST_WIDE_INT) 1
2476                                         << GET_MODE_BITSIZE (m->savemode)))
2477                                       - 1),
2478                              reg, 1, OPTAB_LIB_WIDEN);
2479                           if (tem == 0)
2480                             abort ();
2481                           if (tem != reg)
2482                             emit_move_insn (reg, tem);
2483                           sequence = get_insns ();
2484                           end_sequence ();
2485                           i1 = loop_insn_hoist (loop, sequence);
2486                         }
2487                       else if (CALL_P (p))
2488                         {
2489                           i1 = loop_call_insn_hoist (loop, PATTERN (p));
2490                           /* Because the USAGE information potentially
2491                              contains objects other than hard registers
2492                              we need to copy it.  */
2493                           if (CALL_INSN_FUNCTION_USAGE (p))
2494                             CALL_INSN_FUNCTION_USAGE (i1)
2495                               = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
2496                         }
2497                       else if (count == m->consec && m->move_insn_first)
2498                         {
2499                           rtx seq;
2500                           /* The SET_SRC might not be invariant, so we must
2501                              use the REG_EQUAL note.  */
2502                           start_sequence ();
2503                           emit_move_insn (m->insert_temp ? newreg : m->set_dest,
2504                                           m->set_src);
2505                           seq = get_insns ();
2506                           end_sequence ();
2507
2508                           add_label_notes (m->set_src, seq);
2509
2510                           i1 = loop_insn_hoist (loop, seq);
2511                           if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
2512                             set_unique_reg_note (i1, m->is_equiv ? REG_EQUIV
2513                                                      : REG_EQUAL, m->set_src);
2514                         }
2515                       else if (m->insert_temp)
2516                         {
2517                           rtx *reg_map2 = xcalloc (REGNO (newreg),
2518                                                    sizeof(rtx));
2519                           reg_map2 [m->regno] = newreg;
2520
2521                           i1 = loop_insn_hoist (loop, copy_rtx (PATTERN (p)));
2522                           replace_regs (i1, reg_map2, REGNO (newreg), 1);
2523                           free (reg_map2);
2524                         }
2525                       else
2526                         i1 = loop_insn_hoist (loop, PATTERN (p));
2527
2528                       if (REG_NOTES (i1) == 0)
2529                         {
2530                           REG_NOTES (i1) = REG_NOTES (p);
2531                           REG_NOTES (p) = NULL;
2532
2533                           /* If there is a REG_EQUAL note present whose value
2534                              is not loop invariant, then delete it, since it
2535                              may cause problems with later optimization passes.
2536                              It is possible for cse to create such notes
2537                              like this as a result of record_jump_cond.  */
2538
2539                           if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
2540                               && ! loop_invariant_p (loop, XEXP (temp, 0)))
2541                             remove_note (i1, temp);
2542                         }
2543
2544                       if (new_start == 0)
2545                         new_start = i1;
2546
2547                       if (loop_dump_stream)
2548                         fprintf (loop_dump_stream, " moved to %d",
2549                                  INSN_UID (i1));
2550
2551                       /* If library call, now fix the REG_NOTES that contain
2552                          insn pointers, namely REG_LIBCALL on FIRST
2553                          and REG_RETVAL on I1.  */
2554                       if ((temp = find_reg_note (i1, REG_RETVAL, NULL_RTX)))
2555                         {
2556                           XEXP (temp, 0) = first;
2557                           temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
2558                           XEXP (temp, 0) = i1;
2559                         }
2560
2561                       temp = p;
2562                       delete_insn (p);
2563                       p = NEXT_INSN (p);
2564
2565                       /* simplify_giv_expr expects that it can walk the insns
2566                          at m->insn forwards and see this old sequence we are
2567                          tossing here.  delete_insn does preserve the next
2568                          pointers, but when we skip over a NOTE we must fix
2569                          it up.  Otherwise that code walks into the non-deleted
2570                          insn stream.  */
2571                       while (p && NOTE_P (p))
2572                         p = NEXT_INSN (temp) = NEXT_INSN (p);
2573
2574                       if (m->insert_temp)
2575                         {
2576                           rtx seq;
2577                           /* Replace the original insn with a move from
2578                              our newly created temp.  */
2579                           start_sequence ();
2580                           emit_move_insn (m->set_dest, newreg);
2581                           seq = get_insns ();
2582                           end_sequence ();
2583                           emit_insn_before (seq, p);
2584                         }
2585                     }
2586
2587                   /* The more regs we move, the less we like moving them.  */
2588                   threshold -= 3;
2589                 }
2590
2591               m->done = 1;
2592
2593               if (!m->insert_temp)
2594                 {
2595                   /* Any other movable that loads the same register
2596                      MUST be moved.  */
2597                   already_moved[regno] = 1;
2598
2599                   /* This reg has been moved out of one loop.  */
2600                   regs->array[regno].moved_once = 1;
2601
2602                   /* The reg set here is now invariant.  */
2603                   if (! m->partial)
2604                     {
2605                       int i;
2606                       for (i = 0; i < LOOP_REGNO_NREGS (regno, m->set_dest); i++)
2607                         regs->array[regno+i].set_in_loop = 0;
2608                     }
2609
2610                   /* Change the length-of-life info for the register
2611                      to say it lives at least the full length of this loop.
2612                      This will help guide optimizations in outer loops.  */
2613
2614                   if (REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
2615                     /* This is the old insn before all the moved insns.
2616                        We can't use the moved insn because it is out of range
2617                        in uid_luid.  Only the old insns have luids.  */
2618                     REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
2619                   if (REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
2620                     REGNO_LAST_UID (regno) = INSN_UID (loop_end);
2621                 }
2622
2623               /* Combine with this moved insn any other matching movables.  */
2624
2625               if (! m->partial)
2626                 for (m1 = movables->head; m1; m1 = m1->next)
2627                   if (m1->match == m)
2628                     {
2629                       rtx temp;
2630
2631                       /* Schedule the reg loaded by M1
2632                          for replacement so that shares the reg of M.
2633                          If the modes differ (only possible in restricted
2634                          circumstances, make a SUBREG.
2635
2636                          Note this assumes that the target dependent files
2637                          treat REG and SUBREG equally, including within
2638                          GO_IF_LEGITIMATE_ADDRESS and in all the
2639                          predicates since we never verify that replacing the
2640                          original register with a SUBREG results in a
2641                          recognizable insn.  */
2642                       if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
2643                         reg_map[m1->regno] = m->set_dest;
2644                       else
2645                         reg_map[m1->regno]
2646                           = gen_lowpart_common (GET_MODE (m1->set_dest),
2647                                                 m->set_dest);
2648
2649                       /* Get rid of the matching insn
2650                          and prevent further processing of it.  */
2651                       m1->done = 1;
2652
2653                       /* If library call, delete all insns.  */
2654                       if ((temp = find_reg_note (m1->insn, REG_RETVAL,
2655                                                  NULL_RTX)))
2656                         delete_insn_chain (XEXP (temp, 0), m1->insn);
2657                       else
2658                         delete_insn (m1->insn);
2659
2660                       /* Any other movable that loads the same register
2661                          MUST be moved.  */
2662                       already_moved[m1->regno] = 1;
2663
2664                       /* The reg merged here is now invariant,
2665                          if the reg it matches is invariant.  */
2666                       if (! m->partial)
2667                         {
2668                           int i;
2669                           for (i = 0;
2670                                i < LOOP_REGNO_NREGS (regno, m1->set_dest);
2671                                i++)
2672                             regs->array[m1->regno+i].set_in_loop = 0;
2673                         }
2674                     }
2675             }
2676           else if (loop_dump_stream)
2677             fprintf (loop_dump_stream, "not desirable");
2678         }
2679       else if (loop_dump_stream && !m->match)
2680         fprintf (loop_dump_stream, "not safe");
2681
2682       if (loop_dump_stream)
2683         fprintf (loop_dump_stream, "\n");
2684     }
2685
2686   if (new_start == 0)
2687     new_start = loop_start;
2688
2689   /* Go through all the instructions in the loop, making
2690      all the register substitutions scheduled in REG_MAP.  */
2691   for (p = new_start; p != loop_end; p = NEXT_INSN (p))
2692     if (INSN_P (p))
2693       {
2694         replace_regs (PATTERN (p), reg_map, nregs, 0);
2695         replace_regs (REG_NOTES (p), reg_map, nregs, 0);
2696         INSN_CODE (p) = -1;
2697       }
2698
2699   /* Clean up.  */
2700   free (reg_map);
2701   free (already_moved);
2702 }
2703
2704
2705 static void
2706 loop_movables_add (struct loop_movables *movables, struct movable *m)
2707 {
2708   if (movables->head == 0)
2709     movables->head = m;
2710   else
2711     movables->last->next = m;
2712   movables->last = m;
2713 }
2714
2715
2716 static void
2717 loop_movables_free (struct loop_movables *movables)
2718 {
2719   struct movable *m;
2720   struct movable *m_next;
2721
2722   for (m = movables->head; m; m = m_next)
2723     {
2724       m_next = m->next;
2725       free (m);
2726     }
2727 }
2728 \f
2729 #if 0
2730 /* Scan X and replace the address of any MEM in it with ADDR.
2731    REG is the address that MEM should have before the replacement.  */
2732
2733 static void
2734 replace_call_address (rtx x, rtx reg, rtx addr)
2735 {
2736   enum rtx_code code;
2737   int i;
2738   const char *fmt;
2739
2740   if (x == 0)
2741     return;
2742   code = GET_CODE (x);
2743   switch (code)
2744     {
2745     case PC:
2746     case CC0:
2747     case CONST_INT:
2748     case CONST_DOUBLE:
2749     case CONST:
2750     case SYMBOL_REF:
2751     case LABEL_REF:
2752     case REG:
2753       return;
2754
2755     case SET:
2756       /* Short cut for very common case.  */
2757       replace_call_address (XEXP (x, 1), reg, addr);
2758       return;
2759
2760     case CALL:
2761       /* Short cut for very common case.  */
2762       replace_call_address (XEXP (x, 0), reg, addr);
2763       return;
2764
2765     case MEM:
2766       /* If this MEM uses a reg other than the one we expected,
2767          something is wrong.  */
2768       if (XEXP (x, 0) != reg)
2769         abort ();
2770       XEXP (x, 0) = addr;
2771       return;
2772
2773     default:
2774       break;
2775     }
2776
2777   fmt = GET_RTX_FORMAT (code);
2778   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2779     {
2780       if (fmt[i] == 'e')
2781         replace_call_address (XEXP (x, i), reg, addr);
2782       else if (fmt[i] == 'E')
2783         {
2784           int j;
2785           for (j = 0; j < XVECLEN (x, i); j++)
2786             replace_call_address (XVECEXP (x, i, j), reg, addr);
2787         }
2788     }
2789 }
2790 #endif
2791 \f
2792 /* Return the number of memory refs to addresses that vary
2793    in the rtx X.  */
2794
2795 static int
2796 count_nonfixed_reads (const struct loop *loop, rtx x)
2797 {
2798   enum rtx_code code;
2799   int i;
2800   const char *fmt;
2801   int value;
2802
2803   if (x == 0)
2804     return 0;
2805
2806   code = GET_CODE (x);
2807   switch (code)
2808     {
2809     case PC:
2810     case CC0:
2811     case CONST_INT:
2812     case CONST_DOUBLE:
2813     case CONST:
2814     case SYMBOL_REF:
2815     case LABEL_REF:
2816     case REG:
2817       return 0;
2818
2819     case MEM:
2820       return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
2821               + count_nonfixed_reads (loop, XEXP (x, 0)));
2822
2823     default:
2824       break;
2825     }
2826
2827   value = 0;
2828   fmt = GET_RTX_FORMAT (code);
2829   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2830     {
2831       if (fmt[i] == 'e')
2832         value += count_nonfixed_reads (loop, XEXP (x, i));
2833       if (fmt[i] == 'E')
2834         {
2835           int j;
2836           for (j = 0; j < XVECLEN (x, i); j++)
2837             value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
2838         }
2839     }
2840   return value;
2841 }
2842 \f
2843 /* Scan a loop setting the elements `loops_enclosed',
2844    `has_call', `has_nonconst_call', `has_volatile', `has_tablejump',
2845    `unknown_address_altered', `unknown_constant_address_altered', and
2846    `num_mem_sets' in LOOP.  Also, fill in the array `mems' and the
2847    list `store_mems' in LOOP.  */
2848
2849 static void
2850 prescan_loop (struct loop *loop)
2851 {
2852   int level = 1;
2853   rtx insn;
2854   struct loop_info *loop_info = LOOP_INFO (loop);
2855   rtx start = loop->start;
2856   rtx end = loop->end;
2857   /* The label after END.  Jumping here is just like falling off the
2858      end of the loop.  We use next_nonnote_insn instead of next_label
2859      as a hedge against the (pathological) case where some actual insn
2860      might end up between the two.  */
2861   rtx exit_target = next_nonnote_insn (end);
2862
2863   loop_info->has_indirect_jump = indirect_jump_in_function;
2864   loop_info->pre_header_has_call = 0;
2865   loop_info->has_call = 0;
2866   loop_info->has_nonconst_call = 0;
2867   loop_info->has_prefetch = 0;
2868   loop_info->has_volatile = 0;
2869   loop_info->has_tablejump = 0;
2870   loop_info->has_multiple_exit_targets = 0;
2871   loop->level = 1;
2872
2873   loop_info->unknown_address_altered = 0;
2874   loop_info->unknown_constant_address_altered = 0;
2875   loop_info->store_mems = NULL_RTX;
2876   loop_info->first_loop_store_insn = NULL_RTX;
2877   loop_info->mems_idx = 0;
2878   loop_info->num_mem_sets = 0;
2879
2880   for (insn = start; insn && !LABEL_P (insn);
2881        insn = PREV_INSN (insn))
2882     {
2883       if (CALL_P (insn))
2884         {
2885           loop_info->pre_header_has_call = 1;
2886           break;
2887         }
2888     }
2889
2890   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2891        insn = NEXT_INSN (insn))
2892     {
2893       switch (GET_CODE (insn))
2894         {
2895         case NOTE:
2896           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
2897             {
2898               ++level;
2899               /* Count number of loops contained in this one.  */
2900               loop->level++;
2901             }
2902           else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
2903             --level;
2904           break;
2905
2906         case CALL_INSN:
2907           if (! CONST_OR_PURE_CALL_P (insn))
2908             {
2909               loop_info->unknown_address_altered = 1;
2910               loop_info->has_nonconst_call = 1;
2911             }
2912           else if (pure_call_p (insn))
2913             loop_info->has_nonconst_call = 1;
2914           loop_info->has_call = 1;
2915           if (can_throw_internal (insn))
2916             loop_info->has_multiple_exit_targets = 1;
2917           break;
2918
2919         case JUMP_INSN:
2920           if (! loop_info->has_multiple_exit_targets)
2921             {
2922               rtx set = pc_set (insn);
2923
2924               if (set)
2925                 {
2926                   rtx src = SET_SRC (set);
2927                   rtx label1, label2;
2928
2929                   if (GET_CODE (src) == IF_THEN_ELSE)
2930                     {
2931                       label1 = XEXP (src, 1);
2932                       label2 = XEXP (src, 2);
2933                     }
2934                   else
2935                     {
2936                       label1 = src;
2937                       label2 = NULL_RTX;
2938                     }
2939
2940                   do
2941                     {
2942                       if (label1 && label1 != pc_rtx)
2943                         {
2944                           if (GET_CODE (label1) != LABEL_REF)
2945                             {
2946                               /* Something tricky.  */
2947                               loop_info->has_multiple_exit_targets = 1;
2948                               break;
2949                             }
2950                           else if (XEXP (label1, 0) != exit_target
2951                                    && LABEL_OUTSIDE_LOOP_P (label1))
2952                             {
2953                               /* A jump outside the current loop.  */
2954                               loop_info->has_multiple_exit_targets = 1;
2955                               break;
2956                             }
2957                         }
2958
2959                       label1 = label2;
2960                       label2 = NULL_RTX;
2961                     }
2962                   while (label1);
2963                 }
2964               else
2965                 {
2966                   /* A return, or something tricky.  */
2967                   loop_info->has_multiple_exit_targets = 1;
2968                 }
2969             }
2970           /* Fall through.  */
2971
2972         case INSN:
2973           if (volatile_refs_p (PATTERN (insn)))
2974             loop_info->has_volatile = 1;
2975
2976           if (JUMP_P (insn)
2977               && (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2978                   || GET_CODE (PATTERN (insn)) == ADDR_VEC))
2979             loop_info->has_tablejump = 1;
2980
2981           note_stores (PATTERN (insn), note_addr_stored, loop_info);
2982           if (! loop_info->first_loop_store_insn && loop_info->store_mems)
2983             loop_info->first_loop_store_insn = insn;
2984
2985           if (flag_non_call_exceptions && can_throw_internal (insn))
2986             loop_info->has_multiple_exit_targets = 1;
2987           break;
2988
2989         default:
2990           break;
2991         }
2992     }
2993
2994   /* Now, rescan the loop, setting up the LOOP_MEMS array.  */
2995   if (/* An exception thrown by a called function might land us
2996          anywhere.  */
2997       ! loop_info->has_nonconst_call
2998       /* We don't want loads for MEMs moved to a location before the
2999          one at which their stack memory becomes allocated.  (Note
3000          that this is not a problem for malloc, etc., since those
3001          require actual function calls.  */
3002       && ! current_function_calls_alloca
3003       /* There are ways to leave the loop other than falling off the
3004          end.  */
3005       && ! loop_info->has_multiple_exit_targets)
3006     for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3007          insn = NEXT_INSN (insn))
3008       for_each_rtx (&insn, insert_loop_mem, loop_info);
3009
3010   /* BLKmode MEMs are added to LOOP_STORE_MEM as necessary so
3011      that loop_invariant_p and load_mems can use true_dependence
3012      to determine what is really clobbered.  */
3013   if (loop_info->unknown_address_altered)
3014     {
3015       rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
3016
3017       loop_info->store_mems
3018         = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
3019     }
3020   if (loop_info->unknown_constant_address_altered)
3021     {
3022       rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
3023       MEM_READONLY_P (mem) = 1;
3024       loop_info->store_mems
3025         = gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
3026     }
3027 }
3028 \f
3029 /* Invalidate all loops containing LABEL.  */
3030
3031 static void
3032 invalidate_loops_containing_label (rtx label)
3033 {
3034   struct loop *loop;
3035   for (loop = uid_loop[INSN_UID (label)]; loop; loop = loop->outer)
3036     loop->invalid = 1;
3037 }
3038
3039 /* Scan the function looking for loops.  Record the start and end of each loop.
3040    Also mark as invalid loops any loops that contain a setjmp or are branched
3041    to from outside the loop.  */
3042
3043 static void
3044 find_and_verify_loops (rtx f, struct loops *loops)
3045 {
3046   rtx insn;
3047   rtx label;
3048   int num_loops;
3049   struct loop *current_loop;
3050   struct loop *next_loop;
3051   struct loop *loop;
3052
3053   num_loops = loops->num;
3054
3055   compute_luids (f, NULL_RTX, 0);
3056
3057   /* If there are jumps to undefined labels,
3058      treat them as jumps out of any/all loops.
3059      This also avoids writing past end of tables when there are no loops.  */
3060   uid_loop[0] = NULL;
3061
3062   /* Find boundaries of loops, mark which loops are contained within
3063      loops, and invalidate loops that have setjmp.  */
3064
3065   num_loops = 0;
3066   current_loop = NULL;
3067   for (insn = f; insn; insn = NEXT_INSN (insn))
3068     {
3069       if (NOTE_P (insn))
3070         switch (NOTE_LINE_NUMBER (insn))
3071           {
3072           case NOTE_INSN_LOOP_BEG:
3073             next_loop = loops->array + num_loops;
3074             next_loop->num = num_loops;
3075             num_loops++;
3076             next_loop->start = insn;
3077             next_loop->outer = current_loop;
3078             current_loop = next_loop;
3079             break;
3080
3081           case NOTE_INSN_LOOP_END:
3082             if (! current_loop)
3083               abort ();
3084
3085             current_loop->end = insn;
3086             current_loop = current_loop->outer;
3087             break;
3088
3089           default:
3090             break;
3091           }
3092
3093       if (CALL_P (insn)
3094           && find_reg_note (insn, REG_SETJMP, NULL))
3095         {
3096           /* In this case, we must invalidate our current loop and any
3097              enclosing loop.  */
3098           for (loop = current_loop; loop; loop = loop->outer)
3099             {
3100               loop->invalid = 1;
3101               if (loop_dump_stream)
3102                 fprintf (loop_dump_stream,
3103                          "\nLoop at %d ignored due to setjmp.\n",
3104                          INSN_UID (loop->start));
3105             }
3106         }
3107
3108       /* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
3109          enclosing loop, but this doesn't matter.  */
3110       uid_loop[INSN_UID (insn)] = current_loop;
3111     }
3112
3113   /* Any loop containing a label used in an initializer must be invalidated,
3114      because it can be jumped into from anywhere.  */
3115   for (label = forced_labels; label; label = XEXP (label, 1))
3116     invalidate_loops_containing_label (XEXP (label, 0));
3117
3118   /* Any loop containing a label used for an exception handler must be
3119      invalidated, because it can be jumped into from anywhere.  */
3120   for_each_eh_label (invalidate_loops_containing_label);
3121
3122   /* Now scan all insn's in the function.  If any JUMP_INSN branches into a
3123      loop that it is not contained within, that loop is marked invalid.
3124      If any INSN or CALL_INSN uses a label's address, then the loop containing
3125      that label is marked invalid, because it could be jumped into from
3126      anywhere.
3127
3128      Also look for blocks of code ending in an unconditional branch that
3129      exits the loop.  If such a block is surrounded by a conditional
3130      branch around the block, move the block elsewhere (see below) and
3131      invert the jump to point to the code block.  This may eliminate a
3132      label in our loop and will simplify processing by both us and a
3133      possible second cse pass.  */
3134
3135   for (insn = f; insn; insn = NEXT_INSN (insn))
3136     if (INSN_P (insn))
3137       {
3138         struct loop *this_loop = uid_loop[INSN_UID (insn)];
3139
3140         if (NONJUMP_INSN_P (insn) || CALL_P (insn))
3141           {
3142             rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
3143             if (note)
3144               invalidate_loops_containing_label (XEXP (note, 0));
3145           }
3146
3147         if (!JUMP_P (insn))
3148           continue;
3149
3150         mark_loop_jump (PATTERN (insn), this_loop);
3151
3152         /* See if this is an unconditional branch outside the loop.  */
3153         if (this_loop
3154             && (GET_CODE (PATTERN (insn)) == RETURN
3155                 || (any_uncondjump_p (insn)
3156                     && onlyjump_p (insn)
3157                     && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
3158                         != this_loop)))
3159             && get_max_uid () < max_uid_for_loop)
3160           {
3161             rtx p;
3162             rtx our_next = next_real_insn (insn);
3163             rtx last_insn_to_move = NEXT_INSN (insn);
3164             struct loop *dest_loop;
3165             struct loop *outer_loop = NULL;
3166
3167             /* Go backwards until we reach the start of the loop, a label,
3168                or a JUMP_INSN.  */
3169             for (p = PREV_INSN (insn);
3170                  !LABEL_P (p)
3171                  && ! (NOTE_P (p)
3172                        && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
3173                  && !JUMP_P (p);
3174                  p = PREV_INSN (p))
3175               ;
3176
3177             /* Check for the case where we have a jump to an inner nested
3178                loop, and do not perform the optimization in that case.  */
3179
3180             if (JUMP_LABEL (insn))
3181               {
3182                 dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
3183                 if (dest_loop)
3184                   {
3185                     for (outer_loop = dest_loop; outer_loop;
3186                          outer_loop = outer_loop->outer)
3187                       if (outer_loop == this_loop)
3188                         break;
3189                   }
3190               }
3191
3192             /* Make sure that the target of P is within the current loop.  */
3193
3194             if (JUMP_P (p) && JUMP_LABEL (p)
3195                 && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
3196               outer_loop = this_loop;
3197
3198             /* If we stopped on a JUMP_INSN to the next insn after INSN,
3199                we have a block of code to try to move.
3200
3201                We look backward and then forward from the target of INSN
3202                to find a BARRIER at the same loop depth as the target.
3203                If we find such a BARRIER, we make a new label for the start
3204                of the block, invert the jump in P and point it to that label,
3205                and move the block of code to the spot we found.  */
3206
3207             if (! outer_loop
3208                 && JUMP_P (p)
3209                 && JUMP_LABEL (p) != 0
3210                 /* Just ignore jumps to labels that were never emitted.
3211                    These always indicate compilation errors.  */
3212                 && INSN_UID (JUMP_LABEL (p)) != 0
3213                 && any_condjump_p (p) && onlyjump_p (p)
3214                 && next_real_insn (JUMP_LABEL (p)) == our_next
3215                 /* If it's not safe to move the sequence, then we
3216                    mustn't try.  */
3217                 && insns_safe_to_move_p (p, NEXT_INSN (insn),
3218                                          &last_insn_to_move))
3219               {
3220                 rtx target
3221                   = JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
3222                 struct loop *target_loop = uid_loop[INSN_UID (target)];
3223                 rtx loc, loc2;
3224                 rtx tmp;
3225
3226                 /* Search for possible garbage past the conditional jumps
3227                    and look for the last barrier.  */
3228                 for (tmp = last_insn_to_move;
3229                      tmp && !LABEL_P (tmp); tmp = NEXT_INSN (tmp))
3230                   if (BARRIER_P (tmp))
3231                     last_insn_to_move = tmp;
3232
3233                 for (loc = target; loc; loc = PREV_INSN (loc))
3234                   if (BARRIER_P (loc)
3235                       /* Don't move things inside a tablejump.  */
3236                       && ((loc2 = next_nonnote_insn (loc)) == 0
3237                           || !LABEL_P (loc2)
3238                           || (loc2 = next_nonnote_insn (loc2)) == 0
3239                           || !JUMP_P (loc2)