1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
//===--- ClassHierarchyAnalysis.cpp - Class hierarchy analysis ------------===//
//
// 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/ClassHierarchyAnalysis.h"
#include "swift/AST/ASTContext.h"
#include "swift/AST/Module.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILValue.h"
#include "swift/SIL/SILModule.h"
using namespace swift;
// FIXME: This could be implemented as a request.
void ClassHierarchyAnalysis::populateDirectSubclassesCacheIfNecessary() {
if (DirectSubclassesCache.has_value())
return;
DirectSubclassesCache.emplace();
auto module = M->getSwiftModule();
// For each class declaration in our V-table list:
for (auto &VT : M->getVTables()) {
ClassDecl *C = VT->getClass();
while (true) {
// Ignore classes that are at the top of the class hierarchy:
if (!C->hasSuperclass())
break;
ClassDecl *super = C->getSuperclassDecl();
auto superModule = super->getModuleContext();
// Don't bother collecting subclasses for classes from a different module.
// TODO: cross-module WMO
if (superModule != module)
break;
// Find the superclass's list of direct subclasses. If it's non-empty,
// we've previously walked up to the class, so there's no reason to keep
// walking from this point.
auto &list = (*DirectSubclassesCache)[super];
bool shouldVisitSuper = list.empty();
// Check whether C is already in the list, which can happen
// if we had a v-table that was a subclass of C.
// We expect a linear scan to be cheap enough for this.
if (std::find(list.begin(), list.end(), C) != list.end())
break;
list.push_back(C);
// Keep walking if this is the first time we reached this superclass.
// We have to do this because the SILModule might not have v-tables for
// every class in the module.
if (!shouldVisitSuper)
break;
C = super;
}
}
}
/// Get all subclasses of a given class.
///
/// \p Current class, whose direct and indirect subclasses are
/// to be collected.
/// \p IndirectSubs placeholder for collected results
void ClassHierarchyAnalysis::getIndirectSubClasses(ClassDecl *Cur,
ClassList &IndirectSubs) {
unsigned Idx = IndirectSubs.size();
if (!hasKnownDirectSubclasses(Cur))
return;
// Produce a set of all indirect subclasses in a
// breadth-first order;
// First add subclasses of direct subclasses.
for (auto C : getDirectSubClasses(Cur)) {
// Get direct subclasses
if (!hasKnownDirectSubclasses(C))
continue;
auto &DirectSubclasses = getDirectSubClasses(C);
// Remember all direct subclasses of the current one.
for (auto S : DirectSubclasses) {
IndirectSubs.push_back(S);
}
}
// Then recursively add direct subclasses of already
// added subclasses.
while (Idx != IndirectSubs.size()) {
auto C = IndirectSubs[Idx++];
// Get direct subclasses
if (!hasKnownDirectSubclasses(C))
continue;
auto &DirectSubclasses = getDirectSubClasses(C);
// Remember all direct subclasses of the current one.
for (auto S : DirectSubclasses) {
IndirectSubs.push_back(S);
}
}
}
ClassHierarchyAnalysis::~ClassHierarchyAnalysis() {}
|
