Code Generation for Data Processing
Contents
Code generation is a key technique for efficient program execution and data processing. This lecture will cover the following topics from a practical perspective with accompanying hands-on exercises:
- Execution models of programs (interpretation, bytecode, machine code generation, etc.)
- Program representations (source code, intermediate representations (IRs), different forms of bytecode)
- Classical techniques of code generation
- SSA and optimization techniques, exemplary described on LLVM-IR
- Machine code generation: instruction selection and register allocation
- Execution of programs in virtual machines (e.g., WebAssembly, BPF, JavaScript)
- Sandboxing and optimizations for JIT compilation
- Execution of database queries (e.g., SQL, data frame API)
- Execution models and code representations
- Execution of machine code/binary translation (e.g., RISC-V)
- Specifics when translating machine code
Organization
- Lecture with integrated exercises: Thu 10–14 (c.t., with break) in 02.11.018
- Exercises will include hands-on programming tasks
- (Basic) C++ knowledge is required
- Language: English
- Module: CIT3230001, 6 ECTS, Bachelor/Master elective
- Area "Databases and Information Systems" for Informatics, Wirtschaftsinformatik/Information Systems, Informatics: Games Engineering, Biomedical Engineering
- B1.2 "Advanced Topics in Data Engineering" for Data Engineering and Analystics
- Written exam (90 minutes), might change to oral on low registration count. Exam from winter 2022/23: [exam2223.pdf]. No retake.
- Zulip stream for this lecture; private contact via e-mail
- Note: This might be the last time I'll offer this course at TUM.
Prerequisites
The course is aimed at bachelor/master students who have taken the following (or similar) courses:
- IN0004 Introduction to Computer Architecture
- IN0008 Fundamentals of Databases
Material
Material and exercises will be regularly provided throughout the semester. [lec.pdf] [prs.pdf]
Script (includes content of slides and additional information and comments): [book.pdf]
| Date | Lecture Topic | Homework |
|---|---|---|
| 16.10. | Overview, Motivation, Interpretation Techniques [lec01.pdf] | [hw1.txt] [hw1-sol.c] |
| 23.10. | Compiler Front-end [lec02.pdf] | [hw2.txt] [hw2-sol.cc] |
| 30.10. | Intermediate Representations, CFG, SSA [lec03.pdf] [prs03.pdf] | |
| 06.11. | LLVM-IR [lec04.pdf] [ex04.txt] | [hw3.txt] [hw3-sol.cc] |
| 13.11. | Analyses and Transformations [lec05.pdf] [prs05.pdf] | |
| 20.11. | Optimizations in LLVM [lec06.pdf] [ex06.txt] | [hw4.txt] [hw4-sol.cc] |
| 27.11. | Instruction Selection [lec08.pdf] [prs08.pdf] | [hw5.txt] [hw5-new.txt] [hw5-sol.cc] |
| 04.12. | (no lecture/exercise, Dies Academicus) | |
| 11.12. | SSA Destruction and Liveness Analysis [lec09.pdf] [prs09.pdf] | [hw6.txt] [hw6-sol.cc] |
| 18.12. | Register Allocation [lec10.pdf] | [hw7.txt] [hw7-sol.cc] |
| 08.01. | Object Files, Linker, Loader [lec11.pdf] | |
| 15.01. | Unwinding and Debuginfo [lec12.pdf] [ex12.txt] | [hw8.txt] |
| 22.01. | Vectorization [lec07.pdf] [ex07.txt] | |
| 29.01. | JIT Compilation and Sandboxing [lec13.pdf] [ex13.txt] | |
| 05.02. | (no lecture/exercise, lecturer absent) |
Homework
The successful completion of n-2 homeworks is required for a 0.3 grade bonus (applied to grades 1.3–4.0). Submission instructions and deadlines are noted in the homework assignments. Please carefully observe the following guidelines:
- Include answers to theory questions as comments at the top of the source file.
- Make sure your submission passes as many tests as possible from the test script (most homework assignments are Markdown/Bash polyglots that compile and test your solution when executed).
- The preferred language is for submissions is C++. Other languages are permitted in principle (contact the lecturer first, however), but interacting with LLVM in later homeworks in inpracticable in other languages.
- No external dependencies unless explicitly permitted, build systems other than Makefile, etc.
- Write your solution in a single C++ file if at all possible.
- There's often no point in using multiple files. Having all content in a single file makes it easier to grade. The homeworks don't require a large amount of code (<10kLOC in total).
- If you really need more than just a single C++ file, combine all files s.t. this command sequence works:
split-file submission.txt somedir; cd somedir; bash hwX.txt split-fileis a LLVM utility tool and is typically included in LLVM distributions (e.g., the llvm or llvm-tools package of common Linux distributions).- If you write your own Makefile, respect the flags specified in the environment variables. Never hard-code specific paths to
llvm-config.