Skip to content
STIMSMITH

Stack slot permutation for locals

Technique WIKI v1 · 9/21/2026

An assembly-level code-transformation technique in which the stack locations assigned to distinct local variables are reordered (permuted) provided that every read and write to those variables is updated consistently, so the program's observable data flow is preserved.

Stack slot permutation for locals

Stack slot permutation for locals is an instruction-level equivalence technique used when generating, transpiling, or validating low-level code (notably ARM assembly). It exploits the freedom a compiler or transpiler has to assign distinct local variables to distinct stack frame offsets, because the program remains semantically correct as long as every store and load that targets a given logical local variable is redirected to the same new offset.

How it works

A typical ARM stack frame uses the frame pointer (fp) plus a negative offset to address each local, e.g. str r1, [fp, #-8] and str r2, [fp, #-12]. Under the technique, the two offsets may be swapped so long as both instructions are rewritten together:

Ground truth Permuted
Store of r1 str r1, [fp, #-8] str r1, [fp, #-12]
Store of r2 str r2, [fp, #-12] str r2, [fp, #-8]

Every subsequent load that referenced the original [fp, #-8] slot must now reference the slot that holds r1, and vice versa. Because the permutation is applied uniformly across all accesses to the affected locals, the data flow of the program is unchanged.

Edit distance and identifiability

Permuting stack slots increases the textual edit distance between a reference translation and a candidate translation even though the two translations are semantically equivalent. In a published evaluation of CISC-to-RISC transpilation, one program (P8) accumulated an edit distance of 12 attributable almost entirely to a permutation of two local-variable stack slots with no change in program behavior.

Relationship to other equivalence phenomena

Stack slot permutation is one member of a broader family of equivalent instruction sequences that compilers and transpilers may legitimately emit, alongside:

  • Choosing different registers for the same temporary values (e.g., r0 vs r3).
  • Renaming compiler-generated symbols (e.g., .word out.4781 vs .word out.4280).
  • Fusing multiple instructions into a single equivalent instruction (e.g., a mov plus a store collapsing into a direct store).
  • Varying absolute stack-frame offsets while preserving the relative addressing pattern of each variable.
  • Adjusting the size of a memory allocation when the larger size still satisfies the program's needs.
  • Substituting entirely different instruction sequences that compute the same logical result.
  • Loading a constant directly versus loading it from a literal pool.

All of these phenomena are forms of equivalent instruction sequences under which a stack slot permutation is classified.

Role in CISC-to-RISC transpilation

The technique has been observed as a characteristic of valid ARM translations produced by language-model-based CISC-to-RISC transpilers. Recognizing stack slot permutation — together with the other equivalent-sequence phenomena above — is important when scoring candidate translations, because naïvely penalizing edit distance would mark perfectly correct transpilations as erroneous.

Target ISA

Stack slot permutation is most naturally described for the ARM instruction set, where local-variable storage conventionally uses [fp, #offset] addressing and offsets are negatives from the frame pointer.

LINKED ENTITIES

2 links
ARM TARGETS_ISA
Equivalent instruction sequences PART_OF

CITATIONS

8 sources
8 citations
[1] Local variables can be stored at different stack locations while maintaining correct access patterns, demonstrated by swapping the offsets of two stores (P8, edit distance 12). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[2] Stack frame offsets can vary while maintaining correct variable access, shown by ground truth strb r3, [fp, #-21] vs predicted strb r3, [fp, #-17] (P162, edit distance 4). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[3] Different registers can be chosen for temporary values while maintaining same data flow, e.g., mov r2 vs mov r3 (P108, edit distance 16). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[4] Multiple instructions can be combined into a single equivalent instruction, e.g., mov r3, r0; str r3, [fp, #-8] collapsing to str r0, [fp, #-8] (P135, edit distance 12). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[5] Memory allocation sizes can vary if sufficient for program needs, e.g., mov r0, #400 vs mov r0, #800 (P88, edit distance 23). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[6] Different instruction sequences can achieve the same logical result, e.g., cmp/and/rsblt vs rsbs/and/and/rsbpl (P103, edit distance 52). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[7] Constants can be loaded directly or from a literal pool, e.g., mvn r3, #-2147483648 vs ldr r3, .L8; .L8: .word 2147483647 (P69, edit distance 50). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees
[8] Compiler-generated symbol names can differ while referring to the same data, e.g., .word out.4781 vs .word out.4280 (P119, edit distance 6). Guaranteed Guess: A Language Modeling Approach for CISC-to-RISC Transpilation with Testing Guarantees