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                && GET_CODE (PATTERN (insn)) == SET
2170                && SET_SRC (PATTERN (insn)) == pc_rtx
2171                && SET_DEST (PATTERN (insn)) == pc_rtx)
2172         insn = delete_insn (insn);
2173
2174       else
2175         insn = NEXT_INSN (insn);
2176     }
2177 }
2178
2179 /* Mark the label each jump jumps to.
2180    Combine consecutive labels, and count uses of labels.
2181
2182    For each label, make a chain (using `jump_chain')
2183    of all the *unconditional* jumps that jump to it;
2184    also make a chain of all returns.
2185
2186    CROSS_JUMP indicates whether we are doing cross jumping
2187    and if we are whether we will be paying attention to
2188    death notes or not.  */
2189
2190 static void
2191 mark_all_labels (f, cross_jump)
2192      rtx f;
2193      int cross_jump;
2194 {
2195   rtx insn;
2196
2197   for (insn = f; insn; insn = NEXT_INSN (insn))
2198     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2199       {
2200         mark_jump_label (PATTERN (insn), insn, cross_jump);
2201         if (! INSN_DELETED_P (insn) && GET_CODE (insn) == JUMP_INSN)
2202           {
2203             if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
2204               {
2205                 jump_chain[INSN_UID (insn)]
2206                   = jump_chain[INSN_UID (JUMP_LABEL (insn))];
2207                 jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
2208               }
2209             if (GET_CODE (PATTERN (insn)) == RETURN)
2210               {
2211                 jump_chain[INSN_UID (insn)] = jump_chain[0];
2212                 jump_chain[0] = insn;
2213               }
2214           }
2215       }
2216 }
2217
2218 /* Delete all labels already not referenced.
2219    Also find and return the last insn.  */
2220
2221 static rtx
2222 delete_unreferenced_labels (f)
2223      rtx f;
2224 {
2225   rtx final = NULL_RTX;
2226   rtx insn;
2227
2228   for (insn = f; insn; )
2229     {
2230       if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)
2231         insn = delete_insn (insn);
2232       else
2233         {
2234           final = insn;
2235           insn = NEXT_INSN (insn);
2236         }
2237     }
2238
2239   return final;
2240 }
2241
2242 /* Delete various simple forms of moves which have no necessary
2243    side effect.  */
2244
2245 static void
2246 delete_noop_moves (f)
2247      rtx f;
2248 {
2249   rtx insn, next;
2250
2251   for (insn = f; insn; )
2252     {
2253       next = NEXT_INSN (insn);
2254
2255       if (GET_CODE (insn) == INSN)
2256         {
2257           register rtx body = PATTERN (insn);
2258
2259 /* Combine stack_adjusts with following push_insns.  */
2260 #ifdef PUSH_ROUNDING
2261           if (GET_CODE (body) == SET
2262               && SET_DEST (body) == stack_pointer_rtx
2263               && GET_CODE (SET_SRC (body)) == PLUS
2264               && XEXP (SET_SRC (body), 0) == stack_pointer_rtx
2265               && GET_CODE (XEXP (SET_SRC (body), 1)) == CONST_INT
2266               && INTVAL (XEXP (SET_SRC (body), 1)) > 0)
2267             {
2268               rtx p;
2269               rtx stack_adjust_insn = insn;
2270               int stack_adjust_amount = INTVAL (XEXP (SET_SRC (body), 1));
2271               int total_pushed = 0;
2272               int pushes = 0;
2273
2274               /* Find all successive push insns.  */
2275               p = insn;
2276               /* Don't convert more than three pushes;
2277                  that starts adding too many displaced addresses
2278                  and the whole thing starts becoming a losing
2279                  proposition.  */
2280               while (pushes < 3)
2281                 {
2282                   rtx pbody, dest;
2283                   p = next_nonnote_insn (p);
2284                   if (p == 0 || GET_CODE (p) != INSN)
2285                     break;
2286                   pbody = PATTERN (p);
2287                   if (GET_CODE (pbody) != SET)
2288                     break;
2289                   dest = SET_DEST (pbody);
2290                   /* Allow a no-op move between the adjust and the push.  */
2291                   if (GET_CODE (dest) == REG
2292                       && GET_CODE (SET_SRC (pbody)) == REG
2293                       && REGNO (dest) == REGNO (SET_SRC (pbody)))
2294                     continue;
2295                   if (! (GET_CODE (dest) == MEM
2296                          && GET_CODE (XEXP (dest, 0)) == POST_INC
2297                          && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
2298                     break;
2299                   pushes++;
2300                   if (total_pushed + GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)))
2301                       > stack_adjust_amount)
2302                     break;
2303                   total_pushed += GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
2304                 }
2305
2306               /* Discard the amount pushed from the stack adjust;
2307                  maybe eliminate it entirely.  */
2308               if (total_pushed >= stack_adjust_amount)
2309                 {
2310                   delete_computation (stack_adjust_insn);
2311                   total_pushed = stack_adjust_amount;
2312                 }
2313               else
2314                 XEXP (SET_SRC (PATTERN (stack_adjust_insn)), 1)
2315                   = GEN_INT (stack_adjust_amount - total_pushed);
2316
2317               /* Change the appropriate push insns to ordinary stores.  */
2318               p = insn;
2319               while (total_pushed > 0)
2320                 {
2321                   rtx pbody, dest;
2322                   p = next_nonnote_insn (p);
2323                   if (GET_CODE (p) != INSN)
2324                     break;
2325                   pbody = PATTERN (p);
2326                   if (GET_CODE (pbody) != SET)
2327                     break;
2328                   dest = SET_DEST (pbody);
2329                   /* Allow a no-op move between the adjust and the push.  */
2330                   if (GET_CODE (dest) == REG
2331                       && GET_CODE (SET_SRC (pbody)) == REG
2332                       && REGNO (dest) == REGNO (SET_SRC (pbody)))
2333                     continue;
2334                   if (! (GET_CODE (dest) == MEM
2335                          && GET_CODE (XEXP (dest, 0)) == POST_INC
2336                          && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
2337                     break;
2338                   total_pushed -= GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
2339                   /* If this push doesn't fully fit in the space
2340                      of the stack adjust that we deleted,
2341                      make another stack adjust here for what we
2342                      didn't use up.  There should be peepholes
2343                      to recognize the resulting sequence of insns.  */
2344                   if (total_pushed < 0)
2345                     {
2346                       emit_insn_before (gen_add2_insn (stack_pointer_rtx,
2347                                                        GEN_INT (- total_pushed)),
2348                                         p);
2349                       break;
2350                     }
2351                   XEXP (dest, 0)
2352                     = plus_constant (stack_pointer_rtx, total_pushed);
2353                 }
2354             }
2355 #endif
2356
2357           /* Detect and delete no-op move instructions
2358              resulting from not allocating a parameter in a register.  */
2359
2360           if (GET_CODE (body) == SET
2361               && (SET_DEST (body) == SET_SRC (body)
2362                   || (GET_CODE (SET_DEST (body)) == MEM
2363                       && GET_CODE (SET_SRC (body)) == MEM
2364                       && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
2365               && ! (GET_CODE (SET_DEST (body)) == MEM
2366                     && MEM_VOLATILE_P (SET_DEST (body)))
2367               && ! (GET_CODE (SET_SRC (body)) == MEM
2368                     && MEM_VOLATILE_P (SET_SRC (body))))
2369             delete_computation (insn);
2370
2371           /* Detect and ignore no-op move instructions
2372              resulting from smart or fortuitous register allocation.  */
2373
2374           else if (GET_CODE (body) == SET)
2375             {
2376               int sreg = true_regnum (SET_SRC (body));
2377               int dreg = true_regnum (SET_DEST (body));
2378
2379               if (sreg == dreg && sreg >= 0)
2380                 delete_insn (insn);
2381               else if (sreg >= 0 && dreg >= 0)
2382                 {
2383                   rtx trial;
2384                   rtx tem = find_equiv_reg (NULL_RTX, insn, 0,
2385                                             sreg, NULL_PTR, dreg,
2386                                             GET_MODE (SET_SRC (body)));
2387
2388                   if (tem != 0
2389                       && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
2390                     {
2391                       /* DREG may have been the target of a REG_DEAD note in
2392                          the insn which makes INSN redundant.  If so, reorg
2393                          would still think it is dead.  So search for such a
2394                          note and delete it if we find it.  */
2395                       if (! find_regno_note (insn, REG_UNUSED, dreg))
2396                         for (trial = prev_nonnote_insn (insn);
2397                              trial && GET_CODE (trial) != CODE_LABEL;
2398                              trial = prev_nonnote_insn (trial))
2399                           if (find_regno_note (trial, REG_DEAD, dreg))
2400                             {
2401                               remove_death (dreg, trial);
2402                               break;
2403                             }
2404
2405                       /* Deleting insn could lose a death-note for SREG.  */
2406                       if ((trial = find_regno_note (insn, REG_DEAD, sreg)))
2407                         {
2408                           /* Change this into a USE so that we won't emit
2409                              code for it, but still can keep the note.  */
2410                           PATTERN (insn)
2411                             = gen_rtx_USE (VOIDmode, XEXP (trial, 0));
2412                           INSN_CODE (insn) = -1;
2413                           /* Remove all reg notes but the REG_DEAD one.  */
2414                           REG_NOTES (insn) = trial;
2415                           XEXP (trial, 1) = NULL_RTX;
2416                         }
2417                       else
2418                         delete_insn (insn);
2419                     }
2420                 }
2421               else if (dreg >= 0 && CONSTANT_P (SET_SRC (body))
2422                        && find_equiv_reg (SET_SRC (body), insn, 0, dreg,
2423                                           NULL_PTR, 0,
2424                                           GET_MODE (SET_DEST (body))))
2425                 {
2426                   /* This handles the case where we have two consecutive
2427                      assignments of the same constant to pseudos that didn't
2428                      get a hard reg.  Each SET from the constant will be
2429                      converted into a SET of the spill register and an
2430                      output reload will be made following it.  This produces
2431                      two loads of the same constant into the same spill
2432                      register.  */
2433
2434                   rtx in_insn = insn;
2435
2436                   /* Look back for a death note for the first reg.
2437                      If there is one, it is no longer accurate.  */
2438                   while (in_insn && GET_CODE (in_insn) != CODE_LABEL)
2439                     {
2440                       if ((GET_CODE (in_insn) == INSN
2441                            || GET_CODE (in_insn) == JUMP_INSN)
2442                           && find_regno_note (in_insn, REG_DEAD, dreg))
2443                         {
2444                           remove_death (dreg, in_insn);
2445                           break;
2446                         }
2447                       in_insn = PREV_INSN (in_insn);
2448                     }
2449
2450                   /* Delete the second load of the value.  */
2451                   delete_insn (insn);
2452                 }
2453             }
2454           else if (GET_CODE (body) == PARALLEL)
2455             {
2456               /* If each part is a set between two identical registers or
2457                  a USE or CLOBBER, delete the insn.  */
2458               int i, sreg, dreg;
2459               rtx tem;
2460
2461               for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
2462                 {
2463                   tem = XVECEXP (body, 0, i);
2464                   if (GET_CODE (tem) == USE || GET_CODE (tem) == CLOBBER)
2465                     continue;
2466
2467                   if (GET_CODE (tem) != SET
2468                       || (sreg = true_regnum (SET_SRC (tem))) < 0
2469                       || (dreg = true_regnum (SET_DEST (tem))) < 0
2470                       || dreg != sreg)
2471                     break;
2472                 }
2473
2474               if (i < 0)
2475                 delete_insn (insn);
2476             }
2477           /* Also delete insns to store bit fields if they are no-ops.  */
2478           /* Not worth the hair to detect this in the big-endian case.  */
2479           else if (! BYTES_BIG_ENDIAN
2480                    && GET_CODE (body) == SET
2481                    && GET_CODE (SET_DEST (body)) == ZERO_EXTRACT
2482                    && XEXP (SET_DEST (body), 2) == const0_rtx
2483                    && XEXP (SET_DEST (body), 0) == SET_SRC (body)
2484                    && ! (GET_CODE (SET_SRC (body)) == MEM
2485                          && MEM_VOLATILE_P (SET_SRC (body))))
2486             delete_insn (insn);
2487         }
2488       insn = next;
2489     }
2490 }
2491
2492 /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
2493    If so indicate that this function can drop off the end by returning
2494    1, else return 0.
2495
2496    CHECK_DELETED indicates whether we must check if the note being
2497    searched for has the deleted flag set.
2498
2499    DELETE_FINAL_NOTE indicates whether we should delete the note
2500    if we find it.  */
2501
2502 static int
2503 calculate_can_reach_end (last, check_deleted, delete_final_note)
2504      rtx last;
2505      int check_deleted;
2506      int delete_final_note;
2507 {
2508   rtx insn = last;
2509   int n_labels = 1;
2510
2511   while (insn != NULL_RTX)
2512     {
2513       int ok = 0;
2514
2515       /* One label can follow the end-note: the return label.  */
2516       if (GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
2517         ok = 1;
2518       /* Ordinary insns can follow it if returning a structure.  */
2519       else if (GET_CODE (insn) == INSN)
2520         ok = 1;
2521       /* If machine uses explicit RETURN insns, no epilogue,
2522          then one of them follows the note.  */
2523       else if (GET_CODE (insn) == JUMP_INSN
2524                && GET_CODE (PATTERN (insn)) == RETURN)
2525         ok = 1;
2526       /* A barrier can follow the return insn.  */
2527       else if (GET_CODE (insn) == BARRIER)
2528         ok = 1;
2529       /* Other kinds of notes can follow also.  */
2530       else if (GET_CODE (insn) == NOTE
2531                && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
2532         ok = 1;
2533
2534       if (ok != 1)
2535         break;
2536
2537       insn = PREV_INSN (insn);
2538     }
2539
2540   /* See if we backed up to the appropriate type of note.  */
2541   if (insn != NULL_RTX
2542       && GET_CODE (insn) == NOTE
2543       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END
2544       && (check_deleted == 0
2545           || ! INSN_DELETED_P (insn)))
2546     {
2547       if (delete_final_note)
2548         delete_insn (insn);
2549       return 1;
2550     }
2551
2552   return 0;
2553 }
2554
2555 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
2556    jump.  Assume that this unconditional jump is to the exit test code.  If
2557    the code is sufficiently simple, make a copy of it before INSN,
2558    followed by a jump to the exit of the loop.  Then delete the unconditional
2559    jump after INSN.
2560
2561    Return 1 if we made the change, else 0.
2562
2563    This is only safe immediately after a regscan pass because it uses the
2564    values of regno_first_uid and regno_last_uid.  */
2565
2566 static int
2567 duplicate_loop_exit_test (loop_start)
2568      rtx loop_start;
2569 {
2570   rtx insn, set, reg, p, link;
2571   rtx copy = 0;
2572   int num_insns = 0;
2573   rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
2574   rtx lastexit;
2575   int max_reg = max_reg_num ();
2576   rtx *reg_map = 0;
2577
2578   /* Scan the exit code.  We do not perform this optimization if any insn:
2579
2580          is a CALL_INSN
2581          is a CODE_LABEL
2582          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
2583          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
2584          is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
2585               is not valid.
2586
2587      We also do not do this if we find an insn with ASM_OPERANDS.  While
2588      this restriction should not be necessary, copying an insn with
2589      ASM_OPERANDS can confuse asm_noperands in some cases.
2590
2591      Also, don't do this if the exit code is more than 20 insns.  */
2592
2593   for (insn = exitcode;
2594        insn
2595        && ! (GET_CODE (insn) == NOTE
2596              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
2597        insn = NEXT_INSN (insn))
2598     {
2599       switch (GET_CODE (insn))
2600         {
2601         case CODE_LABEL:
2602         case CALL_INSN:
2603           return 0;
2604         case NOTE:
2605           /* We could be in front of the wrong NOTE_INSN_LOOP_END if there is
2606              a jump immediately after the loop start that branches outside
2607              the loop but within an outer loop, near the exit test.
2608              If we copied this exit test and created a phony
2609              NOTE_INSN_LOOP_VTOP, this could make instructions immediately
2610              before the exit test look like these could be safely moved
2611              out of the loop even if they actually may be never executed.
2612              This can be avoided by checking here for NOTE_INSN_LOOP_CONT.  */
2613
2614           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2615               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2616             return 0;
2617
2618           if (optimize < 2
2619               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2620                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
2621             /* If we were to duplicate this code, we would not move
2622                the BLOCK notes, and so debugging the moved code would
2623                be difficult.  Thus, we only move the code with -O2 or
2624                higher.  */
2625             return 0;
2626
2627           break;
2628         case JUMP_INSN:
2629         case INSN:
2630           /* The code below would grossly mishandle REG_WAS_0 notes,
2631              so get rid of them here.  */
2632           while ((p = find_reg_note (insn, REG_WAS_0, NULL_RTX)) != 0)
2633             remove_note (insn, p);
2634           if (++num_insns > 20
2635               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
2636               || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
2637               || asm_noperands (PATTERN (insn)) > 0)
2638             return 0;
2639           break;
2640         default:
2641           break;
2642         }
2643     }
2644
2645   /* Unless INSN is zero, we can do the optimization.  */
2646   if (insn == 0)
2647     return 0;
2648
2649   lastexit = insn;
2650
2651   /* See if any insn sets a register only used in the loop exit code and
2652      not a user variable.  If so, replace it with a new register.  */
2653   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2654     if (GET_CODE (insn) == INSN
2655         && (set = single_set (insn)) != 0
2656         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
2657             || (GET_CODE (reg) == SUBREG
2658                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
2659         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
2660         && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
2661       {
2662         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
2663           if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
2664             break;
2665
2666         if (p != lastexit)
2667           {
2668             /* We can do the replacement.  Allocate reg_map if this is the
2669                first replacement we found.  */
2670             if (reg_map == 0)
2671               {
2672                 reg_map = (rtx *) alloca (max_reg * sizeof (rtx));
2673                 bzero ((char *) reg_map, max_reg * sizeof (rtx));
2674               }
2675
2676             REG_LOOP_TEST_P (reg) = 1;
2677
2678             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
2679           }
2680       }
2681
2682   /* Now copy each insn.  */
2683   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2684     switch (GET_CODE (insn))
2685       {
2686       case BARRIER:
2687         copy = emit_barrier_before (loop_start);
2688         break;
2689       case NOTE:
2690         /* Only copy line-number notes.  */
2691         if (NOTE_LINE_NUMBER (insn) >= 0)
2692           {
2693             copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
2694             NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
2695           }
2696         break;
2697
2698       case INSN:
2699         copy = emit_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2700         if (reg_map)
2701           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2702
2703         mark_jump_label (PATTERN (copy), copy, 0);
2704
2705         /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
2706            make them.  */
2707         for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2708           if (REG_NOTE_KIND (link) != REG_LABEL)
2709             REG_NOTES (copy)
2710               = copy_rtx (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
2711                                              XEXP (link, 0),
2712                                              REG_NOTES (copy)));
2713         if (reg_map && REG_NOTES (copy))
2714           replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2715         break;
2716
2717       case JUMP_INSN:
2718         copy = emit_jump_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2719         if (reg_map)
2720           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2721         mark_jump_label (PATTERN (copy), copy, 0);
2722         if (REG_NOTES (insn))
2723           {
2724             REG_NOTES (copy) = copy_rtx (REG_NOTES (insn));
2725             if (reg_map)
2726               replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2727           }
2728
2729         /* If this is a simple jump, add it to the jump chain.  */
2730
2731         if (INSN_UID (copy) < max_jump_chain && JUMP_LABEL (copy)
2732             && simplejump_p (copy))
2733           {
2734             jump_chain[INSN_UID (copy)]
2735               = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2736             jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2737           }
2738         break;
2739
2740       default:
2741         abort ();
2742       }
2743
2744   /* Now clean up by emitting a jump to the end label and deleting the jump
2745      at the start of the loop.  */
2746   if (! copy || GET_CODE (copy) != BARRIER)
2747     {
2748       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
2749                                     loop_start);
2750       mark_jump_label (PATTERN (copy), copy, 0);
2751       if (INSN_UID (copy) < max_jump_chain
2752           && INSN_UID (JUMP_LABEL (copy)) < max_jump_chain)
2753         {
2754           jump_chain[INSN_UID (copy)]
2755             = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2756           jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2757         }
2758       emit_barrier_before (loop_start);
2759     }
2760
2761   /* Mark the exit code as the virtual top of the converted loop.  */
2762   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
2763
2764   delete_insn (next_nonnote_insn (loop_start));
2765
2766   return 1;
2767 }
2768 \f
2769 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, and
2770    loop-end notes between START and END out before START.  Assume that
2771    END is not such a note.  START may be such a note.  Returns the value
2772    of the new starting insn, which may be different if the original start
2773    was such a note.  */
2774
2775 rtx
2776 squeeze_notes (start, end)
2777      rtx start, end;
2778 {
2779   rtx insn;
2780   rtx next;
2781
2782   for (insn = start; insn != end; insn = next)
2783     {
2784       next = NEXT_INSN (insn);
2785       if (GET_CODE (insn) == NOTE
2786           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
2787               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2788               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2789               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
2790               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
2791               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
2792         {
2793           if (insn == start)
2794             start = next;
2795           else
2796             {
2797               rtx prev = PREV_INSN (insn);
2798               PREV_INSN (insn) = PREV_INSN (start);
2799               NEXT_INSN (insn) = start;
2800               NEXT_INSN (PREV_INSN (insn)) = insn;
2801               PREV_INSN (NEXT_INSN (insn)) = insn;
2802               NEXT_INSN (prev) = next;
2803               PREV_INSN (next) = prev;
2804             }
2805         }
2806     }
2807
2808   return start;
2809 }
2810 \f
2811 /* Compare the instructions before insn E1 with those before E2
2812    to find an opportunity for cross jumping.
2813    (This means detecting identical sequences of insns followed by
2814    jumps to the same place, or followed by a label and a jump
2815    to that label, and replacing one with a jump to the other.)
2816
2817    Assume E1 is a jump that jumps to label E2
2818    (that is not always true but it might as well be).
2819    Find the longest possible equivalent sequences
2820    and store the first insns of those sequences into *F1 and *F2.
2821    Store zero there if no equivalent preceding instructions are found.
2822
2823    We give up if we find a label in stream 1.
2824    Actually we could transfer that label into stream 2.  */
2825
2826 static void
2827 find_cross_jump (e1, e2, minimum, f1, f2)
2828      rtx e1, e2;
2829      int minimum;
2830      rtx *f1, *f2;
2831 {
2832   register rtx i1 = e1, i2 = e2;
2833   register rtx p1, p2;
2834   int lose = 0;
2835
2836   rtx last1 = 0, last2 = 0;
2837   rtx afterlast1 = 0, afterlast2 = 0;
2838
2839   *f1 = 0;
2840   *f2 = 0;
2841
2842   while (1)
2843     {
2844       i1 = prev_nonnote_insn (i1);
2845
2846       i2 = PREV_INSN (i2);
2847       while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
2848         i2 = PREV_INSN (i2);
2849
2850       if (i1 == 0)
2851         break;
2852
2853       /* Don't allow the range of insns preceding E1 or E2
2854          to include the other (E2 or E1).  */
2855       if (i2 == e1 || i1 == e2)
2856         break;
2857
2858       /* If we will get to this code by jumping, those jumps will be
2859          tensioned to go directly to the new label (before I2),
2860          so this cross-jumping won't cost extra.  So reduce the minimum.  */
2861       if (GET_CODE (i1) == CODE_LABEL)
2862         {
2863           --minimum;
2864           break;
2865         }
2866
2867       if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
2868         break;
2869
2870       /* Avoid moving insns across EH regions if either of the insns
2871          can throw.  */
2872       if (flag_exceptions
2873           && (asynchronous_exceptions || GET_CODE (i1) == CALL_INSN)
2874           && !in_same_eh_region (i1, i2))
2875         break;
2876
2877       p1 = PATTERN (i1);
2878       p2 = PATTERN (i2);
2879
2880       /* If this is a CALL_INSN, compare register usage information.
2881          If we don't check this on stack register machines, the two
2882          CALL_INSNs might be merged leaving reg-stack.c with mismatching
2883          numbers of stack registers in the same basic block.
2884          If we don't check this on machines with delay slots, a delay slot may
2885          be filled that clobbers a parameter expected by the subroutine.
2886
2887          ??? We take the simple route for now and assume that if they're
2888          equal, they were constructed identically.  */
2889
2890       if (GET_CODE (i1) == CALL_INSN
2891           && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
2892                             CALL_INSN_FUNCTION_USAGE (i2)))
2893         lose = 1;
2894
2895 #ifdef STACK_REGS
2896       /* If cross_jump_death_matters is not 0, the insn's mode
2897          indicates whether or not the insn contains any stack-like
2898          regs.  */
2899
2900       if (!lose && cross_jump_death_matters && stack_regs_mentioned (i1))
2901         {
2902           /* If register stack conversion has already been done, then
2903              death notes must also be compared before it is certain that
2904              the two instruction streams match.  */
2905
2906           rtx note;
2907           HARD_REG_SET i1_regset, i2_regset;
2908
2909           CLEAR_HARD_REG_SET (i1_regset);
2910           CLEAR_HARD_REG_SET (i2_regset);
2911
2912           for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
2913             if (REG_NOTE_KIND (note) == REG_DEAD
2914                 && STACK_REG_P (XEXP (note, 0)))
2915               SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
2916
2917           for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
2918             if (REG_NOTE_KIND (note) == REG_DEAD
2919                 && STACK_REG_P (XEXP (note, 0)))
2920               SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
2921
2922           GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
2923
2924           lose = 1;
2925
2926         done:
2927           ;
2928         }
2929 #endif
2930
2931       /* Don't allow old-style asm or volatile extended asms to be accepted
2932          for cross jumping purposes.  It is conceptually correct to allow
2933          them, since cross-jumping preserves the dynamic instruction order
2934          even though it is changing the static instruction order.  However,
2935          if an asm is being used to emit an assembler pseudo-op, such as
2936          the MIPS `.set reorder' pseudo-op, then the static instruction order
2937          matters and it must be preserved.  */
2938       if (GET_CODE (p1) == ASM_INPUT || GET_CODE (p2) == ASM_INPUT
2939           || (GET_CODE (p1) == ASM_OPERANDS && MEM_VOLATILE_P (p1))
2940           || (GET_CODE (p2) == ASM_OPERANDS && MEM_VOLATILE_P (p2)))
2941         lose = 1;
2942
2943       if (lose || GET_CODE (p1) != GET_CODE (p2)
2944           || ! rtx_renumbered_equal_p (p1, p2))
2945         {
2946           /* The following code helps take care of G++ cleanups.  */
2947           rtx equiv1;
2948           rtx equiv2;
2949
2950           if (!lose && GET_CODE (p1) == GET_CODE (p2)
2951               && ((equiv1 = find_reg_note (i1, REG_EQUAL, NULL_RTX)) != 0
2952                   || (equiv1 = find_reg_note (i1, REG_EQUIV, NULL_RTX)) != 0)
2953               && ((equiv2 = find_reg_note (i2, REG_EQUAL, NULL_RTX)) != 0
2954                   || (equiv2 = find_reg_note (i2, REG_EQUIV, NULL_RTX)) != 0)
2955               /* If the equivalences are not to a constant, they may
2956                  reference pseudos that no longer exist, so we can't
2957                  use them.  */
2958               && CONSTANT_P (XEXP (equiv1, 0))
2959               && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
2960             {
2961               rtx s1 = single_set (i1);
2962               rtx s2 = single_set (i2);
2963               if (s1 != 0 && s2 != 0
2964                   && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
2965                 {
2966                   validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
2967                   validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
2968                   if (! rtx_renumbered_equal_p (p1, p2))
2969                     cancel_changes (0);
2970                   else if (apply_change_group ())
2971                     goto win;
2972                 }
2973             }
2974
2975           /* Insns fail to match; cross jumping is limited to the following
2976              insns.  */
2977
2978 #ifdef HAVE_cc0
2979           /* Don't allow the insn after a compare to be shared by
2980              cross-jumping unless the compare is also shared.
2981              Here, if either of these non-matching insns is a compare,
2982              exclude the following insn from possible cross-jumping.  */
2983           if (sets_cc0_p (p1) || sets_cc0_p (p2))
2984             last1 = afterlast1, last2 = afterlast2, ++minimum;
2985 #endif
2986
2987           /* If cross-jumping here will feed a jump-around-jump
2988              optimization, this jump won't cost extra, so reduce
2989              the minimum.  */
2990           if (GET_CODE (i1) == JUMP_INSN
2991               && JUMP_LABEL (i1)
2992               && prev_real_insn (JUMP_LABEL (i1)) == e1)
2993             --minimum;
2994           break;
2995         }
2996
2997     win:
2998       if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
2999         {
3000           /* Ok, this insn is potentially includable in a cross-jump here.  */
3001           afterlast1 = last1, afterlast2 = last2;
3002           last1 = i1, last2 = i2, --minimum;
3003         }
3004     }
3005
3006   if (minimum <= 0 && last1 != 0 && last1 != e1)
3007     *f1 = last1, *f2 = last2;
3008 }
3009
3010 static void
3011 do_cross_jump (insn, newjpos, newlpos)
3012      rtx insn, newjpos, newlpos;
3013 {
3014   /* Find an existing label at this point
3015      or make a new one if there is none.  */
3016   register rtx label = get_label_before (newlpos);
3017
3018   /* Make the same jump insn jump to the new point.  */
3019   if (GET_CODE (PATTERN (insn)) == RETURN)
3020     {
3021       /* Remove from jump chain of returns.  */
3022       delete_from_jump_chain (insn);
3023       /* Change the insn.  */
3024       PATTERN (insn) = gen_jump (label);
3025       INSN_CODE (insn) = -1;
3026       JUMP_LABEL (insn) = label;
3027       LABEL_NUSES (label)++;
3028       /* Add to new the jump chain.  */
3029       if (INSN_UID (label) < max_jump_chain
3030           && INSN_UID (insn) < max_jump_chain)
3031         {
3032           jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (label)];
3033           jump_chain[INSN_UID (label)] = insn;
3034         }
3035     }
3036   else
3037     redirect_jump (insn, label);
3038
3039   /* Delete the matching insns before the jump.  Also, remove any REG_EQUAL
3040      or REG_EQUIV note in the NEWLPOS stream that isn't also present in
3041      the NEWJPOS stream.  */
3042
3043   while (newjpos != insn)
3044     {
3045       rtx lnote;
3046
3047       for (lnote = REG_NOTES (newlpos); lnote; lnote = XEXP (lnote, 1))
3048         if ((REG_NOTE_KIND (lnote) == REG_EQUAL
3049              || REG_NOTE_KIND (lnote) == REG_EQUIV)
3050             && ! find_reg_note (newjpos, REG_EQUAL, XEXP (lnote, 0))
3051             && ! find_reg_note (newjpos, REG_EQUIV, XEXP (lnote, 0)))
3052           remove_note (newlpos, lnote);
3053
3054       delete_insn (newjpos);
3055       newjpos = next_real_insn (newjpos);
3056       newlpos = next_real_insn (newlpos);
3057     }
3058 }
3059 \f
3060 /* Return the label before INSN, or put a new label there.  */
3061
3062 rtx
3063 get_label_before (insn)
3064      rtx insn;
3065 {
3066   rtx label;
3067
3068   /* Find an existing label at this point
3069      or make a new one if there is none.  */
3070   label = prev_nonnote_insn (insn);
3071
3072   if (label == 0 || GET_CODE (label) != CODE_LABEL)
3073     {
3074       rtx prev = PREV_INSN (insn);
3075
3076       label = gen_label_rtx ();
3077       emit_label_after (label, prev);
3078       LABEL_NUSES (label) = 0;
3079     }
3080   return label;
3081 }
3082
3083 /* Return the label after INSN, or put a new label there.  */
3084
3085 rtx
3086 get_label_after (insn)
3087      rtx insn;
3088 {
3089   rtx label;
3090
3091   /* Find an existing label at this point
3092      or make a new one if there is none.  */
3093   label = next_nonnote_insn (insn);
3094
3095   if (label == 0 || GET_CODE (label) != CODE_LABEL)
3096     {
3097       label = gen_label_rtx ();
3098       emit_label_after (label, insn);
3099       LABEL_NUSES (label) = 0;
3100     }
3101   return label;
3102 }
3103 \f
3104 /* Return 1 if INSN is a jump that jumps to right after TARGET
3105    only on the condition that TARGET itself would drop through.
3106    Assumes that TARGET is a conditional jump.  */
3107
3108 static int
3109 jump_back_p (insn, target)
3110      rtx insn, target;
3111 {
3112   rtx cinsn, ctarget;
3113   enum rtx_code codei, codet;
3114
3115   if (simplejump_p (insn) || ! condjump_p (insn)
3116       || simplejump_p (target)
3117       || target != prev_real_insn (JUMP_LABEL (insn)))
3118     return 0;
3119
3120   cinsn = XEXP (SET_SRC (PATTERN (insn)), 0);
3121   ctarget = XEXP (SET_SRC (PATTERN (target)), 0);
3122
3123   codei = GET_CODE (cinsn);
3124   codet = GET_CODE (ctarget);
3125
3126   if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx)
3127     {
3128       if (! can_reverse_comparison_p (cinsn, insn))
3129         return 0;
3130       codei = reverse_condition (codei);
3131     }
3132
3133   if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx)
3134     {
3135       if (! can_reverse_comparison_p (ctarget, target))
3136         return 0;
3137       codet = reverse_condition (codet);
3138     }
3139
3140   return (codei == codet
3141           && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
3142           && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
3143 }
3144 \f
3145 /* Given a comparison, COMPARISON, inside a conditional jump insn, INSN,
3146    return non-zero if it is safe to reverse this comparison.  It is if our
3147    floating-point is not IEEE, if this is an NE or EQ comparison, or if
3148    this is known to be an integer comparison.  */
3149
3150 int
3151 can_reverse_comparison_p (comparison, insn)
3152      rtx comparison;
3153      rtx insn;
3154 {
3155   rtx arg0;
3156
3157   /* If this is not actually a comparison, we can't reverse it.  */
3158   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
3159     return 0;
3160
3161   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3162       /* If this is an NE comparison, it is safe to reverse it to an EQ
3163          comparison and vice versa, even for floating point.  If no operands
3164          are NaNs, the reversal is valid.  If some operand is a NaN, EQ is
3165          always false and NE is always true, so the reversal is also valid.  */
3166       || flag_fast_math
3167       || GET_CODE (comparison) == NE
3168       || GET_CODE (comparison) == EQ)
3169     return 1;
3170
3171   arg0 = XEXP (comparison, 0);
3172
3173   /* Make sure ARG0 is one of the actual objects being compared.  If we
3174      can't do this, we can't be sure the comparison can be reversed.
3175
3176      Handle cc0 and a MODE_CC register.  */
3177   if ((GET_CODE (arg0) == REG && GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC)
3178 #ifdef HAVE_cc0
3179       || arg0 == cc0_rtx
3180 #endif
3181       )
3182     {
3183       rtx prev = prev_nonnote_insn (insn);
3184       rtx set;
3185
3186       /* If the comparison itself was a loop invariant, it could have been
3187          hoisted out of the loop.  If we proceed to unroll such a loop, then
3188          we may not be able to find the comparison when copying the loop.
3189
3190          Returning zero in that case is the safe thing to do.  */
3191       if (prev == 0)
3192         return 0;
3193
3194       set = single_set (prev);
3195       if (set == 0 || SET_DEST (set) != arg0)
3196         return 0;
3197
3198       arg0 = SET_SRC (set);
3199
3200       if (GET_CODE (arg0) == COMPARE)
3201         arg0 = XEXP (arg0, 0);
3202     }
3203
3204   /* We can reverse this if ARG0 is a CONST_INT or if its mode is
3205      not VOIDmode and neither a MODE_CC nor MODE_FLOAT type.  */
3206   return (GET_CODE (arg0) == CONST_INT
3207           || (GET_MODE (arg0) != VOIDmode
3208               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_CC
3209               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_FLOAT));
3210 }
3211
3212 /* Given an rtx-code for a comparison, return the code
3213    for the negated comparison.
3214    WATCH OUT!  reverse_condition is not safe to use on a jump
3215    that might be acting on the results of an IEEE floating point comparison,
3216    because of the special treatment of non-signaling nans in comparisons.
3217    Use can_reverse_comparison_p to be sure.  */
3218
3219 enum rtx_code
3220 reverse_condition (code)
3221      enum rtx_code code;
3222 {
3223   switch (code)
3224     {
3225     case EQ:
3226       return NE;
3227
3228     case NE:
3229       return EQ;
3230
3231     case GT:
3232       return LE;
3233
3234     case GE:
3235       return LT;
3236
3237     case LT:
3238       return GE;
3239
3240     case LE:
3241       return GT;
3242
3243     case GTU:
3244       return LEU;
3245
3246     case GEU:
3247       return LTU;
3248
3249     case LTU:
3250       return GEU;
3251
3252     case LEU:
3253       return GTU;
3254
3255     default:
3256       abort ();
3257       return UNKNOWN;
3258     }
3259 }
3260
3261 /* Similar, but return the code when two operands of a comparison are swapped.
3262    This IS safe for IEEE floating-point.  */
3263
3264 enum rtx_code
3265 swap_condition (code)
3266      enum rtx_code code;
3267 {
3268   switch (code)
3269     {
3270     case EQ:
3271     case NE:
3272       return code;
3273
3274     case GT:
3275       return LT;
3276
3277     case GE:
3278       return LE;
3279
3280     case LT:
3281       return GT;
3282
3283     case LE:
3284       return GE;
3285
3286     case GTU:
3287       return LTU;
3288
3289     case GEU:
3290       return LEU;
3291
3292     case LTU:
3293       return GTU;
3294
3295     case LEU:
3296       return GEU;
3297
3298     default:
3299       abort ();
3300       return UNKNOWN;
3301     }
3302 }
3303
3304 /* Given a comparison CODE, return the corresponding unsigned comparison.
3305    If CODE is an equality comparison or already an unsigned comparison,
3306    CODE is returned.  */
3307
3308 enum rtx_code
3309 unsigned_condition (code)
3310      enum rtx_code code;
3311 {
3312   switch (code)
3313     {
3314     case EQ:
3315     case NE:
3316     case GTU:
3317     case GEU:
3318     case LTU:
3319     case LEU:
3320       return code;
3321
3322     case GT:
3323       return GTU;
3324
3325     case GE:
3326       return GEU;
3327
3328     case LT:
3329       return LTU;
3330
3331     case LE:
3332       return LEU;
3333
3334     default:
3335       abort ();
3336     }
3337 }
3338
3339 /* Similarly, return the signed version of a comparison.  */
3340
3341 enum rtx_code
3342 signed_condition (code)
3343      enum rtx_code code;
3344 {
3345   switch (code)
3346     {
3347     case EQ:
3348     case NE:
3349     case GT:
3350     case GE:
3351     case LT:
3352     case LE:
3353       return code;
3354
3355     case GTU:
3356       return GT;
3357
3358     case GEU:
3359       return GE;
3360
3361     case LTU:
3362       return LT;
3363
3364     case LEU:
3365       return LE;
3366
3367     default:
3368       abort ();
3369     }
3370 }
3371 \f
3372 /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
3373    truth of CODE1 implies the truth of CODE2.  */
3374
3375 int
3376 comparison_dominates_p (code1, code2)
3377      enum rtx_code code1, code2;
3378 {
3379   if (code1 == code2)
3380     return 1;
3381
3382   switch (code1)
3383     {
3384     case EQ:
3385       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU)
3386         return 1;
3387       break;
3388
3389     case LT:
3390       if (code2 == LE || code2 == NE)
3391         return 1;
3392       break;
3393
3394     case GT:
3395       if (code2 == GE || code2 == NE)
3396         return 1;
3397       break;
3398
3399     case LTU:
3400       if (code2 == LEU || code2 == NE)
3401         return 1;
3402       break;
3403
3404     case GTU:
3405       if (code2 == GEU || code2 == NE)
3406         return 1;
3407       break;
3408
3409     default:
3410       break;
3411     }
3412
3413   return 0;
3414 }
3415 \f
3416 /* Return 1 if INSN is an unconditional jump and nothing else.  */
3417
3418 int
3419 simplejump_p (insn)
3420      rtx insn;
3421 {
3422   return (GET_CODE (insn) == JUMP_INSN
3423           && GET_CODE (PATTERN (insn)) == SET
3424           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
3425           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
3426 }
3427
3428 /* Return nonzero if INSN is a (possibly) conditional jump
3429    and nothing more.  */
3430
3431 int
3432 condjump_p (insn)
3433      rtx insn;
3434 {
3435   register rtx x = PATTERN (insn);
3436   if (GET_CODE (x) != SET)
3437     return 0;
3438   if (GET_CODE (SET_DEST (x)) != PC)
3439     return 0;
3440   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
3441     return 1;
3442   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
3443     return 0;
3444   if (XEXP (SET_SRC (x), 2) == pc_rtx
3445       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
3446           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
3447     return 1;
3448   if (XEXP (SET_SRC (x), 1) == pc_rtx
3449       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
3450           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
3451     return 1;
3452   return 0;
3453 }
3454
3455 /* Return nonzero if INSN is a (possibly) conditional jump
3456    and nothing more.  */
3457
3458 int
3459 condjump_in_parallel_p (insn)
3460      rtx insn;
3461 {
3462   register rtx x = PATTERN (insn);
3463
3464   if (GET_CODE (x) != PARALLEL)
3465     return 0;
3466   else
3467     x = XVECEXP (x, 0, 0);
3468
3469   if (GET_CODE (x) != SET)
3470     return 0;
3471   if (GET_CODE (SET_DEST (x)) != PC)
3472     return 0;
3473   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
3474     return 1;
3475   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
3476     return 0;
3477   if (XEXP (SET_SRC (x), 2) == pc_rtx
3478       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
3479           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
3480     return 1;
3481   if (XEXP (SET_SRC (x), 1) == pc_rtx
3482       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
3483           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
3484     return 1;
3485   return 0;
3486 }
3487
3488 /* Return the label of a conditional jump.  */
3489
3490 rtx
3491 condjump_label (insn)
3492      rtx insn;
3493 {
3494   register rtx x = PATTERN (insn);
3495
3496   if (GET_CODE (x) == PARALLEL)
3497     x = XVECEXP (x, 0, 0);
3498   if (GET_CODE (x) != SET)
3499     return NULL_RTX;
3500   if (GET_CODE (SET_DEST (x)) != PC)
3501     return NULL_RTX;
3502   x = SET_SRC (x);
3503   if (GET_CODE (x) == LABEL_REF)
3504     return x;
3505   if (GET_CODE (x) != IF_THEN_ELSE)
3506     return NULL_RTX;
3507   if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
3508     return XEXP (x, 1);
3509   if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
3510     return XEXP (x, 2);
3511   return NULL_RTX;
3512 }
3513
3514 /* Return true if INSN is a (possibly conditional) return insn.  */
3515
3516 static int
3517 returnjump_p_1 (loc, data)
3518      rtx *loc;
3519      void *data ATTRIBUTE_UNUSED;
3520 {
3521   rtx x = *loc;
3522   return GET_CODE (x) == RETURN;
3523 }
3524
3525 int
3526 returnjump_p (insn)
3527      rtx insn;
3528 {
3529   return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
3530 }
3531
3532 /* Return true if INSN is a jump that only transfers control and
3533    nothing more.  */
3534
3535 int
3536 onlyjump_p (insn)
3537      rtx insn;
3538 {
3539   rtx set;
3540
3541   if (GET_CODE (insn) != JUMP_INSN)
3542     return 0;
3543
3544   set = single_set (insn);
3545   if (set == NULL)
3546     return 0;
3547   if (GET_CODE (SET_DEST (set)) != PC)
3548     return 0;
3549   if (side_effects_p (SET_SRC (set)))
3550     return 0;
3551
3552   return 1;
3553 }
3554
3555 #ifdef HAVE_cc0
3556
3557 /* Return 1 if X is an RTX that does nothing but set the condition codes
3558    and CLOBBER or USE registers.
3559    Return -1 if X does explicitly set the condition codes,
3560    but also does other things.  */
3561
3562 int
3563 sets_cc0_p (x)
3564      rtx x ATTRIBUTE_UNUSED;
3565 {
3566   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
3567     return 1;
3568   if (GET_CODE (x) == PARALLEL)
3569     {
3570       int i;
3571       int sets_cc0 = 0;
3572       int other_things = 0;
3573       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3574         {
3575           if (GET_CODE (XVECEXP (x, 0, i)) == SET
3576               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
3577             sets_cc0 = 1;
3578           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
3579             other_things = 1;
3580         }
3581       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
3582     }
3583   return 0;
3584 }
3585 #endif
3586 \f
3587 /* Follow any unconditional jump at LABEL;
3588    return the ultimate label reached by any such chain of jumps.
3589    If LABEL is not followed by a jump, return LABEL.
3590    If the chain loops or we can't find end, return LABEL,
3591    since that tells caller to avoid changing the insn.
3592
3593    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
3594    a USE or CLOBBER.  */
3595
3596 rtx
3597 follow_jumps (label)
3598      rtx label;
3599 {
3600   register rtx insn;
3601   register rtx next;
3602   register rtx value = label;
3603   register int depth;
3604
3605   for (depth = 0;
3606        (depth < 10
3607         && (insn = next_active_insn (value)) != 0
3608         && GET_CODE (insn) == JUMP_INSN
3609         && ((JUMP_LABEL (insn) != 0 && simplejump_p (insn))
3610             || GET_CODE (PATTERN (insn)) == RETURN)
3611         && (next = NEXT_INSN (insn))
3612         && GET_CODE (next) == BARRIER);
3613        depth++)
3614     {
3615       /* Don't chain through the insn that jumps into a loop
3616          from outside the loop,
3617          since that would create multiple loop entry jumps
3618          and prevent loop optimization.  */
3619       rtx tem;
3620       if (!reload_completed)
3621         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
3622           if (GET_CODE (tem) == NOTE
3623               && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
3624                   /* ??? Optional.  Disables some optimizations, but makes
3625                      gcov output more accurate with -O.  */
3626                   || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
3627             return value;
3628
3629       /* If we have found a cycle, make the insn jump to itself.  */
3630       if (JUMP_LABEL (insn) == label)
3631         return label;
3632
3633       tem = next_active_insn (JUMP_LABEL (insn));
3634       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
3635                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
3636         break;
3637
3638       value = JUMP_LABEL (insn);
3639     }
3640   if (depth == 10)
3641     return label;
3642   return value;
3643 }
3644
3645 /* Assuming that field IDX of X is a vector of label_refs,
3646    replace each of them by the ultimate label reached by it.
3647    Return nonzero if a change is made.
3648    If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG.  */
3649
3650 static int
3651 tension_vector_labels (x, idx)
3652      register rtx x;
3653      register int idx;
3654 {
3655   int changed = 0;
3656   register int i;
3657   for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
3658     {
3659       register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
3660       register rtx nlabel = follow_jumps (olabel);
3661       if (nlabel && nlabel != olabel)
3662         {
3663           XEXP (XVECEXP (x, idx, i), 0) = nlabel;
3664           ++LABEL_NUSES (nlabel);
3665           if (--LABEL_NUSES (olabel) == 0)
3666             delete_insn (olabel);
3667           changed = 1;
3668         }
3669     }
3670   return changed;
3671 }
3672 \f
3673 /* Find all CODE_LABELs referred to in X, and increment their use counts.
3674    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
3675    in INSN, then store one of them in JUMP_LABEL (INSN).
3676    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
3677    referenced in INSN, add a REG_LABEL note containing that label to INSN.
3678    Also, when there are consecutive labels, canonicalize on the last of them.
3679
3680    Note that two labels separated by a loop-beginning note
3681    must be kept distinct if we have not yet done loop-optimization,
3682    because the gap between them is where loop-optimize
3683    will want to move invariant code to.  CROSS_JUMP tells us
3684    that loop-optimization is done with.
3685
3686    Once reload has completed (CROSS_JUMP non-zero), we need not consider
3687    two labels distinct if they are separated by only USE or CLOBBER insns.  */
3688
3689 static void
3690 mark_jump_label (x, insn, cross_jump)
3691      register rtx x;
3692      rtx insn;
3693      int cross_jump;
3694 {
3695   register RTX_CODE code = GET_CODE (x);
3696   register int i;
3697   register const char *fmt;
3698
3699   switch (code)
3700     {
3701     case PC:
3702     case CC0:
3703     case REG:
3704     case SUBREG:
3705     case CONST_INT:
3706     case SYMBOL_REF:
3707     case CONST_DOUBLE:
3708     case CLOBBER:
3709     case CALL:
3710       return;
3711
3712     case MEM:
3713       /* If this is a constant-pool reference, see if it is a label.  */
3714       if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
3715           && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
3716         mark_jump_label (get_pool_constant (XEXP (x, 0)), insn, cross_jump);
3717       break;
3718
3719     case LABEL_REF:
3720       {
3721         rtx label = XEXP (x, 0);
3722         rtx olabel = label;
3723         rtx note;
3724         rtx next;
3725
3726         if (GET_CODE (label) != CODE_LABEL)
3727           abort ();
3728
3729         /* Ignore references to labels of containing functions.  */
3730         if (LABEL_REF_NONLOCAL_P (x))
3731           break;
3732
3733         /* If there are other labels following this one,
3734            replace it with the last of the consecutive labels.  */
3735         for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
3736           {
3737             if (GET_CODE (next) == CODE_LABEL)
3738               label = next;
3739             else if (cross_jump && GET_CODE (next) == INSN
3740                      && (GET_CODE (PATTERN (next)) == USE
3741                          || GET_CODE (PATTERN (next)) == CLOBBER))
3742               continue;
3743             else if (GET_CODE (next) != NOTE)
3744               break;
3745             else if (! cross_jump
3746                      && (NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
3747                          || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END
3748                          /* ??? Optional.  Disables some optimizations, but
3749                             makes gcov output more accurate with -O.  */
3750                          || (flag_test_coverage && NOTE_LINE_NUMBER (next) > 0)))
3751               break;
3752           }
3753
3754         XEXP (x, 0) = label;
3755         if (! insn || ! INSN_DELETED_P (insn))
3756           ++LABEL_NUSES (label);
3757
3758         if (insn)
3759           {
3760             if (GET_CODE (insn) == JUMP_INSN)
3761               JUMP_LABEL (insn) = label;
3762
3763             /* If we've changed OLABEL and we had a REG_LABEL note
3764                for it, update it as well.  */
3765             else if (label != olabel
3766                      && (note = find_reg_note (insn, REG_LABEL, olabel)) != 0)
3767               XEXP (note, 0) = label;
3768
3769             /* Otherwise, add a REG_LABEL note for LABEL unless there already
3770                is one.  */
3771             else if (! find_reg_note (insn, REG_LABEL, label))
3772               {
3773                 /* This code used to ignore labels which refered to dispatch
3774                    tables to avoid flow.c generating worse code.
3775
3776                    However, in the presense of global optimizations like
3777                    gcse which call find_basic_blocks without calling
3778                    life_analysis, not recording such labels will lead
3779                    to compiler aborts because of inconsistencies in the
3780                    flow graph.  So we go ahead and record the label.
3781
3782                    It may also be the case that the optimization argument
3783                    is no longer valid because of the more accurate cfg
3784                    we build in find_basic_blocks -- it no longer pessimizes
3785                    code when it finds a REG_LABEL note.  */
3786                 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, label,
3787                                                       REG_NOTES (insn));
3788               }
3789           }
3790         return;
3791       }
3792
3793   /* Do walk the labels in a vector, but not the first operand of an
3794      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
3795     case ADDR_VEC:
3796     case ADDR_DIFF_VEC:
3797       if (! INSN_DELETED_P (insn))
3798         {
3799           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
3800
3801           for (i = 0; i < XVECLEN (x, eltnum); i++)
3802             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, cross_jump);
3803         }
3804       return;
3805
3806     default:
3807       break;
3808     }
3809
3810   fmt = GET_RTX_FORMAT (code);
3811   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3812     {
3813       if (fmt[i] == 'e')
3814         mark_jump_label (XEXP (x, i), insn, cross_jump);
3815       else if (fmt[i] == 'E')
3816         {
3817           register int j;
3818           for (j = 0; j < XVECLEN (x, i); j++)
3819             mark_jump_label (XVECEXP (x, i, j), insn, cross_jump);
3820         }
3821     }
3822 }
3823
3824 /* If all INSN does is set the pc, delete it,
3825    and delete the insn that set the condition codes for it
3826    if that's what the previous thing was.  */
3827
3828 void
3829 delete_jump (insn)
3830      rtx insn;
3831 {
3832   register rtx set = single_set (insn);
3833
3834   if (set && GET_CODE (SET_DEST (set)) == PC)
3835     delete_computation (insn);
3836 }
3837
3838 /* Recursively delete prior insns that compute the value (used only by INSN
3839    which the caller is deleting) stored in the register mentioned by NOTE
3840    which is a REG_DEAD note associated with INSN.  */
3841
3842 static void
3843 delete_prior_computation (note, insn)
3844      rtx note;
3845      rtx insn;
3846 {
3847   rtx our_prev;
3848   rtx reg = XEXP (note, 0);
3849
3850   for (our_prev = prev_nonnote_insn (insn);
3851        our_prev && GET_CODE (our_prev) == INSN;
3852        our_prev = prev_nonnote_insn (our_prev))
3853     {
3854       rtx pat = PATTERN (our_prev);
3855
3856       /* If we reach a SEQUENCE, it is too complex to try to
3857          do anything with it, so give up.  */
3858       if (GET_CODE (pat) == SEQUENCE)
3859         break;
3860
3861       if (GET_CODE (pat) == USE
3862           && GET_CODE (XEXP (pat, 0)) == INSN)
3863         /* reorg creates USEs that look like this.  We leave them
3864            alone because reorg needs them for its own purposes.  */
3865         break;
3866
3867       if (reg_set_p (reg, pat))
3868         {
3869           if (side_effects_p (pat))
3870             break;
3871
3872           if (GET_CODE (pat) == PARALLEL)
3873             {
3874               /* If we find a SET of something else, we can't
3875                  delete the insn.  */
3876
3877               int i;
3878
3879               for (i = 0; i < XVECLEN (pat, 0); i++)
3880                 {
3881                   rtx part = XVECEXP (pat, 0, i);
3882
3883                   if (GET_CODE (part) == SET
3884                       && SET_DEST (part) != reg)
3885                     break;
3886                 }
3887
3888               if (i == XVECLEN (pat, 0))
3889                 delete_computation (our_prev);
3890             }
3891           else if (GET_CODE (pat) == SET
3892                    && GET_CODE (SET_DEST (pat)) == REG)
3893             {
3894               int dest_regno = REGNO (SET_DEST (pat));
3895               int dest_endregno
3896                     = dest_regno + (dest_regno < FIRST_PSEUDO_REGISTER
3897                       ? HARD_REGNO_NREGS (dest_regno,
3898                                 GET_MODE (SET_DEST (pat))) : 1);
3899               int regno = REGNO (reg);
3900               int endregno = regno + (regno < FIRST_PSEUDO_REGISTER
3901                              ? HARD_REGNO_NREGS (regno, GET_MODE (reg)) : 1);
3902
3903               if (dest_regno >= regno
3904                   && dest_endregno <= endregno)
3905                 delete_computation (our_prev);
3906
3907               /* We may have a multi-word hard register and some, but not
3908                  all, of the words of the register are needed in subsequent
3909                  insns.  Write REG_UNUSED notes for those parts that were not
3910                  needed.  */
3911               else if (dest_regno <= regno
3912                        && dest_endregno >= endregno
3913                        && ! find_regno_note (our_prev, REG_UNUSED, REGNO(reg)))
3914                 {
3915                   int i;
3916
3917                   REG_NOTES (our_prev)
3918                     = gen_rtx_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (our_prev));
3919
3920                   for (i = dest_regno; i < dest_endregno; i++)
3921                     if (! find_regno_note (our_prev, REG_UNUSED, i))
3922                       break;
3923
3924                   if (i == dest_endregno)
3925                     delete_computation (our_prev);
3926                 }
3927             }
3928
3929           break;
3930         }
3931
3932       /* If PAT references the register that dies here, it is an
3933          additional use.  Hence any prior SET isn't dead.  However, this
3934          insn becomes the new place for the REG_DEAD note.  */
3935       if (reg_overlap_mentioned_p (reg, pat))
3936         {
3937           XEXP (note, 1) = REG_NOTES (our_prev);
3938           REG_NOTES (our_prev) = note;
3939           break;
3940         }
3941     }
3942 }
3943
3944 /* Delete INSN and recursively delete insns that compute values used only
3945    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
3946    If we are running before flow.c, we need do nothing since flow.c will
3947    delete dead code.  We also can't know if the registers being used are
3948    dead or not at this point.
3949
3950    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
3951    nothing other than set a register that dies in this insn, we can delete
3952    that insn as well.
3953
3954    On machines with CC0, if CC0 is used in this insn, we may be able to
3955    delete the insn that set it.  */
3956
3957 static void
3958 delete_computation (insn)
3959      rtx insn;
3960 {
3961   rtx note, next;
3962   rtx set;
3963
3964 #ifdef HAVE_cc0
3965   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
3966     {
3967       rtx prev = prev_nonnote_insn (insn);
3968       /* We assume that at this stage
3969          CC's are always set explicitly
3970          and always immediately before the jump that
3971          will use them.  So if the previous insn
3972          exists to set the CC's, delete it
3973          (unless it performs auto-increments, etc.).  */
3974       if (prev && GET_CODE (prev) == INSN
3975           && sets_cc0_p (PATTERN (prev)))
3976         {
3977           if (sets_cc0_p (PATTERN (prev)) > 0
3978               && ! side_effects_p (PATTERN (prev)))
3979             delete_computation (prev);
3980           else
3981             /* Otherwise, show that cc0 won't be used.  */
3982             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
3983                                                   cc0_rtx, REG_NOTES (prev));
3984         }
3985     }
3986 #endif
3987
3988 #ifdef INSN_SCHEDULING
3989   /* ?!? The schedulers do not keep REG_DEAD notes accurate after
3990      reload has completed.  The schedulers need to be fixed.  Until
3991      they are, we must not rely on the death notes here.  */
3992   if (reload_completed && flag_schedule_insns_after_reload)
3993     {
3994       delete_insn (insn);
3995       return;
3996     }
3997 #endif
3998
3999   set = single_set (insn);
4000
4001   for (note = REG_NOTES (insn); note; note = next)
4002     {
4003       next = XEXP (note, 1);
4004
4005       if (REG_NOTE_KIND (note) != REG_DEAD
4006           /* Verify that the REG_NOTE is legitimate.  */
4007           || GET_CODE (XEXP (note, 0)) != REG)
4008         continue;
4009
4010       if (set && reg_overlap_mentioned_p (SET_DEST (set), XEXP (note, 0)))
4011         set = NULL_RTX;
4012
4013       delete_prior_computation (note, insn);
4014     }
4015
4016   /* The REG_DEAD note may have been omitted for a register
4017      which is both set and used by the insn.  */
4018   if (set
4019       && GET_CODE (SET_DEST (set)) == REG
4020       && reg_mentioned_p (SET_DEST (set), SET_SRC (set)))
4021     {
4022       note = gen_rtx_EXPR_LIST (REG_DEAD, SET_DEST (set), NULL_RTX);
4023       delete_prior_computation (note, insn);
4024     }
4025
4026   delete_insn (insn);
4027 }
4028 \f
4029 /* Delete insn INSN from the chain of insns and update label ref counts.
4030    May delete some following insns as a consequence; may even delete
4031    a label elsewhere and insns that follow it.
4032
4033    Returns the first insn after INSN that was not deleted.  */
4034
4035 rtx
4036 delete_insn (insn)
4037      register rtx insn;
4038 {
4039   register rtx next = NEXT_INSN (insn);
4040   register rtx prev = PREV_INSN (insn);
4041   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
4042   register int dont_really_delete = 0;
4043
4044   while (next && INSN_DELETED_P (next))
4045     next = NEXT_INSN (next);
4046
4047   /* This insn is already deleted => return first following nondeleted.  */
4048   if (INSN_DELETED_P (insn))
4049     return next;
4050
4051   if (was_code_label)
4052     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
4053
4054   /* Don't delete user-declared labels.  Convert them to special NOTEs
4055      instead.  */
4056   if (was_code_label && LABEL_NAME (insn) != 0
4057       && optimize && ! dont_really_delete)
4058     {
4059       PUT_CODE (insn, NOTE);
4060       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
4061       NOTE_SOURCE_FILE (insn) = 0;
4062       dont_really_delete = 1;
4063     }
4064   else
4065     /* Mark this insn as deleted.  */
4066     INSN_DELETED_P (insn) = 1;
4067
4068   /* If this is an unconditional jump, delete it from the jump chain.  */
4069   if (simplejump_p (insn))
4070     delete_from_jump_chain (insn);
4071
4072   /* If instruction is followed by a barrier,
4073      delete the barrier too.  */
4074
4075   if (next != 0 && GET_CODE (next) == BARRIER)
4076     {
4077       INSN_DELETED_P (next) = 1;
4078       next = NEXT_INSN (next);
4079     }
4080
4081   /* Patch out INSN (and the barrier if any) */
4082
4083   if (optimize && ! dont_really_delete)
4084     {
4085       if (prev)
4086         {
4087           NEXT_INSN (prev) = next;
4088           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
4089             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
4090                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
4091         }
4092
4093       if (next)
4094         {
4095           PREV_INSN (next) = prev;
4096           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
4097             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
4098         }
4099
4100       if (prev && NEXT_INSN (prev) == 0)
4101         set_last_insn (prev);
4102     }
4103
4104   /* If deleting a jump, decrement the count of the label,
4105      and delete the label if it is now unused.  */
4106
4107   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
4108     {
4109       rtx lab = JUMP_LABEL (insn), lab_next;
4110
4111       if (--LABEL_NUSES (lab) == 0)
4112         {
4113           /* This can delete NEXT or PREV,
4114              either directly if NEXT is JUMP_LABEL (INSN),
4115              or indirectly through more levels of jumps.  */
4116           delete_insn (lab);
4117
4118           /* I feel a little doubtful about this loop,
4119              but I see no clean and sure alternative way
4120              to find the first insn after INSN that is not now deleted.
4121              I hope this works.  */
4122           while (next && INSN_DELETED_P (next))
4123             next = NEXT_INSN (next);
4124           return next;
4125         }
4126       else if ((lab_next = next_nonnote_insn (lab)) != NULL
4127                && GET_CODE (lab_next) == JUMP_INSN
4128                && (GET_CODE (PATTERN (lab_next)) == ADDR_VEC
4129                    || GET_CODE (PATTERN (lab_next)) == ADDR_DIFF_VEC))
4130         {
4131           /* If we're deleting the tablejump, delete the dispatch table.
4132              We may not be able to kill the label immediately preceeding
4133              just yet, as it might be referenced in code leading up to
4134              the tablejump.  */
4135           delete_insn (lab_next);
4136         }
4137     }
4138
4139   /* Likewise if we're deleting a dispatch table.  */
4140
4141   if (GET_CODE (insn) == JUMP_INSN
4142       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
4143           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
4144     {
4145       rtx pat = PATTERN (insn);
4146       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
4147       int len = XVECLEN (pat, diff_vec_p);
4148
4149       for (i = 0; i < len; i++)
4150         if (--LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
4151           delete_insn (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
4152       while (next && INSN_DELETED_P (next))
4153         next = NEXT_INSN (next);
4154       return next;
4155     }
4156
4157   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
4158     prev = PREV_INSN (prev);
4159
4160   /* If INSN was a label and a dispatch table follows it,
4161      delete the dispatch table.  The tablejump must have gone already.
4162      It isn't useful to fall through into a table.  */
4163
4164   if (was_code_label
4165       && NEXT_INSN (insn) != 0
4166       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
4167       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
4168           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
4169     next = delete_insn (NEXT_INSN (insn));
4170
4171   /* If INSN was a label, delete insns following it if now unreachable.  */
4172
4173   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
4174     {
4175       register RTX_CODE code;
4176       while (next != 0
4177              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
4178                  || code == NOTE || code == BARRIER
4179                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
4180         {
4181           if (code == NOTE
4182               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
4183             next = NEXT_INSN (next);
4184           /* Keep going past other deleted labels to delete what follows.  */
4185           else if (code == CODE_LABEL && INSN_DELETED_P (next))
4186             next = NEXT_INSN (next);
4187           else
4188             /* Note: if this deletes a jump, it can cause more
4189                deletion of unreachable code, after a different label.
4190                As long as the value from this recursive call is correct,
4191                this invocation functions correctly.  */
4192             next = delete_insn (next);
4193         }
4194     }
4195
4196   return next;
4197 }
4198
4199 /* Advance from INSN till reaching something not deleted
4200    then return that.  May return INSN itself.  */
4201
4202 rtx
4203 next_nondeleted_insn (insn)
4204      rtx insn;
4205 {
4206   while (INSN_DELETED_P (insn))
4207     insn = NEXT_INSN (insn);
4208   return insn;
4209 }
4210 \f
4211 /* Delete a range of insns from FROM to TO, inclusive.
4212    This is for the sake of peephole optimization, so assume
4213    that whatever these insns do will still be done by a new
4214    peephole insn that will replace them.  */
4215
4216 void
4217 delete_for_peephole (from, to)
4218      register rtx from, to;
4219 {
4220   register rtx insn = from;
4221
4222   while (1)
4223     {
4224       register rtx next = NEXT_INSN (insn);
4225       register rtx prev = PREV_INSN (insn);
4226
4227       if (GET_CODE (insn) != NOTE)
4228         {
4229           INSN_DELETED_P (insn) = 1;
4230
4231           /* Patch this insn out of the chain.  */
4232           /* We don't do this all at once, because we
4233              must preserve all NOTEs.  */
4234           if (prev)
4235             NEXT_INSN (prev) = next;
4236
4237           if (next)
4238             PREV_INSN (next) = prev;
4239         }
4240
4241       if (insn == to)
4242         break;
4243       insn = next;
4244     }
4245
4246   /* Note that if TO is an unconditional jump
4247      we *do not* delete the BARRIER that follows,
4248      since the peephole that replaces this sequence
4249      is also an unconditional jump in that case.  */
4250 }
4251 \f
4252 /* We have determined that INSN is never reached, and are about to
4253    delete it.  Print a warning if the user asked for one.
4254
4255    To try to make this warning more useful, this should only be called
4256    once per basic block not reached, and it only warns when the basic
4257    block contains more than one line from the current function, and
4258    contains at least one operation.  CSE and inlining can duplicate insns,
4259    so it's possible to get spurious warnings from this.  */
4260
4261 void
4262 never_reached_warning (avoided_insn)
4263      rtx avoided_insn;
4264 {
4265   rtx insn;
4266   rtx a_line_note = NULL;
4267   int two_avoided_lines = 0;
4268   int contains_insn = 0;
4269
4270   if (! warn_notreached)
4271     return;
4272
4273   /* Scan forwards, looking at LINE_NUMBER notes, until
4274      we hit a LABEL or we run out of insns.  */
4275
4276   for (insn = avoided_insn; insn != NULL; insn = NEXT_INSN (insn))
4277     {
4278        if (GET_CODE (insn) == CODE_LABEL)
4279          break;
4280        else if (GET_CODE (insn) == NOTE         /* A line number note? */
4281                 && NOTE_LINE_NUMBER (insn) >= 0)
4282         {
4283           if (a_line_note == NULL)
4284             a_line_note = insn;
4285           else
4286             two_avoided_lines |= (NOTE_LINE_NUMBER (a_line_note)
4287                                   != NOTE_LINE_NUMBER (insn));
4288         }
4289        else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
4290          contains_insn = 1;
4291     }
4292   if (two_avoided_lines && contains_insn)
4293     warning_with_file_and_line (NOTE_SOURCE_FILE (a_line_note),
4294                                 NOTE_LINE_NUMBER (a_line_note),
4295                                 "will never be executed");
4296 }
4297 \f
4298 /* Invert the condition of the jump JUMP, and make it jump
4299    to label NLABEL instead of where it jumps now.  */
4300
4301 int
4302 invert_jump (jump, nlabel)
4303      rtx jump, nlabel;
4304 {
4305   /* We have to either invert the condition and change the label or
4306      do neither.  Either operation could fail.  We first try to invert
4307      the jump. If that succeeds, we try changing the label.  If that fails,
4308      we invert the jump back to what it was.  */
4309
4310   if (! invert_exp (PATTERN (jump), jump))
4311     return 0;
4312
4313   if (redirect_jump (jump, nlabel))
4314     {
4315       if (flag_branch_probabilities)
4316         {
4317           rtx note = find_reg_note (jump, REG_BR_PROB, 0);
4318
4319           /* An inverted jump means that a probability taken becomes a
4320              probability not taken.  Subtract the branch probability from the
4321              probability base to convert it back to a taken probability.
4322              (We don't flip the probability on a branch that's never taken.  */
4323           if (note && XINT (XEXP (note, 0), 0) >= 0)
4324             XINT (XEXP (note, 0), 0) = REG_BR_PROB_BASE - XINT (XEXP (note, 0), 0);
4325         }
4326
4327       return 1;
4328     }
4329
4330   if (! invert_exp (PATTERN (jump), jump))
4331     /* This should just be putting it back the way it was.  */
4332     abort ();
4333
4334   return  0;
4335 }
4336
4337 /* Invert the jump condition of rtx X contained in jump insn, INSN.
4338
4339    Return 1 if we can do so, 0 if we cannot find a way to do so that
4340    matches a pattern.  */
4341
4342 int
4343 invert_exp (x, insn)
4344      rtx x;
4345      rtx insn;
4346 {
4347   register RTX_CODE code;
4348   register int i;
4349   register const char *fmt;
4350
4351   code = GET_CODE (x);
4352
4353   if (code == IF_THEN_ELSE)
4354     {
4355       register rtx comp = XEXP (x, 0);
4356       register rtx tem;
4357
4358       /* We can do this in two ways:  The preferable way, which can only
4359          be done if this is not an integer comparison, is to reverse
4360          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
4361          of the IF_THEN_ELSE.  If we can't do either, fail.  */
4362
4363       if (can_reverse_comparison_p (comp, insn)
4364           && validate_change (insn, &XEXP (x, 0),
4365                               gen_rtx_fmt_ee (reverse_condition (GET_CODE (comp)),
4366                                               GET_MODE (comp), XEXP (comp, 0),
4367                                               XEXP (comp, 1)), 0))
4368         return 1;
4369
4370       tem = XEXP (x, 1);
4371       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
4372       validate_change (insn, &XEXP (x, 2), tem, 1);
4373       return apply_change_group ();
4374     }
4375
4376   fmt = GET_RTX_FORMAT (code);
4377   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4378     {
4379       if (fmt[i] == 'e')
4380         if (! invert_exp (XEXP (x, i), insn))
4381           return 0;
4382       if (fmt[i] == 'E')
4383         {
4384           register int j;
4385           for (j = 0; j < XVECLEN (x, i); j++)
4386             if (!invert_exp (XVECEXP (x, i, j), insn))
4387               return 0;
4388         }
4389     }
4390
4391   return 1;
4392 }
4393 \f
4394 /* Make jump JUMP jump to label NLABEL instead of where it jumps now.
4395    If the old jump target label is unused as a result,
4396    it and the code following it may be deleted.
4397
4398    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
4399    RETURN insn.
4400
4401    The return value will be 1 if the change was made, 0 if it wasn't (this
4402    can only occur for NLABEL == 0).  */
4403
4404 int
4405 redirect_jump (jump, nlabel)
4406      rtx jump, nlabel;
4407 {
4408   register rtx olabel = JUMP_LABEL (jump);
4409
4410   if (nlabel == olabel)
4411     return 1;
4412
4413   if (! redirect_exp (&PATTERN (jump), olabel, nlabel, jump))
4414     return 0;
4415
4416   /* If this is an unconditional branch, delete it from the jump_chain of
4417      OLABEL and add it to the jump_chain of NLABEL (assuming both labels
4418      have UID's in range and JUMP_CHAIN is valid).  */
4419   if (jump_chain && (simplejump_p (jump)
4420                      || GET_CODE (PATTERN (jump)) == RETURN))
4421     {
4422       int label_index = nlabel ? INSN_UID (nlabel) : 0;
4423
4424       delete_from_jump_chain (jump);
4425       if (label_index < max_jump_chain
4426           && INSN_UID (jump) < max_jump_chain)
4427         {
4428           jump_chain[INSN_UID (jump)] = jump_chain[label_index];
4429           jump_chain[label_index] = jump;
4430         }
4431     }
4432
4433   JUMP_LABEL (jump) = nlabel;
4434   if (nlabel)
4435     ++LABEL_NUSES (nlabel);
4436
4437   if (olabel && --LABEL_NUSES (olabel) == 0)
4438     delete_insn (olabel);
4439
4440   return 1;
4441 }
4442
4443 /* Delete the instruction JUMP from any jump chain it might be on.  */
4444
4445 static void
4446 delete_from_jump_chain (jump)
4447      rtx jump;
4448 {
4449   int index;
4450   rtx olabel = JUMP_LABEL (jump);
4451
4452   /* Handle unconditional jumps.  */
4453   if (jump_chain && olabel != 0
4454       && INSN_UID (olabel) < max_jump_chain
4455       && simplejump_p (jump))
4456     index = INSN_UID (olabel);
4457   /* Handle return insns.  */
4458   else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
4459     index = 0;
4460   else return;
4461
4462   if (jump_chain[index] == jump)
4463     jump_chain[index] = jump_chain[INSN_UID (jump)];
4464   else
4465     {
4466       rtx insn;
4467
4468       for (insn = jump_chain[index];
4469            insn != 0;
4470            insn = jump_chain[INSN_UID (insn)])
4471         if (jump_chain[INSN_UID (insn)] == jump)
4472           {
4473             jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
4474             break;
4475           }
4476     }
4477 }
4478
4479 /* If NLABEL is nonzero, throughout the rtx at LOC,
4480    alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL).  If OLABEL is
4481    zero, alter (RETURN) to (LABEL_REF NLABEL).
4482
4483    If NLABEL is zero, alter (LABEL_REF OLABEL) to (RETURN) and check
4484    validity with validate_change.  Convert (set (pc) (label_ref olabel))
4485    to (return).
4486
4487    Return 0 if we found a change we would like to make but it is invalid.
4488    Otherwise, return 1.  */
4489
4490 int
4491 redirect_exp (loc, olabel, nlabel, insn)
4492      rtx *loc;
4493      rtx olabel, nlabel;
4494      rtx insn;
4495 {
4496   register rtx x = *loc;
4497   register RTX_CODE code = GET_CODE (x);
4498   register int i;
4499   register const char *fmt;
4500
4501   if (code == LABEL_REF)
4502     {
4503       if (XEXP (x, 0) == olabel)
4504         {
4505           if (nlabel)
4506             XEXP (x, 0) = nlabel;
4507           else
4508             return validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 0);
4509           return 1;
4510         }
4511     }
4512   else if (code == RETURN && olabel == 0)
4513     {
4514       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
4515       if (loc == &PATTERN (insn))
4516         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
4517       return validate_change (insn, loc, x, 0);
4518     }
4519
4520   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
4521       && GET_CODE (SET_SRC (x)) == LABEL_REF
4522       && XEXP (SET_SRC (x), 0) == olabel)
4523     return validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 0);
4524
4525   fmt = GET_RTX_FORMAT (code);
4526   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4527     {
4528       if (fmt[i] == 'e')
4529         if (! redirect_exp (&XEXP (x, i), olabel, nlabel, insn))
4530           return 0;
4531       if (fmt[i] == 'E')
4532         {
4533           register int j;
4534           for (j = 0; j < XVECLEN (x, i); j++)
4535             if (! redirect_exp (&XVECEXP (x, i, j), olabel, nlabel, insn))
4536               return 0;
4537         }
4538     }
4539
4540   return 1;
4541 }
4542 \f
4543 /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
4544
4545    If the old jump target label (before the dispatch table) becomes unused,
4546    it and the dispatch table may be deleted.  In that case, find the insn
4547    before the jump references that label and delete it and logical successors
4548    too.  */
4549
4550 static void
4551 redirect_tablejump (jump, nlabel)
4552      rtx jump, nlabel;
4553 {
4554   register rtx olabel = JUMP_LABEL (jump);
4555
4556   /* Add this jump to the jump_chain of NLABEL.  */
4557   if (jump_chain && INSN_UID (nlabel) < max_jump_chain
4558       && INSN_UID (jump) < max_jump_chain)
4559     {
4560       jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
4561       jump_chain[INSN_UID (nlabel)] = jump;
4562     }
4563
4564   PATTERN (jump) = gen_jump (nlabel);
4565   JUMP_LABEL (jump) = nlabel;
4566   ++LABEL_NUSES (nlabel);
4567   INSN_CODE (jump) = -1;
4568
4569   if (--LABEL_NUSES (olabel) == 0)
4570     {
4571       delete_labelref_insn (jump, olabel, 0);
4572       delete_insn (olabel);
4573     }
4574 }
4575
4576 /* Find the insn referencing LABEL that is a logical predecessor of INSN.
4577    If we found one, delete it and then delete this insn if DELETE_THIS is
4578    non-zero.  Return non-zero if INSN or a predecessor references LABEL.  */
4579
4580 static int
4581 delete_labelref_insn (insn, label, delete_this)
4582      rtx insn, label;
4583      int delete_this;
4584 {
4585   int deleted = 0;
4586   rtx link;
4587
4588   if (GET_CODE (insn) != NOTE
4589       && reg_mentioned_p (label, PATTERN (insn)))
4590     {
4591       if (delete_this)
4592         {
4593           delete_insn (insn);
4594           deleted = 1;
4595         }
4596       else
4597         return 1;
4598     }
4599
4600   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
4601     if (delete_labelref_insn (XEXP (link, 0), label, 1))
4602       {
4603         if (delete_this)
4604           {
4605             delete_insn (insn);
4606             deleted = 1;
4607           }
4608         else
4609           return 1;
4610       }
4611
4612   return deleted;
4613 }
4614 \f
4615 /* Like rtx_equal_p except that it considers two REGs as equal
4616    if they renumber to the same value and considers two commutative
4617    operations to be the same if the order of the operands has been
4618    reversed.
4619
4620    ??? Addition is not commutative on the PA due to the weird implicit
4621    space register selection rules for memory addresses.  Therefore, we
4622    don't consider a + b == b + a.
4623
4624    We could/should make this test a little tighter.  Possibly only
4625    disabling it on the PA via some backend macro or only disabling this
4626    case when the PLUS is inside a MEM.  */
4627
4628 int
4629 rtx_renumbered_equal_p (x, y)
4630      rtx x, y;
4631 {
4632   register int i;
4633   register RTX_CODE code = GET_CODE (x);
4634   register const char *fmt;
4635
4636   if (x == y)
4637     return 1;
4638
4639   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
4640       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
4641                                   && GET_CODE (SUBREG_REG (y)) == REG)))
4642     {
4643       int reg_x = -1, reg_y = -1;
4644       int word_x = 0, word_y = 0;
4645
4646       if (GET_MODE (x) != GET_MODE (y))
4647         return 0;
4648
4649       /* If we haven't done any renumbering, don't
4650          make any assumptions.  */
4651       if (reg_renumber == 0)
4652         return rtx_equal_p (x, y);
4653
4654       if (code == SUBREG)
4655         {
4656           reg_x = REGNO (SUBREG_REG (x));
4657           word_x = SUBREG_WORD (x);
4658
4659           if (reg_renumber[reg_x] >= 0)
4660             {
4661               reg_x = reg_renumber[reg_x] + word_x;
4662               word_x = 0;
4663             }
4664         }
4665
4666       else
4667         {
4668           reg_x = REGNO (x);
4669           if (reg_renumber[reg_x] >= 0)
4670             reg_x = reg_renumber[reg_x];
4671         }
4672
4673       if (GET_CODE (y) == SUBREG)
4674         {
4675           reg_y = REGNO (SUBREG_REG (y));
4676           word_y = SUBREG_WORD (y);
4677
4678           if (reg_renumber[reg_y] >= 0)
4679             {
4680               reg_y = reg_renumber[reg_y];
4681               word_y = 0;
4682             }
4683         }
4684
4685       else
4686         {
4687           reg_y = REGNO (y);
4688           if (reg_renumber[reg_y] >= 0)
4689             reg_y = reg_renumber[reg_y];
4690         }
4691
4692       return reg_x >= 0 && reg_x == reg_y && word_x == word_y;
4693     }
4694
4695   /* Now we have disposed of all the cases
4696      in which different rtx codes can match.  */
4697   if (code != GET_CODE (y))
4698     return 0;
4699
4700   switch (code)
4701     {
4702     case PC:
4703     case CC0:
4704     case ADDR_VEC:
4705     case ADDR_DIFF_VEC:
4706       return 0;
4707
4708     case CONST_INT:
4709       return INTVAL (x) == INTVAL (y);
4710
4711     case LABEL_REF:
4712       /* We can't assume nonlocal labels have their following insns yet.  */
4713       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
4714         return XEXP (x, 0) == XEXP (y, 0);
4715
4716       /* Two label-refs are equivalent if they point at labels
4717          in the same position in the instruction stream.  */
4718       return (next_real_insn (XEXP (x, 0))
4719               == next_real_insn (XEXP (y, 0)));
4720
4721     case SYMBOL_REF:
4722       return XSTR (x, 0) == XSTR (y, 0);
4723
4724     case CODE_LABEL:
4725       /* If we didn't match EQ equality above, they aren't the same.  */
4726       return 0;
4727
4728     default:
4729       break;
4730     }
4731
4732   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
4733
4734   if (GET_MODE (x) != GET_MODE (y))
4735     return 0;
4736
4737   /* For commutative operations, the RTX match if the operand match in any
4738      order.  Also handle the simple binary and unary cases without a loop.
4739
4740      ??? Don't consider PLUS a commutative operator; see comments above.  */
4741   if ((code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
4742       && code != PLUS)
4743     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
4744              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
4745             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
4746                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
4747   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
4748     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
4749             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
4750   else if (GET_RTX_CLASS (code) == '1')
4751     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
4752
4753   /* Compare the elements.  If any pair of corresponding elements
4754      fail to match, return 0 for the whole things.  */
4755
4756   fmt = GET_RTX_FORMAT (code);
4757   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4758     {
4759       register int j;
4760       switch (fmt[i])
4761         {
4762         case 'w':
4763           if (XWINT (x, i) != XWINT (y, i))
4764             return 0;
4765           break;
4766
4767         case 'i':
4768           if (XINT (x, i) != XINT (y, i))
4769             return 0;
4770           break;
4771
4772         case 's':
4773           if (strcmp (XSTR (x, i), XSTR (y, i)))
4774             return 0;
4775           break;
4776
4777         case 'e':
4778           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
4779             return 0;
4780           break;
4781
4782         case 'u':
4783           if (XEXP (x, i) != XEXP (y, i))
4784             return 0;
4785           /* fall through.  */
4786         case '0':
4787           break;
4788
4789         case 'E':
4790           if (XVECLEN (x, i) != XVECLEN (y, i))
4791             return 0;
4792           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4793             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
4794               return 0;
4795           break;
4796
4797         default:
4798           abort ();
4799         }
4800     }
4801   return 1;
4802 }
4803 \f
4804 /* If X is a hard register or equivalent to one or a subregister of one,
4805    return the hard register number.  If X is a pseudo register that was not
4806    assigned a hard register, return the pseudo register number.  Otherwise,
4807    return -1.  Any rtx is valid for X.  */
4808
4809 int
4810 true_regnum (x)
4811      rtx x;
4812 {
4813   if (GET_CODE (x) == REG)
4814     {
4815       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
4816         return reg_renumber[REGNO (x)];
4817       return REGNO (x);
4818     }
4819   if (GET_CODE (x) == SUBREG)
4820     {
4821       int base = true_regnum (SUBREG_REG (x));
4822       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
4823         return SUBREG_WORD (x) + base;
4824     }
4825   return -1;
4826 }
4827 \f
4828 /* Optimize code of the form:
4829
4830         for (x = a[i]; x; ...)
4831           ...
4832         for (x = a[i]; x; ...)
4833           ...
4834       foo:
4835
4836    Loop optimize will change the above code into
4837
4838         if (x = a[i])
4839           for (;;)
4840              { ...; if (! (x = ...)) break; }
4841         if (x = a[i])
4842           for (;;)
4843              { ...; if (! (x = ...)) break; }
4844       foo:
4845
4846    In general, if the first test fails, the program can branch
4847    directly to `foo' and skip the second try which is doomed to fail.
4848    We run this after loop optimization and before flow analysis.  */
4849
4850 /* When comparing the insn patterns, we track the fact that different
4851    pseudo-register numbers may have been used in each computation.
4852    The following array stores an equivalence -- same_regs[I] == J means
4853    that pseudo register I was used in the first set of tests in a context
4854    where J was used in the second set.  We also count the number of such
4855    pending equivalences.  If nonzero, the expressions really aren't the
4856    same.  */
4857
4858 static int *same_regs;
4859
4860 static int num_same_regs;
4861
4862 /* Track any registers modified between the target of the first jump and
4863    the second jump.  They never compare equal.  */
4864
4865 static char *modified_regs;
4866
4867 /* Record if memory was modified.  */
4868
4869 static int modified_mem;
4870
4871 /* Called via note_stores on each insn between the target of the first
4872    branch and the second branch.  It marks any changed registers.  */
4873
4874 static void
4875 mark_modified_reg (dest, x)
4876      rtx dest;
4877      rtx x ATTRIBUTE_UNUSED;
4878 {
4879   int regno, i;
4880
4881   if (GET_CODE (dest) == SUBREG)
4882     dest = SUBREG_REG (dest);
4883
4884   if (GET_CODE (dest) == MEM)
4885     modified_mem = 1;
4886
4887   if (GET_CODE (dest) != REG)
4888     return;
4889
4890   regno = REGNO (dest);
4891   if (regno >= FIRST_PSEUDO_REGISTER)
4892     modified_regs[regno] = 1;
4893   else
4894     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
4895       modified_regs[regno + i] = 1;
4896 }
4897
4898 /* F is the first insn in the chain of insns.  */
4899
4900 void
4901 thread_jumps (f, max_reg, flag_before_loop)
4902      rtx f;
4903      int max_reg;
4904      int flag_before_loop;
4905 {
4906   /* Basic algorithm is to find a conditional branch,
4907      the label it may branch to, and the branch after
4908      that label.  If the two branches test the same condition,
4909      walk back from both branch paths until the insn patterns
4910      differ, or code labels are hit.  If we make it back to
4911      the target of the first branch, then we know that the first branch
4912      will either always succeed or always fail depending on the relative
4913      senses of the two branches.  So adjust the first branch accordingly
4914      in this case.  */
4915
4916   rtx label, b1, b2, t1, t2;
4917   enum rtx_code code1, code2;
4918   rtx b1op0, b1op1, b2op0, b2op1;
4919   int changed = 1;
4920   int i;
4921   int *all_reset;
4922
4923   /* Allocate register tables and quick-reset table.  */
4924   modified_regs = (char *) alloca (max_reg * sizeof (char));
4925   same_regs = (int *) alloca (max_reg * sizeof (int));
4926   all_reset = (int *) alloca (max_reg * sizeof (int));
4927   for (i = 0; i < max_reg; i++)
4928     all_reset[i] = -1;
4929
4930   while (changed)
4931     {
4932       changed = 0;
4933
4934       for (b1 = f; b1; b1 = NEXT_INSN (b1))
4935         {
4936           /* Get to a candidate branch insn.  */
4937           if (GET_CODE (b1) != JUMP_INSN
4938               || ! condjump_p (b1) || simplejump_p (b1)
4939               || JUMP_LABEL (b1) == 0)
4940             continue;
4941
4942           bzero (modified_regs, max_reg * sizeof (char));
4943           modified_mem = 0;
4944
4945           bcopy ((char *) all_reset, (char *) same_regs,
4946                  max_reg * sizeof (int));
4947           num_same_regs = 0;
4948
4949           label = JUMP_LABEL (b1);
4950
4951           /* Look for a branch after the target.  Record any registers and
4952              memory modified between the target and the branch.  Stop when we
4953              get to a label since we can't know what was changed there.  */
4954           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
4955             {
4956               if (GET_CODE (b2) == CODE_LABEL)
4957                 break;
4958
4959               else if (GET_CODE (b2) == JUMP_INSN)
4960                 {
4961                   /* If this is an unconditional jump and is the only use of
4962                      its target label, we can follow it.  */
4963                   if (simplejump_p (b2)
4964                       && JUMP_LABEL (b2) != 0
4965                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
4966                     {
4967                       b2 = JUMP_LABEL (b2);
4968                       continue;
4969                     }
4970                   else
4971                     break;
4972                 }
4973
4974               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
4975                 continue;
4976
4977               if (GET_CODE (b2) == CALL_INSN)
4978                 {
4979                   modified_mem = 1;
4980                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4981                     if (call_used_regs[i] && ! fixed_regs[i]
4982                         && i != STACK_POINTER_REGNUM
4983                         && i != FRAME_POINTER_REGNUM
4984                         && i != HARD_FRAME_POINTER_REGNUM
4985                         && i != ARG_POINTER_REGNUM)
4986                       modified_regs[i] = 1;
4987                 }
4988
4989               note_stores (PATTERN (b2), mark_modified_reg);
4990             }
4991
4992           /* Check the next candidate branch insn from the label
4993              of the first.  */
4994           if (b2 == 0
4995               || GET_CODE (b2) != JUMP_INSN
4996               || b2 == b1
4997               || ! condjump_p (b2)
4998               || simplejump_p (b2))
4999             continue;
5000
5001           /* Get the comparison codes and operands, reversing the
5002              codes if appropriate.  If we don't have comparison codes,
5003              we can't do anything.  */
5004           b1op0 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 0);
5005           b1op1 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 1);
5006           code1 = GET_CODE (XEXP (SET_SRC (PATTERN (b1)), 0));
5007           if (XEXP (SET_SRC (PATTERN (b1)), 1) == pc_rtx)
5008             code1 = reverse_condition (code1);
5009
5010           b2op0 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 0);
5011           b2op1 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 1);
5012           code2 = GET_CODE (XEXP (SET_SRC (PATTERN (b2)), 0));
5013           if (XEXP (SET_SRC (PATTERN (b2)), 1) == pc_rtx)
5014             code2 = reverse_condition (code2);
5015
5016           /* If they test the same things and knowing that B1 branches
5017              tells us whether or not B2 branches, check if we
5018              can thread the branch.  */
5019           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
5020               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
5021               && (comparison_dominates_p (code1, code2)
5022                   || (comparison_dominates_p (code1, reverse_condition (code2))
5023                       && can_reverse_comparison_p (XEXP (SET_SRC (PATTERN (b1)),
5024                                                          0),
5025                                                    b1))))
5026             {
5027               t1 = prev_nonnote_insn (b1);
5028               t2 = prev_nonnote_insn (b2);
5029
5030               while (t1 != 0 && t2 != 0)
5031                 {
5032                   if (t2 == label)
5033                     {
5034                       /* We have reached the target of the first branch.
5035                          If there are no pending register equivalents,
5036                          we know that this branch will either always
5037                          succeed (if the senses of the two branches are
5038                          the same) or always fail (if not).  */
5039                       rtx new_label;
5040
5041                       if (num_same_regs != 0)
5042                         break;
5043
5044                       if (comparison_dominates_p (code1, code2))
5045                         new_label = JUMP_LABEL (b2);
5046                       else
5047                         new_label = get_label_after (b2);
5048
5049                       if (JUMP_LABEL (b1) != new_label)
5050                         {
5051                           rtx prev = PREV_INSN (new_label);
5052
5053                           if (flag_before_loop
5054                               && GET_CODE (prev) == NOTE
5055                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
5056                             {
5057                               /* Don't thread to the loop label.  If a loop
5058                                  label is reused, loop optimization will
5059                                  be disabled for that loop.  */
5060                               new_label = gen_label_rtx ();
5061                               emit_label_after (new_label, PREV_INSN (prev));
5062                             }
5063                           changed |= redirect_jump (b1, new_label);
5064                         }
5065                       break;
5066                     }
5067
5068                   /* If either of these is not a normal insn (it might be
5069                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
5070                      have already been skipped above.)  Similarly, fail
5071                      if the insns are different.  */
5072                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
5073                       || recog_memoized (t1) != recog_memoized (t2)
5074                       || ! rtx_equal_for_thread_p (PATTERN (t1),
5075                                                    PATTERN (t2), t2))
5076                     break;
5077
5078                   t1 = prev_nonnote_insn (t1);
5079                   t2 = prev_nonnote_insn (t2);
5080                 }
5081             }
5082         }
5083     }
5084 }
5085 \f
5086 /* This is like RTX_EQUAL_P except that it knows about our handling of
5087    possibly equivalent registers and knows to consider volatile and
5088    modified objects as not equal.
5089
5090    YINSN is the insn containing Y.  */
5091
5092 int
5093 rtx_equal_for_thread_p (x, y, yinsn)
5094      rtx x, y;
5095      rtx yinsn;
5096 {
5097   register int i;
5098   register int j;
5099   register enum rtx_code code;
5100   register const char *fmt;
5101
5102   code = GET_CODE (x);
5103   /* Rtx's of different codes cannot be equal.  */
5104   if (code != GET_CODE (y))
5105     return 0;
5106
5107   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
5108      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
5109
5110   if (GET_MODE (x) != GET_MODE (y))
5111     return 0;
5112
5113   /* For floating-point, consider everything unequal.  This is a bit
5114      pessimistic, but this pass would only rarely do anything for FP
5115      anyway.  */
5116   if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
5117       && FLOAT_MODE_P (GET_MODE (x)) && ! flag_fast_math)
5118     return 0;
5119
5120   /* For commutative operations, the RTX match if the operand match in any
5121      order.  Also handle the simple binary and unary cases without a loop.  */
5122   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
5123     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
5124              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
5125             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
5126                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
5127   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
5128     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
5129             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
5130   else if (GET_RTX_CLASS (code) == '1')
5131     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
5132
5133   /* Handle special-cases first.  */
5134   switch (code)
5135     {
5136     case REG:
5137       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
5138         return 1;
5139
5140       /* If neither is user variable or hard register, check for possible
5141          equivalence.  */
5142       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
5143           || REGNO (x) < FIRST_PSEUDO_REGISTER
5144           || REGNO (y) < FIRST_PSEUDO_REGISTER)
5145         return 0;
5146
5147       if (same_regs[REGNO (x)] == -1)
5148         {
5149           same_regs[REGNO (x)] = REGNO (y);
5150           num_same_regs++;
5151
5152           /* If this is the first time we are seeing a register on the `Y'
5153              side, see if it is the last use.  If not, we can't thread the
5154              jump, so mark it as not equivalent.  */
5155           if (REGNO_LAST_UID (REGNO (y)) != INSN_UID (yinsn))
5156             return 0;
5157
5158           return 1;
5159         }
5160       else
5161         return (same_regs[REGNO (x)] == REGNO (y));
5162
5163       break;
5164
5165     case MEM:
5166       /* If memory modified or either volatile, not equivalent.
5167          Else, check address.  */
5168       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
5169         return 0;
5170
5171       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
5172
5173     case ASM_INPUT:
5174       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
5175         return 0;
5176
5177       break;
5178
5179     case SET:
5180       /* Cancel a pending `same_regs' if setting equivalenced registers.
5181          Then process source.  */
5182       if (GET_CODE (SET_DEST (x)) == REG
5183           && GET_CODE (SET_DEST (y)) == REG)
5184         {
5185           if (same_regs[REGNO (SET_DEST (x))] == REGNO (SET_DEST (y)))
5186             {
5187               same_regs[REGNO (SET_DEST (x))] = -1;
5188               num_same_regs--;
5189             }
5190           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
5191             return 0;
5192         }
5193       else
5194         if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
5195           return 0;
5196
5197       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
5198
5199     case LABEL_REF:
5200       return XEXP (x, 0) == XEXP (y, 0);
5201
5202     case SYMBOL_REF:
5203       return XSTR (x, 0) == XSTR (y, 0);
5204
5205     default:
5206       break;
5207     }
5208
5209   if (x == y)
5210     return 1;
5211
5212   fmt = GET_RTX_FORMAT (code);
5213   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5214     {
5215       switch (fmt[i])
5216         {
5217         case 'w':
5218           if (XWINT (x, i) != XWINT (y, i))
5219             return 0;
5220           break;
5221
5222         case 'n':
5223         case 'i':
5224           if (XINT (x, i) != XINT (y, i))
5225             return 0;
5226           break;
5227
5228         case 'V':
5229         case 'E':
5230           /* Two vectors must have the same length.  */
5231           if (XVECLEN (x, i) != XVECLEN (y, i))
5232             return 0;
5233
5234           /* And the corresponding elements must match.  */
5235           for (j = 0; j < XVECLEN (x, i); j++)
5236             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
5237                                         XVECEXP (y, i, j), yinsn) == 0)
5238               return 0;
5239           break;
5240
5241         case 'e':
5242           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
5243             return 0;
5244           break;
5245
5246         case 'S':
5247         case 's':
5248           if (strcmp (XSTR (x, i), XSTR (y, i)))
5249             return 0;
5250           break;
5251
5252         case 'u':
5253           /* These are just backpointers, so they don't matter.  */
5254           break;
5255
5256         case '0':
5257         case 't':
5258           break;
5259
5260           /* It is believed that rtx's at this level will never
5261              contain anything but integers and other rtx's,
5262              except for within LABEL_REFs and SYMBOL_REFs.  */
5263         default:
5264           abort ();
5265         }
5266     }
5267   return 1;
5268 }
5269 \f
5270
5271 #ifndef HAVE_cc0
5272 /* Return the insn that NEW can be safely inserted in front of starting at
5273    the jump insn INSN.  Return 0 if it is not safe to do this jump
5274    optimization.  Note that NEW must contain a single set. */
5275
5276 static rtx
5277 find_insert_position (insn, new)
5278      rtx insn;
5279      rtx new;
5280 {
5281   int i;
5282   rtx prev;
5283
5284   /* If NEW does not clobber, it is safe to insert NEW before INSN. */
5285   if (GET_CODE (PATTERN (new)) != PARALLEL)
5286     return insn;
5287
5288   for (i = XVECLEN (PATTERN (new), 0) - 1; i >= 0; i--)
5289     if (GET_CODE (XVECEXP (PATTERN (new), 0, i)) == CLOBBER
5290         && reg_overlap_mentioned_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
5291                                     insn))
5292       break;
5293
5294   if (i < 0)
5295     return insn;
5296
5297   /* There is a good chance that the previous insn PREV sets the thing
5298      being clobbered (often the CC in a hard reg).  If PREV does not
5299      use what NEW sets, we can insert NEW before PREV. */
5300
5301   prev = prev_active_insn (insn);
5302   for (i = XVECLEN (PATTERN (new), 0) - 1; i >= 0; i--)
5303     if (GET_CODE (XVECEXP (PATTERN (new), 0, i)) == CLOBBER
5304         && reg_overlap_mentioned_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
5305                                     insn)
5306         && ! modified_in_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
5307                             prev))
5308       return 0;
5309
5310   return reg_mentioned_p (SET_DEST (single_set (new)), prev) ? 0 : prev;
5311 }
5312 #endif /* !HAVE_cc0 */