morluto/rea

Fork 0

mirror of https://github.com/morluto/rea.git synced 2026-11-05 06:45:22 +00:00

[PR #2870] perf(ghidra): resolve Swift select provenance once per function #5455

New issue

Open

opened 2026-10-31 01:06:46 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-31 01:06:46 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/2870
Author: @thefolahan
Created: 10/13/2026
Status: 🔄 Open

Base: main ← Head: perf/swift-select-provenance

📝 Commits (10+)

f4cf8d7 perf(ghidra): resolve Swift select provenance once per function
c719c1a fix(ghidra): charge provenance flow edges before allocating
58583ba fix(ghidra): count provenance edges without collecting them
e725d11 fix(ghidra): poll cancellation in select provenance passes
da3e303 fix(ghidra): bound Swift select provenance storage
dbb85c1 fix(ghidra): bound provenance by distinct registers and poll cancellation
c79b58d test(ghidra): retain Swift select fixture control flow
7f8093a Merge commit '2895a18ca9' into codex/ci-review-pr2870-20261014
2497d3e merge: refresh main to resolve CI baseline failures
f2a4589 fix(ghidra): preserve select queries and poll predecessor conversion

📊 Changes

3 files changed (+283 additions, -66 deletions)

View changed files

📝 bridge/ghidra/ReaGhidraBridge.java (+243 -66)
📝 scripts/verify-real-ghidra-swift.mjs (+3 -0)
📝 tests/conformance/swift/string-literals.swift (+37 -0)

📄 Description

Summary

Follows up #2049 and resolves the open P1 review thread there (discussion_r4258738827). The Swift String literal decoder now answers "was this register produced by a conditional select?" from one forward analysis per function, instead of walking every predecessor path again at each use site. On a function that reuses one literal pair at many call sites, decoding goes from quadratic to linear time, with identical output.

Problem and expected behavior

selectedValue ran a fresh backward search through the function body for each register of each candidate pair, and the cache was keyed by site, so no search was reused. Every search also allocated its own unbounded visited set before the record budget could stop decoding. One literal defined near the entry and passed at N later call sites therefore cost N full walks of the body.

Measured with Ghidra 12.1.4 headless on Apple silicon, calling swiftStringLiterals on a synthetic AArch64 function that loads one small literal into x19/x20 and passes it at every call site (mov x0, x19; mov x1, x20; bl consume):

Call sites	Before	After	Output
3,000	27.2 s	0.36 s	identical, 3,000 literals, no omissions
6,000	110.6 s	0.64 s	identical, 6,000 literals, no omissions

Doubling the sites quadrupled the old time, as expected for quadratic cost. The new time grows linearly.

Change and scope

swiftSelectProvenance computes, once per decode run and only when the first candidate pair needs it, which base registers may hold a conditional select on entry to each instruction of the body:

An instruction with an internal constant CBRANCH (how Ghidra lifts csel) marks every register it defines.
A single COPY or INT_ZEXT from a register carries the source's state to its destination.
Any other definition clears the register.
States merge by union over the same predecessors relation as before, iterated to the least fixed point with a worklist.

This is the same reachability question the backward search asked, so a site's answer is unchanged. The one intended difference: predecessors are now limited to instructions inside the function body. The old walk could follow getFallFrom into a neighbouring function.

Budget: the analysis pre-counts instructions, flow edges, and distinct base registers. An overflow-safe estimate reserves graph/map storage and worst-case dense BitSet backing arrays before graph allocation. If that reservation does not fit, decoding takes the existing structured capacity-omission path and stops. The per-site cache and its takeState charge are removed.

selectedValue(Function, Instruction, Register) remains a single-site query over the shared analysis for #2828's producer regressions. Dossier decoding continues to compute and reuse one function-wide analysis. The single-site helper propagates cancellation and fails explicitly on capacity exhaustion instead of answering false. Predecessor-array conversion now checks cancellation per edge, as the reference scan and worklist already do.

Contract and boundary impact

Semantic owner and earliest changed stage: Ghidra bridge (ReaGhidraBridge.java), Swift literal decoding only.
CLI and MCP/tool-catalog contract: unchanged. Same fields, same values, same omission shape.
Provider, bridge, target-format, or platform compatibility: Ghidra only, AArch64 Swift programs only, as before.

Verification

Current verification at f2a458920:

All bridge/ghidra/*.java sources compile against installed Ghidra 12.1.4 jars with JDK 21.
npm run verify:ghidra:swift passes through the real installed Ghidra provider and MCP workflow, including the selected-loop/join/ordinary-overwrite fixtures. This is static analysis; fixture target code is not executed.
A temporary real-Ghidra producer probe using #2828's source-owned AArch64 assembly fixture passes for ordinary copied values, direct selects, copied selects, and cancellation through the restored selectedValue helper. Running that same probe against original head 7f8093a69 reproduces the missing-helper failure (NoSuchMethodException). This focused probe does not claim that #2828's entire harness or explicit-budget overlay was integrated or run.
npm run check:ci passes, including typecheck, lint, formatting, metadata, unused-code/duplication checks and architecture guards.
The focused product-catalog, artifact-comparison, and managed CIL decoding checks pass: 3 files, 94 tests. These cover the previously failing catalog/README consistency assertion and the files reported by CI lint.
git diff --check passes.
Current main was merged at 2497d3ea3, bringing in the existing fixes for the old lint and Turkish README link failures. New GitHub CI is pending after publication.

The timing table above is the original contributor's measurement; this maintenance pass did not rerun the performance benchmark or measure token usage, CPU time, or peak process-family memory. No new performance improvement is claimed for the compatibility/cancellation corrections.

Not covered: x86_64 (the decoder is AArch64-only), Hopper, IDA, or Windows Ghidra. No new capability or target-execution authority is introduced.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/morluto/rea/pull/2870 **Author:** [@thefolahan](https://github.com/thefolahan) **Created:** 10/13/2026 **Status:** 🔄 Open **Base:** `main` ← **Head:** `perf/swift-select-provenance` --- ### 📝 Commits (10+) - [`f4cf8d7`](https://github.com/morluto/rea/commit/f4cf8d7f18d535a7f4f668d8bc15dfa54a2a9b49) perf(ghidra): resolve Swift select provenance once per function - [`c719c1a`](https://github.com/morluto/rea/commit/c719c1a8e2c5debd7356e42ded6aaf9982d79c43) fix(ghidra): charge provenance flow edges before allocating - [`58583ba`](https://github.com/morluto/rea/commit/58583ba1dc79f98dd196786f65dc9ed8a5329c04) fix(ghidra): count provenance edges without collecting them - [`e725d11`](https://github.com/morluto/rea/commit/e725d11e50aab3899639e688c6cbb52ebdab910a) fix(ghidra): poll cancellation in select provenance passes - [`da3e303`](https://github.com/morluto/rea/commit/da3e303dde995f666d2fd8be29e94155f699de38) fix(ghidra): bound Swift select provenance storage - [`dbb85c1`](https://github.com/morluto/rea/commit/dbb85c1d647f76bbcbb73ccb030ce9181dc3fe5c) fix(ghidra): bound provenance by distinct registers and poll cancellation - [`c79b58d`](https://github.com/morluto/rea/commit/c79b58d130efa81c187753ef14752f63c60fd7f3) test(ghidra): retain Swift select fixture control flow - [`7f8093a`](https://github.com/morluto/rea/commit/7f8093a69ae7aa8296d5d120c88a9e7984bda928) Merge commit '2895a18ca92f415ae62f87167ba9c7a672e3b7dc' into codex/ci-review-pr2870-20261014 - [`2497d3e`](https://github.com/morluto/rea/commit/2497d3ea3e236d00fd5c7aaa5ed37a071be9ecc7) merge: refresh main to resolve CI baseline failures - [`f2a4589`](https://github.com/morluto/rea/commit/f2a458920df94fc6bab262c5394f0cd74f11572e) fix(ghidra): preserve select queries and poll predecessor conversion ### 📊 Changes **3 files changed** (+283 additions, -66 deletions) <details> <summary>View changed files</summary> 📝 `bridge/ghidra/ReaGhidraBridge.java` (+243 -66) 📝 `scripts/verify-real-ghidra-swift.mjs` (+3 -0) 📝 `tests/conformance/swift/string-literals.swift` (+37 -0) </details> ### 📄 Description ## Summary Follows up #2049 and resolves the open P1 review thread there ([discussion_r4258738827](https://github.com/morluto/rea/pull/2049#discussion_r4258738827)). The Swift String literal decoder now answers "was this register produced by a conditional select?" from one forward analysis per function, instead of walking every predecessor path again at each use site. On a function that reuses one literal pair at many call sites, decoding goes from quadratic to linear time, with identical output. ## Problem and expected behavior `selectedValue` ran a fresh backward search through the function body for each register of each candidate pair, and the cache was keyed by site, so no search was reused. Every search also allocated its own unbounded visited set before the record budget could stop decoding. One literal defined near the entry and passed at N later call sites therefore cost N full walks of the body. Measured with Ghidra 12.1.4 headless on Apple silicon, calling `swiftStringLiterals` on a synthetic AArch64 function that loads one small literal into x19/x20 and passes it at every call site (`mov x0, x19; mov x1, x20; bl consume`): | Call sites | Before | After | Output | | ---: | ---: | ---: | --- | | 3,000 | 27.2 s | 0.36 s | identical, 3,000 literals, no omissions | | 6,000 | 110.6 s | 0.64 s | identical, 6,000 literals, no omissions | Doubling the sites quadrupled the old time, as expected for quadratic cost. The new time grows linearly. ## Change and scope `swiftSelectProvenance` computes, once per decode run and only when the first candidate pair needs it, which base registers may hold a conditional select on entry to each instruction of the body: * An instruction with an internal constant `CBRANCH` (how Ghidra lifts `csel`) marks every register it defines. * A single `COPY` or `INT_ZEXT` from a register carries the source's state to its destination. * Any other definition clears the register. * States merge by union over the same `predecessors` relation as before, iterated to the least fixed point with a worklist. This is the same reachability question the backward search asked, so a site's answer is unchanged. The one intended difference: predecessors are now limited to instructions inside the function body. The old walk could follow `getFallFrom` into a neighbouring function. Budget: the analysis pre-counts instructions, flow edges, and distinct base registers. An overflow-safe estimate reserves graph/map storage and worst-case dense BitSet backing arrays before graph allocation. If that reservation does not fit, decoding takes the existing structured capacity-omission path and stops. The per-site cache and its `takeState` charge are removed. `selectedValue(Function, Instruction, Register)` remains a single-site query over the shared analysis for #2828's producer regressions. Dossier decoding continues to compute and reuse one function-wide analysis. The single-site helper propagates cancellation and fails explicitly on capacity exhaustion instead of answering false. Predecessor-array conversion now checks cancellation per edge, as the reference scan and worklist already do. ## Contract and boundary impact - Semantic owner and earliest changed stage: Ghidra bridge (`ReaGhidraBridge.java`), Swift literal decoding only. - CLI and MCP/tool-catalog contract: unchanged. Same fields, same values, same omission shape. - Provider, bridge, target-format, or platform compatibility: Ghidra only, AArch64 Swift programs only, as before. ## Verification Current verification at `f2a458920`: - All `bridge/ghidra/*.java` sources compile against installed Ghidra 12.1.4 jars with JDK 21. - `npm run verify:ghidra:swift` passes through the real installed Ghidra provider and MCP workflow, including the selected-loop/join/ordinary-overwrite fixtures. This is static analysis; fixture target code is not executed. - A temporary real-Ghidra producer probe using #2828's source-owned AArch64 assembly fixture passes for ordinary copied values, direct selects, copied selects, and cancellation through the restored `selectedValue` helper. Running that same probe against original head `7f8093a69` reproduces the missing-helper failure (`NoSuchMethodException`). This focused probe does not claim that #2828's entire harness or explicit-budget overlay was integrated or run. - `npm run check:ci` passes, including typecheck, lint, formatting, metadata, unused-code/duplication checks and architecture guards. - The focused product-catalog, artifact-comparison, and managed CIL decoding checks pass: 3 files, 94 tests. These cover the previously failing catalog/README consistency assertion and the files reported by CI lint. - `git diff --check` passes. - Current main was merged at `2497d3ea3`, bringing in the existing fixes for the old lint and Turkish README link failures. New GitHub CI is pending after publication. The timing table above is the original contributor's measurement; this maintenance pass did not rerun the performance benchmark or measure token usage, CPU time, or peak process-family memory. No new performance improvement is claimed for the compatibility/cancellation corrections. Not covered: x86_64 (the decoder is AArch64-only), Hopper, IDA, or Windows Ghidra. No new capability or target-execution authority is introduced. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi added the

pull-request

label

2026-10-31 01:06:46 +00:00

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#5455

No description provided.

Rows
Columns