This is an archive of the discontinued LLVM Phabricator instance.

[IRSim] Adding a basic similarity identifier.

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



This takes the mapped instructions from the IRInstructionMapper, and passes it to the Suffix Tree to find the repeated substrings. Within each set of repeated substrings, the IRSimilarityCandidates are compared against one another for structure, and ensuring that the operands in the instructions are used in the same way. Each of these structurally similarity IRSimilarityCandidates are contained in a SimilarityGroup.

Tests checking for identifying identity of structure, different isomorphic structure, and different nonisomoprhic structure are found in unittests/Analysis/IRSimilarityIdentifierTest.cpp.

Diff Detail

Event Timeline

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

Updating for clang-format.

jroelofs added inline comments.
574 ↗(On Diff #289465)


616 ↗(On Diff #289465)


Updating for explicit and for ArrayRef.

jroelofs added inline comments.Sep 17 2020, 11:51 AM
644 ↗(On Diff #292093)

I think it would force better hygiene on it if instead of being a flag, this were represented as SimilarityCandidates being an Optional<>.

Updating flag for SimilarityCandidates to an Optional.

Updating optional handling.

jroelofs accepted this revision.Sep 18 2020, 9:17 AM

small nits, otherwise LGTM


I think this check is unnecessary. Sorting one element is already a no-op.

This revision is now accepted and ready to land.Sep 18 2020, 9:17 AM

I'm not sure what happened, but I uploaded the entirely wrong diff last time. This is the similarity identifier with the optional changes.

This revision was automatically updated to reflect the committed changes.
danielkiss added inline comments.
491 ↗(On Diff #293948)

Seems not used, could be removed?

AndrewLitteken added inline comments.Sep 24 2020, 7:57 AM
491 ↗(On Diff #293948)

Yes, I believe they can be.