1 /*
2 * Copyright (c) 2023-2024 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 "condition_chain_manager.h"
17 #include "condition_chain.h"
18
19 namespace ark::compiler {
ConditionChainManager(ArenaAllocator * allocator)20 ConditionChainManager::ConditionChainManager(ArenaAllocator *allocator)
21 : allocator_(allocator), conditionChainBb_(allocator->Adapter())
22 {
23 }
24
FindConditionChain(BasicBlock * bb)25 ConditionChain *ConditionChainManager::FindConditionChain(BasicBlock *bb)
26 {
27 if (bb->GetSuccsBlocks().size() != MAX_SUCCS_NUM) {
28 return nullptr;
29 }
30
31 auto conditionChain = TryConditionChain(bb, bb->GetTrueSuccessor(), bb->GetFalseSuccessor());
32 if (conditionChain != nullptr) {
33 return conditionChain;
34 }
35
36 return TryConditionChain(bb, bb->GetFalseSuccessor(), bb->GetTrueSuccessor());
37 }
38
TryConditionChain(BasicBlock * bb,BasicBlock * multiplePredsSucc,BasicBlock * chainBb)39 ConditionChain *ConditionChainManager::TryConditionChain(BasicBlock *bb, BasicBlock *multiplePredsSucc,
40 BasicBlock *chainBb)
41 {
42 auto loop = bb->GetLoop();
43 if (multiplePredsSucc->GetLoop() != loop) {
44 return nullptr;
45 }
46 if (chainBb->GetLoop() != loop) {
47 return nullptr;
48 }
49 auto chainPos = conditionChainBb_.size();
50 conditionChainBb_.push_back(bb);
51
52 size_t singlePredSuccIndex = 0;
53 while (true) {
54 if (IsConditionChainCandidate(chainBb)) {
55 if (chainBb->GetTrueSuccessor() == multiplePredsSucc) {
56 conditionChainBb_.push_back(chainBb);
57 chainBb = chainBb->GetFalseSuccessor();
58 singlePredSuccIndex = BasicBlock::FALSE_SUCC_IDX;
59 continue;
60 }
61 if (chainBb->GetFalseSuccessor() == multiplePredsSucc) {
62 conditionChainBb_.push_back(chainBb);
63 chainBb = chainBb->GetTrueSuccessor();
64 singlePredSuccIndex = BasicBlock::TRUE_SUCC_IDX;
65 continue;
66 }
67 }
68 auto chainSize = conditionChainBb_.size() - chainPos;
69 if (chainSize > 1) {
70 // store successors indices instead of pointers to basic blocks because they can be changed during loop
71 // transformation
72 return allocator_->New<ConditionChain>(conditionChainBb_.begin() + chainPos, chainSize,
73 bb->GetSuccBlockIndex(multiplePredsSucc), singlePredSuccIndex);
74 }
75 conditionChainBb_.pop_back();
76 break;
77 }
78 return nullptr;
79 }
80
IsConditionChainCandidate(const BasicBlock * bb)81 bool ConditionChainManager::IsConditionChainCandidate(const BasicBlock *bb)
82 {
83 auto loop = bb->GetLoop();
84 return bb->GetSuccsBlocks().size() == MAX_SUCCS_NUM && bb->GetLastInst()->GetPrev() == nullptr &&
85 bb->GetTrueSuccessor()->GetLoop() == loop && bb->GetFalseSuccessor()->GetLoop() == loop;
86 }
87
Reset()88 void ConditionChainManager::Reset()
89 {
90 conditionChainBb_.clear();
91 }
92 } // namespace ark::compiler
93