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