gcc/jump.c

   1 /* Optimize jump instructions, for GNU compiler.
   2    Copyright (C) 1987, 88, 89, 91-97, 1998 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  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    Optionally, cross-jumping can be done.  Currently it is done
  40    only the last time (when after reload and before final).
  41    In fact, the code for cross-jumping now assumes that register
  42    allocation has been done, since it uses `rtx_renumbered_equal_p'.
  43
  44    Jump optimization is done after cse when cse's constant-propagation
  45    causes jumps to become unconditional or to be deleted.
  46
  47    Unreachable loops are not detected here, because the labels
  48    have references and the insns appear reachable from the labels.
  49    find_basic_blocks in flow.c finds and deletes such loops.
  50
  51    The subroutines delete_insn, redirect_jump, and invert_jump are used
  52    from other passes as well.  */
  53
  54 #include "config.h"
  55 #include "system.h"
  56 #include "rtl.h"
  57 #include "flags.h"
  58 #include "hard-reg-set.h"
  59 #include "regs.h"
  60 #include "insn-config.h"
  61 #include "insn-flags.h"
  62 #include "recog.h"
  63 #include "expr.h"
  64 #include "real.h"
  65 #include "except.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 /* List of labels referred to from initializers.
  91    These can never be deleted.  */
  92 rtx forced_labels;
  93
  94 /* Maximum index in jump_chain.  */
  95
  96 static int max_jump_chain;
  97
  98 /* Set nonzero by jump_optimize if control can fall through
  99    to the end of the function.  */
 100 int can_reach_end;
 101
 102 /* Indicates whether death notes are significant in cross jump analysis.
 103    Normally they are not significant, because of A and B jump to C,
 104    and R dies in A, it must die in B.  But this might not be true after
 105    stack register conversion, and we must compare death notes in that
 106    case.  */
 107
 108 static int cross_jump_death_matters = 0;
 109
 110 static int duplicate_loop_exit_test     PROTO((rtx));
 111 static void find_cross_jump             PROTO((rtx, rtx, int, rtx *, rtx *));
 112 static void do_cross_jump               PROTO((rtx, rtx, rtx));
 113 static int jump_back_p                  PROTO((rtx, rtx));
 114 static int tension_vector_labels        PROTO((rtx, int));
 115 static void mark_jump_label             PROTO((rtx, rtx, int));
 116 static void delete_computation          PROTO((rtx));
 117 static void delete_from_jump_chain      PROTO((rtx));
 118 static int delete_labelref_insn         PROTO((rtx, rtx, int));
 119 static void mark_modified_reg           PROTO((rtx, rtx));
 120 static void redirect_tablejump          PROTO((rtx, rtx));
 121 static rtx find_insert_position         PROTO((rtx, rtx));
 122 \f
 123 /* Delete no-op jumps and optimize jumps to jumps
 124    and jumps around jumps.
 125    Delete unused labels and unreachable code.
 126
 127    If CROSS_JUMP is 1, detect matching code
 128    before a jump and its destination and unify them.
 129    If CROSS_JUMP is 2, do cross-jumping, but pay attention to death notes.
 130
 131    If NOOP_MOVES is nonzero, delete no-op move insns.
 132
 133    If AFTER_REGSCAN is nonzero, then this jump pass is being run immediately
 134    after regscan, and it is safe to use regno_first_uid and regno_last_uid.
 135
 136    If `optimize' is zero, don't change any code,
 137    just determine whether control drops off the end of the function.
 138    This case occurs when we have -W and not -O.
 139    It works because `delete_insn' checks the value of `optimize'
 140    and refrains from actually deleting when that is 0.  */
 141
 142 void
 143 jump_optimize (f, cross_jump, noop_moves, after_regscan)
 144      rtx f;
 145      int cross_jump;
 146      int noop_moves;
 147      int after_regscan;
 148 {
 149   register rtx insn, next, note;
 150   int changed;
 151   int first = 1;
 152   int max_uid = 0;
 153   rtx last_insn;
 154
 155   cross_jump_death_matters = (cross_jump == 2);
 156
 157   /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
 158      notes whose labels don't occur in the insn any more.  */
 159
 160   for (insn = f; insn; insn = NEXT_INSN (insn))
 161     {
 162       if (GET_CODE (insn) == CODE_LABEL)
 163         LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
 164       else if (GET_CODE (insn) == JUMP_INSN)
 165         JUMP_LABEL (insn) = 0;
 166       else if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 167         for (note = REG_NOTES (insn); note; note = next)
 168           {
 169             next = XEXP (note, 1);
 170             if (REG_NOTE_KIND (note) == REG_LABEL
 171                 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
 172               remove_note (insn, note);
 173           }
 174
 175       if (INSN_UID (insn) > max_uid)
 176         max_uid = INSN_UID (insn);
 177     }
 178
 179   max_uid++;
 180
 181   /* Delete insns following barriers, up to next label.  */
 182
 183   for (insn = f; insn;)
 184     {
 185       if (GET_CODE (insn) == BARRIER)
 186         {
 187           insn = NEXT_INSN (insn);
 188           while (insn != 0 && GET_CODE (insn) != CODE_LABEL)
 189             {
 190               if (GET_CODE (insn) == NOTE
 191                   && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)
 192                 insn = NEXT_INSN (insn);
 193               else
 194                 insn = delete_insn (insn);
 195             }
 196           /* INSN is now the code_label.  */
 197         }
 198       else
 199         insn = NEXT_INSN (insn);
 200     }
 201
 202   /* Leave some extra room for labels and duplicate exit test insns
 203      we make.  */
 204   max_jump_chain = max_uid * 14 / 10;
 205   jump_chain = (rtx *) alloca (max_jump_chain * sizeof (rtx));
 206   bzero ((char *) jump_chain, max_jump_chain * sizeof (rtx));
 207
 208   /* Mark the label each jump jumps to.
 209      Combine consecutive labels, and count uses of labels.
 210
 211      For each label, make a chain (using `jump_chain')
 212      of all the *unconditional* jumps that jump to it;
 213      also make a chain of all returns.  */
 214
 215   for (insn = f; insn; insn = NEXT_INSN (insn))
 216     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 217       {
 218         mark_jump_label (PATTERN (insn), insn, cross_jump);
 219         if (! INSN_DELETED_P (insn) && GET_CODE (insn) == JUMP_INSN)
 220           {
 221             if (JUMP_LABEL (insn) != 0 && simplejump_p (insn))
 222               {
 223                 jump_chain[INSN_UID (insn)]
 224                   = jump_chain[INSN_UID (JUMP_LABEL (insn))];
 225                 jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
 226               }
 227             if (GET_CODE (PATTERN (insn)) == RETURN)
 228               {
 229                 jump_chain[INSN_UID (insn)] = jump_chain[0];
 230                 jump_chain[0] = insn;
 231               }
 232           }
 233       }
 234
 235   /* Keep track of labels used from static data;
 236      they cannot ever be deleted.  */
 237
 238   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
 239     LABEL_NUSES (XEXP (insn, 0))++;
 240
 241   check_exception_handler_labels ();
 242
 243   /* Keep track of labels used for marking handlers for exception
 244      regions; they cannot usually be deleted.  */
 245
 246   for (insn = exception_handler_labels; insn; insn = XEXP (insn, 1))
 247     LABEL_NUSES (XEXP (insn, 0))++;
 248
 249   exception_optimize ();
 250
 251   /* Delete all labels already not referenced.
 252      Also find the last insn.  */
 253
 254   last_insn = 0;
 255   for (insn = f; insn; )
 256     {
 257       if (GET_CODE (insn) == CODE_LABEL && LABEL_NUSES (insn) == 0)
 258         insn = delete_insn (insn);
 259       else
 260         {
 261           last_insn = insn;
 262           insn = NEXT_INSN (insn);
 263         }
 264     }
 265
 266   if (!optimize)
 267     {
 268       /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
 269          If so record that this function can drop off the end.  */
 270
 271       insn = last_insn;
 272       {
 273         int n_labels = 1;
 274         while (insn
 275                /* One label can follow the end-note: the return label.  */
 276                && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
 277                    /* Ordinary insns can follow it if returning a structure.  */
 278                    || GET_CODE (insn) == INSN
 279                    /* If machine uses explicit RETURN insns, no epilogue,
 280                       then one of them follows the note.  */
 281                    || (GET_CODE (insn) == JUMP_INSN
 282                        && GET_CODE (PATTERN (insn)) == RETURN)
 283                    /* A barrier can follow the return insn.  */
 284                    || GET_CODE (insn) == BARRIER
 285                    /* Other kinds of notes can follow also.  */
 286                    || (GET_CODE (insn) == NOTE
 287                        && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
 288           insn = PREV_INSN (insn);
 289       }
 290
 291       /* Report if control can fall through at the end of the function.  */
 292       if (insn && GET_CODE (insn) == NOTE
 293           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END
 294           && ! INSN_DELETED_P (insn))
 295         can_reach_end = 1;
 296
 297       /* Zero the "deleted" flag of all the "deleted" insns.  */
 298       for (insn = f; insn; insn = NEXT_INSN (insn))
 299         INSN_DELETED_P (insn) = 0;
 300       return;
 301     }
 302
 303 #ifdef HAVE_return
 304   if (HAVE_return)
 305     {
 306       /* If we fall through to the epilogue, see if we can insert a RETURN insn
 307          in front of it.  If the machine allows it at this point (we might be
 308          after reload for a leaf routine), it will improve optimization for it
 309          to be there.  */
 310       insn = get_last_insn ();
 311       while (insn && GET_CODE (insn) == NOTE)
 312         insn = PREV_INSN (insn);
 313
 314       if (insn && GET_CODE (insn) != BARRIER)
 315         {
 316           emit_jump_insn (gen_return ());
 317           emit_barrier ();
 318         }
 319     }
 320 #endif
 321
 322   if (noop_moves)
 323     for (insn = f; insn; )
 324       {
 325         next = NEXT_INSN (insn);
 326
 327         if (GET_CODE (insn) == INSN)
 328           {
 329             register rtx body = PATTERN (insn);
 330
 331 /* Combine stack_adjusts with following push_insns.  */
 332 #ifdef PUSH_ROUNDING
 333             if (GET_CODE (body) == SET
 334                 && SET_DEST (body) == stack_pointer_rtx
 335                 && GET_CODE (SET_SRC (body)) == PLUS
 336                 && XEXP (SET_SRC (body), 0) == stack_pointer_rtx
 337                 && GET_CODE (XEXP (SET_SRC (body), 1)) == CONST_INT
 338                 && INTVAL (XEXP (SET_SRC (body), 1)) > 0)
 339               {
 340                 rtx p;
 341                 rtx stack_adjust_insn = insn;
 342                 int stack_adjust_amount = INTVAL (XEXP (SET_SRC (body), 1));
 343                 int total_pushed = 0;
 344                 int pushes = 0;
 345
 346                 /* Find all successive push insns.  */
 347                 p = insn;
 348                 /* Don't convert more than three pushes;
 349                    that starts adding too many displaced addresses
 350                    and the whole thing starts becoming a losing
 351                    proposition.  */
 352                 while (pushes < 3)
 353                   {
 354                     rtx pbody, dest;
 355                     p = next_nonnote_insn (p);
 356                     if (p == 0 || GET_CODE (p) != INSN)
 357                       break;
 358                     pbody = PATTERN (p);
 359                     if (GET_CODE (pbody) != SET)
 360                       break;
 361                     dest = SET_DEST (pbody);
 362                     /* Allow a no-op move between the adjust and the push.  */
 363                     if (GET_CODE (dest) == REG
 364                         && GET_CODE (SET_SRC (pbody)) == REG
 365                         && REGNO (dest) == REGNO (SET_SRC (pbody)))
 366                       continue;
 367                     if (! (GET_CODE (dest) == MEM
 368                            && GET_CODE (XEXP (dest, 0)) == POST_INC
 369                            && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
 370                       break;
 371                     pushes++;
 372                     if (total_pushed + GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)))
 373                         > stack_adjust_amount)
 374                       break;
 375                     total_pushed += GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
 376                   }
 377
 378                 /* Discard the amount pushed from the stack adjust;
 379                    maybe eliminate it entirely.  */
 380                 if (total_pushed >= stack_adjust_amount)
 381                   {
 382                     delete_computation (stack_adjust_insn);
 383                     total_pushed = stack_adjust_amount;
 384                   }
 385                 else
 386                   XEXP (SET_SRC (PATTERN (stack_adjust_insn)), 1)
 387                     = GEN_INT (stack_adjust_amount - total_pushed);
 388
 389                 /* Change the appropriate push insns to ordinary stores.  */
 390                 p = insn;
 391                 while (total_pushed > 0)
 392                   {
 393                     rtx pbody, dest;
 394                     p = next_nonnote_insn (p);
 395                     if (GET_CODE (p) != INSN)
 396                       break;
 397                     pbody = PATTERN (p);
 398                     if (GET_CODE (pbody) == SET)
 399                       break;
 400                     dest = SET_DEST (pbody);
 401                     if (! (GET_CODE (dest) == MEM
 402                            && GET_CODE (XEXP (dest, 0)) == POST_INC
 403                            && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx))
 404                       break;
 405                     total_pushed -= GET_MODE_SIZE (GET_MODE (SET_DEST (pbody)));
 406                     /* If this push doesn't fully fit in the space
 407                        of the stack adjust that we deleted,
 408                        make another stack adjust here for what we
 409                        didn't use up.  There should be peepholes
 410                        to recognize the resulting sequence of insns.  */
 411                     if (total_pushed < 0)
 412                       {
 413                         emit_insn_before (gen_add2_insn (stack_pointer_rtx,
 414                                                          GEN_INT (- total_pushed)),
 415                                           p);
 416                         break;
 417                       }
 418                     XEXP (dest, 0)
 419                       = plus_constant (stack_pointer_rtx, total_pushed);
 420                   }
 421               }
 422 #endif
 423
 424             /* Detect and delete no-op move instructions
 425                resulting from not allocating a parameter in a register.  */
 426
 427             if (GET_CODE (body) == SET
 428                 && (SET_DEST (body) == SET_SRC (body)
 429                     || (GET_CODE (SET_DEST (body)) == MEM
 430                         && GET_CODE (SET_SRC (body)) == MEM
 431                         && rtx_equal_p (SET_SRC (body), SET_DEST (body))))
 432                 && ! (GET_CODE (SET_DEST (body)) == MEM
 433                       && MEM_VOLATILE_P (SET_DEST (body)))
 434                 && ! (GET_CODE (SET_SRC (body)) == MEM
 435                       && MEM_VOLATILE_P (SET_SRC (body))))
 436               delete_computation (insn);
 437
 438             /* Detect and ignore no-op move instructions
 439                resulting from smart or fortuitous register allocation.  */
 440
 441             else if (GET_CODE (body) == SET)
 442               {
 443                 int sreg = true_regnum (SET_SRC (body));
 444                 int dreg = true_regnum (SET_DEST (body));
 445
 446                 if (sreg == dreg && sreg >= 0)
 447                   delete_insn (insn);
 448                 else if (sreg >= 0 && dreg >= 0)
 449                   {
 450                     rtx trial;
 451                     rtx tem = find_equiv_reg (NULL_RTX, insn, 0,
 452                                               sreg, NULL_PTR, dreg,
 453                                               GET_MODE (SET_SRC (body)));
 454
 455                     if (tem != 0
 456                         && GET_MODE (tem) == GET_MODE (SET_DEST (body)))
 457                       {
 458                         /* DREG may have been the target of a REG_DEAD note in
 459                            the insn which makes INSN redundant.  If so, reorg
 460                            would still think it is dead.  So search for such a
 461                            note and delete it if we find it.  */
 462                         if (! find_regno_note (insn, REG_UNUSED, dreg))
 463                           for (trial = prev_nonnote_insn (insn);
 464                                trial && GET_CODE (trial) != CODE_LABEL;
 465                                trial = prev_nonnote_insn (trial))
 466                             if (find_regno_note (trial, REG_DEAD, dreg))
 467                               {
 468                                 remove_death (dreg, trial);
 469                                 break;
 470                               }
 471 #ifdef PRESERVE_DEATH_INFO_REGNO_P
 472                         /* Deleting insn could lose a death-note for SREG
 473                            so don't do it if final needs accurate
 474                            death-notes.  */
 475                         if (PRESERVE_DEATH_INFO_REGNO_P (sreg)
 476                             && (trial = find_regno_note (insn, REG_DEAD, sreg)))
 477                           {
 478                             /* Change this into a USE so that we won't emit
 479                                code for it, but still can keep the note.  */
 480                             PATTERN (insn)
 481                               = gen_rtx_USE (VOIDmode, XEXP (trial, 0));
 482                             INSN_CODE (insn) = -1;
 483                             /* Remove all reg notes but the REG_DEAD one.  */
 484                             REG_NOTES (insn) = trial;
 485                             XEXP (trial, 1) = NULL_RTX;
 486                           }
 487                         else
 488 #endif
 489                           delete_insn (insn);
 490                       }
 491                   }
 492                 else if (dreg >= 0 && CONSTANT_P (SET_SRC (body))
 493                          && find_equiv_reg (SET_SRC (body), insn, 0, dreg,
 494                                             NULL_PTR, 0,
 495                                             GET_MODE (SET_DEST (body))))
 496                   {
 497                     /* This handles the case where we have two consecutive
 498                        assignments of the same constant to pseudos that didn't
 499                        get a hard reg.  Each SET from the constant will be
 500                        converted into a SET of the spill register and an
 501                        output reload will be made following it.  This produces
 502                        two loads of the same constant into the same spill
 503                        register.  */
 504
 505                     rtx in_insn = insn;
 506
 507                     /* Look back for a death note for the first reg.
 508                        If there is one, it is no longer accurate.  */
 509                     while (in_insn && GET_CODE (in_insn) != CODE_LABEL)
 510                       {
 511                         if ((GET_CODE (in_insn) == INSN
 512                              || GET_CODE (in_insn) == JUMP_INSN)
 513                             && find_regno_note (in_insn, REG_DEAD, dreg))
 514                           {
 515                             remove_death (dreg, in_insn);
 516                             break;
 517                           }
 518                         in_insn = PREV_INSN (in_insn);
 519                       }
 520
 521                     /* Delete the second load of the value.  */
 522                     delete_insn (insn);
 523                   }
 524               }
 525             else if (GET_CODE (body) == PARALLEL)
 526               {
 527                 /* If each part is a set between two identical registers or
 528                    a USE or CLOBBER, delete the insn.  */
 529                 int i, sreg, dreg;
 530                 rtx tem;
 531
 532                 for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
 533                   {
 534                     tem = XVECEXP (body, 0, i);
 535                     if (GET_CODE (tem) == USE || GET_CODE (tem) == CLOBBER)
 536                       continue;
 537
 538                     if (GET_CODE (tem) != SET
 539                         || (sreg = true_regnum (SET_SRC (tem))) < 0
 540                         || (dreg = true_regnum (SET_DEST (tem))) < 0
 541                         || dreg != sreg)
 542                       break;
 543                   }
 544
 545                 if (i < 0)
 546                   delete_insn (insn);
 547               }
 548             /* Also delete insns to store bit fields if they are no-ops.  */
 549             /* Not worth the hair to detect this in the big-endian case.  */
 550             else if (! BYTES_BIG_ENDIAN
 551                      && GET_CODE (body) == SET
 552                      && GET_CODE (SET_DEST (body)) == ZERO_EXTRACT
 553                      && XEXP (SET_DEST (body), 2) == const0_rtx
 554                      && XEXP (SET_DEST (body), 0) == SET_SRC (body)
 555                      && ! (GET_CODE (SET_SRC (body)) == MEM
 556                            && MEM_VOLATILE_P (SET_SRC (body))))
 557               delete_insn (insn);
 558           }
 559       insn = next;
 560     }
 561
 562   /* If we haven't yet gotten to reload and we have just run regscan,
 563      delete any insn that sets a register that isn't used elsewhere.
 564      This helps some of the optimizations below by having less insns
 565      being jumped around.  */
 566
 567   if (! reload_completed && after_regscan)
 568     for (insn = f; insn; insn = next)
 569       {
 570         rtx set = single_set (insn);
 571
 572         next = NEXT_INSN (insn);
 573
 574         if (set && GET_CODE (SET_DEST (set)) == REG
 575             && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
 576             && REGNO_FIRST_UID (REGNO (SET_DEST (set))) == INSN_UID (insn)
 577             /* We use regno_last_note_uid so as not to delete the setting
 578                of a reg that's used in notes.  A subsequent optimization
 579                might arrange to use that reg for real.  */
 580             && REGNO_LAST_NOTE_UID (REGNO (SET_DEST (set))) == INSN_UID (insn)
 581             && ! side_effects_p (SET_SRC (set))
 582             && ! find_reg_note (insn, REG_RETVAL, 0))
 583           delete_insn (insn);
 584       }
 585
 586   /* Now iterate optimizing jumps until nothing changes over one pass.  */
 587   changed = 1;
 588   while (changed)
 589     {
 590       changed = 0;
 591
 592       for (insn = f; insn; insn = next)
 593         {
 594           rtx reallabelprev;
 595           rtx temp, temp1, temp2, temp3, temp4, temp5, temp6;
 596           rtx nlabel;
 597           int this_is_simplejump, this_is_condjump, reversep;
 598           int this_is_condjump_in_parallel;
 599 #if 0
 600           /* If NOT the first iteration, if this is the last jump pass
 601              (just before final), do the special peephole optimizations.
 602              Avoiding the first iteration gives ordinary jump opts
 603              a chance to work before peephole opts.  */
 604
 605           if (reload_completed && !first && !flag_no_peephole)
 606             if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
 607               peephole (insn);
 608 #endif
 609
 610           /* That could have deleted some insns after INSN, so check now
 611              what the following insn is.  */
 612
 613           next = NEXT_INSN (insn);
 614
 615           /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
 616              jump.  Try to optimize by duplicating the loop exit test if so.
 617              This is only safe immediately after regscan, because it uses
 618              the values of regno_first_uid and regno_last_uid.  */
 619           if (after_regscan && GET_CODE (insn) == NOTE
 620               && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
 621               && (temp1 = next_nonnote_insn (insn)) != 0
 622               && simplejump_p (temp1))
 623             {
 624               temp = PREV_INSN (insn);
 625               if (duplicate_loop_exit_test (insn))
 626                 {
 627                   changed = 1;
 628                   next = NEXT_INSN (temp);
 629                   continue;
 630                 }
 631             }
 632
 633           if (GET_CODE (insn) != JUMP_INSN)
 634             continue;
 635
 636           this_is_simplejump = simplejump_p (insn);
 637           this_is_condjump = condjump_p (insn);
 638           this_is_condjump_in_parallel = condjump_in_parallel_p (insn);
 639
 640           /* Tension the labels in dispatch tables.  */
 641
 642           if (GET_CODE (PATTERN (insn)) == ADDR_VEC)
 643             changed |= tension_vector_labels (PATTERN (insn), 0);
 644           if (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 645             changed |= tension_vector_labels (PATTERN (insn), 1);
 646
 647           /* If a dispatch table always goes to the same place,
 648              get rid of it and replace the insn that uses it.  */
 649
 650           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
 651               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
 652             {
 653               int i;
 654               rtx pat = PATTERN (insn);
 655               int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
 656               int len = XVECLEN (pat, diff_vec_p);
 657               rtx dispatch = prev_real_insn (insn);
 658
 659               for (i = 0; i < len; i++)
 660                 if (XEXP (XVECEXP (pat, diff_vec_p, i), 0)
 661                     != XEXP (XVECEXP (pat, diff_vec_p, 0), 0))
 662                   break;
 663               if (i == len
 664                   && dispatch != 0
 665                   && GET_CODE (dispatch) == JUMP_INSN
 666                   && JUMP_LABEL (dispatch) != 0
 667                   /* Don't mess with a casesi insn.  */
 668                   && !(GET_CODE (PATTERN (dispatch)) == SET
 669                        && (GET_CODE (SET_SRC (PATTERN (dispatch)))
 670                            == IF_THEN_ELSE))
 671                   && next_real_insn (JUMP_LABEL (dispatch)) == insn)
 672                 {
 673                   redirect_tablejump (dispatch,
 674                                       XEXP (XVECEXP (pat, diff_vec_p, 0), 0));
 675                   changed = 1;
 676                 }
 677             }
 678
 679           reallabelprev = prev_active_insn (JUMP_LABEL (insn));
 680
 681           /* If a jump references the end of the function, try to turn
 682              it into a RETURN insn, possibly a conditional one.  */
 683           if (JUMP_LABEL (insn)
 684               && (next_active_insn (JUMP_LABEL (insn)) == 0
 685                   || GET_CODE (PATTERN (next_active_insn (JUMP_LABEL (insn))))
 686                       == RETURN))
 687             changed |= redirect_jump (insn, NULL_RTX);
 688
 689           /* Detect jump to following insn.  */
 690           if (reallabelprev == insn && condjump_p (insn))
 691             {
 692               next = next_real_insn (JUMP_LABEL (insn));
 693               delete_jump (insn);
 694               changed = 1;
 695               continue;
 696             }
 697
 698           /* If we have an unconditional jump preceded by a USE, try to put
 699              the USE before the target and jump there.  This simplifies many
 700              of the optimizations below since we don't have to worry about
 701              dealing with these USE insns.  We only do this if the label
 702              being branch to already has the identical USE or if code
 703              never falls through to that label.  */
 704
 705           if (this_is_simplejump
 706               && (temp = prev_nonnote_insn (insn)) != 0
 707               && GET_CODE (temp) == INSN && GET_CODE (PATTERN (temp)) == USE
 708               && (temp1 = prev_nonnote_insn (JUMP_LABEL (insn))) != 0
 709               && (GET_CODE (temp1) == BARRIER
 710                   || (GET_CODE (temp1) == INSN
 711                       && rtx_equal_p (PATTERN (temp), PATTERN (temp1))))
 712               /* Don't do this optimization if we have a loop containing only
 713                  the USE instruction, and the loop start label has a usage
 714                  count of 1.  This is because we will redo this optimization
 715                  everytime through the outer loop, and jump opt will never
 716                  exit.  */
 717               && ! ((temp2 = prev_nonnote_insn (temp)) != 0
 718                     && temp2 == JUMP_LABEL (insn)
 719                     && LABEL_NUSES (temp2) == 1))
 720             {
 721               if (GET_CODE (temp1) == BARRIER)
 722                 {
 723                   emit_insn_after (PATTERN (temp), temp1);
 724                   temp1 = NEXT_INSN (temp1);
 725                 }
 726
 727               delete_insn (temp);
 728               redirect_jump (insn, get_label_before (temp1));
 729               reallabelprev = prev_real_insn (temp1);
 730               changed = 1;
 731             }
 732
 733           /* Simplify   if (...) x = a; else x = b; by converting it
 734              to         x = b; if (...) x = a;
 735              if B is sufficiently simple, the test doesn't involve X,
 736              and nothing in the test modifies B or X.
 737
 738              If we have small register classes, we also can't do this if X
 739              is a hard register.
 740
 741              If the "x = b;" insn has any REG_NOTES, we don't do this because
 742              of the possibility that we are running after CSE and there is a
 743              REG_EQUAL note that is only valid if the branch has already been
 744              taken.  If we move the insn with the REG_EQUAL note, we may
 745              fold the comparison to always be false in a later CSE pass.
 746              (We could also delete the REG_NOTES when moving the insn, but it
 747              seems simpler to not move it.)  An exception is that we can move
 748              the insn if the only note is a REG_EQUAL or REG_EQUIV whose
 749              value is the same as "b".
 750
 751              INSN is the branch over the `else' part.
 752
 753              We set:
 754
 755              TEMP to the jump insn preceding "x = a;"
 756              TEMP1 to X
 757              TEMP2 to the insn that sets "x = b;"
 758              TEMP3 to the insn that sets "x = a;"
 759              TEMP4 to the set of "x = b";  */
 760
 761           if (this_is_simplejump
 762               && (temp3 = prev_active_insn (insn)) != 0
 763               && GET_CODE (temp3) == INSN
 764               && (temp4 = single_set (temp3)) != 0
 765               && GET_CODE (temp1 = SET_DEST (temp4)) == REG
 766               && (! SMALL_REGISTER_CLASSES
 767                   || REGNO (temp1) >= FIRST_PSEUDO_REGISTER)
 768               && (temp2 = next_active_insn (insn)) != 0
 769               && GET_CODE (temp2) == INSN
 770               && (temp4 = single_set (temp2)) != 0
 771               && rtx_equal_p (SET_DEST (temp4), temp1)
 772               && (GET_CODE (SET_SRC (temp4)) == REG
 773                   || GET_CODE (SET_SRC (temp4)) == SUBREG
 774                   || (GET_CODE (SET_SRC (temp4)) == MEM
 775                       && RTX_UNCHANGING_P (SET_SRC (temp4)))
 776                   || CONSTANT_P (SET_SRC (temp4)))
 777               && (REG_NOTES (temp2) == 0
 778                   || ((REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUAL
 779                        || REG_NOTE_KIND (REG_NOTES (temp2)) == REG_EQUIV)
 780                       && XEXP (REG_NOTES (temp2), 1) == 0
 781                       && rtx_equal_p (XEXP (REG_NOTES (temp2), 0),
 782                                       SET_SRC (temp4))))
 783               && (temp = prev_active_insn (temp3)) != 0
 784               && condjump_p (temp) && ! simplejump_p (temp)
 785               /* TEMP must skip over the "x = a;" insn */
 786               && prev_real_insn (JUMP_LABEL (temp)) == insn
 787               && no_labels_between_p (insn, JUMP_LABEL (temp))
 788               /* There must be no other entries to the "x = b;" insn.  */
 789               && no_labels_between_p (JUMP_LABEL (temp), temp2)
 790               /* INSN must either branch to the insn after TEMP2 or the insn
 791                  after TEMP2 must branch to the same place as INSN.  */
 792               && (reallabelprev == temp2
 793                   || ((temp5 = next_active_insn (temp2)) != 0
 794                       && simplejump_p (temp5)
 795                       && JUMP_LABEL (temp5) == JUMP_LABEL (insn))))
 796             {
 797               /* The test expression, X, may be a complicated test with
 798                  multiple branches.  See if we can find all the uses of
 799                  the label that TEMP branches to without hitting a CALL_INSN
 800                  or a jump to somewhere else.  */
 801               rtx target = JUMP_LABEL (temp);
 802               int nuses = LABEL_NUSES (target);
 803               rtx p;
 804 #ifdef HAVE_cc0
 805               rtx q;
 806 #endif
 807
 808               /* Set P to the first jump insn that goes around "x = a;".  */
 809               for (p = temp; nuses && p; p = prev_nonnote_insn (p))
 810                 {
 811                   if (GET_CODE (p) == JUMP_INSN)
 812                     {
 813                       if (condjump_p (p) && ! simplejump_p (p)
 814                           && JUMP_LABEL (p) == target)
 815                         {
 816                           nuses--;
 817                           if (nuses == 0)
 818                             break;
 819                         }
 820                       else
 821                         break;
 822                     }
 823                   else if (GET_CODE (p) == CALL_INSN)
 824                     break;
 825                 }
 826
 827 #ifdef HAVE_cc0
 828               /* We cannot insert anything between a set of cc and its use
 829                  so if P uses cc0, we must back up to the previous insn.  */
 830               q = prev_nonnote_insn (p);
 831               if (q && GET_RTX_CLASS (GET_CODE (q)) == 'i'
 832                   && sets_cc0_p (PATTERN (q)))
 833                 p = q;
 834 #endif
 835
 836               if (p)
 837                 p = PREV_INSN (p);
 838
 839               /* If we found all the uses and there was no data conflict, we
 840                  can move the assignment unless we can branch into the middle
 841                  from somewhere.  */
 842               if (nuses == 0 && p
 843                   && no_labels_between_p (p, insn)
 844                   && ! reg_referenced_between_p (temp1, p, NEXT_INSN (temp3))
 845                   && ! reg_set_between_p (temp1, p, temp3)
 846                   && (GET_CODE (SET_SRC (temp4)) == CONST_INT
 847                       || ! reg_set_between_p (SET_SRC (temp4), p, temp2)))
 848                 {
 849                   emit_insn_after_with_line_notes (PATTERN (temp2), p, temp2);
 850                   delete_insn (temp2);
 851
 852                   /* Set NEXT to an insn that we know won't go away.  */
 853                   next = next_active_insn (insn);
 854
 855                   /* Delete the jump around the set.  Note that we must do
 856                      this before we redirect the test jumps so that it won't
 857                      delete the code immediately following the assignment
 858                      we moved (which might be a jump).  */
 859
 860                   delete_insn (insn);
 861
 862                   /* We either have two consecutive labels or a jump to
 863                      a jump, so adjust all the JUMP_INSNs to branch to where
 864                      INSN branches to.  */
 865                   for (p = NEXT_INSN (p); p != next; p = NEXT_INSN (p))
 866                     if (GET_CODE (p) == JUMP_INSN)
 867                       redirect_jump (p, target);
 868
 869                   changed = 1;
 870                   continue;
 871                 }
 872             }
 873
 874           /* Simplify   if (...) { x = a; goto l; } x = b; by converting it
 875              to         x = a; if (...) goto l; x = b;
 876              if A is sufficiently simple, the test doesn't involve X,
 877              and nothing in the test modifies A or X.
 878
 879              If we have small register classes, we also can't do this if X
 880              is a hard register.
 881
 882              If the "x = a;" insn has any REG_NOTES, we don't do this because
 883              of the possibility that we are running after CSE and there is a
 884              REG_EQUAL note that is only valid if the branch has already been
 885              taken.  If we move the insn with the REG_EQUAL note, we may
 886              fold the comparison to always be false in a later CSE pass.
 887              (We could also delete the REG_NOTES when moving the insn, but it
 888              seems simpler to not move it.)  An exception is that we can move
 889              the insn if the only note is a REG_EQUAL or REG_EQUIV whose
 890              value is the same as "a".
 891
 892              INSN is the goto.
 893
 894              We set:
 895
 896              TEMP to the jump insn preceding "x = a;"
 897              TEMP1 to X
 898              TEMP2 to the insn that sets "x = b;"
 899              TEMP3 to the insn that sets "x = a;"
 900              TEMP4 to the set of "x = a";  */
 901
 902           if (this_is_simplejump
 903               && (temp2 = next_active_insn (insn)) != 0
 904               && GET_CODE (temp2) == INSN
 905               && (temp4 = single_set (temp2)) != 0
 906               && GET_CODE (temp1 = SET_DEST (temp4)) == REG
 907               && (! SMALL_REGISTER_CLASSES
 908                   || REGNO (temp1) >= FIRST_PSEUDO_REGISTER)
 909               && (temp3 = prev_active_insn (insn)) != 0
 910               && GET_CODE (temp3) == INSN
 911               && (temp4 = single_set (temp3)) != 0
 912               && rtx_equal_p (SET_DEST (temp4), temp1)
 913               && (GET_CODE (SET_SRC (temp4)) == REG
 914                   || GET_CODE (SET_SRC (temp4)) == SUBREG
 915                   || (GET_CODE (SET_SRC (temp4)) == MEM
 916                       && RTX_UNCHANGING_P (SET_SRC (temp4)))
 917                   || CONSTANT_P (SET_SRC (temp4)))
 918               && (REG_NOTES (temp3) == 0
 919                   || ((REG_NOTE_KIND (REG_NOTES (temp3)) == REG_EQUAL
 920                        || REG_NOTE_KIND (REG_NOTES (temp3)) == REG_EQUIV)
 921                       && XEXP (REG_NOTES (temp3), 1) == 0
 922                       && rtx_equal_p (XEXP (REG_NOTES (temp3), 0),
 923                                       SET_SRC (temp4))))
 924               && (temp = prev_active_insn (temp3)) != 0
 925               && condjump_p (temp) && ! simplejump_p (temp)
 926               /* TEMP must skip over the "x = a;" insn */
 927               && prev_real_insn (JUMP_LABEL (temp)) == insn
 928               && no_labels_between_p (temp, insn))
 929             {
 930               rtx prev_label = JUMP_LABEL (temp);
 931               rtx insert_after = prev_nonnote_insn (temp);
 932
 933 #ifdef HAVE_cc0
 934               /* We cannot insert anything between a set of cc and its use.  */
 935               if (insert_after && GET_RTX_CLASS (GET_CODE (insert_after)) == 'i'
 936                   && sets_cc0_p (PATTERN (insert_after)))
 937                 insert_after = prev_nonnote_insn (insert_after);
 938 #endif
 939               ++LABEL_NUSES (prev_label);
 940
 941               if (insert_after
 942                   && no_labels_between_p (insert_after, temp)
 943                   && ! reg_referenced_between_p (temp1, insert_after, temp3)
 944                   && ! reg_referenced_between_p (temp1, temp3,
 945                                                  NEXT_INSN (temp2))
 946                   && ! reg_set_between_p (temp1, insert_after, temp)
 947                   && (GET_CODE (SET_SRC (temp4)) == CONST_INT
 948                       || ! reg_set_between_p (SET_SRC (temp4),
 949                                               insert_after, temp))
 950                   && invert_jump (temp, JUMP_LABEL (insn)))
 951                 {
 952                   emit_insn_after_with_line_notes (PATTERN (temp3),
 953                                                    insert_after, temp3);
 954                   delete_insn (temp3);
 955                   delete_insn (insn);
 956                   /* Set NEXT to an insn that we know won't go away.  */
 957                   next = temp2;
 958                   changed = 1;
 959                 }
 960               if (prev_label && --LABEL_NUSES (prev_label) == 0)
 961                 delete_insn (prev_label);
 962               if (changed)
 963                 continue;
 964             }
 965
 966 #ifndef HAVE_cc0
 967           /* If we have if (...) x = exp;  and branches are expensive,
 968              EXP is a single insn, does not have any side effects, cannot
 969              trap, and is not too costly, convert this to
 970              t = exp; if (...) x = t;
 971
 972              Don't do this when we have CC0 because it is unlikely to help
 973              and we'd need to worry about where to place the new insn and
 974              the potential for conflicts.  We also can't do this when we have
 975              notes on the insn for the same reason as above.
 976
 977              We set:
 978
 979              TEMP to the "x = exp;" insn.
 980              TEMP1 to the single set in the "x = exp; insn.
 981              TEMP2 to "x".  */
 982
 983           if (! reload_completed
 984               && this_is_condjump && ! this_is_simplejump
 985               && BRANCH_COST >= 3
 986               && (temp = next_nonnote_insn (insn)) != 0
 987               && GET_CODE (temp) == INSN
 988               && REG_NOTES (temp) == 0
 989               && (reallabelprev == temp
 990                   || ((temp2 = next_active_insn (temp)) != 0
 991                       && simplejump_p (temp2)
 992                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
 993               && (temp1 = single_set (temp)) != 0
 994               && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
 995               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
 996               && (! SMALL_REGISTER_CLASSES
 997                   || REGNO (temp2) >= FIRST_PSEUDO_REGISTER)
 998               && GET_CODE (SET_SRC (temp1)) != REG
 999               && GET_CODE (SET_SRC (temp1)) != SUBREG
1000               && GET_CODE (SET_SRC (temp1)) != CONST_INT
1001               && ! side_effects_p (SET_SRC (temp1))
1002               && ! may_trap_p (SET_SRC (temp1))
1003               && rtx_cost (SET_SRC (temp1), SET) < 10)
1004             {
1005               rtx new = gen_reg_rtx (GET_MODE (temp2));
1006
1007               if ((temp3 = find_insert_position (insn, temp))
1008                   && validate_change (temp, &SET_DEST (temp1), new, 0))
1009                 {
1010                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
1011                   emit_insn_after_with_line_notes (PATTERN (temp),
1012                                                    PREV_INSN (temp3), temp);
1013                   delete_insn (temp);
1014                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
1015                 }
1016             }
1017
1018           /* Similarly, if it takes two insns to compute EXP but they
1019              have the same destination.  Here TEMP3 will be the second
1020              insn and TEMP4 the SET from that insn.  */
1021
1022           if (! reload_completed
1023               && this_is_condjump && ! this_is_simplejump
1024               && BRANCH_COST >= 4
1025               && (temp = next_nonnote_insn (insn)) != 0
1026               && GET_CODE (temp) == INSN
1027               && REG_NOTES (temp) == 0
1028               && (temp3 = next_nonnote_insn (temp)) != 0
1029               && GET_CODE (temp3) == INSN
1030               && REG_NOTES (temp3) == 0
1031               && (reallabelprev == temp3
1032                   || ((temp2 = next_active_insn (temp3)) != 0
1033                       && simplejump_p (temp2)
1034                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
1035               && (temp1 = single_set (temp)) != 0
1036               && (temp2 = SET_DEST (temp1), GET_CODE (temp2) == REG)
1037               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
1038               && (! SMALL_REGISTER_CLASSES
1039                   || REGNO (temp2) >= FIRST_PSEUDO_REGISTER)
1040               && ! side_effects_p (SET_SRC (temp1))
1041               && ! may_trap_p (SET_SRC (temp1))
1042               && rtx_cost (SET_SRC (temp1), SET) < 10
1043               && (temp4 = single_set (temp3)) != 0
1044               && rtx_equal_p (SET_DEST (temp4), temp2)
1045               && ! side_effects_p (SET_SRC (temp4))
1046               && ! may_trap_p (SET_SRC (temp4))
1047               && rtx_cost (SET_SRC (temp4), SET) < 10)
1048             {
1049               rtx new = gen_reg_rtx (GET_MODE (temp2));
1050
1051               if ((temp5 = find_insert_position (insn, temp))
1052                   && (temp6 = find_insert_position (insn, temp3))
1053                   && validate_change (temp, &SET_DEST (temp1), new, 0))
1054                 {
1055                   /* Use the earliest of temp5 and temp6. */
1056                   if (temp5 != insn)
1057                     temp6 = temp5;
1058                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
1059                   emit_insn_after_with_line_notes (PATTERN (temp),
1060                                                    PREV_INSN (temp6), temp);
1061                   emit_insn_after_with_line_notes
1062                     (replace_rtx (PATTERN (temp3), temp2, new),
1063                      PREV_INSN (temp6), temp3);
1064                   delete_insn (temp);
1065                   delete_insn (temp3);
1066                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
1067                 }
1068             }
1069
1070           /* Finally, handle the case where two insns are used to
1071              compute EXP but a temporary register is used.  Here we must
1072              ensure that the temporary register is not used anywhere else.  */
1073
1074           if (! reload_completed
1075               && after_regscan
1076               && this_is_condjump && ! this_is_simplejump
1077               && BRANCH_COST >= 4
1078               && (temp = next_nonnote_insn (insn)) != 0
1079               && GET_CODE (temp) == INSN
1080               && REG_NOTES (temp) == 0
1081               && (temp3 = next_nonnote_insn (temp)) != 0
1082               && GET_CODE (temp3) == INSN
1083               && REG_NOTES (temp3) == 0
1084               && (reallabelprev == temp3
1085                   || ((temp2 = next_active_insn (temp3)) != 0
1086                       && simplejump_p (temp2)
1087                       && JUMP_LABEL (temp2) == JUMP_LABEL (insn)))
1088               && (temp1 = single_set (temp)) != 0
1089               && (temp5 = SET_DEST (temp1),
1090                   (GET_CODE (temp5) == REG
1091                    || (GET_CODE (temp5) == SUBREG
1092                        && (temp5 = SUBREG_REG (temp5),
1093                            GET_CODE (temp5) == REG))))
1094               && REGNO (temp5) >= FIRST_PSEUDO_REGISTER
1095               && REGNO_FIRST_UID (REGNO (temp5)) == INSN_UID (temp)
1096               && REGNO_LAST_UID (REGNO (temp5)) == INSN_UID (temp3)
1097               && ! side_effects_p (SET_SRC (temp1))
1098               && ! may_trap_p (SET_SRC (temp1))
1099               && rtx_cost (SET_SRC (temp1), SET) < 10
1100               && (temp4 = single_set (temp3)) != 0
1101               && (temp2 = SET_DEST (temp4), GET_CODE (temp2) == REG)
1102               && GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT
1103               && (! SMALL_REGISTER_CLASSES
1104                   || REGNO (temp2) >= FIRST_PSEUDO_REGISTER)
1105               && rtx_equal_p (SET_DEST (temp4), temp2)
1106               && ! side_effects_p (SET_SRC (temp4))
1107               && ! may_trap_p (SET_SRC (temp4))
1108               && rtx_cost (SET_SRC (temp4), SET) < 10)
1109             {
1110               rtx new = gen_reg_rtx (GET_MODE (temp2));
1111
1112               if ((temp5 = find_insert_position (insn, temp))
1113                   && (temp6 = find_insert_position (insn, temp3))
1114                   && validate_change (temp3, &SET_DEST (temp4), new, 0))
1115                 {
1116                   /* Use the earliest of temp5 and temp6. */
1117                   if (temp5 != insn)
1118                     temp6 = temp5;
1119                   next = emit_insn_after (gen_move_insn (temp2, new), insn);
1120                   emit_insn_after_with_line_notes (PATTERN (temp),
1121                                                    PREV_INSN (temp6), temp);
1122                   emit_insn_after_with_line_notes (PATTERN (temp3),
1123                                                    PREV_INSN (temp6), temp3);
1124                   delete_insn (temp);
1125                   delete_insn (temp3);
1126                   reallabelprev = prev_active_insn (JUMP_LABEL (insn));
1127                 }
1128             }
1129 #endif /* HAVE_cc0 */
1130
1131           /* Try to use a conditional move (if the target has them), or a
1132              store-flag insn.  The general case is:
1133
1134              1) x = a; if (...) x = b; and
1135              2) if (...) x = b;
1136
1137              If the jump would be faster, the machine should not have defined
1138              the movcc or scc insns!.  These cases are often made by the
1139              previous optimization.
1140
1141              The second case is treated as  x = x; if (...) x = b;.
1142
1143              INSN here is the jump around the store.  We set:
1144
1145              TEMP to the "x = b;" insn.
1146              TEMP1 to X.
1147              TEMP2 to B.
1148              TEMP3 to A (X in the second case).
1149              TEMP4 to the condition being tested.
1150              TEMP5 to the earliest insn used to find the condition.  */
1151
1152           if (/* We can't do this after reload has completed.  */
1153               ! reload_completed
1154               && this_is_condjump && ! this_is_simplejump
1155               /* Set TEMP to the "x = b;" insn.  */
1156               && (temp = next_nonnote_insn (insn)) != 0
1157               && GET_CODE (temp) == INSN
1158               && GET_CODE (PATTERN (temp)) == SET
1159               && GET_CODE (temp1 = SET_DEST (PATTERN (temp))) == REG
1160               && (! SMALL_REGISTER_CLASSES
1161                   || REGNO (temp1) >= FIRST_PSEUDO_REGISTER)
1162               && (GET_CODE (temp2 = SET_SRC (PATTERN (temp))) == REG
1163                   || (GET_CODE (temp2) == MEM && RTX_UNCHANGING_P (temp2))
1164                   || GET_CODE (temp2) == SUBREG
1165                   /* ??? How about floating point constants?  */
1166                   || CONSTANT_P (temp2))
1167               /* Allow either form, but prefer the former if both apply.
1168                  There is no point in using the old value of TEMP1 if
1169                  it is a register, since cse will alias them.  It can
1170                  lose if the old value were a hard register since CSE
1171                  won't replace hard registers.  Avoid using TEMP3 if
1172                  small register classes and it is a hard register.  */
1173               && (((temp3 = reg_set_last (temp1, insn)) != 0
1174                    && ! (SMALL_REGISTER_CLASSES && GET_CODE (temp3) == REG
1175                          && REGNO (temp3) < FIRST_PSEUDO_REGISTER))
1176                   /* Make the latter case look like  x = x; if (...) x = b;  */
1177                   || (temp3 = temp1, 1))
1178               /* INSN must either branch to the insn after TEMP or the insn
1179                  after TEMP must branch to the same place as INSN.  */
1180               && (reallabelprev == temp
1181                   || ((temp4 = next_active_insn (temp)) != 0
1182                       && simplejump_p (temp4)
1183                       && JUMP_LABEL (temp4) == JUMP_LABEL (insn)))
1184               && (temp4 = get_condition (insn, &temp5)) != 0
1185               /* We must be comparing objects whose modes imply the size.
1186                  We could handle BLKmode if (1) emit_store_flag could
1187                  and (2) we could find the size reliably.  */
1188               && GET_MODE (XEXP (temp4, 0)) != BLKmode
1189               /* Even if branches are cheap, the store_flag optimization
1190                  can win when the operation to be performed can be
1191                  expressed directly.  */
1192 #ifdef HAVE_cc0
1193               /* If the previous insn sets CC0 and something else, we can't
1194                  do this since we are going to delete that insn.  */
1195
1196               && ! ((temp6 = prev_nonnote_insn (insn)) != 0
1197                     && GET_CODE (temp6) == INSN
1198                     && (sets_cc0_p (PATTERN (temp6)) == -1
1199                         || (sets_cc0_p (PATTERN (temp6)) == 1
1200                             && FIND_REG_INC_NOTE (temp6, NULL_RTX))))
1201 #endif
1202               )
1203             {
1204 #ifdef HAVE_conditional_move
1205               /* First try a conditional move.  */
1206               {
1207                 enum rtx_code code = GET_CODE (temp4);
1208                 rtx var = temp1;
1209                 rtx cond0, cond1, aval, bval;
1210                 rtx target;
1211
1212                 /* Copy the compared variables into cond0 and cond1, so that
1213                    any side effects performed in or after the old comparison,
1214                    will not affect our compare which will come later.  */
1215                 /* ??? Is it possible to just use the comparison in the jump
1216                    insn?  After all, we're going to delete it.  We'd have
1217                    to modify emit_conditional_move to take a comparison rtx
1218                    instead or write a new function.  */
1219                 cond0 = gen_reg_rtx (GET_MODE (XEXP (temp4, 0)));
1220                 /* We want the target to be able to simplify comparisons with
1221                    zero (and maybe other constants as well), so don't create
1222                    pseudos for them.  There's no need to either.  */
1223                 if (GET_CODE (XEXP (temp4, 1)) == CONST_INT
1224                     || GET_CODE (XEXP (temp4, 1)) == CONST_DOUBLE)
1225                   cond1 = XEXP (temp4, 1);
1226                 else
1227                   cond1 = gen_reg_rtx (GET_MODE (XEXP (temp4, 1)));
1228
1229                 aval = temp3;
1230                 bval = temp2;
1231
1232                 start_sequence ();
1233                 target = emit_conditional_move (var, code,
1234                                                 cond0, cond1, VOIDmode,
1235                                                 aval, bval, GET_MODE (var),
1236                                                 (code == LTU || code == GEU
1237                                                  || code == LEU || code == GTU));
1238
1239                 if (target)
1240                   {
1241                     rtx seq1,seq2;
1242
1243                     /* Save the conditional move sequence but don't emit it
1244                        yet.  On some machines, like the alpha, it is possible
1245                        that temp5 == insn, so next generate the sequence that
1246                        saves the compared values and then emit both
1247                        sequences ensuring seq1 occurs before seq2.  */
1248                     seq2 = get_insns ();
1249                     end_sequence ();
1250
1251                     /* Now that we can't fail, generate the copy insns that
1252                        preserve the compared values.  */
1253                     start_sequence ();
1254                     emit_move_insn (cond0, XEXP (temp4, 0));
1255                     if (cond1 != XEXP (temp4, 1))
1256                       emit_move_insn (cond1, XEXP (temp4, 1));
1257                     seq1 = get_insns ();
1258                     end_sequence ();
1259
1260                     emit_insns_before (seq1, temp5);
1261                     /* Insert conditional move after insn, to be sure that
1262                        the jump and a possible compare won't be separated */
1263                     emit_insns_after (seq2, insn);
1264
1265                     /* ??? We can also delete the insn that sets X to A.
1266                        Flow will do it too though.  */
1267                     delete_insn (temp);
1268                     next = NEXT_INSN (insn);
1269                     delete_jump (insn);
1270                     changed = 1;
1271                     continue;
1272                   }
1273                 else
1274                   end_sequence ();
1275               }
1276 #endif
1277
1278               /* That didn't work, try a store-flag insn.
1279
1280                  We further divide the cases into:
1281
1282                  1) x = a; if (...) x = b; and either A or B is zero,
1283                  2) if (...) x = 0; and jumps are expensive,
1284                  3) x = a; if (...) x = b; and A and B are constants where all
1285                  the set bits in A are also set in B and jumps are expensive,
1286                  4) x = a; if (...) x = b; and A and B non-zero, and jumps are
1287                  more expensive, and
1288                  5) if (...) x = b; if jumps are even more expensive.  */
1289
1290               if (GET_MODE_CLASS (GET_MODE (temp1)) == MODE_INT
1291                   && ((GET_CODE (temp3) == CONST_INT)
1292                       /* Make the latter case look like
1293                          x = x; if (...) x = 0;  */
1294                       || (temp3 = temp1,
1295                           ((BRANCH_COST >= 2
1296                             && temp2 == const0_rtx)
1297                            || BRANCH_COST >= 3)))
1298                   /* If B is zero, OK; if A is zero, can only do (1) if we
1299                      can reverse the condition.  See if (3) applies possibly
1300                      by reversing the condition.  Prefer reversing to (4) when
1301                      branches are very expensive.  */
1302                   && (((BRANCH_COST >= 2
1303                         || STORE_FLAG_VALUE == -1
1304                         || (STORE_FLAG_VALUE == 1
1305                          /* Check that the mask is a power of two,
1306                             so that it can probably be generated
1307                             with a shift.  */
1308                             && exact_log2 (INTVAL (temp3)) >= 0))
1309                        && (reversep = 0, temp2 == const0_rtx))
1310                       || ((BRANCH_COST >= 2
1311                            || STORE_FLAG_VALUE == -1
1312                            || (STORE_FLAG_VALUE == 1
1313                                && exact_log2 (INTVAL (temp2)) >= 0))
1314                           && temp3 == const0_rtx
1315                           && (reversep = can_reverse_comparison_p (temp4, insn)))
1316                       || (BRANCH_COST >= 2
1317                           && GET_CODE (temp2) == CONST_INT
1318                           && GET_CODE (temp3) == CONST_INT
1319                           && ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp2)
1320                               || ((INTVAL (temp2) & INTVAL (temp3)) == INTVAL (temp3)
1321                                   && (reversep = can_reverse_comparison_p (temp4,
1322                                                                            insn)))))
1323                       || BRANCH_COST >= 3)
1324                   )
1325                 {
1326                   enum rtx_code code = GET_CODE (temp4);
1327                   rtx uval, cval, var = temp1;
1328                   int normalizep;
1329                   rtx target;
1330
1331                   /* If necessary, reverse the condition.  */
1332                   if (reversep)
1333                     code = reverse_condition (code), uval = temp2, cval = temp3;
1334                   else
1335                     uval = temp3, cval = temp2;
1336
1337                   /* If CVAL is non-zero, normalize to -1.  Otherwise, if UVAL
1338                      is the constant 1, it is best to just compute the result
1339                      directly.  If UVAL is constant and STORE_FLAG_VALUE
1340                      includes all of its bits, it is best to compute the flag
1341                      value unnormalized and `and' it with UVAL.  Otherwise,
1342                      normalize to -1 and `and' with UVAL.  */
1343                   normalizep = (cval != const0_rtx ? -1
1344                                 : (uval == const1_rtx ? 1
1345                                    : (GET_CODE (uval) == CONST_INT
1346                                       && (INTVAL (uval) & ~STORE_FLAG_VALUE) == 0)
1347                                    ? 0 : -1));
1348
1349                   /* We will be putting the store-flag insn immediately in
1350                      front of the comparison that was originally being done,
1351                      so we know all the variables in TEMP4 will be valid.
1352                      However, this might be in front of the assignment of
1353                      A to VAR.  If it is, it would clobber the store-flag
1354                      we will be emitting.
1355
1356                      Therefore, emit into a temporary which will be copied to
1357                      VAR immediately after TEMP.  */
1358
1359                   start_sequence ();
1360                   target = emit_store_flag (gen_reg_rtx (GET_MODE (var)), code,
1361                                             XEXP (temp4, 0), XEXP (temp4, 1),
1362                                             VOIDmode,
1363                                             (code == LTU || code == LEU
1364                                              || code == GEU || code == GTU),
1365                                             normalizep);
1366                   if (target)
1367                     {
1368                       rtx seq;
1369                       rtx before = insn;
1370
1371                       seq = get_insns ();
1372                       end_sequence ();
1373
1374                       /* Put the store-flag insns in front of the first insn
1375                          used to compute the condition to ensure that we
1376                          use the same values of them as the current
1377                          comparison.  However, the remainder of the insns we
1378                          generate will be placed directly in front of the
1379                          jump insn, in case any of the pseudos we use
1380                          are modified earlier.  */
1381
1382                       emit_insns_before (seq, temp5);
1383
1384                       start_sequence ();
1385
1386                       /* Both CVAL and UVAL are non-zero.  */
1387                       if (cval != const0_rtx && uval != const0_rtx)
1388                         {
1389                           rtx tem1, tem2;
1390
1391                           tem1 = expand_and (uval, target, NULL_RTX);
1392                           if (GET_CODE (cval) == CONST_INT
1393                               && GET_CODE (uval) == CONST_INT
1394                               && (INTVAL (cval) & INTVAL (uval)) == INTVAL (cval))
1395                             tem2 = cval;
1396                           else
1397                             {
1398                               tem2 = expand_unop (GET_MODE (var), one_cmpl_optab,
1399                                                   target, NULL_RTX, 0);
1400                               tem2 = expand_and (cval, tem2,
1401                                                  (GET_CODE (tem2) == REG
1402                                                   ? tem2 : 0));
1403                             }
1404
1405                           /* If we usually make new pseudos, do so here.  This
1406                              turns out to help machines that have conditional
1407                              move insns.  */
1408                           /* ??? Conditional moves have already been handled.
1409                              This may be obsolete.  */
1410
1411                           if (flag_expensive_optimizations)
1412                             target = 0;
1413
1414                           target = expand_binop (GET_MODE (var), ior_optab,
1415                                                  tem1, tem2, target,
1416                                                  1, OPTAB_WIDEN);
1417                         }
1418                       else if (normalizep != 1)
1419                         {
1420                           /* We know that either CVAL or UVAL is zero.  If
1421                              UVAL is zero, negate TARGET and `and' with CVAL.
1422                              Otherwise, `and' with UVAL.  */
1423                           if (uval == const0_rtx)
1424                             {
1425                               target = expand_unop (GET_MODE (var), one_cmpl_optab,
1426                                                     target, NULL_RTX, 0);
1427                               uval = cval;
1428                             }
1429
1430                           target = expand_and (uval, target,
1431                                                (GET_CODE (target) == REG
1432                                                 && ! preserve_subexpressions_p ()
1433                                                 ? target : NULL_RTX));
1434                         }
1435
1436                       emit_move_insn (var, target);
1437                       seq = get_insns ();
1438                       end_sequence ();
1439 #ifdef HAVE_cc0
1440                       /* If INSN uses CC0, we must not separate it from the
1441                          insn that sets cc0.  */
1442                       if (reg_mentioned_p (cc0_rtx, PATTERN (before)))
1443                         before = prev_nonnote_insn (before);
1444 #endif
1445                       emit_insns_before (seq, before);
1446
1447                       delete_insn (temp);
1448                       next = NEXT_INSN (insn);
1449                       delete_jump (insn);
1450                       changed = 1;
1451                       continue;
1452                     }
1453                   else
1454                     end_sequence ();
1455                 }
1456             }
1457
1458           /* If branches are expensive, convert
1459                 if (foo) bar++;    to    bar += (foo != 0);
1460              and similarly for "bar--;"
1461
1462              INSN is the conditional branch around the arithmetic.  We set:
1463
1464              TEMP is the arithmetic insn.
1465              TEMP1 is the SET doing the arithmetic.
1466              TEMP2 is the operand being incremented or decremented.
1467              TEMP3 to the condition being tested.
1468              TEMP4 to the earliest insn used to find the condition.  */
1469
1470           if ((BRANCH_COST >= 2
1471 #ifdef HAVE_incscc
1472                || HAVE_incscc
1473 #endif
1474 #ifdef HAVE_decscc
1475                || HAVE_decscc
1476 #endif
1477               )
1478               && ! reload_completed
1479               && this_is_condjump && ! this_is_simplejump
1480               && (temp = next_nonnote_insn (insn)) != 0
1481               && (temp1 = single_set (temp)) != 0
1482               && (temp2 = SET_DEST (temp1),
1483                   GET_MODE_CLASS (GET_MODE (temp2)) == MODE_INT)
1484               && GET_CODE (SET_SRC (temp1)) == PLUS
1485               && (XEXP (SET_SRC (temp1), 1) == const1_rtx
1486                   || XEXP (SET_SRC (temp1), 1) == constm1_rtx)
1487               && rtx_equal_p (temp2, XEXP (SET_SRC (temp1), 0))
1488               && ! side_effects_p (temp2)
1489               && ! may_trap_p (temp2)
1490               /* INSN must either branch to the insn after TEMP or the insn
1491                  after TEMP must branch to the same place as INSN.  */
1492               && (reallabelprev == temp
1493                   || ((temp3 = next_active_insn (temp)) != 0
1494                       && simplejump_p (temp3)
1495                       && JUMP_LABEL (temp3) == JUMP_LABEL (insn)))
1496               && (temp3 = get_condition (insn, &temp4)) != 0
1497               /* We must be comparing objects whose modes imply the size.
1498                  We could handle BLKmode if (1) emit_store_flag could
1499                  and (2) we could find the size reliably.  */
1500               && GET_MODE (XEXP (temp3, 0)) != BLKmode
1501               && can_reverse_comparison_p (temp3, insn))
1502             {
1503               rtx temp6, target = 0, seq, init_insn = 0, init = temp2;
1504               enum rtx_code code = reverse_condition (GET_CODE (temp3));
1505
1506               start_sequence ();
1507
1508               /* It must be the case that TEMP2 is not modified in the range
1509                  [TEMP4, INSN).  The one exception we make is if the insn
1510                  before INSN sets TEMP2 to something which is also unchanged
1511                  in that range.  In that case, we can move the initialization
1512                  into our sequence.  */
1513
1514               if ((temp5 = prev_active_insn (insn)) != 0
1515                   && no_labels_between_p (temp5, insn)
1516                   && GET_CODE (temp5) == INSN
1517                   && (temp6 = single_set (temp5)) != 0
1518                   && rtx_equal_p (temp2, SET_DEST (temp6))
1519                   && (CONSTANT_P (SET_SRC (temp6))
1520                       || GET_CODE (SET_SRC (temp6)) == REG
1521                       || GET_CODE (SET_SRC (temp6)) == SUBREG))
1522                 {
1523                   emit_insn (PATTERN (temp5));
1524                   init_insn = temp5;
1525                   init = SET_SRC (temp6);
1526                 }
1527
1528               if (CONSTANT_P (init)
1529                   || ! reg_set_between_p (init, PREV_INSN (temp4), insn))
1530                 target = emit_store_flag (gen_reg_rtx (GET_MODE (temp2)), code,
1531                                           XEXP (temp3, 0), XEXP (temp3, 1),
1532                                           VOIDmode,
1533                                           (code == LTU || code == LEU
1534                                            || code == GTU || code == GEU), 1);
1535
1536               /* If we can do the store-flag, do the addition or
1537                  subtraction.  */
1538
1539               if (target)
1540                 target = expand_binop (GET_MODE (temp2),
1541                                        (XEXP (SET_SRC (temp1), 1) == const1_rtx
1542                                         ? add_optab : sub_optab),
1543                                        temp2, target, temp2, 0, OPTAB_WIDEN);
1544
1545               if (target != 0)
1546                 {
1547                   /* Put the result back in temp2 in case it isn't already.
1548                      Then replace the jump, possible a CC0-setting insn in
1549                      front of the jump, and TEMP, with the sequence we have
1550                      made.  */
1551
1552                   if (target != temp2)
1553                     emit_move_insn (temp2, target);
1554
1555                   seq = get_insns ();
1556                   end_sequence ();
1557
1558                   emit_insns_before (seq, temp4);
1559                   delete_insn (temp);
1560
1561                   if (init_insn)
1562                     delete_insn (init_insn);
1563
1564                   next = NEXT_INSN (insn);
1565 #ifdef HAVE_cc0
1566                   delete_insn (prev_nonnote_insn (insn));
1567 #endif
1568                   delete_insn (insn);
1569                   changed = 1;
1570                   continue;
1571                 }
1572               else
1573                 end_sequence ();
1574             }
1575
1576           /* Simplify   if (...) x = 1; else {...}  if (x) ...
1577              We recognize this case scanning backwards as well.
1578
1579              TEMP is the assignment to x;
1580              TEMP1 is the label at the head of the second if.  */
1581           /* ?? This should call get_condition to find the values being
1582              compared, instead of looking for a COMPARE insn when HAVE_cc0
1583              is not defined.  This would allow it to work on the m88k.  */
1584           /* ?? This optimization is only safe before cse is run if HAVE_cc0
1585              is not defined and the condition is tested by a separate compare
1586              insn.  This is because the code below assumes that the result
1587              of the compare dies in the following branch.
1588
1589              Not only that, but there might be other insns between the
1590              compare and branch whose results are live.  Those insns need
1591              to be executed.
1592
1593              A way to fix this is to move the insns at JUMP_LABEL (insn)
1594              to before INSN.  If we are running before flow, they will
1595              be deleted if they aren't needed.   But this doesn't work
1596              well after flow.
1597
1598              This is really a special-case of jump threading, anyway.  The
1599              right thing to do is to replace this and jump threading with
1600              much simpler code in cse.
1601
1602              This code has been turned off in the non-cc0 case in the
1603              meantime.  */
1604
1605 #ifdef HAVE_cc0
1606           else if (this_is_simplejump
1607                    /* Safe to skip USE and CLOBBER insns here
1608                       since they will not be deleted.  */
1609                    && (temp = prev_active_insn (insn))
1610                    && no_labels_between_p (temp, insn)
1611                    && GET_CODE (temp) == INSN
1612                    && GET_CODE (PATTERN (temp)) == SET
1613                    && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1614                    && CONSTANT_P (SET_SRC (PATTERN (temp)))
1615                    && (temp1 = next_active_insn (JUMP_LABEL (insn)))
1616                    /* If we find that the next value tested is `x'
1617                       (TEMP1 is the insn where this happens), win.  */
1618                    && GET_CODE (temp1) == INSN
1619                    && GET_CODE (PATTERN (temp1)) == SET
1620 #ifdef HAVE_cc0
1621                    /* Does temp1 `tst' the value of x?  */
1622                    && SET_SRC (PATTERN (temp1)) == SET_DEST (PATTERN (temp))
1623                    && SET_DEST (PATTERN (temp1)) == cc0_rtx
1624                    && (temp1 = next_nonnote_insn (temp1))
1625 #else
1626                    /* Does temp1 compare the value of x against zero?  */
1627                    && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1628                    && XEXP (SET_SRC (PATTERN (temp1)), 1) == const0_rtx
1629                    && (XEXP (SET_SRC (PATTERN (temp1)), 0)
1630                        == SET_DEST (PATTERN (temp)))
1631                    && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1632                    && (temp1 = find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1633 #endif
1634                    && condjump_p (temp1))
1635             {
1636               /* Get the if_then_else from the condjump.  */
1637               rtx choice = SET_SRC (PATTERN (temp1));
1638               if (GET_CODE (choice) == IF_THEN_ELSE)
1639                 {
1640                   enum rtx_code code = GET_CODE (XEXP (choice, 0));
1641                   rtx val = SET_SRC (PATTERN (temp));
1642                   rtx cond
1643                     = simplify_relational_operation (code, GET_MODE (SET_DEST (PATTERN (temp))),
1644                                                      val, const0_rtx);
1645                   rtx ultimate;
1646
1647                   if (cond == const_true_rtx)
1648                     ultimate = XEXP (choice, 1);
1649                   else if (cond == const0_rtx)
1650                     ultimate = XEXP (choice, 2);
1651                   else
1652                     ultimate = 0;
1653
1654                   if (ultimate == pc_rtx)
1655                     ultimate = get_label_after (temp1);
1656                   else if (ultimate && GET_CODE (ultimate) != RETURN)
1657                     ultimate = XEXP (ultimate, 0);
1658
1659                   if (ultimate && JUMP_LABEL(insn) != ultimate)
1660                     changed |= redirect_jump (insn, ultimate);
1661                 }
1662             }
1663 #endif
1664
1665 #if 0
1666           /* @@ This needs a bit of work before it will be right.
1667
1668              Any type of comparison can be accepted for the first and
1669              second compare.  When rewriting the first jump, we must
1670              compute the what conditions can reach label3, and use the
1671              appropriate code.  We can not simply reverse/swap the code
1672              of the first jump.  In some cases, the second jump must be
1673              rewritten also.
1674
1675              For example,
1676              <  == converts to >  ==
1677              <  != converts to ==  >
1678              etc.
1679
1680              If the code is written to only accept an '==' test for the second
1681              compare, then all that needs to be done is to swap the condition
1682              of the first branch.
1683
1684              It is questionable whether we want this optimization anyways,
1685              since if the user wrote code like this because he/she knew that
1686              the jump to label1 is taken most of the time, then rewriting
1687              this gives slower code.  */
1688           /* @@ This should call get_condition to find the values being
1689              compared, instead of looking for a COMPARE insn when HAVE_cc0
1690              is not defined.  This would allow it to work on the m88k.  */
1691           /* @@ This optimization is only safe before cse is run if HAVE_cc0
1692              is not defined and the condition is tested by a separate compare
1693              insn.  This is because the code below assumes that the result
1694              of the compare dies in the following branch.  */
1695
1696           /* Simplify  test a ~= b
1697                        condjump label1;
1698                        test a == b
1699                        condjump label2;
1700                        jump label3;
1701                        label1:
1702
1703              rewriting as
1704                        test a ~~= b
1705                        condjump label3
1706                        test a == b
1707                        condjump label2
1708                        label1:
1709
1710              where ~= is an inequality, e.g. >, and ~~= is the swapped
1711              inequality, e.g. <.
1712
1713              We recognize this case scanning backwards.
1714
1715              TEMP is the conditional jump to `label2';
1716              TEMP1 is the test for `a == b';
1717              TEMP2 is the conditional jump to `label1';
1718              TEMP3 is the test for `a ~= b'.  */
1719           else if (this_is_simplejump
1720                    && (temp = prev_active_insn (insn))
1721                    && no_labels_between_p (temp, insn)
1722                    && condjump_p (temp)
1723                    && (temp1 = prev_active_insn (temp))
1724                    && no_labels_between_p (temp1, temp)
1725                    && GET_CODE (temp1) == INSN
1726                    && GET_CODE (PATTERN (temp1)) == SET
1727 #ifdef HAVE_cc0
1728                    && sets_cc0_p (PATTERN (temp1)) == 1
1729 #else
1730                    && GET_CODE (SET_SRC (PATTERN (temp1))) == COMPARE
1731                    && GET_CODE (SET_DEST (PATTERN (temp1))) == REG
1732                    && (temp == find_next_ref (SET_DEST (PATTERN (temp1)), temp1))
1733 #endif
1734                    && (temp2 = prev_active_insn (temp1))
1735                    && no_labels_between_p (temp2, temp1)
1736                    && condjump_p (temp2)
1737                    && JUMP_LABEL (temp2) == next_nonnote_insn (NEXT_INSN (insn))
1738                    && (temp3 = prev_active_insn (temp2))
1739                    && no_labels_between_p (temp3, temp2)
1740                    && GET_CODE (PATTERN (temp3)) == SET
1741                    && rtx_equal_p (SET_DEST (PATTERN (temp3)),
1742                                    SET_DEST (PATTERN (temp1)))
1743                    && rtx_equal_p (SET_SRC (PATTERN (temp1)),
1744                                    SET_SRC (PATTERN (temp3)))
1745                    && ! inequality_comparisons_p (PATTERN (temp))
1746                    && inequality_comparisons_p (PATTERN (temp2)))
1747             {
1748               rtx fallthrough_label = JUMP_LABEL (temp2);
1749
1750               ++LABEL_NUSES (fallthrough_label);
1751               if (swap_jump (temp2, JUMP_LABEL (insn)))
1752                 {
1753                   delete_insn (insn);
1754                   changed = 1;
1755                 }
1756
1757               if (--LABEL_NUSES (fallthrough_label) == 0)
1758                 delete_insn (fallthrough_label);
1759             }
1760 #endif
1761           /* Simplify  if (...) {... x = 1;} if (x) ...
1762
1763              We recognize this case backwards.
1764
1765              TEMP is the test of `x';
1766              TEMP1 is the assignment to `x' at the end of the
1767              previous statement.  */
1768           /* @@ This should call get_condition to find the values being
1769              compared, instead of looking for a COMPARE insn when HAVE_cc0
1770              is not defined.  This would allow it to work on the m88k.  */
1771           /* @@ This optimization is only safe before cse is run if HAVE_cc0
1772              is not defined and the condition is tested by a separate compare
1773              insn.  This is because the code below assumes that the result
1774              of the compare dies in the following branch.  */
1775
1776           /* ??? This has to be turned off.  The problem is that the
1777              unconditional jump might indirectly end up branching to the
1778              label between TEMP1 and TEMP.  We can't detect this, in general,
1779              since it may become a jump to there after further optimizations.
1780              If that jump is done, it will be deleted, so we will retry
1781              this optimization in the next pass, thus an infinite loop.
1782
1783              The present code prevents this by putting the jump after the
1784              label, but this is not logically correct.  */
1785 #if 0
1786           else if (this_is_condjump
1787                    /* Safe to skip USE and CLOBBER insns here
1788                       since they will not be deleted.  */
1789                    && (temp = prev_active_insn (insn))
1790                    && no_labels_between_p (temp, insn)
1791                    && GET_CODE (temp) == INSN
1792                    && GET_CODE (PATTERN (temp)) == SET
1793 #ifdef HAVE_cc0
1794                    && sets_cc0_p (PATTERN (temp)) == 1
1795                    && GET_CODE (SET_SRC (PATTERN (temp))) == REG
1796 #else
1797                    /* Temp must be a compare insn, we can not accept a register
1798                       to register move here, since it may not be simply a
1799                       tst insn.  */
1800                    && GET_CODE (SET_SRC (PATTERN (temp))) == COMPARE
1801                    && XEXP (SET_SRC (PATTERN (temp)), 1) == const0_rtx
1802                    && GET_CODE (XEXP (SET_SRC (PATTERN (temp)), 0)) == REG
1803                    && GET_CODE (SET_DEST (PATTERN (temp))) == REG
1804                    && insn == find_next_ref (SET_DEST (PATTERN (temp)), temp)
1805 #endif
1806                    /* May skip USE or CLOBBER insns here
1807                       for checking for opportunity, since we
1808                       take care of them later.  */
1809                    && (temp1 = prev_active_insn (temp))
1810                    && GET_CODE (temp1) == INSN
1811                    && GET_CODE (PATTERN (temp1)) == SET
1812 #ifdef HAVE_cc0
1813                    && SET_SRC (PATTERN (temp)) == SET_DEST (PATTERN (temp1))
1814 #else
1815                    && (XEXP (SET_SRC (PATTERN (temp)), 0)
1816                        == SET_DEST (PATTERN (temp1)))
1817 #endif
1818                    && CONSTANT_P (SET_SRC (PATTERN (temp1)))
1819                    /* If this isn't true, cse will do the job.  */
1820                    && ! no_labels_between_p (temp1, temp))
1821             {
1822               /* Get the if_then_else from the condjump.  */
1823               rtx choice = SET_SRC (PATTERN (insn));
1824               if (GET_CODE (choice) == IF_THEN_ELSE
1825                   && (GET_CODE (XEXP (choice, 0)) == EQ
1826                       || GET_CODE (XEXP (choice, 0)) == NE))
1827                 {
1828                   int want_nonzero = (GET_CODE (XEXP (choice, 0)) == NE);
1829                   rtx last_insn;
1830                   rtx ultimate;
1831                   rtx p;
1832
1833                   /* Get the place that condjump will jump to
1834                      if it is reached from here.  */
1835                   if ((SET_SRC (PATTERN (temp1)) != const0_rtx)
1836                       == want_nonzero)
1837                     ultimate = XEXP (choice, 1);
1838                   else
1839                     ultimate = XEXP (choice, 2);
1840                   /* Get it as a CODE_LABEL.  */
1841                   if (ultimate == pc_rtx)
1842                     ultimate = get_label_after (insn);
1843                   else
1844                     /* Get the label out of the LABEL_REF.  */
1845                     ultimate = XEXP (ultimate, 0);
1846
1847                   /* Insert the jump immediately before TEMP, specifically
1848                      after the label that is between TEMP1 and TEMP.  */
1849                   last_insn = PREV_INSN (temp);
1850
1851                   /* If we would be branching to the next insn, the jump
1852                      would immediately be deleted and the re-inserted in
1853                      a subsequent pass over the code.  So don't do anything
1854                      in that case.  */
1855                   if (next_active_insn (last_insn)
1856                       != next_active_insn (ultimate))
1857                     {
1858                       emit_barrier_after (last_insn);
1859                       p = emit_jump_insn_after (gen_jump (ultimate),
1860                                                 last_insn);
1861                       JUMP_LABEL (p) = ultimate;
1862                       ++LABEL_NUSES (ultimate);
1863                       if (INSN_UID (ultimate) < max_jump_chain
1864                           && INSN_CODE (p) < max_jump_chain)
1865                         {
1866                           jump_chain[INSN_UID (p)]
1867                             = jump_chain[INSN_UID (ultimate)];
1868                           jump_chain[INSN_UID (ultimate)] = p;
1869                         }
1870                       changed = 1;
1871                       continue;
1872                     }
1873                 }
1874             }
1875 #endif
1876           /* Detect a conditional jump going to the same place
1877              as an immediately following unconditional jump.  */
1878           else if (this_is_condjump
1879                    && (temp = next_active_insn (insn)) != 0
1880                    && simplejump_p (temp)
1881                    && (next_active_insn (JUMP_LABEL (insn))
1882                        == next_active_insn (JUMP_LABEL (temp))))
1883             {
1884               rtx tem = temp;
1885
1886               /* ??? Optional.  Disables some optimizations, but makes
1887                  gcov output more accurate with -O.  */
1888               if (flag_test_coverage && !reload_completed)
1889                 for (tem = insn; tem != temp; tem = NEXT_INSN (tem))
1890                   if (GET_CODE (tem) == NOTE && NOTE_LINE_NUMBER (tem) > 0)
1891                     break;
1892
1893               if (tem == temp)
1894                 {
1895                   delete_jump (insn);
1896                   changed = 1;
1897                   continue;
1898                 }
1899             }
1900           /* Detect a conditional jump jumping over an unconditional jump.  */
1901
1902           else if ((this_is_condjump || this_is_condjump_in_parallel)
1903                    && ! this_is_simplejump
1904                    && reallabelprev != 0
1905                    && GET_CODE (reallabelprev) == JUMP_INSN
1906                    && prev_active_insn (reallabelprev) == insn
1907                    && no_labels_between_p (insn, reallabelprev)
1908                    && simplejump_p (reallabelprev))
1909             {
1910               /* When we invert the unconditional jump, we will be
1911                  decrementing the usage count of its old label.
1912                  Make sure that we don't delete it now because that
1913                  might cause the following code to be deleted.  */
1914               rtx prev_uses = prev_nonnote_insn (reallabelprev);
1915               rtx prev_label = JUMP_LABEL (insn);
1916
1917               if (prev_label)
1918                 ++LABEL_NUSES (prev_label);
1919
1920               if (invert_jump (insn, JUMP_LABEL (reallabelprev)))
1921                 {
1922                   /* It is very likely that if there are USE insns before
1923                      this jump, they hold REG_DEAD notes.  These REG_DEAD
1924                      notes are no longer valid due to this optimization,
1925                      and will cause the life-analysis that following passes
1926                      (notably delayed-branch scheduling) to think that
1927                      these registers are dead when they are not.
1928
1929                      To prevent this trouble, we just remove the USE insns
1930                      from the insn chain.  */
1931
1932                   while (prev_uses && GET_CODE (prev_uses) == INSN
1933                          && GET_CODE (PATTERN (prev_uses)) == USE)
1934                     {
1935                       rtx useless = prev_uses;
1936                       prev_uses = prev_nonnote_insn (prev_uses);
1937                       delete_insn (useless);
1938                     }
1939
1940                   delete_insn (reallabelprev);
1941                   next = insn;
1942                   changed = 1;
1943                 }
1944
1945               /* We can now safely delete the label if it is unreferenced
1946                  since the delete_insn above has deleted the BARRIER.  */
1947               if (prev_label && --LABEL_NUSES (prev_label) == 0)
1948                 delete_insn (prev_label);
1949               continue;
1950             }
1951           else
1952             {
1953               /* Detect a jump to a jump.  */
1954
1955               nlabel = follow_jumps (JUMP_LABEL (insn));
1956               if (nlabel != JUMP_LABEL (insn)
1957                   && redirect_jump (insn, nlabel))
1958                 {
1959                   changed = 1;
1960                   next = insn;
1961                 }
1962
1963               /* Look for   if (foo) bar; else break;  */
1964               /* The insns look like this:
1965                  insn = condjump label1;
1966                  ...range1 (some insns)...
1967                  jump label2;
1968                  label1:
1969                  ...range2 (some insns)...
1970                  jump somewhere unconditionally
1971                  label2:  */
1972               {
1973                 rtx label1 = next_label (insn);
1974                 rtx range1end = label1 ? prev_active_insn (label1) : 0;
1975                 /* Don't do this optimization on the first round, so that
1976                    jump-around-a-jump gets simplified before we ask here
1977                    whether a jump is unconditional.
1978
1979                    Also don't do it when we are called after reload since
1980                    it will confuse reorg.  */
1981                 if (! first
1982                     && (reload_completed ? ! flag_delayed_branch : 1)
1983                     /* Make sure INSN is something we can invert.  */
1984                     && condjump_p (insn)
1985                     && label1 != 0
1986                     && JUMP_LABEL (insn) == label1
1987                     && LABEL_NUSES (label1) == 1
1988                     && GET_CODE (range1end) == JUMP_INSN
1989                     && simplejump_p (range1end))
1990                   {
1991                     rtx label2 = next_label (label1);
1992                     rtx range2end = label2 ? prev_active_insn (label2) : 0;
1993                     if (range1end != range2end
1994                         && JUMP_LABEL (range1end) == label2
1995                         && GET_CODE (range2end) == JUMP_INSN
1996                         && GET_CODE (NEXT_INSN (range2end)) == BARRIER
1997                         /* Invert the jump condition, so we
1998                            still execute the same insns in each case.  */
1999                         && invert_jump (insn, label1))
2000                       {
2001                         rtx range1beg = next_active_insn (insn);
2002                         rtx range2beg = next_active_insn (label1);
2003                         rtx range1after, range2after;
2004                         rtx range1before, range2before;
2005                         rtx rangenext;
2006
2007                         /* Include in each range any notes before it, to be
2008                            sure that we get the line number note if any, even
2009                            if there are other notes here.  */
2010                         while (PREV_INSN (range1beg)
2011                                && GET_CODE (PREV_INSN (range1beg)) == NOTE)
2012                           range1beg = PREV_INSN (range1beg);
2013
2014                         while (PREV_INSN (range2beg)
2015                                && GET_CODE (PREV_INSN (range2beg)) == NOTE)
2016                           range2beg = PREV_INSN (range2beg);
2017
2018                         /* Don't move NOTEs for blocks or loops; shift them
2019                            outside the ranges, where they'll stay put.  */
2020                         range1beg = squeeze_notes (range1beg, range1end);
2021                         range2beg = squeeze_notes (range2beg, range2end);
2022
2023                         /* Get current surrounds of the 2 ranges.  */
2024                         range1before = PREV_INSN (range1beg);
2025                         range2before = PREV_INSN (range2beg);
2026                         range1after = NEXT_INSN (range1end);
2027                         range2after = NEXT_INSN (range2end);
2028
2029                         /* Splice range2 where range1 was.  */
2030                         NEXT_INSN (range1before) = range2beg;
2031                         PREV_INSN (range2beg) = range1before;
2032                         NEXT_INSN (range2end) = range1after;
2033                         PREV_INSN (range1after) = range2end;
2034                         /* Splice range1 where range2 was.  */
2035                         NEXT_INSN (range2before) = range1beg;
2036                         PREV_INSN (range1beg) = range2before;
2037                         NEXT_INSN (range1end) = range2after;
2038                         PREV_INSN (range2after) = range1end;
2039
2040                         /* Check for a loop end note between the end of
2041                            range2, and the next code label.  If there is one,
2042                            then what we have really seen is
2043                            if (foo) break; end_of_loop;
2044                            and moved the break sequence outside the loop.
2045                            We must move the LOOP_END note to where the
2046                            loop really ends now, or we will confuse loop
2047                            optimization.  Stop if we find a LOOP_BEG note
2048                            first, since we don't want to move the LOOP_END
2049                            note in that case.  */
2050                         for (;range2after != label2; range2after = rangenext)
2051                           {
2052                             rangenext = NEXT_INSN (range2after);
2053                             if (GET_CODE (range2after) == NOTE)
2054                               {
2055                                 if (NOTE_LINE_NUMBER (range2after)
2056                                     == NOTE_INSN_LOOP_END)
2057                                   {
2058                                     NEXT_INSN (PREV_INSN (range2after))
2059                                       = rangenext;
2060                                     PREV_INSN (rangenext)
2061                                       = PREV_INSN (range2after);
2062                                     PREV_INSN (range2after)
2063                                       = PREV_INSN (range1beg);
2064                                     NEXT_INSN (range2after) = range1beg;
2065                                     NEXT_INSN (PREV_INSN (range1beg))
2066                                       = range2after;
2067                                     PREV_INSN (range1beg) = range2after;
2068                                   }
2069                                 else if (NOTE_LINE_NUMBER (range2after)
2070                                          == NOTE_INSN_LOOP_BEG)
2071                                   break;
2072                               }
2073                           }
2074                         changed = 1;
2075                         continue;
2076                       }
2077                   }
2078               }
2079
2080               /* Now that the jump has been tensioned,
2081                  try cross jumping: check for identical code
2082                  before the jump and before its target label.  */
2083
2084               /* First, cross jumping of conditional jumps:  */
2085
2086               if (cross_jump && condjump_p (insn))
2087                 {
2088                   rtx newjpos, newlpos;
2089                   rtx x = prev_real_insn (JUMP_LABEL (insn));
2090
2091                   /* A conditional jump may be crossjumped
2092                      only if the place it jumps to follows
2093                      an opposing jump that comes back here.  */
2094
2095                   if (x != 0 && ! jump_back_p (x, insn))
2096                     /* We have no opposing jump;
2097                        cannot cross jump this insn.  */
2098                     x = 0;
2099
2100                   newjpos = 0;
2101                   /* TARGET is nonzero if it is ok to cross jump
2102                      to code before TARGET.  If so, see if matches.  */
2103                   if (x != 0)
2104                     find_cross_jump (insn, x, 2,
2105                                      &newjpos, &newlpos);
2106
2107                   if (newjpos != 0)
2108                     {
2109                       do_cross_jump (insn, newjpos, newlpos);
2110                       /* Make the old conditional jump
2111                          into an unconditional one.  */
2112                       SET_SRC (PATTERN (insn))
2113                         = gen_rtx_LABEL_REF (VOIDmode, JUMP_LABEL (insn));
2114                       INSN_CODE (insn) = -1;
2115                       emit_barrier_after (insn);
2116                       /* Add to jump_chain unless this is a new label
2117                          whose UID is too large.  */
2118                       if (INSN_UID (JUMP_LABEL (insn)) < max_jump_chain)
2119                         {
2120                           jump_chain[INSN_UID (insn)]
2121                             = jump_chain[INSN_UID (JUMP_LABEL (insn))];
2122                           jump_chain[INSN_UID (JUMP_LABEL (insn))] = insn;
2123                         }
2124                       changed = 1;
2125                       next = insn;
2126                     }
2127                 }
2128
2129               /* Cross jumping of unconditional jumps:
2130                  a few differences.  */
2131
2132               if (cross_jump && simplejump_p (insn))
2133                 {
2134                   rtx newjpos, newlpos;
2135                   rtx target;
2136
2137                   newjpos = 0;
2138
2139                   /* TARGET is nonzero if it is ok to cross jump
2140                      to code before TARGET.  If so, see if matches.  */
2141                   find_cross_jump (insn, JUMP_LABEL (insn), 1,
2142                                    &newjpos, &newlpos);
2143
2144                   /* If cannot cross jump to code before the label,
2145                      see if we can cross jump to another jump to
2146                      the same label.  */
2147                   /* Try each other jump to this label.  */
2148                   if (INSN_UID (JUMP_LABEL (insn)) < max_uid)
2149                     for (target = jump_chain[INSN_UID (JUMP_LABEL (insn))];
2150                          target != 0 && newjpos == 0;
2151                          target = jump_chain[INSN_UID (target)])
2152                       if (target != insn
2153                           && JUMP_LABEL (target) == JUMP_LABEL (insn)
2154                           /* Ignore TARGET if it's deleted.  */
2155                           && ! INSN_DELETED_P (target))
2156                         find_cross_jump (insn, target, 2,
2157                                          &newjpos, &newlpos);
2158
2159                   if (newjpos != 0)
2160                     {
2161                       do_cross_jump (insn, newjpos, newlpos);
2162                       changed = 1;
2163                       next = insn;
2164                     }
2165                 }
2166
2167               /* This code was dead in the previous jump.c!  */
2168               if (cross_jump && GET_CODE (PATTERN (insn)) == RETURN)
2169                 {
2170                   /* Return insns all "jump to the same place"
2171                      so we can cross-jump between any two of them.  */
2172
2173                   rtx newjpos, newlpos, target;
2174
2175                   newjpos = 0;
2176
2177                   /* If cannot cross jump to code before the label,
2178                      see if we can cross jump to another jump to
2179                      the same label.  */
2180                   /* Try each other jump to this label.  */
2181                   for (target = jump_chain[0];
2182                        target != 0 && newjpos == 0;
2183                        target = jump_chain[INSN_UID (target)])
2184                     if (target != insn
2185                         && ! INSN_DELETED_P (target)
2186                         && GET_CODE (PATTERN (target)) == RETURN)
2187                       find_cross_jump (insn, target, 2,
2188                                        &newjpos, &newlpos);
2189
2190                   if (newjpos != 0)
2191                     {
2192                       do_cross_jump (insn, newjpos, newlpos);
2193                       changed = 1;
2194                       next = insn;
2195                     }
2196                 }
2197             }
2198         }
2199
2200       first = 0;
2201     }
2202
2203   /* Delete extraneous line number notes.
2204      Note that two consecutive notes for different lines are not really
2205      extraneous.  There should be some indication where that line belonged,
2206      even if it became empty.  */
2207
2208   {
2209     rtx last_note = 0;
2210
2211     for (insn = f; insn; insn = NEXT_INSN (insn))
2212       if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0)
2213         {
2214           /* Delete this note if it is identical to previous note.  */
2215           if (last_note
2216               && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
2217               && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
2218             {
2219               delete_insn (insn);
2220               continue;
2221             }
2222
2223           last_note = insn;
2224         }
2225   }
2226
2227 #ifdef HAVE_return
2228   if (HAVE_return)
2229     {
2230       /* If we fall through to the epilogue, see if we can insert a RETURN insn
2231          in front of it.  If the machine allows it at this point (we might be
2232          after reload for a leaf routine), it will improve optimization for it
2233          to be there.  We do this both here and at the start of this pass since
2234          the RETURN might have been deleted by some of our optimizations.  */
2235       insn = get_last_insn ();
2236       while (insn && GET_CODE (insn) == NOTE)
2237         insn = PREV_INSN (insn);
2238
2239       if (insn && GET_CODE (insn) != BARRIER)
2240         {
2241           emit_jump_insn (gen_return ());
2242           emit_barrier ();
2243         }
2244     }
2245 #endif
2246
2247   /* See if there is still a NOTE_INSN_FUNCTION_END in this function.
2248      If so, delete it, and record that this function can drop off the end.  */
2249
2250   insn = last_insn;
2251   {
2252     int n_labels = 1;
2253     while (insn
2254            /* One label can follow the end-note: the return label.  */
2255            && ((GET_CODE (insn) == CODE_LABEL && n_labels-- > 0)
2256                /* Ordinary insns can follow it if returning a structure.  */
2257                || GET_CODE (insn) == INSN
2258                /* If machine uses explicit RETURN insns, no epilogue,
2259                   then one of them follows the note.  */
2260                || (GET_CODE (insn) == JUMP_INSN
2261                    && GET_CODE (PATTERN (insn)) == RETURN)
2262                /* A barrier can follow the return insn.  */
2263                || GET_CODE (insn) == BARRIER
2264                /* Other kinds of notes can follow also.  */
2265                || (GET_CODE (insn) == NOTE
2266                    && NOTE_LINE_NUMBER (insn) != NOTE_INSN_FUNCTION_END)))
2267       insn = PREV_INSN (insn);
2268   }
2269
2270   /* Report if control can fall through at the end of the function.  */
2271   if (insn && GET_CODE (insn) == NOTE
2272       && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_END)
2273     {
2274       can_reach_end = 1;
2275       delete_insn (insn);
2276     }
2277
2278   /* Show JUMP_CHAIN no longer valid.  */
2279   jump_chain = 0;
2280 }
2281 \f
2282 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
2283    jump.  Assume that this unconditional jump is to the exit test code.  If
2284    the code is sufficiently simple, make a copy of it before INSN,
2285    followed by a jump to the exit of the loop.  Then delete the unconditional
2286    jump after INSN.
2287
2288    Return 1 if we made the change, else 0.
2289
2290    This is only safe immediately after a regscan pass because it uses the
2291    values of regno_first_uid and regno_last_uid.  */
2292
2293 static int
2294 duplicate_loop_exit_test (loop_start)
2295      rtx loop_start;
2296 {
2297   rtx insn, set, reg, p, link;
2298   rtx copy = 0;
2299   int num_insns = 0;
2300   rtx exitcode = NEXT_INSN (JUMP_LABEL (next_nonnote_insn (loop_start)));
2301   rtx lastexit;
2302   int max_reg = max_reg_num ();
2303   rtx *reg_map = 0;
2304
2305   /* Scan the exit code.  We do not perform this optimization if any insn:
2306
2307          is a CALL_INSN
2308          is a CODE_LABEL
2309          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
2310          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
2311          is a NOTE_INSN_BLOCK_{BEG,END} because duplicating these notes
2312               are not valid
2313
2314      Also, don't do this if the exit code is more than 20 insns.  */
2315
2316   for (insn = exitcode;
2317        insn
2318        && ! (GET_CODE (insn) == NOTE
2319              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
2320        insn = NEXT_INSN (insn))
2321     {
2322       switch (GET_CODE (insn))
2323         {
2324         case CODE_LABEL:
2325         case CALL_INSN:
2326           return 0;
2327         case NOTE:
2328           /* We could be in front of the wrong NOTE_INSN_LOOP_END if there is
2329              a jump immediately after the loop start that branches outside
2330              the loop but within an outer loop, near the exit test.
2331              If we copied this exit test and created a phony
2332              NOTE_INSN_LOOP_VTOP, this could make instructions immediately
2333              before the exit test look like these could be safely moved
2334              out of the loop even if they actually may be never executed.
2335              This can be avoided by checking here for NOTE_INSN_LOOP_CONT.  */
2336
2337           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2338               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2339               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
2340               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
2341             return 0;
2342           break;
2343         case JUMP_INSN:
2344         case INSN:
2345           if (++num_insns > 20
2346               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
2347               || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2348             return 0;
2349           break;
2350         default:
2351           break;
2352         }
2353     }
2354
2355   /* Unless INSN is zero, we can do the optimization.  */
2356   if (insn == 0)
2357     return 0;
2358
2359   lastexit = insn;
2360
2361   /* See if any insn sets a register only used in the loop exit code and
2362      not a user variable.  If so, replace it with a new register.  */
2363   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2364     if (GET_CODE (insn) == INSN
2365         && (set = single_set (insn)) != 0
2366         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
2367             || (GET_CODE (reg) == SUBREG
2368                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
2369         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
2370         && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
2371       {
2372         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
2373           if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
2374             break;
2375
2376         if (p != lastexit)
2377           {
2378             /* We can do the replacement.  Allocate reg_map if this is the
2379                first replacement we found.  */
2380             if (reg_map == 0)
2381               {
2382                 reg_map = (rtx *) alloca (max_reg * sizeof (rtx));
2383                 bzero ((char *) reg_map, max_reg * sizeof (rtx));
2384               }
2385
2386             REG_LOOP_TEST_P (reg) = 1;
2387
2388             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
2389           }
2390       }
2391
2392   /* Now copy each insn.  */
2393   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
2394     switch (GET_CODE (insn))
2395       {
2396       case BARRIER:
2397         copy = emit_barrier_before (loop_start);
2398         break;
2399       case NOTE:
2400         /* Only copy line-number notes.  */
2401         if (NOTE_LINE_NUMBER (insn) >= 0)
2402           {
2403             copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
2404             NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
2405           }
2406         break;
2407
2408       case INSN:
2409         copy = emit_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2410         if (reg_map)
2411           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2412
2413         mark_jump_label (PATTERN (copy), copy, 0);
2414
2415         /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
2416            make them.  */
2417         for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2418           if (REG_NOTE_KIND (link) != REG_LABEL)
2419             REG_NOTES (copy)
2420               = copy_rtx (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
2421                                              XEXP (link, 0),
2422                                              REG_NOTES (copy)));
2423         if (reg_map && REG_NOTES (copy))
2424           replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2425         break;
2426
2427       case JUMP_INSN:
2428         copy = emit_jump_insn_before (copy_rtx (PATTERN (insn)), loop_start);
2429         if (reg_map)
2430           replace_regs (PATTERN (copy), reg_map, max_reg, 1);
2431         mark_jump_label (PATTERN (copy), copy, 0);
2432         if (REG_NOTES (insn))
2433           {
2434             REG_NOTES (copy) = copy_rtx (REG_NOTES (insn));
2435             if (reg_map)
2436               replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
2437           }
2438
2439         /* If this is a simple jump, add it to the jump chain.  */
2440
2441         if (INSN_UID (copy) < max_jump_chain && JUMP_LABEL (copy)
2442             && simplejump_p (copy))
2443           {
2444             jump_chain[INSN_UID (copy)]
2445               = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2446             jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2447           }
2448         break;
2449
2450       default:
2451         abort ();
2452       }
2453
2454   /* Now clean up by emitting a jump to the end label and deleting the jump
2455      at the start of the loop.  */
2456   if (! copy || GET_CODE (copy) != BARRIER)
2457     {
2458       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
2459                                     loop_start);
2460       mark_jump_label (PATTERN (copy), copy, 0);
2461       if (INSN_UID (copy) < max_jump_chain
2462           && INSN_UID (JUMP_LABEL (copy)) < max_jump_chain)
2463         {
2464           jump_chain[INSN_UID (copy)]
2465             = jump_chain[INSN_UID (JUMP_LABEL (copy))];
2466           jump_chain[INSN_UID (JUMP_LABEL (copy))] = copy;
2467         }
2468       emit_barrier_before (loop_start);
2469     }
2470
2471   /* Mark the exit code as the virtual top of the converted loop.  */
2472   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
2473
2474   delete_insn (next_nonnote_insn (loop_start));
2475
2476   return 1;
2477 }
2478 \f
2479 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, and
2480    loop-end notes between START and END out before START.  Assume that
2481    END is not such a note.  START may be such a note.  Returns the value
2482    of the new starting insn, which may be different if the original start
2483    was such a note.  */
2484
2485 rtx
2486 squeeze_notes (start, end)
2487      rtx start, end;
2488 {
2489   rtx insn;
2490   rtx next;
2491
2492   for (insn = start; insn != end; insn = next)
2493     {
2494       next = NEXT_INSN (insn);
2495       if (GET_CODE (insn) == NOTE
2496           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
2497               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
2498               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
2499               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
2500               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
2501               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
2502         {
2503           if (insn == start)
2504             start = next;
2505           else
2506             {
2507               rtx prev = PREV_INSN (insn);
2508               PREV_INSN (insn) = PREV_INSN (start);
2509               NEXT_INSN (insn) = start;
2510               NEXT_INSN (PREV_INSN (insn)) = insn;
2511               PREV_INSN (NEXT_INSN (insn)) = insn;
2512               NEXT_INSN (prev) = next;
2513               PREV_INSN (next) = prev;
2514             }
2515         }
2516     }
2517
2518   return start;
2519 }
2520 \f
2521 /* Compare the instructions before insn E1 with those before E2
2522    to find an opportunity for cross jumping.
2523    (This means detecting identical sequences of insns followed by
2524    jumps to the same place, or followed by a label and a jump
2525    to that label, and replacing one with a jump to the other.)
2526
2527    Assume E1 is a jump that jumps to label E2
2528    (that is not always true but it might as well be).
2529    Find the longest possible equivalent sequences
2530    and store the first insns of those sequences into *F1 and *F2.
2531    Store zero there if no equivalent preceding instructions are found.
2532
2533    We give up if we find a label in stream 1.
2534    Actually we could transfer that label into stream 2.  */
2535
2536 static void
2537 find_cross_jump (e1, e2, minimum, f1, f2)
2538      rtx e1, e2;
2539      int minimum;
2540      rtx *f1, *f2;
2541 {
2542   register rtx i1 = e1, i2 = e2;
2543   register rtx p1, p2;
2544   int lose = 0;
2545
2546   rtx last1 = 0, last2 = 0;
2547   rtx afterlast1 = 0, afterlast2 = 0;
2548
2549   *f1 = 0;
2550   *f2 = 0;
2551
2552   while (1)
2553     {
2554       i1 = prev_nonnote_insn (i1);
2555
2556       i2 = PREV_INSN (i2);
2557       while (i2 && (GET_CODE (i2) == NOTE || GET_CODE (i2) == CODE_LABEL))
2558         i2 = PREV_INSN (i2);
2559
2560       if (i1 == 0)
2561         break;
2562
2563       /* Don't allow the range of insns preceding E1 or E2
2564          to include the other (E2 or E1).  */
2565       if (i2 == e1 || i1 == e2)
2566         break;
2567
2568       /* If we will get to this code by jumping, those jumps will be
2569          tensioned to go directly to the new label (before I2),
2570          so this cross-jumping won't cost extra.  So reduce the minimum.  */
2571       if (GET_CODE (i1) == CODE_LABEL)
2572         {
2573           --minimum;
2574           break;
2575         }
2576
2577       if (i2 == 0 || GET_CODE (i1) != GET_CODE (i2))
2578         break;
2579
2580       p1 = PATTERN (i1);
2581       p2 = PATTERN (i2);
2582
2583       /* If this is a CALL_INSN, compare register usage information.
2584          If we don't check this on stack register machines, the two
2585          CALL_INSNs might be merged leaving reg-stack.c with mismatching
2586          numbers of stack registers in the same basic block.
2587          If we don't check this on machines with delay slots, a delay slot may
2588          be filled that clobbers a parameter expected by the subroutine.
2589
2590          ??? We take the simple route for now and assume that if they're
2591          equal, they were constructed identically.  */
2592
2593       if (GET_CODE (i1) == CALL_INSN
2594           && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
2595                             CALL_INSN_FUNCTION_USAGE (i2)))
2596         lose = 1;
2597
2598 #ifdef STACK_REGS
2599       /* If cross_jump_death_matters is not 0, the insn's mode
2600          indicates whether or not the insn contains any stack-like
2601          regs.  */
2602
2603       if (!lose && cross_jump_death_matters && GET_MODE (i1) == QImode)
2604         {
2605           /* If register stack conversion has already been done, then
2606              death notes must also be compared before it is certain that
2607              the two instruction streams match.  */
2608
2609           rtx note;
2610           HARD_REG_SET i1_regset, i2_regset;
2611
2612           CLEAR_HARD_REG_SET (i1_regset);
2613           CLEAR_HARD_REG_SET (i2_regset);
2614
2615           for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
2616             if (REG_NOTE_KIND (note) == REG_DEAD
2617                 && STACK_REG_P (XEXP (note, 0)))
2618               SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
2619
2620           for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
2621             if (REG_NOTE_KIND (note) == REG_DEAD
2622                 && STACK_REG_P (XEXP (note, 0)))
2623               SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
2624
2625           GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
2626
2627           lose = 1;
2628
2629         done:
2630           ;
2631         }
2632 #endif
2633
2634       /* Don't allow old-style asm or volatile extended asms to be accepted
2635          for cross jumping purposes.  It is conceptually correct to allow
2636          them, since cross-jumping preserves the dynamic instruction order
2637          even though it is changing the static instruction order.  However,
2638          if an asm is being used to emit an assembler pseudo-op, such as
2639          the MIPS `.set reorder' pseudo-op, then the static instruction order
2640          matters and it must be preserved.  */
2641       if (GET_CODE (p1) == ASM_INPUT || GET_CODE (p2) == ASM_INPUT
2642           || (GET_CODE (p1) == ASM_OPERANDS && MEM_VOLATILE_P (p1))
2643           || (GET_CODE (p2) == ASM_OPERANDS && MEM_VOLATILE_P (p2)))
2644         lose = 1;
2645
2646       if (lose || GET_CODE (p1) != GET_CODE (p2)
2647           || ! rtx_renumbered_equal_p (p1, p2))
2648         {
2649           /* The following code helps take care of G++ cleanups.  */
2650           rtx equiv1;
2651           rtx equiv2;
2652
2653           if (!lose && GET_CODE (p1) == GET_CODE (p2)
2654               && ((equiv1 = find_reg_note (i1, REG_EQUAL, NULL_RTX)) != 0
2655                   || (equiv1 = find_reg_note (i1, REG_EQUIV, NULL_RTX)) != 0)
2656               && ((equiv2 = find_reg_note (i2, REG_EQUAL, NULL_RTX)) != 0
2657                   || (equiv2 = find_reg_note (i2, REG_EQUIV, NULL_RTX)) != 0)
2658               /* If the equivalences are not to a constant, they may
2659                  reference pseudos that no longer exist, so we can't
2660                  use them.  */
2661               && CONSTANT_P (XEXP (equiv1, 0))
2662               && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
2663             {
2664               rtx s1 = single_set (i1);
2665               rtx s2 = single_set (i2);
2666               if (s1 != 0 && s2 != 0
2667                   && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
2668                 {
2669                   validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
2670                   validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
2671                   if (! rtx_renumbered_equal_p (p1, p2))
2672                     cancel_changes (0);
2673                   else if (apply_change_group ())
2674                     goto win;
2675                 }
2676             }
2677
2678           /* Insns fail to match; cross jumping is limited to the following
2679              insns.  */
2680
2681 #ifdef HAVE_cc0
2682           /* Don't allow the insn after a compare to be shared by
2683              cross-jumping unless the compare is also shared.
2684              Here, if either of these non-matching insns is a compare,
2685              exclude the following insn from possible cross-jumping.  */
2686           if (sets_cc0_p (p1) || sets_cc0_p (p2))
2687             last1 = afterlast1, last2 = afterlast2, ++minimum;
2688 #endif
2689
2690           /* If cross-jumping here will feed a jump-around-jump
2691              optimization, this jump won't cost extra, so reduce
2692              the minimum.  */
2693           if (GET_CODE (i1) == JUMP_INSN
2694               && JUMP_LABEL (i1)
2695               && prev_real_insn (JUMP_LABEL (i1)) == e1)
2696             --minimum;
2697           break;
2698         }
2699
2700     win:
2701       if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
2702         {
2703           /* Ok, this insn is potentially includable in a cross-jump here.  */
2704           afterlast1 = last1, afterlast2 = last2;
2705           last1 = i1, last2 = i2, --minimum;
2706         }
2707     }
2708
2709   if (minimum <= 0 && last1 != 0 && last1 != e1)
2710     *f1 = last1, *f2 = last2;
2711 }
2712
2713 static void
2714 do_cross_jump (insn, newjpos, newlpos)
2715      rtx insn, newjpos, newlpos;
2716 {
2717   /* Find an existing label at this point
2718      or make a new one if there is none.  */
2719   register rtx label = get_label_before (newlpos);
2720
2721   /* Make the same jump insn jump to the new point.  */
2722   if (GET_CODE (PATTERN (insn)) == RETURN)
2723     {
2724       /* Remove from jump chain of returns.  */
2725       delete_from_jump_chain (insn);
2726       /* Change the insn.  */
2727       PATTERN (insn) = gen_jump (label);
2728       INSN_CODE (insn) = -1;
2729       JUMP_LABEL (insn) = label;
2730       LABEL_NUSES (label)++;
2731       /* Add to new the jump chain.  */
2732       if (INSN_UID (label) < max_jump_chain
2733           && INSN_UID (insn) < max_jump_chain)
2734         {
2735           jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (label)];
2736           jump_chain[INSN_UID (label)] = insn;
2737         }
2738     }
2739   else
2740     redirect_jump (insn, label);
2741
2742   /* Delete the matching insns before the jump.  Also, remove any REG_EQUAL
2743      or REG_EQUIV note in the NEWLPOS stream that isn't also present in
2744      the NEWJPOS stream.  */
2745
2746   while (newjpos != insn)
2747     {
2748       rtx lnote;
2749
2750       for (lnote = REG_NOTES (newlpos); lnote; lnote = XEXP (lnote, 1))
2751         if ((REG_NOTE_KIND (lnote) == REG_EQUAL
2752              || REG_NOTE_KIND (lnote) == REG_EQUIV)
2753             && ! find_reg_note (newjpos, REG_EQUAL, XEXP (lnote, 0))
2754             && ! find_reg_note (newjpos, REG_EQUIV, XEXP (lnote, 0)))
2755           remove_note (newlpos, lnote);
2756
2757       delete_insn (newjpos);
2758       newjpos = next_real_insn (newjpos);
2759       newlpos = next_real_insn (newlpos);
2760     }
2761 }
2762 \f
2763 /* Return the label before INSN, or put a new label there.  */
2764
2765 rtx
2766 get_label_before (insn)
2767      rtx insn;
2768 {
2769   rtx label;
2770
2771   /* Find an existing label at this point
2772      or make a new one if there is none.  */
2773   label = prev_nonnote_insn (insn);
2774
2775   if (label == 0 || GET_CODE (label) != CODE_LABEL)
2776     {
2777       rtx prev = PREV_INSN (insn);
2778
2779       label = gen_label_rtx ();
2780       emit_label_after (label, prev);
2781       LABEL_NUSES (label) = 0;
2782     }
2783   return label;
2784 }
2785
2786 /* Return the label after INSN, or put a new label there.  */
2787
2788 rtx
2789 get_label_after (insn)
2790      rtx insn;
2791 {
2792   rtx label;
2793
2794   /* Find an existing label at this point
2795      or make a new one if there is none.  */
2796   label = next_nonnote_insn (insn);
2797
2798   if (label == 0 || GET_CODE (label) != CODE_LABEL)
2799     {
2800       label = gen_label_rtx ();
2801       emit_label_after (label, insn);
2802       LABEL_NUSES (label) = 0;
2803     }
2804   return label;
2805 }
2806 \f
2807 /* Return 1 if INSN is a jump that jumps to right after TARGET
2808    only on the condition that TARGET itself would drop through.
2809    Assumes that TARGET is a conditional jump.  */
2810
2811 static int
2812 jump_back_p (insn, target)
2813      rtx insn, target;
2814 {
2815   rtx cinsn, ctarget;
2816   enum rtx_code codei, codet;
2817
2818   if (simplejump_p (insn) || ! condjump_p (insn)
2819       || simplejump_p (target)
2820       || target != prev_real_insn (JUMP_LABEL (insn)))
2821     return 0;
2822
2823   cinsn = XEXP (SET_SRC (PATTERN (insn)), 0);
2824   ctarget = XEXP (SET_SRC (PATTERN (target)), 0);
2825
2826   codei = GET_CODE (cinsn);
2827   codet = GET_CODE (ctarget);
2828
2829   if (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx)
2830     {
2831       if (! can_reverse_comparison_p (cinsn, insn))
2832         return 0;
2833       codei = reverse_condition (codei);
2834     }
2835
2836   if (XEXP (SET_SRC (PATTERN (target)), 2) == pc_rtx)
2837     {
2838       if (! can_reverse_comparison_p (ctarget, target))
2839         return 0;
2840       codet = reverse_condition (codet);
2841     }
2842
2843   return (codei == codet
2844           && rtx_renumbered_equal_p (XEXP (cinsn, 0), XEXP (ctarget, 0))
2845           && rtx_renumbered_equal_p (XEXP (cinsn, 1), XEXP (ctarget, 1)));
2846 }
2847 \f
2848 /* Given a comparison, COMPARISON, inside a conditional jump insn, INSN,
2849    return non-zero if it is safe to reverse this comparison.  It is if our
2850    floating-point is not IEEE, if this is an NE or EQ comparison, or if
2851    this is known to be an integer comparison.  */
2852
2853 int
2854 can_reverse_comparison_p (comparison, insn)
2855      rtx comparison;
2856      rtx insn;
2857 {
2858   rtx arg0;
2859
2860   /* If this is not actually a comparison, we can't reverse it.  */
2861   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
2862     return 0;
2863
2864   if (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
2865       /* If this is an NE comparison, it is safe to reverse it to an EQ
2866          comparison and vice versa, even for floating point.  If no operands
2867          are NaNs, the reversal is valid.  If some operand is a NaN, EQ is
2868          always false and NE is always true, so the reversal is also valid.  */
2869       || flag_fast_math
2870       || GET_CODE (comparison) == NE
2871       || GET_CODE (comparison) == EQ)
2872     return 1;
2873
2874   arg0 = XEXP (comparison, 0);
2875
2876   /* Make sure ARG0 is one of the actual objects being compared.  If we
2877      can't do this, we can't be sure the comparison can be reversed.
2878
2879      Handle cc0 and a MODE_CC register.  */
2880   if ((GET_CODE (arg0) == REG && GET_MODE_CLASS (GET_MODE (arg0)) == MODE_CC)
2881 #ifdef HAVE_cc0
2882       || arg0 == cc0_rtx
2883 #endif
2884       )
2885     {
2886       rtx prev = prev_nonnote_insn (insn);
2887       rtx set = single_set (prev);
2888
2889       if (set == 0 || SET_DEST (set) != arg0)
2890         return 0;
2891
2892       arg0 = SET_SRC (set);
2893
2894       if (GET_CODE (arg0) == COMPARE)
2895         arg0 = XEXP (arg0, 0);
2896     }
2897
2898   /* We can reverse this if ARG0 is a CONST_INT or if its mode is
2899      not VOIDmode and neither a MODE_CC nor MODE_FLOAT type.  */
2900   return (GET_CODE (arg0) == CONST_INT
2901           || (GET_MODE (arg0) != VOIDmode
2902               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_CC
2903               && GET_MODE_CLASS (GET_MODE (arg0)) != MODE_FLOAT));
2904 }
2905
2906 /* Given an rtx-code for a comparison, return the code
2907    for the negated comparison.
2908    WATCH OUT!  reverse_condition is not safe to use on a jump
2909    that might be acting on the results of an IEEE floating point comparison,
2910    because of the special treatment of non-signaling nans in comparisons.
2911    Use can_reverse_comparison_p to be sure.  */
2912
2913 enum rtx_code
2914 reverse_condition (code)
2915      enum rtx_code code;
2916 {
2917   switch (code)
2918     {
2919     case EQ:
2920       return NE;
2921
2922     case NE:
2923       return EQ;
2924
2925     case GT:
2926       return LE;
2927
2928     case GE:
2929       return LT;
2930
2931     case LT:
2932       return GE;
2933
2934     case LE:
2935       return GT;
2936
2937     case GTU:
2938       return LEU;
2939
2940     case GEU:
2941       return LTU;
2942
2943     case LTU:
2944       return GEU;
2945
2946     case LEU:
2947       return GTU;
2948
2949     default:
2950       abort ();
2951       return UNKNOWN;
2952     }
2953 }
2954
2955 /* Similar, but return the code when two operands of a comparison are swapped.
2956    This IS safe for IEEE floating-point.  */
2957
2958 enum rtx_code
2959 swap_condition (code)
2960      enum rtx_code code;
2961 {
2962   switch (code)
2963     {
2964     case EQ:
2965     case NE:
2966       return code;
2967
2968     case GT:
2969       return LT;
2970
2971     case GE:
2972       return LE;
2973
2974     case LT:
2975       return GT;
2976
2977     case LE:
2978       return GE;
2979
2980     case GTU:
2981       return LTU;
2982
2983     case GEU:
2984       return LEU;
2985
2986     case LTU:
2987       return GTU;
2988
2989     case LEU:
2990       return GEU;
2991
2992     default:
2993       abort ();
2994       return UNKNOWN;
2995     }
2996 }
2997
2998 /* Given a comparison CODE, return the corresponding unsigned comparison.
2999    If CODE is an equality comparison or already an unsigned comparison,
3000    CODE is returned.  */
3001
3002 enum rtx_code
3003 unsigned_condition (code)
3004      enum rtx_code code;
3005 {
3006   switch (code)
3007     {
3008     case EQ:
3009     case NE:
3010     case GTU:
3011     case GEU:
3012     case LTU:
3013     case LEU:
3014       return code;
3015
3016     case GT:
3017       return GTU;
3018
3019     case GE:
3020       return GEU;
3021
3022     case LT:
3023       return LTU;
3024
3025     case LE:
3026       return LEU;
3027
3028     default:
3029       abort ();
3030     }
3031 }
3032
3033 /* Similarly, return the signed version of a comparison.  */
3034
3035 enum rtx_code
3036 signed_condition (code)
3037      enum rtx_code code;
3038 {
3039   switch (code)
3040     {
3041     case EQ:
3042     case NE:
3043     case GT:
3044     case GE:
3045     case LT:
3046     case LE:
3047       return code;
3048
3049     case GTU:
3050       return GT;
3051
3052     case GEU:
3053       return GE;
3054
3055     case LTU:
3056       return LT;
3057
3058     case LEU:
3059       return LE;
3060
3061     default:
3062       abort ();
3063     }
3064 }
3065 \f
3066 /* Return non-zero if CODE1 is more strict than CODE2, i.e., if the
3067    truth of CODE1 implies the truth of CODE2.  */
3068
3069 int
3070 comparison_dominates_p (code1, code2)
3071      enum rtx_code code1, code2;
3072 {
3073   if (code1 == code2)
3074     return 1;
3075
3076   switch (code1)
3077     {
3078     case EQ:
3079       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU)
3080         return 1;
3081       break;
3082
3083     case LT:
3084       if (code2 == LE || code2 == NE)
3085         return 1;
3086       break;
3087
3088     case GT:
3089       if (code2 == GE || code2 == NE)
3090         return 1;
3091       break;
3092
3093     case LTU:
3094       if (code2 == LEU || code2 == NE)
3095         return 1;
3096       break;
3097
3098     case GTU:
3099       if (code2 == GEU || code2 == NE)
3100         return 1;
3101       break;
3102
3103     default:
3104       break;
3105     }
3106
3107   return 0;
3108 }
3109 \f
3110 /* Return 1 if INSN is an unconditional jump and nothing else.  */
3111
3112 int
3113 simplejump_p (insn)
3114      rtx insn;
3115 {
3116   return (GET_CODE (insn) == JUMP_INSN
3117           && GET_CODE (PATTERN (insn)) == SET
3118           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
3119           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
3120 }
3121
3122 /* Return nonzero if INSN is a (possibly) conditional jump
3123    and nothing more.  */
3124
3125 int
3126 condjump_p (insn)
3127      rtx insn;
3128 {
3129   register rtx x = PATTERN (insn);
3130   if (GET_CODE (x) != SET)
3131     return 0;
3132   if (GET_CODE (SET_DEST (x)) != PC)
3133     return 0;
3134   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
3135     return 1;
3136   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
3137     return 0;
3138   if (XEXP (SET_SRC (x), 2) == pc_rtx
3139       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
3140           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
3141     return 1;
3142   if (XEXP (SET_SRC (x), 1) == pc_rtx
3143       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
3144           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
3145     return 1;
3146   return 0;
3147 }
3148
3149 /* Return nonzero if INSN is a (possibly) conditional jump
3150    and nothing more.  */
3151
3152 int
3153 condjump_in_parallel_p (insn)
3154      rtx insn;
3155 {
3156   register rtx x = PATTERN (insn);
3157
3158   if (GET_CODE (x) != PARALLEL)
3159     return 0;
3160   else
3161     x = XVECEXP (x, 0, 0);
3162
3163   if (GET_CODE (x) != SET)
3164     return 0;
3165   if (GET_CODE (SET_DEST (x)) != PC)
3166     return 0;
3167   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
3168     return 1;
3169   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
3170     return 0;
3171   if (XEXP (SET_SRC (x), 2) == pc_rtx
3172       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
3173           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
3174     return 1;
3175   if (XEXP (SET_SRC (x), 1) == pc_rtx
3176       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
3177           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
3178     return 1;
3179   return 0;
3180 }
3181
3182 /* Return 1 if X is an RTX that does nothing but set the condition codes
3183    and CLOBBER or USE registers.
3184    Return -1 if X does explicitly set the condition codes,
3185    but also does other things.  */
3186
3187 int
3188 sets_cc0_p (x)
3189      rtx x;
3190 {
3191 #ifdef HAVE_cc0
3192   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
3193     return 1;
3194   if (GET_CODE (x) == PARALLEL)
3195     {
3196       int i;
3197       int sets_cc0 = 0;
3198       int other_things = 0;
3199       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
3200         {
3201           if (GET_CODE (XVECEXP (x, 0, i)) == SET
3202               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
3203             sets_cc0 = 1;
3204           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
3205             other_things = 1;
3206         }
3207       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
3208     }
3209   return 0;
3210 #else
3211   abort ();
3212 #endif
3213 }
3214 \f
3215 /* Follow any unconditional jump at LABEL;
3216    return the ultimate label reached by any such chain of jumps.
3217    If LABEL is not followed by a jump, return LABEL.
3218    If the chain loops or we can't find end, return LABEL,
3219    since that tells caller to avoid changing the insn.
3220
3221    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
3222    a USE or CLOBBER.  */
3223
3224 rtx
3225 follow_jumps (label)
3226      rtx label;
3227 {
3228   register rtx insn;
3229   register rtx next;
3230   register rtx value = label;
3231   register int depth;
3232
3233   for (depth = 0;
3234        (depth < 10
3235         && (insn = next_active_insn (value)) != 0
3236         && GET_CODE (insn) == JUMP_INSN
3237         && ((JUMP_LABEL (insn) != 0 && simplejump_p (insn))
3238             || GET_CODE (PATTERN (insn)) == RETURN)
3239         && (next = NEXT_INSN (insn))
3240         && GET_CODE (next) == BARRIER);
3241        depth++)
3242     {
3243       /* Don't chain through the insn that jumps into a loop
3244          from outside the loop,
3245          since that would create multiple loop entry jumps
3246          and prevent loop optimization.  */
3247       rtx tem;
3248       if (!reload_completed)
3249         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
3250           if (GET_CODE (tem) == NOTE
3251               && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
3252                   /* ??? Optional.  Disables some optimizations, but makes
3253                      gcov output more accurate with -O.  */
3254                   || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
3255             return value;
3256
3257       /* If we have found a cycle, make the insn jump to itself.  */
3258       if (JUMP_LABEL (insn) == label)
3259         return label;
3260
3261       tem = next_active_insn (JUMP_LABEL (insn));
3262       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
3263                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
3264         break;
3265
3266       value = JUMP_LABEL (insn);
3267     }
3268   if (depth == 10)
3269     return label;
3270   return value;
3271 }
3272
3273 /* Assuming that field IDX of X is a vector of label_refs,
3274    replace each of them by the ultimate label reached by it.
3275    Return nonzero if a change is made.
3276    If IGNORE_LOOPS is 0, we do not chain across a NOTE_INSN_LOOP_BEG.  */
3277
3278 static int
3279 tension_vector_labels (x, idx)
3280      register rtx x;
3281      register int idx;
3282 {
3283   int changed = 0;
3284   register int i;
3285   for (i = XVECLEN (x, idx) - 1; i >= 0; i--)
3286     {
3287       register rtx olabel = XEXP (XVECEXP (x, idx, i), 0);
3288       register rtx nlabel = follow_jumps (olabel);
3289       if (nlabel && nlabel != olabel)
3290         {
3291           XEXP (XVECEXP (x, idx, i), 0) = nlabel;
3292           ++LABEL_NUSES (nlabel);
3293           if (--LABEL_NUSES (olabel) == 0)
3294             delete_insn (olabel);
3295           changed = 1;
3296         }
3297     }
3298   return changed;
3299 }
3300 \f
3301 /* Find all CODE_LABELs referred to in X, and increment their use counts.
3302    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
3303    in INSN, then store one of them in JUMP_LABEL (INSN).
3304    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
3305    referenced in INSN, add a REG_LABEL note containing that label to INSN.
3306    Also, when there are consecutive labels, canonicalize on the last of them.
3307
3308    Note that two labels separated by a loop-beginning note
3309    must be kept distinct if we have not yet done loop-optimization,
3310    because the gap between them is where loop-optimize
3311    will want to move invariant code to.  CROSS_JUMP tells us
3312    that loop-optimization is done with.
3313
3314    Once reload has completed (CROSS_JUMP non-zero), we need not consider
3315    two labels distinct if they are separated by only USE or CLOBBER insns.  */
3316
3317 static void
3318 mark_jump_label (x, insn, cross_jump)
3319      register rtx x;
3320      rtx insn;
3321      int cross_jump;
3322 {
3323   register RTX_CODE code = GET_CODE (x);
3324   register int i;
3325   register char *fmt;
3326
3327   switch (code)
3328     {
3329     case PC:
3330     case CC0:
3331     case REG:
3332     case SUBREG:
3333     case CONST_INT:
3334     case SYMBOL_REF:
3335     case CONST_DOUBLE:
3336     case CLOBBER:
3337     case CALL:
3338       return;
3339
3340     case MEM:
3341       /* If this is a constant-pool reference, see if it is a label.  */
3342       if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
3343           && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
3344         mark_jump_label (get_pool_constant (XEXP (x, 0)), insn, cross_jump);
3345       break;
3346
3347     case LABEL_REF:
3348       {
3349         rtx label = XEXP (x, 0);
3350         rtx olabel = label;
3351         rtx note;
3352         rtx next;
3353
3354         if (GET_CODE (label) != CODE_LABEL)
3355           abort ();
3356
3357         /* Ignore references to labels of containing functions.  */
3358         if (LABEL_REF_NONLOCAL_P (x))
3359           break;
3360
3361         /* If there are other labels following this one,
3362            replace it with the last of the consecutive labels.  */
3363         for (next = NEXT_INSN (label); next; next = NEXT_INSN (next))
3364           {
3365             if (GET_CODE (next) == CODE_LABEL)
3366               label = next;
3367             else if (cross_jump && GET_CODE (next) == INSN
3368                      && (GET_CODE (PATTERN (next)) == USE
3369                          || GET_CODE (PATTERN (next)) == CLOBBER))
3370               continue;
3371             else if (GET_CODE (next) != NOTE)
3372               break;
3373             else if (! cross_jump
3374                      && (NOTE_LINE_NUMBER (next) == NOTE_INSN_LOOP_BEG
3375                          || NOTE_LINE_NUMBER (next) == NOTE_INSN_FUNCTION_END
3376                          /* ??? Optional.  Disables some optimizations, but
3377                             makes gcov output more accurate with -O.  */
3378                          || (flag_test_coverage && NOTE_LINE_NUMBER (next) > 0)))
3379               break;
3380           }
3381
3382         XEXP (x, 0) = label;
3383         if (! insn || ! INSN_DELETED_P (insn))
3384           ++LABEL_NUSES (label);
3385
3386         if (insn)
3387           {
3388             if (GET_CODE (insn) == JUMP_INSN)
3389               JUMP_LABEL (insn) = label;
3390
3391             /* If we've changed OLABEL and we had a REG_LABEL note
3392                for it, update it as well.  */
3393             else if (label != olabel
3394                      && (note = find_reg_note (insn, REG_LABEL, olabel)) != 0)
3395               XEXP (note, 0) = label;
3396
3397             /* Otherwise, add a REG_LABEL note for LABEL unless there already
3398                is one.  */
3399             else if (! find_reg_note (insn, REG_LABEL, label))
3400               {
3401                 /* This code used to ignore labels which refered to dispatch
3402                    tables to avoid flow.c generating worse code.
3403
3404                    However, in the presense of global optimizations like
3405                    gcse which call find_basic_blocks without calling
3406                    life_analysis, not recording such labels will lead
3407                    to compiler aborts because of inconsistencies in the
3408                    flow graph.  So we go ahead and record the label.
3409
3410                    It may also be the case that the optimization argument
3411                    is no longer valid because of the more accurate cfg
3412                    we build in find_basic_blocks -- it no longer pessimizes
3413                    code when it finds a REG_LABEL note.  */
3414                 REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, label,
3415                                                       REG_NOTES (insn));
3416               }
3417           }
3418         return;
3419       }
3420
3421   /* Do walk the labels in a vector, but not the first operand of an
3422      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
3423     case ADDR_VEC:
3424     case ADDR_DIFF_VEC:
3425       if (! INSN_DELETED_P (insn))
3426         {
3427           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
3428
3429           for (i = 0; i < XVECLEN (x, eltnum); i++)
3430             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, cross_jump);
3431         }
3432       return;
3433
3434     default:
3435       break;
3436     }
3437
3438   fmt = GET_RTX_FORMAT (code);
3439   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3440     {
3441       if (fmt[i] == 'e')
3442         mark_jump_label (XEXP (x, i), insn, cross_jump);
3443       else if (fmt[i] == 'E')
3444         {
3445           register int j;
3446           for (j = 0; j < XVECLEN (x, i); j++)
3447             mark_jump_label (XVECEXP (x, i, j), insn, cross_jump);
3448         }
3449     }
3450 }
3451
3452 /* If all INSN does is set the pc, delete it,
3453    and delete the insn that set the condition codes for it
3454    if that's what the previous thing was.  */
3455
3456 void
3457 delete_jump (insn)
3458      rtx insn;
3459 {
3460   register rtx set = single_set (insn);
3461
3462   if (set && GET_CODE (SET_DEST (set)) == PC)
3463     delete_computation (insn);
3464 }
3465
3466 /* Delete INSN and recursively delete insns that compute values used only
3467    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
3468    If we are running before flow.c, we need do nothing since flow.c will
3469    delete dead code.  We also can't know if the registers being used are
3470    dead or not at this point.
3471
3472    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
3473    nothing other than set a register that dies in this insn, we can delete
3474    that insn as well.
3475
3476    On machines with CC0, if CC0 is used in this insn, we may be able to
3477    delete the insn that set it.  */
3478
3479 static void
3480 delete_computation (insn)
3481      rtx insn;
3482 {
3483   rtx note, next;
3484
3485 #ifdef HAVE_cc0
3486   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
3487     {
3488       rtx prev = prev_nonnote_insn (insn);
3489       /* We assume that at this stage
3490          CC's are always set explicitly
3491          and always immediately before the jump that
3492          will use them.  So if the previous insn
3493          exists to set the CC's, delete it
3494          (unless it performs auto-increments, etc.).  */
3495       if (prev && GET_CODE (prev) == INSN
3496           && sets_cc0_p (PATTERN (prev)))
3497         {
3498           if (sets_cc0_p (PATTERN (prev)) > 0
3499               && !FIND_REG_INC_NOTE (prev, NULL_RTX))
3500             delete_computation (prev);
3501           else
3502             /* Otherwise, show that cc0 won't be used.  */
3503             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
3504                                                   cc0_rtx, REG_NOTES (prev));
3505         }
3506     }
3507 #endif
3508
3509   for (note = REG_NOTES (insn); note; note = next)
3510     {
3511       rtx our_prev;
3512
3513       next = XEXP (note, 1);
3514
3515       if (REG_NOTE_KIND (note) != REG_DEAD
3516           /* Verify that the REG_NOTE is legitimate.  */
3517           || GET_CODE (XEXP (note, 0)) != REG)
3518         continue;
3519
3520       for (our_prev = prev_nonnote_insn (insn);
3521            our_prev && GET_CODE (our_prev) == INSN;
3522            our_prev = prev_nonnote_insn (our_prev))
3523         {
3524           /* If we reach a SEQUENCE, it is too complex to try to
3525              do anything with it, so give up.  */
3526           if (GET_CODE (PATTERN (our_prev)) == SEQUENCE)
3527             break;
3528
3529           if (GET_CODE (PATTERN (our_prev)) == USE
3530               && GET_CODE (XEXP (PATTERN (our_prev), 0)) == INSN)
3531             /* reorg creates USEs that look like this.  We leave them
3532                alone because reorg needs them for its own purposes.  */
3533             break;
3534
3535           if (reg_set_p (XEXP (note, 0), PATTERN (our_prev)))
3536             {
3537               if (FIND_REG_INC_NOTE (our_prev, NULL_RTX))
3538                 break;
3539
3540               if (GET_CODE (PATTERN (our_prev)) == PARALLEL)
3541                 {
3542                   /* If we find a SET of something else, we can't
3543                      delete the insn.  */
3544
3545                   int i;
3546
3547                   for (i = 0; i < XVECLEN (PATTERN (our_prev), 0); i++)
3548                     {
3549                       rtx part = XVECEXP (PATTERN (our_prev), 0, i);
3550
3551                       if (GET_CODE (part) == SET
3552                           && SET_DEST (part) != XEXP (note, 0))
3553                         break;
3554                     }
3555
3556                   if (i == XVECLEN (PATTERN (our_prev), 0))
3557                     delete_computation (our_prev);
3558                 }
3559               else if (GET_CODE (PATTERN (our_prev)) == SET
3560                        && SET_DEST (PATTERN (our_prev)) == XEXP (note, 0))
3561                 delete_computation (our_prev);
3562
3563               break;
3564             }
3565
3566           /* If OUR_PREV references the register that dies here, it is an
3567              additional use.  Hence any prior SET isn't dead.  However, this
3568              insn becomes the new place for the REG_DEAD note.  */
3569           if (reg_overlap_mentioned_p (XEXP (note, 0),
3570                                        PATTERN (our_prev)))
3571             {
3572               XEXP (note, 1) = REG_NOTES (our_prev);
3573               REG_NOTES (our_prev) = note;
3574               break;
3575             }
3576         }
3577     }
3578
3579   delete_insn (insn);
3580 }
3581 \f
3582 /* Delete insn INSN from the chain of insns and update label ref counts.
3583    May delete some following insns as a consequence; may even delete
3584    a label elsewhere and insns that follow it.
3585
3586    Returns the first insn after INSN that was not deleted.  */
3587
3588 rtx
3589 delete_insn (insn)
3590      register rtx insn;
3591 {
3592   register rtx next = NEXT_INSN (insn);
3593   register rtx prev = PREV_INSN (insn);
3594   register int was_code_label = (GET_CODE (insn) == CODE_LABEL);
3595   register int dont_really_delete = 0;
3596
3597   while (next && INSN_DELETED_P (next))
3598     next = NEXT_INSN (next);
3599
3600   /* This insn is already deleted => return first following nondeleted.  */
3601   if (INSN_DELETED_P (insn))
3602     return next;
3603
3604   /* Don't delete user-declared labels.  Convert them to special NOTEs
3605      instead.  */
3606   if (was_code_label && LABEL_NAME (insn) != 0
3607       && optimize && ! dont_really_delete)
3608     {
3609       PUT_CODE (insn, NOTE);
3610       NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
3611       NOTE_SOURCE_FILE (insn) = 0;
3612       dont_really_delete = 1;
3613     }
3614   else
3615     /* Mark this insn as deleted.  */
3616     INSN_DELETED_P (insn) = 1;
3617
3618   /* If this is an unconditional jump, delete it from the jump chain.  */
3619   if (simplejump_p (insn))
3620     delete_from_jump_chain (insn);
3621
3622   /* If instruction is followed by a barrier,
3623      delete the barrier too.  */
3624
3625   if (next != 0 && GET_CODE (next) == BARRIER)
3626     {
3627       INSN_DELETED_P (next) = 1;
3628       next = NEXT_INSN (next);
3629     }
3630
3631   /* Patch out INSN (and the barrier if any) */
3632
3633   if (optimize && ! dont_really_delete)
3634     {
3635       if (prev)
3636         {
3637           NEXT_INSN (prev) = next;
3638           if (GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SEQUENCE)
3639             NEXT_INSN (XVECEXP (PATTERN (prev), 0,
3640                                 XVECLEN (PATTERN (prev), 0) - 1)) = next;
3641         }
3642
3643       if (next)
3644         {
3645           PREV_INSN (next) = prev;
3646           if (GET_CODE (next) == INSN && GET_CODE (PATTERN (next)) == SEQUENCE)
3647             PREV_INSN (XVECEXP (PATTERN (next), 0, 0)) = prev;
3648         }
3649
3650       if (prev && NEXT_INSN (prev) == 0)
3651         set_last_insn (prev);
3652     }
3653
3654   /* If deleting a jump, decrement the count of the label,
3655      and delete the label if it is now unused.  */
3656
3657   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
3658     if (--LABEL_NUSES (JUMP_LABEL (insn)) == 0)
3659       {
3660         /* This can delete NEXT or PREV,
3661            either directly if NEXT is JUMP_LABEL (INSN),
3662            or indirectly through more levels of jumps.  */
3663         delete_insn (JUMP_LABEL (insn));
3664         /* I feel a little doubtful about this loop,
3665            but I see no clean and sure alternative way
3666            to find the first insn after INSN that is not now deleted.
3667            I hope this works.  */
3668         while (next && INSN_DELETED_P (next))
3669           next = NEXT_INSN (next);
3670         return next;
3671       }
3672
3673   /* Likewise if we're deleting a dispatch table.  */
3674
3675   if (GET_CODE (insn) == JUMP_INSN
3676       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3677           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3678     {
3679       rtx pat = PATTERN (insn);
3680       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
3681       int len = XVECLEN (pat, diff_vec_p);
3682
3683       for (i = 0; i < len; i++)
3684         if (--LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
3685           delete_insn (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
3686       while (next && INSN_DELETED_P (next))
3687         next = NEXT_INSN (next);
3688       return next;
3689     }
3690
3691   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
3692     prev = PREV_INSN (prev);
3693
3694   /* If INSN was a label and a dispatch table follows it,
3695      delete the dispatch table.  The tablejump must have gone already.
3696      It isn't useful to fall through into a table.  */
3697
3698   if (was_code_label
3699       && NEXT_INSN (insn) != 0
3700       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
3701       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
3702           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
3703     next = delete_insn (NEXT_INSN (insn));
3704
3705   /* If INSN was a label, delete insns following it if now unreachable.  */
3706
3707   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
3708     {
3709       register RTX_CODE code;
3710       while (next != 0
3711              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
3712                  || code == NOTE || code == BARRIER
3713                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
3714         {
3715           if (code == NOTE
3716               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
3717             next = NEXT_INSN (next);
3718           /* Keep going past other deleted labels to delete what follows.  */
3719           else if (code == CODE_LABEL && INSN_DELETED_P (next))
3720             next = NEXT_INSN (next);
3721           else
3722             /* Note: if this deletes a jump, it can cause more
3723                deletion of unreachable code, after a different label.
3724                As long as the value from this recursive call is correct,
3725                this invocation functions correctly.  */
3726             next = delete_insn (next);
3727         }
3728     }
3729
3730   return next;
3731 }
3732
3733 /* Advance from INSN till reaching something not deleted
3734    then return that.  May return INSN itself.  */
3735
3736 rtx
3737 next_nondeleted_insn (insn)
3738      rtx insn;
3739 {
3740   while (INSN_DELETED_P (insn))
3741     insn = NEXT_INSN (insn);
3742   return insn;
3743 }
3744 \f
3745 /* Delete a range of insns from FROM to TO, inclusive.
3746    This is for the sake of peephole optimization, so assume
3747    that whatever these insns do will still be done by a new
3748    peephole insn that will replace them.  */
3749
3750 void
3751 delete_for_peephole (from, to)
3752      register rtx from, to;
3753 {
3754   register rtx insn = from;
3755
3756   while (1)
3757     {
3758       register rtx next = NEXT_INSN (insn);
3759       register rtx prev = PREV_INSN (insn);
3760
3761       if (GET_CODE (insn) != NOTE)
3762         {
3763           INSN_DELETED_P (insn) = 1;
3764
3765           /* Patch this insn out of the chain.  */
3766           /* We don't do this all at once, because we
3767              must preserve all NOTEs.  */
3768           if (prev)
3769             NEXT_INSN (prev) = next;
3770
3771           if (next)
3772             PREV_INSN (next) = prev;
3773         }
3774
3775       if (insn == to)
3776         break;
3777       insn = next;
3778     }
3779
3780   /* Note that if TO is an unconditional jump
3781      we *do not* delete the BARRIER that follows,
3782      since the peephole that replaces this sequence
3783      is also an unconditional jump in that case.  */
3784 }
3785 \f
3786 /* Invert the condition of the jump JUMP, and make it jump
3787    to label NLABEL instead of where it jumps now.  */
3788
3789 int
3790 invert_jump (jump, nlabel)
3791      rtx jump, nlabel;
3792 {
3793   /* We have to either invert the condition and change the label or
3794      do neither.  Either operation could fail.  We first try to invert
3795      the jump. If that succeeds, we try changing the label.  If that fails,
3796      we invert the jump back to what it was.  */
3797
3798   if (! invert_exp (PATTERN (jump), jump))
3799     return 0;
3800
3801   if (redirect_jump (jump, nlabel))
3802     {
3803       if (flag_branch_probabilities)
3804         {
3805           rtx note = find_reg_note (jump, REG_BR_PROB, 0);
3806
3807           /* An inverted jump means that a probability taken becomes a
3808              probability not taken.  Subtract the branch probability from the
3809              probability base to convert it back to a taken probability.
3810              (We don't flip the probability on a branch that's never taken.  */
3811           if (note && XINT (XEXP (note, 0), 0) >= 0)
3812             XINT (XEXP (note, 0), 0) = REG_BR_PROB_BASE - XINT (XEXP (note, 0), 0);
3813         }
3814
3815       return 1;
3816     }
3817
3818   if (! invert_exp (PATTERN (jump), jump))
3819     /* This should just be putting it back the way it was.  */
3820     abort ();
3821
3822   return  0;
3823 }
3824
3825 /* Invert the jump condition of rtx X contained in jump insn, INSN.
3826
3827    Return 1 if we can do so, 0 if we cannot find a way to do so that
3828    matches a pattern.  */
3829
3830 int
3831 invert_exp (x, insn)
3832      rtx x;
3833      rtx insn;
3834 {
3835   register RTX_CODE code;
3836   register int i;
3837   register char *fmt;
3838
3839   code = GET_CODE (x);
3840
3841   if (code == IF_THEN_ELSE)
3842     {
3843       register rtx comp = XEXP (x, 0);
3844       register rtx tem;
3845
3846       /* We can do this in two ways:  The preferable way, which can only
3847          be done if this is not an integer comparison, is to reverse
3848          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
3849          of the IF_THEN_ELSE.  If we can't do either, fail.  */
3850
3851       if (can_reverse_comparison_p (comp, insn)
3852           && validate_change (insn, &XEXP (x, 0),
3853                               gen_rtx_fmt_ee (reverse_condition (GET_CODE (comp)),
3854                                               GET_MODE (comp), XEXP (comp, 0),
3855                                               XEXP (comp, 1)), 0))
3856         return 1;
3857
3858       tem = XEXP (x, 1);
3859       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
3860       validate_change (insn, &XEXP (x, 2), tem, 1);
3861       return apply_change_group ();
3862     }
3863
3864   fmt = GET_RTX_FORMAT (code);
3865   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3866     {
3867       if (fmt[i] == 'e')
3868         if (! invert_exp (XEXP (x, i), insn))
3869           return 0;
3870       if (fmt[i] == 'E')
3871         {
3872           register int j;
3873           for (j = 0; j < XVECLEN (x, i); j++)
3874             if (!invert_exp (XVECEXP (x, i, j), insn))
3875               return 0;
3876         }
3877     }
3878
3879   return 1;
3880 }
3881 \f
3882 /* Make jump JUMP jump to label NLABEL instead of where it jumps now.
3883    If the old jump target label is unused as a result,
3884    it and the code following it may be deleted.
3885
3886    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
3887    RETURN insn.
3888
3889    The return value will be 1 if the change was made, 0 if it wasn't (this
3890    can only occur for NLABEL == 0).  */
3891
3892 int
3893 redirect_jump (jump, nlabel)
3894      rtx jump, nlabel;
3895 {
3896   register rtx olabel = JUMP_LABEL (jump);
3897
3898   if (nlabel == olabel)
3899     return 1;
3900
3901   if (! redirect_exp (&PATTERN (jump), olabel, nlabel, jump))
3902     return 0;
3903
3904   /* If this is an unconditional branch, delete it from the jump_chain of
3905      OLABEL and add it to the jump_chain of NLABEL (assuming both labels
3906      have UID's in range and JUMP_CHAIN is valid).  */
3907   if (jump_chain && (simplejump_p (jump)
3908                      || GET_CODE (PATTERN (jump)) == RETURN))
3909     {
3910       int label_index = nlabel ? INSN_UID (nlabel) : 0;
3911
3912       delete_from_jump_chain (jump);
3913       if (label_index < max_jump_chain
3914           && INSN_UID (jump) < max_jump_chain)
3915         {
3916           jump_chain[INSN_UID (jump)] = jump_chain[label_index];
3917           jump_chain[label_index] = jump;
3918         }
3919     }
3920
3921   JUMP_LABEL (jump) = nlabel;
3922   if (nlabel)
3923     ++LABEL_NUSES (nlabel);
3924
3925   if (olabel && --LABEL_NUSES (olabel) == 0)
3926     delete_insn (olabel);
3927
3928   return 1;
3929 }
3930
3931 /* Delete the instruction JUMP from any jump chain it might be on.  */
3932
3933 static void
3934 delete_from_jump_chain (jump)
3935      rtx jump;
3936 {
3937   int index;
3938   rtx olabel = JUMP_LABEL (jump);
3939
3940   /* Handle unconditional jumps.  */
3941   if (jump_chain && olabel != 0
3942       && INSN_UID (olabel) < max_jump_chain
3943       && simplejump_p (jump))
3944     index = INSN_UID (olabel);
3945   /* Handle return insns.  */
3946   else if (jump_chain && GET_CODE (PATTERN (jump)) == RETURN)
3947     index = 0;
3948   else return;
3949
3950   if (jump_chain[index] == jump)
3951     jump_chain[index] = jump_chain[INSN_UID (jump)];
3952   else
3953     {
3954       rtx insn;
3955
3956       for (insn = jump_chain[index];
3957            insn != 0;
3958            insn = jump_chain[INSN_UID (insn)])
3959         if (jump_chain[INSN_UID (insn)] == jump)
3960           {
3961             jump_chain[INSN_UID (insn)] = jump_chain[INSN_UID (jump)];
3962             break;
3963           }
3964     }
3965 }
3966
3967 /* If NLABEL is nonzero, throughout the rtx at LOC,
3968    alter (LABEL_REF OLABEL) to (LABEL_REF NLABEL).  If OLABEL is
3969    zero, alter (RETURN) to (LABEL_REF NLABEL).
3970
3971    If NLABEL is zero, alter (LABEL_REF OLABEL) to (RETURN) and check
3972    validity with validate_change.  Convert (set (pc) (label_ref olabel))
3973    to (return).
3974
3975    Return 0 if we found a change we would like to make but it is invalid.
3976    Otherwise, return 1.  */
3977
3978 int
3979 redirect_exp (loc, olabel, nlabel, insn)
3980      rtx *loc;
3981      rtx olabel, nlabel;
3982      rtx insn;
3983 {
3984   register rtx x = *loc;
3985   register RTX_CODE code = GET_CODE (x);
3986   register int i;
3987   register char *fmt;
3988
3989   if (code == LABEL_REF)
3990     {
3991       if (XEXP (x, 0) == olabel)
3992         {
3993           if (nlabel)
3994             XEXP (x, 0) = nlabel;
3995           else
3996             return validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 0);
3997           return 1;
3998         }
3999     }
4000   else if (code == RETURN && olabel == 0)
4001     {
4002       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
4003       if (loc == &PATTERN (insn))
4004         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
4005       return validate_change (insn, loc, x, 0);
4006     }
4007
4008   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
4009       && GET_CODE (SET_SRC (x)) == LABEL_REF
4010       && XEXP (SET_SRC (x), 0) == olabel)
4011     return validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 0);
4012
4013   fmt = GET_RTX_FORMAT (code);
4014   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4015     {
4016       if (fmt[i] == 'e')
4017         if (! redirect_exp (&XEXP (x, i), olabel, nlabel, insn))
4018           return 0;
4019       if (fmt[i] == 'E')
4020         {
4021           register int j;
4022           for (j = 0; j < XVECLEN (x, i); j++)
4023             if (! redirect_exp (&XVECEXP (x, i, j), olabel, nlabel, insn))
4024               return 0;
4025         }
4026     }
4027
4028   return 1;
4029 }
4030 \f
4031 /* Make jump JUMP jump to label NLABEL, assuming it used to be a tablejump.
4032
4033    If the old jump target label (before the dispatch table) becomes unused,
4034    it and the dispatch table may be deleted.  In that case, find the insn
4035    before the jump references that label and delete it and logical successors
4036    too.  */
4037
4038 static void
4039 redirect_tablejump (jump, nlabel)
4040      rtx jump, nlabel;
4041 {
4042   register rtx olabel = JUMP_LABEL (jump);
4043
4044   /* Add this jump to the jump_chain of NLABEL.  */
4045   if (jump_chain && INSN_UID (nlabel) < max_jump_chain
4046       && INSN_UID (jump) < max_jump_chain)
4047     {
4048       jump_chain[INSN_UID (jump)] = jump_chain[INSN_UID (nlabel)];
4049       jump_chain[INSN_UID (nlabel)] = jump;
4050     }
4051
4052   PATTERN (jump) = gen_jump (nlabel);
4053   JUMP_LABEL (jump) = nlabel;
4054   ++LABEL_NUSES (nlabel);
4055   INSN_CODE (jump) = -1;
4056
4057   if (--LABEL_NUSES (olabel) == 0)
4058     {
4059       delete_labelref_insn (jump, olabel, 0);
4060       delete_insn (olabel);
4061     }
4062 }
4063
4064 /* Find the insn referencing LABEL that is a logical predecessor of INSN.
4065    If we found one, delete it and then delete this insn if DELETE_THIS is
4066    non-zero.  Return non-zero if INSN or a predecessor references LABEL.  */
4067
4068 static int
4069 delete_labelref_insn (insn, label, delete_this)
4070      rtx insn, label;
4071      int delete_this;
4072 {
4073   int deleted = 0;
4074   rtx link;
4075
4076   if (GET_CODE (insn) != NOTE
4077       && reg_mentioned_p (label, PATTERN (insn)))
4078     {
4079       if (delete_this)
4080         {
4081           delete_insn (insn);
4082           deleted = 1;
4083         }
4084       else
4085         return 1;
4086     }
4087
4088   for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
4089     if (delete_labelref_insn (XEXP (link, 0), label, 1))
4090       {
4091         if (delete_this)
4092           {
4093             delete_insn (insn);
4094             deleted = 1;
4095           }
4096         else
4097           return 1;
4098       }
4099
4100   return deleted;
4101 }
4102 \f
4103 /* Like rtx_equal_p except that it considers two REGs as equal
4104    if they renumber to the same value and considers two commutative
4105    operations to be the same if the order of the operands has been
4106    reversed.  */
4107
4108 int
4109 rtx_renumbered_equal_p (x, y)
4110      rtx x, y;
4111 {
4112   register int i;
4113   register RTX_CODE code = GET_CODE (x);
4114   register char *fmt;
4115
4116   if (x == y)
4117     return 1;
4118
4119   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
4120       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
4121                                   && GET_CODE (SUBREG_REG (y)) == REG)))
4122     {
4123       int reg_x = -1, reg_y = -1;
4124       int word_x = 0, word_y = 0;
4125
4126       if (GET_MODE (x) != GET_MODE (y))
4127         return 0;
4128
4129       /* If we haven't done any renumbering, don't
4130          make any assumptions.  */
4131       if (reg_renumber == 0)
4132         return rtx_equal_p (x, y);
4133
4134       if (code == SUBREG)
4135         {
4136           reg_x = REGNO (SUBREG_REG (x));
4137           word_x = SUBREG_WORD (x);
4138
4139           if (reg_renumber[reg_x] >= 0)
4140             {
4141               reg_x = reg_renumber[reg_x] + word_x;
4142               word_x = 0;
4143             }
4144         }
4145
4146       else
4147         {
4148           reg_x = REGNO (x);
4149           if (reg_renumber[reg_x] >= 0)
4150             reg_x = reg_renumber[reg_x];
4151         }
4152
4153       if (GET_CODE (y) == SUBREG)
4154         {
4155           reg_y = REGNO (SUBREG_REG (y));
4156           word_y = SUBREG_WORD (y);
4157
4158           if (reg_renumber[reg_y] >= 0)
4159             {
4160               reg_y = reg_renumber[reg_y];
4161               word_y = 0;
4162             }
4163         }
4164
4165       else
4166         {
4167           reg_y = REGNO (y);
4168           if (reg_renumber[reg_y] >= 0)
4169             reg_y = reg_renumber[reg_y];
4170         }
4171
4172       return reg_x >= 0 && reg_x == reg_y && word_x == word_y;
4173     }
4174
4175   /* Now we have disposed of all the cases
4176      in which different rtx codes can match.  */
4177   if (code != GET_CODE (y))
4178     return 0;
4179
4180   switch (code)
4181     {
4182     case PC:
4183     case CC0:
4184     case ADDR_VEC:
4185     case ADDR_DIFF_VEC:
4186       return 0;
4187
4188     case CONST_INT:
4189       return INTVAL (x) == INTVAL (y);
4190
4191     case LABEL_REF:
4192       /* We can't assume nonlocal labels have their following insns yet.  */
4193       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
4194         return XEXP (x, 0) == XEXP (y, 0);
4195
4196       /* Two label-refs are equivalent if they point at labels
4197          in the same position in the instruction stream.  */
4198       return (next_real_insn (XEXP (x, 0))
4199               == next_real_insn (XEXP (y, 0)));
4200
4201     case SYMBOL_REF:
4202       return XSTR (x, 0) == XSTR (y, 0);
4203
4204     default:
4205       break;
4206     }
4207
4208   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
4209
4210   if (GET_MODE (x) != GET_MODE (y))
4211     return 0;
4212
4213   /* For commutative operations, the RTX match if the operand match in any
4214      order.  Also handle the simple binary and unary cases without a loop.  */
4215   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
4216     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
4217              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
4218             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
4219                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
4220   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
4221     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
4222             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
4223   else if (GET_RTX_CLASS (code) == '1')
4224     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
4225
4226   /* Compare the elements.  If any pair of corresponding elements
4227      fail to match, return 0 for the whole things.  */
4228
4229   fmt = GET_RTX_FORMAT (code);
4230   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4231     {
4232       register int j;
4233       switch (fmt[i])
4234         {
4235         case 'w':
4236           if (XWINT (x, i) != XWINT (y, i))
4237             return 0;
4238           break;
4239
4240         case 'i':
4241           if (XINT (x, i) != XINT (y, i))
4242             return 0;
4243           break;
4244
4245         case 's':
4246           if (strcmp (XSTR (x, i), XSTR (y, i)))
4247             return 0;
4248           break;
4249
4250         case 'e':
4251           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
4252             return 0;
4253           break;
4254
4255         case 'u':
4256           if (XEXP (x, i) != XEXP (y, i))
4257             return 0;
4258           /* fall through.  */
4259         case '0':
4260           break;
4261
4262         case 'E':
4263           if (XVECLEN (x, i) != XVECLEN (y, i))
4264             return 0;
4265           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4266             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
4267               return 0;
4268           break;
4269
4270         default:
4271           abort ();
4272         }
4273     }
4274   return 1;
4275 }
4276 \f
4277 /* If X is a hard register or equivalent to one or a subregister of one,
4278    return the hard register number.  If X is a pseudo register that was not
4279    assigned a hard register, return the pseudo register number.  Otherwise,
4280    return -1.  Any rtx is valid for X.  */
4281
4282 int
4283 true_regnum (x)
4284      rtx x;
4285 {
4286   if (GET_CODE (x) == REG)
4287     {
4288       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
4289         return reg_renumber[REGNO (x)];
4290       return REGNO (x);
4291     }
4292   if (GET_CODE (x) == SUBREG)
4293     {
4294       int base = true_regnum (SUBREG_REG (x));
4295       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
4296         return SUBREG_WORD (x) + base;
4297     }
4298   return -1;
4299 }
4300 \f
4301 /* Optimize code of the form:
4302
4303         for (x = a[i]; x; ...)
4304           ...
4305         for (x = a[i]; x; ...)
4306           ...
4307       foo:
4308
4309    Loop optimize will change the above code into
4310
4311         if (x = a[i])
4312           for (;;)
4313              { ...; if (! (x = ...)) break; }
4314         if (x = a[i])
4315           for (;;)
4316              { ...; if (! (x = ...)) break; }
4317       foo:
4318
4319    In general, if the first test fails, the program can branch
4320    directly to `foo' and skip the second try which is doomed to fail.
4321    We run this after loop optimization and before flow analysis.  */
4322
4323 /* When comparing the insn patterns, we track the fact that different
4324    pseudo-register numbers may have been used in each computation.
4325    The following array stores an equivalence -- same_regs[I] == J means
4326    that pseudo register I was used in the first set of tests in a context
4327    where J was used in the second set.  We also count the number of such
4328    pending equivalences.  If nonzero, the expressions really aren't the
4329    same.  */
4330
4331 static int *same_regs;
4332
4333 static int num_same_regs;
4334
4335 /* Track any registers modified between the target of the first jump and
4336    the second jump.  They never compare equal.  */
4337
4338 static char *modified_regs;
4339
4340 /* Record if memory was modified.  */
4341
4342 static int modified_mem;
4343
4344 /* Called via note_stores on each insn between the target of the first
4345    branch and the second branch.  It marks any changed registers.  */
4346
4347 static void
4348 mark_modified_reg (dest, x)
4349      rtx dest;
4350      rtx x;
4351 {
4352   int regno, i;
4353
4354   if (GET_CODE (dest) == SUBREG)
4355     dest = SUBREG_REG (dest);
4356
4357   if (GET_CODE (dest) == MEM)
4358     modified_mem = 1;
4359
4360   if (GET_CODE (dest) != REG)
4361     return;
4362
4363   regno = REGNO (dest);
4364   if (regno >= FIRST_PSEUDO_REGISTER)
4365     modified_regs[regno] = 1;
4366   else
4367     for (i = 0; i < HARD_REGNO_NREGS (regno, GET_MODE (dest)); i++)
4368       modified_regs[regno + i] = 1;
4369 }
4370
4371 /* F is the first insn in the chain of insns.  */
4372
4373 void
4374 thread_jumps (f, max_reg, flag_before_loop)
4375      rtx f;
4376      int max_reg;
4377      int flag_before_loop;
4378 {
4379   /* Basic algorithm is to find a conditional branch,
4380      the label it may branch to, and the branch after
4381      that label.  If the two branches test the same condition,
4382      walk back from both branch paths until the insn patterns
4383      differ, or code labels are hit.  If we make it back to
4384      the target of the first branch, then we know that the first branch
4385      will either always succeed or always fail depending on the relative
4386      senses of the two branches.  So adjust the first branch accordingly
4387      in this case.  */
4388
4389   rtx label, b1, b2, t1, t2;
4390   enum rtx_code code1, code2;
4391   rtx b1op0, b1op1, b2op0, b2op1;
4392   int changed = 1;
4393   int i;
4394   int *all_reset;
4395
4396   /* Allocate register tables and quick-reset table.  */
4397   modified_regs = (char *) alloca (max_reg * sizeof (char));
4398   same_regs = (int *) alloca (max_reg * sizeof (int));
4399   all_reset = (int *) alloca (max_reg * sizeof (int));
4400   for (i = 0; i < max_reg; i++)
4401     all_reset[i] = -1;
4402
4403   while (changed)
4404     {
4405       changed = 0;
4406
4407       for (b1 = f; b1; b1 = NEXT_INSN (b1))
4408         {
4409           /* Get to a candidate branch insn.  */
4410           if (GET_CODE (b1) != JUMP_INSN
4411               || ! condjump_p (b1) || simplejump_p (b1)
4412               || JUMP_LABEL (b1) == 0)
4413             continue;
4414
4415           bzero (modified_regs, max_reg * sizeof (char));
4416           modified_mem = 0;
4417
4418           bcopy ((char *) all_reset, (char *) same_regs,
4419                  max_reg * sizeof (int));
4420           num_same_regs = 0;
4421
4422           label = JUMP_LABEL (b1);
4423
4424           /* Look for a branch after the target.  Record any registers and
4425              memory modified between the target and the branch.  Stop when we
4426              get to a label since we can't know what was changed there.  */
4427           for (b2 = NEXT_INSN (label); b2; b2 = NEXT_INSN (b2))
4428             {
4429               if (GET_CODE (b2) == CODE_LABEL)
4430                 break;
4431
4432               else if (GET_CODE (b2) == JUMP_INSN)
4433                 {
4434                   /* If this is an unconditional jump and is the only use of
4435                      its target label, we can follow it.  */
4436                   if (simplejump_p (b2)
4437                       && JUMP_LABEL (b2) != 0
4438                       && LABEL_NUSES (JUMP_LABEL (b2)) == 1)
4439                     {
4440                       b2 = JUMP_LABEL (b2);
4441                       continue;
4442                     }
4443                   else
4444                     break;
4445                 }
4446
4447               if (GET_CODE (b2) != CALL_INSN && GET_CODE (b2) != INSN)
4448                 continue;
4449
4450               if (GET_CODE (b2) == CALL_INSN)
4451                 {
4452                   modified_mem = 1;
4453                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4454                     if (call_used_regs[i] && ! fixed_regs[i]
4455                         && i != STACK_POINTER_REGNUM
4456                         && i != FRAME_POINTER_REGNUM
4457                         && i != HARD_FRAME_POINTER_REGNUM
4458                         && i != ARG_POINTER_REGNUM)
4459                       modified_regs[i] = 1;
4460                 }
4461
4462               note_stores (PATTERN (b2), mark_modified_reg);
4463             }
4464
4465           /* Check the next candidate branch insn from the label
4466              of the first.  */
4467           if (b2 == 0
4468               || GET_CODE (b2) != JUMP_INSN
4469               || b2 == b1
4470               || ! condjump_p (b2)
4471               || simplejump_p (b2))
4472             continue;
4473
4474           /* Get the comparison codes and operands, reversing the
4475              codes if appropriate.  If we don't have comparison codes,
4476              we can't do anything.  */
4477           b1op0 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 0);
4478           b1op1 = XEXP (XEXP (SET_SRC (PATTERN (b1)), 0), 1);
4479           code1 = GET_CODE (XEXP (SET_SRC (PATTERN (b1)), 0));
4480           if (XEXP (SET_SRC (PATTERN (b1)), 1) == pc_rtx)
4481             code1 = reverse_condition (code1);
4482
4483           b2op0 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 0);
4484           b2op1 = XEXP (XEXP (SET_SRC (PATTERN (b2)), 0), 1);
4485           code2 = GET_CODE (XEXP (SET_SRC (PATTERN (b2)), 0));
4486           if (XEXP (SET_SRC (PATTERN (b2)), 1) == pc_rtx)
4487             code2 = reverse_condition (code2);
4488
4489           /* If they test the same things and knowing that B1 branches
4490              tells us whether or not B2 branches, check if we
4491              can thread the branch.  */
4492           if (rtx_equal_for_thread_p (b1op0, b2op0, b2)
4493               && rtx_equal_for_thread_p (b1op1, b2op1, b2)
4494               && (comparison_dominates_p (code1, code2)
4495                   || (comparison_dominates_p (code1, reverse_condition (code2))
4496                       && can_reverse_comparison_p (XEXP (SET_SRC (PATTERN (b1)),
4497                                                          0),
4498                                                    b1))))
4499             {
4500               t1 = prev_nonnote_insn (b1);
4501               t2 = prev_nonnote_insn (b2);
4502
4503               while (t1 != 0 && t2 != 0)
4504                 {
4505                   if (t2 == label)
4506                     {
4507                       /* We have reached the target of the first branch.
4508                          If there are no pending register equivalents,
4509                          we know that this branch will either always
4510                          succeed (if the senses of the two branches are
4511                          the same) or always fail (if not).  */
4512                       rtx new_label;
4513
4514                       if (num_same_regs != 0)
4515                         break;
4516
4517                       if (comparison_dominates_p (code1, code2))
4518                         new_label = JUMP_LABEL (b2);
4519                       else
4520                         new_label = get_label_after (b2);
4521
4522                       if (JUMP_LABEL (b1) != new_label)
4523                         {
4524                           rtx prev = PREV_INSN (new_label);
4525
4526                           if (flag_before_loop
4527                               && NOTE_LINE_NUMBER (prev) == NOTE_INSN_LOOP_BEG)
4528                             {
4529                               /* Don't thread to the loop label.  If a loop
4530                                  label is reused, loop optimization will
4531                                  be disabled for that loop.  */
4532                               new_label = gen_label_rtx ();
4533                               emit_label_after (new_label, PREV_INSN (prev));
4534                             }
4535                           changed |= redirect_jump (b1, new_label);
4536                         }
4537                       break;
4538                     }
4539
4540                   /* If either of these is not a normal insn (it might be
4541                      a JUMP_INSN, CALL_INSN, or CODE_LABEL) we fail.  (NOTEs
4542                      have already been skipped above.)  Similarly, fail
4543                      if the insns are different.  */
4544                   if (GET_CODE (t1) != INSN || GET_CODE (t2) != INSN
4545                       || recog_memoized (t1) != recog_memoized (t2)
4546                       || ! rtx_equal_for_thread_p (PATTERN (t1),
4547                                                    PATTERN (t2), t2))
4548                     break;
4549
4550                   t1 = prev_nonnote_insn (t1);
4551                   t2 = prev_nonnote_insn (t2);
4552                 }
4553             }
4554         }
4555     }
4556 }
4557 \f
4558 /* This is like RTX_EQUAL_P except that it knows about our handling of
4559    possibly equivalent registers and knows to consider volatile and
4560    modified objects as not equal.
4561
4562    YINSN is the insn containing Y.  */
4563
4564 int
4565 rtx_equal_for_thread_p (x, y, yinsn)
4566      rtx x, y;
4567      rtx yinsn;
4568 {
4569   register int i;
4570   register int j;
4571   register enum rtx_code code;
4572   register char *fmt;
4573
4574   code = GET_CODE (x);
4575   /* Rtx's of different codes cannot be equal.  */
4576   if (code != GET_CODE (y))
4577     return 0;
4578
4579   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
4580      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
4581
4582   if (GET_MODE (x) != GET_MODE (y))
4583     return 0;
4584
4585   /* For floating-point, consider everything unequal.  This is a bit
4586      pessimistic, but this pass would only rarely do anything for FP
4587      anyway.  */
4588   if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
4589       && FLOAT_MODE_P (GET_MODE (x)) && ! flag_fast_math)
4590     return 0;
4591
4592   /* For commutative operations, the RTX match if the operand match in any
4593      order.  Also handle the simple binary and unary cases without a loop.  */
4594   if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
4595     return ((rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
4596              && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn))
4597             || (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 1), yinsn)
4598                 && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 0), yinsn)));
4599   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
4600     return (rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn)
4601             && rtx_equal_for_thread_p (XEXP (x, 1), XEXP (y, 1), yinsn));
4602   else if (GET_RTX_CLASS (code) == '1')
4603     return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
4604
4605   /* Handle special-cases first.  */
4606   switch (code)
4607     {
4608     case REG:
4609       if (REGNO (x) == REGNO (y) && ! modified_regs[REGNO (x)])
4610         return 1;
4611
4612       /* If neither is user variable or hard register, check for possible
4613          equivalence.  */
4614       if (REG_USERVAR_P (x) || REG_USERVAR_P (y)
4615           || REGNO (x) < FIRST_PSEUDO_REGISTER
4616           || REGNO (y) < FIRST_PSEUDO_REGISTER)
4617         return 0;
4618
4619       if (same_regs[REGNO (x)] == -1)
4620         {
4621           same_regs[REGNO (x)] = REGNO (y);
4622           num_same_regs++;
4623
4624           /* If this is the first time we are seeing a register on the `Y'
4625              side, see if it is the last use.  If not, we can't thread the
4626              jump, so mark it as not equivalent.  */
4627           if (REGNO_LAST_UID (REGNO (y)) != INSN_UID (yinsn))
4628             return 0;
4629
4630           return 1;
4631         }
4632       else
4633         return (same_regs[REGNO (x)] == REGNO (y));
4634
4635       break;
4636
4637     case MEM:
4638       /* If memory modified or either volatile, not equivalent.
4639          Else, check address.  */
4640       if (modified_mem || MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4641         return 0;
4642
4643       return rtx_equal_for_thread_p (XEXP (x, 0), XEXP (y, 0), yinsn);
4644
4645     case ASM_INPUT:
4646       if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
4647         return 0;
4648
4649       break;
4650
4651     case SET:
4652       /* Cancel a pending `same_regs' if setting equivalenced registers.
4653          Then process source.  */
4654       if (GET_CODE (SET_DEST (x)) == REG
4655           && GET_CODE (SET_DEST (y)) == REG)
4656         {
4657           if (same_regs[REGNO (SET_DEST (x))] == REGNO (SET_DEST (y)))
4658             {
4659               same_regs[REGNO (SET_DEST (x))] = -1;
4660               num_same_regs--;
4661             }
4662           else if (REGNO (SET_DEST (x)) != REGNO (SET_DEST (y)))
4663             return 0;
4664         }
4665       else
4666         if (rtx_equal_for_thread_p (SET_DEST (x), SET_DEST (y), yinsn) == 0)
4667           return 0;
4668
4669       return rtx_equal_for_thread_p (SET_SRC (x), SET_SRC (y), yinsn);
4670
4671     case LABEL_REF:
4672       return XEXP (x, 0) == XEXP (y, 0);
4673
4674     case SYMBOL_REF:
4675       return XSTR (x, 0) == XSTR (y, 0);
4676
4677     default:
4678       break;
4679     }
4680
4681   if (x == y)
4682     return 1;
4683
4684   fmt = GET_RTX_FORMAT (code);
4685   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4686     {
4687       switch (fmt[i])
4688         {
4689         case 'w':
4690           if (XWINT (x, i) != XWINT (y, i))
4691             return 0;
4692           break;
4693
4694         case 'n':
4695         case 'i':
4696           if (XINT (x, i) != XINT (y, i))
4697             return 0;
4698           break;
4699
4700         case 'V':
4701         case 'E':
4702           /* Two vectors must have the same length.  */
4703           if (XVECLEN (x, i) != XVECLEN (y, i))
4704             return 0;
4705
4706           /* And the corresponding elements must match.  */
4707           for (j = 0; j < XVECLEN (x, i); j++)
4708             if (rtx_equal_for_thread_p (XVECEXP (x, i, j),
4709                                         XVECEXP (y, i, j), yinsn) == 0)
4710               return 0;
4711           break;
4712
4713         case 'e':
4714           if (rtx_equal_for_thread_p (XEXP (x, i), XEXP (y, i), yinsn) == 0)
4715             return 0;
4716           break;
4717
4718         case 'S':
4719         case 's':
4720           if (strcmp (XSTR (x, i), XSTR (y, i)))
4721             return 0;
4722           break;
4723
4724         case 'u':
4725           /* These are just backpointers, so they don't matter.  */
4726           break;
4727
4728         case '0':
4729           break;
4730
4731           /* It is believed that rtx's at this level will never
4732              contain anything but integers and other rtx's,
4733              except for within LABEL_REFs and SYMBOL_REFs.  */
4734         default:
4735           abort ();
4736         }
4737     }
4738   return 1;
4739 }
4740 \f
4741
4742 /* Return the insn that NEW can be safely inserted in front of starting at
4743    the jump insn INSN.  Return 0 if it is not safe to do this jump
4744    optimization.  Note that NEW must contain a single set. */
4745
4746 static rtx
4747 find_insert_position (insn, new)
4748      rtx insn;
4749      rtx new;
4750 {
4751   int i;
4752   rtx prev;
4753
4754   /* If NEW does not clobber, it is safe to insert NEW before INSN. */
4755   if (GET_CODE (PATTERN (new)) != PARALLEL)
4756     return insn;
4757
4758   for (i = XVECLEN (PATTERN (new), 0) - 1; i >= 0; i--)
4759     if (GET_CODE (XVECEXP (PATTERN (new), 0, i)) == CLOBBER
4760         && reg_overlap_mentioned_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
4761                                     insn))
4762       break;
4763
4764   if (i < 0)
4765     return insn;
4766
4767   /* There is a good chance that the previous insn PREV sets the thing
4768      being clobbered (often the CC in a hard reg).  If PREV does not
4769      use what NEW sets, we can insert NEW before PREV. */
4770
4771   prev = prev_active_insn (insn);
4772   for (i = XVECLEN (PATTERN (new), 0) - 1; i >= 0; i--)
4773     if (GET_CODE (XVECEXP (PATTERN (new), 0, i)) == CLOBBER
4774         && reg_overlap_mentioned_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
4775                                     insn)
4776         && ! modified_in_p (XEXP (XVECEXP (PATTERN (new), 0, i), 0),
4777                             prev))
4778       return 0;
4779
4780   return reg_mentioned_p (SET_DEST (single_set (new)), prev) ? 0 : prev;
4781 }