With removing of pinning and with addressors, the pattern matching did not work anymore.
The good thing is that the SIL is now much simpler and we can handle the 2D case without pattern matching at all.
This removes a lot of code from COWArrayOpts.
rdar://problem/43863081
The optimizations now handle the ref_tail_addr instructions for detecting element addresses
(in addition to the array semantics function _getElementAddress).
After _modify for Array subscript lands, we can get rid of _getElementAddress at all.
SIL passes were violating the existing invariant on non-cond-br
critical edges in several places. I fixed the places that I could
find. Wherever there was a post-pass to "clean up" critical edges, I
replaced it with a a call to verification that the critical edges
aren't broken in the first place.
We still need to eliminate critical edges entirely before enabling
ownership SIL.
The client of this interface naturally expects to get back the
incoming phi value. Ignoring dominance and SIL ownership, the incoming
phi value and the block argument should be substitutable.
This method was actually returning the incoming operand for
checked_cast and switch_enum terminators, which is deeply misleading
and has been the source of bugs.
If the client wants to peek though casts, and enums, it should do so
explicitly. getSingleTerminatorOperand[s]() will do just that.
Consider the attached test cases:
We have a begin_access [dynamic] to a global inside of a loop
There’s a nested conflict on said access due to an apply() instruction between the begin and end accesses.
LICM is currently very conservative: If there are any function calls inside of the loop that conflict with begin and end access, we do not hoist out of the loop.
However, if all conflicting applies are “sandwiched” between the begin and end access. So there’s no reason we can’t hoist out of the loop.
See radar rdar://problem/43660965 - this improves some internal benchmarks by over 3X
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.
