Implement Function Inline Expansion

Topic Overview

Inlining Removes Call Overhead

Function inlining replaces a call site with the callee's body, enabling further optimization across the old boundary. LLVM's inliner uses cost heuristics; C++ inline and LTO push this aggressively. Too much inlining blows code size.

When to Inline

Small callees, hot call sites, and functions marked always_inline are candidates. Copy parameters to locals, rename to avoid clashes, insert return handling at the call site.

cCopy
Loading…

• Size budget prevents code bloat
• Recursive inlining needs depth limits
• Tail calls may not need full frame setup
• Inlining exposes constants to inter-procedural opts

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement function inline expansion on your IR. This exercise requires copying a callee's instructions to the call site, mapping arguments to parameters, and splicing the result back into the caller.

Your Task

Implement inline expansion: replace a call with a renamed copy of the callee's body when the callee is small enough, and explain the decision for every call site.

Input

cCopy
Loading…

Function bodies and main contain x = a, x = a OP b, print a, and calls x = call F(a1, a2, ...) (arguments are names or literals). Each function ends with exactly one return a. Indentation is ignored.

Decisions (for each call in main, top to bottom)

1. Unknown function → not inlined (unknown function)
2. The callee contains a call to itself → not inlined (recursive)
3. The callee's size: body instructions excluding the return: is greater than B → not inlined (size S > budget B)
4. Otherwise → inlined (size S)

Only calls in main are candidates; calls inside an inlined body are copied as they are.

Inlining the k-th inlined call x = call F(args)

• Every variable of F (parameters and locals) named v becomes v_k, where k counts inlined sites from 1.
• First copy each argument into its renamed parameter: p_k = arg, in parameter order.
• Then the body with renamed variables (literals unchanged; callee names in inner calls unchanged).
• Finally x = r_k for return r (or x = N for return N).

Output

The rewritten main body, one instruction per line, then one line per call site:

cCopy
Loading…

and finally inlined=I kept=K.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Parse functions into a table (name, parameters, body instructions); keep the call's original text for sites that are not inlined.
2. A renaming helper that suffixes variable operands and leaves literals alone.

Hidden tests cover recursion, an unknown function, literal returns, a budget of 0, and callees that themselves call other functions.