Debian Codegraph @

visa/iga/IGALibrary/IR/Block.cpp

raw
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 }