This indexes letters f, g, and h.
[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 \addtoindex{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 \addtoindex{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 \addtoindexx{Fortran}
526
527 \begin{lstlisting}
528 IMPLICIT INTEGER(A-Z)
529 COMMON /Common1/ C(100)
530 PARAMETER(SEVEN = 7)
531 \end{lstlisting}
532
533 File Func.f
534 \begin{lstlisting}
535
536 FUNCTION FOO (N)
537 INCLUDE 'CommonStuff.fh'
538 FOO = C(N + SEVEN)
539 RETURN
540 END
541 \end{lstlisting}
542
543
544 Section \refersec{app:duplicateeliminationexample2dwarfsectiongroup}
545 shows the section group 
546 corresponding to the included file 
547 \addtoindexx{Fortran example}
548 CommonStuff.fh.
549
550 \paragraph{Duplicate elimination example 2: DWARF section group}
551 \label{app:duplicateeliminationexample2dwarfsectiongroup}
552
553 \begin{alltt}
554 ==== Section group name:
555
556     my.f90.company.f90.CommonStuff.fh.654321
557
558 == section \addtoindex{.debug\_info}
559
560 DW.myf90.CommonStuff.fh.654321.1:    ! linker global symbol
561     \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit}
562         ! ...compilation unit attributes, including...
563         \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language}(\livelink{chap:DWLANGFortran90}{DW\-\_LANG\-\_Fortran90})
564         \livelink{chap:DWATidentifiercase}{DW\-\_AT\-\_identifier\-\_case}(\livelink{chap:DWIDcaseinsensitive}{DW\-\_ID\-\_case\-\_insensitive})
565
566 DW.myf90.CommonStuff.fh.654321.2: ! linker global symbol
567 3\$: \livelink{chap:DWTAGarraytype}{DW\-\_TAG\-\_array\-\_type}
568         ! unnamed
569         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
570             ! base type INTEGER
571         \livelink{chap:DWTAGsubrangetype}{DW\-\_TAG\-\_subrange\-\_type}
572             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
573                 ! base type INTEGER)
574             \livelink{chap:DWATlowerbound}{DW\-\_AT\-\_lower\-\_bound}(constant 1)
575             \livelink{chap:DWATupperbound}{DW\-\_AT\-\_upper\-\_bound}(constant 100)
576
577 DW.myf90.CommonStuff.fh.654321.3: ! linker global symbol
578     \livelink{chap:DWTAGcommonblock}{DW\-\_TAG\-\_common\-\_block}
579         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Common1")
580         \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(Address of common \nolink{block} Common1)
581         \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
582             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("C")
583             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to 3\$)
584             \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(address of C)
585
586 DW.myf90.CommonStuff.fh.654321.4: ! linker global symbol
587     \livelink{chap:DWTAGconstant}{DW\-\_TAG\-\_constant}
588         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("SEVEN")
589         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
590             ! base type INTEGER
591         \livelink{chap:DWATconstvalue}{DW\-\_AT\-\_const\-\_value}(constant 7)
592 \end{alltt}
593
594 Section \refersec{app:duplicateeliminationexample2primaryunit}
595 shows the sections for the primary compilation unit.
596
597
598
599 \paragraph{Duplicate elimination example 2: primary unit }
600 \label{app:duplicateeliminationexample2primaryunit}
601 \begin{alltt}
602 == section .text
603     [code for function Foo]
604
605 == section \addtoindex{.debug\_info}
606     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
607         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
608             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
609             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
610                 ! base type INTEGER
611             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
612                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
613                     DW.myf90.CommonStuff.fh.654321.1)
614             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! For Common1
615                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
616                     DW.myf90.CommonStuff.fh.654321.3)
617             \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable} ! For function result
618                 \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
619                     \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
620                         ! base type INTEGER
621 \end{alltt}
622
623 A companion main program is shown in 
624 Section \refersec{app:duplicateeliminationexample2companionsource}
625
626 \paragraph{Duplicate elimination example 2: companion source }
627 \label{app:duplicateeliminationexample2companionsource}
628
629 File Main.f 
630
631 \begin{lstlisting}
632 INCLUDE 'CommonStuff.fh'
633 C(50) = 8
634 PRINT *, 'Result = ', FOO(50 - SEVEN)
635 END
636 \end{lstlisting}
637
638 That main program results in an object file that
639 contained a duplicate of the section group named
640 my.f90.company.f90.CommonStuff.fh.654321 
641 corresponding to the
642 included file as well as the remainder of the main subprogram
643 as shown in 
644 Section \refersec{app:duplicateeliminationexample2companiondwarf}.
645
646 \paragraph{Duplicate elimination example 2: companion DWARF }
647 \label{app:duplicateeliminationexample2companiondwarf}
648
649 \begin{alltt}
650 == section \addtoindex{.debug\_info}
651     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
652         \livelink{chap:DWATname}{DW\-\_AT\-\_name}(F90\$main)
653         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
654             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("INTEGER")
655             \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding}(\livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed})
656             \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size}(...)
657
658         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
659             ...
660         ...  ! other base types
661         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
662             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("F90\$main")
663             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
664                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
665                     DW.myf90.CommonStuff.fh.654321.1)
666             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! for Common1
667                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
668                     DW.myf90.CommonStuff.fh.654321.3)
669             ...
670 \end{alltt}
671
672
673 This example uses \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} for the section group
674 because the included declarations are not independently
675 visible as global entities.
676
677
678 \subsubsection{C Example}
679
680 The \addtoindex{C} example 
681 \addtoindexx{DWARF duplicate elimination!C example}
682 in this Section might appear to be equally
683 valid as a \addtoindex{C} example. However, it is prudent to include
684 a \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
685 in the primary unit 
686 (see Figure \refersec{app:duplicateeliminationexample1primarycompilationunit})
687 with an \livelink{chap:DWATimport}{DW\-\_AT\-\_import} attribute that refers to the proper unit
688 in the section group.
689
690 \textit{The \addtoindex{C} rules for consistency of global (file scope) symbols
691 across compilations are less strict than for C++; inclusion
692 of the import unit attribute assures that the declarations of
693 the proper section group are considered before declarations
694 from other compilations.}
695
696
697 \section{Using Type Units}
698 \label{app:usingtypeunits}
699
700 A large portion of debug information is type information, and
701 in a typical compilation environment, many types are duplicated
702 many times. One method of controlling the amount of duplication
703 is separating each type into a separate 
704 addtoindex{.debug\_types} section
705 and arranging for the linker to recognize and eliminate
706 duplicates at the individual type level.
707
708 Using this technique, each substantial type definition is
709 placed in its own individual section, while the remainder
710 of the DWARF information (non-type information, incomplete
711 type declarations, and definitions of trivial types) is
712 placed in the usual debug information section. In a typical
713 implementation, the relocatable object file may contain one
714 of each of these debug sections:
715
716 \begin{alltt}
717 \addtoindex{.debug\_abbrev}
718 \addtoindex{.debug\_info}
719 \addtoindex{.debug\_line}
720 \end{alltt}
721
722 and any number of these additional sections:
723
724 \begin{alltt}
725 \addtoindex{.debug\_types}
726 \end{alltt}
727
728 As discussed in the previous section 
729 (Section \refersec{app:usingcompilationunits}), 
730 many
731 linkers today support the concept of a COMDAT group or
732 linkonce section. The general idea is that a ``key'' can be
733 attached to a section or a group of sections, and the linker
734 will include only one copy of a section group (or individual
735 section) for any given key. For 
736 \addtoindex{.debug\_types} sections, the
737 key is the type signature formed from the algorithm given in
738 Section \refersec{datarep:typesignaturecomputation}.
739
740 \subsection{Signature Computation Example}
741 \label{app:signaturecomputationexample}
742
743 As an example, consider a \addtoindex{C++} header file 
744 containing the type definitions shown
745 in Section \refersec{app:typesignatureexamplescsource}.
746
747 \subsubsection{ Type signature examples: C++ source}
748 \label{app:typesignatureexamplescsource}
749 \begin{lstlisting}
750 namespace N {
751
752  struct B;
753
754  struct C {
755      int x;
756      int y;
757  };
758
759  class A {
760    public:
761      A(int v);
762      int v();
763    private:
764      int v_;
765      struct A *next;
766      struct B *bp;
767      struct C c;
768  };
769
770  }
771 \end{lstlisting}
772
773 Next, consider one possible representation of the DWARF
774 information that describes the type “struct C” as shown
775 in 
776 \refersec{app:typesignaturecomputation1dwarfrepresentation}:
777
778 \subsubsection{Type signature  computation 1: DWARF representation}
779 \label{app:typesignaturecomputation1dwarfrepresentation}
780 % We keep the : (colon) away from the attribute so tokenizing in the python tools
781 % does not result in adding : into the attribute name.
782 \begin{alltt}
783   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
784       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : \livelink{chap:DWLANGCplusplus}{DW\-\_LANG\-\_C\-\_plus\-\_plus} (4)
785     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
786         \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
787 L1:
788       \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
789           \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "C"
790           \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 8
791           \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
792           \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 5
793         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
794             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "x"
795             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
796             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 6
797             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
798             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
799         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
800             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "y"
801             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
802             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 7
803             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
804             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
805 L2:
806      \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
807          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
808          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
809          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
810 \end{alltt}
811
812 In computing a signature for the type N::C, flatten the type
813 description into a byte stream according to the procedure
814 outlined in 
815 Section \refersec{datarep:typesignaturecomputation}.
816 The result is shown in 
817 Section \refersec{app:typesignaturecomputation1flattenedbytestream}.
818
819 \subsubsection{Type signature  computation 1: flattened byte stream}
820 \label{app:typesignaturecomputation1flattenedbytestream}
821
822 \begin{alltt}
823 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
824 0x43 0x39 0x4e 0x00
825 // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
826 0x44 0x13
827 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "C"
828 0x41 0x03 0x08 0x43 0x00
829 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
830 0x41 0x0b 0x0d 0x08
831 // Step 7: First child ("x")
832     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
833     0x44 0x0d
834     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "x"
835     0x41 0x03 0x08 0x78 0x00
836     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
837     0x41 0x38 0x0d 0x00
838     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
839     0x54 0x49
840         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
841         0x44 0x24
842         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "int"
843         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
844         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
845         0x41 0x0b 0x0d 0x04
846         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
847         0x41 0x3e 0x0d 0x05
848         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
849         0x00
850     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
851     0x00
852 // Step 7: Second child ("y")
853     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
854     0x44 0x0d
855     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "y"
856     0x41 0x03 0x08 0x78 0x00
857     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
858     0x41 0x38 0x0d 0x04
859     // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
860     0x52 0x49 0x02
861     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
862     0x00
863 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
864 0x00
865 \end{alltt}
866
867 Running an MD5 hash over this byte stream, and taking the
868 low\dash order 64 bits, yields the final signature: 
869 0xd28081e8 dcf5070a.
870
871 Next, consider a representation of the DWARF information that
872 describes the type ``class A'' as shown in 
873 Section \refersec{app:typesignaturecomputation2dwarfrepresentation}.
874
875
876 \subsubsection{Type signature  computation 2: DWARF representation}
877 \label{app:typesignaturecomputation2dwarfrepresentation}
878
879 \begin{alltt}
880   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
881       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : \livelink{chap:DWLANGCplusplus}{DW\-\_LANG\-\_C\-\_plus\-\_plus} (4)
882     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
883           \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
884 L1:
885         \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
886              \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
887              \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 20
888              \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
889              \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 10
890            \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
891                 \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v\_"
892                 \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
893                 \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 15
894                 \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
895                 \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
896                 \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
897           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
898                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "next"
899                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
900                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 16
901                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
902                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
903                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
904           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
905                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "bp"
906                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
907                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 17
908                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L4
909                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 8
910                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
911           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
912                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "c"
913                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
914                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 18
915                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : 0xd28081e8 dcf5070a (signature for struct C)
916                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 12
917                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
918        \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
919            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
920            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
921            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
922            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 12
923            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
924         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
925            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
926            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
927         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
928            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
929        \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
930            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
931            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v"
932            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
933            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 13
934            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
935            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
936          \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
937            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
938            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
939 L2:
940     \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
941          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
942          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
943          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
944 L3:
945     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
946          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L1
947 L4:
948     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
949          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L5
950     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
951          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
952 L5:
953        \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
954            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "B"
955            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
956 \end{alltt}
957
958 In this example, the structure types N::A and N::C have each
959 been placed in separate type units.  For N::A, the actual
960 definition of the type begins at label L1. The definition
961 involves references to the int base type and to two pointer
962 types. The information for each of these referenced types is
963 also included in this type unit, since base types and pointer
964 types are trivial types that are not worth the overhead of a
965 separate type unit. The last pointer type contains a reference
966 to an incomplete type N::B, which is also included here as
967 a declaration, since the complete type is unknown and its
968 signature is therefore unavailable. There is also a reference
969 to N::C, using 
970 \livelink{chap:DWFORMrefsig8}{DW\-\_FORM\-\_ref\-\_sig8} to refer to the type signature
971 for that type.
972
973 In computing a signature for the type N::A, flatten the type
974 description into a byte stream according to the procedure
975 outlined in 
976 Section \refersec{datarep:typesignaturecomputation}.
977 The result is shown in 
978 Section \refersec{app:typesignatureexample2flattenedbytestream}.
979
980 \subsubsection{Type signature example 2: flattenedbytestream}
981 \label{app:typesignatureexample2flattenedbytestream}
982 % DWARF4 had a \livelink{chap:DWATnamespace}{DW_AT_namespace} below, 
983 % but this error is fixed here to be \livelink{chap:DWTAGnamespace}{DW_TAG_namespace}.
984 \begin{alltt}
985 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
986 0x43 0x39 0x4e 0x00
987 // Step 3: 'D' \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
988 0x44 0x02
989 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "A"
990 0x41 0x03 0x08 0x41 0x00
991 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 20
992 0x41 0x0b 0x0d 0x14
993 // Step 7: First child ("v\_")
994     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
995     0x44 0x0d
996     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "v\_"
997     0x41 0x03 0x08 0x76 0x5f 0x00
998     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
999     0x41 0x32 0x0d 0x03
1000     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
1001     0x41 0x38 0x0d 0x00
1002     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1003     0x54 0x49
1004         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
1005         0x44 0x24
1006         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "int"
1007         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
1008         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1009         0x41 0x0b 0x0d 0x04
1010         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
1011         0x41 0x3e 0x0d 0x05
1012         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
1013         0x00
1014     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "v\_"
1015     0x00
1016 // Step 7: Second child ("next")
1017     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1018     0x44 0x0d
1019     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "next"
1020     0x41 0x03 0x08 0x6e 0x65 0x78 0x74 0x00
1021     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1022     0x41 0x32 0x0d 0x03
1023     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1024     0x41 0x38 0x0d 0x04
1025     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#3)
1026     0x54 0x49
1027         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1028         0x44 0x0f
1029         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
1030         0x4e 0x49
1031         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
1032         0x43 0x39 0x4e 0x00 0x45
1033         // Step 5: "A"
1034         0x41 0x00
1035         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1036         0x00
1037     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1038     0x00
1039 // Step 7: Third child ("bp")
1040     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1041     0x44 0x0d
1042     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "bp"
1043     0x41 0x03 0x08 0x62 0x70 0x00
1044     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1045     0x41 0x32 0x0d 0x03
1046     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
1047     0x41 0x38 0x0d 0x08
1048     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#4)
1049     0x54 0x49
1050         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1051 0x44 0x0f
1052         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
1053         0x4e 0x49
1054         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
1055         0x43 0x39 0x4e 0x00 0x45
1056         // Step 5: "B"
1057         0x42 0x00
1058         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1059         0x00
1060     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1061     0x00
1062 // Step 7: Fourth child ("c")
1063     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1064     0x44 0x0d
1065     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "c"
1066     0x41 0x03 0x08 0x63 0x00
1067     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1068     0x41 0x32 0x0d 0x03
1069     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 12
1070     0x41 0x38 0x0d 0x0c
1071     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#5)
1072     0x54 0x49
1073         // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
1074         0x43 0x39 0x4e 0x00
1075         // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
1076         0x44 0x13
1077         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "C"
1078         0x41 0x03 0x08 0x43 0x00
1079         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
1080         0x41 0x0b 0x0d 0x08
1081         // Step 7: First child ("x")
1082             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1083             0x44 0x0d
1084             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "x"
1085             0x41 0x03 0x08 0x78 0x00
1086             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
1087             0x41 0x38 0x0d 0x00
1088             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1089             0x52 0x49 0x02
1090             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
1091             0x00
1092         // Step 7: Second child ("y")
1093             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1094             0x44 0x0d
1095             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "y"
1096             0x41 0x03 0x08 0x79 0x00
1097             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1098             0x41 0x38 0x0d 0x04
1099             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1100             0x52 0x49 0x02
1101             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
1102             0x00
1103         // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
1104         0x00
1105     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "c"
1106     0x00
1107 // Step 7: Fifth child ("A")
1108     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "A"
1109     0x53 0x2e 0x41 0x00
1110 // Step 7: Sixth child ("v")
1111     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "v"
1112     0x53 0x2e 0x76 0x00
1113 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "A"
1114 0x00
1115 \end{alltt}
1116
1117 Running an MD5 hash over this byte stream, and taking the
1118 low-order 64 bits, yields the final signature: 0xd6d160f5
1119 5589f6e9.
1120
1121
1122 A source file that includes this header file may declare a
1123 variable of type N::A, and its DWARF information may look
1124 that shown in 
1125 Section \refersec{app:typesignatureexampleusage}.
1126
1127
1128 \subsubsection{Type signature example usage}
1129 \label{app:typesignatureexampleusage}
1130
1131 \begin{alltt}
1132   \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
1133   ...
1134   \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
1135     ...
1136     \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
1137       \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "a"
1138       \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : (signature) 0xd6d160f5 5589f6e9
1139       \livelink{chap:DWATlocation}{DW\-\_AT\-\_location} : ...
1140     ...
1141 \end{alltt}
1142
1143 \subsection{Type Signature Computation Grammar}
1144 \label{app:typesignaturecomputationgrammar}
1145
1146 This section
1147 presents a semi-formal grammar that may aid in understanding
1148 how the bytes of the flattened type description are formed
1149 during the type signature computation algorithm of Section
1150 Section \refersec{datarep:typesignaturecomputation}. 
1151
1152 %FIXME: The index entries here with \addtoindexx are ineffective.
1153 \begin{alltt}
1154 signature
1155     : opt-context debug-entry attributes children
1156
1157 opt-context           // Step 2
1158     : 'C' tag-code string opt-context
1159     : empty
1160
1161 debug-entry           // Step 3
1162     : 'D' tag-code
1163
1164 attributes            // Steps 4, 5, 6
1165     : attribute attributes
1166     : empty
1167
1168 attribute
1169     : 'A' at-code form-encoded-value     // Normal attributes
1170     : 'N' at-code opt-context 'E' string // Reference to type
1171                                          // by name
1172     : 'R' at-code back-ref               // Back-reference 
1173                                          // to visited type
1174     : 'T' at-code signature              // Recursive type
1175 children             //  Step 7
1176     : child children
1177     : '\\0'
1178
1179 child
1180     : 'S' tag-code string
1181     : signature
1182 tag-code
1183     : <ULEB128>
1184 at-code
1185     : <ULEB128>
1186 form-encoded-value
1187     : \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} value \addtoindexx{constant class}
1188     : \livelink{chap:DWFORMflag}{DW\-\_FORM\-\_flag} value \addtoindexx{flag class}
1189     : \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} string \addtoindexx{string class}
1190     : \livelink{chap:DWFORMblock}{DW\-\_FORM\-\_block} \nolink{block} \addtoindexx{block class}
1191 \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} \addtoindexx{string class}
1192     : '\\x08'
1193 \livelink{chap:DWFORMblock}{DW\-\_FORM\-\_block}  \addtoindexx{block class}
1194     : '\\x09'
1195 \livelink{chap:DWFORMflag}{DW\-\_FORM\-\_flag} \addtoindexx{flag class}
1196     : '\\x0c'
1197 \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \addtoindexx{constant class}
1198     : '\\x0d'
1199 value
1200     : <SLEB128>
1201 \nolink{block}
1202     : <ULEB128> <fixed-length-block>
1203                       // The ULEB128 gives the length of the \nolink{block}
1204 back-ref
1205     : <ULEB128>
1206 string
1207     : <null-terminated-string>
1208 empty
1209     :
1210 \end{alltt}
1211
1212
1213 \section{Summary of Compression Techniques}
1214 \label{app:summaryofcompressiontechniques}
1215 \subsection{\#include compression}
1216 \label{app:includecompression}
1217
1218 \addtoindex{C++} has a much greater 
1219 problem than 
1220 \addtoindex{C} with the number and
1221 size of the headers included and the amount of data in each,
1222 but even with \addtoindex{C} 
1223 there is substantial header file information
1224 duplication.
1225
1226 A reasonable approach is to put each header file in its own
1227 section group, using the naming rules mentioned above. The
1228 section groups are marked to ensure duplicate removal.
1229
1230 All data instances and code instances (even if they came
1231 from the header files above) are put into non-section group
1232 sections such as the base object file 
1233 \addtoindex{.debug\_info} section.
1234
1235 \subsection{Eliminating function duplication}
1236 \label{app:eliminatingfunctionduplication}
1237
1238
1239 Function templates (C++) result in code for the same template
1240 instantiation being compiled into multiple archives or
1241 relocatable objects. The linker wants to keep only one of a
1242 given entity. The DWARF description, and everything else for
1243 this function, should be reduced to just a single copy.
1244
1245 For each such code group (function template in this example)
1246 the compiler assigns a name for the group which will match
1247 all other instantiations of this function but match nothing
1248 else. The section groups are marked to ensure duplicate
1249 removal, so that the second and subsequent definitions seen
1250 by the static linker are simply discarded.
1251
1252
1253 References to other 
1254 \addtoindex{.debug\_info} sections follow the approach
1255 suggested above, but the naming rule might be slightly
1256 different in that the 
1257 \begin{alltt}
1258 <file-designator> 
1259 \end{alltt}
1260 should be interpreted
1261 as a 
1262 \begin{alltt}
1263 <function-designator>.
1264 \end{alltt}
1265
1266
1267
1268 \subsection{Single-function-per-DWARF-compilation-unit}
1269 \label{app:singlefunctionperdwarfcompilationunit}
1270
1271 Section groups can help make it easy for a linker to completely
1272 remove unused functions.
1273
1274 Such section groups are not marked for duplicate removal,
1275 since the functions are not duplicates of anything.
1276
1277 Each function is given a compilation unit and a section
1278 group. Each such compilation unit is complete, with its own
1279 text, data, and DWARF sections.
1280
1281 There will also be a compilation unit that has the file\dash level
1282 declarations and definitions. Other per\dash function compilation
1283 unit DWARF information (
1284 \addtoindex{.debug\_info}) points to this common
1285 file\dash level compilation unit using \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}.
1286
1287 Section groups can use \livelink{chap:DWFORMrefaddr}{DW\-\_FORM\-\_ref\-\_addr} and internal labels
1288 (section\dash relative relocations) to refer to the main object
1289 file sections, as the section groups here are either deleted
1290 as unused or kept. There is no possibility (aside from error)
1291 of a group from some other compilation being used in place
1292 of one of these groups.
1293
1294
1295 \subsection{Inlining and out-of-line-instances}
1296 \label{app:inliningandoutoflineinstances}
1297
1298 Abstract instances
1299 \addtoindexx{abstract instance}
1300 \addtoindexx{concrete out-of-line instance}
1301 and concrete-out-of-line instances may be
1302 put in distinct compilation units using section groups. This
1303 makes possible some useful duplicate DWARF elimination.
1304
1305 \textit{No special provision for eliminating class duplication
1306 resulting from template instantiation is made here, though
1307 nothing prevents eliminating such duplicates using section
1308 groups.}
1309
1310
1311 \subsection{Separate Type Units}
1312 \label{app:separatetypeunits}
1313
1314 Each complete declaration of a globally-visible type can be
1315 placed in its own separate type section, with a group key
1316 derived from the type signature. The linker can then remove
1317 all duplicate type declarations based on the key.
1318