1 /* 2 * Copyright (C) 2023 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "berberis/backend/x86_64/context_liveness_analyzer.h" 18 19 #include "berberis/backend/x86_64/machine_ir.h" 20 #include "berberis/base/algorithm.h" 21 #include "berberis/base/arena_alloc.h" 22 23 namespace berberis::x86_64 { 24 Init()25void ContextLivenessAnalyzer::Init() { 26 // TODO(b/179708579): For better post order approximation need to implement an 27 // analog of BackwardDataFlowWorkList from High-level IR. 28 MachineBasicBlockList worklist(machine_ir_->bb_list().rbegin(), 29 machine_ir_->bb_list().rend(), 30 ArenaAllocator<MachineBasicBlock*>(machine_ir_->arena())); 31 while (!worklist.empty()) { 32 auto* bb = worklist.back(); 33 worklist.pop_back(); 34 if (VisitBasicBlock(bb)) { 35 // Since there is a change we need to process preds again. 36 for (auto edge : bb->in_edges()) { 37 auto* pred_bb = edge->src(); 38 if (!Contains(worklist, pred_bb)) { 39 worklist.push_back(pred_bb); 40 } 41 } 42 } 43 } 44 } 45 IsLiveIn(const MachineBasicBlock * bb,uint32_t offset) const46bool ContextLivenessAnalyzer::IsLiveIn(const MachineBasicBlock* bb, uint32_t offset) const { 47 return context_live_in_[bb->id()].test(offset); 48 } 49 VisitBasicBlock(const MachineBasicBlock * bb)50bool ContextLivenessAnalyzer::VisitBasicBlock(const MachineBasicBlock* bb) { 51 ContextLiveness running_liveness; 52 if (bb->out_edges().size() == 0) { 53 running_liveness.set(); 54 } else { 55 for (auto* out_edge : bb->out_edges()) { 56 running_liveness |= context_live_in_[out_edge->dst()->id()]; 57 } 58 } 59 60 for (auto insn_it = bb->insn_list().rbegin(); insn_it != bb->insn_list().rend(); insn_it++) { 61 auto* insn = AsMachineInsnX86_64(*insn_it); 62 if (insn->IsCPUStatePut()) { 63 running_liveness.reset(insn->disp()); 64 } else if (insn->IsCPUStateGet()) { 65 running_liveness.set(insn->disp()); 66 } 67 } 68 69 if (context_live_in_[bb->id()] != running_liveness) { 70 context_live_in_[bb->id()] = running_liveness; 71 return true; 72 } 73 74 return false; 75 } 76 77 } // namespace berberis::x86_64 78