gcc/jump.c

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