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
21 namespace panda::compiler {
22 class BasicBlock;
23
AddSpecialTraits(Inst *inst, VnObject *obj)24 static 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
Add(Inst *inst)44 void 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
Add(uint32_t obj)61 void VnObject::Add(uint32_t obj)
62 {
63 ASSERT(size_objs_ < MAX_ARRAY_SIZE);
64 objs_[size_objs_++] = obj;
65 }
66
67 void 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
Compare(VnObject *obj)76 bool 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
ValNum(Graph *graph)90 ValNum::ValNum(Graph *graph) : Optimization(graph), map_insts_(GetGraph()->GetLocalAllocator()->Adapter()) {}
91
SetInstValNum(Inst *inst)92 inline 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
InvalidateAnalyses()98 void ValNum::InvalidateAnalyses()
99 {
100 }
101
TryToApplyCse(Inst *inst, InstVector *equiv_insts)102 bool 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
FindEqualVnOrCreateNew(Inst *inst)124 void 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
RunImpl()152 bool 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