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/Constants.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/Module.h"
25#include "llvm/Support/CFG.h"
26#include "llvm/Support/CallSite.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    llvm::SmallVector<std::pair<Instruction*,Instruction*>, 20> TentativePairs;
199
200    do {
201      assert(LI != LE && RI != R->end());
202      Instruction *LeftI = &*LI, *RightI = &*RI;
203
204      // If the instructions differ, start the more sophisticated diff
205      // algorithm at the start of the block.
206      if (diff(LeftI, RightI, false, false)) {
207        TentativeValues.clear();
208        return runBlockDiff(L->begin(), R->begin());
209      }
210
211      // Otherwise, tentatively unify them.
212      if (!LeftI->use_empty())
213        TentativeValues.insert(std::make_pair(LeftI, RightI));
214
215      ++LI, ++RI;
216    } while (LI != LE); // This is sufficient: we can't get equality of
217                        // terminators if there are residual instructions.
218
219    // Unify everything in the block, non-tentatively this time.
220    TentativeValues.clear();
221    for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
222      unify(&*LI, &*RI);
223  }
224
225  bool matchForBlockDiff(Instruction *L, Instruction *R);
226  void runBlockDiff(BasicBlock::iterator LI, BasicBlock::iterator RI);
227
228  bool diffCallSites(CallSite L, CallSite R, bool Complain) {
229    // FIXME: call attributes
230    if (!equivalentAsOperands(L.getCalledValue(), R.getCalledValue())) {
231      if (Complain) Engine.log("called functions differ");
232      return true;
233    }
234    if (L.arg_size() != R.arg_size()) {
235      if (Complain) Engine.log("argument counts differ");
236      return true;
237    }
238    for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
239      if (!equivalentAsOperands(L.getArgument(I), R.getArgument(I))) {
240        if (Complain)
241          Engine.logf("arguments %l and %r differ")
242            << L.getArgument(I) << R.getArgument(I);
243        return true;
244      }
245    return false;
246  }
247
248  bool diff(Instruction *L, Instruction *R, bool Complain, bool TryUnify) {
249    // FIXME: metadata (if Complain is set)
250
251    // Different opcodes always imply different operations.
252    if (L->getOpcode() != R->getOpcode()) {
253      if (Complain) Engine.log("different instruction types");
254      return true;
255    }
256
257    if (isa<CmpInst>(L)) {
258      if (cast<CmpInst>(L)->getPredicate()
259            != cast<CmpInst>(R)->getPredicate()) {
260        if (Complain) Engine.log("different predicates");
261        return true;
262      }
263    } else if (isa<CallInst>(L)) {
264      return diffCallSites(CallSite(L), CallSite(R), Complain);
265    } else if (isa<PHINode>(L)) {
266      // FIXME: implement.
267
268      // This is really weird;  type uniquing is broken?
269      if (L->getType() != R->getType()) {
270        if (!L->getType()->isPointerTy() || !R->getType()->isPointerTy()) {
271          if (Complain) Engine.log("different phi types");
272          return true;
273        }
274      }
275      return false;
276
277    // Terminators.
278    } else if (isa<InvokeInst>(L)) {
279      InvokeInst *LI = cast<InvokeInst>(L);
280      InvokeInst *RI = cast<InvokeInst>(R);
281      if (diffCallSites(CallSite(LI), CallSite(RI), Complain))
282        return true;
283
284      if (TryUnify) {
285        tryUnify(LI->getNormalDest(), RI->getNormalDest());
286        tryUnify(LI->getUnwindDest(), RI->getUnwindDest());
287      }
288      return false;
289
290    } else if (isa<BranchInst>(L)) {
291      BranchInst *LI = cast<BranchInst>(L);
292      BranchInst *RI = cast<BranchInst>(R);
293      if (LI->isConditional() != RI->isConditional()) {
294        if (Complain) Engine.log("branch conditionality differs");
295        return true;
296      }
297
298      if (LI->isConditional()) {
299        if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
300          if (Complain) Engine.log("branch conditions differ");
301          return true;
302        }
303        if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1));
304      }
305      if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0));
306      return false;
307
308    } else if (isa<SwitchInst>(L)) {
309      SwitchInst *LI = cast<SwitchInst>(L);
310      SwitchInst *RI = cast<SwitchInst>(R);
311      if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
312        if (Complain) Engine.log("switch conditions differ");
313        return true;
314      }
315      if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest());
316
317      bool Difference = false;
318
319      DenseMap<Constant*, BasicBlock*> LCases;
320
321      for (SwitchInst::CaseIt I = LI->case_begin(), E = LI->case_end();
322           I != E; ++I)
323        LCases[I.getCaseValueEx()] = I.getCaseSuccessor();
324
325      for (SwitchInst::CaseIt I = RI->case_begin(), E = RI->case_end();
326           I != E; ++I) {
327        IntegersSubset CaseValue = I.getCaseValueEx();
328        BasicBlock *LCase = LCases[CaseValue];
329        if (LCase) {
330          if (TryUnify) tryUnify(LCase, I.getCaseSuccessor());
331          LCases.erase(CaseValue);
332        } else if (Complain || !Difference) {
333          if (Complain)
334            Engine.logf("right switch has extra case %r") << CaseValue;
335          Difference = true;
336        }
337      }
338      if (!Difference)
339        for (DenseMap<Constant*, BasicBlock*>::iterator
340               I = LCases.begin(), E = LCases.end(); I != E; ++I) {
341          if (Complain)
342            Engine.logf("left switch has extra case %l") << I->first;
343          Difference = true;
344        }
345      return Difference;
346    } else if (isa<UnreachableInst>(L)) {
347      return false;
348    }
349
350    if (L->getNumOperands() != R->getNumOperands()) {
351      if (Complain) Engine.log("instructions have different operand counts");
352      return true;
353    }
354
355    for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
356      Value *LO = L->getOperand(I), *RO = R->getOperand(I);
357      if (!equivalentAsOperands(LO, RO)) {
358        if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
359        return true;
360      }
361    }
362
363    return false;
364  }
365
366  bool equivalentAsOperands(Constant *L, Constant *R) {
367    // Use equality as a preliminary filter.
368    if (L == R)
369      return true;
370
371    if (L->getValueID() != R->getValueID())
372      return false;
373
374    // Ask the engine about global values.
375    if (isa<GlobalValue>(L))
376      return Engine.equivalentAsOperands(cast<GlobalValue>(L),
377                                         cast<GlobalValue>(R));
378
379    // Compare constant expressions structurally.
380    if (isa<ConstantExpr>(L))
381      return equivalentAsOperands(cast<ConstantExpr>(L),
382                                  cast<ConstantExpr>(R));
383
384    // Nulls of the "same type" don't always actually have the same
385    // type; I don't know why.  Just white-list them.
386    if (isa<ConstantPointerNull>(L))
387      return true;
388
389    // Block addresses only match if we've already encountered the
390    // block.  FIXME: tentative matches?
391    if (isa<BlockAddress>(L))
392      return Blocks[cast<BlockAddress>(L)->getBasicBlock()]
393                 == cast<BlockAddress>(R)->getBasicBlock();
394
395    return false;
396  }
397
398  bool equivalentAsOperands(ConstantExpr *L, ConstantExpr *R) {
399    if (L == R)
400      return true;
401    if (L->getOpcode() != R->getOpcode())
402      return false;
403
404    switch (L->getOpcode()) {
405    case Instruction::ICmp:
406    case Instruction::FCmp:
407      if (L->getPredicate() != R->getPredicate())
408        return false;
409      break;
410
411    case Instruction::GetElementPtr:
412      // FIXME: inbounds?
413      break;
414
415    default:
416      break;
417    }
418
419    if (L->getNumOperands() != R->getNumOperands())
420      return false;
421
422    for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I)
423      if (!equivalentAsOperands(L->getOperand(I), R->getOperand(I)))
424        return false;
425
426    return true;
427  }
428
429  bool equivalentAsOperands(Value *L, Value *R) {
430    // Fall out if the values have different kind.
431    // This possibly shouldn't take priority over oracles.
432    if (L->getValueID() != R->getValueID())
433      return false;
434
435    // Value subtypes:  Argument, Constant, Instruction, BasicBlock,
436    //                  InlineAsm, MDNode, MDString, PseudoSourceValue
437
438    if (isa<Constant>(L))
439      return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
440
441    if (isa<Instruction>(L))
442      return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
443
444    if (isa<Argument>(L))
445      return Values[L] == R;
446
447    if (isa<BasicBlock>(L))
448      return Blocks[cast<BasicBlock>(L)] != R;
449
450    // Pretend everything else is identical.
451    return true;
452  }
453
454  // Avoid a gcc warning about accessing 'this' in an initializer.
455  FunctionDifferenceEngine *this_() { return this; }
456
457public:
458  FunctionDifferenceEngine(DifferenceEngine &Engine) :
459    Engine(Engine), Queue(QueueSorter(*this_())) {}
460
461  void diff(Function *L, Function *R) {
462    if (L->arg_size() != R->arg_size())
463      Engine.log("different argument counts");
464
465    // Map the arguments.
466    for (Function::arg_iterator
467           LI = L->arg_begin(), LE = L->arg_end(),
468           RI = R->arg_begin(), RE = R->arg_end();
469         LI != LE && RI != RE; ++LI, ++RI)
470      Values[&*LI] = &*RI;
471
472    tryUnify(&*L->begin(), &*R->begin());
473    processQueue();
474  }
475};
476
477struct DiffEntry {
478  DiffEntry() : Cost(0) {}
479
480  unsigned Cost;
481  llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
482};
483
484bool FunctionDifferenceEngine::matchForBlockDiff(Instruction *L,
485                                                 Instruction *R) {
486  return !diff(L, R, false, false);
487}
488
489void FunctionDifferenceEngine::runBlockDiff(BasicBlock::iterator LStart,
490                                            BasicBlock::iterator RStart) {
491  BasicBlock::iterator LE = LStart->getParent()->end();
492  BasicBlock::iterator RE = RStart->getParent()->end();
493
494  unsigned NL = std::distance(LStart, LE);
495
496  SmallVector<DiffEntry, 20> Paths1(NL+1);
497  SmallVector<DiffEntry, 20> Paths2(NL+1);
498
499  DiffEntry *Cur = Paths1.data();
500  DiffEntry *Next = Paths2.data();
501
502  const unsigned LeftCost = 2;
503  const unsigned RightCost = 2;
504  const unsigned MatchCost = 0;
505
506  assert(TentativeValues.empty());
507
508  // Initialize the first column.
509  for (unsigned I = 0; I != NL+1; ++I) {
510    Cur[I].Cost = I * LeftCost;
511    for (unsigned J = 0; J != I; ++J)
512      Cur[I].Path.push_back(DC_left);
513  }
514
515  for (BasicBlock::iterator RI = RStart; RI != RE; ++RI) {
516    // Initialize the first row.
517    Next[0] = Cur[0];
518    Next[0].Cost += RightCost;
519    Next[0].Path.push_back(DC_right);
520
521    unsigned Index = 1;
522    for (BasicBlock::iterator LI = LStart; LI != LE; ++LI, ++Index) {
523      if (matchForBlockDiff(&*LI, &*RI)) {
524        Next[Index] = Cur[Index-1];
525        Next[Index].Cost += MatchCost;
526        Next[Index].Path.push_back(DC_match);
527        TentativeValues.insert(std::make_pair(&*LI, &*RI));
528      } else if (Next[Index-1].Cost <= Cur[Index].Cost) {
529        Next[Index] = Next[Index-1];
530        Next[Index].Cost += LeftCost;
531        Next[Index].Path.push_back(DC_left);
532      } else {
533        Next[Index] = Cur[Index];
534        Next[Index].Cost += RightCost;
535        Next[Index].Path.push_back(DC_right);
536      }
537    }
538
539    std::swap(Cur, Next);
540  }
541
542  // We don't need the tentative values anymore; everything from here
543  // on out should be non-tentative.
544  TentativeValues.clear();
545
546  SmallVectorImpl<char> &Path = Cur[NL].Path;
547  BasicBlock::iterator LI = LStart, RI = RStart;
548
549  DiffLogBuilder Diff(Engine.getConsumer());
550
551  // Drop trailing matches.
552  while (Path.back() == DC_match)
553    Path.pop_back();
554
555  // Skip leading matches.
556  SmallVectorImpl<char>::iterator
557    PI = Path.begin(), PE = Path.end();
558  while (PI != PE && *PI == DC_match) {
559    unify(&*LI, &*RI);
560    ++PI, ++LI, ++RI;
561  }
562
563  for (; PI != PE; ++PI) {
564    switch (static_cast<DiffChange>(*PI)) {
565    case DC_match:
566      assert(LI != LE && RI != RE);
567      {
568        Instruction *L = &*LI, *R = &*RI;
569        unify(L, R);
570        Diff.addMatch(L, R);
571      }
572      ++LI; ++RI;
573      break;
574
575    case DC_left:
576      assert(LI != LE);
577      Diff.addLeft(&*LI);
578      ++LI;
579      break;
580
581    case DC_right:
582      assert(RI != RE);
583      Diff.addRight(&*RI);
584      ++RI;
585      break;
586    }
587  }
588
589  // Finishing unifying and complaining about the tails of the block,
590  // which should be matches all the way through.
591  while (LI != LE) {
592    assert(RI != RE);
593    unify(&*LI, &*RI);
594    ++LI, ++RI;
595  }
596
597  // If the terminators have different kinds, but one is an invoke and the
598  // other is an unconditional branch immediately following a call, unify
599  // the results and the destinations.
600  TerminatorInst *LTerm = LStart->getParent()->getTerminator();
601  TerminatorInst *RTerm = RStart->getParent()->getTerminator();
602  if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
603    if (cast<BranchInst>(LTerm)->isConditional()) return;
604    BasicBlock::iterator I = LTerm;
605    if (I == LStart->getParent()->begin()) return;
606    --I;
607    if (!isa<CallInst>(*I)) return;
608    CallInst *LCall = cast<CallInst>(&*I);
609    InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
610    if (!equivalentAsOperands(LCall->getCalledValue(), RInvoke->getCalledValue()))
611      return;
612    if (!LCall->use_empty())
613      Values[LCall] = RInvoke;
614    tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest());
615  } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) {
616    if (cast<BranchInst>(RTerm)->isConditional()) return;
617    BasicBlock::iterator I = RTerm;
618    if (I == RStart->getParent()->begin()) return;
619    --I;
620    if (!isa<CallInst>(*I)) return;
621    CallInst *RCall = cast<CallInst>(I);
622    InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
623    if (!equivalentAsOperands(LInvoke->getCalledValue(), RCall->getCalledValue()))
624      return;
625    if (!LInvoke->use_empty())
626      Values[LInvoke] = RCall;
627    tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
628  }
629}
630
631}
632
633void DifferenceEngine::Oracle::anchor() { }
634
635void DifferenceEngine::diff(Function *L, Function *R) {
636  Context C(*this, L, R);
637
638  // FIXME: types
639  // FIXME: attributes and CC
640  // FIXME: parameter attributes
641
642  // If both are declarations, we're done.
643  if (L->empty() && R->empty())
644    return;
645  else if (L->empty())
646    log("left function is declaration, right function is definition");
647  else if (R->empty())
648    log("right function is declaration, left function is definition");
649  else
650    FunctionDifferenceEngine(*this).diff(L, R);
651}
652
653void DifferenceEngine::diff(Module *L, Module *R) {
654  StringSet<> LNames;
655  SmallVector<std::pair<Function*,Function*>, 20> Queue;
656
657  for (Module::iterator I = L->begin(), E = L->end(); I != E; ++I) {
658    Function *LFn = &*I;
659    LNames.insert(LFn->getName());
660
661    if (Function *RFn = R->getFunction(LFn->getName()))
662      Queue.push_back(std::make_pair(LFn, RFn));
663    else
664      logf("function %l exists only in left module") << LFn;
665  }
666
667  for (Module::iterator I = R->begin(), E = R->end(); I != E; ++I) {
668    Function *RFn = &*I;
669    if (!LNames.count(RFn->getName()))
670      logf("function %r exists only in right module") << RFn;
671  }
672
673  for (SmallVectorImpl<std::pair<Function*,Function*> >::iterator
674         I = Queue.begin(), E = Queue.end(); I != E; ++I)
675    diff(I->first, I->second);
676}
677
678bool DifferenceEngine::equivalentAsOperands(GlobalValue *L, GlobalValue *R) {
679  if (globalValueOracle) return (*globalValueOracle)(L, R);
680  return L->getName() == R->getName();
681}
682