gcc/jump.c

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