| /* 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]; |