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 #ifndef BERBERIS_BACKEND_X86_64_LIVENESS_ANALYZER_H_
18 #define BERBERIS_BACKEND_X86_64_LIVENESS_ANALYZER_H_
19 
20 #include "berberis/backend/x86_64/machine_ir.h"
21 #include "berberis/backend/x86_64/vreg_bit_set.h"
22 #include "berberis/base/arena_vector.h"
23 #include "berberis/base/logging.h"
24 
25 namespace berberis::x86_64 {
26 
27 class LivenessAnalyzer {
28  public:
LivenessAnalyzer(const MachineIR * machine_ir)29   explicit LivenessAnalyzer(const MachineIR* machine_ir)
30       : machine_ir_(machine_ir),
31         live_in_(machine_ir->NumBasicBlocks(),
32                  VRegBitSet(machine_ir->NumVReg(), machine_ir->arena()),
33                  machine_ir->arena()) {}
34 
35   void Run();
36 
IsLiveIn(const MachineBasicBlock * bb,MachineReg reg)37   bool IsLiveIn(const MachineBasicBlock* bb, MachineReg reg) const {
38     return live_in_[bb->id()][reg];
39   }
40 
41   // We provide live-in iterators instead of exposing individual bit-sets
42   // because with an efficient VRegBitSet implementation these methods can be made
43   // faster.
GetFirstLiveIn(const MachineBasicBlock * bb)44   MachineReg GetFirstLiveIn(const MachineBasicBlock* bb) const {
45     return GetNextLiveIn(bb, kInvalidMachineReg);
46   }
47 
GetNextLiveIn(const MachineBasicBlock * bb,MachineReg prev)48   MachineReg GetNextLiveIn(const MachineBasicBlock* bb, MachineReg prev) const {
49     CHECK(prev == kInvalidMachineReg || prev.IsVReg());
50     CHECK(prev == kInvalidMachineReg || prev.GetVRegIndex() < static_cast<uint32_t>(NumVReg()));
51 
52     for (uint32_t vreg_index = (prev == kInvalidMachineReg ? 0 : prev.GetVRegIndex() + 1);
53          vreg_index < static_cast<uint32_t>(NumVReg());
54          vreg_index++) {
55       MachineReg vreg = MachineReg::CreateVRegFromIndex(vreg_index);
56       if (IsLiveIn(bb, vreg)) {
57         return vreg;
58       }
59     }
60     return kInvalidMachineReg;
61   }
62 
63  private:
NumVReg()64   [[nodiscard]] int NumVReg() const {
65     CHECK_GT(live_in_.size(), 0);
66     return live_in_[0].Size();
67   }
68 
69   bool VisitBasicBlock(const MachineBasicBlock* bb);
70 
71   const MachineIR* machine_ir_;
72   // Contains a bit-set of live registers for each basic block.
73   ArenaVector<VRegBitSet> live_in_;
74 };
75 
76 }  // namespace berberis::x86_64
77 
78 #endif  // BERBERIS_BACKEND_X86_64_LIVENESS_ANALYZER_H_
79