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
18namespace panda::ecmascript::kungfu {
19
20GateRef 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
79void ValueNumbering::EnsureCapacity()
80{
81    if (entriesSize_ + entriesSize_ / LOAD_FACTOR_THRESHOLD >= entriesLength_) {
82        Grow();
83    }
84}
85
86void 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
118void 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
128size_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
144size_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
157bool 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