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