gcc/reg-stack.c

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