tools/llvm-diff/DifferenceEngine.cpp

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