Page MenuHomePhabricator

[IRSim] Adding a basic similarity identifier.
ClosedPublic

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

Details

Summary

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.
llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
612

explicit

654

ArrayRef

Updating for explicit and for ArrayRef.

jroelofs added inline comments.Sep 17 2020, 11:51 AM
llvm/include/llvm/Analysis/IRSimilarityIdentifier.h
676

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

llvm/lib/Transforms/IPO/IROutliner.cpp
260 ↗(On Diff #292640)

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

275 ↗(On Diff #292640)
llvm/lib/Transforms/IPO/PassManagerBuilder.cpp
107 ↗(On Diff #292640)
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.
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
491

Seems not used, could be removed?

AndrewLitteken added inline comments.Sep 24 2020, 7:57 AM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
491

Yes, I believe they can be.