Skip to main content

Léo's blog

Decompiling sead: a small example

For those who are unfamiliar with recent Nintendo games, sead is Nintendo’s homemade C++ standard library. It is used in every recent first-party game such as Breath of the Wild, New Horizons or Labo.

Since those games rely on sead for data structures, strings, threads, file I/O and more, decompiling a game like BotW (even a very partial decomp) involves decompiling sead first.

By decompiling, I do not mean simply throwing the executable into a decompiler, but painstakingly reconstructing source code that is as accurate as possible to the original code1. Getting an accurate implementation of sead with matching code2 is all the more essential since many of its functions are inlined.

One sead component that is used at the heart of BotW’s actor system to speed up lookups by name is sead::TreeMapImpl<K, V>3. Let’s see what it looks like…

TreeMapImpl and TreeMapNode #

Since TreeMapImpl is a class template, looking at any variant of the class would work. I chose TreeMapImpl<TreeMapKeyImpl<SafeString>> as its insert function looked cleanest.

void* sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(__int64 a1, void *a2, void *a3)
{
  // ...

  v3 = a3;
  v4 = a2;
  if ( a2 )
  {
    cmp = sead::TreeMapKeyImpl<sead::SafeStringBase<char>>::compare(
            (sead::SafeString *)a3 + 2,
            (sead::SafeString *)a2 + 2);
    if ( cmp & 0x80000000 )
    {
      *((_QWORD *)v4 + 1) = sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(
                              a1,
                              *((void **)v4 + 1),
                              v3);
      j = (void *)*((_QWORD *)v4 + 2);
      if ( !j )
        goto label1;
    }
    else if ( cmp )
    {
      *((_QWORD *)v4 + 2) = sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(
                              a1,
                              *((void **)v4 + 2),
                              v3);
      j = (void *)*((_QWORD *)v4 + 2);
      if ( !j )
        goto label1;
    }
    else
    {
      if ( v4 != v3 )
      {
        *((_QWORD *)v3 + 2) = *((_QWORD *)v4 + 2);
        *((_QWORD *)v3 + 1) = *((_QWORD *)v4 + 1);
        *((_QWORD *)v3 + 3) = *((_QWORD *)v4 + 3);
        (*(void (__fastcall **)(void *))(*(_QWORD *)v4 + 16LL))(v4);
        v4 = v3;
      }
      j = (void *)*((_QWORD *)v4 + 2);
      if ( !j )
        goto label1;
    }


    if ( !(*((_BYTE *)j + 24) & 1) )
    {
      v8 = *((_QWORD *)v4 + 1);
      if ( !v8 || *(_BYTE *)(v8 + 24) & 1 )
      {
        *((_QWORD *)v4 + 2) = *((_QWORD *)j + 1);
        *((_QWORD *)j + 1) = v4;
        *((_QWORD *)j + 3) = *((_QWORD *)v4 + 3);
        *((_QWORD *)v4 + 3) = 0LL;
        v3 = (void *)*((_QWORD *)j + 1);
        if ( !v3 )
          return j;
label2:
        if ( *((_BYTE *)v3 + 24) & 1 || (m = *((_QWORD *)v3 + 1)) == 0 )
        {
          k = v3;
          if ( *((_BYTE *)v3 + 24) & 1 )
            return j;
        }
        else
        {
          if ( *(_BYTE *)(m + 24) & 1 )
          {
            k = v3;
          }
          else
          {
            *((_QWORD *)j + 1) = *((_QWORD *)v3 + 2);
            *((_QWORD *)v3 + 2) = j;
            *((_QWORD *)v3 + 3) = *((_QWORD *)j + 3);
            *((_QWORD *)j + 3) = 0LL;
            k = (_BYTE *)*((_QWORD *)v3 + 1);
            j = v3;
            if ( !k )
              return v3;
          }
          if ( k[24] & 1 )
            return j;
        }

        v11 = *((_QWORD *)j + 2);
        if ( !v11 || *(_BYTE *)(v11 + 24) & 1 )
          return j;

        *((_QWORD *)j + 3) ^= 1uLL;
        *((_QWORD *)k + 3) ^= 1uLL;
        *(_QWORD *)(*((_QWORD *)j + 2) + 24LL) ^= 1uLL;
        return j;
      }
    }
label1:
    j = v4;
    v3 = (void *)*((_QWORD *)v4 + 1);
    if ( !v3 )
      return j;
    goto label2;
  }

  *((_QWORD *)a3 + 2) = 0LL;
  *((_QWORD *)a3 + 3) = 0LL;
  *((_QWORD *)a3 + 1) = 0LL;
  return v3;
}

Because of all those ugly casts, the pseudocode isn’t very readable yet, but it is already clear that a2 and a3 are both pointers to nodes. The binary search at the beginning and the boolean at offset 0x18 in nodes suggest that TreeMapImpl in fact implements a red-black tree.

With this in mind, structures can now be defined in IDA to make the output easier to read:

template <typename Key>
class TreeMapImpl
{
public:
    using Node = TreeMapNode<Key>;
    Node* insert(Node* root, Node* node);
    // ...
};

template <typename Key>
class TreeMapNode
{
public:
    virtual ~TreeMapNode() = default;
    virtual void erase_() = 0;
    // ...

protected:
    friend class TreeMapImpl<Key>;

    enum class Color : u64
    {
        Red = 0,
        Black = 1,
    };

    TreeMapNode* mLeft;
    TreeMapNode* mRight;
    Color mColor;
    Key mKey;
};

Well, I cannot exactly define them like that since IDA and Hex-Rays do not really support C++. Note that when C++ classes are C-ified, the pointer to the virtual table (or vtable) has to be added manually. After defining sead::TreeMapNode_SafeString and renaming variables, re-running the decompiler yields the following output:

sead::TreeMapNode_SafeString *__fastcall sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(sead::TreeMapImpl_SafeString *this, sead::TreeMapNode_SafeString *root, sead::TreeMapNode_SafeString *node)
{
  // [COLLAPSED LOCAL DECLARATIONS. PRESS KEYPAD CTRL-"+" TO EXPAND]

  n = node;
  r = root;
  if ( root )
  {
    cmp = sead::TreeMapKeyImpl<sead::SafeStringBase<char>>::compare(&node->mKey, &root->mKey);
    if ( cmp & 0x80000000 )
    {
      r->mLeft = sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(this, r->mLeft, n);
      j = r->mRight;
      if ( !j )
        goto step2;
    }
    else if ( cmp )
    {
      r->mRight = sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char>>>::insert(this, r->mRight, n);
      j = r->mRight;
      if ( !j )
        goto step2;
    }
    else
    {
      if ( r != n )
      {
        n->mRight = r->mRight;
        n->mLeft = r->mLeft;
        n->mColor = r->mColor;
        r->vtable->erase_(r);
        r = n;
      }
      j = r->mRight;
      if ( !j )
        goto step2;
    }


    if ( !(j->mColor & 1) )
    {
      v8 = r->mLeft;
      if ( !v8 || v8->mColor & 1 )
      {
        r->mRight = j->mLeft;
        j->mLeft = r;
        j->mColor = r->mColor;
        r->mColor = 0LL;
        n = j->mLeft;
        if ( !n )
          return j;
step3:
        if ( n->mColor & 1 || (nLeft = n->mLeft) == 0LL )
        {
          k = n;
          if ( n->mColor & 1 )
            return j;
        }
        else
        {
          if ( nLeft->mColor & 1 )
          {
            k = n;
          }
          else
          {
            j->mLeft = n->mRight;
            n->mRight = j;
            n->mColor = j->mColor;
            j->mColor = 0LL;
            k = n->mLeft;
            j = n;
            if ( !k )
              return n;
          }
          if ( k->mColor & 1 )
            return j;
        }

        v11 = j->mRight;
        if ( !v11 || v11->mColor & 1 )
          return j;

        j->mColor ^= 1uLL;
        k->mColor ^= 1uLL;
        j->mRight->mColor ^= 1uLL;
        return j;
      }
    }
step2:
    j = r;
    n = r->mLeft;
    if ( !n )
      return j;
    goto step3;
  }

  node->mRight = 0LL;
  node->mColor = 0LL;
  node->mLeft = 0LL;
  return n;
}

Much better! Now I can actually implement TreeMapImpl<K>::insert and try to make it match…

A first attempt #

While Hex-Rays appears to focus on readability more than on accuracy when compared to decompilers like mips_to_c, the generated pseudocode is usually still a good starting point.

This might seem counterintuitive, but manually applying a couple of optimization prettification passes often goes a long way towards getting a matching version. This is what I obtained after applying transformations like returning early and deduplicating common code paths:

template <typename Key>
TreeMapNode<Key>* TreeMapImpl<Key>::insert(Node* root, Node* node)
{
    if (!root)
    {
        node->mLeft = node->mRight = nullptr;
        node->mColor = Node::Color::Red;
        return node;
    }

    const s32 cmp = node->key().compare(root->key());

    if (cmp < 0)
    {
        root->mLeft = insert(root->mLeft, node);
    }
    else if (cmp > 0)
    {
        root->mRight = insert(root->mRight, node);
    }
    else if (root != node)
    {
        node->mRight = root->mRight;
        node->mLeft = root->mLeft;
        node->mColor = root->mColor;
        root->erase_();
        root = node;
    }

    Node* j = root->mRight;
    if (j && j->isRed() && (!root->mLeft || !root->mLeft->isRed()))
    {
        root->mRight = j->mLeft;
        j->mLeft = root;
        j->mColor = root->mColor;
        root->mColor = Node::Color::Red;
    }
    else
    {
        j = root;
    }

    node = j->mLeft;
    Node* k;
    if (!node || !node->isRed() || !node->mLeft || !node->mLeft->isRed())
    {
        k = node;
    }
    else
    {
        j->mLeft = node->mRight;
        node->mRight = j;
        node->mColor = j->mColor;
        j->mColor = Node::Color::Red;
        k = node->mLeft;
        j = node;
    }

    if (!k || !k->isRed())
        return j;

    if (!j->mRight || !j->mRight->isRed())
        return j;

    j->flipColor();
    k->flipColor();
    j->mRight->flipColor();
    return j;
}

…where flipColor and isRed are defined as follows:

    void flipColor() { mColor = Color(u64(mColor) ^ 1u); }
    bool isRed() const { return (u8(mColor) & 1u) == bool(Color::Red); }

This version isn’t ideal considering that there are still ugly j and k variables that probably don’t exist in the original code, but all the gotos are gone and it almost matches the original function. Promising. This can be seen by using simonlindholm’s asm-differ, which is an amazing tool for comparing assembly:

                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:200
                                                    |         j->mColor = Node::Color::Red;
a5ddb0:    str     xzr, [x8, #0x18]                 2a718:    str     xzr, [x8, #0x18]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:201
                                                    |         k = node->mLeft;
a5ddb4:    ldr     x9, [x19, #8]                    2a71c:    ldr     x9, [x19, #8]
a5ddb8:    mov     x8, x19                        <     
a5ddbc:    cbnz    x9, a5ddd8 ~>                  <     
a5ddc0:    b       a5de1c   ~>                    <     
a5ddc4: ~> mov     x9, x19                        | 2a720:    cbz     x9, 2a778 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
a5ddc8:    ldrb    w10, [x9, #0x18]                 2a724:    ldrb    w10, [x9, #0x18]
a5ddcc:    tbz     w10, #0, a5dde0 ~>               2a728:    tbz     w10, #0, 2a73c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x154> ~>
a5ddd0:    b       a5de18   ~>                    i 2a72c:    b       2a778    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
a5ddd4: ~> mov     x9, x19                          2a730: ~> mov     x9, x19
a5ddd8: ~> ldrb    w10, [x9, #0x18]               | 2a734:    mov     x19, x8 
a5dddc:    tbnz    w10, #0, a5de18 ~>             i 2a738:    tbnz    w10, #0, 2a778 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:208
                                                    |     }
                                                    | 
                                                    |     if (!k || !k->isRed())
                                                    |         return j;
                                                    | 
                                                    |     if (!j->mRight || !j->mRight->isRed())
a5dde0: ~> ldr     x10, [x8, #0x10]               r 2a73c: ~> ldr     x8, [x19, #0x10]
a5dde4:    cbz     x10, a5de18 ~>                 r 2a740:    cbz     x8, 2a778 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
                                                    bool sead::BitUtil::bitCastPtr<bool>(void const*, long)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/prim/seadBitUtil.h:35
a5dde8:    ldrb    w10, [x10, #0x18]              r 2a744:    ldrb    w10, [x8, #0x18]
a5ddec:    tbnz    w10, #0, a5de18 ~>             i 2a748:    tbnz    w10, #0, 2a778 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::flipColor()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:62
                                                    |     void flipColor() { mColor = Color(size_t(mColor) ^ 1u); }
a5ddf0:    ldr     x10, [x8, #0x18]               r 2a74c:    ldr     x10, [x19, #0x18]
a5ddf4:    eor     x10, x10, #0x1                   2a750:    eor     x10, x10, #0x1
a5ddf8:    str     x10, [x8, #0x18]               r 2a754:    str     x10, [x19, #0x18]
a5ddfc:    ldr     x10, [x9, #0x18]                 2a758:    ldr     x10, [x9, #0x18]
a5de00:    eor     x10, x10, #0x1                   2a75c:    eor     x10, x10, #0x1
a5de04:    str     x10, [x9, #0x18]                 2a760:    str     x10, [x9, #0x18]
a5de08:    ldr     x9, [x8, #0x10]                <     
a5de0c:    ldr     x10, [x9, #0x18]               r 2a764:    ldr     x9, [x8, #0x18]
a5de10:    eor     x10, x10, #0x1                 r 2a768:    eor     x9, x9, #0x1
a5de14:    str     x10, [x9, #0x18]               r 2a76c:    str     x9, [x8, #0x18]
                                                  > 2a770:    b       2a778    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x190> ~>
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
a5de18: ~> mov     x19, x8                          2a774: ~> mov     x19, x8
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:215 (discriminator 1)
                                                    | 
                                                    |     j->flipColor();
                                                    |     k->flipColor();
                                                    |     j->mRight->flipColor();
                                                    |     return j;
                                                    | }
a5de1c: ~> mov     x0, x19                          2a778: ~> mov     x0, x19
a5de20:    ldp     x29, x30, [sp, #0x20]            2a77c:    ldp     x29, x30, [sp, #0x20]
a5de24:    ldp     x20, x19, [sp, #0x10]            2a780:    ldp     x20, x19, [sp, #0x10]
a5de28:    ldr     x21, [sp], #0x30                 2a784:    ldr     x21, [sp], #0x30
a5de2c:    ret                                      2a788:    ret

A quick look at the end of the diff reveals two issues:

  1. Clang decided to invert the jump condition (at a5ddb8 on the left): instead of jumping if node->mLeft is not null, the second version branches if it is;
  2. The original code unnecessarily reloads j->mRight from memory (at a5de08), which results in different register allocation in the surrounding code.

If TreeMap were not a header-only utility, I might have stopped here since it is pretty much clear that the code is semantically equivalent. In this case though, it is worth spending some more time to fix those issues.

Inverting the condition and swapping the statements for the if statement in question has absolutely zero effect: Clang generates the exact same code. How can this be fixed?

asm("") to the rescue #

In my experience, adding asm("") in random places can force Clang to generate different code. I don’t really know how that works; it seems to act as a compile-time memory barrier and sometimes also appears to inhibit some optimizations…

After several attempts, I found a combination of asm("") that works around both issues:

    asm("");
    if (!k || !k->isRed())
        return j;

    if (!j->mRight || !j->mRight->isRed())
        return j;

    j->flipColor();
    k->flipColor();
    asm("");
    j->mRight->flipColor();
    return j;

But now Clang realises that some of the if (!k) checks are redundant and merges the code paths (issue #3):

                                                    |         k = node->mLeft;
a5ddb4:    ldr     x9, [x19, #8]                    2a718:    ldr     x9, [x19, #8]
a5ddb8:    mov     x8, x19                          2a71c:    mov     x8, x19
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:205
                                                    |     asm("");
a5ddbc:    cbnz    x9, a5ddd8 ~>                  i 2a720:    cbnz    x9, 2a72c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x148> ~>
a5ddc0:    b       a5de1c   ~>                    i 2a724:    b       2a770    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x18c> ~>
a5ddc4: ~> mov     x9, x19                          2a728: ~> mov     x9, x19
                                                    bool sead::BitUtil::bitCastPtr<bool>(void const*, long)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/prim/seadBitUtil.h:35
a5ddc8:    ldrb    w10, [x9, #0x18]                 2a72c: ~> ldrb    w10, [x9, #0x18]
a5ddcc:    tbz     w10, #0, a5dde0 ~>             <     
a5ddd0:    b       a5de18   ~>                    <     
a5ddd4: ~> mov     x9, x19                        <     
a5ddd8: ~> ldrb    w10, [x9, #0x18]               <     
a5dddc:    tbnz    w10, #0, a5de18 ~>               2a730:    tbnz    w10, #0, 2a76c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x188> ~>

Unfortunately, further simplifying the control flow or doing the exact opposite – reduplicating some of the checks and returns – does nothing to solve that new problem; Clang emits almost identical code every time.

Function outlining #

Another thing that usually helps when doing sead/BotW decomp is imagining how a typical C++ developer would have written the code and extracting bits of code into smaller functions to make the code cleaner. In other words: refactoring.

Given that this is red-black tree stuff, it seems natural to introduce the following helper functions:

    // Null nodes are leaves, and all leaves are black. This also deduplicates some checks.
    static bool isRed(const TreeMapNode* node) { return node && node->isRed(); }

    TreeMapNode* rotateLeft();
    TreeMapNode* rotateRight();

After having implemented those helpers, it became obvious to me that they were used in insert(). All those !child || !child->isRed() are in fact a simple !Node::isRed(child) and the weird assignments are due to rotations changing the left and right node pointers. As you’d expect, outlining all three functions significantly improves code clarity:

template <typename Key>
TreeMapNode<Key>* TreeMapImpl<Key>::insert(Node* root, Node* node)
{
    if (!root)
    {
        node->mLeft = node->mRight = nullptr;
        node->mColor = Node::Color::Red;
        return node;
    }

    const s32 cmp = node->key().compare(root->key());

    if (cmp < 0)
    {
        root->mLeft = insert(root->mLeft, node);
    }
    else if (cmp > 0)
    {
        root->mRight = insert(root->mRight, node);
    }
    else if (root != node)
    {
        node->mRight = root->mRight;
        node->mLeft = root->mLeft;
        node->mColor = root->mColor;
        root->erase_();
        root = node;
    }

    if (Node::isRed(root->mRight) && !Node::isRed(root->mLeft))
        root = root->rotateLeft();

    if (Node::isRed(root->mLeft) && Node::isRed(root->mLeft->mLeft))
        root = root->rotateRight();

    if (Node::isRed(root->mLeft) && Node::isRed(root->mRight))
    {
        root->flipColor();
        root->mLeft->flipColor();
        root->mRight->flipColor();
    }

    return root;
}

Does it match?

<lines of matching instructions removed for brevity...>
a5dde0: ~> ldr     x10, [x8, #0x10]                 2a750: ~> ldr     x10, [x8, #0x10]
a5dde4:    cbz     x10, a5de18 ~>                 i 2a754:    cbz     x10, 2a784 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x194> ~>
a5dde8:    ldrb    w10, [x10, #0x18]              r 2a758:    ldrb    w11, [x10, #0x18]
a5ddec:    tbnz    w10, #0, a5de18 ~>             r 2a75c:    tbnz    w11, #0, 2a784 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x194> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::flipColor()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:61
                                                    |     void flipColor() { mColor = Color(size_t(mColor) ^ 1u); }
a5ddf0:    ldr     x10, [x8, #0x18]               r 2a760:    ldr     x11, [x8, #0x18]
a5ddf4:    eor     x10, x10, #0x1                 r 2a764:    eor     x11, x11, #0x1
a5ddf8:    str     x10, [x8, #0x18]               r 2a768:    str     x11, [x8, #0x18]
a5ddfc:    ldr     x10, [x9, #0x18]               r 2a76c:    ldr     x11, [x9, #0x18]
a5de00:    eor     x10, x10, #0x1                 r 2a770:    eor     x11, x11, #0x1
a5de04:    str     x10, [x9, #0x18]               r 2a774:    str     x11, [x9, #0x18]
a5de08:    ldr     x9, [x8, #0x10]                r 2a778:    ldr     x9, [x10, #0x18]
a5de0c:    ldr     x10, [x9, #0x18]               <     
a5de10:    eor     x10, x10, #0x1                 r 2a77c:    eor     x9, x9, #0x1
a5de14:    str     x10, [x9, #0x18]               r 2a780:    str     x9, [x10, #0x18]
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
a5de18: ~> mov     x19, x8                          2a784: ~> mov     x19, x8

Unfortunately, it doesn’t… While issues #1 and #3 are definitely solved now – without the use of hacks! – issue #2 (the missing memory load) has reappeared. Re-adding asm("") right before root->mRight->flipColor(); would force Clang to reload mRight from memory, but that obviously isn’t a satisfactory solution.

Furthermore, adding asm("") in TreeMapNode<T>::flipColor itself does not solve the problem as that causes another member variable to be reloaded.

A less hacky fix? #

What if, instead of casting twice manually in TreeMapNode<T>::flipColor:

    void flipColor() { mColor = Color(u64(mColor) ^ 1u); }

…Nintendo instead used some kind of bit casting utility, which would let them reinterpret the bits of one type as another type? Something like C++20’s std::bit_cast but in the opposite direction, for example:

template <typename To, typename From>
inline void bitCastWrite(const From& value, To* ptr)
{
    static_assert(sizeof(To) == sizeof(From), "To and From must have the same size");
    std::memcpy(ptr, &value, sizeof(To));
}

Surprisingly enough, replacing flipColor with

    void flipColor() { BitUtil::bitCastWrite(u64(mColor) ^ 1u, &mColor); }

does materialize the extra load. I suspect that even though the call to std::memcpy is lowered into a simple store instruction, merely calling memcpy forces Clang to assume that global memory might have been modified and to reload mRight from memory.

To be honest, I am not convinced this is the correct fix, but this is the only thing I have found so far that has made a difference and it is at least much better than an asm(""). If anyone has suggestions, please let me know!

View the final diff 
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:171
                                                    |     mRoot = insert(mRoot, node);
                                                    | }
                                                    | 
                                                    | template <typename Key>
                                                    | TreeMapNode<Key>* TreeMapImpl<Key>::insert(Node* root, Node* node)
                                                    | {
a5dc80: ~> str     x21, [sp, #-0x30]!               2a5f4: ~> str     x21, [sp, #-0x30]!
a5dc84:    stp     x20, x19, [sp, #0x10]            2a5f8:    stp     x20, x19, [sp, #0x10]
a5dc88:    stp     x29, x30, [sp, #0x20]            2a5fc:    stp     x29, x30, [sp, #0x20]
a5dc8c:    add     x29, sp, #0x20                   2a600:    add     x29, sp, #0x20
a5dc90:    mov     x19, x2                          2a604:    mov     x19, x2
a5dc94:    mov     x20, x1                          2a608:    mov     x20, x1
a5dc98:    mov     x21, x0                          2a60c:    mov     x21, x0
a5dc9c:    cbz     x20, a5dcd4 ~>                   2a610:    cbz     x20, 2a648 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x54> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::key() const
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:48
                                                    |     const Key& key() const { return mKey; }
a5dca0:    add     x0, x19, #0x20                   2a614:    add     x0, x19, #0x20
a5dca4:    add     x1, x20, #0x20                   2a618:    add     x1, x20, #0x20
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:179 (discriminator 2)
                                                    |         node->mLeft = node->mRight = nullptr;
                                                    |         node->mColor = Node::Color::Red;
                                                    |         return node;
                                                    |     }
                                                    | 
                                                    |     const s32 cmp = node->key().compare(root->key());
a5dca8:    bl      a5d4a8   ~>                    i 2a61c:    bl      16f14    <_ZNK4sead14TreeMapKeyImplINS_14SafeStringBaseIcEEE7compareERKS3_@plt> ~>
a5dcac:    tbnz    w0, #31, a5dce0 ~>               2a620:    tbnz    w0, #31, 2a654 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x60> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:185
                                                    | 
                                                    |     if (cmp < 0)
                                                    |     {
                                                    |         root->mLeft = insert(root->mLeft, node);
                                                    |     }
                                                    |     else if (cmp > 0)
a5dcb0:    cbz     w0, a5dd00 ~>                    2a624:    cbz     w0, 2a674 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x80> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:187
                                                    |     {
                                                    |         root->mRight = insert(root->mRight, node);
a5dcb4:    ldr     x1, [x20, #0x10]                 2a628:    ldr     x1, [x20, #0x10]
a5dcb8:    mov     x0, x21                          2a62c:    mov     x0, x21
a5dcbc:    mov     x2, x19                          2a630:    mov     x2, x19
a5dcc0:    bl      a5dc80   ~>                      2a634:    bl      2a5f4    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_> ~>
a5dcc4:    str     x0, [x20, #0x10]                 2a638:    str     x0, [x20, #0x10]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:198
                                                    |         node->mColor = root->mColor;
                                                    |         root->erase_();
                                                    |         root = node;
                                                    |     }
                                                    | 
                                                    |     if (Node::isRed(root->mRight) && !Node::isRed(root->mLeft))
a5dcc8:    ldr     x8, [x20, #0x10]                 2a63c:    ldr     x8, [x20, #0x10]
a5dccc:    cbnz    x8, a5dd3c ~>                    2a640:    cbnz    x8, 2a6b0 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xbc> ~>
a5dcd0:    b       a5dd54   ~>                      2a644:    b       2a6c8    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xd4> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:174
                                                    |         node->mLeft = node->mRight = nullptr;
a5dcd4: ~> stp     xzr, xzr, [x19, #0x10]           2a648: ~> stp     xzr, xzr, [x19, #0x10]
a5dcd8:    str     xzr, [x19, #8]                   2a64c:    str     xzr, [x19, #8]
a5dcdc:    b       a5de1c   ~>                      2a650:    b       2a790    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x19c> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:183
                                                    |         root->mLeft = insert(root->mLeft, node);
a5dce0: ~> ldr     x1, [x20, #8]                    2a654: ~> ldr     x1, [x20, #8]
a5dce4:    mov     x0, x21                          2a658:    mov     x0, x21
a5dce8:    mov     x2, x19                          2a65c:    mov     x2, x19
a5dcec:    bl      a5dc80   ~>                      2a660:    bl      2a5f4    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_> ~>
a5dcf0:    str     x0, [x20, #8]                    2a664:    str     x0, [x20, #8]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:198
                                                    |     if (Node::isRed(root->mRight) && !Node::isRed(root->mLeft))
a5dcf4:    ldr     x8, [x20, #0x10]                 2a668:    ldr     x8, [x20, #0x10]
a5dcf8:    cbnz    x8, a5dd3c ~>                    2a66c:    cbnz    x8, 2a6b0 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xbc> ~>
a5dcfc:    b       a5dd54   ~>                      2a670:    b       2a6c8    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xd4> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:189
                                                    |     else if (root != node)
a5dd00: ~> cmp     x20, x19                         2a674: ~> cmp     x20, x19
a5dd04:    b.eq    a5dd34   ~>                      2a678:    b.eq    2a6a8    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xb4> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:191
                                                    |         node->mRight = root->mRight;
a5dd08:    ldr     x8, [x20, #0x10]                 2a67c:    ldr     x8, [x20, #0x10]
a5dd0c:    str     x8, [x19, #0x10]                 2a680:    str     x8, [x19, #0x10]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:192
                                                    |         node->mLeft = root->mLeft;
a5dd10:    ldr     x8, [x20, #8]                    2a684:    ldr     x8, [x20, #8]
a5dd14:    str     x8, [x19, #8]                    2a688:    str     x8, [x19, #8]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:193
                                                    |         node->mColor = root->mColor;
a5dd18:    ldr     x8, [x20, #0x18]                 2a68c:    ldr     x8, [x20, #0x18]
a5dd1c:    str     x8, [x19, #0x18]                 2a690:    str     x8, [x19, #0x18]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:194
                                                    |         root->erase_();
a5dd20:    ldr     x8, [x20]                        2a694:    ldr     x8, [x20]
a5dd24:    ldr     x8, [x8, #0x10]                  2a698:    ldr     x8, [x8, #0x10]
a5dd28:    mov     x0, x20                          2a69c:    mov     x0, x20
a5dd2c:    blr     x8                               2a6a0:    blr     x8
a5dd30:    mov     x20, x19                         2a6a4:    mov     x20, x19
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:198
                                                    |     if (Node::isRed(root->mRight) && !Node::isRed(root->mLeft))
a5dd34: ~> ldr     x8, [x20, #0x10]                 2a6a8: ~> ldr     x8, [x20, #0x10]
a5dd38:    cbz     x8, a5dd54 ~>                    2a6ac:    cbz     x8, 2a6c8 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xd4> ~>
a5dd3c: ~> ldrb    w9, [x8, #0x18]                  2a6b0: ~> ldrb    w9, [x8, #0x18]
a5dd40:    tbnz    w9, #0, a5dd54 ~>                2a6b4:    tbnz    w9, #0, 2a6c8 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xd4> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:198 (discriminator 1)
a5dd44:    ldr     x9, [x20, #8]                    2a6b8:    ldr     x9, [x20, #8]
a5dd48:    cbz     x9, a5dd64 ~>                    2a6bc:    cbz     x9, 2a6d8 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xe4> ~>
a5dd4c:    ldrb    w9, [x9, #0x18]                  2a6c0:    ldrb    w9, [x9, #0x18]
a5dd50:    tbnz    w9, #0, a5dd64 ~>                2a6c4:    tbnz    w9, #0, 2a6d8 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0xe4> ~>
a5dd54: ~> mov     x8, x20                          2a6c8: ~> mov     x8, x20
a5dd58:    ldr     x19, [x8, #8]                    2a6cc:    ldr     x19, [x8, #8]
a5dd5c:    cbnz    x19, a5dd84 ~>                   2a6d0:    cbnz    x19, 2a6f8 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x104> ~>
a5dd60:    b       a5de18   ~>                      2a6d4:    b       2a78c    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::rotateLeft()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:145
                                                    |     mRight = j->mLeft;
a5dd64: ~> ldr     x9, [x8, #8]                     2a6d8: ~> ldr     x9, [x8, #8]
a5dd68:    str     x9, [x20, #0x10]                 2a6dc:    str     x9, [x20, #0x10]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:146
                                                    |     j->mLeft = this;
a5dd6c:    str     x20, [x8, #8]                    2a6e0:    str     x20, [x8, #8]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:147
                                                    |     j->mColor = mColor;
a5dd70:    ldr     x9, [x20, #0x18]                 2a6e4:    ldr     x9, [x20, #0x18]
a5dd74:    str     x9, [x8, #0x18]                  2a6e8:    str     x9, [x8, #0x18]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:148
                                                    |     mColor = Color::Red;
a5dd78:    str     xzr, [x20, #0x18]                2a6ec:    str     xzr, [x20, #0x18]
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:201
                                                    |         root = root->rotateLeft();
                                                    | 
                                                    |     if (Node::isRed(root->mLeft) && Node::isRed(root->mLeft->mLeft))
a5dd7c:    ldr     x19, [x8, #8]                    2a6f0:    ldr     x19, [x8, #8]
a5dd80:    cbz     x19, a5de18 ~>                   2a6f4:    cbz     x19, 2a78c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
a5dd84: ~> ldrb    w9, [x19, #0x18]                 2a6f8: ~> ldrb    w9, [x19, #0x18]
a5dd88:    tbnz    w9, #0, a5ddc4 ~>                2a6fc:    tbnz    w9, #0, 2a738 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x144> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:201 (discriminator 1)
a5dd8c:    ldr     x9, [x19, #8]                    2a700:    ldr     x9, [x19, #8]
a5dd90:    cbz     x9, a5ddc4 ~>                    2a704:    cbz     x9, 2a738 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x144> ~>
a5dd94:    ldrb    w9, [x9, #0x18]                  2a708:    ldrb    w9, [x9, #0x18]
a5dd98:    tbnz    w9, #0, a5ddd4 ~>                2a70c:    tbnz    w9, #0, 2a748 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x154> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::rotateRight()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:156
                                                    |     mLeft = j->mRight;
a5dd9c:    ldr     x9, [x19, #0x10]                 2a710:    ldr     x9, [x19, #0x10]
a5dda0:    str     x9, [x8, #8]                     2a714:    str     x9, [x8, #8]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:157
                                                    |     j->mRight = this;
a5dda4:    str     x8, [x19, #0x10]                 2a718:    str     x8, [x19, #0x10]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:158
                                                    |     j->mColor = mColor;
a5dda8:    ldr     x9, [x8, #0x18]                  2a71c:    ldr     x9, [x8, #0x18]
a5ddac:    str     x9, [x19, #0x18]                 2a720:    str     x9, [x19, #0x18]
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:159
                                                    |     mColor = Color::Red;
a5ddb0:    str     xzr, [x8, #0x18]                 2a724:    str     xzr, [x8, #0x18]
a5ddb4:    ldr     x9, [x19, #8]                    2a728:    ldr     x9, [x19, #8]
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
a5ddb8:    mov     x8, x19                          2a72c:    mov     x8, x19
a5ddbc:    cbnz    x9, a5ddd8 ~>                    2a730:    cbnz    x9, 2a74c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x158> ~>
a5ddc0:    b       a5de1c   ~>                      2a734:    b       2a790    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x19c> ~>
a5ddc4: ~> mov     x9, x19                          2a738: ~> mov     x9, x19
a5ddc8:    ldrb    w10, [x9, #0x18]                 2a73c:    ldrb    w10, [x9, #0x18]
a5ddcc:    tbz     w10, #0, a5dde0 ~>               2a740:    tbz     w10, #0, 2a754 <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x160> ~>
a5ddd0:    b       a5de18   ~>                      2a744:    b       2a78c    <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
a5ddd4: ~> mov     x9, x19                          2a748: ~> mov     x9, x19
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:204
                                                    |         root = root->rotateRight();
                                                    | 
                                                    |     if (Node::isRed(root->mLeft) && Node::isRed(root->mRight))
a5ddd8: ~> ldrb    w10, [x9, #0x18]                 2a74c: ~> ldrb    w10, [x9, #0x18]
a5dddc:    tbnz    w10, #0, a5de18 ~>               2a750:    tbnz    w10, #0, 2a78c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:204 (discriminator 1)
a5dde0: ~> ldr     x10, [x8, #0x10]                 2a754: ~> ldr     x10, [x8, #0x10]
a5dde4:    cbz     x10, a5de18 ~>                   2a758:    cbz     x10, 2a78c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
a5dde8:    ldrb    w10, [x10, #0x18]                2a75c:    ldrb    w10, [x10, #0x18]
a5ddec:    tbnz    w10, #0, a5de18 ~>               2a760:    tbnz    w10, #0, 2a78c <_ZN4sead11TreeMapImplINS_14TreeMapKeyImplINS_14SafeStringBaseIcEEEEE6insertEPNS_11TreeMapNodeIS4_EES8_+0x198> ~>
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::flipColor()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:62
                                                    |     void flipColor() { BitUtil::bitCastWrite(u64(mColor) ^ 1u, &mColor); }
a5ddf0:    ldr     x10, [x8, #0x18]                 2a764:    ldr     x10, [x8, #0x18]
a5ddf4:    eor     x10, x10, #0x1                   2a768:    eor     x10, x10, #0x1
                                                    void sead::BitUtil::bitCastWrite<sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color, unsigned long>(unsigned long const&, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/prim/seadBitUtil.h:45
                                                    | // Nintendo appears to perform type punning, but we care about UB.
                                                    | template <typename To, typename From>
                                                    | inline void bitCastWrite(const From& value, To* ptr)
                                                    | {
                                                    |     static_assert(sizeof(To) == sizeof(From), "To and From must have the same size");
                                                    |     std::memcpy(ptr, &value, sizeof(To));
a5ddf8:    str     x10, [x8, #0x18]                 2a76c:    str     x10, [x8, #0x18]
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::flipColor()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:62
a5ddfc:    ldr     x10, [x9, #0x18]                 2a770:    ldr     x10, [x9, #0x18]
a5de00:    eor     x10, x10, #0x1                   2a774:    eor     x10, x10, #0x1
                                                    void sead::BitUtil::bitCastWrite<sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color, unsigned long>(unsigned long const&, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/prim/seadBitUtil.h:45
a5de04:    str     x10, [x9, #0x18]                 2a778:    str     x10, [x9, #0x18]
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:208
                                                    |     {
                                                    |         root->flipColor();
                                                    |         root->mLeft->flipColor();
                                                    |         root->mRight->flipColor();
a5de08:    ldr     x9, [x8, #0x10]                  2a77c:    ldr     x9, [x8, #0x10]
                                                    sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::flipColor()
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:62
                                                    |     void flipColor() { BitUtil::bitCastWrite(u64(mColor) ^ 1u, &mColor); }
a5de0c:    ldr     x10, [x9, #0x18]                 2a780:    ldr     x10, [x9, #0x18]
a5de10:    eor     x10, x10, #0x1                   2a784:    eor     x10, x10, #0x1
                                                    void sead::BitUtil::bitCastWrite<sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color, unsigned long>(unsigned long const&, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::Color*)
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/prim/seadBitUtil.h:45
a5de14:    str     x10, [x9, #0x18]                 2a788:    str     x10, [x9, #0x18]
                                                    sead::TreeMapImpl<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >::insert(sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*, sead::TreeMapNode<sead::TreeMapKeyImpl<sead::SafeStringBase<char> > >*)
a5de18: ~> mov     x19, x8                          2a78c: ~> mov     x19, x8
                                                    /home/leo/projects/uking/build/nx64-develop/../../lib/sead/include/container/seadTreeMap.h:212 (discriminator 1)
                                                    |     }
                                                    | 
                                                    |     return root;
                                                    | }
a5de1c: ~> mov     x0, x19                          2a790: ~> mov     x0, x19
a5de20:    ldp     x29, x30, [sp, #0x20]            2a794:    ldp     x29, x30, [sp, #0x20]
a5de24:    ldp     x20, x19, [sp, #0x10]            2a798:    ldp     x20, x19, [sp, #0x10]
a5de28:    ldr     x21, [sp], #0x30                 2a79c:    ldr     x21, [sp], #0x30
a5de2c:    ret                                      2a7a0:    ret

  1. See github.com/zeldaret/oot for an example. ↩︎

  2. Code that perfectly matches the original assembly. Non-matching code is usually semantically equivalent to the original code but differs in register allocation, instruction ordering, etc. ↩︎

  3. All known available versions of BotW are stripped, but it is possible to recover some symbols by diffing BotW and an unstripped game that uses sead (e.g. Super Mario Odyssey, Splatoon 2 or even Nintendo Labo for a debug build). That isn’t perfect, but it’s better than nothing. ↩︎

2020-08-06