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