gcc/reg-stack.c

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