gcc/jump.c

   1 /* Optimize jump instructions, for GNU compiler.
   2    Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
   3    1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* This is the pathetic reminder of old fame of the jump-optimization pass
  23    of the compiler.  Now it contains basically set of utility function to
  24    operate with jumps.
  25
  26    Each CODE_LABEL has a count of the times it is used
  27    stored in the LABEL_NUSES internal field, and each JUMP_INSN
  28    has one label that it refers to stored in the
  29    JUMP_LABEL internal field.  With this we can detect labels that
  30    become unused because of the deletion of all the jumps that
  31    formerly used them.  The JUMP_LABEL info is sometimes looked
  32    at by later passes.
  33
  34    The subroutines delete_insn, redirect_jump, and invert_jump are used
  35    from other passes as well.  */
  36
  37 #include "config.h"
  38 #include "system.h"
  39 #include "rtl.h"
  40 #include "tm_p.h"
  41 #include "flags.h"
  42 #include "hard-reg-set.h"
  43 #include "regs.h"
  44 #include "insn-config.h"
  45 #include "insn-attr.h"
  46 #include "recog.h"
  47 #include "function.h"
  48 #include "expr.h"
  49 #include "real.h"
  50 #include "except.h"
  51 #include "toplev.h"
  52 #include "reload.h"
  53 #include "predict.h"
  54
  55 /* Optimize jump y; x: ... y: jumpif... x?
  56    Don't know if it is worth bothering with.  */
  57 /* Optimize two cases of conditional jump to conditional jump?
  58    This can never delete any instruction or make anything dead,
  59    or even change what is live at any point.
  60    So perhaps let combiner do it.  */
  61
  62 static int init_label_info              PARAMS ((rtx));
  63 static void mark_all_labels             PARAMS ((rtx));
  64 static int duplicate_loop_exit_test     PARAMS ((rtx));
  65 static void delete_computation          PARAMS ((rtx));
  66 static void redirect_exp_1              PARAMS ((rtx *, rtx, rtx, rtx));
  67 static int redirect_exp                 PARAMS ((rtx, rtx, rtx));
  68 static void invert_exp_1                PARAMS ((rtx));
  69 static int invert_exp                   PARAMS ((rtx));
  70 static int returnjump_p_1               PARAMS ((rtx *, void *));
  71 static void delete_prior_computation    PARAMS ((rtx, rtx));
  72 static void mark_modified_reg           PARAMS ((rtx, rtx, void *));
  73 \f
  74 /* Alternate entry into the jump optimizer.  This entry point only rebuilds
  75    the JUMP_LABEL field in jumping insns and REG_LABEL notes in non-jumping
  76    instructions.  */
  77 void
  78 rebuild_jump_labels (f)
  79      rtx f;
  80 {
  81   register rtx insn;
  82   int max_uid = 0;
  83
  84   max_uid = init_label_info (f) + 1;
  85
  86   mark_all_labels (f);
  87
  88   /* Keep track of labels used from static data; we don't track them
  89      closely enough to delete them here, so make sure their reference
  90      count doesn't drop to zero.  */
  91
  92   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
  93     if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
  94       LABEL_NUSES (XEXP (insn, 0))++;
  95
  96   /* Keep track of labels used for marking handlers for exception
  97      regions; they cannot usually be deleted.  */
  98
  99   for (insn = exception_handler_labels; insn; insn = XEXP (insn, 1))
 100     if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
 101       LABEL_NUSES (XEXP (insn, 0))++;
 102 }
 103 \f
 104 /* Some old code expects exactly one BARRIER as the NEXT_INSN of a
 105    non-fallthru insn.  This is not generally true, as multiple barriers
 106    may have crept in, or the BARRIER may be separated from the last
 107    real insn by one or more NOTEs.
 108
 109    This simple pass moves barriers and removes duplicates so that the
 110    old code is happy.
 111  */
 112 void
 113 cleanup_barriers ()
 114 {
 115   rtx insn, next, prev;
 116   for (insn = get_insns (); insn; insn = next)
 117     {
 118       next = NEXT_INSN (insn);
 119       if (GET_CODE (insn) == BARRIER)
 120         {
 121           prev = prev_nonnote_insn (insn);
 122           if (GET_CODE (prev) == BARRIER)
 123             delete_barrier (insn);
 124           else if (prev != PREV_INSN (insn))
 125             reorder_insns (insn, insn, prev);
 126         }
 127     }
 128 }
 129 \f
 130 void
 131 copy_loop_headers (f)
 132      rtx f;
 133 {
 134   register rtx insn, next;
 135   /* Now iterate optimizing jumps until nothing changes over one pass.  */
 136   for (insn = f; insn; insn = next)
 137     {
 138       rtx temp, temp1;
 139
 140       next = NEXT_INSN (insn);
 141
 142       /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
 143          jump.  Try to optimize by duplicating the loop exit test if so.
 144          This is only safe immediately after regscan, because it uses
 145          the values of regno_first_uid and regno_last_uid.  */
 146       if (GET_CODE (insn) == NOTE
 147           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 148           && (temp1 = next_nonnote_insn (insn)) != 0
 149           && any_uncondjump_p (temp1) && onlyjump_p (temp1))
 150         {
 151           temp = PREV_INSN (insn);
 152           if (duplicate_loop_exit_test (insn))
 153             {
 154               next = NEXT_INSN (temp);
 155             }
 156         }
 157     }
 158 }
 159
 160 void
 161 purge_line_number_notes (f)
 162      rtx f;
 163 {
 164   rtx last_note = 0;
 165   rtx insn;
 166   /* Delete extraneous line number notes.
 167      Note that two consecutive notes for different lines are not really
 168      extraneous.  There should be some indication where that line belonged,
 169      even if it became empty.  */
 170
 171   for (insn = f; insn; insn = NEXT_INSN (insn))
 172     if (GET_CODE (insn) == NOTE)
 173       {
 174         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
 175           /* Any previous line note was for the prologue; gdb wants a new
 176              note after the prologue even if it is for the same line.  */
 177           last_note = NULL_RTX;
 178         else if (NOTE_LINE_NUMBER (insn) >= 0)
 179           {
 180             /* Delete this note if it is identical to previous note.  */
 181             if (last_note
 182                 && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
 183                 && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
 184               {
 185                 delete_insn (insn);
 186                 continue;
 187               }
 188
 189             last_note = insn;
 190           }
 191       }
 192 }
 193 \f
 194 /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
 195    notes whose labels don't occur in the insn any more.  Returns the
 196    largest INSN_UID found.  */
 197 static int
 198 init_label_info (f)
 199      rtx f;
 200 {
 201   int largest_uid = 0;
 202   rtx insn;
 203
 204   for (insn = f; insn; insn = NEXT_INSN (insn))
 205     {
 206       if (GET_CODE (insn) == CODE_LABEL)
 207         LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
 208       else if (GET_CODE (insn) == JUMP_INSN)
 209         JUMP_LABEL (insn) = 0;
 210       else if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 211         {
 212           rtx note, next;
 213
 214           for (note = REG_NOTES (insn); note; note = next)
 215             {
 216               next = XEXP (note, 1);
 217               if (REG_NOTE_KIND (note) == REG_LABEL
 218                   && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
 219                 remove_note (insn, note);
 220             }
 221         }
 222       if (INSN_UID (insn) > largest_uid)
 223         largest_uid = INSN_UID (insn);
 224     }
 225
 226   return largest_uid;
 227 }
 228
 229 /* Mark the label each jump jumps to.
 230    Combine consecutive labels, and count uses of labels.  */
 231
 232 static void
 233 mark_all_labels (f)
 234      rtx f;
 235 {
 236   rtx insn;
 237
 238   for (insn = f; insn; insn = NEXT_INSN (insn))
 239     if (INSN_P (insn))
 240       {
 241         if (GET_CODE (insn) == CALL_INSN
 242             && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 243           {
 244             mark_all_labels (XEXP (PATTERN (insn), 0));
 245             mark_all_labels (XEXP (PATTERN (insn), 1));
 246             mark_all_labels (XEXP (PATTERN (insn), 2));
 247
 248             /* Canonicalize the tail recursion label attached to the
 249                CALL_PLACEHOLDER insn.  */
 250             if (XEXP (PATTERN (insn), 3))
 251               {
 252                 rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
 253                                                    XEXP (PATTERN (insn), 3));
 254                 mark_jump_label (label_ref, insn, 0);
 255                 XEXP (PATTERN (insn), 3) = XEXP (label_ref, 0);
 256               }
 257
 258             continue;
 259           }
 260
 261         mark_jump_label (PATTERN (insn), insn, 0);
 262         if (! INSN_DELETED_P (insn) && GET_CODE (insn) == JUMP_INSN)
 263           {
 264             /* When we know the LABEL_REF contained in a REG used in
 265                an indirect jump, we'll have a REG_LABEL note so that
 266                flow can tell where it's going.  */
 267             if (JUMP_LABEL (insn) == 0)
 268               {
 269                 rtx label_note = find_reg_note (insn, REG_LABEL, NULL_RTX);
 270                 if (label_note)
 271                   {
 272                     /* But a LABEL_REF around the REG_LABEL note, so
 273                        that we can canonicalize it.  */
 274                     rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
 275                                                        XEXP (label_note, 0));
 276
 277                     mark_jump_label (label_ref, insn, 0);
 278                     XEXP (label_note, 0) = XEXP (label_ref, 0);
 279                     JUMP_LABEL (insn) = XEXP (label_note, 0);
 280                   }
 281               }
 282           }
 283       }
 284 }
 285
 286 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
 287    jump.  Assume that this unconditional jump is to the exit test code.  If
 288    the code is sufficiently simple, make a copy of it before INSN,
 289    followed by a jump to the exit of the loop.  Then delete the unconditional
 290    jump after INSN.
 291
 292    Return 1 if we made the change, else 0.
 293
 294    This is only safe immediately after a regscan pass because it uses the
 295    values of regno_first_uid and regno_last_uid.  */
 296
 297 static int
 298 duplicate_loop_exit_test (loop_start)
 299      rtx loop_start;
 300 {
 301   rtx insn, set, reg, p, link;
 302   rtx copy = 0, first_copy = 0;
 303   int num_insns = 0;
 304   rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
 305   rtx lastexit;
 306   int max_reg = max_reg_num ();
 307   rtx *reg_map = 0;
 308   rtx loop_pre_header_label;
 309
 310   /* Scan the exit code.  We do not perform this optimization if any insn:
 311
 312          is a CALL_INSN
 313          is a CODE_LABEL
 314          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
 315          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
 316          is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
 317               is not valid.
 318
 319      We also do not do this if we find an insn with ASM_OPERANDS.  While
 320      this restriction should not be necessary, copying an insn with
 321      ASM_OPERANDS can confuse asm_noperands in some cases.
 322
 323      Also, don't do this if the exit code is more than 20 insns.  */
 324
 325   for (insn = exitcode;
 326        insn
 327        && ! (GET_CODE (insn) == NOTE
 328              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
 329        insn = NEXT_INSN (insn))
 330     {
 331       switch (GET_CODE (insn))
 332         {
 333         case CODE_LABEL:
 334         case CALL_INSN:
 335           return 0;
 336         case NOTE:
 337           /* We could be in front of the wrong NOTE_INSN_LOOP_END if there is
 338              a jump immediately after the loop start that branches outside
 339              the loop but within an outer loop, near the exit test.
 340              If we copied this exit test and created a phony
 341              NOTE_INSN_LOOP_VTOP, this could make instructions immediately
 342              before the exit test look like these could be safely moved
 343              out of the loop even if they actually may be never executed.
 344              This can be avoided by checking here for NOTE_INSN_LOOP_CONT.  */
 345
 346           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 347               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
 348             return 0;
 349
 350           if (optimize < 2
 351               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
 352                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
 353             /* If we were to duplicate this code, we would not move
 354                the BLOCK notes, and so debugging the moved code would
 355                be difficult.  Thus, we only move the code with -O2 or
 356                higher.  */
 357             return 0;
 358
 359           break;
 360         case JUMP_INSN:
 361         case INSN:
 362           /* The code below would grossly mishandle REG_WAS_0 notes,
 363              so get rid of them here.  */
 364           while ((p = find_reg_note (insn, REG_WAS_0, NULL_RTX)) != 0)
 365             remove_note (insn, p);
 366           if (++num_insns > 20
 367               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
 368               || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
 369             return 0;
 370           break;
 371         default:
 372           break;
 373         }
 374     }
 375
 376   /* Unless INSN is zero, we can do the optimization.  */
 377   if (insn == 0)
 378     return 0;
 379
 380   lastexit = insn;
 381
 382   /* See if any insn sets a register only used in the loop exit code and
 383      not a user variable.  If so, replace it with a new register.  */
 384   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
 385     if (GET_CODE (insn) == INSN
 386         && (set = single_set (insn)) != 0
 387         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
 388             || (GET_CODE (reg) == SUBREG
 389                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
 390         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
 391         && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
 392       {
 393         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
 394           if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
 395             break;
 396
 397         if (p != lastexit)
 398           {
 399             /* We can do the replacement.  Allocate reg_map if this is the
 400                first replacement we found.  */
 401             if (reg_map == 0)
 402               reg_map = (rtx *) xcalloc (max_reg, sizeof (rtx));
 403
 404             REG_LOOP_TEST_P (reg) = 1;
 405
 406             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
 407           }
 408       }
 409   loop_pre_header_label = gen_label_rtx ();
 410
 411   /* Now copy each insn.  */
 412   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
 413     {
 414       switch (GET_CODE (insn))
 415         {
 416         case BARRIER:
 417           copy = emit_barrier_before (loop_start);
 418           break;
 419         case NOTE:
 420           /* Only copy line-number notes.  */
 421           if (NOTE_LINE_NUMBER (insn) >= 0)
 422             {
 423               copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
 424               NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
 425             }
 426           break;
 427
 428         case INSN:
 429           copy = emit_insn_before (copy_insn (PATTERN (insn)), loop_start);
 430           if (reg_map)
 431             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
 432
 433           mark_jump_label (PATTERN (copy), copy, 0);
 434
 435           /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
 436              make them.  */
 437           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 438             if (REG_NOTE_KIND (link) != REG_LABEL)
 439               {
 440                 if (GET_CODE (link) == EXPR_LIST)
 441                   REG_NOTES (copy)
 442                     = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
 443                                                       XEXP (link, 0),
 444                                                       REG_NOTES (copy)));
 445                 else
 446                   REG_NOTES (copy)
 447                     = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
 448                                                       XEXP (link, 0),
 449                                                       REG_NOTES (copy)));
 450               }
 451
 452           if (reg_map && REG_NOTES (copy))
 453             replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
 454           break;
 455
 456         case JUMP_INSN:
 457           copy = emit_jump_insn_before (copy_insn (PATTERN (insn)),
 458                                         loop_start);
 459           if (reg_map)
 460             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
 461           mark_jump_label (PATTERN (copy), copy, 0);
 462           if (REG_NOTES (insn))
 463             {
 464               REG_NOTES (copy) = copy_insn_1 (REG_NOTES (insn));
 465               if (reg_map)
 466                 replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
 467             }
 468
 469           /* Predict conditional jump that do make loop looping as taken.
 470              Other jumps are probably exit conditions, so predict
 471              them as untaken.  */
 472           if (any_condjump_p (copy))
 473             {
 474               rtx label = JUMP_LABEL (copy);
 475               if (label)
 476                 {
 477                   /* The jump_insn after loop_start should be followed
 478                      by barrier and loopback label.  */
 479                   if (prev_nonnote_insn (label)
 480                       && (prev_nonnote_insn (prev_nonnote_insn (label))
 481                           == next_nonnote_insn (loop_start)))
 482                     {
 483                       predict_insn_def (copy, PRED_LOOP_HEADER, TAKEN);
 484                       /* To keep pre-header, we need to redirect all loop
 485                          entrances before the LOOP_BEG note.  */
 486                       redirect_jump (copy, loop_pre_header_label, 0);
 487                     }
 488                   else
 489                     predict_insn_def (copy, PRED_LOOP_HEADER, NOT_TAKEN);
 490                 }
 491             }
 492           break;
 493
 494         default:
 495           abort ();
 496         }
 497
 498       /* Record the first insn we copied.  We need it so that we can
 499          scan the copied insns for new pseudo registers.  */
 500       if (! first_copy)
 501         first_copy = copy;
 502     }
 503
 504   /* Now clean up by emitting a jump to the end label and deleting the jump
 505      at the start of the loop.  */
 506   if (! copy || GET_CODE (copy) != BARRIER)
 507     {
 508       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
 509                                     loop_start);
 510
 511       /* Record the first insn we copied.  We need it so that we can
 512          scan the copied insns for new pseudo registers.   This may not
 513          be strictly necessary since we should have copied at least one
 514          insn above.  But I am going to be safe.  */
 515       if (! first_copy)
 516         first_copy = copy;
 517
 518       mark_jump_label (PATTERN (copy), copy, 0);
 519       emit_barrier_before (loop_start);
 520     }
 521
 522   emit_label_before (loop_pre_header_label, loop_start);
 523
 524   /* Now scan from the first insn we copied to the last insn we copied
 525      (copy) for new pseudo registers.  Do this after the code to jump to
 526      the end label since that might create a new pseudo too.  */
 527   reg_scan_update (first_copy, copy, max_reg);
 528
 529   /* Mark the exit code as the virtual top of the converted loop.  */
 530   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
 531
 532   delete_insn (next_nonnote_insn (loop_start));
 533
 534   /* Clean up.  */
 535   if (reg_map)
 536     free (reg_map);
 537
 538   return 1;
 539 }
 540 \f
 541 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, loop-end,
 542    notes between START and END out before START.  Assume that END is not
 543    such a note.  START may be such a note.  Returns the value of the new
 544    starting insn, which may be different if the original start was such a
 545    note.  */
 546
 547 rtx
 548 squeeze_notes (start, end)
 549      rtx start, end;
 550 {
 551   rtx insn;
 552   rtx next;
 553
 554   for (insn = start; insn != end; insn = next)
 555     {
 556       next = NEXT_INSN (insn);
 557       if (GET_CODE (insn) == NOTE
 558           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
 559               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
 560               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 561               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
 562               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
 563               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
 564         {
 565           if (insn == start)
 566             start = next;
 567           else
 568             {
 569               rtx prev = PREV_INSN (insn);
 570               PREV_INSN (insn) = PREV_INSN (start);
 571               NEXT_INSN (insn) = start;
 572               NEXT_INSN (PREV_INSN (insn)) = insn;
 573               PREV_INSN (NEXT_INSN (insn)) = insn;
 574               NEXT_INSN (prev) = next;
 575               PREV_INSN (next) = prev;
 576             }
 577         }
 578     }
 579
 580   return start;
 581 }
 582 \f
 583 /* Return the label before INSN, or put a new label there.  */
 584
 585 rtx
 586 get_label_before (insn)
 587      rtx insn;
 588 {
 589   rtx label;
 590
 591   /* Find an existing label at this point
 592      or make a new one if there is none.  */
 593   label = prev_nonnote_insn (insn);
 594
 595   if (label == 0 || GET_CODE (label) != CODE_LABEL)
 596     {
 597       rtx prev = PREV_INSN (insn);
 598
 599       label = gen_label_rtx ();
 600       emit_label_after (label, prev);
 601       LABEL_NUSES (label) = 0;
 602     }
 603   return label;
 604 }
 605
 606 /* Return the label after INSN, or put a new label there.  */
 607
 608 rtx
 609 get_label_after (insn)
 610      rtx insn;
 611 {
 612   rtx label;
 613
 614   /* Find an existing label at this point
 615      or make a new one if there is none.  */
 616   label = next_nonnote_insn (insn);
 617
 618   if (label == 0 || GET_CODE (label) != CODE_LABEL)
 619     {
 620       label = gen_label_rtx ();
 621       emit_label_after (label, insn);
 622       LABEL_NUSES (label) = 0;
 623     }
 624   return label;
 625 }
 626 \f
 627 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
 628    of reversed comparison if it is possible to do so.  Otherwise return UNKNOWN.
 629    UNKNOWN may be returned in case we are having CC_MODE compare and we don't
 630    know whether it's source is floating point or integer comparison.  Machine
 631    description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
 632    to help this function avoid overhead in these cases.  */
 633 enum rtx_code
 634 reversed_comparison_code_parts (code, arg0, arg1, insn)
 635      rtx insn, arg0, arg1;
 636      enum rtx_code code;
 637 {
 638   enum machine_mode mode;
 639
 640   /* If this is not actually a comparison, we can't reverse it.  */
 641   if (GET_RTX_CLASS (code) != '<')
 642     return UNKNOWN;
 643
 644   mode = GET_MODE (arg0);
 645   if (mode == VOIDmode)
 646     mode = GET_MODE (arg1);
 647
 648   /* First see if machine description supply us way to reverse the comparison.
 649      Give it priority over everything else to allow machine description to do
 650      tricks.  */
 651 #ifdef REVERSIBLE_CC_MODE
 652   if (GET_MODE_CLASS (mode) == MODE_CC
 653       && REVERSIBLE_CC_MODE (mode))
 654     {
 655 #ifdef REVERSE_CONDITION
 656       return REVERSE_CONDITION (code, mode);
 657 #endif
 658       return reverse_condition (code);
 659     }
 660 #endif
 661
 662   /* Try a few special cases based on the comparison code.  */
 663   switch (code)
 664     {
 665     case GEU:
 666     case GTU:
 667     case LEU:
 668     case LTU:
 669     case NE:
 670     case EQ:
 671       /* It is always safe to reverse EQ and NE, even for the floating
 672          point.  Similary the unsigned comparisons are never used for
 673          floating point so we can reverse them in the default way.  */
 674       return reverse_condition (code);
 675     case ORDERED:
 676     case UNORDERED:
 677     case LTGT:
 678     case UNEQ:
 679       /* In case we already see unordered comparison, we can be sure to
 680          be dealing with floating point so we don't need any more tests.  */
 681       return reverse_condition_maybe_unordered (code);
 682     case UNLT:
 683     case UNLE:
 684     case UNGT:
 685     case UNGE:
 686       /* We don't have safe way to reverse these yet.  */
 687       return UNKNOWN;
 688     default:
 689       break;
 690     }
 691
 692   /* In case we give up IEEE compatibility, all comparisons are reversible.  */
 693   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
 694       || flag_unsafe_math_optimizations)
 695     return reverse_condition (code);
 696
 697   if (GET_MODE_CLASS (mode) == MODE_CC
 698 #ifdef HAVE_cc0
 699       || arg0 == cc0_rtx
 700 #endif
 701       )
 702     {
 703       rtx prev;
 704       /* Try to search for the comparison to determine the real mode.
 705          This code is expensive, but with sane machine description it
 706          will be never used, since REVERSIBLE_CC_MODE will return true
 707          in all cases.  */
 708       if (! insn)
 709         return UNKNOWN;
 710
 711       for (prev = prev_nonnote_insn (insn);
 712            prev != 0 && GET_CODE (prev) != CODE_LABEL;
 713            prev = prev_nonnote_insn (prev))
 714         {
 715           rtx set = set_of (arg0, prev);
 716           if (set && GET_CODE (set) == SET
 717               && rtx_equal_p (SET_DEST (set), arg0))
 718             {
 719               rtx src = SET_SRC (set);
 720
 721               if (GET_CODE (src) == COMPARE)
 722                 {
 723                   rtx comparison = src;
 724                   arg0 = XEXP (src, 0);
 725                   mode = GET_MODE (arg0);
 726                   if (mode == VOIDmode)
 727                     mode = GET_MODE (XEXP (comparison, 1));
 728                   break;
 729                 }
 730               /* We can get past reg-reg moves.  This may be usefull for model
 731                  of i387 comparisons that first move flag registers around.  */
 732               if (REG_P (src))
 733                 {
 734                   arg0 = src;
 735                   continue;
 736                 }
 737             }
 738           /* If register is clobbered in some ununderstandable way,
 739              give up.  */
 740           if (set)
 741             return UNKNOWN;
 742         }
 743     }
 744
 745   /* An integer condition.  */
 746   if (GET_CODE (arg0) == CONST_INT
 747       || (GET_MODE (arg0) != VOIDmode
 748           && GET_MODE_CLASS (mode) != MODE_CC
 749           && ! FLOAT_MODE_P (mode)))
 750     return reverse_condition (code);
 751
 752   return UNKNOWN;
 753 }
 754
 755 /* An wrapper around the previous function to take COMPARISON as rtx
 756    expression.  This simplifies many callers.  */
 757 enum rtx_code
 758 reversed_comparison_code (comparison, insn)
 759      rtx comparison, insn;
 760 {
 761   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
 762     return UNKNOWN;
 763   return reversed_comparison_code_parts (GET_CODE (comparison),
 764                                          XEXP (comparison, 0),
 765                                          XEXP (comparison, 1), insn);
 766 }
 767 \f
 768 /* Given an rtx-code for a comparison, return the code for the negated
 769    comparison.  If no such code exists, return UNKNOWN.
 770
 771    WATCH OUT!  reverse_condition is not safe to use on a jump that might
 772    be acting on the results of an IEEE floating point comparison, because
 773    of the special treatment of non-signaling nans in comparisons.
 774    Use reversed_comparison_code instead.  */
 775
 776 enum rtx_code
 777 reverse_condition (code)
 778      enum rtx_code code;
 779 {
 780   switch (code)
 781     {
 782     case EQ:
 783       return NE;
 784     case NE:
 785       return EQ;
 786     case GT:
 787       return LE;
 788     case GE:
 789       return LT;
 790     case LT:
 791       return GE;
 792     case LE:
 793       return GT;
 794     case GTU:
 795       return LEU;
 796     case GEU:
 797       return LTU;
 798     case LTU:
 799       return GEU;
 800     case LEU:
 801       return GTU;
 802     case UNORDERED:
 803       return ORDERED;
 804     case ORDERED:
 805       return UNORDERED;
 806
 807     case UNLT:
 808     case UNLE:
 809     case UNGT:
 810     case UNGE:
 811     case UNEQ:
 812     case LTGT:
 813       return UNKNOWN;
 814
 815     default:
 816       abort ();
 817     }
 818 }
 819
 820 /* Similar, but we're allowed to generate unordered comparisons, which
 821    makes it safe for IEEE floating-point.  Of course, we have to recognize
 822    that the target will support them too...  */
 823
 824 enum rtx_code
 825 reverse_condition_maybe_unordered (code)
 826      enum rtx_code code;
 827 {
 828   /* Non-IEEE formats don't have unordered conditions.  */
 829   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
 830     return reverse_condition (code);
 831
 832   switch (code)
 833     {
 834     case EQ:
 835       return NE;
 836     case NE:
 837       return EQ;
 838     case GT:
 839       return UNLE;
 840     case GE:
 841       return UNLT;
 842     case LT:
 843       return UNGE;
 844     case LE:
 845       return UNGT;
 846     case LTGT:
 847       return UNEQ;
 848     case UNORDERED:
 849       return ORDERED;
 850     case ORDERED:
 851       return UNORDERED;
 852     case UNLT:
 853       return GE;
 854     case UNLE:
 855       return GT;
 856     case UNGT:
 857       return LE;
 858     case UNGE:
 859       return LT;
 860     case UNEQ:
 861       return LTGT;
 862
 863     default:
 864       abort ();
 865     }
 866 }
 867
 868 /* Similar, but return the code when two operands of a comparison are swapped.
 869    This IS safe for IEEE floating-point.  */
 870
 871 enum rtx_code
 872 swap_condition (code)
 873      enum rtx_code code;
 874 {
 875   switch (code)
 876     {
 877     case EQ:
 878     case NE:
 879     case UNORDERED:
 880     case ORDERED:
 881     case UNEQ:
 882     case LTGT:
 883       return code;
 884
 885     case GT:
 886       return LT;
 887     case GE:
 888       return LE;
 889     case LT:
 890       return GT;
 891     case LE:
 892       return GE;
 893     case GTU:
 894       return LTU;
 895     case GEU:
 896       return LEU;
 897     case LTU:
 898       return GTU;
 899     case LEU:
 900       return GEU;
 901     case UNLT:
 902       return UNGT;
 903     case UNLE:
 904       return UNGE;
 905     case UNGT:
 906       return UNLT;
 907     case UNGE:
 908       return UNLE;
 909
 910     default:
 911       abort ();
 912     }
 913 }
 914
 915 /* Given a comparison CODE, return the corresponding unsigned comparison.
 916    If CODE is an equality comparison or already an unsigned comparison,
 917    CODE is returned.  */
 918
 919 enum rtx_code
 920 unsigned_condition (code)
 921      enum rtx_code code;
 922 {
 923   switch (code)
 924     {
 925     case EQ:
 926     case NE:
 927     case GTU:
 928     case GEU:
 929     case LTU:
 930     case LEU:
 931       return code;
 932
 933     case GT:
 934       return GTU;
 935     case GE:
 936       return GEU;
 937     case LT:
 938       return LTU;
 939     case LE:
 940       return LEU;
 941
 942     default:
 943       abort ();
 944     }
 945 }
 946
 947 /* Similarly, return the signed version of a comparison.  */
 948
 949 enum rtx_code
 950 signed_condition (code)
 951      enum rtx_code code;
 952 {
 953   switch (code)
 954     {
 955     case EQ:
 956     case NE:
 957     case GT:
 958     case GE:
 959     case LT:
 960     case LE:
 961       return code;
 962
 963     case GTU:
 964       return GT;
 965     case GEU:
 966       return GE;
 967     case LTU:
 968       return LT;
 969     case LEU:
 970       return LE;
 971
 972     default:
 973       abort ();
 974     }
 975 }
 976 \f
 977 /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
 978    truth of CODE1 implies the truth of CODE2.  */
 979
 980 int
 981 comparison_dominates_p (code1, code2)
 982      enum rtx_code code1, code2;
 983 {
 984   /* UNKNOWN comparison codes can happen as a result of trying to revert
 985      comparison codes.
 986      They can't match anything, so we have to reject them here.  */
 987   if (code1 == UNKNOWN || code2 == UNKNOWN)
 988     return 0;
 989
 990   if (code1 == code2)
 991     return 1;
 992
 993   switch (code1)
 994     {
 995     case UNEQ:
 996       if (code2 == UNLE || code2 == UNGE)
 997         return 1;
 998       break;
 999
1000     case EQ:
1001       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
1002           || code2 == ORDERED)
1003         return 1;
1004       break;
1005
1006     case UNLT:
1007       if (code2 == UNLE || code2 == NE)
1008         return 1;
1009       break;
1010
1011     case LT:
1012       if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
1013         return 1;
1014       break;
1015
1016     case UNGT:
1017       if (code2 == UNGE || code2 == NE)
1018         return 1;
1019       break;
1020
1021     case GT:
1022       if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
1023         return 1;
1024       break;
1025
1026     case GE:
1027     case LE:
1028       if (code2 == ORDERED)
1029         return 1;
1030       break;
1031
1032     case LTGT:
1033       if (code2 == NE || code2 == ORDERED)
1034         return 1;
1035       break;
1036
1037     case LTU:
1038       if (code2 == LEU || code2 == NE)
1039         return 1;
1040       break;
1041
1042     case GTU:
1043       if (code2 == GEU || code2 == NE)
1044         return 1;
1045       break;
1046
1047     case UNORDERED:
1048       if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
1049           || code2 == UNGE || code2 == UNGT)
1050         return 1;
1051       break;
1052
1053     default:
1054       break;
1055     }
1056
1057   return 0;
1058 }
1059 \f
1060 /* Return 1 if INSN is an unconditional jump and nothing else.  */
1061
1062 int
1063 simplejump_p (insn)
1064      rtx insn;
1065 {
1066   return (GET_CODE (insn) == JUMP_INSN
1067           && GET_CODE (PATTERN (insn)) == SET
1068           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
1069           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
1070 }
1071
1072 /* Return nonzero if INSN is a (possibly) conditional jump
1073    and nothing more.
1074
1075    Use this function is deprecated, since we need to support combined
1076    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
1077
1078 int
1079 condjump_p (insn)
1080      rtx insn;
1081 {
1082   register rtx x = PATTERN (insn);
1083
1084   if (GET_CODE (x) != SET
1085       || GET_CODE (SET_DEST (x)) != PC)
1086     return 0;
1087
1088   x = SET_SRC (x);
1089   if (GET_CODE (x) == LABEL_REF)
1090     return 1;
1091   else
1092     return (GET_CODE (x) == IF_THEN_ELSE
1093             && ((GET_CODE (XEXP (x, 2)) == PC
1094                  && (GET_CODE (XEXP (x, 1)) == LABEL_REF
1095                      || GET_CODE (XEXP (x, 1)) == RETURN))
1096                 || (GET_CODE (XEXP (x, 1)) == PC
1097                     && (GET_CODE (XEXP (x, 2)) == LABEL_REF
1098                         || GET_CODE (XEXP (x, 2)) == RETURN))));
1099
1100   return 0;
1101 }
1102
1103 /* Return nonzero if INSN is a (possibly) conditional jump inside a
1104    PARALLEL.
1105
1106    Use this function is deprecated, since we need to support combined
1107    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
1108
1109 int
1110 condjump_in_parallel_p (insn)
1111      rtx insn;
1112 {
1113   register rtx x = PATTERN (insn);
1114
1115   if (GET_CODE (x) != PARALLEL)
1116     return 0;
1117   else
1118     x = XVECEXP (x, 0, 0);
1119
1120   if (GET_CODE (x) != SET)
1121     return 0;
1122   if (GET_CODE (SET_DEST (x)) != PC)
1123     return 0;
1124   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
1125     return 1;
1126   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
1127     return 0;
1128   if (XEXP (SET_SRC (x), 2) == pc_rtx
1129       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
1130           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
1131     return 1;
1132   if (XEXP (SET_SRC (x), 1) == pc_rtx
1133       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
1134           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
1135     return 1;
1136   return 0;
1137 }
1138
1139 /* Return set of PC, otherwise NULL.  */
1140
1141 rtx
1142 pc_set (insn)
1143      rtx insn;
1144 {
1145   rtx pat;
1146   if (GET_CODE (insn) != JUMP_INSN)
1147     return NULL_RTX;
1148   pat = PATTERN (insn);
1149
1150   /* The set is allowed to appear either as the insn pattern or
1151      the first set in a PARALLEL.  */
1152   if (GET_CODE (pat) == PARALLEL)
1153     pat = XVECEXP (pat, 0, 0);
1154   if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
1155     return pat;
1156
1157   return NULL_RTX;
1158 }
1159
1160 /* Return true when insn is an unconditional direct jump,
1161    possibly bundled inside a PARALLEL.  */
1162
1163 int
1164 any_uncondjump_p (insn)
1165      rtx insn;
1166 {
1167   rtx x = pc_set (insn);
1168   if (!x)
1169     return 0;
1170   if (GET_CODE (SET_SRC (x)) != LABEL_REF)
1171     return 0;
1172   return 1;
1173 }
1174
1175 /* Return true when insn is a conditional jump.  This function works for
1176    instructions containing PC sets in PARALLELs.  The instruction may have
1177    various other effects so before removing the jump you must verify
1178    onlyjump_p.
1179
1180    Note that unlike condjump_p it returns false for unconditional jumps.  */
1181
1182 int
1183 any_condjump_p (insn)
1184      rtx insn;
1185 {
1186   rtx x = pc_set (insn);
1187   enum rtx_code a, b;
1188
1189   if (!x)
1190     return 0;
1191   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
1192     return 0;
1193
1194   a = GET_CODE (XEXP (SET_SRC (x), 1));
1195   b = GET_CODE (XEXP (SET_SRC (x), 2));
1196
1197   return ((b == PC && (a == LABEL_REF || a == RETURN))
1198           || (a == PC && (b == LABEL_REF || b == RETURN)));
1199 }
1200
1201 /* Return the label of a conditional jump.  */
1202
1203 rtx
1204 condjump_label (insn)
1205      rtx insn;
1206 {
1207   rtx x = pc_set (insn);
1208
1209   if (!x)
1210     return NULL_RTX;
1211   x = SET_SRC (x);
1212   if (GET_CODE (x) == LABEL_REF)
1213     return x;
1214   if (GET_CODE (x) != IF_THEN_ELSE)
1215     return NULL_RTX;
1216   if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
1217     return XEXP (x, 1);
1218   if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
1219     return XEXP (x, 2);
1220   return NULL_RTX;
1221 }
1222
1223 /* Return true if INSN is a (possibly conditional) return insn.  */
1224
1225 static int
1226 returnjump_p_1 (loc, data)
1227      rtx *loc;
1228      void *data ATTRIBUTE_UNUSED;
1229 {
1230   rtx x = *loc;
1231   return x && GET_CODE (x) == RETURN;
1232 }
1233
1234 int
1235 returnjump_p (insn)
1236      rtx insn;
1237 {
1238   if (GET_CODE (insn) != JUMP_INSN)
1239     return 0;
1240   return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
1241 }
1242
1243 /* Return true if INSN is a jump that only transfers control and
1244    nothing more.  */
1245
1246 int
1247 onlyjump_p (insn)
1248      rtx insn;
1249 {
1250   rtx set;
1251
1252   if (GET_CODE (insn) != JUMP_INSN)
1253     return 0;
1254
1255   set = single_set (insn);
1256   if (set == NULL)
1257     return 0;
1258   if (GET_CODE (SET_DEST (set)) != PC)
1259     return 0;
1260   if (side_effects_p (SET_SRC (set)))
1261     return 0;
1262
1263   return 1;
1264 }
1265
1266 #ifdef HAVE_cc0
1267
1268 /* Return non-zero if X is an RTX that only sets the condition codes
1269    and has no side effects.  */
1270
1271 int
1272 only_sets_cc0_p (x)
1273      rtx x;
1274 {
1275
1276   if (! x)
1277     return 0;
1278
1279   if (INSN_P (x))
1280     x = PATTERN (x);
1281
1282   return sets_cc0_p (x) == 1 && ! side_effects_p (x);
1283 }
1284
1285 /* Return 1 if X is an RTX that does nothing but set the condition codes
1286    and CLOBBER or USE registers.
1287    Return -1 if X does explicitly set the condition codes,
1288    but also does other things.  */
1289
1290 int
1291 sets_cc0_p (x)
1292      rtx x;
1293 {
1294
1295   if (! x)
1296     return 0;
1297
1298   if (INSN_P (x))
1299     x = PATTERN (x);
1300
1301   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
1302     return 1;
1303   if (GET_CODE (x) == PARALLEL)
1304     {
1305       int i;
1306       int sets_cc0 = 0;
1307       int other_things = 0;
1308       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1309         {
1310           if (GET_CODE (XVECEXP (x, 0, i)) == SET
1311               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
1312             sets_cc0 = 1;
1313           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
1314             other_things = 1;
1315         }
1316       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
1317     }
1318   return 0;
1319 }
1320 #endif
1321 \f
1322 /* Follow any unconditional jump at LABEL;
1323    return the ultimate label reached by any such chain of jumps.
1324    If LABEL is not followed by a jump, return LABEL.
1325    If the chain loops or we can't find end, return LABEL,
1326    since that tells caller to avoid changing the insn.
1327
1328    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
1329    a USE or CLOBBER.  */
1330
1331 rtx
1332 follow_jumps (label)
1333      rtx label;
1334 {
1335   register rtx insn;
1336   register rtx next;
1337   register rtx value = label;
1338   register int depth;
1339
1340   for (depth = 0;
1341        (depth < 10
1342         && (insn = next_active_insn (value)) != 0
1343         && GET_CODE (insn) == JUMP_INSN
1344         && ((JUMP_LABEL (insn) != 0 && any_uncondjump_p (insn)
1345              && onlyjump_p (insn))
1346             || GET_CODE (PATTERN (insn)) == RETURN)
1347         && (next = NEXT_INSN (insn))
1348         && GET_CODE (next) == BARRIER);
1349        depth++)
1350     {
1351       /* Don't chain through the insn that jumps into a loop
1352          from outside the loop,
1353          since that would create multiple loop entry jumps
1354          and prevent loop optimization.  */
1355       rtx tem;
1356       if (!reload_completed)
1357         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
1358           if (GET_CODE (tem) == NOTE
1359               && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
1360                   /* ??? Optional.  Disables some optimizations, but makes
1361                      gcov output more accurate with -O.  */
1362                   || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
1363             return value;
1364
1365       /* If we have found a cycle, make the insn jump to itself.  */
1366       if (JUMP_LABEL (insn) == label)
1367         return label;
1368
1369       tem = next_active_insn (JUMP_LABEL (insn));
1370       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
1371                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
1372         break;
1373
1374       value = JUMP_LABEL (insn);
1375     }
1376   if (depth == 10)
1377     return label;
1378   return value;
1379 }
1380
1381 \f
1382 /* Find all CODE_LABELs referred to in X, and increment their use counts.
1383    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
1384    in INSN, then store one of them in JUMP_LABEL (INSN).
1385    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
1386    referenced in INSN, add a REG_LABEL note containing that label to INSN.
1387    Also, when there are consecutive labels, canonicalize on the last of them.
1388
1389    Note that two labels separated by a loop-beginning note
1390    must be kept distinct if we have not yet done loop-optimization,
1391    because the gap between them is where loop-optimize
1392    will want to move invariant code to.  CROSS_JUMP tells us
1393    that loop-optimization is done with.  */
1394
1395 void
1396 mark_jump_label (x, insn, in_mem)
1397      register rtx x;
1398      rtx insn;
1399      int in_mem;
1400 {
1401   register RTX_CODE code = GET_CODE (x);
1402   register int i;
1403   register const char *fmt;
1404
1405   switch (code)
1406     {
1407     case PC:
1408     case CC0:
1409     case REG:
1410     case SUBREG:
1411     case CONST_INT:
1412     case CONST_DOUBLE:
1413     case CLOBBER:
1414     case CALL:
1415       return;
1416
1417     case MEM:
1418       in_mem = 1;
1419       break;
1420
1421     case SYMBOL_REF:
1422       if (!in_mem)
1423         return;
1424
1425       /* If this is a constant-pool reference, see if it is a label.  */
1426       if (CONSTANT_POOL_ADDRESS_P (x))
1427         mark_jump_label (get_pool_constant (x), insn, in_mem);
1428       break;
1429
1430     case LABEL_REF:
1431       {
1432         rtx label = XEXP (x, 0);
1433
1434         /* Ignore remaining references to unreachable labels that
1435            have been deleted.  */
1436         if (GET_CODE (label) == NOTE
1437             && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
1438           break;
1439
1440         if (GET_CODE (label) != CODE_LABEL)
1441           abort ();
1442
1443         /* Ignore references to labels of containing functions.  */
1444         if (LABEL_REF_NONLOCAL_P (x))
1445           break;
1446
1447         XEXP (x, 0) = label;
1448         if (! insn || ! INSN_DELETED_P (insn))
1449           ++LABEL_NUSES (label);
1450
1451         if (insn)
1452           {
1453             if (GET_CODE (insn) == JUMP_INSN)
1454               JUMP_LABEL (insn) = label;
1455             else
1456               {
1457                 /* Add a REG_LABEL note for LABEL unless there already
1458                    is one.  All uses of a label, except for labels
1459                    that are the targets of jumps, must have a
1460                    REG_LABEL note.  */
1461                 if (! find_reg_note (insn, REG_LABEL, label))
1462                   REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
1463                                                         REG_NOTES (insn));
1464               }
1465           }
1466         return;
1467       }
1468
1469   /* Do walk the labels in a vector, but not the first operand of an
1470      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
1471     case ADDR_VEC:
1472     case ADDR_DIFF_VEC:
1473       if (! INSN_DELETED_P (insn))
1474         {
1475           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1476
1477           for (i = 0; i < XVECLEN (x, eltnum); i++)
1478             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, in_mem);
1479         }
1480       return;
1481
1482     default:
1483       break;
1484     }
1485
1486   fmt = GET_RTX_FORMAT (code);
1487   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1488     {
1489       if (fmt[i] == 'e')
1490         mark_jump_label (XEXP (x, i), insn, in_mem);
1491       else if (fmt[i] == 'E')
1492         {
1493           register int j;
1494           for (j = 0; j < XVECLEN (x, i); j++)
1495             mark_jump_label (XVECEXP (x, i, j), insn, in_mem);
1496         }
1497     }
1498 }
1499
1500 /* If all INSN does is set the pc, delete it,
1501    and delete the insn that set the condition codes for it
1502    if that's what the previous thing was.  */
1503
1504 void
1505 delete_jump (insn)
1506      rtx insn;
1507 {
1508   register rtx set = single_set (insn);
1509
1510   if (set && GET_CODE (SET_DEST (set)) == PC)
1511     delete_computation (insn);
1512 }
1513
1514 /* Verify INSN is a BARRIER and delete it.  */
1515
1516 void
1517 delete_barrier (insn)
1518      rtx insn;
1519 {
1520   if (GET_CODE (insn) != BARRIER)
1521     abort ();
1522
1523   delete_insn (insn);
1524 }
1525
1526 /* Recursively delete prior insns that compute the value (used only by INSN
1527    which the caller is deleting) stored in the register mentioned by NOTE
1528    which is a REG_DEAD note associated with INSN.  */
1529
1530 static void
1531 delete_prior_computation (note, insn)
1532      rtx note;
1533      rtx insn;
1534 {
1535   rtx our_prev;
1536   rtx reg = XEXP (note, 0);
1537
1538   for (our_prev = prev_nonnote_insn (insn);
1539        our_prev && (GET_CODE (our_prev) == INSN
1540                     || GET_CODE (our_prev) == CALL_INSN);
1541        our_prev = prev_nonnote_insn (our_prev))
1542     {
1543       rtx pat = PATTERN (our_prev);
1544
1545       /* If we reach a CALL which is not calling a const function
1546          or the callee pops the arguments, then give up.  */
1547       if (GET_CODE (our_prev) == CALL_INSN
1548           && (! CONST_OR_PURE_CALL_P (our_prev)
1549               || GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
1550         break;
1551
1552       /* If we reach a SEQUENCE, it is too complex to try to
1553          do anything with it, so give up.  */
1554       if (GET_CODE (pat) == SEQUENCE)
1555         break;
1556
1557       if (GET_CODE (pat) == USE
1558           && GET_CODE (XEXP (pat, 0)) == INSN)
1559         /* reorg creates USEs that look like this.  We leave them
1560            alone because reorg needs them for its own purposes.  */
1561         break;
1562
1563       if (reg_set_p (reg, pat))
1564         {
1565           if (side_effects_p (pat) && GET_CODE (our_prev) != CALL_INSN)
1566             break;
1567
1568           if (GET_CODE (pat) == PARALLEL)
1569             {
1570               /* If we find a SET of something else, we can't
1571                  delete the insn.  */
1572
1573               int i;
1574
1575               for (i = 0; i < XVECLEN (pat, 0); i++)
1576                 {
1577                   rtx part = XVECEXP (pat, 0, i);
1578
1579                   if (GET_CODE (part) == SET
1580                       && SET_DEST (part) != reg)
1581                     break;
1582                 }
1583
1584               if (i == XVECLEN (pat, 0))
1585                 delete_computation (our_prev);
1586             }
1587           else if (GET_CODE (pat) == SET
1588                    && GET_CODE (SET_DEST (pat)) == REG)
1589             {
1590               int dest_regno = REGNO (SET_DEST (pat));
1591               int dest_endregno
1592                 = (dest_regno
1593                    + (dest_regno < FIRST_PSEUDO_REGISTER
1594                       ? HARD_REGNO_NREGS (dest_regno,
1595                                           GET_MODE (SET_DEST (pat))) : 1));
1596               int regno = REGNO (reg);
1597               int endregno
1598                 = (regno
1599                    + (regno < FIRST_PSEUDO_REGISTER
1600                       ? HARD_REGNO_NREGS (regno, GET_MODE (reg)) : 1));
1601
1602               if (dest_regno >= regno
1603                   && dest_endregno <= endregno)
1604                 delete_computation (our_prev);
1605
1606               /* We may have a multi-word hard register and some, but not
1607                  all, of the words of the register are needed in subsequent
1608                  insns.  Write REG_UNUSED notes for those parts that were not
1609                  needed.  */
1610               else if (dest_regno <= regno
1611                        && dest_endregno >= endregno)
1612                 {
1613                   int i;
1614
1615                   REG_NOTES (our_prev)
1616                     = gen_rtx_EXPR_LIST (REG_UNUSED, reg,
1617                                          REG_NOTES (our_prev));
1618
1619                   for (i = dest_regno; i < dest_endregno; i++)
1620                     if (! find_regno_note (our_prev, REG_UNUSED, i))
1621                       break;
1622
1623                   if (i == dest_endregno)
1624                     delete_computation (our_prev);
1625                 }
1626             }
1627
1628           break;
1629         }
1630
1631       /* If PAT references the register that dies here, it is an
1632          additional use.  Hence any prior SET isn't dead.  However, this
1633          insn becomes the new place for the REG_DEAD note.  */
1634       if (reg_overlap_mentioned_p (reg, pat))
1635         {
1636           XEXP (note, 1) = REG_NOTES (our_prev);
1637           REG_NOTES (our_prev) = note;
1638           break;
1639         }
1640     }
1641 }
1642
1643 /* Delete INSN and recursively delete insns that compute values used only
1644    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
1645    If we are running before flow.c, we need do nothing since flow.c will
1646    delete dead code.  We also can't know if the registers being used are
1647    dead or not at this point.
1648
1649    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
1650    nothing other than set a register that dies in this insn, we can delete
1651    that insn as well.
1652
1653    On machines with CC0, if CC0 is used in this insn, we may be able to
1654    delete the insn that set it.  */
1655
1656 static void
1657 delete_computation (insn)
1658      rtx insn;
1659 {
1660   rtx note, next;
1661
1662 #ifdef HAVE_cc0
1663   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
1664     {
1665       rtx prev = prev_nonnote_insn (insn);
1666       /* We assume that at this stage
1667          CC's are always set explicitly
1668          and always immediately before the jump that
1669          will use them.  So if the previous insn
1670          exists to set the CC's, delete it
1671          (unless it performs auto-increments, etc.).  */
1672       if (prev && GET_CODE (prev) == INSN
1673           && sets_cc0_p (PATTERN (prev)))
1674         {
1675           if (sets_cc0_p (PATTERN (prev)) > 0
1676               && ! side_effects_p (PATTERN (prev)))
1677             delete_computation (prev);
1678           else
1679             /* Otherwise, show that cc0 won't be used.  */
1680             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
1681                                                   cc0_rtx, REG_NOTES (prev));
1682         }
1683     }
1684 #endif
1685
1686   for (note = REG_NOTES (insn); note; note = next)
1687     {
1688       next = XEXP (note, 1);
1689
1690       if (REG_NOTE_KIND (note) != REG_DEAD
1691           /* Verify that the REG_NOTE is legitimate.  */
1692           || GET_CODE (XEXP (note, 0)) != REG)
1693         continue;
1694
1695       delete_prior_computation (note, insn);
1696     }
1697
1698   delete_insn (insn);
1699 }
1700 \f
1701 /* Delete insn INSN from the chain of insns and update label ref counts.
1702    May delete some following insns as a consequence; may even delete
1703    a label elsewhere and insns that follow it.
1704
1705    Returns the first insn after INSN that was not deleted.  */
1706
1707 rtx
1708 delete_insn (insn)
1709      register rtx insn;
1710 {
1711   register rtx next = NEXT_INSN (insn);
1712   register rtx prev = PREV_INSN (insn);
1713   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
1714   register int dont_really_delete = 0;
1715   rtx note;
1716
1717   while (next && INSN_DELETED_P (next))
1718     next = NEXT_INSN (next);
1719
1720   /* This insn is already deleted => return first following nondeleted.  */
1721   if (INSN_DELETED_P (insn))
1722     return next;
1723
1724   if (was_code_label)
1725     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
1726
1727   /* Don't delete user-declared labels.  When optimizing, convert them
1728      to special NOTEs instead.  When not optimizing, leave them alone.  */
1729   if (was_code_label && LABEL_NAME (insn) != 0)
1730     {
1731       if (optimize)
1732         {
1733           const char *name = LABEL_NAME (insn);
1734           PUT_CODE (insn, NOTE);
1735           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
1736           NOTE_SOURCE_FILE (insn) = name;
1737         }
1738
1739       dont_really_delete = 1;
1740     }
1741   else
1742     /* Mark this insn as deleted.  */
1743     INSN_DELETED_P (insn) = 1;
1744
1745   /* If instruction is followed by a barrier,
1746      delete the barrier too.  */
1747
1748   if (next != 0 && GET_CODE (next) == BARRIER)
1749     {
1750       INSN_DELETED_P (next) = 1;
1751       next = NEXT_INSN (next);
1752     }
1753
1754   /* Patch out INSN (and the barrier if any) */
1755
1756   if (! dont_really_delete)
1757     {
1758       if (prev)
1759         {
1760           NEXT_INSN (prev) = next;
1761           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
1762             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
1763                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
1764         }
1765
1766       if (next)
1767         {
1768           PREV_INSN (next) = prev;
1769           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
1770             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
1771         }
1772
1773       if (prev && NEXT_INSN (prev) == 0)
1774         set_last_insn (prev);
1775     }
1776
1777   /* If deleting a jump, decrement the count of the label,
1778      and delete the label if it is now unused.  */
1779
1780   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
1781     {
1782       rtx lab = JUMP_LABEL (insn), lab_next;
1783
1784       if (--LABEL_NUSES (lab) == 0)
1785         {
1786           /* This can delete NEXT or PREV,
1787              either directly if NEXT is JUMP_LABEL (INSN),
1788              or indirectly through more levels of jumps.  */
1789           delete_insn (lab);
1790
1791           /* I feel a little doubtful about this loop,
1792              but I see no clean and sure alternative way
1793              to find the first insn after INSN that is not now deleted.
1794              I hope this works.  */
1795           while (next && INSN_DELETED_P (next))
1796             next = NEXT_INSN (next);
1797           return next;
1798         }
1799       else if ((lab_next = next_nonnote_insn (lab)) != NULL
1800                && GET_CODE (lab_next) == JUMP_INSN
1801                && (GET_CODE (PATTERN (lab_next)) == ADDR_VEC
1802                    || GET_CODE (PATTERN (lab_next)) == ADDR_DIFF_VEC))
1803         {
1804           /* If we're deleting the tablejump, delete the dispatch table.
1805              We may not be able to kill the label immediately preceeding
1806              just yet, as it might be referenced in code leading up to
1807              the tablejump.  */
1808           delete_insn (lab_next);
1809         }
1810     }
1811
1812   /* Likewise if we're deleting a dispatch table.  */
1813
1814   if (GET_CODE (insn) == JUMP_INSN
1815       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1816           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1817     {
1818       rtx pat = PATTERN (insn);
1819       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1820       int len = XVECLEN (pat, diff_vec_p);
1821
1822       for (i = 0; i < len; i++)
1823         if (--LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1824           delete_insn (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1825       while (next && INSN_DELETED_P (next))
1826         next = NEXT_INSN (next);
1827       return next;
1828     }
1829
1830   /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
1831   if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
1832     for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1833       if (REG_NOTE_KIND (note) == REG_LABEL
1834           /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
1835           && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
1836         if (--LABEL_NUSES (XEXP (note, 0)) == 0)
1837           delete_insn (XEXP (note, 0));
1838
1839   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
1840     prev = PREV_INSN (prev);
1841
1842   /* If INSN was a label and a dispatch table follows it,
1843      delete the dispatch table.  The tablejump must have gone already.
1844      It isn't useful to fall through into a table.  */
1845
1846   if (was_code_label
1847       && NEXT_INSN (insn) != 0
1848       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
1849       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1850           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1851     next = delete_insn (NEXT_INSN (insn));
1852
1853   /* If INSN was a label, delete insns following it if now unreachable.  */
1854
1855   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
1856     {
1857       register RTX_CODE code;
1858       while (next != 0
1859              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
1860                  || code == NOTE || code == BARRIER
1861                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
1862         {
1863           if (code == NOTE
1864               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
1865             next = NEXT_INSN (next);
1866           /* Keep going past other deleted labels to delete what follows.  */
1867           else if (code == CODE_LABEL && INSN_DELETED_P (next))
1868             next = NEXT_INSN (next);
1869           else
1870             /* Note: if this deletes a jump, it can cause more
1871                deletion of unreachable code, after a different label.
1872                As long as the value from this recursive call is correct,
1873                this invocation functions correctly.  */
1874             next = delete_insn (next);
1875         }
1876     }
1877
1878   return next;
1879 }
1880
1881 /* Advance from INSN till reaching something not deleted
1882    then return that.  May return INSN itself.  */
1883
1884 rtx
1885 next_nondeleted_insn (insn)
1886      rtx insn;
1887 {
1888   while (INSN_DELETED_P (insn))
1889     insn = NEXT_INSN (insn);
1890   return insn;
1891 }
1892 \f
1893 /* Delete a range of insns from FROM to TO, inclusive.
1894    This is for the sake of peephole optimization, so assume
1895    that whatever these insns do will still be done by a new
1896    peephole insn that will replace them.  */
1897
1898 void
1899 delete_for_peephole (from, to)
1900      register rtx from, to;
1901 {
1902   register rtx insn = from;
1903
1904   while (1)
1905     {
1906       register rtx next = NEXT_INSN (insn);
1907       register rtx prev = PREV_INSN (insn);
1908
1909       if (GET_CODE (insn) != NOTE)
1910         {
1911           INSN_DELETED_P (insn) = 1;
1912
1913           /* Patch this insn out of the chain.  */
1914           /* We don't do this all at once, because we
1915              must preserve all NOTEs.  */
1916           if (prev)
1917             NEXT_INSN (prev) = next;
1918
1919           if (next)
1920             PREV_INSN (next) = prev;
1921         }
1922
1923       if (insn == to)
1924         break;
1925       insn = next;
1926     }
1927
1928   /* Note that if TO is an unconditional jump
1929      we *do not* delete the BARRIER that follows,
1930      since the peephole that replaces this sequence
1931      is also an unconditional jump in that case.  */
1932 }
1933 \f
1934 /* We have determined that INSN is never reached, and are about to
1935    delete it.  Print a warning if the user asked for one.
1936
1937    To try to make this warning more useful, this should only be called
1938    once per basic block not reached, and it only warns when the basic
1939    block contains more than one line from the current function, and
1940    contains at least one operation.  CSE and inlining can duplicate insns,
1941    so it's possible to get spurious warnings from this.  */
1942
1943 void
1944 never_reached_warning (avoided_insn)
1945      rtx avoided_insn;
1946 {
1947   rtx insn;
1948   rtx a_line_note = NULL;
1949   int two_avoided_lines = 0;
1950   int contains_insn = 0;
1951
1952   if (! warn_notreached)
1953     return;
1954
1955   /* Scan forwards, looking at LINE_NUMBER notes, until
1956      we hit a LABEL or we run out of insns.  */
1957
1958   for (insn = avoided_insn; insn != NULL; insn = NEXT_INSN (insn))
1959     {
1960       if (GET_CODE (insn) == CODE_LABEL)
1961         break;
1962       else if (GET_CODE (insn) == NOTE          /* A line number note?  */
1963                && NOTE_LINE_NUMBER (insn) >= 0)
1964         {
1965           if (a_line_note == NULL)
1966             a_line_note = insn;
1967           else
1968             two_avoided_lines |= (NOTE_LINE_NUMBER (a_line_note)
1969                                   != NOTE_LINE_NUMBER (insn));
1970         }
1971       else if (INSN_P (insn))
1972         contains_insn = 1;
1973     }
1974   if (two_avoided_lines && contains_insn)
1975     warning_with_file_and_line (NOTE_SOURCE_FILE (a_line_note),
1976                                 NOTE_LINE_NUMBER (a_line_note),
1977                                 "will never be executed");
1978 }
1979 \f
1980 /* Throughout LOC, redirect OLABEL to NLABEL.  Treat null OLABEL or
1981    NLABEL as a return.  Accrue modifications into the change group.  */
1982
1983 static void
1984 redirect_exp_1 (loc, olabel, nlabel, insn)
1985      rtx *loc;
1986      rtx olabel, nlabel;
1987      rtx insn;
1988 {
1989   register rtx x = *loc;
1990   register RTX_CODE code = GET_CODE (x);
1991   register int i;
1992   register const char *fmt;
1993
1994   if (code == LABEL_REF)
1995     {
1996       if (XEXP (x, 0) == olabel)
1997         {
1998           rtx n;
1999           if (nlabel)
2000             n = gen_rtx_LABEL_REF (VOIDmode, nlabel);
2001           else
2002             n = gen_rtx_RETURN (VOIDmode);
2003
2004           validate_change (insn, loc, n, 1);
2005           return;
2006         }
2007     }
2008   else if (code == RETURN && olabel == 0)
2009     {
2010       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
2011       if (loc == &PATTERN (insn))
2012         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
2013       validate_change (insn, loc, x, 1);
2014       return;
2015     }
2016
2017   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
2018       && GET_CODE (SET_SRC (x)) == LABEL_REF
2019       && XEXP (SET_SRC (x), 0) == olabel)
2020     {
2021       validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
2022       return;
2023     }
2024
2025   fmt = GET_RTX_FORMAT (code);
2026   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2027     {
2028       if (fmt[i] == 'e')
2029         redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
2030       else if (fmt[i] == 'E')
2031         {
2032           register int j;
2033           for (j = 0; j < XVECLEN (x, i); j++)
2034             redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
2035         }
2036     }
2037 }
2038
2039 /* Similar, but apply the change group and report success or failure.  */
2040
2041 static int
2042 redirect_exp (olabel, nlabel, insn)
2043      rtx olabel, nlabel;
2044      rtx insn;
2045 {
2046   rtx *loc;
2047
2048   if (GET_CODE (PATTERN (insn)) == PARALLEL)
2049     loc = &XVECEXP (PATTERN (insn), 0, 0);
2050   else
2051     loc = &PATTERN (insn);
2052
2053   redirect_exp_1 (loc, olabel, nlabel, insn);
2054   if (num_validated_changes () == 0)
2055     return 0;
2056
2057   return apply_change_group ();
2058 }
2059
2060 /* Make JUMP go to NLABEL instead of where it jumps now.  Accrue
2061    the modifications into the change group.  Return false if we did
2062    not see how to do that.  */
2063
2064 int
2065 redirect_jump_1 (jump, nlabel)
2066      rtx jump, nlabel;
2067 {
2068   int ochanges = num_validated_changes ();
2069   rtx *loc;
2070
2071   if (GET_CODE (PATTERN (jump)) == PARALLEL)
2072     loc = &XVECEXP (PATTERN (jump), 0, 0);
2073   else
2074     loc = &PATTERN (jump);
2075
2076   redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
2077   return num_validated_changes () > ochanges;
2078 }
2079
2080 /* Make JUMP go to NLABEL instead of where it jumps now.  If the old
2081    jump target label is unused as a result, it and the code following
2082    it may be deleted.
2083
2084    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
2085    RETURN insn.
2086
2087    The return value will be 1 if the change was made, 0 if it wasn't
2088    (this can only occur for NLABEL == 0).  */
2089
2090 int
2091 redirect_jump (jump, nlabel, delete_unused)
2092      rtx jump, nlabel;
2093      int delete_unused;
2094 {
2095   register rtx olabel = JUMP_LABEL (jump);
2096
2097   if (nlabel == olabel)
2098     return 1;
2099
2100   if (! redirect_exp (olabel, nlabel, jump))
2101     return 0;
2102
2103   JUMP_LABEL (jump) = nlabel;
2104   if (nlabel)
2105     ++LABEL_NUSES (nlabel);
2106
2107   /* If we're eliding the jump over exception cleanups at the end of a
2108      function, move the function end note so that -Wreturn-type works.  */
2109   if (olabel && nlabel
2110       && NEXT_INSN (olabel)
2111       && GET_CODE (NEXT_INSN (olabel)) == NOTE
2112       && NOTE_LINE_NUMBER (NEXT_INSN (olabel)) == NOTE_INSN_FUNCTION_END)
2113     emit_note_after (NOTE_INSN_FUNCTION_END, nlabel);
2114
2115   if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused)
2116     delete_insn (olabel);
2117
2118   return 1;
2119 }
2120
2121 /* Invert the jump condition of rtx X contained in jump insn, INSN.
2122    Accrue the modifications into the change group.  */
2123
2124 static void
2125 invert_exp_1 (insn)
2126      rtx insn;
2127 {
2128   register RTX_CODE code;
2129   rtx x = pc_set (insn);
2130
2131   if (!x)
2132     abort ();
2133   x = SET_SRC (x);
2134
2135   code = GET_CODE (x);
2136
2137   if (code == IF_THEN_ELSE)
2138     {
2139       register rtx comp = XEXP (x, 0);
2140       register rtx tem;
2141       enum rtx_code reversed_code;
2142
2143       /* We can do this in two ways:  The preferable way, which can only
2144          be done if this is not an integer comparison, is to reverse
2145          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
2146          of the IF_THEN_ELSE.  If we can't do either, fail.  */
2147
2148       reversed_code = reversed_comparison_code (comp, insn);
2149
2150       if (reversed_code != UNKNOWN)
2151         {
2152           validate_change (insn, &XEXP (x, 0),
2153                            gen_rtx_fmt_ee (reversed_code,
2154                                            GET_MODE (comp), XEXP (comp, 0),
2155                                            XEXP (comp, 1)),
2156                            1);
2157           return;
2158         }
2159
2160       tem = XEXP (x, 1);
2161       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
2162       validate_change (insn, &XEXP (x, 2), tem, 1);
2163     }
2164   else
2165     abort ();
2166 }
2167
2168 /* Invert the jump condition of conditional jump insn, INSN.
2169
2170    Return 1 if we can do so, 0 if we cannot find a way to do so that
2171    matches a pattern.  */
2172
2173 static int
2174 invert_exp (insn)
2175      rtx insn;
2176 {
2177   invert_exp_1 (insn);
2178   if (num_validated_changes () == 0)
2179     return 0;
2180
2181   return apply_change_group ();
2182 }
2183
2184 /* Invert the condition of the jump JUMP, and make it jump to label
2185    NLABEL instead of where it jumps now.  Accrue changes into the
2186    change group.  Return false if we didn't see how to perform the
2187    inversion and redirection.  */
2188
2189 int
2190 invert_jump_1 (jump, nlabel)
2191      rtx jump, nlabel;
2192 {
2193   int ochanges;
2194
2195   ochanges = num_validated_changes ();
2196   invert_exp_1 (jump);
2197   if (num_validated_changes () == ochanges)
2198     return 0;
2199
2200   return redirect_jump_1 (jump, nlabel);
2201 }
2202
2203 /* Invert the condition of the jump JUMP, and make it jump to label
2204    NLABEL instead of where it jumps now.  Return true if successful.  */
2205
2206 int
2207 invert_jump (jump, nlabel, delete_unused)
2208      rtx jump, nlabel;
2209      int delete_unused;
2210 {
2211   /* We have to either invert the condition and change the label or
2212      do neither.  Either operation could fail.  We first try to invert
2213      the jump. If that succeeds, we try changing the label.  If that fails,
2214      we invert the jump back to what it was.  */
2215
2216   if (! invert_exp (jump))
2217     return 0;
2218
2219   if (redirect_jump (jump, nlabel, delete_unused))
2220     {
2221       invert_br_probabilities (jump);
2222
2223       return 1;
2224     }
2225
2226   if (! invert_exp (jump))
2227     /* This should just be putting it back the way it was.  */
2228     abort ();
2229
2230   return 0;
2231 }
2232
2233 \f
2234 /* Like rtx_equal_p except that it considers two REGs as equal
2235    if they renumber to the same value and considers two commutative
2236    operations to be the same if the order of the operands has been
2237    reversed.
2238
2239    ??? Addition is not commutative on the PA due to the weird implicit
2240    space register selection rules for memory addresses.  Therefore, we
2241    don't consider a + b == b + a.
2242
2243    We could/should make this test a little tighter.  Possibly only
2244    disabling it on the PA via some backend macro or only disabling this
2245    case when the PLUS is inside a MEM.  */
2246
2247 int
2248 rtx_renumbered_equal_p (x, y)
2249      rtx x, y;
2250 {
2251   register int i;
2252   register RTX_CODE code = GET_CODE (x);
2253   register const char *fmt;
2254
2255   if (x == y)
2256     return 1;
2257
2258   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
2259       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
2260                                   && GET_CODE (SUBREG_REG (y)) == REG)))
2261     {
2262       int reg_x = -1, reg_y = -1;
2263       int byte_x = 0, byte_y = 0;
2264
2265       if (GET_MODE (x) != GET_MODE (y))
2266         return 0;
2267
2268       /* If we haven't done any renumbering, don't
2269          make any assumptions.  */
2270       if (reg_renumber == 0)
2271         return rtx_equal_p (x, y);
2272
2273       if (code == SUBREG)
2274         {
2275           reg_x = REGNO (SUBREG_REG (x));
2276           byte_x = SUBREG_BYTE (x);
2277
2278           if (reg_renumber[reg_x] >= 0)
2279             {
2280               reg_x = subreg_regno_offset (reg_renumber[reg_x],
2281                                            GET_MODE (SUBREG_REG (x)),
2282                                            byte_x,
2283                                            GET_MODE (x));
2284               byte_x = 0;
2285             }
2286         }
2287       else
2288         {
2289           reg_x = REGNO (x);
2290           if (reg_renumber[reg_x] >= 0)
2291             reg_x = reg_renumber[reg_x];
2292         }
2293
2294       if (GET_CODE (y) == SUBREG)
2295         {
2296           reg_y = REGNO (SUBREG_REG (y));
2297           byte_y = SUBREG_BYTE (y);
2298
2299           if (reg_renumber[reg_y] >= 0)
2300             {
2301               reg_y = subreg_regno_offset (reg_renumber[reg_y],
2302                                            GET_MODE (SUBREG_REG (y)),
2303                                            byte_y,
2304                                            GET_MODE (y));
2305               byte_y = 0;
2306             }
2307         }
2308       else
2309         {
2310           reg_y = REGNO (y);
2311           if (reg_renumber[reg_y] >= 0)
2312             reg_y = reg_renumber[reg_y];
2313         }
2314
2315       return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
2316     }
2317
2318   /* Now we have disposed of all the cases
2319      in which different rtx codes can match.  */
2320   if (code != GET_CODE (y))
2321     return 0;
2322
2323   switch (code)
2324     {
2325     case PC:
2326     case CC0:
2327     case ADDR_VEC:
2328     case ADDR_DIFF_VEC:
2329       return 0;
2330
2331     case CONST_INT:
2332       return INTVAL (x) == INTVAL (y);
2333
2334     case LABEL_REF:
2335       /* We can't assume nonlocal labels have their following insns yet.  */
2336       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
2337         return XEXP (x, 0) == XEXP (y, 0);
2338
2339       /* Two label-refs are equivalent if they point at labels
2340          in the same position in the instruction stream.  */
2341       return (next_real_insn (XEXP (x, 0))
2342               == next_real_insn (XEXP (y, 0)));
2343
2344     case SYMBOL_REF:
2345       return XSTR (x, 0) == XSTR (y, 0);
2346
2347     case CODE_LABEL:
2348       /* If we didn't match EQ equality above, they aren't the same.  */
2349       return 0;
2350
2351     default:
2352       break;
2353     }
2354
2355   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
2356
2357   if (GET_MODE (x) != GET_MODE (y))
2358     return 0;
2359
2360   /* For commutative operations, the RTX match if the operand match in any
2361      order.  Also handle the simple binary and unary cases without a loop.
2362
2363      ??? Don't consider PLUS a commutative operator; see comments above.  */
2364   if ((code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
2365       && code != PLUS)
2366     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
2367              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
2368             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
2369                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
2370   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
2371     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
2372             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
2373   else if (GET_RTX_CLASS (code) == '1')
2374     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
2375
2376   /* Compare the elements.  If any pair of corresponding elements
2377      fail to match, return 0 for the whole things.  */
2378
2379   fmt = GET_RTX_FORMAT (code);
2380   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2381     {
2382       register int j;
2383       switch (fmt[i])
2384         {
2385         case 'w':
2386           if (XWINT (x, i) != XWINT (y, i))
2387             return 0;
2388           break;
2389
2390         case 'i':
2391           if (XINT (x, i) != XINT (y, i))
2392             return 0;
2393           break;
2394
2395         case 't':
2396           if (XTREE (x, i) != XTREE (y, i))
2397             return 0;
2398           break;
2399
2400         case 's':
2401           if (strcmp (XSTR (x, i), XSTR (y, i)))
2402             return 0;
2403           break;
2404
2405         case 'e':
2406           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
2407             return 0;
2408           break;
2409
2410         case 'u':
2411           if (XEXP (x, i) != XEXP (y, i))
2412             return 0;
2413           /* fall through.  */
2414         case '0':
2415           break;
2416
2417         case 'E':
2418           if (XVECLEN (x, i) != XVECLEN (y, i))
2419             return 0;
2420           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2421             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
2422               return 0;
2423           break;
2424
2425         default:
2426           abort ();
2427         }
2428     }
2429   return 1;
2430 }
2431 \f
2432 /* If X is a hard register or equivalent to one or a subregister of one,
2433    return the hard register number.  If X is a pseudo register that was not
2434    assigned a hard register, return the pseudo register number.  Otherwise,
2435    return -1.  Any rtx is valid for X.  */
2436
2437 int
2438 true_regnum (x)
2439      rtx x;
2440 {
2441   if (GET_CODE (x) == REG)
2442     {
2443       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
2444         return reg_renumber[REGNO (x)];
2445       return REGNO (x);
2446     }
2447   if (GET_CODE (x) == SUBREG)
2448     {
2449       int base = true_regnum (SUBREG_REG (x));
2450       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
2451         return base + subreg_regno_offset (REGNO (SUBREG_REG (x)),
2452                                            GET_MODE (SUBREG_REG (x)),
2453                                            SUBREG_BYTE (x), GET_MODE (x));
2454     }
2455   return -1;
2456 }
2457 \f
2458 /* Optimize code of the form:
2459
2460         for (x = a[i]; x; ...)
2461           ...
2462         for (x = a[i]; x; ...)
2463           ...
2464       foo:
2465
2466    Loop optimize will change the above code into
2467
2468         if (x = a[i])
2469           for (;;)
2470              { ...; if (! (x = ...)) break; }
2471         if (x = a[i])
2472           for (;;)
2473              { ...; if (! (x = ...)) break; }
2474       foo:
2475
2476    In general, if the first test fails, the program can branch
2477    directly to `foo' and skip the second try which is doomed to fail.
2478    We run this after loop optimization and before flow analysis.  */
2479
2480 /* When comparing the insn patterns, we track the fact that different
2481    pseudo-register numbers may have been used in each computation.
2482    The following array stores an equivalence -- same_regs[I] == J means
2483    that pseudo register I was used in the first set of tests in a context
2484    where J was used in the second set.  We also count the number of such
2485    pending equivalences.  If nonzero, the expressions really aren't the
2486    same.  */
2487
2488 static int *same_regs;
2489
2490 static int num_same_regs;
2491
2492 /* Track any registers modified between the target of the first jump and
2493    the second jump.  They never compare equal.  */
2494
2495 static char *modified_regs;
2496
2497 /* Record if memory was modified.  */
2498
2499 static int modified_mem;
2500
2501 /* Called via note_stores on each insn between the target of the first
2502    branch and the second branch.  It marks any changed registers.  */
2503
2504 static void
2505 mark_modified_reg (dest, x, data)
2506      rtx dest;
2507      rtx x;
2508      void *data ATTRIBUTE_UNUSED;
2509 {
2510   int regno;
2511   unsigned int i;
2512
2513   if (GET_CODE (dest) == SUBREG)
2514     dest = SUBREG_REG (dest);
2515
2516   if (GET_CODE (dest) == MEM)
2517     modified_mem = 1;
2518
2519   if (GET_CODE (dest) != REG)
2520     return;
2521
2522   regno = REGNO (dest);
2523   if (regno >= FIRST_PSEUDO_REGISTER)
2524     modified_regs[regno] = 1;
2525   /* Don't consider a hard condition code register as modified,
2526      if it is only being set.  thread_jumps will check if it is set
2527      to the same value.  */
2528   else if (GET_MODE_CLASS (GET_MODE (dest)) != MODE_CC
2529            || GET_CODE (x) != SET
2530            || ! rtx_equal_p (dest, SET_DEST (x))
2531            || HARD_REGNO_NREGS (regno, GET_MODE (dest)) != 1)
2532     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
2533       modified_regs[regno + i] = 1;
2534 }
2535
2536 /* F is the first insn in the chain of insns.  */
2537
2538 void
2539 thread_jumps (f, max_reg, flag_before_loop)
2540      rtx f;
2541      int max_reg;
2542      int flag_before_loop;
2543 {
2544   /* Basic algorithm is to find a conditional branch,
2545      the label it may branch to, and the branch after
2546      that label.  If the two branches test the same condition,
2547      walk back from both branch paths until the insn patterns
2548      differ, or code labels are hit.  If we make it back to
2549      the target of the first branch, then we know that the first branch
2550      will either always succeed or always fail depending on the relative
2551      senses of the two branches.  So adjust the first branch accordingly
2552      in this case.  */
2553
2554   rtx label, b1, b2, t1, t2;
2555   enum rtx_code code1, code2;
2556   rtx b1op0, b1op1, b2op0, b2op1;
2557   int changed = 1;
2558   int i;
2559   int *all_reset;
2560   enum rtx_code reversed_code1, reversed_code2;
2561
2562   /* Allocate register tables and quick-reset table.  */
2563   modified_regs = (char *) xmalloc (max_reg * sizeof (char));
2564   same_regs = (int *) xmalloc (max_reg * sizeof (int));
2565   all_reset = (int *) xmalloc (max_reg * sizeof (int));
2566   for (i = 0; i < max_reg; i++)
2567     all_reset[i] = -1;
2568
2569   while (changed)
2570     {
2571       changed = 0;
2572
2573       for (b1 = f; b1; b1 = NEXT_INSN (b1))
2574         {
2575           rtx set;
2576           rtx set2;
2577
2578           /* Get to a candidate branch insn.  */
2579           if (GET_CODE (b1) != JUMP_INSN
2580               || ! any_condjump_p (b1) || JUMP_LABEL (b1) == 0)
2581             continue;
2582
2583           memset (modified_regs, 0, max_reg * sizeof (char));
2584           modified_mem = 0;
2585
2586           memcpy (same_regs, all_reset, max_reg * sizeof (int));
2587           num_same_regs = 0;
2588
2589           label = JUMP_LABEL (b1);
2590
2591           /* Look for a branch after the target.  Record any registers and
2592              memory modified between the target and the branch.  Stop when we
2593              get to a label since we can't know what was changed there.  */
2594           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
2595             {
2596               if (GET_CODE (b2) == CODE_LABEL)
2597                 break;
2598
2599               else if (GET_CODE (b2) == JUMP_INSN)
2600                 {
2601                   /* If this is an unconditional jump and is the only use of
2602                      its target label, we can follow it.  */
2603                   if (any_uncondjump_p (b2)
2604                       && onlyjump_p (b2)
2605                       && JUMP_LABEL (b2) != 0
2606                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
2607                     {
2608                       b2 = JUMP_LABEL (b2);
2609                       continue;
2610                     }
2611                   else
2612                     break;
2613                 }
2614
2615               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
2616                 continue;
2617
2618               if (GET_CODE (b2) == CALL_INSN)
2619                 {
2620                   modified_mem = 1;
2621                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2622                     if (call_used_regs[i] && ! fixed_regs[i]
2623                         && i != STACK_POINTER_REGNUM
2624                         && i != FRAME_POINTER_REGNUM
2625                         && i != HARD_FRAME_POINTER_REGNUM
2626                         && i != ARG_POINTER_REGNUM)
2627                       modified_regs[i] = 1;
2628                 }
2629
2630               note_stores (PATTERN (b2), mark_modified_reg, NULL);
2631             }
2632
2633           /* Check the next candidate branch insn from the label
2634              of the first.  */
2635           if (b2 == 0
2636               || GET_CODE (b2) != JUMP_INSN
2637               || b2 == b1
2638               || !any_condjump_p (b2)
2639               || !onlyjump_p (b2))
2640             continue;
2641           set = pc_set (b1);
2642           set2 = pc_set (b2);
2643
2644           /* Get the comparison codes and operands, reversing the
2645              codes if appropriate.  If we don't have comparison codes,
2646              we can't do anything.  */
2647           b1op0 = XEXP (XEXP (SET_SRC (set), 0), 0);
2648           b1op1 = XEXP (XEXP (SET_SRC (set), 0), 1);
2649           code1 = GET_CODE (XEXP (SET_SRC (set), 0));
2650           reversed_code1 = code1;
2651           if (XEXP (SET_SRC (set), 1) == pc_rtx)
2652             code1 = reversed_comparison_code (XEXP (SET_SRC (set), 0), b1);
2653           else
2654             reversed_code1 = reversed_comparison_code (XEXP (SET_SRC (set), 0), b1);
2655
2656           b2op0 = XEXP (XEXP (SET_SRC (set2), 0), 0);
2657           b2op1 = XEXP (XEXP (SET_SRC (set2), 0), 1);
2658           code2 = GET_CODE (XEXP (SET_SRC (set2), 0));
2659           reversed_code2 = code2;
2660           if (XEXP (SET_SRC (set2), 1) == pc_rtx)
2661             code2 = reversed_comparison_code (XEXP (SET_SRC (set2), 0), b2);
2662           else
2663             reversed_code2 = reversed_comparison_code (XEXP (SET_SRC (set2), 0), b2);
2664
2665           /* If they test the same things and knowing that B1 branches
2666              tells us whether or not B2 branches, check if we
2667              can thread the branch.  */
2668           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
2669               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
2670               && (comparison_dominates_p (code1, code2)
2671                   || comparison_dominates_p (code1, reversed_code2)))
2672
2673             {
2674               t1 = prev_nonnote_insn (b1);
2675               t2 = prev_nonnote_insn (b2);
2676
2677               while (t1 != 0 && t2 != 0)
2678                 {
2679                   if (t2 == label)
2680                     {
2681                       /* We have reached the target of the first branch.
2682                          If there are no pending register equivalents,
2683                          we know that this branch will either always
2684                          succeed (if the senses of the two branches are
2685                          the same) or always fail (if not).  */
2686                       rtx new_label;
2687
2688                       if (num_same_regs != 0)
2689                         break;
2690
2691                       if (comparison_dominates_p (code1, code2))
2692                         new_label = JUMP_LABEL (b2);
2693                       else
2694                         new_label = get_label_after (b2);
2695
2696                       if (JUMP_LABEL (b1) != new_label)
2697                         {
2698                           rtx prev = PREV_INSN (new_label);
2699
2700                           if (flag_before_loop
2701                               && GET_CODE (prev) == NOTE
2702                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
2703                             {
2704                               /* Don't thread to the loop label.  If a loop
2705                                  label is reused, loop optimization will
2706                                  be disabled for that loop.  */
2707                               new_label = gen_label_rtx ();
2708                               emit_label_after (new_label, PREV_INSN (prev));
2709                             }
2710                           changed |= redirect_jump (b1, new_label, 1);
2711                         }
2712                       break;
2713                     }
2714
2715                   /* If either of these is not a normal insn (it might be
2716                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
2717                      have already been skipped above.)  Similarly, fail
2718                      if the insns are different.  */
2719                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
2720                       || recog_memoized (t1) != recog_memoized (t2)
2721                       || ! rtx_equal_for_thread_p (PATTERN (t1),
2722                                                    PATTERN (t2), t2))
2723                     break;
2724
2725                   t1 = prev_nonnote_insn (t1);
2726                   t2 = prev_nonnote_insn (t2);
2727                 }
2728             }
2729         }
2730     }
2731
2732   /* Clean up.  */
2733   free (modified_regs);
2734   free (same_regs);
2735   free (all_reset);
2736 }
2737 \f
2738 /* This is like RTX_EQUAL_P except that it knows about our handling of
2739    possibly equivalent registers and knows to consider volatile and
2740    modified objects as not equal.
2741
2742    YINSN is the insn containing Y.  */
2743
2744 int
2745 rtx_equal_for_thread_p (x, y, yinsn)
2746      rtx x, y;
2747      rtx yinsn;
2748 {
2749   register int i;
2750   register int j;
2751   register enum rtx_code code;
2752   register const char *fmt;
2753
2754   code = GET_CODE (x);
2755   /* Rtx's of different codes cannot be equal.  */
2756   if (code != GET_CODE (y))
2757     return 0;
2758
2759   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
2760      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
2761
2762   if (GET_MODE (x) != GET_MODE (y))
2763     return 0;
2764
2765   /* For floating-point, consider everything unequal.  This is a bit
2766      pessimistic, but this pass would only rarely do anything for FP
2767      anyway.  */
2768   if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
2769       && FLOAT_MODE_P (GET_MODE (x)) && ! flag_unsafe_math_optimizations)
2770     return 0;
2771
2772   /* For commutative operations, the RTX match if the operand match in any
2773      order.  Also handle the simple binary and unary cases without a loop.  */
2774   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
2775     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
2776              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
2777             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
2778                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
2779   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
2780     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
2781             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
2782   else if (GET_RTX_CLASS (code) == '1')
2783     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
2784
2785   /* Handle special-cases first.  */
2786   switch (code)
2787     {
2788     case REG:
2789       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
2790         return 1;
2791
2792       /* If neither is user variable or hard register, check for possible
2793          equivalence.  */
2794       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
2795           || REGNO (x) < FIRST_PSEUDO_REGISTER
2796           || REGNO (y) < FIRST_PSEUDO_REGISTER)
2797         return 0;
2798
2799       if (same_regs[REGNO (x)] == -1)
2800         {
2801           same_regs[REGNO (x)] = REGNO (y);
2802           num_same_regs++;
2803
2804           /* If this is the first time we are seeing a register on the `Y'
2805              side, see if it is the last use.  If not, we can't thread the
2806              jump, so mark it as not equivalent.  */
2807           if (REGNO_LAST_UID (REGNO (y)) != INSN_UID (yinsn))
2808             return 0;
2809
2810           return 1;
2811         }
2812       else
2813         return (same_regs[REGNO (x)] == (int) REGNO (y));
2814
2815       break;
2816
2817     case MEM:
2818       /* If memory modified or either volatile, not equivalent.
2819          Else, check address.  */
2820       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2821         return 0;
2822
2823       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
2824
2825     case ASM_INPUT:
2826       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
2827         return 0;
2828
2829       break;
2830
2831     case SET:
2832       /* Cancel a pending `same_regs' if setting equivalenced registers.
2833          Then process source.  */
2834       if (GET_CODE (SET_DEST (x)) == REG
2835           && GET_CODE (SET_DEST (y)) == REG)
2836         {
2837           if (same_regs[REGNO (SET_DEST (x))] == (int) REGNO (SET_DEST (y)))
2838             {
2839               same_regs[REGNO (SET_DEST (x))] = -1;
2840               num_same_regs--;
2841             }
2842           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
2843             return 0;
2844         }
2845       else
2846         {
2847           if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
2848             return 0;
2849         }
2850
2851       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
2852
2853     case LABEL_REF:
2854       return XEXP (x, 0) == XEXP (y, 0);
2855
2856     case SYMBOL_REF:
2857       return XSTR (x, 0) == XSTR (y, 0);
2858
2859     default:
2860       break;
2861     }
2862
2863   if (x == y)
2864     return 1;
2865
2866   fmt = GET_RTX_FORMAT (code);
2867   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2868     {
2869       switch (fmt[i])
2870         {
2871         case 'w':
2872           if (XWINT (x, i) != XWINT (y, i))
2873             return 0;
2874           break;
2875
2876         case 'n':
2877         case 'i':
2878           if (XINT (x, i) != XINT (y, i))
2879             return 0;
2880           break;
2881
2882         case 'V':
2883         case 'E':
2884           /* Two vectors must have the same length.  */
2885           if (XVECLEN (x, i) != XVECLEN (y, i))
2886             return 0;
2887
2888           /* And the corresponding elements must match.  */
2889           for (j = 0; j < XVECLEN (x, i); j++)
2890             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
2891                                         XVECEXP (y, i, j), yinsn) == 0)
2892               return 0;
2893           break;
2894
2895         case 'e':
2896           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
2897             return 0;
2898           break;
2899
2900         case 'S':
2901         case 's':
2902           if (strcmp (XSTR (x, i), XSTR (y, i)))
2903             return 0;
2904           break;
2905
2906         case 'u':
2907           /* These are just backpointers, so they don't matter.  */
2908           break;
2909
2910         case '0':
2911         case 't':
2912           break;
2913
2914           /* It is believed that rtx's at this level will never
2915              contain anything but integers and other rtx's,
2916              except for within LABEL_REFs and SYMBOL_REFs.  */
2917         default:
2918           abort ();
2919         }
2920     }
2921   return 1;
2922 }