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 "gtest/gtest.h"
18 
19 #include "berberis/backend/code_emitter.h"
20 #include "berberis/backend/x86_64/liveness_analyzer.h"
21 #include "berberis/backend/x86_64/machine_ir.h"
22 #include "berberis/backend/x86_64/machine_ir_builder.h"
23 #include "berberis/backend/x86_64/machine_ir_test_corpus.h"
24 #include "berberis/base/arena_alloc.h"
25 #include "berberis/guest_state/guest_addr.h"
26 
27 namespace berberis {
28 
29 namespace {
30 
31 template <typename... VRegs>
ExpectNoLiveIns(const x86_64::LivenessAnalyzer * liveness,const MachineBasicBlock * bb,VRegs...not_live_in_vregs)32 void ExpectNoLiveIns(const x86_64::LivenessAnalyzer* liveness,
33                      const MachineBasicBlock* bb,
34                      VRegs... not_live_in_vregs) {
35   EXPECT_TRUE((!liveness->IsLiveIn(bb, not_live_in_vregs) && ... && true));
36   EXPECT_EQ(liveness->GetFirstLiveIn(bb), kInvalidMachineReg);
37 }
38 
39 template <typename... VRegs>
ExpectSingleLiveIn(const x86_64::LivenessAnalyzer * liveness,const MachineBasicBlock * bb,MachineReg vreg,VRegs...not_live_in_vregs)40 void ExpectSingleLiveIn(const x86_64::LivenessAnalyzer* liveness,
41                         const MachineBasicBlock* bb,
42                         MachineReg vreg,
43                         VRegs... not_live_in_vregs) {
44   EXPECT_TRUE((!liveness->IsLiveIn(bb, not_live_in_vregs) && ... && true));
45   EXPECT_TRUE(liveness->IsLiveIn(bb, vreg));
46   EXPECT_EQ(liveness->GetFirstLiveIn(bb), vreg);
47   EXPECT_EQ(liveness->GetNextLiveIn(bb, vreg), kInvalidMachineReg);
48 }
49 
ExpectTwoLiveIns(const x86_64::LivenessAnalyzer * liveness,const MachineBasicBlock * bb,MachineReg vreg1,MachineReg vreg2)50 void ExpectTwoLiveIns(const x86_64::LivenessAnalyzer* liveness,
51                       const MachineBasicBlock* bb,
52                       MachineReg vreg1,
53                       MachineReg vreg2) {
54   EXPECT_TRUE(liveness->IsLiveIn(bb, vreg1));
55   EXPECT_TRUE(liveness->IsLiveIn(bb, vreg2));
56 
57   MachineReg live_in1 = liveness->GetFirstLiveIn(bb);
58   ASSERT_TRUE(live_in1 == vreg1 || live_in1 == vreg2);
59   MachineReg live_in2 = liveness->GetNextLiveIn(bb, live_in1);
60   ASSERT_TRUE(live_in2 == vreg1 || live_in2 == vreg2);
61   EXPECT_NE(live_in1, live_in2);
62   EXPECT_EQ(liveness->GetNextLiveIn(bb, live_in2), kInvalidMachineReg);
63 }
64 
TEST(MachineLivenessAnalyzerTest,UseProducesLiveIn)65 TEST(MachineLivenessAnalyzerTest, UseProducesLiveIn) {
66   Arena arena;
67   x86_64::MachineIR machine_ir(&arena);
68 
69   x86_64::MachineIRBuilder builder(&machine_ir);
70   MachineReg vreg = machine_ir.AllocVReg();
71 
72   auto* bb = machine_ir.NewBasicBlock();
73 
74   builder.StartBasicBlock(bb);
75   builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
76   builder.Gen<PseudoJump>(kNullGuestAddr);
77 
78   x86_64::LivenessAnalyzer liveness(&machine_ir);
79   liveness.Run();
80 
81   ExpectSingleLiveIn(&liveness, bb, vreg);
82 }
83 
84 class FakeInsnWithDefEarlyClobber : public MachineInsn {
85  public:
FakeInsnWithDefEarlyClobber(MachineReg reg)86   explicit FakeInsnWithDefEarlyClobber(MachineReg reg)
87       : MachineInsn(kMachineOpUndefined, 1, &reg_kind_, &reg_, kMachineInsnDefault), reg_{reg} {}
GetDebugString() const88   [[nodiscard]] std::string GetDebugString() const override {
89     return "FakeInsnWithDefEarlyClobber";
90   }
Emit(CodeEmitter *) const91   void Emit(CodeEmitter* /*as*/) const override {}
92 
93  private:
94   static MachineRegKind reg_kind_;
95   MachineReg reg_;
96 };
97 
98 MachineRegKind FakeInsnWithDefEarlyClobber::reg_kind_ = {&x86_64::kGeneralReg64,
99                                                          MachineRegKind::kDefEarlyClobber};
100 
TEST(MachineLivenessAnalyzerTest,DefEarlyClobberDoesNotProduceLiveIn)101 TEST(MachineLivenessAnalyzerTest, DefEarlyClobberDoesNotProduceLiveIn) {
102   Arena arena;
103   x86_64::MachineIR machine_ir(&arena);
104 
105   x86_64::MachineIRBuilder builder(&machine_ir);
106   MachineReg vreg = machine_ir.AllocVReg();
107 
108   auto* bb = machine_ir.NewBasicBlock();
109 
110   builder.StartBasicBlock(bb);
111   builder.Gen<FakeInsnWithDefEarlyClobber>(vreg);
112   builder.Gen<PseudoJump>(kNullGuestAddr);
113 
114   x86_64::LivenessAnalyzer liveness(&machine_ir);
115   liveness.Run();
116 
117   ExpectNoLiveIns(&liveness, bb, vreg);
118 }
119 
TEST(MachineLivenessAnalyzerTest,DefKillsUse)120 TEST(MachineLivenessAnalyzerTest, DefKillsUse) {
121   Arena arena;
122   x86_64::MachineIR machine_ir(&arena);
123 
124   x86_64::MachineIRBuilder builder(&machine_ir);
125   MachineReg vreg = machine_ir.AllocVReg();
126 
127   auto* bb = machine_ir.NewBasicBlock();
128 
129   builder.StartBasicBlock(bb);
130   builder.Gen<x86_64::MovqRegImm>(vreg, 0);
131   builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg);
132   builder.Gen<PseudoJump>(kNullGuestAddr);
133 
134   x86_64::LivenessAnalyzer liveness(&machine_ir);
135   liveness.Run();
136 
137   ExpectNoLiveIns(&liveness, bb, vreg);
138 }
139 
TEST(MachineLivenessAnalyzerTest,DefDoesNotKillUseInSameInstruction)140 TEST(MachineLivenessAnalyzerTest, DefDoesNotKillUseInSameInstruction) {
141   Arena arena;
142   x86_64::MachineIR machine_ir(&arena);
143 
144   x86_64::MachineIRBuilder builder(&machine_ir);
145   MachineReg vreg = machine_ir.AllocVReg();
146 
147   auto* bb = machine_ir.NewBasicBlock();
148 
149   builder.StartBasicBlock(bb);
150   builder.Gen<x86_64::MovqRegReg>(vreg, vreg);
151   builder.Gen<PseudoJump>(kNullGuestAddr);
152 
153   x86_64::LivenessAnalyzer liveness(&machine_ir);
154   liveness.Run();
155 
156   ExpectSingleLiveIn(&liveness, bb, vreg);
157 }
158 
TEST(MachineLivenessAnalyzerTest,DefDoesNotKillAnotherVReg)159 TEST(MachineLivenessAnalyzerTest, DefDoesNotKillAnotherVReg) {
160   Arena arena;
161   x86_64::MachineIR machine_ir(&arena);
162 
163   x86_64::MachineIRBuilder builder(&machine_ir);
164   MachineReg vreg1 = machine_ir.AllocVReg();
165   MachineReg vreg2 = machine_ir.AllocVReg();
166 
167   auto* bb = machine_ir.NewBasicBlock();
168 
169   builder.StartBasicBlock(bb);
170   builder.Gen<x86_64::MovqRegImm>(vreg1, 0);
171   builder.Gen<x86_64::MovqRegReg>(x86_64::kMachineRegRAX, vreg2);
172   builder.Gen<PseudoJump>(kNullGuestAddr);
173 
174   x86_64::LivenessAnalyzer liveness(&machine_ir);
175   liveness.Run();
176 
177   ExpectSingleLiveIn(&liveness, bb, vreg2, vreg1);
178 }
179 
TEST(MachineLivenessAnalyzerTest,DataFlowAcrossBasicBlocks)180 TEST(MachineLivenessAnalyzerTest, DataFlowAcrossBasicBlocks) {
181   Arena arena;
182   x86_64::MachineIR machine_ir(&arena);
183 
184   auto [bb1, bb2, bb3, vreg1, vreg2] = BuildDataFlowAcrossBasicBlocks(&machine_ir);
185 
186   x86_64::LivenessAnalyzer liveness(&machine_ir);
187   liveness.Run();
188 
189   ExpectNoLiveIns(&liveness, bb1, vreg1, vreg2);
190   ExpectTwoLiveIns(&liveness, bb2, vreg1, vreg2);
191   ExpectSingleLiveIn(&liveness, bb3, vreg1, vreg2);
192 }
193 
TEST(MachineLivenessAnalyzerTest,DataFlowFromTwoPreds)194 TEST(MachineLivenessAnalyzerTest, DataFlowFromTwoPreds) {
195   Arena arena;
196   x86_64::MachineIR machine_ir(&arena);
197 
198   auto [bb1, bb2, bb3, vreg] = BuildDataFlowFromTwoPreds(&machine_ir);
199 
200   x86_64::LivenessAnalyzer liveness(&machine_ir);
201   liveness.Run();
202 
203   ExpectNoLiveIns(&liveness, bb1, vreg);
204   ExpectNoLiveIns(&liveness, bb2, vreg);
205   ExpectSingleLiveIn(&liveness, bb3, vreg);
206 }
207 
TEST(MachineLivenessAnalyzerTest,DataFlowToTwoSuccs)208 TEST(MachineLivenessAnalyzerTest, DataFlowToTwoSuccs) {
209   Arena arena;
210   x86_64::MachineIR machine_ir(&arena);
211 
212   auto [bb1, bb2, bb3, vreg] = BuildDataFlowToTwoSuccs(&machine_ir);
213 
214   x86_64::LivenessAnalyzer liveness(&machine_ir);
215   liveness.Run();
216 
217   ExpectNoLiveIns(&liveness, bb1, vreg);
218   ExpectSingleLiveIn(&liveness, bb2, vreg);
219   ExpectSingleLiveIn(&liveness, bb3, vreg);
220 }
221 
TEST(MachineLivenessAnalyzerTest,DataFlowAcrossEmptyLoop)222 TEST(MachineLivenessAnalyzerTest, DataFlowAcrossEmptyLoop) {
223   Arena arena;
224   x86_64::MachineIR machine_ir(&arena);
225 
226   auto [bb1, bb2, bb3, bb4, vreg] = BuildDataFlowAcrossEmptyLoop(&machine_ir);
227 
228   x86_64::LivenessAnalyzer liveness(&machine_ir);
229   liveness.Run();
230 
231   ExpectNoLiveIns(&liveness, bb1, vreg);
232   ExpectSingleLiveIn(&liveness, bb2, vreg);
233   ExpectSingleLiveIn(&liveness, bb3, vreg);
234   ExpectSingleLiveIn(&liveness, bb4, vreg);
235 }
236 
237 }  // namespace
238 
239 }  // namespace berberis
240