summaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/IRSimilarityIdentifier.cpp')
-rw-r--r--llvm/lib/Analysis/IRSimilarityIdentifier.cpp262
1 files changed, 238 insertions, 24 deletions
diff --git a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
index a6298afb66f5..f22c6aa04f5e 100644
--- a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
+++ b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp
@@ -23,13 +23,23 @@
using namespace llvm;
using namespace IRSimilarity;
+cl::opt<bool>
+ DisableBranches("no-ir-sim-branch-matching", cl::init(false),
+ cl::ReallyHidden,
+ cl::desc("disable similarity matching, and outlining, "
+ "across branches for debugging purposes."));
+
IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
IRInstructionDataList &IDList)
: Inst(&I), Legal(Legality), IDL(&IDList) {
+ initializeInstruction();
+}
+
+void IRInstructionData::initializeInstruction() {
// We check for whether we have a comparison instruction. If it is, we
// find the "less than" version of the predicate for consistency for
// comparison instructions throught the program.
- if (CmpInst *C = dyn_cast<CmpInst>(&I)) {
+ if (CmpInst *C = dyn_cast<CmpInst>(Inst)) {
CmpInst::Predicate Predicate = predicateForConsistency(C);
if (Predicate != C->getPredicate())
RevisedPredicate = Predicate;
@@ -37,8 +47,8 @@ IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
// Here we collect the operands and their types for determining whether
// the structure of the operand use matches between two different candidates.
- for (Use &OI : I.operands()) {
- if (isa<CmpInst>(I) && RevisedPredicate.hasValue()) {
+ for (Use &OI : Inst->operands()) {
+ if (isa<CmpInst>(Inst) && RevisedPredicate.hasValue()) {
// If we have a CmpInst where the predicate is reversed, it means the
// operands must be reversed as well.
OperVals.insert(OperVals.begin(), OI.get());
@@ -49,6 +59,33 @@ IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
}
}
+IRInstructionData::IRInstructionData(IRInstructionDataList &IDList)
+ : Inst(nullptr), Legal(false), IDL(&IDList) {}
+
+void IRInstructionData::setBranchSuccessors(
+ DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger) {
+ assert(isa<BranchInst>(Inst) && "Instruction must be branch");
+
+ BranchInst *BI = cast<BranchInst>(Inst);
+ DenseMap<BasicBlock *, unsigned>::iterator BBNumIt;
+
+ BBNumIt = BasicBlockToInteger.find(BI->getParent());
+ assert(BBNumIt != BasicBlockToInteger.end() &&
+ "Could not find location for BasicBlock!");
+
+ int CurrentBlockNumber = static_cast<int>(BBNumIt->second);
+
+ for (BasicBlock *Successor : BI->successors()) {
+ BBNumIt = BasicBlockToInteger.find(Successor);
+ assert(BBNumIt != BasicBlockToInteger.end() &&
+ "Could not find number for BasicBlock!");
+ int OtherBlockNumber = static_cast<int>(BBNumIt->second);
+
+ int Relative = OtherBlockNumber - CurrentBlockNumber;
+ RelativeBlockLocations.push_back(Relative);
+ }
+}
+
CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) {
switch (CI->getPredicate()) {
case CmpInst::FCMP_OGT:
@@ -143,6 +180,10 @@ bool IRSimilarity::isClose(const IRInstructionData &A,
return false;
}
+ if (isa<BranchInst>(A.Inst) && isa<BranchInst>(B.Inst) &&
+ A.RelativeBlockLocations.size() != B.RelativeBlockLocations.size())
+ return false;
+
return true;
}
@@ -156,10 +197,6 @@ void IRInstructionMapper::convertToUnsignedVec(
std::vector<unsigned> IntegerMappingForBB;
std::vector<IRInstructionData *> InstrListForBB;
- HaveLegalRange = false;
- CanCombineWithPrevInstr = false;
- AddedIllegalLastTime = true;
-
for (BasicBlock::iterator Et = BB.end(); It != Et; ++It) {
switch (InstClassifier.visit(*It)) {
case InstrType::Legal:
@@ -175,7 +212,8 @@ void IRInstructionMapper::convertToUnsignedVec(
}
if (HaveLegalRange) {
- mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
+ if (AddedIllegalLastTime)
+ mapToIllegalUnsigned(It, IntegerMappingForBB, InstrListForBB, true);
for (IRInstructionData *ID : InstrListForBB)
this->IDL->push_back(*ID);
llvm::append_range(InstrList, InstrListForBB);
@@ -203,6 +241,9 @@ unsigned IRInstructionMapper::mapToLegalUnsigned(
IRInstructionData *ID = allocateIRInstructionData(*It, true, *IDL);
InstrListForBB.push_back(ID);
+ if (isa<BranchInst>(*It))
+ ID->setBranchSuccessors(BasicBlockToInteger);
+
// Add to the instruction list
bool WasInserted;
DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>::iterator
@@ -235,6 +276,11 @@ IRInstructionMapper::allocateIRInstructionData(Instruction &I, bool Legality,
return new (InstDataAllocator->Allocate()) IRInstructionData(I, Legality, IDL);
}
+IRInstructionData *
+IRInstructionMapper::allocateIRInstructionData(IRInstructionDataList &IDL) {
+ return new (InstDataAllocator->Allocate()) IRInstructionData(IDL);
+}
+
IRInstructionDataList *
IRInstructionMapper::allocateIRInstructionDataList() {
return new (IDLAllocator->Allocate()) IRInstructionDataList();
@@ -255,6 +301,8 @@ unsigned IRInstructionMapper::mapToIllegalUnsigned(
IRInstructionData *ID = nullptr;
if (!End)
ID = allocateIRInstructionData(*It, false, *IDL);
+ else
+ ID = allocateIRInstructionData(*IDL);
InstrListForBB.push_back(ID);
// Remember that we added an illegal number last time.
@@ -563,8 +611,50 @@ bool IRSimilarityCandidate::compareCommutativeOperandMapping(
return true;
}
+bool IRSimilarityCandidate::checkRelativeLocations(RelativeLocMapping A,
+ RelativeLocMapping B) {
+ // Get the basic blocks the label refers to.
+ BasicBlock *ABB = static_cast<BasicBlock *>(A.OperVal);
+ BasicBlock *BBB = static_cast<BasicBlock *>(B.OperVal);
+
+ // Get the basic blocks contained in each region.
+ DenseSet<BasicBlock *> BasicBlockA;
+ DenseSet<BasicBlock *> BasicBlockB;
+ A.IRSC.getBasicBlocks(BasicBlockA);
+ B.IRSC.getBasicBlocks(BasicBlockB);
+
+ // Determine if the block is contained in the region.
+ bool AContained = BasicBlockA.contains(ABB);
+ bool BContained = BasicBlockB.contains(BBB);
+
+ // Both blocks need to be contained in the region, or both need to be outside
+ // the reigon.
+ if (AContained != BContained)
+ return false;
+
+ // If both are contained, then we need to make sure that the relative
+ // distance to the target blocks are the same.
+ if (AContained)
+ return A.RelativeLocation == B.RelativeLocation;
+ return true;
+}
+
bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
const IRSimilarityCandidate &B) {
+ DenseMap<unsigned, DenseSet<unsigned>> MappingA;
+ DenseMap<unsigned, DenseSet<unsigned>> MappingB;
+ return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB);
+}
+
+typedef detail::zippy<detail::zip_shortest, SmallVector<int, 4> &,
+ SmallVector<int, 4> &, ArrayRef<Value *> &,
+ ArrayRef<Value *> &>
+ ZippedRelativeLocationsT;
+
+bool IRSimilarityCandidate::compareStructure(
+ const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
+ DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
+ DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) {
if (A.getLength() != B.getLength())
return false;
@@ -574,15 +664,12 @@ bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
iterator ItA = A.begin();
iterator ItB = B.begin();
- // These sets create a create a mapping between the values in one candidate
- // to values in the other candidate. If we create a set with one element,
- // and that same element maps to the original element in the candidate
- // we have a good mapping.
- DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
- DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingB;
+ // These ValueNumber Mapping sets create a create a mapping between the values
+ // in one candidate to values in the other candidate. If we create a set with
+ // one element, and that same element maps to the original element in the
+ // candidate we have a good mapping.
DenseMap<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
- bool WasInserted;
// Iterate over the instructions contained in each candidate
unsigned SectionLength = A.getStartIdx() + A.getLength();
@@ -605,6 +692,7 @@ bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
unsigned InstValA = A.ValueToNumber.find(IA)->second;
unsigned InstValB = B.ValueToNumber.find(IB)->second;
+ bool WasInserted;
// Ensure that the mappings for the instructions exists.
std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert(
std::make_pair(InstValA, DenseSet<unsigned>({InstValB})));
@@ -632,6 +720,37 @@ bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
{A, OperValsA, ValueNumberMappingA},
{B, OperValsB, ValueNumberMappingB}))
return false;
+
+ // Here we check that between two corresponding instructions,
+ // when referring to a basic block in the same region, the
+ // relative locations are the same. And, that the instructions refer to
+ // basic blocks outside the region in the same corresponding locations.
+
+ // We are able to make the assumption about blocks outside of the region
+ // since the target block labels are considered values and will follow the
+ // same number matching that we defined for the other instructions in the
+ // region. So, at this point, in each location we target a specific block
+ // outside the region, we are targeting a corresponding block in each
+ // analagous location in the region we are comparing to.
+ if (!(isa<BranchInst>(IA) && isa<BranchInst>(IB)) &&
+ !(isa<PHINode>(IA) && isa<PHINode>(IB)))
+ continue;
+
+ SmallVector<int, 4> &RelBlockLocsA = ItA->RelativeBlockLocations;
+ SmallVector<int, 4> &RelBlockLocsB = ItB->RelativeBlockLocations;
+ if (RelBlockLocsA.size() != RelBlockLocsB.size() &&
+ OperValsA.size() != OperValsB.size())
+ return false;
+
+ ZippedRelativeLocationsT ZippedRelativeLocations =
+ zip(RelBlockLocsA, RelBlockLocsB, OperValsA, OperValsB);
+ if (any_of(ZippedRelativeLocations,
+ [&A, &B](std::tuple<int, int, Value *, Value *> R) {
+ return !checkRelativeLocations(
+ {A, std::get<0>(R), std::get<2>(R)},
+ {B, std::get<1>(R), std::get<3>(R)});
+ }))
+ return false;
}
return true;
}
@@ -657,6 +776,8 @@ void IRSimilarityIdentifier::populateMapper(
std::vector<unsigned> IntegerMappingForModule;
// Iterate over the functions in the module to map each Instruction in each
// BasicBlock to an unsigned integer.
+ Mapper.initializeForBBs(M);
+
for (Function &F : M) {
if (F.empty())
@@ -664,15 +785,18 @@ void IRSimilarityIdentifier::populateMapper(
for (BasicBlock &BB : F) {
- if (BB.sizeWithoutDebug() < 2)
- continue;
-
// BB has potential to have similarity since it has a size greater than 2
// and can therefore match other regions greater than 2. Map it to a list
// of unsigned integers.
Mapper.convertToUnsignedVec(BB, InstrListForModule,
IntegerMappingForModule);
}
+
+ BasicBlock::iterator It = F.begin()->end();
+ Mapper.mapToIllegalUnsigned(It, IntegerMappingForModule, InstrListForModule,
+ true);
+ if (InstrListForModule.size() > 0)
+ Mapper.IDL->push_back(*InstrListForModule.back());
}
// Insert the InstrListForModule at the end of the overall InstrList so that
@@ -707,6 +831,8 @@ static void createCandidatesFromSuffixTree(
std::vector<IRSimilarityCandidate> &CandsForRepSubstring) {
unsigned StringLen = RS.Length;
+ if (StringLen < 2)
+ return;
// Create an IRSimilarityCandidate for instance of this subsequence \p RS.
for (const unsigned &StartIdx : RS.StartIndices) {
@@ -739,6 +865,84 @@ static void createCandidatesFromSuffixTree(
}
}
+void IRSimilarityCandidate::createCanonicalRelationFrom(
+ IRSimilarityCandidate &SourceCand,
+ DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
+ DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping) {
+ assert(SourceCand.CanonNumToNumber.size() != 0 &&
+ "Base canonical relationship is empty!");
+ assert(SourceCand.NumberToCanonNum.size() != 0 &&
+ "Base canonical relationship is empty!");
+
+ assert(CanonNumToNumber.size() == 0 && "Canonical Relationship is non-empty");
+ assert(NumberToCanonNum.size() == 0 && "Canonical Relationship is non-empty");
+
+ DenseSet<unsigned> UsedGVNs;
+ // Iterate over the mappings provided from this candidate to SourceCand. We
+ // are then able to map the GVN in this candidate to the same canonical number
+ // given to the corresponding GVN in SourceCand.
+ for (std::pair<unsigned, DenseSet<unsigned>> &GVNMapping : ToSourceMapping) {
+ unsigned SourceGVN = GVNMapping.first;
+
+ assert(GVNMapping.second.size() != 0 && "Possible GVNs is 0!");
+
+ unsigned ResultGVN;
+ // We need special handling if we have more than one potential value. This
+ // means that there are at least two GVNs that could correspond to this GVN.
+ // This could lead to potential swapping later on, so we make a decision
+ // here to ensure a one-to-one mapping.
+ if (GVNMapping.second.size() > 1) {
+ bool Found = false;
+ for (unsigned Val : GVNMapping.second) {
+ // We make sure the target value number hasn't already been reserved.
+ if (UsedGVNs.contains(Val))
+ continue;
+
+ // We make sure that the opposite mapping is still consistent.
+ DenseMap<unsigned, DenseSet<unsigned>>::iterator It =
+ FromSourceMapping.find(Val);
+
+ if (!It->second.contains(SourceGVN))
+ continue;
+
+ // We pick the first item that satisfies these conditions.
+ Found = true;
+ ResultGVN = Val;
+ break;
+ }
+
+ assert(Found && "Could not find matching value for source GVN");
+ (void)Found;
+
+ } else
+ ResultGVN = *GVNMapping.second.begin();
+
+ // Whatever GVN is found, we mark it as used.
+ UsedGVNs.insert(ResultGVN);
+
+ unsigned CanonNum = *SourceCand.getCanonicalNum(ResultGVN);
+ CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN));
+ NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum));
+ }
+}
+
+void IRSimilarityCandidate::createCanonicalMappingFor(
+ IRSimilarityCandidate &CurrCand) {
+ assert(CurrCand.CanonNumToNumber.size() == 0 &&
+ "Canonical Relationship is non-empty");
+ assert(CurrCand.NumberToCanonNum.size() == 0 &&
+ "Canonical Relationship is non-empty");
+
+ unsigned CanonNum = 0;
+ // Iterate over the value numbers found, the order does not matter in this
+ // case.
+ for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {
+ CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum));
+ CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first));
+ CanonNum++;
+ }
+}
+
/// From the list of IRSimilarityCandidates, perform a comparison between each
/// IRSimilarityCandidate to determine if there are overlapping
/// IRInstructionData, or if they do not have the same structure.
@@ -774,6 +978,8 @@ static void findCandidateStructures(
// Iterate over the candidates to determine its structural and overlapping
// compatibility with other instructions
+ DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
+ DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingB;
for (CandIt = CandsForRepSubstring.begin(),
CandEndIt = CandsForRepSubstring.end();
CandIt != CandEndIt; CandIt++) {
@@ -792,9 +998,11 @@ static void findCandidateStructures(
// Check if we already have a list of IRSimilarityCandidates for the current
// structural group. Create one if one does not exist.
CurrentGroupPair = StructuralGroups.find(OuterGroupNum);
- if (CurrentGroupPair == StructuralGroups.end())
+ if (CurrentGroupPair == StructuralGroups.end()) {
+ IRSimilarityCandidate::createCanonicalMappingFor(*CandIt);
std::tie(CurrentGroupPair, Inserted) = StructuralGroups.insert(
std::make_pair(OuterGroupNum, SimilarityGroup({*CandIt})));
+ }
// Iterate over the IRSimilarityCandidates following the current
// IRSimilarityCandidate in the list to determine whether the two
@@ -811,11 +1019,15 @@ static void findCandidateStructures(
// Otherwise we determine if they have the same structure and add it to
// vector if they match.
- SameStructure =
- IRSimilarityCandidate::compareStructure(*CandIt, *InnerCandIt);
+ ValueNumberMappingA.clear();
+ ValueNumberMappingB.clear();
+ SameStructure = IRSimilarityCandidate::compareStructure(
+ *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);
if (!SameStructure)
continue;
+ InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA,
+ ValueNumberMappingB);
CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
CurrentGroupPair->second.push_back(*InnerCandIt);
}
@@ -862,6 +1074,7 @@ SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
std::vector<IRInstructionData *> InstrList;
std::vector<unsigned> IntegerMapping;
+ Mapper.InstClassifier.EnableBranches = this->EnableBranches;
populateMapper(Modules, InstrList, IntegerMapping);
findCandidates(InstrList, IntegerMapping);
@@ -871,6 +1084,7 @@ SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(
SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(Module &M) {
resetSimilarityCandidates();
+ Mapper.InstClassifier.EnableBranches = this->EnableBranches;
std::vector<IRInstructionData *> InstrList;
std::vector<unsigned> IntegerMapping;
@@ -891,7 +1105,7 @@ IRSimilarityIdentifierWrapperPass::IRSimilarityIdentifierWrapperPass()
}
bool IRSimilarityIdentifierWrapperPass::doInitialization(Module &M) {
- IRSI.reset(new IRSimilarityIdentifier());
+ IRSI.reset(new IRSimilarityIdentifier(!DisableBranches));
return false;
}
@@ -907,9 +1121,9 @@ bool IRSimilarityIdentifierWrapperPass::runOnModule(Module &M) {
AnalysisKey IRSimilarityAnalysis::Key;
IRSimilarityIdentifier IRSimilarityAnalysis::run(Module &M,
- ModuleAnalysisManager &) {
+ ModuleAnalysisManager &) {
- auto IRSI = IRSimilarityIdentifier();
+ auto IRSI = IRSimilarityIdentifier(!DisableBranches);
IRSI.findSimilarity(M);
return IRSI;
}
generated by cgit v1.3 (git 2.53.0) at 2026-07-28 03:32:59 +0000