Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[ownership] Implement Interior Pointer handling API for RAUWing addresses #35461

Merged
merged 6 commits into from
Jan 20, 2021

Conversation

gottesmm
Copy link
Contributor

This PR contains 4 commits all in service of one goal: allowing us to eliminate address_to_pointer, pointer_to_address round trips. This is an important problem to solve since the stdlib uses this pattern to reinterpret cast addresses that point into COW containers. Our emission strategy of small scopes generally makes it so that when we get the underlying address, we create a borrow scope, then address_to_pointer a pointer derived from a ref_element_addr. Later we then cast the pointer to the new address type and then use it for whatever purpose the author intended.

It is important that we be able to convert these to addresses for memory promotion/alias analysis/etc on the stdlib, so this PR introduces a new utility that if necessary will extend the lifetime of the base value that the interior pointer operand is derived from and produce a new access path into the base value that is valid over all uses of the new value. Later passes (CopyPropagation/SemanticARCOpts) will then clean up the ARC and intervening passes can now actually use these addresses without being stymied by the escaping nature of pointer_to_address.


Now in terms of the 4 commits themselves, lets go through each:

  1. The first is hiding simplifyInstruction and changing all callers of it to use a simplifyAndReplace variant instead. Already there was a hidden assumption that simplifyInstruction's result would be passed to replaceAllUsesAndErase, this just eliminates that bug. It also prepares the
  2. OwnershipFixupContext has grown a bit and I want to convert it back to a more context struct that various utilities use. So, I extracted the RAUW methods onto a new helper class called OwnershipRAUWHelper that composes with OwnershipFixupContext.
  3. In this PR, I implemented the actual RAUW API and got everything in place.
  4. In this final API, I let InstSimplify fold identity address_to_pointer/pointer_to_address using this new utility. I also added a bunch of tests that exercise the new API with various CFG patterns (diamonds, loops, etc). Once this lands, I am going to use this to implement other optimizations like this (e.x.: non-identity reinterpret casts).

@gottesmm gottesmm requested review from atrick and meg-gupta January 16, 2021 23:52
@gottesmm
Copy link
Contributor Author

@swift-ci test

@gottesmm gottesmm force-pushed the ossa-interior-ptr-fixup branch from 08a758e to fb994e9 Compare January 17, 2021 00:00
@gottesmm
Copy link
Contributor Author

@swift-ci test

@swift-ci
Copy link
Contributor

Build failed
Swift Test OS X Platform
Git Sha - fb994e99da151c3bbcd6c11cf7f5b4b42c6b4ed2

@swift-ci
Copy link
Contributor

Build failed
Swift Test Linux Platform
Git Sha - fb994e99da151c3bbcd6c11cf7f5b4b42c6b4ed2

@gottesmm gottesmm force-pushed the ossa-interior-ptr-fixup branch from fb994e9 to 70091cf Compare January 17, 2021 04:02
@gottesmm
Copy link
Contributor Author

@swift-ci test

@swift-ci
Copy link
Contributor

Build failed
Swift Test Linux Platform
Git Sha - 70091cf0820d3454f99d8e975402d5ca467aa874

@swift-ci
Copy link
Contributor

Build failed
Swift Test OS X Platform
Git Sha - 70091cf0820d3454f99d8e975402d5ca467aa874

///
/// This will not clone ref_element_addr or ref_tail_addr because those aren't
/// part of the access chain.
class InteriorPointerAddressRebaseUseDefChainCloner
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

// are within our BorrowedValue's scope. If so, we clear the extra state we
// were tracking (the interior pointer/oldValue's transitive uses), so we
// perform just a normal RAUW (without inserting the copy) when we RAUW.
auto accessPathWithBase = AccessPathWithBase::compute(newValue);
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@atrick This is another case where I am nervous if I did this correctly (I just haven't played with the AccessPath APIs that much). One reason why I am unsure is due to the CSE test failure and some weird behavior I saw around this API and not stopping at pointer_to_address. I am going to dig in and try to understand what's going on.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Based on the surrounding code, this looks like a correct and appropriate use of AccessPathWithBase. I haven't proven to my self yet that replaceAddress is complete yet.

replaceAllSimplifiedUsesAndErase(svi, S, callbacks);
changed = true;
callbacks.resetHadCallbackInvocation();
simplifyAndReplaceAllSimplifiedUsesAndErase(svi, callbacks);
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am going to take a quick look around our usage of deBlocks here. I think the right behavior is to not optimize if we aren't passed a real deBlock and we need one.

@gottesmm
Copy link
Contributor Author

@swift-ci test

1 similar comment
@gottesmm
Copy link
Contributor Author

@swift-ci test

@swift-ci
Copy link
Contributor

Build failed
Swift Test OS X Platform
Git Sha - d6928cd7a9a295fc02e763d0748a16b0ee2fe97b

@swift-ci
Copy link
Contributor

Build failed
Swift Test Linux Platform
Git Sha - d6928cd7a9a295fc02e763d0748a16b0ee2fe97b

Copy link
Contributor

@atrick atrick left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks like it's on the right track. There are a lot of abstractions to grok before I can reason about what's happening, so I'll need to make another pass later to fully understand.

InteriorPointerAddressRebaseUseDefChainCloner looks like overkill as it is currently written. It's essentially AccessUseDefChainCloner with a new base address.

My only concern is whether it's always valid to clone a storage cast. Currently, that includes begin_borrow which is just wrong. But I'm also worried about the type casts in your case.

///
/// NOTE: When OSSA is enabled this API assumes OSSA is properly formed and will
/// insert compensating instructions.
SILBasicBlock::iterator simplifyAndReplaceAllSimplifiedUsesAndErase(
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

simplifyAndEraseInstruction is an unambiguous name.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

good idea!

// are within our BorrowedValue's scope. If so, we clear the extra state we
// were tracking (the interior pointer/oldValue's transitive uses), so we
// perform just a normal RAUW (without inserting the copy) when we RAUW.
auto accessPathWithBase = AccessPathWithBase::compute(newValue);
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Based on the surrounding code, this looks like a correct and appropriate use of AccessPathWithBase. I haven't proven to my self yet that replaceAddress is complete yet.

bool InteriorPointerOperand::getImplicitUses(
SmallVectorImpl<Operand *> &foundUses,
bool InteriorPointerOperand::getImplicitUsesForAddress(
SILValue projectedAddress, SmallVectorImpl<Operand *> &foundUses,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not sure what this method is doing or what an "implicit use" is. Think it's looking at the transitive uses of address to find the lifetime extent of the interior pointer? Maybe it should be called something like findTransitiveInteriorPointerUses with a comment to explain that it defines the maximum extent of the interior pointer's lifetime, which must be within the root object's borrow scope.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm also not sure why it's recording all uses even those that are transitively followed

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You are right. Let me fix that. This is basically the way that the optimizer takes an address and finds all of its uses exhaustively. I think it should be rewritten based off of the AccessUseDefChainVisitor IMO.

@gottesmm
Copy link
Contributor Author

@swift-ci test

…dReplaceAllSimplifiedUsesAndErase.

Currently all of these places in the code base perform simplifyInstruction and
then a replaceAllSimplifiedUsesAndErase(...). This is a bad pattern since:

1. simplifyInstruction assumes its result will be passed to
   replaceAllSimplifiedUsesAndErase. So by leaving these as separate things, we
   allow for users to pointlessly make this mistake.

2. I am going to implement in a subsequent commit a utility that lifetime
   extends interior pointer bases when replacing an address with an interior
   pointer derived address. To do this efficiently, I want to reuse state I
   compute during simplifyInstruction during the actual RAUW meaning that if the
   two operations are split, that is difficult without extending the API. So by
   removing this, I can make the transform and eliminate mistakes at the same
   time.
…ead put its RAUW functionality on OwnershipRAUWHelper.

The reason why I am doing this is that I am building up more utilities based on
passing around this struct of context that do not want it for RAUWing
purposes. So it makes sense on a helper (OwnershipRAUWHelper) that composes with
its state.

Just a refactor, should be NFC.
…UsesFixingInteriorPointerOwnership.

In OSSA, we enforce that addresses from interior pointer instructions are scoped
within a borrow scope. This means that it is invalid to use such an address
outside of its parent borrow scope and as a result one can not just RAUW an
address value by a dominating address value since the latter may be invalid at
the former. I foresee that I am going to have to solve this problem and so I
decided to write this API to handle the vast majority of cases.

The way this API works is that it:

1. Computes an access path with base for the new value. If we do not have a base
value and a valid access path with root, we bail.

2. Then we check if our base value is the result of an interior pointer
instruction. If it isn't, we are immediately done and can RAUW without further
delay.

3. If we do have an interior pointer instruction, we see if the immediate
guaranteed value we projected from has a single borrow introducer value. If not,
we bail. I think this is reasonable since with time, all guaranteed values will
always only have a single borrow introducing value (once struct, tuple,
destructure_struct, destructure_tuple become reborrows).

4. Then we gather up all inner uses of our access path. If for some reason that
fails, we bail.

5. Then we see if all of those uses are within our borrow scope. If so, we can
RAUW without any further worry.

6. Otherwise, we perform a copy+borrow of our interior pointer's operand value
at the interior pointer, create a copy of the interior pointer instruction upon
this new borrow and then RAUW oldValue with that instead. By construction all
uses of oldValue will be within this new interior pointer scope.
…ity transforms using new interior pointer handling utility.

Btw for those curious, the reason why this optimization is important is that the
stdlib often times performs reinterpret casts using address to pointer, pointer
to address to perform the case. So we need to be able to reliably eliminate
these. Since the underlying base object's liveness is already what provides the
liveness to the underlying address, our approach of treating this as a lifetime
extension requiring pattern makes sense since we are adding information into the
IR by canonicalizing these escapes to be normal address operations.

NOTE: In this commit, we only handle the identity transform. In a subsequent
commit, I am going to hit the non-identity transform that is handled by
SILCombine.

Also, I added some specific more general OSSA RAUW tests for this case to
ossa_rauw_tests using this functionality in a more exhaustive way that would be
in appropriate in sil_combine_ossa.sil (since I am stress testing this specific
piece of code).
…passed a non-null deadEndBlocks.

I am trying to be more careful about this rather than letting someone make this
mistake in the future. I also added some comments and a DeadEndBlocks instance
to TempRValueElimination so that it gets full simplifications in OSSA.
…resses rooted in pointer_to_address.

The reason why is that addresses from pointer_to_address never have transitive
interior pointer constraints from where ever the pointer originally came
from. This is the issue that was causing a CSE test to fail, so I added a test
to ossa_rauw_test that works this code path.
@gottesmm gottesmm force-pushed the ossa-interior-ptr-fixup branch from d6928cd to e4e1689 Compare January 18, 2021 04:08
@gottesmm
Copy link
Contributor Author

@swift-ci test

@@ -19,6 +19,7 @@
#ifndef SWIFT_SILOPTIMIZER_UTILS_OWNERSHIPOPTUTILS_H
#define SWIFT_SILOPTIMIZER_UTILS_OWNERSHIPOPTUTILS_H

#include "swift/SIL/BasicBlockUtils.h"

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

  • is not allowed

@gottesmm
Copy link
Contributor Author

@atrick I implemented InteriorPointerAddressRebaseUseDefChainCloner since I couldn't figure out how to extend the code in tree to handle this case. If you can show me how to do this, I would be happy to eliminate it.

@gottesmm
Copy link
Contributor Author

I talked with @atrick, he is going to do the additional review he wanted post-commit.

@gottesmm gottesmm merged commit 2243ffe into swiftlang:main Jan 20, 2021
@gottesmm gottesmm deleted the ossa-interior-ptr-fixup branch January 20, 2021 17:53
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants