Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / lra.c
1 /* LRA (local register allocator) driver and LRA utilities.
2    Copyright (C) 2010-2015 Free Software Foundation, Inc.
3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
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 3, 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 COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21
22 /* The Local Register Allocator (LRA) is a replacement of former
23    reload pass.  It is focused to simplify code solving the reload
24    pass tasks, to make the code maintenance easier, and to implement new
25    perspective optimizations.
26
27    The major LRA design solutions are:
28      o division small manageable, separated sub-tasks
29      o reflection of all transformations and decisions in RTL as more
30        as possible
31      o insn constraints as a primary source of the info (minimizing
32        number of target-depended macros/hooks)
33
34    In brief LRA works by iterative insn process with the final goal is
35    to satisfy all insn and address constraints:
36      o New reload insns (in brief reloads) and reload pseudos might be
37        generated;
38      o Some pseudos might be spilled to assign hard registers to
39        new reload pseudos;
40      o Recalculating spilled pseudo values (rematerialization);
41      o Changing spilled pseudos to stack memory or their equivalences;
42      o Allocation stack memory changes the address displacement and
43        new iteration is needed.
44
45    Here is block diagram of LRA passes:
46
47                                 ------------------------
48            ---------------     | Undo inheritance for   |     ---------------
49           | Memory-memory |    | spilled pseudos,       |    | New (and old) |
50           | move coalesce |<---| splits for pseudos got |<-- |   pseudos     |
51            ---------------     | the same hard regs,    |    |  assignment   |
52   Start           |            | and optional reloads   |     ---------------
53     |             |             ------------------------            ^
54     V             |              ----------------                   |
55  -----------      V             | Update virtual |                  |
56 |  Remove   |----> ------------>|    register    |                  |
57 | scratches |     ^             |  displacements |                  |
58  -----------      |              ----------------                   |
59                   |                      |                          |
60                   |                      V         New              |
61                   |                 ------------  pseudos   -------------------
62                   |                |Constraints:| or insns | Inheritance/split |
63                   |                |    RTL     |--------->|  transformations  |
64                   |                | transfor-  |          |    in EBB scope   |
65                   | substi-        |  mations   |           -------------------
66                   | tutions         ------------
67                   |                     | No change
68           ----------------              V
69          | Spilled pseudo |      -------------------
70          |    to memory   |<----| Rematerialization |
71          |  substitution  |      -------------------
72           ----------------        
73                   | No susbtitions
74                   V                
75       -------------------------
76      | Hard regs substitution, |
77      |  devirtalization, and   |------> Finish
78      | restoring scratches got |
79      |         memory          |
80       -------------------------
81
82    To speed up the process:
83      o We process only insns affected by changes on previous
84        iterations;
85      o We don't use DFA-infrastructure because it results in much slower
86        compiler speed than a special IR described below does;
87      o We use a special insn representation for quick access to insn
88        info which is always *synchronized* with the current RTL;
89        o Insn IR is minimized by memory.  It is divided on three parts:
90          o one specific for each insn in RTL (only operand locations);
91          o one common for all insns in RTL with the same insn code
92            (different operand attributes from machine descriptions);
93          o one oriented for maintenance of live info (list of pseudos).
94        o Pseudo data:
95          o all insns where the pseudo is referenced;
96          o live info (conflicting hard regs, live ranges, # of
97            references etc);
98          o data used for assigning (preferred hard regs, costs etc).
99
100    This file contains LRA driver, LRA utility functions and data, and
101    code for dealing with scratches.  */
102
103 #include "config.h"
104 #include "system.h"
105 #include "coretypes.h"
106 #include "tm.h"
107 #include "hard-reg-set.h"
108 #include "rtl.h"
109 #include "tm_p.h"
110 #include "regs.h"
111 #include "insn-config.h"
112 #include "insn-codes.h"
113 #include "recog.h"
114 #include "output.h"
115 #include "addresses.h"
116 #include "flags.h"
117 #include "hashtab.h"
118 #include "hash-set.h"
119 #include "vec.h"
120 #include "machmode.h"
121 #include "input.h"
122 #include "function.h"
123 #include "symtab.h"
124 #include "wide-int.h"
125 #include "inchash.h"
126 #include "tree.h"
127 #include "optabs.h"
128 #include "statistics.h"
129 #include "double-int.h"
130 #include "real.h"
131 #include "fixed-value.h"
132 #include "alias.h"
133 #include "expmed.h"
134 #include "dojump.h"
135 #include "explow.h"
136 #include "calls.h"
137 #include "emit-rtl.h"
138 #include "varasm.h"
139 #include "stmt.h"
140 #include "expr.h"
141 #include "predict.h"
142 #include "dominance.h"
143 #include "cfg.h"
144 #include "cfgrtl.h"
145 #include "cfgbuild.h"
146 #include "basic-block.h"
147 #include "except.h"
148 #include "tree-pass.h"
149 #include "timevar.h"
150 #include "target.h"
151 #include "ira.h"
152 #include "lra-int.h"
153 #include "df.h"
154
155 /* Dump bitmap SET with TITLE and BB INDEX.  */
156 void
157 lra_dump_bitmap_with_title (const char *title, bitmap set, int index)
158 {
159   unsigned int i;
160   int count;
161   bitmap_iterator bi;
162   static const int max_nums_on_line = 10;
163
164   if (bitmap_empty_p (set))
165     return;
166   fprintf (lra_dump_file, "  %s %d:", title, index);
167   fprintf (lra_dump_file, "\n");
168   count = max_nums_on_line + 1;
169   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
170     {
171       if (count > max_nums_on_line)
172         {
173           fprintf (lra_dump_file, "\n    ");
174           count = 0;
175         }
176       fprintf (lra_dump_file, " %4u", i);
177       count++;
178     }
179   fprintf (lra_dump_file, "\n");
180 }
181
182 /* Hard registers currently not available for allocation.  It can
183    changed after some hard  registers become not eliminable.  */
184 HARD_REG_SET lra_no_alloc_regs;
185
186 static int get_new_reg_value (void);
187 static void expand_reg_info (void);
188 static void invalidate_insn_recog_data (int);
189 static int get_insn_freq (rtx_insn *);
190 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t,
191                                              rtx_insn *, int);
192
193 /* Expand all regno related info needed for LRA.  */
194 static void
195 expand_reg_data (int old)
196 {
197   resize_reg_info ();
198   expand_reg_info ();
199   ira_expand_reg_equiv ();
200   for (int i = (int) max_reg_num () - 1; i >= old; i--)
201     lra_change_class (i, ALL_REGS, "      Set", true);
202 }
203
204 /* Create and return a new reg of ORIGINAL mode.  If ORIGINAL is NULL
205    or of VOIDmode, use MD_MODE for the new reg.  Initialize its
206    register class to RCLASS.  Print message about assigning class
207    RCLASS containing new register name TITLE unless it is NULL.  Use
208    attributes of ORIGINAL if it is a register.  The created register
209    will have unique held value.  */
210 rtx
211 lra_create_new_reg_with_unique_value (machine_mode md_mode, rtx original,
212                                       enum reg_class rclass, const char *title)
213 {
214   machine_mode mode;
215   rtx new_reg;
216
217   if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
218     mode = md_mode;
219   lra_assert (mode != VOIDmode);
220   new_reg = gen_reg_rtx (mode);
221   if (original == NULL_RTX || ! REG_P (original))
222     {
223       if (lra_dump_file != NULL)
224         fprintf (lra_dump_file, "      Creating newreg=%i", REGNO (new_reg));
225     }
226   else
227     {
228       if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
229         ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
230       REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
231       REG_POINTER (new_reg) = REG_POINTER (original);
232       REG_ATTRS (new_reg) = REG_ATTRS (original);
233       if (lra_dump_file != NULL)
234         fprintf (lra_dump_file, "      Creating newreg=%i from oldreg=%i",
235                  REGNO (new_reg), REGNO (original));
236     }
237   if (lra_dump_file != NULL)
238     {
239       if (title != NULL)
240         fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
241                  reg_class_names[rclass], *title == '\0' ? "" : " ",
242                  title, REGNO (new_reg));
243       fprintf (lra_dump_file, "\n");
244     }
245   expand_reg_data (max_reg_num ());
246   setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
247   return new_reg;
248 }
249
250 /* Analogous to the previous function but also inherits value of
251    ORIGINAL.  */
252 rtx
253 lra_create_new_reg (machine_mode md_mode, rtx original,
254                     enum reg_class rclass, const char *title)
255 {
256   rtx new_reg;
257
258   new_reg
259     = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
260   if (original != NULL_RTX && REG_P (original))
261     lra_assign_reg_val (REGNO (original), REGNO (new_reg));
262   return new_reg;
263 }
264
265 /* Set up for REGNO unique hold value.  */
266 void
267 lra_set_regno_unique_value (int regno)
268 {
269   lra_reg_info[regno].val = get_new_reg_value ();
270 }
271
272 /* Invalidate INSN related info used by LRA.  The info should never be
273    used after that.  */
274 void
275 lra_invalidate_insn_data (rtx_insn *insn)
276 {
277   lra_invalidate_insn_regno_info (insn);
278   invalidate_insn_recog_data (INSN_UID (insn));
279 }
280
281 /* Mark INSN deleted and invalidate the insn related info used by
282    LRA.  */
283 void
284 lra_set_insn_deleted (rtx_insn *insn)
285 {
286   lra_invalidate_insn_data (insn);
287   SET_INSN_DELETED (insn);
288 }
289
290 /* Delete an unneeded INSN and any previous insns who sole purpose is
291    loading data that is dead in INSN.  */
292 void
293 lra_delete_dead_insn (rtx_insn *insn)
294 {
295   rtx_insn *prev = prev_real_insn (insn);
296   rtx prev_dest;
297
298   /* If the previous insn sets a register that dies in our insn,
299      delete it too.  */
300   if (prev && GET_CODE (PATTERN (prev)) == SET
301       && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
302       && reg_mentioned_p (prev_dest, PATTERN (insn))
303       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
304       && ! side_effects_p (SET_SRC (PATTERN (prev))))
305     lra_delete_dead_insn (prev);
306
307   lra_set_insn_deleted (insn);
308 }
309
310 /* Emit insn x = y + z.  Return NULL if we failed to do it.
311    Otherwise, return the insn.  We don't use gen_add3_insn as it might
312    clobber CC.  */
313 static rtx
314 emit_add3_insn (rtx x, rtx y, rtx z)
315 {
316   rtx_insn *last;
317
318   last = get_last_insn ();
319
320   if (have_addptr3_insn (x, y, z))
321     {
322       rtx insn = gen_addptr3_insn (x, y, z);
323
324       /* If the target provides an "addptr" pattern it hopefully does
325          for a reason.  So falling back to the normal add would be
326          a bug.  */
327       lra_assert (insn != NULL_RTX);
328       emit_insn (insn);
329       return insn;
330     }
331
332   rtx_insn *insn = emit_insn (gen_rtx_SET (VOIDmode, x,
333                                            gen_rtx_PLUS (GET_MODE (y), y, z)));
334   if (recog_memoized (insn) < 0)
335     {
336       delete_insns_since (last);
337       insn = NULL;
338     }
339   return insn;
340 }
341
342 /* Emit insn x = x + y.  Return the insn.  We use gen_add2_insn as the
343    last resort.  */
344 static rtx
345 emit_add2_insn (rtx x, rtx y)
346 {
347   rtx insn;
348
349   insn = emit_add3_insn (x, x, y);
350   if (insn == NULL_RTX)
351     {
352       insn = gen_add2_insn (x, y);
353       if (insn != NULL_RTX)
354         emit_insn (insn);
355     }
356   return insn;
357 }
358
359 /* Target checks operands through operand predicates to recognize an
360    insn.  We should have a special precaution to generate add insns
361    which are frequent results of elimination.
362
363    Emit insns for x = y + z.  X can be used to store intermediate
364    values and should be not in Y and Z when we use X to store an
365    intermediate value.  Y + Z should form [base] [+ index[ * scale]] [
366    + disp] where base and index are registers, disp and scale are
367    constants.  Y should contain base if it is present, Z should
368    contain disp if any.  index[*scale] can be part of Y or Z.  */
369 void
370 lra_emit_add (rtx x, rtx y, rtx z)
371 {
372   int old;
373   rtx_insn *last;
374   rtx a1, a2, base, index, disp, scale, index_scale;
375   bool ok_p;
376
377   rtx add3_insn = emit_add3_insn (x, y, z);
378   old = max_reg_num ();
379   if (add3_insn != NULL)
380     ;
381   else
382     {
383       disp = a2 = NULL_RTX;
384       if (GET_CODE (y) == PLUS)
385         {
386           a1 = XEXP (y, 0);
387           a2 = XEXP (y, 1);
388           disp = z;
389         }
390       else
391         {
392           a1 = y;
393           if (CONSTANT_P (z))
394             disp = z;
395           else
396             a2 = z;
397         }
398       index_scale = scale = NULL_RTX;
399       if (GET_CODE (a1) == MULT)
400         {
401           index_scale = a1;
402           index = XEXP (a1, 0);
403           scale = XEXP (a1, 1);
404           base = a2;
405         }
406       else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
407         {
408           index_scale = a2;
409           index = XEXP (a2, 0);
410           scale = XEXP (a2, 1);
411           base = a1;
412         }
413       else
414         {
415           base = a1;
416           index = a2;
417         }
418       if (! (REG_P (base) || GET_CODE (base) == SUBREG)
419           || (index != NULL_RTX
420               && ! (REG_P (index) || GET_CODE (index) == SUBREG))
421           || (disp != NULL_RTX && ! CONSTANT_P (disp))
422           || (scale != NULL_RTX && ! CONSTANT_P (scale)))
423         {
424           /* Probably we have no 3 op add.  Last chance is to use 2-op
425              add insn.  To succeed, don't move Z to X as an address
426              segment always comes in Y.  Otherwise, we might fail when
427              adding the address segment to register.  */
428           lra_assert (x != y && x != z);
429           emit_move_insn (x, y);
430           rtx insn = emit_add2_insn (x, z);
431           lra_assert (insn != NULL_RTX);
432         }
433       else
434         {
435           if (index_scale == NULL_RTX)
436             index_scale = index;
437           if (disp == NULL_RTX)
438             {
439               /* Generate x = index_scale; x = x + base.  */
440               lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
441               emit_move_insn (x, index_scale);
442               rtx insn = emit_add2_insn (x, base);
443               lra_assert (insn != NULL_RTX);
444             }
445           else if (scale == NULL_RTX)
446             {
447               /* Try x = base + disp.  */
448               lra_assert (base != NULL_RTX);
449               last = get_last_insn ();
450               rtx_insn *move_insn =
451                 emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), base, disp));
452               if (recog_memoized (move_insn) < 0)
453                 {
454                   delete_insns_since (last);
455                   /* Generate x = disp; x = x + base.  */
456                   emit_move_insn (x, disp);
457                   rtx add2_insn = emit_add2_insn (x, base);
458                   lra_assert (add2_insn != NULL_RTX);
459                 }
460               /* Generate x = x + index.  */
461               if (index != NULL_RTX)
462                 {
463                   rtx insn = emit_add2_insn (x, index);
464                   lra_assert (insn != NULL_RTX);
465                 }
466             }
467           else
468             {
469               /* Try x = index_scale; x = x + disp; x = x + base.  */
470               last = get_last_insn ();
471               rtx_insn *move_insn = emit_move_insn (x, index_scale);
472               ok_p = false;
473               if (recog_memoized (move_insn) >= 0)
474                 {
475                   rtx insn = emit_add2_insn (x, disp);
476                   if (insn != NULL_RTX)
477                     {
478                       insn = emit_add2_insn (x, disp);
479                       if (insn != NULL_RTX)
480                         ok_p = true;
481                     }
482                 }
483               if (! ok_p)
484                 {
485                   delete_insns_since (last);
486                   /* Generate x = disp; x = x + base; x = x + index_scale.  */
487                   emit_move_insn (x, disp);
488                   rtx insn = emit_add2_insn (x, base);
489                   lra_assert (insn != NULL_RTX);
490                   insn = emit_add2_insn (x, index_scale);
491                   lra_assert (insn != NULL_RTX);
492                 }
493             }
494         }
495     }
496   /* Functions emit_... can create pseudos -- so expand the pseudo
497      data.  */
498   if (old != max_reg_num ())
499     expand_reg_data (old);
500 }
501
502 /* The number of emitted reload insns so far.  */
503 int lra_curr_reload_num;
504
505 /* Emit x := y, processing special case when y = u + v or y = u + v *
506    scale + w through emit_add (Y can be an address which is base +
507    index reg * scale + displacement in general case).  X may be used
508    as intermediate result therefore it should be not in Y.  */
509 void
510 lra_emit_move (rtx x, rtx y)
511 {
512   int old;
513
514   if (GET_CODE (y) != PLUS)
515     {
516       if (rtx_equal_p (x, y))
517         return;
518       old = max_reg_num ();
519       emit_move_insn (x, y);
520       if (REG_P (x))
521         lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
522       /* Function emit_move can create pseudos -- so expand the pseudo
523          data.  */
524       if (old != max_reg_num ())
525         expand_reg_data (old);
526       return;
527     }
528   lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
529 }
530
531 /* Update insn operands which are duplication of operands whose
532    numbers are in array of NOPS (with end marker -1).  The insn is
533    represented by its LRA internal representation ID.  */
534 void
535 lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
536 {
537   int i, j, nop;
538   struct lra_static_insn_data *static_id = id->insn_static_data;
539
540   for (i = 0; i < static_id->n_dups; i++)
541     for (j = 0; (nop = nops[j]) >= 0; j++)
542       if (static_id->dup_num[i] == nop)
543         *id->dup_loc[i] = *id->operand_loc[nop];
544 }
545
546 \f
547
548 /* This page contains code dealing with info about registers in the
549    insns.  */
550
551 /* Pools for insn reg info.  */
552 static alloc_pool insn_reg_pool;
553
554 /* Initiate pool for insn reg info.  */
555 static void
556 init_insn_regs (void)
557 {
558   insn_reg_pool
559     = create_alloc_pool ("insn regs", sizeof (struct lra_insn_reg), 100);
560 }
561
562 /* Create LRA insn related info about a reference to REGNO in INSN with
563    TYPE (in/out/inout), biggest reference mode MODE, flag that it is
564    reference through subreg (SUBREG_P), flag that is early clobbered
565    in the insn (EARLY_CLOBBER), and reference to the next insn reg
566    info (NEXT).  */
567 static struct lra_insn_reg *
568 new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
569               machine_mode mode,
570               bool subreg_p, bool early_clobber, struct lra_insn_reg *next)
571 {
572   struct lra_insn_reg *ir;
573
574   ir = (struct lra_insn_reg *) pool_alloc (insn_reg_pool);
575   ir->type = type;
576   ir->biggest_mode = mode;
577   if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode)
578       && NONDEBUG_INSN_P (insn))
579     lra_reg_info[regno].biggest_mode = mode;
580   ir->subreg_p = subreg_p;
581   ir->early_clobber = early_clobber;
582   ir->regno = regno;
583   ir->next = next;
584   return ir;
585 }
586
587 /* Free insn reg info IR.  */
588 static void
589 free_insn_reg (struct lra_insn_reg *ir)
590 {
591   pool_free (insn_reg_pool, ir);
592 }
593
594 /* Free insn reg info list IR.  */
595 static void
596 free_insn_regs (struct lra_insn_reg *ir)
597 {
598   struct lra_insn_reg *next_ir;
599
600   for (; ir != NULL; ir = next_ir)
601     {
602       next_ir = ir->next;
603       free_insn_reg (ir);
604     }
605 }
606
607 /* Finish pool for insn reg info.  */
608 static void
609 finish_insn_regs (void)
610 {
611   free_alloc_pool (insn_reg_pool);
612 }
613
614 \f
615
616 /* This page contains code dealing LRA insn info (or in other words
617    LRA internal insn representation).  */
618
619 /* Map INSN_CODE -> the static insn data.  This info is valid during
620    all translation unit.  */
621 struct lra_static_insn_data *insn_code_data[LAST_INSN_CODE];
622
623 /* Debug insns are represented as a special insn with one input
624    operand which is RTL expression in var_location.  */
625
626 /* The following data are used as static insn operand data for all
627    debug insns.  If structure lra_operand_data is changed, the
628    initializer should be changed too.  */
629 static struct lra_operand_data debug_operand_data =
630   {
631     NULL, /* alternative  */
632     VOIDmode, /* We are not interesting in the operand mode.  */
633     OP_IN,
634     0, 0, 0, 0
635   };
636
637 /* The following data are used as static insn data for all debug
638    insns.  If structure lra_static_insn_data is changed, the
639    initializer should be changed too.  */
640 static struct lra_static_insn_data debug_insn_static_data =
641   {
642     &debug_operand_data,
643     0,  /* Duplication operands #.  */
644     -1, /* Commutative operand #.  */
645     1,  /* Operands #.  There is only one operand which is debug RTL
646            expression.  */
647     0,  /* Duplications #.  */
648     0,  /* Alternatives #.  We are not interesting in alternatives
649            because we does not proceed debug_insns for reloads.  */
650     NULL, /* Hard registers referenced in machine description.  */
651     NULL  /* Descriptions of operands in alternatives.  */
652   };
653
654 /* Called once per compiler work to initialize some LRA data related
655    to insns.  */
656 static void
657 init_insn_code_data_once (void)
658 {
659   memset (insn_code_data, 0, sizeof (insn_code_data));
660 }
661
662 /* Called once per compiler work to finalize some LRA data related to
663    insns.  */
664 static void
665 finish_insn_code_data_once (void)
666 {
667   int i;
668
669   for (i = 0; i < LAST_INSN_CODE; i++)
670     {
671       if (insn_code_data[i] != NULL)
672         free (insn_code_data[i]);
673     }
674 }
675
676 /* Return static insn data, allocate and setup if necessary.  Although
677    dup_num is static data (it depends only on icode), to set it up we
678    need to extract insn first.  So recog_data should be valid for
679    normal insn (ICODE >= 0) before the call.  */
680 static struct lra_static_insn_data *
681 get_static_insn_data (int icode, int nop, int ndup, int nalt)
682 {
683   struct lra_static_insn_data *data;
684   size_t n_bytes;
685
686   lra_assert (icode < LAST_INSN_CODE);
687   if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
688     return data;
689   lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
690   n_bytes = sizeof (struct lra_static_insn_data)
691             + sizeof (struct lra_operand_data) * nop
692             + sizeof (int) * ndup;
693   data = XNEWVAR (struct lra_static_insn_data, n_bytes);
694   data->operand_alternative = NULL;
695   data->n_operands = nop;
696   data->n_dups = ndup;
697   data->n_alternatives = nalt;
698   data->operand = ((struct lra_operand_data *)
699                    ((char *) data + sizeof (struct lra_static_insn_data)));
700   data->dup_num = ((int *) ((char *) data->operand
701                             + sizeof (struct lra_operand_data) * nop));
702   if (icode >= 0)
703     {
704       int i;
705
706       insn_code_data[icode] = data;
707       for (i = 0; i < nop; i++)
708         {
709           data->operand[i].constraint
710             = insn_data[icode].operand[i].constraint;
711           data->operand[i].mode = insn_data[icode].operand[i].mode;
712           data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
713           data->operand[i].is_operator
714             = insn_data[icode].operand[i].is_operator;
715           data->operand[i].type
716             = (data->operand[i].constraint[0] == '=' ? OP_OUT
717                : data->operand[i].constraint[0] == '+' ? OP_INOUT
718                : OP_IN);
719           data->operand[i].is_address = false;
720         }
721       for (i = 0; i < ndup; i++)
722         data->dup_num[i] = recog_data.dup_num[i];
723     }
724   return data;
725 }
726
727 /* The current length of the following array.  */
728 int lra_insn_recog_data_len;
729
730 /* Map INSN_UID -> the insn recog data (NULL if unknown).  */
731 lra_insn_recog_data_t *lra_insn_recog_data;
732
733 /* Initialize LRA data about insns.  */
734 static void
735 init_insn_recog_data (void)
736 {
737   lra_insn_recog_data_len = 0;
738   lra_insn_recog_data = NULL;
739   init_insn_regs ();
740 }
741
742 /* Expand, if necessary, LRA data about insns.  */
743 static void
744 check_and_expand_insn_recog_data (int index)
745 {
746   int i, old;
747
748   if (lra_insn_recog_data_len > index)
749     return;
750   old = lra_insn_recog_data_len;
751   lra_insn_recog_data_len = index * 3 / 2 + 1;
752   lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
753                                     lra_insn_recog_data,
754                                     lra_insn_recog_data_len);
755   for (i = old; i < lra_insn_recog_data_len; i++)
756     lra_insn_recog_data[i] = NULL;
757 }
758
759 /* Finish LRA DATA about insn.  */
760 static void
761 free_insn_recog_data (lra_insn_recog_data_t data)
762 {
763   if (data->operand_loc != NULL)
764     free (data->operand_loc);
765   if (data->dup_loc != NULL)
766     free (data->dup_loc);
767   if (data->arg_hard_regs != NULL)
768     free (data->arg_hard_regs);
769   if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
770     {
771       if (data->insn_static_data->operand_alternative != NULL)
772         free (const_cast <operand_alternative *>
773               (data->insn_static_data->operand_alternative));
774       free_insn_regs (data->insn_static_data->hard_regs);
775       free (data->insn_static_data);
776     }
777   free_insn_regs (data->regs);
778   data->regs = NULL;
779   free (data);
780 }
781
782 /* Finish LRA data about all insns.  */
783 static void
784 finish_insn_recog_data (void)
785 {
786   int i;
787   lra_insn_recog_data_t data;
788
789   for (i = 0; i < lra_insn_recog_data_len; i++)
790     if ((data = lra_insn_recog_data[i]) != NULL)
791       free_insn_recog_data (data);
792   finish_insn_regs ();
793   free (lra_insn_recog_data);
794 }
795
796 /* Setup info about operands in alternatives of LRA DATA of insn.  */
797 static void
798 setup_operand_alternative (lra_insn_recog_data_t data,
799                            const operand_alternative *op_alt)
800 {
801   int i, j, nop, nalt;
802   int icode = data->icode;
803   struct lra_static_insn_data *static_data = data->insn_static_data;
804
805   static_data->commutative = -1;
806   nop = static_data->n_operands;
807   nalt = static_data->n_alternatives;
808   static_data->operand_alternative = op_alt;
809   for (i = 0; i < nop; i++)
810     {
811       static_data->operand[i].early_clobber = false;
812       static_data->operand[i].is_address = false;
813       if (static_data->operand[i].constraint[0] == '%')
814         {
815           /* We currently only support one commutative pair of operands.  */
816           if (static_data->commutative < 0)
817             static_data->commutative = i;
818           else
819             lra_assert (icode < 0); /* Asm  */
820           /* The last operand should not be marked commutative.  */
821           lra_assert (i != nop - 1);
822         }
823     }
824   for (j = 0; j < nalt; j++)
825     for (i = 0; i < nop; i++, op_alt++)
826       {
827         static_data->operand[i].early_clobber |= op_alt->earlyclobber;
828         static_data->operand[i].is_address |= op_alt->is_address;
829       }
830 }
831
832 /* Recursively process X and collect info about registers, which are
833    not the insn operands, in X with TYPE (in/out/inout) and flag that
834    it is early clobbered in the insn (EARLY_CLOBBER) and add the info
835    to LIST.  X is a part of insn given by DATA.  Return the result
836    list.  */
837 static struct lra_insn_reg *
838 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data,
839                                struct lra_insn_reg *list,
840                                enum op_type type, bool early_clobber)
841 {
842   int i, j, regno, last;
843   bool subreg_p;
844   machine_mode mode;
845   struct lra_insn_reg *curr;
846   rtx op = *x;
847   enum rtx_code code = GET_CODE (op);
848   const char *fmt = GET_RTX_FORMAT (code);
849
850   for (i = 0; i < data->insn_static_data->n_operands; i++)
851     if (x == data->operand_loc[i])
852       /* It is an operand loc. Stop here.  */
853       return list;
854   for (i = 0; i < data->insn_static_data->n_dups; i++)
855     if (x == data->dup_loc[i])
856       /* It is a dup loc. Stop here.  */
857       return list;
858   mode = GET_MODE (op);
859   subreg_p = false;
860   if (code == SUBREG)
861     {
862       op = SUBREG_REG (op);
863       code = GET_CODE (op);
864       if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op)))
865         {
866           mode = GET_MODE (op);
867           if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
868             subreg_p = true;
869         }
870     }
871   if (REG_P (op))
872     {
873       if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
874         return list;
875       /* Process all regs even unallocatable ones as we need info
876          about all regs for rematerialization pass.  */
877       for (last = regno + hard_regno_nregs[regno][mode];
878            regno < last;
879            regno++)
880         {
881           for (curr = list; curr != NULL; curr = curr->next)
882             if (curr->regno == regno && curr->subreg_p == subreg_p
883                 && curr->biggest_mode == mode)
884               {
885                 if (curr->type != type)
886                   curr->type = OP_INOUT;
887                 if (curr->early_clobber != early_clobber)
888                   curr->early_clobber = true;
889                 break;
890               }
891           if (curr == NULL)
892             {
893               /* This is a new hard regno or the info can not be
894                  integrated into the found structure.    */
895 #ifdef STACK_REGS
896               early_clobber
897                 = (early_clobber
898                    /* This clobber is to inform popping floating
899                       point stack only.  */
900                    && ! (FIRST_STACK_REG <= regno
901                          && regno <= LAST_STACK_REG));
902 #endif
903               list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
904                                    early_clobber, list);
905             }
906         }
907       return list;
908     }
909   switch (code)
910     {
911     case SET:
912       list = collect_non_operand_hard_regs (&SET_DEST (op), data,
913                                             list, OP_OUT, false);
914       list = collect_non_operand_hard_regs (&SET_SRC (op), data,
915                                             list, OP_IN, false);
916       break;
917     case CLOBBER:
918       /* We treat clobber of non-operand hard registers as early
919          clobber (the behavior is expected from asm).  */
920       list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
921                                             list, OP_OUT, true);
922       break;
923     case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
924       list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
925                                             list, OP_INOUT, false);
926       break;
927     case PRE_MODIFY: case POST_MODIFY:
928       list = collect_non_operand_hard_regs (&XEXP (op, 0), data,
929                                             list, OP_INOUT, false);
930       list = collect_non_operand_hard_regs (&XEXP (op, 1), data,
931                                             list, OP_IN, false);
932       break;
933     default:
934       fmt = GET_RTX_FORMAT (code);
935       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
936         {
937           if (fmt[i] == 'e')
938             list = collect_non_operand_hard_regs (&XEXP (op, i), data,
939                                                   list, OP_IN, false);
940           else if (fmt[i] == 'E')
941             for (j = XVECLEN (op, i) - 1; j >= 0; j--)
942               list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data,
943                                                     list, OP_IN, false);
944         }
945     }
946   return list;
947 }
948
949 /* Set up and return info about INSN.  Set up the info if it is not set up
950    yet.  */
951 lra_insn_recog_data_t
952 lra_set_insn_recog_data (rtx_insn *insn)
953 {
954   lra_insn_recog_data_t data;
955   int i, n, icode;
956   rtx **locs;
957   unsigned int uid = INSN_UID (insn);
958   struct lra_static_insn_data *insn_static_data;
959
960   check_and_expand_insn_recog_data (uid);
961   if (DEBUG_INSN_P (insn))
962     icode = -1;
963   else
964     {
965       icode = INSN_CODE (insn);
966       if (icode < 0)
967         /* It might be a new simple insn which is not recognized yet.  */
968         INSN_CODE (insn) = icode = recog_memoized (insn);
969     }
970   data = XNEW (struct lra_insn_recog_data);
971   lra_insn_recog_data[uid] = data;
972   data->insn = insn;
973   data->used_insn_alternative = -1;
974   data->icode = icode;
975   data->regs = NULL;
976   if (DEBUG_INSN_P (insn))
977     {
978       data->insn_static_data = &debug_insn_static_data;
979       data->dup_loc = NULL;
980       data->arg_hard_regs = NULL;
981       data->preferred_alternatives = ALL_ALTERNATIVES;
982       data->operand_loc = XNEWVEC (rtx *, 1);
983       data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
984       return data;
985     }
986   if (icode < 0)
987     {
988       int nop, nalt;
989       machine_mode operand_mode[MAX_RECOG_OPERANDS];
990       const char *constraints[MAX_RECOG_OPERANDS];
991
992       nop = asm_noperands (PATTERN (insn));
993       data->operand_loc = data->dup_loc = NULL;
994       nalt = 1;
995       if (nop < 0)
996         {
997           /* It is a special insn like USE or CLOBBER.  We should
998              recognize any regular insn otherwise LRA can do nothing
999              with this insn.  */
1000           gcc_assert (GET_CODE (PATTERN (insn)) == USE
1001                       || GET_CODE (PATTERN (insn)) == CLOBBER
1002                       || GET_CODE (PATTERN (insn)) == ASM_INPUT);
1003           data->insn_static_data = insn_static_data
1004             = get_static_insn_data (-1, 0, 0, nalt);
1005         }
1006       else
1007         {
1008           /* expand_asm_operands makes sure there aren't too many
1009              operands.  */
1010           lra_assert (nop <= MAX_RECOG_OPERANDS);
1011           if (nop != 0)
1012             data->operand_loc = XNEWVEC (rtx *, nop);
1013           /* Now get the operand values and constraints out of the
1014              insn.  */
1015           decode_asm_operands (PATTERN (insn), NULL,
1016                                data->operand_loc,
1017                                constraints, operand_mode, NULL);
1018           if (nop > 0)
1019             {
1020               const char *p =  recog_data.constraints[0];
1021
1022               for (p =  constraints[0]; *p; p++)
1023                 nalt += *p == ',';
1024             }
1025           data->insn_static_data = insn_static_data
1026             = get_static_insn_data (-1, nop, 0, nalt);
1027           for (i = 0; i < nop; i++)
1028             {
1029               insn_static_data->operand[i].mode = operand_mode[i];
1030               insn_static_data->operand[i].constraint = constraints[i];
1031               insn_static_data->operand[i].strict_low = false;
1032               insn_static_data->operand[i].is_operator = false;
1033               insn_static_data->operand[i].is_address = false;
1034             }
1035         }
1036       for (i = 0; i < insn_static_data->n_operands; i++)
1037         insn_static_data->operand[i].type
1038           = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1039              : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1040              : OP_IN);
1041       data->preferred_alternatives = ALL_ALTERNATIVES;
1042       if (nop > 0)
1043         {
1044           operand_alternative *op_alt = XCNEWVEC (operand_alternative,
1045                                                   nalt * nop);
1046           preprocess_constraints (nop, nalt, constraints, op_alt);
1047           setup_operand_alternative (data, op_alt);
1048         }
1049     }
1050   else
1051     {
1052       insn_extract (insn);
1053       data->insn_static_data = insn_static_data
1054         = get_static_insn_data (icode, insn_data[icode].n_operands,
1055                                 insn_data[icode].n_dups,
1056                                 insn_data[icode].n_alternatives);
1057       n = insn_static_data->n_operands;
1058       if (n == 0)
1059         locs = NULL;
1060       else
1061         {
1062           locs = XNEWVEC (rtx *, n);
1063           memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
1064         }
1065       data->operand_loc = locs;
1066       n = insn_static_data->n_dups;
1067       if (n == 0)
1068         locs = NULL;
1069       else
1070         {
1071           locs = XNEWVEC (rtx *, n);
1072           memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
1073         }
1074       data->dup_loc = locs;
1075       data->preferred_alternatives = get_preferred_alternatives (insn);
1076       const operand_alternative *op_alt = preprocess_insn_constraints (icode);
1077       if (!insn_static_data->operand_alternative)
1078         setup_operand_alternative (data, op_alt);
1079       else if (op_alt != insn_static_data->operand_alternative)
1080         insn_static_data->operand_alternative = op_alt;
1081     }
1082   if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
1083     insn_static_data->hard_regs = NULL;
1084   else
1085     insn_static_data->hard_regs
1086       = collect_non_operand_hard_regs (&PATTERN (insn), data,
1087                                        NULL, OP_IN, false);
1088   data->arg_hard_regs = NULL;
1089   if (CALL_P (insn))
1090     {
1091       rtx link;
1092       int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
1093
1094       n_hard_regs = 0;
1095       /* Finding implicit hard register usage.  We believe it will be
1096          not changed whatever transformations are used.  Call insns
1097          are such example.  */
1098       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1099            link != NULL_RTX;
1100            link = XEXP (link, 1))
1101         if (GET_CODE (XEXP (link, 0)) == USE
1102             && REG_P (XEXP (XEXP (link, 0), 0)))
1103           {
1104             regno = REGNO (XEXP (XEXP (link, 0), 0));
1105             lra_assert (regno < FIRST_PSEUDO_REGISTER);
1106             /* It is an argument register.  */
1107             for (i = (hard_regno_nregs
1108                       [regno][GET_MODE (XEXP (XEXP (link, 0), 0))]) - 1;
1109                  i >= 0;
1110                  i--)
1111               arg_hard_regs[n_hard_regs++] = regno + i;
1112           }
1113       if (n_hard_regs != 0)
1114         {
1115           arg_hard_regs[n_hard_regs++] = -1;
1116           data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
1117           memcpy (data->arg_hard_regs, arg_hard_regs,
1118                   sizeof (int) * n_hard_regs);
1119         }
1120     }
1121   /* Some output operand can be recognized only from the context not
1122      from the constraints which are empty in this case.  Call insn may
1123      contain a hard register in set destination with empty constraint
1124      and extract_insn treats them as an input.  */
1125   for (i = 0; i < insn_static_data->n_operands; i++)
1126     {
1127       int j;
1128       rtx pat, set;
1129       struct lra_operand_data *operand = &insn_static_data->operand[i];
1130
1131       /* ??? Should we treat 'X' the same way.  It looks to me that
1132          'X' means anything and empty constraint means we do not
1133          care.  */
1134       if (operand->type != OP_IN || *operand->constraint != '\0'
1135           || operand->is_operator)
1136         continue;
1137       pat = PATTERN (insn);
1138       if (GET_CODE (pat) == SET)
1139         {
1140           if (data->operand_loc[i] != &SET_DEST (pat))
1141             continue;
1142         }
1143       else if (GET_CODE (pat) == PARALLEL)
1144         {
1145           for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
1146             {
1147               set = XVECEXP (PATTERN (insn), 0, j);
1148               if (GET_CODE (set) == SET
1149                   && &SET_DEST (set) == data->operand_loc[i])
1150                 break;
1151             }
1152           if (j < 0)
1153             continue;
1154         }
1155       else
1156         continue;
1157       operand->type = OP_OUT;
1158     }
1159   return data;
1160 }
1161
1162 /* Return info about insn give by UID.  The info should be already set
1163    up.  */
1164 static lra_insn_recog_data_t
1165 get_insn_recog_data_by_uid (int uid)
1166 {
1167   lra_insn_recog_data_t data;
1168
1169   data = lra_insn_recog_data[uid];
1170   lra_assert (data != NULL);
1171   return data;
1172 }
1173
1174 /* Invalidate all info about insn given by its UID.  */
1175 static void
1176 invalidate_insn_recog_data (int uid)
1177 {
1178   lra_insn_recog_data_t data;
1179
1180   data = lra_insn_recog_data[uid];
1181   lra_assert (data != NULL);
1182   free_insn_recog_data (data);
1183   lra_insn_recog_data[uid] = NULL;
1184 }
1185
1186 /* Update all the insn info about INSN.  It is usually called when
1187    something in the insn was changed.  Return the updated info.  */
1188 lra_insn_recog_data_t
1189 lra_update_insn_recog_data (rtx_insn *insn)
1190 {
1191   lra_insn_recog_data_t data;
1192   int n;
1193   unsigned int uid = INSN_UID (insn);
1194   struct lra_static_insn_data *insn_static_data;
1195   HOST_WIDE_INT sp_offset = 0;
1196
1197   check_and_expand_insn_recog_data (uid);
1198   if ((data = lra_insn_recog_data[uid]) != NULL
1199       && data->icode != INSN_CODE (insn))
1200     {
1201       sp_offset = data->sp_offset;
1202       invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
1203       invalidate_insn_recog_data (uid);
1204       data = NULL;
1205     }
1206   if (data == NULL)
1207     {
1208       data = lra_get_insn_recog_data (insn);
1209       /* Initiate or restore SP offset.  */
1210       data->sp_offset = sp_offset;
1211       return data;
1212     }
1213   insn_static_data = data->insn_static_data;
1214   data->used_insn_alternative = -1;
1215   if (DEBUG_INSN_P (insn))
1216     return data;
1217   if (data->icode < 0)
1218     {
1219       int nop;
1220       machine_mode operand_mode[MAX_RECOG_OPERANDS];
1221       const char *constraints[MAX_RECOG_OPERANDS];
1222
1223       nop = asm_noperands (PATTERN (insn));
1224       if (nop >= 0)
1225         {
1226           lra_assert (nop == data->insn_static_data->n_operands);
1227           /* Now get the operand values and constraints out of the
1228              insn.  */
1229           decode_asm_operands (PATTERN (insn), NULL,
1230                                data->operand_loc,
1231                                constraints, operand_mode, NULL);
1232 #ifdef ENABLE_CHECKING
1233           {
1234             int i;
1235
1236             for (i = 0; i < nop; i++)
1237               lra_assert
1238                 (insn_static_data->operand[i].mode == operand_mode[i]
1239                  && insn_static_data->operand[i].constraint == constraints[i]
1240                  && ! insn_static_data->operand[i].is_operator);
1241           }
1242 #endif
1243         }
1244 #ifdef ENABLE_CHECKING
1245       {
1246         int i;
1247
1248         for (i = 0; i < insn_static_data->n_operands; i++)
1249           lra_assert
1250             (insn_static_data->operand[i].type
1251              == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
1252                  : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
1253                  : OP_IN));
1254       }
1255 #endif
1256     }
1257   else
1258     {
1259       insn_extract (insn);
1260       n = insn_static_data->n_operands;
1261       if (n != 0)
1262         memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
1263       n = insn_static_data->n_dups;
1264       if (n != 0)
1265         memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
1266       lra_assert (check_bool_attrs (insn));
1267     }
1268   return data;
1269 }
1270
1271 /* Set up that INSN is using alternative ALT now.  */
1272 void
1273 lra_set_used_insn_alternative (rtx_insn *insn, int alt)
1274 {
1275   lra_insn_recog_data_t data;
1276
1277   data = lra_get_insn_recog_data (insn);
1278   data->used_insn_alternative = alt;
1279 }
1280
1281 /* Set up that insn with UID is using alternative ALT now.  The insn
1282    info should be already set up.  */
1283 void
1284 lra_set_used_insn_alternative_by_uid (int uid, int alt)
1285 {
1286   lra_insn_recog_data_t data;
1287
1288   check_and_expand_insn_recog_data (uid);
1289   data = lra_insn_recog_data[uid];
1290   lra_assert (data != NULL);
1291   data->used_insn_alternative = alt;
1292 }
1293
1294 \f
1295
1296 /* This page contains code dealing with common register info and
1297    pseudo copies.  */
1298
1299 /* The size of the following array.  */
1300 static int reg_info_size;
1301 /* Common info about each register.  */
1302 struct lra_reg *lra_reg_info;
1303
1304 /* Last register value.  */
1305 static int last_reg_value;
1306
1307 /* Return new register value.  */
1308 static int
1309 get_new_reg_value (void)
1310 {
1311   return ++last_reg_value;
1312 }
1313
1314 /* Pools for copies.  */
1315 static alloc_pool copy_pool;
1316
1317 /* Vec referring to pseudo copies.  */
1318 static vec<lra_copy_t> copy_vec;
1319
1320 /* Initialize I-th element of lra_reg_info.  */
1321 static inline void
1322 initialize_lra_reg_info_element (int i)
1323 {
1324   bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
1325 #ifdef STACK_REGS
1326   lra_reg_info[i].no_stack_p = false;
1327 #endif
1328   CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1329   CLEAR_HARD_REG_SET (lra_reg_info[i].actual_call_used_reg_set);
1330   lra_reg_info[i].preferred_hard_regno1 = -1;
1331   lra_reg_info[i].preferred_hard_regno2 = -1;
1332   lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1333   lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1334   lra_reg_info[i].biggest_mode = VOIDmode;
1335   lra_reg_info[i].live_ranges = NULL;
1336   lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
1337   lra_reg_info[i].last_reload = 0;
1338   lra_reg_info[i].restore_regno = -1;
1339   lra_reg_info[i].val = get_new_reg_value ();
1340   lra_reg_info[i].offset = 0;
1341   lra_reg_info[i].copies = NULL;
1342 }
1343
1344 /* Initialize common reg info and copies.  */
1345 static void
1346 init_reg_info (void)
1347 {
1348   int i;
1349
1350   last_reg_value = 0;
1351   reg_info_size = max_reg_num () * 3 / 2 + 1;
1352   lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size);
1353   for (i = 0; i < reg_info_size; i++)
1354     initialize_lra_reg_info_element (i);
1355   copy_pool
1356     = create_alloc_pool ("lra copies", sizeof (struct lra_copy), 100);
1357   copy_vec.create (100);
1358 }
1359
1360
1361 /* Finish common reg info and copies.  */
1362 static void
1363 finish_reg_info (void)
1364 {
1365   int i;
1366
1367   for (i = 0; i < reg_info_size; i++)
1368     bitmap_clear (&lra_reg_info[i].insn_bitmap);
1369   free (lra_reg_info);
1370   reg_info_size = 0;
1371   free_alloc_pool (copy_pool);
1372   copy_vec.release ();
1373 }
1374
1375 /* Expand common reg info if it is necessary.  */
1376 static void
1377 expand_reg_info (void)
1378 {
1379   int i, old = reg_info_size;
1380
1381   if (reg_info_size > max_reg_num ())
1382     return;
1383   reg_info_size = max_reg_num () * 3 / 2 + 1;
1384   lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size);
1385   for (i = old; i < reg_info_size; i++)
1386     initialize_lra_reg_info_element (i);
1387 }
1388
1389 /* Free all copies.  */
1390 void
1391 lra_free_copies (void)
1392 {
1393   lra_copy_t cp;
1394
1395   while (copy_vec.length () != 0)
1396     {
1397       cp = copy_vec.pop ();
1398       lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
1399       pool_free (copy_pool, cp);
1400     }
1401 }
1402
1403 /* Create copy of two pseudos REGNO1 and REGNO2.  The copy execution
1404    frequency is FREQ.  */
1405 void
1406 lra_create_copy (int regno1, int regno2, int freq)
1407 {
1408   bool regno1_dest_p;
1409   lra_copy_t cp;
1410
1411   lra_assert (regno1 != regno2);
1412   regno1_dest_p = true;
1413   if (regno1 > regno2)
1414     {
1415       int temp = regno2;
1416
1417       regno1_dest_p = false;
1418       regno2 = regno1;
1419       regno1 = temp;
1420     }
1421   cp = (lra_copy_t) pool_alloc (copy_pool);
1422   copy_vec.safe_push (cp);
1423   cp->regno1_dest_p = regno1_dest_p;
1424   cp->freq = freq;
1425   cp->regno1 = regno1;
1426   cp->regno2 = regno2;
1427   cp->regno1_next = lra_reg_info[regno1].copies;
1428   lra_reg_info[regno1].copies = cp;
1429   cp->regno2_next = lra_reg_info[regno2].copies;
1430   lra_reg_info[regno2].copies = cp;
1431   if (lra_dump_file != NULL)
1432     fprintf (lra_dump_file, "      Creating copy r%d%sr%d@%d\n",
1433              regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
1434 }
1435
1436 /* Return N-th (0, 1, ...) copy.  If there is no copy, return
1437    NULL.  */
1438 lra_copy_t
1439 lra_get_copy (int n)
1440 {
1441   if (n >= (int) copy_vec.length ())
1442     return NULL;
1443   return copy_vec[n];
1444 }
1445
1446 \f
1447
1448 /* This page contains code dealing with info about registers in
1449    insns.  */
1450
1451 /* Process X of insn UID recursively and add info (operand type is
1452    given by TYPE, flag of that it is early clobber is EARLY_CLOBBER)
1453    about registers in X to the insn DATA.  */
1454 static void
1455 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid,
1456                              enum op_type type, bool early_clobber)
1457 {
1458   int i, j, regno;
1459   bool subreg_p;
1460   machine_mode mode;
1461   const char *fmt;
1462   enum rtx_code code;
1463   struct lra_insn_reg *curr;
1464
1465   code = GET_CODE (x);
1466   mode = GET_MODE (x);
1467   subreg_p = false;
1468   if (GET_CODE (x) == SUBREG)
1469     {
1470       x = SUBREG_REG (x);
1471       code = GET_CODE (x);
1472       if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x)))
1473         {
1474           mode = GET_MODE (x);
1475           if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode))
1476             subreg_p = true;
1477         }
1478     }
1479   if (REG_P (x))
1480     {
1481       regno = REGNO (x);
1482       /* Process all regs even unallocatable ones as we need info about
1483          all regs for rematerialization pass.  */
1484       expand_reg_info ();
1485       if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid))
1486         {
1487           data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
1488                                      early_clobber, data->regs);
1489           return;
1490         }
1491       else
1492         {
1493           for (curr = data->regs; curr != NULL; curr = curr->next)
1494             if (curr->regno == regno)
1495               {
1496                 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
1497                   /* The info can not be integrated into the found
1498                      structure.  */
1499                   data->regs = new_insn_reg (data->insn, regno, type, mode,
1500                                              subreg_p, early_clobber,
1501                                              data->regs);
1502                 else
1503                   {
1504                     if (curr->type != type)
1505                       curr->type = OP_INOUT;
1506                     if (curr->early_clobber != early_clobber)
1507                       curr->early_clobber = true;
1508                   }
1509                 return;
1510               }
1511           gcc_unreachable ();
1512         }
1513     }
1514
1515   switch (code)
1516     {
1517     case SET:
1518       add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false);
1519       add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false);
1520       break;
1521     case CLOBBER:
1522       /* We treat clobber of non-operand hard registers as early
1523          clobber (the behavior is expected from asm).  */
1524       add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true);
1525       break;
1526     case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
1527       add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1528       break;
1529     case PRE_MODIFY: case POST_MODIFY:
1530       add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false);
1531       add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false);
1532       break;
1533     default:
1534       if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
1535         /* Some targets place small structures in registers for return
1536            values of functions, and those registers are wrapped in
1537            PARALLEL that we may see as the destination of a SET.  Here
1538            is an example:
1539
1540            (call_insn 13 12 14 2 (set (parallel:BLK [
1541                 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
1542                     (const_int 0 [0]))
1543                 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
1544                     (const_int 8 [0x8]))
1545                ])
1546              (call (mem:QI (symbol_ref:DI (...  */
1547         type = OP_IN;
1548       fmt = GET_RTX_FORMAT (code);
1549       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1550         {
1551           if (fmt[i] == 'e')
1552             add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false);
1553           else if (fmt[i] == 'E')
1554             {
1555               for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1556                 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid,
1557                                              type, false);
1558             }
1559         }
1560     }
1561 }
1562
1563 /* Return execution frequency of INSN.  */
1564 static int
1565 get_insn_freq (rtx_insn *insn)
1566 {
1567   basic_block bb = BLOCK_FOR_INSN (insn);
1568
1569   gcc_checking_assert (bb != NULL);
1570   return REG_FREQ_FROM_BB (bb);
1571 }
1572
1573 /* Invalidate all reg info of INSN with DATA and execution frequency
1574    FREQ.  Update common info about the invalidated registers.  */
1575 static void
1576 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
1577                                  int freq)
1578 {
1579   int uid;
1580   bool debug_p;
1581   unsigned int i;
1582   struct lra_insn_reg *ir, *next_ir;
1583
1584   uid = INSN_UID (insn);
1585   debug_p = DEBUG_INSN_P (insn);
1586   for (ir = data->regs; ir != NULL; ir = next_ir)
1587     {
1588       i = ir->regno;
1589       next_ir = ir->next;
1590       free_insn_reg (ir);
1591       bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
1592       if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
1593         {
1594           lra_reg_info[i].nrefs--;
1595           lra_reg_info[i].freq -= freq;
1596           lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
1597         }
1598     }
1599   data->regs = NULL;
1600 }
1601
1602 /* Invalidate all reg info of INSN.  Update common info about the
1603    invalidated registers.  */
1604 void
1605 lra_invalidate_insn_regno_info (rtx_insn *insn)
1606 {
1607   invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
1608                                    get_insn_freq (insn));
1609 }
1610
1611 /* Update common reg info from reg info of insn given by its DATA and
1612    execution frequency FREQ.  */
1613 static void
1614 setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
1615 {
1616   unsigned int i;
1617   struct lra_insn_reg *ir;
1618
1619   for (ir = data->regs; ir != NULL; ir = ir->next)
1620     if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
1621       {
1622         lra_reg_info[i].nrefs++;
1623         lra_reg_info[i].freq += freq;
1624       }
1625 }
1626
1627 /* Set up insn reg info of INSN.  Update common reg info from reg info
1628    of INSN.  */
1629 void
1630 lra_update_insn_regno_info (rtx_insn *insn)
1631 {
1632   int i, uid, freq;
1633   lra_insn_recog_data_t data;
1634   struct lra_static_insn_data *static_data;
1635   enum rtx_code code;
1636
1637   if (! INSN_P (insn))
1638     return;
1639   data = lra_get_insn_recog_data (insn);
1640   static_data = data->insn_static_data;
1641   freq = get_insn_freq (insn);
1642   invalidate_insn_data_regno_info (data, insn, freq);
1643   uid = INSN_UID (insn);
1644   for (i = static_data->n_operands - 1; i >= 0; i--)
1645     add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid,
1646                                  static_data->operand[i].type,
1647                                  static_data->operand[i].early_clobber);
1648   if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
1649     add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid,
1650                                  code == USE ? OP_IN : OP_OUT, false);
1651   if (NONDEBUG_INSN_P (insn))
1652     setup_insn_reg_info (data, freq);
1653 }
1654
1655 /* Return reg info of insn given by it UID.  */
1656 struct lra_insn_reg *
1657 lra_get_insn_regs (int uid)
1658 {
1659   lra_insn_recog_data_t data;
1660
1661   data = get_insn_recog_data_by_uid (uid);
1662   return data->regs;
1663 }
1664
1665 \f
1666
1667 /* This page contains code dealing with stack of the insns which
1668    should be processed by the next constraint pass.  */
1669
1670 /* Bitmap used to put an insn on the stack only in one exemplar.  */
1671 static sbitmap lra_constraint_insn_stack_bitmap;
1672
1673 /* The stack itself.  */
1674 vec<rtx_insn *> lra_constraint_insn_stack;
1675
1676 /* Put INSN on the stack.  If ALWAYS_UPDATE is true, always update the reg
1677    info for INSN, otherwise only update it if INSN is not already on the
1678    stack.  */
1679 static inline void
1680 lra_push_insn_1 (rtx_insn *insn, bool always_update)
1681 {
1682   unsigned int uid = INSN_UID (insn);
1683   if (always_update)
1684     lra_update_insn_regno_info (insn);
1685   if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
1686     lra_constraint_insn_stack_bitmap =
1687       sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
1688   if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
1689     return;
1690   bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
1691   if (! always_update)
1692     lra_update_insn_regno_info (insn);
1693   lra_constraint_insn_stack.safe_push (insn);
1694 }
1695
1696 /* Put INSN on the stack.  */
1697 void
1698 lra_push_insn (rtx_insn *insn)
1699 {
1700   lra_push_insn_1 (insn, false);
1701 }
1702
1703 /* Put INSN on the stack and update its reg info.  */
1704 void
1705 lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
1706 {
1707   lra_push_insn_1 (insn, true);
1708 }
1709
1710 /* Put insn with UID on the stack.  */
1711 void
1712 lra_push_insn_by_uid (unsigned int uid)
1713 {
1714   lra_push_insn (lra_insn_recog_data[uid]->insn);
1715 }
1716
1717 /* Take the last-inserted insns off the stack and return it.  */
1718 rtx_insn *
1719 lra_pop_insn (void)
1720 {
1721   rtx_insn *insn = lra_constraint_insn_stack.pop ();
1722   bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
1723   return insn;
1724 }
1725
1726 /* Return the current size of the insn stack.  */
1727 unsigned int
1728 lra_insn_stack_length (void)
1729 {
1730   return lra_constraint_insn_stack.length ();
1731 }
1732
1733 /* Push insns FROM to TO (excluding it) going in reverse order.  */
1734 static void
1735 push_insns (rtx_insn *from, rtx_insn *to)
1736 {
1737   rtx_insn *insn;
1738
1739   if (from == NULL_RTX)
1740     return;
1741   for (insn = from; insn != to; insn = PREV_INSN (insn))
1742     if (INSN_P (insn))
1743       lra_push_insn (insn);
1744 }
1745
1746 /* Set up sp offset for insn in range [FROM, LAST].  The offset is
1747    taken from the next BB insn after LAST or zero if there in such
1748    insn.  */
1749 static void
1750 setup_sp_offset (rtx_insn *from, rtx_insn *last)
1751 {
1752   rtx_insn *before = next_nonnote_insn_bb (last);
1753   HOST_WIDE_INT offset = (before == NULL_RTX || ! INSN_P (before)
1754                           ? 0 : lra_get_insn_recog_data (before)->sp_offset);
1755
1756   for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
1757     lra_get_insn_recog_data (insn)->sp_offset = offset;
1758 }
1759
1760 /* Emit insns BEFORE before INSN and insns AFTER after INSN.  Put the
1761    insns onto the stack.  Print about emitting the insns with
1762    TITLE.  */
1763 void
1764 lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
1765                        const char *title)
1766 {
1767   rtx_insn *last;
1768
1769   if (before == NULL_RTX && after == NULL_RTX)
1770     return;
1771   if (lra_dump_file != NULL)
1772     {
1773       dump_insn_slim (lra_dump_file, insn);
1774       if (before != NULL_RTX)
1775         {
1776           fprintf (lra_dump_file,"    %s before:\n", title);
1777           dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
1778         }
1779       if (after != NULL_RTX)
1780         {
1781           fprintf (lra_dump_file, "    %s after:\n", title);
1782           dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
1783         }
1784       fprintf (lra_dump_file, "\n");
1785     }
1786   if (before != NULL_RTX)
1787     {
1788       emit_insn_before (before, insn);
1789       push_insns (PREV_INSN (insn), PREV_INSN (before));
1790       setup_sp_offset (before, PREV_INSN (insn));
1791     }
1792   if (after != NULL_RTX)
1793     {
1794       for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
1795         ;
1796       emit_insn_after (after, insn);
1797       push_insns (last, insn);
1798       setup_sp_offset (after, last);
1799     }
1800 }
1801
1802 \f
1803
1804 /* Replace all references to register OLD_REGNO in *LOC with pseudo
1805    register NEW_REG.  Return true if any change was made.  */
1806 bool
1807 lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg)
1808 {
1809   rtx x = *loc;
1810   bool result = false;
1811   enum rtx_code code;
1812   const char *fmt;
1813   int i, j;
1814
1815   if (x == NULL_RTX)
1816     return false;
1817
1818   code = GET_CODE (x);
1819   if (code == REG && (int) REGNO (x) == old_regno)
1820     {
1821       machine_mode mode = GET_MODE (*loc);
1822       machine_mode inner_mode = GET_MODE (new_reg);
1823
1824       if (mode != inner_mode
1825           && ! (CONST_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
1826         {
1827           if (GET_MODE_SIZE (mode) >= GET_MODE_SIZE (inner_mode)
1828               || ! SCALAR_INT_MODE_P (inner_mode))
1829             new_reg = gen_rtx_SUBREG (mode, new_reg, 0);
1830           else
1831             new_reg = gen_lowpart_SUBREG (mode, new_reg);
1832         }
1833       *loc = new_reg;
1834       return true;
1835     }
1836
1837   /* Scan all the operand sub-expressions.  */
1838   fmt = GET_RTX_FORMAT (code);
1839   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1840     {
1841       if (fmt[i] == 'e')
1842         {
1843           if (lra_substitute_pseudo (&XEXP (x, i), old_regno, new_reg))
1844             result = true;
1845         }
1846       else if (fmt[i] == 'E')
1847         {
1848           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1849             if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno, new_reg))
1850               result = true;
1851         }
1852     }
1853   return result;
1854 }
1855
1856 /* Call lra_substitute_pseudo within an insn.  This won't update the insn ptr,
1857    just the contents of the insn.  */
1858 bool
1859 lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno, rtx new_reg)
1860 {
1861   rtx loc = insn;
1862   return lra_substitute_pseudo (&loc, old_regno, new_reg);
1863 }
1864
1865 \f
1866
1867 /* This page contains code dealing with scratches (changing them onto
1868    pseudos and restoring them from the pseudos).
1869
1870    We change scratches into pseudos at the beginning of LRA to
1871    simplify dealing with them (conflicts, hard register assignments).
1872
1873    If the pseudo denoting scratch was spilled it means that we do need
1874    a hard register for it.  Such pseudos are transformed back to
1875    scratches at the end of LRA.  */
1876
1877 /* Description of location of a former scratch operand.  */
1878 struct sloc
1879 {
1880   rtx_insn *insn; /* Insn where the scratch was.  */
1881   int nop;  /* Number of the operand which was a scratch.  */
1882 };
1883
1884 typedef struct sloc *sloc_t;
1885
1886 /* Locations of the former scratches.  */
1887 static vec<sloc_t> scratches;
1888
1889 /* Bitmap of scratch regnos.  */
1890 static bitmap_head scratch_bitmap;
1891
1892 /* Bitmap of scratch operands.  */
1893 static bitmap_head scratch_operand_bitmap;
1894
1895 /* Return true if pseudo REGNO is made of SCRATCH.  */
1896 bool
1897 lra_former_scratch_p (int regno)
1898 {
1899   return bitmap_bit_p (&scratch_bitmap, regno);
1900 }
1901
1902 /* Return true if the operand NOP of INSN is a former scratch.  */
1903 bool
1904 lra_former_scratch_operand_p (rtx_insn *insn, int nop)
1905 {
1906   return bitmap_bit_p (&scratch_operand_bitmap,
1907                        INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
1908 }
1909
1910 /* Change scratches onto pseudos and save their location.  */
1911 static void
1912 remove_scratches (void)
1913 {
1914   int i;
1915   bool insn_changed_p;
1916   basic_block bb;
1917   rtx_insn *insn;
1918   rtx reg;
1919   sloc_t loc;
1920   lra_insn_recog_data_t id;
1921   struct lra_static_insn_data *static_id;
1922
1923   scratches.create (get_max_uid ());
1924   bitmap_initialize (&scratch_bitmap, &reg_obstack);
1925   bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
1926   FOR_EACH_BB_FN (bb, cfun)
1927     FOR_BB_INSNS (bb, insn)
1928     if (INSN_P (insn))
1929       {
1930         id = lra_get_insn_recog_data (insn);
1931         static_id = id->insn_static_data;
1932         insn_changed_p = false;
1933         for (i = 0; i < static_id->n_operands; i++)
1934           if (GET_CODE (*id->operand_loc[i]) == SCRATCH
1935               && GET_MODE (*id->operand_loc[i]) != VOIDmode)
1936             {
1937               insn_changed_p = true;
1938               *id->operand_loc[i] = reg
1939                 = lra_create_new_reg (static_id->operand[i].mode,
1940                                       *id->operand_loc[i], ALL_REGS, NULL);
1941               add_reg_note (insn, REG_UNUSED, reg);
1942               lra_update_dup (id, i);
1943               loc = XNEW (struct sloc);
1944               loc->insn = insn;
1945               loc->nop = i;
1946               scratches.safe_push (loc);
1947               bitmap_set_bit (&scratch_bitmap, REGNO (*id->operand_loc[i]));
1948               bitmap_set_bit (&scratch_operand_bitmap,
1949                               INSN_UID (insn) * MAX_RECOG_OPERANDS + i);
1950               if (lra_dump_file != NULL)
1951                 fprintf (lra_dump_file,
1952                          "Removing SCRATCH in insn #%u (nop %d)\n",
1953                          INSN_UID (insn), i);
1954             }
1955         if (insn_changed_p)
1956           /* Because we might use DF right after caller-saves sub-pass
1957              we need to keep DF info up to date.  */
1958           df_insn_rescan (insn);
1959       }
1960 }
1961
1962 /* Changes pseudos created by function remove_scratches onto scratches.  */
1963 static void
1964 restore_scratches (void)
1965 {
1966   int regno;
1967   unsigned i;
1968   sloc_t loc;
1969   rtx_insn *last = NULL;
1970   lra_insn_recog_data_t id = NULL;
1971
1972   for (i = 0; scratches.iterate (i, &loc); i++)
1973     {
1974       if (last != loc->insn)
1975         {
1976           last = loc->insn;
1977           id = lra_get_insn_recog_data (last);
1978         }
1979       if (REG_P (*id->operand_loc[loc->nop])
1980           && ((regno = REGNO (*id->operand_loc[loc->nop]))
1981               >= FIRST_PSEUDO_REGISTER)
1982           && lra_get_regno_hard_regno (regno) < 0)
1983         {
1984           /* It should be only case when scratch register with chosen
1985              constraint 'X' did not get memory or hard register.  */
1986           lra_assert (lra_former_scratch_p (regno));
1987           *id->operand_loc[loc->nop]
1988             = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
1989           lra_update_dup (id, loc->nop);
1990           if (lra_dump_file != NULL)
1991             fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
1992                      INSN_UID (loc->insn), loc->nop);
1993         }
1994     }
1995   for (i = 0; scratches.iterate (i, &loc); i++)
1996     free (loc);
1997   scratches.release ();
1998   bitmap_clear (&scratch_bitmap);
1999   bitmap_clear (&scratch_operand_bitmap);
2000 }
2001
2002 \f
2003
2004 #ifdef ENABLE_CHECKING
2005
2006 /* Function checks RTL for correctness.  If FINAL_P is true, it is
2007    done at the end of LRA and the check is more rigorous.  */
2008 static void
2009 check_rtl (bool final_p)
2010 {
2011   basic_block bb;
2012   rtx_insn *insn;
2013
2014   lra_assert (! final_p || reload_completed);
2015   FOR_EACH_BB_FN (bb, cfun)
2016     FOR_BB_INSNS (bb, insn)
2017     if (NONDEBUG_INSN_P (insn)
2018         && GET_CODE (PATTERN (insn)) != USE
2019         && GET_CODE (PATTERN (insn)) != CLOBBER
2020         && GET_CODE (PATTERN (insn)) != ASM_INPUT)
2021       {
2022         if (final_p)
2023           {
2024 #ifdef ENABLED_CHECKING
2025             extract_constrain_insn (insn);
2026 #endif
2027             continue;
2028           }
2029         /* LRA code is based on assumption that all addresses can be
2030            correctly decomposed.  LRA can generate reloads for
2031            decomposable addresses.  The decomposition code checks the
2032            correctness of the addresses.  So we don't need to check
2033            the addresses here.  Don't call insn_invalid_p here, it can
2034            change the code at this stage.  */
2035         if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
2036           fatal_insn_not_found (insn);
2037       }
2038 }
2039 #endif /* #ifdef ENABLE_CHECKING */
2040
2041 /* Determine if the current function has an exception receiver block
2042    that reaches the exit block via non-exceptional edges  */
2043 static bool
2044 has_nonexceptional_receiver (void)
2045 {
2046   edge e;
2047   edge_iterator ei;
2048   basic_block *tos, *worklist, bb;
2049
2050   /* If we're not optimizing, then just err on the safe side.  */
2051   if (!optimize)
2052     return true;
2053
2054   /* First determine which blocks can reach exit via normal paths.  */
2055   tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
2056
2057   FOR_EACH_BB_FN (bb, cfun)
2058     bb->flags &= ~BB_REACHABLE;
2059
2060   /* Place the exit block on our worklist.  */
2061   EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
2062   *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
2063
2064   /* Iterate: find everything reachable from what we've already seen.  */
2065   while (tos != worklist)
2066     {
2067       bb = *--tos;
2068
2069       FOR_EACH_EDGE (e, ei, bb->preds)
2070         if (e->flags & EDGE_ABNORMAL)
2071           {
2072             free (worklist);
2073             return true;
2074           }
2075         else
2076           {
2077             basic_block src = e->src;
2078
2079             if (!(src->flags & BB_REACHABLE))
2080               {
2081                 src->flags |= BB_REACHABLE;
2082                 *tos++ = src;
2083               }
2084           }
2085     }
2086   free (worklist);
2087   /* No exceptional block reached exit unexceptionally.  */
2088   return false;
2089 }
2090
2091 #ifdef AUTO_INC_DEC
2092
2093 /* Process recursively X of INSN and add REG_INC notes if necessary.  */
2094 static void
2095 add_auto_inc_notes (rtx_insn *insn, rtx x)
2096 {
2097   enum rtx_code code = GET_CODE (x);
2098   const char *fmt;
2099   int i, j;
2100
2101   if (code == MEM && auto_inc_p (XEXP (x, 0)))
2102     {
2103       add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
2104       return;
2105     }
2106
2107   /* Scan all X sub-expressions.  */
2108   fmt = GET_RTX_FORMAT (code);
2109   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2110     {
2111       if (fmt[i] == 'e')
2112         add_auto_inc_notes (insn, XEXP (x, i));
2113       else if (fmt[i] == 'E')
2114         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2115           add_auto_inc_notes (insn, XVECEXP (x, i, j));
2116     }
2117 }
2118
2119 #endif
2120
2121 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
2122    We change pseudos by hard registers without notification of DF and
2123    that can make the notes obsolete.  DF-infrastructure does not deal
2124    with REG_INC notes -- so we should regenerate them here.  */
2125 static void
2126 update_inc_notes (void)
2127 {
2128   rtx *pnote;
2129   basic_block bb;
2130   rtx_insn *insn;
2131
2132   FOR_EACH_BB_FN (bb, cfun)
2133     FOR_BB_INSNS (bb, insn)
2134     if (NONDEBUG_INSN_P (insn))
2135       {
2136         pnote = &REG_NOTES (insn);
2137         while (*pnote != 0)
2138           {
2139             if (REG_NOTE_KIND (*pnote) == REG_DEAD
2140                 || REG_NOTE_KIND (*pnote) == REG_UNUSED
2141                 || REG_NOTE_KIND (*pnote) == REG_INC)
2142               *pnote = XEXP (*pnote, 1);
2143             else
2144               pnote = &XEXP (*pnote, 1);
2145           }
2146 #ifdef AUTO_INC_DEC
2147         add_auto_inc_notes (insn, PATTERN (insn));
2148 #endif
2149       }
2150 }
2151
2152 /* Set to 1 while in lra.  */
2153 int lra_in_progress;
2154
2155 /* Start of pseudo regnos before the LRA.  */
2156 int lra_new_regno_start;
2157
2158 /* Start of reload pseudo regnos before the new spill pass.  */
2159 int lra_constraint_new_regno_start;
2160
2161 /* Inheritance pseudo regnos before the new spill pass.  */
2162 bitmap_head lra_inheritance_pseudos;
2163
2164 /* Split regnos before the new spill pass.  */
2165 bitmap_head lra_split_regs;
2166
2167 /* Reload pseudo regnos before the new assignmnet pass which still can
2168    be spilled after the assinment pass as memory is also accepted in
2169    insns for the reload pseudos.  */
2170 bitmap_head lra_optional_reload_pseudos;
2171
2172 /* Pseudo regnos used for subreg reloads before the new assignment
2173    pass.  Such pseudos still can be spilled after the assinment
2174    pass.  */
2175 bitmap_head lra_subreg_reload_pseudos;
2176
2177 /* File used for output of LRA debug information.  */
2178 FILE *lra_dump_file;
2179
2180 /* True if we should try spill into registers of different classes
2181    instead of memory.  */
2182 bool lra_reg_spill_p;
2183
2184 /* Set up value LRA_REG_SPILL_P.  */
2185 static void
2186 setup_reg_spill_flag (void)
2187 {
2188   int cl, mode;
2189
2190   if (targetm.spill_class != NULL)
2191     for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
2192       for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
2193         if (targetm.spill_class ((enum reg_class) cl,
2194                                  (machine_mode) mode) != NO_REGS)
2195           {
2196             lra_reg_spill_p = true;
2197             return;
2198           }
2199   lra_reg_spill_p = false;
2200 }
2201
2202 /* True if the current function is too big to use regular algorithms
2203    in LRA. In other words, we should use simpler and faster algorithms
2204    in LRA.  It also means we should not worry about generation code
2205    for caller saves.  The value is set up in IRA.  */
2206 bool lra_simple_p;
2207
2208 /* Major LRA entry function.  F is a file should be used to dump LRA
2209    debug info.  */
2210 void
2211 lra (FILE *f)
2212 {
2213   int i;
2214   bool live_p, scratch_p, inserted_p;
2215
2216   lra_dump_file = f;
2217
2218   timevar_push (TV_LRA);
2219
2220   /* Make sure that the last insn is a note.  Some subsequent passes
2221      need it.  */
2222   emit_note (NOTE_INSN_DELETED);
2223
2224   COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs);
2225
2226   init_reg_info ();
2227   expand_reg_info ();
2228
2229   init_insn_recog_data ();
2230
2231 #ifdef ENABLE_CHECKING
2232   /* Some quick check on RTL generated by previous passes.  */
2233   check_rtl (false);
2234 #endif
2235
2236   lra_in_progress = 1;
2237
2238   lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
2239   lra_assignment_iter = lra_assignment_iter_after_spill = 0;
2240   lra_inheritance_iter = lra_undo_inheritance_iter = 0;
2241
2242   setup_reg_spill_flag ();
2243
2244   /* Function remove_scratches can creates new pseudos for clobbers --
2245      so set up lra_constraint_new_regno_start before its call to
2246      permit changing reg classes for pseudos created by this
2247      simplification.  */
2248   lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
2249   remove_scratches ();
2250   scratch_p = lra_constraint_new_regno_start != max_reg_num ();
2251
2252   /* A function that has a non-local label that can reach the exit
2253      block via non-exceptional paths must save all call-saved
2254      registers.  */
2255   if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
2256     crtl->saves_all_registers = 1;
2257
2258   if (crtl->saves_all_registers)
2259     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2260       if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
2261         df_set_regs_ever_live (i, true);
2262
2263   /* We don't DF from now and avoid its using because it is to
2264      expensive when a lot of RTL changes are made.  */
2265   df_set_flags (DF_NO_INSN_RESCAN);
2266   lra_constraint_insn_stack.create (get_max_uid ());
2267   lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
2268   bitmap_clear (lra_constraint_insn_stack_bitmap);
2269   lra_live_ranges_init ();
2270   lra_constraints_init ();
2271   lra_curr_reload_num = 0;
2272   push_insns (get_last_insn (), NULL);
2273   /* It is needed for the 1st coalescing.  */
2274   bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
2275   bitmap_initialize (&lra_split_regs, &reg_obstack);
2276   bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
2277   bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
2278   live_p = false;
2279   if (get_frame_size () != 0 && crtl->stack_alignment_needed)
2280     /* If we have a stack frame, we must align it now.  The stack size
2281        may be a part of the offset computation for register
2282        elimination.  */
2283     assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
2284   lra_init_equiv ();
2285   for (;;)
2286     {
2287       for (;;)
2288         {
2289           /* We should try to assign hard registers to scratches even
2290              if there were no RTL transformations in
2291              lra_constraints.  */
2292           if (! lra_constraints (lra_constraint_iter == 0)
2293               && (lra_constraint_iter > 1
2294                   || (! scratch_p && ! caller_save_needed)))
2295             break;
2296           /* Constraint transformations may result in that eliminable
2297              hard regs become uneliminable and pseudos which use them
2298              should be spilled.  It is better to do it before pseudo
2299              assignments.
2300
2301              For example, rs6000 can make
2302              RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
2303              to use a constant pool.  */
2304           lra_eliminate (false, false);
2305           /* Do inheritance only for regular algorithms.  */
2306           if (! lra_simple_p)
2307             {
2308               if (flag_ipa_ra)
2309                 {
2310                   if (live_p)
2311                     lra_clear_live_ranges ();
2312                   /* As a side-effect of lra_create_live_ranges, we calculate
2313                      actual_call_used_reg_set,  which is needed during
2314                      lra_inheritance.  */
2315                   lra_create_live_ranges (true, true);
2316                   live_p = true;
2317                 }
2318               lra_inheritance ();
2319             }
2320           if (live_p)
2321             lra_clear_live_ranges ();
2322           /* We need live ranges for lra_assign -- so build them.  But
2323              don't remove dead insns or change global live info as we
2324              can undo inheritance transformations after inheritance
2325              pseudo assigning.  */
2326           lra_create_live_ranges (true, false);
2327           live_p = true;
2328           /* If we don't spill non-reload and non-inheritance pseudos,
2329              there is no sense to run memory-memory move coalescing.
2330              If inheritance pseudos were spilled, the memory-memory
2331              moves involving them will be removed by pass undoing
2332              inheritance.  */
2333           if (lra_simple_p)
2334             lra_assign ();
2335           else
2336             {
2337               bool spill_p = !lra_assign ();
2338
2339               if (lra_undo_inheritance ())
2340                 live_p = false;
2341               if (spill_p)
2342                 {
2343                   if (! live_p)
2344                     {
2345                       lra_create_live_ranges (true, true);
2346                       live_p = true;
2347                     }
2348                   if (lra_coalesce ())
2349                     live_p = false;
2350                 }
2351               if (! live_p)
2352                 lra_clear_live_ranges ();
2353             }
2354         }
2355       /* Don't clear optional reloads bitmap until all constraints are
2356          satisfied as we need to differ them from regular reloads.  */
2357       bitmap_clear (&lra_optional_reload_pseudos);
2358       bitmap_clear (&lra_subreg_reload_pseudos);
2359       bitmap_clear (&lra_inheritance_pseudos);
2360       bitmap_clear (&lra_split_regs);
2361       if (! live_p)
2362         {
2363           /* We need full live info for spilling pseudos into
2364              registers instead of memory.  */
2365           lra_create_live_ranges (lra_reg_spill_p, true);
2366           live_p = true;
2367         }
2368       /* We should check necessity for spilling here as the above live
2369          range pass can remove spilled pseudos.  */
2370       if (! lra_need_for_spills_p ())
2371         break;
2372       /* Now we know what pseudos should be spilled.  Try to
2373          rematerialize them first.  */
2374       if (lra_remat ())
2375         {
2376           /* We need full live info -- see the comment above.  */
2377           lra_create_live_ranges (lra_reg_spill_p, true);
2378           live_p = true;
2379           if (! lra_need_for_spills_p ())
2380             break;
2381         }
2382       lra_spill ();
2383       /* Assignment of stack slots changes elimination offsets for
2384          some eliminations.  So update the offsets here.  */
2385       lra_eliminate (false, false);
2386       lra_constraint_new_regno_start = max_reg_num ();
2387       lra_assignment_iter_after_spill = 0;
2388     }
2389   restore_scratches ();
2390   lra_eliminate (true, false);
2391   lra_final_code_change ();
2392   lra_in_progress = 0;
2393   if (live_p)
2394     lra_clear_live_ranges ();
2395   lra_live_ranges_finish ();
2396   lra_constraints_finish ();
2397   finish_reg_info ();
2398   sbitmap_free (lra_constraint_insn_stack_bitmap);
2399   lra_constraint_insn_stack.release ();
2400   finish_insn_recog_data ();
2401   regstat_free_n_sets_and_refs ();
2402   regstat_free_ri ();
2403   reload_completed = 1;
2404   update_inc_notes ();
2405
2406   inserted_p = fixup_abnormal_edges ();
2407
2408   /* We've possibly turned single trapping insn into multiple ones.  */
2409   if (cfun->can_throw_non_call_exceptions)
2410     {
2411       sbitmap blocks;
2412       blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
2413       bitmap_ones (blocks);
2414       find_many_sub_basic_blocks (blocks);
2415       sbitmap_free (blocks);
2416     }
2417
2418   if (inserted_p)
2419     commit_edge_insertions ();
2420
2421   /* Replacing pseudos with their memory equivalents might have
2422      created shared rtx.  Subsequent passes would get confused
2423      by this, so unshare everything here.  */
2424   unshare_all_rtl_again (get_insns ());
2425
2426 #ifdef ENABLE_CHECKING
2427   check_rtl (true);
2428 #endif
2429
2430   timevar_pop (TV_LRA);
2431 }
2432
2433 /* Called once per compiler to initialize LRA data once.  */
2434 void
2435 lra_init_once (void)
2436 {
2437   init_insn_code_data_once ();
2438 }
2439
2440 /* Called once per compiler to finish LRA data which are initialize
2441    once.  */
2442 void
2443 lra_finish_once (void)
2444 {
2445   finish_insn_code_data_once ();
2446 }