[llvm-diff] Fix false-positive diffs on forward-referencing phi nodes

[jsilvanus]

Summary

When a phi node references a variable defined in a basic block dominated
by the the basic block containing the phi node, llvm-diff currently cannot determine
whether the variable is equivalent, and thus treats the phi node as different
and reports a difference. This leads to false positive differences as demonstrated
by the loop.ll diff, for which llvm-diff reports a diff when comparing the file
with itself.

Fix that issue by adding the concept of *equivalence assumptions*.
When encountering a pair of values which can neither be proven to be equivalent
nor to be non-equivalent, instead optimistically assume equivalence, and store
somewhere that the equivalence of the currently compared basic blocks depends
on this assumption.

Later, once all BBs have been processed, check all made assumptions and report
blocks as different whose equivalence was depending on an incorrect assumption,
or an assumption we could not prove to be correct.

In order to preserve the original diff report order, also schedule diffs
of blocks already known to be different using the same mechanism, so all block
diffs are now generated at the very end of function diffing.

In case an incorrect assumption was made, all further shown equivalences between
old and new values implictly depend on the incorrect assumption. Some of these
may in fact be not equivalent, but these are neither reverted nor reported,
because they are considered indirect diffs caused by an earlier direct diff.

See inline comments for an argument why we do not run into issues caused by circular
proof dependencies.

[dblaikie]

Can't say I have much context here - but out of curiosity, what's your interest in this tool, @jsilvanus ? & @void is this library/tool still of interest to you? (@nickdesaulniers is this of interest to you? Looks like @void's work recently (last year, at least, which is recent relative to this code mostly not having been touched since 2010 or so... ) was related to maybe adding some live patching tool, which I guess might be kernel related in some way?)

Given how old the code is here, and it's relatively untouched, I'd like to make sure we've got invested folks working together on it.

[jsilvanus]

Hi David, thanks for looking into this change!

I'm aware that there is very little active development for llvm-diff, and I chose you and @void based on the patch introducing phi node diffing.

While experimenting with llvm-diff (for context see below), I noticed this issue.
Since it seems to affect many inputs (essentially anything with a loop counter), and the fix seemed to be not too complicated, I decided to work on this.

My main interest, although I am not yet sure whether llvm-diff is the right tool for the job, is related to update_test_checks.py. I'd like to reduce diff sizes of lit tests caused by changed automatic variable names (%15 -> %16) of updated lit tests, with the goal of simplifying reviews.
Say you have an automatically generated, large lit test. A small change in the generated IR, say one added line, changes all following identifier names, and leads to a huge diff of text IR.
When updating the lit test with update_test_checks.py, these changes are propagated to the CHECK lines, since the generated FileCheck capture names (e.g. TMP15) are also incrementally numbered.
I'd like to have a mode where update_test_checks.py tries to preserve existing capture names to minimize the diff size of changed tests. The work flow would be like this:

1. Implement LLVM change
2. Update lit tests, preserving capture names
3. Normalize capture names in lit tests using an ordinary update_test_checks.py call

The result of 1 + 2 would be one small commit that is the main interest of review. Step 3 would be in a different, possibly large commit that only contains the automatically generated capture renaming and would not needed to be reviewed in the same detail. Note that 3. is not absolutely necessary, but it seems to be nicer to have tests with sequentially named identifiers without any remainders of past versions of the test.

A possible implementation of the above would be to run both the old and new opt binary on the test, use llvm-diff to establish a mapping of variables, and use this correspondence to establish a mapping of FileCheck capture names.

[dblaikie]

Can't say I've got quite the time to page in the algorithm, but it sounds like a reasonable idea & given this tool's probably relatively unused - I think maybe this is the right level of review & you should feel welcome to give it a go, see how it plays out in general/for your use case.

Thanks for the context & patch.

llvm/tools/llvm-diff/lib/DifferenceEngine.cpp

184

SmallVector?

287–289

Maybe?

291

349

Could you change this and others to use something more like this/aggregate initialization (otherwise it looks like it could be a ctor call, which makes reading a bit more difficult/need more care, perhaps)

545–546

would be nice to avoid these unrelated changes, if possible (could pre-commit them if you think they're valuable)

[jsilvanus]

Address review feedback.

[jsilvanus]

Remove reformatting of existing code.

[jsilvanus]

Thanks for your review, I updated the patch to address it.

I'll wait a few days with committing so others have a chance to comment.

llvm/tools/llvm-diff/lib/DifferenceEngine.cpp

184

Thanks, fixed.

287–289

Thanks, that's better indeed.

291

Fixed.

349

Thanks, fixed.

545–546

I removed those.

llvm/test/tools/llvm-diff/assumption-report-order.ll

+; Check that differences are reported in the BB processing order
+; following the control flow, independent on whether the diff was depending
+; on an assumption or not.
+;
+; Replace %newvar1 with %newvar2 in the phi node. This can only
+; be detected to be different once BB2 has been processed, so leads to a assumption
+; and is detected to diff later on.
+; Also, replace the 1000 by 2000 in BB1, which is detected directly.
+;
+; RUN: rm -f %t.ll
+; RUN: cat %s | sed -e 's/ %newvar1, %BB2 / %newvar2, %BB2 /' | sed -e 's/1000/2000/' > %t.ll
+; RUN: not llvm-diff %s %t.ll 2>&1 | FileCheck %s
+
+; CHECK:      in function func:
+; CHECK-NEXT:   in block %BB0:
+; CHECK-NEXT:     >   %var = phi i32 [ 0, %ENTRY ], [ %newvar2, %BB2 ]
+; CHECK-NEXT:     <   %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB2 ]
+; CHECK-NEXT:   in block %BB1:
+; CHECK-NEXT:     >   %diffvar = add i32 %var, 2000
+; CHECK-NEXT:     <   %diffvar = add i32 %var, 1000
+
+define i32 @func() {
+ENTRY:
+  br label %BB0
+
+BB0:
+  ; When diffing this phi node, we need to detect whether
+  ; %newvar1 is equivalent, which is not known until BB2 has been processed.
+  %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB2 ]
+  %cnd = icmp eq i32 %var, 0
+  br i1 %cnd, label %BB1, label %END
+
+BB1:
+  %diffvar = add i32 %var, 1000
+  br label %BB1
+
+BB2:
+  %newvar1 = add i32 %var, 1
+  %newvar2 = add i32 %var, 2
+  br label %BB0
+
+END:
+  ; Equivalence of the ret depends on equivalence of %var.
+  ; Even if %var differs, we do not report a diff here, because
+  ; this is an indirect diff caused by another diff.
+  ret i32 %var
+}

llvm/test/tools/llvm-diff/loop.ll

-; Diff file with itself
-; Due to a current limitation in llvm-diff, a diff is reported here.
-; RUN: not llvm-diff %s %s 2>&1 | FileCheck --check-prefix=SAME-FILE %s
+; Diff file with itself, assert no difference by return code
+; RUN: llvm-diff %s %s
 
 ; Replace %newvar1 with %newvar2 in the phi node. This can only
 ; be detected to be different once BB1 has been processed.
 ; RUN: rm -f %t.ll
 ; RUN: cat %s | sed -e 's/ %newvar1, %BB1 / %newvar2, %BB1 /' > %t.ll
 ; RUN: not llvm-diff %s %t.ll 2>&1 | FileCheck --check-prefix DIFFERENT-VAR %s
 
-; SAME-FILE:      in function func:
-; SAME-FILE-NEXT:   in block %BB0:
-; SAME-FILE-NEXT:     >   %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB1 ]
-; SAME-FILE-NEXT:     >   %cnd = icmp eq i32 %var, 0
-; SAME-FILE-NEXT:     >   br i1 %cnd, label %BB1, label %END
-; SAME-FILE-NEXT:     <   %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB1 ]
-; SAME-FILE-NEXT:     <   %cnd = icmp eq i32 %var, 0
-; SAME-FILE-NEXT:     <   br i1 %cnd, label %BB1, label %END
-
 ; DIFFERENT-VAR:      in function func:
 ; DIFFERENT-VAR-NEXT:   in block %BB0:
 ; DIFFERENT-VAR-NEXT:     >   %var = phi i32 [ 0, %ENTRY ], [ %newvar2, %BB1 ]
-; DIFFERENT-VAR-NEXT:     >   %cnd = icmp eq i32 %var, 0
-; DIFFERENT-VAR-NEXT:     >   br i1 %cnd, label %BB1, label %END
 ; DIFFERENT-VAR-NEXT:     <   %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB1 ]
-; DIFFERENT-VAR-NEXT:     <   %cnd = icmp eq i32 %var, 0
-; DIFFERENT-VAR-NEXT:     <   br i1 %cnd, label %BB1, label %END
 define i32 @func() {
 ENTRY:
   br label %BB0
 
 BB0:
   ; When diffing this phi node, we need to detect whether
   ; %newvar1 is equivalent, which is not known until BB1 has been processed.
   %var = phi i32 [ 0, %ENTRY ], [ %newvar1, %BB1 ]

llvm/tools/llvm-diff/lib/DifferenceEngine.cpp

 //===----------------------------------------------------------------------===//
 
 #include "DifferenceEngine.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/type_traits.h"
class FunctionDifferenceEngine {
   DifferenceEngine &Engine;
 
   // Some initializers may reference the variable we're currently checking. This
   // can cause an infinite loop. The Saved[LR]HS ivars can be checked to prevent
   // recursing.
   const Value *SavedLHS;
   const Value *SavedRHS;
 
-  /// The current mapping from old local values to new local values.
+  // The current mapping from old local values to new local values.
   DenseMap<const Value *, const Value *> Values;
 
-  /// The current mapping from old blocks to new blocks.
+  // The current mapping from old blocks to new blocks.
   DenseMap<const BasicBlock *, const BasicBlock *> Blocks;
 
+  // The tentative mapping from old local values while comparing a pair of
+  // basic blocks. Once the pair has been processed, the tentative mapping is
+  // committed to the Values map.
   DenseSet<std::pair<const Value *, const Value *>> TentativeValues;
 
+  // Equivalence Assumptions
+  //
+  // For basic blocks in loops, some values in phi nodes may depend on
+  // values from not yet processed basic blocks in the loop. When encountering
+  // such values, we optimistically asssume their equivalence and store this
+  // assumption in a BlockDiffCandidate for the pair of compared BBs.
+  //
+  // Once we have diffed all BBs, for every BlockDiffCandidate, we check all
+  // stored assumptions using the Values map that stores proven equivalences
+  // between the old and new values, and report a diff if an assumption cannot
+  // be proven to be true.
+  //
+  // Note that after having made an assumption, all further determined
+  // equivalences implicitly depend on that assumption. These will not be
+  // reverted or reported if the assumption proves to be false, because these
+  // are considered indirect diffs caused by earlier direct diffs.
+  //
+  // We aim to avoid false negatives in llvm-diff, that is, ensure that
+  // whenever no diff is reported, the functions are indeed equal. If
+  // assumptions were made, this is not entirely clear, because in principle we
+  // could end up with a circular proof where the proof of equivalence of two
+  // nodes is depending on the assumption of their equivalence.
+  //
+  // To see that assumptions do not add false negatives, note that if we do not
+  // report a diff, this means that there is an equivalence mapping between old
+  // and new values that is consistent with all assumptions made. The circular
+  // dependency that exists on an IR value level does not exist at run time,
+  // because the values selected by the phi nodes must always already have been
+  // computed. Hence, we can prove equivalence of the old and new functions by
+  // considering step-wise parallel execution, and incrementally proving
+  // equivalence of every new computed value. Another way to think about it is
+  // to imagine cloning the loop BBs for every iteration, turning the loops
+  // into (possibly infinite) DAGs, and proving equivalence by induction on the
+  // iteration, using the computed value mapping.
+
+  // The class BlockDiffCandidate stores pairs which either have already been
+  // proven to differ, or pairs whose equivalence depends on assumptions to be
+  // verified later.
+  struct BlockDiffCandidate {
+    const BasicBlock *LBB;
+    const BasicBlock *RBB;
+    // Maps old values to assumed-to-be-equivalent new values
+    SmallDenseMap<const Value *, const Value *> EquivalenceAssumptions;
+    // If set, we already know the blocks differ.
+    bool KnownToDiffer;
+  };
+
+  // List of block diff candidates in the order found by processing.
+  // We generate reports in this order.
+  // For every LBB, there may only be one corresponding RBB.
+  SmallVector<BlockDiffCandidate> BlockDiffCandidates;
+  // Maps LBB to the index of its BlockDiffCandidate, if existing.
+  DenseMap<const BasicBlock *, uint64_t> BlockDiffCandidateIndices;
+
+  // Note: Every LBB must always be queried together with the same RBB.
+  // The returned reference is not permanently valid and should not be stored.
+  BlockDiffCandidate &getOrCreateBlockDiffCandidate(const BasicBlock *LBB,
+                                                    const BasicBlock *RBB) {
+    auto It = BlockDiffCandidateIndices.find(LBB);
+    // Check if LBB already has a diff candidate
+    if (It == BlockDiffCandidateIndices.end()) {
+      // Add new one
+      BlockDiffCandidateIndices[LBB] = BlockDiffCandidates.size();
+      BlockDiffCandidates.push_back(
+          {LBB, RBB, SmallDenseMap<const Value *, const Value *>(), false});
+      return BlockDiffCandidates.back();
+    }
+    // Use existing one
+    BlockDiffCandidate &Result = BlockDiffCandidates[It->second];
+    assert(Result.RBB == RBB && "Inconsistent basic block pairing!");
+    return Result;
+  }
+
+  // Optionally passed to equivalence checker functions, so these can add
+  // assumptions in BlockDiffCandidates. Its presence controls whether
+  // assumptions are generated.
+  struct AssumptionContext {
+    // The two basic blocks that need the two compared values to be equivalent.
+    const BasicBlock *LBB;
+    const BasicBlock *RBB;
+  };
+
   unsigned getUnprocPredCount(const BasicBlock *Block) const {
     unsigned Count = 0;
     for (const_pred_iterator I = pred_begin(Block), E = pred_end(Block); I != E;
          ++I)
       if (!Blocks.count(*I)) Count++;
     return Count;
   }
 
bool tryUnify(const BasicBlock *L, const BasicBlock *R) {
     return false;
   }
 
   /// Unifies two instructions, given that they're known not to have
   /// structural differences.
   void unify(const Instruction *L, const Instruction *R) {
     DifferenceEngine::Context C(Engine, L, R);
 
-    bool Result = diff(L, R, true, true);
+    bool Result = diff(L, R, true, true, true);
     assert(!Result && "structural differences second time around?");
     (void) Result;
     if (!L->use_empty())
       Values[L] = R;
   }
 
   void processQueue() {
     while (!Queue.empty()) {
       BlockPair Pair = Queue.remove_min();
       diff(Pair.first, Pair.second);
     }
   }
 
+  void checkAndReportDiffCandidates() {
+    for (BlockDiffCandidate &BDC : BlockDiffCandidates) {
+
+      // Check assumptions
+      for (const auto &[L, R] : BDC.EquivalenceAssumptions) {
+        auto It = Values.find(L);
+        if (It == Values.end() || It->second != R) {
+          BDC.KnownToDiffer = true;
+          break;
+        }
+      }
+
+      // Run block diff if the BBs differ
+      if (BDC.KnownToDiffer) {
+        DifferenceEngine::Context C(Engine, BDC.LBB, BDC.RBB);
+        runBlockDiff(BDC.LBB->begin(), BDC.RBB->begin());
+      }
+    }
+  }
+
   void diff(const BasicBlock *L, const BasicBlock *R) {
     DifferenceEngine::Context C(Engine, L, R);
 
     BasicBlock::const_iterator LI = L->begin(), LE = L->end();
     BasicBlock::const_iterator RI = R->begin();
 
     do {
       assert(LI != LE && RI != R->end());
       const Instruction *LeftI = &*LI, *RightI = &*RI;
 
       // If the instructions differ, start the more sophisticated diff
       // algorithm at the start of the block.
-      if (diff(LeftI, RightI, false, false)) {
+      if (diff(LeftI, RightI, false, false, true)) {
         TentativeValues.clear();
-        return runBlockDiff(L->begin(), R->begin());
+        // Register (L, R) as diffing pair. Note that we could directly emit a
+        // block diff here, but this way we ensure all diffs are emitted in one
+        // consistent order, independent of whether the diffs were detected
+        // immediately or via invalid assumptions.
+        getOrCreateBlockDiffCandidate(L, R).KnownToDiffer = true;
+        return;
       }
 
       // Otherwise, tentatively unify them.
       if (!LeftI->use_empty())
         TentativeValues.insert(std::make_pair(LeftI, RightI));
 
       ++LI;
       ++RI;
     } while (LI != LE); // This is sufficient: we can't get equality of
                         // terminators if there are residual instructions.
 
     // Unify everything in the block, non-tentatively this time.
     TentativeValues.clear();
     for (LI = L->begin(), RI = R->begin(); LI != LE; ++LI, ++RI)
       unify(&*LI, &*RI);
   }
 
   bool matchForBlockDiff(const Instruction *L, const Instruction *R);
   void runBlockDiff(BasicBlock::const_iterator LI,
                     BasicBlock::const_iterator RI);
 
   bool diffCallSites(const CallBase &L, const CallBase &R, bool Complain) {
     // FIXME: call attributes
-    if (!equivalentAsOperands(L.getCalledOperand(), R.getCalledOperand())) {
+    AssumptionContext AC = {L.getParent(), R.getParent()};
+    if (!equivalentAsOperands(L.getCalledOperand(), R.getCalledOperand(),
+                              &AC)) {
       if (Complain) Engine.log("called functions differ");
       return true;
     }
     if (L.arg_size() != R.arg_size()) {
       if (Complain) Engine.log("argument counts differ");
       return true;
     }
     for (unsigned I = 0, E = L.arg_size(); I != E; ++I)
-      if (!equivalentAsOperands(L.getArgOperand(I), R.getArgOperand(I))) {
+      if (!equivalentAsOperands(L.getArgOperand(I), R.getArgOperand(I), &AC)) {
         if (Complain)
           Engine.logf("arguments %l and %r differ")
               << L.getArgOperand(I) << R.getArgOperand(I);
         return true;
       }
     return false;
   }
 
+  // If AllowAssumptions is enabled, whenever we encounter a pair of values
+  // that we cannot prove to be equivalent, we assume equivalence and store that
+  // assumption to be checked later in BlockDiffCandidates.
   bool diff(const Instruction *L, const Instruction *R, bool Complain,
-            bool TryUnify) {
+            bool TryUnify, bool AllowAssumptions) {
     // FIXME: metadata (if Complain is set)
+    AssumptionContext ACValue = {L->getParent(), R->getParent()};
+    // nullptr AssumptionContext disables assumption generation.
+    const AssumptionContext *AC = AllowAssumptions ? &ACValue : nullptr;
 
     // Different opcodes always imply different operations.
     if (L->getOpcode() != R->getOpcode()) {
       if (Complain) Engine.log("different instruction types");
       return true;
     }
 
     if (isa<CmpInst>(L)) {
if (isa<CmpInst>(L)) {
         return true;
       }
 
       for (unsigned I = 0; I < LI.getNumIncomingValues(); ++I) {
         if (TryUnify)
           tryUnify(LI.getIncomingBlock(I), RI.getIncomingBlock(I));
 
         if (!equivalentAsOperands(LI.getIncomingValue(I),
-                                  RI.getIncomingValue(I))) {
+                                  RI.getIncomingValue(I), AC)) {
           if (Complain)
             Engine.log("PHI node incoming values differ");
           return true;
         }
       }
 
       return false;
 
// Terminators.
       const BranchInst *LI = cast<BranchInst>(L);
       const BranchInst *RI = cast<BranchInst>(R);
       if (LI->isConditional() != RI->isConditional()) {
         if (Complain) Engine.log("branch conditionality differs");
         return true;
       }
 
       if (LI->isConditional()) {
-        if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
+        if (!equivalentAsOperands(LI->getCondition(), RI->getCondition(), AC)) {
           if (Complain) Engine.log("branch conditions differ");
           return true;
         }
         if (TryUnify) tryUnify(LI->getSuccessor(1), RI->getSuccessor(1));
       }
       if (TryUnify) tryUnify(LI->getSuccessor(0), RI->getSuccessor(0));
       return false;
 
     } else if (isa<IndirectBrInst>(L)) {
       const IndirectBrInst *LI = cast<IndirectBrInst>(L);
       const IndirectBrInst *RI = cast<IndirectBrInst>(R);
       if (LI->getNumDestinations() != RI->getNumDestinations()) {
         if (Complain) Engine.log("indirectbr # of destinations differ");
         return true;
       }
 
-      if (!equivalentAsOperands(LI->getAddress(), RI->getAddress())) {
+      if (!equivalentAsOperands(LI->getAddress(), RI->getAddress(), AC)) {
         if (Complain) Engine.log("indirectbr addresses differ");
         return true;
       }
 
       if (TryUnify) {
         for (unsigned i = 0; i < LI->getNumDestinations(); i++) {
           tryUnify(LI->getDestination(i), RI->getDestination(i));
         }
       }
       return false;
 
     } else if (isa<SwitchInst>(L)) {
       const SwitchInst *LI = cast<SwitchInst>(L);
       const SwitchInst *RI = cast<SwitchInst>(R);
-      if (!equivalentAsOperands(LI->getCondition(), RI->getCondition())) {
+      if (!equivalentAsOperands(LI->getCondition(), RI->getCondition(), AC)) {
         if (Complain) Engine.log("switch conditions differ");
         return true;
       }
       if (TryUnify) tryUnify(LI->getDefaultDest(), RI->getDefaultDest());
 
       bool Difference = false;
 
       DenseMap<const ConstantInt *, const BasicBlock *> LCases;
bool diff(const Instruction *L, const Instruction *R, bool Complain,
 
     if (L->getNumOperands() != R->getNumOperands()) {
       if (Complain) Engine.log("instructions have different operand counts");
       return true;
     }
 
     for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
       Value *LO = L->getOperand(I), *RO = R->getOperand(I);
-      if (!equivalentAsOperands(LO, RO)) {
+      if (!equivalentAsOperands(LO, RO, AC)) {
         if (Complain) Engine.logf("operands %l and %r differ") << LO << RO;
         return true;
       }
     }
 
     return false;
   }
 
 public:
-  bool equivalentAsOperands(const Constant *L, const Constant *R) {
+  bool equivalentAsOperands(const Constant *L, const Constant *R,
+                            const AssumptionContext *AC) {
     // Use equality as a preliminary filter.
     if (L == R)
       return true;
 
     if (L->getValueID() != R->getValueID())
       return false;
 
     // Ask the engine about global values.
     if (isa<GlobalValue>(L))
       return Engine.equivalentAsOperands(cast<GlobalValue>(L),
                                          cast<GlobalValue>(R));
 
     // Compare constant expressions structurally.
     if (isa<ConstantExpr>(L))
-      return equivalentAsOperands(cast<ConstantExpr>(L),
-                                  cast<ConstantExpr>(R));
+      return equivalentAsOperands(cast<ConstantExpr>(L), cast<ConstantExpr>(R),
+                                  AC);
 
     // Constants of the "same type" don't always actually have the same
     // type; I don't know why.  Just white-list them.
     if (isa<ConstantPointerNull>(L) || isa<UndefValue>(L) || isa<ConstantAggregateZero>(L))
       return true;
 
     // Block addresses only match if we've already encountered the
     // block.  FIXME: tentative matches?
     if (isa<BlockAddress>(L))
       return Blocks[cast<BlockAddress>(L)->getBasicBlock()]
                  == cast<BlockAddress>(R)->getBasicBlock();
 
     // If L and R are ConstantVectors, compare each element
     if (isa<ConstantVector>(L)) {
       const ConstantVector *CVL = cast<ConstantVector>(L);
       const ConstantVector *CVR = cast<ConstantVector>(R);
       if (CVL->getType()->getNumElements() != CVR->getType()->getNumElements())
         return false;
       for (unsigned i = 0; i < CVL->getType()->getNumElements(); i++) {
-        if (!equivalentAsOperands(CVL->getOperand(i), CVR->getOperand(i)))
+        if (!equivalentAsOperands(CVL->getOperand(i), CVR->getOperand(i), AC))
           return false;
       }
       return true;
     }
 
     // If L and R are ConstantArrays, compare the element count and types.
     if (isa<ConstantArray>(L)) {
       const ConstantArray *CAL = cast<ConstantArray>(L);
       const ConstantArray *CAR = cast<ConstantArray>(R);
       // Sometimes a type may be equivalent, but not uniquified---e.g. it may
       // contain a GEP instruction. Do a deeper comparison of the types.
       if (CAL->getType()->getNumElements() != CAR->getType()->getNumElements())
         return false;
 
       for (unsigned I = 0; I < CAL->getType()->getNumElements(); ++I) {
         if (!equivalentAsOperands(CAL->getAggregateElement(I),
-                                  CAR->getAggregateElement(I)))
+                                  CAR->getAggregateElement(I), AC))
           return false;
       }
 
       return true;
     }
 
     // If L and R are ConstantStructs, compare each field and type.
     if (isa<ConstantStruct>(L)) {
if (isa<ConstantStruct>(L)) {
             // If the left and right operands aren't both re-analyzing the
             // variable, then the initialiers don't match, so report "false".
             // Otherwise, we skip these operands..
             return false;
 
           continue;
         }
 
-        if (!equivalentAsOperands(LAgg, RAgg)) {
+        if (!equivalentAsOperands(LAgg, RAgg, AC)) {
           return false;
         }
       }
 
       return true;
     }
 
     return false;
   }
 
-  bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R) {
+  bool equivalentAsOperands(const ConstantExpr *L, const ConstantExpr *R,
+                            const AssumptionContext *AC) {
     if (L == R)
       return true;
 
     if (L->getOpcode() != R->getOpcode())
       return false;
 
     switch (L->getOpcode()) {
     case Instruction::ICmp:
for (unsigned I = 0, E = L->getNumOperands(); I != E; ++I) {
           // If the left and right operands aren't both re-analyzing the
           // variable, then the initialiers don't match, so report "false".
           // Otherwise, we skip these operands..
           return false;
 
         continue;
       }
 
-      if (!equivalentAsOperands(LOp, ROp))
+      if (!equivalentAsOperands(LOp, ROp, AC))
         return false;
     }
 
     return true;
   }
 
-  bool equivalentAsOperands(const Value *L, const Value *R) {
+  // There are cases where we cannot determine whether two values are
+  // equivalent, because it depends on not yet processed basic blocks -- see the
+  // documentation on assumptions.
+  //
+  // AC is the context in which we are currently performing a diff.
+  // When we encounter a pair of values for which we can neither prove
+  // equivalence nor the opposite, we do the following:
+  //  * If AC is nullptr, we treat the pair as non-equivalent.
+  //  * If AC is set, we add an assumption for the basic blocks given by AC,
+  //    and treat the pair as equivalent. The assumption is checked later.
+  bool equivalentAsOperands(const Value *L, const Value *R,
+                            const AssumptionContext *AC) {
     // Fall out if the values have different kind.
     // This possibly shouldn't take priority over oracles.
     if (L->getValueID() != R->getValueID())
       return false;
 
     // Value subtypes:  Argument, Constant, Instruction, BasicBlock,
     //                  InlineAsm, MDNode, MDString, PseudoSourceValue
 
     if (isa<Constant>(L))
-      return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R));
+      return equivalentAsOperands(cast<Constant>(L), cast<Constant>(R), AC);
 
-    if (isa<Instruction>(L))
-      return Values[L] == R || TentativeValues.count(std::make_pair(L, R));
+    if (isa<Instruction>(L)) {
+      auto It = Values.find(L);
+      if (It != Values.end())
+        return It->second == R;
+
+      if (TentativeValues.count(std::make_pair(L, R)))
+        return true;
+
+      // L and R might be equivalent, this could depend on not yet processed
+      // basic blocks, so we cannot decide here.
+      if (AC) {
+        // Add an assumption, unless there is a conflict with an existing one
+        BlockDiffCandidate &BDC =
+            getOrCreateBlockDiffCandidate(AC->LBB, AC->RBB);
+        auto InsertionResult = BDC.EquivalenceAssumptions.insert({L, R});
+        if (!InsertionResult.second && InsertionResult.first->second != R) {
+          // We already have a conflicting equivalence assumption for L, so at
+          // least one must be wrong, and we know that there is a diff.
+          BDC.KnownToDiffer = true;
+          BDC.EquivalenceAssumptions.clear();
+          return false;
+        }
+        // Optimistically assume equivalence, and check later once all BBs
+        // have been processed.
+        return true;
+      }
+
+      // Assumptions disabled, so pessimistically assume non-equivalence.
+      return false;
+    }
 
     if (isa<Argument>(L))
       return Values[L] == R;
 
     if (isa<BasicBlock>(L))
       return Blocks[cast<BasicBlock>(L)] != R;
 
     // Pretend everything else is identical.
     return true;
   }
 
   // Avoid a gcc warning about accessing 'this' in an initializer.
   FunctionDifferenceEngine *this_() { return this; }
 
 public:
   FunctionDifferenceEngine(DifferenceEngine &Engine,
                            const Value *SavedLHS = nullptr,
                            const Value *SavedRHS = nullptr)
       : Engine(Engine), SavedLHS(SavedLHS), SavedRHS(SavedRHS),
         Queue(QueueSorter(*this_())) {}
 
   void diff(const Function *L, const Function *R) {
+    assert(Values.empty() && "Multiple diffs per engine are not supported!");
+
     if (L->arg_size() != R->arg_size())
       Engine.log("different argument counts");
 
     // Map the arguments.
     for (Function::const_arg_iterator LI = L->arg_begin(), LE = L->arg_end(),
                                       RI = R->arg_begin(), RE = R->arg_end();
          LI != LE && RI != RE; ++LI, ++RI)
       Values[&*LI] = &*RI;
 
     tryUnify(&*L->begin(), &*R->begin());
     processQueue();
+    checkAndReportDiffCandidates();
   }
 };
 
 struct DiffEntry {
   DiffEntry() : Cost(0) {}
 
   unsigned Cost;
   llvm::SmallVector<char, 8> Path; // actually of DifferenceEngine::DiffChange
 };
 
 bool FunctionDifferenceEngine::matchForBlockDiff(const Instruction *L,
                                                  const Instruction *R) {
-  return !diff(L, R, false, false);
+  return !diff(L, R, false, false, false);
 }
 
 void FunctionDifferenceEngine::runBlockDiff(BasicBlock::const_iterator LStart,
                                             BasicBlock::const_iterator RStart) {
   BasicBlock::const_iterator LE = LStart->getParent()->end();
   BasicBlock::const_iterator RE = RStart->getParent()->end();
 
   unsigned NL = std::distance(LStart, LE);
if (isa<BranchInst>(LTerm) && isa<InvokeInst>(RTerm)) {
     if (cast<BranchInst>(LTerm)->isConditional()) return;
     BasicBlock::const_iterator I = LTerm->getIterator();
     if (I == LStart->getParent()->begin()) return;
     --I;
     if (!isa<CallInst>(*I)) return;
     const CallInst *LCall = cast<CallInst>(&*I);
     const InvokeInst *RInvoke = cast<InvokeInst>(RTerm);
     if (!equivalentAsOperands(LCall->getCalledOperand(),
-                              RInvoke->getCalledOperand()))
+                              RInvoke->getCalledOperand(), nullptr))
       return;
     if (!LCall->use_empty())
       Values[LCall] = RInvoke;
     tryUnify(LTerm->getSuccessor(0), RInvoke->getNormalDest());
   } else if (isa<InvokeInst>(LTerm) && isa<BranchInst>(RTerm)) {
     if (cast<BranchInst>(RTerm)->isConditional()) return;
     BasicBlock::const_iterator I = RTerm->getIterator();
     if (I == RStart->getParent()->begin()) return;
     --I;
     if (!isa<CallInst>(*I)) return;
     const CallInst *RCall = cast<CallInst>(I);
     const InvokeInst *LInvoke = cast<InvokeInst>(LTerm);
     if (!equivalentAsOperands(LInvoke->getCalledOperand(),
-                              RCall->getCalledOperand()))
+                              RCall->getCalledOperand(), nullptr))
       return;
     if (!LInvoke->use_empty())
       Values[LInvoke] = RCall;
     tryUnify(LInvoke->getNormalDest(), RTerm->getSuccessor(0));
   }
 }
 }
 
bool DifferenceEngine::equivalentAsOperands(const GlobalValue *L,
   if (globalValueOracle) return (*globalValueOracle)(L, R);
 
   if (isa<GlobalVariable>(L) && isa<GlobalVariable>(R)) {
     const GlobalVariable *GVL = cast<GlobalVariable>(L);
     const GlobalVariable *GVR = cast<GlobalVariable>(R);
     if (GVL->hasLocalLinkage() && GVL->hasUniqueInitializer() &&
         GVR->hasLocalLinkage() && GVR->hasUniqueInitializer())
       return FunctionDifferenceEngine(*this, GVL, GVR)
-          .equivalentAsOperands(GVL->getInitializer(), GVR->getInitializer());
+          .equivalentAsOperands(GVL->getInitializer(), GVR->getInitializer(),
+                                nullptr);
   }
 
   return L->getName() == R->getName();
 }