#
b0abd489 |
| 17-Jun-2023 |
Elliot Goodrich <elliotgoodrich@gmail.com> |
[llvm] Add missing StringExtras.h includes
In preparation for removing the `#include "llvm/ADT/StringExtras.h"` from the header to source file of `llvm/Support/Error.h`, first add in all the missing
[llvm] Add missing StringExtras.h includes
In preparation for removing the `#include "llvm/ADT/StringExtras.h"` from the header to source file of `llvm/Support/Error.h`, first add in all the missing includes that were previously included transitively through this header.
show more ...
|
#
406e9c93 |
| 23-Jun-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Use object size for allocas as well
The object size and alignment based restriction on the possible allocation range also applies to allocas, not just globals, so handle them as well.
We sho
[SCEV] Use object size for allocas as well
The object size and alignment based restriction on the possible allocation range also applies to allocas, not just globals, so handle them as well.
We shouldn't really need any type restriction here at all, but for now stay conservative.
show more ...
|
#
6555b5dc |
| 23-Jun-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Store getValue() result in variable (NFC)
|
#
ce1ac1cf |
| 19-Jun-2023 |
Dmitry Makogon <d.makogon@g.nsu.ru> |
[SCEV] Don't store AddRec loop when simplifying multiplication of AddRecs
When multiplying several AddRecs, we do the following simplification:
{A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L> = {
[SCEV] Don't store AddRec loop when simplifying multiplication of AddRecs
When multiplying several AddRecs, we do the following simplification:
{A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L> = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [ choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z]] ],+,...up to x=2n}
This is done iteratively, pair by pair. So if we try to multiply three AddRecs A1, A2, A3, then we'd try to simplify A1 * A2 to A1' and then try to simplify A1' * A3 if A1' is also an AddRec. The transform is only legal if the loops of the two AddRecs are the same. It is checked in the code, but the loop of one of the AddRecs is stored in a local variable and doesn't get updated when we simplify a pair to a new AddRec. In the motivating test the new AddRec A1' was created for a different loop and, as the loop variable didn't get updated, the check for different loops passed and the transform worked for two AddRecs from different loops. So it created a wrong SCEV. And it caused LSR to replace an instruction with another one that had the same SCEV as the incorrectly computed one.
Differential Revision: https://reviews.llvm.org/D153254
show more ...
|
#
2ba78229 |
| 09-Jun-2023 |
Florian Hahn <flo@fhahn.com> |
[SCEV] Try smaller ZExts when using loop guard info.
If we didn't find the extact ZExt expr in the rewrite map, check if there's an entry for a smaller ZExt we can use instead.
Reviewed By: nikic
[SCEV] Try smaller ZExts when using loop guard info.
If we didn't find the extact ZExt expr in the rewrite map, check if there's an entry for a smaller ZExt we can use instead.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D149786
show more ...
|
#
c1aa0dce |
| 09-Jun-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Remove -verify-scev-maps flag
This is now checked as part of the usual SCEV verification. There is little value in checking this on each lookup.
These two maps are strictly synchronized nowa
[SCEV] Remove -verify-scev-maps flag
This is now checked as part of the usual SCEV verification. There is little value in checking this on each lookup.
These two maps are strictly synchronized nowadays, which was not the case historically.
show more ...
|
#
6ed152af |
| 30-May-2023 |
Joshua Cao <cao.joshua@yahoo.com> |
[SCEV] Compute AddRec range computations using different type BECount
Before this patch, we can only use the MaxBECount for an AddRec's range computation if the MaxBECount has <= bit width of the Ad
[SCEV] Compute AddRec range computations using different type BECount
Before this patch, we can only use the MaxBECount for an AddRec's range computation if the MaxBECount has <= bit width of the AddRec. This patch reasons that if a MaxBECount has > bit width, and is <= the max value of AddRec's bit width, we can still use the MaxBECount.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D151698
show more ...
|
#
46c59a55 |
| 31-May-2023 |
Joshua Cao <cao.joshua@yahoo.com> |
[SCEV][NFC] Refactor range computation for AddRec to pass around APInt
|
#
ff471dcf |
| 01-Jun-2023 |
Joshua Cao <cao.joshua@yahoo.com> |
[SCEV] Fix verification of SCEV multiples.
|
#
0c23dc20 |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
Reapply [SCEV] Replace IsAvailableOnEntry with block disposition
This exposed an issue in SCEVExpander/LCSSA, which has been fixed in D150681.
-----
As far as I understand, the IsAvailableOnEntry(
Reapply [SCEV] Replace IsAvailableOnEntry with block disposition
This exposed an issue in SCEVExpander/LCSSA, which has been fixed in D150681.
-----
As far as I understand, the IsAvailableOnEntry() function basically implements the same functionality as the properlyDominates() block disposition. The primary difference (apart from a weaker implementation) seems to be in this comment at the top:
// Checks if the SCEV S is available at BB. S is considered available at BB // if S can be materialized at BB without introducing a fault.
However, I don't really understand why there would be such a requirement. It's my understanding that SCEV explicitly does not care about trapping udiv instructions itself, and it's the job of SCEVExpander's isSafeToExpand() to make sure these don't get expanded if they may trap.
Differential Revision: https://reviews.llvm.org/D149344
show more ...
|
#
6006d43e |
| 24-May-2023 |
Craig Topper <craig.topper@sifive.com> |
LLVM_FALLTHROUGH => [[fallthrough]]. NFC
Reviewed By: MaskRay
Differential Revision: https://reviews.llvm.org/D150996
|
#
2bb35151 |
| 03-May-2023 |
Dmitry Makogon <d.makogon@g.nsu.ru> |
[SCEV] Replace NumTripCountsComputed stat with NumExitCountsComputed
This fixes assertion crash in https://github.com/llvm/llvm-project/issues/62380.
In the beginning of ScalarEvolution::getBackedg
[SCEV] Replace NumTripCountsComputed stat with NumExitCountsComputed
This fixes assertion crash in https://github.com/llvm/llvm-project/issues/62380.
In the beginning of ScalarEvolution::getBackedgeTakenInfo we make sure that BackedgeTakenCounts contains an entry for the given loop. Then we call computeBackedgeTakenCount which computes the result, and in the end we insert it in the map like so:
return BackedgeTakenCounts.find(L)->second = std::move(Result);
So we expect that the entry for L still exists in the cache. However, it can get deleted. When it has computed the result, getBackedgeTakenInfo clears all the cached SCEVs that use the AddRecs in the loop.
In the crashing example, getBackedgeTakenInfo first gets called on an inner loop, and during this call it gets called again on its parent loop. This recursion happens after the call to computeBackedgeTakenCount. And it happens so that some SCEV from the BTI of the child loop uses an AddRec of the parent loop. So when we successfully compute BTI for the parent loop, we erase already computed result for the child one.
The recursion happens in some debug only code that updates statistics. The algorithm itself is non-recursive. Namely the recursive call happens in BackedgeTakenInfo::getExact function and its return value is only used to compare it against SCEVCouldNotCompute.
As suggested by nikic I replaced the NumTripCountsComputed and NumTripCountsNotComputed with NumExitCountsComputed and NumExitCountsNotComputed respectively. They are updated during computations made for single exits. It relieves us of the need to compute exact exit count for the loop just to update the named statistic and thus the recursion cannot happen anymore.
Differential Revision: https://reviews.llvm.org/D149251
show more ...
|
#
c8eb535a |
| 23-Mar-2023 |
eopXD <yueh.ting.chen@gmail.com> |
[1/11][IR] Permit load/store/alloca for struct of the same scalable vector type
This patch-set aims to simplify the existing RVV segment load/store intrinsics to use a type that represents a tuple o
[1/11][IR] Permit load/store/alloca for struct of the same scalable vector type
This patch-set aims to simplify the existing RVV segment load/store intrinsics to use a type that represents a tuple of vectors instead.
To achieve this, first we need to relax the current limitation for an aggregate type to be a target of load/store/alloca when the aggregate type contains homogeneous scalable vector types. Then to adjust the prolog of an LLVM function during lowering to clang. Finally we re-define the RVV segment load/store intrinsics to use the tuple types.
The pull request under the RVV intrinsic specification is riscv-non-isa/rvv-intrinsic-doc#198
---
This is the 1st patch of the patch-set. This patch is originated from D98169.
This patch allows aggregate type (StructType) that contains homogeneous scalable vector types to be a target of load/store/alloca. The RFC of this patch was posted in LLVM Discourse.
https://discourse.llvm.org/t/rfc-ir-permit-load-store-alloca-for-struct-of-the-same-scalable-vector-type/69527
The main changes in this patch are:
Extend `StructLayout::StructSize` from `uint64_t` to `TypeSize` to accommodate an expression of scalable size.
Allow `StructType:isSized` to also return true for homogeneous scalable vector types.
Let `Type::isScalableTy` return true when `Type` is `StructType` and contains scalable vectors
Extra description is added in the LLVM Language Reference Manual on the relaxation of this patch.
Authored-by: Hsiangkai Wang <kai.wang@sifive.com> Co-Authored-by: eop Chen <eop.chen@sifive.com>
Reviewed By: craig.topper, nikic
Differential Revision: https://reviews.llvm.org/D146872
show more ...
|
#
79cbedaf |
| 17-May-2023 |
Simon Pilgrim <llvm-dev@redking.me.uk> |
Fix MSVC "result of 32-bit shift implicitly converted to 64 bits" warning. NFC.
|
#
b27f14d9 |
| 15-May-2023 |
Joshua Cao <cao.joshua@yahoo.com> |
[SCEV][NFC-mostly] Remove constant handling in TripMultiple computation
After landing more precise trip multiples in https://reviews.llvm.org/D149529, the SCEV multiple computation handles constants
[SCEV][NFC-mostly] Remove constant handling in TripMultiple computation
After landing more precise trip multiples in https://reviews.llvm.org/D149529, the SCEV multiple computation handles constants, so there is no longer any need for special constant handling in getSmallConstantTripMultiple.
This patch can improve the multiple of a non-constant SCEV that is huge (>=2**32). This is very rare in practice.
Differential Revision: https://reviews.llvm.org/D150541
show more ...
|
#
9fb9c777 |
| 10-May-2023 |
Manoj Gupta <manojgupta@google.com> |
Revert "[SCEV] Replace IsAvailableOnEntry with block disposition"
This reverts commit 103fc0f629aa6218783f65dff0197f257137cade. Causes a clang crash in ChromeOS builds. Testcase provided at D149344.
|
#
9c1d5e4a |
| 25-Apr-2023 |
Joshua Cao <cao.joshua@yahoo.com> |
[SCEV][reland] More precise trip multiples
We currently have getMinTrailingZeros(), from which we can get a SCEV's multiple by computing 1 << MinTrailingZeroes. However, this only gets us multiples
[SCEV][reland] More precise trip multiples
We currently have getMinTrailingZeros(), from which we can get a SCEV's multiple by computing 1 << MinTrailingZeroes. However, this only gets us multiples that are a power of 2. This patch introduces a way to get max constant multiples that are not just a power of 2. The logic is similar to that of getMinTrailingZeros. getMinTrailingZerosImpl is replaced by computing the max constant multiple, and counting the number of trailing bits.
I have so far found this useful in two places:
1) Computing unsigned constant ranges. For example, if we have i8 {10,+,10}<nuw>, we know the max constant it can be is 250.
2) My original intent was to use this in getSmallConstantTripMultiples, but it has no effect right now due to change from D110587. For example, if we have backedge count `(6 * %N) - 1`, the trip count becomes `1 + zext((6 * %N) - 1)`, and we cannot say that 6 is a multiple of the SCEV. I plan to look further into this separately.
The implementation assumes the value is unsigned. It can probably be extended to handle signed values as well.
If the code sees that a SCEV does not have <nuw>, it will fall back to finding the max multiple that is a power of 2. Multiples that are a power of 2 will still be a multiple even after the SCEV overflows. This does not apply to other values. This is the 1st commit message:
---
This relands https://reviews.llvm.org/D141823. The verification fails when expensive checks are turned on. This can occur when:
1. SCEV S's multiple is cached 2. SCEV S's no wrap flags are strengthened, and the multiple changes 3. SCEV verifier finds that S's cached and recomputed multiple are different
We eliminate most cases by forgetting SCEVAddRecExpr's cached values when the flags are modified, but there are still cases for other SCEV types. We relax the check by making sure the cached multiple divides the recomputed multiple, ensuring the cached multiple is correct, conservative multiple.
Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D149529
show more ...
|
#
37161250 |
| 02-May-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Reuse Accum variable when handling GEP flags
The GEP minus the base pointer (which is the pre-inc addrec) is exactly the Accum value that was already calculated.
|
#
b14be1e7 |
| 29-Apr-2023 |
Florian Hahn <flo@fhahn.com> |
[SCEV] Use object size for globals to sharpen ranges.
The highest address the object can start is ObjSize bytes before the end (unsigned max value). If this value is not a multiple of the alignment,
[SCEV] Use object size for globals to sharpen ranges.
The highest address the object can start is ObjSize bytes before the end (unsigned max value). If this value is not a multiple of the alignment, the last possible start value is the next lowest multiple of the alignment. Note: The computations cannot overflow, because if they would there's no possible start address for the object.
At the moment, this is limited to GlobalVariables, because I could not find a API similar to getObjectSize to also get the alignment of the object. With such an API, this can be generalized to general addresses.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D149483
show more ...
|
#
4c2d29f2 |
| 28-Apr-2023 |
Florian Hahn <flo@fhahn.com> |
[SCEV] Skip instrs with non-scevable types in visitAndClearUsers.
No SCEVs are formed for instructions with non-scevable types, so no other SCEV expressions can depend on them. Skip those instructio
[SCEV] Skip instrs with non-scevable types in visitAndClearUsers.
No SCEVs are formed for instructions with non-scevable types, so no other SCEV expressions can depend on them. Skip those instructions and their users when invalidating SCEV expressions.
Depends on D144847.
Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D144848
show more ...
|
#
3ddd1ffb |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Don't invalidate past dependency-breaking instructions
When invalidating a value, we walk all users of that value and invalidate them as well. This can be very expensive for large use graphs.
[SCEV] Don't invalidate past dependency-breaking instructions
When invalidating a value, we walk all users of that value and invalidate them as well. This can be very expensive for large use graphs.
However, we only need to invalidate a user U of instruction I if SCEV(U) can depend on SCEV(I). This is not the case if U is an instruction that always produces a SCEVUnknown, such as a load. If the load pointer operand is invalidated, there is no need to invalidate the load result, which is completely unrelated from a SCEV perspective.
Differential Revision: https://reviews.llvm.org/D149323
show more ...
|
#
103fc0f6 |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Replace IsAvailableOnEntry with block disposition
As far as I understand, the IsAvailableOnEntry() function basically implements the same functionality as the properlyDominates() block dispos
[SCEV] Replace IsAvailableOnEntry with block disposition
As far as I understand, the IsAvailableOnEntry() function basically implements the same functionality as the properlyDominates() block disposition. The primary difference (apart from a weaker implementation) seems to be in this comment at the top:
// Checks if the SCEV S is available at BB. S is considered available at BB // if S can be materialized at BB without introducing a fault.
However, I don't really understand why there would be such a requirement. It's my understanding that SCEV explicitly does not care about trapping udiv instructions itself, and it's the job of SCEVExpander's isSafeToExpand() to make sure these don't get expanded if they may trap.
Differential Revision: https://reviews.llvm.org/D149344
show more ...
|
#
fa0014a6 |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Drop LCSSA check in createNodeFromSelectLikePHI()
SCEV expressions no longer try to preserve LCSSA form. SCEV construction will try to look through LCSSA phi nodes. As such, we also no longer
[SCEV] Drop LCSSA check in createNodeFromSelectLikePHI()
SCEV expressions no longer try to preserve LCSSA form. SCEV construction will try to look through LCSSA phi nodes. As such, we also no longer need to limit this special-case fold.
show more ...
|
#
079c525f |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Try simplifying phi before createNodeFromSelectLikePHI()
Sometimes a phi can both be trivial and match the createNodeFromSelectLikePHI() fold. In that case it is generally more profitable to
[SCEV] Try simplifying phi before createNodeFromSelectLikePHI()
Sometimes a phi can both be trivial and match the createNodeFromSelectLikePHI() fold. In that case it is generally more profitable to look through the phi node.
show more ...
|
#
c27a9660 |
| 27-Apr-2023 |
Nikita Popov <npopov@redhat.com> |
[SCEV] Remove LCSSA special case in getSCEVAtScope() (NFCI)
We no longer try to preserve LCSSA form in SCEV representation: Nowadays, we look through LCSSA PHI nodes directly during SCEV constructio
[SCEV] Remove LCSSA special case in getSCEVAtScope() (NFCI)
We no longer try to preserve LCSSA form in SCEV representation: Nowadays, we look through LCSSA PHI nodes directly during SCEV construction. As such, this separate special case in getSCEVAtScope() is no longer needed.
show more ...
|