[SCCP] Remove forcedconstant, go to overdefined instead

[fhahn]

Summary

This patch removes forcedconstant to simplify things for the
move to ValueLattice, which includes constant ranges, but no
forced constants.

This patch removes forcedconstant and changes ResolvedUndefsIn
to mark instructions with unknown operands as overdefined. This
means we do not do simplifications based on undef directly in SCCP
any longer, but this seems to hardly come up in practice (see stats
below), presumably because InstCombine & others take care
of most of the relevant folds already.

It is still beneficial to keep ResolvedUndefIn, as it allows us delaying
going to overdefined until we propagated all known information.

I also built MultiSource, SPEC2000 and SPEC2006 and compared
sccp.IPNumInstRemoved and sccp.NumInstRemoved. It looks like the impact
is quite low:

Tests: 244
Same hash: 238 (filtered out)
Remaining: 6
Metric: sccp.IPNumInstRemoved

Program base patch diff
test-suite...arks/VersaBench/dbms/dbms.test 4.00 3.00 -25.0%
test-suite...TimberWolfMC/timberwolfmc.test 38.00 34.00 -10.5%
test-suite...006/453.povray/453.povray.test 158.00 155.00 -1.9%
test-suite.../CINT2000/176.gcc/176.gcc.test 668.00 668.00 0.0%
test-suite.../CINT2006/403.gcc/403.gcc.test 1209.00 1209.00 0.0%
test-suite...arks/mafft/pairlocalalign.test 76.00 76.00 0.0%

Tests: 244
Same hash: 238 (filtered out)
Remaining: 6
Metric: sccp.NumInstRemoved

Program base patch diff
test-suite...arks/mafft/pairlocalalign.test 185.00 175.00 -5.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 2059.00 2056.00 -0.1%
test-suite.../CINT2000/176.gcc/176.gcc.test 2358.00 2357.00 -0.0%
test-suite...006/453.povray/453.povray.test 317.00 317.00 0.0%
test-suite...TimberWolfMC/timberwolfmc.test 12.00 12.00 0.0%

[fhahn]

Rebased

[merge_guards_bot]

Unit tests: fail. 61088 tests passed, 1 failed and 728 were skipped.

failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_recursive/lock.pass.cpp

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[fhahn]

Another rebase after splitting up patches.

[merge_guards_bot]

Unit tests: fail. 61133 tests passed, 1 failed and 728 were skipped.

failed: Clang.SemaOpenCL/numbered-address-space.cl

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[efriedma]

You aren't really removing forcedconstant, here; instead, you're basically making every constant behave like a forcedconstant (it can be merged with another constant). I'm not very confident our extension of the SCCP algorithm to include forcedconstants is truly sound. And I think constructing ConstantRanges out of forcedconstants makes the whole foundation shakier; I'm afraid you could end up constructing a contradiction because we don't ever force the value of the forcedconstant.

I'd be much more comfortable with pretending that undef is an opaque constant, like a GlobalValue. That makes the whole algorithm much closer to a textbook algorithm, and it should be essentially sound, I think. If we don't manipulate UndefValues except through ConstantExpr folding, it should be sound as long as ConstantExpr folding is itself sound. And we don't have to do any extra work as undef gets replaced with poison. (Once we have poison constants, I think we can treat them as Unknown without any special logic.)

[efriedma]

I'm not planning to continue reviewing the rest of the patches in this series until my comment here is addressed. Does that make sense?

[fhahn]

In D61314#1836341, @efriedma wrote:

I'm not planning to continue reviewing the rest of the patches in this series until my comment here is addressed. Does that make sense?

Yes that makes a lot of sense, thank you! IIUC your suggestion is independent of the ConstantRange extension and I'll try to put up a patch on top of current master.

[fhahn]

Update the patch to remove forcedconstant and only folding explicit undefs.

I'll update the description. Eli, it would be great if you could have a look to check if that makes sense to you now.

[efriedma]

I'd prefer to get rid of ResolveUndefsIn completely, if possible. If we don't special-case UndefValue anywhere in SCCP, that should just work, I think? SCCP should still be correct even though UndefValue isn't a "normal" constant; it doesn't try to make assumptions based on the pointer equivalence of two "constant" values, except for joins like PHI nodes where it shouldn't matter. Am I missing something? How much optimization power do we lose that way, versus this patch's approach?

The approach here is a little different from that. I'm understanding it correctly, the idea is that in cases where we can't prove a forced constant is actually constant, we instead go straight to overdefined? So we sort of keep our "undef=>undefined" extension of the SCCP model, but get rid of the shakiest part of it? That should work, I think... but I'm not sure the whole ResolvedUndefsIn is giving you any significant benefit at that point. At least, I can't think of a case off the top of my head where it helps. Maybe I'm forgetting something.

I'm not completely confident calling Simplify* with operands that aren't Constants does the right thing here; that's sort of an extension to the algorithm. I guess it should work, though?

Does this patch in its current form still depend on any of the other patches?

[efriedma]

Oh, hmm, in terms of optimization I guess you get some benefit from making assumptions about the behavior of undef, instead of only interacting with it through constant folding. You get better results by implicitly unifying UndefValue with other constants in PHI nodes and call arguments, and forcing branches one way instead of both ways. Maybe this is better than completely dropping ResolveUndefsIn. Maybe this approach is fine, then.

I'd prefer to finish and land this first, and let it bake a little while, before landing the other pieces. It seems a little riskier than the rest, since it's really hard to reason about undef-related changes.

[fhahn]

Removed simplifications based on undef, just go to overdefined directly.

In D61314#1864913, @efriedma wrote:

I'd prefer to get rid of ResolveUndefsIn completely, if possible. If we don't special-case UndefValue anywhere in SCCP, that should just work, I think? SCCP should still be correct even though UndefValue isn't a "normal" constant; it doesn't try to make assumptions based on the pointer equivalence of two "constant" values, except for joins like PHI nodes where it shouldn't matter. Am I missing something? How much optimization power do we lose that way, versus this patch's approach?

The approach here is a little different from that. I'm understanding it correctly, the idea is that in cases where we can't prove a forced constant is actually constant, we instead go straight to overdefined? So we sort of keep our "undef=>undefined" extension of the SCCP model, but get rid of the shakiest part of it? That should work, I think... but I'm not sure the whole ResolvedUndefsIn is giving you any significant benefit at that point. At least, I can't think of a case off the top of my head where it helps. Maybe I'm forgetting something.

I think this and the first paragraph are addressed in the comments later on.

I'm not completely confident calling Simplify* with operands that aren't Constants does the right thing here; that's sort of an extension to the algorithm. I guess it should work, though?

The calls to Simplify* mostly took care of folding existing undef constants. There are a few tests that check for that, but in practice it seems to not really pop up, as other passes should clean up those. I've also compared the stats to the previous version of the patch, and there are no changes.

Does this patch in its current form still depend on any of the other patches?

No, it does not. I've removed the dependencies.

Oh, hmm, in terms of optimization I guess you get some benefit from making assumptions about the behavior of undef, instead of only interacting with it through constant folding. You get better results by implicitly unifying UndefValue with other constants in PHI nodes and call arguments, and forcing branches one way instead of both ways. Maybe this is better than completely dropping ResolveUndefsIn. Maybe this approach is fine, then.

Yes I think there is a benefit of delaying resolving undefs till we finished with an iteration, as we might discover a concrete value later, e.g. for PHIs where we discover that some predecessors are executable later in the iteration. As is I think the patch removes all forced-constant related machinery, which should be the most problematic part of ResolvedUndefsIn.

I'd prefer to finish and land this first, and let it bake a little while, before landing the other pieces. It seems a little riskier than the rest, since it's really hard to reason about undef-related changes.

Sounds good! What do you think of the latest version of the patch? The remainder of ResolvedUndefsIn deals with undef constants as branch conditions. I think keeping those should be save, as they do not really interact with the lattice values.

[efriedma]

LGTM

I'm surprised this works so well, but I'm very happy to get rid of forcedconstant if there isn't a practical performance impact.

[fhahn]

In D61314#1868393, @efriedma wrote:

LGTM

I'm surprised this works so well, but I'm very happy to get rid of forcedconstant if there isn't a practical performance impact.

Thanks Eli! I'll collected the stats again and the impact seems very low, as indicated, but I'll make sure to keep an eye out for any performance regressions.

[nathanchance]

The Linux kernel hits the assert in markConstant on arm32 defconfig in net/mac80211/sta_info.o, as reported by Linaro's CI:

00:14:30 clang: /home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-src/lib/Transforms/Scalar/SCCP.cpp:131: bool {anonymous}::LatticeVal::markConstant(llvm::Constant*): Assertion `isUnknown()' failed.
00:14:30 Stack dump:
00:14:30 0.	Program arguments: /home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang -Wp,-MD,net/mac80211/.sta_info.o.d -nostdinc -isystem /home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/lib/clang/11.0.0/include -I./arch/arm/include -I./arch/arm/include/generated -I./include -I./arch/arm/include/uapi -I./arch/arm/include/generated/uapi -I./include/uapi -I./include/generated/uapi -include ./include/linux/kconfig.h -include ./include/linux/compiler_types.h -D__KERNEL__ -mbig-endian -Qunused-arguments -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -std=gnu89 --target=arm-linux-gnueabihf --prefix=/usr/bin/ --gcc-toolchain=/usr -no-integrated-as -Werror=unknown-warning-option -fno-dwarf2-cfi-asm -mabi=aapcs-linux -mfpu=vfp -funwind-tables -meabi gnu -marm -Wa,-mno-warn-deprecated -D__LINUX_ARM_ARCH__=6 -march=armv6k -mtune=arm1136j-s -msoft-float -Uarm -fno-delete-null-pointer-checks -Wno-address-of-packed-member -O2 -Wframe-larger-than=1024 -fstack-protector-strong -Wno-format-invalid-specifier -Wno-gnu -Wno-tautological-compare -mno-global-merge -Wno-unused-const-variable -ftrivial-auto-var-init=pattern -pg -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -fno-strict-overflow -fno-merge-all-constants -fno-stack-check -Werror=date-time -Werror=incompatible-pointer-types -fmacro-prefix-map=./= -Wno-initializer-overrides -Wno-format -Wno-sign-compare -Wno-format-zero-length -DDEBUG -fsanitize-coverage=trace-pc -fsanitize-coverage=trace-cmp -DKBUILD_MODFILE="net/mac80211/mac80211" -DKBUILD_BASENAME="sta_info" -DKBUILD_MODNAME="mac80211" -c -o net/mac80211/sta_info.o net/mac80211/sta_info.c 
00:14:30 1.	<eof> parser at end of file
00:14:30 2.	Per-module optimization passes
00:14:30 3.	Running pass 'Interprocedural Sparse Conditional Constant Propagation' on module 'net/mac80211/sta_info.c'.
00:14:31  #0 0x000055995af27e4a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1b48e4a)
00:14:31  #1 0x000055995af25944 llvm::sys::RunSignalHandlers() (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1b46944)
00:14:31  #2 0x000055995af25bb5 llvm::sys::CleanupOnSignal(unsigned long) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1b46bb5)
00:14:31  #3 0x000055995ae9cf38 CrashRecoverySignalHandler(int) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1abdf38)
00:14:31  #4 0x00007f9138484890 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12890)
00:14:31  #5 0x00007f9137135e97 raise /build/glibc-OTsEL5/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
00:14:31  #6 0x00007f9137137801 abort /build/glibc-OTsEL5/glibc-2.27/stdlib/abort.c:81:0
00:14:31  #7 0x00007f913712739a __assert_fail_base /build/glibc-OTsEL5/glibc-2.27/assert/assert.c:89:0
00:14:31  #8 0x00007f9137127412 (/lib/x86_64-linux-gnu/libc.so.6+0x30412)
00:14:31  #9 0x000055995ae0aced (anonymous namespace)::LatticeVal::markConstant(llvm::Constant*) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a2bced)
00:14:31 #10 0x000055995ae0cf33 (anonymous namespace)::SCCPSolver::markConstant(llvm::Value*, llvm::Constant*) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a2df33)
00:14:31 #11 0x000055995ae12875 llvm::InstVisitor<(anonymous namespace)::SCCPSolver, void>::visit(llvm::Instruction&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a33875)
00:14:31 #12 0x000055995ae133de (anonymous namespace)::SCCPSolver::markUsersAsChanged(llvm::Value*) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a343de)
00:14:31 #13 0x000055995ae1389c (anonymous namespace)::SCCPSolver::Solve() (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a3489c)
00:14:31 #14 0x000055995ae1511f llvm::runIPSCCP(llvm::Module&, llvm::DataLayout const&, std::function<llvm::TargetLibraryInfo const& (llvm::Function&)>, llvm::function_ref<llvm::AnalysisResultsForFn (llvm::Function&)>) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1a3611f)
00:14:31 #15 0x000055995aa73269 (anonymous namespace)::IPSCCPLegacyPass::runOnModule(llvm::Module&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1694269)
00:14:31 #16 0x000055995a9342b1 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x15552b1)
00:14:31 #17 0x000055995b14d70d (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1d6e70d)
00:14:31 #18 0x000055995b14f195 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1d70195)
00:14:31 #19 0x000055995bc60bf5 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2881bf5)
00:14:31 #20 0x000055995c572379 clang::ParseAST(clang::Sema&, bool, bool) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x3193379)
00:14:31 #21 0x000055995bc60d78 clang::CodeGenAction::ExecuteAction() (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2881d78)
00:14:31 #22 0x000055995b694419 clang::FrontendAction::Execute() (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x22b5419)
00:14:31 #23 0x000055995b653352 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2274352)
00:14:31 #24 0x000055995b743b0c clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2364b0c)
00:14:31 #25 0x0000559959f99d14 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0xbbad14)
00:14:31 #26 0x0000559959f950c9 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0xbb60c9)
00:14:31 #27 0x000055995b535e55 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::'lambda'()>(long) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2156e55)
00:14:31 #28 0x000055995ae9d013 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x1abe013)
00:14:31 #29 0x000055995b536938 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2157938)
00:14:31 #30 0x000055995b512215 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2133215)
00:14:31 #31 0x000055995b512cd1 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x2133cd1)
00:14:31 #32 0x000055995b51b129 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0x213c129)
00:14:31 #33 0x0000559959f29a7f main (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0xb4aa7f)
00:14:31 #34 0x00007f9137118b97 __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:344:0
00:14:31 #35 0x0000559959f94c2a _start (/home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin/clang+0xbb5c2a)
00:14:31 clang-11: error: clang frontend command failed due to signal (use -v to see invocation)
00:14:31 clang version 11.0.0 
00:14:31 Target: arm-unknown-linux-gnueabihf
00:14:31 Thread model: posix
00:14:31 InstalledDir: /home/tcwg-buildslave/workspace/tcwg_kernel_1/llvm-install/bin
00:14:31 clang-11: note: diagnostic msg: PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
00:14:31 clang-11: note: diagnostic msg: 
00:14:31 ********************
00:14:31 
00:14:31 PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
00:14:31 Preprocessed source(s) and associated run script(s) are located at:
00:14:31 clang-11: note: diagnostic msg: /tmp/sta_info-eeebaf.c
00:14:31 clang-11: note: diagnostic msg: /tmp/sta_info-eeebaf.sh
00:14:31 clang-11: note: diagnostic msg: 
00:14:31 
00:14:31 ********************
00:14:31 LLVM ERROR: out of memory
00:14:31 Aborted (core dumped)

I've creduce'd it down to

enum { a };
enum b { c, d };
e;
static _Bool g(struct f *h, enum b i) {
  i &&j();
  return a;
}
static k(char h, enum b i) {
  _Bool l = g(e, i);
  l;
}
m(h) {
  k(h, c);
  g(h, d);
}

The full preprocessed file and interestingness test are available here: https://github.com/nathanchance/creduce-files/tree/872520243c62229267aa0ad0b091a5f4e6e1e2be/aadb635e04854220064b77cc10d0e6772f5492fd

[mstorsjo]

In D61314#1871290, @nathanchance wrote:

The Linux kernel hits the assert in markConstant on arm32 defconfig in net/mac80211/sta_info.o, as reported by Linaro's CI:

FWIW, I also hit this assert, when building Qt in qfontsubset.cpp for x86_64 and aarch64 mingw.

[fhahn]

Thanks, I've managed to reproduce the issue and reverted the change while I investigate.

[fhahn]

I've recommitted the change with a fix as rGbb310b3f73dd . The issue was related to the fact that we skip calls to tracked functions, but we might mark one of the users of the result as overdefined. If we later discover that the result of the call is constant, we try in some cases to mark an overdefined value as constant. I think in theory we also had the same issue without the patch, but got lucky that in case we mark a user of a function result as overdefined the corresponding visitor bails out early if the instruction is overdefined.

As a fix, we can skip instructions depending on tracked and unknown calls. Once we resolve the call result, we propagate it to the users. This also allows us the handle a few additional cases.

[efriedma]

I was thinking about this a bit more, and I'm not sure this is enough to allow value ranges to work correctly around undef.

The problem essentially boils down to this: what happens when an instruction that might return undef is marked "constantrange"? If an instruction is marked "constant", it doesn't really matter if it really returns "constant or undef": SCCP will RAUW the instruction away, so it can't produce undef after SCCP runs. If it's a constantrange, though, we never RAUW the value, so the "undef" case never goes away. And if it's undef, it could be outside the computed range, and we could drop necessary arithmetic/comparisons. For example, suppose we compute a value X is in range 0-255, and then we "and X, 255". It looks like we could drop the "and"... but we never actually eliminated the possibility that the value was undef. So now we've transformed "and undef, 255" -> "undef", which is wrong.

This problem specifically comes up because we resolve undefs "late", I think: if we treated undef as an overdefined value at the point where we initially analyzed it, this case wouldn't come up.

[fhahn]

In D61314#1879602, @efriedma wrote:

I was thinking about this a bit more, and I'm not sure this is enough to allow value ranges to work correctly around undef.

The problem essentially boils down to this: what happens when an instruction that might return undef is marked "constantrange"? If an instruction is marked "constant", it doesn't really matter if it really returns "constant or undef": SCCP will RAUW the instruction away, so it can't produce undef after SCCP runs. If it's a constantrange, though, we never RAUW the value, so the "undef" case never goes away. And if it's undef, it could be outside the computed range, and we could drop necessary arithmetic/comparisons. For example, suppose we compute a value X is in range 0-255, and then we "and X, 255". It looks like we could drop the "and"... but we never actually eliminated the possibility that the value was undef. So now we've transformed "and undef, 255" -> "undef", which is wrong.

I thought a bit more about the cases where we generate ranges:

1. Ops with all operands either constant/constant range (e.g. add, sub, mul, select)
2. Range restricting ops with overdefined, constant/constant range operands (e.g. and overdefined, [0, 255])
3. Phis with multiple live incoming values
4. Function arguments with multiple call sites.

I think for 1. and 2., we should never generate a concrete range, if any of the operands may be undef as in your example. As long as any operand is unknown/undef, we wait until ResolvedUndefsIn.

In 3. and 4. we could however generate concrete ranges when one of the incoming values/concrete arguments may be undef. For phi nodes for example, the current implementation just skips incoming unknown/undefined values. If one of the incoming values is a range 0-255 and the other incoming value is undef, we end up with a value X as you described. I think we could however handle this directly in visitPhiNode: if some of the incoming values are unknown and some others are non-singleton constant ranges we have to go to overdefined.

I think we can deal with 4. in a similar fashion: when merging function arguments, we need to go to overdefined once we merge in an unknown/undef value and a (non singleton) constant range.

I think that should ensure we never construct a concrete range for a value that might be undef. I hope I didn't miss any cases. What do you think?

[fhahn]

In D61314#1879702, @fhahn wrote:

In D61314#1879602, @efriedma wrote:

I was thinking about this a bit more, and I'm not sure this is enough to allow value ranges to work correctly around undef.

The problem essentially boils down to this: what happens when an instruction that might return undef is marked "constantrange"? If an instruction is marked "constant", it doesn't really matter if it really returns "constant or undef": SCCP will RAUW the instruction away, so it can't produce undef after SCCP runs. If it's a constantrange, though, we never RAUW the value, so the "undef" case never goes away. And if it's undef, it could be outside the computed range, and we could drop necessary arithmetic/comparisons. For example, suppose we compute a value X is in range 0-255, and then we "and X, 255". It looks like we could drop the "and"... but we never actually eliminated the possibility that the value was undef. So now we've transformed "and undef, 255" -> "undef", which is wrong.

I thought a bit more about the cases where we generate ranges:

1. Ops with all operands either constant/constant range (e.g. add, sub, mul, select)
2. Range restricting ops with overdefined, constant/constant range operands (e.g. and overdefined, [0, 255])
3. Phis with multiple live incoming values
4. Function arguments with multiple call sites.

I think for 1. and 2., we should never generate a concrete range, if any of the operands may be undef as in your example. As long as any operand is unknown/undef, we wait until ResolvedUndefsIn.

In 3. and 4. we could however generate concrete ranges when one of the incoming values/concrete arguments may be undef. For phi nodes for example, the current implementation just skips incoming unknown/undefined values. If one of the incoming values is a range 0-255 and the other incoming value is undef, we end up with a value X as you described. I think we could however handle this directly in visitPhiNode: if some of the incoming values are unknown and some others are non-singleton constant ranges we have to go to overdefined.

I think we can deal with 4. in a similar fashion: when merging function arguments, we need to go to overdefined once we merge in an unknown/undef value and a (non singleton) constant range.

I think that should ensure we never construct a concrete range for a value that might be undef. I hope I didn't miss any cases. What do you think?

Coincidentally a (I think) related bug just got filed, where LVI gets this wrong for PHIs, as you described. I think to fix is have ValueLattice::mergeIn([x, y], undef) -> overdefined instead of the current result [x, y]
(https://bugs.llvm.org/show_bug.cgi?id=44949)

[efriedma]

I think we could however handle this directly in visitPhiNode: if some of the incoming values are unknown and some others are non-singleton constant ranges we have to go to overdefined.

If you treat unknown as if it were overdefined, you lose some of the nice properties of the sparse conditional propagation: in particular, that you get the same result regardless of the visitation order. You'll get weird results in cases that don't actually involve any undef values.

[fhahn]

In D61314#1881054, @efriedma wrote:

I think we could however handle this directly in visitPhiNode: if some of the incoming values are unknown and some others are non-singleton constant ranges we have to go to overdefined.

If you treat unknown as if it were overdefined, you lose some of the nice properties of the sparse conditional propagation: in particular, that you get the same result regardless of the visitation order. You'll get weird results in cases that don't actually involve any undef values.

Right, I hoped the way we mark blocks/edges as executable should take care of most cases not involving actual undef values. But maybe it is better to just treat undef constants as overdefined at construction. I initially was not sure if that would be enough, but I think it should be. Either way, I think both approaches should rule out the problem outline I think. I'll check the impact of both approaches and I;ll put up a follow up patch. Does that sounds good?

[efriedma]

Yes, that sounds fine

[fhahn]

In D61314#1881334, @efriedma wrote:

Yes, that sounds fine

I'll probably will get the results early next week. I first have to add handling for AND to limit the ranges.

I also pushed a small follow up fix 99809f98d7bb which excludes loads from being marked as overdefined in ResolvedUndefsIn, as this breaks an invariant that all non-store users of unknown constants are replaced and causes a crash. I think that should be fine, especially as it is not related to forcedconstants, but please let me know if you have any concerns, then I'll revert this again.

[fhahn]

I've added another patch that implements AND overdefined, constant range -> constant range (D75054). With that, I checked compared the impact of

1. making ValueLatticeElement::mergeIn go to overdefined, if a constant range is merged with an undefined value
2. Using overdefined for undef constant when we create the ValueLatticeElement.

Comparing 1. and 2. for MultiSource, SPEC2000, SPEC2006 with -O3 & LTO below (sorry for the weird formatting, not sure how to post the output of compare.py better on phab). It seems like the impact of 1. is lower, presumably because we skip incoming values from unreachable blocks in PHIs. I've also added some stats for the impact on CorrelatedValuePropagation in the description of D75054.

it would be great if you could take another look and let me know which direction you prefer.

Sum of all SCCP stats (using cat report.json | grep sccp | cut -d" " -f 10 | cut -d',' -f 1 | awk '{s+=$1} END {print s}')

Base: 220147

1. : 220062
2. : 218205

Program 1. 2.
test-suite...T2000/300.twolf/300.twolf.test 179.00 64.00 -64.2%
test-suite...stones-3.1/fhourstones3.1.test 8.00 3.00 -62.5%
test-suite...lications/minisat/minisat.test 7.00 3.00 -57.1%
test-suite...abench/jpeg/jpeg-6a/cjpeg.test 39.00 19.00 -51.3%
test-suite...ocBench/espresso/espresso.test 131.00 64.00 -51.1%
test-suite...nsumer-jpeg/consumer-jpeg.test 42.00 22.00 -47.6%
test-suite...nchmarks/McCat/09-vor/vor.test 39.00 21.00 -46.2%
test-suite...cations/hexxagon/hexxagon.test 28.00 16.00 -42.9%
test-suite...ve-susan/automotive-susan.test 67.00 43.00 -35.8%
test-suite...Source/Benchmarks/sim/sim.test 24.00 16.00 -33.3%
test-suite...129.compress/129.compress.test 90.00 64.00 -28.9%
test-suite...urce/Applications/hbd/hbd.test 30.00 23.00 -23.3%
test-suite.../Benchmarks/Bullet/bullet.test 233.00 186.00 -20.2%
test-suite...langs-C/unix-tbl/unix-tbl.test 12.00 10.00 -16.7%
test-suite...INT95/132.ijpeg/132.ijpeg.test 100.00 84.00 -16.0%
test-suite...lications/ClamAV/clamscan.test 854.00 722.00 -15.5%
test-suite.../CINT2000/252.eon/252.eon.test 349.00 297.00 -14.9%
test-suite...lications/SIBsim4/SIBsim4.test 16.00 14.00 -12.5%
test-suite...CFP2000/177.mesa/177.mesa.test 256.00 227.00 -11.3%
test-suite...lications/sqlite3/sqlite3.test 473.00 422.00 -10.8%
test-suite...oxyApps-C++/miniFE/miniFE.test 28.00 25.00 -10.7%
test-suite.../CINT2000/176.gcc/176.gcc.test 1015.00 920.00 -9.4%
test-suite...TimberWolfMC/timberwolfmc.test 43.00 39.00 -9.3%
test-suite.../CINT95/134.perl/134.perl.test 86.00 78.00 -9.3%
test-suite...T2006/445.gobmk/445.gobmk.test 1563.00 1422.00 -9.0%
test-suite...SPEC/CINT95/130.li/130.li.test 103.00 94.00 -8.7%
test-suite...006/447.dealII/447.dealII.test 449.00 411.00 -8.5%
test-suite...ce/Applications/Burg/burg.test 26.00 24.00 -7.7%
test-suite...marks/SciMark2-C/scimark2.test 26.00 24.00 -7.7%
test-suite.../CINT2006/403.gcc/403.gcc.test 3684.00 3438.00 -6.7%
test-suite...pplications/oggenc/oggenc.test 222.00 208.00 -6.3%
test-suite...urce/Applications/lua/lua.test 263.00 247.00 -6.1%
test-suite...plications/d/make_dparser.test 51.00 48.00 -5.9%
test-suite...3.xalancbmk/483.xalancbmk.test 3807.00 3604.00 -5.3%
test-suite...nsumer-lame/consumer-lame.test 192.00 182.00 -5.2%
test-suite...CFP2006/444.namd/444.namd.test 195.00 186.00 -4.6%
test-suite...yApps-C++/PENNANT/PENNANT.test 204.00 195.00 -4.4%
test-suite...encode/alacconvert-encode.test 52.00 50.00 -3.8%
test-suite...decode/alacconvert-decode.test 52.00 50.00 -3.8%
test-suite...Applications/kimwitu++/kc.test 646.00 626.00 -3.1%
test-suite...0.perlbench/400.perlbench.test 1580.00 1538.00 -2.7%
test-suite...ProxyApps-C++/CLAMR/CLAMR.test 312.00 304.00 -2.6%
test-suite...marks/7zip/7zip-benchmark.test 4790.00 4670.00 -2.5%
test-suite...CFP2006/433.milc/433.milc.test 201.00 196.00 -2.5%
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 87.00 85.00 -2.3%
test-suite...chmarks/MallocBench/gs/gs.test 397.00 388.00 -2.3%
test-suite...006/450.soplex/450.soplex.test 426.00 418.00 -1.9%
test-suite...ications/JM/ldecod/ldecod.test 152.00 150.00 -1.3%
test-suite.../Applications/SPASS/SPASS.test 2019.00 1996.00 -1.1%
test-suite...0/253.perlbmk/253.perlbmk.test 944.00 935.00 -1.0%
test-suite...rks/tramp3d-v4/tramp3d-v4.test 342.00 339.00 -0.9%
test-suite...6/471.omnetpp/471.omnetpp.test 418.00 415.00 -0.7%
test-suite...:: External/Povray/povray.test 1438.00 1436.00 -0.1%
test-suite...-typeset/consumer-typeset.test 3172.00 3169.00 -0.1%
test-suite...ications/JM/lencod/lencod.test 8296.00 8291.00 -0.1%
test-suite...lFlow-dbl/ControlFlow-dbl.test 520.00 520.00 0.0%

Metric: sccp.NumInstRemoved

Program 1. 2.
test-suite...:: External/Povray/povray.test 191.00 179.00 -6.3%
test-suite...marks/7zip/7zip-benchmark.test 1154.00 1109.00 -3.9%
test-suite...chmarks/MallocBench/gs/gs.test 159.00 154.00 -3.1%
test-suite...006/453.povray/453.povray.test 608.00 590.00 -3.0%
test-suite.../Benchmarks/Bullet/bullet.test 585.00 576.00 -1.5%
test-suite...urce/Applications/lua/lua.test 431.00 427.00 -0.9%
test-suite.../CINT2000/252.eon/252.eon.test 235.00 233.00 -0.9%
test-suite...lications/ClamAV/clamscan.test 1116.00 1111.00 -0.4%
test-suite...0.perlbench/400.perlbench.test 1143.00 1141.00 -0.2%
test-suite...rks/tramp3d-v4/tramp3d-v4.test 6745.00 6737.00 -0.1%
test-suite...CFP2000/177.mesa/177.mesa.test 1641.00 1640.00 -0.1%
test-suite...006/447.dealII/447.dealII.test 12050.00 12043.00 -0.1%
test-suite.../CINT2006/403.gcc/403.gcc.test 7210.00 7211.00 0.0%

[efriedma]

presumably because we skip incoming values from unreachable blocks in PHIs

That doesn't make any sense. We should skip incoming values from unreachable blocks no matter what they contain. I assume the significant difference between the two approaches is that one is special-casing merging undef and a constant.

I'm curious about two other possibilities:

1. Use overdefined for undef constants, but add a special case for PHI nodes with a literal "undef" operand.
2. Treat undef as if it were an opaque constant, like a constant expression you can't analyze, instead of going straight to overdefined, then again add a special case for PHI nodes with a constant undef operand.

[fhahn]

In D61314#1889975, @efriedma wrote:

presumably because we skip incoming values from unreachable blocks in PHIs

That doesn't make any sense. We should skip incoming values from unreachable blocks no matter what they contain. I assume the significant difference between the two approaches is that one is special-casing merging undef and a constant.

Ah yes, my wording got mixed up here, sorry! The point I wanted to make is that we seem to not loose much in terms of precision by mergeIn(ConstantRange, unknown) -> overdefined.

I'm curious about two other possibilities:

1. Use overdefined for undef constants, but add a special case for PHI nodes with a literal "undef" operand.

This seems to have no impact. I've changed getValueState to mark UndefValue constants as overdefined and then added a special case to visitPHINode, which skips incoming UndefValues if the PHI has a constant value. getValueState. (D75122) I think should be along the lines you suggested here.

2. Treat undef as if it were an opaque constant, like a constant expression you can't analyze, instead of going straight to overdefined, then again add a special case for PHI nodes with a constant undef operand.

I started with this approach, but it seemed like it would require updating lots of places where we handle constants which do not expect it to be undef.

I've tried a slightly different approach (see D75120), which I think is quite similar in spirit: add a new undef lattice state, which can be merged with constants, but merging it with non-singleton ranges goes to overdefined. I think that makes it easier to update the code. Most places in SCCP can treat it similar to unknown, in that we can delay marking instructions with undef operands as overdefined until we finished solving. Is that approach roughly along the direction you suggested? For cases like %p = phi [undef], [0] %foo = add %p, 1, it is important to not mark %foo overdefined before we merged all incoming values of %p. Without delaying solving instructions with undef operands, we would have to mark %foo overdefined once we have %p == undef.

Also, from the comments in ValueLattice.h and in LVI, it seems the code expects unknown to mean unreachable/dead, which is slightly different to undef and the new state would help to clarify this.

[efriedma]

Adding an explicit "undef" lattice state makes sense, I think; it should allow modeling everything we need correctly.

Also, from the comments in ValueLattice.h and in LVI, it seems the code expects unknown to mean unreachable/dead, which is slightly different to undef and the new state would help to clarify this.

Yes, I'm happier reserving unknown for unvisited values. It wouldn't be too much of a stretch to also use it for poison values, since they have similar properties in terms of the lattice. (Granted, we don't try to model poison in SCCP at the moment.)

llvm/lib/Transforms/Scalar/SCCP.cpp

 class LatticeVal {
   enum LatticeValueTy {
     /// unknown - This LLVM Value has no known value yet.
     unknown,
 
     /// constant - This LLVM Value has a specific constant value.
     constant,
 
-    /// forcedconstant - This LLVM Value was thought to be undef until
-    /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
-    /// with another (different) constant, it goes to overdefined, instead of
-    /// asserting.
-    forcedconstant,
-
     /// overdefined - This instruction is not known to be constant, and we know
     /// it has a value.
     overdefined
   };
 
   /// Val: This stores the current lattice value along with the Constant* for
-  /// the constant if this is a 'constant' or 'forcedconstant' value.
+  /// the constant if this is a 'constant' value.
   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
 
   LatticeValueTy getLatticeValue() const {
     return Val.getInt();
   }
 
 public:
   LatticeVal() : Val(nullptr, unknown) {}
 
   bool isUnknown() const { return getLatticeValue() == unknown; }
 
-  bool isConstant() const {
-    return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
-  }
+  bool isConstant() const { return getLatticeValue() == constant; }
 
   bool isOverdefined() const { return getLatticeValue() == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return Val.getPointer();
   }
 
   /// markOverdefined - Return true if this is a change in status.
   bool markOverdefined() {
     if (isOverdefined())
       return false;
 
     Val.setInt(overdefined);
     return true;
   }
 
   /// markConstant - Return true if this is a change in status.
   bool markConstant(Constant *V) {
-    if (getLatticeValue() == constant) { // Constant but not forcedconstant.
+    if (getLatticeValue() == constant) { // Constant
       assert(getConstant() == V && "Marking constant with different value");
       return false;
     }
 
-    if (isUnknown()) {
-      Val.setInt(constant);
-      assert(V && "Marking constant with NULL");
-      Val.setPointer(V);
-    } else {
-      assert(getLatticeValue() == forcedconstant &&
-             "Cannot move from overdefined to constant!");
-      // Stay at forcedconstant if the constant is the same.
-      if (V == getConstant()) return false;
-
-      // Otherwise, we go to overdefined.  Assumptions made based on the
-      // forced value are possibly wrong.  Assuming this is another constant
-      // could expose a contradiction.
-      Val.setInt(overdefined);
-    }
+    assert(isUnknown());
     return true;
   }
 
   /// getConstantInt - If this is a constant with a ConstantInt value, return it
   /// otherwise return null.
   ConstantInt *getConstantInt() const {
     if (isConstant())
       return dyn_cast<ConstantInt>(getConstant());
     return nullptr;
   }
 
   /// getBlockAddress - If this is a constant with a BlockAddress value, return
   /// it, otherwise return null.
   BlockAddress *getBlockAddress() const {
     if (isConstant())
       return dyn_cast<BlockAddress>(getConstant());
     return nullptr;
   }
 
-  void markForcedConstant(Constant *V) {
-    assert(isUnknown() && "Can't force a defined value!");
-    Val.setInt(forcedconstant);
-    Val.setPointer(V);
-  }
-
   ValueLatticeElement toValueLattice() const {
     if (isOverdefined())
       return ValueLatticeElement::getOverdefined();
     if (isConstant())
       return ValueLatticeElement::get(getConstant());
     return ValueLatticeElement();
   }
 };
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       LatticeVal LV = It->second;
       if (LV.isOverdefined())
         return false;
     }
     return true;
   }
 
 private:
-  // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
+  // pushToWorkList - Helper for markConstant/markOverdefined
   void pushToWorkList(LatticeVal &IV, Value *V) {
     if (IV.isOverdefined())
       return OverdefinedInstWorkList.push_back(V);
     InstWorkList.push_back(V);
   }
 
   // markConstant - Make a value be marked as "constant".  If the value
   // is not already a constant, add it to the instruction work list so that
   // the users of the instruction are updated later.
   bool markConstant(LatticeVal &IV, Value *V, Constant *C) {
     if (!IV.markConstant(C)) return false;
     LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
     return true;
   }
 
   bool markConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
     return markConstant(ValueState[V], V, C);
   }
 
-  void markForcedConstant(Value *V, Constant *C) {
-    assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
-    LatticeVal &IV = ValueState[V];
-    IV.markForcedConstant(C);
-    LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
-    pushToWorkList(IV, V);
-  }
-
   // markOverdefined - Make a value be marked as "overdefined". If the
   // value is not already overdefined, add it to the overdefined instruction
   // work list so that the users of the instruction are updated later.
   bool markOverdefined(LatticeVal &IV, Value *V) {
     if (!IV.markOverdefined()) return false;
 
     LLVM_DEBUG(dbgs() << "markOverdefined: ";
                if (auto *F = dyn_cast<Function>(V)) dbgs()
Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
                                     V2State.getConstant());
     // X op Y -> undef.
     if (isa<UndefValue>(C))
       return;
     return (void)markConstant(IV, &I, C);
   }
 
   // If something is undef, wait for it to resolve.
-  if (!V1State.isOverdefined() && !V2State.isOverdefined())
+  if (!V1State.isOverdefined() && !V2State.isOverdefined()) {
+
     return;
+  }
 
   // Otherwise, one of our operands is overdefined.  Try to produce something
   // better than overdefined with some tricks.
   // If this is 0 / Y, it doesn't matter that the second operand is
   // overdefined, and we can replace it with zero.
   if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv)
     if (V1State.isConstant() && V1State.getConstant()->isNullValue())
       return (void)markConstant(IV, &I, V1State.getConstant());

 /// This method handles this by finding an unresolved branch and marking it one
 /// of the edges from the block as being feasible, even though the condition
 /// doesn't say it would otherwise be.  This allows SCCP to find the rest of the
 /// CFG and only slightly pessimizes the analysis results (by marking one,
 /// potentially infeasible, edge feasible).  This cannot usefully modify the
 /// constraints on the condition of the branch, as that would impact other users
 /// of the value.
 ///
-/// This scan also checks for values that use undefs, whose results are actually
-/// defined.  For example, 'zext i8 undef to i32' should produce all zeros
-/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
-/// even if X isn't defined.
+/// This scan also checks for values that use undefs. It conservatively marks
+/// them as overdefined.
 bool SCCPSolver::ResolvedUndefsIn(Function &F) {
   for (BasicBlock &BB : F) {
     if (!BBExecutable.count(&BB))
       continue;
 
     for (Instruction &I : BB) {
       // Look for instructions which produce undef values.
       if (I.getType()->isVoidTy()) continue;
 
       if (auto *STy = dyn_cast<StructType>(I.getType())) {
         // Only a few things that can be structs matter for undef.
 
         // Tracked calls must never be marked overdefined in ResolvedUndefsIn.
         if (CallSite CS = CallSite(&I))
           if (Function *F = CS.getCalledFunction())
             if (MRVFunctionsTracked.count(F))
               continue;
 
         // extractvalue and insertvalue don't need to be marked; they are
         // tracked as precisely as their operands.
         if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
           continue;
-
         // Send the results of everything else to overdefined.  We could be
         // more precise than this but it isn't worth bothering.
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           LatticeVal &LV = getStructValueState(&I, i);
           if (LV.isUnknown())
             markOverdefined(LV, &I);
         }
         continue;
       }
 
       LatticeVal &LV = getValueState(&I);
       if (!LV.isUnknown())
         continue;
 
       // There are two reasons a call can have an undef result
       // 1. It could be tracked.
       // 2. It could be constant-foldable.
       // Because of the way we solve return values, tracked calls must
       // never be marked overdefined in ResolvedUndefsIn.
-      if (CallSite CS = CallSite(&I)) {
+      if (CallSite CS = CallSite(&I))
         if (Function *F = CS.getCalledFunction())
           if (TrackedRetVals.count(F))
             continue;
 
-        // If the call is constant-foldable, we mark it overdefined because
-        // we do not know what return values are valid.
-        markOverdefined(&I);
-        return true;
-      }
-
-      // extractvalue is safe; check here because the argument is a struct.
-      if (isa<ExtractValueInst>(I))
-        continue;
-
-      // Compute the operand LatticeVals, for convenience below.
-      // Anything taking a struct is conservatively assumed to require
-      // overdefined markings.
-      if (I.getOperand(0)->getType()->isStructTy()) {
-        markOverdefined(&I);
-        return true;
-      }
-      LatticeVal Op0LV = getValueState(I.getOperand(0));
-      LatticeVal Op1LV;
-      if (I.getNumOperands() == 2) {
-        if (I.getOperand(1)->getType()->isStructTy()) {
-          markOverdefined(&I);
-          return true;
-        }
-
-        Op1LV = getValueState(I.getOperand(1));
-      }
-      // If this is an instructions whose result is defined even if the input is
-      // not fully defined, propagate the information.
-      Type *ITy = I.getType();
-      switch (I.getOpcode()) {
-      case Instruction::Add:
-      case Instruction::Sub:
-      case Instruction::Trunc:
-      case Instruction::FPTrunc:
-      case Instruction::BitCast:
-        break; // Any undef -> undef
-      case Instruction::FSub:
-      case Instruction::FAdd:
-      case Instruction::FMul:
-      case Instruction::FDiv:
-      case Instruction::FRem:
-        // Floating-point binary operation: be conservative.
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          markForcedConstant(&I, Constant::getNullValue(ITy));
-        else
-          markOverdefined(&I);
-        return true;
-      case Instruction::FNeg:
-        break; // fneg undef -> undef
-      case Instruction::ZExt:
-      case Instruction::SExt:
-      case Instruction::FPToUI:
-      case Instruction::FPToSI:
-      case Instruction::FPExt:
-      case Instruction::PtrToInt:
-      case Instruction::IntToPtr:
-      case Instruction::SIToFP:
-      case Instruction::UIToFP:
-        // undef -> 0; some outputs are impossible
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::Mul:
-      case Instruction::And:
-        // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          break;
-        // undef * X -> 0.   X could be zero.
-        // undef & X -> 0.   X could be zero.
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::Or:
-        // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          break;
-        // undef | X -> -1.   X could be -1.
-        markForcedConstant(&I, Constant::getAllOnesValue(ITy));
-        return true;
-      case Instruction::Xor:
-        // undef ^ undef -> 0; strictly speaking, this is not strictly
-        // necessary, but we try to be nice to people who expect this
-        // behavior in simple cases
-        if (Op0LV.isUnknown() && Op1LV.isUnknown()) {
-          markForcedConstant(&I, Constant::getNullValue(ITy));
-          return true;
-        }
-        // undef ^ X -> undef
-        break;
-      case Instruction::SDiv:
-      case Instruction::UDiv:
-      case Instruction::SRem:
-      case Instruction::URem:
-        // X / undef -> undef.  No change.
-        // X % undef -> undef.  No change.
-        if (Op1LV.isUnknown()) break;
-
-        // X / 0 -> undef.  No change.
-        // X % 0 -> undef.  No change.
-        if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())
-          break;
-
-        // undef / X -> 0.   X could be maxint.
-        // undef % X -> 0.   X could be 1.
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::AShr:
-        // X >>a undef -> undef.
-        if (Op1LV.isUnknown()) break;
-
-        // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
-
-        // undef >>a X -> 0
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::LShr:
-      case Instruction::Shl:
-        // X << undef -> undef.
-        // X >> undef -> undef.
-        if (Op1LV.isUnknown()) break;
-
-        // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
-
-        // undef << X -> 0
-        // undef >> X -> 0
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::Select:
-        Op1LV = getValueState(I.getOperand(1));
-        // undef ? X : Y  -> X or Y.  There could be commonality between X/Y.
-        if (Op0LV.isUnknown()) {
-          if (!Op1LV.isConstant())  // Pick the constant one if there is any.
-            Op1LV = getValueState(I.getOperand(2));
-        } else if (Op1LV.isUnknown()) {
-          // c ? undef : undef -> undef.  No change.
-          Op1LV = getValueState(I.getOperand(2));
-          if (Op1LV.isUnknown())
-            break;
-          // Otherwise, c ? undef : x -> x.
-        } else {
-          // Leave Op1LV as Operand(1)'s LatticeValue.
-        }
-
-        if (Op1LV.isConstant())
-          markForcedConstant(&I, Op1LV.getConstant());
-        else
-          markOverdefined(&I);
-        return true;
-      case Instruction::Load:
-        // A load here means one of two things: a load of undef from a global,
-        // a load from an unknown pointer.  Either way, having it return undef
-        // is okay.
-        break;
-      case Instruction::ICmp:
-        // X == undef -> undef.  Other comparisons get more complicated.
-        Op0LV = getValueState(I.getOperand(0));
-        Op1LV = getValueState(I.getOperand(1));
-
-        if ((Op0LV.isUnknown() || Op1LV.isUnknown()) &&
-            cast<ICmpInst>(&I)->isEquality())
-          break;
-        markOverdefined(&I);
-        return true;
-      case Instruction::Call:
-      case Instruction::Invoke:
-      case Instruction::CallBr:
-        llvm_unreachable("Call-like instructions should have be handled early");
-      default:
-        // If we don't know what should happen here, conservatively mark it
-        // overdefined.
-        markOverdefined(&I);
-        return true;
-      }
     }
 
     // Check to see if we have a branch or switch on an undefined value.  If so
     // we force the branch to go one way or the other to make the successor
     // values live.  It doesn't really matter which way we force it.
     Instruction *TI = BB.getTerminator();
     if (auto *BI = dyn_cast<BranchInst>(TI)) {
       if (!BI->isConditional()) continue;

llvm/test/Transforms/IPConstantProp/PR16052.ll

-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes 
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt < %s -S -ipsccp | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i64 @fn2() {
 ; CHECK-LABEL: define {{[^@]+}}@fn2()
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CALL2:%.*]] = call i64 @fn1(i64 undef)
+; CHECK-NEXT:    [[CONV:%.*]] = sext i32 undef to i64
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i64 8, [[CONV]]
+; CHECK-NEXT:    [[CALL2:%.*]] = call i64 @fn1(i64 [[DIV]])
 ; CHECK-NEXT:    ret i64 [[CALL2]]
 ;
 entry:
   %conv = sext i32 undef to i64
   %div = sdiv i64 8, %conv
   %call2 = call i64 @fn1(i64 %div)
   ret i64 %call2
 }
 
 define internal i64 @fn1(i64 %p1) {
 ; CHECK-LABEL: define {{[^@]+}}@fn1
 ; CHECK-SAME: (i64 [[P1:%.*]])
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND:%.*]] = select i1 undef, i64 undef, i64 undef
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i64 [[P1]], 0
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i64 [[P1]], i64 [[P1]]
 ; CHECK-NEXT:    ret i64 [[COND]]
 ;
 entry:
   %tobool = icmp ne i64 %p1, 0
   %cond = select i1 %tobool, i64 %p1, i64 %p1
   ret i64 %cond
 }

llvm/test/Transforms/IPConstantProp/PR26044.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt < %s -S -ipsccp | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @fn2(i32* %P) {
 ; CHECK-LABEL: define {{[^@]+}}@fn2
 ; CHECK-SAME: (i32* [[P:%.*]])
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       for.cond1:
 ; CHECK-NEXT:    br i1 false, label [[IF_END]], label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[CALL:%.*]] = call i32 @fn1(i32 undef)
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 4
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @fn1(i32 [[TMP0]])
 ; CHECK-NEXT:    store i32 [[CALL]], i32* [[P]]
 ; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
 ;
 entry:
   br label %if.end
 
 for.cond1:                                        ; preds = %if.end, %for.end
   br i1 undef, label %if.end, label %if.end
 
 if.end:                                           ; preds = %lbl, %for.cond1
   %e.2 = phi i32* [ undef, %entry ], [ null, %for.cond1 ], [ null, %for.cond1 ]
   %0 = load i32, i32* %e.2, align 4
   %call = call i32 @fn1(i32 %0)
   store i32 %call, i32* %P
   br label %for.cond1
 }
 
 define internal i32 @fn1(i32 %p1) {
 ; CHECK-LABEL: define {{[^@]+}}@fn1
 ; CHECK-SAME: (i32 [[P1:%.*]])
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[COND:%.*]] = select i1 undef, i32 undef, i32 undef
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[P1]], 0
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 [[P1]], i32 [[P1]]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %tobool = icmp ne i32 %p1, 0
   %cond = select i1 %tobool, i32 %p1, i32 %p1
   ret i32 %cond
 }
 

llvm/test/Transforms/SCCP/2006-12-19-UndefBug.ll

-; RUN: opt < %s -sccp -S | \
-; RUN:   grep "ret i1 false"
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
 
 define i1 @foo() {
-  %X = and i1 false, undef    ; <i1> [#uses=1]
-  ret i1 %X
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    [[X:%.*]] = and i1 false, undef
+; CHECK-NEXT:    ret i1 [[X]]
+;
+  %X = and i1 false, undef    ; <i1> [#uses=1]
+  ret i1 %X
 }
 

llvm/test/Transforms/SCCP/apint-bigint2.ll

define i101 @array() {
    %E = trunc i101 %DD to i32
    %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 %E
    %G = load i101, i101* %F
 
    ret i101 %G
 }
 
 ; CHECK-LABEL: @large_aggregate
-; CHECK-NEXT: ret i101 undef
+; CHECK-NEXT:    %B = load i101, i101* undef
+; CHECK-NEXT:    %D = and i101 %B, 1
+; CHECK-NEXT:    %DD = or i101 %D, 1
+; CHECK-NEXT:    %G = getelementptr i101, i101* getelementptr inbounds ([6 x i101], [6 x i101]* @Y, i32 0, i32 5), i101 %DD
+; CHECK-NEXT:    %L3 = load i101, i101* %G
+; CHECK-NEXT:    ret i101 %L3
+;
 define i101 @large_aggregate() {
   %B = load i101, i101* undef
   %D = and i101 %B, 1
   %DD = or i101 %D, 1
   %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 5
   %G = getelementptr i101, i101* %F, i101 %DD
   %L3 = load i101, i101* %G
   ret i101 %L3
 }
 
+; CHECK-LABEL: define i101 @large_aggregate_2() {
+; CHECK-NEXT:     %D = and i101 undef, 1
+; CHECK-NEXT:     %DD = or i101 %D, 1
+; CHECK-NEXT:     %G = getelementptr i101, i101* getelementptr inbounds ([6 x i101], [6 x i101]* @Y, i32 0, i32 5), i101 %DD
+; CHECK-NEXT:     %L3 = load i101, i101* %G
+; CHECK-NEXT:     ret i101 %L3
+;
+define i101 @large_aggregate_2() {
+  %D = and i101 undef, 1
+  %DD = or i101 %D, 1
+  %F = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 5
+  %G = getelementptr i101, i101* %F, i101 %DD
+  %L3 = load i101, i101* %G
+  ret i101 %L3
+}
+
 ; CHECK-LABEL: @index_too_large
 ; CHECK-NEXT: store i101* getelementptr (i101, i101* getelementptr ([6 x i101], [6 x i101]* @Y, i32 0, i32 -1), i101 9224497936761618431), i101** undef
 ; CHECK-NEXT: ret void
 define void @index_too_large() {
   %ptr1 = getelementptr [6 x i101], [6 x i101]* @Y, i32 0, i32 -1
   %ptr2 = getelementptr i101, i101* %ptr1, i101 9224497936761618431
   store i101* %ptr2, i101** undef
   ret void
 }

llvm/test/Transforms/SCCP/apint-ipsccp3.ll

-; RUN: opt < %s -ipsccp -S | not grep global
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 @G = internal global i66 undef
 
 
-
 define void @foo() {
-  %X = load i66, i66* @G
-  store i66 %X, i66* @G
-  ret void
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    [[X:%.*]] = load i66, i66* @G
+; CHECK-NEXT:    store i66 [[X]], i66* @G
+; CHECK-NEXT:    ret void
+;
+  %X = load i66, i66* @G
+  store i66 %X, i66* @G
+  ret void
 }
 
 define i66 @bar() {
-  %V = load i66, i66* @G
-  %C = icmp eq i66 %V, 17
-  br i1 %C, label %T, label %F
+; CHECK-LABEL: @bar(
+; CHECK-NEXT:    [[V:%.*]] = load i66, i66* @G
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i66 [[V]], 17
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       T:
+; CHECK-NEXT:    store i66 17, i66* @G
+; CHECK-NEXT:    ret i66 17
+; CHECK:       F:
+; CHECK-NEXT:    store i66 123, i66* @G
+; CHECK-NEXT:    ret i66 0
+;
+  %V = load i66, i66* @G
+  %C = icmp eq i66 %V, 17
+  br i1 %C, label %T, label %F
 T:
-  store i66 17, i66* @G
-  ret i66 %V
+  store i66 17, i66* @G
+  ret i66 %V
 F:
-  store i66 123, i66* @G
-  ret i66 0
+  store i66 123, i66* @G
+  ret i66 0
 }

llvm/test/Transforms/SCCP/apint-select.ll

-; RUN: opt < %s -sccp -S | not grep select
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
 
 @A = constant i32 10
 
 define i712 @test1() {
-        %P = getelementptr i32, i32* @A, i32 0
-        %B = ptrtoint i32* %P to i64
-        %BB = and i64 %B, undef
-        %C = icmp sge i64 %BB, 0
-  %X = select i1 %C, i712 0, i712 1
-  ret i712 %X
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[BB:%.*]] = and i64 ptrtoint (i32* @A to i64), undef
+; CHECK-NEXT:    [[C:%.*]] = icmp sge i64 [[BB]], 0
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[C]], i712 0, i712 1
+; CHECK-NEXT:    ret i712 [[X]]
+;
+  %X = select i1 %C, i712 0, i712 1
+  ret i712 %X
 }
 
 
 
 define i712 @test2(i1 %C) {
-  %X = select i1 %C, i712 0, i712 undef
-  ret i712 %X
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    ret i712 0
+;
+  %X = select i1 %C, i712 0, i712 undef
+  ret i712 %X
 }
-
-

llvm/test/Transforms/SCCP/ip-constant-ranges.ll

define double @test_struct({ double, double } %test) {
     %v = extractvalue { double, double } %test, 0
     %r = fmul double %v, %v
     ret double %r
 }
 
 ; Constant range for %x is [47, 302)
 ; CHECK-LABEL: @f5
 ; CHECK-NEXT: entry:
-; CHECK-NEXT: %cmp = icmp sgt i32 %x, undef
-; CHECK-NEXT: %res1 = select i1 %cmp, i32 1, i32 2
-; CHECK-NEXT: %res = add i32 %res1, 3
-; CHECK-NEXT: ret i32 %res
+; CHECK-NEXT:   %cmp = icmp sgt i32 %x, undef
+; CHECK-NEXT:   %cmp2 = icmp ne i32 undef, %x
+; CHECK-NEXT:   %res1 = select i1 %cmp, i32 1, i32 2
+; CHECK-NEXT:   %res2 = select i1 %cmp2, i32 3, i32 4
+; CHECK-NEXT:   %res = add i32 %res1, %res2
+; CHECK-NEXT:   ret i32 %res
 define internal i32 @f5(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, undef
   %cmp2 = icmp ne i32 undef, %x
   %res1 = select i1 %cmp, i32 1, i32 2
   %res2 = select i1 %cmp2, i32 3, i32 4
 
   %res = add i32 %res1, %res2

llvm/test/Transforms/SCCP/ipsccp-basic.ll

 @G = internal global i32 undef
 
 define void @test3a() {
   %X = load i32, i32* @G
   store i32 %X, i32* @G
   ret void
 }
 ; CHECK-LABEL: define void @test3a(
-; CHECK-NEXT: ret void
+; CHECK-NEXT:    %X = load i32, i32* @G
+; CHECK-NEXT:    store i32 %X, i32* @G
+; CHECK-NEXT:   ret void
 
 
 define i32 @test3b() {
   %V = load i32, i32* @G
   %C = icmp eq i32 %V, 17
   br i1 %C, label %T, label %F
 T:
   store i32 17, i32* @G
   ret i32 %V
 F:  
   store i32 123, i32* @G
   ret i32 0
 }
 ; CHECK-LABEL: define i32 @test3b(
-; CHECK-NOT: store
-; CHECK: ret i32 0
+; CHECK-NEXT:    %V = load i32, i32* @G
+; CHECK-NEXT:    %C = icmp eq i32 %V, 17
+; CHECK-NEXT:    br i1 %C, label %T, label %F
+
+; CHECK-LABEL: T:
+; CHECK-NEXT:   store i32 17, i32* @G
+; CHECK-NEXT:   ret i32 17
 
+; CHECK-LABEL: F:
+; CHECK-NEXT:    store i32 123, i32* @G
+; CHECK-NEXT:    ret i32 0
 
 ;;======================== test4
 
 define internal {i64,i64} @test4a() {
   %a = insertvalue {i64,i64} undef, i64 4, 1
   %b = insertvalue {i64,i64} %a, i64 5, 0
   ret {i64,i64} %b
 }

 declare i32 @__gxx_personality_v0(...)
 
 ;;======================== test10
 
 define i32 @test10a() nounwind {
 entry:
   %call = call i32 @test10b(i32 undef)
   ret i32 %call
+
 ; CHECK-LABEL: define i32 @test10a(
-; CHECK: ret i32 0
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    %call = call i32 @test10b(i32 undef)
+; CHECK-NEXT:    ret i32 %call
 }
 
 define internal i32 @test10b(i32 %x) nounwind {
 entry:
   %r = and i32 %x, 1
   ret i32 %r
 ; CHECK-LABEL: define internal i32 @test10b(
-; CHECK: ret i32 undef
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    %r = and i32 undef, 1
+; CHECK-NEXT:    ret i32 %r
 }
 
 ;;======================== test11
 
 define i64 @test11a() {
   %xor = xor i64 undef, undef
   ret i64 %xor
 ; CHECK-LABEL: define i64 @test11a
-; CHECK: ret i64 0
+; CHECK-NEXT:    %xor = xor i64 undef, undef
+; CHECK-NEXT:    ret i64 %xor
 }
 
 define i64 @test11b() {
   %call1 = call i64 @test11a()
   %call2 = call i64 @llvm.ctpop.i64(i64 %call1)
   ret i64 %call2
 ; CHECK-LABEL: define i64 @test11b
-; CHECK: %[[call1:.*]] = call i64 @test11a()
-; CHECK-NOT: call i64 @llvm.ctpop.i64
-; CHECK-NEXT: ret i64 0
+; CHECK-NEXT:   [[call1:%.*]] = call i64 @test11a()
+; CHECK-NEXT:    [[call2:%.*]] = call i64 @llvm.ctpop.i64(i64 [[call1]])
+; CHECK-NEXT: ret i64 [[call2]]
 }
 
 declare i64 @llvm.ctpop.i64(i64)
 
 ;;======================== test12
 ;; Ensure that a struct as an arg to a potentially constant-foldable
 ;; function does not crash SCCP (for now it'll just ignores it)
 
 define i1 @test12() {
   %c = call i1 @llvm.is.constant.sl_i32i32s({i32, i32} {i32 -1, i32 32})
   ret i1 %c
 ; CHECK-LABEL: define i1 @test12
 ; CHECK: ret i1 %c
 }
 
 declare i1 @llvm.is.constant.sl_i32i32s({i32, i32} %a)

llvm/test/Transforms/SCCP/logical-nuke.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -sccp -S | FileCheck %s
 
 ; Test that SCCP has basic knowledge of when and/or/mul nuke overdefined values.
 
-; CHECK-LABEL: test
-; CHECK: ret i32 0
  define i32 @test(i32 %X) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    ret i32 0
+;
   %Y = and i32 %X, 0
   ret i32 %Y
 }
 
-; CHECK-LABEL: test2
-; CHECK: ret i32 -1
 define i32 @test2(i32 %X) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    ret i32 -1
+;
   %Y = or i32 -1, %X
   ret i32 %Y
 }
 
-; CHECK-LABEL: test3
-; CHECK: ret i32 0
 define i32 @test3(i32 %X) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[Y:%.*]] = and i32 undef, [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[Y]]
+;
   %Y = and i32 undef, %X
   ret i32 %Y
 }
 
-; CHECK-LABEL: test4
-; CHECK: ret i32 -1
 define i32 @test4(i32 %X) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[Y:%.*]] = or i32 [[X:%.*]], undef
+; CHECK-NEXT:    ret i32 [[Y]]
+;
   %Y = or i32 %X, undef
   ret i32 %Y
 }
 
 ; X * 0 = 0 even if X is overdefined.
-; CHECK-LABEL: test5
-; CHECK: ret i32 0
 define i32 @test5(i32 %foo) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    ret i32 0
+;
   %patatino = mul i32 %foo, 0
   ret i32 %patatino
 }

llvm/test/Transforms/SCCP/switch-multiple-undef.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -ipsccp < %s | FileCheck %s
 
 declare void @foo()
 declare void @goo()
 declare void @patatino()
 
 define void @test1(i32 %t) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[CHOICE:%.*]] = icmp eq i32 undef, -1
+; CHECK-NEXT:    switch i1 [[CHOICE]], label [[FIRST:%.*]] [
+; CHECK-NEXT:    i1 false, label [[SECOND:%.*]]
+; CHECK-NEXT:    i1 true, label [[THIRD:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       first:
+; CHECK-NEXT:    call void @foo()
+; CHECK-NEXT:    ret void
+; CHECK:       second:
+; CHECK-NEXT:    call void @goo()
+; CHECK-NEXT:    ret void
+; CHECK:       third:
+; CHECK-NEXT:    call void @patatino()
+; CHECK-NEXT:    ret void
+;
   %choice = icmp eq i32 undef, -1
   switch i1 %choice, label %first [i1 0, label %second
-                                   i1 1, label %third]
 first:
   call void @foo()
   ret void
 second:
   call void @goo()
   ret void
 third:
   call void @patatino()
   ret void
 }
-
-; CHECK: define void @test1(i32 %t) {
-; CHECK-NEXT:   br label %second
-; CHECK: second:
-; CHECK-NEXT:   call void @goo()
-; CHECK-NEXT:   ret void
-; CHECK-NEXT: }

llvm/test/Transforms/SCCP/ub-shift.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -sccp -S | FileCheck %s
 
-; CHECK-LABEL: shift_undef_64
 define void @shift_undef_64(i64* %p) {
+; CHECK-LABEL: @shift_undef_64(
+; CHECK-NEXT:    [[R1:%.*]] = lshr i64 -1, 4294967296
+; CHECK-NEXT:    store i64 [[R1]], i64* [[P:%.*]]
+; CHECK-NEXT:    [[R2:%.*]] = ashr i64 -1, 4294967297
+; CHECK-NEXT:    store i64 [[R2]], i64* [[P]]
+; CHECK-NEXT:    [[R3:%.*]] = shl i64 -1, 4294967298
+; CHECK-NEXT:    store i64 [[R3]], i64* [[P]]
+; CHECK-NEXT:    ret void
+;
   %r1 = lshr i64 -1, 4294967296 ; 2^32
-  ; CHECK: store i64 undef
   store i64 %r1, i64* %p
 
   %r2 = ashr i64 -1, 4294967297 ; 2^32 + 1
-  ; CHECK: store i64 undef
   store i64 %r2, i64* %p
 
   %r3 = shl i64 -1, 4294967298 ; 2^32 + 2
-  ; CHECK: store i64 undef
   store i64 %r3, i64* %p
 
   ret void
 }
 
-; CHECK-LABEL: shift_undef_65
 define void @shift_undef_65(i65* %p) {
+; CHECK-LABEL: @shift_undef_65(
+; CHECK-NEXT:    [[R1:%.*]] = lshr i65 2, -18446744073709551615
+; CHECK-NEXT:    store i65 [[R1]], i65* [[P:%.*]]
+; CHECK-NEXT:    [[R2:%.*]] = ashr i65 4, -18446744073709551615
+; CHECK-NEXT:    store i65 [[R2]], i65* [[P]]
+; CHECK-NEXT:    [[R3:%.*]] = shl i65 1, -18446744073709551615
+; CHECK-NEXT:    store i65 [[R3]], i65* [[P]]
+; CHECK-NEXT:    ret void
+;
   %r1 = lshr i65 2, 18446744073709551617
-  ; CHECK: store i65 undef
   store i65 %r1, i65* %p
 
   %r2 = ashr i65 4, 18446744073709551617
-  ; CHECK: store i65 undef
   store i65 %r2, i65* %p
 
   %r3 = shl i65 1, 18446744073709551617
-  ; CHECK: store i65 undef
   store i65 %r3, i65* %p
 
   ret void
 }
 
-; CHECK-LABEL: shift_undef_256
 define void @shift_undef_256(i256* %p) {
+; CHECK-LABEL: @shift_undef_256(
+; CHECK-NEXT:    [[R1:%.*]] = lshr i256 2, 18446744073709551617
+; CHECK-NEXT:    store i256 [[R1]], i256* [[P:%.*]]
+; CHECK-NEXT:    [[R2:%.*]] = ashr i256 4, 18446744073709551618
+; CHECK-NEXT:    store i256 [[R2]], i256* [[P]]
+; CHECK-NEXT:    [[R3:%.*]] = shl i256 1, 18446744073709551619
+; CHECK-NEXT:    store i256 [[R3]], i256* [[P]]
+; CHECK-NEXT:    ret void
+;
   %r1 = lshr i256 2, 18446744073709551617
-  ; CHECK: store i256 undef
   store i256 %r1, i256* %p
 
   %r2 = ashr i256 4, 18446744073709551618
-  ; CHECK: store i256 undef
   store i256 %r2, i256* %p
 
   %r3 = shl i256 1, 18446744073709551619
-  ; CHECK: store i256 undef
   store i256 %r3, i256* %p
 
   ret void
 }
 
-; CHECK-LABEL: shift_undef_511
 define void @shift_undef_511(i511* %p) {
+; CHECK-LABEL: @shift_undef_511(
+; CHECK-NEXT:    [[R1:%.*]] = lshr i511 -1, 1208925819614629174706276
+; CHECK-NEXT:    store i511 [[R1]], i511* [[P:%.*]]
+; CHECK-NEXT:    [[R2:%.*]] = ashr i511 -2, 1208925819614629174706200
+; CHECK-NEXT:    store i511 [[R2]], i511* [[P]]
+; CHECK-NEXT:    [[R3:%.*]] = shl i511 -3, 1208925819614629174706180
+; CHECK-NEXT:    store i511 [[R3]], i511* [[P]]
+; CHECK-NEXT:    ret void
+;
   %r1 = lshr i511 -1, 1208925819614629174706276 ; 2^80 + 100
-  ; CHECK: store i511 undef
   store i511 %r1, i511* %p
 
   %r2 = ashr i511 -2, 1208925819614629174706200
-  ; CHECK: store i511 undef
   store i511 %r2, i511* %p
 
   %r3 = shl i511 -3, 1208925819614629174706180
-  ; CHECK: store i511 undef
   store i511 %r3, i511* %p
 
   ret void
 }

llvm/test/Transforms/SCCP/undef-resolve.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -sccp -S < %s | FileCheck %s
 
 
 ; PR6940
 define double @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[T:%.*]] = sitofp i32 undef to double
+; CHECK-NEXT:    ret double [[T]]
+;
   %t = sitofp i32 undef to double
   ret double %t
-; CHECK-LABEL: @test1(
-; CHECK: ret double 0.0
 }
 
 
 ; rdar://7832370
 ; Check that lots of stuff doesn't get turned into undef.
 define i32 @test2() nounwind readnone ssp {
 ; CHECK-LABEL: @test2(
+; CHECK-NEXT:  init:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_OUTER:%.*]]
+; CHECK:       control.outer.loopexit.us-lcssa:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_LOOPEXIT:%.*]]
+; CHECK:       control.outer.loopexit:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_OUTER_BACKEDGE:%.*]]
+; CHECK:       control.outer.outer:
+; CHECK-NEXT:    [[SWITCHCOND_0_PH_PH:%.*]] = phi i32 [ 2, [[INIT:%.*]] ], [ 3, [[CONTROL_OUTER_OUTER_BACKEDGE]] ]
+; CHECK-NEXT:    [[I_0_PH_PH:%.*]] = phi i32 [ undef, [[INIT]] ], [ [[I_0_PH_PH_BE:%.*]], [[CONTROL_OUTER_OUTER_BACKEDGE]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[I_0_PH_PH]], 0
+; CHECK-NEXT:    br i1 [[TMP4]], label [[CONTROL_OUTER_OUTER_SPLIT_US:%.*]], label [[CONTROL_OUTER_OUTER_CONTROL_OUTER_OUTER_SPLIT_CRIT_EDGE:%.*]]
+; CHECK:       control.outer.outer.control.outer.outer.split_crit_edge:
+; CHECK-NEXT:    br label [[CONTROL_OUTER:%.*]]
+; CHECK:       control.outer.outer.split.us:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_US:%.*]]
+; CHECK:       control.outer.us:
+; CHECK-NEXT:    [[A_0_PH_US:%.*]] = phi i32 [ [[SWITCHCOND_0_US:%.*]], [[BB3_US:%.*]] ], [ 4, [[CONTROL_OUTER_OUTER_SPLIT_US]] ]
+; CHECK-NEXT:    [[SWITCHCOND_0_PH_US:%.*]] = phi i32 [ [[A_0_PH_US]], [[BB3_US]] ], [ [[SWITCHCOND_0_PH_PH]], [[CONTROL_OUTER_OUTER_SPLIT_US]] ]
+; CHECK-NEXT:    br label [[CONTROL_US:%.*]]
+; CHECK:       bb3.us:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_US]]
+; CHECK:       bb0.us:
+; CHECK-NEXT:    br label [[CONTROL_US]]
+; CHECK:       control.us:
+; CHECK-NEXT:    [[SWITCHCOND_0_US]] = phi i32 [ [[A_0_PH_US]], [[BB0_US:%.*]] ], [ [[SWITCHCOND_0_PH_US]], [[CONTROL_OUTER_US]] ]
+; CHECK-NEXT:    switch i32 [[SWITCHCOND_0_US]], label [[CONTROL_OUTER_LOOPEXIT_US_LCSSA_US:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB0_US]]
+; CHECK-NEXT:    i32 1, label [[BB1_US_LCSSA_US:%.*]]
+; CHECK-NEXT:    i32 3, label [[BB3_US]]
+; CHECK-NEXT:    i32 4, label [[BB4_US_LCSSA_US:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       control.outer.loopexit.us-lcssa.us:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_LOOPEXIT]]
+; CHECK:       bb1.us-lcssa.us:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb4.us-lcssa.us:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       control.outer:
+; CHECK-NEXT:    [[A_0_PH:%.*]] = phi i32 [ [[NEXTID17:%.*]], [[BB3:%.*]] ], [ 4, [[CONTROL_OUTER_OUTER_CONTROL_OUTER_OUTER_SPLIT_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[SWITCHCOND_0_PH:%.*]] = phi i32 [ 0, [[BB3]] ], [ [[SWITCHCOND_0_PH_PH]], [[CONTROL_OUTER_OUTER_CONTROL_OUTER_OUTER_SPLIT_CRIT_EDGE]] ]
+; CHECK-NEXT:    br label [[CONTROL:%.*]]
+; CHECK:       control:
+; CHECK-NEXT:    [[SWITCHCOND_0:%.*]] = phi i32 [ [[A_0_PH]], [[BB0:%.*]] ], [ [[SWITCHCOND_0_PH]], [[CONTROL_OUTER]] ]
+; CHECK-NEXT:    switch i32 [[SWITCHCOND_0]], label [[CONTROL_OUTER_LOOPEXIT_US_LCSSA:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB0]]
+; CHECK-NEXT:    i32 1, label [[BB1_US_LCSSA:%.*]]
+; CHECK-NEXT:    i32 3, label [[BB3]]
+; CHECK-NEXT:    i32 4, label [[BB4_US_LCSSA:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb4.us-lcssa:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[CONTROL_OUTER_OUTER_BACKEDGE]]
+; CHECK:       control.outer.outer.backedge:
+; CHECK-NEXT:    [[I_0_PH_PH_BE]] = phi i32 [ 1, [[BB4]] ], [ 0, [[CONTROL_OUTER_LOOPEXIT]] ]
+; CHECK-NEXT:    br label [[CONTROL_OUTER_OUTER]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[NEXTID17]] = add i32 [[SWITCHCOND_0]], -2
+; CHECK-NEXT:    br label [[CONTROL_OUTER]]
+; CHECK:       bb0:
+; CHECK-NEXT:    br label [[CONTROL]]
+; CHECK:       bb1.us-lcssa:
+; CHECK-NEXT:    br label [[BB1]]
+; CHECK:       bb1:
+; CHECK-NEXT:    ret i32 0
+;
 init:
   br label %control.outer.outer
 
 control.outer.loopexit.us-lcssa:                  ; preds = %control
   br label %control.outer.loopexit
 
 control.outer.loopexit:                           ; preds = %control.outer.loopexit.us-lcssa.us, %control.outer.loopexit.us-lcssa
   br label %control.outer.outer.backedge
control.outer.us:                                 ; preds = %bb3.us, %control.outer.outer.split.us
   br label %control.us
 
 bb3.us:                                           ; preds = %control.us
   br label %control.outer.us
 
 bb0.us:                                           ; preds = %control.us
   br label %control.us
 
-; CHECK: control.us:                                       ; preds = %bb0.us, %control.outer.us
-; CHECK-NEXT:  %switchCond.0.us = phi i32
-; CHECK-NEXT:  switch i32 %switchCond.0.us
 control.us:                                       ; preds = %bb0.us, %control.outer.us
   %switchCond.0.us = phi i32 [ %A.0.ph.us, %bb0.us ], [ %switchCond.0.ph.us, %control.outer.us ] ; <i32> [#uses=2]
   switch i32 %switchCond.0.us, label %control.outer.loopexit.us-lcssa.us [
-    i32 0, label %bb0.us
-    i32 1, label %bb1.us-lcssa.us
-    i32 3, label %bb3.us
-    i32 4, label %bb4.us-lcssa.us
   ]
 
 control.outer.loopexit.us-lcssa.us:               ; preds = %control.us
   br label %control.outer.loopexit
 
 bb1.us-lcssa.us:                                  ; preds = %control.us
   br label %bb1
 
 bb4.us-lcssa.us:                                  ; preds = %control.us
   br label %bb4
 
 control.outer:                                    ; preds = %bb3, %control.outer.outer.control.outer.outer.split_crit_edge
   %A.0.ph = phi i32 [ %nextId17, %bb3 ], [ 4, %control.outer.outer.control.outer.outer.split_crit_edge ] ; <i32> [#uses=1]
   %switchCond.0.ph = phi i32 [ 0, %bb3 ], [ %switchCond.0.ph.ph, %control.outer.outer.control.outer.outer.split_crit_edge ] ; <i32> [#uses=1]
   br label %control
 
 control:                                          ; preds = %bb0, %control.outer
   %switchCond.0 = phi i32 [ %A.0.ph, %bb0 ], [ %switchCond.0.ph, %control.outer ] ; <i32> [#uses=2]
   switch i32 %switchCond.0, label %control.outer.loopexit.us-lcssa [
-    i32 0, label %bb0
-    i32 1, label %bb1.us-lcssa
-    i32 3, label %bb3
-    i32 4, label %bb4.us-lcssa
   ]
 
 bb4.us-lcssa:                                     ; preds = %control
   br label %bb4
 
 bb4:                                              ; preds = %bb4.us-lcssa, %bb4.us-lcssa.us
   br label %control.outer.outer.backedge
 

 
 bb1:                                              ; preds = %bb1.us-lcssa, %bb1.us-lcssa.us
   ret i32 0
 }
 
 ; Make sure SCCP honors the xor "idiom"
 ; rdar://9956541
 define i32 @test3() {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[T:%.*]] = xor i32 undef, undef
+; CHECK-NEXT:    ret i32 [[T]]
+;
   %t = xor i32 undef, undef
   ret i32 %t
-; CHECK-LABEL: @test3(
-; CHECK: ret i32 0
 }
 
 ; Be conservative with FP ops
 define double @test4(double %x) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[T:%.*]] = fadd double [[X:%.*]], undef
+; CHECK-NEXT:    ret double [[T]]
+;
   %t = fadd double %x, undef
   ret double %t
-; CHECK-LABEL: @test4(
-; CHECK: fadd double %x, undef
 }
 
 ; Make sure casts produce a possible value
 define i32 @test5() {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:    [[T:%.*]] = sext i8 undef to i32
+; CHECK-NEXT:    ret i32 [[T]]
+;
   %t = sext i8 undef to i32
   ret i32 %t
-; CHECK-LABEL: @test5(
-; CHECK: ret i32 0
 }
 
 ; Make sure ashr produces a possible value
 define i32 @test6() {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[T:%.*]] = ashr i32 undef, 31
+; CHECK-NEXT:    ret i32 [[T]]
+;
   %t = ashr i32 undef, 31
   ret i32 %t
-; CHECK-LABEL: @test6(
-; CHECK: ret i32 0
 }
 
 ; Make sure lshr produces a possible value
 define i32 @test7() {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:    [[T:%.*]] = lshr i32 undef, 31
+; CHECK-NEXT:    ret i32 [[T]]
+;
   %t = lshr i32 undef, 31
   ret i32 %t
-; CHECK-LABEL: @test7(
-; CHECK: ret i32 0
 }
 
 ; icmp eq with undef simplifies to undef
 define i1 @test8() {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 undef, -1
+; CHECK-NEXT:    ret i1 [[T]]
+;
   %t = icmp eq i32 undef, -1
   ret i1 %t
-; CHECK-LABEL: @test8(
-; CHECK: ret i1 undef
 }
 
 ; Make sure we don't conclude that relational comparisons simplify to undef
 define i1 @test9() {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:    [[T:%.*]] = icmp ugt i32 undef, -1
+; CHECK-NEXT:    ret i1 [[T]]
+;
   %t = icmp ugt i32 undef, -1
   ret i1 %t
-; CHECK-LABEL: @test9(
-; CHECK: icmp ugt
 }
 
 ; Make sure we handle extractvalue
-define i64 @test10() { 
+define i64 @test10() {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[E:%.*]] = extractvalue { i64, i64 } undef, 1
+; CHECK-NEXT:    ret i64 [[E]]
+;
 entry:
   %e = extractvalue { i64, i64 } undef, 1
   ret i64 %e
-; CHECK-LABEL: @test10(
-; CHECK: ret i64 undef
 }
 
 @GV = external global i32
 
 define i32 @test11(i1 %tobool) {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[SHR4:%.*]] = ashr i32 undef, zext (i1 icmp eq (i32* bitcast (i32 (i1)* @test11 to i32*), i32* @GV) to i32)
+; CHECK-NEXT:    ret i32 [[SHR4]]
+;
 entry:
   %shr4 = ashr i32 undef, zext (i1 icmp eq (i32* bitcast (i32 (i1)* @test11 to i32*), i32* @GV) to i32)
   ret i32 %shr4
-; CHECK-LABEL: @test11(
-; CHECK: ret i32 0
 }
 
 ; Test unary ops
 define double @test12(double %x) {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    [[T:%.*]] = fneg double undef
+; CHECK-NEXT:    ret double [[T]]
+;
   %t = fneg double undef
   ret double %t
-; CHECK-LABEL: @test12(
-; CHECK: double undef
 }