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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
//===--- InstructionRange.swift - a range of instructions -----------------===//
//
// 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 instructions.
///
/// The `InstructionRange` defines a range from a dominating "begin" instruction to one or more "end" instructions.
/// The range is "exclusive", which means that the "end" instructions are not part of the range.
///
/// One or more "potential" end instructions can be inserted.
/// Though, not all inserted instructions end up as "end" instructions.
///
/// `InstructionRange` is useful for calculating the liferange of values.
///
/// The `InstructionRange` is similar to a `BasicBlockRange`, but defines the range
/// in a "finer" granularity, i.e. on instructions instead of blocks.
/// `InstructionRange` uses an underlying `BasicBlockRange` to compute the
/// involved blocks of the instruction range.
///
/// There are several kind of instructions:
/// * begin: it is a single instruction which dominates all instructions of the range
/// * ends: all inserted instruction which are at the end of the range
/// * exits: the first instructions of the exit blocks
/// * interiors: all inserted instructions which are not end instructions.
///
/// See also `BasicBlockRange` for more information.
///
/// 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 InstructionRange : CustomStringConvertible, NoReflectionChildren {
/// The dominating begin instruction.
let begin: Instruction
/// The underlying block range.
private(set) var blockRange: BasicBlockRange
private var insertedInsts: InstructionSet
// For efficiency, this set does not include instructions in blocks which are not the begin or any end block.
private var inExclusiveRange: InstructionSet
init(begin beginInst: Instruction, _ context: some Context) {
self.begin = beginInst
self.blockRange = BasicBlockRange(begin: beginInst.parentBlock, context)
self.insertedInsts = InstructionSet(context)
self.inExclusiveRange = InstructionSet(context)
self.inExclusiveRange.insert(beginInst)
}
init(for value: Value, _ context: some Context) {
self = InstructionRange(begin: InstructionRange.beginningInstruction(for: value), context)
}
static func beginningInstruction(for value: Value) -> Instruction {
if let def = value.definingInstructionOrTerminator {
return def
}
assert(Phi(value) != nil || value is FunctionArgument)
return value.parentBlock.instructions.first!
}
/// Insert a potential end instruction.
mutating func insert(_ inst: Instruction) {
insertedInsts.insert(inst)
insertIntoRange(instructions: ReverseInstructionList(first: inst.previous))
blockRange.insert(inst.parentBlock)
if inst.parentBlock != begin.parentBlock {
// The first time an instruction is inserted in another block than the begin-block we need to insert
// instructions from the begin instruction to the end of the begin block.
// For subsequent insertions this is a no-op: `insertIntoRange` will return immediately because those
// instruction are already inserted.
insertIntoRange(instructions: begin.parentBlock.instructions.reversed())
}
}
/// Insert a sequence of potential end instructions.
mutating func insert<S: Sequence>(contentsOf other: S) where S.Element: Instruction {
for inst in other {
insert(inst)
}
}
/// Returns true if the exclusive range contains `inst`.
func contains(_ inst: Instruction) -> Bool {
if inExclusiveRange.contains(inst) {
return true
}
let block = inst.parentBlock
return block != begin.parentBlock && blockRange.contains(block)
}
/// Returns true if the inclusive range contains `inst`.
func inclusiveRangeContains (_ inst: Instruction) -> Bool {
contains(inst) || insertedInsts.contains(inst)
}
/// Returns true if the range is valid and that's iff the begin instruction
/// dominates all instructions of the range.
var isValid: Bool {
blockRange.isValid &&
// Check if there are any inserted instructions before the begin instruction in its block.
!ReverseInstructionList(first: begin).dropFirst().contains { insertedInsts.contains($0) }
}
/// Returns the end instructions.
///
/// Warning: this returns `begin` if no instructions were inserted.
var ends: LazyMapSequence<LazyFilterSequence<Stack<BasicBlock>>, Instruction> {
blockRange.ends.map {
$0.instructions.reversed().first(where: { insertedInsts.contains($0)})!
}
}
// Returns the exit blocks.
var exitBlocks: LazySequence<FlattenSequence<
LazyMapSequence<LazyFilterSequence<Stack<BasicBlock>>,
LazyFilterSequence<SuccessorArray>>>> {
blockRange.exits
}
/// Returns the exit instructions.
var exits: LazyMapSequence<LazySequence<FlattenSequence<
LazyMapSequence<LazyFilterSequence<Stack<BasicBlock>>,
LazyFilterSequence<SuccessorArray>>>>,
Instruction> {
blockRange.exits.lazy.map { $0.instructions.first! }
}
/// Returns the interior instructions.
var interiors: LazySequence<FlattenSequence<
LazyMapSequence<Stack<BasicBlock>,
LazyFilterSequence<ReverseInstructionList>>>> {
blockRange.inserted.lazy.flatMap {
var include = blockRange.contains($0)
return $0.instructions.reversed().lazy.filter {
if insertedInsts.contains($0) {
let isInterior = include
include = true
return isInterior
}
return false
}
}
}
private mutating func insertIntoRange(instructions: ReverseInstructionList) {
for inst in instructions {
if !inExclusiveRange.insert(inst) {
return
}
}
}
var description: String {
return (isValid ? "" : "<invalid>\n") +
"""
begin: \(begin)
ends: \(ends.map { $0.description }.joined(separator: "\n "))
exits: \(exits.map { $0.description }.joined(separator: "\n "))
interiors:\(interiors.map { $0.description }.joined(separator: "\n "))
"""
}
/// TODO: once we have move-only types, make this a real deinit.
mutating func deinitialize() {
inExclusiveRange.deinitialize()
insertedInsts.deinitialize()
blockRange.deinitialize()
}
}
|
