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