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/StringExtras.h"
20#include "llvm/ADT/StringSet.h"
21#include "llvm/IR/BasicBlock.h"
22#include "llvm/IR/CFG.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 <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 (std::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/// Returns the attributes of \p A that \p B does not have with the same value.
113static std::string getAttributesNotIn(AttributeSet A, AttributeSet B) {
114 SmallVector<std::string, 4> Result;
115 for (Attribute Attr : A) {
116 Attribute Other = Attr.isStringAttribute()
117 ? B.getAttribute(Kind: Attr.getKindAsString())
118 : B.getAttribute(Kind: Attr.getKindAsEnum());
119 if (Attr != Other)
120 Result.push_back(Elt: Attr.getAsString());
121 }
122 return join(R&: Result, Separator: ", ");
123}
124
125/// Compares the function, return and parameter attributes of \p L and \p R.
126/// Logs the attributes that are on only one side if \p Complain is set.
127/// Returns true if they differ.
128static bool diffAttributes(DifferenceEngine &Engine, StringRef Prefix,
129 AttributeList L, AttributeList R, unsigned NumParams,
130 bool Complain) {
131 bool Differ = false;
132 auto DiffSlot = [&](const Twine &Slot, AttributeSet LS, AttributeSet RS) {
133 if (LS == RS)
134 return;
135 Differ = true;
136 if (!Complain)
137 return;
138 Engine.log(text: (Prefix + Slot + " attributes differ:").str());
139 std::string LeftOnly = getAttributesNotIn(A: LS, B: RS);
140 std::string RightOnly = getAttributesNotIn(A: RS, B: LS);
141 if (!LeftOnly.empty())
142 Engine.log(text: " < " + LeftOnly);
143 if (!RightOnly.empty())
144 Engine.log(text: " > " + RightOnly);
145 };
146 DiffSlot("function", L.getFnAttrs(), R.getFnAttrs());
147 DiffSlot("return", L.getRetAttrs(), R.getRetAttrs());
148 for (unsigned I = 0; I != NumParams; ++I)
149 DiffSlot("parameter " + Twine(I), L.getParamAttrs(ArgNo: I), R.getParamAttrs(ArgNo: I));
150 return Differ;
151}
152
153/// Returns true if \p L and \p R, which have the same opcode, have different
154/// poison-generating flags.
155static bool hasDifferentFlags(const Instruction *L, const Instruction *R) {
156 return L->getRawSubclassOptionalData() != R->getRawSubclassOptionalData() ||
157 L->getFastMathFlagsOrNone() != R->getFastMathFlagsOrNone();
158}
159
160/// A function-scope difference engine.
161class FunctionDifferenceEngine {
162 DifferenceEngine &Engine;
163
164 // Some initializers may reference the variable we're currently checking. This
165 // can cause an infinite loop. The Saved[LR]HS ivars can be checked to prevent
166 // recursing.
167 const Value *SavedLHS;
168 const Value *SavedRHS;
169
170 // The current mapping from old local values to new local values.
171 DenseMap<const Value *, const Value *> Values;
172
173 // The current mapping from old blocks to new blocks.
174 DenseMap<const BasicBlock *, const BasicBlock *> Blocks;
175
176 // The tentative mapping from old local values while comparing a pair of
177 // basic blocks. Once the pair has been processed, the tentative mapping is
178 // committed to the Values map.
179 DenseSet<std::pair<const Value *, const Value *>> TentativeValues;
180
181 // Equivalence Assumptions
182 //
183 // For basic blocks in loops, some values in phi nodes may depend on
184 // values from not yet processed basic blocks in the loop. When encountering
185 // such values, we optimistically asssume their equivalence and store this
186 // assumption in a BlockDiffCandidate for the pair of compared BBs.
187 //
188 // Once we have diffed all BBs, for every BlockDiffCandidate, we check all
189 // stored assumptions using the Values map that stores proven equivalences
190 // between the old and new values, and report a diff if an assumption cannot
191 // be proven to be true.
192 //
193 // Note that after having made an assumption, all further determined
194 // equivalences implicitly depend on that assumption. These will not be
195 // reverted or reported if the assumption proves to be false, because these
196 // are considered indirect diffs caused by earlier direct diffs.
197 //
198 // We aim to avoid false negatives in llvm-diff, that is, ensure that
199 // whenever no diff is reported, the functions are indeed equal. If
200 // assumptions were made, this is not entirely clear, because in principle we
201 // could end up with a circular proof where the proof of equivalence of two
202 // nodes is depending on the assumption of their equivalence.
203 //
204 // To see that assumptions do not add false negatives, note that if we do not
205 // report a diff, this means that there is an equivalence mapping between old
206 // and new values that is consistent with all assumptions made. The circular
207 // dependency that exists on an IR value level does not exist at run time,
208 // because the values selected by the phi nodes must always already have been
209 // computed. Hence, we can prove equivalence of the old and new functions by
210 // considering step-wise parallel execution, and incrementally proving
211 // equivalence of every new computed value. Another way to think about it is
212 // to imagine cloning the loop BBs for every iteration, turning the loops
213 // into (possibly infinite) DAGs, and proving equivalence by induction on the
214 // iteration, using the computed value mapping.
215
216 // The class BlockDiffCandidate stores pairs which either have already been
217 // proven to differ, or pairs whose equivalence depends on assumptions to be
218 // verified later.
219 struct BlockDiffCandidate {
220 const BasicBlock *LBB;
221 const BasicBlock *RBB;
222 // Maps old values to assumed-to-be-equivalent new values
223 SmallDenseMap<const Value *, const Value *> EquivalenceAssumptions;
224 // If set, we already know the blocks differ.
225 bool KnownToDiffer;
226 };
227
228 // List of block diff candidates in the order found by processing.
229 // We generate reports in this order.
230 // For every LBB, there may only be one corresponding RBB.
231 SmallVector<BlockDiffCandidate> BlockDiffCandidates;
232 // Maps LBB to the index of its BlockDiffCandidate, if existing.
233 DenseMap<const BasicBlock *, uint64_t> BlockDiffCandidateIndices;
234
235 // Note: Every LBB must always be queried together with the same RBB.
236 // The returned reference is not permanently valid and should not be stored.
237 BlockDiffCandidate &getOrCreateBlockDiffCandidate(const BasicBlock *LBB,
238 const BasicBlock *RBB) {
239 auto [It, Inserted] =
240 BlockDiffCandidateIndices.try_emplace(Key: LBB, Args: BlockDiffCandidates.size());
241 // Check if LBB already has a diff candidate
242 if (Inserted) {
243 // Add new one
244 BlockDiffCandidates.push_back(
245 Elt: {.LBB: LBB, .RBB: RBB, .EquivalenceAssumptions: SmallDenseMap<const Value *, const Value *>(), .KnownToDiffer: false});
246 return BlockDiffCandidates.back();
247 }
248 // Use existing one
249 BlockDiffCandidate &Result = BlockDiffCandidates[It->second];
250 assert(Result.RBB == RBB && "Inconsistent basic block pairing!");
251 return Result;
252 }
253
254 // Optionally passed to equivalence checker functions, so these can add
255 // assumptions in BlockDiffCandidates. Its presence controls whether
256 // assumptions are generated.
257 struct AssumptionContext {
258 // The two basic blocks that need the two compared values to be equivalent.
259 const BasicBlock *LBB;
260 const BasicBlock *RBB;
261 };
262
263 unsigned getUnprocPredCount(const BasicBlock *Block) const {
264 return llvm::count_if(Range: predecessors(BB: Block), P: [&](const BasicBlock *Pred) {
265 return !Blocks.contains(Val: Pred);
266 });
267 }
268
269 typedef std::pair<const BasicBlock *, const BasicBlock *> BlockPair;
270
271 /// A type which sorts a priority queue by the number of unprocessed
272 /// predecessor blocks it has remaining.
273 ///
274 /// This is actually really expensive to calculate.
275 struct QueueSorter {
276 const FunctionDifferenceEngine &fde;
277 explicit QueueSorter(const FunctionDifferenceEngine &fde) : fde(fde) {}
278
279 bool operator()(BlockPair &Old, BlockPair &New) {
280 return fde.getUnprocPredCount(Block: Old.first)
281 < fde.getUnprocPredCount(Block: New.first);
282 }
283 };
284
285 /// A queue of unified blocks to process.
286 PriorityQueue<BlockPair, QueueSorter, 20> Queue;
287
288 /// Try to unify the given two blocks. Enqueues them for processing
289 /// if they haven't already been processed.
290 ///
291 /// Returns true if there was a problem unifying them.
292 bool tryUnify(const BasicBlock *L, const BasicBlock *R) {
293 const BasicBlock *&Ref = Blocks[L];
294
295 if (Ref) {
296 if (Ref == R) return false;
297
298 Engine.logf(text: "successor %l cannot be equivalent to %r; "
299 "it's already equivalent to %r")
300 << L << R << Ref;
301 return true;
302 }
303
304 Ref = R;
305 Queue.insert(V: BlockPair(L, R));
306 return false;
307 }
308
309 /// Unifies two instructions, given that they're known not to have
310 /// structural differences.
311 void unify(const Instruction *L, const Instruction *R) {
312 DifferenceEngine::Context C(Engine, L, R);
313
314 bool Result = diff(L, R, Complain: true, TryUnify: true, AllowAssumptions: true);
315 assert(!Result && "structural differences second time around?");
316 (void) Result;
317 if (!L->use_empty())
318 Values[L] = R;
319 }
320
321 void processQueue() {
322 while (!Queue.empty()) {
323 BlockPair Pair = Queue.remove_min();
324 diff(L: Pair.first, R: Pair.second);
325 }
326 }
327
328 void checkAndReportDiffCandidates() {
329 for (BlockDiffCandidate &BDC : BlockDiffCandidates) {
330
331 // Check assumptions
332 for (const auto &[L, R] : BDC.EquivalenceAssumptions) {
333 auto It = Values.find(Val: L);
334 if (It == Values.end() || It->second != R) {
335 BDC.KnownToDiffer = true;
336 break;
337 }
338 }
339
340 // Run block diff if the BBs differ
341 if (BDC.KnownToDiffer) {
342 DifferenceEngine::Context C(Engine, BDC.LBB, BDC.RBB);
343 runBlockDiff(LI: BDC.LBB->begin(), RI: BDC.RBB->begin());
344 }
345 }
346 }
347
348 void diff(const BasicBlock *L, const BasicBlock *R) {
349 DifferenceEngine::Context C(Engine, L, R);
350
351 BasicBlock::const_iterator LI = L->begin(), LE = L->end();
352 BasicBlock::const_iterator RI = R->begin();
353
354 do {
355 assert(LI != LE && RI != R->end());
356 const Instruction *LeftI = &*LI, *RightI = &*RI;
357
358 // If the instructions differ, start the more sophisticated diff
359 // algorithm at the start of the block.
360 if (diff(L: LeftI, R: RightI, Complain: false, TryUnify: false, AllowAssumptions: true)) {
361 TentativeValues.clear();
362 // Register (L, R) as diffing pair. Note that we could directly emit a
363 // block diff here, but this way we ensure all diffs are emitted in one
364 // consistent order, independent of whether the diffs were detected
365 // immediately or via invalid assumptions.
366 getOrCreateBlockDiffCandidate(LBB: L, RBB: R).KnownToDiffer = true;
367 return;
368 }
369
370 // Otherwise, tentatively unify them.
371 if (!LeftI->use_empty())
372 TentativeValues.insert(V: std::make_pair(x&: LeftI, y&: RightI));
373
374 ++LI;
375 ++RI;
376 } while (LI != LE); // This is sufficient: we can't get equality of
377 // terminators if there are residual instructions.
378
379 // Unify everything in the block, non-tentatively this time.
380 TentativeValues.clear();
381 for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
382 unify(L: &*LI, R: &*RI);
383 }
384
385 bool matchForBlockDiff(const Instruction *L, const Instruction *R);
386 void runBlockDiff(BasicBlock::const_iterator LI,
387 BasicBlock::const_iterator RI);
388
389 bool diffCallSites(const CallBase &L, const CallBase &R, bool Complain,
390 const AssumptionContext *AC) {
391 if (!equivalentAsOperands(L: L.getCalledOperand(), R: R.getCalledOperand(), AC)) {
392 if (Complain) Engine.log(text: "called functions differ");
393 return true;
394 }
395 if (L.arg_size() != R.arg_size()) {
396 if (Complain) Engine.log(text: "argument counts differ");
397 return true;
398 }
399 for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
400 if (!equivalentAsOperands(L: L.getArgOperand(i: I), R: R.getArgOperand(i: I), AC)) {
401 if (Complain)
402 Engine.logf(text: "arguments %l and %r differ")
403 << L.getArgOperand(i: I) << R.getArgOperand(i: I);
404 return true;
405 }
406 bool Differ = L.getCallingConv() != R.getCallingConv();
407 if (Differ && Complain)
408 Engine.log(text: "calling conventions differ");
409 Differ |= diffAttributes(Engine, Prefix: "call ", L: L.getAttributes(),
410 R: R.getAttributes(), NumParams: L.arg_size(), Complain);
411 return Differ;
412 }
413
414 // If AllowAssumptions is enabled, whenever we encounter a pair of values
415 // that we cannot prove to be equivalent, we assume equivalence and store that
416 // assumption to be checked later in BlockDiffCandidates.
417 bool diff(const Instruction *L, const Instruction *R, bool Complain,
418 bool TryUnify, bool AllowAssumptions) {
419 // FIXME: metadata (if Complain is set)
420 AssumptionContext ACValue = {.LBB: L->getParent(), .RBB: R->getParent()};
421 // nullptr AssumptionContext disables assumption generation.
422 const AssumptionContext *AC = AllowAssumptions ? &ACValue : nullptr;
423
424 // Different opcodes always imply different operations.
425 if (L->getOpcode() != R->getOpcode()) {
426 if (Complain) Engine.log(text: "different instruction types");
427 return true;
428 }
429
430 if (hasDifferentFlags(L, R)) {
431 if (Complain)
432 Engine.log(text: "different instruction flags");
433 return true;
434 }
435
436 if (isa<CmpInst>(Val: L)) {
437 if (cast<CmpInst>(Val: L)->getPredicate()
438 != cast<CmpInst>(Val: R)->getPredicate()) {
439 if (Complain) Engine.log(text: "different predicates");
440 return true;
441 }
442 } else if (isa<CallInst>(Val: L)) {
443 return diffCallSites(L: cast<CallInst>(Val: *L), R: cast<CallInst>(Val: *R), Complain,
444 AC);
445 } else if (isa<PHINode>(Val: L)) {
446 const PHINode &LI = cast<PHINode>(Val: *L);
447 const PHINode &RI = cast<PHINode>(Val: *R);
448
449 // This is really weird; type uniquing is broken?
450 if (LI.getType() != RI.getType()) {
451 if (!LI.getType()->isPointerTy() || !RI.getType()->isPointerTy()) {
452 if (Complain) Engine.log(text: "different phi types");
453 return true;
454 }
455 }
456
457 if (LI.getNumIncomingValues() != RI.getNumIncomingValues()) {
458 if (Complain)
459 Engine.log(text: "PHI node # of incoming values differ");
460 return true;
461 }
462
463 for (unsigned I = 0; I < LI.getNumIncomingValues(); ++I) {
464 if (TryUnify)
465 tryUnify(L: LI.getIncomingBlock(i: I), R: RI.getIncomingBlock(i: I));
466
467 if (!equivalentAsOperands(L: LI.getIncomingValue(i: I),
468 R: RI.getIncomingValue(i: I), AC)) {
469 if (Complain)
470 Engine.log(text: "PHI node incoming values differ");
471 return true;
472 }
473 }
474
475 return false;
476
477 // Terminators.
478 } else if (isa<InvokeInst>(Val: L)) {
479 const InvokeInst &LI = cast<InvokeInst>(Val: *L);
480 const InvokeInst &RI = cast<InvokeInst>(Val: *R);
481 if (diffCallSites(L: LI, R: RI, Complain, AC))
482 return true;
483
484 if (TryUnify) {
485 tryUnify(L: LI.getNormalDest(), R: RI.getNormalDest());
486 tryUnify(L: LI.getUnwindDest(), R: RI.getUnwindDest());
487 }
488 return false;
489
490 } else if (isa<CallBrInst>(Val: L)) {
491 const CallBrInst &LI = cast<CallBrInst>(Val: *L);
492 const CallBrInst &RI = cast<CallBrInst>(Val: *R);
493 if (LI.getNumIndirectDests() != RI.getNumIndirectDests()) {
494 if (Complain)
495 Engine.log(text: "callbr # of indirect destinations differ");
496 return true;
497 }
498
499 // Perform the "try unify" step so that we can equate the indirect
500 // destinations before checking the call site.
501 for (unsigned I = 0; I < LI.getNumIndirectDests(); I++)
502 tryUnify(L: LI.getIndirectDest(i: I), R: RI.getIndirectDest(i: I));
503
504 if (diffCallSites(L: LI, R: RI, Complain, AC))
505 return true;
506
507 if (TryUnify)
508 tryUnify(L: LI.getDefaultDest(), R: RI.getDefaultDest());
509 return false;
510
511 } else if (isa<UncondBrInst>(Val: L)) {
512 if (TryUnify)
513 tryUnify(L: L->getSuccessor(Idx: 0), R: R->getSuccessor(Idx: 0));
514 return false;
515
516 } else if (isa<CondBrInst>(Val: L)) {
517 const CondBrInst *LI = cast<CondBrInst>(Val: L);
518 const CondBrInst *RI = cast<CondBrInst>(Val: R);
519 if (!equivalentAsOperands(L: LI->getCondition(), R: RI->getCondition(), AC)) {
520 if (Complain)
521 Engine.log(text: "branch conditions differ");
522 return true;
523 }
524 if (TryUnify)
525 tryUnify(L: LI->getSuccessor(i: 1), R: RI->getSuccessor(i: 1));
526 if (TryUnify) tryUnify(L: LI->getSuccessor(i: 0), R: RI->getSuccessor(i: 0));
527 return false;
528
529 } else if (isa<IndirectBrInst>(Val: L)) {
530 const IndirectBrInst *LI = cast<IndirectBrInst>(Val: L);
531 const IndirectBrInst *RI = cast<IndirectBrInst>(Val: R);
532 if (LI->getNumDestinations() != RI->getNumDestinations()) {
533 if (Complain) Engine.log(text: "indirectbr # of destinations differ");
534 return true;
535 }
536
537 if (!equivalentAsOperands(L: LI->getAddress(), R: RI->getAddress(), AC)) {
538 if (Complain) Engine.log(text: "indirectbr addresses differ");
539 return true;
540 }
541
542 if (TryUnify) {
543 for (unsigned i = 0; i < LI->getNumDestinations(); i++) {
544 tryUnify(L: LI->getDestination(i), R: RI->getDestination(i));
545 }
546 }
547 return false;
548
549 } else if (isa<SwitchInst>(Val: L)) {
550 const SwitchInst *LI = cast<SwitchInst>(Val: L);
551 const SwitchInst *RI = cast<SwitchInst>(Val: R);
552 if (!equivalentAsOperands(L: LI->getCondition(), R: RI->getCondition(), AC)) {
553 if (Complain) Engine.log(text: "switch conditions differ");
554 return true;
555 }
556 if (TryUnify) tryUnify(L: LI->getDefaultDest(), R: RI->getDefaultDest());
557
558 bool Difference = false;
559
560 DenseMap<const ConstantInt *, const BasicBlock *> LCases;
561 for (auto Case : LI->cases())
562 LCases[Case.getCaseValue()] = Case.getCaseSuccessor();
563
564 for (auto Case : RI->cases()) {
565 const ConstantInt *CaseValue = Case.getCaseValue();
566 const BasicBlock *LCase = LCases[CaseValue];
567 if (LCase) {
568 if (TryUnify)
569 tryUnify(L: LCase, R: Case.getCaseSuccessor());
570 LCases.erase(Val: CaseValue);
571 } else if (Complain || !Difference) {
572 if (Complain)
573 Engine.logf(text: "right switch has extra case %r") << CaseValue;
574 Difference = true;
575 }
576 }
577 if (!Difference)
578 for (DenseMap<const ConstantInt *, const BasicBlock *>::iterator
579 I = LCases.begin(),
580 E = LCases.end();
581 I != E; ++I) {
582 if (Complain)
583 Engine.logf(text: "left switch has extra case %l") << I->first;
584 Difference = true;
585 }
586 return Difference;
587 } else if (isa<UnreachableInst>(Val: L)) {
588 return false;
589 }
590
591 if (L->getNumOperands() != R->getNumOperands()) {
592 if (Complain) Engine.log(text: "instructions have different operand counts");
593 return true;
594 }
595
596 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
597 Value *LO = L->getOperand(i: I), *RO = R->getOperand(i: I);
598 if (!equivalentAsOperands(L: LO, R: RO, AC)) {
599 if (Complain) Engine.logf(text: "operands %l and %r differ") << LO << RO;
600 return true;
601 }
602 }
603
604 return false;
605 }
606
607public:
608 bool equivalentAsOperands(const Constant *L, const Constant *R,
609 const AssumptionContext *AC) {
610 // Use equality as a preliminary filter.
611 if (L == R)
612 return true;
613
614 if (L->getValueID() != R->getValueID())
615 return false;
616
617 // Ask the engine about global values.
618 if (isa<GlobalValue>(Val: L))
619 return Engine.equivalentAsOperands(L: cast<GlobalValue>(Val: L),
620 R: cast<GlobalValue>(Val: R));
621
622 // Compare constant expressions structurally.
623 if (isa<ConstantExpr>(Val: L))
624 return equivalentAsOperands(L: cast<ConstantExpr>(Val: L), R: cast<ConstantExpr>(Val: R),
625 AC);
626
627 // Constants of the "same type" don't always actually have the same
628 // type; I don't know why. Just white-list them.
629 if (isa<ConstantPointerNull>(Val: L) || isa<UndefValue>(Val: L) || isa<ConstantAggregateZero>(Val: L))
630 return true;
631
632 // Block addresses only match if we've already encountered the
633 // block. FIXME: tentative matches?
634 if (isa<BlockAddress>(Val: L))
635 return Blocks[cast<BlockAddress>(Val: L)->getBasicBlock()]
636 == cast<BlockAddress>(Val: R)->getBasicBlock();
637
638 // If L and R are ConstantVectors, compare each element
639 if (isa<ConstantVector>(Val: L)) {
640 const ConstantVector *CVL = cast<ConstantVector>(Val: L);
641 const ConstantVector *CVR = cast<ConstantVector>(Val: R);
642 if (CVL->getType()->getNumElements() != CVR->getType()->getNumElements())
643 return false;
644 for (unsigned i = 0; i < CVL->getType()->getNumElements(); i++) {
645 if (!equivalentAsOperands(L: CVL->getOperand(i_nocapture: i), R: CVR->getOperand(i_nocapture: i), AC))
646 return false;
647 }
648 return true;
649 }
650
651 // If L and R are ConstantArrays, compare the element count and types.
652 if (isa<ConstantArray>(Val: L)) {
653 const ConstantArray *CAL = cast<ConstantArray>(Val: L);
654 const ConstantArray *CAR = cast<ConstantArray>(Val: R);
655 // Sometimes a type may be equivalent, but not uniquified---e.g. it may
656 // contain a GEP instruction. Do a deeper comparison of the types.
657 if (CAL->getType()->getNumElements() != CAR->getType()->getNumElements())
658 return false;
659
660 for (unsigned I = 0; I < CAL->getType()->getNumElements(); ++I) {
661 if (!equivalentAsOperands(L: CAL->getAggregateElement(Elt: I),
662 R: CAR->getAggregateElement(Elt: I), AC))
663 return false;
664 }
665
666 return true;
667 }
668
669 // If L and R are ConstantStructs, compare each field and type.
670 if (isa<ConstantStruct>(Val: L)) {
671 const ConstantStruct *CSL = cast<ConstantStruct>(Val: L);
672 const ConstantStruct *CSR = cast<ConstantStruct>(Val: R);
673
674 const StructType *LTy = cast<StructType>(Val: CSL->getType());
675 const StructType *RTy = cast<StructType>(Val: CSR->getType());
676
677 // The StructTypes should have the same attributes. Don't use
678 // isLayoutIdentical(), because that just checks the element pointers,
679 // which may not work here.
680 if (LTy->getNumElements() != RTy->getNumElements() ||
681 LTy->isPacked() != RTy->isPacked())
682 return false;
683
684 for (unsigned I = 0; I < LTy->getNumElements(); I++) {
685 const Value *LAgg = CSL->getAggregateElement(Elt: I);
686 const Value *RAgg = CSR->getAggregateElement(Elt: I);
687
688 if (LAgg == SavedLHS || RAgg == SavedRHS) {
689 if (LAgg != SavedLHS || RAgg != SavedRHS)
690 // If the left and right operands aren't both re-analyzing the
691 // variable, then the initialiers don't match, so report "false".
692 // Otherwise, we skip these operands..
693 return false;
694
695 continue;
696 }
697
698 if (!equivalentAsOperands(L: LAgg, R: RAgg, AC)) {
699 return false;
700 }
701 }
702
703 return true;
704 }
705
706 return false;
707 }
708
709 bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R,
710 const AssumptionContext *AC) {
711 if (L == R)
712 return true;
713
714 if (L->getOpcode() != R->getOpcode())
715 return false;
716
717 switch (L->getOpcode()) {
718 case Instruction::GetElementPtr:
719 // FIXME: inbounds?
720 break;
721
722 default:
723 break;
724 }
725
726 if (L->getNumOperands() != R->getNumOperands())
727 return false;
728
729 for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
730 const auto *LOp = L->getOperand(i_nocapture: I);
731 const auto *ROp = R->getOperand(i_nocapture: I);
732
733 if (LOp == SavedLHS || ROp == SavedRHS) {
734 if (LOp != SavedLHS || ROp != SavedRHS)
735 // If the left and right operands aren't both re-analyzing the
736 // variable, then the initialiers don't match, so report "false".
737 // Otherwise, we skip these operands..
738 return false;
739
740 continue;
741 }
742
743 if (!equivalentAsOperands(L: LOp, R: ROp, AC))
744 return false;
745 }
746
747 return true;
748 }
749
750 // There are cases where we cannot determine whether two values are
751 // equivalent, because it depends on not yet processed basic blocks -- see the
752 // documentation on assumptions.
753 //
754 // AC is the context in which we are currently performing a diff.
755 // When we encounter a pair of values for which we can neither prove
756 // equivalence nor the opposite, we do the following:
757 // * If AC is nullptr, we treat the pair as non-equivalent.
758 // * If AC is set, we add an assumption for the basic blocks given by AC,
759 // and treat the pair as equivalent. The assumption is checked later.
760 bool equivalentAsOperands(const Value *L, const Value *R,
761 const AssumptionContext *AC) {
762 // Fall out if the values have different kind.
763 // This possibly shouldn't take priority over oracles.
764 if (L->getValueID() != R->getValueID())
765 return false;
766
767 // Value subtypes: Argument, Constant, Instruction, BasicBlock,
768 // InlineAsm, MDNode, MDString, PseudoSourceValue
769
770 if (isa<Constant>(Val: L))
771 return equivalentAsOperands(L: cast<Constant>(Val: L), R: cast<Constant>(Val: R), AC);
772
773 if (isa<Instruction>(Val: L)) {
774 auto It = Values.find(Val: L);
775 if (It != Values.end())
776 return It->second == R;
777
778 if (TentativeValues.count(V: std::make_pair(x&: L, y&: R)))
779 return true;
780
781 // L and R might be equivalent, this could depend on not yet processed
782 // basic blocks, so we cannot decide here.
783 if (AC) {
784 // Add an assumption, unless there is a conflict with an existing one
785 BlockDiffCandidate &BDC =
786 getOrCreateBlockDiffCandidate(LBB: AC->LBB, RBB: AC->RBB);
787 auto InsertionResult = BDC.EquivalenceAssumptions.insert(KV: {L, R});
788 if (!InsertionResult.second && InsertionResult.first->second != R) {
789 // We already have a conflicting equivalence assumption for L, so at
790 // least one must be wrong, and we know that there is a diff.
791 BDC.KnownToDiffer = true;
792 BDC.EquivalenceAssumptions.clear();
793 return false;
794 }
795 // Optimistically assume equivalence, and check later once all BBs
796 // have been processed.
797 return true;
798 }
799
800 // Assumptions disabled, so pessimistically assume non-equivalence.
801 return false;
802 }
803
804 if (isa<Argument>(Val: L))
805 return Values[L] == R;
806
807 if (isa<BasicBlock>(Val: L))
808 return Blocks[cast<BasicBlock>(Val: L)] != R;
809
810 // Pretend everything else is identical.
811 return true;
812 }
813
814 // Avoid a gcc warning about accessing 'this' in an initializer.
815 FunctionDifferenceEngine *this_() { return this; }
816
817public:
818 FunctionDifferenceEngine(DifferenceEngine &Engine,
819 const Value *SavedLHS = nullptr,
820 const Value *SavedRHS = nullptr)
821 : Engine(Engine), SavedLHS(SavedLHS), SavedRHS(SavedRHS),
822 Queue(QueueSorter(*this_())) {}
823
824 void diff(const Function *L, const Function *R) {
825 assert(Values.empty() && "Multiple diffs per engine are not supported!");
826
827 if (L->arg_size() != R->arg_size())
828 Engine.log(text: "different argument counts");
829
830 // Map the arguments.
831 for (Function::const_arg_iterator LI = L->arg_begin(), LE = L->arg_end(),
832 RI = R->arg_begin(), RE = R->arg_end();
833 LI != LE && RI != RE; ++LI, ++RI)
834 Values[&*LI] = &*RI;
835
836 tryUnify(L: &*L->begin(), R: &*R->begin());
837 processQueue();
838 checkAndReportDiffCandidates();
839 }
840};
841
842struct DiffEntry {
843 DiffEntry() = default;
844
845 unsigned Cost = 0;
846 llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
847};
848
849bool FunctionDifferenceEngine::matchForBlockDiff(const Instruction *L,
850 const Instruction *R) {
851 return !diff(L, R, Complain: false, TryUnify: false, AllowAssumptions: false);
852}
853
854void FunctionDifferenceEngine::runBlockDiff(BasicBlock::const_iterator LStart,
855 BasicBlock::const_iterator RStart) {
856 BasicBlock::const_iterator LE = LStart->getParent()->end();
857 BasicBlock::const_iterator RE = RStart->getParent()->end();
858
859 unsigned NL = std::distance(first: LStart, last: LE);
860
861 SmallVector<DiffEntry, 20> Paths1(NL+1);
862 SmallVector<DiffEntry, 20> Paths2(NL+1);
863
864 DiffEntry *Cur = Paths1.data();
865 DiffEntry *Next = Paths2.data();
866
867 const unsigned LeftCost = 2;
868 const unsigned RightCost = 2;
869 const unsigned MatchCost = 0;
870
871 assert(TentativeValues.empty());
872
873 // Initialize the first column.
874 for (unsigned I = 0; I != NL+1; ++I) {
875 Cur[I].Cost = I * LeftCost;
876 for (unsigned J = 0; J != I; ++J)
877 Cur[I].Path.push_back(Elt: DC_left);
878 }
879
880 for (BasicBlock::const_iterator RI = RStart; RI != RE; ++RI) {
881 // Initialize the first row.
882 Next[0] = Cur[0];
883 Next[0].Cost += RightCost;
884 Next[0].Path.push_back(Elt: DC_right);
885
886 unsigned Index = 1;
887 for (BasicBlock::const_iterator LI = LStart; LI != LE; ++LI, ++Index) {
888 if (matchForBlockDiff(L: &*LI, R: &*RI)) {
889 Next[Index] = Cur[Index-1];
890 Next[Index].Cost += MatchCost;
891 Next[Index].Path.push_back(Elt: DC_match);
892 TentativeValues.insert(V: std::make_pair(x: &*LI, y: &*RI));
893 } else if (Next[Index-1].Cost <= Cur[Index].Cost) {
894 Next[Index] = Next[Index-1];
895 Next[Index].Cost += LeftCost;
896 Next[Index].Path.push_back(Elt: DC_left);
897 } else {
898 Next[Index] = Cur[Index];
899 Next[Index].Cost += RightCost;
900 Next[Index].Path.push_back(Elt: DC_right);
901 }
902 }
903
904 std::swap(a&: Cur, b&: Next);
905 }
906
907 // We don't need the tentative values anymore; everything from here
908 // on out should be non-tentative.
909 TentativeValues.clear();
910
911 SmallVectorImpl<char> &Path = Cur[NL].Path;
912 BasicBlock::const_iterator LI = LStart, RI = RStart;
913
914 DiffLogBuilder Diff(Engine.getConsumer());
915
916 // Drop trailing matches.
917 while (Path.size() && Path.back() == DC_match)
918 Path.pop_back();
919
920 // Skip leading matches.
921 SmallVectorImpl<char>::iterator
922 PI = Path.begin(), PE = Path.end();
923 while (PI != PE && *PI == DC_match) {
924 unify(L: &*LI, R: &*RI);
925 ++PI;
926 ++LI;
927 ++RI;
928 }
929
930 for (; PI != PE; ++PI) {
931 switch (static_cast<DiffChange>(*PI)) {
932 case DC_match:
933 assert(LI != LE && RI != RE);
934 {
935 const Instruction *L = &*LI, *R = &*RI;
936 unify(L, R);
937 Diff.addMatch(L, R);
938 }
939 ++LI; ++RI;
940 break;
941
942 case DC_left:
943 assert(LI != LE);
944 Diff.addLeft(L: &*LI);
945 ++LI;
946 break;
947
948 case DC_right:
949 assert(RI != RE);
950 Diff.addRight(R: &*RI);
951 ++RI;
952 break;
953 }
954 }
955
956 // Finishing unifying and complaining about the tails of the block,
957 // which should be matches all the way through.
958 while (LI != LE) {
959 assert(RI != RE);
960 unify(L: &*LI, R: &*RI);
961 ++LI;
962 ++RI;
963 }
964
965 // If the terminators have different kinds, but one is an invoke and the
966 // other is an unconditional branch immediately following a call, unify
967 // the results and the destinations.
968 const Instruction *LTerm = LStart->getParent()->getTerminator();
969 const Instruction *RTerm = RStart->getParent()->getTerminator();
970 if (isa<UncondBrInst>(Val: LTerm) && isa<InvokeInst>(Val: RTerm)) {
971 BasicBlock::const_iterator I = LTerm->getIterator();
972 if (I == LStart->getParent()->begin()) return;
973 --I;
974 if (!isa<CallInst>(Val: *I)) return;
975 const CallInst *LCall = cast<CallInst>(Val: &*I);
976 const InvokeInst *RInvoke = cast<InvokeInst>(Val: RTerm);
977 if (!equivalentAsOperands(L: LCall->getCalledOperand(),
978 R: RInvoke->getCalledOperand(), AC: nullptr))
979 return;
980 if (!LCall->use_empty())
981 Values[LCall] = RInvoke;
982 tryUnify(L: LTerm->getSuccessor(Idx: 0), R: RInvoke->getNormalDest());
983 } else if (isa<InvokeInst>(Val: LTerm) && isa<UncondBrInst>(Val: RTerm)) {
984 BasicBlock::const_iterator I = RTerm->getIterator();
985 if (I == RStart->getParent()->begin()) return;
986 --I;
987 if (!isa<CallInst>(Val: *I)) return;
988 const CallInst *RCall = cast<CallInst>(Val&: I);
989 const InvokeInst *LInvoke = cast<InvokeInst>(Val: LTerm);
990 if (!equivalentAsOperands(L: LInvoke->getCalledOperand(),
991 R: RCall->getCalledOperand(), AC: nullptr))
992 return;
993 if (!LInvoke->use_empty())
994 Values[LInvoke] = RCall;
995 tryUnify(L: LInvoke->getNormalDest(), R: RTerm->getSuccessor(Idx: 0));
996 }
997}
998}
999
1000void DifferenceEngine::Oracle::anchor() { }
1001
1002void DifferenceEngine::diff(const Function *L, const Function *R) {
1003 Context C(*this, L, R);
1004
1005 // FIXME: types
1006 if (L->getCallingConv() != R->getCallingConv())
1007 log(text: "different calling conventions");
1008 diffAttributes(Engine&: *this, Prefix: "", L: L->getAttributes(), R: R->getAttributes(),
1009 NumParams: std::max(a: L->arg_size(), b: R->arg_size()), /*Complain=*/true);
1010
1011 // If both are declarations, we're done.
1012 if (L->empty() && R->empty())
1013 return;
1014 else if (L->empty())
1015 log(text: "left function is declaration, right function is definition");
1016 else if (R->empty())
1017 log(text: "right function is declaration, left function is definition");
1018 else
1019 FunctionDifferenceEngine(*this).diff(L, R);
1020}
1021
1022void DifferenceEngine::diff(const Module *L, const Module *R) {
1023 StringSet<> LNames;
1024 SmallVector<std::pair<const Function *, const Function *>, 20> Queue;
1025
1026 unsigned LeftAnonCount = 0;
1027 unsigned RightAnonCount = 0;
1028
1029 for (Module::const_iterator I = L->begin(), E = L->end(); I != E; ++I) {
1030 const Function *LFn = &*I;
1031 StringRef Name = LFn->getName();
1032 if (Name.empty()) {
1033 ++LeftAnonCount;
1034 continue;
1035 }
1036
1037 LNames.insert(key: Name);
1038
1039 if (Function *RFn = R->getFunction(Name: LFn->getName()))
1040 Queue.push_back(Elt: std::make_pair(x&: LFn, y&: RFn));
1041 else
1042 logf(text: "function %l exists only in left module") << LFn;
1043 }
1044
1045 for (Module::const_iterator I = R->begin(), E = R->end(); I != E; ++I) {
1046 const Function *RFn = &*I;
1047 StringRef Name = RFn->getName();
1048 if (Name.empty()) {
1049 ++RightAnonCount;
1050 continue;
1051 }
1052
1053 if (!LNames.count(Key: Name))
1054 logf(text: "function %r exists only in right module") << RFn;
1055 }
1056
1057 if (LeftAnonCount != 0 || RightAnonCount != 0) {
1058 SmallString<32> Tmp;
1059 logf(text: ("not comparing " + Twine(LeftAnonCount) +
1060 " anonymous functions in the left module and " +
1061 Twine(RightAnonCount) + " in the right module")
1062 .toStringRef(Out&: Tmp));
1063 }
1064
1065 for (SmallVectorImpl<std::pair<const Function *, const Function *>>::iterator
1066 I = Queue.begin(),
1067 E = Queue.end();
1068 I != E; ++I)
1069 diff(L: I->first, R: I->second);
1070}
1071
1072bool DifferenceEngine::equivalentAsOperands(const GlobalValue *L,
1073 const GlobalValue *R) {
1074 if (globalValueOracle) return (*globalValueOracle)(L, R);
1075
1076 if (isa<GlobalVariable>(Val: L) && isa<GlobalVariable>(Val: R)) {
1077 const GlobalVariable *GVL = cast<GlobalVariable>(Val: L);
1078 const GlobalVariable *GVR = cast<GlobalVariable>(Val: R);
1079 if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() &&
1080 GVR->hasLocalLinkage() && GVR->hasUniqueInitializer())
1081 return FunctionDifferenceEngine(*this, GVL, GVR)
1082 .equivalentAsOperands(L: GVL->getInitializer(), R: GVR->getInitializer(),
1083 AC: nullptr);
1084 }
1085
1086 return L->getName() == R->getName();
1087}
1088