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