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