OSDN Git Service

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