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 {
38 WTF_MAKE_FAST_ALLOCATED;
39public:
40 PhiChildren(Procedure&);
41 ~PhiChildren();
42
43 class ValueCollection {
44 public:
45 ValueCollection(Vector<UpsilonValue*>* values = nullptr)
46 : m_values(values)
47 {
48 }
49
50 unsigned size() const { return m_values->size(); }
51 Value* at(unsigned index) const { return m_values->at(index)->child(0); }
52 Value* operator[](unsigned index) const { return at(index); }
53
54 bool contains(Value* value) const
55 {
56 for (unsigned i = size(); i--;) {
57 if (at(i) == value)
58 return true;
59 }
60 return false;
61 }
62
63 class iterator {
64 public:
65 iterator(Vector<UpsilonValue*>* values = nullptr, unsigned index = 0)
66 : m_values(values)
67 , m_index(index)
68 {
69 }
70
71 Value* operator*() const
72 {
73 return m_values->at(m_index)->child(0);
74 }
75
76 iterator& operator++()
77 {
78 m_index++;
79 return *this;
80 }
81
82 bool operator==(const iterator& other) const
83 {
84 ASSERT(m_values == other.m_values);
85 return m_index == other.m_index;
86 }
87
88 bool operator!=(const iterator& other) const
89 {
90 return !(*this == other);
91 }
92
93 private:
94 Vector<UpsilonValue*>* m_values;
95 unsigned m_index;
96 };
97
98 iterator begin() const { return iterator(m_values); }
99 iterator end() const { return iterator(m_values, m_values->size()); }
100
101 private:
102 Vector<UpsilonValue*>* m_values;
103 };
104
105 class UpsilonCollection {
106 public:
107 UpsilonCollection()
108 {
109 }
110
111 UpsilonCollection(PhiChildren* phiChildren, Value* value, Vector<UpsilonValue*>* values)
112 : m_phiChildren(phiChildren)
113 , m_value(value)
114 , m_values(values)
115 {
116 }
117
118 unsigned size() const { return m_values->size(); }
119 Value* at(unsigned index) const { return m_values->at(index); }
120 Value* operator[](unsigned index) const { return at(index); }
121
122 bool contains(Value* value) const { return m_values->contains(value); }
123
124 typedef Vector<UpsilonValue*>::const_iterator iterator;
125 Vector<UpsilonValue*>::const_iterator begin() const { return m_values->begin(); }
126 Vector<UpsilonValue*>::const_iterator end() const { return m_values->end(); }
127
128 ValueCollection values() { return ValueCollection(m_values); }
129
130 template<typename Functor>
131 void forAllTransitiveIncomingValues(const Functor& functor)
132 {
133 if (m_value->opcode() != Phi) {
134 functor(m_value);
135 return;
136 }
137
138 GraphNodeWorklist<Value*> worklist;
139 worklist.push(m_value);
140 while (Value* phi = worklist.pop()) {
141 for (Value* child : m_phiChildren->at(phi).values()) {
142 if (child->opcode() == Phi)
143 worklist.push(child);
144 else
145 functor(child);
146 }
147 }
148 }
149
150 bool transitivelyUses(Value* candidate)
151 {
152 bool result = false;
153 forAllTransitiveIncomingValues(
154 [&] (Value* child) {
155 result |= child == candidate;
156 });
157 return result;
158 }
159
160 private:
161 PhiChildren* m_phiChildren { nullptr };
162 Value* m_value { nullptr };
163 Vector<UpsilonValue*>* m_values { nullptr };
164 };
165
166 UpsilonCollection at(Value* value) { return UpsilonCollection(this, value, &m_upsilons[value]); }
167 UpsilonCollection operator[](Value* value) { return at(value); }
168
169 const Vector<Value*, 8>& phis() const { return m_phis; }
170
171private:
172 IndexMap<Value*, Vector<UpsilonValue*>> m_upsilons;
173 Vector<Value*, 8> m_phis;
174};
175
176} } // namespace JSC::B3
177
178#endif // ENABLE(B3_JIT)
179