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         rtx olabel = label;
2003         rtx next;
2004
2005         /* Ignore remaining references to unreachable labels that
2006            have been deleted.  */
2007         if (GET_CODE (label) == NOTE
2008             && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
2009           break;
2010
2011         if (GET_CODE (label) != CODE_LABEL)
2012           abort ();
2013
2014         /* Ignore references to labels of containing functions.  */
2015         if (LABEL_REF_NONLOCAL_P (x))
2016           break;
2017
2018         /* If there are other labels following this one,
2019            replace it with the last of the consecutive labels.  */
2020         for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
2021           {
2022             if (GET_CODE (next) == CODE_LABEL)
2023               label = next;
2024             else if (GET_CODE (next) != NOTE)
2025               break;
2026             else if ((NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
2027                       || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END
2028                       /* ??? Optional.  Disables some optimizations, but
2029                          makes gcov output more accurate with -O.  */
2030                       || (flag_test_coverage
2031                           && NOTE_LINE_NUMBER (next) > 0)))
2032               break;
2033           }
2034
2035         XEXP (x, 0) = label;
2036         if (! insn || ! INSN_DELETED_P (insn))
2037           ++LABEL_NUSES (label);
2038
2039         if (insn)
2040           {
2041             if (GET_CODE (insn) == JUMP_INSN)
2042               JUMP_LABEL (insn) = label;
2043             else
2044               {
2045                 /* If we've changed the label, update notes accordingly.  */
2046                 if (label != olabel)
2047                   {
2048                     rtx note;
2049
2050                     /* We may have a REG_LABEL note to indicate that this
2051                        instruction uses the label.  */
2052                     note = find_reg_note (insn, REG_LABEL, olabel);
2053                     if (note)
2054                       XEXP (note, 0) = label;
2055
2056                     /* We may also have a REG_EQUAL note to indicate that
2057                        a register is being set to the address of the
2058                        label.  */
2059                     note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2060                     if (note
2061                         && GET_CODE (XEXP (note, 0)) == LABEL_REF
2062                         && XEXP (XEXP (note, 0), 0) == olabel)
2063                       XEXP (XEXP (note, 0), 0) = label;
2064                   }
2065
2066                 /* Add a REG_LABEL note for LABEL unless there already
2067                    is one.  All uses of a label, except for labels
2068                    that are the targets of jumps, must have a
2069                    REG_LABEL note.  */
2070                 if (! find_reg_note (insn, REG_LABEL, label))
2071                   REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
2072                                                         REG_NOTES (insn));
2073               }
2074           }
2075         return;
2076       }
2077
2078   /* Do walk the labels in a vector, but not the first operand of an
2079      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
2080     case ADDR_VEC:
2081     case ADDR_DIFF_VEC:
2082       if (! INSN_DELETED_P (insn))
2083         {
2084           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
2085
2086           for (i = 0; i < XVECLEN (x, eltnum); i++)
2087             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, in_mem);
2088         }
2089       return;
2090
2091     default:
2092       break;
2093     }
2094
2095   fmt = GET_RTX_FORMAT (code);
2096   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2097     {
2098       if (fmt[i] == 'e')
2099         mark_jump_label (XEXP (x, i), insn, in_mem);
2100       else if (fmt[i] == 'E')
2101         {
2102           register int j;
2103           for (j = 0; j < XVECLEN (x, i); j++)
2104             mark_jump_label (XVECEXP (x, i, j), insn, in_mem);
2105         }
2106     }
2107 }
2108
2109 /* If all INSN does is set the pc, delete it,
2110    and delete the insn that set the condition codes for it
2111    if that's what the previous thing was.  */
2112
2113 void
2114 delete_jump (insn)
2115      rtx insn;
2116 {
2117   register rtx set = single_set (insn);
2118
2119   if (set && GET_CODE (SET_DEST (set)) == PC)
2120     delete_computation (insn);
2121 }
2122
2123 /* Verify INSN is a BARRIER and delete it.  */
2124
2125 void
2126 delete_barrier (insn)
2127      rtx insn;
2128 {
2129   if (GET_CODE (insn) != BARRIER)
2130     abort ();
2131
2132   delete_insn (insn);
2133 }
2134
2135 /* Recursively delete prior insns that compute the value (used only by INSN
2136    which the caller is deleting) stored in the register mentioned by NOTE
2137    which is a REG_DEAD note associated with INSN.  */
2138
2139 static void
2140 delete_prior_computation (note, insn)
2141      rtx note;
2142      rtx insn;
2143 {
2144   rtx our_prev;
2145   rtx reg = XEXP (note, 0);
2146
2147   for (our_prev = prev_nonnote_insn (insn);
2148        our_prev && (GET_CODE (our_prev) == INSN
2149                     || GET_CODE (our_prev) == CALL_INSN);
2150        our_prev = prev_nonnote_insn (our_prev))
2151     {
2152       rtx pat = PATTERN (our_prev);
2153
2154       /* If we reach a CALL which is not calling a const function
2155          or the callee pops the arguments, then give up.  */
2156       if (GET_CODE (our_prev) == CALL_INSN
2157           && (! CONST_CALL_P (our_prev)
2158               || GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
2159         break;
2160
2161       /* If we reach a SEQUENCE, it is too complex to try to
2162          do anything with it, so give up.  */
2163       if (GET_CODE (pat) == SEQUENCE)
2164         break;
2165
2166       if (GET_CODE (pat) == USE
2167           && GET_CODE (XEXP (pat, 0)) == INSN)
2168         /* reorg creates USEs that look like this.  We leave them
2169            alone because reorg needs them for its own purposes.  */
2170         break;
2171
2172       if (reg_set_p (reg, pat))
2173         {
2174           if (side_effects_p (pat) && GET_CODE (our_prev) != CALL_INSN)
2175             break;
2176
2177           if (GET_CODE (pat) == PARALLEL)
2178             {
2179               /* If we find a SET of something else, we can't
2180                  delete the insn.  */
2181
2182               int i;
2183
2184               for (i = 0; i < XVECLEN (pat, 0); i++)
2185                 {
2186                   rtx part = XVECEXP (pat, 0, i);
2187
2188                   if (GET_CODE (part) == SET
2189                       && SET_DEST (part) != reg)
2190                     break;
2191                 }
2192
2193               if (i == XVECLEN (pat, 0))
2194                 delete_computation (our_prev);
2195             }
2196           else if (GET_CODE (pat) == SET
2197                    && GET_CODE (SET_DEST (pat)) == REG)
2198             {
2199               int dest_regno = REGNO (SET_DEST (pat));
2200               int dest_endregno
2201                 = (dest_regno
2202                    + (dest_regno < FIRST_PSEUDO_REGISTER
2203                       ? HARD_REGNO_NREGS (dest_regno,
2204                                           GET_MODE (SET_DEST (pat))) : 1));
2205               int regno = REGNO (reg);
2206               int endregno
2207                 = (regno
2208                    + (regno < FIRST_PSEUDO_REGISTER
2209                       ? HARD_REGNO_NREGS (regno, GET_MODE (reg)) : 1));
2210
2211               if (dest_regno >= regno
2212                   && dest_endregno <= endregno)
2213                 delete_computation (our_prev);
2214
2215               /* We may have a multi-word hard register and some, but not
2216                  all, of the words of the register are needed in subsequent
2217                  insns.  Write REG_UNUSED notes for those parts that were not
2218                  needed.  */
2219               else if (dest_regno <= regno
2220                        && dest_endregno >= endregno)
2221                 {
2222                   int i;
2223
2224                   REG_NOTES (our_prev)
2225                     = gen_rtx_EXPR_LIST (REG_UNUSED, reg,
2226                                          REG_NOTES (our_prev));
2227
2228                   for (i = dest_regno; i < dest_endregno; i++)
2229                     if (! find_regno_note (our_prev, REG_UNUSED, i))
2230                       break;
2231
2232                   if (i == dest_endregno)
2233                     delete_computation (our_prev);
2234                 }
2235             }
2236
2237           break;
2238         }
2239
2240       /* If PAT references the register that dies here, it is an
2241          additional use.  Hence any prior SET isn't dead.  However, this
2242          insn becomes the new place for the REG_DEAD note.  */
2243       if (reg_overlap_mentioned_p (reg, pat))
2244         {
2245           XEXP (note, 1) = REG_NOTES (our_prev);
2246           REG_NOTES (our_prev) = note;
2247           break;
2248         }
2249     }
2250 }
2251
2252 /* Delete INSN and recursively delete insns that compute values used only
2253    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
2254    If we are running before flow.c, we need do nothing since flow.c will
2255    delete dead code.  We also can't know if the registers being used are
2256    dead or not at this point.
2257
2258    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
2259    nothing other than set a register that dies in this insn, we can delete
2260    that insn as well.
2261
2262    On machines with CC0, if CC0 is used in this insn, we may be able to
2263    delete the insn that set it.  */
2264
2265 static void
2266 delete_computation (insn)
2267      rtx insn;
2268 {
2269   rtx note, next;
2270
2271 #ifdef HAVE_cc0
2272   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
2273     {
2274       rtx prev = prev_nonnote_insn (insn);
2275       /* We assume that at this stage
2276          CC's are always set explicitly
2277          and always immediately before the jump that
2278          will use them.  So if the previous insn
2279          exists to set the CC's, delete it
2280          (unless it performs auto-increments, etc.).  */
2281       if (prev && GET_CODE (prev) == INSN
2282           && sets_cc0_p (PATTERN (prev)))
2283         {
2284           if (sets_cc0_p (PATTERN (prev)) > 0
2285               && ! side_effects_p (PATTERN (prev)))
2286             delete_computation (prev);
2287           else
2288             /* Otherwise, show that cc0 won't be used.  */
2289             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
2290                                                   cc0_rtx, REG_NOTES (prev));
2291         }
2292     }
2293 #endif
2294
2295   for (note = REG_NOTES (insn); note; note = next)
2296     {
2297       next = XEXP (note, 1);
2298
2299       if (REG_NOTE_KIND (note) != REG_DEAD
2300           /* Verify that the REG_NOTE is legitimate.  */
2301           || GET_CODE (XEXP (note, 0)) != REG)
2302         continue;
2303
2304       delete_prior_computation (note, insn);
2305     }
2306
2307   delete_insn (insn);
2308 }
2309 \f
2310 /* Delete insn INSN from the chain of insns and update label ref counts.
2311    May delete some following insns as a consequence; may even delete
2312    a label elsewhere and insns that follow it.
2313
2314    Returns the first insn after INSN that was not deleted.  */
2315
2316 rtx
2317 delete_insn (insn)
2318      register rtx insn;
2319 {
2320   register rtx next = NEXT_INSN (insn);
2321   register rtx prev = PREV_INSN (insn);
2322   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
2323   register int dont_really_delete = 0;
2324   rtx note;
2325
2326   while (next && INSN_DELETED_P (next))
2327     next = NEXT_INSN (next);
2328
2329   /* This insn is already deleted => return first following nondeleted.  */
2330   if (INSN_DELETED_P (insn))
2331     return next;
2332
2333   if (was_code_label)
2334     remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
2335
2336   /* Don't delete user-declared labels.  When optimizing, convert them
2337      to special NOTEs instead.  When not optimizing, leave them alone.  */
2338   if (was_code_label && LABEL_NAME (insn) != 0)
2339     {
2340       if (optimize)
2341         {
2342           const char *name = LABEL_NAME (insn);
2343           PUT_CODE (insn, NOTE);
2344           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
2345           NOTE_SOURCE_FILE (insn) = name;
2346         }
2347
2348       dont_really_delete = 1;
2349     }
2350   else
2351     /* Mark this insn as deleted.  */
2352     INSN_DELETED_P (insn) = 1;
2353
2354   /* If this is an unconditional jump, delete it from the jump chain.  */
2355   if (simplejump_p (insn))
2356     delete_from_jump_chain (insn);
2357
2358   /* If instruction is followed by a barrier,
2359      delete the barrier too.  */
2360
2361   if (next != 0 && GET_CODE (next) == BARRIER)
2362     {
2363       INSN_DELETED_P (next) = 1;
2364       next = NEXT_INSN (next);
2365     }
2366
2367   /* Patch out INSN (and the barrier if any) */
2368
2369   if (! dont_really_delete)
2370     {
2371       if (prev)
2372         {
2373           NEXT_INSN (prev) = next;
2374           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
2375             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
2376                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
2377         }
2378
2379       if (next)
2380         {
2381           PREV_INSN (next) = prev;
2382           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
2383             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
2384         }
2385
2386       if (prev && NEXT_INSN (prev) == 0)
2387         set_last_insn (prev);
2388     }
2389
2390   /* If deleting a jump, decrement the count of the label,
2391      and delete the label if it is now unused.  */
2392
2393   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
2394     {
2395       rtx lab = JUMP_LABEL (insn), lab_next;
2396
2397       if (--LABEL_NUSES (lab) == 0)
2398         {
2399           /* This can delete NEXT or PREV,
2400              either directly if NEXT is JUMP_LABEL (INSN),
2401              or indirectly through more levels of jumps.  */
2402           delete_insn (lab);
2403
2404           /* I feel a little doubtful about this loop,
2405              but I see no clean and sure alternative way
2406              to find the first insn after INSN that is not now deleted.
2407              I hope this works.  */
2408           while (next && INSN_DELETED_P (next))
2409             next = NEXT_INSN (next);
2410           return next;
2411         }
2412       else if ((lab_next = next_nonnote_insn (lab)) != NULL
2413                && GET_CODE (lab_next) == JUMP_INSN
2414                && (GET_CODE (PATTERN (lab_next)) == ADDR_VEC
2415                    || GET_CODE (PATTERN (lab_next)) == ADDR_DIFF_VEC))
2416         {
2417           /* If we're deleting the tablejump, delete the dispatch table.
2418              We may not be able to kill the label immediately preceeding
2419              just yet, as it might be referenced in code leading up to
2420              the tablejump.  */
2421           delete_insn (lab_next);
2422         }
2423     }
2424
2425   /* Likewise if we're deleting a dispatch table.  */
2426
2427   if (GET_CODE (insn) == JUMP_INSN
2428       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
2429           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
2430     {
2431       rtx pat = PATTERN (insn);
2432       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
2433       int len = XVECLEN (pat, diff_vec_p);
2434
2435       for (i = 0; i < len; i++)
2436         if (--LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
2437           delete_insn (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
2438       while (next && INSN_DELETED_P (next))
2439         next = NEXT_INSN (next);
2440       return next;
2441     }
2442
2443   /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
2444   if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
2445     for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2446       if (REG_NOTE_KIND (note) == REG_LABEL
2447           /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
2448           && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
2449         if (--LABEL_NUSES (XEXP (note, 0)) == 0)
2450           delete_insn (XEXP (note, 0));
2451
2452   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
2453     prev = PREV_INSN (prev);
2454
2455   /* If INSN was a label and a dispatch table follows it,
2456      delete the dispatch table.  The tablejump must have gone already.
2457      It isn't useful to fall through into a table.  */
2458
2459   if (was_code_label
2460       && NEXT_INSN (insn) != 0
2461       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
2462       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
2463           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
2464     next = delete_insn (NEXT_INSN (insn));
2465
2466   /* If INSN was a label, delete insns following it if now unreachable.  */
2467
2468   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
2469     {
2470       register RTX_CODE code;
2471       while (next != 0
2472              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
2473                  || code == NOTE || code == BARRIER
2474                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
2475         {
2476           if (code == NOTE
2477               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
2478             next = NEXT_INSN (next);
2479           /* Keep going past other deleted labels to delete what follows.  */
2480           else if (code == CODE_LABEL && INSN_DELETED_P (next))
2481             next = NEXT_INSN (next);
2482           else
2483             /* Note: if this deletes a jump, it can cause more
2484                deletion of unreachable code, after a different label.
2485                As long as the value from this recursive call is correct,
2486                this invocation functions correctly.  */
2487             next = delete_insn (next);
2488         }
2489     }
2490
2491   return next;
2492 }
2493
2494 /* Advance from INSN till reaching something not deleted
2495    then return that.  May return INSN itself.  */
2496
2497 rtx
2498 next_nondeleted_insn (insn)
2499      rtx insn;
2500 {
2501   while (INSN_DELETED_P (insn))
2502     insn = NEXT_INSN (insn);
2503   return insn;
2504 }
2505 \f
2506 /* Delete a range of insns from FROM to TO, inclusive.
2507    This is for the sake of peephole optimization, so assume
2508    that whatever these insns do will still be done by a new
2509    peephole insn that will replace them.  */
2510
2511 void
2512 delete_for_peephole (from, to)
2513      register rtx from, to;
2514 {
2515   register rtx insn = from;
2516
2517   while (1)
2518     {
2519       register rtx next = NEXT_INSN (insn);
2520       register rtx prev = PREV_INSN (insn);
2521
2522       if (GET_CODE (insn) != NOTE)
2523         {
2524           INSN_DELETED_P (insn) = 1;
2525
2526           /* Patch this insn out of the chain.  */
2527           /* We don't do this all at once, because we
2528              must preserve all NOTEs.  */
2529           if (prev)
2530             NEXT_INSN (prev) = next;
2531
2532           if (next)
2533             PREV_INSN (next) = prev;
2534         }
2535
2536       if (insn == to)
2537         break;
2538       insn = next;
2539     }
2540
2541   /* Note that if TO is an unconditional jump
2542      we *do not* delete the BARRIER that follows,
2543      since the peephole that replaces this sequence
2544      is also an unconditional jump in that case.  */
2545 }
2546 \f
2547 /* We have determined that INSN is never reached, and are about to
2548    delete it.  Print a warning if the user asked for one.
2549
2550    To try to make this warning more useful, this should only be called
2551    once per basic block not reached, and it only warns when the basic
2552    block contains more than one line from the current function, and
2553    contains at least one operation.  CSE and inlining can duplicate insns,
2554    so it's possible to get spurious warnings from this.  */
2555
2556 void
2557 never_reached_warning (avoided_insn)
2558      rtx avoided_insn;
2559 {
2560   rtx insn;
2561   rtx a_line_note = NULL;
2562   int two_avoided_lines = 0;
2563   int contains_insn = 0;
2564
2565   if (! warn_notreached)
2566     return;
2567
2568   /* Scan forwards, looking at LINE_NUMBER notes, until
2569      we hit a LABEL or we run out of insns.  */
2570
2571   for (insn = avoided_insn; insn != NULL; insn = NEXT_INSN (insn))
2572     {
2573       if (GET_CODE (insn) == CODE_LABEL)
2574         break;
2575       else if (GET_CODE (insn) == NOTE          /* A line number note?  */
2576                && NOTE_LINE_NUMBER (insn) >= 0)
2577         {
2578           if (a_line_note == NULL)
2579             a_line_note = insn;
2580           else
2581             two_avoided_lines |= (NOTE_LINE_NUMBER (a_line_note)
2582                                   != NOTE_LINE_NUMBER (insn));
2583         }
2584       else if (INSN_P (insn))
2585         contains_insn = 1;
2586     }
2587   if (two_avoided_lines && contains_insn)
2588     warning_with_file_and_line (NOTE_SOURCE_FILE (a_line_note),
2589                                 NOTE_LINE_NUMBER (a_line_note),
2590                                 "will never be executed");
2591 }
2592 \f
2593 /* Throughout LOC, redirect OLABEL to NLABEL.  Treat null OLABEL or
2594    NLABEL as a return.  Accrue modifications into the change group.  */
2595
2596 static void
2597 redirect_exp_1 (loc, olabel, nlabel, insn)
2598      rtx *loc;
2599      rtx olabel, nlabel;
2600      rtx insn;
2601 {
2602   register rtx x = *loc;
2603   register RTX_CODE code = GET_CODE (x);
2604   register int i;
2605   register const char *fmt;
2606
2607   if (code == LABEL_REF)
2608     {
2609       if (XEXP (x, 0) == olabel)
2610         {
2611           rtx n;
2612           if (nlabel)
2613             n = gen_rtx_LABEL_REF (VOIDmode, nlabel);
2614           else
2615             n = gen_rtx_RETURN (VOIDmode);
2616
2617           validate_change (insn, loc, n, 1);
2618           return;
2619         }
2620     }
2621   else if (code == RETURN && olabel == 0)
2622     {
2623       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
2624       if (loc == &PATTERN (insn))
2625         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
2626       validate_change (insn, loc, x, 1);
2627       return;
2628     }
2629
2630   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
2631       && GET_CODE (SET_SRC (x)) == LABEL_REF
2632       && XEXP (SET_SRC (x), 0) == olabel)
2633     {
2634       validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
2635       return;
2636     }
2637
2638   fmt = GET_RTX_FORMAT (code);
2639   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2640     {
2641       if (fmt[i] == 'e')
2642         redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
2643       else if (fmt[i] == 'E')
2644         {
2645           register int j;
2646           for (j = 0; j < XVECLEN (x, i); j++)
2647             redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
2648         }
2649     }
2650 }
2651
2652 /* Similar, but apply the change group and report success or failure.  */
2653
2654 static int
2655 redirect_exp (olabel, nlabel, insn)
2656      rtx olabel, nlabel;
2657      rtx insn;
2658 {
2659   rtx *loc;
2660
2661   if (GET_CODE (PATTERN (insn)) == PARALLEL)
2662     loc = &XVECEXP (PATTERN (insn), 0, 0);
2663   else
2664     loc = &PATTERN (insn);
2665
2666   redirect_exp_1 (loc, olabel, nlabel, insn);
2667   if (num_validated_changes () == 0)
2668     return 0;
2669
2670   return apply_change_group ();
2671 }
2672
2673 /* Make JUMP go to NLABEL instead of where it jumps now.  Accrue
2674    the modifications into the change group.  Return false if we did
2675    not see how to do that.  */
2676
2677 int
2678 redirect_jump_1 (jump, nlabel)
2679      rtx jump, nlabel;
2680 {
2681   int ochanges = num_validated_changes ();
2682   rtx *loc;
2683
2684   if (GET_CODE (PATTERN (jump)) == PARALLEL)
2685     loc = &XVECEXP (PATTERN (jump), 0, 0);
2686   else
2687     loc = &PATTERN (jump);
2688
2689   redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
2690   return num_validated_changes () > ochanges;
2691 }
2692
2693 /* Make JUMP go to NLABEL instead of where it jumps now.  If the old
2694    jump target label is unused as a result, it and the code following
2695    it may be deleted.
2696
2697    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
2698    RETURN insn.
2699
2700    The return value will be 1 if the change was made, 0 if it wasn't
2701    (this can only occur for NLABEL == 0).  */
2702
2703 int
2704 redirect_jump (jump, nlabel, delete_unused)
2705      rtx jump, nlabel;
2706      int delete_unused;
2707 {
2708   register rtx olabel = JUMP_LABEL (jump);
2709
2710   if (nlabel == olabel)
2711     return 1;
2712
2713   if (! redirect_exp (olabel, nlabel, jump))
2714     return 0;
2715
2716   /* If this is an unconditional branch, delete it from the jump_chain of
2717      OLABEL and add it to the jump_chain of NLABEL (assuming both labels
2718      have UID's in range and JUMP_CHAIN is valid).  */
2719   if (jump_chain && (simplejump_p (jump)
2720                      || GET_CODE (PATTERN (jump)) == RETURN))
2721     {
2722       int label_index = nlabel ? INSN_UID (nlabel) : 0;
2723
2724       delete_from_jump_chain (jump);
2725       if (label_index < max_jump_chain
2726           && INSN_UID (jump) < max_jump_chain)
2727         {
2728           jump_chain[INSN_UID (jump)] = jump_chain[label_index];
2729           jump_chain[label_index] = jump;
2730         }
2731     }
2732
2733   JUMP_LABEL (jump) = nlabel;
2734   if (nlabel)
2735     ++LABEL_NUSES (nlabel);
2736
2737   /* If we're eliding the jump over exception cleanups at the end of a
2738      function, move the function end note so that -Wreturn-type works.  */
2739   if (olabel && nlabel
2740       && NEXT_INSN (olabel)
2741       && GET_CODE (NEXT_INSN (olabel)) == NOTE
2742       && NOTE_LINE_NUMBER (NEXT_INSN (olabel)) == NOTE_INSN_FUNCTION_END)
2743     emit_note_after (NOTE_INSN_FUNCTION_END, nlabel);
2744
2745   if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused)
2746     delete_insn (olabel);
2747
2748   return 1;
2749 }
2750
2751 /* Invert the jump condition of rtx X contained in jump insn, INSN.
2752    Accrue the modifications into the change group.  */
2753
2754 static void
2755 invert_exp_1 (insn)
2756      rtx insn;
2757 {
2758   register RTX_CODE code;
2759   rtx x = pc_set (insn);
2760
2761   if (!x)
2762     abort ();
2763   x = SET_SRC (x);
2764
2765   code = GET_CODE (x);
2766
2767   if (code == IF_THEN_ELSE)
2768     {
2769       register rtx comp = XEXP (x, 0);
2770       register rtx tem;
2771       enum rtx_code reversed_code;
2772
2773       /* We can do this in two ways:  The preferable way, which can only
2774          be done if this is not an integer comparison, is to reverse
2775          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
2776          of the IF_THEN_ELSE.  If we can't do either, fail.  */
2777
2778       reversed_code = reversed_comparison_code (comp, insn);
2779
2780       if (reversed_code != UNKNOWN)
2781         {
2782           validate_change (insn, &XEXP (x, 0),
2783                            gen_rtx_fmt_ee (reversed_code,
2784                                            GET_MODE (comp), XEXP (comp, 0),
2785                                            XEXP (comp, 1)),
2786                            1);
2787           return;
2788         }
2789
2790       tem = XEXP (x, 1);
2791       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
2792       validate_change (insn, &XEXP (x, 2), tem, 1);
2793     }
2794   else
2795     abort ();
2796 }
2797
2798 /* Invert the jump condition of conditional jump insn, INSN.
2799
2800    Return 1 if we can do so, 0 if we cannot find a way to do so that
2801    matches a pattern.  */
2802
2803 static int
2804 invert_exp (insn)
2805      rtx insn;
2806 {
2807   invert_exp_1 (insn);
2808   if (num_validated_changes () == 0)
2809     return 0;
2810
2811   return apply_change_group ();
2812 }
2813
2814 /* Invert the condition of the jump JUMP, and make it jump to label
2815    NLABEL instead of where it jumps now.  Accrue changes into the
2816    change group.  Return false if we didn't see how to perform the
2817    inversion and redirection.  */
2818
2819 int
2820 invert_jump_1 (jump, nlabel)
2821      rtx jump, nlabel;
2822 {
2823   int ochanges;
2824
2825   ochanges = num_validated_changes ();
2826   invert_exp_1 (jump);
2827   if (num_validated_changes () == ochanges)
2828     return 0;
2829
2830   return redirect_jump_1 (jump, nlabel);
2831 }
2832
2833 /* Invert the condition of the jump JUMP, and make it jump to label
2834    NLABEL instead of where it jumps now.  Return true if successful.  */
2835
2836 int
2837 invert_jump (jump, nlabel, delete_unused)
2838      rtx jump, nlabel;
2839      int delete_unused;
2840 {
2841   /* We have to either invert the condition and change the label or
2842      do neither.  Either operation could fail.  We first try to invert
2843      the jump. If that succeeds, we try changing the label.  If that fails,
2844      we invert the jump back to what it was.  */
2845
2846   if (! invert_exp (jump))
2847     return 0;
2848
2849   if (redirect_jump (jump, nlabel, delete_unused))
2850     {
2851       invert_br_probabilities (jump);
2852
2853       return 1;
2854     }
2855
2856   if (! invert_exp (jump))
2857     /* This should just be putting it back the way it was.  */
2858     abort ();
2859
2860   return 0;
2861 }
2862
2863 /* Delete the instruction JUMP from any jump chain it might be on.  */
2864
2865 static void
2866 delete_from_jump_chain (jump)
2867      rtx jump;
2868 {
2869   int index;
2870   rtx olabel = JUMP_LABEL (jump);
2871
2872   /* Handle unconditional jumps.  */
2873   if (jump_chain && olabel != 0
2874       && INSN_UID (olabel) < max_jump_chain
2875       && simplejump_p (jump))
2876     index = INSN_UID (olabel);
2877   /* Handle return insns.  */
2878   else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
2879     index = 0;
2880   else
2881     return;
2882
2883   if (jump_chain[index] == jump)
2884     jump_chain[index] = jump_chain[INSN_UID (jump)];
2885   else
2886     {
2887       rtx insn;
2888
2889       for (insn = jump_chain[index];
2890            insn != 0;
2891            insn = jump_chain[INSN_UID (insn)])
2892         if (jump_chain[INSN_UID (insn)] == jump)
2893           {
2894             jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
2895             break;
2896           }
2897     }
2898 }
2899 \f
2900 /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
2901
2902    If the old jump target label (before the dispatch table) becomes unused,
2903    it and the dispatch table may be deleted.  In that case, find the insn
2904    before the jump references that label and delete it and logical successors
2905    too.  */
2906
2907 static void
2908 redirect_tablejump (jump, nlabel)
2909      rtx jump, nlabel;
2910 {
2911   register rtx olabel = JUMP_LABEL (jump);
2912   rtx *notep, note, next;
2913
2914   /* Add this jump to the jump_chain of NLABEL.  */
2915   if (jump_chain && INSN_UID (nlabel) < max_jump_chain
2916       && INSN_UID (jump) < max_jump_chain)
2917     {
2918       jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
2919       jump_chain[INSN_UID (nlabel)] = jump;
2920     }
2921
2922   for (notep = &REG_NOTES (jump), note = *notep; note; note = next)
2923     {
2924       next = XEXP (note, 1);
2925
2926       if (REG_NOTE_KIND (note) != REG_DEAD
2927           /* Verify that the REG_NOTE is legitimate.  */
2928           || GET_CODE (XEXP (note, 0)) != REG
2929           || ! reg_mentioned_p (XEXP (note, 0), PATTERN (jump)))
2930         notep = &XEXP (note, 1);
2931       else
2932         {
2933           delete_prior_computation (note, jump);
2934           *notep = next;
2935         }
2936     }
2937
2938   PATTERN (jump) = gen_jump (nlabel);
2939   JUMP_LABEL (jump) = nlabel;
2940   ++LABEL_NUSES (nlabel);
2941   INSN_CODE (jump) = -1;
2942
2943   if (--LABEL_NUSES (olabel) == 0)
2944     {
2945       delete_labelref_insn (jump, olabel, 0);
2946       delete_insn (olabel);
2947     }
2948 }
2949
2950 /* Find the insn referencing LABEL that is a logical predecessor of INSN.
2951    If we found one, delete it and then delete this insn if DELETE_THIS is
2952    non-zero.  Return non-zero if INSN or a predecessor references LABEL.  */
2953
2954 static int
2955 delete_labelref_insn (insn, label, delete_this)
2956      rtx insn, label;
2957      int delete_this;
2958 {
2959   int deleted = 0;
2960   rtx link;
2961
2962   if (GET_CODE (insn) != NOTE
2963       && reg_mentioned_p (label, PATTERN (insn)))
2964     {
2965       if (delete_this)
2966         {
2967           delete_insn (insn);
2968           deleted = 1;
2969         }
2970       else
2971         return 1;
2972     }
2973
2974   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
2975     if (delete_labelref_insn (XEXP (link, 0), label, 1))
2976       {
2977         if (delete_this)
2978           {
2979             delete_insn (insn);
2980             deleted = 1;
2981           }
2982         else
2983           return 1;
2984       }
2985
2986   return deleted;
2987 }
2988 \f
2989 /* Like rtx_equal_p except that it considers two REGs as equal
2990    if they renumber to the same value and considers two commutative
2991    operations to be the same if the order of the operands has been
2992    reversed.
2993
2994    ??? Addition is not commutative on the PA due to the weird implicit
2995    space register selection rules for memory addresses.  Therefore, we
2996    don't consider a + b == b + a.
2997
2998    We could/should make this test a little tighter.  Possibly only
2999    disabling it on the PA via some backend macro or only disabling this
3000    case when the PLUS is inside a MEM.  */
3001
3002 int
3003 rtx_renumbered_equal_p (x, y)
3004      rtx x, y;
3005 {
3006   register int i;
3007   register RTX_CODE code = GET_CODE (x);
3008   register const char *fmt;
3009
3010   if (x == y)
3011     return 1;
3012
3013   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
3014       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
3015                                   && GET_CODE (SUBREG_REG (y)) == REG)))
3016     {
3017       int reg_x = -1, reg_y = -1;
3018       int byte_x = 0, byte_y = 0;
3019
3020       if (GET_MODE (x) != GET_MODE (y))
3021         return 0;
3022
3023       /* If we haven't done any renumbering, don't
3024          make any assumptions.  */
3025       if (reg_renumber == 0)
3026         return rtx_equal_p (x, y);
3027
3028       if (code == SUBREG)
3029         {
3030           reg_x = REGNO (SUBREG_REG (x));
3031           byte_x = SUBREG_BYTE (x);
3032
3033           if (reg_renumber[reg_x] >= 0)
3034             {
3035               reg_x = subreg_regno_offset (reg_renumber[reg_x],
3036                                            GET_MODE (SUBREG_REG (x)),
3037                                            byte_x,
3038                                            GET_MODE (x));
3039               byte_x = 0;
3040             }
3041         }
3042       else
3043         {
3044           reg_x = REGNO (x);
3045           if (reg_renumber[reg_x] >= 0)
3046             reg_x = reg_renumber[reg_x];
3047         }
3048
3049       if (GET_CODE (y) == SUBREG)
3050         {
3051           reg_y = REGNO (SUBREG_REG (y));
3052           byte_y = SUBREG_BYTE (y);
3053
3054           if (reg_renumber[reg_y] >= 0)
3055             {
3056               reg_y = subreg_regno_offset (reg_renumber[reg_y],
3057                                            GET_MODE (SUBREG_REG (y)),
3058                                            byte_y,
3059                                            GET_MODE (y));
3060               byte_y = 0;
3061             }
3062         }
3063       else
3064         {
3065           reg_y = REGNO (y);
3066           if (reg_renumber[reg_y] >= 0)
3067             reg_y = reg_renumber[reg_y];
3068         }
3069
3070       return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
3071     }
3072
3073   /* Now we have disposed of all the cases
3074      in which different rtx codes can match.  */
3075   if (code != GET_CODE (y))
3076     return 0;
3077
3078   switch (code)
3079     {
3080     case PC:
3081     case CC0:
3082     case ADDR_VEC:
3083     case ADDR_DIFF_VEC:
3084       return 0;
3085
3086     case CONST_INT:
3087       return INTVAL (x) == INTVAL (y);
3088
3089     case LABEL_REF:
3090       /* We can't assume nonlocal labels have their following insns yet.  */
3091       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
3092         return XEXP (x, 0) == XEXP (y, 0);
3093
3094       /* Two label-refs are equivalent if they point at labels
3095          in the same position in the instruction stream.  */
3096       return (next_real_insn (XEXP (x, 0))
3097               == next_real_insn (XEXP (y, 0)));
3098
3099     case SYMBOL_REF:
3100       return XSTR (x, 0) == XSTR (y, 0);
3101
3102     case CODE_LABEL:
3103       /* If we didn't match EQ equality above, they aren't the same.  */
3104       return 0;
3105
3106     default:
3107       break;
3108     }
3109
3110   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
3111
3112   if (GET_MODE (x) != GET_MODE (y))
3113     return 0;
3114
3115   /* For commutative operations, the RTX match if the operand match in any
3116      order.  Also handle the simple binary and unary cases without a loop.
3117
3118      ??? Don't consider PLUS a commutative operator; see comments above.  */
3119   if ((code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3120       && code != PLUS)
3121     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3122              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
3123             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
3124                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
3125   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
3126     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
3127             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
3128   else if (GET_RTX_CLASS (code) == '1')
3129     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
3130
3131   /* Compare the elements.  If any pair of corresponding elements
3132      fail to match, return 0 for the whole things.  */
3133
3134   fmt = GET_RTX_FORMAT (code);
3135   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3136     {
3137       register int j;
3138       switch (fmt[i])
3139         {
3140         case 'w':
3141           if (XWINT (x, i) != XWINT (y, i))
3142             return 0;
3143           break;
3144
3145         case 'i':
3146           if (XINT (x, i) != XINT (y, i))
3147             return 0;
3148           break;
3149
3150         case 't':
3151           if (XTREE (x, i) != XTREE (y, i))
3152             return 0;
3153           break;
3154
3155         case 's':
3156           if (strcmp (XSTR (x, i), XSTR (y, i)))
3157             return 0;
3158           break;
3159
3160         case 'e':
3161           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
3162             return 0;
3163           break;
3164
3165         case 'u':
3166           if (XEXP (x, i) != XEXP (y, i))
3167             return 0;
3168           /* fall through.  */
3169         case '0':
3170           break;
3171
3172         case 'E':
3173           if (XVECLEN (x, i) != XVECLEN (y, i))
3174             return 0;
3175           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3176             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
3177               return 0;
3178           break;
3179
3180         default:
3181           abort ();
3182         }
3183     }
3184   return 1;
3185 }
3186 \f
3187 /* If X is a hard register or equivalent to one or a subregister of one,
3188    return the hard register number.  If X is a pseudo register that was not
3189    assigned a hard register, return the pseudo register number.  Otherwise,
3190    return -1.  Any rtx is valid for X.  */
3191
3192 int
3193 true_regnum (x)
3194      rtx x;
3195 {
3196   if (GET_CODE (x) == REG)
3197     {
3198       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
3199         return reg_renumber[REGNO (x)];
3200       return REGNO (x);
3201     }
3202   if (GET_CODE (x) == SUBREG)
3203     {
3204       int base = true_regnum (SUBREG_REG (x));
3205       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
3206         return base + subreg_regno_offset (REGNO (SUBREG_REG (x)),
3207                                            GET_MODE (SUBREG_REG (x)),
3208                                            SUBREG_BYTE (x), GET_MODE (x));
3209     }
3210   return -1;
3211 }
3212 \f
3213 /* Optimize code of the form:
3214
3215         for (x = a[i]; x; ...)
3216           ...
3217         for (x = a[i]; x; ...)
3218           ...
3219       foo:
3220
3221    Loop optimize will change the above code into
3222
3223         if (x = a[i])
3224           for (;;)
3225              { ...; if (! (x = ...)) break; }
3226         if (x = a[i])
3227           for (;;)
3228              { ...; if (! (x = ...)) break; }
3229       foo:
3230
3231    In general, if the first test fails, the program can branch
3232    directly to `foo' and skip the second try which is doomed to fail.
3233    We run this after loop optimization and before flow analysis.  */
3234
3235 /* When comparing the insn patterns, we track the fact that different
3236    pseudo-register numbers may have been used in each computation.
3237    The following array stores an equivalence -- same_regs[I] == J means
3238    that pseudo register I was used in the first set of tests in a context
3239    where J was used in the second set.  We also count the number of such
3240    pending equivalences.  If nonzero, the expressions really aren't the
3241    same.  */
3242
3243 static int *same_regs;
3244
3245 static int num_same_regs;
3246
3247 /* Track any registers modified between the target of the first jump and
3248    the second jump.  They never compare equal.  */
3249
3250 static char *modified_regs;
3251
3252 /* Record if memory was modified.  */
3253
3254 static int modified_mem;
3255
3256 /* Called via note_stores on each insn between the target of the first
3257    branch and the second branch.  It marks any changed registers.  */
3258
3259 static void
3260 mark_modified_reg (dest, x, data)
3261      rtx dest;
3262      rtx x;
3263      void *data ATTRIBUTE_UNUSED;
3264 {
3265   int regno;
3266   unsigned int i;
3267
3268   if (GET_CODE (dest) == SUBREG)
3269     dest = SUBREG_REG (dest);
3270
3271   if (GET_CODE (dest) == MEM)
3272     modified_mem = 1;
3273
3274   if (GET_CODE (dest) != REG)
3275     return;
3276
3277   regno = REGNO (dest);
3278   if (regno >= FIRST_PSEUDO_REGISTER)
3279     modified_regs[regno] = 1;
3280   /* Don't consider a hard condition code register as modified,
3281      if it is only being set.  thread_jumps will check if it is set
3282      to the same value.  */
3283   else if (GET_MODE_CLASS (GET_MODE (dest)) != MODE_CC
3284            || GET_CODE (x) != SET
3285            || ! rtx_equal_p (dest, SET_DEST (x))
3286            || HARD_REGNO_NREGS (regno, GET_MODE (dest)) != 1)
3287     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
3288       modified_regs[regno + i] = 1;
3289 }
3290
3291 /* F is the first insn in the chain of insns.  */
3292
3293 void
3294 thread_jumps (f, max_reg, flag_before_loop)
3295      rtx f;
3296      int max_reg;
3297      int flag_before_loop;
3298 {
3299   /* Basic algorithm is to find a conditional branch,
3300      the label it may branch to, and the branch after
3301      that label.  If the two branches test the same condition,
3302      walk back from both branch paths until the insn patterns
3303      differ, or code labels are hit.  If we make it back to
3304      the target of the first branch, then we know that the first branch
3305      will either always succeed or always fail depending on the relative
3306      senses of the two branches.  So adjust the first branch accordingly
3307      in this case.  */
3308
3309   rtx label, b1, b2, t1, t2;
3310   enum rtx_code code1, code2;
3311   rtx b1op0, b1op1, b2op0, b2op1;
3312   int changed = 1;
3313   int i;
3314   int *all_reset;
3315   enum rtx_code reversed_code1, reversed_code2;
3316
3317   /* Allocate register tables and quick-reset table.  */
3318   modified_regs = (char *) xmalloc (max_reg * sizeof (char));
3319   same_regs = (int *) xmalloc (max_reg * sizeof (int));
3320   all_reset = (int *) xmalloc (max_reg * sizeof (int));
3321   for (i = 0; i < max_reg; i++)
3322     all_reset[i] = -1;
3323
3324   while (changed)
3325     {
3326       changed = 0;
3327
3328       for (b1 = f; b1; b1 = NEXT_INSN (b1))
3329         {
3330           rtx set;
3331           rtx set2;
3332
3333           /* Get to a candidate branch insn.  */
3334           if (GET_CODE (b1) != JUMP_INSN
3335               || ! any_condjump_p (b1) || JUMP_LABEL (b1) == 0)
3336             continue;
3337
3338           memset (modified_regs, 0, max_reg * sizeof (char));
3339           modified_mem = 0;
3340
3341           memcpy (same_regs, all_reset, max_reg * sizeof (int));
3342           num_same_regs = 0;
3343
3344           label = JUMP_LABEL (b1);
3345
3346           /* Look for a branch after the target.  Record any registers and
3347              memory modified between the target and the branch.  Stop when we
3348              get to a label since we can't know what was changed there.  */
3349           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
3350             {
3351               if (GET_CODE (b2) == CODE_LABEL)
3352                 break;
3353
3354               else if (GET_CODE (b2) == JUMP_INSN)
3355                 {
3356                   /* If this is an unconditional jump and is the only use of
3357                      its target label, we can follow it.  */
3358                   if (any_uncondjump_p (b2)
3359                       && onlyjump_p (b2)
3360                       && JUMP_LABEL (b2) != 0
3361                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
3362                     {
3363                       b2 = JUMP_LABEL (b2);
3364                       continue;
3365                     }
3366                   else
3367                     break;
3368                 }
3369
3370               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
3371                 continue;
3372
3373               if (GET_CODE (b2) == CALL_INSN)
3374                 {
3375                   modified_mem = 1;
3376                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3377                     if (call_used_regs[i] && ! fixed_regs[i]
3378                         && i != STACK_POINTER_REGNUM
3379                         && i != FRAME_POINTER_REGNUM
3380                         && i != HARD_FRAME_POINTER_REGNUM
3381                         && i != ARG_POINTER_REGNUM)
3382                       modified_regs[i] = 1;
3383                 }
3384
3385               note_stores (PATTERN (b2), mark_modified_reg, NULL);
3386             }
3387
3388           /* Check the next candidate branch insn from the label
3389              of the first.  */
3390           if (b2 == 0
3391               || GET_CODE (b2) != JUMP_INSN
3392               || b2 == b1
3393               || !any_condjump_p (b2)
3394               || !onlyjump_p (b2))
3395             continue;
3396           set = pc_set (b1);
3397           set2 = pc_set (b2);
3398
3399           /* Get the comparison codes and operands, reversing the
3400              codes if appropriate.  If we don't have comparison codes,
3401              we can't do anything.  */
3402           b1op0 = XEXP (XEXP (SET_SRC (set), 0), 0);
3403           b1op1 = XEXP (XEXP (SET_SRC (set), 0), 1);
3404           code1 = GET_CODE (XEXP (SET_SRC (set), 0));
3405           reversed_code1 = code1;
3406           if (XEXP (SET_SRC (set), 1) == pc_rtx)
3407             code1 = reversed_comparison_code (XEXP (SET_SRC (set), 0), b1);
3408           else
3409             reversed_code1 = reversed_comparison_code (XEXP (SET_SRC (set), 0), b1);
3410
3411           b2op0 = XEXP (XEXP (SET_SRC (set2), 0), 0);
3412           b2op1 = XEXP (XEXP (SET_SRC (set2), 0), 1);
3413           code2 = GET_CODE (XEXP (SET_SRC (set2), 0));
3414           reversed_code2 = code2;
3415           if (XEXP (SET_SRC (set2), 1) == pc_rtx)
3416             code2 = reversed_comparison_code (XEXP (SET_SRC (set2), 0), b2);
3417           else
3418             reversed_code2 = reversed_comparison_code (XEXP (SET_SRC (set2), 0), b2);
3419
3420           /* If they test the same things and knowing that B1 branches
3421              tells us whether or not B2 branches, check if we
3422              can thread the branch.  */
3423           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
3424               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
3425               && (comparison_dominates_p (code1, code2)
3426                   || comparison_dominates_p (code1, reversed_code2)))
3427
3428             {
3429               t1 = prev_nonnote_insn (b1);
3430               t2 = prev_nonnote_insn (b2);
3431
3432               while (t1 != 0 && t2 != 0)
3433                 {
3434                   if (t2 == label)
3435                     {
3436                       /* We have reached the target of the first branch.
3437                          If there are no pending register equivalents,
3438                          we know that this branch will either always
3439                          succeed (if the senses of the two branches are
3440                          the same) or always fail (if not).  */
3441                       rtx new_label;
3442
3443                       if (num_same_regs != 0)
3444                         break;
3445
3446                       if (comparison_dominates_p (code1, code2))
3447                         new_label = JUMP_LABEL (b2);
3448                       else
3449                         new_label = get_label_after (b2);
3450
3451                       if (JUMP_LABEL (b1) != new_label)
3452                         {
3453                           rtx prev = PREV_INSN (new_label);
3454
3455                           if (flag_before_loop
3456                               && GET_CODE (prev) == NOTE
3457                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
3458                             {
3459                               /* Don't thread to the loop label.  If a loop
3460                                  label is reused, loop optimization will
3461                                  be disabled for that loop.  */
3462                               new_label = gen_label_rtx ();
3463                               emit_label_after (new_label, PREV_INSN (prev));
3464                             }
3465                           changed |= redirect_jump (b1, new_label, 1);
3466                         }
3467                       break;
3468                     }
3469
3470                   /* If either of these is not a normal insn (it might be
3471                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
3472                      have already been skipped above.)  Similarly, fail
3473                      if the insns are different.  */
3474                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
3475                       || recog_memoized (t1) != recog_memoized (t2)
3476                       || ! rtx_equal_for_thread_p (PATTERN (t1),
3477                                                    PATTERN (t2), t2))
3478                     break;
3479
3480                   t1 = prev_nonnote_insn (t1);
3481                   t2 = prev_nonnote_insn (t2);
3482                 }
3483             }
3484         }
3485     }
3486
3487   /* Clean up.  */
3488   free (modified_regs);
3489   free (same_regs);
3490   free (all_reset);
3491 }
3492 \f
3493 /* This is like RTX_EQUAL_P except that it knows about our handling of
3494    possibly equivalent registers and knows to consider volatile and
3495    modified objects as not equal.
3496
3497    YINSN is the insn containing Y.  */
3498
3499 int
3500 rtx_equal_for_thread_p (x, y, yinsn)
3501      rtx x, y;
3502      rtx yinsn;
3503 {
3504   register int i;
3505   register int j;
3506   register enum rtx_code code;
3507   register const char *fmt;
3508
3509   code = GET_CODE (x);
3510   /* Rtx's of different codes cannot be equal.  */
3511   if (code != GET_CODE (y))
3512     return 0;
3513
3514   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
3515      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
3516
3517   if (GET_MODE (x) != GET_MODE (y))
3518     return 0;
3519
3520   /* For floating-point, consider everything unequal.  This is a bit
3521      pessimistic, but this pass would only rarely do anything for FP
3522      anyway.  */
3523   if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
3524       && FLOAT_MODE_P (GET_MODE (x)) && ! flag_unsafe_math_optimizations)
3525     return 0;
3526
3527   /* For commutative operations, the RTX match if the operand match in any
3528      order.  Also handle the simple binary and unary cases without a loop.  */
3529   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
3530     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
3531              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
3532             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
3533                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
3534   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
3535     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
3536             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
3537   else if (GET_RTX_CLASS (code) == '1')
3538     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
3539
3540   /* Handle special-cases first.  */
3541   switch (code)
3542     {
3543     case REG:
3544       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
3545         return 1;
3546
3547       /* If neither is user variable or hard register, check for possible
3548          equivalence.  */
3549       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
3550           || REGNO (x) < FIRST_PSEUDO_REGISTER
3551           || REGNO (y) < FIRST_PSEUDO_REGISTER)
3552         return 0;
3553
3554       if (same_regs[REGNO (x)] == -1)
3555         {
3556           same_regs[REGNO (x)] = REGNO (y);
3557           num_same_regs++;
3558
3559           /* If this is the first time we are seeing a register on the `Y'
3560              side, see if it is the last use.  If not, we can't thread the
3561              jump, so mark it as not equivalent.  */
3562           if (REGNO_LAST_UID (REGNO (y)) != INSN_UID (yinsn))
3563             return 0;
3564
3565           return 1;
3566         }
3567       else
3568         return (same_regs[REGNO (x)] == (int) REGNO (y));
3569
3570       break;
3571
3572     case MEM:
3573       /* If memory modified or either volatile, not equivalent.
3574          Else, check address.  */
3575       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
3576         return 0;
3577
3578       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
3579
3580     case ASM_INPUT:
3581       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
3582         return 0;
3583
3584       break;
3585
3586     case SET:
3587       /* Cancel a pending `same_regs' if setting equivalenced registers.
3588          Then process source.  */
3589       if (GET_CODE (SET_DEST (x)) == REG
3590           && GET_CODE (SET_DEST (y)) == REG)
3591         {
3592           if (same_regs[REGNO (SET_DEST (x))] == (int) REGNO (SET_DEST (y)))
3593             {
3594               same_regs[REGNO (SET_DEST (x))] = -1;
3595               num_same_regs--;
3596             }
3597           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
3598             return 0;
3599         }
3600       else
3601         {
3602           if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
3603             return 0;
3604         }
3605
3606       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
3607
3608     case LABEL_REF:
3609       return XEXP (x, 0) == XEXP (y, 0);
3610
3611     case SYMBOL_REF:
3612       return XSTR (x, 0) == XSTR (y, 0);
3613
3614     default:
3615       break;
3616     }
3617
3618   if (x == y)
3619     return 1;
3620
3621   fmt = GET_RTX_FORMAT (code);
3622   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3623     {
3624       switch (fmt[i])
3625         {
3626         case 'w':
3627           if (XWINT (x, i) != XWINT (y, i))
3628             return 0;
3629           break;
3630
3631         case 'n':
3632         case 'i':
3633           if (XINT (x, i) != XINT (y, i))
3634             return 0;
3635           break;
3636
3637         case 'V':
3638         case 'E':
3639           /* Two vectors must have the same length.  */
3640           if (XVECLEN (x, i) != XVECLEN (y, i))
3641             return 0;
3642
3643           /* And the corresponding elements must match.  */
3644           for (j = 0; j < XVECLEN (x, i); j++)
3645             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
3646                                         XVECEXP (y, i, j), yinsn) == 0)
3647               return 0;
3648           break;
3649
3650         case 'e':
3651           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
3652             return 0;
3653           break;
3654
3655         case 'S':
3656         case 's':
3657           if (strcmp (XSTR (x, i), XSTR (y, i)))
3658             return 0;
3659           break;
3660
3661         case 'u':
3662           /* These are just backpointers, so they don't matter.  */
3663           break;
3664
3665         case '0':
3666         case 't':
3667           break;
3668
3669           /* It is believed that rtx's at this level will never
3670              contain anything but integers and other rtx's,
3671              except for within LABEL_REFs and SYMBOL_REFs.  */
3672         default:
3673           abort ();
3674         }
3675     }
3676   return 1;
3677 }