Use SCEVPtrToAddr instead of SCEVPtrToInt for pointer -> int
conversion in SCEV, like when computing trip count expressions.
getPtrToIntExpr now also creates SCEVPtrToAddrExpr.
Removal of SCEVPtrToIntExpr out of this PR, to limit the scope and
will be done as NFC follow-up.
PR: https://github.com/llvm/llvm-project/pull/180244
abandonDependences() uses unique_ptr::release() which releases
ownership without freeing the Dependences object, causing a memory
leak. Use unique_ptr::reset() instead to properly delete the object
before nullifying the pointer.
The issue was found when AddressSanitizer is enabled in the build.
getBlocksVector, mutable getBlocksSet, getSubLoopsVector, and
getTopLevelLoopsVector expose LoopInfo's internal containers, so every
caller open-codes loop-nest surgery, keeps the block vector and set in
sync by hand, and freezes the representation. Replace them with two
LoopInfoBase operations:
* removeBlocksIf(LoopT &, Pred): drop matching blocks from a loop.
* takeChildrenIf(LoopT *Parent, Pred): detach and return matching
children, clearing their parent; a null Parent means the top level.
Both preserve the relative order of what remains. Mutation inside
LoopInfoBase also lets the analysis repair derived state once per edit
and finish a multi-step edit before any query observes it, which an
accessor returning a container cannot.
For the same reason, move hasNoExitBlocks, getExitEdges, and
getUniqueLatchExitBlock onto LoopInfoBase.
Two behavior changes: SimpleLoopUnswitch's deleteDeadBlocksFromLoop runs
its per-child deletion callbacks while the forest is still consistent,
before detaching and destroying dead children; FixIrreducible's
reconnectChildLoops keeps children in their original order rather than
std::partition's.
Aided by Claude Fable 5
The IslMaxOperationsGuard in DeLICM previously covered only the zone
analysis performed in computeZone(). The subsequent greedyCollapse() ->
collapseScalarsToStore() path calls computeScalarReachingOverwrite(),
which performs an unbounded ISL lexmin().
Share a single[already present], dormant IslMaxOperationsGuard across
both regions and arm it narrowly around each operation intensive
computation via IslQuotaScope, so the same operations budget covers both
computeZone() and the scalar collapsing. When the quota is exceeded
during scalar collapsing, bail out cleanly: increment DeLICMOutOfQuota
and emit an "OutOfQuota" analysis remark.
Fixes: https://github.com/llvm/llvm-project/issues/202045
DeLICM may produce new read access relations whose domain is restricted
to the DefinedBehaviorContext (e.g., only valid when a parameter ensures
no UB). The validation in setNewAccessRelation already accounts for
this, but the debug assertions in createNewAccesses and
generateScalarLoads did not, causing false assertion failures during
code generation.
Intersect the checked domains with getBestKnownDefinedBehaviorContext()
to match the contract that DeLICM relies on.
Fixes#205732
When -polly-annotate-metadata-vectorize is active, Polly marks its
generated loops with llvm.loop.vectorize.enable=true. This is harmful
for loops with a loop-carried dependence of distance 1 that involve
floating-point operations: the Loop Vectorizer reorders FP operations
(e.g. scalar reduction like q = factor*q), producing results that differ
from the sequential scalar reference and causing correctness failures.
Two changes are made:
1. IslAst.cpp: add PollyVectorizeMetadata to the PerformParallelTest
gate so that dependence-distance computation is performed whenever
-polly-annotate-metadata-vectorize is passed, not only when
-polly-parallel or a vectorizer is active.
2. IslNodeBuilder.cpp / LoopGenerators.cpp: when a loop has a dist=1
dependence involving FP operations, omit the vectorize.enable annotation
entirely. This lets the Loop Vectorizer apply its own cost model and
legality checks decide.
The external shell is getting removed soon, so remove the ability to
force enable it for polly tests.
Reviewers: ilovepi, Meinersbur, petrhosek
Pull Request: https://github.com/llvm/llvm-project/pull/209566
#204146 revealed that Polly can call `SCEVDivision::divide` with a
numerator and denominator of different types. I believe such divisions
are not meaningful and should be avoided. As far as I can tell, the root
cause is that `SCEVRemoveMax::rewrite` may collect terms whose types
differ from that of the original expression.
Before this patch, the terms gathered by `SCEVRemoveMax::rewrite` were
used for delinearization as they are. This patch applies
`getTruncateOrSignExtend` to them to matching their types with that of
the original expression.
visitUnknown follow VMap, call GenSE.getSCEV() on the mapped value, and
get back the original AddRec, recursing visitAddRecExpr infinitely.
Insert the result into SCEVCache before calling visit() to cut
recursion.
Fixes#205137.
The precise semantics of `dereferenceable` are currently undocumented,
but de facto they are:
* Argument position `dereferenceable` implies that the memory remains
dereferenceable while the function executes.
* Return position `dereferenceable` implies that the memory remains
dereferenceable forever.
This is not coherent with how these attributes are used, in at least two
ways:
* C++ reference arguments are annotated as `dereferenceable` by Clang.
However, C++ does not actually make any guarantees that the underlying
memory does not get freed during the execution of the function. (Unlike
Rust, which does guarantee this via protectors in SB/TB.)
* We infer `dereferenceable` on allocator return values (from
`allocsize`). Allocator return values quite obviously do not stay
dereferenceable forever, as they can be freed.
This PR changes the semantics of `dereferenceable` to apply at-point,
i.e. only directly on function entry (for arguments), or at the position
of the call (for return values). The fact that the memory cannot be
freed between the point where the `dereferenceable` fact has been
established and the point where we're trying to speculate needs to be
explicitly proven now.
The main ways this happens is:
* Via `nofree` function attributes (inferred).
* Via `noalias nofree` argument attributes. The latter is inferred, but
the former generally requires frontend annotation. In Rust the
combination of `noalias nofree dereferenceable` is used, so it should
not be materially affected by these changes.
* Context-sensitive analysis to check for frees (i.e. non-nofree calls
or synchronizing atomics) between the point of definition and the point
of speculation.
It's expected that this will regress optimization of C++ code in some
cases, because we can no longer use dereferenceability facts that are
not, in fact, guaranteed to hold.
This finishes implementing an old RFC:
https://discourse.llvm.org/t/rfc-decomposing-deref-n-into-deref-n-nofree/57873
llvm-project is home to many sphinx documentation sites, each with
configuration quirks and bespoke extensions.
The sphinx config model makes sharing code somewhat difficult. There
are options like sphinx-multiproject, but some of our docs builds are
out of the source tree while some are done out of the binary tree, so
the multiproject configuration itself would need to be generated. It
also would impose more uniformity around extensions than required.
This change instead creates a python package at utils/docs/llvm_sphinx
and makes it available to all sphinx-build processes via PYTHONPATH.
Each conf.py does not modify its own sys.path because not all builds are
out of the source tree, so there isn't a stable relative path to use to
refer to the utils/docs/ directory.
Type checking via pyright in new package is pinned to being python 3.8
compatible.
The myst slug script from llvm/docs is promoted to be the default,
with a slight edit to targets needed in FlangDriver.md to adapt to the
change.
The ghlinks extension from clang gets lifted to be the first generic
extension, although it is still only used in clang currently. I used it
as an example of a general extension that might be useful for other
projects, but I also intend to add a new generic extension in a future
patch.
As part of the move ghlinks is refactored a bit:
* Rather than have a main function directly to run its tests, those
tests are now run via the command-line entrypoint to the new package,
e.g. `python utils/docs --test` will now replace
`python clang/docs/ghlinks.py --test`. This makes the command-line
more pithy (`python utils/docs/llvm_sphinx/ext/ghlinks --test` is a
bit long), and makes the default behavior when running be to
include utils/docs in the sys.path, so imports can be absolute and
the behavior is as close to the CMake targets as possible.
* The static files that were previously written to a tempdir during
testing are just committed directly in git. The assumption here is
that the original version was taking pains to avoid polluting the
clang/docs directory with test files that would confuse sphinx-build,
and without that limitation the workaround can be removed.
* Some typing-related changes to make it strictly python 3.8 compatible.
Change-Id: Ie16de273f74973f163dbf7fe9d22d80a466d051f
When we're computing the range of the addrec, we already have to reason
about whether it wraps, so we may as well determine the nowrap flags at
the same time.
This is more precise than the previous logic that took the addrec range
and checked whether adding a step to it does not wrap. For example, an
`{0,+,1}` addrec with a full range can still be non-wrapping.
Note that I removed some assertions in the SCEV printed that predicated
exit counts actually have predicates. Due to SCEV's query order
dependence, this can happen, also prior to this change, see for example
https://llvm.godbolt.org/z/cWK1MMEqv. While this indicates suboptimal
results, it's not a bug, and we should not assert.
Fixes https://github.com/llvm/llvm-project/issues/200788.
In the original PR for this feature, the third parameter of
`MemorySSAUpdater::applyUpdates` was not set to `true`. This
caused `DT` to be invalid, resulting in the failures. This PR fixes the
issue and provides an additional testcase.
Also in the original commit had three asserts to confirm
`!ModifiedBranch ` when we bail out. One of these is redundant because
it is enclosed in an `if` statement checking the same condition. This PR removes
the redundant `assert` too.
Includes changes to guard against a nullptr TLI and Call. TargetFold or
InstSimplify fold in IRBuilderBase::CreateIntrinsic, in the same way we
fold in Create(Unary|Binary)Intrinsic.
For a loop like this
```
for (int j = 0; j < M; j++) {
if (N <= 0) continue; // invariant guard branches to latch
for (int i = 0; i < N; i++)
A[i] = B[i] + 1;
}
```
Since none of the successors of the guard branch of the inner loop are
outside the loop `j`, unswitching treats this as a non-trivial branch.
In reality, this is a perfect loop nest. If the condition of the guard
of `i` loop is false, there is nothing to do and so if we unswitch this
branch, the loop does not need to be versioned. This matches the
requirements of a trivial unswitch. This patch extends trivial loop
unswitching to catch cases like this.
The patch changes the loop guard so that instead of branching to the
latch of the outer loop, it exits the loop. This allows the existing code
for trivial unswitching to perform the transformation. The change in the
loop guard will happen only if all conditions for unswitching are met.
The previous attempt at this (b7da956501)
still broke standalone builds. Now I have locally tested standalone
flang, runtimes (with openmp), lldb, combined builds, and the utils
script. Hopefully that covers everything this time, and gets everything
into a more consistent state (always using the HandleDoxygen script in
the same way, included exactly once as required by the cmake design).
Reverts llvm/llvm-project#191501 as cmake CI is having an issue with it:
```
-- Doxygen enabled (1.14.0).
CMake Error at /work/as-worker-4/publish-doxygen-docs/llvm-project/cmake/Modules/HandleDoxygen.cmake:29 (add_custom_target):
add_custom_target cannot create target "doxygen" because another target
with the same name already exists. The existing target is a custom target
created in source directory
"/work/as-worker-4/publish-doxygen-docs/llvm-project/llvm". See
documentation for policy CMP0002 for more details.
Call Stack (most recent call first):
docs/CMakeLists.txt:59 (include)
```
#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.
ScopInfo expects the state of the IR to reflect the state before
codegen. Invalidating ScalarEvolution/SCEVs has the effect that values
need to be reanalyzed, but this is not possible during codegen where the
CFG and SSA is not yet in a consistent state. That is, we rely on
ScalarEvolution to cache SCEVs from before the codegen phase. If
ScalarEvolution did not already do this, Polly would need to more
aggressively store SCEVs itself (in this case: `canSyntheziseInStmt`)
instead of asking ScalarEvolution.
The SCEV invalidation was introduced in
a61eda7698 which unfortunately does not
explain the issue it intends to fix. The added test case passes even
without the invalidation. In any case, SCEVs should represent the state
before codegen.
Fixes#192208
It's very easy to forget to add `isRequired() { return true; }` for
passes that must be run on all IR, rather than e.g. being skipped on
optnone functions.
This PR adds RequiredPassInfoMixin/OptionalPassInfoMixin which have
`isRequired()`, and the long term vision is there to be no default
`isRequired()` on PassInfoMixin.
However, for out-of-tree migration purposes, we leave a `isRequired() {
return false; }` for now in PassInfoMixin.
https://discourse.llvm.org/t/rfc-introduce-mandatorypassinfomixin-optionalpassinfomixin-for-required-not-required-passes/90547
Assisted-by: Gemini
SCEVExpander's builder already uses InstSimplifyFolder. Use it to
construct binary ops via CreateBinOp instead of BinaryOperator::Create.
This helps to simplify away a few more instructions during SCEV
expansion.
PR: https://github.com/llvm/llvm-project/pull/154148
These should use O2 with the optsize or minsize attributes instead.
This enforces that there is no divergence between pipeline-level Os/Oz
and function-level Os/Oz at an architectural level.
For the purpose of testing IR that does not have optsize/minsize itself,
it's possible to use `-force-attribute=optsize` etc.
Polly library targets already disable PCH reuse because Polly
unconditionally builds with -fno-rtti and -fno-exceptions. Reusing LLVM
PCHs that were built with RTTI or exceptions enabled is incompatible
with Clang when compiling Polly targets under those flags.
After 47eb8b43c9 enabled PCH reuse for unit tests, Polly unit tests
can hit the same mismatch as the library targets. Pass DISABLE_PCH_REUSE
through the shared add_polly_unittest wrapper so all Polly unit tests
follow the existing Polly target policy.
cc @aengelke -- a minor fix for polly.
A single-valued set/map is not necessarily single-valued anymore after
applying after gisting a context. In particular, the set/map might not
be single-valued outside the context.
Convert the result of MemoryAccess::getAddressFunction() directly to
pw_aff. Since it is the result of lexmin(), it is single-valued by
definition. Gist the context only after te conversion.
We should consider using `isl_basic_map_partial_lexmin_pw_multi_aff` in
`getAddressFunction()` directly to avoid the intermediate step.
Fixes#190459
The patch moves out of SCEV's scope so they can be re-used for SCEVUse.
SCEVUse gets an additional getNoWrapFlags helper that returns the union
of the expressions SCEV flags and the use-specific flags.
SCEVExpander has been updated to use this new helper.
In order to avoid other changes, the original names are exposed via
constexpr in SCEV. Not sure if there's a nicer way. One alternative
would be to define the enum in struct, and have SCEV inherit from it.
The patch also clarifies that the SCEVUse flags encode NUW/NSW, and
hides getInt, setInt, etc to avoid potential mis-use.
PR: https://github.com/llvm/llvm-project/pull/190199
The code that emits the conditions for whether a statement is executed
by checking whether we are in the statement's domain may apply
assumptions (such as an integer truncation being reversible). Later code
then assumes that these assumptions are only relevent for then the
statement is executed, but actually it is used for determining whether
it is executed.
Break this circular reasoning by introducing an `IsInsideDomain` flag
that can be set when the domain has not been verified yet.
Fixes#190128
Thanks to @thapgua for the bug report
The conversion of SCEVs to isl::pw_aff may only be valid under
conditions that have to be confirmed via RTC. This also happens with
__builtin_assume. These user-added assumptions are then added to
ScopInfo::Context. However, the conclusion in ScopInfo::Context is then
also used to simplify ("gist") its own RTC preconditions in
ScopInfo::AssumedContext and ScopInfo::InvalidContext away.
Avoid by adding user assumptions with preconditions to
ScopInfo::DefinedBehaviourContext instead, which is not used to simplify
AssumedContext/InvalidContext.
Fixes#187922
Thanks @thapgua for the report
#184545 default-enables the IO sandbox in assert-builds. This causes
Clang using Polly to crash (#188568).
The issue is that `PassBuilder` uses `vfs::getRealFileSystem()` by
default which is considered a IO sandbox violation in the Clang process.
With this PR store the VFS from the `PassBuilder` from the original
`registerPollyPasses` call for creating other `PassBuilder` instances.
This PR also adds infrastructure for running Polly in `clang` (in
addition in `opt`). `opt` does not enable the sandbox such that we need
separate tests using Clang.
Closes: #188568
Replace the DenseMap from blocks to their innermost loop a vector
indexed by block numbers, when possible. Supporting number updates is
not trivial as we don't store a list of basic blocks, so this is not
implemented.
NB: I'm generally not happy with the way loops are stored. As I think
that there's room for improvement, I don't want to touch the
representation at this point.
Pull Request: https://github.com/llvm/llvm-project/pull/103400
