gcc/jump.c

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