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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
//===--- FunctionUses.swift -----------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2022 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
//
//===----------------------------------------------------------------------===//
import SIL
/// Provides a list of instructions, which reference a function.
///
/// A function "use" is an instruction in another (or the same) function which
/// references the function. In most cases those are `function_ref` instructions,
/// but can also be e.g. `keypath` instructions.
///
/// 'FunctionUses' performs an analysis of all functions in the module and collects
/// instructions which reference other functions. This utility can be used to do
/// inter-procedural caller-analysis.
///
/// In order to use `FunctionUses`, first call `collect()` and then get use-lists of
/// functions with `getUses(of:)`.
struct FunctionUses {
// Function uses are stored in a single linked list, whereas the "next" is not a pointer
// but an index into `FunctionUses.useStorage`.
fileprivate struct Use {
// The index of the next use in `FunctionUses.useStorage`.
let next: Int?
// The instruction which references the function.
let usingInstruction: Instruction
}
// The head of the single-linked list of function uses.
fileprivate struct FirstUse {
// The head of the use-list.
var first: Int?
// True if the function has unknown uses
var hasUnknownUses: Bool
init(of function: Function) {
self.hasUnknownUses = function.isPossiblyUsedExternally || function.isAvailableExternally
}
mutating func insert(_ inst: Instruction, _ uses: inout [Use]) {
let newFirst = uses.count
uses.append(Use(next: first, usingInstruction: inst))
first = newFirst
}
}
/// The list of uses of a function.
struct UseList : CollectionLikeSequence, CustomStringConvertible {
struct Iterator : IteratorProtocol {
fileprivate let useStorage: [Use]
fileprivate var currentUseIdx: Int?
mutating func next() -> Instruction? {
if let useIdx = currentUseIdx {
let use = useStorage[useIdx]
currentUseIdx = use.next
return use.usingInstruction
}
return nil
}
}
// The "storage" for all function uses.
fileprivate let useStorage: [Use]
// The head of the single-linked use list.
fileprivate let firstUse: FirstUse
/// True if the function has unknown uses in addition to the list of referencing instructions.
///
/// This is the case, e.g. if the function has public linkage or if the function
/// is referenced from a vtable or witness table.
var hasUnknownUses: Bool { firstUse.hasUnknownUses }
func makeIterator() -> Iterator {
return Iterator(useStorage: useStorage, currentUseIdx: firstUse.first)
}
var description: String {
var result = "[\n"
if hasUnknownUses {
result += "<unknown uses>\n"
}
for inst in self {
result += "@\(inst.parentFunction.name): \(inst)\n"
}
result += "]"
return result
}
var customMirror: Mirror { Mirror(self, children: []) }
}
// The "storage" for all function uses.
private var useStorage: [Use] = []
// The use-list head for each function.
private var uses: [Function: FirstUse] = [:]
/// Returns the use-list of `function`.
///
/// Note that `collect` must be called before `getUses` can be used.
func getUses(of function: Function) -> UseList {
UseList(useStorage: useStorage, firstUse: uses[function, default: FirstUse(of: function)])
}
/// Collects all uses of all function in the module.
mutating func collect(context: ModulePassContext) {
// Already start with a reasonable big capacity to reduce the number of
// re-allocations when appending to the data structures.
useStorage.reserveCapacity(128)
uses.reserveCapacity(64)
// Mark all functions, which are referenced from tables, to have "unknown" uses.
for vTable in context.vTables {
for entry in vTable.entries {
markUnknown(entry.function)
}
}
for witnessTable in context.witnessTables {
for entry in witnessTable.entries {
if entry.kind == .Method, let f = entry.methodFunction {
markUnknown(f)
}
}
}
for witnessTable in context.defaultWitnessTables {
for entry in witnessTable.entries {
if entry.kind == .Method, let f = entry.methodFunction {
markUnknown(f)
}
}
}
// Collect all instructions, which reference functions, in the module.
for function in context.functions {
for inst in function.instructions {
inst.visitReferencedFunctions { referencedFunc in
uses[referencedFunc, default: FirstUse(of: referencedFunc)].insert(inst, &useStorage)
}
}
}
}
private mutating func markUnknown(_ function: Function) {
uses[function, default: FirstUse(of: function)].hasUnknownUses = true
}
}
|
