OSDN Git Service

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