[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 ...

[Reassociate] Don't reassociate vXi1 logical expressions (#123329)

Extends what we already do for i1 types and don't serialize vXi1 logical expressions to improve ILP.

llvm-test-suite numbers
ht

[Reassociate] Don't reassociate vXi1 logical expressions (#123329)

Extends what we already do for i1 types and don't serialize vXi1 logical expressions to improve ILP.

llvm-test-suite numbers
https://github.com/llvm/llvm-project/issues/64840#issuecomment-2053621740
indicate that both reassociations are a net win.

Fixes #64840
Fixes #63946

show more ...

[DebugInfo][Reassociate] Preserve DebugLocs when reassociating subs (#114226)

In NegateValue in Reassociate, we return the negation of an existing
value in order to break a subtract into an negate

[DebugInfo][Reassociate] Preserve DebugLocs when reassociating subs (#114226)

In NegateValue in Reassociate, we return the negation of an existing
value in order to break a subtract into an negate + add, potentially
creating a new instruction to perform the negation, but we neglect to
propagate the DebugLoc of the sub being replaced to the negate
instruction if one is created. This patch adds that propagation.

Found using https://github.com/llvm/llvm-project/pull/107279.

show more ...

[Transforms] Use range-based for loops (NFC) (#98725)

[Transforms] Use range-based for loops (NFC) (#98465)

[Reassociate] Preserve `nuw` and `nsw` on `mul` chains

Basically the same rules as `add` but we also need to ensure all
operands a non-zero.

Proofs: https://alive2.llvm.org/ce/z/jzsYht

Closes #970

[Reassociate] Preserve `nuw` and `nsw` on `mul` chains

Basically the same rules as `add` but we also need to ensure all
operands a non-zero.

Proofs: https://alive2.llvm.org/ce/z/jzsYht

Closes #97040

show more ...

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[Reassociate] Use poison instead of undef for dummy operands (NFCI)

These will be replaced later.

[Reassociate] Avoid use of ConstantExpr::getShl()

Use the constant folding API instead.

[DebugInfo][Reassociate] Fix missing debug location drop (#95355)

Fix #95343 .

[llvm] Use llvm::unique (NFC) (#95628)

[Reassociate] Use uint64_t for repeat count (#94232)

This patch relands #91469 and uses `uint64_t` for repeat count to avoid
a miscompilation caused by overflow
https://github.com/llvm/llvm-projec

[Reassociate] Use uint64_t for repeat count (#94232)

This patch relands #91469 and uses `uint64_t` for repeat count to avoid
a miscompilation caused by overflow
https://github.com/llvm/llvm-project/pull/91469#discussion_r1623925158.

show more ...

Revert "[Reassociate] Drop weight reduction to fix issue 91417 (#91469)" (#94210)

Reverts
https://github.com/llvm/llvm-project/commit/3bcccb6af685c3132a9ee578b9e11b2503c35a5c
and
https://github.c

Revert "[Reassociate] Drop weight reduction to fix issue 91417 (#91469)" (#94210)

Reverts
https://github.com/llvm/llvm-project/commit/3bcccb6af685c3132a9ee578b9e11b2503c35a5c
and
https://github.com/llvm/llvm-project/commit/9a282724a29899e84adc91bdeaf639010408a80d
because #91469 causes a miscompilation
https://github.com/llvm/llvm-project/pull/91469#discussion_r1623925158.

show more ...

[Reassociate] Drop weight reduction to fix issue 91417 (#91469)

See the following case: https://alive2.llvm.org/ce/z/A-fBki
```
define i3 @src(i3 %0) {
%2 = mul i3 %0, %0
%3 = mul i3 %2, %0

[Reassociate] Drop weight reduction to fix issue 91417 (#91469)

See the following case: https://alive2.llvm.org/ce/z/A-fBki
```
define i3 @src(i3 %0) {
%2 = mul i3 %0, %0
%3 = mul i3 %2, %0
%4 = mul i3 %3, %0
%5 = mul nsw i3 %4, %0
ret i3 %5
}

define i3 @tgt(i3 %0) {
%2 = mul i3 %0, %0
%5 = mul nsw i3 %2, %0
ret i3 %5
}
```


https://github.com/llvm/llvm-project/commit/d7aeefebd6b049f017711cd7c6ef5f217a17b673
introduced weight reduction during weights combination of the same
operand. As the weight of `%0` changes from 5 to 3, the nsw flag in `%5`
should be dropped.

However, the nsw flag isn't cleared by `RewriteExprTree` since `%5 = mul
nsw i3 %0, %4` is not included in the range of `[ExpressionChangedStart,
ExpressionChangedEnd)`.
```
Calculated Rank[] = 3
Combine negations for: %2 = mul i3 %0, %0
Calculated Rank[] = 4
Combine negations for: %3 = mul i3 %0, %2
Calculated Rank[] = 5
Combine negations for: %4 = mul i3 %0, %3
Calculated Rank[] = 6
Combine negations for: %5 = mul nsw i3 %0, %4
LINEARIZE: %5 = mul nsw i3 %0, %4
OPERAND: i3 %0 (1)
ADD USES LEAF: i3 %0 (1)
OPERAND: %4 = mul i3 %0, %3 (1)
DIRECT ADD: %4 = mul i3 %0, %3 (1)
OPERAND: i3 %0 (1)
OPERAND: %3 = mul i3 %0, %2 (1)
DIRECT ADD: %3 = mul i3 %0, %2 (1)
OPERAND: i3 %0 (1)
OPERAND: %2 = mul i3 %0, %0 (1)
DIRECT ADD: %2 = mul i3 %0, %0 (1)
OPERAND: i3 %0 (1)
OPERAND: i3 %0 (1)
RAIn: mul i3 [ %0, #3] [ %0, #3] [ %0, #3]
RAOut: mul i3 [ %0, #3] [ %0, #3] [ %0, #3]
RAOut after CSE reorder: mul i3 [ %0, #3] [ %0, #3] [ %0, #3]
RA: %5 = mul nsw i3 %0, %4
TO: %5 = mul nsw i3 %4, %0
RA: %4 = mul i3 %0, %3
TO: %4 = mul i3 %0, %0
```

The best way to fix this is to inform `RewriteExprTree` to clear flags
of the whole expr tree when weight reduction happens.

But I find that weight reduction based on Carmichael number never
happens in practice.
See the coverage result
https://dtcxzyw.github.io/llvm-opt-benchmark/coverage/home/dtcxzyw/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp.html#L323

I think it would be better to drop `IncorporateWeight`.

Fixes #91417

show more ...

[Reassociate] Preserve NSW flags after expr tree rewriting (#93105)

We can guarantee NSW on all operands in a reassociated add expression
tree when:

- All adds in an add operator tree are NSW, A

[Reassociate] Preserve NSW flags after expr tree rewriting (#93105)

We can guarantee NSW on all operands in a reassociated add expression
tree when:

- All adds in an add operator tree are NSW, AND either
- All add operands are guaranteed to be nonnegative, OR
- All adds are also NUW

- Alive2:
- Nonnegative Operands
- 3 operands: https://alive2.llvm.org/ce/z/G4XW6Q
- 4 operands: https://alive2.llvm.org/ce/z/FWcZ6D
- NUW NSW adds: https://alive2.llvm.org/ce/z/vRUxeC

---------

Co-authored-by: Nikita Popov <github@npopov.com>

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 ...

[NFC][RemoveDIs] Have CreateNeg only accept iterators (#82999)

Removing debug-intrinsics requires that we always insert with an
iterator, not with an instruction position. To enforce that, we need

[NFC][RemoveDIs] Have CreateNeg only accept iterators (#82999)

Removing debug-intrinsics requires that we always insert with an
iterator, not with an instruction position. To enforce that, we need to
eliminate the `Instruction *` taking functions. It's safe to leave the
insert-at-end-of-block functions as the intention is clear for debug
info purposes (i.e., insert after both instructions and debug-info at
the end of the function).

This patch demonstrates how that needs to happen. At a variety of
call-sites to the `CreateNeg` constructor we need to consider:
* Has this instruction been selected because of the operation it
performs? In that case, just call `getIterator` and pass an iterator in.
* Has this instruction been selected because of it's position? If so, we
need to keep the iterator identifying that position (see the 3rd hunk
changing Reassociate.cpp, although it's coincidentally not debug-info
significant).

This also demonstrates what we'll try and do with the constructor
methods going forwards: have one fully explicit set of parameters
including iterator, and another with default-arguments where the
block-to-insert-into argument defaults to nullptr / no-position,
creating an instruction that hasn't been inserted yet.

show more ...

[Reassociate] Preserve NUW flags after expr tree rewriting (#72360)

Alive2: https://alive2.llvm.org/ce/z/38KiC_

Recommit "[Reassociate] Use disjoint flag to convert Or to Add. (#72772)"

Original message:
We still have to keep the noCommonBitsSet call to handle multiple reassociations in one pass. We'll lose t

Recommit "[Reassociate] Use disjoint flag to convert Or to Add. (#72772)"

Original message:
We still have to keep the noCommonBitsSet call to handle multiple reassociations in one pass. We'll lose the flag on the first reassociation.

show more ...

Revert "[Reassociate] Use disjoint flag to convert Or to Add. (#72772)"

This reverts commit 78964457cf1bafe57a54629fafbd081452a9e528.

Looks like I didn't rebase this correctly before commit

[Reassociate] Use disjoint flag to convert Or to Add. (#72772)

We still have to keep the noCommonBitsSet call to handle multiple reassociations in one pass. We'll lose the flag on the first reassoci

[Reassociate] Use disjoint flag to convert Or to Add. (#72772)

We still have to keep the noCommonBitsSet call to handle multiple reassociations in one pass. We'll lose the flag on the first reassociation.

show more ...

[IR][TRE] Support associative intrinsics (#74226)

There is support for intrinsics in Instruction::isCommunative, but there
is no equivalent implementation for isAssociative. This patch builds
supp

[IR][TRE] Support associative intrinsics (#74226)

There is support for intrinsics in Instruction::isCommunative, but there
is no equivalent implementation for isAssociative. This patch builds
support for associative intrinsics with TRE as an application. TRE can
now have associative intrinsics as an accumulator. For example:
```
struct Node {
Node *next;
unsigned val;
}

unsigned maxval(struct Node *n) {
if (!n) return 0;
return std::max(n->val, maxval(n->next));
}
```
Can be transformed into:
```
unsigned maxval(struct Node *n) {
struct Node *head = n;
unsigned max = 0; // Identity of unsigned std::max
while (true) {
if (!head) return max;
max = std::max(max, head->val);
head = head->next;
}
return max;
}
```
This example results in about 5x speedup in local runs.

We conservatively only consider min/max and as associative for this
patch to limit testing scope. There are probably other intrinsics that
could be considered associative. There are a few consumers of
isAssociative() that could be impacted. Testing has only required to
Reassociate pass be updated.

show more ...

[DebugInfo][RemoveDIs] Have getInsertionPtAfterDef return an iterator (#73149)

Part of the "RemoveDIs" project to remove debug intrinsics requires
passing block-positions around in iterators rather

[DebugInfo][RemoveDIs] Have getInsertionPtAfterDef return an iterator (#73149)

Part of the "RemoveDIs" project to remove debug intrinsics requires
passing block-positions around in iterators rather than as instruction
pointers, allowing some debug-info to reside in BasicBlock::iterator.
This means getInsertionPointAfterDef has to return an iterator, and as
it can return no-instruction that means returning an optional iterator.

This patch changes the signature for getInsertionPtAfterDef and then
patches up the various places that use it to handle the different type.
This would overall be an NFC patch, however in
InstCombinerImpl::freezeOtherUses I've started skipping any debug
intrinsics at the returned insert-position. This should not have any
_meaningful_ effect on the compiler output: at worst it means variable
assignments that are skipped will now cover the freeze instruction and
anything inserted before it, which should be inconsequential.

Sadly: this makes the function signature ugly. This is probably the
ugliest piece of fallout for the "RemoveDIs" work, but it serves the
overall purpose of improving compile times and not allowing `-g` to
affect compiler output, so should be worthwhile in the end.

show more ...

[ValueTracking] Use SimplifyQuery in haveNoCommonBitsSet() (NFC)

Pass SimplifyQuery instead of unpacked list of arguments.

[Reassociate] Keep flags for more unchanged operations

Reassociation destroys nsw/nuw flags from BinOps that are changed. But if the
expression at the end of a tree that was altered, but didn't chan

[Reassociate] Keep flags for more unchanged operations

Reassociation destroys nsw/nuw flags from BinOps that are changed. But if the
expression at the end of a tree that was altered, but didn't change itself,
the flags do not need to be removed. For example, if %a, %b and %c are
reassociated in
%x = add nsw i32 %a, %c
%y = add nsw i32 %x, %b
%z = add nsw i32 %y, %d
The value of %y and so add %y %d remains the same, and %z needn't drop the nsw
flags.
https://alive2.llvm.org/ce/z/_juAiV

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

show more ...