blob: f0ef090a029c03a465080bc2bf49e1f6c67f918c [file] [log] [blame]
//===--- BasicCalleeAnalysis.cpp - Determine callees per call site --------===//
//
// 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
//
//===----------------------------------------------------------------------===//
#include "swift/SILOptimizer/Analysis/BasicCalleeAnalysis.h"
#include "swift/AST/Decl.h"
#include "swift/AST/ProtocolConformance.h"
#include "swift/Basic/Statistic.h"
#include "swift/SIL/SILModule.h"
#include "swift/SILOptimizer/Utils/InstOptUtils.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
#define DEBUG_TYPE "BasicCalleeAnalysis"
using namespace swift;
void CalleeList::dump() const {
print(llvm::errs());
}
void CalleeList::print(llvm::raw_ostream &os) const {
os << "Incomplete callee list? : "
<< (isIncomplete() ? "Yes" : "No");
if (!allCalleesVisible())
os <<", not all callees visible";
os << '\n';
os << "Known callees:\n";
for (auto *CalleeFn : *this) {
os << " " << CalleeFn->getName() << "\n";
}
os << "\n";
}
bool CalleeList::allCalleesVisible() const {
if (isIncomplete())
return false;
for (SILFunction *Callee : *this) {
if (Callee->isExternalDeclaration())
return false;
// Do not consider functions in other modules (libraries) because of library
// evolution: such function may behave differently in future/past versions
// of the library.
// TODO: exclude functions which are deserialized from modules in the same
// resilience domain.
if (Callee->isAvailableExternally() &&
// shared_external functions are always emitted in the client.
Callee->getLinkage() != SILLinkage::SharedExternal)
return false;
}
return true;
}
void CalleeCache::sortAndUniqueCallees() {
// Sort the callees for each decl and remove duplicates.
for (auto &Pair : TheCache) {
auto &Callees = *Pair.second.getPointer();
// Sort by enumeration number so that clients get a stable order.
std::sort(Callees.begin(), Callees.end(),
[](SILFunction *Left, SILFunction *Right) {
// Check if Right's lexicographical order is greater than Left.
return 1 == Right->getName().compare(Left->getName());
});
// Remove duplicates.
Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
}
}
CalleeCache::CalleesAndCanCallUnknown &
CalleeCache::getOrCreateCalleesForMethod(SILDeclRef Decl) {
auto Found = TheCache.find(Decl);
if (Found != TheCache.end())
return Found->second;
auto *TheCallees = new (Allocator.Allocate()) Callees;
bool canCallUnknown = !calleesAreStaticallyKnowable(M, Decl);
CalleesAndCanCallUnknown Entry(TheCallees, canCallUnknown);
bool Inserted;
CacheType::iterator It;
std::tie(It, Inserted) = TheCache.insert(std::make_pair(Decl, Entry));
assert(Inserted && "Expected new entry to be inserted!");
return It->second;
}
/// Update the callees for each method of a given vtable.
void CalleeCache::computeClassMethodCallees() {
SmallPtrSet<AbstractFunctionDecl *, 16> unknownCallees;
// First mark all method declarations which might be overridden in another
// translation unit, i.e. outside the visibility of the optimizer.
// This is a little bit more complicated than to just check the VTable
// entry.Method itself, because an overridden method might be more accessible
// than the base method (e.g. a public method overrides a private method).
for (auto &VTable : M.getVTables()) {
assert(!VTable->getClass()->hasClangNode());
for (Decl *member : VTable->getClass()->getMembers()) {
if (auto *afd = dyn_cast<AbstractFunctionDecl>(member)) {
// If a method implementation might be overridden in another translation
// unit, also mark all the base methods as 'unknown'.
bool unknown = false;
do {
if (!calleesAreStaticallyKnowable(M, afd))
unknown = true;
if (unknown)
unknownCallees.insert(afd);
afd = afd->getOverriddenDecl();
} while (afd);
}
}
}
// Second step: collect all implementations of a method.
for (auto &VTable : M.getVTables()) {
for (const SILVTable::Entry &entry : VTable->getEntries()) {
if (auto *afd = entry.getMethod().getAbstractFunctionDecl()) {
CalleesAndCanCallUnknown &callees =
getOrCreateCalleesForMethod(entry.getMethod());
if (unknownCallees.count(afd) != 0)
callees.setInt(1);
callees.getPointer()->push_back(entry.getImplementation());
}
}
}
}
void CalleeCache::computeWitnessMethodCalleesForWitnessTable(
SILWitnessTable &WT) {
for (const SILWitnessTable::Entry &Entry : WT.getEntries()) {
if (Entry.getKind() != SILWitnessTable::Method)
continue;
auto &WitnessEntry = Entry.getMethodWitness();
auto Requirement = WitnessEntry.Requirement;
auto *WitnessFn = WitnessEntry.Witness;
// Dead function elimination nulls out entries for functions it removes.
if (!WitnessFn)
continue;
auto &TheCallees = getOrCreateCalleesForMethod(Requirement);
assert(TheCallees.getPointer() && "Unexpected null callees!");
TheCallees.getPointer()->push_back(WitnessFn);
// If we can't resolve the witness, conservatively assume it can call
// anything.
if (!Requirement.getDecl()->isProtocolRequirement() ||
!WT.getConformance()->hasWitness(Requirement.getDecl())) {
TheCallees.setInt(true);
continue;
}
bool canCallUnknown = false;
auto Conf = WT.getConformance();
switch (Conf->getProtocol()->getEffectiveAccess()) {
case AccessLevel::Open:
llvm_unreachable("protocols cannot have open access level");
case AccessLevel::Public:
canCallUnknown = true;
break;
case AccessLevel::Internal:
if (!M.isWholeModule()) {
canCallUnknown = true;
break;
}
LLVM_FALLTHROUGH;
case AccessLevel::FilePrivate:
case AccessLevel::Private: {
auto Witness = Conf->getWitness(Requirement.getDecl());
auto DeclRef = SILDeclRef(Witness.getDecl());
canCallUnknown = !calleesAreStaticallyKnowable(M, DeclRef);
}
}
if (canCallUnknown)
TheCallees.setInt(true);
}
}
/// Compute the callees for each method that appears in a VTable or
/// Witness Table.
void CalleeCache::computeMethodCallees() {
SWIFT_FUNC_STAT;
computeClassMethodCallees();
for (auto &WTable : M.getWitnessTableList())
computeWitnessMethodCalleesForWitnessTable(WTable);
}
SILFunction *
CalleeCache::getSingleCalleeForWitnessMethod(WitnessMethodInst *WMI) const {
SILFunction *CalleeFn;
SILWitnessTable *WT;
// Attempt to find a specific callee for the given conformance and member.
std::tie(CalleeFn, WT) = WMI->getModule().lookUpFunctionInWitnessTable(
WMI->getConformance(), WMI->getMember());
return CalleeFn;
}
// Look up the precomputed callees for an abstract function and
// return it as a CalleeList.
CalleeList CalleeCache::getCalleeList(SILDeclRef Decl) const {
auto Found = TheCache.find(Decl);
if (Found == TheCache.end())
return CalleeList();
auto &Pair = Found->second;
return CalleeList(*Pair.getPointer(), Pair.getInt());
}
// Return a callee list for the given witness method.
CalleeList CalleeCache::getCalleeList(WitnessMethodInst *WMI) const {
// First attempt to see if we can narrow it down to a single
// function based on the conformance.
if (auto *CalleeFn = getSingleCalleeForWitnessMethod(WMI))
return CalleeList(CalleeFn);
// Otherwise see if we previously computed the callees based on
// witness tables.
return getCalleeList(WMI->getMember());
}
// Return a callee list for a given class method.
CalleeList CalleeCache::getCalleeList(ClassMethodInst *CMI) const {
// Look for precomputed callees based on vtables.
return getCalleeList(CMI->getMember());
}
// Return the list of functions that can be called via the given callee.
CalleeList CalleeCache::getCalleeListForCalleeKind(SILValue Callee) const {
switch (Callee->getKind()) {
default:
assert(!isa<MethodInst>(Callee) &&
"Unhandled method instruction in callee determination!");
return CalleeList();
case ValueKind::FunctionRefInst:
return CalleeList(
cast<FunctionRefInst>(Callee)->getInitiallyReferencedFunction());
case ValueKind::DynamicFunctionRefInst:
case ValueKind::PreviousDynamicFunctionRefInst:
return CalleeList(); // Don't know the dynamic target.
case ValueKind::PartialApplyInst:
return getCalleeListForCalleeKind(
cast<PartialApplyInst>(Callee)->getCallee());
case ValueKind::WitnessMethodInst:
return getCalleeList(cast<WitnessMethodInst>(Callee));
case ValueKind::ClassMethodInst:
return getCalleeList(cast<ClassMethodInst>(Callee));
case ValueKind::SuperMethodInst:
case ValueKind::ObjCMethodInst:
case ValueKind::ObjCSuperMethodInst:
return CalleeList();
}
}
// Return the list of functions that can be called via the given apply
// site.
CalleeList CalleeCache::getCalleeList(FullApplySite FAS) const {
return getCalleeListForCalleeKind(FAS.getCalleeOrigin());
}
// Return the list of functions that can be called via the given instruction.
CalleeList CalleeCache::getCalleeList(SILInstruction *I) const {
// We support only deallocation instructions at the moment.
assert((isa<StrongReleaseInst>(I) || isa<ReleaseValueInst>(I)) &&
"A deallocation instruction expected");
auto Ty = I->getOperand(0)->getType();
while (auto payloadTy = Ty.getOptionalObjectType())
Ty = payloadTy;
auto Class = Ty.getClassOrBoundGenericClass();
if (!Class || Class->hasClangNode())
return CalleeList();
SILDeclRef Destructor = SILDeclRef(Class->getDestructor());
return getCalleeList(Destructor);
}
void BasicCalleeAnalysis::dump() const {
print(llvm::errs());
}
void BasicCalleeAnalysis::print(llvm::raw_ostream &os) const {
if (!Cache) {
os << "<no cache>\n";
}
llvm::DenseSet<SILDeclRef> printed;
for (auto &VTable : M.getVTables()) {
for (const SILVTable::Entry &entry : VTable->getEntries()) {
if (printed.insert(entry.getMethod()).second) {
os << "callees for " << entry.getMethod() << ":\n";
Cache->getCalleeList(entry.getMethod()).print(os);
}
}
}
}