1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "bytecode_emitter.h"
17 #include <bytecode_instruction-inl.h>
18 #include <macros.h>
19 #include <utils/bit_utils.h>
20 #include <utils/span.h>
21
22 namespace panda {
23
24 using Opcode = BytecodeInstruction::Opcode;
25 using Format = BytecodeInstruction::Format;
26 using BitImmSize = BytecodeEmitter::BitImmSize;
27
GetBitLengthUnsigned(uint32_t val)28 static inline constexpr BitImmSize GetBitLengthUnsigned(uint32_t val)
29 {
30 constexpr size_t BIT_4 = 4;
31 constexpr size_t BIT_8 = 8;
32
33 auto bitlen = MinimumBitsToStore(val);
34 if (bitlen <= BIT_4) {
35 return BitImmSize::BITSIZE_4;
36 }
37 if (bitlen <= BIT_8) {
38 return BitImmSize::BITSIZE_8;
39 }
40 return BitImmSize::BITSIZE_16;
41 }
42
GetBitLengthSigned(int32_t val)43 static inline constexpr BitImmSize GetBitLengthSigned(int32_t val)
44 {
45 constexpr int32_t INT4T_MIN = -8;
46 constexpr int32_t INT4T_MAX = 7;
47 constexpr int32_t INT8T_MIN = std::numeric_limits<int8_t>::min();
48 constexpr int32_t INT8T_MAX = std::numeric_limits<int8_t>::max();
49 constexpr int32_t INT16T_MIN = std::numeric_limits<int16_t>::min();
50 constexpr int32_t INT16T_MAX = std::numeric_limits<int16_t>::max();
51 if (INT4T_MIN <= val && val <= INT4T_MAX) {
52 return BitImmSize::BITSIZE_4;
53 }
54 if (INT8T_MIN <= val && val <= INT8T_MAX) {
55 return BitImmSize::BITSIZE_8;
56 }
57 if (INT16T_MIN <= val && val <= INT16T_MAX) {
58 return BitImmSize::BITSIZE_16;
59 }
60 return BitImmSize::BITSIZE_32;
61 }
62
EmitImpl(Span<uint8_t> buf,Span<const uint8_t> offsets)63 static inline void EmitImpl([[maybe_unused]] Span<uint8_t> buf, [[maybe_unused]] Span<const uint8_t> offsets) {}
64
65 template <typename Type, typename... Types>
EmitImpl(Span<uint8_t> buf,Span<const uint8_t> offsets,Type arg,Types...args)66 static void EmitImpl(Span<uint8_t> buf, Span<const uint8_t> offsets, Type arg, Types... args)
67 {
68 static constexpr uint8_t BYTEMASK = 0xFF;
69 static constexpr uint8_t BITMASK_4 = 0xF;
70 static constexpr size_t BIT_4 = 4;
71 static constexpr size_t BIT_8 = 8;
72 static constexpr size_t BIT_16 = 16;
73 static constexpr size_t BIT_32 = 32;
74 static constexpr size_t BIT_64 = 64;
75
76 uint8_t offset = offsets[0];
77 size_t bitlen = offsets[1] - offsets[0];
78 size_t byte_offset = offset / BIT_8;
79 size_t bit_offset = offset % BIT_8;
80 switch (bitlen) {
81 case BIT_4: {
82 auto val = static_cast<uint8_t>(arg);
83 buf[byte_offset] |= static_cast<uint8_t>(static_cast<uint8_t>(val & BITMASK_4) << bit_offset);
84 break;
85 }
86 case BIT_8: {
87 auto val = static_cast<uint8_t>(arg);
88 buf[byte_offset] = val;
89 break;
90 }
91 case BIT_16: {
92 auto val = static_cast<uint16_t>(arg);
93 buf[byte_offset] = val & BYTEMASK;
94 buf[byte_offset + 1] = val >> BIT_8;
95 break;
96 }
97 case BIT_32: {
98 auto val = static_cast<uint32_t>(arg);
99 for (size_t i = 0; i < sizeof(uint32_t); i++) {
100 buf[byte_offset + i] = (val >> (i * BIT_8)) & BYTEMASK;
101 }
102 break;
103 }
104 case BIT_64: {
105 auto val = static_cast<uint64_t>(arg);
106 for (size_t i = 0; i < sizeof(uint64_t); i++) {
107 buf[byte_offset + i] = (val >> (i * BIT_8)) & BYTEMASK;
108 }
109 break;
110 }
111 default: {
112 UNREACHABLE();
113 break;
114 }
115 }
116 EmitImpl(buf, offsets.SubSpan(1), args...);
117 }
118
119 #ifndef WITH_MOCK
120 template <Format format, typename It, typename... Types>
121 static size_t Emit(It out, Types... args);
122
Bind(const Label & label)123 void BytecodeEmitter::Bind(const Label &label)
124 {
125 *label.pc_ = pc_;
126 targets_.insert(label);
127 }
128
Build(std::vector<uint8_t> * output)129 BytecodeEmitter::ErrorCode BytecodeEmitter::Build(std::vector<uint8_t> *output)
130 {
131 ErrorCode res = CheckLabels();
132 if (res != ErrorCode::SUCCESS) {
133 return res;
134 }
135 res = ReserveSpaceForOffsets();
136 if (res != ErrorCode::SUCCESS) {
137 return res;
138 }
139 res = UpdateBranches();
140 if (res != ErrorCode::SUCCESS) {
141 return res;
142 }
143 *output = bytecode_;
144 return ErrorCode::SUCCESS;
145 }
146
147 /*
148 * NB! All conditional jumps with displacements not fitting into imm16
149 * are transformed into two instructions:
150 * jcc far # cc is any condiitonal code
151 * =>
152 * jCC next # CC is inverted cc
153 * jmp far
154 * next: # This label is inserted just after previous instruction.
155 */
ReserveSpaceForOffsets()156 BytecodeEmitter::ErrorCode BytecodeEmitter::ReserveSpaceForOffsets()
157 {
158 uint32_t bias = 0;
159 std::map<uint32_t, Label> new_branches;
160 auto it = branches_.begin();
161 while (it != branches_.end()) {
162 uint32_t insn_pc = it->first + bias;
163 auto label = it->second;
164
165 BytecodeInstruction insn(&bytecode_[insn_pc]);
166 auto opcode = insn.GetOpcode();
167 const auto ENCODED_IMM_SIZE = GetBitImmSizeByOpcode(opcode);
168 const auto REAL_IMM_SIZE = GetBitLengthSigned(EstimateMaxDistance(insn_pc, label.GetPc(), bias));
169
170 auto new_target = insn_pc;
171 size_t extra_bytes = 0;
172
173 if (REAL_IMM_SIZE > ENCODED_IMM_SIZE) {
174 auto res = DoReserveSpaceForOffset(insn, insn_pc, REAL_IMM_SIZE, &extra_bytes, &new_target);
175 if (res != ErrorCode::SUCCESS) {
176 return res;
177 }
178 }
179
180 new_branches.insert(std::make_pair(new_target, label));
181 if (extra_bytes > 0) {
182 bias += extra_bytes;
183 UpdateLabelTargets(insn_pc, extra_bytes);
184 }
185 it = branches_.erase(it);
186 }
187 branches_ = std::move(new_branches);
188 return ErrorCode::SUCCESS;
189 }
190
DoReserveSpaceForOffset(const BytecodeInstruction & insn,uint32_t insn_pc,BitImmSize expected_imm_size,size_t * extra_bytes_ptr,uint32_t * target_ptr)191 BytecodeEmitter::ErrorCode BytecodeEmitter::DoReserveSpaceForOffset(const BytecodeInstruction &insn, uint32_t insn_pc,
192 BitImmSize expected_imm_size,
193 size_t *extra_bytes_ptr, uint32_t *target_ptr)
194 {
195 auto opcode = insn.GetOpcode();
196 const auto INSN_SIZE = GetSizeByOpcode(opcode);
197
198 auto upd_op = GetSuitableJump(opcode, expected_imm_size);
199 if (upd_op != Opcode::LAST) {
200 *extra_bytes_ptr = GetSizeByOpcode(upd_op) - INSN_SIZE;
201 bytecode_.insert(bytecode_.begin() + insn_pc + INSN_SIZE, *extra_bytes_ptr, 0);
202 } else {
203 *extra_bytes_ptr = GetSizeByOpcode(Opcode::JMP_IMM32);
204 bytecode_.insert(bytecode_.begin() + insn_pc + INSN_SIZE, *extra_bytes_ptr, 0);
205
206 upd_op = RevertConditionCode(opcode);
207 if (upd_op == Opcode::LAST) {
208 UNREACHABLE(); // no revcc and no far opcode
209 return ErrorCode::INTERNAL_ERROR;
210 }
211 UpdateBranchOffs(&bytecode_[insn_pc], INSN_SIZE + GetSizeByOpcode(Opcode::JMP_IMM32));
212 *target_ptr = insn_pc + INSN_SIZE;
213 Emit<Format::IMM32>(bytecode_.begin() + *target_ptr, Opcode::JMP_IMM32, 0);
214 }
215 if (BytecodeInstruction(reinterpret_cast<uint8_t *>(&upd_op)).IsPrefixed()) {
216 Emit<BytecodeInstruction::Format::PREF_NONE>(bytecode_.begin() + insn_pc, upd_op);
217 } else {
218 Emit<BytecodeInstruction::Format::NONE>(bytecode_.begin() + insn_pc, upd_op);
219 }
220 return ErrorCode::SUCCESS;
221 }
222
UpdateBranches()223 BytecodeEmitter::ErrorCode BytecodeEmitter::UpdateBranches()
224 {
225 for (std::pair<const uint32_t, Label> &branch : branches_) {
226 uint32_t insn_pc = branch.first;
227 Label label = branch.second;
228 auto offset = static_cast<int32_t>(label.GetPc()) - static_cast<int32_t>(insn_pc);
229 UpdateBranchOffs(&bytecode_[insn_pc], offset);
230 }
231 return ErrorCode::SUCCESS;
232 }
233
UpdateLabelTargets(uint32_t pc,size_t bias)234 void BytecodeEmitter::UpdateLabelTargets(uint32_t pc, size_t bias)
235 {
236 pc_list_.push_front(pc);
237 Label fake(pc_list_.begin());
238 std::list<Label> updated_labels;
239 auto it = targets_.upper_bound(fake);
240 while (it != targets_.end()) {
241 Label label = *it;
242 it = targets_.erase(it);
243 *label.pc_ += bias;
244 updated_labels.push_back(label);
245 }
246 targets_.insert(updated_labels.begin(), updated_labels.end());
247 pc_list_.pop_front();
248 }
249
EstimateMaxDistance(uint32_t insn_pc,uint32_t target_pc,uint32_t bias) const250 int32_t BytecodeEmitter::EstimateMaxDistance(uint32_t insn_pc, uint32_t target_pc, uint32_t bias) const
251 {
252 int32_t distance = 0;
253 uint32_t end_pc = 0;
254 std::map<uint32_t, Label>::const_iterator it;
255 if (target_pc > insn_pc) {
256 it = branches_.lower_bound(insn_pc - bias);
257 distance = static_cast<int32_t>(target_pc - insn_pc);
258 end_pc = target_pc - bias;
259 } else if (target_pc < insn_pc) {
260 it = branches_.lower_bound(target_pc - bias);
261 distance = static_cast<int32_t>(target_pc - insn_pc);
262 end_pc = insn_pc - bias;
263 } else {
264 // Do we support branch to itself?
265 return 0;
266 }
267
268 while (it != branches_.end() && it->first < end_pc) {
269 auto insn = BytecodeInstruction(&bytecode_[it->first + bias]);
270 auto longest = GetSizeByOpcode(GetLongestJump(insn.GetOpcode()));
271 distance += static_cast<int32_t>(longest - insn.GetSize());
272 ++it;
273 }
274 return distance;
275 }
276
CheckLabels()277 BytecodeEmitter::ErrorCode BytecodeEmitter::CheckLabels()
278 {
279 for (const std::pair<const uint32_t, Label> &branch : branches_) {
280 const Label &label = branch.second;
281 if (targets_.find(label) == targets_.end()) {
282 return ErrorCode::UNBOUND_LABELS;
283 }
284 }
285 return ErrorCode::SUCCESS;
286 }
287
288 #include <bytecode_emitter_gen.h>
289 #endif // WITH_MOCK
290
291 } // namespace panda
292