diff options
Diffstat (limited to 'contrib/llvm/tools/llvm-diff')
| -rw-r--r-- | contrib/llvm/tools/llvm-diff/CMakeLists.txt | 6 | ||||
| -rw-r--r-- | contrib/llvm/tools/llvm-diff/DifferenceEngine.cpp | 676 | ||||
| -rw-r--r-- | contrib/llvm/tools/llvm-diff/DifferenceEngine.h | 179 | ||||
| -rw-r--r-- | contrib/llvm/tools/llvm-diff/Makefile | 17 | ||||
| -rw-r--r-- | contrib/llvm/tools/llvm-diff/llvm-diff.cpp | 331 |
5 files changed, 0 insertions, 1209 deletions
diff --git a/contrib/llvm/tools/llvm-diff/CMakeLists.txt b/contrib/llvm/tools/llvm-diff/CMakeLists.txt deleted file mode 100644 index f6d65c9..0000000 --- a/contrib/llvm/tools/llvm-diff/CMakeLists.txt +++ /dev/null @@ -1,6 +0,0 @@ -set(LLVM_LINK_COMPONENTS support asmparser bitreader) - -add_llvm_tool(llvm-diff - llvm-diff.cpp - DifferenceEngine.cpp - ) diff --git a/contrib/llvm/tools/llvm-diff/DifferenceEngine.cpp b/contrib/llvm/tools/llvm-diff/DifferenceEngine.cpp deleted file mode 100644 index b0a24d0..0000000 --- a/contrib/llvm/tools/llvm-diff/DifferenceEngine.cpp +++ /dev/null @@ -1,676 +0,0 @@ -//===-- DifferenceEngine.cpp - Structural function/module comparison ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This header defines the implementation of the LLVM difference -// engine, which structurally compares global values within a module. -// -//===----------------------------------------------------------------------===// - -#include "DifferenceEngine.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 <utility> - -using namespace llvm; - -namespace { - -/// A priority queue, implemented as a heap. -template <class T, class Sorter, unsigned InlineCapacity> -class PriorityQueue { - Sorter Precedes; - llvm::SmallVector<T, InlineCapacity> Storage; - -public: - PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {} - - /// Checks whether the heap is empty. - bool empty() const { return Storage.empty(); } - - /// Insert a new value on the heap. - void insert(const T &V) { - unsigned Index = Storage.size(); - Storage.push_back(V); - if (Index == 0) return; - - T *data = Storage.data(); - while (true) { - unsigned Target = (Index + 1) / 2 - 1; - if (!Precedes(data[Index], data[Target])) return; - std::swap(data[Index], data[Target]); - if (Target == 0) return; - Index = Target; - } - } - - /// Remove the minimum value in the heap. Only valid on a non-empty heap. - T remove_min() { - assert(!empty()); - T tmp = Storage[0]; - - unsigned NewSize = Storage.size() - 1; - if (NewSize) { - // Move the slot at the end to the beginning. - if (isPodLike<T>::value) - Storage[0] = Storage[NewSize]; - else - std::swap(Storage[0], Storage[NewSize]); - - // Bubble the root up as necessary. - unsigned Index = 0; - while (true) { - // With a 1-based index, the children would be Index*2 and Index*2+1. - unsigned R = (Index + 1) * 2; - unsigned L = R - 1; - - // If R is out of bounds, we're done after this in any case. - if (R >= NewSize) { - // If L is also out of bounds, we're done immediately. - if (L >= NewSize) break; - - // Otherwise, test whether we should swap L and Index. - if (Precedes(Storage[L], Storage[Index])) - std::swap(Storage[L], Storage[Index]); - break; - } - - // Otherwise, we need to compare with the smaller of L and R. - // Prefer R because it's closer to the end of the array. - unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R); - - // If Index is >= the min of L and R, then heap ordering is restored. - if (!Precedes(Storage[IndexToTest], Storage[Index])) - break; - - // Otherwise, keep bubbling up. - std::swap(Storage[IndexToTest], Storage[Index]); - Index = IndexToTest; - } - } - Storage.pop_back(); - - return tmp; - } -}; - -/// A function-scope difference engine. -class FunctionDifferenceEngine { - DifferenceEngine &Engine; - - /// The current mapping from old local values to new local values. - DenseMap<Value*, Value*> Values; - - /// The current mapping from old blocks to new blocks. - DenseMap<BasicBlock*, BasicBlock*> Blocks; - - DenseSet<std::pair<Value*, Value*> > TentativeValues; - - unsigned getUnprocPredCount(BasicBlock *Block) const { - unsigned Count = 0; - for (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; - - /// A type which sorts a priority queue by the number of unprocessed - /// predecessor blocks it has remaining. - /// - /// This is actually really expensive to calculate. - struct QueueSorter { - const FunctionDifferenceEngine &fde; - explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {} - - bool operator()(const BlockPair &Old, const BlockPair &New) { - return fde.getUnprocPredCount(Old.first) - < fde.getUnprocPredCount(New.first); - } - }; - - /// A queue of unified blocks to process. - PriorityQueue<BlockPair, QueueSorter, 20> Queue; - - /// Try to unify the given two blocks. Enqueues them for processing - /// 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]; - - if (Ref) { - if (Ref == R) return false; - - Engine.logf("successor %l cannot be equivalent to %r; " - "it's already equivalent to %r") - << L << R << Ref; - return true; - } - - Ref = R; - 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()) { - BlockPair Pair = Queue.remove_min(); - diff(Pair.first, Pair.second); - } - } - - void diff(BasicBlock *L, BasicBlock *R) { - DifferenceEngine::Context C(Engine, L, R); - - BasicBlock::iterator LI = L->begin(), LE = L->end(); - BasicBlock::iterator RI = R->begin(), RE = R->end(); - - llvm::SmallVector<std::pair<Instruction*,Instruction*>, 20> TentativePairs; - - do { - assert(LI != LE && RI != RE); - Instruction *LeftI = &*LI, *RightI = &*RI; - - // If the instructions differ, start the more sophisticated diff - // algorithm at the start of the block. - if (diff(LeftI, RightI, false, false)) { - TentativeValues.clear(); - return runBlockDiff(L->begin(), R->begin()); - } - - // Otherwise, tentatively unify them. - if (!LeftI->use_empty()) - 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); - void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI); - - bool diffCallSites(CallSite L, CallSite R, bool Complain) { - // FIXME: call attributes - if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) { - if (Complain) Engine.log("called functions differ"); - return true; - } - if (L.arg_size() != R.arg_size()) { - if (Complain) Engine.log("argument counts differ"); - return true; - } - for (unsigned I = 0, E = L.arg_size(); I != E; ++I) - if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) { - if (Complain) - Engine.logf("arguments %l and %r differ") - << L.getArgument(I) << R.getArgument(I); - return true; - } - return false; - } - - bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) { - // FIXME: metadata (if Complain is set) - - // Different opcodes always imply different operations. - if (L->getOpcode() != R->getOpcode()) { - if (Complain) Engine.log("different instruction types"); - return true; - } - - if (isa<CmpInst>(L)) { - if (cast<CmpInst>(L)->getPredicate() - != cast<CmpInst>(R)->getPredicate()) { - if (Complain) Engine.log("different predicates"); - return true; - } - } else if (isa<CallInst>(L)) { - return diffCallSites(CallSite(L), CallSite(R), Complain); - } else if (isa<PHINode>(L)) { - // FIXME: implement. - - // This is really wierd; type uniquing is broken? - if (L->getType() != R->getType()) { - if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) { - if (Complain) Engine.log("different phi types"); - return true; - } - } - return false; - - // Terminators. - } else if (isa<InvokeInst>(L)) { - InvokeInst *LI = cast<InvokeInst>(L); - InvokeInst *RI = cast<InvokeInst>(R); - if (diffCallSites(CallSite(LI), CallSite(RI), Complain)) - return true; - - if (TryUnify) { - tryUnify(LI->getNormalDest(), RI->getNormalDest()); - tryUnify(LI->getUnwindDest(), RI->getUnwindDest()); - } - return false; - - } else if (isa<BranchInst>(L)) { - BranchInst *LI = cast<BranchInst>(L); - BranchInst *RI = cast<BranchInst>(R); - if (LI->isConditional() != RI->isConditional()) { - if (Complain) Engine.log("branch conditionality differs"); - return true; - } - - if (LI->isConditional()) { - if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { - if (Complain) Engine.log("branch conditions differ"); - return true; - } - if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1)); - } - if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0)); - return false; - - } else if (isa<SwitchInst>(L)) { - SwitchInst *LI = cast<SwitchInst>(L); - SwitchInst *RI = cast<SwitchInst>(R); - if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { - if (Complain) Engine.log("switch conditions differ"); - return true; - } - if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest()); - - 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); - BasicBlock *LCase = LCases[CaseValue]; - if (LCase) { - if (TryUnify) tryUnify(LCase, RI->getSuccessor(I)); - LCases.erase(CaseValue); - } else if (!Difference) { - if (Complain) - Engine.logf("right switch has extra case %r") << CaseValue; - Difference = true; - } - } - if (!Difference) - for (DenseMap<ConstantInt*,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; - } - return Difference; - } else if (isa<UnreachableInst>(L)) { - return false; - } - - if (L->getNumOperands() != R->getNumOperands()) { - if (Complain) Engine.log("instructions have different operand counts"); - return true; - } - - 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 %l and %r differ") << LO << RO; - return true; - } - } - - return false; - } - - bool equivalentAsOperands(Constant *L, 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), - cast<GlobalValue>(R)); - - // Compare constant expressions structurally. - if (isa<ConstantExpr>(L)) - return equivalentAsOperands(cast<ConstantExpr>(L), - cast<ConstantExpr>(R)); - - // Nulls of the "same type" don't always actually have the same - // type; I don't know why. Just white-list them. - if (isa<ConstantPointerNull>(L)) - return true; - - // Block addresses only match if we've already encountered the - // block. FIXME: tentative matches? - if (isa<BlockAddress>(L)) - return Blocks[cast<BlockAddress>(L)->getBasicBlock()] - == cast<BlockAddress>(R)->getBasicBlock(); - - return false; - } - - bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) { - if (L == R) - return true; - if (L->getOpcode() != R->getOpcode()) - return false; - - switch (L->getOpcode()) { - case Instruction::ICmp: - case Instruction::FCmp: - if (L->getPredicate() != R->getPredicate()) - return false; - break; - - case Instruction::GetElementPtr: - // FIXME: inbounds? - break; - - default: - break; - } - - 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))) - return false; - - return true; - } - - bool equivalentAsOperands(Value *L, Value *R) { - // Fall out if the values have different kind. - // This possibly shouldn't take priority over oracles. - if (L->getValueID() != R->getValueID()) - return false; - - // Value subtypes: Argument, Constant, Instruction, BasicBlock, - // InlineAsm, MDNode, MDString, PseudoSourceValue - - if (isa<Constant>(L)) - return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R)); - - if (isa<Instruction>(L)) - return Values[L] == R || TentativeValues.count(std::make_pair(L, R)); - - if (isa<Argument>(L)) - return Values[L] == R; - - if (isa<BasicBlock>(L)) - return Blocks[cast<BasicBlock>(L)] != R; - - // Pretend everything else is identical. - return true; - } - - // Avoid a gcc warning about accessing 'this' in an initializer. - FunctionDifferenceEngine *this_() { return this; } - -public: - FunctionDifferenceEngine(DifferenceEngine &Engine) : - Engine(Engine), Queue(QueueSorter(*this_())) {} - - void diff(Function *L, 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(); - LI != LE && RI != RE; ++LI, ++RI) - Values[&*LI] = &*RI; - - tryUnify(&*L->begin(), &*R->begin()); - processQueue(); - } -}; - -struct DiffEntry { - DiffEntry() : Cost(0) {} - - unsigned Cost; - llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange -}; - -bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L, - 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(); - - unsigned NL = std::distance(LStart, LE); - - SmallVector<DiffEntry, 20> Paths1(NL+1); - SmallVector<DiffEntry, 20> Paths2(NL+1); - - DiffEntry *Cur = Paths1.data(); - DiffEntry *Next = Paths2.data(); - - 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 * LeftCost; - for (unsigned J = 0; J != I; ++J) - Cur[I].Path.push_back(DifferenceEngine::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); - - 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); - 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); - } else { - Next[Index] = Cur[Index]; - Next[Index].Cost += RightCost; - Next[Index].Path.push_back(DifferenceEngine::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); - - // Drop trailing matches. - while (Path.back() == DifferenceEngine::DC_match) - Path.pop_back(); - - // Skip leading matches. - SmallVectorImpl<char>::iterator - PI = Path.begin(), PE = Path.end(); - while (PI != PE && *PI == DifferenceEngine::DC_match) { - unify(&*LI, &*RI); - ++PI, ++LI, ++RI; - } - - for (; PI != PE; ++PI) { - switch (static_cast<DifferenceEngine::DiffChange>(*PI)) { - case DifferenceEngine::DC_match: - assert(LI != LE && RI != RE); - { - Instruction *L = &*LI, *R = &*RI; - unify(L, R); - Diff.addMatch(L, R); - } - ++LI; ++RI; - break; - - case DifferenceEngine::DC_left: - assert(LI != LE); - Diff.addLeft(&*LI); - ++LI; - break; - - case DifferenceEngine::DC_right: - assert(RI != RE); - Diff.addRight(&*RI); - ++RI; - break; - } - } - - // 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; - 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; - 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::diff(Function *L, Function *R) { - Context C(*this, L, R); - - // FIXME: types - // FIXME: attributes and CC - // FIXME: parameter attributes - - // If both are declarations, we're done. - if (L->empty() && R->empty()) - return; - else if (L->empty()) - log("left function is declaration, right function is definition"); - else if (R->empty()) - log("right function is declaration, left function is definition"); - else - FunctionDifferenceEngine(*this).diff(L, R); -} - -void DifferenceEngine::diff(Module *L, Module *R) { - StringSet<> LNames; - SmallVector<std::pair<Function*,Function*>, 20> Queue; - - for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) { - Function *LFn = &*I; - LNames.insert(LFn->getName()); - - if (Function *RFn = R->getFunction(LFn->getName())) - Queue.push_back(std::make_pair(LFn, RFn)); - else - 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 %r exists only in right module") << RFn; - } - - for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator - I = Queue.begin(), E = Queue.end(); I != E; ++I) - diff(I->first, I->second); -} - -bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) { - if (globalValueOracle) return (*globalValueOracle)(L, R); - return L->getName() == R->getName(); -} diff --git a/contrib/llvm/tools/llvm-diff/DifferenceEngine.h b/contrib/llvm/tools/llvm-diff/DifferenceEngine.h deleted file mode 100644 index 6eefb06..0000000 --- a/contrib/llvm/tools/llvm-diff/DifferenceEngine.h +++ /dev/null @@ -1,179 +0,0 @@ -//===-- DifferenceEngine.h - Module comparator ------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This header defines the interface to the LLVM difference engine, -// which structurally compares functions within a module. -// -//===----------------------------------------------------------------------===// - -#ifndef _LLVM_DIFFERENCE_ENGINE_H_ -#define _LLVM_DIFFERENCE_ENGINE_H_ - -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" - -#include <utility> - -namespace llvm { - class Function; - class GlobalValue; - class Instruction; - class LLVMContext; - class Module; - class Twine; - class Value; - - /// A class for performing structural comparisons of LLVM assembly. - class DifferenceEngine { - public: - /// A temporary-object class for building up log messages. - class LogBuilder { - DifferenceEngine &Engine; - - /// The use of a stored StringRef here is okay because - /// LogBuilder should be used only as a temporary, and as a - /// temporary it will be destructed before whatever temporary - /// might be initializing this format. - StringRef Format; - - SmallVector<Value*, 4> Arguments; - - public: - LogBuilder(DifferenceEngine &Engine, StringRef Format) - : Engine(Engine), Format(Format) {} - - LogBuilder &operator<<(Value *V) { - Arguments.push_back(V); - return *this; - } - - ~LogBuilder() { - Engine.consumer.logf(*this); - } - - StringRef getFormat() const { return Format; } - - unsigned getNumArguments() const { return Arguments.size(); } - Value *getArgument(unsigned I) const { return Arguments[I]; } - }; - - enum DiffChange { DC_match, DC_left, DC_right }; - - /// A temporary-object class for building up diff messages. - class DiffLogBuilder { - typedef std::pair<Instruction*,Instruction*> DiffRecord; - SmallVector<DiffRecord, 20> Diff; - - DifferenceEngine &Engine; - - public: - DiffLogBuilder(DifferenceEngine &Engine) : Engine(Engine) {} - ~DiffLogBuilder() { Engine.consumer.logd(*this); } - - void addMatch(Instruction *L, Instruction *R) { - Diff.push_back(DiffRecord(L, R)); - } - void addLeft(Instruction *L) { - // HACK: VS 2010 has a bug in the stdlib that requires this. - Diff.push_back(DiffRecord(L, DiffRecord::second_type(0))); - } - void addRight(Instruction *R) { - // HACK: VS 2010 has a bug in the stdlib that requires this. - Diff.push_back(DiffRecord(DiffRecord::first_type(0), R)); - } - - unsigned getNumLines() const { return Diff.size(); } - DiffChange getLineKind(unsigned I) const { - return (Diff[I].first ? (Diff[I].second ? DC_match : DC_left) - : DC_right); - } - Instruction *getLeft(unsigned I) const { return Diff[I].first; } - Instruction *getRight(unsigned I) const { return Diff[I].second; } - }; - - /// The interface for consumers of difference data. - struct Consumer { - /// Record that a local context has been entered. Left and - /// Right are IR "containers" of some sort which are being - /// considered for structural equivalence: global variables, - /// functions, blocks, instructions, etc. - virtual void enterContext(Value *Left, Value *Right) = 0; - - /// Record that a local context has been exited. - virtual void exitContext() = 0; - - /// Record a difference within the current context. - virtual void log(StringRef Text) = 0; - - /// Record a formatted difference within the current context. - virtual void logf(const LogBuilder &Log) = 0; - - /// Record a line-by-line instruction diff. - virtual void logd(const DiffLogBuilder &Log) = 0; - - protected: - virtual ~Consumer() {} - }; - - /// A RAII object for recording the current context. - struct Context { - Context(DifferenceEngine &Engine, Value *L, Value *R) : Engine(Engine) { - Engine.consumer.enterContext(L, R); - } - - ~Context() { - Engine.consumer.exitContext(); - } - - private: - DifferenceEngine &Engine; - }; - - /// An oracle for answering whether two values are equivalent as - /// operands. - struct Oracle { - virtual bool operator()(Value *L, Value *R) = 0; - - protected: - virtual ~Oracle() {} - }; - - DifferenceEngine(LLVMContext &context, Consumer &consumer) - : context(context), consumer(consumer), globalValueOracle(0) {} - - void diff(Module *L, Module *R); - void diff(Function *L, Function *R); - - void log(StringRef text) { - consumer.log(text); - } - - LogBuilder logf(StringRef text) { - return LogBuilder(*this, text); - } - - /// Installs an oracle to decide whether two global values are - /// equivalent as operands. Without an oracle, global values are - /// considered equivalent as operands precisely when they have the - /// same name. - void setGlobalValueOracle(Oracle *oracle) { - globalValueOracle = oracle; - } - - /// Determines whether two global values are equivalent. - bool equivalentAsOperands(GlobalValue *L, GlobalValue *R); - - private: - LLVMContext &context; - Consumer &consumer; - Oracle *globalValueOracle; - }; -} - -#endif diff --git a/contrib/llvm/tools/llvm-diff/Makefile b/contrib/llvm/tools/llvm-diff/Makefile deleted file mode 100644 index 58e49fa..0000000 --- a/contrib/llvm/tools/llvm-diff/Makefile +++ /dev/null @@ -1,17 +0,0 @@ -##===- tools/llvm-diff/Makefile ----------------------------*- Makefile -*-===## -# -# The LLVM Compiler Infrastructure -# -# This file is distributed under the University of Illinois Open Source -# License. See LICENSE.TXT for details. -# -##===----------------------------------------------------------------------===## - -LEVEL = ../.. -TOOLNAME = llvm-diff -LINK_COMPONENTS := asmparser bitreader - -# This tool has no plugins, optimize startup time. -TOOL_NO_EXPORTS = 1 - -include $(LEVEL)/Makefile.common diff --git a/contrib/llvm/tools/llvm-diff/llvm-diff.cpp b/contrib/llvm/tools/llvm-diff/llvm-diff.cpp deleted file mode 100644 index 16a990f..0000000 --- a/contrib/llvm/tools/llvm-diff/llvm-diff.cpp +++ /dev/null @@ -1,331 +0,0 @@ -//===-- llvm-diff.cpp - Module comparator command-line driver ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the command-line driver for the difference engine. -// -//===----------------------------------------------------------------------===// - -#include "DifferenceEngine.h" - -#include "llvm/Instructions.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/Type.h" -#include "llvm/Assembly/Parser.h" -#include "llvm/Bitcode/ReaderWriter.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/SourceMgr.h" - -#include <string> -#include <utility> - - -using namespace llvm; - -/// Reads a module from a file. If the filename ends in .ll, it is -/// interpreted as an assembly file; otherwise, it is interpreted as -/// bitcode. On error, messages are written to stderr and null is -/// returned. -static Module *ReadModule(LLVMContext &Context, StringRef Name) { - // LLVM assembly path. - if (Name.endswith(".ll")) { - SMDiagnostic Diag; - Module *M = ParseAssemblyFile(Name, Diag, Context); - if (M) return M; - - Diag.Print("llvmdiff", errs()); - return 0; - } - - // Bitcode path. - MemoryBuffer *Buffer = MemoryBuffer::getFile(Name); - - // ParseBitcodeFile takes ownership of the buffer if it succeeds. - std::string Error; - Module *M = ParseBitcodeFile(Buffer, Context, &Error); - if (M) return M; - - errs() << "error parsing " << Name << ": " << Error; - delete Buffer; - return 0; -} - -namespace { -struct DiffContext { - DiffContext(Value *L, Value *R) - : L(L), R(R), Differences(false), IsFunction(isa<Function>(L)) {} - Value *L; - Value *R; - bool Differences; - bool IsFunction; - DenseMap<Value*,unsigned> LNumbering; - DenseMap<Value*,unsigned> RNumbering; -}; - -void ComputeNumbering(Function *F, DenseMap<Value*,unsigned> &Numbering) { - unsigned IN = 0; - - // Arguments get the first numbers. - for (Function::arg_iterator - AI = F->arg_begin(), AE = F->arg_end(); AI != AE; ++AI) - if (!AI->hasName()) - Numbering[&*AI] = IN++; - - // Walk the basic blocks in order. - for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI) { - if (!FI->hasName()) - Numbering[&*FI] = IN++; - - // Walk the instructions in order. - for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) - // void instructions don't get numbers. - if (!BI->hasName() && !BI->getType()->isVoidTy()) - Numbering[&*BI] = IN++; - } - - assert(!Numbering.empty() && "asked for numbering but numbering was no-op"); -} - -class DiffConsumer : public DifferenceEngine::Consumer { -private: - raw_ostream &out; - Module *LModule; - Module *RModule; - SmallVector<DiffContext, 5> contexts; - bool Differences; - unsigned Indent; - - void printValue(Value *V, bool isL) { - if (V->hasName()) { - out << (isa<GlobalValue>(V) ? '@' : '%') << V->getName(); - return; - } - if (V->getType()->isVoidTy()) { - if (isa<StoreInst>(V)) { - out << "store to "; - printValue(cast<StoreInst>(V)->getPointerOperand(), isL); - } else if (isa<CallInst>(V)) { - out << "call to "; - printValue(cast<CallInst>(V)->getCalledValue(), isL); - } else if (isa<InvokeInst>(V)) { - out << "invoke to "; - printValue(cast<InvokeInst>(V)->getCalledValue(), isL); - } else { - out << *V; - } - return; - } - - unsigned N = contexts.size(); - while (N > 0) { - --N; - DiffContext &ctxt = contexts[N]; - if (!ctxt.IsFunction) continue; - if (isL) { - if (ctxt.LNumbering.empty()) - ComputeNumbering(cast<Function>(ctxt.L), ctxt.LNumbering); - out << '%' << ctxt.LNumbering[V]; - return; - } else { - if (ctxt.RNumbering.empty()) - ComputeNumbering(cast<Function>(ctxt.R), ctxt.RNumbering); - out << '%' << ctxt.RNumbering[V]; - return; - } - } - - out << "<anonymous>"; - } - - void header() { - if (contexts.empty()) return; - for (SmallVectorImpl<DiffContext>::iterator - I = contexts.begin(), E = contexts.end(); I != E; ++I) { - if (I->Differences) continue; - if (isa<Function>(I->L)) { - // Extra newline between functions. - if (Differences) out << "\n"; - - Function *L = cast<Function>(I->L); - Function *R = cast<Function>(I->R); - if (L->getName() != R->getName()) - out << "in function " << L->getName() - << " / " << R->getName() << ":\n"; - else - out << "in function " << L->getName() << ":\n"; - } else if (isa<BasicBlock>(I->L)) { - BasicBlock *L = cast<BasicBlock>(I->L); - BasicBlock *R = cast<BasicBlock>(I->R); - if (L->hasName() && R->hasName() && L->getName() == R->getName()) - out << " in block %" << L->getName() << ":\n"; - else { - out << " in block "; - printValue(L, true); - out << " / "; - printValue(R, false); - out << ":\n"; - } - } else if (isa<Instruction>(I->L)) { - out << " in instruction "; - printValue(I->L, true); - out << " / "; - printValue(I->R, false); - out << ":\n"; - } - - I->Differences = true; - } - } - - void indent() { - unsigned N = Indent; - while (N--) out << ' '; - } - -public: - DiffConsumer(Module *L, Module *R) - : out(errs()), LModule(L), RModule(R), Differences(false), Indent(0) {} - - bool hadDifferences() const { return Differences; } - - void enterContext(Value *L, Value *R) { - contexts.push_back(DiffContext(L, R)); - Indent += 2; - } - void exitContext() { - Differences |= contexts.back().Differences; - contexts.pop_back(); - Indent -= 2; - } - - void log(StringRef text) { - header(); - indent(); - out << text << '\n'; - } - - void logf(const DifferenceEngine::LogBuilder &Log) { - header(); - indent(); - - unsigned arg = 0; - - StringRef format = Log.getFormat(); - while (true) { - size_t percent = format.find('%'); - if (percent == StringRef::npos) { - out << format; - break; - } - assert(format[percent] == '%'); - - if (percent > 0) out << format.substr(0, percent); - - switch (format[percent+1]) { - case '%': out << '%'; break; - case 'l': printValue(Log.getArgument(arg++), true); break; - case 'r': printValue(Log.getArgument(arg++), false); break; - default: llvm_unreachable("unknown format character"); - } - - format = format.substr(percent+2); - } - - out << '\n'; - } - - void logd(const DifferenceEngine::DiffLogBuilder &Log) { - header(); - - for (unsigned I = 0, E = Log.getNumLines(); I != E; ++I) { - indent(); - switch (Log.getLineKind(I)) { - case DifferenceEngine::DC_match: - out << " "; - Log.getLeft(I)->dump(); - //printValue(Log.getLeft(I), true); - break; - case DifferenceEngine::DC_left: - out << "< "; - Log.getLeft(I)->dump(); - //printValue(Log.getLeft(I), true); - break; - case DifferenceEngine::DC_right: - out << "> "; - Log.getRight(I)->dump(); - //printValue(Log.getRight(I), false); - break; - } - //out << "\n"; - } - } - -}; -} - -static void diffGlobal(DifferenceEngine &Engine, Module *L, Module *R, - StringRef Name) { - // Drop leading sigils from the global name. - if (Name.startswith("@")) Name = Name.substr(1); - - Function *LFn = L->getFunction(Name); - Function *RFn = R->getFunction(Name); - if (LFn && RFn) - Engine.diff(LFn, RFn); - else if (!LFn && !RFn) - errs() << "No function named @" << Name << " in either module\n"; - else if (!LFn) - errs() << "No function named @" << Name << " in left module\n"; - else - errs() << "No function named @" << Name << " in right module\n"; -} - -cl::opt<std::string> LeftFilename(cl::Positional, - cl::desc("<first file>"), - cl::Required); -cl::opt<std::string> RightFilename(cl::Positional, - cl::desc("<second file>"), - cl::Required); -cl::list<std::string> GlobalsToCompare(cl::Positional, - cl::desc("<globals to compare>")); - -int main(int argc, char **argv) { - cl::ParseCommandLineOptions(argc, argv); - - LLVMContext Context; - - // Load both modules. Die if that fails. - Module *LModule = ReadModule(Context, LeftFilename); - Module *RModule = ReadModule(Context, RightFilename); - if (!LModule || !RModule) return 1; - - DiffConsumer Consumer(LModule, RModule); - DifferenceEngine Engine(Context, Consumer); - - // If any global names were given, just diff those. - if (!GlobalsToCompare.empty()) { - for (unsigned I = 0, E = GlobalsToCompare.size(); I != E; ++I) - diffGlobal(Engine, LModule, RModule, GlobalsToCompare[I]); - - // Otherwise, diff everything in the module. - } else { - Engine.diff(LModule, RModule); - } - - delete LModule; - delete RModule; - - return Consumer.hadDifferences(); -} |
