src/gpu-compute/kernel_cfg.cc - amd/gem5 - Git at Google

 /*
  * Copyright (c) 2012-2015 Advanced Micro Devices, Inc.
  * All rights reserved.
  *
  * For use for simulation and test purposes only
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  * 1. Redistributions of source code must retain the above copyright notice,
  * this list of conditions and the following disclaimer.
  *
  * 2. Redistributions in binary form must reproduce the above copyright notice,
  * this list of conditions and the following disclaimer in the documentation
  * and/or other materials provided with the distribution.
  *
  * 3. Neither the name of the copyright holder nor the names of its contributors
  * may be used to endorse or promote products derived from this software
  * without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
  * Author: Steve Reinhardt
  */

 #include "gpu-compute/kernel_cfg.hh"

 #include <algorithm>
 #include <cassert>
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <iterator>
 #include <map>
 #include <string>

 #include "gpu-compute/gpu_static_inst.hh"

 void
 ControlFlowInfo::assignImmediatePostDominators(
         const std::vector<GPUStaticInst*>& instructions)
 {
     ControlFlowInfo cfg(instructions);
     cfg.findImmediatePostDominators();
 }


 ControlFlowInfo::ControlFlowInfo(const std::vector<GPUStaticInst*>& insts) :
         instructions(insts)
 {
     createBasicBlocks();
     connectBasicBlocks();
 }

 BasicBlock*
 ControlFlowInfo::basicBlock(int inst_addr) const {
     for (auto& block: basicBlocks) {
        int first_block_addr = block->firstInstruction->instAddr();
        if (inst_addr >= first_block_addr && inst_addr <
            first_block_addr + block->size * sizeof(TheGpuISA::RawMachInst)) {
            return block.get();
        }
     }
     return nullptr;
 }


 GPUStaticInst*
 ControlFlowInfo::lastInstruction(const BasicBlock* block) const
 {
     if (block->isExit()) {
         return nullptr;
     }

     return instructions.at(block->firstInstruction->instNum() +
                            block->size - 1);
 }

 BasicBlock*
 ControlFlowInfo::postDominator(const BasicBlock* block) const
 {
     if (block->isExit()) {
         return nullptr;
     }
     return basicBlock(lastInstruction(block)->ipdInstNum());
 }

 void
 ControlFlowInfo::createBasicBlocks()
 {
     assert(!instructions.empty());
     std::set<int> leaders;
     // first instruction is a leader
     leaders.insert(0);
     for (const auto &instruction : instructions) {
         if (instruction->isBranch()) {
             const int target_pc = instruction->getTargetPc();
             leaders.insert(target_pc);
             leaders.insert(instruction->nextInstAddr());
         }
     }

     size_t block_size = 0;
     for (const auto &instruction : instructions) {
         if (leaders.find(instruction->instAddr()) != leaders.end()) {
             uint32_t id = basicBlocks.size();
             if (id > 0) {
                 basicBlocks.back()->size = block_size;
             }
             block_size = 0;
             basicBlocks.emplace_back(new BasicBlock(id, instruction));
         }
         block_size++;
     }
     basicBlocks.back()->size = block_size;
     // exit basic block
     basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr));
 }

 void
 ControlFlowInfo::connectBasicBlocks()
 {
     BasicBlock* exit_bb = basicBlocks.back().get();
     for (auto& bb : basicBlocks) {
         if (bb->isExit()) {
             break;
         }
         GPUStaticInst* last = lastInstruction(bb.get());
         if (last->isReturn()) {
             bb->successorIds.insert(exit_bb->id);
             continue;
         }
         if (last->isBranch()) {
             const uint32_t target_pc = last->getTargetPc();
             BasicBlock* target_bb = basicBlock(target_pc);
             bb->successorIds.insert(target_bb->id);
         }

         // Unconditional jump instructions have a unique successor
         if (!last->isUnconditionalJump()) {
             BasicBlock* next_bb = basicBlock(last->nextInstAddr());
             bb->successorIds.insert(next_bb->id);
         }
     }
 }


 // In-place set intersection
 static void
 intersect(std::set<uint32_t>& a, const std::set<uint32_t>& b)
 {
     std::set<uint32_t>::iterator it = a.begin();
     while (it != a.end()) {
         it = b.find(*it) != b.end() ? ++it : a.erase(it);
     }
 }


 void
 ControlFlowInfo::findPostDominators()
 {
     // the only postdominator of the exit block is itself
     basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id);
     //copy all basic blocks to all postdominator lists except for exit block
     for (auto& block : basicBlocks) {
         if (!block->isExit()) {
             for (uint32_t i = 0; i < basicBlocks.size(); i++) {
                 block->postDominatorIds.insert(i);
             }
         }
     }

     bool change = true;
     while (change) {
         change = false;
         for (int h = basicBlocks.size() - 2; h >= 0; --h) {
             size_t num_postdominators =
                     basicBlocks[h]->postDominatorIds.size();
             for (int s : basicBlocks[h]->successorIds) {
                 intersect(basicBlocks[h]->postDominatorIds,
                           basicBlocks[s]->postDominatorIds);
             }
             basicBlocks[h]->postDominatorIds.insert(h);
             change |= (num_postdominators
                     != basicBlocks[h]->postDominatorIds.size());
         }
     }
 }


 // In-place set difference
 static void
 setDifference(std::set<uint32_t>&a,
            const std::set<uint32_t>& b, uint32_t exception)
 {
     for (uint32_t b_elem : b) {
         if (b_elem != exception) {
             a.erase(b_elem);
         }
     }
 }

 void
 ControlFlowInfo::findImmediatePostDominators()
 {
     assert(basicBlocks.size() > 1); // Entry and exit blocks must be present

     findPostDominators();

     for (auto& basicBlock : basicBlocks) {
         if (basicBlock->isExit()) {
             continue;
         }
         std::set<uint32_t> candidates = basicBlock->postDominatorIds;
         candidates.erase(basicBlock->id);
         for (uint32_t postDominatorId : basicBlock->postDominatorIds) {
             if (postDominatorId != basicBlock->id) {
                 setDifference(candidates,
                            basicBlocks[postDominatorId]->postDominatorIds,
                            postDominatorId);
             }
         }
         assert(candidates.size() == 1);
         GPUStaticInst* last_instruction = lastInstruction(basicBlock.get());
         BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get();
         if (!ipd_block->isExit()) {
             GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction;
             last_instruction->ipdInstNum(ipd_first_inst->instAddr());
         } else {
             last_instruction->ipdInstNum(last_instruction->nextInstAddr());
         }
     }
 }

 void
 ControlFlowInfo::printPostDominators() const
 {
     for (auto& block : basicBlocks) {
         std::cout << "PD(" << block->id << ") = {";
         std::copy(block->postDominatorIds.begin(),
                   block->postDominatorIds.end(),
                   std::ostream_iterator<uint32_t>(std::cout, ", "));
         std::cout << "}" << std::endl;
     }
 }

 void
 ControlFlowInfo::printImmediatePostDominators() const
 {
     for (const auto& block : basicBlocks) {
         if (block->isExit()) {
             continue;
         }
         std::cout << "IPD(" << block->id << ") = ";
         std::cout << postDominator(block.get())->id << ", ";
     }
     std::cout << std::endl;
 }
 void
 ControlFlowInfo::printBasicBlocks() const
 {
     for (GPUStaticInst* inst : instructions) {
         int inst_addr = inst->instAddr();
         std::cout << inst_addr << " [" << basicBlock(inst_addr)->id
                 << "]: " << inst->disassemble();
         if (inst->isBranch()) {
             std::cout << ", PC = " << inst->getTargetPc();
         }
         std::cout << std::endl;
     }
 }

 void
 ControlFlowInfo::printBasicBlockDot() const
 {
     printf("digraph {\n");
     for (const auto& basic_block : basicBlocks) {
         printf("\t");
         for (uint32_t successorId : basic_block->successorIds) {
             printf("%d -> %d; ", basic_block->id, successorId);
         }
         printf("\n");
     }
     printf("}\n");
 }
	/*
	* Copyright (c) 2012-2015 Advanced Micro Devices, Inc.
	* All rights reserved.
	*
	* For use for simulation and test purposes only
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are met:
	*
	* 1. Redistributions of source code must retain the above copyright notice,
	* this list of conditions and the following disclaimer.
	*
	* 2. Redistributions in binary form must reproduce the above copyright notice,
	* this list of conditions and the following disclaimer in the documentation
	* and/or other materials provided with the distribution.
	*
	* 3. Neither the name of the copyright holder nor the names of its contributors
	* may be used to endorse or promote products derived from this software
	* without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	* POSSIBILITY OF SUCH DAMAGE.
	*
	* Author: Steve Reinhardt
	*/

	#include "gpu-compute/kernel_cfg.hh"

	#include <algorithm>
	#include <cassert>
	#include <cstdio>
	#include <cstring>
	#include <iostream>
	#include <iterator>
	#include <map>
	#include <string>

	#include "gpu-compute/gpu_static_inst.hh"

	void
	ControlFlowInfo::assignImmediatePostDominators(
	const std::vector<GPUStaticInst*>& instructions)
	{
	ControlFlowInfo cfg(instructions);
	cfg.findImmediatePostDominators();
	}


	ControlFlowInfo::ControlFlowInfo(const std::vector<GPUStaticInst*>& insts) :
	instructions(insts)
	{
	createBasicBlocks();
	connectBasicBlocks();
	}

	BasicBlock*
	ControlFlowInfo::basicBlock(int inst_addr) const {
	for (auto& block: basicBlocks) {
	int first_block_addr = block->firstInstruction->instAddr();
	if (inst_addr >= first_block_addr && inst_addr <
	first_block_addr + block->size * sizeof(TheGpuISA::RawMachInst)) {
	return block.get();
	}
	}
	return nullptr;
	}


	GPUStaticInst*
	ControlFlowInfo::lastInstruction(const BasicBlock* block) const
	{
	if (block->isExit()) {
	return nullptr;
	}

	return instructions.at(block->firstInstruction->instNum() +
	block->size - 1);
	}

	BasicBlock*
	ControlFlowInfo::postDominator(const BasicBlock* block) const
	{
	if (block->isExit()) {
	return nullptr;
	}
	return basicBlock(lastInstruction(block)->ipdInstNum());
	}

	void
	ControlFlowInfo::createBasicBlocks()
	{
	assert(!instructions.empty());
	std::set<int> leaders;
	// first instruction is a leader
	leaders.insert(0);
	for (const auto &instruction : instructions) {
	if (instruction->isBranch()) {
	const int target_pc = instruction->getTargetPc();
	leaders.insert(target_pc);
	leaders.insert(instruction->nextInstAddr());
	}
	}

	size_t block_size = 0;
	for (const auto &instruction : instructions) {
	if (leaders.find(instruction->instAddr()) != leaders.end()) {
	uint32_t id = basicBlocks.size();
	if (id > 0) {
	basicBlocks.back()->size = block_size;
	}
	block_size = 0;
	basicBlocks.emplace_back(new BasicBlock(id, instruction));
	}
	block_size++;
	}
	basicBlocks.back()->size = block_size;
	// exit basic block
	basicBlocks.emplace_back(new BasicBlock(basicBlocks.size(), nullptr));
	}

	void
	ControlFlowInfo::connectBasicBlocks()
	{
	BasicBlock* exit_bb = basicBlocks.back().get();
	for (auto& bb : basicBlocks) {
	if (bb->isExit()) {
	break;
	}
	GPUStaticInst* last = lastInstruction(bb.get());
	if (last->isReturn()) {
	bb->successorIds.insert(exit_bb->id);
	continue;
	}
	if (last->isBranch()) {
	const uint32_t target_pc = last->getTargetPc();
	BasicBlock* target_bb = basicBlock(target_pc);
	bb->successorIds.insert(target_bb->id);
	}

	// Unconditional jump instructions have a unique successor
	if (!last->isUnconditionalJump()) {
	BasicBlock* next_bb = basicBlock(last->nextInstAddr());
	bb->successorIds.insert(next_bb->id);
	}
	}
	}


	// In-place set intersection
	static void
	intersect(std::set<uint32_t>& a, const std::set<uint32_t>& b)
	{
	std::set<uint32_t>::iterator it = a.begin();
	while (it != a.end()) {
	it = b.find(*it) != b.end() ? ++it : a.erase(it);
	}
	}


	void
	ControlFlowInfo::findPostDominators()
	{
	// the only postdominator of the exit block is itself
	basicBlocks.back()->postDominatorIds.insert(basicBlocks.back()->id);
	//copy all basic blocks to all postdominator lists except for exit block
	for (auto& block : basicBlocks) {
	if (!block->isExit()) {
	for (uint32_t i = 0; i < basicBlocks.size(); i++) {
	block->postDominatorIds.insert(i);
	}
	}
	}

	bool change = true;
	while (change) {
	change = false;
	for (int h = basicBlocks.size() - 2; h >= 0; --h) {
	size_t num_postdominators =
	basicBlocks[h]->postDominatorIds.size();
	for (int s : basicBlocks[h]->successorIds) {
	intersect(basicBlocks[h]->postDominatorIds,
	basicBlocks[s]->postDominatorIds);
	}
	basicBlocks[h]->postDominatorIds.insert(h);
	change \|= (num_postdominators
	!= basicBlocks[h]->postDominatorIds.size());
	}
	}
	}


	// In-place set difference
	static void
	setDifference(std::set<uint32_t>&a,
	const std::set<uint32_t>& b, uint32_t exception)
	{
	for (uint32_t b_elem : b) {
	if (b_elem != exception) {
	a.erase(b_elem);
	}
	}
	}

	void
	ControlFlowInfo::findImmediatePostDominators()
	{
	assert(basicBlocks.size() > 1); // Entry and exit blocks must be present

	findPostDominators();

	for (auto& basicBlock : basicBlocks) {
	if (basicBlock->isExit()) {
	continue;
	}
	std::set<uint32_t> candidates = basicBlock->postDominatorIds;
	candidates.erase(basicBlock->id);
	for (uint32_t postDominatorId : basicBlock->postDominatorIds) {
	if (postDominatorId != basicBlock->id) {
	setDifference(candidates,
	basicBlocks[postDominatorId]->postDominatorIds,
	postDominatorId);
	}
	}
	assert(candidates.size() == 1);
	GPUStaticInst* last_instruction = lastInstruction(basicBlock.get());
	BasicBlock* ipd_block = basicBlocks[*(candidates.begin())].get();
	if (!ipd_block->isExit()) {
	GPUStaticInst* ipd_first_inst = ipd_block->firstInstruction;
	last_instruction->ipdInstNum(ipd_first_inst->instAddr());
	} else {
	last_instruction->ipdInstNum(last_instruction->nextInstAddr());
	}
	}
	}

	void
	ControlFlowInfo::printPostDominators() const
	{
	for (auto& block : basicBlocks) {
	std::cout << "PD(" << block->id << ") = {";
	std::copy(block->postDominatorIds.begin(),
	block->postDominatorIds.end(),
	std::ostream_iterator<uint32_t>(std::cout, ", "));
	std::cout << "}" << std::endl;
	}
	}

	void
	ControlFlowInfo::printImmediatePostDominators() const
	{
	for (const auto& block : basicBlocks) {
	if (block->isExit()) {
	continue;
	}
	std::cout << "IPD(" << block->id << ") = ";
	std::cout << postDominator(block.get())->id << ", ";
	}
	std::cout << std::endl;
	}
	void
	ControlFlowInfo::printBasicBlocks() const
	{
	for (GPUStaticInst* inst : instructions) {
	int inst_addr = inst->instAddr();
	std::cout << inst_addr << " [" << basicBlock(inst_addr)->id
	<< "]: " << inst->disassemble();
	if (inst->isBranch()) {
	std::cout << ", PC = " << inst->getTargetPc();
	}
	std::cout << std::endl;
	}
	}

	void
	ControlFlowInfo::printBasicBlockDot() const
	{
	printf("digraph {\n");
	for (const auto& basic_block : basicBlocks) {
	printf("\t");
	for (uint32_t successorId : basic_block->successorIds) {
	printf("%d -> %d; ", basic_block->id, successorId);
	}
	printf("\n");
	}
	printf("}\n");
	}