gcc/jump.c

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