Stream: cranelift

Topic: Non-associative or operation

Chase Wilson (Mar 02 2023 at 16:57):

I know it's a bit strange but I need a non-associative (boolean) or operator, the basic situation I've got set up is this:

• There's two variables, x and x_is_uninit
• x is some arbitrary boolean that is uninitialized iff x_is_uninitis true
• I want to or these two values together, x_is_uninit | x
• However, since x can be uninitialized it would be very bad if the order of operations were swapped

Again, I know it's mildly ill-advised but I'm just not sure how to approach this well

Jamey Sharp (Mar 02 2023 at 18:04):

I'm a little confused by the question. In what sense is x uninitialized, and what would be bad about using the uninitialized value this way? Cranelift doesn't have undefined behavior, so it'll happily compile a bitwise 'or' where the operands are any SSA value, even from a load from memory that you haven't previously stored anything to. And to the extent that we still have booleans at all, they're in the definition of instructions like brif, which treats anything non-zero as "true". So if x_is_uninit is non-zero, no matter what the value of x is, combining them with bor will also be non-zero. And if x_is_uninit is zero, then the result will equal x, but in that case it was initialized. So that is the result you wanted, I think?

Chase Wilson (Mar 02 2023 at 18:19):

Like I said, I'm mainly concerned by the associativity of or, if x_is_uninit | x was folded into x | x_is_uninit then that would cause undefined/incorrect/unwanted behavior

Jamey Sharp (Mar 02 2023 at 18:26):

I gather you mean commutativity rather than associativity, right? But Cranelift's bor instruction really does produce identical results regardless of which order its operands are in, no matter where those operands came from. I still don't know what you mean by "uninitialized" in this context, since Cranelift's instruction semantics don't include any undefined behavior.

Chase Wilson (Mar 02 2023 at 18:44):

Yes my bad, I meant commutativity. I guess you're right though, I need a short-circuiting or operator in order to do this correctly

Jamey Sharp (Mar 02 2023 at 19:00):

You certainly can use branches to implement short-circuiting boolean-or, and Cranelift won't re-order those. But I still would love to understand what correctness criteria you're using, because from Cranelift's perspective I don't see any way to get an "incorrect" result in the situation you've described.

Last updated: Oct 23 2024 at 20:03 UTC