Revert "Recommit "[SCEV] Look through single value PHIs." (take 3)"

This reverts commit 20d798bd47ec5191de1b2a8a031da06a04e612e1.

This commit caused crashes in some cases, see github issue #58152.

Revert "Recommit "[SCEV] Look through single value PHIs." (take 3)"

This reverts commit 20d798bd47ec5191de1b2a8a031da06a04e612e1.

This commit caused crashes in some cases, see github issue #58152.
This is fixed on main, but backporting it requires multiple
nontrivial cherrypicks.

Updating llvm/test/Transforms/LoopVectorize/create-induction-resume.ll
with update_test_checks.py, so this isn't an exact automatic revert,
as that test case was added after the reverted commit.

This fixes #58152 for the release branch.

show more ...

Recommit "[SCEV] Look through single value PHIs." (take 3)

This reverts commit 1fbdbb559569641f6d509b569966901c8fb02b63.

All known issues surfaced by this patch should have been fixed now.

The fix

Recommit "[SCEV] Look through single value PHIs." (take 3)

This reverts commit 1fbdbb559569641f6d509b569966901c8fb02b63.

All known issues surfaced by this patch should have been fixed now.

The fixes included fixing issues with SCEV expansion in LV and DA's
reliance on LCSSA phis.

show more ...

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions ar

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions are not
properly invalidated.

See PR52024, PR52023.

show more ...

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Or

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Original message:

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.

This increases precision of the analysis in some cases.

Reviewed By: mkazantsev, bmahjour

Differential Revision: https://reviews.llvm.org/D71539

show more ...

Recommit [ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers.

As part of making ScalarEvolution's handling of pointers consistent, we
want to forbid multiplying a pointer by -1 (or any

Recommit [ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers.

As part of making ScalarEvolution's handling of pointers consistent, we
want to forbid multiplying a pointer by -1 (or any other value). This
means we can't blindly subtract pointers.

There are a few ways we could deal with this:
1. We could completely forbid subtracting pointers in getMinusSCEV()
2. We could forbid subracting pointers with different pointer bases
(this patch).
3. We could try to ptrtoint pointer operands.

The option in this patch is more friendly to non-integral pointers: code
that works with normal pointers will also work with non-integral
pointers. And it seems like there are very few places that actually
benefit from the third option.

As a minimal patch, the ScalarEvolution implementation of getMinusSCEV
still ends up subtracting pointers if they have the same base. This
should eliminate the shared pointer base, but eventually we'll need to
rewrite it to avoid negating the pointer base. I plan to do this as a
separate step to allow measuring the compile-time impact.

This doesn't cause obvious functional changes in most cases; the one
case that is significantly affected is ICmpZero handling in LSR (which
is the source of almost all the test changes). The resulting changes
seem okay to me, but suggestions welcome. As an alternative, I tried
explicitly ptrtoint'ing the operands, but the result doesn't seem
obviously better.

I deleted the test lsr-undef-in-binop.ll becuase I couldn't figure out
how to repair it to test what it was actually trying to test.

Recommitting with fix to MemoryDepChecker::isDependent.

Differential Revision: https://reviews.llvm.org/D104806

show more ...

Revert "[ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers."

This reverts commit 74d6ce5d5f169e9cf3fac0eb1042602e286dd2b9.

Seeing crashes on buildbots in MemoryDepChecker::isDependen

Revert "[ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers."

This reverts commit 74d6ce5d5f169e9cf3fac0eb1042602e286dd2b9.

Seeing crashes on buildbots in MemoryDepChecker::isDependent.

show more ...

[ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers.

As part of making ScalarEvolution's handling of pointers consistent, we
want to forbid multiplying a pointer by -1 (or any other va

[ScalarEvolution] Make getMinusSCEV() fail for unrelated pointers.

As part of making ScalarEvolution's handling of pointers consistent, we
want to forbid multiplying a pointer by -1 (or any other value). This
means we can't blindly subtract pointers.

There are a few ways we could deal with this:
1. We could completely forbid subtracting pointers in getMinusSCEV()
2. We could forbid subracting pointers with different pointer bases
(this patch).
3. We could try to ptrtoint pointer operands.

The option in this patch is more friendly to non-integral pointers: code
that works with normal pointers will also work with non-integral
pointers. And it seems like there are very few places that actually
benefit from the third option.

As a minimal patch, the ScalarEvolution implementation of getMinusSCEV
still ends up subtracting pointers if they have the same base. This
should eliminate the shared pointer base, but eventually we'll need to
rewrite it to avoid negating the pointer base. I plan to do this as a
separate step to allow measuring the compile-time impact.

This doesn't cause obvious functional changes in most cases; the one
case that is significantly affected is ICmpZero handling in LSR (which
is the source of almost all the test changes). The resulting changes
seem okay to me, but suggestions welcome. As an alternative, I tried
explicitly ptrtoint'ing the operands, but the result doesn't seem
obviously better.

I deleted the test lsr-undef-in-binop.ll becuase I couldn't figure out
how to repair it to test what it was actually trying to test.

Differential Revision: https://reviews.llvm.org/D104806

show more ...

Revert D71539 "Recommit "[SCEV] Look through single value PHIs.""

This reverts commit 11dccf8d3aa5d55210f8b886fb21926c7a8353ca.

A bootstrapped clang crashes (due to ArrayRef::front called on an emp

Revert D71539 "Recommit "[SCEV] Look through single value PHIs.""

This reverts commit 11dccf8d3aa5d55210f8b886fb21926c7a8353ca.

A bootstrapped clang crashes (due to ArrayRef::front called on an empty
ArrayRef) when compiling some files. Very strangely, this only reproduces with
modules.

```
13 0x0000564d3349e968 llvm::ArrayRef<llvm::BasicBlock*>::front() const /proc/self/cwd/llvm/include/llvm/ADT/ArrayRef.h:160:7
14 0x0000564d3349e896 llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getHeader() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfo.h:104:50
15 0x0000564d3349fd9d llvm::LoopBase<llvm::BasicBlock, llvm::Loop>::getLoopLatch() const /proc/self/cwd/llvm/include/llvm/Analysis/LoopInfoImpl.h:210:11
16 0x0000564d33593c8a llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6933:15
17 0x0000564d33592ebc llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:0:30
18 0x0000564d33593a54 llvm::ScalarEvolution::getBackedgeTakenCount(llvm::Loop const*, llvm::ScalarEvolution::ExitCountKind) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:6487:36
19 0x0000564d32be2402 llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount(llvm::Loop const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:768:5
20 0x0000564d33590807 llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:5495:19
21 0x0000564d320abab7 llvm::ScalarEvolution::getSignedRange(llvm::SCEV const*) /proc/self/cwd/llvm/include/llvm/Analysis/ScalarEvolution.h:840:12
22 0x0000564d335a03aa llvm::ScalarEvolution::isKnownPredicateViaConstantRanges(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:9239:60
23 0x0000564d33586a80 llvm::ScalarEvolution::isKnownViaNonRecursiveReasoning(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) /proc/self/cwd/llvm/lib/Analysis/ScalarEvolution.cpp:10284:60
```

show more ...

Recommit "[SCEV] Look through single value PHIs."

This commit was originally because it was suspected to cause a crash,
but a reproducer did not surface.

A crash that was exposed by this change was

Recommit "[SCEV] Look through single value PHIs."

This commit was originally because it was suspected to cause a crash,
but a reproducer did not surface.

A crash that was exposed by this change was fixed in 1d8f2e52925b.

This reverts the revert commit 0581c0b0eeba03da590d1176a4580cf9b9e8d1e3.

show more ...

Revert "[SCEV] Look through single value PHIs."

This reverts commit e441b7a7a0a72c28daf5a8e594559c667e5b4534.

This patch causes a compile error in tensorflow opensource project. The stack trace loo

Revert "[SCEV] Look through single value PHIs."

This reverts commit e441b7a7a0a72c28daf5a8e594559c667e5b4534.

This patch causes a compile error in tensorflow opensource project. The stack trace looks like:

Point of crash:
llvm/include/llvm/Analysis/LoopInfoImpl.h : line 35

(gdb) ptype *this
type = const class llvm::LoopBase<llvm::BasicBlock, llvm::Loop> [with BlockT = llvm::BasicBlock, LoopT = llvm::Loop]

(gdb) p *this
$1 = {ParentLoop = 0x0, SubLoops = std::vector of length 0, capacity 0, Blocks = std::vector of length 0, capacity 1,
DenseBlockSet = {<llvm::SmallPtrSetImpl<llvm::BasicBlock const*>> = {<llvm::SmallPtrSetImplBase> = {<llvm::DebugEpochBase> = {Epoch = 3}, SmallArray = 0x1b2bf6c8, CurArray = 0x1b2bf6c8,
CurArraySize = 8, NumNonEmpty = 0, NumTombstones = 0}, <No data fields>}, SmallStorage = {0xfffffffffffffffe, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}}, IsInvalid = true}

(gdb) p *this->DenseBlockSet->CurArray
$2 = (const void *) 0xfffffffffffffffe

I will try to get a case from tensorflow or use creduce to get a small case.

show more ...

[SCEV] Look through single value PHIs.

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of insert

[SCEV] Look through single value PHIs.

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.

This increases precision of the analysis in some cases.

Reviewed By: mkazantsev, bmahjour

Differential Revision: https://reviews.llvm.org/D71539

show more ...

[SCEV] Add additional tests.

Increase test coverage for upcoming changes to how SCEV deals with LCSSA
phis.

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[LoopStrengthReduce] Don't rewrite PHIs with incoming values from CatchSwitches

Bail out if we have a PHI on an EHPad that gets a value from a
CatchSwitchInst. Because the CatchSwitchInst cannot be

[LoopStrengthReduce] Don't rewrite PHIs with incoming values from CatchSwitches

Bail out if we have a PHI on an EHPad that gets a value from a
CatchSwitchInst. Because the CatchSwitchInst cannot be split, there is
no good place to stick any instructions.

This fixes PR26373.

llvm-svn: 259702

show more ...

[IR] Remove terminatepad

It turns out that terminatepad gives little benefit over a cleanuppad
which calls the termination function. This is not sufficient to
implement fully generic filters but MS

[IR] Remove terminatepad

It turns out that terminatepad gives little benefit over a cleanuppad
which calls the termination function. This is not sufficient to
implement fully generic filters but MSVC doesn't support them which
makes terminatepad a little over-designed.

Depends on D15478.

Differential Revision: http://reviews.llvm.org/D15479

llvm-svn: 255522

show more ...

[IR] Reformulate LLVM's EH funclet IR

While we have successfully implemented a funclet-oriented EH scheme on
top of LLVM IR, our scheme has some notable deficiencies:
- catchendpad and cleanupendpad

[IR] Reformulate LLVM's EH funclet IR

While we have successfully implemented a funclet-oriented EH scheme on
top of LLVM IR, our scheme has some notable deficiencies:
- catchendpad and cleanupendpad are necessary in the current design
but they are difficult to explain to others, even to seasoned LLVM
experts.
- catchendpad and cleanupendpad are optimization barriers. They cannot
be split and force all potentially throwing call-sites to be invokes.
This has a noticable effect on the quality of our code generation.
- catchpad, while similar in some aspects to invoke, is fairly awkward.
It is unsplittable, starts a funclet, and has control flow to other
funclets.
- The nesting relationship between funclets is currently a property of
control flow edges. Because of this, we are forced to carefully
analyze the flow graph to see if there might potentially exist illegal
nesting among funclets. While we have logic to clone funclets when
they are illegally nested, it would be nicer if we had a
representation which forbade them upfront.

Let's clean this up a bit by doing the following:
- Instead, make catchpad more like cleanuppad and landingpad: no control
flow, just a bunch of simple operands; catchpad would be splittable.
- Introduce catchswitch, a control flow instruction designed to model
the constraints of funclet oriented EH.
- Make funclet scoping explicit by having funclet instructions consume
the token produced by the funclet which contains them.
- Remove catchendpad and cleanupendpad. Their presence can be inferred
implicitly using coloring information.

N.B. The state numbering code for the CLR has been updated but the
veracity of it's output cannot be spoken for. An expert should take a
look to make sure the results are reasonable.

Reviewers: rnk, JosephTremoulet, andrew.w.kaylor

Differential Revision: http://reviews.llvm.org/D15139

llvm-svn: 255422

show more ...

[LoopStrengthReduce] Don't bother fixing up PHIs from EH Pad preds

We cannot really insert fixup code into a PHI's predecessor.

This fixes PR25445.

llvm-svn: 252416

[ScalarEvolutionExpander] PHI on a catchpad can be used on both edges

A PHI on a catchpad might be used by both edges out of the catchpad,
feeding back into a loop. In this case, just use the inser

[ScalarEvolutionExpander] PHI on a catchpad can be used on both edges

A PHI on a catchpad might be used by both edges out of the catchpad,
feeding back into a loop. In this case, just use the insertion point.
Anything more clever would require new basic blocks or PHI placement.

llvm-svn: 251442

show more ...

[ScalarEvolutionExpander] Properly insert no-op casts + EH Pads

We want to insert no-op casts as close as possible to the def. This is
tricky when the cast is of a PHI node and the BasicBlocks betw

[ScalarEvolutionExpander] Properly insert no-op casts + EH Pads

We want to insert no-op casts as close as possible to the def. This is
tricky when the cast is of a PHI node and the BasicBlocks between the
def and the use cannot hold any instructions. Iteratively walk EH pads
until we hit a non-EH pad.

This fixes PR25326.

llvm-svn: 251393

show more ...