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