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