computeKnownBits(const llvm::Value*, llvm::KnownBits&, unsigned int, const {anonymous}::Query&): Assertion `Depth <= MaxDepth && "Limit Search Depth"' failed.

[petrhosek]

Bugzilla Link	34131
Resolution	FIXED
Resolved on	Aug 10, 2017 10:34
Version	trunk
OS	Linux
Blocks	#33196
CC	@zmodem

Extended Description

ld.lld: ../../lib/Analysis/ValueTracking.cpp:1500: void computeKnownBits(const llvm::Value , llvm::KnownBits &, unsigned int, const (anonymous namespace)::Query &): Assertion `Depth <= MaxDepth && "Limit Search Depth"' failed.
#​0 0x00000000020fa7f9 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Support/Unix/Signals.inc:398:11
#​1 0x00000000020fa9a9 PrintStackTraceSignalHandler(void) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Support/Unix/Signals.inc:462:1
#​2 0x00000000020f9013 llvm::sys::RunSignalHandlers() /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Support/Signals.cpp:0:5
#​3 0x00000000020fad04 SignalHandler(int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Support/Unix/Signals.inc:252:1
#​4 0x00007f3b1c7df330 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#​5 0x00007f3b1b3cec37 gsignal /build/eglibc-SvCtMH/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#​6 0x00007f3b1b3d2028 abort /build/eglibc-SvCtMH/eglibc-2.19/stdlib/abort.c:91:0
#​7 0x00007f3b1b3c7bf6 __assert_fail_base /build/eglibc-SvCtMH/eglibc-2.19/assert/assert.c:92:0
#​8 0x00007f3b1b3c7ca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#​9 0x0000000004ec9787 computeKnownBits(llvm::Value const*, llvm::KnownBits&, unsigned int, (anonymous namespace)::Query const&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:1501:23
#​10 0x0000000004ec9706 llvm::computeKnownBits(llvm::Value const*, llvm::KnownBits&, llvm::DataLayout const&, unsigned int, llvm::AssumptionCache*, llvm::Instruction const*, llvm::DominatorTree const*, llvm::OptimizationRemarkEmitter*) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:144:1
#​11 0x0000000004edda54 isTruePredicate(llvm::CmpInst::Predicate, llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, unsigned int)::$_9::operator()(llvm::Value const*, llvm::Value const*, llvm::Value const*&, llvm::APInt const*&, llvm::APInt const*&) const /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4416:9
#​12 0x0000000004edd7a0 isTruePredicate(llvm::CmpInst::Predicate, llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4427:9
#​13 0x0000000004edd54e isImpliedCondOperands(llvm::CmpInst::Predicate, llvm::Value const*, llvm::Value const*, llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4454:67
#​14 0x0000000004ed39d1 isImpliedCondICmps(llvm::ICmpInst const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4558:5
#​15 0x0000000004ed361a llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4621:5
#​16 0x0000000004ed3c94 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4588:24
#​17 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​18 0x0000000004ed3bd2 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4585:24
#​19 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​20 0x0000000004ed3bd2 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4585:24
#​21 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​22 0x0000000004ed3bd2 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4585:24
#​23 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​24 0x0000000004ed3bd2 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4585:24
#​25 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​26 0x0000000004ed3bd2 isImpliedCondAndOr(llvm::BinaryOperator const*, llvm::ICmpInst const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4585:24
#​27 0x0000000004ed3688 llvm::isImpliedCondition(llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, bool, unsigned int) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Analysis/ValueTracking.cpp:4629:7
#​28 0x0000000004b8be89 (anonymous namespace)::SimplifyCFGOpt::SimplifyCondBranch(llvm::BranchInst*, llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Utils/SimplifyCFG.cpp:5765:36
#​29 0x0000000004b8a652 (anonymous namespace)::SimplifyCFGOpt::run(llvm::BasicBlock*) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Utils/SimplifyCFG.cpp:5960:11
#​30 0x0000000004b8a284 llvm::SimplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, unsigned int, llvm::AssumptionCache*, llvm::SmallPtrSetImplllvm::BasicBlock*, bool) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Utils/SimplifyCFG.cpp:5998:3
#​31 0x00000000048f0c8c iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::AssumptionCache, unsigned int, bool) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Scalar/SimplifyCFGPass.cpp:149:11
#​32 0x00000000048effb9 simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::AssumptionCache*, int, bool) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Scalar/SimplifyCFGPass.cpp:164:18
#​33 0x00000000048f0fed (anonymous namespace)::BaseCFGSimplifyPass::runOnFunction(llvm::Function&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/Transforms/Scalar/SimplifyCFGPass.cpp:228:5
#​34 0x00000000052fb13f llvm::FPPassManager::runOnFunction(llvm::Function&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/IR/LegacyPassManager.cpp:1514:27
#​35 0x00000000052fb455 llvm::FPPassManager::runOnModule(llvm::Module&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/IR/LegacyPassManager.cpp:1535:16
#​36 0x00000000052fbbea (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/IR/LegacyPassManager.cpp:1591:27
#​37 0x00000000052fb716 llvm::legacy::PassManagerImpl::run(llvm::Module&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/IR/LegacyPassManager.cpp:1694:16
#​38 0x00000000052fc101 llvm::legacy::PassManager::run(llvm::Module&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/IR/LegacyPassManager.cpp:1725:3
#​39 0x0000000003e60a2d (anonymous namespace)::runOldPMPasses(llvm::lto::Config&, llvm::Module&, llvm::TargetMachine*, bool, llvm::ModuleSummaryIndex*, llvm::ModuleSummaryIndex const*) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/LTO/LTOBackend.cpp:259:10
#​40 0x0000000003e5ec50 (anonymous namespace)::opt(llvm::lto::Config&, llvm::TargetMachine*, unsigned int, llvm::Module&, bool, llvm::ModuleSummaryIndex*, llvm::ModuleSummaryIndex const*) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/LTO/LTOBackend.cpp:0:5
#​41 0x0000000003e5e284 llvm::lto::backend(llvm::lto::Config&, std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_deletellvm::lto::NativeObjectStream > (unsigned int)>, unsigned int, std::unique_ptr<llvm::Module, std::default_deletellvm::Module >, llvm::ModuleSummaryIndex&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/LTO/LTOBackend.cpp:379:9
#​42 0x0000000003e2c854 llvm::lto::LTO::runRegularLTO(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_deletellvm::lto::NativeObjectStream > (unsigned int)>) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/LTO/LTO.cpp:785:10
#​43 0x0000000003e2be95 llvm::lto::LTO::run(std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_deletellvm::lto::NativeObjectStream > (unsigned int)>, std::function<std::function<std::unique_ptr<llvm::lto::NativeObjectStream, std::default_deletellvm::lto::NativeObjectStream > (unsigned int)> (unsigned int, llvm::StringRef)>) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../lib/LTO/LTO.cpp:718:18
#​44 0x000000000228c8bf lld::elf::BitcodeCompiler::compile() /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/ELF/LTO.cpp:176:22
#​45 0x00000000022feb66 void lld::elf::SymbolTable::addCombinedLTOObject<llvm::object::ELFType<(llvm::support::endianness)1, true> >() /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/ELF/SymbolTable.cpp:125:31
#​46 0x00000000021deccd void lld::elf::LinkerDriver::link<llvm::object::ELFType<(llvm::support::endianness)1, true> >(llvm::opt::InputArgList&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/ELF/Driver.cpp:1019:11
#​47 0x00000000021ce879 lld::elf::LinkerDriver::main(llvm::ArrayRef<char const*>, bool) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/ELF/Driver.cpp:390:5
#​48 0x00000000021ce07d lld::elf::link(llvm::ArrayRef<char const*>, bool, llvm::raw_ostream&) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/ELF/Driver.cpp:87:3
#​49 0x000000000203a27e main /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/../../tools/lld/tools/lld/lld.cpp:104:12
#​50 0x00007f3b1b3b9f45 __libc_start_main /build/eglibc-SvCtMH/eglibc-2.19/csu/libc-start.c:321:0
#​51 0x000000000203a029 _start (/usr/local/google/home/phosek/clang-llvm/llvm/out/lld/bin/ld.lld+0x203a029)
Stack dump:
0. Program arguments: /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/bin/ld.lld --reproduce=lto-crash.cpio -nostdlib --build-id -m elf_x86_64 -z max-page-size=4096 -z combreloc -z relro -z now -z text --hash-style=gnu --eh-frame-hdr -z defs -shared -soname libhypervisor.so ./build-magenta-pc-x86-64-clang/system/ulib/hypervisor/system/ulib/hypervisor/acpi.c.o ./build-magenta-pc-x86-64-clang/system/ulib/hypervisor/system/ulib/hypervisor/block.c.o ./build-magenta-pc-x86-64-clang/system/ulib/hypervisor/system/ulib/hypervisor/guest.c
.o ./build-magenta-pc-x86-64-clang/system/ulib/hypervisor/system/ulib/hypervisor/vcpu.c.o ./build-magenta-pc-x86-64-clang/system/ulib/hypervisor/system/ulib/hypervisor/decode.c.o scripts/dso_handle.ld ./build-magenta-pc-x86-64-clang/system/ulib/ddk/libddk.a ./build-magenta-pc-x86-64-clang/system/ulib/virtio/libvirtio.a ./build-magenta-pc-x86-64-clang/third_party/ulib/acpica/libacpica.a ./build-magenta-pc-x86-64-clang/system/ulib/c/libc.so.abi ./build-magenta-pc-x86-64-clang/system/ulib/magenta/libmagenta.so.abi ./build-magenta-pc-x86-64-cla
ng/system/ulib/mxio/libmxio.so.abi /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/lib/clang/6.0.0/lib/fuchsia/libclang_rt.builtins-x86_64.a -o build-magenta-pc-x86-64-clang/system/ulib/hypervisor/libhypervisor.so

1.  Running pass 'Function Pass Manager' on module 'ld-temp.o'.
   

2.  Running pass 'Simplify the CFG' on function '@AcpiUtDumpBuffer'
   

zsh: abort (core dumped) /usr/local/google/home/phosek/clang-llvm/llvm/out/lld/bin/ld.lld -nostdlib

[petrhosek]

Reproducer is https://storage.googleapis.com/fuchsia-build/lld/lto-crash.cpio

[llvmbot]

I don't think this is an lld bug.

[llvmbot]

testcase

[llvmbot]

$ ./opt red.ll -simplifycfg
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

opt: ../lib/Analysis/ValueTracking.cpp:1460: void computeKnownBits(const llvm::Value*, llvm::KnownBits&, unsigned int, const {anonymous}::Query&): Assertion `Depth <= MaxDepth && "Limit Search Depth"' failed.

[llvmbot]

Tentatively marking as release blocker.

[llvmbot]

https://reviews.llvm.org/D36512

[llvmbot]

Patch LGTM with one minor comment. IMHO, this should be cherry-picked to the 5.0.0 release branch.

[llvmbot]

r310481

[zmodem]

r310481

Let's have it bake on trunk for a little bit, then I'll merge it. (Note to self, also r310492.)

[llvmbot]

r310481

Let's have it bake on trunk for a little bit, then I'll merge it. (Note to
self, also r310492.)

It seems that the output of simplifycfg is non-deterministic (difference between debug and release), but it's largely unrelated to this patch.
I recommend to also cherry pick the commit that disables the test output
https://reviews.llvm.org/rL310510

I'll investigate the non-determinism in the meanwhile, sigh :(

[zmodem]

Merged r310481, r310492 and r310510 in r310634.