gcc/jump.c

   1 /* Optimize jump instructions, for GNU compiler.
   2    Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
   3    1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* This is the jump-optimization pass of the compiler.
  23    It is run two or three times: once before cse, sometimes once after cse,
  24    and once after reload (before final).
  25
  26    jump_optimize deletes unreachable code and labels that are not used.
  27    It also deletes jumps that jump to the following insn,
  28    and simplifies jumps around unconditional jumps and jumps
  29    to unconditional jumps.
  30
  31    Each CODE_LABEL has a count of the times it is used
  32    stored in the LABEL_NUSES internal field, and each JUMP_INSN
  33    has one label that it refers to stored in the
  34    JUMP_LABEL internal field.  With this we can detect labels that
  35    become unused because of the deletion of all the jumps that
  36    formerly used them.  The JUMP_LABEL info is sometimes looked
  37    at by later passes.
  38
  39    Optionally, cross-jumping can be done.  Currently it is done
  40    only the last time (when after reload and before final).
  41    In fact, the code for cross-jumping now assumes that register
  42    allocation has been done, since it uses `rtx_renumbered_equal_p'.
  43
  44    Jump optimization is done after cse when cse's constant-propagation
  45    causes jumps to become unconditional or to be deleted.
  46
  47    Unreachable loops are not detected here, because the labels
  48    have references and the insns appear reachable from the labels.
  49    find_basic_blocks in flow.c finds and deletes such loops.
  50
  51    The subroutines delete_insn, redirect_jump, and invert_jump are used
  52    from other passes as well.  */
  53
  54 #include "config.h"
  55 #include "system.h"
  56 #include "rtl.h"
  57 #include "tm_p.h"
  58 #include "flags.h"
  59 #include "hard-reg-set.h"
  60 #include "regs.h"
  61 #include "insn-config.h"
  62 #include "insn-flags.h"
  63 #include "insn-attr.h"
  64 #include "recog.h"
  65 #include "function.h"
  66 #include "expr.h"
  67 #include "real.h"
  68 #include "except.h"
  69 #include "toplev.h"
  70
  71 /* ??? Eventually must record somehow the labels used by jumps
  72    from nested functions.  */
  73 /* Pre-record the next or previous real insn for each label?
  74    No, this pass is very fast anyway.  */
  75 /* Condense consecutive labels?
  76    This would make life analysis faster, maybe.  */
  77 /* Optimize jump y; x: ... y: jumpif... x?
  78    Don't know if it is worth bothering with.  */
  79 /* Optimize two cases of conditional jump to conditional jump?
  80    This can never delete any instruction or make anything dead,
  81    or even change what is live at any point.
  82    So perhaps let combiner do it.  */
  83
  84 /* Vector indexed by uid.
  85    For each CODE_LABEL, index by its uid to get first unconditional jump
  86    that jumps to the label.
  87    For each JUMP_INSN, index by its uid to get the next unconditional jump
  88    that jumps to the same label.
  89    Element 0 is the start of a chain of all return insns.
  90    (It is safe to use element 0 because insn uid 0 is not used.  */
  91
  92 static rtx *jump_chain;
  93
  94 /* Maximum index in jump_chain.  */
  95
  96 static int max_jump_chain;
  97
  98 /* Indicates whether death notes are significant in cross jump analysis.
  99    Normally they are not significant, because of A and B jump to C,
 100    and R dies in A, it must die in B.  But this might not be true after
 101    stack register conversion, and we must compare death notes in that
 102    case.  */
 103
 104 static int cross_jump_death_matters = 0;
 105
 106 static int init_label_info              PARAMS ((rtx));
 107 static void delete_barrier_successors   PARAMS ((rtx));
 108 static void mark_all_labels             PARAMS ((rtx, int));
 109 static rtx delete_unreferenced_labels   PARAMS ((rtx));
 110 static void delete_noop_moves           PARAMS ((rtx));
 111 static int duplicate_loop_exit_test     PARAMS ((rtx));
 112 static void find_cross_jump             PARAMS ((rtx, rtx, int, rtx *, rtx *));
 113 static void do_cross_jump               PARAMS ((rtx, rtx, rtx));
 114 static int jump_back_p                  PARAMS ((rtx, rtx));
 115 static int tension_vector_labels        PARAMS ((rtx, int));
 116 static void delete_computation          PARAMS ((rtx));
 117 static void redirect_exp_1              PARAMS ((rtx *, rtx, rtx, rtx));
 118 static int redirect_exp                 PARAMS ((rtx, rtx, rtx));
 119 static void invert_exp_1                PARAMS ((rtx));
 120 static int invert_exp                   PARAMS ((rtx));
 121 static void delete_from_jump_chain      PARAMS ((rtx));
 122 static int delete_labelref_insn         PARAMS ((rtx, rtx, int));
 123 static void mark_modified_reg           PARAMS ((rtx, rtx, void *));
 124 static void redirect_tablejump          PARAMS ((rtx, rtx));
 125 static void jump_optimize_1             PARAMS ((rtx, int, int, int, int, int));
 126 static int returnjump_p_1               PARAMS ((rtx *, void *));
 127 static void delete_prior_computation    PARAMS ((rtx, rtx));
 128 \f
 129 /* Main external entry point into the jump optimizer.  See comments before
 130    jump_optimize_1 for descriptions of the arguments.  */
 131 void
 132 jump_optimize (f, cross_jump, noop_moves, after_regscan)
 133      rtx f;
 134      int cross_jump;
 135      int noop_moves;
 136      int after_regscan;
 137 {
 138   jump_optimize_1 (f, cross_jump, noop_moves, after_regscan, 0, 0);
 139 }
 140
 141 /* Alternate entry into the jump optimizer.  This entry point only rebuilds
 142    the JUMP_LABEL field in jumping insns and REG_LABEL notes in non-jumping
 143    instructions.  */
 144 void
 145 rebuild_jump_labels (f)
 146      rtx f;
 147 {
 148   jump_optimize_1 (f, 0, 0, 0, 1, 0);
 149 }
 150
 151 /* Alternate entry into the jump optimizer.  Do only trivial optimizations.  */
 152
 153 void
 154 jump_optimize_minimal (f)
 155      rtx f;
 156 {
 157   jump_optimize_1 (f, 0, 0, 0, 0, 1);
 158 }
 159 \f
 160 /* Delete no-op jumps and optimize jumps to jumps
 161    and jumps around jumps.
 162    Delete unused labels and unreachable code.
 163
 164    If CROSS_JUMP is 1, detect matching code
 165    before a jump and its destination and unify them.
 166    If CROSS_JUMP is 2, do cross-jumping, but pay attention to death notes.
 167
 168    If NOOP_MOVES is nonzero, delete no-op move insns.
 169
 170    If AFTER_REGSCAN is nonzero, then this jump pass is being run immediately
 171    after regscan, and it is safe to use regno_first_uid and regno_last_uid.
 172
 173    If MARK_LABELS_ONLY is nonzero, then we only rebuild the jump chain
 174    and JUMP_LABEL field for jumping insns.
 175
 176    If `optimize' is zero, don't change any code,
 177    just determine whether control drops off the end of the function.
 178    This case occurs when we have -W and not -O.
 179    It works because `delete_insn' checks the value of `optimize'
 180    and refrains from actually deleting when that is 0.
 181
 182    If MINIMAL is nonzero, then we only perform trivial optimizations:
 183
 184      * Removal of unreachable code after BARRIERs.
 185      * Removal of unreferenced CODE_LABELs.
 186      * Removal of a jump to the next instruction.
 187      * Removal of a conditional jump followed by an unconditional jump
 188        to the same target as the conditional jump.
 189      * Simplify a conditional jump around an unconditional jump.
 190      * Simplify a jump to a jump.
 191      * Delete extraneous line number notes.
 192   */
 193
 194 static void
 195 jump_optimize_1 (f, cross_jump, noop_moves, after_regscan,
 196                  mark_labels_only, minimal)
 197      rtx f;
 198      int cross_jump;
 199      int noop_moves;
 200      int after_regscan;
 201      int mark_labels_only;
 202      int minimal;
 203 {
 204   register rtx insn, next;
 205   int changed;
 206   int old_max_reg;
 207   int first = 1;
 208   int max_uid = 0;
 209   rtx last_insn;
 210
 211   cross_jump_death_matters = (cross_jump == 2);
 212   max_uid = init_label_info (f) + 1;
 213
 214   /* If we are performing cross jump optimizations, then initialize
 215      tables mapping UIDs to EH regions to avoid incorrect movement
 216      of insns from one EH region to another.  */
 217   if (flag_exceptions && cross_jump)
 218     init_insn_eh_region (f, max_uid);
 219
 220   if (! mark_labels_only)
 221     delete_barrier_successors (f);
 222
 223   /* Leave some extra room for labels and duplicate exit test insns
 224      we make.  */
 225   max_jump_chain = max_uid * 14 / 10;
 226   jump_chain = (rtx *) xcalloc (max_jump_chain, sizeof (rtx));
 227
 228   mark_all_labels (f, cross_jump);
 229
 230   /* Keep track of labels used from static data; we don't track them
 231      closely enough to delete them here, so make sure their reference
 232      count doesn't drop to zero.  */
 233
 234   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
 235     if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
 236       LABEL_NUSES (XEXP (insn, 0))++;
 237
 238   check_exception_handler_labels ();
 239
 240   /* Keep track of labels used for marking handlers for exception
 241      regions; they cannot usually be deleted.  */
 242
 243   for (insn = exception_handler_labels; insn; insn = XEXP (insn, 1))
 244     if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
 245       LABEL_NUSES (XEXP (insn, 0))++;
 246
 247   /* Quit now if we just wanted to rebuild the JUMP_LABEL and REG_LABEL
 248      notes and recompute LABEL_NUSES.  */
 249   if (mark_labels_only)
 250     goto end;
 251
 252   if (! minimal)
 253     exception_optimize ();
 254
 255   last_insn = delete_unreferenced_labels (f);
 256
 257   if (noop_moves)
 258     delete_noop_moves (f);
 259
 260   /* If we haven't yet gotten to reload and we have just run regscan,
 261      delete any insn that sets a register that isn't used elsewhere.
 262      This helps some of the optimizations below by having less insns
 263      being jumped around.  */
 264
 265   if (optimize && ! reload_completed && after_regscan)
 266     for (insn = f; insn; insn = next)
 267       {
 268         rtx set = single_set (insn);
 269
 270         next = NEXT_INSN (insn);
 271
 272         if (set && GET_CODE (SET_DEST (set)) == REG
 273             && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
 274             && REGNO_FIRST_UID (REGNO (SET_DEST (set))) == INSN_UID (insn)
 275             /* We use regno_last_note_uid so as not to delete the setting
 276                of a reg that's used in notes.  A subsequent optimization
 277                might arrange to use that reg for real.  */
 278             && REGNO_LAST_NOTE_UID (REGNO (SET_DEST (set))) == INSN_UID (insn)
 279             && ! side_effects_p (SET_SRC (set))
 280             && ! find_reg_note (insn, REG_RETVAL, 0)
 281             /* An ADDRESSOF expression can turn into a use of the internal arg
 282                pointer, so do not delete the initialization of the internal
 283                arg pointer yet.  If it is truly dead, flow will delete the
 284                initializing insn.  */
 285             && SET_DEST (set) != current_function_internal_arg_pointer)
 286           delete_insn (insn);
 287       }
 288
 289   /* Now iterate optimizing jumps until nothing changes over one pass.  */
 290   changed = 1;
 291   old_max_reg = max_reg_num ();
 292   while (changed)
 293     {
 294       changed = 0;
 295
 296       for (insn = f; insn; insn = next)
 297         {
 298           rtx reallabelprev;
 299           rtx temp, temp1, temp2 = NULL_RTX;
 300           rtx temp4 ATTRIBUTE_UNUSED;
 301           rtx nlabel;
 302           int this_is_any_uncondjump;
 303           int this_is_any_condjump;
 304           int this_is_onlyjump;
 305
 306           next = NEXT_INSN (insn);
 307
 308           /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
 309              jump.  Try to optimize by duplicating the loop exit test if so.
 310              This is only safe immediately after regscan, because it uses
 311              the values of regno_first_uid and regno_last_uid.  */
 312           if (after_regscan && GET_CODE (insn) == NOTE
 313               && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 314               && (temp1 = next_nonnote_insn (insn)) != 0
 315               && any_uncondjump_p (temp1)
 316               && onlyjump_p (temp1))
 317             {
 318               temp = PREV_INSN (insn);
 319               if (duplicate_loop_exit_test (insn))
 320                 {
 321                   changed = 1;
 322                   next = NEXT_INSN (temp);
 323                   continue;
 324                 }
 325             }
 326
 327           if (GET_CODE (insn) != JUMP_INSN)
 328             continue;
 329
 330           this_is_any_condjump = any_condjump_p (insn);
 331           this_is_any_uncondjump = any_uncondjump_p (insn);
 332           this_is_onlyjump = onlyjump_p (insn);
 333
 334           /* Tension the labels in dispatch tables.  */
 335
 336           if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
 337             changed |= tension_vector_labels (PATTERN (insn), 0);
 338           if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 339             changed |= tension_vector_labels (PATTERN (insn), 1);
 340
 341           /* See if this jump goes to another jump and redirect if so.  */
 342           nlabel = follow_jumps (JUMP_LABEL (insn));
 343           if (nlabel != JUMP_LABEL (insn))
 344             changed |= redirect_jump (insn, nlabel, 1);
 345
 346           if (! optimize || minimal)
 347             continue;
 348
 349           /* If a dispatch table always goes to the same place,
 350              get rid of it and replace the insn that uses it.  */
 351
 352           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 353               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 354             {
 355               int i;
 356               rtx pat = PATTERN (insn);
 357               int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
 358               int len = XVECLEN (pat, diff_vec_p);
 359               rtx dispatch = prev_real_insn (insn);
 360               rtx set;
 361
 362               for (i = 0; i < len; i++)
 363                 if (XEXP (XVECEXP (pat, diff_vec_p, i), 0)
 364                     != XEXP (XVECEXP (pat, diff_vec_p, 0), 0))
 365                   break;
 366
 367               if (i == len
 368                   && dispatch != 0
 369                   && GET_CODE (dispatch) == JUMP_INSN
 370                   && JUMP_LABEL (dispatch) != 0
 371                   /* Don't mess with a casesi insn.
 372                      XXX according to the comment before computed_jump_p(),
 373                      all casesi insns should be a parallel of the jump
 374                      and a USE of a LABEL_REF.  */
 375                   && ! ((set = single_set (dispatch)) != NULL
 376                         && (GET_CODE (SET_SRC (set)) == IF_THEN_ELSE))
 377                   && next_real_insn (JUMP_LABEL (dispatch)) == insn)
 378                 {
 379                   redirect_tablejump (dispatch,
 380                                       XEXP (XVECEXP (pat, diff_vec_p, 0), 0));
 381                   changed = 1;
 382                 }
 383             }
 384
 385           reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 386
 387           /* Detect jump to following insn.  */
 388           if (reallabelprev == insn
 389               && (this_is_any_condjump || this_is_any_uncondjump)
 390               && this_is_onlyjump)
 391             {
 392               next = next_real_insn (JUMP_LABEL (insn));
 393               delete_jump (insn);
 394
 395               /* Remove the "inactive" but "real" insns (i.e. uses and
 396                  clobbers) in between here and there.  */
 397               temp = insn;
 398               while ((temp = next_real_insn (temp)) != next)
 399                 delete_insn (temp);
 400
 401               changed = 1;
 402               continue;
 403             }
 404
 405           /* Detect a conditional jump going to the same place
 406              as an immediately following unconditional jump.  */
 407           else if (this_is_any_condjump && this_is_onlyjump
 408                    && (temp = next_active_insn (insn)) != 0
 409                    && simplejump_p (temp)
 410                    && (next_active_insn (JUMP_LABEL (insn))
 411                        == next_active_insn (JUMP_LABEL (temp))))
 412             {
 413               /* Don't mess up test coverage analysis.  */
 414               temp2 = temp;
 415               if (flag_test_coverage && !reload_completed)
 416                 for (temp2 = insn; temp2 != temp; temp2 = NEXT_INSN (temp2))
 417                   if (GET_CODE (temp2) == NOTE && NOTE_LINE_NUMBER (temp2) > 0)
 418                     break;
 419
 420               if (temp2 == temp)
 421                 {
 422                   delete_jump (insn);
 423                   changed = 1;
 424                   continue;
 425                 }
 426             }
 427
 428           /* Detect a conditional jump jumping over an unconditional jump.  */
 429
 430           else if (this_is_any_condjump
 431                    && reallabelprev != 0
 432                    && GET_CODE (reallabelprev) == JUMP_INSN
 433                    && prev_active_insn (reallabelprev) == insn
 434                    && no_labels_between_p (insn, reallabelprev)
 435                    && any_uncondjump_p (reallabelprev)
 436                    && onlyjump_p (reallabelprev))
 437             {
 438               /* When we invert the unconditional jump, we will be
 439                  decrementing the usage count of its old label.
 440                  Make sure that we don't delete it now because that
 441                  might cause the following code to be deleted.  */
 442               rtx prev_uses = prev_nonnote_insn (reallabelprev);
 443               rtx prev_label = JUMP_LABEL (insn);
 444
 445               if (prev_label)
 446                 ++LABEL_NUSES (prev_label);
 447
 448               if (invert_jump (insn, JUMP_LABEL (reallabelprev), 1))
 449                 {
 450                   /* It is very likely that if there are USE insns before
 451                      this jump, they hold REG_DEAD notes.  These REG_DEAD
 452                      notes are no longer valid due to this optimization,
 453                      and will cause the life-analysis that following passes
 454                      (notably delayed-branch scheduling) to think that
 455                      these registers are dead when they are not.
 456
 457                      To prevent this trouble, we just remove the USE insns
 458                      from the insn chain.  */
 459
 460                   while (prev_uses && GET_CODE (prev_uses) == INSN
 461                          && GET_CODE (PATTERN (prev_uses)) == USE)
 462                     {
 463                       rtx useless = prev_uses;
 464                       prev_uses = prev_nonnote_insn (prev_uses);
 465                       delete_insn (useless);
 466                     }
 467
 468                   delete_insn (reallabelprev);
 469                   changed = 1;
 470                 }
 471
 472               /* We can now safely delete the label if it is unreferenced
 473                  since the delete_insn above has deleted the BARRIER.  */
 474               if (prev_label && --LABEL_NUSES (prev_label) == 0)
 475                 delete_insn (prev_label);
 476
 477               next = NEXT_INSN (insn);
 478             }
 479
 480           /* If we have an unconditional jump preceded by a USE, try to put
 481              the USE before the target and jump there.  This simplifies many
 482              of the optimizations below since we don't have to worry about
 483              dealing with these USE insns.  We only do this if the label
 484              being branch to already has the identical USE or if code
 485              never falls through to that label.  */
 486
 487           else if (this_is_any_uncondjump
 488                    && (temp = prev_nonnote_insn (insn)) != 0
 489                    && GET_CODE (temp) == INSN
 490                    && GET_CODE (PATTERN (temp)) == USE
 491                    && (temp1 = prev_nonnote_insn (JUMP_LABEL (insn))) != 0
 492                    && (GET_CODE (temp1) == BARRIER
 493                        || (GET_CODE (temp1) == INSN
 494                            && rtx_equal_p (PATTERN (temp), PATTERN (temp1))))
 495                    /* Don't do this optimization if we have a loop containing
 496                       only the USE instruction, and the loop start label has
 497                       a usage count of 1.  This is because we will redo this
 498                       optimization everytime through the outer loop, and jump
 499                       opt will never exit.  */
 500                    && ! ((temp2 = prev_nonnote_insn (temp)) != 0
 501                          && temp2 == JUMP_LABEL (insn)
 502                          && LABEL_NUSES (temp2) == 1))
 503             {
 504               if (GET_CODE (temp1) == BARRIER)
 505                 {
 506                   emit_insn_after (PATTERN (temp), temp1);
 507                   temp1 = NEXT_INSN (temp1);
 508                 }
 509
 510               delete_insn (temp);
 511               redirect_jump (insn, get_label_before (temp1), 1);
 512               reallabelprev = prev_real_insn (temp1);
 513               changed = 1;
 514               next = NEXT_INSN (insn);
 515             }
 516
 517 #ifdef HAVE_trap
 518           /* Detect a conditional jump jumping over an unconditional trap.  */
 519           if (HAVE_trap
 520               && this_is_any_condjump && this_is_onlyjump
 521               && reallabelprev != 0
 522               && GET_CODE (reallabelprev) == INSN
 523               && GET_CODE (PATTERN (reallabelprev)) == TRAP_IF
 524               && TRAP_CONDITION (PATTERN (reallabelprev)) == const_true_rtx
 525               && prev_active_insn (reallabelprev) == insn
 526               && no_labels_between_p (insn, reallabelprev)
 527               && (temp2 = get_condition (insn, &temp4))
 528               && can_reverse_comparison_p (temp2, insn))
 529             {
 530               rtx new = gen_cond_trap (reverse_condition (GET_CODE (temp2)),
 531                                        XEXP (temp2, 0), XEXP (temp2, 1),
 532                                        TRAP_CODE (PATTERN (reallabelprev)));
 533
 534               if (new)
 535                 {
 536                   emit_insn_before (new, temp4);
 537                   delete_insn (reallabelprev);
 538                   delete_jump (insn);
 539                   changed = 1;
 540                   continue;
 541                 }
 542             }
 543           /* Detect a jump jumping to an unconditional trap.  */
 544           else if (HAVE_trap && this_is_onlyjump
 545                    && (temp = next_active_insn (JUMP_LABEL (insn)))
 546                    && GET_CODE (temp) == INSN
 547                    && GET_CODE (PATTERN (temp)) == TRAP_IF
 548                    && (this_is_any_uncondjump
 549                        || (this_is_any_condjump
 550                            && (temp2 = get_condition (insn, &temp4)))))
 551             {
 552               rtx tc = TRAP_CONDITION (PATTERN (temp));
 553
 554               if (tc == const_true_rtx
 555                   || (! this_is_any_uncondjump && rtx_equal_p (temp2, tc)))
 556                 {
 557                   rtx new;
 558                   /* Replace an unconditional jump to a trap with a trap.  */
 559                   if (this_is_any_uncondjump)
 560                     {
 561                       emit_barrier_after (emit_insn_before (gen_trap (), insn));
 562                       delete_jump (insn);
 563                       changed = 1;
 564                       continue;
 565                     }
 566                   new = gen_cond_trap (GET_CODE (temp2), XEXP (temp2, 0),
 567                                        XEXP (temp2, 1),
 568                                        TRAP_CODE (PATTERN (temp)));
 569                   if (new)
 570                     {
 571                       emit_insn_before (new, temp4);
 572                       delete_jump (insn);
 573                       changed = 1;
 574                       continue;
 575                     }
 576                 }
 577               /* If the trap condition and jump condition are mutually
 578                  exclusive, redirect the jump to the following insn.  */
 579               else if (GET_RTX_CLASS (GET_CODE (tc)) == '<'
 580                        && this_is_any_condjump
 581                        && swap_condition (GET_CODE (temp2)) == GET_CODE (tc)
 582                        && rtx_equal_p (XEXP (tc, 0), XEXP (temp2, 0))
 583                        && rtx_equal_p (XEXP (tc, 1), XEXP (temp2, 1))
 584                        && redirect_jump (insn, get_label_after (temp), 1))
 585                 {
 586                   changed = 1;
 587                   continue;
 588                 }
 589             }
 590 #endif
 591           else
 592             {
 593               /* Now that the jump has been tensioned,
 594                  try cross jumping: check for identical code
 595                  before the jump and before its target label.  */
 596
 597               /* First, cross jumping of conditional jumps:  */
 598
 599               if (cross_jump && condjump_p (insn))
 600                 {
 601                   rtx newjpos, newlpos;
 602                   rtx x = prev_real_insn (JUMP_LABEL (insn));
 603
 604                   /* A conditional jump may be crossjumped
 605                      only if the place it jumps to follows
 606                      an opposing jump that comes back here.  */
 607
 608                   if (x != 0 && ! jump_back_p (x, insn))
 609                     /* We have no opposing jump;
 610                        cannot cross jump this insn.  */
 611                     x = 0;
 612
 613                   newjpos = 0;
 614                   /* TARGET is nonzero if it is ok to cross jump
 615                      to code before TARGET.  If so, see if matches.  */
 616                   if (x != 0)
 617                     find_cross_jump (insn, x, 2,
 618                                      &newjpos, &newlpos);
 619
 620                   if (newjpos != 0)
 621                     {
 622                       do_cross_jump (insn, newjpos, newlpos);
 623                       /* Make the old conditional jump
 624                          into an unconditional one.  */
 625                       SET_SRC (PATTERN (insn))
 626                         = gen_rtx_LABEL_REF (VOIDmode, JUMP_LABEL (insn));
 627                       INSN_CODE (insn) = -1;
 628                       emit_barrier_after (insn);
 629                       /* Add to jump_chain unless this is a new label
 630                          whose UID is too large.  */
 631                       if (INSN_UID (JUMP_LABEL (insn)) < max_jump_chain)
 632                         {
 633                           jump_chain[INSN_UID (insn)]
 634                             = jump_chain[INSN_UID (JUMP_LABEL (insn))];
 635                           jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
 636                         }
 637                       changed = 1;
 638                       next = insn;
 639                     }
 640                 }
 641
 642               /* Cross jumping of unconditional jumps:
 643                  a few differences.  */
 644
 645               if (cross_jump && simplejump_p (insn))
 646                 {
 647                   rtx newjpos, newlpos;
 648                   rtx target;
 649
 650                   newjpos = 0;
 651
 652                   /* TARGET is nonzero if it is ok to cross jump
 653                      to code before TARGET.  If so, see if matches.  */
 654                   find_cross_jump (insn, JUMP_LABEL (insn), 1,
 655                                    &newjpos, &newlpos);
 656
 657                   /* If cannot cross jump to code before the label,
 658                      see if we can cross jump to another jump to
 659                      the same label.  */
 660                   /* Try each other jump to this label.  */
 661                   if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
 662                     for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
 663                          target != 0 && newjpos == 0;
 664                          target = jump_chain[INSN_UID (target)])
 665                       if (target != insn
 666                           && JUMP_LABEL (target) == JUMP_LABEL (insn)
 667                           /* Ignore TARGET if it's deleted.  */
 668                           && ! INSN_DELETED_P (target))
 669                         find_cross_jump (insn, target, 2,
 670                                          &newjpos, &newlpos);
 671
 672                   if (newjpos != 0)
 673                     {
 674                       do_cross_jump (insn, newjpos, newlpos);
 675                       changed = 1;
 676                       next = insn;
 677                     }
 678                 }
 679
 680               /* This code was dead in the previous jump.c!  */
 681               if (cross_jump && GET_CODE (PATTERN (insn)) == RETURN)
 682                 {
 683                   /* Return insns all "jump to the same place"
 684                      so we can cross-jump between any two of them.  */
 685
 686                   rtx newjpos, newlpos, target;
 687
 688                   newjpos = 0;
 689
 690                   /* If cannot cross jump to code before the label,
 691                      see if we can cross jump to another jump to
 692                      the same label.  */
 693                   /* Try each other jump to this label.  */
 694                   for (target = jump_chain[0];
 695                        target != 0 && newjpos == 0;
 696                        target = jump_chain[INSN_UID (target)])
 697                     if (target != insn
 698                         && ! INSN_DELETED_P (target)
 699                         && GET_CODE (PATTERN (target)) == RETURN)
 700                       find_cross_jump (insn, target, 2,
 701                                        &newjpos, &newlpos);
 702
 703                   if (newjpos != 0)
 704                     {
 705                       do_cross_jump (insn, newjpos, newlpos);
 706                       changed = 1;
 707                       next = insn;
 708                     }
 709                 }
 710             }
 711         }
 712
 713       first = 0;
 714     }
 715
 716   /* Delete extraneous line number notes.
 717      Note that two consecutive notes for different lines are not really
 718      extraneous.  There should be some indication where that line belonged,
 719      even if it became empty.  */
 720
 721   {
 722     rtx last_note = 0;
 723
 724     for (insn = f; insn; insn = NEXT_INSN (insn))
 725       if (GET_CODE (insn) == NOTE)
 726         {
 727           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
 728             /* Any previous line note was for the prologue; gdb wants a new
 729                note after the prologue even if it is for the same line.  */
 730             last_note = NULL_RTX;
 731           else if (NOTE_LINE_NUMBER (insn) >= 0)
 732             {
 733               /* Delete this note if it is identical to previous note.  */
 734               if (last_note
 735                   && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
 736                   && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
 737                 {
 738                   delete_insn (insn);
 739                   continue;
 740                 }
 741
 742               last_note = insn;
 743             }
 744         }
 745   }
 746
 747 end:
 748   /* Clean up.  */
 749   free (jump_chain);
 750   jump_chain = 0;
 751 }
 752 \f
 753 /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
 754    notes whose labels don't occur in the insn any more.  Returns the
 755    largest INSN_UID found.  */
 756 static int
 757 init_label_info (f)
 758      rtx f;
 759 {
 760   int largest_uid = 0;
 761   rtx insn;
 762
 763   for (insn = f; insn; insn = NEXT_INSN (insn))
 764     {
 765       if (GET_CODE (insn) == CODE_LABEL)
 766         LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
 767       else if (GET_CODE (insn) == JUMP_INSN)
 768         JUMP_LABEL (insn) = 0;
 769       else if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 770         {
 771           rtx note, next;
 772
 773           for (note = REG_NOTES (insn); note; note = next)
 774             {
 775               next = XEXP (note, 1);
 776               if (REG_NOTE_KIND (note) == REG_LABEL
 777                   && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
 778                 remove_note (insn, note);
 779             }
 780         }
 781       if (INSN_UID (insn) > largest_uid)
 782         largest_uid = INSN_UID (insn);
 783     }
 784
 785   return largest_uid;
 786 }
 787
 788 /* Delete insns following barriers, up to next label.
 789
 790    Also delete no-op jumps created by gcse.  */
 791
 792 static void
 793 delete_barrier_successors (f)
 794      rtx f;
 795 {
 796   rtx insn;
 797   rtx set;
 798
 799   for (insn = f; insn;)
 800     {
 801       if (GET_CODE (insn) == BARRIER)
 802         {
 803           insn = NEXT_INSN (insn);
 804
 805           never_reached_warning (insn);
 806
 807           while (insn != 0 && GET_CODE (insn) != CODE_LABEL)
 808             {
 809               if (GET_CODE (insn) == NOTE
 810                   && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
 811                 insn = NEXT_INSN (insn);
 812               else
 813                 insn = delete_insn (insn);
 814             }
 815           /* INSN is now the code_label.  */
 816         }
 817
 818       /* Also remove (set (pc) (pc)) insns which can be created by
 819          gcse.  We eliminate such insns now to avoid having them
 820          cause problems later.  */
 821       else if (GET_CODE (insn) == JUMP_INSN
 822                && (set = pc_set (insn)) != NULL
 823                && SET_SRC (set) == pc_rtx
 824                && SET_DEST (set) == pc_rtx
 825                && onlyjump_p (insn))
 826         insn = delete_insn (insn);
 827
 828       else
 829         insn = NEXT_INSN (insn);
 830     }
 831 }
 832
 833 /* Mark the label each jump jumps to.
 834    Combine consecutive labels, and count uses of labels.
 835
 836    For each label, make a chain (using `jump_chain')
 837    of all the *unconditional* jumps that jump to it;
 838    also make a chain of all returns.
 839
 840    CROSS_JUMP indicates whether we are doing cross jumping
 841    and if we are whether we will be paying attention to
 842    death notes or not.  */
 843
 844 static void
 845 mark_all_labels (f, cross_jump)
 846      rtx f;
 847      int cross_jump;
 848 {
 849   rtx insn;
 850
 851   for (insn = f; insn; insn = NEXT_INSN (insn))
 852     if (INSN_P (insn))
 853       {
 854         if (GET_CODE (insn) == CALL_INSN
 855             && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 856           {
 857             mark_all_labels (XEXP (PATTERN (insn), 0), cross_jump);
 858             mark_all_labels (XEXP (PATTERN (insn), 1), cross_jump);
 859             mark_all_labels (XEXP (PATTERN (insn), 2), cross_jump);
 860             continue;
 861           }
 862
 863         mark_jump_label (PATTERN (insn), insn, cross_jump, 0);
 864         if (! INSN_DELETED_P (insn) && GET_CODE (insn) == JUMP_INSN)
 865           {
 866             /* When we know the LABEL_REF contained in a REG used in
 867                an indirect jump, we'll have a REG_LABEL note so that
 868                flow can tell where it's going.  */
 869             if (JUMP_LABEL (insn) == 0)
 870               {
 871                 rtx label_note = find_reg_note (insn, REG_LABEL, NULL_RTX);
 872                 if (label_note)
 873                   {
 874                     /* But a LABEL_REF around the REG_LABEL note, so
 875                        that we can canonicalize it.  */
 876                     rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
 877                                                        XEXP (label_note, 0));
 878
 879                     mark_jump_label (label_ref, insn, cross_jump, 0);
 880                     XEXP (label_note, 0) = XEXP (label_ref, 0);
 881                     JUMP_LABEL (insn) = XEXP (label_note, 0);
 882                   }
 883               }
 884             if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
 885               {
 886                 jump_chain[INSN_UID (insn)]
 887                   = jump_chain[INSN_UID (JUMP_LABEL (insn))];
 888                 jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
 889               }
 890             if (GET_CODE (PATTERN (insn)) == RETURN)
 891               {
 892                 jump_chain[INSN_UID (insn)] = jump_chain[0];
 893                 jump_chain[0] = insn;
 894               }
 895           }
 896       }
 897 }
 898
 899 /* Delete all labels already not referenced.
 900    Also find and return the last insn.  */
 901
 902 static rtx
 903 delete_unreferenced_labels (f)
 904      rtx f;
 905 {
 906   rtx final = NULL_RTX;
 907   rtx insn;
 908
 909   for (insn = f; insn;)
 910     {
 911       if (GET_CODE (insn) == CODE_LABEL
 912           && LABEL_NUSES (insn) == 0
 913           && LABEL_ALTERNATE_NAME (insn) == NULL)
 914         insn = delete_insn (insn);
 915       else
 916         {
 917           final = insn;
 918           insn = NEXT_INSN (insn);
 919         }
 920     }
 921
 922   return final;
 923 }
 924
 925 /* Delete various simple forms of moves which have no necessary
 926    side effect.  */
 927
 928 static void
 929 delete_noop_moves (f)
 930      rtx f;
 931 {
 932   rtx insn, next;
 933
 934   for (insn = f; insn;)
 935     {
 936       next = NEXT_INSN (insn);
 937
 938       if (GET_CODE (insn) == INSN)
 939         {
 940           register rtx body = PATTERN (insn);
 941
 942           /* Detect and delete no-op move instructions
 943              resulting from not allocating a parameter in a register.  */
 944
 945           if (GET_CODE (body) == SET
 946               && (SET_DEST (body) == SET_SRC (body)
 947                   || (GET_CODE (SET_DEST (body)) == MEM
 948                       && GET_CODE (SET_SRC (body)) == MEM
 949                       && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
 950               && ! (GET_CODE (SET_DEST (body)) == MEM
 951                     && MEM_VOLATILE_P (SET_DEST (body)))
 952               && ! (GET_CODE (SET_SRC (body)) == MEM
 953                     && MEM_VOLATILE_P (SET_SRC (body))))
 954             delete_computation (insn);
 955
 956           /* Detect and ignore no-op move instructions
 957              resulting from smart or fortuitous register allocation.  */
 958
 959           else if (GET_CODE (body) == SET)
 960             {
 961               int sreg = true_regnum (SET_SRC (body));
 962               int dreg = true_regnum (SET_DEST (body));
 963
 964               if (sreg == dreg && sreg >= 0)
 965                 delete_insn (insn);
 966               else if (sreg >= 0 && dreg >= 0)
 967                 {
 968                   rtx trial;
 969                   rtx tem = find_equiv_reg (NULL_RTX, insn, 0,
 970                                             sreg, NULL_PTR, dreg,
 971                                             GET_MODE (SET_SRC (body)));
 972
 973                   if (tem != 0
 974                       && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
 975                     {
 976                       /* DREG may have been the target of a REG_DEAD note in
 977                          the insn which makes INSN redundant.  If so, reorg
 978                          would still think it is dead.  So search for such a
 979                          note and delete it if we find it.  */
 980                       if (! find_regno_note (insn, REG_UNUSED, dreg))
 981                         for (trial = prev_nonnote_insn (insn);
 982                              trial && GET_CODE (trial) != CODE_LABEL;
 983                              trial = prev_nonnote_insn (trial))
 984                           if (find_regno_note (trial, REG_DEAD, dreg))
 985                             {
 986                               remove_death (dreg, trial);
 987                               break;
 988                             }
 989
 990                       /* Deleting insn could lose a death-note for SREG.  */
 991                       if ((trial = find_regno_note (insn, REG_DEAD, sreg)))
 992                         {
 993                           /* Change this into a USE so that we won't emit
 994                              code for it, but still can keep the note.  */
 995                           PATTERN (insn)
 996                             = gen_rtx_USE (VOIDmode, XEXP (trial, 0));
 997                           INSN_CODE (insn) = -1;
 998                           /* Remove all reg notes but the REG_DEAD one.  */
 999                           REG_NOTES (insn) = trial;
1000                           XEXP (trial, 1) = NULL_RTX;
1001                         }
1002                       else
1003                         delete_insn (insn);
1004                     }
1005                 }
1006               else if (dreg >= 0 && CONSTANT_P (SET_SRC (body))
1007                        && find_equiv_reg (SET_SRC (body), insn, 0, dreg,
1008                                           NULL_PTR, 0,
1009                                           GET_MODE (SET_DEST (body))))
1010                 {
1011                   /* This handles the case where we have two consecutive
1012                      assignments of the same constant to pseudos that didn't
1013                      get a hard reg.  Each SET from the constant will be
1014                      converted into a SET of the spill register and an
1015                      output reload will be made following it.  This produces
1016                      two loads of the same constant into the same spill
1017                      register.  */
1018
1019                   rtx in_insn = insn;
1020
1021                   /* Look back for a death note for the first reg.
1022                      If there is one, it is no longer accurate.  */
1023                   while (in_insn && GET_CODE (in_insn) != CODE_LABEL)
1024                     {
1025                       if ((GET_CODE (in_insn) == INSN
1026                            || GET_CODE (in_insn) == JUMP_INSN)
1027                           && find_regno_note (in_insn, REG_DEAD, dreg))
1028                         {
1029                           remove_death (dreg, in_insn);
1030                           break;
1031                         }
1032                       in_insn = PREV_INSN (in_insn);
1033                     }
1034
1035                   /* Delete the second load of the value.  */
1036                   delete_insn (insn);
1037                 }
1038             }
1039           else if (GET_CODE (body) == PARALLEL)
1040             {
1041               /* If each part is a set between two identical registers or
1042                  a USE or CLOBBER, delete the insn.  */
1043               int i, sreg, dreg;
1044               rtx tem;
1045
1046               for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1047                 {
1048                   tem = XVECEXP (body, 0, i);
1049                   if (GET_CODE (tem) == USE || GET_CODE (tem) == CLOBBER)
1050                     continue;
1051
1052                   if (GET_CODE (tem) != SET
1053                       || (sreg = true_regnum (SET_SRC (tem))) < 0
1054                       || (dreg = true_regnum (SET_DEST (tem))) < 0
1055                       || dreg != sreg)
1056                     break;
1057                 }
1058
1059               if (i < 0)
1060                 delete_insn (insn);
1061             }
1062           /* Also delete insns to store bit fields if they are no-ops.  */
1063           /* Not worth the hair to detect this in the big-endian case.  */
1064           else if (! BYTES_BIG_ENDIAN
1065                    && GET_CODE (body) == SET
1066                    && GET_CODE (SET_DEST (body)) == ZERO_EXTRACT
1067                    && XEXP (SET_DEST (body), 2) == const0_rtx
1068                    && XEXP (SET_DEST (body), 0) == SET_SRC (body)
1069                    && ! (GET_CODE (SET_SRC (body)) == MEM
1070                          && MEM_VOLATILE_P (SET_SRC (body))))
1071             delete_insn (insn);
1072         }
1073       insn = next;
1074     }
1075 }
1076
1077 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
1078    jump.  Assume that this unconditional jump is to the exit test code.  If
1079    the code is sufficiently simple, make a copy of it before INSN,
1080    followed by a jump to the exit of the loop.  Then delete the unconditional
1081    jump after INSN.
1082
1083    Return 1 if we made the change, else 0.
1084
1085    This is only safe immediately after a regscan pass because it uses the
1086    values of regno_first_uid and regno_last_uid.  */
1087
1088 static int
1089 duplicate_loop_exit_test (loop_start)
1090      rtx loop_start;
1091 {
1092   rtx insn, set, reg, p, link;
1093   rtx copy = 0, first_copy = 0;
1094   int num_insns = 0;
1095   rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
1096   rtx lastexit;
1097   int max_reg = max_reg_num ();
1098   rtx *reg_map = 0;
1099
1100   /* Scan the exit code.  We do not perform this optimization if any insn:
1101
1102          is a CALL_INSN
1103          is a CODE_LABEL
1104          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
1105          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
1106          is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
1107               is not valid.
1108
1109      We also do not do this if we find an insn with ASM_OPERANDS.  While
1110      this restriction should not be necessary, copying an insn with
1111      ASM_OPERANDS can confuse asm_noperands in some cases.
1112
1113      Also, don't do this if the exit code is more than 20 insns.  */
1114
1115   for (insn = exitcode;
1116        insn
1117        && ! (GET_CODE (insn) == NOTE
1118              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
1119        insn = NEXT_INSN (insn))
1120     {
1121       switch (GET_CODE (insn))
1122         {
1123         case CODE_LABEL:
1124         case CALL_INSN:
1125           return 0;
1126         case NOTE:
1127           /* We could be in front of the wrong NOTE_INSN_LOOP_END if there is
1128              a jump immediately after the loop start that branches outside
1129              the loop but within an outer loop, near the exit test.
1130              If we copied this exit test and created a phony
1131              NOTE_INSN_LOOP_VTOP, this could make instructions immediately
1132              before the exit test look like these could be safely moved
1133              out of the loop even if they actually may be never executed.
1134              This can be avoided by checking here for NOTE_INSN_LOOP_CONT.  */
1135
1136           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1137               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
1138             return 0;
1139
1140           if (optimize < 2
1141               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
1142                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
1143             /* If we were to duplicate this code, we would not move
1144                the BLOCK notes, and so debugging the moved code would
1145                be difficult.  Thus, we only move the code with -O2 or
1146                higher.  */
1147             return 0;
1148
1149           break;
1150         case JUMP_INSN:
1151         case INSN:
1152           /* The code below would grossly mishandle REG_WAS_0 notes,
1153              so get rid of them here.  */
1154           while ((p = find_reg_note (insn, REG_WAS_0, NULL_RTX)) != 0)
1155             remove_note (insn, p);
1156           if (++num_insns > 20
1157               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
1158               || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
1159             return 0;
1160           break;
1161         default:
1162           break;
1163         }
1164     }
1165
1166   /* Unless INSN is zero, we can do the optimization.  */
1167   if (insn == 0)
1168     return 0;
1169
1170   lastexit = insn;
1171
1172   /* See if any insn sets a register only used in the loop exit code and
1173      not a user variable.  If so, replace it with a new register.  */
1174   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
1175     if (GET_CODE (insn) == INSN
1176         && (set = single_set (insn)) != 0
1177         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
1178             || (GET_CODE (reg) == SUBREG
1179                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
1180         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
1181         && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
1182       {
1183         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
1184           if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
1185             break;
1186
1187         if (p != lastexit)
1188           {
1189             /* We can do the replacement.  Allocate reg_map if this is the
1190                first replacement we found.  */
1191             if (reg_map == 0)
1192               reg_map = (rtx *) xcalloc (max_reg, sizeof (rtx));
1193
1194             REG_LOOP_TEST_P (reg) = 1;
1195
1196             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
1197           }
1198       }
1199
1200   /* Now copy each insn.  */
1201   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
1202     {
1203       switch (GET_CODE (insn))
1204         {
1205         case BARRIER:
1206           copy = emit_barrier_before (loop_start);
1207           break;
1208         case NOTE:
1209           /* Only copy line-number notes.  */
1210           if (NOTE_LINE_NUMBER (insn) >= 0)
1211             {
1212               copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
1213               NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
1214             }
1215           break;
1216
1217         case INSN:
1218           copy = emit_insn_before (copy_insn (PATTERN (insn)), loop_start);
1219           if (reg_map)
1220             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
1221
1222           mark_jump_label (PATTERN (copy), copy, 0, 0);
1223
1224           /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
1225              make them.  */
1226           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1227             if (REG_NOTE_KIND (link) != REG_LABEL)
1228               {
1229                 if (GET_CODE (link) == EXPR_LIST)
1230                   REG_NOTES (copy)
1231                     = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
1232                                                       XEXP (link, 0),
1233                                                       REG_NOTES (copy)));
1234                 else
1235                   REG_NOTES (copy)
1236                     = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
1237                                                       XEXP (link, 0),
1238                                                       REG_NOTES (copy)));
1239               }
1240
1241           if (reg_map && REG_NOTES (copy))
1242             replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
1243           break;
1244
1245         case JUMP_INSN:
1246           copy = emit_jump_insn_before (copy_insn (PATTERN (insn)),
1247                                         loop_start);
1248           if (reg_map)
1249             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
1250           mark_jump_label (PATTERN (copy), copy, 0, 0);
1251           if (REG_NOTES (insn))
1252             {
1253               REG_NOTES (copy) = copy_insn_1 (REG_NOTES (insn));
1254               if (reg_map)
1255                 replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
1256             }
1257
1258           /* If this is a simple jump, add it to the jump chain.  */
1259
1260           if (INSN_UID (copy) < max_jump_chain && JUMP_LABEL (copy)
1261               && simplejump_p (copy))
1262             {
1263               jump_chain[INSN_UID (copy)]
1264                 = jump_chain[INSN_UID (JUMP_LABEL (copy))];
1265               jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
1266             }
1267           break;
1268
1269         default:
1270           abort ();
1271         }
1272
1273       /* Record the first insn we copied.  We need it so that we can
1274          scan the copied insns for new pseudo registers.  */
1275       if (! first_copy)
1276         first_copy = copy;
1277     }
1278
1279   /* Now clean up by emitting a jump to the end label and deleting the jump
1280      at the start of the loop.  */
1281   if (! copy || GET_CODE (copy) != BARRIER)
1282     {
1283       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
1284                                     loop_start);
1285
1286       /* Record the first insn we copied.  We need it so that we can
1287          scan the copied insns for new pseudo registers.   This may not
1288          be strictly necessary since we should have copied at least one
1289          insn above.  But I am going to be safe.  */
1290       if (! first_copy)
1291         first_copy = copy;
1292
1293       mark_jump_label (PATTERN (copy), copy, 0, 0);
1294       if (INSN_UID (copy) < max_jump_chain
1295           && INSN_UID (JUMP_LABEL (copy)) < max_jump_chain)
1296         {
1297           jump_chain[INSN_UID (copy)]
1298             = jump_chain[INSN_UID (JUMP_LABEL (copy))];
1299           jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
1300         }
1301       emit_barrier_before (loop_start);
1302     }
1303
1304   /* Now scan from the first insn we copied to the last insn we copied
1305      (copy) for new pseudo registers.  Do this after the code to jump to
1306      the end label since that might create a new pseudo too.  */
1307   reg_scan_update (first_copy, copy, max_reg);
1308
1309   /* Mark the exit code as the virtual top of the converted loop.  */
1310   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
1311
1312   delete_insn (next_nonnote_insn (loop_start));
1313
1314   /* Clean up.  */
1315   if (reg_map)
1316     free (reg_map);
1317
1318   return 1;
1319 }
1320 \f
1321 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, loop-end,
1322    eh-beg, eh-end notes between START and END out before START.  Assume that
1323    END is not such a note.  START may be such a note.  Returns the value
1324    of the new starting insn, which may be different if the original start
1325    was such a note.  */
1326
1327 rtx
1328 squeeze_notes (start, end)
1329      rtx start, end;
1330 {
1331   rtx insn;
1332   rtx next;
1333
1334   for (insn = start; insn != end; insn = next)
1335     {
1336       next = NEXT_INSN (insn);
1337       if (GET_CODE (insn) == NOTE
1338           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
1339               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
1340               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1341               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1342               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
1343               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP
1344               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1345               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1346         {
1347           if (insn == start)
1348             start = next;
1349           else
1350             {
1351               rtx prev = PREV_INSN (insn);
1352               PREV_INSN (insn) = PREV_INSN (start);
1353               NEXT_INSN (insn) = start;
1354               NEXT_INSN (PREV_INSN (insn)) = insn;
1355               PREV_INSN (NEXT_INSN (insn)) = insn;
1356               NEXT_INSN (prev) = next;
1357               PREV_INSN (next) = prev;
1358             }
1359         }
1360     }
1361
1362   return start;
1363 }
1364 \f
1365 /* Compare the instructions before insn E1 with those before E2
1366    to find an opportunity for cross jumping.
1367    (This means detecting identical sequences of insns followed by
1368    jumps to the same place, or followed by a label and a jump
1369    to that label, and replacing one with a jump to the other.)
1370
1371    Assume E1 is a jump that jumps to label E2
1372    (that is not always true but it might as well be).
1373    Find the longest possible equivalent sequences
1374    and store the first insns of those sequences into *F1 and *F2.
1375    Store zero there if no equivalent preceding instructions are found.
1376
1377    We give up if we find a label in stream 1.
1378    Actually we could transfer that label into stream 2.  */
1379
1380 static void
1381 find_cross_jump (e1, e2, minimum, f1, f2)
1382      rtx e1, e2;
1383      int minimum;
1384      rtx *f1, *f2;
1385 {
1386   register rtx i1 = e1, i2 = e2;
1387   register rtx p1, p2;
1388   int lose = 0;
1389
1390   rtx last1 = 0, last2 = 0;
1391   rtx afterlast1 = 0, afterlast2 = 0;
1392
1393   *f1 = 0;
1394   *f2 = 0;
1395
1396   while (1)
1397     {
1398       i1 = prev_nonnote_insn (i1);
1399
1400       i2 = PREV_INSN (i2);
1401       while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
1402         i2 = PREV_INSN (i2);
1403
1404       if (i1 == 0)
1405         break;
1406
1407       /* Don't allow the range of insns preceding E1 or E2
1408          to include the other (E2 or E1).  */
1409       if (i2 == e1 || i1 == e2)
1410         break;
1411
1412       /* If we will get to this code by jumping, those jumps will be
1413          tensioned to go directly to the new label (before I2),
1414          so this cross-jumping won't cost extra.  So reduce the minimum.  */
1415       if (GET_CODE (i1) == CODE_LABEL)
1416         {
1417           --minimum;
1418           break;
1419         }
1420
1421       if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
1422         break;
1423
1424       /* Avoid moving insns across EH regions if either of the insns
1425          can throw.  */
1426       if (flag_exceptions
1427           && (asynchronous_exceptions || GET_CODE (i1) == CALL_INSN)
1428           && !in_same_eh_region (i1, i2))
1429         break;
1430
1431       p1 = PATTERN (i1);
1432       p2 = PATTERN (i2);
1433
1434       /* If this is a CALL_INSN, compare register usage information.
1435          If we don't check this on stack register machines, the two
1436          CALL_INSNs might be merged leaving reg-stack.c with mismatching
1437          numbers of stack registers in the same basic block.
1438          If we don't check this on machines with delay slots, a delay slot may
1439          be filled that clobbers a parameter expected by the subroutine.
1440
1441          ??? We take the simple route for now and assume that if they're
1442          equal, they were constructed identically.  */
1443
1444       if (GET_CODE (i1) == CALL_INSN
1445           && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1446                             CALL_INSN_FUNCTION_USAGE (i2)))
1447         lose = 1;
1448
1449 #ifdef STACK_REGS
1450       /* If cross_jump_death_matters is not 0, the insn's mode
1451          indicates whether or not the insn contains any stack-like
1452          regs.  */
1453
1454       if (!lose && cross_jump_death_matters && stack_regs_mentioned (i1))
1455         {
1456           /* If register stack conversion has already been done, then
1457              death notes must also be compared before it is certain that
1458              the two instruction streams match.  */
1459
1460           rtx note;
1461           HARD_REG_SET i1_regset, i2_regset;
1462
1463           CLEAR_HARD_REG_SET (i1_regset);
1464           CLEAR_HARD_REG_SET (i2_regset);
1465
1466           for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1467             if (REG_NOTE_KIND (note) == REG_DEAD
1468                 && STACK_REG_P (XEXP (note, 0)))
1469               SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1470
1471           for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1472             if (REG_NOTE_KIND (note) == REG_DEAD
1473                 && STACK_REG_P (XEXP (note, 0)))
1474               SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1475
1476           GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
1477
1478           lose = 1;
1479
1480         done:
1481           ;
1482         }
1483 #endif
1484
1485       /* Don't allow old-style asm or volatile extended asms to be accepted
1486          for cross jumping purposes.  It is conceptually correct to allow
1487          them, since cross-jumping preserves the dynamic instruction order
1488          even though it is changing the static instruction order.  However,
1489          if an asm is being used to emit an assembler pseudo-op, such as
1490          the MIPS `.set reorder' pseudo-op, then the static instruction order
1491          matters and it must be preserved.  */
1492       if (GET_CODE (p1) == ASM_INPUT || GET_CODE (p2) == ASM_INPUT
1493           || (GET_CODE (p1) == ASM_OPERANDS && MEM_VOLATILE_P (p1))
1494           || (GET_CODE (p2) == ASM_OPERANDS && MEM_VOLATILE_P (p2)))
1495         lose = 1;
1496
1497       if (lose || GET_CODE (p1) != GET_CODE (p2)
1498           || ! rtx_renumbered_equal_p (p1, p2))
1499         {
1500           /* The following code helps take care of G++ cleanups.  */
1501           rtx equiv1;
1502           rtx equiv2;
1503
1504           if (!lose && GET_CODE (p1) == GET_CODE (p2)
1505               && ((equiv1 = find_reg_note (i1, REG_EQUAL, NULL_RTX)) != 0
1506                   || (equiv1 = find_reg_note (i1, REG_EQUIV, NULL_RTX)) != 0)
1507               && ((equiv2 = find_reg_note (i2, REG_EQUAL, NULL_RTX)) != 0
1508                   || (equiv2 = find_reg_note (i2, REG_EQUIV, NULL_RTX)) != 0)
1509               /* If the equivalences are not to a constant, they may
1510                  reference pseudos that no longer exist, so we can't
1511                  use them.  */
1512               && CONSTANT_P (XEXP (equiv1, 0))
1513               && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1514             {
1515               rtx s1 = single_set (i1);
1516               rtx s2 = single_set (i2);
1517               if (s1 != 0 && s2 != 0
1518                   && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
1519                 {
1520                   validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
1521                   validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
1522                   if (! rtx_renumbered_equal_p (p1, p2))
1523                     cancel_changes (0);
1524                   else if (apply_change_group ())
1525                     goto win;
1526                 }
1527             }
1528
1529           /* Insns fail to match; cross jumping is limited to the following
1530              insns.  */
1531
1532 #ifdef HAVE_cc0
1533           /* Don't allow the insn after a compare to be shared by
1534              cross-jumping unless the compare is also shared.
1535              Here, if either of these non-matching insns is a compare,
1536              exclude the following insn from possible cross-jumping.  */
1537           if (sets_cc0_p (p1) || sets_cc0_p (p2))
1538             last1 = afterlast1, last2 = afterlast2, ++minimum;
1539 #endif
1540
1541           /* If cross-jumping here will feed a jump-around-jump
1542              optimization, this jump won't cost extra, so reduce
1543              the minimum.  */
1544           if (GET_CODE (i1) == JUMP_INSN
1545               && JUMP_LABEL (i1)
1546               && prev_real_insn (JUMP_LABEL (i1)) == e1)
1547             --minimum;
1548           break;
1549         }
1550
1551     win:
1552       if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
1553         {
1554           /* Ok, this insn is potentially includable in a cross-jump here.  */
1555           afterlast1 = last1, afterlast2 = last2;
1556           last1 = i1, last2 = i2, --minimum;
1557         }
1558     }
1559
1560   if (minimum <= 0 && last1 != 0 && last1 != e1)
1561     *f1 = last1, *f2 = last2;
1562 }
1563
1564 static void
1565 do_cross_jump (insn, newjpos, newlpos)
1566      rtx insn, newjpos, newlpos;
1567 {
1568   /* Find an existing label at this point
1569      or make a new one if there is none.  */
1570   register rtx label = get_label_before (newlpos);
1571
1572   /* Make the same jump insn jump to the new point.  */
1573   if (GET_CODE (PATTERN (insn)) == RETURN)
1574     {
1575       /* Remove from jump chain of returns.  */
1576       delete_from_jump_chain (insn);
1577       /* Change the insn.  */
1578       PATTERN (insn) = gen_jump (label);
1579       INSN_CODE (insn) = -1;
1580       JUMP_LABEL (insn) = label;
1581       LABEL_NUSES (label)++;
1582       /* Add to new the jump chain.  */
1583       if (INSN_UID (label) < max_jump_chain
1584           && INSN_UID (insn) < max_jump_chain)
1585         {
1586           jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (label)];
1587           jump_chain[INSN_UID (label)] = insn;
1588         }
1589     }
1590   else
1591     redirect_jump (insn, label, 1);
1592
1593   /* Delete the matching insns before the jump.  Also, remove any REG_EQUAL
1594      or REG_EQUIV note in the NEWLPOS stream that isn't also present in
1595      the NEWJPOS stream.  */
1596
1597   while (newjpos != insn)
1598     {
1599       rtx lnote;
1600
1601       for (lnote = REG_NOTES (newlpos); lnote; lnote = XEXP (lnote, 1))
1602         if ((REG_NOTE_KIND (lnote) == REG_EQUAL
1603              || REG_NOTE_KIND (lnote) == REG_EQUIV)
1604             && ! find_reg_note (newjpos, REG_EQUAL, XEXP (lnote, 0))
1605             && ! find_reg_note (newjpos, REG_EQUIV, XEXP (lnote, 0)))
1606           remove_note (newlpos, lnote);
1607
1608       delete_insn (newjpos);
1609       newjpos = next_real_insn (newjpos);
1610       newlpos = next_real_insn (newlpos);
1611     }
1612 }
1613 \f
1614 /* Return the label before INSN, or put a new label there.  */
1615
1616 rtx
1617 get_label_before (insn)
1618      rtx insn;
1619 {
1620   rtx label;
1621
1622   /* Find an existing label at this point
1623      or make a new one if there is none.  */
1624   label = prev_nonnote_insn (insn);
1625
1626   if (label == 0 || GET_CODE (label) != CODE_LABEL)
1627     {
1628       rtx prev = PREV_INSN (insn);
1629
1630       label = gen_label_rtx ();
1631       emit_label_after (label, prev);
1632       LABEL_NUSES (label) = 0;
1633     }
1634   return label;
1635 }
1636
1637 /* Return the label after INSN, or put a new label there.  */
1638
1639 rtx
1640 get_label_after (insn)
1641      rtx insn;
1642 {
1643   rtx label;
1644
1645   /* Find an existing label at this point
1646      or make a new one if there is none.  */
1647   label = next_nonnote_insn (insn);
1648
1649   if (label == 0 || GET_CODE (label) != CODE_LABEL)
1650     {
1651       label = gen_label_rtx ();
1652       emit_label_after (label, insn);
1653       LABEL_NUSES (label) = 0;
1654     }
1655   return label;
1656 }
1657 \f
1658 /* Return 1 if INSN is a jump that jumps to right after TARGET
1659    only on the condition that TARGET itself would drop through.
1660    Assumes that TARGET is a conditional jump.  */
1661
1662 static int
1663 jump_back_p (insn, target)
1664      rtx insn, target;
1665 {
1666   rtx cinsn, ctarget;
1667   enum rtx_code codei, codet;
1668   rtx set, tset;
1669
1670   if (! any_condjump_p (insn)
1671       || any_uncondjump_p (target)
1672       || target != prev_real_insn (JUMP_LABEL (insn)))
1673     return 0;
1674   set = pc_set (insn);
1675   tset = pc_set (target);
1676
1677   cinsn = XEXP (SET_SRC (set), 0);
1678   ctarget = XEXP (SET_SRC (tset), 0);
1679
1680   codei = GET_CODE (cinsn);
1681   codet = GET_CODE (ctarget);
1682
1683   if (XEXP (SET_SRC (set), 1) == pc_rtx)
1684     {
1685       if (! can_reverse_comparison_p (cinsn, insn))
1686         return 0;
1687       codei = reverse_condition (codei);
1688     }
1689
1690   if (XEXP (SET_SRC (tset), 2) == pc_rtx)
1691     {
1692       if (! can_reverse_comparison_p (ctarget, target))
1693         return 0;
1694       codet = reverse_condition (codet);
1695     }
1696
1697   return (codei == codet
1698           && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
1699           && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
1700 }
1701 \f
1702 /* Given a comparison, COMPARISON, inside a conditional jump insn, INSN,
1703    return non-zero if it is safe to reverse this comparison.  It is if our
1704    floating-point is not IEEE, if this is an NE or EQ comparison, or if
1705    this is known to be an integer comparison.  */
1706
1707 int
1708 can_reverse_comparison_p (comparison, insn)
1709      rtx comparison;
1710      rtx insn;
1711 {
1712   rtx arg0;
1713
1714   /* If this is not actually a comparison, we can't reverse it.  */
1715   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
1716     return 0;
1717
1718   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
1719       /* If this is an NE comparison, it is safe to reverse it to an EQ
1720          comparison and vice versa, even for floating point.  If no operands
1721          are NaNs, the reversal is valid.  If some operand is a NaN, EQ is
1722          always false and NE is always true, so the reversal is also valid.  */
1723       || flag_fast_math
1724       || GET_CODE (comparison) == NE
1725       || GET_CODE (comparison) == EQ)
1726     return 1;
1727
1728   arg0 = XEXP (comparison, 0);
1729
1730   /* Make sure ARG0 is one of the actual objects being compared.  If we
1731      can't do this, we can't be sure the comparison can be reversed.
1732
1733      Handle cc0 and a MODE_CC register.  */
1734   if ((GET_CODE (arg0) == REG && GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC)
1735 #ifdef HAVE_cc0
1736       || arg0 == cc0_rtx
1737 #endif
1738       )
1739     {
1740       rtx prev, set;
1741
1742       /* First see if the condition code mode alone if enough to say we can
1743          reverse the condition.  If not, then search backwards for a set of
1744          ARG0. We do not need to check for an insn clobbering it since valid
1745          code will contain set a set with no intervening clobber.  But
1746          stop when we reach a label.  */
1747 #ifdef REVERSIBLE_CC_MODE
1748       if (GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC
1749           && REVERSIBLE_CC_MODE (GET_MODE (arg0)))
1750         return 1;
1751 #endif
1752
1753       if (! insn)
1754         return 0;
1755
1756       for (prev = prev_nonnote_insn (insn);
1757            prev != 0 && GET_CODE (prev) != CODE_LABEL;
1758            prev = prev_nonnote_insn (prev))
1759         if ((set = single_set (prev)) != 0
1760             && rtx_equal_p (SET_DEST (set), arg0))
1761           {
1762             arg0 = SET_SRC (set);
1763
1764             if (GET_CODE (arg0) == COMPARE)
1765               arg0 = XEXP (arg0, 0);
1766             break;
1767           }
1768     }
1769
1770   /* We can reverse this if ARG0 is a CONST_INT or if its mode is
1771      not VOIDmode and neither a MODE_CC nor MODE_FLOAT type.  */
1772   return (GET_CODE (arg0) == CONST_INT
1773           || (GET_MODE (arg0) != VOIDmode
1774               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_CC
1775               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_FLOAT));
1776 }
1777
1778 /* Given an rtx-code for a comparison, return the code for the negated
1779    comparison.  If no such code exists, return UNKNOWN.
1780
1781    WATCH OUT!  reverse_condition is not safe to use on a jump that might
1782    be acting on the results of an IEEE floating point comparison, because
1783    of the special treatment of non-signaling nans in comparisons.
1784    Use can_reverse_comparison_p to be sure.  */
1785
1786 enum rtx_code
1787 reverse_condition (code)
1788      enum rtx_code code;
1789 {
1790   switch (code)
1791     {
1792     case EQ:
1793       return NE;
1794     case NE:
1795       return EQ;
1796     case GT:
1797       return LE;
1798     case GE:
1799       return LT;
1800     case LT:
1801       return GE;
1802     case LE:
1803       return GT;
1804     case GTU:
1805       return LEU;
1806     case GEU:
1807       return LTU;
1808     case LTU:
1809       return GEU;
1810     case LEU:
1811       return GTU;
1812     case UNORDERED:
1813       return ORDERED;
1814     case ORDERED:
1815       return UNORDERED;
1816
1817     case UNLT:
1818     case UNLE:
1819     case UNGT:
1820     case UNGE:
1821     case UNEQ:
1822     case LTGT:
1823       return UNKNOWN;
1824
1825     default:
1826       abort ();
1827     }
1828 }
1829
1830 /* Similar, but we're allowed to generate unordered comparisons, which
1831    makes it safe for IEEE floating-point.  Of course, we have to recognize
1832    that the target will support them too...  */
1833
1834 enum rtx_code
1835 reverse_condition_maybe_unordered (code)
1836      enum rtx_code code;
1837 {
1838   /* Non-IEEE formats don't have unordered conditions.  */
1839   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
1840     return reverse_condition (code);
1841
1842   switch (code)
1843     {
1844     case EQ:
1845       return NE;
1846     case NE:
1847       return EQ;
1848     case GT:
1849       return UNLE;
1850     case GE:
1851       return UNLT;
1852     case LT:
1853       return UNGE;
1854     case LE:
1855       return UNGT;
1856     case LTGT:
1857       return UNEQ;
1858     case GTU:
1859       return LEU;
1860     case GEU:
1861       return LTU;
1862     case LTU:
1863       return GEU;
1864     case LEU:
1865       return GTU;
1866     case UNORDERED:
1867       return ORDERED;
1868     case ORDERED:
1869       return UNORDERED;
1870     case UNLT:
1871       return GE;
1872     case UNLE:
1873       return GT;
1874     case UNGT:
1875       return LE;
1876     case UNGE:
1877       return LT;
1878     case UNEQ:
1879       return LTGT;
1880
1881     default:
1882       abort ();
1883     }
1884 }
1885
1886 /* Similar, but return the code when two operands of a comparison are swapped.
1887    This IS safe for IEEE floating-point.  */
1888
1889 enum rtx_code
1890 swap_condition (code)
1891      enum rtx_code code;
1892 {
1893   switch (code)
1894     {
1895     case EQ:
1896     case NE:
1897     case UNORDERED:
1898     case ORDERED:
1899     case UNEQ:
1900     case LTGT:
1901       return code;
1902
1903     case GT:
1904       return LT;
1905     case GE:
1906       return LE;
1907     case LT:
1908       return GT;
1909     case LE:
1910       return GE;
1911     case GTU:
1912       return LTU;
1913     case GEU:
1914       return LEU;
1915     case LTU:
1916       return GTU;
1917     case LEU:
1918       return GEU;
1919     case UNLT:
1920       return UNGT;
1921     case UNLE:
1922       return UNGE;
1923     case UNGT:
1924       return UNLT;
1925     case UNGE:
1926       return UNLE;
1927
1928     default:
1929       abort ();
1930     }
1931 }
1932
1933 /* Given a comparison CODE, return the corresponding unsigned comparison.
1934    If CODE is an equality comparison or already an unsigned comparison,
1935    CODE is returned.  */
1936
1937 enum rtx_code
1938 unsigned_condition (code)
1939      enum rtx_code code;
1940 {
1941   switch (code)
1942     {
1943     case EQ:
1944     case NE:
1945     case GTU:
1946     case GEU:
1947     case LTU:
1948     case LEU:
1949       return code;
1950
1951     case GT:
1952       return GTU;
1953     case GE:
1954       return GEU;
1955     case LT:
1956       return LTU;
1957     case LE:
1958       return LEU;
1959
1960     default:
1961       abort ();
1962     }
1963 }
1964
1965 /* Similarly, return the signed version of a comparison.  */
1966
1967 enum rtx_code
1968 signed_condition (code)
1969      enum rtx_code code;
1970 {
1971   switch (code)
1972     {
1973     case EQ:
1974     case NE:
1975     case GT:
1976     case GE:
1977     case LT:
1978     case LE:
1979       return code;
1980
1981     case GTU:
1982       return GT;
1983     case GEU:
1984       return GE;
1985     case LTU:
1986       return LT;
1987     case LEU:
1988       return LE;
1989
1990     default:
1991       abort ();
1992     }
1993 }
1994 \f
1995 /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
1996    truth of CODE1 implies the truth of CODE2.  */
1997
1998 int
1999 comparison_dominates_p (code1, code2)
2000      enum rtx_code code1, code2;
2001 {
2002   if (code1 == code2)
2003     return 1;
2004
2005   switch (code1)
2006     {
2007     case EQ:
2008       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
2009           || code2 == ORDERED)
2010         return 1;
2011       break;
2012
2013     case LT:
2014       if (code2 == LE || code2 == NE || code2 == ORDERED)
2015         return 1;
2016       break;
2017
2018     case GT:
2019       if (code2 == GE || code2 == NE || code2 == ORDERED)
2020         return 1;
2021       break;
2022
2023     case GE:
2024     case LE:
2025       if (code2 == ORDERED)
2026         return 1;
2027       break;
2028
2029     case LTGT:
2030       if (code2 == NE || code2 == ORDERED)
2031         return 1;
2032       break;
2033
2034     case LTU:
2035       if (code2 == LEU || code2 == NE)
2036         return 1;
2037       break;
2038
2039     case GTU:
2040       if (code2 == GEU || code2 == NE)
2041         return 1;
2042       break;
2043
2044     case UNORDERED:
2045       if (code2 == NE)
2046         return 1;
2047       break;
2048
2049     default:
2050       break;
2051     }
2052
2053   return 0;
2054 }
2055 \f
2056 /* Return 1 if INSN is an unconditional jump and nothing else.  */
2057
2058 int
2059 simplejump_p (insn)
2060      rtx insn;
2061 {
2062   return (GET_CODE (insn) == JUMP_INSN
2063           && GET_CODE (PATTERN (insn)) == SET
2064           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
2065           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
2066 }
2067
2068 /* Return nonzero if INSN is a (possibly) conditional jump
2069    and nothing more.
2070
2071    Use this function is deprecated, since we need to support combined
2072    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
2073
2074 int
2075 condjump_p (insn)
2076      rtx insn;
2077 {
2078   register rtx x = PATTERN (insn);
2079
2080   if (GET_CODE (x) != SET
2081       || GET_CODE (SET_DEST (x)) != PC)
2082     return 0;
2083
2084   x = SET_SRC (x);
2085   if (GET_CODE (x) == LABEL_REF)
2086     return 1;
2087   else
2088     return (GET_CODE (x) == IF_THEN_ELSE
2089             && ((GET_CODE (XEXP (x, 2)) == PC
2090                  && (GET_CODE (XEXP (x, 1)) == LABEL_REF
2091                      || GET_CODE (XEXP (x, 1)) == RETURN))
2092                 || (GET_CODE (XEXP (x, 1)) == PC
2093                     && (GET_CODE (XEXP (x, 2)) == LABEL_REF
2094                         || GET_CODE (XEXP (x, 2)) == RETURN))));
2095
2096   return 0;
2097 }
2098
2099 /* Return nonzero if INSN is a (possibly) conditional jump inside a
2100    PARALLEL.
2101
2102    Use this function is deprecated, since we need to support combined
2103    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
2104
2105 int
2106 condjump_in_parallel_p (insn)
2107      rtx insn;
2108 {
2109   register rtx x = PATTERN (insn);
2110
2111   if (GET_CODE (x) != PARALLEL)
2112     return 0;
2113   else
2114     x = XVECEXP (x, 0, 0);
2115
2116   if (GET_CODE (x) != SET)
2117     return 0;
2118   if (GET_CODE (SET_DEST (x)) != PC)
2119     return 0;
2120   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
2121     return 1;
2122   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
2123     return 0;
2124   if (XEXP (SET_SRC (x), 2) == pc_rtx
2125       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
2126           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
2127     return 1;
2128   if (XEXP (SET_SRC (x), 1) == pc_rtx
2129       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
2130           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
2131     return 1;
2132   return 0;
2133 }
2134
2135 /* Return set of PC, otherwise NULL.  */
2136
2137 rtx
2138 pc_set (insn)
2139      rtx insn;
2140 {
2141   rtx pat;
2142   if (GET_CODE (insn) != JUMP_INSN)
2143     return NULL_RTX;
2144   pat = PATTERN (insn);
2145
2146   /* The set is allowed to appear either as the insn pattern or
2147      the first set in a PARALLEL.  */
2148   if (GET_CODE (pat) == PARALLEL)
2149     pat = XVECEXP (pat, 0, 0);
2150   if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
2151     return pat;
2152
2153   return NULL_RTX;
2154 }
2155
2156 /* Return true when insn is an unconditional direct jump,
2157    possibly bundled inside a PARALLEL.  */
2158
2159 int
2160 any_uncondjump_p (insn)
2161      rtx insn;
2162 {
2163   rtx x = pc_set (insn);
2164   if (!x)
2165     return 0;
2166   if (GET_CODE (SET_SRC (x)) != LABEL_REF)
2167     return 0;
2168   return 1;
2169 }
2170
2171 /* Return true when insn is a conditional jump.  This function works for
2172    instructions containing PC sets in PARALLELs.  The instruction may have
2173    various other effects so before removing the jump you must verify
2174    onlyjump_p.
2175
2176    Note that unlike condjump_p it returns false for unconditional jumps.  */
2177
2178 int
2179 any_condjump_p (insn)
2180      rtx insn;
2181 {
2182   rtx x = pc_set (insn);
2183   enum rtx_code a, b;
2184
2185   if (!x)
2186     return 0;
2187   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
2188     return 0;
2189
2190   a = GET_CODE (XEXP (SET_SRC (x), 1));
2191   b = GET_CODE (XEXP (SET_SRC (x), 2));
2192
2193   return ((b == PC && (a == LABEL_REF || a == RETURN))
2194           || (a == PC && (b == LABEL_REF || b == RETURN)));
2195 }
2196
2197 /* Return the label of a conditional jump.  */
2198
2199 rtx
2200 condjump_label (insn)
2201      rtx insn;
2202 {
2203   rtx x = pc_set (insn);
2204
2205   if (!x)
2206     return NULL_RTX;
2207   x = SET_SRC (x);
2208   if (GET_CODE (x) == LABEL_REF)
2209     return x;
2210   if (GET_CODE (x) != IF_THEN_ELSE)
2211     return NULL_RTX;
2212   if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
2213     return XEXP (x, 1);
2214   if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
2215     return XEXP (x, 2);
2216   return NULL_RTX;
2217 }
2218
2219 /* Return true if INSN is a (possibly conditional) return insn.  */
2220
2221 static int
2222 returnjump_p_1 (loc, data)
2223      rtx *loc;
2224      void *data ATTRIBUTE_UNUSED;
2225 {
2226   rtx x = *loc;
2227   return x && GET_CODE (x) == RETURN;
2228 }
2229
2230 int
2231 returnjump_p (insn)
2232      rtx insn;
2233 {
2234   if (GET_CODE (insn) != JUMP_INSN)
2235     return 0;
2236   return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
2237 }
2238
2239 /* Return true if INSN is a jump that only transfers control and
2240    nothing more.  */
2241
2242 int
2243 onlyjump_p (insn)
2244      rtx insn;
2245 {
2246   rtx set;
2247
2248   if (GET_CODE (insn) != JUMP_INSN)
2249     return 0;
2250
2251   set = single_set (insn);
2252   if (set == NULL)
2253     return 0;
2254   if (GET_CODE (SET_DEST (set)) != PC)
2255     return 0;
2256   if (side_effects_p (SET_SRC (set)))
2257     return 0;
2258
2259   return 1;
2260 }
2261
2262 #ifdef HAVE_cc0
2263
2264 /* Return 1 if X is an RTX that does nothing but set the condition codes
2265    and CLOBBER or USE registers.
2266    Return -1 if X does explicitly set the condition codes,
2267    but also does other things.  */
2268
2269 int
2270 sets_cc0_p (x)
2271      rtx x ATTRIBUTE_UNUSED;
2272 {
2273   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
2274     return 1;
2275   if (GET_CODE (x) == PARALLEL)
2276     {
2277       int i;
2278       int sets_cc0 = 0;
2279       int other_things = 0;
2280       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
2281         {
2282           if (GET_CODE (XVECEXP (x, 0, i)) == SET
2283               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
2284             sets_cc0 = 1;
2285           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
2286             other_things = 1;
2287         }
2288       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
2289     }
2290   return 0;
2291 }
2292 #endif
2293 \f
2294 /* Follow any unconditional jump at LABEL;
2295    return the ultimate label reached by any such chain of jumps.
2296    If LABEL is not followed by a jump, return LABEL.
2297    If the chain loops or we can't find end, return LABEL,
2298    since that tells caller to avoid changing the insn.
2299
2300    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
2301    a USE or CLOBBER.  */
2302
2303 rtx
2304 follow_jumps (label)
2305      rtx label;
2306 {
2307   register rtx insn;
2308   register rtx next;
2309   register rtx value = label;
2310   register int depth;
2311
2312   for (depth = 0;
2313        (depth < 10
2314         && (insn = next_active_insn (value)) != 0
2315         && GET_CODE (insn) == JUMP_INSN
2316         && ((JUMP_LABEL (insn) != 0 && any_uncondjump_p (insn)
2317              && onlyjump_p (insn))
2318             || GET_CODE (PATTERN (insn)) == RETURN)
2319         && (next = NEXT_INSN (insn))
2320         && GET_CODE (next) == BARRIER);
2321        depth++)
2322     {
2323       /* Don't chain through the insn that jumps into a loop
2324          from outside the loop,
2325          since that would create multiple loop entry jumps
2326          and prevent loop optimization.  */
2327       rtx tem;
2328       if (!reload_completed)
2329         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
2330           if (GET_CODE (tem) == NOTE
2331               && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
2332                   /* ??? Optional.  Disables some optimizations, but makes
2333                      gcov output more accurate with -O.  */
2334                   || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
2335             return value;
2336
2337       /* If we have found a cycle, make the insn jump to itself.  */
2338       if (JUMP_LABEL (insn) == label)
2339         return label;
2340
2341       tem = next_active_insn (JUMP_LABEL (insn));
2342       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
2343                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
2344         break;
2345
2346       value = JUMP_LABEL (insn);
2347     }
2348   if (depth == 10)
2349     return label;
2350   return value;
2351 }
2352
2353 /* Assuming that field IDX of X is a vector of label_refs,
2354    replace each of them by the ultimate label reached by it.
2355    Return nonzero if a change is made.
2356    If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG.  */
2357
2358 static int
2359 tension_vector_labels (x, idx)
2360      register rtx x;
2361      register int idx;
2362 {
2363   int changed = 0;
2364   register int i;
2365   for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
2366     {
2367       register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
2368       register rtx nlabel = follow_jumps (olabel);
2369       if (nlabel && nlabel != olabel)
2370         {
2371           XEXP (XVECEXP (x, idx, i), 0) = nlabel;
2372           ++LABEL_NUSES (nlabel);
2373           if (--LABEL_NUSES (olabel) == 0)
2374             delete_insn (olabel);
2375           changed = 1;
2376         }
2377     }
2378   return changed;
2379 }
2380 \f
2381 /* Find all CODE_LABELs referred to in X, and increment their use counts.
2382    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
2383    in INSN, then store one of them in JUMP_LABEL (INSN).
2384    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
2385    referenced in INSN, add a REG_LABEL note containing that label to INSN.
2386    Also, when there are consecutive labels, canonicalize on the last of them.
2387
2388    Note that two labels separated by a loop-beginning note
2389    must be kept distinct if we have not yet done loop-optimization,
2390    because the gap between them is where loop-optimize
2391    will want to move invariant code to.  CROSS_JUMP tells us
2392    that loop-optimization is done with.
2393
2394    Once reload has completed (CROSS_JUMP non-zero), we need not consider
2395    two labels distinct if they are separated by only USE or CLOBBER insns.  */
2396
2397 void
2398 mark_jump_label (x, insn, cross_jump, in_mem)
2399      register rtx x;
2400      rtx insn;
2401      int cross_jump;
2402      int in_mem;
2403 {
2404   register RTX_CODE code = GET_CODE (x);
2405   register int i;
2406   register const char *fmt;
2407
2408   switch (code)
2409     {
2410     case PC:
2411     case CC0:
2412     case REG:
2413     case SUBREG:
2414     case CONST_INT:
2415     case CONST_DOUBLE:
2416     case CLOBBER:
2417     case CALL:
2418       return;
2419
2420     case MEM:
2421       in_mem = 1;
2422       break;
2423
2424     case SYMBOL_REF:
2425       if (!in_mem)
2426         return;
2427
2428       /* If this is a constant-pool reference, see if it is a label.  */
2429       if (CONSTANT_POOL_ADDRESS_P (x))
2430         mark_jump_label (get_pool_constant (x), insn, cross_jump, in_mem);
2431       break;
2432
2433     case LABEL_REF:
2434       {
2435         rtx label = XEXP (x, 0);
2436         rtx olabel = label;
2437         rtx note;
2438         rtx next;
2439
2440         /* Ignore remaining references to unreachable labels that
2441            have been deleted.  */
2442         if (GET_CODE (label) == NOTE
2443             && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
2444           break;
2445
2446         if (GET_CODE (label) != CODE_LABEL)
2447           abort ();
2448
2449         /* Ignore references to labels of containing functions.  */
2450         if (LABEL_REF_NONLOCAL_P (x))
2451           break;
2452
2453         /* If there are other labels following this one,
2454            replace it with the last of the consecutive labels.  */
2455         for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
2456           {
2457             if (GET_CODE (next) == CODE_LABEL)
2458               label = next;
2459             else if (cross_jump && GET_CODE (next) == INSN
2460                      && (GET_CODE (PATTERN (next)) == USE
2461                          || GET_CODE (PATTERN (next)) == CLOBBER))
2462               continue;
2463             else if (GET_CODE (next) != NOTE)
2464               break;
2465             else if (! cross_jump
2466                      && (NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
2467                          || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END
2468                          /* ??? Optional.  Disables some optimizations, but
2469                             makes gcov output more accurate with -O.  */
2470                          || (flag_test_coverage
2471                              && NOTE_LINE_NUMBER (next) > 0)))
2472               break;
2473           }
2474
2475         XEXP (x, 0) = label;
2476         if (! insn || ! INSN_DELETED_P (insn))
2477           ++LABEL_NUSES (label);
2478
2479         if (insn)
2480           {
2481             if (GET_CODE (insn) == JUMP_INSN)
2482               JUMP_LABEL (insn) = label;
2483
2484             /* If we've changed OLABEL and we had a REG_LABEL note
2485                for it, update it as well.  */
2486             else if (label != olabel
2487                      && (note = find_reg_note (insn, REG_LABEL, olabel)) != 0)
2488               XEXP (note, 0) = label;
2489
2490             /* Otherwise, add a REG_LABEL note for LABEL unless there already
2491                is one.  */
2492             else if (! find_reg_note (insn, REG_LABEL, label))
2493               {
2494                 /* This code used to ignore labels which refered to dispatch
2495                    tables to avoid flow.c generating worse code.
2496
2497                    However, in the presense of global optimizations like
2498                    gcse which call find_basic_blocks without calling
2499                    life_analysis, not recording such labels will lead
2500                    to compiler aborts because of inconsistencies in the
2501                    flow graph.  So we go ahead and record the label.
2502
2503                    It may also be the case that the optimization argument
2504                    is no longer valid because of the more accurate cfg
2505                    we build in find_basic_blocks -- it no longer pessimizes
2506                    code when it finds a REG_LABEL note.  */
2507                 REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
2508                                                       REG_NOTES (insn));
2509               }
2510           }
2511         return;
2512       }
2513
2514   /* Do walk the labels in a vector, but not the first operand of an
2515      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
2516     case ADDR_VEC:
2517     case ADDR_DIFF_VEC:
2518       if (! INSN_DELETED_P (insn))
2519         {
2520           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
2521
2522           for (i = 0; i < XVECLEN (x, eltnum); i++)
2523             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX,
2524                              cross_jump, in_mem);
2525         }
2526       return;
2527
2528     default:
2529       break;
2530     }
2531
2532   fmt = GET_RTX_FORMAT (code);
2533   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2534     {
2535       if (fmt[i] == 'e')
2536         mark_jump_label (XEXP (x, i), insn, cross_jump, in_mem);
2537       else if (fmt[i] == 'E')
2538         {
2539           register int j;
2540           for (j = 0; j < XVECLEN (x, i); j++)
2541             mark_jump_label (XVECEXP (x, i, j), insn, cross_jump, in_mem);
2542         }
2543     }
2544 }
2545
2546 /* If all INSN does is set the pc, delete it,
2547    and delete the insn that set the condition codes for it
2548    if that's what the previous thing was.  */
2549
2550 void
2551 delete_jump (insn)
2552      rtx insn;
2553 {
2554   register rtx set = single_set (insn);
2555
2556   if (set && GET_CODE (SET_DEST (set)) == PC)
2557     delete_computation (insn);
2558 }
2559
2560 /* Verify INSN is a BARRIER and delete it.  */
2561
2562 void
2563 delete_barrier (insn)
2564      rtx insn;
2565 {
2566   if (GET_CODE (insn) != BARRIER)
2567     abort ();
2568
2569   delete_insn (insn);
2570 }
2571
2572 /* Recursively delete prior insns that compute the value (used only by INSN
2573    which the caller is deleting) stored in the register mentioned by NOTE
2574    which is a REG_DEAD note associated with INSN.  */
2575
2576 static void
2577 delete_prior_computation (note, insn)
2578      rtx note;
2579      rtx insn;
2580 {
2581   rtx our_prev;
2582   rtx reg = XEXP (note, 0);
2583
2584   for (our_prev = prev_nonnote_insn (insn);
2585        our_prev && (GET_CODE (our_prev) == INSN
2586                     || GET_CODE (our_prev) == CALL_INSN);
2587        our_prev = prev_nonnote_insn (our_prev))
2588     {
2589       rtx pat = PATTERN (our_prev);
2590
2591       /* If we reach a CALL which is not calling a const function
2592          or the callee pops the arguments, then give up.  */
2593       if (GET_CODE (our_prev) == CALL_INSN
2594           && (! CONST_CALL_P (our_prev)
2595               || GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
2596         break;
2597
2598       /* If we reach a SEQUENCE, it is too complex to try to
2599          do anything with it, so give up.  */
2600       if (GET_CODE (pat) == SEQUENCE)
2601         break;
2602
2603       if (GET_CODE (pat) == USE
2604           && GET_CODE (XEXP (pat, 0)) == INSN)
2605         /* reorg creates USEs that look like this.  We leave them
2606            alone because reorg needs them for its own purposes.  */
2607         break;
2608
2609       if (reg_set_p (reg, pat))
2610         {
2611           if (side_effects_p (pat) && GET_CODE (our_prev) != CALL_INSN)
2612             break;
2613
2614           if (GET_CODE (pat) == PARALLEL)
2615             {
2616               /* If we find a SET of something else, we can't
2617                  delete the insn.  */
2618
2619               int i;
2620
2621               for (i = 0; i < XVECLEN (pat, 0); i++)
2622                 {
2623                   rtx part = XVECEXP (pat, 0, i);
2624
2625                   if (GET_CODE (part) == SET
2626                       && SET_DEST (part) != reg)
2627                     break;
2628                 }
2629
2630               if (i == XVECLEN (pat, 0))
2631                 delete_computation (our_prev);
2632             }
2633           else if (GET_CODE (pat) == SET
2634                    && GET_CODE (SET_DEST (pat)) == REG)
2635             {
2636               int dest_regno = REGNO (SET_DEST (pat));
2637               int dest_endregno
2638                 = (dest_regno
2639                    + (dest_regno < FIRST_PSEUDO_REGISTER
2640                       ? HARD_REGNO_NREGS (dest_regno,
2641                                           GET_MODE (SET_DEST (pat))) : 1));
2642               int regno = REGNO (reg);
2643               int endregno
2644                 = (regno
2645                    + (regno < FIRST_PSEUDO_REGISTER
2646                       ? HARD_REGNO_NREGS (regno, GET_MODE (reg)) : 1));
2647
2648               if (dest_regno >= regno
2649                   && dest_endregno <= endregno)
2650                 delete_computation (our_prev);
2651
2652               /* We may have a multi-word hard register and some, but not
2653                  all, of the words of the register are needed in subsequent
2654                  insns.  Write REG_UNUSED notes for those parts that were not
2655                  needed.  */
2656               else if (dest_regno <= regno
2657                        && dest_endregno >= endregno)
2658                 {
2659                   int i;
2660
2661                   REG_NOTES (our_prev)
2662                     = gen_rtx_EXPR_LIST (REG_UNUSED, reg,
2663                                          REG_NOTES (our_prev));
2664
2665                   for (i = dest_regno; i < dest_endregno; i++)
2666                     if (! find_regno_note (our_prev, REG_UNUSED, i))
2667                       break;
2668
2669                   if (i == dest_endregno)
2670                     delete_computation (our_prev);
2671                 }
2672             }
2673
2674           break;
2675         }
2676
2677       /* If PAT references the register that dies here, it is an
2678          additional use.  Hence any prior SET isn't dead.  However, this
2679          insn becomes the new place for the REG_DEAD note.  */
2680       if (reg_overlap_mentioned_p (reg, pat))
2681         {
2682           XEXP (note, 1) = REG_NOTES (our_prev);
2683           REG_NOTES (our_prev) = note;
2684           break;
2685         }
2686     }
2687 }
2688
2689 /* Delete INSN and recursively delete insns that compute values used only
2690    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
2691    If we are running before flow.c, we need do nothing since flow.c will
2692    delete dead code.  We also can't know if the registers being used are
2693    dead or not at this point.
2694
2695    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
2696    nothing other than set a register that dies in this insn, we can delete
2697    that insn as well.
2698
2699    On machines with CC0, if CC0 is used in this insn, we may be able to
2700    delete the insn that set it.  */
2701
2702 static void
2703 delete_computation (insn)
2704      rtx insn;
2705 {
2706   rtx note, next;
2707
2708 #ifdef HAVE_cc0
2709   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
2710     {
2711       rtx prev = prev_nonnote_insn (insn);
2712       /* We assume that at this stage
2713          CC's are always set explicitly
2714          and always immediately before the jump that
2715          will use them.  So if the previous insn
2716          exists to set the CC's, delete it
2717          (unless it performs auto-increments, etc.).  */
2718       if (prev && GET_CODE (prev) == INSN
2719           && sets_cc0_p (PATTERN (prev)))
2720         {
2721           if (sets_cc0_p (PATTERN (prev)) > 0
2722               && ! side_effects_p (PATTERN (prev)))
2723             delete_computation (prev);
2724           else
2725             /* Otherwise, show that cc0 won't be used.  */
2726             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
2727                                                   cc0_rtx, REG_NOTES (prev));
2728         }
2729     }
2730 #endif
2731
2732   for (note = REG_NOTES (insn); note; note = next)
2733     {
2734       next = XEXP (note, 1);
2735
2736       if (REG_NOTE_KIND (note) != REG_DEAD
2737           /* Verify that the REG_NOTE is legitimate.  */
2738           || GET_CODE (XEXP (note, 0)) != REG)
2739         continue;
2740
2741       delete_prior_computation (note, insn);
2742     }
2743
2744   delete_insn (insn);
2745 }
2746 \f
2747 /* Delete insn INSN from the chain of insns and update label ref counts.
2748    May delete some following insns as a consequence; may even delete
2749    a label elsewhere and insns that follow it.
2750
2751    Returns the first insn after INSN that was not deleted.  */
2752
2753 rtx
2754 delete_insn (insn)
2755      register rtx insn;
2756 {
2757   register rtx next = NEXT_INSN (insn);
2758   register rtx prev = PREV_INSN (insn);
2759   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
2760   register int dont_really_delete = 0;
2761   rtx note;
2762
2763   while (next && INSN_DELETED_P (next))
2764     next = NEXT_INSN (next);
2765
2766   /* This insn is already deleted => return first following nondeleted.  */
2767   if (INSN_DELETED_P (insn))
2768     return next;
2769
2770   if (was_code_label)
2771     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2772
2773   /* Don't delete user-declared labels.  When optimizing, convert them
2774      to special NOTEs instead.  When not optimizing, leave them alone.  */
2775   if (was_code_label && LABEL_NAME (insn) != 0)
2776     {
2777       if (! optimize)
2778         dont_really_delete = 1;
2779       else if (! dont_really_delete)
2780         {
2781           const char *name = LABEL_NAME (insn);
2782           PUT_CODE (insn, NOTE);
2783           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
2784           NOTE_SOURCE_FILE (insn) = name;
2785           dont_really_delete = 1;
2786         }
2787     }
2788   else
2789     /* Mark this insn as deleted.  */
2790     INSN_DELETED_P (insn) = 1;
2791
2792   /* If this is an unconditional jump, delete it from the jump chain.  */
2793   if (simplejump_p (insn))
2794     delete_from_jump_chain (insn);
2795
2796   /* If instruction is followed by a barrier,
2797      delete the barrier too.  */
2798
2799   if (next != 0 && GET_CODE (next) == BARRIER)
2800     {
2801       INSN_DELETED_P (next) = 1;
2802       next = NEXT_INSN (next);
2803     }
2804
2805   /* Patch out INSN (and the barrier if any) */
2806
2807   if (! dont_really_delete)
2808     {
2809       if (prev)
2810         {
2811           NEXT_INSN (prev) = next;
2812           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
2813             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
2814                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
2815         }
2816
2817       if (next)
2818         {
2819           PREV_INSN (next) = prev;
2820           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
2821             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
2822         }
2823
2824       if (prev && NEXT_INSN (prev) == 0)
2825         set_last_insn (prev);
2826     }
2827
2828   /* If deleting a jump, decrement the count of the label,
2829      and delete the label if it is now unused.  */
2830
2831   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
2832     {
2833       rtx lab = JUMP_LABEL (insn), lab_next;
2834
2835       if (--LABEL_NUSES (lab) == 0)
2836         {
2837           /* This can delete NEXT or PREV,
2838              either directly if NEXT is JUMP_LABEL (INSN),
2839              or indirectly through more levels of jumps.  */
2840           delete_insn (lab);
2841
2842           /* I feel a little doubtful about this loop,
2843              but I see no clean and sure alternative way
2844              to find the first insn after INSN that is not now deleted.
2845              I hope this works.  */
2846           while (next && INSN_DELETED_P (next))
2847             next = NEXT_INSN (next);
2848           return next;
2849         }
2850       else if ((lab_next = next_nonnote_insn (lab)) != NULL
2851                && GET_CODE (lab_next) == JUMP_INSN
2852                && (GET_CODE (PATTERN (lab_next)) == ADDR_VEC
2853                    || GET_CODE (PATTERN (lab_next)) == ADDR_DIFF_VEC))
2854         {
2855           /* If we're deleting the tablejump, delete the dispatch table.
2856              We may not be able to kill the label immediately preceeding
2857              just yet, as it might be referenced in code leading up to
2858              the tablejump.  */
2859           delete_insn (lab_next);
2860         }
2861     }
2862
2863   /* Likewise if we're deleting a dispatch table.  */
2864
2865   if (GET_CODE (insn) == JUMP_INSN
2866       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
2867           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
2868     {
2869       rtx pat = PATTERN (insn);
2870       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
2871       int len = XVECLEN (pat, diff_vec_p);
2872
2873       for (i = 0; i < len; i++)
2874         if (--LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
2875           delete_insn (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
2876       while (next && INSN_DELETED_P (next))
2877         next = NEXT_INSN (next);
2878       return next;
2879     }
2880
2881   /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
2882   if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2883     for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2884       if (REG_NOTE_KIND (note) == REG_LABEL
2885           /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
2886           && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2887         if (--LABEL_NUSES (XEXP (note, 0)) == 0)
2888           delete_insn (XEXP (note, 0));
2889
2890   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
2891     prev = PREV_INSN (prev);
2892
2893   /* If INSN was a label and a dispatch table follows it,
2894      delete the dispatch table.  The tablejump must have gone already.
2895      It isn't useful to fall through into a table.  */
2896
2897   if (was_code_label
2898       && NEXT_INSN (insn) != 0
2899       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
2900       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
2901           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
2902     next = delete_insn (NEXT_INSN (insn));
2903
2904   /* If INSN was a label, delete insns following it if now unreachable.  */
2905
2906   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
2907     {
2908       register RTX_CODE code;
2909       while (next != 0
2910              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
2911                  || code == NOTE || code == BARRIER
2912                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
2913         {
2914           if (code == NOTE
2915               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
2916             next = NEXT_INSN (next);
2917           /* Keep going past other deleted labels to delete what follows.  */
2918           else if (code == CODE_LABEL && INSN_DELETED_P (next))
2919             next = NEXT_INSN (next);
2920           else
2921             /* Note: if this deletes a jump, it can cause more
2922                deletion of unreachable code, after a different label.
2923                As long as the value from this recursive call is correct,
2924                this invocation functions correctly.  */
2925             next = delete_insn (next);
2926         }
2927     }
2928
2929   return next;
2930 }
2931
2932 /* Advance from INSN till reaching something not deleted
2933    then return that.  May return INSN itself.  */
2934
2935 rtx
2936 next_nondeleted_insn (insn)
2937      rtx insn;
2938 {
2939   while (INSN_DELETED_P (insn))
2940     insn = NEXT_INSN (insn);
2941   return insn;
2942 }
2943 \f
2944 /* Delete a range of insns from FROM to TO, inclusive.
2945    This is for the sake of peephole optimization, so assume
2946    that whatever these insns do will still be done by a new
2947    peephole insn that will replace them.  */
2948
2949 void
2950 delete_for_peephole (from, to)
2951      register rtx from, to;
2952 {
2953   register rtx insn = from;
2954
2955   while (1)
2956     {
2957       register rtx next = NEXT_INSN (insn);
2958       register rtx prev = PREV_INSN (insn);
2959
2960       if (GET_CODE (insn) != NOTE)
2961         {
2962           INSN_DELETED_P (insn) = 1;
2963
2964           /* Patch this insn out of the chain.  */
2965           /* We don't do this all at once, because we
2966              must preserve all NOTEs.  */
2967           if (prev)
2968             NEXT_INSN (prev) = next;
2969
2970           if (next)
2971             PREV_INSN (next) = prev;
2972         }
2973
2974       if (insn == to)
2975         break;
2976       insn = next;
2977     }
2978
2979   /* Note that if TO is an unconditional jump
2980      we *do not* delete the BARRIER that follows,
2981      since the peephole that replaces this sequence
2982      is also an unconditional jump in that case.  */
2983 }
2984 \f
2985 /* We have determined that INSN is never reached, and are about to
2986    delete it.  Print a warning if the user asked for one.
2987
2988    To try to make this warning more useful, this should only be called
2989    once per basic block not reached, and it only warns when the basic
2990    block contains more than one line from the current function, and
2991    contains at least one operation.  CSE and inlining can duplicate insns,
2992    so it's possible to get spurious warnings from this.  */
2993
2994 void
2995 never_reached_warning (avoided_insn)
2996      rtx avoided_insn;
2997 {
2998   rtx insn;
2999   rtx a_line_note = NULL;
3000   int two_avoided_lines = 0;
3001   int contains_insn = 0;
3002
3003   if (! warn_notreached)
3004     return;
3005
3006   /* Scan forwards, looking at LINE_NUMBER notes, until
3007      we hit a LABEL or we run out of insns.  */
3008
3009   for (insn = avoided_insn; insn != NULL; insn = NEXT_INSN (insn))
3010     {
3011       if (GET_CODE (insn) == CODE_LABEL)
3012         break;
3013       else if (GET_CODE (insn) == NOTE          /* A line number note?  */
3014                && NOTE_LINE_NUMBER (insn) >= 0)
3015         {
3016           if (a_line_note == NULL)
3017             a_line_note = insn;
3018           else
3019             two_avoided_lines |= (NOTE_LINE_NUMBER (a_line_note)
3020                                   != NOTE_LINE_NUMBER (insn));
3021         }
3022       else if (INSN_P (insn))
3023         contains_insn = 1;
3024     }
3025   if (two_avoided_lines && contains_insn)
3026     warning_with_file_and_line (NOTE_SOURCE_FILE (a_line_note),
3027                                 NOTE_LINE_NUMBER (a_line_note),
3028                                 "will never be executed");
3029 }
3030 \f
3031 /* Throughout LOC, redirect OLABEL to NLABEL.  Treat null OLABEL or
3032    NLABEL as a return.  Accrue modifications into the change group.  */
3033
3034 static void
3035 redirect_exp_1 (loc, olabel, nlabel, insn)
3036      rtx *loc;
3037      rtx olabel, nlabel;
3038      rtx insn;
3039 {
3040   register rtx x = *loc;
3041   register RTX_CODE code = GET_CODE (x);
3042   register int i;
3043   register const char *fmt;
3044
3045   if (code == LABEL_REF)
3046     {
3047       if (XEXP (x, 0) == olabel)
3048         {
3049           rtx n;
3050           if (nlabel)
3051             n = gen_rtx_LABEL_REF (VOIDmode, nlabel);
3052           else
3053             n = gen_rtx_RETURN (VOIDmode);
3054
3055           validate_change (insn, loc, n, 1);
3056           return;
3057         }
3058     }
3059   else if (code == RETURN && olabel == 0)
3060     {
3061       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
3062       if (loc == &PATTERN (insn))
3063         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
3064       validate_change (insn, loc, x, 1);
3065       return;
3066     }
3067
3068   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
3069       && GET_CODE (SET_SRC (x)) == LABEL_REF
3070       && XEXP (SET_SRC (x), 0) == olabel)
3071     {
3072       validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
3073       return;
3074     }
3075
3076   fmt = GET_RTX_FORMAT (code);
3077   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3078     {
3079       if (fmt[i] == 'e')
3080         redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
3081       else if (fmt[i] == 'E')
3082         {
3083           register int j;
3084           for (j = 0; j < XVECLEN (x, i); j++)
3085             redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
3086         }
3087     }
3088 }
3089
3090 /* Similar, but apply the change group and report success or failure.  */
3091
3092 static int
3093 redirect_exp (olabel, nlabel, insn)
3094      rtx olabel, nlabel;
3095      rtx insn;
3096 {
3097   rtx *loc;
3098
3099   if (GET_CODE (PATTERN (insn)) == PARALLEL)
3100     loc = &XVECEXP (PATTERN (insn), 0, 0);
3101   else
3102     loc = &PATTERN (insn);
3103
3104   redirect_exp_1 (loc, olabel, nlabel, insn);
3105   if (num_validated_changes () == 0)
3106     return 0;
3107
3108   return apply_change_group ();
3109 }
3110
3111 /* Make JUMP go to NLABEL instead of where it jumps now.  Accrue
3112    the modifications into the change group.  Return false if we did
3113    not see how to do that.  */
3114
3115 int
3116 redirect_jump_1 (jump, nlabel)
3117      rtx jump, nlabel;
3118 {
3119   int ochanges = num_validated_changes ();
3120   rtx *loc;
3121
3122   if (GET_CODE (PATTERN (jump)) == PARALLEL)
3123     loc = &XVECEXP (PATTERN (jump), 0, 0);
3124   else
3125     loc = &PATTERN (jump);
3126
3127   redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
3128   return num_validated_changes () > ochanges;
3129 }
3130
3131 /* Make JUMP go to NLABEL instead of where it jumps now.  If the old
3132    jump target label is unused as a result, it and the code following
3133    it may be deleted.
3134
3135    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
3136    RETURN insn.
3137
3138    The return value will be 1 if the change was made, 0 if it wasn't
3139    (this can only occur for NLABEL == 0).  */
3140
3141 int
3142 redirect_jump (jump, nlabel, delete_unused)
3143      rtx jump, nlabel;
3144      int delete_unused;
3145 {
3146   register rtx olabel = JUMP_LABEL (jump);
3147
3148   if (nlabel == olabel)
3149     return 1;
3150
3151   if (! redirect_exp (olabel, nlabel, jump))
3152     return 0;
3153
3154   /* If this is an unconditional branch, delete it from the jump_chain of
3155      OLABEL and add it to the jump_chain of NLABEL (assuming both labels
3156      have UID's in range and JUMP_CHAIN is valid).  */
3157   if (jump_chain && (simplejump_p (jump)
3158                      || GET_CODE (PATTERN (jump)) == RETURN))
3159     {
3160       int label_index = nlabel ? INSN_UID (nlabel) : 0;
3161
3162       delete_from_jump_chain (jump);
3163       if (label_index < max_jump_chain
3164           && INSN_UID (jump) < max_jump_chain)
3165         {
3166           jump_chain[INSN_UID (jump)] = jump_chain[label_index];
3167           jump_chain[label_index] = jump;
3168         }
3169     }
3170
3171   JUMP_LABEL (jump) = nlabel;
3172   if (nlabel)
3173     ++LABEL_NUSES (nlabel);
3174
3175   /* If we're eliding the jump over exception cleanups at the end of a
3176      function, move the function end note so that -Wreturn-type works.  */
3177   if (olabel && nlabel
3178       && NEXT_INSN (olabel)
3179       && GET_CODE (NEXT_INSN (olabel)) == NOTE
3180       && NOTE_LINE_NUMBER (NEXT_INSN (olabel)) == NOTE_INSN_FUNCTION_END)
3181     emit_note_after (NOTE_INSN_FUNCTION_END, nlabel);
3182
3183   if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused)
3184     delete_insn (olabel);
3185
3186   return 1;
3187 }
3188
3189 /* Invert the jump condition of rtx X contained in jump insn, INSN.
3190    Accrue the modifications into the change group.  */
3191
3192 static void
3193 invert_exp_1 (insn)
3194      rtx insn;
3195 {
3196   register RTX_CODE code;
3197   rtx x = pc_set (insn);
3198
3199   if (!x)
3200     abort ();
3201   x = SET_SRC (x);
3202
3203   code = GET_CODE (x);
3204
3205   if (code == IF_THEN_ELSE)
3206     {
3207       register rtx comp = XEXP (x, 0);
3208       register rtx tem;
3209
3210       /* We can do this in two ways:  The preferable way, which can only
3211          be done if this is not an integer comparison, is to reverse
3212          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
3213          of the IF_THEN_ELSE.  If we can't do either, fail.  */
3214
3215       if (can_reverse_comparison_p (comp, insn))
3216         {
3217           validate_change (insn, &XEXP (x, 0),
3218                            gen_rtx_fmt_ee (reverse_condition (GET_CODE (comp)),
3219                                            GET_MODE (comp), XEXP (comp, 0),
3220                                            XEXP (comp, 1)),
3221                            1);
3222           return;
3223         }
3224
3225       tem = XEXP (x, 1);
3226       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
3227       validate_change (insn, &XEXP (x, 2), tem, 1);
3228     }
3229   else
3230     abort ();
3231 }
3232
3233 /* Invert the jump condition of conditional jump insn, INSN.
3234
3235    Return 1 if we can do so, 0 if we cannot find a way to do so that
3236    matches a pattern.  */
3237
3238 static int
3239 invert_exp (insn)
3240      rtx insn;
3241 {
3242   invert_exp_1 (insn);
3243   if (num_validated_changes () == 0)
3244     return 0;
3245
3246   return apply_change_group ();
3247 }
3248
3249 /* Invert the condition of the jump JUMP, and make it jump to label
3250    NLABEL instead of where it jumps now.  Accrue changes into the
3251    change group.  Return false if we didn't see how to perform the
3252    inversion and redirection.  */
3253
3254 int
3255 invert_jump_1 (jump, nlabel)
3256      rtx jump, nlabel;
3257 {
3258   int ochanges;
3259
3260   ochanges = num_validated_changes ();
3261   invert_exp_1 (jump);
3262   if (num_validated_changes () == ochanges)
3263     return 0;
3264
3265   return redirect_jump_1 (jump, nlabel);
3266 }
3267
3268 /* Invert the condition of the jump JUMP, and make it jump to label
3269    NLABEL instead of where it jumps now.  Return true if successful.  */
3270
3271 int
3272 invert_jump (jump, nlabel, delete_unused)
3273      rtx jump, nlabel;
3274      int delete_unused;
3275 {
3276   /* We have to either invert the condition and change the label or
3277      do neither.  Either operation could fail.  We first try to invert
3278      the jump. If that succeeds, we try changing the label.  If that fails,
3279      we invert the jump back to what it was.  */
3280
3281   if (! invert_exp (jump))
3282     return 0;
3283
3284   if (redirect_jump (jump, nlabel, delete_unused))
3285     {
3286       /* An inverted jump means that a probability taken becomes a
3287          probability not taken.  Subtract the branch probability from the
3288          probability base to convert it back to a taken probability.  */
3289
3290       rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3291       if (note)
3292         XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
3293
3294       return 1;
3295     }
3296
3297   if (! invert_exp (jump))
3298     /* This should just be putting it back the way it was.  */
3299     abort ();
3300
3301   return 0;
3302 }
3303
3304 /* Delete the instruction JUMP from any jump chain it might be on.  */
3305
3306 static void
3307 delete_from_jump_chain (jump)
3308      rtx jump;
3309 {
3310   int index;
3311   rtx olabel = JUMP_LABEL (jump);
3312
3313   /* Handle unconditional jumps.  */
3314   if (jump_chain && olabel != 0
3315       && INSN_UID (olabel) < max_jump_chain
3316       && simplejump_p (jump))
3317     index = INSN_UID (olabel);
3318   /* Handle return insns.  */
3319   else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
3320     index = 0;
3321   else
3322     return;
3323
3324   if (jump_chain[index] == jump)
3325     jump_chain[index] = jump_chain[INSN_UID (jump)];
3326   else
3327     {
3328       rtx insn;
3329
3330       for (insn = jump_chain[index];
3331            insn != 0;
3332            insn = jump_chain[INSN_UID (insn)])
3333         if (jump_chain[INSN_UID (insn)] == jump)
3334           {
3335             jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
3336             break;
3337           }
3338     }
3339 }
3340 \f
3341 /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
3342
3343    If the old jump target label (before the dispatch table) becomes unused,
3344    it and the dispatch table may be deleted.  In that case, find the insn
3345    before the jump references that label and delete it and logical successors
3346    too.  */
3347
3348 static void
3349 redirect_tablejump (jump, nlabel)
3350      rtx jump, nlabel;
3351 {
3352   register rtx olabel = JUMP_LABEL (jump);
3353   rtx *notep, note, next;
3354
3355   /* Add this jump to the jump_chain of NLABEL.  */
3356   if (jump_chain && INSN_UID (nlabel) < max_jump_chain
3357       && INSN_UID (jump) < max_jump_chain)
3358     {
3359       jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
3360       jump_chain[INSN_UID (nlabel)] = jump;
3361     }
3362
3363   for (notep = &REG_NOTES (jump), note = *notep; note; note = next)
3364     {
3365       next = XEXP (note, 1);
3366
3367       if (REG_NOTE_KIND (note) != REG_DEAD
3368           /* Verify that the REG_NOTE is legitimate.  */
3369           || GET_CODE (XEXP (note, 0)) != REG
3370           || ! reg_mentioned_p (XEXP (note, 0), PATTERN (jump)))
3371         notep = &XEXP (note, 1);
3372       else
3373         {
3374           delete_prior_computation (note, jump);
3375           *notep = next;
3376         }
3377     }
3378
3379   PATTERN (jump) = gen_jump (nlabel);
3380   JUMP_LABEL (jump) = nlabel;
3381   ++LABEL_NUSES (nlabel);
3382   INSN_CODE (jump) = -1;
3383
3384   if (--LABEL_NUSES (olabel) == 0)
3385     {
3386       delete_labelref_insn (jump, olabel, 0);
3387       delete_insn (olabel);
3388     }
3389 }
3390
3391 /* Find the insn referencing LABEL that is a logical predecessor of INSN.
3392    If we found one, delete it and then delete this insn if DELETE_THIS is
3393    non-zero.  Return non-zero if INSN or a predecessor references LABEL.  */
3394
3395 static int
3396 delete_labelref_insn (insn, label, delete_this)
3397      rtx insn, label;
3398      int delete_this;
3399 {
3400   int deleted = 0;
3401   rtx link;
3402
3403   if (GET_CODE (insn) != NOTE
3404       && reg_mentioned_p (label, PATTERN (insn)))
3405     {
3406       if (delete_this)
3407         {
3408           delete_insn (insn);
3409           deleted = 1;
3410         }
3411       else
3412         return 1;
3413     }
3414
3415   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
3416     if (delete_labelref_insn (XEXP (link, 0), label, 1))
3417       {
3418         if (delete_this)
3419           {
3420             delete_insn (insn);
3421             deleted = 1;
3422           }
3423         else
3424           return 1;
3425       }
3426
3427   return deleted;
3428 }
3429 \f
3430 /* Like rtx_equal_p except that it considers two REGs as equal
3431    if they renumber to the same value and considers two commutative
3432    operations to be the same if the order of the operands has been
3433    reversed.
3434
3435    ??? Addition is not commutative on the PA due to the weird implicit
3436    space register selection rules for memory addresses.  Therefore, we
3437    don't consider a + b == b + a.
3438
3439    We could/should make this test a little tighter.  Possibly only
3440    disabling it on the PA via some backend macro or only disabling this
3441    case when the PLUS is inside a MEM.  */
3442
3443 int
3444 rtx_renumbered_equal_p (x, y)
3445      rtx x, y;
3446 {
3447   register int i;
3448   register RTX_CODE code = GET_CODE (x);
3449   register const char *fmt;
3450
3451   if (x == y)
3452     return 1;
3453
3454   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
3455       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
3456                                   && GET_CODE (SUBREG_REG (y)) == REG)))
3457     {
3458       int reg_x = -1, reg_y = -1;
3459       int word_x = 0, word_y = 0;
3460
3461       if (GET_MODE (x) != GET_MODE (y))
3462         return 0;
3463
3464       /* If we haven't done any renumbering, don't
3465          make any assumptions.  */
3466       if (reg_renumber == 0)
3467         return rtx_equal_p (x, y);
3468
3469       if (code == SUBREG)
3470         {
3471           reg_x = REGNO (SUBREG_REG (x));
3472           word_x = SUBREG_WORD (x);
3473
3474           if (reg_renumber[reg_x] >= 0)
3475             {
3476               reg_x = reg_renumber[reg_x] + word_x;
3477               word_x = 0;
3478             }
3479         }
3480
3481       else
3482         {
3483           reg_x = REGNO (x);
3484           if (reg_renumber[reg_x] >= 0)
3485             reg_x = reg_renumber[reg_x];
3486         }
3487
3488       if (GET_CODE (y) == SUBREG)
3489         {
3490           reg_y = REGNO (SUBREG_REG (y));
3491           word_y = SUBREG_WORD (y);
3492
3493           if (reg_renumber[reg_y] >= 0)
3494             {
3495               reg_y = reg_renumber[reg_y];
3496               word_y = 0;
3497             }
3498         }
3499
3500       else
3501         {
3502           reg_y = REGNO (y);
3503           if (reg_renumber[reg_y] >= 0)
3504             reg_y = reg_renumber[reg_y];
3505         }
3506
3507       return reg_x >= 0 && reg_x == reg_y && word_x == word_y;
3508     }
3509
3510   /* Now we have disposed of all the cases
3511      in which different rtx codes can match.  */
3512   if (code != GET_CODE (y))
3513     return 0;
3514
3515   switch (code)
3516     {
3517     case PC:
3518     case CC0:
3519     case ADDR_VEC:
3520     case ADDR_DIFF_VEC:
3521       return 0;
3522
3523     case CONST_INT:
3524       return INTVAL (x) == INTVAL (y);
3525
3526     case LABEL_REF:
3527       /* We can't assume nonlocal labels have their following insns yet.  */
3528       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
3529         return XEXP (x, 0) == XEXP (y, 0);
3530
3531       /* Two label-refs are equivalent if they point at labels
3532          in the same position in the instruction stream.  */
3533       return (next_real_insn (XEXP (x, 0))
3534               == next_real_insn (XEXP (y, 0)));
3535
3536     case SYMBOL_REF:
3537       return XSTR (x, 0) == XSTR (y, 0);
3538
3539     case CODE_LABEL:
3540       /* If we didn't match EQ equality above, they aren't the same.  */
3541       return 0;
3542
3543     default:
3544       break;
3545     }
3546
3547   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
3548
3549   if (GET_MODE (x) != GET_MODE (y))
3550     return 0;
3551
3552   /* For commutative operations, the RTX match if the operand match in any
3553      order.  Also handle the simple binary and unary cases without a loop.
3554
3555      ??? Don't consider PLUS a commutative operator; see comments above.  */
3556   if ((code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3557       && code != PLUS)
3558     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3559              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
3560             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
3561                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
3562   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
3563     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3564             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
3565   else if (GET_RTX_CLASS (code) == '1')
3566     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
3567
3568   /* Compare the elements.  If any pair of corresponding elements
3569      fail to match, return 0 for the whole things.  */
3570
3571   fmt = GET_RTX_FORMAT (code);
3572   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3573     {
3574       register int j;
3575       switch (fmt[i])
3576         {
3577         case 'w':
3578           if (XWINT (x, i) != XWINT (y, i))
3579             return 0;
3580           break;
3581
3582         case 'i':
3583           if (XINT (x, i) != XINT (y, i))
3584             return 0;
3585           break;
3586
3587         case 's':
3588           if (strcmp (XSTR (x, i), XSTR (y, i)))
3589             return 0;
3590           break;
3591
3592         case 'e':
3593           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
3594             return 0;
3595           break;
3596
3597         case 'u':
3598           if (XEXP (x, i) != XEXP (y, i))
3599             return 0;
3600           /* fall through.  */
3601         case '0':
3602           break;
3603
3604         case 'E':
3605           if (XVECLEN (x, i) != XVECLEN (y, i))
3606             return 0;
3607           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3608             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
3609               return 0;
3610           break;
3611
3612         default:
3613           abort ();
3614         }
3615     }
3616   return 1;
3617 }
3618 \f
3619 /* If X is a hard register or equivalent to one or a subregister of one,
3620    return the hard register number.  If X is a pseudo register that was not
3621    assigned a hard register, return the pseudo register number.  Otherwise,
3622    return -1.  Any rtx is valid for X.  */
3623
3624 int
3625 true_regnum (x)
3626      rtx x;
3627 {
3628   if (GET_CODE (x) == REG)
3629     {
3630       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
3631         return reg_renumber[REGNO (x)];
3632       return REGNO (x);
3633     }
3634   if (GET_CODE (x) == SUBREG)
3635     {
3636       int base = true_regnum (SUBREG_REG (x));
3637       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
3638         return SUBREG_WORD (x) + base;
3639     }
3640   return -1;
3641 }
3642 \f
3643 /* Optimize code of the form:
3644
3645         for (x = a[i]; x; ...)
3646           ...
3647         for (x = a[i]; x; ...)
3648           ...
3649       foo:
3650
3651    Loop optimize will change the above code into
3652
3653         if (x = a[i])
3654           for (;;)
3655              { ...; if (! (x = ...)) break; }
3656         if (x = a[i])
3657           for (;;)
3658              { ...; if (! (x = ...)) break; }
3659       foo:
3660
3661    In general, if the first test fails, the program can branch
3662    directly to `foo' and skip the second try which is doomed to fail.
3663    We run this after loop optimization and before flow analysis.  */
3664
3665 /* When comparing the insn patterns, we track the fact that different
3666    pseudo-register numbers may have been used in each computation.
3667    The following array stores an equivalence -- same_regs[I] == J means
3668    that pseudo register I was used in the first set of tests in a context
3669    where J was used in the second set.  We also count the number of such
3670    pending equivalences.  If nonzero, the expressions really aren't the
3671    same.  */
3672
3673 static int *same_regs;
3674
3675 static int num_same_regs;
3676
3677 /* Track any registers modified between the target of the first jump and
3678    the second jump.  They never compare equal.  */
3679
3680 static char *modified_regs;
3681
3682 /* Record if memory was modified.  */
3683
3684 static int modified_mem;
3685
3686 /* Called via note_stores on each insn between the target of the first
3687    branch and the second branch.  It marks any changed registers.  */
3688
3689 static void
3690 mark_modified_reg (dest, x, data)
3691      rtx dest;
3692      rtx x ATTRIBUTE_UNUSED;
3693      void *data ATTRIBUTE_UNUSED;
3694 {
3695   int regno;
3696   unsigned int i;
3697
3698   if (GET_CODE (dest) == SUBREG)
3699     dest = SUBREG_REG (dest);
3700
3701   if (GET_CODE (dest) == MEM)
3702     modified_mem = 1;
3703
3704   if (GET_CODE (dest) != REG)
3705     return;
3706
3707   regno = REGNO (dest);
3708   if (regno >= FIRST_PSEUDO_REGISTER)
3709     modified_regs[regno] = 1;
3710   else
3711     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
3712       modified_regs[regno + i] = 1;
3713 }
3714
3715 /* F is the first insn in the chain of insns.  */
3716
3717 void
3718 thread_jumps (f, max_reg, flag_before_loop)
3719      rtx f;
3720      int max_reg;
3721      int flag_before_loop;
3722 {
3723   /* Basic algorithm is to find a conditional branch,
3724      the label it may branch to, and the branch after
3725      that label.  If the two branches test the same condition,
3726      walk back from both branch paths until the insn patterns
3727      differ, or code labels are hit.  If we make it back to
3728      the target of the first branch, then we know that the first branch
3729      will either always succeed or always fail depending on the relative
3730      senses of the two branches.  So adjust the first branch accordingly
3731      in this case.  */
3732
3733   rtx label, b1, b2, t1, t2;
3734   enum rtx_code code1, code2;
3735   rtx b1op0, b1op1, b2op0, b2op1;
3736   int changed = 1;
3737   int i;
3738   int *all_reset;
3739
3740   /* Allocate register tables and quick-reset table.  */
3741   modified_regs = (char *) xmalloc (max_reg * sizeof (char));
3742   same_regs = (int *) xmalloc (max_reg * sizeof (int));
3743   all_reset = (int *) xmalloc (max_reg * sizeof (int));
3744   for (i = 0; i < max_reg; i++)
3745     all_reset[i] = -1;
3746
3747   while (changed)
3748     {
3749       changed = 0;
3750
3751       for (b1 = f; b1; b1 = NEXT_INSN (b1))
3752         {
3753           rtx set;
3754           rtx set2;
3755
3756           /* Get to a candidate branch insn.  */
3757           if (GET_CODE (b1) != JUMP_INSN
3758               || ! any_condjump_p (b1) || JUMP_LABEL (b1) == 0)
3759             continue;
3760
3761           memset (modified_regs, 0, max_reg * sizeof (char));
3762           modified_mem = 0;
3763
3764           memcpy (same_regs, all_reset, max_reg * sizeof (int));
3765           num_same_regs = 0;
3766
3767           label = JUMP_LABEL (b1);
3768
3769           /* Look for a branch after the target.  Record any registers and
3770              memory modified between the target and the branch.  Stop when we
3771              get to a label since we can't know what was changed there.  */
3772           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
3773             {
3774               if (GET_CODE (b2) == CODE_LABEL)
3775                 break;
3776
3777               else if (GET_CODE (b2) == JUMP_INSN)
3778                 {
3779                   /* If this is an unconditional jump and is the only use of
3780                      its target label, we can follow it.  */
3781                   if (any_uncondjump_p (b2)
3782                       && onlyjump_p (b2)
3783                       && JUMP_LABEL (b2) != 0
3784                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
3785                     {
3786                       b2 = JUMP_LABEL (b2);
3787                       continue;
3788                     }
3789                   else
3790                     break;
3791                 }
3792
3793               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
3794                 continue;
3795
3796               if (GET_CODE (b2) == CALL_INSN)
3797                 {
3798                   modified_mem = 1;
3799                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3800                     if (call_used_regs[i] && ! fixed_regs[i]
3801                         && i != STACK_POINTER_REGNUM
3802                         && i != FRAME_POINTER_REGNUM
3803                         && i != HARD_FRAME_POINTER_REGNUM
3804                         && i != ARG_POINTER_REGNUM)
3805                       modified_regs[i] = 1;
3806                 }
3807
3808               note_stores (PATTERN (b2), mark_modified_reg, NULL);
3809             }
3810
3811           /* Check the next candidate branch insn from the label
3812              of the first.  */
3813           if (b2 == 0
3814               || GET_CODE (b2) != JUMP_INSN
3815               || b2 == b1
3816               || !any_condjump_p (b2)
3817               || !onlyjump_p (b2))
3818             continue;
3819           set = pc_set (b1);
3820           set2 = pc_set (b2);
3821
3822           /* Get the comparison codes and operands, reversing the
3823              codes if appropriate.  If we don't have comparison codes,
3824              we can't do anything.  */
3825           b1op0 = XEXP (XEXP (SET_SRC (set), 0), 0);
3826           b1op1 = XEXP (XEXP (SET_SRC (set), 0), 1);
3827           code1 = GET_CODE (XEXP (SET_SRC (set), 0));
3828           if (XEXP (SET_SRC (set), 1) == pc_rtx)
3829             code1 = reverse_condition (code1);
3830
3831           b2op0 = XEXP (XEXP (SET_SRC (set2), 0), 0);
3832           b2op1 = XEXP (XEXP (SET_SRC (set2), 0), 1);
3833           code2 = GET_CODE (XEXP (SET_SRC (set2), 0));
3834           if (XEXP (SET_SRC (set2), 1) == pc_rtx)
3835             code2 = reverse_condition (code2);
3836
3837           /* If they test the same things and knowing that B1 branches
3838              tells us whether or not B2 branches, check if we
3839              can thread the branch.  */
3840           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
3841               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
3842               && (comparison_dominates_p (code1, code2)
3843                   || (can_reverse_comparison_p (XEXP (SET_SRC (set), 0), b1)
3844                       && comparison_dominates_p (code1,
3845                                                  reverse_condition (code2)))))
3846
3847             {
3848               t1 = prev_nonnote_insn (b1);
3849               t2 = prev_nonnote_insn (b2);
3850
3851               while (t1 != 0 && t2 != 0)
3852                 {
3853                   if (t2 == label)
3854                     {
3855                       /* We have reached the target of the first branch.
3856                          If there are no pending register equivalents,
3857                          we know that this branch will either always
3858                          succeed (if the senses of the two branches are
3859                          the same) or always fail (if not).  */
3860                       rtx new_label;
3861
3862                       if (num_same_regs != 0)
3863                         break;
3864
3865                       if (comparison_dominates_p (code1, code2))
3866                         new_label = JUMP_LABEL (b2);
3867                       else
3868                         new_label = get_label_after (b2);
3869
3870                       if (JUMP_LABEL (b1) != new_label)
3871                         {
3872                           rtx prev = PREV_INSN (new_label);
3873
3874                           if (flag_before_loop
3875                               && GET_CODE (prev) == NOTE
3876                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
3877                             {
3878                               /* Don't thread to the loop label.  If a loop
3879                                  label is reused, loop optimization will
3880                                  be disabled for that loop.  */
3881                               new_label = gen_label_rtx ();
3882                               emit_label_after (new_label, PREV_INSN (prev));
3883                             }
3884                           changed |= redirect_jump (b1, new_label, 1);
3885                         }
3886                       break;
3887                     }
3888
3889                   /* If either of these is not a normal insn (it might be
3890                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
3891                      have already been skipped above.)  Similarly, fail
3892                      if the insns are different.  */
3893                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
3894                       || recog_memoized (t1) != recog_memoized (t2)
3895                       || ! rtx_equal_for_thread_p (PATTERN (t1),
3896                                                    PATTERN (t2), t2))
3897                     break;
3898
3899                   t1 = prev_nonnote_insn (t1);
3900                   t2 = prev_nonnote_insn (t2);
3901                 }
3902             }
3903         }
3904     }
3905
3906   /* Clean up.  */
3907   free (modified_regs);
3908   free (same_regs);
3909   free (all_reset);
3910 }
3911 \f
3912 /* This is like RTX_EQUAL_P except that it knows about our handling of
3913    possibly equivalent registers and knows to consider volatile and
3914    modified objects as not equal.
3915
3916    YINSN is the insn containing Y.  */
3917
3918 int
3919 rtx_equal_for_thread_p (x, y, yinsn)
3920      rtx x, y;
3921      rtx yinsn;
3922 {
3923   register int i;
3924   register int j;
3925   register enum rtx_code code;
3926   register const char *fmt;
3927
3928   code = GET_CODE (x);
3929   /* Rtx's of different codes cannot be equal.  */
3930   if (code != GET_CODE (y))
3931     return 0;
3932
3933   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
3934      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
3935
3936   if (GET_MODE (x) != GET_MODE (y))
3937     return 0;
3938
3939   /* For floating-point, consider everything unequal.  This is a bit
3940      pessimistic, but this pass would only rarely do anything for FP
3941      anyway.  */
3942   if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
3943       && FLOAT_MODE_P (GET_MODE (x)) && ! flag_fast_math)
3944     return 0;
3945
3946   /* For commutative operations, the RTX match if the operand match in any
3947      order.  Also handle the simple binary and unary cases without a loop.  */
3948   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3949     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
3950              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
3951             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
3952                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
3953   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
3954     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
3955             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
3956   else if (GET_RTX_CLASS (code) == '1')
3957     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
3958
3959   /* Handle special-cases first.  */
3960   switch (code)
3961     {
3962     case REG:
3963       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
3964         return 1;
3965
3966       /* If neither is user variable or hard register, check for possible
3967          equivalence.  */
3968       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
3969           || REGNO (x) < FIRST_PSEUDO_REGISTER
3970           || REGNO (y) < FIRST_PSEUDO_REGISTER)
3971         return 0;
3972
3973       if (same_regs[REGNO (x)] == -1)
3974         {
3975           same_regs[REGNO (x)] = REGNO (y);
3976           num_same_regs++;
3977
3978           /* If this is the first time we are seeing a register on the `Y'
3979              side, see if it is the last use.  If not, we can't thread the
3980              jump, so mark it as not equivalent.  */
3981           if (REGNO_LAST_UID (REGNO (y)) != INSN_UID (yinsn))
3982             return 0;
3983
3984           return 1;
3985         }
3986       else
3987         return (same_regs[REGNO (x)] == (int) REGNO (y));
3988
3989       break;
3990
3991     case MEM:
3992       /* If memory modified or either volatile, not equivalent.
3993          Else, check address.  */
3994       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
3995         return 0;
3996
3997       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
3998
3999     case ASM_INPUT:
4000       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4001         return 0;
4002
4003       break;
4004
4005     case SET:
4006       /* Cancel a pending `same_regs' if setting equivalenced registers.
4007          Then process source.  */
4008       if (GET_CODE (SET_DEST (x)) == REG
4009           && GET_CODE (SET_DEST (y)) == REG)
4010         {
4011           if (same_regs[REGNO (SET_DEST (x))] == (int) REGNO (SET_DEST (y)))
4012             {
4013               same_regs[REGNO (SET_DEST (x))] = -1;
4014               num_same_regs--;
4015             }
4016           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
4017             return 0;
4018         }
4019       else
4020         {
4021           if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
4022             return 0;
4023         }
4024
4025       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
4026
4027     case LABEL_REF:
4028       return XEXP (x, 0) == XEXP (y, 0);
4029
4030     case SYMBOL_REF:
4031       return XSTR (x, 0) == XSTR (y, 0);
4032
4033     default:
4034       break;
4035     }
4036
4037   if (x == y)
4038     return 1;
4039
4040   fmt = GET_RTX_FORMAT (code);
4041   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4042     {
4043       switch (fmt[i])
4044         {
4045         case 'w':
4046           if (XWINT (x, i) != XWINT (y, i))
4047             return 0;
4048           break;
4049
4050         case 'n':
4051         case 'i':
4052           if (XINT (x, i) != XINT (y, i))
4053             return 0;
4054           break;
4055
4056         case 'V':
4057         case 'E':
4058           /* Two vectors must have the same length.  */
4059           if (XVECLEN (x, i) != XVECLEN (y, i))
4060             return 0;
4061
4062           /* And the corresponding elements must match.  */
4063           for (j = 0; j < XVECLEN (x, i); j++)
4064             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
4065                                         XVECEXP (y, i, j), yinsn) == 0)
4066               return 0;
4067           break;
4068
4069         case 'e':
4070           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
4071             return 0;
4072           break;
4073
4074         case 'S':
4075         case 's':
4076           if (strcmp (XSTR (x, i), XSTR (y, i)))
4077             return 0;
4078           break;
4079
4080         case 'u':
4081           /* These are just backpointers, so they don't matter.  */
4082           break;
4083
4084         case '0':
4085         case 't':
4086           break;
4087
4088           /* It is believed that rtx's at this level will never
4089              contain anything but integers and other rtx's,
4090              except for within LABEL_REFs and SYMBOL_REFs.  */
4091         default:
4092           abort ();
4093         }
4094     }
4095   return 1;
4096 }