This is an archive of the discontinued LLVM Phabricator instance.

[PredicateInfo] Order instructions in different BBs by DFSNumIn.
ClosedPublic

Authored by fhahn on Jun 15 2018, 12:17 PM.

Details

Summary

Using OrderedInstructions::dominates as comparator for instructions in
BBs without dominance relation can cause a non-deterministic order
between such instructions. That in turn can cause us to materialize
copies in a non-deterministic order. While this does not effect
correctness, it causes some minor non-determinism in the final generated
code, because values have slightly different labels.

Without this patch, running -print-predicateinfo on a reasonably large
module produces slightly different output on each run.

This patch uses the dominator trees DFSInNum to order instruction from
different BBs, which should enforce a deterministic ordering and
guarantee that dominated instructions come after the instructions that
dominate them.

Diff Detail

Event Timeline

fhahn created this revision.Jun 15 2018, 12:17 PM
fhahn added a subscriber: sdesmalen.

because values have slightly different labels

Not sure you're diagnosing the issue correctly; IR optimizations shouldn't care about the names of instructions/basic blocks, as far as I know. But in any case, we need to fix this because a bad sort predicate causes undefined behavior.

Can you think of any way to write a testcase for this?

lib/Transforms/Utils/PredicateInfo.cpp
110

Please fix this comment to note that this only works for instructions in the same BB.

557

There shouldn't be null values in OpSet; you can use dyn_cast instead of dyn_cast_or_null.

fhahn added a comment.Jun 15 2018, 2:28 PM

because values have slightly different labels

Not sure you're diagnosing the issue correctly; IR optimizations shouldn't care about the names of instructions/basic blocks, as far as I know. But in any case, we need to fix this because a bad sort predicate causes undefined behavior.

Yep I think the issue I hit because of this was not related to IR optimization, but something in the strtab generation in codegen.

Can you think of any way to write a testcase for this?

I suppose I could add a test case which would visit ops in different orders without this patch and add checks to make sure they are visited in the expected order?

klimek added a subscriber: klimek.Jun 15 2018, 4:52 PM

Florian: did you manually add Danny on this (the account is disabled and I'm trying to figure out where / how folks are added).

@klimek I think he just replied to the llvm-commits email.

Oh, wait, you mean in the "Reviewers" field; nevermind.

Florian: did you manually add Danny on this (the account is disabled and I'm trying to figure out where / how folks are added).

Yes I think I added his account as reviewer when creating this patch. I did not realize that the account was slightly grey compared to the others in the search drop down. Sorry about that.

fhahn updated this revision to Diff 151892.Jun 19 2018, 7:00 AM

I moved the logic to OrderedInstructions::comesBefore, because I think it makes sense there and has potential to be useful in other places too. I've also added a test case where the collected values are visited in non-deterministic order without this patch and added a debug line to easily check the order.

If that is not desirable, I think I could come up with a larger test case, which also exposes the problem, but might not fail as reliable without this patch.

efriedma added inline comments.Jun 19 2018, 12:08 PM
lib/Transforms/Utils/OrderedInstructions.cpp
17

localDominates.

41

Maybe rename this dfsBefore, so it's more clear what it means by "before"?

test/Transforms/Util/PredicateInfo/ordering.ll
1

Need a REQUIRES line to use -debug.

Instead of checking debug output, could we check the use-list order? (-preserve-ll-uselistorder)

fhahn updated this revision to Diff 151969.Jun 19 2018, 1:12 PM

Renamed functions and added REQUIRES: assert

I had a look at verify-uselistorder, but I am not sure how it would help with the test unfortunately. The order of OpsToRename is unrelated to the use-list order I think. But I am probably missing something about using uselistorder when testing.

efriedma accepted this revision.Jun 19 2018, 1:49 PM

LGTM

Maybe the use list order isn't affected in this exact testcase. In general, the order ssa.copy intrinsics are inserted matters, though.

This revision is now accepted and ready to land.Jun 19 2018, 1:49 PM
This revision was automatically updated to reflect the committed changes.