branch_backup(bb, /*generalized=*/true) previously overwrote a single
backup_point per header in generalizedLoopBackedgeBackup[bb]. A loop
header reached from three or more backedges silently lost every
snapshot except the most recent, and the load_generalized_backup phi
was always 2-incoming (canonical + last-seen backedge). PR #121
pinned this as a KNOWN-LIMITATION microtest.
This commit widens the machinery end-to-end to 1 canonical + N
backedges.
Storage and state:
- generalizedLoopBackedgeBackup is now DenseMap<BB*,
SmallVector<backup_point, 2>>. branch_backup_impl appends,
deduplicated by sourceBlock (repeat call from the same source
replaces its entry in place).
- GeneralizedLoopControlFieldState.backedgeSource/Control/Buffer
become parallel SmallVectors sized N per header.
Phi construction:
- make_generalized_loop_backup takes ArrayRef<backup_point> sources.
Its mergeValue lambda constructs (1 + N)-incoming phis, one
incoming per distinct backedge sourceBlock, with canonicalSource
first. Sources duplicating canonicalSource are filtered. The N=1
path produces the same 2-incoming phi as before (determinism
gate: 42/42 golden hashes match).
- retrieve_generalized_loop_control_slot_value_impl,
retrieve_generalized_loop_target_slot_value_impl, and
retrieve_generalized_loop_control_field_value_impl each emit
(1 + N)-incoming phis from state.backedgeSources/Controls/Buffers.
- retrieve_generalized_loop_phi_address_value_impl and
retrieve_generalized_loop_local_phi_address_value_impl relax
their 'phi->getNumIncomingValues() != 2' sanity check to accept
any phi with >= 2 incomings, and match each incoming against
canonicalSource or any of state->backedgeSources[i].
load_generalized_backup_impl:
- Collects backedges whose sourceBlock differs from canonical AND
whose controlCursor value differs from canonical; activates state
only if at least one such backedge exists.
- seedInvariantLocalQwords requires the qword to read identically
from canonicalBuffer AND every backedgeBuffer to qualify.
record_generalized_loop_backedge_impl:
- The rolled-control promotion (move current backedge into
canonical, install new source as backedge) is only well-defined
for the 1-backedge case, so it now guards on
backedgeSources.size() == 1 and becomes a no-op for multi-way.
Extending the rolled-control semantics to multi-way loops is
left as follow-up when a real sample exercises it.
Tests (Tester.hpp):
- runGeneralizedLoopThirdBackedgeOverwritesPriorBackedgeSilently
flipped and renamed to runGeneralizedLoopThirdBackedgePreservesAllThreeSnapshots:
asserts three-backedge vector holds one entry per sourceBlock.
- runGeneralizedLoopLoadBackupWithThreeBackedgesProducesTwoWayPhiOnly
flipped and renamed to runGeneralizedLoopLoadBackupWithThreeBackedgesProducesFourWayPhi:
asserts GetMemoryValue(controlSlot) at the header yields a
4-incoming phi carrying canonical + all three backedge control
values.
Docs (docs/LOOP_HANDLING.md):
- Struct and mergeValue snippets updated to N-way shapes.
- branch_backup state-transition row describes append+dedup.
- Multi-way backedge row removed from Known limitations.
Verification:
- python test.py micro: all pass, including the two flipped tests.
- python test.py baseline: all rewrite regression checks passed,
determinism check passed (42 golden files match - 2-way loop
IR shape unchanged).
- Themida reference sample (../testthemida/example2-virt.bin @
0x140001000): 2544 instructions lifted, 0 warnings, 0 errors.
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
resolveTargetedThemidaR9 was added to recover the controlCursor identity
of R9 at three hardcoded Themida instruction addresses where the symbolic
pipeline had lost provenance. PR #112 (generalized-loop control-field /
slot phi infrastructure) since landed retrieve_generalized_loop_control_*
helpers that produce the correct phi shape through the normal
GetMemoryValue path. The R9 override is now dead code: it overwrites a
correct value with another correct value at three sites that the
upstream pipeline already handles.
Empirical bisect on the reference Themida sample
(../testthemida/example2-virt.bin @ 0x140001000) confirmed:
- site 0x140023671 disabled alone: 2544 lifted, 0 warn, 0 err
- site 0x14002368D disabled alone: 2544 lifted, 0 warn, 0 err
- site 0x140023741 disabled alone: 2544 lifted, 0 warn, 0 err
- all three disabled simultaneously: 2544 lifted, 0 warn, 0 err
- baseline (override active): 2544 lifted, 0 warn, 0 err
The MERGEN_DIAG_LIFT_PROGRESS=1 trace at site 0x14002368D shows R9 is
already `add i64 %generalized_phi_load, 10` before the override fires -
the generalized-loop machinery produced the correct phi independently.
Removed:
- resolveTargetedThemidaR9() in lifter/core/LifterClass_Concolic.hpp
- R9 special-case branch + session-scaffolding diag block in
GetRegisterValue_impl (now just `return get_impl(key)`)
- Three microtests in lifter/test/Tester.hpp:
runTargetedThemidaR9OverrideProducesPhi
runTargetedThemidaR9OverrideDoesNotFireAtAdjacentAddress
runTargetedThemidaR9OverrideFallsThroughWithoutLoopState
- Their three runCustom() registrations
- Override row in helper table, hardcoded-address subsection, and
limitations row in docs/LOOP_HANDLING.md
Retained: kThemidaControlCursorSlot, kThemidaLoopCarriedSlot, and
kSupportedGeneralizedControlFieldOffsets - still consumed by the
generalized-loop control-field/slot retrieve_* helpers.
Verified:
- python test.py micro: all instruction microtests passed
- python test.py baseline: all rewrite regression checks passed,
determinism check passed (42 golden files match)
- Themida sample: 2544 instructions lifted, 0 warnings, 0 errors
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
The identifier 'resolveTargetedThemid\u0430R9' (declared in LifterClass_Concolic.hpp)
contained U+0430 (Cyrillic small letter a) instead of U+0061 (Latin a)
between 'Themid' and 'R9'. Every in-tree reference mirrored the
Cyrillic form, but prose mentions and merge titles (e.g. PR #115 title)
used ASCII, so an ASCII grep for 'resolveTargetedThemidaR9' returned
zero hits. This was a silent discoverability hazard for future sessions
and grep-based tooling.
Rename to pure ASCII across the single declaration, the single
caller in getLatestValueForKey, the six test entry points in
lifter/test/Tester.hpp, and the four references in
docs/LOOP_HANDLING.md. No behavior change.
Verified:
- python test.py micro: all instruction microtests passed
(including the three targeted_themida_r9_override_* cases)
- Themida reference sample (../testthemida/example2-virt.bin @
0x140001000): 2544 instructions lifted, 0 warnings, 0 errors
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
Line 28 read 'Temporarily disabled while the team keeps required VMP 3.8.x targets on the safe high-budget path'. That is stale relative to the current code: canGeneralizeStructuredLoopHeader (lifter/core/LifterClass.hpp) gates generalization on path-solve context plus nine operational guards, and the corresponding loop_generalization_* microtests pass on main. Describe the actual gating and point readers at docs/LOOP_HANDLING.md.
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
Captures the three-phase architecture (detect/generalize/consume), the path-solve context gating table, the GeneralizedLoopControlFieldState layout, mergeValue's widenFirstBackedge contract, the full set of retrieve_generalized_loop_* helpers, and the hardcoded reference-sample addresses (kThemidaControlCursorSlot, the three resolveTargetedThemidаR9 instruction addresses with fire-counts on the reference binary).
Documents known limitations at the bottom: REP SCAS, VMP 3.6 INT 2 dispatcher, the reference-sample hardcodes, unrolling/LICM, multi-way backedges.
Flags that SCOPE.md's 'loop-header generalization temporarily disabled' entry appears to be stale: the code gates generalization on path-solve context (ConditionalBranch / DirectJump / resolved IndirectJump) rather than disabling it wholesale. Not changed in this PR; maintainer decision.
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
* docs: sync rewrite workflow guidance
* docs: drop machine-local pointers and fix stale README branch link
* lifter: allow resolved indirect jumps to participate in structured loop generalization
When a register-indirect jmp has already been resolved to a concrete target via solvePath (ConstantInt or solver), it's no longer speculative. If the target also points backward at a visited block, treat it as a loop back-edge for generalization purposes, the same way a direct or conditional jump would be treated.
Introduces currentPathSolveAllowsStructuredLoopGeneralizationForResolvedTarget() alongside the existing narrow predicate. canGeneralizeStructuredLoopHeader gains an opt-in targetResolvedConcretely parameter that routes through the widened check. getLiftedBackedgeBB uses the widened variant so back-edge reuse fires for resolved indirect jumps. resolveTargetBlock passes targetResolvedConcretely=true (its entry condition requires a concrete destination) and extends stackBypassGeneralizedLoopAddresses to include IndirectJump-context inserts.
Ret-path contexts remain excluded. Tests updated: the old runLoopGeneralizationIndirectJumpBlocked splits into runLoopGeneralizationIndirectJumpBlockedWhenUnresolved (unchanged semantics) and runLoopGeneralizationIndirectJumpAllowedWhenResolved (new). runPendingGeneralizedLoopBlockedByContext becomes runPendingGeneralizedLoopByContext with an expectReuse parameter; Ret still expects no reuse, IndirectJump with a resolved target now expects reuse.
---------
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
The windows-latest preinstalled clang-cl (currently 20.1.8 at
`C:\Program Files\LLVM\bin\clang-cl.exe`) produces a lifter binary
that segfaults on calc_fib before emitting any IR, causing the rewrite
gate to fail. Clang 21.1.8 has been verified locally to compile the
lifter into a binary that lifts both calc_fib and calc_sum_array to
their expected constant returns (`ret i64 13` and `ret i64 150`).
Rolling back to clang 18.x is not an option: the runner image's MSVC STL
(14.44+) hard-requires clang 19.0.0 or newer via a static_assert in
yvals_core.h. Clang 21 satisfies that bound and dodges the clang 20.1.8
miscompile.
Upgrading via `choco upgrade llvm --version=21.1.8` keeps the existing
`C:\Program Files\LLVM\bin\clang-cl.exe` path valid, so the rest of
the pipeline (Resolve LLVM_DIR, Resolve clang-cl, Configure, Build) is
unchanged.
## Changes
- `.github/workflows/rewrite-strict-gate.yml`: add an "Upgrade clang-cl
to 21.1.8" step before `Resolve LLVM_DIR` that runs `choco upgrade
llvm` and pins `CMAKE_{C,CXX}_COMPILER` to the upgraded binary.
- `scripts/rewrite/instruction_microtests.json`: drop the `ci_skip`
entries on `calc_fib` and `calc_sum_array`.
- `docs/SCOPE.md`: bump the corpus counts to 33 samples / 177 runtime
semantic cases.
## Follow-up
Investigating the underlying clang 20.1.8 miscompile in the lifter is
still worth doing \u2014 it's almost certainly UB somewhere in the
structured-loop recovery path that clang 21 happens to tolerate. Tracked
separately.
Co-authored-by: NaC-L <nac-l@users.noreply.github.com>
PR #93 un-skipped both samples after a clean local Release build proved
they lift correctly, but the windows-latest CI lane still fails on them
`Lifter failed for calc_fib` (run 24077021868). The HANDOFF note that
windows-latest clang-cl produces a different codegen shape than the
locally pinned clang-cl turned out to be the actual root cause; the
"stale build cache" theory only explained the local symptom.
Restoring the `ci_skip` entries unbreaks the rewrite-strict-gate and
rewrite-quick-gate workflows. Real fix tracked as a follow-up: either
teach the lifter the CI codegen shape, or pin the rewrite CI lane to a
toolchain that matches the local one byte-for-byte.
Also reverts the `docs/SCOPE.md` corpus counts to 31 samples / 175 cases.
Co-authored-by: NaC-L <nac-l@users.noreply.github.com>
Both samples were originally CI-skipped because windows-latest clang-cl
produced loop/array codegen shapes that tripped the lifter on CI even
though local runs passed. Since then the rewrite CI lane has been pinned
to the same LLVM 18.1.8 clang-cl used locally (eb49a35, 949acaa, a28a368)
and several structured loop recovery fixes have landed (2989e5a, 2eaa22e),
so the codegen mismatch that motivated the skips is gone.
Verified locally with a clean Release build (`cmd /c scripts\dev\configure_iced.cmd`
followed by `build_iced.cmd`):
- `calc_fib` lifts to `ret i64 13` and passes its semantic case
- `calc_sum_array` lifts to `ret i64 150` and passes its semantic case
- `python test.py all` is fully green: semantic 33/33 (was 31/31),
baseline, micro --check-flags, full handler suite 115/119, determinism
Drops the two `ci_skip` entries from `instruction_microtests.json` and
updates `docs/SCOPE.md` corpus counts to 33 samples / 177 cases.
Co-authored-by: NaC-L <nac-l@users.noreply.github.com>
- Add lift_punpcklqdq handler in Semantics_Misc.ipp (XMM dest, low-quadword
interleave from dest+src into a 128-bit result; rejects MMX/non-XMM forms
via the standard not_implemented bailout)
- Wire OPCODE(punpcklqdq, PUNPCKLQDQ) in x86_64_opcodes.x and add a missing
trailing newline
- Add manual punpcklqdq case to TestInstructions.cpp (rdrand-style XMM seed)
and matching seeds in build_full_handler_seed.py
- Regenerate oracle_seed_full_handlers{,_enriched}.json, oracle_seed_vectors.json,
and oracle_vectors_full_handlers.json with two punpcklqdq vectors
(basic interleave, low-source-zero edge case)
- Drop ci_skip on calc_cout in instruction_microtests.json now that the STL
PUNPCKLQDQ path lifts cleanly (4/4 semantic cases pass locally)
- Keep calc_fib and calc_sum_array ci_skipped: they still trip a separate
lifter dyn_cast assertion that is not related to PUNPCKLQDQ; tracked as
follow-up
- Update docs/SCOPE.md handler counts (115/119 covered, 4 intentional skips)
and corpus counts (31 active samples / 175 cases)
Co-authored-by: NaC-L <nac-l@users.noreply.github.com>
Two new post-optimization passes that run after the final O2 pipeline:
PrototypeMinimizationPass:
- Removes unused function arguments based on Argument::use_empty()
- Typical reduction: 34 params -> 0-2 (e.g. @main(i64 %RCX) instead of all 16 GPRs + 16 XMMs + 2 ptrs)
- Splices basic blocks into new function, remaps argument uses, erases old function
- Updated check_semantic.py to parse actual IR signatures instead of hardcoded 34-param list
CanonicalNamingPass:
- Strips address-derived suffixes from block/value names for deterministic output
- Blocks: entry, bb1, bb2, ... (sequential)
- Values: semantic prefix preserved, address suffix removed (realadd-5368713230- -> realadd)
- Same input now produces byte-identical IR across rebuilds
Also fixed writeFunctionToFile to use stored module pointer M instead of
fnc->getParent() (dangling after prototype minimization erases the old function).
Review fixes:
- CanonicalNamingPass: use StringMap<unsigned> instead of DenseMap<StringRef> (dangling key)
- PrototypeMinimizationPass: restrict call rewriting to CallInst (not InvokeInst/CallBrInst)
- PrototypeMinimizationPass: guard F->eraseFromParent() with use_empty() check
- check_semantic.py: widen define regex to handle dso_local and other prefixes
All 28 samples pass, 146 semantic cases, 56 golden hashes updated.
* test: add jump table regression suite (5 samples, 39 semantic cases)
Add 5 new jump table test cases covering the major dispatch patterns:
- jumptable_rel32.asm: RIP-relative dword offset table (lea+movsxd+add+jmp)
- jumptable_shifted.asm: base-shifted range check (sub before index)
- jumptable_shared_targets.asm: multiple cases sharing handlers
- jumptable_computation.asm: case bodies with symbolic arithmetic
- calc_jumptable_large.c: 16-case dense C switch compiled at /O2
All 5 pass lifting and semantic validation (39 new cases, 146 total).
Update golden hashes (46 -> 56 files), manifest, and docs.
* fix(ci): exclude C-compiled samples from golden IR hashes
C-compiled samples (calc_*) produce address-dependent IR because the
linker places symbols at different addresses depending on toolchain
version, link order, and build environment. The determinism check
comment (test.py L123-125) already documented this exclusion policy
but the golden hash file included them anyway, causing rewrite-quick-gate
to fail on CI.
Remove all 14 calc_* entries from golden_ir_hashes.json (56 -> 42).
C-compiled sample correctness is still validated by semantic tests.
---------
Co-authored-by: yusufcanislek <yusuf.canislek@meetdandy.com>
naciandyusufcanislek
wcscpy
Chrizz
naci
pseuxide
r3bb1t