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 "ecmascript/base/hash_combine.h"
17
18 namespace panda::ecmascript::kungfu {
19
VisitGate(GateRef gate)20 GateRef ValueNumbering::VisitGate(GateRef gate)
21 {
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 uint64_t hash = HashCode(gate);
31
32 if (entries_ == nullptr) {
33 InitEntries(entriesLength_);
34 SetEntry(hash, gate);
35 entriesSize_++;
36 return Circuit::NullGate();
37 }
38 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_ && entriesLength_ >= 1);
39 const size_t mask = entriesLength_ - 1;
40 size_t dead = entriesLength_;
41 for (size_t i = hash & mask;; i = (i + 1) & mask) {
42 GateRef entry = entries_[i];
43 if (entry == Circuit::NullGate()) {
44 if (dead != entriesLength_) {
45 entries_[dead] = gate;
46 } else {
47 // Have to insert a new entry.
48 entries_[i] = gate;
49 entriesSize_++;
50 // Resize to keep load factor below 80%
51 EnsureCapacity();
52 }
53 ASSERT(entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD < entriesLength_);
54 return Circuit::NullGate();
55 }
56
57 if (entry == gate) {
58 return Circuit::NullGate();
59 }
60
61 // Skip dead entries, but remember their indices so we can reuse them.
62 if (acc_.IsNop(entry)) {
63 dead = i;
64 continue;
65 }
66
67 if (CheckReplacement(gate, entry)) {
68 optimizedGateCount++;
69 if (enableLog_) {
70 LOG_COMPILER(INFO) << "Found a replaceable node, before -> after";
71 acc_.Print(gate);
72 acc_.Print(entry);
73 }
74 return entry;
75 }
76 }
77 return Circuit::NullGate();
78 }
79
EnsureCapacity()80 void ValueNumbering::EnsureCapacity()
81 {
82 if (entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD >= entriesLength_) {
83 Grow();
84 }
85 }
86
Grow()87 void ValueNumbering::Grow()
88 {
89 GateRef *const oldEntries = entries_;
90 size_t const oldSize = entriesLength_;
91 entriesLength_ *= 2; // 2 : entriesLength
92 InitEntries(entriesLength_);
93 ASSERT(entriesLength_ > 0);
94 size_t const mask = entriesLength_ - 1;
95
96 for (size_t i = 0; i < oldSize; i++) {
97 GateRef oldEnrty = oldEntries[i];
98 if (oldEnrty == Circuit::NullGate() || acc_.IsNop(oldEnrty)) {
99 continue;
100 }
101 for (size_t j = HashCode(oldEnrty) & mask;; j = (j + 1) & mask) {
102 GateRef entry = entries_[j];
103 if (entry == oldEnrty) {
104 break;
105 }
106 if (entry == Circuit::NullGate()) {
107 entries_[j] = oldEnrty;
108 entriesSize_++;
109 break;
110 }
111 }
112 }
113 chunk_->Free(oldEntries);
114 if (enableLog_) {
115 LOG_COMPILER(INFO) << "Grow happend";
116 }
117 }
118
InitEntries(size_t initSize)119 void ValueNumbering::InitEntries(size_t initSize)
120 {
121 entries_ = chunk_->NewArray<int32_t>(initSize);
122 for (size_t i = 0; i < initSize; i++) {
123 entries_[i] = Circuit::NullGate();
124 }
125 entriesSize_ = 0;
126 }
127
HashCode(GateRef gate)128 size_t ValueNumbering::HashCode(GateRef gate)
129 {
130 size_t valueCount = acc_.GetNumValueIn(gate);
131 uint64_t hash = acc_.GetMetaDataHash(gate);
132 hash = base::HashCombiner::HashCombine(hash, static_cast<uint64_t>(acc_.GetGateType(gate).Value()));
133 hash = base::HashCombiner::HashCombine(hash, static_cast<uint64_t>(acc_.GetMachineType(gate)));
134 for (size_t i = 0; i < valueCount; i++) {
135 GateRef input = acc_.GetValueIn(gate, i);
136 auto id = acc_.GetId(input);
137 hash = base::HashCombiner::HashCombine(hash, id);
138 }
139 return hash;
140 }
141
142 // Gates are considered replaceable only when their values are identical
CheckReplacement(GateRef lhs,GateRef rhs)143 bool ValueNumbering::CheckReplacement(GateRef lhs, GateRef rhs)
144 {
145 if (acc_.GetOpCode(lhs) != acc_.GetOpCode(rhs))
146 return false;
147
148 size_t valueCount1 = acc_.GetNumIns(lhs);
149 size_t valueCount2 = acc_.GetNumIns(rhs);
150 if (valueCount1 != valueCount2)
151 return false;
152 for (size_t i = 0; i < valueCount1; i++) {
153 if (acc_.GetIn(lhs, i) != acc_.GetIn(rhs, i)) {
154 return false;
155 }
156 }
157
158 if (acc_.GetGateType(lhs) != acc_.GetGateType(rhs)) {
159 return false;
160 }
161
162 if (acc_.GetMachineType(lhs) != acc_.GetMachineType(rhs)) {
163 return false;
164 }
165
166 if (!acc_.MetaDataValueEqu(lhs, rhs)) {
167 return false;
168 }
169
170 return true;
171 }
172 } // namespace panda::ecmascript::kungfu
173