<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/57714>57714</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Possible refactoring of InputSection hierarchy
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            lld:MachO
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
            int3
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          int3
      </td>
    </tr>
</table>

<pre>
    Been thinking about how our InputSection hierarchy is not ideal, but I'm not ready to put a diff out for it just yet so here are some thoughts. Basically the problem is that we are conflating how sections are represented with how they are used

To recap, right now we have 3 types of InputSections.

1. `ConcatInputSection`s: As the name suggests, these are concatenated together for output (i.e. the "how it is used"). However they are also the only way to handle variable-size subsections that can contain relocations pointing to other sections...
2. `WordLiteralInputSection`s: These efficiently represent fixed-sized subsections that are some power of 2. However (as "Literal" implies) they cannot contain relocations. I.e. they must be leaf nodes in the graph of subsections.
3. `CStringInputSection`s: These represent variable-sized subsections that each contain a null-terminated string. They support string hash -> output offset lookups. These InputSections must also be leaf nodes.

Notably lacking is an InputSection that can efficiently represent fixed-sized subsections whilst being an internal node. This would be useful for `__objc_selrefs`, `__objc_classrefs`, and `__cfstring` (at least). Right now we represent them as ConcatInputSections, which is fine, just inefficient. Allocating a 128-byte ConcatInputSection for every 8 byte selector reference is not ideal.

At the same time, I'm wary of growing the complexity of the class hierarchy. Right now we `dyn_cast` InputSections in a number of places, but primarily we do this to distinguish ConcatInputSections from the other two, in order that we can correctly handle the fact that they are internal nodes. We don't usually need to dynamically distinguish between `WordLiteralInputSection` and `CStringInputSection`s. Similarly, I anticipate that we'll rarely have a need to distinguish between fixed-sized non-literal sections from the variable-sized ones.

All that said, here's what I think an ideal refactored class hierarchy would look like:
* InputSection gets renamed to InputSectionBase (mirroring LLD-ELF)
* ConcatInputSection gets renamed to `NonLiteralInputSection` (or just `InputSection` for short), extending InputSectionBase
* We then have `FixedSizeInputSection` and VariableSizedInputSection classes that extend our (NonLiteral)InputSection
* We also introduce a LiteralInputSection that extends InputSectionBase. That is further extended into `WordLiteralInputSection` (maybe `FixedSizeLiteralInputSection` would be a better name?) and `CStringInputSection`. I'm sure `FixedSizeLiteralInputSection` and `FixedSizeInputSection` would share a lot of implementation details, though, so we can factor out some of that into a `FixedSizeMixin` class.

I'm wondering if we should enable `dyn_cast`ing to every class in this hierarchy, or if we should only enable it for `(NonLiteral)InputSection` and `LiteralInputSection`. Too much manual type dispatch in the code is a nightmare, so we shouldn't make it too easy for people to write it. At the same time, having the LLVM RTTI not truly mirror the actual class hierarchy seems a bit sketchy...

All that said, this seems like a pretty big refactoring for an unclear perf win right now, so I'm inclined to punt on it. Just wanted to record my thoughts + gather feedback
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyVV01z2zYQ_TXSBWOORVm2fNDBTuKpO07aqT3J0QOSoIgYBDgAaFn99X27oD4ju-2hqUUQi7cPb98uC1etF7dKWREbbV-0XQpZuD6Kxq2E6724t10fH1UZtbOi0cpLXzZroYOwLgpdKWlG-SdRYMv9KL9q-bFXslqL6AT2CikqXdeCgtbOCx3Fzz5EsVZRBCca5ZWQ-C-4VgGE65dNDJm4lUGX0hiEaZTovCuMaunY2MgoVmlP6WxtZCTUhDckmIHXvOq8CspGVYmVjg2_gVhrXu2Dqkbnn0fnN-nfJ4cNpewoF68BAXms6JhGvioxFXHdqSBcfcBHyPZDTDIxujz_5Gwp4_5beBhG0xtxEzgVK5Fn6JdLFWKg4_AwbNPBXmUlYY5uqbDkmTSQR1SO8rnOVMZxRnlOGYFOkMLp5Pkov87Eb26lXrFvm6s04Jm2OAs6V5JvppG2Mkq8Sq8lqD0L-m-CVWw5ZJ5LaQlVlNqCH-MAjxc7py3TjkiOUW72ZdlASs50_HC-etARsjGnOHni3FVd61LjqgBve22i1m-qYlzVr8C2iumQraeLyXeZgyYZiKDhZPwldNsZrUD4dSIGmZFSTySXifuB47VoSamFEkbJGoqooAFtmcull11D5-5BGzKfJiE8Rg-G3s96l-nBJZxIVsmy2SKVwvbGnCGxVielBD4oo7BrbO465-PwENccGnE2mn7ZSMjVdUDlGede-i5kA5YDVaesWTUHqR-o_ZuLgLwWRpbsGhAhtHLgFlsF_b_7XTXaMOtsRhaEI1crDYMgwDhq5XpTEToIv-4N1wjYfX52xc_yOSjjVR3wgOpr97w0MoS9FZRAWi3rRBd-sHgiZR0il9Nf-26wQw8NtAIq-7XeuaiRBO4MSGttFT1gz8PfGyoycWOS5ChLMcnnZ8U6qhPxODnS9VrMBb-D_LCEp8gF9mlLdeDHB_d0w1BFINeJumUsyahXEhEh4KV3Ky7lhhwIZaLedOQVfkKc7Yz_iA8QVq3tc0lkgbtDGQ1ibYtUoB2kosKmWXRet5A9GZISFfkTebtDrwhESa-h2xPcitq7NpkZ205cOYqIo2A0bHqpOyTj8vB0Et1gdrStlmVMb2398UBgKIkfBMiCowh59dyDrGJHFkhWtkNf2kdaqLiiJvqh42309o4zZOJRt9pIb9Z8SXg9QisdanyTFjAZI3ATipNCZ5I7aCfg7JeYdfbMJFy7Rrll88iCnD0qd4g1gQhSVwSP-jbgULni6X0aH7hcSYKkTEkSRawjBQ21SwYkjH5RMMThoPzm0D_Q_wICUcPkDPcXMR5QC5y32nvHTvfw8Pnsy8MdanYX7kQxHQcF89-cfefCcACqjEsXP49XqS5DA7OlM0GJekPvrgjLMdIdoh-sQpsuD0Hu6IYewfkprXwfLoXWq4MsmFO1aQ98Lk9rALzLBrAOou6DYHeH8L2r-pJkdIKB_ejhl5zIiSUPH3XvuRbTm6AVcd2_lAJdnVwXhxy88-7W7CUJG6_wDDWa0l1_XFPZYHWh9__ppCHYu5eSkISGpypImNopTxaqhaXz-CAqhTZthsmOpln6C2QPppTKgqdhnl_YZolH4kwenP5Vv2k-lm_7oBwHB3egm8Wva4oPMRI-iBuiOfLmYVhLfSSVJE8yeq80CSlN6PvBeGYcIuq4abQf6mxH5GmaoRznMGSgQbbSwmB5uiYDg9dR17RDL6q4r8HiqOWgW6gdlQldMulWvjC2iKho22sG2SnXkeXjbQ8UWEfHPdELUYib5vfw8P2r-Ovp6Z5bafQ9Mk_-wsu4OMJ6bGdBqZZAFkAQXlSkJpl97J3MetpHDojNmCoiem6hl1vnJFSUCDTT2xLzCOXkcTU0rW568EBIkoPGa5gwqvThhRkFaqS0fyf_WkmbviroOwd1Kdr19msL1XgrljJ9baCdFJjpxmoxubycnl9d5LP5uFpMq-vptRxHHY1a_OlC0KSIfbBHH0c7isa9N4smxo6G31GOsr1b4oOsLzKMG_hhzOvmf2f40PuJ_fipQ-hpXLibXV1NLsbNoijzeTG5uCquq9msuFB1ObuezKeTYn5dqss6HxtZKBMWo9ktBn5jKpz2FZPzH_RhNPs81ov8PM_PryfTyfT8YjLLpvO8LGs5q8rJ5ErJYnRxrlrUbkZIMueXY79gUEW_DFg06LBhtwgZ6CW673AgCng6nCR7MOsX9GTMaSw4h38Ah45lRg">