aboutsummaryrefslogtreecommitdiff
path: root/llvm/tools/llvm-diff/DifferenceEngine.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/tools/llvm-diff/DifferenceEngine.cpp')
-rw-r--r--llvm/tools/llvm-diff/DifferenceEngine.cpp265
1 files changed, 186 insertions, 79 deletions
diff --git a/llvm/tools/llvm-diff/DifferenceEngine.cpp b/llvm/tools/llvm-diff/DifferenceEngine.cpp
index 64c0dc61e806..eb746cd2a865 100644
--- a/llvm/tools/llvm-diff/DifferenceEngine.cpp
+++ b/llvm/tools/llvm-diff/DifferenceEngine.cpp
@@ -113,22 +113,29 @@ public:
class FunctionDifferenceEngine {
DifferenceEngine &Engine;
+ // Some initializers may reference the variable we're currently checking. This
+ // can cause an infinite loop. The Saved[LR]HS ivars can be checked to prevent
+ // recursing.
+ const Value *SavedLHS;
+ const Value *SavedRHS;
+
/// The current mapping from old local values to new local values.
- DenseMap<Value*, Value*> Values;
+ DenseMap<const Value *, const Value *> Values;
/// The current mapping from old blocks to new blocks.
- DenseMap<BasicBlock*, BasicBlock*> Blocks;
+ DenseMap<const BasicBlock *, const BasicBlock *> Blocks;
- DenseSet<std::pair<Value*, Value*> > TentativeValues;
+ DenseSet<std::pair<const Value *, const Value *>> TentativeValues;
- unsigned getUnprocPredCount(BasicBlock *Block) const {
+ unsigned getUnprocPredCount(const BasicBlock *Block) const {
unsigned Count = 0;
- for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I)
+ for (const_pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E;
+ ++I)
if (!Blocks.count(*I)) Count++;
return Count;
}
- typedef std::pair<BasicBlock*, BasicBlock*> BlockPair;
+ typedef std::pair<const BasicBlock *, const BasicBlock *> BlockPair;
/// A type which sorts a priority queue by the number of unprocessed
/// predecessor blocks it has remaining.
@@ -138,7 +145,7 @@ class FunctionDifferenceEngine {
const FunctionDifferenceEngine &fde;
explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {}
- bool operator()(const BlockPair &Old, const BlockPair &New) {
+ bool operator()(BlockPair &Old, BlockPair &New) {
return fde.getUnprocPredCount(Old.first)
< fde.getUnprocPredCount(New.first);
}
@@ -151,8 +158,8 @@ class FunctionDifferenceEngine {
/// if they haven't already been processed.
///
/// Returns true if there was a problem unifying them.
- bool tryUnify(BasicBlock *L, BasicBlock *R) {
- BasicBlock *&Ref = Blocks[L];
+ bool tryUnify(const BasicBlock *L, const BasicBlock *R) {
+ const BasicBlock *&Ref = Blocks[L];
if (Ref) {
if (Ref == R) return false;
@@ -167,10 +174,10 @@ class FunctionDifferenceEngine {
Queue.insert(BlockPair(L, R));
return false;
}
-
+
/// Unifies two instructions, given that they're known not to have
/// structural differences.
- void unify(Instruction *L, Instruction *R) {
+ void unify(const Instruction *L, const Instruction *R) {
DifferenceEngine::Context C(Engine, L, R);
bool Result = diff(L, R, true, true);
@@ -187,15 +194,15 @@ class FunctionDifferenceEngine {
}
}
- void diff(BasicBlock *L, BasicBlock *R) {
+ void diff(const BasicBlock *L, const BasicBlock *R) {
DifferenceEngine::Context C(Engine, L, R);
- BasicBlock::iterator LI = L->begin(), LE = L->end();
- BasicBlock::iterator RI = R->begin();
+ BasicBlock::const_iterator LI = L->begin(), LE = L->end();
+ BasicBlock::const_iterator RI = R->begin();
do {
assert(LI != LE && RI != R->end());
- Instruction *LeftI = &*LI, *RightI = &*RI;
+ const Instruction *LeftI = &*LI, *RightI = &*RI;
// If the instructions differ, start the more sophisticated diff
// algorithm at the start of the block.
@@ -219,10 +226,11 @@ class FunctionDifferenceEngine {
unify(&*LI, &*RI);
}
- bool matchForBlockDiff(Instruction *L, Instruction *R);
- void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI);
+ bool matchForBlockDiff(const Instruction *L, const Instruction *R);
+ void runBlockDiff(BasicBlock::const_iterator LI,
+ BasicBlock::const_iterator RI);
- bool diffCallSites(CallBase &L, CallBase &R, bool Complain) {
+ bool diffCallSites(const CallBase &L, const CallBase &R, bool Complain) {
// FIXME: call attributes
if (!equivalentAsOperands(L.getCalledOperand(), R.getCalledOperand())) {
if (Complain) Engine.log("called functions differ");
@@ -242,7 +250,8 @@ class FunctionDifferenceEngine {
return false;
}
- bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) {
+ bool diff(const Instruction *L, const Instruction *R, bool Complain,
+ bool TryUnify) {
// FIXME: metadata (if Complain is set)
// Different opcodes always imply different operations.
@@ -273,8 +282,8 @@ class FunctionDifferenceEngine {
// Terminators.
} else if (isa<InvokeInst>(L)) {
- InvokeInst &LI = cast<InvokeInst>(*L);
- InvokeInst &RI = cast<InvokeInst>(*R);
+ const InvokeInst &LI = cast<InvokeInst>(*L);
+ const InvokeInst &RI = cast<InvokeInst>(*R);
if (diffCallSites(LI, RI, Complain))
return true;
@@ -284,9 +293,30 @@ class FunctionDifferenceEngine {
}
return false;
+ } else if (isa<CallBrInst>(L)) {
+ const CallBrInst &LI = cast<CallBrInst>(*L);
+ const CallBrInst &RI = cast<CallBrInst>(*R);
+ if (LI.getNumIndirectDests() != RI.getNumIndirectDests()) {
+ if (Complain)
+ Engine.log("callbr # of indirect destinations differ");
+ return true;
+ }
+
+ // Perform the "try unify" step so that we can equate the indirect
+ // destinations before checking the call site.
+ for (unsigned I = 0; I < LI.getNumIndirectDests(); I++)
+ tryUnify(LI.getIndirectDest(I), RI.getIndirectDest(I));
+
+ if (diffCallSites(LI, RI, Complain))
+ return true;
+
+ if (TryUnify)
+ tryUnify(LI.getDefaultDest(), RI.getDefaultDest());
+ return false;
+
} else if (isa<BranchInst>(L)) {
- BranchInst *LI = cast<BranchInst>(L);
- BranchInst *RI = cast<BranchInst>(R);
+ const BranchInst *LI = cast<BranchInst>(L);
+ const BranchInst *RI = cast<BranchInst>(R);
if (LI->isConditional() != RI->isConditional()) {
if (Complain) Engine.log("branch conditionality differs");
return true;
@@ -303,8 +333,8 @@ class FunctionDifferenceEngine {
return false;
} else if (isa<IndirectBrInst>(L)) {
- IndirectBrInst *LI = cast<IndirectBrInst>(L);
- IndirectBrInst *RI = cast<IndirectBrInst>(R);
+ const IndirectBrInst *LI = cast<IndirectBrInst>(L);
+ const IndirectBrInst *RI = cast<IndirectBrInst>(R);
if (LI->getNumDestinations() != RI->getNumDestinations()) {
if (Complain) Engine.log("indirectbr # of destinations differ");
return true;
@@ -323,8 +353,8 @@ class FunctionDifferenceEngine {
return false;
} else if (isa<SwitchInst>(L)) {
- SwitchInst *LI = cast<SwitchInst>(L);
- SwitchInst *RI = cast<SwitchInst>(R);
+ const SwitchInst *LI = cast<SwitchInst>(L);
+ const SwitchInst *RI = cast<SwitchInst>(R);
if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
if (Complain) Engine.log("switch conditions differ");
return true;
@@ -333,13 +363,13 @@ class FunctionDifferenceEngine {
bool Difference = false;
- DenseMap<ConstantInt*,BasicBlock*> LCases;
+ DenseMap<const ConstantInt *, const BasicBlock *> LCases;
for (auto Case : LI->cases())
LCases[Case.getCaseValue()] = Case.getCaseSuccessor();
for (auto Case : RI->cases()) {
- ConstantInt *CaseValue = Case.getCaseValue();
- BasicBlock *LCase = LCases[CaseValue];
+ const ConstantInt *CaseValue = Case.getCaseValue();
+ const BasicBlock *LCase = LCases[CaseValue];
if (LCase) {
if (TryUnify)
tryUnify(LCase, Case.getCaseSuccessor());
@@ -351,8 +381,10 @@ class FunctionDifferenceEngine {
}
}
if (!Difference)
- for (DenseMap<ConstantInt*,BasicBlock*>::iterator
- I = LCases.begin(), E = LCases.end(); I != E; ++I) {
+ for (DenseMap<const ConstantInt *, const BasicBlock *>::iterator
+ I = LCases.begin(),
+ E = LCases.end();
+ I != E; ++I) {
if (Complain)
Engine.logf("left switch has extra case %l") << I->first;
Difference = true;
@@ -378,14 +410,15 @@ class FunctionDifferenceEngine {
return false;
}
- bool equivalentAsOperands(Constant *L, Constant *R) {
+public:
+ bool equivalentAsOperands(const Constant *L, const Constant *R) {
// Use equality as a preliminary filter.
if (L == R)
return true;
if (L->getValueID() != R->getValueID())
return false;
-
+
// Ask the engine about global values.
if (isa<GlobalValue>(L))
return Engine.equivalentAsOperands(cast<GlobalValue>(L),
@@ -409,8 +442,8 @@ class FunctionDifferenceEngine {
// If L and R are ConstantVectors, compare each element
if (isa<ConstantVector>(L)) {
- ConstantVector *CVL = cast<ConstantVector>(L);
- ConstantVector *CVR = cast<ConstantVector>(R);
+ const ConstantVector *CVL = cast<ConstantVector>(L);
+ const ConstantVector *CVR = cast<ConstantVector>(R);
if (CVL->getType()->getNumElements() != CVR->getType()->getNumElements())
return false;
for (unsigned i = 0; i < CVL->getType()->getNumElements(); i++) {
@@ -420,12 +453,68 @@ class FunctionDifferenceEngine {
return true;
}
+ // If L and R are ConstantArrays, compare the element count and types.
+ if (isa<ConstantArray>(L)) {
+ const ConstantArray *CAL = cast<ConstantArray>(L);
+ const ConstantArray *CAR = cast<ConstantArray>(R);
+ // Sometimes a type may be equivalent, but not uniquified---e.g. it may
+ // contain a GEP instruction. Do a deeper comparison of the types.
+ if (CAL->getType()->getNumElements() != CAR->getType()->getNumElements())
+ return false;
+
+ for (unsigned I = 0; I < CAL->getType()->getNumElements(); ++I) {
+ if (!equivalentAsOperands(CAL->getAggregateElement(I),
+ CAR->getAggregateElement(I)))
+ return false;
+ }
+
+ return true;
+ }
+
+ // If L and R are ConstantStructs, compare each field and type.
+ if (isa<ConstantStruct>(L)) {
+ const ConstantStruct *CSL = cast<ConstantStruct>(L);
+ const ConstantStruct *CSR = cast<ConstantStruct>(R);
+
+ const StructType *LTy = cast<StructType>(CSL->getType());
+ const StructType *RTy = cast<StructType>(CSR->getType());
+
+ // The StructTypes should have the same attributes. Don't use
+ // isLayoutIdentical(), because that just checks the element pointers,
+ // which may not work here.
+ if (LTy->getNumElements() != RTy->getNumElements() ||
+ LTy->isPacked() != RTy->isPacked())
+ return false;
+
+ for (unsigned I = 0; I < LTy->getNumElements(); I++) {
+ const Value *LAgg = CSL->getAggregateElement(I);
+ const Value *RAgg = CSR->getAggregateElement(I);
+
+ if (LAgg == SavedLHS || RAgg == SavedRHS) {
+ if (LAgg != SavedLHS || RAgg != SavedRHS)
+ // If the left and right operands aren't both re-analyzing the
+ // variable, then the initialiers don't match, so report "false".
+ // Otherwise, we skip these operands..
+ return false;
+
+ continue;
+ }
+
+ if (!equivalentAsOperands(LAgg, RAgg)) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
return false;
}
- bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) {
+ bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R) {
if (L == R)
return true;
+
if (L->getOpcode() != R->getOpcode())
return false;
@@ -447,14 +536,28 @@ class FunctionDifferenceEngine {
if (L->getNumOperands() != R->getNumOperands())
return false;
- for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I)
- if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I)))
+ for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
+ const auto *LOp = L->getOperand(I);
+ const auto *ROp = R->getOperand(I);
+
+ if (LOp == SavedLHS || ROp == SavedRHS) {
+ if (LOp != SavedLHS || ROp != SavedRHS)
+ // If the left and right operands aren't both re-analyzing the
+ // variable, then the initialiers don't match, so report "false".
+ // Otherwise, we skip these operands..
+ return false;
+
+ continue;
+ }
+
+ if (!equivalentAsOperands(LOp, ROp))
return false;
+ }
return true;
}
- bool equivalentAsOperands(Value *L, Value *R) {
+ bool equivalentAsOperands(const Value *L, const Value *R) {
// Fall out if the values have different kind.
// This possibly shouldn't take priority over oracles.
if (L->getValueID() != R->getValueID())
@@ -483,17 +586,19 @@ class FunctionDifferenceEngine {
FunctionDifferenceEngine *this_() { return this; }
public:
- FunctionDifferenceEngine(DifferenceEngine &Engine) :
- Engine(Engine), Queue(QueueSorter(*this_())) {}
+ FunctionDifferenceEngine(DifferenceEngine &Engine,
+ const Value *SavedLHS = nullptr,
+ const Value *SavedRHS = nullptr)
+ : Engine(Engine), SavedLHS(SavedLHS), SavedRHS(SavedRHS),
+ Queue(QueueSorter(*this_())) {}
- void diff(Function *L, Function *R) {
+ void diff(const Function *L, const Function *R) {
if (L->arg_size() != R->arg_size())
Engine.log("different argument counts");
// Map the arguments.
- for (Function::arg_iterator
- LI = L->arg_begin(), LE = L->arg_end(),
- RI = R->arg_begin(), RE = R->arg_end();
+ for (Function::const_arg_iterator LI = L->arg_begin(), LE = L->arg_end(),
+ RI = R->arg_begin(), RE = R->arg_end();
LI != LE && RI != RE; ++LI, ++RI)
Values[&*LI] = &*RI;
@@ -509,15 +614,15 @@ struct DiffEntry {
llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
};
-bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L,
- Instruction *R) {
+bool FunctionDifferenceEngine::matchForBlockDiff(const Instruction *L,
+ const Instruction *R) {
return !diff(L, R, false, false);
}
-void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
- BasicBlock::iterator RStart) {
- BasicBlock::iterator LE = LStart->getParent()->end();
- BasicBlock::iterator RE = RStart->getParent()->end();
+void FunctionDifferenceEngine::runBlockDiff(BasicBlock::const_iterator LStart,
+ BasicBlock::const_iterator RStart) {
+ BasicBlock::const_iterator LE = LStart->getParent()->end();
+ BasicBlock::const_iterator RE = RStart->getParent()->end();
unsigned NL = std::distance(LStart, LE);
@@ -540,14 +645,14 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
Cur[I].Path.push_back(DC_left);
}
- for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) {
+ for (BasicBlock::const_iterator RI = RStart; RI != RE; ++RI) {
// Initialize the first row.
Next[0] = Cur[0];
Next[0].Cost += RightCost;
Next[0].Path.push_back(DC_right);
unsigned Index = 1;
- for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) {
+ for (BasicBlock::const_iterator LI = LStart; LI != LE; ++LI, ++Index) {
if (matchForBlockDiff(&*LI, &*RI)) {
Next[Index] = Cur[Index-1];
Next[Index].Cost += MatchCost;
@@ -572,7 +677,7 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
TentativeValues.clear();
SmallVectorImpl<char> &Path = Cur[NL].Path;
- BasicBlock::iterator LI = LStart, RI = RStart;
+ BasicBlock::const_iterator LI = LStart, RI = RStart;
DiffLogBuilder Diff(Engine.getConsumer());
@@ -595,7 +700,7 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
case DC_match:
assert(LI != LE && RI != RE);
{
- Instruction *L = &*LI, *R = &*RI;
+ const Instruction *L = &*LI, *R = &*RI;
unify(L, R);
Diff.addMatch(L, R);
}
@@ -628,16 +733,16 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
// If the terminators have different kinds, but one is an invoke and the
// other is an unconditional branch immediately following a call, unify
// the results and the destinations.
- Instruction *LTerm = LStart->getParent()->getTerminator();
- Instruction *RTerm = RStart->getParent()->getTerminator();
+ const Instruction *LTerm = LStart->getParent()->getTerminator();
+ const Instruction *RTerm = RStart->getParent()->getTerminator();
if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
if (cast<BranchInst>(LTerm)->isConditional()) return;
- BasicBlock::iterator I = LTerm->getIterator();
+ BasicBlock::const_iterator I = LTerm->getIterator();
if (I == LStart->getParent()->begin()) return;
--I;
if (!isa<CallInst>(*I)) return;
- CallInst *LCall = cast<CallInst>(&*I);
- InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
+ const CallInst *LCall = cast<CallInst>(&*I);
+ const InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
if (!equivalentAsOperands(LCall->getCalledOperand(),
RInvoke->getCalledOperand()))
return;
@@ -646,12 +751,12 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest());
} else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) {
if (cast<BranchInst>(RTerm)->isConditional()) return;
- BasicBlock::iterator I = RTerm->getIterator();
+ BasicBlock::const_iterator I = RTerm->getIterator();
if (I == RStart->getParent()->begin()) return;
--I;
if (!isa<CallInst>(*I)) return;
- CallInst *RCall = cast<CallInst>(I);
- InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
+ const CallInst *RCall = cast<CallInst>(I);
+ const InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
if (!equivalentAsOperands(LInvoke->getCalledOperand(),
RCall->getCalledOperand()))
return;
@@ -660,12 +765,11 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
}
}
-
}
void DifferenceEngine::Oracle::anchor() { }
-void DifferenceEngine::diff(Function *L, Function *R) {
+void DifferenceEngine::diff(const Function *L, const Function *R) {
Context C(*this, L, R);
// FIXME: types
@@ -683,15 +787,15 @@ void DifferenceEngine::diff(Function *L, Function *R) {
FunctionDifferenceEngine(*this).diff(L, R);
}
-void DifferenceEngine::diff(Module *L, Module *R) {
+void DifferenceEngine::diff(const Module *L, const Module *R) {
StringSet<> LNames;
- SmallVector<std::pair<Function*,Function*>, 20> Queue;
+ SmallVector<std::pair<const Function *, const Function *>, 20> Queue;
unsigned LeftAnonCount = 0;
unsigned RightAnonCount = 0;
- for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) {
- Function *LFn = &*I;
+ for (Module::const_iterator I = L->begin(), E = L->end(); I != E; ++I) {
+ const Function *LFn = &*I;
StringRef Name = LFn->getName();
if (Name.empty()) {
++LeftAnonCount;
@@ -706,8 +810,8 @@ void DifferenceEngine::diff(Module *L, Module *R) {
logf("function %l exists only in left module") << LFn;
}
- for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) {
- Function *RFn = &*I;
+ for (Module::const_iterator I = R->begin(), E = R->end(); I != E; ++I) {
+ const Function *RFn = &*I;
StringRef Name = RFn->getName();
if (Name.empty()) {
++RightAnonCount;
@@ -718,7 +822,6 @@ void DifferenceEngine::diff(Module *L, Module *R) {
logf("function %r exists only in right module") << RFn;
}
-
if (LeftAnonCount != 0 || RightAnonCount != 0) {
SmallString<32> Tmp;
logf(("not comparing " + Twine(LeftAnonCount) +
@@ -727,20 +830,24 @@ void DifferenceEngine::diff(Module *L, Module *R) {
.toStringRef(Tmp));
}
- for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator
- I = Queue.begin(), E = Queue.end(); I != E; ++I)
+ for (SmallVectorImpl<std::pair<const Function *, const Function *>>::iterator
+ I = Queue.begin(),
+ E = Queue.end();
+ I != E; ++I)
diff(I->first, I->second);
}
-bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) {
+bool DifferenceEngine::equivalentAsOperands(const GlobalValue *L,
+ const GlobalValue *R) {
if (globalValueOracle) return (*globalValueOracle)(L, R);
if (isa<GlobalVariable>(L) && isa<GlobalVariable>(R)) {
- GlobalVariable *GVL = cast<GlobalVariable>(L);
- GlobalVariable *GVR = cast<GlobalVariable>(R);
+ const GlobalVariable *GVL = cast<GlobalVariable>(L);
+ const GlobalVariable *GVR = cast<GlobalVariable>(R);
if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() &&
GVR->hasLocalLinkage() && GVR->hasUniqueInitializer())
- return GVL->getInitializer() == GVR->getInitializer();
+ return FunctionDifferenceEngine(*this, GVL, GVR)
+ .equivalentAsOperands(GVL->getInitializer(), GVR->getInitializer());
}
return L->getName() == R->getName();
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-27 20:41:59 +0000