1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #include "ecmascript/compiler/value_numbering.h"
16 #include <cstddef>
17
18 namespace panda::ecmascript::kungfu {
19
VisitGate(GateRef gate)20 GateRef ValueNumbering::VisitGate(GateRef gate)
21 {
22 size_t hash = HashCode(gate);
23 auto opcode = acc_.GetOpCode(gate);
24 if (opcode != OpCode::CONVERT && !useNewGVN_) {
25 return Circuit::NullGate();
26 }
27 if (acc_.GetStateCount(gate) > 0 || acc_.GetDependCount(gate) > 0) {
28 return Circuit::NullGate();
29 }
30
31 if (entries_ == nullptr) {
32 InitEntries(entriesLength_);
33 SetEntry(hash, gate);
34 entriesSize_++;
35 return Circuit::NullGate();
36 }
37 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_);
38 const size_t mask = entriesLength_ - 1;
39 size_t dead = entriesLength_;
40 for (size_t i = hash & mask;; i = (i + 1) & mask) {
41 GateRef entry = entries_[i];
42 if (entry == Circuit::NullGate()) {
43 if (dead != entriesLength_) {
44 entries_[dead] = gate;
45 } else {
46 // Have to insert a new entry.
47 entries_[i] = gate;
48 entriesSize_++;
49 // Resize to keep load factor below 80%
50 EnsureCapacity();
51 }
52 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_);
53 return Circuit::NullGate();
54 }
55
56 if (entry == gate) {
57 return Circuit::NullGate();
58 }
59
60 // Skip dead entries, but remember their indices so we can reuse them.
61 if (acc_.IsNop(entry)) {
62 dead = i;
63 continue;
64 }
65
66 if (CheckReplacement(gate, entry)) {
67 optimizedGateCount++;
68 if (enableLog_) {
69 LOG_COMPILER(INFO) << "Found a replaceable node, before -> after";
70 acc_.Print(gate);
71 acc_.Print(entry);
72 }
73 return entry;
74 }
75 }
76 return Circuit::NullGate();
77 }
78
EnsureCapacity()79 void ValueNumbering::EnsureCapacity()
80 {
81 if (entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD >= entriesLength_) {
82 Grow();
83 }
84 }
85
Grow()86 void ValueNumbering::Grow()
87 {
88 GateRef *const oldEntries = entries_;
89 size_t const oldSize = entriesLength_;
90 entriesLength_ *= 2; // 2 : entriesLength
91 InitEntries(entriesLength_);
92 size_t const mask = entriesLength_ - 1;
93
94 for (size_t i = 0; i < oldSize; i++) {
95 GateRef oldEnrty = oldEntries[i];
96 if (oldEnrty == Circuit::NullGate() || acc_.IsNop(oldEnrty)) {
97 continue;
98 }
99 for (size_t j = HashCode(oldEnrty) & mask;; j = (j + 1) & mask) {
100 GateRef entry = entries_[j];
101 if (entry == oldEnrty) {
102 break;
103 }
104 if (entry == Circuit::NullGate()) {
105 entries_[j] = oldEnrty;
106 entriesSize_++;
107 break;
108 }
109 }
110 }
111 chunk_->Free(oldEntries);
112 if (enableLog_) {
113 LOG_COMPILER(INFO) << "Grow happend";
114 }
115 }
116
InitEntries(size_t initSize)117 void ValueNumbering::InitEntries(size_t initSize)
118 {
119 entries_ = chunk_->NewArray<int32_t>(initSize);
120 for (size_t i = 0; i < initSize; i++) {
121 entries_[i] = Circuit::NullGate();
122 }
123 entriesSize_ = 0;
124 }
125
126
HashCombine(size_t seed,size_t value)127 size_t HashCombine(size_t seed, size_t value)
128 {
129 // In the meantime, we're not considering 32-bit systems
130 assert(sizeof(void *) == 8); // 8 : make sure the void* pointer is 8 bytes in size
131 const uint64_t m = uint64_t{0xC6A4A7935BD1E995};
132 const uint32_t r = 47;
133
134 value *= m;
135 value ^= value >> r;
136 value *= m;
137
138 seed ^= value;
139 seed *= m;
140 return seed;
141 }
142
HashCode(GateRef gate)143 size_t ValueNumbering::HashCode(GateRef gate)
144 {
145 size_t valueCount = acc_.GetNumValueIn(gate);
146 size_t hash = HashCombine(static_cast<size_t>(acc_.GetOpCode(gate)), valueCount);
147 for (size_t i = 0; i < valueCount; i++) {
148 GateRef input = acc_.GetValueIn(gate, i);
149 auto id = acc_.GetId(input);
150 hash = HashCombine(hash, id);
151 }
152 return hash;
153 }
154
155 // Gates are considered replaceable only when their values are identical
CheckReplacement(GateRef lhs,GateRef rhs)156 bool ValueNumbering::CheckReplacement(GateRef lhs, GateRef rhs)
157 {
158 if (acc_.GetOpCode(lhs) != acc_.GetOpCode(rhs))
159 return false;
160
161 size_t valueCount1 = acc_.GetNumIns(lhs);
162 size_t valueCount2 = acc_.GetNumIns(rhs);
163 if (valueCount1 != valueCount2)
164 return false;
165 for (size_t i = 0; i < valueCount1; i++) {
166 if (acc_.GetIn(lhs, i) != acc_.GetIn(rhs, i)) {
167 return false;
168 }
169 }
170
171 if (acc_.GetGateType(lhs) != acc_.GetGateType(rhs)) {
172 return false;
173 }
174
175 if (acc_.GetMachineType(lhs) != acc_.GetMachineType(rhs)) {
176 return false;
177 }
178
179 if (!acc_.MetaDataValueEqu(lhs, rhs)) {
180 return false;
181 }
182
183 return true;
184 }
185 } // namespace panda::ecmascript::kungfu