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_addr) const {
67    for (auto& block: basicBlocks) {
68       int first_block_addr = block->firstInstruction->instAddr();
69       if (inst_addr >= first_block_addr && inst_addr <
70           first_block_addr + block->size * sizeof(TheGpuISA::RawMachInst)) {
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 (const auto &instruction : instructions) {
106        if (instruction->isBranch()) {
107            const int target_pc = instruction->getTargetPc();
108            leaders.insert(target_pc);
109            leaders.insert(instruction->nextInstAddr());
110        }
111    }
112
113    size_t block_size = 0;
114    for (const auto &instruction : instructions) {
115        if (leaders.find(instruction->instAddr()) != leaders.end()) {
116            uint32_t id = basicBlocks.size();
117            if (id > 0) {
118                basicBlocks.back()->size = block_size;
119            }
120            block_size = 0;
121            basicBlocks.emplace_back(new BasicBlock(id, instruction));
122        }
123        block_size++;
124    }
125    basicBlocks.back()->size = block_size;
126    // exit basic block
127    basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr));
128}
129
130void
131ControlFlowInfo::connectBasicBlocks()
132{
133    BasicBlock* exit_bb = basicBlocks.back().get();
134    for (auto& bb : basicBlocks) {
135        if (bb->isExit()) {
136            break;
137        }
138        GPUStaticInst* last = lastInstruction(bb.get());
139        if (last->isReturn()) {
140            bb->successorIds.insert(exit_bb->id);
141            continue;
142        }
143        if (last->isBranch()) {
144            const uint32_t target_pc = last->getTargetPc();
145            BasicBlock* target_bb = basicBlock(target_pc);
146            bb->successorIds.insert(target_bb->id);
147        }
148
149        // Unconditional jump instructions have a unique successor
150        if (!last->isUnconditionalJump()) {
151            BasicBlock* next_bb = basicBlock(last->nextInstAddr());
152            bb->successorIds.insert(next_bb->id);
153        }
154    }
155}
156
157
158// In-place set intersection
159static void
160intersect(std::set<uint32_t>& a, const std::set<uint32_t>& b)
161{
162    std::set<uint32_t>::iterator it = a.begin();
163    while (it != a.end()) {
164        it = b.find(*it) != b.end() ? ++it : a.erase(it);
165    }
166}
167
168
169void
170ControlFlowInfo::findPostDominators()
171{
172    // the only postdominator of the exit block is itself
173    basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id);
174    //copy all basic blocks to all postdominator lists except for exit block
175    for (auto& block : basicBlocks) {
176        if (!block->isExit()) {
177            for (uint32_t i = 0; i < basicBlocks.size(); i++) {
178                block->postDominatorIds.insert(i);
179            }
180        }
181    }
182
183    bool change = true;
184    while (change) {
185        change = false;
186        for (int h = basicBlocks.size() - 2; h >= 0; --h) {
187            size_t num_postdominators =
188                    basicBlocks[h]->postDominatorIds.size();
189            for (int s : basicBlocks[h]->successorIds) {
190                intersect(basicBlocks[h]->postDominatorIds,
191                          basicBlocks[s]->postDominatorIds);
192            }
193            basicBlocks[h]->postDominatorIds.insert(h);
194            change |= (num_postdominators
195                    != basicBlocks[h]->postDominatorIds.size());
196        }
197    }
198}
199
200
201// In-place set difference
202static void
203setDifference(std::set<uint32_t>&a,
204           const std::set<uint32_t>& b, uint32_t exception)
205{
206    for (uint32_t b_elem : b) {
207        if (b_elem != exception) {
208            a.erase(b_elem);
209        }
210    }
211}
212
213void
214ControlFlowInfo::findImmediatePostDominators()
215{
216    assert(basicBlocks.size() > 1); // Entry and exit blocks must be present
217
218    findPostDominators();
219
220    for (auto& basicBlock : basicBlocks) {
221        if (basicBlock->isExit()) {
222            continue;
223        }
224        std::set<uint32_t> candidates = basicBlock->postDominatorIds;
225        candidates.erase(basicBlock->id);
226        for (uint32_t postDominatorId : basicBlock->postDominatorIds) {
227            if (postDominatorId != basicBlock->id) {
228                setDifference(candidates,
229                           basicBlocks[postDominatorId]->postDominatorIds,
230                           postDominatorId);
231            }
232        }
233        assert(candidates.size() == 1);
234        GPUStaticInst* last_instruction = lastInstruction(basicBlock.get());
235        BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get();
236        if (!ipd_block->isExit()) {
237            GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction;
238            last_instruction->ipdInstNum(ipd_first_inst->instAddr());
239        } else {
240            last_instruction->ipdInstNum(last_instruction->nextInstAddr());
241        }
242    }
243}
244
245void
246ControlFlowInfo::printPostDominators() const
247{
248    for (auto& block : basicBlocks) {
249        std::cout << "PD(" << block->id << ") = {";
250        std::copy(block->postDominatorIds.begin(),
251                  block->postDominatorIds.end(),
252                  std::ostream_iterator<uint32_t>(std::cout, ", "));
253        std::cout << "}" << std::endl;
254    }
255}
256
257void
258ControlFlowInfo::printImmediatePostDominators() const
259{
260    for (const auto& block : basicBlocks) {
261        if (block->isExit()) {
262            continue;
263        }
264        std::cout << "IPD(" << block->id << ") = ";
265        std::cout << postDominator(block.get())->id << ", ";
266    }
267    std::cout << std::endl;
268}
269void
270ControlFlowInfo::printBasicBlocks() const
271{
272    for (GPUStaticInst* inst : instructions) {
273        int inst_addr = inst->instAddr();
274        std::cout << inst_addr << " [" << basicBlock(inst_addr)->id
275                << "]: " << inst->disassemble();
276        if (inst->isBranch()) {
277            std::cout << ", PC = " << inst->getTargetPc();
278        }
279        std::cout << std::endl;
280    }
281}
282
283void
284ControlFlowInfo::printBasicBlockDot() const
285{
286    printf("digraph {\n");
287    for (const auto& basic_block : basicBlocks) {
288        printf("\t");
289        for (uint32_t successorId : basic_block->successorIds) {
290            printf("%d -> %d; ", basic_block->id, successorId);
291        }
292        printf("\n");
293    }
294    printf("}\n");
295}
296