diff options
Diffstat (limited to 'contrib/gcc/ra-build.c')
| -rw-r--r-- | contrib/gcc/ra-build.c | 3203 |
1 files changed, 0 insertions, 3203 deletions
diff --git a/contrib/gcc/ra-build.c b/contrib/gcc/ra-build.c deleted file mode 100644 index a305921..0000000 --- a/contrib/gcc/ra-build.c +++ /dev/null @@ -1,3203 +0,0 @@ -/* Graph coloring register allocator - Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. - Contributed by Michael Matz <matz@suse.de> - and Daniel Berlin <dan@cgsoftware.com> - - This file is part of GCC. - - GCC is free software; you can redistribute it and/or modify it under the - terms of the GNU General Public License as published by the Free Software - Foundation; either version 2, or (at your option) any later version. - - GCC is distributed in the hope that it will be useful, but WITHOUT ANY - WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS - FOR A PARTICULAR PURPOSE. See the GNU General Public License for more - details. - - You should have received a copy of the GNU General Public License along - with GCC; see the file COPYING. If not, write to the Free Software - Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tm.h" -#include "rtl.h" -#include "tm_p.h" -#include "insn-config.h" -#include "recog.h" -#include "reload.h" -#include "function.h" -#include "regs.h" -#include "hard-reg-set.h" -#include "basic-block.h" -#include "df.h" -#include "output.h" -#include "ggc.h" -#include "ra.h" - -/* 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. - - The first part (the functions called from build_web_parts_and_conflicts() - ) constructs a web_part for each pseudo register reference in the insn - stream, then goes backward from each use, until it reaches defs for that - pseudo. While going back it remember seen defs for other registers as - conflicts. By connecting the uses and defs, which reach each other, webs - (or live ranges) are built conceptually. - - 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, - a subweb of the corresponding super web is built. Finally all the - conflicts noted in the first part (as bitmaps) are transformed into real - edges. - - As part of that process the webs are also classified (their spill cost - is calculated, and if they are spillable at all, and if not, for what - reason; or if they are rematerializable), and move insns are collected, - which are potentially coalescable. - - The top-level entry of this file (build_i_graph) puts it all together, - and leaves us with a complete interference graph, which just has to - be colored. */ - - -struct curr_use; - -static unsigned HOST_WIDE_INT rtx_to_undefined (rtx); -static bitmap find_sub_conflicts (struct web_part *, unsigned int); -static bitmap get_sub_conflicts (struct web_part *, unsigned int); -static unsigned int undef_to_size_word (rtx, unsigned HOST_WIDE_INT *); -static bitmap undef_to_bitmap (struct web_part *, - unsigned HOST_WIDE_INT *); -static struct web_part * find_web_part_1 (struct web_part *); -static struct web_part * union_web_part_roots - (struct web_part *, struct web_part *); -static int defuse_overlap_p_1 (rtx, struct curr_use *); -static int live_out_1 (struct df *, struct curr_use *, rtx); -static int live_out (struct df *, struct curr_use *, rtx); -static rtx live_in_edge ( struct df *, struct curr_use *, edge); -static void live_in (struct df *, struct curr_use *, rtx); -static int copy_insn_p (rtx, rtx *, rtx *); -static void remember_move (rtx); -static void handle_asm_insn (struct df *, rtx); -static void prune_hardregs_for_mode (HARD_REG_SET *, enum machine_mode); -static void init_one_web_common (struct web *, rtx); -static void init_one_web (struct web *, rtx); -static void reinit_one_web (struct web *, rtx); -static struct web * add_subweb (struct web *, rtx); -static struct web * add_subweb_2 (struct web *, unsigned int); -static void init_web_parts (struct df *); -static void copy_conflict_list (struct web *); -static void add_conflict_edge (struct web *, struct web *); -static void build_inverse_webs (struct web *); -static void copy_web (struct web *, struct web_link **); -static void compare_and_free_webs (struct web_link **); -static void init_webs_defs_uses (void); -static unsigned int parts_to_webs_1 (struct df *, struct web_link **, - struct df_link *); -static void parts_to_webs (struct df *); -static void reset_conflicts (void); -#if 0 -static void check_conflict_numbers (void) -#endif -static void conflicts_between_webs (struct df *); -static void remember_web_was_spilled (struct web *); -static void detect_spill_temps (void); -static int contains_pseudo (rtx); -static int want_to_remat (rtx x); -static void detect_remat_webs (void); -static void determine_web_costs (void); -static void detect_webs_set_in_cond_jump (void); -static void make_webs (struct df *); -static void moves_to_webs (struct df *); -static void connect_rmw_web_parts (struct df *); -static void update_regnos_mentioned (void); -static void livethrough_conflicts_bb (basic_block); -static void init_bb_info (void); -static void free_bb_info (void); -static void build_web_parts_and_conflicts (struct df *); - - -/* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal - edge. */ -static sbitmap live_over_abnormal; - -/* To cache if we already saw a certain edge while analyzing one - use, we use a tick count incremented per use. */ -static unsigned int visited_pass; - -/* A sbitmap of UIDs of move insns, which we already analyzed. */ -static sbitmap move_handled; - -/* One such structed is allocated per insn, and traces for the currently - analyzed use, which web part belongs to it, and how many bytes of - it were still undefined when that insn was reached. */ -struct visit_trace -{ - struct web_part *wp; - unsigned HOST_WIDE_INT undefined; -}; -/* Indexed by UID. */ -static struct visit_trace *visit_trace; - -/* Per basic block we have one such structure, used to speed up - the backtracing of uses. */ -struct ra_bb_info -{ - /* The value of visited_pass, as the first insn of this BB was reached - the last time. If this equals the current visited_pass, then - undefined is valid. Otherwise not. */ - unsigned int pass; - /* The still undefined bytes at that time. The use to which this is - relative is the current use. */ - unsigned HOST_WIDE_INT undefined; - /* Bit regno is set, if that regno is mentioned in this BB as a def, or - the source of a copy insn. In these cases we can not skip the whole - block if we reach it from the end. */ - bitmap regnos_mentioned; - /* If a use reaches the end of a BB, and that BB doesn't mention its - regno, we skip the block, and remember the ID of that use - as living throughout the whole block. */ - bitmap live_throughout; - /* The content of the aux field before placing a pointer to this - structure there. */ - void *old_aux; -}; - -/* We need a fast way to describe a certain part of a register. - Therefore we put together the size and offset (in bytes) in one - integer. */ -#define BL_TO_WORD(b, l) ((((b) & 0xFFFF) << 16) | ((l) & 0xFFFF)) -#define BYTE_BEGIN(i) (((unsigned int)(i) >> 16) & 0xFFFF) -#define BYTE_LENGTH(i) ((unsigned int)(i) & 0xFFFF) - -/* For a REG or SUBREG expression X return the size/offset pair - as an integer. */ - -unsigned int -rtx_to_bits (rtx x) -{ - unsigned int len, beg; - len = GET_MODE_SIZE (GET_MODE (x)); - beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0; - return BL_TO_WORD (beg, len); -} - -/* X is a REG or SUBREG rtx. Return the bytes it touches as a bitmask. */ - -static unsigned HOST_WIDE_INT -rtx_to_undefined (rtx x) -{ - unsigned int len, beg; - unsigned HOST_WIDE_INT ret; - len = GET_MODE_SIZE (GET_MODE (x)); - beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0; - ret = ~ ((unsigned HOST_WIDE_INT) 0); - ret = (~(ret << len)) << beg; - return ret; -} - -/* We remember if we've analyzed an insn for being a move insn, and if yes - between which operands. */ -struct copy_p_cache -{ - int seen; - rtx source; - rtx target; -}; - -/* On demand cache, for if insns are copy insns, and if yes, what - source/target they have. */ -static struct copy_p_cache * copy_cache; - -int *number_seen; - -/* For INSN, return nonzero, if it's a move insn, we consider to coalesce - later, and place the operands in *SOURCE and *TARGET, if they are - not NULL. */ - -static int -copy_insn_p (rtx insn, rtx *source, rtx *target) -{ - rtx d, s; - unsigned int d_regno, s_regno; - int uid = INSN_UID (insn); - - if (!INSN_P (insn)) - abort (); - - /* First look, if we already saw this insn. */ - if (copy_cache[uid].seen) - { - /* And if we saw it, if it's actually a copy insn. */ - if (copy_cache[uid].seen == 1) - { - if (source) - *source = copy_cache[uid].source; - if (target) - *target = copy_cache[uid].target; - return 1; - } - return 0; - } - - /* Mark it as seen, but not being a copy insn. */ - copy_cache[uid].seen = 2; - insn = single_set (insn); - if (!insn) - return 0; - d = SET_DEST (insn); - s = SET_SRC (insn); - - /* We recognize moves between subreg's as copy insns. This is used to avoid - conflicts of those subwebs. But they are currently _not_ used for - coalescing (the check for this is in remember_move() below). */ - while (GET_CODE (d) == STRICT_LOW_PART) - d = XEXP (d, 0); - if (GET_CODE (d) != REG - && (GET_CODE (d) != SUBREG || GET_CODE (SUBREG_REG (d)) != REG)) - return 0; - while (GET_CODE (s) == STRICT_LOW_PART) - s = XEXP (s, 0); - if (GET_CODE (s) != REG - && (GET_CODE (s) != SUBREG || GET_CODE (SUBREG_REG (s)) != REG)) - return 0; - - s_regno = (unsigned) REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s); - d_regno = (unsigned) REGNO (GET_CODE (d) == SUBREG ? SUBREG_REG (d) : d); - - /* Copies between hardregs are useless for us, as not coalesable anyway. */ - if ((s_regno < FIRST_PSEUDO_REGISTER - && d_regno < FIRST_PSEUDO_REGISTER) - || s_regno >= max_normal_pseudo - || d_regno >= max_normal_pseudo) - return 0; - - if (source) - *source = s; - if (target) - *target = d; - - /* Still mark it as seen, but as a copy insn this time. */ - copy_cache[uid].seen = 1; - copy_cache[uid].source = s; - copy_cache[uid].target = d; - return 1; -} - -/* We build webs, as we process the conflicts. For each use we go upward - the insn stream, noting any defs as potentially conflicting with the - current use. We stop at defs of the current regno. The conflicts are only - potentially, because we may never reach a def, so this is an undefined use, - which conflicts with nothing. */ - - -/* Given a web part WP, and the location of a reg part SIZE_WORD - return the conflict bitmap for that reg part, or NULL if it doesn't - exist yet in WP. */ - -static bitmap -find_sub_conflicts (struct web_part *wp, unsigned int size_word) -{ - struct tagged_conflict *cl; - cl = wp->sub_conflicts; - for (; cl; cl = cl->next) - if (cl->size_word == size_word) - return cl->conflicts; - return NULL; -} - -/* Similar to find_sub_conflicts(), but creates that bitmap, if it - doesn't exist. I.e. this never returns NULL. */ - -static bitmap -get_sub_conflicts (struct web_part *wp, unsigned int size_word) -{ - bitmap b = find_sub_conflicts (wp, size_word); - if (!b) - { - struct tagged_conflict *cl = ra_alloc (sizeof *cl); - cl->conflicts = BITMAP_XMALLOC (); - cl->size_word = size_word; - cl->next = wp->sub_conflicts; - wp->sub_conflicts = cl; - b = cl->conflicts; - } - return b; -} - -/* Helper table for undef_to_size_word() below for small values - of UNDEFINED. Offsets and lengths are byte based. */ -static struct undef_table_s { - unsigned int new_undef; - /* size | (byte << 16) */ - unsigned int size_word; -} const undef_table [] = { - { 0, BL_TO_WORD (0, 0)}, /* 0 */ - { 0, BL_TO_WORD (0, 1)}, - { 0, BL_TO_WORD (1, 1)}, - { 0, BL_TO_WORD (0, 2)}, - { 0, BL_TO_WORD (2, 1)}, /* 4 */ - { 1, BL_TO_WORD (2, 1)}, - { 2, BL_TO_WORD (2, 1)}, - { 3, BL_TO_WORD (2, 1)}, - { 0, BL_TO_WORD (3, 1)}, /* 8 */ - { 1, BL_TO_WORD (3, 1)}, - { 2, BL_TO_WORD (3, 1)}, - { 3, BL_TO_WORD (3, 1)}, - { 0, BL_TO_WORD (2, 2)}, /* 12 */ - { 1, BL_TO_WORD (2, 2)}, - { 2, BL_TO_WORD (2, 2)}, - { 0, BL_TO_WORD (0, 4)}}; - -/* 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 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. - - For example: *UNDEFINED size+ofs new *UNDEFINED - 1111 4+0 0 - 1100 2+2 0 - 1101 2+2 1 - 0001 1+0 0 - 10101 1+4 101 - - */ - -static unsigned int -undef_to_size_word (rtx reg, unsigned HOST_WIDE_INT *undefined) -{ - /* When only the lower four bits are possibly set, we use - a fast lookup table. */ - if (*undefined <= 15) - { - struct undef_table_s u; - u = undef_table[*undefined]; - *undefined = u.new_undef; - return u.size_word; - } - - /* Otherwise we handle certain cases directly. */ - 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 0x0ff0 : *undefined = 0xf0; return BL_TO_WORD (8, 4); - case 0x0fff : - if (INTEGRAL_MODE_P (GET_MODE (reg))) - { *undefined = 0xff; return BL_TO_WORD (8, 4); } - else - { *undefined = 0; return BL_TO_WORD (0, 12); /* XFmode */ } - case 0xf000 : *undefined = 0; return BL_TO_WORD (12, 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. */ - { - 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 - as bitmap *UNDEFINED, look for (create if necessary) and return the - corresponding conflict bitmap. Change *UNDEFINED to remove the bytes - covered by the part for that bitmap. */ - -static bitmap -undef_to_bitmap (struct web_part *wp, unsigned HOST_WIDE_INT *undefined) -{ - unsigned int size_word = undef_to_size_word (DF_REF_REAL_REG (wp->ref), - undefined); - return get_sub_conflicts (wp, size_word); -} - -/* Returns the root of the web part P is a member of. Additionally - it compresses the path. P may not be NULL. */ - -static struct web_part * -find_web_part_1 (struct web_part *p) -{ - struct web_part *r = p; - struct web_part *p_next; - while (r->uplink) - r = r->uplink; - for (; p != r; p = p_next) - { - p_next = p->uplink; - p->uplink = r; - } - return r; -} - -/* Fast macro for the common case (WP either being the root itself, or - the end of an already compressed path. */ - -#define find_web_part(wp) ((! (wp)->uplink) ? (wp) \ - : (! (wp)->uplink->uplink) ? (wp)->uplink : find_web_part_1 (wp)) - -/* Unions together the parts R1 resp. R2 is a root of. - All dynamic information associated with the parts (number of spanned insns - and so on) is also merged. - The root of the resulting (possibly larger) web part is returned. */ - -static struct web_part * -union_web_part_roots (struct web_part *r1, struct web_part *r2) -{ - if (r1 != r2) - { - /* 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 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 - web part is not a def, this is an uninitialized web part. The - way we construct the I-graph ensures, that if a web is initialized, - then the first part we find (besides trivial 1 item parts) has a - def. */ - if (r1 > r2) - { - struct web_part *h = r1; - r1 = r2; - r2 = h; - } - r2->uplink = r1; - num_webs--; - - /* Now we merge the dynamic information of R1 and R2. */ - r1->spanned_deaths += r2->spanned_deaths; - - if (!r1->sub_conflicts) - r1->sub_conflicts = r2->sub_conflicts; - else if (r2->sub_conflicts) - /* We need to merge the conflict bitmaps from R2 into R1. */ - { - struct tagged_conflict *cl1, *cl2; - /* First those from R2, which are also contained in R1. - We union the bitmaps, and free those from R2, resetting them - to 0. */ - for (cl1 = r1->sub_conflicts; cl1; cl1 = cl1->next) - for (cl2 = r2->sub_conflicts; cl2; cl2 = cl2->next) - if (cl1->size_word == cl2->size_word) - { - bitmap_operation (cl1->conflicts, cl1->conflicts, - cl2->conflicts, BITMAP_IOR); - BITMAP_XFREE (cl2->conflicts); - cl2->conflicts = NULL; - } - /* Now the conflict lists from R2 which weren't in R1. - We simply copy the entries from R2 into R1' list. */ - for (cl2 = r2->sub_conflicts; cl2;) - { - struct tagged_conflict *cl_next = cl2->next; - if (cl2->conflicts) - { - cl2->next = r1->sub_conflicts; - r1->sub_conflicts = cl2; - } - cl2 = cl_next; - } - } - r2->sub_conflicts = NULL; - r1->crosses_call |= r2->crosses_call; - } - return r1; -} - -/* 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))) - -/* Remember that we've handled a given move, so we don't reprocess it. */ - -static void -remember_move (rtx insn) -{ - if (!TEST_BIT (move_handled, INSN_UID (insn))) - { - rtx s, d; - SET_BIT (move_handled, INSN_UID (insn)); - if (copy_insn_p (insn, &s, &d)) - { - /* Some sanity test for the copy insn. */ - struct df_link *slink = DF_INSN_USES (df, insn); - struct df_link *link = DF_INSN_DEFS (df, insn); - if (!link || !link->ref || !slink || !slink->ref) - abort (); - /* The following (link->next != 0) happens when a hardreg - is used in wider mode (REG:DI %eax). Then df.* creates - a def/use for each hardreg contained therein. We only - allow hardregs here. */ - if (link->next - && DF_REF_REGNO (link->next->ref) >= FIRST_PSEUDO_REGISTER) - abort (); - } - else - abort (); - /* 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 coalescing). */ - if (GET_CODE (s) == REG && GET_CODE (d) == REG) - { - struct move *m = ra_calloc (sizeof (struct move)); - struct move_list *ml; - m->insn = insn; - ml = ra_alloc (sizeof (struct move_list)); - ml->move = m; - ml->next = wl_moves; - wl_moves = ml; - } - } -} - -/* This describes the USE currently looked at in the main-loop in - build_web_parts_and_conflicts(). */ -struct curr_use { - struct web_part *wp; - /* This has a 1-bit for each byte in the USE, which is still undefined. */ - unsigned HOST_WIDE_INT undefined; - /* For easy access. */ - unsigned int regno; - rtx x; - /* If some bits of this USE are live over an abnormal edge. */ - unsigned int live_over_abnormal; -}; - -/* Returns nonzero iff rtx DEF and USE have bits in common (but see below). - 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 - 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: - 0 for no common bits, - 1 if DEF and USE exactly cover the same bytes, - 2 if the DEF only covers a part of the bits of USE - 3 if the DEF covers more than the bits of the USE, and - 4 if both are SUBREG's of different size, but have bytes in common. - -1 is a special case, for when DEF and USE refer to the same regno, but - have for other reasons no bits in common (can only happen with - subregs referring to different words, or to words which already were - defined for this USE). - Furthermore it modifies use->undefined to clear the bits which get defined - by DEF (only for cases with partial overlap). - I.e. if bit 1 is set for the result != -1, the USE was completely covered, - otherwise a test is needed to track the already defined bytes. */ - -static int -defuse_overlap_p_1 (rtx def, struct curr_use *use) -{ - int mode = 0; - if (def == use->x) - return 1; - if (!def) - return 0; - if (GET_CODE (def) == SUBREG) - { - if (REGNO (SUBREG_REG (def)) != use->regno) - return 0; - mode |= 1; - } - else if (REGNO (def) != use->regno) - return 0; - if (GET_CODE (use->x) == SUBREG) - mode |= 2; - switch (mode) - { - case 0: /* REG, REG */ - return 1; - case 1: /* SUBREG, REG */ - { - unsigned HOST_WIDE_INT old_u = use->undefined; - use->undefined &= ~ rtx_to_undefined (def); - return (old_u != use->undefined) ? 2 : -1; - } - case 2: /* REG, SUBREG */ - return 3; - case 3: /* SUBREG, SUBREG */ - if (GET_MODE_SIZE (GET_MODE (def)) == GET_MODE_SIZE (GET_MODE (use->x))) - /* If the size of both things is the same, the subreg's overlap - if they refer to the same word. */ - if (SUBREG_BYTE (def) == SUBREG_BYTE (use->x)) - return 1; - /* Now the more difficult part: the same regno is referred, 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, whereas the latter overlaps with (subreg:SI (reg:CDI a) 3). - */ - { - unsigned HOST_WIDE_INT old_u; - int b1, e1, b2, e2; - unsigned int bl1, bl2; - bl1 = rtx_to_bits (def); - bl2 = rtx_to_bits (use->x); - b1 = BYTE_BEGIN (bl1); - b2 = BYTE_BEGIN (bl2); - e1 = b1 + BYTE_LENGTH (bl1) - 1; - e2 = b2 + BYTE_LENGTH (bl2) - 1; - if (b1 > e2 || b2 > e1) - return -1; - old_u = use->undefined; - use->undefined &= ~ rtx_to_undefined (def); - return (old_u != use->undefined) ? 4 : -1; - } - default: - abort (); - } -} - -/* Macro for the common case of either def and use having the same rtx, - or based on different regnos. */ -#define defuse_overlap_p(def, use) \ - ((def) == (use)->x ? 1 : \ - (REGNO (GET_CODE (def) == SUBREG \ - ? SUBREG_REG (def) : def) != use->regno \ - ? 0 : defuse_overlap_p_1 (def, use))) - - -/* The use USE flows into INSN (backwards). Determine INSNs effect on it, - and return nonzero, if (parts of) that USE are also live before it. - This also notes conflicts between the USE and all DEFS in that insn, - and modifies the undefined bits of USE in case parts of it were set in - this insn. */ - -static int -live_out_1 (struct df *df ATTRIBUTE_UNUSED, struct curr_use *use, rtx insn) -{ - int defined = 0; - int uid = INSN_UID (insn); - struct web_part *wp = use->wp; - - /* Mark, that this insn needs this webpart live. */ - visit_trace[uid].wp = wp; - visit_trace[uid].undefined = use->undefined; - - if (INSN_P (insn)) - { - unsigned int source_regno = ~0; - unsigned int regno = use->regno; - unsigned HOST_WIDE_INT orig_undef = use->undefined; - unsigned HOST_WIDE_INT final_undef = use->undefined; - rtx s = NULL; - unsigned int n, num_defs = insn_df[uid].num_defs; - struct ref **defs = insn_df[uid].defs; - - /* We want to access the root webpart. */ - wp = find_web_part (wp); - if (GET_CODE (insn) == CALL_INSN) - wp->crosses_call = 1; - else if (copy_insn_p (insn, &s, NULL)) - source_regno = REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s); - - /* Look at all DEFS in this insn. */ - for (n = 0; n < num_defs; n++) - { - struct ref *ref = defs[n]; - int lap; - - /* Reset the undefined bits for each iteration, in case this - insn has more than one set, and one of them sets this regno. - But still the original undefined part conflicts with the other - sets. */ - use->undefined = orig_undef; - if ((lap = defuse_overlap_p (DF_REF_REG (ref), use)) != 0) - { - if (lap == -1) - /* Same regnos but non-overlapping or already defined bits, - so ignore this DEF, or better said make the yet undefined - part and this DEF conflicting. */ - { - unsigned HOST_WIDE_INT undef; - undef = use->undefined; - while (undef) - bitmap_set_bit (undef_to_bitmap (wp, &undef), - DF_REF_ID (ref)); - continue; - } - if ((lap & 1) != 0) - /* The current DEF completely covers the USE, so we can - stop traversing the code looking for further DEFs. */ - defined = 1; - else - /* We have a partial overlap. */ - { - final_undef &= use->undefined; - if (final_undef == 0) - /* Now the USE is completely defined, which means, that - we can stop looking for former DEFs. */ - defined = 1; - /* If this is a partial overlap, which left some bits - in USE undefined, we normally would need to create - conflicts between that undefined part and the part of - this DEF which overlapped with some of the formerly - undefined bits. We don't need to do this, because both - parts of this DEF (that which overlaps, and that which - doesn't) are written together in this one DEF, and can - not be colored in a way which would conflict with - the USE. This is only true for partial overlap, - because only then the DEF and USE have bits in common, - which makes the DEF move, if the USE moves, making them - aligned. - If they have no bits in common (lap == -1), they are - really independent. Therefore we there made a - conflict above. */ - } - /* This is at least a partial overlap, so we need to union - the web parts. */ - wp = union_web_parts (wp, &web_parts[DF_REF_ID (ref)]); - } - else - { - /* The DEF and the USE don't overlap at all, different - regnos. I.e. make conflicts between the undefined bits, - and that DEF. */ - unsigned HOST_WIDE_INT undef = use->undefined; - - if (regno == source_regno) - /* This triggers only, when this was a copy insn and the - source is at least a part of the USE currently looked at. - In this case only the bits of the USE conflict with the - DEF, which are not covered by the source of this copy - insn, and which are still undefined. I.e. in the best - case (the whole reg being the source), _no_ conflicts - between that USE and this DEF (the target of the move) - are created by this insn (though they might be by - others). This is a super case of the normal copy insn - only between full regs. */ - { - undef &= ~ rtx_to_undefined (s); - } - if (undef) - { - /*struct web_part *cwp; - cwp = find_web_part (&web_parts[DF_REF_ID - (ref)]);*/ - - /* TODO: somehow instead of noting the ID of the LINK - use an ID nearer to the root webpart of that LINK. - We can't use the root itself, because we later use the - ID to look at the form (reg or subreg, and if yes, - which subreg) of this conflict. This means, that we - need to remember in the root an ID for each form, and - maintaining this, when merging web parts. This makes - the bitmaps smaller. */ - do - bitmap_set_bit (undef_to_bitmap (wp, &undef), - DF_REF_ID (ref)); - while (undef); - } - } - } - if (defined) - use->undefined = 0; - else - { - /* If this insn doesn't completely define the USE, increment also - it's spanned deaths count (if this insn contains a death). */ - if (uid >= death_insns_max_uid) - abort (); - if (TEST_BIT (insns_with_deaths, uid)) - wp->spanned_deaths++; - use->undefined = final_undef; - } - } - - return !defined; -} - -/* Same as live_out_1() (actually calls it), but caches some information. - E.g. if we reached this INSN with the current regno already, and the - current undefined bits are a subset of those as we came here, we - simply connect the web parts of the USE, and the one cached for this - INSN, and additionally return zero, indicating we don't need to traverse - this path any longer (all effect were already seen, as we first reached - this insn). */ - -static inline int -live_out (struct df *df, struct curr_use *use, rtx insn) -{ - unsigned int uid = INSN_UID (insn); - if (visit_trace[uid].wp - && DF_REF_REGNO (visit_trace[uid].wp->ref) == use->regno - && (use->undefined & ~visit_trace[uid].undefined) == 0) - { - union_web_parts (visit_trace[uid].wp, use->wp); - /* Don't search any further, as we already were here with this regno. */ - return 0; - } - else - return live_out_1 (df, use, insn); -} - -/* The current USE reached a basic block head. The edge E is one - of the predecessors edges. This evaluates the effect of the predecessor - block onto the USE, and returns the next insn, which should be looked at. - This either is the last insn of that pred. block, or the first one. - The latter happens, when the pred. block has no possible effect on the - USE, except for conflicts. In that case, it's remembered, that the USE - is live over that whole block, and it's skipped. Otherwise we simply - continue with the last insn of the block. - - This also determines the effects of abnormal edges, and remembers - which uses are live at the end of that basic block. */ - -static rtx -live_in_edge (struct df *df, struct curr_use *use, edge e) -{ - struct ra_bb_info *info_pred; - rtx next_insn; - /* Call used hard regs die over an exception edge, ergo - they don't reach the predecessor block, so ignore such - uses. And also don't set the live_over_abnormal flag - for them. */ - if ((e->flags & EDGE_EH) && use->regno < FIRST_PSEUDO_REGISTER - && call_used_regs[use->regno]) - return NULL_RTX; - if (e->flags & EDGE_ABNORMAL) - use->live_over_abnormal = 1; - bitmap_set_bit (live_at_end[e->src->index], DF_REF_ID (use->wp->ref)); - info_pred = (struct ra_bb_info *) e->src->aux; - next_insn = BB_END (e->src); - - /* If the last insn of the pred. block doesn't completely define the - current use, we need to check the block. */ - if (live_out (df, use, next_insn)) - { - /* If the current regno isn't mentioned anywhere in the whole block, - and the complete use is still undefined... */ - if (!bitmap_bit_p (info_pred->regnos_mentioned, use->regno) - && (rtx_to_undefined (use->x) & ~use->undefined) == 0) - { - /* ...we can hop over the whole block and defer conflict - creation to later. */ - bitmap_set_bit (info_pred->live_throughout, - DF_REF_ID (use->wp->ref)); - next_insn = BB_HEAD (e->src); - } - return next_insn; - } - else - return NULL_RTX; -} - -/* USE flows into the end of the insns preceding INSN. Determine - their effects (in live_out()) and possibly loop over the preceding INSN, - or call itself recursively on a basic block border. When a topleve - call of this function returns the USE is completely analyzed. I.e. - its def-use chain (at least) is built, possibly connected with other - def-use chains, and all defs during that chain are noted. */ - -static void -live_in (struct df *df, struct curr_use *use, rtx insn) -{ - unsigned int loc_vpass = visited_pass; - - /* Note, that, even _if_ we are called with use->wp a root-part, this might - become non-root in the for() loop below (due to live_out() unioning - it). So beware, not to change use->wp in a way, for which only root-webs - are allowed. */ - while (1) - { - int uid = INSN_UID (insn); - basic_block bb = BLOCK_FOR_INSN (insn); - number_seen[uid]++; - - /* 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)) - ; - if (!insn) - return; - if (bb != BLOCK_FOR_INSN (insn)) - { - edge e; - unsigned HOST_WIDE_INT undef = use->undefined; - struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; - if ((e = bb->pred) == NULL) - return; - /* We now check, if we already traversed the predecessors of this - block for the current pass and the current set of undefined - bits. If yes, we don't need to check the predecessors again. - So, conceptually this information is tagged to the first - insn of a basic block. */ - if (info->pass == loc_vpass && (undef & ~info->undefined) == 0) - return; - info->pass = loc_vpass; - info->undefined = undef; - /* All but the last predecessor are handled recursively. */ - for (; e->pred_next; e = e->pred_next) - { - insn = live_in_edge (df, use, e); - if (insn) - live_in (df, use, insn); - use->undefined = undef; - } - insn = live_in_edge (df, use, e); - if (!insn) - return; - } - else if (!live_out (df, use, insn)) - return; - } -} - -/* Determine all regnos which are mentioned in a basic block, in an - interesting way. Interesting here means either in a def, or as the - source of a move insn. We only look at insns added since the last - pass. */ - -static void -update_regnos_mentioned (void) -{ - int last_uid = last_max_uid; - rtx insn; - basic_block bb; - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - if (INSN_P (insn)) - { - /* Don't look at old insns. */ - if (INSN_UID (insn) < last_uid) - { - /* XXX We should also remember moves over iterations (we already - save the cache, but not the movelist). */ - if (copy_insn_p (insn, NULL, NULL)) - remember_move (insn); - } - else if ((bb = BLOCK_FOR_INSN (insn)) != NULL) - { - rtx source; - struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; - bitmap mentioned = info->regnos_mentioned; - struct df_link *link; - if (copy_insn_p (insn, &source, NULL)) - { - remember_move (insn); - bitmap_set_bit (mentioned, - REGNO (GET_CODE (source) == SUBREG - ? SUBREG_REG (source) : source)); - } - for (link = DF_INSN_DEFS (df, insn); link; link = link->next) - if (link->ref) - bitmap_set_bit (mentioned, DF_REF_REGNO (link->ref)); - } - } -} - -/* 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. */ - -static void -livethrough_conflicts_bb (basic_block bb) -{ - struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; - rtx insn; - bitmap all_defs; - int first, use_id; - unsigned int deaths = 0; - unsigned int contains_call = 0; - - /* If there are no deferred uses, just return. */ - if ((first = bitmap_first_set_bit (info->live_throughout)) < 0) - return; - - /* First collect the IDs of all defs, count the number of death - containing insns, and if there's some call_insn here. */ - all_defs = BITMAP_XMALLOC (); - for (insn = BB_HEAD (bb); insn; insn = NEXT_INSN (insn)) - { - if (INSN_P (insn)) - { - unsigned int n; - struct ra_insn_info info; - - info = insn_df[INSN_UID (insn)]; - for (n = 0; n < info.num_defs; n++) - bitmap_set_bit (all_defs, DF_REF_ID (info.defs[n])); - if (TEST_BIT (insns_with_deaths, INSN_UID (insn))) - deaths++; - if (GET_CODE (insn) == CALL_INSN) - contains_call = 1; - } - if (insn == BB_END (bb)) - break; - } - - /* And now, if we have found anything, make all live_through - uses conflict with all defs, and update their other members. */ - if (deaths > 0 || bitmap_first_set_bit (all_defs) >= 0) - EXECUTE_IF_SET_IN_BITMAP (info->live_throughout, first, use_id, - { - struct web_part *wp = &web_parts[df->def_id + use_id]; - unsigned int bl = rtx_to_bits (DF_REF_REG (wp->ref)); - bitmap conflicts; - wp = find_web_part (wp); - wp->spanned_deaths += deaths; - wp->crosses_call |= contains_call; - conflicts = get_sub_conflicts (wp, bl); - bitmap_operation (conflicts, conflicts, all_defs, BITMAP_IOR); - }); - - BITMAP_XFREE (all_defs); -} - -/* Allocate the per basic block info for traversing the insn stream for - building live ranges. */ - -static void -init_bb_info (void) -{ - basic_block bb; - FOR_ALL_BB (bb) - { - struct ra_bb_info *info = xcalloc (1, sizeof *info); - info->regnos_mentioned = BITMAP_XMALLOC (); - info->live_throughout = BITMAP_XMALLOC (); - info->old_aux = bb->aux; - bb->aux = (void *) info; - } -} - -/* Free that per basic block info. */ - -static void -free_bb_info (void) -{ - basic_block bb; - FOR_ALL_BB (bb) - { - struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; - BITMAP_XFREE (info->regnos_mentioned); - BITMAP_XFREE (info->live_throughout); - bb->aux = info->old_aux; - free (info); - } -} - -/* Toplevel function for the first part of this file. - Connect web parts, thereby implicitly building webs, and remember - their conflicts. */ - -static void -build_web_parts_and_conflicts (struct df *df) -{ - struct df_link *link; - struct curr_use use; - basic_block bb; - - number_seen = xcalloc (get_max_uid (), sizeof (int)); - visit_trace = xcalloc (get_max_uid (), sizeof (visit_trace[0])); - update_regnos_mentioned (); - - /* Here's the main loop. - It goes through all insn's, connects web parts along the way, notes - conflicts between webparts, and remembers move instructions. */ - visited_pass = 0; - for (use.regno = 0; use.regno < (unsigned int)max_regno; use.regno++) - if (use.regno >= FIRST_PSEUDO_REGISTER || !fixed_regs[use.regno]) - for (link = df->regs[use.regno].uses; link; link = link->next) - if (link->ref) - { - struct ref *ref = link->ref; - rtx insn = DF_REF_INSN (ref); - /* Only recheck marked or new uses, or uses from hardregs. */ - if (use.regno >= FIRST_PSEUDO_REGISTER - && DF_REF_ID (ref) < last_use_id - && !TEST_BIT (last_check_uses, DF_REF_ID (ref))) - continue; - use.wp = &web_parts[df->def_id + DF_REF_ID (ref)]; - use.x = DF_REF_REG (ref); - use.live_over_abnormal = 0; - use.undefined = rtx_to_undefined (use.x); - visited_pass++; - live_in (df, &use, insn); - if (use.live_over_abnormal) - SET_BIT (live_over_abnormal, DF_REF_ID (ref)); - } - - dump_number_seen (); - FOR_ALL_BB (bb) - { - struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; - livethrough_conflicts_bb (bb); - bitmap_zero (info->live_throughout); - info->pass = 0; - } - free (visit_trace); - free (number_seen); -} - -/* Here we look per insn, for DF references being in uses _and_ defs. - This means, in the RTL a (REG xx) expression was seen as a - read/modify/write, as happens for (set (subreg:SI (reg:DI xx)) (...)) - e.g. Our code has created two webs for this, as it should. Unfortunately, - as the REG reference is only one time in the RTL we can't color - both webs different (arguably this also would be wrong for a real - read-mod-write instruction), so we must reconnect such webs. */ - -static void -connect_rmw_web_parts (struct df *df) -{ - unsigned int i; - - for (i = 0; i < df->use_id; i++) - { - struct web_part *wp1 = &web_parts[df->def_id + i]; - rtx reg; - struct df_link *link; - if (!wp1->ref) - continue; - /* If it's an uninitialized web, we don't want to connect it to others, - as the read cycle in read-mod-write had probably no effect. */ - if (find_web_part (wp1) >= &web_parts[df->def_id]) - continue; - reg = DF_REF_REAL_REG (wp1->ref); - link = DF_INSN_DEFS (df, DF_REF_INSN (wp1->ref)); - for (; link; link = link->next) - if (reg == DF_REF_REAL_REG (link->ref)) - { - struct web_part *wp2 = &web_parts[DF_REF_ID (link->ref)]; - union_web_parts (wp1, wp2); - } - } -} - -/* Deletes all hardregs from *S which are not allowed for MODE. */ - -static void -prune_hardregs_for_mode (HARD_REG_SET *s, enum machine_mode mode) -{ - AND_HARD_REG_SET (*s, hardregs_for_mode[(int) mode]); -} - -/* Initialize the members of a web, which are deducible from REG. */ - -static void -init_one_web_common (struct web *web, rtx reg) -{ - if (GET_CODE (reg) != REG) - abort (); - /* web->id isn't initialized here. */ - web->regno = REGNO (reg); - web->orig_x = reg; - if (!web->dlink) - { - web->dlink = ra_calloc (sizeof (struct dlist)); - DLIST_WEB (web->dlink) = web; - } - /* XXX - the former (superunion) doesn't constrain the graph enough. E.g. - on x86 QImode _requires_ QI_REGS, but as alternate class usually - GENERAL_REGS is given. So the graph is not constrained enough, - thinking it has more freedom then it really has, which leads - to repeated spill tryings. OTOH the latter (only using preferred - class) is too constrained, as normally (e.g. with all SImode - pseudos), they can be allocated also in the alternate class. - What we really want, are the _exact_ hard regs allowed, not - just a class. Later. */ - /*web->regclass = reg_class_superunion - [reg_preferred_class (web->regno)] - [reg_alternate_class (web->regno)];*/ - /*web->regclass = reg_preferred_class (web->regno);*/ - web->regclass = reg_class_subunion - [reg_preferred_class (web->regno)] [reg_alternate_class (web->regno)]; - web->regclass = reg_preferred_class (web->regno); - if (web->regno < FIRST_PSEUDO_REGISTER) - { - web->color = web->regno; - put_web (web, PRECOLORED); - web->num_conflicts = UINT_MAX; - web->add_hardregs = 0; - CLEAR_HARD_REG_SET (web->usable_regs); - SET_HARD_REG_BIT (web->usable_regs, web->regno); - web->num_freedom = 1; - } - else - { - HARD_REG_SET alternate; - web->color = -1; - put_web (web, INITIAL); - /* add_hardregs is wrong in multi-length classes, e.g. - using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS, - where, if it finally is allocated to GENERAL_REGS it needs two, - if allocated to FLOAT_REGS only one hardreg. XXX */ - web->add_hardregs = - CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1; - web->num_conflicts = 0 * web->add_hardregs; - COPY_HARD_REG_SET (web->usable_regs, - reg_class_contents[reg_preferred_class (web->regno)]); - COPY_HARD_REG_SET (alternate, - reg_class_contents[reg_alternate_class (web->regno)]); - IOR_HARD_REG_SET (web->usable_regs, alternate); - /*IOR_HARD_REG_SET (web->usable_regs, - reg_class_contents[reg_alternate_class - (web->regno)]);*/ - AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors); - prune_hardregs_for_mode (&web->usable_regs, - PSEUDO_REGNO_MODE (web->regno)); -#ifdef CANNOT_CHANGE_MODE_CLASS - if (web->mode_changed) - AND_COMPL_HARD_REG_SET (web->usable_regs, invalid_mode_change_regs); -#endif - web->num_freedom = hard_regs_count (web->usable_regs); - web->num_freedom -= web->add_hardregs; - if (!web->num_freedom) - abort(); - } - COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs); -} - -/* Initializes WEBs members from REG or zero them. */ - -static void -init_one_web (struct web *web, rtx reg) -{ - memset (web, 0, sizeof (struct web)); - init_one_web_common (web, reg); - web->useless_conflicts = BITMAP_XMALLOC (); -} - -/* WEB is an old web, meaning it came from the last pass, and got a - color. We want to remember some of it's info, so zero only some - members. */ - -static void -reinit_one_web (struct web *web, rtx reg) -{ - web->old_color = web->color + 1; - init_one_web_common (web, reg); - web->span_deaths = 0; - web->spill_temp = 0; - web->orig_spill_temp = 0; - web->use_my_regs = 0; - web->spill_cost = 0; - web->was_spilled = 0; - web->is_coalesced = 0; - web->artificial = 0; - web->live_over_abnormal = 0; - web->mode_changed = 0; - web->subreg_stripped = 0; - web->move_related = 0; - web->in_load = 0; - web->target_of_spilled_move = 0; - web->num_aliased = 0; - if (web->type == PRECOLORED) - { - web->num_defs = 0; - web->num_uses = 0; - web->orig_spill_cost = 0; - } - CLEAR_HARD_REG_SET (web->bias_colors); - CLEAR_HARD_REG_SET (web->prefer_colors); - web->reg_rtx = NULL; - web->stack_slot = NULL; - web->pattern = NULL; - web->alias = NULL; - if (web->moves) - abort (); - if (!web->useless_conflicts) - abort (); -} - -/* Insert and returns a subweb corresponding to REG into WEB (which - becomes its super web). It must not exist already. */ - -static struct web * -add_subweb (struct web *web, rtx reg) -{ - struct web *w; - if (GET_CODE (reg) != SUBREG) - abort (); - w = xmalloc (sizeof (struct web)); - /* Copy most content from parent-web. */ - *w = *web; - /* And initialize the private stuff. */ - w->orig_x = reg; - w->add_hardregs = CLASS_MAX_NREGS (web->regclass, GET_MODE (reg)) - 1; - w->num_conflicts = 0 * w->add_hardregs; - w->num_defs = 0; - w->num_uses = 0; - w->dlink = NULL; - w->parent_web = web; - w->subreg_next = web->subreg_next; - web->subreg_next = w; - return w; -} - -/* Similar to add_subweb(), but instead of relying on a given SUBREG, - we have just a size and an offset of the subpart of the REG rtx. - In difference to add_subweb() this marks the new subweb as artificial. */ - -static struct web * -add_subweb_2 (struct web *web, unsigned int size_word) -{ - /* To get a correct mode for the to be produced subreg, we don't want to - simply do a mode_for_size() for the mode_class of the whole web. - Suppose we deal with a CDImode web, but search for a 8 byte part. - Now mode_for_size() would only search in the class MODE_COMPLEX_INT - and would find CSImode which probably is not what we want. Instead - we want DImode, which is in a completely other class. For this to work - we instead first search the already existing subwebs, and take - _their_ modeclasses as base for a search for ourself. */ - rtx ref_rtx = (web->subreg_next ? web->subreg_next : web)->orig_x; - unsigned int size = BYTE_LENGTH (size_word) * BITS_PER_UNIT; - enum machine_mode mode; - mode = mode_for_size (size, GET_MODE_CLASS (GET_MODE (ref_rtx)), 0); - if (mode == BLKmode) - mode = mode_for_size (size, MODE_INT, 0); - if (mode == BLKmode) - abort (); - web = add_subweb (web, gen_rtx_SUBREG (mode, web->orig_x, - BYTE_BEGIN (size_word))); - web->artificial = 1; - return web; -} - -/* Initialize all the web parts we are going to need. */ - -static void -init_web_parts (struct df *df) -{ - int regno; - unsigned int no; - num_webs = 0; - for (no = 0; no < df->def_id; no++) - { - if (df->defs[no]) - { - if (no < last_def_id && web_parts[no].ref != df->defs[no]) - abort (); - web_parts[no].ref = df->defs[no]; - /* Uplink might be set from the last iteration. */ - if (!web_parts[no].uplink) - num_webs++; - } - else - /* The last iteration might have left .ref set, while df_analyse() - removed that ref (due to a removed copy insn) from the df->defs[] - array. As we don't check for that in realloc_web_parts() - we do that here. */ - web_parts[no].ref = NULL; - } - for (no = 0; no < df->use_id; no++) - { - if (df->uses[no]) - { - if (no < last_use_id - && web_parts[no + df->def_id].ref != df->uses[no]) - abort (); - web_parts[no + df->def_id].ref = df->uses[no]; - if (!web_parts[no + df->def_id].uplink) - num_webs++; - } - else - web_parts[no + df->def_id].ref = NULL; - } - - /* We want to have only one web for each precolored register. */ - for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) - { - struct web_part *r1 = NULL; - struct df_link *link; - /* Here once was a test, if there is any DEF at all, and only then to - merge all the parts. This was incorrect, we really also want to have - only one web-part for hardregs, even if there is no explicit DEF. */ - /* Link together all defs... */ - for (link = df->regs[regno].defs; link; link = link->next) - if (link->ref) - { - struct web_part *r2 = &web_parts[DF_REF_ID (link->ref)]; - if (!r1) - r1 = r2; - else - r1 = union_web_parts (r1, r2); - } - /* ... and all uses. */ - for (link = df->regs[regno].uses; link; link = link->next) - if (link->ref) - { - struct web_part *r2 = &web_parts[df->def_id - + DF_REF_ID (link->ref)]; - if (!r1) - r1 = r2; - else - r1 = union_web_parts (r1, r2); - } - } -} - -/* In case we want to remember the conflict list of a WEB, before adding - new conflicts, we copy it here to orig_conflict_list. */ - -static void -copy_conflict_list (struct web *web) -{ - struct conflict_link *cl; - if (web->orig_conflict_list || web->have_orig_conflicts) - abort (); - web->have_orig_conflicts = 1; - for (cl = web->conflict_list; cl; cl = cl->next) - { - struct conflict_link *ncl; - ncl = ra_alloc (sizeof *ncl); - ncl->t = cl->t; - ncl->sub = NULL; - ncl->next = web->orig_conflict_list; - web->orig_conflict_list = ncl; - if (cl->sub) - { - struct sub_conflict *sl, *nsl; - for (sl = cl->sub; sl; sl = sl->next) - { - nsl = ra_alloc (sizeof *nsl); - nsl->s = sl->s; - nsl->t = sl->t; - nsl->next = ncl->sub; - ncl->sub = nsl; - } - } - } -} - -/* 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 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 - happen, if SUBREG webs are involved. */ - -static void -add_conflict_edge (struct web *from, struct web *to) -{ - if (from->type != PRECOLORED) - { - struct web *pfrom = find_web_for_subweb (from); - struct web *pto = find_web_for_subweb (to); - struct sub_conflict *sl; - struct conflict_link *cl = pfrom->conflict_list; - int may_delete = 1; - - /* This can happen when subwebs of one web conflict with each - other. In live_out_1() we created such conflicts between yet - undefined webparts and defs of parts which didn't overlap with the - undefined bits. Then later they nevertheless could have merged into - one web, and then we land here. */ - if (pfrom == pto) - return; - if (remember_conflicts && !pfrom->have_orig_conflicts) - copy_conflict_list (pfrom); - if (!TEST_BIT (sup_igraph, (pfrom->id * num_webs + pto->id))) - { - cl = ra_alloc (sizeof (*cl)); - cl->t = pto; - cl->sub = NULL; - cl->next = pfrom->conflict_list; - pfrom->conflict_list = cl; - if (pto->type != SELECT && pto->type != COALESCED) - pfrom->num_conflicts += 1 + pto->add_hardregs; - SET_BIT (sup_igraph, (pfrom->id * num_webs + pto->id)); - may_delete = 0; - } - else - /* We don't need to test for cl==NULL, because at this point - a cl with cl->t==pto is guaranteed to exist. */ - while (cl->t != pto) - cl = cl->next; - if (pfrom != from || pto != to) - { - /* This is a subconflict which should be added. - If we inserted cl in this invocation, we really need to add this - subconflict. If we did _not_ add it here, we only add the - subconflict, if cl already had subconflicts, because otherwise - this indicated, that the whole webs already conflict, which - means we are not interested in this subconflict. */ - if (!may_delete || cl->sub != NULL) - { - sl = ra_alloc (sizeof (*sl)); - sl->s = from; - sl->t = to; - sl->next = cl->sub; - cl->sub = sl; - } - } - else - /* pfrom == from && pto == to means, that we are not interested - anymore in the subconflict list for this pair, because anyway - the whole webs conflict. */ - cl->sub = NULL; - } -} - -/* Record a conflict between two webs, if we haven't recorded it - already. */ - -void -record_conflict (struct web *web1, struct web *web2) -{ - unsigned int id1 = web1->id, id2 = web2->id; - unsigned int index = igraph_index (id1, id2); - /* Trivial non-conflict or already recorded conflict. */ - if (web1 == web2 || TEST_BIT (igraph, index)) - return; - if (id1 == id2) - abort (); - /* As fixed_regs are no targets for allocation, conflicts with them - are pointless. */ - if ((web1->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web1->regno]) - || (web2->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web2->regno])) - return; - /* Conflicts with hardregs, which are not even a candidate - for this pseudo are also pointless. */ - if ((web1->type == PRECOLORED - && ! TEST_HARD_REG_BIT (web2->usable_regs, web1->regno)) - || (web2->type == PRECOLORED - && ! TEST_HARD_REG_BIT (web1->usable_regs, web2->regno))) - return; - /* Similar if the set of possible hardregs don't intersect. This iteration - those conflicts are useless (and would make num_conflicts wrong, because - num_freedom is calculated from the set of possible hardregs). - But in presence of spilling and incremental building of the graph we - need to note all uses of webs conflicting with the spilled ones. - Because the set of possible hardregs can change in the next round for - spilled webs, we possibly have then conflicts with webs which would - be excluded now (because then hardregs intersect). But we actually - need to check those uses, and to get hold of them, we need to remember - also webs conflicting with this one, although not conflicting in this - round because of non-intersecting hardregs. */ - if (web1->type != PRECOLORED && web2->type != PRECOLORED - && ! hard_regs_intersect_p (&web1->usable_regs, &web2->usable_regs)) - { - struct web *p1 = find_web_for_subweb (web1); - struct web *p2 = find_web_for_subweb (web2); - /* We expect these to be rare enough to justify bitmaps. And because - we have only a special use for it, we note only the superwebs. */ - bitmap_set_bit (p1->useless_conflicts, p2->id); - bitmap_set_bit (p2->useless_conflicts, p1->id); - return; - } - SET_BIT (igraph, index); - add_conflict_edge (web1, web2); - add_conflict_edge (web2, web1); -} - -/* For each web W this produces the missing subwebs Wx, such that it's - possible to exactly specify (W-Wy) for all already existing subwebs Wy. */ - -static void -build_inverse_webs (struct web *web) -{ - struct web *sweb = web->subreg_next; - unsigned HOST_WIDE_INT undef; - - undef = rtx_to_undefined (web->orig_x); - for (; sweb; sweb = sweb->subreg_next) - /* Only create inverses of non-artificial webs. */ - if (!sweb->artificial) - { - unsigned HOST_WIDE_INT bits; - bits = undef & ~ rtx_to_undefined (sweb->orig_x); - while (bits) - { - unsigned int size_word = undef_to_size_word (web->orig_x, &bits); - if (!find_subweb_2 (web, size_word)) - add_subweb_2 (web, size_word); - } - } -} - -/* Copies the content of WEB to a new one, and link it into WL. - Used for consistency checking. */ - -static void -copy_web (struct web *web, struct web_link **wl) -{ - struct web *cweb = xmalloc (sizeof *cweb); - struct web_link *link = ra_alloc (sizeof *link); - link->next = *wl; - *wl = link; - link->web = cweb; - *cweb = *web; -} - -/* Given a list of webs LINK, compare the content of the webs therein - with the global webs of the same ID. For consistency checking. */ - -static void -compare_and_free_webs (struct web_link **link) -{ - struct web_link *wl; - for (wl = *link; wl; wl = wl->next) - { - struct web *web1 = wl->web; - struct web *web2 = ID2WEB (web1->id); - if (web1->regno != web2->regno - || 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)) - /* 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) - { - unsigned int i; - for (i = 0; i < web1->num_defs; i++) - if (web1->defs[i] != web2->defs[i]) - abort (); - for (i = 0; i < web1->num_uses; i++) - if (web1->uses[i] != web2->uses[i]) - abort (); - } - if (web1->type == PRECOLORED) - { - if (web1->defs) - free (web1->defs); - if (web1->uses) - free (web1->uses); - } - free (web1); - } - *link = NULL; -} - -/* Setup and fill uses[] and defs[] arrays of the webs. */ - -static void -init_webs_defs_uses (void) -{ - struct dlist *d; - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - unsigned int def_i, use_i; - struct df_link *link; - if (web->old_web) - continue; - if (web->type == PRECOLORED) - { - web->num_defs = web->num_uses = 0; - continue; - } - if (web->num_defs) - web->defs = xmalloc (web->num_defs * sizeof (web->defs[0])); - if (web->num_uses) - web->uses = xmalloc (web->num_uses * sizeof (web->uses[0])); - def_i = use_i = 0; - for (link = web->temp_refs; link; link = link->next) - { - if (DF_REF_REG_DEF_P (link->ref)) - web->defs[def_i++] = link->ref; - else - web->uses[use_i++] = link->ref; - } - web->temp_refs = NULL; - if (def_i != web->num_defs || use_i != web->num_uses) - abort (); - } -} - -/* Called by parts_to_webs(). This creates (or recreates) the webs (and - subwebs) from web parts, gives them IDs (only to super webs), and sets - up use2web and def2web arrays. */ - -static unsigned int -parts_to_webs_1 (struct df *df, struct web_link **copy_webs, - struct df_link *all_refs) -{ - unsigned int i; - unsigned int webnum; - unsigned int def_id = df->def_id; - unsigned int use_id = df->use_id; - struct web_part *wp_first_use = &web_parts[def_id]; - - /* For each root web part: create and initialize a new web, - setup def2web[] and use2web[] for all defs and uses, and - id2web for all new webs. */ - - webnum = 0; - for (i = 0; i < def_id + use_id; i++) - { - struct web *subweb, *web = 0; /* Initialize web to silence warnings. */ - struct web_part *wp = &web_parts[i]; - struct ref *ref = wp->ref; - unsigned int ref_id; - rtx reg; - if (!ref) - continue; - ref_id = i; - if (i >= def_id) - ref_id -= def_id; - all_refs[i].ref = ref; - reg = DF_REF_REG (ref); - if (! wp->uplink) - { - /* If we have a web part root, create a new web. */ - unsigned int newid = ~(unsigned)0; - unsigned int old_web = 0; - - /* In the first pass, there are no old webs, so unconditionally - allocate a new one. */ - if (ra_pass == 1) - { - web = xmalloc (sizeof (struct web)); - newid = last_num_webs++; - init_one_web (web, GET_CODE (reg) == SUBREG - ? SUBREG_REG (reg) : reg); - } - /* Otherwise, we look for an old web. */ - else - { - /* Remember, that use2web == def2web + def_id. - Ergo is def2web[i] == use2web[i - def_id] for i >= def_id. - So we only need to look into def2web[] array. - Try to look at the web, which formerly belonged to this - def (or use). */ - web = def2web[i]; - /* Or which belonged to this hardreg. */ - if (!web && DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER) - web = hardreg2web[DF_REF_REGNO (ref)]; - if (web) - { - /* If we found one, reuse it. */ - web = find_web_for_subweb (web); - remove_list (web->dlink, &WEBS(INITIAL)); - old_web = 1; - copy_web (web, copy_webs); - } - else - { - /* Otherwise use a new one. First from the free list. */ - if (WEBS(FREE)) - web = DLIST_WEB (pop_list (&WEBS(FREE))); - else - { - /* Else allocate a new one. */ - web = xmalloc (sizeof (struct web)); - newid = last_num_webs++; - } - } - /* The id is zeroed in init_one_web(). */ - if (newid == ~(unsigned)0) - newid = web->id; - if (old_web) - reinit_one_web (web, GET_CODE (reg) == SUBREG - ? SUBREG_REG (reg) : reg); - else - init_one_web (web, GET_CODE (reg) == SUBREG - ? SUBREG_REG (reg) : reg); - web->old_web = (old_web && web->type != PRECOLORED) ? 1 : 0; - } - web->span_deaths = wp->spanned_deaths; - web->crosses_call = wp->crosses_call; - web->id = newid; - web->temp_refs = NULL; - webnum++; - if (web->regno < FIRST_PSEUDO_REGISTER && !hardreg2web[web->regno]) - hardreg2web[web->regno] = web; - else if (web->regno < FIRST_PSEUDO_REGISTER - && hardreg2web[web->regno] != web) - abort (); - } - - /* If this reference already had a web assigned, we are done. - This test better is equivalent to the web being an old web. - Otherwise something is screwed. (This is tested) */ - if (def2web[i] != NULL) - { - web = def2web[i]; - web = find_web_for_subweb (web); - /* But if this ref includes a mode change, or was a use live - over an abnormal call, set appropriate flags in the web. */ - if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0 - && web->regno >= FIRST_PSEUDO_REGISTER) - web->mode_changed = 1; - if ((DF_REF_FLAGS (ref) & DF_REF_STRIPPED) != 0 - && web->regno >= FIRST_PSEUDO_REGISTER) - web->subreg_stripped = 1; - if (i >= def_id - && TEST_BIT (live_over_abnormal, ref_id)) - web->live_over_abnormal = 1; - /* And check, that it's not a newly allocated web. This would be - an inconsistency. */ - if (!web->old_web || web->type == PRECOLORED) - abort (); - continue; - } - /* In case this was no web part root, we need to initialize WEB - from the ref2web array belonging to the root. */ - if (wp->uplink) - { - struct web_part *rwp = find_web_part (wp); - unsigned int j = DF_REF_ID (rwp->ref); - if (rwp < wp_first_use) - web = def2web[j]; - else - web = use2web[j]; - web = find_web_for_subweb (web); - } - - /* Remember all references for a web in a single linked list. */ - all_refs[i].next = web->temp_refs; - web->temp_refs = &all_refs[i]; - - /* And the test, that if def2web[i] was NULL above, that we are _not_ - an old web. */ - if (web->old_web && web->type != PRECOLORED) - abort (); - - /* Possible create a subweb, if this ref was a subreg. */ - if (GET_CODE (reg) == SUBREG) - { - subweb = find_subweb (web, reg); - if (!subweb) - { - subweb = add_subweb (web, reg); - if (web->old_web) - abort (); - } - } - else - subweb = web; - - /* And look, if the ref involves an invalid mode change. */ - if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0 - && web->regno >= FIRST_PSEUDO_REGISTER) - web->mode_changed = 1; - if ((DF_REF_FLAGS (ref) & DF_REF_STRIPPED) != 0 - && web->regno >= FIRST_PSEUDO_REGISTER) - web->subreg_stripped = 1; - - /* Setup def2web, or use2web, and increment num_defs or num_uses. */ - if (i < def_id) - { - /* Some sanity checks. */ - if (ra_pass > 1) - { - struct web *compare = def2web[i]; - if (i < last_def_id) - { - if (web->old_web && compare != subweb) - abort (); - } - if (!web->old_web && compare) - abort (); - if (compare && compare != subweb) - abort (); - } - def2web[i] = subweb; - web->num_defs++; - } - else - { - if (ra_pass > 1) - { - struct web *compare = use2web[ref_id]; - if (ref_id < last_use_id) - { - if (web->old_web && compare != subweb) - abort (); - } - if (!web->old_web && compare) - abort (); - if (compare && compare != subweb) - abort (); - } - use2web[ref_id] = subweb; - web->num_uses++; - if (TEST_BIT (live_over_abnormal, ref_id)) - web->live_over_abnormal = 1; - } - } - - /* We better now have exactly as many webs as we had web part roots. */ - if (webnum != num_webs) - abort (); - - return webnum; -} - -/* This builds full webs out of web parts, without relating them to each - other (i.e. without creating the conflict edges). */ - -static void -parts_to_webs (struct df *df) -{ - unsigned int i; - unsigned int webnum; - struct web_link *copy_webs = NULL; - struct dlist *d; - struct df_link *all_refs; - num_subwebs = 0; - - /* First build webs and ordinary subwebs. */ - all_refs = xcalloc (df->def_id + df->use_id, sizeof (all_refs[0])); - webnum = parts_to_webs_1 (df, ©_webs, all_refs); - - /* Setup the webs for hardregs which are still missing (weren't - mentioned in the code). */ - for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (!hardreg2web[i]) - { - struct web *web = xmalloc (sizeof (struct web)); - init_one_web (web, gen_rtx_REG (reg_raw_mode[i], i)); - web->id = last_num_webs++; - hardreg2web[web->regno] = web; - } - num_webs = last_num_webs; - - /* Now create all artificial subwebs, i.e. those, which do - not correspond to a real subreg in the current function's RTL, but - which nevertheless is a target of a conflict. - XXX we need to merge this loop with the one above, which means, we need - a way to later override the artificiality. Beware: currently - add_subweb_2() relies on the existence of normal subwebs for deducing - a sane mode to use for the artificial subwebs. */ - for (i = 0; i < df->def_id + df->use_id; i++) - { - struct web_part *wp = &web_parts[i]; - struct tagged_conflict *cl; - struct web *web; - if (wp->uplink || !wp->ref) - { - if (wp->sub_conflicts) - abort (); - continue; - } - web = def2web[i]; - web = find_web_for_subweb (web); - for (cl = wp->sub_conflicts; cl; cl = cl->next) - if (!find_subweb_2 (web, cl->size_word)) - add_subweb_2 (web, cl->size_word); - } - - /* And now create artificial subwebs needed for representing the inverse - of some subwebs. This also gives IDs to all subwebs. */ - webnum = last_num_webs; - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - if (web->subreg_next) - { - struct web *sweb; - build_inverse_webs (web); - for (sweb = web->subreg_next; sweb; sweb = sweb->subreg_next) - sweb->id = webnum++; - } - } - - /* Now that everyone has an ID, we can setup the id2web array. */ - id2web = xcalloc (webnum, sizeof (id2web[0])); - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - ID2WEB (web->id) = web; - for (web = web->subreg_next; web; web = web->subreg_next) - ID2WEB (web->id) = web; - } - num_subwebs = webnum - last_num_webs; - num_allwebs = num_webs + num_subwebs; - num_webs += num_subwebs; - - /* Allocate and clear the conflict graph bitmaps. */ - igraph = sbitmap_alloc (num_webs * num_webs / 2); - sup_igraph = sbitmap_alloc (num_webs * num_webs); - sbitmap_zero (igraph); - sbitmap_zero (sup_igraph); - - /* 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. */ - compare_and_free_webs (©_webs); - free (all_refs); -} - -/* This deletes all conflicts to and from webs which need to be renewed - in this pass of the allocator, i.e. those which were spilled in the - last pass. Furthermore it also rebuilds the bitmaps for the remaining - conflicts. */ - -static void -reset_conflicts (void) -{ - unsigned int i; - bitmap newwebs = BITMAP_XMALLOC (); - for (i = 0; i < num_webs - num_subwebs; i++) - { - struct web *web = ID2WEB (i); - /* Hardreg webs and non-old webs are new webs (which - need rebuilding). */ - if (web->type == PRECOLORED || !web->old_web) - bitmap_set_bit (newwebs, web->id); - } - - for (i = 0; i < num_webs - num_subwebs; i++) - { - struct web *web = ID2WEB (i); - struct conflict_link *cl; - struct conflict_link **pcl; - pcl = &(web->conflict_list); - - /* First restore the conflict list to be like it was before - coalescing. */ - if (web->have_orig_conflicts) - { - web->conflict_list = web->orig_conflict_list; - web->orig_conflict_list = NULL; - } - if (web->orig_conflict_list) - abort (); - - /* New non-precolored webs, have no conflict list. */ - if (web->type != PRECOLORED && !web->old_web) - { - *pcl = NULL; - /* Useless conflicts will be rebuilt completely. But check - for cleanliness, as the web might have come from the - free list. */ - if (bitmap_first_set_bit (web->useless_conflicts) >= 0) - abort (); - } - else - { - /* Useless conflicts with new webs will be rebuilt if they - are still there. */ - bitmap_operation (web->useless_conflicts, web->useless_conflicts, - newwebs, BITMAP_AND_COMPL); - /* Go through all conflicts, and retain those to old webs. */ - for (cl = web->conflict_list; cl; cl = cl->next) - { - if (cl->t->old_web || cl->t->type == PRECOLORED) - { - *pcl = cl; - pcl = &(cl->next); - - /* Also restore the entries in the igraph bitmaps. */ - web->num_conflicts += 1 + cl->t->add_hardregs; - SET_BIT (sup_igraph, (web->id * num_webs + cl->t->id)); - /* No subconflicts mean full webs conflict. */ - if (!cl->sub) - SET_BIT (igraph, igraph_index (web->id, cl->t->id)); - else - /* Else only the parts in cl->sub must be in the - bitmap. */ - { - struct sub_conflict *sl; - for (sl = cl->sub; sl; sl = sl->next) - SET_BIT (igraph, igraph_index (sl->s->id, sl->t->id)); - } - } - } - *pcl = NULL; - } - web->have_orig_conflicts = 0; - } - BITMAP_XFREE (newwebs); -} - -/* For each web check it's num_conflicts member against that - number, as calculated from scratch from all neighbors. */ - -#if 0 -static void -check_conflict_numbers (void) -{ - unsigned int i; - for (i = 0; i < num_webs; i++) - { - struct web *web = ID2WEB (i); - int new_conf = 0 * web->add_hardregs; - struct conflict_link *cl; - for (cl = web->conflict_list; cl; cl = cl->next) - if (cl->t->type != SELECT && cl->t->type != COALESCED) - new_conf += 1 + cl->t->add_hardregs; - if (web->type != PRECOLORED && new_conf != web->num_conflicts) - abort (); - } -} -#endif - -/* Convert the conflicts between web parts to conflicts between full webs. - - This can't be done in parts_to_webs(), because for recording conflicts - between webs we need to know their final usable_regs set, which is used - to discard non-conflicts (between webs having no hard reg in common). - But this is set for spill temporaries only after the webs itself are - built. Until then the usable_regs set is based on the pseudo regno used - in this web, which may contain far less registers than later determined. - This would result in us loosing conflicts (due to record_conflict() - thinking that a web can only be allocated to the current usable_regs, - whereas later this is extended) leading to colorings, where some regs which - in reality conflict get the same color. */ - -static void -conflicts_between_webs (struct df *df) -{ - unsigned int i; -#ifdef STACK_REGS - struct dlist *d; -#endif - bitmap ignore_defs = BITMAP_XMALLOC (); - unsigned int have_ignored; - unsigned int *pass_cache = xcalloc (num_webs, sizeof (int)); - unsigned int pass = 0; - - if (ra_pass > 1) - reset_conflicts (); - - /* It is possible, that in the conflict bitmaps still some defs I are noted, - which have web_parts[I].ref being NULL. This can happen, when from the - last iteration the conflict bitmap for this part wasn't deleted, but a - conflicting move insn was removed. It's DEF is still in the conflict - bitmap, but it doesn't exist anymore in df->defs. To not have to check - it in the tight loop below, we instead remember the ID's of them in a - bitmap, and loop only over IDs which are not in it. */ - for (i = 0; i < df->def_id; i++) - if (web_parts[i].ref == NULL) - bitmap_set_bit (ignore_defs, i); - have_ignored = (bitmap_first_set_bit (ignore_defs) >= 0); - - /* Now record all conflicts between webs. Note that we only check - the conflict bitmaps of all defs. Conflict bitmaps are only in - webpart roots. If they are in uses, those uses are roots, which - means, that this is an uninitialized web, whose conflicts - don't matter. Nevertheless for hardregs we also need to check uses. - E.g. hardregs used for argument passing have no DEF in the RTL, - but if they have uses, they indeed conflict with all DEFs they - overlap. */ - for (i = 0; i < df->def_id + df->use_id; i++) - { - struct tagged_conflict *cl = web_parts[i].sub_conflicts; - struct web *supweb1; - if (!cl - || (i >= df->def_id - && DF_REF_REGNO (web_parts[i].ref) >= FIRST_PSEUDO_REGISTER)) - continue; - supweb1 = def2web[i]; - supweb1 = find_web_for_subweb (supweb1); - for (; cl; cl = cl->next) - if (cl->conflicts) - { - int j; - struct web *web1 = find_subweb_2 (supweb1, cl->size_word); - if (have_ignored) - bitmap_operation (cl->conflicts, cl->conflicts, ignore_defs, - BITMAP_AND_COMPL); - /* We reduce the number of calls to record_conflict() with this - pass thing. record_conflict() itself also has some early-out - optimizations, but here we can use the special properties of - the loop (constant web1) to reduce that even more. - We once used an sbitmap of already handled web indices, - but sbitmaps are slow to clear and bitmaps are slow to - set/test. The current approach needs more memory, but - locality is large. */ - pass++; - - /* Note, that there are only defs in the conflicts bitset. */ - EXECUTE_IF_SET_IN_BITMAP ( - cl->conflicts, 0, j, - { - struct web *web2 = def2web[j]; - unsigned int id2 = web2->id; - if (pass_cache[id2] != pass) - { - pass_cache[id2] = pass; - record_conflict (web1, web2); - } - }); - } - } - - free (pass_cache); - BITMAP_XFREE (ignore_defs); - -#ifdef STACK_REGS - /* Pseudos can't go in stack regs if they are live at the beginning of - a block that is reached by an abnormal edge. */ - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - int j; - if (web->live_over_abnormal) - for (j = FIRST_STACK_REG; j <= LAST_STACK_REG; j++) - record_conflict (web, hardreg2web[j]); - } -#endif -} - -/* Remember that a web was spilled, and change some characteristics - accordingly. */ - -static void -remember_web_was_spilled (struct web *web) -{ - int i; - unsigned int found_size = 0; - int adjust; - web->spill_temp = 1; - - /* From now on don't use reg_pref/alt_class (regno) anymore for - this web, but instead usable_regs. We can't use spill_temp for - this, as it might get reset later, when we are coalesced to a - non-spill-temp. In that case we still want to use usable_regs. */ - web->use_my_regs = 1; - - /* We don't constrain spill temporaries in any way for now. - It's wrong sometimes to have the same constraints or - preferences as the original pseudo, esp. if they were very narrow. - (E.g. there once was a reg wanting class AREG (only one register) - without alternative class. As long, as also the spill-temps for - this pseudo had the same constraints it was spilled over and over. - Ideally we want some constraints also on spill-temps: Because they are - not only loaded/stored, but also worked with, any constraints from insn - alternatives needs applying. Currently this is dealt with by reload, as - many other things, but at some time we want to integrate that - functionality into the allocator. */ - if (web->regno >= max_normal_pseudo) - { - COPY_HARD_REG_SET (web->usable_regs, - reg_class_contents[reg_preferred_class (web->regno)]); - IOR_HARD_REG_SET (web->usable_regs, - reg_class_contents[reg_alternate_class (web->regno)]); - } - else - COPY_HARD_REG_SET (web->usable_regs, - reg_class_contents[(int) GENERAL_REGS]); - AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors); - prune_hardregs_for_mode (&web->usable_regs, PSEUDO_REGNO_MODE (web->regno)); -#ifdef CANNOT_CHANGE_MODE_CLASS - if (web->mode_changed) - AND_COMPL_HARD_REG_SET (web->usable_regs, invalid_mode_change_regs); -#endif - web->num_freedom = hard_regs_count (web->usable_regs); - if (!web->num_freedom) - abort(); - COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs); - /* Now look for a class, which is subset of our constraints, to - setup add_hardregs, and regclass for debug output. */ - web->regclass = NO_REGS; - for (i = (int) ALL_REGS - 1; i > 0; i--) - { - unsigned int size; - HARD_REG_SET test; - COPY_HARD_REG_SET (test, reg_class_contents[i]); - AND_COMPL_HARD_REG_SET (test, never_use_colors); - GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found); - continue; - found: - /* Measure the actual number of bits which really are overlapping - the target regset, not just the reg_class_size. */ - size = hard_regs_count (test); - if (found_size < size) - { - web->regclass = (enum reg_class) i; - found_size = size; - } - } - - adjust = 0 * web->add_hardregs; - web->add_hardregs = - CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1; - web->num_freedom -= web->add_hardregs; - if (!web->num_freedom) - abort(); - adjust -= 0 * web->add_hardregs; - web->num_conflicts -= adjust; -} - -/* Look at each web, if it is used as spill web. Or better said, - if it will be spillable in this pass. */ - -static void -detect_spill_temps (void) -{ - struct dlist *d; - bitmap already = BITMAP_XMALLOC (); - - /* Detect webs used for spill temporaries. */ - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - - /* Below only the detection of spill temporaries. We never spill - precolored webs, so those can't be spill temporaries. The code above - (remember_web_was_spilled) can't currently cope with hardregs - anyway. */ - if (web->regno < FIRST_PSEUDO_REGISTER) - continue; - /* Uninitialized webs can't be spill-temporaries. */ - if (web->num_defs == 0) - continue; - - /* A web with only defs and no uses can't be spilled. Nevertheless - it must get a color, as it takes away a register from all webs - live at these defs. So we make it a short web. */ - if (web->num_uses == 0) - web->spill_temp = 3; - /* A web which was spilled last time, but for which no insns were - emitted (can happen with IR spilling ignoring sometimes - all deaths). */ - else if (web->changed) - web->spill_temp = 1; - /* A spill temporary has one def, one or more uses, all uses - are in one insn, and either the def or use insn was inserted - by the allocator. */ - /* XXX not correct currently. There might also be spill temps - involving more than one def. Usually that's an additional - clobber in the using instruction. We might also constrain - ourself to that, instead of like currently marking all - webs involving any spill insns at all. */ - else - { - unsigned int i; - int spill_involved = 0; - for (i = 0; i < web->num_uses && !spill_involved; i++) - if (DF_REF_INSN_UID (web->uses[i]) >= orig_max_uid) - spill_involved = 1; - for (i = 0; i < web->num_defs && !spill_involved; i++) - if (DF_REF_INSN_UID (web->defs[i]) >= orig_max_uid) - spill_involved = 1; - - if (spill_involved/* && ra_pass > 2*/) - { - int num_deaths = web->span_deaths; - /* Mark webs involving at least one spill insn as - spill temps. */ - remember_web_was_spilled (web); - /* Search for insns which define and use the web in question - at the same time, i.e. look for rmw insns. If these insns - are also deaths of other webs they might have been counted - as such into web->span_deaths. But because of the rmw nature - of this insn it is no point where a load/reload could be - placed successfully (it would still conflict with the - dead web), so reduce the number of spanned deaths by those - insns. Note that sometimes such deaths are _not_ counted, - so negative values can result. */ - bitmap_zero (already); - for (i = 0; i < web->num_defs; i++) - { - rtx insn = web->defs[i]->insn; - if (TEST_BIT (insns_with_deaths, INSN_UID (insn)) - && !bitmap_bit_p (already, INSN_UID (insn))) - { - unsigned int j; - bitmap_set_bit (already, INSN_UID (insn)); - /* Only decrement it once for each insn. */ - for (j = 0; j < web->num_uses; j++) - if (web->uses[j]->insn == insn) - { - num_deaths--; - break; - } - } - } - /* But mark them specially if they could possibly be spilled, - either because they cross some deaths (without the above - mentioned ones) or calls. */ - if (web->crosses_call || num_deaths > 0) - web->spill_temp = 1 * 2; - } - /* A web spanning no deaths can't be spilled either. No loads - would be created for it, ergo no defs. So the insns wouldn't - change making the graph not easier to color. Make this also - a short web. Don't do this if it crosses calls, as these are - also points of reloads. */ - else if (web->span_deaths == 0 && !web->crosses_call) - web->spill_temp = 3; - } - web->orig_spill_temp = web->spill_temp; - } - BITMAP_XFREE (already); -} - -/* Returns nonzero if the rtx MEM refers somehow to a stack location. */ - -int -memref_is_stack_slot (rtx mem) -{ - rtx ad = XEXP (mem, 0); - rtx x; - if (GET_CODE (ad) != PLUS || GET_CODE (XEXP (ad, 1)) != CONST_INT) - return 0; - x = XEXP (ad, 0); - if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx - || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]) - || x == stack_pointer_rtx) - return 1; - return 0; -} - -/* Returns nonzero, if rtx X somewhere contains any pseudo register. */ - -static int -contains_pseudo (rtx x) -{ - const char *fmt; - int i; - if (GET_CODE (x) == SUBREG) - x = SUBREG_REG (x); - if (GET_CODE (x) == REG) - { - if (REGNO (x) >= FIRST_PSEUDO_REGISTER) - return 1; - else - return 0; - } - - fmt = GET_RTX_FORMAT (GET_CODE (x)); - for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) - if (fmt[i] == 'e') - { - if (contains_pseudo (XEXP (x, i))) - return 1; - } - else if (fmt[i] == 'E') - { - int j; - for (j = 0; j < XVECLEN (x, i); j++) - if (contains_pseudo (XVECEXP (x, i, j))) - return 1; - } - return 0; -} - -/* Returns nonzero, if we are able to rematerialize something with - value X. If it's not a general operand, we test if we can produce - a valid insn which set a pseudo to that value, and that insn doesn't - clobber anything. */ - -static GTY(()) rtx remat_test_insn; -static int -want_to_remat (rtx x) -{ - int num_clobbers = 0; - int icode; - - /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ - if (general_operand (x, GET_MODE (x))) - return 1; - - /* Otherwise, check if we can make a valid insn from it. First initialize - our test insn if we haven't already. */ - if (remat_test_insn == 0) - { - remat_test_insn - = make_insn_raw (gen_rtx_SET (VOIDmode, - gen_rtx_REG (word_mode, - FIRST_PSEUDO_REGISTER * 2), - const0_rtx)); - NEXT_INSN (remat_test_insn) = PREV_INSN (remat_test_insn) = 0; - } - - /* Now make an insn like the one we would make when rematerializing - the value X and see if valid. */ - PUT_MODE (SET_DEST (PATTERN (remat_test_insn)), GET_MODE (x)); - SET_SRC (PATTERN (remat_test_insn)) = x; - /* XXX For now we don't allow any clobbers to be added, not just no - hardreg clobbers. */ - return ((icode = recog (PATTERN (remat_test_insn), remat_test_insn, - &num_clobbers)) >= 0 - && (num_clobbers == 0 - /*|| ! added_clobbers_hard_reg_p (icode)*/)); -} - -/* Look at all webs, if they perhaps are rematerializable. - They are, if all their defs are simple sets to the same value, - and that value is simple enough, and want_to_remat() holds for it. */ - -static void -detect_remat_webs (void) -{ - struct dlist *d; - for (d = WEBS(INITIAL); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - unsigned int i; - rtx pat = NULL_RTX; - /* Hardregs and useless webs aren't spilled -> no remat necessary. - Defless webs obviously also can't be rematerialized. */ - if (web->regno < FIRST_PSEUDO_REGISTER || !web->num_defs - || !web->num_uses) - continue; - for (i = 0; i < web->num_defs; i++) - { - rtx insn; - rtx set = single_set (insn = DF_REF_INSN (web->defs[i])); - rtx src; - if (!set) - break; - src = SET_SRC (set); - /* When only subregs of the web are set it isn't easily - rematerializable. */ - if (!rtx_equal_p (SET_DEST (set), web->orig_x)) - break; - /* If we already have a pattern it must be equal to the current. */ - if (pat && !rtx_equal_p (pat, src)) - break; - /* Don't do the expensive checks multiple times. */ - if (pat) - continue; - /* For now we allow only constant sources. */ - if ((CONSTANT_P (src) - /* If the whole thing is stable already, it is a source for - remat, no matter how complicated (probably all needed - resources for it are live everywhere, and don't take - additional register resources). */ - /* XXX Currently we can't use patterns which contain - pseudos, _even_ if they are stable. The code simply isn't - prepared for that. All those operands can't be spilled (or - the dependent remat webs are not remat anymore), so they - would be oldwebs in the next iteration. But currently - 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 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. */ - || (GET_CODE (src) == MEM - && INSN_UID (insn) >= orig_max_uid - && memref_is_stack_slot (src))) - /* And we must be able to construct an insn without - side-effects to actually load that value into a reg. */ - && want_to_remat (src)) - pat = src; - else - break; - } - if (pat && i == web->num_defs) - web->pattern = pat; - } -} - -/* Determine the spill costs of all webs. */ - -static void -determine_web_costs (void) -{ - struct dlist *d; - for (d = WEBS(INITIAL); d; d = d->next) - { - unsigned int i, num_loads; - int load_cost, store_cost; - unsigned HOST_WIDE_INT w; - struct web *web = DLIST_WEB (d); - if (web->type == PRECOLORED) - continue; - /* Get costs for one load/store. Note that we offset them by 1, - because some patterns have a zero rtx_cost(), but we of course - still need the actual load/store insns. With zero all those - webs would be the same, no matter how often and where - they are used. */ - if (web->pattern) - { - /* This web is rematerializable. Beware, we set store_cost to - zero optimistically assuming, that we indeed don't emit any - stores in the spill-code addition. This might be wrong if - at the point of the load not all needed resources are - available, in which case we emit a stack-based load, for - which we in turn need the according stores. */ - load_cost = 1 + rtx_cost (web->pattern, 0); - store_cost = 0; - } - else - { - load_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), - web->regclass, 1); - store_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), - web->regclass, 0); - } - /* We create only loads at deaths, whose number is in span_deaths. */ - num_loads = MIN (web->span_deaths, web->num_uses); - for (w = 0, i = 0; i < web->num_uses; i++) - w += DF_REF_BB (web->uses[i])->frequency + 1; - if (num_loads < web->num_uses) - w = (w * num_loads + web->num_uses - 1) / web->num_uses; - web->spill_cost = w * load_cost; - if (store_cost) - { - for (w = 0, i = 0; i < web->num_defs; i++) - w += DF_REF_BB (web->defs[i])->frequency + 1; - web->spill_cost += w * store_cost; - } - web->orig_spill_cost = web->spill_cost; - } -} - -/* Detect webs which are set in a conditional jump insn (possibly a - decrement-and-branch type of insn), and mark them not to be - spillable. The stores for them would need to be placed on edges, - which destroys the CFG. (Somewhen we want to deal with that XXX) */ - -static void -detect_webs_set_in_cond_jump (void) -{ - basic_block bb; - FOR_EACH_BB (bb) - if (GET_CODE (BB_END (bb)) == JUMP_INSN) - { - struct df_link *link; - for (link = DF_INSN_DEFS (df, BB_END (bb)); link; link = link->next) - if (link->ref && DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER) - { - struct web *web = def2web[DF_REF_ID (link->ref)]; - web->orig_spill_temp = web->spill_temp = 3; - } - } -} - -/* Second top-level function of this file. - Converts the connected web parts to full webs. This means, it allocates - all webs, and initializes all fields, including detecting spill - temporaries. It does not distribute moves to their corresponding webs, - though. */ - -static void -make_webs (struct df *df) -{ - /* First build all the webs itself. They are not related with - others yet. */ - parts_to_webs (df); - /* Now detect spill temporaries to initialize their usable_regs set. */ - detect_spill_temps (); - detect_webs_set_in_cond_jump (); - /* And finally relate them to each other, meaning to record all possible - conflicts between webs (see the comment there). */ - conflicts_between_webs (df); - detect_remat_webs (); - determine_web_costs (); -} - -/* Distribute moves to the corresponding webs. */ - -static void -moves_to_webs (struct df *df) -{ - struct df_link *link; - struct move_list *ml; - - /* Distribute all moves to their corresponding webs, making sure, - each move is in a web maximally one time (happens on some strange - insns). */ - for (ml = wl_moves; ml; ml = ml->next) - { - struct move *m = ml->move; - struct web *web; - struct move_list *newml; - if (!m) - continue; - m->type = WORKLIST; - m->dlink = NULL; - /* Multiple defs/uses can happen in moves involving hard-regs in - a wider mode. For those df.* creates use/def references for each - real hard-reg involved. For coalescing we are interested in - the smallest numbered hard-reg. */ - for (link = DF_INSN_DEFS (df, m->insn); link; link = link->next) - if (link->ref) - { - web = def2web[DF_REF_ID (link->ref)]; - web = find_web_for_subweb (web); - if (!m->target_web || web->regno < m->target_web->regno) - m->target_web = web; - } - for (link = DF_INSN_USES (df, m->insn); link; link = link->next) - if (link->ref) - { - web = use2web[DF_REF_ID (link->ref)]; - web = find_web_for_subweb (web); - if (!m->source_web || web->regno < m->source_web->regno) - m->source_web = web; - } - if (m->source_web && m->target_web - /* If the usable_regs don't intersect we can't coalesce the two - webs anyway, as this is no simple copy insn (it might even - need an intermediate stack temp to execute this "copy" insn). */ - && hard_regs_intersect_p (&m->source_web->usable_regs, - &m->target_web->usable_regs)) - { - if (!flag_ra_optimistic_coalescing) - { - struct move_list *test = m->source_web->moves; - for (; test && test->move != m; test = test->next); - if (! test) - { - newml = ra_alloc (sizeof (struct move_list)); - newml->move = m; - newml->next = m->source_web->moves; - m->source_web->moves = newml; - } - test = m->target_web->moves; - for (; test && test->move != m; test = test->next); - if (! test) - { - newml = ra_alloc (sizeof (struct move_list)); - newml->move = m; - newml->next = m->target_web->moves; - m->target_web->moves = newml; - } - } - } - else - /* Delete this move. */ - ml->move = NULL; - } -} - -/* Handle tricky asm insns. - Supposed to create conflicts to hardregs which aren't allowed in - the constraints. Doesn't actually do that, as it might confuse - and constrain the allocator too much. */ - -static void -handle_asm_insn (struct df *df, rtx insn) -{ - const char *constraints[MAX_RECOG_OPERANDS]; - enum machine_mode operand_mode[MAX_RECOG_OPERANDS]; - int i, noperands, in_output; - HARD_REG_SET clobbered, allowed, conflict; - rtx pat; - if (! INSN_P (insn) - || (noperands = asm_noperands (PATTERN (insn))) < 0) - return; - pat = PATTERN (insn); - CLEAR_HARD_REG_SET (clobbered); - - if (GET_CODE (pat) == PARALLEL) - for (i = 0; i < XVECLEN (pat, 0); i++) - { - rtx t = XVECEXP (pat, 0, i); - if (GET_CODE (t) == CLOBBER && GET_CODE (XEXP (t, 0)) == REG - && REGNO (XEXP (t, 0)) < FIRST_PSEUDO_REGISTER) - SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0))); - } - - decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc, - constraints, operand_mode); - in_output = 1; - for (i = 0; i < noperands; i++) - { - const char *p = constraints[i]; - int cls = (int) NO_REGS; - struct df_link *link; - rtx reg; - struct web *web; - int nothing_allowed = 1; - reg = recog_data.operand[i]; - - /* Look, if the constraints apply to a pseudo reg, and not to - e.g. a mem. */ - while (GET_CODE (reg) == SUBREG - || GET_CODE (reg) == ZERO_EXTRACT - || GET_CODE (reg) == SIGN_EXTRACT - || GET_CODE (reg) == STRICT_LOW_PART) - reg = XEXP (reg, 0); - if (GET_CODE (reg) != REG || REGNO (reg) < FIRST_PSEUDO_REGISTER) - continue; - - /* Search the web corresponding to this operand. We depend on - that decode_asm_operands() places the output operands - before the input operands. */ - while (1) - { - if (in_output) - link = df->insns[INSN_UID (insn)].defs; - else - link = df->insns[INSN_UID (insn)].uses; - while (link && link->ref && DF_REF_REAL_REG (link->ref) != reg) - link = link->next; - if (!link || !link->ref) - { - if (in_output) - in_output = 0; - else - abort (); - } - else - break; - } - if (in_output) - web = def2web[DF_REF_ID (link->ref)]; - else - web = use2web[DF_REF_ID (link->ref)]; - reg = DF_REF_REG (link->ref); - - /* Find the constraints, noting the allowed hardregs in allowed. */ - CLEAR_HARD_REG_SET (allowed); - while (1) - { - char c = *p; - - if (c == '\0' || c == ',' || c == '#') - { - /* End of one alternative - mark the regs in the current - class, and reset the class. */ - p++; - IOR_HARD_REG_SET (allowed, reg_class_contents[cls]); - if (cls != NO_REGS) - nothing_allowed = 0; - cls = NO_REGS; - if (c == '#') - do { - c = *p++; - } while (c != '\0' && c != ','); - if (c == '\0') - break; - continue; - } - - switch (c) - { - case '=': case '+': case '*': case '%': case '?': case '!': - case '0': case '1': case '2': case '3': case '4': case 'm': - case '<': case '>': case 'V': case 'o': case '&': case 'E': - case 'F': case 's': case 'i': case 'n': case 'X': case 'I': - case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': - case 'P': - break; - - case 'p': - cls = (int) reg_class_subunion[cls][(int) BASE_REG_CLASS]; - nothing_allowed = 0; - break; - - case 'g': - case 'r': - cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS]; - nothing_allowed = 0; - break; - - default: - cls = - (int) reg_class_subunion[cls][(int) - 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 explicitly - allowed, so we allow the whole class (i.e. we make no - additional conflicts). */ - CLEAR_HARD_REG_SET (conflict); - } - else - { - COPY_HARD_REG_SET (conflict, usable_regs - [reg_preferred_class (web->regno)]); - IOR_HARD_REG_SET (conflict, usable_regs - [reg_alternate_class (web->regno)]); - AND_COMPL_HARD_REG_SET (conflict, allowed); - /* We can't yet establish these conflicts. Reload must go first - (or better said, we must implement some functionality of reload). - E.g. if some operands must match, and they need the same color - we don't see yet, that they do not conflict (because they match). - For us it looks like two normal references with different DEFs, - so they conflict, and as they both need the same color, the - graph becomes uncolorable. */ -#if 0 - for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) - if (TEST_HARD_REG_BIT (conflict, c)) - record_conflict (web, hardreg2web[c]); -#endif - } - if (rtl_dump_file) - { - int c; - ra_debug_msg (DUMP_ASM, " ASM constrain Web %d conflicts with:", web->id); - for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) - if (TEST_HARD_REG_BIT (conflict, c)) - ra_debug_msg (DUMP_ASM, " %d", c); - ra_debug_msg (DUMP_ASM, "\n"); - } - } -} - -/* The real toplevel function in this file. - Build (or rebuilds) the complete interference graph with webs - and conflicts. */ - -void -build_i_graph (struct df *df) -{ - rtx insn; - - init_web_parts (df); - - sbitmap_zero (move_handled); - wl_moves = NULL; - - build_web_parts_and_conflicts (df); - - /* For read-modify-write instructions we may have created two webs. - Reconnect them here. (s.a.) */ - connect_rmw_web_parts (df); - - /* The webs are conceptually complete now, but still scattered around as - connected web parts. Collect all information and build the webs - including all conflicts between webs (instead web parts). */ - make_webs (df); - moves_to_webs (df); - - /* Look for additional constraints given by asms. */ - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - handle_asm_insn (df, insn); -} - -/* Allocates or reallocates most memory for the interference graph and - 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. */ - -void -ra_build_realloc (struct df *df) -{ - struct web_part *last_web_parts = web_parts; - struct web **last_def2web = def2web; - struct web **last_use2web = use2web; - sbitmap last_live_over_abnormal = live_over_abnormal; - unsigned int i; - struct dlist *d; - move_handled = sbitmap_alloc (get_max_uid () ); - web_parts = xcalloc (df->def_id + df->use_id, sizeof web_parts[0]); - def2web = xcalloc (df->def_id + df->use_id, sizeof def2web[0]); - use2web = &def2web[df->def_id]; - live_over_abnormal = sbitmap_alloc (df->use_id); - sbitmap_zero (live_over_abnormal); - - /* First go through all old defs and uses. */ - for (i = 0; i < last_def_id + last_use_id; i++) - { - /* And relocate them to the new array. This is made ugly by the - fact, that defs and uses are placed consecutive into one array. */ - struct web_part *dest = &web_parts[i < last_def_id - ? i : (df->def_id + i - last_def_id)]; - struct web_part *up; - *dest = last_web_parts[i]; - up = dest->uplink; - dest->uplink = NULL; - - /* Also relocate the uplink to point into the new array. */ - if (up && up->ref) - { - unsigned int id = DF_REF_ID (up->ref); - if (up < &last_web_parts[last_def_id]) - { - if (df->defs[id]) - dest->uplink = &web_parts[DF_REF_ID (up->ref)]; - } - else if (df->uses[id]) - dest->uplink = &web_parts[df->def_id + DF_REF_ID (up->ref)]; - } - } - - /* Also set up the def2web and use2web arrays, from the last pass.i - Remember also the state of live_over_abnormal. */ - for (i = 0; i < last_def_id; i++) - { - struct web *web = last_def2web[i]; - if (web) - { - web = find_web_for_subweb (web); - if (web->type != FREE && web->type != PRECOLORED) - def2web[i] = last_def2web[i]; - } - } - for (i = 0; i < last_use_id; i++) - { - struct web *web = last_use2web[i]; - if (web) - { - web = find_web_for_subweb (web); - if (web->type != FREE && web->type != PRECOLORED) - use2web[i] = last_use2web[i]; - } - if (TEST_BIT (last_live_over_abnormal, i)) - SET_BIT (live_over_abnormal, i); - } - - /* We don't have any subwebs for now. Somewhen we might want to - remember them too, instead of recreating all of them every time. - The problem is, that which subwebs we need, depends also on what - other webs and subwebs exist, and which conflicts are there. - OTOH it should be no problem, if we had some more subwebs than strictly - needed. Later. */ - for (d = WEBS(FREE); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - struct web *wnext; - for (web = web->subreg_next; web; web = wnext) - { - wnext = web->subreg_next; - free (web); - } - DLIST_WEB (d)->subreg_next = NULL; - } - - /* The uses we anyway are going to check, are not yet live over an abnormal - edge. In fact, they might actually not anymore, due to added - loads. */ - if (last_check_uses) - sbitmap_difference (live_over_abnormal, live_over_abnormal, - last_check_uses); - - if (last_def_id || last_use_id) - { - sbitmap_free (last_live_over_abnormal); - free (last_web_parts); - free (last_def2web); - } - if (!last_max_uid) - { - /* Setup copy cache, for copy_insn_p (). */ - copy_cache = xcalloc (get_max_uid (), sizeof (copy_cache[0])); - init_bb_info (); - } - else - { - copy_cache = xrealloc (copy_cache, get_max_uid () * sizeof (copy_cache[0])); - memset (©_cache[last_max_uid], 0, - (get_max_uid () - last_max_uid) * sizeof (copy_cache[0])); - } -} - -/* Free up/clear some memory, only needed for one pass. */ - -void -ra_build_free (void) -{ - struct dlist *d; - unsigned int i; - - /* Clear the moves associated with a web (we also need to look into - subwebs here). */ - for (i = 0; i < num_webs; i++) - { - struct web *web = ID2WEB (i); - if (!web) - abort (); - if (i >= num_webs - num_subwebs - && (web->conflict_list || web->orig_conflict_list)) - abort (); - web->moves = NULL; - } - /* All webs in the free list have no defs or uses anymore. */ - for (d = WEBS(FREE); d; d = d->next) - { - struct web *web = DLIST_WEB (d); - if (web->defs) - free (web->defs); - web->defs = NULL; - if (web->uses) - free (web->uses); - web->uses = NULL; - /* We can't free the subwebs here, as they are referenced from - def2web[], and possibly needed in the next ra_build_realloc(). - We free them there (or in free_all_mem()). */ - } - - /* Free all conflict bitmaps from web parts. Note that we clear - _all_ these conflicts, and don't rebuild them next time for uses - which aren't rechecked. This mean, that those conflict bitmaps - only contain the incremental information. The cumulative one - is still contained in the edges of the I-graph, i.e. in - conflict_list (or orig_conflict_list) of the webs. */ - for (i = 0; i < df->def_id + df->use_id; i++) - { - struct tagged_conflict *cl; - for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next) - { - if (cl->conflicts) - BITMAP_XFREE (cl->conflicts); - } - web_parts[i].sub_conflicts = NULL; - } - - wl_moves = NULL; - - free (id2web); - free (move_handled); - sbitmap_free (sup_igraph); - sbitmap_free (igraph); -} - -/* Free all memory for the interference graph structures. */ - -void -ra_build_free_all (struct df *df) -{ - unsigned int i; - - free_bb_info (); - free (copy_cache); - copy_cache = NULL; - for (i = 0; i < df->def_id + df->use_id; i++) - { - struct tagged_conflict *cl; - for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next) - { - if (cl->conflicts) - BITMAP_XFREE (cl->conflicts); - } - web_parts[i].sub_conflicts = NULL; - } - sbitmap_free (live_over_abnormal); - free (web_parts); - web_parts = NULL; - if (last_check_uses) - sbitmap_free (last_check_uses); - last_check_uses = NULL; - free (def2web); - use2web = NULL; - def2web = NULL; -} - -#include "gt-ra-build.h" - -/* -vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: -*/ |
