gsg

Perhaps mincaml: https://github.com/esumii/min-caml

It's a small (few thousand lines), rather neat, weakly optimising compiler for a subset of OCaml, written in OCaml. It has more than one backend, a few optimisations, a register allocator. No SSA form or 'advanced' stuff though.

Interesting. MLton did the basic-blocks-with-arguments thing too:

  http://mlton.org/pipermail/mlton/2007-February/029597.html
  http://mlton.org/pipermail/mlton/2003-January/023061.html

> extract the same information again in hardware

It isn't necessarily the same information. OoO engines happily speculate through branches without waiting for a test value to become available, forward values based on exact addresses rather than a static approximation thereof, etc. There are real advantages to doing things dynamically.

I don't think that needs to happen. From the article:

"Basically, we re-enter a clone of the loop from above…. a clone specially made to be re-entered at any iteration"

This is put forward as the explanation for how variables are mutated in the debugger, but as a mechanism for "un-unrolling" the loop it probably serves to support such conditional breakpoints too.

Populating x86-64 floating point registers is also an amusing subject.

The obvious instruction for loading a (64-bit) float into an xmm register is movsd. With a memory source operand, the higher part of the register is zeroed, which is what you want. No problem.

Now the fun part: if the source is not memory but another xmm register, the higher part of the register is not zeroed. This induces a false dependency on the previous value of the destination register that can cause performance issues. To avoid this problem, such register-register copies should be done with a packed move instruction. (Or vmovsd, but that was added much later.)

The obvious packed move instruction for 64-bit floats is movapd, but we can do better than that by using movaps - it is still a float domain instruction but is a byte smaller.

So the optimal way to move a single double from one register to another is to use a vector move of the wrong type.

This is an interesting design question - which layer should be backwards compatible and under which significant freedom of design is allowed.

I'm not at all sure that the best answer is "source code". For x86 CPUs the compatible layer has been the ISA and that has turned out pretty damn well, suggesting that source compatibility is not the only and may not be the most effective choice.

Particularly if the source is C, which is rather ambiguous compared to most machine languages.

> In the name of software compatibility

You say this as if it is a bad thing (or am I misinterpreting here?), but compatibility is enormously valuable. That's why the strategy of choosing compatibility over cleanliness of architecture is so widespread in successful complex systems - ISAs, OSs, the Web, programming languages, etc etc.

It's hard to love the resulting complexities, but remaining compatible really is almost always the right thing to do.

Having TurboFan compile the interpreter from machine-independent templates is what struck me as unusual.

The rest is familiar enough, true.

Interesting decision.

The architecture sounds a little unusual:

"The interpreter itself consists of a set of bytecode handler code snippets, each of which handles a specific bytecode and dispatches to the handler for the next bytecode. These bytecode handlers are written in a high level, machine architecture agnostic form of assembly code, as implemented by the RawMachineAssembler class and compiled by Turbofan"

It also seems as if all calls are mediated by code generated by the compiler, which has the advantage of avoiding the awkwardness of different calling conventions between native and bytecode functions (possibly at some cost to performance?).

Fascinating reading. Thanks V8 people for allowing such documents to be public!

DEC deliberately moved away from VAX to work on Alpha, which performed quite well for its time.

John Mashey made some interesting comments on the (lack of) future prospects for the VAX here: http://yarchive.net/comp/vax.html

The structured SSA building algorithm I had in mind has a fairly simple extension that covers break, continue, and early return. It's more complicated, but still way simpler than iterated dominance frontiers.

> you can always compute a loop forest

It's easier to not have to.

Yeah. Even basic things like building SSA can be done more simply on "structured" CFGs.

The benefits are enough that data structure and algorithm designs in the JVM compiler world often take advantage of assuming reducible control flow even though Java bytecode can express irreducible CFGs. Instead, such programs are left to the interpreter.

It's not true that traditional code generation approaches ignore this problem. Copy coalescing is a well-studied problem - the problem is that solving it optimally is expensive enough that compilers use heuristics[1]. Sometimes they don't do what you want. (Any reasonable allocator should catch the case that you mention, though.)

Higher quality compilers will also try things like commuting instructions, using lea as a three-address add, etc to avoid a move.

[1] Some recent progress on register allocation over SSA may improve this situation, but I don't think that work has made it into production compilers yet.

Calls and other instructions that use specific registers (variable shift and division on x86, for example) tend to ruin that ideal somewhat.

I wonder what percentage of those xors are for generating zero? I would guess a large majority of them.

Note that you don't need a dumb compiler, register pressure, or an instruction with physical register constraints to require a copy. Two-address instructions suffice: simply have a register for the first operand that contains a value that is used later. A copy is required to preserve the value stomped by the mutating instruction.

In any case I believe the point of the GP is that any necessary copy can be done by going through memory, so register-register moves can be dispensed with where minimalism is the goal.

Fair enough! Good luck with your rewrite.

That's an admirable sentiment, but aren't your hands tied by the promises made by the standard? In particular the addresses of elements are guaranteed to be stable, which would seem to prevent an implementor from relocating them to achieve more cache-friendly layout.

(Of course, you would want to do as well as possible within the given bounds.)

That doesn't quite fit with "you already know exactly what it does" - you left out a detail.

Whether it is reasonable to leave that out or not, the point is that it takes a lot of text to unambiguously cover every possible facet of meaning even for tiny, simple operations.

Does it mutate the list in place or return a new one?

The old UNCOL dream, still alive after all this time.

You'd think people would learn.

Multiple real implementations of register VMs have three operand instructions. Lua, Luajit and Guile are examples that I'm familiar with. For that matter, many ISAs feature three operand instructions. Even some of the recent extensions to x86-64 are three operand versions of (some of) the vector instructions.

If you think three-operand instructions aren't common in both hardware and interpreter design, you are simply misinformed.

None of this has anything to do with SSA. SSA IR can be reasonably constructed from any of stack, accumulator, two-operand register or three operand register bytecode. All of the usual optimizations follow from that.

> the VM speed is much faster than with two or multi word ops

While variable length encodings are best avoided, that doesn't rule out three operand instructions. For a good example of an extremely fast interpreter that uses such instructions, have a look at luajit.

> Nobody does that, it's not needed.

That's what the OP was suggesting, so that's what I was discussing.

JIT compilers aren't really an argument either way, as you can do tracing or transform to an SSA graph from either representation quite easily. All the real complexity is further down the compilation pipeline.

I (half) wrote a toy trace compiler based on a register bytecode a while back. Writing the front end was quite pleasant - the difficult parts were back end stuff like figuring out how to support trace exit information. (The difficulty there is that you might want to perform stores, materialize objects etc as you go off trace as part of store and allocation sinking.)

That would be very inefficient, because registers cannot be indexed. The dispatch you have to introduce to jump to code that references the right physical regs would murder you with mispredictions.

Also, register VMs typically have three operands. Specialising each instruction for each possible register for three operands would result in a ridiculous volume of code.

Special purpose instructions that access fixed registers would be fine, but general purpose operand references cannot be sanely implemented in this way. Existing register VMs use memory because it's faster.

Interesting.

A while back I did some rough tests on search of arrays in depth first order. The hope was that the better contiguity (the next element in the array is the next element to test 50% of the time) would lead to better search performance, but I wasn't able to observe much of a difference in practice.

I also found that while writing the search operation was very easy for arrays in this order, insertion was much more difficult.

Yes. Various parts of the stdlib are intended to be used by catching Not_found or End_of_file or whichever exception happens to be relevant.

It's not what I would have done.

(Mark text as code by putting it on a fresh line with two or more spaces in front. I don't think there is a way to do this inline.)

Oops, breaks on empty files. I should have matched on the input_line chan in sum_channel to catch End_of_file - damn exceptions.

print_string should also be print_endline to match the original.

Hmm, the OCaml could be a lot shorter:

    let rec fold_channel f acc chan =
      match input_line chan with
      | line -> fold_channel f (f line acc) chan
      | exception End_of_file -> acc

    let comma = Str.regexp ","

    let values_of_line line =
      List.map float_of_string (Str.split comma line)

    let sum_channel chan =
      let folder line tot = List.map2 (+.) tot (values_of_line line) in
      fold_channel folder (values_of_line (input_line chan)) chan

    let sum_and_print_file filename =
      let chan = open_in filename in
      sum_channel chan |> List.map string_of_float |> String.concat "," |> print_string;
      close_in chan

    let () =
      match Sys.argv with
      | [|_; filename|] -> sum_and_print_file filename
      | _ -> failwith "Exactly 1 filename must be given"

This is also a bit faster, and almost all of the difference is because I hoisted the Str.regexp ",". I suspect using a split-on-character operation would make a bit more difference there, but of course the spartan OCaml stdlib lacks such a function.

"Race to sleep" is a well known power saving strategy.

> This of course ignores leakage

You can't ignore leakage. The ability of a chip to turn off currently unused silicon is crucial to power management on modern devices.

The large volume of -O0 code is just a result of skipping register allocation to save compilation time. There's no problem here.