gcc/jump.c

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