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
|
//===--- ColdBlockInfo.cpp - Fast/slow path analysis for the SIL CFG ------===//
//
// 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/ColdBlockInfo.h"
#include "swift/SILOptimizer/Analysis/DominanceAnalysis.h"
#include "swift/SIL/SILArgument.h"
#include "swift/AST/SemanticAttrs.h"
using namespace swift;
/// Peek through an extract of Bool.value.
static SILValue getCondition(SILValue C) {
if (auto *SEI = dyn_cast<StructExtractInst>(C)) {
if (auto *Struct = dyn_cast<StructInst>(SEI->getOperand()))
return Struct->getFieldValue(SEI->getField());
return SEI->getOperand();
}
return C;
}
/// \return a BranchHint if this call is a builtin branch hint.
ColdBlockInfo::BranchHint ColdBlockInfo::getBranchHint(SILValue Cond,
int recursionDepth) {
// Handle the fully inlined Builtin.
if (auto *BI = dyn_cast<BuiltinInst>(Cond)) {
if (BI->getIntrinsicInfo().ID == llvm::Intrinsic::expect) {
// peek through an extract of Bool.value.
SILValue ExpectedValue = getCondition(BI->getArguments()[1]);
if (auto *Literal = dyn_cast<IntegerLiteralInst>(ExpectedValue)) {
return (Literal->getValue() == 0)
? BranchHint::LikelyFalse : BranchHint::LikelyTrue;
}
}
return BranchHint::None;
}
if (auto *Arg = dyn_cast<SILArgument>(Cond)) {
llvm::SmallVector<std::pair<SILBasicBlock *, SILValue>, 4> InValues;
if (!Arg->getIncomingPhiValues(InValues))
return BranchHint::None;
if (recursionDepth > RecursionDepthLimit)
return BranchHint::None;
BranchHint Hint = BranchHint::None;
// Check all predecessor values which come from non-cold blocks.
for (auto Pair : InValues) {
if (isCold(Pair.first, recursionDepth + 1))
continue;
auto *IL = dyn_cast<IntegerLiteralInst>(Pair.second);
if (!IL)
return BranchHint::None;
// Check if we have a consistent value for all non-cold predecessors.
if (IL->getValue().getBoolValue()) {
if (Hint == BranchHint::LikelyFalse)
return BranchHint::None;
Hint = BranchHint::LikelyTrue;
} else {
if (Hint == BranchHint::LikelyTrue)
return BranchHint::None;
Hint = BranchHint::LikelyFalse;
}
}
return Hint;
}
// Handle the @semantic functions used for branch hints.
auto AI = dyn_cast<ApplyInst>(Cond);
if (!AI)
return BranchHint::None;
if (auto *F = AI->getReferencedFunctionOrNull()) {
if (F->hasSemanticsAttrs()) {
// fastpath/slowpath attrs are untested because the inliner luckily
// inlines them before the downstream calls.
if (F->hasSemanticsAttr(semantics::SLOWPATH))
return BranchHint::LikelyFalse;
else if (F->hasSemanticsAttr(semantics::FASTPATH))
return BranchHint::LikelyTrue;
}
}
return BranchHint::None;
}
/// \return true if the CFG edge FromBB->ToBB is directly gated by a _slowPath
/// branch hint.
bool ColdBlockInfo::isSlowPath(const SILBasicBlock *FromBB,
const SILBasicBlock *ToBB,
int recursionDepth) {
auto *CBI = dyn_cast<CondBranchInst>(FromBB->getTerminator());
if (!CBI)
return false;
SILValue C = getCondition(CBI->getCondition());
BranchHint hint = getBranchHint(C, recursionDepth);
if (hint == BranchHint::None)
return false;
const SILBasicBlock *ColdTarget =
(hint == BranchHint::LikelyTrue) ? CBI->getFalseBB() : CBI->getTrueBB();
return ToBB == ColdTarget;
}
/// \return true if the given block is dominated by a _slowPath branch hint.
///
/// Cache all blocks visited to avoid introducing quadratic behavior.
bool ColdBlockInfo::isCold(const SILBasicBlock *BB, int recursionDepth) {
auto I = ColdBlockMap.find(BB);
if (I != ColdBlockMap.end())
return I->second;
typedef llvm::DomTreeNodeBase<SILBasicBlock> DomTreeNode;
DominanceInfo *DT = DA->get(const_cast<SILFunction*>(BB->getParent()));
DomTreeNode *Node = DT->getNode(const_cast<SILBasicBlock*>(BB));
// Always consider unreachable code cold.
if (!Node)
return true;
std::vector<const SILBasicBlock*> DomChain;
DomChain.push_back(BB);
bool IsCold = false;
Node = Node->getIDom();
while (Node) {
if (isSlowPath(Node->getBlock(), DomChain.back(), recursionDepth)) {
IsCold = true;
break;
}
auto I = ColdBlockMap.find(Node->getBlock());
if (I != ColdBlockMap.end()) {
IsCold = I->second;
break;
}
DomChain.push_back(Node->getBlock());
Node = Node->getIDom();
}
for (auto *ChainBB : DomChain)
ColdBlockMap[ChainBB] = IsCold;
return IsCold;
}
|
