Complete work on live links, cleanup some indexing and redo pagination.
[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 \needlines{5}
769 As discussed in the previous section 
770 (Section \refersec{app:usingcompilationunits}), 
771 many
772 linkers today support the concept of a COMDAT group or
773 linkonce section. The general idea is that a ``key'' can be
774 attached to a section or a group of sections, and the linker
775 will include only one copy of a \addtoindex{section group}
776 (or individual section) for any given key. 
777 For 
778 \dotdebugtypes{} sections, the
779 key is the \addtoindex{type signature}
780 formed from the algorithm given in
781 Section \refersec{datarep:typesignaturecomputation}.
782
783 \subsection{Signature Computation Example}
784 \label{app:signaturecomputationexample}
785
786 As an example, 
787 \addtoindexx{type signature!example computation}
788 consider a \addtoindex{C++} header file 
789 containing the type definitions shown
790 in Figure \refersec{fig:typesignatureexamplescsource}.
791
792 \begin{figure}[h]
793 \begin{lstlisting}
794 namespace N {
795
796     struct B;
797
798     struct C {
799         int x;
800         int y;
801     };
802
803     class A {
804     public:
805         A(int v);
806         int v();
807     private:
808         int v_;
809         struct A *next;
810         struct B *bp;
811         struct C c;
812     };
813 }
814 \end{lstlisting}
815 \caption{Type signature examples: C++ source}
816 \label{fig:typesignatureexamplescsource}
817 \end{figure}
818
819 Next, consider one possible representation of the DWARF
820 information that describes the type \doublequote{struct C} as shown
821 in 
822 \refersec{fig:typesignaturecomputation1dwarfrepresentation}:
823
824 \begin{figure}
825 \begin{dwflisting}
826 % We keep the : (colon) away from the attribute so tokenizing in the python tools
827 % does not result in adding : into the attribute name.
828 \begin{alltt}
829   \livelink{chap:DWTAGtypeunit}{DW\_TAG\_type\_unit}
830       \livelink{chap:DWATlanguage}{DW\_AT\_language} : \livelink{chap:DWLANGCplusplus}{DW\_LANG\_C\_plus\_plus} (4)
831     \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace}
832         \livelink{chap:DWATname}{DW\_AT\_name} : "N"
833 L1:
834       \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type}
835           \livelink{chap:DWATname}{DW\_AT\_name} : "C"
836           \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} : 8
837           \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
838           \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 5
839         \livelink{chap:DWTAGmember}{DW\_TAG\_member}
840             \livelink{chap:DWATname}{DW\_AT\_name} : "x"
841             \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
842             \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 6
843             \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L2
844             \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 0
845         \livelink{chap:DWTAGmember}{DW\_TAG\_member}
846             \livelink{chap:DWATname}{DW\_AT\_name} : "y"
847             \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
848             \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 7
849             \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L2
850             \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 4
851 L2:
852      \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type}
853          \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} : 4
854          \livelink{chap:DWATencoding}{DW\_AT\_encoding} : \livelink{chap:DWATEsigned}{DW\_ATE\_signed}
855          \livelink{chap:DWATname}{DW\_AT\_name} : "int"
856 \end{alltt}
857 \end{dwflisting}
858 \caption{Type signature computation \#1: DWARF representation}
859 \label{fig:typesignaturecomputation1dwarfrepresentation}
860 \end{figure}
861
862 \needlines{3}
863 In computing a signature for the type \texttt{N::C}, flatten the type
864 \addtoindexx{type signature}
865 description into a byte stream according to the procedure
866 outlined in 
867 Section \refersec{datarep:typesignaturecomputation}.
868 The result is shown in 
869 Figure \refersec{fig:typesignaturecomputation1flattenedbytestream}.
870
871 \begin{figure}
872 \begin{dwflisting}
873 \begin{alltt}
874 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace} "N"
875 0x43 0x39 0x4e 0x00
876 // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type}
877 0x44 0x13
878 // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "C"
879 0x41 0x03 0x08 0x43 0x00
880 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 8
881 0x41 0x0b 0x0d 0x08
882 // Step 7: First child ("x")
883     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
884     0x44 0x0d
885     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "x"
886     0x41 0x03 0x08 0x78 0x00
887     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 0
888     0x41 0x38 0x0d 0x00
889     // Step 6: 'T' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#2)
890     0x54 0x49
891         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type}
892         0x44 0x24
893         // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "int"
894         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
895         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 4
896         0x41 0x0b 0x0d 0x04
897         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\_AT\_encoding} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWATEsigned}{DW\_ATE\_signed}
898         0x41 0x3e 0x0d 0x05
899         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type} "int"
900         0x00
901     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "x"
902     0x00
903 // Step 7: Second child ("y")
904     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
905     0x44 0x0d
906     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "y"
907     0x41 0x03 0x08 0x78 0x00
908     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 4
909     0x41 0x38 0x0d 0x04
910     // Step 6: 'R' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#2)
911     0x52 0x49 0x02
912     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "y"
913     0x00
914 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type} "C"
915 0x00
916 \end{alltt}
917 \end{dwflisting}
918 \caption{Type signature computation \#1: flattened byte stream}
919 \label{fig:typesignaturecomputation1flattenedbytestream}
920 \end{figure}
921
922 \needlines{4}
923 Running an \addtoindex{MD5 hash} over this byte stream, and taking the
924 low\dash order 64 bits, yields the final signature: 
925 0xd28081e8 dcf5070a.
926
927 Next, consider a representation of the DWARF information that
928 describes the type ``class A'' as shown in 
929 Figure \refersec{fig:typesignaturecomputation2dwarfrepresentation}.
930
931 \begin{figure}
932 \figurepart{1}{2}
933 \begin{dwflisting}
934 \begin{alltt}
935   \livelink{chap:DWTAGtypeunit}{DW\_TAG\_type\_unit}
936       \livelink{chap:DWATlanguage}{DW\_AT\_language} : \livelink{chap:DWLANGCplusplus}{DW\_LANG\_C\_plus\_plus} (4)
937     \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace}
938         \livelink{chap:DWATname}{DW\_AT\_name} : "N"
939 L1:
940         \livelink{chap:DWTAGclasstype}{DW\_TAG\_class\_type}
941              \livelink{chap:DWATname}{DW\_AT\_name} : "A"
942              \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} : 20
943              \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
944              \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 10
945            \livelink{chap:DWTAGmember}{DW\_TAG\_member}
946                 \livelink{chap:DWATname}{DW\_AT\_name} : "v\_"
947                 \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
948                 \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 15
949                 \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L2
950                 \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 0
951                 \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
952           \livelink{chap:DWTAGmember}{DW\_TAG\_member}
953                \livelink{chap:DWATname}{DW\_AT\_name} : "next"
954                \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
955                \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 16
956                \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L3
957                \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 4
958                \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
959           \livelink{chap:DWTAGmember}{DW\_TAG\_member}
960                \livelink{chap:DWATname}{DW\_AT\_name} : "bp"
961                \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
962                \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 17
963                \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L4
964                \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 8
965                \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
966           \livelink{chap:DWTAGmember}{DW\_TAG\_member}
967                \livelink{chap:DWATname}{DW\_AT\_name} : "c"
968                \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
969                \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 18
970                \livelink{chap:DWATtype}{DW\_AT\_type} : 0xd28081e8 dcf5070a (signature for struct C)
971                \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} : 12
972                \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
973 \end{alltt}
974 \end{dwflisting}
975 \caption{Type signature computation \#2: DWARF representation}
976 \label{fig:typesignaturecomputation2dwarfrepresentation}
977 \end{figure}
978
979 \begin{figure}
980 \figurepart{2}{2}
981 \begin{dwflisting}
982 \begin{alltt}
983       \livelink{chap:DWTAGsubprogram}{DW\_TAG\_subprogram}
984            \livelink{chap:DWATexternal}{DW\_AT\_external} : 1
985            \livelink{chap:DWATname}{DW\_AT\_name} : "A"
986            \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
987            \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 12
988            \livelink{chap:DWATdeclaration}{DW\_AT\_declaration} : 1
989         \livelink{chap:DWTAGformalparameter}{DW\_TAG\_formal\_parameter}
990            \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L3
991            \livelink{chap:DWATartificial}{DW\_AT\_artificial} : 1
992         \livelink{chap:DWTAGformalparameter}{DW\_TAG\_formal\_parameter}
993            \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L2
994        \livelink{chap:DWTAGsubprogram}{DW\_TAG\_subprogram}
995            \livelink{chap:DWATexternal}{DW\_AT\_external} : 1
996            \livelink{chap:DWATname}{DW\_AT\_name} : "v"
997            \livelink{chap:DWATdeclfile}{DW\_AT\_decl\_file} : 1
998            \livelink{chap:DWATdeclline}{DW\_AT\_decl\_line} : 13
999            \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L2
1000            \livelink{chap:DWATdeclaration}{DW\_AT\_declaration} : 1
1001          \livelink{chap:DWTAGformalparameter}{DW\_TAG\_formal\_parameter}
1002            \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L3
1003            \livelink{chap:DWATartificial}{DW\_AT\_artificial} : 1
1004 L2:
1005     \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type}
1006          \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} : 4
1007          \livelink{chap:DWATencoding}{DW\_AT\_encoding} : \livelink{chap:DWATEsigned}{DW\_ATE\_signed}
1008          \livelink{chap:DWATname}{DW\_AT\_name} : "int"
1009 L3:
1010     \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1011          \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L1
1012 L4:
1013     \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1014          \livelink{chap:DWATtype}{DW\_AT\_type} : reference to L5
1015     \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace}
1016          \livelink{chap:DWATname}{DW\_AT\_name} : "N"
1017 L5:
1018        \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type}
1019            \livelink{chap:DWATname}{DW\_AT\_name} : "B"
1020            \livelink{chap:DWATdeclaration}{DW\_AT\_declaration} : 1
1021 \end{alltt}
1022 \end{dwflisting}
1023 \begin{center}
1024 Figure~\ref{fig:typesignaturecomputation2dwarfrepresentation} Type signature computation \#2: DWARF representation \textit{(concluded)}
1025 \end{center}
1026 \end{figure}
1027
1028 In this example, the structure types \texttt{N::A} and \texttt{N::C} have each
1029 been placed in separate 
1030 \addtoindexx{type unit}
1031 type units.  For \texttt{N::A}, the actual
1032 definition of the type begins at label L1. The definition
1033 involves references to the int base type and to two pointer
1034 types. The information for each of these referenced types is
1035 also included in this \addtoindex{type unit}, 
1036 since base types and pointer
1037 types are trivial types that are not worth the overhead of a
1038 separate \addtoindex{type unit}. 
1039 The last pointer type contains a reference
1040 to an incomplete type \texttt{N::B}, which is also included here as
1041 a declaration, since the complete type is unknown and its
1042 signature is therefore unavailable. There is also a reference
1043 to \texttt{N::C}, using 
1044 \livelink{chap:DWFORMrefsig8}{DW\_FORM\_ref\_sig8} to 
1045 refer to the type signature
1046 \addtoindexx{type signature}
1047 for that type.
1048
1049 In computing a signature for the type \texttt{N::A}, flatten the type
1050 description into a byte stream according to the procedure
1051 outlined in 
1052 Section \refersec{datarep:typesignaturecomputation}.
1053 The result is shown in 
1054 Figure \refersec{fig:typesignatureexample2flattenedbytestream}.
1055
1056 \begin{figure}
1057 \figurepart{1}{3}
1058 \begin{dwflisting}
1059 % DWARF4 had a \livelink{chap:DWATnamespace}{DW\_AT\_namespace} below, 
1060 % but this error is fixed here to be \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace}.
1061 \begin{alltt}
1062 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace} "N"
1063 0x43 0x39 0x4e 0x00
1064 // Step 3: 'D' \livelink{chap:DWTAGclasstype}{DW\_TAG\_class\_type}
1065 0x44 0x02
1066 // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "A"
1067 0x41 0x03 0x08 0x41 0x00
1068 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 20
1069 0x41 0x0b 0x0d 0x14
1070 // Step 7: First child ("v\_")
1071     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1072     0x44 0x0d
1073     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "v\_"
1074     0x41 0x03 0x08 0x76 0x5f 0x00
1075     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
1076     0x41 0x32 0x0d 0x03
1077     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 0
1078     0x41 0x38 0x0d 0x00
1079     // Step 6: 'T' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#2)
1080     0x54 0x49
1081         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type}
1082         0x44 0x24
1083         // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "int"
1084         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
1085         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 4
1086         0x41 0x0b 0x0d 0x04
1087         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\_AT\_encoding} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWATEsigned}{DW\_ATE\_signed}
1088         0x41 0x3e 0x0d 0x05
1089         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\_TAG\_base\_type} "int"
1090         0x00
1091     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "v\_"
1092     0x00
1093 // Step 7: Second child ("next")
1094     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1095     0x44 0x0d
1096     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "next"
1097     0x41 0x03 0x08 0x6e 0x65 0x78 0x74 0x00
1098     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
1099     0x41 0x32 0x0d 0x03
1100     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 4
1101     0x41 0x38 0x0d 0x04
1102 \end{alltt}
1103 \end{dwflisting}
1104 \caption{Type signature example \#2: flattened byte stream}
1105 \label{fig:typesignatureexample2flattenedbytestream}
1106 \end{figure}
1107
1108 \begin{figure}
1109 \figurepart{2}{3}
1110 \begin{dwflisting}
1111 \begin{alltt}    
1112     // Step 6: 'T' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#3)
1113     0x54 0x49
1114         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1115         0x44 0x0f
1116         // Step 5: 'N' \livelink{chap:DWATtype}{DW\_AT\_type}
1117         0x4e 0x49
1118         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace} "N" 'E'
1119         0x43 0x39 0x4e 0x00 0x45
1120         // Step 5: "A"
1121         0x41 0x00
1122         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1123         0x00
1124     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "next"
1125     0x00
1126 // Step 7: Third child ("bp")
1127     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1128     0x44 0x0d
1129     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "bp"
1130     0x41 0x03 0x08 0x62 0x70 0x00
1131     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
1132     0x41 0x32 0x0d 0x03
1133     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 8
1134     0x41 0x38 0x0d 0x08
1135     // Step 6: 'T' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#4)
1136     0x54 0x49
1137         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1138 0x44 0x0f
1139         // Step 5: 'N' \livelink{chap:DWATtype}{DW\_AT\_type}
1140         0x4e 0x49
1141         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace} "N" 'E'
1142         0x43 0x39 0x4e 0x00 0x45
1143         // Step 5: "B"
1144         0x42 0x00
1145         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\_TAG\_pointer\_type}
1146         0x00
1147     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "next"
1148     0x00
1149 // Step 7: Fourth child ("c")
1150     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1151     0x44 0x0d
1152     // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "c"
1153     0x41 0x03 0x08 0x63 0x00
1154     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\_AT\_accessibility} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \livelink{chap:DWACCESSprivate}{DW\_ACCESS\_private}
1155     0x41 0x32 0x0d 0x03
1156 \end{alltt}
1157 \end{dwflisting}
1158 \begin{center}
1159 Figure~\ref{fig:typesignatureexample2flattenedbytestream} Type signature example \#2: flattened byte stream \textit{(continued)}
1160 \end{center}
1161 \end{figure}
1162     
1163 \begin{figure}
1164 \figurepart{3}{3}
1165 \begin{dwflisting}
1166 \begin{alltt}
1167     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 12
1168     0x41 0x38 0x0d 0x0c
1169     // Step 6: 'T' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#5)
1170     0x54 0x49
1171         // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\_TAG\_namespace} "N"
1172         0x43 0x39 0x4e 0x00
1173         // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type}
1174         0x44 0x13
1175         // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "C"
1176         0x41 0x03 0x08 0x43 0x00
1177         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\_AT\_byte\_size} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 8
1178         0x41 0x0b 0x0d 0x08
1179         // Step 7: First child ("x")
1180             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1181             0x44 0x0d
1182             // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "x"
1183             0x41 0x03 0x08 0x78 0x00
1184             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 0
1185             0x41 0x38 0x0d 0x00
1186             // Step 6: 'R' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#2)
1187             0x52 0x49 0x02
1188             // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "x"
1189             0x00
1190         // Step 7: Second child ("y")
1191             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\_TAG\_member}
1192             0x44 0x0d
1193             // Step 4: 'A' \livelink{chap:DWATname}{DW\_AT\_name} \livelink{chap:DWFORMstring}{DW\_FORM\_string} "y"
1194             0x41 0x03 0x08 0x79 0x00
1195             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\_AT\_data\_member\_location} \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} 4
1196             0x41 0x38 0x0d 0x04
1197             // Step 6: 'R' \livelink{chap:DWATtype}{DW\_AT\_type} (type \#2)
1198             0x52 0x49 0x02
1199             // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "y"
1200             0x00
1201         // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type} "C"
1202         0x00
1203     // Step 7: End of \livelink{chap:DWTAGmember}{DW\_TAG\_member} "c"
1204     0x00
1205 // Step 7: Fifth child ("A")
1206     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\_TAG\_subprogram} "A"
1207     0x53 0x2e 0x41 0x00
1208 // Step 7: Sixth child ("v")
1209     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\_TAG\_subprogram} "v"
1210     0x53 0x2e 0x76 0x00
1211 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\_TAG\_structure\_type} "A"
1212 0x00
1213 \end{alltt}
1214 \end{dwflisting}
1215 \begin{center}
1216 Figure~\ref{fig:typesignatureexample2flattenedbytestream} Type signature example \#2: flattened byte stream \textit{(concluded)}
1217 \end{center}
1218 \end{figure}
1219
1220 Running an \addtoindex{MD5 hash} over this byte stream, and taking the
1221 low-order 64 bits, yields the final signature: 0xd6d160f5
1222 5589f6e9.
1223
1224
1225 A source file that includes this header file may declare a
1226 variable of type \texttt{N::A}, and its DWARF information may look
1227 like that shown in 
1228 Figure \refersec{fig:typesignatureexampleusage}.
1229
1230 \begin{figure}
1231 \begin{dwflisting}
1232 \begin{alltt}
1233   \livelink{chap:DWTAGcompileunit}{DW\_TAG\_compile\_unit}
1234   ...
1235   \livelink{chap:DWTAGsubprogram}{DW\_TAG\_subprogram}
1236     ...
1237     \livelink{chap:DWTAGvariable}{DW\_TAG\_variable}
1238       \livelink{chap:DWATname}{DW\_AT\_name} : "a"
1239       \livelink{chap:DWATtype}{DW\_AT\_type} : (signature) 0xd6d160f5 5589f6e9
1240       \livelink{chap:DWATlocation}{DW\_AT\_location} : ...
1241     ...
1242 \end{alltt}
1243 \end{dwflisting}
1244 \caption{Type signature example usage}
1245 \label{fig:typesignatureexampleusage}
1246 \end{figure}
1247
1248 \subsection{Type Signature Computation Grammar}
1249 \label{app:typesignaturecomputationgrammar}
1250
1251 Figure \refersec{fig:typesignaturecomputationgrammar}
1252 \addtoindexx{type signature!computation grammar}
1253 presents a semi-formal grammar that may aid in understanding
1254 how the bytes of the flattened type description are formed
1255 during the type signature computation algorithm of
1256 Section \refersec{datarep:typesignaturecomputation}. 
1257
1258 \begin{figure}[h]
1259 \begin{dwflisting}
1260 %FIXME: The index entries here with \addtoindexx are ineffective.
1261 \begin{alltt}
1262 signature
1263     : opt-context debug-entry attributes children
1264 opt-context               // Step 2
1265     : 'C' tag-code string opt-context
1266     : empty
1267 debug-entry               // Step 3
1268     : 'D' tag-code
1269 attributes                // Steps 4, 5, 6
1270     : attribute attributes
1271     : empty
1272 attribute
1273     : 'A' at-code form-encoded-value     // Normal attributes
1274     : 'N' at-code opt-context 'E' string // Reference to type by name
1275     : 'R' at-code back-ref               // Back-reference to visited type
1276     : 'T' at-code signature              // Recursive type
1277 children                 //  Step 7
1278     : child children
1279     : '0'
1280 child
1281     : 'S' tag-code string
1282     : signature
1283 tag-code
1284     : <ULEB128>
1285 at-code
1286     : <ULEB128>
1287 form-encoded-value
1288     : \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} value \addtoindexx{constant class}
1289     : \livelink{chap:DWFORMflag}{DW\_FORM\_flag} value \addtoindexx{flag class}
1290     : \livelink{chap:DWFORMstring}{DW\_FORM\_string} string \addtoindexx{string class}
1291     : \livelink{chap:DWFORMblock}{DW\_FORM\_block} \nolink{block} \addtoindexx{block class}
1292 \livelink{chap:DWFORMstring}{DW\_FORM\_string} \addtoindexx{string class}
1293     : 'x08'
1294 \livelink{chap:DWFORMblock}{DW\_FORM\_block}  \addtoindexx{block class}
1295     : 'x09'
1296 \livelink{chap:DWFORMflag}{DW\_FORM\_flag} \addtoindexx{flag class}
1297     : 'x0c'
1298 \livelink{chap:DWFORMsdata}{DW\_FORM\_sdata} \addtoindexx{constant class}
1299     : 'x0d'
1300 value
1301     : <SLEB128>
1302 \nolink{block}
1303     : <ULEB128> <fixed-length-block> // The ULEB128 gives the length of the \nolink{block}
1304 back-ref
1305     : <ULEB128>
1306 string
1307     : <null-terminated-string>
1308 empty
1309     :
1310 \end{alltt}
1311 \end{dwflisting}
1312 \caption{Type signature computation grammar}
1313 \label{fig:typesignaturecomputationgrammar}
1314 \end{figure}
1315
1316 \section{Summary of Compression Techniques}
1317 \label{app:summaryofcompressiontechniques}
1318 \subsection{\#include compression}
1319 \label{app:includecompression}
1320
1321 \addtoindex{C++} has a much greater 
1322 problem than 
1323 \addtoindex{C} with the number and
1324 size of the headers included and the amount of data in each,
1325 but even with \addtoindex{C} 
1326 there is substantial header file information
1327 duplication.
1328
1329 A reasonable approach is to put each header file in its own
1330 \addtoindex{section group}, using the naming rules mentioned above. The
1331 section groups are marked to ensure duplicate removal.
1332
1333 All data instances and code instances (even if they came
1334 from the header files above) are put 
1335 \addtoindexx{section group}
1336 into non-section group
1337 sections such as the base object file 
1338 \dotdebuginfo{} section.
1339
1340 \subsection{Eliminating function duplication}
1341 \label{app:eliminatingfunctionduplication}
1342
1343
1344 Function templates (C++) result in code for the same template
1345 instantiation being compiled into multiple archives or
1346 relocatable objects. The linker wants to keep only one of a
1347 given entity. The DWARF description, and everything else for
1348 this function, should be reduced to just a single copy.
1349
1350 \needlines{5}
1351 For each such code group (function template in this example)
1352 the compiler assigns a name for the group which will match
1353 all other instantiations of this function but match nothing
1354 else. 
1355 The 
1356 \addtoindexx{section group}
1357 section groups are marked to ensure duplicate
1358 removal, so that the second and subsequent definitions seen
1359 by the static linker are simply discarded.
1360
1361
1362 References to other 
1363 \dotdebuginfo{} sections follow the approach
1364 suggested above, but the naming rule is slightly
1365 different in that the \texttt{\textless file-designator\textgreater} 
1366 should be interpreted as a \texttt{\textless file-designator\textgreater}.
1367
1368
1369
1370 \subsection{Single-function-per-DWARF-compilation-unit}
1371 \label{app:singlefunctionperdwarfcompilationunit}
1372
1373 Section groups can help make it easy for a linker to completely
1374 remove unused functions.
1375
1376 Such 
1377 \addtoindexx{section group}
1378 section groups are not marked for duplicate removal,
1379 since the functions are not duplicates of anything.
1380
1381 Each function is given a compilation unit and a section
1382 group. Each such compilation unit is complete, with its own
1383 text, data, and DWARF sections.
1384
1385 There will also be a compilation unit that has the file\dash level
1386 declarations and definitions. Other per\dash function compilation
1387 unit DWARF information (\dotdebuginfo{}) points to this common
1388 file\dash level compilation unit using 
1389 \livelink{chap:DWTAGimportedunit}{DW\_TAG\_imported\_unit}.
1390
1391 Section groups can use \livelink{chap:DWFORMrefaddr}{DW\_FORM\_ref\_addr} and internal labels
1392 (section\dash relative relocations) to refer to the main object
1393 file sections, as the 
1394 \addtoindexx{section group}
1395 section groups here are either deleted
1396 as unused or kept. There is no possibility (aside from error)
1397 of a group from some other compilation being used in place
1398 of one of these groups.
1399
1400
1401 \subsection{Inlining and out-of-line-instances}
1402 \label{app:inliningandoutoflineinstances}
1403
1404 Abstract instances
1405 \addtoindexx{abstract instance}
1406 \addtoindexx{concrete out-of-line instance}
1407 and concrete-out-of-line instances may be
1408 put in distinct compilation units using 
1409 \addtoindexx{section group}
1410 section groups. 
1411 This
1412 makes possible some useful duplicate DWARF elimination.
1413
1414 \textit{No special provision for eliminating class duplication
1415 resulting from template instantiation is made here, though
1416 nothing prevents eliminating such duplicates using section
1417 groups.}
1418
1419
1420 \subsection{Separate Type Units}
1421 \label{app:separatetypeunits}
1422
1423 Each complete declaration of a globally-visible type can be
1424 \addtoindexx{type unit}
1425 placed in its own separate type section, with a group key
1426 derived from the type signature. The linker can then remove
1427 all duplicate type declarations based on the key.
1428