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