[LSR] Fix bug for optimizing unused IVs to final values

[syzaara]

Summary

This is a fix for a crash reported for https://reviews.llvm.org/D118808
The fix is to only consider PHINodes which are induction phis.

[uabelho]

Thanks! I have confirmed this patch solves the crash I saw.

I don't feel confident reviewing this so adding @Whitney who reviewed the original patch.

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5603–5604

Since this immediately returns true, no other non-induction phi is being considered. I.e. the test depends on the ordering of ExitBB->phis().

That's already a problem with the if (ExitPhi.getNumIncomingValues() != 1) break; test. Isn't here are more conceptional condition, such that all uses are recognized inductions by SCEV instead counting the number of uses?

5606

[style] Function names should start with lower case.

[syzaara]

Shift handling into rewriteLoopExitValues so we can check each individual phi. Added a new entry to enum ReplaceExitVal called UnusedIndVar which will allow rewriteLoopExitValues to check for exit values that can be replaced when they are used as induction variables in the loop with no other uses in the loop.

[uabelho]

I've verified that the updated fix also solves the problem I saw.
Thanks!

[Meinersbur]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

110

UnusedIndVar seems to subsume OnlyCheapRepl. If this not tautological (see comment below), consider reflecting that in the description. Suggestion: "Replace only unused induction variables and only when the cost is cheap".

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

5604–5606

I like deferring this to rewriteLoopExitValue itself. 👍

llvm/lib/Transforms/Utils/LoopUtils.cpp

1316

[style]

1329

[style] No Almost-Always-Auto

[suggestion] Instead of set-flag-and-break, you may also consider if (llvm::any_of(Inst->users(), [](User *U) {...})) continue;. Alternatively, you could move all the conditions into a separate function where you just return false; when a violating condition is found no matter what loops it is nested in.

1336

This tries to check the "instruction is induction-phi" and "instruction is induction-operator" cases at the same time. You already determined which of the two cases it is above. That the wrong case applies here. isInductionPHI does not necessarily depend on there being an BinaryOperator as it works on the normalized SCEV. I.e. there might not be a BinaryOperator at all and the condition just pass through.

Could we merge the the two for (auto &U : Inst->uses()) loops, determine which of the two cases it is, and then require exactly one PHINode or BinaryOperator use?

1414

Is this assuming that unused induction variables are always cheap?

[syzaara]

Address review comments.

[syzaara]

ping

[uabelho]

Verified that the current patch also solves the problem I saw.
Thanks!

[syzaara]

@Meinersbur hi Michael, could you please take another look at the addressed review comments.

[bjope]

We get the "Assertion `EVL->contains(L) && "LCSSA breach detected!"' failed." assertion failures more or less every day in fuzzy testing which is pretty annoying. Just saying that I'm looking forward to the solution, although this review seems to have get stuck a couple of weeks ago :-(

Unfortunately I do not know much about the code involved to help out reviewing (unless it only are stylistic things remaining).

[Meinersbur]

LGTM

[Meinersbur]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

113–114

Could you update this to indicate that it is "unused in the loop"/it is only used to compute the loop LCSSA exit value?

[bjope]

Thanks! I've validated that our downstream tests that were hitting assertion failures related to this problem are passing again.

[nathanchance]

I bisected an assertion failure while building the Linux kernel for PowerPC to this patch:

# bad: [20962c1240691d25b21ce425313c81eed0b1b358] [SimplifyCFG] Don't split predecessors of callbr terminator
# good: [dc969061c68e62328607d68215ed8b9ef4a1e4b1] [SimplifyCFG] Thread all predecessors with same value at once
git bisect start '20962c1240691d25b21ce425313c81eed0b1b358' 'dc969061c68e62328607d68215ed8b9ef4a1e4b1'
# bad: [a6e63e35ede4b9f23b58437263eaac9a2926c9bf] [NFC][HLSL] Add tests for vector alias. Remove dead code.
git bisect bad a6e63e35ede4b9f23b58437263eaac9a2926c9bf
# good: [5493f8fc59ca9cc6fc14da8e6aafe6a52fb9ebc0] [VectorCombine] Improve shuffle select shuffle-of-shuffles
git bisect good 5493f8fc59ca9cc6fc14da8e6aafe6a52fb9ebc0
# bad: [b170d856a3a303ab826f6896812bfd0ce05ec706] [SimplifyCFG] Skip hoisting common instructions that return token type
git bisect bad b170d856a3a303ab826f6896812bfd0ce05ec706
# bad: [7b1ff859feaaf1316932d0be113d762626009fd6] [gn build] Port b8dbc6ffea93
git bisect bad 7b1ff859feaaf1316932d0be113d762626009fd6
# good: [a2158374ba1a6f81f4cce3eb54d0bc44f3ab75e0] [mlir][LLVMIR] Apply CallOp/CallableInterface on suitable operations
git bisect good a2158374ba1a6f81f4cce3eb54d0bc44f3ab75e0
# bad: [dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e] [LSR] Fix bug for optimizing unused IVs to final values
git bisect bad dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e
# good: [b8dbc6ffea93976dc0d8569c9d23e9c21e33e317] [HLSL] Add ExternalSemaSource & vector alias
git bisect good b8dbc6ffea93976dc0d8569c9d23e9c21e33e317
# first bad commit: [dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e] [LSR] Fix bug for optimizing unused IVs to final values

A simplified C reproducer:

enum { true } typedef size_t;
struct kernfs_node {
  struct kernfs_node *parent;
} kernfs_path_from_node_locked_kn_to;
size_t kernfs_path_from_node_locked___trans_tmp_1;
void kernfs_path_from_node() {
  asm goto("" : : : : __label_warn_on);
__label_warn_on:;
  struct kernfs_node *to = &kernfs_path_from_node_locked_kn_to;
  size_t depth;
  while (to) {
    depth++;
    to = to->parent;
  }
  kernfs_path_from_node_locked___trans_tmp_1 = depth;
}

$ clang --target=powerpc64-linux-gnu -O2 -c -o /dev/null dir.i
clang: /home/nathan/cbl/src/llvm-project/llvm/include/llvm/IR/Instructions.h:2838: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: clang --target=powerpc64-linux-gnu -O2 -c -o /dev/null dir.i
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module 'dir.i'.
4.      Running pass 'Loop Pass Manager' on function '@kernfs_path_from_node'
5.      Running pass 'Loop Strength Reduction' on basic block '%while.body'
 #0 0x000055926ab23473 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3445473)
 #1 0x000055926ab2140e llvm::sys::RunSignalHandlers() (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x344340e)
 #2 0x000055926aaa7893 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x000055926aaa7a0e CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007fbd976d8b90 __restore_rt (/lib64/libc.so.6+0x38b90)
 #5 0x00007fbd97728c4c __pthread_kill_implementation (/lib64/libc.so.6+0x88c4c)
 #6 0x00007fbd976d8ae6 gsignal (/lib64/libc.so.6+0x38ae6)
 #7 0x00007fbd976c27f4 abort (/lib64/libc.so.6+0x227f4)
 #8 0x00007fbd976c271b _nl_load_domain.cold (/lib64/libc.so.6+0x2271b)
 #9 0x00007fbd976d1696 (/lib64/libc.so.6+0x31696)
#10 0x0000559269ca1c1d llvm::InductionDescriptor::isInductionPHI(llvm::PHINode*, llvm::Loop const*, llvm::ScalarEvolution*, llvm::InductionDescriptor&, llvm::SCEV const*, llvm::SmallVectorImpl<llvm::Instruction*>*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x25c3c1d)
#11 0x000055926abe97dc llvm::rewriteLoopExitValues(llvm::Loop*, llvm::LoopInfo*, llvm::TargetLibraryInfo*, llvm::ScalarEvolution*, llvm::TargetTransformInfo const*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::ReplaceExitVal, llvm::SmallVector<llvm::WeakTrackingVH, 16u>&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x350b7dc)
#12 0x000055926a96f3d8 ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) LoopStrengthReduce.cpp:0:0
#13 0x000055926a99d154 (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopStrengthReduce.cpp:0:0
#14 0x0000559269efcaeb llvm::LPPassManager::runOnFunction(llvm::Function&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x281eaeb)
#15 0x000055926a3a7197 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cc9197)
#16 0x000055926a3aec41 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cd0c41)
#17 0x000055926a3a7ba5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cc9ba5)
#18 0x000055926b332f5d clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3c54f5d)
#19 0x000055926b6eafde clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#20 0x000055926bfbafc4 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x48dcfc4)
#21 0x000055926b62d8f0 clang::FrontendAction::Execute() (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3f4f8f0)
#22 0x000055926b5a1f5f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3ec3f5f)
#23 0x000055926b6e4682 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x4006682)
#24 0x00005592696f6f4a cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2018f4a)
#25 0x00005592696f4cdf ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#26 0x000055926b423572 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::$_1>(long) Job.cpp:0:0
#27 0x000055926aaa77a7 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x33c97a7)
#28 0x000055926b4230cf 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/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d450cf)
#29 0x000055926b3e2dde clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d04dde)
#30 0x000055926b3e308e clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d0508e)
#31 0x000055926b3ff030 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d21030)
#32 0x00005592696f43a1 clang_main(int, char**) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x20163a1)
#33 0x00007fbd976c3550 __libc_start_call_main (/lib64/libc.so.6+0x23550)
#34 0x00007fbd976c3609 __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x23609)
#35 0x00005592696f1945 _start /build/glibc/src/glibc/csu/../sysdeps/x86_64/start.S:117:0
clang-15: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 15.0.0 (https://github.com/llvm/llvm-project dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e)
Target: powerpc64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin
clang-15: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

At the parent commit, there is no crash.

[syzaara]

In D125990#3633683, @nathanchance wrote:

I bisected an assertion failure while building the Linux kernel for PowerPC to this patch:

# bad: [20962c1240691d25b21ce425313c81eed0b1b358] [SimplifyCFG] Don't split predecessors of callbr terminator
# good: [dc969061c68e62328607d68215ed8b9ef4a1e4b1] [SimplifyCFG] Thread all predecessors with same value at once
git bisect start '20962c1240691d25b21ce425313c81eed0b1b358' 'dc969061c68e62328607d68215ed8b9ef4a1e4b1'
# bad: [a6e63e35ede4b9f23b58437263eaac9a2926c9bf] [NFC][HLSL] Add tests for vector alias. Remove dead code.
git bisect bad a6e63e35ede4b9f23b58437263eaac9a2926c9bf
# good: [5493f8fc59ca9cc6fc14da8e6aafe6a52fb9ebc0] [VectorCombine] Improve shuffle select shuffle-of-shuffles
git bisect good 5493f8fc59ca9cc6fc14da8e6aafe6a52fb9ebc0
# bad: [b170d856a3a303ab826f6896812bfd0ce05ec706] [SimplifyCFG] Skip hoisting common instructions that return token type
git bisect bad b170d856a3a303ab826f6896812bfd0ce05ec706
# bad: [7b1ff859feaaf1316932d0be113d762626009fd6] [gn build] Port b8dbc6ffea93
git bisect bad 7b1ff859feaaf1316932d0be113d762626009fd6
# good: [a2158374ba1a6f81f4cce3eb54d0bc44f3ab75e0] [mlir][LLVMIR] Apply CallOp/CallableInterface on suitable operations
git bisect good a2158374ba1a6f81f4cce3eb54d0bc44f3ab75e0
# bad: [dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e] [LSR] Fix bug for optimizing unused IVs to final values
git bisect bad dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e
# good: [b8dbc6ffea93976dc0d8569c9d23e9c21e33e317] [HLSL] Add ExternalSemaSource & vector alias
git bisect good b8dbc6ffea93976dc0d8569c9d23e9c21e33e317
# first bad commit: [dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e] [LSR] Fix bug for optimizing unused IVs to final values

A simplified C reproducer:

enum { true } typedef size_t;
struct kernfs_node {
  struct kernfs_node *parent;
} kernfs_path_from_node_locked_kn_to;
size_t kernfs_path_from_node_locked___trans_tmp_1;
void kernfs_path_from_node() {
  asm goto("" : : : : __label_warn_on);
__label_warn_on:;
  struct kernfs_node *to = &kernfs_path_from_node_locked_kn_to;
  size_t depth;
  while (to) {
    depth++;
    to = to->parent;
  }
  kernfs_path_from_node_locked___trans_tmp_1 = depth;
}

$ clang --target=powerpc64-linux-gnu -O2 -c -o /dev/null dir.i
clang: /home/nathan/cbl/src/llvm-project/llvm/include/llvm/IR/Instructions.h:2838: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: clang --target=powerpc64-linux-gnu -O2 -c -o /dev/null dir.i
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module 'dir.i'.
4.      Running pass 'Loop Pass Manager' on function '@kernfs_path_from_node'
5.      Running pass 'Loop Strength Reduction' on basic block '%while.body'
 #0 0x000055926ab23473 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3445473)
 #1 0x000055926ab2140e llvm::sys::RunSignalHandlers() (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x344340e)
 #2 0x000055926aaa7893 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x000055926aaa7a0e CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007fbd976d8b90 __restore_rt (/lib64/libc.so.6+0x38b90)
 #5 0x00007fbd97728c4c __pthread_kill_implementation (/lib64/libc.so.6+0x88c4c)
 #6 0x00007fbd976d8ae6 gsignal (/lib64/libc.so.6+0x38ae6)
 #7 0x00007fbd976c27f4 abort (/lib64/libc.so.6+0x227f4)
 #8 0x00007fbd976c271b _nl_load_domain.cold (/lib64/libc.so.6+0x2271b)
 #9 0x00007fbd976d1696 (/lib64/libc.so.6+0x31696)
#10 0x0000559269ca1c1d llvm::InductionDescriptor::isInductionPHI(llvm::PHINode*, llvm::Loop const*, llvm::ScalarEvolution*, llvm::InductionDescriptor&, llvm::SCEV const*, llvm::SmallVectorImpl<llvm::Instruction*>*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x25c3c1d)
#11 0x000055926abe97dc llvm::rewriteLoopExitValues(llvm::Loop*, llvm::LoopInfo*, llvm::TargetLibraryInfo*, llvm::ScalarEvolution*, llvm::TargetTransformInfo const*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::ReplaceExitVal, llvm::SmallVector<llvm::WeakTrackingVH, 16u>&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x350b7dc)
#12 0x000055926a96f3d8 ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) LoopStrengthReduce.cpp:0:0
#13 0x000055926a99d154 (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopStrengthReduce.cpp:0:0
#14 0x0000559269efcaeb llvm::LPPassManager::runOnFunction(llvm::Function&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x281eaeb)
#15 0x000055926a3a7197 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cc9197)
#16 0x000055926a3aec41 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cd0c41)
#17 0x000055926a3a7ba5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2cc9ba5)
#18 0x000055926b332f5d clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3c54f5d)
#19 0x000055926b6eafde clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#20 0x000055926bfbafc4 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x48dcfc4)
#21 0x000055926b62d8f0 clang::FrontendAction::Execute() (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3f4f8f0)
#22 0x000055926b5a1f5f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3ec3f5f)
#23 0x000055926b6e4682 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x4006682)
#24 0x00005592696f6f4a cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x2018f4a)
#25 0x00005592696f4cdf ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#26 0x000055926b423572 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::$_1>(long) Job.cpp:0:0
#27 0x000055926aaa77a7 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x33c97a7)
#28 0x000055926b4230cf 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/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d450cf)
#29 0x000055926b3e2dde clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d04dde)
#30 0x000055926b3e308e clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d0508e)
#31 0x000055926b3ff030 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x3d21030)
#32 0x00005592696f43a1 clang_main(int, char**) (/home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin/clang-15+0x20163a1)
#33 0x00007fbd976c3550 __libc_start_call_main (/lib64/libc.so.6+0x23550)
#34 0x00007fbd976c3609 __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x23609)
#35 0x00005592696f1945 _start /build/glibc/src/glibc/csu/../sysdeps/x86_64/start.S:117:0
clang-15: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 15.0.0 (https://github.com/llvm/llvm-project dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e)
Target: powerpc64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/tmp/install/llvm/dbf6ab5ef9ae0e1f4706917c2b3f98a67c35826e/bin
clang-15: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

At the parent commit, there is no crash.

Thank you for the reproducer! Posted fix in https://reviews.llvm.org/D129297

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// Returns true if \p S is defined and never is equal to signed/unsigned max.
 bool cannotBeMaxInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
                        bool Signed);
 
 /// Returns true if \p S is defined and never is equal to signed/unsigned min.
 bool cannotBeMinInLoop(const SCEV *S, const Loop *L, ScalarEvolution &SE,
                        bool Signed);
 
-enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, NoHardUse, AlwaysRepl };
+enum ReplaceExitVal {
+  NeverRepl,
+  OnlyCheapRepl,
+  NoHardUse,
+  UnusedIndVarInLoop,
+  AlwaysRepl
+};
 
 /// If the final value of any expressions that are recurrent in the loop can
 /// be computed, substitute the exit values from the loop into any instructions
 /// outside of the loop that use the final values of the current expressions.
 /// Return the number of loop exit values that have been replaced, and the
 /// corresponding phi node will be added to DeadInsts.
 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
                           ScalarEvolution *SE, const TargetTransformInfo *TTI,

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

static cl::opt<bool> VerifyIndvars(
     "verify-indvars", cl::Hidden,
     cl::desc("Verify the ScalarEvolution result after running indvars. Has no "
              "effect in release builds. (Note: this adds additional SCEV "
              "queries potentially changing the analysis result)"));
 
 static cl::opt<ReplaceExitVal> ReplaceExitValue(
     "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
     cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
-    cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
-               clEnumValN(OnlyCheapRepl, "cheap",
-                          "only replace exit value when the cost is cheap"),
-               clEnumValN(NoHardUse, "noharduse",
-                          "only replace exit values when loop def likely dead"),
-               clEnumValN(AlwaysRepl, "always",
-                          "always replace exit value whenever possible")));
+    cl::values(
+        clEnumValN(NeverRepl, "never", "never replace exit value"),
+        clEnumValN(
+            UnusedIndVarInLoop, "unusedindvarinloop",
+            "only replace exit value when it is an unused "
+            "induction variable in the loop and has cheap replacement cost"),
 
 static cl::opt<bool> UsePostIncrementRanges(
   "indvars-post-increment-ranges", cl::Hidden,
   cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),
   cl::init(true));
 
 static cl::opt<bool>
 DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (LU.Kind == LSRUse::ICmpZero)
       LF.UserInst->setOperand(0, FullV);
     else
       LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV);
   }
 
   if (auto *OperandIsInstr = dyn_cast<Instruction>(LF.OperandValToReplace))
     DeadInsts.emplace_back(OperandIsInstr);
 }
 
-// Check if there are any loop exit values which are only used once within the
-// loop which may potentially be optimized with a call to rewriteLoopExitValue.
-static bool LoopExitValHasSingleUse(Loop *L) {
-  BasicBlock *ExitBB = L->getExitBlock();
-  if (!ExitBB)
-    return false;
-
-  for (PHINode &ExitPhi : ExitBB->phis()) {
-    if (ExitPhi.getNumIncomingValues() != 1)
-      break;
-
-    BasicBlock *Pred = ExitPhi.getIncomingBlock(0);
-    Value *IVNext = ExitPhi.getIncomingValueForBlock(Pred);
-    // One use would be the exit phi node, and there should be only one other
-    // use for this to be considered.
-    if (IVNext->getNumUses() == 2)
-      return true;
-  }
-  return false;
-}
-
 /// Rewrite all the fixup locations with new values, following the chosen
 /// solution.
 void LSRInstance::ImplementSolution(
     const SmallVectorImpl<const Formula *> &Solution) {
   // Keep track of instructions we may have made dead, so that
   // we can remove them after we are done working.
   SmallVector<WeakTrackingVH, 16> DeadInsts;
 
   SCEVExpander Rewriter(SE, L->getHeader()->getModule()->getDataLayout(), "lsr",
                         false);
 #ifndef NDEBUG
if (numFolded) {
       DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
     }
   }
   // LSR may at times remove all uses of an induction variable from a loop.
   // The only remaining use is the PHI in the exit block.
   // When this is the case, if the exit value of the IV can be calculated using
   // SCEV, we can replace the exit block PHI with the final value of the IV and
   // skip the updates in each loop iteration.
-  if (L->isRecursivelyLCSSAForm(DT, LI) && LoopExitValHasSingleUse(L)) {
+  if (L->isRecursivelyLCSSAForm(DT, LI) && L->getExitBlock()) {
     SmallVector<WeakTrackingVH, 16> DeadInsts;
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
     SCEVExpander Rewriter(SE, DL, "lsr", false);
     int Rewrites = rewriteLoopExitValues(L, &LI, &TLI, &SE, &TTI, Rewriter, &DT,
-                                         OnlyCheapRepl, DeadInsts);
+                                         UnusedIndVarInLoop, DeadInsts);
     if (Rewrites) {
       Changed = true;
       RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts, &TLI,
                                                            MSSAU.get());
       DeleteDeadPHIs(L->getHeader(), &TLI, MSSAU.get());
     }
   }
 

llvm/lib/Transforms/Utils/LoopUtils.cpp

while ((PN = dyn_cast<PHINode>(BBI++))) {
         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
           continue; // The Block is in a subloop, skip it.
 
         // Check that InVal is defined in the loop.
         Instruction *Inst = cast<Instruction>(InVal);
         if (!L->contains(Inst))
           continue;
 
+        // Find exit values which are induction variables in the loop, and are
+        // unused in the loop, with the only use being the exit block PhiNode,
+        // and the induction variable update binary operator.
+        // The exit value can be replaced with the final value when it is cheap
+        // to do so.
+        if (ReplaceExitValue == UnusedIndVarInLoop) {
+          InductionDescriptor ID;
+          PHINode *IndPhi = dyn_cast<PHINode>(Inst);
+          if (IndPhi) {
+            if (IndPhi->getParent() != L->getHeader())
+              continue;
+            // Do not consider non induction phis.
+            if (!InductionDescriptor::isInductionPHI(IndPhi, L, SE, ID))
+              continue;
+            // This is an induction PHI. Check that the only users are PHI
+            // nodes, and induction variable update binary operators.
+            if (llvm::any_of(Inst->users(), [&](User *U) {
+                  if (!isa<PHINode>(U) && !isa<BinaryOperator>(U))
+                    return true;
+                  BinaryOperator *B = dyn_cast<BinaryOperator>(U);
+                  if (B && B != ID.getInductionBinOp())
+                    return true;
+                  return false;
+                }))
+              continue;
+          } else {
+            // If it is not an induction phi, it must be an induction update
+            // binary operator with an induction phi user.
+            BinaryOperator *B = dyn_cast<BinaryOperator>(Inst);
+            if (!B)
+              continue;
+            if (llvm::any_of(Inst->users(), [&](User *U) {
+                  PHINode *Phi = dyn_cast<PHINode>(U);
+                  if (!Phi)
+                    return true;
+                  if (Phi->getParent() == L->getHeader()) {
+                    if (!InductionDescriptor::isInductionPHI(Phi, L, SE, ID))
+                      return true;
+                  }
+                  return false;
+                }))
+              continue;
+            if (B != ID.getInductionBinOp())
+              continue;
+          }
+        }
+
         // Okay, this instruction has a user outside of the current loop
         // and varies predictably *inside* the loop.  Evaluate the value it
         // contains when the loop exits, if possible.  We prefer to start with
         // expressions which are true for all exits (so as to maximize
         // expression reuse by the SCEVExpander), but resort to per-exit
         // evaluation if that fails.
         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
         if (isa<SCEVCouldNotCompute>(ExitValue) ||
int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
   int NumReplaced = 0;
 
   // Transformation.
   for (const RewritePhi &Phi : RewritePhiSet) {
     PHINode *PN = Phi.PN;
 
     // Only do the rewrite when the ExitValue can be expanded cheaply.
     // If LoopCanBeDel is true, rewrite exit value aggressively.
-    if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost)
+    if ((ReplaceExitValue == OnlyCheapRepl ||
+         ReplaceExitValue == UnusedIndVarInLoop) &&
+        !LoopCanBeDel && Phi.HighCost)
       continue;
 
     Value *ExitVal = Rewriter.expandCodeFor(
         Phi.ExpansionSCEV, Phi.PN->getType(), Phi.ExpansionPoint);
 
     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = " << *ExitVal
                       << '\n'
                       << "  LoopVal = " << *(Phi.ExpansionPoint) << "\n");

llvm/test/Transforms/LoopStrengthReduce/remove_scev_indvars.ll

 ; CHECK: %indvars.iv.unr = phi i64 [ %1, %for.exit ]
 for.exit:
   %iv.prol.lcssa = phi i64 [ %iv.prol, %for.body ]
   br label %exit
 exit:
   %indvars.iv.unr = phi i64 [%iv.prol.lcssa, %for.exit]
   ret void
 }
+
+define void @testNonIndVarPhi() {
+cont5820:
+  br label %for.cond5821
+
+for.cond5821:                                     ; preds = %cont5825, %cont5820
+  %0 = phi i32 [ 0, %cont5825 ], [ 1, %cont5820 ]
+  br label %cont5825
+
+cont5825:                                         ; preds = %for.cond5821
+  br i1 false, label %for.cond5821, label %for.cond6403
+
+for.cond6403:                                     ; preds = %dead, %cont5825
+  %1 = phi i32 [ %.lcssa221, %dead ], [ 0, %cont5825 ]
+  br label %for.cond6418
+
+for.cond6418:                                     ; preds = %cont6497, %for.cond6403
+  %2 = phi i32 [ %0, %cont6497 ], [ %1, %for.cond6403 ]
+  %3 = phi i64 [ 1, %cont6497 ], [ 0, %for.cond6403 ]
+  %cmp6419 = icmp ule i64 %3, 0
+  br i1 %cmp6419, label %cont6497, label %for.end6730
+
+cont6497:                                         ; preds = %for.cond6418
+  %conv6498 = sext i32 %2 to i64
+  br label %for.cond6418
+
+for.end6730:                                      ; preds = %for.cond6418
+; Check that we don't make changes for phis which are not considered
+; induction variables
+; CHECK: %.lcssa221 = phi i32 [ %2, %for.cond6418 ]
+  %.lcssa221 = phi i32 [ %2, %for.cond6418 ]
+  ret void
+
+dead:                                             ; No predecessors!
+  br label %for.cond6403
+}