In some instances, some instructions, like ref_element_addr, can be hoisted outside of loops even if they are not guaranteed to be executed.
We currently don’t support that / bail. We only try to do so / do further analysis only for begin_access because they are extremely heavy.
However, we need to support hosting of ref_element_addr in that case, if it does not have a loop dependent operand, in order to be able to hoist begin_access instructions in some benchmarks.
Initial local testing shows that this PR, when we enable exclusivity, improves the performance of a certain internal benchmark by over 40%
See rdar://problem/43623829
We can’t hoist everything that is hoist-able
The canHoist method does not do all the required analysis
Some of the work is done at COW Array Opt
TODO: Refactor COW Array Opt + canHoist - radar 41601468
All this does is automate the creation of the ${DIRNAME}_SOURCES variables that we already create and allows for the author to avoid having to prefix with the directory name, i.e.:
set(FOOBAR_SOURCES
FooBar/Source.cpp
PARENT_SCOPE)
=>
silopt_register_sources(
Source.cpp)
Much easier and cleaner to read. I put the code that implements this in the
CMakeLists.txt file just for the SILOptimizer.
Major refactoring + tuning of LICM. Includes:
Support for hosting more array semantic calls
Remove restrictions for sinking instructions
Add support for hoisting and sinking instruction pairs (begin and end accesses)
Testing with Exclusivity enabled on a couple of benchmarks shows:
ReversedArray 7x improvement
StringWalk 2.6x improvement
Removing this optimization from SIL: It is not worth the extra code complexity and compilation time.
More in-depth explanation for the reasoning behind my decision:
1) What is being done there is obviously not LICM (more below) - even if it is useful it should be its own separate optimization
2) The regression that caused us to add this code is no longer there in most cases - 10% in only one specific corner-case
3) Even if the regression was still there, this is an extremely specific code pattern that we are pattern-matching against. Said pattern would be hard to find in any real code.
There is a small code snippet in rdar://17451529 that caused us to add this optimization. Looking at it now we see that the only difference is in loop1 example -
The only difference in SIL level is in loop 1:
%295 = tuple_extract %294 : $(Builtin.Int64, Builtin.Int1), 0
%296 = tuple_extract %294 : $(Builtin.Int64, Builtin.Int1), 1
cond_fail %296 : $Builtin.Int1
%298 = struct $Int (%295 : $Builtin.Int64)
store %298 to %6 : $*Int
%300 = builtin "cmp_eq_Int64"(%292 : $Builtin.Int64, %16 : $Builtin.Int64) : $Builtin.Int1
cond_br %300, bb1, bb12
The cond_fail instruction in said loop is moved below the store instruction / above the builtin.
Looking at the resulting IR. And how LLVM optimizes it. It is almost the same.
If we look at the assembly code being executed then, before removing this optimization, we have:
LBB0_11:
testq %rcx, %rcx
je LBB0_2
decq %rcx
incq %rax
movq %rax, _$S4main4sum1Sivp(%rip)
jno LBB0_11
After removing it we have:
LBB0_11:
incq %rax
testq %rcx, %rcx
je LBB0_2
decq %rcx
movq %rax, %rdx
incq %rdx
jno LBB0_11
There is no extra load/movq which was mentioned the radar.
Make this a generic analysis so that it can be used to analyze any
kind of function effect.
FunctionSideEffect becomes a trivial specialization of the analysis.
The immediate need for this is to introduce an new
AccessedStorageAnalysis, although I foresee it as a generally very
useful utility. This way, new kinds of function effects can be
computed without adding any complexity or compile time to
FunctionSideEffects. We have the flexibility of computing different
kinds of function effects at different points in the pipeline.
In the case of AccessedStorageAnalysis, it will compute both
FunctionSideEffects and FunctionAccessedStorage in the same pass by
implementing a simple wrapper on top of FunctionEffects.
This cleanup reflects my feeling that nested classes make the code
extremely unreadable unless they are very small and either private or
only used directly via its parent class. It's easier to see how these
classes compose with a flat type system.
In addition to enabling new kinds of function effects analyses, I
think this makes the implementation of side effect analysis easier to
understand by separating concerns.
This is a property of an instruction and should be a member
function of `SILInstruction` and not a free function in
`DebugUtils`. Discussed with Adrian.
* Implement a few silcombine transformations for arrays
- Useless existential_ref <-> class conversions.
- mark_dependence_inst depending on uninteresting instructions.
- release(init_existential_ref(x)) -> release(x) when hasOneUse(x)
- Update COWArrayOpt to handle the new forms generated by this.
these aren't massive performance wins, but do shrink the size of SIL when
dealing with arrays.
* Generalize testcase to work on linux and on mac when checking stdlib is enabled.
This commit is mostly refactoring.
*) Introduce a new OptimizationMode enum and use that in SILOptions and IRGenOptions
*) Allow the optimization mode also be specified for specific SILFunctions. This is not used in this commit yet and thus still a NFC.
Also, fixes a minor bug: we didn’t run mandatory IRGen passes for functions with @_semantics("optimize.sil.never")
This replaces the '[volatile]' flag. Now, class_method and
super_method are only used for vtable dispatch.
The witness_method instruction is still overloaded for use
with both ObjC protocol requirements and Swift protocol
requirements; the next step is to make it only mean the
latter, also using objc_method for ObjC protocol calls.
We need to walk the dominator tree starting at the header and update the
dominator of all nodes outside the loop we hit i.e the dominator tree nodes that
are immediately dominated 'by the loop' instead of only updating dominated exit
blocks.
rdar://34523864
introduce a common superclass, SILNode.
This is in preparation for allowing instructions to have multiple
results. It is also a somewhat more elegant representation for
instructions that have zero results. Instructions that are known
to have exactly one result inherit from a class, SingleValueInstruction,
that subclasses both ValueBase and SILInstruction. Some care must be
taken when working with SILNode pointers and testing for equality;
please see the comment on SILNode for more information.
A number of SIL passes needed to be updated in order to handle this
new distinction between SIL values and SIL instructions.
Note that the SIL parser is now stricter about not trying to assign
a result value from an instruction (like 'return' or 'strong_retain')
that does not produce any.
It is more profitable in most cases to inline the big callee rather than unroll the loop, because unrolling it would create a lot of calls which cannot be further optimized due to increased size of the function containing a loop.
Replace `NameOfType foo = dyn_cast<NameOfType>(bar)` with DRY version `auto foo = dyn_cast<NameOfType>(bar)`.
The DRY auto version is by far the dominant form already used in the repo, so this PR merely brings the exceptional cases (redundant repetition form) in line with the dominant form (auto form).
See the [C++ Core Guidelines](https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#es11-use-auto-to-avoid-redundant-repetition-of-type-names) for a general discussion on why to use `auto` to avoid redundant repetition of type names.
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.
array.append_element(newElement: Element)
array.append_contentsOf(contentsOf newElements: S)
And allow early inlining of them.
Those functions will be needed to optimize Array.append(contentsOf)
Separate formal lowered types from SIL types.
The SIL type of an argument will depend on the SIL module's conventions.
The module conventions are determined by the SIL stage and LangOpts.
Almost NFC, but specialized manglings are broken incidentally as a result of
fixes to the way passes handle book-keeping of aruments. The mangler is fixed in
the subsequent commit.
Otherwise, NFC is intended, but quite possible do to rewriting the logic in many
places.
Most of this involved sprinkling ValueOwnershipKind::Owned in many places. In
some of these places, I am sure I was too cavalier and I expect some of them to
be trivial. The verifier will help me to track those down.
On the other hand, I do expect there to be some places where we are willing to
accept guaranteed+trivial or owned+trivial. In those cases, I am going to
provide an aggregate ValueOwnershipKind that will then tell SILArgument that it
should disambiguate using the type. This will eliminate the ackwardness from
such code.
I am going to use a verifier to fix such cases.
This commit also begins the serialization of ValueOwnershipKind of arguments,
but does not implement parsing of value ownership kinds. That and undef are the
last places that we still use ValueOwnershipKind::Any.
rdar://29791263
Not sure why but this was another "toxic utility method".
Most of the usages fell into one of three categories:
- The base value was always non-null, so we could just call
getCanonicalType() instead, making intent more explicit
- The result was being compared for equality, so we could
skip canonicalization and call isEqual() instead, removing
some boilerplate
- Utterly insane code that made no sense
There were only a couple of legitimate uses, and even there
open-coding the conditional null check made the code clearer.
Also while I'm at it, make the SIL open archetypes tracker
more typesafe by passing around ArchetypeType * instead of
Type and CanType.
We preserve the current behavior of assuming Any ownership always and use
default arguments to hide this change most of the time. There are asserts now in
the SILBasicBlock::{create,replace,insert}{PHI,Function}Argument to ensure that
the people can only create SILFunctionArguments in entry blocks and
SILPHIArguments in non-entry blocks. This will ensure that the code in tree
maintains the API distinction even if we are not using the full distinction in
between the two.
Once the verifier is finished being upstreamed, I am going to audit the
createPHIArgument cases for the proper ownership. This is b/c I will be able to
use the verifier to properly debug the code. At that point, I will also start
serializing/printing/parsing the ownershipkind of SILPHIArguments, but lets take
things one step at a time and move incrementally.
In the process, I also discovered a CSE bug. I am not sure how it ever worked.
Basically we replace an argument with a new argument type but return the uses of
the old argument to refer to the old argument instead of a new argument.
rdar://29671437
For a long time, we have:
1. Created methods on SILArgument that only work on either function arguments or
block arguments.
2. Created code paths in the compiler that only allow for "function"
SILArguments or "block" SILArguments.
This commit refactors SILArgument into two subclasses, SILPHIArgument and
SILFunctionArgument, separates the function and block APIs onto the subclasses
(leaving the common APIs on SILArgument). It also goes through and changes all
places in the compiler that conditionalize on one of the forms of SILArgument to
just use the relevant subclass. This is made easier by the relevant APIs not
being on SILArgument anymore. If you take a quick look through you will see that
the API now expresses a lot more of its intention.
The reason why I am performing this refactoring now is that SILFunctionArguments
have a ValueOwnershipKind defined by the given function's signature. On the
other hand, SILBlockArguments have a stored ValueOwnershipKind. Rather than
store ValueOwnershipKind in both instances and in the function case have a dead
variable, I decided to just bite the bullet and fix this.
rdar://29671437
Changes:
* Terminate all namespaces with the correct closing comment.
* Make sure argument names in comments match the corresponding parameter name.
* Remove redundant get() calls on smart pointers.
* Prefer using "override" or "final" instead of "virtual". Remove "virtual" where appropriate.
