UniQP

The blog post doesn't mention integer overflows. If integers wrap around on overflow, min(INT_MIN - 1, 0 - 1) = -1 but min(INT_MIN, 0) - 1 = INT_MAX. However, in PHP the values are converted to floats, which should preserve the equation min(a -c, b - c) = min(a, b) - c.

None, it's a hardware problem.

Since there is also a programming language called C2, I took a look at the wrong compiler.

Can you provide a link to the source code?

You can stay in SSA form even after register allocation. In libFirm the assigned registers are just attributes of the values in the SSA representation. There was some additional discussion regarding this in [1].

GCC uses a separate representation (RTL) for their backend that is not in SSA form [2]. LLVM stays in SSA form for some backend phases but lowers the SSA form before register allocation (as also mentioned in [1]).

I took a quick look at the C2 and the Graal compiler. C2 seems to use LLVM's code generator (and thus lowers SSA before register allocation) but Graal seems to support SSA-based register allocation, nice.

[1] https://news.ycombinator.com/item?id=11210948

[2] https://en.wikibooks.org/wiki/GNU_C_Compiler_Internals/GNU_C...

SSA is standard for the middle end but not for the backend. According to my knowledge there are only two compilers with an SSA-based backend: libFirm (www.libfirm.org) and the Go compiler.

Does anyone know an open source tool for monoalphabetic (or polyalphabetic) substitution that can handle arbitrary dictionaries?

Compile time is an issue of C++ but not of C.

[citation needed]

I'm sure, you can also self-compile the tip. Would be really interesting if this was done for benchmarks.

So it's not impossible, but libfirm avoids it or performs the necessary phi insertion in various places to avoid creating invalid SSA for the representation it has.

It's impossible to have one edge pointing to multiple reaching definitions.

There are theoretical benefits, but in practice, LLVM does pretty well with it's current scheme.

I think having a decoupled spilling phase is nice feature of the SSA-based scheme. However, I don't say that LLVM (or GCC) should switch to the SSA-based scheme. I just appreciate that the Go compiler switched to the SSA-based scheme, because it may bring some new insights to the research community.

At some point it lowers out of SSA, but you have to do that at some point anyway.

libfirm never goes out of SSA (since it uses a graph-based representation it's simply impossible: the data dependency edges need one target). It converts the programm to CSSA and assigns the same register to all phi operands. When finally emitting the program, phi nodes emit nothing.

Yes, in the middle end, but they don't have an SSA-based back end (for example SSA-based register allocation).

After libfirm [1], the Go compiler now seems to be the second mature compiler with an SSA-based backend. I hope more compilers will follow.

I missed some references to corresponding papers in the source code. For instance, is the register allocator an implementation of "Linear Scan Register Allocation on SSA Form" [2]?

Also some facts mention in comments [3] are a bit scary but I guess this will be resolved over time.

[1] http://pp.ipd.kit.edu/firm/

[2] http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer1...

[3] https://github.com/golang/go/blob/master/src/cmd/compile/int...

As stated in [1] they use a variant of "Simple and Efficient Construction of Static Single Assignment Form" [2], which does not require a dominator tree (or a liveness analysis).

[1] https://github.com/golang/go/blob/master/src/cmd/compile/int...

[2] http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun1...

libfirm (http://pp.ipd.kit.edu/firm/) uses SSA-based register allocation (http://d-nb.info/986273813/34), which allows a decoupled spilling phase. Moreover, the register assignment becomes polynomial, while register coalescing remains NP-complete.

You are right, this should be static single assignment.

There are a lot of compiler optimizations that uses global analyses/optimizations that are not covered by optimizing a sequence of assembly instructions. Thus, I doubt that CompCert + STOKE would reach the code quality of production compilers.

Nevertheless, I agree that superoptimizers ofter find optimizations that are not considered by the compiler engineers. Another good example is the Optgen tool [1] that also identified missing (machine-independent) optimizations in all production compilers.

[1] http://pp.ipd.kit.edu/optgen/

That's because a) the initial STOKE paper (2013) is older than Souper (initial commit 2014) and b) there is no Souper paper so far

Documentation->LLVM: http://pp.ipd.kit.edu/firm/LLVM ;-)

That sounds like an (e-)SSA-based optimization but not like an SSA backend.

Does anyone know the current state of the SSA backend mentioned in https://news.ycombinator.com/item?id=9099744 ?

Jump threading can also enables additional optimizations. For instance, if you apply jump threading to

int eight(int a) { int b; if (a) { b = 1; } else { b = a; } b += 3; if (a) { return b + b; } else { return b + 5; } }

you duplicate the "b += 3;" but both branches can be optimized afterwards. In fact, the function always returns 8.

I do not have an example for Souper, but the Optgen tool uses similar techniques and the paper provides a list of missing optimizations for LLVM, GCC and ICC: http://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwa... .

The permutation problem is not related to IR superoptimization itself.

The goal of an optimization pass is to improve the performance of an average, and that's exactly what the IR superoptimization does.

My advisor once said "Optimization means: sometimes, it is not getting worse", and that's excactly what happens if you perform any optimization on IR level. You don't have any guarantee that your result is optimal (regarding whatever). That's exactly the reason why Massalin introduced the term superoptimization, because on machine level you can provide such guarantees for the considered instruction sequence.

Of course there a cases where preventing an IR optimization can trigger a more powerful one and the resulting code gets better. However, in general I would say it's the other way around: Performing the IR superoptimization leads to better code quality.

The advantage of performing superoptimization on IR level is that you have explicit data dependencies (due to SSA form). Thus you don't have unrelated instructions in between. Figure 1 of the cited Optgen paper http://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwa... shows an example that can be optimized with IR-based superoptimization but not with a machine-specific one.

In summary, no approache subsumes the other one. Thus, it is worthwhile to have them both.

What do you mean by more advanced?

The LLVM implementation is more mature from a software point of view, but libFirm's implementation supports more PBQP reductions, and thus may find a better PBQP solution.