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