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 "move_constants.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 {
22
MoveConstants(Graph * graph)23 MoveConstants::MoveConstants(Graph *graph)
24 : Optimization {graph},
25 user_dominators_cache_ {graph->GetLocalAllocator()->Adapter()},
26 user_dominating_blocks_ {graph->GetLocalAllocator()->Adapter()},
27 moved_constants_counter_ {0}
28 {
29 }
30
31 static Inst *SingleBlockNoPhiDominatingUser(Inst *inst);
32
RunImpl()33 bool MoveConstants::RunImpl()
34 {
35 for (auto const_inst = GetGraph()->GetFirstConstInst(); const_inst != nullptr;) {
36 // save next const because it can be lost while move
37 auto next_const = const_inst->GetNextConst();
38 if (const_inst->HasUsers()) {
39 MoveFromStartBlock(const_inst);
40 }
41 const_inst = next_const;
42 }
43
44 if (GetGraph()->HasNullPtrInst()) {
45 auto null_ptr = GetGraph()->GetNullPtrInst();
46 if (null_ptr->HasUsers()) {
47 MoveFromStartBlock(null_ptr);
48 }
49 }
50
51 return moved_constants_counter_ > 0;
52 }
53
IsBlockSuitable(const BasicBlock * bb)54 bool IsBlockSuitable(const BasicBlock *bb)
55 {
56 return (!bb->IsLoopValid() || bb->GetLoop()->IsRoot()) && !bb->IsTryBegin();
57 }
58
MoveFromStartBlock(Inst * inst)59 void MoveConstants::MoveFromStartBlock(Inst *inst)
60 {
61 auto graph = GetGraph();
62
63 BasicBlock *target_bb = nullptr;
64 auto user_inst = SingleBlockNoPhiDominatingUser(inst);
65 if (user_inst != nullptr) {
66 target_bb = user_inst->GetBasicBlock();
67
68 if (IsBlockSuitable(target_bb)) {
69 graph->GetStartBlock()->EraseInst(inst);
70 target_bb->InsertBefore(inst, user_inst);
71 moved_constants_counter_++;
72 return;
73 }
74 } else {
75 GetUsersDominatingBlocks(inst);
76 target_bb = FindCommonDominator();
77 ASSERT(target_bb);
78 }
79
80 while (!IsBlockSuitable(target_bb)) {
81 target_bb = target_bb->GetDominator();
82 }
83
84 if (target_bb != graph->GetStartBlock()) {
85 graph->GetStartBlock()->EraseInst(inst);
86 target_bb->PrependInst(inst);
87 moved_constants_counter_++;
88 }
89 }
90
SingleBlockNoPhiDominatingUser(Inst * inst)91 static Inst *SingleBlockNoPhiDominatingUser(Inst *inst)
92 {
93 Inst *first_inst {};
94 for (auto &user : inst->GetUsers()) {
95 auto user_inst = user.GetInst();
96 if (user_inst->IsPhi() || user_inst->IsCatchPhi()) {
97 return nullptr;
98 }
99 if (first_inst == nullptr) {
100 first_inst = user_inst;
101 continue;
102 }
103 if (first_inst->GetBasicBlock() != user_inst->GetBasicBlock()) {
104 return nullptr;
105 }
106 if (user_inst->IsDominate(first_inst)) {
107 first_inst = user_inst;
108 }
109 }
110 return first_inst;
111 }
112
GetUsersDominatingBlocks(const Inst * inst)113 void MoveConstants::GetUsersDominatingBlocks(const Inst *inst)
114 {
115 ASSERT(inst->HasUsers());
116
117 user_dominating_blocks_.clear();
118
119 for (auto &user : inst->GetUsers()) {
120 user_dominating_blocks_.emplace_back(GetDominators(user));
121 }
122 }
123
GetDominators(const User & user)124 const ArenaVector<BasicBlock *> *MoveConstants::GetDominators(const User &user)
125 {
126 auto inst = user.GetInst();
127 if (inst->IsCatchPhi()) {
128 // do not move catch-phi's input over throwable instruction
129 inst = inst->CastToCatchPhi()->GetThrowableInst(user.GetIndex());
130 }
131 auto id = inst->GetId();
132 auto cached_dominators = user_dominators_cache_.find(id);
133 if (cached_dominators != user_dominators_cache_.end()) {
134 return &cached_dominators->second;
135 }
136
137 ArenaVector<BasicBlock *> dominators(GetGraph()->GetLocalAllocator()->Adapter());
138
139 // method does not mutate user but returns non const basic blocks
140 auto first_dominator = const_cast<BasicBlock *>(inst->GetBasicBlock());
141 if (inst->IsPhi()) {
142 // block where phi-input is located should dominate predecessor block corresponding to this input
143 first_dominator = first_dominator->GetDominator();
144 }
145 for (auto blk = first_dominator; blk != nullptr; blk = blk->GetDominator()) {
146 dominators.push_back(blk);
147 }
148
149 auto result = user_dominators_cache_.emplace(id, dominators);
150 return &result.first->second;
151 }
152
FindCommonDominator()153 BasicBlock *MoveConstants::FindCommonDominator()
154 {
155 ASSERT(!user_dominating_blocks_.empty());
156
157 BasicBlock *common_dominator {};
158
159 for (size_t i = 0;; ++i) {
160 BasicBlock *common_dominator_candidate {};
161
162 for (auto blocks : user_dominating_blocks_) {
163 if (i >= blocks->size()) {
164 return common_dominator;
165 }
166
167 auto blk = (*blocks)[blocks->size() - i - 1];
168 if (common_dominator_candidate == nullptr) {
169 common_dominator_candidate = blk;
170 continue;
171 }
172 if (common_dominator_candidate != blk) {
173 return common_dominator;
174 }
175 }
176
177 common_dominator = common_dominator_candidate;
178 }
179
180 return common_dominator;
181 }
182
183 } // namespace panda::compiler
184