gcc/ra.h

   1 /* Graph coloring register allocator
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Michael Matz <matz@suse.de>
   4    and Daniel Berlin <dan@cgsoftware.com>.
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify it under the
   9    terms of the GNU General Public License as published by the Free Software
  10    Foundation; either version 2, or (at your option) any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  15    details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with GCC; see the file COPYING.  If not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 #ifndef GCC_RA_H
  22 #define GCC_RA_H
  23
  24 #include "bitmap.h"
  25 #include "sbitmap.h"
  26 #include "hard-reg-set.h"
  27 #include "insn-modes.h"
  28
  29 /* Double linked list to implement the per-type lists of webs
  30    and moves.  */
  31 struct dlist
  32 {
  33   struct dlist *prev;
  34   struct dlist *next;
  35   union
  36     {
  37       struct web *web;
  38       struct move *move;
  39     } value;
  40 };
  41 /* Simple helper macros for ease of misuse.  */
  42 #define DLIST_WEB(l) ((l)->value.web)
  43 #define DLIST_MOVE(l) ((l)->value.move)
  44
  45 /* Classification of a given node (i.e. what state it's in).  */
  46 enum ra_node_type
  47 {
  48   INITIAL = 0, FREE,
  49   PRECOLORED,
  50   SIMPLIFY, SIMPLIFY_SPILL, SIMPLIFY_FAT, FREEZE, SPILL,
  51   SELECT,
  52   SPILLED, COALESCED, COLORED,
  53   LAST_NODE_TYPE
  54 };
  55
  56 /* A list of conflict bitmaps, factorized on the exact part of
  57    the source, which conflicts with the DEFs, whose ID are noted in
  58    the bitmap.  This is used while building web-parts with conflicts.  */
  59 struct tagged_conflict
  60 {
  61   struct tagged_conflict *next;
  62   bitmap conflicts;
  63
  64   /* If the part of source identified by size S, byteoffset O conflicts,
  65      then size_word == S | (O << 16).  */
  66   unsigned int size_word;
  67 };
  68
  69 /* Such a structure is allocated initially for each def and use.
  70    In the process of building the interference graph web parts are
  71    connected together, if they have common instructions and reference the
  72    same register.  That way live ranges are build (by connecting defs and
  73    uses) and implicitly complete webs (by connecting web parts in common
  74    uses).  */
  75 struct web_part
  76 {
  77   /* The def or use for this web part.  */
  78   struct ref *ref;
  79   /* The uplink implementing the disjoint set.  */
  80   struct web_part *uplink;
  81
  82   /* Here dynamic information associated with each def/use is saved.
  83      This all is only valid for root web parts (uplink==NULL).
  84      That's the information we need to merge, if web parts are unioned.  */
  85
  86   /* Number of spanned insns containing any deaths.  */
  87   unsigned int spanned_deaths;
  88   /* The list of bitmaps of DEF ID's with which this part conflicts.  */
  89   struct tagged_conflict *sub_conflicts;
  90   /* If there's any call_insn, while this part is live.  */
  91   unsigned int crosses_call : 1;
  92 };
  93
  94 /* Web structure used to store info about connected live ranges.
  95    This represents the nodes of the interference graph, which gets
  96    colored.  It can also hold subwebs, which are contained in webs
  97    and represent subregs.  */
  98 struct web
  99 {
 100   /* Unique web ID.  */
 101   unsigned int id;
 102
 103   /* Register number of the live range's variable.  */
 104   unsigned int regno;
 105
 106   /* How many insns containing deaths do we span?  */
 107   unsigned int span_deaths;
 108
 109   /* Spill_temp indicates if this web was part of a web spilled in the
 110      last iteration, or or reasons why this shouldn't be spilled again.
 111      1 spill web, can't be spilled.
 112      2 big spill web (live over some deaths).  Discouraged, but not
 113        impossible to spill again.
 114      3 short web (spans no deaths), can't be spilled.  */
 115   unsigned int spill_temp;
 116
 117   /* When coalescing we might change spill_temp.  If breaking aliases we
 118      need to restore it.  */
 119   unsigned int orig_spill_temp;
 120
 121   /* Cost of spilling.  */
 122   unsigned HOST_WIDE_INT spill_cost;
 123   unsigned HOST_WIDE_INT orig_spill_cost;
 124
 125   /* How many webs are aliased to us?  */
 126   unsigned int num_aliased;
 127
 128   /* The color we got.  This is a hardreg number.  */
 129   int color;
 130   /* 1 + the color this web got in the last pass.  If it hadn't got a color,
 131      or we are in the first pass, or this web is a new one, this is zero.  */
 132   int old_color;
 133
 134   /* Now follow some flags characterizing the web.  */
 135
 136   /* Nonzero, if we should use usable_regs for this web, instead of
 137      preferred_class() or alternate_class().  */
 138   unsigned int use_my_regs:1;
 139
 140   /* Nonzero if we selected this web as possible spill candidate in
 141      select_spill().  */
 142   unsigned int was_spilled:1;
 143
 144   /* We need to distinguish also webs which are targets of coalescing
 145      (all x with some y, so that x==alias(y)), but the alias field is
 146      only set for sources of coalescing.  This flag is set for all webs
 147      involved in coalescing in some way.  */
 148   unsigned int is_coalesced:1;
 149
 150   /* Nonzero, if this web (or subweb) doesn't correspond with any of
 151      the current functions actual use of reg rtx.  Happens e.g. with
 152      conflicts to a web, of which only a part was still undefined at the
 153      point of that conflict.  In this case we construct a subweb
 154      representing these yet undefined bits to have a target for the
 155      conflict.  Suppose e.g. this sequence:
 156      (set (reg:DI x) ...)
 157      (set (reg:SI y) ...)
 158      (set (subreg:SI (reg:DI x) 0) ...)
 159      (use (reg:DI x))
 160      Here x only partly conflicts with y.  Namely only (subreg:SI (reg:DI x)
 161      1) conflicts with it, but this rtx doesn't show up in the program.  For
 162      such things an "artificial" subweb is built, and this flag is true for
 163      them.  */
 164   unsigned int artificial:1;
 165
 166   /* Nonzero if we span a call_insn.  */
 167   unsigned int crosses_call:1;
 168
 169   /* Wether the web is involved in a move insn.  */
 170   unsigned int move_related:1;
 171
 172   /* 1 when this web (or parts thereof) are live over an abnormal edge.  */
 173   unsigned int live_over_abnormal:1;
 174
 175   /* Nonzero if this web is used in subregs where the mode change
 176      was illegal for hardregs in CLASS_CANNOT_CHANGE_MODE.  */
 177   unsigned int mode_changed:1;
 178
 179   /* Nonzero if some references of this web, where in subreg context,
 180      but the actual subreg is already stripped (i.e. we don't know the
 181      outer mode of the actual reference).  */
 182   unsigned int subreg_stripped:1;
 183
 184   /* Nonzero, when this web stems from the last pass of the allocator,
 185      and all info is still valid (i.e. it wasn't spilled).  */
 186   unsigned int old_web:1;
 187
 188   /* Used in rewrite_program2() to remember webs, which
 189      are already marked for (re)loading.  */
 190   unsigned int in_load:1;
 191
 192   /* If in_load is != 0, then this is nonzero, if only one use was seen
 193      since insertion in loadlist.  Zero if more uses currently need a
 194      reload.  Used to differentiate between inserting register loads or
 195      directly substituting the stackref.  */
 196   unsigned int one_load:1;
 197
 198   /* When using rewrite_program2() this flag gets set if some insns
 199      were inserted on behalf of this web.  IR spilling might ignore some
 200      deaths up to the def, so no code might be emitted and we need not to
 201      spill such a web again.  */
 202   unsigned int changed:1;
 203
 204   /* With interference region spilling it's sometimes the case, that a
 205      bb border is also an IR border for webs, which were targets of moves,
 206      which are already removed due to coalescing.  All webs, which are
 207      a destination of such a removed move, have this flag set.  */
 208   unsigned int target_of_spilled_move:1;
 209
 210   /* For optimistic coalescing we need to be able to break aliases, which
 211      includes restoring conflicts to those before coalescing.  This flag
 212      is set, if we have a list of conflicts before coalescing.  It's needed
 213      because that list is lazily constructed only when actually needed.  */
 214   unsigned int have_orig_conflicts:1;
 215
 216   /* Current state of the node.  */
 217   ENUM_BITFIELD(ra_node_type) type:5;
 218
 219   /* A regclass, combined from preferred and alternate class, or calculated
 220      from usable_regs.  Used only for debugging, and to determine
 221      add_hardregs.  */
 222   ENUM_BITFIELD(reg_class) regclass:10;
 223
 224   /* Additional consecutive hardregs needed for this web.  */
 225   int add_hardregs;
 226
 227   /* Number of conflicts currently.  */
 228   int num_conflicts;
 229
 230   /* Numbers of uses and defs, which belong to this web.  */
 231   unsigned int num_uses;
 232   unsigned int num_defs;
 233
 234   /* The (reg:M a) or (subreg:M1 (reg:M2 a) x) rtx which this
 235      web is based on.  This is used to distinguish subreg webs
 236      from it's reg parents, and to get hold of the mode.  */
 237   rtx orig_x;
 238
 239   /* If this web is a subweb, this point to the super web.  Otherwise
 240      it's NULL.  */
 241   struct web *parent_web;
 242
 243   /* If this web is a subweb, but not the last one, this points to the
 244      next subweb of the same super web.  Otherwise it's NULL.  */
 245   struct web *subreg_next;
 246
 247   /* The set of webs (or subwebs), this web conflicts with.  */
 248   struct conflict_link *conflict_list;
 249
 250   /* If have_orig_conflicts is set this contains a copy of conflict_list,
 251      as it was right after building the interference graph.
 252      It's used for incremental i-graph building and for breaking
 253      coalescings again.  */
 254   struct conflict_link *orig_conflict_list;
 255
 256   /* Bitmap of all conflicts which don't count this pass, because of
 257      non-intersecting hardregs of the conflicting webs.  See also
 258      record_conflict().  */
 259   bitmap useless_conflicts;
 260
 261   /* Different sets of hard registers, for all usable registers, ...  */
 262   HARD_REG_SET usable_regs;
 263   /* ... the same before coalescing, ...  */
 264   HARD_REG_SET orig_usable_regs;
 265   /* ... colors of all already colored neighbors (used when biased coloring
 266      is active), and ...  */
 267   HARD_REG_SET bias_colors;
 268   /* ... colors of PRECOLORED webs this web is connected to by a move.  */
 269   HARD_REG_SET prefer_colors;
 270
 271   /* Number of usable colors in usable_regs.  */
 272   int num_freedom;
 273
 274   /* After successful coloring the graph each web gets a new reg rtx,
 275      with which the original uses and defs are replaced.  This is it.  */
 276   rtx reg_rtx;
 277
 278   /* While spilling this is the rtx of the home of spilled webs.
 279      It can be a mem ref (a stack slot), or a pseudo register.  */
 280   rtx stack_slot;
 281
 282   /* Used in rewrite_program2() to remember the using
 283      insn last seen for webs needing (re)loads.  */
 284   rtx last_use_insn;
 285
 286   /* If this web is rematerializable, this contains the RTL pattern
 287      usable as source for that.  Otherwise it's NULL.  */
 288   rtx pattern;
 289
 290   /* All the defs and uses.  There are num_defs, resp.
 291      num_uses elements.  */
 292   struct ref **defs; /* [0..num_defs-1] */
 293   struct ref **uses; /* [0..num_uses-1] */
 294
 295   /* The web to which this web is aliased (coalesced).  If NULL, this
 296      web is not coalesced into some other (but might still be a target
 297      for other webs).  */
 298   struct web *alias;
 299
 300   /* With iterated coalescing this is a list of active moves this web
 301      is involved in.  */
 302   struct move_list *moves;
 303
 304   /* The list implementation.  */
 305   struct dlist *dlink;
 306
 307   /* While building webs, out of web-parts, this holds a (partial)
 308      list of all refs for this web seen so far.  */
 309   struct df_link *temp_refs;
 310 };
 311
 312 /* For implementing a single linked list.  */
 313 struct web_link
 314 {
 315   struct web_link *next;
 316   struct web *web;
 317 };
 318
 319 /* A subconflict is part of a conflict edge to track precisely,
 320    which parts of two webs conflict, in case not all of both webs do.  */
 321 struct sub_conflict
 322 {
 323   /* The next partial conflict.  For one such list the parent-web of
 324      all the S webs, resp. the parent of all the T webs are constant.  */
 325   struct sub_conflict *next;
 326   struct web *s;
 327   struct web *t;
 328 };
 329
 330 /* This represents an edge in the conflict graph.  */
 331 struct conflict_link
 332 {
 333   struct conflict_link *next;
 334
 335   /* The web we conflict with (the Target of the edge).  */
 336   struct web *t;
 337
 338   /* If not the complete source web and T conflict, this points to
 339      the list of parts which really conflict.  */
 340   struct sub_conflict *sub;
 341 };
 342
 343 /* For iterated coalescing the moves can be in these states.  */
 344 enum move_type
 345 {
 346   WORKLIST, MV_COALESCED, CONSTRAINED, FROZEN, ACTIVE,
 347   LAST_MOVE_TYPE
 348 };
 349
 350 /* Structure of a move we are considering coalescing.  */
 351 struct move
 352 {
 353   rtx insn;
 354   struct web *source_web;
 355   struct web *target_web;
 356   enum move_type type;
 357   struct dlist *dlink;
 358 };
 359
 360 /* List of moves.  */
 361 struct move_list
 362 {
 363   struct move_list *next;
 364   struct move *move;
 365 };
 366
 367 /* To have fast access to the defs and uses per insn, we have one such
 368    structure per insn.  The difference to the normal df.c structures is,
 369    that it doesn't contain any NULL refs, which df.c produces in case
 370    an insn was modified and it only contains refs to pseudo regs, or to
 371    hardregs which matter for allocation, i.e. those not in
 372    never_use_colors.  */
 373 struct ra_insn_info
 374 {
 375   unsigned int num_defs, num_uses;
 376   struct ref **defs, **uses;
 377 };
 378
 379 /* The above structures are stored in this array, indexed by UID...  */
 380 extern struct ra_insn_info *insn_df;
 381 /* ... and the size of that array, as we add insn after setting it up.  */
 382 extern int insn_df_max_uid;
 383
 384 /* The interference graph.  */
 385 extern sbitmap igraph;
 386 /* And how to access it.  I and J are web indices.  If the bit
 387    igraph_index(I, J) is set, then they conflict.  Note, that
 388    if only parts of webs conflict, then also only those parts
 389    are noted in the I-graph (i.e. the parent webs not).  */
 390 #define igraph_index(i, j) ((i) < (j) ? ((j)*((j)-1)/2)+(i) : ((i)*((i)-1)/2)+(j))
 391 /* This is the bitmap of all (even partly) conflicting super webs.
 392    If bit I*num_webs+J or J*num_webs+I is set, then I and J (both being
 393    super web indices) conflict, maybe only partially.  Note the
 394    asymmetry.  */
 395 extern sbitmap sup_igraph;
 396
 397 /* After the first pass, and when interference region spilling is
 398    activated, bit I is set, when the insn with UID I contains some
 399    refs to pseudos which die at the insn.  */
 400 extern sbitmap insns_with_deaths;
 401 /* The size of that sbitmap.  */
 402 extern int death_insns_max_uid;
 403
 404 /* All the web-parts.  There are exactly as many web-parts as there
 405    are register refs in the insn stream.  */
 406 extern struct web_part *web_parts;
 407
 408 /* The number of all webs, including subwebs.  */
 409 extern unsigned int num_webs;
 410 /* The number of just the subwebs.  */
 411 extern unsigned int num_subwebs;
 412 /* The number of all webs, including subwebs.  */
 413 extern unsigned int num_allwebs;
 414
 415 /* For easy access when given a web ID: id2web[W->id] == W.  */
 416 extern struct web **id2web;
 417 /* For each hardreg, the web which represents it.  */
 418 extern struct web *hardreg2web[FIRST_PSEUDO_REGISTER];
 419
 420 /* Given the ID of a df_ref, which represent a DEF, def2web[ID] is
 421    the web, to which this def belongs.  */
 422 extern struct web **def2web;
 423 /* The same as def2web, just for uses.  */
 424 extern struct web **use2web;
 425
 426 /* The list of all recognized and coalescable move insns.  */
 427 extern struct move_list *wl_moves;
 428
 429
 430 /* Some parts of the compiler which we run after colorizing
 431    clean reg_renumber[], so we need another place for the colors.
 432    This is copied to reg_renumber[] just before returning to toplev.  */
 433 extern short *ra_reg_renumber;
 434 /* The size of that array.  Some passes after coloring might have created
 435    new pseudos, which will get no color.  */
 436 extern int ra_max_regno;
 437
 438 /* The dataflow structure of the current function, while regalloc
 439    runs.  */
 440 extern struct df *df;
 441
 442 /* For each basic block B we have a bitmap of DF_REF_ID's of uses,
 443    which backward reach the end of B.  */
 444 extern bitmap *live_at_end;
 445
 446 /* One pass is: collecting registers refs, building I-graph, spilling.
 447    And this is how often we already ran that for the current function.  */
 448 extern int ra_pass;
 449
 450 /* The maximum pseudo regno, just before register allocation starts.
 451    While regalloc runs all pseudos with a larger number represent
 452    potentially stack slots or hardregs.  I call them stackwebs or
 453    stackpseudos.  */
 454 extern unsigned int max_normal_pseudo;
 455
 456 /* One of the fixed colors.  It must be < FIRST_PSEUDO_REGISTER, because
 457    we sometimes want to check the color against a HARD_REG_SET.  It must
 458    be >= 0, because negative values mean "no color".
 459    This color is used for the above stackwebs, when they can't be colored.
 460    I.e. normally they would be spilled, but they already represent
 461    stackslots.  So they are colored with an invalid color.  It has
 462    the property that even webs which conflict can have that color at the
 463    same time.  I.e. a stackweb with that color really represents a
 464    stackslot.  */
 465 extern int an_unusable_color;
 466
 467 /* While building the I-graph, every time insn UID is looked at,
 468    number_seen[UID] is incremented.  For debugging.  */
 469 extern int *number_seen;
 470
 471 /* The different lists on which a web can be (based on the type).  */
 472 extern struct dlist *web_lists[(int) LAST_NODE_TYPE];
 473 #define WEBS(type) (web_lists[(int)(type)])
 474
 475 /* The largest DF_REF_ID of defs resp. uses, as it was in the
 476    last pass.  In the first pass this is zero.  Used to distinguish new
 477    from old references.  */
 478 extern unsigned int last_def_id;
 479 extern unsigned int last_use_id;
 480
 481 /* Similar for UIDs and number of webs.  */
 482 extern int last_max_uid;
 483 extern unsigned int last_num_webs;
 484
 485 /* If I is the ID of an old use, and last_check_uses[I] is set,
 486    then we must reevaluate it's flow while building the new I-graph.  */
 487 extern sbitmap last_check_uses;
 488
 489 /* If nonzero, record_conflict() saves the current conflict list of
 490    webs in orig_conflict_list, when not already done so, and the conflict
 491    list is going to be changed.  It is set, after initially building the
 492    I-graph.  I.e. new conflicts due to coalescing trigger that copying.  */
 493 extern unsigned int remember_conflicts;
 494
 495 /* The maximum UID right before calling regalloc().
 496    Used to detect any instructions inserted by the allocator.  */
 497 extern int orig_max_uid;
 498
 499 /* A HARD_REG_SET of those color, which can't be used for coalescing.
 500    Includes e.g. fixed_regs.  */
 501 extern HARD_REG_SET never_use_colors;
 502 /* For each class C this is reg_class_contents[C] \ never_use_colors.  */
 503 extern HARD_REG_SET usable_regs[N_REG_CLASSES];
 504 /* For each class C the count of hardregs in usable_regs[C].  */
 505 extern unsigned int num_free_regs[N_REG_CLASSES];
 506 /* For each class C which has num_free_regs[C]==1, the color of the
 507    single register in that class, -1 otherwise.  */
 508 extern int single_reg_in_regclass[N_REG_CLASSES];
 509 /* For each mode M the hardregs, which are MODE_OK for M, and have
 510    enough space behind them to hold an M value.  Additionally
 511    if reg R is OK for mode M, but it needs two hardregs, then R+1 will
 512    also be set here, even if R+1 itself is not OK for M.  I.e. this
 513    represent the possible resources which could be taken away be a value
 514    in mode M.  */
 515 extern HARD_REG_SET hardregs_for_mode[NUM_MACHINE_MODES];
 516 /* The set of hardregs, for which _any_ mode change is invalid.  */
 517 extern HARD_REG_SET invalid_mode_change_regs;
 518 /* For 0 <= I <= 255, the number of bits set in I.  Used to calculate
 519    the number of set bits in a HARD_REG_SET.  */
 520 extern unsigned char byte2bitcount[256];
 521
 522 /* Expressive helper macros.  */
 523 #define ID2WEB(I) id2web[I]
 524 #define NUM_REGS(W) (((W)->type == PRECOLORED) ? 1 : (W)->num_freedom)
 525 #define SUBWEB_P(W) (GET_CODE ((W)->orig_x) == SUBREG)
 526
 527 /* Constant usable as debug area to ra_debug_msg.  */
 528 #define DUMP_COSTS              0x0001
 529 #define DUMP_WEBS               0x0002
 530 #define DUMP_IGRAPH             0x0004
 531 #define DUMP_PROCESS            0x0008
 532 #define DUMP_COLORIZE           0x0010
 533 #define DUMP_ASM                0x0020
 534 #define DUMP_CONSTRAINTS        0x0040
 535 #define DUMP_RESULTS            0x0080
 536 #define DUMP_DF                 0x0100
 537 #define DUMP_RTL                0x0200
 538 #define DUMP_FINAL_RTL          0x0400
 539 #define DUMP_REGCLASS           0x0800
 540 #define DUMP_SM                 0x1000
 541 #define DUMP_LAST_FLOW          0x2000
 542 #define DUMP_LAST_RTL           0x4000
 543 #define DUMP_REBUILD            0x8000
 544 #define DUMP_IGRAPH_M           0x10000
 545 #define DUMP_VALIDIFY           0x20000
 546 #define DUMP_EVER               ((unsigned int)-1)
 547 #define DUMP_NEARLY_EVER        (DUMP_EVER - DUMP_COSTS - DUMP_IGRAPH_M)
 548
 549 /* All the wanted debug levels as ORing of the various DUMP_xxx
 550    constants.  */
 551 extern unsigned int debug_new_regalloc;
 552
 553 /* Nonzero means we want biased coloring.  */
 554 extern int flag_ra_biased;
 555
 556 /* Nonzero if we want to use improved (and slow) spilling.  This
 557    includes also interference region spilling (see below).  */
 558 extern int flag_ra_improved_spilling;
 559
 560 /* Nonzero for using interference region spilling.  Zero for improved
 561    Chaintin style spilling (only at deaths).  */
 562 extern int flag_ra_ir_spilling;
 563
 564 /* Nonzero if we use optimistic coalescing, zero for iterated
 565    coalescing.  */
 566 extern int flag_ra_optimistic_coalescing;
 567
 568 /* Nonzero if we want to break aliases of spilled webs.  Forced to
 569    nonzero, when flag_ra_optimistic_coalescing is.  */
 570 extern int flag_ra_break_aliases;
 571
 572 /* Nonzero if we want to merge the spill costs of webs which
 573    are coalesced.  */
 574 extern int flag_ra_merge_spill_costs;
 575
 576 /* Nonzero if we want to spill at every use, instead of at deaths,
 577    or interference region borders.  */
 578 extern int flag_ra_spill_every_use;
 579
 580 /* Nonzero to output all notes in the debug dumps.  */
 581 extern int flag_ra_dump_notes;
 582
 583 extern void * ra_alloc (size_t);
 584 extern void * ra_calloc (size_t);
 585 extern int hard_regs_count (HARD_REG_SET);
 586 extern rtx ra_emit_move_insn (rtx, rtx);
 587 extern void ra_debug_msg (unsigned int, const char *, ...) ATTRIBUTE_PRINTF_2;
 588 extern int hard_regs_intersect_p (HARD_REG_SET *, HARD_REG_SET *);
 589 extern unsigned int rtx_to_bits (rtx);
 590 extern struct web * find_subweb (struct web *, rtx);
 591 extern struct web * find_subweb_2 (struct web *, unsigned int);
 592 extern struct web * find_web_for_subweb_1 (struct web *);
 593
 594 #define find_web_for_subweb(w) (((w)->parent_web) \
 595                                 ? find_web_for_subweb_1 ((w)->parent_web) \
 596                                 : (w))
 597
 598 extern void ra_build_realloc (struct df *);
 599 extern void ra_build_free (void);
 600 extern void ra_build_free_all (struct df *);
 601 extern void ra_colorize_init (void);
 602 extern void ra_colorize_free_all (void);
 603 extern void ra_rewrite_init (void);
 604
 605 extern void ra_print_rtx (FILE *, rtx, int);
 606 extern void ra_print_rtx_top (FILE *, rtx, int);
 607 extern void ra_debug_rtx (rtx);
 608 extern void ra_debug_insns (rtx, int);
 609 extern void ra_debug_bbi (int);
 610 extern void ra_print_rtl_with_bb (FILE *, rtx);
 611 extern void dump_igraph (struct df *);
 612 extern void dump_igraph_machine (void);
 613 extern void dump_constraints (void);
 614 extern void dump_cost (unsigned int);
 615 extern void dump_graph_cost (unsigned int, const char *);
 616 extern void dump_ra (struct df *);
 617 extern void dump_number_seen (void);
 618 extern void dump_static_insn_cost (FILE *, const char *, const char *);
 619 extern void dump_web_conflicts (struct web *);
 620 extern void dump_web_insns (struct web*);
 621 extern int web_conflicts_p (struct web *, struct web *);
 622 extern void debug_hard_reg_set (HARD_REG_SET);
 623
 624 extern void remove_list (struct dlist *, struct dlist **);
 625 extern struct dlist * pop_list (struct dlist **);
 626 extern void record_conflict (struct web *, struct web *);
 627 extern int memref_is_stack_slot (rtx);
 628 extern void build_i_graph (struct df *);
 629 extern void put_web (struct web *, enum ra_node_type);
 630 extern void remove_web_from_list (struct web *);
 631 extern void reset_lists (void);
 632 extern struct web * alias (struct web *);
 633 extern void merge_moves (struct web *, struct web *);
 634 extern void ra_colorize_graph (struct df *);
 635
 636 extern void actual_spill (void);
 637 extern void emit_colors (struct df *);
 638 extern void delete_moves (void);
 639 extern void setup_renumber (int);
 640 extern void remove_suspicious_death_notes (void);
 641
 642 #endif /* GCC_RA_H */