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 "adjust_arefs.h"
17 #include "optimizer/ir/basicblock.h"
18 #include "optimizer/ir/graph.h"
19 #include "optimizer/analysis/loop_analyzer.h"
20
21 namespace panda::compiler {
AdjustRefs(Graph * graph)22 AdjustRefs::AdjustRefs(Graph *graph)
23 : Optimization {graph},
24 defs_ {graph->GetLocalAllocator()->Adapter()},
25 workset_ {graph->GetLocalAllocator()->Adapter()},
26 chains_ {graph->GetLocalAllocator()->Adapter()}
27 {
28 }
29
IsRefAdjustable(const Inst * inst)30 static bool IsRefAdjustable(const Inst *inst)
31 {
32 switch (inst->GetOpcode()) {
33 case Opcode::StoreArray:
34 return !inst->CastToStoreArray()->GetNeedBarrier();
35 case Opcode::LoadArray:
36 return !inst->CastToLoadArray()->GetNeedBarrier() && !inst->CastToLoadArray()->IsString();
37 default:
38 break;
39 }
40
41 return false;
42 }
43
RunImpl()44 bool AdjustRefs::RunImpl()
45 {
46 for (const auto &bb : GetGraph()->GetBlocksRPO()) {
47 if (bb->GetLoop()->IsRoot()) {
48 continue;
49 }
50
51 for (auto inst : bb->Insts()) {
52 if (IsRefAdjustable(inst)) {
53 if (defs_.find(inst->GetInput(0).GetInst()) != defs_.end()) {
54 continue;
55 }
56 defs_.insert(inst->GetInput(0).GetInst());
57 }
58 }
59 }
60
61 for (auto def : defs_) {
62 workset_.clear();
63 for (auto &user : def->GetUsers()) {
64 auto i = user.GetInst();
65 if (!IsRefAdjustable(i) || i->GetBasicBlock()->GetLoop()->IsRoot()) {
66 continue;
67 }
68 workset_.insert(i);
69 }
70 ProcessArrayUses();
71 }
72
73 return added_;
74 }
75
ProcessArrayUses()76 void AdjustRefs::ProcessArrayUses()
77 {
78 chains_.clear();
79 for (auto inst : GetHeads()) {
80 ASSERT(IsRefAdjustable(inst));
81 ASSERT(workset_.find(inst) != workset_.end());
82 loop_ = inst->GetBasicBlock()->GetLoop();
83 WalkChainDown(inst, nullptr);
84 }
85 }
86
87 /* Create the list of "heads" - the instructions that are
88 * not dominated by any other instruction in the workset */
GetHeads()89 ArenaVector<Inst *> AdjustRefs::GetHeads()
90 {
91 ArenaVector<Inst *> heads(GetGraph()->GetLocalAllocator()->Adapter());
92 for (const auto i : workset_) {
93 auto comp = [i](const Inst *i1) { return i1->IsDominate(i) && i != i1; };
94 if (workset_.end() == std::find_if(workset_.begin(), workset_.end(), comp)) {
95 heads.emplace_back(i);
96 }
97 }
98 return heads;
99 }
100
WalkChainDown(Inst * inst,Inst * head)101 void AdjustRefs::WalkChainDown(Inst *inst, Inst *head)
102 {
103 if (inst == nullptr || (inst->GetBasicBlock()->GetLoop() != loop_)) {
104 return;
105 }
106
107 auto cur = inst;
108 for (; cur != nullptr; cur = cur->GetNext()) {
109 /* potential switch to VM, the chain breaks here */
110 if (cur->RequireState() || cur->GetOpcode() == Opcode::SafePoint) {
111 head = nullptr;
112 } else if (IsRefAdjustable(cur) && workset_.find(cur) != workset_.end()) {
113 if (head == nullptr) {
114 head = cur;
115 } else {
116 ASSERT(head->IsDominate(cur));
117 }
118 chains_.emplace(head, cur);
119 break;
120 }
121 }
122 if (cur == nullptr) {
123 auto bb = inst->GetBasicBlock();
124 for (auto succ : bb->GetDominatedBlocks()) {
125 WalkChainDown(succ->GetFirstInst(), head);
126 }
127 } else {
128 WalkChainDown(cur->GetNext(), head);
129 }
130
131 if (cur == head && chains_.count(head) > 1) {
132 ProcessChain(head);
133 }
134 }
135
ProcessChain(Inst * head)136 void AdjustRefs::ProcessChain(Inst *head)
137 {
138 Inst *def = head->GetInput(0).GetInst();
139 auto *bb = head->GetBasicBlock();
140 auto arr_data = GetGraph()->CreateInst(Opcode::AddI);
141 arr_data->SetPc(def->GetPc());
142 arr_data->SetInput(0, def);
143 auto off = GetGraph()->GetRuntime()->GetArrayDataOffset(GetGraph()->GetArch());
144 arr_data->CastToAddI()->SetImm(off);
145 arr_data->SetType(DataType::POINTER);
146 bb->InsertBefore(arr_data, head);
147
148 auto range = chains_.equal_range(head);
149 for (auto it = range.first; it != range.second; ++it) {
150 Inst *ldst = nullptr;
151 Inst *org = it->second;
152 /* we don't do arrays of references anyway so the arch-dependent
153 * difference in referece size does not really matter */
154 auto scale = DataType::ShiftByType(org->GetType(), static_cast<panda::Arch>(0));
155
156 ASSERT(arr_data->IsDominate(org));
157
158 if (org->IsStore()) {
159 constexpr auto value_idx = 2;
160 ldst = bb->GetGraph()->CreateInst(Opcode::Store);
161 ldst->SetInput(value_idx, org->GetInput(value_idx).GetInst());
162 ldst->CastToStore()->SetScale(scale);
163 } else if (org->IsLoad()) {
164 ldst = bb->GetGraph()->CreateInst(Opcode::Load);
165 ldst->CastToLoad()->SetScale(scale);
166 } else {
167 UNREACHABLE();
168 }
169 ldst->SetInput(0, arr_data);
170 ldst->SetInput(1, org->GetInput(1).GetInst());
171 ldst->SetType(org->GetType());
172 org->ReplaceUsers(ldst);
173 org->RemoveInputs();
174 org->GetBasicBlock()->ReplaceInst(org, ldst);
175 ASSERT(ldst->GetBasicBlock() != nullptr);
176 }
177
178 added_ = true;
179 }
180 } // namespace panda::compiler
181