gcc/reg-stack.c

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