Assembly Language and Code Generation Questions

Knowledge and practical skill reading and writing assembly language for relevant instruction set architectures such as ARM Thumb, RISC V, or x86. Core topics include calling conventions and application binary interface details, stack frame layout and management, register usage and allocation, function prologue and epilogue, position independent code and linking, object file and symbol concepts, inline assembly and writing callable assembly routines, and how high level language constructs map to generated code. Candidates should understand compiler backends and optimization passes, how optimization levels change generated code, how inlining, loop transformation, and instruction selection affect performance, and techniques for optimizing critical sections with hand written assembly when appropriate. Familiarity with toolchain behaviors such as assembler and linker flags, compiler diagnostics about generated code, and basic conventions for calling into and out of assembly from higher level languages is expected.

MediumTechnical

40 practiced

Compare and contrast graph-coloring and linear-scan register allocation algorithms. Describe how each constructs live ranges, performs coalescing and spilling, their compile-time complexity, and why JITs often prefer linear-scan while AOT compilers sometimes favor graph-coloring.

Sample Answer

Situation/Overview: Both graph-coloring and linear-scan solve the same problem—map an unbounded number of SSA or virtual registers to a fixed set of physical registers— but they trade compilation time, optimality, and implementation complexity differently.

Live ranges:- Graph-coloring: Builds an interference graph where nodes = live ranges (usually after liveness analysis on a control-flow graph), and an edge means two ranges overlap at some program point. Live ranges can be arbitrary (noncontiguous) and are computed precisely across basic blocks.- Linear-scan: Computes live intervals by numbering instructions (or using linearized code / trace) and recording for each virtual register the start and end positions where it is live. Intervals are typically contiguous per linearization; noncontiguous liveness requires splitting into multiple intervals.

Coalescing:- Graph-coloring: Can use optimistic/coalescing heuristics (Briggs, George) on the interference graph to remove move-related nodes if they don't create spills—more global, can consider many alternatives.- Linear-scan: Performs local/coarse coalescing by merging intervals when safe (usually when no overlap). Simpler and faster but less aggressive; some implementations do interval splitting to enable more coalescing.

Spilling:- Graph-coloring: Decides spills via select/heuristic phases—pick low-cost nodes to remove (spill candidates), rewrite code to load/store spilled temps, then re-run coloring. More global view yields better spill choices often producing fewer loads/stores.- Linear-scan: Chooses spills at runtime of allocation: when no free register, pick the interval with farthest next use (or longest remaining live) to spill or spill the newly starting interval. Spilling decisions are greedy and local, simpler but can cause suboptimal spill placement; interval splitting reduces impact.

Compile-time complexity:- Graph-coloring: Generally higher; exact coloring is NP-complete, practical algorithms use heuristic simplification/select and can be O(n^2) or worse in practice for dense graphs. More memory and time overhead.- Linear-scan: Linear or near-linear time in number of intervals/positions (O(n log k) with sorting by start and maintaining active set). Low constant factors.

Why JITs prefer linear-scan:- Low compilation latency and predictable, low memory use are critical for JITs. Linear-scan is fast, simple to implement on streaming code, integrates well with tiered compilation and on-stack-replacement, and produces "good enough" code quickly. Its greedy nature and interval-splitting suit dynamic code generation where compile budget is tight.

Why AOT compilers sometimes favor graph-coloring:- AOT has larger compile budgets and benefits from better register utilization and fewer spills—improving runtime performance. Graph-coloring’s global view, sophisticated coalescing and spill minimization can yield measurably faster generated code for hot, long-running programs where compile time is acceptable.

Trade-offs summary:- Graph-coloring: Higher quality allocations, more complex and slower.- Linear-scan: Faster, simpler, lower-quality in worst cases but excellent for JIT constraints.

EasyTechnical

45 practiced

Write a callable assembly function on x86-64 (Intel syntax) that takes two 64-bit integers and returns their sum. Use the System V AMD64 ABI; provide the assembly implementation and the corresponding C declaration (e.g., uint64_t add(uint64_t a, uint64_t b);). Keep it minimal and correct with respect to ABI-preserved registers.

Sample Answer

Approach: Under the System V AMD64 ABI, the first two integer/pointer arguments are passed in RDI and RSI; a 64-bit integer return value is returned in RAX. The function simply adds the two inputs and returns the sum. No callee-saved registers are used, so no preservation is necessary.

Assembly (GAS, Intel syntax):

asm

.intel_syntax noprefix
.global add
.type add, @function

# uint64_t add(uint64_t a, uint64_t b);
add:
    mov rax, rdi    # move first argument a into return register
    add rax, rsi    # add second argument b
    ret

C declaration:

#include <stdint.h>

uint64_t add(uint64_t a, uint64_t b);

Key points:- Arguments: a in RDI, b in RSI.- Return: sum in RAX.- No stack frame or callee-saved registers used, so function is minimal and ABI-correct.- Works for unsigned 64-bit wrap-around semantics; identical machine code works for signed integers if caller expects signed behavior (two's complement).

Complexity: O(1) time, O(1) space.

Edge cases:- Sum overflow wraps modulo 2^64 (expected for uint64_t). If overflow detection is needed, use ADC/SETC or check CF after addition.

MediumTechnical

38 practiced

Examine this x86-64 assembly (Intel syntax) and identify the stack frame layout: which offsets correspond to saved registers, local variables, and spilled temporaries? Explain how rbp and rsp are used and compute the offset to a local buffer placed at [rbp-0x30]. Assembly:\n\n push rbp\n mov rbp, rsp\n sub rsp, 0x50\n mov [rbp-0x10], rdi\n mov rax, [rbp-0x20]\n pop rbp\n ret\n\nAssume SysV ABI.

HardTechnical

35 practiced

Given C code with heavy pointer aliasing that prevents many optimizations (loads/stores are assumed to alias), explain how type-based alias analysis, the restrict keyword, and compiler-specific attributes (e.g., __attribute__((noalias))) can help the optimizer. Provide examples and explain how generated assembly can change when aliasing information is improved.

Sample Answer

Type-based alias analysis (TBAA), restrict, and compiler-specific noalias attributes give the compiler provable guarantees that different pointers do not refer to the same memory. That lets the optimizer reorder, combine, or eliminate loads/stores and vectorize code.

Example — ambiguous pointers (optimizer must assume aliasing):

void update(int *a, int *b) {
    *a += 1;
    *b += 2;
    *a += 3;
}

If a and b might alias, the compiler must reload *a after modifying *b. Generated code might do: load a, add 1, store a, load b, add 2, store b, load a, add 3, store a.

Improve alias info with restrict (C99) or attributes:

void update(int * restrict a, int * restrict b) {
    *a += 1;
    *b += 2;
    *a += 3;
}

Now a and b are guaranteed not to overlap; compiler can keep *a in register across the *b update:- load a -> add 4 -> store a- load b -> add 2 -> store bThis eliminates an extra load/store and reduces memory traffic and register spills.

TBAA: compilers also use type information (e.g., an int* won't alias a float* under strict rules). Correctly-typed accesses allow further optimizations. Example: accessing a struct with different member types—TBAA prevents treats accesses to distinct non-overlapping types as non-aliasing.

Compiler-specific attributes: some compilers offer __attribute__((noalias)) or __builtin_assume_aligned, or LLVM’s __restrict__ variants that express aliasing or alignment across function boundaries. Example:

int * __attribute__((noalias)) foo();

tells the compiler pointers returned by foo won’t alias other pointers, enabling interprocedural optimization.

Concrete codegen effect:- Before: three memory ops (load/store/load/store/load/store).- After restrict/TBAA: two stores and one fewer load; registers hold intermediate values; auto-vectorization becomes possible because loop-carried dependencies are eliminated.

Caveats and correctness:- Misusing restrict/noalias when pointers can actually alias is undefined behavior.- TBAA differs by compiler and ABI (use -fno-strict-aliasing disables some optimizations).- For maximal effect, combine restrict with const/inline and whole-program visibility (LTO) so the compiler can see call sites.

Conclusion: Providing precise aliasing contracts via types, restrict, and attributes reduces conservative assumptions, enabling load/store elimination, reordering, register promotion, and vectorization — measurable wins in generated assembly and runtime performance.

EasyTechnical

33 practiced

When writing inline assembly in GCC/Clang (extended asm syntax), what constraints and precautions must you specify to ensure the compiler generates correct code? Discuss input/output operands, clobber lists, the 'memory' clobber, volatile, and how incorrect constraints can cause undefined behavior.

Sample Answer

When writing extended asm in GCC/Clang you must precisely describe how the asm interacts with the compiler so it can schedule/register-allocate correctly. Key points:

- Input/output operands: declare each input ("r"(x)) and output ("=r"(out)) operand. If an asm reads and writes the same operand, use a tied operand: "0"(val) or "+r"(val) to tell the compiler it's the same location.- Early-clobber: use the '&' constraint if an output must not overlap any input (prevents the compiler from assigning the same register).- Clobber list: list any registers the asm modifies that are not listed as outputs (e.g., "cc" for flags, "rax" if you use it). Failing to list clobbers lets the compiler assume values in those registers persist → wrong code.- "memory" clobber: use this when asm reads/writes memory in ways the compiler can't see (prevents reordering/optimizations and forces loads/stores to/from memory).- "cc" clobber: declare if condition codes/flags are modified.- volatile: mark asm volatile if it must not be optimized away or reordered relative to surrounding code (e.g., I/O, barriers). Avoid volatile for merely performance-related hints.- Constraints correctness: choose appropriate constraint letters ("r", "m", "g", "i") and be careful with immediate-only or memory-only constraints.

Example:

int atomic_inc(volatile int *p){
    int old;
    __asm__ volatile(
        "lock; xaddl %0, %1"
        : "+r"(old), "+m"(*p)    /* old is read+write, memory operand is read+write */
        : /* no inputs */
        : "cc", "memory"         /* we modified flags and memory */
    );
    return old;
}

Why mistakes matter:- Missing clobbers or incorrect operand ties can let the compiler reuse registers or reorder memory accesses, producing subtle, non-deterministic bugs or undefined behavior.- Mis-specified constraints (e.g., using a register constraint but actually requiring memory) can crash or corrupt data.

Best practices:- Prefer outputs/input operands over raw clobbering registers.- Test on target architectures and enable -O2 to catch scheduling issues.- When in doubt, use "volatile" + "memory" or write a separate function in assembly.

Unlock Full Question Bank

Get access to hundreds of Assembly Language and Code Generation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.