| 1 |
/*========================== begin_copyright_notice ============================ |
| 2 |
|
| 3 |
Copyright (C) 2017-2021 Intel Corporation |
| 4 |
|
| 5 |
SPDX-License-Identifier: MIT |
| 6 |
|
| 7 |
============================= end_copyright_notice ===========================*/ |
| 8 |
|
| 9 |
// #define DEBUG_BLOCKS |
| 10 |
#define TRACE_BLOCK(...) DebugTrace(iga::format(__VA_ARGS__).c_str()) |
| 11 |
|
| 12 |
#include "Block.hpp" |
| 13 |
#include "../ErrorHandler.hpp" |
| 14 |
#include "../Frontend/IRToString.hpp" |
| 15 |
#include "../asserts.hpp" |
| 16 |
#include "Instruction.hpp" |
| 17 |
|
| 18 |
#include <set> |
| 19 |
#include <sstream> |
| 20 |
#include <vector> |
| 21 |
|
| 22 |
using namespace iga; |
| 23 |
|
| 24 |
struct BlockInference { |
| 25 |
MemManager *allocator; |
| 26 |
|
| 27 |
std::map<int32_t, Block *> &blockStarts; |
| 28 |
std::set<int32_t> instStarts; |
| 29 |
|
| 30 |
struct ResolvedTarget { |
| 31 |
Loc loc; // instruction location |
| 32 |
int srcIx; // source index |
| 33 |
int32_t targetPc; |
| 34 |
ResolvedTarget(Loc _loc, int _srcIx, int32_t _targetPc) |
| 35 |
: loc(_loc), srcIx(_srcIx), targetPc(_targetPc) {} |
| 36 |
}; |
| 37 |
std::vector<ResolvedTarget> resolved; |
| 38 |
|
| 39 |
BlockInference(std::map<int32_t, Block *> &bs, MemManager *a) |
| 40 |
: allocator(a), blockStarts(bs) {} |
| 41 |
|
| 42 |
Block *getBlock(int32_t pc) { |
| 43 |
auto itr = blockStarts.find(pc); |
| 44 |
if (itr == blockStarts.end()) { |
| 45 |
Block *blk = new (allocator) Block(pc); |
| 46 |
blockStarts[pc] = blk; |
| 47 |
return blk; |
| 48 |
} else { |
| 49 |
return itr->second; |
| 50 |
} |
| 51 |
} |
| 52 |
|
| 53 |
void replaceNumericLabel(ErrorHandler &errHandler, size_t binaryLength, |
| 54 |
int32_t pc, int32_t instLen, Instruction *inst, |
| 55 |
int srcIx) { |
| 56 |
Operand &src = inst->getSource(srcIx); |
| 57 |
if (src.getKind() == Operand::Kind::LABEL) { |
| 58 |
int32_t targetPc = src.getImmediateValue().s32; |
| 59 |
if (!inst->getOpSpec().isJipAbsolute()) |
| 60 |
targetPc += pc; |
| 61 |
if (targetPc < 0 || targetPc > (int32_t)binaryLength) { |
| 62 |
std::stringstream ss; |
| 63 |
ss << "src" << srcIx << " targets"; |
| 64 |
if (targetPc < 0) { |
| 65 |
ss << " before kernel start"; |
| 66 |
} else { |
| 67 |
ss << " after kernel end"; |
| 68 |
} |
| 69 |
ss << ": PC " << targetPc; |
| 70 |
|
| 71 |
Loc loc(0, 0, (uint32_t)pc, (uint32_t)instLen); |
| 72 |
errHandler.reportError(loc, ss.str()); |
| 73 |
} else { |
| 74 |
resolved.emplace_back(inst->getLoc(), srcIx, targetPc); |
| 75 |
} |
| 76 |
src.setLabelSource(getBlock(targetPc), src.getType()); |
| 77 |
} |
| 78 |
} |
| 79 |
|
| 80 |
void run(ErrorHandler &errHandler, int32_t binaryLength, InstList &insts) { |
| 81 |
// define start block to ensure at least one block exists |
| 82 |
(void)getBlock(0); |
| 83 |
|
| 84 |
int32_t pc = 0; |
| 85 |
for (Instruction *inst : insts) { |
| 86 |
instStarts.insert(inst->getPC()); |
| 87 |
int32_t instLen = inst->hasInstOpt(InstOpt::COMPACTED) ? 8 : 16; |
| 88 |
if (inst->getOpSpec().isBranching() || inst->isMovWithLabel()) { |
| 89 |
// all branching instructions can redirect to next instruction |
| 90 |
// start a new block after this one |
| 91 |
(void)getBlock(pc + instLen); |
| 92 |
// replace src0 |
| 93 |
replaceNumericLabel(errHandler, binaryLength, pc, instLen, inst, 0); |
| 94 |
// replace src1 |
| 95 |
if (inst->getSourceCount() > 1) { |
| 96 |
replaceNumericLabel(errHandler, binaryLength, pc, instLen, inst, 1); |
| 97 |
} |
| 98 |
} else if (inst->hasInstOpt(InstOpt::EOT)) { |
| 99 |
// also treat EOT as the end of a BB |
| 100 |
(void)getBlock(pc + instLen); |
| 101 |
} |
| 102 |
pc += instLen; |
| 103 |
} |
| 104 |
|
| 105 |
// for each block, we need to append the following instructions |
| 106 |
pc = 0; |
| 107 |
auto bitr = blockStarts.begin(); |
| 108 |
Block *currBlock = bitr->second; |
| 109 |
bitr++; |
| 110 |
|
| 111 |
for (Instruction *inst : insts) { |
| 112 |
int32_t instLen = inst->hasInstOpt(InstOpt::COMPACTED) ? 8 : 16; |
| 113 |
if (bitr != blockStarts.end() && pc >= bitr->first) { |
| 114 |
currBlock = bitr->second; |
| 115 |
bitr++; |
| 116 |
} |
| 117 |
|
| 118 |
currBlock->appendInstruction(inst); |
| 119 |
|
| 120 |
pc += instLen; |
| 121 |
} |
| 122 |
|
| 123 |
for (const ResolvedTarget &rt : resolved) { |
| 124 |
if (rt.targetPc != binaryLength && // EOF is also a valid target |
| 125 |
instStarts.find(rt.targetPc) == instStarts.end()) { |
| 126 |
std::stringstream ss; |
| 127 |
ss << "src" << rt.srcIx << |
| 128 |
// it must've been a numeric label because symbolic labels |
| 129 |
// couldn't cause this |
| 130 |
": numeric label targets the middle of an instruction"; |
| 131 |
errHandler.reportError(rt.loc, ss.str()); |
| 132 |
} |
| 133 |
} |
| 134 |
} |
| 135 |
}; // class BlockInference |
| 136 |
|
| 137 |
#ifdef DEBUG_BLOCKS |
| 138 |
static void traceOperand(const Operand &op) { |
| 139 |
TRACE_BLOCK(" "); |
| 140 |
switch (op.getKind()) { |
| 141 |
case Operand::Kind::DIRECT: |
| 142 |
TRACE_BLOCK(ToSyntax(op.getDirRegName()), (int)op.getDirRegRef().regNum, |
| 143 |
".", (int)op.getDirRegRef().subRegNum); |
| 144 |
break; |
| 145 |
case Operand::Kind::INDIRECT: |
| 146 |
TRACE_BLOCK("IND"); |
| 147 |
break; |
| 148 |
case Operand::Kind::IMMEDIATE: |
| 149 |
TRACE_BLOCK("0x", hex(op.getImmediateValue().u64)); |
| 150 |
if (op.getType() == Type::F) { |
| 151 |
TRACE_BLOCK("(=", op.getImmediateValue().f32, ")"); |
| 152 |
} else if (op.getType() == Type::DF) { |
| 153 |
TRACE_BLOCK("(=", op.getImmediateValue().f64, ")"); |
| 154 |
} |
| 155 |
break; |
| 156 |
case Operand::Kind::LABEL: |
| 157 |
TRACE_BLOCK("@", op.getTargetBlock(), ":", op.getImmediateValue().s32); |
| 158 |
break; |
| 159 |
case Operand::Kind::INVALID: |
| 160 |
TRACE_BLOCK("INV"); |
| 161 |
break; |
| 162 |
default: |
| 163 |
TRACE_BLOCK("??"); |
| 164 |
break; |
| 165 |
} |
| 166 |
if (op.getType() != Type::INVALID) { |
| 167 |
TRACE_BLOCK(ToSyntax(op.getType()).c_str()); |
| 168 |
} |
| 169 |
} |
| 170 |
#endif // DEBUG_BLOCKS |
| 171 |
|
| 172 |
std::map<int32_t, Block *> |
| 173 |
Block::inferBlocks(ErrorHandler &errHandler, MemManager &mem, InstList &insts) { |
| 174 |
std::map<int32_t, Block *> blockStarts; |
| 175 |
BlockInference bi(blockStarts, &mem); |
| 176 |
int32_t binaryLength = 0; |
| 177 |
if (!insts.empty()) { |
| 178 |
Instruction *i = insts.back(); |
| 179 |
binaryLength = i->getPC(); |
| 180 |
binaryLength += i->hasInstOpt(InstOpt::COMPACTED) ? 8 : 16; |
| 181 |
} |
| 182 |
bi.run(errHandler, binaryLength, insts); |
| 183 |
#ifdef DEBUG_BLOCKS |
| 184 |
TRACE_BLOCK("**********************************************\n"); |
| 185 |
for (const auto& bitr : blockStarts) { |
| 186 |
auto instList = bitr.second->getInstList(); |
| 187 |
TRACE_BLOCK("BLOCK ", (int)bitr.first, " (", bitr.second, ") => ", |
| 188 |
(int)instList.size(), " instrs\n"); |
| 189 |
for (auto inst : instList) { |
| 190 |
auto mne = inst->getOpSpec().mnemonic.str(); |
| 191 |
TRACE_BLOCK(" ID", inst->getID(), " => PC", inst->getPC(), " ", mne); |
| 192 |
traceOperand(inst->getDestination()); |
| 193 |
|
| 194 |
for (int srcIx = 0; srcIx < (int)inst->getSourceCount(); srcIx++) { |
| 195 |
TRACE_BLOCK(", "); |
| 196 |
traceOperand(inst->getSource(srcIx)); |
| 197 |
} |
| 198 |
if (inst->hasInstOpt(InstOpt::EOT)) { |
| 199 |
TRACE_BLOCK(" {EOT}"); |
| 200 |
} |
| 201 |
TRACE_BLOCK("\n"); |
| 202 |
} |
| 203 |
} |
| 204 |
#endif // DEBUG_BLOCKS |
| 205 |
|
| 206 |
return blockStarts; |
| 207 |
} |
| 208 |
|
| 209 |
void Block::insertInstBefore(InstList::iterator itr, Instruction *i) { |
| 210 |
m_instructions.insert(itr, i); |
| 211 |
} |