]>
Commit | Line | Data |
---|---|---|
ed8d2920 | 1 | /* Graph coloring register allocator |
88462c42 | 2 | Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
ed8d2920 MM |
3 | Contributed by Michael Matz <matz@suse.de> |
4 | and Daniel Berlin <dan@cgsoftware.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under the | |
9 | terms of the GNU General Public License as published by the Free Software | |
10 | Foundation; either version 2, or (at your option) any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS | |
14 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more | |
15 | details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License along | |
18 | with GCC; see the file COPYING. If not, write to the Free Software | |
19 | Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
ed8d2920 MM |
25 | #include "rtl.h" |
26 | #include "tm_p.h" | |
27 | #include "insn-config.h" | |
28 | #include "recog.h" | |
54b2a7f8 | 29 | #include "reload.h" |
ed8d2920 MM |
30 | #include "function.h" |
31 | #include "regs.h" | |
32 | #include "hard-reg-set.h" | |
33 | #include "basic-block.h" | |
34 | #include "df.h" | |
35 | #include "output.h" | |
36 | #include "ggc.h" | |
37 | #include "ra.h" | |
38 | ||
d55d8fc7 | 39 | /* This file is part of the graph coloring register allocator. |
ed8d2920 MM |
40 | It deals with building the interference graph. When rebuilding |
41 | the graph for a function after spilling, we rebuild only those | |
42 | parts needed, i.e. it works incrementally. | |
43 | ||
44 | The first part (the functions called from build_web_parts_and_conflicts() | |
45 | ) constructs a web_part for each pseudo register reference in the insn | |
46 | stream, then goes backward from each use, until it reaches defs for that | |
47 | pseudo. While going back it remember seen defs for other registers as | |
48 | conflicts. By connecting the uses and defs, which reach each other, webs | |
49 | (or live ranges) are built conceptually. | |
50 | ||
d55d8fc7 | 51 | The second part (make_webs() and children) deals with converting that |
ed8d2920 MM |
52 | structure to the nodes and edges, on which our interference graph is |
53 | built. For each root web part constructed above, an instance of struct | |
54 | web is created. For all subregs of pseudos, which matter for allocation, | |
55 | a subweb of the corresponding super web is built. Finally all the | |
56 | conflicts noted in the first part (as bitmaps) are transformed into real | |
57 | edges. | |
58 | ||
59 | As part of that process the webs are also classified (their spill cost | |
60 | is calculated, and if they are spillable at all, and if not, for what | |
61 | reason; or if they are rematerializable), and move insns are collected, | |
62 | which are potentially coalescable. | |
63 | ||
64 | The top-level entry of this file (build_i_graph) puts it all together, | |
65 | and leaves us with a complete interference graph, which just has to | |
66 | be colored. */ | |
67 | ||
68 | ||
69 | struct curr_use; | |
70 | ||
93bad80e SB |
71 | static unsigned HOST_WIDE_INT rtx_to_undefined (rtx); |
72 | static bitmap find_sub_conflicts (struct web_part *, unsigned int); | |
73 | static bitmap get_sub_conflicts (struct web_part *, unsigned int); | |
74 | static unsigned int undef_to_size_word (rtx, unsigned HOST_WIDE_INT *); | |
75 | static bitmap undef_to_bitmap (struct web_part *, | |
76 | unsigned HOST_WIDE_INT *); | |
77 | static struct web_part * find_web_part_1 (struct web_part *); | |
ed8d2920 | 78 | static struct web_part * union_web_part_roots |
93bad80e SB |
79 | (struct web_part *, struct web_part *); |
80 | static int defuse_overlap_p_1 (rtx, struct curr_use *); | |
81 | static int live_out_1 (struct df *, struct curr_use *, rtx); | |
82 | static int live_out (struct df *, struct curr_use *, rtx); | |
83 | static rtx live_in_edge ( struct df *, struct curr_use *, edge); | |
84 | static void live_in (struct df *, struct curr_use *, rtx); | |
85 | static int copy_insn_p (rtx, rtx *, rtx *); | |
86 | static void remember_move (rtx); | |
87 | static void handle_asm_insn (struct df *, rtx); | |
88 | static void prune_hardregs_for_mode (HARD_REG_SET *, enum machine_mode); | |
89 | static void init_one_web_common (struct web *, rtx); | |
90 | static void init_one_web (struct web *, rtx); | |
91 | static void reinit_one_web (struct web *, rtx); | |
92 | static struct web * add_subweb (struct web *, rtx); | |
93 | static struct web * add_subweb_2 (struct web *, unsigned int); | |
94 | static void init_web_parts (struct df *); | |
95 | static void copy_conflict_list (struct web *); | |
96 | static void add_conflict_edge (struct web *, struct web *); | |
97 | static void build_inverse_webs (struct web *); | |
98 | static void copy_web (struct web *, struct web_link **); | |
99 | static void compare_and_free_webs (struct web_link **); | |
100 | static void init_webs_defs_uses (void); | |
101 | static unsigned int parts_to_webs_1 (struct df *, struct web_link **, | |
102 | struct df_link *); | |
103 | static void parts_to_webs (struct df *); | |
104 | static void reset_conflicts (void); | |
533c4863 | 105 | #if 0 |
93bad80e | 106 | static void check_conflict_numbers (void) |
533c4863 | 107 | #endif |
93bad80e SB |
108 | static void conflicts_between_webs (struct df *); |
109 | static void remember_web_was_spilled (struct web *); | |
110 | static void detect_spill_temps (void); | |
111 | static int contains_pseudo (rtx); | |
112 | static int want_to_remat (rtx x); | |
113 | static void detect_remat_webs (void); | |
114 | static void determine_web_costs (void); | |
115 | static void detect_webs_set_in_cond_jump (void); | |
116 | static void make_webs (struct df *); | |
117 | static void moves_to_webs (struct df *); | |
118 | static void connect_rmw_web_parts (struct df *); | |
119 | static void update_regnos_mentioned (void); | |
120 | static void livethrough_conflicts_bb (basic_block); | |
121 | static void init_bb_info (void); | |
122 | static void free_bb_info (void); | |
123 | static void build_web_parts_and_conflicts (struct df *); | |
ed8d2920 MM |
124 | |
125 | ||
126 | /* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal | |
127 | edge. */ | |
128 | static sbitmap live_over_abnormal; | |
129 | ||
130 | /* To cache if we already saw a certain edge while analyzing one | |
131 | use, we use a tick count incremented per use. */ | |
132 | static unsigned int visited_pass; | |
133 | ||
134 | /* A sbitmap of UIDs of move insns, which we already analyzed. */ | |
135 | static sbitmap move_handled; | |
136 | ||
137 | /* One such structed is allocated per insn, and traces for the currently | |
138 | analyzed use, which web part belongs to it, and how many bytes of | |
139 | it were still undefined when that insn was reached. */ | |
140 | struct visit_trace | |
141 | { | |
142 | struct web_part *wp; | |
143 | unsigned HOST_WIDE_INT undefined; | |
144 | }; | |
145 | /* Indexed by UID. */ | |
146 | static struct visit_trace *visit_trace; | |
147 | ||
148 | /* Per basic block we have one such structure, used to speed up | |
149 | the backtracing of uses. */ | |
150 | struct ra_bb_info | |
151 | { | |
152 | /* The value of visited_pass, as the first insn of this BB was reached | |
153 | the last time. If this equals the current visited_pass, then | |
154 | undefined is valid. Otherwise not. */ | |
155 | unsigned int pass; | |
156 | /* The still undefined bytes at that time. The use to which this is | |
157 | relative is the current use. */ | |
158 | unsigned HOST_WIDE_INT undefined; | |
159 | /* Bit regno is set, if that regno is mentioned in this BB as a def, or | |
160 | the source of a copy insn. In these cases we can not skip the whole | |
161 | block if we reach it from the end. */ | |
162 | bitmap regnos_mentioned; | |
163 | /* If a use reaches the end of a BB, and that BB doesn't mention its | |
164 | regno, we skip the block, and remember the ID of that use | |
165 | as living throughout the whole block. */ | |
166 | bitmap live_throughout; | |
167 | /* The content of the aux field before placing a pointer to this | |
168 | structure there. */ | |
169 | void *old_aux; | |
170 | }; | |
171 | ||
172 | /* We need a fast way to describe a certain part of a register. | |
173 | Therefore we put together the size and offset (in bytes) in one | |
174 | integer. */ | |
175 | #define BL_TO_WORD(b, l) ((((b) & 0xFFFF) << 16) | ((l) & 0xFFFF)) | |
176 | #define BYTE_BEGIN(i) (((unsigned int)(i) >> 16) & 0xFFFF) | |
177 | #define BYTE_LENGTH(i) ((unsigned int)(i) & 0xFFFF) | |
178 | ||
179 | /* For a REG or SUBREG expression X return the size/offset pair | |
180 | as an integer. */ | |
181 | ||
182 | unsigned int | |
93bad80e | 183 | rtx_to_bits (rtx x) |
ed8d2920 MM |
184 | { |
185 | unsigned int len, beg; | |
186 | len = GET_MODE_SIZE (GET_MODE (x)); | |
187 | beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0; | |
188 | return BL_TO_WORD (beg, len); | |
189 | } | |
190 | ||
191 | /* X is a REG or SUBREG rtx. Return the bytes it touches as a bitmask. */ | |
192 | ||
193 | static unsigned HOST_WIDE_INT | |
93bad80e | 194 | rtx_to_undefined (rtx x) |
ed8d2920 MM |
195 | { |
196 | unsigned int len, beg; | |
197 | unsigned HOST_WIDE_INT ret; | |
198 | len = GET_MODE_SIZE (GET_MODE (x)); | |
199 | beg = (GET_CODE (x) == SUBREG) ? SUBREG_BYTE (x) : 0; | |
200 | ret = ~ ((unsigned HOST_WIDE_INT) 0); | |
201 | ret = (~(ret << len)) << beg; | |
202 | return ret; | |
203 | } | |
204 | ||
205 | /* We remember if we've analyzed an insn for being a move insn, and if yes | |
206 | between which operands. */ | |
207 | struct copy_p_cache | |
208 | { | |
209 | int seen; | |
210 | rtx source; | |
211 | rtx target; | |
212 | }; | |
213 | ||
214 | /* On demand cache, for if insns are copy insns, and if yes, what | |
215 | source/target they have. */ | |
216 | static struct copy_p_cache * copy_cache; | |
217 | ||
218 | int *number_seen; | |
219 | ||
220 | /* For INSN, return nonzero, if it's a move insn, we consider to coalesce | |
221 | later, and place the operands in *SOURCE and *TARGET, if they are | |
222 | not NULL. */ | |
223 | ||
224 | static int | |
93bad80e | 225 | copy_insn_p (rtx insn, rtx *source, rtx *target) |
ed8d2920 MM |
226 | { |
227 | rtx d, s; | |
228 | unsigned int d_regno, s_regno; | |
229 | int uid = INSN_UID (insn); | |
230 | ||
231 | if (!INSN_P (insn)) | |
232 | abort (); | |
233 | ||
234 | /* First look, if we already saw this insn. */ | |
235 | if (copy_cache[uid].seen) | |
236 | { | |
237 | /* And if we saw it, if it's actually a copy insn. */ | |
238 | if (copy_cache[uid].seen == 1) | |
239 | { | |
240 | if (source) | |
241 | *source = copy_cache[uid].source; | |
242 | if (target) | |
243 | *target = copy_cache[uid].target; | |
244 | return 1; | |
245 | } | |
246 | return 0; | |
247 | } | |
248 | ||
249 | /* Mark it as seen, but not being a copy insn. */ | |
250 | copy_cache[uid].seen = 2; | |
251 | insn = single_set (insn); | |
252 | if (!insn) | |
253 | return 0; | |
254 | d = SET_DEST (insn); | |
255 | s = SET_SRC (insn); | |
256 | ||
257 | /* We recognize moves between subreg's as copy insns. This is used to avoid | |
258 | conflicts of those subwebs. But they are currently _not_ used for | |
259 | coalescing (the check for this is in remember_move() below). */ | |
260 | while (GET_CODE (d) == STRICT_LOW_PART) | |
261 | d = XEXP (d, 0); | |
262 | if (GET_CODE (d) != REG | |
263 | && (GET_CODE (d) != SUBREG || GET_CODE (SUBREG_REG (d)) != REG)) | |
264 | return 0; | |
265 | while (GET_CODE (s) == STRICT_LOW_PART) | |
266 | s = XEXP (s, 0); | |
267 | if (GET_CODE (s) != REG | |
268 | && (GET_CODE (s) != SUBREG || GET_CODE (SUBREG_REG (s)) != REG)) | |
269 | return 0; | |
270 | ||
271 | s_regno = (unsigned) REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s); | |
272 | d_regno = (unsigned) REGNO (GET_CODE (d) == SUBREG ? SUBREG_REG (d) : d); | |
273 | ||
4b7e68e7 | 274 | /* Copies between hardregs are useless for us, as not coalesable anyway. */ |
ed8d2920 MM |
275 | if ((s_regno < FIRST_PSEUDO_REGISTER |
276 | && d_regno < FIRST_PSEUDO_REGISTER) | |
277 | || s_regno >= max_normal_pseudo | |
278 | || d_regno >= max_normal_pseudo) | |
279 | return 0; | |
280 | ||
281 | if (source) | |
282 | *source = s; | |
283 | if (target) | |
284 | *target = d; | |
285 | ||
286 | /* Still mark it as seen, but as a copy insn this time. */ | |
287 | copy_cache[uid].seen = 1; | |
288 | copy_cache[uid].source = s; | |
289 | copy_cache[uid].target = d; | |
290 | return 1; | |
291 | } | |
292 | ||
293 | /* We build webs, as we process the conflicts. For each use we go upward | |
294 | the insn stream, noting any defs as potentially conflicting with the | |
295 | current use. We stop at defs of the current regno. The conflicts are only | |
296 | potentially, because we may never reach a def, so this is an undefined use, | |
297 | which conflicts with nothing. */ | |
298 | ||
299 | ||
300 | /* Given a web part WP, and the location of a reg part SIZE_WORD | |
301 | return the conflict bitmap for that reg part, or NULL if it doesn't | |
302 | exist yet in WP. */ | |
303 | ||
304 | static bitmap | |
93bad80e | 305 | find_sub_conflicts (struct web_part *wp, unsigned int size_word) |
ed8d2920 MM |
306 | { |
307 | struct tagged_conflict *cl; | |
308 | cl = wp->sub_conflicts; | |
309 | for (; cl; cl = cl->next) | |
310 | if (cl->size_word == size_word) | |
311 | return cl->conflicts; | |
312 | return NULL; | |
313 | } | |
314 | ||
315 | /* Similar to find_sub_conflicts(), but creates that bitmap, if it | |
316 | doesn't exist. I.e. this never returns NULL. */ | |
317 | ||
318 | static bitmap | |
93bad80e | 319 | get_sub_conflicts (struct web_part *wp, unsigned int size_word) |
ed8d2920 MM |
320 | { |
321 | bitmap b = find_sub_conflicts (wp, size_word); | |
322 | if (!b) | |
323 | { | |
703ad42b | 324 | struct tagged_conflict *cl = ra_alloc (sizeof *cl); |
ed8d2920 MM |
325 | cl->conflicts = BITMAP_XMALLOC (); |
326 | cl->size_word = size_word; | |
327 | cl->next = wp->sub_conflicts; | |
328 | wp->sub_conflicts = cl; | |
329 | b = cl->conflicts; | |
330 | } | |
331 | return b; | |
332 | } | |
333 | ||
334 | /* Helper table for undef_to_size_word() below for small values | |
335 | of UNDEFINED. Offsets and lengths are byte based. */ | |
336 | static struct undef_table_s { | |
337 | unsigned int new_undef; | |
338 | /* size | (byte << 16) */ | |
339 | unsigned int size_word; | |
d3969c34 | 340 | } const undef_table [] = { |
ed8d2920 MM |
341 | { 0, BL_TO_WORD (0, 0)}, /* 0 */ |
342 | { 0, BL_TO_WORD (0, 1)}, | |
343 | { 0, BL_TO_WORD (1, 1)}, | |
344 | { 0, BL_TO_WORD (0, 2)}, | |
345 | { 0, BL_TO_WORD (2, 1)}, /* 4 */ | |
346 | { 1, BL_TO_WORD (2, 1)}, | |
347 | { 2, BL_TO_WORD (2, 1)}, | |
348 | { 3, BL_TO_WORD (2, 1)}, | |
349 | { 0, BL_TO_WORD (3, 1)}, /* 8 */ | |
350 | { 1, BL_TO_WORD (3, 1)}, | |
351 | { 2, BL_TO_WORD (3, 1)}, | |
352 | { 3, BL_TO_WORD (3, 1)}, | |
353 | { 0, BL_TO_WORD (2, 2)}, /* 12 */ | |
354 | { 1, BL_TO_WORD (2, 2)}, | |
355 | { 2, BL_TO_WORD (2, 2)}, | |
356 | { 0, BL_TO_WORD (0, 4)}}; | |
357 | ||
358 | /* Interpret *UNDEFINED as bitmask where each bit corresponds to a byte. | |
359 | A set bit means an undefined byte. Factor all undefined bytes into | |
360 | groups, and return a size/ofs pair of consecutive undefined bytes, | |
d55d8fc7 | 361 | but according to certain borders. Clear out those bits corresponding |
ed8d2920 MM |
362 | to bytes overlaid by that size/ofs pair. REG is only used for |
363 | the mode, to detect if it's a floating mode or not. | |
364 | ||
365 | For example: *UNDEFINED size+ofs new *UNDEFINED | |
366 | 1111 4+0 0 | |
367 | 1100 2+2 0 | |
368 | 1101 2+2 1 | |
369 | 0001 1+0 0 | |
370 | 10101 1+4 101 | |
371 | ||
372 | */ | |
373 | ||
374 | static unsigned int | |
93bad80e | 375 | undef_to_size_word (rtx reg, unsigned HOST_WIDE_INT *undefined) |
ed8d2920 MM |
376 | { |
377 | /* When only the lower four bits are possibly set, we use | |
378 | a fast lookup table. */ | |
379 | if (*undefined <= 15) | |
380 | { | |
381 | struct undef_table_s u; | |
382 | u = undef_table[*undefined]; | |
383 | *undefined = u.new_undef; | |
384 | return u.size_word; | |
385 | } | |
386 | ||
387 | /* Otherwise we handle certain cases directly. */ | |
25e42e9d KG |
388 | if (*undefined <= 0xffff) |
389 | switch ((int) *undefined) | |
390 | { | |
ed8d2920 MM |
391 | case 0x00f0 : *undefined = 0; return BL_TO_WORD (4, 4); |
392 | case 0x00ff : *undefined = 0; return BL_TO_WORD (0, 8); | |
393 | case 0x0f00 : *undefined = 0; return BL_TO_WORD (8, 4); | |
394 | case 0x0ff0 : *undefined = 0xf0; return BL_TO_WORD (8, 4); | |
395 | case 0x0fff : | |
396 | if (INTEGRAL_MODE_P (GET_MODE (reg))) | |
397 | { *undefined = 0xff; return BL_TO_WORD (8, 4); } | |
398 | else | |
399 | { *undefined = 0; return BL_TO_WORD (0, 12); /* XFmode */ } | |
400 | case 0xf000 : *undefined = 0; return BL_TO_WORD (12, 4); | |
401 | case 0xff00 : *undefined = 0; return BL_TO_WORD (8, 8); | |
402 | case 0xfff0 : *undefined = 0xf0; return BL_TO_WORD (8, 8); | |
403 | case 0xffff : *undefined = 0; return BL_TO_WORD (0, 16); | |
25e42e9d KG |
404 | } |
405 | ||
406 | /* And if nothing matched fall back to the general solution. For | |
407 | now unknown undefined bytes are converted to sequences of maximal | |
408 | length 4 bytes. We could make this larger if necessary. */ | |
409 | { | |
410 | unsigned HOST_WIDE_INT u = *undefined; | |
411 | int word; | |
412 | struct undef_table_s tab; | |
413 | for (word = 0; (u & 15) == 0; word += 4) | |
414 | u >>= 4; | |
415 | u = u & 15; | |
416 | tab = undef_table[u]; | |
417 | u = tab.new_undef; | |
418 | u = (*undefined & ~((unsigned HOST_WIDE_INT)15 << word)) | (u << word); | |
419 | *undefined = u; | |
420 | /* Size remains the same, only the begin is moved up move bytes. */ | |
421 | return tab.size_word + BL_TO_WORD (word, 0); | |
422 | } | |
ed8d2920 MM |
423 | } |
424 | ||
425 | /* Put the above three functions together. For a set of undefined bytes | |
426 | as bitmap *UNDEFINED, look for (create if necessary) and return the | |
427 | corresponding conflict bitmap. Change *UNDEFINED to remove the bytes | |
428 | covered by the part for that bitmap. */ | |
429 | ||
430 | static bitmap | |
93bad80e | 431 | undef_to_bitmap (struct web_part *wp, unsigned HOST_WIDE_INT *undefined) |
ed8d2920 MM |
432 | { |
433 | unsigned int size_word = undef_to_size_word (DF_REF_REAL_REG (wp->ref), | |
434 | undefined); | |
435 | return get_sub_conflicts (wp, size_word); | |
436 | } | |
437 | ||
438 | /* Returns the root of the web part P is a member of. Additionally | |
439 | it compresses the path. P may not be NULL. */ | |
440 | ||
441 | static struct web_part * | |
93bad80e | 442 | find_web_part_1 (struct web_part *p) |
ed8d2920 MM |
443 | { |
444 | struct web_part *r = p; | |
445 | struct web_part *p_next; | |
446 | while (r->uplink) | |
447 | r = r->uplink; | |
448 | for (; p != r; p = p_next) | |
449 | { | |
450 | p_next = p->uplink; | |
451 | p->uplink = r; | |
452 | } | |
453 | return r; | |
454 | } | |
455 | ||
456 | /* Fast macro for the common case (WP either being the root itself, or | |
457 | the end of an already compressed path. */ | |
458 | ||
459 | #define find_web_part(wp) ((! (wp)->uplink) ? (wp) \ | |
460 | : (! (wp)->uplink->uplink) ? (wp)->uplink : find_web_part_1 (wp)) | |
461 | ||
462 | /* Unions together the parts R1 resp. R2 is a root of. | |
463 | All dynamic information associated with the parts (number of spanned insns | |
464 | and so on) is also merged. | |
465 | The root of the resulting (possibly larger) web part is returned. */ | |
466 | ||
467 | static struct web_part * | |
93bad80e | 468 | union_web_part_roots (struct web_part *r1, struct web_part *r2) |
ed8d2920 MM |
469 | { |
470 | if (r1 != r2) | |
471 | { | |
472 | /* The new root is the smaller (pointerwise) of both. This is crucial | |
473 | to make the construction of webs from web parts work (so, when | |
d55d8fc7 | 474 | scanning all parts, we see the roots before all its children). |
ed8d2920 MM |
475 | Additionally this ensures, that if the web has a def at all, than |
476 | the root is a def (because all def parts are before use parts in the | |
477 | web_parts[] array), or put another way, as soon, as the root of a | |
478 | web part is not a def, this is an uninitialized web part. The | |
479 | way we construct the I-graph ensures, that if a web is initialized, | |
480 | then the first part we find (besides trivial 1 item parts) has a | |
481 | def. */ | |
482 | if (r1 > r2) | |
483 | { | |
484 | struct web_part *h = r1; | |
485 | r1 = r2; | |
486 | r2 = h; | |
487 | } | |
488 | r2->uplink = r1; | |
489 | num_webs--; | |
490 | ||
491 | /* Now we merge the dynamic information of R1 and R2. */ | |
492 | r1->spanned_deaths += r2->spanned_deaths; | |
493 | ||
494 | if (!r1->sub_conflicts) | |
495 | r1->sub_conflicts = r2->sub_conflicts; | |
496 | else if (r2->sub_conflicts) | |
497 | /* We need to merge the conflict bitmaps from R2 into R1. */ | |
498 | { | |
499 | struct tagged_conflict *cl1, *cl2; | |
500 | /* First those from R2, which are also contained in R1. | |
501 | We union the bitmaps, and free those from R2, resetting them | |
502 | to 0. */ | |
503 | for (cl1 = r1->sub_conflicts; cl1; cl1 = cl1->next) | |
504 | for (cl2 = r2->sub_conflicts; cl2; cl2 = cl2->next) | |
505 | if (cl1->size_word == cl2->size_word) | |
506 | { | |
507 | bitmap_operation (cl1->conflicts, cl1->conflicts, | |
508 | cl2->conflicts, BITMAP_IOR); | |
509 | BITMAP_XFREE (cl2->conflicts); | |
510 | cl2->conflicts = NULL; | |
511 | } | |
512 | /* Now the conflict lists from R2 which weren't in R1. | |
513 | We simply copy the entries from R2 into R1' list. */ | |
514 | for (cl2 = r2->sub_conflicts; cl2;) | |
515 | { | |
516 | struct tagged_conflict *cl_next = cl2->next; | |
517 | if (cl2->conflicts) | |
518 | { | |
519 | cl2->next = r1->sub_conflicts; | |
520 | r1->sub_conflicts = cl2; | |
521 | } | |
522 | cl2 = cl_next; | |
523 | } | |
524 | } | |
525 | r2->sub_conflicts = NULL; | |
526 | r1->crosses_call |= r2->crosses_call; | |
527 | } | |
528 | return r1; | |
529 | } | |
530 | ||
d55d8fc7 | 531 | /* Convenience macro, that is capable of unioning also non-roots. */ |
ed8d2920 MM |
532 | #define union_web_parts(p1, p2) \ |
533 | ((p1 == p2) ? find_web_part (p1) \ | |
534 | : union_web_part_roots (find_web_part (p1), find_web_part (p2))) | |
535 | ||
536 | /* Remember that we've handled a given move, so we don't reprocess it. */ | |
537 | ||
538 | static void | |
93bad80e | 539 | remember_move (rtx insn) |
ed8d2920 MM |
540 | { |
541 | if (!TEST_BIT (move_handled, INSN_UID (insn))) | |
542 | { | |
543 | rtx s, d; | |
544 | SET_BIT (move_handled, INSN_UID (insn)); | |
545 | if (copy_insn_p (insn, &s, &d)) | |
546 | { | |
4b7e68e7 | 547 | /* Some sanity test for the copy insn. */ |
ed8d2920 MM |
548 | struct df_link *slink = DF_INSN_USES (df, insn); |
549 | struct df_link *link = DF_INSN_DEFS (df, insn); | |
550 | if (!link || !link->ref || !slink || !slink->ref) | |
551 | abort (); | |
552 | /* The following (link->next != 0) happens when a hardreg | |
553 | is used in wider mode (REG:DI %eax). Then df.* creates | |
554 | a def/use for each hardreg contained therein. We only | |
555 | allow hardregs here. */ | |
556 | if (link->next | |
557 | && DF_REF_REGNO (link->next->ref) >= FIRST_PSEUDO_REGISTER) | |
558 | abort (); | |
559 | } | |
560 | else | |
561 | abort (); | |
562 | /* XXX for now we don't remember move insns involving any subregs. | |
563 | Those would be difficult to coalesce (we would need to implement | |
564 | handling of all the subwebs in the allocator, including that such | |
d55d8fc7 | 565 | subwebs could be source and target of coalescing). */ |
ed8d2920 MM |
566 | if (GET_CODE (s) == REG && GET_CODE (d) == REG) |
567 | { | |
703ad42b | 568 | struct move *m = ra_calloc (sizeof (struct move)); |
ed8d2920 MM |
569 | struct move_list *ml; |
570 | m->insn = insn; | |
703ad42b | 571 | ml = ra_alloc (sizeof (struct move_list)); |
ed8d2920 MM |
572 | ml->move = m; |
573 | ml->next = wl_moves; | |
574 | wl_moves = ml; | |
575 | } | |
576 | } | |
577 | } | |
578 | ||
579 | /* This describes the USE currently looked at in the main-loop in | |
580 | build_web_parts_and_conflicts(). */ | |
581 | struct curr_use { | |
582 | struct web_part *wp; | |
583 | /* This has a 1-bit for each byte in the USE, which is still undefined. */ | |
584 | unsigned HOST_WIDE_INT undefined; | |
585 | /* For easy access. */ | |
586 | unsigned int regno; | |
587 | rtx x; | |
588 | /* If some bits of this USE are live over an abnormal edge. */ | |
589 | unsigned int live_over_abnormal; | |
590 | }; | |
591 | ||
592 | /* Returns nonzero iff rtx DEF and USE have bits in common (but see below). | |
593 | It is only called with DEF and USE being (reg:M a) or (subreg:M1 (reg:M2 a) | |
594 | x) rtx's. Furthermore if it's a subreg rtx M1 is at least one word wide, | |
595 | and a is a multi-word pseudo. If DEF or USE are hardregs, they are in | |
28432d9f | 596 | word_mode, so we don't need to check for further hardregs which would result |
ed8d2920 MM |
597 | from wider references. We are never called with paradoxical subregs. |
598 | ||
599 | This returns: | |
600 | 0 for no common bits, | |
601 | 1 if DEF and USE exactly cover the same bytes, | |
602 | 2 if the DEF only covers a part of the bits of USE | |
603 | 3 if the DEF covers more than the bits of the USE, and | |
604 | 4 if both are SUBREG's of different size, but have bytes in common. | |
605 | -1 is a special case, for when DEF and USE refer to the same regno, but | |
606 | have for other reasons no bits in common (can only happen with | |
e0bb17a8 | 607 | subregs referring to different words, or to words which already were |
ed8d2920 MM |
608 | defined for this USE). |
609 | Furthermore it modifies use->undefined to clear the bits which get defined | |
610 | by DEF (only for cases with partial overlap). | |
611 | I.e. if bit 1 is set for the result != -1, the USE was completely covered, | |
612 | otherwise a test is needed to track the already defined bytes. */ | |
613 | ||
614 | static int | |
93bad80e | 615 | defuse_overlap_p_1 (rtx def, struct curr_use *use) |
ed8d2920 MM |
616 | { |
617 | int mode = 0; | |
618 | if (def == use->x) | |
619 | return 1; | |
620 | if (!def) | |
621 | return 0; | |
622 | if (GET_CODE (def) == SUBREG) | |
623 | { | |
624 | if (REGNO (SUBREG_REG (def)) != use->regno) | |
625 | return 0; | |
626 | mode |= 1; | |
627 | } | |
628 | else if (REGNO (def) != use->regno) | |
629 | return 0; | |
630 | if (GET_CODE (use->x) == SUBREG) | |
631 | mode |= 2; | |
632 | switch (mode) | |
633 | { | |
634 | case 0: /* REG, REG */ | |
635 | return 1; | |
636 | case 1: /* SUBREG, REG */ | |
637 | { | |
638 | unsigned HOST_WIDE_INT old_u = use->undefined; | |
639 | use->undefined &= ~ rtx_to_undefined (def); | |
640 | return (old_u != use->undefined) ? 2 : -1; | |
641 | } | |
642 | case 2: /* REG, SUBREG */ | |
643 | return 3; | |
644 | case 3: /* SUBREG, SUBREG */ | |
645 | if (GET_MODE_SIZE (GET_MODE (def)) == GET_MODE_SIZE (GET_MODE (use->x))) | |
646 | /* If the size of both things is the same, the subreg's overlap | |
647 | if they refer to the same word. */ | |
648 | if (SUBREG_BYTE (def) == SUBREG_BYTE (use->x)) | |
649 | return 1; | |
4d6922ee | 650 | /* Now the more difficult part: the same regno is referred, but the |
ed8d2920 MM |
651 | sizes of the references or the words differ. E.g. |
652 | (subreg:SI (reg:CDI a) 0) and (subreg:DI (reg:CDI a) 2) do not | |
d55d8fc7 | 653 | overlap, whereas the latter overlaps with (subreg:SI (reg:CDI a) 3). |
ed8d2920 MM |
654 | */ |
655 | { | |
656 | unsigned HOST_WIDE_INT old_u; | |
657 | int b1, e1, b2, e2; | |
658 | unsigned int bl1, bl2; | |
659 | bl1 = rtx_to_bits (def); | |
660 | bl2 = rtx_to_bits (use->x); | |
661 | b1 = BYTE_BEGIN (bl1); | |
662 | b2 = BYTE_BEGIN (bl2); | |
663 | e1 = b1 + BYTE_LENGTH (bl1) - 1; | |
664 | e2 = b2 + BYTE_LENGTH (bl2) - 1; | |
665 | if (b1 > e2 || b2 > e1) | |
666 | return -1; | |
667 | old_u = use->undefined; | |
668 | use->undefined &= ~ rtx_to_undefined (def); | |
669 | return (old_u != use->undefined) ? 4 : -1; | |
670 | } | |
671 | default: | |
672 | abort (); | |
673 | } | |
674 | } | |
675 | ||
676 | /* Macro for the common case of either def and use having the same rtx, | |
677 | or based on different regnos. */ | |
678 | #define defuse_overlap_p(def, use) \ | |
679 | ((def) == (use)->x ? 1 : \ | |
680 | (REGNO (GET_CODE (def) == SUBREG \ | |
681 | ? SUBREG_REG (def) : def) != use->regno \ | |
682 | ? 0 : defuse_overlap_p_1 (def, use))) | |
683 | ||
684 | ||
685 | /* The use USE flows into INSN (backwards). Determine INSNs effect on it, | |
686 | and return nonzero, if (parts of) that USE are also live before it. | |
687 | This also notes conflicts between the USE and all DEFS in that insn, | |
688 | and modifies the undefined bits of USE in case parts of it were set in | |
689 | this insn. */ | |
690 | ||
691 | static int | |
93bad80e | 692 | live_out_1 (struct df *df ATTRIBUTE_UNUSED, struct curr_use *use, rtx insn) |
ed8d2920 MM |
693 | { |
694 | int defined = 0; | |
695 | int uid = INSN_UID (insn); | |
696 | struct web_part *wp = use->wp; | |
697 | ||
698 | /* Mark, that this insn needs this webpart live. */ | |
699 | visit_trace[uid].wp = wp; | |
700 | visit_trace[uid].undefined = use->undefined; | |
701 | ||
702 | if (INSN_P (insn)) | |
703 | { | |
704 | unsigned int source_regno = ~0; | |
705 | unsigned int regno = use->regno; | |
706 | unsigned HOST_WIDE_INT orig_undef = use->undefined; | |
707 | unsigned HOST_WIDE_INT final_undef = use->undefined; | |
708 | rtx s = NULL; | |
709 | unsigned int n, num_defs = insn_df[uid].num_defs; | |
710 | struct ref **defs = insn_df[uid].defs; | |
711 | ||
712 | /* We want to access the root webpart. */ | |
713 | wp = find_web_part (wp); | |
714 | if (GET_CODE (insn) == CALL_INSN) | |
715 | wp->crosses_call = 1; | |
716 | else if (copy_insn_p (insn, &s, NULL)) | |
717 | source_regno = REGNO (GET_CODE (s) == SUBREG ? SUBREG_REG (s) : s); | |
718 | ||
719 | /* Look at all DEFS in this insn. */ | |
720 | for (n = 0; n < num_defs; n++) | |
721 | { | |
722 | struct ref *ref = defs[n]; | |
723 | int lap; | |
724 | ||
725 | /* Reset the undefined bits for each iteration, in case this | |
726 | insn has more than one set, and one of them sets this regno. | |
727 | But still the original undefined part conflicts with the other | |
728 | sets. */ | |
729 | use->undefined = orig_undef; | |
730 | if ((lap = defuse_overlap_p (DF_REF_REG (ref), use)) != 0) | |
731 | { | |
732 | if (lap == -1) | |
733 | /* Same regnos but non-overlapping or already defined bits, | |
734 | so ignore this DEF, or better said make the yet undefined | |
735 | part and this DEF conflicting. */ | |
736 | { | |
737 | unsigned HOST_WIDE_INT undef; | |
738 | undef = use->undefined; | |
739 | while (undef) | |
740 | bitmap_set_bit (undef_to_bitmap (wp, &undef), | |
741 | DF_REF_ID (ref)); | |
742 | continue; | |
743 | } | |
744 | if ((lap & 1) != 0) | |
745 | /* The current DEF completely covers the USE, so we can | |
746 | stop traversing the code looking for further DEFs. */ | |
747 | defined = 1; | |
748 | else | |
749 | /* We have a partial overlap. */ | |
750 | { | |
751 | final_undef &= use->undefined; | |
752 | if (final_undef == 0) | |
753 | /* Now the USE is completely defined, which means, that | |
754 | we can stop looking for former DEFs. */ | |
755 | defined = 1; | |
756 | /* If this is a partial overlap, which left some bits | |
757 | in USE undefined, we normally would need to create | |
758 | conflicts between that undefined part and the part of | |
759 | this DEF which overlapped with some of the formerly | |
760 | undefined bits. We don't need to do this, because both | |
761 | parts of this DEF (that which overlaps, and that which | |
762 | doesn't) are written together in this one DEF, and can | |
763 | not be colored in a way which would conflict with | |
764 | the USE. This is only true for partial overlap, | |
765 | because only then the DEF and USE have bits in common, | |
766 | which makes the DEF move, if the USE moves, making them | |
767 | aligned. | |
768 | If they have no bits in common (lap == -1), they are | |
769 | really independent. Therefore we there made a | |
770 | conflict above. */ | |
771 | } | |
772 | /* This is at least a partial overlap, so we need to union | |
773 | the web parts. */ | |
774 | wp = union_web_parts (wp, &web_parts[DF_REF_ID (ref)]); | |
775 | } | |
776 | else | |
777 | { | |
778 | /* The DEF and the USE don't overlap at all, different | |
779 | regnos. I.e. make conflicts between the undefined bits, | |
780 | and that DEF. */ | |
781 | unsigned HOST_WIDE_INT undef = use->undefined; | |
782 | ||
783 | if (regno == source_regno) | |
784 | /* This triggers only, when this was a copy insn and the | |
785 | source is at least a part of the USE currently looked at. | |
786 | In this case only the bits of the USE conflict with the | |
787 | DEF, which are not covered by the source of this copy | |
788 | insn, and which are still undefined. I.e. in the best | |
789 | case (the whole reg being the source), _no_ conflicts | |
790 | between that USE and this DEF (the target of the move) | |
791 | are created by this insn (though they might be by | |
792 | others). This is a super case of the normal copy insn | |
793 | only between full regs. */ | |
794 | { | |
795 | undef &= ~ rtx_to_undefined (s); | |
796 | } | |
797 | if (undef) | |
798 | { | |
799 | /*struct web_part *cwp; | |
800 | cwp = find_web_part (&web_parts[DF_REF_ID | |
801 | (ref)]);*/ | |
802 | ||
803 | /* TODO: somehow instead of noting the ID of the LINK | |
804 | use an ID nearer to the root webpart of that LINK. | |
805 | We can't use the root itself, because we later use the | |
806 | ID to look at the form (reg or subreg, and if yes, | |
807 | which subreg) of this conflict. This means, that we | |
808 | need to remember in the root an ID for each form, and | |
809 | maintaining this, when merging web parts. This makes | |
810 | the bitmaps smaller. */ | |
811 | do | |
812 | bitmap_set_bit (undef_to_bitmap (wp, &undef), | |
813 | DF_REF_ID (ref)); | |
814 | while (undef); | |
815 | } | |
816 | } | |
817 | } | |
818 | if (defined) | |
819 | use->undefined = 0; | |
820 | else | |
821 | { | |
822 | /* If this insn doesn't completely define the USE, increment also | |
4b7e68e7 | 823 | it's spanned deaths count (if this insn contains a death). */ |
ed8d2920 MM |
824 | if (uid >= death_insns_max_uid) |
825 | abort (); | |
826 | if (TEST_BIT (insns_with_deaths, uid)) | |
827 | wp->spanned_deaths++; | |
828 | use->undefined = final_undef; | |
829 | } | |
830 | } | |
831 | ||
832 | return !defined; | |
833 | } | |
834 | ||
835 | /* Same as live_out_1() (actually calls it), but caches some information. | |
836 | E.g. if we reached this INSN with the current regno already, and the | |
837 | current undefined bits are a subset of those as we came here, we | |
838 | simply connect the web parts of the USE, and the one cached for this | |
839 | INSN, and additionally return zero, indicating we don't need to traverse | |
840 | this path any longer (all effect were already seen, as we first reached | |
841 | this insn). */ | |
842 | ||
843 | static inline int | |
93bad80e | 844 | live_out (struct df *df, struct curr_use *use, rtx insn) |
ed8d2920 MM |
845 | { |
846 | unsigned int uid = INSN_UID (insn); | |
847 | if (visit_trace[uid].wp | |
848 | && DF_REF_REGNO (visit_trace[uid].wp->ref) == use->regno | |
849 | && (use->undefined & ~visit_trace[uid].undefined) == 0) | |
850 | { | |
851 | union_web_parts (visit_trace[uid].wp, use->wp); | |
4b7e68e7 | 852 | /* Don't search any further, as we already were here with this regno. */ |
ed8d2920 MM |
853 | return 0; |
854 | } | |
855 | else | |
856 | return live_out_1 (df, use, insn); | |
857 | } | |
858 | ||
859 | /* The current USE reached a basic block head. The edge E is one | |
860 | of the predecessors edges. This evaluates the effect of the predecessor | |
861 | block onto the USE, and returns the next insn, which should be looked at. | |
862 | This either is the last insn of that pred. block, or the first one. | |
863 | The latter happens, when the pred. block has no possible effect on the | |
864 | USE, except for conflicts. In that case, it's remembered, that the USE | |
865 | is live over that whole block, and it's skipped. Otherwise we simply | |
866 | continue with the last insn of the block. | |
867 | ||
868 | This also determines the effects of abnormal edges, and remembers | |
869 | which uses are live at the end of that basic block. */ | |
870 | ||
871 | static rtx | |
93bad80e | 872 | live_in_edge (struct df *df, struct curr_use *use, edge e) |
ed8d2920 MM |
873 | { |
874 | struct ra_bb_info *info_pred; | |
875 | rtx next_insn; | |
876 | /* Call used hard regs die over an exception edge, ergo | |
877 | they don't reach the predecessor block, so ignore such | |
878 | uses. And also don't set the live_over_abnormal flag | |
879 | for them. */ | |
880 | if ((e->flags & EDGE_EH) && use->regno < FIRST_PSEUDO_REGISTER | |
881 | && call_used_regs[use->regno]) | |
882 | return NULL_RTX; | |
883 | if (e->flags & EDGE_ABNORMAL) | |
884 | use->live_over_abnormal = 1; | |
885 | bitmap_set_bit (live_at_end[e->src->index], DF_REF_ID (use->wp->ref)); | |
886 | info_pred = (struct ra_bb_info *) e->src->aux; | |
a813c111 | 887 | next_insn = BB_END (e->src); |
ed8d2920 MM |
888 | |
889 | /* If the last insn of the pred. block doesn't completely define the | |
890 | current use, we need to check the block. */ | |
891 | if (live_out (df, use, next_insn)) | |
892 | { | |
893 | /* If the current regno isn't mentioned anywhere in the whole block, | |
894 | and the complete use is still undefined... */ | |
895 | if (!bitmap_bit_p (info_pred->regnos_mentioned, use->regno) | |
896 | && (rtx_to_undefined (use->x) & ~use->undefined) == 0) | |
897 | { | |
898 | /* ...we can hop over the whole block and defer conflict | |
899 | creation to later. */ | |
900 | bitmap_set_bit (info_pred->live_throughout, | |
901 | DF_REF_ID (use->wp->ref)); | |
a813c111 | 902 | next_insn = BB_HEAD (e->src); |
ed8d2920 MM |
903 | } |
904 | return next_insn; | |
905 | } | |
906 | else | |
907 | return NULL_RTX; | |
908 | } | |
909 | ||
910 | /* USE flows into the end of the insns preceding INSN. Determine | |
911 | their effects (in live_out()) and possibly loop over the preceding INSN, | |
912 | or call itself recursively on a basic block border. When a topleve | |
913 | call of this function returns the USE is completely analyzed. I.e. | |
914 | its def-use chain (at least) is built, possibly connected with other | |
915 | def-use chains, and all defs during that chain are noted. */ | |
916 | ||
917 | static void | |
93bad80e | 918 | live_in (struct df *df, struct curr_use *use, rtx insn) |
ed8d2920 MM |
919 | { |
920 | unsigned int loc_vpass = visited_pass; | |
921 | ||
922 | /* Note, that, even _if_ we are called with use->wp a root-part, this might | |
923 | become non-root in the for() loop below (due to live_out() unioning | |
924 | it). So beware, not to change use->wp in a way, for which only root-webs | |
925 | are allowed. */ | |
926 | while (1) | |
927 | { | |
928 | int uid = INSN_UID (insn); | |
929 | basic_block bb = BLOCK_FOR_INSN (insn); | |
930 | number_seen[uid]++; | |
931 | ||
d55d8fc7 | 932 | /* We want to be as fast as possible, so explicitly write |
ed8d2920 MM |
933 | this loop. */ |
934 | for (insn = PREV_INSN (insn); insn && !INSN_P (insn); | |
935 | insn = PREV_INSN (insn)) | |
936 | ; | |
937 | if (!insn) | |
938 | return; | |
939 | if (bb != BLOCK_FOR_INSN (insn)) | |
940 | { | |
941 | edge e; | |
942 | unsigned HOST_WIDE_INT undef = use->undefined; | |
943 | struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; | |
944 | if ((e = bb->pred) == NULL) | |
945 | return; | |
946 | /* We now check, if we already traversed the predecessors of this | |
947 | block for the current pass and the current set of undefined | |
948 | bits. If yes, we don't need to check the predecessors again. | |
949 | So, conceptually this information is tagged to the first | |
950 | insn of a basic block. */ | |
951 | if (info->pass == loc_vpass && (undef & ~info->undefined) == 0) | |
952 | return; | |
953 | info->pass = loc_vpass; | |
954 | info->undefined = undef; | |
955 | /* All but the last predecessor are handled recursively. */ | |
956 | for (; e->pred_next; e = e->pred_next) | |
957 | { | |
958 | insn = live_in_edge (df, use, e); | |
959 | if (insn) | |
960 | live_in (df, use, insn); | |
961 | use->undefined = undef; | |
962 | } | |
963 | insn = live_in_edge (df, use, e); | |
964 | if (!insn) | |
965 | return; | |
966 | } | |
967 | else if (!live_out (df, use, insn)) | |
968 | return; | |
969 | } | |
970 | } | |
971 | ||
972 | /* Determine all regnos which are mentioned in a basic block, in an | |
973 | interesting way. Interesting here means either in a def, or as the | |
974 | source of a move insn. We only look at insns added since the last | |
975 | pass. */ | |
976 | ||
977 | static void | |
93bad80e | 978 | update_regnos_mentioned (void) |
ed8d2920 MM |
979 | { |
980 | int last_uid = last_max_uid; | |
981 | rtx insn; | |
982 | basic_block bb; | |
983 | for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) | |
984 | if (INSN_P (insn)) | |
985 | { | |
986 | /* Don't look at old insns. */ | |
987 | if (INSN_UID (insn) < last_uid) | |
988 | { | |
989 | /* XXX We should also remember moves over iterations (we already | |
990 | save the cache, but not the movelist). */ | |
991 | if (copy_insn_p (insn, NULL, NULL)) | |
992 | remember_move (insn); | |
993 | } | |
994 | else if ((bb = BLOCK_FOR_INSN (insn)) != NULL) | |
995 | { | |
996 | rtx source; | |
997 | struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; | |
998 | bitmap mentioned = info->regnos_mentioned; | |
999 | struct df_link *link; | |
1000 | if (copy_insn_p (insn, &source, NULL)) | |
1001 | { | |
1002 | remember_move (insn); | |
1003 | bitmap_set_bit (mentioned, | |
1004 | REGNO (GET_CODE (source) == SUBREG | |
1005 | ? SUBREG_REG (source) : source)); | |
1006 | } | |
1007 | for (link = DF_INSN_DEFS (df, insn); link; link = link->next) | |
1008 | if (link->ref) | |
1009 | bitmap_set_bit (mentioned, DF_REF_REGNO (link->ref)); | |
1010 | } | |
1011 | } | |
1012 | } | |
1013 | ||
d55d8fc7 | 1014 | /* Handle the uses which reach a block end, but were deferred due |
ed8d2920 MM |
1015 | to it's regno not being mentioned in that block. This adds the |
1016 | remaining conflicts and updates also the crosses_call and | |
1017 | spanned_deaths members. */ | |
1018 | ||
1019 | static void | |
93bad80e | 1020 | livethrough_conflicts_bb (basic_block bb) |
ed8d2920 MM |
1021 | { |
1022 | struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; | |
1023 | rtx insn; | |
1024 | bitmap all_defs; | |
1025 | int first, use_id; | |
1026 | unsigned int deaths = 0; | |
1027 | unsigned int contains_call = 0; | |
1028 | ||
d55d8fc7 | 1029 | /* If there are no deferred uses, just return. */ |
ed8d2920 MM |
1030 | if ((first = bitmap_first_set_bit (info->live_throughout)) < 0) |
1031 | return; | |
1032 | ||
1033 | /* First collect the IDs of all defs, count the number of death | |
1034 | containing insns, and if there's some call_insn here. */ | |
1035 | all_defs = BITMAP_XMALLOC (); | |
a813c111 | 1036 | for (insn = BB_HEAD (bb); insn; insn = NEXT_INSN (insn)) |
ed8d2920 MM |
1037 | { |
1038 | if (INSN_P (insn)) | |
1039 | { | |
ed8d2920 | 1040 | unsigned int n; |
533c4863 KG |
1041 | struct ra_insn_info info; |
1042 | ||
1043 | info = insn_df[INSN_UID (insn)]; | |
ed8d2920 MM |
1044 | for (n = 0; n < info.num_defs; n++) |
1045 | bitmap_set_bit (all_defs, DF_REF_ID (info.defs[n])); | |
1046 | if (TEST_BIT (insns_with_deaths, INSN_UID (insn))) | |
1047 | deaths++; | |
1048 | if (GET_CODE (insn) == CALL_INSN) | |
1049 | contains_call = 1; | |
1050 | } | |
a813c111 | 1051 | if (insn == BB_END (bb)) |
ed8d2920 MM |
1052 | break; |
1053 | } | |
1054 | ||
1055 | /* And now, if we have found anything, make all live_through | |
1056 | uses conflict with all defs, and update their other members. */ | |
1057 | if (deaths > 0 || bitmap_first_set_bit (all_defs) >= 0) | |
1058 | EXECUTE_IF_SET_IN_BITMAP (info->live_throughout, first, use_id, | |
1059 | { | |
1060 | struct web_part *wp = &web_parts[df->def_id + use_id]; | |
1061 | unsigned int bl = rtx_to_bits (DF_REF_REG (wp->ref)); | |
1062 | bitmap conflicts; | |
1063 | wp = find_web_part (wp); | |
1064 | wp->spanned_deaths += deaths; | |
1065 | wp->crosses_call |= contains_call; | |
1066 | conflicts = get_sub_conflicts (wp, bl); | |
1067 | bitmap_operation (conflicts, conflicts, all_defs, BITMAP_IOR); | |
1068 | }); | |
1069 | ||
1070 | BITMAP_XFREE (all_defs); | |
1071 | } | |
1072 | ||
1073 | /* Allocate the per basic block info for traversing the insn stream for | |
1074 | building live ranges. */ | |
1075 | ||
1076 | static void | |
93bad80e | 1077 | init_bb_info (void) |
ed8d2920 MM |
1078 | { |
1079 | basic_block bb; | |
1080 | FOR_ALL_BB (bb) | |
1081 | { | |
703ad42b | 1082 | struct ra_bb_info *info = xcalloc (1, sizeof *info); |
ed8d2920 MM |
1083 | info->regnos_mentioned = BITMAP_XMALLOC (); |
1084 | info->live_throughout = BITMAP_XMALLOC (); | |
1085 | info->old_aux = bb->aux; | |
1086 | bb->aux = (void *) info; | |
1087 | } | |
1088 | } | |
1089 | ||
1090 | /* Free that per basic block info. */ | |
1091 | ||
1092 | static void | |
93bad80e | 1093 | free_bb_info (void) |
ed8d2920 MM |
1094 | { |
1095 | basic_block bb; | |
1096 | FOR_ALL_BB (bb) | |
1097 | { | |
1098 | struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; | |
1099 | BITMAP_XFREE (info->regnos_mentioned); | |
1100 | BITMAP_XFREE (info->live_throughout); | |
1101 | bb->aux = info->old_aux; | |
1102 | free (info); | |
1103 | } | |
1104 | } | |
1105 | ||
1106 | /* Toplevel function for the first part of this file. | |
d55d8fc7 | 1107 | Connect web parts, thereby implicitly building webs, and remember |
ed8d2920 MM |
1108 | their conflicts. */ |
1109 | ||
1110 | static void | |
93bad80e | 1111 | build_web_parts_and_conflicts (struct df *df) |
ed8d2920 MM |
1112 | { |
1113 | struct df_link *link; | |
1114 | struct curr_use use; | |
1115 | basic_block bb; | |
1116 | ||
703ad42b KG |
1117 | number_seen = xcalloc (get_max_uid (), sizeof (int)); |
1118 | visit_trace = xcalloc (get_max_uid (), sizeof (visit_trace[0])); | |
ed8d2920 MM |
1119 | update_regnos_mentioned (); |
1120 | ||
1121 | /* Here's the main loop. | |
1122 | It goes through all insn's, connects web parts along the way, notes | |
1123 | conflicts between webparts, and remembers move instructions. */ | |
1124 | visited_pass = 0; | |
1125 | for (use.regno = 0; use.regno < (unsigned int)max_regno; use.regno++) | |
1126 | if (use.regno >= FIRST_PSEUDO_REGISTER || !fixed_regs[use.regno]) | |
1127 | for (link = df->regs[use.regno].uses; link; link = link->next) | |
1128 | if (link->ref) | |
1129 | { | |
1130 | struct ref *ref = link->ref; | |
1131 | rtx insn = DF_REF_INSN (ref); | |
1132 | /* Only recheck marked or new uses, or uses from hardregs. */ | |
1133 | if (use.regno >= FIRST_PSEUDO_REGISTER | |
1134 | && DF_REF_ID (ref) < last_use_id | |
1135 | && !TEST_BIT (last_check_uses, DF_REF_ID (ref))) | |
1136 | continue; | |
1137 | use.wp = &web_parts[df->def_id + DF_REF_ID (ref)]; | |
1138 | use.x = DF_REF_REG (ref); | |
1139 | use.live_over_abnormal = 0; | |
1140 | use.undefined = rtx_to_undefined (use.x); | |
1141 | visited_pass++; | |
1142 | live_in (df, &use, insn); | |
1143 | if (use.live_over_abnormal) | |
1144 | SET_BIT (live_over_abnormal, DF_REF_ID (ref)); | |
1145 | } | |
1146 | ||
1147 | dump_number_seen (); | |
1148 | FOR_ALL_BB (bb) | |
1149 | { | |
1150 | struct ra_bb_info *info = (struct ra_bb_info *) bb->aux; | |
1151 | livethrough_conflicts_bb (bb); | |
1152 | bitmap_zero (info->live_throughout); | |
1153 | info->pass = 0; | |
1154 | } | |
1155 | free (visit_trace); | |
1156 | free (number_seen); | |
1157 | } | |
1158 | ||
1159 | /* Here we look per insn, for DF references being in uses _and_ defs. | |
1160 | This means, in the RTL a (REG xx) expression was seen as a | |
1161 | read/modify/write, as happens for (set (subreg:SI (reg:DI xx)) (...)) | |
1162 | e.g. Our code has created two webs for this, as it should. Unfortunately, | |
1163 | as the REG reference is only one time in the RTL we can't color | |
1164 | both webs different (arguably this also would be wrong for a real | |
1165 | read-mod-write instruction), so we must reconnect such webs. */ | |
1166 | ||
1167 | static void | |
93bad80e | 1168 | connect_rmw_web_parts (struct df *df) |
ed8d2920 MM |
1169 | { |
1170 | unsigned int i; | |
1171 | ||
1172 | for (i = 0; i < df->use_id; i++) | |
1173 | { | |
1174 | struct web_part *wp1 = &web_parts[df->def_id + i]; | |
1175 | rtx reg; | |
1176 | struct df_link *link; | |
1177 | if (!wp1->ref) | |
1178 | continue; | |
1179 | /* If it's an uninitialized web, we don't want to connect it to others, | |
1180 | as the read cycle in read-mod-write had probably no effect. */ | |
1181 | if (find_web_part (wp1) >= &web_parts[df->def_id]) | |
1182 | continue; | |
1183 | reg = DF_REF_REAL_REG (wp1->ref); | |
1184 | link = DF_INSN_DEFS (df, DF_REF_INSN (wp1->ref)); | |
1185 | for (; link; link = link->next) | |
1186 | if (reg == DF_REF_REAL_REG (link->ref)) | |
1187 | { | |
1188 | struct web_part *wp2 = &web_parts[DF_REF_ID (link->ref)]; | |
1189 | union_web_parts (wp1, wp2); | |
1190 | } | |
1191 | } | |
1192 | } | |
1193 | ||
1194 | /* Deletes all hardregs from *S which are not allowed for MODE. */ | |
1195 | ||
1196 | static void | |
93bad80e | 1197 | prune_hardregs_for_mode (HARD_REG_SET *s, enum machine_mode mode) |
ed8d2920 MM |
1198 | { |
1199 | AND_HARD_REG_SET (*s, hardregs_for_mode[(int) mode]); | |
1200 | } | |
1201 | ||
1202 | /* Initialize the members of a web, which are deducible from REG. */ | |
1203 | ||
1204 | static void | |
93bad80e | 1205 | init_one_web_common (struct web *web, rtx reg) |
ed8d2920 MM |
1206 | { |
1207 | if (GET_CODE (reg) != REG) | |
1208 | abort (); | |
1209 | /* web->id isn't initialized here. */ | |
1210 | web->regno = REGNO (reg); | |
1211 | web->orig_x = reg; | |
1212 | if (!web->dlink) | |
1213 | { | |
703ad42b | 1214 | web->dlink = ra_calloc (sizeof (struct dlist)); |
ed8d2920 MM |
1215 | DLIST_WEB (web->dlink) = web; |
1216 | } | |
1217 | /* XXX | |
1218 | the former (superunion) doesn't constrain the graph enough. E.g. | |
1219 | on x86 QImode _requires_ QI_REGS, but as alternate class usually | |
1220 | GENERAL_REGS is given. So the graph is not constrained enough, | |
1221 | thinking it has more freedom then it really has, which leads | |
1222 | to repeated spill tryings. OTOH the latter (only using preferred | |
1223 | class) is too constrained, as normally (e.g. with all SImode | |
1224 | pseudos), they can be allocated also in the alternate class. | |
1225 | What we really want, are the _exact_ hard regs allowed, not | |
1226 | just a class. Later. */ | |
1227 | /*web->regclass = reg_class_superunion | |
1228 | [reg_preferred_class (web->regno)] | |
1229 | [reg_alternate_class (web->regno)];*/ | |
1230 | /*web->regclass = reg_preferred_class (web->regno);*/ | |
1231 | web->regclass = reg_class_subunion | |
1232 | [reg_preferred_class (web->regno)] [reg_alternate_class (web->regno)]; | |
1233 | web->regclass = reg_preferred_class (web->regno); | |
1234 | if (web->regno < FIRST_PSEUDO_REGISTER) | |
1235 | { | |
1236 | web->color = web->regno; | |
1237 | put_web (web, PRECOLORED); | |
1238 | web->num_conflicts = UINT_MAX; | |
1239 | web->add_hardregs = 0; | |
1240 | CLEAR_HARD_REG_SET (web->usable_regs); | |
1241 | SET_HARD_REG_BIT (web->usable_regs, web->regno); | |
1242 | web->num_freedom = 1; | |
1243 | } | |
1244 | else | |
1245 | { | |
1246 | HARD_REG_SET alternate; | |
1247 | web->color = -1; | |
1248 | put_web (web, INITIAL); | |
1249 | /* add_hardregs is wrong in multi-length classes, e.g. | |
1250 | using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS, | |
1251 | where, if it finally is allocated to GENERAL_REGS it needs two, | |
1252 | if allocated to FLOAT_REGS only one hardreg. XXX */ | |
1253 | web->add_hardregs = | |
1254 | CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1; | |
1255 | web->num_conflicts = 0 * web->add_hardregs; | |
1256 | COPY_HARD_REG_SET (web->usable_regs, | |
1257 | reg_class_contents[reg_preferred_class (web->regno)]); | |
1258 | COPY_HARD_REG_SET (alternate, | |
1259 | reg_class_contents[reg_alternate_class (web->regno)]); | |
1260 | IOR_HARD_REG_SET (web->usable_regs, alternate); | |
1261 | /*IOR_HARD_REG_SET (web->usable_regs, | |
1262 | reg_class_contents[reg_alternate_class | |
1263 | (web->regno)]);*/ | |
1264 | AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors); | |
1265 | prune_hardregs_for_mode (&web->usable_regs, | |
1266 | PSEUDO_REGNO_MODE (web->regno)); | |
50aac998 | 1267 | #ifdef CANNOT_CHANGE_MODE_CLASS |
ed8d2920 | 1268 | if (web->mode_changed) |
50aac998 | 1269 | AND_COMPL_HARD_REG_SET (web->usable_regs, invalid_mode_change_regs); |
ed8d2920 MM |
1270 | #endif |
1271 | web->num_freedom = hard_regs_count (web->usable_regs); | |
1272 | web->num_freedom -= web->add_hardregs; | |
1273 | if (!web->num_freedom) | |
1274 | abort(); | |
1275 | } | |
1276 | COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs); | |
1277 | } | |
1278 | ||
1279 | /* Initializes WEBs members from REG or zero them. */ | |
1280 | ||
1281 | static void | |
93bad80e | 1282 | init_one_web (struct web *web, rtx reg) |
ed8d2920 MM |
1283 | { |
1284 | memset (web, 0, sizeof (struct web)); | |
1285 | init_one_web_common (web, reg); | |
1286 | web->useless_conflicts = BITMAP_XMALLOC (); | |
1287 | } | |
1288 | ||
1289 | /* WEB is an old web, meaning it came from the last pass, and got a | |
1290 | color. We want to remember some of it's info, so zero only some | |
1291 | members. */ | |
1292 | ||
1293 | static void | |
93bad80e | 1294 | reinit_one_web (struct web *web, rtx reg) |
ed8d2920 MM |
1295 | { |
1296 | web->old_color = web->color + 1; | |
1297 | init_one_web_common (web, reg); | |
1298 | web->span_deaths = 0; | |
1299 | web->spill_temp = 0; | |
1300 | web->orig_spill_temp = 0; | |
1301 | web->use_my_regs = 0; | |
1302 | web->spill_cost = 0; | |
1303 | web->was_spilled = 0; | |
1304 | web->is_coalesced = 0; | |
1305 | web->artificial = 0; | |
1306 | web->live_over_abnormal = 0; | |
1307 | web->mode_changed = 0; | |
50aac998 | 1308 | web->subreg_stripped = 0; |
ed8d2920 MM |
1309 | web->move_related = 0; |
1310 | web->in_load = 0; | |
1311 | web->target_of_spilled_move = 0; | |
1312 | web->num_aliased = 0; | |
1313 | if (web->type == PRECOLORED) | |
1314 | { | |
1315 | web->num_defs = 0; | |
1316 | web->num_uses = 0; | |
1317 | web->orig_spill_cost = 0; | |
1318 | } | |
1319 | CLEAR_HARD_REG_SET (web->bias_colors); | |
1320 | CLEAR_HARD_REG_SET (web->prefer_colors); | |
1321 | web->reg_rtx = NULL; | |
1322 | web->stack_slot = NULL; | |
1323 | web->pattern = NULL; | |
1324 | web->alias = NULL; | |
1325 | if (web->moves) | |
1326 | abort (); | |
1327 | if (!web->useless_conflicts) | |
1328 | abort (); | |
1329 | } | |
1330 | ||
1331 | /* Insert and returns a subweb corresponding to REG into WEB (which | |
1332 | becomes its super web). It must not exist already. */ | |
1333 | ||
1334 | static struct web * | |
93bad80e | 1335 | add_subweb (struct web *web, rtx reg) |
ed8d2920 MM |
1336 | { |
1337 | struct web *w; | |
1338 | if (GET_CODE (reg) != SUBREG) | |
1339 | abort (); | |
703ad42b | 1340 | w = xmalloc (sizeof (struct web)); |
ed8d2920 MM |
1341 | /* Copy most content from parent-web. */ |
1342 | *w = *web; | |
1343 | /* And initialize the private stuff. */ | |
1344 | w->orig_x = reg; | |
1345 | w->add_hardregs = CLASS_MAX_NREGS (web->regclass, GET_MODE (reg)) - 1; | |
1346 | w->num_conflicts = 0 * w->add_hardregs; | |
1347 | w->num_defs = 0; | |
1348 | w->num_uses = 0; | |
1349 | w->dlink = NULL; | |
1350 | w->parent_web = web; | |
1351 | w->subreg_next = web->subreg_next; | |
1352 | web->subreg_next = w; | |
1353 | return w; | |
1354 | } | |
1355 | ||
1356 | /* Similar to add_subweb(), but instead of relying on a given SUBREG, | |
1357 | we have just a size and an offset of the subpart of the REG rtx. | |
1358 | In difference to add_subweb() this marks the new subweb as artificial. */ | |
1359 | ||
1360 | static struct web * | |
93bad80e | 1361 | add_subweb_2 (struct web *web, unsigned int size_word) |
ed8d2920 MM |
1362 | { |
1363 | /* To get a correct mode for the to be produced subreg, we don't want to | |
1364 | simply do a mode_for_size() for the mode_class of the whole web. | |
1365 | Suppose we deal with a CDImode web, but search for a 8 byte part. | |
1366 | Now mode_for_size() would only search in the class MODE_COMPLEX_INT | |
1367 | and would find CSImode which probably is not what we want. Instead | |
1368 | we want DImode, which is in a completely other class. For this to work | |
1369 | we instead first search the already existing subwebs, and take | |
1370 | _their_ modeclasses as base for a search for ourself. */ | |
1371 | rtx ref_rtx = (web->subreg_next ? web->subreg_next : web)->orig_x; | |
1372 | unsigned int size = BYTE_LENGTH (size_word) * BITS_PER_UNIT; | |
1373 | enum machine_mode mode; | |
1374 | mode = mode_for_size (size, GET_MODE_CLASS (GET_MODE (ref_rtx)), 0); | |
1375 | if (mode == BLKmode) | |
1376 | mode = mode_for_size (size, MODE_INT, 0); | |
1377 | if (mode == BLKmode) | |
1378 | abort (); | |
1379 | web = add_subweb (web, gen_rtx_SUBREG (mode, web->orig_x, | |
1380 | BYTE_BEGIN (size_word))); | |
1381 | web->artificial = 1; | |
1382 | return web; | |
1383 | } | |
1384 | ||
1385 | /* Initialize all the web parts we are going to need. */ | |
1386 | ||
1387 | static void | |
93bad80e | 1388 | init_web_parts (struct df *df) |
ed8d2920 MM |
1389 | { |
1390 | int regno; | |
1391 | unsigned int no; | |
1392 | num_webs = 0; | |
1393 | for (no = 0; no < df->def_id; no++) | |
1394 | { | |
1395 | if (df->defs[no]) | |
1396 | { | |
1397 | if (no < last_def_id && web_parts[no].ref != df->defs[no]) | |
1398 | abort (); | |
1399 | web_parts[no].ref = df->defs[no]; | |
1400 | /* Uplink might be set from the last iteration. */ | |
1401 | if (!web_parts[no].uplink) | |
1402 | num_webs++; | |
1403 | } | |
1404 | else | |
b57f2e10 | 1405 | /* The last iteration might have left .ref set, while df_analyze() |
ed8d2920 MM |
1406 | removed that ref (due to a removed copy insn) from the df->defs[] |
1407 | array. As we don't check for that in realloc_web_parts() | |
1408 | we do that here. */ | |
1409 | web_parts[no].ref = NULL; | |
1410 | } | |
1411 | for (no = 0; no < df->use_id; no++) | |
1412 | { | |
1413 | if (df->uses[no]) | |
1414 | { | |
1415 | if (no < last_use_id | |
1416 | && web_parts[no + df->def_id].ref != df->uses[no]) | |
1417 | abort (); | |
1418 | web_parts[no + df->def_id].ref = df->uses[no]; | |
1419 | if (!web_parts[no + df->def_id].uplink) | |
1420 | num_webs++; | |
1421 | } | |
1422 | else | |
1423 | web_parts[no + df->def_id].ref = NULL; | |
1424 | } | |
1425 | ||
1426 | /* We want to have only one web for each precolored register. */ | |
1427 | for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) | |
1428 | { | |
1429 | struct web_part *r1 = NULL; | |
1430 | struct df_link *link; | |
1431 | /* Here once was a test, if there is any DEF at all, and only then to | |
1432 | merge all the parts. This was incorrect, we really also want to have | |
1433 | only one web-part for hardregs, even if there is no explicit DEF. */ | |
1434 | /* Link together all defs... */ | |
1435 | for (link = df->regs[regno].defs; link; link = link->next) | |
1436 | if (link->ref) | |
1437 | { | |
1438 | struct web_part *r2 = &web_parts[DF_REF_ID (link->ref)]; | |
1439 | if (!r1) | |
1440 | r1 = r2; | |
1441 | else | |
1442 | r1 = union_web_parts (r1, r2); | |
1443 | } | |
1444 | /* ... and all uses. */ | |
1445 | for (link = df->regs[regno].uses; link; link = link->next) | |
1446 | if (link->ref) | |
1447 | { | |
1448 | struct web_part *r2 = &web_parts[df->def_id | |
1449 | + DF_REF_ID (link->ref)]; | |
1450 | if (!r1) | |
1451 | r1 = r2; | |
1452 | else | |
1453 | r1 = union_web_parts (r1, r2); | |
1454 | } | |
1455 | } | |
1456 | } | |
1457 | ||
1458 | /* In case we want to remember the conflict list of a WEB, before adding | |
1459 | new conflicts, we copy it here to orig_conflict_list. */ | |
1460 | ||
1461 | static void | |
93bad80e | 1462 | copy_conflict_list (struct web *web) |
ed8d2920 MM |
1463 | { |
1464 | struct conflict_link *cl; | |
1465 | if (web->orig_conflict_list || web->have_orig_conflicts) | |
1466 | abort (); | |
1467 | web->have_orig_conflicts = 1; | |
1468 | for (cl = web->conflict_list; cl; cl = cl->next) | |
1469 | { | |
1470 | struct conflict_link *ncl; | |
703ad42b | 1471 | ncl = ra_alloc (sizeof *ncl); |
ed8d2920 MM |
1472 | ncl->t = cl->t; |
1473 | ncl->sub = NULL; | |
1474 | ncl->next = web->orig_conflict_list; | |
1475 | web->orig_conflict_list = ncl; | |
1476 | if (cl->sub) | |
1477 | { | |
1478 | struct sub_conflict *sl, *nsl; | |
1479 | for (sl = cl->sub; sl; sl = sl->next) | |
1480 | { | |
703ad42b | 1481 | nsl = ra_alloc (sizeof *nsl); |
ed8d2920 MM |
1482 | nsl->s = sl->s; |
1483 | nsl->t = sl->t; | |
1484 | nsl->next = ncl->sub; | |
1485 | ncl->sub = nsl; | |
1486 | } | |
1487 | } | |
1488 | } | |
1489 | } | |
1490 | ||
1491 | /* Possibly add an edge from web FROM to TO marking a conflict between | |
1492 | those two. This is one half of marking a complete conflict, which notes | |
1493 | in FROM, that TO is a conflict. Adding TO to FROM's conflicts might | |
d55d8fc7 | 1494 | make other conflicts superfluous, because the current TO overlaps some web |
ed8d2920 MM |
1495 | already being in conflict with FROM. In this case the smaller webs are |
1496 | deleted from the conflict list. Likewise if TO is overlapped by a web | |
1497 | already in the list, it isn't added at all. Note, that this can only | |
1498 | happen, if SUBREG webs are involved. */ | |
1499 | ||
1500 | static void | |
93bad80e | 1501 | add_conflict_edge (struct web *from, struct web *to) |
ed8d2920 MM |
1502 | { |
1503 | if (from->type != PRECOLORED) | |
1504 | { | |
1505 | struct web *pfrom = find_web_for_subweb (from); | |
1506 | struct web *pto = find_web_for_subweb (to); | |
1507 | struct sub_conflict *sl; | |
1508 | struct conflict_link *cl = pfrom->conflict_list; | |
1509 | int may_delete = 1; | |
1510 | ||
1511 | /* This can happen when subwebs of one web conflict with each | |
1512 | other. In live_out_1() we created such conflicts between yet | |
1513 | undefined webparts and defs of parts which didn't overlap with the | |
1514 | undefined bits. Then later they nevertheless could have merged into | |
1515 | one web, and then we land here. */ | |
1516 | if (pfrom == pto) | |
1517 | return; | |
1518 | if (remember_conflicts && !pfrom->have_orig_conflicts) | |
1519 | copy_conflict_list (pfrom); | |
1520 | if (!TEST_BIT (sup_igraph, (pfrom->id * num_webs + pto->id))) | |
1521 | { | |
703ad42b | 1522 | cl = ra_alloc (sizeof (*cl)); |
ed8d2920 MM |
1523 | cl->t = pto; |
1524 | cl->sub = NULL; | |
1525 | cl->next = pfrom->conflict_list; | |
1526 | pfrom->conflict_list = cl; | |
1527 | if (pto->type != SELECT && pto->type != COALESCED) | |
1528 | pfrom->num_conflicts += 1 + pto->add_hardregs; | |
1529 | SET_BIT (sup_igraph, (pfrom->id * num_webs + pto->id)); | |
1530 | may_delete = 0; | |
1531 | } | |
1532 | else | |
1533 | /* We don't need to test for cl==NULL, because at this point | |
1534 | a cl with cl->t==pto is guaranteed to exist. */ | |
1535 | while (cl->t != pto) | |
1536 | cl = cl->next; | |
1537 | if (pfrom != from || pto != to) | |
1538 | { | |
1539 | /* This is a subconflict which should be added. | |
1540 | If we inserted cl in this invocation, we really need to add this | |
1541 | subconflict. If we did _not_ add it here, we only add the | |
1542 | subconflict, if cl already had subconflicts, because otherwise | |
1543 | this indicated, that the whole webs already conflict, which | |
1544 | means we are not interested in this subconflict. */ | |
1545 | if (!may_delete || cl->sub != NULL) | |
1546 | { | |
703ad42b | 1547 | sl = ra_alloc (sizeof (*sl)); |
ed8d2920 MM |
1548 | sl->s = from; |
1549 | sl->t = to; | |
1550 | sl->next = cl->sub; | |
1551 | cl->sub = sl; | |
1552 | } | |
1553 | } | |
1554 | else | |
1555 | /* pfrom == from && pto == to means, that we are not interested | |
1556 | anymore in the subconflict list for this pair, because anyway | |
1557 | the whole webs conflict. */ | |
1558 | cl->sub = NULL; | |
1559 | } | |
1560 | } | |
1561 | ||
1562 | /* Record a conflict between two webs, if we haven't recorded it | |
1563 | already. */ | |
1564 | ||
1565 | void | |
93bad80e | 1566 | record_conflict (struct web *web1, struct web *web2) |
ed8d2920 MM |
1567 | { |
1568 | unsigned int id1 = web1->id, id2 = web2->id; | |
1569 | unsigned int index = igraph_index (id1, id2); | |
1570 | /* Trivial non-conflict or already recorded conflict. */ | |
1571 | if (web1 == web2 || TEST_BIT (igraph, index)) | |
1572 | return; | |
1573 | if (id1 == id2) | |
1574 | abort (); | |
1575 | /* As fixed_regs are no targets for allocation, conflicts with them | |
1576 | are pointless. */ | |
1577 | if ((web1->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web1->regno]) | |
1578 | || (web2->regno < FIRST_PSEUDO_REGISTER && fixed_regs[web2->regno])) | |
1579 | return; | |
1580 | /* Conflicts with hardregs, which are not even a candidate | |
1581 | for this pseudo are also pointless. */ | |
1582 | if ((web1->type == PRECOLORED | |
1583 | && ! TEST_HARD_REG_BIT (web2->usable_regs, web1->regno)) | |
1584 | || (web2->type == PRECOLORED | |
1585 | && ! TEST_HARD_REG_BIT (web1->usable_regs, web2->regno))) | |
1586 | return; | |
1587 | /* Similar if the set of possible hardregs don't intersect. This iteration | |
1588 | those conflicts are useless (and would make num_conflicts wrong, because | |
1589 | num_freedom is calculated from the set of possible hardregs). | |
1590 | But in presence of spilling and incremental building of the graph we | |
1591 | need to note all uses of webs conflicting with the spilled ones. | |
1592 | Because the set of possible hardregs can change in the next round for | |
1593 | spilled webs, we possibly have then conflicts with webs which would | |
1594 | be excluded now (because then hardregs intersect). But we actually | |
1595 | need to check those uses, and to get hold of them, we need to remember | |
1596 | also webs conflicting with this one, although not conflicting in this | |
1597 | round because of non-intersecting hardregs. */ | |
1598 | if (web1->type != PRECOLORED && web2->type != PRECOLORED | |
1599 | && ! hard_regs_intersect_p (&web1->usable_regs, &web2->usable_regs)) | |
1600 | { | |
1601 | struct web *p1 = find_web_for_subweb (web1); | |
1602 | struct web *p2 = find_web_for_subweb (web2); | |
1603 | /* We expect these to be rare enough to justify bitmaps. And because | |
1604 | we have only a special use for it, we note only the superwebs. */ | |
1605 | bitmap_set_bit (p1->useless_conflicts, p2->id); | |
1606 | bitmap_set_bit (p2->useless_conflicts, p1->id); | |
1607 | return; | |
1608 | } | |
1609 | SET_BIT (igraph, index); | |
1610 | add_conflict_edge (web1, web2); | |
1611 | add_conflict_edge (web2, web1); | |
1612 | } | |
1613 | ||
1614 | /* For each web W this produces the missing subwebs Wx, such that it's | |
1615 | possible to exactly specify (W-Wy) for all already existing subwebs Wy. */ | |
1616 | ||
1617 | static void | |
93bad80e | 1618 | build_inverse_webs (struct web *web) |
ed8d2920 MM |
1619 | { |
1620 | struct web *sweb = web->subreg_next; | |
1621 | unsigned HOST_WIDE_INT undef; | |
1622 | ||
1623 | undef = rtx_to_undefined (web->orig_x); | |
1624 | for (; sweb; sweb = sweb->subreg_next) | |
1625 | /* Only create inverses of non-artificial webs. */ | |
1626 | if (!sweb->artificial) | |
1627 | { | |
1628 | unsigned HOST_WIDE_INT bits; | |
1629 | bits = undef & ~ rtx_to_undefined (sweb->orig_x); | |
1630 | while (bits) | |
1631 | { | |
1632 | unsigned int size_word = undef_to_size_word (web->orig_x, &bits); | |
1633 | if (!find_subweb_2 (web, size_word)) | |
1634 | add_subweb_2 (web, size_word); | |
1635 | } | |
1636 | } | |
1637 | } | |
1638 | ||
1639 | /* Copies the content of WEB to a new one, and link it into WL. | |
1640 | Used for consistency checking. */ | |
1641 | ||
1642 | static void | |
93bad80e | 1643 | copy_web (struct web *web, struct web_link **wl) |
ed8d2920 | 1644 | { |
703ad42b KG |
1645 | struct web *cweb = xmalloc (sizeof *cweb); |
1646 | struct web_link *link = ra_alloc (sizeof *link); | |
ed8d2920 MM |
1647 | link->next = *wl; |
1648 | *wl = link; | |
1649 | link->web = cweb; | |
1650 | *cweb = *web; | |
1651 | } | |
1652 | ||
1653 | /* Given a list of webs LINK, compare the content of the webs therein | |
1654 | with the global webs of the same ID. For consistency checking. */ | |
1655 | ||
1656 | static void | |
93bad80e | 1657 | compare_and_free_webs (struct web_link **link) |
ed8d2920 MM |
1658 | { |
1659 | struct web_link *wl; | |
1660 | for (wl = *link; wl; wl = wl->next) | |
1661 | { | |
1662 | struct web *web1 = wl->web; | |
1663 | struct web *web2 = ID2WEB (web1->id); | |
1664 | if (web1->regno != web2->regno | |
ed8d2920 MM |
1665 | || web1->mode_changed != web2->mode_changed |
1666 | || !rtx_equal_p (web1->orig_x, web2->orig_x) | |
1667 | || web1->type != web2->type | |
1668 | /* Only compare num_defs/num_uses with non-hardreg webs. | |
1669 | E.g. the number of uses of the framepointer changes due to | |
1670 | inserting spill code. */ | |
d58f6584 DJ |
1671 | || (web1->type != PRECOLORED |
1672 | && (web1->num_uses != web2->num_uses | |
1673 | || web1->num_defs != web2->num_defs)) | |
1674 | /* Similarly, if the framepointer was unreferenced originally | |
3dc575ff | 1675 | but we added spills, these fields may not match. */ |
d58f6584 DJ |
1676 | || (web1->type != PRECOLORED |
1677 | && web1->crosses_call != web2->crosses_call) | |
1678 | || (web1->type != PRECOLORED | |
1679 | && web1->live_over_abnormal != web2->live_over_abnormal)) | |
ed8d2920 MM |
1680 | abort (); |
1681 | if (web1->type != PRECOLORED) | |
1682 | { | |
1683 | unsigned int i; | |
1684 | for (i = 0; i < web1->num_defs; i++) | |
1685 | if (web1->defs[i] != web2->defs[i]) | |
1686 | abort (); | |
1687 | for (i = 0; i < web1->num_uses; i++) | |
1688 | if (web1->uses[i] != web2->uses[i]) | |
1689 | abort (); | |
1690 | } | |
1691 | if (web1->type == PRECOLORED) | |
1692 | { | |
1693 | if (web1->defs) | |
1694 | free (web1->defs); | |
1695 | if (web1->uses) | |
1696 | free (web1->uses); | |
1697 | } | |
1698 | free (web1); | |
1699 | } | |
1700 | *link = NULL; | |
1701 | } | |
1702 | ||
1703 | /* Setup and fill uses[] and defs[] arrays of the webs. */ | |
1704 | ||
1705 | static void | |
93bad80e | 1706 | init_webs_defs_uses (void) |
ed8d2920 MM |
1707 | { |
1708 | struct dlist *d; | |
1709 | for (d = WEBS(INITIAL); d; d = d->next) | |
1710 | { | |
1711 | struct web *web = DLIST_WEB (d); | |
1712 | unsigned int def_i, use_i; | |
1713 | struct df_link *link; | |
1714 | if (web->old_web) | |
1715 | continue; | |
1716 | if (web->type == PRECOLORED) | |
1717 | { | |
1718 | web->num_defs = web->num_uses = 0; | |
1719 | continue; | |
1720 | } | |
1721 | if (web->num_defs) | |
703ad42b | 1722 | web->defs = xmalloc (web->num_defs * sizeof (web->defs[0])); |
ed8d2920 | 1723 | if (web->num_uses) |
703ad42b | 1724 | web->uses = xmalloc (web->num_uses * sizeof (web->uses[0])); |
ed8d2920 MM |
1725 | def_i = use_i = 0; |
1726 | for (link = web->temp_refs; link; link = link->next) | |
1727 | { | |
1728 | if (DF_REF_REG_DEF_P (link->ref)) | |
1729 | web->defs[def_i++] = link->ref; | |
1730 | else | |
1731 | web->uses[use_i++] = link->ref; | |
1732 | } | |
1733 | web->temp_refs = NULL; | |
1734 | if (def_i != web->num_defs || use_i != web->num_uses) | |
1735 | abort (); | |
1736 | } | |
1737 | } | |
1738 | ||
1739 | /* Called by parts_to_webs(). This creates (or recreates) the webs (and | |
1740 | subwebs) from web parts, gives them IDs (only to super webs), and sets | |
1741 | up use2web and def2web arrays. */ | |
1742 | ||
1743 | static unsigned int | |
93bad80e SB |
1744 | parts_to_webs_1 (struct df *df, struct web_link **copy_webs, |
1745 | struct df_link *all_refs) | |
ed8d2920 MM |
1746 | { |
1747 | unsigned int i; | |
1748 | unsigned int webnum; | |
1749 | unsigned int def_id = df->def_id; | |
1750 | unsigned int use_id = df->use_id; | |
1751 | struct web_part *wp_first_use = &web_parts[def_id]; | |
1752 | ||
1753 | /* For each root web part: create and initialize a new web, | |
1754 | setup def2web[] and use2web[] for all defs and uses, and | |
1755 | id2web for all new webs. */ | |
1756 | ||
1757 | webnum = 0; | |
1758 | for (i = 0; i < def_id + use_id; i++) | |
1759 | { | |
d950dee3 | 1760 | struct web *subweb, *web = 0; /* Initialize web to silence warnings. */ |
ed8d2920 MM |
1761 | struct web_part *wp = &web_parts[i]; |
1762 | struct ref *ref = wp->ref; | |
1763 | unsigned int ref_id; | |
1764 | rtx reg; | |
1765 | if (!ref) | |
1766 | continue; | |
1767 | ref_id = i; | |
1768 | if (i >= def_id) | |
1769 | ref_id -= def_id; | |
1770 | all_refs[i].ref = ref; | |
1771 | reg = DF_REF_REG (ref); | |
1772 | if (! wp->uplink) | |
1773 | { | |
1774 | /* If we have a web part root, create a new web. */ | |
533c4863 | 1775 | unsigned int newid = ~(unsigned)0; |
ed8d2920 MM |
1776 | unsigned int old_web = 0; |
1777 | ||
1778 | /* In the first pass, there are no old webs, so unconditionally | |
1779 | allocate a new one. */ | |
1780 | if (ra_pass == 1) | |
1781 | { | |
703ad42b | 1782 | web = xmalloc (sizeof (struct web)); |
ed8d2920 MM |
1783 | newid = last_num_webs++; |
1784 | init_one_web (web, GET_CODE (reg) == SUBREG | |
1785 | ? SUBREG_REG (reg) : reg); | |
1786 | } | |
1787 | /* Otherwise, we look for an old web. */ | |
1788 | else | |
1789 | { | |
1790 | /* Remember, that use2web == def2web + def_id. | |
1791 | Ergo is def2web[i] == use2web[i - def_id] for i >= def_id. | |
1792 | So we only need to look into def2web[] array. | |
1793 | Try to look at the web, which formerly belonged to this | |
1794 | def (or use). */ | |
1795 | web = def2web[i]; | |
1796 | /* Or which belonged to this hardreg. */ | |
1797 | if (!web && DF_REF_REGNO (ref) < FIRST_PSEUDO_REGISTER) | |
1798 | web = hardreg2web[DF_REF_REGNO (ref)]; | |
1799 | if (web) | |
1800 | { | |
1801 | /* If we found one, reuse it. */ | |
1802 | web = find_web_for_subweb (web); | |
1803 | remove_list (web->dlink, &WEBS(INITIAL)); | |
1804 | old_web = 1; | |
1805 | copy_web (web, copy_webs); | |
1806 | } | |
1807 | else | |
1808 | { | |
1809 | /* Otherwise use a new one. First from the free list. */ | |
1810 | if (WEBS(FREE)) | |
1811 | web = DLIST_WEB (pop_list (&WEBS(FREE))); | |
1812 | else | |
1813 | { | |
1814 | /* Else allocate a new one. */ | |
703ad42b | 1815 | web = xmalloc (sizeof (struct web)); |
ed8d2920 MM |
1816 | newid = last_num_webs++; |
1817 | } | |
1818 | } | |
1819 | /* The id is zeroed in init_one_web(). */ | |
533c4863 | 1820 | if (newid == ~(unsigned)0) |
ed8d2920 MM |
1821 | newid = web->id; |
1822 | if (old_web) | |
1823 | reinit_one_web (web, GET_CODE (reg) == SUBREG | |
1824 | ? SUBREG_REG (reg) : reg); | |
1825 | else | |
1826 | init_one_web (web, GET_CODE (reg) == SUBREG | |
1827 | ? SUBREG_REG (reg) : reg); | |
1828 | web->old_web = (old_web && web->type != PRECOLORED) ? 1 : 0; | |
1829 | } | |
1830 | web->span_deaths = wp->spanned_deaths; | |
1831 | web->crosses_call = wp->crosses_call; | |
1832 | web->id = newid; | |
1833 | web->temp_refs = NULL; | |
1834 | webnum++; | |
1835 | if (web->regno < FIRST_PSEUDO_REGISTER && !hardreg2web[web->regno]) | |
1836 | hardreg2web[web->regno] = web; | |
1837 | else if (web->regno < FIRST_PSEUDO_REGISTER | |
1838 | && hardreg2web[web->regno] != web) | |
1839 | abort (); | |
1840 | } | |
1841 | ||
1842 | /* If this reference already had a web assigned, we are done. | |
1843 | This test better is equivalent to the web being an old web. | |
1844 | Otherwise something is screwed. (This is tested) */ | |
1845 | if (def2web[i] != NULL) | |
1846 | { | |
1847 | web = def2web[i]; | |
1848 | web = find_web_for_subweb (web); | |
1849 | /* But if this ref includes a mode change, or was a use live | |
1850 | over an abnormal call, set appropriate flags in the web. */ | |
1851 | if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0 | |
1852 | && web->regno >= FIRST_PSEUDO_REGISTER) | |
1853 | web->mode_changed = 1; | |
50aac998 MM |
1854 | if ((DF_REF_FLAGS (ref) & DF_REF_STRIPPED) != 0 |
1855 | && web->regno >= FIRST_PSEUDO_REGISTER) | |
1856 | web->subreg_stripped = 1; | |
ed8d2920 MM |
1857 | if (i >= def_id |
1858 | && TEST_BIT (live_over_abnormal, ref_id)) | |
1859 | web->live_over_abnormal = 1; | |
1860 | /* And check, that it's not a newly allocated web. This would be | |
1861 | an inconsistency. */ | |
1862 | if (!web->old_web || web->type == PRECOLORED) | |
1863 | abort (); | |
1864 | continue; | |
1865 | } | |
1866 | /* In case this was no web part root, we need to initialize WEB | |
1867 | from the ref2web array belonging to the root. */ | |
1868 | if (wp->uplink) | |
1869 | { | |
1870 | struct web_part *rwp = find_web_part (wp); | |
1871 | unsigned int j = DF_REF_ID (rwp->ref); | |
1872 | if (rwp < wp_first_use) | |
1873 | web = def2web[j]; | |
1874 | else | |
1875 | web = use2web[j]; | |
1876 | web = find_web_for_subweb (web); | |
1877 | } | |
1878 | ||
1879 | /* Remember all references for a web in a single linked list. */ | |
1880 | all_refs[i].next = web->temp_refs; | |
1881 | web->temp_refs = &all_refs[i]; | |
1882 | ||
1883 | /* And the test, that if def2web[i] was NULL above, that we are _not_ | |
1884 | an old web. */ | |
1885 | if (web->old_web && web->type != PRECOLORED) | |
1886 | abort (); | |
1887 | ||
1888 | /* Possible create a subweb, if this ref was a subreg. */ | |
1889 | if (GET_CODE (reg) == SUBREG) | |
1890 | { | |
1891 | subweb = find_subweb (web, reg); | |
1892 | if (!subweb) | |
1893 | { | |
1894 | subweb = add_subweb (web, reg); | |
1895 | if (web->old_web) | |
1896 | abort (); | |
1897 | } | |
1898 | } | |
1899 | else | |
1900 | subweb = web; | |
1901 | ||
1902 | /* And look, if the ref involves an invalid mode change. */ | |
1903 | if ((DF_REF_FLAGS (ref) & DF_REF_MODE_CHANGE) != 0 | |
1904 | && web->regno >= FIRST_PSEUDO_REGISTER) | |
1905 | web->mode_changed = 1; | |
50aac998 MM |
1906 | if ((DF_REF_FLAGS (ref) & DF_REF_STRIPPED) != 0 |
1907 | && web->regno >= FIRST_PSEUDO_REGISTER) | |
1908 | web->subreg_stripped = 1; | |
ed8d2920 MM |
1909 | |
1910 | /* Setup def2web, or use2web, and increment num_defs or num_uses. */ | |
1911 | if (i < def_id) | |
1912 | { | |
1913 | /* Some sanity checks. */ | |
1914 | if (ra_pass > 1) | |
1915 | { | |
1916 | struct web *compare = def2web[i]; | |
1917 | if (i < last_def_id) | |
1918 | { | |
1919 | if (web->old_web && compare != subweb) | |
1920 | abort (); | |
1921 | } | |
1922 | if (!web->old_web && compare) | |
1923 | abort (); | |
1924 | if (compare && compare != subweb) | |
1925 | abort (); | |
1926 | } | |
1927 | def2web[i] = subweb; | |
1928 | web->num_defs++; | |
1929 | } | |
1930 | else | |
1931 | { | |
1932 | if (ra_pass > 1) | |
1933 | { | |
1934 | struct web *compare = use2web[ref_id]; | |
1935 | if (ref_id < last_use_id) | |
1936 | { | |
1937 | if (web->old_web && compare != subweb) | |
1938 | abort (); | |
1939 | } | |
1940 | if (!web->old_web && compare) | |
1941 | abort (); | |
1942 | if (compare && compare != subweb) | |
1943 | abort (); | |
1944 | } | |
1945 | use2web[ref_id] = subweb; | |
1946 | web->num_uses++; | |
1947 | if (TEST_BIT (live_over_abnormal, ref_id)) | |
1948 | web->live_over_abnormal = 1; | |
1949 | } | |
1950 | } | |
1951 | ||
1952 | /* We better now have exactly as many webs as we had web part roots. */ | |
1953 | if (webnum != num_webs) | |
1954 | abort (); | |
1955 | ||
1956 | return webnum; | |
1957 | } | |
1958 | ||
1959 | /* This builds full webs out of web parts, without relating them to each | |
1960 | other (i.e. without creating the conflict edges). */ | |
1961 | ||
1962 | static void | |
93bad80e | 1963 | parts_to_webs (struct df *df) |
ed8d2920 MM |
1964 | { |
1965 | unsigned int i; | |
1966 | unsigned int webnum; | |
1967 | struct web_link *copy_webs = NULL; | |
1968 | struct dlist *d; | |
1969 | struct df_link *all_refs; | |
1970 | num_subwebs = 0; | |
1971 | ||
1972 | /* First build webs and ordinary subwebs. */ | |
703ad42b | 1973 | all_refs = xcalloc (df->def_id + df->use_id, sizeof (all_refs[0])); |
ed8d2920 MM |
1974 | webnum = parts_to_webs_1 (df, ©_webs, all_refs); |
1975 | ||
1976 | /* Setup the webs for hardregs which are still missing (weren't | |
1977 | mentioned in the code). */ | |
1978 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
1979 | if (!hardreg2web[i]) | |
1980 | { | |
703ad42b | 1981 | struct web *web = xmalloc (sizeof (struct web)); |
ed8d2920 MM |
1982 | init_one_web (web, gen_rtx_REG (reg_raw_mode[i], i)); |
1983 | web->id = last_num_webs++; | |
1984 | hardreg2web[web->regno] = web; | |
1985 | } | |
1986 | num_webs = last_num_webs; | |
1987 | ||
1988 | /* Now create all artificial subwebs, i.e. those, which do | |
1989 | not correspond to a real subreg in the current function's RTL, but | |
1990 | which nevertheless is a target of a conflict. | |
1991 | XXX we need to merge this loop with the one above, which means, we need | |
1992 | a way to later override the artificiality. Beware: currently | |
1993 | add_subweb_2() relies on the existence of normal subwebs for deducing | |
1994 | a sane mode to use for the artificial subwebs. */ | |
1995 | for (i = 0; i < df->def_id + df->use_id; i++) | |
1996 | { | |
1997 | struct web_part *wp = &web_parts[i]; | |
1998 | struct tagged_conflict *cl; | |
1999 | struct web *web; | |
2000 | if (wp->uplink || !wp->ref) | |
2001 | { | |
2002 | if (wp->sub_conflicts) | |
2003 | abort (); | |
2004 | continue; | |
2005 | } | |
2006 | web = def2web[i]; | |
2007 | web = find_web_for_subweb (web); | |
2008 | for (cl = wp->sub_conflicts; cl; cl = cl->next) | |
2009 | if (!find_subweb_2 (web, cl->size_word)) | |
2010 | add_subweb_2 (web, cl->size_word); | |
2011 | } | |
2012 | ||
2013 | /* And now create artificial subwebs needed for representing the inverse | |
2014 | of some subwebs. This also gives IDs to all subwebs. */ | |
2015 | webnum = last_num_webs; | |
2016 | for (d = WEBS(INITIAL); d; d = d->next) | |
2017 | { | |
2018 | struct web *web = DLIST_WEB (d); | |
2019 | if (web->subreg_next) | |
2020 | { | |
2021 | struct web *sweb; | |
2022 | build_inverse_webs (web); | |
2023 | for (sweb = web->subreg_next; sweb; sweb = sweb->subreg_next) | |
2024 | sweb->id = webnum++; | |
2025 | } | |
2026 | } | |
2027 | ||
2028 | /* Now that everyone has an ID, we can setup the id2web array. */ | |
703ad42b | 2029 | id2web = xcalloc (webnum, sizeof (id2web[0])); |
ed8d2920 MM |
2030 | for (d = WEBS(INITIAL); d; d = d->next) |
2031 | { | |
2032 | struct web *web = DLIST_WEB (d); | |
2033 | ID2WEB (web->id) = web; | |
2034 | for (web = web->subreg_next; web; web = web->subreg_next) | |
2035 | ID2WEB (web->id) = web; | |
2036 | } | |
2037 | num_subwebs = webnum - last_num_webs; | |
2038 | num_allwebs = num_webs + num_subwebs; | |
2039 | num_webs += num_subwebs; | |
2040 | ||
2041 | /* Allocate and clear the conflict graph bitmaps. */ | |
2042 | igraph = sbitmap_alloc (num_webs * num_webs / 2); | |
2043 | sup_igraph = sbitmap_alloc (num_webs * num_webs); | |
2044 | sbitmap_zero (igraph); | |
2045 | sbitmap_zero (sup_igraph); | |
2046 | ||
d55d8fc7 | 2047 | /* Distribute the references to their webs. */ |
ed8d2920 MM |
2048 | init_webs_defs_uses (); |
2049 | /* And do some sanity checks if old webs, and those recreated from the | |
2050 | really are the same. */ | |
2051 | compare_and_free_webs (©_webs); | |
2052 | free (all_refs); | |
2053 | } | |
2054 | ||
2055 | /* This deletes all conflicts to and from webs which need to be renewed | |
2056 | in this pass of the allocator, i.e. those which were spilled in the | |
2057 | last pass. Furthermore it also rebuilds the bitmaps for the remaining | |
2058 | conflicts. */ | |
2059 | ||
2060 | static void | |
93bad80e | 2061 | reset_conflicts (void) |
ed8d2920 MM |
2062 | { |
2063 | unsigned int i; | |
2064 | bitmap newwebs = BITMAP_XMALLOC (); | |
2065 | for (i = 0; i < num_webs - num_subwebs; i++) | |
2066 | { | |
2067 | struct web *web = ID2WEB (i); | |
2068 | /* Hardreg webs and non-old webs are new webs (which | |
2069 | need rebuilding). */ | |
2070 | if (web->type == PRECOLORED || !web->old_web) | |
2071 | bitmap_set_bit (newwebs, web->id); | |
2072 | } | |
2073 | ||
2074 | for (i = 0; i < num_webs - num_subwebs; i++) | |
2075 | { | |
2076 | struct web *web = ID2WEB (i); | |
2077 | struct conflict_link *cl; | |
2078 | struct conflict_link **pcl; | |
2079 | pcl = &(web->conflict_list); | |
2080 | ||
2081 | /* First restore the conflict list to be like it was before | |
2082 | coalescing. */ | |
2083 | if (web->have_orig_conflicts) | |
2084 | { | |
2085 | web->conflict_list = web->orig_conflict_list; | |
2086 | web->orig_conflict_list = NULL; | |
2087 | } | |
2088 | if (web->orig_conflict_list) | |
2089 | abort (); | |
2090 | ||
2091 | /* New non-precolored webs, have no conflict list. */ | |
2092 | if (web->type != PRECOLORED && !web->old_web) | |
2093 | { | |
2094 | *pcl = NULL; | |
2095 | /* Useless conflicts will be rebuilt completely. But check | |
d55d8fc7 | 2096 | for cleanliness, as the web might have come from the |
ed8d2920 MM |
2097 | free list. */ |
2098 | if (bitmap_first_set_bit (web->useless_conflicts) >= 0) | |
2099 | abort (); | |
2100 | } | |
2101 | else | |
2102 | { | |
2103 | /* Useless conflicts with new webs will be rebuilt if they | |
2104 | are still there. */ | |
2105 | bitmap_operation (web->useless_conflicts, web->useless_conflicts, | |
2106 | newwebs, BITMAP_AND_COMPL); | |
2107 | /* Go through all conflicts, and retain those to old webs. */ | |
2108 | for (cl = web->conflict_list; cl; cl = cl->next) | |
2109 | { | |
2110 | if (cl->t->old_web || cl->t->type == PRECOLORED) | |
2111 | { | |
2112 | *pcl = cl; | |
2113 | pcl = &(cl->next); | |
2114 | ||
2115 | /* Also restore the entries in the igraph bitmaps. */ | |
2116 | web->num_conflicts += 1 + cl->t->add_hardregs; | |
2117 | SET_BIT (sup_igraph, (web->id * num_webs + cl->t->id)); | |
2118 | /* No subconflicts mean full webs conflict. */ | |
2119 | if (!cl->sub) | |
2120 | SET_BIT (igraph, igraph_index (web->id, cl->t->id)); | |
2121 | else | |
2122 | /* Else only the parts in cl->sub must be in the | |
2123 | bitmap. */ | |
2124 | { | |
2125 | struct sub_conflict *sl; | |
2126 | for (sl = cl->sub; sl; sl = sl->next) | |
2127 | SET_BIT (igraph, igraph_index (sl->s->id, sl->t->id)); | |
2128 | } | |
2129 | } | |
2130 | } | |
2131 | *pcl = NULL; | |
2132 | } | |
2133 | web->have_orig_conflicts = 0; | |
2134 | } | |
2135 | BITMAP_XFREE (newwebs); | |
2136 | } | |
2137 | ||
2138 | /* For each web check it's num_conflicts member against that | |
2139 | number, as calculated from scratch from all neighbors. */ | |
2140 | ||
533c4863 | 2141 | #if 0 |
ed8d2920 | 2142 | static void |
93bad80e | 2143 | check_conflict_numbers (void) |
ed8d2920 MM |
2144 | { |
2145 | unsigned int i; | |
2146 | for (i = 0; i < num_webs; i++) | |
2147 | { | |
2148 | struct web *web = ID2WEB (i); | |
2149 | int new_conf = 0 * web->add_hardregs; | |
2150 | struct conflict_link *cl; | |
2151 | for (cl = web->conflict_list; cl; cl = cl->next) | |
2152 | if (cl->t->type != SELECT && cl->t->type != COALESCED) | |
2153 | new_conf += 1 + cl->t->add_hardregs; | |
2154 | if (web->type != PRECOLORED && new_conf != web->num_conflicts) | |
2155 | abort (); | |
2156 | } | |
2157 | } | |
533c4863 | 2158 | #endif |
ed8d2920 MM |
2159 | |
2160 | /* Convert the conflicts between web parts to conflicts between full webs. | |
2161 | ||
2162 | This can't be done in parts_to_webs(), because for recording conflicts | |
2163 | between webs we need to know their final usable_regs set, which is used | |
2164 | to discard non-conflicts (between webs having no hard reg in common). | |
2165 | But this is set for spill temporaries only after the webs itself are | |
2166 | built. Until then the usable_regs set is based on the pseudo regno used | |
2167 | in this web, which may contain far less registers than later determined. | |
2168 | This would result in us loosing conflicts (due to record_conflict() | |
2169 | thinking that a web can only be allocated to the current usable_regs, | |
2170 | whereas later this is extended) leading to colorings, where some regs which | |
2171 | in reality conflict get the same color. */ | |
2172 | ||
2173 | static void | |
93bad80e | 2174 | conflicts_between_webs (struct df *df) |
ed8d2920 MM |
2175 | { |
2176 | unsigned int i; | |
533c4863 | 2177 | #ifdef STACK_REGS |
ed8d2920 | 2178 | struct dlist *d; |
533c4863 | 2179 | #endif |
ed8d2920 MM |
2180 | bitmap ignore_defs = BITMAP_XMALLOC (); |
2181 | unsigned int have_ignored; | |
703ad42b | 2182 | unsigned int *pass_cache = xcalloc (num_webs, sizeof (int)); |
ed8d2920 MM |
2183 | unsigned int pass = 0; |
2184 | ||
2185 | if (ra_pass > 1) | |
2186 | reset_conflicts (); | |
2187 | ||
2188 | /* It is possible, that in the conflict bitmaps still some defs I are noted, | |
2189 | which have web_parts[I].ref being NULL. This can happen, when from the | |
2190 | last iteration the conflict bitmap for this part wasn't deleted, but a | |
2191 | conflicting move insn was removed. It's DEF is still in the conflict | |
2192 | bitmap, but it doesn't exist anymore in df->defs. To not have to check | |
2193 | it in the tight loop below, we instead remember the ID's of them in a | |
2194 | bitmap, and loop only over IDs which are not in it. */ | |
2195 | for (i = 0; i < df->def_id; i++) | |
2196 | if (web_parts[i].ref == NULL) | |
2197 | bitmap_set_bit (ignore_defs, i); | |
2198 | have_ignored = (bitmap_first_set_bit (ignore_defs) >= 0); | |
2199 | ||
2200 | /* Now record all conflicts between webs. Note that we only check | |
2201 | the conflict bitmaps of all defs. Conflict bitmaps are only in | |
2202 | webpart roots. If they are in uses, those uses are roots, which | |
2203 | means, that this is an uninitialized web, whose conflicts | |
2204 | don't matter. Nevertheless for hardregs we also need to check uses. | |
2205 | E.g. hardregs used for argument passing have no DEF in the RTL, | |
2206 | but if they have uses, they indeed conflict with all DEFs they | |
2207 | overlap. */ | |
2208 | for (i = 0; i < df->def_id + df->use_id; i++) | |
2209 | { | |
2210 | struct tagged_conflict *cl = web_parts[i].sub_conflicts; | |
2211 | struct web *supweb1; | |
2212 | if (!cl | |
2213 | || (i >= df->def_id | |
2214 | && DF_REF_REGNO (web_parts[i].ref) >= FIRST_PSEUDO_REGISTER)) | |
2215 | continue; | |
2216 | supweb1 = def2web[i]; | |
2217 | supweb1 = find_web_for_subweb (supweb1); | |
2218 | for (; cl; cl = cl->next) | |
2219 | if (cl->conflicts) | |
2220 | { | |
2221 | int j; | |
2222 | struct web *web1 = find_subweb_2 (supweb1, cl->size_word); | |
2223 | if (have_ignored) | |
2224 | bitmap_operation (cl->conflicts, cl->conflicts, ignore_defs, | |
2225 | BITMAP_AND_COMPL); | |
2226 | /* We reduce the number of calls to record_conflict() with this | |
2227 | pass thing. record_conflict() itself also has some early-out | |
2228 | optimizations, but here we can use the special properties of | |
2229 | the loop (constant web1) to reduce that even more. | |
2230 | We once used an sbitmap of already handled web indices, | |
2231 | but sbitmaps are slow to clear and bitmaps are slow to | |
2232 | set/test. The current approach needs more memory, but | |
2233 | locality is large. */ | |
2234 | pass++; | |
2235 | ||
2236 | /* Note, that there are only defs in the conflicts bitset. */ | |
2237 | EXECUTE_IF_SET_IN_BITMAP ( | |
2238 | cl->conflicts, 0, j, | |
2239 | { | |
2240 | struct web *web2 = def2web[j]; | |
2241 | unsigned int id2 = web2->id; | |
2242 | if (pass_cache[id2] != pass) | |
2243 | { | |
2244 | pass_cache[id2] = pass; | |
2245 | record_conflict (web1, web2); | |
2246 | } | |
2247 | }); | |
2248 | } | |
2249 | } | |
2250 | ||
2251 | free (pass_cache); | |
2252 | BITMAP_XFREE (ignore_defs); | |
2253 | ||
2254 | #ifdef STACK_REGS | |
2255 | /* Pseudos can't go in stack regs if they are live at the beginning of | |
2256 | a block that is reached by an abnormal edge. */ | |
2257 | for (d = WEBS(INITIAL); d; d = d->next) | |
2258 | { | |
2259 | struct web *web = DLIST_WEB (d); | |
2260 | int j; | |
2261 | if (web->live_over_abnormal) | |
2262 | for (j = FIRST_STACK_REG; j <= LAST_STACK_REG; j++) | |
2263 | record_conflict (web, hardreg2web[j]); | |
2264 | } | |
2265 | #endif | |
2266 | } | |
2267 | ||
2268 | /* Remember that a web was spilled, and change some characteristics | |
2269 | accordingly. */ | |
2270 | ||
2271 | static void | |
93bad80e | 2272 | remember_web_was_spilled (struct web *web) |
ed8d2920 MM |
2273 | { |
2274 | int i; | |
2275 | unsigned int found_size = 0; | |
2276 | int adjust; | |
2277 | web->spill_temp = 1; | |
2278 | ||
2279 | /* From now on don't use reg_pref/alt_class (regno) anymore for | |
2280 | this web, but instead usable_regs. We can't use spill_temp for | |
2281 | this, as it might get reset later, when we are coalesced to a | |
2282 | non-spill-temp. In that case we still want to use usable_regs. */ | |
2283 | web->use_my_regs = 1; | |
2284 | ||
2285 | /* We don't constrain spill temporaries in any way for now. | |
2286 | It's wrong sometimes to have the same constraints or | |
2287 | preferences as the original pseudo, esp. if they were very narrow. | |
2288 | (E.g. there once was a reg wanting class AREG (only one register) | |
2289 | without alternative class. As long, as also the spill-temps for | |
2290 | this pseudo had the same constraints it was spilled over and over. | |
2291 | Ideally we want some constraints also on spill-temps: Because they are | |
2292 | not only loaded/stored, but also worked with, any constraints from insn | |
2293 | alternatives needs applying. Currently this is dealt with by reload, as | |
2294 | many other things, but at some time we want to integrate that | |
2295 | functionality into the allocator. */ | |
2296 | if (web->regno >= max_normal_pseudo) | |
2297 | { | |
2298 | COPY_HARD_REG_SET (web->usable_regs, | |
2299 | reg_class_contents[reg_preferred_class (web->regno)]); | |
2300 | IOR_HARD_REG_SET (web->usable_regs, | |
2301 | reg_class_contents[reg_alternate_class (web->regno)]); | |
2302 | } | |
2303 | else | |
47cc673a MM |
2304 | COPY_HARD_REG_SET (web->usable_regs, |
2305 | reg_class_contents[(int) GENERAL_REGS]); | |
ed8d2920 MM |
2306 | AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors); |
2307 | prune_hardregs_for_mode (&web->usable_regs, PSEUDO_REGNO_MODE (web->regno)); | |
50aac998 | 2308 | #ifdef CANNOT_CHANGE_MODE_CLASS |
ed8d2920 | 2309 | if (web->mode_changed) |
50aac998 | 2310 | AND_COMPL_HARD_REG_SET (web->usable_regs, invalid_mode_change_regs); |
ed8d2920 MM |
2311 | #endif |
2312 | web->num_freedom = hard_regs_count (web->usable_regs); | |
2313 | if (!web->num_freedom) | |
2314 | abort(); | |
2315 | COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs); | |
2316 | /* Now look for a class, which is subset of our constraints, to | |
2317 | setup add_hardregs, and regclass for debug output. */ | |
2318 | web->regclass = NO_REGS; | |
2319 | for (i = (int) ALL_REGS - 1; i > 0; i--) | |
2320 | { | |
2321 | unsigned int size; | |
2322 | HARD_REG_SET test; | |
2323 | COPY_HARD_REG_SET (test, reg_class_contents[i]); | |
2324 | AND_COMPL_HARD_REG_SET (test, never_use_colors); | |
2325 | GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found); | |
2326 | continue; | |
2327 | found: | |
2328 | /* Measure the actual number of bits which really are overlapping | |
2329 | the target regset, not just the reg_class_size. */ | |
2330 | size = hard_regs_count (test); | |
2331 | if (found_size < size) | |
2332 | { | |
2333 | web->regclass = (enum reg_class) i; | |
2334 | found_size = size; | |
2335 | } | |
2336 | } | |
2337 | ||
2338 | adjust = 0 * web->add_hardregs; | |
2339 | web->add_hardregs = | |
2340 | CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1; | |
2341 | web->num_freedom -= web->add_hardregs; | |
2342 | if (!web->num_freedom) | |
2343 | abort(); | |
2344 | adjust -= 0 * web->add_hardregs; | |
2345 | web->num_conflicts -= adjust; | |
2346 | } | |
2347 | ||
2348 | /* Look at each web, if it is used as spill web. Or better said, | |
2349 | if it will be spillable in this pass. */ | |
2350 | ||
2351 | static void | |
93bad80e | 2352 | detect_spill_temps (void) |
ed8d2920 MM |
2353 | { |
2354 | struct dlist *d; | |
2355 | bitmap already = BITMAP_XMALLOC (); | |
2356 | ||
2357 | /* Detect webs used for spill temporaries. */ | |
2358 | for (d = WEBS(INITIAL); d; d = d->next) | |
2359 | { | |
2360 | struct web *web = DLIST_WEB (d); | |
2361 | ||
2362 | /* Below only the detection of spill temporaries. We never spill | |
2363 | precolored webs, so those can't be spill temporaries. The code above | |
2364 | (remember_web_was_spilled) can't currently cope with hardregs | |
2365 | anyway. */ | |
2366 | if (web->regno < FIRST_PSEUDO_REGISTER) | |
2367 | continue; | |
2368 | /* Uninitialized webs can't be spill-temporaries. */ | |
2369 | if (web->num_defs == 0) | |
2370 | continue; | |
2371 | ||
2372 | /* A web with only defs and no uses can't be spilled. Nevertheless | |
dcc24678 | 2373 | it must get a color, as it takes away a register from all webs |
ed8d2920 MM |
2374 | live at these defs. So we make it a short web. */ |
2375 | if (web->num_uses == 0) | |
2376 | web->spill_temp = 3; | |
2377 | /* A web which was spilled last time, but for which no insns were | |
2378 | emitted (can happen with IR spilling ignoring sometimes | |
2379 | all deaths). */ | |
2380 | else if (web->changed) | |
2381 | web->spill_temp = 1; | |
2382 | /* A spill temporary has one def, one or more uses, all uses | |
2383 | are in one insn, and either the def or use insn was inserted | |
2384 | by the allocator. */ | |
2385 | /* XXX not correct currently. There might also be spill temps | |
2386 | involving more than one def. Usually that's an additional | |
2387 | clobber in the using instruction. We might also constrain | |
2388 | ourself to that, instead of like currently marking all | |
2389 | webs involving any spill insns at all. */ | |
2390 | else | |
2391 | { | |
2392 | unsigned int i; | |
2393 | int spill_involved = 0; | |
2394 | for (i = 0; i < web->num_uses && !spill_involved; i++) | |
2395 | if (DF_REF_INSN_UID (web->uses[i]) >= orig_max_uid) | |
2396 | spill_involved = 1; | |
2397 | for (i = 0; i < web->num_defs && !spill_involved; i++) | |
2398 | if (DF_REF_INSN_UID (web->defs[i]) >= orig_max_uid) | |
2399 | spill_involved = 1; | |
2400 | ||
2401 | if (spill_involved/* && ra_pass > 2*/) | |
2402 | { | |
2403 | int num_deaths = web->span_deaths; | |
2404 | /* Mark webs involving at least one spill insn as | |
2405 | spill temps. */ | |
2406 | remember_web_was_spilled (web); | |
2407 | /* Search for insns which define and use the web in question | |
2408 | at the same time, i.e. look for rmw insns. If these insns | |
2409 | are also deaths of other webs they might have been counted | |
2410 | as such into web->span_deaths. But because of the rmw nature | |
2411 | of this insn it is no point where a load/reload could be | |
2412 | placed successfully (it would still conflict with the | |
2413 | dead web), so reduce the number of spanned deaths by those | |
2414 | insns. Note that sometimes such deaths are _not_ counted, | |
2415 | so negative values can result. */ | |
2416 | bitmap_zero (already); | |
2417 | for (i = 0; i < web->num_defs; i++) | |
2418 | { | |
2419 | rtx insn = web->defs[i]->insn; | |
2420 | if (TEST_BIT (insns_with_deaths, INSN_UID (insn)) | |
2421 | && !bitmap_bit_p (already, INSN_UID (insn))) | |
2422 | { | |
2423 | unsigned int j; | |
2424 | bitmap_set_bit (already, INSN_UID (insn)); | |
2425 | /* Only decrement it once for each insn. */ | |
2426 | for (j = 0; j < web->num_uses; j++) | |
2427 | if (web->uses[j]->insn == insn) | |
2428 | { | |
2429 | num_deaths--; | |
2430 | break; | |
2431 | } | |
2432 | } | |
2433 | } | |
2434 | /* But mark them specially if they could possibly be spilled, | |
2435 | either because they cross some deaths (without the above | |
2436 | mentioned ones) or calls. */ | |
2437 | if (web->crosses_call || num_deaths > 0) | |
2438 | web->spill_temp = 1 * 2; | |
2439 | } | |
2440 | /* A web spanning no deaths can't be spilled either. No loads | |
2441 | would be created for it, ergo no defs. So the insns wouldn't | |
2442 | change making the graph not easier to color. Make this also | |
2443 | a short web. Don't do this if it crosses calls, as these are | |
2444 | also points of reloads. */ | |
2445 | else if (web->span_deaths == 0 && !web->crosses_call) | |
2446 | web->spill_temp = 3; | |
2447 | } | |
2448 | web->orig_spill_temp = web->spill_temp; | |
2449 | } | |
2450 | BITMAP_XFREE (already); | |
2451 | } | |
2452 | ||
2453 | /* Returns nonzero if the rtx MEM refers somehow to a stack location. */ | |
2454 | ||
2455 | int | |
93bad80e | 2456 | memref_is_stack_slot (rtx mem) |
ed8d2920 MM |
2457 | { |
2458 | rtx ad = XEXP (mem, 0); | |
2459 | rtx x; | |
2460 | if (GET_CODE (ad) != PLUS || GET_CODE (XEXP (ad, 1)) != CONST_INT) | |
2461 | return 0; | |
2462 | x = XEXP (ad, 0); | |
2463 | if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx | |
2464 | || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]) | |
2465 | || x == stack_pointer_rtx) | |
2466 | return 1; | |
2467 | return 0; | |
2468 | } | |
2469 | ||
2470 | /* Returns nonzero, if rtx X somewhere contains any pseudo register. */ | |
2471 | ||
2472 | static int | |
93bad80e | 2473 | contains_pseudo (rtx x) |
ed8d2920 MM |
2474 | { |
2475 | const char *fmt; | |
2476 | int i; | |
2477 | if (GET_CODE (x) == SUBREG) | |
2478 | x = SUBREG_REG (x); | |
2479 | if (GET_CODE (x) == REG) | |
2480 | { | |
2481 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER) | |
2482 | return 1; | |
2483 | else | |
2484 | return 0; | |
2485 | } | |
2486 | ||
2487 | fmt = GET_RTX_FORMAT (GET_CODE (x)); | |
2488 | for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--) | |
2489 | if (fmt[i] == 'e') | |
2490 | { | |
2491 | if (contains_pseudo (XEXP (x, i))) | |
2492 | return 1; | |
2493 | } | |
2494 | else if (fmt[i] == 'E') | |
2495 | { | |
2496 | int j; | |
2497 | for (j = 0; j < XVECLEN (x, i); j++) | |
2498 | if (contains_pseudo (XVECEXP (x, i, j))) | |
2499 | return 1; | |
2500 | } | |
2501 | return 0; | |
2502 | } | |
2503 | ||
2504 | /* Returns nonzero, if we are able to rematerialize something with | |
2505 | value X. If it's not a general operand, we test if we can produce | |
2506 | a valid insn which set a pseudo to that value, and that insn doesn't | |
2507 | clobber anything. */ | |
2508 | ||
2509 | static GTY(()) rtx remat_test_insn; | |
2510 | static int | |
93bad80e | 2511 | want_to_remat (rtx x) |
ed8d2920 MM |
2512 | { |
2513 | int num_clobbers = 0; | |
2514 | int icode; | |
2515 | ||
2516 | /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */ | |
2517 | if (general_operand (x, GET_MODE (x))) | |
2518 | return 1; | |
2519 | ||
2520 | /* Otherwise, check if we can make a valid insn from it. First initialize | |
2521 | our test insn if we haven't already. */ | |
2522 | if (remat_test_insn == 0) | |
2523 | { | |
2524 | remat_test_insn | |
2525 | = make_insn_raw (gen_rtx_SET (VOIDmode, | |
2526 | gen_rtx_REG (word_mode, | |
2527 | FIRST_PSEUDO_REGISTER * 2), | |
2528 | const0_rtx)); | |
2529 | NEXT_INSN (remat_test_insn) = PREV_INSN (remat_test_insn) = 0; | |
2530 | } | |
2531 | ||
2532 | /* Now make an insn like the one we would make when rematerializing | |
2533 | the value X and see if valid. */ | |
2534 | PUT_MODE (SET_DEST (PATTERN (remat_test_insn)), GET_MODE (x)); | |
2535 | SET_SRC (PATTERN (remat_test_insn)) = x; | |
2536 | /* XXX For now we don't allow any clobbers to be added, not just no | |
2537 | hardreg clobbers. */ | |
2538 | return ((icode = recog (PATTERN (remat_test_insn), remat_test_insn, | |
2539 | &num_clobbers)) >= 0 | |
2540 | && (num_clobbers == 0 | |
2541 | /*|| ! added_clobbers_hard_reg_p (icode)*/)); | |
2542 | } | |
2543 | ||
2544 | /* Look at all webs, if they perhaps are rematerializable. | |
2545 | They are, if all their defs are simple sets to the same value, | |
2546 | and that value is simple enough, and want_to_remat() holds for it. */ | |
2547 | ||
2548 | static void | |
93bad80e | 2549 | detect_remat_webs (void) |
ed8d2920 MM |
2550 | { |
2551 | struct dlist *d; | |
2552 | for (d = WEBS(INITIAL); d; d = d->next) | |
2553 | { | |
2554 | struct web *web = DLIST_WEB (d); | |
2555 | unsigned int i; | |
2556 | rtx pat = NULL_RTX; | |
2557 | /* Hardregs and useless webs aren't spilled -> no remat necessary. | |
2558 | Defless webs obviously also can't be rematerialized. */ | |
2559 | if (web->regno < FIRST_PSEUDO_REGISTER || !web->num_defs | |
2560 | || !web->num_uses) | |
2561 | continue; | |
2562 | for (i = 0; i < web->num_defs; i++) | |
2563 | { | |
2564 | rtx insn; | |
2565 | rtx set = single_set (insn = DF_REF_INSN (web->defs[i])); | |
2566 | rtx src; | |
2567 | if (!set) | |
2568 | break; | |
2569 | src = SET_SRC (set); | |
2570 | /* When only subregs of the web are set it isn't easily | |
2571 | rematerializable. */ | |
2572 | if (!rtx_equal_p (SET_DEST (set), web->orig_x)) | |
2573 | break; | |
2574 | /* If we already have a pattern it must be equal to the current. */ | |
2575 | if (pat && !rtx_equal_p (pat, src)) | |
2576 | break; | |
2577 | /* Don't do the expensive checks multiple times. */ | |
2578 | if (pat) | |
2579 | continue; | |
2580 | /* For now we allow only constant sources. */ | |
2581 | if ((CONSTANT_P (src) | |
2582 | /* If the whole thing is stable already, it is a source for | |
2583 | remat, no matter how complicated (probably all needed | |
2584 | resources for it are live everywhere, and don't take | |
2585 | additional register resources). */ | |
2586 | /* XXX Currently we can't use patterns which contain | |
2587 | pseudos, _even_ if they are stable. The code simply isn't | |
2588 | prepared for that. All those operands can't be spilled (or | |
2589 | the dependent remat webs are not remat anymore), so they | |
2590 | would be oldwebs in the next iteration. But currently | |
2591 | oldwebs can't have their references changed. The | |
2592 | incremental machinery barfs on that. */ | |
2593 | || (!rtx_unstable_p (src) && !contains_pseudo (src)) | |
3d042e77 | 2594 | /* Additionally also memrefs to stack-slots are useful, when |
ed8d2920 MM |
2595 | we created them ourself. They might not have set their |
2596 | unchanging flag set, but nevertheless they are stable across | |
2597 | the livetime in question. */ | |
2598 | || (GET_CODE (src) == MEM | |
2599 | && INSN_UID (insn) >= orig_max_uid | |
2600 | && memref_is_stack_slot (src))) | |
2601 | /* And we must be able to construct an insn without | |
2602 | side-effects to actually load that value into a reg. */ | |
2603 | && want_to_remat (src)) | |
2604 | pat = src; | |
2605 | else | |
2606 | break; | |
2607 | } | |
2608 | if (pat && i == web->num_defs) | |
2609 | web->pattern = pat; | |
2610 | } | |
2611 | } | |
2612 | ||
2613 | /* Determine the spill costs of all webs. */ | |
2614 | ||
2615 | static void | |
93bad80e | 2616 | determine_web_costs (void) |
ed8d2920 MM |
2617 | { |
2618 | struct dlist *d; | |
2619 | for (d = WEBS(INITIAL); d; d = d->next) | |
2620 | { | |
2621 | unsigned int i, num_loads; | |
2622 | int load_cost, store_cost; | |
2623 | unsigned HOST_WIDE_INT w; | |
2624 | struct web *web = DLIST_WEB (d); | |
2625 | if (web->type == PRECOLORED) | |
2626 | continue; | |
2627 | /* Get costs for one load/store. Note that we offset them by 1, | |
2628 | because some patterns have a zero rtx_cost(), but we of course | |
2629 | still need the actual load/store insns. With zero all those | |
2630 | webs would be the same, no matter how often and where | |
2631 | they are used. */ | |
2632 | if (web->pattern) | |
2633 | { | |
2634 | /* This web is rematerializable. Beware, we set store_cost to | |
2635 | zero optimistically assuming, that we indeed don't emit any | |
2636 | stores in the spill-code addition. This might be wrong if | |
2637 | at the point of the load not all needed resources are | |
2638 | available, in which case we emit a stack-based load, for | |
2639 | which we in turn need the according stores. */ | |
2640 | load_cost = 1 + rtx_cost (web->pattern, 0); | |
2641 | store_cost = 0; | |
2642 | } | |
2643 | else | |
2644 | { | |
2645 | load_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), | |
2646 | web->regclass, 1); | |
2647 | store_cost = 1 + MEMORY_MOVE_COST (GET_MODE (web->orig_x), | |
2648 | web->regclass, 0); | |
2649 | } | |
2650 | /* We create only loads at deaths, whose number is in span_deaths. */ | |
2651 | num_loads = MIN (web->span_deaths, web->num_uses); | |
2652 | for (w = 0, i = 0; i < web->num_uses; i++) | |
2653 | w += DF_REF_BB (web->uses[i])->frequency + 1; | |
2654 | if (num_loads < web->num_uses) | |
2655 | w = (w * num_loads + web->num_uses - 1) / web->num_uses; | |
2656 | web->spill_cost = w * load_cost; | |
2657 | if (store_cost) | |
2658 | { | |
2659 | for (w = 0, i = 0; i < web->num_defs; i++) | |
2660 | w += DF_REF_BB (web->defs[i])->frequency + 1; | |
2661 | web->spill_cost += w * store_cost; | |
2662 | } | |
2663 | web->orig_spill_cost = web->spill_cost; | |
2664 | } | |
2665 | } | |
2666 | ||
2667 | /* Detect webs which are set in a conditional jump insn (possibly a | |
2668 | decrement-and-branch type of insn), and mark them not to be | |
2669 | spillable. The stores for them would need to be placed on edges, | |
2670 | which destroys the CFG. (Somewhen we want to deal with that XXX) */ | |
2671 | ||
2672 | static void | |
93bad80e | 2673 | detect_webs_set_in_cond_jump (void) |
ed8d2920 MM |
2674 | { |
2675 | basic_block bb; | |
2676 | FOR_EACH_BB (bb) | |
a813c111 | 2677 | if (GET_CODE (BB_END (bb)) == JUMP_INSN) |
ed8d2920 MM |
2678 | { |
2679 | struct df_link *link; | |
a813c111 | 2680 | for (link = DF_INSN_DEFS (df, BB_END (bb)); link; link = link->next) |
ed8d2920 MM |
2681 | if (link->ref && DF_REF_REGNO (link->ref) >= FIRST_PSEUDO_REGISTER) |
2682 | { | |
2683 | struct web *web = def2web[DF_REF_ID (link->ref)]; | |
2684 | web->orig_spill_temp = web->spill_temp = 3; | |
2685 | } | |
2686 | } | |
2687 | } | |
2688 | ||
2689 | /* Second top-level function of this file. | |
2690 | Converts the connected web parts to full webs. This means, it allocates | |
2691 | all webs, and initializes all fields, including detecting spill | |
2692 | temporaries. It does not distribute moves to their corresponding webs, | |
2693 | though. */ | |
2694 | ||
2695 | static void | |
93bad80e | 2696 | make_webs (struct df *df) |
ed8d2920 MM |
2697 | { |
2698 | /* First build all the webs itself. They are not related with | |
2699 | others yet. */ | |
2700 | parts_to_webs (df); | |
2701 | /* Now detect spill temporaries to initialize their usable_regs set. */ | |
2702 | detect_spill_temps (); | |
2703 | detect_webs_set_in_cond_jump (); | |
2704 | /* And finally relate them to each other, meaning to record all possible | |
2705 | conflicts between webs (see the comment there). */ | |
2706 | conflicts_between_webs (df); | |
2707 | detect_remat_webs (); | |
2708 | determine_web_costs (); | |
2709 | } | |
2710 | ||
2711 | /* Distribute moves to the corresponding webs. */ | |
2712 | ||
2713 | static void | |
93bad80e | 2714 | moves_to_webs (struct df *df) |
ed8d2920 MM |
2715 | { |
2716 | struct df_link *link; | |
2717 | struct move_list *ml; | |
2718 | ||
2719 | /* Distribute all moves to their corresponding webs, making sure, | |
2720 | each move is in a web maximally one time (happens on some strange | |
2721 | insns). */ | |
2722 | for (ml = wl_moves; ml; ml = ml->next) | |
2723 | { | |
2724 | struct move *m = ml->move; | |
2725 | struct web *web; | |
2726 | struct move_list *newml; | |
2727 | if (!m) | |
2728 | continue; | |
2729 | m->type = WORKLIST; | |
2730 | m->dlink = NULL; | |
2731 | /* Multiple defs/uses can happen in moves involving hard-regs in | |
2732 | a wider mode. For those df.* creates use/def references for each | |
2733 | real hard-reg involved. For coalescing we are interested in | |
2734 | the smallest numbered hard-reg. */ | |
2735 | for (link = DF_INSN_DEFS (df, m->insn); link; link = link->next) | |
2736 | if (link->ref) | |
2737 | { | |
2738 | web = def2web[DF_REF_ID (link->ref)]; | |
2739 | web = find_web_for_subweb (web); | |
2740 | if (!m->target_web || web->regno < m->target_web->regno) | |
2741 | m->target_web = web; | |
2742 | } | |
2743 | for (link = DF_INSN_USES (df, m->insn); link; link = link->next) | |
2744 | if (link->ref) | |
2745 | { | |
2746 | web = use2web[DF_REF_ID (link->ref)]; | |
2747 | web = find_web_for_subweb (web); | |
2748 | if (!m->source_web || web->regno < m->source_web->regno) | |
2749 | m->source_web = web; | |
2750 | } | |
2751 | if (m->source_web && m->target_web | |
2752 | /* If the usable_regs don't intersect we can't coalesce the two | |
2753 | webs anyway, as this is no simple copy insn (it might even | |
4b7e68e7 | 2754 | need an intermediate stack temp to execute this "copy" insn). */ |
ed8d2920 MM |
2755 | && hard_regs_intersect_p (&m->source_web->usable_regs, |
2756 | &m->target_web->usable_regs)) | |
2757 | { | |
2758 | if (!flag_ra_optimistic_coalescing) | |
2759 | { | |
2760 | struct move_list *test = m->source_web->moves; | |
2761 | for (; test && test->move != m; test = test->next); | |
2762 | if (! test) | |
2763 | { | |
703ad42b | 2764 | newml = ra_alloc (sizeof (struct move_list)); |
ed8d2920 MM |
2765 | newml->move = m; |
2766 | newml->next = m->source_web->moves; | |
2767 | m->source_web->moves = newml; | |
2768 | } | |
2769 | test = m->target_web->moves; | |
2770 | for (; test && test->move != m; test = test->next); | |
2771 | if (! test) | |
2772 | { | |
703ad42b | 2773 | newml = ra_alloc (sizeof (struct move_list)); |
ed8d2920 MM |
2774 | newml->move = m; |
2775 | newml->next = m->target_web->moves; | |
2776 | m->target_web->moves = newml; | |
2777 | } | |
2778 | } | |
2779 | } | |
2780 | else | |
2781 | /* Delete this move. */ | |
2782 | ml->move = NULL; | |
2783 | } | |
2784 | } | |
2785 | ||
2786 | /* Handle tricky asm insns. | |
2787 | Supposed to create conflicts to hardregs which aren't allowed in | |
2788 | the constraints. Doesn't actually do that, as it might confuse | |
2789 | and constrain the allocator too much. */ | |
2790 | ||
2791 | static void | |
93bad80e | 2792 | handle_asm_insn (struct df *df, rtx insn) |
ed8d2920 MM |
2793 | { |
2794 | const char *constraints[MAX_RECOG_OPERANDS]; | |
2795 | enum machine_mode operand_mode[MAX_RECOG_OPERANDS]; | |
2796 | int i, noperands, in_output; | |
2797 | HARD_REG_SET clobbered, allowed, conflict; | |
2798 | rtx pat; | |
2799 | if (! INSN_P (insn) | |
2800 | || (noperands = asm_noperands (PATTERN (insn))) < 0) | |
2801 | return; | |
2802 | pat = PATTERN (insn); | |
2803 | CLEAR_HARD_REG_SET (clobbered); | |
2804 | ||
2805 | if (GET_CODE (pat) == PARALLEL) | |
2806 | for (i = 0; i < XVECLEN (pat, 0); i++) | |
2807 | { | |
2808 | rtx t = XVECEXP (pat, 0, i); | |
2809 | if (GET_CODE (t) == CLOBBER && GET_CODE (XEXP (t, 0)) == REG | |
2810 | && REGNO (XEXP (t, 0)) < FIRST_PSEUDO_REGISTER) | |
2811 | SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0))); | |
2812 | } | |
2813 | ||
2814 | decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc, | |
2815 | constraints, operand_mode); | |
2816 | in_output = 1; | |
2817 | for (i = 0; i < noperands; i++) | |
2818 | { | |
2819 | const char *p = constraints[i]; | |
2820 | int cls = (int) NO_REGS; | |
2821 | struct df_link *link; | |
2822 | rtx reg; | |
2823 | struct web *web; | |
2824 | int nothing_allowed = 1; | |
2825 | reg = recog_data.operand[i]; | |
2826 | ||
2827 | /* Look, if the constraints apply to a pseudo reg, and not to | |
2828 | e.g. a mem. */ | |
2829 | while (GET_CODE (reg) == SUBREG | |
2830 | || GET_CODE (reg) == ZERO_EXTRACT | |
2831 | || GET_CODE (reg) == SIGN_EXTRACT | |
2832 | || GET_CODE (reg) == STRICT_LOW_PART) | |
2833 | reg = XEXP (reg, 0); | |
2834 | if (GET_CODE (reg) != REG || REGNO (reg) < FIRST_PSEUDO_REGISTER) | |
2835 | continue; | |
2836 | ||
2837 | /* Search the web corresponding to this operand. We depend on | |
2838 | that decode_asm_operands() places the output operands | |
2839 | before the input operands. */ | |
2840 | while (1) | |
2841 | { | |
2842 | if (in_output) | |
2843 | link = df->insns[INSN_UID (insn)].defs; | |
2844 | else | |
2845 | link = df->insns[INSN_UID (insn)].uses; | |
2846 | while (link && link->ref && DF_REF_REAL_REG (link->ref) != reg) | |
2847 | link = link->next; | |
2848 | if (!link || !link->ref) | |
2849 | { | |
2850 | if (in_output) | |
2851 | in_output = 0; | |
2852 | else | |
2853 | abort (); | |
2854 | } | |
2855 | else | |
2856 | break; | |
2857 | } | |
2858 | if (in_output) | |
2859 | web = def2web[DF_REF_ID (link->ref)]; | |
2860 | else | |
2861 | web = use2web[DF_REF_ID (link->ref)]; | |
2862 | reg = DF_REF_REG (link->ref); | |
2863 | ||
2864 | /* Find the constraints, noting the allowed hardregs in allowed. */ | |
2865 | CLEAR_HARD_REG_SET (allowed); | |
2866 | while (1) | |
2867 | { | |
97488870 | 2868 | char c = *p; |
ed8d2920 MM |
2869 | |
2870 | if (c == '\0' || c == ',' || c == '#') | |
2871 | { | |
2872 | /* End of one alternative - mark the regs in the current | |
97488870 R |
2873 | class, and reset the class. */ |
2874 | p++; | |
ed8d2920 MM |
2875 | IOR_HARD_REG_SET (allowed, reg_class_contents[cls]); |
2876 | if (cls != NO_REGS) | |
2877 | nothing_allowed = 0; | |
2878 | cls = NO_REGS; | |
2879 | if (c == '#') | |
2880 | do { | |
2881 | c = *p++; | |
2882 | } while (c != '\0' && c != ','); | |
2883 | if (c == '\0') | |
2884 | break; | |
2885 | continue; | |
2886 | } | |
2887 | ||
2888 | switch (c) | |
2889 | { | |
2890 | case '=': case '+': case '*': case '%': case '?': case '!': | |
2891 | case '0': case '1': case '2': case '3': case '4': case 'm': | |
2892 | case '<': case '>': case 'V': case 'o': case '&': case 'E': | |
2893 | case 'F': case 's': case 'i': case 'n': case 'X': case 'I': | |
2894 | case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': | |
2895 | case 'P': | |
2896 | break; | |
2897 | ||
2898 | case 'p': | |
2899 | cls = (int) reg_class_subunion[cls][(int) BASE_REG_CLASS]; | |
2900 | nothing_allowed = 0; | |
2901 | break; | |
2902 | ||
2903 | case 'g': | |
2904 | case 'r': | |
2905 | cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS]; | |
2906 | nothing_allowed = 0; | |
2907 | break; | |
2908 | ||
2909 | default: | |
2910 | cls = | |
2911 | (int) reg_class_subunion[cls][(int) | |
97488870 R |
2912 | REG_CLASS_FROM_CONSTRAINT (c, |
2913 | p)]; | |
ed8d2920 | 2914 | } |
97488870 | 2915 | p += CONSTRAINT_LEN (c, p); |
ed8d2920 MM |
2916 | } |
2917 | ||
2918 | /* Now make conflicts between this web, and all hardregs, which | |
2919 | are not allowed by the constraints. */ | |
2920 | if (nothing_allowed) | |
2921 | { | |
d55d8fc7 | 2922 | /* If we had no real constraints nothing was explicitly |
ed8d2920 MM |
2923 | allowed, so we allow the whole class (i.e. we make no |
2924 | additional conflicts). */ | |
2925 | CLEAR_HARD_REG_SET (conflict); | |
2926 | } | |
2927 | else | |
2928 | { | |
2929 | COPY_HARD_REG_SET (conflict, usable_regs | |
2930 | [reg_preferred_class (web->regno)]); | |
2931 | IOR_HARD_REG_SET (conflict, usable_regs | |
2932 | [reg_alternate_class (web->regno)]); | |
2933 | AND_COMPL_HARD_REG_SET (conflict, allowed); | |
2934 | /* We can't yet establish these conflicts. Reload must go first | |
2935 | (or better said, we must implement some functionality of reload). | |
2936 | E.g. if some operands must match, and they need the same color | |
2937 | we don't see yet, that they do not conflict (because they match). | |
2938 | For us it looks like two normal references with different DEFs, | |
2939 | so they conflict, and as they both need the same color, the | |
2940 | graph becomes uncolorable. */ | |
2941 | #if 0 | |
2942 | for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) | |
2943 | if (TEST_HARD_REG_BIT (conflict, c)) | |
2944 | record_conflict (web, hardreg2web[c]); | |
2945 | #endif | |
2946 | } | |
c263766c | 2947 | if (dump_file) |
ed8d2920 MM |
2948 | { |
2949 | int c; | |
2950 | ra_debug_msg (DUMP_ASM, " ASM constrain Web %d conflicts with:", web->id); | |
2951 | for (c = 0; c < FIRST_PSEUDO_REGISTER; c++) | |
2952 | if (TEST_HARD_REG_BIT (conflict, c)) | |
2953 | ra_debug_msg (DUMP_ASM, " %d", c); | |
2954 | ra_debug_msg (DUMP_ASM, "\n"); | |
2955 | } | |
2956 | } | |
2957 | } | |
2958 | ||
2959 | /* The real toplevel function in this file. | |
2960 | Build (or rebuilds) the complete interference graph with webs | |
2961 | and conflicts. */ | |
2962 | ||
2963 | void | |
93bad80e | 2964 | build_i_graph (struct df *df) |
ed8d2920 MM |
2965 | { |
2966 | rtx insn; | |
2967 | ||
2968 | init_web_parts (df); | |
2969 | ||
2970 | sbitmap_zero (move_handled); | |
2971 | wl_moves = NULL; | |
2972 | ||
2973 | build_web_parts_and_conflicts (df); | |
2974 | ||
2975 | /* For read-modify-write instructions we may have created two webs. | |
2976 | Reconnect them here. (s.a.) */ | |
2977 | connect_rmw_web_parts (df); | |
2978 | ||
2979 | /* The webs are conceptually complete now, but still scattered around as | |
2980 | connected web parts. Collect all information and build the webs | |
2981 | including all conflicts between webs (instead web parts). */ | |
2982 | make_webs (df); | |
2983 | moves_to_webs (df); | |
2984 | ||
2985 | /* Look for additional constraints given by asms. */ | |
2986 | for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) | |
2987 | handle_asm_insn (df, insn); | |
2988 | } | |
2989 | ||
2990 | /* Allocates or reallocates most memory for the interference graph and | |
d55d8fc7 | 2991 | associated structures. If it reallocates memory (meaning, this is not |
ed8d2920 MM |
2992 | the first pass), this also changes some structures to reflect the |
2993 | additional entries in various array, and the higher number of | |
2994 | defs and uses. */ | |
2995 | ||
2996 | void | |
93bad80e | 2997 | ra_build_realloc (struct df *df) |
ed8d2920 MM |
2998 | { |
2999 | struct web_part *last_web_parts = web_parts; | |
3000 | struct web **last_def2web = def2web; | |
3001 | struct web **last_use2web = use2web; | |
3002 | sbitmap last_live_over_abnormal = live_over_abnormal; | |
3003 | unsigned int i; | |
3004 | struct dlist *d; | |
3005 | move_handled = sbitmap_alloc (get_max_uid () ); | |
703ad42b KG |
3006 | web_parts = xcalloc (df->def_id + df->use_id, sizeof web_parts[0]); |
3007 | def2web = xcalloc (df->def_id + df->use_id, sizeof def2web[0]); | |
ed8d2920 MM |
3008 | use2web = &def2web[df->def_id]; |
3009 | live_over_abnormal = sbitmap_alloc (df->use_id); | |
3010 | sbitmap_zero (live_over_abnormal); | |
3011 | ||
3012 | /* First go through all old defs and uses. */ | |
3013 | for (i = 0; i < last_def_id + last_use_id; i++) | |
3014 | { | |
3015 | /* And relocate them to the new array. This is made ugly by the | |
3016 | fact, that defs and uses are placed consecutive into one array. */ | |
3017 | struct web_part *dest = &web_parts[i < last_def_id | |
3018 | ? i : (df->def_id + i - last_def_id)]; | |
3019 | struct web_part *up; | |
3020 | *dest = last_web_parts[i]; | |
3021 | up = dest->uplink; | |
3022 | dest->uplink = NULL; | |
3023 | ||
3024 | /* Also relocate the uplink to point into the new array. */ | |
3025 | if (up && up->ref) | |
3026 | { | |
3027 | unsigned int id = DF_REF_ID (up->ref); | |
3028 | if (up < &last_web_parts[last_def_id]) | |
3029 | { | |
3030 | if (df->defs[id]) | |
3031 | dest->uplink = &web_parts[DF_REF_ID (up->ref)]; | |
3032 | } | |
3033 | else if (df->uses[id]) | |
3034 | dest->uplink = &web_parts[df->def_id + DF_REF_ID (up->ref)]; | |
3035 | } | |
3036 | } | |
3037 | ||
3038 | /* Also set up the def2web and use2web arrays, from the last pass.i | |
3039 | Remember also the state of live_over_abnormal. */ | |
3040 | for (i = 0; i < last_def_id; i++) | |
3041 | { | |
3042 | struct web *web = last_def2web[i]; | |
3043 | if (web) | |
3044 | { | |
3045 | web = find_web_for_subweb (web); | |
3046 | if (web->type != FREE && web->type != PRECOLORED) | |
3047 | def2web[i] = last_def2web[i]; | |
3048 | } | |
3049 | } | |
3050 | for (i = 0; i < last_use_id; i++) | |
3051 | { | |
3052 | struct web *web = last_use2web[i]; | |
3053 | if (web) | |
3054 | { | |
3055 | web = find_web_for_subweb (web); | |
3056 | if (web->type != FREE && web->type != PRECOLORED) | |
3057 | use2web[i] = last_use2web[i]; | |
3058 | } | |
3059 | if (TEST_BIT (last_live_over_abnormal, i)) | |
3060 | SET_BIT (live_over_abnormal, i); | |
3061 | } | |
3062 | ||
3063 | /* We don't have any subwebs for now. Somewhen we might want to | |
3064 | remember them too, instead of recreating all of them every time. | |
3065 | The problem is, that which subwebs we need, depends also on what | |
3066 | other webs and subwebs exist, and which conflicts are there. | |
3067 | OTOH it should be no problem, if we had some more subwebs than strictly | |
3068 | needed. Later. */ | |
3069 | for (d = WEBS(FREE); d; d = d->next) | |
3070 | { | |
3071 | struct web *web = DLIST_WEB (d); | |
3072 | struct web *wnext; | |
3073 | for (web = web->subreg_next; web; web = wnext) | |
3074 | { | |
3075 | wnext = web->subreg_next; | |
3076 | free (web); | |
3077 | } | |
3078 | DLIST_WEB (d)->subreg_next = NULL; | |
3079 | } | |
3080 | ||
3081 | /* The uses we anyway are going to check, are not yet live over an abnormal | |
3082 | edge. In fact, they might actually not anymore, due to added | |
3083 | loads. */ | |
3084 | if (last_check_uses) | |
3085 | sbitmap_difference (live_over_abnormal, live_over_abnormal, | |
3086 | last_check_uses); | |
3087 | ||
3088 | if (last_def_id || last_use_id) | |
3089 | { | |
3090 | sbitmap_free (last_live_over_abnormal); | |
3091 | free (last_web_parts); | |
3092 | free (last_def2web); | |
3093 | } | |
3094 | if (!last_max_uid) | |
3095 | { | |
3096 | /* Setup copy cache, for copy_insn_p (). */ | |
703ad42b | 3097 | copy_cache = xcalloc (get_max_uid (), sizeof (copy_cache[0])); |
ed8d2920 MM |
3098 | init_bb_info (); |
3099 | } | |
3100 | else | |
3101 | { | |
703ad42b | 3102 | copy_cache = xrealloc (copy_cache, get_max_uid () * sizeof (copy_cache[0])); |
ed8d2920 MM |
3103 | memset (©_cache[last_max_uid], 0, |
3104 | (get_max_uid () - last_max_uid) * sizeof (copy_cache[0])); | |
3105 | } | |
3106 | } | |
3107 | ||
3108 | /* Free up/clear some memory, only needed for one pass. */ | |
3109 | ||
3110 | void | |
93bad80e | 3111 | ra_build_free (void) |
ed8d2920 MM |
3112 | { |
3113 | struct dlist *d; | |
3114 | unsigned int i; | |
3115 | ||
3116 | /* Clear the moves associated with a web (we also need to look into | |
3117 | subwebs here). */ | |
3118 | for (i = 0; i < num_webs; i++) | |
3119 | { | |
3120 | struct web *web = ID2WEB (i); | |
3121 | if (!web) | |
3122 | abort (); | |
3123 | if (i >= num_webs - num_subwebs | |
3124 | && (web->conflict_list || web->orig_conflict_list)) | |
3125 | abort (); | |
3126 | web->moves = NULL; | |
3127 | } | |
3128 | /* All webs in the free list have no defs or uses anymore. */ | |
3129 | for (d = WEBS(FREE); d; d = d->next) | |
3130 | { | |
3131 | struct web *web = DLIST_WEB (d); | |
3132 | if (web->defs) | |
3133 | free (web->defs); | |
3134 | web->defs = NULL; | |
3135 | if (web->uses) | |
3136 | free (web->uses); | |
3137 | web->uses = NULL; | |
3138 | /* We can't free the subwebs here, as they are referenced from | |
3139 | def2web[], and possibly needed in the next ra_build_realloc(). | |
3140 | We free them there (or in free_all_mem()). */ | |
3141 | } | |
3142 | ||
3143 | /* Free all conflict bitmaps from web parts. Note that we clear | |
3144 | _all_ these conflicts, and don't rebuild them next time for uses | |
3145 | which aren't rechecked. This mean, that those conflict bitmaps | |
3146 | only contain the incremental information. The cumulative one | |
3147 | is still contained in the edges of the I-graph, i.e. in | |
3148 | conflict_list (or orig_conflict_list) of the webs. */ | |
3149 | for (i = 0; i < df->def_id + df->use_id; i++) | |
3150 | { | |
3151 | struct tagged_conflict *cl; | |
3152 | for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next) | |
3153 | { | |
3154 | if (cl->conflicts) | |
3155 | BITMAP_XFREE (cl->conflicts); | |
3156 | } | |
3157 | web_parts[i].sub_conflicts = NULL; | |
3158 | } | |
3159 | ||
3160 | wl_moves = NULL; | |
3161 | ||
3162 | free (id2web); | |
3163 | free (move_handled); | |
3164 | sbitmap_free (sup_igraph); | |
3165 | sbitmap_free (igraph); | |
3166 | } | |
3167 | ||
3168 | /* Free all memory for the interference graph structures. */ | |
3169 | ||
3170 | void | |
93bad80e | 3171 | ra_build_free_all (struct df *df) |
ed8d2920 MM |
3172 | { |
3173 | unsigned int i; | |
3174 | ||
3175 | free_bb_info (); | |
3176 | free (copy_cache); | |
3177 | copy_cache = NULL; | |
3178 | for (i = 0; i < df->def_id + df->use_id; i++) | |
3179 | { | |
3180 | struct tagged_conflict *cl; | |
3181 | for (cl = web_parts[i].sub_conflicts; cl; cl = cl->next) | |
3182 | { | |
3183 | if (cl->conflicts) | |
3184 | BITMAP_XFREE (cl->conflicts); | |
3185 | } | |
3186 | web_parts[i].sub_conflicts = NULL; | |
3187 | } | |
3188 | sbitmap_free (live_over_abnormal); | |
3189 | free (web_parts); | |
3190 | web_parts = NULL; | |
3191 | if (last_check_uses) | |
3192 | sbitmap_free (last_check_uses); | |
3193 | last_check_uses = NULL; | |
3194 | free (def2web); | |
3195 | use2web = NULL; | |
3196 | def2web = NULL; | |
3197 | } | |
3198 | ||
3199 | #include "gt-ra-build.h" | |
3200 | ||
3201 | /* | |
3202 | vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4: | |
3203 | */ |