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