1======================================
2Kaleidoscope: Adding Debug Information
3======================================
4
5.. contents::
6   :local:
7
8Chapter 9 Introduction
9======================
10
11Welcome to Chapter 9 of the "`Implementing a language with
12LLVM <index.html>`_" tutorial. In chapters 1 through 8, we've built a
13decent little programming language with functions and variables.
14What happens if something goes wrong though, how do you debug your
15program?
16
17Source level debugging uses formatted data that helps a debugger
18translate from binary and the state of the machine back to the
19source that the programmer wrote. In LLVM we generally use a format
20called `DWARF <http://dwarfstd.org>`_. DWARF is a compact encoding
21that represents types, source locations, and variable locations.
22
23The short summary of this chapter is that we'll go through the
24various things you have to add to a programming language to
25support debug info, and how you translate that into DWARF.
26
27Caveat: For now we can't debug via the JIT, so we'll need to compile
28our program down to something small and standalone. As part of this
29we'll make a few modifications to the running of the language and
30how programs are compiled. This means that we'll have a source file
31with a simple program written in Kaleidoscope rather than the
32interactive JIT. It does involve a limitation that we can only
33have one "top level" command at a time to reduce the number of
34changes necessary.
35
36Here's the sample program we'll be compiling:
37
38.. code-block:: python
39
40   def fib(x)
41     if x < 3 then
42       1
43     else
44       fib(x-1)+fib(x-2);
45
46   fib(10)
47
48
49Why is this a hard problem?
50===========================
51
52Debug information is a hard problem for a few different reasons - mostly
53centered around optimized code. First, optimization makes keeping source
54locations more difficult. In LLVM IR we keep the original source location
55for each IR level instruction on the instruction. Optimization passes
56should keep the source locations for newly created instructions, but merged
57instructions only get to keep a single location - this can cause jumping
58around when stepping through optimized programs. Secondly, optimization
59can move variables in ways that are either optimized out, shared in memory
60with other variables, or difficult to track. For the purposes of this
61tutorial we're going to avoid optimization (as you'll see with one of the
62next sets of patches).
63
64Ahead-of-Time Compilation Mode
65==============================
66
67To highlight only the aspects of adding debug information to a source
68language without needing to worry about the complexities of JIT debugging
69we're going to make a few changes to Kaleidoscope to support compiling
70the IR emitted by the front end into a simple standalone program that
71you can execute, debug, and see results.
72
73First we make our anonymous function that contains our top level
74statement be our "main":
75
76.. code-block:: udiff
77
78  -    auto Proto = std::make_unique<PrototypeAST>("", std::vector<std::string>());
79  +    auto Proto = std::make_unique<PrototypeAST>("main", std::vector<std::string>());
80
81just with the simple change of giving it a name.
82
83Then we're going to remove the command line code wherever it exists:
84
85.. code-block:: udiff
86
87  @@ -1129,7 +1129,6 @@ static void HandleTopLevelExpression() {
88   /// top ::= definition | external | expression | ';'
89   static void MainLoop() {
90     while (1) {
91  -    fprintf(stderr, "ready> ");
92       switch (CurTok) {
93       case tok_eof:
94         return;
95  @@ -1184,7 +1183,6 @@ int main() {
96     BinopPrecedence['*'] = 40; // highest.
97
98     // Prime the first token.
99  -  fprintf(stderr, "ready> ");
100     getNextToken();
101
102Lastly we're going to disable all of the optimization passes and the JIT so
103that the only thing that happens after we're done parsing and generating
104code is that the LLVM IR goes to standard error:
105
106.. code-block:: udiff
107
108  @@ -1108,17 +1108,8 @@ static void HandleExtern() {
109   static void HandleTopLevelExpression() {
110     // Evaluate a top-level expression into an anonymous function.
111     if (auto FnAST = ParseTopLevelExpr()) {
112  -    if (auto *FnIR = FnAST->codegen()) {
113  -      // We're just doing this to make sure it executes.
114  -      TheExecutionEngine->finalizeObject();
115  -      // JIT the function, returning a function pointer.
116  -      void *FPtr = TheExecutionEngine->getPointerToFunction(FnIR);
117  -
118  -      // Cast it to the right type (takes no arguments, returns a double) so we
119  -      // can call it as a native function.
120  -      double (*FP)() = (double (*)())(intptr_t)FPtr;
121  -      // Ignore the return value for this.
122  -      (void)FP;
123  +    if (!F->codegen()) {
124  +      fprintf(stderr, "Error generating code for top level expr");
125       }
126     } else {
127       // Skip token for error recovery.
128  @@ -1439,11 +1459,11 @@ int main() {
129     // target lays out data structures.
130     TheModule->setDataLayout(TheExecutionEngine->getDataLayout());
131     OurFPM.add(new DataLayoutPass());
132  +#if 0
133     OurFPM.add(createBasicAliasAnalysisPass());
134     // Promote allocas to registers.
135     OurFPM.add(createPromoteMemoryToRegisterPass());
136  @@ -1218,7 +1210,7 @@ int main() {
137     OurFPM.add(createGVNPass());
138     // Simplify the control flow graph (deleting unreachable blocks, etc).
139     OurFPM.add(createCFGSimplificationPass());
140  -
141  +  #endif
142     OurFPM.doInitialization();
143
144     // Set the global so the code gen can use this.
145
146This relatively small set of changes get us to the point that we can compile
147our piece of Kaleidoscope language down to an executable program via this
148command line:
149
150.. code-block:: bash
151
152  Kaleidoscope-Ch9 < fib.ks | & clang -x ir -
153
154which gives an a.out/a.exe in the current working directory.
155
156Compile Unit
157============
158
159The top level container for a section of code in DWARF is a compile unit.
160This contains the type and function data for an individual translation unit
161(read: one file of source code). So the first thing we need to do is
162construct one for our fib.ks file.
163
164DWARF Emission Setup
165====================
166
167Similar to the ``IRBuilder`` class we have a
168`DIBuilder <https://llvm.org/doxygen/classllvm_1_1DIBuilder.html>`_ class
169that helps in constructing debug metadata for an LLVM IR file. It
170corresponds 1:1 similarly to ``IRBuilder`` and LLVM IR, but with nicer names.
171Using it does require that you be more familiar with DWARF terminology than
172you needed to be with ``IRBuilder`` and ``Instruction`` names, but if you
173read through the general documentation on the
174`Metadata Format <https://llvm.org/docs/SourceLevelDebugging.html>`_ it
175should be a little more clear. We'll be using this class to construct all
176of our IR level descriptions. Construction for it takes a module so we
177need to construct it shortly after we construct our module. We've left it
178as a global static variable to make it a bit easier to use.
179
180Next we're going to create a small container to cache some of our frequent
181data. The first will be our compile unit, but we'll also write a bit of
182code for our one type since we won't have to worry about multiple typed
183expressions:
184
185.. code-block:: c++
186
187  static DIBuilder *DBuilder;
188
189  struct DebugInfo {
190    DICompileUnit *TheCU;
191    DIType *DblTy;
192
193    DIType *getDoubleTy();
194  } KSDbgInfo;
195
196  DIType *DebugInfo::getDoubleTy() {
197    if (DblTy)
198      return DblTy;
199
200    DblTy = DBuilder->createBasicType("double", 64, dwarf::DW_ATE_float);
201    return DblTy;
202  }
203
204And then later on in ``main`` when we're constructing our module:
205
206.. code-block:: c++
207
208  DBuilder = new DIBuilder(*TheModule);
209
210  KSDbgInfo.TheCU = DBuilder->createCompileUnit(
211      dwarf::DW_LANG_C, DBuilder->createFile("fib.ks", "."),
212      "Kaleidoscope Compiler", 0, "", 0);
213
214There are a couple of things to note here. First, while we're producing a
215compile unit for a language called Kaleidoscope we used the language
216constant for C. This is because a debugger wouldn't necessarily understand
217the calling conventions or default ABI for a language it doesn't recognize
218and we follow the C ABI in our LLVM code generation so it's the closest
219thing to accurate. This ensures we can actually call functions from the
220debugger and have them execute. Secondly, you'll see the "fib.ks" in the
221call to ``createCompileUnit``. This is a default hard coded value since
222we're using shell redirection to put our source into the Kaleidoscope
223compiler. In a usual front end you'd have an input file name and it would
224go there.
225
226One last thing as part of emitting debug information via DIBuilder is that
227we need to "finalize" the debug information. The reasons are part of the
228underlying API for DIBuilder, but make sure you do this near the end of
229main:
230
231.. code-block:: c++
232
233  DBuilder->finalize();
234
235before you dump out the module.
236
237Functions
238=========
239
240Now that we have our ``Compile Unit`` and our source locations, we can add
241function definitions to the debug info. So in ``PrototypeAST::codegen()`` we
242add a few lines of code to describe a context for our subprogram, in this
243case the "File", and the actual definition of the function itself.
244
245So the context:
246
247.. code-block:: c++
248
249  DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU.getFilename(),
250                                      KSDbgInfo.TheCU.getDirectory());
251
252giving us an DIFile and asking the ``Compile Unit`` we created above for the
253directory and filename where we are currently. Then, for now, we use some
254source locations of 0 (since our AST doesn't currently have source location
255information) and construct our function definition:
256
257.. code-block:: c++
258
259  DIScope *FContext = Unit;
260  unsigned LineNo = 0;
261  unsigned ScopeLine = 0;
262  DISubprogram *SP = DBuilder->createFunction(
263      FContext, P.getName(), StringRef(), Unit, LineNo,
264      CreateFunctionType(TheFunction->arg_size(), Unit),
265      false /* internal linkage */, true /* definition */, ScopeLine,
266      DINode::FlagPrototyped, false);
267  TheFunction->setSubprogram(SP);
268
269and we now have an DISubprogram that contains a reference to all of our
270metadata for the function.
271
272Source Locations
273================
274
275The most important thing for debug information is accurate source location -
276this makes it possible to map your source code back. We have a problem though,
277Kaleidoscope really doesn't have any source location information in the lexer
278or parser so we'll need to add it.
279
280.. code-block:: c++
281
282   struct SourceLocation {
283     int Line;
284     int Col;
285   };
286   static SourceLocation CurLoc;
287   static SourceLocation LexLoc = {1, 0};
288
289   static int advance() {
290     int LastChar = getchar();
291
292     if (LastChar == '\n' || LastChar == '\r') {
293       LexLoc.Line++;
294       LexLoc.Col = 0;
295     } else
296       LexLoc.Col++;
297     return LastChar;
298   }
299
300In this set of code we've added some functionality on how to keep track of the
301line and column of the "source file". As we lex every token we set our current
302current "lexical location" to the assorted line and column for the beginning
303of the token. We do this by overriding all of the previous calls to
304``getchar()`` with our new ``advance()`` that keeps track of the information
305and then we have added to all of our AST classes a source location:
306
307.. code-block:: c++
308
309   class ExprAST {
310     SourceLocation Loc;
311
312     public:
313       ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {}
314       virtual ~ExprAST() {}
315       virtual Value* codegen() = 0;
316       int getLine() const { return Loc.Line; }
317       int getCol() const { return Loc.Col; }
318       virtual raw_ostream &dump(raw_ostream &out, int ind) {
319         return out << ':' << getLine() << ':' << getCol() << '\n';
320       }
321
322that we pass down through when we create a new expression:
323
324.. code-block:: c++
325
326   LHS = std::make_unique<BinaryExprAST>(BinLoc, BinOp, std::move(LHS),
327                                          std::move(RHS));
328
329giving us locations for each of our expressions and variables.
330
331To make sure that every instruction gets proper source location information,
332we have to tell ``Builder`` whenever we're at a new source location.
333We use a small helper function for this:
334
335.. code-block:: c++
336
337  void DebugInfo::emitLocation(ExprAST *AST) {
338    DIScope *Scope;
339    if (LexicalBlocks.empty())
340      Scope = TheCU;
341    else
342      Scope = LexicalBlocks.back();
343    Builder.SetCurrentDebugLocation(
344        DILocation::get(Scope->getContext(), AST->getLine(), AST->getCol(), Scope));
345  }
346
347This both tells the main ``IRBuilder`` where we are, but also what scope
348we're in. The scope can either be on compile-unit level or be the nearest
349enclosing lexical block like the current function.
350To represent this we create a stack of scopes:
351
352.. code-block:: c++
353
354   std::vector<DIScope *> LexicalBlocks;
355
356and push the scope (function) to the top of the stack when we start
357generating the code for each function:
358
359.. code-block:: c++
360
361  KSDbgInfo.LexicalBlocks.push_back(SP);
362
363Also, we may not forget to pop the scope back off of the scope stack at the
364end of the code generation for the function:
365
366.. code-block:: c++
367
368  // Pop off the lexical block for the function since we added it
369  // unconditionally.
370  KSDbgInfo.LexicalBlocks.pop_back();
371
372Then we make sure to emit the location every time we start to generate code
373for a new AST object:
374
375.. code-block:: c++
376
377   KSDbgInfo.emitLocation(this);
378
379Variables
380=========
381
382Now that we have functions, we need to be able to print out the variables
383we have in scope. Let's get our function arguments set up so we can get
384decent backtraces and see how our functions are being called. It isn't
385a lot of code, and we generally handle it when we're creating the
386argument allocas in ``FunctionAST::codegen``.
387
388.. code-block:: c++
389
390    // Record the function arguments in the NamedValues map.
391    NamedValues.clear();
392    unsigned ArgIdx = 0;
393    for (auto &Arg : TheFunction->args()) {
394      // Create an alloca for this variable.
395      AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, Arg.getName());
396
397      // Create a debug descriptor for the variable.
398      DILocalVariable *D = DBuilder->createParameterVariable(
399          SP, Arg.getName(), ++ArgIdx, Unit, LineNo, KSDbgInfo.getDoubleTy(),
400          true);
401
402      DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(),
403                              DILocation::get(SP->getContext(), LineNo, 0, SP),
404                              Builder.GetInsertBlock());
405
406      // Store the initial value into the alloca.
407      Builder.CreateStore(&Arg, Alloca);
408
409      // Add arguments to variable symbol table.
410      NamedValues[Arg.getName()] = Alloca;
411    }
412
413
414Here we're first creating the variable, giving it the scope (``SP``),
415the name, source location, type, and since it's an argument, the argument
416index. Next, we create an ``lvm.dbg.declare`` call to indicate at the IR
417level that we've got a variable in an alloca (and it gives a starting
418location for the variable), and setting a source location for the
419beginning of the scope on the declare.
420
421One interesting thing to note at this point is that various debuggers have
422assumptions based on how code and debug information was generated for them
423in the past. In this case we need to do a little bit of a hack to avoid
424generating line information for the function prologue so that the debugger
425knows to skip over those instructions when setting a breakpoint. So in
426``FunctionAST::CodeGen`` we add some more lines:
427
428.. code-block:: c++
429
430  // Unset the location for the prologue emission (leading instructions with no
431  // location in a function are considered part of the prologue and the debugger
432  // will run past them when breaking on a function)
433  KSDbgInfo.emitLocation(nullptr);
434
435and then emit a new location when we actually start generating code for the
436body of the function:
437
438.. code-block:: c++
439
440  KSDbgInfo.emitLocation(Body.get());
441
442With this we have enough debug information to set breakpoints in functions,
443print out argument variables, and call functions. Not too bad for just a
444few simple lines of code!
445
446Full Code Listing
447=================
448
449Here is the complete code listing for our running example, enhanced with
450debug information. To build this example, use:
451
452.. code-block:: bash
453
454    # Compile
455    clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orcjit native` -O3 -o toy
456    # Run
457    ./toy
458
459Here is the code:
460
461.. literalinclude:: ../../../examples/Kaleidoscope/Chapter9/toy.cpp
462   :language: c++
463
464`Next: Conclusion and other useful LLVM tidbits <LangImpl10.html>`_
465
466