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