PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key p

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key pieces of infrastructure that must be updated to match a CmpInst
respecting samesign information. Implement this change to Cmp-matchers.

This is a preparatory step in migrating the codebase over to
CmpPredicate. Since we no functional changes are desired at this stage,
we have chosen not to migrate CmpPredicate::operator==(CmpPredicate)
calls to use CmpPredicate::getMatching(), as that would have visible
impact on tests that are not yet written: instead, we call
CmpPredicate::operator==(Predicate), preserving the old behavior, while
also inserting a few FIXME comments for follow-ups.

show more ...

[Transforms] Avoid repeated hash lookups (NFC) (#112654)

[LoopPeel] Fix LCSSA phi node invalidation

In the test case, the BECount of the second loop uses %load,
but we only have an LCSSA phi node for %add, so that is what
gets invalidated. Use the forgetL

[LoopPeel] Fix LCSSA phi node invalidation

In the test case, the BECount of the second loop uses %load,
but we only have an LCSSA phi node for %add, so that is what
gets invalidated. Use the forgetLcssaPhiWithNewPredecessor()
API instead, which will invalidate the roots of the expression
instead.

Fixes https://github.com/llvm/llvm-project/issues/109333.

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

Reapply "[llvm][IR] Extend BranchWeightMetadata to track provenance o… (#95281)

…f weights" #95136

Reverts #95060, and relands #86609, with the unintended code generation
changes addressed.

T

Reapply "[llvm][IR] Extend BranchWeightMetadata to track provenance o… (#95281)

…f weights" #95136

Reverts #95060, and relands #86609, with the unintended code generation
changes addressed.

This patch implements the changes to LLVM IR discussed in
https://discourse.llvm.org/t/rfc-update-branch-weights-metadata-to-allow-tracking-branch-weight-origins/75032

In this patch, we add an optional field to MD_prof meatdata nodes for
branch weights, which can be used to distinguish weights added from
llvm.expect* intrinsics from those added via other methods, e.g. from
profiles or inserted by the compiler.

One of the major motivations, is for use with MisExpect diagnostics,
which need to know if branch_weight metadata originates from an
llvm.expect intrinsic. Without that information, we end up checking
branch weights multiple times in the case if ThinLTO + SampleProfiling,
leading to some inaccuracy in how we report MisExpect related
diagnostics to users.

Since we change the format of MD_prof metadata in a fundamental way, we
need to update code handling branch weights in a number of places.

We also update the lang ref for branch weights to reflect the change.

show more ...

Revert "[llvm][IR] Extend BranchWeightMetadata to track provenance of weights" (#95060)

Reverts llvm/llvm-project#86609

This change causes compile-time regressions for stage2 builds
(https://llv

Revert "[llvm][IR] Extend BranchWeightMetadata to track provenance of weights" (#95060)

Reverts llvm/llvm-project#86609

This change causes compile-time regressions for stage2 builds
(https://llvm-compile-time-tracker.com/compare.php?from=3254f31a66263ea9647c9547f1531c3123444fcd&to=c5978f1eb5eeca8610b9dfce1fcbf1f473911cd8&stat=instructions:u).
It also introduced unintended changes to `.text` which should be
addressed before relanding.

show more ...

[llvm][IR] Extend BranchWeightMetadata to track provenance of weights (#86609)

This patch implements the changes to LLVM IR discussed in

https://discourse.llvm.org/t/rfc-update-branch-weights-met

[llvm][IR] Extend BranchWeightMetadata to track provenance of weights (#86609)

This patch implements the changes to LLVM IR discussed in

https://discourse.llvm.org/t/rfc-update-branch-weights-metadata-to-allow-tracking-branch-weight-origins/75032

In this patch, we add an optional field to MD_prof metadata nodes for
branch weights, which can be used to distinguish weights added from
`llvm.expect*` intrinsics from those added via other methods, e.g.
from profiles or inserted by the compiler.

One of the major motivations, is for use with MisExpect diagnostics,
which need to know if branch_weight metadata originates from an
llvm.expect intrinsic. Without that information, we end up checking
branch weights multiple times in the case if ThinLTO + SampleProfiling,
leading to some inaccuracy in how we report MisExpect related
diagnostics to users.

Since we change the format of MD_prof metadata in a fundamental way, we
need to update code handling branch weights in a number of places.

We also update the lang ref for branch weights to reflect the change.

show more ...

[LoopPeel] Support min/max intrinsics in loop peeling (#93162)

This patch adds processing of min/max intrinsics in LoopPeel in the
similar way as it was done for conditional statements: for
min/ma

[LoopPeel] Support min/max intrinsics in loop peeling (#93162)

This patch adds processing of min/max intrinsics in LoopPeel in the
similar way as it was done for conditional statements: for
min/max(IterVal, BoundVal) we peel iterations where IterVal < BoundVal
for monotonically increasing IterVal; for monotonically decreasing
IterVal we peel iterations where IterVal > BoundVal (strict comparision
predicates are used to minimize number of peeled iterations).

show more ...

[LoopPeel] Peel iterations based on and, or conditions (#73413)

For example, this allows us to peel this loop with a `and`:
```
for (int i = 0; i < N; ++i) {
if (i % 2 == 0 && i < 3) // can pee

[LoopPeel] Peel iterations based on and, or conditions (#73413)

For example, this allows us to peel this loop with a `and`:
```
for (int i = 0; i < N; ++i) {
if (i % 2 == 0 && i < 3) // can peel based on || as well
f1();
f2();
```
into:
```
for (int i = 0; i < 3; ++i) { // peel three iterations
if (i % 2 == 0)
f1();
f2();
}
for (int i = 3; i < N; ++i)
f2();
```

show more ...

Add setBranchWeigths convenience function. NFC (#72446)

Add `setBranchWeights` convenience function to ProfDataUtils.h and use
it where appropriate.

[LoopPeeling] Fix weights updating of peeled off branches (#70094)

In https://reviews.llvm.org/D64235 a new algorithm has been introduced
for updating the branch weights of latch blocks and their c

[LoopPeeling] Fix weights updating of peeled off branches (#70094)

In https://reviews.llvm.org/D64235 a new algorithm has been introduced
for updating the branch weights of latch blocks and their copies.

It increases the probability of going to the exit block for each next
peel iteration, calculating weights by (F - I * E, E), where:
- F is a weight of the edge from latch to header.
- E is a weight of the edge from latch to exit.
- I is a number of peeling iteration.

E.g: Let's say the latch branch weights are (100,300) and the estimated
trip count is 4. If we peel off all 4 iterations the weights of the
copied branches will be:
0: (100,300)
1: (100,200)
2: (100,100)
3: (100,1)

https://godbolt.org/z/93KnoEsT6

So we make the original loop almost unreachable from the 3rd peeled copy
according to the profile data. But that's only true if the profiling
data is accurate.
Underestimated trip count can lead to a performance issues with the
register allocator, which may decide to spill intervals inside the loop
assuming it's unreachable.

Since we don't know how accurate the profiling data is, it seems better
to set neutral 1/1 weights on the last peeled latch branch. After this
change, the weights in the example above will look like this:
0: (100,300)
1: (100,200)
2: (100,100)
3: (100,100)

Co-authored-by: Aleksandr Popov <apopov@azul.com>

show more ...

[llvm] Fix duplicate word typos. NFC

Those fixes were taken from https://reviews.llvm.org/D137338

[LoopPeel] Clear dispositions after peeling

Block dispositions of values defined inside the loop may change
during peeling, so clear them. We already do this for other kinds
of unrolling.

Different

[LoopPeel] Clear dispositions after peeling

Block dispositions of values defined inside the loop may change
during peeling, so clear them. We already do this for other kinds
of unrolling.

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

show more ...

[LoopUnroll] Peel iterations based on select conditions

This also allows us to peel loops with a `select`:
```
for (int i = 0; i <= N; ++i);
f3(i == 0 ? a : b); // select instruction
```
into:
```

[LoopUnroll] Peel iterations based on select conditions

This also allows us to peel loops with a `select`:
```
for (int i = 0; i <= N; ++i);
f3(i == 0 ? a : b); // select instruction
```
into:
```
f3(a); // peel one iteration
for (int i = 1; i <= N; ++i)
f3(b);
```

Reviewed By: nikic

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

show more ...

[LoopPeel] Expose ValueMap of last peeled iteration. NFC

The value map of last peeled iteration is computed within peelLoop API.
This patch exposes it for callers of peelLoop.
While this is not curr

[LoopPeel] Expose ValueMap of last peeled iteration. NFC

The value map of last peeled iteration is computed within peelLoop API.
This patch exposes it for callers of peelLoop.
While this is not currently used by upstream passes, we have a usecase
downstream which benefits from this API update. Future users of peelLoop
can also use the ValueMap if needed.

Similar value maps are exposed by other loop utilities such as loop
cloning.

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

show more ...

Don't include Optional.h

These files no longer use llvm::Optional.

[NFC] Cleanup: Replace Function::getBasicBlockList().splice() with Function::splice()

This is part of a series of patches that aim at making Function::getBasicBlockList() private.

Differential Revi

[NFC] Cleanup: Replace Function::getBasicBlockList().splice() with Function::splice()

This is part of a series of patches that aim at making Function::getBasicBlockList() private.

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

show more ...

Transforms/Utils: llvm::Optional => std::optional

Expand loop peeling phi computation to handle binary ops and casts

Summary:
Expand the capabilities of the code for computing how many peels are
needed to make phis determined. A cast gets the peel

Expand loop peeling phi computation to handle binary ops and casts

Summary:
Expand the capabilities of the code for computing how many peels are
needed to make phis determined. A cast gets the peel count for the
value being casted while a binary op gets the maximum of the operands.

Respond to review comments: remove redundant asserts.

Author: Jamie Schmeiser <schmeise@ca.ibm.com>
Reviewed By:mkazantsev (Max Kazantsev),syzaara (Zaara Syeda)
Differential Revision: https://reviews.llvm.org/D138719

show more ...

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

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

[Utils] Use std::optional in LoopPeel.cpp (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

[Utils] Use std::optional in LoopPeel.cpp (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 ...

[NFC] Refactor loop peeling code for calculating phi invariance.

Summary:
Refactor loop peeling code by moving code for calculating phi invariance
into a separate class that does the calculation. R

[NFC] Refactor loop peeling code for calculating phi invariance.

Summary:
Refactor loop peeling code by moving code for calculating phi invariance
into a separate class that does the calculation. Redescribe and rework
the algorithm in preparation for adding increased functionality. Add
test case that does not exhibit peeling that will be subsequently supported.

Author: Jamie Schmeiser <schmeise@ca.ibm.com>
Reviewed By: mkazantsev (Max Kazantsev)
Differential Revision: https://reviews.llvm.org/D138232

show more ...

[NFC] Replaced BB->getInstList().{erase(),pop_front(),pop_back()} with eraseFromParent().

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

[LoopPeeling] Add flag to disable support for peeling loops with non-latch exits

Add a flag to allow disabling the changes in
https://reviews.llvm.org/D134803.

Differential Revision: https://review

[LoopPeeling] Add flag to disable support for peeling loops with non-latch exits

Add a flag to allow disabling the changes in
https://reviews.llvm.org/D134803.

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

show more ...

[LoopPeeling] Support peeling loops with non-latch exits

Loop peeling currently requires that a) the latch is exiting
b) a branch and c) other exits are unreachable/deopt. This patch
removes all of

[LoopPeeling] Support peeling loops with non-latch exits

Loop peeling currently requires that a) the latch is exiting
b) a branch and c) other exits are unreachable/deopt. This patch
removes all of these limitations, and adds the necessary branch
weight updating support. It essentially works the same way as
before with latch -> exiting terminator and
loop trip count -> per exit trip count.

It's worth noting that there are still other limitations in
profitability heuristics: This patch enables peeling of loops to
make conditions invariant (which is pretty much always highly
profitable if possible), while peeling to make loads dereferenceable
still checks that non-latch exits are unreachable and PGO-based
peeling has even more conditions. Those checks could be relaxed
later if we consider those cases profitable.

The motivation for this change is that loops using iterator adaptors
in Rust often optimize very badly, and end up with a loop phi of the
form phi(true, false) in the final result. Peeling eliminates that
phi and conditions based on it, which enables a lot of follow-on
simplification.

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

show more ...