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_ && entriesLength_ >= 1);
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 ASSERT(entriesLength_ > 0);
93 size_t const mask = entriesLength_ - 1;
94
95 for (size_t i = 0; i < oldSize; i++) {
96 GateRef oldEnrty = oldEntries[i];
97 if (oldEnrty == Circuit::NullGate() || acc_.IsNop(oldEnrty)) {
98 continue;
99 }
100 for (size_t j = HashCode(oldEnrty) & mask;; j = (j + 1) & mask) {
101 GateRef entry = entries_[j];
102 if (entry == oldEnrty) {
103 break;
104 }
105 if (entry == Circuit::NullGate()) {
106 entries_[j] = oldEnrty;
107 entriesSize_++;
108 break;
109 }
110 }
111 }
112 chunk_->Free(oldEntries);
113 if (enableLog_) {
114 LOG_COMPILER(INFO) << "Grow happend";
115 }
116 }
117
InitEntries(size_t initSize)118 void ValueNumbering::InitEntries(size_t initSize)
119 {
120 entries_ = chunk_->NewArray<int32_t>(initSize);
121 for (size_t i = 0; i < initSize; i++) {
122 entries_[i] = Circuit::NullGate();
123 }
124 entriesSize_ = 0;
125 }
126
127
HashCombine(size_t seed,size_t value)128 size_t HashCombine(size_t seed, size_t value)
129 {
130 // In the meantime, we're not considering 32-bit systems
131 assert(sizeof(void *) == 8); // 8 : make sure the void* pointer is 8 bytes in size
132 const uint64_t m = uint64_t{0xC6A4A7935BD1E995};
133 const uint32_t r = 47;
134
135 value *= m;
136 value ^= value >> r;
137 value *= m;
138
139 seed ^= value;
140 seed *= m;
141 return seed;
142 }
143
HashCode(GateRef gate)144 size_t ValueNumbering::HashCode(GateRef gate)
145 {
146 size_t valueCount = acc_.GetNumValueIn(gate);
147 size_t hash = HashCombine(static_cast<size_t>(acc_.GetOpCode(gate)), valueCount);
148 for (size_t i = 0; i < valueCount; i++) {
149 GateRef input = acc_.GetValueIn(gate, i);
150 auto id = acc_.GetId(input);
151 hash = HashCombine(hash, id);
152 }
153 return hash;
154 }
155
156 // Gates are considered replaceable only when their values are identical
CheckReplacement(GateRef lhs,GateRef rhs)157 bool ValueNumbering::CheckReplacement(GateRef lhs, GateRef rhs)
158 {
159 if (acc_.GetOpCode(lhs) != acc_.GetOpCode(rhs))
160 return false;
161
162 size_t valueCount1 = acc_.GetNumIns(lhs);
163 size_t valueCount2 = acc_.GetNumIns(rhs);
164 if (valueCount1 != valueCount2)
165 return false;
166 for (size_t i = 0; i < valueCount1; i++) {
167 if (acc_.GetIn(lhs, i) != acc_.GetIn(rhs, i)) {
168 return false;
169 }
170 }
171
172 if (acc_.GetGateType(lhs) != acc_.GetGateType(rhs)) {
173 return false;
174 }
175
176 if (acc_.GetMachineType(lhs) != acc_.GetMachineType(rhs)) {
177 return false;
178 }
179
180 if (!acc_.MetaDataValueEqu(lhs, rhs)) {
181 return false;
182 }
183
184 return true;
185 }
186 } // namespace panda::ecmascript::kungfu