[SCEVExpander] Remove unnecessary mul/udiv check (NFC)

Pointer-typed SCEV expressions can no longer be mul or udiv, so
we do not need to specially handle them here.

[SCEVExpander] Assert single pointer op in add (NFC)

There can only be one pointer operand in an add expression, and
we have sorted operands to guarantee that it is the first. As
such, the pointer c

[SCEVExpander] Assert single pointer op in add (NFC)

There can only be one pointer operand in an add expression, and
we have sorted operands to guarantee that it is the first. As
such, the pointer check for other operands is dead code.

show more ...

[SCEVExpander] Stop hoisting IR when reusing phis

his is a fix for PR43678, and is an alternate patch to D105723.

The basic issue we're running into is that LSR + SCEVExpander are moving the very i

[SCEVExpander] Stop hoisting IR when reusing phis

his is a fix for PR43678, and is an alternate patch to D105723.

The basic issue we're running into is that LSR + SCEVExpander are moving the very instruction whose operand we're in the process of expanding. This breaks the subtle and ill-documented invariant which let LSR work. (Full story can be found here: https://reviews.llvm.org/D105723#2878473)

Rather than attempting a fix, this change just removes the optimization entirely. The code is entirely untested, and removing it appears to have no impact I can find. This code was added back in 2014 by 1e12f8563d4b7 with a single test which does not seem to actually test the hoisting logic.

From a philosophical standpoint, it also seems very strange to have the expander implementing optimizations which should live in a dedicated transform pass.

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

show more ...

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

Reapply commit d675b594f4f1e1f6a195fb9a4fd02cf3de92292d that was
reverted due to buildbot failures. A simple fix has been applied to
r

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

Reapply commit d675b594f4f1e1f6a195fb9a4fd02cf3de92292d that was
reverted due to buildbot failures. A simple fix has been applied to
remove an assertion.

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

show more ...

Revert "[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR"
Reverted due to buildbot failures.
This reverts commit d675b594f4f1e1f6a195fb9a4fd02cf3de92292d.

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

Reapply commit 796b84d26f4d461fb50e7b4e84e15a10eaca88fc that was
reverted due to reports of crashes. A minor change now guards against

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

Reapply commit 796b84d26f4d461fb50e7b4e84e15a10eaca88fc that was
reverted due to reports of crashes. A minor change now guards against
getVariableLocationOperand() returning a nullptr.

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

show more ...

Revert "[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR"

Crashes were reported on the upstreamm revision:
https://reviews.llvm.org/D105207

This reverts commit 796b84d26f4d461fb50e7b

Revert "[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR"

Crashes were reported on the upstreamm revision:
https://reviews.llvm.org/D105207

This reverts commit 796b84d26f4d461fb50e7b4e84e15a10eaca88fc.

show more ...

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

This reapplies commit 76f3ffb2b285998f02639db8fd42fb0de8a540d0 that was
reverted due to buildbot failures.

- Update lit tests with RE

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

This reapplies commit 76f3ffb2b285998f02639db8fd42fb0de8a540d0 that was
reverted due to buildbot failures.

- Update lit tests with REQUIRES condition.
- Abandon salvage attempt if SCEVUnknown::getValue() returns nullptr.

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

show more ...

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

This reverts commit 76f3ffb2b285998f02639db8fd42fb0de8a540d0 because
of a failure on sanitixer-X86-64-linux-autoconf.

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

This patch extends salvaging of debuginfo in the Loop Strength Reduction
(LSR) pass by translating Scalar Evaluations (SCEV) into DIEx

[DebugInfo][LoopStrengthReduction] SCEV-based salvaging for LSR

This patch extends salvaging of debuginfo in the Loop Strength Reduction
(LSR) pass by translating Scalar Evaluations (SCEV) into DIExpressions.
The method is as follows:
- Cache dbg.value intrinsics that are salvageable.
- Obtain a loop Induction Variable (IV) from ScalarExpressionExpander or
the loop header.
- Translate the IV SCEV into an expression that recovers the current
loop iteration count. Combine this with the dbg.value's location
op SCEV to create a DIExpression that salvages the value.

Review by: jmorse

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

show more ...

[ScalarEvolution] Strictly enforce pointer/int type rules.

Rules:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a
pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other S

[ScalarEvolution] Strictly enforce pointer/int type rules.

Rules:

1. SCEVUnknown is a pointer if and only if the LLVM IR value is a
pointer.
2. SCEVPtrToInt is never a pointer.
3. If any other SCEV expression has no pointer operands, the result is
an integer.
4. If a SCEVAddExpr has exactly one pointer operand, the result is a
pointer.
5. If a SCEVAddRecExpr's first operand is a pointer, and it has no other
pointer operands, the result is a pointer.
6. If every operand of a SCEVMinMaxExpr is a pointer, the result is a
pointer.
7. Otherwise, the SCEV expression is invalid.

I'm not sure how useful rule 6 is in practice. If we exclude it, we can
guarantee that ScalarEvolution::getPointerBase always returns a
SCEVUnknown, which might be a helpful property. Anyway, I'll leave that
for a followup.

This is basically mop-up at this point; all the changes with significant
functional effects have landed. Some of the remaining changes could be
split off, but I don't see much point.

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

show more ...

[SCEVExpander] Support opaque pointers

This adds support for opaque pointers to expandAddToGEP() by always
generating an i8 GEP for opaque pointers. After looking at some other
cases (constexpr GEP

[SCEVExpander] Support opaque pointers

This adds support for opaque pointers to expandAddToGEP() by always
generating an i8 GEP for opaque pointers. After looking at some other
cases (constexpr GEP folding, SROA GEP generation), I've come around
to the idea that we should use i8 GEPs for opaque pointers, because
the alternative would be to guess a GEP type from surrounding code,
which will not be reliable. Ultimately, i8 GEPs is where we want to
end up anyway, and opaque pointers just make that the natural choice.

There are a couple of other places in SCEVExpander that check pointer
element types, I plan to update those when I run across usable test
coverage that doesn't assert elsewhere.

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

show more ...

ABI breaking changes fixes.

This commit mostly just replaces bad uses of `NDEBUG` with uses of
`LLVM_ENABLE_ABI_BREAKING_CHANGES` - the safe way to include ABI
breaking changes (normally extra struc

ABI breaking changes fixes.

This commit mostly just replaces bad uses of `NDEBUG` with uses of
`LLVM_ENABLE_ABI_BREAKING_CHANGES` - the safe way to include ABI
breaking changes (normally extra struct elements in headers).

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

show more ...

[NFC][OpaquePtr] Explicitly pass GEP source type to IRBuilder in more places

[NFC] ScalarEvolution: apply SSO to the ExprValueMap value

ExprValueMap is a map from SCEV * to a set-vector of (Value *, ConstantInt *) pair,
and while the map itself will likely be big-ish (have m

[NFC] ScalarEvolution: apply SSO to the ExprValueMap value

ExprValueMap is a map from SCEV * to a set-vector of (Value *, ConstantInt *) pair,
and while the map itself will likely be big-ish (have many keys),
it is a reasonable assumption that each key will refer to a small-ish
number of pairs.

In particular looking at n=512 case from
https://bugs.llvm.org/show_bug.cgi?id=50384,
the small-size of 4 appears to be the sweet spot,
it results in the least allocations while minimizing memory footprint.
```
$ for i in $(ls heaptrack.opt.*.gz); do echo $i; heaptrack_print $i | tail -n 6; echo ""; done
heaptrack.opt.0-orig.gz
total runtime: 14.32s.
calls to allocation functions: 8222442 (574192/s)
temporary memory allocations: 2419000 (168924/s)
peak heap memory consumption: 190.98MB
peak RSS (including heaptrack overhead): 239.65MB
total memory leaked: 67.58KB

heaptrack.opt.1-n1.gz
total runtime: 13.72s.
calls to allocation functions: 7184188 (523705/s)
temporary memory allocations: 2419017 (176338/s)
peak heap memory consumption: 191.38MB
peak RSS (including heaptrack overhead): 239.64MB
total memory leaked: 67.58KB

heaptrack.opt.2-n2.gz
total runtime: 12.24s.
calls to allocation functions: 6146827 (502355/s)
temporary memory allocations: 2418997 (197695/s)
peak heap memory consumption: 163.31MB
peak RSS (including heaptrack overhead): 211.01MB
total memory leaked: 67.58KB

heaptrack.opt.3-n4.gz
total runtime: 12.28s.
calls to allocation functions: 6068532 (494260/s)
temporary memory allocations: 2418985 (197017/s)
peak heap memory consumption: 155.43MB
peak RSS (including heaptrack overhead): 201.77MB
total memory leaked: 67.58KB

heaptrack.opt.4-n8.gz
total runtime: 12.06s.
calls to allocation functions: 6068042 (503321/s)
temporary memory allocations: 2418992 (200646/s)
peak heap memory consumption: 166.03MB
peak RSS (including heaptrack overhead): 213.55MB
total memory leaked: 67.58KB

heaptrack.opt.5-n16.gz
total runtime: 12.14s.
calls to allocation functions: 6067993 (499958/s)
temporary memory allocations: 2418999 (199307/s)
peak heap memory consumption: 187.24MB
peak RSS (including heaptrack overhead): 233.69MB
total memory leaked: 67.58KB
```

While that test may be an edge worst-case scenario,
https://llvm-compile-time-tracker.com/compare.php?from=dee85d47d9f15fc268f7b18f279dac2774836615&to=98a57e31b1947d5bcdf4a5605ac2ab32b4bd5f63&stat=instructions
agrees that this also results in improvements in the usual situations.

show more ...

[SCEVExpander] ReuseOrCreateCast(): use IRBuilder to actually create the cast

In particular, this allows to create constant expressions
instead of IR Instruction's if the argumen is a constant.

[SCEVExpander] Expand explicit PtrToInt casts just like we would implicit ones

I.e., use GetOptimalInsertionPointForCastOf() helper to get the insertion
point, and try to reuse casts first.

[SCEVExpander] GetOptimalInsertionPointForCastOf(): gracefully handle Constant's

I guess this case hasn't come up thus far, and i'm not sure if it can
really happen for the existing usages, thus no

[SCEVExpander] GetOptimalInsertionPointForCastOf(): gracefully handle Constant's

I guess this case hasn't come up thus far, and i'm not sure if it can
really happen for the existing usages, thus no test in *this* commit.

But, the following commit adds test coverage,
there we'd expirience a crash without this fix.

show more ...

[NFCI][SCEVExpander] Extract GetOptimalInsertionPointForCastOf() helper

[SCEVExpander] generateOverflowCheck(): explicitly PtrToInt the Start

Currently, InsertNoopCastOfTo() would implicitly insert that cast,
but now that we have SCEVPtrToIntExpr, i'm hoping we could st

[SCEVExpander] generateOverflowCheck(): explicitly PtrToInt the Start

Currently, InsertNoopCastOfTo() would implicitly insert that cast,
but now that we have SCEVPtrToIntExpr, i'm hoping we could stop
InsertNoopCastOfTo() from doing that. But first all users must be fixed.

show more ...

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This

[NFCI] SCEVExpander: emit intrinsics for integral {u,s}{min,max} SCEV expressions

These intrinsics, not the icmp+select are the canonical form nowadays,
so we might as well directly emit them.

This should not cause any regressions, but if it does,
then then they would needed to be fixed regardless.

Note that this doesn't deal with `SCEVExpander::isHighCostExpansion()`,
but that is a pessimization, not a correctness issue.

Additionally, the non-intrinsic form has issues with undef,
see https://reviews.llvm.org/D88287#2587863

show more ...

[LV] Generate RT checks up-front and remove them if required.

This patch updates LV to generate the runtime checks just after cost
modeling, to allow a more precise estimate of the actual cost of th

[LV] Generate RT checks up-front and remove them if required.

This patch updates LV to generate the runtime checks just after cost
modeling, to allow a more precise estimate of the actual cost of the
checks. This information will be used in future patches to generate
larger runtime checks in cases where the checks only make up a small
fraction of the expected scalar loop execution time.

The runtime checks are created up-front in a temporary block to allow better
estimating the cost and un-linked from the existing IR. After deciding to
vectorize, the checks are moved backed. If deciding not to vectorize, the
temporary block is completely removed.

This patch is similar in spirit to D71053, but explores a different
direction: instead of delaying the decision on whether to vectorize in
the presence of runtime checks it instead optimistically creates the
runtime checks early and discards them later if decided to not
vectorize. This has the advantage that the cost-modeling decisions
can be kept together and can be done up-front and thus preserving the
general code structure. I think delaying (part) of the decision to
vectorize would also make the VPlan migration a bit harder.

One potential drawback of this patch is that we speculatively
generate IR which we might have to clean up later. However it seems like
the code required to do so is quite manageable.

Reviewed By: lebedev.ri, ebrevnov

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

show more ...

[Transforms/Utils] Use range-based for loops (NFC)

[SCEVExpander] Migrate costAndCollectOperands to use InstructionCost.

This patch changes costAndCollectOperands to use InstructionCost for
accumulated cost values.

isHighCostExpansion will return t

[SCEVExpander] Migrate costAndCollectOperands to use InstructionCost.

This patch changes costAndCollectOperands to use InstructionCost for
accumulated cost values.

isHighCostExpansion will return true if the cost has exceeded the budget.

Reviewed By: CarolineConcatto, ctetreau

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

show more ...

[llvm] Use llvm::is_contained (NFC)