Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
5 changes: 5 additions & 0 deletions packages/bugc/CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -92,6 +92,10 @@ support. Changes to the specification itself are tracked in the root
merged writes repeated it. A marker with no op on its path to carry
it is dropped: debug information does not change the code
([#384]).
- At the JUMPDEST where an inlined function's code starts, the caller's
locals are listed as they are at the call, with the same pointers.
Before, a local with a version the optimizer removed was listed with
no pointer at that one step ([#380]).
- A local defined before a call keeps its pointer after the call.
The dominator tree that local-variable tracking uses left out a
call's edge to its continuation, so every local defined before a call
Expand Down Expand Up @@ -571,6 +575,7 @@ First publication.
[#377]: https://github.com/ethdebug/format/pull/377
[#378]: https://github.com/ethdebug/format/pull/378
[#379]: https://github.com/ethdebug/format/pull/379
[#380]: https://github.com/ethdebug/format/pull/380
[#383]: https://github.com/ethdebug/format/pull/383
[#384]: https://github.com/ethdebug/format/pull/384
[#388]: https://github.com/ethdebug/format/pull/388
Expand Down
240 changes: 240 additions & 0 deletions packages/bugc/src/evmgen/debug/local-variables.soundness.test.ts
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,9 @@ import { Program } from "@ethdebug/format";
import { executeProgram } from "#test/evm/behavioral";
import {
type Level,
type Local,
type LocalsProgram,
type LocalsTrace,
type Shape,
check,
localsOf,
Expand Down Expand Up @@ -57,6 +59,112 @@ code {
r = h;
}`;

/** The same, with the call only on one branch */
const callInBranch = `name CallInBranch;
define {
struct P { a: uint64; b: uint32; };
function f() -> uint256 { return r + 3; };
}
storage { [0] r: uint256; [1] ps: mapping<address, P>; [2] c: uint256; }
create { c = 1; }
code {
let p: P = ps[msg.sender];
p.a = p.a + 5;
if (c == 1) { r = f(); }
p.b = p.b + 1;
ps[msg.sender] = p;
}`;

/** The same, with the call where two branches meet */
const callAfterBranch = `name CallAfterBranch;
define {
struct P { a: uint64; b: uint32; };
function f() -> uint256 { return r + 3; };
}
storage {
[0] r: uint256; [1] ps: mapping<address, P>; [2] c: uint256;
[3] s: uint256;
}
create { c = 1; }
code {
let p: P = ps[msg.sender];
p.a = p.a + 5;
if (c == 1) { s = 1; }
let h = f();
p.b = p.b + 1;
ps[msg.sender] = p;
r = h;
}`;

/** The same, with a constant argument: the callee's first
* instruction folds away once inlined */
const constantArgument = `name ConstantArgument;
define {
struct P { a: uint64; b: uint32; };
function f(a: uint256) -> uint256 { return a + 3; };
}
storage { [0] r: uint256; [1] ps: mapping<address, P>; }
create {}
code {
let p: P = ps[msg.sender];
p.a = p.a + 5;
let h = f(4);
if (h == 0) { return; }
p.b = p.b + 1;
ps[msg.sender] = p;
r = h;
}`;

/** The same, in an inlined function, across a call it inlines */
const nestedCall = `name NestedCall;
define {
struct P { a: uint64; b: uint32; };
function g(q: uint256) -> uint256 { let w = q * 3; return w; };
function f(n: uint256) -> uint256 {
let p: P = ps[msg.sender];
p.a = p.a + 5;
let t = g(n);
p.b = p.b + 1;
ps[msg.sender] = p;
return t;
};
}
storage { [0] r: uint256; [1] ps: mapping<address, P>; }
create { r = 1; }
code { r = f(r); }`;

/** A local given a constant between two calls */
const constantBetweenCalls = `name ConstantBetweenCalls;
define {
function f(a: uint256) -> uint256 { return a + 1; };
function g(b: uint256) -> uint256 { return b * 2; };
}
storage { [0] r: uint256; [1] s: uint256; }
create { s = 3; }
code {
let x = s + 1;
let h = f(x);
x = 7;
let k = g(h);
r = k + x;
}`;

/** The same, with the second call on a branch */
const constantBeforeBranch = `name ConstantBeforeBranch;
define {
function f(a: uint256) -> uint256 { return a + 1; };
function g(b: uint256) -> uint256 { return b * 2; };
}
storage { [0] r: uint256; [1] s: uint256; }
create { s = 3; }
code {
let x = s + 1;
let h = f(x);
x = 7;
if (h > 1) { r = g(h); }
r = r + x;
}`;

describe("which locals are listed", () => {
it("(a) does not list a local before its declaration", async () => {
const source = `name PreDef;
Expand Down Expand Up @@ -271,6 +379,73 @@ code {
];
};

/** The steps just before each invoke of `callee` */
const beforeInvokes = (run: LocalsTrace, callee: string) =>
run.steps.flatMap((step, k) =>
k > 0 &&
activations(run.instructionAt(step)?.context, "invoke").includes(callee)
? [run.steps[k - 1]]
: [],
);

it.each([2, 3] as const)(
"(l) lists the caller's locals located where inlined code starts at O%i",
async (level) => {
// The step before the invoke is the JUMPDEST that starts the
// inlined code. It changes nothing, so `p` is where it was at the
// step before (and holds its value there: see `programs`). At
// O3, block merging can leave no entry between them
const sources = {
// (by the function called)
acrossCall: [acrossCall, "f"],
callInBranch: [callInBranch, "f"],
callAfterBranch: [callAfterBranch, "f"],
constantArgument: [constantArgument, "f"],
nestedCall: [nestedCall, "g"],
};
for (const [name, [source, callee]] of Object.entries(sources)) {
const run = await traceLocals(source, level);
const steps = beforeInvokes(run, callee);
expect(steps.length, name).toBe(1);
for (const step of steps) {
if (step.opcode !== "JUMPDEST" && level === 3) continue;
expect(step.opcode, name).toBe("JUMPDEST");
const p = localsOf(run.instructionAt(step)?.context).find(
(v) => v.identifier === "p",
);
expect(p?.pointer, `${name}, pc ${step.pc}`).toBeDefined();
}
}
},
);

// At O3, `g`'s code follows `f`'s return in one block in
// `constantBetweenCalls`, with no entry between them
it.each([
[2, "constantBetweenCalls", constantBetweenCalls],
[2, "constantBeforeBranch", constantBeforeBranch],
[3, "constantBeforeBranch", constantBeforeBranch],
] as const)(
"(m) lists a local as it is just before an inlined call at O%i (%s)",
async (level, _, source) => {
// `x = 7` comes between the calls: at `g`'s entry, `x` is 7,
// which has no place, so `x` has no pointer (its old place still
// holds 4); `h` is located
const run = await traceLocals(source, level);
const steps = beforeInvokes(run, "g");
expect(steps.length).toBe(1);
for (const step of steps) {
expect(step.opcode).toBe("JUMPDEST");
const pointer = (name: string) =>
localsOf(run.instructionAt(step)?.context).find(
(v) => v.identifier === name,
)?.pointer;
expect(pointer("x"), `x at pc ${step.pc}`).toBeUndefined();
expect(pointer("h"), `h at pc ${step.pc}`).toBeDefined();
}
},
);

it.each([2, 3] as const)(
"(h) lists an inlined function's locals only within its body at O%i",
async (level) => {
Expand Down Expand Up @@ -967,6 +1142,71 @@ code {
h: { values: [3n] },
},
},
...(
[
["on one branch", callInBranch, {}],
["after a branch", callAfterBranch, { h: { values: [3n] } }],
[
"with a constant argument",
constantArgument,
{ h: { values: [7n] }, a: { values: [4n] } },
],
[
"in an inlined function",
nestedCall,
{
n: { values: [1n] },
t: { values: [3n] },
q: { values: [1n] },
w: { values: [3n] },
},
],
] as Array<[string, string, Record<string, Local>]>
).map(
([where, source, others]): LocalsProgram => ({
name: `a struct local across a call ${where}`,
source,
locals: {
p: {
shape: {
kind: "struct",
fields: {
a: { kind: "scalar", size: 8 },
b: { kind: "scalar", size: 4 },
},
},
everyLevel: true,
values: [
{ a: 0n, b: 0n },
{ value: { a: 5n, b: 0n }, after: "p.a = p.a + 5" },
{ value: { a: 5n, b: 1n }, after: "p.b = p.b + 1" },
],
},
...others,
},
}),
),
{
name: "a local given a constant before a call on a branch",
source: constantBeforeBranch,
locals: {
x: { values: [4n, { value: 7n, after: "x = 7" }] },
h: { values: [5n] },
a: { values: [4n] },
b: { values: [5n] },
},
},
{
name: "a local given a constant between two calls",
source: constantBetweenCalls,
locals: {
x: { values: [4n, { value: 7n, after: "x = 7" }] },
h: { values: [5n] },
k: { values: [10n] },
a: { values: [4n] },
b: { values: [5n] },
},
},
{
name: "a void call",
source: `name VoidCall;
Expand Down
14 changes: 13 additions & 1 deletion packages/bugc/src/evmgen/debug/local-variables.ts
Original file line number Diff line number Diff line change
Expand Up @@ -796,8 +796,16 @@ function enrichFunction(
for (const [blockId, block] of func.blocks) {
// The block's entry: just before its first instruction (or its
// terminator), with that instruction's scope and inline site. Just
// before an inlined function's invoke, that is the caller's.
// before an inlined function's invoke, that is the caller's, at
// the call: the instruction's own origin is in the callee, where
// the caller's versions are not placed, so the position is the
// call's before optimization (`callOrigin`). A call is a
// terminator, and its result is defined in its continuation, so
// the call's own position is the caller's state as the call
// begins, as for the call itself; `stamp` shifts the position
// back one, so the origin is given one past it.
const first = block.instructions[0] ?? block.terminator;
const callOrigin = first.operationDebug?.callOrigin;
const result = spilled.get(blockId);
const sites = first.operationDebug?.inlineSites ?? [];
const invokes = Ir.Utils.activationsOf(
Expand All @@ -809,6 +817,10 @@ function enrichFunction(
? {
...first.operationDebug,
inlineSites: sites.slice(0, -Math.min(invokes, sites.length)),
origin: callOrigin && {
...callOrigin,
index: callOrigin.index + 1,
},
}
: first.operationDebug,
blockId,
Expand Down
6 changes: 6 additions & 0 deletions packages/bugc/src/ir/spec/instruction.ts
Original file line number Diff line number Diff line change
Expand Up @@ -63,6 +63,12 @@ export namespace Instruction {
inlineSites?: string[];
/** Where the instruction was before optimization */
origin?: Function.Origin;
/**
* For the op that invokes an inlined function: where the call was
* before optimization. Just before the invoke, the caller's
* variables are as they were there, at the call.
*/
callOrigin?: Function.Origin;
/**
* Listed locals whose value may be on the stack: code generation
* gives each a stack pointer where the stack holds its temp.
Expand Down
Loading
Loading