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