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