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