1/**
2 * Copyright (c) 2021-2022 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
16#ifndef COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H
17#define COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H
18
19#include <unordered_map>
20#include <array>
21#include "utils/hash.h"
22#include "optimizer/pass.h"
23
24namespace panda::compiler {
25class Inst;
26class VnObject;
27class Graph;
28
29class VnObject {
30public:
31    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-member-init,hicpp-member-init)
32    explicit VnObject()
33    {
34        for (uint8_t i = 0; i < MAX_ARRAY_SIZE; i++) {
35            objs_[i] = 0;
36        }
37    }
38    NO_MOVE_SEMANTIC(VnObject);
39    NO_COPY_SEMANTIC(VnObject);
40    ~VnObject() = default;
41
42    void Add(Inst *inst);
43    void Add(uint32_t obj);
44    void Add(uint64_t obj);
45    bool Compare(VnObject *obj);
46    uint32_t GetSize() const
47    {
48        return size_objs_;
49    }
50    uint64_t GetElement(uint32_t index) const
51    {
52        ASSERT(index < size_objs_);
53        return objs_[index];
54    }
55    uint32_t *GetArray()
56    {
57        return objs_.data();
58    }
59
60private:
61    uint8_t size_objs_ {0};
62    // opcode, type, 2 inputs, 2 advanced property
63    static constexpr uint8_t MAX_ARRAY_SIZE = 6;
64    std::array<uint32_t, MAX_ARRAY_SIZE> objs_;
65};
66
67struct VnObjEqual {
68    bool operator()(VnObject *obj1, VnObject *obj2) const
69    {
70        return obj1->Compare(obj2);
71    }
72};
73
74struct VnObjHash {
75    uint32_t operator()(VnObject *obj) const
76    {
77        return GetHash32(reinterpret_cast<const uint8_t *>(obj->GetArray()), obj->GetSize());
78    }
79};
80
81/*
82 * Optimization assigns numbers(named vn) to all instructions.
83 * Equivalent instructions have equivalent vn.
84 * If instruction A dominates B and they have equivalent vn, users B are moved to A and DCE removes B at the end.
85 * The instruction with the property NO_CSE has unique vn and they can't be removed.
86 * The optimization creates VnObject for instruction without NO_CSE.
87 * The VnObject is key for the instruction.
88 * The unordered_map is used for searching equivalent instruction by the key(VnObject).
89 */
90class ValNum : public Optimization {
91public:
92    explicit ValNum(Graph *graph);
93    NO_MOVE_SEMANTIC(ValNum);
94    NO_COPY_SEMANTIC(ValNum);
95    ~ValNum() override = default;
96
97    bool RunImpl() override;
98
99    const char *GetPassName() const override
100    {
101        return "GVN";
102    }
103
104    bool IsEnable() const override
105    {
106        return options.IsCompilerVn();
107    }
108
109    void InvalidateAnalyses() override;
110
111    void FindEqualVnOrCreateNew(Inst *inst);
112
113private:
114    using InstVector = ArenaVector<Inst *>;
115
116    // Sets vn for the inst
117    void SetInstValNum(Inst *inst);
118
119    bool TryToApplyCse(Inst *inst, InstVector *equiv_insts);
120
121    // !TODO add own allocator
122    ArenaUnorderedMap<VnObject *, InstVector, VnObjHash, VnObjEqual> map_insts_;
123
124    uint32_t curr_vn_ {0};
125    bool cse_is_appied_ {false};
126};
127}  // namespace panda::compiler
128
129#endif  // COMPILER_OPTIMIZER_OPTIMIZATIONS_VN_H
130