gcc/jump.c

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