[llvm-diff] Fix false-positive diffs on forward-referencing phi nodes
authorJannik Silvanus <jannik.silvanus@amd.com>
Thu, 27 Oct 2022 07:14:40 +0000 (09:14 +0200)
committerJannik Silvanus <jannik.silvanus@amd.com>
Wed, 9 Nov 2022 19:40:47 +0000 (20:40 +0100)
commite044796132abd9e10e21093822dc234003628fbd
treeeddbad294e30dfe3a020e2f8e8bf5e1e709a9702
parent8a084f68c8a1cac99d9fa0fbcf490b53ab3b6e0c
[llvm-diff] Fix false-positive diffs on forward-referencing phi nodes

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.

Differential Revision: https://reviews.llvm.org/D137318
llvm/test/tools/llvm-diff/assumption-report-order.ll [new file with mode: 0644]
llvm/test/tools/llvm-diff/loop.ll
llvm/tools/llvm-diff/lib/DifferenceEngine.cpp