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