[DomTree] Assert that blocks in queries aren't from another function

[DaniilSuchkov]

Summary

This assertion should help us catch cases when DT is used in a way that doesn't make much sense and usually indicates usage errors. In D110752 you can see a test on which this assertion catches a miscompile. When processing foo SimpleLoopUnswitch decided to make dominates(BB1, BB2) query with BB2 being a block from another function (bar). In that case the result of the query was true since B isn't reachable from foo's entry, so SimpleLoopUnswitch went ahead and replaced the use of true in bar because the preheader of one of the loops from foo "dominates" the entry block from bar.

I decided to add this assertion to getNode since all queries seem to be routed through that function for all non-trivial cases.

[DaniilSuchkov]

Since SimpleLoopUnswitch is known to break this assertion, I'm going to land this patch only together with D110752.

[nikic]

llvm/include/llvm/Support/GenericDomTree.h

353

Is !BB really a valid input to this function?

[DaniilSuchkov]

llvm/include/llvm/Support/GenericDomTree.h

353

I don't know, but since there are no checks for that anywhere and it's not mentioned in its description, I decided refrain from making any assumptions.
If you think it's not, I can add an assertion for that in a separate patch.

[DaniilSuchkov]

Updated testcase to make it clearer how this patch impacts it.

[DaniilSuchkov]

That was wrong diff.

[aeubanks]

adding the test here is confusing, I think just adding the assert is good enough. so D110752 would have to land first

llvm/include/llvm/Support/GenericDomTree.h

353

I'd just remove the check for !BB if check-llvm doesn't complain

[DaniilSuchkov]

In D110751#3034967, @aeubanks wrote:

adding the test here is confusing, I think just adding the assert is good enough. so D110752 would have to land first

I'm not adding the test here, it'll be in a separate patch. I want to land this patch before the D110752 because this way it's obvious the assertion catches this bug.

[DaniilSuchkov]

llvm/include/llvm/Support/GenericDomTree.h

353

make check quickly reminded me that !BB || wasn't accidental at all:

Skipped          :    36
Unsupported      : 19985
Passed           : 19299
Expectedly Failed:    58
Failed           :  6325

That's almost 1/3 of all tests.

[DaniilSuchkov]

Rebased it on top of D110752.

[MaskRay]

LGTM.

llvm/include/llvm/Support/GenericDomTree.h

353

If my memory doesn't fail me: it may be used by postdominator as the root node.
I did notice that this should be avoided to prevent confusion.

[DaniilSuchkov]

It looks like it has found an actual bug: https://lab.llvm.org/buildbot/#/builders/70/builds/12409/steps/10/logs/stdio

clang++: /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:353: llvm::DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase<NodeT, IsPostDom>::getNode(const NodeT*) const [with NodeT = llvm::BasicBlock; bool IsPostDom = false]: Assertion `(!BB || !BB->getParent() || BB->getParent() == Parent) && "A node from another function!"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Transforms/Instrumentation -I/b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Instrumentation -Iinclude -I/b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O2 -g -DNDEBUG -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Transforms/Instrumentation/CMakeFiles/LLVMInstrumentation.dir/DataFlowSanitizer.cpp.o -MF lib/Transforms/Instrumentation/CMakeFiles/LLVMInstrumentation.dir/DataFlowSanitizer.cpp.o.d -o lib/Transforms/Instrumentation/CMakeFiles/LLVMInstrumentation.dir/DataFlowSanitizer.cpp.o -c /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x00005654354a733c llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Support/Unix/Signals.inc:569:3
 #1 0x00005654354a53d4 llvm::sys::RunSignalHandlers() /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Support/Signals.cpp:97:20
 #2 0x00005654354a5949 llvm::sys::CleanupOnSignal(unsigned long) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Support/Unix/Signals.inc:361:31
 #3 0x000056543540d3a8 HandleCrash /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:74:27
 #4 0x000056543540d3a8 CrashRecoverySignalHandler(int) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:389:62
 #5 0x00007fbbaaebd730 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12730)
 #6 0x00007fbbaa7a37bb raise (/lib/x86_64-linux-gnu/libc.so.6+0x377bb)
 #7 0x00007fbbaa78e535 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22535)
 #8 0x00007fbbaa78e40f (/lib/x86_64-linux-gnu/libc.so.6+0x2240f)
 #9 0x00007fbbaa79c102 (/lib/x86_64-linux-gnu/libc.so.6+0x30102)
#10 0x0000565434c0f580 llvm::DominatorTreeBase<llvm::BasicBlock, false>::operator[](llvm::BasicBlock const*) const /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:363:22
#11 0x0000565434c0fec5 llvm::DominatorTreeBase<llvm::BasicBlock, false>::properlyDominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:947:51
#12 0x0000565434c0fec5 llvm::DominatorTreeBase<llvm::BasicBlock, false>::properlyDominates(llvm::BasicBlock const*, llvm::BasicBlock const*) const /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:938:6
#13 0x0000565435235a9d isLoadInvariantInLoop /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:1095:61
#14 0x0000565435235a9d llvm::canSinkOrHoistInst(llvm::Instruction&, llvm::AAResults*, llvm::DominatorTree*, llvm::Loop*, llvm::AliasSetTracker*, llvm::MemorySSAUpdater*, bool, llvm::SinkAndHoistLICMFlags*, llvm::OptimizationRemarkEmitter*) (.part.845) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:1187:30
#15 0x000056543523bf29 llvm::hoistRegion(llvm::DomTreeNodeBase<llvm::BasicBlock>*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::Loop*, llvm::MemorySSAUpdater*, llvm::ScalarEvolution*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*, bool) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:909:49
#16 0x0000565435240e04 (anonymous namespace)::LoopInvariantCodeMotion::runOnLoop(llvm::Loop*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::ScalarEvolution*, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter*, bool) (.part.877) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:436:38
#17 0x00005654352424c0 llvm::LICMPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Scalar/LICM.cpp:274:3
<...>

I can't imagine a good reason for LICM to make queries about blocks from other functions.
Upd: it seems LICM calls isLoadInvariantInLoop for a load where ptr arg is a global value and then isLoadInvariantInLoop runs a check for all users of the ptr arg, including ones from other functions. Given that it says "yeah, it's invariant" whenever it finds any user which ticks all the boxes, making this check for users from other functions can actually lead to miscompiles.

[DaniilSuchkov]

And another one: https://lab.llvm.org/buildbot/#/builders/5/builds/12562/steps/13/logs/stdio

******************** TEST 'LLVM :: CodeGen/X86/misched-new.ll' FAILED ********************
Script:
--
: 'RUN: at line 1';   /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc < /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/CodeGen/X86/misched-new.ll -mtriple=x86_64-- -mcpu=core2 -x86-early-ifcvt -enable-misched           -misched=shuffle -misched-bottomup -verify-machineinstrs      | /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/FileCheck /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/CodeGen/X86/misched-new.ll
: 'RUN: at line 4';   /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc < /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/CodeGen/X86/misched-new.ll -mtriple=x86_64-- -mcpu=core2 -x86-early-ifcvt -enable-misched           -misched=shuffle -misched-topdown -verify-machineinstrs      | /b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/FileCheck /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/CodeGen/X86/misched-new.ll --check-prefix TOPDOWN
--
Exit Code: 2
Command Output (stderr):
--
=================================================================
==632==ERROR: AddressSanitizer: use-after-poison on address 0x62100006ab10 at pc 0x0000096c272a bp 0x7ffcd29574b0 sp 0x7ffcd29574a8
READ of size 8 at 0x62100006ab10 thread T0
    #0 0x96c2729 in getParent /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/CodeGen/MachineBasicBlock.h:225:53
    #1 0x96c2729 in llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>::getNode(llvm::MachineBasicBlock const*) const /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:352:5
    #2 0x93d9b32 in getNode /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/include/llvm/CodeGen/MachineDominators.h:171:16
    #3 0x93d9b32 in (anonymous namespace)::updateDomTree(llvm::MachineDominatorTree*, (anonymous namespace)::SSAIfConv const&, llvm::ArrayRef<llvm::MachineBasicBlock*>) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/EarlyIfConversion.cpp:814:41
    #4 0x93d1e95 in tryConvertIf /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/EarlyIfConversion.cpp:1037:5
    #5 0x93d1e95 in (anonymous namespace)::EarlyIfConverter::runOnMachineFunction(llvm::MachineFunction&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/EarlyIfConversion.cpp:1071:9
    #6 0x970dd68 in llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:72:13
    #7 0xa54710c in llvm::FPPassManager::runOnFunction(llvm::Function&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1439:27
    #8 0xa562670 in llvm::FPPassManager::runOnModule(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1485:16
    #9 0xa549328 in runOnModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1554:27
    #10 0xa549328 in llvm::legacy::PassManagerImpl::run(llvm::Module&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:542:44
    #11 0x4ca65a0 in compileModule /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:687:8
    #12 0x4ca65a0 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llc/llc.cpp:388:22
    #13 0x7f16128a009a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
    #14 0x4be6899 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/llc+0x4be6899)

The use-after-poison makes me think they're making a query about a block that is already deleted.

[aeubanks]

nice find, looks like Addr might be a global with type i8*, might need a similar fix to the unswitch one like

--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -1068,6 +1068,8 @@ static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
       return false;
     Addr = BC->getOperand(0);
   }
+  if (isa<Constant>(Addr))
+    return false;
 
   unsigned UsesVisited = 0;
   // Traverse all uses of the load operand value, to see if invariant.start is

I managed to repro the stage2 failure and this fix does fix the crash, just need to come up with a reduced test case

[DaniilSuchkov]

In D110751#3037655, @aeubanks wrote:

nice find, looks like Addr might be a global with type i8*, might need a similar fix to the unswitch one like

--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -1068,6 +1068,8 @@ static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
       return false;
     Addr = BC->getOperand(0);
   }
+  if (isa<Constant>(Addr))
+    return false;
 
   unsigned UsesVisited = 0;
   // Traverse all uses of the load operand value, to see if invariant.start is

I managed to repro the stage2 failure and this fix does fix the crash, just need to come up with a reduced test case

I think it's better to just skip the users from other functions within the for (auto *U : Addr->users()) { loop. Because on its own, trying to prove that within current loop/function a load of a global value is invariant, seems reasonable. We just shouldn't take into account the users from other functions.

Btw, thank you for looking into it!

llvm/include/llvm/Support/GenericDomTree.h

bool compare(const DominatorTreeBase &Other) const {
     return false;
   }
 
   /// getNode - return the (Post)DominatorTree node for the specified basic
   /// block.  This is the same as using operator[] on this class.  The result
   /// may (but is not required to) be null for a forward (backwards)
   /// statically unreachable block.
   DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
+    assert((!BB || !BB->getParent() || BB->getParent() == Parent) &&
+           "A node from another function!");
+
     auto I = DomTreeNodes.find(BB);
     if (I != DomTreeNodes.end())
       return I->second.get();
     return nullptr;
   }
 
   /// See getNode.
   DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {