IDO BSS Reordering

The purpose of this document is to provide information on how the IDO compiler reorders BSS, and ways to deal with it in the context of matching decompilation (with and without -g3).

What is BSS?

If you're already familiar with BSS or the output of a compiler in general, you can skip this section, but otherwise here is a summary of the parts relevant to matching decompilation:

When compiling files, the C compiler outputs data into various sections depending on their purpose. For IDO, there are 4 relevant sections:

• .text for generated machine code
• .data and .bss for statically allocated variables
• .rodata for read-only data (ex: string constants)

In the context of this document, BSS refers to the .bss section which contains statically allocated variables that do not have an initial value (as opposed to the .data section which contains initialized variables). In a C file, this corresponds to any global or static variable that is declared without being set to a value.

int gFoo = 30; // -> .data
int gBar; // -> .bss

static int sFoo = 20; // -> .data
static int sBar; // -> .bss

// .text
void foobar() {
    static int sBaz = 10; // -> .data
    static int sQux; // -> .bss
    int frog; // -> stack or register

    ...
}

Note that in practice .bss is usually initialized to 0 by the program, so you can also treat this section as zero-initialized data. Some compilers might even put variables set to 0 in it when configured to do so, although IDO doesn't.

BSS Ordering with IDO

Since relying on the order of separate variables is undefined behaviour in C, the compiler is free to order variables in .bss as it wants. Normally, IDO simply keeps them in source order, just like it does for .data. However, in the case of BSS, IDO is known to reorder variables which can cause issues when trying to match the original order.

Essentially, the IDO compiler sorts bss variables by their "block index" mod 256. The "block index" (aka. "name index" or "dense number") is a unique number used by the compiler internally and assigned to each variable as well as various over things. The index starts at 1 and is incremented while going through the C file in source order. As for what actually increments the index, it heavily depends on the debug flag used (eg. using -g3 or not).

Without -g3, only a few specific things will increment it. Here is a list of known ones (possibly incomplete):

• BSS Variable declarations
• External references (ie. referencing a variable from another file)
• Uses of the #line directive with a filename (at least the first time)

With -g3, a lot more stuff will increment it. Here are a few notable examples:

• Type or struct definitions (typedefs, structs, etc)
• Extern declarations (using the keyword extern)
• Variable declarations

In general, we refer to this index as the "bss index" since it's only relevant for bss as far as we're concerned (but it's used for other things by the compiler internally).

---

A common misconception is that bss reordering only happens with -g3, but that's not true. It's simply a lot less common without it because files are unlikely to have the bss index go over 255, so no reordering happens. Furthermore, it's also a lot more difficult to deal with when it happens since there aren't as many ways to manipulate the index.

Also, something very important to note is that, with -g3, the index affected to a variable is determined on the first extern of that variable, if there are any. This means that a group of variables might end up with very different indexes depending on if they have externs or not, even if they are all declared together.

Lastly, it's worth noting for projects that use asm_processor that it always adds at least one #line directive to the file as part of its process, so using it increases the initial bss index by 1, which can be important.

Preventing reorderings

Usually, matching the original order of bss variables can be done by simply laying out the variables in that order. In this case, we just need to prevent any reordering from happening during the build.

Sometimes this is not possible and we have to reproduce a specific reordering, for example when in-function static variables are involved and we can't simply order variables as we want, but this will be covered later as it's a bit more involved.

With -g3

In order to prevent BSS reorderings when using -g3, the most common approach is to use some kind of prevent_bss_reordering.h file (for example in MM). This file essentially shifts (ie. bumps) the bss index by 128 when you include it, due to the specific amount of struct/typedef it contains.
The idea is that if a C file runs into bss reordering, that means it's reaching a bss index 256 boundary, so adding this header can shift everything up by 128 and put it in a position where it doesn't reach a boundary and thus doesn't shift. Also, since changes in headers can change the index when -g3 is used, a file that includes this header might end up with bss reordering again later, in which case the header can be removed to shift everything down by 128 and achieve a similar result.

This approach works in simple cases, but there are a few issues with it. First, it assumes the bss index difference between the first and last bss variable in the file is smaller than 128. This is often the case since you can usually group bss variables together and there are rarely more than 128 bss variables in a file, but it's not always possible (eg. with in-function static variables). Secondly, it doesn't always work in cases where there is a mix of variables with and without corresponding externs.
But when it works it's pretty good, and the only caveat is having to add or remove the include when headers are changed, although even that can be automated if it's an issue.

Without -g3

It's pretty rare to have to prevent BSS reordering when not using -g3, since files that run into reordering once decompiled very likely had a reordering in the original build, in which case we need to reproduce the specific reordering (which will be covered later).

However, it can still be needed for some files. But since there is no generic way to increment the bss index like prevent_bss_reordering.h without -g3, the only known solution is to use one or more of the methods mentioned below (TODO). One example would be to add references to external variables inside a if (0) {} block, if it's compatible with codegen.

Forcing a specific reordering

TODO (with and w/o -g3)

Visualizing BSS indexes

TODO guide on how to use ido-ucode-utils

Reference documents

MIPS Language Guide: https://www.cs.unibo.it/~solmi/teaching/arch_2002-2003/AssemblyLanguageProgDoc.pdf
IDO CC man page: https://cocky-wescoff-177c47.netlify.app/cc_manual.html