Hello,
gdb currently displays the contents of set variables wrongly on big endian machines for at least GPC and FPC. The reason is that it treats a set as a linear array of bits, while both GPC and FPC treat it as an array of ordinals in which bits are set using "1 shl (elementnr mod sizeof(ordinal))".
The problem with creating a patch is that in FPC the size of this ordinal is always 32 bit, while on GPC it is MedCard (which is 64 bit on 64 bit architectures). The main reasons for FPC to always use 32 bits are
a) binary compatibility b) performance (even on 64 bit machines, loading/storing a 32 bit value from/to memory is often faster)
I have found several mails in the archives of this list noting that people should not rely on GPC sets having a particular format, so I wonder whether this could be changed in GPC? Regardless of those warnings, I guess it will still cause problems (the same binary compatibility mentioned above, for people who created data files containing sets on 64 bit machines with GPC), but it will also have advantages (making files containing sets compatible with both 32 and 64 bit apps compiled by GPC).
If someone sees a way to automatically detect the used set format inside gdb itself, that would be great as well of course.
What do you think?
Jonas
PS: I've attached a patch to gdb which fixes the problem for big endian FPC and 32 bit GPC apps. I think it may still have to be changed to not treat bitstrings differently from sets, because the stabs docs (http://www.cygwin.com/stabs.html) state:
--- S Indicate that this type is a string instead of an array of characters, or a bitstring instead of a set. It doesn't change the layout of the data being represented, but does enable the debugger to know which type it is. ---
What are "bitstrings" in Pascal anyway? gdb displays them as
B'1..3,5,7' (sets are printed as [1..3,5,7])
so they don't seem to be the same as a bit-packed array of boolean or so.
PS2: the patch was created against Apple's gdb-477. However it applies cleanly to plain GNU gdb (cvs version) as well (with a few line offset differences)
Jonas Maebe wrote:
Hello,
gdb currently displays the contents of set variables wrongly on big endian machines for at least GPC and FPC. The reason is that it treats a set as a linear array of bits, while both GPC and FPC treat it as an array of ordinals in which bits are set using "1 shl (elementnr mod sizeof(ordinal))".
I am surprised, but AFAICS you are right (ATM I can not test on a big endian machine (no gdb there), but the problem already appears on little endian machines).
The problem with creating a patch is that in FPC the size of this ordinal is always 32 bit, while on GPC it is MedCard (which is 64 bit on 64 bit architectures).
I do not know what FPC is doing, but GPC also "aligns" sets, so for example `set of 11..37' is stored as a subset of `set of 0..37'. gdb has no idea of set alignment, so such set are printed wrong even on little endian machines.
The main reasons for FPC to always use 32 bits are
a) binary compatibility b) performance (even on 64 bit machines, loading/storing a 32 bit value from/to memory is often faster)
I think that there is a subtle iteraction between space usage and instruction count. For data-heavy program storing sets as byte sequences will minimize space usage which may pay reducing cache misses. OTOH 64 bit machines tend to have 64 bit buses, so working in cache machine should handle 64 bit chunk as fast as 32 bit chunk. Hence, for mass operations (copy, sum or intersection) on moderate or large sets 64 bit chunks should give much better speed then 32 bit chunks.
I have found several mails in the archives of this list noting that people should not rely on GPC sets having a particular format, so I wonder whether this could be changed in GPC? Regardless of those warnings, I guess it will still cause problems (the same binary compatibility mentioned above, for people who created data files containing sets on 64 bit machines with GPC), but it will also have advantages (making files containing sets compatible with both 32 and 64 bit apps compiled by GPC).
In principle we can change set representation. In fact, there is one change that I intend to do in the future: currently even the smalles set use a MedCard sized word, I plan to allocate smaller space for them (smallest unit which can represent them). OTOH I am not convinced that always using 32 bit chunks for sets is the best choice. GPC on 64 bit machines uses 64 bit types in so many places that I doubt in usefulness of having the same set representation (and still big endian machines would use different representation than little endian).
If someone sees a way to automatically detect the used set format inside gdb itself, that would be great as well of course.
What do you think?
My first thought was to change GPC representation to match gdb, but while we can rather easily (and with minor performance impact) change bit order in sets, the alignment problem remains...
Technically in the compiler proper the change would be just to set a few parameters to different value. The main change would be to runtime support. Here we depend very much on set alignment (of course removing alignment is doable, but we would get both lower performing and more complicated code).
I am affraid that set representation affects not only FPC and GPC. There is also GNU Modula-2 (would be nice to be able to have calling convention compatibility with Modula-2). AFAIK now Modula-2 uses default gcc (which is the same as gdb) representation.
Also, most RISC vendors had Pascal compilers. It seems that now vendors are dropping Pascal support, but for gdb this may be an issue.
In principle gdb could try to detect the compiler: gpc uses some pretty characteristic symbols (like `_p_GPC_RTS_VERSION_20060215') and I suspect that FPC is doing something similar.
Jonas
PS: I've attached a patch to gdb which fixes the problem for big endian FPC and 32 bit GPC apps. I think it may still have to be changed to not treat bitstrings differently from sets, because the stabs docs (http://www.cygwin.com/stabs.html) state:
S Indicate that this type is a string instead of an array of characters, or a bitstring instead of a set. It doesn't change the layout of the data being represented, but does enable the debugger to know which type it is.
What are "bitstrings" in Pascal anyway? gdb displays them as
B'1..3,5,7' (sets are printed as [1..3,5,7])
so they don't seem to be the same as a bit-packed array of boolean or so.
Bitstrings are Chill speciality (Chill has both sets and bitstrings, they share most of backend support in gcc). Chill is included in gcc-2.95.x and AFAICS its data representation agrees with current gdb.
Waldek Hebisch wrote:
The main reasons for FPC to always use 32 bits are
a) binary compatibility b) performance (even on 64 bit machines, loading/storing a 32 bit value from/to memory is often faster)
I think that there is a subtle iteraction between space usage and instruction count. For data-heavy program storing sets as byte sequences will minimize space usage which may pay reducing cache misses. OTOH 64 bit machines tend to have 64 bit buses, so working in cache machine should handle 64 bit chunk as fast as 32 bit chunk. Hence, for mass operations (copy, sum or intersection) on moderate or large sets 64 bit chunks should give much better speed then 32 bit chunks.
Also things might change in the future, more likely to favour 64 bit access, so I don't think we should optimize too much for today's and yesterday's machines.
If someone sees a way to automatically detect the used set format inside gdb itself, that would be great as well of course.
What do you think?
My first thought was to change GPC representation to match gdb, but while we can rather easily (and with minor performance impact) change bit order in sets, the alignment problem remains...
Technically in the compiler proper the change would be just to set a few parameters to different value. The main change would be to runtime support. Here we depend very much on set alignment (of course removing alignment is doable, but we would get both lower performing and more complicated code).
Yes. I don't think that's worth it to please the debugger. I don't suppose there's a way to get GNU Modula 2 to align as well (should be more efficient for them, too), is there?
In principle gdb could try to detect the compiler: gpc uses some pretty characteristic symbols (like `_p_GPC_RTS_VERSION_20060215') and I suspect that FPC is doing something similar.
A nicer way would be to attach the necessary information to the type debugging info (e.g., a flag for alignment, and a size info or a base type for the size issue). I'm not sure what the various debug info formats support, though ...
BTW, one way to get rid of the size dependence (but not alignment) would be to be fully big-endian on big-endian machines, i.e. store the highest words first. That would also require code changes, but not nearly as much as removing alignment, and also only incur a minor performance hit, I think. Then it wouldn't matter whether they're accessed in 64 or 32 bit parts or whatever (modulo alignment padding, but this could perhaps be inferred from the total size). It wouldn't be compatible with FPC either, AIUI ...
Frank
On 1 aug 2006, at 23:53, Waldek Hebisch wrote:
I do not know what FPC is doing, but GPC also "aligns" sets, so for example `set of 11..37' is stored as a subset of `set of 0..37'. gdb has no idea of set alignment, so such set are printed wrong even on little endian machines.
FPC does the same. I never noticed it because I rarely if ever use such non-zero based subrange types.
The main reasons for FPC to always use 32 bits are
a) binary compatibility b) performance (even on 64 bit machines, loading/storing a 32 bit value from/to memory is often faster)
I think that there is a subtle iteraction between space usage and instruction count. For data-heavy program storing sets as byte sequences will minimize space usage which may pay reducing cache misses. OTOH 64 bit machines tend to have 64 bit buses, so working in cache machine should handle 64 bit chunk as fast as 32 bit chunk.
If the set is aligned to 64 bit, and once the set is in the cache, possibly. At least the G5 has only two 32 bit busses from the cpu to memory (one for loads and one for stores).
Anyway, you could still do the adding/subbing/... of sets by typecasting the set to a MedCard array of the appropriate size. This issue is only with inserting/removing/testing elements (and in that case you're doing more or less random access, so there is less chance that the chunk you need is already in the cache).
In principle we can change set representation. In fact, there is one change that I intend to do in the future: currently even the smalles set use a MedCard sized word, I plan to allocate smaller space for them (smallest unit which can represent them).
There have been plans for a long time to do that in FPC as well. If you do this as meticulously as Delphi does (its set size grows by 1 byte at a time), then you more or less need by definition a little- endian representation of sets in all cases though (because of the left-over bytes at the end).
For this reason, a number of FPC developers are in favour of using "little endian" sets on all platforms. I'm a bit wary of breaking backwards binary compatibility though, and possibly also compatibility with other big endian Pascal compilers (does anyone know how CodeWarrior/PPC and/or Think Pascal store their sets?)
OTOH I am not convinced that always using 32 bit chunks for sets is the best choice. GPC on 64 bit machines uses 64 bit types in so many places that I doubt in usefulness of having the same set representation
Possibly.
(and still big endian machines would use different representation than little endian).
Big and little endian machines using different representations is logical, and people porting from little to big endian (and vice versa) are used to add byte swapping code all over the place.
If someone sees a way to automatically detect the used set format inside gdb itself, that would be great as well of course.
What do you think?
My first thought was to change GPC representation to match gdb, but while we can rather easily (and with minor performance impact) change bit order in sets, the alignment problem remains...
Well, those are two different issues, I think, which can be solved separately.
Technically in the compiler proper the change would be just to set a few parameters to different value. The main change would be to runtime support. Here we depend very much on set alignment (of course removing alignment is doable, but we would get both lower performing and more complicated code).
Indeed.
I am affraid that set representation affects not only FPC and GPC. There is also GNU Modula-2 (would be nice to be able to have calling convention compatibility with Modula-2). AFAIK now Modula-2 uses default gcc (which is the same as gdb) representation.
Marco also already suggested to involve a Modula-2 developer.
In principle gdb could try to detect the compiler: gpc uses some pretty characteristic symbols (like `_p_GPC_RTS_VERSION_20060215') and I suspect that FPC is doing something similar.
There are indeed a lof of FPC_* symbols, but I don't really like such a solution, and I'm not sure whether the gdb people would like that either.
PS: I've attached a patch to gdb which fixes the problem for big endian FPC and 32 bit GPC apps. I think it may still have to be changed to not treat bitstrings differently from sets, because the stabs docs (http://www.cygwin.com/stabs.html) state:
Note: my patch is not really correct. The reason is that gdb's bit testing routine checks whether the bit to be tested lies between the high and low bound of the set member type. So unless you have set of a type which has a multiple of 32 elements, you get a lot of "<error type>" errors from gdb even if it's zero-based (since my patch takes the 32-complement of the bit to be tested).
I had only quickly tested it with a "set of byte", for which it obviously worked properly.
Jonas
Jonas Maebe wrote:
Anyway, you could still do the adding/subbing/... of sets by typecasting the set to a MedCard array of the appropriate size. This issue is only with inserting/removing/testing elements (and in that case you're doing more or less random access, so there is less chance that the chunk you need is already in the cache).
There is still issue of alignment: we need alignment to avoid shifts when lower bounds do not match, also set variables must be allocated on proper (word) boundary. Looks messy.
In principle we can change set representation. In fact, there is one change that I intend to do in the future: currently even the smalles set use a MedCard sized word, I plan to allocate smaller space for them (smallest unit which can represent them).
There have been plans for a long time to do that in FPC as well. If you do this as meticulously as Delphi does (its set size grows by 1 byte at a time), then you more or less need by definition a little- endian representation of sets in all cases though (because of the left-over bytes at the end).
I would say proper big endian representation. Currently both GPC and FPC use little endian bit order for set hunks, which conflicts with big endian byte order. Using big endian bit order would remove this discrepancy. However, I think about much simpler scheme, trying to allocate 1, 2, 4, 8 bytes (in that order) and if that fails allocating sequence of 8 byte words (all that assuming 64 bit machine, with obvious changes for other wordlengths). The main reason is that with such a scheme one can perform operations on small sets inline, using just a couple of instructions. Delphi way require rather complicated instruction sequence or special runtime routines.
For this reason, a number of FPC developers are in favour of using "little endian" sets on all platforms. I'm a bit wary of breaking backwards binary compatibility though, and possibly also compatibility with other big endian Pascal compilers (does anyone know how CodeWarrior/PPC and/or Think Pascal store their sets?)
I do not know. But I have looked into XL Pascal and Sun Pascal manuals. Both claim that set are implemented as bitstrings. XL Pascal limits sets to 256 elements and all of them are 0 based. It looks that Sun Pascal aligns sets, but the manulal omits exact rules. The manuals are pretty imprecise, but at least Sun example show that bits are stored in consequitive byte (but I was not able to find specification of bit order).
(and still big endian machines would use different representation than little endian).
Big and little endian machines using different representations is logical, and people porting from little to big endian (and vice versa) are used to add byte swapping code all over the place.
I got used to adding changes going from 32 bit machine to 64 bit system.
If someone sees a way to automatically detect the used set format inside gdb itself, that would be great as well of course.
What do you think?
My first thought was to change GPC representation to match gdb, but while we can rather easily (and with minor performance impact) change bit order in sets, the alignment problem remains...
Well, those are two different issues, I think, which can be solved separately.
Hmm, let me see: if we use natural alignment (to the chunk boundary) and the set needs bigger alignment then the size of variable gets bigger. So we can detect alignment used from the set bound and size of the set variable. AFAIK it is possible to tell gdb about correct size. So, if we agree to use natural alignment gdb can detect the exact amount used (sometimes it can not detect if alignment is used at all, so gdb must know if the natural alignment rule is used).
So, ATM for me bit reversal (plus teaching gdb about alignment) is the most attractive solution.
In principle gdb could try to detect the compiler: gpc uses some pretty characteristic symbols (like `_p_GPC_RTS_VERSION_20060215') and I suspect that FPC is doing something similar.
There are indeed a lof of FPC_* symbols, but I don't really like such a solution, and I'm not sure whether the gdb people would like that either.
AFAICS any method to choose between set representations is going to be non-standard. I am not sure if some ad hoc extensions to format of debug info are better.
Waldek Hebisch wrote:
Jonas Maebe wrote:
Anyway, you could still do the adding/subbing/... of sets by typecasting the set to a MedCard array of the appropriate size. This issue is only with inserting/removing/testing elements (and in that case you're doing more or less random access, so there is less chance that the chunk you need is already in the cache).
There is still issue of alignment: we need alignment to avoid shifts when lower bounds do not match, also set variables must be allocated on proper (word) boundary. Looks messy.
I agree.
There have been plans for a long time to do that in FPC as well. If you do this as meticulously as Delphi does (its set size grows by 1 byte at a time), then you more or less need by definition a little- endian representation of sets in all cases though (because of the left-over bytes at the end).
I would say proper big endian representation. Currently both GPC and FPC use little endian bit order for set hunks, which conflicts with big endian byte order.
Indeed, it's a bit strange as it is now. Using proper big endian representation we'd be independent of word size (though not alignment). The byte order would then be the same between big and little endian machines, though not the bit order within a byte, so no binary compatibility (but we don't have that now, so we wouldn't lose anything).
Using big endian bit order would remove this discrepancy. However, I think about much simpler scheme, trying to allocate 1, 2, 4, 8 bytes (in that order) and if that fails allocating sequence of 8 byte words (all that assuming 64 bit machine, with obvious changes for other wordlengths). The main reason is that with such a scheme one can perform operations on small sets inline, using just a couple of instructions.
Seems reasonable.
Delphi way require rather complicated instruction sequence or special runtime routines.
I'd imagine so. I don't think that's worth it for larger sets (saving a byte at some performance cost or so), so we shouldn't bother.
Hmm, let me see: if we use natural alignment (to the chunk boundary) and the set needs bigger alignment then the size of variable gets bigger. So we can detect alignment used from the set bound and size of the set variable. AFAIK it is possible to tell gdb about correct size. So, if we agree to use natural alignment gdb can detect the exact amount used (sometimes it can not detect if alignment is used at all, so gdb must know if the natural alignment rule is used).
So, ATM for me bit reversal (plus teaching gdb about alignment) is the most attractive solution.
AFAICS any method to choose between set representations is going to be non-standard. I am not sure if some ad hoc extensions to format of debug info are better.
If we can get the extensions working through the backend and gdb, and perhaps even "officially" approved, I'd certainly prefer this. Otherwise, the "alignment detection", though it seems a bit backward, looks best to me.
Frank
On 02 Aug 2006, at 22:16, Frank Heckenbach wrote:
Waldek Hebisch wrote:
There is still issue of alignment: we need alignment to avoid shifts when lower bounds do not match, also set variables must be allocated on proper (word) boundary. Looks messy.
I agree.
Allocation on a proper word boundary can be easily done by keeping the format as an array of MedCard, and only typecasting to something else inside the set/test/remove helpers.
I think the alignment issue could in that case be handled in the same way as deciding the size of sets mentioned by Waldek below (a tradeoff of size vs efficiency).
I would say proper big endian representation. Currently both GPC and FPC use little endian bit order for set hunks, which conflicts with big endian byte order.
Indeed, it's a bit strange as it is now.
I personally don't consider it strange since all cpu's I know of have the same endianess as far as bit ordering is concerned (regardless of their byte endianess). At least there's no architecture I know of where the byte with value 1 is represented as $80.
Using proper big endian representation we'd be independent of word size (though not alignment). The byte order would then be the same between big and little endian machines, though not the bit order within a byte, so no binary compatibility (but we don't have that now, so we wouldn't lose anything).
Bit swapping when porting from big to little endian is a lot less obvious than byte swapping though. We'd at least have to provide routines to do this (maybe GPC has them already, but FPC doesn't).
That said, there are two big arguments in favour of using that solution (i.e., treating sets basically as packed bit arrays on big endian architectures):
a) gdb has a define called BITS_BIG_ENDIAN which is set to the same value as the byte endianess of the target architecture. If this define is set, it currently treats sets as packed bit arrays on big endian architectures (but not on little endian architectures, there it treats them the same way as FPC and GPC currently store their sets). b) at least Think Pascal also uses this set format. I do not have MW Pascal to test against.
Using big endian bit order would remove this discrepancy. However, I think about much simpler scheme, trying to allocate 1, 2, 4, 8 bytes (in that order) and if that fails allocating sequence of 8 byte words (all that assuming 64 bit machine, with obvious changes for other wordlengths). The main reason is that with such a scheme one can perform operations on small sets inline, using just a couple of instructions.
Seems reasonable.
To me as well overall, although I'm personally in favour of always using the same cut-off and extension sizes regardless of the native word size (e.g. 1, 2, 4, 8, 12, 16, ... everywhere) to keep same sets the same size on 32 and 64 bit archs.
Making people extend their set base types so the sets are a multiple of 8 bytes on both 32 and 64 bit archs seems awkward: it may mess up bit-packed records elsewhere as well, and for enums it may amount to adding a bunch of dummy enum elements (which doesn't look nice either).
If we can get the extensions working through the backend and gdb, and perhaps even "officially" approved, I'd certainly prefer this. Otherwise, the "alignment detection", though it seems a bit backward, looks best to me.
I agree. Concerning M2: it uses a hack for (some?) larger sets (m2- valprint.c):
case TYPE_CODE_STRUCT: if (m2_is_long_set (type)) m2_print_long_set (type, valaddr, embedded_offset, address, stream, format, pretty);
else cp_print_value_fields (type, type, valaddr, embedded_offset, address, stream, format, recurse, pretty, NULL, 0);
m2_is_long_set checks if all the fields of the record are consecutive sets (i.e. sets of consecutive range types). I don't really understand why this is useful though, nor do I see at first sight what m2_print_long_set does so differently compared to the M2 print code for TYPE_CODE_SET.
But for some reason it gave me an easy idea to solve the gdb alignment problem we have: even if it's a set of 48..50 (which we will store as a set of 0..63), put in the debug info that it's a set of 0..50 and gdb will print everything correctly.
Jonas
Jonas Maebe wrote:
I would say proper big endian representation. Currently both GPC and FPC use little endian bit order for set hunks, which conflicts with big endian byte order.
Indeed, it's a bit strange as it is now.
I personally don't consider it strange since all cpu's I know of have the same endianess as far as bit ordering is concerned (regardless of their byte endianess). At least there's no architecture I know of where the byte with value 1 is represented as $80.
I think that's a tautology, as we don't see the internal representation (i.e., which bit of memory is actually used), but we consider the value 1 (i.e., the value which behaves like 1 in operations) as being represented as 1.
What I think is strange is when you look at the byte order with current (GPC and apparently also FPC) sets on big-endian machines, e.g. for a 0-based set on a 32 bit machine:
Byte Elements 0 24..31 1 16..23 2 8..15 3 0..7 4 56..63 5 48..55
etc.
This is because the bytes within a word are big-endian, but we always treat the sequence of words as little-endian (lowest elements first), so we actually get a mixed endianness when considering set elements.
Using proper big endian representation, as Waldek suggested, would mean reversing the bits in a word, so we'd get
Byte Elements 0 0..7 1 8..15 2 16..23 3 24..31 4 32..39 5 40..47
just like on little-endian.
Indeed, it would also reverse the order of elements in a byte (perhaps that's what you meant above), so the set element 1, e.g., wouldn't correspond to the "bit #1", i.e. value 2, anymore, but instead "bit #6", i.e. value $40.
BTW, actually I used to wonder about the latter when I previously saw it on its own (WRT packed arrays IIRC). Why put the lowest-indexed values in the highest-values bits? But when looking at it in the context of words, as above, it makes sense. (Because if you don't, i.e. want to have the same byte order and bit order as on little-endian, you get strange shifts, like 24 for element 0, 25 for 1, ..., 31 for 7, 16 for 8, 17 for 9, ... This is awkward for single elements already, but really gets ugly when you need bit-masks for ranges etc.)
Using proper big endian representation we'd be independent of word size (though not alignment). The byte order would then be the same between big and little endian machines, though not the bit order within a byte, so no binary compatibility (but we don't have that now, so we wouldn't lose anything).
Bit swapping when porting from big to little endian is a lot less obvious than byte swapping though. We'd at least have to provide routines to do this (maybe GPC has them already, but FPC doesn't).
I don't think we have such a routine, but it wouldn't be hard to provide one (probably table-based for efficiency).
Using big endian bit order would remove this discrepancy. However, I think about much simpler scheme, trying to allocate 1, 2, 4, 8 bytes (in that order) and if that fails allocating sequence of 8 byte words (all that assuming 64 bit machine, with obvious changes for other wordlengths). The main reason is that with such a scheme one can perform operations on small sets inline, using just a couple of instructions.
Seems reasonable.
To me as well overall, although I'm personally in favour of always using the same cut-off and extension sizes regardless of the native word size (e.g. 1, 2, 4, 8, 12, 16, ... everywhere) to keep same sets the same size on 32 and 64 bit archs.
Making people extend their set base types so the sets are a multiple of 8 bytes on both 32 and 64 bit archs seems awkward: it may mess up bit-packed records elsewhere as well, and for enums it may amount to adding a bunch of dummy enum elements (which doesn't look nice either).
You seem to be very concerned with sets in binary file formats, judging from these and previous concerns. I admit that's not such a big concern of mine (in particular, in contrast to runtime efficiency, or proper gdb support, of course). Actually I haven't seen many file formats containing sets. That's probably because many languages don't have sets, so file formats that should be accessible from different languages probably use bit-fields or something like this instead.
If we can get the extensions working through the backend and gdb, and perhaps even "officially" approved, I'd certainly prefer this. Otherwise, the "alignment detection", though it seems a bit backward, looks best to me.
I agree. Concerning M2: it uses a hack for (some?) larger sets (m2- valprint.c):
case TYPE_CODE_STRUCT: if (m2_is_long_set (type)) m2_print_long_set (type, valaddr, embedded_offset, address, stream, format, pretty); else cp_print_value_fields (type, type, valaddr, embedded_offset, address, stream, format, recurse, pretty, NULL, 0);
m2_is_long_set checks if all the fields of the record are consecutive sets (i.e. sets of consecutive range types). I don't really understand why this is useful though, nor do I see at first sight what m2_print_long_set does so differently compared to the M2 print code for TYPE_CODE_SET.
I don't currently have the time to check the code carefully, but since you speak of a record, does the compiler divide large sets internally into record fields (so the debugger has to reassemble them to look as one set), or something like this? (Otherwise I wonder when a programmer would use "consecutive sets" manually.)
But for some reason it gave me an easy idea to solve the gdb alignment problem we have: even if it's a set of 48..50 (which we will store as a set of 0..63), put in the debug info that it's a set of 0..50 and gdb will print everything correctly.
Well, I think we make sure that unused bits are stored as 0, so it wouldn't print any spurious values.
OTOH, the gcc backend generates most of the debug info from the type information itself, so I don't know if we easily "fake" it. (In another case we tried lying to the backend, it failed badly.) Maybe it wouldn't be as bad here since the memory layout wouldn't change, but we'd probably need to store the real bounds (for range-checking etc.) elsewhere. I'm not sure if this will work well. Waldek?
Frank
On 06 Aug 2006, at 00:40, Frank Heckenbach wrote:
Jonas Maebe wrote:
[snip]
What I think is strange is when you look at the byte order with current (GPC and apparently also FPC) sets on big-endian machines, e.g. for a 0-based set on a 32 bit machine:
Byte Elements 0 24..31 1 16..23 2 8..15 3 0..7 4 56..63 5 48..55
etc.
This is because the bytes within a word are big-endian, but we always treat the sequence of words as little-endian (lowest elements first), so we actually get a mixed endianness when considering set elements.
I disagree that for sets this is strange, if only for the reason that apparently both the GPC and FPC implementors did it that way independently, and without any hacking or ugly workarounds.
On the contrary, this representation is extremely convenient because it allows one to implement all set routines in an endian-agnostic way (both in the rtl/rts and in the compiler), and the only thing needed to load the values from one endianess architecture on another is byte- swapping.
At a very low level it may seem strange once you start to think about it (I also thought it to be strange the first time I realised this), but does that matter if it's easy to work with it at a high level? (both for the compiler implementors and the end-users no less)
Indeed, it would also reverse the order of elements in a byte (perhaps that's what you meant above), so the set element 1, e.g., wouldn't correspond to the "bit #1", i.e. value 2, anymore, but instead "bit #6", i.e. value $40.
This is indeed what I was referring to.
BTW, actually I used to wonder about the latter when I previously saw it on its own (WRT packed arrays IIRC). Why put the lowest-indexed values in the highest-values bits? But when looking at it in the context of words, as above, it makes sense. (Because if you don't, i.e. want to have the same byte order and bit order as on little-endian, you get strange shifts, like 24 for element 0, 25 for 1, ..., 31 for 7, 16 for 8, 17 for 9, ... This is awkward for single elements already, but really gets ugly when you need bit-masks for ranges etc.)
As long as you treat the set as an "array" of components of the same size which is used when inserting/testing/deleting elements, your range code can remain generic (as e.g. GPC's SetIncludeRange demonstrates). Of course, to make sets binary compatible between little and big endian archs you have to use bytes as opposed to words when doing these operations, and therefore you'd have to do the same with the range code.
For adding/substracting/... it wouldn't make a difference, of course; they could keep working on words.
Bit swapping when porting from big to little endian is a lot less obvious than byte swapping though. We'd at least have to provide routines to do this (maybe GPC has them already, but FPC doesn't).
I don't think we have such a routine, but it wouldn't be hard to provide one (probably table-based for efficiency).
Indeed.
Making people extend their set base types so the sets are a multiple of 8 bytes on both 32 and 64 bit archs seems awkward: it may mess up bit-packed records elsewhere as well, and for enums it may amount to adding a bunch of dummy enum elements (which doesn't look nice either).
You seem to be very concerned with sets in binary file formats, judging from these and previous concerns.
I am indeed. These sort of issues can waste a lot of programmer time when going from one platform to another, which could be spent on much more useful things.
I admit that's not such a big concern of mine (in particular, in contrast to runtime efficiency, or proper gdb support, of course). Actually I haven't seen many file formats containing sets. That's probably because many languages don't have sets, so file formats that should be accessible from different languages probably use bit-fields or something like this instead.
It would at least be a problem for FPC itself. Our ppu files (comparable to a combination of GPC's .gpd and .gpi files) contain a ton of sets. Flags describing properties of functions/proceedures, variables, types, ... are all sets in FPC, and all are stored that way in the .ppu files.
If sets have different sizes on 32 and 64 bit archs, the compiler would need hacks in the ppu writing and reading routines if we want to keep the ability to cross-compile usable ppu files from 32 bit to 64 bit platforms (and vice versa). Similar for ppudump, which "disassembles" ppu files.
Sets may indeed be rare in datafiles used among a lot of different programming environments, but they are quite common in datafiles for use by a single Pascal program (simply because may be no need to make them easily accessible from other languages, like e.g. our ppu files, and because sets are a first class datatype in Pascal).
m2_is_long_set checks if all the fields of the record are consecutive sets (i.e. sets of consecutive range types). I don't really understand why this is useful though, nor do I see at first sight what m2_print_long_set does so differently compared to the M2 print code for TYPE_CODE_SET.
I don't currently have the time to check the code carefully, but since you speak of a record, does the compiler divide large sets internally into record fields (so the debugger has to reassemble them to look as one set), or something like this?
That's what it looks like, yes. The code I posted came from gdb, not gcc though. I don't know Modula-2, and I know next to nothing of gcc internals, so I don't feel like diving into that.
(Otherwise I wonder when a programmer would use "consecutive sets" manually.)
I'm also pretty sure the compiler does it, but as I said I have no idea why it does this since at first sight I can't determine a difference in binary layout compared to the conventional TYPE_CODE_SET way, or what gdb does differently for the two (apart from the fact that the routine for printing these record-sets is a lot more complex than the regular one because it has to hop from field to field).
Jonas
Jonas Maebe wrote:
On 06 Aug 2006, at 00:40, Frank Heckenbach wrote:
Jonas Maebe wrote:
[snip]
What I think is strange is when you look at the byte order with current (GPC and apparently also FPC) sets on big-endian machines, e.g. for a 0-based set on a 32 bit machine:
Byte Elements 0 24..31 1 16..23 2 8..15 3 0..7 4 56..63 5 48..55
etc.
This is because the bytes within a word are big-endian, but we always treat the sequence of words as little-endian (lowest elements first), so we actually get a mixed endianness when considering set elements.
I disagree that for sets this is strange, if only for the reason that apparently both the GPC and FPC implementors did it that way independently, and without any hacking or ugly workarounds.
What I mean is that the memory layout is strange when looking closer at it. The code to handle it is not strange that's probably why we developed it like this.
On the contrary, this representation is extremely convenient because it allows one to implement all set routines in an endian-agnostic way (both in the rtl/rts and in the compiler), and the only thing needed to load the values from one endianess architecture on another is byte- swapping.
At a very low level it may seem strange once you start to think about it (I also thought it to be strange the first time I realised this), but does that matter if it's easy to work with it at a high level? (both for the compiler implementors and the end-users no less)
On a high-level it's not a problem. But you started this thread with gdb access which is a low-level issue. The advantage of formats without "strange" memory layout is that they're also agnostic of element sizes used (the original problem). But of course, that's not an absolute requirement. In fact, I'd prefer if there's a way to tell gdb about the element size (and bit/byte/word endianness and alignment), so different formats can be tried and used without worrying whether gdb suports them.
You seem to be very concerned with sets in binary file formats, judging from these and previous concerns.
I am indeed. These sort of issues can waste a lot of programmer time when going from one platform to another, which could be spent on much more useful things.
As you explained that FPC itself need this, I understand your concern. ;-) (It might be one of the biggest users of sets in binary files, otherwise I haven't seen many programs that do.) However, as you said, you need some conversions anyway, does it make a big difference which kind of conversions (bit, byte, word reversing), once you have generic routines for these (which is a small one-time effort, of course).
Gale Paeper wrote:
68K and PPC CodeWarrior Pascal, YHINK Pascal, and MPW Pascal all use the same data format for sets. The format is an array of bytes and (from the CodeWarrior Pascal documentation) the formula for determining a specific set element bit in the array is:
bit : BAND(SET[|SET| - 1 - EL div 8],(BSL(1,EL mod 8))
where BAND and BSL are 68K intrinsics for 68K instructions for respectively bitwise AND and bitwise shift left.
OK, so that's just the reverse of what Waldek suggested. It's also word-size-agnostic and allows for simple range operations with any word-size. (It's just quite different from the little-endian format in that the byte-order is completely reversed.)
EL is the element number which corresponds to the ord of the element in the base type the set is derived from. |SET| is the number of bytes in the set, so the byte array has an index subrange of 0..(|SET| - 1).
The byte array is always sized/allocated with an element number zero base even in the cases of a subrange base type set (e.g., set of [5..15] will be allocated the same as set of [0..15] and the bits for 0..4 won't be used).
What about negative lower bounds? I take it they're not supported in this format.
Frank
On 06 Aug 2006, at 13:58, Frank Heckenbach wrote:
On a high-level it's not a problem. But you started this thread with gdb access which is a low-level issue. The advantage of formats without "strange" memory layout is that they're also agnostic of element sizes used (the original problem). But of course, that's not an absolute requirement. In fact, I'd prefer if there's a way to tell gdb about the element size (and bit/byte/word endianness and alignment), so different formats can be tried and used without worrying whether gdb suports them.
Maybe that is possible to a certain extent with the M2 record-set trick... At least you can order the bytes in any way you like using that.
I am indeed. These sort of issues can waste a lot of programmer time when going from one platform to another, which could be spent on much more useful things.
As you explained that FPC itself need this, I understand your concern. ;-) (It might be one of the biggest users of sets in binary files, otherwise I haven't seen many programs that do.)
I've at least already seen some others on the macpascal list.
However, as you said, you need some conversions anyway, does it make a big difference which kind of conversions (bit, byte, word reversing), once you have generic routines for these (which is a small one-time effort, of course).
There are two different things:
a) since we implement the compiler, it's obviously no problem to also implement and use the necessary helpers. Additionally, all our set reading and writing goes through two single routines, so it's easy to do this in the compiler. However, for end users it will be less obvious what's needed and they may have a lot more separate reads/ writes scattered throughout their sources (which may have to be updated again after they already did so previously). b) case a) is only about different byte/bit order. If in addition also the size of the set varies depending on the architecture, you open a whole new can of worms (because you have to start manually padding either on disk or in memory, and/or somehow calculate what the size of the set would be on another architecture).
Jonas
Frank Heckenbach wrote:
Gale Paeper wrote:
68K and PPC CodeWarrior Pascal, YHINK Pascal, and MPW Pascal all use the same data format for sets. The format is an array of bytes and (from the CodeWarrior Pascal documentation) the formula for determining a specific set element bit in the array is:
bit : BAND(SET[|SET| - 1 - EL div 8],(BSL(1,EL mod 8))
where BAND and BSL are 68K intrinsics for 68K instructions for respectively bitwise AND and bitwise shift left.
OK, so that's just the reverse of what Waldek suggested. It's also word-size-agnostic and allows for simple range operations with any word-size. (It's just quite different from the little-endian format in that the byte-order is completely reversed.)
At least for the 68K instruction set, it also has some nice "for free" space and cycle savings properties. The 68K simgle bit instructions (BCLR, BSET, BTST, etc.) automatically do a mod 8 on the element number when operating on a memory byte and a mod 32 on the element number when operating on a register. Although savings are down in the noise level on todays machines, saving a few bytes and cycles here and there on the machines in use when the format was established made a noticable difference.
Just to be certain the format is clear to everyone, the layout for the example being used is (with traditional MacPascal compilers):
Byte Elements 0 47..40 1 39..32 2 31..24 3 23..16 4 15..8 5 7..0
EL is the element number which corresponds to the ord of the element in the base type the set is derived from. |SET| is the number of bytes in the set, so the byte array has an index subrange of 0..(|SET| - 1).
The byte array is always sized/allocated with an element number zero base even in the cases of a subrange base type set (e.g., set of [5..15] will be allocated the same as set of [0..15] and the bits for 0..4 won't be used).
What about negative lower bounds? I take it they're not supported in this format.
Correct. No negative lower bounds are allowed for integer subrange sets. The lower bound must be greater than or equal to zero.
Gale Paeper gpaeper@empirenet.com
Jonas Maebe wrote:
On 1 aug 2006, at 23:53, Waldek Hebisch wrote:
[snip]
In principle we can change set representation. In fact, there is one change that I intend to do in the future: currently even the smalles set use a MedCard sized word, I plan to allocate smaller space for them (smallest unit which can represent them).
There have been plans for a long time to do that in FPC as well. If you do this as meticulously as Delphi does (its set size grows by 1 byte at a time), then you more or less need by definition a little- endian representation of sets in all cases though (because of the left-over bytes at the end).
For this reason, a number of FPC developers are in favour of using "little endian" sets on all platforms. I'm a bit wary of breaking backwards binary compatibility though, and possibly also compatibility with other big endian Pascal compilers (does anyone know how CodeWarrior/PPC and/or Think Pascal store their sets?)
68K and PPC CodeWarrior Pascal, YHINK Pascal, and MPW Pascal all use the same data format for sets. The format is an array of bytes and (from the CodeWarrior Pascal documentation) the formula for determining a specific set element bit in the array is:
bit : BAND(SET[|SET| - 1 - EL div 8],(BSL(1,EL mod 8))
where BAND and BSL are 68K intrinsics for 68K instructions for respectively bitwise AND and bitwise shift left. EL is the element number which corresponds to the ord of the element in the base type the set is derived from. |SET| is the number of bytes in the set, so the byte array has an index subrange of 0..(|SET| - 1).
The byte array is always sized/allocated with an element number zero base even in the cases of a subrange base type set (e.g., set of [5..15] will be allocated the same as set of [0..15] and the bits for 0..4 won't be used). The array can be as small as one byte (for sets in the subrange 0..7) and as large as 256 bytes for the maximum support set size (i.e., subrange 0..2047). For one byte sized sets, there are no alignment restrictions for storage. Larger sets are even byte aligned.
Thus, array[|array| - 1] is where bits for set elements 7..0 (in that order; i.e., set element 7 is the most significant bit in the byte) are found.
As an aside, I'll note CodeWarrior and YHINK Pascal always use RTL calls for set expression operations; whereas, MPW Pascal will use the appropriate inline bitwise and, or, and not 68K instructions for set expressions involving one, two, and four byte sized sets. Compatability with MPW Pascal and 68K inline instructions is the origin for the set data format in all the traditional MacPascal compilers.
Gale Paeper gpaeper@empirenet.com