gcc/reg-stack.c

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