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
Add(uint64_t obj)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 obj->Add(inst);
134 COMPILER_LOG(DEBUG, VN_OPT) << " Equivalent instructions are searched for inst with id " << inst->GetId();
135 auto it = map_insts_.find(obj);
136 if (it == map_insts_.cend()) {
137 COMPILER_LOG(DEBUG, VN_OPT) << " Equivalent instructions aren't found";
138 SetInstValNum(inst);
139 InstVector equiv_insts(GetGraph()->GetLocalAllocator()->Adapter());
140 equiv_insts.push_back(inst);
141 map_insts_.insert({obj, std::move(equiv_insts)});
142 return;
143 }
144
145 auto &equiv_insts = it->second;
146 if (!TryToApplyCse(inst, &equiv_insts)) {
147 equiv_insts.push_back(inst);
148 }
149 }
150
RunImpl()151 bool ValNum::RunImpl()
152 {
153 GetGraph()->RunPass<DominatorsTree>();
154 for (auto bb : GetGraph()->GetBlocksRPO()) {
155 for (auto inst : bb->AllInsts()) {
156 inst->SetVN(INVALID_VN);
157 }
158 }
159 for (auto bb : GetGraph()->GetBlocksRPO()) {
160 for (auto inst : bb->AllInsts()) {
161 FindEqualVnOrCreateNew(inst);
162 }
163 }
164 return cse_is_appied_;
165 }
166 } // namespace panda::compiler
167