| blob | 63fb24e05970bbebc8f369df60c026db6972bc8a |
1 /* Graph coloring register allocator
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Michael Matz <matz@suse.de>
4 and Daniel Berlin <dan@cgsoftware.com>
6 This file is part of GCC.
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.
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.
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. */
39 /* This file is part of the graph coloring register allocator.
40 It deals with building the interference graph. When rebuilding
41 the graph for a function after spilling, we rebuild only those
42 parts needed, i.e. it works incrementally.
44 The first part (the functions called from build_web_parts_and_conflicts()
45 ) constructs a web_part for each pseudo register reference in the insn
46 stream, then goes backward from each use, until it reaches defs for that
47 pseudo. While going back it remember seen defs for other registers as
48 conflicts. By connecting the uses and defs, which reach each other, webs
49 (or live ranges) are built conceptually.
51 The second part (make_webs() and children) deals with converting that
52 structure to the nodes and edges, on which our interference graph is
53 built. For each root web part constructed above, an instance of struct
54 web is created. For all subregs of pseudos, which matter for allocation,
55 a subweb of the corresponding super web is built. Finally all the
56 conflicts noted in the first part (as bitmaps) are transformed into real
57 edges.
59 As part of that process the webs are also classified (their spill cost
60 is calculated, and if they are spillable at all, and if not, for what
61 reason; or if they are rematerializable), and move insns are collected,
62 which are potentially coalescable.
64 The top-level entry of this file (build_i_graph) puts it all together,
65 and leaves us with a complete interference graph, which just has to
66 be colored. */
105 #if 0
107 #endif
126 /* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
127 edge. */
130 /* To cache if we already saw a certain edge while analyzing one
131 use, we use a tick count incremented per use. */
134 /* A sbitmap of UIDs of move insns, which we already analyzed. */
137 /* One such structed is allocated per insn, and traces for the currently
138 analyzed use, which web part belongs to it, and how many bytes of
139 it were still undefined when that insn was reached. */
140 struct visit_trace
141 {
144 };
145 /* Indexed by UID. */
148 /* Per basic block we have one such structure, used to speed up
149 the backtracing of uses. */
150 struct ra_bb_info
151 {
152 /* The value of visited_pass, as the first insn of this BB was reached
153 the last time. If this equals the current visited_pass, then
154 undefined is valid. Otherwise not. */
156 /* The still undefined bytes at that time. The use to which this is
157 relative is the current use. */
159 /* Bit regno is set, if that regno is mentioned in this BB as a def, or
160 the source of a copy insn. In these cases we can not skip the whole
161 block if we reach it from the end. */
162 bitmap regnos_mentioned;
163 /* If a use reaches the end of a BB, and that BB doesn't mention its
164 regno, we skip the block, and remember the ID of that use
165 as living throughout the whole block. */
166 bitmap live_throughout;
167 /* The content of the aux field before placing a pointer to this
168 structure there. */
170 };
172 /* We need a fast way to describe a certain part of a register.
173 Therefore we put together the size and offset (in bytes) in one
174 integer. */
175 #define BL_TO_WORD(b, l) ((((b) & 0xFFFF) << 16) | ((l) & 0xFFFF))
176 #define BYTE_BEGIN(i) (((unsigned int)(i) >> 16) & 0xFFFF)
177 #define BYTE_LENGTH(i) ((unsigned int)(i) & 0xFFFF)
179 /* For a REG or SUBREG expression X return the size/offset pair
180 as an integer. */
182 unsigned int
184 {
189 }
191 /* X is a REG or SUBREG rtx. Return the bytes it touches as a bitmask. */
193 static unsigned HOST_WIDE_INT
195 {
203 }
205 /* We remember if we've analyzed an insn for being a move insn, and if yes
206 between which operands. */
207 struct copy_p_cache
208 {
210 rtx source;
211 rtx target;
212 };
214 /* On demand cache, for if insns are copy insns, and if yes, what
215 source/target they have. */
220 /* For INSN, return nonzero, if it's a move insn, we consider to coalesce
221 later, and place the operands in *SOURCE and *TARGET, if they are
222 not NULL. */
224 static int
226 {
234 /* First look, if we already saw this insn. */
236 {
237 /* And if we saw it, if it's actually a copy insn. */
239 {
245 }
247 }
249 /* Mark it as seen, but not being a copy insn. */
257 /* We recognize moves between subreg's as copy insns. This is used to avoid
258 conflicts of those subwebs. But they are currently _not_ used for
259 coalescing (the check for this is in remember_move() below). */
274 /* Copies between hardregs are useless for us, as not coalesable anyway. */
286 /* Still mark it as seen, but as a copy insn this time. */
291 }
293 /* We build webs, as we process the conflicts. For each use we go upward
294 the insn stream, noting any defs as potentially conflicting with the
295 current use. We stop at defs of the current regno. The conflicts are only
296 potentially, because we may never reach a def, so this is an undefined use,
297 which conflicts with nothing. */
300 /* Given a web part WP, and the location of a reg part SIZE_WORD
301 return the conflict bitmap for that reg part, or NULL if it doesn't
302 exist yet in WP. */
304 static bitmap
306 {
313 }
315 /* Similar to find_sub_conflicts(), but creates that bitmap, if it
316 doesn't exist. I.e. this never returns NULL. */
318 static bitmap
320 {
323 {
330 }
332 }
334 /* Helper table for undef_to_size_word() below for small values
335 of UNDEFINED. Offsets and lengths are byte based. */
338 /* size | (byte << 16) */
358 /* Interpret *UNDEFINED as bitmask where each bit corresponds to a byte.
359 A set bit means an undefined byte. Factor all undefined bytes into
360 groups, and return a size/ofs pair of consecutive undefined bytes,
361 but according to certain borders. Clear out those bits corresponding
362 to bytes overlaid by that size/ofs pair. REG is only used for
363 the mode, to detect if it's a floating mode or not.
365 For example: *UNDEFINED size+ofs new *UNDEFINED
366 1111 4+0 0
367 1100 2+2 0
368 1101 2+2 1
369 0001 1+0 0
370 10101 1+4 101
372 */
374 static unsigned int
376 {
377 /* When only the lower four bits are possibly set, we use
378 a fast lookup table. */
380 {
385 }
387 /* Otherwise we handle certain cases directly. */
390 {
398 else
404 }
406 /* And if nothing matched fall back to the general solution. For
407 now unknown undefined bytes are converted to sequences of maximal
408 length 4 bytes. We could make this larger if necessary. */
409 {
420 /* Size remains the same, only the begin is moved up move bytes. */
422 }
423 }
425 /* Put the above three functions together. For a set of undefined bytes
426 as bitmap *UNDEFINED, look for (create if necessary) and return the
427 corresponding conflict bitmap. Change *UNDEFINED to remove the bytes
428 covered by the part for that bitmap. */
430 static bitmap
432 {
434 undefined);
436 }
438 /* Returns the root of the web part P is a member of. Additionally
439 it compresses the path. P may not be NULL. */
443 {
449 {
452 }
454 }
456 /* Fast macro for the common case (WP either being the root itself, or
457 the end of an already compressed path. */
459 #define find_web_part(wp) ((! (wp)->uplink) ? (wp) \
460 : (! (wp)->uplink->uplink) ? (wp)->uplink : find_web_part_1 (wp))
462 /* Unions together the parts R1 resp. R2 is a root of.
463 All dynamic information associated with the parts (number of spanned insns
464 and so on) is also merged.
465 The root of the resulting (possibly larger) web part is returned. */
469 {
471 {
472 /* The new root is the smaller (pointerwise) of both. This is crucial
473 to make the construction of webs from web parts work (so, when
474 scanning all parts, we see the roots before all its children).
475 Additionally this ensures, that if the web has a def at all, than
476 the root is a def (because all def parts are before use parts in the
477 web_parts[] array), or put another way, as soon, as the root of a
478 web part is not a def, this is an uninitialized web part. The
479 way we construct the I-graph ensures, that if a web is initialized,
480 then the first part we find (besides trivial 1 item parts) has a
481 def. */
483 {
487 }
489 num_webs--;
491 /* Now we merge the dynamic information of R1 and R2. */
497 /* We need to merge the conflict bitmaps from R2 into R1. */
498 {
500 /* First those from R2, which are also contained in R1.
501 We union the bitmaps, and free those from R2, resetting them
502 to 0. */
506 {
511 }
512 /* Now the conflict lists from R2 which weren't in R1.
513 We simply copy the entries from R2 into R1' list. */
515 {
518 {
521 }
523 }
524 }
527 }
529 }
531 /* Convenience macro, that is capable of unioning also non-roots. */
532 #define union_web_parts(p1, p2) \
533 ((p1 == p2) ? find_web_part (p1) \
534 : union_web_part_roots (find_web_part (p1), find_web_part (p2)))
536 /* Remember that we've handled a given move, so we don't reprocess it. */
538 static void
540 {
542 {
546 {
547 /* Some sanity test for the copy insn. */
552 /* The following (link->next != 0) happens when a hardreg
553 is used in wider mode (REG:DI %eax). Then df.* creates
554 a def/use for each hardreg contained therein. We only
555 allow hardregs here. */
559 }
560 else
562 /* XXX for now we don't remember move insns involving any subregs.
563 Those would be difficult to coalesce (we would need to implement
564 handling of all the subwebs in the allocator, including that such
565 subwebs could be source and target of coalescing). */
567 {
575 }
576 }
577 }
579 /* This describes the USE currently looked at in the main-loop in
580 build_web_parts_and_conflicts(). */
583 /* This has a 1-bit for each byte in the USE, which is still undefined. */
585 /* For easy access. */
587 rtx x;
588 /* If some bits of this USE are live over an abnormal edge. */
590 };
592 /* Returns nonzero iff rtx DEF and USE have bits in common (but see below).
593 It is only called with DEF and USE being (reg:M a) or (subreg:M1 (reg:M2 a)
594 x) rtx's. Furthermore if it's a subreg rtx M1 is at least one word wide,
595 and a is a multi-word pseudo. If DEF or USE are hardregs, they are in
596 word_mode, so we don't need to check for further hardregs which would result
597 from wider references. We are never called with paradoxical subregs.
599 This returns:
600 0 for no common bits,
601 1 if DEF and USE exactly cover the same bytes,
602 2 if the DEF only covers a part of the bits of USE
603 3 if the DEF covers more than the bits of the USE, and
604 4 if both are SUBREG's of different size, but have bytes in common.
605 -1 is a special case, for when DEF and USE refer to the same regno, but
606 have for other reasons no bits in common (can only happen with
607 subregs referring to different words, or to words which already were
608 defined for this USE).
609 Furthermore it modifies use->undefined to clear the bits which get defined
610 by DEF (only for cases with partial overlap).
611 I.e. if bit 1 is set for the result != -1, the USE was completely covered,
612 otherwise a test is needed to track the already defined bytes. */
614 static int
616 {
623 {
627 }
633 {
637 {
641 }
646 /* If the size of both things is the same, the subreg's overlap
647 if they refer to the same word. */
650 /* Now the more difficult part: the same regno is referred, but the
651 sizes of the references or the words differ. E.g.
652 (subreg:SI (reg:CDI a) 0) and (subreg:DI (reg:CDI a) 2) do not
653 overlap, whereas the latter overlaps with (subreg:SI (reg:CDI a) 3).
654 */
655 {
670 }
673 }
674 }
676 /* Macro for the common case of either def and use having the same rtx,
677 or based on different regnos. */
678 #define defuse_overlap_p(def, use) \
679 ((def) == (use)->x ? 1 : \
680 (REGNO (GET_CODE (def) == SUBREG \
681 ? SUBREG_REG (def) : def) != use->regno \
682 ? 0 : defuse_overlap_p_1 (def, use)))
685 /* The use USE flows into INSN (backwards). Determine INSNs effect on it,
686 and return nonzero, if (parts of) that USE are also live before it.
687 This also notes conflicts between the USE and all DEFS in that insn,
688 and modifies the undefined bits of USE in case parts of it were set in
689 this insn. */
691 static int
693 {
698 /* Mark, that this insn needs this webpart live. */
703 {
712 /* We want to access the root webpart. */
719 /* Look at all DEFS in this insn. */
721 {
725 /* Reset the undefined bits for each iteration, in case this
726 insn has more than one set, and one of them sets this regno.
727 But still the original undefined part conflicts with the other
728 sets. */
731 {
733 /* Same regnos but non-overlapping or already defined bits,
734 so ignore this DEF, or better said make the yet undefined
735 part and this DEF conflicting. */
736 {
743 }
745 /* The current DEF completely covers the USE, so we can
746 stop traversing the code looking for further DEFs. */
748 else
749 /* We have a partial overlap. */
750 {
753 /* Now the USE is completely defined, which means, that
754 we can stop looking for former DEFs. */
756 /* If this is a partial overlap, which left some bits
757 in USE undefined, we normally would need to create
758 conflicts between that undefined part and the part of
759 this DEF which overlapped with some of the formerly
760 undefined bits. We don't need to do this, because both
761 parts of this DEF (that which overlaps, and that which
762 doesn't) are written together in this one DEF, and can
763 not be colored in a way which would conflict with
764 the USE. This is only true for partial overlap,
765 because only then the DEF and USE have bits in common,
766 which makes the DEF move, if the USE moves, making them
767 aligned.
768 If they have no bits in common (lap == -1), they are
769 really independent. Therefore we there made a
770 conflict above. */
771 }
772 /* This is at least a partial overlap, so we need to union
773 the web parts. */
775 }
776 else
777 {
778 /* The DEF and the USE don't overlap at all, different
779 regnos. I.e. make conflicts between the undefined bits,
780 and that DEF. */
784 /* This triggers only, when this was a copy insn and the
785 source is at least a part of the USE currently looked at.
786 In this case only the bits of the USE conflict with the
787 DEF, which are not covered by the source of this copy
788 insn, and which are still undefined. I.e. in the best
789 case (the whole reg being the source), _no_ conflicts
790 between that USE and this DEF (the target of the move)
791 are created by this insn (though they might be by
792 others). This is a super case of the normal copy insn
793 only between full regs. */
794 {
796 }
798 {
799 /*struct web_part *cwp;
800 cwp = find_web_part (&web_parts[DF_REF_ID
801 (ref)]);*/
803 /* TODO: somehow instead of noting the ID of the LINK
804 use an ID nearer to the root webpart of that LINK.
805 We can't use the root itself, because we later use the
806 ID to look at the form (reg or subreg, and if yes,
807 which subreg) of this conflict. This means, that we
808 need to remember in the root an ID for each form, and
809 maintaining this, when merging web parts. This makes
810 the bitmaps smaller. */
811 do
815 }
816 }
817 }
820 else
821 {
822 /* If this insn doesn't completely define the USE, increment also
823 it's spanned deaths count (if this insn contains a death). */
829 }
830 }
833 }
835 /* Same as live_out_1() (actually calls it), but caches some information.
836 E.g. if we reached this INSN with the current regno already, and the
837 current undefined bits are a subset of those as we came here, we
838 simply connect the web parts of the USE, and the one cached for this
839 INSN, and additionally return zero, indicating we don't need to traverse
840 this path any longer (all effect were already seen, as we first reached
841 this insn). */
845 {
850 {
852 /* Don't search any further, as we already were here with this regno. */
854 }
855 else
857 }
859 /* The current USE reached a basic block head. The edge E is one
860 of the predecessors edges. This evaluates the effect of the predecessor
861 block onto the USE, and returns the next insn, which should be looked at.
862 This either is the last insn of that pred. block, or the first one.
863 The latter happens, when the pred. block has no possible effect on the
864 USE, except for conflicts. In that case, it's remembered, that the USE
865 is live over that whole block, and it's skipped. Otherwise we simply
866 continue with the last insn of the block.
868 This also determines the effects of abnormal edges, and remembers
869 which uses are live at the end of that basic block. */
871 static rtx
873 {
875 rtx next_insn;
876 /* Call used hard regs die over an exception edge, ergo
877 they don't reach the predecessor block, so ignore such
878 uses. And also don't set the live_over_abnormal flag
879 for them. */
889 /* If the last insn of the pred. block doesn't completely define the
890 current use, we need to check the block. */
892 {
893 /* If the current regno isn't mentioned anywhere in the whole block,
894 and the complete use is still undefined... */
897 {
898 /* ...we can hop over the whole block and defer conflict
899 creation to later. */
903 }
905 }
906 else
908 }
910 /* USE flows into the end of the insns preceding INSN. Determine
911 their effects (in live_out()) and possibly loop over the preceding INSN,
912 or call itself recursively on a basic block border. When a topleve
913 call of this function returns the USE is completely analyzed. I.e.
914 its def-use chain (at least) is built, possibly connected with other
915 def-use chains, and all defs during that chain are noted. */
917 static void
919 {
922 /* Note, that, even _if_ we are called with use->wp a root-part, this might
923 become non-root in the for() loop below (due to live_out() unioning
924 it). So beware, not to change use->wp in a way, for which only root-webs
925 are allowed. */
927 {
932 /* We want to be as fast as possible, so explicitly write
933 this loop. */
936 ;
940 {
941 edge e;
946 /* We now check, if we already traversed the predecessors of this
947 block for the current pass and the current set of undefined
948 bits. If yes, we don't need to check the predecessors again.
949 So, conceptually this information is tagged to the first
950 insn of a basic block. */
955 /* All but the last predecessor are handled recursively. */
957 {
962 }
966 }
969 }
970 }
972 /* Determine all regnos which are mentioned in a basic block, in an
973 interesting way. Interesting here means either in a def, or as the
974 source of a move insn. We only look at insns added since the last
975 pass. */
977 static void
979 {
981 rtx insn;
982 basic_block bb;
985 {
986 /* Don't look at old insns. */
988 {
989 /* XXX We should also remember moves over iterations (we already
990 save the cache, but not the movelist). */
993 }
995 {
996 rtx source;
1001 {
1006 }
1010 }
1011 }
1012 }
1014 /* Handle the uses which reach a block end, but were deferred due
1015 to it's regno not being mentioned in that block. This adds the
1016 remaining conflicts and updates also the crosses_call and
1017 spanned_deaths members. */
1019 static void
1021 {
1023 rtx insn;
1024 bitmap all_defs;
1029 /* If there are no deferred uses, just return. */
1033 /* First collect the IDs of all defs, count the number of death
1034 containing insns, and if there's some call_insn here. */
1037 {
1039 {
1047 deaths++;
1050 }
1053 }
1055 /* And now, if we have found anything, make all live_through
1056 uses conflict with all defs, and update their other members. */
1058 || contains_call
1061 {
1064 bitmap conflicts;
1070 });
1073 }
1075 /* Allocate the per basic block info for traversing the insn stream for
1076 building live ranges. */
1078 static void
1080 {
1081 basic_block bb;
1083 {
1089 }
1090 }
1092 /* Free that per basic block info. */
1094 static void
1096 {
1097 basic_block bb;
1099 {
1105 }
1106 }
1108 /* Toplevel function for the first part of this file.
1109 Connect web parts, thereby implicitly building webs, and remember
1110 their conflicts. */
1112 static void
1114 {
1117 basic_block bb;
1123 /* Here's the main loop.
1124 It goes through all insn's, connects web parts along the way, notes
1125 conflicts between webparts, and remembers move instructions. */
1131 {
1134 /* Only recheck marked or new uses, or uses from hardregs. */
1143 visited_pass++;
1147 }
1151 {
1156 }
1159 }
1161 /* Here we look per insn, for DF references being in uses _and_ defs.
1162 This means, in the RTL a (REG xx) expression was seen as a
1163 read/modify/write, as happens for (set (subreg:SI (reg:DI xx)) (...))
1164 e.g. Our code has created two webs for this, as it should. Unfortunately,
1165 as the REG reference is only one time in the RTL we can't color
1166 both webs different (arguably this also would be wrong for a real
1167 read-mod-write instruction), so we must reconnect such webs. */
1169 static void
1171 {
1175 {
1177 rtx reg;
1181 /* If it's an uninitialized web, we don't want to connect it to others,
1182 as the read cycle in read-mod-write had probably no effect. */
1189 {
1192 }
1193 }
1194 }
1196 /* Deletes all hardregs from *S which are not allowed for MODE. */
1198 static void
1200 {
1202 }
1204 /* Initialize the members of a web, which are deducible from REG. */
1206 static void
1208 {
1211 /* web->id isn't initialized here. */
1215 {
1218 }
1219 /* XXX
1220 the former (superunion) doesn't constrain the graph enough. E.g.
1221 on x86 QImode _requires_ QI_REGS, but as alternate class usually
1222 GENERAL_REGS is given. So the graph is not constrained enough,
1223 thinking it has more freedom then it really has, which leads
1224 to repeated spill tryings. OTOH the latter (only using preferred
1225 class) is too constrained, as normally (e.g. with all SImode
1226 pseudos), they can be allocated also in the alternate class.
1227 What we really want, are the _exact_ hard regs allowed, not
1228 just a class. Later. */
1229 /*web->regclass = reg_class_superunion
1230 [reg_preferred_class (web->regno)]
1231 [reg_alternate_class (web->regno)];*/
1232 /*web->regclass = reg_preferred_class (web->regno);*/
1237 {
1245 }
1246 else
1247 {
1248 HARD_REG_SET alternate;
1251 /* add_hardregs is wrong in multi-length classes, e.g.
1252 using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
1253 where, if it finally is allocated to GENERAL_REGS it needs two,
1254 if allocated to FLOAT_REGS only one hardreg. XXX */
1263 /*IOR_HARD_REG_SET (web->usable_regs,
1264 reg_class_contents[reg_alternate_class
1265 (web->regno)]);*/
1269 #ifdef CANNOT_CHANGE_MODE_CLASS
1272 #endif
1277 }
1279 }
1281 /* Initializes WEBs members from REG or zero them. */
1283 static void
1285 {
1289 }
1291 /* WEB is an old web, meaning it came from the last pass, and got a
1292 color. We want to remember some of it's info, so zero only some
1293 members. */
1295 static void
1297 {
1316 {
1320 }
1331 }
1333 /* Insert and returns a subweb corresponding to REG into WEB (which
1334 becomes its super web). It must not exist already. */
1338 {
1343 /* Copy most content from parent-web. */
1345 /* And initialize the private stuff. */
1356 }
1358 /* Similar to add_subweb(), but instead of relying on a given SUBREG,
1359 we have just a size and an offset of the subpart of the REG rtx.
1360 In difference to add_subweb() this marks the new subweb as artificial. */
1364 {
1365 /* To get a correct mode for the to be produced subreg, we don't want to
1366 simply do a mode_for_size() for the mode_class of the whole web.
1367 Suppose we deal with a CDImode web, but search for a 8 byte part.
1368 Now mode_for_size() would only search in the class MODE_COMPLEX_INT
1369 and would find CSImode which probably is not what we want. Instead
1370 we want DImode, which is in a completely other class. For this to work
1371 we instead first search the already existing subwebs, and take
1372 _their_ modeclasses as base for a search for ourself. */
1385 }
1387 /* Initialize all the web parts we are going to need. */
1389 static void
1391 {
1396 {
1398 {
1402 /* Uplink might be set from the last iteration. */
1404 num_webs++;
1405 }
1406 else
1407 /* The last iteration might have left .ref set, while df_analyze()
1408 removed that ref (due to a removed copy insn) from the df->defs[]
1409 array. As we don't check for that in realloc_web_parts()
1410 we do that here. */
1412 }
1414 {
1416 {
1422 num_webs++;
1423 }
1424 else
1426 }
1428 /* We want to have only one web for each precolored register. */
1430 {
1433 /* Here once was a test, if there is any DEF at all, and only then to
1434 merge all the parts. This was incorrect, we really also want to have
1435 only one web-part for hardregs, even if there is no explicit DEF. */
1436 /* Link together all defs... */
1439 {
1443 else
1445 }
1446 /* ... and all uses. */
1449 {
1454 else
1456 }
1457 }
1458 }
1460 /* In case we want to remember the conflict list of a WEB, before adding
1461 new conflicts, we copy it here to orig_conflict_list. */
1463 static void
1465 {
1471 {
1479 {
1482 {
1488 }
1489 }
1490 }
1491 }
1493 /* Possibly add an edge from web FROM to TO marking a conflict between
1494 those two. This is one half of marking a complete conflict, which notes
1495 in FROM, that TO is a conflict. Adding TO to FROM's conflicts might
1496 make other conflicts superfluous, because the current TO overlaps some web
1497 already being in conflict with FROM. In this case the smaller webs are
1498 deleted from the conflict list. Likewise if TO is overlapped by a web
1499 already in the list, it isn't added at all. Note, that this can only
1500 happen, if SUBREG webs are involved. */
1502 static void
1504 {
1506 {
1513 /* This can happen when subwebs of one web conflict with each
1514 other. In live_out_1() we created such conflicts between yet
1515 undefined webparts and defs of parts which didn't overlap with the
1516 undefined bits. Then later they nevertheless could have merged into
1517 one web, and then we land here. */
1523 {
1533 }
1534 else
1535 /* We don't need to test for cl==NULL, because at this point
1536 a cl with cl->t==pto is guaranteed to exist. */
1540 {
1541 /* This is a subconflict which should be added.
1542 If we inserted cl in this invocation, we really need to add this
1543 subconflict. If we did _not_ add it here, we only add the
1544 subconflict, if cl already had subconflicts, because otherwise
1545 this indicated, that the whole webs already conflict, which
1546 means we are not interested in this subconflict. */
1548 {
1554 }
1555 }
1556 else
1557 /* pfrom == from && pto == to means, that we are not interested
1558 anymore in the subconflict list for this pair, because anyway
1559 the whole webs conflict. */
1561 }
1562 }
1564 /* Record a conflict between two webs, if we haven't recorded it
1565 already. */
1567 void
1569 {
1572 /* Trivial non-conflict or already recorded conflict. */
1577 /* As fixed_regs are no targets for allocation, conflicts with them
1578 are pointless. */
1582 /* Conflicts with hardregs, which are not even a candidate
1583 for this pseudo are also pointless. */
1589 /* Similar if the set of possible hardregs don't intersect. This iteration
1590 those conflicts are useless (and would make num_conflicts wrong, because
1591 num_freedom is calculated from the set of possible hardregs).
1592 But in presence of spilling and incremental building of the graph we
1593 need to note all uses of webs conflicting with the spilled ones.
1594 Because the set of possible hardregs can change in the next round for
1595 spilled webs, we possibly have then conflicts with webs which would
1596 be excluded now (because then hardregs intersect). But we actually
1597 need to check those uses, and to get hold of them, we need to remember
1598 also webs conflicting with this one, although not conflicting in this
1599 round because of non-intersecting hardregs. */
1602 {
1605 /* We expect these to be rare enough to justify bitmaps. And because
1606 we have only a special use for it, we note only the superwebs. */
1610 }
1614 }
1616 /* For each web W this produces the missing subwebs Wx, such that it's
1617 possible to exactly specify (W-Wy) for all already existing subwebs Wy. */
1619 static void
1621 {
1627 /* Only create inverses of non-artificial webs. */
1629 {
1633 {
1637 }
1638 }
1639 }
1641 /* Copies the content of WEB to a new one, and link it into WL.
1642 Used for consistency checking. */
1644 static void
1646 {
1653 }
1655 /* Given a list of webs LINK, compare the content of the webs therein
1656 with the global webs of the same ID. For consistency checking. */
1658 static void
1660 {
1663 {
1670 /* Only compare num_defs/num_uses with non-hardreg webs.
1671 E.g. the number of uses of the framepointer changes due to
1672 inserting spill code. */
1676 /* Similarly, if the framepointer was unreferenced originally
1677 but we added spills, these fields may not match. */
1684 {
1692 }
1694 {
1699 }
1701 }
1703 }
1705 /* Setup and fill uses[] and defs[] arrays of the webs. */
1707 static void
1709 {
1712 {
1719 {
1722 }
1729 {
1732 else
1734 }
1738 }
1739 }
1741 /* Called by parts_to_webs(). This creates (or recreates) the webs (and
1742 subwebs) from web parts, gives them IDs (only to super webs), and sets
1743 up use2web and def2web arrays. */
1745 static unsigned int
1748 {
1755 /* For each root web part: create and initialize a new web,
1756 setup def2web[] and use2web[] for all defs and uses, and
1757 id2web for all new webs. */
1761 {
1766 rtx reg;
1775 {
1776 /* If we have a web part root, create a new web. */
1780 /* In the first pass, there are no old webs, so unconditionally
1781 allocate a new one. */
1783 {
1788 }
1789 /* Otherwise, we look for an old web. */
1790 else
1791 {
1792 /* Remember, that use2web == def2web + def_id.
1793 Ergo is def2web[i] == use2web[i - def_id] for i >= def_id.
1794 So we only need to look into def2web[] array.
1795 Try to look at the web, which formerly belonged to this
1796 def (or use). */
1798 /* Or which belonged to this hardreg. */
1802 {
1803 /* If we found one, reuse it. */
1808 }
1809 else
1810 {
1811 /* Otherwise use a new one. First from the free list. */
1814 else
1815 {
1816 /* Else allocate a new one. */
1819 }
1820 }
1821 /* The id is zeroed in init_one_web(). */
1827 else
1831 }
1836 webnum++;
1842 }
1844 /* If this reference already had a web assigned, we are done.
1845 This test better is equivalent to the web being an old web.
1846 Otherwise something is screwed. (This is tested) */
1848 {
1851 /* But if this ref includes a mode change, or was a use live
1852 over an abnormal call, set appropriate flags in the web. */
1862 /* And check, that it's not a newly allocated web. This would be
1863 an inconsistency. */
1867 }
1868 /* In case this was no web part root, we need to initialize WEB
1869 from the ref2web array belonging to the root. */
1871 {
1876 else
1879 }
1881 /* Remember all references for a web in a single linked list. */
1885 /* And the test, that if def2web[i] was NULL above, that we are _not_
1886 an old web. */
1890 /* Possible create a subweb, if this ref was a subreg. */
1892 {
1895 {
1899 }
1900 }
1901 else
1904 /* And look, if the ref involves an invalid mode change. */
1912 /* Setup def2web, or use2web, and increment num_defs or num_uses. */
1914 {
1915 /* Some sanity checks. */
1917 {
1920 {
1923 }
1928 }
1931 }
1932 else
1933 {
1935 {
1938 {
1941 }
1946 }
1951 }
1952 }
1954 /* We better now have exactly as many webs as we had web part roots. */
1959 }
1961 /* This builds full webs out of web parts, without relating them to each
1962 other (i.e. without creating the conflict edges). */
1964 static void
1966 {
1974 /* First build webs and ordinary subwebs. */
1978 /* Setup the webs for hardregs which are still missing (weren't
1979 mentioned in the code). */
1982 {
1987 }
1990 /* Now create all artificial subwebs, i.e. those, which do
1991 not correspond to a real subreg in the current function's RTL, but
1992 which nevertheless is a target of a conflict.
1993 XXX we need to merge this loop with the one above, which means, we need
1994 a way to later override the artificiality. Beware: currently
1995 add_subweb_2() relies on the existence of normal subwebs for deducing
1996 a sane mode to use for the artificial subwebs. */
1998 {
2003 {
2007 }
2013 }
2015 /* And now create artificial subwebs needed for representing the inverse
2016 of some subwebs. This also gives IDs to all subwebs. */
2019 {
2022 {
2027 }
2028 }
2030 /* Now that everyone has an ID, we can setup the id2web array. */
2033 {
2038 }
2043 /* Allocate and clear the conflict graph bitmaps. */
2049 /* Distribute the references to their webs. */
2051 /* And do some sanity checks if old webs, and those recreated from the
2052 really are the same. */
2055 }
2057 /* This deletes all conflicts to and from webs which need to be renewed
2058 in this pass of the allocator, i.e. those which were spilled in the
2059 last pass. Furthermore it also rebuilds the bitmaps for the remaining
2060 conflicts. */
2062 static void
2064 {
2068 {
2070 /* Hardreg webs and non-old webs are new webs (which
2071 need rebuilding). */
2074 }
2077 {
2083 /* First restore the conflict list to be like it was before
2084 coalescing. */
2086 {
2089 }
2093 /* New non-precolored webs, have no conflict list. */
2095 {
2097 /* Useless conflicts will be rebuilt completely. But check
2098 for cleanliness, as the web might have come from the
2099 free list. */
2102 }
2103 else
2104 {
2105 /* Useless conflicts with new webs will be rebuilt if they
2106 are still there. */
2109 /* Go through all conflicts, and retain those to old webs. */
2111 {
2113 {
2117 /* Also restore the entries in the igraph bitmaps. */
2120 /* No subconflicts mean full webs conflict. */
2123 else
2124 /* Else only the parts in cl->sub must be in the
2125 bitmap. */
2126 {
2130 }
2131 }
2132 }
2134 }
2136 }
2138 }
2140 /* For each web check it's num_conflicts member against that
2141 number, as calculated from scratch from all neighbors. */
2143 #if 0
2144 static void
2146 {
2149 {
2158 }
2159 }
2160 #endif
2162 /* Convert the conflicts between web parts to conflicts between full webs.
2164 This can't be done in parts_to_webs(), because for recording conflicts
2165 between webs we need to know their final usable_regs set, which is used
2166 to discard non-conflicts (between webs having no hard reg in common).
2167 But this is set for spill temporaries only after the webs itself are
2168 built. Until then the usable_regs set is based on the pseudo regno used
2169 in this web, which may contain far less registers than later determined.
2170 This would result in us loosing conflicts (due to record_conflict()
2171 thinking that a web can only be allocated to the current usable_regs,
2172 whereas later this is extended) leading to colorings, where some regs which
2173 in reality conflict get the same color. */
2175 static void
2177 {
2188 /* It is possible, that in the conflict bitmaps still some defs I are noted,
2189 which have web_parts[I].ref being NULL. This can happen, when from the
2190 last iteration the conflict bitmap for this part wasn't deleted, but a
2191 conflicting move insn was removed. It's DEF is still in the conflict
2192 bitmap, but it doesn't exist anymore in df->defs. To not have to check
2193 it in the tight loop below, we instead remember the ID's of them in a
2194 bitmap, and loop only over IDs which are not in it. */
2200 /* Now record all conflicts between webs. Note that we only check
2201 the conflict bitmaps of all defs. Conflict bitmaps are only in
2202 webpart roots. If they are in uses, those uses are roots, which
2203 means, that this is an uninitialized web, whose conflicts
2204 don't matter. Nevertheless for hardregs we also need to check uses.
2205 E.g. hardregs used for argument passing have no DEF in the RTL,
2206 but if they have uses, they indeed conflict with all DEFs they
2207 overlap. */
2209 {
2220 {
2225 BITMAP_AND_COMPL);
2226 /* We reduce the number of calls to record_conflict() with this
2227 pass thing. record_conflict() itself also has some early-out
2228 optimizations, but here we can use the special properties of
2229 the loop (constant web1) to reduce that even more.
2230 We once used an sbitmap of already handled web indices,
2231 but sbitmaps are slow to clear and bitmaps are slow to
2232 set/test. The current approach needs more memory, but
2233 locality is large. */
2234 pass++;
2236 /* Note, that there are only defs in the conflicts bitset. */
2239 {
2243 {
2246 }
2247 });
2248 }
2249 }
2255 {
2264 #ifdef STACK_REGS
2265 /* Pseudos can't go in stack regs if they are live at the beginning of
2266 a block that is reached by an abnormal edge. */
2270 #endif
2271 }
2272 }
2274 /* Remember that a web was spilled, and change some characteristics
2275 accordingly. */
2277 static void
2279 {
2285 /* From now on don't use reg_pref/alt_class (regno) anymore for
2286 this web, but instead usable_regs. We can't use spill_temp for
2287 this, as it might get reset later, when we are coalesced to a
2288 non-spill-temp. In that case we still want to use usable_regs. */
2291 /* We don't constrain spill temporaries in any way for now.
2292 It's wrong sometimes to have the same constraints or
2293 preferences as the original pseudo, esp. if they were very narrow.
2294 (E.g. there once was a reg wanting class AREG (only one register)
2295 without alternative class. As long, as also the spill-temps for
2296 this pseudo had the same constraints it was spilled over and over.
2297 Ideally we want some constraints also on spill-temps: Because they are
2298 not only loaded/stored, but also worked with, any constraints from insn
2299 alternatives needs applying. Currently this is dealt with by reload, as
2300 many other things, but at some time we want to integrate that
2301 functionality into the allocator. */
2303 {
2308 }
2309 else
2314 #ifdef CANNOT_CHANGE_MODE_CLASS
2317 #endif
2322 /* Now look for a class, which is subset of our constraints, to
2323 setup add_hardregs, and regclass for debug output. */
2326 {
2328 HARD_REG_SET test;
2333 found:
2334 /* Measure the actual number of bits which really are overlapping
2335 the target regset, not just the reg_class_size. */
2338 {
2341 }
2342 }
2352 }
2354 /* Look at each web, if it is used as spill web. Or better said,
2355 if it will be spillable in this pass. */
2357 static void
2359 {
2363 /* Detect webs used for spill temporaries. */
2365 {
2368 /* Below only the detection of spill temporaries. We never spill
2369 precolored webs, so those can't be spill temporaries. The code above
2370 (remember_web_was_spilled) can't currently cope with hardregs
2371 anyway. */
2374 /* Uninitialized webs can't be spill-temporaries. */
2378 /* A web with only defs and no uses can't be spilled. Nevertheless
2379 it must get a color, as it takes away a register from all webs
2380 live at these defs. So we make it a short web. */
2383 /* A web which was spilled last time, but for which no insns were
2384 emitted (can happen with IR spilling ignoring sometimes
2385 all deaths). */
2388 /* A spill temporary has one def, one or more uses, all uses
2389 are in one insn, and either the def or use insn was inserted
2390 by the allocator. */
2391 /* XXX not correct currently. There might also be spill temps
2392 involving more than one def. Usually that's an additional
2393 clobber in the using instruction. We might also constrain
2394 ourself to that, instead of like currently marking all
2395 webs involving any spill insns at all. */
2396 else
2397 {
2408 {
2410 /* Mark webs involving at least one spill insn as
2411 spill temps. */
2413 /* Search for insns which define and use the web in question
2414 at the same time, i.e. look for rmw insns. If these insns
2415 are also deaths of other webs they might have been counted
2416 as such into web->span_deaths. But because of the rmw nature
2417 of this insn it is no point where a load/reload could be
2418 placed successfully (it would still conflict with the
2419 dead web), so reduce the number of spanned deaths by those
2420 insns. Note that sometimes such deaths are _not_ counted,
2421 so negative values can result. */
2424 {
2428 {
2431 /* Only decrement it once for each insn. */
2434 {
2435 num_deaths--;
2437 }
2438 }
2439 }
2440 /* But mark them specially if they could possibly be spilled,
2441 either because they cross some deaths (without the above
2442 mentioned ones) or calls. */
2445 }
2446 /* A web spanning no deaths can't be spilled either. No loads
2447 would be created for it, ergo no defs. So the insns wouldn't
2448 change making the graph not easier to color. Make this also
2449 a short web. Don't do this if it crosses calls, as these are
2450 also points of reloads. */
2453 }
2455 }
2457 }
2459 /* Returns nonzero if the rtx MEM refers somehow to a stack location. */
2461 int
2463 {
2465 rtx x;
2474 }
2476 /* Returns nonzero, if rtx X somewhere contains any pseudo register. */
2478 static int
2480 {
2486 {
2489 else
2491 }
2496 {
2499 }
2501 {
2506 }
2508 }
2510 /* Returns nonzero, if we are able to rematerialize something with
2511 value X. If it's not a general operand, we test if we can produce
2512 a valid insn which set a pseudo to that value, and that insn doesn't
2513 clobber anything. */
2516 static int
2518 {
2522 /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
2526 /* Otherwise, check if we can make a valid insn from it. First initialize
2527 our test insn if we haven't already. */
2529 {
2530 remat_test_insn
2534 const0_rtx));
2536 }
2538 /* Now make an insn like the one we would make when rematerializing
2539 the value X and see if valid. */
2542 /* XXX For now we don't allow any clobbers to be added, not just no
2543 hardreg clobbers. */
2548 }
2550 /* Look at all webs, if they perhaps are rematerializable.
2551 They are, if all their defs are simple sets to the same value,
2552 and that value is simple enough, and want_to_remat() holds for it. */
2554 static void
2556 {
2559 {
2563 /* Hardregs and useless webs aren't spilled -> no remat necessary.
2564 Defless webs obviously also can't be rematerialized. */
2569 {
2570 rtx insn;
2572 rtx src;
2576 /* When only subregs of the web are set it isn't easily
2577 rematerializable. */
2580 /* If we already have a pattern it must be equal to the current. */
2583 /* Don't do the expensive checks multiple times. */
2586 /* For now we allow only constant sources. */
2588 /* If the whole thing is stable already, it is a source for
2589 remat, no matter how complicated (probably all needed
2590 resources for it are live everywhere, and don't take
2591 additional register resources). */
2592 /* XXX Currently we can't use patterns which contain
2593 pseudos, _even_ if they are stable. The code simply isn't
2594 prepared for that. All those operands can't be spilled (or
2595 the dependent remat webs are not remat anymore), so they
2596 would be oldwebs in the next iteration. But currently
2597 oldwebs can't have their references changed. The
2598 incremental machinery barfs on that. */
2600 /* Additionally also memrefs to stack-slots are useful, when
2601 we created them ourself. They might not have set their
2602 unchanging flag set, but nevertheless they are stable across
2603 the livetime in question. */
2607 /* And we must be able to construct an insn without
2608 side-effects to actually load that value into a reg. */
2611 else
2613 }
2616 }
2617 }
2619 /* Determine the spill costs of all webs. */
2621 static void
2623 {
2626 {
2633 /* Get costs for one load/store. Note that we offset them by 1,
2634 because some patterns have a zero rtx_cost(), but we of course
2635 still need the actual load/store insns. With zero all those
2636 webs would be the same, no matter how often and where
2637 they are used. */
2639 {
2640 /* This web is rematerializable. Beware, we set store_cost to
2641 zero optimistically assuming, that we indeed don't emit any
2642 stores in the spill-code addition. This might be wrong if
2643 at the point of the load not all needed resources are
2644 available, in which case we emit a stack-based load, for
2645 which we in turn need the according stores. */
2648 }
2649 else
2650 {
2655 }
2656 /* We create only loads at deaths, whose number is in span_deaths. */
2664 {
2668 }
2670 }
2671 }
2673 /* Detect webs which are set in a conditional jump insn (possibly a
2674 decrement-and-branch type of insn), and mark them not to be
2675 spillable. The stores for them would need to be placed on edges,
2676 which destroys the CFG. (Somewhen we want to deal with that XXX) */
2678 static void
2680 {
2681 basic_block bb;
2684 {
2688 {
2691 }
2692 }
2693 }
2695 /* Second top-level function of this file.
2696 Converts the connected web parts to full webs. This means, it allocates
2697 all webs, and initializes all fields, including detecting spill
2698 temporaries. It does not distribute moves to their corresponding webs,
2699 though. */
2701 static void
2703 {
2704 /* First build all the webs itself. They are not related with
2705 others yet. */
2707 /* Now detect spill temporaries to initialize their usable_regs set. */
2710 /* And finally relate them to each other, meaning to record all possible
2711 conflicts between webs (see the comment there). */
2715 }
2717 /* Distribute moves to the corresponding webs. */
2719 static void
2721 {
2725 /* Distribute all moves to their corresponding webs, making sure,
2726 each move is in a web maximally one time (happens on some strange
2727 insns). */
2729 {
2737 /* Multiple defs/uses can happen in moves involving hard-regs in
2738 a wider mode. For those df.* creates use/def references for each
2739 real hard-reg involved. For coalescing we are interested in
2740 the smallest numbered hard-reg. */
2743 {
2748 }
2751 {
2756 }
2758 /* If the usable_regs don't intersect we can't coalesce the two
2759 webs anyway, as this is no simple copy insn (it might even
2760 need an intermediate stack temp to execute this "copy" insn). */
2763 {
2765 {
2769 {
2774 }
2778 {
2783 }
2784 }
2785 }
2786 else
2787 /* Delete this move. */
2789 }
2790 }
2792 /* Handle tricky asm insns.
2793 Supposed to create conflicts to hardregs which aren't allowed in
2794 the constraints. Doesn't actually do that, as it might confuse
2795 and constrain the allocator too much. */
2797 static void
2799 {
2804 rtx pat;
2813 {
2818 }
2824 {
2828 rtx reg;
2833 /* Look, if the constraints apply to a pseudo reg, and not to
2834 e.g. a mem. */
2843 /* Search the web corresponding to this operand. We depend on
2844 that decode_asm_operands() places the output operands
2845 before the input operands. */
2847 {
2850 else
2855 {
2858 else
2860 }
2861 else
2863 }
2866 else
2870 /* Find the constraints, noting the allowed hardregs in allowed. */
2873 {
2877 {
2878 /* End of one alternative - mark the regs in the current
2879 class, and reset the class. */
2880 p++;
2892 }
2895 {
2916 cls =
2919 p)];
2920 }
2922 }
2924 /* Now make conflicts between this web, and all hardregs, which
2925 are not allowed by the constraints. */
2927 {
2928 /* If we had no real constraints nothing was explicitly
2929 allowed, so we allow the whole class (i.e. we make no
2930 additional conflicts). */
2932 }
2933 else
2934 {
2940 /* We can't yet establish these conflicts. Reload must go first
2941 (or better said, we must implement some functionality of reload).
2942 E.g. if some operands must match, and they need the same color
2943 we don't see yet, that they do not conflict (because they match).
2944 For us it looks like two normal references with different DEFs,
2945 so they conflict, and as they both need the same color, the
2946 graph becomes uncolorable. */
2947 #if 0
2951 #endif
2952 }
2954 {
2961 }
2962 }
2963 }
2965 /* The real toplevel function in this file.
2966 Build (or rebuilds) the complete interference graph with webs
2967 and conflicts. */
2969 void
2971 {
2972 rtx insn;
2981 /* For read-modify-write instructions we may have created two webs.
2982 Reconnect them here. (s.a.) */
2985 /* The webs are conceptually complete now, but still scattered around as
2986 connected web parts. Collect all information and build the webs
2987 including all conflicts between webs (instead web parts). */
2991 /* Look for additional constraints given by asms. */
2994 }
2996 /* Allocates or reallocates most memory for the interference graph and
2997 associated structures. If it reallocates memory (meaning, this is not
2998 the first pass), this also changes some structures to reflect the
2999 additional entries in various array, and the higher number of
3000 defs and uses. */
3002 void
3004 {
3018 /* First go through all old defs and uses. */
3020 {
3021 /* And relocate them to the new array. This is made ugly by the
3022 fact, that defs and uses are placed consecutive into one array. */
3030 /* Also relocate the uplink to point into the new array. */
3032 {
3035 {
3038 }
3041 }
3042 }
3044 /* Also set up the def2web and use2web arrays, from the last pass.i
3045 Remember also the state of live_over_abnormal. */
3047 {
3050 {
3054 }
3055 }
3057 {
3060 {
3064 }
3067 }
3069 /* We don't have any subwebs for now. Somewhen we might want to
3070 remember them too, instead of recreating all of them every time.
3071 The problem is, that which subwebs we need, depends also on what
3072 other webs and subwebs exist, and which conflicts are there.
3073 OTOH it should be no problem, if we had some more subwebs than strictly
3074 needed. Later. */
3076 {
3080 {
3083 }
3085 }
3087 /* The uses we anyway are going to check, are not yet live over an abnormal
3088 edge. In fact, they might actually not anymore, due to added
3089 loads. */
3092 last_check_uses);
3095 {
3099 }
3101 {
3102 /* Setup copy cache, for copy_insn_p (). */
3105 }
3106 else
3107 {
3111 }
3112 }
3114 /* Free up/clear some memory, only needed for one pass. */
3116 void
3118 {
3122 /* Clear the moves associated with a web (we also need to look into
3123 subwebs here). */
3125 {
3133 }
3134 /* All webs in the free list have no defs or uses anymore. */
3136 {
3144 /* We can't free the subwebs here, as they are referenced from
3145 def2web[], and possibly needed in the next ra_build_realloc().
3146 We free them there (or in free_all_mem()). */
3147 }
3149 /* Free all conflict bitmaps from web parts. Note that we clear
3150 _all_ these conflicts, and don't rebuild them next time for uses
3151 which aren't rechecked. This mean, that those conflict bitmaps
3152 only contain the incremental information. The cumulative one
3153 is still contained in the edges of the I-graph, i.e. in
3154 conflict_list (or orig_conflict_list) of the webs. */
3156 {
3159 {
3162 }
3164 }
3172 }
3174 /* Free all memory for the interference graph structures. */
3176 void
3178 {
3185 {
3188 {
3191 }
3193 }
3203 }
3207 /*
3208 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
3209 */