gcc/jump.c

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