gcc/jump.c

   1 /* Optimize jump instructions, for GNU compiler.
   2    Copyright (C) 1987, 88, 89, 91, 92, 93, 1994 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 /* This is the jump-optimization pass of the compiler.
  22    It is run two or three times: once before cse, sometimes once after cse,
  23    and once after reload (before final).
  24
  25    jump_optimize deletes unreachable code and labels that are not used.
  26    It also deletes jumps that jump to the following insn,
  27    and simplifies jumps around unconditional jumps and jumps
  28    to unconditional jumps.
  29
  30    Each CODE_LABEL has a count of the times it is used
  31    stored in the LABEL_NUSES internal field, and each JUMP_INSN
  32    has one label that it refers to stored in the
  33    JUMP_LABEL internal field.  With this we can detect labels that
  34    become unused because of the deletion of all the jumps that
  35    formerly used them.  The JUMP_LABEL info is sometimes looked
  36    at by later passes.
  37
  38    Optionally, cross-jumping can be done.  Currently it is done
  39    only the last time (when after reload and before final).
  40    In fact, the code for cross-jumping now assumes that register
  41    allocation has been done, since it uses `rtx_renumbered_equal_p'.
  42
  43    Jump optimization is done after cse when cse's constant-propagation
  44    causes jumps to become unconditional or to be deleted.
  45
  46    Unreachable loops are not detected here, because the labels
  47    have references and the insns appear reachable from the labels.
  48    find_basic_blocks in flow.c finds and deletes such loops.
  49
  50    The subroutines delete_insn, redirect_jump, and invert_jump are used
  51    from other passes as well.  */
  52
  53 #include "config.h"
  54 #include "rtl.h"
  55 #include "flags.h"
  56 #include "hard-reg-set.h"
  57 #include "regs.h"
  58 #include "expr.h"
  59 #include "insn-config.h"
  60 #include "insn-flags.h"
  61 #include "real.h"
  62
  63 /* ??? Eventually must record somehow the labels used by jumps
  64    from nested functions.  */
  65 /* Pre-record the next or previous real insn for each label?
  66    No, this pass is very fast anyway.  */
  67 /* Condense consecutive labels?
  68    This would make life analysis faster, maybe.  */
  69 /* Optimize jump y; x: ... y: jumpif... x?
  70    Don't know if it is worth bothering with.  */
  71 /* Optimize two cases of conditional jump to conditional jump?
  72    This can never delete any instruction or make anything dead,
  73    or even change what is live at any point.
  74    So perhaps let combiner do it.  */
  75
  76 /* Vector indexed by uid.
  77    For each CODE_LABEL, index by its uid to get first unconditional jump
  78    that jumps to the label.
  79    For each JUMP_INSN, index by its uid to get the next unconditional jump
  80    that jumps to the same label.
  81    Element 0 is the start of a chain of all return insns.
  82    (It is safe to use element 0 because insn uid 0 is not used.  */
  83
  84 static rtx *jump_chain;
  85
  86 /* List of labels referred to from initializers.
  87    These can never be deleted.  */
  88 rtx forced_labels;
  89
  90 /* Maximum index in jump_chain.  */
  91
  92 static int max_jump_chain;
  93
  94 /* Set nonzero by jump_optimize if control can fall through
  95    to the end of the function.  */
  96 int can_reach_end;
  97
  98 /* Indicates whether death notes are significant in cross jump analysis.
  99    Normally they are not significant, because of A and B jump to C,
 100    and R dies in A, it must die in B.  But this might not be true after
 101    stack register conversion, and we must compare death notes in that
 102    case. */
 103
 104 static int cross_jump_death_matters = 0;
 105
 106 static int duplicate_loop_exit_test     PROTO((rtx));
 107 static void find_cross_jump             PROTO((rtx, rtx, int, rtx *, rtx *));
 108 static void do_cross_jump               PROTO((rtx, rtx, rtx));
 109 static int jump_back_p                  PROTO((rtx, rtx));
 110 static int tension_vector_labels        PROTO((rtx, int));
 111 static void mark_jump_label             PROTO((rtx, rtx, int));
 112 static void delete_computation          PROTO((rtx));
 113 static void delete_from_jump_chain      PROTO((rtx));
 114 static int delete_labelref_insn         PROTO((rtx, rtx, int));
 115 static void redirect_tablejump          PROTO((rtx, rtx));
 116 \f
 117 /* Delete no-op jumps and optimize jumps to jumps
 118    and jumps around jumps.
 119    Delete unused labels and unreachable code.
 120
 121    If CROSS_JUMP is 1, detect matching code
 122    before a jump and its destination and unify them.
 123    If CROSS_JUMP is 2, do cross-jumping, but pay attention to death notes.
 124
 125    If NOOP_MOVES is nonzero, delete no-op move insns.
 126
 127    If AFTER_REGSCAN is nonzero, then this jump pass is being run immediately
 128    after regscan, and it is safe to use regno_first_uid and regno_last_uid.
 129
 130    If `optimize' is zero, don't change any code,
 131    just determine whether control drops off the end of the function.
 132    This case occurs when we have -W and not -O.
 133    It works because `delete_insn' checks the value of `optimize'
 134    and refrains from actually deleting when that is 0.  */
 135
 136 void
 137 jump_optimize (f, cross_jump, noop_moves, after_regscan)
 138      rtx f;
 139      int cross_jump;
 140      int noop_moves;
 141      int after_regscan;
 142 {
 143   register rtx insn, next, note;
 144   int changed;
 145   int first = 1;
 146   int max_uid = 0;
 147   rtx last_insn;
 148
 149   cross_jump_death_matters = (cross_jump == 2);
 150
 151   /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
 152      notes whose labels don't occur in the insn any more.  */
 153
 154   for (insn = f; insn; insn = NEXT_INSN (insn))
 155     {
 156       if (GET_CODE (insn) == CODE_LABEL)
 157         LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
 158       else if (GET_CODE (insn) == JUMP_INSN)
 159         JUMP_LABEL (insn) = 0;
 160       else if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 161         for (note = REG_NOTES (insn); note; note = next)
 162           {
 163             next = XEXP (note, 1);
 164             if (REG_NOTE_KIND (note) == REG_LABEL
 165                 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
 166               remove_note (insn, note);
 167           }
 168
 169       if (INSN_UID (insn) > max_uid)
 170         max_uid = INSN_UID (insn);
 171     }
 172
 173   max_uid++;
 174
 175   /* Delete insns following barriers, up to next label.  */
 176
 177   for (insn = f; insn;)
 178     {
 179       if (GET_CODE (insn) == BARRIER)
 180         {
 181           insn = NEXT_INSN (insn);
 182           while (insn != 0 && GET_CODE (insn) != CODE_LABEL)
 183             {
 184               if (GET_CODE (insn) == NOTE
 185                   && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
 186                 insn = NEXT_INSN (insn);
 187               else
 188                 insn = delete_insn (insn);
 189             }
 190           /* INSN is now the code_label.  */
 191         }
 192       else
 193         insn = NEXT_INSN (insn);
 194     }
 195
 196   /* Leave some extra room for labels and duplicate exit test insns
 197      we make.  */
 198   max_jump_chain = max_uid * 14 / 10;
 199   jump_chain = (rtx *) alloca (max_jump_chain * sizeof (rtx));
 200   bzero ((char *) jump_chain, max_jump_chain * sizeof (rtx));
 201
 202   /* Mark the label each jump jumps to.
 203      Combine consecutive labels, and count uses of labels.
 204
 205      For each label, make a chain (using `jump_chain')
 206      of all the *unconditional* jumps that jump to it;
 207      also make a chain of all returns.  */
 208
 209   for (insn = f; insn; insn = NEXT_INSN (insn))
 210     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
 211         && ! INSN_DELETED_P (insn))
 212       {
 213         mark_jump_label (PATTERN (insn), insn, cross_jump);
 214         if (GET_CODE (insn) == JUMP_INSN)
 215           {
 216             if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
 217               {
 218                 jump_chain[INSN_UID (insn)]
 219                   = jump_chain[INSN_UID (JUMP_LABEL (insn))];
 220                 jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
 221               }
 222             if (GET_CODE (PATTERN (insn)) == RETURN)
 223               {
 224                 jump_chain[INSN_UID (insn)] = jump_chain[0];
 225                 jump_chain[0] = insn;
 226               }
 227           }
 228       }
 229
 230   /* Keep track of labels used from static data;
 231      they cannot ever be deleted.  */
 232
 233   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
 234     LABEL_NUSES (XEXP (insn, 0))++;
 235
 236   /* Delete all labels already not referenced.
 237      Also find the last insn.  */
 238
 239   last_insn = 0;
 240   for (insn = f; insn; )
 241     {
 242       if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)
 243         insn = delete_insn (insn);
 244       else
 245         {
 246           last_insn = insn;
 247           insn = NEXT_INSN (insn);
 248         }
 249     }
 250
 251   if (!optimize)
 252     {
 253       /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
 254          If so record that this function can drop off the end.  */
 255
 256       insn = last_insn;
 257       {
 258         int n_labels = 1;
 259         while (insn
 260                /* One label can follow the end-note: the return label.  */
 261                && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
 262                    /* Ordinary insns can follow it if returning a structure.  */
 263                    || GET_CODE (insn) == INSN
 264                    /* If machine uses explicit RETURN insns, no epilogue,
 265                       then one of them follows the note.  */
 266                    || (GET_CODE (insn) == JUMP_INSN
 267                        && GET_CODE (PATTERN (insn)) == RETURN)
 268                    /* Other kinds of notes can follow also.  */
 269                    || (GET_CODE (insn) == NOTE
 270                        && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
 271           insn = PREV_INSN (insn);
 272       }
 273
 274       /* Report if control can fall through at the end of the function.  */
 275       if (insn && GET_CODE (insn) == NOTE
 276           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END
 277           && ! INSN_DELETED_P (insn))
 278         can_reach_end = 1;
 279
 280       /* Zero the "deleted" flag of all the "deleted" insns.  */
 281       for (insn = f; insn; insn = NEXT_INSN (insn))
 282         INSN_DELETED_P (insn) = 0;
 283       return;
 284     }
 285
 286 #ifdef HAVE_return
 287   if (HAVE_return)
 288     {
 289       /* If we fall through to the epilogue, see if we can insert a RETURN insn
 290          in front of it.  If the machine allows it at this point (we might be
 291          after reload for a leaf routine), it will improve optimization for it
 292          to be there.  */
 293       insn = get_last_insn ();
 294       while (insn && GET_CODE (insn) == NOTE)
 295         insn = PREV_INSN (insn);
 296
 297       if (insn && GET_CODE (insn) != BARRIER)
 298         {
 299           emit_jump_insn (gen_return ());
 300           emit_barrier ();
 301         }
 302     }
 303 #endif
 304
 305   if (noop_moves)
 306     for (insn = f; insn; )
 307       {
 308         next = NEXT_INSN (insn);
 309
 310         if (GET_CODE (insn) == INSN)
 311           {
 312             register rtx body = PATTERN (insn);
 313
 314 /* Combine stack_adjusts with following push_insns.  */
 315 #ifdef PUSH_ROUNDING
 316             if (GET_CODE (body) == SET
 317                 && SET_DEST (body) == stack_pointer_rtx
 318                 && GET_CODE (SET_SRC (body)) == PLUS
 319                 && XEXP (SET_SRC (body), 0) == stack_pointer_rtx
 320                 && GET_CODE (XEXP (SET_SRC (body), 1)) == CONST_INT
 321                 && INTVAL (XEXP (SET_SRC (body), 1)) > 0)
 322               {
 323                 rtx p;
 324                 rtx stack_adjust_insn = insn;
 325                 int stack_adjust_amount = INTVAL (XEXP (SET_SRC (body), 1));
 326                 int total_pushed = 0;
 327                 int pushes = 0;
 328
 329                 /* Find all successive push insns.  */
 330                 p = insn;
 331                 /* Don't convert more than three pushes;
 332                    that starts adding too many displaced addresses
 333                    and the whole thing starts becoming a losing
 334                    proposition.  */
 335                 while (pushes < 3)
 336                   {
 337                     rtx pbody, dest;
 338                     p = next_nonnote_insn (p);
 339                     if (p == 0 || GET_CODE (p) != INSN)
 340                       break;
 341                     pbody = PATTERN (p);
 342                     if (GET_CODE (pbody) != SET)
 343                       break;
 344                     dest = SET_DEST (pbody);
 345                     /* Allow a no-op move between the adjust and the push.  */
 346                     if (GET_CODE (dest) == REG
 347                         && GET_CODE (SET_SRC (pbody)) == REG
 348                         && REGNO (dest) == REGNO (SET_SRC (pbody)))
 349                       continue;
 350                     if (! (GET_CODE (dest) == MEM
 351                            && GET_CODE (XEXP (dest, 0)) == POST_INC
 352                            && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
 353                       break;
 354                     pushes++;
 355                     if (total_pushed + GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)))
 356                         > stack_adjust_amount)
 357                       break;
 358                     total_pushed += GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
 359                   }
 360
 361                 /* Discard the amount pushed from the stack adjust;
 362                    maybe eliminate it entirely.  */
 363                 if (total_pushed >= stack_adjust_amount)
 364                   {
 365                     delete_computation (stack_adjust_insn);
 366                     total_pushed = stack_adjust_amount;
 367                   }
 368                 else
 369                   XEXP (SET_SRC (PATTERN (stack_adjust_insn)), 1)
 370                     = GEN_INT (stack_adjust_amount - total_pushed);
 371
 372                 /* Change the appropriate push insns to ordinary stores.  */
 373                 p = insn;
 374                 while (total_pushed > 0)
 375                   {
 376                     rtx pbody, dest;
 377                     p = next_nonnote_insn (p);
 378                     if (GET_CODE (p) != INSN)
 379                       break;
 380                     pbody = PATTERN (p);
 381                     if (GET_CODE (pbody) == SET)
 382                       break;
 383                     dest = SET_DEST (pbody);
 384                     if (! (GET_CODE (dest) == MEM
 385                            && GET_CODE (XEXP (dest, 0)) == POST_INC
 386                            && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
 387                       break;
 388                     total_pushed -= GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
 389                     /* If this push doesn't fully fit in the space
 390                        of the stack adjust that we deleted,
 391                        make another stack adjust here for what we
 392                        didn't use up.  There should be peepholes
 393                        to recognize the resulting sequence of insns.  */
 394                     if (total_pushed < 0)
 395                       {
 396                         emit_insn_before (gen_add2_insn (stack_pointer_rtx,
 397                                                          GEN_INT (- total_pushed)),
 398                                           p);
 399                         break;
 400                       }
 401                     XEXP (dest, 0)
 402                       = plus_constant (stack_pointer_rtx, total_pushed);
 403                   }
 404               }
 405 #endif
 406
 407             /* Detect and delete no-op move instructions
 408                resulting from not allocating a parameter in a register.  */
 409
 410             if (GET_CODE (body) == SET
 411                 && (SET_DEST (body) == SET_SRC (body)
 412                     || (GET_CODE (SET_DEST (body)) == MEM
 413                         && GET_CODE (SET_SRC (body)) == MEM
 414                         && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
 415                 && ! (GET_CODE (SET_DEST (body)) == MEM
 416                       && MEM_VOLATILE_P (SET_DEST (body)))
 417                 && ! (GET_CODE (SET_SRC (body)) == MEM
 418                       && MEM_VOLATILE_P (SET_SRC (body))))
 419               delete_computation (insn);
 420
 421             /* Detect and ignore no-op move instructions
 422                resulting from smart or fortuitous register allocation.  */
 423
 424             else if (GET_CODE (body) == SET)
 425               {
 426                 int sreg = true_regnum (SET_SRC (body));
 427                 int dreg = true_regnum (SET_DEST (body));
 428
 429                 if (sreg == dreg && sreg >= 0)
 430                   delete_insn (insn);
 431                 else if (sreg >= 0 && dreg >= 0)
 432                   {
 433                     rtx trial;
 434                     rtx tem = find_equiv_reg (NULL_RTX, insn, 0,
 435                                               sreg, NULL_PTR, dreg,
 436                                               GET_MODE (SET_SRC (body)));
 437
 438 #ifdef PRESERVE_DEATH_INFO_REGNO_P
 439                     /* Deleting insn could lose a death-note for SREG or DREG
 440                        so don't do it if final needs accurate death-notes.  */
 441                     if (! PRESERVE_DEATH_INFO_REGNO_P (sreg)
 442                         && ! PRESERVE_DEATH_INFO_REGNO_P (dreg))
 443 #endif
 444                       {
 445                         /* DREG may have been the target of a REG_DEAD note in
 446                            the insn which makes INSN redundant.  If so, reorg
 447                            would still think it is dead.  So search for such a
 448                            note and delete it if we find it.  */
 449                         for (trial = prev_nonnote_insn (insn);
 450                              trial && GET_CODE (trial) != CODE_LABEL;
 451                              trial = prev_nonnote_insn (trial))
 452                           if (find_regno_note (trial, REG_DEAD, dreg))
 453                             {
 454                               remove_death (dreg, trial);
 455                               break;
 456                             }
 457
 458                         if (tem != 0
 459                             && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
 460                           delete_insn (insn);
 461                       }
 462                   }
 463                 else if (dreg >= 0 && CONSTANT_P (SET_SRC (body))
 464                          && find_equiv_reg (SET_SRC (body), insn, 0, dreg,
 465                                             NULL_PTR, 0,
 466                                             GET_MODE (SET_DEST (body))))
 467                   {
 468                     /* This handles the case where we have two consecutive
 469                        assignments of the same constant to pseudos that didn't
 470                        get a hard reg.  Each SET from the constant will be
 471                        converted into a SET of the spill register and an
 472                        output reload will be made following it.  This produces
 473                        two loads of the same constant into the same spill
 474                        register.  */
 475
 476                     rtx in_insn = insn;
 477
 478                     /* Look back for a death note for the first reg.
 479                        If there is one, it is no longer accurate.  */
 480                     while (in_insn && GET_CODE (in_insn) != CODE_LABEL)
 481                       {
 482                         if ((GET_CODE (in_insn) == INSN
 483                              || GET_CODE (in_insn) == JUMP_INSN)
 484                             && find_regno_note (in_insn, REG_DEAD, dreg))
 485                           {
 486                             remove_death (dreg, in_insn);
 487                             break;
 488                           }
 489                         in_insn = PREV_INSN (in_insn);
 490                       }
 491
 492                     /* Delete the second load of the value.  */
 493                     delete_insn (insn);
 494                   }
 495               }
 496             else if (GET_CODE (body) == PARALLEL)
 497               {
 498                 /* If each part is a set between two identical registers or
 499                    a USE or CLOBBER, delete the insn. */
 500                 int i, sreg, dreg;
 501                 rtx tem;
 502
 503                 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 504                   {
 505                     tem = XVECEXP (body, 0, i);
 506                     if (GET_CODE (tem) == USE || GET_CODE (tem) == CLOBBER)
 507                       continue;
 508
 509                     if (GET_CODE (tem) != SET
 510                         || (sreg = true_regnum (SET_SRC (tem))) < 0
 511                         || (dreg = true_regnum (SET_DEST (tem))) < 0
 512                         || dreg != sreg)
 513                       break;
 514                   }
 515
 516                 if (i < 0)
 517                   delete_insn (insn);
 518               }
 519 #if !BYTES_BIG_ENDIAN /* Not worth the hair to detect this
 520                          in the big-endian case.  */
 521             /* Also delete insns to store bit fields if they are no-ops.  */
 522             else if (GET_CODE (body) == SET
 523                      && GET_CODE (SET_DEST (body)) == ZERO_EXTRACT
 524                      && XEXP (SET_DEST (body), 2) == const0_rtx
 525                      && XEXP (SET_DEST (body), 0) == SET_SRC (body)
 526                      && ! (GET_CODE (SET_SRC (body)) == MEM
 527                            && MEM_VOLATILE_P (SET_SRC (body))))
 528               delete_insn (insn);
 529 #endif /* not BYTES_BIG_ENDIAN */
 530           }
 531       insn = next;
 532     }
 533
 534   /* If we haven't yet gotten to reload and we have just run regscan,
 535      delete any insn that sets a register that isn't used elsewhere.
 536      This helps some of the optimizations below by having less insns
 537      being jumped around.  */
 538
 539   if (! reload_completed && after_regscan)
 540     for (insn = f; insn; insn = next)
 541       {
 542         rtx set = single_set (insn);
 543
 544         next = NEXT_INSN (insn);
 545
 546         if (set && GET_CODE (SET_DEST (set)) == REG
 547             && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
 548             && regno_first_uid[REGNO (SET_DEST (set))] == INSN_UID (insn)
 549             /* We use regno_last_note_uid so as not to delete the setting
 550                of a reg that's used in notes.  A subsequent optimization
 551                might arrange to use that reg for real.  */
 552             && regno_last_note_uid[REGNO (SET_DEST (set))] == INSN_UID (insn)
 553             && ! side_effects_p (SET_SRC (set))
 554             && ! find_reg_note (insn, REG_RETVAL, 0))
 555           delete_insn (insn);
 556       }
 557
 558   /* Now iterate optimizing jumps until nothing changes over one pass.  */
 559   changed = 1;
 560   while (changed)
 561     {
 562       changed = 0;
 563
 564       for (insn = f; insn; insn = next)
 565         {
 566           rtx reallabelprev;
 567           rtx temp, temp1, temp2, temp3, temp4, temp5, temp6;
 568           rtx nlabel;
 569           int this_is_simplejump, this_is_condjump, reversep;
 570           int this_is_condjump_in_parallel;
 571 #if 0
 572           /* If NOT the first iteration, if this is the last jump pass
 573              (just before final), do the special peephole optimizations.
 574              Avoiding the first iteration gives ordinary jump opts
 575              a chance to work before peephole opts.  */
 576
 577           if (reload_completed && !first && !flag_no_peephole)
 578             if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
 579               peephole (insn);
 580 #endif
 581
 582           /* That could have deleted some insns after INSN, so check now
 583              what the following insn is.  */
 584
 585           next = NEXT_INSN (insn);
 586
 587           /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
 588              jump.  Try to optimize by duplicating the loop exit test if so.
 589              This is only safe immediately after regscan, because it uses
 590              the values of regno_first_uid and regno_last_uid.  */
 591           if (after_regscan && GET_CODE (insn) == NOTE
 592               && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 593               && (temp1 = next_nonnote_insn (insn)) != 0
 594               && simplejump_p (temp1))
 595             {
 596               temp = PREV_INSN (insn);
 597               if (duplicate_loop_exit_test (insn))
 598                 {
 599                   changed = 1;
 600                   next = NEXT_INSN (temp);
 601                   continue;
 602                 }
 603             }
 604
 605           if (GET_CODE (insn) != JUMP_INSN)
 606             continue;
 607
 608           this_is_simplejump = simplejump_p (insn);
 609           this_is_condjump = condjump_p (insn);
 610           this_is_condjump_in_parallel = condjump_in_parallel_p (insn);
 611
 612           /* Tension the labels in dispatch tables.  */
 613
 614           if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
 615             changed |= tension_vector_labels (PATTERN (insn), 0);
 616           if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 617             changed |= tension_vector_labels (PATTERN (insn), 1);
 618
 619           /* If a dispatch table always goes to the same place,
 620              get rid of it and replace the insn that uses it.  */
 621
 622           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 623               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 624             {
 625               int i;
 626               rtx pat = PATTERN (insn);
 627               int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
 628               int len = XVECLEN (pat, diff_vec_p);
 629               rtx dispatch = prev_real_insn (insn);
 630
 631               for (i = 0; i < len; i++)
 632                 if (XEXP (XVECEXP (pat, diff_vec_p, i), 0)
 633                     != XEXP (XVECEXP (pat, diff_vec_p, 0), 0))
 634                   break;
 635               if (i == len
 636                   && dispatch != 0
 637                   && GET_CODE (dispatch) == JUMP_INSN
 638                   && JUMP_LABEL (dispatch) != 0
 639                   /* Don't mess with a casesi insn.  */
 640                   && !(GET_CODE (PATTERN (dispatch)) == SET
 641                        && (GET_CODE (SET_SRC (PATTERN (dispatch)))
 642                            == IF_THEN_ELSE))
 643                   && next_real_insn (JUMP_LABEL (dispatch)) == insn)
 644                 {
 645                   redirect_tablejump (dispatch,
 646                                       XEXP (XVECEXP (pat, diff_vec_p, 0), 0));
 647                   changed = 1;
 648                 }
 649             }
 650
 651           reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 652
 653           /* If a jump references the end of the function, try to turn
 654              it into a RETURN insn, possibly a conditional one.  */
 655           if (JUMP_LABEL (insn)
 656               && (next_active_insn (JUMP_LABEL (insn)) == 0
 657                   || GET_CODE (PATTERN (next_active_insn (JUMP_LABEL (insn))))
 658                       == RETURN))
 659             changed |= redirect_jump (insn, NULL_RTX);
 660
 661           /* Detect jump to following insn.  */
 662           if (reallabelprev == insn && condjump_p (insn))
 663             {
 664               delete_jump (insn);
 665               changed = 1;
 666               continue;
 667             }
 668
 669           /* If we have an unconditional jump preceded by a USE, try to put
 670              the USE before the target and jump there.  This simplifies many
 671              of the optimizations below since we don't have to worry about
 672              dealing with these USE insns.  We only do this if the label
 673              being branch to already has the identical USE or if code
 674              never falls through to that label.  */
 675
 676           if (this_is_simplejump
 677               && (temp = prev_nonnote_insn (insn)) != 0
 678               && GET_CODE (temp) == INSN && GET_CODE (PATTERN (temp)) == USE
 679               && (temp1 = prev_nonnote_insn (JUMP_LABEL (insn))) != 0
 680               && (GET_CODE (temp1) == BARRIER
 681                   || (GET_CODE (temp1) == INSN
 682                       && rtx_equal_p (PATTERN (temp), PATTERN (temp1)))))
 683             {
 684               if (GET_CODE (temp1) == BARRIER)
 685                 {
 686                   emit_insn_after (PATTERN (temp), temp1);
 687                   temp1 = NEXT_INSN (temp1);
 688                 }
 689
 690               delete_insn (temp);
 691               redirect_jump (insn, get_label_before (temp1));
 692               reallabelprev = prev_real_insn (temp1);
 693               changed = 1;
 694             }
 695
 696           /* Simplify   if (...) x = a; else x = b; by converting it
 697              to         x = b; if (...) x = a;
 698              if B is sufficiently simple, the test doesn't involve X,
 699              and nothing in the test modifies B or X.
 700
 701              If we have small register classes, we also can't do this if X
 702              is a hard register.
 703
 704              If the "x = b;" insn has any REG_NOTES, we don't do this because
 705              of the possibility that we are running after CSE and there is a
 706              REG_EQUAL note that is only valid if the branch has already been
 707              taken.  If we move the insn with the REG_EQUAL note, we may
 708              fold the comparison to always be false in a later CSE pass.
 709              (We could also delete the REG_NOTES when moving the insn, but it
 710              seems simpler to not move it.)  An exception is that we can move
 711              the insn if the only note is a REG_EQUAL or REG_EQUIV whose
 712              value is the same as "b".
 713
 714              INSN is the branch over the `else' part.
 715
 716              We set:
 717
 718              TEMP to the jump insn preceding "x = a;"
 719              TEMP1 to X
 720              TEMP2 to the insn that sets "x = b;"
 721              TEMP3 to the insn that sets "x = a;"
 722              TEMP4 to the set of "x = b";  */
 723
 724           if (this_is_simplejump
 725               && (temp3 = prev_active_insn (insn)) != 0
 726               && GET_CODE (temp3) == INSN
 727               && (temp4 = single_set (temp3)) != 0
 728               && GET_CODE (temp1 = SET_DEST (temp4)) == REG
 729 #ifdef SMALL_REGISTER_CLASSES
 730               && REGNO (temp1) >= FIRST_PSEUDO_REGISTER
 731 #endif
 732               && (temp2 = next_active_insn (insn)) != 0
 733               && GET_CODE (temp2) == INSN
 734               && (temp4 = single_set (temp2)) != 0
 735               && rtx_equal_p (SET_DEST (temp4), temp1)
 736               && (GET_CODE (SET_SRC (temp4)) == REG
 737                   || GET_CODE (SET_SRC (temp4)) == SUBREG
 738                   || CONSTANT_P (SET_SRC (temp4)))
 739               && (REG_NOTES (temp2) == 0
 740                   || ((REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUAL
 741                        || REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUIV)
 742                       && XEXP (REG_NOTES (temp2), 1) == 0
 743                       && rtx_equal_p (XEXP (REG_NOTES (temp2), 0),
 744                                       SET_SRC (temp4))))
 745               && (temp = prev_active_insn (temp3)) != 0
 746               && condjump_p (temp) && ! simplejump_p (temp)
 747               /* TEMP must skip over the "x = a;" insn */
 748               && prev_real_insn (JUMP_LABEL (temp)) == insn
 749               && no_labels_between_p (insn, JUMP_LABEL (temp))
 750               /* There must be no other entries to the "x = b;" insn.  */
 751               && no_labels_between_p (JUMP_LABEL (temp), temp2)
 752               /* INSN must either branch to the insn after TEMP2 or the insn
 753                  after TEMP2 must branch to the same place as INSN.  */
 754               && (reallabelprev == temp2
 755                   || ((temp5 = next_active_insn (temp2)) != 0
 756                       && simplejump_p (temp5)
 757                       && JUMP_LABEL (temp5) == JUMP_LABEL (insn))))
 758             {
 759               /* The test expression, X, may be a complicated test with
 760                  multiple branches.  See if we can find all the uses of
 761                  the label that TEMP branches to without hitting a CALL_INSN
 762                  or a jump to somewhere else.  */
 763               rtx target = JUMP_LABEL (temp);
 764               int nuses = LABEL_NUSES (target);
 765               rtx p, q;
 766
 767               /* Set P to the first jump insn that goes around "x = a;".  */
 768               for (p = temp; nuses && p; p = prev_nonnote_insn (p))
 769                 {
 770                   if (GET_CODE (p) == JUMP_INSN)
 771                     {
 772                       if (condjump_p (p) && ! simplejump_p (p)
 773                           && JUMP_LABEL (p) == target)
 774                         {
 775                           nuses--;
 776                           if (nuses == 0)
 777                             break;
 778                         }
 779                       else
 780                         break;
 781                     }
 782                   else if (GET_CODE (p) == CALL_INSN)
 783                     break;
 784                 }
 785
 786 #ifdef HAVE_cc0
 787               /* We cannot insert anything between a set of cc and its use
 788                  so if P uses cc0, we must back up to the previous insn.  */
 789               q = prev_nonnote_insn (p);
 790               if (q && GET_RTX_CLASS (GET_CODE (q)) == 'i'
 791                   && sets_cc0_p (PATTERN (q)))
 792                 p = q;
 793 #endif
 794
 795               if (p)
 796                 p = PREV_INSN (p);
 797
 798               /* If we found all the uses and there was no data conflict, we
 799                  can move the assignment unless we can branch into the middle
 800                  from somewhere.  */
 801               if (nuses == 0 && p
 802                   && no_labels_between_p (p, insn)
 803                   && ! reg_referenced_between_p (temp1, p, NEXT_INSN (temp3))
 804                   && ! reg_set_between_p (temp1, p, temp3)
 805                   && (GET_CODE (SET_SRC (temp4)) == CONST_INT
 806                       || ! reg_set_between_p (SET_SRC (temp4), p, temp2)))
 807                 {
 808                   emit_insn_after_with_line_notes (PATTERN (temp2), p, temp2);
 809                   delete_insn (temp2);
 810
 811                   /* Set NEXT to an insn that we know won't go away.  */
 812                   next = next_active_insn (insn);
 813
 814                   /* Delete the jump around the set.  Note that we must do
 815                      this before we redirect the test jumps so that it won't
 816                      delete the code immediately following the assignment
 817                      we moved (which might be a jump).  */
 818
 819                   delete_insn (insn);
 820
 821                   /* We either have two consecutive labels or a jump to
 822                      a jump, so adjust all the JUMP_INSNs to branch to where
 823                      INSN branches to.  */
 824                   for (p = NEXT_INSN (p); p != next; p = NEXT_INSN (p))
 825                     if (GET_CODE (p) == JUMP_INSN)
 826                       redirect_jump (p, target);
 827
 828                   changed = 1;
 829                   continue;
 830                 }
 831             }
 832
 833 #ifndef HAVE_cc0
 834           /* If we have if (...) x = exp;  and branches are expensive,
 835              EXP is a single insn, does not have any side effects, cannot
 836              trap, and is not too costly, convert this to
 837              t = exp; if (...) x = t;
 838
 839              Don't do this when we have CC0 because it is unlikely to help
 840              and we'd need to worry about where to place the new insn and
 841              the potential for conflicts.  We also can't do this when we have
 842              notes on the insn for the same reason as above.
 843
 844              We set:
 845
 846              TEMP to the "x = exp;" insn.
 847              TEMP1 to the single set in the "x = exp; insn.
 848              TEMP2 to "x".  */
 849
 850           if (! reload_completed
 851               && this_is_condjump && ! this_is_simplejump
 852               && BRANCH_COST >= 3
 853               && (temp = next_nonnote_insn (insn)) != 0
 854               && GET_CODE (temp) == INSN
 855               && REG_NOTES (temp) == 0
 856               && (reallabelprev == temp
 857                   || ((temp2 = next_active_insn (temp)) != 0
 858                       && simplejump_p (temp2)
 859                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
 860               && (temp1 = single_set (temp)) != 0
 861               && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
 862               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
 863 #ifdef SMALL_REGISTER_CLASSES
 864               && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
 865 #endif
 866               && GET_CODE (SET_SRC (temp1)) != REG
 867               && GET_CODE (SET_SRC (temp1)) != SUBREG
 868               && GET_CODE (SET_SRC (temp1)) != CONST_INT
 869               && ! side_effects_p (SET_SRC (temp1))
 870               && ! may_trap_p (SET_SRC (temp1))
 871               && rtx_cost (SET_SRC (temp1)) < 10)
 872             {
 873               rtx new = gen_reg_rtx (GET_MODE (temp2));
 874
 875               if (validate_change (temp, &SET_DEST (temp1), new, 0))
 876                 {
 877                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
 878                   emit_insn_after_with_line_notes (PATTERN (temp),
 879                                                    PREV_INSN (insn), temp);
 880                   delete_insn (temp);
 881                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 882                 }
 883             }
 884
 885           /* Similarly, if it takes two insns to compute EXP but they
 886              have the same destination.  Here TEMP3 will be the second
 887              insn and TEMP4 the SET from that insn.  */
 888
 889           if (! reload_completed
 890               && this_is_condjump && ! this_is_simplejump
 891               && BRANCH_COST >= 4
 892               && (temp = next_nonnote_insn (insn)) != 0
 893               && GET_CODE (temp) == INSN
 894               && REG_NOTES (temp) == 0
 895               && (temp3 = next_nonnote_insn (temp)) != 0
 896               && GET_CODE (temp3) == INSN
 897               && REG_NOTES (temp3) == 0
 898               && (reallabelprev == temp3
 899                   || ((temp2 = next_active_insn (temp3)) != 0
 900                       && simplejump_p (temp2)
 901                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
 902               && (temp1 = single_set (temp)) != 0
 903               && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
 904               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
 905 #ifdef SMALL_REGISTER_CLASSES
 906               && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
 907 #endif
 908               && ! side_effects_p (SET_SRC (temp1))
 909               && ! may_trap_p (SET_SRC (temp1))
 910               && rtx_cost (SET_SRC (temp1)) < 10
 911               && (temp4 = single_set (temp3)) != 0
 912               && rtx_equal_p (SET_DEST (temp4), temp2)
 913               && ! side_effects_p (SET_SRC (temp4))
 914               && ! may_trap_p (SET_SRC (temp4))
 915               && rtx_cost (SET_SRC (temp4)) < 10)
 916             {
 917               rtx new = gen_reg_rtx (GET_MODE (temp2));
 918
 919               if (validate_change (temp, &SET_DEST (temp1), new, 0))
 920                 {
 921                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
 922                   emit_insn_after_with_line_notes (PATTERN (temp),
 923                                                    PREV_INSN (insn), temp);
 924                   emit_insn_after_with_line_notes
 925                     (replace_rtx (PATTERN (temp3), temp2, new),
 926                      PREV_INSN (insn), temp3);
 927                   delete_insn (temp);
 928                   delete_insn (temp3);
 929                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 930                 }
 931             }
 932
 933           /* Finally, handle the case where two insns are used to
 934              compute EXP but a temporary register is used.  Here we must
 935              ensure that the temporary register is not used anywhere else. */
 936
 937           if (! reload_completed
 938               && after_regscan
 939               && this_is_condjump && ! this_is_simplejump
 940               && BRANCH_COST >= 4
 941               && (temp = next_nonnote_insn (insn)) != 0
 942               && GET_CODE (temp) == INSN
 943               && REG_NOTES (temp) == 0
 944               && (temp3 = next_nonnote_insn (temp)) != 0
 945               && GET_CODE (temp3) == INSN
 946               && REG_NOTES (temp3) == 0
 947               && (reallabelprev == temp3
 948                   || ((temp2 = next_active_insn (temp3)) != 0
 949                       && simplejump_p (temp2)
 950                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
 951               && (temp1 = single_set (temp)) != 0
 952               && (temp5 = SET_DEST (temp1),
 953                   (GET_CODE (temp5) == REG
 954                    || (GET_CODE (temp5) == SUBREG
 955                        && (temp5 = SUBREG_REG (temp5),
 956                            GET_CODE (temp5) == REG))))
 957               && REGNO (temp5) >= FIRST_PSEUDO_REGISTER
 958               && regno_first_uid[REGNO (temp5)] == INSN_UID (temp)
 959               && regno_last_uid[REGNO (temp5)] == INSN_UID (temp3)
 960               && ! side_effects_p (SET_SRC (temp1))
 961               && ! may_trap_p (SET_SRC (temp1))
 962               && rtx_cost (SET_SRC (temp1)) < 10
 963               && (temp4 = single_set (temp3)) != 0
 964               && (temp2 = SET_DEST (temp4), GET_CODE (temp2) == REG)
 965               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
 966 #ifdef SMALL_REGISTER_CLASSES
 967               && REGNO (temp2) >= FIRST_PSEUDO_REGISTER
 968 #endif
 969               && rtx_equal_p (SET_DEST (temp4), temp2)
 970               && ! side_effects_p (SET_SRC (temp4))
 971               && ! may_trap_p (SET_SRC (temp4))
 972               && rtx_cost (SET_SRC (temp4)) < 10)
 973             {
 974               rtx new = gen_reg_rtx (GET_MODE (temp2));
 975
 976               if (validate_change (temp3, &SET_DEST (temp4), new, 0))
 977                 {
 978                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
 979                   emit_insn_after_with_line_notes (PATTERN (temp),
 980                                                    PREV_INSN (insn), temp);
 981                   emit_insn_after_with_line_notes (PATTERN (temp3),
 982                                                    PREV_INSN (insn), temp3);
 983                   delete_insn (temp);
 984                   delete_insn (temp3);
 985                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 986                 }
 987             }
 988 #endif /* HAVE_cc0 */
 989
 990           /* We deal with four cases:
 991
 992              1) x = a; if (...) x = b; and either A or B is zero,
 993              2) if (...) x = 0; and jumps are expensive,
 994              3) x = a; if (...) x = b; and A and B are constants where all the
 995                 set bits in A are also set in B and jumps are expensive, and
 996              4) x = a; if (...) x = b; and A and B non-zero, and jumps are
 997                 more expensive.
 998              5) if (...) x = b; if jumps are even more expensive.
 999
1000              In each of these try to use a store-flag insn to avoid the jump.
1001              (If the jump would be faster, the machine should not have
1002              defined the scc insns!).  These cases are often made by the
1003              previous optimization.
1004
1005              INSN here is the jump around the store.  We set:
1006
1007              TEMP to the "x = b;" insn.
1008              TEMP1 to X.
1009              TEMP2 to B (const0_rtx in the second case).
1010              TEMP3 to A (X in the second case).
1011              TEMP4 to the condition being tested.
1012              TEMP5 to the earliest insn used to find the condition.  */
1013
1014           if (/* We can't do this after reload has completed.  */
1015               ! reload_completed
1016               && this_is_condjump && ! this_is_simplejump
1017               /* Set TEMP to the "x = b;" insn.  */
1018               && (temp = next_nonnote_insn (insn)) != 0
1019               && GET_CODE (temp) == INSN
1020               && GET_CODE (PATTERN (temp)) == SET
1021               && GET_CODE (temp1 = SET_DEST (PATTERN (temp))) == REG
1022 #ifdef SMALL_REGISTER_CLASSES
1023               && REGNO (temp1) >= FIRST_PSEUDO_REGISTER
1024 #endif
1025               && GET_MODE_CLASS (GET_MODE (temp1)) == MODE_INT
1026               && (GET_CODE (temp2 = SET_SRC (PATTERN (temp))) == REG
1027                   || GET_CODE (temp2) == SUBREG
1028                   || GET_CODE (temp2) == CONST_INT)
1029               /* Allow either form, but prefer the former if both apply.
1030                  There is no point in using the old value of TEMP1 if
1031                  it is a register, since cse will alias them.  It can
1032                  lose if the old value were a hard register since CSE
1033                  won't replace hard registers.  */
1034               && (((temp3 = reg_set_last (temp1, insn)) != 0
1035                    && GET_CODE (temp3) == CONST_INT)
1036                   /* Make the latter case look like  x = x; if (...) x = 0;  */
1037                   || (temp3 = temp1,
1038                       ((BRANCH_COST >= 2
1039                         && temp2 == const0_rtx)
1040 #ifdef HAVE_conditional_move
1041                        || HAVE_conditional_move
1042 #endif
1043                        || BRANCH_COST >= 3)))
1044               /* INSN must either branch to the insn after TEMP or the insn
1045                  after TEMP must branch to the same place as INSN.  */
1046               && (reallabelprev == temp
1047                   || ((temp4 = next_active_insn (temp)) != 0
1048                       && simplejump_p (temp4)
1049                       && JUMP_LABEL (temp4) == JUMP_LABEL (insn)))
1050               && (temp4 = get_condition (insn, &temp5)) != 0
1051               /* We must be comparing objects whose modes imply the size.
1052                  We could handle BLKmode if (1) emit_store_flag could
1053                  and (2) we could find the size reliably.  */
1054               && GET_MODE (XEXP (temp4, 0)) != BLKmode
1055
1056               /* If B is zero, OK; if A is zero, can only do (1) if we
1057                  can reverse the condition.  See if (3) applies possibly
1058                  by reversing the condition.  Prefer reversing to (4) when
1059                  branches are very expensive.  */
1060               && ((reversep = 0, temp2 == const0_rtx)
1061                   || (temp3 == const0_rtx
1062                       && (reversep = can_reverse_comparison_p (temp4, insn)))
1063                   || (BRANCH_COST >= 2
1064                       && GET_CODE (temp2) == CONST_INT
1065                       && GET_CODE (temp3) == CONST_INT
1066                       && ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp2)
1067                           || ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp3)
1068                               && (reversep = can_reverse_comparison_p (temp4,
1069                                                                        insn)))))
1070 #ifdef HAVE_conditional_move
1071                   || HAVE_conditional_move
1072 #endif
1073                   || BRANCH_COST >= 3)
1074 #ifdef HAVE_cc0
1075               /* If the previous insn sets CC0 and something else, we can't
1076                  do this since we are going to delete that insn.  */
1077
1078               && ! ((temp6 = prev_nonnote_insn (insn)) != 0
1079                     && GET_CODE (temp6) == INSN
1080                     && (sets_cc0_p (PATTERN (temp6)) == -1
1081                         || (sets_cc0_p (PATTERN (temp6)) == 1
1082                             && FIND_REG_INC_NOTE (temp6, NULL_RTX))))
1083 #endif
1084               )
1085             {
1086               enum rtx_code code = GET_CODE (temp4);
1087               rtx uval, cval, var = temp1;
1088               int normalizep;
1089               rtx target;
1090
1091               /* If necessary, reverse the condition.  */
1092               if (reversep)
1093                 code = reverse_condition (code), uval = temp2, cval = temp3;
1094               else
1095                 uval = temp3, cval = temp2;
1096
1097               /* See if we can do this with a store-flag insn. */
1098               start_sequence ();
1099
1100               /* If CVAL is non-zero, normalize to -1.  Otherwise,
1101                  if UVAL is the constant 1, it is best to just compute
1102                  the result directly.  If UVAL is constant and STORE_FLAG_VALUE
1103                  includes all of its bits, it is best to compute the flag
1104                  value unnormalized and `and' it with UVAL.  Otherwise,
1105                  normalize to -1 and `and' with UVAL.  */
1106               normalizep = (cval != const0_rtx ? -1
1107                             : (uval == const1_rtx ? 1
1108                                : (GET_CODE (uval) == CONST_INT
1109                                   && (INTVAL (uval) & ~STORE_FLAG_VALUE) == 0)
1110                                ? 0 : -1));
1111
1112               /* We will be putting the store-flag insn immediately in
1113                  front of the comparison that was originally being done,
1114                  so we know all the variables in TEMP4 will be valid.
1115                  However, this might be in front of the assignment of
1116                  A to VAR.  If it is, it would clobber the store-flag
1117                  we will be emitting.
1118
1119                  Therefore, emit into a temporary which will be copied to
1120                  VAR immediately after TEMP.  */
1121
1122               target = emit_store_flag (gen_reg_rtx (GET_MODE (var)), code,
1123                                         XEXP (temp4, 0), XEXP (temp4, 1),
1124                                         VOIDmode,
1125                                         (code == LTU || code == LEU
1126                                          || code == GEU || code == GTU),
1127                                         normalizep);
1128               if (target)
1129                 {
1130                   rtx before = insn;
1131                   rtx seq;
1132
1133                   /* Put the store-flag insns in front of the first insn
1134                      used to compute the condition to ensure that we
1135                      use the same values of them as the current
1136                      comparison.  However, the remainder of the insns we
1137                      generate will be placed directly in front of the
1138                      jump insn, in case any of the pseudos we use
1139                      are modified earlier.  */
1140
1141                   seq = get_insns ();
1142                   end_sequence ();
1143
1144                   emit_insns_before (seq, temp5);
1145
1146                   start_sequence ();
1147
1148                   /* Both CVAL and UVAL are non-zero.  */
1149                   if (cval != const0_rtx && uval != const0_rtx)
1150                     {
1151                       rtx tem1, tem2;
1152
1153                       tem1 = expand_and (uval, target, NULL_RTX);
1154                       if (GET_CODE (cval) == CONST_INT
1155                           && GET_CODE (uval) == CONST_INT
1156                           && (INTVAL (cval) & INTVAL (uval)) == INTVAL (cval))
1157                         tem2 = cval;
1158                       else
1159                         {
1160                           tem2 = expand_unop (GET_MODE (var), one_cmpl_optab,
1161                                               target, NULL_RTX, 0);
1162                           tem2 = expand_and (cval, tem2,
1163                                              (GET_CODE (tem2) == REG
1164                                               ? tem2 : 0));
1165                         }
1166
1167                       /* If we usually make new pseudos, do so here.  This
1168                          turns out to help machines that have conditional
1169                          move insns.  */
1170
1171                       if (flag_expensive_optimizations)
1172                         target = 0;
1173
1174                       target = expand_binop (GET_MODE (var), ior_optab,
1175                                              tem1, tem2, target,
1176                                              1, OPTAB_WIDEN);
1177                     }
1178                   else if (normalizep != 1)
1179                     {
1180                       /* We know that either CVAL or UVAL is zero.  If
1181                          UVAL is zero, negate TARGET and `and' with CVAL.
1182                          Otherwise, `and' with UVAL.  */
1183                       if (uval == const0_rtx)
1184                         {
1185                           target = expand_unop (GET_MODE (var), one_cmpl_optab,
1186                                                 target, NULL_RTX, 0);
1187                           uval = cval;
1188                         }
1189
1190                       target = expand_and (uval, target,
1191                                            (GET_CODE (target) == REG
1192                                             && ! preserve_subexpressions_p ()
1193                                             ? target : NULL_RTX));
1194                     }
1195
1196                   emit_move_insn (var, target);
1197                   seq = get_insns ();
1198                   end_sequence ();
1199
1200 #ifdef HAVE_cc0
1201                   /* If INSN uses CC0, we must not separate it from the
1202                      insn that sets cc0.  */
1203
1204                   if (reg_mentioned_p (cc0_rtx, PATTERN (before)))
1205                     before = prev_nonnote_insn (before);
1206 #endif
1207
1208                   emit_insns_before (seq, before);
1209
1210                   delete_insn (temp);
1211                   next = NEXT_INSN (insn);
1212
1213                   delete_jump (insn);
1214                   changed = 1;
1215                   continue;
1216                 }
1217               else
1218                 end_sequence ();
1219             }
1220
1221           /* If branches are expensive, convert
1222                 if (foo) bar++;    to    bar += (foo != 0);
1223              and similarly for "bar--;"
1224
1225              INSN is the conditional branch around the arithmetic.  We set:
1226
1227              TEMP is the arithmetic insn.
1228              TEMP1 is the SET doing the arithmetic.
1229              TEMP2 is the operand being incremented or decremented.
1230              TEMP3 to the condition being tested.
1231              TEMP4 to the earliest insn used to find the condition.  */
1232
1233           if ((BRANCH_COST >= 2
1234 #ifdef HAVE_incscc
1235                || HAVE_incscc
1236 #endif
1237 #ifdef HAVE_decscc
1238                || HAVE_decscc
1239 #endif
1240               )
1241               && ! reload_completed
1242               && this_is_condjump && ! this_is_simplejump
1243               && (temp = next_nonnote_insn (insn)) != 0
1244               && (temp1 = single_set (temp)) != 0
1245               && (temp2 = SET_DEST (temp1),
1246                   GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT)
1247               && GET_CODE (SET_SRC (temp1)) == PLUS
1248               && (XEXP (SET_SRC (temp1), 1) == const1_rtx
1249                   || XEXP (SET_SRC (temp1), 1) == constm1_rtx)
1250               && rtx_equal_p (temp2, XEXP (SET_SRC (temp1), 0))
1251               && ! side_effects_p (temp2)
1252               && ! may_trap_p (temp2)
1253               /* INSN must either branch to the insn after TEMP or the insn
1254                  after TEMP must branch to the same place as INSN.  */
1255               && (reallabelprev == temp
1256                   || ((temp3 = next_active_insn (temp)) != 0
1257                       && simplejump_p (temp3)
1258                       && JUMP_LABEL (temp3) == JUMP_LABEL (insn)))
1259               && (temp3 = get_condition (insn, &temp4)) != 0
1260               /* We must be comparing objects whose modes imply the size.
1261                  We could handle BLKmode if (1) emit_store_flag could
1262                  and (2) we could find the size reliably.  */
1263               && GET_MODE (XEXP (temp3, 0)) != BLKmode
1264               && can_reverse_comparison_p (temp3, insn))
1265             {
1266               rtx temp6, target = 0, seq, init_insn = 0, init = temp2;
1267               enum rtx_code code = reverse_condition (GET_CODE (temp3));
1268
1269               start_sequence ();
1270
1271               /* It must be the case that TEMP2 is not modified in the range
1272                  [TEMP4, INSN).  The one exception we make is if the insn
1273                  before INSN sets TEMP2 to something which is also unchanged
1274                  in that range.  In that case, we can move the initialization
1275                  into our sequence.  */
1276
1277               if ((temp5 = prev_active_insn (insn)) != 0
1278                   && GET_CODE (temp5) == INSN
1279                   && (temp6 = single_set (temp5)) != 0
1280                   && rtx_equal_p (temp2, SET_DEST (temp6))
1281                   && (CONSTANT_P (SET_SRC (temp6))
1282                       || GET_CODE (SET_SRC (temp6)) == REG
1283                       || GET_CODE (SET_SRC (temp6)) == SUBREG))
1284                 {
1285                   emit_insn (PATTERN (temp5));
1286                   init_insn = temp5;
1287                   init = SET_SRC (temp6);
1288                 }
1289
1290               if (CONSTANT_P (init)
1291                   || ! reg_set_between_p (init, PREV_INSN (temp4), insn))
1292                 target = emit_store_flag (gen_reg_rtx (GET_MODE (temp2)), code,
1293                                           XEXP (temp3, 0), XEXP (temp3, 1),
1294                                           VOIDmode,
1295                                           (code == LTU || code == LEU
1296                                            || code == GTU || code == GEU), 1);
1297
1298               /* If we can do the store-flag, do the addition or
1299                  subtraction.  */
1300
1301               if (target)
1302                 target = expand_binop (GET_MODE (temp2),
1303                                        (XEXP (SET_SRC (temp1), 1) == const1_rtx
1304                                         ? add_optab : sub_optab),
1305                                        temp2, target, temp2, 0, OPTAB_WIDEN);
1306
1307               if (target != 0)
1308                 {
1309                   /* Put the result back in temp2 in case it isn't already.
1310                      Then replace the jump, possible a CC0-setting insn in
1311                      front of the jump, and TEMP, with the sequence we have
1312                      made.  */
1313
1314                   if (target != temp2)
1315                     emit_move_insn (temp2, target);
1316
1317                   seq = get_insns ();
1318                   end_sequence ();
1319
1320                   emit_insns_before (seq, temp4);
1321                   delete_insn (temp);
1322
1323                   if (init_insn)
1324                     delete_insn (init_insn);
1325
1326                   next = NEXT_INSN (insn);
1327 #ifdef HAVE_cc0
1328                   delete_insn (prev_nonnote_insn (insn));
1329 #endif
1330                   delete_insn (insn);
1331                   changed = 1;
1332                   continue;
1333                 }
1334               else
1335                 end_sequence ();
1336             }
1337
1338           /* Simplify   if (...) x = 1; else {...}  if (x) ...
1339              We recognize this case scanning backwards as well.
1340
1341              TEMP is the assignment to x;
1342              TEMP1 is the label at the head of the second if.  */
1343           /* ?? This should call get_condition to find the values being
1344              compared, instead of looking for a COMPARE insn when HAVE_cc0
1345              is not defined.  This would allow it to work on the m88k.  */
1346           /* ?? This optimization is only safe before cse is run if HAVE_cc0
1347              is not defined and the condition is tested by a separate compare
1348              insn.  This is because the code below assumes that the result
1349              of the compare dies in the following branch.
1350
1351              Not only that, but there might be other insns between the
1352              compare and branch whose results are live.  Those insns need
1353              to be executed.
1354
1355              A way to fix this is to move the insns at JUMP_LABEL (insn)
1356              to before INSN.  If we are running before flow, they will
1357              be deleted if they aren't needed.   But this doesn't work
1358              well after flow.
1359
1360              This is really a special-case of jump threading, anyway.  The
1361              right thing to do is to replace this and jump threading with
1362              much simpler code in cse.
1363
1364              This code has been turned off in the non-cc0 case in the
1365              meantime.  */
1366
1367 #ifdef HAVE_cc0
1368           else if (this_is_simplejump
1369                    /* Safe to skip USE and CLOBBER insns here
1370                       since they will not be deleted.  */
1371                    && (temp = prev_active_insn (insn))
1372                    && no_labels_between_p (temp, insn)
1373                    && GET_CODE (temp) == INSN
1374                    && GET_CODE (PATTERN (temp)) == SET
1375                    && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1376                    && CONSTANT_P (SET_SRC (PATTERN (temp)))
1377                    && (temp1 = next_active_insn (JUMP_LABEL (insn)))
1378                    /* If we find that the next value tested is `x'
1379                       (TEMP1 is the insn where this happens), win.  */
1380                    && GET_CODE (temp1) == INSN
1381                    && GET_CODE (PATTERN (temp1)) == SET
1382 #ifdef HAVE_cc0
1383                    /* Does temp1 `tst' the value of x?  */
1384                    && SET_SRC (PATTERN (temp1)) == SET_DEST (PATTERN (temp))
1385                    && SET_DEST (PATTERN (temp1)) == cc0_rtx
1386                    && (temp1 = next_nonnote_insn (temp1))
1387 #else
1388                    /* Does temp1 compare the value of x against zero?  */
1389                    && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1390                    && XEXP (SET_SRC (PATTERN (temp1)), 1) == const0_rtx
1391                    && (XEXP (SET_SRC (PATTERN (temp1)), 0)
1392                        == SET_DEST (PATTERN (temp)))
1393                    && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1394                    && (temp1 = find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1395 #endif
1396                    && condjump_p (temp1))
1397             {
1398               /* Get the if_then_else from the condjump.  */
1399               rtx choice = SET_SRC (PATTERN (temp1));
1400               if (GET_CODE (choice) == IF_THEN_ELSE)
1401                 {
1402                   enum rtx_code code = GET_CODE (XEXP (choice, 0));
1403                   rtx val = SET_SRC (PATTERN (temp));
1404                   rtx cond
1405                     = simplify_relational_operation (code, GET_MODE (SET_DEST (PATTERN (temp))),
1406                                                      val, const0_rtx);
1407                   rtx ultimate;
1408
1409                   if (cond == const_true_rtx)
1410                     ultimate = XEXP (choice, 1);
1411                   else if (cond == const0_rtx)
1412                     ultimate = XEXP (choice, 2);
1413                   else
1414                     ultimate = 0;
1415
1416                   if (ultimate == pc_rtx)
1417                     ultimate = get_label_after (temp1);
1418                   else if (ultimate && GET_CODE (ultimate) != RETURN)
1419                     ultimate = XEXP (ultimate, 0);
1420
1421                   if (ultimate)
1422                     changed |= redirect_jump (insn, ultimate);
1423                 }
1424             }
1425 #endif
1426
1427 #if 0
1428           /* @@ This needs a bit of work before it will be right.
1429
1430              Any type of comparison can be accepted for the first and
1431              second compare.  When rewriting the first jump, we must
1432              compute the what conditions can reach label3, and use the
1433              appropriate code.  We can not simply reverse/swap the code
1434              of the first jump.  In some cases, the second jump must be
1435              rewritten also.
1436
1437              For example,
1438              <  == converts to >  ==
1439              <  != converts to ==  >
1440              etc.
1441
1442              If the code is written to only accept an '==' test for the second
1443              compare, then all that needs to be done is to swap the condition
1444              of the first branch.
1445
1446              It is questionable whether we want this optimization anyways,
1447              since if the user wrote code like this because he/she knew that
1448              the jump to label1 is taken most of the time, then rewriting
1449              this gives slower code.  */
1450           /* @@ This should call get_condition to find the values being
1451              compared, instead of looking for a COMPARE insn when HAVE_cc0
1452              is not defined.  This would allow it to work on the m88k.  */
1453           /* @@ This optimization is only safe before cse is run if HAVE_cc0
1454              is not defined and the condition is tested by a separate compare
1455              insn.  This is because the code below assumes that the result
1456              of the compare dies in the following branch.  */
1457
1458           /* Simplify  test a ~= b
1459                        condjump label1;
1460                        test a == b
1461                        condjump label2;
1462                        jump label3;
1463                        label1:
1464
1465              rewriting as
1466                        test a ~~= b
1467                        condjump label3
1468                        test a == b
1469                        condjump label2
1470                        label1:
1471
1472              where ~= is an inequality, e.g. >, and ~~= is the swapped
1473              inequality, e.g. <.
1474
1475              We recognize this case scanning backwards.
1476
1477              TEMP is the conditional jump to `label2';
1478              TEMP1 is the test for `a == b';
1479              TEMP2 is the conditional jump to `label1';
1480              TEMP3 is the test for `a ~= b'.  */
1481           else if (this_is_simplejump
1482                    && (temp = prev_active_insn (insn))
1483                    && no_labels_between_p (temp, insn)
1484                    && condjump_p (temp)
1485                    && (temp1 = prev_active_insn (temp))
1486                    && no_labels_between_p (temp1, temp)
1487                    && GET_CODE (temp1) == INSN
1488                    && GET_CODE (PATTERN (temp1)) == SET
1489 #ifdef HAVE_cc0
1490                    && sets_cc0_p (PATTERN (temp1)) == 1
1491 #else
1492                    && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1493                    && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1494                    && (temp == find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1495 #endif
1496                    && (temp2 = prev_active_insn (temp1))
1497                    && no_labels_between_p (temp2, temp1)
1498                    && condjump_p (temp2)
1499                    && JUMP_LABEL (temp2) == next_nonnote_insn (NEXT_INSN (insn))
1500                    && (temp3 = prev_active_insn (temp2))
1501                    && no_labels_between_p (temp3, temp2)
1502                    && GET_CODE (PATTERN (temp3)) == SET
1503                    && rtx_equal_p (SET_DEST (PATTERN (temp3)),
1504                                    SET_DEST (PATTERN (temp1)))
1505                    && rtx_equal_p (SET_SRC (PATTERN (temp1)),
1506                                    SET_SRC (PATTERN (temp3)))
1507                    && ! inequality_comparisons_p (PATTERN (temp))
1508                    && inequality_comparisons_p (PATTERN (temp2)))
1509             {
1510               rtx fallthrough_label = JUMP_LABEL (temp2);
1511
1512               ++LABEL_NUSES (fallthrough_label);
1513               if (swap_jump (temp2, JUMP_LABEL (insn)))
1514                 {
1515                   delete_insn (insn);
1516                   changed = 1;
1517                 }
1518
1519               if (--LABEL_NUSES (fallthrough_label) == 0)
1520                 delete_insn (fallthrough_label);
1521             }
1522 #endif
1523           /* Simplify  if (...) {... x = 1;} if (x) ...
1524
1525              We recognize this case backwards.
1526
1527              TEMP is the test of `x';
1528              TEMP1 is the assignment to `x' at the end of the
1529              previous statement.  */
1530           /* @@ This should call get_condition to find the values being
1531              compared, instead of looking for a COMPARE insn when HAVE_cc0
1532              is not defined.  This would allow it to work on the m88k.  */
1533           /* @@ This optimization is only safe before cse is run if HAVE_cc0
1534              is not defined and the condition is tested by a separate compare
1535              insn.  This is because the code below assumes that the result
1536              of the compare dies in the following branch.  */
1537
1538           /* ??? This has to be turned off.  The problem is that the
1539              unconditional jump might indirectly end up branching to the
1540              label between TEMP1 and TEMP.  We can't detect this, in general,
1541              since it may become a jump to there after further optimizations.
1542              If that jump is done, it will be deleted, so we will retry
1543              this optimization in the next pass, thus an infinite loop.
1544
1545              The present code prevents this by putting the jump after the
1546              label, but this is not logically correct.  */
1547 #if 0
1548           else if (this_is_condjump
1549                    /* Safe to skip USE and CLOBBER insns here
1550                       since they will not be deleted.  */
1551                    && (temp = prev_active_insn (insn))
1552                    && no_labels_between_p (temp, insn)
1553                    && GET_CODE (temp) == INSN
1554                    && GET_CODE (PATTERN (temp)) == SET
1555 #ifdef HAVE_cc0
1556                    && sets_cc0_p (PATTERN (temp)) == 1
1557                    && GET_CODE (SET_SRC (PATTERN (temp))) == REG
1558 #else
1559                    /* Temp must be a compare insn, we can not accept a register
1560                       to register move here, since it may not be simply a
1561                       tst insn.  */
1562                    && GET_CODE (SET_SRC (PATTERN (temp))) == COMPARE
1563                    && XEXP (SET_SRC (PATTERN (temp)), 1) == const0_rtx
1564                    && GET_CODE (XEXP (SET_SRC (PATTERN (temp)), 0)) == REG
1565                    && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1566                    && insn == find_next_ref (SET_DEST (PATTERN (temp)), temp)
1567 #endif
1568                    /* May skip USE or CLOBBER insns here
1569                       for checking for opportunity, since we
1570                       take care of them later.  */
1571                    && (temp1 = prev_active_insn (temp))
1572                    && GET_CODE (temp1) == INSN
1573                    && GET_CODE (PATTERN (temp1)) == SET
1574 #ifdef HAVE_cc0
1575                    && SET_SRC (PATTERN (temp)) == SET_DEST (PATTERN (temp1))
1576 #else
1577                    && (XEXP (SET_SRC (PATTERN (temp)), 0)
1578                        == SET_DEST (PATTERN (temp1)))
1579 #endif
1580                    && CONSTANT_P (SET_SRC (PATTERN (temp1)))
1581                    /* If this isn't true, cse will do the job.  */
1582                    && ! no_labels_between_p (temp1, temp))
1583             {
1584               /* Get the if_then_else from the condjump.  */
1585               rtx choice = SET_SRC (PATTERN (insn));
1586               if (GET_CODE (choice) == IF_THEN_ELSE
1587                   && (GET_CODE (XEXP (choice, 0)) == EQ
1588                       || GET_CODE (XEXP (choice, 0)) == NE))
1589                 {
1590                   int want_nonzero = (GET_CODE (XEXP (choice, 0)) == NE);
1591                   rtx last_insn;
1592                   rtx ultimate;
1593                   rtx p;
1594
1595                   /* Get the place that condjump will jump to
1596                      if it is reached from here.  */
1597                   if ((SET_SRC (PATTERN (temp1)) != const0_rtx)
1598                       == want_nonzero)
1599                     ultimate = XEXP (choice, 1);
1600                   else
1601                     ultimate = XEXP (choice, 2);
1602                   /* Get it as a CODE_LABEL.  */
1603                   if (ultimate == pc_rtx)
1604                     ultimate = get_label_after (insn);
1605                   else
1606                     /* Get the label out of the LABEL_REF.  */
1607                     ultimate = XEXP (ultimate, 0);
1608
1609                   /* Insert the jump immediately before TEMP, specifically
1610                      after the label that is between TEMP1 and TEMP.  */
1611                   last_insn = PREV_INSN (temp);
1612
1613                   /* If we would be branching to the next insn, the jump
1614                      would immediately be deleted and the re-inserted in
1615                      a subsequent pass over the code.  So don't do anything
1616                      in that case.  */
1617                   if (next_active_insn (last_insn)
1618                       != next_active_insn (ultimate))
1619                     {
1620                       emit_barrier_after (last_insn);
1621                       p = emit_jump_insn_after (gen_jump (ultimate),
1622                                                 last_insn);
1623                       JUMP_LABEL (p) = ultimate;
1624                       ++LABEL_NUSES (ultimate);
1625                       if (INSN_UID (ultimate) < max_jump_chain
1626                           && INSN_CODE (p) < max_jump_chain)
1627                         {
1628                           jump_chain[INSN_UID (p)]
1629                             = jump_chain[INSN_UID (ultimate)];
1630                           jump_chain[INSN_UID (ultimate)] = p;
1631                         }
1632                       changed = 1;
1633                       continue;
1634                     }
1635                 }
1636             }
1637 #endif
1638           /* Detect a conditional jump going to the same place
1639              as an immediately following unconditional jump.  */
1640           else if (this_is_condjump
1641                    && (temp = next_active_insn (insn)) != 0
1642                    && simplejump_p (temp)
1643                    && (next_active_insn (JUMP_LABEL (insn))
1644                        == next_active_insn (JUMP_LABEL (temp))))
1645             {
1646               delete_jump (insn);
1647               changed = 1;
1648               continue;
1649             }
1650           /* Detect a conditional jump jumping over an unconditional jump.  */
1651
1652           else if ((this_is_condjump || this_is_condjump_in_parallel)
1653                    && ! this_is_simplejump
1654                    && reallabelprev != 0
1655                    && GET_CODE (reallabelprev) == JUMP_INSN
1656                    && prev_active_insn (reallabelprev) == insn
1657                    && no_labels_between_p (insn, reallabelprev)
1658                    && simplejump_p (reallabelprev))
1659             {
1660               /* When we invert the unconditional jump, we will be
1661                  decrementing the usage count of its old label.
1662                  Make sure that we don't delete it now because that
1663                  might cause the following code to be deleted.  */
1664               rtx prev_uses = prev_nonnote_insn (reallabelprev);
1665               rtx prev_label = JUMP_LABEL (insn);
1666
1667               if (prev_label)
1668                 ++LABEL_NUSES (prev_label);
1669
1670               if (invert_jump (insn, JUMP_LABEL (reallabelprev)))
1671                 {
1672                   /* It is very likely that if there are USE insns before
1673                      this jump, they hold REG_DEAD notes.  These REG_DEAD
1674                      notes are no longer valid due to this optimization,
1675                      and will cause the life-analysis that following passes
1676                      (notably delayed-branch scheduling) to think that
1677                      these registers are dead when they are not.
1678
1679                      To prevent this trouble, we just remove the USE insns
1680                      from the insn chain.  */
1681
1682                   while (prev_uses && GET_CODE (prev_uses) == INSN
1683                          && GET_CODE (PATTERN (prev_uses)) == USE)
1684                     {
1685                       rtx useless = prev_uses;
1686                       prev_uses = prev_nonnote_insn (prev_uses);
1687                       delete_insn (useless);
1688                     }
1689
1690                   delete_insn (reallabelprev);
1691                   next = insn;
1692                   changed = 1;
1693                 }
1694
1695               /* We can now safely delete the label if it is unreferenced
1696                  since the delete_insn above has deleted the BARRIER.  */
1697               if (prev_label && --LABEL_NUSES (prev_label) == 0)
1698                 delete_insn (prev_label);
1699               continue;
1700             }
1701           else
1702             {
1703               /* Detect a jump to a jump.  */
1704
1705               nlabel = follow_jumps (JUMP_LABEL (insn));
1706               if (nlabel != JUMP_LABEL (insn)
1707                   && redirect_jump (insn, nlabel))
1708                 {
1709                   changed = 1;
1710                   next = insn;
1711                 }
1712
1713               /* Look for   if (foo) bar; else break;  */
1714               /* The insns look like this:
1715                  insn = condjump label1;
1716                  ...range1 (some insns)...
1717                  jump label2;
1718                  label1:
1719                  ...range2 (some insns)...
1720                  jump somewhere unconditionally
1721                  label2:  */
1722               {
1723                 rtx label1 = next_label (insn);
1724                 rtx range1end = label1 ? prev_active_insn (label1) : 0;
1725                 /* Don't do this optimization on the first round, so that
1726                    jump-around-a-jump gets simplified before we ask here
1727                    whether a jump is unconditional.
1728
1729                    Also don't do it when we are called after reload since
1730                    it will confuse reorg.  */
1731                 if (! first
1732                     && (reload_completed ? ! flag_delayed_branch : 1)
1733                     /* Make sure INSN is something we can invert.  */
1734                     && condjump_p (insn)
1735                     && label1 != 0
1736                     && JUMP_LABEL (insn) == label1
1737                     && LABEL_NUSES (label1) == 1
1738                     && GET_CODE (range1end) == JUMP_INSN
1739                     && simplejump_p (range1end))
1740                   {
1741                     rtx label2 = next_label (label1);
1742                     rtx range2end = label2 ? prev_active_insn (label2) : 0;
1743                     if (range1end != range2end
1744                         && JUMP_LABEL (range1end) == label2
1745                         && GET_CODE (range2end) == JUMP_INSN
1746                         && GET_CODE (NEXT_INSN (range2end)) == BARRIER
1747                         /* Invert the jump condition, so we
1748                            still execute the same insns in each case.  */
1749                         && invert_jump (insn, label1))
1750                       {
1751                         rtx range1beg = next_active_insn (insn);
1752                         rtx range2beg = next_active_insn (label1);
1753                         rtx range1after, range2after;
1754                         rtx range1before, range2before;
1755                         rtx rangenext;
1756
1757                         /* Include in each range any notes before it, to be
1758                            sure that we get the line number note if any, even
1759                            if there are other notes here.  */
1760                         while (PREV_INSN (range1beg)
1761                                && GET_CODE (PREV_INSN (range1beg)) == NOTE)
1762                           range1beg = PREV_INSN (range1beg);
1763
1764                         while (PREV_INSN (range2beg)
1765                                && GET_CODE (PREV_INSN (range2beg)) == NOTE)
1766                           range2beg = PREV_INSN (range2beg);
1767
1768                         /* Don't move NOTEs for blocks or loops; shift them
1769                            outside the ranges, where they'll stay put.  */
1770                         range1beg = squeeze_notes (range1beg, range1end);
1771                         range2beg = squeeze_notes (range2beg, range2end);
1772
1773                         /* Get current surrounds of the 2 ranges.  */
1774                         range1before = PREV_INSN (range1beg);
1775                         range2before = PREV_INSN (range2beg);
1776                         range1after = NEXT_INSN (range1end);
1777                         range2after = NEXT_INSN (range2end);
1778
1779                         /* Splice range2 where range1 was.  */
1780                         NEXT_INSN (range1before) = range2beg;
1781                         PREV_INSN (range2beg) = range1before;
1782                         NEXT_INSN (range2end) = range1after;
1783                         PREV_INSN (range1after) = range2end;
1784                         /* Splice range1 where range2 was.  */
1785                         NEXT_INSN (range2before) = range1beg;
1786                         PREV_INSN (range1beg) = range2before;
1787                         NEXT_INSN (range1end) = range2after;
1788                         PREV_INSN (range2after) = range1end;
1789
1790                         /* Check for a loop end note between the end of
1791                            range2, and the next code label.  If there is one,
1792                            then what we have really seen is
1793                            if (foo) break; end_of_loop;
1794                            and moved the break sequence outside the loop.
1795                            We must move the LOOP_END note to where the
1796                            loop really ends now, or we will confuse loop
1797                            optimization.  */
1798                         for (;range2after != label2; range2after = rangenext)
1799                           {
1800                             rangenext = NEXT_INSN (range2after);
1801                             if (GET_CODE (range2after) == NOTE
1802                                 && (NOTE_LINE_NUMBER (range2after)
1803                                     == NOTE_INSN_LOOP_END))
1804                               {
1805                                 NEXT_INSN (PREV_INSN (range2after))
1806                                   = rangenext;
1807                                 PREV_INSN (rangenext)
1808                                   = PREV_INSN (range2after);
1809                                 PREV_INSN (range2after)
1810                                   = PREV_INSN (range1beg);
1811                                 NEXT_INSN (range2after) = range1beg;
1812                                 NEXT_INSN (PREV_INSN (range1beg))
1813                                   = range2after;
1814                                 PREV_INSN (range1beg) = range2after;
1815                               }
1816                           }
1817                         changed = 1;
1818                         continue;
1819                       }
1820                   }
1821               }
1822
1823               /* Now that the jump has been tensioned,
1824                  try cross jumping: check for identical code
1825                  before the jump and before its target label. */
1826
1827               /* First, cross jumping of conditional jumps:  */
1828
1829               if (cross_jump && condjump_p (insn))
1830                 {
1831                   rtx newjpos, newlpos;
1832                   rtx x = prev_real_insn (JUMP_LABEL (insn));
1833
1834                   /* A conditional jump may be crossjumped
1835                      only if the place it jumps to follows
1836                      an opposing jump that comes back here.  */
1837
1838                   if (x != 0 && ! jump_back_p (x, insn))
1839                     /* We have no opposing jump;
1840                        cannot cross jump this insn.  */
1841                     x = 0;
1842
1843                   newjpos = 0;
1844                   /* TARGET is nonzero if it is ok to cross jump
1845                      to code before TARGET.  If so, see if matches.  */
1846                   if (x != 0)
1847                     find_cross_jump (insn, x, 2,
1848                                      &newjpos, &newlpos);
1849
1850                   if (newjpos != 0)
1851                     {
1852                       do_cross_jump (insn, newjpos, newlpos);
1853                       /* Make the old conditional jump
1854                          into an unconditional one.  */
1855                       SET_SRC (PATTERN (insn))
1856                         = gen_rtx (LABEL_REF, VOIDmode, JUMP_LABEL (insn));
1857                       INSN_CODE (insn) = -1;
1858                       emit_barrier_after (insn);
1859                       /* Add to jump_chain unless this is a new label
1860                          whose UID is too large. */
1861                       if (INSN_UID (JUMP_LABEL (insn)) < max_jump_chain)
1862                         {
1863                           jump_chain[INSN_UID (insn)]
1864                             = jump_chain[INSN_UID (JUMP_LABEL (insn))];
1865                           jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
1866                         }
1867                       changed = 1;
1868                       next = insn;
1869                     }
1870                 }
1871
1872               /* Cross jumping of unconditional jumps:
1873                  a few differences.  */
1874
1875               if (cross_jump && simplejump_p (insn))
1876                 {
1877                   rtx newjpos, newlpos;
1878                   rtx target;
1879
1880                   newjpos = 0;
1881
1882                   /* TARGET is nonzero if it is ok to cross jump
1883                      to code before TARGET.  If so, see if matches.  */
1884                   find_cross_jump (insn, JUMP_LABEL (insn), 1,
1885                                    &newjpos, &newlpos);
1886
1887                   /* If cannot cross jump to code before the label,
1888                      see if we can cross jump to another jump to
1889                      the same label.  */
1890                   /* Try each other jump to this label.  */
1891                   if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
1892                     for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
1893                          target != 0 && newjpos == 0;
1894                          target = jump_chain[INSN_UID (target)])
1895                       if (target != insn
1896                           && JUMP_LABEL (target) == JUMP_LABEL (insn)
1897                           /* Ignore TARGET if it's deleted.  */
1898                           && ! INSN_DELETED_P (target))
1899                         find_cross_jump (insn, target, 2,
1900                                          &newjpos, &newlpos);
1901
1902                   if (newjpos != 0)
1903                     {
1904                       do_cross_jump (insn, newjpos, newlpos);
1905                       changed = 1;
1906                       next = insn;
1907                     }
1908                 }
1909
1910               /* This code was dead in the previous jump.c!  */
1911               if (cross_jump && GET_CODE (PATTERN (insn)) == RETURN)
1912                 {
1913                   /* Return insns all "jump to the same place"
1914                      so we can cross-jump between any two of them.  */
1915
1916                   rtx newjpos, newlpos, target;
1917
1918                   newjpos = 0;
1919
1920                   /* If cannot cross jump to code before the label,
1921                      see if we can cross jump to another jump to
1922                      the same label.  */
1923                   /* Try each other jump to this label.  */
1924                   for (target = jump_chain[0];
1925                        target != 0 && newjpos == 0;
1926                        target = jump_chain[INSN_UID (target)])
1927                     if (target != insn
1928                         && ! INSN_DELETED_P (target)
1929                         && GET_CODE (PATTERN (target)) == RETURN)
1930                       find_cross_jump (insn, target, 2,
1931                                        &newjpos, &newlpos);
1932
1933                   if (newjpos != 0)
1934                     {
1935                       do_cross_jump (insn, newjpos, newlpos);
1936                       changed = 1;
1937                       next = insn;
1938                     }
1939                 }
1940             }
1941         }
1942
1943       first = 0;
1944     }
1945
1946   /* Delete extraneous line number notes.
1947      Note that two consecutive notes for different lines are not really
1948      extraneous.  There should be some indication where that line belonged,
1949      even if it became empty.  */
1950
1951   {
1952     rtx last_note = 0;
1953
1954     for (insn = f; insn; insn = NEXT_INSN (insn))
1955       if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0)
1956         {
1957           /* Delete this note if it is identical to previous note.  */
1958           if (last_note
1959               && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
1960               && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
1961             {
1962               delete_insn (insn);
1963               continue;
1964             }
1965
1966           last_note = insn;
1967         }
1968   }
1969
1970 #ifdef HAVE_return
1971   if (HAVE_return)
1972     {
1973       /* If we fall through to the epilogue, see if we can insert a RETURN insn
1974          in front of it.  If the machine allows it at this point (we might be
1975          after reload for a leaf routine), it will improve optimization for it
1976          to be there.  We do this both here and at the start of this pass since
1977          the RETURN might have been deleted by some of our optimizations.  */
1978       insn = get_last_insn ();
1979       while (insn && GET_CODE (insn) == NOTE)
1980         insn = PREV_INSN (insn);
1981
1982       if (insn && GET_CODE (insn) != BARRIER)
1983         {
1984           emit_jump_insn (gen_return ());
1985           emit_barrier ();
1986         }
1987     }
1988 #endif
1989
1990   /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
1991      If so, delete it, and record that this function can drop off the end.  */
1992
1993   insn = last_insn;
1994   {
1995     int n_labels = 1;
1996     while (insn
1997            /* One label can follow the end-note: the return label.  */
1998            && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
1999                /* Ordinary insns can follow it if returning a structure.  */
2000                || GET_CODE (insn) == INSN
2001                /* If machine uses explicit RETURN insns, no epilogue,
2002                   then one of them follows the note.  */
2003                || (GET_CODE (insn) == JUMP_INSN
2004                    && GET_CODE (PATTERN (insn)) == RETURN)
2005                /* Other kinds of notes can follow also.  */
2006                || (GET_CODE (insn) == NOTE
2007                    && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
2008       insn = PREV_INSN (insn);
2009   }
2010
2011   /* Report if control can fall through at the end of the function.  */
2012   if (insn && GET_CODE (insn) == NOTE
2013       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END)
2014     {
2015       can_reach_end = 1;
2016       delete_insn (insn);
2017     }
2018
2019   /* Show JUMP_CHAIN no longer valid.  */
2020   jump_chain = 0;
2021 }
2022 \f
2023 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
2024    jump.  Assume that this unconditional jump is to the exit test code.  If
2025    the code is sufficiently simple, make a copy of it before INSN,
2026    followed by a jump to the exit of the loop.  Then delete the unconditional
2027    jump after INSN.
2028
2029    Note that it is possible we can get confused here if the jump immediately
2030    after the loop start branches outside the loop but within an outer loop.
2031    If we are near the exit of that loop, we will copy its exit test.  This
2032    will not generate incorrect code, but could suppress some optimizations.
2033    However, such cases are degenerate loops anyway.
2034
2035    Return 1 if we made the change, else 0.
2036
2037    This is only safe immediately after a regscan pass because it uses the
2038    values of regno_first_uid and regno_last_uid.  */
2039
2040 static int
2041 duplicate_loop_exit_test (loop_start)
2042      rtx loop_start;
2043 {
2044   rtx insn, set, reg, p, link;
2045   rtx copy = 0;
2046   int num_insns = 0;
2047   rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
2048   rtx lastexit;
2049   int max_reg = max_reg_num ();
2050   rtx *reg_map = 0;
2051
2052   /* Scan the exit code.  We do not perform this optimization if any insn:
2053
2054          is a CALL_INSN
2055          is a CODE_LABEL
2056          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
2057          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
2058          is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
2059               are not valid
2060
2061      Also, don't do this if the exit code is more than 20 insns.  */
2062
2063   for (insn = exitcode;
2064        insn
2065        && ! (GET_CODE (insn) == NOTE
2066              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
2067        insn = NEXT_INSN (insn))
2068     {
2069       switch (GET_CODE (insn))
2070         {
2071         case CODE_LABEL:
2072         case CALL_INSN:
2073           return 0;
2074         case NOTE:
2075           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2076               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2077               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
2078             return 0;
2079           break;
2080         case JUMP_INSN:
2081         case INSN:
2082           if (++num_insns > 20
2083               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
2084               || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2085             return 0;
2086           break;
2087         }
2088     }
2089
2090   /* Unless INSN is zero, we can do the optimization.  */
2091   if (insn == 0)
2092     return 0;
2093
2094   lastexit = insn;
2095
2096   /* See if any insn sets a register only used in the loop exit code and
2097      not a user variable.  If so, replace it with a new register.  */
2098   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2099     if (GET_CODE (insn) == INSN
2100         && (set = single_set (insn)) != 0
2101         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
2102             || (GET_CODE (reg) == SUBREG
2103                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
2104         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
2105         && regno_first_uid[REGNO (reg)] == INSN_UID (insn))
2106       {
2107         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
2108           if (regno_last_uid[REGNO (reg)] == INSN_UID (p))
2109             break;
2110
2111         if (p != lastexit)
2112           {
2113             /* We can do the replacement.  Allocate reg_map if this is the
2114                first replacement we found.  */
2115             if (reg_map == 0)
2116               {
2117                 reg_map = (rtx *) alloca (max_reg * sizeof (rtx));
2118                 bzero ((char *) reg_map, max_reg * sizeof (rtx));
2119               }
2120
2121             REG_LOOP_TEST_P (reg) = 1;
2122
2123             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
2124           }
2125       }
2126
2127   /* Now copy each insn.  */
2128   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2129     switch (GET_CODE (insn))
2130       {
2131       case BARRIER:
2132         copy = emit_barrier_before (loop_start);
2133         break;
2134       case NOTE:
2135         /* Only copy line-number notes.  */
2136         if (NOTE_LINE_NUMBER (insn) >= 0)
2137           {
2138             copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
2139             NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
2140           }
2141         break;
2142
2143       case INSN:
2144         copy = emit_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2145         if (reg_map)
2146           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2147
2148         mark_jump_label (PATTERN (copy), copy, 0);
2149
2150         /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
2151            make them.  */
2152         for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2153           if (REG_NOTE_KIND (link) != REG_LABEL)
2154             REG_NOTES (copy)
2155               = copy_rtx (gen_rtx (EXPR_LIST, REG_NOTE_KIND (link),
2156                                    XEXP (link, 0), REG_NOTES (copy)));
2157         if (reg_map && REG_NOTES (copy))
2158           replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2159         break;
2160
2161       case JUMP_INSN:
2162         copy = emit_jump_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2163         if (reg_map)
2164           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2165         mark_jump_label (PATTERN (copy), copy, 0);
2166         if (REG_NOTES (insn))
2167           {
2168             REG_NOTES (copy) = copy_rtx (REG_NOTES (insn));
2169             if (reg_map)
2170               replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2171           }
2172
2173         /* If this is a simple jump, add it to the jump chain.  */
2174
2175         if (INSN_UID (copy) < max_jump_chain && JUMP_LABEL (copy)
2176             && simplejump_p (copy))
2177           {
2178             jump_chain[INSN_UID (copy)]
2179               = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2180             jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2181           }
2182         break;
2183
2184       default:
2185         abort ();
2186       }
2187
2188   /* Now clean up by emitting a jump to the end label and deleting the jump
2189      at the start of the loop.  */
2190   if (! copy || GET_CODE (copy) != BARRIER)
2191     {
2192       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
2193                                     loop_start);
2194       mark_jump_label (PATTERN (copy), copy, 0);
2195       if (INSN_UID (copy) < max_jump_chain
2196           && INSN_UID (JUMP_LABEL (copy)) < max_jump_chain)
2197         {
2198           jump_chain[INSN_UID (copy)]
2199             = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2200           jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2201         }
2202       emit_barrier_before (loop_start);
2203     }
2204
2205   delete_insn (next_nonnote_insn (loop_start));
2206
2207   /* Mark the exit code as the virtual top of the converted loop.  */
2208   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
2209
2210   return 1;
2211 }
2212 \f
2213 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, and
2214    loop-end notes between START and END out before START.  Assume that
2215    END is not such a note.  START may be such a note.  Returns the value
2216    of the new starting insn, which may be different if the original start
2217    was such a note.  */
2218
2219 rtx
2220 squeeze_notes (start, end)
2221      rtx start, end;
2222 {
2223   rtx insn;
2224   rtx next;
2225
2226   for (insn = start; insn != end; insn = next)
2227     {
2228       next = NEXT_INSN (insn);
2229       if (GET_CODE (insn) == NOTE
2230           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
2231               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2232               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2233               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
2234               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
2235               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
2236         {
2237           if (insn == start)
2238             start = next;
2239           else
2240             {
2241               rtx prev = PREV_INSN (insn);
2242               PREV_INSN (insn) = PREV_INSN (start);
2243               NEXT_INSN (insn) = start;
2244               NEXT_INSN (PREV_INSN (insn)) = insn;
2245               PREV_INSN (NEXT_INSN (insn)) = insn;
2246               NEXT_INSN (prev) = next;
2247               PREV_INSN (next) = prev;
2248             }
2249         }
2250     }
2251
2252   return start;
2253 }
2254 \f
2255 /* Compare the instructions before insn E1 with those before E2
2256    to find an opportunity for cross jumping.
2257    (This means detecting identical sequences of insns followed by
2258    jumps to the same place, or followed by a label and a jump
2259    to that label, and replacing one with a jump to the other.)
2260
2261    Assume E1 is a jump that jumps to label E2
2262    (that is not always true but it might as well be).
2263    Find the longest possible equivalent sequences
2264    and store the first insns of those sequences into *F1 and *F2.
2265    Store zero there if no equivalent preceding instructions are found.
2266
2267    We give up if we find a label in stream 1.
2268    Actually we could transfer that label into stream 2.  */
2269
2270 static void
2271 find_cross_jump (e1, e2, minimum, f1, f2)
2272      rtx e1, e2;
2273      int minimum;
2274      rtx *f1, *f2;
2275 {
2276   register rtx i1 = e1, i2 = e2;
2277   register rtx p1, p2;
2278   int lose = 0;
2279
2280   rtx last1 = 0, last2 = 0;
2281   rtx afterlast1 = 0, afterlast2 = 0;
2282   rtx prev1;
2283
2284   *f1 = 0;
2285   *f2 = 0;
2286
2287   while (1)
2288     {
2289       i1 = prev_nonnote_insn (i1);
2290
2291       i2 = PREV_INSN (i2);
2292       while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
2293         i2 = PREV_INSN (i2);
2294
2295       if (i1 == 0)
2296         break;
2297
2298       /* Don't allow the range of insns preceding E1 or E2
2299          to include the other (E2 or E1).  */
2300       if (i2 == e1 || i1 == e2)
2301         break;
2302
2303       /* If we will get to this code by jumping, those jumps will be
2304          tensioned to go directly to the new label (before I2),
2305          so this cross-jumping won't cost extra.  So reduce the minimum.  */
2306       if (GET_CODE (i1) == CODE_LABEL)
2307         {
2308           --minimum;
2309           break;
2310         }
2311
2312       if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
2313         break;
2314
2315       p1 = PATTERN (i1);
2316       p2 = PATTERN (i2);
2317
2318       /* If this is a CALL_INSN, compare register usage information.
2319          If we don't check this on stack register machines, the two
2320          CALL_INSNs might be merged leaving reg-stack.c with mismatching
2321          numbers of stack registers in the same basic block.
2322          If we don't check this on machines with delay slots, a delay slot may
2323          be filled that clobbers a parameter expected by the subroutine.
2324
2325          ??? We take the simple route for now and assume that if they're
2326          equal, they were constructed identically.  */
2327
2328       if (GET_CODE (i1) == CALL_INSN
2329           && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
2330                             CALL_INSN_FUNCTION_USAGE (i2)))
2331         lose = 1;
2332
2333 #ifdef STACK_REGS
2334       /* If cross_jump_death_matters is not 0, the insn's mode
2335          indicates whether or not the insn contains any stack-like
2336          regs. */
2337
2338       if (!lose && cross_jump_death_matters && GET_MODE (i1) == QImode)
2339         {
2340           /* If register stack conversion has already been done, then
2341              death notes must also be compared before it is certain that
2342              the two instruction streams match. */
2343
2344           rtx note;
2345           HARD_REG_SET i1_regset, i2_regset;
2346
2347           CLEAR_HARD_REG_SET (i1_regset);
2348           CLEAR_HARD_REG_SET (i2_regset);
2349
2350           for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
2351             if (REG_NOTE_KIND (note) == REG_DEAD
2352                 && STACK_REG_P (XEXP (note, 0)))
2353               SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
2354
2355           for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
2356             if (REG_NOTE_KIND (note) == REG_DEAD
2357                 && STACK_REG_P (XEXP (note, 0)))
2358               SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
2359
2360           GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
2361
2362           lose = 1;
2363
2364         done:
2365           ;
2366         }
2367 #endif
2368
2369       if (lose  || GET_CODE (p1) != GET_CODE (p2)
2370           || ! rtx_renumbered_equal_p (p1, p2))
2371         {
2372           /* The following code helps take care of G++ cleanups.  */
2373           rtx equiv1;
2374           rtx equiv2;
2375
2376           if (!lose && GET_CODE (p1) == GET_CODE (p2)
2377               && ((equiv1 = find_reg_note (i1, REG_EQUAL, NULL_RTX)) != 0
2378                   || (equiv1 = find_reg_note (i1, REG_EQUIV, NULL_RTX)) != 0)
2379               && ((equiv2 = find_reg_note (i2, REG_EQUAL, NULL_RTX)) != 0
2380                   || (equiv2 = find_reg_note (i2, REG_EQUIV, NULL_RTX)) != 0)
2381               /* If the equivalences are not to a constant, they may
2382                  reference pseudos that no longer exist, so we can't
2383                  use them.  */
2384               && CONSTANT_P (XEXP (equiv1, 0))
2385               && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
2386             {
2387               rtx s1 = single_set (i1);
2388               rtx s2 = single_set (i2);
2389               if (s1 != 0 && s2 != 0
2390                   && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
2391                 {
2392                   validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
2393                   validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
2394                   if (! rtx_renumbered_equal_p (p1, p2))
2395                     cancel_changes (0);
2396                   else if (apply_change_group ())
2397                     goto win;
2398                 }
2399             }
2400
2401           /* Insns fail to match; cross jumping is limited to the following
2402              insns.  */
2403
2404 #ifdef HAVE_cc0
2405           /* Don't allow the insn after a compare to be shared by
2406              cross-jumping unless the compare is also shared.
2407              Here, if either of these non-matching insns is a compare,
2408              exclude the following insn from possible cross-jumping.  */
2409           if (sets_cc0_p (p1) || sets_cc0_p (p2))
2410             last1 = afterlast1, last2 = afterlast2, ++minimum;
2411 #endif
2412
2413           /* If cross-jumping here will feed a jump-around-jump
2414              optimization, this jump won't cost extra, so reduce
2415              the minimum.  */
2416           if (GET_CODE (i1) == JUMP_INSN
2417               && JUMP_LABEL (i1)
2418               && prev_real_insn (JUMP_LABEL (i1)) == e1)
2419             --minimum;
2420           break;
2421         }
2422
2423     win:
2424       if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
2425         {
2426           /* Ok, this insn is potentially includable in a cross-jump here.  */
2427           afterlast1 = last1, afterlast2 = last2;
2428           last1 = i1, last2 = i2, --minimum;
2429         }
2430     }
2431
2432   if (minimum <= 0 && last1 != 0 && last1 != e1)
2433     *f1 = last1, *f2 = last2;
2434 }
2435
2436 static void
2437 do_cross_jump (insn, newjpos, newlpos)
2438      rtx insn, newjpos, newlpos;
2439 {
2440   /* Find an existing label at this point
2441      or make a new one if there is none.  */
2442   register rtx label = get_label_before (newlpos);
2443
2444   /* Make the same jump insn jump to the new point.  */
2445   if (GET_CODE (PATTERN (insn)) == RETURN)
2446     {
2447       /* Remove from jump chain of returns.  */
2448       delete_from_jump_chain (insn);
2449       /* Change the insn.  */
2450       PATTERN (insn) = gen_jump (label);
2451       INSN_CODE (insn) = -1;
2452       JUMP_LABEL (insn) = label;
2453       LABEL_NUSES (label)++;
2454       /* Add to new the jump chain.  */
2455       if (INSN_UID (label) < max_jump_chain
2456           && INSN_UID (insn) < max_jump_chain)
2457         {
2458           jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (label)];
2459           jump_chain[INSN_UID (label)] = insn;
2460         }
2461     }
2462   else
2463     redirect_jump (insn, label);
2464
2465   /* Delete the matching insns before the jump.  Also, remove any REG_EQUAL
2466      or REG_EQUIV note in the NEWLPOS stream that isn't also present in
2467      the NEWJPOS stream.  */
2468
2469   while (newjpos != insn)
2470     {
2471       rtx lnote;
2472
2473       for (lnote = REG_NOTES (newlpos); lnote; lnote = XEXP (lnote, 1))
2474         if ((REG_NOTE_KIND (lnote) == REG_EQUAL
2475              || REG_NOTE_KIND (lnote) == REG_EQUIV)
2476             && ! find_reg_note (newjpos, REG_EQUAL, XEXP (lnote, 0))
2477             && ! find_reg_note (newjpos, REG_EQUIV, XEXP (lnote, 0)))
2478           remove_note (newlpos, lnote);
2479
2480       delete_insn (newjpos);
2481       newjpos = next_real_insn (newjpos);
2482       newlpos = next_real_insn (newlpos);
2483     }
2484 }
2485 \f
2486 /* Return the label before INSN, or put a new label there.  */
2487
2488 rtx
2489 get_label_before (insn)
2490      rtx insn;
2491 {
2492   rtx label;
2493
2494   /* Find an existing label at this point
2495      or make a new one if there is none.  */
2496   label = prev_nonnote_insn (insn);
2497
2498   if (label == 0 || GET_CODE (label) != CODE_LABEL)
2499     {
2500       rtx prev = PREV_INSN (insn);
2501
2502       label = gen_label_rtx ();
2503       emit_label_after (label, prev);
2504       LABEL_NUSES (label) = 0;
2505     }
2506   return label;
2507 }
2508
2509 /* Return the label after INSN, or put a new label there.  */
2510
2511 rtx
2512 get_label_after (insn)
2513      rtx insn;
2514 {
2515   rtx label;
2516
2517   /* Find an existing label at this point
2518      or make a new one if there is none.  */
2519   label = next_nonnote_insn (insn);
2520
2521   if (label == 0 || GET_CODE (label) != CODE_LABEL)
2522     {
2523       label = gen_label_rtx ();
2524       emit_label_after (label, insn);
2525       LABEL_NUSES (label) = 0;
2526     }
2527   return label;
2528 }
2529 \f
2530 /* Return 1 if INSN is a jump that jumps to right after TARGET
2531    only on the condition that TARGET itself would drop through.
2532    Assumes that TARGET is a conditional jump.  */
2533
2534 static int
2535 jump_back_p (insn, target)
2536      rtx insn, target;
2537 {
2538   rtx cinsn, ctarget;
2539   enum rtx_code codei, codet;
2540
2541   if (simplejump_p (insn) || ! condjump_p (insn)
2542       || simplejump_p (target)
2543       || target != prev_real_insn (JUMP_LABEL (insn)))
2544     return 0;
2545
2546   cinsn = XEXP (SET_SRC (PATTERN (insn)), 0);
2547   ctarget = XEXP (SET_SRC (PATTERN (target)), 0);
2548
2549   codei = GET_CODE (cinsn);
2550   codet = GET_CODE (ctarget);
2551
2552   if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx)
2553     {
2554       if (! can_reverse_comparison_p (cinsn, insn))
2555         return 0;
2556       codei = reverse_condition (codei);
2557     }
2558
2559   if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx)
2560     {
2561       if (! can_reverse_comparison_p (ctarget, target))
2562         return 0;
2563       codet = reverse_condition (codet);
2564     }
2565
2566   return (codei == codet
2567           && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
2568           && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
2569 }
2570 \f
2571 /* Given a comparison, COMPARISON, inside a conditional jump insn, INSN,
2572    return non-zero if it is safe to reverse this comparison.  It is if our
2573    floating-point is not IEEE, if this is an NE or EQ comparison, or if
2574    this is known to be an integer comparison.  */
2575
2576 int
2577 can_reverse_comparison_p (comparison, insn)
2578      rtx comparison;
2579      rtx insn;
2580 {
2581   rtx arg0;
2582
2583   /* If this is not actually a comparison, we can't reverse it.  */
2584   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
2585     return 0;
2586
2587   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
2588       /* If this is an NE comparison, it is safe to reverse it to an EQ
2589          comparison and vice versa, even for floating point.  If no operands
2590          are NaNs, the reversal is valid.  If some operand is a NaN, EQ is
2591          always false and NE is always true, so the reversal is also valid.  */
2592       || flag_fast_math
2593       || GET_CODE (comparison) == NE
2594       || GET_CODE (comparison) == EQ)
2595     return 1;
2596
2597   arg0 = XEXP (comparison, 0);
2598
2599   /* Make sure ARG0 is one of the actual objects being compared.  If we
2600      can't do this, we can't be sure the comparison can be reversed.
2601
2602      Handle cc0 and a MODE_CC register.  */
2603   if ((GET_CODE (arg0) == REG && GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC)
2604 #ifdef HAVE_cc0
2605       || arg0 == cc0_rtx
2606 #endif
2607       )
2608     {
2609       rtx prev = prev_nonnote_insn (insn);
2610       rtx set = single_set (prev);
2611
2612       if (set == 0 || SET_DEST (set) != arg0)
2613         return 0;
2614
2615       arg0 = SET_SRC (set);
2616
2617       if (GET_CODE (arg0) == COMPARE)
2618         arg0 = XEXP (arg0, 0);
2619     }
2620
2621   /* We can reverse this if ARG0 is a CONST_INT or if its mode is
2622      not VOIDmode and neither a MODE_CC nor MODE_FLOAT type.  */
2623   return (GET_CODE (arg0) == CONST_INT
2624           || (GET_MODE (arg0) != VOIDmode
2625               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_CC
2626               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_FLOAT));
2627 }
2628
2629 /* Given an rtx-code for a comparison, return the code
2630    for the negated comparison.
2631    WATCH OUT!  reverse_condition is not safe to use on a jump
2632    that might be acting on the results of an IEEE floating point comparison,
2633    because of the special treatment of non-signaling nans in comparisons.
2634    Use can_reverse_comparison_p to be sure.  */
2635
2636 enum rtx_code
2637 reverse_condition (code)
2638      enum rtx_code code;
2639 {
2640   switch (code)
2641     {
2642     case EQ:
2643       return NE;
2644
2645     case NE:
2646       return EQ;
2647
2648     case GT:
2649       return LE;
2650
2651     case GE:
2652       return LT;
2653
2654     case LT:
2655       return GE;
2656
2657     case LE:
2658       return GT;
2659
2660     case GTU:
2661       return LEU;
2662
2663     case GEU:
2664       return LTU;
2665
2666     case LTU:
2667       return GEU;
2668
2669     case LEU:
2670       return GTU;
2671
2672     default:
2673       abort ();
2674       return UNKNOWN;
2675     }
2676 }
2677
2678 /* Similar, but return the code when two operands of a comparison are swapped.
2679    This IS safe for IEEE floating-point.  */
2680
2681 enum rtx_code
2682 swap_condition (code)
2683      enum rtx_code code;
2684 {
2685   switch (code)
2686     {
2687     case EQ:
2688     case NE:
2689       return code;
2690
2691     case GT:
2692       return LT;
2693
2694     case GE:
2695       return LE;
2696
2697     case LT:
2698       return GT;
2699
2700     case LE:
2701       return GE;
2702
2703     case GTU:
2704       return LTU;
2705
2706     case GEU:
2707       return LEU;
2708
2709     case LTU:
2710       return GTU;
2711
2712     case LEU:
2713       return GEU;
2714
2715     default:
2716       abort ();
2717       return UNKNOWN;
2718     }
2719 }
2720
2721 /* Given a comparison CODE, return the corresponding unsigned comparison.
2722    If CODE is an equality comparison or already an unsigned comparison,
2723    CODE is returned.  */
2724
2725 enum rtx_code
2726 unsigned_condition (code)
2727      enum rtx_code code;
2728 {
2729   switch (code)
2730     {
2731     case EQ:
2732     case NE:
2733     case GTU:
2734     case GEU:
2735     case LTU:
2736     case LEU:
2737       return code;
2738
2739     case GT:
2740       return GTU;
2741
2742     case GE:
2743       return GEU;
2744
2745     case LT:
2746       return LTU;
2747
2748     case LE:
2749       return LEU;
2750
2751     default:
2752       abort ();
2753     }
2754 }
2755
2756 /* Similarly, return the signed version of a comparison.  */
2757
2758 enum rtx_code
2759 signed_condition (code)
2760      enum rtx_code code;
2761 {
2762   switch (code)
2763     {
2764     case EQ:
2765     case NE:
2766     case GT:
2767     case GE:
2768     case LT:
2769     case LE:
2770       return code;
2771
2772     case GTU:
2773       return GT;
2774
2775     case GEU:
2776       return GE;
2777
2778     case LTU:
2779       return LT;
2780
2781     case LEU:
2782       return LE;
2783
2784     default:
2785       abort ();
2786     }
2787 }
2788 \f
2789 /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
2790    truth of CODE1 implies the truth of CODE2.  */
2791
2792 int
2793 comparison_dominates_p (code1, code2)
2794      enum rtx_code code1, code2;
2795 {
2796   if (code1 == code2)
2797     return 1;
2798
2799   switch (code1)
2800     {
2801     case EQ:
2802       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU)
2803         return 1;
2804       break;
2805
2806     case LT:
2807       if (code2 == LE || code2 == NE)
2808         return 1;
2809       break;
2810
2811     case GT:
2812       if (code2 == GE || code2 == NE)
2813         return 1;
2814       break;
2815
2816     case LTU:
2817       if (code2 == LEU || code2 == NE)
2818         return 1;
2819       break;
2820
2821     case GTU:
2822       if (code2 == GEU || code2 == NE)
2823         return 1;
2824       break;
2825     }
2826
2827   return 0;
2828 }
2829 \f
2830 /* Return 1 if INSN is an unconditional jump and nothing else.  */
2831
2832 int
2833 simplejump_p (insn)
2834      rtx insn;
2835 {
2836   return (GET_CODE (insn) == JUMP_INSN
2837           && GET_CODE (PATTERN (insn)) == SET
2838           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
2839           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
2840 }
2841
2842 /* Return nonzero if INSN is a (possibly) conditional jump
2843    and nothing more.  */
2844
2845 int
2846 condjump_p (insn)
2847      rtx insn;
2848 {
2849   register rtx x = PATTERN (insn);
2850   if (GET_CODE (x) != SET)
2851     return 0;
2852   if (GET_CODE (SET_DEST (x)) != PC)
2853     return 0;
2854   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
2855     return 1;
2856   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
2857     return 0;
2858   if (XEXP (SET_SRC (x), 2) == pc_rtx
2859       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
2860           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
2861     return 1;
2862   if (XEXP (SET_SRC (x), 1) == pc_rtx
2863       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
2864           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
2865     return 1;
2866   return 0;
2867 }
2868
2869 /* Return nonzero if INSN is a (possibly) conditional jump
2870    and nothing more.  */
2871
2872 int
2873 condjump_in_parallel_p (insn)
2874      rtx insn;
2875 {
2876   register rtx x = PATTERN (insn);
2877
2878   if (GET_CODE (x) != PARALLEL)
2879     return 0;
2880   else
2881     x = XVECEXP (x, 0, 0);
2882
2883   if (GET_CODE (x) != SET)
2884     return 0;
2885   if (GET_CODE (SET_DEST (x)) != PC)
2886     return 0;
2887   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
2888     return 1;
2889   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
2890     return 0;
2891   if (XEXP (SET_SRC (x), 2) == pc_rtx
2892       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
2893           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
2894     return 1;
2895   if (XEXP (SET_SRC (x), 1) == pc_rtx
2896       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
2897           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
2898     return 1;
2899   return 0;
2900 }
2901
2902 /* Return 1 if X is an RTX that does nothing but set the condition codes
2903    and CLOBBER or USE registers.
2904    Return -1 if X does explicitly set the condition codes,
2905    but also does other things.  */
2906
2907 int
2908 sets_cc0_p (x)
2909      rtx x;
2910 {
2911 #ifdef HAVE_cc0
2912   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
2913     return 1;
2914   if (GET_CODE (x) == PARALLEL)
2915     {
2916       int i;
2917       int sets_cc0 = 0;
2918       int other_things = 0;
2919       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2920         {
2921           if (GET_CODE (XVECEXP (x, 0, i)) == SET
2922               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
2923             sets_cc0 = 1;
2924           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
2925             other_things = 1;
2926         }
2927       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
2928     }
2929   return 0;
2930 #else
2931   abort ();
2932 #endif
2933 }
2934 \f
2935 /* Follow any unconditional jump at LABEL;
2936    return the ultimate label reached by any such chain of jumps.
2937    If LABEL is not followed by a jump, return LABEL.
2938    If the chain loops or we can't find end, return LABEL,
2939    since that tells caller to avoid changing the insn.
2940
2941    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
2942    a USE or CLOBBER.  */
2943
2944 rtx
2945 follow_jumps (label)
2946      rtx label;
2947 {
2948   register rtx insn;
2949   register rtx next;
2950   register rtx value = label;
2951   register int depth;
2952
2953   for (depth = 0;
2954        (depth < 10
2955         && (insn = next_active_insn (value)) != 0
2956         && GET_CODE (insn) == JUMP_INSN
2957         && (JUMP_LABEL (insn) != 0 || GET_CODE (PATTERN (insn)) == RETURN)
2958         && (next = NEXT_INSN (insn))
2959         && GET_CODE (next) == BARRIER);
2960        depth++)
2961     {
2962       /* Don't chain through the insn that jumps into a loop
2963          from outside the loop,
2964          since that would create multiple loop entry jumps
2965          and prevent loop optimization.  */
2966       rtx tem;
2967       if (!reload_completed)
2968         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
2969           if (GET_CODE (tem) == NOTE
2970               && NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG)
2971             return value;
2972
2973       /* If we have found a cycle, make the insn jump to itself.  */
2974       if (JUMP_LABEL (insn) == label)
2975         return label;
2976
2977       tem = next_active_insn (JUMP_LABEL (insn));
2978       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
2979                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
2980         break;
2981
2982       value = JUMP_LABEL (insn);
2983     }
2984   if (depth == 10)
2985     return label;
2986   return value;
2987 }
2988
2989 /* Assuming that field IDX of X is a vector of label_refs,
2990    replace each of them by the ultimate label reached by it.
2991    Return nonzero if a change is made.
2992    If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG.  */
2993
2994 static int
2995 tension_vector_labels (x, idx)
2996      register rtx x;
2997      register int idx;
2998 {
2999   int changed = 0;
3000   register int i;
3001   for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
3002     {
3003       register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
3004       register rtx nlabel = follow_jumps (olabel);
3005       if (nlabel && nlabel != olabel)
3006         {
3007           XEXP (XVECEXP (x, idx, i), 0) = nlabel;
3008           ++LABEL_NUSES (nlabel);
3009           if (--LABEL_NUSES (olabel) == 0)
3010             delete_insn (olabel);
3011           changed = 1;
3012         }
3013     }
3014   return changed;
3015 }
3016 \f
3017 /* Find all CODE_LABELs referred to in X, and increment their use counts.
3018    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
3019    in INSN, then store one of them in JUMP_LABEL (INSN).
3020    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
3021    referenced in INSN, add a REG_LABEL note containing that label to INSN.
3022    Also, when there are consecutive labels, canonicalize on the last of them.
3023
3024    Note that two labels separated by a loop-beginning note
3025    must be kept distinct if we have not yet done loop-optimization,
3026    because the gap between them is where loop-optimize
3027    will want to move invariant code to.  CROSS_JUMP tells us
3028    that loop-optimization is done with.
3029
3030    Once reload has completed (CROSS_JUMP non-zero), we need not consider
3031    two labels distinct if they are separated by only USE or CLOBBER insns.  */
3032
3033 static void
3034 mark_jump_label (x, insn, cross_jump)
3035      register rtx x;
3036      rtx insn;
3037      int cross_jump;
3038 {
3039   register RTX_CODE code = GET_CODE (x);
3040   register int i;
3041   register char *fmt;
3042
3043   switch (code)
3044     {
3045     case PC:
3046     case CC0:
3047     case REG:
3048     case SUBREG:
3049     case CONST_INT:
3050     case SYMBOL_REF:
3051     case CONST_DOUBLE:
3052     case CLOBBER:
3053     case CALL:
3054       return;
3055
3056     case MEM:
3057       /* If this is a constant-pool reference, see if it is a label.  */
3058       if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
3059           && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
3060         mark_jump_label (get_pool_constant (XEXP (x, 0)), insn, cross_jump);
3061       break;
3062
3063     case LABEL_REF:
3064       {
3065         rtx label = XEXP (x, 0);
3066         rtx olabel = label;
3067         rtx note;
3068         rtx next;
3069
3070         if (GET_CODE (label) != CODE_LABEL)
3071           abort ();
3072
3073         /* Ignore references to labels of containing functions.  */
3074         if (LABEL_REF_NONLOCAL_P (x))
3075           break;
3076
3077         /* If there are other labels following this one,
3078            replace it with the last of the consecutive labels.  */
3079         for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
3080           {
3081             if (GET_CODE (next) == CODE_LABEL)
3082               label = next;
3083             else if (cross_jump && GET_CODE (next) == INSN
3084                      && (GET_CODE (PATTERN (next)) == USE
3085                          || GET_CODE (PATTERN (next)) == CLOBBER))
3086               continue;
3087             else if (GET_CODE (next) != NOTE)
3088               break;
3089             else if (! cross_jump
3090                      && (NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
3091                          || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END))
3092               break;
3093           }
3094
3095         XEXP (x, 0) = label;
3096         ++LABEL_NUSES (label);
3097
3098         if (insn)
3099           {
3100             if (GET_CODE (insn) == JUMP_INSN)
3101               JUMP_LABEL (insn) = label;
3102
3103             /* If we've changed OLABEL and we had a REG_LABEL note
3104                for it, update it as well.  */
3105             else if (label != olabel
3106                      && (note = find_reg_note (insn, REG_LABEL, olabel)) != 0)
3107               XEXP (note, 0) = label;
3108
3109             /* Otherwise, add a REG_LABEL note for LABEL unless there already
3110                is one.  */
3111             else if (! find_reg_note (insn, REG_LABEL, label))
3112               {
3113                 rtx next = next_real_insn (label);
3114                 /* Don't record labels that refer to dispatch tables.
3115                    This is not necessary, since the tablejump
3116                    references the same label.
3117                    And if we did record them, flow.c would make worse code.  */
3118                 if (next == 0
3119                     || ! (GET_CODE (next) == JUMP_INSN
3120                           && (GET_CODE (PATTERN (next)) == ADDR_VEC
3121                               || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)))
3122                   REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, label,
3123                                               REG_NOTES (insn));
3124               }
3125           }
3126         return;
3127       }
3128
3129   /* Do walk the labels in a vector, but not the first operand of an
3130      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
3131     case ADDR_VEC:
3132     case ADDR_DIFF_VEC:
3133       {
3134         int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
3135
3136         for (i = 0; i < XVECLEN (x, eltnum); i++)
3137           mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, cross_jump);
3138         return;
3139       }
3140     }
3141
3142   fmt = GET_RTX_FORMAT (code);
3143   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3144     {
3145       if (fmt[i] == 'e')
3146         mark_jump_label (XEXP (x, i), insn, cross_jump);
3147       else if (fmt[i] == 'E')
3148         {
3149           register int j;
3150           for (j = 0; j < XVECLEN (x, i); j++)
3151             mark_jump_label (XVECEXP (x, i, j), insn, cross_jump);
3152         }
3153     }
3154 }
3155
3156 /* If all INSN does is set the pc, delete it,
3157    and delete the insn that set the condition codes for it
3158    if that's what the previous thing was.  */
3159
3160 void
3161 delete_jump (insn)
3162      rtx insn;
3163 {
3164   register rtx set = single_set (insn);
3165
3166   if (set && GET_CODE (SET_DEST (set)) == PC)
3167     delete_computation (insn);
3168 }
3169
3170 /* Delete INSN and recursively delete insns that compute values used only
3171    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
3172    If we are running before flow.c, we need do nothing since flow.c will
3173    delete dead code.  We also can't know if the registers being used are
3174    dead or not at this point.
3175
3176    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
3177    nothing other than set a register that dies in this insn, we can delete
3178    that insn as well.
3179
3180    On machines with CC0, if CC0 is used in this insn, we may be able to
3181    delete the insn that set it.  */
3182
3183 static void
3184 delete_computation (insn)
3185      rtx insn;
3186 {
3187   rtx note, next;
3188
3189 #ifdef HAVE_cc0
3190   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
3191     {
3192       rtx prev = prev_nonnote_insn (insn);
3193       /* We assume that at this stage
3194          CC's are always set explicitly
3195          and always immediately before the jump that
3196          will use them.  So if the previous insn
3197          exists to set the CC's, delete it
3198          (unless it performs auto-increments, etc.).  */
3199       if (prev && GET_CODE (prev) == INSN
3200           && sets_cc0_p (PATTERN (prev)))
3201         {
3202           if (sets_cc0_p (PATTERN (prev)) > 0
3203               && !FIND_REG_INC_NOTE (prev, NULL_RTX))
3204             delete_computation (prev);
3205           else
3206             /* Otherwise, show that cc0 won't be used.  */
3207             REG_NOTES (prev) = gen_rtx (EXPR_LIST, REG_UNUSED,
3208                                         cc0_rtx, REG_NOTES (prev));
3209         }
3210     }
3211 #endif
3212
3213   for (note = REG_NOTES (insn); note; note = next)
3214     {
3215       rtx our_prev;
3216
3217       next = XEXP (note, 1);
3218
3219       if (REG_NOTE_KIND (note) != REG_DEAD
3220           /* Verify that the REG_NOTE is legitimate.  */
3221           || GET_CODE (XEXP (note, 0)) != REG)
3222         continue;
3223
3224       for (our_prev = prev_nonnote_insn (insn);
3225            our_prev && GET_CODE (our_prev) == INSN;
3226            our_prev = prev_nonnote_insn (our_prev))
3227         {
3228           /* If we reach a SEQUENCE, it is too complex to try to
3229              do anything with it, so give up.  */
3230           if (GET_CODE (PATTERN (our_prev)) == SEQUENCE)
3231             break;
3232
3233           if (GET_CODE (PATTERN (our_prev)) == USE
3234               && GET_CODE (XEXP (PATTERN (our_prev), 0)) == INSN)
3235             /* reorg creates USEs that look like this.  We leave them
3236                alone because reorg needs them for its own purposes.  */
3237             break;
3238
3239           if (reg_set_p (XEXP (note, 0), PATTERN (our_prev)))
3240             {
3241               if (FIND_REG_INC_NOTE (our_prev, NULL_RTX))
3242                 break;
3243
3244               if (GET_CODE (PATTERN (our_prev)) == PARALLEL)
3245                 {
3246                   /* If we find a SET of something else, we can't
3247                      delete the insn.  */
3248
3249                   int i;
3250
3251                   for (i = 0; i < XVECLEN (PATTERN (our_prev), 0); i++)
3252                     {
3253                       rtx part = XVECEXP (PATTERN (our_prev), 0, i);
3254
3255                       if (GET_CODE (part) == SET
3256                           && SET_DEST (part) != XEXP (note, 0))
3257                         break;
3258                     }
3259
3260                   if (i == XVECLEN (PATTERN (our_prev), 0))
3261                     delete_computation (our_prev);
3262                 }
3263               else if (GET_CODE (PATTERN (our_prev)) == SET
3264                        && SET_DEST (PATTERN (our_prev)) == XEXP (note, 0))
3265                 delete_computation (our_prev);
3266
3267               break;
3268             }
3269
3270           /* If OUR_PREV references the register that dies here, it is an
3271              additional use.  Hence any prior SET isn't dead.  However, this
3272              insn becomes the new place for the REG_DEAD note.  */
3273           if (reg_overlap_mentioned_p (XEXP (note, 0),
3274                                        PATTERN (our_prev)))
3275             {
3276               XEXP (note, 1) = REG_NOTES (our_prev);
3277               REG_NOTES (our_prev) = note;
3278               break;
3279             }
3280         }
3281     }
3282
3283   delete_insn (insn);
3284 }
3285 \f
3286 /* Delete insn INSN from the chain of insns and update label ref counts.
3287    May delete some following insns as a consequence; may even delete
3288    a label elsewhere and insns that follow it.
3289
3290    Returns the first insn after INSN that was not deleted.  */
3291
3292 rtx
3293 delete_insn (insn)
3294      register rtx insn;
3295 {
3296   register rtx next = NEXT_INSN (insn);
3297   register rtx prev = PREV_INSN (insn);
3298   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
3299   register int dont_really_delete = 0;
3300
3301   while (next && INSN_DELETED_P (next))
3302     next = NEXT_INSN (next);
3303
3304   /* This insn is already deleted => return first following nondeleted.  */
3305   if (INSN_DELETED_P (insn))
3306     return next;
3307
3308   /* Don't delete user-declared labels.  Convert them to special NOTEs
3309      instead.  */
3310   if (was_code_label && LABEL_NAME (insn) != 0
3311       && optimize && ! dont_really_delete)
3312     {
3313       PUT_CODE (insn, NOTE);
3314       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
3315       NOTE_SOURCE_FILE (insn) = 0;
3316       dont_really_delete = 1;
3317     }
3318   else
3319     /* Mark this insn as deleted.  */
3320     INSN_DELETED_P (insn) = 1;
3321
3322   /* If this is an unconditional jump, delete it from the jump chain.  */
3323   if (simplejump_p (insn))
3324     delete_from_jump_chain (insn);
3325
3326   /* If instruction is followed by a barrier,
3327      delete the barrier too.  */
3328
3329   if (next != 0 && GET_CODE (next) == BARRIER)
3330     {
3331       INSN_DELETED_P (next) = 1;
3332       next = NEXT_INSN (next);
3333     }
3334
3335   /* Patch out INSN (and the barrier if any) */
3336
3337   if (optimize && ! dont_really_delete)
3338     {
3339       if (prev)
3340         {
3341           NEXT_INSN (prev) = next;
3342           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
3343             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
3344                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
3345         }
3346
3347       if (next)
3348         {
3349           PREV_INSN (next) = prev;
3350           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
3351             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
3352         }
3353
3354       if (prev && NEXT_INSN (prev) == 0)
3355         set_last_insn (prev);
3356     }
3357
3358   /* If deleting a jump, decrement the count of the label,
3359      and delete the label if it is now unused.  */
3360
3361   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
3362     if (--LABEL_NUSES (JUMP_LABEL (insn)) == 0)
3363       {
3364         /* This can delete NEXT or PREV,
3365            either directly if NEXT is JUMP_LABEL (INSN),
3366            or indirectly through more levels of jumps.  */
3367         delete_insn (JUMP_LABEL (insn));
3368         /* I feel a little doubtful about this loop,
3369            but I see no clean and sure alternative way
3370            to find the first insn after INSN that is not now deleted.
3371            I hope this works.  */
3372         while (next && INSN_DELETED_P (next))
3373           next = NEXT_INSN (next);
3374         return next;
3375       }
3376
3377   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
3378     prev = PREV_INSN (prev);
3379
3380   /* If INSN was a label and a dispatch table follows it,
3381      delete the dispatch table.  The tablejump must have gone already.
3382      It isn't useful to fall through into a table.  */
3383
3384   if (was_code_label
3385       && NEXT_INSN (insn) != 0
3386       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
3387       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
3388           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
3389     next = delete_insn (NEXT_INSN (insn));
3390
3391   /* If INSN was a label, delete insns following it if now unreachable.  */
3392
3393   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
3394     {
3395       register RTX_CODE code;
3396       while (next != 0
3397              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
3398                  || code == NOTE
3399                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
3400         {
3401           if (code == NOTE
3402               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
3403             next = NEXT_INSN (next);
3404           /* Keep going past other deleted labels to delete what follows.  */
3405           else if (code == CODE_LABEL && INSN_DELETED_P (next))
3406             next = NEXT_INSN (next);
3407           else
3408             /* Note: if this deletes a jump, it can cause more
3409                deletion of unreachable code, after a different label.
3410                As long as the value from this recursive call is correct,
3411                this invocation functions correctly.  */
3412             next = delete_insn (next);
3413         }
3414     }
3415
3416   return next;
3417 }
3418
3419 /* Advance from INSN till reaching something not deleted
3420    then return that.  May return INSN itself.  */
3421
3422 rtx
3423 next_nondeleted_insn (insn)
3424      rtx insn;
3425 {
3426   while (INSN_DELETED_P (insn))
3427     insn = NEXT_INSN (insn);
3428   return insn;
3429 }
3430 \f
3431 /* Delete a range of insns from FROM to TO, inclusive.
3432    This is for the sake of peephole optimization, so assume
3433    that whatever these insns do will still be done by a new
3434    peephole insn that will replace them.  */
3435
3436 void
3437 delete_for_peephole (from, to)
3438      register rtx from, to;
3439 {
3440   register rtx insn = from;
3441
3442   while (1)
3443     {
3444       register rtx next = NEXT_INSN (insn);
3445       register rtx prev = PREV_INSN (insn);
3446
3447       if (GET_CODE (insn) != NOTE)
3448         {
3449           INSN_DELETED_P (insn) = 1;
3450
3451           /* Patch this insn out of the chain.  */
3452           /* We don't do this all at once, because we
3453              must preserve all NOTEs.  */
3454           if (prev)
3455             NEXT_INSN (prev) = next;
3456
3457           if (next)
3458             PREV_INSN (next) = prev;
3459         }
3460
3461       if (insn == to)
3462         break;
3463       insn = next;
3464     }
3465
3466   /* Note that if TO is an unconditional jump
3467      we *do not* delete the BARRIER that follows,
3468      since the peephole that replaces this sequence
3469      is also an unconditional jump in that case.  */
3470 }
3471 \f
3472 /* Invert the condition of the jump JUMP, and make it jump
3473    to label NLABEL instead of where it jumps now.  */
3474
3475 int
3476 invert_jump (jump, nlabel)
3477      rtx jump, nlabel;
3478 {
3479   /* We have to either invert the condition and change the label or
3480      do neither.  Either operation could fail.  We first try to invert
3481      the jump. If that succeeds, we try changing the label.  If that fails,
3482      we invert the jump back to what it was.  */
3483
3484   if (! invert_exp (PATTERN (jump), jump))
3485     return 0;
3486
3487   if (redirect_jump (jump, nlabel))
3488     return 1;
3489
3490   if (! invert_exp (PATTERN (jump), jump))
3491     /* This should just be putting it back the way it was.  */
3492     abort ();
3493
3494   return  0;
3495 }
3496
3497 /* Invert the jump condition of rtx X contained in jump insn, INSN.
3498
3499    Return 1 if we can do so, 0 if we cannot find a way to do so that
3500    matches a pattern.  */
3501
3502 int
3503 invert_exp (x, insn)
3504      rtx x;
3505      rtx insn;
3506 {
3507   register RTX_CODE code;
3508   register int i;
3509   register char *fmt;
3510
3511   code = GET_CODE (x);
3512
3513   if (code == IF_THEN_ELSE)
3514     {
3515       register rtx comp = XEXP (x, 0);
3516       register rtx tem;
3517
3518       /* We can do this in two ways:  The preferable way, which can only
3519          be done if this is not an integer comparison, is to reverse
3520          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
3521          of the IF_THEN_ELSE.  If we can't do either, fail.  */
3522
3523       if (can_reverse_comparison_p (comp, insn)
3524           && validate_change (insn, &XEXP (x, 0),
3525                               gen_rtx (reverse_condition (GET_CODE (comp)),
3526                                        GET_MODE (comp), XEXP (comp, 0),
3527                                        XEXP (comp, 1)), 0))
3528         return 1;
3529
3530       tem = XEXP (x, 1);
3531       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
3532       validate_change (insn, &XEXP (x, 2), tem, 1);
3533       return apply_change_group ();
3534     }
3535
3536   fmt = GET_RTX_FORMAT (code);
3537   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3538     {
3539       if (fmt[i] == 'e')
3540         if (! invert_exp (XEXP (x, i), insn))
3541           return 0;
3542       if (fmt[i] == 'E')
3543         {
3544           register int j;
3545           for (j = 0; j < XVECLEN (x, i); j++)
3546             if (!invert_exp (XVECEXP (x, i, j), insn))
3547               return 0;
3548         }
3549     }
3550
3551   return 1;
3552 }
3553 \f
3554 /* Make jump JUMP jump to label NLABEL instead of where it jumps now.
3555    If the old jump target label is unused as a result,
3556    it and the code following it may be deleted.
3557
3558    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
3559    RETURN insn.
3560
3561    The return value will be 1 if the change was made, 0 if it wasn't (this
3562    can only occur for NLABEL == 0).  */
3563
3564 int
3565 redirect_jump (jump, nlabel)
3566      rtx jump, nlabel;
3567 {
3568   register rtx olabel = JUMP_LABEL (jump);
3569
3570   if (nlabel == olabel)
3571     return 1;
3572
3573   if (! redirect_exp (&PATTERN (jump), olabel, nlabel, jump))
3574     return 0;
3575
3576   /* If this is an unconditional branch, delete it from the jump_chain of
3577      OLABEL and add it to the jump_chain of NLABEL (assuming both labels
3578      have UID's in range and JUMP_CHAIN is valid).  */
3579   if (jump_chain && (simplejump_p (jump)
3580                      || GET_CODE (PATTERN (jump)) == RETURN))
3581     {
3582       int label_index = nlabel ? INSN_UID (nlabel) : 0;
3583
3584       delete_from_jump_chain (jump);
3585       if (label_index < max_jump_chain
3586           && INSN_UID (jump) < max_jump_chain)
3587         {
3588           jump_chain[INSN_UID (jump)] = jump_chain[label_index];
3589           jump_chain[label_index] = jump;
3590         }
3591     }
3592
3593   JUMP_LABEL (jump) = nlabel;
3594   if (nlabel)
3595     ++LABEL_NUSES (nlabel);
3596
3597   if (olabel && --LABEL_NUSES (olabel) == 0)
3598     delete_insn (olabel);
3599
3600   return 1;
3601 }
3602
3603 /* Delete the instruction JUMP from any jump chain it might be on.  */
3604
3605 static void
3606 delete_from_jump_chain (jump)
3607      rtx jump;
3608 {
3609   int index;
3610   rtx olabel = JUMP_LABEL (jump);
3611
3612   /* Handle unconditional jumps.  */
3613   if (jump_chain && olabel != 0
3614       && INSN_UID (olabel) < max_jump_chain
3615       && simplejump_p (jump))
3616     index = INSN_UID (olabel);
3617   /* Handle return insns.  */
3618   else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
3619     index = 0;
3620   else return;
3621
3622   if (jump_chain[index] == jump)
3623     jump_chain[index] = jump_chain[INSN_UID (jump)];
3624   else
3625     {
3626       rtx insn;
3627
3628       for (insn = jump_chain[index];
3629            insn != 0;
3630            insn = jump_chain[INSN_UID (insn)])
3631         if (jump_chain[INSN_UID (insn)] == jump)
3632           {
3633             jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
3634             break;
3635           }
3636     }
3637 }
3638
3639 /* If NLABEL is nonzero, throughout the rtx at LOC,
3640    alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL).  If OLABEL is
3641    zero, alter (RETURN) to (LABEL_REF NLABEL).
3642
3643    If NLABEL is zero, alter (LABEL_REF OLABEL) to (RETURN) and check
3644    validity with validate_change.  Convert (set (pc) (label_ref olabel))
3645    to (return).
3646
3647    Return 0 if we found a change we would like to make but it is invalid.
3648    Otherwise, return 1.  */
3649
3650 int
3651 redirect_exp (loc, olabel, nlabel, insn)
3652      rtx *loc;
3653      rtx olabel, nlabel;
3654      rtx insn;
3655 {
3656   register rtx x = *loc;
3657   register RTX_CODE code = GET_CODE (x);
3658   register int i;
3659   register char *fmt;
3660
3661   if (code == LABEL_REF)
3662     {
3663       if (XEXP (x, 0) == olabel)
3664         {
3665           if (nlabel)
3666             XEXP (x, 0) = nlabel;
3667           else
3668             return validate_change (insn, loc, gen_rtx (RETURN, VOIDmode), 0);
3669           return 1;
3670         }
3671     }
3672   else if (code == RETURN && olabel == 0)
3673     {
3674       x = gen_rtx (LABEL_REF, VOIDmode, nlabel);
3675       if (loc == &PATTERN (insn))
3676         x = gen_rtx (SET, VOIDmode, pc_rtx, x);
3677       return validate_change (insn, loc, x, 0);
3678     }
3679
3680   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
3681       && GET_CODE (SET_SRC (x)) == LABEL_REF
3682       && XEXP (SET_SRC (x), 0) == olabel)
3683     return validate_change (insn, loc, gen_rtx (RETURN, VOIDmode), 0);
3684
3685   fmt = GET_RTX_FORMAT (code);
3686   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3687     {
3688       if (fmt[i] == 'e')
3689         if (! redirect_exp (&XEXP (x, i), olabel, nlabel, insn))
3690           return 0;
3691       if (fmt[i] == 'E')
3692         {
3693           register int j;
3694           for (j = 0; j < XVECLEN (x, i); j++)
3695             if (! redirect_exp (&XVECEXP (x, i, j), olabel, nlabel, insn))
3696               return 0;
3697         }
3698     }
3699
3700   return 1;
3701 }
3702 \f
3703 /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
3704
3705    If the old jump target label (before the dispatch table) becomes unused,
3706    it and the dispatch table may be deleted.  In that case, find the insn
3707    before the jump references that label and delete it and logical successors
3708    too.  */
3709
3710 static void
3711 redirect_tablejump (jump, nlabel)
3712      rtx jump, nlabel;
3713 {
3714   register rtx olabel = JUMP_LABEL (jump);
3715
3716   /* Add this jump to the jump_chain of NLABEL.  */
3717   if (jump_chain && INSN_UID (nlabel) < max_jump_chain
3718       && INSN_UID (jump) < max_jump_chain)
3719     {
3720       jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
3721       jump_chain[INSN_UID (nlabel)] = jump;
3722     }
3723
3724   PATTERN (jump) = gen_jump (nlabel);
3725   JUMP_LABEL (jump) = nlabel;
3726   ++LABEL_NUSES (nlabel);
3727   INSN_CODE (jump) = -1;
3728
3729   if (--LABEL_NUSES (olabel) == 0)
3730     {
3731       delete_labelref_insn (jump, olabel, 0);
3732       delete_insn (olabel);
3733     }
3734 }
3735
3736 /* Find the insn referencing LABEL that is a logical predecessor of INSN.
3737    If we found one, delete it and then delete this insn if DELETE_THIS is
3738    non-zero.  Return non-zero if INSN or a predecessor references LABEL.  */
3739
3740 static int
3741 delete_labelref_insn (insn, label, delete_this)
3742      rtx insn, label;
3743      int delete_this;
3744 {
3745   int deleted = 0;
3746   rtx link;
3747
3748   if (GET_CODE (insn) != NOTE
3749       && reg_mentioned_p (label, PATTERN (insn)))
3750     {
3751       if (delete_this)
3752         {
3753           delete_insn (insn);
3754           deleted = 1;
3755         }
3756       else
3757         return 1;
3758     }
3759
3760   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
3761     if (delete_labelref_insn (XEXP (link, 0), label, 1))
3762       {
3763         if (delete_this)
3764           {
3765             delete_insn (insn);
3766             deleted = 1;
3767           }
3768         else
3769           return 1;
3770       }
3771
3772   return deleted;
3773 }
3774 \f
3775 /* Like rtx_equal_p except that it considers two REGs as equal
3776    if they renumber to the same value and considers two commutative
3777    operations to be the same if the order of the operands has been
3778    reversed.  */
3779
3780 int
3781 rtx_renumbered_equal_p (x, y)
3782      rtx x, y;
3783 {
3784   register int i;
3785   register RTX_CODE code = GET_CODE (x);
3786   register char *fmt;
3787
3788   if (x == y)
3789     return 1;
3790
3791   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
3792       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
3793                                   && GET_CODE (SUBREG_REG (y)) == REG)))
3794     {
3795       int reg_x = -1, reg_y = -1;
3796       int word_x = 0, word_y = 0;
3797
3798       if (GET_MODE (x) != GET_MODE (y))
3799         return 0;
3800
3801       /* If we haven't done any renumbering, don't
3802          make any assumptions.  */
3803       if (reg_renumber == 0)
3804         return rtx_equal_p (x, y);
3805
3806       if (code == SUBREG)
3807         {
3808           reg_x = REGNO (SUBREG_REG (x));
3809           word_x = SUBREG_WORD (x);
3810
3811           if (reg_renumber[reg_x] >= 0)
3812             {
3813               reg_x = reg_renumber[reg_x] + word_x;
3814               word_x = 0;
3815             }
3816         }
3817
3818       else
3819         {
3820           reg_x = REGNO (x);
3821           if (reg_renumber[reg_x] >= 0)
3822             reg_x = reg_renumber[reg_x];
3823         }
3824
3825       if (GET_CODE (y) == SUBREG)
3826         {
3827           reg_y = REGNO (SUBREG_REG (y));
3828           word_y = SUBREG_WORD (y);
3829
3830           if (reg_renumber[reg_y] >= 0)
3831             {
3832               reg_y = reg_renumber[reg_y];
3833               word_y = 0;
3834             }
3835         }
3836
3837       else
3838         {
3839           reg_y = REGNO (y);
3840           if (reg_renumber[reg_y] >= 0)
3841             reg_y = reg_renumber[reg_y];
3842         }
3843
3844       return reg_x >= 0 && reg_x == reg_y && word_x == word_y;
3845     }
3846
3847   /* Now we have disposed of all the cases
3848      in which different rtx codes can match.  */
3849   if (code != GET_CODE (y))
3850     return 0;
3851
3852   switch (code)
3853     {
3854     case PC:
3855     case CC0:
3856     case ADDR_VEC:
3857     case ADDR_DIFF_VEC:
3858       return 0;
3859
3860     case CONST_INT:
3861       return INTVAL (x) == INTVAL (y);
3862
3863     case LABEL_REF:
3864       /* We can't assume nonlocal labels have their following insns yet.  */
3865       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
3866         return XEXP (x, 0) == XEXP (y, 0);
3867
3868       /* Two label-refs are equivalent if they point at labels
3869          in the same position in the instruction stream.  */
3870       return (next_real_insn (XEXP (x, 0))
3871               == next_real_insn (XEXP (y, 0)));
3872
3873     case SYMBOL_REF:
3874       return XSTR (x, 0) == XSTR (y, 0);
3875     }
3876
3877   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
3878
3879   if (GET_MODE (x) != GET_MODE (y))
3880     return 0;
3881
3882   /* For commutative operations, the RTX match if the operand match in any
3883      order.  Also handle the simple binary and unary cases without a loop.  */
3884   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3885     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3886              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
3887             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
3888                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
3889   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
3890     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3891             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
3892   else if (GET_RTX_CLASS (code) == '1')
3893     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
3894
3895   /* Compare the elements.  If any pair of corresponding elements
3896      fail to match, return 0 for the whole things.  */
3897
3898   fmt = GET_RTX_FORMAT (code);
3899   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3900     {
3901       register int j;
3902       switch (fmt[i])
3903         {
3904         case 'w':
3905           if (XWINT (x, i) != XWINT (y, i))
3906             return 0;
3907           break;
3908
3909         case 'i':
3910           if (XINT (x, i) != XINT (y, i))
3911             return 0;
3912           break;
3913
3914         case 's':
3915           if (strcmp (XSTR (x, i), XSTR (y, i)))
3916             return 0;
3917           break;
3918
3919         case 'e':
3920           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
3921             return 0;
3922           break;
3923
3924         case 'u':
3925           if (XEXP (x, i) != XEXP (y, i))
3926             return 0;
3927           /* fall through.  */
3928         case '0':
3929           break;
3930
3931         case 'E':
3932           if (XVECLEN (x, i) != XVECLEN (y, i))
3933             return 0;
3934           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3935             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
3936               return 0;
3937           break;
3938
3939         default:
3940           abort ();
3941         }
3942     }
3943   return 1;
3944 }
3945 \f
3946 /* If X is a hard register or equivalent to one or a subregister of one,
3947    return the hard register number.  If X is a pseudo register that was not
3948    assigned a hard register, return the pseudo register number.  Otherwise,
3949    return -1.  Any rtx is valid for X.  */
3950
3951 int
3952 true_regnum (x)
3953      rtx x;
3954 {
3955   if (GET_CODE (x) == REG)
3956     {
3957       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
3958         return reg_renumber[REGNO (x)];
3959       return REGNO (x);
3960     }
3961   if (GET_CODE (x) == SUBREG)
3962     {
3963       int base = true_regnum (SUBREG_REG (x));
3964       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
3965         return SUBREG_WORD (x) + base;
3966     }
3967   return -1;
3968 }
3969 \f
3970 /* Optimize code of the form:
3971
3972         for (x = a[i]; x; ...)
3973           ...
3974         for (x = a[i]; x; ...)
3975           ...
3976       foo:
3977
3978    Loop optimize will change the above code into
3979
3980         if (x = a[i])
3981           for (;;)
3982              { ...; if (! (x = ...)) break; }
3983         if (x = a[i])
3984           for (;;)
3985              { ...; if (! (x = ...)) break; }
3986       foo:
3987
3988    In general, if the first test fails, the program can branch
3989    directly to `foo' and skip the second try which is doomed to fail.
3990    We run this after loop optimization and before flow analysis.  */
3991
3992 /* When comparing the insn patterns, we track the fact that different
3993    pseudo-register numbers may have been used in each computation.
3994    The following array stores an equivalence -- same_regs[I] == J means
3995    that pseudo register I was used in the first set of tests in a context
3996    where J was used in the second set.  We also count the number of such
3997    pending equivalences.  If nonzero, the expressions really aren't the
3998    same.  */
3999
4000 static int *same_regs;
4001
4002 static int num_same_regs;
4003
4004 /* Track any registers modified between the target of the first jump and
4005    the second jump.  They never compare equal.  */
4006
4007 static char *modified_regs;
4008
4009 /* Record if memory was modified.  */
4010
4011 static int modified_mem;
4012
4013 /* Called via note_stores on each insn between the target of the first
4014    branch and the second branch.  It marks any changed registers.  */
4015
4016 static void
4017 mark_modified_reg (dest, x)
4018      rtx dest;
4019      rtx x;
4020 {
4021   int regno, i;
4022
4023   if (GET_CODE (dest) == SUBREG)
4024     dest = SUBREG_REG (dest);
4025
4026   if (GET_CODE (dest) == MEM)
4027     modified_mem = 1;
4028
4029   if (GET_CODE (dest) != REG)
4030     return;
4031
4032   regno = REGNO (dest);
4033   if (regno >= FIRST_PSEUDO_REGISTER)
4034     modified_regs[regno] = 1;
4035   else
4036     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
4037       modified_regs[regno + i] = 1;
4038 }
4039
4040 /* F is the first insn in the chain of insns.  */
4041
4042 void
4043 thread_jumps (f, max_reg, flag_before_loop)
4044      rtx f;
4045      int max_reg;
4046      int flag_before_loop;
4047 {
4048   /* Basic algorithm is to find a conditional branch,
4049      the label it may branch to, and the branch after
4050      that label.  If the two branches test the same condition,
4051      walk back from both branch paths until the insn patterns
4052      differ, or code labels are hit.  If we make it back to
4053      the target of the first branch, then we know that the first branch
4054      will either always succeed or always fail depending on the relative
4055      senses of the two branches.  So adjust the first branch accordingly
4056      in this case.  */
4057
4058   rtx label, b1, b2, t1, t2;
4059   enum rtx_code code1, code2;
4060   rtx b1op0, b1op1, b2op0, b2op1;
4061   int changed = 1;
4062   int i;
4063   int *all_reset;
4064
4065   /* Allocate register tables and quick-reset table.  */
4066   modified_regs = (char *) alloca (max_reg * sizeof (char));
4067   same_regs = (int *) alloca (max_reg * sizeof (int));
4068   all_reset = (int *) alloca (max_reg * sizeof (int));
4069   for (i = 0; i < max_reg; i++)
4070     all_reset[i] = -1;
4071
4072   while (changed)
4073     {
4074       changed = 0;
4075
4076       for (b1 = f; b1; b1 = NEXT_INSN (b1))
4077         {
4078           /* Get to a candidate branch insn.  */
4079           if (GET_CODE (b1) != JUMP_INSN
4080               || ! condjump_p (b1) || simplejump_p (b1)
4081               || JUMP_LABEL (b1) == 0)
4082             continue;
4083
4084           bzero (modified_regs, max_reg * sizeof (char));
4085           modified_mem = 0;
4086
4087           bcopy ((char *) all_reset, (char *) same_regs,
4088                  max_reg * sizeof (int));
4089           num_same_regs = 0;
4090
4091           label = JUMP_LABEL (b1);
4092
4093           /* Look for a branch after the target.  Record any registers and
4094              memory modified between the target and the branch.  Stop when we
4095              get to a label since we can't know what was changed there.  */
4096           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
4097             {
4098               if (GET_CODE (b2) == CODE_LABEL)
4099                 break;
4100
4101               else if (GET_CODE (b2) == JUMP_INSN)
4102                 {
4103                   /* If this is an unconditional jump and is the only use of
4104                      its target label, we can follow it.  */
4105                   if (simplejump_p (b2)
4106                       && JUMP_LABEL (b2) != 0
4107                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
4108                     {
4109                       b2 = JUMP_LABEL (b2);
4110                       continue;
4111                     }
4112                   else
4113                     break;
4114                 }
4115
4116               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
4117                 continue;
4118
4119               if (GET_CODE (b2) == CALL_INSN)
4120                 {
4121                   modified_mem = 1;
4122                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4123                     if (call_used_regs[i] && ! fixed_regs[i]
4124                         && i != STACK_POINTER_REGNUM
4125                         && i != FRAME_POINTER_REGNUM
4126                         && i != HARD_FRAME_POINTER_REGNUM
4127                         && i != ARG_POINTER_REGNUM)
4128                       modified_regs[i] = 1;
4129                 }
4130
4131               note_stores (PATTERN (b2), mark_modified_reg);
4132             }
4133
4134           /* Check the next candidate branch insn from the label
4135              of the first.  */
4136           if (b2 == 0
4137               || GET_CODE (b2) != JUMP_INSN
4138               || b2 == b1
4139               || ! condjump_p (b2)
4140               || simplejump_p (b2))
4141             continue;
4142
4143           /* Get the comparison codes and operands, reversing the
4144              codes if appropriate.  If we don't have comparison codes,
4145              we can't do anything.  */
4146           b1op0 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 0);
4147           b1op1 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 1);
4148           code1 = GET_CODE (XEXP (SET_SRC (PATTERN (b1)), 0));
4149           if (XEXP (SET_SRC (PATTERN (b1)), 1) == pc_rtx)
4150             code1 = reverse_condition (code1);
4151
4152           b2op0 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 0);
4153           b2op1 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 1);
4154           code2 = GET_CODE (XEXP (SET_SRC (PATTERN (b2)), 0));
4155           if (XEXP (SET_SRC (PATTERN (b2)), 1) == pc_rtx)
4156             code2 = reverse_condition (code2);
4157
4158           /* If they test the same things and knowing that B1 branches
4159              tells us whether or not B2 branches, check if we
4160              can thread the branch.  */
4161           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
4162               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
4163               && (comparison_dominates_p (code1, code2)
4164                   || comparison_dominates_p (code1, reverse_condition (code2))))
4165             {
4166               t1 = prev_nonnote_insn (b1);
4167               t2 = prev_nonnote_insn (b2);
4168
4169               while (t1 != 0 && t2 != 0)
4170                 {
4171                   if (t2 == label)
4172                     {
4173                       /* We have reached the target of the first branch.
4174                          If there are no pending register equivalents,
4175                          we know that this branch will either always
4176                          succeed (if the senses of the two branches are
4177                          the same) or always fail (if not).  */
4178                       rtx new_label;
4179
4180                       if (num_same_regs != 0)
4181                         break;
4182
4183                       if (comparison_dominates_p (code1, code2))
4184                         new_label = JUMP_LABEL (b2);
4185                       else
4186                         new_label = get_label_after (b2);
4187
4188                       if (JUMP_LABEL (b1) != new_label)
4189                         {
4190                           rtx prev = PREV_INSN (new_label);
4191
4192                           if (flag_before_loop
4193                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
4194                             {
4195                               /* Don't thread to the loop label.  If a loop
4196                                  label is reused, loop optimization will
4197                                  be disabled for that loop.  */
4198                               new_label = gen_label_rtx ();
4199                               emit_label_after (new_label, PREV_INSN (prev));
4200                             }
4201                           changed |= redirect_jump (b1, new_label);
4202                         }
4203                       break;
4204                     }
4205
4206                   /* If either of these is not a normal insn (it might be
4207                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
4208                      have already been skipped above.)  Similarly, fail
4209                      if the insns are different.  */
4210                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
4211                       || recog_memoized (t1) != recog_memoized (t2)
4212                       || ! rtx_equal_for_thread_p (PATTERN (t1),
4213                                                    PATTERN (t2), t2))
4214                     break;
4215
4216                   t1 = prev_nonnote_insn (t1);
4217                   t2 = prev_nonnote_insn (t2);
4218                 }
4219             }
4220         }
4221     }
4222 }
4223 \f
4224 /* This is like RTX_EQUAL_P except that it knows about our handling of
4225    possibly equivalent registers and knows to consider volatile and
4226    modified objects as not equal.
4227
4228    YINSN is the insn containing Y.  */
4229
4230 int
4231 rtx_equal_for_thread_p (x, y, yinsn)
4232      rtx x, y;
4233      rtx yinsn;
4234 {
4235   register int i;
4236   register int j;
4237   register enum rtx_code code;
4238   register char *fmt;
4239
4240   code = GET_CODE (x);
4241   /* Rtx's of different codes cannot be equal.  */
4242   if (code != GET_CODE (y))
4243     return 0;
4244
4245   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
4246      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
4247
4248   if (GET_MODE (x) != GET_MODE (y))
4249     return 0;
4250
4251   /* For commutative operations, the RTX match if the operand match in any
4252      order.  Also handle the simple binary and unary cases without a loop.  */
4253   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
4254     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
4255              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
4256             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
4257                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
4258   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
4259     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
4260             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
4261   else if (GET_RTX_CLASS (code) == '1')
4262     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
4263
4264   /* Handle special-cases first.  */
4265   switch (code)
4266     {
4267     case REG:
4268       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
4269         return 1;
4270
4271       /* If neither is user variable or hard register, check for possible
4272          equivalence.  */
4273       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
4274           || REGNO (x) < FIRST_PSEUDO_REGISTER
4275           || REGNO (y) < FIRST_PSEUDO_REGISTER)
4276         return 0;
4277
4278       if (same_regs[REGNO (x)] == -1)
4279         {
4280           same_regs[REGNO (x)] = REGNO (y);
4281           num_same_regs++;
4282
4283           /* If this is the first time we are seeing a register on the `Y'
4284              side, see if it is the last use.  If not, we can't thread the
4285              jump, so mark it as not equivalent.  */
4286           if (regno_last_uid[REGNO (y)] != INSN_UID (yinsn))
4287             return 0;
4288
4289           return 1;
4290         }
4291       else
4292         return (same_regs[REGNO (x)] == REGNO (y));
4293
4294       break;
4295
4296     case MEM:
4297       /* If memory modified or either volatile, not equivalent.
4298          Else, check address. */
4299       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4300         return 0;
4301
4302       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
4303
4304     case ASM_INPUT:
4305       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4306         return 0;
4307
4308       break;
4309
4310     case SET:
4311       /* Cancel a pending `same_regs' if setting equivalenced registers.
4312          Then process source.  */
4313       if (GET_CODE (SET_DEST (x)) == REG
4314           && GET_CODE (SET_DEST (y)) == REG)
4315         {
4316           if (same_regs[REGNO (SET_DEST (x))] == REGNO (SET_DEST (y)))
4317             {
4318               same_regs[REGNO (SET_DEST (x))] = -1;
4319               num_same_regs--;
4320             }
4321           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
4322             return 0;
4323         }
4324       else
4325         if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
4326           return 0;
4327
4328       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
4329
4330     case LABEL_REF:
4331       return XEXP (x, 0) == XEXP (y, 0);
4332
4333     case SYMBOL_REF:
4334       return XSTR (x, 0) == XSTR (y, 0);
4335     }
4336
4337   if (x == y)
4338     return 1;
4339
4340   fmt = GET_RTX_FORMAT (code);
4341   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4342     {
4343       switch (fmt[i])
4344         {
4345         case 'w':
4346           if (XWINT (x, i) != XWINT (y, i))
4347             return 0;
4348           break;
4349
4350         case 'n':
4351         case 'i':
4352           if (XINT (x, i) != XINT (y, i))
4353             return 0;
4354           break;
4355
4356         case 'V':
4357         case 'E':
4358           /* Two vectors must have the same length.  */
4359           if (XVECLEN (x, i) != XVECLEN (y, i))
4360             return 0;
4361
4362           /* And the corresponding elements must match.  */
4363           for (j = 0; j < XVECLEN (x, i); j++)
4364             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
4365                                         XVECEXP (y, i, j), yinsn) == 0)
4366               return 0;
4367           break;
4368
4369         case 'e':
4370           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
4371             return 0;
4372           break;
4373
4374         case 'S':
4375         case 's':
4376           if (strcmp (XSTR (x, i), XSTR (y, i)))
4377             return 0;
4378           break;
4379
4380         case 'u':
4381           /* These are just backpointers, so they don't matter.  */
4382           break;
4383
4384         case '0':
4385           break;
4386
4387           /* It is believed that rtx's at this level will never
4388              contain anything but integers and other rtx's,
4389              except for within LABEL_REFs and SYMBOL_REFs.  */
4390         default:
4391           abort ();
4392         }
4393     }
4394   return 1;
4395 }