Jump to content

  • Log In with Google      Sign In   
  • Create Account

- - - - -

AngelScript JIT/AOT implementation details (technical)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
49 replies to this topic

#21 Andreas Jonsson   Moderators   -  Reputation: 3499

Like
0Likes
Like

Posted 29 June 2009 - 11:56 AM

Thanks, midnite. I'm sure these will come in handy.

After a quick glance at them, it would seem that the JIT interface that quarnster is defining ought to work with an LLVM implementation as well.
AngelCode.com - game development and more - Reference DB - game developer references
AngelScript - free scripting library - BMFont - free bitmap font generator - Tower - free puzzle game

Sponsor:

#22 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 03 July 2009 - 12:54 AM

I wonder about the current use of "jitOffset" though when using that with LLVM. The current way it is used implies that each jitOffset in the buffer is a separate function entry point, which is fine for a handrolled buffer as we know exactly how this convention works.

However take an LLVM jit implementation, a for-loop and a script function call in that loop. That would mean that the beginning and the end of the for loop are in different functions, which, I'm sure, would prevent LLVM from optimizing the code as good as it could have. Also, either these functions would have to call eachother to satisfy the loop (and likely run out of native heap very quickly) or they would have to break out to the VM all the time.

Thus I suggest that offset 0 in the jit buffer is always used as the entry, and the jitOffset is turned into an implementation specific ID of which SUSPEND instruction execution should resume at. In other words, jitOffset is used as an argument to the jit function.

In the simplest case, the jit would just give out this ID as the offset into the buffer and then the code at offset 0 is just a "branch to offset" instruction. But what the ID actually means AngelScript does not care about.


#23 Andreas Jonsson   Moderators   -  Reputation: 3499

Like
0Likes
Like

Posted 03 July 2009 - 02:27 PM

Yes, I agree. The jitOffset should probably be an argument to the function.

I see it like something like this:


void jitFunction(asSVMRegisters *regs, int jitOffset)
{
// Extract the needed VM values into local variables (or registers)
...

// Jump to the correct starting point, based on jitOffset
...

// Function implementation
...
}


asSVMRegisters is local structure within the asCContext that holds all the values for the VM that the JIT function needs to be able to do its work.
AngelCode.com - game development and more - Reference DB - game developer references
AngelScript - free scripting library - BMFont - free bitmap font generator - Tower - free puzzle game

#24 RAZORUNREAL   Members   -  Reputation: 567

Like
0Likes
Like

Posted 04 July 2009 - 03:31 AM

Is there a reason you can't simply have the JIT code natively call a function which then executes the correct script function? So all calls to script functions in JIT code would be compiled as a call to this single wrapper function, with arguments determining which script function to execute. There would probably be tricky details, like I don't know enough about angel script to know what to do with the context, and the wrapper function would have to do something with return values, but I thought it seemed feasible.

#25 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 04 July 2009 - 09:07 AM

A JIT still need to support the resume points to be able to handle suspending scripts, debugging and co-routines. So as it already must be taken care of, and as data must be saved and restored in either case, the difference of branching backwards (return to the VM) or forwards (call into some function which then calls into the VM) when making a call from a script isn't that big.

#26 Andreas Jonsson   Moderators   -  Reputation: 3499

Like
0Likes
Like

Posted 05 July 2009 - 06:49 AM

Besides, this is only going to be one of the options for JIT compilation. This one will optimize the execution speed, but won't take away any features.

The other option that will eventually be available as well will completely substitute the bytecode for native code so the VM isn't invoked at all. In this option, it is necessary that the JIT compiled code will make the actual function calls itself. On the other hand, with this option you'll likely loose the ability to suspend the code or debug it.
AngelCode.com - game development and more - Reference DB - game developer references
AngelScript - free scripting library - BMFont - free bitmap font generator - Tower - free puzzle game

#27 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 15 July 2009 - 04:05 AM

I've stumbled upon Nanojit (https://developer.mozilla.org/En/Nanojit) which I personally find very interesting. It is very small (yes I care), it is the backbone of Firefox's javascript JIT and seems to have support (judging by the source code filenames) for ARM, x86, PPC, SPARC and x64.

I'm definately going to have a closer look and might abandon my homerolled ARM code if I find that Nanojit does everything I want.

#28 Wavesonics   Members   -  Reputation: 330

Like
0Likes
Like

Posted 15 July 2009 - 05:23 AM

That looks like a fantastic project! I was just reading some of the overview on it.

The Guards sound like a fantastic way to allow for lots of higher level functionality that scripting languages offer.

The only difficulty i see is writing an intermediate layer that translates between AngleScript byte code, and Nanojit's LIR.

Is AngleScript's byte code roughly RISC, or CISC in nature? A mismatch between Nanojit's LIR and AngleScript's byte code could be a pain there I would think.

Another thing I was wondering, obviously there would be different compiled versions for ARM vs x86, but would an x86 build be able to detect SSE2, SSE3 ect, and use those instructions automatically?

This is exciting, looking forward to seeing how this develops!

#29 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 15 July 2009 - 06:24 AM

Angelscript is CISCish (as it should be). As ARM is RISC i've already had to deal with some of the issues there, although I'm interested to see what (if anything) Nanojit optimizes. It seems for example that it doesn't support 32-bit floats but always use 64-bit doubles for any floating point operations, which is a bit nasty.

Unsure whether Nanojit supports SSE*, but if you really need that level of optimization handwritten assembly routines registered with the angelscript engine is probably better than putting your trust in a jit compiler.

The speed up over normal bytecode interpretation on ARM is going to be many, many times faster no matter how lousy the JIT is just due to the fact that all the branches between the instructions goes away.

In a very specific case I measured my current JIT to be ~27 times faster, and about half the speed of native compiled code with full optimizations turned on. Now this was a very optimistic case where I knew that it was going to be as fast as possible, so is in no way representative of the final script performance.

Also having said that, Nanojit is opensource so you are always free to hack it as you please yourself. And again, nothing stops anyone wanting to use LLVM or any other technology to use, I'm personally just not interested in it.

#30 Andreas Jonsson   Moderators   -  Reputation: 3499

Like
0Likes
Like

Posted 15 July 2009 - 02:24 PM

Yes, AngelScript is CISC in nature. RISC would be way too slow for a VM. Currently AngelScript has 176 different bytecode instructions.

NanoJIT and LLVM seems to work pretty much the same way. The application would build a buffer or intermediate code using a basic instruction set, and then ask the JIT compiler to produce the machine code for it.

LLVM is more generic than NanoJIT, as the latter is probably created specifically to compile javascript code. So while it is much smaller than LLVM it is probably not too well suited for AngelScript due to AS having many more specific datatypes than JS.

By the way, the interface for a JIT compiler plug-in is already available in the WIP version, so if anyone else than quarnster is interested in playing around with producing a JIT compiler for AS you can start already. In fact, it would be very valuable to get feedback on this interface as early as possible.




AngelCode.com - game development and more - Reference DB - game developer references
AngelScript - free scripting library - BMFont - free bitmap font generator - Tower - free puzzle game

#31 Wavesonics   Members   -  Reputation: 330

Like
0Likes
Like

Posted 15 July 2009 - 03:19 PM

Ya I would think decomposing a CISC instruction into it's equivalent RISC sequence would be much more painless then take a sequence of RISC instructions and trying to synthesize the correct CISC instruction, especially after a scheduler tried to optimize the it :P

I would love to take a look at the interface, I've been reading up on LLVM my self. Things at work are crazy at the moment, and I'm trying to push my own little project that uses AS out the door. Hopefully it will all clear up soon and I can poke around with LLVM :D

#32 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 15 July 2009 - 08:50 PM

The problem I have myself with LLVM is that it is such a big beast and not really well suited for embedded environments where memory constraints are an issue. I don't think the data types will be a too big issue with Nanojit though, it supports loading of 8,16,32,and 64 bit types, but sign extends them into 32-bit or 64-bit depending on the type you wish to operate on. Ie the same as the native machine code does.

The bigger win of LLVM is that it's capable of some serious optimization of the generated code.

But at this moment in time, no matter what solution is chosen the bottleneck is still very likely to be having to breakout to the VM for "special" bytecode instructions.

Also, while I'm at it, if AS could inline small functions that would already be a win. Or if the JIT compiler could access another function's bytecode (and length) it could possibly do this inlining itself? Although it might get nasty with AS's stack if the JIT compiler does it. Which again goes back to the problem of trying to implement the more complex instructions of AS in a JIT...

#33 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 16 July 2009 - 06:04 AM

Reading up more on Nanojit and Tracemonkey I am now seriously interested in the trace tree approach, which btw also happens to be what LuaJIT 2.x is using http://lua-users.org/lists/lua-l/2008-02/msg00051.html.

Recommended reading: http://www.ics.uci.edu/%7Efranz/Site/pubs-pdf/ICS-TR-06-16.pdf, http://www.usenix.org/events/vee06/full_papers/p144-gal.pdf

In short (and a bit simplified) it records all instructions encountered for a specific path, inlining function calls and in the end you basically end up with a completely flat code version of that "hot path", ie no branches. There are some other very nice optimizations that can be done as the whole path is known and specific for that hot path.

#34 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 18 July 2009 - 12:11 AM

This libjit branch looks interesting too (and claims to have support for MMX/SSE/SSE2/SSE3): http://code.google.com/p/libjit-linear-scan-register-allocator/.

The claim of "LibJIT is probably the best free library for development of advanced Just-In-Time (JIT) compilation in virtual machine runtimes, implementating domain-specific languages, dynamic programming languages, and scripting languages" is a bit arrogant, but for all I know it could very well be true.

And for reference, there's also GNU lighting: http://www.gnu.org/software/lightning/ (although this one has no ARM support so not personally interesting).



#35 Wavesonics   Members   -  Reputation: 330

Like
0Likes
Like

Posted 18 July 2009 - 05:16 AM

Don't love that libJIT is LGPL :/

LLVM is essentially BSD from what I read which is nice, also take a look at this:
Quote:

The other nice thing about LLVM is that since it's completely modular, you would only link in the portions that you need. If you were building a JIT application like libjit would be used for, you would choose the core library, the JIT library, a code generator for the current target and that's about it. You could choose to add a bytecode reader or .ll file parser if you wanted to, but as we've discussed to death, that is not required.


Sounds like LLVM *can* be light weight, or atleast *lighter* weight.

#36 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 18 July 2009 - 11:10 AM

That is an interesting point. I must confess that I have not actually tried llvm out myself and maybe it does fit my needs just fine. BTW, my own homerolled jit has come to the point now where it no longer is fun and the problems involved just get nasty (like register allocation, register merging from several code paths, register conflicts (float vs int) when exiting the jit from different SUSPEND positions, and probably lots more that I've repressed). Hence I'm looking at these projects to see if they can solve some of the nasty bits for me so I can go one with the other fun bits, like you know, actually making AS faster :)

#37 quarnster   Members   -  Reputation: 266

Like
0Likes
Like

Posted 18 July 2009 - 07:07 PM

Ehhh, seems the executable size of even creating a tiny, tiny JIT with LLVM is 7.6MB? This is their own "HowToUseJIT" example that comes with the LLVM package and that is totally unacceptable to me. On the good side if anyone does want to take the LLVM approach it would be veeery quick and easy to implement a basic JIT as the compiler can output the cpp code that would build the LLVM graph: http://stackoverflow.com/questions/504389/how-would-you-re-use-c-opcode-implementations-when-writing-a-jit-with-llvm.

#38 Wavesonics   Members   -  Reputation: 330

Like
0Likes
Like

Posted 19 July 2009 - 03:43 AM

ya holy crap, that's pretty big :P

#39 Andreas Jonsson   Moderators   -  Reputation: 3499

Like
0Likes
Like

Posted 20 July 2009 - 01:08 PM

Quote:
Original post by quarnster
Also, while I'm at it, if AS could inline small functions that would already be a win. Or if the JIT compiler could access another function's bytecode (and length) it could possibly do this inlining itself? Although it might get nasty with AS's stack if the JIT compiler does it. Which again goes back to the problem of trying to implement the more complex instructions of AS in a JIT...


AngelScript will eventually have capability of inlining smaller functions.

While technically it would be possible for the JIT compiler to inline functions by itself, it would have to make sure it never breaks back to the VM when inside an inlined function as AS wouldn't be aware of the function call then. Unless of course the JIT function would be allowed to update the call stack as well, which I think would be going too far in the JIT compilation.


AngelCode.com - game development and more - Reference DB - game developer references
AngelScript - free scripting library - BMFont - free bitmap font generator - Tower - free puzzle game

#40 Wavesonics   Members   -  Reputation: 330

Like
0Likes
Like

Posted 20 July 2009 - 01:14 PM

Seems like the most important thing about a JIT is that it preserves all functionality and expected behavior of the normal interpreted version.

Sounds like you would start to run into some small problems w\ JIT controlled in lining...

Anyway quarnster, have you done any tests with nanoJIT, how large/small does that turn out to be?

My project is MIT License, so I couldn't use nanoJIT except as a DLL, but I suppose that would be do-able if it works out well... would it? idk...




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS