OSDN Git Service

* tracer.c (tracer): Don't take FLAGS argument. Assert we are
[pf3gnuchains/gcc-fork.git] / gcc / reg-stack.c
1 /* Register to Stack convert for GNU compiler.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
3    2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5    This file is part of GCC.
6
7    GCC is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2, or (at your option)
10    any later version.
11
12    GCC is distributed in the hope that it will be useful, but WITHOUT
13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
15    License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with GCC; see the file COPYING.  If not, write to the Free
19    Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20    02110-1301, USA.  */
21
22 /* This pass converts stack-like registers from the "flat register
23    file" model that gcc uses, to a stack convention that the 387 uses.
24
25    * The form of the input:
26
27    On input, the function consists of insn that have had their
28    registers fully allocated to a set of "virtual" registers.  Note that
29    the word "virtual" is used differently here than elsewhere in gcc: for
30    each virtual stack reg, there is a hard reg, but the mapping between
31    them is not known until this pass is run.  On output, hard register
32    numbers have been substituted, and various pop and exchange insns have
33    been emitted.  The hard register numbers and the virtual register
34    numbers completely overlap - before this pass, all stack register
35    numbers are virtual, and afterward they are all hard.
36
37    The virtual registers can be manipulated normally by gcc, and their
38    semantics are the same as for normal registers.  After the hard
39    register numbers are substituted, the semantics of an insn containing
40    stack-like regs are not the same as for an insn with normal regs: for
41    instance, it is not safe to delete an insn that appears to be a no-op
42    move.  In general, no insn containing hard regs should be changed
43    after this pass is done.
44
45    * The form of the output:
46
47    After this pass, hard register numbers represent the distance from
48    the current top of stack to the desired register.  A reference to
49    FIRST_STACK_REG references the top of stack, FIRST_STACK_REG + 1,
50    represents the register just below that, and so forth.  Also, REG_DEAD
51    notes indicate whether or not a stack register should be popped.
52
53    A "swap" insn looks like a parallel of two patterns, where each
54    pattern is a SET: one sets A to B, the other B to A.
55
56    A "push" or "load" insn is a SET whose SET_DEST is FIRST_STACK_REG
57    and whose SET_DEST is REG or MEM.  Any other SET_DEST, such as PLUS,
58    will replace the existing stack top, not push a new value.
59
60    A store insn is a SET whose SET_DEST is FIRST_STACK_REG, and whose
61    SET_SRC is REG or MEM.
62
63    The case where the SET_SRC and SET_DEST are both FIRST_STACK_REG
64    appears ambiguous.  As a special case, the presence of a REG_DEAD note
65    for FIRST_STACK_REG differentiates between a load insn and a pop.
66
67    If a REG_DEAD is present, the insn represents a "pop" that discards
68    the top of the register stack.  If there is no REG_DEAD note, then the
69    insn represents a "dup" or a push of the current top of stack onto the
70    stack.
71
72    * Methodology:
73
74    Existing REG_DEAD and REG_UNUSED notes for stack registers are
75    deleted and recreated from scratch.  REG_DEAD is never created for a
76    SET_DEST, only REG_UNUSED.
77
78    * asm_operands:
79
80    There are several rules on the usage of stack-like regs in
81    asm_operands insns.  These rules apply only to the operands that are
82    stack-like regs:
83
84    1. Given a set of input regs that die in an asm_operands, it is
85       necessary to know which are implicitly popped by the asm, and
86       which must be explicitly popped by gcc.
87
88         An input reg that is implicitly popped by the asm must be
89         explicitly clobbered, unless it is constrained to match an
90         output operand.
91
92    2. For any input reg that is implicitly popped by an asm, it is
93       necessary to know how to adjust the stack to compensate for the pop.
94       If any non-popped input is closer to the top of the reg-stack than
95       the implicitly popped reg, it would not be possible to know what the
96       stack looked like - it's not clear how the rest of the stack "slides
97       up".
98
99         All implicitly popped input regs must be closer to the top of
100         the reg-stack than any input that is not implicitly popped.
101
102    3. It is possible that if an input dies in an insn, reload might
103       use the input reg for an output reload.  Consider this example:
104
105                 asm ("foo" : "=t" (a) : "f" (b));
106
107       This asm says that input B is not popped by the asm, and that
108       the asm pushes a result onto the reg-stack, i.e., the stack is one
109       deeper after the asm than it was before.  But, it is possible that
110       reload will think that it can use the same reg for both the input and
111       the output, if input B dies in this insn.
112
113         If any input operand uses the "f" constraint, all output reg
114         constraints must use the "&" earlyclobber.
115
116       The asm above would be written as
117
118                 asm ("foo" : "=&t" (a) : "f" (b));
119
120    4. Some operands need to be in particular places on the stack.  All
121       output operands fall in this category - there is no other way to
122       know which regs the outputs appear in unless the user indicates
123       this in the constraints.
124
125         Output operands must specifically indicate which reg an output
126         appears in after an asm.  "=f" is not allowed: the operand
127         constraints must select a class with a single reg.
128
129    5. Output operands may not be "inserted" between existing stack regs.
130       Since no 387 opcode uses a read/write operand, all output operands
131       are dead before the asm_operands, and are pushed by the asm_operands.
132       It makes no sense to push anywhere but the top of the reg-stack.
133
134         Output operands must start at the top of the reg-stack: output
135         operands may not "skip" a reg.
136
137    6. Some asm statements may need extra stack space for internal
138       calculations.  This can be guaranteed by clobbering stack registers
139       unrelated to the inputs and outputs.
140
141    Here are a couple of reasonable asms to want to write.  This asm
142    takes one input, which is internally popped, and produces two outputs.
143
144         asm ("fsincos" : "=t" (cos), "=u" (sin) : "0" (inp));
145
146    This asm takes two inputs, which are popped by the fyl2xp1 opcode,
147    and replaces them with one output.  The user must code the "st(1)"
148    clobber for reg-stack.c to know that fyl2xp1 pops both inputs.
149
150         asm ("fyl2xp1" : "=t" (result) : "0" (x), "u" (y) : "st(1)");
151
152 */
153 \f
154 #include "config.h"
155 #include "system.h"
156 #include "coretypes.h"
157 #include "tm.h"
158 #include "tree.h"
159 #include "rtl.h"
160 #include "tm_p.h"
161 #include "function.h"
162 #include "insn-config.h"
163 #include "regs.h"
164 #include "hard-reg-set.h"
165 #include "flags.h"
166 #include "toplev.h"
167 #include "recog.h"
168 #include "output.h"
169 #include "basic-block.h"
170 #include "cfglayout.h"
171 #include "varray.h"
172 #include "reload.h"
173 #include "ggc.h"
174 #include "timevar.h"
175 #include "tree-pass.h"
176 #include "target.h"
177 #include "vecprim.h"
178
179 #ifdef STACK_REGS
180
181 /* We use this array to cache info about insns, because otherwise we
182    spend too much time in stack_regs_mentioned_p.
183
184    Indexed by insn UIDs.  A value of zero is uninitialized, one indicates
185    the insn uses stack registers, two indicates the insn does not use
186    stack registers.  */
187 static VEC(char,heap) *stack_regs_mentioned_data;
188
189 #define REG_STACK_SIZE (LAST_STACK_REG - FIRST_STACK_REG + 1)
190
191 int regstack_completed = 0;
192
193 /* This is the basic stack record.  TOP is an index into REG[] such
194    that REG[TOP] is the top of stack.  If TOP is -1 the stack is empty.
195
196    If TOP is -2, REG[] is not yet initialized.  Stack initialization
197    consists of placing each live reg in array `reg' and setting `top'
198    appropriately.
199
200    REG_SET indicates which registers are live.  */
201
202 typedef struct stack_def
203 {
204   int top;                      /* index to top stack element */
205   HARD_REG_SET reg_set;         /* set of live registers */
206   unsigned char reg[REG_STACK_SIZE];/* register - stack mapping */
207 } *stack;
208
209 /* This is used to carry information about basic blocks.  It is
210    attached to the AUX field of the standard CFG block.  */
211
212 typedef struct block_info_def
213 {
214   struct stack_def stack_in;    /* Input stack configuration.  */
215   struct stack_def stack_out;   /* Output stack configuration.  */
216   HARD_REG_SET out_reg_set;     /* Stack regs live on output.  */
217   int done;                     /* True if block already converted.  */
218   int predecessors;             /* Number of predecessors that need
219                                    to be visited.  */
220 } *block_info;
221
222 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
223
224 /* Passed to change_stack to indicate where to emit insns.  */
225 enum emit_where
226 {
227   EMIT_AFTER,
228   EMIT_BEFORE
229 };
230
231 /* The block we're currently working on.  */
232 static basic_block current_block;
233
234 /* In the current_block, whether we're processing the first register
235    stack or call instruction, i.e. the regstack is currently the
236    same as BLOCK_INFO(current_block)->stack_in.  */
237 static bool starting_stack_p;
238
239 /* This is the register file for all register after conversion.  */
240 static rtx
241   FP_mode_reg[LAST_STACK_REG+1-FIRST_STACK_REG][(int) MAX_MACHINE_MODE];
242
243 #define FP_MODE_REG(regno,mode) \
244   (FP_mode_reg[(regno)-FIRST_STACK_REG][(int) (mode)])
245
246 /* Used to initialize uninitialized registers.  */
247 static rtx not_a_num;
248
249 /* Forward declarations */
250
251 static int stack_regs_mentioned_p (rtx pat);
252 static void pop_stack (stack, int);
253 static rtx *get_true_reg (rtx *);
254
255 static int check_asm_stack_operands (rtx);
256 static int get_asm_operand_n_inputs (rtx);
257 static rtx stack_result (tree);
258 static void replace_reg (rtx *, int);
259 static void remove_regno_note (rtx, enum reg_note, unsigned int);
260 static int get_hard_regnum (stack, rtx);
261 static rtx emit_pop_insn (rtx, stack, rtx, enum emit_where);
262 static void swap_to_top(rtx, stack, rtx, rtx);
263 static bool move_for_stack_reg (rtx, stack, rtx);
264 static bool move_nan_for_stack_reg (rtx, stack, rtx);
265 static int swap_rtx_condition_1 (rtx);
266 static int swap_rtx_condition (rtx);
267 static void compare_for_stack_reg (rtx, stack, rtx);
268 static bool subst_stack_regs_pat (rtx, stack, rtx);
269 static void subst_asm_stack_regs (rtx, stack);
270 static bool subst_stack_regs (rtx, stack);
271 static void change_stack (rtx, stack, stack, enum emit_where);
272 static void print_stack (FILE *, stack);
273 static rtx next_flags_user (rtx);
274 \f
275 /* Return nonzero if any stack register is mentioned somewhere within PAT.  */
276
277 static int
278 stack_regs_mentioned_p (rtx pat)
279 {
280   const char *fmt;
281   int i;
282
283   if (STACK_REG_P (pat))
284     return 1;
285
286   fmt = GET_RTX_FORMAT (GET_CODE (pat));
287   for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
288     {
289       if (fmt[i] == 'E')
290         {
291           int j;
292
293           for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
294             if (stack_regs_mentioned_p (XVECEXP (pat, i, j)))
295               return 1;
296         }
297       else if (fmt[i] == 'e' && stack_regs_mentioned_p (XEXP (pat, i)))
298         return 1;
299     }
300
301   return 0;
302 }
303
304 /* Return nonzero if INSN mentions stacked registers, else return zero.  */
305
306 int
307 stack_regs_mentioned (rtx insn)
308 {
309   unsigned int uid, max;
310   int test;
311
312   if (! INSN_P (insn) || !stack_regs_mentioned_data)
313     return 0;
314
315   uid = INSN_UID (insn);
316   max = VEC_length (char, stack_regs_mentioned_data);
317   if (uid >= max)
318     {
319       /* Allocate some extra size to avoid too many reallocs, but
320          do not grow too quickly.  */
321       max = uid + uid / 20 + 1;
322       VEC_safe_grow_cleared (char, heap, stack_regs_mentioned_data, max);
323     }
324
325   test = VEC_index (char, stack_regs_mentioned_data, uid);
326   if (test == 0)
327     {
328       /* This insn has yet to be examined.  Do so now.  */
329       test = stack_regs_mentioned_p (PATTERN (insn)) ? 1 : 2;
330       VEC_replace (char, stack_regs_mentioned_data, uid, test);
331     }
332
333   return test == 1;
334 }
335 \f
336 static rtx ix86_flags_rtx;
337
338 static rtx
339 next_flags_user (rtx insn)
340 {
341   /* Search forward looking for the first use of this value.
342      Stop at block boundaries.  */
343
344   while (insn != BB_END (current_block))
345     {
346       insn = NEXT_INSN (insn);
347
348       if (INSN_P (insn) && reg_mentioned_p (ix86_flags_rtx, PATTERN (insn)))
349         return insn;
350
351       if (CALL_P (insn))
352         return NULL_RTX;
353     }
354   return NULL_RTX;
355 }
356 \f
357 /* Reorganize the stack into ascending numbers, before this insn.  */
358
359 static void
360 straighten_stack (rtx insn, stack regstack)
361 {
362   struct stack_def temp_stack;
363   int top;
364
365   /* If there is only a single register on the stack, then the stack is
366      already in increasing order and no reorganization is needed.
367
368      Similarly if the stack is empty.  */
369   if (regstack->top <= 0)
370     return;
371
372   COPY_HARD_REG_SET (temp_stack.reg_set, regstack->reg_set);
373
374   for (top = temp_stack.top = regstack->top; top >= 0; top--)
375     temp_stack.reg[top] = FIRST_STACK_REG + temp_stack.top - top;
376
377   change_stack (insn, regstack, &temp_stack, EMIT_BEFORE);
378 }
379
380 /* Pop a register from the stack.  */
381
382 static void
383 pop_stack (stack regstack, int regno)
384 {
385   int top = regstack->top;
386
387   CLEAR_HARD_REG_BIT (regstack->reg_set, regno);
388   regstack->top--;
389   /* If regno was not at the top of stack then adjust stack.  */
390   if (regstack->reg [top] != regno)
391     {
392       int i;
393       for (i = regstack->top; i >= 0; i--)
394         if (regstack->reg [i] == regno)
395           {
396             int j;
397             for (j = i; j < top; j++)
398               regstack->reg [j] = regstack->reg [j + 1];
399             break;
400           }
401     }
402 }
403 \f
404 /* Return a pointer to the REG expression within PAT.  If PAT is not a
405    REG, possible enclosed by a conversion rtx, return the inner part of
406    PAT that stopped the search.  */
407
408 static rtx *
409 get_true_reg (rtx *pat)
410 {
411   for (;;)
412     switch (GET_CODE (*pat))
413       {
414       case SUBREG:
415         /* Eliminate FP subregister accesses in favor of the
416            actual FP register in use.  */
417         {
418           rtx subreg;
419           if (FP_REG_P (subreg = SUBREG_REG (*pat)))
420             {
421               int regno_off = subreg_regno_offset (REGNO (subreg),
422                                                    GET_MODE (subreg),
423                                                    SUBREG_BYTE (*pat),
424                                                    GET_MODE (*pat));
425               *pat = FP_MODE_REG (REGNO (subreg) + regno_off,
426                                   GET_MODE (subreg));
427             default:
428               return pat;
429             }
430         }
431       case FLOAT:
432       case FIX:
433       case FLOAT_EXTEND:
434         pat = & XEXP (*pat, 0);
435         break;
436
437       case UNSPEC:
438         if (XINT (*pat, 1) == UNSPEC_TRUNC_NOOP)
439           pat = & XVECEXP (*pat, 0, 0);
440         return pat;
441
442       case FLOAT_TRUNCATE:
443         if (!flag_unsafe_math_optimizations)
444           return pat;
445         pat = & XEXP (*pat, 0);
446         break;
447       }
448 }
449 \f
450 /* Set if we find any malformed asms in a block.  */
451 static bool any_malformed_asm;
452
453 /* There are many rules that an asm statement for stack-like regs must
454    follow.  Those rules are explained at the top of this file: the rule
455    numbers below refer to that explanation.  */
456
457 static int
458 check_asm_stack_operands (rtx insn)
459 {
460   int i;
461   int n_clobbers;
462   int malformed_asm = 0;
463   rtx body = PATTERN (insn);
464
465   char reg_used_as_output[FIRST_PSEUDO_REGISTER];
466   char implicitly_dies[FIRST_PSEUDO_REGISTER];
467   int alt;
468
469   rtx *clobber_reg = 0;
470   int n_inputs, n_outputs;
471
472   /* Find out what the constraints require.  If no constraint
473      alternative matches, this asm is malformed.  */
474   extract_insn (insn);
475   constrain_operands (1);
476   alt = which_alternative;
477
478   preprocess_constraints ();
479
480   n_inputs = get_asm_operand_n_inputs (body);
481   n_outputs = recog_data.n_operands - n_inputs;
482
483   if (alt < 0)
484     {
485       malformed_asm = 1;
486       /* Avoid further trouble with this insn.  */
487       PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
488       return 0;
489     }
490
491   /* Strip SUBREGs here to make the following code simpler.  */
492   for (i = 0; i < recog_data.n_operands; i++)
493     if (GET_CODE (recog_data.operand[i]) == SUBREG
494         && REG_P (SUBREG_REG (recog_data.operand[i])))
495       recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
496
497   /* Set up CLOBBER_REG.  */
498
499   n_clobbers = 0;
500
501   if (GET_CODE (body) == PARALLEL)
502     {
503       clobber_reg = alloca (XVECLEN (body, 0) * sizeof (rtx));
504
505       for (i = 0; i < XVECLEN (body, 0); i++)
506         if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
507           {
508             rtx clobber = XVECEXP (body, 0, i);
509             rtx reg = XEXP (clobber, 0);
510
511             if (GET_CODE (reg) == SUBREG && REG_P (SUBREG_REG (reg)))
512               reg = SUBREG_REG (reg);
513
514             if (STACK_REG_P (reg))
515               {
516                 clobber_reg[n_clobbers] = reg;
517                 n_clobbers++;
518               }
519           }
520     }
521
522   /* Enforce rule #4: Output operands must specifically indicate which
523      reg an output appears in after an asm.  "=f" is not allowed: the
524      operand constraints must select a class with a single reg.
525
526      Also enforce rule #5: Output operands must start at the top of
527      the reg-stack: output operands may not "skip" a reg.  */
528
529   memset (reg_used_as_output, 0, sizeof (reg_used_as_output));
530   for (i = 0; i < n_outputs; i++)
531     if (STACK_REG_P (recog_data.operand[i]))
532       {
533         if (reg_class_size[(int) recog_op_alt[i][alt].cl] != 1)
534           {
535             error_for_asm (insn, "output constraint %d must specify a single register", i);
536             malformed_asm = 1;
537           }
538         else
539           {
540             int j;
541
542             for (j = 0; j < n_clobbers; j++)
543               if (REGNO (recog_data.operand[i]) == REGNO (clobber_reg[j]))
544                 {
545                   error_for_asm (insn, "output constraint %d cannot be specified together with \"%s\" clobber",
546                                  i, reg_names [REGNO (clobber_reg[j])]);
547                   malformed_asm = 1;
548                   break;
549                 }
550             if (j == n_clobbers)
551               reg_used_as_output[REGNO (recog_data.operand[i])] = 1;
552           }
553       }
554
555
556   /* Search for first non-popped reg.  */
557   for (i = FIRST_STACK_REG; i < LAST_STACK_REG + 1; i++)
558     if (! reg_used_as_output[i])
559       break;
560
561   /* If there are any other popped regs, that's an error.  */
562   for (; i < LAST_STACK_REG + 1; i++)
563     if (reg_used_as_output[i])
564       break;
565
566   if (i != LAST_STACK_REG + 1)
567     {
568       error_for_asm (insn, "output regs must be grouped at top of stack");
569       malformed_asm = 1;
570     }
571
572   /* Enforce rule #2: All implicitly popped input regs must be closer
573      to the top of the reg-stack than any input that is not implicitly
574      popped.  */
575
576   memset (implicitly_dies, 0, sizeof (implicitly_dies));
577   for (i = n_outputs; i < n_outputs + n_inputs; i++)
578     if (STACK_REG_P (recog_data.operand[i]))
579       {
580         /* An input reg is implicitly popped if it is tied to an
581            output, or if there is a CLOBBER for it.  */
582         int j;
583
584         for (j = 0; j < n_clobbers; j++)
585           if (operands_match_p (clobber_reg[j], recog_data.operand[i]))
586             break;
587
588         if (j < n_clobbers || recog_op_alt[i][alt].matches >= 0)
589           implicitly_dies[REGNO (recog_data.operand[i])] = 1;
590       }
591
592   /* Search for first non-popped reg.  */
593   for (i = FIRST_STACK_REG; i < LAST_STACK_REG + 1; i++)
594     if (! implicitly_dies[i])
595       break;
596
597   /* If there are any other popped regs, that's an error.  */
598   for (; i < LAST_STACK_REG + 1; i++)
599     if (implicitly_dies[i])
600       break;
601
602   if (i != LAST_STACK_REG + 1)
603     {
604       error_for_asm (insn,
605                      "implicitly popped regs must be grouped at top of stack");
606       malformed_asm = 1;
607     }
608
609   /* Enforce rule #3: If any input operand uses the "f" constraint, all
610      output constraints must use the "&" earlyclobber.
611
612      ??? Detect this more deterministically by having constrain_asm_operands
613      record any earlyclobber.  */
614
615   for (i = n_outputs; i < n_outputs + n_inputs; i++)
616     if (recog_op_alt[i][alt].matches == -1)
617       {
618         int j;
619
620         for (j = 0; j < n_outputs; j++)
621           if (operands_match_p (recog_data.operand[j], recog_data.operand[i]))
622             {
623               error_for_asm (insn,
624                              "output operand %d must use %<&%> constraint", j);
625               malformed_asm = 1;
626             }
627       }
628
629   if (malformed_asm)
630     {
631       /* Avoid further trouble with this insn.  */
632       PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
633       any_malformed_asm = true;
634       return 0;
635     }
636
637   return 1;
638 }
639 \f
640 /* Calculate the number of inputs and outputs in BODY, an
641    asm_operands.  N_OPERANDS is the total number of operands, and
642    N_INPUTS and N_OUTPUTS are pointers to ints into which the results are
643    placed.  */
644
645 static int
646 get_asm_operand_n_inputs (rtx body)
647 {
648   switch (GET_CODE (body))
649     {
650     case SET:
651       gcc_assert (GET_CODE (SET_SRC (body)) == ASM_OPERANDS);
652       return ASM_OPERANDS_INPUT_LENGTH (SET_SRC (body));
653       
654     case ASM_OPERANDS:
655       return ASM_OPERANDS_INPUT_LENGTH (body);
656       
657     case PARALLEL:
658       return get_asm_operand_n_inputs (XVECEXP (body, 0, 0));
659       
660     default:
661       gcc_unreachable ();
662     }
663 }
664
665 /* If current function returns its result in an fp stack register,
666    return the REG.  Otherwise, return 0.  */
667
668 static rtx
669 stack_result (tree decl)
670 {
671   rtx result;
672
673   /* If the value is supposed to be returned in memory, then clearly
674      it is not returned in a stack register.  */
675   if (aggregate_value_p (DECL_RESULT (decl), decl))
676     return 0;
677
678   result = DECL_RTL_IF_SET (DECL_RESULT (decl));
679   if (result != 0)
680     result = targetm.calls.function_value (TREE_TYPE (DECL_RESULT (decl)),
681                                            decl, true);
682
683   return result != 0 && STACK_REG_P (result) ? result : 0;
684 }
685 \f
686
687 /*
688  * This section deals with stack register substitution, and forms the second
689  * pass over the RTL.
690  */
691
692 /* Replace REG, which is a pointer to a stack reg RTX, with an RTX for
693    the desired hard REGNO.  */
694
695 static void
696 replace_reg (rtx *reg, int regno)
697 {
698   gcc_assert (regno >= FIRST_STACK_REG);
699   gcc_assert (regno <= LAST_STACK_REG);
700   gcc_assert (STACK_REG_P (*reg));
701
702   gcc_assert (SCALAR_FLOAT_MODE_P (GET_MODE (*reg))
703               || GET_MODE_CLASS (GET_MODE (*reg)) == MODE_COMPLEX_FLOAT);
704
705   *reg = FP_MODE_REG (regno, GET_MODE (*reg));
706 }
707
708 /* Remove a note of type NOTE, which must be found, for register
709    number REGNO from INSN.  Remove only one such note.  */
710
711 static void
712 remove_regno_note (rtx insn, enum reg_note note, unsigned int regno)
713 {
714   rtx *note_link, this;
715
716   note_link = &REG_NOTES (insn);
717   for (this = *note_link; this; this = XEXP (this, 1))
718     if (REG_NOTE_KIND (this) == note
719         && REG_P (XEXP (this, 0)) && REGNO (XEXP (this, 0)) == regno)
720       {
721         *note_link = XEXP (this, 1);
722         return;
723       }
724     else
725       note_link = &XEXP (this, 1);
726
727   gcc_unreachable ();
728 }
729
730 /* Find the hard register number of virtual register REG in REGSTACK.
731    The hard register number is relative to the top of the stack.  -1 is
732    returned if the register is not found.  */
733
734 static int
735 get_hard_regnum (stack regstack, rtx reg)
736 {
737   int i;
738
739   gcc_assert (STACK_REG_P (reg));
740
741   for (i = regstack->top; i >= 0; i--)
742     if (regstack->reg[i] == REGNO (reg))
743       break;
744
745   return i >= 0 ? (FIRST_STACK_REG + regstack->top - i) : -1;
746 }
747 \f
748 /* Emit an insn to pop virtual register REG before or after INSN.
749    REGSTACK is the stack state after INSN and is updated to reflect this
750    pop.  WHEN is either emit_insn_before or emit_insn_after.  A pop insn
751    is represented as a SET whose destination is the register to be popped
752    and source is the top of stack.  A death note for the top of stack
753    cases the movdf pattern to pop.  */
754
755 static rtx
756 emit_pop_insn (rtx insn, stack regstack, rtx reg, enum emit_where where)
757 {
758   rtx pop_insn, pop_rtx;
759   int hard_regno;
760
761   /* For complex types take care to pop both halves.  These may survive in
762      CLOBBER and USE expressions.  */
763   if (COMPLEX_MODE_P (GET_MODE (reg)))
764     {
765       rtx reg1 = FP_MODE_REG (REGNO (reg), DFmode);
766       rtx reg2 = FP_MODE_REG (REGNO (reg) + 1, DFmode);
767
768       pop_insn = NULL_RTX;
769       if (get_hard_regnum (regstack, reg1) >= 0)
770         pop_insn = emit_pop_insn (insn, regstack, reg1, where);
771       if (get_hard_regnum (regstack, reg2) >= 0)
772         pop_insn = emit_pop_insn (insn, regstack, reg2, where);
773       gcc_assert (pop_insn);
774       return pop_insn;
775     }
776
777   hard_regno = get_hard_regnum (regstack, reg);
778
779   gcc_assert (hard_regno >= FIRST_STACK_REG);
780
781   pop_rtx = gen_rtx_SET (VOIDmode, FP_MODE_REG (hard_regno, DFmode),
782                          FP_MODE_REG (FIRST_STACK_REG, DFmode));
783
784   if (where == EMIT_AFTER)
785     pop_insn = emit_insn_after (pop_rtx, insn);
786   else
787     pop_insn = emit_insn_before (pop_rtx, insn);
788
789   REG_NOTES (pop_insn)
790     = gen_rtx_EXPR_LIST (REG_DEAD, FP_MODE_REG (FIRST_STACK_REG, DFmode),
791                          REG_NOTES (pop_insn));
792
793   regstack->reg[regstack->top - (hard_regno - FIRST_STACK_REG)]
794     = regstack->reg[regstack->top];
795   regstack->top -= 1;
796   CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (reg));
797
798   return pop_insn;
799 }
800 \f
801 /* Emit an insn before or after INSN to swap virtual register REG with
802    the top of stack.  REGSTACK is the stack state before the swap, and
803    is updated to reflect the swap.  A swap insn is represented as a
804    PARALLEL of two patterns: each pattern moves one reg to the other.
805
806    If REG is already at the top of the stack, no insn is emitted.  */
807
808 static void
809 emit_swap_insn (rtx insn, stack regstack, rtx reg)
810 {
811   int hard_regno;
812   rtx swap_rtx;
813   int tmp, other_reg;           /* swap regno temps */
814   rtx i1;                       /* the stack-reg insn prior to INSN */
815   rtx i1set = NULL_RTX;         /* the SET rtx within I1 */
816
817   hard_regno = get_hard_regnum (regstack, reg);
818
819   if (hard_regno == FIRST_STACK_REG)
820     return;
821   if (hard_regno == -1)
822     {
823       /* Something failed if the register wasn't on the stack.  If we had
824          malformed asms, we zapped the instruction itself, but that didn't
825          produce the same pattern of register sets as before.  To prevent
826          further failure, adjust REGSTACK to include REG at TOP.  */
827       gcc_assert (any_malformed_asm);
828       regstack->reg[++regstack->top] = REGNO (reg);
829       return;
830     }
831   gcc_assert (hard_regno >= FIRST_STACK_REG);
832
833   other_reg = regstack->top - (hard_regno - FIRST_STACK_REG);
834
835   tmp = regstack->reg[other_reg];
836   regstack->reg[other_reg] = regstack->reg[regstack->top];
837   regstack->reg[regstack->top] = tmp;
838
839   /* Find the previous insn involving stack regs, but don't pass a
840      block boundary.  */
841   i1 = NULL;
842   if (current_block && insn != BB_HEAD (current_block))
843     {
844       rtx tmp = PREV_INSN (insn);
845       rtx limit = PREV_INSN (BB_HEAD (current_block));
846       while (tmp != limit)
847         {
848           if (LABEL_P (tmp)
849               || CALL_P (tmp)
850               || NOTE_INSN_BASIC_BLOCK_P (tmp)
851               || (NONJUMP_INSN_P (tmp)
852                   && stack_regs_mentioned (tmp)))
853             {
854               i1 = tmp;
855               break;
856             }
857           tmp = PREV_INSN (tmp);
858         }
859     }
860
861   if (i1 != NULL_RTX
862       && (i1set = single_set (i1)) != NULL_RTX)
863     {
864       rtx i1src = *get_true_reg (&SET_SRC (i1set));
865       rtx i1dest = *get_true_reg (&SET_DEST (i1set));
866
867       /* If the previous register stack push was from the reg we are to
868          swap with, omit the swap.  */
869
870       if (REG_P (i1dest) && REGNO (i1dest) == FIRST_STACK_REG
871           && REG_P (i1src)
872           && REGNO (i1src) == (unsigned) hard_regno - 1
873           && find_regno_note (i1, REG_DEAD, FIRST_STACK_REG) == NULL_RTX)
874         return;
875
876       /* If the previous insn wrote to the reg we are to swap with,
877          omit the swap.  */
878
879       if (REG_P (i1dest) && REGNO (i1dest) == (unsigned) hard_regno
880           && REG_P (i1src) && REGNO (i1src) == FIRST_STACK_REG
881           && find_regno_note (i1, REG_DEAD, FIRST_STACK_REG) == NULL_RTX)
882         return;
883     }
884
885   /* Avoid emitting the swap if this is the first register stack insn
886      of the current_block.  Instead update the current_block's stack_in
887      and let compensate edges take care of this for us.  */
888   if (current_block && starting_stack_p)
889     {
890       BLOCK_INFO (current_block)->stack_in = *regstack;
891       starting_stack_p = false;
892       return;
893     }
894
895   swap_rtx = gen_swapxf (FP_MODE_REG (hard_regno, XFmode),
896                          FP_MODE_REG (FIRST_STACK_REG, XFmode));
897
898   if (i1)
899     emit_insn_after (swap_rtx, i1);
900   else if (current_block)
901     emit_insn_before (swap_rtx, BB_HEAD (current_block));
902   else
903     emit_insn_before (swap_rtx, insn);
904 }
905 \f
906 /* Emit an insns before INSN to swap virtual register SRC1 with
907    the top of stack and virtual register SRC2 with second stack
908    slot. REGSTACK is the stack state before the swaps, and
909    is updated to reflect the swaps.  A swap insn is represented as a
910    PARALLEL of two patterns: each pattern moves one reg to the other.
911
912    If SRC1 and/or SRC2 are already at the right place, no swap insn
913    is emitted.  */
914
915 static void
916 swap_to_top (rtx insn, stack regstack, rtx src1, rtx src2)
917 {
918   struct stack_def temp_stack;
919   int regno, j, k, temp;
920
921   temp_stack = *regstack;
922
923   /* Place operand 1 at the top of stack.  */
924   regno = get_hard_regnum (&temp_stack, src1);
925   gcc_assert (regno >= 0);
926   if (regno != FIRST_STACK_REG)
927     {
928       k = temp_stack.top - (regno - FIRST_STACK_REG);
929       j = temp_stack.top;
930
931       temp = temp_stack.reg[k];
932       temp_stack.reg[k] = temp_stack.reg[j];
933       temp_stack.reg[j] = temp;
934     }
935
936   /* Place operand 2 next on the stack.  */
937   regno = get_hard_regnum (&temp_stack, src2);
938   gcc_assert (regno >= 0);
939   if (regno != FIRST_STACK_REG + 1)
940     {
941       k = temp_stack.top - (regno - FIRST_STACK_REG);
942       j = temp_stack.top - 1;
943
944       temp = temp_stack.reg[k];
945       temp_stack.reg[k] = temp_stack.reg[j];
946       temp_stack.reg[j] = temp;
947     }
948
949   change_stack (insn, regstack, &temp_stack, EMIT_BEFORE);
950 }
951 \f
952 /* Handle a move to or from a stack register in PAT, which is in INSN.
953    REGSTACK is the current stack.  Return whether a control flow insn
954    was deleted in the process.  */
955
956 static bool
957 move_for_stack_reg (rtx insn, stack regstack, rtx pat)
958 {
959   rtx *psrc =  get_true_reg (&SET_SRC (pat));
960   rtx *pdest = get_true_reg (&SET_DEST (pat));
961   rtx src, dest;
962   rtx note;
963   bool control_flow_insn_deleted = false;
964
965   src = *psrc; dest = *pdest;
966
967   if (STACK_REG_P (src) && STACK_REG_P (dest))
968     {
969       /* Write from one stack reg to another.  If SRC dies here, then
970          just change the register mapping and delete the insn.  */
971
972       note = find_regno_note (insn, REG_DEAD, REGNO (src));
973       if (note)
974         {
975           int i;
976
977           /* If this is a no-op move, there must not be a REG_DEAD note.  */
978           gcc_assert (REGNO (src) != REGNO (dest));
979
980           for (i = regstack->top; i >= 0; i--)
981             if (regstack->reg[i] == REGNO (src))
982               break;
983
984           /* The destination must be dead, or life analysis is borked.  */
985           gcc_assert (get_hard_regnum (regstack, dest) < FIRST_STACK_REG);
986
987           /* If the source is not live, this is yet another case of
988              uninitialized variables.  Load up a NaN instead.  */
989           if (i < 0)
990             return move_nan_for_stack_reg (insn, regstack, dest);
991
992           /* It is possible that the dest is unused after this insn.
993              If so, just pop the src.  */
994
995           if (find_regno_note (insn, REG_UNUSED, REGNO (dest)))
996             emit_pop_insn (insn, regstack, src, EMIT_AFTER);
997           else
998             {
999               regstack->reg[i] = REGNO (dest);
1000               SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1001               CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (src));
1002             }
1003
1004           control_flow_insn_deleted |= control_flow_insn_p (insn);
1005           delete_insn (insn);
1006           return control_flow_insn_deleted;
1007         }
1008
1009       /* The source reg does not die.  */
1010
1011       /* If this appears to be a no-op move, delete it, or else it
1012          will confuse the machine description output patterns. But if
1013          it is REG_UNUSED, we must pop the reg now, as per-insn processing
1014          for REG_UNUSED will not work for deleted insns.  */
1015
1016       if (REGNO (src) == REGNO (dest))
1017         {
1018           if (find_regno_note (insn, REG_UNUSED, REGNO (dest)))
1019             emit_pop_insn (insn, regstack, dest, EMIT_AFTER);
1020
1021           control_flow_insn_deleted |= control_flow_insn_p (insn);
1022           delete_insn (insn);
1023           return control_flow_insn_deleted;
1024         }
1025
1026       /* The destination ought to be dead.  */
1027       gcc_assert (get_hard_regnum (regstack, dest) < FIRST_STACK_REG);
1028
1029       replace_reg (psrc, get_hard_regnum (regstack, src));
1030
1031       regstack->reg[++regstack->top] = REGNO (dest);
1032       SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1033       replace_reg (pdest, FIRST_STACK_REG);
1034     }
1035   else if (STACK_REG_P (src))
1036     {
1037       /* Save from a stack reg to MEM, or possibly integer reg.  Since
1038          only top of stack may be saved, emit an exchange first if
1039          needs be.  */
1040
1041       emit_swap_insn (insn, regstack, src);
1042
1043       note = find_regno_note (insn, REG_DEAD, REGNO (src));
1044       if (note)
1045         {
1046           replace_reg (&XEXP (note, 0), FIRST_STACK_REG);
1047           regstack->top--;
1048           CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (src));
1049         }
1050       else if ((GET_MODE (src) == XFmode)
1051                && regstack->top < REG_STACK_SIZE - 1)
1052         {
1053           /* A 387 cannot write an XFmode value to a MEM without
1054              clobbering the source reg.  The output code can handle
1055              this by reading back the value from the MEM.
1056              But it is more efficient to use a temp register if one is
1057              available.  Push the source value here if the register
1058              stack is not full, and then write the value to memory via
1059              a pop.  */
1060           rtx push_rtx;
1061           rtx top_stack_reg = FP_MODE_REG (FIRST_STACK_REG, GET_MODE (src));
1062
1063           push_rtx = gen_movxf (top_stack_reg, top_stack_reg);
1064           emit_insn_before (push_rtx, insn);
1065           REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_DEAD, top_stack_reg,
1066                                                 REG_NOTES (insn));
1067         }
1068
1069       replace_reg (psrc, FIRST_STACK_REG);
1070     }
1071   else
1072     {
1073       rtx pat = PATTERN (insn);
1074
1075       gcc_assert (STACK_REG_P (dest));
1076
1077       /* Load from MEM, or possibly integer REG or constant, into the
1078          stack regs.  The actual target is always the top of the
1079          stack. The stack mapping is changed to reflect that DEST is
1080          now at top of stack.  */
1081
1082       /* The destination ought to be dead.  However, there is a
1083          special case with i387 UNSPEC_TAN, where destination is live
1084          (an argument to fptan) but inherent load of 1.0 is modelled
1085          as a load from a constant.  */
1086       if (! (GET_CODE (pat) == PARALLEL
1087              && XVECLEN (pat, 0) == 2
1088              && GET_CODE (XVECEXP (pat, 0, 1)) == SET
1089              && GET_CODE (SET_SRC (XVECEXP (pat, 0, 1))) == UNSPEC
1090              && XINT (SET_SRC (XVECEXP (pat, 0, 1)), 1) == UNSPEC_TAN))
1091         gcc_assert (get_hard_regnum (regstack, dest) < FIRST_STACK_REG);
1092
1093       gcc_assert (regstack->top < REG_STACK_SIZE);
1094
1095       regstack->reg[++regstack->top] = REGNO (dest);
1096       SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1097       replace_reg (pdest, FIRST_STACK_REG);
1098     }
1099
1100   return control_flow_insn_deleted;
1101 }
1102
1103 /* A helper function which replaces INSN with a pattern that loads up
1104    a NaN into DEST, then invokes move_for_stack_reg.  */
1105
1106 static bool
1107 move_nan_for_stack_reg (rtx insn, stack regstack, rtx dest)
1108 {
1109   rtx pat;
1110
1111   dest = FP_MODE_REG (REGNO (dest), SFmode);
1112   pat = gen_rtx_SET (VOIDmode, dest, not_a_num);
1113   PATTERN (insn) = pat;
1114   INSN_CODE (insn) = -1;
1115
1116   return move_for_stack_reg (insn, regstack, pat);
1117 }
1118 \f
1119 /* Swap the condition on a branch, if there is one.  Return true if we
1120    found a condition to swap.  False if the condition was not used as
1121    such.  */
1122
1123 static int
1124 swap_rtx_condition_1 (rtx pat)
1125 {
1126   const char *fmt;
1127   int i, r = 0;
1128
1129   if (COMPARISON_P (pat))
1130     {
1131       PUT_CODE (pat, swap_condition (GET_CODE (pat)));
1132       r = 1;
1133     }
1134   else
1135     {
1136       fmt = GET_RTX_FORMAT (GET_CODE (pat));
1137       for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
1138         {
1139           if (fmt[i] == 'E')
1140             {
1141               int j;
1142
1143               for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
1144                 r |= swap_rtx_condition_1 (XVECEXP (pat, i, j));
1145             }
1146           else if (fmt[i] == 'e')
1147             r |= swap_rtx_condition_1 (XEXP (pat, i));
1148         }
1149     }
1150
1151   return r;
1152 }
1153
1154 static int
1155 swap_rtx_condition (rtx insn)
1156 {
1157   rtx pat = PATTERN (insn);
1158
1159   /* We're looking for a single set to cc0 or an HImode temporary.  */
1160
1161   if (GET_CODE (pat) == SET
1162       && REG_P (SET_DEST (pat))
1163       && REGNO (SET_DEST (pat)) == FLAGS_REG)
1164     {
1165       insn = next_flags_user (insn);
1166       if (insn == NULL_RTX)
1167         return 0;
1168       pat = PATTERN (insn);
1169     }
1170
1171   /* See if this is, or ends in, a fnstsw.  If so, we're not doing anything
1172      with the cc value right now.  We may be able to search for one
1173      though.  */
1174
1175   if (GET_CODE (pat) == SET
1176       && GET_CODE (SET_SRC (pat)) == UNSPEC
1177       && XINT (SET_SRC (pat), 1) == UNSPEC_FNSTSW)
1178     {
1179       rtx dest = SET_DEST (pat);
1180
1181       /* Search forward looking for the first use of this value.
1182          Stop at block boundaries.  */
1183       while (insn != BB_END (current_block))
1184         {
1185           insn = NEXT_INSN (insn);
1186           if (INSN_P (insn) && reg_mentioned_p (dest, insn))
1187             break;
1188           if (CALL_P (insn))
1189             return 0;
1190         }
1191
1192       /* We haven't found it.  */
1193       if (insn == BB_END (current_block))
1194         return 0;
1195
1196       /* So we've found the insn using this value.  If it is anything
1197          other than sahf or the value does not die (meaning we'd have
1198          to search further), then we must give up.  */
1199       pat = PATTERN (insn);
1200       if (GET_CODE (pat) != SET
1201           || GET_CODE (SET_SRC (pat)) != UNSPEC
1202           || XINT (SET_SRC (pat), 1) != UNSPEC_SAHF
1203           || ! dead_or_set_p (insn, dest))
1204         return 0;
1205
1206       /* Now we are prepared to handle this as a normal cc0 setter.  */
1207       insn = next_flags_user (insn);
1208       if (insn == NULL_RTX)
1209         return 0;
1210       pat = PATTERN (insn);
1211     }
1212
1213   if (swap_rtx_condition_1 (pat))
1214     {
1215       int fail = 0;
1216       INSN_CODE (insn) = -1;
1217       if (recog_memoized (insn) == -1)
1218         fail = 1;
1219       /* In case the flags don't die here, recurse to try fix
1220          following user too.  */
1221       else if (! dead_or_set_p (insn, ix86_flags_rtx))
1222         {
1223           insn = next_flags_user (insn);
1224           if (!insn || !swap_rtx_condition (insn))
1225             fail = 1;
1226         }
1227       if (fail)
1228         {
1229           swap_rtx_condition_1 (pat);
1230           return 0;
1231         }
1232       return 1;
1233     }
1234   return 0;
1235 }
1236
1237 /* Handle a comparison.  Special care needs to be taken to avoid
1238    causing comparisons that a 387 cannot do correctly, such as EQ.
1239
1240    Also, a pop insn may need to be emitted.  The 387 does have an
1241    `fcompp' insn that can pop two regs, but it is sometimes too expensive
1242    to do this - a `fcomp' followed by a `fstpl %st(0)' may be easier to
1243    set up.  */
1244
1245 static void
1246 compare_for_stack_reg (rtx insn, stack regstack, rtx pat_src)
1247 {
1248   rtx *src1, *src2;
1249   rtx src1_note, src2_note;
1250
1251   src1 = get_true_reg (&XEXP (pat_src, 0));
1252   src2 = get_true_reg (&XEXP (pat_src, 1));
1253
1254   /* ??? If fxch turns out to be cheaper than fstp, give priority to
1255      registers that die in this insn - move those to stack top first.  */
1256   if ((! STACK_REG_P (*src1)
1257        || (STACK_REG_P (*src2)
1258            && get_hard_regnum (regstack, *src2) == FIRST_STACK_REG))
1259       && swap_rtx_condition (insn))
1260     {
1261       rtx temp;
1262       temp = XEXP (pat_src, 0);
1263       XEXP (pat_src, 0) = XEXP (pat_src, 1);
1264       XEXP (pat_src, 1) = temp;
1265
1266       src1 = get_true_reg (&XEXP (pat_src, 0));
1267       src2 = get_true_reg (&XEXP (pat_src, 1));
1268
1269       INSN_CODE (insn) = -1;
1270     }
1271
1272   /* We will fix any death note later.  */
1273
1274   src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1275
1276   if (STACK_REG_P (*src2))
1277     src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
1278   else
1279     src2_note = NULL_RTX;
1280
1281   emit_swap_insn (insn, regstack, *src1);
1282
1283   replace_reg (src1, FIRST_STACK_REG);
1284
1285   if (STACK_REG_P (*src2))
1286     replace_reg (src2, get_hard_regnum (regstack, *src2));
1287
1288   if (src1_note)
1289     {
1290       pop_stack (regstack, REGNO (XEXP (src1_note, 0)));
1291       replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
1292     }
1293
1294   /* If the second operand dies, handle that.  But if the operands are
1295      the same stack register, don't bother, because only one death is
1296      needed, and it was just handled.  */
1297
1298   if (src2_note
1299       && ! (STACK_REG_P (*src1) && STACK_REG_P (*src2)
1300             && REGNO (*src1) == REGNO (*src2)))
1301     {
1302       /* As a special case, two regs may die in this insn if src2 is
1303          next to top of stack and the top of stack also dies.  Since
1304          we have already popped src1, "next to top of stack" is really
1305          at top (FIRST_STACK_REG) now.  */
1306
1307       if (get_hard_regnum (regstack, XEXP (src2_note, 0)) == FIRST_STACK_REG
1308           && src1_note)
1309         {
1310           pop_stack (regstack, REGNO (XEXP (src2_note, 0)));
1311           replace_reg (&XEXP (src2_note, 0), FIRST_STACK_REG + 1);
1312         }
1313       else
1314         {
1315           /* The 386 can only represent death of the first operand in
1316              the case handled above.  In all other cases, emit a separate
1317              pop and remove the death note from here.  */
1318
1319           /* link_cc0_insns (insn); */
1320
1321           remove_regno_note (insn, REG_DEAD, REGNO (XEXP (src2_note, 0)));
1322
1323           emit_pop_insn (insn, regstack, XEXP (src2_note, 0),
1324                          EMIT_AFTER);
1325         }
1326     }
1327 }
1328 \f
1329 /* Substitute new registers in PAT, which is part of INSN.  REGSTACK
1330    is the current register layout.  Return whether a control flow insn
1331    was deleted in the process.  */
1332
1333 static bool
1334 subst_stack_regs_pat (rtx insn, stack regstack, rtx pat)
1335 {
1336   rtx *dest, *src;
1337   bool control_flow_insn_deleted = false;
1338
1339   switch (GET_CODE (pat))
1340     {
1341     case USE:
1342       /* Deaths in USE insns can happen in non optimizing compilation.
1343          Handle them by popping the dying register.  */
1344       src = get_true_reg (&XEXP (pat, 0));
1345       if (STACK_REG_P (*src)
1346           && find_regno_note (insn, REG_DEAD, REGNO (*src)))
1347         {
1348           emit_pop_insn (insn, regstack, *src, EMIT_AFTER);
1349           return control_flow_insn_deleted;
1350         }
1351       /* ??? Uninitialized USE should not happen.  */
1352       else
1353         gcc_assert (get_hard_regnum (regstack, *src) != -1);
1354       break;
1355
1356     case CLOBBER:
1357       {
1358         rtx note;
1359
1360         dest = get_true_reg (&XEXP (pat, 0));
1361         if (STACK_REG_P (*dest))
1362           {
1363             note = find_reg_note (insn, REG_DEAD, *dest);
1364
1365             if (pat != PATTERN (insn))
1366               {
1367                 /* The fix_truncdi_1 pattern wants to be able to allocate
1368                    its own scratch register.  It does this by clobbering
1369                    an fp reg so that it is assured of an empty reg-stack
1370                    register.  If the register is live, kill it now.
1371                    Remove the DEAD/UNUSED note so we don't try to kill it
1372                    later too.  */
1373
1374                 if (note)
1375                   emit_pop_insn (insn, regstack, *dest, EMIT_BEFORE);
1376                 else
1377                   {
1378                     note = find_reg_note (insn, REG_UNUSED, *dest);
1379                     gcc_assert (note);
1380                   }
1381                 remove_note (insn, note);
1382                 replace_reg (dest, FIRST_STACK_REG + 1);
1383               }
1384             else
1385               {
1386                 /* A top-level clobber with no REG_DEAD, and no hard-regnum
1387                    indicates an uninitialized value.  Because reload removed
1388                    all other clobbers, this must be due to a function
1389                    returning without a value.  Load up a NaN.  */
1390
1391                 if (!note)
1392                   {
1393                     rtx t = *dest;
1394                     if (COMPLEX_MODE_P (GET_MODE (t)))
1395                       {
1396                         rtx u = FP_MODE_REG (REGNO (t) + 1, SFmode);
1397                         if (get_hard_regnum (regstack, u) == -1)
1398                           {
1399                             rtx pat2 = gen_rtx_CLOBBER (VOIDmode, u);
1400                             rtx insn2 = emit_insn_before (pat2, insn);
1401                             control_flow_insn_deleted
1402                               |= move_nan_for_stack_reg (insn2, regstack, u);
1403                           }
1404                       }
1405                     if (get_hard_regnum (regstack, t) == -1)
1406                       control_flow_insn_deleted
1407                         |= move_nan_for_stack_reg (insn, regstack, t);
1408                   }
1409               }
1410           }
1411         break;
1412       }
1413
1414     case SET:
1415       {
1416         rtx *src1 = (rtx *) 0, *src2;
1417         rtx src1_note, src2_note;
1418         rtx pat_src;
1419
1420         dest = get_true_reg (&SET_DEST (pat));
1421         src  = get_true_reg (&SET_SRC (pat));
1422         pat_src = SET_SRC (pat);
1423
1424         /* See if this is a `movM' pattern, and handle elsewhere if so.  */
1425         if (STACK_REG_P (*src)
1426             || (STACK_REG_P (*dest)
1427                 && (REG_P (*src) || MEM_P (*src)
1428                     || GET_CODE (*src) == CONST_DOUBLE)))
1429           {
1430             control_flow_insn_deleted |= move_for_stack_reg (insn, regstack, pat);
1431             break;
1432           }
1433
1434         switch (GET_CODE (pat_src))
1435           {
1436           case COMPARE:
1437             compare_for_stack_reg (insn, regstack, pat_src);
1438             break;
1439
1440           case CALL:
1441             {
1442               int count;
1443               for (count = hard_regno_nregs[REGNO (*dest)][GET_MODE (*dest)];
1444                    --count >= 0;)
1445                 {
1446                   regstack->reg[++regstack->top] = REGNO (*dest) + count;
1447                   SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest) + count);
1448                 }
1449             }
1450             replace_reg (dest, FIRST_STACK_REG);
1451             break;
1452
1453           case REG:
1454             /* This is a `tstM2' case.  */
1455             gcc_assert (*dest == cc0_rtx);
1456             src1 = src;
1457
1458             /* Fall through.  */
1459
1460           case FLOAT_TRUNCATE:
1461           case SQRT:
1462           case ABS:
1463           case NEG:
1464             /* These insns only operate on the top of the stack. DEST might
1465                be cc0_rtx if we're processing a tstM pattern. Also, it's
1466                possible that the tstM case results in a REG_DEAD note on the
1467                source.  */
1468
1469             if (src1 == 0)
1470               src1 = get_true_reg (&XEXP (pat_src, 0));
1471
1472             emit_swap_insn (insn, regstack, *src1);
1473
1474             src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1475
1476             if (STACK_REG_P (*dest))
1477               replace_reg (dest, FIRST_STACK_REG);
1478
1479             if (src1_note)
1480               {
1481                 replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
1482                 regstack->top--;
1483                 CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (*src1));
1484               }
1485
1486             replace_reg (src1, FIRST_STACK_REG);
1487             break;
1488
1489           case MINUS:
1490           case DIV:
1491             /* On i386, reversed forms of subM3 and divM3 exist for
1492                MODE_FLOAT, so the same code that works for addM3 and mulM3
1493                can be used.  */
1494           case MULT:
1495           case PLUS:
1496             /* These insns can accept the top of stack as a destination
1497                from a stack reg or mem, or can use the top of stack as a
1498                source and some other stack register (possibly top of stack)
1499                as a destination.  */
1500
1501             src1 = get_true_reg (&XEXP (pat_src, 0));
1502             src2 = get_true_reg (&XEXP (pat_src, 1));
1503
1504             /* We will fix any death note later.  */
1505
1506             if (STACK_REG_P (*src1))
1507               src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1508             else
1509               src1_note = NULL_RTX;
1510             if (STACK_REG_P (*src2))
1511               src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
1512             else
1513               src2_note = NULL_RTX;
1514
1515             /* If either operand is not a stack register, then the dest
1516                must be top of stack.  */
1517
1518             if (! STACK_REG_P (*src1) || ! STACK_REG_P (*src2))
1519               emit_swap_insn (insn, regstack, *dest);
1520             else
1521               {
1522                 /* Both operands are REG.  If neither operand is already
1523                    at the top of stack, choose to make the one that is the dest
1524                    the new top of stack.  */
1525
1526                 int src1_hard_regnum, src2_hard_regnum;
1527
1528                 src1_hard_regnum = get_hard_regnum (regstack, *src1);
1529                 src2_hard_regnum = get_hard_regnum (regstack, *src2);
1530                 gcc_assert (src1_hard_regnum != -1);
1531                 gcc_assert (src2_hard_regnum != -1);
1532
1533                 if (src1_hard_regnum != FIRST_STACK_REG
1534                     && src2_hard_regnum != FIRST_STACK_REG)
1535                   emit_swap_insn (insn, regstack, *dest);
1536               }
1537
1538             if (STACK_REG_P (*src1))
1539               replace_reg (src1, get_hard_regnum (regstack, *src1));
1540             if (STACK_REG_P (*src2))
1541               replace_reg (src2, get_hard_regnum (regstack, *src2));
1542
1543             if (src1_note)
1544               {
1545                 rtx src1_reg = XEXP (src1_note, 0);
1546
1547                 /* If the register that dies is at the top of stack, then
1548                    the destination is somewhere else - merely substitute it.
1549                    But if the reg that dies is not at top of stack, then
1550                    move the top of stack to the dead reg, as though we had
1551                    done the insn and then a store-with-pop.  */
1552
1553                 if (REGNO (src1_reg) == regstack->reg[regstack->top])
1554                   {
1555                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1556                     replace_reg (dest, get_hard_regnum (regstack, *dest));
1557                   }
1558                 else
1559                   {
1560                     int regno = get_hard_regnum (regstack, src1_reg);
1561
1562                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1563                     replace_reg (dest, regno);
1564
1565                     regstack->reg[regstack->top - (regno - FIRST_STACK_REG)]
1566                       = regstack->reg[regstack->top];
1567                   }
1568
1569                 CLEAR_HARD_REG_BIT (regstack->reg_set,
1570                                     REGNO (XEXP (src1_note, 0)));
1571                 replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
1572                 regstack->top--;
1573               }
1574             else if (src2_note)
1575               {
1576                 rtx src2_reg = XEXP (src2_note, 0);
1577                 if (REGNO (src2_reg) == regstack->reg[regstack->top])
1578                   {
1579                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1580                     replace_reg (dest, get_hard_regnum (regstack, *dest));
1581                   }
1582                 else
1583                   {
1584                     int regno = get_hard_regnum (regstack, src2_reg);
1585
1586                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1587                     replace_reg (dest, regno);
1588
1589                     regstack->reg[regstack->top - (regno - FIRST_STACK_REG)]
1590                       = regstack->reg[regstack->top];
1591                   }
1592
1593                 CLEAR_HARD_REG_BIT (regstack->reg_set,
1594                                     REGNO (XEXP (src2_note, 0)));
1595                 replace_reg (&XEXP (src2_note, 0), FIRST_STACK_REG);
1596                 regstack->top--;
1597               }
1598             else
1599               {
1600                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1601                 replace_reg (dest, get_hard_regnum (regstack, *dest));
1602               }
1603
1604             /* Keep operand 1 matching with destination.  */
1605             if (COMMUTATIVE_ARITH_P (pat_src)
1606                 && REG_P (*src1) && REG_P (*src2)
1607                 && REGNO (*src1) != REGNO (*dest))
1608              {
1609                 int tmp = REGNO (*src1);
1610                 replace_reg (src1, REGNO (*src2));
1611                 replace_reg (src2, tmp);
1612              }
1613             break;
1614
1615           case UNSPEC:
1616             switch (XINT (pat_src, 1))
1617               {
1618               case UNSPEC_FIST:
1619
1620               case UNSPEC_FIST_FLOOR:
1621               case UNSPEC_FIST_CEIL:
1622
1623                 /* These insns only operate on the top of the stack.  */
1624
1625                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1626                 emit_swap_insn (insn, regstack, *src1);
1627
1628                 src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1629
1630                 if (STACK_REG_P (*dest))
1631                   replace_reg (dest, FIRST_STACK_REG);
1632
1633                 if (src1_note)
1634                   {
1635                     replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
1636                     regstack->top--;
1637                     CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (*src1));
1638                   }
1639
1640                 replace_reg (src1, FIRST_STACK_REG);
1641                 break;
1642
1643               case UNSPEC_FXAM:
1644
1645                 /* This insn only operate on the top of the stack.  */
1646
1647                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1648                 emit_swap_insn (insn, regstack, *src1);
1649
1650                 src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1651
1652                 replace_reg (src1, FIRST_STACK_REG);
1653
1654                 if (src1_note)
1655                   {
1656                     remove_regno_note (insn, REG_DEAD,
1657                                        REGNO (XEXP (src1_note, 0)));
1658                     emit_pop_insn (insn, regstack, XEXP (src1_note, 0),
1659                                    EMIT_AFTER);
1660                   }
1661
1662                 break;
1663
1664               case UNSPEC_SIN:
1665               case UNSPEC_COS:
1666               case UNSPEC_FRNDINT:
1667               case UNSPEC_F2XM1:
1668
1669               case UNSPEC_FRNDINT_FLOOR:
1670               case UNSPEC_FRNDINT_CEIL:
1671               case UNSPEC_FRNDINT_TRUNC:
1672               case UNSPEC_FRNDINT_MASK_PM:
1673
1674                 /* Above insns operate on the top of the stack.  */
1675
1676               case UNSPEC_SINCOS_COS:
1677               case UNSPEC_XTRACT_FRACT:
1678
1679                 /* Above insns operate on the top two stack slots,
1680                    first part of one input, double output insn.  */
1681
1682                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1683
1684                 emit_swap_insn (insn, regstack, *src1);
1685
1686                 /* Input should never die, it is replaced with output.  */
1687                 src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1688                 gcc_assert (!src1_note);
1689
1690                 if (STACK_REG_P (*dest))
1691                   replace_reg (dest, FIRST_STACK_REG);
1692
1693                 replace_reg (src1, FIRST_STACK_REG);
1694                 break;
1695
1696               case UNSPEC_SINCOS_SIN:
1697               case UNSPEC_XTRACT_EXP:
1698
1699                 /* These insns operate on the top two stack slots,
1700                    second part of one input, double output insn.  */
1701
1702                 regstack->top++;
1703                 /* FALLTHRU */
1704
1705               case UNSPEC_TAN:
1706
1707                 /* For UNSPEC_TAN, regstack->top is already increased
1708                    by inherent load of constant 1.0.  */
1709
1710                 /* Output value is generated in the second stack slot.
1711                    Move current value from second slot to the top.  */
1712                 regstack->reg[regstack->top]
1713                   = regstack->reg[regstack->top - 1];
1714
1715                 gcc_assert (STACK_REG_P (*dest));
1716
1717                 regstack->reg[regstack->top - 1] = REGNO (*dest);
1718                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1719                 replace_reg (dest, FIRST_STACK_REG + 1);
1720
1721                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1722
1723                 replace_reg (src1, FIRST_STACK_REG);
1724                 break;
1725
1726               case UNSPEC_FPATAN:
1727               case UNSPEC_FYL2X:
1728               case UNSPEC_FYL2XP1:
1729                 /* These insns operate on the top two stack slots.  */
1730
1731                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1732                 src2 = get_true_reg (&XVECEXP (pat_src, 0, 1));
1733
1734                 src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1735                 src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
1736
1737                 swap_to_top (insn, regstack, *src1, *src2);
1738
1739                 replace_reg (src1, FIRST_STACK_REG);
1740                 replace_reg (src2, FIRST_STACK_REG + 1);
1741
1742                 if (src1_note)
1743                   replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
1744                 if (src2_note)
1745                   replace_reg (&XEXP (src2_note, 0), FIRST_STACK_REG + 1);
1746
1747                 /* Pop both input operands from the stack.  */
1748                 CLEAR_HARD_REG_BIT (regstack->reg_set,
1749                                     regstack->reg[regstack->top]);
1750                 CLEAR_HARD_REG_BIT (regstack->reg_set,
1751                                     regstack->reg[regstack->top - 1]);
1752                 regstack->top -= 2;
1753
1754                 /* Push the result back onto the stack.  */
1755                 regstack->reg[++regstack->top] = REGNO (*dest);
1756                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1757                 replace_reg (dest, FIRST_STACK_REG);
1758                 break;
1759
1760               case UNSPEC_FSCALE_FRACT:
1761               case UNSPEC_FPREM_F:
1762               case UNSPEC_FPREM1_F:
1763                 /* These insns operate on the top two stack slots,
1764                    first part of double input, double output insn.  */
1765
1766                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1767                 src2 = get_true_reg (&XVECEXP (pat_src, 0, 1));
1768
1769                 src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1770                 src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
1771
1772                 /* Inputs should never die, they are
1773                    replaced with outputs.  */
1774                 gcc_assert (!src1_note);
1775                 gcc_assert (!src2_note);
1776
1777                 swap_to_top (insn, regstack, *src1, *src2);
1778
1779                 /* Push the result back onto stack. Empty stack slot
1780                    will be filled in second part of insn.  */
1781                 if (STACK_REG_P (*dest))
1782                   {
1783                     regstack->reg[regstack->top] = REGNO (*dest);
1784                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1785                     replace_reg (dest, FIRST_STACK_REG);
1786                   }
1787
1788                 replace_reg (src1, FIRST_STACK_REG);
1789                 replace_reg (src2, FIRST_STACK_REG + 1);
1790                 break;
1791
1792               case UNSPEC_FSCALE_EXP:
1793               case UNSPEC_FPREM_U:
1794               case UNSPEC_FPREM1_U:
1795                 /* These insns operate on the top two stack slots,
1796                    second part of double input, double output insn.  */
1797
1798                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1799                 src2 = get_true_reg (&XVECEXP (pat_src, 0, 1));
1800
1801                 /* Push the result back onto stack. Fill empty slot from
1802                    first part of insn and fix top of stack pointer.  */
1803                 if (STACK_REG_P (*dest))
1804                   {
1805                     regstack->reg[regstack->top - 1] = REGNO (*dest);
1806                     SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1807                     replace_reg (dest, FIRST_STACK_REG + 1);
1808                   }
1809
1810                 replace_reg (src1, FIRST_STACK_REG);
1811                 replace_reg (src2, FIRST_STACK_REG + 1);
1812                 break;
1813
1814               case UNSPEC_C2_FLAG:
1815                 /* This insn operates on the top two stack slots,
1816                    third part of C2 setting double input insn.  */
1817
1818                 src1 = get_true_reg (&XVECEXP (pat_src, 0, 0));
1819                 src2 = get_true_reg (&XVECEXP (pat_src, 0, 1));
1820
1821                 replace_reg (src1, FIRST_STACK_REG);
1822                 replace_reg (src2, FIRST_STACK_REG + 1);
1823                 break;
1824
1825               case UNSPEC_SAHF:
1826                 /* (unspec [(unspec [(compare)] UNSPEC_FNSTSW)] UNSPEC_SAHF)
1827                    The combination matches the PPRO fcomi instruction.  */
1828
1829                 pat_src = XVECEXP (pat_src, 0, 0);
1830                 gcc_assert (GET_CODE (pat_src) == UNSPEC);
1831                 gcc_assert (XINT (pat_src, 1) == UNSPEC_FNSTSW);
1832                 /* Fall through.  */
1833
1834               case UNSPEC_FNSTSW:
1835                 /* Combined fcomp+fnstsw generated for doing well with
1836                    CSE.  When optimizing this would have been broken
1837                    up before now.  */
1838
1839                 pat_src = XVECEXP (pat_src, 0, 0);
1840                 gcc_assert (GET_CODE (pat_src) == COMPARE);
1841
1842                 compare_for_stack_reg (insn, regstack, pat_src);
1843                 break;
1844
1845               default:
1846                 gcc_unreachable ();
1847               }
1848             break;
1849
1850           case IF_THEN_ELSE:
1851             /* This insn requires the top of stack to be the destination.  */
1852
1853             src1 = get_true_reg (&XEXP (pat_src, 1));
1854             src2 = get_true_reg (&XEXP (pat_src, 2));
1855
1856             src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
1857             src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
1858
1859             /* If the comparison operator is an FP comparison operator,
1860                it is handled correctly by compare_for_stack_reg () who
1861                will move the destination to the top of stack. But if the
1862                comparison operator is not an FP comparison operator, we
1863                have to handle it here.  */
1864             if (get_hard_regnum (regstack, *dest) >= FIRST_STACK_REG
1865                 && REGNO (*dest) != regstack->reg[regstack->top])
1866               {
1867                 /* In case one of operands is the top of stack and the operands
1868                    dies, it is safe to make it the destination operand by
1869                    reversing the direction of cmove and avoid fxch.  */
1870                 if ((REGNO (*src1) == regstack->reg[regstack->top]
1871                      && src1_note)
1872                     || (REGNO (*src2) == regstack->reg[regstack->top]
1873                         && src2_note))
1874                   {
1875                     int idx1 = (get_hard_regnum (regstack, *src1)
1876                                 - FIRST_STACK_REG);
1877                     int idx2 = (get_hard_regnum (regstack, *src2)
1878                                 - FIRST_STACK_REG);
1879
1880                     /* Make reg-stack believe that the operands are already
1881                        swapped on the stack */
1882                     regstack->reg[regstack->top - idx1] = REGNO (*src2);
1883                     regstack->reg[regstack->top - idx2] = REGNO (*src1);
1884
1885                     /* Reverse condition to compensate the operand swap.
1886                        i386 do have comparison always reversible.  */
1887                     PUT_CODE (XEXP (pat_src, 0),
1888                               reversed_comparison_code (XEXP (pat_src, 0), insn));
1889                   }
1890                 else
1891                   emit_swap_insn (insn, regstack, *dest);
1892               }
1893
1894             {
1895               rtx src_note [3];
1896               int i;
1897
1898               src_note[0] = 0;
1899               src_note[1] = src1_note;
1900               src_note[2] = src2_note;
1901
1902               if (STACK_REG_P (*src1))
1903                 replace_reg (src1, get_hard_regnum (regstack, *src1));
1904               if (STACK_REG_P (*src2))
1905                 replace_reg (src2, get_hard_regnum (regstack, *src2));
1906
1907               for (i = 1; i <= 2; i++)
1908                 if (src_note [i])
1909                   {
1910                     int regno = REGNO (XEXP (src_note[i], 0));
1911
1912                     /* If the register that dies is not at the top of
1913                        stack, then move the top of stack to the dead reg.
1914                        Top of stack should never die, as it is the
1915                        destination.  */
1916                     gcc_assert (regno != regstack->reg[regstack->top]);
1917                     remove_regno_note (insn, REG_DEAD, regno);
1918                     emit_pop_insn (insn, regstack, XEXP (src_note[i], 0),
1919                                     EMIT_AFTER);
1920                   }
1921             }
1922
1923             /* Make dest the top of stack.  Add dest to regstack if
1924                not present.  */
1925             if (get_hard_regnum (regstack, *dest) < FIRST_STACK_REG)
1926               regstack->reg[++regstack->top] = REGNO (*dest);
1927             SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
1928             replace_reg (dest, FIRST_STACK_REG);
1929             break;
1930
1931           default:
1932             gcc_unreachable ();
1933           }
1934         break;
1935       }
1936
1937     default:
1938       break;
1939     }
1940
1941   return control_flow_insn_deleted;
1942 }
1943 \f
1944 /* Substitute hard regnums for any stack regs in INSN, which has
1945    N_INPUTS inputs and N_OUTPUTS outputs.  REGSTACK is the stack info
1946    before the insn, and is updated with changes made here.
1947
1948    There are several requirements and assumptions about the use of
1949    stack-like regs in asm statements.  These rules are enforced by
1950    record_asm_stack_regs; see comments there for details.  Any
1951    asm_operands left in the RTL at this point may be assume to meet the
1952    requirements, since record_asm_stack_regs removes any problem asm.  */
1953
1954 static void
1955 subst_asm_stack_regs (rtx insn, stack regstack)
1956 {
1957   rtx body = PATTERN (insn);
1958   int alt;
1959
1960   rtx *note_reg;                /* Array of note contents */
1961   rtx **note_loc;               /* Address of REG field of each note */
1962   enum reg_note *note_kind;     /* The type of each note */
1963
1964   rtx *clobber_reg = 0;
1965   rtx **clobber_loc = 0;
1966
1967   struct stack_def temp_stack;
1968   int n_notes;
1969   int n_clobbers;
1970   rtx note;
1971   int i;
1972   int n_inputs, n_outputs;
1973
1974   if (! check_asm_stack_operands (insn))
1975     return;
1976
1977   /* Find out what the constraints required.  If no constraint
1978      alternative matches, that is a compiler bug: we should have caught
1979      such an insn in check_asm_stack_operands.  */
1980   extract_insn (insn);
1981   constrain_operands (1);
1982   alt = which_alternative;
1983
1984   preprocess_constraints ();
1985
1986   n_inputs = get_asm_operand_n_inputs (body);
1987   n_outputs = recog_data.n_operands - n_inputs;
1988
1989   gcc_assert (alt >= 0);
1990
1991   /* Strip SUBREGs here to make the following code simpler.  */
1992   for (i = 0; i < recog_data.n_operands; i++)
1993     if (GET_CODE (recog_data.operand[i]) == SUBREG
1994         && REG_P (SUBREG_REG (recog_data.operand[i])))
1995       {
1996         recog_data.operand_loc[i] = & SUBREG_REG (recog_data.operand[i]);
1997         recog_data.operand[i] = SUBREG_REG (recog_data.operand[i]);
1998       }
1999
2000   /* Set up NOTE_REG, NOTE_LOC and NOTE_KIND.  */
2001
2002   for (i = 0, note = REG_NOTES (insn); note; note = XEXP (note, 1))
2003     i++;
2004
2005   note_reg = alloca (i * sizeof (rtx));
2006   note_loc = alloca (i * sizeof (rtx *));
2007   note_kind = alloca (i * sizeof (enum reg_note));
2008
2009   n_notes = 0;
2010   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2011     {
2012       rtx reg = XEXP (note, 0);
2013       rtx *loc = & XEXP (note, 0);
2014
2015       if (GET_CODE (reg) == SUBREG && REG_P (SUBREG_REG (reg)))
2016         {
2017           loc = & SUBREG_REG (reg);
2018           reg = SUBREG_REG (reg);
2019         }
2020
2021       if (STACK_REG_P (reg)
2022           && (REG_NOTE_KIND (note) == REG_DEAD
2023               || REG_NOTE_KIND (note) == REG_UNUSED))
2024         {
2025           note_reg[n_notes] = reg;
2026           note_loc[n_notes] = loc;
2027           note_kind[n_notes] = REG_NOTE_KIND (note);
2028           n_notes++;
2029         }
2030     }
2031
2032   /* Set up CLOBBER_REG and CLOBBER_LOC.  */
2033
2034   n_clobbers = 0;
2035
2036   if (GET_CODE (body) == PARALLEL)
2037     {
2038       clobber_reg = alloca (XVECLEN (body, 0) * sizeof (rtx));
2039       clobber_loc = alloca (XVECLEN (body, 0) * sizeof (rtx *));
2040
2041       for (i = 0; i < XVECLEN (body, 0); i++)
2042         if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
2043           {
2044             rtx clobber = XVECEXP (body, 0, i);
2045             rtx reg = XEXP (clobber, 0);
2046             rtx *loc = & XEXP (clobber, 0);
2047
2048             if (GET_CODE (reg) == SUBREG && REG_P (SUBREG_REG (reg)))
2049               {
2050                 loc = & SUBREG_REG (reg);
2051                 reg = SUBREG_REG (reg);
2052               }
2053
2054             if (STACK_REG_P (reg))
2055               {
2056                 clobber_reg[n_clobbers] = reg;
2057                 clobber_loc[n_clobbers] = loc;
2058                 n_clobbers++;
2059               }
2060           }
2061     }
2062
2063   temp_stack = *regstack;
2064
2065   /* Put the input regs into the desired place in TEMP_STACK.  */
2066
2067   for (i = n_outputs; i < n_outputs + n_inputs; i++)
2068     if (STACK_REG_P (recog_data.operand[i])
2069         && reg_class_subset_p (recog_op_alt[i][alt].cl,
2070                                FLOAT_REGS)
2071         && recog_op_alt[i][alt].cl != FLOAT_REGS)
2072       {
2073         /* If an operand needs to be in a particular reg in
2074            FLOAT_REGS, the constraint was either 't' or 'u'.  Since
2075            these constraints are for single register classes, and
2076            reload guaranteed that operand[i] is already in that class,
2077            we can just use REGNO (recog_data.operand[i]) to know which
2078            actual reg this operand needs to be in.  */
2079
2080         int regno = get_hard_regnum (&temp_stack, recog_data.operand[i]);
2081
2082         gcc_assert (regno >= 0);
2083
2084         if ((unsigned int) regno != REGNO (recog_data.operand[i]))
2085           {
2086             /* recog_data.operand[i] is not in the right place.  Find
2087                it and swap it with whatever is already in I's place.
2088                K is where recog_data.operand[i] is now.  J is where it
2089                should be.  */
2090             int j, k, temp;
2091
2092             k = temp_stack.top - (regno - FIRST_STACK_REG);
2093             j = (temp_stack.top
2094                  - (REGNO (recog_data.operand[i]) - FIRST_STACK_REG));
2095
2096             temp = temp_stack.reg[k];
2097             temp_stack.reg[k] = temp_stack.reg[j];
2098             temp_stack.reg[j] = temp;
2099           }
2100       }
2101
2102   /* Emit insns before INSN to make sure the reg-stack is in the right
2103      order.  */
2104
2105   change_stack (insn, regstack, &temp_stack, EMIT_BEFORE);
2106
2107   /* Make the needed input register substitutions.  Do death notes and
2108      clobbers too, because these are for inputs, not outputs.  */
2109
2110   for (i = n_outputs; i < n_outputs + n_inputs; i++)
2111     if (STACK_REG_P (recog_data.operand[i]))
2112       {
2113         int regnum = get_hard_regnum (regstack, recog_data.operand[i]);
2114
2115         gcc_assert (regnum >= 0);
2116
2117         replace_reg (recog_data.operand_loc[i], regnum);
2118       }
2119
2120   for (i = 0; i < n_notes; i++)
2121     if (note_kind[i] == REG_DEAD)
2122       {
2123         int regnum = get_hard_regnum (regstack, note_reg[i]);
2124
2125         gcc_assert (regnum >= 0);
2126
2127         replace_reg (note_loc[i], regnum);
2128       }
2129
2130   for (i = 0; i < n_clobbers; i++)
2131     {
2132       /* It's OK for a CLOBBER to reference a reg that is not live.
2133          Don't try to replace it in that case.  */
2134       int regnum = get_hard_regnum (regstack, clobber_reg[i]);
2135
2136       if (regnum >= 0)
2137         {
2138           /* Sigh - clobbers always have QImode.  But replace_reg knows
2139              that these regs can't be MODE_INT and will assert.  Just put
2140              the right reg there without calling replace_reg.  */
2141
2142           *clobber_loc[i] = FP_MODE_REG (regnum, DFmode);
2143         }
2144     }
2145
2146   /* Now remove from REGSTACK any inputs that the asm implicitly popped.  */
2147
2148   for (i = n_outputs; i < n_outputs + n_inputs; i++)
2149     if (STACK_REG_P (recog_data.operand[i]))
2150       {
2151         /* An input reg is implicitly popped if it is tied to an
2152            output, or if there is a CLOBBER for it.  */
2153         int j;
2154
2155         for (j = 0; j < n_clobbers; j++)
2156           if (operands_match_p (clobber_reg[j], recog_data.operand[i]))
2157             break;
2158
2159         if (j < n_clobbers || recog_op_alt[i][alt].matches >= 0)
2160           {
2161             /* recog_data.operand[i] might not be at the top of stack.
2162                But that's OK, because all we need to do is pop the
2163                right number of regs off of the top of the reg-stack.
2164                record_asm_stack_regs guaranteed that all implicitly
2165                popped regs were grouped at the top of the reg-stack.  */
2166
2167             CLEAR_HARD_REG_BIT (regstack->reg_set,
2168                                 regstack->reg[regstack->top]);
2169             regstack->top--;
2170           }
2171       }
2172
2173   /* Now add to REGSTACK any outputs that the asm implicitly pushed.
2174      Note that there isn't any need to substitute register numbers.
2175      ???  Explain why this is true.  */
2176
2177   for (i = LAST_STACK_REG; i >= FIRST_STACK_REG; i--)
2178     {
2179       /* See if there is an output for this hard reg.  */
2180       int j;
2181
2182       for (j = 0; j < n_outputs; j++)
2183         if (STACK_REG_P (recog_data.operand[j])
2184             && REGNO (recog_data.operand[j]) == (unsigned) i)
2185           {
2186             regstack->reg[++regstack->top] = i;
2187             SET_HARD_REG_BIT (regstack->reg_set, i);
2188             break;
2189           }
2190     }
2191
2192   /* Now emit a pop insn for any REG_UNUSED output, or any REG_DEAD
2193      input that the asm didn't implicitly pop.  If the asm didn't
2194      implicitly pop an input reg, that reg will still be live.
2195
2196      Note that we can't use find_regno_note here: the register numbers
2197      in the death notes have already been substituted.  */
2198
2199   for (i = 0; i < n_outputs; i++)
2200     if (STACK_REG_P (recog_data.operand[i]))
2201       {
2202         int j;
2203
2204         for (j = 0; j < n_notes; j++)
2205           if (REGNO (recog_data.operand[i]) == REGNO (note_reg[j])
2206               && note_kind[j] == REG_UNUSED)
2207             {
2208               insn = emit_pop_insn (insn, regstack, recog_data.operand[i],
2209                                     EMIT_AFTER);
2210               break;
2211             }
2212       }
2213
2214   for (i = n_outputs; i < n_outputs + n_inputs; i++)
2215     if (STACK_REG_P (recog_data.operand[i]))
2216       {
2217         int j;
2218
2219         for (j = 0; j < n_notes; j++)
2220           if (REGNO (recog_data.operand[i]) == REGNO (note_reg[j])
2221               && note_kind[j] == REG_DEAD
2222               && TEST_HARD_REG_BIT (regstack->reg_set,
2223                                     REGNO (recog_data.operand[i])))
2224             {
2225               insn = emit_pop_insn (insn, regstack, recog_data.operand[i],
2226                                     EMIT_AFTER);
2227               break;
2228             }
2229       }
2230 }
2231 \f
2232 /* Substitute stack hard reg numbers for stack virtual registers in
2233    INSN.  Non-stack register numbers are not changed.  REGSTACK is the
2234    current stack content.  Insns may be emitted as needed to arrange the
2235    stack for the 387 based on the contents of the insn.  Return whether
2236    a control flow insn was deleted in the process.  */
2237
2238 static bool
2239 subst_stack_regs (rtx insn, stack regstack)
2240 {
2241   rtx *note_link, note;
2242   bool control_flow_insn_deleted = false;
2243   int i;
2244
2245   if (CALL_P (insn))
2246     {
2247       int top = regstack->top;
2248
2249       /* If there are any floating point parameters to be passed in
2250          registers for this call, make sure they are in the right
2251          order.  */
2252
2253       if (top >= 0)
2254         {
2255           straighten_stack (insn, regstack);
2256
2257           /* Now mark the arguments as dead after the call.  */
2258
2259           while (regstack->top >= 0)
2260             {
2261               CLEAR_HARD_REG_BIT (regstack->reg_set, FIRST_STACK_REG + regstack->top);
2262               regstack->top--;
2263             }
2264         }
2265     }
2266
2267   /* Do the actual substitution if any stack regs are mentioned.
2268      Since we only record whether entire insn mentions stack regs, and
2269      subst_stack_regs_pat only works for patterns that contain stack regs,
2270      we must check each pattern in a parallel here.  A call_value_pop could
2271      fail otherwise.  */
2272
2273   if (stack_regs_mentioned (insn))
2274     {
2275       int n_operands = asm_noperands (PATTERN (insn));
2276       if (n_operands >= 0)
2277         {
2278           /* This insn is an `asm' with operands.  Decode the operands,
2279              decide how many are inputs, and do register substitution.
2280              Any REG_UNUSED notes will be handled by subst_asm_stack_regs.  */
2281
2282           subst_asm_stack_regs (insn, regstack);
2283           return control_flow_insn_deleted;
2284         }
2285
2286       if (GET_CODE (PATTERN (insn)) == PARALLEL)
2287         for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2288           {
2289             if (stack_regs_mentioned_p (XVECEXP (PATTERN (insn), 0, i)))
2290               {
2291                 if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
2292                    XVECEXP (PATTERN (insn), 0, i)
2293                      = shallow_copy_rtx (XVECEXP (PATTERN (insn), 0, i));
2294                 control_flow_insn_deleted
2295                   |= subst_stack_regs_pat (insn, regstack,
2296                                            XVECEXP (PATTERN (insn), 0, i));
2297               }
2298           }
2299       else
2300         control_flow_insn_deleted
2301           |= subst_stack_regs_pat (insn, regstack, PATTERN (insn));
2302     }
2303
2304   /* subst_stack_regs_pat may have deleted a no-op insn.  If so, any
2305      REG_UNUSED will already have been dealt with, so just return.  */
2306
2307   if (NOTE_P (insn) || INSN_DELETED_P (insn))
2308     return control_flow_insn_deleted;
2309
2310   /* If this a noreturn call, we can't insert pop insns after it.
2311      Instead, reset the stack state to empty.  */
2312   if (CALL_P (insn)
2313       && find_reg_note (insn, REG_NORETURN, NULL))
2314     {
2315       regstack->top = -1;
2316       CLEAR_HARD_REG_SET (regstack->reg_set);
2317       return control_flow_insn_deleted;
2318     }
2319
2320   /* If there is a REG_UNUSED note on a stack register on this insn,
2321      the indicated reg must be popped.  The REG_UNUSED note is removed,
2322      since the form of the newly emitted pop insn references the reg,
2323      making it no longer `unset'.  */
2324
2325   note_link = &REG_NOTES (insn);
2326   for (note = *note_link; note; note = XEXP (note, 1))
2327     if (REG_NOTE_KIND (note) == REG_UNUSED && STACK_REG_P (XEXP (note, 0)))
2328       {
2329         *note_link = XEXP (note, 1);
2330         insn = emit_pop_insn (insn, regstack, XEXP (note, 0), EMIT_AFTER);
2331       }
2332     else
2333       note_link = &XEXP (note, 1);
2334
2335   return control_flow_insn_deleted;
2336 }
2337 \f
2338 /* Change the organization of the stack so that it fits a new basic
2339    block.  Some registers might have to be popped, but there can never be
2340    a register live in the new block that is not now live.
2341
2342    Insert any needed insns before or after INSN, as indicated by
2343    WHERE.  OLD is the original stack layout, and NEW is the desired
2344    form.  OLD is updated to reflect the code emitted, i.e., it will be
2345    the same as NEW upon return.
2346
2347    This function will not preserve block_end[].  But that information
2348    is no longer needed once this has executed.  */
2349
2350 static void
2351 change_stack (rtx insn, stack old, stack new, enum emit_where where)
2352 {
2353   int reg;
2354   int update_end = 0;
2355
2356   /* Stack adjustments for the first insn in a block update the
2357      current_block's stack_in instead of inserting insns directly.
2358      compensate_edges will add the necessary code later.  */
2359   if (current_block
2360       && starting_stack_p
2361       && where == EMIT_BEFORE)
2362     {
2363       BLOCK_INFO (current_block)->stack_in = *new;
2364       starting_stack_p = false;
2365       *old = *new;
2366       return;
2367     }
2368
2369   /* We will be inserting new insns "backwards".  If we are to insert
2370      after INSN, find the next insn, and insert before it.  */
2371
2372   if (where == EMIT_AFTER)
2373     {
2374       if (current_block && BB_END (current_block) == insn)
2375         update_end = 1;
2376       insn = NEXT_INSN (insn);
2377     }
2378
2379   /* Pop any registers that are not needed in the new block.  */
2380
2381   /* If the destination block's stack already has a specified layout
2382      and contains two or more registers, use a more intelligent algorithm
2383      to pop registers that minimizes the number number of fxchs below.  */
2384   if (new->top > 0)
2385     {
2386       bool slots[REG_STACK_SIZE];
2387       int pops[REG_STACK_SIZE];
2388       int next, dest, topsrc;
2389
2390       /* First pass to determine the free slots.  */
2391       for (reg = 0; reg <= new->top; reg++)
2392         slots[reg] = TEST_HARD_REG_BIT (new->reg_set, old->reg[reg]);
2393
2394       /* Second pass to allocate preferred slots.  */
2395       topsrc = -1;
2396       for (reg = old->top; reg > new->top; reg--)
2397         if (TEST_HARD_REG_BIT (new->reg_set, old->reg[reg]))
2398           {
2399             dest = -1;
2400             for (next = 0; next <= new->top; next++)
2401               if (!slots[next] && new->reg[next] == old->reg[reg])
2402                 {
2403                   /* If this is a preference for the new top of stack, record
2404                      the fact by remembering it's old->reg in topsrc.  */
2405                   if (next == new->top)
2406                     topsrc = reg;
2407                   slots[next] = true;
2408                   dest = next;
2409                   break;
2410                 }
2411             pops[reg] = dest;
2412           }
2413         else
2414           pops[reg] = reg;
2415
2416       /* Intentionally, avoid placing the top of stack in it's correct
2417          location, if we still need to permute the stack below and we
2418          can usefully place it somewhere else.  This is the case if any
2419          slot is still unallocated, in which case we should place the
2420          top of stack there.  */
2421       if (topsrc != -1)
2422         for (reg = 0; reg < new->top; reg++)
2423           if (!slots[reg])
2424             {
2425               pops[topsrc] = reg;
2426               slots[new->top] = false;
2427               slots[reg] = true;
2428               break;
2429             }
2430
2431       /* Third pass allocates remaining slots and emits pop insns.  */
2432       next = new->top;
2433       for (reg = old->top; reg > new->top; reg--)
2434         {
2435           dest = pops[reg];
2436           if (dest == -1)
2437             {
2438               /* Find next free slot.  */
2439               while (slots[next])
2440                 next--;
2441               dest = next--;
2442             }
2443           emit_pop_insn (insn, old, FP_MODE_REG (old->reg[dest], DFmode),
2444                          EMIT_BEFORE);
2445         }
2446     }
2447   else
2448     {
2449       /* The following loop attempts to maximize the number of times we
2450          pop the top of the stack, as this permits the use of the faster
2451          ffreep instruction on platforms that support it.  */
2452       int live, next;
2453
2454       live = 0;
2455       for (reg = 0; reg <= old->top; reg++)
2456         if (TEST_HARD_REG_BIT (new->reg_set, old->reg[reg]))
2457           live++;
2458
2459       next = live;
2460       while (old->top >= live)
2461         if (TEST_HARD_REG_BIT (new->reg_set, old->reg[old->top]))
2462           {
2463             while (TEST_HARD_REG_BIT (new->reg_set, old->reg[next]))
2464               next--;
2465             emit_pop_insn (insn, old, FP_MODE_REG (old->reg[next], DFmode),
2466                            EMIT_BEFORE);
2467           }
2468         else
2469           emit_pop_insn (insn, old, FP_MODE_REG (old->reg[old->top], DFmode),
2470                          EMIT_BEFORE);
2471     }
2472
2473   if (new->top == -2)
2474     {
2475       /* If the new block has never been processed, then it can inherit
2476          the old stack order.  */
2477
2478       new->top = old->top;
2479       memcpy (new->reg, old->reg, sizeof (new->reg));
2480     }
2481   else
2482     {
2483       /* This block has been entered before, and we must match the
2484          previously selected stack order.  */
2485
2486       /* By now, the only difference should be the order of the stack,
2487          not their depth or liveliness.  */
2488
2489       GO_IF_HARD_REG_EQUAL (old->reg_set, new->reg_set, win);
2490       gcc_unreachable ();
2491     win:
2492       gcc_assert (old->top == new->top);
2493
2494       /* If the stack is not empty (new->top != -1), loop here emitting
2495          swaps until the stack is correct.
2496
2497          The worst case number of swaps emitted is N + 2, where N is the
2498          depth of the stack.  In some cases, the reg at the top of
2499          stack may be correct, but swapped anyway in order to fix
2500          other regs.  But since we never swap any other reg away from
2501          its correct slot, this algorithm will converge.  */
2502
2503       if (new->top != -1)
2504         do
2505           {
2506             /* Swap the reg at top of stack into the position it is
2507                supposed to be in, until the correct top of stack appears.  */
2508
2509             while (old->reg[old->top] != new->reg[new->top])
2510               {
2511                 for (reg = new->top; reg >= 0; reg--)
2512                   if (new->reg[reg] == old->reg[old->top])
2513                     break;
2514
2515                 gcc_assert (reg != -1);
2516
2517                 emit_swap_insn (insn, old,
2518                                 FP_MODE_REG (old->reg[reg], DFmode));
2519               }
2520
2521             /* See if any regs remain incorrect.  If so, bring an
2522              incorrect reg to the top of stack, and let the while loop
2523              above fix it.  */
2524
2525             for (reg = new->top; reg >= 0; reg--)
2526               if (new->reg[reg] != old->reg[reg])
2527                 {
2528                   emit_swap_insn (insn, old,
2529                                   FP_MODE_REG (old->reg[reg], DFmode));
2530                   break;
2531                 }
2532           } while (reg >= 0);
2533
2534       /* At this point there must be no differences.  */
2535
2536       for (reg = old->top; reg >= 0; reg--)
2537         gcc_assert (old->reg[reg] == new->reg[reg]);
2538     }
2539
2540   if (update_end)
2541     BB_END (current_block) = PREV_INSN (insn);
2542 }
2543 \f
2544 /* Print stack configuration.  */
2545
2546 static void
2547 print_stack (FILE *file, stack s)
2548 {
2549   if (! file)
2550     return;
2551
2552   if (s->top == -2)
2553     fprintf (file, "uninitialized\n");
2554   else if (s->top == -1)
2555     fprintf (file, "empty\n");
2556   else
2557     {
2558       int i;
2559       fputs ("[ ", file);
2560       for (i = 0; i <= s->top; ++i)
2561         fprintf (file, "%d ", s->reg[i]);
2562       fputs ("]\n", file);
2563     }
2564 }
2565 \f
2566 /* This function was doing life analysis.  We now let the regular live
2567    code do it's job, so we only need to check some extra invariants
2568    that reg-stack expects.  Primary among these being that all registers
2569    are initialized before use.
2570
2571    The function returns true when code was emitted to CFG edges and
2572    commit_edge_insertions needs to be called.  */
2573
2574 static int
2575 convert_regs_entry (void)
2576 {
2577   int inserted = 0;
2578   edge e;
2579   edge_iterator ei;
2580
2581   /* Load something into each stack register live at function entry.
2582      Such live registers can be caused by uninitialized variables or
2583      functions not returning values on all paths.  In order to keep
2584      the push/pop code happy, and to not scrog the register stack, we
2585      must put something in these registers.  Use a QNaN.
2586
2587      Note that we are inserting converted code here.  This code is
2588      never seen by the convert_regs pass.  */
2589
2590   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2591     {
2592       basic_block block = e->dest;
2593       block_info bi = BLOCK_INFO (block);
2594       int reg, top = -1;
2595
2596       for (reg = LAST_STACK_REG; reg >= FIRST_STACK_REG; --reg)
2597         if (TEST_HARD_REG_BIT (bi->stack_in.reg_set, reg))
2598           {
2599             rtx init;
2600
2601             bi->stack_in.reg[++top] = reg;
2602
2603             init = gen_rtx_SET (VOIDmode,
2604                                 FP_MODE_REG (FIRST_STACK_REG, SFmode),
2605                                 not_a_num);
2606             insert_insn_on_edge (init, e);
2607             inserted = 1;
2608           }
2609
2610       bi->stack_in.top = top;
2611     }
2612
2613   return inserted;
2614 }
2615
2616 /* Construct the desired stack for function exit.  This will either
2617    be `empty', or the function return value at top-of-stack.  */
2618
2619 static void
2620 convert_regs_exit (void)
2621 {
2622   int value_reg_low, value_reg_high;
2623   stack output_stack;
2624   rtx retvalue;
2625
2626   retvalue = stack_result (current_function_decl);
2627   value_reg_low = value_reg_high = -1;
2628   if (retvalue)
2629     {
2630       value_reg_low = REGNO (retvalue);
2631       value_reg_high = value_reg_low
2632         + hard_regno_nregs[value_reg_low][GET_MODE (retvalue)] - 1;
2633     }
2634
2635   output_stack = &BLOCK_INFO (EXIT_BLOCK_PTR)->stack_in;
2636   if (value_reg_low == -1)
2637     output_stack->top = -1;
2638   else
2639     {
2640       int reg;
2641
2642       output_stack->top = value_reg_high - value_reg_low;
2643       for (reg = value_reg_low; reg <= value_reg_high; ++reg)
2644         {
2645           output_stack->reg[value_reg_high - reg] = reg;
2646           SET_HARD_REG_BIT (output_stack->reg_set, reg);
2647         }
2648     }
2649 }
2650
2651 /* Copy the stack info from the end of edge E's source block to the
2652    start of E's destination block.  */
2653
2654 static void
2655 propagate_stack (edge e)
2656 {
2657   stack src_stack = &BLOCK_INFO (e->src)->stack_out;
2658   stack dest_stack = &BLOCK_INFO (e->dest)->stack_in;
2659   int reg;
2660
2661   /* Preserve the order of the original stack, but check whether
2662      any pops are needed.  */
2663   dest_stack->top = -1;
2664   for (reg = 0; reg <= src_stack->top; ++reg)
2665     if (TEST_HARD_REG_BIT (dest_stack->reg_set, src_stack->reg[reg]))
2666       dest_stack->reg[++dest_stack->top] = src_stack->reg[reg];
2667 }
2668
2669
2670 /* Adjust the stack of edge E's source block on exit to match the stack
2671    of it's target block upon input.  The stack layouts of both blocks
2672    should have been defined by now.  */
2673
2674 static bool
2675 compensate_edge (edge e)
2676 {
2677   basic_block source = e->src, target = e->dest;
2678   stack target_stack = &BLOCK_INFO (target)->stack_in;
2679   stack source_stack = &BLOCK_INFO (source)->stack_out;
2680   struct stack_def regstack;
2681   int reg;
2682
2683   if (dump_file)
2684     fprintf (dump_file, "Edge %d->%d: ", source->index, target->index);
2685
2686   gcc_assert (target_stack->top != -2);
2687
2688   /* Check whether stacks are identical.  */
2689   if (target_stack->top == source_stack->top)
2690     {
2691       for (reg = target_stack->top; reg >= 0; --reg)
2692         if (target_stack->reg[reg] != source_stack->reg[reg])
2693           break;
2694
2695       if (reg == -1)
2696         {
2697           if (dump_file)
2698             fprintf (dump_file, "no changes needed\n");
2699           return false;
2700         }
2701     }
2702
2703   if (dump_file)
2704     {
2705       fprintf (dump_file, "correcting stack to ");
2706       print_stack (dump_file, target_stack);
2707     }
2708
2709   /* Abnormal calls may appear to have values live in st(0), but the
2710      abnormal return path will not have actually loaded the values.  */
2711   if (e->flags & EDGE_ABNORMAL_CALL)
2712     {
2713       /* Assert that the lifetimes are as we expect -- one value
2714          live at st(0) on the end of the source block, and no
2715          values live at the beginning of the destination block.
2716          For complex return values, we may have st(1) live as well.  */
2717       gcc_assert (source_stack->top == 0 || source_stack->top == 1);
2718       gcc_assert (target_stack->top == -1);
2719       return false;
2720     }
2721
2722   /* Handle non-call EH edges specially.  The normal return path have
2723      values in registers.  These will be popped en masse by the unwind
2724      library.  */
2725   if (e->flags & EDGE_EH)
2726     {
2727       gcc_assert (target_stack->top == -1);
2728       return false;
2729     }
2730
2731   /* We don't support abnormal edges.  Global takes care to
2732      avoid any live register across them, so we should never
2733      have to insert instructions on such edges.  */
2734   gcc_assert (! (e->flags & EDGE_ABNORMAL));
2735
2736   /* Make a copy of source_stack as change_stack is destructive.  */
2737   regstack = *source_stack;
2738
2739   /* It is better to output directly to the end of the block
2740      instead of to the edge, because emit_swap can do minimal
2741      insn scheduling.  We can do this when there is only one
2742      edge out, and it is not abnormal.  */
2743   if (EDGE_COUNT (source->succs) == 1)
2744     {
2745       current_block = source;
2746       change_stack (BB_END (source), &regstack, target_stack,
2747                     (JUMP_P (BB_END (source)) ? EMIT_BEFORE : EMIT_AFTER));
2748     }
2749   else
2750     {
2751       rtx seq, after;
2752
2753       current_block = NULL;
2754       start_sequence ();
2755
2756       /* ??? change_stack needs some point to emit insns after.  */
2757       after = emit_note (NOTE_INSN_DELETED);
2758
2759       change_stack (after, &regstack, target_stack, EMIT_BEFORE);
2760
2761       seq = get_insns ();
2762       end_sequence ();
2763
2764       insert_insn_on_edge (seq, e);
2765       return true;
2766     }
2767   return false;
2768 }
2769
2770 /* Traverse all non-entry edges in the CFG, and emit the necessary
2771    edge compensation code to change the stack from stack_out of the
2772    source block to the stack_in of the destination block.  */
2773
2774 static bool
2775 compensate_edges (void)
2776 {
2777   bool inserted = false;
2778   basic_block bb;
2779
2780   starting_stack_p = false;
2781
2782   FOR_EACH_BB (bb)
2783     if (bb != ENTRY_BLOCK_PTR)
2784       {
2785         edge e;
2786         edge_iterator ei;
2787
2788         FOR_EACH_EDGE (e, ei, bb->succs)
2789           inserted |= compensate_edge (e);
2790       }
2791   return inserted;
2792 }
2793
2794 /* Select the better of two edges E1 and E2 to use to determine the
2795    stack layout for their shared destination basic block.  This is
2796    typically the more frequently executed.  The edge E1 may be NULL
2797    (in which case E2 is returned), but E2 is always non-NULL.  */
2798
2799 static edge
2800 better_edge (edge e1, edge e2)
2801 {
2802   if (!e1)
2803     return e2;
2804
2805   if (EDGE_FREQUENCY (e1) > EDGE_FREQUENCY (e2))
2806     return e1;
2807   if (EDGE_FREQUENCY (e1) < EDGE_FREQUENCY (e2))
2808     return e2;
2809
2810   if (e1->count > e2->count)
2811     return e1;
2812   if (e1->count < e2->count)
2813     return e2;
2814
2815   /* Prefer critical edges to minimize inserting compensation code on
2816      critical edges.  */
2817
2818   if (EDGE_CRITICAL_P (e1) != EDGE_CRITICAL_P (e2))
2819     return EDGE_CRITICAL_P (e1) ? e1 : e2;
2820
2821   /* Avoid non-deterministic behavior.  */
2822   return (e1->src->index < e2->src->index) ? e1 : e2;
2823 }
2824
2825 /* Convert stack register references in one block.  */
2826
2827 static void
2828 convert_regs_1 (basic_block block)
2829 {
2830   struct stack_def regstack;
2831   block_info bi = BLOCK_INFO (block);
2832   int reg;
2833   rtx insn, next;
2834   bool control_flow_insn_deleted = false;
2835
2836   any_malformed_asm = false;
2837
2838   /* Choose an initial stack layout, if one hasn't already been chosen.  */
2839   if (bi->stack_in.top == -2)
2840     {
2841       edge e, beste = NULL;
2842       edge_iterator ei;
2843
2844       /* Select the best incoming edge (typically the most frequent) to
2845          use as a template for this basic block.  */
2846       FOR_EACH_EDGE (e, ei, block->preds)
2847         if (BLOCK_INFO (e->src)->done)
2848           beste = better_edge (beste, e);
2849
2850       if (beste)
2851         propagate_stack (beste);
2852       else
2853         {
2854           /* No predecessors.  Create an arbitrary input stack.  */
2855           bi->stack_in.top = -1;
2856           for (reg = LAST_STACK_REG; reg >= FIRST_STACK_REG; --reg)
2857             if (TEST_HARD_REG_BIT (bi->stack_in.reg_set, reg))
2858               bi->stack_in.reg[++bi->stack_in.top] = reg;
2859         }
2860     }
2861
2862   if (dump_file)
2863     {
2864       fprintf (dump_file, "\nBasic block %d\nInput stack: ", block->index);
2865       print_stack (dump_file, &bi->stack_in);
2866     }
2867
2868   /* Process all insns in this block.  Keep track of NEXT so that we
2869      don't process insns emitted while substituting in INSN.  */
2870   current_block = block;
2871   next = BB_HEAD (block);
2872   regstack = bi->stack_in;
2873   starting_stack_p = true;
2874
2875   do
2876     {
2877       insn = next;
2878       next = NEXT_INSN (insn);
2879
2880       /* Ensure we have not missed a block boundary.  */
2881       gcc_assert (next);
2882       if (insn == BB_END (block))
2883         next = NULL;
2884
2885       /* Don't bother processing unless there is a stack reg
2886          mentioned or if it's a CALL_INSN.  */
2887       if (stack_regs_mentioned (insn)
2888           || CALL_P (insn))
2889         {
2890           if (dump_file)
2891             {
2892               fprintf (dump_file, "  insn %d input stack: ",
2893                        INSN_UID (insn));
2894               print_stack (dump_file, &regstack);
2895             }
2896           control_flow_insn_deleted |= subst_stack_regs (insn, &regstack);
2897           starting_stack_p = false;
2898         }
2899     }
2900   while (next);
2901
2902   if (dump_file)
2903     {
2904       fprintf (dump_file, "Expected live registers [");
2905       for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; ++reg)
2906         if (TEST_HARD_REG_BIT (bi->out_reg_set, reg))
2907           fprintf (dump_file, " %d", reg);
2908       fprintf (dump_file, " ]\nOutput stack: ");
2909       print_stack (dump_file, &regstack);
2910     }
2911
2912   insn = BB_END (block);
2913   if (JUMP_P (insn))
2914     insn = PREV_INSN (insn);
2915
2916   /* If the function is declared to return a value, but it returns one
2917      in only some cases, some registers might come live here.  Emit
2918      necessary moves for them.  */
2919
2920   for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; ++reg)
2921     {
2922       if (TEST_HARD_REG_BIT (bi->out_reg_set, reg)
2923           && ! TEST_HARD_REG_BIT (regstack.reg_set, reg))
2924         {
2925           rtx set;
2926
2927           if (dump_file)
2928             fprintf (dump_file, "Emitting insn initializing reg %d\n", reg);
2929
2930           set = gen_rtx_SET (VOIDmode, FP_MODE_REG (reg, SFmode), not_a_num);
2931           insn = emit_insn_after (set, insn);
2932           control_flow_insn_deleted |= subst_stack_regs (insn, &regstack);
2933         }
2934     }
2935   
2936   /* Amongst the insns possibly deleted during the substitution process above,
2937      might have been the only trapping insn in the block.  We purge the now
2938      possibly dead EH edges here to avoid an ICE from fixup_abnormal_edges,
2939      called at the end of convert_regs.  The order in which we process the
2940      blocks ensures that we never delete an already processed edge.
2941
2942      Note that, at this point, the CFG may have been damaged by the emission
2943      of instructions after an abnormal call, which moves the basic block end
2944      (and is the reason why we call fixup_abnormal_edges later).  So we must
2945      be sure that the trapping insn has been deleted before trying to purge
2946      dead edges, otherwise we risk purging valid edges.
2947
2948      ??? We are normally supposed not to delete trapping insns, so we pretend
2949      that the insns deleted above don't actually trap.  It would have been
2950      better to detect this earlier and avoid creating the EH edge in the first
2951      place, still, but we don't have enough information at that time.  */
2952
2953   if (control_flow_insn_deleted)
2954     purge_dead_edges (block);
2955
2956   /* Something failed if the stack lives don't match.  If we had malformed
2957      asms, we zapped the instruction itself, but that didn't produce the
2958      same pattern of register kills as before.  */
2959   GO_IF_HARD_REG_EQUAL (regstack.reg_set, bi->out_reg_set, win);
2960   gcc_assert (any_malformed_asm);
2961  win:
2962   bi->stack_out = regstack;
2963   bi->done = true;
2964 }
2965
2966 /* Convert registers in all blocks reachable from BLOCK.  */
2967
2968 static void
2969 convert_regs_2 (basic_block block)
2970 {
2971   basic_block *stack, *sp;
2972
2973   /* We process the blocks in a top-down manner, in a way such that one block
2974      is only processed after all its predecessors.  The number of predecessors
2975      of every block has already been computed.  */ 
2976
2977   stack = XNEWVEC (basic_block, n_basic_blocks);
2978   sp = stack;
2979
2980   *sp++ = block;
2981
2982   do
2983     {
2984       edge e;
2985       edge_iterator ei;
2986
2987       block = *--sp;
2988
2989       /* Processing BLOCK is achieved by convert_regs_1, which may purge
2990          some dead EH outgoing edge after the deletion of the trapping
2991          insn inside the block.  Since the number of predecessors of
2992          BLOCK's successors was computed based on the initial edge set,
2993          we check the necessity to process some of these successors
2994          before such an edge deletion may happen.  However, there is
2995          a pitfall: if BLOCK is the only predecessor of a successor and
2996          the edge between them happens to be deleted, the successor
2997          becomes unreachable and should not be processed.  The problem
2998          is that there is no way to preventively detect this case so we
2999          stack the successor in all cases and hand over the task of
3000          fixing up the discrepancy to convert_regs_1.  */
3001
3002       FOR_EACH_EDGE (e, ei, block->succs)
3003         if (! (e->flags & EDGE_DFS_BACK))
3004           {
3005             BLOCK_INFO (e->dest)->predecessors--;
3006             if (!BLOCK_INFO (e->dest)->predecessors)
3007               *sp++ = e->dest;
3008           }
3009
3010       convert_regs_1 (block);
3011     }
3012   while (sp != stack);
3013
3014   free (stack);
3015 }
3016
3017 /* Traverse all basic blocks in a function, converting the register
3018    references in each insn from the "flat" register file that gcc uses,
3019    to the stack-like registers the 387 uses.  */
3020
3021 static void
3022 convert_regs (void)
3023 {
3024   int inserted;
3025   basic_block b;
3026   edge e;
3027   edge_iterator ei;
3028
3029   /* Initialize uninitialized registers on function entry.  */
3030   inserted = convert_regs_entry ();
3031
3032   /* Construct the desired stack for function exit.  */
3033   convert_regs_exit ();
3034   BLOCK_INFO (EXIT_BLOCK_PTR)->done = 1;
3035
3036   /* ??? Future: process inner loops first, and give them arbitrary
3037      initial stacks which emit_swap_insn can modify.  This ought to
3038      prevent double fxch that often appears at the head of a loop.  */
3039
3040   /* Process all blocks reachable from all entry points.  */
3041   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3042     convert_regs_2 (e->dest);
3043
3044   /* ??? Process all unreachable blocks.  Though there's no excuse
3045      for keeping these even when not optimizing.  */
3046   FOR_EACH_BB (b)
3047     {
3048       block_info bi = BLOCK_INFO (b);
3049
3050       if (! bi->done)
3051         convert_regs_2 (b);
3052     }
3053
3054   inserted |= compensate_edges ();
3055
3056   clear_aux_for_blocks ();
3057
3058   fixup_abnormal_edges ();
3059   if (inserted)
3060     commit_edge_insertions ();
3061
3062   if (dump_file)
3063     fputc ('\n', dump_file);
3064 }
3065 \f
3066 /* Convert register usage from "flat" register file usage to a "stack
3067    register file.  FILE is the dump file, if used.
3068
3069    Construct a CFG and run life analysis.  Then convert each insn one
3070    by one.  Run a last cleanup_cfg pass, if optimizing, to eliminate
3071    code duplication created when the converter inserts pop insns on
3072    the edges.  */
3073
3074 static bool
3075 reg_to_stack (void)
3076 {
3077   basic_block bb;
3078   int i;
3079   int max_uid;
3080
3081   /* Clean up previous run.  */
3082   if (stack_regs_mentioned_data != NULL)
3083     VEC_free (char, heap, stack_regs_mentioned_data);
3084
3085   /* See if there is something to do.  Flow analysis is quite
3086      expensive so we might save some compilation time.  */
3087   for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
3088     if (regs_ever_live[i])
3089       break;
3090   if (i > LAST_STACK_REG)
3091     return false;
3092
3093   /* Ok, floating point instructions exist.  If not optimizing,
3094      build the CFG and run life analysis.
3095      Also need to rebuild life when superblock scheduling is done
3096      as it don't update liveness yet.  */
3097   if (!optimize
3098       || ((flag_sched2_use_superblocks || flag_sched2_use_traces)
3099           && flag_schedule_insns_after_reload))
3100     {
3101       count_or_remove_death_notes (NULL, 1);
3102       life_analysis (PROP_DEATH_NOTES);
3103     }
3104   mark_dfs_back_edges ();
3105
3106   /* Set up block info for each basic block.  */
3107   alloc_aux_for_blocks (sizeof (struct block_info_def));
3108   FOR_EACH_BB (bb)
3109     {
3110       block_info bi = BLOCK_INFO (bb);
3111       edge_iterator ei;
3112       edge e;
3113       int reg;
3114
3115       FOR_EACH_EDGE (e, ei, bb->preds)
3116         if (!(e->flags & EDGE_DFS_BACK)
3117             && e->src != ENTRY_BLOCK_PTR)
3118           bi->predecessors++;
3119
3120       /* Set current register status at last instruction `uninitialized'.  */
3121       bi->stack_in.top = -2;
3122
3123       /* Copy live_at_end and live_at_start into temporaries.  */
3124       for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
3125         {
3126           if (REGNO_REG_SET_P (bb->il.rtl->global_live_at_end, reg))
3127             SET_HARD_REG_BIT (bi->out_reg_set, reg);
3128           if (REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, reg))
3129             SET_HARD_REG_BIT (bi->stack_in.reg_set, reg);
3130         }
3131     }
3132
3133   /* Create the replacement registers up front.  */
3134   for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
3135     {
3136       enum machine_mode mode;
3137       for (mode = GET_CLASS_NARROWEST_MODE (MODE_FLOAT);
3138            mode != VOIDmode;
3139            mode = GET_MODE_WIDER_MODE (mode))
3140         FP_MODE_REG (i, mode) = gen_rtx_REG (mode, i);
3141       for (mode = GET_CLASS_NARROWEST_MODE (MODE_COMPLEX_FLOAT);
3142            mode != VOIDmode;
3143            mode = GET_MODE_WIDER_MODE (mode))
3144         FP_MODE_REG (i, mode) = gen_rtx_REG (mode, i);
3145     }
3146
3147   ix86_flags_rtx = gen_rtx_REG (CCmode, FLAGS_REG);
3148
3149   /* A QNaN for initializing uninitialized variables.
3150
3151      ??? We can't load from constant memory in PIC mode, because
3152      we're inserting these instructions before the prologue and
3153      the PIC register hasn't been set up.  In that case, fall back
3154      on zero, which we can get from `ldz'.  */
3155
3156   if ((flag_pic && !TARGET_64BIT)
3157       || ix86_cmodel == CM_LARGE || ix86_cmodel == CM_LARGE_PIC)
3158     not_a_num = CONST0_RTX (SFmode);
3159   else
3160     {
3161       not_a_num = gen_lowpart (SFmode, GEN_INT (0x7fc00000));
3162       not_a_num = force_const_mem (SFmode, not_a_num);
3163     }
3164
3165   /* Allocate a cache for stack_regs_mentioned.  */
3166   max_uid = get_max_uid ();
3167   stack_regs_mentioned_data = VEC_alloc (char, heap, max_uid + 1);
3168   memset (VEC_address (char, stack_regs_mentioned_data),
3169           0, sizeof (char) * max_uid + 1);
3170
3171   convert_regs ();
3172
3173   free_aux_for_blocks ();
3174   return true;
3175 }
3176 #endif /* STACK_REGS */
3177 \f
3178 static bool
3179 gate_handle_stack_regs (void)
3180 {
3181 #ifdef STACK_REGS
3182   return 1;
3183 #else
3184   return 0;
3185 #endif
3186 }
3187
3188 /* Convert register usage from flat register file usage to a stack
3189    register file.  */
3190 static unsigned int
3191 rest_of_handle_stack_regs (void)
3192 {
3193 #ifdef STACK_REGS
3194   if (reg_to_stack () && optimize)
3195     {
3196       regstack_completed = 1;
3197       if (cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_POST_REGSTACK
3198                        | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0))
3199           && (flag_reorder_blocks || flag_reorder_blocks_and_partition))
3200         {
3201           basic_block bb;
3202
3203           cfg_layout_initialize (0);
3204
3205           reorder_basic_blocks ();
3206           cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_POST_REGSTACK);
3207
3208           FOR_EACH_BB (bb)
3209             if (bb->next_bb != EXIT_BLOCK_PTR)
3210               bb->aux = bb->next_bb;
3211           cfg_layout_finalize ();
3212         }
3213     }
3214   else 
3215     regstack_completed = 1;
3216 #endif
3217   return 0;
3218 }
3219
3220 struct tree_opt_pass pass_stack_regs =
3221 {
3222   "stack",                              /* name */
3223   gate_handle_stack_regs,               /* gate */
3224   rest_of_handle_stack_regs,            /* execute */
3225   NULL,                                 /* sub */
3226   NULL,                                 /* next */
3227   0,                                    /* static_pass_number */
3228   TV_REG_STACK,                         /* tv_id */
3229   0,                                    /* properties_required */
3230   0,                                    /* properties_provided */
3231   0,                                    /* properties_destroyed */
3232   0,                                    /* todo_flags_start */
3233   TODO_dump_func |
3234   TODO_ggc_collect,                     /* todo_flags_finish */
3235   'k'                                   /* letter */
3236 };