Stream: t-compiler/wg-mir-opt

Topic: `x & false == false`


oli (Jul 13 2020 at 10:48, on Zulip):

oooh I have one for you

oli (Jul 13 2020 at 10:48, on Zulip):

https://github.com/rust-lang/rust/issues/72751

oli (Jul 13 2020 at 10:48, on Zulip):

This one is great

oli (Jul 13 2020 at 10:49, on Zulip):

x & false is guaranteed false but const prop can't figure that out

oli (Jul 13 2020 at 10:50, on Zulip):

If you look at https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1ef992fe05b4e49b40ff5f63acc796d5, and click (MIR in the menu in the top left corner), you can see that there's a BitAnd operation that doesn't actually make sense

oli (Jul 13 2020 at 10:51, on Zulip):

you can basically follow the instructions in https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/multiple.20return.20terminators/near/203699347

oli (Jul 13 2020 at 10:51, on Zulip):

to get started

oli (Jul 13 2020 at 10:51, on Zulip):

but you won't create your own new optimization, you'll work on src/librustc_mir/transform/const_prop.rs

oli (Jul 13 2020 at 10:56, on Zulip):

basically you have to change https://github.com/rust-lang/rust/blob/9d09331e00b02f81c714b0c41ce3a38380dd36a2/src/librustc_mir/transform/const_prop.rs#L534 into a match and add arms for BitAnd and BitOr

oli (Jul 13 2020 at 10:57, on Zulip):

if the type of the values being operated on is bool, then the idea is to read the left and right side of the operators, but read them fallibly. We're fine with one value not existing in case the other has a short circuiting value

oli (Jul 13 2020 at 10:59, on Zulip):

though, now that I'm looking at this, I think you need to work at https://github.com/rust-lang/rust/blob/9d09331e00b02f81c714b0c41ce3a38380dd36a2/src/librustc_mir/transform/const_prop.rs#L613 instead of inside the function being called from there

Xavier Denis (Jul 13 2020 at 11:03, on Zulip):

Cool :) I’ve got my rustc working already so I’ll take a look this afternoon

Xavier Denis (Jul 13 2020 at 17:47, on Zulip):

ok I think I understand how all these functions fit together to decide prop

Xavier Denis (Jul 13 2020 at 17:47, on Zulip):

I'll add support for && and || and push a PR this evening

Xavier Denis (Jul 13 2020 at 17:50, on Zulip):

how do I add a new testcase?

Xavier Denis (Jul 13 2020 at 17:51, on Zulip):

nvm i think i found it in the book

Wesley Wiser (Jul 13 2020 at 17:52, on Zulip):

You can take a look at some of the existing tests (for example src/test/mir-opt/const_prop/aggregate.rs). The main thing to notice is the // EMIT_MIR rustc.main.ConstProp.diff directive.

Wesley Wiser (Jul 13 2020 at 17:53, on Zulip):

After you add your new test file, you can run ./x.py test --stage 1 -i --bless src/test/mir-opt to have it generate the diff file for you

Xavier Denis (Jul 13 2020 at 17:56, on Zulip):

just did that :)

Xavier Denis (Jul 13 2020 at 18:15, on Zulip):

:'( built the compiler without trace! and debug!

Xavier Denis (Jul 13 2020 at 19:15, on Zulip):

hmm, it seems like this specific optimization is just an instance of a more general pattern where constant prop doesn't work if only one arg is defined

Xavier Denis (Jul 13 2020 at 19:15, on Zulip):

for example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=618c614caefa638e6b5782e519b07e03

Xavier Denis (Jul 13 2020 at 19:16, on Zulip):

we should expect a + 0 == a

Xavier Denis (Jul 13 2020 at 19:16, on Zulip):

at the very least for all builtin types, no?

Xavier Denis (Jul 13 2020 at 19:17, on Zulip):

it's all because check_binary_op which is meant to verify if there are overflows expects both args to be defined and if not will abort the constant propagation for that BinaryOp

Xavier Denis (Jul 13 2020 at 19:18, on Zulip):

it needs both args in order to call overflowing_binary_op.

PS: I'm logging my work here hopefully it doesn't bother anyone :) let me know otherwise

Wesley Wiser (Jul 13 2020 at 19:18, on Zulip):

Yes, you're correct.

Wesley Wiser (Jul 13 2020 at 19:19, on Zulip):

IMO this feels a bit more like a "peephole optimization" to me than something that has to go in const_prop

Xavier Denis (Jul 13 2020 at 19:19, on Zulip):

yea honestly that's the feeling im getting

Wesley Wiser (Jul 13 2020 at 19:20, on Zulip):

I feel like we have an existing pass for that kind of thing

Wesley Wiser (Jul 13 2020 at 19:20, on Zulip):

One sec

Wesley Wiser (Jul 13 2020 at 19:20, on Zulip):

Yeah https://github.com/rust-lang/rust/blob/master/src/librustc_mir/transform/instcombine.rs

Xavier Denis (Jul 13 2020 at 19:20, on Zulip):

instcombine?

Xavier Denis (Jul 13 2020 at 19:20, on Zulip):

yea

Wesley Wiser (Jul 13 2020 at 19:22, on Zulip):

Given that you don't need any interpreter state to recognize the a + 0 == a case (or any of the other binary operators) that pass seems like a better fit for this to me

Xavier Denis (Jul 13 2020 at 19:22, on Zulip):

yea, is it run for several iterations?

Wesley Wiser (Jul 13 2020 at 19:22, on Zulip):

Not currently it looks like

Xavier Denis (Jul 13 2020 at 19:22, on Zulip):

these kind of identity opts can ripple through

Wesley Wiser (Jul 13 2020 at 19:23, on Zulip):

If it doesn't hurt our perf benchmarks, I don't think there would be any objection to making it do so

Wesley Wiser (Jul 13 2020 at 19:24, on Zulip):

Alternatively, we might 80% of the cases just by running it twice during the optimization pipeline.

Wesley Wiser (Jul 13 2020 at 19:24, on Zulip):

I don't have an issue running it to a fixed point though.

Xavier Denis (Jul 13 2020 at 19:25, on Zulip):

I think a constant number of iterations probs is good enough

Xavier Denis (Jul 13 2020 at 19:25, on Zulip):

or bounded fixpoint

Xavier Denis (Jul 13 2020 at 19:25, on Zulip):

I'll start by implementing the opt :)

Wesley Wiser (Jul 13 2020 at 19:25, on Zulip):

Yeah, I'd start with that

Wesley Wiser (Jul 13 2020 at 19:25, on Zulip):

I don't think running it multiple times will be very beneficial currently

Xavier Denis (Jul 13 2020 at 19:26, on Zulip):

it's trivial to write examples that defeat a single pass but uncertain how common they are in practice

Xavier Denis (Jul 13 2020 at 19:27, on Zulip):

ie: y & (x & false)

Xavier Denis (Jul 13 2020 at 19:31, on Zulip):

Wesley Wiser said:

Given that you don't need any interpreter state to recognize the a + 0 == a case (or any of the other binary operators) that pass seems like a better fit for this to me

I do though, since I need to evaluate the places? unless I misunderstood you

Wesley Wiser (Jul 13 2020 at 19:31, on Zulip):

I'd say go a head and include some examples of that kind of expression in the MIR tests you add. When we make InstrCombine iterate, we should see those expressions get optimized.

Wesley Wiser (Jul 13 2020 at 19:33, on Zulip):

Xavier Denis said:

Wesley Wiser said:

Given that you don't need any interpreter state to recognize the a + 0 == a case (or any of the other binary operators) that pass seems like a better fit for this to me

I do though, since I need to evaluate the places? unless I misunderstood you

Hmm I was thinking that if this ran after ConstProp, then we'd see things like

_4 = CheckedAdd(move _3, const 0i32);
Wesley Wiser (Jul 13 2020 at 19:34, on Zulip):

So you'd just walk every MIR statement looking for things like CheckedAdd or Add where one of the arguments is const 0i{size}

Xavier Denis (Jul 13 2020 at 19:34, on Zulip):

for whatever reason in the original bitand example

Xavier Denis (Jul 13 2020 at 19:34, on Zulip):

the false is not propagated

Xavier Denis (Jul 13 2020 at 19:35, on Zulip):

so in the original example we get BitAnd(_X, _Y)

Wesley Wiser (Jul 13 2020 at 19:35, on Zulip):

Hmm

Xavier Denis (Jul 13 2020 at 19:35, on Zulip):

seems like there could be a seperate issue propagating bools?

Xavier Denis (Jul 13 2020 at 19:35, on Zulip):

I'll start by adding this peephole opt for binary operations

Xavier Denis (Jul 13 2020 at 19:36, on Zulip):

then i'll figure out why false is not propagating

Wesley Wiser (Jul 13 2020 at 19:37, on Zulip):

Is this what you're seeing? https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=5352bfb0576e4efc33a357bde970def7

Wesley Wiser (Jul 13 2020 at 19:37, on Zulip):

_4 = BitAnd(move _5, const false); // scope 0 at src/lib.rs:2:10: 2:21

Xavier Denis (Jul 13 2020 at 19:38, on Zulip):

look at oli's example

Xavier Denis (Jul 13 2020 at 19:38, on Zulip):

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1ef992fe05b4e49b40ff5f63acc796d5

Xavier Denis (Jul 13 2020 at 19:38, on Zulip):

_3 = const false;
_5 = BitAnd(move _3, move _4);

Wesley Wiser (Jul 13 2020 at 19:38, on Zulip):

Oh

Wesley Wiser (Jul 13 2020 at 19:38, on Zulip):

Gotcha

Xavier Denis (Jul 13 2020 at 19:38, on Zulip):

ohhh i think that's cuz the bitand

Wesley Wiser (Jul 13 2020 at 19:39, on Zulip):

Yeah, we don't do partial propagation yet

Xavier Denis (Jul 13 2020 at 19:39, on Zulip):

is inserted during lowering

Wesley Wiser (Jul 13 2020 at 19:39, on Zulip):

ConstProp currently really wants to evaluate & replace the entire statement

Xavier Denis (Jul 13 2020 at 19:39, on Zulip):

ah nvm, I thought it could have been from a pass between const prop and instcombine

Xavier Denis (Jul 13 2020 at 19:39, on Zulip):

yep, I noticed :P

Wesley Wiser (Jul 13 2020 at 19:39, on Zulip):

Not just whatever parts it knows the values to

Wesley Wiser (Jul 13 2020 at 19:39, on Zulip):

Heh

Xavier Denis (Jul 13 2020 at 19:40, on Zulip):

but couldn't it still propagate _3 into _5?

Xavier Denis (Jul 13 2020 at 19:40, on Zulip):

it knows it's value...

Xavier Denis (Jul 13 2020 at 19:43, on Zulip):

InstCombine is also run before ConstProp

Xavier Denis (Jul 13 2020 at 20:21, on Zulip):

hmm seems like for this opt to be useful it has to be in ConstProp and I'll need to write something like eval_rval_into_place which only does binaryops with missing args

Xavier Denis (Jul 13 2020 at 20:23, on Zulip):

or, I need to get constant prop to properly propagate simple constants into rvalues + flip the ordering between the passes

Wesley Wiser (Jul 13 2020 at 20:35, on Zulip):

That's true. Putting it in const props seems fine.

Xavier Denis (Jul 13 2020 at 20:58, on Zulip):

in summary: rustc only propagates constants if it can immediately fold them. this means that when an operation uses a non-constant value, propagation isn't done. this prevents writing a simple peephole opt which folds neutral elements / top elements for &, |, +, -, / etc..

Félix Fischer (Jul 14 2020 at 05:55, on Zulip):

Hellu

Félix Fischer (Jul 14 2020 at 05:55, on Zulip):

I think it makes sense to run this after const-prop

Félix Fischer (Jul 14 2020 at 05:55, on Zulip):

Um

Félix Fischer (Jul 14 2020 at 05:55, on Zulip):

Also!

Félix Fischer (Jul 14 2020 at 05:56, on Zulip):

@Xavier Denis I'm getting ready to write my thesis on mir-opts. I plan to complete the current const-prop implementation, by letting it go past blocks

Félix Fischer (Jul 14 2020 at 05:57, on Zulip):

Currently const-prop propagates constants more or less forever

Félix Fischer (Jul 14 2020 at 05:57, on Zulip):

Like "const" constants

Félix Fischer (Jul 14 2020 at 05:57, on Zulip):

But we don't have the same yet for local variables that also happen to reduce to a constant at compile time, if that makes sense

Félix Fischer (Jul 14 2020 at 05:59, on Zulip):

I will be working on that so don't worry

Félix Fischer (Jul 14 2020 at 05:59, on Zulip):

I'll cover those bases for you

Félix Fischer (Jul 14 2020 at 05:59, on Zulip):

:heart:

Félix Fischer (Jul 14 2020 at 06:00, on Zulip):

We have an algorithm ready (that oli and I think is correct). I just need to get past bureaucracy with uni now ^^

Félix Fischer (Jul 14 2020 at 06:01, on Zulip):

But yeah, coming back to local vars. The reason they don't get propagated further is that we have restricted their propagation to just their own blocks

Félix Fischer (Jul 14 2020 at 06:02, on Zulip):

Because when you get into other blocks you have to be aware of control flow

Félix Fischer (Jul 14 2020 at 06:05, on Zulip):

I think it makes sense to add your opt in const-prop.

Adding zero, multiplying by one, multiplying by zero, doing & false and | true, are all edge cases of expression evaluation that can result in simplified expressions at compile time.

Félix Fischer (Jul 14 2020 at 06:06, on Zulip):

So... I think it makes sense. To add it to const-prop. @oli what do you think?

oli (Jul 14 2020 at 07:52, on Zulip):

Wesley Wiser said:

Yeah, we don't do partial propagation yet

that's why I wanted to do this in const prop first. Another reason is that in contrast to a + 0, we can continue const propping after true | a, so if we do it in const prop we don't need a fixed point iteration

RalfJ (Jul 15 2020 at 07:32, on Zulip):

Wesley Wiser said:

Given that you don't need any interpreter state to recognize the a + 0 == a case (or any of the other binary operators) that pass seems like a better fit for this to me

well there can be advantages to doing both together, if a const-prop simplification and an instcombine mutually depend on each other.
out constprop likely is not powerful enough for that though.

Xavier Denis (Jul 17 2020 at 22:31, on Zulip):

I got x || false and x && true working :) but getting cases like x + 0 working is awkward with the current const_prop setup and would be better suited to instcombine currently I think.

oli (Jul 18 2020 at 06:46, on Zulip):

sounds good, let's do nop integer math on non-constants in a separate PR

Xavier Denis (Jul 18 2020 at 20:18, on Zulip):

I noticed however that constant prop misses a lot of opportunities currently, it doesn't actually push constants into the operands of rvalues!

Xavier Denis (Jul 18 2020 at 20:19, on Zulip):

this makes it easy to get code like _1 = 5; _2 = x + _1 it'd be nice for it to at least constprop _1 into _2

Xavier Denis (Jul 18 2020 at 20:36, on Zulip):

I think it's just a matter of adding another case to the visitor so that we properly substitute into operands

Lokathor (Jul 19 2020 at 02:01, on Zulip):

As a side question: is this at least an optimization the LLVM catches later in the compilation? and then adding this to MIR just helps generics and miri and such?

Félix Fischer (Jul 19 2020 at 07:55, on Zulip):

@Lokathor the one that Xavier just mentioned? Yes. This is something that LLVM catches later.

Félix Fischer (Jul 19 2020 at 07:56, on Zulip):

Adding this to MIR helps because MIR is more aware of everything. LLVM has to do a lot of work to optimize our code. Doing it in MIR is more efficient.

Félix Fischer (Jul 19 2020 at 07:57, on Zulip):

@Xavier Denis it actually does push them, but it cannot currently do so for all cases. Locals aren't propagated outside of their own block.

Félix Fischer (Jul 19 2020 at 07:58, on Zulip):

That is what I'll be working on

Félix Fischer (Jul 19 2020 at 07:58, on Zulip):

Because the code that you posted should and will be able to propagate ^^

Félix Fischer (Jul 19 2020 at 08:01, on Zulip):

I'm not yet coding it because I have to wait on uni to start my thesis. But it's the first on my list, and oli and I have an algorithm in mind to do the propagation without breaking correct code.

oli (Jul 19 2020 at 08:58, on Zulip):

propagating into operands is an independent thing of the cross basic-block optimization, if someone wants to implement that for more things than call terminators, I'd be happy to mentor

lcnr (Jul 19 2020 at 09:10, on Zulip):

@oli wanna give me some pointers, this seems interesting?

Xavier Denis (Jul 19 2020 at 09:31, on Zulip):

I checked it doesn’t and they are marked as always propagate

Xavier Denis (Jul 19 2020 at 09:32, on Zulip):

The problem is the code only propagates into a statement if that statement itself is good to propagate

Xavier Denis (Jul 19 2020 at 09:32, on Zulip):

But I’ll leave it to toy

oli (Jul 19 2020 at 09:33, on Zulip):

it only propagates into assignments to locals if the entire local is constant

oli (Jul 19 2020 at 09:33, on Zulip):

if you have x + known_to_be_const, there's no partial propagation happening

oli (Jul 19 2020 at 09:33, on Zulip):

discussion and impl about that continues in https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/const.20prop.20into.20operands/near/204339934

Xavier Denis (Jul 19 2020 at 10:08, on Zulip):

Yep that’s what I meant

Félix Fischer (Jul 19 2020 at 18:28, on Zulip):

Ahhh I see, my bad

Félix Fischer (Jul 19 2020 at 18:28, on Zulip):

:)

Xavier Denis (Jul 20 2020 at 21:22, on Zulip):

weeiiird... I'm getting a bizarre failure from my changes

Xavier Denis (Jul 20 2020 at 21:22, on Zulip):

but it's not actually the optimization??

Xavier Denis (Jul 20 2020 at 21:47, on Zulip):

it seems related to running these lines:

                    let l = this.ecx.eval_operand(left, None);
                    let r = this.ecx.eval_operand(right, None);

                    if let (Ok(_), Ok(_)) = (&l, &r) {
                        this.ecx.eval_rvalue_into_place(rvalue, place)?;
                        return Ok(());
                    }
Xavier Denis (Jul 20 2020 at 21:47, on Zulip):

but i really don't see how that would cause crossbeam-utils to no longer compile

Xavier Denis (Jul 20 2020 at 22:31, on Zulip):

if i replace the if let by using is_ok everything compiles?

Last update: Sep 28 2020 at 16:30UTC