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