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