The llvmcompiler branch

Truecolor ZDoom with extra features and some unofficial/beta GZDoom features.
[Home] [Download] [Git builds (Win)] [Git builds (Mac)] [Libs (Win)] [Repo] [Bugs&Suggestions]

Moderators: Rachael, dpJudas

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 8:38

I'm almost done with porting all the true color drawers to use LLVM instead of C++ SSE intrinsics. Even the first version where I haven't even tried to optimize the codegen seems to be able to compete with what MSVC generated. Span and wall drawers are done, with just sprite/column drawers left to go.

I'd like to merge this back into the master branch once I'm done with the column drawers, if that's alright. The only catch is that you will have to compile LLVM first before being able to compile QZDoom. On the plus side it gives a much much better way to add new drawers variants or increase the speed of the current ones. It will also allow me to delete literally thousands of lines of drawer code from r_draw_rgba and r_drawt_rgba. :)

User avatar
Rachael
Developer
Developer
Posts: 3617
Joined: Sat May 13, 2006 10:30

Re: The llvmcompiler branch

Post by Rachael » Fri Sep 30, 2016 8:57

That should be fine. XD Are there any guides to setting up LLVM? I'd prefer to get that ready before you do the merge.
Spoiler: Zen Sarcasm

User avatar
Graf Zahl
GZDoom Developer
GZDoom Developer
Posts: 7148
Joined: Wed Jul 20, 2005 9:48
Location: Germany
Contact:

Re: The llvmcompiler branch

Post by Graf Zahl » Fri Sep 30, 2016 10:27

Can this later also be used to compile the DECORATE code?

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 17:44

Eruanna wrote:That should be fine. XD Are there any guides to setting up LLVM? I'd prefer to get that ready before you do the merge.
I just downloaded the latest release tar.gz from llvm.org and then opened it with CMake. The only external dependency it asked for was Python for building. Maybe the most important detail is that I had to change the following two options in CMake when compiling LLVM:

LLVM_USE_CRT_DEBUG = MTd
LLVM_USE_CRT_MINSIZEREL = MT
LLVM_USE_CRT_RELEASE = MT
LLVM_USE_CRT_RELWITHDEBINFO = MT

Those settings change LLVM to output static libraries compatible with ZDoom. If you don't do this part you'll get a bunch of linker errors when compiling QZDoom.

After LLVM finished compiling you need to tell QZDoom's CMake where to find it. I used the following path on my computer:

LLVM_DIR = C:/Development/Environment/Src/llvm-3.9.0/build/lib/cmake/llvm

That's it. CMake itself does the rest, linking the two together, and you can build QZDoom as usual.
Graf Zahl wrote:Can this later also be used to compile the DECORATE code?
I don't know the DECORATE part too well. Is it using an interpreter today? If it is, there's a good chance it would useful. In particular for something like DoomScript/ZScript it would save a ton of time as you wouldn't have to write the back-end of the compiler.

User avatar
Graf Zahl
GZDoom Developer
GZDoom Developer
Posts: 7148
Joined: Wed Jul 20, 2005 9:48
Location: Germany
Contact:

Re: The llvmcompiler branch

Post by Graf Zahl » Fri Sep 30, 2016 18:18

dpJudas wrote:
Graf Zahl wrote:Can this later also be used to compile the DECORATE code?
I don't know the DECORATE part too well. Is it using an interpreter today? If it is, there's a good chance it would useful. In particular for something like DoomScript/ZScript it would save a ton of time as you wouldn't have to write the back-end of the compiler.

At the moment it compiles to a RISC inspired bytecode. The parsed data before the code generation is compiled to a tree-like expression structure for each function, which in a second pass is then converted to the bytecode. Of course for more extensive scripting this will bring a performance hit, so if the VM could be replaced with compiled native code, it'd not only get rid of the VM (which is way too obtuse for my taste) but also would enable converting larger portions of the engine to script code.

Actually, if I could get a hang on what to feed to the code generator it'd be something I'd really like to do. And if this is going to be done it should be before the scripting stuff sees further development so that it doesnt make too much use of features that are not natively doable without considerable overhead.

User avatar
Rachael
Developer
Developer
Posts: 3617
Joined: Sat May 13, 2006 10:30

Re: The llvmcompiler branch

Post by Rachael » Fri Sep 30, 2016 19:04

Well I am compiling it now. Once it's done I'll give the branch a try. :)
Spoiler: Zen Sarcasm

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 19:12

Graf Zahl wrote:At the moment it compiles to a RISC inspired bytecode. The parsed data before the code generation is compiled to a tree-like expression structure for each function, which in a second pass is then converted to the bytecode.
What you're describing there sounds like a perfect match: an abstract syntax tree that outputs bytecode. The main thing to change then should be to map over each emit of a RISC bytecode to the equivalent LLVM IR bytecode.

My approach would be to use llvm::IRBuilder<> directly to emit the IR. You'll probably find section 3 of their Kaleidoscope tutorial interesting:

http://llvm.org/docs/tutorial/LangImpl03.html

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 19:26

Eruanna wrote:Well I am compiling it now. Once it's done I'll give the branch a try. :)
Excellent! Are you doing a 32 bit or 64 bit build?

User avatar
Rachael
Developer
Developer
Posts: 3617
Joined: Sat May 13, 2006 10:30

Re: The llvmcompiler branch

Post by Rachael » Fri Sep 30, 2016 19:35

64-bit. Please don't tell me I have to recompile 32-bit in order to make 32-bit .exe's with this. >_> It's still not done compiling the 64.
Spoiler: Zen Sarcasm

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 19:43

Eruanna wrote:64-bit. Please don't tell me I have to recompile 32-bit in order to make 32-bit .exe's with this. >_> It's still not done compiling the 64.
I'm afraid you also need to build LLVM again with a 32-bit setup to build the 32 bit exe's - probably in a different build output directory for CMake. The good news this is a one-time thing - once LLVM is built you won't have to do it again for a long time. :)

I think my current version is 32-bit right now. Please let me know if it crashes when you start a game. Theoretically, it should all work. But one never knows!

User avatar
Graf Zahl
GZDoom Developer
GZDoom Developer
Posts: 7148
Joined: Wed Jul 20, 2005 9:48
Location: Germany
Contact:

Re: The llvmcompiler branch

Post by Graf Zahl » Fri Sep 30, 2016 19:53

dpJudas wrote: My approach would be to use llvm::IRBuilder<> directly to emit the IR. You'll probably find section 3 of their Kaleidoscope tutorial interesting:

http://llvm.org/docs/tutorial/LangImpl03.html
Since you seem to already know a bit of this stuff, can you give me a quick summary of what code from LLVM I need so that I can quickstart the whole thing?

User avatar
Rachael
Developer
Developer
Posts: 3617
Joined: Sat May 13, 2006 10:30

Re: The llvmcompiler branch

Post by Rachael » Fri Sep 30, 2016 21:23

Alright - well I hate to be the stinker in this whole mess but it has to be said.

Requiring the entire LLVM project is a bit much for a little port like ZDoom (or QZDoom). But I wouldn't mind it if bits and pieces of it could be compiled as dependencies that don't take (now going on 3) hours to compile.

There are some major issues with it as it is right now: First off, 32-bit support is still being maintained, and for QZDoom that is a significant base of users for the project. With how overwhelming this compile process is, it simply is not feasible to have a 32-bit environment and 64-bit environment ready within a reasonable amount of time for anyone else to use.

Secondly, executables are not normally provided for Linux. This means that in order to even play QZDoom on Linux - you either have to compile this stuff yourself, or just use Wine. That also means I'd have to prepare an LLVM environment for both 32-bit and 64-bit Linux, as well, if I were to provide my own executables - not to mention it's now impossible to even just test on Linux without waiting for hours again.

If the LLVM license allows it, I would not mind the specific libraries that are needed to be imported to the project as long as they do not create too much bloat, and as long as someone can import the repository and have a working executable from scratch in under 40 minutes (not counting dependency download times).

I feel right now like the cost (time) of this is a bit overkill to the benefit gained.
Spoiler: Zen Sarcasm

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 21:39

Graf Zahl wrote:Since you seem to already know a bit of this stuff, can you give me a quick summary of what code from LLVM I need so that I can quickstart the whole thing?
Sure. First you need to boot LLVM. I'd grab the LLVMProgram class from my branch to do this. The main classes we need to use after this step are:
  • llvm::LLVMContext - Used for using LLVM in multiple threads. We always only have one.
  • llvm::ExecutionEngine - The JIT compiler. We use it at the end to get pointers to our functions so we can call them.
  • llvm::Module - The container for our functions. Its equivalent in C++ is an .obj file.
  • llvm::Function - A function in a module. Create one for each function in decorate.
  • llvm::BasicBlock - A list of instructions that ends with a jump or return statement. All functions start with a basic block.
  • llvm::IRBuilder<> - Used to emit/insert instructions into a basic block.
  • llvm::Value - Immutable values. Constants, the result of an instruction, function arguments.
  • llvm::Type - Integers, floats, structs, etc.
Let's say we want to create a simple function that in C++ would be: "int foobar(int a, int b) { return a + b * 42; }". The LLVM code emitting that would look like this:

Code: Select all

void CreateFoobar(llvm::Context *context, llvm::Module *module)
{
	using namespace llvm;
	
	Type *int32Type = Type::getInt32Ty(*context);
	
	// Describe function arguments and return type:
	Type *returnType = int32Type;
	Type *parameterTypes[] = { int32Type, int32Type };
	FunctionType *funcType = FunctionType::get(returnType, parameterTypes, false);
	
	// Create function in module and its entry point basic block:
	Function *func = Function::Create(funcType, Function::ExternalLinkage, "foobar", module);
	BasicBlock *entryBB = BasicBlock::Create(*context, "entry", func);
	
	// Grab argument values:
	auto argIterator = func->arg_begin();
	Value *a = static_cast<llvm::Argument*>(argIterator++);
	Value *b = static_cast<llvm::Argument*>(argIterator++);
	
	// Constant value for 42:
	Value *constant42 = ConstantInt::get(*context, APInt(32, 42, true));
	
	// Setup builder to emit instructions into the basic block:
	IRBuilder<> builder;
	builder.SetInsertPoint(entryBB);
	
	// Emit add and mul instructions into basic block and return the result:
	Value result = builder.CreateMul(builder.CreateAdd(a, b), constant42);
	builder.CreateRet(result);
	
	// Verify that we didn't emit nonsense:
	if (verifyFunction(func))
		I_FatalError("verifyFunction failed");
}

int (*)(int, int) GetFoobarAddress(llvm::ExecutionEngine *engine, llvm::Module *module)
{
	using namespace llvm;
	
	// Tell JIT compiler to mark the memory pages executable:
	engine->finalizeObject();
	
	// Get pointer from JIT compiler:
	Function *func = module->getFunction("foobar");
	return reinterpret_cast<int(*)(int, int)>(engine->getPointerToFunction(func));
}
That's it. Generates a simple foobar function.

There's only really two things missing from the above example: stack variables and branching. As SSA variables are effectively constants, changing variables requires storing and loading them from the stack. Branching requires jump statements. All jumping in LLVM works by doing a conditional check at the end of a basic block that jumps to another basic block. A for loop function: int sum(int count, int *values) { int val = 0; for (int i = 0; i < count; i++) val += values; return val; } looks like this:

Code: Select all

void CreateForLoop(llvm::Context *context, llvm::Module *module)
{
	[... create func like in first example ...]
	
	// Grab argument values:
	auto argIterator = func->arg_begin();
	Value *count = static_cast<llvm::Argument*>(argIterator++);
	Value *values = static_cast<llvm::Argument*>(argIterator++);
	
	// Setup builder to emit instructions into the basic block:
	IRBuilder<> builder;
	builder.SetInsertPoint(entryBB);
	
	Value *constant0 = ConstantInt::get(*context, APInt(32, 0, true));
	Value *constant1 = ConstantInt::get(*context, APInt(32, 1, true));
	
	// Allocate working variables on the stack and place values in them:
	Value *stackIndex = builder.CreateAlloca(int32Type, constant1);
	Value *stackVal = builder.CreateAlloca(int32Type, constant1);
	builder.CreateStore(stackIndex, constant0);
	builder.CreateStore(stackVal, constant0);
	
	// Create three basic blocks:
	// one for the conditional check, one for the loop, and one for what should happen when the loop ends
	BasicBlock *conditionBB = BasicBlock::Create(*content);
	BasicBlock *loopBB = BasicBlock::Create(*content);
	BasicBlock *endBB = BasicBlock::Create(*content);
	
	// Jump to condition basic block
	builder.CreateBr(conditionBB);
	
	// Emit to condition basic block, grab index from stack and do a conditional jump
	builder.SetInsertPoint(conditionBB);
	Value *index = builder.CreateLoad(stackIndex);
	builder.CreateCondBr(builder.CreateICmpSLT(index, count), loopBB, endBB);
	
	// In the loop we grab the val from the stack, add to it and store result back on the stack
	builder.SetInsertPoint(loopBB);
	Value *val = builder.CreateLoad(stackVal);
	Value *newVal = builder.CreateAdd(val, builder.CreateLoad(builder.CreateGEP(values, index)));
	builder.CreateStore(newVal, stackVal);
	builder.CreateStore(builder.CreateAdd(index, constant0), stackIndex);
	builder.CreateBr(conditionBB);
	
	builder.SetInsertPoint(endBB);
	builder.CreateRet(builder.CreateLoad(stackVal));
}
My SSA* family of classes does exactly the above using constructors and operator overloading. I'll let you decide which method is best for the decorate stuff, but just for comparison, the last function looks like this with the SSA classes:

Code: Select all

void CreateForLoop(llvm::Context *context, llvm::Module *module)
{
	using namespace llvm;
	
	IRBuilder<> builder(*context);
	SSAScope ssa_scope(*context, module, &builder);
	
	SSAFunction function("sum");
	function.add_parameter(SSAInt::llvm_type());
	function.add_parameter(SSAIntPtr::llvm_type());
	function.set_return_type(SSAInt::llvm_type());
	function.create_public();
	
	SSAInt count = function.parameter(0);
	SSAIntPtr values = function.parameter(1);
	
	SSAStack<SSAInt> stackIndex, stackVal;
	stackIndex.store(0);
	stackVal.store(0);
	
	SSAForBlock branch;
	SSAInt index = stackIndex.load();
	branch.loop_block(index < count);
	SSAInt val = stackVal.load();
	SSAInt newVal = val + values[index].load();
	stackVal.store(newVal);
	stackIndex.store(index + 1);
	branch.end_block();
	
	builder.CreateRet(stackVal.load().v);
}
It is just syntactic sugar around the LLVM API. Because of the way it works it is important to be aware of what kind of LLVM instructions it generates as you type those lines.

Wow, that was a long post! I hope I didn't discourage you too much with it. :)

dpJudas
Developer
Developer
Posts: 798
Joined: Sat Jul 23, 2016 7:53

Re: The llvmcompiler branch

Post by dpJudas » Fri Sep 30, 2016 22:05

Eruanna wrote:Requiring the entire LLVM project is a bit much for a little port like ZDoom (or QZDoom). But I wouldn't mind it if bits and pieces of it could be compiled as dependencies that don't take (now going on 3) hours to compile.
I'm not sure why it is taking your system that long to build it. Think it took something like 20 minutes on my computer. Are you building it on some VM? That said, you are right that LLVM is a very big beast. However, it is also fairly modular where not everything has to be linked into the final executable. If building LLVM is considered too much of a hassle there is always the option of including precompiled binaries of the modules used.

The main reason I didn't just merge this into master was exactly because I wanted to know how it went for you to get this compiling. Not so well it seems. :(
Secondly, executables are not normally provided for Linux.
Actually, for Linux, I'm fairly sure you can just apt-get install a llvm-dev style package and CMake would find it automatically - already precompiled by the distro. Not that I actually tested this theory. :)
If the LLVM license allows it, I would not mind the specific libraries that are needed to be imported to the project as long as they do not create too much bloat, and as long as someone can import the repository and have a working executable from scratch in under 40 minutes (not counting dependency download times).
I'm all for that. The only catch is that MSVC loves creating bloated .lib files that can be compressed to 1/5th its original size. It would probably increase the download size of the source by 20 megabytes if we zip them - maybe less. I need to figure out exactly which of the 110 libraries LLVM has that we are using.
I feel right now like the cost (time) of this is a bit overkill to the benefit gained.
The main benefit of this is easier maintainability of the drawer code. If it really ends up being way too high a price to pay, the codegen part could be moved outside the main codebase as an utility. I'd rather not use that approach unless there's little other choice, though.

User avatar
Graf Zahl
GZDoom Developer
GZDoom Developer
Posts: 7148
Joined: Wed Jul 20, 2005 9:48
Location: Germany
Contact:

Re: The llvmcompiler branch

Post by Graf Zahl » Fri Sep 30, 2016 22:09

Eruanna wrote: I feel right now like the cost (time) of this is a bit overkill to the benefit gained.
I have to agree. The LLVM distribution is a monster, we really can't ask anyone interested in compiling ZDoom et.al. to bother with that, at least not if it's such a chore.
The concept is definitely interesting and I don't want to give up on it, but I believe we have to work with something more stripped down, I cannot believe that everything in this huge package is really needed.

So for toying around, it's certainly fine, but this definitely will need some organizational work.

Locked

Return to “QZDoom”