blob: 65ef7d69011a1bf8d5762d0deb49675723dfc1ad [file] [log] [blame]
//===--- Sink.cpp ----- Code Sinking --------------------------------------===//
// This source file is part of the 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 for license information
// See 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/DebugUtils.h"
#include "swift/SIL/Dominance.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILDebugScope.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILValue.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SILOptimizer/Analysis/LoopAnalysis.h"
#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.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 {
CodeSinkingPass() = default;
DominanceInfo *DT;
PostOrderFunctionInfo *PO;
SILLoopInfo *LoopInfo;
/// 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();
// 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;
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.
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);
} else {
// Move the iterator to the next instruction because we may sink the
// current instruction.
SILInstruction *II = &*Inst;
Changed |= sinkInstruction(II);
if (Changed) PM->invalidateAnalysis(F,
} // end anonymous namespace
SILTransform *swift::createCodeSinking() {
return new CodeSinkingPass();