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