c5b650322427ffa0f5807b05c4d5971f1d0a8e3a
[dwarf-doc.git] / dwarf5 / latexdoc / compression.tex
1 \chapter[Compression (Informative)]{DWARF Compression and Duplicate Elimination (Informative)}
2 \label{dwarfcompressionandduplicateeliminationinformative}
3
4 % It seemed difficult to get close to the same layout and 
5 % captioning as DWARF4 here with figures as they moved (floated)
6 % making it hard to follow.  Hence this uses fewer figures.
7
8 DWARF can use a lot of disk space.
9
10 This is especially true for C++, where the depth and complexity
11 of headers can mean that many, many (possibly thousands of)
12 declarations are repeated in every compilation unit. C++
13 templates can also mean that some functions and their DWARF
14 descriptions get duplicated.
15
16 This Appendix describes techniques for using the DWARF
17 representation in combination with features and characteristics
18 of some common object file representations to reduce redundancy
19 without losing information. It is worth emphasizing that none
20 of these techniques are necessary to provide a complete and
21 accurate DWARF description; they are solely concerned with
22 reducing the size of DWARF information.
23
24 The techniques described here depend more directly and more
25 obviously on object file concepts and linker mechanisms than
26 most other parts of DWARF. While the presentation tends to
27 use the vocabulary of specific systems, this is primarily to
28 aid in describing the techniques by appealing to well\dash known
29 terminology. These techniques can be employed on any system
30 that supports certain general functional capabilities
31 (described below).
32
33
34 \section{Using Compilation Units}
35 \label{app:usingcompilationunits}
36
37 \subsection{Overview}
38 The general approach is to break up the debug information of
39 a compilation into separate normal and partial compilation
40 units, each consisting of one or more sections. By arranging
41 that a sufficiently similar partitioning occurs in other
42 compilations, a suitable system linker can delete redundant
43 groups of sections when combining object files.
44
45 \textit{The following uses some traditional section naming here
46 but aside from the DWARF sections, the names are just meant
47 to suggest traditional contents as a way of explaining the
48 approach, not to be limiting.}
49
50 A traditional relocatable object output 
51 from a single compilation might contain sections named:
52 \begin{alltt}
53     .data
54     .text
55     .debug\_info
56     .debug\_abbrev
57     .debug\_line
58     .debug\_aranges
59 \end{alltt}
60 A relocatable object from a compilation system 
61 attempting duplicate DWARF elimination might
62 contain sections as in:
63
64 \begin{alltt}
65     .data
66     .text
67     .debug\_info
68     .debug\_abbrev
69     .debug\_line
70     .debug\_aranges
71 \end{alltt}
72
73 followed (or preceded, the order is not significant) 
74 by a series of section groups:
75 \begin{alltt}
76 ==== Section group 1
77     .debug\_info
78     .debug\_abbrev
79     .debug\_line
80 ==== ...
81 ==== Section group N
82     .debug\_info
83     .debug\_abbrev
84     .debug\_line
85 \end{alltt}
86
87 where each section group might or might not contain executable
88 code (\textit{.text} sections) or data (\textit{.data} sections).
89
90 A \textit{section group} is a named set of section contributions
91 within an object file with the property that the entire set
92 of section contributions must be retained or discarded as a
93 whole; no partial elimination is allowed. Section groups can
94 generally be handled by a linker in two ways:
95
96 \begin{enumerate}[1.]
97 \item Given multiple identical (duplicate) section groups,
98 one of them is chosen to be kept and used, while the rest
99 are discarded.
100
101 \item Given a section group that is not referenced from any
102 section outside of the section group, the section group
103 is discarded.
104
105
106 \end{enumerate}
107
108
109 Which handling applies may be indicated by the section group
110 itself and/or selection of certain linker options.
111
112 For example, if a linker determines that section group 1
113 from A.o and section group 3 from B.o are identical, it could
114 discard one group and arrange that all references in A.o and
115 B.o apply to the remaining one of the two identical section
116 groups. This saves space.
117
118 An important part of making it possible to “redirect”
119 references to the surviving section group is the use of
120 consistently chosen linker global symbols for referring to
121 locations within each section group. It follows that references
122 are simply to external names and the linker already knows
123 how to match up references and definitions.
124
125 What is minimally needed from the object file format and system
126 linker (outside of DWARF itself, and normal object/linker
127 facilities such as simple relocations) are:
128
129 \begin{enumerate}[1.]
130
131 \item A means of referencing from inside one .debug\_info
132 compilation unit to another .debug\_info compilation unit
133 (DW\-\_FORM\-\_ref\-\_addr provides this).
134
135 \item A means of having multiple contributions to specific sections
136 (for example, .debug\_info, and so on) in a single object file.
137
138 \item  A means of identifying a section group (giving it a name).
139
140 \item A means of identifying which sections go together to make
141 up a section group, so that the group can be treated as a unit
142 (kept or discarded).
143
144 \item  A means of indicating how each section group should be
145 processed by the linker.
146
147 \end{enumerate}
148
149 \textit{The notion of section and section contribution used here
150 corresponds closely to the similarly named concepts in the
151 ELF object file representation. The notion of section group is
152 an abstraction of common extensions of the ELF representation
153 widely known as ``COMDATs'' or ``COMDAT sections''. (Other
154 object file representations provide COMDAT\dash style mechanisms as
155 well.) There are several variations in the COMDAT schemes in
156 common use, any of which should be sufficient for the purposes
157 of the DWARF duplicate elimination techniques described here.}
158
159 \subsection{Naming and Usage Considerations}
160 \label{app:namingandusageconsiderations}
161
162 A precise description of the means of deriving names usable
163 by the linker to access DWARF entities is not part of this
164 specification. Nonetheless, an outline of a usable approach
165 is given here to make this more understandable and to guide
166 implementors.
167
168 Implementations should clearly document their naming conventions.
169
170 In the following, it will be helpful to refer to the examples
171 in 
172 Figure \refersec{app:duplicateeliminationexample1csource}
173 through 
174 Figure \refersec{app:duplicateeliminationexample2companiondwarf}
175 of 
176 Section \refersec{app:examples}.
177
178 \textbf{Section Group Names}
179
180 Section groups must have a section group name. For the subsequent C++ example, a name like
181
182 <producer-prefix>.<file-designator>.<gid-number>
183
184 will suffice, where
185
186 \begin{itemize}
187
188 \item  \textless producer\dash prefix \textgreater 
189 is some string specific to the
190 producer, which has a language\dash designation embedded in the
191 name when appropriate. (Alternatively, the language name
192 could be embedded in the 
193 \textless gid\dash number \textgreater).
194
195
196 \item  \textless file\dash designator \textgreater
197 names the file, such as wa.h in
198 the example.
199
200
201 \item  \textless gid\dash number \textgreater
202 is a string generated to identify the
203 specific wa.h header file in such a way that
204
205 \begin{itemize}
206
207 \item  a 'matching' output from another compile generates
208 the same 
209 \textless gid\dash number \textgreater,
210 and
211
212 \item  a non\dash matching output (say because of \#defines)
213 generates a different 
214 \textless gid\dash number \textgreater.
215 \end{itemize}
216
217 \end{itemize}
218
219 \textit{It may be useful to think of a 
220 \textless gid\dash number \textgreater
221 as a kind
222 of ``digital signature'' that allows a fast test for the
223 equality of two section groups.}
224
225 So, for example, the section group corresponding to file wa.h
226 above is given the name \textit{my.compiler.company.cpp.wa.h.123456}.
227
228
229
230 \textbf{Debugging Information Entry Names}
231
232 Global labels for debugging information entries (need explained
233 below) within a section group can be given names of the form
234
235 \begin{alltt}
236     <prefix>.<file-designator>.<gid-number>.<die-number>
237 \end{alltt}
238
239 such as
240
241 \begin{alltt}
242     my.compiler.company.wa.h.123456.987
243 \end{alltt}
244
245 where
246 \begin{itemize}
247 \item \textless prefix \textgreater\  
248 distinguishes this as a DWARF debug info name, and should identify the producer
249 and, when appropriate, the language.
250 \item \textless file\dash designator\textgreater\  
251 and 
252 \textless gid\dash number \textgreater
253 are as above.
254
255 \item  \textless die\dash number \textgreater
256 could be a number sequentially assigned 
257 to entities (tokens, perhaps) found
258 during compilation.
259
260 \end{itemize}
261
262 In general, every point in the section group .debug\_info that
263 could be referenced from outside by any compilation unit must
264 normally have an external name generated for it in the linker
265 symbol table, whether the current compilation references all
266 those points or not.
267
268 The completeness of the set of names generated is a
269 quality\dash of\dash implementation issue.
270
271 It is up to the producer to ensure that if 
272 <die-numbers>
273 \textless die\dash numbers \textgreater
274 in separate compilations would not match properly then a
275 distinct 
276 \textless gid\dash number \textgreater
277 is generated.
278
279 Note that only section groups that are designated as
280 duplicate\dash removal\dash applies actually require the
281 \begin{alltt}
282     <prefix>.<file-designator>.<gid-number>.<die-number>
283 \end{alltt}
284 external labels for debugging information entries as all other
285 section group sections can use 'local' labels 
286 (section\dash relative
287 relocations).
288
289 (This is a consequence of separate compilation, not a rule
290 imposed by this document.)
291
292 \textit{Local labels use references with form DW\-\_FORM\-\_ref4
293 or 
294 DW\-\_FORM\-\_ref8. 
295 (These are affected by relocations
296 so 
297 DW\-\_FORM\-\_ref\-\_udata, 
298 DW\-\_FORM\-\_ref1 and 
299 DW\-\_FORM\-\_ref2 are
300 normally not usable and 
301 DW\-\_FORM\-\_ref\-\_addr is not necessary
302 for a local label.)}
303
304 \textbf{Use of \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} versus 
305 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit}}
306
307 A section group compilation unit that uses 
308 \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
309 is like any other compilation unit, in that its contents
310 are evaluated by consumers as though it were an ordinary
311 compilation unit.
312
313 An \#include directive appearing outside any other
314 declarations is a good candidate to be represented using
315 \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}. 
316 However, an \#include appearing inside
317 a C++ namespace declaration or a function, for example, is
318 not a good candidate because the entities included are not
319 necessarily file level entities.
320
321 This also applies to Fortran INCLUDE lines when declarations
322 are included into a procedure or module context.
323
324 Consequently a compiler must use \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} (instead
325 of \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}) in a section group whenever the section
326 group contents are not necessarily globally visible. This
327 directs consumers to ignore that compilation unit when scanning
328 top level declarations and definitions.
329
330 The \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} compilation unit will be referenced
331 from elsewhere and the referencing locations give the
332 appropriate context for interpreting the partial compilation
333 unit.
334
335 A \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} entry may have, as appropriate, any of
336 the attributes assigned to a \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}.
337
338
339 \textbf{Use of \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}}
340
341 A \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit} debugging information entry has an
342 \livelink{chap:DWATimport}{DW\-\_AT\-\_import} attribute referencing a \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} or
343 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} debugging information entry.
344
345 A \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit} debugging information entry refers
346 to a 
347 \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} or 
348 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} debugging
349 information entry to specify that the 
350 \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} or
351 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} contents logically appear at the point
352 of the 
353 \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit} entry.
354
355
356 \textbf{Use of DW\-\_FORM\-\_ref\-\_addr}
357
358 Use 
359 DW\-\_FORM\-\_ref\-\_addr to reference from one compilation
360 unit's debugging information entries to those of another
361 compilation unit.
362
363 When referencing into a removable section group .debug\_info
364 from another .debug\_info (from anywhere), the
365 \begin{alltt}
366 <prefix>.<file-designator>.<gid-number>.<die-number>
367 \end{alltt}
368 name should be used for an external symbol and a relocation
369 generated based on that name.
370
371 When referencing into a non-section group .debug\_info,
372 from another .debug\_info (from anywhere) 
373 DW\-\_FORM\-\_ref\-\_addr is
374 still the form to be used, but a section\dash relative relocation
375 generated by use of a non-exported name (often called an
376 ``internal name'') may be used for references within the
377 same object file.
378
379 \subsection{Examples}
380 \label{app:examples}
381
382 This section provides several examples in order to have a
383 concrete basis for discussion.
384
385 In these examples, the focus is on the arrangement of DWARF
386 information into sections (specifically the .debug\_info
387 section) and the naming conventions used to achieve references
388 into section groups. In practice, all of the examples that
389 follow involve DWARF sections other than just .debug\_info
390 (for example, .debug\_line, .debug\_aranges, or others);
391 however, only the .debug\_info section is shown to keep the
392 examples compact and easier to read.
393
394 The grouping of sections into a named set is shown, but the means for achieving this in terms of
395 the underlying object language is not (and varies from system to system).
396
397 \subsubsection{C++ Example}
398
399 The C++ source in 
400 Section \refersec{app:duplicateeliminationexample1csource}
401 is used to illustrate the DWARF
402 representation intended to allow duplicate elimination.
403
404 \paragraph{Duplicate elimination example 1: C++ Source} 
405 \label{app:duplicateeliminationexample1csource}
406
407 File wa.h
408
409 \begin{lstlisting}
410 struct A {
411    int i;
412 };
413 \end{lstlisting}
414
415 File wa.C
416
417 \begin{lstlisting}
418 #include "wa.h";
419 int
420 f(A &a)
421 {
422     return a.i + 2;
423 }
424 \end{lstlisting}
425
426
427 section \refersec{app:duplicateeliminationexample1dwarfsectiongroup}
428 shows the section group corresponding to the included file 
429 wa.h.
430
431
432 \paragraph{Duplicate elimination example 1: DWARF section group} 
433
434 \label{app:duplicateeliminationexample1dwarfsectiongroup}
435
436 \begin{alltt}
437 ==== Section group name:
438     my.compiler.company.cpp.wa.h.123456
439 == section .debug\_info
440 DW.cpp.wa.h.123456.1: ! linker global symbol
441     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
442         \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language}(DW\-\_LANG\-\_C\-\_plus\-\_plus)
443         ...  ! other unit attributes
444 DW.cpp.wa.h.123456.2: ! linker global symbol
445     \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
446         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("int")
447 DW.cpp.wa.h.123456.3: ! linker global symbol
448     \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
449         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("A")
450 DW.cpp.wa.h.123456.4: ! linker global symbol
451         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
452         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("i")
453         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(DW\-\_FORM\-\_refn to DW.cpp.wa.h.123456.2)
454             ! (This is a local reference, so the more
455             ! compact form DW\-\_FORM\-\_refn can be used)
456 \end{alltt}
457
458
459 Figure \refersec{app:duplicateeliminationexample1primarycompilationunit}
460 shows the ``normal'' DWARF sections, which are not part of
461 any section group, and how they make use of the information
462 in the section group shown above.
463
464 \paragraph{Duplicate elimination example 1: primary compilation unit} 
465 \label{app:duplicateeliminationexample1primarycompilationunit}
466 \begin{alltt}
467 == section .text
468     [generated code for function f]
469 == section .debug\_info
470     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
471 .L1:                   ! local (non-linker) symbol
472         \livelink{chap:DWTAGreferencetype}{DW\-\_TAG\-\_reference\-\_type}
473             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.cpp.wa.h.123456.3)
474         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
475             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("f")
476             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.cpp.wa.h.123456.2)
477             \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
478                 \livelink{chap:DWATname}{DW\-\_AT\-\_name}("a")
479                 \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to .L1)
480         ...
481 \end{alltt}
482
483 This example uses \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} for the section group,
484 implying that the contents of the compilation unit are
485 globally visible (in accordance with C++ language rules).
486 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} is not needed for the same reason.
487
488 \subsubsection{Fortran Example}
489
490
491 For a Fortran example, consider 
492 Figure \refersec{app:duplicateeliminationexample2fortransource}.
493
494
495 \paragraph{Duplicate elimination example 2: Fortran source} 
496 \label{app:duplicateeliminationexample2fortransource}
497
498 File CommonStuff.fh
499
500 \begin{lstlisting}
501 IMPLICIT INTEGER(A-Z)
502 COMMON /Common1/ C(100)
503 PARAMETER(SEVEN = 7)
504 \end{lstlisting}
505
506 File Func.f
507 \begin{lstlisting}
508
509 FUNCTION FOO (N)
510 INCLUDE 'CommonStuff.fh'
511 FOO = C(N + SEVEN)
512 RETURN
513 END
514 \end{lstlisting}
515
516
517 Section \refersec{app:duplicateeliminationexample2dwarfsectiongroup}
518 shows the section group 
519 corresponding to the included file CommonStuff.fh.
520
521 \paragraph{Duplicate elimination example 2: DWARF section group}
522 \label{app:duplicateeliminationexample2dwarfsectiongroup}
523
524 \begin{alltt}
525 ==== Section group name:
526
527     my.f90.company.f90.CommonStuff.fh.654321
528
529 == section .debug\_info
530
531 DW.myf90.CommonStuff.fh.654321.1:    ! linker global symbol
532     \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit}
533         ! ...compilation unit attributes, including...
534         \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language}(DW\-\_LANG\-\_Fortran90)
535         \livelink{chap:DWATidentifiercase}{DW\-\_AT\-\_identifier\-\_case}(DW\-\_ID\-\_case\-\_insensitive)
536
537 DW.myf90.CommonStuff.fh.654321.2: ! linker global symbol
538 3\$: \livelink{chap:DWTAGarraytype}{DW\-\_TAG\-\_array\-\_type}
539         ! unnamed
540         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
541             ! base type INTEGER
542         \livelink{chap:DWTAGsubrangetype}{DW\-\_TAG\-\_subrange\-\_type}
543             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
544                 ! base type INTEGER)
545             \livelink{chap:DWATlowerbound}{DW\-\_AT\-\_lower\-\_bound}(constant 1)
546             \livelink{chap:DWATupperbound}{DW\-\_AT\-\_upper\-\_bound}(constant 100)
547
548 DW.myf90.CommonStuff.fh.654321.3: ! linker global symbol
549     \livelink{chap:DWTAGcommonblock}{DW\-\_TAG\-\_common\-\_block}
550         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Common1")
551         \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(Address of common block Common1)
552         \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
553             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("C")
554             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to 3\$)
555             \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(address of C)
556
557 DW.myf90.CommonStuff.fh.654321.4: ! linker global symbol
558     \livelink{chap:DWTAGconstant}{DW\-\_TAG\-\_constant}
559         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("SEVEN")
560         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
561             ! base type INTEGER
562         \livelink{chap:DWATconstvalue}{DW\-\_AT\-\_const\-\_value}(constant 7)
563 \end{alltt}
564
565 Section \refersec{app:duplicateeliminationexample2primaryunit}
566 shows the sections for the primary compilation unit.
567
568
569
570 \paragraph{Duplicate elimination example 2: primary unit }
571 \label{app:duplicateeliminationexample2primaryunit}
572 \begin{alltt}
573 == section .text
574     [code for function Foo]
575
576 == section .debug\_info
577     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
578         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
579             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
580             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
581                 ! base type INTEGER
582             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
583                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
584                     DW.myf90.CommonStuff.fh.654321.1)
585             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! For Common1
586                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
587                     DW.myf90.CommonStuff.fh.654321.3)
588             \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable} ! For function result
589                 \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
590                     \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
591                         ! base type INTEGER
592 \end{alltt}
593
594 A companion main program is shown in 
595 Section \refersec{app:duplicateeliminationexample2companionsource}
596
597 \paragraph{Duplicate elimination example 2: companion source }
598 \label{app:duplicateeliminationexample2companionsource}
599
600 File Main.f 
601
602 \begin{lstlisting}
603 INCLUDE 'CommonStuff.fh'
604 C(50) = 8
605 PRINT *, 'Result = ', FOO(50 - SEVEN)
606 END
607 \end{lstlisting}
608
609 That main program results in an object file that
610 contained a duplicate of the section group named
611 my.f90.company.f90.CommonStuff.fh.654321 
612 corresponding to the
613 included file as well as the remainder of the main subprogram
614 as shown in 
615 Section \refersec{app:duplicateeliminationexample2companiondwarf}.
616
617 \paragraph{Duplicate elimination example 2: companion DWARF }
618 \label{app:duplicateeliminationexample2companiondwarf}
619
620 \begin{alltt}
621 == section .debug\_info
622     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
623         \livelink{chap:DWATname}{DW\-\_AT\-\_name}(F90\$main)
624         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
625             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("INTEGER")
626             \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding}(DW\-\_ATE\-\_signed)
627             \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size}(...)
628
629         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
630             ...
631         ...  ! other base types
632         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
633             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("F90\$main")
634             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
635                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
636                     DW.myf90.CommonStuff.fh.654321.1)
637             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! for Common1
638                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
639                     DW.myf90.CommonStuff.fh.654321.3)
640             ...
641 \end{alltt}
642
643
644 This example uses \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} for the section group
645 because the included declarations are not independently
646 visible as global entities.
647
648
649 \subsubsection{C Example}
650
651 The C++ example in this Section might appear to be equally
652 valid as a C example. However, it is prudent to include
653 a \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit} in the primary unit (see Figure 84)
654 with an \livelink{chap:DWATimport}{DW\-\_AT\-\_import} attribute that refers to the proper unit
655 in the section group.
656
657 \textit{The C rules for consistency of global (file scope) symbols
658 across compilations are less strict than for C++; inclusion
659 of the import unit attribute assures that the declarations of
660 the proper section group are considered before declarations
661 from other compilations.}
662
663
664 \section{Using Type Units}
665 \label{app:usingtypeunits}
666
667 A large portion of debug information is type information, and
668 in a typical compilation environment, many types are duplicated
669 many times. One method of controlling the amount of duplication
670 is separating each type into a separate .debug\_types section
671 and arranging for the linker to recognize and eliminate
672 duplicates at the individual type level.
673
674 Using this technique, each substantial type definition is
675 placed in its own individual section, while the remainder
676 of the DWARF information (non-type information, incomplete
677 type declarations, and definitions of trivial types) is
678 placed in the usual debug information section. In a typical
679 implementation, the relocatable object file may contain one
680 of each of these debug sections:
681
682 \begin{alltt}
683 .debug\_abbrev
684 .debug\_info
685 .debug\_line
686 \end{alltt}
687
688 and any number of these additional sections:
689
690 \begin{alltt}
691 .debug\_types
692 \end{alltt}
693
694 As discussed in the previous section 
695 (Section \refersec{app:usingcompilationunits}), 
696 many
697 linkers today support the concept of a COMDAT group or
698 linkonce section. The general idea is that a ``key'' can be
699 attached to a section or a group of sections, and the linker
700 will include only one copy of a section group (or individual
701 section) for any given key. For .debug\_types sections, the
702 key is the type signature formed from the algorithm given in
703 Section \refersec{datarep:typesignaturecomputation}.
704
705 \subsection{Signature Computation Example}
706 \label{app:signaturecomputationexample}
707
708 As an example, consider a C++ header file 
709 containing the type definitions shown
710 in Section \refersec{app:typesignatureexamplescsource}.
711
712 \subsubsection{ Type signature examples: C++ source}
713 \label{app:typesignatureexamplescsource}
714 \begin{lstlisting}
715 namespace N {
716
717  struct B;
718
719  struct C {
720      int x;
721      int y;
722  };
723
724  class A {
725    public:
726      A(int v);
727      int v();
728    private:
729      int v_;
730      struct A *next;
731      struct B *bp;
732      struct C c;
733  };
734
735  }
736 \end{lstlisting}
737
738 Next, consider one possible representation of the DWARF
739 information that describes the type “struct C” as shown
740 in 
741 \refersec{app:typesignaturecomputation1dwarfrepresentation}:
742
743 \subsubsection{Type signature  computation 1: DWARF representation}
744 \label{app:typesignaturecomputation1dwarfrepresentation}
745 % We keep the : (colon) away from the attribute so tokenizing in the python tools
746 % does not result in adding : into the attribute name.
747 \begin{alltt}
748   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
749       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : DW\-\_LANG\-\_C\-\_plus\-\_plus (4)
750     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
751         \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
752 L1:
753       \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
754           \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "C"
755           \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 8
756           \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
757           \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 5
758         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
759             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "x"
760             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
761             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 6
762             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
763             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
764         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
765             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "y"
766             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
767             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 7
768             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
769             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
770 L2:
771      \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
772          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
773          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : DW\-\_ATE\-\_signed
774          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
775 \end{alltt}
776
777 In computing a signature for the type N::C, flatten the type
778 description into a byte stream according to the procedure
779 outlined in 
780 Section \refersec{datarep:typesignaturecomputation}.
781 The result is shown in 
782 Section \refersec{app:typesignaturecomputation1flattenedbytestream}.
783
784 \subsubsection{Type signature  computation 1: flattened byte stream}
785 \label{app:typesignaturecomputation1flattenedbytestream}
786
787 \begin{alltt}
788 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
789 0x43 0x39 0x4e 0x00
790 // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
791 0x44 0x13
792 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "C"
793 0x41 0x03 0x08 0x43 0x00
794 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} DW\-\_FORM\-\_sdata 8
795 0x41 0x0b 0x0d 0x08
796 // Step 7: First child ("x")
797     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
798     0x44 0x0d
799     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "x"
800     0x41 0x03 0x08 0x78 0x00
801     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 0
802     0x41 0x38 0x0d 0x00
803     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
804     0x54 0x49
805         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
806         0x44 0x24
807         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "int"
808         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
809         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} DW\-\_FORM\-\_sdata 4
810         0x41 0x0b 0x0d 0x04
811         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} DW\-\_FORM\-\_sdata DW\-\_ATE\-\_signed
812         0x41 0x3e 0x0d 0x05
813         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
814         0x00
815     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
816     0x00
817 // Step 7: Second child ("y")
818     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
819     0x44 0x0d
820     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "y"
821     0x41 0x03 0x08 0x78 0x00
822     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 4
823     0x41 0x38 0x0d 0x04
824     // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
825     0x52 0x49 0x02
826     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
827     0x00
828 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
829 0x00
830 \end{alltt}
831
832 Running an MD5 hash over this byte stream, and taking the
833 low\dash order 64 bits, yields the final signature: 
834 0xd28081e8 dcf5070a.
835
836 Next, consider a representation of the DWARF information that
837 describes the type ``class A'' as shown in 
838 Section \refersec{app:typesignaturecomputation2dwarfrepresentation}.
839
840
841 \subsubsection{Type signature  computation 2: DWARF representation}
842 \label{app:typesignaturecomputation2dwarfrepresentation}
843
844 \begin{alltt}
845   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
846       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : DW\-\_LANG\-\_C\-\_plus\-\_plus (4)
847     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
848           \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
849 L1:
850         \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
851              \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
852              \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 20
853              \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
854              \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 10
855            \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
856                 \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v\_"
857                 \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
858                 \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 15
859                 \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
860                 \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
861                 \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : DW\-\_ACCESS\-\_private
862           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
863                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "next"
864                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
865                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 16
866                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
867                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
868                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : DW\-\_ACCESS\-\_private
869           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
870                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "bp"
871                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
872                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 17
873                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L4
874                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 8
875                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : DW\-\_ACCESS\-\_private
876           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
877                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "c"
878                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
879                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 18
880                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : 0xd28081e8 dcf5070a (signature for struct C)
881                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 12
882                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : DW\-\_ACCESS\-\_private
883        \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
884            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
885            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
886            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
887            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 12
888            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
889         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
890            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
891            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
892         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
893            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
894        \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
895            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
896            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v"
897            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
898            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 13
899            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
900            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
901          \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
902            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
903            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
904 L2:
905     \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
906          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
907          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : DW\-\_ATE\-\_signed
908          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
909 L3:
910     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
911          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L1
912 L4:
913     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
914          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L5
915     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
916          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
917 L5:
918        \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
919            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "B"
920            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
921 \end{alltt}
922
923 In this example, the structure types N::A and N::C have each
924 been placed in separate type units.  For N::A, the actual
925 definition of the type begins at label L1. The definition
926 involves references to the int base type and to two pointer
927 types. The information for each of these referenced types is
928 also included in this type unit, since base types and pointer
929 types are trivial types that are not worth the overhead of a
930 separate type unit. The last pointer type contains a reference
931 to an incomplete type N::B, which is also included here as
932 a declaration, since the complete type is unknown and its
933 signature is therefore unavailable. There is also a reference
934 to N::C, using DW\-\_FORM\-\_sig8 to refer to the type signature
935 for that type.
936
937 In computing a signature for the type N::A, flatten the type
938 description into a byte stream according to the procedure
939 outlined in 
940 Section \refersec{datarep:typesignaturecomputation}.
941 The result is shown in 
942 Section \refersec{app:typesignatureexample2flattenedbytestream}.
943
944 \subsubsection{Type signature example 2: flattenedbytestream}
945 \label{app:typesignatureexample2flattenedbytestream}
946 % DWARF4 had a DW_AT_namespace below, 
947 % but this error is fixed here to be DW_TAG_namespace.
948 \begin{alltt}
949 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
950 0x43 0x39 0x4e 0x00
951 // Step 3: 'D' \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
952 0x44 0x02
953 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "A"
954 0x41 0x03 0x08 0x41 0x00
955 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} DW\-\_FORM\-\_sdata 20
956 0x41 0x0b 0x0d 0x14
957 // Step 7: First child ("v\_")
958     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
959     0x44 0x0d
960     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "v\_"
961     0x41 0x03 0x08 0x76 0x5f 0x00
962     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} DW\-\_FORM\-\_sdata DW\-\_ACCESS\-\_private
963     0x41 0x32 0x0d 0x03
964     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 0
965     0x41 0x38 0x0d 0x00
966     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
967     0x54 0x49
968         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
969         0x44 0x24
970         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "int"
971         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
972         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} DW\-\_FORM\-\_sdata 4
973         0x41 0x0b 0x0d 0x04
974         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} DW\-\_FORM\-\_sdata DW\-\_ATE\-\_signed
975         0x41 0x3e 0x0d 0x05
976         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
977         0x00
978     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "v\_"
979     0x00
980 // Step 7: Second child ("next")
981     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
982     0x44 0x0d
983     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "next"
984     0x41 0x03 0x08 0x6e 0x65 0x78 0x74 0x00
985     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} DW\-\_FORM\-\_sdata DW\-\_ACCESS\-\_private
986     0x41 0x32 0x0d 0x03
987     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 4
988     0x41 0x38 0x0d 0x04
989     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#3)
990     0x54 0x49
991         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
992         0x44 0x0f
993         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
994         0x4e 0x49
995         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
996         0x43 0x39 0x4e 0x00 0x45
997         // Step 5: "A"
998         0x41 0x00
999         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1000         0x00
1001     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1002     0x00
1003 // Step 7: Third child ("bp")
1004     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1005     0x44 0x0d
1006     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "bp"
1007     0x41 0x03 0x08 0x62 0x70 0x00
1008     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} DW\-\_FORM\-\_sdata DW\-\_ACCESS\-\_private
1009     0x41 0x32 0x0d 0x03
1010     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 8
1011     0x41 0x38 0x0d 0x08
1012     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#4)
1013     0x54 0x49
1014         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1015 0x44 0x0f
1016         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
1017         0x4e 0x49
1018         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
1019         0x43 0x39 0x4e 0x00 0x45
1020         // Step 5: "B"
1021         0x42 0x00
1022         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1023         0x00
1024     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1025     0x00
1026 // Step 7: Fourth child ("c")
1027     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1028     0x44 0x0d
1029     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "c"
1030     0x41 0x03 0x08 0x63 0x00
1031     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} DW\-\_FORM\-\_sdata DW\-\_ACCESS\-\_private
1032     0x41 0x32 0x0d 0x03
1033     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 12
1034     0x41 0x38 0x0d 0x0c
1035     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#5)
1036     0x54 0x49
1037         // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
1038         0x43 0x39 0x4e 0x00
1039         // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
1040         0x44 0x13
1041         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "C"
1042         0x41 0x03 0x08 0x43 0x00
1043         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} DW\-\_FORM\-\_sdata 8
1044         0x41 0x0b 0x0d 0x08
1045         // Step 7: First child ("x")
1046             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1047             0x44 0x0d
1048             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "x"
1049             0x41 0x03 0x08 0x78 0x00
1050             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 0
1051             0x41 0x38 0x0d 0x00
1052             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1053             0x52 0x49 0x02
1054             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
1055             0x00
1056         // Step 7: Second child ("y")
1057             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1058             0x44 0x0d
1059             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} DW\-\_FORM\-\_string "y"
1060             0x41 0x03 0x08 0x79 0x00
1061             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} DW\-\_FORM\-\_sdata 4
1062             0x41 0x38 0x0d 0x04
1063             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1064             0x52 0x49 0x02
1065             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
1066             0x00
1067         // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
1068         0x00
1069     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "c"
1070     0x00
1071 // Step 7: Fifth child ("A")
1072     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "A"
1073     0x53 0x2e 0x41 0x00
1074 // Step 7: Sixth child ("v")
1075     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "v"
1076     0x53 0x2e 0x76 0x00
1077 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "A"
1078 0x00
1079 \end{alltt}
1080
1081 Running an MD5 hash over this byte stream, and taking the
1082 low-order 64 bits, yields the final signature: 0xd6d160f5
1083 5589f6e9.
1084
1085
1086 A source file that includes this header file may declare a
1087 variable of type N::A, and its DWARF information may look
1088 that shown in 
1089 Section \refersec{app:typesignatureexampleusage}.
1090
1091
1092 \subsubsection{Type signature example usage}
1093 \label{app:typesignatureexampleusage}
1094
1095 \begin{alltt}
1096   \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
1097   ...
1098   \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
1099     ...
1100     \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
1101       \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "a"
1102       \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : (signature) 0xd6d160f5 5589f6e9
1103       \livelink{chap:DWATlocation}{DW\-\_AT\-\_location} : ...
1104     ...
1105 \end{alltt}
1106
1107 \subsection{Type Signature Computation Grammar}
1108 \label{app:typesignaturecomputationgrammar}
1109
1110 This section
1111 presents a semi-formal grammar that may aid in understanding
1112 how the bytes of the flattened type description are formed
1113 during the type signature computation algorithm of Section
1114 Section \refersec{datarep:typesignaturecomputation}. 
1115
1116
1117 \begin{alltt}
1118 signature
1119     : opt-context debug-entry attributes children
1120
1121 opt-context           // Step 2
1122     : 'C' tag-code string opt-context
1123     : empty
1124
1125 debug-entry           // Step 3
1126     : 'D' tag-code
1127
1128 attributes            // Steps 4, 5, 6
1129     : attribute attributes
1130     : empty
1131
1132 attribute
1133     : 'A' at-code form-encoded-value     // Normal attributes
1134     : 'N' at-code opt-context 'E' string // Reference to type
1135                                          // by name
1136     : 'R' at-code back-ref               // Back-reference 
1137                                          // to visited type
1138     : 'T' at-code signature              // Recursive type
1139 children             //  Step 7
1140     : child children
1141     : '\\0'
1142
1143 child
1144     : 'S' tag-code string
1145     : signature
1146 tag-code
1147     : <ULEB128>
1148 at-code
1149     : <ULEB128>
1150 form-encoded-value
1151     : DW\-\_FORM\-\_sdata value
1152     : DW\-\_FORM\-\_flag value
1153     : DW\-\_FORM\-\_string string
1154     : DW\-\_FORM\-\_block block
1155 DW\-\_FORM\-\_string
1156     : '\\x08'
1157 DW\-\_FORM\-\_block
1158     : '\\x09'
1159 DW\-\_FORM\-\_flag
1160     : '\\x0c'
1161 DW\-\_FORM\-\_sdata
1162     : '\\x0d'
1163 value
1164     : <SLEB128>
1165 block
1166     : <ULEB128> <fixed-length-block>
1167                       // The ULEB128 gives the length of the block
1168 back-ref
1169     : <ULEB128>
1170 string
1171     : <null-terminated-string>
1172 empty
1173     :
1174 \end{alltt}
1175
1176
1177 \section{Summary of Compression Techniques}
1178 \label{app:summaryofcompressiontechniques}
1179 \subsection{\#include compression}
1180 \label{app:includecompression}
1181
1182 C++ has a much greater problem than C with the number and
1183 size of the headers included and the amount of data in each,
1184 but even with C there is substantial header file information
1185 duplication.
1186
1187 A reasonable approach is to put each header file in its own
1188 section group, using the naming rules mentioned above. The
1189 section groups are marked to ensure duplicate removal.
1190
1191 All data instances and code instances (even if they came
1192 from the header files above) are put into non-section group
1193 sections such as the base object file .debug\_info section.
1194
1195 \subsection{Eliminating function duplication}
1196 \label{app:eliminatingfunctionduplication}
1197
1198
1199 Function templates (C++) result in code for the same template
1200 instantiation being compiled into multiple archives or
1201 relocatable objects. The linker wants to keep only one of a
1202 given entity. The DWARF description, and everything else for
1203 this function, should be reduced to just a single copy.
1204
1205 For each such code group (function template in this example)
1206 the compiler assigns a name for the group which will match
1207 all other instantiations of this function but match nothing
1208 else. The section groups are marked to ensure duplicate
1209 removal, so that the second and subsequent definitions seen
1210 by the static linker are simply discarded.
1211
1212
1213 References to other .debug\_info sections follow the approach
1214 suggested above, but the naming rule might be slightly
1215 different in that the 
1216 \begin{alltt}
1217 <file-designator> 
1218 \end{alltt}
1219 should be interpreted
1220 as a 
1221 \begin{alltt}
1222 <function-designator>.
1223 \end{alltt}
1224
1225
1226
1227 \subsection{Single-function-per-DWARF-compilation-unit}
1228 \label{app:singlefunctionperdwarfcompilationunit}
1229
1230 Section groups can help make it easy for a linker to completely
1231 remove unused functions.
1232
1233 Such section groups are not marked for duplicate removal,
1234 since the functions are not duplicates of anything.
1235
1236 Each function is given a compilation unit and a section
1237 group. Each such compilation unit is complete, with its own
1238 text, data, and DWARF sections.
1239
1240 There will also be a compilation unit that has the file\dash level
1241 declarations and definitions. Other per\dash function compilation
1242 unit DWARF information (.debug\_info) points to this common
1243 file\dash level compilation unit using \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}.
1244
1245 Section groups can use DW\-\_FORM\-\_ref\-\_addr and internal labels
1246 (section\dash relative relocations) to refer to the main object
1247 file sections, as the section groups here are either deleted
1248 as unused or kept. There is no possibility (aside from error)
1249 of a group from some other compilation being used in place
1250 of one of these groups.
1251
1252
1253 \subsection{Inlining and out-of-line-instances}
1254 \label{app:inliningandoutoflineinstances}
1255
1256 Abstract instances and concrete-out-of-line instances may be
1257 put in distinct compilation units using section groups. This
1258 makes possible some useful duplicate DWARF elimination.
1259
1260 \textit{No special provision for eliminating class duplication
1261 resulting from template instantiation is made here, though
1262 nothing prevents eliminating such duplicates using section
1263 groups.}
1264
1265
1266 \subsection{Separate Type Units}
1267 \label{app:separatetypeunits}
1268
1269 Each complete declaration of a globally-visible type can be
1270 placed in its own separate type section, with a group key
1271 derived from the type signature. The linker can then remove
1272 all duplicate type declarations based on the key.
1273