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