gcc/reg-stack.c

   1 /* Register to Stack convert for GNU compiler.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /* This pass converts stack-like registers from the "flat register
  22    file" model that gcc uses, to a stack convention that the 387 uses.
  23
  24    * The form of the input:
  25
  26    On input, the function consists of insn that have had their
  27    registers fully allocated to a set of "virtual" registers.  Note that
  28    the word "virtual" is used differently here than elsewhere in gcc: for
  29    each virtual stack reg, there is a hard reg, but the mapping between
  30    them is not known until this pass is run.  On output, hard register
  31    numbers have been substituted, and various pop and exchange insns have
  32    been emitted.  The hard register numbers and the virtual register
  33    numbers completely overlap - before this pass, all stack register
  34    numbers are virtual, and afterward they are all hard.
  35
  36    The virtual registers can be manipulated normally by gcc, and their
  37    semantics are the same as for normal registers.  After the hard
  38    register numbers are substituted, the semantics of an insn containing
  39    stack-like regs are not the same as for an insn with normal regs: for
  40    instance, it is not safe to delete an insn that appears to be a no-op
  41    move.  In general, no insn containing hard regs should be changed
  42    after this pass is done.
  43
  44    * The form of the output:
  45
  46    After this pass, hard register numbers represent the distance from
  47    the current top of stack to the desired register.  A reference to
  48    FIRST_STACK_REG references the top of stack, FIRST_STACK_REG + 1,
  49    represents the register just below that, and so forth.  Also, REG_DEAD
  50    notes indicate whether or not a stack register should be popped.
  51
  52    A "swap" insn looks like a parallel of two patterns, where each
  53    pattern is a SET: one sets A to B, the other B to A.
  54
  55    A "push" or "load" insn is a SET whose SET_DEST is FIRST_STACK_REG
  56    and whose SET_DEST is REG or MEM.  Any other SET_DEST, such as PLUS,
  57    will replace the existing stack top, not push a new value.
  58
  59    A store insn is a SET whose SET_DEST is FIRST_STACK_REG, and whose
  60    SET_SRC is REG or MEM.
  61
  62    The case where the SET_SRC and SET_DEST are both FIRST_STACK_REG
  63    appears ambiguous.  As a special case, the presence of a REG_DEAD note
  64    for FIRST_STACK_REG differentiates between a load insn and a pop.
  65
  66    If a REG_DEAD is present, the insn represents a "pop" that discards
  67    the top of the register stack.  If there is no REG_DEAD note, then the
  68    insn represents a "dup" or a push of the current top of stack onto the
  69    stack.
  70
  71    * Methodology:
  72
  73    Existing REG_DEAD and REG_UNUSED notes for stack registers are
  74    deleted and recreated from scratch.  REG_DEAD is never created for a
  75    SET_DEST, only REG_UNUSED.
  76
  77    Before life analysis, the mode of each insn is set based on whether
  78    or not any stack registers are mentioned within that insn.  VOIDmode
  79    means that no regs are mentioned anyway, and QImode means that at
  80    least one pattern within the insn mentions stack registers.  This
  81    information is valid until after reg_to_stack returns, and is used
  82    from jump_optimize.
  83
  84    * asm_operands:
  85
  86    There are several rules on the usage of stack-like regs in
  87    asm_operands insns.  These rules apply only to the operands that are
  88    stack-like regs:
  89
  90    1. Given a set of input regs that die in an asm_operands, it is
  91       necessary to know which are implicitly popped by the asm, and
  92       which must be explicitly popped by gcc.
  93
  94         An input reg that is implicitly popped by the asm must be
  95         explicitly clobbered, unless it is constrained to match an
  96         output operand.
  97
  98    2. For any input reg that is implicitly popped by an asm, it is
  99       necessary to know how to adjust the stack to compensate for the pop.
 100       If any non-popped input is closer to the top of the reg-stack than
 101       the implicitly popped reg, it would not be possible to know what the
 102       stack looked like - it's not clear how the rest of the stack "slides
 103       up".
 104
 105         All implicitly popped input regs must be closer to the top of
 106         the reg-stack than any input that is not implicitly popped.
 107
 108    3. It is possible that if an input dies in an insn, reload might
 109       use the input reg for an output reload.  Consider this example:
 110
 111                 asm ("foo" : "=t" (a) : "f" (b));
 112
 113       This asm says that input B is not popped by the asm, and that
 114       the asm pushes a result onto the reg-stack, ie, the stack is one
 115       deeper after the asm than it was before.  But, it is possible that
 116       reload will think that it can use the same reg for both the input and
 117       the output, if input B dies in this insn.
 118
 119         If any input operand uses the "f" constraint, all output reg
 120         constraints must use the "&" earlyclobber.
 121
 122       The asm above would be written as
 123
 124                 asm ("foo" : "=&t" (a) : "f" (b));
 125
 126    4. Some operands need to be in particular places on the stack.  All
 127       output operands fall in this category - there is no other way to
 128       know which regs the outputs appear in unless the user indicates
 129       this in the constraints.
 130
 131         Output operands must specifically indicate which reg an output
 132         appears in after an asm.  "=f" is not allowed: the operand
 133         constraints must select a class with a single reg.
 134
 135    5. Output operands may not be "inserted" between existing stack regs.
 136       Since no 387 opcode uses a read/write operand, all output operands
 137       are dead before the asm_operands, and are pushed by the asm_operands.
 138       It makes no sense to push anywhere but the top of the reg-stack.
 139
 140         Output operands must start at the top of the reg-stack: output
 141         operands may not "skip" a reg.
 142
 143    6. Some asm statements may need extra stack space for internal
 144       calculations.  This can be guaranteed by clobbering stack registers
 145       unrelated to the inputs and outputs.
 146
 147    Here are a couple of reasonable asms to want to write.  This asm
 148    takes one input, which is internally popped, and produces two outputs.
 149
 150         asm ("fsincos" : "=t" (cos), "=u" (sin) : "0" (inp));
 151
 152    This asm takes two inputs, which are popped by the fyl2xp1 opcode,
 153    and replaces them with one output.  The user must code the "st(1)"
 154    clobber for reg-stack.c to know that fyl2xp1 pops both inputs.
 155
 156         asm ("fyl2xp1" : "=t" (result) : "0" (x), "u" (y) : "st(1)");
 157
 158    */
 159 \f
 160 #include <stdio.h>
 161 #include "config.h"
 162 #include "tree.h"
 163 #include "rtl.h"
 164 #include "insn-config.h"
 165 #include "regs.h"
 166 #include "hard-reg-set.h"
 167 #include "flags.h"
 168 #include "insn-flags.h"
 169
 170 #ifdef STACK_REGS
 171
 172 #define REG_STACK_SIZE (LAST_STACK_REG - FIRST_STACK_REG + 1)
 173
 174 /* This is the basic stack record.  TOP is an index into REG[] such
 175    that REG[TOP] is the top of stack.  If TOP is -1 the stack is empty.
 176
 177    If TOP is -2, REG[] is not yet initialized.  Stack initialization
 178    consists of placing each live reg in array `reg' and setting `top'
 179    appropriately.
 180
 181    REG_SET indicates which registers are live.  */
 182
 183 typedef struct stack_def
 184 {
 185   int top;                      /* index to top stack element */
 186   HARD_REG_SET reg_set;         /* set of live registers */
 187   char reg[REG_STACK_SIZE];     /* register - stack mapping */
 188 } *stack;
 189
 190 /* highest instruction uid */
 191 static int max_uid = 0;
 192
 193 /* Number of basic blocks in the current function.  */
 194 static int blocks;
 195
 196 /* Element N is first insn in basic block N.
 197    This info lasts until we finish compiling the function.  */
 198 static rtx *block_begin;
 199
 200 /* Element N is last insn in basic block N.
 201    This info lasts until we finish compiling the function.  */
 202 static rtx *block_end;
 203
 204 /* Element N is nonzero if control can drop into basic block N */
 205 static char *block_drops_in;
 206
 207 /* Element N says all about the stack at entry block N */
 208 static stack block_stack_in;
 209
 210 /* Element N says all about the stack life at the end of block N */
 211 static HARD_REG_SET *block_out_reg_set;
 212
 213 /* This is where the BLOCK_NUM values are really stored.  This is set
 214    up by find_blocks and used there and in life_analysis.  It can be used
 215    later, but only to look up an insn that is the head or tail of some
 216    block.  life_analysis and the stack register conversion process can
 217    add insns within a block.  */
 218 static int *block_number;
 219
 220 /* This is the register file for all register after conversion */
 221 static rtx
 222   FP_mode_reg[LAST_STACK_REG+1-FIRST_STACK_REG][(int) MAX_MACHINE_MODE];
 223
 224 #define FP_MODE_REG(regno,mode) \
 225   (FP_mode_reg[(regno)-FIRST_STACK_REG][(int)(mode)])
 226
 227 /* Get the basic block number of an insn.  See note at block_number
 228    definition are validity of this information.  */
 229
 230 #define BLOCK_NUM(INSN)  \
 231   ((INSN_UID (INSN) > max_uid)  \
 232    ? (abort() , -1) : block_number[INSN_UID (INSN)])
 233
 234 extern rtx forced_labels;
 235
 236 /* Forward declarations */
 237
 238 static void mark_regs_pat               PROTO((rtx, HARD_REG_SET *));
 239 static void straighten_stack            PROTO((rtx, stack));
 240 static void record_label_references     PROTO((rtx, rtx));
 241 static rtx *get_true_reg                PROTO((rtx *));
 242 static int constrain_asm_operands       PROTO((int, rtx *, char **, int *,
 243                                                enum reg_class *));
 244
 245 static void record_asm_reg_life         PROTO((rtx,stack, rtx *, char **,
 246                                                int, int));
 247 static void record_reg_life_pat         PROTO((rtx, HARD_REG_SET *,
 248                                                HARD_REG_SET *, int));
 249 static void get_asm_operand_length      PROTO((rtx, int, int *, int *));
 250 static void record_reg_life             PROTO((rtx, int, stack));
 251 static void find_blocks                 PROTO((rtx));
 252 static int uses_reg_or_mem              PROTO((rtx));
 253 static rtx stack_result                 PROTO((tree));
 254 static void stack_reg_life_analysis     PROTO((rtx, HARD_REG_SET *));
 255 static void replace_reg                 PROTO((rtx *, int));
 256 static void remove_regno_note           PROTO((rtx, enum reg_note, int));
 257 static int get_hard_regnum              PROTO((stack, rtx));
 258 static void delete_insn_for_stacker     PROTO((rtx));
 259 static rtx emit_pop_insn                PROTO((rtx, stack, rtx, rtx (*) ()));
 260 static void emit_swap_insn              PROTO((rtx, stack, rtx));
 261 static void move_for_stack_reg          PROTO((rtx, stack, rtx));
 262 static void swap_rtx_condition          PROTO((rtx));
 263 static void compare_for_stack_reg       PROTO((rtx, stack, rtx));
 264 static void subst_stack_regs_pat        PROTO((rtx, stack, rtx));
 265 static void subst_asm_stack_regs        PROTO((rtx, stack, rtx *, rtx **,
 266                                                char **, int, int));
 267 static void subst_stack_regs            PROTO((rtx, stack));
 268 static void change_stack                PROTO((rtx, stack, stack, rtx (*) ()));
 269
 270 static void goto_block_pat              PROTO((rtx, stack, rtx));
 271 static void convert_regs                PROTO((void));
 272 static void print_blocks                PROTO((FILE *, rtx, rtx));
 273 static void dump_stack_info             PROTO((FILE *));
 274 \f
 275 /* Mark all registers needed for this pattern.  */
 276
 277 static void
 278 mark_regs_pat (pat, set)
 279      rtx pat;
 280      HARD_REG_SET *set;
 281 {
 282   enum machine_mode mode;
 283   register int regno;
 284   register int count;
 285
 286   if (GET_CODE (pat) == SUBREG)
 287    {
 288      mode = GET_MODE (pat);
 289      regno = SUBREG_WORD (pat);
 290      regno += REGNO (SUBREG_REG (pat));
 291    }
 292   else
 293      regno = REGNO (pat), mode = GET_MODE (pat);
 294
 295   for (count = HARD_REGNO_NREGS (regno, mode);
 296        count; count--, regno++)
 297      SET_HARD_REG_BIT (*set, regno);
 298 }
 299 \f
 300 /* Reorganise the stack into ascending numbers,
 301    after this insn.  */
 302
 303 static void
 304 straighten_stack (insn, regstack)
 305      rtx insn;
 306      stack regstack;
 307 {
 308   struct stack_def temp_stack;
 309   int top;
 310
 311   temp_stack.reg_set = regstack->reg_set;
 312
 313   for (top = temp_stack.top = regstack->top; top >= 0; top--)
 314      temp_stack.reg[top] = FIRST_STACK_REG + temp_stack.top - top;
 315
 316   change_stack (insn, regstack, &temp_stack, emit_insn_after);
 317 }
 318 \f
 319 /* Return non-zero if any stack register is mentioned somewhere within PAT.  */
 320
 321 int
 322 stack_regs_mentioned_p (pat)
 323      rtx pat;
 324 {
 325   register char *fmt;
 326   register int i;
 327
 328   if (STACK_REG_P (pat))
 329     return 1;
 330
 331   fmt = GET_RTX_FORMAT (GET_CODE (pat));
 332   for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
 333     {
 334       if (fmt[i] == 'E')
 335         {
 336           register int j;
 337
 338           for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
 339             if (stack_regs_mentioned_p (XVECEXP (pat, i, j)))
 340               return 1;
 341         }
 342       else if (fmt[i] == 'e' && stack_regs_mentioned_p (XEXP (pat, i)))
 343         return 1;
 344     }
 345
 346   return 0;
 347 }
 348 \f
 349 /* Convert register usage from "flat" register file usage to a "stack
 350    register file.  FIRST is the first insn in the function, FILE is the
 351    dump file, if used.
 352
 353    First compute the beginning and end of each basic block.  Do a
 354    register life analysis on the stack registers, recording the result
 355    for the head and tail of each basic block.  The convert each insn one
 356    by one.  Run a last jump_optimize() pass, if optimizing, to eliminate
 357    any cross-jumping created when the converter inserts pop insns.*/
 358
 359 void
 360 reg_to_stack (first, file)
 361      rtx first;
 362      FILE *file;
 363 {
 364   register rtx insn;
 365   register int i;
 366   int stack_reg_seen = 0;
 367   enum machine_mode mode;
 368   HARD_REG_SET stackentry;
 369
 370   CLEAR_HARD_REG_SET (stackentry);
 371
 372    {
 373      static initialised;
 374      if (!initialised)
 375       {
 376 #if 0
 377         initialised = 1;        /* This array can not have been previously
 378                                    initialised, because the rtx's are
 379                                    thrown away between compilations of
 380                                    functions.  */
 381 #endif
 382         for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
 383          {
 384            for (mode = GET_CLASS_NARROWEST_MODE (MODE_FLOAT); mode != VOIDmode;
 385                mode = GET_MODE_WIDER_MODE (mode))
 386               FP_MODE_REG (i, mode) = gen_rtx (REG, mode, i);
 387            for (mode = GET_CLASS_NARROWEST_MODE (MODE_COMPLEX_FLOAT); mode != VOIDmode;
 388                mode = GET_MODE_WIDER_MODE (mode))
 389               FP_MODE_REG (i, mode) = gen_rtx (REG, mode, i);
 390          }
 391       }
 392    }
 393
 394   /* Count the basic blocks.  Also find maximum insn uid.  */
 395   {
 396     register RTX_CODE prev_code = BARRIER;
 397     register RTX_CODE code;
 398     register before_function_beg = 1;
 399
 400     max_uid = 0;
 401     blocks = 0;
 402     for (insn = first; insn; insn = NEXT_INSN (insn))
 403       {
 404         /* Note that this loop must select the same block boundaries
 405            as code in find_blocks.  Also note that this code is not the
 406            same as that used in flow.c.  */
 407
 408         if (INSN_UID (insn) > max_uid)
 409           max_uid = INSN_UID (insn);
 410
 411         code = GET_CODE (insn);
 412
 413         if (code == CODE_LABEL
 414             || (prev_code != INSN
 415                 && prev_code != CALL_INSN
 416                 && prev_code != CODE_LABEL
 417                 && GET_RTX_CLASS (code) == 'i'))
 418           blocks++;
 419
 420         if (code == NOTE && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
 421            before_function_beg = 0;
 422
 423         /* Remember whether or not this insn mentions an FP regs.
 424            Check JUMP_INSNs too, in case someone creates a funny PARALLEL.  */
 425
 426         if (GET_RTX_CLASS (code) == 'i'
 427             && stack_regs_mentioned_p (PATTERN (insn)))
 428           {
 429             stack_reg_seen = 1;
 430             PUT_MODE (insn, QImode);
 431
 432             /* Note any register passing parameters.  */
 433
 434             if (before_function_beg && code == INSN
 435                 && GET_CODE (PATTERN (insn)) == USE)
 436               record_reg_life_pat (PATTERN (insn), (HARD_REG_SET *) 0,
 437                                    &stackentry, 1);
 438           }
 439         else
 440           PUT_MODE (insn, VOIDmode);
 441
 442         if (code == CODE_LABEL)
 443           LABEL_REFS (insn) = insn; /* delete old chain */
 444
 445         if (code != NOTE)
 446           prev_code = code;
 447       }
 448   }
 449
 450   /* If no stack register reference exists in this insn, there isn't
 451      anything to convert.  */
 452
 453   if (! stack_reg_seen)
 454     return;
 455
 456   /* If there are stack registers, there must be at least one block.  */
 457
 458   if (! blocks)
 459     abort ();
 460
 461   /* Allocate some tables that last till end of compiling this function
 462      and some needed only in find_blocks and life_analysis.  */
 463
 464   block_begin = (rtx *) alloca (blocks * sizeof (rtx));
 465   block_end = (rtx *) alloca (blocks * sizeof (rtx));
 466   block_drops_in = (char *) alloca (blocks);
 467
 468   block_stack_in = (stack) alloca (blocks * sizeof (struct stack_def));
 469   block_out_reg_set = (HARD_REG_SET *) alloca (blocks * sizeof (HARD_REG_SET));
 470   bzero ((char *) block_stack_in, blocks * sizeof (struct stack_def));
 471   bzero ((char *) block_out_reg_set, blocks * sizeof (HARD_REG_SET));
 472
 473   block_number = (int *) alloca ((max_uid + 1) * sizeof (int));
 474
 475   find_blocks (first);
 476   stack_reg_life_analysis (first, &stackentry);
 477
 478   /* Dump the life analysis debug information before jump
 479      optimization, as that will destroy the LABEL_REFS we keep the
 480      information in.  */
 481
 482   if (file)
 483     dump_stack_info (file);
 484
 485   convert_regs ();
 486
 487   if (optimize)
 488     jump_optimize (first, 2, 0, 0);
 489 }
 490 \f
 491 /* Check PAT, which is in INSN, for LABEL_REFs.  Add INSN to the
 492    label's chain of references, and note which insn contains each
 493    reference.  */
 494
 495 static void
 496 record_label_references (insn, pat)
 497      rtx insn, pat;
 498 {
 499   register enum rtx_code code = GET_CODE (pat);
 500   register int i;
 501   register char *fmt;
 502
 503   if (code == LABEL_REF)
 504     {
 505       register rtx label = XEXP (pat, 0);
 506       register rtx ref;
 507
 508       if (GET_CODE (label) != CODE_LABEL)
 509         abort ();
 510
 511       /* If this is an undefined label, LABEL_REFS (label) contains
 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           int computed_jump = 0;
1356           rtx x;
1357
1358           if (GET_CODE (pat) == PARALLEL)
1359             {
1360               int len = XVECLEN (pat, 0);
1361               int has_use_labelref = 0;
1362               int i;
1363
1364               for (i = len - 1; i >= 0; i--)
1365                 if (GET_CODE (XVECEXP (pat, 0, i)) == USE
1366                     && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == LABEL_REF)
1367                   has_use_labelref = 1;
1368
1369               if (! has_use_labelref)
1370                 for (i = len - 1; i >= 0; i--)
1371                   if (GET_CODE (XVECEXP (pat, 0, i)) == SET
1372                       && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
1373                       && uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
1374                     computed_jump = 1;
1375             }
1376           else if (GET_CODE (pat) == SET
1377                    && SET_DEST (pat) == pc_rtx
1378                    && uses_reg_or_mem (SET_SRC (pat)))
1379             computed_jump = 1;
1380
1381           if (computed_jump)
1382             {
1383               for (x = label_value_list; x; x = XEXP (x, 1))
1384                 record_label_references (insn,
1385                                          gen_rtx (LABEL_REF, VOIDmode,
1386                                                   XEXP (x, 0)));
1387
1388               for (x = forced_labels; x; x = XEXP (x, 1))
1389                 record_label_references (insn,
1390                                          gen_rtx (LABEL_REF, VOIDmode,
1391                                                   XEXP (x, 0)));
1392             }
1393
1394           record_label_references (insn, pat);
1395         }
1396     }
1397 }
1398
1399 /* Return 1 if X contain a REG or MEM that is not in the constant pool.  */
1400
1401 static int
1402 uses_reg_or_mem (x)
1403      rtx x;
1404 {
1405   enum rtx_code code = GET_CODE (x);
1406   int i, j;
1407   char *fmt;
1408
1409   if (code == REG
1410       || (code == MEM
1411           && ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
1412                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))))
1413     return 1;
1414
1415   fmt = GET_RTX_FORMAT (code);
1416   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1417     {
1418       if (fmt[i] == 'e'
1419           && uses_reg_or_mem (XEXP (x, i)))
1420         return 1;
1421
1422       if (fmt[i] == 'E')
1423         for (j = 0; j < XVECLEN (x, i); j++)
1424           if (uses_reg_or_mem (XVECEXP (x, i, j)))
1425             return 1;
1426     }
1427
1428   return 0;
1429 }
1430
1431 /* If current function returns its result in an fp stack register,
1432    return the REG.  Otherwise, return 0.  */
1433
1434 static rtx
1435 stack_result (decl)
1436      tree decl;
1437 {
1438   rtx result = DECL_RTL (DECL_RESULT (decl));
1439
1440   if (result != 0
1441       && ! (GET_CODE (result) == REG
1442             && REGNO (result) < FIRST_PSEUDO_REGISTER))
1443     {
1444 #ifdef FUNCTION_OUTGOING_VALUE
1445       result
1446         = FUNCTION_OUTGOING_VALUE (TREE_TYPE (DECL_RESULT (decl)), decl);
1447 #else
1448       result = FUNCTION_VALUE (TREE_TYPE (DECL_RESULT (decl)), decl);
1449 #endif
1450     }
1451
1452   return result != 0 && STACK_REG_P (result) ? result : 0;
1453 }
1454 \f
1455 /* Determine the which registers are live at the start of each basic
1456    block of the function whose first insn is FIRST.
1457
1458    First, if the function returns a real_type, mark the function
1459    return type as live at each return point, as the RTL may not give any
1460    hint that the register is live.
1461
1462    Then, start with the last block and work back to the first block.
1463    Similarly, work backwards within each block, insn by insn, recording
1464    which regs are dead and which are used (and therefore live) in the
1465    hard reg set of block_stack_in[].
1466
1467    After processing each basic block, if there is a label at the start
1468    of the block, propagate the live registers to all jumps to this block.
1469
1470    As a special case, if there are regs live in this block, that are
1471    not live in a block containing a jump to this label, and the block
1472    containing the jump has already been processed, we must propagate this
1473    block's entry register life back to the block containing the jump, and
1474    restart life analysis from there.
1475
1476    In the worst case, this function may traverse the insns
1477    REG_STACK_SIZE times.  This is necessary, since a jump towards the end
1478    of the insns may not know that a reg is live at a target that is early
1479    in the insns.  So we back up and start over with the new reg live.
1480
1481    If there are registers that are live at the start of the function,
1482    insns are emitted to initialize these registers.  Something similar is
1483    done after CALL_INSNs in record_reg_life.  */
1484
1485 static void
1486 stack_reg_life_analysis (first, stackentry)
1487      rtx first;
1488      HARD_REG_SET *stackentry;
1489 {
1490   int reg, block;
1491   struct stack_def regstack;
1492
1493    {
1494      rtx retvalue;
1495
1496      if (retvalue = stack_result (current_function_decl))
1497       {
1498         /* Find all RETURN insns and mark them.  */
1499
1500         for (block = blocks - 1; --block >= 0;)
1501            if (GET_CODE (block_end[block]) == JUMP_INSN
1502              && GET_CODE (PATTERN (block_end[block])) == RETURN)
1503               mark_regs_pat (retvalue, block_out_reg_set+block);
1504
1505         /* Mark off the end of last block if we "fall off" the end of the
1506            function into the epilogue.  */
1507
1508         if (GET_CODE (block_end[blocks-1]) != JUMP_INSN
1509             || GET_CODE (PATTERN (block_end[blocks-1])) == RETURN)
1510           mark_regs_pat (retvalue, block_out_reg_set+blocks-1);
1511       }
1512    }
1513
1514   /* now scan all blocks backward for stack register use */
1515
1516   block = blocks - 1;
1517   while (block >= 0)
1518     {
1519       register rtx insn, prev;
1520
1521       /* current register status at last instruction */
1522
1523       COPY_HARD_REG_SET (regstack.reg_set, block_out_reg_set[block]);
1524
1525       prev = block_end[block];
1526       do
1527         {
1528           insn = prev;
1529           prev = PREV_INSN (insn);
1530
1531           /* If the insn is a CALL_INSN, we need to ensure that
1532              everything dies.  But otherwise don't process unless there
1533              are some stack regs present.  */
1534
1535           if (GET_MODE (insn) == QImode || GET_CODE (insn) == CALL_INSN)
1536             record_reg_life (insn, block, &regstack);
1537
1538         } while (insn != block_begin[block]);
1539
1540       /* Set the state at the start of the block.  Mark that no
1541          register mapping information known yet.  */
1542
1543       COPY_HARD_REG_SET (block_stack_in[block].reg_set, regstack.reg_set);
1544       block_stack_in[block].top = -2;
1545
1546       /* If there is a label, propagate our register life to all jumps
1547          to this label.  */
1548
1549       if (GET_CODE (insn) == CODE_LABEL)
1550         {
1551           register rtx label;
1552           int must_restart = 0;
1553
1554           for (label = LABEL_REFS (insn); label != insn;
1555                label = LABEL_NEXTREF (label))
1556             {
1557               int jump_block = BLOCK_NUM (CONTAINING_INSN (label));
1558
1559               if (jump_block < block)
1560                 IOR_HARD_REG_SET (block_out_reg_set[jump_block],
1561                                   block_stack_in[block].reg_set);
1562               else
1563                 {
1564                   /* The block containing the jump has already been
1565                      processed.  If there are registers that were not known
1566                      to be live then, but are live now, we must back up
1567                      and restart life analysis from that point with the new
1568                      life information.  */
1569
1570                   GO_IF_HARD_REG_SUBSET (block_stack_in[block].reg_set,
1571                                          block_out_reg_set[jump_block],
1572                                          win);
1573
1574                   IOR_HARD_REG_SET (block_out_reg_set[jump_block],
1575                                     block_stack_in[block].reg_set);
1576
1577                   block = jump_block;
1578                   must_restart = 1;
1579
1580                 win:
1581                   ;
1582                 }
1583             }
1584           if (must_restart)
1585             continue;
1586         }
1587
1588       if (block_drops_in[block])
1589         IOR_HARD_REG_SET (block_out_reg_set[block-1],
1590                           block_stack_in[block].reg_set);
1591
1592       block -= 1;
1593     }
1594
1595     /* If any reg is live at the start of the first block of a
1596        function, then we must guarantee that the reg holds some value by
1597        generating our own "load" of that register.  Otherwise a 387 would
1598        fault trying to access an empty register.  */
1599
1600   /* Load zero into each live register.  The fact that a register
1601      appears live at the function start necessarily implies an error
1602      in the user program: it means that (unless the offending code is *never*
1603      executed) this program is using uninitialised floating point
1604      variables.  In order to keep broken code like this happy, we initialise
1605      those variables with zero.
1606
1607      Note that we are inserting virtual register references here:
1608      these insns must be processed by convert_regs later.  Also, these
1609      insns will not be in block_number, so BLOCK_NUM() will fail for them.  */
1610
1611   for (reg = LAST_STACK_REG; reg >= FIRST_STACK_REG; reg--)
1612     if (TEST_HARD_REG_BIT (block_stack_in[0].reg_set, reg)
1613         && ! TEST_HARD_REG_BIT (*stackentry, reg))
1614       {
1615         rtx init_rtx;
1616
1617         init_rtx = gen_rtx (SET, VOIDmode, FP_MODE_REG(reg, DFmode),
1618                             CONST0_RTX (DFmode));
1619         block_begin[0] = emit_insn_after (init_rtx, first);
1620         PUT_MODE (block_begin[0], QImode);
1621
1622         CLEAR_HARD_REG_BIT (block_stack_in[0].reg_set, reg);
1623       }
1624 }
1625 \f
1626 /*****************************************************************************
1627    This section deals with stack register substitution, and forms the second
1628    pass over the RTL.
1629  *****************************************************************************/
1630
1631 /* Replace REG, which is a pointer to a stack reg RTX, with an RTX for
1632    the desired hard REGNO.  */
1633
1634 static void
1635 replace_reg (reg, regno)
1636      rtx *reg;
1637      int regno;
1638 {
1639   if (regno < FIRST_STACK_REG || regno > LAST_STACK_REG
1640       || ! STACK_REG_P (*reg))
1641     abort ();
1642
1643   switch (GET_MODE_CLASS (GET_MODE (*reg)))
1644    {
1645      default: abort ();
1646      case MODE_FLOAT:
1647      case MODE_COMPLEX_FLOAT:;
1648    }
1649
1650   *reg = FP_MODE_REG (regno, GET_MODE (*reg));
1651 }
1652
1653 /* Remove a note of type NOTE, which must be found, for register
1654    number REGNO from INSN.  Remove only one such note.  */
1655
1656 static void
1657 remove_regno_note (insn, note, regno)
1658      rtx insn;
1659      enum reg_note note;
1660      int regno;
1661 {
1662   register rtx *note_link, this;
1663
1664   note_link = &REG_NOTES(insn);
1665   for (this = *note_link; this; this = XEXP (this, 1))
1666     if (REG_NOTE_KIND (this) == note
1667         && REG_P (XEXP (this, 0)) && REGNO (XEXP (this, 0)) == regno)
1668       {
1669         *note_link = XEXP (this, 1);
1670         return;
1671       }
1672     else
1673       note_link = &XEXP (this, 1);
1674
1675   abort ();
1676 }
1677
1678 /* Find the hard register number of virtual register REG in REGSTACK.
1679    The hard register number is relative to the top of the stack.  -1 is
1680    returned if the register is not found.  */
1681
1682 static int
1683 get_hard_regnum (regstack, reg)
1684      stack regstack;
1685      rtx reg;
1686 {
1687   int i;
1688
1689   if (! STACK_REG_P (reg))
1690     abort ();
1691
1692   for (i = regstack->top; i >= 0; i--)
1693     if (regstack->reg[i] == REGNO (reg))
1694       break;
1695
1696   return i >= 0 ? (FIRST_STACK_REG + regstack->top - i) : -1;
1697 }
1698
1699 /* Delete INSN from the RTL.  Mark the insn, but don't remove it from
1700    the chain of insns.  Doing so could confuse block_begin and block_end
1701    if this were the only insn in the block.  */
1702
1703 static void
1704 delete_insn_for_stacker (insn)
1705      rtx insn;
1706 {
1707   PUT_CODE (insn, NOTE);
1708   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1709   NOTE_SOURCE_FILE (insn) = 0;
1710 }
1711 \f
1712 /* Emit an insn to pop virtual register REG before or after INSN.
1713    REGSTACK is the stack state after INSN and is updated to reflect this
1714    pop.  WHEN is either emit_insn_before or emit_insn_after.  A pop insn
1715    is represented as a SET whose destination is the register to be popped
1716    and source is the top of stack.  A death note for the top of stack
1717    cases the movdf pattern to pop.  */
1718
1719 static rtx
1720 emit_pop_insn (insn, regstack, reg, when)
1721      rtx insn;
1722      stack regstack;
1723      rtx reg;
1724      rtx (*when)();
1725 {
1726   rtx pop_insn, pop_rtx;
1727   int hard_regno;
1728
1729   hard_regno = get_hard_regnum (regstack, reg);
1730
1731   if (hard_regno < FIRST_STACK_REG)
1732     abort ();
1733
1734   pop_rtx = gen_rtx (SET, VOIDmode, FP_MODE_REG (hard_regno, DFmode),
1735                      FP_MODE_REG (FIRST_STACK_REG, DFmode));
1736
1737   pop_insn = (*when) (pop_rtx, insn);
1738   /* ??? This used to be VOIDmode, but that seems wrong.  */
1739   PUT_MODE (pop_insn, QImode);
1740
1741   REG_NOTES (pop_insn) = gen_rtx (EXPR_LIST, REG_DEAD,
1742                                   FP_MODE_REG (FIRST_STACK_REG, DFmode),
1743                                   REG_NOTES (pop_insn));
1744
1745   regstack->reg[regstack->top - (hard_regno - FIRST_STACK_REG)]
1746     = regstack->reg[regstack->top];
1747   regstack->top -= 1;
1748   CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (reg));
1749
1750   return pop_insn;
1751 }
1752 \f
1753 /* Emit an insn before or after INSN to swap virtual register REG with the
1754    top of stack.  WHEN should be `emit_insn_before' or `emit_insn_before'
1755    REGSTACK is the stack state before the swap, and is updated to reflect
1756    the swap.  A swap insn is represented as a PARALLEL of two patterns:
1757    each pattern moves one reg to the other.
1758
1759    If REG is already at the top of the stack, no insn is emitted.  */
1760
1761 static void
1762 emit_swap_insn (insn, regstack, reg)
1763      rtx insn;
1764      stack regstack;
1765      rtx reg;
1766 {
1767   int hard_regno;
1768   rtx gen_swapdf();
1769   rtx swap_rtx, swap_insn;
1770   int tmp, other_reg;           /* swap regno temps */
1771   rtx i1;                       /* the stack-reg insn prior to INSN */
1772   rtx i1set = NULL_RTX;         /* the SET rtx within I1 */
1773
1774   hard_regno = get_hard_regnum (regstack, reg);
1775
1776   if (hard_regno < FIRST_STACK_REG)
1777     abort ();
1778   if (hard_regno == FIRST_STACK_REG)
1779     return;
1780
1781   other_reg = regstack->top - (hard_regno - FIRST_STACK_REG);
1782
1783   tmp = regstack->reg[other_reg];
1784   regstack->reg[other_reg] = regstack->reg[regstack->top];
1785   regstack->reg[regstack->top] = tmp;
1786
1787   /* Find the previous insn involving stack regs, but don't go past
1788      any labels, calls or jumps.  */
1789   i1 = prev_nonnote_insn (insn);
1790   while (i1 && GET_CODE (i1) == INSN && GET_MODE (i1) != QImode)
1791     i1 = prev_nonnote_insn (i1);
1792
1793   if (i1)
1794     i1set = single_set (i1);
1795
1796   if (i1set)
1797     {
1798       rtx i2;                   /* the stack-reg insn prior to I1 */
1799       rtx i1src = *get_true_reg (&SET_SRC (i1set));
1800       rtx i1dest = *get_true_reg (&SET_DEST (i1set));
1801
1802       /* If the previous register stack push was from the reg we are to
1803          swap with, omit the swap.  */
1804
1805       if (GET_CODE (i1dest) == REG && REGNO (i1dest) == FIRST_STACK_REG
1806           && GET_CODE (i1src) == REG && REGNO (i1src) == hard_regno - 1
1807           && find_regno_note (i1, REG_DEAD, FIRST_STACK_REG) == NULL_RTX)
1808         return;
1809
1810       /* If the previous insn wrote to the reg we are to swap with,
1811          omit the swap.  */
1812
1813       if (GET_CODE (i1dest) == REG && REGNO (i1dest) == hard_regno
1814           && GET_CODE (i1src) == REG && REGNO (i1src) == FIRST_STACK_REG
1815           && find_regno_note (i1, REG_DEAD, FIRST_STACK_REG) == NULL_RTX)
1816         return;
1817     }
1818
1819   if (GET_RTX_CLASS (GET_CODE (i1)) == 'i' && sets_cc0_p (PATTERN (i1)))
1820     {
1821       i1 = next_nonnote_insn (i1);
1822       if (i1 == insn)
1823         abort ();
1824     }
1825
1826   swap_rtx = gen_swapdf (FP_MODE_REG (hard_regno, DFmode),
1827                          FP_MODE_REG (FIRST_STACK_REG, DFmode));
1828   swap_insn = emit_insn_after (swap_rtx, i1);
1829   /* ??? This used to be VOIDmode, but that seems wrong.  */
1830   PUT_MODE (swap_insn, QImode);
1831 }
1832 \f
1833 /* Handle a move to or from a stack register in PAT, which is in INSN.
1834    REGSTACK is the current stack.  */
1835
1836 static void
1837 move_for_stack_reg (insn, regstack, pat)
1838      rtx insn;
1839      stack regstack;
1840      rtx pat;
1841 {
1842   rtx *psrc =  get_true_reg (&SET_SRC (pat));
1843   rtx *pdest = get_true_reg (&SET_DEST (pat));
1844   rtx src, dest;
1845   rtx note;
1846
1847   src = *psrc; dest = *pdest;
1848
1849   if (STACK_REG_P (src) && STACK_REG_P (dest))
1850     {
1851       /* Write from one stack reg to another.  If SRC dies here, then
1852          just change the register mapping and delete the insn.  */
1853
1854       note = find_regno_note (insn, REG_DEAD, REGNO (src));
1855       if (note)
1856         {
1857           int i;
1858
1859           /* If this is a no-op move, there must not be a REG_DEAD note.  */
1860           if (REGNO (src) == REGNO (dest))
1861             abort ();
1862
1863           for (i = regstack->top; i >= 0; i--)
1864             if (regstack->reg[i] == REGNO (src))
1865               break;
1866
1867           /* The source must be live, and the dest must be dead.  */
1868           if (i < 0 || get_hard_regnum (regstack, dest) >= FIRST_STACK_REG)
1869             abort ();
1870
1871           /* It is possible that the dest is unused after this insn.
1872              If so, just pop the src.  */
1873
1874           if (find_regno_note (insn, REG_UNUSED, REGNO (dest)))
1875             {
1876               emit_pop_insn (insn, regstack, src, emit_insn_after);
1877
1878               delete_insn_for_stacker (insn);
1879               return;
1880             }
1881
1882           regstack->reg[i] = REGNO (dest);
1883
1884           SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1885           CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (src));
1886
1887           delete_insn_for_stacker (insn);
1888
1889           return;
1890         }
1891
1892       /* The source reg does not die.  */
1893
1894       /* If this appears to be a no-op move, delete it, or else it
1895          will confuse the machine description output patterns. But if
1896          it is REG_UNUSED, we must pop the reg now, as per-insn processing
1897          for REG_UNUSED will not work for deleted insns.  */
1898
1899       if (REGNO (src) == REGNO (dest))
1900         {
1901           if (find_regno_note (insn, REG_UNUSED, REGNO (dest)))
1902             emit_pop_insn (insn, regstack, dest, emit_insn_after);
1903
1904           delete_insn_for_stacker (insn);
1905           return;
1906         }
1907
1908       /* The destination ought to be dead */
1909       if (get_hard_regnum (regstack, dest) >= FIRST_STACK_REG)
1910         abort ();
1911
1912       replace_reg (psrc, get_hard_regnum (regstack, src));
1913
1914       regstack->reg[++regstack->top] = REGNO (dest);
1915       SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1916       replace_reg (pdest, FIRST_STACK_REG);
1917     }
1918   else if (STACK_REG_P (src))
1919     {
1920       /* Save from a stack reg to MEM, or possibly integer reg.  Since
1921          only top of stack may be saved, emit an exchange first if
1922          needs be.  */
1923
1924       emit_swap_insn (insn, regstack, src);
1925
1926       note = find_regno_note (insn, REG_DEAD, REGNO (src));
1927       if (note)
1928         {
1929           replace_reg (&XEXP (note, 0), FIRST_STACK_REG);
1930           regstack->top--;
1931           CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (src));
1932         }
1933       else if (GET_MODE (src) == XFmode && regstack->top < REG_STACK_SIZE - 1)
1934         {
1935           /* A 387 cannot write an XFmode value to a MEM without
1936              clobbering the source reg.  The output code can handle
1937              this by reading back the value from the MEM.
1938              But it is more efficient to use a temp register if one is
1939              available.  Push the source value here if the register
1940              stack is not full, and then write the value to memory via
1941              a pop.  */
1942           rtx push_rtx, push_insn;
1943           rtx top_stack_reg = FP_MODE_REG (FIRST_STACK_REG, XFmode);
1944
1945           push_rtx = gen_movxf (top_stack_reg, top_stack_reg);
1946           push_insn = emit_insn_before (push_rtx, insn);
1947           PUT_MODE (push_insn, QImode);
1948           REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_DEAD, top_stack_reg,
1949                                       REG_NOTES (insn));
1950         }
1951
1952       replace_reg (psrc, FIRST_STACK_REG);
1953     }
1954   else if (STACK_REG_P (dest))
1955     {
1956       /* Load from MEM, or possibly integer REG or constant, into the
1957          stack regs.  The actual target is always the top of the
1958          stack. The stack mapping is changed to reflect that DEST is
1959          now at top of stack.  */
1960
1961       /* The destination ought to be dead */
1962       if (get_hard_regnum (regstack, dest) >= FIRST_STACK_REG)
1963         abort ();
1964
1965       if (regstack->top >= REG_STACK_SIZE)
1966         abort ();
1967
1968       regstack->reg[++regstack->top] = REGNO (dest);
1969       SET_HARD_REG_BIT (regstack->reg_set, REGNO (dest));
1970       replace_reg (pdest, FIRST_STACK_REG);
1971     }
1972   else
1973     abort ();
1974 }
1975 \f
1976 static void
1977 swap_rtx_condition (pat)
1978      rtx pat;
1979 {
1980   register char *fmt;
1981   register int i;
1982
1983   if (GET_RTX_CLASS (GET_CODE (pat)) == '<')
1984     {
1985       PUT_CODE (pat, swap_condition (GET_CODE (pat)));
1986       return;
1987     }
1988
1989   fmt = GET_RTX_FORMAT (GET_CODE (pat));
1990   for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
1991     {
1992       if (fmt[i] == 'E')
1993         {
1994           register int j;
1995
1996           for (j = XVECLEN (pat, i) - 1; j >= 0; j--)
1997             swap_rtx_condition (XVECEXP (pat, i, j));
1998         }
1999       else if (fmt[i] == 'e')
2000         swap_rtx_condition (XEXP (pat, i));
2001     }
2002 }
2003
2004 /* Handle a comparison.  Special care needs to be taken to avoid
2005    causing comparisons that a 387 cannot do correctly, such as EQ.
2006
2007    Also, a pop insn may need to be emitted.  The 387 does have an
2008    `fcompp' insn that can pop two regs, but it is sometimes too expensive
2009    to do this - a `fcomp' followed by a `fstpl %st(0)' may be easier to
2010    set up.  */
2011
2012 static void
2013 compare_for_stack_reg (insn, regstack, pat)
2014      rtx insn;
2015      stack regstack;
2016      rtx pat;
2017 {
2018   rtx *src1, *src2;
2019   rtx src1_note, src2_note;
2020   rtx cc0_user;
2021
2022   src1 = get_true_reg (&XEXP (SET_SRC (pat), 0));
2023   src2 = get_true_reg (&XEXP (SET_SRC (pat), 1));
2024   cc0_user = next_cc0_user (insn);
2025
2026   /* If the insn that uses cc0 is a conditional move, then the destination
2027      must be the top of stack */
2028   if (GET_CODE (PATTERN (cc0_user)) == SET
2029       && SET_DEST (PATTERN (cc0_user)) != pc_rtx
2030       && GET_CODE (SET_SRC (PATTERN (cc0_user))) == IF_THEN_ELSE)
2031     {
2032       rtx *dest, src_note;
2033
2034       dest = get_true_reg (&SET_DEST (PATTERN (cc0_user)));
2035       if (REGNO (*dest) != regstack->reg[regstack->top])
2036         {
2037           emit_swap_insn (insn, regstack, *dest);
2038         }
2039     }
2040
2041   /* ??? If fxch turns out to be cheaper than fstp, give priority to
2042      registers that die in this insn - move those to stack top first.  */
2043   if (! STACK_REG_P (*src1)
2044       || (STACK_REG_P (*src2)
2045           && get_hard_regnum (regstack, *src2) == FIRST_STACK_REG))
2046     {
2047       rtx temp, next;
2048
2049       temp = XEXP (SET_SRC (pat), 0);
2050       XEXP (SET_SRC (pat), 0) = XEXP (SET_SRC (pat), 1);
2051       XEXP (SET_SRC (pat), 1) = temp;
2052
2053       src1 = get_true_reg (&XEXP (SET_SRC (pat), 0));
2054       src2 = get_true_reg (&XEXP (SET_SRC (pat), 1));
2055
2056       next = next_cc0_user (insn);
2057       if (next == NULL_RTX)
2058         abort ();
2059
2060       swap_rtx_condition (PATTERN (next));
2061       INSN_CODE (next) = -1;
2062       INSN_CODE (insn) = -1;
2063     }
2064
2065   /* We will fix any death note later.  */
2066
2067   src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
2068
2069   if (STACK_REG_P (*src2))
2070     src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
2071   else
2072     src2_note = NULL_RTX;
2073
2074   emit_swap_insn (insn, regstack, *src1);
2075
2076   replace_reg (src1, FIRST_STACK_REG);
2077
2078   if (STACK_REG_P (*src2))
2079     replace_reg (src2, get_hard_regnum (regstack, *src2));
2080
2081   if (src1_note)
2082     {
2083       CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (XEXP (src1_note, 0)));
2084       replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
2085       regstack->top--;
2086     }
2087
2088   /* If the second operand dies, handle that.  But if the operands are
2089      the same stack register, don't bother, because only one death is
2090      needed, and it was just handled.  */
2091
2092   if (src2_note
2093       && ! (STACK_REG_P (*src1) && STACK_REG_P (*src2)
2094             && REGNO (*src1) == REGNO (*src2)))
2095     {
2096       /* As a special case, two regs may die in this insn if src2 is
2097          next to top of stack and the top of stack also dies.  Since
2098          we have already popped src1, "next to top of stack" is really
2099          at top (FIRST_STACK_REG) now.  */
2100
2101       if (get_hard_regnum (regstack, XEXP (src2_note, 0)) == FIRST_STACK_REG
2102           && src1_note)
2103         {
2104           CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (XEXP (src2_note, 0)));
2105           replace_reg (&XEXP (src2_note, 0), FIRST_STACK_REG + 1);
2106           regstack->top--;
2107         }
2108       else
2109         {
2110           /* The 386 can only represent death of the first operand in
2111              the case handled above.  In all other cases, emit a separate
2112              pop and remove the death note from here.  */
2113
2114           link_cc0_insns (insn);
2115
2116           remove_regno_note (insn, REG_DEAD, REGNO (XEXP (src2_note, 0)));
2117
2118           emit_pop_insn (insn, regstack, XEXP (src2_note, 0),
2119                          emit_insn_after);
2120         }
2121     }
2122 }
2123 \f
2124 /* Substitute new registers in PAT, which is part of INSN.  REGSTACK
2125    is the current register layout.  */
2126
2127 static void
2128 subst_stack_regs_pat (insn, regstack, pat)
2129      rtx insn;
2130      stack regstack;
2131      rtx pat;
2132 {
2133   rtx *dest, *src;
2134   rtx *src1 = (rtx *) NULL_PTR, *src2;
2135   rtx src1_note, src2_note;
2136
2137   if (GET_CODE (pat) != SET)
2138     return;
2139
2140   dest = get_true_reg (&SET_DEST (pat));
2141   src  = get_true_reg (&SET_SRC (pat));
2142
2143   /* See if this is a `movM' pattern, and handle elsewhere if so.  */
2144
2145   if (*dest != cc0_rtx
2146       && (STACK_REG_P (*src)
2147           || (STACK_REG_P (*dest)
2148               && (GET_CODE (*src) == REG || GET_CODE (*src) == MEM
2149                   || GET_CODE (*src) == CONST_DOUBLE))))
2150     move_for_stack_reg (insn, regstack, pat);
2151   else
2152     switch (GET_CODE (SET_SRC (pat)))
2153       {
2154       case COMPARE:
2155         compare_for_stack_reg (insn, regstack, pat);
2156         break;
2157
2158       case CALL:
2159          {
2160            int count;
2161            for (count = HARD_REGNO_NREGS (REGNO (*dest), GET_MODE (*dest));
2162               --count >= 0;)
2163             {
2164               regstack->reg[++regstack->top] = REGNO (*dest) + count;
2165               SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest) + count);
2166             }
2167          }
2168         replace_reg (dest, FIRST_STACK_REG);
2169         break;
2170
2171       case REG:
2172         /* This is a `tstM2' case.  */
2173         if (*dest != cc0_rtx)
2174           abort ();
2175
2176         src1 = src;
2177
2178         /* Fall through.  */
2179
2180       case FLOAT_TRUNCATE:
2181       case SQRT:
2182       case ABS:
2183       case NEG:
2184         /* These insns only operate on the top of the stack. DEST might
2185            be cc0_rtx if we're processing a tstM pattern. Also, it's
2186            possible that the tstM case results in a REG_DEAD note on the
2187            source.  */
2188
2189         if (src1 == 0)
2190           src1 = get_true_reg (&XEXP (SET_SRC (pat), 0));
2191
2192         emit_swap_insn (insn, regstack, *src1);
2193
2194         src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
2195
2196         if (STACK_REG_P (*dest))
2197           replace_reg (dest, FIRST_STACK_REG);
2198
2199         if (src1_note)
2200           {
2201             replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
2202             regstack->top--;
2203             CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (*src1));
2204           }
2205
2206         replace_reg (src1, FIRST_STACK_REG);
2207
2208         break;
2209
2210       case MINUS:
2211       case DIV:
2212         /* On i386, reversed forms of subM3 and divM3 exist for
2213            MODE_FLOAT, so the same code that works for addM3 and mulM3
2214            can be used.  */
2215       case MULT:
2216       case PLUS:
2217         /* These insns can accept the top of stack as a destination
2218            from a stack reg or mem, or can use the top of stack as a
2219            source and some other stack register (possibly top of stack)
2220            as a destination.  */
2221
2222         src1 = get_true_reg (&XEXP (SET_SRC (pat), 0));
2223         src2 = get_true_reg (&XEXP (SET_SRC (pat), 1));
2224
2225         /* We will fix any death note later.  */
2226
2227         if (STACK_REG_P (*src1))
2228           src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
2229         else
2230           src1_note = NULL_RTX;
2231         if (STACK_REG_P (*src2))
2232           src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
2233         else
2234           src2_note = NULL_RTX;
2235
2236         /* If either operand is not a stack register, then the dest
2237            must be top of stack.  */
2238
2239         if (! STACK_REG_P (*src1) || ! STACK_REG_P (*src2))
2240           emit_swap_insn (insn, regstack, *dest);
2241         else
2242           {
2243             /* Both operands are REG.  If neither operand is already
2244                at the top of stack, choose to make the one that is the dest
2245                the new top of stack.  */
2246
2247             int src1_hard_regnum, src2_hard_regnum;
2248
2249             src1_hard_regnum = get_hard_regnum (regstack, *src1);
2250             src2_hard_regnum = get_hard_regnum (regstack, *src2);
2251             if (src1_hard_regnum == -1 || src2_hard_regnum == -1)
2252               abort ();
2253
2254             if (src1_hard_regnum != FIRST_STACK_REG
2255                 && src2_hard_regnum != FIRST_STACK_REG)
2256               emit_swap_insn (insn, regstack, *dest);
2257           }
2258
2259         if (STACK_REG_P (*src1))
2260           replace_reg (src1, get_hard_regnum (regstack, *src1));
2261         if (STACK_REG_P (*src2))
2262           replace_reg (src2, get_hard_regnum (regstack, *src2));
2263
2264         if (src1_note)
2265           {
2266             /* If the register that dies is at the top of stack, then
2267                the destination is somewhere else - merely substitute it.
2268                But if the reg that dies is not at top of stack, then
2269                move the top of stack to the dead reg, as though we had
2270                done the insn and then a store-with-pop.  */
2271
2272             if (REGNO (XEXP (src1_note, 0)) == regstack->reg[regstack->top])
2273               {
2274                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2275                 replace_reg (dest, get_hard_regnum (regstack, *dest));
2276               }
2277             else
2278               {
2279                 int regno = get_hard_regnum (regstack, XEXP (src1_note, 0));
2280
2281                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2282                 replace_reg (dest, regno);
2283
2284                 regstack->reg[regstack->top - (regno - FIRST_STACK_REG)]
2285                   = regstack->reg[regstack->top];
2286               }
2287
2288             CLEAR_HARD_REG_BIT (regstack->reg_set,
2289                                 REGNO (XEXP (src1_note, 0)));
2290             replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
2291             regstack->top--;
2292           }
2293         else if (src2_note)
2294           {
2295             if (REGNO (XEXP (src2_note, 0)) == regstack->reg[regstack->top])
2296               {
2297                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2298                 replace_reg (dest, get_hard_regnum (regstack, *dest));
2299               }
2300             else
2301               {
2302                 int regno = get_hard_regnum (regstack, XEXP (src2_note, 0));
2303
2304                 SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2305                 replace_reg (dest, regno);
2306
2307                 regstack->reg[regstack->top - (regno - FIRST_STACK_REG)]
2308                   = regstack->reg[regstack->top];
2309               }
2310
2311             CLEAR_HARD_REG_BIT (regstack->reg_set,
2312                                 REGNO (XEXP (src2_note, 0)));
2313             replace_reg (&XEXP (src2_note, 0), FIRST_STACK_REG);
2314             regstack->top--;
2315           }
2316         else
2317           {
2318             SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2319             replace_reg (dest, get_hard_regnum (regstack, *dest));
2320           }
2321
2322         break;
2323
2324       case UNSPEC:
2325         switch (XINT (SET_SRC (pat), 1))
2326           {
2327           case 1: /* sin */
2328           case 2: /* cos */
2329             /* These insns only operate on the top of the stack.  */
2330
2331             src1 = get_true_reg (&XVECEXP (SET_SRC (pat), 0, 0));
2332
2333             emit_swap_insn (insn, regstack, *src1);
2334
2335             src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
2336
2337             if (STACK_REG_P (*dest))
2338               replace_reg (dest, FIRST_STACK_REG);
2339
2340             if (src1_note)
2341               {
2342                 replace_reg (&XEXP (src1_note, 0), FIRST_STACK_REG);
2343                 regstack->top--;
2344                 CLEAR_HARD_REG_BIT (regstack->reg_set, REGNO (*src1));
2345               }
2346
2347             replace_reg (src1, FIRST_STACK_REG);
2348
2349             break;
2350
2351           default:
2352             abort ();
2353           }
2354         break;
2355
2356       case IF_THEN_ELSE:
2357         /* This insn requires the top of stack to be the destination. */
2358
2359         src1 = get_true_reg (&XEXP (SET_SRC (pat), 1));
2360         src2 = get_true_reg (&XEXP (SET_SRC (pat), 2));
2361
2362         src1_note = find_regno_note (insn, REG_DEAD, REGNO (*src1));
2363         src2_note = find_regno_note (insn, REG_DEAD, REGNO (*src2));
2364
2365         {
2366           rtx src_note [3];
2367           int i;
2368
2369           src_note[0] = 0;
2370           src_note[1] = src1_note;
2371           src_note[2] = src2_note;
2372
2373           if (STACK_REG_P (*src1))
2374             replace_reg (src1, get_hard_regnum (regstack, *src1));
2375           if (STACK_REG_P (*src2))
2376             replace_reg (src2, get_hard_regnum (regstack, *src2));
2377
2378           for (i = 1; i <= 2; i++)
2379             if (src_note [i])
2380               {
2381                 int regno = get_hard_regnum (regstack, XEXP (src_note [i], 0));
2382
2383                 /* If the register that dies is not at the top of stack, then
2384                    move the top of stack to the dead reg */
2385                 if (REGNO (XEXP (src_note[i], 0))
2386                     != regstack->reg[regstack->top])
2387                   {
2388                     remove_regno_note (insn, REG_DEAD,
2389                                        REGNO (XEXP (src_note [i], 0)));
2390                     emit_pop_insn (insn, regstack, XEXP (src_note[i], 0),
2391                                    emit_insn_after);
2392                   }
2393                 else
2394                   {
2395                     CLEAR_HARD_REG_BIT (regstack->reg_set,
2396                                         REGNO (XEXP (src_note[i], 0)));
2397                     replace_reg (&XEXP (src_note[i], 0), FIRST_STACK_REG);
2398                     regstack->top--;
2399                   }
2400
2401               }
2402
2403           SET_HARD_REG_BIT (regstack->reg_set, REGNO (*dest));
2404           replace_reg (dest, FIRST_STACK_REG);
2405         }
2406
2407         break;
2408
2409       default:
2410         abort ();
2411       }
2412 }
2413 \f
2414 /* Substitute hard regnums for any stack regs in INSN, which has
2415    N_INPUTS inputs and N_OUTPUTS outputs.  REGSTACK is the stack info
2416    before the insn, and is updated with changes made here.  CONSTRAINTS is
2417    an array of the constraint strings used in the asm statement.
2418
2419    OPERANDS is an array of the operands, and OPERANDS_LOC is a
2420    parallel array of where the operands were found.  The output operands
2421    all precede the input operands.
2422
2423    There are several requirements and assumptions about the use of
2424    stack-like regs in asm statements.  These rules are enforced by
2425    record_asm_stack_regs; see comments there for details.  Any
2426    asm_operands left in the RTL at this point may be assume to meet the
2427    requirements, since record_asm_stack_regs removes any problem asm.  */
2428
2429 static void
2430 subst_asm_stack_regs (insn, regstack, operands, operands_loc, constraints,
2431                       n_inputs, n_outputs)
2432      rtx insn;
2433      stack regstack;
2434      rtx *operands, **operands_loc;
2435      char **constraints;
2436      int n_inputs, n_outputs;
2437 {
2438   int n_operands = n_inputs + n_outputs;
2439   int first_input = n_outputs;
2440   rtx body = PATTERN (insn);
2441
2442   int *operand_matches = (int *) alloca (n_operands * sizeof (int *));
2443   enum reg_class *operand_class
2444     = (enum reg_class *) alloca (n_operands * sizeof (enum reg_class *));
2445
2446   rtx *note_reg;                /* Array of note contents */
2447   rtx **note_loc;               /* Address of REG field of each note */
2448   enum reg_note *note_kind;     /* The type of each note */
2449
2450   rtx *clobber_reg;
2451   rtx **clobber_loc;
2452
2453   struct stack_def temp_stack;
2454   int n_notes;
2455   int n_clobbers;
2456   rtx note;
2457   int i;
2458
2459   /* Find out what the constraints required.  If no constraint
2460      alternative matches, that is a compiler bug: we should have caught
2461      such an insn during the life analysis pass (and reload should have
2462      caught it regardless).  */
2463
2464   i = constrain_asm_operands (n_operands, operands, constraints,
2465                               operand_matches, operand_class);
2466   if (i < 0)
2467     abort ();
2468
2469   /* Strip SUBREGs here to make the following code simpler.  */
2470   for (i = 0; i < n_operands; i++)
2471     if (GET_CODE (operands[i]) == SUBREG
2472         && GET_CODE (SUBREG_REG (operands[i])) == REG)
2473       {
2474         operands_loc[i] = & SUBREG_REG (operands[i]);
2475         operands[i] = SUBREG_REG (operands[i]);
2476       }
2477
2478   /* Set up NOTE_REG, NOTE_LOC and NOTE_KIND.  */
2479
2480   for (i = 0, note = REG_NOTES (insn); note; note = XEXP (note, 1))
2481     i++;
2482
2483   note_reg = (rtx *) alloca (i * sizeof (rtx));
2484   note_loc = (rtx **) alloca (i * sizeof (rtx *));
2485   note_kind = (enum reg_note *) alloca (i * sizeof (enum reg_note));
2486
2487   n_notes = 0;
2488   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2489     {
2490       rtx reg = XEXP (note, 0);
2491       rtx *loc = & XEXP (note, 0);
2492
2493       if (GET_CODE (reg) == SUBREG && GET_CODE (SUBREG_REG (reg)) == REG)
2494         {
2495           loc = & SUBREG_REG (reg);
2496           reg = SUBREG_REG (reg);
2497         }
2498
2499       if (STACK_REG_P (reg)
2500           && (REG_NOTE_KIND (note) == REG_DEAD
2501               || REG_NOTE_KIND (note) == REG_UNUSED))
2502         {
2503           note_reg[n_notes] = reg;
2504           note_loc[n_notes] = loc;
2505           note_kind[n_notes] = REG_NOTE_KIND (note);
2506           n_notes++;
2507         }
2508     }
2509
2510   /* Set up CLOBBER_REG and CLOBBER_LOC.  */
2511
2512   n_clobbers = 0;
2513
2514   if (GET_CODE (body) == PARALLEL)
2515     {
2516       clobber_reg = (rtx *) alloca (XVECLEN (body, 0) * sizeof (rtx *));
2517       clobber_loc = (rtx **) alloca (XVECLEN (body, 0) * sizeof (rtx **));
2518
2519       for (i = 0; i < XVECLEN (body, 0); i++)
2520         if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
2521           {
2522             rtx clobber = XVECEXP (body, 0, i);
2523             rtx reg = XEXP (clobber, 0);
2524             rtx *loc = & XEXP (clobber, 0);
2525
2526             if (GET_CODE (reg) == SUBREG && GET_CODE (SUBREG_REG (reg)) == REG)
2527               {
2528                 loc = & SUBREG_REG (reg);
2529                 reg = SUBREG_REG (reg);
2530               }
2531
2532             if (STACK_REG_P (reg))
2533               {
2534                 clobber_reg[n_clobbers] = reg;
2535                 clobber_loc[n_clobbers] = loc;
2536                 n_clobbers++;
2537               }
2538           }
2539     }
2540
2541   bcopy ((char *) regstack, (char *) &temp_stack, sizeof (temp_stack));
2542
2543   /* Put the input regs into the desired place in TEMP_STACK.  */
2544
2545   for (i = first_input; i < first_input + n_inputs; i++)
2546     if (STACK_REG_P (operands[i])
2547         && reg_class_subset_p (operand_class[i], FLOAT_REGS)
2548         && operand_class[i] != FLOAT_REGS)
2549       {
2550         /* If an operand needs to be in a particular reg in
2551            FLOAT_REGS, the constraint was either 't' or 'u'.  Since
2552            these constraints are for single register classes, and reload
2553            guaranteed that operand[i] is already in that class, we can
2554            just use REGNO (operands[i]) to know which actual reg this
2555            operand needs to be in.  */
2556
2557         int regno = get_hard_regnum (&temp_stack, operands[i]);
2558
2559         if (regno < 0)
2560           abort ();
2561
2562         if (regno != REGNO (operands[i]))
2563           {
2564             /* operands[i] is not in the right place.  Find it
2565                and swap it with whatever is already in I's place.
2566                K is where operands[i] is now.  J is where it should
2567                be.  */
2568             int j, k, temp;
2569
2570             k = temp_stack.top - (regno - FIRST_STACK_REG);
2571             j = (temp_stack.top
2572                  - (REGNO (operands[i]) - FIRST_STACK_REG));
2573
2574             temp = temp_stack.reg[k];
2575             temp_stack.reg[k] = temp_stack.reg[j];
2576             temp_stack.reg[j] = temp;
2577           }
2578       }
2579
2580   /* emit insns before INSN to make sure the reg-stack is in the right
2581      order.  */
2582
2583   change_stack (insn, regstack, &temp_stack, emit_insn_before);
2584
2585   /* Make the needed input register substitutions.  Do death notes and
2586      clobbers too, because these are for inputs, not outputs.  */
2587
2588   for (i = first_input; i < first_input + n_inputs; i++)
2589     if (STACK_REG_P (operands[i]))
2590       {
2591         int regnum = get_hard_regnum (regstack, operands[i]);
2592
2593         if (regnum < 0)
2594           abort ();
2595
2596         replace_reg (operands_loc[i], regnum);
2597       }
2598
2599   for (i = 0; i < n_notes; i++)
2600     if (note_kind[i] == REG_DEAD)
2601       {
2602         int regnum = get_hard_regnum (regstack, note_reg[i]);
2603
2604         if (regnum < 0)
2605           abort ();
2606
2607         replace_reg (note_loc[i], regnum);
2608       }
2609
2610   for (i = 0; i < n_clobbers; i++)
2611     {
2612       /* It's OK for a CLOBBER to reference a reg that is not live.
2613          Don't try to replace it in that case.  */
2614       int regnum = get_hard_regnum (regstack, clobber_reg[i]);
2615
2616       if (regnum >= 0)
2617         {
2618           /* Sigh - clobbers always have QImode.  But replace_reg knows
2619              that these regs can't be MODE_INT and will abort.  Just put
2620              the right reg there without calling replace_reg.  */
2621
2622           *clobber_loc[i] = FP_MODE_REG (regnum, DFmode);
2623         }
2624     }
2625
2626   /* Now remove from REGSTACK any inputs that the asm implicitly popped.  */
2627
2628   for (i = first_input; i < first_input + n_inputs; i++)
2629     if (STACK_REG_P (operands[i]))
2630       {
2631         /* An input reg is implicitly popped if it is tied to an
2632            output, or if there is a CLOBBER for it.  */
2633         int j;
2634
2635         for (j = 0; j < n_clobbers; j++)
2636           if (operands_match_p (clobber_reg[j], operands[i]))
2637             break;
2638
2639         if (j < n_clobbers || operand_matches[i] >= 0)
2640           {
2641             /* operands[i] might not be at the top of stack.  But that's OK,
2642                because all we need to do is pop the right number of regs
2643                off of the top of the reg-stack.  record_asm_stack_regs
2644                guaranteed that all implicitly popped regs were grouped
2645                at the top of the reg-stack.  */
2646
2647             CLEAR_HARD_REG_BIT (regstack->reg_set,
2648                                 regstack->reg[regstack->top]);
2649             regstack->top--;
2650           }
2651       }
2652
2653   /* Now add to REGSTACK any outputs that the asm implicitly pushed.
2654      Note that there isn't any need to substitute register numbers.
2655      ???  Explain why this is true.  */
2656
2657   for (i = LAST_STACK_REG; i >= FIRST_STACK_REG; i--)
2658     {
2659       /* See if there is an output for this hard reg.  */
2660       int j;
2661
2662       for (j = 0; j < n_outputs; j++)
2663         if (STACK_REG_P (operands[j]) && REGNO (operands[j]) == i)
2664           {
2665             regstack->reg[++regstack->top] = i;
2666             SET_HARD_REG_BIT (regstack->reg_set, i);
2667             break;
2668           }
2669     }
2670
2671   /* Now emit a pop insn for any REG_UNUSED output, or any REG_DEAD
2672      input that the asm didn't implicitly pop.  If the asm didn't
2673      implicitly pop an input reg, that reg will still be live.
2674
2675      Note that we can't use find_regno_note here: the register numbers
2676      in the death notes have already been substituted.  */
2677
2678   for (i = 0; i < n_outputs; i++)
2679     if (STACK_REG_P (operands[i]))
2680       {
2681         int j;
2682
2683         for (j = 0; j < n_notes; j++)
2684           if (REGNO (operands[i]) == REGNO (note_reg[j])
2685               && note_kind[j] == REG_UNUSED)
2686             {
2687               insn = emit_pop_insn (insn, regstack, operands[i],
2688                                     emit_insn_after);
2689               break;
2690             }
2691       }
2692
2693   for (i = first_input; i < first_input + n_inputs; i++)
2694     if (STACK_REG_P (operands[i]))
2695       {
2696         int j;
2697
2698         for (j = 0; j < n_notes; j++)
2699           if (REGNO (operands[i]) == REGNO (note_reg[j])
2700               && note_kind[j] == REG_DEAD
2701               && TEST_HARD_REG_BIT (regstack->reg_set, REGNO (operands[i])))
2702             {
2703               insn = emit_pop_insn (insn, regstack, operands[i],
2704                                     emit_insn_after);
2705               break;
2706             }
2707       }
2708 }
2709 \f
2710 /* Substitute stack hard reg numbers for stack virtual registers in
2711    INSN.  Non-stack register numbers are not changed.  REGSTACK is the
2712    current stack content.  Insns may be emitted as needed to arrange the
2713    stack for the 387 based on the contents of the insn.  */
2714
2715 static void
2716 subst_stack_regs (insn, regstack)
2717      rtx insn;
2718      stack regstack;
2719 {
2720   register rtx *note_link, note;
2721   register int i;
2722   int n_operands;
2723
2724   if (GET_CODE (insn) == CALL_INSN)
2725    {
2726      int top = regstack->top;
2727
2728      /* If there are any floating point parameters to be passed in
2729         registers for this call, make sure they are in the right
2730         order.  */
2731
2732      if (top >= 0)
2733       {
2734         straighten_stack (PREV_INSN (insn), regstack);
2735
2736         /* Now mark the arguments as dead after the call.  */
2737
2738         while (regstack->top >= 0)
2739          {
2740            CLEAR_HARD_REG_BIT (regstack->reg_set, FIRST_STACK_REG + regstack->top);
2741            regstack->top--;
2742          }
2743       }
2744    }
2745
2746   /* Do the actual substitution if any stack regs are mentioned.
2747      Since we only record whether entire insn mentions stack regs, and
2748      subst_stack_regs_pat only works for patterns that contain stack regs,
2749      we must check each pattern in a parallel here.  A call_value_pop could
2750      fail otherwise.  */
2751
2752   if (GET_MODE (insn) == QImode)
2753     {
2754       n_operands = asm_noperands (PATTERN (insn));
2755       if (n_operands >= 0)
2756         {
2757           /* This insn is an `asm' with operands.  Decode the operands,
2758              decide how many are inputs, and do register substitution.
2759              Any REG_UNUSED notes will be handled by subst_asm_stack_regs.  */
2760
2761           rtx operands[MAX_RECOG_OPERANDS];
2762           rtx *operands_loc[MAX_RECOG_OPERANDS];
2763           rtx body = PATTERN (insn);
2764           int n_inputs, n_outputs;
2765           char **constraints
2766             = (char **) alloca (n_operands * sizeof (char *));
2767
2768           decode_asm_operands (body, operands, operands_loc,
2769                                constraints, NULL_PTR);
2770           get_asm_operand_lengths (body, n_operands, &n_inputs, &n_outputs);
2771           subst_asm_stack_regs (insn, regstack, operands, operands_loc,
2772                                 constraints, n_inputs, n_outputs);
2773           return;
2774         }
2775
2776       if (GET_CODE (PATTERN (insn)) == PARALLEL)
2777         for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
2778           {
2779             if (stack_regs_mentioned_p (XVECEXP (PATTERN (insn), 0, i)))
2780               subst_stack_regs_pat (insn, regstack,
2781                                     XVECEXP (PATTERN (insn), 0, i));
2782           }
2783       else
2784         subst_stack_regs_pat (insn, regstack, PATTERN (insn));
2785     }
2786
2787   /* subst_stack_regs_pat may have deleted a no-op insn.  If so, any
2788      REG_UNUSED will already have been dealt with, so just return.  */
2789
2790   if (GET_CODE (insn) == NOTE)
2791     return;
2792
2793   /* If there is a REG_UNUSED note on a stack register on this insn,
2794      the indicated reg must be popped.  The REG_UNUSED note is removed,
2795      since the form of the newly emitted pop insn references the reg,
2796      making it no longer `unset'.  */
2797
2798   note_link = &REG_NOTES(insn);
2799   for (note = *note_link; note; note = XEXP (note, 1))
2800     if (REG_NOTE_KIND (note) == REG_UNUSED && STACK_REG_P (XEXP (note, 0)))
2801       {
2802         *note_link = XEXP (note, 1);
2803         insn = emit_pop_insn (insn, regstack, XEXP (note, 0), emit_insn_after);
2804       }
2805     else
2806       note_link = &XEXP (note, 1);
2807 }
2808 \f
2809 /* Change the organization of the stack so that it fits a new basic
2810    block.  Some registers might have to be popped, but there can never be
2811    a register live in the new block that is not now live.
2812
2813    Insert any needed insns before or after INSN.  WHEN is emit_insn_before
2814    or emit_insn_after. OLD is the original stack layout, and NEW is
2815    the desired form.  OLD is updated to reflect the code emitted, ie, it
2816    will be the same as NEW upon return.
2817
2818    This function will not preserve block_end[].  But that information
2819    is no longer needed once this has executed.  */
2820
2821 static void
2822 change_stack (insn, old, new, when)
2823      rtx insn;
2824      stack old;
2825      stack new;
2826      rtx (*when)();
2827 {
2828   int reg;
2829
2830   /* We will be inserting new insns "backwards", by calling emit_insn_before.
2831      If we are to insert after INSN, find the next insn, and insert before
2832      it.  */
2833
2834   if (when == emit_insn_after)
2835     insn = NEXT_INSN (insn);
2836
2837   /* Pop any registers that are not needed in the new block.  */
2838
2839   for (reg = old->top; reg >= 0; reg--)
2840     if (! TEST_HARD_REG_BIT (new->reg_set, old->reg[reg]))
2841       emit_pop_insn (insn, old, FP_MODE_REG (old->reg[reg], DFmode),
2842                      emit_insn_before);
2843
2844   if (new->top == -2)
2845     {
2846       /* If the new block has never been processed, then it can inherit
2847          the old stack order.  */
2848
2849       new->top = old->top;
2850       bcopy (old->reg, new->reg, sizeof (new->reg));
2851     }
2852   else
2853     {
2854       /* This block has been entered before, and we must match the
2855          previously selected stack order.  */
2856
2857       /* By now, the only difference should be the order of the stack,
2858          not their depth or liveliness.  */
2859
2860       GO_IF_HARD_REG_EQUAL (old->reg_set, new->reg_set, win);
2861
2862       abort ();
2863
2864     win:
2865
2866       if (old->top != new->top)
2867         abort ();
2868
2869       /* Loop here emitting swaps until the stack is correct.  The
2870          worst case number of swaps emitted is N + 2, where N is the
2871          depth of the stack.  In some cases, the reg at the top of
2872          stack may be correct, but swapped anyway in order to fix
2873          other regs.  But since we never swap any other reg away from
2874          its correct slot, this algorithm will converge.  */
2875
2876       do
2877         {
2878           /* Swap the reg at top of stack into the position it is
2879              supposed to be in, until the correct top of stack appears.  */
2880
2881           while (old->reg[old->top] != new->reg[new->top])
2882             {
2883               for (reg = new->top; reg >= 0; reg--)
2884                 if (new->reg[reg] == old->reg[old->top])
2885                   break;
2886
2887               if (reg == -1)
2888                 abort ();
2889
2890               emit_swap_insn (insn, old,
2891                               FP_MODE_REG (old->reg[reg], DFmode));
2892             }
2893
2894           /* See if any regs remain incorrect.  If so, bring an
2895              incorrect reg to the top of stack, and let the while loop
2896              above fix it.  */
2897
2898           for (reg = new->top; reg >= 0; reg--)
2899             if (new->reg[reg] != old->reg[reg])
2900               {
2901                 emit_swap_insn (insn, old,
2902                                 FP_MODE_REG (old->reg[reg], DFmode));
2903                 break;
2904               }
2905         } while (reg >= 0);
2906
2907       /* At this point there must be no differences.  */
2908
2909       for (reg = old->top; reg >= 0; reg--)
2910         if (old->reg[reg] != new->reg[reg])
2911           abort ();
2912     }
2913 }
2914 \f
2915 /* Check PAT, which points to RTL in INSN, for a LABEL_REF.  If it is
2916    found, ensure that a jump from INSN to the code_label to which the
2917    label_ref points ends up with the same stack as that at the
2918    code_label.  Do this by inserting insns just before the code_label to
2919    pop and rotate the stack until it is in the correct order.  REGSTACK
2920    is the order of the register stack in INSN.
2921
2922    Any code that is emitted here must not be later processed as part
2923    of any block, as it will already contain hard register numbers.  */
2924
2925 static void
2926 goto_block_pat (insn, regstack, pat)
2927      rtx insn;
2928      stack regstack;
2929      rtx pat;
2930 {
2931   rtx label;
2932   rtx new_jump, new_label, new_barrier;
2933   rtx *ref;
2934   stack label_stack;
2935   struct stack_def temp_stack;
2936   int reg;
2937
2938   switch (GET_CODE (pat))
2939    {
2940      case RETURN:
2941         straighten_stack (PREV_INSN (insn), regstack);
2942         return;
2943      default:
2944      {
2945       int i, j;
2946       char *fmt = GET_RTX_FORMAT (GET_CODE (pat));
2947
2948       for (i = GET_RTX_LENGTH (GET_CODE (pat)) - 1; i >= 0; i--)
2949         {
2950           if (fmt[i] == 'e')
2951             goto_block_pat (insn, regstack, XEXP (pat, i));
2952           if (fmt[i] == 'E')
2953             for (j = 0; j < XVECLEN (pat, i); j++)
2954               goto_block_pat (insn, regstack, XVECEXP (pat, i, j));
2955         }
2956       return;
2957      }
2958      case LABEL_REF:;
2959    }
2960
2961   label = XEXP (pat, 0);
2962   if (GET_CODE (label) != CODE_LABEL)
2963     abort ();
2964
2965   /* First, see if in fact anything needs to be done to the stack at all.  */
2966   if (INSN_UID (label) <= 0)
2967     return;
2968
2969   label_stack = &block_stack_in[BLOCK_NUM (label)];
2970
2971   if (label_stack->top == -2)
2972     {
2973       /* If the target block hasn't had a stack order selected, then
2974          we need merely ensure that no pops are needed.  */
2975
2976       for (reg = regstack->top; reg >= 0; reg--)
2977         if (! TEST_HARD_REG_BIT (label_stack->reg_set, regstack->reg[reg]))
2978           break;
2979
2980       if (reg == -1)
2981         {
2982           /* change_stack will not emit any code in this case.  */
2983
2984           change_stack (label, regstack, label_stack, emit_insn_after);
2985           return;
2986         }
2987     }
2988   else if (label_stack->top == regstack->top)
2989     {
2990       for (reg = label_stack->top; reg >= 0; reg--)
2991         if (label_stack->reg[reg] != regstack->reg[reg])
2992           break;
2993
2994       if (reg == -1)
2995         return;
2996     }
2997
2998   /* At least one insn will need to be inserted before label.  Insert
2999      a jump around the code we are about to emit.  Emit a label for the new
3000      code, and point the original insn at this new label. We can't use
3001      redirect_jump here, because we're using fld[4] of the code labels as
3002      LABEL_REF chains, no NUSES counters.  */
3003
3004   new_jump = emit_jump_insn_before (gen_jump (label), label);
3005   record_label_references (new_jump, PATTERN (new_jump));
3006   JUMP_LABEL (new_jump) = label;
3007
3008   new_barrier = emit_barrier_after (new_jump);
3009
3010   new_label = gen_label_rtx ();
3011   emit_label_after (new_label, new_barrier);
3012   LABEL_REFS (new_label) = new_label;
3013
3014   /* The old label_ref will no longer point to the code_label if now uses,
3015      so strip the label_ref from the code_label's chain of references.  */
3016
3017   for (ref = &LABEL_REFS (label); *ref != label; ref = &LABEL_NEXTREF (*ref))
3018     if (*ref == pat)
3019       break;
3020
3021   if (*ref == label)
3022     abort ();
3023
3024   *ref = LABEL_NEXTREF (*ref);
3025
3026   XEXP (pat, 0) = new_label;
3027   record_label_references (insn, PATTERN (insn));
3028
3029   if (JUMP_LABEL (insn) == label)
3030     JUMP_LABEL (insn) = new_label;
3031
3032   /* Now emit the needed code.  */
3033
3034   temp_stack = *regstack;
3035
3036   change_stack (new_label, &temp_stack, label_stack, emit_insn_after);
3037 }
3038 \f
3039 /* Traverse all basic blocks in a function, converting the register
3040    references in each insn from the "flat" register file that gcc uses, to
3041    the stack-like registers the 387 uses.  */
3042
3043 static void
3044 convert_regs ()
3045 {
3046   register int block, reg;
3047   register rtx insn, next;
3048   struct stack_def regstack;
3049
3050   for (block = 0; block < blocks; block++)
3051     {
3052       if (block_stack_in[block].top == -2)
3053         {
3054           /* This block has not been previously encountered.  Choose a
3055              default mapping for any stack regs live on entry */
3056
3057           block_stack_in[block].top = -1;
3058
3059           for (reg = LAST_STACK_REG; reg >= FIRST_STACK_REG; reg--)
3060             if (TEST_HARD_REG_BIT (block_stack_in[block].reg_set, reg))
3061               block_stack_in[block].reg[++block_stack_in[block].top] = reg;
3062         }
3063
3064       /* Process all insns in this block.  Keep track of `next' here,
3065          so that we don't process any insns emitted while making
3066          substitutions in INSN.  */
3067
3068       next = block_begin[block];
3069       regstack = block_stack_in[block];
3070       do
3071         {
3072           insn = next;
3073           next = NEXT_INSN (insn);
3074
3075           /* Don't bother processing unless there is a stack reg
3076              mentioned or if it's a CALL_INSN (register passing of
3077              floating point values).  */
3078
3079           if (GET_MODE (insn) == QImode || GET_CODE (insn) == CALL_INSN)
3080             subst_stack_regs (insn, &regstack);
3081
3082         } while (insn != block_end[block]);
3083
3084       /* Something failed if the stack life doesn't match.  */
3085
3086       GO_IF_HARD_REG_EQUAL (regstack.reg_set, block_out_reg_set[block], win);
3087
3088       abort ();
3089
3090     win:
3091
3092       /* Adjust the stack of this block on exit to match the stack of
3093          the target block, or copy stack information into stack of
3094          jump target if the target block's stack order hasn't been set
3095          yet.  */
3096
3097       if (GET_CODE (insn) == JUMP_INSN)
3098         goto_block_pat (insn, &regstack, PATTERN (insn));
3099
3100       /* Likewise handle the case where we fall into the next block.  */
3101
3102       if ((block < blocks - 1) && block_drops_in[block+1])
3103         change_stack (insn, &regstack, &block_stack_in[block+1],
3104                       emit_insn_after);
3105     }
3106
3107   /* If the last basic block is the end of a loop, and that loop has
3108      regs live at its start, then the last basic block will have regs live
3109      at its end that need to be popped before the function returns.  */
3110
3111    {
3112      int value_reg_low, value_reg_high;
3113      value_reg_low = value_reg_high = -1;
3114       {
3115         rtx retvalue;
3116         if (retvalue = stack_result (current_function_decl))
3117          {
3118            value_reg_low = REGNO (retvalue);
3119            value_reg_high = value_reg_low +
3120             HARD_REGNO_NREGS (value_reg_low, GET_MODE (retvalue)) - 1;
3121          }
3122
3123       }
3124      for (reg = regstack.top; reg >= 0; reg--)
3125         if (regstack.reg[reg] < value_reg_low ||
3126             regstack.reg[reg] > value_reg_high)
3127            insn = emit_pop_insn (insn, &regstack,
3128                             FP_MODE_REG (regstack.reg[reg], DFmode),
3129                             emit_insn_after);
3130    }
3131   straighten_stack (insn, &regstack);
3132 }
3133 \f
3134 /* Check expression PAT, which is in INSN, for label references.  if
3135    one is found, print the block number of destination to FILE.  */
3136
3137 static void
3138 print_blocks (file, insn, pat)
3139      FILE *file;
3140      rtx insn, pat;
3141 {
3142   register RTX_CODE code = GET_CODE (pat);
3143   register int i;
3144   register char *fmt;
3145
3146   if (code == LABEL_REF)
3147     {
3148       register rtx label = XEXP (pat, 0);
3149
3150       if (GET_CODE (label) != CODE_LABEL)
3151         abort ();
3152
3153       fprintf (file, " %d", BLOCK_NUM (label));
3154
3155       return;
3156     }
3157
3158   fmt = GET_RTX_FORMAT (code);
3159   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3160     {
3161       if (fmt[i] == 'e')
3162         print_blocks (file, insn, XEXP (pat, i));
3163       if (fmt[i] == 'E')
3164         {
3165           register int j;
3166           for (j = 0; j < XVECLEN (pat, i); j++)
3167             print_blocks (file, insn, XVECEXP (pat, i, j));
3168         }
3169     }
3170 }
3171 \f
3172 /* Write information about stack registers and stack blocks into FILE.
3173    This is part of making a debugging dump.  */
3174
3175 static void
3176 dump_stack_info (file)
3177      FILE *file;
3178 {
3179   register int block;
3180
3181   fprintf (file, "\n%d stack blocks.\n", blocks);
3182   for (block = 0; block < blocks; block++)
3183     {
3184       register rtx head, jump, end;
3185       register int regno;
3186
3187       fprintf (file, "\nStack block %d: first insn %d, last %d.\n",
3188                block, INSN_UID (block_begin[block]),
3189                INSN_UID (block_end[block]));
3190
3191       head = block_begin[block];
3192
3193       fprintf (file, "Reached from blocks: ");
3194       if (GET_CODE (head) == CODE_LABEL)
3195         for (jump = LABEL_REFS (head);
3196              jump != head;
3197              jump = LABEL_NEXTREF (jump))
3198           {
3199             register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
3200             fprintf (file, " %d", from_block);
3201           }
3202       if (block_drops_in[block])
3203         fprintf (file, " previous");
3204
3205       fprintf (file, "\nlive stack registers on block entry: ");
3206       for (regno = FIRST_STACK_REG; regno <= LAST_STACK_REG; regno++)
3207         {
3208           if (TEST_HARD_REG_BIT (block_stack_in[block].reg_set, regno))
3209             fprintf (file, "%d ", regno);
3210         }
3211
3212       fprintf (file, "\nlive stack registers on block exit: ");
3213       for (regno = FIRST_STACK_REG; regno <= LAST_STACK_REG; regno++)
3214         {
3215           if (TEST_HARD_REG_BIT (block_out_reg_set[block], regno))
3216             fprintf (file, "%d ", regno);
3217         }
3218
3219       end = block_end[block];
3220
3221       fprintf (file, "\nJumps to blocks: ");
3222       if (GET_CODE (end) == JUMP_INSN)
3223         print_blocks (file, end, PATTERN (end));
3224
3225       if (block + 1 < blocks && block_drops_in[block+1])
3226         fprintf (file, " next");
3227       else if (block + 1 == blocks
3228                || (GET_CODE (end) == JUMP_INSN
3229                    && GET_CODE (PATTERN (end)) == RETURN))
3230         fprintf (file, " return");
3231
3232       fprintf (file, "\n");
3233     }
3234 }
3235 #endif /* STACK_REGS */