gcc/jump.c

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