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