This is an archive of the discontinued LLVM Phabricator instance.

[IRSim] Adding structural comparison to IRSimilarityCandidate.
ClosedPublic

Authored by AndrewLitteken on Sep 1 2020, 1:16 PM.

Details

Summary

Just because sequences of instructions are similar to one another, doesn't mean they are doing the same thing.

This introduces a structural check for the IRSimilarityCandidate that compares two IRSimilarityCandidates against one another, and in each instruction creates a mapping between the operands and results, or checks that the existing mapping is valid. If this check passes, it means we have structurally similar IRSimilarityCandidates.

Tests for whether the candidates are found in unittests/Analysis/IRSimilarityIdentifierTest.cpp.

Diff Detail

Event Timeline

AndrewLitteken created this revision.Sep 1 2020, 1:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2020, 1:16 PM
AndrewLitteken added a reviewer: paquette.

Updating for clang-format.

AndrewLitteken added a subscriber: jroelofs.

Updating SmallVectors to ArrayRefs, related to comment by @jroelofs in https://reviews.llvm.org/D87311.

jroelofs added inline comments.Sep 15 2020, 9:34 AM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
364

does this iterator have an operator->()?

Updating iterator use.

jroelofs accepted this revision.Sep 16 2020, 8:37 AM

LGTM, with some optional suggestions.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
404
463–467

Functions with a ton of parameters like this can sometimes get a bit unwieldy, but this one has an obvious structure that could be taken advantage of. What do you think about making the signature be:

struct OperandMapping {
  const IRSimilarityCandidate &IRSC;
  ArrayRef<Value *> &OperVals;
  DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMapping;
};

static bool compareOperandMapping(OperandMapping A, OperandMapping B);

Then the call site is just:

compareOperandMapping({ A, OperVals, ValueNumberMapping },
                      { B, OtherOperVals, OtherValueNumberMapping });

and everything gets grouped succinctly.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp
343

In here, all the names are Thing/OtherThing-ish, whereas in compareOperandMapping they're AThing/BThing-ish. I think it'd be helpful to keep the latter style to have them consistent.

This revision is now accepted and ready to land.Sep 16 2020, 8:37 AM
AndrewLitteken added inline comments.Sep 16 2020, 9:43 AM
llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
463–467

I think that would definitely make it easier to work with from the outside. I'll change it to this style.

Updating to reduce complexity of function call.

update LGTM too