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