thedigitalengel

In any case, Java's stack-based bytecode is really a register machine in disguise. It isn't a general stack machine -- for instance, at a given "PC" the shape of the expression stack (i.e. the number and "basic" types of elements in it) needs to be constant.

The right way to look at Java's bytecode stream is opcodes for a register machine with _implicit_ input and output registers. Mapping it to a compiler IR would not be easy in the general case if that weren't true.

Thank you for taking time out to comment! :)

> But you said that the JMM guarantees that all reads in C_i - C_(i-1) > will see writes in C_(i-1); this means that C_3 which reads > `tuple.nonVolatileF` will see the write to that variable in C_2, no?

Talking about such things in English is ambiguous. The formal statement is

"For any read r ∈ C_i −C_(i−1), we have W_i(r) ∈ C_(i−1) and W(r) ∈ C_(i−1)".

A clearer way to state the clause in English is "writes seen by reads in C_i - C_(i-1) belong to C_(i-1);". I can justify an execution as long as reads (ultimately) seen any write in the commit previous to the one it is in, subject to happens before consistency. To prevent causality loops, the JMM allows a read to see a write that happened before it in the commit that introduces it. Then, to allow certain interesting optimizations, the JMM allows us the bait-and-switch the write a read saw -- "Each read r in C_i − C_(i−1) must see writes in C_(i−1) in both E_i and E, but may see a different write in E_i from the one it sees in E.".

The non-volatile read is _allowed_ to see the non-volatile write (i.e. such an execution exists, this is the question I ask in the exercise), but it doesn't have to. The transform in question is illegal because the transformed program allows behavior that the untransformed program didn't allow -- the transform breaks semantics.

> Since you're constructing an execution, why didn't you interleave > the execution to make this trivially true?

I don't understand this, make /what/ trivially true? In any case, the transformed program has a data race, and so observationally it doesn't need to have a sequentially consistent execution. Specifically, it is allowed to show behavior that cannot be described by any interleaving of the instructions streams of the individual threads.

> Also, can't you wrap the writer in an atomic block during > transformation?

What purpose would that serve?

> Should the first 'illegal' read legal?

Well it depends. :) I did mean "illegal", though there certainly are many illegal transforms that look legal and vice versa.

Unfortunately, the solution ultimately proposed doesn't work in this case:

  int _a = 50;
  int result = min(num, _a);

you end up expanding to "int _a = _a;" which creates a new int _a, and assigns it to itself.

Thank you for taking out time to comment. :)

> - It doesn't address how you decide which edges to speculatively > consider executable. > > - Optimizers intentionally do not play the "what if" game and try > optimizing things multiple different ways to see what wins or what > gains might be had. It simply gets too expensive (in compile time) > too quickly.

My use case was that you already have a set of edges that profiling tells you is "rarely taken", and you wish to know if eliding any of those edges improves optimization. Normally JIT compilers end up installing traps in most of these edges, hoping that the cost of the occasional side exit to the interpreter is worth the added performance in the fast case. I wanted a way to push the decision on whether to install a trap for a specific edge to later in the optimization process.

> - There are already other ways to achieve similar effect, > e.g. superblock formation or simple tail duplication (which can be > done for specific effect, e.g. see branch threading in LLVM).

I don't disagree here. I'll have to admit that this approach is somewhat "out there", in its current form it doesn't seem very practical.

(Disclaimer: I know nothing about Ruby, but I know some things about JIT compilers)

Another way to handle this is to assume that Fixnum#+ hasn't changed when compiling a method that is using it (maybe add a check at method entry); but when it does get redefined you "deoptimize" the methods that you compiled while holding that assumption.

Related: https://github.com/sanjoy/bfjit (a brainfuck interpreter with a tracing JIT for hot loops).

A quick solution involves starting at a corner, and placing each queen one horizontal and two vertical (a constrained knight's move, basically) away from the previous one. This works for an 8x8 board, but does not generalize to an NxN board (it is easy to see that this won't work when N is divisible by 3). Determining which N's it exactly works for is a math, not a programming puzzle, however. :)

I'm from the same place as the artagnon. Anti-weed laws are almost never enforced, and weed is incredibly cheap (you'll get enough weed to get 10 people stoned out of their minds for the price of a bottle of beer). And the ease of storage means you can easily maintain a huge stash.

A "false" register dependency is a Write-after-read (WAR) [1].

As far as three address code making register renaming easier, I'm not sure what the author had in mind -- isn't `add $5, %rax` essentially a condensed form of `add $5, %rax, %rax` (which is a 3AC)? In fact, 3AC is _more_ general and should make register renaming harder if anything at all.

[1] http://en.wikipedia.org/wiki/Register_renaming

For multiple functions taking different arguments you could exploit atexit's specified calling order

    data_t *global;
    
    int main() {
      atexit(callback);
      atexit(set_global_to_x);
      atexit(callback);
      atexit(set_global_to_y);
    }

Since functions are called in reverse order of their installation using atexit, you end up with two calls to callback; one with global set to y and one with global set to x.

I don't know if this counts, but the linux kernel famously uses a JIT to filter network packets:

https://github.com/torvalds/linux/blob/master/arch/x86/net/b...

It isn't truly arch-independent till it assumes PARAMETER_CONSTANT and FUNCTION_CONSTANT will be stored as direct immediates in the generated code. On some archs, for instance, 0xFEEDBEEF might be too big a constant; and the compiler would then be forced to move it to a register (or a stack slot) in parts.

Edit: and of course, you run the possibility that on some archs, 0XFEEDBEEF is actually a valid encoding for some instruction. :)

On llvm: http://llvm.org/docs/LangRef.html#trampoline-intrinsics

Representing self is actually not that difficult or mind-bending; you just need a representation that is isomorphic to the program source. For instance, you could store the ASCII symbols in an integer array:

  int array = { ... } // holds the source code,
                      //  except its own representation

  int array_index; // The index in the source code
                   // (where the actual integers in
                   // array interpreted as source appear)

  for i = 0 to array_index:
    print (array[i] as an ASCII character)

  for i = 0 to array_length:
    print (array[i] as integer ++ ", ")

  for i = array_index + 1 to array_length:
    print (array[i] as an ASCII character)

The core idea is that you can interpret `array` in two ways, as an array of integers or an array of ascii characters representing the program source. The only difficult part is adjusting array_index. With a little effort, this can be scaled to a chain of languages.

I was very lucky in the sense that I could participate in two Google Summer of Code programs. With some relevant experience, I'm now in a good position to get the exact kind of job I want (which also happens to be related to compilers / VMs).

Would you feel secure about using a cryptographic system without a proof?

They're not the same. VMs can assume invariants (which may not always hold) and compile specialized methods which depend on those assumptions and then fall back to a non-optimized version during the execution of a method. To do something like that (OSR) in C, you'll have to have a very sophisticated runtime.

The point is, unless you are using some macro magic in C, you'll almost always have to make such a compromise to get an abstracted out sort function.

This is the best -- I've literally built my software engineering career pivoting off this program.

I think the total budget is of the order of several million dollars.

Right now, the macros are very naive -- they are passed the entire unevaluated AST on which the macro is invoked and the new AST they return is used instead. I think this makes them FEXPRs. They do capture the defining lexical environment.

Thanks for the link, looks very helpful.

This is really a no-risk, learning project, so I'll probably try to implement System F in some form; eventually. It isn't an assignment and I have no deadlines.

But, yes, I agree that starting with some simpler type system (Hindley Milner maybe) will probably be more approachable and will give me a good base to build on.

There is a list here: http://www.haskell.org/haskellwiki/Template_Haskell#Projects

I'm a Haskell newbie, and have not done much with TH yet. But I can imagine a bunch of TH code generating a lexer or a parser out of some meta-description. Like Happy, but with everything directly embedded in the source itself.

That is very true, I'll definitely use TH only as a last resort. Perhaps it would be cleaner to output a list of tokens, which the compiler then parses. But then that is not much far away from generating a string. :)

This (the second) way of doing things looks much more sensible -- thanks!

Neither have I. I just find it very beautiful.

Reminds me of Tyler:

It's only after you've lost everything that you're free to do anything.

I can't say much about "Dive into Python", since I've not read it.

I've always found SICP quite overrated (I'm saying this after reading it).

Given Python's learning curve, a much better curriculum would involve going through the codebase of a few well-chosen projects, sending in a few patches and perhaps writing a report on the high-level design of the piece of software or on how the project solves a particular problem (how does XYZ handle i18n? how does ABC stay stable even on a failing network?)