gcc/jump.c

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