13dd706b5288b83967968287c0950480948e8c3f6John McCall//===-- DifferenceEngine.cpp - Structural function/module comparison ------===// 23dd706b5288b83967968287c0950480948e8c3f6John McCall// 33dd706b5288b83967968287c0950480948e8c3f6John McCall// The LLVM Compiler Infrastructure 43dd706b5288b83967968287c0950480948e8c3f6John McCall// 53dd706b5288b83967968287c0950480948e8c3f6John McCall// This file is distributed under the University of Illinois Open Source 63dd706b5288b83967968287c0950480948e8c3f6John McCall// License. See LICENSE.TXT for details. 73dd706b5288b83967968287c0950480948e8c3f6John McCall// 83dd706b5288b83967968287c0950480948e8c3f6John McCall//===----------------------------------------------------------------------===// 93dd706b5288b83967968287c0950480948e8c3f6John McCall// 1073b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall// This header defines the implementation of the LLVM difference 1173b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall// engine, which structurally compares global values within a module. 123dd706b5288b83967968287c0950480948e8c3f6John McCall// 133dd706b5288b83967968287c0950480948e8c3f6John McCall//===----------------------------------------------------------------------===// 143dd706b5288b83967968287c0950480948e8c3f6John McCall 1573b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "DifferenceEngine.h" 1673b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/ADT/DenseMap.h" 1773b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/ADT/DenseSet.h" 1873b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/ADT/SmallVector.h" 1973b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/ADT/StringRef.h" 2073b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/ADT/StringSet.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 2573b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/Support/CFG.h" 26f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Support/CallSite.h" 2773b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/Support/ErrorHandling.h" 2873b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/Support/raw_ostream.h" 2973b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include "llvm/Support/type_traits.h" 3073b21b738ee74f33f16ca6bf88bd4344b3fca0a9John McCall#include <utility> 313dd706b5288b83967968287c0950480948e8c3f6John McCall 323dd706b5288b83967968287c0950480948e8c3f6John McCallusing namespace llvm; 333dd706b5288b83967968287c0950480948e8c3f6John McCall 343dd706b5288b83967968287c0950480948e8c3f6John McCallnamespace { 353dd706b5288b83967968287c0950480948e8c3f6John McCall 363dd706b5288b83967968287c0950480948e8c3f6John McCall/// A priority queue, implemented as a heap. 373dd706b5288b83967968287c0950480948e8c3f6John McCalltemplate <class T, class Sorter, unsigned InlineCapacity> 383dd706b5288b83967968287c0950480948e8c3f6John McCallclass PriorityQueue { 393dd706b5288b83967968287c0950480948e8c3f6John McCall Sorter Precedes; 403dd706b5288b83967968287c0950480948e8c3f6John McCall llvm::SmallVector<T, InlineCapacity> Storage; 413dd706b5288b83967968287c0950480948e8c3f6John McCall 423dd706b5288b83967968287c0950480948e8c3f6John McCallpublic: 433dd706b5288b83967968287c0950480948e8c3f6John McCall PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {} 443dd706b5288b83967968287c0950480948e8c3f6John McCall 453dd706b5288b83967968287c0950480948e8c3f6John McCall /// Checks whether the heap is empty. 463dd706b5288b83967968287c0950480948e8c3f6John McCall bool empty() const { return Storage.empty(); } 473dd706b5288b83967968287c0950480948e8c3f6John McCall 483dd706b5288b83967968287c0950480948e8c3f6John McCall /// Insert a new value on the heap. 493dd706b5288b83967968287c0950480948e8c3f6John McCall void insert(const T &V) { 503dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Index = Storage.size(); 513dd706b5288b83967968287c0950480948e8c3f6John McCall Storage.push_back(V); 523dd706b5288b83967968287c0950480948e8c3f6John McCall if (Index == 0) return; 533dd706b5288b83967968287c0950480948e8c3f6John McCall 543dd706b5288b83967968287c0950480948e8c3f6John McCall T *data = Storage.data(); 553dd706b5288b83967968287c0950480948e8c3f6John McCall while (true) { 563dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Target = (Index + 1) / 2 - 1; 573dd706b5288b83967968287c0950480948e8c3f6John McCall if (!Precedes(data[Index], data[Target])) return; 583dd706b5288b83967968287c0950480948e8c3f6John McCall std::swap(data[Index], data[Target]); 593dd706b5288b83967968287c0950480948e8c3f6John McCall if (Target == 0) return; 603dd706b5288b83967968287c0950480948e8c3f6John McCall Index = Target; 613dd706b5288b83967968287c0950480948e8c3f6John McCall } 623dd706b5288b83967968287c0950480948e8c3f6John McCall } 633dd706b5288b83967968287c0950480948e8c3f6John McCall 643dd706b5288b83967968287c0950480948e8c3f6John McCall /// Remove the minimum value in the heap. Only valid on a non-empty heap. 653dd706b5288b83967968287c0950480948e8c3f6John McCall T remove_min() { 663dd706b5288b83967968287c0950480948e8c3f6John McCall assert(!empty()); 673dd706b5288b83967968287c0950480948e8c3f6John McCall T tmp = Storage[0]; 683dd706b5288b83967968287c0950480948e8c3f6John McCall 693dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned NewSize = Storage.size() - 1; 703dd706b5288b83967968287c0950480948e8c3f6John McCall if (NewSize) { 713dd706b5288b83967968287c0950480948e8c3f6John McCall // Move the slot at the end to the beginning. 723dd706b5288b83967968287c0950480948e8c3f6John McCall if (isPodLike<T>::value) 733dd706b5288b83967968287c0950480948e8c3f6John McCall Storage[0] = Storage[NewSize]; 743dd706b5288b83967968287c0950480948e8c3f6John McCall else 753dd706b5288b83967968287c0950480948e8c3f6John McCall std::swap(Storage[0], Storage[NewSize]); 763dd706b5288b83967968287c0950480948e8c3f6John McCall 773dd706b5288b83967968287c0950480948e8c3f6John McCall // Bubble the root up as necessary. 783dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Index = 0; 793dd706b5288b83967968287c0950480948e8c3f6John McCall while (true) { 803dd706b5288b83967968287c0950480948e8c3f6John McCall // With a 1-based index, the children would be Index*2 and Index*2+1. 813dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned R = (Index + 1) * 2; 823dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned L = R - 1; 833dd706b5288b83967968287c0950480948e8c3f6John McCall 843dd706b5288b83967968287c0950480948e8c3f6John McCall // If R is out of bounds, we're done after this in any case. 853dd706b5288b83967968287c0950480948e8c3f6John McCall if (R >= NewSize) { 863dd706b5288b83967968287c0950480948e8c3f6John McCall // If L is also out of bounds, we're done immediately. 873dd706b5288b83967968287c0950480948e8c3f6John McCall if (L >= NewSize) break; 883dd706b5288b83967968287c0950480948e8c3f6John McCall 893dd706b5288b83967968287c0950480948e8c3f6John McCall // Otherwise, test whether we should swap L and Index. 903dd706b5288b83967968287c0950480948e8c3f6John McCall if (Precedes(Storage[L], Storage[Index])) 913dd706b5288b83967968287c0950480948e8c3f6John McCall std::swap(Storage[L], Storage[Index]); 923dd706b5288b83967968287c0950480948e8c3f6John McCall break; 933dd706b5288b83967968287c0950480948e8c3f6John McCall } 943dd706b5288b83967968287c0950480948e8c3f6John McCall 953dd706b5288b83967968287c0950480948e8c3f6John McCall // Otherwise, we need to compare with the smaller of L and R. 963dd706b5288b83967968287c0950480948e8c3f6John McCall // Prefer R because it's closer to the end of the array. 973dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R); 983dd706b5288b83967968287c0950480948e8c3f6John McCall 993dd706b5288b83967968287c0950480948e8c3f6John McCall // If Index is >= the min of L and R, then heap ordering is restored. 1003dd706b5288b83967968287c0950480948e8c3f6John McCall if (!Precedes(Storage[IndexToTest], Storage[Index])) 1013dd706b5288b83967968287c0950480948e8c3f6John McCall break; 1023dd706b5288b83967968287c0950480948e8c3f6John McCall 1033dd706b5288b83967968287c0950480948e8c3f6John McCall // Otherwise, keep bubbling up. 1043dd706b5288b83967968287c0950480948e8c3f6John McCall std::swap(Storage[IndexToTest], Storage[Index]); 1053dd706b5288b83967968287c0950480948e8c3f6John McCall Index = IndexToTest; 1063dd706b5288b83967968287c0950480948e8c3f6John McCall } 1073dd706b5288b83967968287c0950480948e8c3f6John McCall } 1083dd706b5288b83967968287c0950480948e8c3f6John McCall Storage.pop_back(); 1093dd706b5288b83967968287c0950480948e8c3f6John McCall 1103dd706b5288b83967968287c0950480948e8c3f6John McCall return tmp; 1113dd706b5288b83967968287c0950480948e8c3f6John McCall } 1123dd706b5288b83967968287c0950480948e8c3f6John McCall}; 1133dd706b5288b83967968287c0950480948e8c3f6John McCall 1143dd706b5288b83967968287c0950480948e8c3f6John McCall/// A function-scope difference engine. 1153dd706b5288b83967968287c0950480948e8c3f6John McCallclass FunctionDifferenceEngine { 1163dd706b5288b83967968287c0950480948e8c3f6John McCall DifferenceEngine &Engine; 1173dd706b5288b83967968287c0950480948e8c3f6John McCall 1183dd706b5288b83967968287c0950480948e8c3f6John McCall /// The current mapping from old local values to new local values. 1193dd706b5288b83967968287c0950480948e8c3f6John McCall DenseMap<Value*, Value*> Values; 1203dd706b5288b83967968287c0950480948e8c3f6John McCall 1213dd706b5288b83967968287c0950480948e8c3f6John McCall /// The current mapping from old blocks to new blocks. 1223dd706b5288b83967968287c0950480948e8c3f6John McCall DenseMap<BasicBlock*, BasicBlock*> Blocks; 1233dd706b5288b83967968287c0950480948e8c3f6John McCall 124dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall DenseSet<std::pair<Value*, Value*> > TentativeValues; 1253dd706b5288b83967968287c0950480948e8c3f6John McCall 1263dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned getUnprocPredCount(BasicBlock *Block) const { 1273dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Count = 0; 1283dd706b5288b83967968287c0950480948e8c3f6John McCall for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I) 1293dd706b5288b83967968287c0950480948e8c3f6John McCall if (!Blocks.count(*I)) Count++; 1303dd706b5288b83967968287c0950480948e8c3f6John McCall return Count; 1313dd706b5288b83967968287c0950480948e8c3f6John McCall } 1323dd706b5288b83967968287c0950480948e8c3f6John McCall 1333dd706b5288b83967968287c0950480948e8c3f6John McCall typedef std::pair<BasicBlock*, BasicBlock*> BlockPair; 1343dd706b5288b83967968287c0950480948e8c3f6John McCall 1353dd706b5288b83967968287c0950480948e8c3f6John McCall /// A type which sorts a priority queue by the number of unprocessed 1363dd706b5288b83967968287c0950480948e8c3f6John McCall /// predecessor blocks it has remaining. 1373dd706b5288b83967968287c0950480948e8c3f6John McCall /// 1383dd706b5288b83967968287c0950480948e8c3f6John McCall /// This is actually really expensive to calculate. 1393dd706b5288b83967968287c0950480948e8c3f6John McCall struct QueueSorter { 1403dd706b5288b83967968287c0950480948e8c3f6John McCall const FunctionDifferenceEngine &fde; 1413dd706b5288b83967968287c0950480948e8c3f6John McCall explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {} 1423dd706b5288b83967968287c0950480948e8c3f6John McCall 1433dd706b5288b83967968287c0950480948e8c3f6John McCall bool operator()(const BlockPair &Old, const BlockPair &New) { 1443dd706b5288b83967968287c0950480948e8c3f6John McCall return fde.getUnprocPredCount(Old.first) 1453dd706b5288b83967968287c0950480948e8c3f6John McCall < fde.getUnprocPredCount(New.first); 1463dd706b5288b83967968287c0950480948e8c3f6John McCall } 1473dd706b5288b83967968287c0950480948e8c3f6John McCall }; 1483dd706b5288b83967968287c0950480948e8c3f6John McCall 1493dd706b5288b83967968287c0950480948e8c3f6John McCall /// A queue of unified blocks to process. 1503dd706b5288b83967968287c0950480948e8c3f6John McCall PriorityQueue<BlockPair, QueueSorter, 20> Queue; 1513dd706b5288b83967968287c0950480948e8c3f6John McCall 1523dd706b5288b83967968287c0950480948e8c3f6John McCall /// Try to unify the given two blocks. Enqueues them for processing 1533dd706b5288b83967968287c0950480948e8c3f6John McCall /// if they haven't already been processed. 1543dd706b5288b83967968287c0950480948e8c3f6John McCall /// 1553dd706b5288b83967968287c0950480948e8c3f6John McCall /// Returns true if there was a problem unifying them. 1563dd706b5288b83967968287c0950480948e8c3f6John McCall bool tryUnify(BasicBlock *L, BasicBlock *R) { 1573dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock *&Ref = Blocks[L]; 1583dd706b5288b83967968287c0950480948e8c3f6John McCall 1593dd706b5288b83967968287c0950480948e8c3f6John McCall if (Ref) { 1603dd706b5288b83967968287c0950480948e8c3f6John McCall if (Ref == R) return false; 1613dd706b5288b83967968287c0950480948e8c3f6John McCall 16262dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall Engine.logf("successor %l cannot be equivalent to %r; " 16362dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall "it's already equivalent to %r") 1643dd706b5288b83967968287c0950480948e8c3f6John McCall << L << R << Ref; 1653dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 1663dd706b5288b83967968287c0950480948e8c3f6John McCall } 1673dd706b5288b83967968287c0950480948e8c3f6John McCall 1683dd706b5288b83967968287c0950480948e8c3f6John McCall Ref = R; 1693dd706b5288b83967968287c0950480948e8c3f6John McCall Queue.insert(BlockPair(L, R)); 1703dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 1713dd706b5288b83967968287c0950480948e8c3f6John McCall } 17282bd5eaa710b18893951e199fda4376e84b7ec34John McCall 17382bd5eaa710b18893951e199fda4376e84b7ec34John McCall /// Unifies two instructions, given that they're known not to have 17482bd5eaa710b18893951e199fda4376e84b7ec34John McCall /// structural differences. 17582bd5eaa710b18893951e199fda4376e84b7ec34John McCall void unify(Instruction *L, Instruction *R) { 17682bd5eaa710b18893951e199fda4376e84b7ec34John McCall DifferenceEngine::Context C(Engine, L, R); 17782bd5eaa710b18893951e199fda4376e84b7ec34John McCall 17882bd5eaa710b18893951e199fda4376e84b7ec34John McCall bool Result = diff(L, R, true, true); 17982bd5eaa710b18893951e199fda4376e84b7ec34John McCall assert(!Result && "structural differences second time around?"); 18082bd5eaa710b18893951e199fda4376e84b7ec34John McCall (void) Result; 18182bd5eaa710b18893951e199fda4376e84b7ec34John McCall if (!L->use_empty()) 18282bd5eaa710b18893951e199fda4376e84b7ec34John McCall Values[L] = R; 18382bd5eaa710b18893951e199fda4376e84b7ec34John McCall } 1843dd706b5288b83967968287c0950480948e8c3f6John McCall 1853dd706b5288b83967968287c0950480948e8c3f6John McCall void processQueue() { 1863dd706b5288b83967968287c0950480948e8c3f6John McCall while (!Queue.empty()) { 1873dd706b5288b83967968287c0950480948e8c3f6John McCall BlockPair Pair = Queue.remove_min(); 1883dd706b5288b83967968287c0950480948e8c3f6John McCall diff(Pair.first, Pair.second); 1893dd706b5288b83967968287c0950480948e8c3f6John McCall } 1903dd706b5288b83967968287c0950480948e8c3f6John McCall } 1913dd706b5288b83967968287c0950480948e8c3f6John McCall 1923dd706b5288b83967968287c0950480948e8c3f6John McCall void diff(BasicBlock *L, BasicBlock *R) { 1933dd706b5288b83967968287c0950480948e8c3f6John McCall DifferenceEngine::Context C(Engine, L, R); 1943dd706b5288b83967968287c0950480948e8c3f6John McCall 1953dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock::iterator LI = L->begin(), LE = L->end(); 1961f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands BasicBlock::iterator RI = R->begin(); 1973dd706b5288b83967968287c0950480948e8c3f6John McCall 198dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall llvm::SmallVector<std::pair<Instruction*,Instruction*>, 20> TentativePairs; 199dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall 2003dd706b5288b83967968287c0950480948e8c3f6John McCall do { 2011f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands assert(LI != LE && RI != R->end()); 2023dd706b5288b83967968287c0950480948e8c3f6John McCall Instruction *LeftI = &*LI, *RightI = &*RI; 2033dd706b5288b83967968287c0950480948e8c3f6John McCall 2043dd706b5288b83967968287c0950480948e8c3f6John McCall // If the instructions differ, start the more sophisticated diff 205dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall // algorithm at the start of the block. 206e2921432b6e0ba916ebfca312ae2cac7641279ecJohn McCall if (diff(LeftI, RightI, false, false)) { 207dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall TentativeValues.clear(); 208dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall return runBlockDiff(L->begin(), R->begin()); 209dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall } 2103dd706b5288b83967968287c0950480948e8c3f6John McCall 211dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall // Otherwise, tentatively unify them. 2123dd706b5288b83967968287c0950480948e8c3f6John McCall if (!LeftI->use_empty()) 213dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall TentativeValues.insert(std::make_pair(LeftI, RightI)); 2143dd706b5288b83967968287c0950480948e8c3f6John McCall 2153dd706b5288b83967968287c0950480948e8c3f6John McCall ++LI, ++RI; 2163dd706b5288b83967968287c0950480948e8c3f6John McCall } while (LI != LE); // This is sufficient: we can't get equality of 2173dd706b5288b83967968287c0950480948e8c3f6John McCall // terminators if there are residual instructions. 218dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall 21982bd5eaa710b18893951e199fda4376e84b7ec34John McCall // Unify everything in the block, non-tentatively this time. 220dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall TentativeValues.clear(); 22182bd5eaa710b18893951e199fda4376e84b7ec34John McCall for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI) 22282bd5eaa710b18893951e199fda4376e84b7ec34John McCall unify(&*LI, &*RI); 2233dd706b5288b83967968287c0950480948e8c3f6John McCall } 2243dd706b5288b83967968287c0950480948e8c3f6John McCall 2253dd706b5288b83967968287c0950480948e8c3f6John McCall bool matchForBlockDiff(Instruction *L, Instruction *R); 2263dd706b5288b83967968287c0950480948e8c3f6John McCall void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI); 2273dd706b5288b83967968287c0950480948e8c3f6John McCall 2283dd706b5288b83967968287c0950480948e8c3f6John McCall bool diffCallSites(CallSite L, CallSite R, bool Complain) { 2293dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: call attributes 2303dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) { 2313dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("called functions differ"); 2323dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2333dd706b5288b83967968287c0950480948e8c3f6John McCall } 2343dd706b5288b83967968287c0950480948e8c3f6John McCall if (L.arg_size() != R.arg_size()) { 2353dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("argument counts differ"); 2363dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2373dd706b5288b83967968287c0950480948e8c3f6John McCall } 2383dd706b5288b83967968287c0950480948e8c3f6John McCall for (unsigned I = 0, E = L.arg_size(); I != E; ++I) 2393dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) { 2403dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) 24162dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall Engine.logf("arguments %l and %r differ") 2423dd706b5288b83967968287c0950480948e8c3f6John McCall << L.getArgument(I) << R.getArgument(I); 2433dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2443dd706b5288b83967968287c0950480948e8c3f6John McCall } 2453dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 2463dd706b5288b83967968287c0950480948e8c3f6John McCall } 2473dd706b5288b83967968287c0950480948e8c3f6John McCall 2483dd706b5288b83967968287c0950480948e8c3f6John McCall bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) { 2493dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: metadata (if Complain is set) 2503dd706b5288b83967968287c0950480948e8c3f6John McCall 2513dd706b5288b83967968287c0950480948e8c3f6John McCall // Different opcodes always imply different operations. 2523dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getOpcode() != R->getOpcode()) { 2533dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("different instruction types"); 2543dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2553dd706b5288b83967968287c0950480948e8c3f6John McCall } 2563dd706b5288b83967968287c0950480948e8c3f6John McCall 2573dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<CmpInst>(L)) { 2583dd706b5288b83967968287c0950480948e8c3f6John McCall if (cast<CmpInst>(L)->getPredicate() 2593dd706b5288b83967968287c0950480948e8c3f6John McCall != cast<CmpInst>(R)->getPredicate()) { 2603dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("different predicates"); 2613dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2623dd706b5288b83967968287c0950480948e8c3f6John McCall } 2633dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<CallInst>(L)) { 2643dd706b5288b83967968287c0950480948e8c3f6John McCall return diffCallSites(CallSite(L), CallSite(R), Complain); 2653dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<PHINode>(L)) { 2663dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: implement. 2673dd706b5288b83967968287c0950480948e8c3f6John McCall 2687a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // This is really weird; type uniquing is broken? 2693dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getType() != R->getType()) { 2703dd706b5288b83967968287c0950480948e8c3f6John McCall if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) { 2713dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("different phi types"); 2723dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2733dd706b5288b83967968287c0950480948e8c3f6John McCall } 2743dd706b5288b83967968287c0950480948e8c3f6John McCall } 2753dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 2763dd706b5288b83967968287c0950480948e8c3f6John McCall 2773dd706b5288b83967968287c0950480948e8c3f6John McCall // Terminators. 2783dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<InvokeInst>(L)) { 2793dd706b5288b83967968287c0950480948e8c3f6John McCall InvokeInst *LI = cast<InvokeInst>(L); 2803dd706b5288b83967968287c0950480948e8c3f6John McCall InvokeInst *RI = cast<InvokeInst>(R); 2813dd706b5288b83967968287c0950480948e8c3f6John McCall if (diffCallSites(CallSite(LI), CallSite(RI), Complain)) 2823dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2833dd706b5288b83967968287c0950480948e8c3f6John McCall 2843dd706b5288b83967968287c0950480948e8c3f6John McCall if (TryUnify) { 2853dd706b5288b83967968287c0950480948e8c3f6John McCall tryUnify(LI->getNormalDest(), RI->getNormalDest()); 2863dd706b5288b83967968287c0950480948e8c3f6John McCall tryUnify(LI->getUnwindDest(), RI->getUnwindDest()); 2873dd706b5288b83967968287c0950480948e8c3f6John McCall } 2883dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 2893dd706b5288b83967968287c0950480948e8c3f6John McCall 2903dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<BranchInst>(L)) { 2913dd706b5288b83967968287c0950480948e8c3f6John McCall BranchInst *LI = cast<BranchInst>(L); 2923dd706b5288b83967968287c0950480948e8c3f6John McCall BranchInst *RI = cast<BranchInst>(R); 2933dd706b5288b83967968287c0950480948e8c3f6John McCall if (LI->isConditional() != RI->isConditional()) { 2943dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("branch conditionality differs"); 2953dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 2963dd706b5288b83967968287c0950480948e8c3f6John McCall } 2973dd706b5288b83967968287c0950480948e8c3f6John McCall 2983dd706b5288b83967968287c0950480948e8c3f6John McCall if (LI->isConditional()) { 2993dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 3003dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("branch conditions differ"); 3013dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3023dd706b5288b83967968287c0950480948e8c3f6John McCall } 3033dd706b5288b83967968287c0950480948e8c3f6John McCall if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1)); 3043dd706b5288b83967968287c0950480948e8c3f6John McCall } 3053dd706b5288b83967968287c0950480948e8c3f6John McCall if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0)); 3063dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 3073dd706b5288b83967968287c0950480948e8c3f6John McCall 3083dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<SwitchInst>(L)) { 3093dd706b5288b83967968287c0950480948e8c3f6John McCall SwitchInst *LI = cast<SwitchInst>(L); 3103dd706b5288b83967968287c0950480948e8c3f6John McCall SwitchInst *RI = cast<SwitchInst>(R); 3113dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 3123dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("switch conditions differ"); 3133dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3143dd706b5288b83967968287c0950480948e8c3f6John McCall } 3153dd706b5288b83967968287c0950480948e8c3f6John McCall if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest()); 3163dd706b5288b83967968287c0950480948e8c3f6John McCall 3173dd706b5288b83967968287c0950480948e8c3f6John McCall bool Difference = false; 3183dd706b5288b83967968287c0950480948e8c3f6John McCall 319f4c261b1378b0f7aaede3a791f0e05c9ab94ea34Stepan Dyatkovskiy DenseMap<Constant*, BasicBlock*> LCases; 320c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy 3213d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end(); 322c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy I != E; ++I) 323f4c261b1378b0f7aaede3a791f0e05c9ab94ea34Stepan Dyatkovskiy LCases[I.getCaseValueEx()] = I.getCaseSuccessor(); 324c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy 3253d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end(); 326c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy I != E; ++I) { 3270aa32d5d0ff6cd65b6cff957858a79e2d2a614bdStepan Dyatkovskiy IntegersSubset CaseValue = I.getCaseValueEx(); 3283dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock *LCase = LCases[CaseValue]; 3293dd706b5288b83967968287c0950480948e8c3f6John McCall if (LCase) { 330c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy if (TryUnify) tryUnify(LCase, I.getCaseSuccessor()); 3313dd706b5288b83967968287c0950480948e8c3f6John McCall LCases.erase(CaseValue); 332bd3c5ecd37e760f0430c9cbd1fda5740eb7c0e27John McCall } else if (Complain || !Difference) { 3333dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) 33462dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall Engine.logf("right switch has extra case %r") << CaseValue; 3353dd706b5288b83967968287c0950480948e8c3f6John McCall Difference = true; 3363dd706b5288b83967968287c0950480948e8c3f6John McCall } 3373dd706b5288b83967968287c0950480948e8c3f6John McCall } 3383dd706b5288b83967968287c0950480948e8c3f6John McCall if (!Difference) 339f4c261b1378b0f7aaede3a791f0e05c9ab94ea34Stepan Dyatkovskiy for (DenseMap<Constant*, BasicBlock*>::iterator 3403dd706b5288b83967968287c0950480948e8c3f6John McCall I = LCases.begin(), E = LCases.end(); I != E; ++I) { 3413dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) 34262dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall Engine.logf("left switch has extra case %l") << I->first; 3433dd706b5288b83967968287c0950480948e8c3f6John McCall Difference = true; 3443dd706b5288b83967968287c0950480948e8c3f6John McCall } 3453dd706b5288b83967968287c0950480948e8c3f6John McCall return Difference; 3463dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (isa<UnreachableInst>(L)) { 3473dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 3483dd706b5288b83967968287c0950480948e8c3f6John McCall } 3493dd706b5288b83967968287c0950480948e8c3f6John McCall 3503dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getNumOperands() != R->getNumOperands()) { 3513dd706b5288b83967968287c0950480948e8c3f6John McCall if (Complain) Engine.log("instructions have different operand counts"); 3523dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3533dd706b5288b83967968287c0950480948e8c3f6John McCall } 3543dd706b5288b83967968287c0950480948e8c3f6John McCall 3553dd706b5288b83967968287c0950480948e8c3f6John McCall for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) { 3563dd706b5288b83967968287c0950480948e8c3f6John McCall Value *LO = L->getOperand(I), *RO = R->getOperand(I); 3573dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(LO, RO)) { 35862dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall if (Complain) Engine.logf("operands %l and %r differ") << LO << RO; 3593dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3603dd706b5288b83967968287c0950480948e8c3f6John McCall } 3613dd706b5288b83967968287c0950480948e8c3f6John McCall } 3623dd706b5288b83967968287c0950480948e8c3f6John McCall 3633dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 3643dd706b5288b83967968287c0950480948e8c3f6John McCall } 3653dd706b5288b83967968287c0950480948e8c3f6John McCall 3663dd706b5288b83967968287c0950480948e8c3f6John McCall bool equivalentAsOperands(Constant *L, Constant *R) { 3673dd706b5288b83967968287c0950480948e8c3f6John McCall // Use equality as a preliminary filter. 3683dd706b5288b83967968287c0950480948e8c3f6John McCall if (L == R) 3693dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3703dd706b5288b83967968287c0950480948e8c3f6John McCall 3713dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getValueID() != R->getValueID()) 3723dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 3733dd706b5288b83967968287c0950480948e8c3f6John McCall 3743dd706b5288b83967968287c0950480948e8c3f6John McCall // Ask the engine about global values. 3753dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<GlobalValue>(L)) 3763dd706b5288b83967968287c0950480948e8c3f6John McCall return Engine.equivalentAsOperands(cast<GlobalValue>(L), 3773dd706b5288b83967968287c0950480948e8c3f6John McCall cast<GlobalValue>(R)); 3783dd706b5288b83967968287c0950480948e8c3f6John McCall 3793dd706b5288b83967968287c0950480948e8c3f6John McCall // Compare constant expressions structurally. 3803dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<ConstantExpr>(L)) 3813dd706b5288b83967968287c0950480948e8c3f6John McCall return equivalentAsOperands(cast<ConstantExpr>(L), 3823dd706b5288b83967968287c0950480948e8c3f6John McCall cast<ConstantExpr>(R)); 3833dd706b5288b83967968287c0950480948e8c3f6John McCall 3843dd706b5288b83967968287c0950480948e8c3f6John McCall // Nulls of the "same type" don't always actually have the same 3853dd706b5288b83967968287c0950480948e8c3f6John McCall // type; I don't know why. Just white-list them. 3863dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<ConstantPointerNull>(L)) 3873dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 3883dd706b5288b83967968287c0950480948e8c3f6John McCall 3893dd706b5288b83967968287c0950480948e8c3f6John McCall // Block addresses only match if we've already encountered the 3903dd706b5288b83967968287c0950480948e8c3f6John McCall // block. FIXME: tentative matches? 3913dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<BlockAddress>(L)) 3923dd706b5288b83967968287c0950480948e8c3f6John McCall return Blocks[cast<BlockAddress>(L)->getBasicBlock()] 3933dd706b5288b83967968287c0950480948e8c3f6John McCall == cast<BlockAddress>(R)->getBasicBlock(); 3943dd706b5288b83967968287c0950480948e8c3f6John McCall 3953dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 3963dd706b5288b83967968287c0950480948e8c3f6John McCall } 3973dd706b5288b83967968287c0950480948e8c3f6John McCall 3983dd706b5288b83967968287c0950480948e8c3f6John McCall bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) { 3993dd706b5288b83967968287c0950480948e8c3f6John McCall if (L == R) 4003dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 4013dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getOpcode() != R->getOpcode()) 4023dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 4033dd706b5288b83967968287c0950480948e8c3f6John McCall 4043dd706b5288b83967968287c0950480948e8c3f6John McCall switch (L->getOpcode()) { 4053dd706b5288b83967968287c0950480948e8c3f6John McCall case Instruction::ICmp: 4063dd706b5288b83967968287c0950480948e8c3f6John McCall case Instruction::FCmp: 4073dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getPredicate() != R->getPredicate()) 4083dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 4093dd706b5288b83967968287c0950480948e8c3f6John McCall break; 4103dd706b5288b83967968287c0950480948e8c3f6John McCall 4113dd706b5288b83967968287c0950480948e8c3f6John McCall case Instruction::GetElementPtr: 4123dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: inbounds? 4133dd706b5288b83967968287c0950480948e8c3f6John McCall break; 4143dd706b5288b83967968287c0950480948e8c3f6John McCall 4153dd706b5288b83967968287c0950480948e8c3f6John McCall default: 4163dd706b5288b83967968287c0950480948e8c3f6John McCall break; 4173dd706b5288b83967968287c0950480948e8c3f6John McCall } 4183dd706b5288b83967968287c0950480948e8c3f6John McCall 4193dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getNumOperands() != R->getNumOperands()) 4203dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 4213dd706b5288b83967968287c0950480948e8c3f6John McCall 4223dd706b5288b83967968287c0950480948e8c3f6John McCall for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) 4233dd706b5288b83967968287c0950480948e8c3f6John McCall if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I))) 4243dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 4253dd706b5288b83967968287c0950480948e8c3f6John McCall 4263dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 4273dd706b5288b83967968287c0950480948e8c3f6John McCall } 4283dd706b5288b83967968287c0950480948e8c3f6John McCall 4293dd706b5288b83967968287c0950480948e8c3f6John McCall bool equivalentAsOperands(Value *L, Value *R) { 4303dd706b5288b83967968287c0950480948e8c3f6John McCall // Fall out if the values have different kind. 4313dd706b5288b83967968287c0950480948e8c3f6John McCall // This possibly shouldn't take priority over oracles. 4323dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->getValueID() != R->getValueID()) 4333dd706b5288b83967968287c0950480948e8c3f6John McCall return false; 4343dd706b5288b83967968287c0950480948e8c3f6John McCall 4353dd706b5288b83967968287c0950480948e8c3f6John McCall // Value subtypes: Argument, Constant, Instruction, BasicBlock, 4363dd706b5288b83967968287c0950480948e8c3f6John McCall // InlineAsm, MDNode, MDString, PseudoSourceValue 4373dd706b5288b83967968287c0950480948e8c3f6John McCall 4383dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<Constant>(L)) 4393dd706b5288b83967968287c0950480948e8c3f6John McCall return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R)); 4403dd706b5288b83967968287c0950480948e8c3f6John McCall 4413dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<Instruction>(L)) 442dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall return Values[L] == R || TentativeValues.count(std::make_pair(L, R)); 4433dd706b5288b83967968287c0950480948e8c3f6John McCall 4443dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<Argument>(L)) 4453dd706b5288b83967968287c0950480948e8c3f6John McCall return Values[L] == R; 4463dd706b5288b83967968287c0950480948e8c3f6John McCall 4473dd706b5288b83967968287c0950480948e8c3f6John McCall if (isa<BasicBlock>(L)) 4483dd706b5288b83967968287c0950480948e8c3f6John McCall return Blocks[cast<BasicBlock>(L)] != R; 4493dd706b5288b83967968287c0950480948e8c3f6John McCall 4503dd706b5288b83967968287c0950480948e8c3f6John McCall // Pretend everything else is identical. 4513dd706b5288b83967968287c0950480948e8c3f6John McCall return true; 4523dd706b5288b83967968287c0950480948e8c3f6John McCall } 4533dd706b5288b83967968287c0950480948e8c3f6John McCall 4543dd706b5288b83967968287c0950480948e8c3f6John McCall // Avoid a gcc warning about accessing 'this' in an initializer. 4553dd706b5288b83967968287c0950480948e8c3f6John McCall FunctionDifferenceEngine *this_() { return this; } 4563dd706b5288b83967968287c0950480948e8c3f6John McCall 4573dd706b5288b83967968287c0950480948e8c3f6John McCallpublic: 4583dd706b5288b83967968287c0950480948e8c3f6John McCall FunctionDifferenceEngine(DifferenceEngine &Engine) : 4593dd706b5288b83967968287c0950480948e8c3f6John McCall Engine(Engine), Queue(QueueSorter(*this_())) {} 4603dd706b5288b83967968287c0950480948e8c3f6John McCall 4613dd706b5288b83967968287c0950480948e8c3f6John McCall void diff(Function *L, Function *R) { 4623dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->arg_size() != R->arg_size()) 4633dd706b5288b83967968287c0950480948e8c3f6John McCall Engine.log("different argument counts"); 4643dd706b5288b83967968287c0950480948e8c3f6John McCall 4653dd706b5288b83967968287c0950480948e8c3f6John McCall // Map the arguments. 4663dd706b5288b83967968287c0950480948e8c3f6John McCall for (Function::arg_iterator 4673dd706b5288b83967968287c0950480948e8c3f6John McCall LI = L->arg_begin(), LE = L->arg_end(), 4683dd706b5288b83967968287c0950480948e8c3f6John McCall RI = R->arg_begin(), RE = R->arg_end(); 4693dd706b5288b83967968287c0950480948e8c3f6John McCall LI != LE && RI != RE; ++LI, ++RI) 4703dd706b5288b83967968287c0950480948e8c3f6John McCall Values[&*LI] = &*RI; 4713dd706b5288b83967968287c0950480948e8c3f6John McCall 4723dd706b5288b83967968287c0950480948e8c3f6John McCall tryUnify(&*L->begin(), &*R->begin()); 4733dd706b5288b83967968287c0950480948e8c3f6John McCall processQueue(); 4743dd706b5288b83967968287c0950480948e8c3f6John McCall } 4753dd706b5288b83967968287c0950480948e8c3f6John McCall}; 4763dd706b5288b83967968287c0950480948e8c3f6John McCall 4773dd706b5288b83967968287c0950480948e8c3f6John McCallstruct DiffEntry { 4783dd706b5288b83967968287c0950480948e8c3f6John McCall DiffEntry() : Cost(0) {} 4793dd706b5288b83967968287c0950480948e8c3f6John McCall 4803dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Cost; 4813dd706b5288b83967968287c0950480948e8c3f6John McCall llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange 4823dd706b5288b83967968287c0950480948e8c3f6John McCall}; 4833dd706b5288b83967968287c0950480948e8c3f6John McCall 4843dd706b5288b83967968287c0950480948e8c3f6John McCallbool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L, 4853dd706b5288b83967968287c0950480948e8c3f6John McCall Instruction *R) { 4863dd706b5288b83967968287c0950480948e8c3f6John McCall return !diff(L, R, false, false); 4873dd706b5288b83967968287c0950480948e8c3f6John McCall} 4883dd706b5288b83967968287c0950480948e8c3f6John McCall 4893dd706b5288b83967968287c0950480948e8c3f6John McCallvoid FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart, 4903dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock::iterator RStart) { 4913dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock::iterator LE = LStart->getParent()->end(); 4923dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock::iterator RE = RStart->getParent()->end(); 4933dd706b5288b83967968287c0950480948e8c3f6John McCall 4943dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned NL = std::distance(LStart, LE); 4953dd706b5288b83967968287c0950480948e8c3f6John McCall 4963dd706b5288b83967968287c0950480948e8c3f6John McCall SmallVector<DiffEntry, 20> Paths1(NL+1); 4973dd706b5288b83967968287c0950480948e8c3f6John McCall SmallVector<DiffEntry, 20> Paths2(NL+1); 4983dd706b5288b83967968287c0950480948e8c3f6John McCall 4993dd706b5288b83967968287c0950480948e8c3f6John McCall DiffEntry *Cur = Paths1.data(); 5003dd706b5288b83967968287c0950480948e8c3f6John McCall DiffEntry *Next = Paths2.data(); 5013dd706b5288b83967968287c0950480948e8c3f6John McCall 502dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall const unsigned LeftCost = 2; 503dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall const unsigned RightCost = 2; 504dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall const unsigned MatchCost = 0; 505dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall 506dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall assert(TentativeValues.empty()); 5073dd706b5288b83967968287c0950480948e8c3f6John McCall 5083dd706b5288b83967968287c0950480948e8c3f6John McCall // Initialize the first column. 5093dd706b5288b83967968287c0950480948e8c3f6John McCall for (unsigned I = 0; I != NL+1; ++I) { 510dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall Cur[I].Cost = I * LeftCost; 5113dd706b5288b83967968287c0950480948e8c3f6John McCall for (unsigned J = 0; J != I; ++J) 5127d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin Cur[I].Path.push_back(DC_left); 5133dd706b5288b83967968287c0950480948e8c3f6John McCall } 5143dd706b5288b83967968287c0950480948e8c3f6John McCall 5153dd706b5288b83967968287c0950480948e8c3f6John McCall for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) { 5163dd706b5288b83967968287c0950480948e8c3f6John McCall // Initialize the first row. 5173dd706b5288b83967968287c0950480948e8c3f6John McCall Next[0] = Cur[0]; 518dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall Next[0].Cost += RightCost; 5197d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin Next[0].Path.push_back(DC_right); 5203dd706b5288b83967968287c0950480948e8c3f6John McCall 5213dd706b5288b83967968287c0950480948e8c3f6John McCall unsigned Index = 1; 5223dd706b5288b83967968287c0950480948e8c3f6John McCall for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) { 5233dd706b5288b83967968287c0950480948e8c3f6John McCall if (matchForBlockDiff(&*LI, &*RI)) { 5243dd706b5288b83967968287c0950480948e8c3f6John McCall Next[Index] = Cur[Index-1]; 525dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall Next[Index].Cost += MatchCost; 5267d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin Next[Index].Path.push_back(DC_match); 527dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall TentativeValues.insert(std::make_pair(&*LI, &*RI)); 5283dd706b5288b83967968287c0950480948e8c3f6John McCall } else if (Next[Index-1].Cost <= Cur[Index].Cost) { 5293dd706b5288b83967968287c0950480948e8c3f6John McCall Next[Index] = Next[Index-1]; 530dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall Next[Index].Cost += LeftCost; 5317d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin Next[Index].Path.push_back(DC_left); 5323dd706b5288b83967968287c0950480948e8c3f6John McCall } else { 5333dd706b5288b83967968287c0950480948e8c3f6John McCall Next[Index] = Cur[Index]; 534dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall Next[Index].Cost += RightCost; 5357d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin Next[Index].Path.push_back(DC_right); 5363dd706b5288b83967968287c0950480948e8c3f6John McCall } 5373dd706b5288b83967968287c0950480948e8c3f6John McCall } 5383dd706b5288b83967968287c0950480948e8c3f6John McCall 5393dd706b5288b83967968287c0950480948e8c3f6John McCall std::swap(Cur, Next); 5403dd706b5288b83967968287c0950480948e8c3f6John McCall } 5413dd706b5288b83967968287c0950480948e8c3f6John McCall 54282bd5eaa710b18893951e199fda4376e84b7ec34John McCall // We don't need the tentative values anymore; everything from here 54382bd5eaa710b18893951e199fda4376e84b7ec34John McCall // on out should be non-tentative. 54482bd5eaa710b18893951e199fda4376e84b7ec34John McCall TentativeValues.clear(); 54582bd5eaa710b18893951e199fda4376e84b7ec34John McCall 5463dd706b5288b83967968287c0950480948e8c3f6John McCall SmallVectorImpl<char> &Path = Cur[NL].Path; 5473dd706b5288b83967968287c0950480948e8c3f6John McCall BasicBlock::iterator LI = LStart, RI = RStart; 5483dd706b5288b83967968287c0950480948e8c3f6John McCall 5497d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin DiffLogBuilder Diff(Engine.getConsumer()); 5503dd706b5288b83967968287c0950480948e8c3f6John McCall 5513dd706b5288b83967968287c0950480948e8c3f6John McCall // Drop trailing matches. 5527d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin while (Path.back() == DC_match) 5533dd706b5288b83967968287c0950480948e8c3f6John McCall Path.pop_back(); 5543dd706b5288b83967968287c0950480948e8c3f6John McCall 555dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall // Skip leading matches. 556dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall SmallVectorImpl<char>::iterator 557dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall PI = Path.begin(), PE = Path.end(); 5587d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin while (PI != PE && *PI == DC_match) { 55982bd5eaa710b18893951e199fda4376e84b7ec34John McCall unify(&*LI, &*RI); 560dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall ++PI, ++LI, ++RI; 56182bd5eaa710b18893951e199fda4376e84b7ec34John McCall } 562dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall 563dfb44ac690b9404469a485e252f4ac026bcdefa1John McCall for (; PI != PE; ++PI) { 5647d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin switch (static_cast<DiffChange>(*PI)) { 5657d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin case DC_match: 5663dd706b5288b83967968287c0950480948e8c3f6John McCall assert(LI != LE && RI != RE); 5673dd706b5288b83967968287c0950480948e8c3f6John McCall { 5683dd706b5288b83967968287c0950480948e8c3f6John McCall Instruction *L = &*LI, *R = &*RI; 56982bd5eaa710b18893951e199fda4376e84b7ec34John McCall unify(L, R); 5703dd706b5288b83967968287c0950480948e8c3f6John McCall Diff.addMatch(L, R); 5713dd706b5288b83967968287c0950480948e8c3f6John McCall } 5723dd706b5288b83967968287c0950480948e8c3f6John McCall ++LI; ++RI; 5733dd706b5288b83967968287c0950480948e8c3f6John McCall break; 5743dd706b5288b83967968287c0950480948e8c3f6John McCall 5757d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin case DC_left: 5763dd706b5288b83967968287c0950480948e8c3f6John McCall assert(LI != LE); 5773dd706b5288b83967968287c0950480948e8c3f6John McCall Diff.addLeft(&*LI); 5783dd706b5288b83967968287c0950480948e8c3f6John McCall ++LI; 5793dd706b5288b83967968287c0950480948e8c3f6John McCall break; 5803dd706b5288b83967968287c0950480948e8c3f6John McCall 5817d4fc4fb345ee8a1de15c718a854b5f38c1e6e46Renato Golin case DC_right: 5823dd706b5288b83967968287c0950480948e8c3f6John McCall assert(RI != RE); 5833dd706b5288b83967968287c0950480948e8c3f6John McCall Diff.addRight(&*RI); 5843dd706b5288b83967968287c0950480948e8c3f6John McCall ++RI; 5853dd706b5288b83967968287c0950480948e8c3f6John McCall break; 5863dd706b5288b83967968287c0950480948e8c3f6John McCall } 5873dd706b5288b83967968287c0950480948e8c3f6John McCall } 5883dd706b5288b83967968287c0950480948e8c3f6John McCall 58982bd5eaa710b18893951e199fda4376e84b7ec34John McCall // Finishing unifying and complaining about the tails of the block, 59082bd5eaa710b18893951e199fda4376e84b7ec34John McCall // which should be matches all the way through. 59182bd5eaa710b18893951e199fda4376e84b7ec34John McCall while (LI != LE) { 59282bd5eaa710b18893951e199fda4376e84b7ec34John McCall assert(RI != RE); 59382bd5eaa710b18893951e199fda4376e84b7ec34John McCall unify(&*LI, &*RI); 59482bd5eaa710b18893951e199fda4376e84b7ec34John McCall ++LI, ++RI; 59582bd5eaa710b18893951e199fda4376e84b7ec34John McCall } 596b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall 597b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall // If the terminators have different kinds, but one is an invoke and the 598b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall // other is an unconditional branch immediately following a call, unify 599b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall // the results and the destinations. 600b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall TerminatorInst *LTerm = LStart->getParent()->getTerminator(); 601b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall TerminatorInst *RTerm = RStart->getParent()->getTerminator(); 602b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) { 603b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (cast<BranchInst>(LTerm)->isConditional()) return; 604b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall BasicBlock::iterator I = LTerm; 605b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (I == LStart->getParent()->begin()) return; 606b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall --I; 607b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!isa<CallInst>(*I)) return; 608b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall CallInst *LCall = cast<CallInst>(&*I); 609b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall InvokeInst *RInvoke = cast<InvokeInst>(RTerm); 610b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue())) 611b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall return; 612b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!LCall->use_empty()) 613b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall Values[LCall] = RInvoke; 614b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest()); 615b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) { 616b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (cast<BranchInst>(RTerm)->isConditional()) return; 617b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall BasicBlock::iterator I = RTerm; 618b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (I == RStart->getParent()->begin()) return; 619b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall --I; 620b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!isa<CallInst>(*I)) return; 621b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall CallInst *RCall = cast<CallInst>(I); 622b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall InvokeInst *LInvoke = cast<InvokeInst>(LTerm); 623b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue())) 624b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall return; 625b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall if (!LInvoke->use_empty()) 626b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall Values[LInvoke] = RCall; 627b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0)); 628b82b4339d1dded9c7e36afac80aac2ca73918e51John McCall } 6293dd706b5288b83967968287c0950480948e8c3f6John McCall} 6303dd706b5288b83967968287c0950480948e8c3f6John McCall 6313dd706b5288b83967968287c0950480948e8c3f6John McCall} 6323dd706b5288b83967968287c0950480948e8c3f6John McCall 6332d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid DifferenceEngine::Oracle::anchor() { } 6342d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 6353dd706b5288b83967968287c0950480948e8c3f6John McCallvoid DifferenceEngine::diff(Function *L, Function *R) { 6363dd706b5288b83967968287c0950480948e8c3f6John McCall Context C(*this, L, R); 6373dd706b5288b83967968287c0950480948e8c3f6John McCall 6383dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: types 6393dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: attributes and CC 6403dd706b5288b83967968287c0950480948e8c3f6John McCall // FIXME: parameter attributes 6413dd706b5288b83967968287c0950480948e8c3f6John McCall 6423dd706b5288b83967968287c0950480948e8c3f6John McCall // If both are declarations, we're done. 6433dd706b5288b83967968287c0950480948e8c3f6John McCall if (L->empty() && R->empty()) 6443dd706b5288b83967968287c0950480948e8c3f6John McCall return; 6453dd706b5288b83967968287c0950480948e8c3f6John McCall else if (L->empty()) 6463dd706b5288b83967968287c0950480948e8c3f6John McCall log("left function is declaration, right function is definition"); 6473dd706b5288b83967968287c0950480948e8c3f6John McCall else if (R->empty()) 6483dd706b5288b83967968287c0950480948e8c3f6John McCall log("right function is declaration, left function is definition"); 6493dd706b5288b83967968287c0950480948e8c3f6John McCall else 6503dd706b5288b83967968287c0950480948e8c3f6John McCall FunctionDifferenceEngine(*this).diff(L, R); 6513dd706b5288b83967968287c0950480948e8c3f6John McCall} 6523dd706b5288b83967968287c0950480948e8c3f6John McCall 6533dd706b5288b83967968287c0950480948e8c3f6John McCallvoid DifferenceEngine::diff(Module *L, Module *R) { 6543dd706b5288b83967968287c0950480948e8c3f6John McCall StringSet<> LNames; 6553dd706b5288b83967968287c0950480948e8c3f6John McCall SmallVector<std::pair<Function*,Function*>, 20> Queue; 6563dd706b5288b83967968287c0950480948e8c3f6John McCall 6573dd706b5288b83967968287c0950480948e8c3f6John McCall for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) { 6583dd706b5288b83967968287c0950480948e8c3f6John McCall Function *LFn = &*I; 6593dd706b5288b83967968287c0950480948e8c3f6John McCall LNames.insert(LFn->getName()); 6603dd706b5288b83967968287c0950480948e8c3f6John McCall 6613dd706b5288b83967968287c0950480948e8c3f6John McCall if (Function *RFn = R->getFunction(LFn->getName())) 6623dd706b5288b83967968287c0950480948e8c3f6John McCall Queue.push_back(std::make_pair(LFn, RFn)); 6633dd706b5288b83967968287c0950480948e8c3f6John McCall else 66462dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall logf("function %l exists only in left module") << LFn; 6653dd706b5288b83967968287c0950480948e8c3f6John McCall } 6663dd706b5288b83967968287c0950480948e8c3f6John McCall 6673dd706b5288b83967968287c0950480948e8c3f6John McCall for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) { 6683dd706b5288b83967968287c0950480948e8c3f6John McCall Function *RFn = &*I; 6693dd706b5288b83967968287c0950480948e8c3f6John McCall if (!LNames.count(RFn->getName())) 67062dc1f3d827df8b0e2f88ae9e649893d0dbe8830John McCall logf("function %r exists only in right module") << RFn; 6713dd706b5288b83967968287c0950480948e8c3f6John McCall } 6723dd706b5288b83967968287c0950480948e8c3f6John McCall 6733dd706b5288b83967968287c0950480948e8c3f6John McCall for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator 6743dd706b5288b83967968287c0950480948e8c3f6John McCall I = Queue.begin(), E = Queue.end(); I != E; ++I) 6753dd706b5288b83967968287c0950480948e8c3f6John McCall diff(I->first, I->second); 6763dd706b5288b83967968287c0950480948e8c3f6John McCall} 6773dd706b5288b83967968287c0950480948e8c3f6John McCall 6783dd706b5288b83967968287c0950480948e8c3f6John McCallbool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) { 6793dd706b5288b83967968287c0950480948e8c3f6John McCall if (globalValueOracle) return (*globalValueOracle)(L, R); 6803dd706b5288b83967968287c0950480948e8c3f6John McCall return L->getName() == R->getName(); 6813dd706b5288b83967968287c0950480948e8c3f6John McCall} 682