docs/SourceLevelDebugging.rst

   1 ================================
   2 Source Level Debugging with LLVM
   3 ================================
   4
   5 .. contents::
   6    :local:
   7
   8 Introduction
   9 ============
  10
  11 This document is the central repository for all information pertaining to debug
  12 information in LLVM.  It describes the :ref:`actual format that the LLVM debug
  13 information takes <format>`, which is useful for those interested in creating
  14 front-ends or dealing directly with the information.  Further, this document
  15 provides specific examples of what debug information for C/C++ looks like.
  16
  17 Philosophy behind LLVM debugging information
  18 --------------------------------------------
  19
  20 The idea of the LLVM debugging information is to capture how the important
  21 pieces of the source-language's Abstract Syntax Tree map onto LLVM code.
  22 Several design aspects have shaped the solution that appears here.  The
  23 important ones are:
  24
  25 * Debugging information should have very little impact on the rest of the
  26   compiler.  No transformations, analyses, or code generators should need to
  27   be modified because of debugging information.
  28
  29 * LLVM optimizations should interact in :ref:`well-defined and easily described
  30   ways <intro_debugopt>` with the debugging information.
  31
  32 * Because LLVM is designed to support arbitrary programming languages,
  33   LLVM-to-LLVM tools should not need to know anything about the semantics of
  34   the source-level-language.
  35
  36 * Source-level languages are often **widely** different from one another.
  37   LLVM should not put any restrictions of the flavor of the source-language,
  38   and the debugging information should work with any language.
  39
  40 * With code generator support, it should be possible to use an LLVM compiler
  41   to compile a program to native machine code and standard debugging
  42   formats.  This allows compatibility with traditional machine-code level
  43   debuggers, like GDB or DBX.
  44
  45 The approach used by the LLVM implementation is to use a small set of
  46 :ref:`intrinsic functions <format_common_intrinsics>` to define a mapping
  47 between LLVM program objects and the source-level objects.  The description of
  48 the source-level program is maintained in LLVM metadata in an
  49 :ref:`implementation-defined format <ccxx_frontend>` (the C/C++ front-end
  50 currently uses working draft 7 of the `DWARF 3 standard
  51 <http://www.eagercon.com/dwarf/dwarf3std.htm>`_).
  52
  53 When a program is being debugged, a debugger interacts with the user and turns
  54 the stored debug information into source-language specific information.  As
  55 such, a debugger must be aware of the source-language, and is thus tied to a
  56 specific language or family of languages.
  57
  58 Debug information consumers
  59 ---------------------------
  60
  61 The role of debug information is to provide meta information normally stripped
  62 away during the compilation process.  This meta information provides an LLVM
  63 user a relationship between generated code and the original program source
  64 code.
  65
  66 Currently, debug information is consumed by DwarfDebug to produce dwarf
  67 information used by the gdb debugger.  Other targets could use the same
  68 information to produce stabs or other debug forms.
  69
  70 It would also be reasonable to use debug information to feed profiling tools
  71 for analysis of generated code, or, tools for reconstructing the original
  72 source from generated code.
  73
  74 TODO - expound a bit more.
  75
  76 .. _intro_debugopt:
  77
  78 Debugging optimized code
  79 ------------------------
  80
  81 An extremely high priority of LLVM debugging information is to make it interact
  82 well with optimizations and analysis.  In particular, the LLVM debug
  83 information provides the following guarantees:
  84
  85 * LLVM debug information **always provides information to accurately read
  86   the source-level state of the program**, regardless of which LLVM
  87   optimizations have been run, and without any modification to the
  88   optimizations themselves.  However, some optimizations may impact the
  89   ability to modify the current state of the program with a debugger, such
  90   as setting program variables, or calling functions that have been
  91   deleted.
  92
  93 * As desired, LLVM optimizations can be upgraded to be aware of the LLVM
  94   debugging information, allowing them to update the debugging information
  95   as they perform aggressive optimizations.  This means that, with effort,
  96   the LLVM optimizers could optimize debug code just as well as non-debug
  97   code.
  98
  99 * LLVM debug information does not prevent optimizations from
 100   happening (for example inlining, basic block reordering/merging/cleanup,
 101   tail duplication, etc).
 102
 103 * LLVM debug information is automatically optimized along with the rest of
 104   the program, using existing facilities.  For example, duplicate
 105   information is automatically merged by the linker, and unused information
 106   is automatically removed.
 107
 108 Basically, the debug information allows you to compile a program with
 109 "``-O0 -g``" and get full debug information, allowing you to arbitrarily modify
 110 the program as it executes from a debugger.  Compiling a program with
 111 "``-O3 -g``" gives you full debug information that is always available and
 112 accurate for reading (e.g., you get accurate stack traces despite tail call
 113 elimination and inlining), but you might lose the ability to modify the program
 114 and call functions where were optimized out of the program, or inlined away
 115 completely.
 116
 117 :ref:`LLVM test suite <test-suite-quickstart>` provides a framework to test
 118 optimizer's handling of debugging information.  It can be run like this:
 119
 120 .. code-block:: bash
 121
 122   % cd llvm/projects/test-suite/MultiSource/Benchmarks  # or some other level
 123   % make TEST=dbgopt
 124
 125 This will test impact of debugging information on optimization passes.  If
 126 debugging information influences optimization passes then it will be reported
 127 as a failure.  See :doc:`TestingGuide` for more information on LLVM test
 128 infrastructure and how to run various tests.
 129
 130 .. _format:
 131
 132 Debugging information format
 133 ============================
 134
 135 LLVM debugging information has been carefully designed to make it possible for
 136 the optimizer to optimize the program and debugging information without
 137 necessarily having to know anything about debugging information.  In
 138 particular, the use of metadata avoids duplicated debugging information from
 139 the beginning, and the global dead code elimination pass automatically deletes
 140 debugging information for a function if it decides to delete the function.
 141
 142 To do this, most of the debugging information (descriptors for types,
 143 variables, functions, source files, etc) is inserted by the language front-end
 144 in the form of LLVM metadata.
 145
 146 Debug information is designed to be agnostic about the target debugger and
 147 debugging information representation (e.g. DWARF/Stabs/etc).  It uses a generic
 148 pass to decode the information that represents variables, types, functions,
 149 namespaces, etc: this allows for arbitrary source-language semantics and
 150 type-systems to be used, as long as there is a module written for the target
 151 debugger to interpret the information.
 152
 153 To provide basic functionality, the LLVM debugger does have to make some
 154 assumptions about the source-level language being debugged, though it keeps
 155 these to a minimum.  The only common features that the LLVM debugger assumes
 156 exist are :ref:`source files <format_files>`, and :ref:`program objects
 157 <format_global_variables>`.  These abstract objects are used by a debugger to
 158 form stack traces, show information about local variables, etc.
 159
 160 This section of the documentation first describes the representation aspects
 161 common to any source-language.  :ref:`ccxx_frontend` describes the data layout
 162 conventions used by the C and C++ front-ends.
 163
 164 Debug information descriptors
 165 -----------------------------
 166
 167 In consideration of the complexity and volume of debug information, LLVM
 168 provides a specification for well formed debug descriptors.
 169
 170 Consumers of LLVM debug information expect the descriptors for program objects
 171 to start in a canonical format, but the descriptors can include additional
 172 information appended at the end that is source-language specific.  All debugging
 173 information objects start with a tag to indicate what type of object it is.
 174 The source-language is allowed to define its own objects, by using unreserved
 175 tag numbers.  We recommend using with tags in the range 0x1000 through 0x2000
 176 (there is a defined ``enum DW_TAG_user_base = 0x1000``.)
 177
 178 The fields of debug descriptors used internally by LLVM are restricted to only
 179 the simple data types ``i32``, ``i1``, ``float``, ``double``, ``mdstring`` and
 180 ``mdnode``.
 181
 182 .. code-block:: llvm
 183
 184   !1 = metadata !{
 185     i32,   ;; A tag
 186     ...
 187   }
 188
 189 Most of the string and integer fields in descriptors are packed into a single,
 190 null-separated ``mdstring``.  The first field of the header is always an
 191 ``i32`` containing the DWARF tag value identifying the content of the
 192 descriptor.
 193
 194 For clarity of definition in this document, these header fields are described
 195 below split inside an imaginary ``DIHeader`` construct.  This is invalid
 196 assembly syntax.  In valid IR, these fields are stringified and concatenated,
 197 separated by ``\00``.
 198
 199 The details of the various descriptors follow.
 200
 201 Compile unit descriptors
 202 ^^^^^^^^^^^^^^^^^^^^^^^^
 203
 204 .. code-block:: llvm
 205
 206   !0 = metadata !{
 207     DIHeader(
 208       i32,       ;; Tag = 17 (DW_TAG_compile_unit)
 209       i32,       ;; DWARF language identifier (ex. DW_LANG_C89)
 210       mdstring,  ;; Producer (ex. "4.0.1 LLVM (LLVM research group)")
 211       i1,        ;; True if this is optimized.
 212       mdstring,  ;; Flags
 213       i32,       ;; Runtime version
 214       mdstring,  ;; Split debug filename
 215       i32        ;; Debug info emission kind (1 = Full Debug Info, 2 = Line Tables Only)
 216     ),
 217     metadata,  ;; Source directory (including trailing slash) & file pair
 218     metadata,  ;; List of enums types
 219     metadata,  ;; List of retained types
 220     metadata,  ;; List of subprograms
 221     metadata,  ;; List of global variables
 222     metadata   ;; List of imported entities
 223   }
 224
 225 These descriptors contain a source language ID for the file (we use the DWARF
 226 3.0 ID numbers, such as ``DW_LANG_C89``, ``DW_LANG_C_plus_plus``,
 227 ``DW_LANG_Cobol74``, etc), a reference to a metadata node containing a pair of
 228 strings for the source file name and the working directory, as well as an
 229 identifier string for the compiler that produced it.
 230
 231 Compile unit descriptors provide the root context for objects declared in a
 232 specific compilation unit.  File descriptors are defined using this context.
 233 These descriptors are collected by a named metadata ``!llvm.dbg.cu``.  They
 234 keep track of subprograms, global variables, type information, and imported
 235 entities (declarations and namespaces).
 236
 237 .. _format_files:
 238
 239 File descriptors
 240 ^^^^^^^^^^^^^^^^
 241
 242 .. code-block:: llvm
 243
 244   !0 = metadata !{
 245     DIHeader(
 246       i32       ;; Tag = 41 (DW_TAG_file_type)
 247     ),
 248     metadata  ;; Source directory (including trailing slash) & file pair
 249   }
 250
 251 These descriptors contain information for a file.  Global variables and top
 252 level functions would be defined using this context.  File descriptors also
 253 provide context for source line correspondence.
 254
 255 Each input file is encoded as a separate file descriptor in LLVM debugging
 256 information output.
 257
 258 .. _format_global_variables:
 259
 260 Global variable descriptors
 261 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 262
 263 .. code-block:: llvm
 264
 265   !1 = metadata !{
 266     DIHeader(
 267       i32,      ;; Tag = 52 (DW_TAG_variable)
 268       mdstring, ;; Name
 269       mdstring, ;; Display name (fully qualified C++ name)
 270       mdstring, ;; MIPS linkage name (for C++)
 271       i32,      ;; Line number where defined
 272       i1,       ;; True if the global is local to compile unit (static)
 273       i1        ;; True if the global is defined in the compile unit (not extern)
 274     ),
 275     metadata, ;; Reference to context descriptor
 276     metadata, ;; Reference to file where defined
 277     metadata, ;; Reference to type descriptor
 278     {}*,      ;; Reference to the global variable
 279     metadata, ;; The static member declaration, if any
 280   }
 281
 282 These descriptors provide debug information about global variables.  They
 283 provide details such as name, type and where the variable is defined.  All
 284 global variables are collected inside the named metadata ``!llvm.dbg.cu``.
 285
 286 .. _format_subprograms:
 287
 288 Subprogram descriptors
 289 ^^^^^^^^^^^^^^^^^^^^^^
 290
 291 .. code-block:: llvm
 292
 293   !2 = metadata !{
 294     DIHeader(
 295       i32,      ;; Tag = 46 (DW_TAG_subprogram)
 296       mdstring, ;; Name
 297       mdstring, ;; Display name (fully qualified C++ name)
 298       mdstring, ;; MIPS linkage name (for C++)
 299       i32,      ;; Line number where defined
 300       i1,       ;; True if the global is local to compile unit (static)
 301       i1,       ;; True if the global is defined in the compile unit (not extern)
 302       i32,      ;; Virtuality, e.g. dwarf::DW_VIRTUALITY__virtual
 303       i32,      ;; Index into a virtual function
 304       i32,      ;; Flags - Artificial, Private, Protected, Explicit, Prototyped.
 305       i1,       ;; isOptimized
 306       i32       ;; Line number where the scope of the subprogram begins
 307     ),
 308     metadata, ;; Source directory (including trailing slash) & file pair
 309     metadata, ;; Reference to context descriptor
 310     metadata, ;; Reference to type descriptor
 311     metadata, ;; indicates which base type contains the vtable pointer for the
 312               ;; derived class
 313     {}*,      ;; Reference to the LLVM function
 314     metadata, ;; Lists function template parameters
 315     metadata, ;; Function declaration descriptor
 316     metadata  ;; List of function variables
 317   }
 318
 319 These descriptors provide debug information about functions, methods and
 320 subprograms.  They provide details such as name, return types and the source
 321 location where the subprogram is defined.
 322
 323 Block descriptors
 324 ^^^^^^^^^^^^^^^^^
 325
 326 .. code-block:: llvm
 327
 328   !3 = metadata !{
 329     DIHeader(
 330       i32,      ;; Tag = 11 (DW_TAG_lexical_block)
 331       i32,      ;; Line number
 332       i32,      ;; Column number
 333       i32       ;; Unique ID to identify blocks from a template function
 334     ),
 335     metadata, ;; Source directory (including trailing slash) & file pair
 336     metadata  ;; Reference to context descriptor
 337   }
 338
 339 This descriptor provides debug information about nested blocks within a
 340 subprogram.  The line number and column numbers are used to dinstinguish two
 341 lexical blocks at same depth.
 342
 343 .. code-block:: llvm
 344
 345   !3 = metadata !{
 346     DIHeader(
 347       i32,      ;; Tag = 11 (DW_TAG_lexical_block)
 348       i32       ;; DWARF path discriminator value
 349     ),
 350     metadata, ;; Source directory (including trailing slash) & file pair
 351     metadata  ;; Reference to the scope we're annotating with a file change
 352   }
 353
 354 This descriptor provides a wrapper around a lexical scope to handle file
 355 changes in the middle of a lexical block.
 356
 357 .. _format_basic_type:
 358
 359 Basic type descriptors
 360 ^^^^^^^^^^^^^^^^^^^^^^
 361
 362 .. code-block:: llvm
 363
 364   !4 = metadata !{
 365     DIHeader(
 366       i32,      ;; Tag = 36 (DW_TAG_base_type)
 367       mdstring, ;; Name (may be "" for anonymous types)
 368       i32,      ;; Line number where defined (may be 0)
 369       i64,      ;; Size in bits
 370       i64,      ;; Alignment in bits
 371       i64,      ;; Offset in bits
 372       i32,      ;; Flags
 373       i32       ;; DWARF type encoding
 374     ),
 375     metadata, ;; Source directory (including trailing slash) & file pair (may be null)
 376     metadata  ;; Reference to context
 377   }
 378
 379 These descriptors define primitive types used in the code.  Example ``int``,
 380 ``bool`` and ``float``.  The context provides the scope of the type, which is
 381 usually the top level.  Since basic types are not usually user defined the
 382 context and line number can be left as NULL and 0.  The size, alignment and
 383 offset are expressed in bits and can be 64 bit values.  The alignment is used
 384 to round the offset when embedded in a :ref:`composite type
 385 <format_composite_type>` (example to keep float doubles on 64 bit boundaries).
 386 The offset is the bit offset if embedded in a :ref:`composite type
 387 <format_composite_type>`.
 388
 389 The type encoding provides the details of the type.  The values are typically
 390 one of the following:
 391
 392 .. code-block:: llvm
 393
 394   DW_ATE_address       = 1
 395   DW_ATE_boolean       = 2
 396   DW_ATE_float         = 4
 397   DW_ATE_signed        = 5
 398   DW_ATE_signed_char   = 6
 399   DW_ATE_unsigned      = 7
 400   DW_ATE_unsigned_char = 8
 401
 402 .. _format_derived_type:
 403
 404 Derived type descriptors
 405 ^^^^^^^^^^^^^^^^^^^^^^^^
 406
 407 .. code-block:: llvm
 408
 409   !5 = metadata !{
 410     DIHeader(
 411       i32,      ;; Tag (see below)
 412       mdstring, ;; Name (may be "" for anonymous types)
 413       i32,      ;; Line number where defined (may be 0)
 414       i64,      ;; Size in bits
 415       i64,      ;; Alignment in bits
 416       i64,      ;; Offset in bits
 417       i32       ;; Flags to encode attributes, e.g. private
 418     ),
 419     metadata, ;; Source directory (including trailing slash) & file pair (may be null)
 420     metadata, ;; Reference to context
 421     metadata, ;; Reference to type derived from
 422     metadata  ;; (optional) Objective C property node
 423   }
 424
 425 These descriptors are used to define types derived from other types.  The value
 426 of the tag varies depending on the meaning.  The following are possible tag
 427 values:
 428
 429 .. code-block:: llvm
 430
 431   DW_TAG_formal_parameter   = 5
 432   DW_TAG_member             = 13
 433   DW_TAG_pointer_type       = 15
 434   DW_TAG_reference_type     = 16
 435   DW_TAG_typedef            = 22
 436   DW_TAG_ptr_to_member_type = 31
 437   DW_TAG_const_type         = 38
 438   DW_TAG_volatile_type      = 53
 439   DW_TAG_restrict_type      = 55
 440
 441 ``DW_TAG_member`` is used to define a member of a :ref:`composite type
 442 <format_composite_type>` or :ref:`subprogram <format_subprograms>`.  The type
 443 of the member is the :ref:`derived type <format_derived_type>`.
 444 ``DW_TAG_formal_parameter`` is used to define a member which is a formal
 445 argument of a subprogram.
 446
 447 ``DW_TAG_typedef`` is used to provide a name for the derived type.
 448
 449 ``DW_TAG_pointer_type``, ``DW_TAG_reference_type``, ``DW_TAG_const_type``,
 450 ``DW_TAG_volatile_type`` and ``DW_TAG_restrict_type`` are used to qualify the
 451 :ref:`derived type <format_derived_type>`.
 452
 453 :ref:`Derived type <format_derived_type>` location can be determined from the
 454 context and line number.  The size, alignment and offset are expressed in bits
 455 and can be 64 bit values.  The alignment is used to round the offset when
 456 embedded in a :ref:`composite type <format_composite_type>`  (example to keep
 457 float doubles on 64 bit boundaries.) The offset is the bit offset if embedded
 458 in a :ref:`composite type <format_composite_type>`.
 459
 460 Note that the ``void *`` type is expressed as a type derived from NULL.
 461
 462 .. _format_composite_type:
 463
 464 Composite type descriptors
 465 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 466
 467 .. code-block:: llvm
 468
 469   !6 = metadata !{
 470     DIHeader(
 471       i32,      ;; Tag (see below)
 472       mdstring, ;; Name (may be "" for anonymous types)
 473       i32,      ;; Line number where defined (may be 0)
 474       i64,      ;; Size in bits
 475       i64,      ;; Alignment in bits
 476       i64,      ;; Offset in bits
 477       i32,      ;; Flags
 478       i32       ;; Runtime languages
 479     ),
 480     metadata, ;; Source directory (including trailing slash) & file pair (may be null)
 481     metadata, ;; Reference to context
 482     metadata, ;; Reference to type derived from
 483     metadata, ;; Reference to array of member descriptors
 484     metadata, ;; Base type containing the vtable pointer for this type
 485     metadata, ;; Template parameters
 486     mdstring  ;; A unique identifier for type uniquing purpose (may be null)
 487   }
 488
 489 These descriptors are used to define types that are composed of 0 or more
 490 elements.  The value of the tag varies depending on the meaning.  The following
 491 are possible tag values:
 492
 493 .. code-block:: llvm
 494
 495   DW_TAG_array_type       = 1
 496   DW_TAG_enumeration_type = 4
 497   DW_TAG_structure_type   = 19
 498   DW_TAG_union_type       = 23
 499   DW_TAG_subroutine_type  = 21
 500   DW_TAG_inheritance      = 28
 501
 502 The vector flag indicates that an array type is a native packed vector.
 503
 504 The members of array types (tag = ``DW_TAG_array_type``) are
 505 :ref:`subrange descriptors <format_subrange>`, each
 506 representing the range of subscripts at that level of indexing.
 507
 508 The members of enumeration types (tag = ``DW_TAG_enumeration_type``) are
 509 :ref:`enumerator descriptors <format_enumerator>`, each representing the
 510 definition of enumeration value for the set.  All enumeration type descriptors
 511 are collected inside the named metadata ``!llvm.dbg.cu``.
 512
 513 The members of structure (tag = ``DW_TAG_structure_type``) or union (tag =
 514 ``DW_TAG_union_type``) types are any one of the :ref:`basic
 515 <format_basic_type>`, :ref:`derived <format_derived_type>` or :ref:`composite
 516 <format_composite_type>` type descriptors, each representing a field member of
 517 the structure or union.
 518
 519 For C++ classes (tag = ``DW_TAG_structure_type``), member descriptors provide
 520 information about base classes, static members and member functions.  If a
 521 member is a :ref:`derived type descriptor <format_derived_type>` and has a tag
 522 of ``DW_TAG_inheritance``, then the type represents a base class.  If the member
 523 of is a :ref:`global variable descriptor <format_global_variables>` then it
 524 represents a static member.  And, if the member is a :ref:`subprogram
 525 descriptor <format_subprograms>` then it represents a member function.  For
 526 static members and member functions, ``getName()`` returns the members link or
 527 the C++ mangled name.  ``getDisplayName()`` the simplied version of the name.
 528
 529 The first member of subroutine (tag = ``DW_TAG_subroutine_type``) type elements
 530 is the return type for the subroutine.  The remaining elements are the formal
 531 arguments to the subroutine.
 532
 533 :ref:`Composite type <format_composite_type>` location can be determined from
 534 the context and line number.  The size, alignment and offset are expressed in
 535 bits and can be 64 bit values.  The alignment is used to round the offset when
 536 embedded in a :ref:`composite type <format_composite_type>` (as an example, to
 537 keep float doubles on 64 bit boundaries).  The offset is the bit offset if
 538 embedded in a :ref:`composite type <format_composite_type>`.
 539
 540 .. _format_subrange:
 541
 542 Subrange descriptors
 543 ^^^^^^^^^^^^^^^^^^^^
 544
 545 .. code-block:: llvm
 546
 547   !42 = metadata !{
 548     DIHeader(
 549       i32,      ;; Tag = 33 (DW_TAG_subrange_type)
 550       i64,      ;; Low value
 551       i64       ;; High value
 552     )
 553   }
 554
 555 These descriptors are used to define ranges of array subscripts for an array
 556 :ref:`composite type <format_composite_type>`.  The low value defines the lower
 557 bounds typically zero for C/C++.  The high value is the upper bounds.  Values
 558 are 64 bit.  ``High - Low + 1`` is the size of the array.  If ``Low > High``
 559 the array bounds are not included in generated debugging information.
 560
 561 .. _format_enumerator:
 562
 563 Enumerator descriptors
 564 ^^^^^^^^^^^^^^^^^^^^^^
 565
 566 .. code-block:: llvm
 567
 568   !6 = metadata !{
 569     DIHeader(
 570       i32,      ;; Tag = 40 (DW_TAG_enumerator)
 571       mdstring, ;; Name
 572       i64       ;; Value
 573     )
 574   }
 575
 576 These descriptors are used to define members of an enumeration :ref:`composite
 577 type <format_composite_type>`, it associates the name to the value.
 578
 579 Local variables
 580 ^^^^^^^^^^^^^^^
 581
 582 .. code-block:: llvm
 583
 584   !7 = metadata !{
 585     DIHeader(
 586       i32,      ;; Tag (see below)
 587       mdstring, ;; Name
 588       i32,      ;; 24 bit - Line number where defined
 589                 ;; 8 bit - Argument number. 1 indicates 1st argument.
 590       i32       ;; flags
 591     ),
 592     metadata, ;; Context
 593     metadata, ;; Reference to file where defined
 594     metadata, ;; Reference to the type descriptor
 595     metadata  ;; (optional) Reference to inline location
 596   }
 597
 598 These descriptors are used to define variables local to a sub program.  The
 599 value of the tag depends on the usage of the variable:
 600
 601 .. code-block:: llvm
 602
 603   DW_TAG_auto_variable   = 256
 604   DW_TAG_arg_variable    = 257
 605
 606 An auto variable is any variable declared in the body of the function.  An
 607 argument variable is any variable that appears as a formal argument to the
 608 function.
 609
 610 The context is either the subprogram or block where the variable is defined.
 611 Name the source variable name.  Context and line indicate where the variable
 612 was defined.  Type descriptor defines the declared type of the variable.
 613
 614 Complex Expressions
 615 ^^^^^^^^^^^^^^^^^^^
 616 .. code-block:: llvm
 617
 618   !8 = metadata !{
 619     i32,      ;; DW_TAG_expression
 620     ...
 621   }
 622
 623 Complex expressions describe variable storage locations in terms of
 624 prefix-notated DWARF expressions. Currently the only supported
 625 operators are ``DW_OP_plus``, ``DW_OP_deref``, and ``DW_OP_piece``.
 626
 627 The ``DW_OP_piece`` operator is used for (typically larger aggregate)
 628 variables that are fragmented across several locations. It takes two
 629 i32 arguments, an offset and a size in bytes to describe which piece
 630 of the variable is at this location.
 631
 632
 633 .. _format_common_intrinsics:
 634
 635 Debugger intrinsic functions
 636 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 637
 638 LLVM uses several intrinsic functions (name prefixed with "``llvm.dbg``") to
 639 provide debug information at various points in generated code.
 640
 641 ``llvm.dbg.declare``
 642 ^^^^^^^^^^^^^^^^^^^^
 643
 644 .. code-block:: llvm
 645
 646   void %llvm.dbg.declare(metadata, metadata)
 647
 648 This intrinsic provides information about a local element (e.g., variable).
 649 The first argument is metadata holding the alloca for the variable.  The second
 650 argument is metadata containing a description of the variable.
 651
 652 ``llvm.dbg.value``
 653 ^^^^^^^^^^^^^^^^^^
 654
 655 .. code-block:: llvm
 656
 657   void %llvm.dbg.value(metadata, i64, metadata)
 658
 659 This intrinsic provides information when a user source variable is set to a new
 660 value.  The first argument is the new value (wrapped as metadata).  The second
 661 argument is the offset in the user source variable where the new value is
 662 written.  The third argument is metadata containing a description of the user
 663 source variable.
 664
 665 Object lifetimes and scoping
 666 ============================
 667
 668 In many languages, the local variables in functions can have their lifetimes or
 669 scopes limited to a subset of a function.  In the C family of languages, for
 670 example, variables are only live (readable and writable) within the source
 671 block that they are defined in.  In functional languages, values are only
 672 readable after they have been defined.  Though this is a very obvious concept,
 673 it is non-trivial to model in LLVM, because it has no notion of scoping in this
 674 sense, and does not want to be tied to a language's scoping rules.
 675
 676 In order to handle this, the LLVM debug format uses the metadata attached to
 677 llvm instructions to encode line number and scoping information.  Consider the
 678 following C fragment, for example:
 679
 680 .. code-block:: c
 681
 682   1.  void foo() {
 683   2.    int X = 21;
 684   3.    int Y = 22;
 685   4.    {
 686   5.      int Z = 23;
 687   6.      Z = X;
 688   7.    }
 689   8.    X = Y;
 690   9.  }
 691
 692 Compiled to LLVM, this function would be represented like this:
 693
 694 .. code-block:: llvm
 695
 696   define void @foo() #0 {
 697   entry:
 698    %X = alloca i32, align 4
 699     %Y = alloca i32, align 4
 700     %Z = alloca i32, align 4
 701     call void @llvm.dbg.declare(metadata !{i32* %X}, metadata !10), !dbg !12
 702       ; [debug line = 2:7] [debug variable = X]
 703     store i32 21, i32* %X, align 4, !dbg !12
 704     call void @llvm.dbg.declare(metadata !{i32* %Y}, metadata !13), !dbg !14
 705       ; [debug line = 3:7] [debug variable = Y]
 706     store i32 22, i32* %Y, align 4, !dbg !14
 707     call void @llvm.dbg.declare(metadata !{i32* %Z}, metadata !15), !dbg !17
 708       ; [debug line = 5:9] [debug variable = Z]
 709     store i32 23, i32* %Z, align 4, !dbg !17
 710     %0 = load i32* %X, align 4, !dbg !18
 711       [debug line = 6:5]
 712     store i32 %0, i32* %Z, align 4, !dbg !18
 713     %1 = load i32* %Y, align 4, !dbg !19
 714       [debug line = 8:3]
 715     store i32 %1, i32* %X, align 4, !dbg !19
 716     ret void, !dbg !20
 717   }
 718
 719   ; Function Attrs: nounwind readnone
 720   declare void @llvm.dbg.declare(metadata, metadata) #1
 721
 722   attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false"
 723     "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf"
 724     "no-infs-fp-math"="false" "no-nans-fp-math"="false"
 725     "stack-protector-buffer-size"="8" "unsafe-fp-math"="false"
 726     "use-soft-float"="false" }
 727   attributes #1 = { nounwind readnone }
 728
 729   !llvm.dbg.cu = !{!0}
 730   !llvm.module.flags = !{!8}
 731   !llvm.ident = !{!9}
 732
 733   !0 = metadata !{i32 786449, metadata !1, i32 12,
 734                   metadata !"clang version 3.4 (trunk 193128) (llvm/trunk 193139)",
 735                   i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3,
 736                   metadata !2, metadata !2, metadata !""} ; [ DW_TAG_compile_unit ] \
 737                     [/private/tmp/foo.c] \
 738                     [DW_LANG_C99]
 739   !1 = metadata !{metadata !"t.c", metadata !"/private/tmp"}
 740   !2 = metadata !{i32 0}
 741   !3 = metadata !{metadata !4}
 742   !4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"foo",
 743                   metadata !"foo", metadata !"", i32 1, metadata !6,
 744                   i1 false, i1 true, i32 0, i32 0, null, i32 0, i1 false,
 745                   void ()* @foo, null, null, metadata !2, i32 1}
 746                   ; [ DW_TAG_subprogram ] [line 1] [def] [foo]
 747   !5 = metadata !{i32 786473, metadata !1}  ; [ DW_TAG_file_type ] \
 748                     [/private/tmp/t.c]
 749   !6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0,
 750                   i64 0, i32 0, null, metadata !7, i32 0, null, null, null}
 751                   ; [ DW_TAG_subroutine_type ] \
 752                     [line 0, size 0, align 0, offset 0] [from ]
 753   !7 = metadata !{null}
 754   !8 = metadata !{i32 2, metadata !"Dwarf Version", i32 2}
 755   !9 = metadata !{metadata !"clang version 3.4 (trunk 193128) (llvm/trunk 193139)"}
 756   !10 = metadata !{i32 786688, metadata !4, metadata !"X", metadata !5, i32 2,
 757                    metadata !11, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [X] \
 758                      [line 2]
 759   !11 = metadata !{i32 786468, null, null, metadata !"int", i32 0, i64 32,
 760                    i64 32, i64 0, i32 0, i32 5} ; [ DW_TAG_base_type ] [int] \
 761                      [line 0, size 32, align 32, offset 0, enc DW_ATE_signed]
 762   !12 = metadata !{i32 2, i32 0, metadata !4, null}
 763   !13 = metadata !{i32 786688, metadata !4, metadata !"Y", metadata !5, i32 3,
 764                    metadata !11, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [Y] \
 765                      [line 3]
 766   !14 = metadata !{i32 3, i32 0, metadata !4, null}
 767   !15 = metadata !{i32 786688, metadata !16, metadata !"Z", metadata !5, i32 5,
 768                    metadata !11, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [Z] \
 769                      [line 5]
 770   !16 = metadata !{i32 786443, metadata !1, metadata !4, i32 4, i32 0, i32 0} \
 771                    ; [ DW_TAG_lexical_block ] [/private/tmp/t.c]
 772   !17 = metadata !{i32 5, i32 0, metadata !16, null}
 773   !18 = metadata !{i32 6, i32 0, metadata !16, null}
 774   !19 = metadata !{i32 8, i32 0, metadata !4, null} ; [ DW_TAG_imported_declaration ]
 775   !20 = metadata !{i32 9, i32 0, metadata !4, null}
 776
 777 This example illustrates a few important details about LLVM debugging
 778 information.  In particular, it shows how the ``llvm.dbg.declare`` intrinsic and
 779 location information, which are attached to an instruction, are applied
 780 together to allow a debugger to analyze the relationship between statements,
 781 variable definitions, and the code used to implement the function.
 782
 783 .. code-block:: llvm
 784
 785   call void @llvm.dbg.declare(metadata !{i32* %X}, metadata !10), !dbg !12
 786     ; [debug line = 2:7] [debug variable = X]
 787
 788 The first intrinsic ``%llvm.dbg.declare`` encodes debugging information for the
 789 variable ``X``.  The metadata ``!dbg !12`` attached to the intrinsic provides
 790 scope information for the variable ``X``.
 791
 792 .. code-block:: llvm
 793
 794   !12 = metadata !{i32 2, i32 0, metadata !4, null}
 795   !4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"foo",
 796                   metadata !"foo", metadata !"", i32 1, metadata !6,
 797                   i1 false, i1 true, i32 0, i32 0, null, i32 0, i1 false,
 798                   void ()* @foo, null, null, metadata !2, i32 1}
 799                     ; [ DW_TAG_subprogram ] [line 1] [def] [foo]
 800
 801 Here ``!12`` is metadata providing location information.  It has four fields:
 802 line number, column number, scope, and original scope.  The original scope
 803 represents inline location if this instruction is inlined inside a caller, and
 804 is null otherwise.  In this example, scope is encoded by ``!4``, a
 805 :ref:`subprogram descriptor <format_subprograms>`.  This way the location
 806 information attached to the intrinsics indicates that the variable ``X`` is
 807 declared at line number 2 at a function level scope in function ``foo``.
 808
 809 Now lets take another example.
 810
 811 .. code-block:: llvm
 812
 813   call void @llvm.dbg.declare(metadata !{i32* %Z}, metadata !15), !dbg !17
 814     ; [debug line = 5:9] [debug variable = Z]
 815
 816 The third intrinsic ``%llvm.dbg.declare`` encodes debugging information for
 817 variable ``Z``.  The metadata ``!dbg !17`` attached to the intrinsic provides
 818 scope information for the variable ``Z``.
 819
 820 .. code-block:: llvm
 821
 822   !16 = metadata !{i32 786443, metadata !1, metadata !4, i32 4, i32 0, i32 0} \
 823                    ; [ DW_TAG_lexical_block ] [/private/tmp/t.c]
 824   !17 = metadata !{i32 5, i32 0, metadata !16, null}
 825
 826 Here ``!15`` indicates that ``Z`` is declared at line number 5 and
 827 column number 0 inside of lexical scope ``!16``.  The lexical scope itself
 828 resides inside of subprogram ``!4`` described above.
 829
 830 The scope information attached with each instruction provides a straightforward
 831 way to find instructions covered by a scope.
 832
 833 .. _ccxx_frontend:
 834
 835 C/C++ front-end specific debug information
 836 ==========================================
 837
 838 The C and C++ front-ends represent information about the program in a format
 839 that is effectively identical to `DWARF 3.0
 840 <http://www.eagercon.com/dwarf/dwarf3std.htm>`_ in terms of information
 841 content.  This allows code generators to trivially support native debuggers by
 842 generating standard dwarf information, and contains enough information for
 843 non-dwarf targets to translate it as needed.
 844
 845 This section describes the forms used to represent C and C++ programs.  Other
 846 languages could pattern themselves after this (which itself is tuned to
 847 representing programs in the same way that DWARF 3 does), or they could choose
 848 to provide completely different forms if they don't fit into the DWARF model.
 849 As support for debugging information gets added to the various LLVM
 850 source-language front-ends, the information used should be documented here.
 851
 852 The following sections provide examples of various C/C++ constructs and the
 853 debug information that would best describe those constructs.
 854
 855 C/C++ source file information
 856 -----------------------------
 857
 858 Given the source files ``MySource.cpp`` and ``MyHeader.h`` located in the
 859 directory ``/Users/mine/sources``, the following code:
 860
 861 .. code-block:: c
 862
 863   #include "MyHeader.h"
 864
 865   int main(int argc, char *argv[]) {
 866     return 0;
 867   }
 868
 869 a C/C++ front-end would generate the following descriptors:
 870
 871 .. code-block:: llvm
 872
 873   ...
 874   ;;
 875   ;; Define the compile unit for the main source file "/Users/mine/sources/MySource.cpp".
 876   ;;
 877   !0 = metadata !{
 878     i32 786449,   ;; Tag
 879     metadata !1,  ;; File/directory name
 880     i32 4,        ;; Language Id
 881     metadata !"clang version 3.4 ",
 882     i1 false,     ;; Optimized compile unit
 883     metadata !"", ;; Compiler flags
 884     i32 0,        ;; Runtime version
 885     metadata !2,  ;; Enumeration types
 886     metadata !2,  ;; Retained types
 887     metadata !3,  ;; Subprograms
 888     metadata !2,  ;; Global variables
 889     metadata !2,  ;; Imported entities (declarations and namespaces)
 890     metadata !""  ;; Split debug filename
 891     1,            ;; Full debug info
 892   }
 893
 894   ;;
 895   ;; Define the file for the file "/Users/mine/sources/MySource.cpp".
 896   ;;
 897   !1 = metadata !{
 898     metadata !"MySource.cpp",
 899     metadata !"/Users/mine/sources"
 900   }
 901   !5 = metadata !{
 902     i32 786473, ;; Tag
 903     metadata !1
 904   }
 905
 906   ;;
 907   ;; Define the file for the file "/Users/mine/sources/Myheader.h"
 908   ;;
 909   !14 = metadata !{
 910     i32 786473, ;; Tag
 911     metadata !15
 912   }
 913   !15 = metadata !{
 914     metadata !"./MyHeader.h",
 915     metadata !"/Users/mine/sources",
 916   }
 917
 918   ...
 919
 920 ``llvm::Instruction`` provides easy access to metadata attached with an
 921 instruction.  One can extract line number information encoded in LLVM IR using
 922 ``Instruction::getMetadata()`` and ``DILocation::getLineNumber()``.
 923
 924 .. code-block:: c++
 925
 926   if (MDNode *N = I->getMetadata("dbg")) {  // Here I is an LLVM instruction
 927     DILocation Loc(N);                      // DILocation is in DebugInfo.h
 928     unsigned Line = Loc.getLineNumber();
 929     StringRef File = Loc.getFilename();
 930     StringRef Dir = Loc.getDirectory();
 931   }
 932
 933 C/C++ global variable information
 934 ---------------------------------
 935
 936 Given an integer global variable declared as follows:
 937
 938 .. code-block:: c
 939
 940   int MyGlobal = 100;
 941
 942 a C/C++ front-end would generate the following descriptors:
 943
 944 .. code-block:: llvm
 945
 946   ;;
 947   ;; Define the global itself.
 948   ;;
 949   %MyGlobal = global int 100
 950   ...
 951   ;;
 952   ;; List of debug info of globals
 953   ;;
 954   !llvm.dbg.cu = !{!0}
 955
 956   ;; Define the compile unit.
 957   !0 = metadata !{
 958     i32 786449,                       ;; Tag
 959     i32 0,                            ;; Context
 960     i32 4,                            ;; Language
 961     metadata !"foo.cpp",              ;; File
 962     metadata !"/Volumes/Data/tmp",    ;; Directory
 963     metadata !"clang version 3.1 ",   ;; Producer
 964     i1 true,                          ;; Deprecated field
 965     i1 false,                         ;; "isOptimized"?
 966     metadata !"",                     ;; Flags
 967     i32 0,                            ;; Runtime Version
 968     metadata !1,                      ;; Enum Types
 969     metadata !1,                      ;; Retained Types
 970     metadata !1,                      ;; Subprograms
 971     metadata !3,                      ;; Global Variables
 972     metadata !1,                      ;; Imported entities
 973     "",                               ;; Split debug filename
 974     1,                                ;; Full debug info
 975   } ; [ DW_TAG_compile_unit ]
 976
 977   ;; The Array of Global Variables
 978   !3 = metadata !{
 979     metadata !4
 980   }
 981
 982   ;;
 983   ;; Define the global variable itself.
 984   ;;
 985   !4 = metadata !{
 986     i32 786484,                        ;; Tag
 987     i32 0,                             ;; Unused
 988     null,                              ;; Unused
 989     metadata !"MyGlobal",              ;; Name
 990     metadata !"MyGlobal",              ;; Display Name
 991     metadata !"",                      ;; Linkage Name
 992     metadata !6,                       ;; File
 993     i32 1,                             ;; Line
 994     metadata !7,                       ;; Type
 995     i32 0,                             ;; IsLocalToUnit
 996     i32 1,                             ;; IsDefinition
 997     i32* @MyGlobal,                    ;; LLVM-IR Value
 998     null                               ;; Static member declaration
 999   } ; [ DW_TAG_variable ]
1000
1001   ;;
1002   ;; Define the file
1003   ;;
1004   !5 = metadata !{
1005     metadata !"foo.cpp",               ;; File
1006     metadata !"/Volumes/Data/tmp",     ;; Directory
1007   }
1008   !6 = metadata !{
1009     i32 786473,                        ;; Tag
1010     metadata !5                        ;; Unused
1011   } ; [ DW_TAG_file_type ]
1012
1013   ;;
1014   ;; Define the type
1015   ;;
1016   !7 = metadata !{
1017     i32 786468,                         ;; Tag
1018     null,                               ;; Unused
1019     null,                               ;; Unused
1020     metadata !"int",                    ;; Name
1021     i32 0,                              ;; Line
1022     i64 32,                             ;; Size in Bits
1023     i64 32,                             ;; Align in Bits
1024     i64 0,                              ;; Offset
1025     i32 0,                              ;; Flags
1026     i32 5                               ;; Encoding
1027   } ; [ DW_TAG_base_type ]
1028
1029 C/C++ function information
1030 --------------------------
1031
1032 Given a function declared as follows:
1033
1034 .. code-block:: c
1035
1036   int main(int argc, char *argv[]) {
1037     return 0;
1038   }
1039
1040 a C/C++ front-end would generate the following descriptors:
1041
1042 .. code-block:: llvm
1043
1044   ;;
1045   ;; Define the anchor for subprograms.
1046   ;;
1047   !6 = metadata !{
1048     i32 786484,        ;; Tag
1049     metadata !1,       ;; File
1050     metadata !1,       ;; Context
1051     metadata !"main",  ;; Name
1052     metadata !"main",  ;; Display name
1053     metadata !"main",  ;; Linkage name
1054     i32 1,             ;; Line number
1055     metadata !4,       ;; Type
1056     i1 false,          ;; Is local
1057     i1 true,           ;; Is definition
1058     i32 0,             ;; Virtuality attribute, e.g. pure virtual function
1059     i32 0,             ;; Index into virtual table for C++ methods
1060     i32 0,             ;; Type that holds virtual table.
1061     i32 0,             ;; Flags
1062     i1 false,          ;; True if this function is optimized
1063     Function *,        ;; Pointer to llvm::Function
1064     null,              ;; Function template parameters
1065     null,              ;; List of function variables (emitted when optimizing)
1066     1                  ;; Line number of the opening '{' of the function
1067   }
1068   ;;
1069   ;; Define the subprogram itself.
1070   ;;
1071   define i32 @main(i32 %argc, i8** %argv) {
1072   ...
1073   }
1074
1075 C/C++ basic types
1076 -----------------
1077
1078 The following are the basic type descriptors for C/C++ core types:
1079
1080 bool
1081 ^^^^
1082
1083 .. code-block:: llvm
1084
1085   !2 = metadata !{
1086     i32 786468,        ;; Tag
1087     null,              ;; File
1088     null,              ;; Context
1089     metadata !"bool",  ;; Name
1090     i32 0,             ;; Line number
1091     i64 8,             ;; Size in Bits
1092     i64 8,             ;; Align in Bits
1093     i64 0,             ;; Offset in Bits
1094     i32 0,             ;; Flags
1095     i32 2              ;; Encoding
1096   }
1097
1098 char
1099 ^^^^
1100
1101 .. code-block:: llvm
1102
1103   !2 = metadata !{
1104     i32 786468,        ;; Tag
1105     null,              ;; File
1106     null,              ;; Context
1107     metadata !"char",  ;; Name
1108     i32 0,             ;; Line number
1109     i64 8,             ;; Size in Bits
1110     i64 8,             ;; Align in Bits
1111     i64 0,             ;; Offset in Bits
1112     i32 0,             ;; Flags
1113     i32 6              ;; Encoding
1114   }
1115
1116 unsigned char
1117 ^^^^^^^^^^^^^
1118
1119 .. code-block:: llvm
1120
1121   !2 = metadata !{
1122     i32 786468,        ;; Tag
1123     null,              ;; File
1124     null,              ;; Context
1125     metadata !"unsigned char",
1126     i32 0,             ;; Line number
1127     i64 8,             ;; Size in Bits
1128     i64 8,             ;; Align in Bits
1129     i64 0,             ;; Offset in Bits
1130     i32 0,             ;; Flags
1131     i32 8              ;; Encoding
1132   }
1133
1134 short
1135 ^^^^^
1136
1137 .. code-block:: llvm
1138
1139   !2 = metadata !{
1140     i32 786468,        ;; Tag
1141     null,              ;; File
1142     null,              ;; Context
1143     metadata !"short int",
1144     i32 0,             ;; Line number
1145     i64 16,            ;; Size in Bits
1146     i64 16,            ;; Align in Bits
1147     i64 0,             ;; Offset in Bits
1148     i32 0,             ;; Flags
1149     i32 5              ;; Encoding
1150   }
1151
1152 unsigned short
1153 ^^^^^^^^^^^^^^
1154
1155 .. code-block:: llvm
1156
1157   !2 = metadata !{
1158     i32 786468,        ;; Tag
1159     null,              ;; File
1160     null,              ;; Context
1161     metadata !"short unsigned int",
1162     i32 0,             ;; Line number
1163     i64 16,            ;; Size in Bits
1164     i64 16,            ;; Align in Bits
1165     i64 0,             ;; Offset in Bits
1166     i32 0,             ;; Flags
1167     i32 7              ;; Encoding
1168   }
1169
1170 int
1171 ^^^
1172
1173 .. code-block:: llvm
1174
1175   !2 = metadata !{
1176     i32 786468,        ;; Tag
1177     null,              ;; File
1178     null,              ;; Context
1179     metadata !"int",   ;; Name
1180     i32 0,             ;; Line number
1181     i64 32,            ;; Size in Bits
1182     i64 32,            ;; Align in Bits
1183     i64 0,             ;; Offset in Bits
1184     i32 0,             ;; Flags
1185     i32 5              ;; Encoding
1186   }
1187
1188 unsigned int
1189 ^^^^^^^^^^^^
1190
1191 .. code-block:: llvm
1192
1193   !2 = metadata !{
1194     i32 786468,        ;; Tag
1195     null,              ;; File
1196     null,              ;; Context
1197     metadata !"unsigned int",
1198     i32 0,             ;; Line number
1199     i64 32,            ;; Size in Bits
1200     i64 32,            ;; Align in Bits
1201     i64 0,             ;; Offset in Bits
1202     i32 0,             ;; Flags
1203     i32 7              ;; Encoding
1204   }
1205
1206 long long
1207 ^^^^^^^^^
1208
1209 .. code-block:: llvm
1210
1211   !2 = metadata !{
1212     i32 786468,        ;; Tag
1213     null,              ;; File
1214     null,              ;; Context
1215     metadata !"long long int",
1216     i32 0,             ;; Line number
1217     i64 64,            ;; Size in Bits
1218     i64 64,            ;; Align in Bits
1219     i64 0,             ;; Offset in Bits
1220     i32 0,             ;; Flags
1221     i32 5              ;; Encoding
1222   }
1223
1224 unsigned long long
1225 ^^^^^^^^^^^^^^^^^^
1226
1227 .. code-block:: llvm
1228
1229   !2 = metadata !{
1230     i32 786468,        ;; Tag
1231     null,              ;; File
1232     null,              ;; Context
1233     metadata !"long long unsigned int",
1234     i32 0,             ;; Line number
1235     i64 64,            ;; Size in Bits
1236     i64 64,            ;; Align in Bits
1237     i64 0,             ;; Offset in Bits
1238     i32 0,             ;; Flags
1239     i32 7              ;; Encoding
1240   }
1241
1242 float
1243 ^^^^^
1244
1245 .. code-block:: llvm
1246
1247   !2 = metadata !{
1248     i32 786468,        ;; Tag
1249     null,              ;; File
1250     null,              ;; Context
1251     metadata !"float",
1252     i32 0,             ;; Line number
1253     i64 32,            ;; Size in Bits
1254     i64 32,            ;; Align in Bits
1255     i64 0,             ;; Offset in Bits
1256     i32 0,             ;; Flags
1257     i32 4              ;; Encoding
1258   }
1259
1260 double
1261 ^^^^^^
1262
1263 .. code-block:: llvm
1264
1265   !2 = metadata !{
1266     i32 786468,        ;; Tag
1267     null,              ;; File
1268     null,              ;; Context
1269     metadata !"double",;; Name
1270     i32 0,             ;; Line number
1271     i64 64,            ;; Size in Bits
1272     i64 64,            ;; Align in Bits
1273     i64 0,             ;; Offset in Bits
1274     i32 0,             ;; Flags
1275     i32 4              ;; Encoding
1276   }
1277
1278 C/C++ derived types
1279 -------------------
1280
1281 Given the following as an example of C/C++ derived type:
1282
1283 .. code-block:: c
1284
1285   typedef const int *IntPtr;
1286
1287 a C/C++ front-end would generate the following descriptors:
1288
1289 .. code-block:: llvm
1290
1291   ;;
1292   ;; Define the typedef "IntPtr".
1293   ;;
1294   !2 = metadata !{
1295     i32 786454,          ;; Tag
1296     metadata !3,         ;; File
1297     metadata !1,         ;; Context
1298     metadata !"IntPtr",  ;; Name
1299     i32 0,               ;; Line number
1300     i64 0,               ;; Size in bits
1301     i64 0,               ;; Align in bits
1302     i64 0,               ;; Offset in bits
1303     i32 0,               ;; Flags
1304     metadata !4          ;; Derived From type
1305   }
1306   ;;
1307   ;; Define the pointer type.
1308   ;;
1309   !4 = metadata !{
1310     i32 786447,          ;; Tag
1311     null,                ;; File
1312     null,                ;; Context
1313     metadata !"",        ;; Name
1314     i32 0,               ;; Line number
1315     i64 64,              ;; Size in bits
1316     i64 64,              ;; Align in bits
1317     i64 0,               ;; Offset in bits
1318     i32 0,               ;; Flags
1319     metadata !5          ;; Derived From type
1320   }
1321   ;;
1322   ;; Define the const type.
1323   ;;
1324   !5 = metadata !{
1325     i32 786470,          ;; Tag
1326     null,                ;; File
1327     null,                ;; Context
1328     metadata !"",        ;; Name
1329     i32 0,               ;; Line number
1330     i64 0,               ;; Size in bits
1331     i64 0,               ;; Align in bits
1332     i64 0,               ;; Offset in bits
1333     i32 0,               ;; Flags
1334     metadata !6          ;; Derived From type
1335   }
1336   ;;
1337   ;; Define the int type.
1338   ;;
1339   !6 = metadata !{
1340     i32 786468,          ;; Tag
1341     null,                ;; File
1342     null,                ;; Context
1343     metadata !"int",     ;; Name
1344     i32 0,               ;; Line number
1345     i64 32,              ;; Size in bits
1346     i64 32,              ;; Align in bits
1347     i64 0,               ;; Offset in bits
1348     i32 0,               ;; Flags
1349     i32 5                ;; Encoding
1350   }
1351
1352 C/C++ struct/union types
1353 ------------------------
1354
1355 Given the following as an example of C/C++ struct type:
1356
1357 .. code-block:: c
1358
1359   struct Color {
1360     unsigned Red;
1361     unsigned Green;
1362     unsigned Blue;
1363   };
1364
1365 a C/C++ front-end would generate the following descriptors:
1366
1367 .. code-block:: llvm
1368
1369   ;;
1370   ;; Define basic type for unsigned int.
1371   ;;
1372   !5 = metadata !{
1373     i32 786468,        ;; Tag
1374     null,              ;; File
1375     null,              ;; Context
1376     metadata !"unsigned int",
1377     i32 0,             ;; Line number
1378     i64 32,            ;; Size in Bits
1379     i64 32,            ;; Align in Bits
1380     i64 0,             ;; Offset in Bits
1381     i32 0,             ;; Flags
1382     i32 7              ;; Encoding
1383   }
1384   ;;
1385   ;; Define composite type for struct Color.
1386   ;;
1387   !2 = metadata !{
1388     i32 786451,        ;; Tag
1389     metadata !1,       ;; Compile unit
1390     null,              ;; Context
1391     metadata !"Color", ;; Name
1392     i32 1,             ;; Line number
1393     i64 96,            ;; Size in bits
1394     i64 32,            ;; Align in bits
1395     i64 0,             ;; Offset in bits
1396     i32 0,             ;; Flags
1397     null,              ;; Derived From
1398     metadata !3,       ;; Elements
1399     i32 0,             ;; Runtime Language
1400     null,              ;; Base type containing the vtable pointer for this type
1401     null               ;; Template parameters
1402   }
1403
1404   ;;
1405   ;; Define the Red field.
1406   ;;
1407   !4 = metadata !{
1408     i32 786445,        ;; Tag
1409     metadata !1,       ;; File
1410     metadata !1,       ;; Context
1411     metadata !"Red",   ;; Name
1412     i32 2,             ;; Line number
1413     i64 32,            ;; Size in bits
1414     i64 32,            ;; Align in bits
1415     i64 0,             ;; Offset in bits
1416     i32 0,             ;; Flags
1417     metadata !5        ;; Derived From type
1418   }
1419
1420   ;;
1421   ;; Define the Green field.
1422   ;;
1423   !6 = metadata !{
1424     i32 786445,        ;; Tag
1425     metadata !1,       ;; File
1426     metadata !1,       ;; Context
1427     metadata !"Green", ;; Name
1428     i32 3,             ;; Line number
1429     i64 32,            ;; Size in bits
1430     i64 32,            ;; Align in bits
1431     i64 32,             ;; Offset in bits
1432     i32 0,             ;; Flags
1433     metadata !5        ;; Derived From type
1434   }
1435
1436   ;;
1437   ;; Define the Blue field.
1438   ;;
1439   !7 = metadata !{
1440     i32 786445,        ;; Tag
1441     metadata !1,       ;; File
1442     metadata !1,       ;; Context
1443     metadata !"Blue",  ;; Name
1444     i32 4,             ;; Line number
1445     i64 32,            ;; Size in bits
1446     i64 32,            ;; Align in bits
1447     i64 64,             ;; Offset in bits
1448     i32 0,             ;; Flags
1449     metadata !5        ;; Derived From type
1450   }
1451
1452   ;;
1453   ;; Define the array of fields used by the composite type Color.
1454   ;;
1455   !3 = metadata !{metadata !4, metadata !6, metadata !7}
1456
1457 C/C++ enumeration types
1458 -----------------------
1459
1460 Given the following as an example of C/C++ enumeration type:
1461
1462 .. code-block:: c
1463
1464   enum Trees {
1465     Spruce = 100,
1466     Oak = 200,
1467     Maple = 300
1468   };
1469
1470 a C/C++ front-end would generate the following descriptors:
1471
1472 .. code-block:: llvm
1473
1474   ;;
1475   ;; Define composite type for enum Trees
1476   ;;
1477   !2 = metadata !{
1478     i32 786436,        ;; Tag
1479     metadata !1,       ;; File
1480     metadata !1,       ;; Context
1481     metadata !"Trees", ;; Name
1482     i32 1,             ;; Line number
1483     i64 32,            ;; Size in bits
1484     i64 32,            ;; Align in bits
1485     i64 0,             ;; Offset in bits
1486     i32 0,             ;; Flags
1487     null,              ;; Derived From type
1488     metadata !3,       ;; Elements
1489     i32 0              ;; Runtime language
1490   }
1491
1492   ;;
1493   ;; Define the array of enumerators used by composite type Trees.
1494   ;;
1495   !3 = metadata !{metadata !4, metadata !5, metadata !6}
1496
1497   ;;
1498   ;; Define Spruce enumerator.
1499   ;;
1500   !4 = metadata !{i32 786472, metadata !"Spruce", i64 100}
1501
1502   ;;
1503   ;; Define Oak enumerator.
1504   ;;
1505   !5 = metadata !{i32 786472, metadata !"Oak", i64 200}
1506
1507   ;;
1508   ;; Define Maple enumerator.
1509   ;;
1510   !6 = metadata !{i32 786472, metadata !"Maple", i64 300}
1511
1512 Debugging information format
1513 ============================
1514
1515 Debugging Information Extension for Objective C Properties
1516 ----------------------------------------------------------
1517
1518 Introduction
1519 ^^^^^^^^^^^^
1520
1521 Objective C provides a simpler way to declare and define accessor methods using
1522 declared properties.  The language provides features to declare a property and
1523 to let compiler synthesize accessor methods.
1524
1525 The debugger lets developer inspect Objective C interfaces and their instance
1526 variables and class variables.  However, the debugger does not know anything
1527 about the properties defined in Objective C interfaces.  The debugger consumes
1528 information generated by compiler in DWARF format.  The format does not support
1529 encoding of Objective C properties.  This proposal describes DWARF extensions to
1530 encode Objective C properties, which the debugger can use to let developers
1531 inspect Objective C properties.
1532
1533 Proposal
1534 ^^^^^^^^
1535
1536 Objective C properties exist separately from class members.  A property can be
1537 defined only by "setter" and "getter" selectors, and be calculated anew on each
1538 access.  Or a property can just be a direct access to some declared ivar.
1539 Finally it can have an ivar "automatically synthesized" for it by the compiler,
1540 in which case the property can be referred to in user code directly using the
1541 standard C dereference syntax as well as through the property "dot" syntax, but
1542 there is no entry in the ``@interface`` declaration corresponding to this ivar.
1543
1544 To facilitate debugging, these properties we will add a new DWARF TAG into the
1545 ``DW_TAG_structure_type`` definition for the class to hold the description of a
1546 given property, and a set of DWARF attributes that provide said description.
1547 The property tag will also contain the name and declared type of the property.
1548
1549 If there is a related ivar, there will also be a DWARF property attribute placed
1550 in the ``DW_TAG_member`` DIE for that ivar referring back to the property TAG
1551 for that property.  And in the case where the compiler synthesizes the ivar
1552 directly, the compiler is expected to generate a ``DW_TAG_member`` for that
1553 ivar (with the ``DW_AT_artificial`` set to 1), whose name will be the name used
1554 to access this ivar directly in code, and with the property attribute pointing
1555 back to the property it is backing.
1556
1557 The following examples will serve as illustration for our discussion:
1558
1559 .. code-block:: objc
1560
1561   @interface I1 {
1562     int n2;
1563   }
1564
1565   @property int p1;
1566   @property int p2;
1567   @end
1568
1569   @implementation I1
1570   @synthesize p1;
1571   @synthesize p2 = n2;
1572   @end
1573
1574 This produces the following DWARF (this is a "pseudo dwarfdump" output):
1575
1576 .. code-block:: none
1577
1578   0x00000100:  TAG_structure_type [7] *
1579                  AT_APPLE_runtime_class( 0x10 )
1580                  AT_name( "I1" )
1581                  AT_decl_file( "Objc_Property.m" )
1582                  AT_decl_line( 3 )
1583
1584   0x00000110    TAG_APPLE_property
1585                   AT_name ( "p1" )
1586                   AT_type ( {0x00000150} ( int ) )
1587
1588   0x00000120:   TAG_APPLE_property
1589                   AT_name ( "p2" )
1590                   AT_type ( {0x00000150} ( int ) )
1591
1592   0x00000130:   TAG_member [8]
1593                   AT_name( "_p1" )
1594                   AT_APPLE_property ( {0x00000110} "p1" )
1595                   AT_type( {0x00000150} ( int ) )
1596                   AT_artificial ( 0x1 )
1597
1598   0x00000140:    TAG_member [8]
1599                    AT_name( "n2" )
1600                    AT_APPLE_property ( {0x00000120} "p2" )
1601                    AT_type( {0x00000150} ( int ) )
1602
1603   0x00000150:  AT_type( ( int ) )
1604
1605 Note, the current convention is that the name of the ivar for an
1606 auto-synthesized property is the name of the property from which it derives
1607 with an underscore prepended, as is shown in the example.  But we actually
1608 don't need to know this convention, since we are given the name of the ivar
1609 directly.
1610
1611 Also, it is common practice in ObjC to have different property declarations in
1612 the @interface and @implementation - e.g. to provide a read-only property in
1613 the interface,and a read-write interface in the implementation.  In that case,
1614 the compiler should emit whichever property declaration will be in force in the
1615 current translation unit.
1616
1617 Developers can decorate a property with attributes which are encoded using
1618 ``DW_AT_APPLE_property_attribute``.
1619
1620 .. code-block:: objc
1621
1622   @property (readonly, nonatomic) int pr;
1623
1624 .. code-block:: none
1625
1626   TAG_APPLE_property [8]
1627     AT_name( "pr" )
1628     AT_type ( {0x00000147} (int) )
1629     AT_APPLE_property_attribute (DW_APPLE_PROPERTY_readonly, DW_APPLE_PROPERTY_nonatomic)
1630
1631 The setter and getter method names are attached to the property using
1632 ``DW_AT_APPLE_property_setter`` and ``DW_AT_APPLE_property_getter`` attributes.
1633
1634 .. code-block:: objc
1635
1636   @interface I1
1637   @property (setter=myOwnP3Setter:) int p3;
1638   -(void)myOwnP3Setter:(int)a;
1639   @end
1640
1641   @implementation I1
1642   @synthesize p3;
1643   -(void)myOwnP3Setter:(int)a{ }
1644   @end
1645
1646 The DWARF for this would be:
1647
1648 .. code-block:: none
1649
1650   0x000003bd: TAG_structure_type [7] *
1651                 AT_APPLE_runtime_class( 0x10 )
1652                 AT_name( "I1" )
1653                 AT_decl_file( "Objc_Property.m" )
1654                 AT_decl_line( 3 )
1655
1656   0x000003cd      TAG_APPLE_property
1657                     AT_name ( "p3" )
1658                     AT_APPLE_property_setter ( "myOwnP3Setter:" )
1659                     AT_type( {0x00000147} ( int ) )
1660
1661   0x000003f3:     TAG_member [8]
1662                     AT_name( "_p3" )
1663                     AT_type ( {0x00000147} ( int ) )
1664                     AT_APPLE_property ( {0x000003cd} )
1665                     AT_artificial ( 0x1 )
1666
1667 New DWARF Tags
1668 ^^^^^^^^^^^^^^
1669
1670 +-----------------------+--------+
1671 | TAG                   | Value  |
1672 +=======================+========+
1673 | DW_TAG_APPLE_property | 0x4200 |
1674 +-----------------------+--------+
1675
1676 New DWARF Attributes
1677 ^^^^^^^^^^^^^^^^^^^^
1678
1679 +--------------------------------+--------+-----------+
1680 | Attribute                      | Value  | Classes   |
1681 +================================+========+===========+
1682 | DW_AT_APPLE_property           | 0x3fed | Reference |
1683 +--------------------------------+--------+-----------+
1684 | DW_AT_APPLE_property_getter    | 0x3fe9 | String    |
1685 +--------------------------------+--------+-----------+
1686 | DW_AT_APPLE_property_setter    | 0x3fea | String    |
1687 +--------------------------------+--------+-----------+
1688 | DW_AT_APPLE_property_attribute | 0x3feb | Constant  |
1689 +--------------------------------+--------+-----------+
1690
1691 New DWARF Constants
1692 ^^^^^^^^^^^^^^^^^^^
1693
1694 +--------------------------------+-------+
1695 | Name                           | Value |
1696 +================================+=======+
1697 | DW_AT_APPLE_PROPERTY_readonly  | 0x1   |
1698 +--------------------------------+-------+
1699 | DW_AT_APPLE_PROPERTY_readwrite | 0x2   |
1700 +--------------------------------+-------+
1701 | DW_AT_APPLE_PROPERTY_assign    | 0x4   |
1702 +--------------------------------+-------+
1703 | DW_AT_APPLE_PROPERTY_retain    | 0x8   |
1704 +--------------------------------+-------+
1705 | DW_AT_APPLE_PROPERTY_copy      | 0x10  |
1706 +--------------------------------+-------+
1707 | DW_AT_APPLE_PROPERTY_nonatomic | 0x20  |
1708 +--------------------------------+-------+
1709
1710 Name Accelerator Tables
1711 -----------------------
1712
1713 Introduction
1714 ^^^^^^^^^^^^
1715
1716 The "``.debug_pubnames``" and "``.debug_pubtypes``" formats are not what a
1717 debugger needs.  The "``pub``" in the section name indicates that the entries
1718 in the table are publicly visible names only.  This means no static or hidden
1719 functions show up in the "``.debug_pubnames``".  No static variables or private
1720 class variables are in the "``.debug_pubtypes``".  Many compilers add different
1721 things to these tables, so we can't rely upon the contents between gcc, icc, or
1722 clang.
1723
1724 The typical query given by users tends not to match up with the contents of
1725 these tables.  For example, the DWARF spec states that "In the case of the name
1726 of a function member or static data member of a C++ structure, class or union,
1727 the name presented in the "``.debug_pubnames``" section is not the simple name
1728 given by the ``DW_AT_name attribute`` of the referenced debugging information
1729 entry, but rather the fully qualified name of the data or function member."
1730 So the only names in these tables for complex C++ entries is a fully
1731 qualified name.  Debugger users tend not to enter their search strings as
1732 "``a::b::c(int,const Foo&) const``", but rather as "``c``", "``b::c``" , or
1733 "``a::b::c``".  So the name entered in the name table must be demangled in
1734 order to chop it up appropriately and additional names must be manually entered
1735 into the table to make it effective as a name lookup table for debuggers to
1736 se.
1737
1738 All debuggers currently ignore the "``.debug_pubnames``" table as a result of
1739 its inconsistent and useless public-only name content making it a waste of
1740 space in the object file.  These tables, when they are written to disk, are not
1741 sorted in any way, leaving every debugger to do its own parsing and sorting.
1742 These tables also include an inlined copy of the string values in the table
1743 itself making the tables much larger than they need to be on disk, especially
1744 for large C++ programs.
1745
1746 Can't we just fix the sections by adding all of the names we need to this
1747 table? No, because that is not what the tables are defined to contain and we
1748 won't know the difference between the old bad tables and the new good tables.
1749 At best we could make our own renamed sections that contain all of the data we
1750 need.
1751
1752 These tables are also insufficient for what a debugger like LLDB needs.  LLDB
1753 uses clang for its expression parsing where LLDB acts as a PCH.  LLDB is then
1754 often asked to look for type "``foo``" or namespace "``bar``", or list items in
1755 namespace "``baz``".  Namespaces are not included in the pubnames or pubtypes
1756 tables.  Since clang asks a lot of questions when it is parsing an expression,
1757 we need to be very fast when looking up names, as it happens a lot.  Having new
1758 accelerator tables that are optimized for very quick lookups will benefit this
1759 type of debugging experience greatly.
1760
1761 We would like to generate name lookup tables that can be mapped into memory
1762 from disk, and used as is, with little or no up-front parsing.  We would also
1763 be able to control the exact content of these different tables so they contain
1764 exactly what we need.  The Name Accelerator Tables were designed to fix these
1765 issues.  In order to solve these issues we need to:
1766
1767 * Have a format that can be mapped into memory from disk and used as is
1768 * Lookups should be very fast
1769 * Extensible table format so these tables can be made by many producers
1770 * Contain all of the names needed for typical lookups out of the box
1771 * Strict rules for the contents of tables
1772
1773 Table size is important and the accelerator table format should allow the reuse
1774 of strings from common string tables so the strings for the names are not
1775 duplicated.  We also want to make sure the table is ready to be used as-is by
1776 simply mapping the table into memory with minimal header parsing.
1777
1778 The name lookups need to be fast and optimized for the kinds of lookups that
1779 debuggers tend to do.  Optimally we would like to touch as few parts of the
1780 mapped table as possible when doing a name lookup and be able to quickly find
1781 the name entry we are looking for, or discover there are no matches.  In the
1782 case of debuggers we optimized for lookups that fail most of the time.
1783
1784 Each table that is defined should have strict rules on exactly what is in the
1785 accelerator tables and documented so clients can rely on the content.
1786
1787 Hash Tables
1788 ^^^^^^^^^^^
1789
1790 Standard Hash Tables
1791 """"""""""""""""""""
1792
1793 Typical hash tables have a header, buckets, and each bucket points to the
1794 bucket contents:
1795
1796 .. code-block:: none
1797
1798   .------------.
1799   |  HEADER    |
1800   |------------|
1801   |  BUCKETS   |
1802   |------------|
1803   |  DATA      |
1804   `------------'
1805
1806 The BUCKETS are an array of offsets to DATA for each hash:
1807
1808 .. code-block:: none
1809
1810   .------------.
1811   | 0x00001000 | BUCKETS[0]
1812   | 0x00002000 | BUCKETS[1]
1813   | 0x00002200 | BUCKETS[2]
1814   | 0x000034f0 | BUCKETS[3]
1815   |            | ...
1816   | 0xXXXXXXXX | BUCKETS[n_buckets]
1817   '------------'
1818
1819 So for ``bucket[3]`` in the example above, we have an offset into the table
1820 0x000034f0 which points to a chain of entries for the bucket.  Each bucket must
1821 contain a next pointer, full 32 bit hash value, the string itself, and the data
1822 for the current string value.
1823
1824 .. code-block:: none
1825
1826               .------------.
1827   0x000034f0: | 0x00003500 | next pointer
1828               | 0x12345678 | 32 bit hash
1829               | "erase"    | string value
1830               | data[n]    | HashData for this bucket
1831               |------------|
1832   0x00003500: | 0x00003550 | next pointer
1833               | 0x29273623 | 32 bit hash
1834               | "dump"     | string value
1835               | data[n]    | HashData for this bucket
1836               |------------|
1837   0x00003550: | 0x00000000 | next pointer
1838               | 0x82638293 | 32 bit hash
1839               | "main"     | string value
1840               | data[n]    | HashData for this bucket
1841               `------------'
1842
1843 The problem with this layout for debuggers is that we need to optimize for the
1844 negative lookup case where the symbol we're searching for is not present.  So
1845 if we were to lookup "``printf``" in the table above, we would make a 32 hash
1846 for "``printf``", it might match ``bucket[3]``.  We would need to go to the
1847 offset 0x000034f0 and start looking to see if our 32 bit hash matches.  To do
1848 so, we need to read the next pointer, then read the hash, compare it, and skip
1849 to the next bucket.  Each time we are skipping many bytes in memory and
1850 touching new cache pages just to do the compare on the full 32 bit hash.  All
1851 of these accesses then tell us that we didn't have a match.
1852
1853 Name Hash Tables
1854 """"""""""""""""
1855
1856 To solve the issues mentioned above we have structured the hash tables a bit
1857 differently: a header, buckets, an array of all unique 32 bit hash values,
1858 followed by an array of hash value data offsets, one for each hash value, then
1859 the data for all hash values:
1860
1861 .. code-block:: none
1862
1863   .-------------.
1864   |  HEADER     |
1865   |-------------|
1866   |  BUCKETS    |
1867   |-------------|
1868   |  HASHES     |
1869   |-------------|
1870   |  OFFSETS    |
1871   |-------------|
1872   |  DATA       |
1873   `-------------'
1874
1875 The ``BUCKETS`` in the name tables are an index into the ``HASHES`` array.  By
1876 making all of the full 32 bit hash values contiguous in memory, we allow
1877 ourselves to efficiently check for a match while touching as little memory as
1878 possible.  Most often checking the 32 bit hash values is as far as the lookup
1879 goes.  If it does match, it usually is a match with no collisions.  So for a
1880 table with "``n_buckets``" buckets, and "``n_hashes``" unique 32 bit hash
1881 values, we can clarify the contents of the ``BUCKETS``, ``HASHES`` and
1882 ``OFFSETS`` as:
1883
1884 .. code-block:: none
1885
1886   .-------------------------.
1887   |  HEADER.magic           | uint32_t
1888   |  HEADER.version         | uint16_t
1889   |  HEADER.hash_function   | uint16_t
1890   |  HEADER.bucket_count    | uint32_t
1891   |  HEADER.hashes_count    | uint32_t
1892   |  HEADER.header_data_len | uint32_t
1893   |  HEADER_DATA            | HeaderData
1894   |-------------------------|
1895   |  BUCKETS                | uint32_t[n_buckets] // 32 bit hash indexes
1896   |-------------------------|
1897   |  HASHES                 | uint32_t[n_hashes] // 32 bit hash values
1898   |-------------------------|
1899   |  OFFSETS                | uint32_t[n_hashes] // 32 bit offsets to hash value data
1900   |-------------------------|
1901   |  ALL HASH DATA          |
1902   `-------------------------'
1903
1904 So taking the exact same data from the standard hash example above we end up
1905 with:
1906
1907 .. code-block:: none
1908
1909               .------------.
1910               | HEADER     |
1911               |------------|
1912               |          0 | BUCKETS[0]
1913               |          2 | BUCKETS[1]
1914               |          5 | BUCKETS[2]
1915               |          6 | BUCKETS[3]
1916               |            | ...
1917               |        ... | BUCKETS[n_buckets]
1918               |------------|
1919               | 0x........ | HASHES[0]
1920               | 0x........ | HASHES[1]
1921               | 0x........ | HASHES[2]
1922               | 0x........ | HASHES[3]
1923               | 0x........ | HASHES[4]
1924               | 0x........ | HASHES[5]
1925               | 0x12345678 | HASHES[6]    hash for BUCKETS[3]
1926               | 0x29273623 | HASHES[7]    hash for BUCKETS[3]
1927               | 0x82638293 | HASHES[8]    hash for BUCKETS[3]
1928               | 0x........ | HASHES[9]
1929               | 0x........ | HASHES[10]
1930               | 0x........ | HASHES[11]
1931               | 0x........ | HASHES[12]
1932               | 0x........ | HASHES[13]
1933               | 0x........ | HASHES[n_hashes]
1934               |------------|
1935               | 0x........ | OFFSETS[0]
1936               | 0x........ | OFFSETS[1]
1937               | 0x........ | OFFSETS[2]
1938               | 0x........ | OFFSETS[3]
1939               | 0x........ | OFFSETS[4]
1940               | 0x........ | OFFSETS[5]
1941               | 0x000034f0 | OFFSETS[6]   offset for BUCKETS[3]
1942               | 0x00003500 | OFFSETS[7]   offset for BUCKETS[3]
1943               | 0x00003550 | OFFSETS[8]   offset for BUCKETS[3]
1944               | 0x........ | OFFSETS[9]
1945               | 0x........ | OFFSETS[10]
1946               | 0x........ | OFFSETS[11]
1947               | 0x........ | OFFSETS[12]
1948               | 0x........ | OFFSETS[13]
1949               | 0x........ | OFFSETS[n_hashes]
1950               |------------|
1951               |            |
1952               |            |
1953               |            |
1954               |            |
1955               |            |
1956               |------------|
1957   0x000034f0: | 0x00001203 | .debug_str ("erase")
1958               | 0x00000004 | A 32 bit array count - number of HashData with name "erase"
1959               | 0x........ | HashData[0]
1960               | 0x........ | HashData[1]
1961               | 0x........ | HashData[2]
1962               | 0x........ | HashData[3]
1963               | 0x00000000 | String offset into .debug_str (terminate data for hash)
1964               |------------|
1965   0x00003500: | 0x00001203 | String offset into .debug_str ("collision")
1966               | 0x00000002 | A 32 bit array count - number of HashData with name "collision"
1967               | 0x........ | HashData[0]
1968               | 0x........ | HashData[1]
1969               | 0x00001203 | String offset into .debug_str ("dump")
1970               | 0x00000003 | A 32 bit array count - number of HashData with name "dump"
1971               | 0x........ | HashData[0]
1972               | 0x........ | HashData[1]
1973               | 0x........ | HashData[2]
1974               | 0x00000000 | String offset into .debug_str (terminate data for hash)
1975               |------------|
1976   0x00003550: | 0x00001203 | String offset into .debug_str ("main")
1977               | 0x00000009 | A 32 bit array count - number of HashData with name "main"
1978               | 0x........ | HashData[0]
1979               | 0x........ | HashData[1]
1980               | 0x........ | HashData[2]
1981               | 0x........ | HashData[3]
1982               | 0x........ | HashData[4]
1983               | 0x........ | HashData[5]
1984               | 0x........ | HashData[6]
1985               | 0x........ | HashData[7]
1986               | 0x........ | HashData[8]
1987               | 0x00000000 | String offset into .debug_str (terminate data for hash)
1988               `------------'
1989
1990 So we still have all of the same data, we just organize it more efficiently for
1991 debugger lookup.  If we repeat the same "``printf``" lookup from above, we
1992 would hash "``printf``" and find it matches ``BUCKETS[3]`` by taking the 32 bit
1993 hash value and modulo it by ``n_buckets``.  ``BUCKETS[3]`` contains "6" which
1994 is the index into the ``HASHES`` table.  We would then compare any consecutive
1995 32 bit hashes values in the ``HASHES`` array as long as the hashes would be in
1996 ``BUCKETS[3]``.  We do this by verifying that each subsequent hash value modulo
1997 ``n_buckets`` is still 3.  In the case of a failed lookup we would access the
1998 memory for ``BUCKETS[3]``, and then compare a few consecutive 32 bit hashes
1999 before we know that we have no match.  We don't end up marching through
2000 multiple words of memory and we really keep the number of processor data cache
2001 lines being accessed as small as possible.
2002
2003 The string hash that is used for these lookup tables is the Daniel J.
2004 Bernstein hash which is also used in the ELF ``GNU_HASH`` sections.  It is a
2005 very good hash for all kinds of names in programs with very few hash
2006 collisions.
2007
2008 Empty buckets are designated by using an invalid hash index of ``UINT32_MAX``.
2009
2010 Details
2011 ^^^^^^^
2012
2013 These name hash tables are designed to be generic where specializations of the
2014 table get to define additional data that goes into the header ("``HeaderData``"),
2015 how the string value is stored ("``KeyType``") and the content of the data for each
2016 hash value.
2017
2018 Header Layout
2019 """""""""""""
2020
2021 The header has a fixed part, and the specialized part.  The exact format of the
2022 header is:
2023
2024 .. code-block:: c
2025
2026   struct Header
2027   {
2028     uint32_t   magic;           // 'HASH' magic value to allow endian detection
2029     uint16_t   version;         // Version number
2030     uint16_t   hash_function;   // The hash function enumeration that was used
2031     uint32_t   bucket_count;    // The number of buckets in this hash table
2032     uint32_t   hashes_count;    // The total number of unique hash values and hash data offsets in this table
2033     uint32_t   header_data_len; // The bytes to skip to get to the hash indexes (buckets) for correct alignment
2034                                 // Specifically the length of the following HeaderData field - this does not
2035                                 // include the size of the preceding fields
2036     HeaderData header_data;     // Implementation specific header data
2037   };
2038
2039 The header starts with a 32 bit "``magic``" value which must be ``'HASH'``
2040 encoded as an ASCII integer.  This allows the detection of the start of the
2041 hash table and also allows the table's byte order to be determined so the table
2042 can be correctly extracted.  The "``magic``" value is followed by a 16 bit
2043 ``version`` number which allows the table to be revised and modified in the
2044 future.  The current version number is 1. ``hash_function`` is a ``uint16_t``
2045 enumeration that specifies which hash function was used to produce this table.
2046 The current values for the hash function enumerations include:
2047
2048 .. code-block:: c
2049
2050   enum HashFunctionType
2051   {
2052     eHashFunctionDJB = 0u, // Daniel J Bernstein hash function
2053   };
2054
2055 ``bucket_count`` is a 32 bit unsigned integer that represents how many buckets
2056 are in the ``BUCKETS`` array.  ``hashes_count`` is the number of unique 32 bit
2057 hash values that are in the ``HASHES`` array, and is the same number of offsets
2058 are contained in the ``OFFSETS`` array.  ``header_data_len`` specifies the size
2059 in bytes of the ``HeaderData`` that is filled in by specialized versions of
2060 this table.
2061
2062 Fixed Lookup
2063 """"""""""""
2064
2065 The header is followed by the buckets, hashes, offsets, and hash value data.
2066
2067 .. code-block:: c
2068
2069   struct FixedTable
2070   {
2071     uint32_t buckets[Header.bucket_count];  // An array of hash indexes into the "hashes[]" array below
2072     uint32_t hashes [Header.hashes_count];  // Every unique 32 bit hash for the entire table is in this table
2073     uint32_t offsets[Header.hashes_count];  // An offset that corresponds to each item in the "hashes[]" array above
2074   };
2075
2076 ``buckets`` is an array of 32 bit indexes into the ``hashes`` array.  The
2077 ``hashes`` array contains all of the 32 bit hash values for all names in the
2078 hash table.  Each hash in the ``hashes`` table has an offset in the ``offsets``
2079 array that points to the data for the hash value.
2080
2081 This table setup makes it very easy to repurpose these tables to contain
2082 different data, while keeping the lookup mechanism the same for all tables.
2083 This layout also makes it possible to save the table to disk and map it in
2084 later and do very efficient name lookups with little or no parsing.
2085
2086 DWARF lookup tables can be implemented in a variety of ways and can store a lot
2087 of information for each name.  We want to make the DWARF tables extensible and
2088 able to store the data efficiently so we have used some of the DWARF features
2089 that enable efficient data storage to define exactly what kind of data we store
2090 for each name.
2091
2092 The ``HeaderData`` contains a definition of the contents of each HashData chunk.
2093 We might want to store an offset to all of the debug information entries (DIEs)
2094 for each name.  To keep things extensible, we create a list of items, or
2095 Atoms, that are contained in the data for each name.  First comes the type of
2096 the data in each atom:
2097
2098 .. code-block:: c
2099
2100   enum AtomType
2101   {
2102     eAtomTypeNULL       = 0u,
2103     eAtomTypeDIEOffset  = 1u,   // DIE offset, check form for encoding
2104     eAtomTypeCUOffset   = 2u,   // DIE offset of the compiler unit header that contains the item in question
2105     eAtomTypeTag        = 3u,   // DW_TAG_xxx value, should be encoded as DW_FORM_data1 (if no tags exceed 255) or DW_FORM_data2
2106     eAtomTypeNameFlags  = 4u,   // Flags from enum NameFlags
2107     eAtomTypeTypeFlags  = 5u,   // Flags from enum TypeFlags
2108   };
2109
2110 The enumeration values and their meanings are:
2111
2112 .. code-block:: none
2113
2114   eAtomTypeNULL       - a termination atom that specifies the end of the atom list
2115   eAtomTypeDIEOffset  - an offset into the .debug_info section for the DWARF DIE for this name
2116   eAtomTypeCUOffset   - an offset into the .debug_info section for the CU that contains the DIE
2117   eAtomTypeDIETag     - The DW_TAG_XXX enumeration value so you don't have to parse the DWARF to see what it is
2118   eAtomTypeNameFlags  - Flags for functions and global variables (isFunction, isInlined, isExternal...)
2119   eAtomTypeTypeFlags  - Flags for types (isCXXClass, isObjCClass, ...)
2120
2121 Then we allow each atom type to define the atom type and how the data for each
2122 atom type data is encoded:
2123
2124 .. code-block:: c
2125
2126   struct Atom
2127   {
2128     uint16_t type;  // AtomType enum value
2129     uint16_t form;  // DWARF DW_FORM_XXX defines
2130   };
2131
2132 The ``form`` type above is from the DWARF specification and defines the exact
2133 encoding of the data for the Atom type.  See the DWARF specification for the
2134 ``DW_FORM_`` definitions.
2135
2136 .. code-block:: c
2137
2138   struct HeaderData
2139   {
2140     uint32_t die_offset_base;
2141     uint32_t atom_count;
2142     Atoms    atoms[atom_count0];
2143   };
2144
2145 ``HeaderData`` defines the base DIE offset that should be added to any atoms
2146 that are encoded using the ``DW_FORM_ref1``, ``DW_FORM_ref2``,
2147 ``DW_FORM_ref4``, ``DW_FORM_ref8`` or ``DW_FORM_ref_udata``.  It also defines
2148 what is contained in each ``HashData`` object -- ``Atom.form`` tells us how large
2149 each field will be in the ``HashData`` and the ``Atom.type`` tells us how this data
2150 should be interpreted.
2151
2152 For the current implementations of the "``.apple_names``" (all functions +
2153 globals), the "``.apple_types``" (names of all types that are defined), and
2154 the "``.apple_namespaces``" (all namespaces), we currently set the ``Atom``
2155 array to be:
2156
2157 .. code-block:: c
2158
2159   HeaderData.atom_count = 1;
2160   HeaderData.atoms[0].type = eAtomTypeDIEOffset;
2161   HeaderData.atoms[0].form = DW_FORM_data4;
2162
2163 This defines the contents to be the DIE offset (eAtomTypeDIEOffset) that is
2164 encoded as a 32 bit value (DW_FORM_data4).  This allows a single name to have
2165 multiple matching DIEs in a single file, which could come up with an inlined
2166 function for instance.  Future tables could include more information about the
2167 DIE such as flags indicating if the DIE is a function, method, block,
2168 or inlined.
2169
2170 The KeyType for the DWARF table is a 32 bit string table offset into the
2171 ".debug_str" table.  The ".debug_str" is the string table for the DWARF which
2172 may already contain copies of all of the strings.  This helps make sure, with
2173 help from the compiler, that we reuse the strings between all of the DWARF
2174 sections and keeps the hash table size down.  Another benefit to having the
2175 compiler generate all strings as DW_FORM_strp in the debug info, is that
2176 DWARF parsing can be made much faster.
2177
2178 After a lookup is made, we get an offset into the hash data.  The hash data
2179 needs to be able to deal with 32 bit hash collisions, so the chunk of data
2180 at the offset in the hash data consists of a triple:
2181
2182 .. code-block:: c
2183
2184   uint32_t str_offset
2185   uint32_t hash_data_count
2186   HashData[hash_data_count]
2187
2188 If "str_offset" is zero, then the bucket contents are done. 99.9% of the
2189 hash data chunks contain a single item (no 32 bit hash collision):
2190
2191 .. code-block:: none
2192
2193   .------------.
2194   | 0x00001023 | uint32_t KeyType (.debug_str[0x0001023] => "main")
2195   | 0x00000004 | uint32_t HashData count
2196   | 0x........ | uint32_t HashData[0] DIE offset
2197   | 0x........ | uint32_t HashData[1] DIE offset
2198   | 0x........ | uint32_t HashData[2] DIE offset
2199   | 0x........ | uint32_t HashData[3] DIE offset
2200   | 0x00000000 | uint32_t KeyType (end of hash chain)
2201   `------------'
2202
2203 If there are collisions, you will have multiple valid string offsets:
2204
2205 .. code-block:: none
2206
2207   .------------.
2208   | 0x00001023 | uint32_t KeyType (.debug_str[0x0001023] => "main")
2209   | 0x00000004 | uint32_t HashData count
2210   | 0x........ | uint32_t HashData[0] DIE offset
2211   | 0x........ | uint32_t HashData[1] DIE offset
2212   | 0x........ | uint32_t HashData[2] DIE offset
2213   | 0x........ | uint32_t HashData[3] DIE offset
2214   | 0x00002023 | uint32_t KeyType (.debug_str[0x0002023] => "print")
2215   | 0x00000002 | uint32_t HashData count
2216   | 0x........ | uint32_t HashData[0] DIE offset
2217   | 0x........ | uint32_t HashData[1] DIE offset
2218   | 0x00000000 | uint32_t KeyType (end of hash chain)
2219   `------------'
2220
2221 Current testing with real world C++ binaries has shown that there is around 1
2222 32 bit hash collision per 100,000 name entries.
2223
2224 Contents
2225 ^^^^^^^^
2226
2227 As we said, we want to strictly define exactly what is included in the
2228 different tables.  For DWARF, we have 3 tables: "``.apple_names``",
2229 "``.apple_types``", and "``.apple_namespaces``".
2230
2231 "``.apple_names``" sections should contain an entry for each DWARF DIE whose
2232 ``DW_TAG`` is a ``DW_TAG_label``, ``DW_TAG_inlined_subroutine``, or
2233 ``DW_TAG_subprogram`` that has address attributes: ``DW_AT_low_pc``,
2234 ``DW_AT_high_pc``, ``DW_AT_ranges`` or ``DW_AT_entry_pc``.  It also contains
2235 ``DW_TAG_variable`` DIEs that have a ``DW_OP_addr`` in the location (global and
2236 static variables).  All global and static variables should be included,
2237 including those scoped within functions and classes.  For example using the
2238 following code:
2239
2240 .. code-block:: c
2241
2242   static int var = 0;
2243
2244   void f ()
2245   {
2246     static int var = 0;
2247   }
2248
2249 Both of the static ``var`` variables would be included in the table.  All
2250 functions should emit both their full names and their basenames.  For C or C++,
2251 the full name is the mangled name (if available) which is usually in the
2252 ``DW_AT_MIPS_linkage_name`` attribute, and the ``DW_AT_name`` contains the
2253 function basename.  If global or static variables have a mangled name in a
2254 ``DW_AT_MIPS_linkage_name`` attribute, this should be emitted along with the
2255 simple name found in the ``DW_AT_name`` attribute.
2256
2257 "``.apple_types``" sections should contain an entry for each DWARF DIE whose
2258 tag is one of:
2259
2260 * DW_TAG_array_type
2261 * DW_TAG_class_type
2262 * DW_TAG_enumeration_type
2263 * DW_TAG_pointer_type
2264 * DW_TAG_reference_type
2265 * DW_TAG_string_type
2266 * DW_TAG_structure_type
2267 * DW_TAG_subroutine_type
2268 * DW_TAG_typedef
2269 * DW_TAG_union_type
2270 * DW_TAG_ptr_to_member_type
2271 * DW_TAG_set_type
2272 * DW_TAG_subrange_type
2273 * DW_TAG_base_type
2274 * DW_TAG_const_type
2275 * DW_TAG_constant
2276 * DW_TAG_file_type
2277 * DW_TAG_namelist
2278 * DW_TAG_packed_type
2279 * DW_TAG_volatile_type
2280 * DW_TAG_restrict_type
2281 * DW_TAG_interface_type
2282 * DW_TAG_unspecified_type
2283 * DW_TAG_shared_type
2284
2285 Only entries with a ``DW_AT_name`` attribute are included, and the entry must
2286 not be a forward declaration (``DW_AT_declaration`` attribute with a non-zero
2287 value).  For example, using the following code:
2288
2289 .. code-block:: c
2290
2291   int main ()
2292   {
2293     int *b = 0;
2294     return *b;
2295   }
2296
2297 We get a few type DIEs:
2298
2299 .. code-block:: none
2300
2301   0x00000067:     TAG_base_type [5]
2302                   AT_encoding( DW_ATE_signed )
2303                   AT_name( "int" )
2304                   AT_byte_size( 0x04 )
2305
2306   0x0000006e:     TAG_pointer_type [6]
2307                   AT_type( {0x00000067} ( int ) )
2308                   AT_byte_size( 0x08 )
2309
2310 The DW_TAG_pointer_type is not included because it does not have a ``DW_AT_name``.
2311
2312 "``.apple_namespaces``" section should contain all ``DW_TAG_namespace`` DIEs.
2313 If we run into a namespace that has no name this is an anonymous namespace, and
2314 the name should be output as "``(anonymous namespace)``" (without the quotes).
2315 Why?  This matches the output of the ``abi::cxa_demangle()`` that is in the
2316 standard C++ library that demangles mangled names.
2317
2318
2319 Language Extensions and File Format Changes
2320 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2321
2322 Objective-C Extensions
2323 """"""""""""""""""""""
2324
2325 "``.apple_objc``" section should contain all ``DW_TAG_subprogram`` DIEs for an
2326 Objective-C class.  The name used in the hash table is the name of the
2327 Objective-C class itself.  If the Objective-C class has a category, then an
2328 entry is made for both the class name without the category, and for the class
2329 name with the category.  So if we have a DIE at offset 0x1234 with a name of
2330 method "``-[NSString(my_additions) stringWithSpecialString:]``", we would add
2331 an entry for "``NSString``" that points to DIE 0x1234, and an entry for
2332 "``NSString(my_additions)``" that points to 0x1234.  This allows us to quickly
2333 track down all Objective-C methods for an Objective-C class when doing
2334 expressions.  It is needed because of the dynamic nature of Objective-C where
2335 anyone can add methods to a class.  The DWARF for Objective-C methods is also
2336 emitted differently from C++ classes where the methods are not usually
2337 contained in the class definition, they are scattered about across one or more
2338 compile units.  Categories can also be defined in different shared libraries.
2339 So we need to be able to quickly find all of the methods and class functions
2340 given the Objective-C class name, or quickly find all methods and class
2341 functions for a class + category name.  This table does not contain any
2342 selector names, it just maps Objective-C class names (or class names +
2343 category) to all of the methods and class functions.  The selectors are added
2344 as function basenames in the "``.debug_names``" section.
2345
2346 In the "``.apple_names``" section for Objective-C functions, the full name is
2347 the entire function name with the brackets ("``-[NSString
2348 stringWithCString:]``") and the basename is the selector only
2349 ("``stringWithCString:``").
2350
2351 Mach-O Changes
2352 """"""""""""""
2353
2354 The sections names for the apple hash tables are for non-mach-o files.  For
2355 mach-o files, the sections should be contained in the ``__DWARF`` segment with
2356 names as follows:
2357
2358 * "``.apple_names``" -> "``__apple_names``"
2359 * "``.apple_types``" -> "``__apple_types``"
2360 * "``.apple_namespaces``" -> "``__apple_namespac``" (16 character limit)
2361 * "``.apple_objc``" -> "``__apple_objc``"
2362