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 "linear_order.h"
17 #include "optimizer/ir/basicblock.h"
18 #include "optimizer/ir/graph.h"
19
20 namespace panda::compiler {
LinearOrder(Graph * graph)21 LinearOrder::LinearOrder(Graph *graph)
22 : Analysis(graph),
23 linear_blocks_(graph->GetAllocator()->Adapter()),
24 rpo_blocks_(graph->GetAllocator()->Adapter()),
25 reordered_blocks_(graph->GetAllocator()->Adapter())
26 {
27 }
28
HandleIfBlock(BasicBlock * if_true_block,BasicBlock * next_block)29 void LinearOrder::HandleIfBlock(BasicBlock *if_true_block, BasicBlock *next_block)
30 {
31 ASSERT(if_true_block != nullptr && next_block != nullptr);
32 ASSERT(!if_true_block->IsEmpty());
33 if (if_true_block->GetTrueSuccessor() == next_block) {
34 auto if_inst = if_true_block->GetLastInst();
35 if_true_block->SwapTrueFalseSuccessors<true>();
36 if (if_inst->GetOpcode() == Opcode::IfImm) {
37 if_inst->CastToIfImm()->InverseConditionCode();
38 } else if (if_inst->GetOpcode() == Opcode::If) {
39 if_inst->CastToIf()->InverseConditionCode();
40 } else if (if_inst->GetOpcode() == Opcode::AddOverflow) {
41 if_inst->CastToAddOverflow()->InverseConditionCode();
42 } else if (if_inst->GetOpcode() == Opcode::SubOverflow) {
43 if_inst->CastToSubOverflow()->InverseConditionCode();
44 } else {
45 LOG(FATAL, COMPILER) << "Unexpected `If` instruction: " << *if_inst;
46 }
47 } else if (if_true_block->GetFalseSuccessor() != next_block) {
48 if_true_block->SetNeedsJump(true);
49 }
50 }
51
HandlePrevInstruction(BasicBlock * block,BasicBlock * prev_block)52 void LinearOrder::HandlePrevInstruction(BasicBlock *block, BasicBlock *prev_block)
53 {
54 ASSERT(block != nullptr && prev_block != nullptr);
55 ASSERT(!prev_block->NeedsJump());
56 if (!prev_block->IsEmpty()) {
57 auto prev_inst = prev_block->GetLastInst();
58 switch (prev_inst->GetOpcode()) {
59 case Opcode::IfImm:
60 case Opcode::If:
61 case Opcode::AddOverflow:
62 case Opcode::SubOverflow:
63 ASSERT(prev_block->GetSuccsBlocks().size() == MAX_SUCCS_NUM);
64 HandleIfBlock(prev_block, block);
65 break;
66
67 case Opcode::Throw:
68 break;
69
70 default:
71 ASSERT(prev_block->GetSuccsBlocks().size() == 1 || prev_block->IsTryBegin() || prev_block->IsTryEnd());
72 if (block != prev_block->GetSuccessor(0) && !prev_block->GetLastInst()->IsControlFlow()) {
73 prev_block->SetNeedsJump(true);
74 }
75 break;
76 }
77 } else if (!prev_block->IsEndBlock() && block != prev_block->GetSuccessor(0) &&
78 !prev_block->GetSuccessor(0)->IsEndBlock()) {
79 ASSERT(prev_block->GetSuccsBlocks().size() == 1 || prev_block->IsTryEnd());
80 prev_block->SetNeedsJump(true);
81 }
82 }
83
AddSortedByPc(ArenaList<BasicBlock * > * rpo_blocks,BasicBlock * bb)84 static void AddSortedByPc(ArenaList<BasicBlock *> *rpo_blocks, BasicBlock *bb)
85 {
86 auto cmp = [](BasicBlock *lhs, BasicBlock *rhs) { return lhs->GetGuestPc() >= rhs->GetGuestPc(); };
87
88 if (rpo_blocks->empty()) {
89 rpo_blocks->push_back(bb);
90 return;
91 }
92
93 auto iter = rpo_blocks->end();
94 --iter;
95 while (true) {
96 if (cmp(bb, *iter)) {
97 rpo_blocks->insert(++iter, bb);
98 break;
99 }
100 if (iter == rpo_blocks->begin()) {
101 rpo_blocks->push_front(bb);
102 break;
103 }
104 --iter;
105 }
106 }
107
108 template <class T>
MakeLinearOrder(const T & blocks)109 void LinearOrder::MakeLinearOrder(const T &blocks)
110 {
111 linear_blocks_.clear();
112 linear_blocks_.reserve(blocks.size());
113
114 BasicBlock *prev = nullptr;
115 for (auto block : blocks) {
116 if (prev != nullptr) {
117 HandlePrevInstruction(block, prev);
118 }
119 linear_blocks_.push_back(block);
120 prev = block;
121 }
122
123 if (prev != nullptr && !prev->IsEndBlock()) {
124 // Handle last block
125 ASSERT(prev->GetSuccsBlocks().size() == 1 || prev->IsIfBlock());
126 prev->SetNeedsJump(true);
127 }
128 }
129
LeastLikelySuccessor(const BasicBlock * block)130 BasicBlock *LinearOrder::LeastLikelySuccessor(const BasicBlock *block)
131 {
132 if (!options.IsCompilerFreqBasedBranchReorder()) {
133 return nullptr;
134 }
135
136 if (block->GetSuccsBlocks().size() != MAX_SUCCS_NUM) {
137 return nullptr;
138 }
139
140 auto counter0 = GetGraph()->GetBranchCounter(block, true);
141 auto counter1 = GetGraph()->GetBranchCounter(block, false);
142
143 if (counter0 > 0 || counter1 > 0) {
144 auto denom = std::max(counter0, counter1);
145 // NOLINTNEXTLINE(readability-magic-numbers)
146 auto r = (counter0 - counter1) * 100 / denom;
147 if (std::abs(r) < options.GetCompilerFreqBasedBranchReorderThreshold()) {
148 return nullptr;
149 }
150 return r < 0 ? block->GetTrueSuccessor() : block->GetFalseSuccessor();
151 }
152
153 return nullptr;
154 }
155
156 // Similar to DFS but move least frequent branch to the end.
157 // First time method is called with defer_least_frequent=true template param which moves least likely successors to the
158 // end. After all most likely successors are processed call method with defer_least_frequent=false and process least
159 // frequent successors with DFS.
160 template <bool defer_least_frequent>
DFSAndDeferLeastFrequentBranches(BasicBlock * block,size_t * blocks_count)161 void LinearOrder::DFSAndDeferLeastFrequentBranches(BasicBlock *block, size_t *blocks_count)
162 {
163 ASSERT(block != nullptr);
164 block->SetMarker(marker_);
165
166 auto least_likely_successor = defer_least_frequent ? LeastLikelySuccessor(block) : nullptr;
167 if (least_likely_successor == nullptr) {
168 for (auto succ_block : block->GetSuccsBlocks()) {
169 if (!succ_block->IsMarked(marker_)) {
170 DFSAndDeferLeastFrequentBranches<defer_least_frequent>(succ_block, blocks_count);
171 }
172 }
173 } else {
174 linear_blocks_.push_back(least_likely_successor);
175 auto most_likely_successor = least_likely_successor == block->GetTrueSuccessor() ? block->GetFalseSuccessor()
176 : block->GetTrueSuccessor();
177 if (!most_likely_successor->IsMarked(marker_)) {
178 DFSAndDeferLeastFrequentBranches<defer_least_frequent>(most_likely_successor, blocks_count);
179 }
180 }
181
182 if constexpr (defer_least_frequent) { // NOLINT(readability-braces-around-statements,bugprone-suspicious-semicolon)
183 for (auto succ_block : linear_blocks_) {
184 if (!succ_block->IsMarked(marker_)) {
185 DFSAndDeferLeastFrequentBranches<false>(succ_block, blocks_count);
186 }
187 }
188 linear_blocks_.clear();
189 }
190
191 ASSERT(blocks_count != nullptr && *blocks_count > 0);
192 reordered_blocks_[--(*blocks_count)] = block;
193 }
194
RunImpl()195 bool LinearOrder::RunImpl()
196 {
197 if (GetGraph()->IsBytecodeOptimizer()) {
198 // Make blocks order sorted by bytecode PC
199 rpo_blocks_.clear();
200 for (auto bb : GetGraph()->GetBlocksRPO()) {
201 ASSERT(bb->GetGuestPc() != INVALID_PC);
202 AddSortedByPc(&rpo_blocks_, bb);
203 }
204 MakeLinearOrder(rpo_blocks_);
205 } else {
206 marker_ = GetGraph()->NewMarker();
207 size_t blocks_count = GetGraph()->GetAliveBlocksCount();
208 linear_blocks_.clear();
209 reordered_blocks_.clear();
210 reordered_blocks_.resize(blocks_count);
211 DFSAndDeferLeastFrequentBranches<true>(GetGraph()->GetStartBlock(), &blocks_count);
212 #ifndef NDEBUG
213 if (blocks_count != 0) {
214 std::cerr << "There are unreachable blocks:\n";
215 for (auto bb : *GetGraph()) {
216 if (bb != nullptr && !bb->IsMarked(marker_)) {
217 bb->Dump(&std::cerr);
218 }
219 }
220 UNREACHABLE();
221 }
222 #endif // NDEBUG
223 MakeLinearOrder(reordered_blocks_);
224 GetGraph()->EraseMarker(marker_);
225 }
226 return true;
227 }
228 } // namespace panda::compiler
229