WebAssembly / WebAssembly/binaryen
Unroll constant-sized loops
Nobody has claimed this yet.
- Dominant language
- WebAssembly
- Stars
- 8.6k
- Forks
- 885
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 69
Description
Sometimes it could greatly improve code size. Let's look at real world example from KhronosGroup's project (AssemblyScript):
for (let bits: u32 = 0; bits < 4; bits++) {
const a = (bits & 1) ? 0x1FF : 0;
const b = (bits & 2) ? 0x116 : 0;
for (let trit: u32 = 0; trit < 3; trit++) {
const i = (trit << 2) | bits;
const u = (a & 0x80) | (((trit * 93 + b) ^ a) >> 2);
store<u8>(i, u, 0x40);
}
}
this nested loops could be completely unrolled with partially evaluation to:
// bits = 0
store<u8>(0, 0, 0x40);
store<u8>(4, 23, 0x40);
store<u8>(8, 46, 0x40);
// bits = 1
store<u8>(1, 255, 0x40);
store<u8>(5, 232, 0x40);
store<u8>(9, 209, 0x40);
// bits = 2
store<u8>(2, 69, 0x40);
store<u8>(6, 82, 0x40);
store<u8>(10, 107, 0x40);
// bits = 3
store<u8>(3, 186, 0x40);
store<u8>(7, 163, 0x40);
store<u8>(11, 139, 0x40);
next step it could sort stores/loads in order by access and merge as:
store<u32>(0, (186 << 24) | (69 << 16) | (255 << 8) | (0 << 0), 0x40);
store<u32>(4, (163 << 24) | (82 << 16) | (232 << 8) | (23 << 0), 0x40);
store<u32>(8, (139 << 24) | (107 << 16) | (209 << 8) | (46 << 0), 0x40);
finally after constant folding:
store<u32>(0x40, 0xba45ff00);
store<u32>(0x44, 0xa352e817);
store<u32>(0x48, 0x8b6bd12e);
before 116 bytes
after: 35 bytes
of course it's not always may lead to size improvements. So perhaps need some cost prediction function before try to apply this unrolling. WDYT?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
The issue names no files, tests, or entry points. Start by locating Binaryen's loop optimization and constant-folding passes, then determine how a cost model could govern unrolling and memory-store merging; done means a tested implementation that improves eligible constant-sized loops without regressing code size.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- wasm
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100