1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#if ENABLE(B3_JIT)
29
30#include "B3Procedure.h"
31#include "B3UpsilonValue.h"
32#include <wtf/GraphNodeWorklist.h>
33#include <wtf/IndexMap.h>
34
35namespace JSC { namespace B3 {
36
37class PhiChildren {
38public:
39 PhiChildren(Procedure&);
40 ~PhiChildren();
41
42 class ValueCollection {
43 public:
44 ValueCollection(Vector<UpsilonValue*>* values = nullptr)
45 : m_values(values)
46 {
47 }
48
49 unsigned size() const { return m_values->size(); }
50 Value* at(unsigned index) const { return m_values->at(index)->child(0); }
51 Value* operator[](unsigned index) const { return at(index); }
52
53 bool contains(Value* value) const
54 {
55 for (unsigned i = size(); i--;) {
56 if (at(i) == value)
57 return true;
58 }
59 return false;
60 }
61
62 class iterator {
63 public:
64 iterator(Vector<UpsilonValue*>* values = nullptr, unsigned index = 0)
65 : m_values(values)
66 , m_index(index)
67 {
68 }
69
70 Value* operator*() const
71 {
72 return m_values->at(m_index)->child(0);
73 }
74
75 iterator& operator++()
76 {
77 m_index++;
78 return *this;
79 }
80
81 bool operator==(const iterator& other) const
82 {
83 ASSERT(m_values == other.m_values);
84 return m_index == other.m_index;
85 }
86
87 bool operator!=(const iterator& other) const
88 {
89 return !(*this == other);
90 }
91
92 private:
93 Vector<UpsilonValue*>* m_values;
94 unsigned m_index;
95 };
96
97 iterator begin() const { return iterator(m_values); }
98 iterator end() const { return iterator(m_values, m_values->size()); }
99
100 private:
101 Vector<UpsilonValue*>* m_values;
102 };
103
104 class UpsilonCollection {
105 public:
106 UpsilonCollection()
107 {
108 }
109
110 UpsilonCollection(PhiChildren* phiChildren, Value* value, Vector<UpsilonValue*>* values)
111 : m_phiChildren(phiChildren)
112 , m_value(value)
113 , m_values(values)
114 {
115 }
116
117 unsigned size() const { return m_values->size(); }
118 Value* at(unsigned index) const { return m_values->at(index); }
119 Value* operator[](unsigned index) const { return at(index); }
120
121 bool contains(Value* value) const { return m_values->contains(value); }
122
123 typedef Vector<UpsilonValue*>::const_iterator iterator;
124 Vector<UpsilonValue*>::const_iterator begin() const { return m_values->begin(); }
125 Vector<UpsilonValue*>::const_iterator end() const { return m_values->end(); }
126
127 ValueCollection values() { return ValueCollection(m_values); }
128
129 template<typename Functor>
130 void forAllTransitiveIncomingValues(const Functor& functor)
131 {
132 if (m_value->opcode() != Phi) {
133 functor(m_value);
134 return;
135 }
136
137 GraphNodeWorklist<Value*> worklist;
138 worklist.push(m_value);
139 while (Value* phi = worklist.pop()) {
140 for (Value* child : m_phiChildren->at(phi).values()) {
141 if (child->opcode() == Phi)
142 worklist.push(child);
143 else
144 functor(child);
145 }
146 }
147 }
148
149 bool transitivelyUses(Value* candidate)
150 {
151 bool result = false;
152 forAllTransitiveIncomingValues(
153 [&] (Value* child) {
154 result |= child == candidate;
155 });
156 return result;
157 }
158
159 private:
160 PhiChildren* m_phiChildren { nullptr };
161 Value* m_value { nullptr };
162 Vector<UpsilonValue*>* m_values { nullptr };
163 };
164
165 UpsilonCollection at(Value* value) { return UpsilonCollection(this, value, &m_upsilons[value]); }
166 UpsilonCollection operator[](Value* value) { return at(value); }
167
168 const Vector<Value*, 8>& phis() const { return m_phis; }
169
170private:
171 IndexMap<Value*, Vector<UpsilonValue*>> m_upsilons;
172 Vector<Value*, 8> m_phis;
173};
174
175} } // namespace JSC::B3
176
177#endif // ENABLE(B3_JIT)
178