This is an archive of the discontinued LLVM Phabricator instance.

[MergeICmps] Don't reorder unmerged comparisons
ClosedPublic

Authored by nikic on Sep 18 2021, 8:49 AM.

Details

Summary

MergeICmps will currently sort (by offset) all comparisons in a chain, including those that do not get merged. This is problematic in two ways:

  • We may end up moving the original first block into the middle of the chain, in which case the "extra work" instructions will also be in the middle of the chain, resulting in invalid IR (https://reviews.llvm.org/D108782#3005583).
  • Reordering branches is generally not legal, because it may introduce branch on poison, which is UB (https://bugs.llvm.org/show_bug.cgi?id=51845). The merging done by MergeICmps is legal as long as we assume that memcmp() works on frozen memory, but the reordering of unmerged comparisons is definitely incorrect (without inserting freeze instructions), so we should avoid it.

There are easier ways to fix the first issue, but I figured it was worthwhile to do this properly to also fix the second one. What we now do is to restore the original relative order of (potentially merged) comparisons.

I took the liberty of dropping the MERGEICMPS_DOT_ON functionality, because it would be more awkward to implement now (as the before and after representation is different) and it doesn't seem terribly useful nowadays.

Diff Detail

Event Timeline

nikic created this revision.Sep 18 2021, 8:49 AM
nikic requested review of this revision.Sep 18 2021, 8:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 18 2021, 8:49 AM
nikic edited the summary of this revision. (Show Details)Sep 18 2021, 8:51 AM
courbet added inline comments.Sep 20 2021, 12:40 AM
llvm/lib/Transforms/Scalar/MergeICmps.cpp
407–408

Can you please add a comment for the reader to say what these represent ? Something like "The list of all blocks in the chain, grouped by contiguity."

I think it would also help readability to introduce an alias:

using ContiguousBlocks = std::vector<BCECmpBlock>;

std::vector<ContiguousBlocks> MergedBlocks;
429

Add a comment to state what this does, e.g.

// Given a  chain of comparison blocks, groups the blocks into contiguous ranges that can be merged together in a single comparison.
llvm/test/Transforms/MergeICmps/X86/entry-block-shuffled-2.ll
2

can you submit the test as a preliminary step so that we can see the diff here ?

Can you also please clang-format the diff ?

nikic added inline comments.Sep 20 2021, 12:50 AM
llvm/test/Transforms/MergeICmps/X86/entry-block-shuffled-2.ll
2

The test fails verification before the test. Do you suggest to commit it with -disable-verify?

courbet added inline comments.Sep 20 2021, 12:52 AM
llvm/test/Transforms/MergeICmps/X86/entry-block-shuffled-2.ll
2

Never mind. I was thinking we would see the first block after the merged one, but obviously this would fail verification...

nikic updated this revision to Diff 373627.Sep 20 2021, 9:40 AM
nikic marked 2 inline comments as done.

Add ContiguousBlocks alias, add comments, fix style.

courbet accepted this revision.Sep 20 2021, 10:46 PM
This revision is now accepted and ready to land.Sep 20 2021, 10:46 PM
This revision was landed with ongoing or failed builds.Sep 21 2021, 12:22 PM
This revision was automatically updated to reflect the committed changes.