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