Stream: git-cranelift

Topic: cranelift / Issue #1102 Allow extending InstBuilder with ...

GitHub (Feb 28 2020 at 23:27):

alexcrichton transferred Issue #1102:

This is a continuation from https://github.com/CraneStation/cranelift/pull/921 which was a WIP showing demo code. It's usually better to discuss scope and advantages in issues, so opening one.

Currently, the best, secure way to create the Cranelift IR is to go through InstBuilder, a trait implemented by several structures. If you've manipulated Cranelift, there are chances you've interacted with it: pos.ins() or pos.replace(inst) returns an InstBuilder.

It is doing the minimal job at the moment: creating the instruction format, filling it with data, putting it into the DFG, and returning the result SSA values.

This issue proposes adding the possibility to extend the InstBuilder with more advanced behaviors.

New opportunities

Constant folding

For instance:

let v1 = pos.ins().iconst(I32, 42);
let v2 = pos.ins().uextend(I64, v1);

currently results in two IR nodes, while it could just be one with pos.ins().iconst(I64, 42). This would mean that the v1 value may be dead after the conversion, in which case DCE could remove it. If an InstBuilder is used after DCE happened, it also means these dead nodes can stay around forever.

(You might interject that Cranelift IR is a low-level compiler and that constant propagation should have been performed by the compiler. In most cases, you'd be right, but translating from an IR to another introduces redundancies / new folding opportunities that the initial IR didn't have. I've certainly observed this when translating from wasm to CLIF IR with cranelift-wasm.)

Pattern-match some sequences of IR nodes into other nodes

Mostly what simple_preopt does, like converting iadd(iconst(C), x) into iadd_imm(x, C), or folding together series of iadd_imm(x, C). At the limit, we could even remove simple-preopt entirely, or move it into the cranelift-preopt crate. Maybe postop could also be integrated as part of these custom methods.

Same caveat about dead nodes.

Fix some incorrect behaviors

Arguably, things like https://github.com/CraneStation/cranelift/issues/815 could be fixed as part of a custom builder method. Would be better to fix it in the plain trait method, though.

Proposed implementation

• See https://github.com/CraneStation/cranelift/pull/921. The idea is: put what's currently in the inst builder methods in inline default_ prefixed trait methods or external functions, have the trait method called the default method. Thus, the user can either just not override the default trait impl, or add custom behavior and use the default method to trigger the default behavior.
• The above implementation does it by default. Another way to do it would be to propose an additional InstBuilder with custom behaviors, so users can opt-in into choosing which InstBuilder they want to use.
• Additionally, the custom InstBuilder would need to track which pipeline stage we're at, since otherwise it could create illegal opcodes in post-legalization phases. (Maybe a good reason to use the TypeState pattern.)

Drawbacks / Caveats

• May result in creation of dead IR nodes, as shown above.
• Could create illegal opcodes in post-legalization phase, see above. This can already happen now, but this would be harder to debug with custom methods.
• Create infinite recursion under InstBuilder. This can't happen right now, but this category of issues sounds simple enough to detect.
• Create infinite loop during legalization. This can already happen, but could be harder to fix too with custom InstBuilders.
• It might slow down construction of the function's IR, because of looking up types / values of previous IR nodes. Not a strong issue if the use of the better InstBuilder is optional.

Benefits

• Fewer IR nodes mean fewer SSA nodes mean better register allocation, less processing time for each optimization pass, less memory used, etc. This would quite big.
• Almost free constant propagation / simple-preopt.
• We could eventually remove simple-preopt / move it entirely to the cranelift-preopt crate. Maybe the postopt phase too.

Curious to hear people's thoughts about this!

Last updated: Nov 22 2024 at 16:03 UTC