2 * Copyright (c) 2012-2015 Advanced Micro Devices, Inc.
5 * For use for simulation and test purposes only
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
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.
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.
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.
33 * Author: Steve Reinhardt
36 #include "gpu-compute/kernel_cfg.hh"
47 #include "gpu-compute/gpu_static_inst.hh"
50 ControlFlowInfo::assignImmediatePostDominators(
51 const std::vector
<GPUStaticInst
*>& instructions
)
53 ControlFlowInfo
cfg(instructions
);
54 cfg
.findImmediatePostDominators();
58 ControlFlowInfo::ControlFlowInfo(const std::vector
<GPUStaticInst
*>& insts
) :
66 ControlFlowInfo::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
)) {
79 ControlFlowInfo::lastInstruction(const BasicBlock
* block
) const
81 if (block
->isExit()) {
85 return instructions
.at(block
->firstInstruction
->instNum() +
90 ControlFlowInfo::postDominator(const BasicBlock
* block
) const
92 if (block
->isExit()) {
95 return basicBlock(lastInstruction(block
)->ipdInstNum());
99 ControlFlowInfo::createBasicBlocks()
101 assert(!instructions
.empty());
102 std::set
<int> leaders
;
103 // first instruction is a leader
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());
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();
118 basicBlocks
.back()->size
= block_size
;
121 basicBlocks
.emplace_back(new BasicBlock(id
, instruction
));
125 basicBlocks
.back()->size
= block_size
;
127 basicBlocks
.emplace_back(new BasicBlock(basicBlocks
.size(), nullptr));
131 ControlFlowInfo::connectBasicBlocks()
133 BasicBlock
* exit_bb
= basicBlocks
.back().get();
134 for (auto& bb
: basicBlocks
) {
138 GPUStaticInst
* last
= lastInstruction(bb
.get());
139 if (last
->isReturn()) {
140 bb
->successorIds
.insert(exit_bb
->id
);
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
);
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
);
158 // In-place set intersection
160 intersect(std::set
<uint32_t>& a
, const std::set
<uint32_t>& b
)
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
);
170 ControlFlowInfo::findPostDominators()
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
);
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
);
193 basicBlocks
[h
]->postDominatorIds
.insert(h
);
194 change
|= (num_postdominators
195 != basicBlocks
[h
]->postDominatorIds
.size());
201 // In-place set difference
203 setDifference(std::set
<uint32_t>&a
,
204 const std::set
<uint32_t>& b
, uint32_t exception
)
206 for (uint32_t b_elem
: b
) {
207 if (b_elem
!= exception
) {
214 ControlFlowInfo::findImmediatePostDominators()
216 assert(basicBlocks
.size() > 1); // Entry and exit blocks must be present
218 findPostDominators();
220 for (auto& basicBlock
: basicBlocks
) {
221 if (basicBlock
->isExit()) {
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
,
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());
240 last_instruction
->ipdInstNum(last_instruction
->nextInstAddr());
246 ControlFlowInfo::printPostDominators() const
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
;
258 ControlFlowInfo::printImmediatePostDominators() const
260 for (const auto& block
: basicBlocks
) {
261 if (block
->isExit()) {
264 std::cout
<< "IPD(" << block
->id
<< ") = ";
265 std::cout
<< postDominator(block
.get())->id
<< ", ";
267 std::cout
<< std::endl
;
270 ControlFlowInfo::printBasicBlocks() const
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();
279 std::cout
<< std::endl
;
284 ControlFlowInfo::printBasicBlockDot() const
286 printf("digraph {\n");
287 for (const auto& basic_block
: basicBlocks
) {
289 for (uint32_t successorId
: basic_block
->successorIds
) {
290 printf("%d -> %d; ", basic_block
->id
, successorId
);