Location lists and discontiguous scopes share a common problem. The proposals
of 001101.1 and 001130.1 attempted to address that problem for both of them,
although those proposals talked mostly about ranges lists because they are
the simpler of the two (having no location associated with each list entry)
and the problem was originally noticed in the context of thinking about ranges
lists.

After two attempts, it appears that trying to separate location lists and
discontiguous scopes into two independent proposals doesn't work. So,
following is a single proposal to cover them both. (Note: this proposal
merely merges both parts of my 24 January email into a single proposal.)

PROBLEM STATEMENT
-----------------

The DWARF V2 design of location lists for representing the locations of
variables that change over time is not adequate to deal with variables
declared in functions whose code is split into multiple program (text)
sections. Similarly for discontiguous scopes.

Recall that in DWARF V2, location lists are defined in Sections 2.4,
2.4.6 and 7.7.2. In DWARF V2.1 Draft 5DW they are defined in Figure 3
(see specifically loclistptr), Sections 2.5, 2.5.4, 7.5.4 (see
specifically loclistptr) and 7.7.3. In both cases they are referenced
from attributes, most notably DW_AT_location, whose value is interpreted
as an offset in the .debug_loc section where the beginning of a location
list is found.

Recall that in DWARF V2.1 Draft 5DW, discontiguous scopes are defined in
Figure 3 (see specifically rangelistptr), Sections 2.6.3, 7.5.4 (see
specifically rangelistptr) and 7.24. A range list is referenced from
a DW_ranges attribute whose value is interpreted as an offset in the
.debug_ranges section where the beginning of a ranges list is found.

A location list consists of a sequence of location list entries, where
each entry consists of

    - A beginning address
    - An ending address
    - A location expression

The two addresses are specified to be "relative to the base address of
the compilation unit referencing this location list". (An attractive
consequence of this formulation is the two addresses need not be relocated
at linktime or loadtime, which has both size and system performance
benefits.)

In DWARF V2, there are two problems with this formulation. The first is
that in a compilation that is split into more than one program section,
it is ambiguous which program section establishes "the base address".
DWARF V2.1 Section 3.1 resolves this problem as follows:

    "The base address of a compilation is defined as follows: If a
    DW_AT_entry_pc is given for the unit, the base address is the
    value of that attribute. Otherwise, if a DW_AT_low_pc attribute
    is specified, the base address is the value of that attribute.
    If neither is present, then the base address is undefined and
    any DWARF [debugging information] entry or structure defined
    in terms of the base address of that compilation is not valid."

(Section 2.5.4 would benefit from a reference to this definition.)

The second problem is more subtle and is the problem that this proposal
seeks to correct.

The second problem derives from the definition of the beginning and
ending addresses as relative to the base address, which is to say
as the difference (offset) of the given address minus (relative to)
the base address. That is, for a location list entry with beginning
address BEG, ending address END, location register R0, and base address
BASE, the location list entry is represented as

    (BEG - BASE, END - BASE, <location expression for register R0>)

If there is only a single text program section, then there is no problem:
BEG and BASE are at known offsets relative to the beginning of that section
and the difference is easily computed by the compiler. However, if BEG and
END are defined in one program section and BASE is defined in another,
then there is a problem: Few object file representations in common use
today provide relocation commands that singly or in combination are able
to compute the required difference and use it to initialize storage at
link time (or possibly even load time).

    As a key example, ELF for the IA-32 architecture does not provide such
    relocation capability.

Without such relocation capability, optimizing compilers that split
modules and functions into more than one program section cannot implement
DWARF location lists.

Similarly, a ranges list consists of a sequence of ranges list entries,
where each entry consists of

    - A beginning address
    - An ending address

The two addresses are specified to be "relative to the base address of
the compilation unit referencing this ranges list".

A ranges list is just like a location list in its use of relative
addresses to define the beginning and ending addresses of each entry of
the list. As a result, it shares all of the problems of location lists when
multiple sections containing generated machine code are involved.

The discussion that follows is presented in terms of location lists; however
it should be understood that it applies to ranges lists as well. Moreover,
the proposed textural changes do cover both location lists and ranges lists.

A detailed example that illustrates how this problem comes about can be
found at the end of this proposal.


PROPOSAL
--------

This proposal has two main parts:

  - Define an attribute DW_AT_base_addresses, which may be used only
    for the compilation unit DIE, and whose value is a sequence of
    addresses where each address is the beginning address of one of
    the text program sections that hold the machine code.

  - Define a means to associate one or more entries in a location list or
    ranges list with one of the base addresses from the DW_AT_base_addresses
    attribute, and use that particular base address in computing the
    relative addresses for those entries.


DW_AT_base_addresses

This attribute is used only on a compilation unit DIE and is used in
combination with DW_AT_ranges (and instead of DW_AT_low_pc and
DW_AT_high_pc). The value of this attribute is a sequence of addresses,
represented using class block, where each address is the beginning address
of one of the (text) sections that contain some of the machine code for
the compilation unit.

DW_AT_ranges and DW_AT_base_addresses are used when the machine code
for the compilation unit is contained in discontiguous ranges of
addresses. This will always be the case when the code is contained
in multiple, independently relocated text sections; moreover, it can
also apply when there is only a single program section with contains
both instructions and data, where the instructions are non-contiguous.

The order of addresses is arbitrary but the actual order is used in
the encoding of location lists as explained below. Let the first
address be called the "first base address", the second called the
"second base address", and so on.

When DW_AT_base_addresses is not present, then the value of DW_AT_low_pc
is called the "first base address", or for simplicity just "the base
address".

This proposal replaces the use of DW_AT_entry_pc in establishing the
base address of a compilation unit.

Relating a location list entry to "its" base address

First, recall that the addresses BEG and END of a relocation list entry
must satisfy the relationship BEG < END. (The end address is defined as
one past the last address in the range, so even for a range consisting
of one address ADR we have ADR < ADR + 1.) Since the two relative
addresses must logically be relative to the same base address, we can
define the low relative address L = BEG - BASE and the high relative
address H = END - BASE, and it immediately follows that L < H.

As a consequence, any relative address pair (L, H) that does not satisfy
L < H can be used to encode something other than a "normal" location
list entry. DWARF already exploits this! The pair (0, 0), that is, a pair
of zeros, identifies the end of a list.

Define a "base address selection entry" to consist of the pair (N, 0)
where N > 0; it specifies that subsequent entries in the same location
list are defined relative to the N'th base address (as specified in the
DW_AT_base_addresses attribute of the referencing compilation unit).
This selection applies to subsequent location list entries until a
new base address selection entry is encountered. The first location
list entry is assumed to be relative to the first base address (so that
an initial (1,0) is redundant and need not be present).

There is no need to append a fake DWARF expression (eg, a 2-byte count
of zero) in a (misguided) attempt to make the base address selection
entry "look like" a location entry. (The (0, 0) end of list entry does
not have a pseudo-location either.) The ability of dumpers to scan and
interpret the .debug_loc section independent of other information is not
compromised by this omission.

Finally, adjust the definition of location list to be a sequence of
entries, each of which is either a base address selection entry or
a location list entry, followed by an end of list entry.


DOCUMENT CHANGES
----------------

A) In Figure 2 (Section 2.2), add DW_AT_base_addresses.

B) In Section 2.5.4, replace "Each entry in a location list consists
   of:" together with the following bullets with (note: | helps mark the
   actual changes)

|     "Each entry in a location list is either a base address selection
|     entry (see Section 3.1.2) or a location list entry. A location
      list entry consists of:

|     1. A beginning address. This address is relative to the applicable
         base address of the compilation unit referencing this location
         list. It marks the beginning of the address range over which
         the location is valid.
|     2. An ending address, again relative to the applicable base
         address of the compilation unit referencing this location list.
         It marks the first address past the end of the address range
         over which the location is valid.
      3. A location expression describing the location of the object
         over the range specified by the beginning and ending address.

|     "The applicable base address of a location list entry is determined
|     by the closest preceding base address selection entry in the
|     same location list. If there is no such selection entry, then the
|     applicable base address is the first (possibly only) base address
|     of the compilation unit (see Section 3.1.1).

|     "<italics>In the case of a compilation unit where all of the
|     machine code is contained in a single contiguous section, no base
|     address selection entry is ever needed.</italics>"

C) In Section 2.16.3, replace "Each entry in a range list consists
   of:" together with the following bullets with (note: | helps mark
   the actual changes)

|     "Each entry in a range list is either a base address selection
|     entry (see Section 3.1.2) or a range list entry. A range list
      entry consists of:

|     1. A beginning address. This address is relative to the applicable
      base address of the compilation unit referencing this range
      list.
|     2. An ending address, again relative to the applicable base
      address of the compilation unit referencing this range list.

|     "The applicable base address of a range list entry is determined
|     by the closest preceding base address selection entry in the
|     same ranges list. If there is no such selection entry, then the
|     applicable base address is the first (possibly only) base address
|     of the compilation unit (see Section 3.1.1).

|     <italics>"In the case of a compilation unit where all of the
|     machine code is contained in a single contiguous section, no base
|     address selection entry is ever needed.</italics>"

D) In Section 3.1, bullet 1, replace the bullet with the following:

      "Either a DW_AT_low_pc and DW_AT_high_pc pair of attributes or
      a DW_AT_ranges and DW_AT_base_addresses pair of attributes whose
      values encode the contiguous or non-contiguous address ranges,
      respectively, of the machine instructions generated for the
      compilation unit.

      "DW_AT_low_pc, DW_AT_high_pc and DW_AT_ranges attributes are
      described in Section 2.16.3. The DW_AT_base_addresses attribute
      is described later in Section 3.1.1."

E) In Section 3.1, replace the last paragraph (which defines the base
   address of a compilation unit) with the following:

      "3.1.1 Base Addresses

      "A compilation unit may have one or more base addresses, which are
      specified by the DW_AT_low_pc or DW_AT_base_addresses attribute
      of the compilation unit entry. If neither DW_AT_low_pc nor
      DW_AT_base_addresses is present, then the base address(es) is
      (are) undefined and any DWARF debugging information entry or
      related structure defined in terms of the base address(es) of
      the compilation unit is invalid."

      "If the DW_AT_low_pc attribute is given, then the value of the
      first (and only) base address of the compilation unit is the
      value of that attribute.

      "The value of a DW_AT_base_addresses attribute is a sequence of
      addresses represented using class block, where each address is
      the beginning address of one of the independently relocatable
      sections that contain machine code of the compilation unit.
      There is one address for each section. The first base address
      of the compilation unit is the value of the first address in
      the block, the second base address of the compilation unit is
      the value of the second address in the block, and so on.

      "<italics>There may be only one such address if the machine
      code has multiple discontiguous ranges of instructions, all
      generated in a single section (possibly separated by program
      data or other system information).</italics>

      "3.1.2 Base Address Selection

      "Location lists (see Section 2.5.4) and range lists (see
      Section 2.16.3) may include one or more base address selection
      entries.

      "A base address selection entry consists of:

      "1. A base address index. The value N indicates that the N'th
          base address of the referencing compilation unit is the
          appropriate base address for use in interpreting the beginning
          and ending relative addresses of subsequent entries of
          the location list or ranges list. The value N must not
          be zero or larger than the number of base addresses defined
          for the referencing compilation unit.

          <italics>A base address selection entry affects only the
          list in which it is contained.</italics>

      "2. Zero.

          <italics>The pair (N, 0) cannot be part of a location
          list entry or be a ranges list entry because N and 0
          do not constitute a valid range of addresses (for which
          the beginning address is necessarily less than the
          ending address). The pair (N, 0) cannot be an end of list
          marker because N cannot be 0 in a base address selection
          entry.</italics>

      "If a compilation unit has only a single base address, then
      no base address selection entry is ever required in a location
      list or ranges list of that compilation unit."


F) In Section 7.7.3, replace the current two paragraphs with (note:
   | helps mark the actual changes)

|     "Each entry in a location list is either a base address
|     selection entry or a location list entry.

|     "A base address selection entry consists of two integers.
|     The integers are the same size as used by DW_FORM_addr on the
|     target machine.

|     "A location list entry consists of two relative addresses
      followed by a 2-byte length, followed by a block of contiguous
      bytes. The length specifies the number of bytes in the block
      that follows. The two addresses are the same size as used
      by DW_FORM_addr on the target machine.

G) In Section 7.24, replace the current two paragraphs with (note:
   | helps mark the actual changes)

|     "Each entry in a ranges list is either a base address
|     selection entry or a ranges list entry.

|     "A base address selection entry consists of two integers.
|     The integers are the same size as used by DW_FORM_addr on the
|     target machine.

|     "A ranges list entry consists of two relative addresses.
      The addresses are the same size as used by DW_FORM_addr on
      the target machine.

DISCUSSION
----------

There are a variety of ways to address the problem described, but an
important constraint is that the solution is upward compatible with
the DWARF V2 specification of location lists. The proposal does that.

This proposal solves the problem in a way that retains the property that
no relocations are needed for the .debug_loc section.

It has been suggested that it is desirable for whatever solution is
proposed to be first implemented as a vendor extension, as a way of
proving the viability and correctness of the proposal. While desirable,
it is not possible for me to do so. Of the systems available to me:
  - Alpha VMS supports generating code in multiple sections that are
    independently relocated as late as load time. The proprietary debug
    symbol table representation supports the equivalent of location
    lists in a way that uses real address and length
    pairs rather than relative addresses. That approach does not share
    the DWARF problem.
  - Alpha Tru64 does not support generating code in multiple sections
    that are independently relocated (it uses a variation of COFF);
    neither does it use ELF.
  - Alpha Linux supports generating code in multiple sections that are
    independently relocated at load time, using ELF and DWARF. The
    compilers, however, do not currently support this (treating the
    underlying ELF object format in a manner similar to Tru64 COFF).


ALTERNATIVES CONSIDERED
-----------------------

Here is how this proposal compares to the earlier proposals 001101.1
and 001130.1.

Compared to 001101.1:
  - This proposal and 001101.1 are identical in the way that the
    so-called base address selection entry is used to select the
    appropriate base address for subsequent entries in a location
    list.
  - This proposal defines the DW_AT_base_addresses attribute to
    establish the sequence of base addresses for the unit; 001101.1
    uses the DWARF V2 defined .debug_aranges section to provide that
    information.
  - This proposal uses the DW_AT_ranges attribute on a compilation
    unit to specify the set of ranges for a discontiguous compilation
    unit; 001101.1 did not need (nor allow) DW_AT_ranges on a
    compilation unit because the full range information is already
    available in the .debug_aranges section.
  - This proposal does not change the implementer optional status of
    the .debug_aranges section; 001101.1 requires the use of the
    .debug_aranges section for those (and only those) compilation
    units that generate code in multiple independently relocated
    sections.

Compared to 001130.1:
  - This proposal has a single "central" attribute that specifies
    the set of base addresses for a compilation unit; 001130.1 has
    no central specification.
  - This proposal and 001130.1 both exploit the requirement that
    L < H in a valid location list entry, so that other pairs of
    values can be interpreted in a different way. This proposal
    uses the pair (N, 0) to encode an index that identifies the
    applicable base address; 001130.1 uses the pair (M, B) where
    M is the maximum possible address (either 0xFFFFFFFF or
    0xFFFFFFFFFFFFFFFF) and B is the base address itself to be
    used for subsequent entries.
  - This proposal requires no relocations in the .debug_loc section;
    001130.1 requires a relocation for each occurrence of a base
    address (one for each base address selection entry).

All three proposals drop the use of DW_AT_entry_pc to define "the"
base address of a compilation unit, because the limitation to a single
base address is in fact part of the problem.

One could also explore possible schemes where the control information
that associates a base address with an location list entry is external
to the .debug_loc section. While I played with some such ideas, they
all seemed to be less intuitive and more complicated than any of the
ones mentioned here.


DETAILED PROBLEM DESCRIPTION
----------------------------

Suppose we have an application that looks sort'a like this

---- File application.cxx -----

    void ROUT1 {...}

    void ROUT2 {

        int status = 0;

        while (status) {

            ...hot computes 1...

            if (status) {

                // report the error, should never happen
                //
                ...cold code...

                goto done;
            }

            ...hot computes 2...

            if (status) {

                // report the error, should never happen
                //
                ...cold code...

                goto done;
            }
        }

    done: return;
    }

----------

Suppose the compiler determines (based in clever heuristics, or source
pragmas [not shown], or run-time profile feedback) that the best way to
compile this module is to split the code for ROUT2 into two independent
sections called, say, .text_hot and .text_cold. At the assembler level
the compiled code will look sort'a like this

[*Note: any resemblance to real assembly code for any particular assembler
is mostly amazingly good luck. Hopefully the notion is more or less generic
and suggestive enough to be self-explanatory.]

                      .section   .text_hot
        SECTION$$1:
        ROUT1:         .entry
                      ...some code...

        ROUT2:         .entry
                      ...allocate stack
                      ...initialize status
        ROUT2$$L:
                      ...test status
                      ...hot computes 1

                      beq      ROUT2$$1
                      jmp      COLD$$1
        ROUT2$$1:

                      ...hot computes 2

                      beq      ROUT2$$2
                      jmp      COLD$$2
        ROUT2$$2:

                      br       ROUT2$$L
        ROUT2$$DONE:
                      ...deallocate stack
                      ...return

        SECTION$$1$$END:
                      .end     .text_hot

                      .section .text_cold
        SECTION$$2:
        COLD$$1:
                      ...error reporting code 1 using variable status
                      jmp      ROUT2$$DONE

        COLD$$2:
                      ...error reporting code 2 using variable status
                      jmp      ROUT2$$DONE

        SECTION$$2$$END:
                      .end      .text_cold


Now, given that generated code, what should the DWARF sections look like?

                      .section .debug_abbrev
                      ...yada yada...
                      .end      .debug_abbrev

                      .section .debug_info

                      DW_TAG_compile_unit
                          ...
                          DW_AT_entry_pc(address SECTION$$1)
                          ...
                          DW_TAG_subroutine
                              DW_AT_name("ROUT2")
                              DW_AT_ranges(reference to ROUT2$$RANGES)
                              ...

                      .end      .debug_info

                      .section .debug_loc

        ROUT2$$LOC:          ! Location list for variable 'status' in ROUT2
                      .word      ROUT2 - SECTION$$1                  ! hot part
                      .word      SECTION$$1$$END - SECTION$$1
                      .word      ...<location expression for status>

                      .word      COLD$$1 - SECTION$$1                ! cold part
                      .word      SECTION$$2$$END - SECTION$$1
                      .word      ...<location expression for status>

                      .word 0
                      .word 0

                      .end       .debug_ranges

Consider just the line that reads

                      .word      COLD$$1 - SECTION$$1                ! cold part

This line creates the relative address for the lower bound of one of the
location list entries for status in ROUT2. The compiler surely knows the
offset of COLD$$1 within section .text_cold and it knows offset of SECTION$$1
within section .text_hot. But, the compiler knows nothing about the
relationship of the section .text_hot and .text_cold. That will be
determined later by the linker and/or loader. So, it must use some kind
of relocation directives in the underlying object module representation
to construct the difference between this two locations.

    The PROBLEM is that many object module representations do not
    provide a way to do this. ELF for the IA-32 is an example.

Why subtract SECTION$$1? Because that is the base address specified by the
DW_AT_entry_pc attribute for the compilation unit. It makes no difference
what base address is selected, even one in section .text_cold. The same
problem just shows up again for other entries.

In the solution I propose, we would instead have:

Instead of DW_AT_entry_pc(address SECTION$$1) in the compilation unit we
would have

    DW_AT_base_addresses(address SECTION$$1, address SECTION$$2)

And the location list would look like:

        ROUT2$$LOC:                                      ! assume base 1
                    .word      ROUT2 - SECTION$$1        ! hot part
                    .word      SECTION$$1$$END - SECTION1$$
                    .word      ...<location expression for status>

                    .word      2                          ! select base 2
                    .word      0

                    .word      COLD$$1 - SECTION$$2      ! cold part
                    .word      SECTION$$2$$END - SECTION$$2
                    .word      ...<location expression for status>

                    .word      0
                    .word      0

The first entry in the location list is unchanged.

The two new words are a base address selection entry, which "states" that
following entries are relative to the second base address specified in
the DW_AT_base_addresses attribute of the compilation unit.

The following entry is similar to before but subtracts SECTION$$2
rather than SECTION$$1. Since COLD$$1 and SECTION$$2 are in the same
section (.text_cold), the compiler can compute the difference in their
offsets and establish the contents of that word directly. Similarly for
SECTION$$2$$END and SECTION$$2.

Notice that no relocations of any kind are required for this .debug_loc
section.