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#include "optimizer/ir/basicblock.h"
17#include "optimizer/ir/graph.h"
18#include "compiler_logger.h"
19#include "vn.h"
20
21namespace panda::compiler {
22class BasicBlock;
23
24static void AddSpecialTraits(Inst *inst, VnObject *obj)
25{
26    switch (inst->GetOpcode()) {
27        case Opcode::Intrinsic:
28            if (inst->GetFlagsMask() == 0) {
29                /* Add only those intrinsics that have no flags set */
30                obj->Add(static_cast<uint32_t>(inst->CastToIntrinsic()->GetIntrinsicId()));
31            }
32            break;
33        case Opcode::CompareAnyType:
34            obj->Add(static_cast<uint32_t>(inst->CastToCompareAnyType()->GetAnyType()));
35            break;
36        case Opcode::CastAnyTypeValue:
37            obj->Add(static_cast<uint32_t>(inst->CastToCastAnyTypeValue()->GetAnyType()));
38            break;
39        default:
40            break;
41    }
42}
43
44void VnObject::Add(Inst *inst)
45{
46    Add(static_cast<uint32_t>(inst->GetOpcode()));
47    Add(static_cast<uint32_t>(inst->GetType()));
48
49    AddSpecialTraits(inst, this);
50
51    for (auto input : inst->GetInputs()) {
52        auto input_inst = inst->GetDataFlowInput(input.GetInst());
53        auto vn = input_inst->GetVN();
54        ASSERT(vn != INVALID_VN);
55        Add(vn);
56    }
57
58    inst->SetVnObject(this);
59}
60
61void VnObject::Add(uint32_t obj)
62{
63    ASSERT(size_objs_ < MAX_ARRAY_SIZE);
64    objs_[size_objs_++] = obj;
65}
66
67void VnObject::Add(uint64_t obj)
68{
69    ASSERT(size_objs_ < MAX_ARRAY_SIZE);
70    static constexpr uint64_t MASK32 = std::numeric_limits<uint32_t>::max();
71    static constexpr uint64_t SHIFT32 = 32;
72    objs_[size_objs_++] = static_cast<uint32_t>(obj & MASK32);
73    objs_[size_objs_++] = static_cast<uint32_t>(obj >> SHIFT32);
74}
75
76bool VnObject::Compare(VnObject *obj)
77{
78    uint32_t size = GetSize();
79    if (size != obj->GetSize()) {
80        return false;
81    }
82    for (uint32_t i = 0; i < size; ++i) {
83        if (GetElement(i) != obj->GetElement(i)) {
84            return false;
85        }
86    }
87    return true;
88}
89
90ValNum::ValNum(Graph *graph) : Optimization(graph), map_insts_(GetGraph()->GetLocalAllocator()->Adapter()) {}
91
92inline void ValNum::SetInstValNum(Inst *inst)
93{
94    COMPILER_LOG(DEBUG, VN_OPT) << " Set VN " << curr_vn_ << " for inst " << inst->GetId();
95    inst->SetVN(curr_vn_++);
96}
97
98void ValNum::InvalidateAnalyses()
99{
100}
101
102bool ValNum::TryToApplyCse(Inst *inst, InstVector *equiv_insts)
103{
104    ASSERT(!equiv_insts->empty());
105    inst->SetVN((*equiv_insts)[0]->GetVN());
106    COMPILER_LOG(DEBUG, VN_OPT) << " Set VN " << inst->GetVN() << " for inst " << inst->GetId();
107    auto block = inst->GetBasicBlock();
108    for (auto equiv_inst : *equiv_insts) {
109        COMPILER_LOG(DEBUG, VN_OPT) << " Equivalent instructions are found, id " << equiv_inst->GetId();
110        if (block == equiv_inst->GetBasicBlock() || equiv_inst->IsDominate(inst)) {
111            COMPILER_LOG(DEBUG, VN_OPT) << " CSE is applied for inst with id " << inst->GetId();
112            GetGraph()->GetEventWriter().EventGvn(inst->GetId(), inst->GetPc(), equiv_inst->GetId(),
113                                                  equiv_inst->GetPc());
114            inst->ReplaceUsers(equiv_inst);
115            inst->ClearFlag(compiler::inst_flags::NO_DCE);
116            cse_is_appied_ = true;
117            return true;
118        }
119    }
120
121    return false;
122}
123
124void ValNum::FindEqualVnOrCreateNew(Inst *inst)
125{
126    // create new vn for instruction with the property NO_CSE
127    if (inst->IsNotCseApplicable()) {
128        COMPILER_LOG(DEBUG, VN_OPT) << " The inst with id " << inst->GetId() << " has the property NO_CSE";
129        SetInstValNum(inst);
130        return;
131    }
132    auto obj = GetGraph()->GetLocalAllocator()->New<VnObject>();
133    CHECK_NOT_NULL(obj);
134    obj->Add(inst);
135    COMPILER_LOG(DEBUG, VN_OPT) << " Equivalent instructions are searched for inst with id " << inst->GetId();
136    auto it = map_insts_.find(obj);
137    if (it == map_insts_.cend()) {
138        COMPILER_LOG(DEBUG, VN_OPT) << " Equivalent instructions aren't found";
139        SetInstValNum(inst);
140        InstVector equiv_insts(GetGraph()->GetLocalAllocator()->Adapter());
141        equiv_insts.push_back(inst);
142        map_insts_.insert({obj, std::move(equiv_insts)});
143        return;
144    }
145
146    auto &equiv_insts = it->second;
147    if (!TryToApplyCse(inst, &equiv_insts)) {
148        equiv_insts.push_back(inst);
149    }
150}
151
152bool ValNum::RunImpl()
153{
154    GetGraph()->RunPass<DominatorsTree>();
155    for (auto bb : GetGraph()->GetBlocksRPO()) {
156        for (auto inst : bb->AllInsts()) {
157            inst->SetVN(INVALID_VN);
158        }
159    }
160    for (auto bb : GetGraph()->GetBlocksRPO()) {
161        for (auto inst : bb->AllInsts()) {
162            FindEqualVnOrCreateNew(inst);
163        }
164    }
165    return cse_is_appied_;
166}
167}  // namespace panda::compiler
168