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