0x332 Compiler
1. Frontend
1.1. Lexical Analysis
Most of lexical grammars can be handled by regular languages. There are exceptions though, for example, Python's lexical requires indents counts of previous line, which requires non-regular context
1.2. Syntax Analysis
Syntactic analysis is the process of analyzing a string of symbols (or tokens), either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.
1.2.1. Top-down parsing
recursive descent parsing is a top-down parsing which is constructed from top and from left to right
1.2.2. Bottom-up parsing
Shift-Reduce
Operator-precedence parser (Shunting-yard)
1.3. Semantic Analysis
types, scopes, variable binding...
2. LLVM
Command
# compile into llvm IR text format
clang -S -emit-llvm hello.c -o hello.ll
2.1. MLIR
2.2. LLVM IR
Check the Language Reference and this Youtube
The following code snippet is from this blog, illustrating how LLVM IR looks like
unsigned add1(unsigned a, unsigned b) {
return a+b;
}
// Perhaps not the most efficient way to add two numbers.
unsigned add2(unsigned a, unsigned b) {
if (a == 0) return b;
return add2(a-1, b+1);
}
Those C codes will be translated to the following IRs
define i32 @add1(i32 %a, i32 %b) {
entry:
%tmp1 = add i32 %a, %b
ret i32 %tmp1
}
define i32 @add2(i32 %a, i32 %b) {
entry:
%tmp1 = icmp eq i32 %a, 0
br i1 %tmp1, label %done, label %recurse
recurse:
%tmp2 = sub i32 %a, 1
%tmp3 = add i32 %b, 1
%tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
ret i32 %tmp4
done:
ret i32 %b
}
2.2.1. Structures
Global variables are pointers whose names get prefixed with "@" initialized with global or constant (constant pointers)
Basic Block is a list of non-terminator instructions ending with a terminator instruction
2.2.2. Type Systems
2.2.3. Instructions
LLVM Instruction
Terminator instructions: every basic block in a program should end with a terminator instruction.
- ret: return
- br: Branching transfer to another basic blocks
- switch
Binary Operations
- add
- fadd
- mul
- fmul
Memory Operations
- alloca: stack allocation of a type and get automatically released
- load
- store
3. Optimization (Passes)
Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.
3.1. Loop optimization
3.2. Dataflow optimization
Dataflow is represetned with Control Flow Graph (also abbreviated as CFG), it consists of the basic block, which is a block of code that can can only branch to the beginning of other blocks at the end of this block. This help analysis of data flow.
Some simple optimizations are:
- constant folding and propagation: replacing expressions consisting with constants with their final value (e.g. 3+5 -> 8)
- dead code elimination: remove code that does not affect results
4. Backend
See this turorial for developing a llvm backend
4.1. Code Generation
JIT
Watch this video for LLVM JIT API (MCJIT vs ORC JIT)
Both are using the same underlying architecture:
- static compiler
- JIT linker (RuntimeDyld)
MCJIT implements ExecutionEngine API which is restricted in many scenarios, ORC instead is better by
- offer a superset of feature
- has more flexible API
- supports remoteness and laziness
5. Security
There are several compilers features to mitigate security risks
Stack smashing protector To mitigate risk of stack buffer overflow. (only mitigate, can be exploited by overwriting canary by the correct value, maybe overwriting the canary's global reference ?) insert canary variable into higher stack address before running risk function. Check whether the canary (expected value is on heap) has been modified after running risk.
/* Note how buffer overruns are undefined behavior and the compilers tend to
optimize these checks away if you wrote them yourself, this only works
robustly because the compiler did it itself. */
extern uintptr_t __stack_chk_guard;
noreturn void __stack_chk_fail(void);
void foo(const char* str)
{
uintptr_t canary = __stack_chk_guard; // automatically inserted by compiler
char buffer[16];
strcpy(buffer, str);
if ( (canary = canary ^ __stack_chk_guard) != 0 ) // automatically inserted by compiler
__stack_chk_fail();
}
6. JIT
check this tutorial to get the high-level concept of how it works.
The following snippe is to implement an identity function from the previous tutorial, it writes asm corresponding to the identity function into some memory with some flag and then execute this memory.
// jitproto.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
typedef long(*fn)(long);
fn compile_identity(void) {
// Allocate some memory and set its permissions correctly. In particular, we
// need PROT_EXEC (which isn't normally enabled for data memory, e.g. from
// malloc()), which tells the processor it's ok to execute it as machine
// code.
char *memory = mmap(NULL, // address
4096, // size
PROT_READ | PROT_WRITE | PROT_EXEC,
MAP_PRIVATE | MAP_ANONYMOUS,
-1, // fd (not used here)
0); // offset (not used here)
if (memory == MAP_FAILED) {
perror("failed to allocate memory");
exit(1);
}
int i = 0;
// mov %rdi, %rax
memory[i++] = 0x48; // REX.W prefix
memory[i++] = 0x8b; // MOV opcode, register/register
memory[i++] = 0xc7; // MOD/RM byte for %rdi -> %rax
// ret
memory[i++] = 0xc3; // RET opcode
return (fn) memory;
}
int main() {
fn f = compile_identity();
int i;
for (i = 0; i < 10; ++i)
printf("f(%d) = %ld\n", i, (*f)(i));
munmap(f, 4096);
return 0;
}
7. IDE
There is a concept called Language Server Protocol, which splits the language-related parsing features into a service provided from a remote server, the client is usually an editor which interacts with server using this json-based protocol.