1212793Sdim//===-- DifferenceEngine.cpp - Structural function/module comparison ------===// 2212793Sdim// 3212793Sdim// The LLVM Compiler Infrastructure 4212793Sdim// 5212793Sdim// This file is distributed under the University of Illinois Open Source 6212793Sdim// License. See LICENSE.TXT for details. 7212793Sdim// 8212793Sdim//===----------------------------------------------------------------------===// 9212793Sdim// 10212793Sdim// This header defines the implementation of the LLVM difference 11212793Sdim// engine, which structurally compares global values within a module. 12212793Sdim// 13212793Sdim//===----------------------------------------------------------------------===// 14212793Sdim 15212793Sdim#include "DifferenceEngine.h" 16212793Sdim#include "llvm/ADT/DenseMap.h" 17212793Sdim#include "llvm/ADT/DenseSet.h" 18212793Sdim#include "llvm/ADT/SmallVector.h" 19212793Sdim#include "llvm/ADT/StringRef.h" 20212793Sdim#include "llvm/ADT/StringSet.h" 21249423Sdim#include "llvm/IR/Constants.h" 22249423Sdim#include "llvm/IR/Function.h" 23249423Sdim#include "llvm/IR/Instructions.h" 24249423Sdim#include "llvm/IR/Module.h" 25249423Sdim#include "llvm/Support/CFG.h" 26212793Sdim#include "llvm/Support/CallSite.h" 27212793Sdim#include "llvm/Support/ErrorHandling.h" 28212793Sdim#include "llvm/Support/raw_ostream.h" 29212793Sdim#include "llvm/Support/type_traits.h" 30212793Sdim#include <utility> 31212793Sdim 32212793Sdimusing namespace llvm; 33212793Sdim 34212793Sdimnamespace { 35212793Sdim 36212793Sdim/// A priority queue, implemented as a heap. 37212793Sdimtemplate <class T, class Sorter, unsigned InlineCapacity> 38212793Sdimclass PriorityQueue { 39212793Sdim Sorter Precedes; 40212793Sdim llvm::SmallVector<T, InlineCapacity> Storage; 41212793Sdim 42212793Sdimpublic: 43212793Sdim PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {} 44212793Sdim 45212793Sdim /// Checks whether the heap is empty. 46212793Sdim bool empty() const { return Storage.empty(); } 47212793Sdim 48212793Sdim /// Insert a new value on the heap. 49212793Sdim void insert(const T &V) { 50212793Sdim unsigned Index = Storage.size(); 51212793Sdim Storage.push_back(V); 52212793Sdim if (Index == 0) return; 53212793Sdim 54212793Sdim T *data = Storage.data(); 55212793Sdim while (true) { 56212793Sdim unsigned Target = (Index + 1) / 2 - 1; 57212793Sdim if (!Precedes(data[Index], data[Target])) return; 58212793Sdim std::swap(data[Index], data[Target]); 59212793Sdim if (Target == 0) return; 60212793Sdim Index = Target; 61212793Sdim } 62212793Sdim } 63212793Sdim 64212793Sdim /// Remove the minimum value in the heap. Only valid on a non-empty heap. 65212793Sdim T remove_min() { 66212793Sdim assert(!empty()); 67212793Sdim T tmp = Storage[0]; 68212793Sdim 69212793Sdim unsigned NewSize = Storage.size() - 1; 70212793Sdim if (NewSize) { 71212793Sdim // Move the slot at the end to the beginning. 72212793Sdim if (isPodLike<T>::value) 73212793Sdim Storage[0] = Storage[NewSize]; 74212793Sdim else 75212793Sdim std::swap(Storage[0], Storage[NewSize]); 76212793Sdim 77212793Sdim // Bubble the root up as necessary. 78212793Sdim unsigned Index = 0; 79212793Sdim while (true) { 80212793Sdim // With a 1-based index, the children would be Index*2 and Index*2+1. 81212793Sdim unsigned R = (Index + 1) * 2; 82212793Sdim unsigned L = R - 1; 83212793Sdim 84212793Sdim // If R is out of bounds, we're done after this in any case. 85212793Sdim if (R >= NewSize) { 86212793Sdim // If L is also out of bounds, we're done immediately. 87212793Sdim if (L >= NewSize) break; 88212793Sdim 89212793Sdim // Otherwise, test whether we should swap L and Index. 90212793Sdim if (Precedes(Storage[L], Storage[Index])) 91212793Sdim std::swap(Storage[L], Storage[Index]); 92212793Sdim break; 93212793Sdim } 94212793Sdim 95212793Sdim // Otherwise, we need to compare with the smaller of L and R. 96212793Sdim // Prefer R because it's closer to the end of the array. 97212793Sdim unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R); 98212793Sdim 99212793Sdim // If Index is >= the min of L and R, then heap ordering is restored. 100212793Sdim if (!Precedes(Storage[IndexToTest], Storage[Index])) 101212793Sdim break; 102212793Sdim 103212793Sdim // Otherwise, keep bubbling up. 104212793Sdim std::swap(Storage[IndexToTest], Storage[Index]); 105212793Sdim Index = IndexToTest; 106212793Sdim } 107212793Sdim } 108212793Sdim Storage.pop_back(); 109212793Sdim 110212793Sdim return tmp; 111212793Sdim } 112212793Sdim}; 113212793Sdim 114212793Sdim/// A function-scope difference engine. 115212793Sdimclass FunctionDifferenceEngine { 116212793Sdim DifferenceEngine &Engine; 117212793Sdim 118212793Sdim /// The current mapping from old local values to new local values. 119212793Sdim DenseMap<Value*, Value*> Values; 120212793Sdim 121212793Sdim /// The current mapping from old blocks to new blocks. 122212793Sdim DenseMap<BasicBlock*, BasicBlock*> Blocks; 123212793Sdim 124212793Sdim DenseSet<std::pair<Value*, Value*> > TentativeValues; 125212793Sdim 126212793Sdim unsigned getUnprocPredCount(BasicBlock *Block) const { 127212793Sdim unsigned Count = 0; 128212793Sdim for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I) 129212793Sdim if (!Blocks.count(*I)) Count++; 130212793Sdim return Count; 131212793Sdim } 132212793Sdim 133212793Sdim typedef std::pair<BasicBlock*, BasicBlock*> BlockPair; 134212793Sdim 135212793Sdim /// A type which sorts a priority queue by the number of unprocessed 136212793Sdim /// predecessor blocks it has remaining. 137212793Sdim /// 138212793Sdim /// This is actually really expensive to calculate. 139212793Sdim struct QueueSorter { 140212793Sdim const FunctionDifferenceEngine &fde; 141212793Sdim explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {} 142212793Sdim 143212793Sdim bool operator()(const BlockPair &Old, const BlockPair &New) { 144212793Sdim return fde.getUnprocPredCount(Old.first) 145212793Sdim < fde.getUnprocPredCount(New.first); 146212793Sdim } 147212793Sdim }; 148212793Sdim 149212793Sdim /// A queue of unified blocks to process. 150212793Sdim PriorityQueue<BlockPair, QueueSorter, 20> Queue; 151212793Sdim 152212793Sdim /// Try to unify the given two blocks. Enqueues them for processing 153212793Sdim /// if they haven't already been processed. 154212793Sdim /// 155212793Sdim /// Returns true if there was a problem unifying them. 156212793Sdim bool tryUnify(BasicBlock *L, BasicBlock *R) { 157212793Sdim BasicBlock *&Ref = Blocks[L]; 158212793Sdim 159212793Sdim if (Ref) { 160212793Sdim if (Ref == R) return false; 161212793Sdim 162212793Sdim Engine.logf("successor %l cannot be equivalent to %r; " 163212793Sdim "it's already equivalent to %r") 164212793Sdim << L << R << Ref; 165212793Sdim return true; 166212793Sdim } 167212793Sdim 168212793Sdim Ref = R; 169212793Sdim Queue.insert(BlockPair(L, R)); 170212793Sdim return false; 171212793Sdim } 172212793Sdim 173212793Sdim /// Unifies two instructions, given that they're known not to have 174212793Sdim /// structural differences. 175212793Sdim void unify(Instruction *L, Instruction *R) { 176212793Sdim DifferenceEngine::Context C(Engine, L, R); 177212793Sdim 178212793Sdim bool Result = diff(L, R, true, true); 179212793Sdim assert(!Result && "structural differences second time around?"); 180212793Sdim (void) Result; 181212793Sdim if (!L->use_empty()) 182212793Sdim Values[L] = R; 183212793Sdim } 184212793Sdim 185212793Sdim void processQueue() { 186212793Sdim while (!Queue.empty()) { 187212793Sdim BlockPair Pair = Queue.remove_min(); 188212793Sdim diff(Pair.first, Pair.second); 189212793Sdim } 190212793Sdim } 191212793Sdim 192212793Sdim void diff(BasicBlock *L, BasicBlock *R) { 193212793Sdim DifferenceEngine::Context C(Engine, L, R); 194212793Sdim 195212793Sdim BasicBlock::iterator LI = L->begin(), LE = L->end(); 196226584Sdim BasicBlock::iterator RI = R->begin(); 197212793Sdim 198212793Sdim do { 199226584Sdim assert(LI != LE && RI != R->end()); 200212793Sdim Instruction *LeftI = &*LI, *RightI = &*RI; 201212793Sdim 202212793Sdim // If the instructions differ, start the more sophisticated diff 203212793Sdim // algorithm at the start of the block. 204212793Sdim if (diff(LeftI, RightI, false, false)) { 205212793Sdim TentativeValues.clear(); 206212793Sdim return runBlockDiff(L->begin(), R->begin()); 207212793Sdim } 208212793Sdim 209212793Sdim // Otherwise, tentatively unify them. 210212793Sdim if (!LeftI->use_empty()) 211212793Sdim TentativeValues.insert(std::make_pair(LeftI, RightI)); 212212793Sdim 213212793Sdim ++LI, ++RI; 214212793Sdim } while (LI != LE); // This is sufficient: we can't get equality of 215212793Sdim // terminators if there are residual instructions. 216212793Sdim 217212793Sdim // Unify everything in the block, non-tentatively this time. 218212793Sdim TentativeValues.clear(); 219212793Sdim for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI) 220212793Sdim unify(&*LI, &*RI); 221212793Sdim } 222212793Sdim 223212793Sdim bool matchForBlockDiff(Instruction *L, Instruction *R); 224212793Sdim void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI); 225212793Sdim 226212793Sdim bool diffCallSites(CallSite L, CallSite R, bool Complain) { 227212793Sdim // FIXME: call attributes 228212793Sdim if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) { 229212793Sdim if (Complain) Engine.log("called functions differ"); 230212793Sdim return true; 231212793Sdim } 232212793Sdim if (L.arg_size() != R.arg_size()) { 233212793Sdim if (Complain) Engine.log("argument counts differ"); 234212793Sdim return true; 235212793Sdim } 236212793Sdim for (unsigned I = 0, E = L.arg_size(); I != E; ++I) 237212793Sdim if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) { 238212793Sdim if (Complain) 239212793Sdim Engine.logf("arguments %l and %r differ") 240212793Sdim << L.getArgument(I) << R.getArgument(I); 241212793Sdim return true; 242212793Sdim } 243212793Sdim return false; 244212793Sdim } 245212793Sdim 246212793Sdim bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) { 247212793Sdim // FIXME: metadata (if Complain is set) 248212793Sdim 249212793Sdim // Different opcodes always imply different operations. 250212793Sdim if (L->getOpcode() != R->getOpcode()) { 251212793Sdim if (Complain) Engine.log("different instruction types"); 252212793Sdim return true; 253212793Sdim } 254212793Sdim 255212793Sdim if (isa<CmpInst>(L)) { 256212793Sdim if (cast<CmpInst>(L)->getPredicate() 257212793Sdim != cast<CmpInst>(R)->getPredicate()) { 258212793Sdim if (Complain) Engine.log("different predicates"); 259212793Sdim return true; 260212793Sdim } 261212793Sdim } else if (isa<CallInst>(L)) { 262212793Sdim return diffCallSites(CallSite(L), CallSite(R), Complain); 263212793Sdim } else if (isa<PHINode>(L)) { 264212793Sdim // FIXME: implement. 265212793Sdim 266221337Sdim // This is really weird; type uniquing is broken? 267212793Sdim if (L->getType() != R->getType()) { 268212793Sdim if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) { 269212793Sdim if (Complain) Engine.log("different phi types"); 270212793Sdim return true; 271212793Sdim } 272212793Sdim } 273212793Sdim return false; 274212793Sdim 275212793Sdim // Terminators. 276212793Sdim } else if (isa<InvokeInst>(L)) { 277212793Sdim InvokeInst *LI = cast<InvokeInst>(L); 278212793Sdim InvokeInst *RI = cast<InvokeInst>(R); 279212793Sdim if (diffCallSites(CallSite(LI), CallSite(RI), Complain)) 280212793Sdim return true; 281212793Sdim 282212793Sdim if (TryUnify) { 283212793Sdim tryUnify(LI->getNormalDest(), RI->getNormalDest()); 284212793Sdim tryUnify(LI->getUnwindDest(), RI->getUnwindDest()); 285212793Sdim } 286212793Sdim return false; 287212793Sdim 288212793Sdim } else if (isa<BranchInst>(L)) { 289212793Sdim BranchInst *LI = cast<BranchInst>(L); 290212793Sdim BranchInst *RI = cast<BranchInst>(R); 291212793Sdim if (LI->isConditional() != RI->isConditional()) { 292212793Sdim if (Complain) Engine.log("branch conditionality differs"); 293212793Sdim return true; 294212793Sdim } 295212793Sdim 296212793Sdim if (LI->isConditional()) { 297212793Sdim if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 298212793Sdim if (Complain) Engine.log("branch conditions differ"); 299212793Sdim return true; 300212793Sdim } 301212793Sdim if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1)); 302212793Sdim } 303212793Sdim if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0)); 304212793Sdim return false; 305212793Sdim 306212793Sdim } else if (isa<SwitchInst>(L)) { 307212793Sdim SwitchInst *LI = cast<SwitchInst>(L); 308212793Sdim SwitchInst *RI = cast<SwitchInst>(R); 309212793Sdim if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 310212793Sdim if (Complain) Engine.log("switch conditions differ"); 311212793Sdim return true; 312212793Sdim } 313212793Sdim if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest()); 314212793Sdim 315212793Sdim bool Difference = false; 316212793Sdim 317263508Sdim DenseMap<ConstantInt*,BasicBlock*> LCases; 318234353Sdim 319234353Sdim for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end(); 320234353Sdim I != E; ++I) 321263508Sdim LCases[I.getCaseValue()] = I.getCaseSuccessor(); 322234353Sdim 323234353Sdim for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end(); 324234353Sdim I != E; ++I) { 325263508Sdim ConstantInt *CaseValue = I.getCaseValue(); 326212793Sdim BasicBlock *LCase = LCases[CaseValue]; 327212793Sdim if (LCase) { 328234353Sdim if (TryUnify) tryUnify(LCase, I.getCaseSuccessor()); 329212793Sdim LCases.erase(CaseValue); 330234353Sdim } else if (Complain || !Difference) { 331212793Sdim if (Complain) 332212793Sdim Engine.logf("right switch has extra case %r") << CaseValue; 333212793Sdim Difference = true; 334212793Sdim } 335212793Sdim } 336212793Sdim if (!Difference) 337263508Sdim for (DenseMap<ConstantInt*,BasicBlock*>::iterator 338212793Sdim I = LCases.begin(), E = LCases.end(); I != E; ++I) { 339212793Sdim if (Complain) 340212793Sdim Engine.logf("left switch has extra case %l") << I->first; 341212793Sdim Difference = true; 342212793Sdim } 343212793Sdim return Difference; 344212793Sdim } else if (isa<UnreachableInst>(L)) { 345212793Sdim return false; 346212793Sdim } 347212793Sdim 348212793Sdim if (L->getNumOperands() != R->getNumOperands()) { 349212793Sdim if (Complain) Engine.log("instructions have different operand counts"); 350212793Sdim return true; 351212793Sdim } 352212793Sdim 353212793Sdim for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) { 354212793Sdim Value *LO = L->getOperand(I), *RO = R->getOperand(I); 355212793Sdim if (!equivalentAsOperands(LO, RO)) { 356212793Sdim if (Complain) Engine.logf("operands %l and %r differ") << LO << RO; 357212793Sdim return true; 358212793Sdim } 359212793Sdim } 360212793Sdim 361212793Sdim return false; 362212793Sdim } 363212793Sdim 364212793Sdim bool equivalentAsOperands(Constant *L, Constant *R) { 365212793Sdim // Use equality as a preliminary filter. 366212793Sdim if (L == R) 367212793Sdim return true; 368212793Sdim 369212793Sdim if (L->getValueID() != R->getValueID()) 370212793Sdim return false; 371212793Sdim 372212793Sdim // Ask the engine about global values. 373212793Sdim if (isa<GlobalValue>(L)) 374212793Sdim return Engine.equivalentAsOperands(cast<GlobalValue>(L), 375212793Sdim cast<GlobalValue>(R)); 376212793Sdim 377212793Sdim // Compare constant expressions structurally. 378212793Sdim if (isa<ConstantExpr>(L)) 379212793Sdim return equivalentAsOperands(cast<ConstantExpr>(L), 380212793Sdim cast<ConstantExpr>(R)); 381212793Sdim 382212793Sdim // Nulls of the "same type" don't always actually have the same 383212793Sdim // type; I don't know why. Just white-list them. 384212793Sdim if (isa<ConstantPointerNull>(L)) 385212793Sdim return true; 386212793Sdim 387212793Sdim // Block addresses only match if we've already encountered the 388212793Sdim // block. FIXME: tentative matches? 389212793Sdim if (isa<BlockAddress>(L)) 390212793Sdim return Blocks[cast<BlockAddress>(L)->getBasicBlock()] 391212793Sdim == cast<BlockAddress>(R)->getBasicBlock(); 392212793Sdim 393212793Sdim return false; 394212793Sdim } 395212793Sdim 396212793Sdim bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) { 397212793Sdim if (L == R) 398212793Sdim return true; 399212793Sdim if (L->getOpcode() != R->getOpcode()) 400212793Sdim return false; 401212793Sdim 402212793Sdim switch (L->getOpcode()) { 403212793Sdim case Instruction::ICmp: 404212793Sdim case Instruction::FCmp: 405212793Sdim if (L->getPredicate() != R->getPredicate()) 406212793Sdim return false; 407212793Sdim break; 408212793Sdim 409212793Sdim case Instruction::GetElementPtr: 410212793Sdim // FIXME: inbounds? 411212793Sdim break; 412212793Sdim 413212793Sdim default: 414212793Sdim break; 415212793Sdim } 416212793Sdim 417212793Sdim if (L->getNumOperands() != R->getNumOperands()) 418212793Sdim return false; 419212793Sdim 420212793Sdim for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) 421212793Sdim if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I))) 422212793Sdim return false; 423212793Sdim 424212793Sdim return true; 425212793Sdim } 426212793Sdim 427212793Sdim bool equivalentAsOperands(Value *L, Value *R) { 428212793Sdim // Fall out if the values have different kind. 429212793Sdim // This possibly shouldn't take priority over oracles. 430212793Sdim if (L->getValueID() != R->getValueID()) 431212793Sdim return false; 432212793Sdim 433212793Sdim // Value subtypes: Argument, Constant, Instruction, BasicBlock, 434212793Sdim // InlineAsm, MDNode, MDString, PseudoSourceValue 435212793Sdim 436212793Sdim if (isa<Constant>(L)) 437212793Sdim return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R)); 438212793Sdim 439212793Sdim if (isa<Instruction>(L)) 440212793Sdim return Values[L] == R || TentativeValues.count(std::make_pair(L, R)); 441212793Sdim 442212793Sdim if (isa<Argument>(L)) 443212793Sdim return Values[L] == R; 444212793Sdim 445212793Sdim if (isa<BasicBlock>(L)) 446212793Sdim return Blocks[cast<BasicBlock>(L)] != R; 447212793Sdim 448212793Sdim // Pretend everything else is identical. 449212793Sdim return true; 450212793Sdim } 451212793Sdim 452212793Sdim // Avoid a gcc warning about accessing 'this' in an initializer. 453212793Sdim FunctionDifferenceEngine *this_() { return this; } 454212793Sdim 455212793Sdimpublic: 456212793Sdim FunctionDifferenceEngine(DifferenceEngine &Engine) : 457212793Sdim Engine(Engine), Queue(QueueSorter(*this_())) {} 458212793Sdim 459212793Sdim void diff(Function *L, Function *R) { 460212793Sdim if (L->arg_size() != R->arg_size()) 461212793Sdim Engine.log("different argument counts"); 462212793Sdim 463212793Sdim // Map the arguments. 464212793Sdim for (Function::arg_iterator 465212793Sdim LI = L->arg_begin(), LE = L->arg_end(), 466212793Sdim RI = R->arg_begin(), RE = R->arg_end(); 467212793Sdim LI != LE && RI != RE; ++LI, ++RI) 468212793Sdim Values[&*LI] = &*RI; 469212793Sdim 470212793Sdim tryUnify(&*L->begin(), &*R->begin()); 471212793Sdim processQueue(); 472212793Sdim } 473212793Sdim}; 474212793Sdim 475212793Sdimstruct DiffEntry { 476212793Sdim DiffEntry() : Cost(0) {} 477212793Sdim 478212793Sdim unsigned Cost; 479212793Sdim llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange 480212793Sdim}; 481212793Sdim 482212793Sdimbool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L, 483212793Sdim Instruction *R) { 484212793Sdim return !diff(L, R, false, false); 485212793Sdim} 486212793Sdim 487212793Sdimvoid FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart, 488212793Sdim BasicBlock::iterator RStart) { 489212793Sdim BasicBlock::iterator LE = LStart->getParent()->end(); 490212793Sdim BasicBlock::iterator RE = RStart->getParent()->end(); 491212793Sdim 492212793Sdim unsigned NL = std::distance(LStart, LE); 493212793Sdim 494212793Sdim SmallVector<DiffEntry, 20> Paths1(NL+1); 495212793Sdim SmallVector<DiffEntry, 20> Paths2(NL+1); 496212793Sdim 497212793Sdim DiffEntry *Cur = Paths1.data(); 498212793Sdim DiffEntry *Next = Paths2.data(); 499212793Sdim 500212793Sdim const unsigned LeftCost = 2; 501212793Sdim const unsigned RightCost = 2; 502212793Sdim const unsigned MatchCost = 0; 503212793Sdim 504212793Sdim assert(TentativeValues.empty()); 505212793Sdim 506212793Sdim // Initialize the first column. 507212793Sdim for (unsigned I = 0; I != NL+1; ++I) { 508212793Sdim Cur[I].Cost = I * LeftCost; 509212793Sdim for (unsigned J = 0; J != I; ++J) 510221337Sdim Cur[I].Path.push_back(DC_left); 511212793Sdim } 512212793Sdim 513212793Sdim for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) { 514212793Sdim // Initialize the first row. 515212793Sdim Next[0] = Cur[0]; 516212793Sdim Next[0].Cost += RightCost; 517221337Sdim Next[0].Path.push_back(DC_right); 518212793Sdim 519212793Sdim unsigned Index = 1; 520212793Sdim for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) { 521212793Sdim if (matchForBlockDiff(&*LI, &*RI)) { 522212793Sdim Next[Index] = Cur[Index-1]; 523212793Sdim Next[Index].Cost += MatchCost; 524221337Sdim Next[Index].Path.push_back(DC_match); 525212793Sdim TentativeValues.insert(std::make_pair(&*LI, &*RI)); 526212793Sdim } else if (Next[Index-1].Cost <= Cur[Index].Cost) { 527212793Sdim Next[Index] = Next[Index-1]; 528212793Sdim Next[Index].Cost += LeftCost; 529221337Sdim Next[Index].Path.push_back(DC_left); 530212793Sdim } else { 531212793Sdim Next[Index] = Cur[Index]; 532212793Sdim Next[Index].Cost += RightCost; 533221337Sdim Next[Index].Path.push_back(DC_right); 534212793Sdim } 535212793Sdim } 536212793Sdim 537212793Sdim std::swap(Cur, Next); 538212793Sdim } 539212793Sdim 540212793Sdim // We don't need the tentative values anymore; everything from here 541212793Sdim // on out should be non-tentative. 542212793Sdim TentativeValues.clear(); 543212793Sdim 544212793Sdim SmallVectorImpl<char> &Path = Cur[NL].Path; 545212793Sdim BasicBlock::iterator LI = LStart, RI = RStart; 546212793Sdim 547221337Sdim DiffLogBuilder Diff(Engine.getConsumer()); 548212793Sdim 549212793Sdim // Drop trailing matches. 550221337Sdim while (Path.back() == DC_match) 551212793Sdim Path.pop_back(); 552212793Sdim 553212793Sdim // Skip leading matches. 554212793Sdim SmallVectorImpl<char>::iterator 555212793Sdim PI = Path.begin(), PE = Path.end(); 556221337Sdim while (PI != PE && *PI == DC_match) { 557212793Sdim unify(&*LI, &*RI); 558212793Sdim ++PI, ++LI, ++RI; 559212793Sdim } 560212793Sdim 561212793Sdim for (; PI != PE; ++PI) { 562221337Sdim switch (static_cast<DiffChange>(*PI)) { 563221337Sdim case DC_match: 564212793Sdim assert(LI != LE && RI != RE); 565212793Sdim { 566212793Sdim Instruction *L = &*LI, *R = &*RI; 567212793Sdim unify(L, R); 568212793Sdim Diff.addMatch(L, R); 569212793Sdim } 570212793Sdim ++LI; ++RI; 571212793Sdim break; 572212793Sdim 573221337Sdim case DC_left: 574212793Sdim assert(LI != LE); 575212793Sdim Diff.addLeft(&*LI); 576212793Sdim ++LI; 577212793Sdim break; 578212793Sdim 579221337Sdim case DC_right: 580212793Sdim assert(RI != RE); 581212793Sdim Diff.addRight(&*RI); 582212793Sdim ++RI; 583212793Sdim break; 584212793Sdim } 585212793Sdim } 586212793Sdim 587212793Sdim // Finishing unifying and complaining about the tails of the block, 588212793Sdim // which should be matches all the way through. 589212793Sdim while (LI != LE) { 590212793Sdim assert(RI != RE); 591212793Sdim unify(&*LI, &*RI); 592212793Sdim ++LI, ++RI; 593212793Sdim } 594212793Sdim 595212793Sdim // If the terminators have different kinds, but one is an invoke and the 596212793Sdim // other is an unconditional branch immediately following a call, unify 597212793Sdim // the results and the destinations. 598212793Sdim TerminatorInst *LTerm = LStart->getParent()->getTerminator(); 599212793Sdim TerminatorInst *RTerm = RStart->getParent()->getTerminator(); 600212793Sdim if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) { 601212793Sdim if (cast<BranchInst>(LTerm)->isConditional()) return; 602212793Sdim BasicBlock::iterator I = LTerm; 603212793Sdim if (I == LStart->getParent()->begin()) return; 604212793Sdim --I; 605212793Sdim if (!isa<CallInst>(*I)) return; 606212793Sdim CallInst *LCall = cast<CallInst>(&*I); 607212793Sdim InvokeInst *RInvoke = cast<InvokeInst>(RTerm); 608212793Sdim if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue())) 609212793Sdim return; 610212793Sdim if (!LCall->use_empty()) 611212793Sdim Values[LCall] = RInvoke; 612212793Sdim tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest()); 613212793Sdim } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) { 614212793Sdim if (cast<BranchInst>(RTerm)->isConditional()) return; 615212793Sdim BasicBlock::iterator I = RTerm; 616212793Sdim if (I == RStart->getParent()->begin()) return; 617212793Sdim --I; 618212793Sdim if (!isa<CallInst>(*I)) return; 619212793Sdim CallInst *RCall = cast<CallInst>(I); 620212793Sdim InvokeInst *LInvoke = cast<InvokeInst>(LTerm); 621212793Sdim if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue())) 622212793Sdim return; 623212793Sdim if (!LInvoke->use_empty()) 624212793Sdim Values[LInvoke] = RCall; 625212793Sdim tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0)); 626212793Sdim } 627212793Sdim} 628212793Sdim 629212793Sdim} 630212793Sdim 631234353Sdimvoid DifferenceEngine::Oracle::anchor() { } 632234353Sdim 633212793Sdimvoid DifferenceEngine::diff(Function *L, Function *R) { 634212793Sdim Context C(*this, L, R); 635212793Sdim 636212793Sdim // FIXME: types 637212793Sdim // FIXME: attributes and CC 638212793Sdim // FIXME: parameter attributes 639212793Sdim 640212793Sdim // If both are declarations, we're done. 641212793Sdim if (L->empty() && R->empty()) 642212793Sdim return; 643212793Sdim else if (L->empty()) 644212793Sdim log("left function is declaration, right function is definition"); 645212793Sdim else if (R->empty()) 646212793Sdim log("right function is declaration, left function is definition"); 647212793Sdim else 648212793Sdim FunctionDifferenceEngine(*this).diff(L, R); 649212793Sdim} 650212793Sdim 651212793Sdimvoid DifferenceEngine::diff(Module *L, Module *R) { 652212793Sdim StringSet<> LNames; 653212793Sdim SmallVector<std::pair<Function*,Function*>, 20> Queue; 654212793Sdim 655212793Sdim for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) { 656212793Sdim Function *LFn = &*I; 657212793Sdim LNames.insert(LFn->getName()); 658212793Sdim 659212793Sdim if (Function *RFn = R->getFunction(LFn->getName())) 660212793Sdim Queue.push_back(std::make_pair(LFn, RFn)); 661212793Sdim else 662212793Sdim logf("function %l exists only in left module") << LFn; 663212793Sdim } 664212793Sdim 665212793Sdim for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) { 666212793Sdim Function *RFn = &*I; 667212793Sdim if (!LNames.count(RFn->getName())) 668212793Sdim logf("function %r exists only in right module") << RFn; 669212793Sdim } 670212793Sdim 671212793Sdim for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator 672212793Sdim I = Queue.begin(), E = Queue.end(); I != E; ++I) 673212793Sdim diff(I->first, I->second); 674212793Sdim} 675212793Sdim 676212793Sdimbool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) { 677212793Sdim if (globalValueOracle) return (*globalValueOracle)(L, R); 678212793Sdim return L->getName() == R->getName(); 679212793Sdim} 680