flat assembler
Message board for the users of flat assembler.

Index > Macroinstructions > Documentation lacks. Value prediction and resolving.

Author
Thread Post new topic Reply to topic
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 09 Dec 2012, 20:49
There have already been discussions regarding the fasm's resolver behaviour and documentation. There are many situations, when a programmer should think twice, whether an implementation goes beyond the borders of the documentation, because the documentation in many cases just does not say "this is possible and this is not". As long as the following situation seems to be on the border or even beyond, I'm unsure whether the topic should be in this subforum or in "Compiler Internals" as a bug report.

Long speech short sense:
Code:
x = x    

Why isn't this getting resolved? And what is the essential difference of this code to the following:
Code:
y = x
x = y    


There are also related situations, where I'd have to use the above workaround to get the code compiled:
Code:
if used x
      x = 1
end if
x = x + 1    

Similar problem arises with defined instead of used.
Post 09 Dec 2012, 20:49
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr 22 Dec 2012, 11:00
l_inc,

Well, let's see:
Code:
x = x    
Right-hand-side of the assignment contains undefined x, thus directive fails on first pass. On second (and any subsequent) pass interpreter sees that x is predicted as undefined and fails too, hence "code cannot be generated" error.
Code:
x = y
y = x    
This works completely different: after first pass x is predicted as defined (with default value of 0; here I speculate on FASM behavior); moreover, y is predicted as defined with default value of 0 too. On second pass that default value is used to define x (and y therefore). No mispredictions, success.
Code:
if used x
  x = 1
end if
x = x + 1    
This example successfully resolves in two passes as follows:
  • Pass 1:
    • there is no prediction (from previous pass), so x is treated as not used in if used x clause; x = 1 is skipped;
    • next, while analyzing right-hand-side of x = x + 1, x is marked as used;
    • this pass fails because x isn't yet defined.
  • Pass 2:
    • now there is prediction that x will be used, consequently it gets defined;
    • x is used in x = x + 1;
    • there were no mispredictions during this pass and code can be generated, so it's final.
Au contraire, if defined x will fail: x is predicted as defined but it isn't accessible there since it's redefined later by x = x + 1.

Second example highlights unique FASM feature: it can solve diophantine equations! You may consult "Code resolving" chapter in Understanding flat assembler article, I'll present another example:
Code:
x = y + 1
y = 3/(x + 1)    
In four passes FASM founds solution: x == 2, y == 1. If you exchange those lines, it takes only three passes to get to it. One can be tempted to substitute y and try x = 3/(x + 1) + 1, but this kind of dependency seems to be unresolvable by FASM (for a good reason).

Though not every solvable equation can be resolved by FASM:
Code:
y = 35/(x + 1)
x = y + 1    
While this system of equations have solution (x == 6, y == 5), FASM can't reach it using initial point (0; 0); within this recurrence it's stuck in (4; 7)<->(8; 3) loop on lattice.

Hope this helps.
Post 22 Dec 2012, 11:00
View user's profile Send private message Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 22 Dec 2012, 13:45
baldr
Quote:
Right-hand-side of the assignment contains undefined x, thus directive fails on first pass.

x is here forward referenced. Thus the assignment contains an undefined x, but speculates on it's value to be equal to zero, to satisfy the assignment. Actually it doesn't matter on what default value fasm speculates, because any value would be a valid solution.
Quote:
On second (and any subsequent) pass interpreter sees that x is predicted as undefined and fails too

No. x should already be predicted to be defined, because it was defined on the previous pass by the speculative assignment.
Quote:
after first pass x is predicted as defined (with default value of 0; here I speculate on FASM behavior)

That's strange, you didn't speculate on the fasm's behaviour the same way in the previous example, because it's the same speculative assignment with forward referencing.
Quote:
This example successfully resolves in two passes as follows:

The problem is, that this example actually does not successfully resolve. The result is same: "error: code cannot be generated". However I completely agree with your explanation, how it should work.
Quote:
Au contraire, if defined x will fail: x is predicted as defined but it isn't accessible there since it's redefined later by x = x + 1.

So what? x is not expected to be accessible, because it's value is not used before x is actually defined. Thus on the second pass it's predicted to be defined, and it actually gets defined. No mispredictions — successful compilation (expected).
Post 22 Dec 2012, 13:45
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr 22 Dec 2012, 15:48
l_inc wrote:
x is here forward referenced.
I disagree. There is no definition of x below this directive. This is crucial difference between first two cases: y is predicted to be defined somewhere below, so x = y can use its predicted (default) value.
l_inc wrote:
That's strange, you didn't speculate on the fasm's behaviour the same way in the previous example, because it's the same speculative assignment with forward referencing.
I emphasize this: x is not predicted as defined because x = x can't succeed (because x is not predicted as defined on previous pass) and so on.

Consider this:
Code:
x = x; (1)
x = x; (2)    
Here at (1) RHS x actually is forward reference, but redefinition at (2) makes it out-of-scope.
l_inc wrote:
The problem is, that this example actually does not successfully resolve.
Yes it does (1.71.06).
l_inc wrote:
So what? x is not expected to be accessible, because it's value is not used before x is actually defined.
The defined operator can be followed by any expression, usually just by a single symbol name; it checks whether the given expression contains only symbols that are defined in the source and accessible from the current position.
QED.
Post 22 Dec 2012, 15:48
View user's profile Send private message Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 22 Dec 2012, 16:42
baldr
Quote:
I disagree. There is no definition of x below this directive.

Yes. And IMHO this is a mistake. There is "usage" and there is "definition". This distinction allows to resolve the situation without breaking anything else (as it seems to me). Why should there be "above" and "below"?
Quote:
Consider this: Code:
Code:
x = x; (1) 
x = x; (2)    

This case is obvious and does not come into question, because it's clearly defined in the documentation (redefined variables cannot be forward-referenced).
Quote:
Yes it does (1.71.06).

No, it does not (1.71.06). Smile
Code:
C:\>copy con a.asm
if used x
  x = 1
end if
x = x + 1
^Z
        1 file(s) copied.

C:\>fasm a.asm
flat assembler  version 1.71.06  (1126545 kilobytes memory)
error: code cannot be generated.

C:\>    

I assume, we should ask someone else to test that.
Quote:
l_inc wrote:
So what? x is not expected to be accessible, because it's value is not used before x is actually defined.
The defined operator can be followed by any expression, usually just by a single symbol name; it checks whether the given expression contains only symbols that are defined in the source and accessible from the current position.

Wait, wait. I think there was already discussion regarding this case, where fasm stagnates around a once redefined value, and does not allow it to be a numeric constant, even if it's defined only once in later passes. Please, disregard this case currently.
Post 22 Dec 2012, 16:42
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr 22 Dec 2012, 17:08
l_inc wrote:
Yes. And IMHO this is a mistake. There is "usage" and there is "definition". This distinction allows to resolve the situation without breaking anything else (as it seems to me). Why should there be "above" and "below"?
Let's see: x = x (alone) can't be forward reference (there's nothing forward), and x is not defined (or in scope) yet.
l_inc wrote:
No, it does not (1.71.06). :-)
Mea culpa. There was dd x at the end of my test (it was used to reveal final value of x in the second case). Without that x seems to be predicted as unused (since x = x + 1 alone doesn't suffice because it fails).
Post 22 Dec 2012, 17:08
View user's profile Send private message Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 22 Dec 2012, 17:21
baldr
Quote:
Let's see: x = x (alone) can't be forward reference (there's nothing forward).

Why not? Right side of the equation is usage/reference and as long as x was not defined before, it's a forward-reference. And the left side is a definition.

The thing is that these are implementation details. Conceptually there are infinite obvious solutions to the case. If the implementation is unable to find any of those, then it's a bad implementation.
Quote:
Without that x seems to be predicted as unused (since x = x + 1 alone doesn't suffice because it fails)

The concept of "failing" is no good. It prevents from extracting information out of the statement. If x is not defined before, then the statement won't be resolved anyway. Otherwise fasm could already extract some information from the statement for future predictions.

Besides, why isn't "failing" applied to this case:
Code:
x = y
y = x    

The first x = y fails, thus x could be predicted as undefined in the second y = x, and therefore also the second equation fails.
Post 22 Dec 2012, 17:21
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland
Tomasz Grysztar 22 Dec 2012, 20:16
l_inc wrote:
baldr
Quote:
Let's see: x = x (alone) can't be forward reference (there's nothing forward).

Why not? Right side of the equation is usage/reference and as long as x was not defined before, it's a forward-reference. And the left side is a definition.
Baldr is right here - this is not a forward reference, it is a self-reference. And fasm does not allow self-references (they are most likely a programmer's mistake). A forward reference is when you use symbol that is defined in some later statement. And "simple" reference is when you use something that was defined in earlier statement. These are three mutually exclusive kinds.

A self-reference is the same thing that makes it possible to do recursion in some languages - when it is allowed for a function to call itself. It is not the same thing as forward referencing, which would be simply calling the function that is defined later in source.
Post 22 Dec 2012, 20:16
View user's profile Send private message Visit poster's website Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 23 Dec 2012, 00:00
Tomasz Grysztar
Finally, I could get the official point of view. Smile
Quote:
A self-reference is the same thing that makes it possible to do recursion in some languages

Regarding variable definition, I would not compare it to a recursive function definition, because a function is defined by it's whole body as opposed to a variable, which is defined by the result of the expression on the right side of the equality sign, and not by the whole expression as is. A function can get different input values, which makes it impossible to define a function by the result of it's execution. On the other hand the result of a specific expression on the right side of a specific equality sign is always same (otherwise the variable on the left side would have an ambiguous value).
Besides, to some extent you position fasm's control directives not as imperative, but as declarative. I.e., x = x is actually more an equation than an assignment. As an equation it perfectly fits into fasm's model.

I'm also interested, what you think regarding the example with used.
Post 23 Dec 2012, 00:00
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20448
Location: In your JS exploiting you and your system
revolution 23 Dec 2012, 00:29
l_inc wrote:
A function can get different input values, which makes it impossible to define a function by the result of it's execution. On the other hand the result of a specific expression on the right side of a specific equality sign is always same (otherwise the variable on the left side would have an ambiguous value).
x = x also has an ambiguous solution. Every possible value satisfies it. Should we define x as 0? Or 1? Or 3.141592653589793...? Or ∞?
Post 23 Dec 2012, 00:29
View user's profile Send private message Visit poster's website Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 23 Dec 2012, 01:56
revolution
fasm is documented to find one solution, if there are multiple possible. Pi and infinity are nonsense, because fasm works with integers.
Post 23 Dec 2012, 01:56
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland
Tomasz Grysztar 23 Dec 2012, 15:20
l_inc wrote:
Regarding variable definition, I would not compare it to a recursive function definition
This was merely to illustrate the difference between the self-reference and forward-reference - the latter, by its very name, is referring to something that is defined in later statement.

Whether fasm should allow self-references or not is a topic for a separate
discussion. I chose to disallow it specifically, because this catches some mistakes, while there is still a way to define indirect self references like in the example of "solving" equations.

l_inc wrote:
I'm also interested, what you think regarding the example with used.
I may have introduced some bug recently, I will look into it later and let you know what is the reason that it worked with some versions but does not anymore.
Post 23 Dec 2012, 15:20
View user's profile Send private message Visit poster's website Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr 23 Dec 2012, 17:14
Tomasz Grysztar,

This works fine:
Code:
if used x
  x = 1
end if
x = x + 1
db x    
l_inc, perhaps, mentions error if last line is absent. I think this is not a bug: x is not really used without db x (or anything that correctly uses x, not like x = x + 1 above).
Post 23 Dec 2012, 17:14
View user's profile Send private message Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland
Tomasz Grysztar 23 Dec 2012, 17:21
I analyzed it, and it was a bug. "x = x + 1" is still a correct usage as long as "x" is defined in such a way that it is in scope.

There was a problem in a way in which fasm was blocking self-references - it caused the "used" flag to be cleared as well, though it was not the intention. I modified this scheme, and with 1.71.07 it should work more smoothly.
Post 23 Dec 2012, 17:21
View user's profile Send private message Visit poster's website Reply with quote
l_inc



Joined: 23 Oct 2009
Posts: 881
l_inc 23 Dec 2012, 18:25
Tomasz Grysztar
Quote:
This was merely to illustrate the difference between the self-reference and forward-reference - the latter, by its very name, is referring to something that is defined in later statement.

Well. I also answered in the same context of differentiation of self-reference and forward-reference. If you talk about a recursive function, it's a self-reference, because the reference to the function is a part of it's definition (body). If you talk about an expression with a variable, which is assigned to the variable, then it's not a self-reference, because what defines the variable is not the expression, but the value obtained after the expression is calculated. This "after" is what makes it to a forward-reference: you first use the value of the variable for computation, and after that you define this variable by the result of the computation.
Quote:
Whether fasm should allow self-references or not is a topic for a separate discussion.

Agree. But I wouldn't call this situation a self-reference. Sure, it's just a matter of definition. You could explicitly define a self-reference to be "a usage of a variable within the same statement used to define the variable", and after that explicitly disallow such self-references (this would however require additional clarification of what a "variable definition" is, because x = x + 1 is allowed as a redefinition statement). But the very existence of the operators used and defined already separates such statements into two consequent pieces: first usage (right side) and then definition (left side).
Post 23 Dec 2012, 18:25
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.