OSDN Git Service

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