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