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/machine_ir_check.h"
18
19 #include "berberis/backend/x86_64/machine_ir.h"
20 #include "berberis/base/algorithm.h"
21
22 namespace berberis::x86_64 {
23
24 namespace {
25
CheckEdgeInVector(const MachineEdge * target_edge,const MachineEdgeVector & edge_vector)26 bool CheckEdgeInVector(const MachineEdge* target_edge, const MachineEdgeVector& edge_vector) {
27 return Contains(edge_vector, target_edge);
28 }
29
CheckBasicBlockInIR(const MachineBasicBlock * bb,const MachineIR & machine_ir)30 bool CheckBasicBlockInIR(const MachineBasicBlock* bb, const MachineIR& machine_ir) {
31 auto& bb_list = machine_ir.bb_list();
32 return Contains(bb_list, bb);
33 }
34
CheckNoDanglingEdgesOrBasicBlocks(const MachineIR & machine_ir,const MachineBasicBlock * bb)35 MachineIRCheckStatus CheckNoDanglingEdgesOrBasicBlocks(const MachineIR& machine_ir,
36 const MachineBasicBlock* bb) {
37 if (bb->out_edges().size() == 0 && bb->in_edges().size() == 0) {
38 if (machine_ir.bb_list().size() != 1) {
39 return kMachineIRCheckDanglingBasicBlock;
40 }
41 return kMachineIRCheckSuccess;
42 }
43
44 for (auto* edge : bb->out_edges()) {
45 if (!CheckEdgeInVector(edge, edge->dst()->in_edges())) {
46 return kMachineIRCheckDanglingEdge;
47 }
48 if (!CheckBasicBlockInIR(edge->dst(), machine_ir)) {
49 return kMachineIRCheckDanglingBasicBlock;
50 }
51 }
52 for (auto* edge : bb->in_edges()) {
53 if (!CheckEdgeInVector(edge, edge->src()->out_edges())) {
54 return kMachineIRCheckDanglingEdge;
55 }
56 if (!CheckBasicBlockInIR(edge->src(), machine_ir)) {
57 return kMachineIRCheckDanglingBasicBlock;
58 }
59 }
60 return kMachineIRCheckSuccess;
61 }
62
CheckInOutEdgesLinksToBasicBlock(const MachineBasicBlock * bb)63 bool CheckInOutEdgesLinksToBasicBlock(const MachineBasicBlock* bb) {
64 for (auto* edge : bb->in_edges()) {
65 if (edge->dst() != bb) {
66 return false;
67 }
68 }
69 for (auto* edge : bb->out_edges()) {
70 if (edge->src() != bb) {
71 return false;
72 }
73 }
74 return true;
75 }
76
IsBasicBlockSuccessor(const MachineBasicBlock * src,const MachineBasicBlock * dst)77 bool IsBasicBlockSuccessor(const MachineBasicBlock* src, const MachineBasicBlock* dst) {
78 for (auto* edge : src->out_edges()) {
79 if (edge->dst() == dst) {
80 return true;
81 }
82 }
83 return false;
84 }
85
CheckControlTransferInsn(const MachineBasicBlock * bb)86 bool CheckControlTransferInsn(const MachineBasicBlock* bb) {
87 for (auto* insn : bb->insn_list()) {
88 switch (insn->opcode()) {
89 case MachineOpcode::kMachineOpPseudoIndirectJump:
90 return insn == bb->insn_list().back();
91 case MachineOpcode::kMachineOpPseudoJump:
92 return insn == bb->insn_list().back();
93 case MachineOpcode::kMachineOpPseudoBranch: {
94 if (insn != bb->insn_list().back()) {
95 return false;
96 }
97 const PseudoBranch* branch = reinterpret_cast<const PseudoBranch*>(insn);
98 return IsBasicBlockSuccessor(bb, branch->then_bb());
99 }
100 case MachineOpcode::kMachineOpPseudoCondBranch: {
101 if (insn != bb->insn_list().back()) {
102 return false;
103 }
104 const PseudoCondBranch* cond_branch = reinterpret_cast<const PseudoCondBranch*>(insn);
105 return IsBasicBlockSuccessor(bb, cond_branch->then_bb()) &&
106 IsBasicBlockSuccessor(bb, cond_branch->else_bb());
107 }
108 default:
109 continue;
110 }
111 }
112 return false;
113 }
114
CheckCFG(const MachineIR & machine_ir)115 MachineIRCheckStatus CheckCFG(const MachineIR& machine_ir) {
116 for (auto* bb : machine_ir.bb_list()) {
117 if (!CheckInOutEdgesLinksToBasicBlock(bb)) {
118 return kMachineIRCheckFail;
119 }
120 auto status = CheckNoDanglingEdgesOrBasicBlocks(machine_ir, bb);
121 if (status != kMachineIRCheckSuccess) {
122 return status;
123 }
124 if (!CheckControlTransferInsn(bb)) {
125 return kMachineIRCheckFail;
126 }
127 }
128 return kMachineIRCheckSuccess;
129 }
130
131 } // namespace
132
CheckMachineIR(const MachineIR & machine_ir)133 MachineIRCheckStatus CheckMachineIR(const MachineIR& machine_ir) {
134 return CheckCFG(machine_ir);
135 }
136
137 } // namespace berberis::x86_64
138