Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / lra-constraints.c
1 /* Code for RTL transformations to satisfy insn constraints.
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 /* This file contains code for 3 passes: constraint pass,
23    inheritance/split pass, and pass for undoing failed inheritance and
24    split.
25
26    The major goal of constraint pass is to transform RTL to satisfy
27    insn and address constraints by:
28      o choosing insn alternatives;
29      o generating *reload insns* (or reloads in brief) and *reload
30        pseudos* which will get necessary hard registers later;
31      o substituting pseudos with equivalent values and removing the
32        instructions that initialized those pseudos.
33
34    The constraint pass has biggest and most complicated code in LRA.
35    There are a lot of important details like:
36      o reuse of input reload pseudos to simplify reload pseudo
37        allocations;
38      o some heuristics to choose insn alternative to improve the
39        inheritance;
40      o early clobbers etc.
41
42    The pass is mimicking former reload pass in alternative choosing
43    because the reload pass is oriented to current machine description
44    model.  It might be changed if the machine description model is
45    changed.
46
47    There is special code for preventing all LRA and this pass cycling
48    in case of bugs.
49
50    On the first iteration of the pass we process every instruction and
51    choose an alternative for each one.  On subsequent iterations we try
52    to avoid reprocessing instructions if we can be sure that the old
53    choice is still valid.
54
55    The inheritance/spilt pass is to transform code to achieve
56    ineheritance and live range splitting.  It is done on backward
57    traversal of EBBs.
58
59    The inheritance optimization goal is to reuse values in hard
60    registers. There is analogous optimization in old reload pass.  The
61    inheritance is achieved by following transformation:
62
63        reload_p1 <- p        reload_p1 <- p
64        ...                   new_p <- reload_p1
65        ...              =>   ...
66        reload_p2 <- p        reload_p2 <- new_p
67
68    where p is spilled and not changed between the insns.  Reload_p1 is
69    also called *original pseudo* and new_p is called *inheritance
70    pseudo*.
71
72    The subsequent assignment pass will try to assign the same (or
73    another if it is not possible) hard register to new_p as to
74    reload_p1 or reload_p2.
75
76    If the assignment pass fails to assign a hard register to new_p,
77    this file will undo the inheritance and restore the original code.
78    This is because implementing the above sequence with a spilled
79    new_p would make the code much worse.  The inheritance is done in
80    EBB scope.  The above is just a simplified example to get an idea
81    of the inheritance as the inheritance is also done for non-reload
82    insns.
83
84    Splitting (transformation) is also done in EBB scope on the same
85    pass as the inheritance:
86
87        r <- ... or ... <- r              r <- ... or ... <- r
88        ...                               s <- r (new insn -- save)
89        ...                        =>
90        ...                               r <- s (new insn -- restore)
91        ... <- r                          ... <- r
92
93     The *split pseudo* s is assigned to the hard register of the
94     original pseudo or hard register r.
95
96     Splitting is done:
97       o In EBBs with high register pressure for global pseudos (living
98         in at least 2 BBs) and assigned to hard registers when there
99         are more one reloads needing the hard registers;
100       o for pseudos needing save/restore code around calls.
101
102     If the split pseudo still has the same hard register as the
103     original pseudo after the subsequent assignment pass or the
104     original pseudo was split, the opposite transformation is done on
105     the same pass for undoing inheritance.  */
106
107 #undef REG_OK_STRICT
108
109 #include "config.h"
110 #include "system.h"
111 #include "coretypes.h"
112 #include "tm.h"
113 #include "hard-reg-set.h"
114 #include "rtl.h"
115 #include "tm_p.h"
116 #include "regs.h"
117 #include "insn-config.h"
118 #include "insn-codes.h"
119 #include "recog.h"
120 #include "output.h"
121 #include "addresses.h"
122 #include "target.h"
123 #include "hashtab.h"
124 #include "hash-set.h"
125 #include "vec.h"
126 #include "machmode.h"
127 #include "input.h"
128 #include "function.h"
129 #include "symtab.h"
130 #include "flags.h"
131 #include "statistics.h"
132 #include "double-int.h"
133 #include "real.h"
134 #include "fixed-value.h"
135 #include "alias.h"
136 #include "wide-int.h"
137 #include "inchash.h"
138 #include "tree.h"
139 #include "expmed.h"
140 #include "dojump.h"
141 #include "explow.h"
142 #include "calls.h"
143 #include "emit-rtl.h"
144 #include "varasm.h"
145 #include "stmt.h"
146 #include "expr.h"
147 #include "predict.h"
148 #include "dominance.h"
149 #include "cfg.h"
150 #include "cfgrtl.h"
151 #include "basic-block.h"
152 #include "except.h"
153 #include "optabs.h"
154 #include "df.h"
155 #include "ira.h"
156 #include "rtl-error.h"
157 #include "lra-int.h"
158
159 /* Value of LRA_CURR_RELOAD_NUM at the beginning of BB of the current
160    insn.  Remember that LRA_CURR_RELOAD_NUM is the number of emitted
161    reload insns.  */
162 static int bb_reload_num;
163
164 /* The current insn being processed and corresponding its single set
165    (NULL otherwise), its data (basic block, the insn data, the insn
166    static data, and the mode of each operand).  */
167 static rtx_insn *curr_insn;
168 static rtx curr_insn_set;
169 static basic_block curr_bb;
170 static lra_insn_recog_data_t curr_id;
171 static struct lra_static_insn_data *curr_static_id;
172 static machine_mode curr_operand_mode[MAX_RECOG_OPERANDS];
173 /* Mode of the register substituted by its equivalence with VOIDmode
174    (e.g. constant) and whose subreg is given operand of the current
175    insn.  VOIDmode in all other cases.  */
176 static machine_mode original_subreg_reg_mode[MAX_RECOG_OPERANDS];
177
178 \f
179
180 /* Start numbers for new registers and insns at the current constraints
181    pass start.  */
182 static int new_regno_start;
183 static int new_insn_uid_start;
184
185 /* If LOC is nonnull, strip any outer subreg from it.  */
186 static inline rtx *
187 strip_subreg (rtx *loc)
188 {
189   return loc && GET_CODE (*loc) == SUBREG ? &SUBREG_REG (*loc) : loc;
190 }
191
192 /* Return hard regno of REGNO or if it is was not assigned to a hard
193    register, use a hard register from its allocno class.  */
194 static int
195 get_try_hard_regno (int regno)
196 {
197   int hard_regno;
198   enum reg_class rclass;
199
200   if ((hard_regno = regno) >= FIRST_PSEUDO_REGISTER)
201     hard_regno = lra_get_regno_hard_regno (regno);
202   if (hard_regno >= 0)
203     return hard_regno;
204   rclass = lra_get_allocno_class (regno);
205   if (rclass == NO_REGS)
206     return -1;
207   return ira_class_hard_regs[rclass][0];
208 }
209
210 /* Return final hard regno (plus offset) which will be after
211    elimination.  We do this for matching constraints because the final
212    hard regno could have a different class.  */
213 static int
214 get_final_hard_regno (int hard_regno, int offset)
215 {
216   if (hard_regno < 0)
217     return hard_regno;
218   hard_regno = lra_get_elimination_hard_regno (hard_regno);
219   return hard_regno + offset;
220 }
221
222 /* Return hard regno of X after removing subreg and making
223    elimination.  If X is not a register or subreg of register, return
224    -1.  For pseudo use its assignment.  */
225 static int
226 get_hard_regno (rtx x)
227 {
228   rtx reg;
229   int offset, hard_regno;
230
231   reg = x;
232   if (GET_CODE (x) == SUBREG)
233     reg = SUBREG_REG (x);
234   if (! REG_P (reg))
235     return -1;
236   if ((hard_regno = REGNO (reg)) >= FIRST_PSEUDO_REGISTER)
237     hard_regno = lra_get_regno_hard_regno (hard_regno);
238   if (hard_regno < 0)
239     return -1;
240   offset = 0;
241   if (GET_CODE (x) == SUBREG)
242     offset += subreg_regno_offset (hard_regno, GET_MODE (reg),
243                                    SUBREG_BYTE (x),  GET_MODE (x));
244   return get_final_hard_regno (hard_regno, offset);
245 }
246
247 /* If REGNO is a hard register or has been allocated a hard register,
248    return the class of that register.  If REGNO is a reload pseudo
249    created by the current constraints pass, return its allocno class.
250    Return NO_REGS otherwise.  */
251 static enum reg_class
252 get_reg_class (int regno)
253 {
254   int hard_regno;
255
256   if ((hard_regno = regno) >= FIRST_PSEUDO_REGISTER)
257     hard_regno = lra_get_regno_hard_regno (regno);
258   if (hard_regno >= 0)
259     {
260       hard_regno = get_final_hard_regno (hard_regno, 0);
261       return REGNO_REG_CLASS (hard_regno);
262     }
263   if (regno >= new_regno_start)
264     return lra_get_allocno_class (regno);
265   return NO_REGS;
266 }
267
268 /* Return true if REG satisfies (or will satisfy) reg class constraint
269    CL.  Use elimination first if REG is a hard register.  If REG is a
270    reload pseudo created by this constraints pass, assume that it will
271    be allocated a hard register from its allocno class, but allow that
272    class to be narrowed to CL if it is currently a superset of CL.
273
274    If NEW_CLASS is nonnull, set *NEW_CLASS to the new allocno class of
275    REGNO (reg), or NO_REGS if no change in its class was needed.  */
276 static bool
277 in_class_p (rtx reg, enum reg_class cl, enum reg_class *new_class)
278 {
279   enum reg_class rclass, common_class;
280   machine_mode reg_mode;
281   int class_size, hard_regno, nregs, i, j;
282   int regno = REGNO (reg);
283
284   if (new_class != NULL)
285     *new_class = NO_REGS;
286   if (regno < FIRST_PSEUDO_REGISTER)
287     {
288       rtx final_reg = reg;
289       rtx *final_loc = &final_reg;
290
291       lra_eliminate_reg_if_possible (final_loc);
292       return TEST_HARD_REG_BIT (reg_class_contents[cl], REGNO (*final_loc));
293     }
294   reg_mode = GET_MODE (reg);
295   rclass = get_reg_class (regno);
296   if (regno < new_regno_start
297       /* Do not allow the constraints for reload instructions to
298          influence the classes of new pseudos.  These reloads are
299          typically moves that have many alternatives, and restricting
300          reload pseudos for one alternative may lead to situations
301          where other reload pseudos are no longer allocatable.  */
302       || (INSN_UID (curr_insn) >= new_insn_uid_start
303           && curr_insn_set != NULL
304           && ((OBJECT_P (SET_SRC (curr_insn_set))
305                && ! CONSTANT_P (SET_SRC (curr_insn_set)))
306               || (GET_CODE (SET_SRC (curr_insn_set)) == SUBREG
307                   && OBJECT_P (SUBREG_REG (SET_SRC (curr_insn_set)))
308                   && ! CONSTANT_P (SUBREG_REG (SET_SRC (curr_insn_set)))))))
309     /* When we don't know what class will be used finally for reload
310        pseudos, we use ALL_REGS.  */
311     return ((regno >= new_regno_start && rclass == ALL_REGS)
312             || (rclass != NO_REGS && ira_class_subset_p[rclass][cl]
313                 && ! hard_reg_set_subset_p (reg_class_contents[cl],
314                                             lra_no_alloc_regs)));
315   else
316     {
317       common_class = ira_reg_class_subset[rclass][cl];
318       if (new_class != NULL)
319         *new_class = common_class;
320       if (hard_reg_set_subset_p (reg_class_contents[common_class],
321                                  lra_no_alloc_regs))
322         return false;
323       /* Check that there are enough allocatable regs.  */
324       class_size = ira_class_hard_regs_num[common_class];
325       for (i = 0; i < class_size; i++)
326         {
327           hard_regno = ira_class_hard_regs[common_class][i];
328           nregs = hard_regno_nregs[hard_regno][reg_mode];
329           if (nregs == 1)
330             return true;
331           for (j = 0; j < nregs; j++)
332             if (TEST_HARD_REG_BIT (lra_no_alloc_regs, hard_regno + j)
333                 || ! TEST_HARD_REG_BIT (reg_class_contents[common_class],
334                                         hard_regno + j))
335               break;
336           if (j >= nregs)
337             return true;
338         }
339       return false;
340     }
341 }
342
343 /* Return true if REGNO satisfies a memory constraint.  */
344 static bool
345 in_mem_p (int regno)
346 {
347   return get_reg_class (regno) == NO_REGS;
348 }
349
350 /* Return 1 if ADDR is a valid memory address for mode MODE in address
351    space AS, and check that each pseudo has the proper kind of hard
352    reg.  */
353 static int
354 valid_address_p (machine_mode mode ATTRIBUTE_UNUSED,
355                  rtx addr, addr_space_t as)
356 {
357 #ifdef GO_IF_LEGITIMATE_ADDRESS
358   lra_assert (ADDR_SPACE_GENERIC_P (as));
359   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
360   return 0;
361
362  win:
363   return 1;
364 #else
365   return targetm.addr_space.legitimate_address_p (mode, addr, 0, as);
366 #endif
367 }
368
369 namespace {
370   /* Temporarily eliminates registers in an address (for the lifetime of
371      the object).  */
372   class address_eliminator {
373   public:
374     address_eliminator (struct address_info *ad);
375     ~address_eliminator ();
376
377   private:
378     struct address_info *m_ad;
379     rtx *m_base_loc;
380     rtx m_base_reg;
381     rtx *m_index_loc;
382     rtx m_index_reg;
383   };
384 }
385
386 address_eliminator::address_eliminator (struct address_info *ad)
387   : m_ad (ad),
388     m_base_loc (strip_subreg (ad->base_term)),
389     m_base_reg (NULL_RTX),
390     m_index_loc (strip_subreg (ad->index_term)),
391     m_index_reg (NULL_RTX)
392 {
393   if (m_base_loc != NULL)
394     {
395       m_base_reg = *m_base_loc;
396       lra_eliminate_reg_if_possible (m_base_loc);
397       if (m_ad->base_term2 != NULL)
398         *m_ad->base_term2 = *m_ad->base_term;
399     }
400   if (m_index_loc != NULL)
401     {
402       m_index_reg = *m_index_loc;
403       lra_eliminate_reg_if_possible (m_index_loc);
404     }
405 }
406
407 address_eliminator::~address_eliminator ()
408 {
409   if (m_base_loc && *m_base_loc != m_base_reg)
410     {
411       *m_base_loc = m_base_reg;
412       if (m_ad->base_term2 != NULL)
413         *m_ad->base_term2 = *m_ad->base_term;
414     }
415   if (m_index_loc && *m_index_loc != m_index_reg)
416     *m_index_loc = m_index_reg;
417 }
418
419 /* Return true if the eliminated form of AD is a legitimate target address.  */
420 static bool
421 valid_address_p (struct address_info *ad)
422 {
423   address_eliminator eliminator (ad);
424   return valid_address_p (ad->mode, *ad->outer, ad->as);
425 }
426
427 /* Return true if the eliminated form of memory reference OP satisfies
428    extra memory constraint CONSTRAINT.  */
429 static bool
430 satisfies_memory_constraint_p (rtx op, enum constraint_num constraint)
431 {
432   struct address_info ad;
433
434   decompose_mem_address (&ad, op);
435   address_eliminator eliminator (&ad);
436   return constraint_satisfied_p (op, constraint);
437 }
438
439 /* Return true if the eliminated form of address AD satisfies extra
440    address constraint CONSTRAINT.  */
441 static bool
442 satisfies_address_constraint_p (struct address_info *ad,
443                                 enum constraint_num constraint)
444 {
445   address_eliminator eliminator (ad);
446   return constraint_satisfied_p (*ad->outer, constraint);
447 }
448
449 /* Return true if the eliminated form of address OP satisfies extra
450    address constraint CONSTRAINT.  */
451 static bool
452 satisfies_address_constraint_p (rtx op, enum constraint_num constraint)
453 {
454   struct address_info ad;
455
456   decompose_lea_address (&ad, &op);
457   return satisfies_address_constraint_p (&ad, constraint);
458 }
459
460 /* Initiate equivalences for LRA.  As we keep original equivalences
461    before any elimination, we need to make copies otherwise any change
462    in insns might change the equivalences.  */
463 void
464 lra_init_equiv (void)
465 {
466   ira_expand_reg_equiv ();
467   for (int i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
468     {
469       rtx res;
470
471       if ((res = ira_reg_equiv[i].memory) != NULL_RTX)
472         ira_reg_equiv[i].memory = copy_rtx (res);
473       if ((res = ira_reg_equiv[i].invariant) != NULL_RTX)
474         ira_reg_equiv[i].invariant = copy_rtx (res);
475     }
476 }
477
478 static rtx loc_equivalence_callback (rtx, const_rtx, void *);
479
480 /* Update equivalence for REGNO.  We need to this as the equivalence
481    might contain other pseudos which are changed by their
482    equivalences.  */
483 static void
484 update_equiv (int regno)
485 {
486   rtx x;
487   
488   if ((x = ira_reg_equiv[regno].memory) != NULL_RTX)
489     ira_reg_equiv[regno].memory
490       = simplify_replace_fn_rtx (x, NULL_RTX, loc_equivalence_callback,
491                                  NULL_RTX);
492   if ((x = ira_reg_equiv[regno].invariant) != NULL_RTX)
493     ira_reg_equiv[regno].invariant
494       = simplify_replace_fn_rtx (x, NULL_RTX, loc_equivalence_callback,
495                                  NULL_RTX);
496 }
497
498 /* If we have decided to substitute X with another value, return that
499    value, otherwise return X.  */
500 static rtx
501 get_equiv (rtx x)
502 {
503   int regno;
504   rtx res;
505
506   if (! REG_P (x) || (regno = REGNO (x)) < FIRST_PSEUDO_REGISTER
507       || ! ira_reg_equiv[regno].defined_p
508       || ! ira_reg_equiv[regno].profitable_p
509       || lra_get_regno_hard_regno (regno) >= 0)
510     return x;
511   if ((res = ira_reg_equiv[regno].memory) != NULL_RTX)
512     {
513       if (targetm.cannot_substitute_mem_equiv_p (res))
514         return x;
515       return res;
516     }
517   if ((res = ira_reg_equiv[regno].constant) != NULL_RTX)
518     return res;
519   if ((res = ira_reg_equiv[regno].invariant) != NULL_RTX)
520     return res;
521   gcc_unreachable ();
522 }
523
524 /* If we have decided to substitute X with the equivalent value,
525    return that value after elimination for INSN, otherwise return
526    X.  */
527 static rtx
528 get_equiv_with_elimination (rtx x, rtx_insn *insn)
529 {
530   rtx res = get_equiv (x);
531
532   if (x == res || CONSTANT_P (res))
533     return res;
534   return lra_eliminate_regs_1 (insn, res, GET_MODE (res),
535                                0, false, false, true);
536 }
537
538 /* Set up curr_operand_mode.  */
539 static void
540 init_curr_operand_mode (void)
541 {
542   int nop = curr_static_id->n_operands;
543   for (int i = 0; i < nop; i++)
544     {
545       machine_mode mode = GET_MODE (*curr_id->operand_loc[i]);
546       if (mode == VOIDmode)
547         {
548           /* The .md mode for address operands is the mode of the
549              addressed value rather than the mode of the address itself.  */
550           if (curr_id->icode >= 0 && curr_static_id->operand[i].is_address)
551             mode = Pmode;
552           else
553             mode = curr_static_id->operand[i].mode;
554         }
555       curr_operand_mode[i] = mode;
556     }
557 }
558
559 \f
560
561 /* The page contains code to reuse input reloads.  */
562
563 /* Structure describes input reload of the current insns.  */
564 struct input_reload
565 {
566   /* Reloaded value.  */
567   rtx input;
568   /* Reload pseudo used.  */
569   rtx reg;
570 };
571
572 /* The number of elements in the following array.  */
573 static int curr_insn_input_reloads_num;
574 /* Array containing info about input reloads.  It is used to find the
575    same input reload and reuse the reload pseudo in this case.  */
576 static struct input_reload curr_insn_input_reloads[LRA_MAX_INSN_RELOADS];
577
578 /* Initiate data concerning reuse of input reloads for the current
579    insn.  */
580 static void
581 init_curr_insn_input_reloads (void)
582 {
583   curr_insn_input_reloads_num = 0;
584 }
585
586 /* Create a new pseudo using MODE, RCLASS, ORIGINAL or reuse already
587    created input reload pseudo (only if TYPE is not OP_OUT).  Don't
588    reuse pseudo if IN_SUBREG_P is true and the reused pseudo should be
589    wrapped up in SUBREG.  The result pseudo is returned through
590    RESULT_REG.  Return TRUE if we created a new pseudo, FALSE if we
591    reused the already created input reload pseudo.  Use TITLE to
592    describe new registers for debug purposes.  */
593 static bool
594 get_reload_reg (enum op_type type, machine_mode mode, rtx original,
595                 enum reg_class rclass, bool in_subreg_p,
596                 const char *title, rtx *result_reg)
597 {
598   int i, regno;
599   enum reg_class new_class;
600
601   if (type == OP_OUT)
602     {
603       *result_reg
604         = lra_create_new_reg_with_unique_value (mode, original, rclass, title);
605       return true;
606     }
607   /* Prevent reuse value of expression with side effects,
608      e.g. volatile memory.  */
609   if (! side_effects_p (original))
610     for (i = 0; i < curr_insn_input_reloads_num; i++)
611       if (rtx_equal_p (curr_insn_input_reloads[i].input, original)
612           && in_class_p (curr_insn_input_reloads[i].reg, rclass, &new_class))
613         {
614           rtx reg = curr_insn_input_reloads[i].reg;
615           regno = REGNO (reg);
616           /* If input is equal to original and both are VOIDmode,
617              GET_MODE (reg) might be still different from mode.
618              Ensure we don't return *result_reg with wrong mode.  */
619           if (GET_MODE (reg) != mode)
620             {
621               if (in_subreg_p)
622                 continue;
623               if (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (mode))
624                 continue;
625               reg = lowpart_subreg (mode, reg, GET_MODE (reg));
626               if (reg == NULL_RTX || GET_CODE (reg) != SUBREG)
627                 continue;
628             }
629           *result_reg = reg;
630           if (lra_dump_file != NULL)
631             {
632               fprintf (lra_dump_file, "  Reuse r%d for reload ", regno);
633               dump_value_slim (lra_dump_file, original, 1);
634             }
635           if (new_class != lra_get_allocno_class (regno))
636             lra_change_class (regno, new_class, ", change to", false);
637           if (lra_dump_file != NULL)
638             fprintf (lra_dump_file, "\n");
639           return false;
640         }
641   *result_reg = lra_create_new_reg (mode, original, rclass, title);
642   lra_assert (curr_insn_input_reloads_num < LRA_MAX_INSN_RELOADS);
643   curr_insn_input_reloads[curr_insn_input_reloads_num].input = original;
644   curr_insn_input_reloads[curr_insn_input_reloads_num++].reg = *result_reg;
645   return true;
646 }
647
648 \f
649
650 /* The page contains code to extract memory address parts.  */
651
652 /* Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudos.  */
653 static inline bool
654 ok_for_index_p_nonstrict (rtx reg)
655 {
656   unsigned regno = REGNO (reg);
657
658   return regno >= FIRST_PSEUDO_REGISTER || REGNO_OK_FOR_INDEX_P (regno);
659 }
660
661 /* A version of regno_ok_for_base_p for use here, when all pseudos
662    should count as OK.  Arguments as for regno_ok_for_base_p.  */
663 static inline bool
664 ok_for_base_p_nonstrict (rtx reg, machine_mode mode, addr_space_t as,
665                          enum rtx_code outer_code, enum rtx_code index_code)
666 {
667   unsigned regno = REGNO (reg);
668
669   if (regno >= FIRST_PSEUDO_REGISTER)
670     return true;
671   return ok_for_base_p_1 (regno, mode, as, outer_code, index_code);
672 }
673
674 \f
675
676 /* The page contains major code to choose the current insn alternative
677    and generate reloads for it.  */
678
679 /* Return the offset from REGNO of the least significant register
680    in (reg:MODE REGNO).
681
682    This function is used to tell whether two registers satisfy
683    a matching constraint.  (reg:MODE1 REGNO1) matches (reg:MODE2 REGNO2) if:
684
685          REGNO1 + lra_constraint_offset (REGNO1, MODE1)
686          == REGNO2 + lra_constraint_offset (REGNO2, MODE2)  */
687 int
688 lra_constraint_offset (int regno, machine_mode mode)
689 {
690   lra_assert (regno < FIRST_PSEUDO_REGISTER);
691   if (WORDS_BIG_ENDIAN && GET_MODE_SIZE (mode) > UNITS_PER_WORD
692       && SCALAR_INT_MODE_P (mode))
693     return hard_regno_nregs[regno][mode] - 1;
694   return 0;
695 }
696
697 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
698    if they are the same hard reg, and has special hacks for
699    auto-increment and auto-decrement.  This is specifically intended for
700    process_alt_operands to use in determining whether two operands
701    match.  X is the operand whose number is the lower of the two.
702
703    It is supposed that X is the output operand and Y is the input
704    operand.  Y_HARD_REGNO is the final hard regno of register Y or
705    register in subreg Y as we know it now.  Otherwise, it is a
706    negative value.  */
707 static bool
708 operands_match_p (rtx x, rtx y, int y_hard_regno)
709 {
710   int i;
711   RTX_CODE code = GET_CODE (x);
712   const char *fmt;
713
714   if (x == y)
715     return true;
716   if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
717       && (REG_P (y) || (GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y)))))
718     {
719       int j;
720
721       i = get_hard_regno (x);
722       if (i < 0)
723         goto slow;
724
725       if ((j = y_hard_regno) < 0)
726         goto slow;
727
728       i += lra_constraint_offset (i, GET_MODE (x));
729       j += lra_constraint_offset (j, GET_MODE (y));
730
731       return i == j;
732     }
733
734   /* If two operands must match, because they are really a single
735      operand of an assembler insn, then two post-increments are invalid
736      because the assembler insn would increment only once.  On the
737      other hand, a post-increment matches ordinary indexing if the
738      post-increment is the output operand.  */
739   if (code == POST_DEC || code == POST_INC || code == POST_MODIFY)
740     return operands_match_p (XEXP (x, 0), y, y_hard_regno);
741
742   /* Two pre-increments are invalid because the assembler insn would
743      increment only once.  On the other hand, a pre-increment matches
744      ordinary indexing if the pre-increment is the input operand.  */
745   if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC
746       || GET_CODE (y) == PRE_MODIFY)
747     return operands_match_p (x, XEXP (y, 0), -1);
748
749  slow:
750
751   if (code == REG && GET_CODE (y) == SUBREG && REG_P (SUBREG_REG (y))
752       && x == SUBREG_REG (y))
753     return true;
754   if (GET_CODE (y) == REG && code == SUBREG && REG_P (SUBREG_REG (x))
755       && SUBREG_REG (x) == y)
756     return true;
757
758   /* Now we have disposed of all the cases in which different rtx
759      codes can match.  */
760   if (code != GET_CODE (y))
761     return false;
762
763   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
764   if (GET_MODE (x) != GET_MODE (y))
765     return false;
766
767   switch (code)
768     {
769     CASE_CONST_UNIQUE:
770       return false;
771
772     case LABEL_REF:
773       return LABEL_REF_LABEL (x) == LABEL_REF_LABEL (y);
774     case SYMBOL_REF:
775       return XSTR (x, 0) == XSTR (y, 0);
776
777     default:
778       break;
779     }
780
781   /* Compare the elements.  If any pair of corresponding elements fail
782      to match, return false for the whole things.  */
783
784   fmt = GET_RTX_FORMAT (code);
785   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
786     {
787       int val, j;
788       switch (fmt[i])
789         {
790         case 'w':
791           if (XWINT (x, i) != XWINT (y, i))
792             return false;
793           break;
794
795         case 'i':
796           if (XINT (x, i) != XINT (y, i))
797             return false;
798           break;
799
800         case 'e':
801           val = operands_match_p (XEXP (x, i), XEXP (y, i), -1);
802           if (val == 0)
803             return false;
804           break;
805
806         case '0':
807           break;
808
809         case 'E':
810           if (XVECLEN (x, i) != XVECLEN (y, i))
811             return false;
812           for (j = XVECLEN (x, i) - 1; j >= 0; --j)
813             {
814               val = operands_match_p (XVECEXP (x, i, j), XVECEXP (y, i, j), -1);
815               if (val == 0)
816                 return false;
817             }
818           break;
819
820           /* It is believed that rtx's at this level will never
821              contain anything but integers and other rtx's, except for
822              within LABEL_REFs and SYMBOL_REFs.  */
823         default:
824           gcc_unreachable ();
825         }
826     }
827   return true;
828 }
829
830 /* True if X is a constant that can be forced into the constant pool.
831    MODE is the mode of the operand, or VOIDmode if not known.  */
832 #define CONST_POOL_OK_P(MODE, X)                \
833   ((MODE) != VOIDmode                           \
834    && CONSTANT_P (X)                            \
835    && GET_CODE (X) != HIGH                      \
836    && !targetm.cannot_force_const_mem (MODE, X))
837
838 /* True if C is a non-empty register class that has too few registers
839    to be safely used as a reload target class.  */
840 #define SMALL_REGISTER_CLASS_P(C)               \
841   (ira_class_hard_regs_num [(C)] == 1           \
842    || (ira_class_hard_regs_num [(C)] >= 1       \
843        && targetm.class_likely_spilled_p (C)))
844
845 /* If REG is a reload pseudo, try to make its class satisfying CL.  */
846 static void
847 narrow_reload_pseudo_class (rtx reg, enum reg_class cl)
848 {
849   enum reg_class rclass;
850
851   /* Do not make more accurate class from reloads generated.  They are
852      mostly moves with a lot of constraints.  Making more accurate
853      class may results in very narrow class and impossibility of find
854      registers for several reloads of one insn.  */
855   if (INSN_UID (curr_insn) >= new_insn_uid_start)
856     return;
857   if (GET_CODE (reg) == SUBREG)
858     reg = SUBREG_REG (reg);
859   if (! REG_P (reg) || (int) REGNO (reg) < new_regno_start)
860     return;
861   if (in_class_p (reg, cl, &rclass) && rclass != cl)
862     lra_change_class (REGNO (reg), rclass, "      Change to", true);
863 }
864
865 /* Generate reloads for matching OUT and INS (array of input operand
866    numbers with end marker -1) with reg class GOAL_CLASS.  Add input
867    and output reloads correspondingly to the lists *BEFORE and *AFTER.
868    OUT might be negative.  In this case we generate input reloads for
869    matched input operands INS.  */
870 static void
871 match_reload (signed char out, signed char *ins, enum reg_class goal_class,
872               rtx_insn **before, rtx_insn **after)
873 {
874   int i, in;
875   rtx new_in_reg, new_out_reg, reg, clobber;
876   machine_mode inmode, outmode;
877   rtx in_rtx = *curr_id->operand_loc[ins[0]];
878   rtx out_rtx = out < 0 ? in_rtx : *curr_id->operand_loc[out];
879
880   inmode = curr_operand_mode[ins[0]];
881   outmode = out < 0 ? inmode : curr_operand_mode[out];
882   push_to_sequence (*before);
883   if (inmode != outmode)
884     {
885       if (GET_MODE_SIZE (inmode) > GET_MODE_SIZE (outmode))
886         {
887           reg = new_in_reg
888             = lra_create_new_reg_with_unique_value (inmode, in_rtx,
889                                                     goal_class, "");
890           if (SCALAR_INT_MODE_P (inmode))
891             new_out_reg = gen_lowpart_SUBREG (outmode, reg);
892           else
893             new_out_reg = gen_rtx_SUBREG (outmode, reg, 0);
894           LRA_SUBREG_P (new_out_reg) = 1;
895           /* If the input reg is dying here, we can use the same hard
896              register for REG and IN_RTX.  We do it only for original
897              pseudos as reload pseudos can die although original
898              pseudos still live where reload pseudos dies.  */
899           if (REG_P (in_rtx) && (int) REGNO (in_rtx) < lra_new_regno_start
900               && find_regno_note (curr_insn, REG_DEAD, REGNO (in_rtx)))
901             lra_assign_reg_val (REGNO (in_rtx), REGNO (reg));
902         }
903       else
904         {
905           reg = new_out_reg
906             = lra_create_new_reg_with_unique_value (outmode, out_rtx,
907                                                     goal_class, "");
908           if (SCALAR_INT_MODE_P (outmode))
909             new_in_reg = gen_lowpart_SUBREG (inmode, reg);
910           else
911             new_in_reg = gen_rtx_SUBREG (inmode, reg, 0);
912           /* NEW_IN_REG is non-paradoxical subreg.  We don't want
913              NEW_OUT_REG living above.  We add clobber clause for
914              this.  This is just a temporary clobber.  We can remove
915              it at the end of LRA work.  */
916           clobber = emit_clobber (new_out_reg);
917           LRA_TEMP_CLOBBER_P (PATTERN (clobber)) = 1;
918           LRA_SUBREG_P (new_in_reg) = 1;
919           if (GET_CODE (in_rtx) == SUBREG)
920             {
921               rtx subreg_reg = SUBREG_REG (in_rtx);
922               
923               /* If SUBREG_REG is dying here and sub-registers IN_RTX
924                  and NEW_IN_REG are similar, we can use the same hard
925                  register for REG and SUBREG_REG.  */
926               if (REG_P (subreg_reg)
927                   && (int) REGNO (subreg_reg) < lra_new_regno_start
928                   && GET_MODE (subreg_reg) == outmode
929                   && SUBREG_BYTE (in_rtx) == SUBREG_BYTE (new_in_reg)
930                   && find_regno_note (curr_insn, REG_DEAD, REGNO (subreg_reg)))
931                 lra_assign_reg_val (REGNO (subreg_reg), REGNO (reg));
932             }
933         }
934     }
935   else
936     {
937       /* Pseudos have values -- see comments for lra_reg_info.
938          Different pseudos with the same value do not conflict even if
939          they live in the same place.  When we create a pseudo we
940          assign value of original pseudo (if any) from which we
941          created the new pseudo.  If we create the pseudo from the
942          input pseudo, the new pseudo will no conflict with the input
943          pseudo which is wrong when the input pseudo lives after the
944          insn and as the new pseudo value is changed by the insn
945          output.  Therefore we create the new pseudo from the output.
946
947          We cannot reuse the current output register because we might
948          have a situation like "a <- a op b", where the constraints
949          force the second input operand ("b") to match the output
950          operand ("a").  "b" must then be copied into a new register
951          so that it doesn't clobber the current value of "a".  */
952
953       new_in_reg = new_out_reg
954         = lra_create_new_reg_with_unique_value (outmode, out_rtx,
955                                                 goal_class, "");
956     }
957   /* In operand can be got from transformations before processing insn
958      constraints.  One example of such transformations is subreg
959      reloading (see function simplify_operand_subreg).  The new
960      pseudos created by the transformations might have inaccurate
961      class (ALL_REGS) and we should make their classes more
962      accurate.  */
963   narrow_reload_pseudo_class (in_rtx, goal_class);
964   lra_emit_move (copy_rtx (new_in_reg), in_rtx);
965   *before = get_insns ();
966   end_sequence ();
967   for (i = 0; (in = ins[i]) >= 0; i++)
968     {
969       lra_assert
970         (GET_MODE (*curr_id->operand_loc[in]) == VOIDmode
971          || GET_MODE (new_in_reg) == GET_MODE (*curr_id->operand_loc[in]));
972       *curr_id->operand_loc[in] = new_in_reg;
973     }
974   lra_update_dups (curr_id, ins);
975   if (out < 0)
976     return;
977   /* See a comment for the input operand above.  */
978   narrow_reload_pseudo_class (out_rtx, goal_class);
979   if (find_reg_note (curr_insn, REG_UNUSED, out_rtx) == NULL_RTX)
980     {
981       start_sequence ();
982       lra_emit_move (out_rtx, copy_rtx (new_out_reg));
983       emit_insn (*after);
984       *after = get_insns ();
985       end_sequence ();
986     }
987   *curr_id->operand_loc[out] = new_out_reg;
988   lra_update_dup (curr_id, out);
989 }
990
991 /* Return register class which is union of all reg classes in insn
992    constraint alternative string starting with P.  */
993 static enum reg_class
994 reg_class_from_constraints (const char *p)
995 {
996   int c, len;
997   enum reg_class op_class = NO_REGS;
998
999   do
1000     switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
1001       {
1002       case '#':
1003       case ',':
1004         return op_class;
1005
1006       case 'g':
1007         op_class = reg_class_subunion[op_class][GENERAL_REGS];
1008         break;
1009
1010       default:
1011         enum constraint_num cn = lookup_constraint (p);
1012         enum reg_class cl = reg_class_for_constraint (cn);
1013         if (cl == NO_REGS)
1014           {
1015             if (insn_extra_address_constraint (cn))
1016               op_class
1017                 = (reg_class_subunion
1018                    [op_class][base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
1019                                               ADDRESS, SCRATCH)]);
1020             break;
1021           }
1022
1023         op_class = reg_class_subunion[op_class][cl];
1024         break;
1025       }
1026   while ((p += len), c);
1027   return op_class;
1028 }
1029
1030 /* If OP is a register, return the class of the register as per
1031    get_reg_class, otherwise return NO_REGS.  */
1032 static inline enum reg_class
1033 get_op_class (rtx op)
1034 {
1035   return REG_P (op) ? get_reg_class (REGNO (op)) : NO_REGS;
1036 }
1037
1038 /* Return generated insn mem_pseudo:=val if TO_P or val:=mem_pseudo
1039    otherwise.  If modes of MEM_PSEUDO and VAL are different, use
1040    SUBREG for VAL to make them equal.  */
1041 static rtx_insn *
1042 emit_spill_move (bool to_p, rtx mem_pseudo, rtx val)
1043 {
1044   if (GET_MODE (mem_pseudo) != GET_MODE (val))
1045     {
1046       /* Usually size of mem_pseudo is greater than val size but in
1047          rare cases it can be less as it can be defined by target
1048          dependent macro HARD_REGNO_CALLER_SAVE_MODE.  */
1049       if (! MEM_P (val))
1050         {
1051           val = gen_rtx_SUBREG (GET_MODE (mem_pseudo),
1052                                 GET_CODE (val) == SUBREG ? SUBREG_REG (val) : val,
1053                                 0);
1054           LRA_SUBREG_P (val) = 1;
1055         }
1056       else
1057         {
1058           mem_pseudo = gen_lowpart_SUBREG (GET_MODE (val), mem_pseudo);
1059           LRA_SUBREG_P (mem_pseudo) = 1;
1060         }
1061     }
1062   return as_a <rtx_insn *> (to_p
1063                             ? gen_move_insn (mem_pseudo, val)
1064                             : gen_move_insn (val, mem_pseudo));
1065 }
1066
1067 /* Process a special case insn (register move), return true if we
1068    don't need to process it anymore.  INSN should be a single set
1069    insn.  Set up that RTL was changed through CHANGE_P and macro
1070    SECONDARY_MEMORY_NEEDED says to use secondary memory through
1071    SEC_MEM_P.  */
1072 static bool
1073 check_and_process_move (bool *change_p, bool *sec_mem_p ATTRIBUTE_UNUSED)
1074 {
1075   int sregno, dregno;
1076   rtx dest, src, dreg, sreg, old_sreg, new_reg, scratch_reg;
1077   rtx_insn *before;
1078   enum reg_class dclass, sclass, secondary_class;
1079   machine_mode sreg_mode;
1080   secondary_reload_info sri;
1081
1082   lra_assert (curr_insn_set != NULL_RTX);
1083   dreg = dest = SET_DEST (curr_insn_set);
1084   sreg = src = SET_SRC (curr_insn_set);
1085   if (GET_CODE (dest) == SUBREG)
1086     dreg = SUBREG_REG (dest);
1087   if (GET_CODE (src) == SUBREG)
1088     sreg = SUBREG_REG (src);
1089   if (! (REG_P (dreg) || MEM_P (dreg)) || ! (REG_P (sreg) || MEM_P (sreg)))
1090     return false;
1091   sclass = dclass = NO_REGS;
1092   if (REG_P (dreg))
1093     dclass = get_reg_class (REGNO (dreg));
1094   if (dclass == ALL_REGS)
1095     /* ALL_REGS is used for new pseudos created by transformations
1096        like reload of SUBREG_REG (see function
1097        simplify_operand_subreg).  We don't know their class yet.  We
1098        should figure out the class from processing the insn
1099        constraints not in this fast path function.  Even if ALL_REGS
1100        were a right class for the pseudo, secondary_... hooks usually
1101        are not define for ALL_REGS.  */
1102     return false;
1103   sreg_mode = GET_MODE (sreg);
1104   old_sreg = sreg;
1105   if (REG_P (sreg))
1106     sclass = get_reg_class (REGNO (sreg));
1107   if (sclass == ALL_REGS)
1108     /* See comments above.  */
1109     return false;
1110   if (sclass == NO_REGS && dclass == NO_REGS)
1111     return false;
1112 #ifdef SECONDARY_MEMORY_NEEDED
1113   if (SECONDARY_MEMORY_NEEDED (sclass, dclass, GET_MODE (src))
1114 #ifdef SECONDARY_MEMORY_NEEDED_MODE
1115       && ((sclass != NO_REGS && dclass != NO_REGS)
1116           || GET_MODE (src) != SECONDARY_MEMORY_NEEDED_MODE (GET_MODE (src)))
1117 #endif
1118       )
1119     {
1120       *sec_mem_p = true;
1121       return false;
1122     }
1123 #endif
1124   if (! REG_P (dreg) || ! REG_P (sreg))
1125     return false;
1126   sri.prev_sri = NULL;
1127   sri.icode = CODE_FOR_nothing;
1128   sri.extra_cost = 0;
1129   secondary_class = NO_REGS;
1130   /* Set up hard register for a reload pseudo for hook
1131      secondary_reload because some targets just ignore unassigned
1132      pseudos in the hook.  */
1133   if (dclass != NO_REGS && lra_get_regno_hard_regno (REGNO (dreg)) < 0)
1134     {
1135       dregno = REGNO (dreg);
1136       reg_renumber[dregno] = ira_class_hard_regs[dclass][0];
1137     }
1138   else
1139     dregno = -1;
1140   if (sclass != NO_REGS && lra_get_regno_hard_regno (REGNO (sreg)) < 0)
1141     {
1142       sregno = REGNO (sreg);
1143       reg_renumber[sregno] = ira_class_hard_regs[sclass][0];
1144     }
1145   else
1146     sregno = -1;
1147   if (sclass != NO_REGS)
1148     secondary_class
1149       = (enum reg_class) targetm.secondary_reload (false, dest,
1150                                                    (reg_class_t) sclass,
1151                                                    GET_MODE (src), &sri);
1152   if (sclass == NO_REGS
1153       || ((secondary_class != NO_REGS || sri.icode != CODE_FOR_nothing)
1154           && dclass != NO_REGS))
1155     {
1156       enum reg_class old_sclass = secondary_class;
1157       secondary_reload_info old_sri = sri;
1158
1159       sri.prev_sri = NULL;
1160       sri.icode = CODE_FOR_nothing;
1161       sri.extra_cost = 0;
1162       secondary_class
1163         = (enum reg_class) targetm.secondary_reload (true, sreg,
1164                                                      (reg_class_t) dclass,
1165                                                      sreg_mode, &sri);
1166       /* Check the target hook consistency.  */
1167       lra_assert
1168         ((secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
1169          || (old_sclass == NO_REGS && old_sri.icode == CODE_FOR_nothing)
1170          || (secondary_class == old_sclass && sri.icode == old_sri.icode));
1171     }
1172   if (sregno >= 0)
1173     reg_renumber [sregno] = -1;
1174   if (dregno >= 0)
1175     reg_renumber [dregno] = -1;
1176   if (secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
1177     return false;
1178   *change_p = true;
1179   new_reg = NULL_RTX;
1180   if (secondary_class != NO_REGS)
1181     new_reg = lra_create_new_reg_with_unique_value (sreg_mode, NULL_RTX,
1182                                                     secondary_class,
1183                                                     "secondary");
1184   start_sequence ();
1185   if (old_sreg != sreg)
1186     sreg = copy_rtx (sreg);
1187   if (sri.icode == CODE_FOR_nothing)
1188     lra_emit_move (new_reg, sreg);
1189   else
1190     {
1191       enum reg_class scratch_class;
1192
1193       scratch_class = (reg_class_from_constraints
1194                        (insn_data[sri.icode].operand[2].constraint));
1195       scratch_reg = (lra_create_new_reg_with_unique_value
1196                      (insn_data[sri.icode].operand[2].mode, NULL_RTX,
1197                       scratch_class, "scratch"));
1198       emit_insn (GEN_FCN (sri.icode) (new_reg != NULL_RTX ? new_reg : dest,
1199                                       sreg, scratch_reg));
1200     }
1201   before = get_insns ();
1202   end_sequence ();
1203   lra_process_new_insns (curr_insn, before, NULL, "Inserting the move");
1204   if (new_reg != NULL_RTX)
1205     {
1206       if (GET_CODE (src) == SUBREG)
1207         SUBREG_REG (src) = new_reg;
1208       else
1209         SET_SRC (curr_insn_set) = new_reg;
1210     }
1211   else
1212     {
1213       if (lra_dump_file != NULL)
1214         {
1215           fprintf (lra_dump_file, "Deleting move %u\n", INSN_UID (curr_insn));
1216           dump_insn_slim (lra_dump_file, curr_insn);
1217         }
1218       lra_set_insn_deleted (curr_insn);
1219       return true;
1220     }
1221   return false;
1222 }
1223
1224 /* The following data describe the result of process_alt_operands.
1225    The data are used in curr_insn_transform to generate reloads.  */
1226
1227 /* The chosen reg classes which should be used for the corresponding
1228    operands.  */
1229 static enum reg_class goal_alt[MAX_RECOG_OPERANDS];
1230 /* True if the operand should be the same as another operand and that
1231    other operand does not need a reload.  */
1232 static bool goal_alt_match_win[MAX_RECOG_OPERANDS];
1233 /* True if the operand does not need a reload.  */
1234 static bool goal_alt_win[MAX_RECOG_OPERANDS];
1235 /* True if the operand can be offsetable memory.  */
1236 static bool goal_alt_offmemok[MAX_RECOG_OPERANDS];
1237 /* The number of an operand to which given operand can be matched to.  */
1238 static int goal_alt_matches[MAX_RECOG_OPERANDS];
1239 /* The number of elements in the following array.  */
1240 static int goal_alt_dont_inherit_ops_num;
1241 /* Numbers of operands whose reload pseudos should not be inherited.  */
1242 static int goal_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1243 /* True if the insn commutative operands should be swapped.  */
1244 static bool goal_alt_swapped;
1245 /* The chosen insn alternative.  */
1246 static int goal_alt_number;
1247
1248 /* The following five variables are used to choose the best insn
1249    alternative.  They reflect final characteristics of the best
1250    alternative.  */
1251
1252 /* Number of necessary reloads and overall cost reflecting the
1253    previous value and other unpleasantness of the best alternative.  */
1254 static int best_losers, best_overall;
1255 /* Overall number hard registers used for reloads.  For example, on
1256    some targets we need 2 general registers to reload DFmode and only
1257    one floating point register.  */
1258 static int best_reload_nregs;
1259 /* Overall number reflecting distances of previous reloading the same
1260    value.  The distances are counted from the current BB start.  It is
1261    used to improve inheritance chances.  */
1262 static int best_reload_sum;
1263
1264 /* True if the current insn should have no correspondingly input or
1265    output reloads.  */
1266 static bool no_input_reloads_p, no_output_reloads_p;
1267
1268 /* True if we swapped the commutative operands in the current
1269    insn.  */
1270 static int curr_swapped;
1271
1272 /* if CHECK_ONLY_P is false, arrange for address element *LOC to be a
1273    register of class CL.  Add any input reloads to list BEFORE.  AFTER
1274    is nonnull if *LOC is an automodified value; handle that case by
1275    adding the required output reloads to list AFTER.  Return true if
1276    the RTL was changed.
1277
1278    if CHECK_ONLY_P is true, check that the *LOC is a correct address
1279    register.  Return false if the address register is correct.  */
1280 static bool
1281 process_addr_reg (rtx *loc, bool check_only_p, rtx_insn **before, rtx_insn **after,
1282                   enum reg_class cl)
1283 {
1284   int regno;
1285   enum reg_class rclass, new_class;
1286   rtx reg;
1287   rtx new_reg;
1288   machine_mode mode;
1289   bool subreg_p, before_p = false;
1290
1291   subreg_p = GET_CODE (*loc) == SUBREG;
1292   if (subreg_p)
1293     loc = &SUBREG_REG (*loc);
1294   reg = *loc;
1295   mode = GET_MODE (reg);
1296   if (! REG_P (reg))
1297     {
1298       if (check_only_p)
1299         return true;
1300       /* Always reload memory in an address even if the target supports
1301          such addresses.  */
1302       new_reg = lra_create_new_reg_with_unique_value (mode, reg, cl, "address");
1303       before_p = true;
1304     }
1305   else
1306     {
1307       regno = REGNO (reg);
1308       rclass = get_reg_class (regno);
1309       if (! check_only_p
1310           && (*loc = get_equiv_with_elimination (reg, curr_insn)) != reg)
1311         {
1312           if (lra_dump_file != NULL)
1313             {
1314               fprintf (lra_dump_file,
1315                        "Changing pseudo %d in address of insn %u on equiv ",
1316                        REGNO (reg), INSN_UID (curr_insn));
1317               dump_value_slim (lra_dump_file, *loc, 1);
1318               fprintf (lra_dump_file, "\n");
1319             }
1320           *loc = copy_rtx (*loc);
1321         }
1322       if (*loc != reg || ! in_class_p (reg, cl, &new_class))
1323         {
1324           if (check_only_p)
1325             return true;
1326           reg = *loc;
1327           if (get_reload_reg (after == NULL ? OP_IN : OP_INOUT,
1328                               mode, reg, cl, subreg_p, "address", &new_reg))
1329             before_p = true;
1330         }
1331       else if (new_class != NO_REGS && rclass != new_class)
1332         {
1333           if (check_only_p)
1334             return true;
1335           lra_change_class (regno, new_class, "    Change to", true);
1336           return false;
1337         }
1338       else
1339         return false;
1340     }
1341   if (before_p)
1342     {
1343       push_to_sequence (*before);
1344       lra_emit_move (new_reg, reg);
1345       *before = get_insns ();
1346       end_sequence ();
1347     }
1348   *loc = new_reg;
1349   if (after != NULL)
1350     {
1351       start_sequence ();
1352       lra_emit_move (reg, new_reg);
1353       emit_insn (*after);
1354       *after = get_insns ();
1355       end_sequence ();
1356     }
1357   return true;
1358 }
1359
1360 /* Insert move insn in simplify_operand_subreg. BEFORE returns
1361    the insn to be inserted before curr insn. AFTER returns the
1362    the insn to be inserted after curr insn.  ORIGREG and NEWREG
1363    are the original reg and new reg for reload.  */
1364 static void
1365 insert_move_for_subreg (rtx_insn **before, rtx_insn **after, rtx origreg,
1366                         rtx newreg)
1367 {
1368   if (before)
1369     {
1370       push_to_sequence (*before);
1371       lra_emit_move (newreg, origreg);
1372       *before = get_insns ();
1373       end_sequence ();
1374     }
1375   if (after)
1376     {
1377       start_sequence ();
1378       lra_emit_move (origreg, newreg);
1379       emit_insn (*after);
1380       *after = get_insns ();
1381       end_sequence ();
1382     }
1383 }
1384
1385 static int valid_address_p (machine_mode mode, rtx addr, addr_space_t as);
1386
1387 /* Make reloads for subreg in operand NOP with internal subreg mode
1388    REG_MODE, add new reloads for further processing.  Return true if
1389    any change was done.  */
1390 static bool
1391 simplify_operand_subreg (int nop, machine_mode reg_mode)
1392 {
1393   int hard_regno;
1394   rtx_insn *before, *after;
1395   machine_mode mode, innermode;
1396   rtx reg, new_reg;
1397   rtx operand = *curr_id->operand_loc[nop];
1398   enum reg_class regclass;
1399   enum op_type type;
1400
1401   before = after = NULL;
1402
1403   if (GET_CODE (operand) != SUBREG)
1404     return false;
1405
1406   mode = GET_MODE (operand);
1407   reg = SUBREG_REG (operand);
1408   innermode = GET_MODE (reg);
1409   type = curr_static_id->operand[nop].type;
1410   /* If we change address for paradoxical subreg of memory, the
1411      address might violate the necessary alignment or the access might
1412      be slow.  So take this into consideration.  We should not worry
1413      about access beyond allocated memory for paradoxical memory
1414      subregs as we don't substitute such equiv memory (see processing
1415      equivalences in function lra_constraints) and because for spilled
1416      pseudos we allocate stack memory enough for the biggest
1417      corresponding paradoxical subreg.  */
1418   if (MEM_P (reg)
1419       && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (reg))
1420           || MEM_ALIGN (reg) >= GET_MODE_ALIGNMENT (mode)))
1421     {
1422       rtx subst, old = *curr_id->operand_loc[nop];
1423
1424       alter_subreg (curr_id->operand_loc[nop], false);
1425       subst = *curr_id->operand_loc[nop];
1426       lra_assert (MEM_P (subst));
1427       if (! valid_address_p (innermode, XEXP (reg, 0),
1428                              MEM_ADDR_SPACE (reg))
1429           || valid_address_p (GET_MODE (subst), XEXP (subst, 0),
1430                               MEM_ADDR_SPACE (subst)))
1431         return true;
1432       /* If the address was valid and became invalid, prefer to reload
1433          the memory.  Typical case is when the index scale should
1434          correspond the memory.  */
1435       *curr_id->operand_loc[nop] = old;
1436     }
1437   else if (REG_P (reg) && REGNO (reg) < FIRST_PSEUDO_REGISTER)
1438     {
1439       alter_subreg (curr_id->operand_loc[nop], false);
1440       return true;
1441     }
1442   else if (CONSTANT_P (reg))
1443     {
1444       /* Try to simplify subreg of constant.  It is usually result of
1445          equivalence substitution.  */
1446       if (innermode == VOIDmode
1447           && (innermode = original_subreg_reg_mode[nop]) == VOIDmode)
1448         innermode = curr_static_id->operand[nop].mode;
1449       if ((new_reg = simplify_subreg (mode, reg, innermode,
1450                                       SUBREG_BYTE (operand))) != NULL_RTX)
1451         {
1452           *curr_id->operand_loc[nop] = new_reg;
1453           return true;
1454         }
1455     }
1456   /* Put constant into memory when we have mixed modes.  It generates
1457      a better code in most cases as it does not need a secondary
1458      reload memory.  It also prevents LRA looping when LRA is using
1459      secondary reload memory again and again.  */
1460   if (CONSTANT_P (reg) && CONST_POOL_OK_P (reg_mode, reg)
1461       && SCALAR_INT_MODE_P (reg_mode) != SCALAR_INT_MODE_P (mode))
1462     {
1463       SUBREG_REG (operand) = force_const_mem (reg_mode, reg);
1464       alter_subreg (curr_id->operand_loc[nop], false);
1465       return true;
1466     }
1467   /* Force a reload of the SUBREG_REG if this is a constant or PLUS or
1468      if there may be a problem accessing OPERAND in the outer
1469      mode.  */
1470   if ((REG_P (reg)
1471        && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1472        && (hard_regno = lra_get_regno_hard_regno (REGNO (reg))) >= 0
1473        /* Don't reload paradoxical subregs because we could be looping
1474           having repeatedly final regno out of hard regs range.  */
1475        && (hard_regno_nregs[hard_regno][innermode]
1476            >= hard_regno_nregs[hard_regno][mode])
1477        && simplify_subreg_regno (hard_regno, innermode,
1478                                  SUBREG_BYTE (operand), mode) < 0
1479        /* Don't reload subreg for matching reload.  It is actually
1480           valid subreg in LRA.  */
1481        && ! LRA_SUBREG_P (operand))
1482       || CONSTANT_P (reg) || GET_CODE (reg) == PLUS || MEM_P (reg))
1483     {
1484       enum reg_class rclass;
1485
1486       if (REG_P (reg))
1487         /* There is a big probability that we will get the same class
1488            for the new pseudo and we will get the same insn which
1489            means infinite looping.  So spill the new pseudo.  */
1490         rclass = NO_REGS;
1491       else
1492         /* The class will be defined later in curr_insn_transform.  */
1493         rclass
1494           = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1495
1496       if (get_reload_reg (curr_static_id->operand[nop].type, reg_mode, reg,
1497                           rclass, TRUE, "subreg reg", &new_reg))
1498         {
1499           bool insert_before, insert_after;
1500           bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1501
1502           insert_before = (type != OP_OUT
1503                            || GET_MODE_SIZE (innermode) > GET_MODE_SIZE (mode));
1504           insert_after = (type != OP_IN);
1505           insert_move_for_subreg (insert_before ? &before : NULL,
1506                                   insert_after ? &after : NULL,
1507                                   reg, new_reg);
1508         }
1509       SUBREG_REG (operand) = new_reg;
1510       lra_process_new_insns (curr_insn, before, after,
1511                              "Inserting subreg reload");
1512       return true;
1513     }
1514   /* Force a reload for a paradoxical subreg. For paradoxical subreg,
1515      IRA allocates hardreg to the inner pseudo reg according to its mode
1516      instead of the outermode, so the size of the hardreg may not be enough
1517      to contain the outermode operand, in that case we may need to insert
1518      reload for the reg. For the following two types of paradoxical subreg,
1519      we need to insert reload:
1520      1. If the op_type is OP_IN, and the hardreg could not be paired with
1521         other hardreg to contain the outermode operand
1522         (checked by in_hard_reg_set_p), we need to insert the reload.
1523      2. If the op_type is OP_OUT or OP_INOUT.
1524
1525      Here is a paradoxical subreg example showing how the reload is generated:
1526
1527      (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
1528         (subreg:TI (reg:DI 107 [ __comp ]) 0)) {*movti_internal_rex64}
1529
1530      In IRA, reg107 is allocated to a DImode hardreg. We use x86-64 as example
1531      here, if reg107 is assigned to hardreg R15, because R15 is the last
1532      hardreg, compiler cannot find another hardreg to pair with R15 to
1533      contain TImode data. So we insert a TImode reload reg180 for it.
1534      After reload is inserted:
1535
1536      (insn 283 0 0 (set (subreg:DI (reg:TI 180 [orig:107 __comp ] [107]) 0)
1537         (reg:DI 107 [ __comp ])) -1
1538      (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
1539         (subreg:TI (reg:TI 180 [orig:107 __comp ] [107]) 0)) {*movti_internal_rex64}
1540
1541      Two reload hard registers will be allocated to reg180 to save TImode data
1542      in LRA_assign.  */
1543   else if (REG_P (reg)
1544            && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1545            && (hard_regno = lra_get_regno_hard_regno (REGNO (reg))) >= 0
1546            && (hard_regno_nregs[hard_regno][innermode]
1547                < hard_regno_nregs[hard_regno][mode])
1548            && (regclass = lra_get_allocno_class (REGNO (reg)))
1549            && (type != OP_IN
1550                || !in_hard_reg_set_p (reg_class_contents[regclass],
1551                                       mode, hard_regno)))
1552     {
1553       /* The class will be defined later in curr_insn_transform.  */
1554       enum reg_class rclass
1555         = (enum reg_class) targetm.preferred_reload_class (reg, ALL_REGS);
1556
1557       if (get_reload_reg (curr_static_id->operand[nop].type, mode, reg,
1558                           rclass, TRUE, "paradoxical subreg", &new_reg))
1559         {
1560           rtx subreg;
1561           bool insert_before, insert_after;
1562
1563           PUT_MODE (new_reg, mode);
1564           subreg = simplify_gen_subreg (innermode, new_reg, mode, 0);
1565           bitmap_set_bit (&lra_subreg_reload_pseudos, REGNO (new_reg));
1566
1567           insert_before = (type != OP_OUT);
1568           insert_after = (type != OP_IN);
1569           insert_move_for_subreg (insert_before ? &before : NULL,
1570                                   insert_after ? &after : NULL,
1571                                   reg, subreg);
1572         }
1573       SUBREG_REG (operand) = new_reg;
1574       lra_process_new_insns (curr_insn, before, after,
1575                              "Inserting paradoxical subreg reload");
1576       return true;
1577     }
1578   return false;
1579 }
1580
1581 /* Return TRUE if X refers for a hard register from SET.  */
1582 static bool
1583 uses_hard_regs_p (rtx x, HARD_REG_SET set)
1584 {
1585   int i, j, x_hard_regno;
1586   machine_mode mode;
1587   const char *fmt;
1588   enum rtx_code code;
1589
1590   if (x == NULL_RTX)
1591     return false;
1592   code = GET_CODE (x);
1593   mode = GET_MODE (x);
1594   if (code == SUBREG)
1595     {
1596       x = SUBREG_REG (x);
1597       code = GET_CODE (x);
1598       if (GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (mode))
1599         mode = GET_MODE (x);
1600     }
1601
1602   if (REG_P (x))
1603     {
1604       x_hard_regno = get_hard_regno (x);
1605       return (x_hard_regno >= 0
1606               && overlaps_hard_reg_set_p (set, mode, x_hard_regno));
1607     }
1608   if (MEM_P (x))
1609     {
1610       struct address_info ad;
1611
1612       decompose_mem_address (&ad, x);
1613       if (ad.base_term != NULL && uses_hard_regs_p (*ad.base_term, set))
1614         return true;
1615       if (ad.index_term != NULL && uses_hard_regs_p (*ad.index_term, set))
1616         return true;
1617     }
1618   fmt = GET_RTX_FORMAT (code);
1619   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1620     {
1621       if (fmt[i] == 'e')
1622         {
1623           if (uses_hard_regs_p (XEXP (x, i), set))
1624             return true;
1625         }
1626       else if (fmt[i] == 'E')
1627         {
1628           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1629             if (uses_hard_regs_p (XVECEXP (x, i, j), set))
1630               return true;
1631         }
1632     }
1633   return false;
1634 }
1635
1636 /* Return true if OP is a spilled pseudo. */
1637 static inline bool
1638 spilled_pseudo_p (rtx op)
1639 {
1640   return (REG_P (op)
1641           && REGNO (op) >= FIRST_PSEUDO_REGISTER && in_mem_p (REGNO (op)));
1642 }
1643
1644 /* Return true if X is a general constant.  */
1645 static inline bool
1646 general_constant_p (rtx x)
1647 {
1648   return CONSTANT_P (x) && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (x));
1649 }
1650
1651 static bool
1652 reg_in_class_p (rtx reg, enum reg_class cl)
1653 {
1654   if (cl == NO_REGS)
1655     return get_reg_class (REGNO (reg)) == NO_REGS;
1656   return in_class_p (reg, cl, NULL);
1657 }
1658
1659 /* Return true if SET of RCLASS contains no hard regs which can be
1660    used in MODE.  */
1661 static bool
1662 prohibited_class_reg_set_mode_p (enum reg_class rclass,
1663                                  HARD_REG_SET &set,
1664                                  enum machine_mode mode)
1665 {
1666   HARD_REG_SET temp;
1667   
1668   lra_assert (hard_reg_set_subset_p (set, reg_class_contents[rclass]));
1669   COPY_HARD_REG_SET (temp, set);
1670   AND_COMPL_HARD_REG_SET (temp, lra_no_alloc_regs);
1671   return (hard_reg_set_subset_p
1672           (temp, ira_prohibited_class_mode_regs[rclass][mode]));
1673 }
1674
1675 /* Major function to choose the current insn alternative and what
1676    operands should be reloaded and how.  If ONLY_ALTERNATIVE is not
1677    negative we should consider only this alternative.  Return false if
1678    we can not choose the alternative or find how to reload the
1679    operands.  */
1680 static bool
1681 process_alt_operands (int only_alternative)
1682 {
1683   bool ok_p = false;
1684   int nop, overall, nalt;
1685   int n_alternatives = curr_static_id->n_alternatives;
1686   int n_operands = curr_static_id->n_operands;
1687   /* LOSERS counts the operands that don't fit this alternative and
1688      would require loading.  */
1689   int losers;
1690   /* REJECT is a count of how undesirable this alternative says it is
1691      if any reloading is required.  If the alternative matches exactly
1692      then REJECT is ignored, but otherwise it gets this much counted
1693      against it in addition to the reloading needed.  */
1694   int reject;
1695   int op_reject;
1696   /* The number of elements in the following array.  */
1697   int early_clobbered_regs_num;
1698   /* Numbers of operands which are early clobber registers.  */
1699   int early_clobbered_nops[MAX_RECOG_OPERANDS];
1700   enum reg_class curr_alt[MAX_RECOG_OPERANDS];
1701   HARD_REG_SET curr_alt_set[MAX_RECOG_OPERANDS];
1702   bool curr_alt_match_win[MAX_RECOG_OPERANDS];
1703   bool curr_alt_win[MAX_RECOG_OPERANDS];
1704   bool curr_alt_offmemok[MAX_RECOG_OPERANDS];
1705   int curr_alt_matches[MAX_RECOG_OPERANDS];
1706   /* The number of elements in the following array.  */
1707   int curr_alt_dont_inherit_ops_num;
1708   /* Numbers of operands whose reload pseudos should not be inherited.  */
1709   int curr_alt_dont_inherit_ops[MAX_RECOG_OPERANDS];
1710   rtx op;
1711   /* The register when the operand is a subreg of register, otherwise the
1712      operand itself.  */
1713   rtx no_subreg_reg_operand[MAX_RECOG_OPERANDS];
1714   /* The register if the operand is a register or subreg of register,
1715      otherwise NULL.  */
1716   rtx operand_reg[MAX_RECOG_OPERANDS];
1717   int hard_regno[MAX_RECOG_OPERANDS];
1718   machine_mode biggest_mode[MAX_RECOG_OPERANDS];
1719   int reload_nregs, reload_sum;
1720   bool costly_p;
1721   enum reg_class cl;
1722
1723   /* Calculate some data common for all alternatives to speed up the
1724      function.  */
1725   for (nop = 0; nop < n_operands; nop++)
1726     {
1727       rtx reg;
1728
1729       op = no_subreg_reg_operand[nop] = *curr_id->operand_loc[nop];
1730       /* The real hard regno of the operand after the allocation.  */
1731       hard_regno[nop] = get_hard_regno (op);
1732
1733       operand_reg[nop] = reg = op;
1734       biggest_mode[nop] = GET_MODE (op);
1735       if (GET_CODE (op) == SUBREG)
1736         {
1737           operand_reg[nop] = reg = SUBREG_REG (op);
1738           if (GET_MODE_SIZE (biggest_mode[nop])
1739               < GET_MODE_SIZE (GET_MODE (reg)))
1740             biggest_mode[nop] = GET_MODE (reg);
1741         }
1742       if (! REG_P (reg))
1743         operand_reg[nop] = NULL_RTX;
1744       else if (REGNO (reg) >= FIRST_PSEUDO_REGISTER
1745                || ((int) REGNO (reg)
1746                    == lra_get_elimination_hard_regno (REGNO (reg))))
1747         no_subreg_reg_operand[nop] = reg;
1748       else
1749         operand_reg[nop] = no_subreg_reg_operand[nop]
1750           /* Just use natural mode for elimination result.  It should
1751              be enough for extra constraints hooks.  */
1752           = regno_reg_rtx[hard_regno[nop]];
1753     }
1754
1755   /* The constraints are made of several alternatives.  Each operand's
1756      constraint looks like foo,bar,... with commas separating the
1757      alternatives.  The first alternatives for all operands go
1758      together, the second alternatives go together, etc.
1759
1760      First loop over alternatives.  */
1761   alternative_mask preferred = curr_id->preferred_alternatives;
1762   if (only_alternative >= 0)
1763     preferred &= ALTERNATIVE_BIT (only_alternative);
1764
1765   for (nalt = 0; nalt < n_alternatives; nalt++)
1766     {
1767       /* Loop over operands for one constraint alternative.  */
1768       if (!TEST_BIT (preferred, nalt))
1769         continue;
1770
1771       overall = losers = reject = reload_nregs = reload_sum = 0;
1772       for (nop = 0; nop < n_operands; nop++)
1773         {
1774           int inc = (curr_static_id
1775                      ->operand_alternative[nalt * n_operands + nop].reject);
1776           if (lra_dump_file != NULL && inc != 0)
1777             fprintf (lra_dump_file,
1778                      "            Staticly defined alt reject+=%d\n", inc);
1779           reject += inc;
1780         }
1781       early_clobbered_regs_num = 0;
1782
1783       for (nop = 0; nop < n_operands; nop++)
1784         {
1785           const char *p;
1786           char *end;
1787           int len, c, m, i, opalt_num, this_alternative_matches;
1788           bool win, did_match, offmemok, early_clobber_p;
1789           /* false => this operand can be reloaded somehow for this
1790              alternative.  */
1791           bool badop;
1792           /* true => this operand can be reloaded if the alternative
1793              allows regs.  */
1794           bool winreg;
1795           /* True if a constant forced into memory would be OK for
1796              this operand.  */
1797           bool constmemok;
1798           enum reg_class this_alternative, this_costly_alternative;
1799           HARD_REG_SET this_alternative_set, this_costly_alternative_set;
1800           bool this_alternative_match_win, this_alternative_win;
1801           bool this_alternative_offmemok;
1802           bool scratch_p;
1803           machine_mode mode;
1804           enum constraint_num cn;
1805
1806           opalt_num = nalt * n_operands + nop;
1807           if (curr_static_id->operand_alternative[opalt_num].anything_ok)
1808             {
1809               /* Fast track for no constraints at all.  */
1810               curr_alt[nop] = NO_REGS;
1811               CLEAR_HARD_REG_SET (curr_alt_set[nop]);
1812               curr_alt_win[nop] = true;
1813               curr_alt_match_win[nop] = false;
1814               curr_alt_offmemok[nop] = false;
1815               curr_alt_matches[nop] = -1;
1816               continue;
1817             }
1818
1819           op = no_subreg_reg_operand[nop];
1820           mode = curr_operand_mode[nop];
1821
1822           win = did_match = winreg = offmemok = constmemok = false;
1823           badop = true;
1824
1825           early_clobber_p = false;
1826           p = curr_static_id->operand_alternative[opalt_num].constraint;
1827
1828           this_costly_alternative = this_alternative = NO_REGS;
1829           /* We update set of possible hard regs besides its class
1830              because reg class might be inaccurate.  For example,
1831              union of LO_REGS (l), HI_REGS(h), and STACK_REG(k) in ARM
1832              is translated in HI_REGS because classes are merged by
1833              pairs and there is no accurate intermediate class.  */
1834           CLEAR_HARD_REG_SET (this_alternative_set);
1835           CLEAR_HARD_REG_SET (this_costly_alternative_set);
1836           this_alternative_win = false;
1837           this_alternative_match_win = false;
1838           this_alternative_offmemok = false;
1839           this_alternative_matches = -1;
1840
1841           /* An empty constraint should be excluded by the fast
1842              track.  */
1843           lra_assert (*p != 0 && *p != ',');
1844
1845           op_reject = 0;
1846           /* Scan this alternative's specs for this operand; set WIN
1847              if the operand fits any letter in this alternative.
1848              Otherwise, clear BADOP if this operand could fit some
1849              letter after reloads, or set WINREG if this operand could
1850              fit after reloads provided the constraint allows some
1851              registers.  */
1852           costly_p = false;
1853           do
1854             {
1855               switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
1856                 {
1857                 case '\0':
1858                   len = 0;
1859                   break;
1860                 case ',':
1861                   c = '\0';
1862                   break;
1863
1864                 case '&':
1865                   early_clobber_p = true;
1866                   break;
1867
1868                 case '$':
1869                   op_reject += LRA_MAX_REJECT;
1870                   break;
1871                 case '^':
1872                   op_reject += LRA_LOSER_COST_FACTOR;
1873                   break;
1874
1875                 case '#':
1876                   /* Ignore rest of this alternative.  */
1877                   c = '\0';
1878                   break;
1879
1880                 case '0':  case '1':  case '2':  case '3':  case '4':
1881                 case '5':  case '6':  case '7':  case '8':  case '9':
1882                   {
1883                     int m_hregno;
1884                     bool match_p;
1885
1886                     m = strtoul (p, &end, 10);
1887                     p = end;
1888                     len = 0;
1889                     lra_assert (nop > m);
1890
1891                     this_alternative_matches = m;
1892                     m_hregno = get_hard_regno (*curr_id->operand_loc[m]);
1893                     /* We are supposed to match a previous operand.
1894                        If we do, we win if that one did.  If we do
1895                        not, count both of the operands as losers.
1896                        (This is too conservative, since most of the
1897                        time only a single reload insn will be needed
1898                        to make the two operands win.  As a result,
1899                        this alternative may be rejected when it is
1900                        actually desirable.)  */
1901                     match_p = false;
1902                     if (operands_match_p (*curr_id->operand_loc[nop],
1903                                           *curr_id->operand_loc[m], m_hregno))
1904                       {
1905                         /* We should reject matching of an early
1906                            clobber operand if the matching operand is
1907                            not dying in the insn.  */
1908                         if (! curr_static_id->operand[m].early_clobber
1909                             || operand_reg[nop] == NULL_RTX
1910                             || (find_regno_note (curr_insn, REG_DEAD,
1911                                                  REGNO (op))
1912                                 || REGNO (op) == REGNO (operand_reg[m])))
1913                           match_p = true;
1914                       }
1915                     if (match_p)
1916                       {
1917                         /* If we are matching a non-offsettable
1918                            address where an offsettable address was
1919                            expected, then we must reject this
1920                            combination, because we can't reload
1921                            it.  */
1922                         if (curr_alt_offmemok[m]
1923                             && MEM_P (*curr_id->operand_loc[m])
1924                             && curr_alt[m] == NO_REGS && ! curr_alt_win[m])
1925                           continue;
1926                       }
1927                     else
1928                       {
1929                         /* Operands don't match.  Both operands must
1930                            allow a reload register, otherwise we
1931                            cannot make them match.  */
1932                         if (curr_alt[m] == NO_REGS)
1933                           break;
1934                         /* Retroactively mark the operand we had to
1935                            match as a loser, if it wasn't already and
1936                            it wasn't matched to a register constraint
1937                            (e.g it might be matched by memory). */
1938                         if (curr_alt_win[m]
1939                             && (operand_reg[m] == NULL_RTX
1940                                 || hard_regno[m] < 0))
1941                           {
1942                             losers++;
1943                             reload_nregs
1944                               += (ira_reg_class_max_nregs[curr_alt[m]]
1945                                   [GET_MODE (*curr_id->operand_loc[m])]);
1946                           }
1947
1948                         /* Prefer matching earlyclobber alternative as
1949                            it results in less hard regs required for
1950                            the insn than a non-matching earlyclobber
1951                            alternative.  */
1952                         if (curr_static_id->operand[m].early_clobber)
1953                           {
1954                             if (lra_dump_file != NULL)
1955                               fprintf
1956                                 (lra_dump_file,
1957                                  "            %d Matching earlyclobber alt:"
1958                                  " reject--\n",
1959                                  nop);
1960                             reject--;
1961                           }
1962                         /* Otherwise we prefer no matching
1963                            alternatives because it gives more freedom
1964                            in RA.  */
1965                         else if (operand_reg[nop] == NULL_RTX
1966                                  || (find_regno_note (curr_insn, REG_DEAD,
1967                                                       REGNO (operand_reg[nop]))
1968                                      == NULL_RTX))
1969                           {
1970                             if (lra_dump_file != NULL)
1971                               fprintf
1972                                 (lra_dump_file,
1973                                  "            %d Matching alt: reject+=2\n",
1974                                  nop);
1975                             reject += 2;
1976                           }
1977                       }
1978                     /* If we have to reload this operand and some
1979                        previous operand also had to match the same
1980                        thing as this operand, we don't know how to do
1981                        that.  */
1982                     if (!match_p || !curr_alt_win[m])
1983                       {
1984                         for (i = 0; i < nop; i++)
1985                           if (curr_alt_matches[i] == m)
1986                             break;
1987                         if (i < nop)
1988                           break;
1989                       }
1990                     else
1991                       did_match = true;
1992
1993                     /* This can be fixed with reloads if the operand
1994                        we are supposed to match can be fixed with
1995                        reloads. */
1996                     badop = false;
1997                     this_alternative = curr_alt[m];
1998                     COPY_HARD_REG_SET (this_alternative_set, curr_alt_set[m]);
1999                     winreg = this_alternative != NO_REGS;
2000                     break;
2001                   }
2002
2003                 case 'g':
2004                   if (MEM_P (op)
2005                       || general_constant_p (op)
2006                       || spilled_pseudo_p (op))
2007                     win = true;
2008                   cl = GENERAL_REGS;
2009                   goto reg;
2010
2011                 default:
2012                   cn = lookup_constraint (p);
2013                   switch (get_constraint_type (cn))
2014                     {
2015                     case CT_REGISTER:
2016                       cl = reg_class_for_constraint (cn);
2017                       if (cl != NO_REGS)
2018                         goto reg;
2019                       break;
2020
2021                     case CT_CONST_INT:
2022                       if (CONST_INT_P (op)
2023                           && insn_const_int_ok_for_constraint (INTVAL (op), cn))
2024                         win = true;
2025                       break;
2026
2027                     case CT_MEMORY:
2028                       if (MEM_P (op)
2029                           && satisfies_memory_constraint_p (op, cn))
2030                         win = true;
2031                       else if (spilled_pseudo_p (op))
2032                         win = true;
2033
2034                       /* If we didn't already win, we can reload constants
2035                          via force_const_mem or put the pseudo value into
2036                          memory, or make other memory by reloading the
2037                          address like for 'o'.  */
2038                       if (CONST_POOL_OK_P (mode, op)
2039                           || MEM_P (op) || REG_P (op))
2040                         badop = false;
2041                       constmemok = true;
2042                       offmemok = true;
2043                       break;
2044
2045                     case CT_ADDRESS:
2046                       /* If we didn't already win, we can reload the address
2047                          into a base register.  */
2048                       if (satisfies_address_constraint_p (op, cn))
2049                         win = true;
2050                       cl = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC,
2051                                            ADDRESS, SCRATCH);
2052                       badop = false;
2053                       goto reg;
2054
2055                     case CT_FIXED_FORM:
2056                       if (constraint_satisfied_p (op, cn))
2057                         win = true;
2058                       break;
2059                     }
2060                   break;
2061
2062                 reg:
2063                   this_alternative = reg_class_subunion[this_alternative][cl];
2064                   IOR_HARD_REG_SET (this_alternative_set,
2065                                     reg_class_contents[cl]);
2066                   if (costly_p)
2067                     {
2068                       this_costly_alternative
2069                         = reg_class_subunion[this_costly_alternative][cl];
2070                       IOR_HARD_REG_SET (this_costly_alternative_set,
2071                                         reg_class_contents[cl]);
2072                     }
2073                   if (mode == BLKmode)
2074                     break;
2075                   winreg = true;
2076                   if (REG_P (op))
2077                     {
2078                       if (hard_regno[nop] >= 0
2079                           && in_hard_reg_set_p (this_alternative_set,
2080                                                 mode, hard_regno[nop]))
2081                         win = true;
2082                       else if (hard_regno[nop] < 0
2083                                && in_class_p (op, this_alternative, NULL))
2084                         win = true;
2085                     }
2086                   break;
2087                 }
2088               if (c != ' ' && c != '\t')
2089                 costly_p = c == '*';
2090             }
2091           while ((p += len), c);
2092
2093           scratch_p = (operand_reg[nop] != NULL_RTX
2094                        && lra_former_scratch_p (REGNO (operand_reg[nop])));
2095           /* Record which operands fit this alternative.  */
2096           if (win)
2097             {
2098               this_alternative_win = true;
2099               if (operand_reg[nop] != NULL_RTX)
2100                 {
2101                   if (hard_regno[nop] >= 0)
2102                     {
2103                       if (in_hard_reg_set_p (this_costly_alternative_set,
2104                                              mode, hard_regno[nop]))
2105                         {
2106                           if (lra_dump_file != NULL)
2107                             fprintf (lra_dump_file,
2108                                      "            %d Costly set: reject++\n",
2109                                      nop);
2110                           reject++;
2111                         }
2112                     }
2113                   else
2114                     {
2115                       /* Prefer won reg to spilled pseudo under other
2116                          equal conditions for possibe inheritance.  */
2117                       if (! scratch_p)
2118                         {
2119                           if (lra_dump_file != NULL)
2120                             fprintf
2121                               (lra_dump_file,
2122                                "            %d Non pseudo reload: reject++\n",
2123                                nop);
2124                           reject++;
2125                         }
2126                       if (in_class_p (operand_reg[nop],
2127                                       this_costly_alternative, NULL))
2128                         {
2129                           if (lra_dump_file != NULL)
2130                             fprintf
2131                               (lra_dump_file,
2132                                "            %d Non pseudo costly reload:"
2133                                " reject++\n",
2134                                nop);
2135                           reject++;
2136                         }
2137                     }
2138                   /* We simulate the behaviour of old reload here.
2139                      Although scratches need hard registers and it
2140                      might result in spilling other pseudos, no reload
2141                      insns are generated for the scratches.  So it
2142                      might cost something but probably less than old
2143                      reload pass believes.  */
2144                   if (scratch_p)
2145                     {
2146                       if (lra_dump_file != NULL)
2147                         fprintf (lra_dump_file,
2148                                  "            %d Scratch win: reject+=2\n",
2149                                  nop);
2150                       reject += 2;
2151                     }
2152                 }
2153             }
2154           else if (did_match)
2155             this_alternative_match_win = true;
2156           else
2157             {
2158               int const_to_mem = 0;
2159               bool no_regs_p;
2160
2161               reject += op_reject;
2162               /* Never do output reload of stack pointer.  It makes
2163                  impossible to do elimination when SP is changed in
2164                  RTL.  */
2165               if (op == stack_pointer_rtx && ! frame_pointer_needed
2166                   && curr_static_id->operand[nop].type != OP_IN)
2167                 goto fail;
2168
2169               /* If this alternative asks for a specific reg class, see if there
2170                  is at least one allocatable register in that class.  */
2171               no_regs_p
2172                 = (this_alternative == NO_REGS
2173                    || (hard_reg_set_subset_p
2174                        (reg_class_contents[this_alternative],
2175                         lra_no_alloc_regs)));
2176
2177               /* For asms, verify that the class for this alternative is possible
2178                  for the mode that is specified.  */
2179               if (!no_regs_p && INSN_CODE (curr_insn) < 0)
2180                 {
2181                   int i;
2182                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2183                     if (HARD_REGNO_MODE_OK (i, mode)
2184                         && in_hard_reg_set_p (reg_class_contents[this_alternative],
2185                                               mode, i))
2186                       break;
2187                   if (i == FIRST_PSEUDO_REGISTER)
2188                     winreg = false;
2189                 }
2190
2191               /* If this operand accepts a register, and if the
2192                  register class has at least one allocatable register,
2193                  then this operand can be reloaded.  */
2194               if (winreg && !no_regs_p)
2195                 badop = false;
2196
2197               if (badop)
2198                 {
2199                   if (lra_dump_file != NULL)
2200                     fprintf (lra_dump_file,
2201                              "            alt=%d: Bad operand -- refuse\n",
2202                              nalt);
2203                   goto fail;
2204                 }
2205
2206               /* If not assigned pseudo has a class which a subset of
2207                  required reg class, it is a less costly alternative
2208                  as the pseudo still can get a hard reg of necessary
2209                  class.  */
2210               if (! no_regs_p && REG_P (op) && hard_regno[nop] < 0
2211                   && (cl = get_reg_class (REGNO (op))) != NO_REGS
2212                   && ira_class_subset_p[this_alternative][cl])
2213                 {
2214                   if (lra_dump_file != NULL)
2215                     fprintf
2216                       (lra_dump_file,
2217                        "            %d Super set class reg: reject-=3\n", nop);
2218                   reject -= 3;
2219                 }
2220
2221               this_alternative_offmemok = offmemok;
2222               if (this_costly_alternative != NO_REGS)
2223                 {
2224                   if (lra_dump_file != NULL)
2225                     fprintf (lra_dump_file,
2226                              "            %d Costly loser: reject++\n", nop);
2227                   reject++;
2228                 }
2229               /* If the operand is dying, has a matching constraint,
2230                  and satisfies constraints of the matched operand
2231                  which failed to satisfy the own constraints, most probably
2232                  the reload for this operand will be gone.  */
2233               if (this_alternative_matches >= 0
2234                   && !curr_alt_win[this_alternative_matches]
2235                   && REG_P (op)
2236                   && find_regno_note (curr_insn, REG_DEAD, REGNO (op))
2237                   && (hard_regno[nop] >= 0
2238                       ? in_hard_reg_set_p (this_alternative_set,
2239                                            mode, hard_regno[nop])
2240                       : in_class_p (op, this_alternative, NULL)))
2241                 {
2242                   if (lra_dump_file != NULL)
2243                     fprintf
2244                       (lra_dump_file,
2245                        "            %d Dying matched operand reload: reject++\n",
2246                        nop);
2247                   reject++;
2248                 }
2249               else
2250                 {
2251                   /* Strict_low_part requires to reload the register
2252                      not the sub-register.  In this case we should
2253                      check that a final reload hard reg can hold the
2254                      value mode.  */
2255                   if (curr_static_id->operand[nop].strict_low
2256                       && REG_P (op)
2257                       && hard_regno[nop] < 0
2258                       && GET_CODE (*curr_id->operand_loc[nop]) == SUBREG
2259                       && ira_class_hard_regs_num[this_alternative] > 0
2260                       && ! HARD_REGNO_MODE_OK (ira_class_hard_regs
2261                                                [this_alternative][0],
2262                                                GET_MODE
2263                                                (*curr_id->operand_loc[nop])))
2264                     {
2265                       if (lra_dump_file != NULL)
2266                         fprintf
2267                           (lra_dump_file,
2268                            "            alt=%d: Strict low subreg reload -- refuse\n",
2269                            nalt);
2270                       goto fail;
2271                     }
2272                   losers++;
2273                 }
2274               if (operand_reg[nop] != NULL_RTX
2275                   /* Output operands and matched input operands are
2276                      not inherited.  The following conditions do not
2277                      exactly describe the previous statement but they
2278                      are pretty close.  */
2279                   && curr_static_id->operand[nop].type != OP_OUT
2280                   && (this_alternative_matches < 0
2281                       || curr_static_id->operand[nop].type != OP_IN))
2282                 {
2283                   int last_reload = (lra_reg_info[ORIGINAL_REGNO
2284                                                   (operand_reg[nop])]
2285                                      .last_reload);
2286
2287                   /* The value of reload_sum has sense only if we
2288                      process insns in their order.  It happens only on
2289                      the first constraints sub-pass when we do most of
2290                      reload work.  */
2291                   if (lra_constraint_iter == 1 && last_reload > bb_reload_num)
2292                     reload_sum += last_reload - bb_reload_num;
2293                 }
2294               /* If this is a constant that is reloaded into the
2295                  desired class by copying it to memory first, count
2296                  that as another reload.  This is consistent with
2297                  other code and is required to avoid choosing another
2298                  alternative when the constant is moved into memory.
2299                  Note that the test here is precisely the same as in
2300                  the code below that calls force_const_mem.  */
2301               if (CONST_POOL_OK_P (mode, op)
2302                   && ((targetm.preferred_reload_class
2303                        (op, this_alternative) == NO_REGS)
2304                       || no_input_reloads_p))
2305                 {
2306                   const_to_mem = 1;
2307                   if (! no_regs_p)
2308                     losers++;
2309                 }
2310
2311               /* Alternative loses if it requires a type of reload not
2312                  permitted for this insn.  We can always reload
2313                  objects with a REG_UNUSED note.  */
2314               if ((curr_static_id->operand[nop].type != OP_IN
2315                    && no_output_reloads_p
2316                    && ! find_reg_note (curr_insn, REG_UNUSED, op))
2317                   || (curr_static_id->operand[nop].type != OP_OUT
2318                       && no_input_reloads_p && ! const_to_mem)
2319                   || (this_alternative_matches >= 0
2320                       && (no_input_reloads_p
2321                           || (no_output_reloads_p
2322                               && (curr_static_id->operand
2323                                   [this_alternative_matches].type != OP_IN)
2324                               && ! find_reg_note (curr_insn, REG_UNUSED,
2325                                                   no_subreg_reg_operand
2326                                                   [this_alternative_matches])))))
2327                 {
2328                   if (lra_dump_file != NULL)
2329                     fprintf
2330                       (lra_dump_file,
2331                        "            alt=%d: No input/otput reload -- refuse\n",
2332                        nalt);
2333                   goto fail;
2334                 }
2335
2336               /* Alternative loses if it required class pseudo can not
2337                  hold value of required mode.  Such insns can be
2338                  described by insn definitions with mode iterators.  */
2339               if (GET_MODE (*curr_id->operand_loc[nop]) != VOIDmode
2340                   && ! hard_reg_set_empty_p (this_alternative_set)
2341                   /* It is common practice for constraints to use a
2342                      class which does not have actually enough regs to
2343                      hold the value (e.g. x86 AREG for mode requiring
2344                      more one general reg).  Therefore we have 2
2345                      conditions to check that the reload pseudo can
2346                      not hold the mode value.  */
2347                   && ! HARD_REGNO_MODE_OK (ira_class_hard_regs
2348                                            [this_alternative][0],
2349                                            GET_MODE (*curr_id->operand_loc[nop]))
2350                   /* The above condition is not enough as the first
2351                      reg in ira_class_hard_regs can be not aligned for
2352                      multi-words mode values.  */
2353                   && (prohibited_class_reg_set_mode_p
2354                       (this_alternative, this_alternative_set,
2355                        GET_MODE (*curr_id->operand_loc[nop]))))
2356                 {
2357                   if (lra_dump_file != NULL)
2358                     fprintf (lra_dump_file,
2359                              "            alt=%d: reload pseudo for op %d "
2360                              " can not hold the mode value -- refuse\n",
2361                              nalt, nop);
2362                   goto fail;
2363                 }
2364
2365               /* Check strong discouragement of reload of non-constant
2366                  into class THIS_ALTERNATIVE.  */
2367               if (! CONSTANT_P (op) && ! no_regs_p
2368                   && (targetm.preferred_reload_class
2369                       (op, this_alternative) == NO_REGS
2370                       || (curr_static_id->operand[nop].type == OP_OUT
2371                           && (targetm.preferred_output_reload_class
2372                               (op, this_alternative) == NO_REGS))))
2373                 {
2374                   if (lra_dump_file != NULL)
2375                     fprintf (lra_dump_file,
2376                              "            %d Non-prefered reload: reject+=%d\n",
2377                              nop, LRA_MAX_REJECT);
2378                   reject += LRA_MAX_REJECT;
2379                 }
2380
2381               if (! (MEM_P (op) && offmemok)
2382                   && ! (const_to_mem && constmemok))
2383                 {
2384                   /* We prefer to reload pseudos over reloading other
2385                      things, since such reloads may be able to be
2386                      eliminated later.  So bump REJECT in other cases.
2387                      Don't do this in the case where we are forcing a
2388                      constant into memory and it will then win since
2389                      we don't want to have a different alternative
2390                      match then.  */
2391                   if (! (REG_P (op) && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2392                     {
2393                       if (lra_dump_file != NULL)
2394                         fprintf
2395                           (lra_dump_file,
2396                            "            %d Non-pseudo reload: reject+=2\n",
2397                            nop);
2398                       reject += 2;
2399                     }
2400
2401                   if (! no_regs_p)
2402                     reload_nregs
2403                       += ira_reg_class_max_nregs[this_alternative][mode];
2404
2405                   if (SMALL_REGISTER_CLASS_P (this_alternative))
2406                     {
2407                       if (lra_dump_file != NULL)
2408                         fprintf
2409                           (lra_dump_file,
2410                            "            %d Small class reload: reject+=%d\n",
2411                            nop, LRA_LOSER_COST_FACTOR / 2);
2412                       reject += LRA_LOSER_COST_FACTOR / 2;
2413                     }
2414                 }
2415
2416               /* We are trying to spill pseudo into memory.  It is
2417                  usually more costly than moving to a hard register
2418                  although it might takes the same number of
2419                  reloads.  */
2420               if (no_regs_p && REG_P (op) && hard_regno[nop] >= 0)
2421                 {
2422                   if (lra_dump_file != NULL)
2423                     fprintf
2424                       (lra_dump_file,
2425                        "            %d Spill pseudo into memory: reject+=3\n",
2426                        nop);
2427                   reject += 3;
2428                   if (VECTOR_MODE_P (mode))
2429                     {
2430                       /* Spilling vectors into memory is usually more
2431                          costly as they contain big values.  */
2432                       if (lra_dump_file != NULL)
2433                         fprintf
2434                           (lra_dump_file,
2435                            "            %d Spill vector pseudo: reject+=2\n",
2436                            nop);
2437                       reject += 2;
2438                     }
2439                 }
2440
2441 #ifdef SECONDARY_MEMORY_NEEDED
2442               /* If reload requires moving value through secondary
2443                  memory, it will need one more insn at least.  */
2444               if (this_alternative != NO_REGS 
2445                   && REG_P (op) && (cl = get_reg_class (REGNO (op))) != NO_REGS
2446                   && ((curr_static_id->operand[nop].type != OP_OUT
2447                        && SECONDARY_MEMORY_NEEDED (cl, this_alternative,
2448                                                    GET_MODE (op)))
2449                       || (curr_static_id->operand[nop].type != OP_IN
2450                           && SECONDARY_MEMORY_NEEDED (this_alternative, cl,
2451                                                       GET_MODE (op)))))
2452                 losers++;
2453 #endif
2454               /* Input reloads can be inherited more often than output
2455                  reloads can be removed, so penalize output
2456                  reloads.  */
2457               if (!REG_P (op) || curr_static_id->operand[nop].type != OP_IN)
2458                 {
2459                   if (lra_dump_file != NULL)
2460                     fprintf
2461                       (lra_dump_file,
2462                        "            %d Non input pseudo reload: reject++\n",
2463                        nop);
2464                   reject++;
2465                 }
2466             }
2467
2468           if (early_clobber_p && ! scratch_p)
2469             {
2470               if (lra_dump_file != NULL)
2471                 fprintf (lra_dump_file,
2472                          "            %d Early clobber: reject++\n", nop);
2473               reject++;
2474             }
2475           /* ??? We check early clobbers after processing all operands
2476              (see loop below) and there we update the costs more.
2477              Should we update the cost (may be approximately) here
2478              because of early clobber register reloads or it is a rare
2479              or non-important thing to be worth to do it.  */
2480           overall = losers * LRA_LOSER_COST_FACTOR + reject;
2481           if ((best_losers == 0 || losers != 0) && best_overall < overall)
2482             {
2483               if (lra_dump_file != NULL)
2484                 fprintf (lra_dump_file,
2485                          "            alt=%d,overall=%d,losers=%d -- refuse\n",
2486                          nalt, overall, losers);
2487               goto fail;
2488             }
2489
2490           curr_alt[nop] = this_alternative;
2491           COPY_HARD_REG_SET (curr_alt_set[nop], this_alternative_set);
2492           curr_alt_win[nop] = this_alternative_win;
2493           curr_alt_match_win[nop] = this_alternative_match_win;
2494           curr_alt_offmemok[nop] = this_alternative_offmemok;
2495           curr_alt_matches[nop] = this_alternative_matches;
2496
2497           if (this_alternative_matches >= 0
2498               && !did_match && !this_alternative_win)
2499             curr_alt_win[this_alternative_matches] = false;
2500
2501           if (early_clobber_p && operand_reg[nop] != NULL_RTX)
2502             early_clobbered_nops[early_clobbered_regs_num++] = nop;
2503         }
2504       if (curr_insn_set != NULL_RTX && n_operands == 2
2505           /* Prevent processing non-move insns.  */
2506           && (GET_CODE (SET_SRC (curr_insn_set)) == SUBREG
2507               || SET_SRC (curr_insn_set) == no_subreg_reg_operand[1])
2508           && ((! curr_alt_win[0] && ! curr_alt_win[1]
2509                && REG_P (no_subreg_reg_operand[0])
2510                && REG_P (no_subreg_reg_operand[1])
2511                && (reg_in_class_p (no_subreg_reg_operand[0], curr_alt[1])
2512                    || reg_in_class_p (no_subreg_reg_operand[1], curr_alt[0])))
2513               || (! curr_alt_win[0] && curr_alt_win[1]
2514                   && REG_P (no_subreg_reg_operand[1])
2515                   && reg_in_class_p (no_subreg_reg_operand[1], curr_alt[0]))
2516               || (curr_alt_win[0] && ! curr_alt_win[1]
2517                   && REG_P (no_subreg_reg_operand[0])
2518                   && reg_in_class_p (no_subreg_reg_operand[0], curr_alt[1])
2519                   && (! CONST_POOL_OK_P (curr_operand_mode[1],
2520                                          no_subreg_reg_operand[1])
2521                       || (targetm.preferred_reload_class
2522                           (no_subreg_reg_operand[1],
2523                            (enum reg_class) curr_alt[1]) != NO_REGS))
2524                   /* If it is a result of recent elimination in move
2525                      insn we can transform it into an add still by
2526                      using this alternative.  */
2527                   && GET_CODE (no_subreg_reg_operand[1]) != PLUS)))
2528         {
2529           /* We have a move insn and a new reload insn will be similar
2530              to the current insn.  We should avoid such situation as it
2531              results in LRA cycling.  */
2532           overall += LRA_MAX_REJECT;
2533         }
2534       ok_p = true;
2535       curr_alt_dont_inherit_ops_num = 0;
2536       for (nop = 0; nop < early_clobbered_regs_num; nop++)
2537         {
2538           int i, j, clobbered_hard_regno, first_conflict_j, last_conflict_j;
2539           HARD_REG_SET temp_set;
2540
2541           i = early_clobbered_nops[nop];
2542           if ((! curr_alt_win[i] && ! curr_alt_match_win[i])
2543               || hard_regno[i] < 0)
2544             continue;
2545           lra_assert (operand_reg[i] != NULL_RTX);
2546           clobbered_hard_regno = hard_regno[i];
2547           CLEAR_HARD_REG_SET (temp_set);
2548           add_to_hard_reg_set (&temp_set, biggest_mode[i], clobbered_hard_regno);
2549           first_conflict_j = last_conflict_j = -1;
2550           for (j = 0; j < n_operands; j++)
2551             if (j == i
2552                 /* We don't want process insides of match_operator and
2553                    match_parallel because otherwise we would process
2554                    their operands once again generating a wrong
2555                    code.  */
2556                 || curr_static_id->operand[j].is_operator)
2557               continue;
2558             else if ((curr_alt_matches[j] == i && curr_alt_match_win[j])
2559                      || (curr_alt_matches[i] == j && curr_alt_match_win[i]))
2560               continue;
2561             /* If we don't reload j-th operand, check conflicts.  */
2562             else if ((curr_alt_win[j] || curr_alt_match_win[j])
2563                      && uses_hard_regs_p (*curr_id->operand_loc[j], temp_set))
2564               {
2565                 if (first_conflict_j < 0)
2566                   first_conflict_j = j;
2567                 last_conflict_j = j;
2568               }
2569           if (last_conflict_j < 0)
2570             continue;
2571           /* If earlyclobber operand conflicts with another
2572              non-matching operand which is actually the same register
2573              as the earlyclobber operand, it is better to reload the
2574              another operand as an operand matching the earlyclobber
2575              operand can be also the same.  */
2576           if (first_conflict_j == last_conflict_j
2577               && operand_reg[last_conflict_j]
2578               != NULL_RTX && ! curr_alt_match_win[last_conflict_j]
2579               && REGNO (operand_reg[i]) == REGNO (operand_reg[last_conflict_j]))
2580             {
2581               curr_alt_win[last_conflict_j] = false;
2582               curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++]
2583                 = last_conflict_j;
2584               losers++;
2585               /* Early clobber was already reflected in REJECT. */
2586               lra_assert (reject > 0);
2587               if (lra_dump_file != NULL)
2588                 fprintf
2589                   (lra_dump_file,
2590                    "            %d Conflict early clobber reload: reject--\n",
2591                    i);
2592               reject--;
2593               overall += LRA_LOSER_COST_FACTOR - 1;
2594             }
2595           else
2596             {
2597               /* We need to reload early clobbered register and the
2598                  matched registers.  */
2599               for (j = 0; j < n_operands; j++)
2600                 if (curr_alt_matches[j] == i)
2601                   {
2602                     curr_alt_match_win[j] = false;
2603                     losers++;
2604                     overall += LRA_LOSER_COST_FACTOR;
2605                   }
2606               if (! curr_alt_match_win[i])
2607                 curr_alt_dont_inherit_ops[curr_alt_dont_inherit_ops_num++] = i;
2608               else
2609                 {
2610                   /* Remember pseudos used for match reloads are never
2611                      inherited.  */
2612                   lra_assert (curr_alt_matches[i] >= 0);
2613                   curr_alt_win[curr_alt_matches[i]] = false;
2614                 }
2615               curr_alt_win[i] = curr_alt_match_win[i] = false;
2616               losers++;
2617               /* Early clobber was already reflected in REJECT. */
2618               lra_assert (reject > 0);
2619               if (lra_dump_file != NULL)
2620                 fprintf
2621                   (lra_dump_file,
2622                    "            %d Matched conflict early clobber reloads:"
2623                    "reject--\n",
2624                    i);
2625               reject--;
2626               overall += LRA_LOSER_COST_FACTOR - 1;
2627             }
2628         }
2629       if (lra_dump_file != NULL)
2630         fprintf (lra_dump_file, "          alt=%d,overall=%d,losers=%d,rld_nregs=%d\n",
2631                  nalt, overall, losers, reload_nregs);
2632
2633       /* If this alternative can be made to work by reloading, and it
2634          needs less reloading than the others checked so far, record
2635          it as the chosen goal for reloading.  */
2636       if ((best_losers != 0 && losers == 0)
2637           || (((best_losers == 0 && losers == 0)
2638                || (best_losers != 0 && losers != 0))
2639               && (best_overall > overall
2640                   || (best_overall == overall
2641                       /* If the cost of the reloads is the same,
2642                          prefer alternative which requires minimal
2643                          number of reload regs.  */
2644                       && (reload_nregs < best_reload_nregs
2645                           || (reload_nregs == best_reload_nregs
2646                               && (best_reload_sum < reload_sum
2647                                   || (best_reload_sum == reload_sum
2648                                       && nalt < goal_alt_number))))))))
2649         {
2650           for (nop = 0; nop < n_operands; nop++)
2651             {
2652               goal_alt_win[nop] = curr_alt_win[nop];
2653               goal_alt_match_win[nop] = curr_alt_match_win[nop];
2654               goal_alt_matches[nop] = curr_alt_matches[nop];
2655               goal_alt[nop] = curr_alt[nop];
2656               goal_alt_offmemok[nop] = curr_alt_offmemok[nop];
2657             }
2658           goal_alt_dont_inherit_ops_num = curr_alt_dont_inherit_ops_num;
2659           for (nop = 0; nop < curr_alt_dont_inherit_ops_num; nop++)
2660             goal_alt_dont_inherit_ops[nop] = curr_alt_dont_inherit_ops[nop];
2661           goal_alt_swapped = curr_swapped;
2662           best_overall = overall;
2663           best_losers = losers;
2664           best_reload_nregs = reload_nregs;
2665           best_reload_sum = reload_sum;
2666           goal_alt_number = nalt;
2667         }
2668       if (losers == 0)
2669         /* Everything is satisfied.  Do not process alternatives
2670            anymore.  */
2671         break;
2672     fail:
2673       ;
2674     }
2675   return ok_p;
2676 }
2677
2678 /* Make reload base reg from address AD.  */
2679 static rtx
2680 base_to_reg (struct address_info *ad)
2681 {
2682   enum reg_class cl;
2683   int code = -1;
2684   rtx new_inner = NULL_RTX;
2685   rtx new_reg = NULL_RTX;
2686   rtx_insn *insn;
2687   rtx_insn *last_insn = get_last_insn();
2688
2689   lra_assert (ad->base == ad->base_term && ad->disp == ad->disp_term);
2690   cl = base_reg_class (ad->mode, ad->as, ad->base_outer_code,
2691                        get_index_code (ad));
2692   new_reg = lra_create_new_reg (GET_MODE (*ad->base_term), NULL_RTX,
2693                                 cl, "base");
2694   new_inner = simplify_gen_binary (PLUS, GET_MODE (new_reg), new_reg,
2695                                    ad->disp_term == NULL
2696                                    ? gen_int_mode (0, ad->mode)
2697                                    : *ad->disp_term);
2698   if (!valid_address_p (ad->mode, new_inner, ad->as))
2699     return NULL_RTX;
2700   insn = emit_insn (gen_rtx_SET (ad->mode, new_reg, *ad->base_term));
2701   code = recog_memoized (insn);
2702   if (code < 0)
2703     {
2704       delete_insns_since (last_insn);
2705       return NULL_RTX;
2706     }
2707
2708   return new_inner;
2709 }
2710
2711 /* Make reload base reg + disp from address AD.  Return the new pseudo.  */
2712 static rtx
2713 base_plus_disp_to_reg (struct address_info *ad)
2714 {
2715   enum reg_class cl;
2716   rtx new_reg;
2717
2718   lra_assert (ad->base == ad->base_term && ad->disp == ad->disp_term);
2719   cl = base_reg_class (ad->mode, ad->as, ad->base_outer_code,
2720                        get_index_code (ad));
2721   new_reg = lra_create_new_reg (GET_MODE (*ad->base_term), NULL_RTX,
2722                                 cl, "base + disp");
2723   lra_emit_add (new_reg, *ad->base_term, *ad->disp_term);
2724   return new_reg;
2725 }
2726
2727 /* Make reload of index part of address AD.  Return the new
2728    pseudo.  */
2729 static rtx
2730 index_part_to_reg (struct address_info *ad)
2731 {
2732   rtx new_reg;
2733
2734   new_reg = lra_create_new_reg (GET_MODE (*ad->index), NULL_RTX,
2735                                 INDEX_REG_CLASS, "index term");
2736   expand_mult (GET_MODE (*ad->index), *ad->index_term,
2737                GEN_INT (get_index_scale (ad)), new_reg, 1);
2738   return new_reg;
2739 }
2740
2741 /* Return true if we can add a displacement to address AD, even if that
2742    makes the address invalid.  The fix-up code requires any new address
2743    to be the sum of the BASE_TERM, INDEX and DISP_TERM fields.  */
2744 static bool
2745 can_add_disp_p (struct address_info *ad)
2746 {
2747   return (!ad->autoinc_p
2748           && ad->segment == NULL
2749           && ad->base == ad->base_term
2750           && ad->disp == ad->disp_term);
2751 }
2752
2753 /* Make equiv substitution in address AD.  Return true if a substitution
2754    was made.  */
2755 static bool
2756 equiv_address_substitution (struct address_info *ad)
2757 {
2758   rtx base_reg, new_base_reg, index_reg, new_index_reg, *base_term, *index_term;
2759   HOST_WIDE_INT disp, scale;
2760   bool change_p;
2761
2762   base_term = strip_subreg (ad->base_term);
2763   if (base_term == NULL)
2764     base_reg = new_base_reg = NULL_RTX;
2765   else
2766     {
2767       base_reg = *base_term;
2768       new_base_reg = get_equiv_with_elimination (base_reg, curr_insn);
2769     }
2770   index_term = strip_subreg (ad->index_term);
2771   if (index_term == NULL)
2772     index_reg = new_index_reg = NULL_RTX;
2773   else
2774     {
2775       index_reg = *index_term;
2776       new_index_reg = get_equiv_with_elimination (index_reg, curr_insn);
2777     }
2778   if (base_reg == new_base_reg && index_reg == new_index_reg)
2779     return false;
2780   disp = 0;
2781   change_p = false;
2782   if (lra_dump_file != NULL)
2783     {
2784       fprintf (lra_dump_file, "Changing address in insn %d ",
2785                INSN_UID (curr_insn));
2786       dump_value_slim (lra_dump_file, *ad->outer, 1);
2787     }
2788   if (base_reg != new_base_reg)
2789     {
2790       if (REG_P (new_base_reg))
2791         {
2792           *base_term = new_base_reg;
2793           change_p = true;
2794         }
2795       else if (GET_CODE (new_base_reg) == PLUS
2796                && REG_P (XEXP (new_base_reg, 0))
2797                && CONST_INT_P (XEXP (new_base_reg, 1))
2798                && can_add_disp_p (ad))
2799         {
2800           disp += INTVAL (XEXP (new_base_reg, 1));
2801           *base_term = XEXP (new_base_reg, 0);
2802           change_p = true;
2803         }
2804       if (ad->base_term2 != NULL)
2805         *ad->base_term2 = *ad->base_term;
2806     }
2807   if (index_reg != new_index_reg)
2808     {
2809       if (REG_P (new_index_reg))
2810         {
2811           *index_term = new_index_reg;
2812           change_p = true;
2813         }
2814       else if (GET_CODE (new_index_reg) == PLUS
2815                && REG_P (XEXP (new_index_reg, 0))
2816                && CONST_INT_P (XEXP (new_index_reg, 1))
2817                && can_add_disp_p (ad)
2818                && (scale = get_index_scale (ad)))
2819         {
2820           disp += INTVAL (XEXP (new_index_reg, 1)) * scale;
2821           *index_term = XEXP (new_index_reg, 0);
2822           change_p = true;
2823         }
2824     }
2825   if (disp != 0)
2826     {
2827       if (ad->disp != NULL)
2828         *ad->disp = plus_constant (GET_MODE (*ad->inner), *ad->disp, disp);
2829       else
2830         {
2831           *ad->inner = plus_constant (GET_MODE (*ad->inner), *ad->inner, disp);
2832           update_address (ad);
2833         }
2834       change_p = true;
2835     }
2836   if (lra_dump_file != NULL)
2837     {
2838       if (! change_p)
2839         fprintf (lra_dump_file, " -- no change\n");
2840       else
2841         {
2842           fprintf (lra_dump_file, " on equiv ");
2843           dump_value_slim (lra_dump_file, *ad->outer, 1);
2844           fprintf (lra_dump_file, "\n");
2845         }
2846     }
2847   return change_p;
2848 }
2849
2850 /* Major function to make reloads for an address in operand NOP or
2851    check its correctness (If CHECK_ONLY_P is true). The supported
2852    cases are:
2853
2854    1) an address that existed before LRA started, at which point it
2855    must have been valid.  These addresses are subject to elimination
2856    and may have become invalid due to the elimination offset being out
2857    of range.
2858
2859    2) an address created by forcing a constant to memory
2860    (force_const_to_mem).  The initial form of these addresses might
2861    not be valid, and it is this function's job to make them valid.
2862
2863    3) a frame address formed from a register and a (possibly zero)
2864    constant offset.  As above, these addresses might not be valid and
2865    this function must make them so.
2866
2867    Add reloads to the lists *BEFORE and *AFTER.  We might need to add
2868    reloads to *AFTER because of inc/dec, {pre, post} modify in the
2869    address.  Return true for any RTL change.
2870
2871    The function is a helper function which does not produce all
2872    transformations (when CHECK_ONLY_P is false) which can be
2873    necessary.  It does just basic steps.  To do all necessary
2874    transformations use function process_address.  */
2875 static bool
2876 process_address_1 (int nop, bool check_only_p,
2877                    rtx_insn **before, rtx_insn **after)
2878 {
2879   struct address_info ad;
2880   rtx new_reg;
2881   rtx op = *curr_id->operand_loc[nop];
2882   const char *constraint = curr_static_id->operand[nop].constraint;
2883   enum constraint_num cn = lookup_constraint (constraint);
2884   bool change_p = false;
2885
2886   if (insn_extra_address_constraint (cn))
2887     decompose_lea_address (&ad, curr_id->operand_loc[nop]);
2888   else if (MEM_P (op))
2889     decompose_mem_address (&ad, op);
2890   else if (GET_CODE (op) == SUBREG
2891            && MEM_P (SUBREG_REG (op)))
2892     decompose_mem_address (&ad, SUBREG_REG (op));
2893   else
2894     return false;
2895   /* If INDEX_REG_CLASS is assigned to base_term already and isn't to
2896      index_term, swap them so to avoid assigning INDEX_REG_CLASS to both
2897      when INDEX_REG_CLASS is a single register class.  */
2898   if (ad.base_term != NULL
2899       && ad.index_term != NULL
2900       && ira_class_hard_regs_num[INDEX_REG_CLASS] == 1
2901       && REG_P (*ad.base_term)
2902       && REG_P (*ad.index_term)
2903       && in_class_p (*ad.base_term, INDEX_REG_CLASS, NULL)
2904       && ! in_class_p (*ad.index_term, INDEX_REG_CLASS, NULL))
2905     {
2906       std::swap (ad.base, ad.index);
2907       std::swap (ad.base_term, ad.index_term);
2908     }
2909   if (! check_only_p)
2910     change_p = equiv_address_substitution (&ad);
2911   if (ad.base_term != NULL
2912       && (process_addr_reg
2913           (ad.base_term, check_only_p, before,
2914            (ad.autoinc_p
2915             && !(REG_P (*ad.base_term)
2916                  && find_regno_note (curr_insn, REG_DEAD,
2917                                      REGNO (*ad.base_term)) != NULL_RTX)
2918             ? after : NULL),
2919            base_reg_class (ad.mode, ad.as, ad.base_outer_code,
2920                            get_index_code (&ad)))))
2921     {
2922       change_p = true;
2923       if (ad.base_term2 != NULL)
2924         *ad.base_term2 = *ad.base_term;
2925     }
2926   if (ad.index_term != NULL
2927       && process_addr_reg (ad.index_term, check_only_p,
2928                            before, NULL, INDEX_REG_CLASS))
2929     change_p = true;
2930
2931   /* Target hooks sometimes don't treat extra-constraint addresses as
2932      legitimate address_operands, so handle them specially.  */
2933   if (insn_extra_address_constraint (cn)
2934       && satisfies_address_constraint_p (&ad, cn))
2935     return change_p;
2936
2937   if (check_only_p)
2938     return change_p;
2939
2940   /* There are three cases where the shape of *AD.INNER may now be invalid:
2941
2942      1) the original address was valid, but either elimination or
2943      equiv_address_substitution was applied and that made
2944      the address invalid.
2945
2946      2) the address is an invalid symbolic address created by
2947      force_const_to_mem.
2948
2949      3) the address is a frame address with an invalid offset.
2950
2951      4) the address is a frame address with an invalid base.
2952
2953      All these cases involve a non-autoinc address, so there is no
2954      point revalidating other types.  */
2955   if (ad.autoinc_p || valid_address_p (&ad))
2956     return change_p;
2957
2958   /* Any index existed before LRA started, so we can assume that the
2959      presence and shape of the index is valid.  */
2960   push_to_sequence (*before);
2961   lra_assert (ad.disp == ad.disp_term);
2962   if (ad.base == NULL)
2963     {
2964       if (ad.index == NULL)
2965         {
2966           int code = -1;
2967           enum reg_class cl = base_reg_class (ad.mode, ad.as,
2968                                               SCRATCH, SCRATCH);
2969           rtx addr = *ad.inner;
2970
2971           new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "addr");
2972 #ifdef HAVE_lo_sum
2973           {
2974             rtx_insn *insn;
2975             rtx_insn *last = get_last_insn ();
2976
2977             /* addr => lo_sum (new_base, addr), case (2) above.  */
2978             insn = emit_insn (gen_rtx_SET
2979                               (VOIDmode, new_reg,
2980                                gen_rtx_HIGH (Pmode, copy_rtx (addr))));
2981             code = recog_memoized (insn);
2982             if (code >= 0)
2983               {
2984                 *ad.inner = gen_rtx_LO_SUM (Pmode, new_reg, addr);
2985                 if (! valid_address_p (ad.mode, *ad.outer, ad.as))
2986                   {
2987                     /* Try to put lo_sum into register.  */
2988                     insn = emit_insn (gen_rtx_SET
2989                                       (VOIDmode, new_reg,
2990                                        gen_rtx_LO_SUM (Pmode, new_reg, addr)));
2991                     code = recog_memoized (insn);
2992                     if (code >= 0)
2993                       {
2994                         *ad.inner = new_reg;
2995                         if (! valid_address_p (ad.mode, *ad.outer, ad.as))
2996                           {
2997                             *ad.inner = addr;
2998                             code = -1;
2999                           }
3000                       }
3001                     
3002                   }
3003               }
3004             if (code < 0)
3005               delete_insns_since (last);
3006           }
3007 #endif
3008           if (code < 0)
3009             {
3010               /* addr => new_base, case (2) above.  */
3011               lra_emit_move (new_reg, addr);
3012               *ad.inner = new_reg;
3013             }
3014         }
3015       else
3016         {
3017           /* index * scale + disp => new base + index * scale,
3018              case (1) above.  */
3019           enum reg_class cl = base_reg_class (ad.mode, ad.as, PLUS,
3020                                               GET_CODE (*ad.index));
3021
3022           lra_assert (INDEX_REG_CLASS != NO_REGS);
3023           new_reg = lra_create_new_reg (Pmode, NULL_RTX, cl, "disp");
3024           lra_emit_move (new_reg, *ad.disp);
3025           *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3026                                            new_reg, *ad.index);
3027         }
3028     }
3029   else if (ad.index == NULL)
3030     {
3031       int regno;
3032       enum reg_class cl;
3033       rtx set;
3034       rtx_insn *insns, *last_insn;
3035       /* Try to reload base into register only if the base is invalid
3036          for the address but with valid offset, case (4) above.  */
3037       start_sequence ();
3038       new_reg = base_to_reg (&ad);
3039
3040       /* base + disp => new base, cases (1) and (3) above.  */
3041       /* Another option would be to reload the displacement into an
3042          index register.  However, postreload has code to optimize
3043          address reloads that have the same base and different
3044          displacements, so reloading into an index register would
3045          not necessarily be a win.  */
3046       if (new_reg == NULL_RTX)
3047         new_reg = base_plus_disp_to_reg (&ad);
3048       insns = get_insns ();
3049       last_insn = get_last_insn ();
3050       /* If we generated at least two insns, try last insn source as
3051          an address.  If we succeed, we generate one less insn.  */
3052       if (last_insn != insns && (set = single_set (last_insn)) != NULL_RTX
3053           && GET_CODE (SET_SRC (set)) == PLUS
3054           && REG_P (XEXP (SET_SRC (set), 0))
3055           && CONSTANT_P (XEXP (SET_SRC (set), 1)))
3056         {
3057           *ad.inner = SET_SRC (set);
3058           if (valid_address_p (ad.mode, *ad.outer, ad.as))
3059             {
3060               *ad.base_term = XEXP (SET_SRC (set), 0);
3061               *ad.disp_term = XEXP (SET_SRC (set), 1);
3062               cl = base_reg_class (ad.mode, ad.as, ad.base_outer_code,
3063                                    get_index_code (&ad));
3064               regno = REGNO (*ad.base_term);
3065               if (regno >= FIRST_PSEUDO_REGISTER
3066                   && cl != lra_get_allocno_class (regno))
3067                 lra_change_class (regno, cl, "      Change to", true);
3068               new_reg = SET_SRC (set);
3069               delete_insns_since (PREV_INSN (last_insn));
3070             }
3071         }
3072       /* Try if target can split displacement into legitimite new disp
3073          and offset.  If it's the case, we replace the last insn with
3074          insns for base + offset => new_reg and set new_reg + new disp
3075          to *ad.inner.  */
3076       last_insn = get_last_insn ();
3077       if ((set = single_set (last_insn)) != NULL_RTX
3078           && GET_CODE (SET_SRC (set)) == PLUS
3079           && REG_P (XEXP (SET_SRC (set), 0))
3080           && REGNO (XEXP (SET_SRC (set), 0)) < FIRST_PSEUDO_REGISTER
3081           && CONST_INT_P (XEXP (SET_SRC (set), 1)))
3082         {
3083           rtx addend, disp = XEXP (SET_SRC (set), 1);
3084           if (targetm.legitimize_address_displacement (&disp, &addend,
3085                                                        ad.mode))
3086             {
3087               rtx_insn *new_insns;
3088               start_sequence ();
3089               lra_emit_add (new_reg, XEXP (SET_SRC (set), 0), addend);
3090               new_insns = get_insns ();
3091               end_sequence ();
3092               new_reg = gen_rtx_PLUS (Pmode, new_reg, disp);
3093               delete_insns_since (PREV_INSN (last_insn));
3094               add_insn (new_insns);
3095               insns = get_insns ();
3096             }
3097         }
3098       end_sequence ();
3099       emit_insn (insns);
3100       *ad.inner = new_reg;
3101     }
3102   else if (ad.disp_term != NULL)
3103     {
3104       /* base + scale * index + disp => new base + scale * index,
3105          case (1) above.  */
3106       new_reg = base_plus_disp_to_reg (&ad);
3107       *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3108                                        new_reg, *ad.index);
3109     }
3110   else if (get_index_scale (&ad) == 1)
3111     {
3112       /* The last transformation to one reg will be made in
3113          curr_insn_transform function.  */
3114       end_sequence ();
3115       return false;
3116     }
3117   else
3118     {
3119       /* base + scale * index => base + new_reg,
3120          case (1) above.
3121       Index part of address may become invalid.  For example, we
3122       changed pseudo on the equivalent memory and a subreg of the
3123       pseudo onto the memory of different mode for which the scale is
3124       prohibitted.  */
3125       new_reg = index_part_to_reg (&ad);
3126       *ad.inner = simplify_gen_binary (PLUS, GET_MODE (new_reg),
3127                                        *ad.base_term, new_reg);
3128     }
3129   *before = get_insns ();
3130   end_sequence ();
3131   return true;
3132 }
3133
3134 /* If CHECK_ONLY_P is false, do address reloads until it is necessary.
3135    Use process_address_1 as a helper function.  Return true for any
3136    RTL changes.
3137
3138    If CHECK_ONLY_P is true, just check address correctness.  Return
3139    false if the address correct.  */
3140 static bool
3141 process_address (int nop, bool check_only_p,
3142                  rtx_insn **before, rtx_insn **after)
3143 {
3144   bool res = false;
3145
3146   while (process_address_1 (nop, check_only_p, before, after))
3147     {
3148       if (check_only_p)
3149         return true;
3150       res = true;
3151     }
3152   return res;
3153 }
3154
3155 /* Emit insns to reload VALUE into a new register.  VALUE is an
3156    auto-increment or auto-decrement RTX whose operand is a register or
3157    memory location; so reloading involves incrementing that location.
3158    IN is either identical to VALUE, or some cheaper place to reload
3159    value being incremented/decremented from.
3160
3161    INC_AMOUNT is the number to increment or decrement by (always
3162    positive and ignored for POST_MODIFY/PRE_MODIFY).
3163
3164    Return pseudo containing the result.  */
3165 static rtx
3166 emit_inc (enum reg_class new_rclass, rtx in, rtx value, int inc_amount)
3167 {
3168   /* REG or MEM to be copied and incremented.  */
3169   rtx incloc = XEXP (value, 0);
3170   /* Nonzero if increment after copying.  */
3171   int post = (GET_CODE (value) == POST_DEC || GET_CODE (value) == POST_INC
3172               || GET_CODE (value) == POST_MODIFY);
3173   rtx_insn *last;
3174   rtx inc;
3175   rtx_insn *add_insn;
3176   int code;
3177   rtx real_in = in == value ? incloc : in;
3178   rtx result;
3179   bool plus_p = true;
3180
3181   if (GET_CODE (value) == PRE_MODIFY || GET_CODE (value) == POST_MODIFY)
3182     {
3183       lra_assert (GET_CODE (XEXP (value, 1)) == PLUS
3184                   || GET_CODE (XEXP (value, 1)) == MINUS);
3185       lra_assert (rtx_equal_p (XEXP (XEXP (value, 1), 0), XEXP (value, 0)));
3186       plus_p = GET_CODE (XEXP (value, 1)) == PLUS;
3187       inc = XEXP (XEXP (value, 1), 1);
3188     }
3189   else
3190     {
3191       if (GET_CODE (value) == PRE_DEC || GET_CODE (value) == POST_DEC)
3192         inc_amount = -inc_amount;
3193
3194       inc = GEN_INT (inc_amount);
3195     }
3196
3197   if (! post && REG_P (incloc))
3198     result = incloc;
3199   else
3200     result = lra_create_new_reg (GET_MODE (value), value, new_rclass,
3201                                  "INC/DEC result");
3202
3203   if (real_in != result)
3204     {
3205       /* First copy the location to the result register.  */
3206       lra_assert (REG_P (result));
3207       emit_insn (gen_move_insn (result, real_in));
3208     }
3209
3210   /* We suppose that there are insns to add/sub with the constant
3211      increment permitted in {PRE/POST)_{DEC/INC/MODIFY}.  At least the
3212      old reload worked with this assumption.  If the assumption
3213      becomes wrong, we should use approach in function
3214      base_plus_disp_to_reg.  */
3215   if (in == value)
3216     {
3217       /* See if we can directly increment INCLOC.  */
3218       last = get_last_insn ();
3219       add_insn = emit_insn (plus_p
3220                             ? gen_add2_insn (incloc, inc)
3221                             : gen_sub2_insn (incloc, inc));
3222
3223       code = recog_memoized (add_insn);
3224       if (code >= 0)
3225         {
3226           if (! post && result != incloc)
3227             emit_insn (gen_move_insn (result, incloc));
3228           return result;
3229         }
3230       delete_insns_since (last);
3231     }
3232
3233   /* If couldn't do the increment directly, must increment in RESULT.
3234      The way we do this depends on whether this is pre- or
3235      post-increment.  For pre-increment, copy INCLOC to the reload
3236      register, increment it there, then save back.  */
3237   if (! post)
3238     {
3239       if (real_in != result)
3240         emit_insn (gen_move_insn (result, real_in));
3241       if (plus_p)
3242         emit_insn (gen_add2_insn (result, inc));
3243       else
3244         emit_insn (gen_sub2_insn (result, inc));
3245       if (result != incloc)
3246         emit_insn (gen_move_insn (incloc, result));
3247     }
3248   else
3249     {
3250       /* Post-increment.
3251
3252          Because this might be a jump insn or a compare, and because
3253          RESULT may not be available after the insn in an input
3254          reload, we must do the incrementing before the insn being
3255          reloaded for.
3256
3257          We have already copied IN to RESULT.  Increment the copy in
3258          RESULT, save that back, then decrement RESULT so it has
3259          the original value.  */
3260       if (plus_p)
3261         emit_insn (gen_add2_insn (result, inc));
3262       else
3263         emit_insn (gen_sub2_insn (result, inc));
3264       emit_insn (gen_move_insn (incloc, result));
3265       /* Restore non-modified value for the result.  We prefer this
3266          way because it does not require an additional hard
3267          register.  */
3268       if (plus_p)
3269         {
3270           if (CONST_INT_P (inc))
3271             emit_insn (gen_add2_insn (result,
3272                                       gen_int_mode (-INTVAL (inc),
3273                                                     GET_MODE (result))));
3274           else
3275             emit_insn (gen_sub2_insn (result, inc));
3276         }
3277       else
3278         emit_insn (gen_add2_insn (result, inc));
3279     }
3280   return result;
3281 }
3282
3283 /* Return true if the current move insn does not need processing as we
3284    already know that it satisfies its constraints.  */
3285 static bool
3286 simple_move_p (void)
3287 {
3288   rtx dest, src;
3289   enum reg_class dclass, sclass;
3290
3291   lra_assert (curr_insn_set != NULL_RTX);
3292   dest = SET_DEST (curr_insn_set);
3293   src = SET_SRC (curr_insn_set);
3294   return ((dclass = get_op_class (dest)) != NO_REGS
3295           && (sclass = get_op_class (src)) != NO_REGS
3296           /* The backend guarantees that register moves of cost 2
3297              never need reloads.  */
3298           && targetm.register_move_cost (GET_MODE (src), sclass, dclass) == 2);
3299  }
3300
3301 /* Swap operands NOP and NOP + 1. */
3302 static inline void
3303 swap_operands (int nop)
3304 {
3305   machine_mode mode = curr_operand_mode[nop];
3306   curr_operand_mode[nop] = curr_operand_mode[nop + 1];
3307   curr_operand_mode[nop + 1] = mode;
3308   mode = original_subreg_reg_mode[nop];
3309   original_subreg_reg_mode[nop] = original_subreg_reg_mode[nop + 1];
3310   original_subreg_reg_mode[nop + 1] = mode;
3311   rtx x = *curr_id->operand_loc[nop];
3312   *curr_id->operand_loc[nop] = *curr_id->operand_loc[nop + 1];
3313   *curr_id->operand_loc[nop + 1] = x;
3314   /* Swap the duplicates too.  */
3315   lra_update_dup (curr_id, nop);
3316   lra_update_dup (curr_id, nop + 1);
3317 }
3318
3319 /* Main entry point of the constraint code: search the body of the
3320    current insn to choose the best alternative.  It is mimicking insn
3321    alternative cost calculation model of former reload pass.  That is
3322    because machine descriptions were written to use this model.  This
3323    model can be changed in future.  Make commutative operand exchange
3324    if it is chosen.
3325
3326    if CHECK_ONLY_P is false, do RTL changes to satisfy the
3327    constraints.  Return true if any change happened during function
3328    call.
3329
3330    If CHECK_ONLY_P is true then don't do any transformation.  Just
3331    check that the insn satisfies all constraints.  If the insn does
3332    not satisfy any constraint, return true.  */
3333 static bool
3334 curr_insn_transform (bool check_only_p)
3335 {
3336   int i, j, k;
3337   int n_operands;
3338   int n_alternatives;
3339   int commutative;
3340   signed char goal_alt_matched[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
3341   signed char match_inputs[MAX_RECOG_OPERANDS + 1];
3342   rtx_insn *before, *after;
3343   bool alt_p = false;
3344   /* Flag that the insn has been changed through a transformation.  */
3345   bool change_p;
3346   bool sec_mem_p;
3347 #ifdef SECONDARY_MEMORY_NEEDED
3348   bool use_sec_mem_p;
3349 #endif
3350   int max_regno_before;
3351   int reused_alternative_num;
3352
3353   curr_insn_set = single_set (curr_insn);
3354   if (curr_insn_set != NULL_RTX && simple_move_p ())
3355     return false;
3356
3357   no_input_reloads_p = no_output_reloads_p = false;
3358   goal_alt_number = -1;
3359   change_p = sec_mem_p = false;
3360   /* JUMP_INSNs and CALL_INSNs are not allowed to have any output
3361      reloads; neither are insns that SET cc0.  Insns that use CC0 are
3362      not allowed to have any input reloads.  */
3363   if (JUMP_P (curr_insn) || CALL_P (curr_insn))
3364     no_output_reloads_p = true;
3365
3366 #ifdef HAVE_cc0
3367   if (reg_referenced_p (cc0_rtx, PATTERN (curr_insn)))
3368     no_input_reloads_p = true;
3369   if (reg_set_p (cc0_rtx, PATTERN (curr_insn)))
3370     no_output_reloads_p = true;
3371 #endif
3372
3373   n_operands = curr_static_id->n_operands;
3374   n_alternatives = curr_static_id->n_alternatives;
3375
3376   /* Just return "no reloads" if insn has no operands with
3377      constraints.  */
3378   if (n_operands == 0 || n_alternatives == 0)
3379     return false;
3380
3381   max_regno_before = max_reg_num ();
3382
3383   for (i = 0; i < n_operands; i++)
3384     {
3385       goal_alt_matched[i][0] = -1;
3386       goal_alt_matches[i] = -1;
3387     }
3388
3389   commutative = curr_static_id->commutative;
3390
3391   /* Now see what we need for pseudos that didn't get hard regs or got
3392      the wrong kind of hard reg.  For this, we must consider all the
3393      operands together against the register constraints.  */
3394
3395   best_losers = best_overall = INT_MAX;
3396   best_reload_sum = 0;
3397
3398   curr_swapped = false;
3399   goal_alt_swapped = false;
3400
3401   if (! check_only_p)
3402     /* Make equivalence substitution and memory subreg elimination
3403        before address processing because an address legitimacy can
3404        depend on memory mode.  */
3405     for (i = 0; i < n_operands; i++)
3406       {
3407         rtx op = *curr_id->operand_loc[i];
3408         rtx subst, old = op;
3409         bool op_change_p = false;
3410         
3411         if (GET_CODE (old) == SUBREG)
3412           old = SUBREG_REG (old);
3413         subst = get_equiv_with_elimination (old, curr_insn);
3414         original_subreg_reg_mode[i] = VOIDmode;
3415         if (subst != old)
3416           {
3417             subst = copy_rtx (subst);
3418             lra_assert (REG_P (old));
3419             if (GET_CODE (op) != SUBREG)
3420               *curr_id->operand_loc[i] = subst;
3421             else
3422               {
3423                 SUBREG_REG (op) = subst;
3424                 if (GET_MODE (subst) == VOIDmode)
3425                   original_subreg_reg_mode[i] = GET_MODE (old);
3426               }
3427             if (lra_dump_file != NULL)
3428               {
3429                 fprintf (lra_dump_file,
3430                          "Changing pseudo %d in operand %i of insn %u on equiv ",
3431                          REGNO (old), i, INSN_UID (curr_insn));
3432                 dump_value_slim (lra_dump_file, subst, 1);
3433                 fprintf (lra_dump_file, "\n");
3434               }
3435             op_change_p = change_p = true;
3436           }
3437         if (simplify_operand_subreg (i, GET_MODE (old)) || op_change_p)
3438           {
3439             change_p = true;
3440             lra_update_dup (curr_id, i);
3441           }
3442       }
3443
3444   /* Reload address registers and displacements.  We do it before
3445      finding an alternative because of memory constraints.  */
3446   before = after = NULL;
3447   for (i = 0; i < n_operands; i++)
3448     if (! curr_static_id->operand[i].is_operator
3449         && process_address (i, check_only_p, &before, &after))
3450       {
3451         if (check_only_p)
3452           return true;
3453         change_p = true;
3454         lra_update_dup (curr_id, i);
3455       }
3456   
3457   if (change_p)
3458     /* If we've changed the instruction then any alternative that
3459        we chose previously may no longer be valid.  */
3460     lra_set_used_insn_alternative (curr_insn, -1);
3461
3462   if (! check_only_p && curr_insn_set != NULL_RTX
3463       && check_and_process_move (&change_p, &sec_mem_p))
3464     return change_p;
3465
3466  try_swapped:
3467
3468   reused_alternative_num = check_only_p ? -1 : curr_id->used_insn_alternative;
3469   if (lra_dump_file != NULL && reused_alternative_num >= 0)
3470     fprintf (lra_dump_file, "Reusing alternative %d for insn #%u\n",
3471              reused_alternative_num, INSN_UID (curr_insn));
3472
3473   if (process_alt_operands (reused_alternative_num))
3474     alt_p = true;
3475
3476   if (check_only_p)
3477     return ! alt_p || best_losers != 0;
3478
3479   /* If insn is commutative (it's safe to exchange a certain pair of
3480      operands) then we need to try each alternative twice, the second
3481      time matching those two operands as if we had exchanged them.  To
3482      do this, really exchange them in operands.
3483
3484      If we have just tried the alternatives the second time, return
3485      operands to normal and drop through.  */
3486
3487   if (reused_alternative_num < 0 && commutative >= 0)
3488     {
3489       curr_swapped = !curr_swapped;
3490       if (curr_swapped)
3491         {
3492           swap_operands (commutative);
3493           goto try_swapped;
3494         }
3495       else
3496         swap_operands (commutative);
3497     }
3498
3499   if (! alt_p && ! sec_mem_p)
3500     {
3501       /* No alternative works with reloads??  */
3502       if (INSN_CODE (curr_insn) >= 0)
3503         fatal_insn ("unable to generate reloads for:", curr_insn);
3504       error_for_asm (curr_insn,
3505                      "inconsistent operand constraints in an %<asm%>");
3506       /* Avoid further trouble with this insn.  */
3507       PATTERN (curr_insn) = gen_rtx_USE (VOIDmode, const0_rtx);
3508       lra_invalidate_insn_data (curr_insn);
3509       return true;
3510     }
3511
3512   /* If the best alternative is with operands 1 and 2 swapped, swap
3513      them.  Update the operand numbers of any reloads already
3514      pushed.  */
3515
3516   if (goal_alt_swapped)
3517     {
3518       if (lra_dump_file != NULL)
3519         fprintf (lra_dump_file, "  Commutative operand exchange in insn %u\n",
3520                  INSN_UID (curr_insn));
3521
3522       /* Swap the duplicates too.  */
3523       swap_operands (commutative);
3524       change_p = true;
3525     }
3526
3527 #ifdef SECONDARY_MEMORY_NEEDED
3528   /* Some target macros SECONDARY_MEMORY_NEEDED (e.g. x86) are defined
3529      too conservatively.  So we use the secondary memory only if there
3530      is no any alternative without reloads.  */
3531   use_sec_mem_p = false;
3532   if (! alt_p)
3533     use_sec_mem_p = true;
3534   else if (sec_mem_p)
3535     {
3536       for (i = 0; i < n_operands; i++)
3537         if (! goal_alt_win[i] && ! goal_alt_match_win[i])
3538           break;
3539       use_sec_mem_p = i < n_operands;
3540     }
3541
3542   if (use_sec_mem_p)
3543     {
3544       rtx new_reg, src, dest, rld;
3545       machine_mode sec_mode, rld_mode;
3546
3547       lra_assert (sec_mem_p);
3548       lra_assert (curr_static_id->operand[0].type == OP_OUT
3549                   && curr_static_id->operand[1].type == OP_IN);
3550       dest = *curr_id->operand_loc[0];
3551       src = *curr_id->operand_loc[1];
3552       rld = (GET_MODE_SIZE (GET_MODE (dest)) <= GET_MODE_SIZE (GET_MODE (src))
3553              ? dest : src);
3554       rld_mode = GET_MODE (rld);
3555 #ifdef SECONDARY_MEMORY_NEEDED_MODE
3556       sec_mode = SECONDARY_MEMORY_NEEDED_MODE (rld_mode);
3557 #else
3558       sec_mode = rld_mode;
3559 #endif
3560       new_reg = lra_create_new_reg (sec_mode, NULL_RTX,
3561                                     NO_REGS, "secondary");
3562       /* If the mode is changed, it should be wider.  */
3563       lra_assert (GET_MODE_SIZE (sec_mode) >= GET_MODE_SIZE (rld_mode));
3564       if (sec_mode != rld_mode)
3565         {
3566           /* If the target says specifically to use another mode for
3567              secondary memory moves we can not reuse the original
3568              insn.  */
3569           after = emit_spill_move (false, new_reg, dest);
3570           lra_process_new_insns (curr_insn, NULL, after,
3571                                  "Inserting the sec. move");
3572           /* We may have non null BEFORE here (e.g. after address
3573              processing.  */
3574           push_to_sequence (before);
3575           before = emit_spill_move (true, new_reg, src);
3576           emit_insn (before);
3577           before = get_insns ();
3578           end_sequence ();
3579           lra_process_new_insns (curr_insn, before, NULL, "Changing on");
3580           lra_set_insn_deleted (curr_insn);
3581         }
3582       else if (dest == rld)
3583         {
3584           *curr_id->operand_loc[0] = new_reg;
3585           after = emit_spill_move (false, new_reg, dest);
3586           lra_process_new_insns (curr_insn, NULL, after,
3587                                  "Inserting the sec. move");
3588         }
3589       else
3590         {
3591           *curr_id->operand_loc[1] = new_reg;
3592           /* See comments above.  */
3593           push_to_sequence (before);
3594           before = emit_spill_move (true, new_reg, src);
3595           emit_insn (before);
3596           before = get_insns ();
3597           end_sequence ();
3598           lra_process_new_insns (curr_insn, before, NULL,
3599                                  "Inserting the sec. move");
3600         }
3601       lra_update_insn_regno_info (curr_insn);
3602       return true;
3603     }
3604 #endif
3605
3606   lra_assert (goal_alt_number >= 0);
3607   lra_set_used_insn_alternative (curr_insn, goal_alt_number);
3608
3609   if (lra_dump_file != NULL)
3610     {
3611       const char *p;
3612
3613       fprintf (lra_dump_file, "  Choosing alt %d in insn %u:",
3614                goal_alt_number, INSN_UID (curr_insn));
3615       for (i = 0; i < n_operands; i++)
3616         {
3617           p = (curr_static_id->operand_alternative
3618                [goal_alt_number * n_operands + i].constraint);
3619           if (*p == '\0')
3620             continue;
3621           fprintf (lra_dump_file, "  (%d) ", i);
3622           for (; *p != '\0' && *p != ',' && *p != '#'; p++)
3623             fputc (*p, lra_dump_file);
3624         }
3625       if (INSN_CODE (curr_insn) >= 0
3626           && (p = get_insn_name (INSN_CODE (curr_insn))) != NULL)
3627         fprintf (lra_dump_file, " {%s}", p);
3628       if (curr_id->sp_offset != 0)
3629         fprintf (lra_dump_file, " (sp_off=%" HOST_WIDE_INT_PRINT "d)",
3630                  curr_id->sp_offset);
3631        fprintf (lra_dump_file, "\n");
3632     }
3633
3634   /* Right now, for any pair of operands I and J that are required to
3635      match, with J < I, goal_alt_matches[I] is J.  Add I to
3636      goal_alt_matched[J].  */
3637
3638   for (i = 0; i < n_operands; i++)
3639     if ((j = goal_alt_matches[i]) >= 0)
3640       {
3641         for (k = 0; goal_alt_matched[j][k] >= 0; k++)
3642           ;
3643         /* We allow matching one output operand and several input
3644            operands.  */
3645         lra_assert (k == 0
3646                     || (curr_static_id->operand[j].type == OP_OUT
3647                         && curr_static_id->operand[i].type == OP_IN
3648                         && (curr_static_id->operand
3649                             [goal_alt_matched[j][0]].type == OP_IN)));
3650         goal_alt_matched[j][k] = i;
3651         goal_alt_matched[j][k + 1] = -1;
3652       }
3653
3654   for (i = 0; i < n_operands; i++)
3655     goal_alt_win[i] |= goal_alt_match_win[i];
3656
3657   /* Any constants that aren't allowed and can't be reloaded into
3658      registers are here changed into memory references.  */
3659   for (i = 0; i < n_operands; i++)
3660     if (goal_alt_win[i])
3661       {
3662         int regno;
3663         enum reg_class new_class;
3664         rtx reg = *curr_id->operand_loc[i];
3665
3666         if (GET_CODE (reg) == SUBREG)
3667           reg = SUBREG_REG (reg);
3668
3669         if (REG_P (reg) && (regno = REGNO (reg)) >= FIRST_PSEUDO_REGISTER)
3670           {
3671             bool ok_p = in_class_p (reg, goal_alt[i], &new_class);
3672
3673             if (new_class != NO_REGS && get_reg_class (regno) != new_class)
3674               {
3675                 lra_assert (ok_p);
3676                 lra_change_class (regno, new_class, "      Change to", true);
3677               }
3678           }
3679       }
3680     else
3681       {
3682         const char *constraint;
3683         char c;
3684         rtx op = *curr_id->operand_loc[i];
3685         rtx subreg = NULL_RTX;
3686         machine_mode mode = curr_operand_mode[i];
3687
3688         if (GET_CODE (op) == SUBREG)
3689           {
3690             subreg = op;
3691             op = SUBREG_REG (op);
3692             mode = GET_MODE (op);
3693           }
3694
3695         if (CONST_POOL_OK_P (mode, op)
3696             && ((targetm.preferred_reload_class
3697                  (op, (enum reg_class) goal_alt[i]) == NO_REGS)
3698                 || no_input_reloads_p))
3699           {
3700             rtx tem = force_const_mem (mode, op);
3701
3702             change_p = true;
3703             if (subreg != NULL_RTX)
3704               tem = gen_rtx_SUBREG (mode, tem, SUBREG_BYTE (subreg));
3705
3706             *curr_id->operand_loc[i] = tem;
3707             lra_update_dup (curr_id, i);
3708             process_address (i, false, &before, &after);
3709
3710             /* If the alternative accepts constant pool refs directly
3711                there will be no reload needed at all.  */
3712             if (subreg != NULL_RTX)
3713               continue;
3714             /* Skip alternatives before the one requested.  */
3715             constraint = (curr_static_id->operand_alternative
3716                           [goal_alt_number * n_operands + i].constraint);
3717             for (;