Hacker News Reader

Comment by bogomipz | Hacker News Reader

The author states:

>"An optimizing compiler would constant-fold our expression into a single number ahead of time."

Could someone say what is meant by constant-folding here?

As a concrete example I wrote a simple interpreter a while back, in golang. Operations would be compiled to a simple bytecode which would be executed at runtime. So:

     3 + 4

Would get "compiled" to:

     PUSH_INT 3
     PUSH_INT 4
     OP_PLUS

As you can imagine this was a virtual stack-machine. After a while I started folding these operations:

* If there was a "push int"

* And another "push int"

* And a maths operation.

* Then replace.

So in my case I'd first generate the naive version, then have a separate "optimise" pass which would rewrite the program:

     PUSH_INT 7
     NOP
     NOP
     NOP
     NOP

A later optimization pass would remove consecutive NOP operations. I made a brief blog-post here:

https://blog.steve.fi/adventures_optimizing_a_bytecode_based...

There were a couple of bugs found along the way, but the actual implementation of this optimization pass was pretty simple:

https://github.com/skx/evalfilter/pull/66/files

The biggest issue I had to face was that "1 + 3 => 4" is trivial, but my virtual machine only supports loading integers. So I couldn't collapse "2 * 3.3" into the constant "6.6".

For anyone wondering, the NOPs are so that jumps don't get messed up. Assembly level GOTOs generally work on byte/word offsets, so if something intended to jump back before the calculation but was expecting two PUSH_INTs and an OP_PLUS (5 words: 3 opcodes, 2 arguments) but there was only a single PUSH_INT (2 words), it would jump back 3 words too far.

Good clarification, and exactly right!

Later I do walk back over the bytecode and remove the nops. But I have to update all JMP/CALL instructions to cope with the changed destination offsets. Not a hard job in my case, as there are only a couple of instructions which refer to byte-offsets.

(If I allowed "LD A,[BC]", or similar permuations I'd have a lot more work to do.)

Basically you have all the info you need at compile time, so you just do the work then rather than having to do it every time while the program is running.

Ex: 4 + 4 would be condensed down to just 8 at compile time rather than writing the code to get 4 and 4 both into registers and add them at execution time.

https://en.wikipedia.org/wiki/Constant_folding: "Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time. Consider the statement:

    i = 320 * 200 * 32;

Most compilers would not actually generate two multiply instructions and a store for this statement. Instead, they identify constructs such as these and substitute the computed values at compile time (in this case, 2,048,000)."

Say you have a simple expression within your code: 4+3*2. Rather than computing the result at run time, you can reduce (fold) that expression into 10, because it's a simple constant that only needs to be computed once.

Reply on news.ycombinator.com