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/rename_vregs.h"
18
19 #include <algorithm> // std::max
20
21 #include "berberis/backend/x86_64/liveness_analyzer.h"
22 #include "berberis/backend/x86_64/machine_ir.h"
23
24 namespace berberis::x86_64 {
25
AssignNewVRegs()26 void VRegMap::AssignNewVRegs() {
27 for (auto* bb : machine_ir_->bb_list()) {
28 for (auto* insn : bb->insn_list()) {
29 for (int i = 0; i < insn->NumRegOperands(); ++i) {
30 auto reg = insn->RegAt(i);
31 if (reg.IsVReg()) {
32 insn->SetRegAt(i, Get(reg, bb));
33 auto& max_size = max_size_.at(reg.GetVRegIndex());
34 max_size = std::max(max_size, insn->RegKindAt(i).RegClass()->RegSize());
35 }
36 }
37 }
38 }
39 }
40
Get(MachineReg reg,const MachineBasicBlock * bb)41 MachineReg VRegMap::Get(MachineReg reg, const MachineBasicBlock* bb) {
42 CHECK(reg.IsVReg());
43 MachineReg& mapped_reg = map_.at(bb->id()).at(reg.GetVRegIndex());
44 if (mapped_reg == kInvalidMachineReg) {
45 mapped_reg = machine_ir_->AllocVReg();
46 }
47 return mapped_reg;
48 }
49
GenInterBasicBlockMove(MachineIR * machine_ir,VRegMap * vreg_map,MachineBasicBlock * pred_bb,MachineBasicBlock * succ_bb,MachineReg vreg)50 void GenInterBasicBlockMove(MachineIR* machine_ir,
51 VRegMap* vreg_map,
52 MachineBasicBlock* pred_bb,
53 MachineBasicBlock* succ_bb,
54 MachineReg vreg) {
55 MachineReg pred_vreg = vreg_map->Get(vreg, pred_bb);
56 MachineReg succ_vreg = vreg_map->Get(vreg, succ_bb);
57 PseudoCopy* insn =
58 machine_ir->NewInsn<PseudoCopy>(succ_vreg, pred_vreg, vreg_map->GetMaxSize(vreg));
59
60 if (succ_bb->in_edges().size() == 1) {
61 // Successor has single pred.
62 // Build move at the beginning of succ.
63 succ_bb->insn_list().insert(succ_bb->insn_list().begin(), insn);
64 succ_bb->live_in().push_back(pred_vreg);
65 pred_bb->live_out().push_back(pred_vreg);
66 } else {
67 // Successor has multiple preds.
68 // Assume no critical edges, so pred has just one succ.
69 // Build move at the end of pred.
70 CHECK_EQ(pred_bb->out_edges().size(), 1);
71 pred_bb->insn_list().insert(--pred_bb->insn_list().end(), insn);
72 succ_bb->live_in().push_back(succ_vreg);
73 pred_bb->live_out().push_back(succ_vreg);
74 }
75 }
76
77 // Rename vregs so that they have different names in different basic blocks
78 // and build the data-flow connecting moves.
RenameVRegs(MachineIR * machine_ir)79 void RenameVRegs(MachineIR* machine_ir) {
80 LivenessAnalyzer liveness(machine_ir);
81 VRegMap vreg_map(machine_ir);
82
83 // We want to analyze liveness before assigning new vregs.
84 liveness.Run();
85 vreg_map.AssignNewVRegs();
86
87 // Build moves connecting the data-flow.
88 for (auto bb : machine_ir->bb_list()) {
89 for (auto edge : bb->out_edges()) {
90 auto succ_bb = edge->dst();
91 for (auto vreg = liveness.GetFirstLiveIn(succ_bb); vreg != kInvalidMachineReg;
92 vreg = liveness.GetNextLiveIn(succ_bb, vreg)) {
93 GenInterBasicBlockMove(machine_ir, &vreg_map, bb, succ_bb, vreg);
94 }
95 }
96 }
97 }
98
99 } // namespace berberis::x86_64
100