gcc/reg-stack.c

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