gcc/jump.c

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