Increment Operator

[Bartc]

Bartc wrote:
) There's probably a misunderstanding. A typical asm listing of x=x++
might
) be:
)
) (1) mov R,[x]
) (2) inc [x]
) (3) mov [x],R

Another typical asm listing of x=x++ might be:
(1) mov [x],[x]
(2) inc [x]

That one might be tricky..

And yet another, on a CPU with special post-increment instructions:
(1) mov R,[x]
(2) mpi R,R (move, post-increment)
(3) mov [x],R
In this case, the mpi instruction does the move and the increment
*at the same time*!! This is roughly how it works:

mpi is only register to register? C's ++ works on l-values. And if mpi
expects to work on two distinct registers then I'd say this is a code
generation problem. Assuming the increment is on the right-hand register,
this can be coded as:

mov R,[x] R=1
mpi S,R R=2, S=1
mov [x],R x=2
mov [x],S x=1

although I would understand the mov [x],R being optimised out.

At the clock tick, the input of R has *two* outputs connected to it.
Now, as it happens, the circuitry is such that if two ones or two zeroes
are both connected to an input, then it becomes one or zero respectively,
but if a one and a zero are connected, then the zero wins out(*).
(Of course, this works for each bit separately)

(And that sounds like a hardware problem, usually you can't tie two logic
outputs together, unless they're open-collector or something, according to
my 1983-vintage electronics knowledge)

) It's possible that some crazy compiler might reverse the order of lines
(2)
) and (3) for some reasons best known to itself, but it seems obvious to
me
) that the right-hand-side of an assignment should be evaluated before
storing
) it in the left-hand-side, which in this case requires no calculation.

Could you explain why this seems obvious to you ? Obviously it does not
seem so for most people.

Because in x = expr you might expect the expression to be evaluated first
before you assign it's value to x.

Besides I've always considered ++x and x++ as single, indivisible
operations. Now you've demonstrated some architectural scenarios where it
would be tricky (ie. take extra effort) to keep these effectively
indivisible.

All the code generators I've worked on (forgetting the distant past) for x86
and virtual machines, exhibit this indivisible behaviour, but then ++ and --
have always been troublesome to work with anyway.

 

[luserXtrog]

Bartc wrote:
) There's probably a misunderstanding. A typical asm listing of x=x++
might
) be:
)
) (1)    mov R,[x]
) (2)    inc [x]
) (3)    mov [x],R

) It's possible that some crazy compiler might reverse the order of lines
(2)
) and (3) for some reasons best known to itself, but it seems obvious to
me
) that the right-hand-side of an assignment should be evaluated before
storing
) it in the left-hand-side, which in this case requires no calculation.

Could you explain why this seems obvious to you ?  Obviously it does not
seem so for most people.

Because in x = expr you might expect the expression to be evaluated first
before you assign it's value to x.

Yes, but "x = expr" is itself an expression. To me it seems more
obvious that the side-effects should occur after the "assignment
expression" as well. They should all occur by the next sequence point
(one of , ?: && || or at the invisible "end-of-expression" just before
the semicolon).

 

[Phil Carmody]

It seemed to be more confusion over x++ and ++x.


There's that too,

There is no "too". Once you've got that, all bets are off.
Completely. Non-negotiably. Everything else is irrelevant.

Phil

 

[Phil Carmody]

There's that too, but I can't see how, in this simple expression, the
compiler can do anything else other than evaluate x++ then assign the
result
to x. [for x = x++;]

There are two modifications between sequence points. This is undefined
behavior, in which case anything can happen, such as having 'x' wind up
with the value 666. But let's assume somewhat sane behavior and try to
"reason out" the expression:

x = 5;
x = x++;

With somewhat sane compiler behavior, we're still left deciding
whether to assign 'x' 5 or 6, since either of the two modifications
could occur before the other.

Only if x++ is split up so that other things can happen between getting the
value x, and incrementing (namely, assigning x to x). I suppose it's
possible, but I'd hesitate to call the compiler sane. A programmer
would naturally think of x++ as a semi-atomic operation.

I'd like to hereby state in the strongest possible terms that
I'm about as insane as they come. Batshit fucking crazy.

There's absolutely nothing that hints atomicity about 'x++'
to me at all. It's, if anything, one of the constructs that
says 'two separate things happen here' the most to me.

Phil

 

[Willem]

Bartc wrote:
) mpi is only register to register? C's ++ works on l-values.

But compilers can assign local variables to registers.

Also, think about a CISC processor with such an mpi instruction, that
*does* work on memory ?

Something like: mpi [T],
Where [T] and is the memory pointed to by those registers.
It moves to [T] and increases simultaneously.

) And if mpi
) expects to work on two distinct registers then I'd say this is a code
) generation problem.

What part of 'the burden of doing-it-right lies with the programmer, not
the compiler.' did you not understand ?

)> At the clock tick, the input of R has *two* outputs connected to it.
)> Now, as it happens, the circuitry is such that if two ones or two zeroes
)> are both connected to an input, then it becomes one or zero respectively,
)> but if a one and a zero are connected, then the zero wins out(*).
)> (Of course, this works for each bit separately)
)
) (And that sounds like a hardware problem, usually you can't tie two logic
) outputs together, unless they're open-collector or something, according to
) my 1983-vintage electronics knowledge)

You should really check out some of the undocumented instructions of the
6510 cpu. And also the hardware specs on it. Perhaps it is open-collector.

) All the code generators I've worked on (forgetting the distant past) for x86
) and virtual machines, exhibit this indivisible behaviour, but then ++ and --
) have always been troublesome to work with anyway.

I'm pretty sure that a lot of compilers will emit:
mov [x],[x]
inc [x]
when you write x = x++;

And I think even the x86 has auto-increment instructions.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Nate Eldredge]

I'm pretty sure that a lot of compilers will emit:
mov [x],[x]
inc [x]
when you write x = x++;

And I think even the x86 has auto-increment instructions.

It has the so-called "string instructions" MOVS, LODS, STOS, CMPS, SCAS
which perform various loads, stores, comparisons on the values pointed
to by a pair of fixed "index registers" ESI and EDI, and then
automatically increment the pointers in those registers. But that
wouldn't be useful for just incrementing an integer variable. It would
be more useful for `*p++ = 5', etc, if p were stored in EDI.

 

[JosephKK]

Bartc wrote:
) There's probably a misunderstanding. A typical asm listing of x=x++ might
) be:
)
) (1) mov R,[x]
) (2) inc [x]
) (3) mov [x],R

Another typical asm listing of x=x++ might be:
(1) mov [x],[x]
(2) inc [x]



And yet another, on a CPU with special post-increment instructions:
(1) mov R,[x]
(2) mpi R,R (move, post-increment)
(3) mov [x],R
In this case, the mpi instruction does the move and the increment
*at the same time*!! This is roughly how it works:

mpi T,S

- The S register output is connected to the T register input
- The S register output is connected to the 1-adder input
- The 1-adder output is connected to the S register input
(A 1-adder immediately puts its input +1 on its output)
- A clock tick is fired, causing each register to take the value of its
input.

Seems perfectly reasonable, yes ?
Of course, the CPU builders didn't add any special checks that the mpi
instruction is not used with the same register as input and output.
That would need extra circuitry, and therefore extra cost.
(Besides, if it were there, then x=x++ would become a trap instruction.)

Now, let's see what happens in the case of " mpi R,R ":

At the clock tick, the input of R has *two* outputs connected to it.
Now, as it happens, the circuitry is such that if two ones or two zeroes
are both connected to an input, then it becomes one or zero respectively,
but if a one and a zero are connected, then the zero wins out(*).
(Of course, this works for each bit separately)

So, basically, you get a bitwise-and of the two outputs.

This means that if you do x=x++, then the result is the bitwise-and
of x and x+1. For example, if x==5, then after x=x++ you have x=4.

And consider yourself lucky, it could also be such that the bits
fluctuate and are semi-random, depending on external factors.

*) I think this is what happens if you have pull-to-ground logic or
whatever it's called.

And yes, CPUs that connects multiple outputs to a register input
simultaneously happens to exist. The 6510 for example.


) Line (1) is the fetching of the value of x in x++
) Line (2) is the incrementing of the contents of x in x++
) Line (3) is the storing of the value fetched in line (1), into x
)
) Clearly there's nothing between Line (1) and (2).
)
) It's possible that some crazy compiler might reverse the order of lines (2)
) and (3) for some reasons best known to itself, but it seems obvious to me
) that the right-hand-side of an assignment should be evaluated before storing
) it in the left-hand-side, which in this case requires no calculation.

Could you explain why this seems obvious to you ? Obviously it does not
seem so for most people.


SaSW, Willem

WTH? Some posters in this thread seem to be posting about theoretical
machines. Why not post about actual machines instead (and identify
them)? It is not like there is not an abundance of them. Moreover,
it makes it much easier to "keep it real". Plus dealing with real
machines helps everyone check the reasonableness of the proposed
assembly level equivalent of the "C" code in question.
.

 

[Flash Gordon]

WTH? Some posters in this thread seem to be posting about theoretical
machines. Why not post about actual machines instead (and identify
them)? It is not like there is not an abundance of them. Moreover,
it makes it much easier to "keep it real". Plus dealing with real
machines helps everyone check the reasonableness of the proposed
assembly level equivalent of the "C" code in question.

I don't know about the others, but I don't have access to a lot of the
systems I've worked on in the past. This makes it far easier to give
simple examples of what could happen legally on a theoretical machine
than a concrete example. Also, sometimes, it is only when things get
complex and the optimiser does major rearrangement making it hard to see
what is going on that you see the problems.

 

[JosephKK]

I don't know about the others, but I don't have access to a lot of the
systems I've worked on in the past. This makes it far easier to give
simple examples of what could happen legally on a theoretical machine
than a concrete example. Also, sometimes, it is only when things get
complex and the optimiser does major rearrangement making it hard to see
what is going on that you see the problems.

Either way, i just find it easier do draw examples with machines i
have actually studied (becaused i worked with them). I may have done
as much in asm for various machines as i have done in any other
language. Not all of them had "C" compilers.
.