Skip to content

Discuss binding immediates to instructions#3

Closed
abrown wants to merge 61 commits intomasterfrom
immediate-predicates
Closed

Discuss binding immediates to instructions#3
abrown wants to merge 61 commits intomasterfrom
immediate-predicates

Conversation

@abrown
Copy link
Owner

@abrown abrown commented Sep 4, 2019

This is a WIP change published as a PR for discussion. The main ideas are:

  • it adds a Bindable trait and associated conversions to unify all of the bind_any, bind_ref, etc. to a single bind (though I have retained a helper bind_vector due to it having a second parameter
  • when a immediate value is passed to bind the EncodingBuilder should add the appropriate predicate to ensure that the encoding is only applied if the immediate value in the code matches the bound immediate value (this is not finished: see notes on code).

.zip(inst.inst.operands_in.iter().filter(|o| o.is_immediate()))
{
let immediate_predicate = InstructionPredicate::new_is_field_equal(
&inst.inst.format, // TODO need a handle to a FormatRegistry here
Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One issue is that in order to use this type of predicate we would need a handle to a FormatRegistry; another issue is that I believe this is_field_equal predicate is actually doing a string comparison, which is a compile-time cost but a cost nonetheless.

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The EncodingBuilder are mostly used in the encodings.rs files, where there are also stores for all the encodings per mode; we could store the FormatRegistry by ref there, and pass it to this function.

is_field_equal ends up generating a predicates::is_equal call which handles any types that implements Eq, so we should be fine for those.

FloatCC(u8),
UInt8(u8),
UInt128(u128),
}
Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If we are fine with doing string comparisons at compile-time, this could be removed and a string could be passed to bind as the immediate value.

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's nice to have more fined types here, because we can probably add more checks on what kinds of immediates fit or not (like forbidding an u128 value when an u8 is expected).

)
fn verify_immediate_binding(&self) -> Result<(), String> {
// TODO
Ok(())
Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not exactly sure how I would need to check this but I believe I need to ensure at the very least that I don't have more immediates to bind than the format specifies (but again I might need a FormatRegistry for that because the Instruction only has a format index).

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good question. It'd be nice to have to rely on order, if the instruction has several immediates, although it's a bonus (for values we don't even do it).

Instead of requiring the FormatRegistry, can you look at the inst.operands_in vector? I wonder if we could then merge this function with the other one checking SSA values, and maybe add extra checks for SSA regarding the expected types... (Please don't take my feature-creeping as a hard blocker for this work)

nbp and others added 3 commits September 5, 2019 14:55
* [codegen] add encodings for iadd carry variants

Add encodings for iadd carry variants (iadd_cout, iadd_cin, iadd_carry)
for x86_32, enabling the legalization for iadd.i64 to work.

* [codegen] remove support for iadd carry variants on riscv

Previously, the carry variants of iadd (iadd_cin, iadd_cout and
iadd_carry) were being legalized for isa/riscv since RISC architectures
lack a flags register.

This forced us to return and accept booleans for these operations, which
proved to be problematic and inconvenient, especially for x86.

This commit removes support for said statements and all dependent
statements for isa/riscv so that we can work on a better legalization
strategy in the future.

* [codegen] change operand type from bool to iflag for iadd carry variants

The type of the carry operands for the carry variants of the iadd
instruction (iadd_cin, iadd_cout, iadd_carry) was bool for compatibility
reasons for isa/riscv. Since support for these instructions on RISC
architectures has been temporarily suspended, we can safely change the
type to iflags.
Copy link

@bnjbvr bnjbvr left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice!


pub fn bind_any(&self) -> BoundInstruction {
bind(self.clone(), None, Vec::new())
impl Bindable for Instruction {
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I just thought of something even simpler: maybe we could just convert Instruction into BoundInstruction with a bind() method, and have all the bind_ methods that are in the trait only on BoundInstruction? (it would even remove the need for the trait)
This might make the encodings very verbose, though... Or make them cute instead: my_inst.bind().any().ty(i32).vec(i32, 4) etc.

Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've been going back and forth about this: does it make sense to have a BoundInstruction that isn't bound? my_inst.bind() is a valid BoundInstruction but it isn't really bound to anything yet. I worried that adding BoundInstruction::new would make people think this was ok but I kept that method private to limit the confusion to only this one file. I would prefer to code this so that Instruction and InstSpec can only become a BoundInstruction when they are truly bound but I could be convinced otherwise.

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You're right it might create some confusion when finishing building encodings in particular; I was trying to avoid the trait altogether, the (meta crate) compile cost that comes with it and the need to have use statements in all the files that use it. The current way looks good, thanks.

bind(self.clone(), None, Vec::new())
impl Bindable for Instruction {
fn bind(&self, parameter: impl Into<InstructionParameter>) -> BoundInstruction {
BoundInstruction::new(self).bind(parameter)
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

(This doesn't check that we're not overbinding the instruction, as is done in verify_polymorphic below)

Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The verification is done in BoundInstruction::bind.

)
fn verify_immediate_binding(&self) -> Result<(), String> {
// TODO
Ok(())
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good question. It'd be nice to have to rely on order, if the instruction has several immediates, although it's a bonus (for values we don't even do it).

Instead of requiring the FormatRegistry, can you look at the inst.operands_in vector? I wonder if we could then merge this function with the other one checking SSA values, and maybe add extra checks for SSA regarding the expected types... (Please don't take my feature-creeping as a hard blocker for this work)

FloatCC(u8),
UInt8(u8),
UInt128(u128),
}
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's nice to have more fined types here, because we can probably add more checks on what kinds of immediates fit or not (like forbidding an u128 value when an u8 is expected).

.zip(inst.inst.operands_in.iter().filter(|o| o.is_immediate()))
{
let immediate_predicate = InstructionPredicate::new_is_field_equal(
&inst.inst.format, // TODO need a handle to a FormatRegistry here
Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The EncodingBuilder are mostly used in the encodings.rs files, where there are also stores for all the encodings per mode; we could store the FormatRegistry by ref there, and pass it to this function.

is_field_equal ends up generating a predicates::is_equal call which handles any types that implements Eq, so we should be fine for those.

bnjbvr and others added 20 commits September 5, 2019 17:55
Add encodings for isub borrow variants (isub_bout, isub_bin,
isub_borrow) for x86_32, enabling the legalization for isub.i64 to work.

Bug: https://bugzilla.mozilla.org/show_bug.cgi?id=1576675
Bug: https://github.com/CraneStation/cranelift/issues/765
Previously, the borrow variants of isub (isub_bin, isub_bout and
isub_borrow) were being legalized for isa/riscv since RISC architectures
lack a flags register.

This forced us to return and accept booleans for these operations, which
proved to be problematic and inconvenient, especially for x86.

This commit removes support for said statements and all dependent
statements for isa/riscv so that we can work on a better legalization
strategy in the future.
…ants

The type of the borrow operands for the borrow variants of the isub
instruction (isub_bin, isub_bout, isub_borrow) was bool for compatibility
reasons for isa/riscv. Since support for these instructions on RISC
architectures has been temporarily suspended, we can safely change the
type to iflags.
this fixes the compile for arm and aarch64

reported via bytecodealliance#977
This removes the explicit dependency on target-lexicon for the embedder,
which can instead use the ISA's name directly. It can simplify
dependency management, in particular avoid the need for synchronizing
the target-lexicon dependencies versions.

It also tweak the error when an ISA isn't built as part of Cranelift to
be a SupportDisabled error; this was dead code before this.
bjorn3 and others added 20 commits September 7, 2019 09:55
This commit adds a hook to the `ModuleEnvironment` trait to learn when a
custom section in a wasm file is read. This hook can in theory be used
to parse and handle custom sections as they appear in the wasm file
without having to re-iterate over the wasm file after cranelift has
already parsed the wasm file.

The `translate_module` function is now less strict in that it doesn't
require sections to be in a particular order, but it's figured that the
wasm file is already validated elsewhere to verify the section order.
Pushing on the `val_stack` vector is CL's biggest source of calls to
malloc/realloc/free, by some margin.  It accounts for about 27.7% of all heap
blocks allocated when compiling wasm_lua_binarytrees.  This change removes
pretty much all dynamic allocation by changing to a SmallVec<[Value; 8]>
instead.  A fixed size of 4 gets all the gains to be had, in testing, so 8
gives some safety margin and is harmless from a stack-use perspective: 8
Values will occupy 32 bytes.

As a bonus, this change also reduces the compiler's dynamic instruction count
by about 0.5%.
Allocations associated with pushes to EbbHeaderBlockData::predecessors account
for 4.9% of all heap allocation (calls) in CL.  This change avoids almost all
of them by changing it to be a SmallVec<[PredBlock; 4]>.  Dynamic instruction
count falls by 0.15%.
…f Vec

This function is responsible for 8.5% of all heap allocation (calls) in CL.
This change avoids almost all of them by using a SmallVec::<[Value; 32]>
instead.  Dynamic instruction count falls by 0.25%.  The fixed size of 32 was
arrived at after profiling with fixed sizes of 1, 2, 4, 8, 16, 32, 64 and 128.
32 is as high as I can push it without the instruction count starting to creep
up again, and gets almost all the block-reduction win of 64 and 128.
@abrown abrown force-pushed the immediate-predicates branch from d5b1032 to 8a66f2e Compare September 9, 2019 21:25
TODO remove the helper functions still retained (e.g. bind_any, bind_ref, etc.)
The vector usages are left with a helper method, Bindable::bind_vector(), because a second parameter is passed (i.e. bector bit width)
@abrown abrown force-pushed the immediate-predicates branch from 8a66f2e to b78cdd4 Compare September 9, 2019 21:37
@abrown
Copy link
Owner Author

abrown commented Sep 9, 2019

Closed in favor of bytecodealliance#1012

@abrown abrown closed this Sep 9, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

10 participants