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_analysis.h"
18
19 #include <algorithm>
20
21 #include "berberis/backend/common/machine_ir.h"
22 #include "berberis/backend/x86_64/machine_ir.h"
23 #include "berberis/base/algorithm.h"
24 #include "berberis/base/arena_alloc.h"
25 #include "berberis/base/arena_vector.h"
26 #include "berberis/base/logging.h"
27
28 namespace berberis::x86_64 {
29
30 namespace {
31
32 class LoopBuilder {
33 public:
LoopBuilder(MachineIR * ir,Loop * loop,MachineBasicBlock * loop_head)34 LoopBuilder(MachineIR* ir, Loop* loop, MachineBasicBlock* loop_head)
35 : loop_(loop), is_bb_in_loop_(ir->NumBasicBlocks(), false, ir->arena()) {
36 CHECK_EQ(loop_->size(), 0u);
37 loop_->reserve(ir->NumBasicBlocks());
38 loop_->push_back(loop_head);
39 is_bb_in_loop_[loop_head->id()] = true;
40 }
41
42 // Appends bb to loop (bb-vector) unless bb is already in loop.
43 // Returns whether bb is appended.
PushBackIfNotInLoop(MachineBasicBlock * bb)44 bool PushBackIfNotInLoop(MachineBasicBlock* bb) {
45 if (is_bb_in_loop_[bb->id()]) {
46 return false;
47 }
48 loop_->push_back(bb);
49 is_bb_in_loop_[bb->id()] = true;
50 return true;
51 }
52
53 private:
54 Loop* loop_;
55 ArenaVector<bool> is_bb_in_loop_;
56 };
57
PostOrderTraverseBBListRecursive(MachineBasicBlock * bb,ArenaVector<bool> & is_visited,MachineBasicBlockList & result)58 void PostOrderTraverseBBListRecursive(MachineBasicBlock* bb,
59 ArenaVector<bool>& is_visited,
60 MachineBasicBlockList& result) {
61 is_visited[bb->id()] = true;
62 for (auto* edge : bb->out_edges()) {
63 auto* dst = edge->dst();
64 if (!is_visited[dst->id()]) {
65 PostOrderTraverseBBListRecursive(dst, is_visited, result);
66 }
67 }
68 // We push to front so that the post order list is automatically reversed.
69 result.push_front(bb);
70 }
71
CompareBackEdges(const MachineEdge * left,const MachineEdge * right)72 bool CompareBackEdges(const MachineEdge* left, const MachineEdge* right) {
73 return left->dst()->id() < right->dst()->id();
74 }
75
CollectLoop(MachineIR * ir,const MachineEdgeVector & back_edges,size_t begin,size_t end)76 Loop* CollectLoop(MachineIR* ir, const MachineEdgeVector& back_edges, size_t begin, size_t end) {
77 Arena* arena = ir->arena();
78 auto* loop = NewInArena<Loop>(arena, arena);
79 auto* head_bb = back_edges[begin]->dst();
80
81 LoopBuilder builder(ir, loop, head_bb);
82
83 for (size_t edge_no = begin; edge_no < end; ++edge_no) {
84 auto* back_branch_bb = back_edges[edge_no]->src();
85 // All back-edges must be to the same head.
86 CHECK_EQ(back_edges[edge_no]->dst(), head_bb);
87
88 if (!builder.PushBackIfNotInLoop(back_branch_bb)) {
89 // We have already processed this basic-block (and consequently
90 // all its predecessors) while processing another back-edge.
91 continue;
92 }
93
94 // Go from back-branching bb to (tentatively) dominating
95 // loop head collecting all passed bbs.
96 for (size_t bb_no = loop->size() - 1; bb_no < loop->size(); ++bb_no) {
97 auto* bb = loop->at(bb_no);
98
99 if (bb->in_edges().size() == 0) {
100 // Reached start-bb: head doesn't dominate back_branch_bb.
101 // Loop is irreducible - ignore it.
102 return nullptr;
103 }
104
105 for (auto in_edge : bb->in_edges()) {
106 builder.PushBackIfNotInLoop(in_edge->src());
107 }
108 } // Walk new loop-bbs
109 } // Walk back
110 return loop;
111 }
112
113 } // namespace
114
GetReversePostOrderBBList(MachineIR * ir)115 MachineBasicBlockList GetReversePostOrderBBList(MachineIR* ir) {
116 if (ir->bb_order() == MachineIR::BasicBlockOrder::kReversePostOrder) {
117 return ir->bb_list();
118 }
119 MachineBasicBlock* entry_bb = ir->bb_list().front();
120 CHECK_EQ(entry_bb->in_edges().size(), 0);
121
122 ArenaVector<bool> is_visited(ir->NumBasicBlocks(), false, ir->arena());
123 MachineBasicBlockList rpo_list(ir->arena());
124 PostOrderTraverseBBListRecursive(entry_bb, is_visited, rpo_list);
125 return rpo_list;
126 }
127
FindLoops(MachineIR * ir)128 LoopVector FindLoops(MachineIR* ir) {
129 Arena* arena = ir->arena();
130 ArenaVector<bool> is_visited(ir->NumBasicBlocks(), false, arena);
131 LoopVector loops_vector(arena);
132
133 const size_t kMaxBackEdgesExpected = 16;
134 loops_vector.reserve(kMaxBackEdgesExpected);
135
136 ArenaVector<MachineEdge*> back_edges(arena);
137 back_edges.reserve(kMaxBackEdgesExpected);
138
139 // Collects back-edges.
140 // Traversal relies on the reverse post order of basic-blocks.
141 for (auto* bb : GetReversePostOrderBBList(ir)) {
142 is_visited[bb->id()] = true;
143
144 for (auto* edge : bb->out_edges()) {
145 MachineBasicBlock* succ_bb = edge->dst();
146
147 if (is_visited[succ_bb->id()]) {
148 back_edges.push_back(edge);
149 }
150 } // Walk bb-succs
151 } // Walk basic-blocks
152
153 // Pull back-edges with the same target (loop head) together.
154 std::sort(back_edges.begin(), back_edges.end(), CompareBackEdges);
155
156 // Guard which makes the following loop-body simpler.
157 auto empty_edge = MachineEdge(arena, nullptr, nullptr);
158 back_edges.push_back(&empty_edge);
159
160 size_t begin_edge_no = 0;
161 // Collect loops for back-edges with the same target.
162 for (size_t edge_no = 1; edge_no < back_edges.size(); ++edge_no) {
163 if (back_edges[begin_edge_no]->dst() == back_edges[edge_no]->dst()) {
164 continue;
165 }
166 // Encountered new head - collect loop for the previous one.
167 // Guard (being the last) doesn't require loop collection.
168 auto* loop = CollectLoop(ir, back_edges, begin_edge_no, edge_no);
169 if (loop) {
170 loops_vector.push_back(loop);
171 }
172 begin_edge_no = edge_no;
173 }
174 return loops_vector;
175 }
176
TryInsertLoopAtNode(LoopTreeNode * node,Loop * loop)177 bool LoopTree::TryInsertLoopAtNode(LoopTreeNode* node, Loop* loop) {
178 if (node->loop() != nullptr && !Contains(*node->loop(), loop->at(0))) {
179 return false;
180 }
181
182 for (size_t i = 0; i < node->NumInnerloops(); i++) {
183 auto* innerloop_node = node->GetInnerloopNode(i);
184 if (TryInsertLoopAtNode(innerloop_node, loop)) {
185 return true;
186 }
187 }
188
189 LoopTreeNode* innerloop_node = NewInArena<LoopTreeNode>(ir_->arena(), ir_, loop);
190 node->AddInnerloopNode(innerloop_node);
191 return true;
192 }
193
BuildLoopTree(MachineIR * ir)194 LoopTree BuildLoopTree(MachineIR* ir) {
195 auto loops = FindLoops(ir);
196 std::sort(loops.begin(), loops.end(), [](auto* loop1, auto* loop2) {
197 return loop1->size() > loop2->size();
198 });
199
200 LoopTree loop_tree(ir);
201 for (auto* loop : loops) {
202 loop_tree.InsertLoop(loop);
203 }
204
205 return loop_tree;
206 }
207
208 } // namespace berberis::x86_64
209