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
17 namespace panda::ecmascript::kungfu {
18
VisitGate(GateRef gate)19 GateRef ValueNumbering::VisitGate(GateRef gate)
20 {
21 size_t hash = HashCode(gate);
22 auto opcode = acc_.GetOpCode(gate);
23 if (opcode != OpCode::CONVERT && !useNewGVN_) {
24 return Circuit::NullGate();
25 }
26 if (acc_.GetStateCount(gate) > 0 || acc_.GetDependCount(gate) > 0) {
27 return Circuit::NullGate();
28 }
29
30 if (entries_ == nullptr) {
31 InitEntries(entriesLength_);
32 SetEntry(hash, gate);
33 entriesSize_++;
34 return Circuit::NullGate();
35 }
36 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_ && entriesLength_ >= 1);
37 const size_t mask = entriesLength_ - 1;
38 size_t dead = entriesLength_;
39 for (size_t i = hash & mask;; i = (i + 1) & mask) {
40 GateRef entry = entries_[i];
41 if (entry == Circuit::NullGate()) {
42 if (dead != entriesLength_) {
43 entries_[dead] = gate;
44 } else {
45 // Have to insert a new entry.
46 entries_[i] = gate;
47 entriesSize_++;
48 // Resize to keep load factor below 80%
49 EnsureCapacity();
50 }
51 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_);
52 return Circuit::NullGate();
53 }
54
55 if (entry == gate) {
56 return Circuit::NullGate();
57 }
58
59 // Skip dead entries, but remember their indices so we can reuse them.
60 if (acc_.IsNop(entry)) {
61 dead = i;
62 continue;
63 }
64
65 if (CheckReplacement(gate, entry)) {
66 optimizedGateCount++;
67 if (enableLog_) {
68 LOG_COMPILER(INFO) << "Found a replaceable node, before -> after";
69 acc_.Print(gate);
70 acc_.Print(entry);
71 }
72 return entry;
73 }
74 }
75 return Circuit::NullGate();
76 }
77
EnsureCapacity()78 void ValueNumbering::EnsureCapacity()
79 {
80 if (entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD >= entriesLength_) {
81 Grow();
82 }
83 }
84
Grow()85 void ValueNumbering::Grow()
86 {
87 GateRef *const oldEntries = entries_;
88 size_t const oldSize = entriesLength_;
89 entriesLength_ *= 2; // 2 : entriesLength
90 InitEntries(entriesLength_);
91 ASSERT(entriesLength_ > 0);
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