gcc/reg-stack.c

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