gcc/jump.c

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