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