This new OSSA invariant simplifies many optimizations because they don't have to take care of the corner case of incomplete lifetimes in dead-end blocks.
The implementation basically consists of these changes:
* add the lifetime completion utility
* add a flag in SILFunction which tells optimization that they need to run the lifetime completion utility
* let all optimizations complete lifetimes if necessary
* enable the ownership verifier to check complete lifetimes
These two new invariants eliminate corner cases which caused bugs if optimization didn't handle them.
Also, it will significantly simplify lifetime completion.
The implementation basically consists of these changes:
* add a flag in SILFunction which tells optimization if they need to take care of infinite loops
* add a utility to break infinite loops
* let all optimizations remove unreachable blocks and break infinite loops if necessary
* add verification to check the new SIL invariants
The new `breakIfniniteLoops` utility breaks infinite loops in the control flow by inserting an "artificial" loop exit to a new dead-end block with an `unreachable`.
It inserts a `cond_br` with a `builtin "infinite_loop_true_condition"`:
```
bb0:
br bb1
bb1:
br bb1 // back-end branch
```
->
```
bb0:
br bb1
bb1:
%1 = builtin "infinite_loop_true_condition"() // always true, but the compiler doesn't know
cond_br %1, bb2, bb3
bb2: // new back-end block
br bb1
bb3: // new dead-end block
unreachable
```
Specialization might create new references to conformances. A
specialized init_existential_ref might now refer to a concrete
conformance.
In Embedded swift protocol witness tables are emitted lazily. Therefore
deserialization of the sil_witness_table becomes mandatory if it is
referenced because we can't rely on it being defined in the originating
module.
rdar://167843592
Implements SE-0460 -- the non-underscored version of @specialized.
It allows to specify "internal" (not abi affecting) specializations.
rdar://150033316
Put AvailabilityRange into its own header with very few dependencies so that it
can be included freely in other headers that need to use it as a complete type.
NFC.
This ended up in creating a lot of Array functions, even if a program didn't use Array at all.
Now, only add specialization attributes if a function is already there.
Otherwise remember the attributes and add them to a function once it is created.
Although I don't plan to bring over new assertions wholesale
into the current qualification branch, it's entirely possible
that various minor changes in main will use the new assertions;
having this basic support in the release branch will simplify that.
(This is why I'm adding the includes as a separate pass from
rewriting the individual assertions)
In order to support lazy typechecking during module emission for modules
containing specialized functions, the computation of generic signatures for
`@_specialized` attributes must be requestified.
Resolves rdar://115569606
MandatoryGenericSpecializer inlines transparent functions that it
specializes.
Now that in OSSA `partial_apply [on_stack]`s are represented as owned
values rather than stack locations, it is possible for their destroys to
violate stack discipline. A direct lowering of the instructions to
non-OSSA would violate stack nesting.
Previously, when inlining during MandatoryGenericSpecializer, it was
assumed that the callee maintained stack discipline. And, when inlining
an OSSA function into a non-OSSA function, OSSA instructions were
lowered directly. The result was that stack discipline would be
violated when directly lowering callees with `partial_apply [on_stack]`s
that violate stack discipline.
Here, when MandatoryGenericSpecializer inlines a specialized generic
function in OSSA form into a function lowered out of OSSA form, stack
nesting is fixed up.
Remove dead `metatype` instructions which only have `debug_value` uses.
We lose debug info for such type variables, but this is a compromise we need to accept to get allocation/lock free code.
rdar://103270882
Add `deletableInstructions()` and `reverseDeletableInstructions()` in SILBasicBlock.
It allows deleting instructions while iterating over all instructions of the block.
This is a replacement for `InstructionDeleter::updatingRange()`.
It's a simpler implementation than the existing `UpdatingListIterator` and `UpdatingInstructionIteratorRegistry`, because it just needs to keep the prev/next pointers for "deleted" instructions instead of the iterator-registration machinery.
It's also safer, because it doesn't require to delete instructions via a specific instance of an InstructionDeleter (which can be missed easily).
In performance-annotated functions optimize the pattern where a partial_apply is immediately applied.
This remove the partial apply and thus avoids an allocation.
Fixes an unnecessary performance violation error.
rdar://95155145
This invalidation kind is used when a compute-effects pass changes function effects.
Also, let optimization passes which don't change effects only invalidate the `FunctionBody` and not `Everything`.
* [SILOptimizer] Add prespecialization for arbitray reference types
* Fix benchmark Package.swift
* Move SimpleArray to utils
* Fix multiple indirect result case
* Remove leftover code from previous attempt
* Fix test after rebase
* Move code to compute type replacements to SpecializedFunction
* Fix ownership when OSSA is enabled
* Fixes after rebase
* Changes after rebasing
* Add feature flag for layout pre-specialization
* Fix pre_specialize-macos.swift
* Add compiler flag to benchmark build
* Fix benchmark SwiftPM flags
Co-routines (called by `begin_apply`) may allocate and therefore it’s important to always inline them.
Also, refactor the code a bit to fix the if-changed-then-return-true logic.
rdar://94833845
The main point of this change is to make sure that a shared function always has a body: both, in the optimizer pipeline and in the swiftmodule file.
This is important because the compiler always needs to emit code for a shared function. Shared functions cannot be referenced from outside the module.
In several corner cases we missed to maintain this invariant which resulted in unresolved-symbol linker errors.
As side-effect of this change we can drop the shared_external SIL linkage and the IsSerializable flag, which simplifies the serialization and linkage concept.
This pass is only used for functions with performance annotations (@_noLocks, @_noAllocation).
It runs in the mandatory pipeline and specializes all function calls in performance-annotated functions and functions which are called from such functions.
In addition, the pass also does some other related optimizations: devirtualization, constant-folding Builtin.canBeClass, inlining of transparent functions and memory access optimizations.
This attribute allows to define a pre-specialized entry point of a
generic function in a library.
The following definition provides a pre-specialized entry point for
`genericFunc(_:)` for the parameter type `Int` that clients of the
library can call.
```
@_specialize(exported: true, where T == Int)
public func genericFunc<T>(_ t: T) { ... }
```
Pre-specializations of internal `@inlinable` functions are allowed.
```
@usableFromInline
internal struct GenericThing<T> {
@_specialize(exported: true, where T == Int)
@inlinable
internal func genericMethod(_ t: T) {
}
}
```
There is syntax to pre-specialize a method from a different module.
```
import ModuleDefiningGenericFunc
@_specialize(exported: true, target: genericFunc(_:), where T == Double)
func prespecialize_genericFunc(_ t: T) { fatalError("dont call") }
```
Specially marked extensions allow for pre-specialization of internal
methods accross module boundries (respecting `@inlinable` and
`@usableFromInline`).
```
import ModuleDefiningGenericThing
public struct Something {}
@_specializeExtension
extension GenericThing {
@_specialize(exported: true, target: genericMethod(_:), where T == Something)
func prespecialize_genericMethod(_ t: T) { fatalError("dont call") }
}
```
rdar://64993425
In all of these cases, we already had a SILFunction and were just grabbing its
SILModule instead of passing it in. So this is just an NFC change.
The reason why I am doing this is so that I can force emit opt-remarks on
functions with the semantics attribute "optremark", so I need to be able to
access the SILFunction in the optimization remark infrastructure.
The idea is that this will let me remove these assertions that were in place to
make sure we were really conservative around specializing ownership code. For me
to remove that I need to be able to actually test out this code (since I think
there are some code paths where this will trigger in other parts of the compiler
now).
So to work out the kinks, I added a flag that allows for the generic specializer
to process ownership code and translated most of the .sil test cases/fixed any
bugs that I found. This hopefully will expose anything that is missing.
NOTE: I have not enabled the generic specializer running in ownership in the
pipeline. This is just a step in that direction by adding tests/etc.
The XXOptUtils.h convention is already established and parallels
the SIL/XXUtils convention.
New:
- InstOptUtils.h
- CFGOptUtils.h
- BasicBlockOptUtils.h
- ValueLifetime.h
Removed:
- Local.h
- Two conflicting CFG.h files
This reorganization is helpful before I introduce more
utilities for block cloning similar to SinkAddressProjections.
Move the control flow utilies out of Local.h, which was an
unreadable, unprincipled mess. Rename it to InstOptUtils.h, and
confine it to small APIs for working with individual instructions.
These are the optimizer's additions to /SIL/InstUtils.h.
Rename CFG.h to CFGOptUtils.h and remove the one in /Analysis. Now
there is only SIL/CFG.h, resolving the naming conflict within the
swift project (this has always been a problem for source tools). Limit
this header to low-level APIs for working with branches and CFG edges.
Add BasicBlockOptUtils.h for block level transforms (it makes me sad
that I can't use BBOptUtils.h, but SIL already has
BasicBlockUtils.h). These are larger APIs for cloning or removing
whole blocks.
With the advent of dynamic_function_ref the actual callee of such a ref
my vary. Optimizations should not assume to know the content of a
function referenced by dynamic_function_ref. Introduce
getReferencedFunctionOrNull which will return null for such function
refs. And getInitialReferencedFunction to return the referenced
function.
Use as appropriate.
rdar://50959798
This disables a bunch of passes when ownership is enabled. This will allow me to
keep transparent functions in ossa and skip most of the performance pipeline without
being touched by passes that have not been updated for ownership.
This is important so that we can in -Onone code import transparent functions and
inline them into other ossa functions (you can't inline from ossa => non-ossa).
To do so this commit does a few different things:
1. I changed SILOptFunctionBuilder to notify the pass manager's logging
functionality when new functions are added to the module and to notify analyses
as well. NOTE: This on purpose does not put the new function on the pass manager
worklist since we do not want to by mistake introduce a large amount of
re-optimizations. Such a thing should be explicit.
2. I eliminated SILModuleTransform::notifyAddFunction. This just performed the
operations from 1. Now that SILOptFunctionBuilder performs this operation for
us, it is not needed.
3. I changed SILFunctionTransform::notifyAddFunction to just add the function to
the passmanager worklist. It does not need to notify the pass manager's logging
or analyses that a new function was added to the module since
SILOptFunctionBuilder now performs that operation. Given its reduced
functionality, I changed the name to addFunctionToPassManagerWorklist(...). The
name is a little long/verbose, but this is a feature since one should think
before getting the pass manager to rerun transforms on a function. Also, giving
it a longer name calls out the operation in the code visually, giving this
operation more prominance when reading code. NOTE: I did the rename using
Xcode's refactoring functionality!
rdar://42301529
I am going to add the code in a bit that does the notifications. I tried to pass
down the builder instead of the pass manager. I also tried not to change the
formatting.
rdar://42301529
Adds a combined API to output both debug message and optimization remarks.
The previously added test partial_specialization_debug.sil ensures that it's an
NFC for debug output.
For now these are underscored attributes, i.e. compiler internal attributes:
@_optimize(speed)
@_optimize(size)
@_optimize(none)
Those attributes override the command-line specified optimization mode for a specific function.
The @_optimize(none) attribute is equivalent to the already existing @_semantics("optimize.sil.never") attribute
At some point, pass definitions were heavily macro-ized. Pass
descriptive names were added in two places. This is not only redundant
but a source of confusion. You could waste a lot of time grepping for
the wrong string. I removed all the getName() overrides which, at
around 90 passes, was a fairly significant amount of code bloat.
Any pass that we want to be able to invoke by name from a tool
(sil-opt) or pipeline plan *should* have unique type name, enum value,
commend-line string, and name string. I removed a comment about the
various inliner passes that contradicted that.
Side note: We should be consistent with the policy that a pass is
identified by its type. We have a couple passes, LICM and CSE, which
currently violate that convention.
Erik Eckstein
Arnold Schwaighofer
Meghana Gupta
Allan Shortlidge
Tim Kientzle
Nate Chandler
Max Desiatov
Josh Soref
Dario Rexin
Andrew Trick
Meghana Gupta
Michael Gottesman
Bob Wilson
Jordan Rose
swift-ci
Adam Nemet