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