gcc/jump.c

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