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