Empty instruction, or other way to improve code rewrites

[yrashk]

I admit this may be (a bit) controversial, but here's a problem I am working on. I am using CodeAssembler (in my case, using the Rust version of the library) to generate code. Then I take another optimization pass over it to detect known redundancies and other optimizations to make generated code more efficient.

The problem, however, comes with relative addressing and labels. If I remove some instructions, eventually, my code would stop working as labels are pointing to an instruction index, and this changes the number of instructions. If I nop the optimized-away instructions instead of removing, everything still works fine, but the final code gets polluted with NOPs, which is not ideal.

So I was thinking, how can this be addressed. So far, I have some ideas, and I am not sure if any of them are good yet, but I wanted to entertain this problem with you guys.

1. Make a special case Instruction that denotes an "empty" or "void" instruction so that it encodes to nothing during assembly time. This would work for most of the cases where I am reducing the size of the code. But it'll break if my optimization will actually add more instructions (not that I have any optimizations like this at the moment)
2. Find a way to make label -> index binding lazily. This might be non-trivial or even impossible, given the current design. However, an approximation to this method (deferring calling set_label until after optimizations) is the approach I am exploring right now (and will perhaps continue down that road if my use case is a non-goal for you guys).

Any thoughts?

[wtfsck]

Adding a new 'empty' instruction (one new Code variant) would probably be the easiest solution. Seems like the current code would have no problem with this, just one debug-assert that can be removed that checks that the size != 0.

[yrashk]

For reference, I ended up going through with late label binding, and here is what I've got

https://github.com/paraexec/ParaOS/blob/master/parawasm/src/x86_64/mod.rs#L365-L379
https://github.com/paraexec/ParaOS/blob/master/parawasm/src/x86_64/optimizer.rs#L97-L103

Seems to have worked well enough so far.

I suspect some of the mechanics of this can be extracted for re-usability and contributed to iced. Happy to help where I can. Is this of any interest?

[wtfsck]

I suspect some of the mechanics of this can be extracted for re-usability and contributed to iced. Happy to help where I can. Is this of any interest?

What API do you propose should be added? Some method that initializes labels after all instructions have been added? I.e., no calls to set_label() while adding instructions, and once all instructions have been added, some method gets called that does something similar to what set_label() does?

[yrashk]

Great question. While the explicit late binding is what I've done (and it seems to work), I don't think it is very intuitive.

What if we developed an instruction insertion/removal API and allowed set_label to be done eagerly and then upon insertion/removal we can update all CodeLabels with proper instruction index, or we can find a better way to indicate a location of a label other than instruction's index.

On the latter note, how [un]reasonable is it to apply the Empty instruction method we discussed above to labels? (Besides it being a breaking change unless a new type of label is introduced). Say, if we can actually insert an instruction that represents a label. This way, we don't need to track its positional index.

[wtfsck]

Seems like adding a new zero-byte instruction would be the easiest solution. Then just use it as a label and I think your code will work too.

If so, I can add one later this week.

[yrashk]

I agree this is the easiest. Maybe down the road I'll be able to help with more sophisticated labels? The beauty of using CodeLabel right now is that they can be used in operands before I bind them.

[wtfsck]

I've added a zero_bytes() method you can call to create this new empty instruction.

I've also added assemble_options() which returns the same thing as BlockEncoder. You can use it to get the address of a label (call result.label_ip(&label)). That should hopefully eliminate your extra assembler.assemble(0)?.len() calls from your first link.

[yrashk]

Thank you for the idea. It seems like I am still missing something, as changing to this:

--- a/parawasm/src/x86_64/mod.rs
+++ b/parawasm/src/x86_64/mod.rs
@@ -371,6 +371,8 @@ impl Compiler for X86_64Compiler {
         for instruction in optimizer::optimize(assembler.take_instructions(), &mut label_indices)? {
             assembler.add_instruction(instruction)?;
         }
+        let code_assembler_result =
+            assembler.assemble_options(0, BlockEncoderOptions::RETURN_NEW_INSTRUCTION_OFFSETS)?;
         // Bind labels
         for (idx, instruction) in assembler.take_instructions().into_iter().enumerate() {
             if let Some((_, label)) = label_indices.iter_mut().find(|(i, _)| *i == idx) {
@@ -380,15 +382,9 @@ impl Compiler for X86_64Compiler {
                 if let Some((_label, index)) =
                     function_bodies.iter().find(|(label_, _)| label_ == label)
                 {
-                    module.function_bodies.insert(
-                        *index,
-                        assembler
-                            .assemble_options(
-                                0,
-                                BlockEncoderOptions::RETURN_NEW_INSTRUCTION_OFFSETS,
-                            )?
-                            .label_ip(label)? as usize,
-                    );
+                    module
+                        .function_bodies
+                        .insert(*index, code_assembler_result.label_ip(label)? as usize);
                 }
             }
             assembler.add_instruction(instruction)?;

breaks the tests fail and in some cases, I get the Invalid label instruction index or BlockEncoderOptions::RETURN_NEW_INSTRUCTION_OFFSETSoption was not enabled when callingassemble_options()` error even though the option is enabled.

I'll try to figure out what's going on.

[wtfsck]

Did you initialize the labels before calling assemble_options()? Are you using the correct labels that were used when calling assemble_options()? If you're using labels created after assemble_options() you'll probably get an error.

[yrashk]

Labels are created before assemble_options() but set_label is called after (because I am binding them with post-processed code as they come). Perhaps that's the reason for the failure?

[wtfsck]

Yes, they must be initialized (call set_label()) before assembling the instructions.

Is it possible to move assemble_options() after the loop instead of before the loop? (assuming you initialize the labels in the loop like in paraexec/ParaOS@ed343c2 )

[yrashk]

I guess it would be possible to move it after the loop but then I'd need to iterate over labels again to get their offsets in another loop, and at that point, will the gains of initializing asssemble_options once be significant enough? I'd need to test it on a much larger scale to see any big difference. Will see.