How to compile arithmetic expressions to x86?

hi prog, say I want to take as given some variables on the stack x,y,z,w and compile expressions (x+y)*(z+w) to x86 asm.

first off the instructions take registers or pointers and well x86 is weird and has instructions like this:

add x, y ;x OR y must be a register, result in x
mul x ;multiplies eax with x, result is put into eax

so this would work:

mov eax, stack0
add eax, stack1
mov ebx, stack2
add ebx, stack3
mul ebx

but how would you make an algorithm to do this in general?

This is not the only way, but this is the traditional way. Introduce temporaries to generate code like the following.

t1 = x + y
t2 = z + w
t3 = t1*t2

Each node of the expression tree becomes a variable. You can also locate common subexpressions if you wish.

Then assign the variables to registers and stack positions and generate assembly like you wrote.

some variables on the stack

The question you should be asking yourself is why aren't they in the registers already?

If you don't need x again (or one of the other ones, similarly), this uses one less register:
mov eax, [ebp+_y]
add [ebp+_x], eax
mov eax, [ebp+_z]
add eax, [ebp+_w]
mul [ebp+_x]

The general algorithm depends on how many of those values will need to be used after that single expression. It produces a dataflow graph and then matches the available instructions against it.

Please marry me, Cudder-sama ;_;

>>3
>>4
fuck off and kill yourself

>>3
That doesn't help you if you need to pass more values than there are registers, which is stupidly common on your beloved x86 because it only has a handful. It is also not fun at all to debug code for architectures with limited registers because an optimal register scheduling scheme will destroy even very recent and useful intermediate values with great eagerness.

Sure, you can always dial back the optimization level in your code generator or use tracing features, but on non prematurely optimized ISAs you aren't forced into doing this immediately for the most trivial cases. With x86, you have to reach for a bazooka to swat a fly.

>>4
fuck off cockring-nigger.

>>5
fuck off and optimize your quotes

>>6
If you don't need to use memory then don't. Start using memory only when it doesn't all fit into registers - and arrange things suitably so that the values that are used first/most are the ones that get chosen for registers first. That's all there is to it.

It is also not fun at all to debug code for architectures with limited registers because an optimal register scheduling scheme will destroy even very recent and useful intermediate values with great eagerness.

I have no idea WTF you're complaining about. "It's too hard to debug"? It should be. This is not BASIC. If you're working at Asm level and worrying about debugging then YOU ARE DOING IT WRONG.

How to compile arithmetic expressions to x86?

You don't. First you wait for garbage collector to run and then, if you're lucky, the interpreter parses the expression and evaluates to some result.

>>9
kill yourself namefag, no one wants you here

>>10
lmao nice prog memes I can tell youre a true old/prog/

https://en.wikipedia.org/wiki/Three-address_code

I can easily compile to 3 address code, it's going from that to x86 that is hard

>>12
Then compile to two address code.

>>9

If you're working at Asm level and worrying about debugging then YOU ARE DOING IT WRONG.

This problem doesn't just apply to people who are writing assembly by hand. Any language implementation that compiles to native code and implements symbolic debugging by mapping the generated code back to high level constructs will have the same problem. It is usually hopeless to try and debug optimized x86 code generated by a compiler symbolically because the compiler will almost never generate code that maps back to the source in a straightforward fashion. Lack of registers is a major cause for this.

>>14

"I'm too stupid to read Asm."

Go back to mental masturbation with your ultra-high-level languages, quiche-eater.

>>15
Who are you quoting.

>>16

Who are you quoting.

Whom are you quoting?

>>15 kill
>>16 your
>>17 self

x86

http://www.youtube.com/watch?v=PA9_VCM-bSc

>>15
You're a stupid codemonkey. You're an autist who would rather build spaceships out of legos than think about real spaceships because you can put yours together piece by piece. But in the end, all you'll have is a toy, while actual humans will have a ship that, while sometimes explosive, actually exist and can do everything your Assembly trinkets can't.

Who else loves quiche?

No real man, that's who

>>20
>>21
>>22
you retards can shut up until i get helped

>>23
You want some quiche too?

>>15
I wouldn't call C an ultra high level language. Not when targeting x86, anyway. I'm only familar with a handful of the most common optimizations, but the x86 output of most C compilers is rarely surprising to me. The main thing that makes things hard to follow is the incessant bouncing of values to the stack frame and back, which is a direct consequence of the shortage of registers.

>>24
Will it optimize his quotes?

OPTIMIZE THE QUICHE

>>25
I am Haskal programmer.

>>12
It is my opinion that Three Address Code would be drastically overcomplicated in this situation.
This is because simple arithmetic expressions require no concept of looping or jumping, which would serve to only complicate this endeavor.
Surely a better approach would be utilizing Dijkstra's Shunting Yard algorithm¹ to translate a given infix expressoan to a Postfix² expression.
The advantages of this are obvious, of course, in that you could allocate registers³ and generate x86 Assembly⁴ efficiently in one pass over the postfix expression.

As an example, let us consider the infix expression, "(3 * 4) + 2".
The tokenization of this expression is displayed in figure A.
The translation of this expression to a linear stream of assembly instructions is not immediately clear in infix form, but if we are to translate it to a postfix expression, as in figure B, the (slightly naive) translation is simple and straightforward, as displayed in figure C.

I believe it is now adaquately obvious that translation to postfix is highly preferable to three address code. There is one alternative worth mentioning, however, which is building a tree⁵ from the infix expression, and generating assembly by recursively iterating through it. This is approximately equivalent in difficulty, but can make traversal and register allocation slightly more complex.

(
3
*
4
)
+
2
^{Figure A}

3
4
*
2
+
^{Figure B}

mov $3, %eax
mov $4, %ebx
mul %ebx
mov $2, %ebx
add %ebx, %eax
; The end result of the expression is now stored in %eax.
^{Figure C}

References:
1: https://en.wikipedia.org/wiki/Shunting_yard_algorithm
2: https://en.wikipedia.org/wiki/Reverse_Polish_notation
3: https://en.wikipedia.org/wiki/Register_allocation
4: https://en.wikipedia.org/wiki/X86_instruction_listings
5: https://en.wikipedia.org/wiki/Parse_tree

>>29
You are actually posting something that makes me think! It's been so long since this has happened!

In that example the size of the stack never exceeded two, so you could do the whole thing directly in registers by just assigning registers to stack positions. If the stack grows larger it's a little harder, but I'm sure there are many ways of adapting it. The stack would be the usual stack and the registers would act like a sliding circular buffer cache for the top elements of the stack.

>>29
Welcome to the 1970s, here's your peephole optimizer and an absence of common subexpression elimination.

>>31
You can do subexpression elimination by duping a value at a specified depth in the stack.

>>32
Yes, that's the easy part, i.e. what happens once the values have been identified as duplicates.

>>33
And identifying duplicates isn't too bad either. Just search for maximal identical subtrees of the expression tree.

the problem is to produce asm, not search for common subexpressions

>>31
If it was the 1970s, he would have to give that compiler away for free if he wanted anyone to use it.

>>35
Search for my anus.

>>36
Use my anus.

>>36
UNIX QUALITY!

>>29
RPN just gets you the order of operations. That's trivial stuff. Mapping values to registers and selecting instructions is the interesting part. Relevant links:

https://en.wikipedia.org/wiki/Strahler_number
https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm

And use the standard syntax, not that backwards GNU shit.

>>30
Once you need more storage than available registers then a dataflow-directed method should be far better than "stack emulation", although testing this will be left as an exercise for the reader.

Ullman claims in his personal page at Stanford to be against the Iranian government,[5] but it's also alleged that he has demonstrated anti-Iranian sentiments. In one case, he responded to an email from an Iranian student who had inquired about admission at Stanford with an off-topic political rant and went on to say that he would not help Iranian students even if he could:

And even if I were in a position to help, I will not help Iranian students until Iran recognizes and respects Israel as the land of the Jewish people. I know that you may not hold the same insane position as the mullahs that run your country, but it is a matter of principle. If Iranians want the benefits of Stanford and other institutions in the US, they have to respect the values we hold in the US, including freedom of religion and respect for human rights.

Following that the National Iranian American Council issued a formal complaint to Stanford University,[6] to which Stanford spokesperson, Lisa Lapin responded that Ullman was expressing his own personal views and not the views of the University and that "he has no involvement in admission, and Stanford doesn’t discriminate in their admission process"[7][8][9][10]