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
|
//===--- Worklist.swift ---------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2023 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 utility for processing entities in a worklist.
///
/// A `Worklist` is basically a combination of a stack and a set.
/// It can be used for typical worklist-processing algorithms.
///
/// 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 Worklist<Set: IntrusiveSet> : CustomStringConvertible, NoReflectionChildren {
typealias Element = Set.Element
private var worklist: Stack<Element>
private var pushedElements: Set
init(_ context: some Context) {
self.worklist = Stack(context)
self.pushedElements = Set(context)
}
mutating func pop() -> Element? { return worklist.pop() }
/// Pop and allow the popped element to be pushed again to the worklist.
mutating func popAndForget() -> Element? {
if let element = worklist.pop() {
pushedElements.erase(element)
return element
}
return nil
}
mutating func pushIfNotVisited(_ element: Element) {
if pushedElements.insert(element) {
worklist.append(element)
}
}
mutating func pushIfNotVisited<S: Sequence>(contentsOf other: S) where S.Element == Element {
for element in other {
pushIfNotVisited(element)
}
}
/// Returns true if \p element was pushed to the worklist, regardless if it's already popped or not.
func hasBeenPushed(_ element: Element) -> Bool { pushedElements.contains(element) }
var isEmpty: Bool { worklist.isEmpty }
var description: String {
"""
worklist: \(worklist)
pushed: \(pushedElements)
"""
}
/// TODO: once we have move-only types, make this a real deinit.
mutating func deinitialize() {
pushedElements.deinitialize()
worklist.deinitialize()
}
}
typealias BasicBlockWorklist = Worklist<BasicBlockSet>
typealias InstructionWorklist = Worklist<InstructionSet>
typealias SpecificInstructionWorklist<InstType: Instruction> = Worklist<SpecificInstructionSet<InstType>>
typealias ValueWorklist = Worklist<ValueSet>
typealias OperandWorklist = Worklist<OperandSet>
extension InstructionWorklist {
mutating func pushPredecessors(of inst: Instruction, ignoring ignoreInst: SingleValueInstruction) {
if let prev = inst.previous {
if prev != ignoreInst {
pushIfNotVisited(prev)
}
} else {
for predBlock in inst.parentBlock.predecessors {
let termInst = predBlock.terminator
if termInst != ignoreInst {
pushIfNotVisited(termInst)
}
}
}
}
}
|
