kernel_cfg.cc revision 11308:7d8836fd043d
16498Snate@binkert.org/* 26498Snate@binkert.org * Copyright (c) 2012-2015 Advanced Micro Devices, Inc. 36498Snate@binkert.org * All rights reserved. 46498Snate@binkert.org * 56498Snate@binkert.org * For use for simulation and test purposes only 66498Snate@binkert.org * 76498Snate@binkert.org * Redistribution and use in source and binary forms, with or without 86498Snate@binkert.org * modification, are permitted provided that the following conditions are met: 96498Snate@binkert.org * 106498Snate@binkert.org * 1. Redistributions of source code must retain the above copyright notice, 116498Snate@binkert.org * this list of conditions and the following disclaimer. 126498Snate@binkert.org * 136498Snate@binkert.org * 2. Redistributions in binary form must reproduce the above copyright notice, 146498Snate@binkert.org * this list of conditions and the following disclaimer in the documentation 156498Snate@binkert.org * and/or other materials provided with the distribution. 166498Snate@binkert.org * 176498Snate@binkert.org * 3. Neither the name of the copyright holder nor the names of its contributors 186498Snate@binkert.org * may be used to endorse or promote products derived from this software 196498Snate@binkert.org * without specific prior written permission. 206498Snate@binkert.org * 216498Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 226498Snate@binkert.org * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 236498Snate@binkert.org * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 246498Snate@binkert.org * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 256498Snate@binkert.org * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 266498Snate@binkert.org * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 276498Snate@binkert.org * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 286498Snate@binkert.org * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 296498Snate@binkert.org * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 306498Snate@binkert.org * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 316498Snate@binkert.org * POSSIBILITY OF SUCH DAMAGE. 326498Snate@binkert.org * 336498Snate@binkert.org * Author: Steve Reinhardt 346498Snate@binkert.org */ 356498Snate@binkert.org 366498Snate@binkert.org#include "gpu-compute/kernel_cfg.hh" 376498Snate@binkert.org 386498Snate@binkert.org#include <algorithm> 396498Snate@binkert.org#include <cassert> 406498Snate@binkert.org#include <cstdio> 416498Snate@binkert.org#include <cstring> 426498Snate@binkert.org#include <iostream> 436498Snate@binkert.org#include <iterator> 446498Snate@binkert.org#include <map> 456498Snate@binkert.org#include <string> 466498Snate@binkert.org 476498Snate@binkert.org#include "gpu-compute/gpu_static_inst.hh" 486498Snate@binkert.org 496498Snate@binkert.orgvoid 506498Snate@binkert.orgControlFlowInfo::assignImmediatePostDominators( 516498Snate@binkert.org const std::vector<GPUStaticInst*>& instructions) 526498Snate@binkert.org{ 536498Snate@binkert.org ControlFlowInfo cfg(instructions); 546498Snate@binkert.org cfg.findImmediatePostDominators(); 556498Snate@binkert.org} 566498Snate@binkert.org 576498Snate@binkert.org 586498Snate@binkert.orgControlFlowInfo::ControlFlowInfo(const std::vector<GPUStaticInst*>& insts) : 596498Snate@binkert.org instructions(insts) 606498Snate@binkert.org{ 616498Snate@binkert.org createBasicBlocks(); 626498Snate@binkert.org connectBasicBlocks(); 636498Snate@binkert.org} 646498Snate@binkert.org 656498Snate@binkert.orgBasicBlock* 666498Snate@binkert.orgControlFlowInfo::basicBlock(int inst_num) const { 676498Snate@binkert.org for (auto& block: basicBlocks) { 686498Snate@binkert.org int first_block_id = block->firstInstruction->instNum(); 696498Snate@binkert.org if (inst_num >= first_block_id && 706498Snate@binkert.org inst_num < first_block_id + block->size) { 716498Snate@binkert.org return block.get(); 726498Snate@binkert.org } 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 break; 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