This adds a mostly flow-insensitive analysis that runs before the
dominator-based transformations. The analysis is simple and efficient
because it only needs to track data flow of currently in-scope
accesses. The original dominator tree walk remains simple, but it now
checks the flow insensitive analysis information to determine general
correctness. This is now correct in the presence of all kinds of nested
static and dynamic nested accesses, call sites, coroutines, etc.
This is a better compromise than:
(a) disabling the pass and taking a major performance loss.
(b) converting the pass itself to full-fledged data flow driven
optimization, which would be more optimal because it could remove
accesses when nesting is involved, but would be much more expensive
and complicated, and there's no indication that it's useful.
The new approach is also simpler than adding more complexity to
independently handle to each of many issues:
- Nested reads followed by a modify without a false conflict.
- Reads nested within a function call without a false conflict.
- Conflicts nested within a function call without dropping enforcement.
- Accesses within a generalized accessor.
- Conservative treatment of invalid storage locations.
- Conservative treatment of unknown apply callee.
- General analysis invalidation.
Some of these issues also needed to be considered in the
LoopDominatingAccess sub-pass. Rather than fix that sub-pass, I just
integrated it into the main pass. This is a simplification, is more
efficient, and also handles nested loops without creating more
redundant accesses. It is also generalized to:
- hoist non-uniquely identified accesses.
- Avoid unnecessarily promoting accesses inside the loop.
With this approach we can remove the scary warnings and caveats in the
comments.
While doing this I also took the opportunity to eliminate quadratic
behavior, make the domtree walk non-recursive, and eliminate cutoff
thresholds.
Note that simple nested dynamic reads to identical storage could very
easily be removed via separate logic, but it does not fit with the
dominator-based algorithm. For example, during the analysis phase, we
could simply mark the "fully nested" read scopes, then convert them to
[static] right after the analysis, removing them from the result
map. I didn't do this because I don't know if it happens in practice.
This is the first in a sequence of patches that implement various optimizations
to transform load [copy] into load_borrow.
The optimization works by looking for a load [copy] that:
1. Only has destroy_value as consuming users. This implies that we do not need
to pass off the in memory value at +1 and that we can use a +0 value.
2. Is loading from a memory location that is never written to or only written to
after all uses of the load [copy].
and then RAUW the load [copy] with a load_borrow and convertes the destroy_value
to end_borrow.
NOTE: I also a .def file for AccessedStorage so we can do visitors over the
kinds. The reason I want to do this is to ensure that people update these
optimizations if we add new storage kinds.
The SIL verifier was asserting while attempting to prove that all
formal accesses are well-formed. This is necessary because
unrecognized access could lead to invalid whole-module optimization.
We would like to eliminate address-phis from SIL, but there are still
optimizer passes that produce them. For now, the best we can do is
hope to recover the original base of each phi value and prove they are
actually the same value. They should be because the optimizer
produced the phi through block cloning.
Fixes <rdar://problem/46114512> SIL verification failed: Unknown
formal access pattern: storage
This silences the instances of the warning from Visual Studio about not all
codepaths returning a value. This makes the output more readable and less
likely to lose useful warnings. NFC.
Sometions we don't have a projection path for each ref_elem_addr - fixes a compiler crash in Deferred in the Source Compatibility Suite
When checking if two storage locations are distinct from one another, play it safe in such a case.
Consider a class ‘C’ with distinct fields ‘A’ and ‘B’
And consider we are accessing C.A and C.B inside a loop
LICM well not hoist the exclusivity checking outside of the loop because isDistinctFrom(C.A, C.B) returns false.
This is because the helper function bails if isUniquelyIdentified returns false (which is the case in class kinds)
Same with all other potential access enforcement optimizations.
This PR resolves that
For now, the accessors have been underscored as `_read` and `_modify`.
I'll prepare an evolution proposal for this feature which should allow
us to remove the underscores or, y'know, rename them to `purple` and
`lettuce`.
`_read` accessors do not make any effort yet to avoid copying the
value being yielded. I'll work on it in follow-up patches.
Opaque accesses to properties and subscripts defined with `_modify`
accessors will use an inefficient `materializeForSet` pattern that
materializes the value to a temporary instead of accessing it in-place.
That will be fixed by migrating to `modify` over `materializeForSet`,
which is next up after the `read` optimizations.
SIL ownership verification doesn't pass yet for the test cases here
because of a general fault in SILGen where borrows can outlive their
borrowed value due to being cleaned up on the general cleanup stack
when the borrowed value is cleaned up on the formal-access stack.
Michael, Andy, and I discussed various ways to fix this, but it seems
clear to me that it's not in any way specific to coroutine accesses.
rdar://35399664
Now that SILGen change adds Unsafe access markers to addressors and
materializeForSet, we can use that as a sentinel to enable strict
verification everywhere.
* SILModule::isVisibleExternally utility for VarDecls.
* Fix the SIL parser so it doesn't drop global variable decls.
This information was getting lost in SIL printing/parsing.
Some passes rely on it. Regardless of whether passes should rely on it,
it is totally unacceptable for the SIL passes to have subtle differences
in behavior depending on the frontend mode. So, if we don't want passes
to rely on global variable decls, that needs to be enforced by the API
independent of how the frontend is invoked or how SIL is serialized.
* Use custom DemangleOptions to lookup global variable identifiers.
* SILGlobalVariable utilities.
Move the utilities that are required for recognizing SILGlobalVariable access
into SILGlobalVariable.[h|cpp].
Structural SIL properties that are assumed by the optimizer, and thus required
for SIL verification, should never be embedded in SILOptimizer passes, or even
in SILOptimizer/Utils. Structural SIL properties need to be defined in
/SIL. They are as much part of the SIL language as the opcode list.
These particular utilities are required for working with SILGlobalVariables, and
will be used by a whole-module access enforcement optimization.
The primary API for recognizing SIL globals is `getVariableOfGlobalInit`. It is
required to find the association between the addressor SILFunction marked
[global_init], and the SILGlobalVariable being addressed.
Other helper APIs expose more details about the addressor's SIL patterns and are
useful for transforming the initializer itself into an optimized form.
Use AccessedStorageAnalysis to find access markers with no nested conflicts.
This optimization analyzes the scope of each access to determine
whether it contains a potentially conflicting access. If not, then it
can be demoted to an instantaneous check, which still catches
conflicts on any enclosing outer scope.
This removes up to half of the runtime calls associated with
exclusivity checking.
An interprocedural analysis pass that summarizes the dynamically
enforced formal accesses within a function. These summaries will be
used by a new AccessEnforcementOpts pass to locally fold access scopes
and remove dynamic checks based on whole module analysis.
Added new files, MemAccessUtils.h and MemAccessUtils.cpp to house the
new utility. Three functions previously in InstructionUtils.h move
here:
- findAccessedAddressBase
- isPossibleFormalAccessBase
- visitAccessedAddress
Rather than working with SILValues, these routines now work with the
AccessedStorage abstraction. This allows enforcement logic and SIL
pattern recognition to be shared across diagnostics and
optimization. (It's very important for this to be consistent).
The new AccessedStorage utility is a superset of the class that was
local to DiagnoseStaticExclusivity. It exposes the full set of all
recognized kinds of storage. It also represents function arguments as
an index rather that a SILValue. This allows an analysis pass to
compare/merge AccessedStorage results from multiple callee functions,
or more naturally propagate from callee to caller context.
