gcc/jump.c

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