Page MenuHomePhabricator

[PHINode] Preserve use-list order when removing incoming values.
Needs ReviewPublic

Authored by fhahn on Jul 17 2019, 2:26 PM.

Details

Summary

Currently we remove/add all ops we copy from their use lists. We can
just swap the op to remove with the last op, which preserves the
use-lists and needs fewer copies.

But it changes the order of the PHI operands. With this change, 14 unit
tests fail. If that's no concern, I'll go ahead and update them.
Otherwise we could also do the copy with preserving the use-list order I
think.

My motivation for this change is to fix a case where we end up with
a non-deterministic use-list order after simplifycfg, which I think is
caused by this trashing of the use-lists.

Event Timeline

fhahn created this revision.Jul 17 2019, 2:26 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 17 2019, 2:26 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn updated this revision to Diff 210554.Jul 18 2019, 6:59 AM

Add move assignment operator that preserves the uselist order and use
std::move instead of std::copy. This preserves the original order of operands instead
of swapping them, which is slightly better IMO as swapping would mean that the order
of the remaining operands is dependent on the order in which we remove incoming values.

rnk removed a reviewer: rnk.Aug 6 2019, 1:41 PM
rnk added a subscriber: rnk.

My motivation for this change is to fix a case where we end up with a non-deterministic use-list order after simplifycfg, which I think is caused by this trashing of the use-lists.

I don't see how this could be a problem. Sure, mixing up the order is sort of confusing, but it should get mixed up in a deterministic way.

llvm/include/llvm/IR/Value.h
739

Is this "if" actually necessary? Use::removeFromList just unconditionally dereferences Prev.

llvm/lib/IR/Instructions.cpp
129

Even if this patch fixes the use/def list thrashing, swap would still be faster.

fhahn marked an inline comment as done.Mon, Sep 16, 1:14 PM

My motivation for this change is to fix a case where we end up with a non-deterministic use-list order after simplifycfg, which I think is caused by this trashing of the use-lists.

I don't see how this could be a problem. Sure, mixing up the order is sort of confusing, but it should get mixed up in a deterministic way.

I think I came across this for a codegen non-determinism case fixed by rL365970.

The issue there was that removing blocks in non-deterministic order caused non-deterministic codegen later on, because depending on the deletion order, the use lists order of some PHIs were different. With this fix, we would not have to enforce an order on block deletions, at least not because of the use-list issue.

llvm/lib/IR/Instructions.cpp
129

Yep, I also fixed a similar use-list issue when wapping, so we could swap here as well (D64886).

But that would make the order of incoming values dependent on the deletion order, I think, defeating the original motivation of the patch.