//
//===----------------------------------------------------------------------===//
//
-// This header defines the interface to the LLVM difference engine,
-// which structurally compares functions within a module.
+// This header defines the implementation of the LLVM difference
+// engine, which structurally compares global values within a module.
//
//===----------------------------------------------------------------------===//
-#include <utility>
-
-#include <llvm/ADT/DenseMap.h>
-#include <llvm/ADT/DenseSet.h>
-#include <llvm/ADT/SmallVector.h>
-#include <llvm/ADT/StringRef.h>
-#include <llvm/ADT/StringSet.h>
-
-#include <llvm/Module.h>
-#include <llvm/Function.h>
-#include <llvm/Instructions.h>
-#include <llvm/Support/CFG.h>
-
-#include <llvm/Support/raw_ostream.h>
-#include <llvm/Support/type_traits.h>
-#include <llvm/Support/ErrorHandling.h>
-#include <llvm/Support/CallSite.h>
-
#include "DifferenceEngine.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/type_traits.h"
+#include <utility>
using namespace llvm;
/// The current mapping from old blocks to new blocks.
DenseMap<BasicBlock*, BasicBlock*> Blocks;
- DenseSet<std::pair<Value*, Value*> > TentativeValuePairs;
+ DenseSet<std::pair<Value*, Value*> > TentativeValues;
unsigned getUnprocPredCount(BasicBlock *Block) const {
unsigned Count = 0;
if (Ref) {
if (Ref == R) return false;
- Engine.logf("successor %s cannot be equivalent to %s; "
- "it's already equivalent to %s")
+ Engine.logf("successor %l cannot be equivalent to %r; "
+ "it's already equivalent to %r")
<< L << R << Ref;
return true;
}
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) {
+ DifferenceEngine::Context C(Engine, L, R);
+
+ bool Result = diff(L, R, true, true);
+ assert(!Result && "structural differences second time around?");
+ (void) Result;
+ if (!L->use_empty())
+ Values[L] = R;
+ }
void processQueue() {
while (!Queue.empty()) {
DifferenceEngine::Context C(Engine, L, R);
BasicBlock::iterator LI = L->begin(), LE = L->end();
- BasicBlock::iterator RI = R->begin(), RE = R->end();
+ BasicBlock::iterator RI = R->begin();
do {
- assert(LI != LE && RI != RE);
+ assert(LI != LE && RI != R->end());
Instruction *LeftI = &*LI, *RightI = &*RI;
// If the instructions differ, start the more sophisticated diff
- // algorithm here.
- if (diff(LeftI, RightI, false, true))
- return runBlockDiff(LI, RI);
+ // algorithm at the start of the block.
+ if (diff(LeftI, RightI, false, false)) {
+ TentativeValues.clear();
+ return runBlockDiff(L->begin(), R->begin());
+ }
- // Otherwise, unify them.
+ // Otherwise, tentatively unify them.
if (!LeftI->use_empty())
- Values[LeftI] = RightI;
+ TentativeValues.insert(std::make_pair(LeftI, RightI));
++LI, ++RI;
} while (LI != LE); // This is sufficient: we can't get equality of
// terminators if there are residual instructions.
+
+ // Unify everything in the block, non-tentatively this time.
+ TentativeValues.clear();
+ for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
+ unify(&*LI, &*RI);
}
bool matchForBlockDiff(Instruction *L, Instruction *R);
for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) {
if (Complain)
- Engine.logf("arguments %s and %s differ")
+ Engine.logf("arguments %l and %r differ")
<< L.getArgument(I) << R.getArgument(I);
return true;
}
} else if (isa<PHINode>(L)) {
// FIXME: implement.
- // This is really wierd; type uniquing is broken?
+ // This is really weird; type uniquing is broken?
if (L->getType() != R->getType()) {
if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) {
if (Complain) Engine.log("different phi types");
bool Difference = false;
DenseMap<ConstantInt*,BasicBlock*> LCases;
- for (unsigned I = 1, E = LI->getNumCases(); I != E; ++I)
- LCases[LI->getCaseValue(I)] = LI->getSuccessor(I);
- for (unsigned I = 1, E = RI->getNumCases(); I != E; ++I) {
- ConstantInt *CaseValue = RI->getCaseValue(I);
+
+ for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end();
+ I != E; ++I)
+ LCases[I.getCaseValue()] = I.getCaseSuccessor();
+
+ for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end();
+ I != E; ++I) {
+ ConstantInt *CaseValue = I.getCaseValue();
BasicBlock *LCase = LCases[CaseValue];
if (LCase) {
- if (TryUnify) tryUnify(LCase, RI->getSuccessor(I));
+ if (TryUnify) tryUnify(LCase, I.getCaseSuccessor());
LCases.erase(CaseValue);
- } else if (!Difference) {
+ } else if (Complain || !Difference) {
if (Complain)
- Engine.logf("right switch has extra case %s") << CaseValue;
+ Engine.logf("right switch has extra case %r") << CaseValue;
Difference = true;
}
}
for (DenseMap<ConstantInt*,BasicBlock*>::iterator
I = LCases.begin(), E = LCases.end(); I != E; ++I) {
if (Complain)
- Engine.logf("left switch has extra case %s") << I->first;
+ Engine.logf("left switch has extra case %l") << I->first;
Difference = true;
}
return Difference;
for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
Value *LO = L->getOperand(I), *RO = R->getOperand(I);
if (!equivalentAsOperands(LO, RO)) {
- if (Complain) Engine.logf("operands %s and %s differ") << LO << RO;
+ if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
return true;
}
}
return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
if (isa<Instruction>(L))
- return Values[L] == R || TentativeValuePairs.count(std::make_pair(L, R));
+ return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
if (isa<Argument>(L))
return Values[L] == R;
DiffEntry *Cur = Paths1.data();
DiffEntry *Next = Paths2.data();
- assert(TentativeValuePairs.empty());
+ const unsigned LeftCost = 2;
+ const unsigned RightCost = 2;
+ const unsigned MatchCost = 0;
+
+ assert(TentativeValues.empty());
// Initialize the first column.
for (unsigned I = 0; I != NL+1; ++I) {
- Cur[I].Cost = I;
+ Cur[I].Cost = I * LeftCost;
for (unsigned J = 0; J != I; ++J)
- Cur[I].Path.push_back(DifferenceEngine::DC_left);
+ Cur[I].Path.push_back(DC_left);
}
for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) {
// Initialize the first row.
Next[0] = Cur[0];
- Next[0].Path.push_back(DifferenceEngine::DC_right);
+ Next[0].Cost += RightCost;
+ Next[0].Path.push_back(DC_right);
unsigned Index = 1;
for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) {
if (matchForBlockDiff(&*LI, &*RI)) {
Next[Index] = Cur[Index-1];
- Next[Index].Path.push_back(DifferenceEngine::DC_match);
- TentativeValuePairs.insert(std::make_pair(&*LI, &*RI));
+ Next[Index].Cost += MatchCost;
+ Next[Index].Path.push_back(DC_match);
+ TentativeValues.insert(std::make_pair(&*LI, &*RI));
} else if (Next[Index-1].Cost <= Cur[Index].Cost) {
Next[Index] = Next[Index-1];
- Next[Index].Path.push_back(DifferenceEngine::DC_left);
+ Next[Index].Cost += LeftCost;
+ Next[Index].Path.push_back(DC_left);
} else {
Next[Index] = Cur[Index];
- Next[Index].Path.push_back(DifferenceEngine::DC_right);
+ Next[Index].Cost += RightCost;
+ Next[Index].Path.push_back(DC_right);
}
}
std::swap(Cur, Next);
}
+ // We don't need the tentative values anymore; everything from here
+ // on out should be non-tentative.
+ TentativeValues.clear();
+
SmallVectorImpl<char> &Path = Cur[NL].Path;
BasicBlock::iterator LI = LStart, RI = RStart;
- DifferenceEngine::DiffLogBuilder Diff(Engine);
+ DiffLogBuilder Diff(Engine.getConsumer());
// Drop trailing matches.
- while (Path.back() == DifferenceEngine::DC_match)
+ while (Path.back() == DC_match)
Path.pop_back();
- for (SmallVectorImpl<char>::iterator
- PI = Path.begin(), PE = Path.end(); PI != PE; ++PI) {
- switch (static_cast<DifferenceEngine::DiffChange>(*PI)) {
- case DifferenceEngine::DC_match:
+ // Skip leading matches.
+ SmallVectorImpl<char>::iterator
+ PI = Path.begin(), PE = Path.end();
+ while (PI != PE && *PI == DC_match) {
+ unify(&*LI, &*RI);
+ ++PI, ++LI, ++RI;
+ }
+
+ for (; PI != PE; ++PI) {
+ switch (static_cast<DiffChange>(*PI)) {
+ case DC_match:
assert(LI != LE && RI != RE);
{
Instruction *L = &*LI, *R = &*RI;
- DifferenceEngine::Context C(Engine, L, R);
- diff(L, R, false, true);
+ unify(L, R);
Diff.addMatch(L, R);
}
++LI; ++RI;
break;
- case DifferenceEngine::DC_left:
+ case DC_left:
assert(LI != LE);
Diff.addLeft(&*LI);
++LI;
break;
- case DifferenceEngine::DC_right:
+ case DC_right:
assert(RI != RE);
Diff.addRight(&*RI);
++RI;
}
}
- TentativeValuePairs.clear();
+ // Finishing unifying and complaining about the tails of the block,
+ // which should be matches all the way through.
+ while (LI != LE) {
+ assert(RI != RE);
+ unify(&*LI, &*RI);
+ ++LI, ++RI;
+ }
+
+ // 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.
+ TerminatorInst *LTerm = LStart->getParent()->getTerminator();
+ TerminatorInst *RTerm = RStart->getParent()->getTerminator();
+ if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
+ if (cast<BranchInst>(LTerm)->isConditional()) return;
+ BasicBlock::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);
+ if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue()))
+ return;
+ if (!LCall->use_empty())
+ Values[LCall] = RInvoke;
+ 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();
+ if (I == RStart->getParent()->begin()) return;
+ --I;
+ if (!isa<CallInst>(*I)) return;
+ CallInst *RCall = cast<CallInst>(I);
+ InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
+ if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue()))
+ return;
+ if (!LInvoke->use_empty())
+ Values[LInvoke] = RCall;
+ tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
+ }
}
}
+void DifferenceEngine::Oracle::anchor() { }
+
void DifferenceEngine::diff(Function *L, Function *R) {
Context C(*this, L, R);
if (Function *RFn = R->getFunction(LFn->getName()))
Queue.push_back(std::make_pair(LFn, RFn));
else
- logf("function %s exists only in left module") << LFn;
+ logf("function %l exists only in left module") << LFn;
}
for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) {
Function *RFn = &*I;
if (!LNames.count(RFn->getName()))
- logf("function %s exists only in right module") << RFn;
+ logf("function %r exists only in right module") << RFn;
}
for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator
projects / oota-llvm.git / blobdiff