X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=tools%2Fllvm-diff%2FDifferenceEngine.cpp;h=0c1e30c987ea31288635fff4fee4695e65cd4e20;hb=0aa32d5d0ff6cd65b6cff957858a79e2d2a614bd;hp=764b56a296acef40f9bb8ce42653f514dd0f31ac;hpb=e2921432b6e0ba916ebfca312ae2cac7641279ec;p=oota-llvm.git diff --git a/tools/llvm-diff/DifferenceEngine.cpp b/tools/llvm-diff/DifferenceEngine.cpp index 764b56a296a..0c1e30c987e 100644 --- a/tools/llvm-diff/DifferenceEngine.cpp +++ b/tools/llvm-diff/DifferenceEngine.cpp @@ -7,30 +7,29 @@ // //===----------------------------------------------------------------------===// // -// 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 - -#include -#include -#include -#include -#include - -#include -#include -#include -#include +#include "DifferenceEngine.h" -#include -#include -#include -#include +#include "llvm/Constants.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/Module.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/Support/CallSite.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/type_traits.h" -#include "DifferenceEngine.h" +#include using namespace llvm; @@ -172,6 +171,18 @@ 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) { + 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()) { @@ -184,12 +195,12 @@ class FunctionDifferenceEngine { 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(); llvm::SmallVector, 20> TentativePairs; 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 @@ -207,22 +218,10 @@ class FunctionDifferenceEngine { } 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(); - - // Do another pass over the block, this time in complaints mode. - LI = L->begin(); RI = R->begin(); - do { - assert(LI != LE && RI != RE); - bool Result = diff(&*LI, &*RI, true, true); - assert(!Result && "structural differences second time around?"); - (void) Result; - - // Make the mapping non-tentative this time. - if (!LI->use_empty()) - Values[&*LI] = &*RI; - - ++LI, ++RI; - } while (LI != LE); + for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI) + unify(&*LI, &*RI); } bool matchForBlockDiff(Instruction *L, Instruction *R); @@ -268,7 +267,7 @@ class FunctionDifferenceEngine { } else if (isa(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"); @@ -319,23 +318,27 @@ class FunctionDifferenceEngine { bool Difference = false; - DenseMap 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); + DenseMap LCases; + + for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end(); + I != E; ++I) + LCases[I.getCaseValueEx()] = I.getCaseSuccessor(); + + for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end(); + I != E; ++I) { + IntegersSubset CaseValue = I.getCaseValueEx(); 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 %r") << CaseValue; Difference = true; } } if (!Difference) - for (DenseMap::iterator + for (DenseMap::iterator I = LCases.begin(), E = LCases.end(); I != E; ++I) { if (Complain) Engine.logf("left switch has extra case %l") << I->first; @@ -508,72 +511,76 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart, for (unsigned I = 0; I != NL+1; ++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].Cost += RightCost; - Next[0].Path.push_back(DifferenceEngine::DC_right); + 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].Cost += MatchCost; - Next[Index].Path.push_back(DifferenceEngine::DC_match); + 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].Cost += LeftCost; - Next[Index].Path.push_back(DifferenceEngine::DC_left); + Next[Index].Path.push_back(DC_left); } else { Next[Index] = Cur[Index]; Next[Index].Cost += RightCost; - Next[Index].Path.push_back(DifferenceEngine::DC_right); + 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 &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(); // Skip leading matches. SmallVectorImpl::iterator PI = Path.begin(), PE = Path.end(); - while (PI != PE && *PI == DifferenceEngine::DC_match) + while (PI != PE && *PI == DC_match) { + unify(&*LI, &*RI); ++PI, ++LI, ++RI; + } for (; PI != PE; ++PI) { - switch (static_cast(*PI)) { - case DifferenceEngine::DC_match: + switch (static_cast(*PI)) { + case DC_match: assert(LI != LE && RI != RE); { Instruction *L = &*LI, *R = &*RI; - DifferenceEngine::Context C(Engine, L, R); - diff(L, R, true, true); // complain and unify successors - Values[L] = R; // make non-tentative + 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; @@ -581,11 +588,52 @@ void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart, } } - TentativeValues.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(LTerm) && isa(RTerm)) { + if (cast(LTerm)->isConditional()) return; + BasicBlock::iterator I = LTerm; + if (I == LStart->getParent()->begin()) return; + --I; + if (!isa(*I)) return; + CallInst *LCall = cast(&*I); + InvokeInst *RInvoke = cast(RTerm); + if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue())) + return; + if (!LCall->use_empty()) + Values[LCall] = RInvoke; + tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest()); + } else if (isa(LTerm) && isa(RTerm)) { + if (cast(RTerm)->isConditional()) return; + BasicBlock::iterator I = RTerm; + if (I == RStart->getParent()->begin()) return; + --I; + if (!isa(*I)) return; + CallInst *RCall = cast(I); + InvokeInst *LInvoke = cast(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);