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