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