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
|
//===--- BasicBlockRange.swift - a range of basic blocks ------------------===//
//
// 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
/// A range of basic blocks.
///
/// The `BasicBlockRange` defines a range from a dominating "begin" block to one or more "end" blocks.
/// The range is "exclusive", which means that the "end" blocks are not part of the range.
///
/// The `BasicBlockRange` is in the same spirit as a linear range, but as the control flow is a graph
/// and not a linear list, there can be "exit" blocks from within the range.
///
/// One or more "potential" end blocks can be inserted.
/// Though, not all inserted blocks end up as "end" blocks.
///
/// There are several kind of blocks:
/// * begin: it is a single block which dominates all blocks of the range
/// * range: all blocks from which there is a path from the begin block to any of the end blocks
/// * ends: all inserted blocks which are at the end of the range
/// * exits: all successor blocks of range blocks which are not in the range themselves
/// * interiors: all inserted blocks which are not end blocks.
///
/// In the following example, let's assume `B` is the begin block and `I1`, `I2` and `I3`
/// were inserted as potential end blocks:
///
/// B
/// / \
/// I1 I2
/// / \
/// I3 X
///
/// Then `I1` and `I3` are "end" blocks. `I2` is an interior block and `X` is an exit block.
/// The range consists of `B` and `I2`. Note that the range does not include `I1` and `I3`
/// because it's an _exclusive_ range.
///
/// This type should be a move-only type, but unfortunately we don't have move-only
/// types yet. Therefore it's needed to call `deinitialize()` explicitly to
/// destruct this data structure, e.g. in a `defer {}` block.
struct BasicBlockRange : CustomStringConvertible, NoReflectionChildren {
/// The dominating begin block.
let begin: BasicBlock
/// The inclusive range, i.e. the exclusive range plus the end blocks.
private(set) var inclusiveRange: Stack<BasicBlock>
/// The exclusive range, i.e. not containing the end blocks.
var range: LazyFilterSequence<Stack<BasicBlock>> {
inclusiveRange.lazy.filter { contains($0) }
}
/// All inserted blocks.
private(set) var inserted: Stack<BasicBlock>
private var wasInserted: BasicBlockSet
private var inExclusiveRange: BasicBlockSet
private var worklist: BasicBlockWorklist
init(begin: BasicBlock, _ context: some Context) {
self.begin = begin
self.inclusiveRange = Stack(context)
self.inserted = Stack(context)
self.wasInserted = BasicBlockSet(context)
self.inExclusiveRange = BasicBlockSet(context)
self.worklist = BasicBlockWorklist(context)
worklist.pushIfNotVisited(begin)
}
/// Insert a potential end block.
mutating func insert(_ block: BasicBlock) {
if wasInserted.insert(block) {
inserted.append(block)
}
worklist.pushIfNotVisited(block)
while let b = worklist.pop() {
inclusiveRange.append(b)
if b != begin {
for pred in b.predecessors {
worklist.pushIfNotVisited(pred)
inExclusiveRange.insert(pred)
}
}
}
}
/// Insert a sequence of potential end blocks.
mutating func insert<S: Sequence>(contentsOf other: S) where S.Element == BasicBlock {
for block in other {
insert(block)
}
}
/// Returns true if the exclusive range contains `block`.
func contains(_ block: BasicBlock) -> Bool { inExclusiveRange.contains(block) }
/// Returns true if the inclusive range contains `block`.
func inclusiveRangeContains (_ block: BasicBlock) -> Bool {
worklist.hasBeenPushed(block)
}
/// Returns true if the range is valid and that's iff the begin block dominates all blocks of the range.
var isValid: Bool {
let entry = begin.parentFunction.entryBlock
return begin == entry ||
// If any block in the range is not dominated by `begin`, the range propagates back to the entry block.
!inclusiveRangeContains(entry)
}
/// Returns the end blocks.
var ends: LazyFilterSequence<Stack<BasicBlock>> {
inserted.lazy.filter { !contains($0) }
}
/// Returns the exit blocks.
var exits: LazySequence<FlattenSequence<
LazyMapSequence<LazyFilterSequence<Stack<BasicBlock>>,
LazyFilterSequence<SuccessorArray>>>> {
range.flatMap {
$0.successors.lazy.filter {
!inclusiveRangeContains($0) || $0 == begin
}
}
}
/// Returns the interior blocks.
var interiors: LazyFilterSequence<Stack<BasicBlock>> {
inserted.lazy.filter { contains($0) && $0 != begin }
}
var description: String {
return (isValid ? "" : "<invalid>\n") +
"""
begin: \(begin.name)
range: \(range)
inclrange: \(inclusiveRange)
ends: \(ends)
exits: \(exits)
interiors: \(interiors)
"""
}
/// TODO: once we have move-only types, make this a real deinit.
mutating func deinitialize() {
worklist.deinitialize()
inExclusiveRange.deinitialize()
wasInserted.deinitialize()
inserted.deinitialize()
inclusiveRange.deinitialize()
}
}
|
