1 /* 2 * Copyright (c) 2025 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 "live_in_analysis.h" 17 #include "loop_analyzer.h" 18 19 namespace ark::compiler { 20 IsAlive(const BasicBlock * block,const Inst * inst) const21bool LiveInAnalysis::IsAlive(const BasicBlock *block, const Inst *inst) const 22 { 23 if (inst->GetType() == DataType::ANY) { 24 return true; 25 } 26 if (!inst->HasUsers()) { 27 return false; 28 } 29 ASSERT(DataType::IsReference(inst->GetType())); 30 inst = Inst::GetDataFlowInput(const_cast<Inst *>(inst)); 31 ASSERT_PRINT(inst->GetId() < allInsts_.size() && allInsts_[inst->GetId()] == inst, "No inst in LiveIn: " << *inst); 32 auto &liveIns = liveIn_[block->GetId()]; 33 return liveIns.GetBit(inst->GetId()); 34 } 35 ProcessBlock(BasicBlock * block)36void LiveInAnalysis::ProcessBlock(BasicBlock *block) 37 { 38 auto &liveIns = liveIn_[block->GetId()]; 39 40 for (auto succ : block->GetSuccsBlocks()) { 41 liveIns |= liveIn_[succ->GetId()]; 42 for (auto phiInst : succ->PhiInsts()) { 43 auto phiInput = phiInst->CastToPhi()->GetPhiInput(block); 44 if (DataType::IsReference(phiInput->GetType())) { 45 liveIns.SetBit(phiInput->GetId()); 46 AddInst(phiInput); 47 } 48 } 49 } 50 51 for (auto inst : block->InstsReverse()) { 52 if (DataType::IsReference(inst->GetType())) { 53 liveIns.ClearBit(inst->GetId()); 54 } 55 for (auto &input : inst->GetInputs()) { 56 auto inputInst = input.GetInst(); 57 if (!DataType::IsReference(inputInst->GetType())) { 58 continue; 59 } 60 liveIns.SetBit(inputInst->GetId()); 61 AddInst(inputInst); 62 auto dfInput = inst->GetDataFlowInput(inputInst); 63 if (dfInput != inputInst) { 64 liveIns.SetBit(dfInput->GetId()); 65 AddInst(dfInput); 66 } 67 } 68 } 69 for (auto inst : block->PhiInsts()) { 70 if (DataType::IsReference(inst->GetType())) { 71 liveIns.ClearBit(inst->GetId()); 72 } 73 } 74 75 // Loop header's live-ins are alive throughout the whole loop. 76 // If current block is a header then propagate its live-ins 77 // to all current loop's blocks as well as to all inner loops. 78 auto loop = block->GetLoop(); 79 if (loop->IsRoot() || loop->GetHeader() != block) { 80 return; 81 } 82 for (auto loopBlock : graph_->GetVectorBlocks()) { 83 if (loopBlock == nullptr || loopBlock == block) { 84 continue; 85 } 86 if (loopBlock->GetLoop() == loop || loopBlock->GetLoop()->IsInside(loop)) { 87 auto &loopBlockLiveIns = liveIn_[loopBlock->GetId()]; 88 loopBlockLiveIns |= liveIns; 89 } 90 } 91 } 92 HasAllocs(Graph * graph)93bool LiveInAnalysis::HasAllocs(Graph *graph) 94 { 95 for (auto block : graph->GetBlocksRPO()) { 96 for (auto inst : block->Insts()) { 97 if (IsAllocInst(inst)) { 98 return true; 99 } 100 } 101 } 102 return false; 103 } 104 Run(bool checkAllocs)105bool LiveInAnalysis::Run(bool checkAllocs) 106 { 107 if (checkAllocs && !HasAllocs(graph_)) { 108 return false; 109 } 110 graph_->RunPass<LoopAnalyzer>(); 111 112 // Must be fresh LiveInAnalysis because we use LocalAllocator 113 ASSERT(liveIn_.empty()); 114 ASSERT(allInsts_.empty()); 115 for (size_t idx = 0; idx < graph_->GetVectorBlocks().size(); ++idx) { 116 liveIn_.emplace_back(graph_->GetLocalAllocator()); 117 } 118 119 auto &rpo = graph_->GetBlocksRPO(); 120 for (auto it = rpo.rbegin(), end = rpo.rend(); it != end; ++it) { 121 ProcessBlock(*it); 122 } 123 return true; 124 } 125 126 } // namespace ark::compiler 127