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