| //===--- Sink.cpp ----- Code Sinking --------------------------------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 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 |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// Many SIL instructions that don't have side effects at the SIL level are |
| /// lowered to a sequence of LLVM instructions that does have side effects that |
| /// LLVM can't sink. This pass sinks instructions close to their users. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "sink-instructions" |
| |
| #include "swift/SIL/Dominance.h" |
| #include "swift/SILOptimizer/Analysis/DominanceAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h" |
| #include "swift/SILOptimizer/Analysis/LoopAnalysis.h" |
| #include "swift/SILOptimizer/PassManager/Passes.h" |
| #include "swift/SIL/SILArgument.h" |
| #include "swift/SIL/SILValue.h" |
| #include "swift/SIL/SILDebugScope.h" |
| #include "swift/SIL/DebugUtils.h" |
| #include "swift/SILOptimizer/PassManager/Transforms.h" |
| #include "swift/SILOptimizer/Utils/Local.h" |
| #include "swift/SIL/SILInstruction.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Support/Debug.h" |
| |
| using namespace swift; |
| |
| STATISTIC(NumInstrSunk, "Number of instructions sunk"); |
| |
| namespace { |
| |
| class CodeSinkingPass : public SILFunctionTransform { |
| public: |
| CodeSinkingPass() = default; |
| |
| DominanceInfo *DT; |
| PostOrderFunctionInfo *PO; |
| SILLoopInfo *LoopInfo; |
| |
| /// \brief returns True if were able to sink the instruction \p II |
| /// closer to it's users. |
| bool sinkInstruction(SILInstruction *II) { |
| |
| // We can't sink instructions that may read or write to memory |
| // or side effects because it can change the semantics of the program. |
| if (II->mayHaveSideEffects() || II->mayReadOrWriteMemory()) return false; |
| |
| // Some instructions don't have direct memory side effects but can't be sunk |
| // because of other reasons. |
| if (isa<MarkUninitializedInst>(II) || |
| isa<MarkFunctionEscapeInst>(II) || |
| isa<MarkDependenceInst>(II)) return false; |
| |
| // We don't sink stack allocations to not destroy the proper nesting of |
| // stack allocations. |
| if (II->isAllocatingStack() || II->isDeallocatingStack()) |
| return false; |
| |
| SILBasicBlock *CurrentBlock = II->getParent(); |
| SILBasicBlock *Dest = nullptr; |
| unsigned InitialLoopDepth = LoopInfo->getLoopDepth(CurrentBlock); |
| |
| // TODO: We may want to delete debug instructions to allow us to sink more |
| // instructions. |
| for (auto result : II->getResults()) { |
| for (auto *Operand : result->getUses()) { |
| SILInstruction *User = Operand->getUser(); |
| |
| // Check if the instruction is already in the user's block. |
| if (User->getParent() == CurrentBlock) return false; |
| |
| // Record the block of the first user and move on to |
| // other users. |
| if (!Dest) { |
| Dest = User->getParent(); |
| continue; |
| } |
| |
| // Find a location that dominates all users. If we did not find such |
| // a block or if it is the current block then bail out. |
| Dest = DT->findNearestCommonDominator(Dest, User->getParent()); |
| |
| if (!Dest || Dest == CurrentBlock) |
| return false; |
| } |
| } |
| |
| if (!Dest) return false; |
| |
| // We don't want to sink instructions into loops. Walk up the dom tree |
| // until we reach the same loop nest level. |
| while (LoopInfo->getLoopDepth(Dest) != InitialLoopDepth) { |
| auto Node = DT->getNode(Dest); |
| assert(Node && "Invalid dom tree"); |
| auto IDom = Node->getIDom(); |
| assert(IDom && "Can't find the idom"); |
| Dest = IDom->getBlock(); |
| |
| if (!Dest || Dest == CurrentBlock) |
| return false; |
| } |
| |
| II->moveBefore(&*Dest->begin()); |
| NumInstrSunk++; |
| return true; |
| } |
| |
| void run() override { |
| bool Changed = false; |
| auto *F = getFunction(); |
| DT = PM->getAnalysis<DominanceAnalysis>()->get(F); |
| PO = getAnalysis<PostOrderAnalysis>()->get(F); |
| SILLoopAnalysis *LA = PM->getAnalysis<SILLoopAnalysis>(); |
| LoopInfo = LA->get(F); |
| |
| auto postOrder = PO->getPostOrder(); |
| |
| // Scan the blocks in a post-order direction to make sure that we sink the |
| // users of each instruction before visiting the instruction itself to allow |
| // us to scan the function just once. |
| for (auto &BB : postOrder) { |
| auto Inst = BB->end(); |
| auto Begin = BB->begin(); |
| |
| // Skip empty blocks. |
| if (Inst == Begin) continue; |
| // Point to the first real instruction. |
| Inst--; |
| |
| while (true) { |
| if (Inst == Begin) { |
| // This is the first instruction in the block. Try to sink it and |
| // move on to the next block. |
| Changed |= sinkInstruction(&*Inst); |
| break; |
| } else { |
| // Move the iterator to the next instruction because we may sink the |
| // current instruction. |
| SILInstruction *II = &*Inst; |
| --Inst; |
| Changed |= sinkInstruction(II); |
| } |
| } |
| |
| } |
| |
| if (Changed) PM->invalidateAnalysis(F, |
| SILAnalysis::InvalidationKind::Instructions); |
| } |
| |
| |
| }; |
| } // end anonymous namespace |
| |
| SILTransform *swift::createCodeSinking() { |
| return new CodeSinkingPass(); |
| } |