kernel_cfg.cc revision 11623:b56cbe6b63a2 
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}
297