kernel_cfg.cc revision 11623
111308Santhony.gutierrez@amd.com/* 211308Santhony.gutierrez@amd.com * Copyright (c) 2012-2015 Advanced Micro Devices, Inc. 311308Santhony.gutierrez@amd.com * All rights reserved. 411308Santhony.gutierrez@amd.com * 511308Santhony.gutierrez@amd.com * For use for simulation and test purposes only 611308Santhony.gutierrez@amd.com * 711308Santhony.gutierrez@amd.com * Redistribution and use in source and binary forms, with or without 811308Santhony.gutierrez@amd.com * modification, are permitted provided that the following conditions are met: 911308Santhony.gutierrez@amd.com * 1011308Santhony.gutierrez@amd.com * 1. Redistributions of source code must retain the above copyright notice, 1111308Santhony.gutierrez@amd.com * this list of conditions and the following disclaimer. 1211308Santhony.gutierrez@amd.com * 1311308Santhony.gutierrez@amd.com * 2. Redistributions in binary form must reproduce the above copyright notice, 1411308Santhony.gutierrez@amd.com * this list of conditions and the following disclaimer in the documentation 1511308Santhony.gutierrez@amd.com * and/or other materials provided with the distribution. 1611308Santhony.gutierrez@amd.com * 1711308Santhony.gutierrez@amd.com * 3. Neither the name of the copyright holder nor the names of its contributors 1811308Santhony.gutierrez@amd.com * may be used to endorse or promote products derived from this software 1911308Santhony.gutierrez@amd.com * without specific prior written permission. 2011308Santhony.gutierrez@amd.com * 2111308Santhony.gutierrez@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 2211308Santhony.gutierrez@amd.com * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2311308Santhony.gutierrez@amd.com * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2411308Santhony.gutierrez@amd.com * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 2511308Santhony.gutierrez@amd.com * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2611308Santhony.gutierrez@amd.com * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2711308Santhony.gutierrez@amd.com * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2811308Santhony.gutierrez@amd.com * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2911308Santhony.gutierrez@amd.com * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 3011308Santhony.gutierrez@amd.com * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 3111308Santhony.gutierrez@amd.com * POSSIBILITY OF SUCH DAMAGE. 3211308Santhony.gutierrez@amd.com * 3311308Santhony.gutierrez@amd.com * Author: Steve Reinhardt 3411308Santhony.gutierrez@amd.com */ 3511308Santhony.gutierrez@amd.com 3611308Santhony.gutierrez@amd.com#include "gpu-compute/kernel_cfg.hh" 3711308Santhony.gutierrez@amd.com 3811308Santhony.gutierrez@amd.com#include <algorithm> 3911308Santhony.gutierrez@amd.com#include <cassert> 4011308Santhony.gutierrez@amd.com#include <cstdio> 4111308Santhony.gutierrez@amd.com#include <cstring> 4211308Santhony.gutierrez@amd.com#include <iostream> 4311308Santhony.gutierrez@amd.com#include <iterator> 4411308Santhony.gutierrez@amd.com#include <map> 4511308Santhony.gutierrez@amd.com#include <string> 4611308Santhony.gutierrez@amd.com 4711308Santhony.gutierrez@amd.com#include "gpu-compute/gpu_static_inst.hh" 4811308Santhony.gutierrez@amd.com 4911308Santhony.gutierrez@amd.comvoid 5011308Santhony.gutierrez@amd.comControlFlowInfo::assignImmediatePostDominators( 5111308Santhony.gutierrez@amd.com const std::vector<GPUStaticInst*>& instructions) 5211308Santhony.gutierrez@amd.com{ 5311308Santhony.gutierrez@amd.com ControlFlowInfo cfg(instructions); 5411308Santhony.gutierrez@amd.com cfg.findImmediatePostDominators(); 5511308Santhony.gutierrez@amd.com} 5611308Santhony.gutierrez@amd.com 5711308Santhony.gutierrez@amd.com 5811308Santhony.gutierrez@amd.comControlFlowInfo::ControlFlowInfo(const std::vector<GPUStaticInst*>& insts) : 5911308Santhony.gutierrez@amd.com instructions(insts) 6011308Santhony.gutierrez@amd.com{ 6111308Santhony.gutierrez@amd.com createBasicBlocks(); 6211308Santhony.gutierrez@amd.com connectBasicBlocks(); 6311308Santhony.gutierrez@amd.com} 6411308Santhony.gutierrez@amd.com 6511308Santhony.gutierrez@amd.comBasicBlock* 6611308Santhony.gutierrez@amd.comControlFlowInfo::basicBlock(int inst_num) const { 6711308Santhony.gutierrez@amd.com for (auto& block: basicBlocks) { 6811308Santhony.gutierrez@amd.com int first_block_id = block->firstInstruction->instNum(); 6911308Santhony.gutierrez@amd.com if (inst_num >= first_block_id && 7011308Santhony.gutierrez@amd.com inst_num < first_block_id + block->size) { 7111308Santhony.gutierrez@amd.com return block.get(); 7211308Santhony.gutierrez@amd.com } 7311308Santhony.gutierrez@amd.com } 7411308Santhony.gutierrez@amd.com return nullptr; 7511308Santhony.gutierrez@amd.com} 7611308Santhony.gutierrez@amd.com 7711308Santhony.gutierrez@amd.com 7811308Santhony.gutierrez@amd.comGPUStaticInst* 7911308Santhony.gutierrez@amd.comControlFlowInfo::lastInstruction(const BasicBlock* block) const 8011308Santhony.gutierrez@amd.com{ 8111308Santhony.gutierrez@amd.com if (block->isExit()) { 8211308Santhony.gutierrez@amd.com return nullptr; 8311308Santhony.gutierrez@amd.com } 8411308Santhony.gutierrez@amd.com 8511308Santhony.gutierrez@amd.com return instructions.at(block->firstInstruction->instNum() + 8611308Santhony.gutierrez@amd.com block->size - 1); 8711308Santhony.gutierrez@amd.com} 8811308Santhony.gutierrez@amd.com 8911308Santhony.gutierrez@amd.comBasicBlock* 9011308Santhony.gutierrez@amd.comControlFlowInfo::postDominator(const BasicBlock* block) const 9111308Santhony.gutierrez@amd.com{ 9211308Santhony.gutierrez@amd.com if (block->isExit()) { 9311308Santhony.gutierrez@amd.com return nullptr; 9411308Santhony.gutierrez@amd.com } 9511308Santhony.gutierrez@amd.com return basicBlock(lastInstruction(block)->ipdInstNum()); 9611308Santhony.gutierrez@amd.com} 9711308Santhony.gutierrez@amd.com 9811308Santhony.gutierrez@amd.comvoid 9911308Santhony.gutierrez@amd.comControlFlowInfo::createBasicBlocks() 10011308Santhony.gutierrez@amd.com{ 10111308Santhony.gutierrez@amd.com assert(!instructions.empty()); 10211308Santhony.gutierrez@amd.com std::set<int> leaders; 10311308Santhony.gutierrez@amd.com // first instruction is a leader 10411308Santhony.gutierrez@amd.com leaders.insert(0); 10511308Santhony.gutierrez@amd.com for (int i = 1; i < instructions.size(); i++) { 10611308Santhony.gutierrez@amd.com GPUStaticInst* instruction = instructions[i]; 10711308Santhony.gutierrez@amd.com if (instruction->o_type == Enums::OT_BRANCH) { 10811308Santhony.gutierrez@amd.com const int target_pc = instruction->getTargetPc(); 10911308Santhony.gutierrez@amd.com leaders.insert(target_pc); 11011308Santhony.gutierrez@amd.com leaders.insert(i + 1); 11111308Santhony.gutierrez@amd.com } 11211308Santhony.gutierrez@amd.com } 11311308Santhony.gutierrez@amd.com 11411308Santhony.gutierrez@amd.com size_t block_size = 0; 11511308Santhony.gutierrez@amd.com for (int i = 0; i < instructions.size(); i++) { 11611308Santhony.gutierrez@amd.com if (leaders.find(i) != leaders.end()) { 11711308Santhony.gutierrez@amd.com uint32_t id = basicBlocks.size(); 11811308Santhony.gutierrez@amd.com if (id > 0) { 11911308Santhony.gutierrez@amd.com basicBlocks.back()->size = block_size; 12011308Santhony.gutierrez@amd.com } 12111308Santhony.gutierrez@amd.com block_size = 0; 12211308Santhony.gutierrez@amd.com basicBlocks.emplace_back(new BasicBlock(id, instructions[i])); 12311308Santhony.gutierrez@amd.com } 12411308Santhony.gutierrez@amd.com block_size++; 12511308Santhony.gutierrez@amd.com } 12611308Santhony.gutierrez@amd.com basicBlocks.back()->size = block_size; 12711308Santhony.gutierrez@amd.com // exit basic block 12811308Santhony.gutierrez@amd.com basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr)); 12911308Santhony.gutierrez@amd.com} 13011308Santhony.gutierrez@amd.com 13111308Santhony.gutierrez@amd.comvoid 13211308Santhony.gutierrez@amd.comControlFlowInfo::connectBasicBlocks() 13311308Santhony.gutierrez@amd.com{ 13411308Santhony.gutierrez@amd.com BasicBlock* exit_bb = basicBlocks.back().get(); 13511308Santhony.gutierrez@amd.com for (auto& bb : basicBlocks) { 13611308Santhony.gutierrez@amd.com if (bb->isExit()) { 13711308Santhony.gutierrez@amd.com break; 13811308Santhony.gutierrez@amd.com } 13911308Santhony.gutierrez@amd.com GPUStaticInst* last = lastInstruction(bb.get()); 14011308Santhony.gutierrez@amd.com if (last->o_type == Enums::OT_RET) { 14111308Santhony.gutierrez@amd.com bb->successorIds.insert(exit_bb->id); 14211623Smichael.lebeane@amd.com continue; 14311308Santhony.gutierrez@amd.com } 14411308Santhony.gutierrez@amd.com if (last->o_type == Enums::OT_BRANCH) { 14511308Santhony.gutierrez@amd.com const uint32_t target_pc = last->getTargetPc(); 14611308Santhony.gutierrez@amd.com BasicBlock* target_bb = basicBlock(target_pc); 14711308Santhony.gutierrez@amd.com bb->successorIds.insert(target_bb->id); 14811308Santhony.gutierrez@amd.com } 14911308Santhony.gutierrez@amd.com 15011308Santhony.gutierrez@amd.com // Unconditional jump instructions have a unique successor 15111308Santhony.gutierrez@amd.com if (!last->unconditionalJumpInstruction()) { 15211308Santhony.gutierrez@amd.com BasicBlock* next_bb = basicBlock(last->instNum() + 1); 15311308Santhony.gutierrez@amd.com bb->successorIds.insert(next_bb->id); 15411308Santhony.gutierrez@amd.com } 15511308Santhony.gutierrez@amd.com } 15611308Santhony.gutierrez@amd.com} 15711308Santhony.gutierrez@amd.com 15811308Santhony.gutierrez@amd.com 15911308Santhony.gutierrez@amd.com// In-place set intersection 16011308Santhony.gutierrez@amd.comstatic void 16111308Santhony.gutierrez@amd.comintersect(std::set<uint32_t>& a, const std::set<uint32_t>& b) 16211308Santhony.gutierrez@amd.com{ 16311308Santhony.gutierrez@amd.com std::set<uint32_t>::iterator it = a.begin(); 16411308Santhony.gutierrez@amd.com while (it != a.end()) { 16511308Santhony.gutierrez@amd.com it = b.find(*it) != b.end() ? ++it : a.erase(it); 16611308Santhony.gutierrez@amd.com } 16711308Santhony.gutierrez@amd.com} 16811308Santhony.gutierrez@amd.com 16911308Santhony.gutierrez@amd.com 17011308Santhony.gutierrez@amd.comvoid 17111308Santhony.gutierrez@amd.comControlFlowInfo::findPostDominators() 17211308Santhony.gutierrez@amd.com{ 17311308Santhony.gutierrez@amd.com // the only postdominator of the exit block is itself 17411308Santhony.gutierrez@amd.com basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id); 17511308Santhony.gutierrez@amd.com //copy all basic blocks to all postdominator lists except for exit block 17611308Santhony.gutierrez@amd.com for (auto& block : basicBlocks) { 17711308Santhony.gutierrez@amd.com if (!block->isExit()) { 17811308Santhony.gutierrez@amd.com for (uint32_t i = 0; i < basicBlocks.size(); i++) { 17911308Santhony.gutierrez@amd.com block->postDominatorIds.insert(i); 18011308Santhony.gutierrez@amd.com } 18111308Santhony.gutierrez@amd.com } 18211308Santhony.gutierrez@amd.com } 18311308Santhony.gutierrez@amd.com 18411308Santhony.gutierrez@amd.com bool change = true; 18511308Santhony.gutierrez@amd.com while (change) { 18611308Santhony.gutierrez@amd.com change = false; 18711308Santhony.gutierrez@amd.com for (int h = basicBlocks.size() - 2; h >= 0; --h) { 18811308Santhony.gutierrez@amd.com size_t num_postdominators = 18911308Santhony.gutierrez@amd.com basicBlocks[h]->postDominatorIds.size(); 19011308Santhony.gutierrez@amd.com for (int s : basicBlocks[h]->successorIds) { 19111308Santhony.gutierrez@amd.com intersect(basicBlocks[h]->postDominatorIds, 19211308Santhony.gutierrez@amd.com basicBlocks[s]->postDominatorIds); 19311308Santhony.gutierrez@amd.com } 19411308Santhony.gutierrez@amd.com basicBlocks[h]->postDominatorIds.insert(h); 19511308Santhony.gutierrez@amd.com change |= (num_postdominators 19611308Santhony.gutierrez@amd.com != basicBlocks[h]->postDominatorIds.size()); 19711308Santhony.gutierrez@amd.com } 19811308Santhony.gutierrez@amd.com } 19911308Santhony.gutierrez@amd.com} 20011308Santhony.gutierrez@amd.com 20111308Santhony.gutierrez@amd.com 20211308Santhony.gutierrez@amd.com// In-place set difference 20311308Santhony.gutierrez@amd.comstatic void 20411308Santhony.gutierrez@amd.comsetDifference(std::set<uint32_t>&a, 20511308Santhony.gutierrez@amd.com const std::set<uint32_t>& b, uint32_t exception) 20611308Santhony.gutierrez@amd.com{ 20711308Santhony.gutierrez@amd.com for (uint32_t b_elem : b) { 20811308Santhony.gutierrez@amd.com if (b_elem != exception) { 20911308Santhony.gutierrez@amd.com a.erase(b_elem); 21011308Santhony.gutierrez@amd.com } 21111308Santhony.gutierrez@amd.com } 21211308Santhony.gutierrez@amd.com} 21311308Santhony.gutierrez@amd.com 21411308Santhony.gutierrez@amd.comvoid 21511308Santhony.gutierrez@amd.comControlFlowInfo::findImmediatePostDominators() 21611308Santhony.gutierrez@amd.com{ 21711308Santhony.gutierrez@amd.com assert(basicBlocks.size() > 1); // Entry and exit blocks must be present 21811308Santhony.gutierrez@amd.com 21911308Santhony.gutierrez@amd.com findPostDominators(); 22011308Santhony.gutierrez@amd.com 22111308Santhony.gutierrez@amd.com for (auto& basicBlock : basicBlocks) { 22211308Santhony.gutierrez@amd.com if (basicBlock->isExit()) { 22311308Santhony.gutierrez@amd.com continue; 22411308Santhony.gutierrez@amd.com } 22511308Santhony.gutierrez@amd.com std::set<uint32_t> candidates = basicBlock->postDominatorIds; 22611308Santhony.gutierrez@amd.com candidates.erase(basicBlock->id); 22711308Santhony.gutierrez@amd.com for (uint32_t postDominatorId : basicBlock->postDominatorIds) { 22811308Santhony.gutierrez@amd.com if (postDominatorId != basicBlock->id) { 22911308Santhony.gutierrez@amd.com setDifference(candidates, 23011308Santhony.gutierrez@amd.com basicBlocks[postDominatorId]->postDominatorIds, 23111308Santhony.gutierrez@amd.com postDominatorId); 23211308Santhony.gutierrez@amd.com } 23311308Santhony.gutierrez@amd.com } 23411308Santhony.gutierrez@amd.com assert(candidates.size() == 1); 23511308Santhony.gutierrez@amd.com GPUStaticInst* last_instruction = lastInstruction(basicBlock.get()); 23611308Santhony.gutierrez@amd.com BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get(); 23711308Santhony.gutierrez@amd.com if (!ipd_block->isExit()) { 23811308Santhony.gutierrez@amd.com GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction; 23911308Santhony.gutierrez@amd.com last_instruction->ipdInstNum(ipd_first_inst->instNum()); 24011308Santhony.gutierrez@amd.com } else { 24111308Santhony.gutierrez@amd.com last_instruction->ipdInstNum(last_instruction->instNum() + 1); 24211308Santhony.gutierrez@amd.com } 24311308Santhony.gutierrez@amd.com } 24411308Santhony.gutierrez@amd.com} 24511308Santhony.gutierrez@amd.com 24611308Santhony.gutierrez@amd.comvoid 24711308Santhony.gutierrez@amd.comControlFlowInfo::printPostDominators() const 24811308Santhony.gutierrez@amd.com{ 24911308Santhony.gutierrez@amd.com for (auto& block : basicBlocks) { 25011308Santhony.gutierrez@amd.com std::cout << "PD(" << block->id << ") = {"; 25111308Santhony.gutierrez@amd.com std::copy(block->postDominatorIds.begin(), 25211308Santhony.gutierrez@amd.com block->postDominatorIds.end(), 25311308Santhony.gutierrez@amd.com std::ostream_iterator<uint32_t>(std::cout, ", ")); 25411308Santhony.gutierrez@amd.com std::cout << "}" << std::endl; 25511308Santhony.gutierrez@amd.com } 25611308Santhony.gutierrez@amd.com} 25711308Santhony.gutierrez@amd.com 25811308Santhony.gutierrez@amd.comvoid 25911308Santhony.gutierrez@amd.comControlFlowInfo::printImmediatePostDominators() const 26011308Santhony.gutierrez@amd.com{ 26111308Santhony.gutierrez@amd.com for (const auto& block : basicBlocks) { 26211308Santhony.gutierrez@amd.com if (block->isExit()) { 26311308Santhony.gutierrez@amd.com continue; 26411308Santhony.gutierrez@amd.com } 26511308Santhony.gutierrez@amd.com std::cout << "IPD(" << block->id << ") = "; 26611308Santhony.gutierrez@amd.com std::cout << postDominator(block.get())->id << ", "; 26711308Santhony.gutierrez@amd.com } 26811308Santhony.gutierrez@amd.com std::cout << std::endl; 26911308Santhony.gutierrez@amd.com} 27011308Santhony.gutierrez@amd.comvoid 27111308Santhony.gutierrez@amd.comControlFlowInfo::printBasicBlocks() const 27211308Santhony.gutierrez@amd.com{ 27311308Santhony.gutierrez@amd.com for (GPUStaticInst* inst : instructions) { 27411308Santhony.gutierrez@amd.com int inst_num = inst->instNum(); 27511308Santhony.gutierrez@amd.com std::cout << inst_num << " [" << basicBlock(inst_num)->id 27611308Santhony.gutierrez@amd.com << "]: " << inst->disassemble(); 27711308Santhony.gutierrez@amd.com if (inst->o_type == Enums::OT_BRANCH) { 27811308Santhony.gutierrez@amd.com std::cout << ", PC = " << inst->getTargetPc(); 27911308Santhony.gutierrez@amd.com } 28011308Santhony.gutierrez@amd.com std::cout << std::endl; 28111308Santhony.gutierrez@amd.com } 28211308Santhony.gutierrez@amd.com} 28311308Santhony.gutierrez@amd.com 28411308Santhony.gutierrez@amd.comvoid 28511308Santhony.gutierrez@amd.comControlFlowInfo::printBasicBlockDot() const 28611308Santhony.gutierrez@amd.com{ 28711308Santhony.gutierrez@amd.com printf("digraph {\n"); 28811308Santhony.gutierrez@amd.com for (const auto& basic_block : basicBlocks) { 28911308Santhony.gutierrez@amd.com printf("\t"); 29011308Santhony.gutierrez@amd.com for (uint32_t successorId : basic_block->successorIds) { 29111308Santhony.gutierrez@amd.com printf("%d -> %d; ", basic_block->id, successorId); 29211308Santhony.gutierrez@amd.com } 29311308Santhony.gutierrez@amd.com printf("\n"); 29411308Santhony.gutierrez@amd.com } 29511308Santhony.gutierrez@amd.com printf("}\n"); 29611308Santhony.gutierrez@amd.com} 297