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