/* Graph coloring register allocator
- Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
Contributed by Michael Matz <matz@suse.de>
and Daniel Berlin <dan@cgsoftware.com>
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "ggc.h"
#include "ra.h"
-/* This file is part of the graph coloring register alloctor.
+/* This file is part of the graph coloring register allocator.
It deals with building the interference graph. When rebuilding
the graph for a function after spilling, we rebuild only those
parts needed, i.e. it works incrementally.
conflicts. By connecting the uses and defs, which reach each other, webs
(or live ranges) are built conceptually.
- The second part (make_webs() and childs) deals with converting that
+ The second part (make_webs() and children) deals with converting that
structure to the nodes and edges, on which our interference graph is
built. For each root web part constructed above, an instance of struct
web is created. For all subregs of pseudos, which matter for allocation,
/* Interpret *UNDEFINED as bitmask where each bit corresponds to a byte.
A set bit means an undefined byte. Factor all undefined bytes into
groups, and return a size/ofs pair of consecutive undefined bytes,
- but according to certain borders. Clear out those bits corrsponding
+ but according to certain borders. Clear out those bits corresponding
to bytes overlaid by that size/ofs pair. REG is only used for
the mode, to detect if it's a floating mode or not.
}
/* Otherwise we handle certain cases directly. */
- switch (*undefined)
- {
+ if (*undefined <= 0xffff)
+ switch ((int) *undefined)
+ {
case 0x00f0 : *undefined = 0; return BL_TO_WORD (4, 4);
case 0x00ff : *undefined = 0; return BL_TO_WORD (0, 8);
case 0x0f00 : *undefined = 0; return BL_TO_WORD (8, 4);
case 0xff00 : *undefined = 0; return BL_TO_WORD (8, 8);
case 0xfff0 : *undefined = 0xf0; return BL_TO_WORD (8, 8);
case 0xffff : *undefined = 0; return BL_TO_WORD (0, 16);
+ }
- /* And if nothing matched fall back to the general solution.
- For now unknown undefined bytes are converted to sequences
- of maximal length 4 bytes. We could make this larger if
- necessary. */
- default :
- {
- unsigned HOST_WIDE_INT u = *undefined;
- int word;
- struct undef_table_s tab;
- for (word = 0; (u & 15) == 0; word += 4)
- u >>= 4;
- u = u & 15;
- tab = undef_table[u];
- u = tab.new_undef;
- u = (*undefined & ~((unsigned HOST_WIDE_INT)15 << word))
- | (u << word);
- *undefined = u;
- /* Size remains the same, only the begin is moved up move bytes. */
- return tab.size_word + BL_TO_WORD (word, 0);
- }
- break;
- }
+ /* And if nothing matched fall back to the general solution. For
+ now unknown undefined bytes are converted to sequences of maximal
+ length 4 bytes. We could make this larger if necessary. */
+ {
+ unsigned HOST_WIDE_INT u = *undefined;
+ int word;
+ struct undef_table_s tab;
+ for (word = 0; (u & 15) == 0; word += 4)
+ u >>= 4;
+ u = u & 15;
+ tab = undef_table[u];
+ u = tab.new_undef;
+ u = (*undefined & ~((unsigned HOST_WIDE_INT)15 << word)) | (u << word);
+ *undefined = u;
+ /* Size remains the same, only the begin is moved up move bytes. */
+ return tab.size_word + BL_TO_WORD (word, 0);
+ }
}
/* Put the above three functions together. For a set of undefined bytes
{
/* The new root is the smaller (pointerwise) of both. This is crucial
to make the construction of webs from web parts work (so, when
- scanning all parts, we see the roots before all it's childs).
+ scanning all parts, we see the roots before all its children).
Additionally this ensures, that if the web has a def at all, than
the root is a def (because all def parts are before use parts in the
web_parts[] array), or put another way, as soon, as the root of a
return r1;
}
-/* Convenience macro, that is cabable of unioning also non-roots. */
+/* Convenience macro, that is capable of unioning also non-roots. */
#define union_web_parts(p1, p2) \
((p1 == p2) ? find_web_part (p1) \
: union_web_part_roots (find_web_part (p1), find_web_part (p2)))
/* XXX for now we don't remember move insns involving any subregs.
Those would be difficult to coalesce (we would need to implement
handling of all the subwebs in the allocator, including that such
- subwebs could be source and target of coalesing). */
+ subwebs could be source and target of coalescing). */
if (GET_CODE (s) == REG && GET_CODE (d) == REG)
{
struct move *m = (struct move *) ra_calloc (sizeof (struct move));
It is only called with DEF and USE being (reg:M a) or (subreg:M1 (reg:M2 a)
x) rtx's. Furthermore if it's a subreg rtx M1 is at least one word wide,
and a is a multi-word pseudo. If DEF or USE are hardregs, they are in
- wordmode, so we don't need to check for further hardregs which would result
+ word_mode, so we don't need to check for further hardregs which would result
from wider references. We are never called with paradoxical subregs.
This returns:
/* Now the more difficult part: the same regno is refered, but the
sizes of the references or the words differ. E.g.
(subreg:SI (reg:CDI a) 0) and (subreg:DI (reg:CDI a) 2) do not
- overlap, wereas the latter overlaps with (subreg:SI (reg:CDI a) 3).
+ overlap, whereas the latter overlaps with (subreg:SI (reg:CDI a) 3).
*/
{
unsigned HOST_WIDE_INT old_u;
basic_block bb = BLOCK_FOR_INSN (insn);
number_seen[uid]++;
- /* We want to be as fast as possible, so explicitely write
+ /* We want to be as fast as possible, so explicitly write
this loop. */
for (insn = PREV_INSN (insn); insn && !INSN_P (insn);
insn = PREV_INSN (insn))
}
}
-/* Handle the uses which reach a block end, but were defered due
+/* Handle the uses which reach a block end, but were deferred due
to it's regno not being mentioned in that block. This adds the
remaining conflicts and updates also the crosses_call and
spanned_deaths members. */
unsigned int deaths = 0;
unsigned int contains_call = 0;
- /* If there are no defered uses, just return. */
+ /* If there are no deferred uses, just return. */
if ((first = bitmap_first_set_bit (info->live_throughout)) < 0)
return;
}
/* Toplevel function for the first part of this file.
- Connect web parts, thereby implicitely building webs, and remember
+ Connect web parts, thereby implicitly building webs, and remember
their conflicts. */
static void
/* Possibly add an edge from web FROM to TO marking a conflict between
those two. This is one half of marking a complete conflict, which notes
in FROM, that TO is a conflict. Adding TO to FROM's conflicts might
- make other conflicts superflous, because the current TO overlaps some web
+ make other conflicts superfluous, because the current TO overlaps some web
already being in conflict with FROM. In this case the smaller webs are
deleted from the conflict list. Likewise if TO is overlapped by a web
already in the list, it isn't added at all. Note, that this can only
struct web *web1 = wl->web;
struct web *web2 = ID2WEB (web1->id);
if (web1->regno != web2->regno
- || web1->crosses_call != web2->crosses_call
- || web1->live_over_abnormal != web2->live_over_abnormal
|| web1->mode_changed != web2->mode_changed
|| !rtx_equal_p (web1->orig_x, web2->orig_x)
|| web1->type != web2->type
/* Only compare num_defs/num_uses with non-hardreg webs.
E.g. the number of uses of the framepointer changes due to
inserting spill code. */
- || (web1->type != PRECOLORED &&
- (web1->num_uses != web2->num_uses
- || web1->num_defs != web2->num_defs)))
+ || (web1->type != PRECOLORED
+ && (web1->num_uses != web2->num_uses
+ || web1->num_defs != web2->num_defs))
+ /* Similarly, if the framepointer was unreferenced originally
+ but we added spills, these fields may not match. */
+ || (web1->type != PRECOLORED
+ && web1->crosses_call != web2->crosses_call)
+ || (web1->type != PRECOLORED
+ && web1->live_over_abnormal != web2->live_over_abnormal))
abort ();
if (web1->type != PRECOLORED)
{
sbitmap_zero (igraph);
sbitmap_zero (sup_igraph);
- /* Distibute the references to their webs. */
+ /* Distribute the references to their webs. */
init_webs_defs_uses ();
/* And do some sanity checks if old webs, and those recreated from the
really are the same. */
{
*pcl = NULL;
/* Useless conflicts will be rebuilt completely. But check
- for cleanlyness, as the web might have come from the
+ for cleanliness, as the web might have come from the
free list. */
if (bitmap_first_set_bit (web->useless_conflicts) >= 0)
abort ();
oldwebs can't have their references changed. The
incremental machinery barfs on that. */
|| (!rtx_unstable_p (src) && !contains_pseudo (src))
- /* Additionally also memrefs to stack-slots are usefull, when
+ /* Additionally also memrefs to stack-slots are useful, when
we created them ourself. They might not have set their
unchanging flag set, but nevertheless they are stable across
the livetime in question. */
CLEAR_HARD_REG_SET (allowed);
while (1)
{
- char c = *p++;
+ char c = *p;
if (c == '\0' || c == ',' || c == '#')
{
/* End of one alternative - mark the regs in the current
- class, and reset the class.
- */
+ class, and reset the class. */
+ p++;
IOR_HARD_REG_SET (allowed, reg_class_contents[cls]);
if (cls != NO_REGS)
nothing_allowed = 0;
default:
cls =
(int) reg_class_subunion[cls][(int)
- REG_CLASS_FROM_LETTER (c)];
+ REG_CLASS_FROM_CONSTRAINT (c,
+ p)];
}
+ p += CONSTRAINT_LEN (c, p);
}
/* Now make conflicts between this web, and all hardregs, which
are not allowed by the constraints. */
if (nothing_allowed)
{
- /* If we had no real constraints nothing was explicitely
+ /* If we had no real constraints nothing was explicitly
allowed, so we allow the whole class (i.e. we make no
additional conflicts). */
CLEAR_HARD_REG_SET (conflict);
}
/* Allocates or reallocates most memory for the interference graph and
- assiciated structures. If it reallocates memory (meaning, this is not
+ associated structures. If it reallocates memory (meaning, this is not
the first pass), this also changes some structures to reflect the
additional entries in various array, and the higher number of
defs and uses. */
OSDN Git Service
