1//===-- DifferenceEngine.cpp - Structural function/module comparison ------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This header defines the implementation of the LLVM difference 10// engine, which structurally compares global values within a module. 11// 12//===----------------------------------------------------------------------===// 13 14#include "DifferenceEngine.h" 15#include "llvm/ADT/DenseMap.h" 16#include "llvm/ADT/DenseSet.h" 17#include "llvm/ADT/SmallString.h" 18#include "llvm/ADT/SmallVector.h" 19#include "llvm/ADT/StringSet.h" 20#include "llvm/IR/CFG.h" 21#include "llvm/IR/Constants.h" 22#include "llvm/IR/Function.h" 23#include "llvm/IR/Instructions.h" 24#include "llvm/IR/Module.h" 25#include "llvm/Support/ErrorHandling.h" 26#include "llvm/Support/raw_ostream.h" 27#include "llvm/Support/type_traits.h" 28#include <utility> 29 30using namespace llvm; 31 32namespace { 33 34/// A priority queue, implemented as a heap. 35template <class T, class Sorter, unsigned InlineCapacity> 36class PriorityQueue { 37 Sorter Precedes; 38 llvm::SmallVector<T, InlineCapacity> Storage; 39 40public: 41 PriorityQueue(const Sorter &Precedes) : Precedes(Precedes) {} 42 43 /// Checks whether the heap is empty. 44 bool empty() const { return Storage.empty(); } 45 46 /// Insert a new value on the heap. 47 void insert(const T &V) { 48 unsigned Index = Storage.size(); 49 Storage.push_back(V); 50 if (Index == 0) return; 51 52 T *data = Storage.data(); 53 while (true) { 54 unsigned Target = (Index + 1) / 2 - 1; 55 if (!Precedes(data[Index], data[Target])) return; 56 std::swap(data[Index], data[Target]); 57 if (Target == 0) return; 58 Index = Target; 59 } 60 } 61 62 /// Remove the minimum value in the heap. Only valid on a non-empty heap. 63 T remove_min() { 64 assert(!empty()); 65 T tmp = Storage[0]; 66 67 unsigned NewSize = Storage.size() - 1; 68 if (NewSize) { 69 // Move the slot at the end to the beginning. 70 if (is_trivially_copyable<T>::value) 71 Storage[0] = Storage[NewSize]; 72 else 73 std::swap(Storage[0], Storage[NewSize]); 74 75 // Bubble the root up as necessary. 76 unsigned Index = 0; 77 while (true) { 78 // With a 1-based index, the children would be Index*2 and Index*2+1. 79 unsigned R = (Index + 1) * 2; 80 unsigned L = R - 1; 81 82 // If R is out of bounds, we're done after this in any case. 83 if (R >= NewSize) { 84 // If L is also out of bounds, we're done immediately. 85 if (L >= NewSize) break; 86 87 // Otherwise, test whether we should swap L and Index. 88 if (Precedes(Storage[L], Storage[Index])) 89 std::swap(Storage[L], Storage[Index]); 90 break; 91 } 92 93 // Otherwise, we need to compare with the smaller of L and R. 94 // Prefer R because it's closer to the end of the array. 95 unsigned IndexToTest = (Precedes(Storage[L], Storage[R]) ? L : R); 96 97 // If Index is >= the min of L and R, then heap ordering is restored. 98 if (!Precedes(Storage[IndexToTest], Storage[Index])) 99 break; 100 101 // Otherwise, keep bubbling up. 102 std::swap(Storage[IndexToTest], Storage[Index]); 103 Index = IndexToTest; 104 } 105 } 106 Storage.pop_back(); 107 108 return tmp; 109 } 110}; 111 112/// A function-scope difference engine. 113class FunctionDifferenceEngine { 114 DifferenceEngine &Engine; 115 116 /// The current mapping from old local values to new local values. 117 DenseMap<Value*, Value*> Values; 118 119 /// The current mapping from old blocks to new blocks. 120 DenseMap<BasicBlock*, BasicBlock*> Blocks; 121 122 DenseSet<std::pair<Value*, Value*> > TentativeValues; 123 124 unsigned getUnprocPredCount(BasicBlock *Block) const { 125 unsigned Count = 0; 126 for (pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E; ++I) 127 if (!Blocks.count(*I)) Count++; 128 return Count; 129 } 130 131 typedef std::pair<BasicBlock*, BasicBlock*> BlockPair; 132 133 /// A type which sorts a priority queue by the number of unprocessed 134 /// predecessor blocks it has remaining. 135 /// 136 /// This is actually really expensive to calculate. 137 struct QueueSorter { 138 const FunctionDifferenceEngine &fde; 139 explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {} 140 141 bool operator()(const BlockPair &Old, const BlockPair &New) { 142 return fde.getUnprocPredCount(Old.first) 143 < fde.getUnprocPredCount(New.first); 144 } 145 }; 146 147 /// A queue of unified blocks to process. 148 PriorityQueue<BlockPair, QueueSorter, 20> Queue; 149 150 /// Try to unify the given two blocks. Enqueues them for processing 151 /// if they haven't already been processed. 152 /// 153 /// Returns true if there was a problem unifying them. 154 bool tryUnify(BasicBlock *L, BasicBlock *R) { 155 BasicBlock *&Ref = Blocks[L]; 156 157 if (Ref) { 158 if (Ref == R) return false; 159 160 Engine.logf("successor %l cannot be equivalent to %r; " 161 "it's already equivalent to %r") 162 << L << R << Ref; 163 return true; 164 } 165 166 Ref = R; 167 Queue.insert(BlockPair(L, R)); 168 return false; 169 } 170 171 /// Unifies two instructions, given that they're known not to have 172 /// structural differences. 173 void unify(Instruction *L, Instruction *R) { 174 DifferenceEngine::Context C(Engine, L, R); 175 176 bool Result = diff(L, R, true, true); 177 assert(!Result && "structural differences second time around?"); 178 (void) Result; 179 if (!L->use_empty()) 180 Values[L] = R; 181 } 182 183 void processQueue() { 184 while (!Queue.empty()) { 185 BlockPair Pair = Queue.remove_min(); 186 diff(Pair.first, Pair.second); 187 } 188 } 189 190 void diff(BasicBlock *L, BasicBlock *R) { 191 DifferenceEngine::Context C(Engine, L, R); 192 193 BasicBlock::iterator LI = L->begin(), LE = L->end(); 194 BasicBlock::iterator RI = R->begin(); 195 196 do { 197 assert(LI != LE && RI != R->end()); 198 Instruction *LeftI = &*LI, *RightI = &*RI; 199 200 // If the instructions differ, start the more sophisticated diff 201 // algorithm at the start of the block. 202 if (diff(LeftI, RightI, false, false)) { 203 TentativeValues.clear(); 204 return runBlockDiff(L->begin(), R->begin()); 205 } 206 207 // Otherwise, tentatively unify them. 208 if (!LeftI->use_empty()) 209 TentativeValues.insert(std::make_pair(LeftI, RightI)); 210 211 ++LI; 212 ++RI; 213 } while (LI != LE); // This is sufficient: we can't get equality of 214 // terminators if there are residual instructions. 215 216 // Unify everything in the block, non-tentatively this time. 217 TentativeValues.clear(); 218 for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI) 219 unify(&*LI, &*RI); 220 } 221 222 bool matchForBlockDiff(Instruction *L, Instruction *R); 223 void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI); 224 225 bool diffCallSites(CallBase &L, CallBase &R, bool Complain) { 226 // FIXME: call attributes 227 if (!equivalentAsOperands(L.getCalledOperand(), R.getCalledOperand())) { 228 if (Complain) Engine.log("called functions differ"); 229 return true; 230 } 231 if (L.arg_size() != R.arg_size()) { 232 if (Complain) Engine.log("argument counts differ"); 233 return true; 234 } 235 for (unsigned I = 0, E = L.arg_size(); I != E; ++I) 236 if (!equivalentAsOperands(L.getArgOperand(I), R.getArgOperand(I))) { 237 if (Complain) 238 Engine.logf("arguments %l and %r differ") 239 << L.getArgOperand(I) << R.getArgOperand(I); 240 return true; 241 } 242 return false; 243 } 244 245 bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) { 246 // FIXME: metadata (if Complain is set) 247 248 // Different opcodes always imply different operations. 249 if (L->getOpcode() != R->getOpcode()) { 250 if (Complain) Engine.log("different instruction types"); 251 return true; 252 } 253 254 if (isa<CmpInst>(L)) { 255 if (cast<CmpInst>(L)->getPredicate() 256 != cast<CmpInst>(R)->getPredicate()) { 257 if (Complain) Engine.log("different predicates"); 258 return true; 259 } 260 } else if (isa<CallInst>(L)) { 261 return diffCallSites(cast<CallInst>(*L), cast<CallInst>(*R), Complain); 262 } else if (isa<PHINode>(L)) { 263 // FIXME: implement. 264 265 // This is really weird; type uniquing is broken? 266 if (L->getType() != R->getType()) { 267 if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) { 268 if (Complain) Engine.log("different phi types"); 269 return true; 270 } 271 } 272 return false; 273 274 // Terminators. 275 } else if (isa<InvokeInst>(L)) { 276 InvokeInst &LI = cast<InvokeInst>(*L); 277 InvokeInst &RI = cast<InvokeInst>(*R); 278 if (diffCallSites(LI, RI, Complain)) 279 return true; 280 281 if (TryUnify) { 282 tryUnify(LI.getNormalDest(), RI.getNormalDest()); 283 tryUnify(LI.getUnwindDest(), RI.getUnwindDest()); 284 } 285 return false; 286 287 } else if (isa<BranchInst>(L)) { 288 BranchInst *LI = cast<BranchInst>(L); 289 BranchInst *RI = cast<BranchInst>(R); 290 if (LI->isConditional() != RI->isConditional()) { 291 if (Complain) Engine.log("branch conditionality differs"); 292 return true; 293 } 294 295 if (LI->isConditional()) { 296 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 297 if (Complain) Engine.log("branch conditions differ"); 298 return true; 299 } 300 if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1)); 301 } 302 if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0)); 303 return false; 304 305 } else if (isa<IndirectBrInst>(L)) { 306 IndirectBrInst *LI = cast<IndirectBrInst>(L); 307 IndirectBrInst *RI = cast<IndirectBrInst>(R); 308 if (LI->getNumDestinations() != RI->getNumDestinations()) { 309 if (Complain) Engine.log("indirectbr # of destinations differ"); 310 return true; 311 } 312 313 if (!equivalentAsOperands(LI->getAddress(), RI->getAddress())) { 314 if (Complain) Engine.log("indirectbr addresses differ"); 315 return true; 316 } 317 318 if (TryUnify) { 319 for (unsigned i = 0; i < LI->getNumDestinations(); i++) { 320 tryUnify(LI->getDestination(i), RI->getDestination(i)); 321 } 322 } 323 return false; 324 325 } else if (isa<SwitchInst>(L)) { 326 SwitchInst *LI = cast<SwitchInst>(L); 327 SwitchInst *RI = cast<SwitchInst>(R); 328 if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) { 329 if (Complain) Engine.log("switch conditions differ"); 330 return true; 331 } 332 if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest()); 333 334 bool Difference = false; 335 336 DenseMap<ConstantInt*,BasicBlock*> LCases; 337 for (auto Case : LI->cases()) 338 LCases[Case.getCaseValue()] = Case.getCaseSuccessor(); 339 340 for (auto Case : RI->cases()) { 341 ConstantInt *CaseValue = Case.getCaseValue(); 342 BasicBlock *LCase = LCases[CaseValue]; 343 if (LCase) { 344 if (TryUnify) 345 tryUnify(LCase, Case.getCaseSuccessor()); 346 LCases.erase(CaseValue); 347 } else if (Complain || !Difference) { 348 if (Complain) 349 Engine.logf("right switch has extra case %r") << CaseValue; 350 Difference = true; 351 } 352 } 353 if (!Difference) 354 for (DenseMap<ConstantInt*,BasicBlock*>::iterator 355 I = LCases.begin(), E = LCases.end(); I != E; ++I) { 356 if (Complain) 357 Engine.logf("left switch has extra case %l") << I->first; 358 Difference = true; 359 } 360 return Difference; 361 } else if (isa<UnreachableInst>(L)) { 362 return false; 363 } 364 365 if (L->getNumOperands() != R->getNumOperands()) { 366 if (Complain) Engine.log("instructions have different operand counts"); 367 return true; 368 } 369 370 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) { 371 Value *LO = L->getOperand(I), *RO = R->getOperand(I); 372 if (!equivalentAsOperands(LO, RO)) { 373 if (Complain) Engine.logf("operands %l and %r differ") << LO << RO; 374 return true; 375 } 376 } 377 378 return false; 379 } 380 381 bool equivalentAsOperands(Constant *L, Constant *R) { 382 // Use equality as a preliminary filter. 383 if (L == R) 384 return true; 385 386 if (L->getValueID() != R->getValueID()) 387 return false; 388 389 // Ask the engine about global values. 390 if (isa<GlobalValue>(L)) 391 return Engine.equivalentAsOperands(cast<GlobalValue>(L), 392 cast<GlobalValue>(R)); 393 394 // Compare constant expressions structurally. 395 if (isa<ConstantExpr>(L)) 396 return equivalentAsOperands(cast<ConstantExpr>(L), 397 cast<ConstantExpr>(R)); 398 399 // Constants of the "same type" don't always actually have the same 400 // type; I don't know why. Just white-list them. 401 if (isa<ConstantPointerNull>(L) || isa<UndefValue>(L) || isa<ConstantAggregateZero>(L)) 402 return true; 403 404 // Block addresses only match if we've already encountered the 405 // block. FIXME: tentative matches? 406 if (isa<BlockAddress>(L)) 407 return Blocks[cast<BlockAddress>(L)->getBasicBlock()] 408 == cast<BlockAddress>(R)->getBasicBlock(); 409 410 // If L and R are ConstantVectors, compare each element 411 if (isa<ConstantVector>(L)) { 412 ConstantVector *CVL = cast<ConstantVector>(L); 413 ConstantVector *CVR = cast<ConstantVector>(R); 414 if (CVL->getType()->getNumElements() != CVR->getType()->getNumElements()) 415 return false; 416 for (unsigned i = 0; i < CVL->getType()->getNumElements(); i++) { 417 if (!equivalentAsOperands(CVL->getOperand(i), CVR->getOperand(i))) 418 return false; 419 } 420 return true; 421 } 422 423 return false; 424 } 425 426 bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) { 427 if (L == R) 428 return true; 429 if (L->getOpcode() != R->getOpcode()) 430 return false; 431 432 switch (L->getOpcode()) { 433 case Instruction::ICmp: 434 case Instruction::FCmp: 435 if (L->getPredicate() != R->getPredicate()) 436 return false; 437 break; 438 439 case Instruction::GetElementPtr: 440 // FIXME: inbounds? 441 break; 442 443 default: 444 break; 445 } 446 447 if (L->getNumOperands() != R->getNumOperands()) 448 return false; 449 450 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) 451 if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I))) 452 return false; 453 454 return true; 455 } 456 457 bool equivalentAsOperands(Value *L, Value *R) { 458 // Fall out if the values have different kind. 459 // This possibly shouldn't take priority over oracles. 460 if (L->getValueID() != R->getValueID()) 461 return false; 462 463 // Value subtypes: Argument, Constant, Instruction, BasicBlock, 464 // InlineAsm, MDNode, MDString, PseudoSourceValue 465 466 if (isa<Constant>(L)) 467 return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R)); 468 469 if (isa<Instruction>(L)) 470 return Values[L] == R || TentativeValues.count(std::make_pair(L, R)); 471 472 if (isa<Argument>(L)) 473 return Values[L] == R; 474 475 if (isa<BasicBlock>(L)) 476 return Blocks[cast<BasicBlock>(L)] != R; 477 478 // Pretend everything else is identical. 479 return true; 480 } 481 482 // Avoid a gcc warning about accessing 'this' in an initializer. 483 FunctionDifferenceEngine *this_() { return this; } 484 485public: 486 FunctionDifferenceEngine(DifferenceEngine &Engine) : 487 Engine(Engine), Queue(QueueSorter(*this_())) {} 488 489 void diff(Function *L, Function *R) { 490 if (L->arg_size() != R->arg_size()) 491 Engine.log("different argument counts"); 492 493 // Map the arguments. 494 for (Function::arg_iterator 495 LI = L->arg_begin(), LE = L->arg_end(), 496 RI = R->arg_begin(), RE = R->arg_end(); 497 LI != LE && RI != RE; ++LI, ++RI) 498 Values[&*LI] = &*RI; 499 500 tryUnify(&*L->begin(), &*R->begin()); 501 processQueue(); 502 } 503}; 504 505struct DiffEntry { 506 DiffEntry() : Cost(0) {} 507 508 unsigned Cost; 509 llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange 510}; 511 512bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L, 513 Instruction *R) { 514 return !diff(L, R, false, false); 515} 516 517void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart, 518 BasicBlock::iterator RStart) { 519 BasicBlock::iterator LE = LStart->getParent()->end(); 520 BasicBlock::iterator RE = RStart->getParent()->end(); 521 522 unsigned NL = std::distance(LStart, LE); 523 524 SmallVector<DiffEntry, 20> Paths1(NL+1); 525 SmallVector<DiffEntry, 20> Paths2(NL+1); 526 527 DiffEntry *Cur = Paths1.data(); 528 DiffEntry *Next = Paths2.data(); 529 530 const unsigned LeftCost = 2; 531 const unsigned RightCost = 2; 532 const unsigned MatchCost = 0; 533 534 assert(TentativeValues.empty()); 535 536 // Initialize the first column. 537 for (unsigned I = 0; I != NL+1; ++I) { 538 Cur[I].Cost = I * LeftCost; 539 for (unsigned J = 0; J != I; ++J) 540 Cur[I].Path.push_back(DC_left); 541 } 542 543 for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) { 544 // Initialize the first row. 545 Next[0] = Cur[0]; 546 Next[0].Cost += RightCost; 547 Next[0].Path.push_back(DC_right); 548 549 unsigned Index = 1; 550 for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) { 551 if (matchForBlockDiff(&*LI, &*RI)) { 552 Next[Index] = Cur[Index-1]; 553 Next[Index].Cost += MatchCost; 554 Next[Index].Path.push_back(DC_match); 555 TentativeValues.insert(std::make_pair(&*LI, &*RI)); 556 } else if (Next[Index-1].Cost <= Cur[Index].Cost) { 557 Next[Index] = Next[Index-1]; 558 Next[Index].Cost += LeftCost; 559 Next[Index].Path.push_back(DC_left); 560 } else { 561 Next[Index] = Cur[Index]; 562 Next[Index].Cost += RightCost; 563 Next[Index].Path.push_back(DC_right); 564 } 565 } 566 567 std::swap(Cur, Next); 568 } 569 570 // We don't need the tentative values anymore; everything from here 571 // on out should be non-tentative. 572 TentativeValues.clear(); 573 574 SmallVectorImpl<char> &Path = Cur[NL].Path; 575 BasicBlock::iterator LI = LStart, RI = RStart; 576 577 DiffLogBuilder Diff(Engine.getConsumer()); 578 579 // Drop trailing matches. 580 while (Path.size() && Path.back() == DC_match) 581 Path.pop_back(); 582 583 // Skip leading matches. 584 SmallVectorImpl<char>::iterator 585 PI = Path.begin(), PE = Path.end(); 586 while (PI != PE && *PI == DC_match) { 587 unify(&*LI, &*RI); 588 ++PI; 589 ++LI; 590 ++RI; 591 } 592 593 for (; PI != PE; ++PI) { 594 switch (static_cast<DiffChange>(*PI)) { 595 case DC_match: 596 assert(LI != LE && RI != RE); 597 { 598 Instruction *L = &*LI, *R = &*RI; 599 unify(L, R); 600 Diff.addMatch(L, R); 601 } 602 ++LI; ++RI; 603 break; 604 605 case DC_left: 606 assert(LI != LE); 607 Diff.addLeft(&*LI); 608 ++LI; 609 break; 610 611 case DC_right: 612 assert(RI != RE); 613 Diff.addRight(&*RI); 614 ++RI; 615 break; 616 } 617 } 618 619 // Finishing unifying and complaining about the tails of the block, 620 // which should be matches all the way through. 621 while (LI != LE) { 622 assert(RI != RE); 623 unify(&*LI, &*RI); 624 ++LI; 625 ++RI; 626 } 627 628 // If the terminators have different kinds, but one is an invoke and the 629 // other is an unconditional branch immediately following a call, unify 630 // the results and the destinations. 631 Instruction *LTerm = LStart->getParent()->getTerminator(); 632 Instruction *RTerm = RStart->getParent()->getTerminator(); 633 if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) { 634 if (cast<BranchInst>(LTerm)->isConditional()) return; 635 BasicBlock::iterator I = LTerm->getIterator(); 636 if (I == LStart->getParent()->begin()) return; 637 --I; 638 if (!isa<CallInst>(*I)) return; 639 CallInst *LCall = cast<CallInst>(&*I); 640 InvokeInst *RInvoke = cast<InvokeInst>(RTerm); 641 if (!equivalentAsOperands(LCall->getCalledOperand(), 642 RInvoke->getCalledOperand())) 643 return; 644 if (!LCall->use_empty()) 645 Values[LCall] = RInvoke; 646 tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest()); 647 } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) { 648 if (cast<BranchInst>(RTerm)->isConditional()) return; 649 BasicBlock::iterator I = RTerm->getIterator(); 650 if (I == RStart->getParent()->begin()) return; 651 --I; 652 if (!isa<CallInst>(*I)) return; 653 CallInst *RCall = cast<CallInst>(I); 654 InvokeInst *LInvoke = cast<InvokeInst>(LTerm); 655 if (!equivalentAsOperands(LInvoke->getCalledOperand(), 656 RCall->getCalledOperand())) 657 return; 658 if (!LInvoke->use_empty()) 659 Values[LInvoke] = RCall; 660 tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0)); 661 } 662} 663 664} 665 666void DifferenceEngine::Oracle::anchor() { } 667 668void DifferenceEngine::diff(Function *L, Function *R) { 669 Context C(*this, L, R); 670 671 // FIXME: types 672 // FIXME: attributes and CC 673 // FIXME: parameter attributes 674 675 // If both are declarations, we're done. 676 if (L->empty() && R->empty()) 677 return; 678 else if (L->empty()) 679 log("left function is declaration, right function is definition"); 680 else if (R->empty()) 681 log("right function is declaration, left function is definition"); 682 else 683 FunctionDifferenceEngine(*this).diff(L, R); 684} 685 686void DifferenceEngine::diff(Module *L, Module *R) { 687 StringSet<> LNames; 688 SmallVector<std::pair<Function*,Function*>, 20> Queue; 689 690 unsigned LeftAnonCount = 0; 691 unsigned RightAnonCount = 0; 692 693 for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) { 694 Function *LFn = &*I; 695 StringRef Name = LFn->getName(); 696 if (Name.empty()) { 697 ++LeftAnonCount; 698 continue; 699 } 700 701 LNames.insert(Name); 702 703 if (Function *RFn = R->getFunction(LFn->getName())) 704 Queue.push_back(std::make_pair(LFn, RFn)); 705 else 706 logf("function %l exists only in left module") << LFn; 707 } 708 709 for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) { 710 Function *RFn = &*I; 711 StringRef Name = RFn->getName(); 712 if (Name.empty()) { 713 ++RightAnonCount; 714 continue; 715 } 716 717 if (!LNames.count(Name)) 718 logf("function %r exists only in right module") << RFn; 719 } 720 721 722 if (LeftAnonCount != 0 || RightAnonCount != 0) { 723 SmallString<32> Tmp; 724 logf(("not comparing " + Twine(LeftAnonCount) + 725 " anonymous functions in the left module and " + 726 Twine(RightAnonCount) + " in the right module") 727 .toStringRef(Tmp)); 728 } 729 730 for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator 731 I = Queue.begin(), E = Queue.end(); I != E; ++I) 732 diff(I->first, I->second); 733} 734 735bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) { 736 if (globalValueOracle) return (*globalValueOracle)(L, R); 737 738 if (isa<GlobalVariable>(L) && isa<GlobalVariable>(R)) { 739 GlobalVariable *GVL = cast<GlobalVariable>(L); 740 GlobalVariable *GVR = cast<GlobalVariable>(R); 741 if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() && 742 GVR->hasLocalLinkage() && GVR->hasUniqueInitializer()) 743 return GVL->getInitializer() == GVR->getInitializer(); 744 } 745 746 return L->getName() == R->getName(); 747} 748