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* 6611697Santhony.gutierrez@amd.comControlFlowInfo::basicBlock(int inst_addr) const { 6711308Santhony.gutierrez@amd.com for (auto& block: basicBlocks) { 6811697Santhony.gutierrez@amd.com int first_block_addr = block->firstInstruction->instAddr(); 6911697Santhony.gutierrez@amd.com if (inst_addr >= first_block_addr && inst_addr < 7011697Santhony.gutierrez@amd.com first_block_addr + block->size * sizeof(TheGpuISA::RawMachInst)) { 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); 10511697Santhony.gutierrez@amd.com for (const auto &instruction : instructions) { 10611692Santhony.gutierrez@amd.com if (instruction->isBranch()) { 10711308Santhony.gutierrez@amd.com const int target_pc = instruction->getTargetPc(); 10811308Santhony.gutierrez@amd.com leaders.insert(target_pc); 10911697Santhony.gutierrez@amd.com leaders.insert(instruction->nextInstAddr()); 11011308Santhony.gutierrez@amd.com } 11111308Santhony.gutierrez@amd.com } 11211308Santhony.gutierrez@amd.com 11311308Santhony.gutierrez@amd.com size_t block_size = 0; 11411697Santhony.gutierrez@amd.com for (const auto &instruction : instructions) { 11511697Santhony.gutierrez@amd.com if (leaders.find(instruction->instAddr()) != leaders.end()) { 11611308Santhony.gutierrez@amd.com uint32_t id = basicBlocks.size(); 11711308Santhony.gutierrez@amd.com if (id > 0) { 11811308Santhony.gutierrez@amd.com basicBlocks.back()->size = block_size; 11911308Santhony.gutierrez@amd.com } 12011308Santhony.gutierrez@amd.com block_size = 0; 12111697Santhony.gutierrez@amd.com basicBlocks.emplace_back(new BasicBlock(id, instruction)); 12211308Santhony.gutierrez@amd.com } 12311308Santhony.gutierrez@amd.com block_size++; 12411308Santhony.gutierrez@amd.com } 12511308Santhony.gutierrez@amd.com basicBlocks.back()->size = block_size; 12611308Santhony.gutierrez@amd.com // exit basic block 12711308Santhony.gutierrez@amd.com basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr)); 12811308Santhony.gutierrez@amd.com} 12911308Santhony.gutierrez@amd.com 13011308Santhony.gutierrez@amd.comvoid 13111308Santhony.gutierrez@amd.comControlFlowInfo::connectBasicBlocks() 13211308Santhony.gutierrez@amd.com{ 13311308Santhony.gutierrez@amd.com BasicBlock* exit_bb = basicBlocks.back().get(); 13411308Santhony.gutierrez@amd.com for (auto& bb : basicBlocks) { 13511308Santhony.gutierrez@amd.com if (bb->isExit()) { 13611308Santhony.gutierrez@amd.com break; 13711308Santhony.gutierrez@amd.com } 13811308Santhony.gutierrez@amd.com GPUStaticInst* last = lastInstruction(bb.get()); 13911692Santhony.gutierrez@amd.com if (last->isReturn()) { 14011308Santhony.gutierrez@amd.com bb->successorIds.insert(exit_bb->id); 14111623Smichael.lebeane@amd.com continue; 14211308Santhony.gutierrez@amd.com } 14311692Santhony.gutierrez@amd.com if (last->isBranch()) { 14411308Santhony.gutierrez@amd.com const uint32_t target_pc = last->getTargetPc(); 14511308Santhony.gutierrez@amd.com BasicBlock* target_bb = basicBlock(target_pc); 14611308Santhony.gutierrez@amd.com bb->successorIds.insert(target_bb->id); 14711308Santhony.gutierrez@amd.com } 14811308Santhony.gutierrez@amd.com 14911308Santhony.gutierrez@amd.com // Unconditional jump instructions have a unique successor 15011692Santhony.gutierrez@amd.com if (!last->isUnconditionalJump()) { 15111697Santhony.gutierrez@amd.com BasicBlock* next_bb = basicBlock(last->nextInstAddr()); 15211308Santhony.gutierrez@amd.com bb->successorIds.insert(next_bb->id); 15311308Santhony.gutierrez@amd.com } 15411308Santhony.gutierrez@amd.com } 15511308Santhony.gutierrez@amd.com} 15611308Santhony.gutierrez@amd.com 15711308Santhony.gutierrez@amd.com 15811308Santhony.gutierrez@amd.com// In-place set intersection 15911308Santhony.gutierrez@amd.comstatic void 16011308Santhony.gutierrez@amd.comintersect(std::set<uint32_t>& a, const std::set<uint32_t>& b) 16111308Santhony.gutierrez@amd.com{ 16211308Santhony.gutierrez@amd.com std::set<uint32_t>::iterator it = a.begin(); 16311308Santhony.gutierrez@amd.com while (it != a.end()) { 16411308Santhony.gutierrez@amd.com it = b.find(*it) != b.end() ? ++it : a.erase(it); 16511308Santhony.gutierrez@amd.com } 16611308Santhony.gutierrez@amd.com} 16711308Santhony.gutierrez@amd.com 16811308Santhony.gutierrez@amd.com 16911308Santhony.gutierrez@amd.comvoid 17011308Santhony.gutierrez@amd.comControlFlowInfo::findPostDominators() 17111308Santhony.gutierrez@amd.com{ 17211308Santhony.gutierrez@amd.com // the only postdominator of the exit block is itself 17311308Santhony.gutierrez@amd.com basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id); 17411308Santhony.gutierrez@amd.com //copy all basic blocks to all postdominator lists except for exit block 17511308Santhony.gutierrez@amd.com for (auto& block : basicBlocks) { 17611308Santhony.gutierrez@amd.com if (!block->isExit()) { 17711308Santhony.gutierrez@amd.com for (uint32_t i = 0; i < basicBlocks.size(); i++) { 17811308Santhony.gutierrez@amd.com block->postDominatorIds.insert(i); 17911308Santhony.gutierrez@amd.com } 18011308Santhony.gutierrez@amd.com } 18111308Santhony.gutierrez@amd.com } 18211308Santhony.gutierrez@amd.com 18311308Santhony.gutierrez@amd.com bool change = true; 18411308Santhony.gutierrez@amd.com while (change) { 18511308Santhony.gutierrez@amd.com change = false; 18611308Santhony.gutierrez@amd.com for (int h = basicBlocks.size() - 2; h >= 0; --h) { 18711308Santhony.gutierrez@amd.com size_t num_postdominators = 18811308Santhony.gutierrez@amd.com basicBlocks[h]->postDominatorIds.size(); 18911308Santhony.gutierrez@amd.com for (int s : basicBlocks[h]->successorIds) { 19011308Santhony.gutierrez@amd.com intersect(basicBlocks[h]->postDominatorIds, 19111308Santhony.gutierrez@amd.com basicBlocks[s]->postDominatorIds); 19211308Santhony.gutierrez@amd.com } 19311308Santhony.gutierrez@amd.com basicBlocks[h]->postDominatorIds.insert(h); 19411308Santhony.gutierrez@amd.com change |= (num_postdominators 19511308Santhony.gutierrez@amd.com != basicBlocks[h]->postDominatorIds.size()); 19611308Santhony.gutierrez@amd.com } 19711308Santhony.gutierrez@amd.com } 19811308Santhony.gutierrez@amd.com} 19911308Santhony.gutierrez@amd.com 20011308Santhony.gutierrez@amd.com 20111308Santhony.gutierrez@amd.com// In-place set difference 20211308Santhony.gutierrez@amd.comstatic void 20311308Santhony.gutierrez@amd.comsetDifference(std::set<uint32_t>&a, 20411308Santhony.gutierrez@amd.com const std::set<uint32_t>& b, uint32_t exception) 20511308Santhony.gutierrez@amd.com{ 20611308Santhony.gutierrez@amd.com for (uint32_t b_elem : b) { 20711308Santhony.gutierrez@amd.com if (b_elem != exception) { 20811308Santhony.gutierrez@amd.com a.erase(b_elem); 20911308Santhony.gutierrez@amd.com } 21011308Santhony.gutierrez@amd.com } 21111308Santhony.gutierrez@amd.com} 21211308Santhony.gutierrez@amd.com 21311308Santhony.gutierrez@amd.comvoid 21411308Santhony.gutierrez@amd.comControlFlowInfo::findImmediatePostDominators() 21511308Santhony.gutierrez@amd.com{ 21611308Santhony.gutierrez@amd.com assert(basicBlocks.size() > 1); // Entry and exit blocks must be present 21711308Santhony.gutierrez@amd.com 21811308Santhony.gutierrez@amd.com findPostDominators(); 21911308Santhony.gutierrez@amd.com 22011308Santhony.gutierrez@amd.com for (auto& basicBlock : basicBlocks) { 22111308Santhony.gutierrez@amd.com if (basicBlock->isExit()) { 22211308Santhony.gutierrez@amd.com continue; 22311308Santhony.gutierrez@amd.com } 22411308Santhony.gutierrez@amd.com std::set<uint32_t> candidates = basicBlock->postDominatorIds; 22511308Santhony.gutierrez@amd.com candidates.erase(basicBlock->id); 22611308Santhony.gutierrez@amd.com for (uint32_t postDominatorId : basicBlock->postDominatorIds) { 22711308Santhony.gutierrez@amd.com if (postDominatorId != basicBlock->id) { 22811308Santhony.gutierrez@amd.com setDifference(candidates, 22911308Santhony.gutierrez@amd.com basicBlocks[postDominatorId]->postDominatorIds, 23011308Santhony.gutierrez@amd.com postDominatorId); 23111308Santhony.gutierrez@amd.com } 23211308Santhony.gutierrez@amd.com } 23311308Santhony.gutierrez@amd.com assert(candidates.size() == 1); 23411308Santhony.gutierrez@amd.com GPUStaticInst* last_instruction = lastInstruction(basicBlock.get()); 23511308Santhony.gutierrez@amd.com BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get(); 23611308Santhony.gutierrez@amd.com if (!ipd_block->isExit()) { 23711308Santhony.gutierrez@amd.com GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction; 23811697Santhony.gutierrez@amd.com last_instruction->ipdInstNum(ipd_first_inst->instAddr()); 23911308Santhony.gutierrez@amd.com } else { 24011697Santhony.gutierrez@amd.com last_instruction->ipdInstNum(last_instruction->nextInstAddr()); 24111308Santhony.gutierrez@amd.com } 24211308Santhony.gutierrez@amd.com } 24311308Santhony.gutierrez@amd.com} 24411308Santhony.gutierrez@amd.com 24511308Santhony.gutierrez@amd.comvoid 24611308Santhony.gutierrez@amd.comControlFlowInfo::printPostDominators() const 24711308Santhony.gutierrez@amd.com{ 24811308Santhony.gutierrez@amd.com for (auto& block : basicBlocks) { 24911308Santhony.gutierrez@amd.com std::cout << "PD(" << block->id << ") = {"; 25011308Santhony.gutierrez@amd.com std::copy(block->postDominatorIds.begin(), 25111308Santhony.gutierrez@amd.com block->postDominatorIds.end(), 25211308Santhony.gutierrez@amd.com std::ostream_iterator<uint32_t>(std::cout, ", ")); 25311308Santhony.gutierrez@amd.com std::cout << "}" << std::endl; 25411308Santhony.gutierrez@amd.com } 25511308Santhony.gutierrez@amd.com} 25611308Santhony.gutierrez@amd.com 25711308Santhony.gutierrez@amd.comvoid 25811308Santhony.gutierrez@amd.comControlFlowInfo::printImmediatePostDominators() const 25911308Santhony.gutierrez@amd.com{ 26011308Santhony.gutierrez@amd.com for (const auto& block : basicBlocks) { 26111308Santhony.gutierrez@amd.com if (block->isExit()) { 26211308Santhony.gutierrez@amd.com continue; 26311308Santhony.gutierrez@amd.com } 26411308Santhony.gutierrez@amd.com std::cout << "IPD(" << block->id << ") = "; 26511308Santhony.gutierrez@amd.com std::cout << postDominator(block.get())->id << ", "; 26611308Santhony.gutierrez@amd.com } 26711308Santhony.gutierrez@amd.com std::cout << std::endl; 26811308Santhony.gutierrez@amd.com} 26911308Santhony.gutierrez@amd.comvoid 27011308Santhony.gutierrez@amd.comControlFlowInfo::printBasicBlocks() const 27111308Santhony.gutierrez@amd.com{ 27211308Santhony.gutierrez@amd.com for (GPUStaticInst* inst : instructions) { 27311697Santhony.gutierrez@amd.com int inst_addr = inst->instAddr(); 27411697Santhony.gutierrez@amd.com std::cout << inst_addr << " [" << basicBlock(inst_addr)->id 27511308Santhony.gutierrez@amd.com << "]: " << inst->disassemble(); 27611692Santhony.gutierrez@amd.com if (inst->isBranch()) { 27711308Santhony.gutierrez@amd.com std::cout << ", PC = " << inst->getTargetPc(); 27811308Santhony.gutierrez@amd.com } 27911308Santhony.gutierrez@amd.com std::cout << std::endl; 28011308Santhony.gutierrez@amd.com } 28111308Santhony.gutierrez@amd.com} 28211308Santhony.gutierrez@amd.com 28311308Santhony.gutierrez@amd.comvoid 28411308Santhony.gutierrez@amd.comControlFlowInfo::printBasicBlockDot() const 28511308Santhony.gutierrez@amd.com{ 28611308Santhony.gutierrez@amd.com printf("digraph {\n"); 28711308Santhony.gutierrez@amd.com for (const auto& basic_block : basicBlocks) { 28811308Santhony.gutierrez@amd.com printf("\t"); 28911308Santhony.gutierrez@amd.com for (uint32_t successorId : basic_block->successorIds) { 29011308Santhony.gutierrez@amd.com printf("%d -> %d; ", basic_block->id, successorId); 29111308Santhony.gutierrez@amd.com } 29211308Santhony.gutierrez@amd.com printf("\n"); 29311308Santhony.gutierrez@amd.com } 29411308Santhony.gutierrez@amd.com printf("}\n"); 29511308Santhony.gutierrez@amd.com} 296