[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and sim

[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to moveBefore use iterators.

This patch adds a (guaranteed dereferenceable) iterator-taking
moveBefore, and changes a bunch of call-sites where it's obviously safe
to change to use it by just calling getIterator() on an instruction
pointer. A follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
insertBefore, but not before adding concise documentation of what
considerations are needed (very few).

show more ...

[DebugInfo][DivRemPairs] Fix missing debug location updates (#96045)

Fix #96014 .

[DivRemPairs] Do not freeze poisons that can't be undef (#92627)

Per comments in DivRemPairs, the rewrite from
```llvm
%div = div %X, %Y
%rem = rem %X, %Y
```
to
```llvm
%div = di

[DivRemPairs] Do not freeze poisons that can't be undef (#92627)

Per comments in DivRemPairs, the rewrite from
```llvm
%div = div %X, %Y
%rem = rem %X, %Y
```
to
```llvm
%div = div %X, %Y
%.mul = mul %div, %Y
%rem = sub %X, %mul
```
is unsound when %X or %Y are undef.

However, it is known to be sound if %X or %Y are poison but can't be
undef, since both the pre- and post-rewrite %rem are `poison`.

Additionally, proofs: https://alive2.llvm.org/ce/z/xtNQ8j

A comment in the pass listed a TODO for changing a usage of
isGuaranteedNotToBeUndefOrPoison() in the pass to something that only
detects undef. Such a function has been implemented since the time that
TODO was written, but has not been used.

Therefore, this commit updates DivRemPairs to use
isGuaranteedNotToBeUndef() instead.

show more ...

[NFC][RemoveDIs] Insert instruction using iterators in Transforms/

As part of the RemoveDIs project we need LLVM to insert instructions using
iterators wherever possible, so that the iterators can c

[NFC][RemoveDIs] Insert instruction using iterators in Transforms/

As part of the RemoveDIs project we need LLVM to insert instructions using
iterators wherever possible, so that the iterators can carry a bit of
debug-info. This commit implements some of that by updating the contents of
llvm/lib/Transforms/Utils to always use iterator-versions of instruction
constructors.

There are two general flavours of update:
* Almost all call-sites just call getIterator on an instruction
* Several make use of an existing iterator (scenarios where the code is
actually significant for debug-info)
The underlying logic is that any call to getFirstInsertionPt or similar
APIs that identify the start of a block need to have that iterator passed
directly to the insertion function, without being converted to a bare
Instruction pointer along the way.

Noteworthy changes:
* FindInsertedValue now takes an optional iterator rather than an
instruction pointer, as we need to always insert with iterators,
* I've added a few iterator-taking versions of some value-tracking and
DomTree methods -- they just unwrap the iterator. These are purely
convenience methods to avoid extra syntax in some passes.
* A few calls to getNextNode become std::next instead (to keep in the
theme of using iterators for positions),
* SeparateConstOffsetFromGEP has it's insertion-position field changed.
Noteworthy because it's not a purely localised spelling change.

All this should be NFC.

show more ...

Remove several no longer needed includes. NFCI

Mostly removing includes of InitializePasses.h and Pass.h in
passes that no longer has support for the legacy PM.

[DivRemPairs] Remove legacy pass

Following recent changes to remove non-core legacy passes.

[DivRemPairs] Strip division's poison generating flag

Given this transformation: X % Y -> X - (X / Y) * Y

This patch strips off the poison-generating flag of X / Y such as exact, because it may mak

[DivRemPairs] Strip division's poison generating flag

Given this transformation: X % Y -> X - (X / Y) * Y

This patch strips off the poison-generating flag of X / Y such as exact, because it may make the optimized form result poison whereas X % Y does not.

The issue was reported here: https://github.com/llvm/llvm-project/issues/60748

Reviewed By: nikic

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

show more ...

Handle simple diamond CFG hoisting in DivRemPairs.

Previous we only handled triangle CFGs. This patch expands that
to support diamonds, where the div and rem appear in the then/else
sides of a condi

Handle simple diamond CFG hoisting in DivRemPairs.

Previous we only handled triangle CFGs. This patch expands that
to support diamonds, where the div and rem appear in the then/else
sides of a condition. In that case, we can hoist the div into the
shared predecessor.

This could be generalized further to use nearest common ancestors,
but some of the conditions for hoisting would then require
post-dominator information.

Reviewed By: nikic, lebedev.ri

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

show more ...

[Scalar] Teach matchExpandedRem to return std::optional (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-has

[Scalar] Teach matchExpandedRem to return std::optional (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[DivRemPairs] make sure we have a valid CFG for hoisting division

This transform was added with e38b7e894808ec2
and as shown in:
https://llvm.org/PR51241
...it could crash without an extra check of

[DivRemPairs] make sure we have a valid CFG for hoisting division

This transform was added with e38b7e894808ec2
and as shown in:
https://llvm.org/PR51241
...it could crash without an extra check of the blocks.

There might be a more compact way to write this constraint,
but we can't just count the successors/predecessors without
affecting a test that includes a switch instruction.

show more ...

[DivRemPairs] Add an initial case for hoisting to a common predecessor.

This patch adds support for hoisting the division and maybe the
remainder for control flow graphs like this.

```
PredBB
|

[DivRemPairs] Add an initial case for hoisting to a common predecessor.

This patch adds support for hoisting the division and maybe the
remainder for control flow graphs like this.

```
PredBB
| \
| Rem
| /
Div
```

If we have DivRem we'll hoist both to PredBB. If not we'll just
hoist Div and expand Rem using the Div.

This improves our codegen for something like this

```
__uint128_t udivmodti4(__uint128_t dividend, __uint128_t divisor, __uint128_t *remainder) {
if (remainder != 0)
*remainder = dividend % divisor;
return dividend / divisor;
}
```

Reviewed By: spatel, lebedev.ri

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

show more ...

[NewPM] Don't mark AA analyses as preserved

Currently all AA analyses marked as preserved are stateless, not taking
into account their dependent analyses. So there's no need to mark them
as preserve

[NewPM] Don't mark AA analyses as preserved

Currently all AA analyses marked as preserved are stateless, not taking
into account their dependent analyses. So there's no need to mark them
as preserved, they won't be invalidated unless their analyses are.

SCEVAAResults was the one exception to this, it was treated like a
typical analysis result. Make it like the others and don't invalidate
unless SCEV is invalidated.

Reviewed By: asbirlea

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

show more ...

[ValueTracking] Use assume's noundef operand bundle

This patch updates `isGuaranteedNotToBeUndefOrPoison` to use `llvm.assume`'s `noundef` operand bundle.

Reviewed By: jdoerfert

Differential Revis

[ValueTracking] Use assume's noundef operand bundle

This patch updates `isGuaranteedNotToBeUndefOrPoison` to use `llvm.assume`'s `noundef` operand bundle.

Reviewed By: jdoerfert

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

show more ...

[DivRemPairs] Use DenseMapBase::find instead of operator[]. NFC

Correctly report modified status for DivRemPairs

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

[DivRemPairs] Freeze operands if they can be undef values

Summary:
DivRemPairs is unsound with respect to undef values.

```
// bb1:
// %rem = srem %x, %y
// bb2:
// %div

[DivRemPairs] Freeze operands if they can be undef values

Summary:
DivRemPairs is unsound with respect to undef values.

```
// bb1:
// %rem = srem %x, %y
// bb2:
// %div = sdiv %x, %y
// -->
// bb1:
// %div = sdiv %x, %y
// %mul = mul %div, %y
// %rem = sub %x, %mul
```

If X can be undef, X should be frozen first.
For example, let's assume that Y = 1 & X = undef:
```
%div = sdiv undef, 1 // %div = undef
%rem = srem undef, 1 // %rem = 0
=>
%div = sdiv undef, 1 // %div = undef
%mul = mul %div, 1 // %mul = undef
%rem = sub %x, %mul // %rem = undef - undef = undef
```
http://volta.cs.utah.edu:8080/z/m7Xrx5

Same for Y. If X = 1 and Y = (undef | 1), %rem in src is either 1 or 0,
but %rem in tgt can be one of many integer values.

This resolves https://bugs.llvm.org/show_bug.cgi?id=42619 .

This miscompilation disappears if undef value is removed, but it may take a while.
DivRemPair happens pretty late during the optimization pipeline, so this optimization seemed as a good candidate to fix without major regression using freeze than other broken optimizations.

Reviewers: spatel, lebedev.ri, george.burgess.iv

Reviewed By: spatel

Subscribers: wuzish, regehr, nlopes, nemanjai, hiraditya, llvm-commits

Tags: #llvm

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

show more ...

Give helpers internal linkage. NFC.

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

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

show more ...

[DivRemPairs] Don't assert that we won't ever get expanded-form rem pairs in different BB's (PR43500)

If we happen to have the same div in two basic blocks,
and in one of those we also happen to hav

[DivRemPairs] Don't assert that we won't ever get expanded-form rem pairs in different BB's (PR43500)

If we happen to have the same div in two basic blocks,
and in one of those we also happen to have the rem part,
we'd match the div-rem pair, but the wrong ones.
So let's drop overly-ambiguous assert.

Fixes https://bugs.llvm.org/show_bug.cgi?id=43500

llvm-svn: 373167

show more ...

[DivRemPairs] Fixup DNDEBUG build - variable is only used in assertion

llvm-svn: 367423

[DivRemPairs] Recommit: Handling for expanded-form rem - recomposition (PR42673)

Summary:
While `-div-rem-pairs` pass can decompose rem in div+rem pair when div-rem pair
is unsupported by target, no

[DivRemPairs] Recommit: Handling for expanded-form rem - recomposition (PR42673)

Summary:
While `-div-rem-pairs` pass can decompose rem in div+rem pair when div-rem pair
is unsupported by target, nothing performs the opposite fold.
We can't do that in InstCombine or DAGCombine since neither of those has access to TTI.
So it makes most sense to teach `-div-rem-pairs` about it.

If we matched rem in expanded form, we know we will be able to place div-rem pair
next to each other so we won't regress the situation.
Also, we shouldn't decompose rem if we matched already-decomposed form.
This is surprisingly straight-forward otherwise.

The original patch was committed in rL367288 but was reverted in rL367289
because it exposed pre-existing RAUW issues in internal data structures
of the pass; those now have been addressed in a previous patch.

https://bugs.llvm.org/show_bug.cgi?id=42673

Reviewers: spatel, RKSimon, efriedma, ZaMaZaN4iK, bogner

Reviewed By: bogner

Subscribers: bogner, hiraditya, llvm-commits

Tags: #llvm

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

llvm-svn: 367419

show more ...

[DivRemPairs] Avoid RAUW pitfalls (PR42823)

Summary:
`DivRemPairs` internally creates two maps:
* {sign, divident, divisor} -> div instruction
* {sign, divident, divisor} -> rem instruction
Then it

[DivRemPairs] Avoid RAUW pitfalls (PR42823)

Summary:
`DivRemPairs` internally creates two maps:
* {sign, divident, divisor} -> div instruction
* {sign, divident, divisor} -> rem instruction
Then it iterates over rem map, and looks if there is an entry
in div map with the same key. Then depending on some internal logic
it may RAUW rem instruction with something else.

But if that rem instruction is an input to other div/rem,
then it was used as a key in these maps, so the old value (used in key)
is now dandling, because RAUW didn't update those maps.
And we can't even RAUW map keys in general, there's `ValueMap`,
but we don't have a single `Value` as key...

The bug was discovered via D65298, and the test there exists.
Now, i'm not sure how to expose this issue in trunk.
The bug is clearly there if i change the map keys to be `AssertingVH`/`PoisoningVH`,
but i guess this didn't miscompiled anything thus far?
I really don't think this is benin without that patch.

The fix is actually rather straight-forward - instead of trying to somehow
shoe-horn `ValueMap` here (doesn't fit, key isn't just `Value`), or writing a new
`ValueMap` with key being a struct of `Value`s, we can just have an intermediate
data structure - a vector, each entry containing matching `Div, Rem` pair,
and pre-filling it before doing any modifications.
This way we won't need to query map after doing RAUW, so no bug is possible.

Reviewers: spatel, bogner, RKSimon, craig.topper

Reviewed By: spatel

Subscribers: hiraditya, hans, llvm-commits

Tags: #llvm

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

llvm-svn: 367417

show more ...

Revert "[DivRemPairs] Handling for expanded-form rem - recomposition (PR42673)"

test-suite/MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG broke:

Only PHI nodes may reference their own value!
%sub

Revert "[DivRemPairs] Handling for expanded-form rem - recomposition (PR42673)"

test-suite/MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG broke:

Only PHI nodes may reference their own value!
%sub33 = srem i32 %sub33, %ranks_in_i

This reverts commit r367288.

llvm-svn: 367289

show more ...

[DivRemPairs] Handling for expanded-form rem - recomposition (PR42673)

Summary:
While `-div-rem-pairs` pass can decompose rem in div+rem pair when div-rem pair
is unsupported by target, nothing perf

[DivRemPairs] Handling for expanded-form rem - recomposition (PR42673)

Summary:
While `-div-rem-pairs` pass can decompose rem in div+rem pair when div-rem pair
is unsupported by target, nothing performs the opposite fold.
We can't do that in InstCombine or DAGCombine since neither of those has access to TTI.
So it makes most sense to teach `-div-rem-pairs` about it.

If we matched rem in expanded form, we know we will be able to place div-rem pair
next to each other so we won't regress the situation.
Also, we shouldn't decompose rem if we matched already-decomposed form.
This is surprisingly straight-forward otherwise.

https://bugs.llvm.org/show_bug.cgi?id=42673

Reviewers: spatel, RKSimon, efriedma, ZaMaZaN4iK, bogner

Reviewed By: bogner

Subscribers: bogner, hiraditya, llvm-commits

Tags: #llvm

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

llvm-svn: 367288

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...