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