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