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