Change many figures to tables, lots of other fixes
[dwarf-doc.git] / dwarf5 / latexdoc / compression.tex
1 \chapter[Compression (Informative)]{DWARF Compression and Duplicate Elimination (Informative)}
2 \label{dwarfcompressionandduplicateeliminationinformative}
3
4 % It seemed difficult to get close to the same layout and 
5 % captioning as DWARF4 here with figures as they moved (floated)
6 % making it hard to follow.  Hence this uses fewer figures.
7
8 DWARF 
9 \addtoindexx{DWARF compression}
10 can 
11 \addtoindexx{DWARF duplicate elimination}
12 use a lot of disk space.
13
14 This is especially true for C++, where the depth and complexity
15 of headers can mean that many, many (possibly thousands of)
16 declarations are repeated in every compilation unit. C++
17 templates can also mean that some functions and their DWARF
18 descriptions get duplicated.
19
20 This Appendix describes techniques for using the DWARF
21 representation in combination with features and characteristics
22 of some common object file representations to reduce redundancy
23 without losing information. It is worth emphasizing that none
24 of these techniques are necessary to provide a complete and
25 accurate DWARF description; they are solely concerned with
26 reducing the size of DWARF information.
27
28 The techniques described here depend more directly and more
29 obviously on object file concepts and linker mechanisms than
30 most other parts of DWARF. While the presentation tends to
31 use the vocabulary of specific systems, this is primarily to
32 aid in describing the techniques by appealing to well\dash known
33 terminology. These techniques can be employed on any system
34 that supports certain general functional capabilities
35 (described below).
36
37
38 \section{Using Compilation Units}
39 \label{app:usingcompilationunits}
40
41 \subsection{Overview}
42 The general approach is to break up the debug information of
43 a compilation into separate normal and partial compilation
44 units, each consisting of one or more sections. By arranging
45 that a sufficiently similar partitioning occurs in other
46 compilations, a suitable system linker can delete redundant
47 groups of sections when combining object files.
48
49 \textit{The following uses some traditional section naming here
50 but aside from the DWARF sections, the names are just meant
51 to suggest traditional contents as a way of explaining the
52 approach, not to be limiting.}
53
54 A traditional relocatable object output 
55 from a single compilation might contain sections 
56 named:
57 \begin{alltt}
58     \addtoindex{.data}
59     \addtoindex{.text}
60     \addtoindex{.debug\_info}
61     \addtoindex{.debug\_abbrev}
62     \addtoindex{.debug\_line}
63     \addtoindex{.debug\_aranges}
64 \end{alltt}
65 A relocatable object from a compilation system 
66 attempting duplicate DWARF elimination might
67 contain sections as in:
68
69 \begin{alltt}
70     \addtoindex{.data}
71     \addtoindex{.text}
72     \addtoindex{.debug\_info}
73     \addtoindex{.debug\_abbrev}
74     \addtoindex{.debug\_line}
75     \addtoindex{.debug\_aranges}
76 \end{alltt}
77
78 followed (or preceded, the order is not significant) 
79 by a series of 
80 \addtoindexx{section group}
81 section groups:
82 \begin{alltt}
83 ==== Section group 1
84     \addtoindex{.debug\_info}
85     \addtoindex{.debug\_abbrev}
86     \addtoindex{.debug\_line}
87 ==== ...
88 ==== Section group N
89     \addtoindex{.debug\_info}
90     \addtoindex{.debug\_abbrev}
91     \addtoindex{.debug\_line}
92 \end{alltt}
93
94 where each \addtoindex{section group} might or might not contain executable
95 code (\textit{.text} sections) or data (\textit{.data} sections).
96
97 A \textit{\addtoindex{section group}} is a named set 
98 of section contributions
99 within an object file with the property that the entire set
100 of section contributions must be retained or discarded as a
101 whole; no partial elimination is allowed. Section groups can
102 generally be handled by a linker in two ways:
103
104 \begin{enumerate}[1.]
105 \item Given multiple identical (duplicate) section groups,
106 \addtoindexx{section group}
107 one of them is chosen to be kept and used, while the rest
108 are discarded.
109
110 \item Given a \addtoindex{section group} 
111 that is not referenced from any
112 section outside of the \addtoindex{section group}, 
113 the section group
114 is discarded.
115
116 \end{enumerate}
117
118
119 Which handling applies may be indicated by the 
120 \addtoindex{section group}
121 itself and/or selection of certain linker options.
122
123 For example, if a linker determines that 
124 \addtoindex{section group} 1
125 from A.o and 
126 \addtoindex{section group} 3 from B.o are identical, it could
127 discard one group and arrange that all references in A.o and
128 B.o apply to the remaining one of the two identical section
129 groups. This saves space.
130
131 An important part of making it possible to “redirect”
132 references to the surviving 
133 \addtoindex{section group} is the use of
134 consistently chosen linker global symbols for referring to
135 locations within each 
136 \addtoindex{section group}.
137 It follows that references
138 are simply to external names and the linker already knows
139 how to match up references and definitions.
140
141 What is minimally needed from the object file format and system
142 linker (outside of DWARF itself, and normal object/linker
143 facilities such as simple relocations) are:
144
145 \begin{enumerate}[1.]
146
147 \item A means of referencing from inside one \addtoindex{.debug\_info}
148 compilation unit to another 
149 \addtoindex{.debug\_info} 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, \addtoindex{.debug\_info}, 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{app:duplicateeliminationexample1csource}
194 through 
195 Figure \ref{app: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 \textit{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 \addtoindex{.debug\_info} that
296 could be referenced from outside by 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 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 % This should be a subsubsubsection header but that does work...
339 \textbf{Use of \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} versus 
340 \livelink{chap:DWTAGpartialunit}{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 \textbf{Use of \livelink{chap:DWTAGimportedunit}{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 \textbf{Use of \livelink{chap:DWFORMrefaddr}{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 \addtoindex{.debug\_info}
403 from another \addtoindex{.debug\_info} (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 When referencing into a 
409 \addtoindexx{section group}
410 non-section group 
411 \addtoindex{.debug\_info},
412 from another \addtoindex{.debug\_info} (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 \addtoindex{.debug\_info}
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 \addtoindex{.debug\_info}
437 (for example, \addtoindex{.debug\_line}, 
438 \addtoindex{.debug\_aranges}, or others);
439 however, only the \addtoindex{.debug\_info}
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}[t]
456 \textbf{File wa.h:}
457 \begin{lstlisting}[numbers=none]
458 struct A {
459    int i;
460 };
461 \end{lstlisting}
462 \textbf{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 \addtoindex{.debug\_info}
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 \caption{Duplicate elimination example \#1: DWARF section group} 
506 \label{fig:duplicateeliminationexample1dwarfsectiongroup}
507 \end{figure}
508
509 Figure \refersec{fig:duplicateeliminationexample1primarycompilationunit}
510 shows the ``normal'' DWARF sections, which are not part of
511 any \addtoindex{section group}, 
512 and how they make use of the information
513 in the \addtoindex{section group} shown above.
514
515 \begin{figure}
516 \begin{dwflisting}
517 \begin{alltt}
518 == section .text
519     [generated code for function f]
520 == section \addtoindex{.debug\_info}
521     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
522 .L1:                   ! local (non-linker) symbol
523         \livelink{chap:DWTAGreferencetype}{DW\-\_TAG\-\_reference\-\_type}
524             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.cpp.wa.h.123456.3)
525         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
526             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("f")
527             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.cpp.wa.h.123456.2)
528             \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
529                 \livelink{chap:DWATname}{DW\-\_AT\-\_name}("a")
530                 \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to .L1)
531         ...
532 \end{alltt}
533 \end{dwflisting}
534 \caption{Duplicate elimination example \#1: primary compilation unit} 
535 \label{fig:duplicateeliminationexample1primarycompilationunit}
536 \end{figure}
537
538 This example uses \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit} for the \addtoindex{section group},
539 implying that the contents of the compilation unit are
540 globally visible (in accordance with 
541 \addtoindex{C++} language rules).
542 \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} is not needed for the same reason.
543
544 \subsubsection{Fortran Example}
545
546
547 For a \addtoindex{Fortran}
548 \addtoindexx{DWARF duplicate elimination!Fortran example}
549 example, consider 
550 Figure \refersec{fig:duplicateeliminationexample2fortransource}.
551
552 \begin{figure}
553 \textbf{File CommonStuff.fh}
554 \addtoindexx{Fortran}
555 \begin{lstlisting}[numbers=none]
556 IMPLICIT INTEGER(A-Z)
557 COMMON /Common1/ C(100)
558 PARAMETER(SEVEN = 7)
559 \end{lstlisting}
560
561 \textbf{File Func.f}
562 \begin{lstlisting}[numbers=none]
563 FUNCTION FOO (N)
564 INCLUDE 'CommonStuff.fh'
565 FOO = C(N + SEVEN)
566 RETURN
567 END
568 \end{lstlisting}
569 \caption{Duplicate elimination example \#2: Fortran source} 
570 \label{fig:duplicateeliminationexample2fortransource}
571 \end{figure}
572
573
574 Figure \refersec{fig:duplicateeliminationexample2dwarfsectiongroup}
575 shows the \addtoindex{section group}
576 corresponding to the included file 
577 \addtoindexx{Fortran example}
578 CommonStuff.fh.
579
580 \begin{figure}
581 \begin{dwflisting}
582 \begin{alltt}
583 ==== Section group name:
584
585     my.f90.company.f90.CommonStuff.fh.654321
586
587 == section \addtoindex{.debug\_info}
588
589 DW.myf90.CommonStuff.fh.654321.1:    ! linker global symbol
590     \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit}
591         ! ...compilation unit attributes, including...
592         \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language}(\livelink{chap:DWLANGFortran90}{DW\-\_LANG\-\_Fortran90})
593         \livelink{chap:DWATidentifiercase}{DW\-\_AT\-\_identifier\-\_case}(\livelink{chap:DWIDcaseinsensitive}{DW\-\_ID\-\_case\-\_insensitive})
594
595 DW.myf90.CommonStuff.fh.654321.2: ! linker global symbol
596 3\$: \livelink{chap:DWTAGarraytype}{DW\-\_TAG\-\_array\-\_type}
597         ! unnamed
598         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
599             ! base type INTEGER
600         \livelink{chap:DWTAGsubrangetype}{DW\-\_TAG\-\_subrange\-\_type}
601             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
602                 ! base type INTEGER)
603             \livelink{chap:DWATlowerbound}{DW\-\_AT\-\_lower\-\_bound}(constant 1)
604             \livelink{chap:DWATupperbound}{DW\-\_AT\-\_upper\-\_bound}(constant 100)
605
606 DW.myf90.CommonStuff.fh.654321.3: ! linker global symbol
607     \livelink{chap:DWTAGcommonblock}{DW\-\_TAG\-\_common\-\_block}
608         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Common1")
609         \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(Address of common \nolink{block} Common1)
610         \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
611             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("C")
612             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to 3\$)
613             \livelink{chap:DWATlocation}{DW\-\_AT\-\_location}(address of C)
614
615 DW.myf90.CommonStuff.fh.654321.4: ! linker global symbol
616     \livelink{chap:DWTAGconstant}{DW\-\_TAG\-\_constant}
617         \livelink{chap:DWATname}{DW\-\_AT\-\_name}("SEVEN")
618         \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
619             ! base type INTEGER
620         \livelink{chap:DWATconstvalue}{DW\-\_AT\-\_const\-\_value}(constant 7)
621 \end{alltt}
622 \end{dwflisting}
623 \caption{Duplicate elimination example \#2: DWARF section group}
624 \label{fig:duplicateeliminationexample2dwarfsectiongroup}
625 \end{figure}
626
627 Figure \refersec{fig:duplicateeliminationexample2primaryunit}
628 shows the sections for the primary compilation unit.
629
630 \begin{figure}
631 \begin{dwflisting}
632 \begin{alltt}
633 == section .text
634     [code for function Foo]
635
636 == section \addtoindex{.debug\_info}
637     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
638         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
639             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
640             \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
641                 ! base type INTEGER
642             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
643                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
644                     DW.myf90.CommonStuff.fh.654321.1)
645             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! For Common1
646                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
647                     DW.myf90.CommonStuff.fh.654321.3)
648             \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable} ! For function result
649                 \livelink{chap:DWATname}{DW\-\_AT\-\_name}("Foo")
650                     \livelink{chap:DWATtype}{DW\-\_AT\-\_type}(reference to DW.f90.F90\$main.f.2)
651                         ! base type INTEGER
652 \end{alltt}
653 \end{dwflisting}
654 \caption{Duplicate elimination example \#2: primary unit}
655 \label{fig:duplicateeliminationexample2primaryunit}
656 \end{figure}
657
658 A companion main program is shown in 
659 Figure \refersec{fig:duplicateeliminationexample2companionsource}
660
661 \begin{figure}
662 \textbf{File Main.f:} 
663 \begin{lstlisting}[numbers=none]
664 INCLUDE 'CommonStuff.fh'
665 C(50) = 8
666 PRINT *, 'Result = ', FOO(50 - SEVEN)
667 END
668 \end{lstlisting}
669 \caption{Duplicate elimination example \#2: companion source }
670 \label{fig:duplicateeliminationexample2companionsource}
671 \end{figure}
672
673 That main program results in an object file that
674 contained a duplicate of the \addtoindex{section group} named
675 my.f90.company.f90.CommonStuff.fh.654321 
676 corresponding to the
677 included file as well as the remainder of the main subprogram
678 as shown in 
679 Figure \refersec{fig:duplicateeliminationexample2companiondwarf}.
680
681 \begin{figure}
682 \begin{dwflisting}
683 \begin{alltt}
684 == section \addtoindex{.debug\_info}
685     \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
686         \livelink{chap:DWATname}{DW\-\_AT\-\_name}(F90\$main)
687         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
688             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("INTEGER")
689             \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding}(\livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed})
690             \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size}(...)
691
692         \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
693             ...
694         ...  ! other base types
695         \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
696             \livelink{chap:DWATname}{DW\-\_AT\-\_name}("F90\$main")
697             \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
698                 \livelink{chap:DWATimport}{DW\-\_AT\-\_import}(reference to
699                     DW.myf90.CommonStuff.fh.654321.1)
700             \livelink{chap:DWTAGcommoninclusion}{DW\-\_TAG\-\_common\-\_inclusion} ! for Common1
701                 \livelink{chap:DWATcommonreference}{DW\-\_AT\-\_common\-\_reference}(reference to
702                     DW.myf90.CommonStuff.fh.654321.3)
703             ...
704 \end{alltt}
705 \end{dwflisting}
706 \caption{Duplicate elimination example \#2: companion DWARF }
707 \label{fig:duplicateeliminationexample2companiondwarf}
708 \end{figure}
709
710 This example uses \livelink{chap:DWTAGpartialunit}{DW\-\_TAG\-\_partial\-\_unit} for the \addtoindex{section group}
711 because the included declarations are not independently
712 visible as global entities.
713
714
715 \subsubsection{C Example}
716
717 The \addtoindex{C} example 
718 \addtoindexx{DWARF duplicate elimination!C example}
719 in this Section might appear to be equally
720 valid as a \addtoindex{C} example. However, it is prudent to include
721 a \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}
722 in the primary unit 
723 (see Figure \refersec{fig:duplicateeliminationexample1primarycompilationunit})
724 with an \livelink{chap:DWATimport}{DW\-\_AT\-\_import} attribute that refers to the proper unit
725 in the \addtoindex{section group}.
726
727 \textit{The \addtoindex{C} rules for consistency of global (file scope) symbols
728 across compilations are less strict than for C++; inclusion
729 of the import unit attribute assures that the declarations of
730 the proper \addtoindex{section group} are considered before declarations
731 from other compilations.}
732
733
734 \section{Using Type Units}
735 \label{app:usingtypeunits}
736
737 A large portion of debug information is type information, and
738 in a typical compilation environment, many types are duplicated
739 many times. One method of controlling the amount of duplication
740 is separating each type into a separate 
741 \addtoindex{.debug\_types} section
742 and arranging for the linker to recognize and eliminate
743 duplicates at the individual type level.
744
745 Using this technique, each substantial type definition is
746 placed in its own individual section, while the remainder
747 of the DWARF information (non-type information, incomplete
748 type declarations, and definitions of trivial types) is
749 placed in the usual debug information section. In a typical
750 implementation, the relocatable object file may contain one
751 of each of these debug sections:
752
753 \begin{alltt}
754 \addtoindex{.debug\_abbrev}
755 \addtoindex{.debug\_info}
756 \addtoindex{.debug\_line}
757 \end{alltt}
758
759 and any number of these additional sections:
760
761 \begin{alltt}
762 \addtoindex{.debug\_types}
763 \end{alltt}
764
765 As discussed in the previous section 
766 (Section \refersec{app:usingcompilationunits}), 
767 many
768 linkers today support the concept of a COMDAT group or
769 linkonce section. The general idea is that a ``key'' can be
770 attached to a section or a group of sections, and the linker
771 will include only one copy of a \addtoindex{section group}
772 (or individual section) for any given key. 
773 For 
774 \addtoindex{.debug\_types} sections, the
775 key is the \addtoindex{type signature}
776 formed from the algorithm given in
777 Section \refersec{datarep:typesignaturecomputation}.
778
779 \subsection{Signature Computation Example}
780 \label{app:signaturecomputationexample}
781
782 As an example, 
783 \addtoindexx{type signature!example computation}
784 consider a \addtoindex{C++} header file 
785 containing the type definitions shown
786 in Figure \refersec{fig:typesignatureexamplescsource}.
787
788 \begin{figure}
789 \begin{lstlisting}
790 namespace N {
791
792     struct B;
793
794     struct C {
795         int x;
796         int y;
797     };
798
799     class A {
800     public:
801         A(int v);
802         int v();
803     private:
804         int v_;
805         struct A *next;
806         struct B *bp;
807         struct C c;
808     };
809 }
810 \end{lstlisting}
811 \caption{Type signature examples: C++ source}
812 \label{fig:typesignatureexamplescsource}
813 \end{figure}
814
815 Next, consider one possible representation of the DWARF
816 information that describes the type “struct C” as shown
817 in 
818 \refersec{fig:typesignaturecomputation1dwarfrepresentation}:
819
820 \begin{figure}
821 \begin{dwflisting}
822 % We keep the : (colon) away from the attribute so tokenizing in the python tools
823 % does not result in adding : into the attribute name.
824 \begin{alltt}
825   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
826       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : \livelink{chap:DWLANGCplusplus}{DW\-\_LANG\-\_C\-\_plus\-\_plus} (4)
827     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
828         \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
829 L1:
830       \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
831           \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "C"
832           \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 8
833           \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
834           \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 5
835         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
836             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "x"
837             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
838             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 6
839             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
840             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
841         \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
842             \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "y"
843             \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
844             \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 7
845             \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
846             \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
847 L2:
848      \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
849          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
850          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
851          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
852 \end{alltt}
853 \end{dwflisting}
854 \caption{Type signature computation \#1: DWARF representation}
855 \label{fig:typesignaturecomputation1dwarfrepresentation}
856 \end{figure}
857
858 In computing a signature for the type N::C, flatten the type
859 \addtoindexx{type signature}
860 description into a byte stream according to the procedure
861 outlined in 
862 Section \refersec{datarep:typesignaturecomputation}.
863 The result is shown in 
864 Figure \refersec{fig:typesignaturecomputation1flattenedbytestream}.
865
866 \begin{figure}
867 \begin{dwflisting}
868 \begin{alltt}
869 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
870 0x43 0x39 0x4e 0x00
871 // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
872 0x44 0x13
873 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "C"
874 0x41 0x03 0x08 0x43 0x00
875 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
876 0x41 0x0b 0x0d 0x08
877 // Step 7: First child ("x")
878     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
879     0x44 0x0d
880     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "x"
881     0x41 0x03 0x08 0x78 0x00
882     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
883     0x41 0x38 0x0d 0x00
884     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
885     0x54 0x49
886         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
887         0x44 0x24
888         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "int"
889         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
890         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
891         0x41 0x0b 0x0d 0x04
892         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
893         0x41 0x3e 0x0d 0x05
894         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
895         0x00
896     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
897     0x00
898 // Step 7: Second child ("y")
899     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
900     0x44 0x0d
901     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "y"
902     0x41 0x03 0x08 0x78 0x00
903     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
904     0x41 0x38 0x0d 0x04
905     // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
906     0x52 0x49 0x02
907     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
908     0x00
909 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
910 0x00
911 \end{alltt}
912 \end{dwflisting}
913 \caption{Type signature computation \#1: flattened byte stream}
914 \label{fig:typesignaturecomputation1flattenedbytestream}
915 \end{figure}
916
917 Running an \addtoindex{MD5 hash} over this byte stream, and taking the
918 low\dash order 64 bits, yields the final signature: 
919 0xd28081e8 dcf5070a.
920
921 Next, consider a representation of the DWARF information that
922 describes the type ``class A'' as shown in 
923 Figure \refersec{fig:typesignaturecomputation2dwarfrepresentation}.
924
925 \begin{figure}
926 \figurepart{1}{2}
927 \begin{dwflisting}
928 \begin{alltt}
929   \livelink{chap:DWTAGtypeunit}{DW\-\_TAG\-\_type\-\_unit}
930       \livelink{chap:DWATlanguage}{DW\-\_AT\-\_language} : \livelink{chap:DWLANGCplusplus}{DW\-\_LANG\-\_C\-\_plus\-\_plus} (4)
931     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
932         \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
933 L1:
934         \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
935              \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
936              \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 20
937              \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
938              \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 10
939            \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
940                 \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v\_"
941                 \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
942                 \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 15
943                 \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
944                 \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 0
945                 \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
946           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
947                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "next"
948                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
949                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 16
950                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
951                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 4
952                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
953           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
954                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "bp"
955                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
956                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 17
957                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L4
958                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 8
959                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
960           \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
961                \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "c"
962                \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
963                \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 18
964                \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : 0xd28081e8 dcf5070a (signature for struct C)
965                \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} : 12
966                \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} : \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
967 \end{alltt}
968 \end{dwflisting}
969 \caption{Type signature computation \#2: DWARF representation}
970 \label{fig:typesignaturecomputation2dwarfrepresentation}
971 \end{figure}
972
973 \begin{figure}
974 \figurepart{2}{2}
975 \begin{dwflisting}
976 \begin{alltt}
977       \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
978            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
979            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "A"
980            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
981            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 12
982            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
983         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
984            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
985            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
986         \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
987            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
988        \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
989            \livelink{chap:DWATexternal}{DW\-\_AT\-\_external} : 1
990            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "v"
991            \livelink{chap:DWATdeclfile}{DW\-\_AT\-\_decl\-\_file} : 1
992            \livelink{chap:DWATdeclline}{DW\-\_AT\-\_decl\-\_line} : 13
993            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L2
994            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
995          \livelink{chap:DWTAGformalparameter}{DW\-\_TAG\-\_formal\-\_parameter}
996            \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L3
997            \livelink{chap:DWATartificial}{DW\-\_AT\-\_artificial} : 1
998 L2:
999     \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
1000          \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} : 4
1001          \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} : \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
1002          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "int"
1003 L3:
1004     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1005          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L1
1006 L4:
1007     \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1008          \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : reference to L5
1009     \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace}
1010          \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "N"
1011 L5:
1012        \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
1013            \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "B"
1014            \livelink{chap:DWATdeclaration}{DW\-\_AT\-\_declaration} : 1
1015 \end{alltt}
1016 \end{dwflisting}
1017 \begin{center}
1018 Figure~\ref{fig:typesignaturecomputation2dwarfrepresentation} Type signature computation \#2: DWARF representation \textit{(concluded)}
1019 \end{center}
1020 \end{figure}
1021
1022 In this example, the structure types N::A and N::C have each
1023 been placed in separate 
1024 \addtoindexx{type unit}
1025 type units.  For N::A, the actual
1026 definition of the type begins at label L1. The definition
1027 involves references to the int base type and to two pointer
1028 types. The information for each of these referenced types is
1029 also included in this \addtoindex{type unit}, 
1030 since base types and pointer
1031 types are trivial types that are not worth the overhead of a
1032 separate \addtoindex{type unit}. 
1033 The last pointer type contains a reference
1034 to an incomplete type N::B, which is also included here as
1035 a declaration, since the complete type is unknown and its
1036 signature is therefore unavailable. There is also a reference
1037 to N::C, using 
1038 \livelink{chap:DWFORMrefsig8}{DW\-\_FORM\-\_ref\-\_sig8} to 
1039 refer to the type signature
1040 \addtoindexx{type signature}
1041 for that type.
1042
1043 In computing a signature for the type N::A, flatten the type
1044 description into a byte stream according to the procedure
1045 outlined in 
1046 Section \refersec{datarep:typesignaturecomputation}.
1047 The result is shown in 
1048 Figure \refersec{fig:typesignatureexample2flattenedbytestream}.
1049
1050 \begin{figure}
1051 \figurepart{1}{3}
1052 \begin{dwflisting}
1053 % DWARF4 had a \livelink{chap:DWATnamespace}{DW_AT_namespace} below, 
1054 % but this error is fixed here to be \livelink{chap:DWTAGnamespace}{DW_TAG_namespace}.
1055 \begin{alltt}
1056 // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
1057 0x43 0x39 0x4e 0x00
1058 // Step 3: 'D' \livelink{chap:DWTAGclasstype}{DW\-\_TAG\-\_class\-\_type}
1059 0x44 0x02
1060 // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "A"
1061 0x41 0x03 0x08 0x41 0x00
1062 // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 20
1063 0x41 0x0b 0x0d 0x14
1064 // Step 7: First child ("v\_")
1065     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1066     0x44 0x0d
1067     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "v\_"
1068     0x41 0x03 0x08 0x76 0x5f 0x00
1069     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1070     0x41 0x32 0x0d 0x03
1071     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
1072     0x41 0x38 0x0d 0x00
1073     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1074     0x54 0x49
1075         // Step 3: 'D' \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type}
1076         0x44 0x24
1077         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "int"
1078         0x41 0x03 0x08 0x69 0x6e 0x74 0x00
1079         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1080         0x41 0x0b 0x0d 0x04
1081         // Step 4: 'A' \livelink{chap:DWATencoding}{DW\-\_AT\-\_encoding} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWATEsigned}{DW\-\_ATE\-\_signed}
1082         0x41 0x3e 0x0d 0x05
1083         // Step 7: End of \livelink{chap:DWTAGbasetype}{DW\-\_TAG\-\_base\-\_type} "int"
1084         0x00
1085     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "v\_"
1086     0x00
1087 // Step 7: Second child ("next")
1088     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1089     0x44 0x0d
1090     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "next"
1091     0x41 0x03 0x08 0x6e 0x65 0x78 0x74 0x00
1092     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1093     0x41 0x32 0x0d 0x03
1094     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1095     0x41 0x38 0x0d 0x04
1096 \end{alltt}
1097 \end{dwflisting}
1098 \caption{Type signature example \#2: flattened byte stream}
1099 \label{fig:typesignatureexample2flattenedbytestream}
1100 \end{figure}
1101
1102 \begin{figure}
1103 \figurepart{2}{3}
1104 \begin{dwflisting}
1105 \begin{alltt}    
1106     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#3)
1107     0x54 0x49
1108         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1109         0x44 0x0f
1110         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
1111         0x4e 0x49
1112         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
1113         0x43 0x39 0x4e 0x00 0x45
1114         // Step 5: "A"
1115         0x41 0x00
1116         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1117         0x00
1118     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1119     0x00
1120 // Step 7: Third child ("bp")
1121     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1122     0x44 0x0d
1123     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "bp"
1124     0x41 0x03 0x08 0x62 0x70 0x00
1125     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1126     0x41 0x32 0x0d 0x03
1127     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
1128     0x41 0x38 0x0d 0x08
1129     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#4)
1130     0x54 0x49
1131         // Step 3: 'D' \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1132 0x44 0x0f
1133         // Step 5: 'N' \livelink{chap:DWATtype}{DW\-\_AT\-\_type}
1134         0x4e 0x49
1135         // Step 5: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N" 'E'
1136         0x43 0x39 0x4e 0x00 0x45
1137         // Step 5: "B"
1138         0x42 0x00
1139         // Step 7: End of \livelink{chap:DWTAGpointertype}{DW\-\_TAG\-\_pointer\-\_type}
1140         0x00
1141     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "next"
1142     0x00
1143 // Step 7: Fourth child ("c")
1144     // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1145     0x44 0x0d
1146     // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "c"
1147     0x41 0x03 0x08 0x63 0x00
1148     // Step 4: 'A' \livelink{chap:DWATaccessibility}{DW\-\_AT\-\_accessibility} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \livelink{chap:DWACCESSprivate}{DW\-\_ACCESS\-\_private}
1149     0x41 0x32 0x0d 0x03
1150 \end{alltt}
1151 \end{dwflisting}
1152 \begin{center}
1153 Figure~\ref{fig:typesignatureexample2flattenedbytestream} Type signature example \#2: flattened byte stream \textit{(continued)}
1154 \end{center}
1155 \end{figure}
1156     
1157 \begin{figure}
1158 \figurepart{3}{3}
1159 \begin{dwflisting}
1160 \begin{alltt}
1161     // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 12
1162     0x41 0x38 0x0d 0x0c
1163     // Step 6: 'T' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#5)
1164     0x54 0x49
1165         // Step 2: 'C' \livelink{chap:DWTAGnamespace}{DW\-\_TAG\-\_namespace} "N"
1166         0x43 0x39 0x4e 0x00
1167         // Step 3: 'D' \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type}
1168         0x44 0x13
1169         // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "C"
1170         0x41 0x03 0x08 0x43 0x00
1171         // Step 4: 'A' \livelink{chap:DWATbytesize}{DW\-\_AT\-\_byte\-\_size} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 8
1172         0x41 0x0b 0x0d 0x08
1173         // Step 7: First child ("x")
1174             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1175             0x44 0x0d
1176             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "x"
1177             0x41 0x03 0x08 0x78 0x00
1178             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 0
1179             0x41 0x38 0x0d 0x00
1180             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1181             0x52 0x49 0x02
1182             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "x"
1183             0x00
1184         // Step 7: Second child ("y")
1185             // Step 3: 'D' \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member}
1186             0x44 0x0d
1187             // Step 4: 'A' \livelink{chap:DWATname}{DW\-\_AT\-\_name} \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} "y"
1188             0x41 0x03 0x08 0x79 0x00
1189             // Step 4: 'A' \livelink{chap:DWATdatamemberlocation}{DW\-\_AT\-\_data\-\_member\-\_location} \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} 4
1190             0x41 0x38 0x0d 0x04
1191             // Step 6: 'R' \livelink{chap:DWATtype}{DW\-\_AT\-\_type} (type \#2)
1192             0x52 0x49 0x02
1193             // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "y"
1194             0x00
1195         // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "C"
1196         0x00
1197     // Step 7: End of \livelink{chap:DWTAGmember}{DW\-\_TAG\-\_member} "c"
1198     0x00
1199 // Step 7: Fifth child ("A")
1200     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "A"
1201     0x53 0x2e 0x41 0x00
1202 // Step 7: Sixth child ("v")
1203     // Step 3: 'S' \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram} "v"
1204     0x53 0x2e 0x76 0x00
1205 // Step 7: End of \livelink{chap:DWTAGstructuretype}{DW\-\_TAG\-\_structure\-\_type} "A"
1206 0x00
1207 \end{alltt}
1208 \end{dwflisting}
1209 \begin{center}
1210 Figure~\ref{fig:typesignatureexample2flattenedbytestream} Type signature example \#2: flattened byte stream \textit{(concluded)}
1211 \end{center}
1212 \end{figure}
1213
1214 Running an \addtoindex{MD5 hash} over this byte stream, and taking the
1215 low-order 64 bits, yields the final signature: 0xd6d160f5
1216 5589f6e9.
1217
1218
1219 A source file that includes this header file may declare a
1220 variable of type N::A, and its DWARF information may look
1221 like that shown in 
1222 Figure \refersec{fig:typesignatureexampleusage}.
1223
1224 \begin{figure}
1225 \begin{dwflisting}
1226 \begin{alltt}
1227   \livelink{chap:DWTAGcompileunit}{DW\-\_TAG\-\_compile\-\_unit}
1228   ...
1229   \livelink{chap:DWTAGsubprogram}{DW\-\_TAG\-\_subprogram}
1230     ...
1231     \livelink{chap:DWTAGvariable}{DW\-\_TAG\-\_variable}
1232       \livelink{chap:DWATname}{DW\-\_AT\-\_name} : "a"
1233       \livelink{chap:DWATtype}{DW\-\_AT\-\_type} : (signature) 0xd6d160f5 5589f6e9
1234       \livelink{chap:DWATlocation}{DW\-\_AT\-\_location} : ...
1235     ...
1236 \end{alltt}
1237 \end{dwflisting}
1238 \caption{Type signature example usage}
1239 \label{fig:typesignatureexampleusage}
1240 \end{figure}
1241
1242 \subsection{Type Signature Computation Grammar}
1243 \label{app:typesignaturecomputationgrammar}
1244
1245 This section
1246 \addtoindexx{type signature!computation grammar}
1247 presents a semi-formal grammar that may aid in understanding
1248 how the bytes of the flattened type description are formed
1249 during the type signature computation algorithm of Section
1250 Section \refersec{datarep:typesignaturecomputation}. 
1251
1252 %FIXME: The index entries here with \addtoindexx are ineffective.
1253 \begin{alltt}
1254 signature
1255     : opt-context debug-entry attributes children
1256
1257 opt-context           // Step 2
1258     : 'C' tag-code string opt-context
1259     : empty
1260
1261 debug-entry           // Step 3
1262     : 'D' tag-code
1263
1264 attributes            // Steps 4, 5, 6
1265     : attribute attributes
1266     : empty
1267
1268 attribute
1269     : 'A' at-code form-encoded-value     // Normal attributes
1270     : 'N' at-code opt-context 'E' string // Reference to type
1271                                          // by name
1272     : 'R' at-code back-ref               // Back-reference 
1273                                          // to visited type
1274     : 'T' at-code signature              // Recursive type
1275     
1276 children             //  Step 7
1277     : child children
1278     : '0'
1279
1280 child
1281     : 'S' tag-code string
1282     : signature
1283
1284 tag-code
1285     : <ULEB128>
1286
1287 at-code
1288     : <ULEB128>
1289     
1290 form-encoded-value
1291     : \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} value \addtoindexx{constant class}
1292     : \livelink{chap:DWFORMflag}{DW\-\_FORM\-\_flag} value \addtoindexx{flag class}
1293     : \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} string \addtoindexx{string class}
1294     : \livelink{chap:DWFORMblock}{DW\-\_FORM\-\_block} \nolink{block} \addtoindexx{block class}
1295 \livelink{chap:DWFORMstring}{DW\-\_FORM\-\_string} \addtoindexx{string class}
1296     : 'x08'
1297 \livelink{chap:DWFORMblock}{DW\-\_FORM\-\_block}  \addtoindexx{block class}
1298     : 'x09'
1299 \livelink{chap:DWFORMflag}{DW\-\_FORM\-\_flag} \addtoindexx{flag class}
1300     : 'x0c'
1301 \livelink{chap:DWFORMsdata}{DW\-\_FORM\-\_sdata} \addtoindexx{constant class}
1302     : 'x0d'
1303     
1304 value
1305     : <SLEB128>
1306     
1307 \nolink{block}
1308     : <ULEB128> <fixed-length-block>
1309                       // The ULEB128 gives the length of the \nolink{block}
1310 back-ref
1311     : <ULEB128>
1312     
1313 string
1314     : <null-terminated-string>
1315     
1316 empty
1317     :
1318 \end{alltt}
1319
1320
1321 \section{Summary of Compression Techniques}
1322 \label{app:summaryofcompressiontechniques}
1323 \subsection{\#include compression}
1324 \label{app:includecompression}
1325
1326 \addtoindex{C++} has a much greater 
1327 problem than 
1328 \addtoindex{C} with the number and
1329 size of the headers included and the amount of data in each,
1330 but even with \addtoindex{C} 
1331 there is substantial header file information
1332 duplication.
1333
1334 A reasonable approach is to put each header file in its own
1335 \addtoindex{section group}, using the naming rules mentioned above. The
1336 section groups are marked to ensure duplicate removal.
1337
1338 All data instances and code instances (even if they came
1339 from the header files above) are put 
1340 \addtoindexx{section group}
1341 into non-section group
1342 sections such as the base object file 
1343 \addtoindex{.debug\_info} section.
1344
1345 \subsection{Eliminating function duplication}
1346 \label{app:eliminatingfunctionduplication}
1347
1348
1349 Function templates (C++) result in code for the same template
1350 instantiation being compiled into multiple archives or
1351 relocatable objects. The linker wants to keep only one of a
1352 given entity. The DWARF description, and everything else for
1353 this function, should be reduced to just a single copy.
1354
1355 For each such code group (function template in this example)
1356 the compiler assigns a name for the group which will match
1357 all other instantiations of this function but match nothing
1358 else. 
1359 The 
1360 \addtoindexx{section group}
1361 section groups are marked to ensure duplicate
1362 removal, so that the second and subsequent definitions seen
1363 by the static linker are simply discarded.
1364
1365
1366 References to other 
1367 \addtoindex{.debug\_info} sections follow the approach
1368 suggested above, but the naming rule might be slightly
1369 different in that the 
1370 \begin{alltt}
1371 <file-designator> 
1372 \end{alltt}
1373 should be interpreted
1374 as a 
1375 \begin{alltt}
1376 <function-designator>.
1377 \end{alltt}
1378
1379
1380
1381 \subsection{Single-function-per-DWARF-compilation-unit}
1382 \label{app:singlefunctionperdwarfcompilationunit}
1383
1384 Section groups can help make it easy for a linker to completely
1385 remove unused functions.
1386
1387 Such 
1388 \addtoindexx{section group}
1389 section groups are not marked for duplicate removal,
1390 since the functions are not duplicates of anything.
1391
1392 Each function is given a compilation unit and a section
1393 group. Each such compilation unit is complete, with its own
1394 text, data, and DWARF sections.
1395
1396 There will also be a compilation unit that has the file\dash level
1397 declarations and definitions. Other per\dash function compilation
1398 unit DWARF information (
1399 \addtoindex{.debug\_info}) points to this common
1400 file\dash level compilation unit using \livelink{chap:DWTAGimportedunit}{DW\-\_TAG\-\_imported\-\_unit}.
1401
1402 Section groups can use \livelink{chap:DWFORMrefaddr}{DW\-\_FORM\-\_ref\-\_addr} and internal labels
1403 (section\dash relative relocations) to refer to the main object
1404 file sections, as the 
1405 \addtoindexx{section group}
1406 section groups here are either deleted
1407 as unused or kept. There is no possibility (aside from error)
1408 of a group from some other compilation being used in place
1409 of one of these groups.
1410
1411
1412 \subsection{Inlining and out-of-line-instances}
1413 \label{app:inliningandoutoflineinstances}
1414
1415 Abstract instances
1416 \addtoindexx{abstract instance}
1417 \addtoindexx{concrete out-of-line instance}
1418 and concrete-out-of-line instances may be
1419 put in distinct compilation units using 
1420 \addtoindexx{section group}
1421 section groups. 
1422 This
1423 makes possible some useful duplicate DWARF elimination.
1424
1425 \textit{No special provision for eliminating class duplication
1426 resulting from template instantiation is made here, though
1427 nothing prevents eliminating such duplicates using section
1428 groups.}
1429
1430
1431 \subsection{Separate Type Units}
1432 \label{app:separatetypeunits}
1433
1434 Each complete declaration of a globally-visible type can be
1435 \addtoindexx{type unit}
1436 placed in its own separate type section, with a group key
1437 derived from the type signature. The linker can then remove
1438 all duplicate type declarations based on the key.
1439