1/*
2 * Copyright (c) 2012-2015 Advanced Micro Devices, Inc.
3 * All rights reserved.
4 *
5 * For use for simulation and test purposes only
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the copyright holder nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 *
33 * Author: Steve Reinhardt
34 */
35
36#include "gpu-compute/kernel_cfg.hh"
37
38#include <algorithm>
39#include <cassert>
40#include <cstdio>
41#include <cstring>
42#include <iostream>
43#include <iterator>
44#include <map>
45#include <string>
46
47#include "gpu-compute/gpu_static_inst.hh"
48
49void
50ControlFlowInfo::assignImmediatePostDominators(
51 const std::vector<GPUStaticInst*>& instructions)
52{
53 ControlFlowInfo cfg(instructions);
54 cfg.findImmediatePostDominators();
55}
56
57
58ControlFlowInfo::ControlFlowInfo(const std::vector<GPUStaticInst*>& insts) :
59 instructions(insts)
60{
61 createBasicBlocks();
62 connectBasicBlocks();
63}
64
65BasicBlock*
66ControlFlowInfo::basicBlock(int inst_num) const {
67 for (auto& block: basicBlocks) {
68 int first_block_id = block->firstInstruction->instNum();
69 if (inst_num >= first_block_id &&
70 inst_num < first_block_id + block->size) {
71 return block.get();
72 }
73 }
74 return nullptr;
75}
76
77
78GPUStaticInst*
79ControlFlowInfo::lastInstruction(const BasicBlock* block) const
80{
81 if (block->isExit()) {
82 return nullptr;
83 }
84
85 return instructions.at(block->firstInstruction->instNum() +
86 block->size - 1);
87}
88
89BasicBlock*
90ControlFlowInfo::postDominator(const BasicBlock* block) const
91{
92 if (block->isExit()) {
93 return nullptr;
94 }
95 return basicBlock(lastInstruction(block)->ipdInstNum());
96}
97
98void
99ControlFlowInfo::createBasicBlocks()
100{
101 assert(!instructions.empty());
102 std::set<int> leaders;
103 // first instruction is a leader
104 leaders.insert(0);
105 for (int i = 1; i < instructions.size(); i++) {
106 GPUStaticInst* instruction = instructions[i];
107 if (instruction->o_type == Enums::OT_BRANCH) {
108 const int target_pc = instruction->getTargetPc();
109 leaders.insert(target_pc);
110 leaders.insert(i + 1);
111 }
112 }
113
114 size_t block_size = 0;
115 for (int i = 0; i < instructions.size(); i++) {
116 if (leaders.find(i) != leaders.end()) {
117 uint32_t id = basicBlocks.size();
118 if (id > 0) {
119 basicBlocks.back()->size = block_size;
120 }
121 block_size = 0;
122 basicBlocks.emplace_back(new BasicBlock(id, instructions[i]));
123 }
124 block_size++;
125 }
126 basicBlocks.back()->size = block_size;
127 // exit basic block
128 basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr));
129}
130
131void
132ControlFlowInfo::connectBasicBlocks()
133{
134 BasicBlock* exit_bb = basicBlocks.back().get();
135 for (auto& bb : basicBlocks) {
136 if (bb->isExit()) {
137 break;
138 }
139 GPUStaticInst* last = lastInstruction(bb.get());
140 if (last->o_type == Enums::OT_RET) {
141 bb->successorIds.insert(exit_bb->id);
142 continue;
143 }
144 if (last->o_type == Enums::OT_BRANCH) {
145 const uint32_t target_pc = last->getTargetPc();
146 BasicBlock* target_bb = basicBlock(target_pc);
147 bb->successorIds.insert(target_bb->id);
148 }
149
150 // Unconditional jump instructions have a unique successor
151 if (!last->unconditionalJumpInstruction()) {
152 BasicBlock* next_bb = basicBlock(last->instNum() + 1);
153 bb->successorIds.insert(next_bb->id);
154 }
155 }
156}
157
158
159// In-place set intersection
160static void
161intersect(std::set<uint32_t>& a, const std::set<uint32_t>& b)
162{
163 std::set<uint32_t>::iterator it = a.begin();
164 while (it != a.end()) {
165 it = b.find(*it) != b.end() ? ++it : a.erase(it);
166 }
167}
168
169
170void
171ControlFlowInfo::findPostDominators()
172{
173 // the only postdominator of the exit block is itself
174 basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id);
175 //copy all basic blocks to all postdominator lists except for exit block
176 for (auto& block : basicBlocks) {
177 if (!block->isExit()) {
178 for (uint32_t i = 0; i < basicBlocks.size(); i++) {
179 block->postDominatorIds.insert(i);
180 }
181 }
182 }
183
184 bool change = true;
185 while (change) {
186 change = false;
187 for (int h = basicBlocks.size() - 2; h >= 0; --h) {
188 size_t num_postdominators =
189 basicBlocks[h]->postDominatorIds.size();
190 for (int s : basicBlocks[h]->successorIds) {
191 intersect(basicBlocks[h]->postDominatorIds,
192 basicBlocks[s]->postDominatorIds);
193 }
194 basicBlocks[h]->postDominatorIds.insert(h);
195 change |= (num_postdominators
196 != basicBlocks[h]->postDominatorIds.size());
197 }
198 }
199}
200
201
202// In-place set difference
203static void
204setDifference(std::set<uint32_t>&a,
205 const std::set<uint32_t>& b, uint32_t exception)
206{
207 for (uint32_t b_elem : b) {
208 if (b_elem != exception) {
209 a.erase(b_elem);
210 }
211 }
212}
213
214void
215ControlFlowInfo::findImmediatePostDominators()
216{
217 assert(basicBlocks.size() > 1); // Entry and exit blocks must be present
218
219 findPostDominators();
220
221 for (auto& basicBlock : basicBlocks) {
222 if (basicBlock->isExit()) {
223 continue;
224 }
225 std::set<uint32_t> candidates = basicBlock->postDominatorIds;
226 candidates.erase(basicBlock->id);
227 for (uint32_t postDominatorId : basicBlock->postDominatorIds) {
228 if (postDominatorId != basicBlock->id) {
229 setDifference(candidates,
230 basicBlocks[postDominatorId]->postDominatorIds,
231 postDominatorId);
232 }
233 }
234 assert(candidates.size() == 1);
235 GPUStaticInst* last_instruction = lastInstruction(basicBlock.get());
236 BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get();
237 if (!ipd_block->isExit()) {
238 GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction;
239 last_instruction->ipdInstNum(ipd_first_inst->instNum());
240 } else {
241 last_instruction->ipdInstNum(last_instruction->instNum() + 1);
242 }
243 }
244}
245
246void
247ControlFlowInfo::printPostDominators() const
248{
249 for (auto& block : basicBlocks) {
250 std::cout << "PD(" << block->id << ") = {";
251 std::copy(block->postDominatorIds.begin(),
252 block->postDominatorIds.end(),
253 std::ostream_iterator<uint32_t>(std::cout, ", "));
254 std::cout << "}" << std::endl;
255 }
256}
257
258void
259ControlFlowInfo::printImmediatePostDominators() const
260{
261 for (const auto& block : basicBlocks) {
262 if (block->isExit()) {
263 continue;
264 }
265 std::cout << "IPD(" << block->id << ") = ";
266 std::cout << postDominator(block.get())->id << ", ";
267 }
268 std::cout << std::endl;
269}
270void
271ControlFlowInfo::printBasicBlocks() const
272{
273 for (GPUStaticInst* inst : instructions) {
274 int inst_num = inst->instNum();
275 std::cout << inst_num << " [" << basicBlock(inst_num)->id
276 << "]: " << inst->disassemble();
277 if (inst->o_type == Enums::OT_BRANCH) {
278 std::cout << ", PC = " << inst->getTargetPc();
279 }
280 std::cout << std::endl;
281 }
282}
283
284void
285ControlFlowInfo::printBasicBlockDot() const
286{
287 printf("digraph {\n");
288 for (const auto& basic_block : basicBlocks) {
289 printf("\t");
290 for (uint32_t successorId : basic_block->successorIds) {
291 printf("%d -> %d; ", basic_block->id, successorId);
292 }
293 printf("\n");
294 }
295 printf("}\n");
296}