I read that FASM does multiple passes to determine all labels correctly, but what is the actual algorithm used?

The basic procedure is that fasm just keeps doing another pass until all labels are marked as resolved, or until the pass limit is reached, whichever comes first.

Maybe Tomasz will clarify some of the details, but the code is always there for inspection.

First we need to define what it means that the labels are resolved. This is delicate matter, because no label can be considered resolved on its own, the entire assembly must be resolved as a whole. Even if a label seems to have a stable value, it may suddenly change when some other value reaches a critical point and causes a cascade of changes throughout the code.

Therefore, fasm searches for a resolved state of entire assembly, which is reached only when every prediction it makes during the assembly is fulfilled exactly.

The assembler has to make a prediction every time a symbol is used before being defined. Usually the value is predicted based on the value of the same symbol from the previous (unsuccessful) pass, but there are some additional heuristics that fasm uses to guess what the actual value is going to be.

If even a single value has been mispredicted, the pass is considered unsuccessful and assembler proceeds to make another one. Hopefully this time the predictions are going to be better, based on new knowledge gathered.

This general process is implemented in its pure form in my fasmg assembler, and there resolving applies to all kinds of entities that can be defined - including macroinstructions.

However, if you are interested more in how the process applies to specific machine-code-related cases, like resolving labels in x86 code, I recommend reading my article on types of multi-pass assembly.

Okay, thanks.