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