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.

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

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

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

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

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