averello/swift-mirror
1
0
Fork 0
mirror of https://github.com/apple/swift.git synced 2025-12-14 20:36:38 +01:00
Code Issues Packages Projects Releases Wiki Activity
Files
swift-3-api-guidelines
swift-mirror/lib/SILOptimizer/Analysis/EscapeAnalysis.cpp
Arnold Schwaighofer b5f018a4b1 Mark Array.withUnsafeMutableBuffer as not escaping the array storage. 
This is safe because the closure is not allowed to capture the array according
to the documentation of 'withUnsafeMutableBuffer' and the current implementation
makes sure that any such capture would observe an empty array by swapping self
with an empty array.

Users will get "almost guaranteed" stack promotion for small arrays by writing
something like:

  func testStackAllocation(p: Proto) {
    var a = [p, p, p]
    a.withUnsafeMutableBufferPointer {
      let array = $0
      work(array)
    }
  }

It is "almost guaranteed" because we need to statically be able to tell the size
required for the array (no unspecialized generics) and the total buffer size
must not exceed 1K.
2016-03-08 19:37:47 -08:00

1833 lines
62 KiB
C++
Raw Permalink Blame History

//===--- EscapeAnalysis.cpp - SIL Escape Analysis -------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "sil-escape"
#include "swift/SILOptimizer/Analysis/EscapeAnalysis.h"
#include "swift/SILOptimizer/Analysis/BasicCalleeAnalysis.h"
#include "swift/SILOptimizer/Analysis/ArraySemantic.h"
#include "swift/SILOptimizer/Analysis/ValueTracking.h"
#include "swift/SILOptimizer/PassManager/PassManager.h"
#include "swift/SIL/SILArgument.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
using namespace swift;
static bool isProjection(ValueBase *V) {
switch (V->getKind()) {
case ValueKind::IndexAddrInst:
case ValueKind::IndexRawPointerInst:
case ValueKind::StructElementAddrInst:
case ValueKind::TupleElementAddrInst:
case ValueKind::UncheckedTakeEnumDataAddrInst:
case ValueKind::StructExtractInst:
case ValueKind::TupleExtractInst:
case ValueKind::UncheckedEnumDataInst:
case ValueKind::MarkDependenceInst:
case ValueKind::PointerToAddressInst:
case ValueKind::AddressToPointerInst:
case ValueKind::InitEnumDataAddrInst:
return true;
default:
return false;
}
}
static bool isNonWritableMemoryAddress(ValueBase *V) {
switch (V->getKind()) {
case ValueKind::FunctionRefInst:
case ValueKind::WitnessMethodInst:
case ValueKind::ClassMethodInst:
case ValueKind::SuperMethodInst:
case ValueKind::DynamicMethodInst:
case ValueKind::StringLiteralInst:
case ValueKind::ThinToThickFunctionInst:
case ValueKind::ThinFunctionToPointerInst:
case ValueKind::PointerToThinFunctionInst:
// These instructions return pointers to memory which can't be a
// destination of a store.
return true;
default:
return false;
}
}
static ValueBase *skipProjections(ValueBase *V) {
for (;;) {
if (!isProjection(V))
return V;
V = cast<SILInstruction>(V)->getOperand(0);
}
llvm_unreachable("there is no escape from an infinite loop");
}
void EscapeAnalysis::ConnectionGraph::clear() {
Values2Nodes.clear();
Nodes.clear();
ReturnNode = nullptr;
UsePoints.clear();
NodeAllocator.DestroyAll();
assert(ToMerge.empty());
}
EscapeAnalysis::CGNode *EscapeAnalysis::ConnectionGraph::
getNode(ValueBase *V, EscapeAnalysis *EA, bool createIfNeeded) {
if (isa<FunctionRefInst>(V))
return nullptr;
if (!V->hasValue())
return nullptr;
if (!EA->isPointer(V))
return nullptr;
V = skipProjections(V);
if (!createIfNeeded)
return lookupNode(V);
CGNode * &Node = Values2Nodes[V];
if (!Node) {
if (SILArgument *Arg = dyn_cast<SILArgument>(V)) {
if (Arg->isFunctionArg()) {
Node = allocNode(V, NodeType::Argument);
if (!isSummaryGraph)
Node->mergeEscapeState(EscapeState::Arguments);
} else {
Node = allocNode(V, NodeType::Value);
}
} else {
Node = allocNode(V, NodeType::Value);
}
}
return Node->getMergeTarget();
}
EscapeAnalysis::CGNode *EscapeAnalysis::ConnectionGraph::getContentNode(
CGNode *AddrNode) {
// Do we already have a content node (which is not necessarily an immediate
// successor of AddrNode)?
if (AddrNode->pointsTo)
return AddrNode->pointsTo;
CGNode *Node = allocNode(AddrNode->V, NodeType::Content);
updatePointsTo(AddrNode, Node);
assert(ToMerge.empty() &&
"Initially setting pointsTo should not require any node merges");
return Node;
}
bool EscapeAnalysis::ConnectionGraph::addDeferEdge(CGNode *From, CGNode *To) {
if (!From->addDeferred(To))
return false;
CGNode *FromPointsTo = From->pointsTo;
CGNode *ToPointsTo = To->pointsTo;
if (FromPointsTo != ToPointsTo) {
if (!ToPointsTo) {
updatePointsTo(To, FromPointsTo->getMergeTarget());
assert(ToMerge.empty() &&
"Initially setting pointsTo should not require any node merges");
} else {
// We are adding an edge between two pointers which point to different
// content nodes. This will require to merge the content nodes (and maybe
// other content nodes as well), because of the graph invariance 4).
updatePointsTo(From, ToPointsTo->getMergeTarget());
}
}
return true;
}
void EscapeAnalysis::ConnectionGraph::mergeAllScheduledNodes() {
while (!ToMerge.empty()) {
CGNode *From = ToMerge.pop_back_val();
CGNode *To = From->getMergeTarget();
assert(To != From && "Node scheduled to merge but no merge target set");
assert(!From->isMerged && "Merge source is already merged");
assert(From->Type == NodeType::Content && "Can only merge content nodes");
assert(To->Type == NodeType::Content && "Can only merge content nodes");
// Unlink the predecessors and redirect the incoming pointsTo edge.
// Note: we don't redirect the defer-edges because we don't want to trigger
// updatePointsTo (which is called by addDeferEdge) right now.
for (Predecessor Pred : From->Preds) {
CGNode *PredNode = Pred.getPointer();
if (Pred.getInt() == EdgeType::PointsTo) {
assert(PredNode->getPointsToEdge() == From &&
"Incoming pointsTo edge not set in predecessor");
if (PredNode != From)
PredNode->setPointsTo(To);
} else {
assert(PredNode != From);
auto Iter = PredNode->findDeferred(From);
assert(Iter != PredNode->defersTo.end() &&
"Incoming defer-edge not found in predecessor's defer list");
PredNode->defersTo.erase(Iter);
}
}
// Unlink and redirect the outgoing pointsTo edge.
if (CGNode *PT = From->getPointsToEdge()) {
if (PT != From) {
PT->removeFromPreds(Predecessor(From, EdgeType::PointsTo));
} else {
PT = To;
}
if (CGNode *ExistingPT = To->getPointsToEdge()) {
// The To node already has an outgoing pointsTo edge, so the only thing
// we can do is to merge both content nodes.
scheduleToMerge(ExistingPT, PT);
} else {
To->setPointsTo(PT);
}
}
// Unlink the outgoing defer edges.
for (CGNode *Defers : From->defersTo) {
assert(Defers != From && "defer edge may not form a self-cycle");
Defers->removeFromPreds(Predecessor(From, EdgeType::Defer));
}
// Redirect the incoming defer edges. This may trigger other node merges.
// Note that the Pred iterator may be invalidated (because we may add
// edges in the loop). So we don't do: for (Pred : From->Preds) {...}
for (unsigned PredIdx = 0; PredIdx < From->Preds.size(); ++PredIdx) {
CGNode *PredNode = From->Preds[PredIdx].getPointer();
if (From->Preds[PredIdx].getInt() == EdgeType::Defer) {
assert(PredNode != From && "defer edge may not form a self-cycle");
addDeferEdge(PredNode, To);
}
}
// Redirect the outgoing defer edges, which may also trigger other node
// merges.
for (CGNode *Defers : From->defersTo) {
addDeferEdge(To, Defers);
}
// There is no point in updating the pointsTo if the To node will be
// merged to another node eventually.
if (!To->mergeTo) {
// Ensure that graph invariance 4) is kept. At this point there may be still
// some violations because of the new adjacent edges of the To node.
for (unsigned PredIdx = 0; PredIdx < To->Preds.size(); ++PredIdx) {
if (To->Preds[PredIdx].getInt() == EdgeType::PointsTo) {
CGNode *PredNode = To->Preds[PredIdx].getPointer();
for (unsigned PPIdx = 0; PPIdx < PredNode->Preds.size(); ++PPIdx) {
if (PredNode->Preds[PPIdx].getInt() == EdgeType::Defer)
updatePointsTo(PredNode->Preds[PPIdx].getPointer(), To);
}
for (CGNode *Def : PredNode->defersTo) {
updatePointsTo(Def, To);
}
}
}
if (CGNode *ToPT = To->getPointsToEdge()) {
ToPT = ToPT->getMergeTarget();
for (CGNode *ToDef : To->defersTo) {
updatePointsTo(ToDef, ToPT);
assert(!ToPT->mergeTo);
}
for (unsigned PredIdx = 0; PredIdx < To->Preds.size(); ++PredIdx) {
if (To->Preds[PredIdx].getInt() == EdgeType::Defer)
updatePointsTo(To->Preds[PredIdx].getPointer(), ToPT);
}
}
To->mergeEscapeState(From->State);
}
// Cleanup the merged node.
From->isMerged = true;
From->Preds.clear();
From->defersTo.clear();
From->pointsTo = nullptr;
}
}
void EscapeAnalysis::ConnectionGraph::
updatePointsTo(CGNode *InitialNode, CGNode *pointsTo) {
// Visit all nodes in the defer web, which don't have the right pointsTo set.
assert(!pointsTo->mergeTo);
llvm::SmallVector<CGNode *, 8> WorkList;
WorkList.push_back(InitialNode);
InitialNode->isInWorkList = true;
bool isInitialSet = false;
for (unsigned Idx = 0; Idx < WorkList.size(); ++Idx) {
auto *Node = WorkList[Idx];
if (Node->pointsTo == pointsTo)
continue;
if (Node->pointsTo) {
// Mismatching: we need to merge!
scheduleToMerge(Node->pointsTo, pointsTo);
} else {
isInitialSet = true;
}
// If the node already has a pointsTo _edge_ we don't change it (we don't
// want to change the structure of the graph at this point).
if (!Node->pointsToIsEdge) {
if (Node->defersTo.empty()) {
// This node is the end of a defer-edge path with no pointsTo connected.
// We create an edge to pointsTo (agreed, this changes the structure of
// the graph but adding this edge is harmless).
Node->setPointsTo(pointsTo);
} else {
Node->pointsTo = pointsTo;
}
}
// Add all adjacent nodes to the WorkList.
for (auto *Deferred : Node->defersTo) {
if (!Deferred->isInWorkList) {
WorkList.push_back(Deferred);
Deferred->isInWorkList = true;
}
}
for (Predecessor Pred : Node->Preds) {
if (Pred.getInt() == EdgeType::Defer) {
CGNode *PredNode = Pred.getPointer();
if (!PredNode->isInWorkList) {
WorkList.push_back(PredNode);
PredNode->isInWorkList = true;
}
}
}
}
if (isInitialSet) {
// Here we handle a special case: all defer-edge paths must eventually end
// in a points-to edge to pointsTo. We ensure this by setting the edge on
// nodes which have no defer-successors (see above). But this does not cover
// the case where there is a terminating cycle in the defer-edge path,
// e.g. A -> B -> C -> B
// We find all nodes which don't reach a points-to edge and add additional
// points-to edges to fix that.
llvm::SmallVector<CGNode *, 8> PotentiallyInCycles;
// Keep all nodes with a points-to edge in the WorkList and remove all other
// nodes.
unsigned InsertionPoint = 0;
for (CGNode *Node : WorkList) {
if (Node->pointsToIsEdge) {
WorkList[InsertionPoint++] = Node;
} else {
Node->isInWorkList = false;
PotentiallyInCycles.push_back(Node);
}
}
WorkList.set_size(InsertionPoint);
unsigned Idx = 0;
while (!PotentiallyInCycles.empty()) {
// Propagate the "reaches-a-points-to-edge" backwards in the defer-edge
// sub-graph by adding those nodes to the WorkList.
while (Idx < WorkList.size()) {
auto *Node = WorkList[Idx++];
for (Predecessor Pred : Node->Preds) {
if (Pred.getInt() == EdgeType::Defer) {
CGNode *PredNode = Pred.getPointer();
if (!PredNode->isInWorkList) {
WorkList.push_back(PredNode);
PredNode->isInWorkList = true;
}
}
}
}
// Check if we still have some nodes which don't reach a points-to edge,
// i.e. points not yet in the WorkList.
while (!PotentiallyInCycles.empty()) {
auto *Node = PotentiallyInCycles.pop_back_val();
if (!Node->isInWorkList) {
// We create a points-to edge for the first node which doesn't reach
// a points-to edge yet.
Node->setPointsTo(pointsTo);
WorkList.push_back(Node);
Node->isInWorkList = true;
break;
}
}
}
}
clearWorkListFlags(WorkList);
}
void EscapeAnalysis::ConnectionGraph::propagateEscapeStates() {
bool Changed = false;
do {
Changed = false;
for (CGNode *Node : Nodes) {
// Propagate the state to all successor nodes.
if (Node->pointsTo) {
Changed |= Node->pointsTo->mergeEscapeState(Node->State);
}
for (CGNode *Def : Node->defersTo) {
Changed |= Def->mergeEscapeState(Node->State);
}
}
} while (Changed);
}
void EscapeAnalysis::ConnectionGraph::computeUsePoints() {
// First scan the whole function and add relevant instructions as use-points.
for (auto &BB : *F) {
for (SILArgument *BBArg : BB.getBBArgs()) {
/// In addition to releasing instructions (see below) we also add block
/// arguments as use points. In case of loops, block arguments can
/// "extend" the liferange of a reference in upward direction.
if (CGNode *ArgNode = lookupNode(BBArg)) {
addUsePoint(ArgNode, BBArg);
}
}
for (auto &I : BB) {
switch (I.getKind()) {
case ValueKind::StrongReleaseInst:
case ValueKind::ReleaseValueInst:
case ValueKind::UnownedReleaseInst:
case ValueKind::ApplyInst:
case ValueKind::TryApplyInst: {
/// Actually we only add instructions which may release a reference.
/// We need the use points only for getting the end of a reference's
/// liferange. And that must be a releasing instruction.
int ValueIdx = -1;
for (const Operand &Op : I.getAllOperands()) {
ValueBase *OpV = Op.get();
if (CGNode *OpNd = lookupNode(skipProjections(OpV))) {
if (ValueIdx < 0) {
ValueIdx = addUsePoint(OpNd, &I);
} else {
OpNd->setUsePointBit(ValueIdx);
}
}
}
break;
}
default:
break;
}
}
}
// Second, we propagate the use-point information through the graph.
bool Changed = false;
do {
Changed = false;
for (CGNode *Node : Nodes) {
// Propagate the bits to all successor nodes.
if (Node->pointsTo) {
Changed |= Node->pointsTo->mergeUsePoints(Node);
}
for (CGNode *Def : Node->defersTo) {
Changed |= Def->mergeUsePoints(Node);
}
}
} while (Changed);
}
bool EscapeAnalysis::ConnectionGraph::mergeFrom(ConnectionGraph *SourceGraph,
CGNodeMap &Mapping) {
// The main point of the merging algorithm is to map each content node in the
// source graph to a content node in this (destination) graph. This may
// require to create new nodes or to merge existing nodes in this graph.
// First step: replicate the points-to edges and the content nodes of the
// source graph in this graph.
bool Changed = false;
bool NodesMerged;
do {
NodesMerged = false;
for (unsigned Idx = 0; Idx < Mapping.getMappedNodes().size(); ++Idx) {
CGNode *SourceNd = Mapping.getMappedNodes()[Idx];
CGNode *DestNd = Mapping.get(SourceNd);
assert(DestNd);
if (SourceNd->getEscapeState() >= EscapeState::Global) {
// We don't need to merge the source subgraph of nodes which have the
// global escaping state set.
// Just set global escaping in the caller node and that's it.
Changed |= DestNd->mergeEscapeState(EscapeState::Global);
continue;
}
CGNode *SourcePT = SourceNd->pointsTo;
if (!SourcePT)
continue;
CGNode *MappedDestPT = Mapping.get(SourcePT);
if (!DestNd->pointsTo) {
// The following getContentNode() will create a new content node.
Changed = true;
}
CGNode *DestPT = getContentNode(DestNd);
if (MappedDestPT) {
// We already found the destination node through another path.
if (DestPT != MappedDestPT) {
// There are two content nodes in this graph which map to the same
// content node in the source graph -> we have to merge them.
scheduleToMerge(DestPT, MappedDestPT);
mergeAllScheduledNodes();
Changed = true;
NodesMerged = true;
}
assert(SourcePT->isInWorkList);
} else {
// It's the first time we see the destination node, so we add it to the
// mapping.
Mapping.add(SourcePT, DestPT);
}
}
} while (NodesMerged);
clearWorkListFlags(Mapping.getMappedNodes());
// Second step: add the source graph's defer edges to this graph.
llvm::SmallVector<CGNode *, 8> WorkList;
for (CGNode *SourceNd : Mapping.getMappedNodes()) {
assert(WorkList.empty());
WorkList.push_back(SourceNd);
SourceNd->isInWorkList = true;
CGNode *DestFrom = Mapping.get(SourceNd);
assert(DestFrom && "node should have been merged to the graph");
// Collect all nodes which are reachable from the SourceNd via a path
// which only contains defer-edges.
for (unsigned Idx = 0; Idx < WorkList.size(); ++Idx) {
CGNode *SourceReachable = WorkList[Idx];
CGNode *DestReachable = Mapping.get(SourceReachable);
// Create the edge in this graph. Note: this may trigger merging of
// content nodes.
if (DestReachable) {
DestFrom = defer(DestFrom, DestReachable, Changed);
}
for (auto *Deferred : SourceReachable->defersTo) {
if (!Deferred->isInWorkList) {
WorkList.push_back(Deferred);
Deferred->isInWorkList = true;
}
}
}
clearWorkListFlags(WorkList);
WorkList.clear();
}
return Changed;
}
/// Returns true if \p V is a use of \p Node, i.e. V may (indirectly)
/// somehow refer to the Node's value.
/// Use-points are only values which are relevant for lifeness computation,
/// e.g. release or apply instructions.
bool EscapeAnalysis::ConnectionGraph::isUsePoint(ValueBase *V, CGNode *Node) {
assert(Node->getEscapeState() < EscapeState::Global &&
"Use points are only valid for non-escaping nodes");
auto Iter = UsePoints.find(V);
if (Iter == UsePoints.end())
return false;
int Idx = Iter->second;
if (Idx >= (int)Node->UsePoints.size())
return false;
return Node->UsePoints.test(Idx);
}
bool EscapeAnalysis::ConnectionGraph::isReachable(CGNode *From, CGNode *To) {
// See if we can reach the From-node by transitively visiting the
// predecessor nodes of the To-node.
// Usually nodes have few predecessor nodes and the graph depth is small.
// So this should be fast.
llvm::SmallVector<CGNode *, 8> WorkList;
WorkList.push_back(From);
From->isInWorkList = true;
for (unsigned Idx = 0; Idx < WorkList.size(); ++Idx) {
CGNode *Reachable = WorkList[Idx];
if (Reachable == To)
return true;
for (Predecessor Pred : Reachable->Preds) {
CGNode *PredNode = Pred.getPointer();
if (!PredNode->isInWorkList) {
PredNode->isInWorkList = true;
WorkList.push_back(PredNode);
}
}
}
clearWorkListFlags(WorkList);
return false;
}
//===----------------------------------------------------------------------===//
// Dumping, Viewing and Verification
//===----------------------------------------------------------------------===//
#ifndef NDEBUG
/// For the llvm's GraphWriter we copy the connection graph into CGForDotView.
/// This makes iterating over the edges easier.
struct CGForDotView {
enum EdgeTypes {
PointsTo,
Deferred
};
struct Node {
EscapeAnalysis::CGNode *OrigNode;
CGForDotView *Graph;
SmallVector<Node *, 8> Children;
SmallVector<EdgeTypes, 8> ChildrenTypes;
};
CGForDotView(const EscapeAnalysis::ConnectionGraph *CG);
std::string getNodeLabel(const Node *Node) const;
std::string getNodeAttributes(const Node *Node) const;
std::vector<Node> Nodes;
SILFunction *F;
const EscapeAnalysis::ConnectionGraph *OrigGraph;
// The same IDs as the SILPrinter uses.
llvm::DenseMap<const ValueBase *, unsigned> InstToIDMap;
typedef std::vector<Node>::iterator iterator;
typedef SmallVectorImpl<Node *>::iterator child_iterator;
};
CGForDotView::CGForDotView(const EscapeAnalysis::ConnectionGraph *CG) :
F(CG->F), OrigGraph(CG) {
Nodes.resize(CG->Nodes.size());
llvm::DenseMap<EscapeAnalysis::CGNode *, Node *> Orig2Node;
int idx = 0;
for (auto *OrigNode : CG->Nodes) {
if (OrigNode->isMerged)
continue;
Orig2Node[OrigNode] = &Nodes[idx++];
}
Nodes.resize(idx);
CG->F->numberValues(InstToIDMap);
idx = 0;
for (auto *OrigNode : CG->Nodes) {
if (OrigNode->isMerged)
continue;
auto &Nd = Nodes[idx++];
Nd.Graph = this;
Nd.OrigNode = OrigNode;
if (auto *PT = OrigNode->getPointsToEdge()) {
Nd.Children.push_back(Orig2Node[PT]);
Nd.ChildrenTypes.push_back(PointsTo);
}
for (auto *Def : OrigNode->defersTo) {
Nd.Children.push_back(Orig2Node[Def]);
Nd.ChildrenTypes.push_back(Deferred);
}
}
}
std::string CGForDotView::getNodeLabel(const Node *Node) const {
std::string Label;
llvm::raw_string_ostream O(Label);
if (ValueBase *V = Node->OrigNode->V)
O << '%' << InstToIDMap.lookup(V) << '\n';
switch (Node->OrigNode->Type) {
case swift::EscapeAnalysis::NodeType::Content:
O << "content";
break;
case swift::EscapeAnalysis::NodeType::Return:
O << "return";
break;
default: {
std::string Inst;
llvm::raw_string_ostream OI(Inst);
SILValue(Node->OrigNode->V)->print(OI);
size_t start = Inst.find(" = ");
if (start != std::string::npos) {
start += 3;
} else {
start = 2;
}
O << Inst.substr(start, 20);
break;
}
}
if (!Node->OrigNode->matchPointToOfDefers()) {
O << "\nPT mismatch: ";
if (Node->OrigNode->pointsTo) {
if (ValueBase *V = Node->OrigNode->pointsTo->V)
O << '%' << Node->Graph->InstToIDMap[V];
} else {
O << "null";
}
}
O.flush();
return Label;
}
std::string CGForDotView::getNodeAttributes(const Node *Node) const {
auto *Orig = Node->OrigNode;
std::string attr;
switch (Orig->Type) {
case swift::EscapeAnalysis::NodeType::Content:
attr = "style=\"rounded\"";
break;
case swift::EscapeAnalysis::NodeType::Argument:
case swift::EscapeAnalysis::NodeType::Return:
attr = "style=\"bold\"";
break;
default:
break;
}
if (Orig->getEscapeState() != swift::EscapeAnalysis::EscapeState::None &&
!attr.empty())
attr += ',';
switch (Orig->getEscapeState()) {
case swift::EscapeAnalysis::EscapeState::None:
break;
case swift::EscapeAnalysis::EscapeState::Return:
attr += "color=\"green\"";
break;
case swift::EscapeAnalysis::EscapeState::Arguments:
attr += "color=\"blue\"";
break;
case swift::EscapeAnalysis::EscapeState::Global:
attr += "color=\"red\"";
break;
}
return attr;
}
namespace llvm {
/// GraphTraits specialization so the CGForDotView can be
/// iterable by generic graph iterators.
template <> struct GraphTraits<CGForDotView::Node *> {
typedef CGForDotView::Node NodeType;
typedef CGForDotView::child_iterator ChildIteratorType;
static NodeType *getEntryNode(NodeType *N) { return N; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->Children.begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->Children.end();
}
};
template <> struct GraphTraits<CGForDotView *>
: public GraphTraits<CGForDotView::Node *> {
typedef CGForDotView *GraphType;
static NodeType *getEntryNode(GraphType F) { return nullptr; }
typedef CGForDotView::iterator nodes_iterator;
static nodes_iterator nodes_begin(GraphType OCG) {
return OCG->Nodes.begin();
}
static nodes_iterator nodes_end(GraphType OCG) { return OCG->Nodes.end(); }
static unsigned size(GraphType CG) { return CG->Nodes.size(); }
};
/// This is everything the llvm::GraphWriter needs to write the call graph in
/// a dot file.
template <>
struct DOTGraphTraits<CGForDotView *> : public DefaultDOTGraphTraits {
DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
static std::string getGraphName(const CGForDotView *Graph) {
return "CG for " + Graph->F->getName().str();
}
std::string getNodeLabel(const CGForDotView::Node *Node,
const CGForDotView *Graph) {
return Graph->getNodeLabel(Node);
}
static std::string getNodeAttributes(const CGForDotView::Node *Node,
const CGForDotView *Graph) {
return Graph->getNodeAttributes(Node);
}
static std::string getEdgeAttributes(const CGForDotView::Node *Node,
CGForDotView::child_iterator I,
const CGForDotView *Graph) {
unsigned ChildIdx = I - Node->Children.begin();
switch (Node->ChildrenTypes[ChildIdx]) {
case CGForDotView::PointsTo: return "";
case CGForDotView::Deferred: return "color=\"gray\"";
}
}
};
} // end llvm namespace
#endif
void EscapeAnalysis::ConnectionGraph::viewCG() const {
/// When asserts are disabled, this should be a NoOp.
#ifndef NDEBUG
CGForDotView CGDot(this);
llvm::ViewGraph(&CGDot, "connection-graph");
#endif
}
void EscapeAnalysis::CGNode::dump() const {
llvm::errs() << getTypeStr();
if (V)
llvm::errs() << ": " << *V;
else
llvm::errs() << '\n';
if (mergeTo) {
llvm::errs() << " -> merged to ";
mergeTo->dump();
}
}
const char *EscapeAnalysis::CGNode::getTypeStr() const {
switch (Type) {
case NodeType::Value: return "Val";
case NodeType::Content: return "Con";
case NodeType::Argument: return "Arg";
case NodeType::Return: return "Ret";
}
}
void EscapeAnalysis::ConnectionGraph::dump() const {
print(llvm::errs());
}
void EscapeAnalysis::ConnectionGraph::print(llvm::raw_ostream &OS) const {
#ifndef NDEBUG
OS << "CG of " << F->getName() << '\n';
// Assign the same IDs to SILValues as the SILPrinter does.
llvm::DenseMap<const ValueBase *, unsigned> InstToIDMap;
InstToIDMap[nullptr] = (unsigned)-1;
F->numberValues(InstToIDMap);
// Assign consecutive subindices for nodes which map to the same value.
llvm::DenseMap<const ValueBase *, unsigned> NumSubindicesPerValue;
llvm::DenseMap<CGNode *, unsigned> Node2Subindex;
// Sort by SILValue ID+Subindex. To make the output somehow consistent with
// the output of the function's SIL.
auto sortNodes = [&](llvm::SmallVectorImpl<CGNode *> &Nodes) {
std::sort(Nodes.begin(), Nodes.end(),
[&](CGNode *Nd1, CGNode *Nd2) -> bool {
unsigned VIdx1 = InstToIDMap[Nd1->V];
unsigned VIdx2 = InstToIDMap[Nd2->V];
if (VIdx1 != VIdx2)
return VIdx1 < VIdx2;
return Node2Subindex[Nd1] < Node2Subindex[Nd2];
});
};
auto NodeStr = [&](CGNode *Nd) -> std::string {
std::string Str;
if (Nd->V) {
llvm::raw_string_ostream OS(Str);
OS << '%' << InstToIDMap[Nd->V];
unsigned Idx = Node2Subindex[Nd];
if (Idx != 0)
OS << '.' << Idx;
OS.flush();
}
return Str;
};
llvm::SmallVector<CGNode *, 8> SortedNodes;
for (CGNode *Nd : Nodes) {
if (!Nd->isMerged) {
unsigned &Idx = NumSubindicesPerValue[Nd->V];
Node2Subindex[Nd] = Idx++;
SortedNodes.push_back(Nd);
}
}
sortNodes(SortedNodes);
llvm::DenseMap<int, ValueBase *> Idx2UsePoint;
for (auto Iter : UsePoints) {
Idx2UsePoint[Iter.second] = Iter.first;
}
for (CGNode *Nd : SortedNodes) {
OS << " " << Nd->getTypeStr() << ' ' << NodeStr(Nd) << " Esc: ";
switch (Nd->getEscapeState()) {
case EscapeState::None: {
const char *Separator = "";
for (unsigned VIdx = Nd->UsePoints.find_first(); VIdx != -1u;
VIdx = Nd->UsePoints.find_next(VIdx)) {
ValueBase *V = Idx2UsePoint[VIdx];
OS << Separator << '%' << InstToIDMap[V];
Separator = ",";
}
break;
}
case EscapeState::Return:
OS << 'R';
break;
case EscapeState::Arguments:
OS << 'A';
break;
case EscapeState::Global:
OS << 'G';
break;
}
OS << ", Succ: ";
const char *Separator = "";
if (CGNode *PT = Nd->getPointsToEdge()) {
OS << '(' << NodeStr(PT) << ')';
Separator = ", ";
}
llvm::SmallVector<CGNode *, 8> SortedDefers = Nd->defersTo;
sortNodes(SortedDefers);
for (CGNode *Def : SortedDefers) {
OS << Separator << NodeStr(Def);
Separator = ", ";
}
OS << '\n';
}
OS << "End\n";
#endif
}
void EscapeAnalysis::ConnectionGraph::verify() const {
#ifndef NDEBUG
verifyStructure();
// Check graph invariance 4)
for (CGNode *Nd : Nodes) {
assert(Nd->matchPointToOfDefers());
}
#endif
}
void EscapeAnalysis::ConnectionGraph::verifyStructure() const {
#ifndef NDEBUG
for (CGNode *Nd : Nodes) {
if (Nd->isMerged) {
assert(Nd->mergeTo);
assert(!Nd->pointsTo);
assert(Nd->defersTo.empty());
assert(Nd->Preds.empty());
assert(Nd->Type == NodeType::Content);
continue;
}
// Check if predecessor and successor edges are linked correctly.
for (Predecessor Pred : Nd->Preds) {
CGNode *PredNode = Pred.getPointer();
if (Pred.getInt() == EdgeType::Defer) {
assert(PredNode->findDeferred(Nd) != PredNode->defersTo.end());
} else {
assert(Pred.getInt() == EdgeType::PointsTo);
assert(PredNode->getPointsToEdge() == Nd);
}
}
for (CGNode *Def : Nd->defersTo) {
assert(Def->findPred(Predecessor(Nd, EdgeType::Defer)) != Def->Preds.end());
assert(Def != Nd);
}
if (CGNode *PT = Nd->getPointsToEdge()) {
assert(PT->Type == NodeType::Content);
assert(PT->findPred(Predecessor(Nd, EdgeType::PointsTo)) != PT->Preds.end());
}
}
#endif
}
//===----------------------------------------------------------------------===//
// EscapeAnalysis
//===----------------------------------------------------------------------===//
EscapeAnalysis::EscapeAnalysis(SILModule *M) :
BottomUpIPAnalysis(AnalysisKind::Escape), M(M),
ArrayType(M->getASTContext().getArrayDecl()), BCA(nullptr) {
}
void EscapeAnalysis::initialize(SILPassManager *PM) {
BCA = PM->getAnalysis<BasicCalleeAnalysis>();
}
/// Returns true if we need to add defer edges for the arguments of a block.
static bool linkBBArgs(SILBasicBlock *BB) {
// Don't need to handle function arguments.
if (BB == &BB->getParent()->front())
return false;
// We don't need to link to the try_apply's normal result argument, because
// we handle it separately in setAllEscaping() and mergeCalleeGraph().
if (SILBasicBlock *SinglePred = BB->getSinglePredecessor()) {
auto *TAI = dyn_cast<TryApplyInst>(SinglePred->getTerminator());
if (TAI && BB == TAI->getNormalBB())
return false;
}
return true;
}
/// Returns true if the type \p Ty is a reference or transitively contains
/// a reference, i.e. if it is a "pointer" type.
static bool isOrContainsReference(SILType Ty, SILModule *Mod) {
if (Ty.hasReferenceSemantics())
return true;
if (Ty.getSwiftType() == Mod->getASTContext().TheRawPointerType)
return true;
if (auto *Str = Ty.getStructOrBoundGenericStruct()) {
for (auto *Field : Str->getStoredProperties()) {
if (isOrContainsReference(Ty.getFieldType(Field, *Mod), Mod))
return true;
}
return false;
}
if (auto TT = Ty.getAs<TupleType>()) {
for (unsigned i = 0, e = TT->getNumElements(); i != e; ++i) {
if (isOrContainsReference(Ty.getTupleElementType(i), Mod))
return true;
}
return false;
}
if (auto En = Ty.getEnumOrBoundGenericEnum()) {
for (auto *ElemDecl : En->getAllElements()) {
if (ElemDecl->hasArgumentType() &&
isOrContainsReference(Ty.getEnumElementType(ElemDecl, *Mod), Mod))
return true;
}
return false;
}
return false;
}
bool EscapeAnalysis::isPointer(ValueBase *V) {
assert(V->hasValue());
SILType Ty = V->getType();
auto Iter = isPointerCache.find(Ty);
if (Iter != isPointerCache.end())
return Iter->second;
bool IP = (Ty.isAddress() || isOrContainsReference(Ty, M));
isPointerCache[Ty] = IP;
return IP;
}
void EscapeAnalysis::buildConnectionGraph(FunctionInfo *FInfo,
FunctionOrder &BottomUpOrder,
int RecursionDepth) {
if (BottomUpOrder.prepareForVisiting(FInfo))
return;
DEBUG(llvm::dbgs() << " >> build graph for " <<
FInfo->Graph.F->getName() << '\n');
FInfo->NeedUpdateSummaryGraph = true;
ConnectionGraph *ConGraph = &FInfo->Graph;
assert(ConGraph->isEmpty());
// We use a worklist for iteration to visit the blocks in dominance order.
llvm::SmallPtrSet<SILBasicBlock*, 32> VisitedBlocks;
llvm::SmallVector<SILBasicBlock *, 16> WorkList;
VisitedBlocks.insert(&*ConGraph->F->begin());
WorkList.push_back(&*ConGraph->F->begin());
while (!WorkList.empty()) {
SILBasicBlock *BB = WorkList.pop_back_val();
// Create edges for the instructions.
for (auto &I : *BB) {
analyzeInstruction(&I, FInfo, BottomUpOrder, RecursionDepth);
}
for (auto &Succ : BB->getSuccessors()) {
if (VisitedBlocks.insert(Succ.getBB()).second)
WorkList.push_back(Succ.getBB());
}
}
// Second step: create defer-edges for block arguments.
for (SILBasicBlock &BB : *ConGraph->F) {
if (!linkBBArgs(&BB))
continue;
// Create defer-edges from the block arguments to it's values in the
// predecessor's terminator instructions.
for (SILArgument *BBArg : BB.getBBArgs()) {
CGNode *ArgNode = ConGraph->getNode(BBArg, this);
if (!ArgNode)
continue;
llvm::SmallVector<SILValue,4> Incoming;
if (!BBArg->getIncomingValues(Incoming)) {
// We don't know where the block argument comes from -> treat it
// conservatively.
ConGraph->setEscapesGlobal(ArgNode);
continue;
}
for (SILValue Src : Incoming) {
CGNode *SrcArg = ConGraph->getNode(Src, this);
if (SrcArg) {
ArgNode = ConGraph->defer(ArgNode, SrcArg);
} else {
ConGraph->setEscapesGlobal(ArgNode);
break;
}
}
}
}
DEBUG(llvm::dbgs() << " << finished graph for " <<
FInfo->Graph.F->getName() << '\n');
}
void EscapeAnalysis::analyzeInstruction(SILInstruction *I,
FunctionInfo *FInfo,
FunctionOrder &BottomUpOrder,
int RecursionDepth) {
ConnectionGraph *ConGraph = &FInfo->Graph;
FullApplySite FAS = FullApplySite::isa(I);
if (FAS) {
ArraySemanticsCall ASC(FAS.getInstruction());
switch (ASC.getKind()) {
case ArrayCallKind::kArrayPropsIsNativeTypeChecked:
case ArrayCallKind::kCheckSubscript:
case ArrayCallKind::kCheckIndex:
case ArrayCallKind::kGetCount:
case ArrayCallKind::kGetCapacity:
case ArrayCallKind::kMakeMutable:
// These array semantics calls do not capture anything.
return;
case ArrayCallKind::kArrayUninitialized:
// array.uninitialized may have a first argument which is the
// allocated array buffer. The call is like a struct(buffer)
// instruction.
if (CGNode *BufferNode = ConGraph->getNode(FAS.getArgument(0), this)) {
ConGraph->defer(ConGraph->getNode(I, this), BufferNode);
}
return;
case ArrayCallKind::kGetArrayOwner:
if (CGNode *BufferNode = ConGraph->getNode(ASC.getSelf(), this)) {
ConGraph->defer(ConGraph->getNode(I, this), BufferNode);
}
return;
case ArrayCallKind::kGetElement:
if (CGNode *AddrNode = ConGraph->getNode(ASC.getSelf(), this)) {
CGNode *DestNode = nullptr;
// This is like a load from a ref_element_addr.
if (ASC.hasGetElementDirectResult()) {
DestNode = ConGraph->getNode(FAS.getInstruction(), this);
} else {
CGNode *DestAddrNode = ConGraph->getNode(FAS.getArgument(0), this);
assert(DestAddrNode && "indirect result must have node");
// The content of the destination address.
DestNode = ConGraph->getContentNode(DestAddrNode);
}
if (DestNode) {
// One content node for going from the array buffer pointer to
// the element address (like ref_element_addr).
CGNode *RefElement = ConGraph->getContentNode(AddrNode);
// Another content node to actually load the element.
CGNode *ArrayContent = ConGraph->getContentNode(RefElement);
ConGraph->defer(DestNode, ArrayContent);
return;
}
}
break;
case ArrayCallKind::kGetElementAddress:
// This is like a ref_element_addr.
if (CGNode *SelfNode = ConGraph->getNode(ASC.getSelf(), this)) {
ConGraph->defer(ConGraph->getNode(I, this),
ConGraph->getContentNode(SelfNode));
}
return;
case ArrayCallKind::kWithUnsafeMutableBufferPointer:
// Model this like an escape of the elements of the array and a capture
// of anything captured by the closure.
// Self is passed inout.
if (CGNode *AddrArrayStruct = ConGraph->getNode(ASC.getSelf(), this)) {
CGNode *ArrayStructValueNode =
ConGraph->getContentNode(AddrArrayStruct);
// One content node for going from the array buffer pointer to
// the element address (like ref_element_addr).
CGNode *RefElement = ConGraph->getContentNode(ArrayStructValueNode);
// Another content node to actually load the element.
CGNode *ArrayContent = ConGraph->getContentNode(RefElement);
ConGraph->setEscapesGlobal(ArrayContent);
// The first non indirect result is the closure.
auto Args = FAS.getArgumentsWithoutIndirectResults();
setEscapesGlobal(ConGraph, Args[0]);
return;
}
break;
default:
break;
}
if (RecursionDepth < MaxRecursionDepth) {
CalleeList Callees = BCA->getCalleeList(FAS);
if (Callees.allCalleesVisible()) {
// Derive the connection graph of the apply from the known callees.
for (SILFunction *Callee : Callees) {
FunctionInfo *CalleeInfo = getFunctionInfo(Callee);
CalleeInfo->addCaller(FInfo, FAS);
if (!CalleeInfo->isVisited()) {
// Recursively visit the called function.
buildConnectionGraph(CalleeInfo, BottomUpOrder, RecursionDepth + 1);
BottomUpOrder.tryToSchedule(CalleeInfo);
}
}
return;
}
}
if (auto *Fn = FAS.getReferencedFunction()) {
if (Fn->getName() == "swift_bufferAllocate")
// The call is a buffer allocation, e.g. for Array.
return;
}
}
if (isProjection(I))
return;
// Instructions which return the address of non-writable memory cannot have
// an effect on escaping.
if (isNonWritableMemoryAddress(I))
return;
switch (I->getKind()) {
case ValueKind::AllocStackInst:
case ValueKind::AllocRefInst:
case ValueKind::AllocBoxInst:
ConGraph->getNode(I, this);
return;
case ValueKind::DeallocStackInst:
case ValueKind::StrongRetainInst:
case ValueKind::StrongRetainUnownedInst:
case ValueKind::RetainValueInst:
case ValueKind::UnownedRetainInst:
case ValueKind::BranchInst:
case ValueKind::CondBranchInst:
case ValueKind::SwitchEnumInst:
case ValueKind::DebugValueInst:
case ValueKind::DebugValueAddrInst:
case ValueKind::ValueMetatypeInst:
case ValueKind::InitExistentialMetatypeInst:
case ValueKind::OpenExistentialMetatypeInst:
case ValueKind::ExistentialMetatypeInst:
// These instructions don't have any effect on escaping.
return;
case ValueKind::StrongReleaseInst:
case ValueKind::ReleaseValueInst:
case ValueKind::StrongUnpinInst:
case ValueKind::UnownedReleaseInst: {
SILValue OpV = I->getOperand(0);
if (CGNode *AddrNode = ConGraph->getNode(OpV, this)) {
// A release instruction may deallocate the pointer operand. This may
// capture any content of the released object, but not the pointer to
// the object itself (because it will be a dangling pointer after
// deallocation).
CGNode *CapturedByDeinit = ConGraph->getContentNode(AddrNode);
CapturedByDeinit = ConGraph->getContentNode(CapturedByDeinit);
if (deinitIsKnownToNotCapture(OpV)) {
CapturedByDeinit = ConGraph->getContentNode(CapturedByDeinit);
}
ConGraph->setEscapesGlobal(CapturedByDeinit);
}
return;
}
case ValueKind::LoadInst:
case ValueKind::LoadWeakInst:
// We treat ref_element_addr like a load (see NodeType::Content).
case ValueKind::RefElementAddrInst:
case ValueKind::ProjectBoxInst:
case ValueKind::InitExistentialAddrInst:
case ValueKind::OpenExistentialAddrInst:
if (isPointer(I)) {
CGNode *AddrNode = ConGraph->getNode(I->getOperand(0), this);
if (!AddrNode) {
// A load from an address we don't handle -> be conservative.
CGNode *ValueNode = ConGraph->getNode(I, this);
ConGraph->setEscapesGlobal(ValueNode);
return;
}
CGNode *PointsTo = ConGraph->getContentNode(AddrNode);
// No need for a separate node for the load instruction:
// just reuse the content node.
ConGraph->setNode(I, PointsTo);
}
return;
case ValueKind::CopyAddrInst: {
// Be conservative if the dest may be the final release.
if (!cast<CopyAddrInst>(I)->isInitializationOfDest()) {
setAllEscaping(I, ConGraph);
break;
}
// A copy_addr is like a 'store (load src) to dest'.
CGNode *SrcAddrNode = ConGraph->getNode(I->getOperand(CopyAddrInst::Src),
this);
if (!SrcAddrNode) {
setAllEscaping(I, ConGraph);
break;
}
CGNode *LoadedValue = ConGraph->getContentNode(SrcAddrNode);
CGNode *DestAddrNode = ConGraph->getNode(
I->getOperand(CopyAddrInst::Dest), this);
if (DestAddrNode) {
// Create a defer-edge from the loaded to the stored value.
CGNode *PointsTo = ConGraph->getContentNode(DestAddrNode);
ConGraph->defer(PointsTo, LoadedValue);
} else {
// A store to an address we don't handle -> be conservative.
ConGraph->setEscapesGlobal(LoadedValue);
}
return;
}
break;
case ValueKind::StoreInst:
case ValueKind::StoreWeakInst:
if (CGNode *ValueNode = ConGraph->getNode(I->getOperand(StoreInst::Src),
this)) {
CGNode *AddrNode = ConGraph->getNode(I->getOperand(StoreInst::Dest),
this);
if (AddrNode) {
// Create a defer-edge from the content to the stored value.
CGNode *PointsTo = ConGraph->getContentNode(AddrNode);
ConGraph->defer(PointsTo, ValueNode);
} else {
// A store to an address we don't handle -> be conservative.
ConGraph->setEscapesGlobal(ValueNode);
}
}
return;
case ValueKind::PartialApplyInst: {
// The result of a partial_apply is a thick function which stores the
// boxed partial applied arguments. We create defer-edges from the
// partial_apply values to the arguments.
CGNode *ResultNode = ConGraph->getNode(I, this);
assert(ResultNode && "thick functions must have a CG node");
for (const Operand &Op : I->getAllOperands()) {
if (CGNode *ArgNode = ConGraph->getNode(Op.get(), this)) {
ResultNode = ConGraph->defer(ResultNode, ArgNode);
}
}
return;
}
case ValueKind::SelectEnumInst:
case ValueKind::SelectEnumAddrInst:
analyzeSelectInst(cast<SelectEnumInstBase>(I), ConGraph);
return;
case ValueKind::SelectValueInst:
analyzeSelectInst(cast<SelectValueInst>(I), ConGraph);
return;
case ValueKind::StructInst:
case ValueKind::TupleInst:
case ValueKind::EnumInst: {
// Aggregate composition is like assigning the aggregate fields to the
// resulting aggregate value.
CGNode *ResultNode = nullptr;
for (const Operand &Op : I->getAllOperands()) {
if (CGNode *FieldNode = ConGraph->getNode(Op.get(), this)) {
if (!ResultNode) {
// A small optimization to reduce the graph size: we re-use the
// first field node as result node.
ConGraph->setNode(I, FieldNode);
ResultNode = FieldNode;
assert(isPointer(I));
} else {
ResultNode = ConGraph->defer(ResultNode, FieldNode);
}
}
}
return;
}
case ValueKind::UncheckedRefCastInst:
case ValueKind::ConvertFunctionInst:
case ValueKind::UpcastInst:
case ValueKind::InitExistentialRefInst:
case ValueKind::OpenExistentialRefInst:
case ValueKind::UnownedToRefInst:
case ValueKind::RefToUnownedInst:
case ValueKind::RawPointerToRefInst:
case ValueKind::RefToRawPointerInst:
case ValueKind::RefToBridgeObjectInst:
case ValueKind::BridgeObjectToRefInst:
case ValueKind::UncheckedAddrCastInst:
case ValueKind::UnconditionalCheckedCastInst:
case ValueKind::StrongPinInst:
// A cast is almost like a projection.
if (CGNode *OpNode = ConGraph->getNode(I->getOperand(0), this)) {
ConGraph->setNode(I, OpNode);
}
break;
case ValueKind::UncheckedRefCastAddrInst: {
auto *URCAI = cast<UncheckedRefCastAddrInst>(I);
CGNode *SrcNode = ConGraph->getNode(URCAI->getSrc(), this);
CGNode *DestNode = ConGraph->getNode(URCAI->getDest(), this);
assert(SrcNode && DestNode && "must have nodes for address operands");
ConGraph->defer(DestNode, SrcNode);
return;
}
case ValueKind::ReturnInst:
if (CGNode *ValueNd = ConGraph->getNode(cast<ReturnInst>(I)->getOperand(),
this)) {
ConGraph->defer(ConGraph->getReturnNode(), ValueNd);
}
return;
default:
// We handle all other instructions conservatively.
setAllEscaping(I, ConGraph);
return;
}
}
template<class SelectInst> void EscapeAnalysis::
analyzeSelectInst(SelectInst *SI, ConnectionGraph *ConGraph) {
if (auto *ResultNode = ConGraph->getNode(SI, this)) {
// Connect all case values to the result value.
// Note that this does not include the first operand (the condition).
for (unsigned Idx = 0, End = SI->getNumCases(); Idx < End; ++Idx) {
SILValue CaseVal = SI->getCase(Idx).second;
auto *ArgNode = ConGraph->getNode(CaseVal, this);
assert(ArgNode &&
"there should be an argument node if there is a result node");
ResultNode = ConGraph->defer(ResultNode, ArgNode);
}
// ... also including the default value.
auto *DefaultNode = ConGraph->getNode(SI->getDefaultResult(), this);
assert(DefaultNode &&
"there should be an argument node if there is a result node");
ConGraph->defer(ResultNode, DefaultNode);
}
}
bool EscapeAnalysis::deinitIsKnownToNotCapture(SILValue V) {
for (;;) {
// The deinit of an array buffer does not capture the array elements.
if (V->getType().getNominalOrBoundGenericNominal() == ArrayType)
return true;
// The deinit of a box does not capture its content.
if (V->getType().is<SILBoxType>())
return true;
if (isa<FunctionRefInst>(V))
return true;
// Check all operands of a partial_apply
if (auto *PAI = dyn_cast<PartialApplyInst>(V)) {
for (Operand &Op : PAI->getAllOperands()) {
if (isPointer(Op.get()) && !deinitIsKnownToNotCapture(Op.get()))
return false;
}
return true;
}
if (isProjection(V)) {
V = dyn_cast<SILInstruction>(V)->getOperand(0);
continue;
}
return false;
}
}
void EscapeAnalysis::setAllEscaping(SILInstruction *I,
ConnectionGraph *ConGraph) {
if (auto *TAI = dyn_cast<TryApplyInst>(I)) {
setEscapesGlobal(ConGraph, TAI->getNormalBB()->getBBArg(0));
setEscapesGlobal(ConGraph, TAI->getErrorBB()->getBBArg(0));
}
// Even if the instruction does not write memory we conservatively set all
// operands to escaping, because they may "escape" to the result value in
// an unspecified way. For example consider bit-casting a pointer to an int.
// In this case we don't even create a node for the resulting int value.
for (const Operand &Op : I->getAllOperands()) {
SILValue OpVal = Op.get();
if (!isNonWritableMemoryAddress(OpVal))
setEscapesGlobal(ConGraph, OpVal);
}
// Even if the instruction does not write memory it could e.g. return the
// address of global memory. Therefore we have to define it as escaping.
setEscapesGlobal(ConGraph, I);
}
void EscapeAnalysis::recompute(FunctionInfo *Initial) {
allocNewUpdateID();
DEBUG(llvm::dbgs() << "recompute escape analysis with UpdateID " <<
getCurrentUpdateID() << '\n');
// Collect and analyze all functions to recompute, starting at Initial.
FunctionOrder BottomUpOrder(getCurrentUpdateID());
buildConnectionGraph(Initial, BottomUpOrder, 0);
// Build the bottom-up order.
BottomUpOrder.tryToSchedule(Initial);
BottomUpOrder.finishScheduling();
// Second step: propagate the connection graphs up the call-graph until it
// stabilizes.
int Iteration = 0;
bool NeedAnotherIteration;
do {
DEBUG(llvm::dbgs() << "iteration " << Iteration << '\n');
NeedAnotherIteration = false;
for (FunctionInfo *FInfo : BottomUpOrder) {
bool SummaryGraphChanged = false;
if (FInfo->NeedUpdateSummaryGraph) {
DEBUG(llvm::dbgs() << " create summary graph for " <<
FInfo->Graph.F->getName() << '\n');
FInfo->Graph.propagateEscapeStates();
// Derive the summary graph of the current function. Even if the
// complete graph of the function did change, it does not mean that the
// summary graph will change.
SummaryGraphChanged = mergeSummaryGraph(&FInfo->SummaryGraph,
&FInfo->Graph);
FInfo->NeedUpdateSummaryGraph = false;
}
if (Iteration < MaxGraphMerges) {
// In the first iteration we have to merge the summary graphs, even if
// they didn't change (in not recomputed leaf functions).
if (Iteration == 0 || SummaryGraphChanged) {
// Merge the summary graph into all callers.
for (const auto &E : FInfo->getCallers()) {
assert(E.isValid());
// Only include callers which we are actually recomputing.
if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(E.Caller)) {
DEBUG(llvm::dbgs() << " merge " << FInfo->Graph.F->getName() <<
" into " << E.Caller->Graph.F->getName() << '\n');
if (mergeCalleeGraph(E.FAS, &E.Caller->Graph,
&FInfo->SummaryGraph)) {
E.Caller->NeedUpdateSummaryGraph = true;
if (!E.Caller->isScheduledAfter(FInfo)) {
// This happens if we have a cycle in the call-graph.
NeedAnotherIteration = true;
}
}
}
}
}
} else if (Iteration == MaxGraphMerges) {
// Limit the total number of iterations. First to limit compile time,
// second to make sure that the loop terminates. Theoretically this
// should always be the case, but who knows?
DEBUG(llvm::dbgs() << " finalize conservatively " <<
FInfo->Graph.F->getName() << '\n');
for (const auto &E : FInfo->getCallers()) {
assert(E.isValid());
if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(E.Caller)) {
setAllEscaping(E.FAS.getInstruction(), &E.Caller->Graph);
E.Caller->NeedUpdateSummaryGraph = true;
NeedAnotherIteration = true;
}
}
}
}
Iteration++;
} while (NeedAnotherIteration);
for (FunctionInfo *FInfo : BottomUpOrder) {
if (BottomUpOrder.wasRecomputedWithCurrentUpdateID(FInfo)) {
FInfo->Graph.computeUsePoints();
FInfo->Graph.verify();
FInfo->SummaryGraph.verify();
}
}
}
bool EscapeAnalysis::mergeCalleeGraph(FullApplySite FAS,
ConnectionGraph *CallerGraph,
ConnectionGraph *CalleeGraph) {
CGNodeMap Callee2CallerMapping;
// First map the callee parameters to the caller arguments.
SILFunction *Callee = CalleeGraph->F;
unsigned numCallerArgs = FAS.getNumArguments();
unsigned numCalleeArgs = Callee->getArguments().size();
assert(numCalleeArgs >= numCallerArgs);
for (unsigned Idx = 0; Idx < numCalleeArgs; ++Idx) {
// If there are more callee parameters than arguments it means that the
// callee is the result of a partial_apply - a thick function. A thick
// function also references the boxed partially applied arguments.
// Therefore we map all the extra callee parameters to the callee operand
// of the apply site.
SILValue CallerArg = (Idx < numCallerArgs ? FAS.getArgument(Idx) :
FAS.getCallee());
CGNode *CalleeNd = CalleeGraph->getNode(Callee->getArgument(Idx), this);
if (!CalleeNd)
continue;
CGNode *CallerNd = CallerGraph->getNode(CallerArg, this);
// There can be the case that we see a callee argument as pointer but not
// the caller argument. E.g. if the callee argument has a @convention(c)
// function type and the caller passes a function_ref.
if (!CallerNd)
continue;
Callee2CallerMapping.add(CalleeNd, CallerNd);
}
// Map the return value.
if (CGNode *RetNd = CalleeGraph->getReturnNodeOrNull()) {
ValueBase *CallerReturnVal = nullptr;
if (auto *TAI = dyn_cast<TryApplyInst>(FAS.getInstruction())) {
CallerReturnVal = TAI->getNormalBB()->getBBArg(0);
} else {
CallerReturnVal = FAS.getInstruction();
}
CGNode *CallerRetNd = CallerGraph->getNode(CallerReturnVal, this);
Callee2CallerMapping.add(RetNd, CallerRetNd);
}
return CallerGraph->mergeFrom(CalleeGraph, Callee2CallerMapping);
}
bool EscapeAnalysis::mergeSummaryGraph(ConnectionGraph *SummaryGraph,
ConnectionGraph *Graph) {
// Make a 1-to-1 mapping of all arguments and the return value.
CGNodeMap Mapping;
for (SILArgument *Arg : Graph->F->getArguments()) {
if (CGNode *ArgNd = Graph->getNode(Arg, this)) {
Mapping.add(ArgNd, SummaryGraph->getNode(Arg, this));
}
}
if (CGNode *RetNd = Graph->getReturnNodeOrNull()) {
Mapping.add(RetNd, SummaryGraph->getReturnNode());
}
// Merging actually creates the summary graph.
return SummaryGraph->mergeFrom(Graph, Mapping);
}
bool EscapeAnalysis::canEscapeToUsePoint(SILValue V, ValueBase *UsePoint,
ConnectionGraph *ConGraph) {
assert((FullApplySite::isa(UsePoint) || isa<RefCountingInst>(UsePoint)) &&
"use points are only created for calls and refcount instructions");
CGNode *Node = ConGraph->getNodeOrNull(V, this);
if (!Node)
return true;
// First check if there are escape paths which we don't explicitly see
// in the graph.
if (Node->escapesInsideFunction(isNotAliasingArgument(V)))
return true;
// No hidden escapes: check if the Node is reachable from the UsePoint.
return ConGraph->isUsePoint(UsePoint, Node);
}
bool EscapeAnalysis::canEscapeTo(SILValue V, FullApplySite FAS) {
// If it's not a local object we don't know anything about the value.
if (!pointsToLocalObject(V))
return true;
auto *ConGraph = getConnectionGraph(FAS.getFunction());
return canEscapeToUsePoint(V, FAS.getInstruction(), ConGraph);
}
static bool hasReferenceSemantics(SILType T) {
// Exclude address types.
return T.isObject() && T.hasReferenceSemantics();
}
bool EscapeAnalysis::canObjectOrContentEscapeTo(SILValue V, FullApplySite FAS) {
// If it's not a local object we don't know anything about the value.
if (!pointsToLocalObject(V))
return true;
auto *ConGraph = getConnectionGraph(FAS.getFunction());
CGNode *Node = ConGraph->getNodeOrNull(V, this);
if (!Node)
return true;
// First check if there are escape paths which we don't explicitly see
// in the graph.
if (Node->escapesInsideFunction(isNotAliasingArgument(V)))
return true;
// Check if the object itself can escape to the called function.
SILInstruction *UsePoint = FAS.getInstruction();
if (ConGraph->isUsePoint(UsePoint, Node))
return true;
if (hasReferenceSemantics(V->getType())) {
// Check if the object "content", i.e. a pointer to one of its stored
// properties, can escape to the called function.
CGNode *ContentNode = ConGraph->getContentNode(Node);
if (ContentNode->escapesInsideFunction(false))
return true;
if (ConGraph->isUsePoint(UsePoint, ContentNode))
return true;
}
return false;
}
bool EscapeAnalysis::canEscapeTo(SILValue V, RefCountingInst *RI) {
// If it's not a local object we don't know anything about the value.
if (!pointsToLocalObject(V))
return true;
auto *ConGraph = getConnectionGraph(RI->getFunction());
return canEscapeToUsePoint(V, RI, ConGraph);
}
/// Utility to get the function which contains both values \p V1 and \p V2.
static SILFunction *getCommonFunction(SILValue V1, SILValue V2) {
SILBasicBlock *BB1 = V1->getParentBB();
SILBasicBlock *BB2 = V2->getParentBB();
if (!BB1 || !BB2)
return nullptr;
SILFunction *F = BB1->getParent();
assert(BB2->getParent() == F && "values not in same function");
return F;
}
bool EscapeAnalysis::canEscapeToValue(SILValue V, SILValue To) {
if (!pointsToLocalObject(V))
return true;
SILFunction *F = getCommonFunction(V, To);
if (!F)
return true;
auto *ConGraph = getConnectionGraph(F);
CGNode *Node = ConGraph->getNodeOrNull(V, this);
if (!Node)
return true;
CGNode *ToNode = ConGraph->getNodeOrNull(To, this);
if (!ToNode)
return true;
return ConGraph->isReachable(Node, ToNode);
}
bool EscapeAnalysis::canPointToSameMemory(SILValue V1, SILValue V2) {
// At least one of the values must be a non-escaping local object.
bool isLocal1 = pointsToLocalObject(V1);
bool isLocal2 = pointsToLocalObject(V2);
if (!isLocal1 && !isLocal2)
return true;
SILFunction *F = getCommonFunction(V1, V2);
if (!F)
return true;
auto *ConGraph = getConnectionGraph(F);
CGNode *Node1 = ConGraph->getNodeOrNull(V1, this);
if (!Node1)
return true;
CGNode *Node2 = ConGraph->getNodeOrNull(V2, this);
if (!Node2)
return true;
// Finish the check for one value being a non-escaping local object.
if (isLocal1 && Node1->escapesInsideFunction(isNotAliasingArgument(V1)))
isLocal1 = false;
if (isLocal2 && Node2->escapesInsideFunction(isNotAliasingArgument(V2)))
isLocal2 = false;
if (!isLocal1 && !isLocal2)
return true;
// Check if both nodes may point to the same content.
CGNode *Content1 = ConGraph->getContentNode(Node1);
CGNode *Content2 = ConGraph->getContentNode(Node2);
SILType T1 = V1->getType();
SILType T2 = V2->getType();
if (T1.isAddress() && T2.isAddress()) {
return Content1 == Content2;
}
if (hasReferenceSemantics(T1) && hasReferenceSemantics(T2)) {
return Content1 == Content2;
}
// As we model the ref_element_addr instruction as a content-relationship, we
// have to go down one content level if just one of the values is a
// ref-counted object.
if (T1.isAddress() && hasReferenceSemantics(T2)) {
Content2 = ConGraph->getContentNode(Content2);
return Content1 == Content2;
}
if (T2.isAddress() && hasReferenceSemantics(T1)) {
Content1 = ConGraph->getContentNode(Content1);
return Content1 == Content2;
}
return true;
}
bool EscapeAnalysis::canParameterEscape(FullApplySite FAS, int ParamIdx,
bool checkContentOfIndirectParam) {
CalleeList Callees = BCA->getCalleeList(FAS);
if (!Callees.allCalleesVisible())
return true;
// Derive the connection graph of the apply from the known callees.
for (SILFunction *Callee : Callees) {
FunctionInfo *FInfo = getFunctionInfo(Callee);
if (!FInfo->isValid())
recompute(FInfo);
CGNode *Node = FInfo->SummaryGraph.getNodeOrNull(
Callee->getArgument(ParamIdx), this);
if (!Node)
return true;
if (checkContentOfIndirectParam) {
Node = Node->getContentNodeOrNull();
if (!Node)
continue;
}
if (Node->escapes())
return true;
}
return false;
}
void EscapeAnalysis::invalidate(InvalidationKind K) {
Function2Info.clear();
Allocator.DestroyAll();
DEBUG(llvm::dbgs() << "invalidate all\n");
}
void EscapeAnalysis::invalidate(SILFunction *F, InvalidationKind K) {
if (FunctionInfo *FInfo = Function2Info.lookup(F)) {
DEBUG(llvm::dbgs() << " invalidate " << FInfo->Graph.F->getName() << '\n');
invalidateIncludingAllCallers(FInfo);
}
}
void EscapeAnalysis::handleDeleteNotification(ValueBase *I) {
if (SILBasicBlock *Parent = I->getParentBB()) {
SILFunction *F = Parent->getParent();
if (FunctionInfo *FInfo = Function2Info.lookup(F)) {
if (FInfo->isValid()) {
FInfo->Graph.removeFromGraph(I);
FInfo->SummaryGraph.removeFromGraph(I);
}
}
}
}
SILAnalysis *swift::createEscapeAnalysis(SILModule *M) {
return new EscapeAnalysis(M);
}
Reference in New Issue View Git Blame Copy Permalink