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.

In D118808#3518558, @uabelho wrote:

Hi,

The following starts crashing with this patch:

llc -O1 -o /dev/null bbi-69670_x86.ll

I get:

llc: ../lib/Transforms/Utils/LoopUtils.cpp:1385: int llvm::rewriteLoopExitValues(llvm::Loop *, llvm::LoopInfo *, llvm::TargetLibraryInfo *, llvm::ScalarEvolution *, const llvm::TargetTransformInfo *, llvm::SCEVExpander &, llvm::DominatorTree *, llvm::ReplaceExitVal, SmallVector<llvm::WeakTrackingVH, 16> &): Assertion `EVL->contains(L) && "LCSSA breach detected!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/llc -O1 -o /dev/null bbi-69670_x86.ll
1.	Running pass 'Function Pass Manager' on module 'bbi-69670_x86.ll'.
2.	Running pass 'Loop Pass Manager' on function '@func_1'
3.	Running pass 'Loop Strength Reduction' on basic block '%for.cond6418'
 #0 0x0000000002abded3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/llc+0x2abded3)
 #1 0x0000000002abbb4e llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/llc+0x2abbb4e)
 #2 0x0000000002abe256 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007fcb1f00e630 __restore_rt sigaction.c:0:0
 #4 0x00007fcb1c755387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007fcb1c756a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007fcb1c74e1a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007fcb1c74e252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000002b80be3 llvm::rewriteLoopExitValues(llvm::Loop*, llvm::LoopInfo*, llvm::TargetLibraryInfo*, llvm::ScalarEvolution*, llvm::TargetTransformInfo const*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::ReplaceExitVal, llvm::SmallVector<llvm::WeakTrackingVH, 16u>&) (../../main-github/llvm/build-all/bin/llc+0x2b80be3)
 #9 0x00000000024c0a1e ReduceLoopStrength(llvm::Loop*, llvm::IVUsers&, llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::MemorySSA*) LoopStrengthReduce.cpp:0:0
#10 0x00000000024ec121 (anonymous namespace)::LoopStrengthReduce::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopStrengthReduce.cpp:0:0
#11 0x0000000001b2d17b llvm::LPPassManager::runOnFunction(llvm::Function&) (../../main-github/llvm/build-all/bin/llc+0x1b2d17b)
#12 0x000000000230895f llvm::FPPassManager::runOnFunction(llvm::Function&) (../../main-github/llvm/build-all/bin/llc+0x230895f)
#13 0x000000000230f398 llvm::FPPassManager::runOnModule(llvm::Module&) (../../main-github/llvm/build-all/bin/llc+0x230f398)
#14 0x0000000002308f2d llvm::legacy::PassManagerImpl::run(llvm::Module&) (../../main-github/llvm/build-all/bin/llc+0x2308f2d)
#15 0x000000000074a073 main (../../main-github/llvm/build-all/bin/llc+0x74a073)
#16 0x00007fcb1c741555 __libc_start_main (/lib64/libc.so.6+0x22555)
#17 0x0000000000747670 _start (../../main-github/llvm/build-all/bin/llc+0x747670)
Abort

bbi-69670_x86.ll1 KBDownload

I wouldn't be surprised if it's the dead bb jumping to non-dead code that trips up something:

for.cond6403:                                     ; preds = %dead, %cont5825
  %1 = phi i32 [ %.lcssa221, %dead ], [ 0, %cont5825 ]
  br label %for.cond6418
[...]
dead:                                             ; No predecessors!
  br label %for.cond6403

I wrote
https://github.com/llvm/llvm-project/issues/55529
about the crash.

In D123408#3443538, @bmahjour wrote:

The cleanest way I can think of to teach LoopVectorizer about this would be to introduce a whole new set of composite reduction operations of the form <op>-then-<lop> (eg RecurKind::AddThenAnd, RecurKind::MulThenAnd, RecurKind::OrThenAnd, and so on)...and that's just for combining logical and with the known integer reduction ops, so if we want to support e.g. or we'd need to double the number of additional recurrence kinds (and the extra logic that comes with it) again. The identity value would be determined from the <op>, and the <lop> has to be applied when reducing the final vector into a single scalar upon loop exit.

@lebedev.ri is this what you had in mind or is there a better way to do it?

In D123408#3439555, @lebedev.ri wrote:

This seems like a vectorizer bug.

Updated to use rewriteLoopExitValues from LoopUtils.

In D118808#3365997, @Whitney wrote:

IndVarSimply calls rewriteLoopExitValues from LoopUtils to do this optimization. I tried to call the same function in LoopStrengthReduce, however rewriteLoopExitValues asserts that it requires: L->isRecursivelyLCSSAForm(*DT, *LI).

When calling rewriteLoopExitValues from LoopStrengthReduce, this assert is not met.

I am confused, is the assert from rewriteLoopExitValues met or not when calling from LoopStrengthReduce? Does LoopStrengthReduce currently rely on LCSSA form? Is it only become not LCSSA after LoopStrengthReduce changes the code?
Can we first invoke formLCSSA to form LCSSA before calling rewriteLoopExitValues?

In D118808#3338917, @Whitney wrote:

Is it possible to abstract the portion of the code in IndVarSimplify to simplify this code pattern, and call that function instead of creating your own ReplaceExitPHIsWithFinalVal?

@nikic Hi Nikita, could you help me with assessing the compile time impact of adding the IndVarSimplifyPass after LoopStrengthReduce?

PING

In D118808#3290873, @lebedev.ri wrote:

This is normally a IndVar's problem, but i guess LSR runs so late that there is no IndVar's scheduled after it?
Do you have a phase-ordering test showing this missing simplification?

In D118808#3290873, @lebedev.ri wrote:

This is normally a IndVar's problem, but i guess LSR runs so late that there is no IndVar's scheduled after it?
Do you have a phase-ordering test showing this missing simplification?

LGTM

We have similar definitions in PPCDisassembler.cpp, it would be good to condense those definitions as well.

In D48091#1165410, @MaskRay wrote:

Just a question. Does this patch support the optimization that fills in the GOT slot when a group of initial-exec relocations are known to be link-time constants?

__attribute__((tls_model("initial-exec")))
static __thread DTLS dtls;

48:   00 00 62 3c     addis   r3,r2,0
                      48: R_PPC64_GOT_TPREL16_HA      _ZN11__sanitizerL4dtlsE
4c:   00 00 63 e8     ld      r3,0(r3)
                      4c: R_PPC64_GOT_TPREL16_LO_DS   _ZN11__sanitizerL4dtlsE
50:   14 6a 83 7c     add     r4,r3,r13
                      50: R_PPC64_TLS _ZN11__sanitizerL4dtlsE

https://github.com/llvm-mirror/lld/tree/master/ELF/Relocations.cpp#L747

template <class ELFT> static void addGotEntry(Symbol &Sym) {
...
  bool IsLinkTimeConstant =
      !Sym.IsPreemptible && (!Config->Pic || isAbsolute(Sym));
  /// if R_PPC64_GOT_TPREL16_HA R_PPC64_GOT_TPREL16_LO_DS are link-time constants, they can be filled but `Target->GotRel` should not be used here as it is a 64-bit value.
  /// Target->GotRel is R_PPC64_GLOB_DAT but I think it should not be used.
  if (IsLinkTimeConstant) {
    InX::Got->Relocations.push_back({Expr, Target->GotRel, Off, 0, &Sym});
    return;
  }

@kcc @filcab Should this test be disabled for PPC?

LGTM

LGTM