| //===--------- CopyPropagation.cpp - Remove redundant SSA copies. ---------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// SSA Copy propagation pass to remove unnecessary copy_value and destroy_value |
| /// instructions. |
| /// |
| /// Because this algorithm rewrites copies and destroys without attempting |
| /// to balance the retain count, it is only sound for ownership-SSA. |
| /// |
| /// [WIP] This complements -enable-sil-opaque-values. It is not yet enabled by |
| /// default. It can be enabled once the ownership properties, currently |
| /// specified as helpers at the top of this file, are formalized via a central |
| /// API. |
| /// |
| /// The pass has four steps: |
| /// |
| /// 1. Find SSA defs that have been copied. |
| /// |
| /// Then, separately, for each copied def, perform steps 2-4: |
| /// |
| /// 2. Compute "pruned" liveness of the def and its copies, ignoring original |
| /// destroys. |
| /// |
| /// 3. Find the SSA def's final destroy points based on its pruned liveness. |
| /// |
| /// 4. Rewrite the def's original copies and destroys, inserting new copies |
| /// where needed. |
| /// |
| /// The state used by this pass is encapsulated in CopyPropagationState, simply |
| /// refered to as `pass`: |
| /// |
| /// - Step 1 initializes `pass.currDef`. |
| /// |
| /// - Step 2 initializes `pass.liveness`. |
| /// |
| /// - Step 3 initializes `pass.destroys` and inserts destroy_value instructions. |
| /// |
| /// - Step 4 deletes original copies and destroys and inserts new copies. |
| /// |
| /// Example #1: Handle consuming and nonconsuming uses. |
| /// |
| /// bb0(%arg : @owned $T, %addr : @trivial $*T): |
| /// %copy = copy_value %arg : $T |
| /// debug_value %copy : $T |
| /// store %copy to [init] %addr : $*T |
| /// debug_value %arg : $T |
| /// debug_value_addr %addr : $*T |
| /// destroy_value %arg : $T |
| /// |
| /// Will be transformed to: |
| /// |
| /// bb0(%arg : @owned $T, %addr : @trivial $*T): |
| /// (The original copy is deleted.) |
| /// debug_value %arg : $T |
| /// (A new copy_value is inserted before the consuming store.) |
| /// %copy = copy_value %arg : $T |
| /// store %copy to [init] %addr : $*T |
| /// (The non-consuming use now uses the original value.) |
| /// debug_value %arg : $T |
| /// (A new destroy is inserted after the last use.) |
| /// destroy_value %arg : $T |
| /// debug_value_addr %addr : $*T |
| /// (The original destroy is deleted.) |
| /// |
| /// Example #2: Handle control flow. |
| /// |
| /// bb0(%arg : @owned $T): |
| /// cond_br %_, bb1, bxb2 |
| /// |
| /// bb1: |
| /// debug_value %arg : $T |
| /// %copy = copy_value %arg : $T |
| /// destroy_value %copy : $T |
| /// br bb2 |
| /// |
| /// bb2: |
| /// destroy_value %arg : $T |
| /// |
| /// Will be transformed to: |
| /// |
| /// bb0(%arg : @owned $T, %addr : @trivial $*T, %z : @trivial $Builtin.Int1): |
| /// cond_br %z, bb1, bb3 |
| /// |
| /// bb1: |
| /// (The critical edge is split.) |
| /// destroy_value %arg : $T |
| /// br bb2 |
| /// |
| /// bb3: |
| /// (The original copy is deleted.) |
| /// debug_value %arg : $T |
| /// destroy_value %arg : $T |
| /// br bb2 |
| /// |
| /// bb2: |
| /// (The original destroy is deleted.) |
| /// |
| /// FIXME: When we ban critical edges in SIL, this pass does not need to |
| /// invalidate any CFG analyses. |
| /// |
| /// FIXME: SILGen currently emits spurious borrow scopes which block |
| /// elimination of copies within a scope. |
| /// |
| /// TODO: Possibly extend this algorithm to better handle aggregates. If |
| /// ownership SIL consistently uses a `destructure` operation to split |
| /// aggregates, then the current scalar algorithm should work |
| /// naturally. However, if we instead need to handle borrow scopes, then this |
| /// becomes much harder. We would need a DI-style tracker to track the uses of a |
| /// particular copied def. The single boolean "live" state would be replaced |
| /// with a bitvector that tracks each tuple element. |
| /// |
| /// TODO: Cleanup the resulting SIL. Delete instructions with no side effects |
| /// that produce values which are immediately destroyed after copy propagation. |
| /// ===----------------------------------------------------------------------=== |
| |
| #define DEBUG_TYPE "copy-propagation" |
| #include "swift/SIL/InstructionUtils.h" |
| #include "swift/SIL/Projection.h" |
| #include "swift/SILOptimizer/PassManager/Passes.h" |
| #include "swift/SILOptimizer/PassManager/Transforms.h" |
| #include "swift/SILOptimizer/Utils/CFGOptUtils.h" |
| #include "swift/SILOptimizer/Utils/IndexTrie.h" |
| #include "swift/SILOptimizer/Utils/InstOptUtils.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/Statistic.h" |
| |
| using namespace swift; |
| using llvm::DenseMap; |
| using llvm::DenseSet; |
| using llvm::SmallSetVector; |
| |
| STATISTIC(NumCopiesEliminated, "number of copy_value instructions removed"); |
| STATISTIC(NumDestroysEliminated, |
| "number of destroy_value instructions removed"); |
| STATISTIC(NumCopiesGenerated, "number of copy_value instructions created"); |
| STATISTIC(NumDestroysGenerated, "number of destroy_value instructions created"); |
| STATISTIC(NumUnknownUsers, "number of functions with unknown users"); |
| |
| //===----------------------------------------------------------------------===// |
| // Ownership Abstraction. |
| // |
| // FIXME: These helpers are only defined in this pass for prototyping. After |
| // bootstrapping, they should be moved to a central ownership API (shared by |
| // SILOwnershipVerifier, etc.). |
| // |
| // Categories of owned value users. (U1-U2 apply to any value, O3-O5 only apply |
| // to owned values). |
| // |
| // U1. Use the value instantaneously (copy_value, @guaranteed). |
| // |
| // U2. Escape the nontrivial contents of the value (ref_to_unowned, |
| // unchecked_trivial_bitcast). |
| // |
| // O3. Propagate the value without consuming it (mark_dependence, begin_borrow). |
| // |
| // O4. Consume the value immediately (store, destroy, @owned, destructure). |
| // |
| // O5. Consume the value indirectly via a move (tuple, struct). |
| // ===---------------------------------------------------------------------===// |
| |
| // TODO: Figure out how to handle these cases if possible. |
| static bool isUnknownUse(Operand *use) { |
| switch (use->getUser()->getKind()) { |
| default: |
| return false; |
| // FIXME: (Category O3) mark_dependence requires recursion to find all |
| // uses. It should be replaced by begin/end dependence. |
| case SILInstructionKind::MarkDependenceInst: // Dependent |
| // FIXME: (Category O3) ref_tail_addr should require a borrow because it |
| // doesn't rely on fix_lifetime like other escaping instructions. |
| case SILInstructionKind::RefTailAddrInst: |
| // FIXME: (Category O3) dynamic_method_br seems to capture self, presumably |
| // propagating lifetime. This should probably borrow self, then be treated |
| // like mark_dependence. |
| case SILInstructionKind::DynamicMethodBranchInst: |
| // FIXME: (Category O3) The ownership verifier says project_box can accept an |
| // owned value as a normal use, but it projects the address. That's either an |
| // ownership bug or a special case. |
| case SILInstructionKind::ProjectBoxInst: |
| case SILInstructionKind::ProjectExistentialBoxInst: |
| // FIXME: (Category O3) The ownership verifier says open_existential_box can |
| // accept an owned value as a normal use, but it projects an address. |
| case SILInstructionKind::OpenExistentialBoxInst: |
| // Unmanaged operations hopefully don't apply to the same value as CopyValue? |
| case SILInstructionKind::UnmanagedRetainValueInst: |
| case SILInstructionKind::UnmanagedReleaseValueInst: |
| case SILInstructionKind::UnmanagedAutoreleaseValueInst: |
| return true; |
| } |
| } |
| |
| /// Return true if the given owned operand is consumed by the given call. |
| static bool isAppliedArgConsumed(ApplySite apply, Operand *oper) { |
| ParameterConvention paramConv; |
| if (oper->get() == apply.getCallee()) { |
| assert(oper->getOperandNumber() == 0 |
| && "function can't be passed to itself"); |
| paramConv = apply.getSubstCalleeType()->getCalleeConvention(); |
| } else { |
| unsigned argIndex = apply.getCalleeArgIndex(*oper); |
| paramConv = apply.getSubstCalleeConv() |
| .getParamInfoForSILArg(argIndex) |
| .getConvention(); |
| } |
| return isConsumedParameter(paramConv); |
| } |
| |
| /// Return true if the given builtin consumes its operand. |
| static bool isBuiltinArgConsumed(BuiltinInst *BI) { |
| const BuiltinInfo &Builtin = BI->getBuiltinInfo(); |
| switch (Builtin.ID) { |
| default: |
| llvm_unreachable("Unexpected Builtin with owned value operand."); |
| // Extend lifetime without consuming. |
| case BuiltinValueKind::ErrorInMain: |
| case BuiltinValueKind::UnexpectedError: |
| case BuiltinValueKind::WillThrow: |
| return false; |
| // UnsafeGuaranteed moves the value, which will later be destroyed. |
| case BuiltinValueKind::UnsafeGuaranteed: |
| return true; |
| } |
| } |
| |
| /// Return true if the given operand is consumed by its user. |
| /// |
| /// TODO: Review the semantics of operations that extend the lifetime *without* |
| /// propagating the value. Ideally, that never happens without borrowing first. |
| static bool isConsuming(Operand *use) { |
| auto *user = use->getUser(); |
| if (isa<ApplySite>(user)) |
| return isAppliedArgConsumed(ApplySite(user), use); |
| |
| if (auto *BI = dyn_cast<BuiltinInst>(user)) |
| return isBuiltinArgConsumed(BI); |
| |
| switch (user->getKind()) { |
| default: |
| llvm::dbgs() << *user; |
| llvm_unreachable("Unexpected use of a loadable owned value."); |
| |
| // Consume the value. |
| case SILInstructionKind::AutoreleaseValueInst: |
| case SILInstructionKind::DeallocBoxInst: |
| case SILInstructionKind::DeallocExistentialBoxInst: |
| case SILInstructionKind::DeallocRefInst: |
| case SILInstructionKind::DeinitExistentialValueInst: |
| case SILInstructionKind::DestroyValueInst: |
| case SILInstructionKind::EndLifetimeInst: |
| case SILInstructionKind::InitExistentialRefInst: |
| case SILInstructionKind::InitExistentialValueInst: |
| case SILInstructionKind::KeyPathInst: |
| case SILInstructionKind::ReleaseValueInst: |
| case SILInstructionKind::ReleaseValueAddrInst: |
| case SILInstructionKind::StoreInst: |
| case SILInstructionKind::StrongReleaseInst: |
| case SILInstructionKind::UnownedReleaseInst: |
| case SILInstructionKind::UnconditionalCheckedCastValueInst: |
| return true; |
| |
| // Terminators must consume their owned values. |
| case SILInstructionKind::BranchInst: |
| case SILInstructionKind::CheckedCastBranchInst: |
| case SILInstructionKind::CheckedCastValueBranchInst: |
| case SILInstructionKind::CondBranchInst: |
| case SILInstructionKind::ReturnInst: |
| case SILInstructionKind::ThrowInst: |
| return true; |
| |
| case SILInstructionKind::DeallocPartialRefInst: |
| return cast<DeallocPartialRefInst>(user)->getInstance() == use->get(); |
| |
| // Move the value. |
| case SILInstructionKind::TupleInst: |
| case SILInstructionKind::StructInst: |
| case SILInstructionKind::ObjectInst: |
| case SILInstructionKind::EnumInst: |
| case SILInstructionKind::OpenExistentialRefInst: |
| case SILInstructionKind::UpcastInst: |
| case SILInstructionKind::UncheckedRefCastInst: |
| case SILInstructionKind::ConvertFunctionInst: |
| case SILInstructionKind::RefToBridgeObjectInst: |
| case SILInstructionKind::BridgeObjectToRefInst: |
| case SILInstructionKind::UnconditionalCheckedCastInst: |
| case SILInstructionKind::MarkUninitializedInst: |
| case SILInstructionKind::UncheckedEnumDataInst: |
| case SILInstructionKind::DestructureStructInst: |
| case SILInstructionKind::DestructureTupleInst: |
| return true; |
| |
| // BeginBorrow should already be skipped. |
| // EndBorrow extends the lifetime like a normal use. |
| case SILInstructionKind::EndBorrowInst: |
| return false; |
| |
| // Extend the lifetime without borrowing, propagating, or destroying it. |
| case SILInstructionKind::BridgeObjectToWordInst: |
| case SILInstructionKind::ClassMethodInst: |
| case SILInstructionKind::CopyBlockInst: |
| case SILInstructionKind::CopyValueInst: |
| case SILInstructionKind::DebugValueInst: |
| case SILInstructionKind::ExistentialMetatypeInst: |
| case SILInstructionKind::FixLifetimeInst: |
| case SILInstructionKind::SelectEnumInst: |
| case SILInstructionKind::SetDeallocatingInst: |
| case SILInstructionKind::StoreWeakInst: |
| case SILInstructionKind::ValueMetatypeInst: |
| return false; |
| |
| // Escape the value. The lifetime must already be enforced via something like |
| // fix_lifetime. |
| case SILInstructionKind::RefToRawPointerInst: |
| case SILInstructionKind::RefToUnmanagedInst: |
| case SILInstructionKind::RefToUnownedInst: |
| case SILInstructionKind::UncheckedBitwiseCastInst: |
| case SILInstructionKind::UncheckedTrivialBitCastInst: |
| return false; |
| |
| // Dynamic dispatch without capturing self. |
| case SILInstructionKind::ObjCMethodInst: |
| case SILInstructionKind::ObjCSuperMethodInst: |
| case SILInstructionKind::SuperMethodInst: |
| case SILInstructionKind::WitnessMethodInst: |
| return false; |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CopyPropagationState: shared state for the pass's analysis and transforms. |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| /// LiveWithin blocks have at least one use and/or def within the block, but are |
| /// not LiveOut. |
| /// |
| /// LiveOut blocks are live on at least one successor path. |
| /// |
| /// Dead blocks are either outside of the def's pruned liveness region, or they |
| /// have not yet been discovered by the liveness computation. |
| enum IsLive_t { LiveWithin, LiveOut, Dead }; |
| |
| /// Liveness information, which is produced by step #2, computeLiveness, and |
| /// consumed by step #3, findOrInsertDestroys. |
| class LivenessInfo { |
| // Map of all blocks in which current def is live. True if it is also liveout. |
| DenseMap<SILBasicBlock *, bool> liveBlocks; |
| // Set of all "interesting" users in this def's live range and whether their |
| // used value is consumed. (Non-consuming uses within a block that is already |
| // known to be live are uninteresting.) |
| DenseMap<SILInstruction *, bool> users; |
| // Original points in the CFG where the current value was consumed or |
| // destroyed. |
| typedef SmallSetVector<SILBasicBlock *, 8> BlockSetVec; |
| BlockSetVec originalDestroyBlocks; |
| |
| public: |
| bool empty() { |
| assert(!liveBlocks.empty() || users.empty()); |
| return liveBlocks.empty(); |
| } |
| |
| void clear() { |
| liveBlocks.clear(); |
| users.clear(); |
| originalDestroyBlocks.clear(); |
| } |
| |
| IsLive_t isBlockLive(SILBasicBlock *bb) const { |
| auto liveBlockIter = liveBlocks.find(bb); |
| if (liveBlockIter == liveBlocks.end()) |
| return Dead; |
| return liveBlockIter->second ? LiveOut : LiveWithin; |
| } |
| |
| void markBlockLive(SILBasicBlock *bb, IsLive_t isLive) { |
| assert(isLive != Dead && "erasing live blocks isn't implemented."); |
| liveBlocks[bb] = (isLive == LiveOut); |
| } |
| |
| // Return a valid result if the given user was identified as an interesting |
| // use of the current def. Returns true if the interesting use consumes the |
| // current def. |
| Optional<bool> isConsumingUser(SILInstruction *user) const { |
| auto useIter = users.find(user); |
| if (useIter == users.end()) |
| return None; |
| return useIter->second; |
| } |
| |
| // Record the user of this operand in the set of interesting users. |
| // |
| // Note that a user may use the current value from multiple operands. If any |
| // of the uses are non-consuming, then we must consider the use itself |
| // non-consuming; it cannot be a final destroy point because the value of the |
| // non-consuming operand must be kept alive until the end of the |
| // user. Consider a call that takes the same value using different |
| // conventions: |
| // |
| // apply %f(%val, %val) : $(@guaranteed, @owned) -> () |
| // |
| // This call cannot be allowed to destroy %val. |
| void recordUser(Operand *use) { |
| bool consume = isConsuming(use); |
| auto iterAndSuccess = users.try_emplace(use->getUser(), consume); |
| if (!iterAndSuccess.second) |
| iterAndSuccess.first->second &= consume; |
| } |
| |
| void recordOriginalDestroy(Operand *use) { |
| originalDestroyBlocks.insert(use->getUser()->getParent()); |
| } |
| |
| iterator_range<BlockSetVec::const_iterator> |
| getOriginalDestroyBlocks() const { |
| return originalDestroyBlocks; |
| } |
| }; |
| |
| /// Information about final destroy points, which is produced by step #3, |
| /// findOrInsertDestroys, and consumed by step #4, rewriteCopies. |
| /// |
| /// This remains valid during copy rewriting. The only instructions referenced |
| /// are destroys that cannot be deleted. |
| /// |
| /// For non-owned values, this remains empty. |
| class DestroyInfo { |
| // Map blocks that contain a final destroy to the destroying instruction. |
| DenseMap<SILBasicBlock *, SILInstruction *> finalBlockDestroys; |
| |
| public: |
| bool empty() const { return finalBlockDestroys.empty(); } |
| |
| void clear() { finalBlockDestroys.clear(); } |
| |
| bool hasFinalDestroy(SILBasicBlock *bb) const { |
| return finalBlockDestroys.count(bb); |
| } |
| |
| // Return true if this instruction is marked as a final destroy point of the |
| // current def's live range. A destroy can only be claimed once because |
| // instructions like `tuple` can consume the same value via multiple operands. |
| bool claimDestroy(SILInstruction *inst) { |
| auto destroyPos = finalBlockDestroys.find(inst->getParent()); |
| if (destroyPos != finalBlockDestroys.end() && destroyPos->second == inst) { |
| finalBlockDestroys.erase(destroyPos); |
| return true; |
| } |
| return false; |
| } |
| |
| void recordFinalDestroy(SILInstruction *inst) { |
| finalBlockDestroys[inst->getParent()] = inst; |
| } |
| |
| void invalidateFinalDestroy(SILInstruction *inst) { |
| finalBlockDestroys[inst->getParent()] = inst; |
| } |
| }; |
| |
| /// This pass' shared state. |
| struct CopyPropagationState { |
| SILFunction *F; |
| |
| // Per-function invalidation state. |
| unsigned invalidation; |
| |
| // Current copied def for which this state describes the liveness. |
| SILValue currDef; |
| |
| // computeLiveness result. |
| LivenessInfo liveness; |
| |
| // findOrInsertDestroys result. |
| DestroyInfo destroys; |
| |
| CopyPropagationState(SILFunction *F) |
| : F(F), invalidation(SILAnalysis::InvalidationKind::Nothing) {} |
| |
| bool isValueOwned() const { |
| return currDef.getOwnershipKind() == ValueOwnershipKind::Owned; |
| } |
| |
| void markInvalid(SILAnalysis::InvalidationKind kind) { |
| invalidation |= (unsigned)kind; |
| } |
| |
| void resetDef(SILValue def) { |
| // Do not clear invalidation. It accumulates for an entire function before |
| // the PassManager is notified. |
| liveness.clear(); |
| destroys.clear(); |
| currDef = def; |
| } |
| }; |
| } // namespace |
| |
| //===----------------------------------------------------------------------===// |
| // Step 2. Discover "pruned" liveness for a copied def, ignoring copies and |
| // destroys. |
| // |
| // Generate pass.liveness. |
| // - marks blocks as LiveOut or LiveWithin. |
| // - records users that may become the last user on that path. |
| // - records blocks in which currDef may be destroyed. |
| // |
| // TODO: Make sure all dependencies are accounted for (mark_dependence, |
| // ref_element_addr, project_box?). We should have an ownership API so that the |
| // pass doesn't require any special knowledge of value dependencies. |
| //===----------------------------------------------------------------------===// |
| |
| /// Mark blocks live during a reverse CFG traversal from one specific block |
| /// containing a user. |
| static void computeUseBlockLiveness(SILBasicBlock *userBB, |
| CopyPropagationState &pass) { |
| |
| // If we are visiting this block, then it is not already LiveOut. Mark it |
| // LiveWithin to indicate a liveness boundary within the block. |
| pass.liveness.markBlockLive(userBB, LiveWithin); |
| |
| SmallVector<SILBasicBlock *, 8> predBBWorklist({userBB}); |
| while (!predBBWorklist.empty()) { |
| SILBasicBlock *bb = predBBWorklist.pop_back_val(); |
| // The popped `bb` is live; mark all its predecessors LiveOut. |
| // pass.currDef was already marked LiveWithin, which terminates traversal. |
| for (auto *predBB : bb->getPredecessorBlocks()) { |
| switch (pass.liveness.isBlockLive(predBB)) { |
| case Dead: |
| predBBWorklist.push_back(predBB); |
| LLVM_FALLTHROUGH; |
| case LiveWithin: |
| pass.liveness.markBlockLive(predBB, LiveOut); |
| break; |
| case LiveOut: |
| break; |
| } |
| } |
| } |
| } |
| |
| /// Update the current def's liveness based on one specific use operand. |
| /// |
| /// Terminators consume their owned operands, so they are not live out of the |
| /// block. |
| static void computeUseLiveness(Operand *use, CopyPropagationState &pass) { |
| auto *bb = use->getUser()->getParent(); |
| auto isLive = pass.liveness.isBlockLive(bb); |
| switch (isLive) { |
| case LiveOut: |
| // Ignore uses within the pruned liveness. |
| return; |
| case LiveWithin: |
| // Record all uses of blocks on the liveness boundary. Whoever uses this |
| // liveness result determines the instruction-level liveness boundary to be |
| // the last use in the block. |
| pass.liveness.recordUser(use); |
| break; |
| case Dead: { |
| // This use block has not yet been marked live. Mark it and its predecessor |
| // blocks live. |
| computeUseBlockLiveness(bb, pass); |
| // Record all uses of blocks on the liveness boundary. This cannot be |
| // determined until after the `computeUseBlockLiveness` CFG traversal |
| // because a loop may result in this block being LiveOut. |
| if (pass.liveness.isBlockLive(bb) == LiveWithin) |
| pass.liveness.recordUser(use); |
| break; |
| } |
| } |
| } |
| |
| /// Generate pass.liveness. |
| /// Return true if successful. |
| /// |
| /// This finds the "pruned" liveness by recursing through copies and ignoring |
| /// the original destroys. |
| /// |
| /// Assumption: No users occur before 'def' in def's BB because this follows the |
| /// SSA def-use chains without "looking through" any terminators. |
| static bool computeLiveness(CopyPropagationState &pass) { |
| assert(pass.liveness.empty()); |
| |
| SILBasicBlock *defBB = pass.currDef->getParentBlock(); |
| |
| pass.liveness.markBlockLive(defBB, LiveWithin); |
| |
| SmallSetVector<SILValue, 8> defUseWorkList; |
| defUseWorkList.insert(pass.currDef); |
| |
| while (!defUseWorkList.empty()) { |
| SILValue value = defUseWorkList.pop_back_val(); |
| for (Operand *use : value->getUses()) { |
| auto *user = use->getUser(); |
| |
| // Bailout if we cannot yet determine the ownership of a use. |
| if (isUnknownUse(use)) { |
| LLVM_DEBUG(llvm::dbgs() << "Unknown owned value user: "; user->dump()); |
| ++NumUnknownUsers; |
| return false; |
| } |
| // Recurse through copies. |
| if (auto *copy = dyn_cast<CopyValueInst>(user)) { |
| defUseWorkList.insert(copy); |
| continue; |
| } |
| // An entire borrow scope is considered a single use that occurs at the |
| // point of the end_borrow. |
| if (auto *BBI = dyn_cast<BeginBorrowInst>(user)) { |
| for (Operand *use : BBI->getUses()) { |
| if (isa<EndBorrowInst>(use->getUser())) |
| computeUseLiveness(use, pass); |
| } |
| continue; |
| } |
| if (isConsuming(use)) { |
| pass.liveness.recordOriginalDestroy(use); |
| // Destroying a values does not force liveness. |
| if (isa<DestroyValueInst>(user)) |
| continue; |
| } |
| computeUseLiveness(use, pass); |
| } |
| } |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Step 3. Find the destroy points of the current def based on the pruned |
| // liveness computed in Step 2. |
| //===----------------------------------------------------------------------===// |
| |
| /// The liveness boundary is at a CFG edge `predBB` -> `succBB`, meaning that |
| /// `pass.currDef` is live out of at least one other `predBB` successor. |
| /// |
| /// Create and record a final destroy_value at the beginning of `succBB` |
| /// (assuming no critical edges). |
| static void insertDestroyOnCFGEdge(SILBasicBlock *predBB, SILBasicBlock *succBB, |
| CopyPropagationState &pass) { |
| // FIXME: ban critical edges and avoid invalidating CFG analyses. |
| auto *destroyBB = splitIfCriticalEdge(predBB, succBB); |
| if (destroyBB != succBB) |
| pass.markInvalid(SILAnalysis::InvalidationKind::Branches); |
| |
| SILBuilderWithScope B(destroyBB->begin()); |
| auto *DI = B.createDestroyValue(succBB->begin()->getLoc(), pass.currDef); |
| |
| pass.destroys.recordFinalDestroy(DI); |
| |
| ++NumDestroysGenerated; |
| LLVM_DEBUG(llvm::dbgs() << " Destroy on edge "; DI->dump()); |
| |
| pass.markInvalid(SILAnalysis::InvalidationKind::Instructions); |
| } |
| |
| /// This liveness boundary is within a basic block at the given position. |
| /// |
| /// Create a final destroy, immediately after `pos`. |
| static void insertDestroyAtInst(SILBasicBlock::iterator pos, |
| CopyPropagationState &pass) { |
| SILBuilderWithScope B(pos); |
| auto *DI = B.createDestroyValue((*pos).getLoc(), pass.currDef); |
| pass.destroys.recordFinalDestroy(DI); |
| ++NumDestroysGenerated; |
| LLVM_DEBUG(llvm::dbgs() << " Destroy at last use "; DI->dump()); |
| pass.markInvalid(SILAnalysis::InvalidationKind::Instructions); |
| } |
| |
| // The pruned liveness boundary is within the given basic block. Find the |
| // block's last use. If the last use consumes the value, record it as a |
| // destroy. Otherwise, insert a new destroy_value. |
| static void findOrInsertDestroyInBlock(SILBasicBlock *bb, |
| CopyPropagationState &pass) { |
| auto *defInst = pass.currDef->getDefiningInstruction(); |
| auto I = bb->getTerminator()->getIterator(); |
| while (true) { |
| auto *inst = &*I; |
| Optional<bool> isConsumingResult = pass.liveness.isConsumingUser(inst); |
| if (isConsumingResult.hasValue()) { |
| if (isConsumingResult.getValue()) { |
| // This consuming use becomes a final destroy. |
| pass.destroys.recordFinalDestroy(inst); |
| break; |
| } |
| // Insert a destroy after this non-consuming use. |
| assert(inst != bb->getTerminator() && "Terminator must consume operand."); |
| insertDestroyAtInst(std::next(I), pass); |
| break; |
| } |
| // This is not a potential last user. Keep scanning. |
| // If the original destroy is reached, this is a dead live range. Insert a |
| // destroy immediately after the def. |
| if (I == bb->begin()) { |
| assert(cast<SILArgument>(pass.currDef)->getParent() == bb); |
| insertDestroyAtInst(I, pass); |
| break; |
| } |
| --I; |
| if (&*I == defInst) { |
| insertDestroyAtInst(std::next(I), pass); |
| break; |
| } |
| } |
| } |
| |
| /// Populate `pass.finalBlockDestroys` with the final destroy points once copies |
| /// are eliminated. This only applies to owned values. |
| /// |
| /// Observations: |
| /// - The pass.currDef must be postdominated by some subset of its |
| /// consuming uses, including destroys. |
| /// - The postdominating consumes cannot be within nested loops. |
| /// - Any blocks in nested loops are now marked LiveOut. |
| static void findOrInsertDestroys(CopyPropagationState &pass) { |
| assert(!pass.liveness.empty()); |
| if (!pass.isValueOwned()) |
| return; |
| |
| // Visit each original consuming use or destroy as the starting point for a |
| // backward CFG traversal. |
| for (auto *originalDestroyBB : pass.liveness.getOriginalDestroyBlocks()) { |
| SmallSetVector<SILBasicBlock *, 8> blockPredWorklist; |
| |
| // Process each visited block, where succBB == nullptr for the starting |
| // point of the CFG traversal. |
| auto visitBB = [&](SILBasicBlock *bb, SILBasicBlock *succBB) { |
| switch (pass.liveness.isBlockLive(bb)) { |
| case LiveOut: |
| // If succBB is null, then the original destroy must be an inner |
| // nested destroy, so just skip it. |
| // |
| // Otherwise, this CFG edge is a liveness boundary, so insert a new |
| // destroy on the edge. |
| if (succBB) |
| insertDestroyOnCFGEdge(bb, succBB, pass); |
| break; |
| case LiveWithin: |
| // The liveness boundary is inside this block. Insert a final destroy |
| // inside the block if it doesn't already have one. |
| if (!pass.destroys.hasFinalDestroy(bb)) |
| findOrInsertDestroyInBlock(bb, pass); |
| break; |
| case Dead: { |
| // Continue searching upward to find the pruned liveness boundary. |
| blockPredWorklist.insert(bb); |
| } |
| } |
| }; |
| // Perform a backward CFG traversal up to the pruned liveness boundary, |
| // visiting each block. |
| visitBB(originalDestroyBB, nullptr); |
| while (!blockPredWorklist.empty()) { |
| auto *succBB = blockPredWorklist.pop_back_val(); |
| for (auto *predBB : succBB->getPredecessorBlocks()) |
| visitBB(predBB, succBB); |
| } |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Step 4. Rewrite copies and destroys for a single copied definition. |
| //===----------------------------------------------------------------------===// |
| |
| /// `pass.currDef` is live across the given consuming use. Copy the value. |
| static void copyLiveUse(Operand *use, CopyPropagationState &pass) { |
| SILInstruction *user = use->getUser(); |
| SILBuilder B(user->getIterator()); |
| B.setCurrentDebugScope(user->getDebugScope()); |
| |
| auto *copy = B.createCopyValue(user->getLoc(), use->get()); |
| use->set(copy); |
| ++NumCopiesGenerated; |
| LLVM_DEBUG(llvm::dbgs() << " Copying at last use "; copy->dump()); |
| pass.markInvalid(SILAnalysis::InvalidationKind::Instructions); |
| } |
| |
| /// Revisit the def-use chain of `pass.currDef`. Mark unneeded original copies |
| /// and destroys for deletion. Insert new copies for interior uses that require |
| /// ownership of the used operand. |
| /// |
| /// TODO: Avoid unnecessary rewrites. Identify copies and destroys that already |
| /// complement a non-consuming use. |
| static void rewriteCopies(CopyPropagationState &pass) { |
| SmallSetVector<SILInstruction *, 8> instsToDelete; |
| SmallSetVector<SILValue, 8> defUseWorklist; |
| |
| // Visit each operand in the def-use chain. |
| auto visitUse = [&](Operand *use) { |
| auto *user = use->getUser(); |
| // Recurse through copies. |
| if (auto *copy = dyn_cast<CopyValueInst>(user)) { |
| defUseWorklist.insert(copy); |
| return; |
| } |
| if (auto *destroy = dyn_cast<DestroyValueInst>(user)) { |
| // If this destroy was marked as a final destroy, ignore it; otherwise, |
| // delete it. |
| if (!pass.destroys.claimDestroy(destroy)) { |
| instsToDelete.insert(destroy); |
| LLVM_DEBUG(llvm::dbgs() << " Removing "; destroy->dump()); |
| ++NumDestroysEliminated; |
| } |
| return; |
| } |
| // Nonconsuming uses do not need copies and cannot be marked as destroys. |
| if (!isConsuming(use)) |
| return; |
| |
| // If this use was marked as a final destroy *and* this is the first |
| // consumed operand we have visited, then ignore it. Otherwise, treat it as |
| // an "interior" consuming use and insert a copy. |
| if (!pass.destroys.claimDestroy(user)) |
| copyLiveUse(use, pass); |
| }; |
| |
| // Perform a def-use traversal, visiting each use operand. |
| defUseWorklist.insert(pass.currDef); |
| while (!defUseWorklist.empty()) { |
| SILValue value = defUseWorklist.pop_back_val(); |
| // Recurse through copies then remove them. |
| if (auto *copy = dyn_cast<CopyValueInst>(value)) { |
| for (auto *use : copy->getUses()) |
| visitUse(use); |
| copy->replaceAllUsesWith(copy->getOperand()); |
| instsToDelete.insert(copy); |
| LLVM_DEBUG(llvm::dbgs() << " Removing "; copy->dump()); |
| ++NumCopiesEliminated; |
| continue; |
| } |
| for (Operand *use : value->getUses()) |
| visitUse(use); |
| } |
| assert(pass.destroys.empty()); |
| |
| // Remove the leftover copy_value and destroy_value instructions. |
| if (!instsToDelete.empty()) { |
| recursivelyDeleteTriviallyDeadInstructions(instsToDelete.takeVector(), |
| /*force=*/true); |
| pass.markInvalid(SILAnalysis::InvalidationKind::Instructions); |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // CopyPropagation: Top-Level Function Transform. |
| //===----------------------------------------------------------------------===// |
| |
| /// TODO: we could strip casts as well, then when recursing through users keep |
| /// track of the nearest non-copy def. For opaque values, we don't expect to see |
| /// casts. |
| static SILValue stripCopies(SILValue v) { |
| while (true) { |
| v = stripSinglePredecessorArgs(v); |
| |
| if (auto *srcCopy = dyn_cast<CopyValueInst>(v)) { |
| v = srcCopy->getOperand(); |
| continue; |
| } |
| return v; |
| } |
| } |
| |
| namespace { |
| class CopyPropagation : public SILFunctionTransform { |
| /// The entry point to this function transformation. |
| void run() override; |
| }; |
| } // end anonymous namespace |
| |
| /// Top-level pass driver. |
| void CopyPropagation::run() { |
| LLVM_DEBUG(llvm::dbgs() << "*** CopyPropagation: " << getFunction()->getName() |
| << "\n"); |
| |
| // This algorithm fundamentally assumes ownership. |
| if (!getFunction()->hasOwnership()) |
| return; |
| |
| // Step 1. Find all copied defs. |
| CopyPropagationState pass(getFunction()); |
| SmallSetVector<SILValue, 16> copiedDefs; |
| for (auto &BB : *pass.F) { |
| for (auto &I : BB) { |
| if (auto *copy = dyn_cast<CopyValueInst>(&I)) |
| copiedDefs.insert(stripCopies(copy)); |
| } |
| } |
| for (auto &def : copiedDefs) { |
| pass.resetDef(def); |
| // Step 2: computeLiveness |
| if (computeLiveness(pass)) { |
| // Step 3: findOrInsertDestroys |
| findOrInsertDestroys(pass); |
| // Invalidate book-keeping before deleting instructions. |
| pass.liveness.clear(); |
| // Step 4: rewriteCopies |
| rewriteCopies(pass); |
| } |
| } |
| invalidateAnalysis(SILAnalysis::InvalidationKind(pass.invalidation)); |
| } |
| |
| SILTransform *swift::createCopyPropagation() { return new CopyPropagation(); } |