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
|
//===--- FunctionOrder.cpp - Utility for function ordering ----------------===//
//
// 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/FunctionOrder.h"
#include "swift/SIL/SILBasicBlock.h"
#include "swift/SIL/SILFunction.h"
#include "swift/SIL/SILInstruction.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include <algorithm>
using namespace swift;
/// Use Tarjan's strongly connected components (SCC) algorithm to find
/// the SCCs in the call graph.
void BottomUpFunctionOrder::DFS(SILFunction *Start) {
// Set the DFSNum for this node if we haven't already, and if we
// have, which indicates it's already been visited, return.
if (!DFSNum.insert(std::make_pair(Start, NextDFSNum)).second)
return;
assert(MinDFSNum.find(Start) == MinDFSNum.end() &&
"Function should not already have a minimum DFS number!");
MinDFSNum[Start] = NextDFSNum;
++NextDFSNum;
DFSStack.insert(Start);
// Visit all the instructions, looking for apply sites.
for (auto &B : *Start) {
for (auto &I : B) {
CalleeList callees;
if (auto FAS = FullApplySite::isa(&I)) {
callees = BCA->getCalleeList(FAS);
} else if (isa<StrongReleaseInst>(&I) || isa<ReleaseValueInst>(&I) ||
isa<DestroyValueInst>(&I)) {
callees = BCA->getDestructors(I.getOperand(0)->getType(), /*isExactType*/ false);
} else if (auto *bi = dyn_cast<BuiltinInst>(&I)) {
switch (bi->getBuiltinInfo().ID) {
case BuiltinValueKind::Once:
case BuiltinValueKind::OnceWithContext:
callees = BCA->getCalleeListOfValue(bi->getArguments()[1]);
break;
default:
continue;
}
} else {
continue;
}
for (auto *CalleeFn : callees) {
// If not yet visited, visit the callee.
if (DFSNum.find(CalleeFn) == DFSNum.end()) {
DFS(CalleeFn);
MinDFSNum[Start] = std::min(MinDFSNum[Start], MinDFSNum[CalleeFn]);
} else if (DFSStack.count(CalleeFn)) {
// If the callee is on the stack, it update our minimum DFS
// number based on it's DFS number.
MinDFSNum[Start] = std::min(MinDFSNum[Start], DFSNum[CalleeFn]);
}
}
}
}
// If our DFS number is the minimum found, we've found a
// (potentially singleton) SCC, so pop the nodes off the stack and
// push the new SCC on our stack of SCCs.
if (DFSNum[Start] == MinDFSNum[Start]) {
SCC CurrentSCC;
SILFunction *Popped;
do {
Popped = DFSStack.pop_back_val();
CurrentSCC.push_back(Popped);
} while (Popped != Start);
TheSCCs.push_back(CurrentSCC);
}
}
void BottomUpFunctionOrder::FindSCCs(SILModule &M) {
for (auto &F : M)
DFS(&F);
}
|
