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