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#ifndef __KERNEL_CFG_HH__
37#define __KERNEL_CFG_HH__
38
39#include <cstddef>
40#include <cstdint>
41#include <memory>
42#include <set>
43#include <vector>
44
45
46class GPUStaticInst;
47class HsailCode;
48
49struct BasicBlock
50{
51    BasicBlock(uint32_t num, GPUStaticInst* begin) :
52            id(num), size(0), firstInstruction(begin)
53    {
54    }
55
56    bool
57    isEntry() const
58    {
59        return !id;
60    }
61
62    bool
63    isExit() const
64    {
65        return !size;
66    }
67
68    /**
69     * Unique identifier for the block within a given kernel.
70     */
71    const uint32_t id;
72
73    /**
74     * Number of instructions contained in the block
75     */
76    size_t size;
77
78    /**
79     * Pointer to first instruction of the block.
80     */
81    GPUStaticInst* firstInstruction;
82
83    /**
84     * Identifiers of the blocks that follow (are reachable from) this block.
85     */
86    std::set<uint32_t> successorIds;
87
88    /**
89     * Identifiers of the blocks that will be visited from this block.
90     */
91    std::set<uint32_t> postDominatorIds;
92};
93
94class ControlFlowInfo
95{
96public:
97
98    /**
99     * Compute immediate post-dominator instruction for kernel instructions.
100     */
101    static void assignImmediatePostDominators(
102            const std::vector<GPUStaticInst*>& instructions);
103
104private:
105    ControlFlowInfo(const std::vector<GPUStaticInst*>& instructions);
106
107    GPUStaticInst* lastInstruction(const BasicBlock* block) const;
108
109    BasicBlock* basicBlock(int inst_addr) const;
110
111    BasicBlock* postDominator(const BasicBlock* block) const;
112
113    void createBasicBlocks();
114
115    void connectBasicBlocks();
116
117    void findPostDominators();
118
119    void findImmediatePostDominators();
120
121    void printBasicBlocks() const;
122
123    void printBasicBlockDot() const;
124
125    void printPostDominators() const;
126
127    void printImmediatePostDominators() const;
128
129    std::vector<std::unique_ptr<BasicBlock>> basicBlocks;
130    std::vector<GPUStaticInst*> instructions;
131};
132
133#endif // __KERNEL_CFG_HH__
134