gcc/sched-deps.c

   1 /* Instruction scheduling pass.  This file computes dependencies between
   2    instructions.
   3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
   6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify it under
  11 the terms of the GNU General Public License as published by the Free
  12 Software Foundation; either version 2, or (at your option) any later
  13 version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18 for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING.  If not, write to the Free
  22 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  23 02111-1307, USA.  */
  24 \f
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "tm.h"
  29 #include "toplev.h"
  30 #include "rtl.h"
  31 #include "tm_p.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "regs.h"
  35 #include "function.h"
  36 #include "flags.h"
  37 #include "insn-config.h"
  38 #include "insn-attr.h"
  39 #include "except.h"
  40 #include "toplev.h"
  41 #include "recog.h"
  42 #include "sched-int.h"
  43 #include "params.h"
  44 #include "cselib.h"
  45
  46 extern char *reg_known_equiv_p;
  47 extern rtx *reg_known_value;
  48
  49 static regset_head reg_pending_sets_head;
  50 static regset_head reg_pending_clobbers_head;
  51 static regset_head reg_pending_uses_head;
  52
  53 static regset reg_pending_sets;
  54 static regset reg_pending_clobbers;
  55 static regset reg_pending_uses;
  56 static bool reg_pending_barrier;
  57
  58 /* To speed up the test for duplicate dependency links we keep a
  59    record of dependencies created by add_dependence when the average
  60    number of instructions in a basic block is very large.
  61
  62    Studies have shown that there is typically around 5 instructions between
  63    branches for typical C code.  So we can make a guess that the average
  64    basic block is approximately 5 instructions long; we will choose 100X
  65    the average size as a very large basic block.
  66
  67    Each insn has associated bitmaps for its dependencies.  Each bitmap
  68    has enough entries to represent a dependency on any other insn in
  69    the insn chain.  All bitmap for true dependencies cache is
  70    allocated then the rest two ones are also allocated.  */
  71 static sbitmap *true_dependency_cache;
  72 static sbitmap *anti_dependency_cache;
  73 static sbitmap *output_dependency_cache;
  74
  75 /* To speed up checking consistency of formed forward insn
  76    dependencies we use the following cache.  Another possible solution
  77    could be switching off checking duplication of insns in forward
  78    dependencies.  */
  79 #ifdef ENABLE_CHECKING
  80 static sbitmap *forward_dependency_cache;
  81 #endif
  82
  83 static int deps_may_trap_p PARAMS ((rtx));
  84 static void add_dependence_list PARAMS ((rtx, rtx, enum reg_note));
  85 static void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note));
  86 static void set_sched_group_p PARAMS ((rtx));
  87
  88 static void flush_pending_lists PARAMS ((struct deps *, rtx, int, int));
  89 static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx));
  90 static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx));
  91 static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx));
  92
  93 static rtx get_condition PARAMS ((rtx));
  94 static int conditions_mutex_p PARAMS ((rtx, rtx));
  95 \f
  96 /* Return nonzero if a load of the memory reference MEM can cause a trap.  */
  97
  98 static int
  99 deps_may_trap_p (mem)
 100      rtx mem;
 101 {
 102   rtx addr = XEXP (mem, 0);
 103
 104   if (REG_P (addr)
 105       && REGNO (addr) >= FIRST_PSEUDO_REGISTER
 106       && reg_known_value[REGNO (addr)])
 107     addr = reg_known_value[REGNO (addr)];
 108   return rtx_addr_can_trap_p (addr);
 109 }
 110 \f
 111 /* Return the INSN_LIST containing INSN in LIST, or NULL
 112    if LIST does not contain INSN.  */
 113
 114 rtx
 115 find_insn_list (insn, list)
 116      rtx insn;
 117      rtx list;
 118 {
 119   while (list)
 120     {
 121       if (XEXP (list, 0) == insn)
 122         return list;
 123       list = XEXP (list, 1);
 124     }
 125   return 0;
 126 }
 127 \f
 128 /* Find the condition under which INSN is executed.  */
 129
 130 static rtx
 131 get_condition (insn)
 132      rtx insn;
 133 {
 134   rtx pat = PATTERN (insn);
 135   rtx cond;
 136
 137   if (pat == 0)
 138     return 0;
 139   if (GET_CODE (pat) == COND_EXEC)
 140     return COND_EXEC_TEST (pat);
 141   if (GET_CODE (insn) != JUMP_INSN)
 142     return 0;
 143   if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx)
 144     return 0;
 145   if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE)
 146     return 0;
 147   pat = SET_DEST (pat);
 148   cond = XEXP (pat, 0);
 149   if (GET_CODE (XEXP (cond, 1)) == LABEL_REF
 150       && XEXP (cond, 2) == pc_rtx)
 151     return cond;
 152   else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF
 153            && XEXP (cond, 1) == pc_rtx)
 154     return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond),
 155                            XEXP (cond, 0), XEXP (cond, 1));
 156   else
 157     return 0;
 158 }
 159
 160 /* Return nonzero if conditions COND1 and COND2 can never be both true.  */
 161
 162 static int
 163 conditions_mutex_p (cond1, cond2)
 164      rtx cond1, cond2;
 165 {
 166   if (GET_RTX_CLASS (GET_CODE (cond1)) == '<'
 167       && GET_RTX_CLASS (GET_CODE (cond2)) == '<'
 168       && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2))
 169       && XEXP (cond1, 0) == XEXP (cond2, 0)
 170       && XEXP (cond1, 1) == XEXP (cond2, 1))
 171     return 1;
 172   return 0;
 173 }
 174 \f
 175 /* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the
 176    LOG_LINKS of INSN, if not already there.  DEP_TYPE indicates the
 177    type of dependence that this link represents.  The function returns
 178    nonzero if a new entry has been added to insn's LOG_LINK.  */
 179
 180 int
 181 add_dependence (insn, elem, dep_type)
 182      rtx insn;
 183      rtx elem;
 184      enum reg_note dep_type;
 185 {
 186   rtx link;
 187   int present_p;
 188   rtx cond1, cond2;
 189
 190   /* Don't depend an insn on itself.  */
 191   if (insn == elem)
 192     return 0;
 193
 194   /* We can get a dependency on deleted insns due to optimizations in
 195      the register allocation and reloading or due to splitting.  Any
 196      such dependency is useless and can be ignored.  */
 197   if (GET_CODE (elem) == NOTE)
 198     return 0;
 199
 200   /* flow.c doesn't handle conditional lifetimes entirely correctly;
 201      calls mess up the conditional lifetimes.  */
 202   /* ??? add_dependence is the wrong place to be eliding dependencies,
 203      as that forgets that the condition expressions themselves may
 204      be dependent.  */
 205   if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN)
 206     {
 207       cond1 = get_condition (insn);
 208       cond2 = get_condition (elem);
 209       if (cond1 && cond2
 210           && conditions_mutex_p (cond1, cond2)
 211           /* Make sure first instruction doesn't affect condition of second
 212              instruction if switched.  */
 213           && !modified_in_p (cond1, elem)
 214           /* Make sure second instruction doesn't affect condition of first
 215              instruction if switched.  */
 216           && !modified_in_p (cond2, insn))
 217         return 0;
 218     }
 219
 220   present_p = 1;
 221 #ifdef INSN_SCHEDULING
 222   /* ??? No good way to tell from here whether we're doing interblock
 223      scheduling.  Possibly add another callback.  */
 224 #if 0
 225   /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.)
 226      No need for interblock dependences with calls, since
 227      calls are not moved between blocks.   Note: the edge where
 228      elem is a CALL is still required.  */
 229   if (GET_CODE (insn) == CALL_INSN
 230       && (INSN_BB (elem) != INSN_BB (insn)))
 231     return 0;
 232 #endif
 233
 234   /* If we already have a dependency for ELEM, then we do not need to
 235      do anything.  Avoiding the list walk below can cut compile times
 236      dramatically for some code.  */
 237   if (true_dependency_cache != NULL)
 238     {
 239       enum reg_note present_dep_type = 0;
 240
 241       if (anti_dependency_cache == NULL || output_dependency_cache == NULL)
 242         abort ();
 243       if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)))
 244         /* Do nothing (present_set_type is already 0).  */
 245         ;
 246       else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)],
 247                          INSN_LUID (elem)))
 248         present_dep_type = REG_DEP_ANTI;
 249       else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)],
 250                          INSN_LUID (elem)))
 251         present_dep_type = REG_DEP_OUTPUT;
 252       else
 253         present_p = 0;
 254       if (present_p && (int) dep_type >= (int) present_dep_type)
 255         return 0;
 256     }
 257 #endif
 258
 259   /* Check that we don't already have this dependence.  */
 260   if (present_p)
 261     for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
 262       if (XEXP (link, 0) == elem)
 263         {
 264 #ifdef INSN_SCHEDULING
 265           /* Clear corresponding cache entry because type of the link
 266              may be changed.  */
 267           if (true_dependency_cache != NULL)
 268             {
 269               if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 270                 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 271                            INSN_LUID (elem));
 272               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT
 273                        && output_dependency_cache)
 274                 RESET_BIT (output_dependency_cache[INSN_LUID (insn)],
 275                            INSN_LUID (elem));
 276               else
 277                 abort ();
 278             }
 279 #endif
 280
 281           /* If this is a more restrictive type of dependence than the existing
 282              one, then change the existing dependence to this type.  */
 283           if ((int) dep_type < (int) REG_NOTE_KIND (link))
 284             PUT_REG_NOTE_KIND (link, dep_type);
 285
 286 #ifdef INSN_SCHEDULING
 287           /* If we are adding a dependency to INSN's LOG_LINKs, then
 288              note that in the bitmap caches of dependency information.  */
 289           if (true_dependency_cache != NULL)
 290             {
 291               if ((int) REG_NOTE_KIND (link) == 0)
 292                 SET_BIT (true_dependency_cache[INSN_LUID (insn)],
 293                          INSN_LUID (elem));
 294               else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
 295                 SET_BIT (anti_dependency_cache[INSN_LUID (insn)],
 296                          INSN_LUID (elem));
 297               else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
 298                 SET_BIT (output_dependency_cache[INSN_LUID (insn)],
 299                          INSN_LUID (elem));
 300             }
 301 #endif
 302           return 0;
 303         }
 304   /* Might want to check one level of transitivity to save conses.  */
 305
 306   link = alloc_INSN_LIST (elem, LOG_LINKS (insn));
 307   LOG_LINKS (insn) = link;
 308
 309   /* Insn dependency, not data dependency.  */
 310   PUT_REG_NOTE_KIND (link, dep_type);
 311
 312 #ifdef INSN_SCHEDULING
 313   /* If we are adding a dependency to INSN's LOG_LINKs, then note that
 314      in the bitmap caches of dependency information.  */
 315   if (true_dependency_cache != NULL)
 316     {
 317       if ((int) dep_type == 0)
 318         SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 319       else if (dep_type == REG_DEP_ANTI)
 320         SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 321       else if (dep_type == REG_DEP_OUTPUT)
 322         SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem));
 323     }
 324 #endif
 325   return 1;
 326 }
 327
 328 /* A convenience wrapper to operate on an entire list.  */
 329
 330 static void
 331 add_dependence_list (insn, list, dep_type)
 332      rtx insn, list;
 333      enum reg_note dep_type;
 334 {
 335   for (; list; list = XEXP (list, 1))
 336     add_dependence (insn, XEXP (list, 0), dep_type);
 337 }
 338
 339 /* Similar, but free *LISTP at the same time.  */
 340
 341 static void
 342 add_dependence_list_and_free (insn, listp, dep_type)
 343      rtx insn;
 344      rtx *listp;
 345      enum reg_note dep_type;
 346 {
 347   rtx list, next;
 348   for (list = *listp, *listp = NULL; list ; list = next)
 349     {
 350       next = XEXP (list, 1);
 351       add_dependence (insn, XEXP (list, 0), dep_type);
 352       free_INSN_LIST_node (list);
 353     }
 354 }
 355
 356 /* Set SCHED_GROUP_P and care for the rest of the bookkeeping that
 357    goes along with that.  */
 358
 359 static void
 360 set_sched_group_p (insn)
 361      rtx insn;
 362 {
 363   rtx prev;
 364
 365   SCHED_GROUP_P (insn) = 1;
 366
 367   prev = prev_nonnote_insn (insn);
 368   add_dependence (insn, prev, REG_DEP_ANTI);
 369 }
 370 \f
 371 /* Process an insn's memory dependencies.  There are four kinds of
 372    dependencies:
 373
 374    (0) read dependence: read follows read
 375    (1) true dependence: read follows write
 376    (2) anti dependence: write follows read
 377    (3) output dependence: write follows write
 378
 379    We are careful to build only dependencies which actually exist, and
 380    use transitivity to avoid building too many links.  */
 381
 382 /* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST.
 383    The MEM is a memory reference contained within INSN, which we are saving
 384    so that we can do memory aliasing on it.  */
 385
 386 void
 387 add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem)
 388      struct deps *deps;
 389      rtx *insn_list, *mem_list, insn, mem;
 390 {
 391   rtx link;
 392
 393   link = alloc_INSN_LIST (insn, *insn_list);
 394   *insn_list = link;
 395
 396   if (current_sched_info->use_cselib)
 397     {
 398       mem = shallow_copy_rtx (mem);
 399       XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
 400     }
 401   link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list);
 402   *mem_list = link;
 403
 404   deps->pending_lists_length++;
 405 }
 406
 407 /* Make a dependency between every memory reference on the pending lists
 408    and INSN, thus flushing the pending lists.  FOR_READ is true if emitting
 409    dependencies for a read operation, similarly with FOR_WRITE.  */
 410
 411 static void
 412 flush_pending_lists (deps, insn, for_read, for_write)
 413      struct deps *deps;
 414      rtx insn;
 415      int for_read, for_write;
 416 {
 417   if (for_write)
 418     {
 419       add_dependence_list_and_free (insn, &deps->pending_read_insns,
 420                                     REG_DEP_ANTI);
 421       free_EXPR_LIST_list (&deps->pending_read_mems);
 422     }
 423
 424   add_dependence_list_and_free (insn, &deps->pending_write_insns,
 425                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 426   free_EXPR_LIST_list (&deps->pending_write_mems);
 427   deps->pending_lists_length = 0;
 428
 429   add_dependence_list_and_free (insn, &deps->last_pending_memory_flush,
 430                                 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
 431   deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
 432   deps->pending_flush_length = 1;
 433 }
 434 \f
 435 /* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC
 436    rtx, X, creating all dependencies generated by the write to the
 437    destination of X, and reads of everything mentioned.  */
 438
 439 static void
 440 sched_analyze_1 (deps, x, insn)
 441      struct deps *deps;
 442      rtx x;
 443      rtx insn;
 444 {
 445   int regno;
 446   rtx dest = XEXP (x, 0);
 447   enum rtx_code code = GET_CODE (x);
 448
 449   if (dest == 0)
 450     return;
 451
 452   if (GET_CODE (dest) == PARALLEL)
 453     {
 454       int i;
 455
 456       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
 457         if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
 458           sched_analyze_1 (deps,
 459                            gen_rtx_CLOBBER (VOIDmode,
 460                                             XEXP (XVECEXP (dest, 0, i), 0)),
 461                            insn);
 462
 463       if (GET_CODE (x) == SET)
 464         sched_analyze_2 (deps, SET_SRC (x), insn);
 465       return;
 466     }
 467
 468   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
 469          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 470     {
 471       if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
 472         {
 473           /* The second and third arguments are values read by this insn.  */
 474           sched_analyze_2 (deps, XEXP (dest, 1), insn);
 475           sched_analyze_2 (deps, XEXP (dest, 2), insn);
 476         }
 477       dest = XEXP (dest, 0);
 478     }
 479
 480   if (GET_CODE (dest) == REG)
 481     {
 482       regno = REGNO (dest);
 483
 484       /* A hard reg in a wide mode may really be multiple registers.
 485          If so, mark all of them just like the first.  */
 486       if (regno < FIRST_PSEUDO_REGISTER)
 487         {
 488           int i = HARD_REGNO_NREGS (regno, GET_MODE (dest));
 489           if (code == SET)
 490             {
 491               while (--i >= 0)
 492                 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
 493             }
 494           else
 495             {
 496               while (--i >= 0)
 497                 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
 498             }
 499         }
 500       /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 501          it does not reload.  Ignore these as they have served their
 502          purpose already.  */
 503       else if (regno >= deps->max_reg)
 504         {
 505           if (GET_CODE (PATTERN (insn)) != USE
 506               && GET_CODE (PATTERN (insn)) != CLOBBER)
 507             abort ();
 508         }
 509       else
 510         {
 511           if (code == SET)
 512             SET_REGNO_REG_SET (reg_pending_sets, regno);
 513           else
 514             SET_REGNO_REG_SET (reg_pending_clobbers, regno);
 515
 516           /* Pseudos that are REG_EQUIV to something may be replaced
 517              by that during reloading.  We need only add dependencies for
 518              the address in the REG_EQUIV note.  */
 519           if (!reload_completed
 520               && reg_known_equiv_p[regno]
 521               && GET_CODE (reg_known_value[regno]) == MEM)
 522             sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
 523
 524           /* Don't let it cross a call after scheduling if it doesn't
 525              already cross one.  */
 526           if (REG_N_CALLS_CROSSED (regno) == 0)
 527             add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI);
 528         }
 529     }
 530   else if (GET_CODE (dest) == MEM)
 531     {
 532       /* Writing memory.  */
 533       rtx t = dest;
 534
 535       if (current_sched_info->use_cselib)
 536         {
 537           t = shallow_copy_rtx (dest);
 538           cselib_lookup (XEXP (t, 0), Pmode, 1);
 539           XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 540         }
 541
 542       if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
 543         {
 544           /* Flush all pending reads and writes to prevent the pending lists
 545              from getting any larger.  Insn scheduling runs too slowly when
 546              these lists get long.  When compiling GCC with itself,
 547              this flush occurs 8 times for sparc, and 10 times for m88k using
 548              the default value of 32.  */
 549           flush_pending_lists (deps, insn, false, true);
 550         }
 551       else
 552         {
 553           rtx pending, pending_mem;
 554
 555           pending = deps->pending_read_insns;
 556           pending_mem = deps->pending_read_mems;
 557           while (pending)
 558             {
 559               if (anti_dependence (XEXP (pending_mem, 0), t))
 560                 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 561
 562               pending = XEXP (pending, 1);
 563               pending_mem = XEXP (pending_mem, 1);
 564             }
 565
 566           pending = deps->pending_write_insns;
 567           pending_mem = deps->pending_write_mems;
 568           while (pending)
 569             {
 570               if (output_dependence (XEXP (pending_mem, 0), t))
 571                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 572
 573               pending = XEXP (pending, 1);
 574               pending_mem = XEXP (pending_mem, 1);
 575             }
 576
 577           add_dependence_list (insn, deps->last_pending_memory_flush,
 578                                REG_DEP_ANTI);
 579
 580           add_insn_mem_dependence (deps, &deps->pending_write_insns,
 581                                    &deps->pending_write_mems, insn, dest);
 582         }
 583       sched_analyze_2 (deps, XEXP (dest, 0), insn);
 584     }
 585
 586   /* Analyze reads.  */
 587   if (GET_CODE (x) == SET)
 588     sched_analyze_2 (deps, SET_SRC (x), insn);
 589 }
 590
 591 /* Analyze the uses of memory and registers in rtx X in INSN.  */
 592
 593 static void
 594 sched_analyze_2 (deps, x, insn)
 595      struct deps *deps;
 596      rtx x;
 597      rtx insn;
 598 {
 599   int i;
 600   int j;
 601   enum rtx_code code;
 602   const char *fmt;
 603
 604   if (x == 0)
 605     return;
 606
 607   code = GET_CODE (x);
 608
 609   switch (code)
 610     {
 611     case CONST_INT:
 612     case CONST_DOUBLE:
 613     case CONST_VECTOR:
 614     case SYMBOL_REF:
 615     case CONST:
 616     case LABEL_REF:
 617       /* Ignore constants.  Note that we must handle CONST_DOUBLE here
 618          because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but
 619          this does not mean that this insn is using cc0.  */
 620       return;
 621
 622 #ifdef HAVE_cc0
 623     case CC0:
 624       /* User of CC0 depends on immediately preceding insn.  */
 625       set_sched_group_p (insn);
 626       return;
 627 #endif
 628
 629     case REG:
 630       {
 631         int regno = REGNO (x);
 632         if (regno < FIRST_PSEUDO_REGISTER)
 633           {
 634             int i = HARD_REGNO_NREGS (regno, GET_MODE (x));
 635             while (--i >= 0)
 636               SET_REGNO_REG_SET (reg_pending_uses, regno + i);
 637           }
 638         /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that
 639            it does not reload.  Ignore these as they have served their
 640            purpose already.  */
 641         else if (regno >= deps->max_reg)
 642           {
 643             if (GET_CODE (PATTERN (insn)) != USE
 644                 && GET_CODE (PATTERN (insn)) != CLOBBER)
 645               abort ();
 646           }
 647         else
 648           {
 649             SET_REGNO_REG_SET (reg_pending_uses, regno);
 650
 651             /* Pseudos that are REG_EQUIV to something may be replaced
 652                by that during reloading.  We need only add dependencies for
 653                the address in the REG_EQUIV note.  */
 654             if (!reload_completed
 655                 && reg_known_equiv_p[regno]
 656                 && GET_CODE (reg_known_value[regno]) == MEM)
 657               sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn);
 658
 659             /* If the register does not already cross any calls, then add this
 660                insn to the sched_before_next_call list so that it will still
 661                not cross calls after scheduling.  */
 662             if (REG_N_CALLS_CROSSED (regno) == 0)
 663               deps->sched_before_next_call
 664                 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
 665           }
 666         return;
 667       }
 668
 669     case MEM:
 670       {
 671         /* Reading memory.  */
 672         rtx u;
 673         rtx pending, pending_mem;
 674         rtx t = x;
 675
 676         if (current_sched_info->use_cselib)
 677           {
 678             t = shallow_copy_rtx (t);
 679             cselib_lookup (XEXP (t, 0), Pmode, 1);
 680             XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
 681           }
 682         pending = deps->pending_read_insns;
 683         pending_mem = deps->pending_read_mems;
 684         while (pending)
 685           {
 686             if (read_dependence (XEXP (pending_mem, 0), t))
 687               add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
 688
 689             pending = XEXP (pending, 1);
 690             pending_mem = XEXP (pending_mem, 1);
 691           }
 692
 693         pending = deps->pending_write_insns;
 694         pending_mem = deps->pending_write_mems;
 695         while (pending)
 696           {
 697             if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
 698                                  t, rtx_varies_p))
 699               add_dependence (insn, XEXP (pending, 0), 0);
 700
 701             pending = XEXP (pending, 1);
 702             pending_mem = XEXP (pending_mem, 1);
 703           }
 704
 705         for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
 706           if (GET_CODE (XEXP (u, 0)) != JUMP_INSN
 707               || deps_may_trap_p (x))
 708             add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
 709
 710         /* Always add these dependencies to pending_reads, since
 711            this insn may be followed by a write.  */
 712         add_insn_mem_dependence (deps, &deps->pending_read_insns,
 713                                  &deps->pending_read_mems, insn, x);
 714
 715         /* Take advantage of tail recursion here.  */
 716         sched_analyze_2 (deps, XEXP (x, 0), insn);
 717         return;
 718       }
 719
 720     /* Force pending stores to memory in case a trap handler needs them.  */
 721     case TRAP_IF:
 722       flush_pending_lists (deps, insn, true, false);
 723       break;
 724
 725     case ASM_OPERANDS:
 726     case ASM_INPUT:
 727     case UNSPEC_VOLATILE:
 728       {
 729         /* Traditional and volatile asm instructions must be considered to use
 730            and clobber all hard registers, all pseudo-registers and all of
 731            memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
 732
 733            Consider for instance a volatile asm that changes the fpu rounding
 734            mode.  An insn should not be moved across this even if it only uses
 735            pseudo-regs because it might give an incorrectly rounded result.  */
 736         if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
 737           reg_pending_barrier = true;
 738
 739         /* For all ASM_OPERANDS, we must traverse the vector of input operands.
 740            We can not just fall through here since then we would be confused
 741            by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
 742            traditional asms unlike their normal usage.  */
 743
 744         if (code == ASM_OPERANDS)
 745           {
 746             for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
 747               sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
 748             return;
 749           }
 750         break;
 751       }
 752
 753     case PRE_DEC:
 754     case POST_DEC:
 755     case PRE_INC:
 756     case POST_INC:
 757       /* These both read and modify the result.  We must handle them as writes
 758          to get proper dependencies for following instructions.  We must handle
 759          them as reads to get proper dependencies from this to previous
 760          instructions.  Thus we need to pass them to both sched_analyze_1
 761          and sched_analyze_2.  We must call sched_analyze_2 first in order
 762          to get the proper antecedent for the read.  */
 763       sched_analyze_2 (deps, XEXP (x, 0), insn);
 764       sched_analyze_1 (deps, x, insn);
 765       return;
 766
 767     case POST_MODIFY:
 768     case PRE_MODIFY:
 769       /* op0 = op0 + op1 */
 770       sched_analyze_2 (deps, XEXP (x, 0), insn);
 771       sched_analyze_2 (deps, XEXP (x, 1), insn);
 772       sched_analyze_1 (deps, x, insn);
 773       return;
 774
 775     default:
 776       break;
 777     }
 778
 779   /* Other cases: walk the insn.  */
 780   fmt = GET_RTX_FORMAT (code);
 781   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 782     {
 783       if (fmt[i] == 'e')
 784         sched_analyze_2 (deps, XEXP (x, i), insn);
 785       else if (fmt[i] == 'E')
 786         for (j = 0; j < XVECLEN (x, i); j++)
 787           sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
 788     }
 789 }
 790
 791 /* Analyze an INSN with pattern X to find all dependencies.  */
 792
 793 static void
 794 sched_analyze_insn (deps, x, insn, loop_notes)
 795      struct deps *deps;
 796      rtx x, insn;
 797      rtx loop_notes;
 798 {
 799   RTX_CODE code = GET_CODE (x);
 800   rtx link;
 801   int i;
 802
 803   if (code == COND_EXEC)
 804     {
 805       sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
 806
 807       /* ??? Should be recording conditions so we reduce the number of
 808          false dependencies.  */
 809       x = COND_EXEC_CODE (x);
 810       code = GET_CODE (x);
 811     }
 812   if (code == SET || code == CLOBBER)
 813     {
 814       sched_analyze_1 (deps, x, insn);
 815
 816       /* Bare clobber insns are used for letting life analysis, reg-stack
 817          and others know that a value is dead.  Depend on the last call
 818          instruction so that reg-stack won't get confused.  */
 819       if (code == CLOBBER)
 820         add_dependence_list (insn, deps->last_function_call, REG_DEP_OUTPUT);
 821     }
 822   else if (code == PARALLEL)
 823     {
 824       int i;
 825       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
 826         {
 827           rtx sub = XVECEXP (x, 0, i);
 828           code = GET_CODE (sub);
 829
 830           if (code == COND_EXEC)
 831             {
 832               sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
 833               sub = COND_EXEC_CODE (sub);
 834               code = GET_CODE (sub);
 835             }
 836           if (code == SET || code == CLOBBER)
 837             sched_analyze_1 (deps, sub, insn);
 838           else
 839             sched_analyze_2 (deps, sub, insn);
 840         }
 841     }
 842   else
 843     sched_analyze_2 (deps, x, insn);
 844
 845   /* Mark registers CLOBBERED or used by called function.  */
 846   if (GET_CODE (insn) == CALL_INSN)
 847     {
 848       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
 849         {
 850           if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 851             sched_analyze_1 (deps, XEXP (link, 0), insn);
 852           else
 853             sched_analyze_2 (deps, XEXP (link, 0), insn);
 854         }
 855       if (find_reg_note (insn, REG_SETJMP, NULL))
 856         reg_pending_barrier = true;
 857     }
 858
 859   if (GET_CODE (insn) == JUMP_INSN)
 860     {
 861       rtx next;
 862       next = next_nonnote_insn (insn);
 863       if (next && GET_CODE (next) == BARRIER)
 864         reg_pending_barrier = true;
 865       else
 866         {
 867           rtx pending, pending_mem;
 868           regset_head tmp;
 869           INIT_REG_SET (&tmp);
 870
 871           (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp);
 872           /* Make latency of jump equal to 0 by using anti-dependence.  */
 873           EXECUTE_IF_SET_IN_REG_SET (&tmp, 0, i,
 874             {
 875               struct deps_reg *reg_last = &deps->reg_last[i];
 876               add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
 877               add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
 878               reg_last->uses_length++;
 879               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
 880             });
 881           CLEAR_REG_SET (&tmp);
 882
 883           /* All memory writes and volatile reads must happen before the
 884              jump.  Non-volatile reads must happen before the jump iff
 885              the result is needed by the above register used mask.  */
 886
 887           pending = deps->pending_write_insns;
 888           pending_mem = deps->pending_write_mems;
 889           while (pending)
 890             {
 891               add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 892               pending = XEXP (pending, 1);
 893               pending_mem = XEXP (pending_mem, 1);
 894             }
 895
 896           pending = deps->pending_read_insns;
 897           pending_mem = deps->pending_read_mems;
 898           while (pending)
 899             {
 900               if (MEM_VOLATILE_P (XEXP (pending_mem, 0)))
 901                 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
 902               pending = XEXP (pending, 1);
 903               pending_mem = XEXP (pending_mem, 1);
 904             }
 905
 906           add_dependence_list (insn, deps->last_pending_memory_flush,
 907                                REG_DEP_ANTI);
 908         }
 909     }
 910
 911   /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic
 912      block, then we must be sure that no instructions are scheduled across it.
 913      Otherwise, the reg_n_refs info (which depends on loop_depth) would
 914      become incorrect.  */
 915   if (loop_notes)
 916     {
 917       rtx link;
 918
 919       /* Update loop_notes with any notes from this insn.  Also determine
 920          if any of the notes on the list correspond to instruction scheduling
 921          barriers (loop, eh & setjmp notes, but not range notes).  */
 922       link = loop_notes;
 923       while (XEXP (link, 1))
 924         {
 925           if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG
 926               || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END
 927               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG
 928               || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END)
 929             reg_pending_barrier = true;
 930
 931           link = XEXP (link, 1);
 932         }
 933       XEXP (link, 1) = REG_NOTES (insn);
 934       REG_NOTES (insn) = loop_notes;
 935     }
 936
 937   /* If this instruction can throw an exception, then moving it changes
 938      where block boundaries fall.  This is mighty confusing elsewhere.
 939      Therefore, prevent such an instruction from being moved.  */
 940   if (can_throw_internal (insn))
 941     reg_pending_barrier = true;
 942
 943   /* Add dependencies if a scheduling barrier was found.  */
 944   if (reg_pending_barrier)
 945     {
 946       /* In the case of barrier the most added dependencies are not
 947          real, so we use anti-dependence here.  */
 948       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
 949         {
 950           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
 951             {
 952               struct deps_reg *reg_last = &deps->reg_last[i];
 953               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
 954               add_dependence_list (insn, reg_last->sets, REG_DEP_ANTI);
 955               add_dependence_list (insn, reg_last->clobbers, REG_DEP_ANTI);
 956             });
 957         }
 958       else
 959         {
 960           EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
 961             {
 962               struct deps_reg *reg_last = &deps->reg_last[i];
 963               add_dependence_list_and_free (insn, &reg_last->uses,
 964                                             REG_DEP_ANTI);
 965               add_dependence_list_and_free (insn, &reg_last->sets,
 966                                             REG_DEP_ANTI);
 967               add_dependence_list_and_free (insn, &reg_last->clobbers,
 968                                             REG_DEP_ANTI);
 969               reg_last->uses_length = 0;
 970               reg_last->clobbers_length = 0;
 971             });
 972         }
 973
 974       for (i = 0; i < deps->max_reg; i++)
 975         {
 976           struct deps_reg *reg_last = &deps->reg_last[i];
 977           reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
 978           SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
 979         }
 980
 981       flush_pending_lists (deps, insn, true, true);
 982       reg_pending_barrier = false;
 983     }
 984   else
 985     {
 986       /* If the current insn is conditional, we can't free any
 987          of the lists.  */
 988       if (GET_CODE (PATTERN (insn)) == COND_EXEC)
 989         {
 990           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
 991             {
 992               struct deps_reg *reg_last = &deps->reg_last[i];
 993               add_dependence_list (insn, reg_last->sets, 0);
 994               add_dependence_list (insn, reg_last->clobbers, 0);
 995               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
 996               reg_last->uses_length++;
 997             });
 998           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
 999             {
1000               struct deps_reg *reg_last = &deps->reg_last[i];
1001               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1002               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1003               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1004               reg_last->clobbers_length++;
1005             });
1006           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1007             {
1008               struct deps_reg *reg_last = &deps->reg_last[i];
1009               add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1010               add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT);
1011               add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1012               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1013             });
1014         }
1015       else
1016         {
1017           EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i,
1018             {
1019               struct deps_reg *reg_last = &deps->reg_last[i];
1020               add_dependence_list (insn, reg_last->sets, 0);
1021               add_dependence_list (insn, reg_last->clobbers, 0);
1022               reg_last->uses_length++;
1023               reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
1024             });
1025           EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i,
1026             {
1027               struct deps_reg *reg_last = &deps->reg_last[i];
1028               if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
1029                   || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
1030                 {
1031                   add_dependence_list_and_free (insn, &reg_last->sets,
1032                                                 REG_DEP_OUTPUT);
1033                   add_dependence_list_and_free (insn, &reg_last->uses,
1034                                                 REG_DEP_ANTI);
1035                   add_dependence_list_and_free (insn, &reg_last->clobbers,
1036                                                 REG_DEP_OUTPUT);
1037                   reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1038                   reg_last->clobbers_length = 0;
1039                   reg_last->uses_length = 0;
1040                 }
1041               else
1042                 {
1043                   add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT);
1044                   add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI);
1045                 }
1046               reg_last->clobbers_length++;
1047               reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
1048             });
1049           EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i,
1050             {
1051               struct deps_reg *reg_last = &deps->reg_last[i];
1052               add_dependence_list_and_free (insn, &reg_last->sets,
1053                                             REG_DEP_OUTPUT);
1054               add_dependence_list_and_free (insn, &reg_last->clobbers,
1055                                             REG_DEP_OUTPUT);
1056               add_dependence_list_and_free (insn, &reg_last->uses,
1057                                             REG_DEP_ANTI);
1058               reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
1059               reg_last->uses_length = 0;
1060               reg_last->clobbers_length = 0;
1061             });
1062         }
1063
1064       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
1065       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
1066       IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
1067     }
1068   CLEAR_REG_SET (reg_pending_uses);
1069   CLEAR_REG_SET (reg_pending_clobbers);
1070   CLEAR_REG_SET (reg_pending_sets);
1071
1072   /* If we are currently in a libcall scheduling group, then mark the
1073      current insn as being in a scheduling group and that it can not
1074      be moved into a different basic block.  */
1075
1076   if (deps->libcall_block_tail_insn)
1077     {
1078       set_sched_group_p (insn);
1079       CANT_MOVE (insn) = 1;
1080     }
1081
1082   /* If a post-call group is still open, see if it should remain so.
1083      This insn must be a simple move of a hard reg to a pseudo or
1084      vice-versa.
1085
1086      We must avoid moving these insns for correctness on
1087      SMALL_REGISTER_CLASS machines, and for special registers like
1088      PIC_OFFSET_TABLE_REGNUM.  For simplicity, extend this to all
1089      hard regs for all targets.  */
1090
1091   if (deps->in_post_call_group_p)
1092     {
1093       rtx tmp, set = single_set (insn);
1094       int src_regno, dest_regno;
1095
1096       if (set == NULL)
1097         goto end_call_group;
1098
1099       tmp = SET_DEST (set);
1100       if (GET_CODE (tmp) == SUBREG)
1101         tmp = SUBREG_REG (tmp);
1102       if (GET_CODE (tmp) == REG)
1103         dest_regno = REGNO (tmp);
1104       else
1105         goto end_call_group;
1106
1107       tmp = SET_SRC (set);
1108       if (GET_CODE (tmp) == SUBREG)
1109         tmp = SUBREG_REG (tmp);
1110       if (GET_CODE (tmp) == REG)
1111         src_regno = REGNO (tmp);
1112       else
1113         goto end_call_group;
1114
1115       if (src_regno < FIRST_PSEUDO_REGISTER
1116           || dest_regno < FIRST_PSEUDO_REGISTER)
1117         {
1118           set_sched_group_p (insn);
1119           CANT_MOVE (insn) = 1;
1120         }
1121       else
1122         {
1123         end_call_group:
1124           deps->in_post_call_group_p = false;
1125         }
1126     }
1127 }
1128
1129 /* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS
1130    for every dependency.  */
1131
1132 void
1133 sched_analyze (deps, head, tail)
1134      struct deps *deps;
1135      rtx head, tail;
1136 {
1137   rtx insn;
1138   rtx loop_notes = 0;
1139
1140   if (current_sched_info->use_cselib)
1141     cselib_init ();
1142
1143   for (insn = head;; insn = NEXT_INSN (insn))
1144     {
1145       rtx link, end_seq, r0, set;
1146
1147       if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1148         {
1149           /* Clear out the stale LOG_LINKS from flow.  */
1150           free_INSN_LIST_list (&LOG_LINKS (insn));
1151
1152           /* Make each JUMP_INSN a scheduling barrier for memory
1153              references.  */
1154           if (GET_CODE (insn) == JUMP_INSN)
1155             {
1156               /* Keep the list a reasonable size.  */
1157               if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
1158                 flush_pending_lists (deps, insn, true, true);
1159               else
1160                 deps->last_pending_memory_flush
1161                   = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
1162             }
1163           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1164           loop_notes = 0;
1165         }
1166       else if (GET_CODE (insn) == CALL_INSN)
1167         {
1168           int i;
1169
1170           CANT_MOVE (insn) = 1;
1171
1172           /* Clear out the stale LOG_LINKS from flow.  */
1173           free_INSN_LIST_list (&LOG_LINKS (insn));
1174
1175           if (find_reg_note (insn, REG_SETJMP, NULL))
1176             {
1177               /* This is setjmp.  Assume that all registers, not just
1178                  hard registers, may be clobbered by this call.  */
1179               reg_pending_barrier = true;
1180             }
1181           else
1182             {
1183               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1184                 /* A call may read and modify global register variables.  */
1185                 if (global_regs[i])
1186                   {
1187                     SET_REGNO_REG_SET (reg_pending_sets, i);
1188                     SET_REGNO_REG_SET (reg_pending_uses, i);
1189                   }
1190                 /* Other call-clobbered hard regs may be clobbered.
1191                    Since we only have a choice between 'might be clobbered'
1192                    and 'definitely not clobbered', we must include all
1193                    partly call-clobbered registers here.  */
1194                 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
1195                          || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1196                   SET_REGNO_REG_SET (reg_pending_clobbers, i);
1197                 /* We don't know what set of fixed registers might be used
1198                    by the function, but it is certain that the stack pointer
1199                    is among them, but be conservative.  */
1200                 else if (fixed_regs[i])
1201                   SET_REGNO_REG_SET (reg_pending_uses, i);
1202                 /* The frame pointer is normally not used by the function
1203                    itself, but by the debugger.  */
1204                 /* ??? MIPS o32 is an exception.  It uses the frame pointer
1205                    in the macro expansion of jal but does not represent this
1206                    fact in the call_insn rtl.  */
1207                 else if (i == FRAME_POINTER_REGNUM
1208                          || (i == HARD_FRAME_POINTER_REGNUM
1209                              && (! reload_completed || frame_pointer_needed)))
1210                   SET_REGNO_REG_SET (reg_pending_uses, i);
1211             }
1212
1213           /* For each insn which shouldn't cross a call, add a dependence
1214              between that insn and this call insn.  */
1215           add_dependence_list_and_free (insn, &deps->sched_before_next_call,
1216                                         REG_DEP_ANTI);
1217
1218           sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes);
1219           loop_notes = 0;
1220
1221           /* In the absence of interprocedural alias analysis, we must flush
1222              all pending reads and writes, and start new dependencies starting
1223              from here.  But only flush writes for constant calls (which may
1224              be passed a pointer to something we haven't written yet).  */
1225           flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
1226
1227           /* Remember the last function call for limiting lifetimes.  */
1228           free_INSN_LIST_list (&deps->last_function_call);
1229           deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
1230
1231           /* Before reload, begin a post-call group, so as to keep the
1232              lifetimes of hard registers correct.  */
1233           if (! reload_completed)
1234             deps->in_post_call_group_p = true;
1235         }
1236
1237       /* See comments on reemit_notes as to why we do this.
1238          ??? Actually, the reemit_notes just say what is done, not why.  */
1239
1240       if (GET_CODE (insn) == NOTE
1241                && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
1242                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
1243                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1244                    || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
1245         {
1246           rtx rtx_region;
1247
1248           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG
1249               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
1250             rtx_region = GEN_INT (NOTE_EH_HANDLER (insn));
1251           else
1252             rtx_region = GEN_INT (0);
1253
1254           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1255                                         rtx_region,
1256                                         loop_notes);
1257           loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE,
1258                                         GEN_INT (NOTE_LINE_NUMBER (insn)),
1259                                         loop_notes);
1260           CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn);
1261         }
1262
1263       if (current_sched_info->use_cselib)
1264         cselib_process_insn (insn);
1265
1266       /* Now that we have completed handling INSN, check and see if it is
1267          a CLOBBER beginning a libcall block.   If it is, record the
1268          end of the libcall sequence.
1269
1270          We want to schedule libcall blocks as a unit before reload.  While
1271          this restricts scheduling, it preserves the meaning of a libcall
1272          block.
1273
1274          As a side effect, we may get better code due to decreased register
1275          pressure as well as less chance of a foreign insn appearing in
1276          a libcall block.  */
1277       if (!reload_completed
1278           /* Note we may have nested libcall sequences.  We only care about
1279              the outermost libcall sequence.  */
1280           && deps->libcall_block_tail_insn == 0
1281           /* The sequence must start with a clobber of a register.  */
1282           && GET_CODE (insn) == INSN
1283           && GET_CODE (PATTERN (insn)) == CLOBBER
1284           && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG)
1285           && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
1286           /* The CLOBBER must also have a REG_LIBCALL note attached.  */
1287           && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1288           && (end_seq = XEXP (link, 0)) != 0
1289           /* The insn referenced by the REG_LIBCALL note must be a
1290              simple nop copy with the same destination as the register
1291              mentioned in the clobber.  */
1292           && (set = single_set (end_seq)) != 0
1293           && SET_DEST (set) == r0 && SET_SRC (set) == r0
1294           /* And finally the insn referenced by the REG_LIBCALL must
1295              also contain a REG_EQUAL note and a REG_RETVAL note.  */
1296           && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
1297           && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
1298         deps->libcall_block_tail_insn = XEXP (link, 0);
1299
1300       /* If we have reached the end of a libcall block, then close the
1301          block.  */
1302       if (deps->libcall_block_tail_insn == insn)
1303         deps->libcall_block_tail_insn = 0;
1304
1305       if (insn == tail)
1306         {
1307           if (current_sched_info->use_cselib)
1308             cselib_finish ();
1309           return;
1310         }
1311     }
1312   abort ();
1313 }
1314 \f
1315
1316 /* The following function adds forward dependence (FROM, TO) with
1317    given DEP_TYPE.  The forward dependence should be not exist before.  */
1318
1319 void
1320 add_forward_dependence (from, to, dep_type)
1321      rtx from;
1322      rtx to;
1323      enum reg_note dep_type;
1324 {
1325   rtx new_link;
1326
1327 #ifdef ENABLE_CHECKING
1328   /* If add_dependence is working properly there should never
1329      be notes, deleted insns or duplicates in the backward
1330      links.  Thus we need not check for them here.
1331
1332      However, if we have enabled checking we might as well go
1333      ahead and verify that add_dependence worked properly.  */
1334   if (GET_CODE (from) == NOTE
1335       || INSN_DELETED_P (from)
1336       || (forward_dependency_cache != NULL
1337           && TEST_BIT (forward_dependency_cache[INSN_LUID (from)],
1338                        INSN_LUID (to)))
1339       || (forward_dependency_cache == NULL
1340           && find_insn_list (to, INSN_DEPEND (from))))
1341     abort ();
1342   if (forward_dependency_cache != NULL)
1343     SET_BIT (forward_dependency_cache[INSN_LUID (from)],
1344              INSN_LUID (to));
1345 #endif
1346
1347   new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
1348
1349   PUT_REG_NOTE_KIND (new_link, dep_type);
1350
1351   INSN_DEPEND (from) = new_link;
1352   INSN_DEP_COUNT (to) += 1;
1353 }
1354
1355 /* Examine insns in the range [ HEAD, TAIL ] and Use the backward
1356    dependences from LOG_LINKS to build forward dependences in
1357    INSN_DEPEND.  */
1358
1359 void
1360 compute_forward_dependences (head, tail)
1361      rtx head, tail;
1362 {
1363   rtx insn, link;
1364   rtx next_tail;
1365
1366   next_tail = NEXT_INSN (tail);
1367   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1368     {
1369       if (! INSN_P (insn))
1370         continue;
1371
1372       for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
1373         add_forward_dependence (XEXP (link, 0), insn, REG_NOTE_KIND (link));
1374     }
1375 }
1376 \f
1377 /* Initialize variables for region data dependence analysis.
1378    n_bbs is the number of region blocks.  */
1379
1380 void
1381 init_deps (deps)
1382      struct deps *deps;
1383 {
1384   int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
1385
1386   deps->max_reg = max_reg;
1387   deps->reg_last = (struct deps_reg *)
1388     xcalloc (max_reg, sizeof (struct deps_reg));
1389   INIT_REG_SET (&deps->reg_last_in_use);
1390
1391   deps->pending_read_insns = 0;
1392   deps->pending_read_mems = 0;
1393   deps->pending_write_insns = 0;
1394   deps->pending_write_mems = 0;
1395   deps->pending_lists_length = 0;
1396   deps->pending_flush_length = 0;
1397   deps->last_pending_memory_flush = 0;
1398   deps->last_function_call = 0;
1399   deps->sched_before_next_call = 0;
1400   deps->in_post_call_group_p = false;
1401   deps->libcall_block_tail_insn = 0;
1402 }
1403
1404 /* Free insn lists found in DEPS.  */
1405
1406 void
1407 free_deps (deps)
1408      struct deps *deps;
1409 {
1410   int i;
1411
1412   free_INSN_LIST_list (&deps->pending_read_insns);
1413   free_EXPR_LIST_list (&deps->pending_read_mems);
1414   free_INSN_LIST_list (&deps->pending_write_insns);
1415   free_EXPR_LIST_list (&deps->pending_write_mems);
1416   free_INSN_LIST_list (&deps->last_pending_memory_flush);
1417
1418   /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions
1419      times.  For a test case with 42000 regs and 8000 small basic blocks,
1420      this loop accounted for nearly 60% (84 sec) of the total -O2 runtime.  */
1421   EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i,
1422     {
1423       struct deps_reg *reg_last = &deps->reg_last[i];
1424       if (reg_last->uses)
1425         free_INSN_LIST_list (&reg_last->uses);
1426       if (reg_last->sets)
1427         free_INSN_LIST_list (&reg_last->sets);
1428       if (reg_last->clobbers)
1429         free_INSN_LIST_list (&reg_last->clobbers);
1430     });
1431   CLEAR_REG_SET (&deps->reg_last_in_use);
1432
1433   free (deps->reg_last);
1434 }
1435
1436 /* If it is profitable to use them, initialize caches for tracking
1437    dependency information.  LUID is the number of insns to be scheduled,
1438    it is used in the estimate of profitability.  */
1439
1440 void
1441 init_dependency_caches (luid)
1442      int luid;
1443 {
1444   /* ?!? We could save some memory by computing a per-region luid mapping
1445      which could reduce both the number of vectors in the cache and the size
1446      of each vector.  Instead we just avoid the cache entirely unless the
1447      average number of instructions in a basic block is very high.  See
1448      the comment before the declaration of true_dependency_cache for
1449      what we consider "very high".  */
1450   if (luid / n_basic_blocks > 100 * 5)
1451     {
1452       true_dependency_cache = sbitmap_vector_alloc (luid, luid);
1453       sbitmap_vector_zero (true_dependency_cache, luid);
1454       anti_dependency_cache = sbitmap_vector_alloc (luid, luid);
1455       sbitmap_vector_zero (anti_dependency_cache, luid);
1456       output_dependency_cache = sbitmap_vector_alloc (luid, luid);
1457       sbitmap_vector_zero (output_dependency_cache, luid);
1458 #ifdef ENABLE_CHECKING
1459       forward_dependency_cache = sbitmap_vector_alloc (luid, luid);
1460       sbitmap_vector_zero (forward_dependency_cache, luid);
1461 #endif
1462     }
1463 }
1464
1465 /* Free the caches allocated in init_dependency_caches.  */
1466
1467 void
1468 free_dependency_caches ()
1469 {
1470   if (true_dependency_cache)
1471     {
1472       sbitmap_vector_free (true_dependency_cache);
1473       true_dependency_cache = NULL;
1474       sbitmap_vector_free (anti_dependency_cache);
1475       anti_dependency_cache = NULL;
1476       sbitmap_vector_free (output_dependency_cache);
1477       output_dependency_cache = NULL;
1478 #ifdef ENABLE_CHECKING
1479       sbitmap_vector_free (forward_dependency_cache);
1480       forward_dependency_cache = NULL;
1481 #endif
1482     }
1483 }
1484
1485 /* Initialize some global variables needed by the dependency analysis
1486    code.  */
1487
1488 void
1489 init_deps_global ()
1490 {
1491   reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head);
1492   reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head);
1493   reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head);
1494   reg_pending_barrier = false;
1495 }
1496
1497 /* Free everything used by the dependency analysis code.  */
1498
1499 void
1500 finish_deps_global ()
1501 {
1502   FREE_REG_SET (reg_pending_sets);
1503   FREE_REG_SET (reg_pending_clobbers);
1504   FREE_REG_SET (reg_pending_uses);
1505 }