gcc/jump.c

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