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