Anton Ertl wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>> Anton Ertl wrote:
>>> What would be your alternative?
>>>
>>> 1) Worst-case assumptions for everything outside the compilation unit,
>>> and stick with these sizes? That would certainly make the linker
>>> easier to implement, but it squanders much of the benefit of being
>>> able to have shorter encodings.
>>>
>>> 2) Start out with worst-case assumptions, and let the linker shrink if
>>> possible? I don't see that this would be any less bug-prone than the
>>> approach actually taken, and actually an approach where you allow
>>> shrinking is more bug-prone, because shrinking in one place means that
>>> you may have to grow in a different place, so you need extra
>>> complexity to ensure termination. An approach that only ever grows
>>> will terminate after polynomial time. See
>>> <http://www.complang.tuwien.ac.at/anton/assembling-span-dependent.html>.
>>>
>>> - anton
>> I don't see why you think termination for shrinking is complicated:
>> it terminates when the code stops shrinking (or earlier).
>
> In that case the result may be invalid. I give an example in
> <http://www.complang.tuwien.ac.at/anton/assembling-span-dependent.html>:
>
> |foo:
> | movl foo+133-bar(%rdi),%eax
> |bar:
> |
> |If you choose the large encoding, the offset is 127 and would seem to
> |fit in the small encoding. But if you choose the small encoding, the
> |offset is 130 and does not fit in the small encoding.
>
> So if you start big and shrink, you will choose the small encoding for
> this instruction, and then you will notice that the result cannot be
> encoded. Since you cannot grow, you are stuck.
>
> Other posters have pointed out that alignment can also cause this
> effect.

(I originally saw this as a series of trial runs but this has been
overtaken by the jitter-sum-and-shrink approach in other msgs.
Note that it does only produce valid results each iteration.)

I was assuming that we start with large offsets and a valid solution,
and that each iteration only produces a valid though possibly
non-optimal solution.

My initial thought was to do a trial shrink.
Then a verify pass and mark all the items that break as to be skipped.
Then retry without skipped items. Iterate until a valid solution.
Iterate producing valid solutions until it stops shrinking.

Anyway, this has been superseded.

>> The difference between shrinking (start big, optimize to smaller) and
>> expansion (start small, discover problems, expand, propagate side effects)
>> is that shrinking starts with valid code - all the BR and LD/ST offsets
>> are valid just not necessarily optimal. That means that shrinking
>> optimization can stop at any point and still produce a valid executable.
>
> The difference is that with expansion you can stop as soon as you have
> a valid solution, while with shrinking you move towards invalidity, and
> when you find that your "solution" is invalid, it's too late.
>
>> A shrinker could do 3 or 4 sweeps checking each of the m references
>> and then just stop, so be O(4*m) and thus avoid pathological examples,
>> whereas expansion run to completion no matter the cost.
>
> So what? In practice it's O(3*m) or so, and if pathological cases
> cost O(n*m) (where n is the number of references), who cares?
> Apparently the incompetently written RISC-V linker (which does O(n*m)
> even for cases where O(3*m) would be enough with a better
> implementation) is not bad enough to get anyone to pay for rewriting
> it (and also not bad enough to get anyone to do it for free).
>
> - anton

As long as the result is a valid executable then yes I don't care
about infrequent pathological cases that remain non-optimal,
as no matter what algorithm we choose there will always be some.
I don't want to make perfect the enemy of good enough.

On Tuesday, July 25, 2023 at 1:09:04 PM UTC-5, Scott Lurndal wrote:
> MitchAlsup <Mitch...@aol.com> writes:
> >On Tuesday, July 25, 2023 at 10:48:28=E2=80=AFAM UTC-5, Scott Lurndal wrote=
> >:
> >> MitchAlsup <Mitch...@aol.com> writes:=20
> >> >On Tuesday, July 25, 2023 at 5:12:27=3DE2=3D80=3DAFAM UTC-5, Anton Ertl =
> >wrote:=20
> >> >> MitchAlsup <Mitch...@aol.com> writes:=3D20=20
> >> >> >Every expansion makes it possible that some other already resolved re=
> >loc=3D=20
> >> >ati=3D3D=3D20=20
> >> >> >on=3D3D20=20
> >> >> >has now slipped out of range; whereas shrinking does not have this pr=
> >obl=3D=20
> >> >em.=20
> >> >> Shrinking can result in another or even the shrunken value become=3D20
> >> >> bigger, so it definitely has this problem.=20
> >> ><=20
> >> >In Mc 88100 time, we did not have IP relative addressing, which makes=20
> >> >your chosen example no longer an example creating such a condition.
> >> I was looking at the 88100 databook the other day, and noticed the=20
> >> instruction encoding for load unsigned byte is the same as xmem dw - how =
> >were the=20
> >> two disinguished from each other in hardware?
> ><
> >Probably an error in the text they were different OpCodes.
> The text is the (M) Motorola MC88100 Risc Microprocessor User's
> manual, second edition (Prentice Hall ISBN 0-13-567090-X). I have
> a paper copy, but there's a scan of it on bitsavers.
>
> Table 3-14.
>
> xmem (imm) 0 0 0 0 T Y D D D D D S S S S S I I I I I I I I I I I I I I I I
> ld (imm) 0 0 P P T Y D D D D D S S S S S I I I I I I I I I I I I I I I I
>
> P 0 0 - Load Unsigned
> 0 1 - Load Signed
> TY 0 0 - DW
> 0 1 - W
> 1 0 - HW
> 1 1 - B
>
> The only difference is in bits [29:28] and 0b00 is legal in both encodings.
>
> It looks like a bug in the documentation - the MC88110 documentation doesn't
> show S1+imm form for xmem.
<
Sounds perfectly plausible, I don't recall xmem having an immediate form.
<
Although it looks amusing at the B,H,W,D ordering.

Anton Ertl wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> writes:
>> I have watched several iterations of this discussion over the
>> years: It seems pretty obvious to me that Ivan's approach is always
>> valid, i.e. sweep across the code and then for each instructions
>> with multiple possible encodings, check which category it is in:
>>
>> a) Always reachable in short form? Mark so and lock down.
>
> How do you determine that?

As Ivan (and EricP) explained it, you traverse the code and for each
instruction (and branch target) you maintain a running min and max IP
value: Min is for when all the variable instructions up to this point
resolve to the short form, max is the opposite.

When you reach a backwards branch you know that the current min IP minus
the branch target min IP is the smallest possible offset. Forward
branches are resolved the same way when you get to the target IP.

If the maximum possible offset fits in a short form, then use it and
mark it as resolved.

>
>> b) Never reachable in short form. Mark as long and lock.
>
> How do you determine that?

As above: If the minimum possible offset needs a long form, then resolve
as such.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On 7/25/2023 5:10 AM, Terje Mathisen wrote:
> I have watched several iterations of this discussion over the years: It
> seems pretty obvious to me that Ivan's approach is always valid, i.e.
> sweep across the code and then for each instructions with multiple
> possible encodings, check which category it is in:
>
> a) Always reachable in short form? Mark so and lock down.
> b) Never reachable in short form. Mark as long and lock.
> c) Not determined yet.
>
> Repeating this scan N (Ivan says 3) times and locking down any remainder
> as long form is guaranteed to leave you with working code which will be
> pretty darn close to optimal.
>
> The nice thing about this method is that it automatically handles
> alignment road blocks that can mess up other methods.
> I.e. if the branch offset is less than 128-16=112 bytes, then a byte
> offset will reach it no matter where an ALIGN 16 directive would
> position it.
>
> It is also OK on cpus with branches relative to the next instruction,
> i.e. where the length of the branch instruction itself impacts the
> distance to be reached.
>
> Terje
>
> Thomas Koenig wrote:
>> On 2023-07-25, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> Quadibloc <jsavard@ecn.ab.ca> writes:
>>>> Although subsequent discussion has noted that as long as
>>>> instruction sizes can only change *downwards*, then there
>>>> is no problem
>>>
>>> No matter how often this claim is repeated, it still stays wrong.  If
>>> sizes can only grow downwards, you can reach an invalid state and then
>>> you are stuck there.
>>
>> Does this also hold for ISAs where the branches are relative to
>> the start of the instruction?  If you shrink a branch instruction,
>> this will make a later target come closer.
>>
>
>

Final step after iteration stops resolves remainder to *short*, not to
long.

On 7/25/2023 5:10 AM, Terje Mathisen wrote:
> I have watched several iterations of this discussion over the years: It
> seems pretty obvious to me that Ivan's approach is always valid, i.e.
> sweep across the code and then for each instructions with multiple
> possible encodings, check which category it is in:
>
> a) Always reachable in short form? Mark so and lock down.
> b) Never reachable in short form. Mark as long and lock.
> c) Not determined yet.
>
> Repeating this scan N (Ivan says 3) times and locking down any remainder
> as long form is guaranteed to leave you with working code which will be
> pretty darn close to optimal.

If you iterate until nothing new resolves during a pass then any
remainder can be resolved as short. If you quit early then the remainder
must be resolved as long. In my experience four passes will resolve
everything that will. The fourth is just verifying; it doesn't actually
do anything, and it and further can be omitted at the cost of resolving
the remainder long.

However, the remainder is often empty early, so early passes should
check whether they have resolved the last one, in addition to checking
whether anything at all was resolved.

> The nice thing about this method is that it automatically handles
> alignment road blocks that can mess up other methods.
> I.e. if the branch offset is less than 128-16=112 bytes, then a byte
> offset will reach it no matter where an ALIGN 16 directive would
> position it.
>
> It is also OK on cpus with branches relative to the next instruction,
> i.e. where the length of the branch instruction itself impacts the
> distance to be reached.
>
> Terje
>
> Thomas Koenig wrote:
>> On 2023-07-25, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> Quadibloc <jsavard@ecn.ab.ca> writes:
>>>> Although subsequent discussion has noted that as long as
>>>> instruction sizes can only change *downwards*, then there
>>>> is no problem
>>>
>>> No matter how often this claim is repeated, it still stays wrong.  If
>>> sizes can only grow downwards, you can reach an invalid state and then
>>> you are stuck there.
>>
>> Does this also hold for ISAs where the branches are relative to
>> the start of the instruction?  If you shrink a branch instruction,
>> this will make a later target come closer.
>>
>
>

EricP <ThatWouldBeTelling@thevillage.com> writes:

> Tim Rentsch wrote:

[on bitfields]

>> It sounds like you think bitfields are either not usable or not
>> useful. I admit that bitfields have some annoying properties,
>> but they are both usable and useful, for people who know how
>> to use them.
>
> No, I use bitfields when needed. I am aware of their weaknesses
> and I have no illusions they are completely portable, just mostly
> portable. [...]

Okay, good to know. I had a different impression from your
earlier writing.

On 7/26/2023 4:25 AM, Tim Rentsch wrote:
> EricP <ThatWouldBeTelling@thevillage.com> writes:
>
>> Tim Rentsch wrote:
>
> [on bitfields]
>
>>> It sounds like you think bitfields are either not usable or not
>>> useful. I admit that bitfields have some annoying properties,
>>> but they are both usable and useful, for people who know how
>>> to use them.
>>
>> No, I use bitfields when needed. I am aware of their weaknesses
>> and I have no illusions they are completely portable, just mostly
>> portable. [...]
>
> Okay, good to know. I had a different impression from your
> earlier writing.

Ironically, I didn't use them, and seemingly pretty much none of the
code I had ported over had used them either.

Have (theoretically) added them to my compiler (1), but not gotten
around to testing them yet.

1: In the sense of actually handling them, rather than accepting it in
the parser and then just ignoring it and using the base type instead
(eg: "int x:7;" being compiled as-if it were "int x;").
Ended up with a new notation in the type-signature notation, eg: "B7i", ...

EricP <ThatWouldBeTelling@thevillage.com> writes:
>What do you think of the jitter-sum-and-shrink loop approach?

It appears more complex than necessary to me, without providing a
significant benefit.

Yes, for fast relaxation you won't work with the actual code until you
know the actual sizes of the shrinkable instructions, and you
represent all the unchanging contiguous code only by its size.

But otherwise I would just start out with everything small, (*)
process the instructions from the lower addresses to the higher ones
(because alignment works towards higher addresses), compute actual
values for the labels, use that for seeing which instructions are too
small and grow them, and then repeat starting at "(*)". Once you have
a pass that does not change any instructions, you can work with the
actual code.

If you want something more efficient, Szymanski describes an approach
that represents the program as a graph, and I think it processes the
growable/shrinkable instructions in a more intelligent way than just
doing a passes through all of them, but Szymanski did not take
alignment directives into account, and adapting his algorithm to take
that into account is non-trivial. I think the pass approach is fast
enough nowadays.

The much bigger problem than everything I have discussed above is the
complexity of the requirements from the involved standards as discussed in

https://maskray.me/blog/2021-03-14-the-dark-side-of-riscv-linker-relaxation

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Thomas Koenig <tkoenig@netcologne.de> writes:
>There is an interesting article about RISC-V linker relaxation, which
>appears to be highly cursed, at
>
>https://maskray.me/blog/2021-03-14-the-dark-side-of-riscv-linker-relaxation

Actually my major takeaway from this is the large complexity of ELF,
with the generic standard leaving stuff open for architecture-specific
supplements, and those filling these in. This complexity seems to be
caused by the requirements of the tools interfacing through ELF:
Assemblers/compilers, linkers, dynamic linkers, tools like nm and
objdump, debuggers, and maybe others. And I remember also reading
about a requirement that is not covered by ELF, leading to some missed
opportunity.

I wonder if with the benefit of hindsight someone who is familiar with
the requirements could not design something significantly simpler. Or
alternatively, if going with architecture-specific tool chains (at
least for assembly and linking) would not have resulted in reduced
overall effort compared to having generic assemblers and linkers with
architecture-specific parts that all have to fit into the generic
framework.

Concerning RISC-V, most of the problems seem to be generic; in a few
places RISC-V-specific choices (i.e., coming from the RISC-V
supplement of from the assembler) are mentioned that cause problems.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

On 7/31/2023 2:51 AM, Anton Ertl wrote:
> Thomas Koenig <tkoenig@netcologne.de> writes:
>> There is an interesting article about RISC-V linker relaxation, which
>> appears to be highly cursed, at
>>
>> https://maskray.me/blog/2021-03-14-the-dark-side-of-riscv-linker-relaxation
>
> Actually my major takeaway from this is the large complexity of ELF,
> with the generic standard leaving stuff open for architecture-specific
> supplements, and those filling these in. This complexity seems to be
> caused by the requirements of the tools interfacing through ELF:
> Assemblers/compilers, linkers, dynamic linkers, tools like nm and
> objdump, debuggers, and maybe others. And I remember also reading
> about a requirement that is not covered by ELF, leading to some missed
> opportunity.
>

For the cases I have used object files, I have usually been more
inclined towards COFF.

Where, say, despite some annoyances with the design of COFF, it was at
least less prone to pointlessly over-engineer stuff or add needless
complexity.

I had felt half-tempted to stick a "proper" file magic on the start of
the object files though.

PE/COFF was sorta similar, and it can be noted that (for images
generated with an RVA==file-offset constraint and no DLLs), the simplest
case loader is:
Look at headers to figure out load address and entry point and similar;
Read PE/COFF image into RAM at that address;
Jump to entry point.

Though, the offset==RVA constraint can be relaxed for non-resident
sections (such as the base-reloc table and similar) which in PEL were
allowed to overlap with non-stored sections (such as ".bss").

If you want to load anywhere, or deal with DLLs, one has to make use of
the "Base Relocation Table" and Import/Export tables, but in both cases,
the mechanisms are relatively straightforward (and, also, the Import
tables tell you which DLL to load the symbol from).

Though, DLLs did have two different mechanisms for importing symbols:
By 16-bit "ordinal number" (matching between export and import);
By symbolic name, keyed internally to an ordinal number.

For TestKern, had wrote the loaded under the assumption of importing by
symbolic name, mostly assuming the ordinal number to be effectively
"internal use only" (with no support for "import by ordinal" semantics).

Between them, PE/COFF base relocs are simpler partly as one does not
need to care about symbols; only the relative offset between the default
image base address and wherever it is being loaded.

Though, my PBO ABI effectively added some complexity by internally
splitting the base reloc table:
The first part is applied when the image is first loaded, applying to
".text" and other read-only sections;
The second part is applied to dynamic sections when the image is being
instantiated within a process (with the data/bss sections being handled
and located separately from the main executable).

Though, I can note that at one point I did also look at the Mach-O
format and similar as well.

Some ideas I had considered were sort of grafted onto PE/COFF, creating
my PEL format.

Otherwise, the executable format might have instead been structured as a
linear series of LZ compressed sections and "load commands".

> I wonder if with the benefit of hindsight someone who is familiar with
> the requirements could not design something significantly simpler. Or
> alternatively, if going with architecture-specific tool chains (at
> least for assembly and linking) would not have resulted in reduced
> overall effort compared to having generic assemblers and linkers with
> architecture-specific parts that all have to fit into the generic
> framework.
>

If I were to try to design a "simple" object format, I would likely just
sort of end up defining one based on the Doom IWAD or Quake WAD2 formats
(though, in this case, more likely WAD2).

Say, WAD2 based:
'text' / 'data' / 'bss' / ...
Ye olde sections (names limited to 16 chars).
'$symtab', '$reloc'
Symbol and relocation tables
'$symstr'
Symbol string table

Or, IWAD based:
TEXT/DATA/BSS:
Sections (names limited to 8 chars).
$SYMTAB / $RELOC / $SYMSTR
Metadata

Symbol:
{
u32 name_ofs; //offset of name within string table
u32 sec_ofs; //offset within section
u16 sec_id; //containing section (lump ID)
byte sym_type; //symbol type
byte resv1;
}
Reloc:
{
u32 sym_idx; //target symbol index
u32 sec_ofs; //reference offset
u16 sec_id; //reference section
byte rlc_type; //relocation type
byte resv1;
}

Would likely not bother with GOT or anything of the sort.

Probably no "linker relaxation" either (instead, say, assume that user
either gets the compiler and linker options correct, or faces annoyances
if the program fails to link).

Though, this wouldn't make as much sense for an executable format.

Possible "simple executable format":
Series of Loader commands;
Linear payload data, corresponding to each command.
When "played out", the commands say how much data to read or process.

With the data organized in a way that the whole image can be loaded
without any need for file-seeks. Commands being stuff like "copy the
next n kB to this RVA" or "Apply the following Base-Relocs".

IMHO, trying to make a single format serve as both an object-file format
and executable format seems a little off IMO, as the requirements
between the use-cases differ.

> Concerning RISC-V, most of the problems seem to be generic; in a few
> places RISC-V-specific choices (i.e., coming from the RISC-V
> supplement of from the assembler) are mentioned that cause problems.
>

OK.

Kinda funny recently is that I started writing out some ideas for
another possible filesystem, and it ended up looking sort of like a
hybrid of EXT2 and NTFS.

General idea was sort of like:
Filesystem image was a flat collection of blocks;
The superblock/etc is simply marked as in-use, and understood as "special";
The "inode table" is itself treated like a file (Inode 0 is the Inode
Table);
The INode entries contain several header records stored in a TLV format
(minor annoyance, but increases flexibility).

Directory records were 64 bytes, handling names up to 256 characters by
daisy-chained records (sort of like FAT LFNs), but with 48-character
names for the single-entry case (where 48 chars is sufficient for the
vast majority of file names). They would hold both the name, INode
Number, and some entries related to file-lookup (handled as a balanced
binary tree).

I personally consider this to "less bad" than the use of free-form
variable-length directory entries. Idea was that names would be stored
in UTF-8 and organized in "memcmp()" order (with names being NUL padded).

A binary tree structure would serve the dual purpose of both allowing
faster lookup and also allowing the directory to be walked in (more or
less) alphabetical order. Though, by default would assume the use of a
case-sensitive filesystem (case insensitivity would add complexity by
requiring case normalization).

This time around, decided to go with a block-indirection scheme similar
to that in the EXTn filesystems (as opposed to span-tables). Would
differ slightly in that the indirect and double/triple indirect tables
would replicate the entries from the lower indirection levels (or, by
directly including the tables from lower indirection levels).

Don't yet know if I will do much with this...

Partly this is related to the annoyance that despite various
file-systems existing, not many really matching the properties that I
would want.